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 (35)
- ADADELTA: An Adaptive Learning Rate Method
- Communication-Efficient Learning of Deep Networks from Decentralized Data
- MCMC using Hamiltonian dynamics
- Federated Learning: Strategies for Improving Communication Efficiency
- Federated Learning with Non-IID Data
- On the Convergence of FedAvg on Non-IID Data
- Towards Federated Learning at Scale: System Design
- SPIDER: Near-Optimal Non-Convex Optimization via Stochastic Path Integrated Differential Estimator
- Don't Use Large Mini-Batches, Use Local SGD
- Optimal algorithms for smooth and strongly convex distributed optimization in networks
- Decentralized Stochastic Optimization and Gossip Algorithms with Compressed Communication
- Communication Compression for Decentralized Training
- D: Decentralized Training over Decentralized Data
- A Unified Theory of Decentralized SGD with Changing Topology and Local Updates
- Cooperative SGD: A unified Framework for the Design and Analysis of Communication-Efficient SGD Algorithms
- Stochastic Gradient Push for Distributed Deep Learning
- Communication Complexity of Distributed Convex Learning and Optimization
- DoubleSqueeze: Parallel Stochastic Gradient Descent with Double-Pass Error-Compensated Compression
- An improved convergence analysis for decentralized online stochastic non-convex optimization
- Distributed Non-Convex First-Order Optimization and Information Processing: Lower Complexity Bounds and Rate Optimal Algorithms
- Graph Oracle Models, Lower Bounds, and Gaps for Parallel Stochastic Optimization
- A Lower Bound for the Optimization of Finite Sums
- How To Make the Gradients Small Stochastically: Even Faster Convex and Nonconvex SGD
- MATCHA: Speeding Up Decentralized SGD via Matching Decomposition Sampling
- Moniqua: Modulo Quantized Communication in Decentralized SGD
- Asynchronous Accelerated Proximal Stochastic Gradient for Strongly Convex Distributed Finite Sums
- Distributed Learning over Unreliable Networks
- The Complexity of Making the Gradient Small in Stochastic Convex Optimization
- Parallelization does not Accelerate Convex Optimization: Adaptivity Lower Bounds for Non-smooth Convex Minimization
- 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