Distributed Learning with Compressed Gradient Differences
  Training large machine learning models requires a distributed computing
approach, with communication of the model updates being the bottleneck. For
this reason, several methods based on the compression (e.g., sparsification
and/or quantization) of updates were recently proposed, including QSGD
(Alistarh et al., 2017), TernGrad (Wen et al., 2017), SignSGD (Bernstein et
al., 2018), and DQGD (Khirirat et al., 2018). However, none of these methods
are able to learn the gradients, which renders them incapable of converging to
the true optimum in the batch mode, incompatible with non-smooth regularizers,
and slows down their convergence. In this work we propose a new distributed
learning method --- DIANA --- which resolves these issues via compression of
gradient differences. We perform a theoretical analysis in the strongly convex
and nonconvex settings and show that our rates are superior to existing rates.
Our analysis of block-quantization and differences between $\ell_2$ and
$\ell_\infty$ quantization closes the gaps in theory and practice. Finally, by
applying our analysis technique to TernGrad, we establish the first convergence
rate for this method.
