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

arXiv: https://arxiv.org/abs/2111.03741 · HTML: https://mlsanity.com/paper/2111.03741/

## Key facts

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

## Builds on (most cited first, 30 of 51)

- [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)
- [Federated Optimization in Heterogeneous Networks](https://mlsanity.com/paper/1812.06127/) (2018)
- [Federated Learning: Challenges, Methods, and Future Directions](https://mlsanity.com/paper/1908.07873/) (2019)
- [On the Convergence of FedAvg on Non-IID Data](https://mlsanity.com/paper/1907.02189/) (2019)
- [Adaptive Federated Optimization](https://mlsanity.com/paper/2003.00295/) (2020)
- [Measuring the Effects of Non-Identical Data Distribution for Federated Visual Classification](https://mlsanity.com/paper/1909.06335/) (2019)
- [Ensemble Distillation for Robust Model Fusion in Federated Learning](https://mlsanity.com/paper/2006.07242/) (2020)
- [Federated Multi-Task Learning](https://mlsanity.com/paper/1705.10467/) (2017)
- [Personalized Federated Learning with Moreau Envelopes](https://mlsanity.com/paper/2006.08848/) (2020)
- [Local SGD Converges Fast and Communicates Little](https://mlsanity.com/paper/1805.09767/) (2018)
- [Agnostic Federated Learning](https://mlsanity.com/paper/1902.00146/) (2019)
- [A Unified Theory of Decentralized SGD with Changing Topology and Local Updates](https://mlsanity.com/paper/2003.10422/) (2020)
- [Adaptive Personalized Federated Learning](https://mlsanity.com/paper/2003.13461/) (2020)
- [FedPAQ: A Communication-Efficient Federated Learning Method with Periodic Averaging and Quantization](https://mlsanity.com/paper/1909.13014/) (2019)
- [HeteroFL: Computation and Communication Efficient Federated Learning for Heterogeneous Clients](https://mlsanity.com/paper/2010.01264/) (2020)
- [A Field Guide to Federated Optimization](https://mlsanity.com/paper/2107.06917/) (2021)
- [Parallel Restarted SGD with Faster Convergence and Less Communication: Demystifying Why Model Averaging Works for Deep Learning](https://mlsanity.com/paper/1807.06629/) (2018)
- [Three Factors Influencing Minima in SGD](https://mlsanity.com/paper/1711.04623/) (2017)
- [Improving Federated Learning Personalization via Model Agnostic Meta Learning](https://mlsanity.com/paper/1909.12488/) (2019)
- [Tighter Theory for Local SGD on Identical and Heterogeneous Data](https://mlsanity.com/paper/1909.04746/) (2019)
- [Federated Learning of a Mixture of Global and Local Models](https://mlsanity.com/paper/2002.05516/) (2020)
- [Don't Use Large Mini-Batches, Use Local SGD](https://mlsanity.com/paper/1808.07217/) (2018)
- [Federated Optimization:Distributed Optimization Beyond the Datacenter](https://mlsanity.com/paper/1511.03575/) (2015)
- [On the Linear Speedup Analysis of Communication Efficient Momentum SGD for Distributed Non-Convex Optimization](https://mlsanity.com/paper/1905.03817/) (2019)
- [FedBE: Making Bayesian Model Ensemble Applicable to Federated Learning](https://mlsanity.com/paper/2009.01974/) (2020)
- [Federated Meta-Learning with Fast Convergence and Efficient Communication](https://mlsanity.com/paper/1802.07876/) (2018)
- [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)
- [FedPD: A Federated Learning Framework with Optimal Rates and Adaptivity to Non-IID Data](https://mlsanity.com/paper/2005.11418/) (2020)

## Built on by (most cited first, 30 of 38)

- [Federated Learning for Generalization, Robustness, Fairness: A Survey and Benchmark](https://mlsanity.com/paper/2311.06750/) (2023)
- [On the Unreasonable Effectiveness of Federated Averaging with Heterogeneous Data](https://mlsanity.com/paper/2206.04723/) (2022)
- [Variance Reduced ProxSkip: Algorithm, Theory and Application to Federated Learning](https://mlsanity.com/paper/2207.04338/) (2022)
- [Can 5th Generation Local Training Methods Support Client Sampling? Yes!](https://mlsanity.com/paper/2212.14370/) (2022)
- [Federated Optimization Algorithms with Random Reshuffling and Gradient Compression](https://mlsanity.com/paper/2206.07021/) (2022)
- [Randomized Asymmetric Chain of LoRA: The First Meaningful Theoretical Framework for Low-Rank Adaptation](https://mlsanity.com/paper/2410.08305/) (2024)
- [The Limits and Potentials of Local SGD for Distributed Heterogeneous Learning with Intermittent Communication](https://mlsanity.com/paper/2405.11667/) (2024)
- [Task Arithmetic Through The Lens Of One-Shot Federated Learning](https://mlsanity.com/paper/2411.18607/) (2024)
- [CompressedScaffnew: The First Theoretical Double Acceleration of Communication from Local Training and Compression in Distributed Optimization](https://mlsanity.com/paper/2210.13277/) (2022)
- [Understanding Outer Optimizers in Local SGD: Learning Rates, Momentum, and Acceleration](https://mlsanity.com/paper/2509.10439/) (2025)
- [Improving Accelerated Federated Learning with Compression and Importance Sampling](https://mlsanity.com/paper/2306.03240/) (2023)
- [Federated Learning under Periodic Client Participation and Heterogeneous Data: A New Communication-Efficient Algorithm and Analysis](https://mlsanity.com/paper/2410.23131/) (2024)
- [Fast Adaptive Federated Bilevel Optimization](https://mlsanity.com/paper/2211.01122/) (2022)
- [Federated Online and Bandit Convex Optimization](https://mlsanity.com/paper/2311.17586/) (2023)
- [Adaptive Federated Minimax Optimization with Lower Complexities](https://mlsanity.com/paper/2211.07303/) (2022)
- [Faster Convergence of Local SGD for Over-Parameterized Models](https://mlsanity.com/paper/2201.12719/) (2022)
- [TAMUNA: Doubly Accelerated Distributed Optimization under Partial Participation](https://mlsanity.com/paper/2302.09832/) (2023)
- [SLowcal-SGD: Slow Query Points Improve Local-SGD for Stochastic Convex Optimization](https://mlsanity.com/paper/2304.04169/) (2023)
- [Distributed Event-Based Learning via ADMM](https://mlsanity.com/paper/2405.10618/) (2024)
- [Incentivizing Truthful Collaboration in Heterogeneous Federated Learning](https://mlsanity.com/paper/2412.00980/) (2024)
- [FedDA: Faster Framework of Local Adaptive Gradient Methods via Restarted Dual Averaging](https://mlsanity.com/paper/2302.06103/) (2023)
- [On the Convergence of Federated Learning Algorithms without Data Similarity](https://mlsanity.com/paper/2403.02347/) (2024)
- [Constant Stepsize Local GD for Logistic Regression: Acceleration by Instability](https://mlsanity.com/paper/2506.13974/) (2025)
- [Local Methods with Adaptivity via Scaling](https://mlsanity.com/paper/2406.00846/) (2024)
- [Addressing Label Shift in Distributed Learning via Entropy Regularization](https://mlsanity.com/paper/2502.02544/) (2025)
- [Sharp Gaussian approximations for Decentralized Federated Learning](https://mlsanity.com/paper/2505.08125/) (2025)
- [Personalized Collaborative Learning with Affinity-Based Variance Reduction](https://mlsanity.com/paper/2510.16232/) (2025)
- [Tight Analysis of Decentralized SGD: A Markov Chain Perspective](https://mlsanity.com/paper/2601.07021/) (2026)
- [BiCoLoR: Communication-Efficient Optimization with Bidirectional Compression and Local Training](https://mlsanity.com/paper/2601.12400/) (2026)
- [Improved Convergence Analysis of Topology Dependence in Decentralized SGD](https://mlsanity.com/paper/2606.09154/) (2026)

## 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.