Achieving Linear Convergence in Distributed Asynchronous Multi-agent Optimization
arXiv:1803.10359
Abstract
This papers studies multi-agent (convex and \emph{nonconvex}) optimization over static digraphs. We propose a general distributed \emph{asynchronous} algorithmic framework whereby i) agents can update their local variables as well as communicate with their neighbors at any time, without any form of coordination; and ii) they can perform their local computations using (possibly) delayed, out-of-sync information from the other agents. Delays need not be known to the agent or obey any specific profile, and can also be time-varying (but bounded). The algorithm builds on a tracking mechanism that is robust against asynchrony (in the above sense), whose goal is to estimate locally the average of agents' gradients. When applied to strongly convex functions, we prove that it converges at an R-linear (geometric) rate as long as the step-size is {sufficiently small}. A sublinear convergence rate is proved, when nonconvex problems and/or diminishing, {\it uncoordinated} step-sizes are considered. To the best of our knowledge, this is the first distributed algorithm with provable geometric convergence rate in such a general asynchronous setting. Preliminary numerical results demonstrate the efficacy of the proposed algorithm and validate our theoretical findings.
arXiv commentPart of this work has been presented to Allerton 2018; first version posted on arxiv on March 2018; revised Nov. 2018. To appear on IEEE Trans. on Automatic Control
References in corpus (7)
- HOGWILD!: A Lock-Free Approach to Parallelizing Stochastic Gradient Descent
- Asynchronous Parallel Stochastic Gradient for Nonconvex Optimization
- ARock: an Algorithmic Framework for Asynchronous Parallel Coordinate Updates
- Decentralized Quasi-Newton Methods
- Asynchronous Parallel Algorithms for Nonconvex Big-Data Optimization. Part II: Complexity and Numerical Results
- Newton-Raphson Consensus under asynchronous and lossy communications for peer-to-peer networks
- A Class of Parallel Doubly Stochastic Algorithms for Large-Scale Learning
Cited by in corpus (6)
- Distributed Non-Convex First-Order Optimization and Information Processing: Lower Complexity Bounds and Rate Optimal Algorithms
- Decentralized Stochastic Gradient Tracking for Non-convex Empirical Risk Minimization
- Fully Asynchronous Distributed Optimization with Linear Convergence in Directed Networks
- Optimization over time-varying directed graphs with row and column-stochastic matrices
- Asynchronous Decentralized Successive Convex Approximation
- A Primal-Dual Framework for Decentralized Stochastic Optimization