Communication-efficient SGD: From Local SGD to One-Shot Averaging

Abstract

We consider speeding up stochastic gradient descent (SGD) by parallelizing it across multiple workers. We assume the same data set is shared among $N$ workers, who can take SGD steps and coordinate with a central server. While it is possible to obtain a linear reduction in the variance by averaging all the stochastic gradients at every step, this requires a lot of communication between the workers and the server, which can dramatically reduce the gains from parallelism. The Local SGD method, proposed and analyzed in the earlier literature, suggests machines should make many local steps between such communications. While the initial analysis of Local SGD showed it needs $\Omega (\sqrt{T})$ communications for $T$ local gradient steps in order for the error to scale proportionately to $1/(NT)$, this has been successively improved in a string of papers, with the state of the art requiring $Ω\left( N \left( \mbox{ poly} (\log T) \right) \right)$ communications. In this paper, we suggest a Local SGD scheme that communicates less overall by communicating less frequently as the number of iterations grows. Our analysis shows that this can achieve an error that scales as $1/(NT)$ with a number of communications that is completely independent of $T$. In particular, we show that $\Omega (N)$ communications are sufficient. Empirical evidence suggests this bound is close to tight as we further show that $\sqrt{N}$ or $N^{3/4}$ communications fail to achieve linear speed-up in simulations. Moreover, we show that under mild assumptions, the main of which is twice differentiability on any neighborhood of the optimal solution, one-shot averaging which only uses a single round of communication can also achieve the optimal convergence rate asymptotically.

arXiv commentarXiv admin note: substantial text overlap with arXiv:2006.02582

References in corpus (17)

• Communication-Efficient Learning of Deep Networks from Decentralized Data
• Federated Learning: Strategies for Improving Communication Efficiency
• Optimal Distributed Online Prediction using Mini-Batches
• Horovod: fast and easy distributed deep learning in TensorFlow
• Sparsified SGD with Memory
• Don't Use Large Mini-Batches, Use Local SGD
• A Unified Theory of Decentralized SGD with Changing Topology and Local Updates
• Cooperative SGD: A unified Framework for the Design and Analysis of Communication-Efficient SGD Algorithms
• Local SGD with Periodic Averaging: Tighter Analysis and Adaptive Synchronization
• Communication-Efficient Distributed Deep Learning: A Comprehensive Survey
• Parallel SGD: When does averaging help?
• The Error-Feedback Framework: Better Rates for SGD with Delayed Gradients and Compressed Communication
• Is Local SGD Better than Minibatch SGD?
• MATCHA: Speeding Up Decentralized SGD via Matching Decomposition Sampling
• Robust Asynchronous Stochastic Gradient-Push: Asymptotically Optimal and Network-Independent Performance for Strongly Convex Functions
• An Accelerated Decentralized Stochastic Proximal Algorithm for Finite Sums
• On Data Dependence in Distributed Stochastic Optimization

Cited by in corpus (1)

• Local SGD for Near-Quadratic Problems: Improving Convergence under Unconstrained Noise Conditions