Fast Heterogeneous Federated Learning with Hybrid Client Selection

Guangyuan Shen, Dehong Gao, Duanxiao Song, Libin Yang, Xukai Zhou, Shirui Pan, Wei Lou, Fang Zhou

Abstract: Federated Learning (FL) faces significant challenges in heterogeneous environments where non-IID data distributions across clients lead to high variance in model updates. This paper introduces HCSFed (Hybrid Clustering-based client Selection), a framework that accelerates convergence by combining gradient compression, intelligent clustering, and dynamic sample size reallocation. Experimental results demonstrate that HCSFed achieves up to a 10.7x speedup in convergence on standard benchmarks compared to random selection methods.

Introduction

In Federated Learning, a central server coordinates training across a vast network of remote devices. Due to communication constraints, only a small subset of clients is typically selected for each training round. However, when client data is heterogeneous (non-IID), random selection often results in unrepresentative updates, introducing significant gradient noise and slowing convergence. Existing methods like importance sampling or raw gradient clustering often struggle with the high dimensionality of modern models or fail to capture client similarities effectively.

The HCSFed Methodology

HCSFed addresses these issues through a three-pronged hybrid strategy designed to select the most informative clients while minimizing variance:

  1. Compressed Gradient Clustering: Rather than clustering based on raw, high-dimensional gradients, HCSFed utilizes gradient compression. By grouping gradient components and retaining only group centers, the framework creates expressive features for clustering that are both computationally efficient and robust to noise.
  2. Sample Size Re-allocation: Unlike standard methods that allocate sampling slots equally, HCSFed identifies clusters with high internal heterogeneity and dynamically allocates more sampling slots to them, ensuring diverse data distributions are adequately represented.
  3. Intra-cluster Importance Sampling: Within each cluster, clients are selected using importance sampling based on the norm of their compressed gradients, prioritizing the most informative individuals.
Comparison of client selection strategies: (a) Importance Sampling, (b) Cluster Sampling, and (c) the proposed HCSFed approach.

Theoretical analysis confirms that this hybrid approach consistently yields lower variance than either random selection or basic clustering methods.

Experimental Evaluation

The performance of HCSFed was evaluated on MNIST, Fashion-MNIST (FMNIST), and CIFAR-10 datasets under varying degrees of heterogeneity (controlled via a Dirichlet distribution).

Key Results

  • Convergence Speed: On non-IID MNIST, HCSFed reached 80% accuracy in just 9 rounds, a 10.7x improvement over the 96 rounds required by random selection.
  • Accuracy: HCSFed consistently outperformed state-of-the-art methods like SCAFFOLD, particularly in highly heterogeneous settings.
  • Robustness: Sensitivity analysis showed that the framework maintains stable performance across different cluster counts and compression rates, simplifying deployment.

Key Insights

  • Compression as a Feature: Gradient compression serves as an effective filter, removing redundant information and highlighting essential features for client similarity.
  • Stabilizing Selection: Dynamic reallocation makes the sampling process robust against fluctuations in clustering quality.
  • Orthogonality of Techniques: The combination of clustering (similarity-based) and importance sampling (magnitude-based) provides a fine-grained optimization that neither technique can achieve in isolation.

Conclusion and Future Work

HCSFed presents a robust solution for accelerating Federated Learning in heterogeneous environments. By leveraging the synergy between compression, clustering, and importance sampling, it significantly reduces update variance and communication overhead. Future work will focus on relaxing theoretical assumptions for non-convex scenarios and addressing practical challenges such as client availability and stragglers.

Summary updated

BibTeX
@inproceedings{shen2023fast,
  author = {Guangyuan Shen and Dehong Gao and Duanxiao Song and Libin Yang and Xukai Zhou and Shirui Pan and Wei Lou and Fang Zhou},
  title = {{Fast Heterogeneous Federated Learning with Hybrid Client Selection}},
  booktitle = {Conference on Uncertainty in Artificial Intelligence},
  year = {2023},
  url = {https://openreview.net/forum?id=sQ2J52ccuh},
}
Figure