  To address the high communication costs of distributed machine learning, a
large body of work has been devoted in recent years to designing various
compression strategies, such as sparsification and quantization, and
optimization algorithms capable of using them. Recently, Safaryan et al. (2021)
pioneered a dramatically different compression design approach: they first use
the local training data to form local smoothness matrices and then propose to
design a compressor capable of exploiting the smoothness information contained
therein. While this novel approach leads to substantial savings in
communication, it is limited to sparsification as it crucially depends on the
linearity of the compression operator. In this work, we generalize their
smoothness-aware compression strategy to arbitrary unbiased compression
operators, which also include sparsification. Specializing our results to
stochastic quantization, we guarantee significant savings in communication
complexity compared to standard quantization. In particular, we prove that
block quantization with $n$ blocks theoretically outperforms single block
quantization, leading to a reduction in communication complexity by an
$\mathcal{O}(n)$ factor, where $n$ is the number of nodes in the distributed
system. Finally, we provide extensive numerical evidence with convex
optimization problems that our smoothness-aware quantization strategies
outperform existing quantization schemes as well as the aforementioned
smoothness-aware sparsification strategies with respect to three evaluation
metrics: the number of iterations, the total amount of bits communicated, and
wall-clock time.
