mlsanityData to 7 Oct 2026

Tighter Theory for Local SGD on Identical and Heterogeneous Data

arXiv 1909.04746 ↗First posted 10 Sep 2019cs.LG cs.DC cs.NAcited by 266

Not on the map. Why?

Abstract (arXiv)

We provide a new analysis of local SGD, removing unnecessary assumptions and elaborating on the difference between two data regimes: identical and heterogeneous. In both cases, we improve the existing theory and provide values of the optimal stepsize and optimal number of local iterations. Our bounds are based on a new notion of variance that is specific to local SGD methods with different data. The tightness of our results is guaranteed by recovering known statements when we plug H=1, where H is the number of local steps. The empirical evidence further validates the severe impact of data heterogeneity on the performance of local SGD.

Key facts. Cited by 266 papers in the map (data through 7 Oct 2026). First posted on arXiv 10 Sep 2019.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 63; 2022: 67; 2023: 50; 2024: 42; 2025: 28; 2026: 16.

266 papers.

Sort:

By area:

  1. 2021Federated Learning Based on Dynamic Regularizationcited by 555
  2. 2021A Field Guide to Federated Optimizationcited by 312
  3. 2022FedDC: Federated Learning with Non-IID Data via Local Drift Decoupling and Correctioncited by 181
  4. 2022Fine-tuning Global Model via Data-Free Knowledge Distillation for Non-IID Federated Learningcited by 172
  5. 2022ProxSkip: Yes! Local Gradient Steps Provably Lead to Communication Acceleration! Finally!cited by 134
  6. 2021Linear Convergence in Federated Learning: Tackling Client Heterogeneity and Sparse Gradientscited by 122
  7. 2021Federated Graph Classification over Non-IID Graphscited by 113
  8. 2021Distributionally Robust Federated Averagingcited by 104
  9. 2021Clustered Sampling: Low-Variance and Improved Representativity for Clients Selection in Federated Learningcited by 93
  10. 2021Trustworthy AI: A Computational Perspectivecited by 93
  11. 2021Preservation of the Global Knowledge by Not-True Distillation in Federated Learningcited by 87
  12. 2021Differentially Private Federated Learning on Heterogeneous Datacited by 74
38 more
  1. 2021On Large-Cohort Training for Federated Learningcited by 73
  2. 2021Fast Federated Learning in the Presence of Arbitrary Device Unavailabilitycited by 72
  3. 2023FedExP: Speeding Up Federated Averaging via Extrapolationcited by 68
  4. 2021What Do We Mean by Generalization in Federated Learning?cited by 62
  5. 2022FedVARP: Tackling the Variance Due to Partial Client Participation in Federated Learningcited by 62
  6. 2022Asynchronous SGD Beats Minibatch SGD Under Arbitrary Delayscited by 61
  7. 2022Communication-Efficient Stochastic Zeroth-Order Optimization for Federated Learningcited by 59
  8. 2022FedAvg with Fine Tuning: Local Updates Lead to Representation Learningcited by 55
  9. 2021FedNL: Making Newton-Type Methods Applicable to Federated Learningcited by 50
  10. 2021Hierarchical Federated Learning with Quantization: Convergence Analysis and System Designcited by 47
  11. 2021Local Stochastic Gradient Descent Ascent: Convergence Analysis and Communication Efficiencycited by 40
  12. 2021Sharp Bounds for Federated Averaging (Local SGD) and Continuous Perspectivecited by 38
  13. 2022Federated Minimax Optimization: Improved Convergence Analyses and Algorithmscited by 37
  14. 2022On Convergence of FedProx: Local Dissimilarity Invariant Bounds, Non-smoothness and Beyondcited by 37
  15. 2021Moshpit SGD: Communication-Efficient Decentralized Training on Heterogeneous Unreliable Devicescited by 36
  16. 2022On the Unreasonable Effectiveness of Federated Averaging with Heterogeneous Datacited by 36
  17. 2022Faster Adaptive Federated Learningcited by 35
  18. 2022SoteriaFL: A Unified Framework for Private Federated Learning with Communication Compressioncited by 34
  19. 2021Proximal and Federated Random Reshufflingcited by 33
  20. 2022Variance Reduced ProxSkip: Algorithm, Theory and Application to Federated Learningcited by 33
  21. 2021FedJAX: Federated learning simulation with JAXcited by 32
  22. 2021Local Adaptivity in Federated Learning: Convergence and Consistencycited by 31
  23. 2022On the Convergence of Clustered Federated Learningcited by 31
  24. 2021Bias-Variance Reduced Local SGD for Less Heterogeneous Federated Learningcited by 30
  25. 2021Implicit Gradient Alignment in Distributed and Federated Learningcited by 29
  26. 2023Towards Federated Foundation Models: Scalable Dataset Pipelines for Group-Structured Learningcited by 29
  27. 2021A New Look and Convergence Rate of Federated Multi-Task Learning with Laplacian Regularizationcited by 27
  28. 20223PC: Three Point Compressors for Communication-Efficient Distributed Training and a Better Theory for Lazy Aggregationcited by 27
  29. 2021Distributed Second Order Methods with Fast Rates and Compressed Communicationcited by 25
  30. 2021Decentralized Local Stochastic Extra-Gradient for Variational Inequalitiescited by 25
  31. 2022FedADMM: A Robust Federated Deep Learning Framework with Adaptivity to System Heterogeneitycited by 25
  32. 2022Sketching for First Order Method: Efficient Algorithm for Low-Bandwidth Channel and Vulnerabilitycited by 25
  33. 2023Federated Temporal Difference Learning with Linear Function Approximation under Environmental Heterogeneitycited by 25
  34. 2023Robust Distributed Learning: Tight Error Bounds and Breakdown Point under Data Heterogeneitycited by 25
  35. 2021CANITA: Faster Rates for Distributed Convex Optimization with Communication Compressioncited by 23
  36. 2021Personalized Federated Learning for Heterogeneous Clients with Clustered Knowledge Transfercited by 23
  37. 2021Towards Federated Learning on Time-Evolving Heterogeneous Datacited by 23
  38. 2022Server-Side Stepsizes and Sampling Without Replacement Provably Help in Federated Optimizationcited by 23

50 most cited of 266 All 266 (JSON)