Revisiting LocalSGD and SCAFFOLD: Improved rates and missing analysis
Luo R, Stich SU, Horváth S, Takáč M. 2025. Revisiting LocalSGD and SCAFFOLD: Improved rates and missing analysis. The 28th International Conference on Artificial Intelligence and Statistics. AISTATS: Conference on Artificial Intelligence and Statistics, PMLR, vol. 258, 2539–2547.
Download (ext.)
Conference Paper
| Published
| English
Scopus indexed
Author
Luo, RuichenISTA;
Stich, Sebastian U.;
Horváth, Samuel;
Takáč, Martin
Department
Series Title
PMLR
Abstract
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.
Publishing Year
Date Published
2025-05-01
Proceedings Title
The 28th International Conference on Artificial Intelligence and Statistics
Publisher
ML Research Press
Acknowledgement
The authors thank for the helpful discussions with Eduard Gorbunov, Kumar Kshitij Patel, Anton
Rodomanov, and Ali Zindari during the preparation of this work. This work was partially done during the first author’s stays at CISPA and at MBZUAI. The first author also acknowledges ERC CoG 863818 (ForM-SMArt) and Austrian Science Fund (FWF) 10.55776/COE12.
Volume
258
Page
2539-2547
Conference
AISTATS: Conference on Artificial Intelligence and Statistics
Conference Location
Mai Khao, Thailand
Conference Date
2025-05-03 – 2025-05-05
eISSN
IST-REx-ID
Cite this
Luo R, Stich SU, Horváth S, Takáč M. Revisiting LocalSGD and SCAFFOLD: Improved rates and missing analysis. In: The 28th International Conference on Artificial Intelligence and Statistics. Vol 258. ML Research Press; 2025:2539-2547.
Luo, R., Stich, S. U., Horváth, S., & Takáč, M. (2025). Revisiting LocalSGD and SCAFFOLD: Improved rates and missing analysis. In The 28th International Conference on Artificial Intelligence and Statistics (Vol. 258, pp. 2539–2547). Mai Khao, Thailand: ML Research Press.
Luo, Ruichen, Sebastian U. Stich, Samuel Horváth, and Martin Takáč. “Revisiting LocalSGD and SCAFFOLD: Improved Rates and Missing Analysis.” In The 28th International Conference on Artificial Intelligence and Statistics, 258:2539–47. ML Research Press, 2025.
R. Luo, S. U. Stich, S. Horváth, and M. Takáč, “Revisiting LocalSGD and SCAFFOLD: Improved rates and missing analysis,” in The 28th International Conference on Artificial Intelligence and Statistics, Mai Khao, Thailand, 2025, vol. 258, pp. 2539–2547.
Luo R, Stich SU, Horváth S, Takáč M. 2025. Revisiting LocalSGD and SCAFFOLD: Improved rates and missing analysis. The 28th International Conference on Artificial Intelligence and Statistics. AISTATS: Conference on Artificial Intelligence and Statistics, PMLR, vol. 258, 2539–2547.
Luo, Ruichen, et al. “Revisiting LocalSGD and SCAFFOLD: Improved Rates and Missing Analysis.” The 28th International Conference on Artificial Intelligence and Statistics, vol. 258, ML Research Press, 2025, pp. 2539–47.
All files available under the following license(s):
Copyright Statement:
This Item is protected by copyright and/or related rights. [...]
Link(s) to Main File(s)
Access Level

Export
Marked PublicationsOpen Data ISTA Research Explorer
Sources
arXiv 2501.04443