EF21: A New, Simpler, Theoretically Better, and Practically Faster Error Feedback

Abstract

Error feedback (EF), also known as error compensation, is an immensely popular convergence stabilization mechanism in the context of distributed training of supervised machine learning models enhanced by the use of contractive communication compression mechanisms, such as Top-$k$. First proposed by Seide et al (2014) as a heuristic, EF resisted any theoretical understanding until recently [Stich et al., 2018, Alistarh et al., 2018]. However, all existing analyses either i) apply to the single node setting only, ii) rely on very strong and often unreasonable assumptions, such global boundedness of the gradients, or iterate-dependent assumptions that cannot be checked a-priori and may not hold in practice, or iii) circumvent these issues via the introduction of additional unbiased compressors, which increase the communication cost. In this work we fix all these deficiencies by proposing and analyzing a new EF mechanism, which we call EF21, which consistently and substantially outperforms EF in practice. Our theoretical analysis relies on standard assumptions only, works in the distributed heterogeneous data setting, and leads to better and more meaningful rates. In particular, we prove that EF21 enjoys a fast $O(1/T)$ convergence rate for smooth nonconvex problems, beating the previous bound of $O(1/T^{2/3})$, which was shown a bounded gradients assumption. We further improve this to a fast linear rate for PL functions, which is the first linear convergence result for an EF-type method not relying on unbiased compressors. Since EF has a large number of applications where it reigns supreme, we believe that our 2021 variant, EF21, can a large impact on the practice of communication efficient distributed learning.

arXiv comment37 pages, 5 algorithms, 3 Theorems, 8 Lemmas, 15 Figures

References in corpus (17)

• PyTorch: An Imperative Style, High-Performance Deep Learning Library
• Sparsified SGD with Memory
• Error Feedback Fixes SignSGD and other Gradient Compression Schemes
• DoubleSqueeze: Parallel Stochastic Gradient Descent with Double-Pass Error-Compensated Compression
• 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
• Natural Compression for Distributed Deep Learning
• On Biased Compression for Distributed Learning
• Distributed learning with compressed gradients
• A Unified Analysis of Stochastic Gradient Methods for Nonconvex Federated Optimization
• PAGE: A Simple and Optimal Probabilistic Gradient Estimator for Nonconvex Optimization
• MARINA: Faster Non-Convex Distributed Learning with Compression
• On the Convergence of SGD with Biased Gradients
• Distributed Second Order Methods with Fast Rates and Compressed Communication
• Bidirectional compression in heterogeneous settings for distributed or federated learning with partial participation: tight convergence guarantees
• Error Compensated Distributed SGD Can Be Accelerated

Cited by in corpus (12)

• Gradient Compression and Correlation Driven Federated Learning for Wireless Traffic Prediction
• PAGE: A Simple and Optimal Probabilistic Gradient Estimator for Nonconvex Optimization
• ScionFL: Efficient and Robust Secure Quantized Aggregation
• CANITA: Faster Rates for Distributed Convex Optimization with Communication Compression
• Activations and Gradients Compression for Model-Parallel Training
• On the Convergence of Federated Learning Algorithms without Data Similarity
• Federated Learning is Better with Non-Homomorphic Encryption
• Sparse Training for Federated Learning with Regularized Error Correction
• Permutation Compressors for Provably Faster Distributed Nonconvex Optimization
• Communication-Compressed Adaptive Gradient Method for Distributed Nonconvex Optimization
• Det-CGD: Compressed Gradient Descent with Matrix Stepsizes for Non-Convex Optimization
• Parallel Momentum Methods Under Biased Gradient Estimations