# Tackling System and Statistical Heterogeneity for Federated Learning with Adaptive Client Sampling

arXiv: https://arxiv.org/abs/2112.11256 · HTML: https://mlsanity.com/paper/2112.11256/

## Key facts

- Cited by 66 papers in the map (data through 14 Oct 2026).
- Builds on 37 of its 47 references that are in the map.
- First posted on arXiv 21 Dec 2021.

## Builds on (most cited first, 30 of 37)

- [Communication-Efficient Learning of Deep Networks from Decentralized Data](https://mlsanity.com/paper/1602.05629/) (2016)
- [Advances and Open Problems in Federated Learning](https://mlsanity.com/paper/1912.04977/) (2019)
- [Federated Optimization in Heterogeneous Networks](https://mlsanity.com/paper/1812.06127/) (2018)
- [Convex optimization](https://mlsanity.com/paper/2106.01946/) (2021)
- [Federated Learning: Challenges, Methods, and Future Directions](https://mlsanity.com/paper/1908.07873/) (2019)
- [Federated Learning: Strategies for Improving Communication Efficiency](https://mlsanity.com/paper/1610.05492/) (2016)
- [On the Convergence of FedAvg on Non-IID Data](https://mlsanity.com/paper/1907.02189/) (2019)
- [Towards Federated Learning at Scale: System Design](https://mlsanity.com/paper/1902.01046/) (2019)
- [Local SGD Converges Fast and Communicates Little](https://mlsanity.com/paper/1805.09767/) (2018)
- [Federated Machine Learning: Concept and Applications](https://mlsanity.com/paper/1902.04885/) (2019)
- [Adaptive Federated Learning in Resource Constrained Edge Computing Systems](https://mlsanity.com/paper/1804.05271/) (2018)
- [Client Selection for Federated Learning with Heterogeneous Resources in Mobile Edge](https://mlsanity.com/paper/1804.08333/) (2018)
- [Parallel Restarted SGD with Faster Convergence and Less Communication: Demystifying Why Model Averaging Works for Deep Learning](https://mlsanity.com/paper/1807.06629/) (2018)
- [Client Selection in Federated Learning: Convergence Analysis and Power-of-Choice Selection Strategies](https://mlsanity.com/paper/2010.01243/) (2020)
- [Achieving Linear Speedup with Partial Worker Participation in Non-IID Federated Learning](https://mlsanity.com/paper/2101.11203/) (2021)
- [On the Linear Speedup Analysis of Communication Efficient Momentum SGD for Distributed Non-Convex Optimization](https://mlsanity.com/paper/1905.03817/) (2019)
- [Practical Secure Aggregation for Federated Learning on User-Held Data](https://mlsanity.com/paper/1611.04482/) (2016)
- [SCAFFOLD: Stochastic Controlled Averaging for Federated Learning](https://mlsanity.com/paper/1910.06378/) (2019)
- [On the Convergence of Local Descent Methods in Federated Learning](https://mlsanity.com/paper/1910.14425/) (2019)
- [Stochastic Gradient Descent, Weighted Sampling, and the Randomized Kaczmarz algorithm](https://mlsanity.com/paper/1310.5715/) (2013)
- [Scheduling Policies for Federated Learning in Wireless Networks](https://mlsanity.com/paper/1908.06287/) (2019)
- [Optimal Client Sampling for Federated Learning](https://mlsanity.com/paper/2010.13723/) (2020)
- [TiFL: A Tier-based Federated Learning System](https://mlsanity.com/paper/2001.09249/) (2020)
- [Stochastic Optimization with Importance Sampling](https://mlsanity.com/paper/1401.2753/) (2014)
- [Joint Device Scheduling and Resource Allocation for Latency Constrained Wireless Federated Learning](https://mlsanity.com/paper/2007.07174/) (2020)
- [Convergence Time Optimization for Federated Learning over Wireless Networks](https://mlsanity.com/paper/2001.07845/) (2020)
- [Variance Reduction in SGD by Distributed Importance Sampling](https://mlsanity.com/paper/1511.06481/) (2015)
- [Adaptive Communication Strategies to Achieve the Best Error-Runtime Trade-off in Local-Update SGD](https://mlsanity.com/paper/1810.08313/) (2018)
- [Cost-Effective Federated Learning Design](https://mlsanity.com/paper/2012.08336/) (2020)
- [Fast-Convergent Federated Learning](https://mlsanity.com/paper/2007.13137/) (2020)

## Built on by (most cited first, 30 of 66)

- [Client Selection in Federated Learning: Principles, Challenges, and Opportunities](https://mlsanity.com/paper/2211.01549/) (2022)
- [Federated Continual Learning via Knowledge Fusion: A Survey](https://mlsanity.com/paper/2312.16475/) (2023)
- [DELTA: Diverse Client Sampling for Fasting Federated Learning](https://mlsanity.com/paper/2205.13925/) (2022)
- [Over-The-Air Federated Learning: Status Quo, Open Challenges, and Future Directions](https://mlsanity.com/paper/2307.00974/) (2023)
- [Scheduling and Aggregation Design for Asynchronous Federated Learning over Wireless Networks](https://mlsanity.com/paper/2212.07356/) (2022)
- [Ten Challenging Problems in Federated Foundation Models](https://mlsanity.com/paper/2502.12176/) (2025)
- [GradSkip: Communication-Accelerated Local Gradient Methods with Better Computational Complexity](https://mlsanity.com/paper/2210.16402/) (2022)
- [Data and Model Poisoning Backdoor Attacks on Wireless Federated Learning, and the Defense Mechanisms: A Comprehensive Survey](https://mlsanity.com/paper/2312.08667/) (2023)
- [Federated Learning with Regularized Client Participation](https://mlsanity.com/paper/2302.03662/) (2023)
- [DYNAMITE: Dynamic Interplay of Mini-Batch Size and Aggregation Frequency for Federated Learning with Static and Streaming Dataset](https://mlsanity.com/paper/2310.14906/) (2023)
- [MergeSFL: Split Federated Learning with Feature Merging and Batch Size Regulation](https://mlsanity.com/paper/2311.13348/) (2023)
- [Federated Learning with Flexible Control](https://mlsanity.com/paper/2212.08496/) (2022)
- [Green Federated Learning: A new era of Green Aware AI](https://mlsanity.com/paper/2409.12626/) (2024)
- [A Survey on Participant Selection for Federated Learning in Mobile Networks](https://mlsanity.com/paper/2207.03681/) (2022)
- [Communication-Efficient Multimodal Federated Learning: Joint Modality and Client Selection](https://mlsanity.com/paper/2401.16685/) (2024)
- [Federated Learning Across Decentralized and Unshared Archives for Remote Sensing Image Classification](https://mlsanity.com/paper/2311.06141/) (2023)
- [Adaptive Heterogeneous Client Sampling for Federated Learning over Wireless Networks](https://mlsanity.com/paper/2404.13804/) (2024)
- [Knowledge Distillation in Federated Learning: a Survey on Long Lasting Challenges and New Solutions](https://mlsanity.com/paper/2406.10861/) (2024)
- [Incentive Mechanism Design for Unbiased Federated Learning with Randomized Client Participation](https://mlsanity.com/paper/2304.07981/) (2023)
- [GlueFL: Reconciling Client Sampling and Model Masking for Bandwidth Efficient Federated Learning](https://mlsanity.com/paper/2212.01523/) (2022)
- [Optimization Design for Federated Learning in Heterogeneous 6G Networks](https://mlsanity.com/paper/2303.08322/) (2023)
- [Flow: Per-Instance Personalized Federated Learning Through Dynamic Routing](https://mlsanity.com/paper/2211.15281/) (2022)
- [Neural Characteristic Activation Analysis and Geometric Parameterization for ReLU Networks](https://mlsanity.com/paper/2305.15912/) (2023)
- [Adaptive Parameter-Efficient Federated Fine-Tuning on Heterogeneous Devices](https://mlsanity.com/paper/2412.20004/) (2024)
- [FedGPS: Statistical Rectification Against Data Heterogeneity in Federated Learning](https://mlsanity.com/paper/2510.20250/) (2025)
- [Adaptive Control of Client Selection and Gradient Compression for Efficient Federated Learning](https://mlsanity.com/paper/2212.09483/) (2022)
- [Stabilizing and Improving Federated Learning with Non-IID Data and Client Dropout](https://mlsanity.com/paper/2303.06314/) (2023)
- [FedAST: Federated Asynchronous Simultaneous Training](https://mlsanity.com/paper/2406.00302/) (2024)
- [Review of Mathematical Optimization in Federated Learning](https://mlsanity.com/paper/2412.01630/) (2024)
- [Collaborative Mean Estimation over Intermittently Connected Networks with Peer-To-Peer Privacy](https://mlsanity.com/paper/2303.00035/) (2023)

## Abstract (arXiv)

Federated learning (FL) algorithms usually sample a fraction of clients in each round (partial participation) when the number of participants is large and the server's communication bandwidth is limited. Recent works on the convergence analysis of FL have focused on unbiased client sampling, e.g., sampling uniformly at random, which suffers from slow wall-clock time for convergence due to high degrees of system heterogeneity and statistical heterogeneity. This paper aims to design an adaptive client sampling algorithm that tackles both system and statistical heterogeneity to minimize the wall-clock convergence time. We obtain a new tractable convergence bound for FL algorithms with arbitrary client sampling probabilities. Based on the bound, we analytically establish the relationship between the total learning time and sampling probabilities, which results in a non-convex optimization problem for training time minimization. We design an efficient algorithm for learning the unknown parameters in the convergence bound and develop a low-complexity algorithm to approximately solve the non-convex problem. Experimental results from both hardware prototype and simulation demonstrate that our proposed sampling scheme significantly reduces the convergence time compared to several baseline sampling schemes. Notably, our scheme in hardware prototype spends 73% less time than the uniform sampling baseline for reaching the same target loss.