Achieving Geometric Convergence for Distributed Optimization Over Time-Varying Graphs
By Angelia Nedić, Alexander Olshevsky, Wei Shi. 2016
1,137 citations recorded by the source corpus.
This paper considers the problem of distributed optimization over time-varying graphs. For the case of undirected graphs, we introduce a distributed algorithm, referred to as DIGing, based on a combination of a distributed inexact gradient method and a gradient tracking technique. The DIGing algorithm uses doubly stochastic mixing matrices and employs fixed step-sizes and, yet, drives all the agents' iterates to a global and consensual minimizer. When the graphs are directed, in which case the implementation of doubly stochastic mixing matrices is unrealistic, we construct an algorithm that incorporates the push-sum protocol into the DIGing structure, thus obtaining Push-DIGing algorithm. The Push-DIGing uses column stochastic matrices and fixed step-sizes, but it still converges to a global and consensual minimizer. Under the strong convexity assumption, we prove that the algorithms converge at R-linear (geometric) rates as long as the step-sizes do not exceed some upper bounds. We establish explicit estimates for the convergence rates. When the graph is undirected it shows that DIGing scales polynomially in the number of agents. We also provide some numerical experiments to demonstrate the efficacy of the proposed algorithms and to validate our theoretical findings.
Subfields: Computer Networks and Communications, Optimization & Training, Algorithms & Complexity
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
- Angelia Nedić
- Martin Jaggi
- Alexander Olshevsky
- Sebastian U. Stich
- Wei Shi
- Ali H. Sayed
- Anastasia Koloskova
- Ji Liu
In Optimization & Training
- Martin Jaggi
- Sebastian U. Stich
- Nicolas Loizou
- Peter Richtárik
- Anastasia Koloskova
- Ji Liu
- Francis R. Bach
- Aryan Mokhtari
In Algorithms & Complexity
- Martin Jaggi
- Angelia Nedić
- Guannan Qu
- Na Li
- Sebastian U. Stich
- Anastasia Koloskova
- Ali H. Sayed
- Giovanni Neglia
Citations in the corpus
- A Unified Theory of Decentralized SGD with Changing Topology and Local Updates (2020, methodology): “However, as we require W to be symmetric, our setting is less general than the one considered in (Nedić et al., 2017; Xi & Khan, 2017; Saadatniaki et al., 2018; Assran & Rabbat, 2018; Scutari & Sun, 2019; Assran et al., 2019).”
- GADMM: Fast and Communication Efficient Framework for Distributed Machine Learning (2019, background): “variables to its neighboring nodes per iteration and achieves O(1= p k) convergence rate. In contrast to that, in D-GADMM, only primal variables are shared with neighbors at each iteration. Finally, (Nedic et al., 2017) proposed an algorithm that achieves a linear convergence speed but for strongly ”
- DoubleSqueeze: Parallel Stochastic Gradient Descent with Double-Pass Error-Compensated Compression (2019, neutral): “For the random topology decentralized algorithms, the communication network changes over time, for example, (Nedi ´ c & Olshevsky, 2015; Nedic et al., 2017; ?”
- Distributed Learning over Unreliable Networks (2018, background): “llowed to change the communication network based on the availability of the network. There are many works [Boyd et al., 2006, Li and Zhang, 2010, Lobel and Ozdaglar, 2011, Nedic´ and Olshevsky, 2015, Nedic et al., 2017] studying the random topology decentralized SGD algorithms under different assump”
- COLA: Decentralized Linear Learning (2018, methodology): “One can observe that for both generally and strongly convex objectives, C O L A significantly outperforms DIGing and decentralized ADMM in terms of number of communication rounds and computation time.”
- Optimal Algorithms for Non-Smooth Distributed Optimization in Networks (2018, background): “Most often, these algorithms alternate between local and incremental improvement steps (such as gradient steps) with communication steps between nodes in the network, and come with a variety of convergence rates (see for example [5, 4, 6, 7]).”
- 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].”
- Compressed Distributed Gradient Descent: Communication-Efficient Consensus over Networks (2018, background): “, achieving the same O(1/k) convergence rate with constant step-size [18] or even under time-varying network graphs [19]).”
- Push–Pull Gradient Methods for Distributed Optimization in Networks (2018, methodology): “Unlike the push-sum type protocol used in the previous literature [9], [14], our algorithm uses a row stochastic matrix for the mixing of the decision variables, while it employs a column stochastic matrix for tracking the average gradients.”
- Harnessing smoothness to accelerate distributed optimization (2016, background): “Also, our way of proving the linear convergence rate is inherently different from that of [27], [28].”
- Optimization over time-varying directed graphs with row and column-stochastic matrices (2018, methodology): “classification problem in a distributed manner, agents initialize their states xi 0 according to IID zero-mean Gaussian random variables with variance 9. The performance of TV-ABalong with Push-DIGing [26], and subgradientpush [18] (with constant and diminishing step-sizes) is shown in Fig. 3 with th”
- Multiagent Fully Decentralized Value Function Learning With Linear Convergence Rates (2018, background): “Several other works employ instead a gradient tracking strategy [27], [28], [33].”
- A Non-Asymptotic Analysis of Network Independence for Distributed Stochastic Gradient Descent (2019, background): “1) has been studied extensively in the literature under various distributed algorithms [43, 25, 26, 19, 15, 16, 39, 11, 35, 23, 45, 34], among which the distributed gradient descent (DGD) method proposed in [25] has drawn the greatest attention.”