Communication-Efficient Device Scheduling for Federated Learning Using Lyapunov Optimization
Not on the map. Why?
Abstract (arXiv)
Federated learning (FL) is a useful tool that enables the training of machine learning models over distributed data without having to collect data centrally. When deploying FL in constrained wireless environments, however, intermittent connectivity of devices, heterogeneous connection quality, and non-i.i.d. data can severely slow convergence. In this paper, we consider FL with arbitrary device participation probabilities for each round and show that by weighing each device's update by the reciprocal of their per-round participation probability, we can guarantee convergence to a stationary point. Our bound applies to non-convex loss functions and non-i.i.d. datasets and recovers state-of-the-art convergence rates for both full and uniform partial participation, including linear speedup, with only a single-sided learning rate. Then, using the derived convergence bound, we develop a new online client selection and power allocation algorithm that utilizes the Lyapunov drift-plus-penalty framework to opportunistically minimize a function of the convergence bound and the average communication time under a transmit power constraint. We use optimization over manifold techniques to obtain a solution to the minimization problem. Thanks to the Lyapunov framework, one key feature of the algorithm is that knowledge of the channel distribution is not required and only the instantaneous channel state information needs to be known. Using the CIFAR-10 dataset with varying levels of data heterogeneity, we show through simulations that the communication time can be significantly decreased using our algorithm compared to uniformly random participation, especially for heterogeneous channel conditions.
Key facts. Cited by 1 paper in the map (data through 7 Oct 2026). Builds on 36 of its 51 references that are in the map. First posted on arXiv 1 Mar 2025.
Builds on
36 of 51 references.
References · 36
- 2016Communication-Efficient Learning of Deep Networks from Decentralized Datacited by 7,592
- 2018Federated Optimization in Heterogeneous Networkscited by 2,971
- 2016Federated Learning: Strategies for Improving Communication Efficiencycited by 1,461
- 2016On Large-Batch Training for Deep Learning: Generalization Gap and Sharp Minimacited by 1,337
- 2019On the Convergence of FedAvg on Non-IID Datacited by 1,220
- 2020Adaptive Federated Optimizationcited by 1,036
- 2019Measuring the Effects of Non-Identical Data Distribution for Federated Visual Classificationcited by 836
- 2017Can Decentralized Algorithms Outperform Centralized Algorithms? A Case Study for Decentralized Parallel Stochastic Gradient Descentcited by 496
- 2017Differentially Private Federated Learning: A Client Level Perspectivecited by 451
- 2019Robust and Communication-Efficient Federated Learning from Non-IID Datacited by 415
- 2018Adaptive Federated Learning in Resource Constrained Edge Computing Systemscited by 408
- 2019FedPAQ: A Communication-Efficient Federated Learning Method with Periodic Averaging and Quantizationcited by 349
24 more
- 2018Client Selection for Federated Learning with Heterogeneous Resources in Mobile Edgecited by 347
- 2018Parallel Restarted SGD with Faster Convergence and Less Communication: Demystifying Why Model Averaging Works for Deep Learningcited by 277
- 2019A Joint Learning and Communications Framework for Federated Learning over Wireless Networkscited by 262
- 2018A Hybrid Approach to Privacy-Preserving Federated Learningcited by 208
- 2021Achieving Linear Speedup with Partial Worker Participation in Non-IID Federated Learningcited by 192
- 2019Energy Efficient Federated Learning Over Wireless Communication Networkscited by 181
- 2019Scheduling Policies for Federated Learning in Wireless Networkscited by 131
- 2021Linear Convergence in Federated Learning: Tackling Client Heterogeneity and Sparse Gradientscited by 122
- 2013Manopt, a Matlab toolbox for optimization on manifoldscited by 112
- 2021Clustered Sampling: Low-Variance and Improved Representativity for Clients Selection in Federated Learningcited by 93
- 2020Joint Device Scheduling and Resource Allocation for Latency Constrained Wireless Federated Learningcited by 90
- 2020Adaptive Gradient Sparsification for Efficient Federated Learning: An Online Learning Approachcited by 80
- 2021Fast Federated Learning in the Presence of Arbitrary Device Unavailabilitycited by 72
- 2020Towards Flexible Device Participation in Federated Learningcited by 64
- 2019Active Federated Learningcited by 63
- 2020Scheduling for Cellular Federated Edge Learning with Importance and Channel Awarenesscited by 62
- 2020An Efficiency-boosting Client Selection Scheme for Federated Learning with Fairness Guaranteecited by 61
- 2022A Unified Analysis of Federated Learning with Arbitrary Client Participationcited by 45
- 2020Communication-Efficient Federated Learning via Optimal Client Samplingcited by 39
- 2020Optimal Gradient Compression for Distributed and Federated Learningcited by 37
- 2022Communication-Efficient Device Scheduling for Federated Learning Using Stochastic Optimizationcited by 28
- 2020Federated Learning under Channel Uncertainty: Joint Client Scheduling and Resource Allocationcited by 18
- 2021Optimal Rate Adaption in Federated Learning with Compressed Communicationscited by 15
- 2022Federated Learning with Flexible Controlcited by 12
Built on by
Citing papers per year: 2026: 1.
1 paper.