mlsanityData to 13 Oct 2026

Adaptive Client Sampling in Federated Learning via Online Learning with Bandit Feedback

arXiv 2112.14332 ↗First posted 28 Dec 2021cs.LGcited by 6

Not on the map. Why?

Abstract (arXiv)

Due to the high cost of communication, federated learning (FL) systems need to sample a subset of clients that are involved in each round of training. As a result, client sampling plays an important role in FL systems as it affects the convergence rate of optimization algorithms used to train machine learning models. Despite its importance, there is limited work on how to sample clients effectively. In this paper, we cast client sampling as an online learning task with bandit feedback, which we solve with an online stochastic mirror descent (OSMD) algorithm designed to minimize the sampling variance. We then theoretically show how our sampling method can improve the convergence speed of federated optimization algorithms over the widely used uniform sampling. Through both simulated and real data experiments, we empirically illustrate the advantages of the proposed client sampling algorithm over uniform sampling and existing online learning-based sampling strategies. The proposed adaptive sampling procedure is applicable beyond the FL problem studied here and can be used to improve the performance of stochastic optimization procedures such as stochastic gradient descent and stochastic coordinate descent.

Key facts. Cited by 6 papers in the map (data through 13 Oct 2026). Builds on 40 of its 60 references that are in the map. First posted on arXiv 28 Dec 2021.

Builds on

40 of 60 references.

References · 40

  1. 2016Communication-Efficient Learning of Deep Networks from Decentralized Datacited by 7,653
  2. 2017Fashion-MNIST: a Novel Image Dataset for Benchmarking Machine Learning Algorithmscited by 4,328
  3. 2019Advances and Open Problems in Federated Learningcited by 3,040
  4. 2016Optimization Methods for Large-Scale Machine Learningcited by 1,142
  5. 2019Introduction to Online Convex Optimizationcited by 798
  6. 2018LEAF: A Benchmark for Federated Settingscited by 789
  7. 2013Stochastic First- and Zeroth-order Methods for Nonconvex Stochastic Programmingcited by 718
  8. 2016TensorFlow: Large-Scale Machine Learning on Heterogeneous Distributed Systemscited by 662
  9. 2019Meta-Learning with Implicit Gradientscited by 523
  10. 2018Deep Learning for Classical Japanese Literaturecited by 418
  11. 2014SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectivescited by 401
  12. 2020Client Selection in Federated Learning: Convergence Analysis and Power-of-Choice Selection Strategiescited by 198
28 more
  1. 2020Mime: Mimicking Centralized Stochastic Algorithms in Federated Learningcited by 154
  2. 2020Survey of Personalization Techniques for Federated Learningcited by 144
  3. 2016Katyusha: The First Direct Acceleration of Stochastic Gradient Methodscited by 134
  4. 2013Stochastic Gradient Descent, Weighted Sampling, and the Randomized Kaczmarz algorithmcited by 133
  5. 2018Adaptive Online Learning in Dynamic Environmentscited by 131
  6. 2020Optimal Client Sampling for Federated Learningcited by 124
  7. 2015Strongly Adaptive Online Learningcited by 103
  8. 2014Stochastic Optimization with Importance Samplingcited by 91
  9. 2016Tracking Slowly Moving Clairvoyant: Optimal Dynamic Regret of Online Learning with True and Noisy Gradientcited by 65
  10. 2020Federated learning with class imbalance reductioncited by 52
  11. 2016MetaGrad: Multiple Learning Rates in Online Learningcited by 46
  12. 2020Communication-Efficient Federated Learning via Optimal Client Samplingcited by 39
  13. 2016Importance Sampling for Minibatchescited by 36
  14. 2020On the Outsized Importance of Learning Rates in Local Update Methodscited by 36
  15. 2021Personalized Federated Learning: A Unified Framework and Universal Optimization Techniquescited by 34
  16. 2020Bandit-based Communication-Efficient Client Selection Strategies for Federated Learningcited by 29
  17. 2015Even Faster Accelerated Coordinate Descent Using Non-Uniform Samplingcited by 23
  18. 2013Accelerated Proximal Stochastic Dual Coordinate Ascent for Regularized Loss Minimizationcited by 19
  19. 2017Safe Adaptive Importance Samplingcited by 19
  20. 2018Online Variance Reduction for Stochastic Optimizationcited by 10
  21. 2021Adaptive Importance Sampling for Finite-Sum Optimization and Sampling with Decreasing Step-Sizescited by 9
  22. 2017Stochastic Optimization with Bandit Samplingcited by 8
  23. 2020Variance Reduced Coordinate Descent with Acceleration: New Method With a Surprising Application to Finite-Sum Problemscited by 8
  24. 2019Online Variance Reduction with Mixturescited by 7
  25. 2020Accurate and Fast Federated Learning via Combinatorial Multi-Armed Banditscited by 7
  26. 2017Faster Coordinate Descent via Adaptive Importance Samplingcited by 5
  27. 2017Coordinate Descent with Bandit Samplingcited by 5
  28. 2018ASVRG: Accelerated Proximal SVRGcited by 3

Built on by

Cited by year

Citing papers per year: 2022: 2; 2023: 2; 2024: 0; 2025: 2.

6 papers.

  1. 2022DELTA: Diverse Client Sampling for Fasting Federated Learningcited by 24
  2. 2023Addressing Budget Allocation and Revenue Allocation in Data Market Environments Using an Adaptive Sampling Algorithmcited by 5
  3. 2022L-SVRG and L-Katyusha with Adaptive Samplingcited by 1
  4. 2023Enhanced Federated Optimization: Adaptive Unbiased Client Sampling with Reduced Variancecited by 1
  5. 2025FedAvgen: Metadata for Model Aggregation In Communication Systemscited by 0
  6. 2025Overcoming Challenges of Partial Client Participation in Federated Learning : A Comprehensive Reviewcited by 0