mlsanityData to 7 Oct 2026

EF21 with Bells & Whistles: Six Algorithmic Extensions of Modern Error Feedback

arXiv 2110.03294 ↗First posted 7 Oct 2021cs.LG math.OCcited by 6

Not on the map. Why?

Abstract (arXiv)

First proposed by Seide (2014) as a heuristic, error feedback (EF) is a very popular mechanism for enforcing convergence of distributed gradient-based optimization methods enhanced with communication compression strategies based on the application of contractive compression operators. However, existing theory of EF relies on very strong assumptions (e.g., bounded gradients), and provides pessimistic convergence rates (e.g., while the best known rate for EF in the smooth nonconvex regime, and when full gradients are compressed, is O(1/T2/3), the rate of gradient descent in the same regime is O(1/T)). Recently, Richt'arik et al. (2021) proposed a new error feedback mechanism, EF21, based on the construction of a Markov compressor induced by a contractive compressor. EF21 removes the aforementioned theoretical deficiencies of EF and at the same time works better in practice. In this work we propose six practical extensions of EF21, all supported by strong convergence theory: partial participation, stochastic approximation, variance reduction, proximal setting, momentum, and bidirectional compression. To the best of our knowledge, several of these techniques have not been previously analyzed in combination with EF, and in cases where prior analysis exists -- such as for bidirectional compression -- our theoretical convergence guarantees significantly improve upon existing results.

Key facts. Cited by 6 papers in the map (data through 7 Oct 2026). Builds on 44 of its 59 references that are in the map. First posted on arXiv 7 Oct 2021.

Builds on

44 of 59 references.

References · 44

  1. 2019Advances and Open Problems in Federated Learningcited by 3,021
  2. 2017Accurate, Large Minibatch SGD: Training ImageNet in 1 Hourcited by 1,479
  3. 2016Federated Learning: Strategies for Improving Communication Efficiencycited by 1,461
  4. 2019Large Batch Optimization for Deep Learning: Training BERT in 76 minutescited by 671
  5. 2019Error Feedback Fixes SignSGD and other Gradient Compression Schemescited by 306
  6. 2019Lower Bounds for Non-Convex Stochastic Optimizationcited by 303
  7. 2018On the Optimization of Deep Networks: Implicit Acceleration by Overparameterizationcited by 280
  8. 2019PowerSGD: Practical Low-Rank Gradient Compression for Distributed Optimizationcited by 234
  9. 2019SGD: General Analysis and Improved Ratescited by 206
  10. 2020Client Selection in Federated Learning: Convergence Analysis and Power-of-Choice Selection Strategiescited by 196
  11. 2021Achieving Linear Speedup with Partial Worker Participation in Non-IID Federated Learningcited by 192
  12. 2020Better Theory for SGD in the Nonconvex Worldcited by 156
32 more
  1. 2020On Biased Compression for Distributed Learningcited by 140
  2. 2016Katyusha: The First Direct Acceleration of Stochastic Gradient Methodscited by 134
  3. 2021EF21: A New, Simpler, Theoretically Better, and Practically Faster Error Feedbackcited by 131
  4. 2020An Improved Analysis of Stochastic Gradient Descent with Momentumcited by 117
  5. 2020PAGE: A Simple and Optimal Probabilistic Gradient Estimator for Nonconvex Optimizationcited by 116
  6. 2019Distributed Learning with Compressed Gradient Differencescited by 110
  7. 2019Decentralized Deep Learning with Arbitrary Communication Compressioncited by 109
  8. 2019DoubleSqueeze: Parallel Stochastic Gradient Descent with Double-Pass Error-Compensated Compressioncited by 98
  9. 2020Acceleration for Compressed Gradient Descent in Distributed and Federated Optimizationcited by 90
  10. 2019Natural Compression for Distributed Deep Learningcited by 88
  11. 2020Variance-Reduced Methods for Machine Learningcited by 79
  12. 2021MARINA: Faster Non-Convex Distributed Learning with Compressioncited by 77
  13. 2019Stochastic Distributed Learning with Gradient Quantization and Variance Reductioncited by 64
  14. 2020Linearly Converging Error Compensated SGDcited by 61
  15. 2018Distributed learning with compressed gradientscited by 53
  16. 2021FedNL: Making Newton-Type Methods Applicable to Federated Learningcited by 50
  17. 2017Momentum and Stochastic Momentum for Stochastic Gradient, Newton, Proximal Point and Subspace Descent Methodscited by 49
  18. 2020Bidirectional compression in heterogeneous settings for distributed or federated learning with partial participation: tight convergence guaranteescited by 45
  19. 2020Error Compensated Distributed SGD Can Be Acceleratedcited by 45
  20. 2020A Better Alternative to Error Feedback for Communication-Efficient Distributed Learningcited by 42
  21. 2018A Simple Proximal Stochastic Gradient Method for Nonsmooth Nonconvex Optimizationcited by 33
  22. 2015An optimal randomized incremental gradient methodcited by 32
  23. 2021ZeroSARAH: Efficient Nonconvex Finite-Sum Optimization with Zero Full Gradient Computationcited by 28
  24. 2020A Unified Analysis of Stochastic Gradient Methods for Nonconvex Federated Optimizationcited by 27
  25. 2020CSER: Communication-efficient SGD with Error Resetcited by 27
  26. 2021Distributed Second Order Methods with Fast Rates and Compressed Communicationcited by 25
  27. 2019A unified variance-reduced accelerated gradient method for convex optimizationcited by 23
  28. 2021CANITA: Faster Rates for Distributed Convex Optimization with Communication Compressioncited by 23
  29. 2021FedPAGE: A Fast Local Stochastic Gradient Method for Communication-Efficient Federated Learningcited by 19
  30. 2019Gradient Descent with Compressed Iteratescited by 11
  31. 2021ANITA: An Optimal Loopless Accelerated Variance-Reduced Gradient Methodcited by 9
  32. 2014Coordinate Descent with Arbitrary Sampling II: Expected Separable Overapproximationcited by 5

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2022: 1; 2023: 1; 2024: 0; 2025: 2; 2026: 2.

6 papers.

  1. 2023Byzantine Robustness and Partial Participation Can Be Achieved at Once: Just Clip Gradient Differencescited by 5
  2. 2022Better Methods and Theory for Federated Learning: Compression, Client Selection and Heterogeneitycited by 0
  3. 2025Gradient Projection onto Historical Descent Directions for Communication-Efficient Federated Learningcited by 0
  4. 2025Improved Convergence in Parameter-Agnostic Error Feedback through Momentumcited by 0
  5. 2026SA-PEF: Step-Ahead Partial Error Feedback for Efficient Federated Learningcited by 0
  6. 2026A Tight Theory of Error Feedback Algorithms in Distributed Optimizationcited by 0