Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The paper proposes an interesting new federated learning approach called CLIMB that leverages a special formulation of the FL problem as optimization with constraints. The approach aims to improve the classification performance of FL method on class imbalanced data.

main_review: My main concern about the paper is the presentation of CLIMB as the method counteracting the issue of class imbalance. The method itself directly optimizes a problem that imposes small differences in classification performance among the clients. This certainly improves the fairness of the trained model, but it does not help when data is imbalanced. The authors demonstrate that CLIMB improves performance on minority classes in the imbalanced setting; however, it seems that it is only because the authors distribute the data across the clients in a special manner. Concretely, the dataset of selected clients contains a lot of minority examples, to the extent that locally the minority class has much more examples than majority classes. Therefore, a method that looks for a fair model (similar performance for each client) naturally also improves for imbalanced classes. However, it is difficult to say to what extent such particular data distribution occurs in practice. Moreover, the approach seems not to handle class imbalance in any way if the data is not distributed in such a particular way.

The second concern is about privacy. The approach seems to require sending lambda values for each client to the server, which are directly related to the difference between average performance among the clients and the client's performance. Therefore, by observing the value of lambda, one can deduce if the performance on client's data is good. Since the classifier usually better recognizes majority classes (particularly during training), the high lambda value possibly indicates clients with many minority class data? Have the authors considered this issue? 


summary_of_the_review: In general, the paper is well written, and the algorithm presentation is clear. The experimental evaluation is, in my opinion, insufficient if we interpret CLIMB as an imbalanced learning method (see the second paragraph of the review). For instance, more different ways of distributing data among the clients should be investigated.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The authors design a method, CLIMB, to solve the severe class imbalance issues in FL problem. In their method, they propose a constrained FL formulation (CFL) and adopt the method of Lagrange multipliers to solve this problem. They present some theoretical and experimental results to prove that their method is effective.
main_review: Strengths: 
1. Their method is agnostic to class distribution of the client data, which satisfies the privacy requirements of FL.

2. There is no need for active client selection in their method which is more practical than other similar work.

Weaknesses:
1. My first concern is about the Assumption 3.4. It seems too strong to me. Can you provide more FL literature which support this assumptions? I also hope you could provide a simple example which satisfies this assumption.

2. I am quite confused with the Theorem 3.2. What is the relationship between Theorem 3.2 and convergence of FL algorithms? Maybe you could combine it with Theorem 3.1 and add more detailed explanations to them.

3. The settings of  the experiments is ambiguous. In the caption of Table 1&2, what does “sufficiently many communication rounds” means? 
I recommend the authors should add some “Accuracy and Epoch” figures to show how fast the accuracy increases in their method and other baselines.

4. The results in Table 2 show that their method can achieve a better performance than Table 1. I think the authors should provide some theoretical analysis to explain this phenomenon.

5. In the section of introduction, the authors mention that a drawback of Yang et al., 2020 is that “a subset of the client’s local data need to be shared”. Why? 

6. Minor typos. “they will a higher probability to”->"there will ..."

summary_of_the_review: Although reducing the class imbalance in FL is an interesting topic and the method in this paper is new, I still think their method are not well-supported by theories and experiments according to the above discussion. Therefore, I think it is marginally below the acceptance threshold and needs further improvements.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The paper describes an agnostic constraint learning method for handling class imbalance in a federated learning setting. Here, a client may have a minority class which is globally (across clients) a majority class. By setting up the constraint learning using Lagrange multipliers, the theoretical solution and convergence guarantees is shown, along with empirical evidence of the methods superiority.
main_review: Overall, the paper is well written, with sufficient background and motivating examples on the problem under consideration. There exists some minor grammatical issues in Section 2 which needs to be carefully reviewed.
The empirical results clearly shows benefits of the solution setup. However, there are 3 suggestions to improve the paper: (1) Use of more complex datasets, (2) Comparison with other FL algorithms mentioned in the paper, even under additional settings such as active learning, MAB etc. (3) Need for ablation study on alpha.

Though MNIST and CIFAR10 is typically used as a standard dataset in literature, there exists more complex image datasets where the proposed method may struggle. From the current description, the limitations of the methods are not clear. Where does the method not work? If it works, why does it work? Here, comparison with existing techniques may aid in showing reasons for enhanced model performance. Finally, it would be interesting to see how variation in alpha affects model performance. If alpha=0.5, would the model still work relative to its baseline? When deploying the model in practice, alpha may not be known.

It is also not clear on how training and deployment of the algorithm work in practice. If a new client is added to the federated system, how does that affect model performance when shift in global data imbalance change? It would be good to discuss future work and how its applicability to multiclass classification would affect computational performance.
summary_of_the_review: The paper provides good theoretical and empirical justification of a unique problem of addressing extreme local imbalance in a federated data system while maintaining data privacy. However, additional supporting material and stronger empirical support may be required to justify strong conclusions in the paper.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper focuses on an interesting and challenging setting in federated learning, where number of classes and samples are imbalanced across different local workers. Compared to other methods which might require subset of local data or prior knowledge of the minor classes, the algorithm proposed in this paper does not need neither local data nor prior knowledge, which maintains the privacy principle in federated learning and aligned to real-world settings. The main contributions are:
1. Proposes a new algorithm solving the non-iid issue in federated learning which only adds constraints on local losses, without sacrificing local data privacy;
2. Utilizes a primal-dual optimization mechanism to solve the problem, provides theoretical guarantees on convergence;
3. Based on the experiments, there is a significant performance increase compared to FedAvg.
main_review: Strengths:
1. The problem is clearly stated and the algorithm is well-organised, theoretical analysis is provided;
2. The problem itself is interesting, non-iid and imbalance is a key challenge in federated learning and real-world setting;
3. The proposed algorithm is simple but efficient, since it does need sharing local data, privacy of local clients is also kept. Also, no prior knowledge required matches the real-world setting;
4. The way of partitioning the data is reasonable;
5. The experiments are mostly sound and comprehensive. Code is provided in the material, thus it should be easy to repeat the experiments and utilize the algorithm;

Weaknesses:
1. More citations on non-iid/imbalanced federated learning should be cited or taken into consideration as baselines. For example, [1][2][3];
2. Some minor written issues need to be taken care of. For example, g(\theta) needs to be defined before using it;
3. In the paper, the authors stated that "in the extreme case where every device has only one class, these methods have inferior performance than the classic Fed-Avg method," it would be good if the authors can provide the results in appendix. Also, in some non-extreme settings, if some of those algorithms perform better than FedAvg, it should be considered as a baseline;
4. The experiments are good, but would be better if results of experiments on other datasets, for example, synthetic dataset, fashion-MNIST are provided.



[1] Tackling the objective inconsistency problem in heterogeneous federated optimization. J Wang, Q Liu, H Liang, G Joshi, HV Poor - arXiv preprint arXiv:2007.07481, 2020

[2] H. Wang, Z. Kaplan, D. Niu and B. Li, "Optimizing Federated Learning on Non-IID Data with Reinforcement Learning," IEEE INFOCOM 2020 - IEEE Conference on Computer Communications, 2020, pp. 1698-1707, doi: 10.1109/INFOCOM41043.2020.9155494.

[3] On the convergence of fedavg on non-iid data. X Li, K Huang, W Yang, S Wang, Z Zhang - arXiv preprint arXiv:1907.02189, 2019
summary_of_the_review: This paper proposes a new algorithm on imbalanced setting in federated learning. It enjoys the advantages of not leaking local data and no need of prior knowledge and overall the algorithm based on primal-dual optimization is easy to understand and be utilized. It is a good paper after minor revisions.
review_title: null

Meta-review: This paper presents a method to handle class imbalance in federated learning, while accounting for data heterogeneity and privacy. The key idea is to solve a constrained optimization problem where the difference between the global and local objective values has to be less than some parameter $\epsilon$. The paper proposes a primal-dual optimization algorithm called CLIMB to solve this constrained FL problem. The paper presents a theoretical analysis of the algorithm, as well as experimental results. 

All the reviewers found the formulation interesting and novel and gave a positive assessment of the paper. Reviewer obo5 had some concerns about whether the optimization problem is improving fairness and getting reduced class imbalance as a side benefit or whether it is directly addressing class imbalance. After discussion with the authors, their concerns were partially addressed. Reviewer 8nbc had concerns about the assumptions and theoretical analysis. Their concerns were also mostly addressed by the authors during the discussion phase. I suggest the authors to also address Reviewer u6Lr and Reviewer Mp3G's concerns about experimental results and citing related work respectively when they revise the paper.

Overall, I recommend acceptance of the paper, and strongly encourage the authors to take the reviewers' suggestions about 1) fairness connections, 2) privacy connections, 3) theoretical analysis, 4) experimental results, and 5) prior work into account when revising it.
Decision: Accept (Poster)