Linearly Converging Error Compensated SGD

Abstract

In this paper, we propose a unified analysis of variants of distributed SGD with arbitrary compressions and delayed updates. Our framework is general enough to cover different variants of quantized SGD, Error-Compensated SGD (EC-SGD) and SGD with delayed updates (D-SGD). Via a single theorem, we derive the complexity results for all the methods that fit our framework. For the existing methods, this theorem gives the best-known complexity results. Moreover, using our general scheme, we develop new variants of SGD that combine variance reduction or arbitrary sampling with error feedback and quantization and derive the convergence rates for these methods beating the state-of-the-art results. In order to illustrate the strength of our framework, we develop 16 new methods that fit this. In particular, we propose the first method called EC-SGD-DIANA that is based on error-feedback for biased compression operator and quantization of gradient differences and prove the convergence guarantees showing that EC-SGD-DIANA converges to the exact optimum asymptotically in expectation with constant learning rate for both convex and strongly convex objectives when workers compute full gradients of their loss functions. Moreover, for the case when the loss function of the worker has the form of finite sum, we modified the method and got a new one called EC-LSVRG-DIANA which is the first distributed stochastic method with error feedback and variance reduction that converges to the exact optimum asymptotically in expectation with a constant learning rate.

arXiv commentNeurIPS 2020, 99 pages

References in corpus (9)

• Federated Learning: Strategies for Improving Communication Efficiency
• Accurate, Large Minibatch SGD: Training ImageNet in 1 Hour
• Local SGD Converges Fast and Communicates Little
• Stochastic Distributed Learning with Gradient Quantization and Variance Reduction
• Unified Optimal Analysis of the (Stochastic) Gradient Method
• Is Local SGD Better than Minibatch SGD?
• Improved asynchronous parallel optimization analysis for stochastic incremental methods
• Distributed learning with compressed gradients
• Decentralized Deep Learning with Arbitrary Communication Compression

Cited by in corpus (15)

• Linear Convergence in Federated Learning: Tackling Client Heterogeneity and Sparse Gradients
• Recent theoretical advances in decentralized distributed convex optimization
• MARINA: Faster Non-Convex Distributed Learning with Compression
• 1-bit Adam: Communication Efficient Large-Scale Training with Adam's Convergence Speed
• What Do We Mean by Generalization in Federated Learning?
• FedNL: Making Newton-Type Methods Applicable to Federated Learning
• On Communication Compression for Distributed Optimization on Heterogeneous Data
• Moshpit SGD: Communication-Efficient Decentralized Training on Heterogeneous Unreliable Devices
• 1-bit LAMB: Communication Efficient Large-Scale Large-Batch Training with LAMB's Convergence Speed
• ErrorCompensatedX: error compensation for variance reduced algorithms
• Error Compensated Loopless SVRG, Quartz, and SDCA for Distributed Optimization
• Towards Tight Communication Lower Bounds for Distributed Optimisation
• Parallel and Distributed algorithms for ML problems
• Secure Distributed Training at Scale
• MURANA: A Generic Framework for Stochastic Variance-Reduced Optimization