  Large scale distributed optimization has become the default tool for the
training of supervised machine learning models with a large number of
parameters and training data. Recent advancements in the field provide several
mechanisms for speeding up the training, including {\em compressed
communication}, {\em variance reduction} and {\em acceleration}. However, none
of these methods is capable of exploiting the inherently rich data-dependent
smoothness structure of the local losses beyond standard smoothness constants.
In this paper, we argue that when training supervised models, {\em smoothness
matrices} -- information-rich generalizations of the ubiquitous smoothness
constants -- can and should be exploited for further dramatic gains, both in
theory and practice. In order to further alleviate the communication burden
inherent in distributed optimization, we propose a novel communication
sparsification strategy that can take full advantage of the smoothness matrices
associated with local losses. To showcase the power of this tool, we describe
how our sparsification technique can be adapted to three distributed
optimization algorithms -- DCGD, DIANA and ADIANA -- yielding significant
savings in terms of communication complexity. The new methods always outperform
the baselines, often dramatically so.
