EF-BV: A Unified Theory of Error Feedback and Variance Reduction Mechanisms for Biased and Unbiased Compression in Distributed Optimization
In distributed or federated optimization and learning, communication between
the different computing units is often the bottleneck, and gradient compression
is a widely used technique for reducing the number of bits sent within each
communication round of iterative methods. There are two classes of compression
operators and separate algorithms making use of them. In the case of unbiased
random compressors with bounded variance (e.g., rand-k), the DIANA algorithm of
Mishchenko et al. [2019], which implements a variance reduction technique for
handling the variance introduced by compression, is the current state of the
art. In the case of biased and contractive compressors (e.g., top-k), the EF21
algorithm of Richt\'arik et al. [2021], which implements an error-feedback
mechanism for handling the error introduced by compression, is the current
state of the art. These two classes of compression schemes and algorithms are
distinct, with different analyses and proof techniques. In this paper, we unify
them into a single framework and propose a new algorithm, recovering DIANA and
EF21 as particular cases. We prove linear convergence under certain conditions.
Our general approach works with a new, larger class of compressors, which
includes unbiased and biased compressors as particular cases, and has two
parameters, the bias and the variance. These gives a finer control and allows
us to inherit the best of the two worlds: biased compressors, whose good
performance in practice is recognized, can be used. And independent randomness
at the compressors allows to mitigate the effects of compression, with the
convergence rate improving when the number of parallel workers is large. This
is the first time that an algorithm with all these features is proposed. Our
approach takes a step towards better understanding of two so-far distinct
worlds of communication-efficient distributed learning.