mlsanityData to 7 Oct 2026

Sharp Bounds for Federated Averaging (Local SGD) and Continuous Perspective

arXiv 2111.03741 ↗First posted 5 Nov 2021cs.LG cs.DC math.OCcited by 38

Not on the map. Why?

Abstract (arXiv)

Federated Averaging (FedAvg), also known as Local SGD, is one of the most popular algorithms in Federated Learning (FL). Despite its simplicity and popularity, the convergence rate of FedAvg has thus far been undetermined. Even under the simplest assumptions (convex, smooth, homogeneous, and bounded covariance), the best-known upper and lower bounds do not match, and it is not clear whether the existing analysis captures the capacity of the algorithm. In this work, we first resolve this question by providing a lower bound for FedAvg that matches the existing upper bound, which shows the existing FedAvg upper bound analysis is not improvable. Additionally, we establish a lower bound in a heterogeneous setting that nearly matches the existing upper bound. While our lower bounds show the limitations of FedAvg, under an additional assumption of third-order smoothness, we prove more optimistic state-of-the-art convergence results in both convex and non-convex settings. Our analysis stems from a notion we call iterate bias, which is defined by the deviation of the expectation of the SGD trajectory from the noiseless gradient descent trajectory with the same initialization. We prove novel sharp bounds on this quantity, and show intuitively how to analyze this quantity from a Stochastic Differential Equation (SDE) perspective.

Key facts. Cited by 38 papers in the map (data through 7 Oct 2026). Builds on 51 of its 76 references that are in the map. First posted on arXiv 5 Nov 2021.

Builds on

51 of 76 references.

References · 51

  1. 2016Communication-Efficient Learning of Deep Networks from Decentralized Datacited by 7,592
  2. 2019Advances and Open Problems in Federated Learningcited by 3,021
  3. 2018Federated Optimization in Heterogeneous Networkscited by 2,971
  4. 2019Federated Learning: Challenges, Methods, and Future Directionscited by 1,531
  5. 2019On the Convergence of FedAvg on Non-IID Datacited by 1,220
  6. 2020Adaptive Federated Optimizationcited by 1,036
  7. 2019Measuring the Effects of Non-Identical Data Distribution for Federated Visual Classificationcited by 836
  8. 2020Ensemble Distillation for Robust Model Fusion in Federated Learningcited by 678
  9. 2017Federated Multi-Task Learningcited by 669
  10. 2020Personalized Federated Learning with Moreau Envelopescited by 612
  11. 2018Local SGD Converges Fast and Communicates Littlecited by 595
  12. 2019Agnostic Federated Learningcited by 451
38 more
  1. 2020A Unified Theory of Decentralized SGD with Changing Topology and Local Updatescited by 361
  2. 2020Adaptive Personalized Federated Learningcited by 353
  3. 2019FedPAQ: A Communication-Efficient Federated Learning Method with Periodic Averaging and Quantizationcited by 349
  4. 2020HeteroFL: Computation and Communication Efficient Federated Learning for Heterogeneous Clientscited by 334
  5. 2021A Field Guide to Federated Optimizationcited by 312
  6. 2018Parallel Restarted SGD with Faster Convergence and Less Communication: Demystifying Why Model Averaging Works for Deep Learningcited by 277
  7. 2017Three Factors Influencing Minima in SGDcited by 270
  8. 2019Tighter Theory for Local SGD on Identical and Heterogeneous Datacited by 266
  9. 2019Improving Federated Learning Personalization via Model Agnostic Meta Learningcited by 264
  10. 2020Federated Learning of a Mixture of Global and Local Modelscited by 208
  11. 2018Don't Use Large Mini-Batches, Use Local SGDcited by 201
  12. 2015Federated Optimization:Distributed Optimization Beyond the Datacentercited by 193
  13. 2019On the Linear Speedup Analysis of Communication Efficient Momentum SGD for Distributed Non-Convex Optimizationcited by 178
  14. 2020FedBE: Making Bayesian Model Ensemble Applicable to Federated Learningcited by 176
  15. 2018Federated Meta-Learning with Fast Convergence and Efficient Communicationcited by 154
  16. 2020Is Local SGD Better than Minibatch SGD?cited by 151
  17. 2020Minibatch vs Local SGD for Heterogeneous Distributed Learningcited by 147
  18. 2020FedPD: A Federated Learning Framework with Optimal Rates and Adaptivity to Non-IID Datacited by 143
  19. 2019Implicit regularization for deep neural networks driven by an Ornstein-Uhlenbeck like processcited by 123
  20. 2020Lower Bounds and Optimal Algorithms for Personalized Federated Learningcited by 122
  21. 2021Label Noise SGD Provably Prefers Flat Global Minimizerscited by 121
  22. 2020FedSplit: An algorithmic framework for fast federated optimizationcited by 108
  23. 2021FedMix: Approximation of Mixup under Mean Augmented Federated Learningcited by 108
  24. 2018Cooperative SGD: A unified Framework for the Design and Analysis of Communication-Efficient SGD Algorithmscited by 106
  25. 2017On the convergence properties of a K-step averaging stochastic gradient descent algorithm for nonconvex optimizationcited by 91
  26. 2017Implicit Regularization in Deep Learningcited by 90
  27. 2020Federated Accelerated Stochastic Gradient Descentcited by 85
  28. 2017Bridging the Gap between Constant Step Size Stochastic Gradient Descent and Markov Chainscited by 84
  29. 2019Variance Reduced Local SGD with Lower Communication Complexitycited by 80
  30. 2020Federated Learning via Posterior Averaging: A New Perspective and Practical Algorithmscited by 78
  31. 2021What Do We Mean by Generalization in Federated Learning?cited by 62
  32. 2020Federated Composite Optimizationcited by 49
  33. 2020On the Outsized Importance of Learning Rates in Local Update Methodscited by 34
  34. 2021The Min-Max Complexity of Distributed Stochastic Convex Optimization with Intermittent Communicationcited by 30
  35. 2019Distributed Training with Heterogeneous Data: Bridging Median- and Mean-Based Algorithmscited by 29
  36. 2020Federated Residual Learningcited by 23
  37. 2014On the Optimality of Averaging in Distributed Statistical Learningcited by 14
  38. 2019On the Computation and Communication Complexity of Parallel SGD with Dynamic Batch Sizes for Stochastic Non-Convex Optimizationcited by 14

50 most cited of 51 All 51 (JSON)

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2022: 8; 2023: 7; 2024: 10; 2025: 7; 2026: 6.

38 papers.

Sort:

  1. 2023Federated Learning for Generalization, Robustness, Fairness: A Survey and Benchmarkcited by 97
  2. 2022On the Unreasonable Effectiveness of Federated Averaging with Heterogeneous Datacited by 36
  3. 2022Variance Reduced ProxSkip: Algorithm, Theory and Application to Federated Learningcited by 33
  4. 2022Can 5th Generation Local Training Methods Support Client Sampling? Yes!cited by 22
  5. 2022Federated Optimization Algorithms with Random Reshuffling and Gradient Compressioncited by 18
  6. 2024The Limits and Potentials of Local SGD for Distributed Heterogeneous Learning with Intermittent Communicationcited by 12
  7. 2024Randomized Asymmetric Chain of LoRA: The First Meaningful Theoretical Framework for Low-Rank Adaptationcited by 12
  8. 2024Task Arithmetic Through The Lens Of One-Shot Federated Learningcited by 12
  9. 2022CompressedScaffnew: The First Theoretical Double Acceleration of Communication from Local Training and Compression in Distributed Optimizationcited by 11
  10. 2024Federated Learning under Periodic Client Participation and Heterogeneous Data: A New Communication-Efficient Algorithm and Analysiscited by 8
  11. 2023Improving Accelerated Federated Learning with Compression and Importance Samplingcited by 7
  12. 2023Federated Online and Bandit Convex Optimizationcited by 7
26 more
  1. 2025Understanding Outer Optimizers in Local SGD: Learning Rates, Momentum, and Accelerationcited by 7
  2. 2022Fast Adaptive Federated Bilevel Optimizationcited by 6
  3. 2022Adaptive Federated Minimax Optimization with Lower Complexitiescited by 5
  4. 2022Faster Convergence of Local SGD for Over-Parameterized Modelscited by 4
  5. 2023SLowcal-SGD: Slow Query Points Improve Local-SGD for Stochastic Convex Optimizationcited by 4
  6. 2023TAMUNA: Doubly Accelerated Distributed Optimization under Partial Participationcited by 3
  7. 2024Distributed Event-Based Learning via ADMMcited by 3
  8. 2024Incentivizing Truthful Collaboration in Heterogeneous Federated Learningcited by 3
  9. 2023FedDA: Faster Framework of Local Adaptive Gradient Methods via Restarted Dual Averagingcited by 2
  10. 2024On the Convergence of Federated Learning Algorithms without Data Similaritycited by 2
  11. 2024Local Methods with Adaptivity via Scalingcited by 1
  12. 2025Addressing Label Shift in Distributed Learning via Entropy Regularizationcited by 1
  13. 2025Sharp Gaussian approximations for Decentralized Federated Learningcited by 1
  14. 2025Constant Stepsize Local GD for Logistic Regression: Acceleration by Instabilitycited by 1
  15. 2025Personalized Collaborative Learning with Affinity-Based Variance Reductioncited by 1
  16. 2026Tight Analysis of Decentralized SGD: A Markov Chain Perspectivecited by 1
  17. 2026BiCoLoR: Communication-Efficient Optimization with Bidirectional Compression and Local Trainingcited by 1
  18. 2023Federated Composite Saddle Point Optimizationcited by 0
  19. 2024FLeNS: Federated Learning with Enhanced Nesterov-Newton Sketchcited by 0
  20. 2024Refined Analysis of Federated Averaging and Federated Richardson-Rombergcited by 0
  21. 2025Convergence Analysis of Federated Learning Methods Using Backward Error Analysiscited by 0
  22. 2025Avoid Forgetting by Preserving Global Knowledge Gradients in Federated Learning with Non-IID Datacited by 0
  23. 2026Local MixVR: Breaking the Communication-Sample Dependence in Distributed Learningcited by 0
  24. 2026Improved Convergence Analysis of Topology Dependence in Decentralized SGDcited by 0
  25. 2026How Edge of Stability Hinders SCAFFOLD in Federated Optimizationcited by 0
  26. 2026DART-FL: Burst-Aware Multitask Federated Learning under Dynamic Inference Demand at the Edgecited by 0