Distributed and federated learning rely heavily on algorithms that minimize communication overhead. LocalSGD and SCAFFOLD are two primary methods used to achieve this by allowing workers to perform multiple local updates before synchronizing. While these methods show superior performance in practice compared to standard Minibatch SGD (MbSGD), theoretical justifications for their success in non-convex settings have historically lagged behind, often relying on restrictive and unrealistic assumptions.
This research bridges the gap between theory and practice by providing tighter convergence rates under more general conditions, proving that LocalSGD and SCAFFOLD are fundamentally faster than MbSGD for a wide range of non-convex optimization tasks.
The Theoretical Gap in Distributed Optimization
In large-scale distributed training, communication between a central server and multiple worker nodes is often the primary bottleneck. To mitigate this, LocalSGD allows workers to take $\tau$ local gradient steps between communication rounds. SCAFFOLD further improves upon this by incorporating variance reduction to combat "client drift," where local models diverge due to data heterogeneity.
Despite their empirical success, proving a theoretical "speedup" over MbSGD for non-convex functions has been challenging. Previous analyses often assumed:
- Uniform Gradient Similarity: The difference between local and global gradients is bounded everywhere, which is rarely true in heterogeneous federated learning.
- Perfectly Quadratic Losses: Speedup proofs for SCAFFOLD were largely limited to toy quadratic problems.
This paper addresses these limitations, providing a more robust mathematical framework for analyzing these algorithms.
Analytical Innovations
The authors introduce several key techniques to sharpen the theoretical bounds:
- The Variance Trick: A novel way to bound the variance between worker models by relating it to the previous step and the global gradient, rather than just the last communication round. This recursion unrolling leads to significantly tighter results.
- Noiseless Sequence Construction: A theoretical tool used to decouple stochastic noise from the discrepancies caused by local updates, allowing for a clearer analysis of higher-order smoothness benefits.
- Relaxed Hessian Assumptions: Instead of requiring every local function to have a Lipschitz continuous Hessian, the authors show that it is sufficient if at least one function in the convex hull of the distributed functions satisfies this property.
Key Insights
The paper's analysis leads to several important conclusions regarding the behavior of distributed optimization:
- Heterogeneity is Not a Barrier for LocalSGD: The study proves that "standard gradient similarity" (bounded on average) is sufficient for LocalSGD to outperform MbSGD. This validates the use of LocalSGD in real-world federated learning where data across devices is highly non-IID.
- Benefits of Smoothness: Even as first-order methods, LocalSGD and SCAFFOLD can mathematically exploit higher-order landscape properties like Hessian similarity to accelerate convergence.
- Generalizing SCAFFOLD: The theoretical speedup of SCAFFOLD is extended from simple quadratics to a much broader class of general non-quadratic, weakly convex functions.
Key Results
The primary contribution of this work is the derivation of improved optimization terms. For weakly convex functions, the authors established a rate of $\mathcal{O}((L/\tau + \rho)\Delta/R)$ for LocalSGD and $\mathcal{O}((L/\tau + \sqrt{L\delta} + \rho)\Delta/R)$ for SCAFFOLD. These results represent the first time a speedup over MbSGD has been rigorously proven for these algorithms in non-convex settings without relying on uniform gradient similarity.
The theoretical findings were validated through experiments on synthetic datasets. While MbSGD's performance remained constant regardless of Hessian similarity, both LocalSGD and SCAFFOLD showed marked improvements as the similarity between local Hessians increased, aligning perfectly with the new theoretical bounds.
Limitations and Future Directions
While this work significantly advances the theoretical understanding of LocalSGD and SCAFFOLD, it focuses on the standard intermittent communication model. Modern federated learning often employs additional techniques such as gradient quantization, sparsification, and asynchronous updates. Integrating these communication-saving strategies into the current analytical framework remains an important area for future research.
Summary updated