Multi-Armed Bandit Based Client Scheduling for Federated Learning

Abstract

By exploiting the computing power and local data of distributed clients, federated learning (FL) features ubiquitous properties such as reduction of communication overhead and preserving data privacy. In each communication round of FL, the clients update local models based on their own data and upload their local updates via wireless channels. However, latency caused by hundreds to thousands of communication rounds remains a bottleneck in FL. To minimize the training latency, this work provides a multi-armed bandit-based framework for online client scheduling (CS) in FL without knowing wireless channel state information and statistical characteristics of clients. Firstly, we propose a CS algorithm based on the upper confidence bound policy (CS-UCB) for ideal scenarios where local datasets of clients are independent and identically distributed (i.i.d.) and balanced. An upper bound of the expected performance regret of the proposed CS-UCB algorithm is provided, which indicates that the regret grows logarithmically over communication rounds. Then, to address non-ideal scenarios with non-i.i.d. and unbalanced properties of local datasets and varying availability of clients, we further propose a CS algorithm based on the UCB policy and virtual queue technique (CS-UCB-Q). An upper bound is also derived, which shows that the expected performance regret of the proposed CS-UCB-Q algorithm can have a sub-linear growth over communication rounds under certain conditions. Besides, the convergence performance of FL training is also analyzed. Finally, simulation results validate the efficiency of the proposed algorithms.

References in corpus (17)

• Communication-Efficient Learning of Deep Networks from Decentralized Data
• Client Selection for Federated Learning with Heterogeneous Resources in Mobile Edge
• Deep Gradient Compression: Reducing the Communication Bandwidth for Distributed Training
• On the Convergence of FedAvg on Non-IID Data
• Towards Federated Learning at Scale: System Design
• Revisiting Distributed Synchronous SGD
• Machine Learning at the Wireless Edge: Distributed Stochastic Gradient Descent Over-the-Air
• Sparse Communication for Distributed Gradient Descent
• Distributed Learning in Multi-Armed Bandit with Multiple Players
• Local SGD Converges Fast and Communicates Little
• On the Convergence of Local Descent Methods in Federated Learning
• High-Dimensional Stochastic Gradient Quantization for Communication-Efficient Edge Learning
• A Joint Learning and Communications Framework for Federated Learning over Wireless Networks
• Zeno: Distributed Stochastic Gradient Descent with Suspicion-based Fault-tolerance
• Federated Learning via Over-the-Air Computation
• Energy-Efficient Radio Resource Allocation for Federated Edge Learning
• Convergence Time Optimization for Federated Learning over Wireless Networks

Cited by in corpus (19)

• Federated Learning: A Signal Processing Perspective
• Federated Learning Under Intermittent Client Availability and Time-Varying Communication Constraints
• Time-sensitive Learning for Heterogeneous Federated Edge Intelligence
• Multi-Model Federated Learning
• A Contribution-based Device Selection Scheme in Federated Learning
• DYNAMITE: Dynamic Interplay of Mini-Batch Size and Aggregation Frequency for Federated Learning with Static and Streaming Dataset
• Federated Learning for Smart Healthcare: A Survey
• FedGreen: Federated Learning with Fine-Grained Gradient Compression for Green Mobile Edge Computing
• Gradient Sparsification for Efficient Wireless Federated Learning with Differential Privacy
• Distributed Non-Convex Optimization with Sublinear Speedup under Intermittent Client Availability
• Federated learning with class imbalance reduction
• Ed-Fed: A generic federated learning framework with resource-aware client selection for edge devices
• Learning to Transmit with Provable Guarantees in Wireless Federated Learning
• Accurate and Fast Federated Learning via Combinatorial Multi-Armed Bandits
• Low-Latency Federated Learning over Wireless Channels with Differential Privacy
• From Learning to Analytics: Improving Model Efficacy with Goal-Directed Client Selection
• Revolutionizing Wireless Networks with Federated Learning: A Comprehensive Review
• Integrated user scheduling and beam steering in over-the-air federated learning for mobile IoT
• Cost-efficient and Skew-aware Data Scheduling for Incremental Learning in 5G Network