  A standard approach in large scale machine learning is distributed stochastic
gradient training, which requires the computation of aggregated stochastic
gradients over multiple nodes on a network. Communication is a major bottleneck
in such applications, and in recent years, compressed stochastic gradient
methods such as QSGD (quantized SGD) and sparse SGD have been proposed to
reduce communication. It was also shown that error compensation can be combined
with compression to achieve better convergence in a scheme that each node
compresses its local stochastic gradient and broadcast the result to all other
nodes over the network in a single pass. However, such a single pass broadcast
approach is not realistic in many practical implementations. For example, under
the popular parameter server model for distributed learning, the worker nodes
need to send the compressed local gradients to the parameter server, which
performs the aggregation. The parameter server has to compress the aggregated
stochastic gradient again before sending it back to the worker nodes. In this
work, we provide a detailed analysis on this two-pass communication model and
its asynchronous parallel variant, with error-compensated compression both on
the worker nodes and on the parameter server. We show that the
error-compensated stochastic gradient algorithm admits three very nice
properties: 1) it is compatible with an \emph{arbitrary} compression technique;
2) it admits an improved convergence rate than the non error-compensated
stochastic gradient methods such as QSGD and sparse SGD; 3) it admits linear
speedup with respect to the number of workers. The empirical study is also
conducted to validate our theoretical results.
