Variance-Reduced Heterogeneous Federated Learning via Stratified Client Selection

Shirui PanarXiv 2022 · arXiv

TL;DR

This paper introduces a novel "stratified client selection" strategy for Federated Learning (FL) to improve model convergence and accuracy, especially in heterogeneous data environments. By grouping clients into similar data distribution strata and then optimizing sample allocation within these strata, the method significantly reduces the variance of model updates, outperforming existing selection techniques.

What Problem Does This Paper Address?

Federated Learning (FL) trains models across decentralized data without sharing raw data, but communication costs are a major bottleneck. Client selection aims to reduce this by choosing a subset of clients for each training round. However, in real-world FL, client data is often heterogeneous (non-IID), meaning different clients have vastly different data distributions. This heterogeneity, combined with limited sampling ratios (only selecting a fraction of clients), leads to high variance in the model updates from the selected subset. This high variance slows down convergence and degrades model accuracy. Existing methods like random sampling, importance sampling, and cluster sampling struggle to effectively mitigate this variance in heterogeneous settings.

Methods

The paper proposes a Stratified Client Selection scheme. The core idea is to first group clients into "strata" where clients within each stratum have similar local data distributions. This stratification aims to create more homogeneous groups. The authors use the Silhouette Coefficient to determine the optimal number of strata.

After stratification, they employ an Optimized Sample Size Allocation strategy. Instead of simply picking clients proportionally to stratum size (as in some cluster sampling methods), they consider both the stratum's size and its variability (measured by cohesion, a proxy for standard deviation). This ensures that more diverse or informative strata are adequately represented in the sample.

The overall process involves:

  1. Client Stratification: Grouping clients into homogeneous strata based on their local data distribution.
  2. Optimal Sample Allocation: Determining the number of clients to sample from each stratum based on stratum size and variability.
  3. Stratified Sampling: Randomly selecting the determined number of clients from each stratum.
  4. FedAvg Integration: The selected clients then participate in the standard FedAvg training round.

The paper also provides theoretical analysis to prove that their stratified selection scheme leads to lower variance compared to proportional stratified sampling and random sampling.

Datasets

The paper evaluates its approach on the following datasets:

  • MNIST
  • FMNIST (Fashion-MNIST)
  • CIFAR-10

These datasets are partitioned using both IID (Independent and Identically Distributed) and non-IID strategies. The non-IID partitions are generated using Dirichlet distribution (varying the concentration parameter 'a' to control heterogeneity) and a "Shard" method (assigning clients data from only one class).

Key Insights and Ideas

  • Heterogeneity is the Enemy of Simple Sampling: The paper strongly demonstrates that as data heterogeneity increases and sampling ratios decrease, simple random sampling performs poorly. This highlights the need for more sophisticated selection strategies.
  • Stratification as a Variance Reduction Tool: By grouping clients with similar data distributions, the authors create more predictable and less volatile subsets for training, directly reducing the variance of model updates.
  • Beyond Proportional Allocation: The key innovation is not just stratification but also the optimized sample size allocation within strata. This acknowledges that not all strata are equally informative, and their variability matters for effective sampling.
  • Compatibility is Key: The proposed stratified selection scheme is shown to be compatible with existing FL algorithms like FedAvg, FedProx, and FedNova, enhancing their performance without requiring fundamental changes to the FL framework itself.

Key Results

  • Improved Accuracy and Convergence: The stratified client selection scheme consistently achieves higher final test accuracy and faster convergence compared to random sampling, importance sampling, and cluster sampling across various datasets and heterogeneity levels.
  • Significant Gains in Heterogeneous Settings: On non-IID datasets, the stratified approach shows substantial improvements. For example, on non-IID MNIST, it achieved 83.2% accuracy, while random sampling achieved only 62.0%.
  • Robustness to Sampling Ratio: The method remains effective even at low sampling ratios (e.g., q=0.1), where other methods degrade significantly.
  • Theoretical Guarantees: The paper provides theoretical proofs showing that the variance of model updates under stratified selection is less than or equal to that of proportional stratified sampling and random sampling.

Limitations and Future Work

  • Determining Strata and Variability: While the paper uses Silhouette Coefficient for stratification and cohesion for variability, the authors acknowledge that the "best" method for stratification and variability measurement is an open issue and may need adaptation to specific application scenarios.
  • Co-variance Consideration: The authors suggest that future work should consider the co-variance among different clients, as this can also contribute to performance degradation in FL.
  • Computational Overhead: While not explicitly detailed as a limitation, the stratification and optimized allocation steps add some computational overhead compared to simple random sampling. However, the experimental results suggest the benefits outweigh this cost.

Summary updated

Abstract

Client selection strategies are widely adopted to handle the communication-efficient problem in recent studies of Federated Learning (FL). However, due to the large variance of the selected subset's update, prior selection approaches with a limited sampling ratio cannot perform well on convergence and accuracy in heterogeneous FL. To address this problem, in this paper, we propose a novel stratified client selection scheme to reduce the variance for the pursuit of better convergence and higher accuracy. Specifically, to mitigate the impact of heterogeneity, we develop stratification based on clients' local data distribution to derive approximate homogeneous strata for better selection in each stratum. Concentrating on a limited sampling ratio scenario, we next present an optimized sample size allocation scheme by considering the diversity of stratum's variability, with the promise of further variance reduction. Theoretically, we elaborate the explicit relation among different selection schemes with regard to variance, under heterogeneous settings, we demonstrate the effectiveness of our selection scheme. Experimental results confirm that our approach not only allows for better performance relative to state-of-the-art methods but also is compatible with prevalent FL algorithms.
BibTeX
@misc{pan2022variance,
  author = {Shirui Pan},
  title = {{Variance-Reduced Heterogeneous Federated Learning via Stratified Client Selection}},
  year = {2022},
  eprint = {2201.05762},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2201.05762},
}
Figure