Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: This paper presents an approach for learning predictors that have a small 'sufficiency' gap. Here the sufficiency gap is a difference that measures how invariant a predictor is across different subgroups.  The paper gives a theorem that bounds the sufficiency gap of a predictor in terms of the bayes optimal classifier. The proposed bound is then specified to the learned/randomized predictor in a separate corollary leading to 1) an optimization term and 2) an approximation term. Finally, the paper gives a bilevel optimization formulation for learning a predictor that has small sufficiency gap. In the lower level objective, the goal is to learn group specific predictors that while the upper level loss updates a global objective that tries to make the predictor as 'close' as possible to each of the subgroup predictors learned by the lower level problem. The bilevel formulation is compared to other baselines on different datasets where it has favorable performance.
strengths_and_weaknesses: ## Strengths
- **Studies Important Problem & Proposes an Interesting Solution**: The paper studies an important but open problem of learning predictors that have low sufficiency gap. The bilevel formulation presented is also interesting and is a relatively new way to approach the problem.

- **Interesting Generalization Error Bound**: Theorem 4.1 gives a generalization error bound of learning group-based predictors, which is also an interesting result.

- **Empirical Performance**: The results and comparison do seem to show that the bilevel formulation here either compares favorably or outperfoms other methods.


## Weaknesses
None of the weaknesses here are really disqualifying, but could be easily addressed in the paper.

- **Limited Samples**: The paper motivation of the paper is that there are only limited samples in each subgroup; however, how can there only be limited samples if one still has to learn a predictor for that subgroup? In practice, I don't think this approach works with only a limited number of samples. However, this issue is a matter of semantics.

- **Feasibility**: It is unclear how such group based approaches will scale with the number of groups. If $\vert \mathcal{A} \vert = 100$, is this approach even feasible? There is an assumption here that the $ \mathcal{A}$ partitions the available samples, but in practice you can have a sample be the intersection of two protected attributes, i.e., race and gender. In practice, poor performance often persists for the groups that happen to be intersection of protected attributes.

- **Link From Theorems to Bilevel Formulation**: It is not clear to me how the propositions and theorems in the paper suggest a bilevel formulation. It is still possible to relax the bilevel problem into a single objective with several penalties for each group. Not sure what in the theorems really necessitates a bilevel formulation.


- **Take away from the theorems**: Several of the theorems are in terms of the bayes optimal classifier for either a group or all data. Since the bayes classifier is usually infeasible to compute in practice, it is a bit hard to translate these insights to practice.


- **Challenge with different structural groups**: I wonder if the authors can speak to issues that occur when, say two groups just have different structural properties. Consider a 1-d case where a group of points have two regression parameters with positive slope, but the other groups has true parameters with negative slope. I am not sure how the formulation will handle that. Perhaps this is a limitation of the current setup?

- **Missing Literature on Bilevel Optimization**: There is an emerging rich literature on bilevel optimization that this paper did not reference or discuss. Once can often solve these problems with implicit differentiation or unrolling(as is done here). A discussion of these points is needed here.
questions: The main questions that I have a listed in the weakness section above. The ones I would like to hear the authors opinion on are 1) Challenge with different structural groups and 2) Feasibility.
limitations: An explicit discussion of limitations is not in the draft; perhaps this can be included in the next iteration.
review_title: null

final_score: rating: 8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.
review_content: summary: This paper discussed learning group sufficiency and accuracy for multiple subgroups. More specifically, it can have many subgroups and limited samples for each subgroup, which is a practically realistic and challenging task. The authors proposed a bi-level optimization to learn the fair predictor, and further derived several theoretical results to justify that both group sufficiency and accuracy could be controlled. The empirical performance demonstrated better fairness and accuracy of the proposed approach.
strengths_and_weaknesses: Strength: 
1.	The fairness topic discussed in this paper is interesting and important: when and how we could simultaneously achieve fairness (groups sufficiency) and accuracy (small generalization error). 
2.	Based on the theoretical analysis, this paper derived a novel fair learning approach. Besides, extensive empirical results demonstrated the superiority of the proposed approach. 
3.	In general, the paper is clearly written and well presented.
Weaknesses and comments:
1.	This paper mainly focused on group sufficiency as the fairness metric. Is it possible to derive similar results under criteria of demographic parity or equalized odds? What are the potential challenges for other fair metrics? Under these settings, is it still possible to achieve both fairness and accuracy for many subgroups?
2.	The regularization coefficient $\lambda$ seems to have a joint optimal value in 0.1-2. Could you elaborate more on why both fairness and accuracy drop when $\lambda$ is large?
3.	Is it possible to assume the general gaussian distribution rather than isotropic gaussian in the proposed algorithm? What is the difference?
4.	Can the proposed theoretical analysis be extended for a regression or segmentation task? For example, could we obtain the same results as the classification task?
5.	Could you explain a bit more on the intuition of group sufficiency? Is there any relation to the well-known sufficient statistics?
        Other comments:
1.	Could we extend the protected feature $A$ to a vector form? For instance, $A$ represents multiple attributes.
2.	In the Introduction part, the authors introduced a medical therapy instance to present the importance of group sufficiency. Could you explain a bit more about the difference between sufficiency and DP/EO metrics in the real-world application scenarios?
3.	In line 225 and line 227, the mathematical expression of gaussian distribution is ambiguous.
4.	In section 4.4, it mentions the utilization of Monte-Carlo sampling method. I am curious about the influence of different sampling numbers.


================================================
Thanks the effort from the authors, and I am satisfied with the rebuttal. I would like to raise my score to 8.
questions: It would be great if the author could address the questions in weakness and comments.
limitations: This paper discussed the limitations in the checklist.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: This paper presents a method for learning a fair predictor which is designed for scenarios where the data contains multiple subgroups, each with limited number of samples. This method formulates the subgroups fair predictor question as a bilevel objective. 

post-rebuttal
Thank you for the clarifications. I will raise my score to 7.
strengths_and_weaknesses:  Strengths:
(1) The paper proposed a novel method and provides solid prof. 
(2) The paper's framework seems technically sound. The gradient estimates seem reasonable to me. 
(3) The paper focuses on group sufficiency gap to measure fairness
Weaknesses:
(1) For Figure 3(a), though the method could achieve a lower group sufficiency gap, the accuracy is worse. I think this result is not enough to show the benefit because of the trade off between accuracy and fairness. 
(2) The bilevel optimization idea is not very novel as there are some existing works such as Ditto[1].
[1] Tian Li, Shengyuan Hu, Ahmad Beirami, and Virginia Smith. Ditto: Fair and robust federated learning through personalization. In International Conference on Machine Learning, pages 6357–6368. PMLR, 2021.
questions: (1) Need optimal $\lambda$ to be tuned by hand for each dataset?
(2) As I described in the weakness part, I think it's not a fair comparison in Figure 3(a). Could you please show the group sufficiency gap for each dataset with the same accuracy?
(3) How does the number of subgroups influence the final result.
limitations: The author didn't described the limitations of this work.
review_title: null

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: This paper considers the multiple subgroups scenario in the binary classification task. In order to avoid the inherent trade-off between accuracy and fairness (with fairness criteria such as DP and EO), authors focus on the group sufficiency, which requires that conditional expectation of $Y$ is invariant across different sub-groups. The proposed method is theoretical justified. Several theoretical results including the generalization error and the upper bound on the group sufficiency gap are derived. Based on the upper bound on the group sufficiency gap of the randomized algorithm, a machine learning algorithm is proposed to mitigate the bias of a model while not losing the informativeness. The idea of the novel bilevel optimization algorithm is to train an individual fair predictor by training the subgroup-specific predictors and then aggregating them. The idea of the novel bilevel optimization algorithm is to train an individual fair predictor by training the subgroup-specific predictors and then aggregating them. This allows to achieve superior performance over the other baselines on Amazon review, Toxic comment datasets.
strengths_and_weaknesses: [Strength]
* The paper is cleary written and the proposed bilevel optimization algorithm based on the theoretical results is original.
* It is quite meaningful that a model can achieve accuracy and fairness simultaneously under the Group sufficiency criterion unlike DP/EO (However, this appears to be achievable only when $f$ is similar)
* It is a great advantage that it can be applied to a variety of datasets, including NLP datasets (in typical fairness methods, there is often no scalability for diverse data types).
* From the group sufficiency of the $A$-group Bayes predictor, it is shown that the model can achieve both informativeness and fairness, simultaneously (Proposition 3.1).
* In theorem 3.2, an upper bound of the group sufficiency gap of any predictor $f$ is derived.
* Based on the theorem 3.2, an upper bound for the randomized algorithm is proposed. (Corollary 4.1).
* In theorem 4.1, the generalization error bound corresponding to the lower-level of the proposed algorithm is drawn.

[Weakness]
* In order for $Q$ to be informative and fair prediction, $f^{Bayes}$ should be similar, which seems to be a strong assumption in practical scenario.
* In algorithm 1, subset $A'$ is sampled for memory saving at each epoch, however, as this type of sampling is quite unfamiliar, it would be better to discuss further.
* Given that it can be applied to various datasets, the additional experimental results on vision datasets will have the effect of highlighting strengths of this paper.
* Experimental results on commonly used datasets in fairness literature such as COMPAS and Adult can be considered. (In these datasets, it seems possible to compare the proposed algorithm with baselines such as FSCS and EIIL.)
* It would be good to conduct an ablation study on using $Q$ as an informative prior.

questions: * Through the proof of proposition 3.1, it was confirmed that the suggested group sufficiency gap can be achieved to zero with $f^{Bayes}$. However, since $\mathbb{E}[Y|f^{Bayes}(X,A_1)] = \mathbb{E}[Y|f^{Bayes}(X,A_2)]$ is not generally satisfied, the invariance of conditional expectation for different subgroups is not established ($A_1$ and $A_2$ denotes two different groups). In other words, even if ${Suf}_{f}$=0, that conditional expectation of ground-truth label given predictor output ($\mathbb{E}[Y|f^{Bayes}(X,A_i), A_i]$) is invariant to the different groups is not guaranteed, which seems undesirable when considering the introduction background of Group sufficiency (line 30-32).
* The assumption that the Bayes-predictors for each group are the same seems to be strong, and the use of different classifiers for each group seems to have induced this phenomenon, what do you think?
* In the algorithm, $Q$ is used as an informative prior, but it seems that $Q$ may not be informative at the beginning of learning. I wonder if there is an experimental result or discussion for that. (Adaptively allocating lambda values according to the epoch may be a way.)
* DRO is a method that considers the worst-group accuracy, so it does not seem surprising that it is not effective in reducing the group sufficiency gap compared to the proposed method. It would be good to add a comment on the background of using DRO as a baseline.
limitations: It is mentioned that the main theoretical analysis is restricted to the randomized algorithm. It is noted that while Group sufficiency is improved, other fairness criteria such as DP/EO can be deteriorated. Also, authors mentioned that if the variance of Bayes predictors is large, the fair prediction model derived from the proposed algorithm may not that effective.
review_title: null

Meta-review: metareview: All reviewers acknowledged the contribution of the paper and its focus on the multiple (potentially a large number of) subgroup’s sufficiency gap. This is also a practically challenging setting, with each subgroup having only a very limited number of samples. The paper presents a bi-level optimization solution that shows favorable performance and is believed to be a solid and novel contribution to the relevant literature. The reviewers are unanimously happy with the reported results and the one added during the rebuttal. 

confidence: Certain
Decision: Accept