Distributed Asynchronous Deterministic and Stochastic Gradient Optimization Algorithms

By John N. Tsitsiklis, Dimitri P. Bertsekas, M. Athans. 1984

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 communications between processors plus communication delays are not too large.

Subfields: Optimization & Training, ML Systems & Hardware

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Optimization & Training

In ML Systems & Hardware

Citations in the corpus

Decentralized gradient methods: does topology matter? (2020, neutral): “This family of algorithms became originally popular in the control community, starting from the seminal work of Tsitsiklis et al. (1986) on distributed gradient methods.”
MATCHA: Speeding Up Decentralized SGD via Matching Decomposition Sampling (2019, background): “In the context of decentralized optimization, previous works have studied the error convergence in terms of iterations or communication rounds for decentralized gradient descent [1], [2], [3], [4], [5], [6], [7], [8] mostly for (strongly) convex loss functions.”
Cooperative SGD: A unified Framework for the Design and Analysis of Communication-Efficient SGD Algorithms (2018, background): “Decentralized averaging has a long history in the distributed and consensus optimization community (Tsitsiklis et al., 1986; Nedic & Ozdaglar, 2009; Duchi et al., 2012; Tsianos et al., 2012; Zeng & Yin, 2016; Yuan et al., 2016; Sirb & Ye, 2018).”
COLA: Decentralized Linear Learning (2018, background): “Research in decentralized optimization dates back to the 1980s with the seminal work of Bertsekas and Tsitsiklis, cf. [Tsitsiklis et al., 1986].”
Slow and Stale Gradients Can Win the Race: Error-Runtime Trade-offs in Distributed SGD (2018, neutral): “In [Tsitsiklis et al., 1986], a fully decentralized analysis was proposed that considers no central PS.”
Differentially Private Distributed Optimization (2014, background): “Categories and Subject Descriptors D.1.3 [Software]: Concurrent Programming—Distributed programming General Terms Algorithm Keywords Distributed Optimization, Differential Privacy, Iterative Consensus”
Optimal Distributed Online Prediction Using Mini-Batches (2010, background): “In an asynchronous distributed computing environment (see, e.g., Tsitsiklis et al., 1986; Bertsekas and Tsitsiklis, 1989), this can be quite wasteful.”
An Overview of Recent Progress in the Study of Distributed Multi-Agent Coordination (2012, background): “In addition, there are some recent reviews and progress reports given in the surveys [11]–[15] and the books [16]–[23], among others.”
Dual Averaging for Distributed Optimization: Convergence Analysis and Network Scaling (2010, neutral): “Earlier seminal work [1], [6], [7] analyzed algorithms for minimization of a smooth function known to several agents while distributing processing of components of the parameter vector .”
Perturbed Iterate Analysis for Asynchronous Stochastic Optimization (2015, background): “A large body of recent work has demonstrated that near-linear speedups are achievable, in theory and practice, on many common machine learning tasks [1– 8].”
Communication-Efficient Distributed Dual Coordinate Ascent (2014, background): “We see that thoughβK has a larger impact on the smaller batch size, it is still not enough to improve the mini-batch algorithms beyond what is achieved by COCOA and local-SGD.”
On the Convergence of Decentralized Gradient Descent (2013, background): “The study on decentralized optimization can be traced back to the seminal work in the 1980s [30, 31].”
Distributed Stochastic Subgradient Projection Algorithms for Convex Optimization (2008, neutral): “Also related are the optimization algorithms in [2, 31].”
Communication-efficient algorithms for decentralized and stochastic optimization (2017, neutral): “hui Lan et al. 1.3 Literature review Decentralized optimization has been extensively studied in recent years due to the emergence of large-scale networks. The seminal work on distributed optimization [60,59] has been followed by distributed incremental (sub)gradient methods and proximal methods [36,”
An asynchronous mini-batch algorithm for regularized stochastic optimization (2015, neutral): “able to split the data and distribute the computation across multiple processors or multiple cluster nodes [15]–[30].”
Distributed optimization over time-varying directed graphs (2013, positive): “mark that the matrices A(t) have a special structure that allows us to efﬁciently analyze their products. Speciﬁcally, we have the following properties of the matrices A(t) (see [2], [8], [15], [19], [33] for proofs of this and similar statements). Lemma 2: Suppose that the graph sequence fG(t)g is ”
Demystifying Parallel and Distributed Deep Learning (2018, background): “progress. HOGWILD has been proven to converge for sparse learning problems [205 ], where updates only modify small subsets of w, and generally 55 . Based on foundations of distributed asynchronous SGD[229], the proofs impose that (a) writeaccesses (adding gradients) are always atomic; (b) Lipschitz ”
Towards More Efficient Stochastic Decentralized Learning: Faster Convergence and Sparse Communication (2018, background): “While early work dates back to 1980’s (Tsitsiklis et al., 1986; Bertsekas & Tsitsiklis, 1989), consensus based gradient descent and dual averaging methods with sublinear convergence have made their debut (Nedic & Ozdaglar, 2009; Duchi et al.”