3PC: Three Point Compressors for Communication-Efficient Distributed
  Training and a Better Theory for Lazy Aggregation
  We propose and study a new class of gradient communication mechanisms for
communication-efficient training -- three point compressors (3PC) -- as well as
efficient distributed nonconvex optimization algorithms that can take advantage
of them. Unlike most established approaches, which rely on a static compressor
choice (e.g., Top-$K$), our class allows the compressors to {\em evolve}
throughout the training process, with the aim of improving the theoretical
communication complexity and practical efficiency of the underlying methods. We
show that our general approach can recover the recently proposed
state-of-the-art error feedback mechanism EF21 (Richt\'arik et al., 2021) and
its theoretical properties as a special case, but also leads to a number of new
efficient methods. Notably, our approach allows us to improve upon the state of
the art in the algorithmic and theoretical foundations of the {\em lazy
aggregation} literature (Chen et al., 2018). As a by-product that may be of
independent interest, we provide a new and fundamental link between the lazy
aggregation and error feedback literature. A special feature of our work is
that we do not require the compressors to be unbiased.
