Linearly Converging Error Compensated SGD
  In this paper, we propose a unified analysis of variants of distributed SGD
with arbitrary compressions and delayed updates. Our framework is general
enough to cover different variants of quantized SGD, Error-Compensated SGD
(EC-SGD) and SGD with delayed updates (D-SGD). Via a single theorem, we derive
the complexity results for all the methods that fit our framework. For the
existing methods, this theorem gives the best-known complexity results.
Moreover, using our general scheme, we develop new variants of SGD that combine
variance reduction or arbitrary sampling with error feedback and quantization
and derive the convergence rates for these methods beating the state-of-the-art
results. In order to illustrate the strength of our framework, we develop 16
new methods that fit this. In particular, we propose the first method called
EC-SGD-DIANA that is based on error-feedback for biased compression operator
and quantization of gradient differences and prove the convergence guarantees
showing that EC-SGD-DIANA converges to the exact optimum asymptotically in
expectation with constant learning rate for both convex and strongly convex
objectives when workers compute full gradients of their loss functions.
Moreover, for the case when the loss function of the worker has the form of
finite sum, we modified the method and got a new one called EC-LSVRG-DIANA
which is the first distributed stochastic method with error feedback and
variance reduction that converges to the exact optimum asymptotically in
expectation with a constant learning rate.
