EF21 with bells & whistles: Six algorithmic extensions of modern error feedback
Fatkhullin, Ilyas Sokolov, Igor Gorbunov, Eduard Li, Zhize Richtarik, Peter
Fatkhullin, Ilyas
Sokolov, Igor
Gorbunov, Eduard
Li, Zhize
Richtarik, Peter
Author
Supervisor
Department
Computer Science
Embargo End Date
Type
Journal article
Date
2025
License
Language
English
Collections
Research Projects
Organizational Units
Journal Issue
Abstract
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àrik 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.
Citation
I. Sokolov, E. Gorbunov EDUARDGORBUNOV, Z. Li, P. Richtárik, I. Fatkhullin, and E. Gorbunov, “EF21 with Bells & Whistles: Six Algorithmic Extensions of Modern Error Feedback,” Journal of Machine Learning Research, vol. 26, no. 189, pp. 1–50, 2025,[Online]. Available: http://jmlr.org/papers/v26/24-0059.html
Source
Journal of Machine Learning Research
Conference
Keywords
Distributed Computing, Compressed Communication, Error Feedback
Subjects
Source
Publisher
Microtome Publishing