Heterogeneity-Guided Client Sampling: Towards Fast and Efficient Non-IID Federated Learning

Summary

This paper provides an interesting approach HiCS-FL to investigate the client sampling problem in federated learning, especially for the non-iid setting. This paper estimates the clients' data statistical heterogeneity (label distributions) via the client-updated gradients of the output layer's weights. By using this distance information, the server can distinguish which client owns more balanced data.

Strengths

- This paper found an interesting relationship between the last layer's bias and the label distributions of a given client data. - The proposed distance metric can be used to estimate the local data heterogeneity and distinguish which one's data is more balanced. - The paper is well-written and easy to follow.

Weaknesses

- A potential privacy issue may be raised since it needs to access the individual client update (i.e., gradient) information. More client's data information may be leaked from the gradient inversion attacks [1]. [1] Evaluating Gradient Inversion Attacks and Defenses in Federated Learning, NeurIPS 2021.

Questions

- Why the first training rounds set to be $\lceil N / K\rceil$ in line 235?

Rating

6

Confidence

2

Soundness

3

Presentation

3

Contribution

3

Limitations

See Weaknesses.

Summary

The paper address data heterogeneity by clustering clients via the gradients of the output layer to distinguish between clients with balanced from those with imbalanced data. HiCS-FL assigns different importance to the clusters according to their average estimated data heterogeneity. The paper found that there is a correlation between the gradient of the output layer and the label distribution.

Strengths

The paper is very well written. The paper did a good job of summarizing what others have done and how HiCS-FL differs. Figure 2, and Figure 3 shows considerable gain over the baselines on common FL datasets. The method doesn't incur computation or communication overhead and leads to 2x speed up over other methods.

Weaknesses

The approach of clustering to address heterogeneity might be practical as there are simpler methods that can achieve the same goal. The experiments were done on a small set of clients, 50. As the number of clients increases, the more pronounced the effect of heterogeneity can have.

Questions

Data heterogeneity can be mitigated with pre-training and personalization. Would pre-training make clustering unnecessary?

Rating

6

Confidence

4

Soundness

3

Presentation

3

Contribution

3

Limitations

The paper doesn't list limitation but I think a limitation there is the experimental setting. Using Dirichlet to generate clients is unrealistic (I know this is common in FL papers), and the paper focuses only on classification tasks.

Summary

The paper addresses the challenges posed by non-IID data in FL systems, particularly under communication constraints where only a small fraction of clients can participate in each training round. It introduces HiCS-FL, a novel client selection method. HiCS-FL estimates the statistical heterogeneity of a client’s data using updates from the network’s output layer to cluster and sample clients more effectively. Based on the heterogeneity information, clients are clustered, and those with more balanced data are preferentially sampled. Experimental results demonstrate HiCS-FL's superior performance compared to state-of-the-art methods.

Strengths

The introduction of a hierarchical clustering-based method that considers data heterogeneity is a significant advancement over existing client selection techniques. The solution considers the balanced and imbalanced client data to train the model, which is a very interesting perspective. The extensive experiments on multiple datasets and comparison with several baselines demonstrate the robustness and generalizability of HiCS-FL. This paper is well-written.

Weaknesses

- The paper primarily focuses on label imbalance when discussing data heterogeneity. However, other types of imbalances, such as feature imbalances within the data, are not considered. Addressing these other forms of data imbalance could provide a more comprehensive solution. - The method involves collecting updates from the fully connected layer, which may inadvertently reveal the label distribution of a client’s data. This could raise privacy concerns, as it potentially compromises the confidentiality of the client's data distribution. - The paper does not compare HiCS-FL with other relevant algorithms, such as Oort and Auxo, which also focus on client selection and clustering. Including these comparisons or discussions would provide a clearer picture of HiCS-FL's relative performance and effectiveness. [1] Oort: Efficient Federated Learning via Guided Participant Selection [2] Auxo: Heterogeneity-Mitigating Federated Learning via Scalable Client Clustering - The assumption that clients can be clustered into M groups, where M is larger than the number of selected clients (K) per round, may not be practical in large-scale systems. Specifically, the paper assumes that all clients are available during the initial clustering phase and that no new clients join the system later, which is unrealistic in dynamic FL environments. There might be additional overhead associated with the proposed clustering method. The paper should ensure that the experimental comparisons account for this overhead to maintain fairness in the evaluation of HiCS-FL’s performance.

Questions

- The rationale behind using gradients from different rounds for clustering clients is not clearly explained. Given that gradients can vary significantly across rounds, further clarification is needed to justify this approach and its impact on the effectiveness of the clustering process.

Rating

5

Confidence

4

Soundness

2

Presentation

3

Contribution

2

Limitations

See weakness

Summary

The authors propose a novel client selection method to address federated learning scenarios where clients exhibit varying degrees of data imbalance. The authors estimate the label distribution entropy of clients on the server side using the gradient of the output layer's bias. Based on this estimation, they cluster and sample clients, utilizing those with more balanced data to train the global model. Experiments in the paper demonstrate that the proposed method, HiCS-FL, achieves better and faster convergence compared to baselines. The authors provide detailed theoretical proofs to support their approach.

Strengths

1. This paper proposes HiCS-FL, a new federated learning method designed to adaptively handle clients with varying label distributions. It achieves better convergence and greater efficiency compared to baseline methods in experiments. 2. HiCS-FL utilizes the gradients of the output layer's bias to estimate clients' statistical data heterogeneity. This estimation is then used to cluster and sample clients, enabling efficient training of the global model with relatively data-balanced clients. 3. This paper provides a detailed theoretical analysis of HiCS-FL.

Weaknesses

See questions.

Questions

1. Is it due to privacy concerns that clients cannot directly compute and upload label distribution entropy to the server? If so, does estimating label distribution entropy through $ \Delta \mathbf{b}^{(k)} $ still pose privacy concerns for clients? Additionally, could you consider conducting an experiment comparing the federated learning performance (accuracy, convergence speed, etc.) using the true label distribution entropy versus the gradient-based label distribution entropy estimation proposed in this paper? 2. Why wasn't an experimental analysis conducted on different values of $ \lambda $ in Eq. 9? 3. Will the final trained global model be used for inference on local clients? If so, wouldn't the client selection method that prefers more data-balanced clients be suboptimal for local clients with severe data imbalance?

Rating

5

Confidence

3

Soundness

3

Presentation

2

Contribution

3

Limitations

The authors mention leaving studies of system heterogeneity to future work in the first paragraph of the Introduction, but there is no further discussion on the limitations of the proposed approach. There are no concerns raised about the societal impacts of the research.