EF21 with Bells & Whistles: Practical Algorithmic Extensions of Modern
  Error Feedback
  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/T^{2/3})$, the rate of gradient descent in the same regime is $O(1/T)$).
Recently, Richt\'{a}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. Several of these techniques
were never analyzed in conjunction with EF before, and in cases where they were
(e.g., bidirectional compression), our rates are vastly superior.
