# EF21 with Bells & Whistles: Six Algorithmic Extensions of Modern Error Feedback arXiv: https://arxiv.org/abs/2110.03294 ยท HTML: https://mlsanity.com/paper/2110.03294/ ## Key facts - Cited by 8 papers in the map (data through 14 Oct 2026). - Builds on 44 of its 59 references that are in the map. - First posted on arXiv 7 Oct 2021. ## Builds on (most cited first, 30 of 44) - [Advances and Open Problems in Federated Learning](https://mlsanity.com/paper/1912.04977/) (2019) - [Accurate, Large Minibatch SGD: Training ImageNet in 1 Hour](https://mlsanity.com/paper/1706.02677/) (2017) - [Federated Learning: Strategies for Improving Communication Efficiency](https://mlsanity.com/paper/1610.05492/) (2016) - [Large Batch Optimization for Deep Learning: Training BERT in 76 minutes](https://mlsanity.com/paper/1904.00962/) (2019) - [Error Feedback Fixes SignSGD and other Gradient Compression Schemes](https://mlsanity.com/paper/1901.09847/) (2019) - [Lower Bounds for Non-Convex Stochastic Optimization](https://mlsanity.com/paper/1912.02365/) (2019) - [On the Optimization of Deep Networks: Implicit Acceleration by Overparameterization](https://mlsanity.com/paper/1802.06509/) (2018) - [PowerSGD: Practical Low-Rank Gradient Compression for Distributed Optimization](https://mlsanity.com/paper/1905.13727/) (2019) - [SGD: General Analysis and Improved Rates](https://mlsanity.com/paper/1901.09401/) (2019) - [Client Selection in Federated Learning: Convergence Analysis and Power-of-Choice Selection Strategies](https://mlsanity.com/paper/2010.01243/) (2020) - [Achieving Linear Speedup with Partial Worker Participation in Non-IID Federated Learning](https://mlsanity.com/paper/2101.11203/) (2021) - [Better Theory for SGD in the Nonconvex World](https://mlsanity.com/paper/2002.03329/) (2020) - [On Biased Compression for Distributed Learning](https://mlsanity.com/paper/2002.12410/) (2020) - [Katyusha: The First Direct Acceleration of Stochastic Gradient Methods](https://mlsanity.com/paper/1603.05953/) (2016) - [EF21: A New, Simpler, Theoretically Better, and Practically Faster Error Feedback](https://mlsanity.com/paper/2106.05203/) (2021) - [An Improved Analysis of Stochastic Gradient Descent with Momentum](https://mlsanity.com/paper/2007.07989/) (2020) - [PAGE: A Simple and Optimal Probabilistic Gradient Estimator for Nonconvex Optimization](https://mlsanity.com/paper/2008.10898/) (2020) - [Distributed Learning with Compressed Gradient Differences](https://mlsanity.com/paper/1901.09269/) (2019) - [Decentralized Deep Learning with Arbitrary Communication Compression](https://mlsanity.com/paper/1907.09356/) (2019) - [DoubleSqueeze: Parallel Stochastic Gradient Descent with Double-Pass Error-Compensated Compression](https://mlsanity.com/paper/1905.05957/) (2019) - [Natural Compression for Distributed Deep Learning](https://mlsanity.com/paper/1905.10988/) (2019) - [Acceleration for Compressed Gradient Descent in Distributed and Federated Optimization](https://mlsanity.com/paper/2002.11364/) (2020) - [Variance-Reduced Methods for Machine Learning](https://mlsanity.com/paper/2010.00892/) (2020) - [MARINA: Faster Non-Convex Distributed Learning with Compression](https://mlsanity.com/paper/2102.07845/) (2021) - [Stochastic Distributed Learning with Gradient Quantization and Variance Reduction](https://mlsanity.com/paper/1904.05115/) (2019) - [Linearly Converging Error Compensated SGD](https://mlsanity.com/paper/2010.12292/) (2020) - [Distributed learning with compressed gradients](https://mlsanity.com/paper/1806.06573/) (2018) - [FedNL: Making Newton-Type Methods Applicable to Federated Learning](https://mlsanity.com/paper/2106.02969/) (2021) - [Momentum and Stochastic Momentum for Stochastic Gradient, Newton, Proximal Point and Subspace Descent Methods](https://mlsanity.com/paper/1712.09677/) (2017) - [Bidirectional compression in heterogeneous settings for distributed or federated learning with partial participation: tight convergence guarantees](https://mlsanity.com/paper/2006.14591/) (2020) ## Built on by (most cited first, 8 of 8) - [Byzantine Robustness and Partial Participation Can Be Achieved at Once: Just Clip Gradient Differences](https://mlsanity.com/paper/2311.14127/) (2023) - [Improved Convergence in Parameter-Agnostic Error Feedback through Momentum](https://mlsanity.com/paper/2511.14501/) (2025) - [Better Methods and Theory for Federated Learning: Compression, Client Selection and Heterogeneity](https://mlsanity.com/paper/2207.00392/) (2022) - [Gradient Projection onto Historical Descent Directions for Communication-Efficient Federated Learning](https://mlsanity.com/paper/2511.05593/) (2025) - [SA-PEF: Step-Ahead Partial Error Feedback for Efficient Federated Learning](https://mlsanity.com/paper/2601.20738/) (2026) - [A Tight Theory of Error Feedback Algorithms in Distributed Optimization](https://mlsanity.com/paper/2605.31594/) (2026) - [SILAGE: Memory-Efficient, Full-Gradient-Free Nonconvex Optimization for Nested Finite Sums](https://mlsanity.com/paper/2606.15832/) (2026) - [Theoretical Foundations of Communication-Efficient, Robust, and Practical Distributed and Federated Optimization](https://mlsanity.com/paper/2608.06563/) (2026) ## 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.