# Clustered Sampling: Low-Variance and Improved Representativity for Clients Selection in Federated Learning

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

## Key facts

- Cited by 93 papers in the map (data through 14 Oct 2026).
- Builds on 16 of its 23 references that are in the map.
- First posted on arXiv 12 May 2021.

## Builds on (most cited first, 16 of 16)

- [Communication-Efficient Learning of Deep Networks from Decentralized Data](https://mlsanity.com/paper/1602.05629/) (2016)
- [Federated Optimization in Heterogeneous Networks](https://mlsanity.com/paper/1812.06127/) (2018)
- [On the Convergence of FedAvg on Non-IID Data](https://mlsanity.com/paper/1907.02189/) (2019)
- [Optimization Methods for Large-Scale Machine Learning](https://mlsanity.com/paper/1606.04838/) (2016)
- [Tackling the Objective Inconsistency Problem in Heterogeneous Federated Optimization](https://mlsanity.com/paper/2007.07481/) (2020)
- [Measuring the Effects of Non-Identical Data Distribution for Federated Visual Classification](https://mlsanity.com/paper/1909.06335/) (2019)
- [Local SGD Converges Fast and Communicates Little](https://mlsanity.com/paper/1805.09767/) (2018)
- [Clustered Federated Learning: Model-Agnostic Distributed Multi-Task Optimization under Privacy Constraints](https://mlsanity.com/paper/1910.01991/) (2019)
- [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)
- [Tighter Theory for Local SGD on Identical and Heterogeneous Data](https://mlsanity.com/paper/1909.04746/) (2019)
- [Don't Use Large Mini-Batches, Use Local SGD](https://mlsanity.com/paper/1808.07217/) (2018)
- [Is Local SGD Better than Minibatch SGD?](https://mlsanity.com/paper/2002.07839/) (2020)
- [Optimal Client Sampling for Federated Learning](https://mlsanity.com/paper/2010.13723/) (2020)
- [Local SGD with Periodic Averaging: Tighter Analysis and Adaptive Synchronization](https://mlsanity.com/paper/1910.13598/) (2019)
- [MATCHA: Speeding Up Decentralized SGD via Matching Decomposition Sampling](https://mlsanity.com/paper/1905.09435/) (2019)

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

- [Fine-tuning Global Model via Data-Free Knowledge Distillation for Non-IID Federated Learning](https://mlsanity.com/paper/2203.09249/) (2022)
- [Personalized Federated Learning with Feature Alignment and Classifier Collaboration](https://mlsanity.com/paper/2306.11867/) (2023)
- [DisPFL: Towards Communication-Efficient Personalized Federated Learning via Decentralized Sparse Training](https://mlsanity.com/paper/2206.00187/) (2022)
- [A Unified Analysis of Federated Learning with Arbitrary Client Participation](https://mlsanity.com/paper/2205.13648/) (2022)
- [Fed-CBS: A Heterogeneity-Aware Client Sampling Mechanism for Federated Learning via Class-Imbalance Reduction](https://mlsanity.com/paper/2209.15245/) (2022)
- [A Multi-agent Reinforcement Learning Approach for Efficient Client Selection in Federated Learning](https://mlsanity.com/paper/2201.02932/) (2022)
- [DELTA: Diverse Client Sampling for Fasting Federated Learning](https://mlsanity.com/paper/2205.13925/) (2022)
- [FedCross: Towards Accurate Federated Learning via Multi-Model Cross-Aggregation](https://mlsanity.com/paper/2210.08285/) (2022)
- [Context-Aware Online Client Selection for Hierarchical Federated Learning](https://mlsanity.com/paper/2112.00925/) (2021)
- [MP-FedCL: Multiprototype Federated Contrastive Learning for Edge Intelligence](https://mlsanity.com/paper/2304.01950/) (2023)
- [Federated Learning under Heterogeneous and Correlated Client Availability](https://mlsanity.com/paper/2301.04632/) (2023)
- [Federated Learning with Regularized Client Participation](https://mlsanity.com/paper/2302.03662/) (2023)
- [Is Aggregation the Only Choice? Federated Learning via Layer-wise Model Recombination](https://mlsanity.com/paper/2305.10730/) (2023)
- [Federated Learning in Non-IID Settings Aided by Differentially Private Synthetic Data](https://mlsanity.com/paper/2206.00686/) (2022)
- [Federated Learning with Flexible Control](https://mlsanity.com/paper/2212.08496/) (2022)
- [SAFARI: Sparsity enabled Federated Learning with Limited and Unreliable Communications](https://mlsanity.com/paper/2204.02321/) (2022)
- [A Survey on Participant Selection for Federated Learning in Mobile Networks](https://mlsanity.com/paper/2207.03681/) (2022)
- [FedGS: Federated Graph-based Sampling with Arbitrary Client Availability](https://mlsanity.com/paper/2211.13975/) (2022)
- [Adaptive Heterogeneous Client Sampling for Federated Learning over Wireless Networks](https://mlsanity.com/paper/2404.13804/) (2024)
- [From Deterioration to Acceleration: A Calibration Approach to Rehabilitating Step Asynchronism in Federated Optimization](https://mlsanity.com/paper/2112.09355/) (2021)
- [Fast Heterogeneous Federated Learning with Hybrid Client Selection](https://mlsanity.com/paper/2208.05135/) (2022)
- [Improving Accelerated Federated Learning with Compression and Importance Sampling](https://mlsanity.com/paper/2306.03240/) (2023)
- [FedSampling: A Better Sampling Strategy for Federated Learning](https://mlsanity.com/paper/2306.14245/) (2023)
- [Federated Learning While Providing Model as a Service: Joint Training and Inference Optimization](https://mlsanity.com/paper/2312.12863/) (2023)
- [Federated Learning under Periodic Client Participation and Heterogeneous Data: A New Communication-Efficient Algorithm and Analysis](https://mlsanity.com/paper/2410.23131/) (2024)
- [GlueFL: Reconciling Client Sampling and Model Masking for Bandwidth Efficient Federated Learning](https://mlsanity.com/paper/2212.01523/) (2022)
- [Differentially Private Federated Clustering over Non-IID Data](https://mlsanity.com/paper/2301.00955/) (2023)
- [FedStale: leveraging stale client updates in federated learning](https://mlsanity.com/paper/2405.04171/) (2024)
- [Federated Submodel Optimization for Hot and Cold Data Features](https://mlsanity.com/paper/2109.07704/) (2021)
- [Federated Learning on Non-iid Data via Local and Global Distillation](https://mlsanity.com/paper/2306.14443/) (2023)

## Abstract (arXiv)

This work addresses the problem of optimizing communications between server and clients in federated learning (FL). Current sampling approaches in FL are either biased, or non optimal in terms of server-clients communications and training stability. To overcome this issue, we introduce textitclustered sampling for clients selection. We prove that clustered sampling leads to better clients representatitivity and to reduced variance of the clients stochastic aggregation weights in FL. Compatibly with our theory, we provide two different clustering approaches enabling clients aggregation based on 1) sample size, and 2) models similarity. Through a series of experiments in non-iid and unbalanced scenarios, we demonstrate that model aggregation through clustered sampling consistently leads to better training convergence and variability when compared to standard sampling approaches. Our approach does not require any additional operation on the clients side, and can be seamlessly integrated in standard FL implementations. Finally, clustered sampling is compatible with existing methods and technologies for privacy enhancement, and for communication reduction through model compression.