# The Limits and Potentials of Local SGD for Distributed Heterogeneous Learning with Intermittent Communication arXiv: https://arxiv.org/abs/2405.11667 ยท HTML: https://mlsanity.com/paper/2405.11667/ ## Key facts - Cited by 12 papers in the map (data through 14 Oct 2026). - Builds on 34 of its 48 references that are in the map. - First posted on arXiv 19 May 2024. ## Builds on (most cited first, 30 of 34) - [Communication-Efficient Learning of Deep Networks from Decentralized Data](https://mlsanity.com/paper/1602.05629/) (2016) - [Advances and Open Problems in Federated Learning](https://mlsanity.com/paper/1912.04977/) (2019) - [Introduction to Online Convex Optimization](https://mlsanity.com/paper/1909.05207/) (2019) - [Local SGD Converges Fast and Communicates Little](https://mlsanity.com/paper/1805.09767/) (2018) - [A Unified Theory of Decentralized SGD with Changing Topology and Local Updates](https://mlsanity.com/paper/2003.10422/) (2020) - [A Field Guide to Federated Optimization](https://mlsanity.com/paper/2107.06917/) (2021) - [Tighter Theory for Local SGD on Identical and Heterogeneous Data](https://mlsanity.com/paper/1909.04746/) (2019) - [Don't Use Large Mini-Batches, Use Local SGD](https://mlsanity.com/paper/1808.07217/) (2018) - [Mime: Mimicking Centralized Stochastic Algorithms in Federated Learning](https://mlsanity.com/paper/2008.03606/) (2020) - [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) - [Lower Bounds for Finding Stationary Points I](https://mlsanity.com/paper/1710.11606/) (2017) - [FedSplit: An algorithmic framework for fast federated optimization](https://mlsanity.com/paper/2005.05238/) (2020) - [Federated Accelerated Stochastic Gradient Descent](https://mlsanity.com/paper/2006.08950/) (2020) - [Unified Optimal Analysis of the (Stochastic) Gradient Method](https://mlsanity.com/paper/1907.04232/) (2019) - [From Local SGD to Local Fixed-Point Methods for Federated Learning](https://mlsanity.com/paper/2004.01442/) (2020) - [On Large-Cohort Training for Federated Learning](https://mlsanity.com/paper/2106.07820/) (2021) - [FedExP: Speeding Up Federated Averaging via Extrapolation](https://mlsanity.com/paper/2301.09604/) (2023) - [STEM: A Stochastic Two-Sided Momentum Algorithm Achieving Near-Optimal Sample and Communication Complexities for Federated Learning](https://mlsanity.com/paper/2106.10435/) (2021) - [On-Demand Sampling: Learning Optimally from Multiple Distributions](https://mlsanity.com/paper/2210.12529/) (2022) - [Sharp Bounds for Federated Averaging (Local SGD) and Continuous Perspective](https://mlsanity.com/paper/2111.03741/) (2021) - [On the Unreasonable Effectiveness of Federated Averaging with Heterogeneous Data](https://mlsanity.com/paper/2206.04723/) (2022) - [On the Outsized Importance of Learning Rates in Local Update Methods](https://mlsanity.com/paper/2007.00878/) (2020) - [Graph Oracle Models, Lower Bounds, and Gaps for Parallel Stochastic Optimization](https://mlsanity.com/paper/1805.10222/) (2018) - [Parallel SGD: When does averaging help?](https://mlsanity.com/paper/1606.07365/) (2016) - [The Min-Max Complexity of Distributed Stochastic Convex Optimization with Intermittent Communication](https://mlsanity.com/paper/2102.01583/) (2021) - [Bias-Variance Reduced Local SGD for Less Heterogeneous Federated Learning](https://mlsanity.com/paper/2102.03198/) (2021) - [Stochastic Newton and Cubic Newton Methods with Simple Local Linear-Quadratic Rates](https://mlsanity.com/paper/1912.01597/) (2019) - [Improved Algorithms for Collaborative PAC Learning](https://mlsanity.com/paper/1805.08356/) (2018) - [FedPAGE: A Fast Local Stochastic Gradient Method for Communication-Efficient Federated Learning](https://mlsanity.com/paper/2108.04755/) (2021) ## Built on by (most cited first, 12 of 12) - [Task Arithmetic Through The Lens Of One-Shot Federated Learning](https://mlsanity.com/paper/2411.18607/) (2024) - [Understanding Outer Optimizers in Local SGD: Learning Rates, Momentum, and Acceleration](https://mlsanity.com/paper/2509.10439/) (2025) - [The Limitations of Model Retraining in the Face of Performativity](https://mlsanity.com/paper/2408.08499/) (2024) - [Revisiting LocalSGD and SCAFFOLD: Improved Rates and Missing Analysis](https://mlsanity.com/paper/2501.04443/) (2025) - [Incentivizing Truthful Collaboration in Heterogeneous Federated Learning](https://mlsanity.com/paper/2412.00980/) (2024) - [Constant Stepsize Local GD for Logistic Regression: Acceleration by Instability](https://mlsanity.com/paper/2506.13974/) (2025) - [Effectiveness of Distributed Gradient Descent with Local Steps for Overparameterized Models](https://mlsanity.com/paper/2412.07971/) (2024) - [Exploiting Similarity for Computation and Communication-Efficient Decentralized Optimization](https://mlsanity.com/paper/2506.05791/) (2025) - [First Provable Guarantees for Practical Private FL: Beyond Restrictive Assumptions](https://mlsanity.com/paper/2512.21521/) (2025) - [Improved Convergence Analysis of Topology Dependence in Decentralized SGD](https://mlsanity.com/paper/2606.09154/) (2026) - [Decoupled SGDA for Games with Intermittent Strategy Communication](https://mlsanity.com/paper/2501.14652/) (2025) - [How Edge of Stability Hinders SCAFFOLD in Federated Optimization](https://mlsanity.com/paper/2608.25873/) (2026) ## Abstract (arXiv) Local SGD is a popular optimization method in distributed learning, often outperforming other algorithms in practice, including mini-batch SGD. Despite this success, theoretically proving the dominance of local SGD in settings with reasonable data heterogeneity has been difficult, creating a significant gap between theory and practice. In this paper, we provide new lower bounds for local SGD under existing first-order data heterogeneity assumptions, showing that these assumptions are insufficient to prove the effectiveness of local update steps. Furthermore, under these same assumptions, we demonstrate the min-max optimality of accelerated mini-batch SGD, which fully resolves our understanding of distributed optimization for several problem classes. Our results emphasize the need for better models of data heterogeneity to understand the effectiveness of local SGD in practice. Towards this end, we consider higher-order smoothness and heterogeneity assumptions, providing new upper bounds that imply the dominance of local SGD over mini-batch SGD when data heterogeneity is low.