mlsanityData to 7 Oct 2026

Local SGD with Periodic Averaging: Tighter Analysis and Adaptive Synchronization

arXiv 1910.13598 ↗First posted 30 Oct 2019cs.LG cs.DC stat.MLcited by 106

Not on the map. Why?

Abstract (arXiv)

Communication overhead is one of the key challenges that hinders the scalability of distributed optimization algorithms. In this paper, we study local distributed SGD, where data is partitioned among computation nodes, and the computation nodes perform local updates with periodically exchanging the model among the workers to perform averaging. While local SGD is empirically shown to provide promising results, a theoretical understanding of its performance remains open. We strengthen convergence analysis for local SGD, and show that local SGD can be far less expensive and applied far more generally than current theory suggests. Specifically, we show that for loss functions that satisfy the Polyak-Lojasiewicz condition, O((pT)1/3) rounds of communication suffice to achieve a linear speed up, that is, an error of O(1/pT), where T is the total number of model updates at each worker. This is in contrast with previous work which required higher number of communication rounds, as well as was limited to strongly convex loss functions, for a similar asymptotic performance. We also develop an adaptive synchronization scheme that provides a general condition for linear speed up. Finally, we validate the theory with experimental results, running over AWS EC2 clouds and an internal GPU cluster.

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

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 28; 2022: 23; 2023: 21; 2024: 16; 2025: 10; 2026: 8.

106 papers.

Sort:

  1. 2021Federated Learning with Buffered Asynchronous Aggregationcited by 188
  2. 2021Linear Convergence in Federated Learning: Tackling Client Heterogeneity and Sparse Gradientscited by 122
  3. 2021Distributionally Robust Federated Averagingcited by 104
  4. 2021Clustered Sampling: Low-Variance and Improved Representativity for Clients Selection in Federated Learningcited by 93
  5. 2021What Do We Mean by Generalization in Federated Learning?cited by 62
  6. 2021Adaptive Quantization of Model Updates for Communication-Efficient Federated Learningcited by 60
  7. 2022FedAvg with Fine Tuning: Local Updates Lead to Representation Learningcited by 55
  8. 2022A Unified Analysis of Federated Learning with Arbitrary Client Participationcited by 45
  9. 2021Local Stochastic Gradient Descent Ascent: Convergence Analysis and Communication Efficiencycited by 40
  10. 2021Layer-wise Adaptive Model Aggregation for Scalable Federated Learningcited by 35
  11. 2023Decentralized Gradient Tracking with Local Stepscited by 32
  12. 2023On the Convergence of Federated Averaging with Cyclic Client Participationcited by 31
38 more
  1. 2021The Min-Max Complexity of Distributed Stochastic Convex Optimization with Intermittent Communicationcited by 30
  2. 2021Bias-Variance Reduced Local SGD for Less Heterogeneous Federated Learningcited by 30
  3. 2021FedDR -- Randomized Douglas-Rachford Splitting Algorithms for Nonconvex Federated Composite Optimizationcited by 29
  4. 2022FedKL: Tackling Data Heterogeneity in Federated Reinforcement Learning by Penalizing KL Divergencecited by 29
  5. 2023Towards Federated Foundation Models: Scalable Dataset Pipelines for Group-Structured Learningcited by 29
  6. 2023Federated Temporal Difference Learning with Linear Function Approximation under Environmental Heterogeneitycited by 25
  7. 2021Federated Deep AUC Maximization for Heterogeneous Data with a Constant Communication Complexitycited by 21
  8. 2021Exploiting Heterogeneity in Robust Federated Best-Arm Identificationcited by 20
  9. 2022A Communication-Efficient Distributed Gradient Clipping Algorithm for Training Deep Neural Networkscited by 20
  10. 2023FusionAI: Decentralized Training and Deploying LLMs with Massive Consumer-Level GPUscited by 20
  11. 2021Communication-efficient SGD: From Local SGD to One-Shot Averagingcited by 19
  12. 2022FedShuffle: Recipes for Better Use of Local Work in Federated Learningcited by 19
  13. 2021Persia: An Open, Hybrid System Scaling Deep Learning-based Recommenders up to 100 Trillion Parameterscited by 17
  14. 2021LocalNewton: Reducing Communication Bottleneck for Distributed Learningcited by 15
  15. 2022Towards Communication-efficient Vertical Federated Learning Training via Cache-enabled Local Updatescited by 15
  16. 2021Citadel: Protecting Data Privacy and Model Confidentiality for Collaborative Learning with SGXcited by 14
  17. 2022Anchor Sampling for Federated Learning with Partial Client Participationcited by 14
  18. 2021BAGUA: Scaling up Distributed Learning with System Relaxationscited by 13
  19. 2021Compositional federated learning: Applications in distributionally robust averaging and meta learningcited by 12
  20. 2022Fast Composite Optimization and Statistical Recovery in Federated Learningcited by 12
  21. 2022Federated Learning with Flexible Controlcited by 12
  22. 2023Taming Resource Heterogeneity In Distributed ML Training With Dynamic Batchingcited by 12
  23. 2021Local SGD Optimizes Overparameterized Neural Networks in Polynomial Timecited by 10
  24. 2022FeDXL: Provable Federated Learning for Deep X-Risk Optimizationcited by 10
  25. 2023More Communication Does Not Result in Smaller Generalization Error in Federated Learningcited by 10
  26. 2023MimiC: Combating Client Dropouts in Federated Learning by Mimicking Central Updatescited by 10
  27. 2024Communication-Efficient Large-Scale Distributed Deep Learning: A Comprehensive Surveycited by 9
  28. 2021Federated Learning over Noisy Channels: Convergence Analysis and Design Examplescited by 8
  29. 2022Partial Model Averaging in Federated Learning: Performance Guarantees and Benefitscited by 8
  30. 2022Fast Heterogeneous Federated Learning with Hybrid Client Selectioncited by 8
  31. 2023Federated Minimax Optimization with Client Heterogeneitycited by 8
  32. 2023Lessons from Generalization Error Analysis of Federated Learning: You May Communicate Less Often!cited by 8
  33. 2024The Sample-Communication Complexity Trade-off in Federated Q-Learningcited by 8
  34. 2022Confederated Learning: Federated Learning with Decentralized Edge Serverscited by 7
  35. 2023A Communication-Efficient Adaptive Algorithm for Federated Learning under Cumulative Regretcited by 7
  36. 2023EPISODE: Episodic Gradient Clipping with Periodic Resampled Corrections for Federated Learning with Heterogeneous Datacited by 7
  37. 2024Achieving Linear Speedup in Asynchronous Federated Learning with Heterogeneous Clientscited by 7
  38. 2022Personalized Federated Learning with Communication Compressioncited by 6

50 most cited of 106 All 106 (JSON)