On Biased Compression for Distributed Learning
  In the last few years, various communication compression techniques have
emerged as an indispensable tool helping to alleviate the communication
bottleneck in distributed learning. However, despite the fact {\em biased}
compressors often show superior performance in practice when compared to the
much more studied and understood {\em unbiased} compressors, very little is
known about them. In this work we study three classes of biased compression
operators, two of which are new, and their performance when applied to
(stochastic) gradient descent and distributed (stochastic) gradient descent. We
show for the first time that biased compressors can lead to linear convergence
rates both in the single node and distributed settings. We prove that
distributed compressed SGD method, employed with error feedback mechanism,
enjoys the ergodic rate $\mathcal{O}\left( \delta L \exp[-\frac{\mu K}{\delta
L}] + \frac{(C + \delta D)}{K\mu}\right)$, where $\delta\ge1$ is a compression
parameter which grows when more compression is applied, $L$ and $\mu$ are the
smoothness and strong convexity constants, $C$ captures stochastic gradient
noise ($C=0$ if full gradients are computed on each node) and $D$ captures the
variance of the gradients at the optimum ($D=0$ for over-parameterized models).
Further, via a theoretical study of several synthetic and empirical
distributions of communicated gradients, we shed light on why and by how much
biased compressors outperform their unbiased variants. Finally, we propose
several new biased compressors with promising theoretical guarantees and
practical performance.
