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 the landscape of distributed machine learning, communication overhead remains the primary bottleneck. Standard Stochastic Gradient Descent (SGD) requires frequent synchronization between workers and a central server, which is often prohibitively slow in network-constrained environments. Local SGD (also known as Federated Averaging) addresses this by allowing workers to perform multiple local updates ($H$) before averaging their models.
However, theoretical understanding of Local SGD has historically lagged behind its practical success. Previous analyses often relied on restrictive and "pathological" assumptions, such as bounded gradients, or failed to accurately capture the performance degradation caused by data heterogeneity—a critical factor in Federated Learning scenarios.
Theoretical Framework and the New Variance Notion
This work provides a significantly tighter theoretical analysis by removing the standard "bounded gradient" assumption, which often fails for simple strongly convex functions. Instead, the authors introduce a more precise measure of data heterogeneity: a new variance term, $\sigma_{dif}^2$.
This variance term measures the difference between local gradients at the global optimum, providing a quantifiable metric for "how different" datasets are across nodes. As shown in the variance analysis, this metric allows for a more nuanced understanding of how local minibatch sizes and the number of workers ($M$) influence the convergence behavior. The theory is proven to be "tight," as the bounds simplify exactly to well-known Minibatch SGD rates when $H=1$.
Identical vs. Heterogeneous Data
The paper distinguishes between two primary regimes:
- Identical Data: All nodes share the same distribution. Here, the error term related to local steps grows linearly with $H$.
- Heterogeneous Data: Nodes have unique datasets (non-i.i.d.). In this regime, the heterogeneity penalty grows quadratically ($H^2$).
This quadratic growth explains why Federated Learning is significantly more challenging than standard distributed training. Despite this penalty, the authors prove that a "linear speedup" is still achievable—doubling the number of machines can roughly halve training time—provided the number of local steps is carefully optimized.
Empirical Validation and Communication Efficiency
The theoretical findings were validated using standard classification datasets (a8a, mushrooms, w8a, etc.) from the LIBSVM library. The experiments focused on logistic regression with $\ell_2$ regularization, simulating various data splits.
A key empirical insight is the "diminishing return" of local updates. While increasing $H$ reduces the number of communication rounds, it eventually causes the model to converge to a "noise ball" or a sub-optimal neighborhood rather than the true global optimum. As seen in the time-based convergence plots, while 32 local steps might offer the fastest initial descent, they lead to a higher final error floor compared to configurations with fewer local steps.
Conclusion
By introducing a tighter theoretical framework and a more realistic variance notion, this work clarifies the performance bounds of Local SGD. The distinction between linear and quadratic penalties for data heterogeneity provides a roadmap for optimizing synchronization frequency in distributed and federated systems. Future work remains to extend these tight bounds to non-convex landscapes and dynamic client participation.
Summary updated