# A Non-parametric View of FedAvg and FedProx: Beyond Stationary Points

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

## Key facts

- Cited by 13 papers in the map (data through 14 Oct 2026).
- Builds on 21 of its 44 references that are in the map.
- First posted on arXiv 29 Jun 2021.

## Builds on (most cited first, 21 of 21)

- [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: Strategies for Improving Communication Efficiency](https://mlsanity.com/paper/1610.05492/) (2016)
- [On the Convergence of FedAvg on Non-IID Data](https://mlsanity.com/paper/1907.02189/) (2019)
- [Federated Learning with Non-IID Data](https://mlsanity.com/paper/1806.00582/) (2018)
- [Gradient Descent Provably Optimizes Over-parameterized Neural Networks](https://mlsanity.com/paper/1810.02054/) (2018)
- [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)
- [Gradient Descent Finds Global Minima of Deep Neural Networks](https://mlsanity.com/paper/1811.03804/) (2018)
- [Federated Optimization: Distributed Machine Learning for On-Device Intelligence](https://mlsanity.com/paper/1610.02527/) (2016)
- [Adaptive Personalized Federated Learning](https://mlsanity.com/paper/2003.13461/) (2020)
- [Improving Federated Learning Personalization via Model Agnostic Meta Learning](https://mlsanity.com/paper/1909.12488/) (2019)
- [Federated Meta-Learning with Fast Convergence and Efficient Communication](https://mlsanity.com/paper/1802.07876/) (2018)
- [Linear Convergence in Federated Learning: Tackling Client Heterogeneity and Sparse Gradients](https://mlsanity.com/paper/2102.07053/) (2021)
- [FedSplit: An algorithmic framework for fast federated optimization](https://mlsanity.com/paper/2005.05238/) (2020)
- [Early stopping and non-parametric regression: An optimal data-dependent stopping rule](https://mlsanity.com/paper/1306.3574/) (2013)
- [Local SGD: Unified Theory and New Efficient Methods](https://mlsanity.com/paper/2011.02828/) (2020)
- [Convergence and Accuracy Trade-Offs in Federated Learning and Meta-Learning](https://mlsanity.com/paper/2103.05032/) (2021)
- [On the Outsized Importance of Learning Rates in Local Update Methods](https://mlsanity.com/paper/2007.00878/) (2020)
- [Exact minimax risk for linear least squares, and the lower tail of sample covariance matrices](https://mlsanity.com/paper/1912.10754/) (2019)

## Built on by (most cited first, 13 of 13)

- [Global Convergence of Federated Learning for Mixed Regression](https://mlsanity.com/paper/2206.07279/) (2022)
- [FedNS: A Fast Sketching Newton-Type Algorithm for Federated Learning](https://mlsanity.com/paper/2401.02734/) (2024)
- [On the Convergence Rates of Federated Q-Learning across Heterogeneous Environments](https://mlsanity.com/paper/2409.03897/) (2024)
- [Training Memory in Deep Neural Networks: Mechanisms, Evidence, and Measurement Gaps](https://mlsanity.com/paper/2601.21624/) (2026)
- [A Kernel Perspective on Distillation-based Collaborative Learning](https://mlsanity.com/paper/2410.17592/) (2024)
- [FedP3E: Privacy-Preserving Prototype Exchange for Non-IID IoT Malware Detection in Cross-Silo Federated Learning](https://mlsanity.com/paper/2507.07258/) (2025)
- [Decision-Focused Federated Learning Under Heterogeneous Objectives and Constraints](https://mlsanity.com/paper/2604.20031/) (2026)
- [FedSLoP: Memory-Efficient Federated Learning with Low-Rank Gradient Projection](https://mlsanity.com/paper/2604.24012/) (2026)
- [Enhancing IoT Security Against DDoS Attacks through Federated Learning](https://mlsanity.com/paper/2403.10968/) (2024)
- [FLeNS: Federated Learning with Enhanced Nesterov-Newton Sketch](https://mlsanity.com/paper/2409.15216/) (2024)
- [FedVSR: Towards Model-Agnostic Federated Learning in Video Super-Resolution](https://mlsanity.com/paper/2503.13745/) (2025)
- [Traversal Learning: A Lossless And Efficient Distributed Learning Framework](https://mlsanity.com/paper/2504.07471/) (2025)
- [A Robust Clustered Federated Learning Approach for Non-IID Data with Quantity Skew](https://mlsanity.com/paper/2510.03380/) (2025)

## Abstract (arXiv)

Federated Learning (FL) is a promising decentralized learning framework and has great potentials in privacy preservation and in lowering the computation load at the cloud. Recent work showed that FedAvg and FedProx - the two widely-adopted FL algorithms - fail to reach the stationary points of the global optimization objective even for homogeneous linear regression problems. Further, it is concerned that the common model learned might not generalize well locally at all in the presence of heterogeneity. In this paper, we analyze the convergence and statistical efficiency of FedAvg and FedProx, addressing the above two concerns. Our analysis is based on the standard non-parametric regression in a reproducing kernel Hilbert space (RKHS), and allows for heterogeneous local data distributions and unbalanced local datasets. We prove that the estimation errors, measured in either the empirical norm or the RKHS norm, decay with a rate of 1/t in general and exponentially for finite-rank kernels. In certain heterogeneous settings, these upper bounds also imply that both FedAvg and FedProx achieve the optimal error rate. To further analytically quantify the impact of the heterogeneity at each client, we propose and characterize a novel notion-federation gain, defined as the reduction of the estimation error for a client to join the FL. We discover that when the data heterogeneity is moderate, a client with limited local data can benefit from a common model with a large federation gain. Numerical experiments further corroborate our theoretical findings.