Optimal Complexity in Decentralized Training
arXiv:2006.08085
Abstract
Decentralization is a promising method of scaling up parallel machine learning systems. In this paper, we provide a tight lower bound on the iteration complexity for such methods in a stochastic non-convex setting. Our lower bound reveals a theoretical gap in known convergence rates of many existing decentralized training algorithms, such as D-PSGD. We prove by construction this lower bound is tight and achievable. Motivated by our insights, we further propose DeTAG, a practical gossip-style decentralized algorithm that achieves the lower bound with only a logarithm gap. Empirically, we compare DeTAG with other decentralized algorithms on image classification tasks, and we show DeTAG enjoys faster convergence compared to baselines, especially on unshuffled data and in sparse networks.
References in corpus (14)
- ADADELTA: An Adaptive Learning Rate Method
- Towards Federated Learning at Scale: System Design
- Decentralized Stochastic Optimization and Gossip Algorithms with Compressed Communication
- A Unified Theory of Decentralized SGD with Changing Topology and Local Updates
- An improved convergence analysis for decentralized online stochastic non-convex optimization
- Moniqua: Modulo Quantized Communication in Decentralized SGD
- Asynchronous Accelerated Proximal Stochastic Gradient for Strongly Convex Distributed Finite Sums
- The Complexity of Making the Gradient Small in Stochastic Convex Optimization
- A Hybrid Variance-Reduced Method for Decentralized Stochastic Non-Convex Optimization
- Elastic Consistency: A General Consistency Model for Distributed Stochastic Gradient Descent
- Lower Bounds for Smooth Nonconvex Finite-Sum Optimization
- Theoretical Limits of Pipeline Parallel Optimization and Application to Distributed Deep Learning
- MixML: A Unified Analysis of Weakly Consistent Parallel Learning
- Oracle Complexity of Second-Order Methods for Finite-Sum Problems