# Revisiting LocalSGD and SCAFFOLD: Improved Rates and Missing Analysis

arXiv: https://arxiv.org/abs/2501.04443 · HTML: https://mlsanity.com/paper/2501.04443/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 27 of its 41 references that are in the map.
- First posted on arXiv 8 Jan 2025.

## Builds on (most cited first, 27 of 27)

- [Communication-Efficient Learning of Deep Networks from Decentralized Data](https://mlsanity.com/paper/1602.05629/) (2016)
- [Optimization Methods for Large-Scale Machine Learning](https://mlsanity.com/paper/1606.04838/) (2016)
- [Local SGD Converges Fast and Communicates Little](https://mlsanity.com/paper/1805.09767/) (2018)
- [Can Decentralized Algorithms Outperform Centralized Algorithms? A Case Study for Decentralized Parallel Stochastic Gradient Descent](https://mlsanity.com/paper/1705.09056/) (2017)
- [Flower: A Friendly Federated Learning Research Framework](https://mlsanity.com/paper/2007.14390/) (2020)
- [SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectives](https://mlsanity.com/paper/1407.0202/) (2014)
- [A Unified Theory of Decentralized SGD with Changing Topology and Local Updates](https://mlsanity.com/paper/2003.10422/) (2020)
- [FedML: A Research Library and Benchmark for Federated Machine Learning](https://mlsanity.com/paper/2007.13518/) (2020)
- [Parallel Restarted SGD with Faster Convergence and Less Communication: Demystifying Why Model Averaging Works for Deep Learning](https://mlsanity.com/paper/1807.06629/) (2018)
- [Is Local SGD Better than Minibatch SGD?](https://mlsanity.com/paper/2002.07839/) (2020)
- [Minibatch vs Local SGD for Heterogeneous Distributed Learning](https://mlsanity.com/paper/2006.04735/) (2020)
- [ProxSkip: Yes! Local Gradient Steps Provably Lead to Communication Acceleration! Finally!](https://mlsanity.com/paper/2202.09357/) (2022)
- [Communication Efficient Distributed Optimization using an Approximate Newton-type Method](https://mlsanity.com/paper/1312.7853/) (2013)
- [Stochastic Controlled Averaging for Federated Learning with Communication Compression](https://mlsanity.com/paper/2308.08165/) (2023)
- [SGD and Hogwild! Convergence Without the Bounded Gradients Assumption](https://mlsanity.com/paper/1802.03801/) (2018)
- [On the convergence properties of a K-step averaging stochastic gradient descent algorithm for nonconvex optimization](https://mlsanity.com/paper/1708.01012/) (2017)
- [Bias-Variance Reduced Local SGD for Less Heterogeneous Federated Learning](https://mlsanity.com/paper/2102.03198/) (2021)
- [Statistically Preconditioned Accelerated Gradient Method for Distributed Optimization](https://mlsanity.com/paper/2002.10726/) (2020)
- [Understanding Generalization of Federated Learning via Stability: Heterogeneity Matters](https://mlsanity.com/paper/2306.03824/) (2023)
- [Why (and When) does Local SGD Generalize Better than SGD?](https://mlsanity.com/paper/2303.01215/) (2023)
- [Faster federated optimization under second-order similarity](https://mlsanity.com/paper/2209.02257/) (2022)
- [Decentralized Personalized Federated Learning: Lower Bounds and Optimal Algorithm for All Personalization Modes](https://mlsanity.com/paper/2107.07190/) (2021)
- [Mini-Batch Primal and Dual Methods for SVMs](https://mlsanity.com/paper/1303.2314/) (2013)
- [The Limits and Potentials of Local SGD for Distributed Heterogeneous Learning with Intermittent Communication](https://mlsanity.com/paper/2405.11667/) (2024)
- [Federated Optimization with Doubly Regularized Drift Correction](https://mlsanity.com/paper/2404.08447/) (2024)
- [STL-SGD: Speeding Up Local SGD with Stagewise Communication Period](https://mlsanity.com/paper/2006.06377/) (2020)
- [Lessons from Generalization Error Analysis of Federated Learning: You May Communicate Less Often!](https://mlsanity.com/paper/2306.05862/) (2023)

## Built on by (most cited first, 4 of 4)

- [Accelerated Methods with Complexity Separation Under Data Similarity for Federated Learning Problems](https://mlsanity.com/paper/2601.08614/) (2026)
- [Gaussian Approximation and Multiplier Bootstrap for Federated Linear Stochastic Approximation](https://mlsanity.com/paper/2605.19629/) (2026)
- [What's in a Smoothness Constant? Tighter Rates for Local SGD with Bounded Second-order Heterogeneity](https://mlsanity.com/paper/2607.14731/) (2026)
- [Beyond Client Averaging: A Client-Independent Second-Order Stationary-Bias Component in Stochastic SCAFFOLD](https://mlsanity.com/paper/2608.26765/) (2026)

## Abstract (arXiv)

LocalSGD and SCAFFOLD are widely used methods in distributed stochastic optimization, with numerous applications in machine learning, large-scale data processing, and federated learning. However, rigorously establishing their theoretical advantages over simpler methods, such as minibatch SGD (MbSGD), has proven challenging, as existing analyses often rely on strong assumptions, unrealistic premises, or overly restrictive scenarios. In this work, we revisit the convergence properties of LocalSGD and SCAFFOLD under a variety of existing or weaker conditions, including gradient similarity, Hessian similarity, weak convexity, and Lipschitz continuity of the Hessian. Our analysis shows that (i) LocalSGD achieves faster convergence compared to MbSGD for weakly convex functions without requiring stronger gradient similarity assumptions; (ii) LocalSGD benefits significantly from higher-order similarity and smoothness; and (iii) SCAFFOLD demonstrates faster convergence than MbSGD for a broader class of non-quadratic functions. These theoretical insights provide a clearer understanding of the conditions under which LocalSGD and SCAFFOLD outperform MbSGD.