Debiasing Federated Learning with Correlated Client Participation
Not on the map. Why?
Abstract (arXiv)
In cross-device federated learning (FL) with millions of mobile clients, only a small subset of clients participate in training in every communication round, and Federated Averaging (FedAvg) is the most popular algorithm in practice. Existing analyses of FedAvg usually assume the participating clients are independently sampled in each round from a uniform distribution, which does not reflect real-world scenarios. This paper introduces a theoretical framework that models client participation in FL as a Markov chain to study optimization convergence when clients have non-uniform and correlated participation across rounds. We apply this framework to analyze a more general and practical pattern: every client must wait a minimum number of R rounds (minimum separation) before re-participating. We theoretically prove and empirically observe that increasing minimum separation reduces the bias induced by intrinsic non-uniformity of client availability in cross-device FL systems. Furthermore, we develop an effective debiasing algorithm for FedAvg that provably converges to the unbiased optimal solution under arbitrary minimum separation and unknown client availability distribution.
Key facts. Cited by 1 paper in the map (data through 7 Oct 2026). Builds on 35 of its 51 references that are in the map. First posted on arXiv 2 Oct 2024.
Builds on
35 of 51 references.
References · 35
- 2016Communication-Efficient Learning of Deep Networks from Decentralized Datacited by 7,592
- 2019Advances and Open Problems in Federated Learningcited by 3,021
- 2019Federated Learning: Challenges, Methods, and Future Directionscited by 1,531
- 2019On the Convergence of FedAvg on Non-IID Datacited by 1,220
- 2020Tackling the Objective Inconsistency Problem in Heterogeneous Federated Optimizationcited by 897
- 2019Towards Federated Learning at Scale: System Designcited by 826
- 2018Federated Learning for Mobile Keyboard Predictioncited by 565
- 2014SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectivescited by 401
- 2021A Field Guide to Federated Optimizationcited by 312
- 2020Client Selection in Federated Learning: Convergence Analysis and Power-of-Choice Selection Strategiescited by 196
- 2021Achieving Linear Speedup with Partial Worker Participation in Non-IID Federated Learningcited by 192
- 2019SCAFFOLD: Stochastic Controlled Averaging for Federated Learningcited by 174
23 more
- 2021Practical and Private (Deep) Learning without Sampling or Shufflingcited by 169
- 2020Minibatch vs Local SGD for Heterogeneous Distributed Learningcited by 147
- 2016Katyusha: The First Direct Acceleration of Stochastic Gradient Methodscited by 134
- 2020Optimal Client Sampling for Federated Learningcited by 123
- 2021Clustered Sampling: Low-Variance and Improved Representativity for Clients Selection in Federated Learningcited by 93
- 2021Papaya: Practical, Private, and Scalable Federated Learningcited by 89
- 2021Federated Evaluation and Tuning for On-Device Personalization: System Design & Applicationscited by 84
- 2016Variance Reduction for Faster Non-Convex Optimizationcited by 72
- 2023Federated Learning of Gboard Language Models with Differential Privacycited by 64
- 2022FedVARP: Tackling the Variance Due to Partial Client Participation in Federated Learningcited by 62
- 2023(Amplified) Banded Matrix Factorization: A unified approach to private trainingcited by 49
- 2022A Unified Analysis of Federated Learning with Arbitrary Client Participationcited by 45
- 2019Semi-Cyclic Stochastic Gradient Descentcited by 40
- 2023Stochastic Gradient Descent under Markovian Sampling Schemescited by 37
- 2022On the Unreasonable Effectiveness of Federated Averaging with Heterogeneous Datacited by 36
- 2023On the Convergence of Federated Averaging with Cyclic Client Participationcited by 31
- 2022Federated Learning Under Intermittent Client Availability and Time-Varying Communication Constraintscited by 30
- 2023Federated Learning under Heterogeneous and Correlated Client Availabilitycited by 18
- 2023Accelerating Hybrid Federated Learning Convergence under Partial Participationcited by 15
- 2023First Order Methods with Markovian Noise: from Acceleration to Variational Inequalitiescited by 14
- 2022A Communication-efficient Algorithm with Linear Convergence for Federated Minimax Learningcited by 9
- 2024A Hassle-free Algorithm for Private Learning in Practice: Don't Use Tree Aggregation, Use BLTscited by 9
- 2024Efficient Federated Learning against Heterogeneous and Non-stationary Client Unavailabilitycited by 9
Built on by
Citing papers per year: 2026: 1.
1 paper.