# On the Convergence of FedAvg on Non-IID Data

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

## Key facts

- Cited by 1,229 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 4 Jul 2019.

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

- [TIES-Merging: Resolving Interference When Merging Models](https://mlsanity.com/paper/2306.01708/) (2023)
- [Model-Contrastive Federated Learning](https://mlsanity.com/paper/2103.16257/) (2021)
- [FedBN: Federated Learning on Non-IID Features via Local Batch Normalization](https://mlsanity.com/paper/2102.07623/) (2021)
- [Federated Learning on Non-IID Data Silos: An Experimental Study](https://mlsanity.com/paper/2102.02079/) (2021)
- [Federated Learning Based on Dynamic Regularization](https://mlsanity.com/paper/2111.04263/) (2021)
- [Towards Personalized Federated Learning](https://mlsanity.com/paper/2103.00710/) (2021)
- [Towards Out-Of-Distribution Generalization: A Survey](https://mlsanity.com/paper/2108.13624/) (2021)
- [Dataless Knowledge Fusion by Merging Weights of Language Models](https://mlsanity.com/paper/2212.09849/) (2022)
- [Data-Free Knowledge Distillation for Heterogeneous Federated Learning](https://mlsanity.com/paper/2105.10056/) (2021)
- [AdaMerging: Adaptive Model Merging for Multi-Task Learning](https://mlsanity.com/paper/2310.02575/) (2023)
- [No Fear of Heterogeneity: Classifier Calibration for Federated Learning with Non-IID Data](https://mlsanity.com/paper/2106.05001/) (2021)
- [Trustworthy AI: From Principles to Practices](https://mlsanity.com/paper/2110.01167/) (2021)
- [Achieving Linear Speedup with Partial Worker Participation in Non-IID Federated Learning](https://mlsanity.com/paper/2101.11203/) (2021)
- [Federated Learning with Buffered Asynchronous Aggregation](https://mlsanity.com/paper/2106.06639/) (2021)
- [FedDC: Federated Learning with Non-IID Data via Local Drift Decoupling and Correction](https://mlsanity.com/paper/2203.11751/) (2022)
- [Fine-tuning Global Model via Data-Free Knowledge Distillation for Non-IID Federated Learning](https://mlsanity.com/paper/2203.09249/) (2022)
- [FLoRA: Federated Fine-Tuning Large Language Models with Heterogeneous Low-Rank Adaptations](https://mlsanity.com/paper/2409.05976/) (2024)
- [Generalized Federated Learning via Sharpness Aware Minimization](https://mlsanity.com/paper/2206.02618/) (2022)
- [OpenFedLLM: Training Large Language Models on Decentralized Private Data via Federated Learning](https://mlsanity.com/paper/2402.06954/) (2024)
- [Linear Convergence in Federated Learning: Tackling Client Heterogeneity and Sparse Gradients](https://mlsanity.com/paper/2102.07053/) (2021)
- [Decentralized Federated Averaging](https://mlsanity.com/paper/2104.11375/) (2021)
- [Federated Learning with Partial Model Personalization](https://mlsanity.com/paper/2204.03809/) (2022)
- [FedMix: Approximation of Mixup under Mean Augmented Federated Learning](https://mlsanity.com/paper/2107.00233/) (2021)
- [Distributionally Robust Federated Averaging](https://mlsanity.com/paper/2102.12660/) (2021)
- [Stochastic Controlled Averaging for Federated Learning with Communication Compression](https://mlsanity.com/paper/2308.08165/) (2023)
- [Federated Learning for Generalization, Robustness, Fairness: A Survey and Benchmark](https://mlsanity.com/paper/2311.06750/) (2023)
- [Edge Artificial Intelligence for 6G: Vision, Enabling Technologies, and Applications](https://mlsanity.com/paper/2111.12444/) (2021)
- [Clustered Sampling: Low-Variance and Improved Representativity for Clients Selection in Federated Learning](https://mlsanity.com/paper/2105.05883/) (2021)
- [Trustworthy AI: A Computational Perspective](https://mlsanity.com/paper/2107.06641/) (2021)
- [Federated Fine-tuning of Large Language Models under Heterogeneous Tasks and Client Resources](https://mlsanity.com/paper/2402.11505/) (2024)

## Abstract (arXiv)

Federated learning enables a large amount of edge computing devices to jointly learn a model without data sharing. As a leading algorithm in this setting, Federated Averaging (textttFedAvg) runs Stochastic Gradient Descent (SGD) in parallel on a small subset of the total devices and averages the sequences only once in a while. Despite its simplicity, it lacks theoretical guarantees under realistic settings. In this paper, we analyze the convergence of textttFedAvg on non-iid data and establish a convergence rate of O(frac1T) for strongly convex and smooth problems, where T is the number of SGDs. Importantly, our bound demonstrates a trade-off between communication-efficiency and convergence rate. As user devices may be disconnected from the server, we relax the assumption of full device participation to partial device participation and study different averaging schemes; low device participation rate can be achieved without severely slowing down the learning. Our results indicate that heterogeneity of data slows down the convergence, which matches empirical observations. Furthermore, we provide a necessary condition for textttFedAvg on non-iid data: the learning rate η must decay, even if full-gradient is used; otherwise, the solution will be Omega (η) away from the optimal.