New Bounds For Distributed Mean Estimation and Variance Reduction
  We consider the problem of distributed mean estimation (DME), in which $n$
machines are each given a local $d$-dimensional vector $x_v \in \mathbb{R}^d$,
and must cooperate to estimate the mean of their inputs $\mu = \frac 1n\sum_{v
= 1}^n x_v$, while minimizing total communication cost.
  DME is a fundamental construct in distributed machine learning, and there has
been considerable work on variants of this problem, especially in the context
of distributed variance reduction for stochastic gradients in parallel SGD.
Previous work typically assumes an upper bound on the norm of the input
vectors, and achieves an error bound in terms of this norm. However, in many
real applications, the input vectors are concentrated around the correct output
$\mu$, but $\mu$ itself has large norm. In such cases, previous output error
bounds perform poorly.
  In this paper, we show that output error bounds need not depend on input
norm. We provide a method of quantization which allows distributed mean
estimation to be performed with solution quality dependent only on the distance
between inputs, not on input norm, and show an analogous result for distributed
variance reduction. The technique is based on a new connection with lattice
theory. We also provide lower bounds showing that the communication to error
trade-off of our algorithms is asymptotically optimal.
  As the lattices achieving optimal bounds under $\ell_2$-norm can be
computationally impractical, we also present an extension which leverages
easy-to-use cubic lattices, and is loose only up to a logarithmic factor in
$d$. We show experimentally that our method yields practical improvements for
common applications, relative to prior approaches.
