  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.
