Distributed asynchronous deterministic and stochastic gradient optimization algorithms
IEEE Transactions on Automatic ControlPublished 1 September 1986
John N. Tsitsiklis, Dimitri P. Bertsekas, Michael Athans
Citations2,021
SJR quartileQ1
SJR score3.80
SNIP2.59
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
Abstract
We present a model for asynchronous distributed computation and then proceed to analyze the convergence of natural asynchronous distributed versions of a large class of deterministic and stochastic gradient-like algorithms. We show that such algorithms retain the desirable convergence properties of their centralized counterparts, provided that the time between consecutive interprocessor communications and the communication delays are not too large.
Keywords
Computer ScienceEngineering
Theory and Practice of Recursive Identification
4,008 Citations1983Lennart Ljung, Torsten Söderström
Methods of recursive identification deal with the problem of building mathematical models of signals and systems on-line, at the same time as data is being collected.
Applied mathematical sciencesStochastic Approximation Methods for Constrained and Unconstrained Systems
1,482 Citations1978Harold J. Kushner, Dean S. Clark
The Robbins-Monro and Kiefer-Wolfowitz Algorithm for Inequality Constraints and the Weak Convergence of Probability Measures, a simple example, and the Convergence Theorem, a proof of the Main Theorem.
IEEE Transactions on Automatic ControlAnalysis of recursive stochastic algorithms
1,468 Citations1977Lennart Ljung
It is shown how a deterministic differential equation can be associated with the algorithm and examples of applications of the results to problems in identification and adaptive control.
PROBLEMS IN DECENTRALIZED DECISION MAKING AND COMPUTATION
1,360 Citations1984Ιωάννης Τσιτσικλής
A scheme whereby a set of decision makers (processors) exchange and update tentative decisions which minimize a common cost function, given information they possess is considered; it is shown that they are guaranteed to converge to consensus.
Some complexity questions related to distributive computing(Preliminary Report)
1,062 Citations1979Andrew Chi-Chih Yao
The quantity of interest, which measures the information exchange necessary for computing f, is the minimum number of bits exchanged in any algorithm.
IRE Transactions on Communications SystemsA Minimum Delay Routing Algorithm Using Distributed Computation
650 Citations1977Robert G. Gallager
A new global convergence theorem for noncontinuous iteration algorithms is developed that converges, with successive updates of the routing tables, to the minimum average delay over all routing assignments.
Journal of the ACMAsynchronous Iterative Methods for Multiprocessors
521 Citations1978Gérard M. Baudet
A class of asynchronous iterative methods is presented for solving a system of equations corresponding to a parallel implementation on a multiprocessor system with no synchronization between cooperating processes to show clearly the advantage of purely asynchronous Iterative methods.
Journal of the London Mathematical SocietyPROBABILITY AND POTENTIALS
330 Citations1967David G. Kendall
IEEE Transactions on Automatic ControlThe convergence of AML
253 Citations1979Victor Solo
It is shown that provided a certain positive real condition is satisfied, the AML recursion for the parameters of a scalar ARMAX time series model converges with probability one without the need of monitoring.
Mathematical ProgrammingDistributed asynchronous computation of fixed points
228 Citations1983Dimitri P. Bertsekas
A general convergence theorem is provided for algorithms of this type including the calculation of fixed points of contraction and monotone mappings arising in linear and nonlinear systems of equations, optimization problems, shortest path problems, and dynamic programming.
IEEE Transactions on Automatic ControlDistributed dynamic programming
218 Citations1982Dimitri P. Bertsekas
FigshareSynchronized and asynchronous parallel algorithms for multiprocessors
87 Citations2018H. T. Kung
Parallel algorithms for multiprocessors are classified into synchronized and asynchronous algorithms, and several examples of the two types of algorithms are described in depth.
Information and ControlOn the complexity of designing distributed protocols
48 Citations1982Christos H. Papadimitriou, John N. Tsitsiklis
It is shown that deciding whether two distant agents can arrive at compatible decisions without any communication can be done in polynomial time if there are two possible decisions for each agent, but is NP-complete if one agent has three or more alternatives.
Lecture notes in control and information sciencesConvergence theories of distributed iterative processes: A survey
23 Citations1986Dimitri P. Bertsekas, John N. Tsitsiklis +1 more
This work considers a model of distributed iterative algorithms whereby several processors participate in the computation while collecting, possibly stochastic information from the environment or other processors via communication links.
Algorithms and Complexity
9 Citations2020Mark Wallace
Distributed asynchronous optimal routing in data networks
6 Citations1984John N. Tsitsiklis, Dimitri P. Bertsekas