Client Selection in Federated Learning: Convergence Analysis and Power-of-Choice Selection Strategies

By Yae Jee Cho, Jianyu Wang, Gauri Joshi. arXiv.org, 2020

552 citations recorded by the source corpus.

Federated learning is a distributed optimization paradigm that enables a large number of resource-limited client nodes to cooperatively train a model without data sharing. Several works have analyzed the convergence of federated learning by accounting of data heterogeneity, communication and computation limitations, and partial client participation. However, they assume unbiased client participation, where clients are selected at random or in proportion of their data sizes. In this paper, we present the first convergence analysis of federated optimization for biased client selection strategies, and quantify how the selection bias affects convergence speed. We reveal that biasing client selection towards clients with higher local loss achieves faster error convergence. Using this insight, we propose Power-of-Choice, a communication- and computation-efficient client selection framework that can flexibly span the trade-off between convergence speed and solution bias. Our experiments demonstrate that Power-of-Choice strategies converge up to 3 $\times$ faster and give $10$% higher test accuracy than the baseline random selection.

Subfields: Artificial Intelligence

View Paper: https://www.semanticscholar.org/paper/e245f15bdddac514454fecf32f2a3ecb069f6dec

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

1. Bo Du
2. Mang Ye
3. Zachary B. Charles
4. Pong Chi Yuen
5. Dacheng Tao
6. Zhouyuan Huo
7. Xiuwen Fang
8. Zachary Garrett

Citations in the corpus

• Federated Learning in Edge Computing: A Systematic Survey (2022, background): “The authors of [208] described the convergence analysis of federated optimization for biased client selection strategies and quantified how selection bias affects the convergence speed.”
• On Large-Cohort Training for Federated Learning (2021, background): “…McMahan et al., 2017; Basu et al., 2019; Laguel et al., 2021), data and systems heterogeneity (Li et al., 2020a, 2019; Karimireddy et al., 2020b; Hsu et al., 2019; Karimireddy et al., 2020a; Li et al., 2020b; Wang et al., 2020; Li and Wang, 2019), and fairness (Li et al., 2020c; Hu et al., 2020).”
• Heterogeneous Federated Learning: State-of-the-art and Research Challenges (2023, background): “Thus, a large number of client selection strategies [1, 14, 32, 83, 235] aim to address these issues.”