ADOM: Accelerated Decentralized Optimization Method for Time-Varying Networks
arXiv:2102.09234
Abstract
We propose ADOM - an accelerated method for smooth and strongly convex decentralized optimization over time-varying networks. ADOM uses a dual oracle, i.e., we assume access to the gradient of the Fenchel conjugate of the individual loss functions. Up to a constant factor, which depends on the network structure only, its communication complexity is the same as that of accelerated Nesterov gradient method (Nesterov, 2003). To the best of our knowledge, only the algorithm of Rogozin et al. (2019) has a convergence rate with similar properties. However, their algorithm converges under the very restrictive assumption that the number of network changes can not be greater than a tiny percentage of the number of iterations. This assumption is hard to satisfy in practice, as the network topology changes usually can not be controlled. In contrast, ADOM merely requires the network to stay connected throughout time.
References in corpus (9)
- Communication-Efficient Learning of Deep Networks from Decentralized Data
- Federated Learning: Strategies for Improving Communication Efficiency
- TUDataset: A collection of benchmark datasets for learning with graphs
- The Error-Feedback Framework: Better Rates for SGD with Delayed Gradients and Compressed Communication
- On Biased Compression for Distributed Learning
- Multi-consensus Decentralized Accelerated Gradient Descent
- Recent theoretical advances in decentralized distributed convex optimization
- Decentralized Accelerated Gradient Methods With Increasing Penalty Parameters
- Error Compensated Distributed SGD Can Be Accelerated
Cited by in corpus (5)
- Recent theoretical advances in decentralized distributed convex optimization
- Accelerated Gradient Tracking over Time-varying Graphs for Decentralized Optimization
- Lower Bounds and Optimal Algorithms for Smooth and Strongly Convex Decentralized Optimization Over Time-Varying Networks
- Near-Optimal Decentralized Algorithms for Saddle Point Problems over Time-Varying Networks
- Optimal Gradient Tracking for Decentralized Optimization