99% of Distributed Optimization is a Waste of Time: The Issue and How to
  Fix it
  Many popular distributed optimization methods for training machine learning
models fit the following template: a local gradient estimate is computed
independently by each worker, then communicated to a master, which subsequently
performs averaging. The average is broadcast back to the workers, which use it
to perform a gradient-type step to update the local version of the model. It is
also well known that many such methods, including SGD, SAGA, and accelerated
SGD for over-parameterized models, do not scale well with the number of
parallel workers. In this paper we observe that the above template is
fundamentally inefficient in that too much data is unnecessarily communicated
by the workers, which slows down the overall system. We propose a fix based on
a new update-sparsification method we develop in this work, which we suggest be
used on top of existing methods. Namely, we develop a new variant of parallel
block coordinate descent based on independent sparsification of the local
gradient estimates before communication. We demonstrate that with only $m/n$
blocks sent by each of $n$ workers, where $m$ is the total number of parameter
blocks, the theoretical iteration complexity of the underlying distributed
methods is essentially unaffected. As an illustration, this means that when
$n=100$ parallel workers are used, the communication of $99\%$ blocks is
redundant, and hence a waste of time. Our theoretical claims are supported
through extensive numerical experiments which demonstrate an almost perfect
match with our theory on a number of synthetic and real datasets.
