Momentum Provably Improves Error Feedback!
METADATA ONLY
Loading...
Author / Producer
Date
2024-07
Publication Type
Conference Paper
ETH Bibliography
yes
Citations
Altmetric
METADATA ONLY
Data
Rights / License
Abstract
Due to the high communication overhead when training machine learning models in a distributed environment, modern algorithms invariably rely on lossy communication compression. However, when untreated, the errors caused by compression propagate, and can lead to severely unstable behavior, including exponential divergence. Almost a decade ago, Seide et al. (2014) proposed an error feedback (EF) mechanism, which we refer to as EF14, as an immensely effective heuristic for mitigating this issue. However, despite steady algorithmic and theoretical advances in the EF field in the last decade, our understanding is far from complete. In this work we address one of the most pressing issues. In particular, in the canonical nonconvex setting, all known variants of EF rely on very large batch sizes to converge, which can be prohibitive in practice. We propose a surprisingly simple fix which removes this issue both theoretically, and in practice: the application of Polyak's momentum to the latest incarnation of EF due to Richtárik et al. (2021) known as EF21. Our algorithm, for which we coin the name EF21-SGDM, improves the communication and sample complexities of previous error feedback algorithms under standard smoothness and bounded variance assumptions, and does not require any further strong assumptions such as bounded gradient dissimilarity. Moreover, we propose a double momentum version of our method that improves the complexities even further. Our proof seems to be novel even when compression is removed from the method, and as such, our proof technique is of independent interest in the study of nonconvex stochastic optimization enriched with Polyak's momentum.
Permanent link
Publication status
published
Book title
Advances in Neural Information Processing Systems 36
Journal / series
Volume
Pages / Article No.
76444 - 76495
Publisher
Curran
Event
37th Annual Conference on Neural Information Processing Systems (NeurIPS 2023)
Edition / version
Methods
Software
Geographic location
Date collected
Date created
Subject
Federated learning; stochastic optimization; distributed optimisation; Momentum; nonconvex optimization
Organisational unit
09729 - He, Niao / He, Niao
02219 - ETH AI Center / ETH AI Center
Notes
Poster presentation on December 12, 2023.