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:
- 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.
- 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.
- 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.
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