A Better Alternative to Error Feedback for Communication-Efficient Distributed Learning

Abstract

Modern large-scale machine learning applications require stochastic optimization algorithms to be implemented on distributed compute systems. A key bottleneck of such systems is the communication overhead for exchanging information across the workers, such as stochastic gradients. Among the many techniques proposed to remedy this issue, one of the most successful is the framework of compressed communication with error feedback (EF). EF remains the only known technique that can deal with the error induced by contractive compressors which are not unbiased, such as Top-$K$. In this paper, we propose a new and theoretically and practically better alternative to EF for dealing with contractive compressors. In particular, we propose a construction which can transform any contractive compressor into an induced unbiased compressor. Following this transformation, existing methods able to work with unbiased compressors can be applied. We show that our approach leads to vast improvements over EF, including reduced memory requirements, better communication complexity guarantees and fewer assumptions. We further extend our results to federated learning with partial participation following an arbitrary distribution over the nodes, and demonstrate the benefits thereof. We perform several numerical experiments which validate our theoretical findings.

arXiv comment10 pages, 7 figures, published as a conference paper at ICLR 2021

References in corpus (21)

• On the Convergence of Adam and Beyond
• Deep Gradient Compression: Reducing the Communication Bandwidth for Distributed Training
• QSGD: Communication-Efficient SGD via Gradient Quantization and Encoding
• SCAFFOLD: Stochastic Controlled Averaging for Federated Learning
• TernGrad: Ternary Gradients to Reduce Communication in Distributed Deep Learning
• FedPAQ: A Communication-Efficient Federated Learning Method with Periodic Averaging and Quantization
• Sparsified SGD with Memory
• Don't Use Large Mini-Batches, Use Local SGD
• Decentralized Stochastic Optimization and Gossip Algorithms with Compressed Communication
• PowerSGD: Practical Low-Rank Gradient Compression for Distributed Optimization
• Distributed Learning with Compressed Gradient Differences
• Unified Convergence Analysis of Stochastic Momentum Methods for Convex and Non-convex Optimization
• Stochastic Distributed Learning with Gradient Quantization and Variance Reduction
• The Error-Feedback Framework: Better Rates for SGD with Delayed Gradients and Compressed Communication
• Acceleration for Compressed Gradient Descent in Distributed and Federated Optimization
• Natural Compression for Distributed Deep Learning
• Unified Optimal Analysis of the (Stochastic) Gradient Method
• On Biased Compression for Distributed Learning
• Is Local SGD Better than Minibatch SGD?
• Distributed learning with compressed gradients
• Nonconvex Variance Reduced Optimization with Arbitrary Sampling

Cited by in corpus (8)

• A Field Guide to Federated Optimization
• Optimal Client Sampling for Federated Learning
• What Do We Mean by Generalization in Federated Learning?
• FedSKETCH: Communication-Efficient and Private Federated Learning via Sketching
• Bidirectional compression in heterogeneous settings for distributed or federated learning with partial participation: tight convergence guarantees
• Quantized and Asynchronous Federated Learning
• Leveraging Spatial and Temporal Correlations in Sparsified Mean Estimation
• Communication-Efficient Distributed Learning via Sparse and Adaptive Stochastic Gradient