On the Convergence of Decentralized Gradient Descent
By Kun Yuan, Qing Ling, Wotao Yin. 2013
766 citations recorded by the source corpus.
Consider the consensus problem of minimizing $f(x)=\sum_{i=1}^n f_i(x)$, where $x\in{\mathbb{R}}^p$ and each $f_i$ is only known to the individual agent $i$ in a connected network of $n$ agents. To solve this problem and obtain the solution, all the agents collaborate with their neighbors through information exchange. This type of decentralized computation does not need a fusion center, offers better network load balance, and improves data privacy. This paper studies the decentralized gradient descent method [A. Nedic and A. Ozdaglar, IEEE Trans. Automat. Control, 54 (2009), pp. 48--61], in which each agent $i$ updates its local variable $x_{(i)}\in{\mathbb{R}}^n$ by combining the average of its neighbors' with a local negative-gradient step $-\alpha \nabla f_i(x_{(i)})$. The method is described by the iteration $ x_{(i)}(k+1) \gets \sum_{j=1}^n w_{ij} x_{(j)}(k) - \alpha \nabla f_i(x_{(i)}(k)),\ \text{for each agent}~i, $ where $w_{ij}$ is nonzero only if $i$ and $j$ are neighbors or $i=j$ and the matrix...
Subfields: Computer Networks and Communications, Optimization & Training, Federated & Distributed Learning
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Computer Networks and Communications
In Optimization & Training
- Aryan Mokhtari
- Peter Richtárik
- Nicolas Loizou
- Martin Jaggi
- Sebastian U. Stich
- Wotao Yin
- Angelia Nedić
- Ji Liu
In Federated & Distributed Learning
Citations in the corpus
- Local AdaAlter: Communication-Efficient Stochastic Gradient Descent with Adaptive Learning Rates (2019, background): “For example, decentralized SGD (Shi et al., 2014; Yuan et al., 2013; Lian et al., 2017) avoids congesting the central server node and improves the scalability by removing the server, and letting the workers communicate with their neighbours only.”
- Communication Efficient Decentralized Training with Multiple Local Updates (2019, methodology): “Decentralized (stochastic) algorithms used to tackle the failure of being centralized as a compromise and used to be studied as consensus optimization in the control community [28, 50, 36].”
- Robust and Communication-Efficient Collaborative Learning (2019, methodology): “• Decentralized SGD (DSGD) (Yuan et al., 2016): Each worker updates its decision variable as xi,t+1 = P j2Ni wijxj,t ↵ e rfi(xi,t).”
- 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.”
- Decentralized Online Learning: Take Benefits from Others’ Data without Sharing Your Own to Track Global Trend (2019, background): “:[ n ] , edges: E ), and is a doubly stochastic matrix [Wu et al., 2018, Zeng and Yin, 2018, Yuan et al., 2016], but may be not symmetric.”
- Cooperative SGD: A unified Framework for the Design and Analysis of Communication-Efficient SGD Algorithms (2018, methodology): “Decentralized averaging has a long history in the distributed and consensus optimization community (Tsitsik-lis 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): “[Yuan et al., 2016] further prove that DGD will converge to the neighborhood of a global optimum at a linear rate when used with a constant stepsize for strongly convex objectives.”
- cpSGD: Communication-efficient and differentially-private distributed SGD (2018, background): “In our paper we specifically consider the centralized setting, for the decentralized case the authors are referred to [36] and references therein.”
- D2: Decentralized Training over Decentralized Data (2018, background): “However, many recent theoretical results (Lian et al., 2017a;b; Nedic & Ozdaglar, 2009; Yuan et al., 2016) assume a bounded data variance across workers — when data hosted on different workers are very different, these approaches converge slowly, both empirically and theoretically.”
- Asynchronous Decentralized Parallel Stochastic Gradient Descent (2017, background): “(Yuan et al., 2016) studied decentralized gradient descent on convex and strongly convex objectives.”
- Can Decentralized Algorithms Outperform Centralized Algorithms? A Case Study for Decentralized Parallel Stochastic Gradient Descent (2017, methodology): “…have been studied as consensus optimization in the control community and used for preserving data privacy [Ram et al., 2009a, Yan et al., 2013, Yuan et al., 2016], for the application scenario where only the decentralized network is available, it is still an open question if decentralized…”
- Communication Compression for Decentralized Training (2018, background): “Both decentralized training and quantized (or compressed more generally) training have attracted intensive interests recently [Yuan et al., 2016, Zhao and Song, 2016, Lian et al., 2017a, Konečn`y and Richtárik, 2016, Alistarh et al., 2017].”
- Collaborative Deep Learning in Fixed Topology Networks (2017, methodology): “(Consensus with fixed step size) Under Assumptions 1 and 2, the iterates of CDSGD (Algorithm 1) satisfy ∀ k ∈ N : where The proof of this proposition can be adapted from [26, Lemma 1].”
- EXTRA: An Exact First-Order Algorithm for Decentralized Consensus Optimization (2014, methodology): “Recent work [36] relaxes such assumptions for decentralized gradient descent.”
- Towards More Efficient Stochastic Decentralized Learning: Faster Convergence and Sparse Communication (2018, methodology): “Related Work Deterministic Methods: Directly solving the primal objective, the consensus-based Decentralized Gradient Descent (DGD) method (Nedic & Ozdaglar, 2009; Yuan et al., 2016) has been proposed, yielding sublinear convergence rate.”
- Achieving Geometric Convergence for Distributed Optimization Over Time-Varying Graphs (2016, methodology): “References [60–62] use a difference structure to cancel the steady state error in decentralized gradient descent [47, 75], thereby developing the algorithm EXTRA and its proximal-gradient variant.”
- DSA: Decentralized Double Stochastic Averaging Gradient Algorithm (2015, methodology): “Choose i tn uniformly at random from the set { 1 , . . . , q n } .”
- Accelerating the Convergence Rates of Distributed Subgradient Methods with Adaptive Quantization (2018, methodology): “…attention during the last decade, mostly focusing on three classes of algorithms, namely, the alternating direction method of multipliers (ADMM) [1,17,33,35], distributed dual methods (mirror descent/dual averaging) [6,9,14,34,37], and distributed gradient algorithms [3–5,13,16,22,23,27,29,32,38].”
- An Exact Quantized Decentralized Gradient Descent Algorithm (2018, methodology): “Remark 2: We can derive the total communication cost for the vanilla DGD method ([11]), as well.”
- On Nonconvex Decentralized Gradient Descent (2016, methodology): “When fi’s are convex, the existing algorithms include the (sub)gradient methods [8], [10], [24], [37], [40], [46], [59], [65], and the primal-dual domain methods such as the decentralized alternating direction method of multipliers (DADMM) [9], [51], [52], DLM [31], and EXTRA [53], [54].”