Abstract
Mini-batch stochastic gradient descent (SGD) is state of the art in large scale distributed training. The scheme can reach a linear speedup with respect to the number of workers, but this is rarely seen in practice as the scheme often suffers from large network delays and bandwidth limits. To overcome this communication bottleneck recent works propose to reduce the communication frequency. An algorithm of this type is local SGD that runs SGD independently in parallel on different workers and averages the sequences only once in a while. This scheme shows promising results in practice, but eluded thorough theoretical analysis. We prove concise convergence rates for local SGD on convex problems and show that it converges at the same rate as mini-batch SGD in terms of number of evaluated gradients, that is, the scheme achieves linear speedup in the number of workers and mini-batch size. The number of communication rounds can be reduced up to a factor of $T^{1/2}$—where $T$ denotes the number of total steps—compared to mini-batch SGD. This also holds for asynchronous implementations.
The Communication Bottleneck in Distributed Learning
In large-scale distributed machine learning, the standard approach is Parallel Mini-batch SGD. In this setup, multiple workers compute gradients on their local data, share them with everyone else, and average them to update a global model.
However, communication is a massive bottleneck. High network latency and limited bandwidth often mean that workers spend more time waiting for data to transfer than actually computing gradients. While increasing the mini-batch size can help, it often leads to "generalization gaps" where the model performs worse on new data. Local SGD (also known as iterative parameter mixing) was proposed as a practical fix: let workers run multiple steps of SGD locally on their own machines and only average their models once in a while.
Local SGD: Lazy Communication, Fast Convergence
The Local SGD algorithm works as follows:
- Initialize: $K$ workers start with the same model weights.
- Local Evolution: Each worker performs $H$ steps of standard SGD independently using their local data.
- Global Synchronization: After $H$ steps, all workers average their local models to create a new starting point for the next round.
While practitioners have long favored this approach, its theoretical properties were previously unclear. This paper provides the first rigorous proof that this "lazy" communication style can match the gold-standard convergence rates of fully synchronized systems.
Theoretical Insights
The core of the paper's contribution is a "perturbed iterate analysis." Instead of tracking $K$ different diverging sequences, the author defines a "virtual" averaged sequence and proves that the individual workers' models do not drift too far from this average. This allows the author to show that the variance reduction benefits of having $K$ workers still apply, even if they aren't perfectly in sync.
The analysis establishes that the error for Local SGD scales as $O(\frac{1}{KT})$, which is the same rate as mini-batch SGD. The most striking insight is that you can reduce communication by a factor of $O(\sqrt{T})$ without hurting the asymptotic convergence rate. As long as synchronization occurs "often enough," the errors introduced by local divergence are negligible compared to the noise inherent in stochastic gradients. This theory also extends to Asynchronous Local SGD, where workers do not have to wait for a global "heartbeat" to sync, making it robust to stragglers.
Empirical Validation
The paper validates its theoretical findings using the w8a dataset from the LIBSVM library (logistic regression, $d = 300$ features, $n = 49,749$ samples). The author simulated various configurations of workers ($K$), synchronization intervals ($H$), and mini-batch sizes ($b$) to measure "time-to-accuracy."
Experiments confirmed the theory: increasing the synchronization interval $H$ from 1 to 16 or 64 showed significant speedups in wall-clock time. The time saved on communication far outweighed any slight delay in convergence, allowing the system to approach the "perfect speedup" line more closely than standard parallel SGD.
Conclusion and Future Directions
This work provides a solid theoretical foundation for Local SGD, proving it achieves linear speedup while drastically reducing communication overhead. While the current analysis focuses on strongly convex functions, it serves as a guideline for exploring Local SGD in non-convex deep learning applications. Future work remains to be done in "one-shot" averaging scenarios and in Federated Learning environments where data is highly non-IID across workers.
Summary updated