# On the Unreasonable Effectiveness of Federated Averaging with Heterogeneous Data

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

## Key facts

- Cited by 38 papers in the map (data through 14 Oct 2026).
- Builds on 32 of its 32 references that are in the map.
- First posted on arXiv 9 Jun 2022.

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

- [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)
- [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)
- [Tackling the Objective Inconsistency Problem in Heterogeneous Federated Optimization](https://mlsanity.com/paper/2007.07481/) (2020)
- [Measuring the Effects of Non-Identical Data Distribution for Federated Visual Classification](https://mlsanity.com/paper/1909.06335/) (2019)
- [On the Convergence of Adam and Beyond](https://mlsanity.com/paper/1904.09237/) (2019)
- [Local SGD Converges Fast and Communicates Little](https://mlsanity.com/paper/1805.09767/) (2018)
- [Can Decentralized Algorithms Outperform Centralized Algorithms? A Case Study for Decentralized Parallel Stochastic Gradient Descent](https://mlsanity.com/paper/1705.09056/) (2017)
- [A Unified Theory of Decentralized SGD with Changing Topology and Local Updates](https://mlsanity.com/paper/2003.10422/) (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)
- [Tighter Theory for Local SGD on Identical and Heterogeneous Data](https://mlsanity.com/paper/1909.04746/) (2019)
- [SGD: General Analysis and Improved Rates](https://mlsanity.com/paper/1901.09401/) (2019)
- [Achieving Linear Speedup with Partial Worker Participation in Non-IID Federated Learning](https://mlsanity.com/paper/2101.11203/) (2021)
- [On the Linear Speedup Analysis of Communication Efficient Momentum SGD for Distributed Non-Convex Optimization](https://mlsanity.com/paper/1905.03817/) (2019)
- [SCAFFOLD: Stochastic Controlled Averaging for Federated Learning](https://mlsanity.com/paper/1910.06378/) (2019)
- [On the Convergence of Decentralized Gradient Descent](https://mlsanity.com/paper/1310.7063/) (2013)
- [On the Convergence of Local Descent Methods in Federated Learning](https://mlsanity.com/paper/1910.14425/) (2019)
- [Stochastic Gradient Push for Distributed Deep Learning](https://mlsanity.com/paper/1811.10792/) (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)
- [SlowMo: Improving Communication-Efficient Distributed SGD with Slow Momentum](https://mlsanity.com/paper/1910.00643/) (2019)
- [Cooperative SGD: A unified Framework for the Design and Analysis of Communication-Efficient SGD Algorithms](https://mlsanity.com/paper/1808.07576/) (2018)
- [On the convergence properties of a K-step averaging stochastic gradient descent algorithm for nonconvex optimization](https://mlsanity.com/paper/1708.01012/) (2017)
- [Unified Optimal Analysis of the (Stochastic) Gradient Method](https://mlsanity.com/paper/1907.04232/) (2019)
- [From Local SGD to Local Fixed-Point Methods for Federated Learning](https://mlsanity.com/paper/2004.01442/) (2020)
- [On Large-Cohort Training for Federated Learning](https://mlsanity.com/paper/2106.07820/) (2021)
- [Convergence and Accuracy Trade-Offs in Federated Learning and Meta-Learning](https://mlsanity.com/paper/2103.05032/) (2021)

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

- [How to DP-fy ML: A Practical Guide to Machine Learning with Differential Privacy](https://mlsanity.com/paper/2303.00654/) (2023)
- [FedML-HE: An Efficient Homomorphic-Encryption-Based Privacy-Preserving Federated Learning System](https://mlsanity.com/paper/2303.10837/) (2023)
- [On the Convergence of Federated Averaging with Cyclic Client Participation](https://mlsanity.com/paper/2302.03109/) (2023)
- [TCT: Convexifying Federated Learning using Bootstrapped Neural Tangent Kernels](https://mlsanity.com/paper/2207.06343/) (2022)
- [Why (and When) does Local SGD Generalize Better than SGD?](https://mlsanity.com/paper/2303.01215/) (2023)
- [Learning to Generate Image Embeddings with User-level Differential Privacy](https://mlsanity.com/paper/2211.10844/) (2022)
- [Decentralized SGD and Average-direction SAM are Asymptotically Equivalent](https://mlsanity.com/paper/2306.02913/) (2023)
- [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)
- [Understanding and Improving Model Averaging in Federated Learning on Heterogeneous Data](https://mlsanity.com/paper/2305.07845/) (2023)
- [Federated Online and Bandit Convex Optimization](https://mlsanity.com/paper/2311.17586/) (2023)
- [SCAFFLSA: Taming Heterogeneity in Federated Linear Stochastic Approximation and TD Learning](https://mlsanity.com/paper/2402.04114/) (2024)
- [A Privacy Preserving System for Movie Recommendations Using Federated Learning](https://mlsanity.com/paper/2303.04689/) (2023)
- [Distributed Personalized Empirical Risk Minimization](https://mlsanity.com/paper/2310.17761/) (2023)
- [Distributed Stochastic Optimization under a General Variance Condition](https://mlsanity.com/paper/2301.12677/) (2023)
- [A New Theoretical Perspective on Data Heterogeneity in Federated Optimization](https://mlsanity.com/paper/2407.15567/) (2024)
- [Federated Learning from Molecules to Processes: A Perspective](https://mlsanity.com/paper/2506.18525/) (2025)
- [An Empirical Evaluation of Federated Contextual Bandit Algorithms](https://mlsanity.com/paper/2303.10218/) (2023)
- [Synthetic data shuffling accelerates the convergence of federated learning under data heterogeneity](https://mlsanity.com/paper/2306.13263/) (2023)
- [On the Convergence of Federated Learning Algorithms without Data Similarity](https://mlsanity.com/paper/2403.02347/) (2024)
- [On the Convergence Rates of Federated Q-Learning across Heterogeneous Environments](https://mlsanity.com/paper/2409.03897/) (2024)
- [Constant Stepsize Local GD for Logistic Regression: Acceleration by Instability](https://mlsanity.com/paper/2506.13974/) (2025)
- [Debiasing Federated Learning with Correlated Client Participation](https://mlsanity.com/paper/2410.01209/) (2024)
- [Heterogeneity Matters even More in Distributed Learning: Study from Generalization Perspective](https://mlsanity.com/paper/2503.01598/) (2025)
- [Tight Analysis of Decentralized SGD: A Markov Chain Perspective](https://mlsanity.com/paper/2601.07021/) (2026)
- [Improved Convergence Analysis of Topology Dependence in Decentralized SGD](https://mlsanity.com/paper/2606.09154/) (2026)
- [Communication-Efficient Zeroth-Order Distributed Online Optimization: Algorithm, Theory, and Applications](https://mlsanity.com/paper/2306.05655/) (2023)
- [FedSym: Unleashing the Power of Entropy for Benchmarking the Algorithms for Federated Learning](https://mlsanity.com/paper/2310.07807/) (2023)
- [Understanding Generalization of Federated Learning: the Trade-off between Model Stability and Optimization](https://mlsanity.com/paper/2411.16303/) (2024)
- [Refined Analysis of Federated Averaging and Federated Richardson-Romberg](https://mlsanity.com/paper/2412.01389/) (2024)

## Abstract (arXiv)

Existing theory predicts that data heterogeneity will degrade the performance of the Federated Averaging (FedAvg) algorithm in federated learning. However, in practice, the simple FedAvg algorithm converges very well. This paper explains the seemingly unreasonable effectiveness of FedAvg that contradicts the previous theoretical predictions. We find that the key assumption of bounded gradient dissimilarity in previous theoretical analyses is too pessimistic to characterize data heterogeneity in practical applications. For a simple quadratic problem, we demonstrate there exist regimes where large gradient dissimilarity does not have any negative impact on the convergence of FedAvg. Motivated by this observation, we propose a new quantity, average drift at optimum, to measure the effects of data heterogeneity, and explicitly use it to present a new theoretical analysis of FedAvg. We show that the average drift at optimum is nearly zero across many real-world federated training tasks, whereas the gradient dissimilarity can be large. And our new analysis suggests FedAvg can have identical convergence rates in homogeneous and heterogeneous data settings, and hence, leads to better understanding of its empirical success.