Convergence of Agnostic Federated Averaging
Not on the map. Why?
Abstract (arXiv)
Federated learning (FL) enables decentralized model training without centralizing raw data. However, practical FL deployments often face a key realistic challenge: Clients participate intermittently in server aggregation and with unknown, possibly biased participation probabilities. Most existing convergence results either assume full-device participation, or rely on knowledge of (in fact uniform) client availability distributions -- assumptions that rarely hold in practice. In this work, we characterize the optimization problem that consistently adheres to the stochastic dynamics of the well-known agnostic Federated Averaging (FedAvg) algorithm under random (and variably-sized) client availability, and rigorously establish its convergence for convex, possibly nonsmooth losses, achieving a standard rate of order O(1/√T), where T denotes the aggregation horizon. Our analysis provides the first convergence guarantees for agnostic FedAvg under general, non-uniform, stochastic client participation, without knowledge of the participation distribution. We also empirically demonstrate that agnostic FedAvg in fact outperforms common (and suboptimal) weighted aggregation FedAvg variants, even with server-side knowledge of participation weights.
Key facts. Cited by 2 papers in the map (data through 14 Oct 2026). Builds on 25 of its 27 references that are in the map. First posted on arXiv 14 Jul 2025.
Builds on
25 of 27 references.
References · 25
- 2016Communication-Efficient Learning of Deep Networks from Decentralized Datacited by 7,669
- 2019Advances and Open Problems in Federated Learningcited by 3,046
- 2018Federated Optimization in Heterogeneous Networkscited by 2,987
- 2016Federated Learning: Strategies for Improving Communication Efficiencycited by 1,475
- 2019On the Convergence of FedAvg on Non-IID Datacited by 1,229
- 2020Adaptive Federated Optimizationcited by 1,046
- 2019Towards Federated Learning at Scale: System Designcited by 832
- 2018Federated Learning for Mobile Keyboard Predictioncited by 572
- 2019Federated Learning with Differential Privacy: Algorithms and Performance Analysiscited by 536
- 2018Exploiting Unintended Feature Leakage in Collaborative Learningcited by 520
- 2017Differentially Private Federated Learning: A Client Level Perspectivecited by 459
- 2019FedPAQ: A Communication-Efficient Federated Learning Method with Periodic Averaging and Quantizationcited by 356
13 more
- 2018Client Selection for Federated Learning with Heterogeneous Resources in Mobile Edgecited by 352
- 2021Federated Learning on Non-IID Data: A Surveycited by 346
- 2021A Field Guide to Federated Optimizationcited by 315
- 2020Client Selection in Federated Learning: Convergence Analysis and Power-of-Choice Selection Strategiescited by 198
- 2020Federated Learning with Compression: Unified Analysis and Sharp Guaranteescited by 160
- 2013Communication Efficient Distributed Optimization using an Approximate Newton-type Methodcited by 132
- 2020Optimal Client Sampling for Federated Learningcited by 124
- 2016AIDE: Fast and Communication Efficient Distributed Optimizationcited by 43
- 2019Semi-Cyclic Stochastic Gradient Descentcited by 40
- 2020Device Heterogeneity in Federated Learning: A Superquantile Approachcited by 21
- 2023Federated TD Learning over Finite-Rate Erasure Channels: Linear Speedup under Markovian Samplingcited by 15
- 2022On the Generalization of Wasserstein Robust Federated Learningcited by 9
- 2023Federated Learning Under Restricted User Availabilitycited by 4
Built on by
Citing papers per year: 2025: 1; 2026: 1.
2 papers.