Abstract
We provide a new analysis of local SGD, removing unnecessary assumptions and elaborating on the difference between two data regimes: identical and heterogeneous. In both cases, we improve the existing theory and provide values of the optimal stepsize and optimal number of local iterations. Our bounds are based on a new notion of variance that is specific to local SGD methods with different data. The tightness of our results is guaranteed by recovering known statements when we plug $H=1$, where $H$ is the number of local steps. The empirical evidence further validates the severe impact of data heterogeneity on the performance of local SGD.
Introduction
In large-scale machine learning, training models across distributed nodes—such as parallel machines in a data center or mobile devices in a Federated Learning network—is standard practice. The traditional approach, Minibatch SGD, requires nodes to synchronize and communicate after every single update step. This creates a significant communication bottleneck, especially in high-latency environments.
Local SGD (often referred to as Federated Averaging) addresses this by allowing each node to perform multiple local updates before averaging the results globally. While empirically successful, theoretical explanations for its performance have often relied on restrictive and unrealistic assumptions, such as "bounded gradients." This paper provides a refined theoretical analysis that removes these assumptions and introduces a new framework for understanding the impact of data heterogeneity.
Methodology: Beyond Bounded Gradients
The authors analyze the Local SGD algorithm, which alternates between local computation phases and global synchronization. Their analysis introduces three key improvements over existing literature:
- Realistic Assumptions: They replace the "bounded gradient" assumption—which rarely holds for common unconstrained optimization problems—with standard L-smoothness and convexity assumptions.
- A New Variance Metric ($\sigma^2_{dif}$): To capture data heterogeneity precisely, the authors introduce a variance term that measures the dissimilarity of gradients at the optimum. Unlike previous metrics, this one naturally reduces to zero if the data across nodes is identical, providing a seamless bridge between IID and non-IID theory.
- Perturbed Iterate Analysis: By treating the average of local models as a sequence following a "noisy" gradient descent path, they carefully bound the "drift" caused by local steps.
Key Insights: The Impact of Heterogeneity
A critical finding of this work is the mathematical quantification of the "penalty" paid for data heterogeneity. In the identical data regime, the error caused by local model drift grows linearly with the number of local steps ($H$). However, in the heterogeneous regime typical of Federated Learning, this drift error grows quadratically ($H^2$). This explains why Federated Learning is significantly more sensitive to the synchronization interval than standard distributed training.
Furthermore, the theory is "tight" in that it recovers the well-established convergence rates for standard Minibatch SGD when the number of local steps is set to one ($H=1$).
Empirical Results and Convergence
The authors validated their theory using logistic regression with $L_2$ regularization on several standard benchmarks (a8a, w8a, mushrooms, a9a, a5a).
As shown in Figure 4, increasing the number of local steps allows the model to reach a neighborhood of the solution faster in terms of communication rounds. However, the size of this neighborhood—the final precision—is directly impacted by the degree of data heterogeneity across nodes.
Optimal Communication Strategy
One of the most practical contributions of the paper is a recipe for finding the "sweet spot" in communication. There is a fundamental trade-off: taking more local steps saves communication time but increases model drift error.
Figure 5 illustrates how the optimal number of local steps depends on the system's communication-to-computation ratio ($T_{communication}/T_{computation}$). For systems where communication is expensive, taking more local steps is beneficial up to a certain point, after which the drift penalty outweighs the savings.
Conclusion and Future Work
This research provides the fastest known convergence rates for convex and strongly convex Local SGD without requiring bounded gradients. It proves that a "linear speedup" (training $M$ times faster with $M$ nodes) is achievable even with local steps, provided $H$ is chosen correctly.
While this work significantly advances the theory for convex optimization, most modern deep learning involves non-convex landscapes. Future research directions include extending these tighter bounds to non-convex functions and addressing "partial participation," where only a subset of devices is active in each round—a common scenario in massive-scale Federated Learning.
Summary updated