  With distributed machine learning being a prominent technique for large-scale
machine learning tasks, communication complexity has become a major bottleneck
for speeding up training and scaling up machine numbers. In this paper, we
propose a new technique named Common randOm REconstruction(CORE), which can be
used to compress the information transmitted between machines in order to
reduce communication complexity without other strict conditions. Especially,
our technique CORE projects the vector-valued information to a low-dimensional
one through common random vectors and reconstructs the information with the
same random noises after communication. We apply CORE to two distributed tasks,
respectively convex optimization on linear models and generic non-convex
optimization, and design new distributed algorithms, which achieve provably
lower communication complexities. For example, we show for linear models
CORE-based algorithm can encode the gradient vector to $\mathcal{O}(1)$-bits
(against $\mathcal{O}(d)$), with the convergence rate not worse, preceding the
existing results.
