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

Abstract

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.

References in corpus (6)

• Towards Federated Learning at Scale: System Design
• Tackling the Objective Inconsistency Problem in Heterogeneous Federated Optimization
• On the Convergence of Local Descent Methods in Federated Learning
• FedSplit: An algorithmic framework for fast federated optimization
• Accelerating Deep Learning by Focusing on the Biggest Losers
• Faster On-Device Training Using New Federated Momentum Algorithm

Cited by in corpus (19)

• A Field Guide to Federated Optimization
• Towards Fairness-Aware Federated Learning
• A Decentralized Federated Learning Framework via Committee Mechanism with Convergence Guarantee
• The Internet of Federated Things (IoFT): A Vision for the Future and In-depth Survey of Data-driven Approaches for Federated Learning
• Communication Efficiency in Federated Learning: Achievements and Challenges
• Oort: Efficient Federated Learning via Guided Participant Selection
• Local Adaptivity in Federated Learning: Convergence and Consistency
• Heterogeneity for the Win: One-Shot Federated Clustering
• Securing Secure Aggregation: Mitigating Multi-Round Privacy Leakage in Federated Learning
• Personalized Federated Learning for Heterogeneous Clients with Clustered Knowledge Transfer
• Sustainable Federated Learning
• FedFm: Towards a Robust Federated Learning Approach For Fault Mitigation at the Edge Nodes
• Is Shapley Value fair? Improving Client Selection for Mavericks in Federated Learning
• Accurate and Fast Federated Learning via Combinatorial Multi-Armed Bandits
• Dubhe: Towards Data Unbiasedness with Homomorphic Encryption in Federated Learning Client Selection
• On Large-Cohort Training for Federated Learning
• Federated Submodel Optimization for Hot and Cold Data Features
• FedProf: Selective Federated Learning with Representation Profiling
• Management of Resource at the Network Edge for Federated Learning