  This paper targets solving distributed machine learning problems such as
federated learning in a communication-efficient fashion. A class of new
stochastic gradient descent (SGD) approaches have been developed, which can be
viewed as the stochastic generalization to the recently developed lazily
aggregated gradient (LAG) method --- justifying the name LASG. LAG adaptively
predicts the contribution of each round of communication and chooses only the
significant ones to perform. It saves communication while also maintains the
rate of convergence. However, LAG only works with deterministic gradients, and
applying it to stochastic gradients yields poor performance. The key components
of LASG are a set of new rules tailored for stochastic gradients that can be
implemented either to save download, upload, or both. The new algorithms
adaptively choose between fresh and stale stochastic gradients and have
convergence rates comparable to the original SGD. LASG achieves impressive
empirical performance --- it typically saves total communication by an order of
magnitude.
