A Linearly Convergent Algorithm for Decentralized Optimization: Sending Less Bits for Free!
arXiv:2011.01697
Abstract
Decentralized optimization methods enable on-device training of machine learning models without a central coordinator. In many scenarios communication between devices is energy demanding and time consuming and forms the bottleneck of the entire system. We propose a new randomized first-order method which tackles the communication bottleneck by applying randomized compression operators to the communicated messages. By combining our scheme with a new variance reduction technique that progressively throughout the iterations reduces the adverse effect of the injected quantization noise, we obtain the first scheme that converges linearly on strongly convex decentralized problems while using compressed communication only. We prove that our method can solve the problems without any increase in the number of communications compared to the baseline which does not perform any communication compression while still allowing for a significant compression factor which depends on the conditioning of the problem and the topology of the network. Our key theoretical findings are supported by numerical experiments.
References in corpus (17)
- Communication-Efficient Learning of Deep Networks from Decentralized Data
- On the Linear Convergence of the ADMM in Decentralized Consensus Optimization
- Sparsified SGD with Memory
- 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
- A Universal Catalyst for First-Order Optimization
- Error Feedback Fixes SignSGD and other Gradient Compression Schemes
- DSA: Decentralized Double Stochastic Averaging Gradient Algorithm
- Distributed Mean Estimation with Limited Communication
- An Exact Quantized Decentralized Gradient Descent Algorithm
- Variance-Reduced Decentralized Stochastic Optimization with Accelerated Convergence
- Stochastic Distributed Learning with Gradient Quantization and Variance Reduction
- The Error-Feedback Framework: Better Rates for SGD with Delayed Gradients and Compressed Communication
- COLA: Decentralized Linear Learning
- : Decentralization Meets Error-Compensated Compression
- Breaking the Span Assumption Yields Fast Finite-Sum Minimization