Error Compensated Distributed SGD Can Be Accelerated

Abstract

Gradient compression is a recent and increasingly popular technique for reducing the communication cost in distributed training of large-scale machine learning models. In this work we focus on developing efficient distributed methods that can work for any compressor satisfying a certain contraction property, which includes both unbiased (after appropriate scaling) and biased compressors such as RandK and TopK. Applied naively, gradient compression introduces errors that either slow down convergence or lead to divergence. A popular technique designed to tackle this issue is error compensation/error feedback. Due to the difficulties associated with analyzing biased compressors, it is not known whether gradient compression with error compensation can be combined with Nesterov's acceleration. In this work, we show for the first time that error compensated gradient compression methods can be accelerated. In particular, we propose and study the error compensated loopless Katyusha method, and establish an accelerated linear convergence rate under standard assumptions. We show through numerical experiments that the proposed method converges with substantially fewer communication rounds than previous error compensated algorithms.

24 pages, 6 figures

References in corpus (14)

• Federated Learning: Strategies for Improving Communication Efficiency
• Federated Optimization: Distributed Machine Learning for On-Device Intelligence
• QSGD: Communication-Efficient SGD via Gradient Quantization and Encoding
• Federated Learning of a Mixture of Global and Local Models
• Sparsified SGD with Memory
• Communication Compression for Decentralized Training
• DoubleSqueeze: Parallel Stochastic Gradient Descent with Double-Pass Error-Compensated Compression
• Distributed Delayed Stochastic Optimization
• Distributed Learning with Compressed Gradient Differences
• Stochastic Distributed Learning with Gradient Quantization and Variance Reduction
• The Error-Feedback Framework: Better Rates for SGD with Delayed Gradients and Compressed Communication
• On Biased Compression for Distributed Learning
• Is Local SGD Better than Minibatch SGD?
• L-SVRG and L-Katyusha with Arbitrary Sampling

Cited by in corpus (7)

• A Field Guide to Federated Optimization
• EF21: A New, Simpler, Theoretically Better, and Practically Faster Error Feedback
• ADOM: Accelerated Decentralized Optimization Method for Time-Varying Networks
• CANITA: Faster Rates for Distributed Convex Optimization with Communication Compression
• Moshpit SGD: Communication-Efficient Decentralized Training on Heterogeneous Unreliable Devices
• Smoothness Matrices Beat Smoothness Constants: Better Communication Compression Techniques for Distributed Optimization
• Parallel and Distributed algorithms for ML problems