Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: The authors propose a new fair FL algorithm that penalizes the variance (or semi-variance) of the utilities among the clients.
strength_and_weaknesses: -- I am surprised that the most closely related paper is not even mentioned. It seems clear that the authors are not aware that similar risk measures, adopted from mathematical finance, have been proposed in the group fairness literature.  In particular, conditional value at risk (CVaR) has been used in the literature since the following seminal work. 

https://proceedings.mlr.press/v97/williamson19a.html

Though it's not exactly the variance form, I believe that the CVaR formulation will be very similar when applied in the federated learning setting. The authors should have discussed the similarities/differences between the proposed approach and the CVaR formulation + FedAvg approach. 

-- Also, it will be great if the authors can comment on the relationship between robust optimization and mean/variance optimization. According to [Gotoh, Kim, Lim], they are essentially equivalent. This means that the robust federated learning algorithm such as DITTO might be very similar to what the authors proposed.

https://www.sciencedirect.com/science/article/pii/S016763771730514X

-- Some baselines are missing: Addressing Algorithmic Disparity and Performance Inconsistency in Federated Learning, NeurIPS'21
clarity,_quality,_novelty_and_reproducibility: n/a
summary_of_the_review: See my comments above.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper proposes two new fair federated learning (FL) algorithms, Variance Reduction (VRed) and Semi-Variance Reduction (Semi-VRed), which are inspired by two well-known risk modeling methods in Finance. VRed encourages equality between clients loss functions by penalizing their variance. In addition, Semi-VRed penalizes the discrepancy of only the worst-off clients loss functions from the average loss. Through extensive experiments on multiple vision and language datasets, it is shown that Semi-VRed achieves SoTA performance in scenarios with highly heterogeneous data distributions and improves both fairness and system overall average performance.
strength_and_weaknesses: Strength:
The proposed algorithm has a very intuitive justification, i.e., improving the overall performance without sacrificing the utilities of well-performing clients by penalizing the discrepancy of
only the worst-off client’s loss functions from the average loss. The connection between the proposed algorithms and risk modeling methods in Finance is also interesting. The experimental results also validate the proposed algorithm. 

Weaknesses:
The convergence result in Theorem1 is really hard to digest. It only provides an upper bound for the minimum expected gradient norm, and the second term will not converge to zero as T increases. It cannot show that the proposed algorithm will converge, and it is purely a bound for empirical risk during the optimization process instead of a bound of population risk or generalization error, which is not that informative in practice.

clarity,_quality,_novelty_and_reproducibility: The paper is well-written, and the proposed algorithm is novel based on my knowledge.
summary_of_the_review: The proposed algorithm is easy to implement and effective based on the experiments provided in the paper. However, there is still room for improving the theoretical guarantee in section 5.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper aims to guarantee the performance fairness among different clients in federated learning, while protecting the overall average performance from being sacrificed. The authors propose two algorithms based on variance reduction (in terms of all clients) and semi-variance reduction (in terms of the worst-off clients), respectively. Experimental results show that the proposed method can achieve SOTA performance.
strength_and_weaknesses: Strength:
1) This paper is well-motivated. Client-level performance fairness is an important topic in federated learning. Most of existing studies improve the fairness with the scarification of overall performance, while this paper focuses on both fairness and overall performance.
2) This paper is well-organized and the presentation is clear.

Weakness:
1) (Main Concern) I cannot understand why the proposed algorithm can protect the overall average performance from being sacrificed? According to the objective function Eq. (3) and Eq. (9), the proposed method improves fairness by minimizing the combination of overall risk and variance. Among them, the semi-VRed only penalizes the clients with local risk higher than the average risk. The semi-VRed does not encourage the clients with good performance to be closed to the average performance explicitly, however, it seems that there is also a performance sacrifice. There are always some clients that are up-weighted, which means that other clients are down-weighted relatively.
2) From the view of distributionally robust optimization, it seems that the proposed method is similar to reweight techniques (but with a smaller uncertainty set), which are widely used in the previous work, such as AFL [1] and DRFA [2]. The relations between this work and distributionally robust optimization-based methods should be discussed more.
3) The hyper-parameter local step number $K$ should be discussed, and it would be better to add more ablation studies about $K$, since there may be a trade-off between communication cost and performance (fairness). If $K$ is too small, more rounds of communication are needed to guarantee the convergence of federated model. If K is too large, the performance (fairness) may be not guaranteed, since the proposed federated algorithm is an approximation for the proposed objective function. Specifically, the difference between two rounds of local model parameters $f_i(\theta)-\bar{f}(\theta)$ is an unbiased estimation for the true weights (used to penalize the clients with worst performance) of clients, however, the variance of the estimation is very large (O(K^2)).

[1] Mohri M et. al. Agnostic federated learning. ICML 2019.
[2] Deng Yet. al. Distributionally robust federated averaging. NeurIPS 2020.

clarity,_quality,_novelty_and_reproducibility: This paper is easy to follow. The motivation is very interesting and the proposed problem is novel. But it seems that the proposed method lacks of novelty, since the core idea is similar to reweight for each client. A deep discussion about the difference of the proposed method and the previous work is expected. The authors have provided code and I think the reproducibility can be guaranteed.
summary_of_the_review: This paper investigates a well-motivated problem, and the experimental results show the effectiveness of the proposed method.

However, I have some concerns about the technically soundness of the proposed methods. A deep discussion is expected.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper provides two federated learning algorithms that aim to minimize the gap between the average performance of the trained model among clients and the performance on the worst-performing subgroups. The methods are designed to either minimize the variance or semi-variance of the clients' performance; called VRed and Semi-VRed, respectively. Authors establish convergence guarantees for VRed, and give several lemma to demystify the proposed algorithms. Through experiments, authors show that the performance of the proposed algorithms, especially that of Semi-VRed, is better than the prior state-of-the-arts.
strength_and_weaknesses: __Strengths__

- Theorem 1 seems to be a working way of giving convergence guarantees for variance-penalized optimizations under the context of federated learning. The proof idea may be useful for the future works that aim to give convergence guarantees based on alternative risk measures on clients (other than averaging).

- I like how authors compared the empirical performance of the proposed algorithm with a variety of baselines on the experimental setups that, up to my knowledge, has not been popularly used in the literature. From the appendices, I see that authors have put considerable effort in tuning the hyperparameters of the baseline methods, which will be a great academic asset of the community if the code is released.

__Weaknesses__

- It is not clear to me why authors did not consider any model personalization in this context. In footnote 1, authors explain that authors do not use model personalization in this work for a fair comparison with baseline algorithms. Putting a constraint purely for a fair comparison is not a very practical thing to do---if one can have improved (average and worst-case) performance by removing a constraint, why should one even consider a setup with such constraint? Could you provide any practical justification on why it is (at least sometimes) useful to consider federated learning without any model personalization?

- The performance of the trained models seems to be very low overall, which may be due to an excessive number of clients. For instance, the CIFAR-10 performance with ResNet-18 models is quite low; lower than 50% accuracy. It may be useful to have comparisons under such regime, but it will also be useful to have experimental results in a more well-performing regime, where the computation/communication budget is higher and the number of clients is perhaps smaller.

- The discussion about Theorem 1 is rather weak. Is there any helpful knowledge that we could deduce from the upper bound of Theorem 1? Comparing with the discussion on lemma 2, I think that Theorem 1 is way more non-trivial than lemma 1,2 should be treated better.
clarity,_quality,_novelty_and_reproducibility: Regarding the clarity, I must point out two issues:

- There should be some fixes to Algorithm 1: The parameter $\theta$ appears multiple time in the algorithm, but it is not clear what it is; is it $\theta_t$, or is it an adapted version, or maybe even a parameter of the previous global epoch?

- The notion of fairness under consideration should be explicitly spelled out. From the experimental results, I guess that the ultimate aim of this work is to maximize both (1) the worst-client accuracy, and (2) the average-client accuracy. Is this true? If so, it should help readers a lot to clarify this point early in the text.

Other than that, I do think that this manuscript is of sufficient quality, novelty, and reproducibility.
summary_of_the_review: This paper gives a simple, concrete, and well-performing federated learning algorithm with a sufficient degree of empirical validation. The paper could be much more impactful with some added experiments, but I do not see a very big reason to reject the paper.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: The main contribution of this work lies in exploiting the Variance Reduction and Semi-Variance Reduction of clients' utilities for achieving equality in federated learning.

After reviewing the authors' rebuttal and an active discussion, the reviewers agree that the problem is well-motivated and interesting.

The main concerns among the reviewers are that (A) there is a lack of discussion of the novelty of this work relative to existing bodies of works (e.g., DRO, risk measures, reweight techniques); and (B) the initial convergence results do not show algorithm convergence. The authors have responded to both these concerns by (A) discussing the above-mentioned bodies of related work, and (B) providing a new proof of convergence guarantee. However, for (A), some reviewers remain concerned about the similarity of this work to CVaR + FL and reweight techniques. For (B), it is noted that a strongly convex assumption is required for the new proof. (C) Finally, it is not clear if it is practical to achieve fairness in the case of low performance of trained models on CIFAR-10/100, albeit due to high data heterogeneity.

The authors are strongly encouraged to revise their work based on the reviewers' feedback and suggestions.
justification_for_why_not_higher_score: See the aforementioned main concerns (A), (B), and (C).
justification_for_why_not_lower_score: N/A.
Decision: Reject