# On the Convergence of Federated Averaging under Partial Participation for Over-parameterized Neural Networks

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 31 of its 43 references that are in the map.
- First posted on arXiv 9 Oct 2023.

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

- [Communication-Efficient Learning of Deep Networks from Decentralized Data](https://mlsanity.com/paper/1602.05629/) (2016)
- [Fashion-MNIST: a Novel Image Dataset for Benchmarking Machine Learning Algorithms](https://mlsanity.com/paper/1708.07747/) (2017)
- [Advances and Open Problems in Federated Learning](https://mlsanity.com/paper/1912.04977/) (2019)
- [Deep Learning with Differential Privacy](https://mlsanity.com/paper/1607.00133/) (2016)
- [Neural Tangent Kernel: Convergence and Generalization in Neural Networks](https://mlsanity.com/paper/1806.07572/) (2018)
- [Understanding deep learning requires rethinking generalization](https://mlsanity.com/paper/1611.03530/) (2016)
- [Federated Learning: Strategies for Improving Communication Efficiency](https://mlsanity.com/paper/1610.05492/) (2016)
- [A Convergence Theory for Deep Learning via Over-Parameterization](https://mlsanity.com/paper/1811.03962/) (2018)
- [Gradient Descent Provably Optimizes Over-parameterized Neural Networks](https://mlsanity.com/paper/1810.02054/) (2018)
- [Federated Learning for Mobile Keyboard Prediction](https://mlsanity.com/paper/1811.03604/) (2018)
- [FedBN: Federated Learning on Non-IID Features via Local Batch Normalization](https://mlsanity.com/paper/2102.07623/) (2021)
- [Fine-Grained Analysis of Optimization and Generalization for Overparameterized Two-Layer Neural Networks](https://mlsanity.com/paper/1901.08584/) (2019)
- [Federated Learning with Matched Averaging](https://mlsanity.com/paper/2002.06440/) (2020)
- [Adaptive Federated Learning in Resource Constrained Edge Computing Systems](https://mlsanity.com/paper/1804.05271/) (2018)
- [Learning Overparameterized Neural Networks via Stochastic Gradient Descent on Structured Data](https://mlsanity.com/paper/1808.01204/) (2018)
- [A Hybrid Approach to Privacy-Preserving Federated Learning](https://mlsanity.com/paper/1812.03224/) (2018)
- [Achieving Linear Speedup with Partial Worker Participation in Non-IID Federated Learning](https://mlsanity.com/paper/2101.11203/) (2021)
- [Qsparse-local-SGD: Distributed SGD with Quantization, Sparsification, and Local Computations](https://mlsanity.com/paper/1906.02367/) (2019)
- [Practical Secure Aggregation for Federated Learning on User-Held Data](https://mlsanity.com/paper/1611.04482/) (2016)
- [Threats to Federated Learning: A Survey](https://mlsanity.com/paper/2003.02133/) (2020)
- [FedVARP: Tackling the Variance Due to Partial Client Participation in Federated Learning](https://mlsanity.com/paper/2207.14130/) (2022)
- [Quadratic Suffices for Over-parametrization via Matrix Chernoff Bound](https://mlsanity.com/paper/1906.03593/) (2019)
- [Width Provably Matters in Optimization for Deep Linear Neural Networks](https://mlsanity.com/paper/1901.08572/) (2019)
- [Privacy-preserving Federated Learning based on Multi-key Homomorphic Encryption](https://mlsanity.com/paper/2104.06824/) (2021)
- [A Modular Analysis of Provable Acceleration via Polyak's Momentum: Training a Wide ReLU Network and a Deep Linear Network](https://mlsanity.com/paper/2010.01618/) (2020)
- [Aggregation Service for Federated Learning: An Efficient, Secure, and More Resilient Realization](https://mlsanity.com/paper/2202.01971/) (2022)
- [Accelerating Hybrid Federated Learning Convergence under Partial Participation](https://mlsanity.com/paper/2304.05397/) (2023)
- ["The Squawk Bot": Joint Learning of Time Series and Text Data Modalities for Automated Financial Information Filtering](https://mlsanity.com/paper/1912.10858/) (2019)
- [A Dynamical View on Optimization Algorithms of Overparameterized Neural Networks](https://mlsanity.com/paper/2010.13165/) (2020)
- [Local SGD Optimizes Overparameterized Neural Networks in Polynomial Time](https://mlsanity.com/paper/2107.10868/) (2021)

## Abstract (arXiv)

Federated learning (FL) is a widely employed distributed paradigm for collaboratively training machine learning models from multiple clients without sharing local data. In practice, FL encounters challenges in dealing with partial client participation due to the limited bandwidth, intermittent connection and strict synchronized delay. Simultaneously, there exist few theoretical convergence guarantees in this practical setting, especially when associated with the non-convex optimization of neural networks. To bridge this gap, we focus on the training problem of federated averaging (FedAvg) method for two canonical models: a deep linear network and a two-layer ReLU network. Under the over-parameterized assumption, we provably show that FedAvg converges to a global minimum at a linear rate Oleft((1-fracmini ∈ [t]|Si|N2)tright) after t iterations, where N is the number of clients and |Si| is the number of the participated clients in the i-th iteration. Experimental evaluations confirm our theoretical results.