Exact Diffusion for Distributed Optimization and Learning --- Part II: Convergence Analysis
arXiv:1702.05142
Abstract
Part I of this work [2] developed the exact diffusion algorithm to remove the bias that is characteristic of distributed solutions for deterministic optimization problems. The algorithm was shown to be applicable to a larger set of combination policies than earlier approaches in the literature. In particular, the combination matrices are not required to be doubly stochastic, which impose stringent conditions on the graph topology and communications protocol. In this Part II, we examine the convergence and stability properties of exact diffusion in some detail and establish its linear convergence rate. We also show that it has a wider stability range than the EXTRA consensus solution, meaning that it is stable for a wider range of step-sizes and can, therefore, attain faster convergence rates. Analytical examples and numerical simulations illustrate the theoretical findings.
arXiv comment18 pages; 5 figures; submitted for publication
References in corpus (10)
- On the Linear Convergence of the ADMM in Decentralized Consensus Optimization
- Diffusion Adaptation Strategies for Distributed Optimization and Learning over Networks
- Convergence Rate Analysis of Distributed Gossip (Linear Parameter) Estimation: Fundamental Limits and Tradeoffs
- Distributed Clustering and Learning Over Networks
- DQM: Decentralized Quadratically Approximated Alternating Direction Method of Multipliers
- A Sparsity-Aware Adaptive Algorithm for Distributed Learning
- Dictionary Learning over Distributed Models
- ExtraPush for convex smooth decentralized optimization over directed networks
- On the Linear Convergence of Distributed Optimization over Directed Graphs
- Exact Diffusion for Distributed Optimization and Learning --- Part I: Algorithm Development
Cited by in corpus (4)
- Exact Diffusion for Distributed Optimization and Learning --- Part I: Algorithm Development
- Distributed heavy-ball: A generalization and acceleration of first-order methods with gradient tracking
- A Unification and Generalization of Exact Distributed First Order Methods
- Variance-Reduced Stochastic Learning by Networked Agents under Random Reshuffling