Local SGD With a Communication Overhead Depending Only on the Number of Workers

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. Unfortunately, this could require 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{ polynomial in log } (T) \right) \right)$ communications. In this paper, we give a new analysis of Local SGD. A consequence of our analysis is that Local SGD can achieve an error that scales as $1/(nT)$ with only a fixed number of communications independent of $T$: specifically, only $\Omega (n)$ communications are required.

References in corpus (17)

• Communication-Efficient Learning of Deep Networks from Decentralized Data
• Federated Learning: Strategies for Improving Communication Efficiency
• QSGD: Communication-Efficient SGD via Gradient Quantization and Encoding
• Optimal Distributed Online Prediction using Mini-Batches
• 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
• Communication Complexity of Distributed Convex Learning and Optimization
• 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
• On Data Dependence in Distributed Stochastic Optimization

Cited by in corpus (5)

• Linear Convergence in Federated Learning: Tackling Client Heterogeneity and Sparse Gradients
• Adversarial training in communication constrained federated learning
• Exploiting Heterogeneity in Robust Federated Best-Arm Identification
• Hogwild! over Distributed Local Data Sets with Linearly Increasing Mini-Batch Sizes
• Minibatch vs Local SGD with Shuffling: Tight Convergence Bounds and Beyond