Asynchrony and Acceleration in Gossip Algorithms
arXiv:2011.02379
Abstract
This paper considers the minimization of a sum of smooth and strongly convex functions dispatched over the nodes of a communication network. Previous works on the subject either focus on synchronous algorithms, which can be heavily slowed down by a few slow nodes (the straggler problem), or consider a model of asynchronous operation (Boyd et al., 2006) in which adjacent nodes communicate at the instants of Poisson point processes. We have two main contributions. 1) We propose CACDM (a Continuously Accelerated Coordinate Dual Method), and for the Poisson model of asynchronous operation, we prove CACDM to converge to optimality at an accelerated convergence rate in the sense of Nesterov et Stich, 2017. In contrast, previously proposed asynchronous algorithms have not been proven to achieve such accelerated rate. While CACDM is based on discrete updates, the proof of its convergence crucially depends on a continuous time analysis. 2) We introduce a new communication scheme based on Loss-Networks, that is programmable in a fully asynchronous and decentralized way, unlike the Poisson model of asynchronous operation that does not capture essential aspects of asynchrony such as non-instantaneous communications and computations. Under this Loss-Network model of asynchrony, we establish for CDM (a Coordinate Dual Method) a rate of convergence in terms of the eigengap of the Laplacian of the graph weighted by local effective delays. We believe this eigengap to be a fundamental bottleneck for convergence rates of asynchronous optimization. Finally, we verify empirically that CACDM enjoys an accelerated convergence rate in the Loss-Network model of asynchrony.
References in corpus (14)
- HOGWILD!: A Lock-Free Approach to Parallelizing Stochastic Gradient Descent
- Geographic Gossip: Efficient Averaging for Sensor Networks
- Optimal algorithms for smooth and strongly convex distributed optimization in networks
- D: Decentralized Training over Decentralized Data
- DSA: Decentralized Double Stochastic Averaging Gradient Algorithm
- Optimization and Analysis of Distributed Averaging with Short Node Memory
- Asynchronous Decentralized Parallel Stochastic Gradient Descent
- Achieving Geometric Convergence for Distributed Optimization over Time-Varying Graphs
- Accelerated Decentralized Optimization with Local Updates for Smooth and Strongly Convex Objectives
- Advances in Asynchronous Parallel and Distributed Optimization
- A2BCD: An Asynchronous Accelerated Block Coordinate Descent Algorithm With Optimal Complexity
- Asynchronous Stochastic Coordinate Descent: Parallelism and Convergence Properties
- Asynchronous Gossip-Based Random Projection Algorithms Over Networks
- Accelerated Gossip in Networks of Given Dimension using Jacobi Polynomial Iterations