Bi-level Sampling: Improved Clients Selection in Heterogeneous Settings for Federated Learning

Client selection (a.k.a., client sampling) is one of the hot topics in Federated Learning (FL). In each communication round, selecting some clients to participate in aggregation can effectively reduce the communication overhead caused by exchanging model parameters. However, due to statistical heterogeneity in FL, selecting clients randomly may affect the performance of aggregated global models. existing approaches regarding client selection firstly cluster clients and then sample(select) some representative clients from each cluster. However, these clusteringbased approaches may be either time-intensive or high complexity. To address these issues, In this paper, we introduce Bi-level Sampling, a clustering-based approach for client selection. After multinomial distribution sampling, Bi-level Sampling clusters clients based on weighted per-label mean class scores and then selects participating clients for federated learning in each round. Bi-level Sampling can lead to better client representativity and the reduced variance of the client's stochastic aggregation weights in FL. Our approach can be integrated into typical FL frameworks. Experimental results show that, compared with state-of-the-art approaches, our approach demonstrates significantly more stable and accurate convergence behavior-getting higher test accuracy and less training time, especially in highly Non-IID settings.