  In distributed statistical learning, $N$ samples are split across $m$
machines and a learner wishes to use minimal communication to learn as well as
if the examples were on a single machine. This model has received substantial
interest in machine learning due to its scalability and potential for parallel
speedup. However, in high-dimensional settings, where the number examples is
smaller than the number of features ("dimension"), the speedup afforded by
distributed learning may be overshadowed by the cost of communicating a single
example. This paper investigates the following question: When is it possible to
learn a $d$-dimensional model in the distributed setting with total
communication sublinear in $d$?
  Starting with a negative result, we show that for learning $\ell_1$-bounded
or sparse linear models, no algorithm can obtain optimal error until
communication is linear in dimension. Our main result is that that by slightly
relaxing the standard boundedness assumptions for linear models, we can obtain
distributed algorithms that enjoy optimal error with communication logarithmic
in dimension. This result is based on a family of algorithms that combine
mirror descent with randomized sparsification/quantization of iterates, and
extends to the general stochastic convex optimization model.
