  An increasing bottleneck in decentralized optimization is communication.
Bigger models and growing datasets mean that decentralization of computation is
important and that the amount of information exchanged is quickly growing.
While compression techniques have been introduced to cope with the latter, none
has considered leveraging the temporal correlations that exist in consecutive
vector updates. An important example is distributed momentum-SGD where temporal
correlation is enhanced by the low-pass-filtering effect of applying momentum.
In this paper we design and analyze compression methods that exploit temporal
correlation in systems both with and without error-feedback. Experiments with
the ImageNet dataset demonstrate that our proposed methods offer significant
reduction in the rate of communication at only a negligible increase in
computation complexity. We further analyze the convergence of SGD when
compression is applied with error-feedback. In the literature, convergence
guarantees are developed only for compressors that provide error-bounds
point-wise, i.e., for each input to the compressor. In contrast, many important
codes (e.g. rate-distortion codes) provide error-bounds only in expectation and
thus provide a more general guarantee. In this paper we prove the convergence
of SGD under an expected error assumption by establishing a bound for the
minimum gradient norm.
