mlsanityData to 14 Oct 2026

The Limits and Potentials of Local SGD for Distributed Heterogeneous Learning with Intermittent Communication

arXiv 2405.11667 ↗First posted 19 May 2024cs.LG cs.DC math.OCcited by 12

Not on the map. Why?

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.

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

34 of 48 references.

References · 34

  1. 2016Communication-Efficient Learning of Deep Networks from Decentralized Datacited by 7,669
  2. 2019Advances and Open Problems in Federated Learningcited by 3,046
  3. 2019Introduction to Online Convex Optimizationcited by 803
  4. 2018Local SGD Converges Fast and Communicates Littlecited by 605
  5. 2020A Unified Theory of Decentralized SGD with Changing Topology and Local Updatescited by 367
  6. 2021A Field Guide to Federated Optimizationcited by 315
  7. 2019Tighter Theory for Local SGD on Identical and Heterogeneous Datacited by 266
  8. 2018Don't Use Large Mini-Batches, Use Local SGDcited by 202
  9. 2020Mime: Mimicking Centralized Stochastic Algorithms in Federated Learningcited by 154
  10. 2020Is Local SGD Better than Minibatch SGD?cited by 151
  11. 2020Minibatch vs Local SGD for Heterogeneous Distributed Learningcited by 147
  12. 2017Lower Bounds for Finding Stationary Points Icited by 126
22 more
  1. 2020FedSplit: An algorithmic framework for fast federated optimizationcited by 108
  2. 2020Federated Accelerated Stochastic Gradient Descentcited by 85
  3. 2019Unified Optimal Analysis of the (Stochastic) Gradient Methodcited by 82
  4. 2020From Local SGD to Local Fixed-Point Methods for Federated Learningcited by 74
  5. 2021On Large-Cohort Training for Federated Learningcited by 74
  6. 2023FedExP: Speeding Up Federated Averaging via Extrapolationcited by 69
  7. 2021STEM: A Stochastic Two-Sided Momentum Algorithm Achieving Near-Optimal Sample and Communication Complexities for Federated Learningcited by 43
  8. 2022On-Demand Sampling: Learning Optimally from Multiple Distributionscited by 39
  9. 2021Sharp Bounds for Federated Averaging (Local SGD) and Continuous Perspectivecited by 38
  10. 2022On the Unreasonable Effectiveness of Federated Averaging with Heterogeneous Datacited by 38
  11. 2020On the Outsized Importance of Learning Rates in Local Update Methodscited by 36
  12. 2018Graph Oracle Models, Lower Bounds, and Gaps for Parallel Stochastic Optimizationcited by 34
  13. 2016Parallel SGD: When does averaging help?cited by 32
  14. 2021The Min-Max Complexity of Distributed Stochastic Convex Optimization with Intermittent Communicationcited by 31
  15. 2021Bias-Variance Reduced Local SGD for Less Heterogeneous Federated Learningcited by 31
  16. 2019Stochastic Newton and Cubic Newton Methods with Simple Local Linear-Quadratic Ratescited by 24
  17. 2018Improved Algorithms for Collaborative PAC Learningcited by 20
  18. 2021FedPAGE: A Fast Local Stochastic Gradient Method for Communication-Efficient Federated Learningcited by 20
  19. 2021FedChain: Chained Algorithms for Near-Optimal Communication Cost in Federated Learningcited by 11
  20. 2023Federated Online and Bandit Convex Optimizationcited by 7
  21. 2021A Stochastic Newton Algorithm for Distributed Convex Optimizationcited by 6
  22. 2023On the Effect of Defections in Federated Learning and How to Prevent Themcited by 5

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2024: 4; 2025: 6; 2026: 2.

12 papers.

  1. 2024Task Arithmetic Through The Lens Of One-Shot Federated Learningcited by 12
  2. 2025Understanding Outer Optimizers in Local SGD: Learning Rates, Momentum, and Accelerationcited by 9
  3. 2024The Limitations of Model Retraining in the Face of Performativitycited by 4
  4. 2025Revisiting LocalSGD and SCAFFOLD: Improved Rates and Missing Analysiscited by 4
  5. 2024Incentivizing Truthful Collaboration in Heterogeneous Federated Learningcited by 3
  6. 2025Constant Stepsize Local GD for Logistic Regression: Acceleration by Instabilitycited by 2
  7. 2024Effectiveness of Distributed Gradient Descent with Local Steps for Overparameterized Modelscited by 1
  8. 2025Exploiting Similarity for Computation and Communication-Efficient Decentralized Optimizationcited by 1
  9. 2025First Provable Guarantees for Practical Private FL: Beyond Restrictive Assumptionscited by 1
  10. 2026Improved Convergence Analysis of Topology Dependence in Decentralized SGDcited by 1
  11. 2025Decoupled SGDA for Games with Intermittent Strategy Communicationcited by 0
  12. 2026How Edge of Stability Hinders SCAFFOLD in Federated Optimizationcited by 0