Venue: NeurIPS 2022 Conference

Reviews:

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 Predictive Parity (PP) notion of fairness and conducts theoretical and empirical analysis. In particular, the paper considers the form of fair Bayes-optimal classifier as group-wise threshold-based classifiers (GWTRs), and provides sufficient condition for GWTRs to be optimal PP classifier. The analysis w.r.t. situations where such condition is or is not violated are also provided.
strengths_and_weaknesses: Overall, the paper is relatively well-written and easy to follow. The analysis provides connection between the cost-sensitive GWTRs and fair Bayes-optimal for binary classification. A two-stage algorithm is also proposed and evaluated empirically.

The weakness of the paper comes from a potential worry about the takeaway msg. It would be very helpful if the authors can also share the insight (if there are some) behind the possibility of deriving a necessary condition for GWTRs to be the fair Bayes optima. The paper provides sufficient condition, which is relatively intuitive. Condition 4.1 essentially requires that the output score $\eta_a(x)$ assigned to $(a, x)$ should not be too low (across the group) such that the classifier can easily achieve PP (e.g., the trivial case as an extreme). Here, it is natural to wonder what, if there is one, would be the necessary condition? Although this is not a trivial question, it would be nice to provide some analysis on it, especially considering the fact that there is an algorithm proposed to handle cases where Condition 4.1 is not satisfied.
questions: ### Q1: can authors share some insights regarding the potential necessary condition (or, the difficulty behind such analysis)?

(as detailed in Section `Strengths and Weakness`)

### Q2: w.r.t. the term "within-group fairness"

While I understand the phenomenon described in Section 4, I am a little bit confused about the role played by "within-group fairness". In PP notion of fairness, the definition is w.r.t. the proportion of real positive labels among predicted positives/negatives, there is no detailed characterization of instance-level qualification comparison within each group. I understand that the paper is not indicating the instance-level comparison, but personally I think it would be clearer if the authors can avoid such kind of potential misunderstandings.

### Q3: Equation 3

Is there a typo on $\eta_a(x)$ (i.e., it should be $\eta_1(x)$ since A = 1 is conditioned), or, there is a typo on the value assignment of $A$ (i.e., for left-hand side, A = a, but for right-hand side A = a')? From the context, I am not sure how to parse Equation 3. A clarification would be very helpful.

### Q4: w.r.t. recommended action in Algorithm 1

In lines 211-213, it is mentioned that if Condition 4.1 is not satisfied, the authors recommend considering other fairness notions. This is a little hard to parse. If Condition 4.1 is a sufficient condition, then the violation of it should not be advise us to go for a different fairness notion. After all, Condition 4.1 is not a necessary condition, the violation of which directly indicate the impossibility of pursuing PP.
limitations: It would be desirable if the paper can provide some discussion w.r.t. necessary condition beyond the sufficient condition 4.1 to give a whole picture of the problem at hand. 

Minor typo: line 310 [man] algorithms
review_title: null

final_score: rating: 4: Borderline reject: Technically solid paper where reasons to reject, e.g., limited evaluation, outweigh reasons to accept, e.g., good evaluation. Please use sparingly.
review_content: summary: This paper studies predictive parity, which is a kind of sufficiency-based fairness and requires the same probability of positive prediction. This paper makes two major contributions:1) Bayes-optimal classifiers satisfying predictive parity may or may not be 66 group-wise thresholding rules (GWTRs) 2) propose the FairBayes-DPP algorithm for binary fair classification, which is a post-processing  algorithm and to estimate the fair Bayes-optimal classifier under predictive parity This paper also provides the experiments to support the proposed method.
strengths_and_weaknesses: **Strengths**
1.The fairness studied in the paper is interesting. The predictive parity is of practical significance.
2. The theoretical analysis in this paper seems sound to me. The finding that “ the optimal fair classifiers may or may not be a GWTR, depending on the data distribution” is interesting and insightful. And it would be a good addition to the fairness community.
3. This paper is easy to follow.

**Weaknesses**
1. The motivation of this paper is not clear. 
    - I do not agree with the claim in this paper that “such as predictive parity are much less studied”(Line 5). As far as I know and also pointed out in this paper, there are tons of paper studies such fairness.  
    - The claim that “sufficiency-based measures such as predictive parity are less commonly considered, possibly due to the complexity of their constraints”(Line 40-41) is wrong to me. From Definition 3.3, we can see that the predictive parity is quite similar to separation-based measures(demographic parity), thus I don’t agree such fairness constraints is complicated. 
    - The proposed methods FairBayes-DPP is not well motivated. This paper should provide more reasons why the proposed method is suitable for this problem.
2. The preliminary about GWTR is not sufficient. The claim that “for many fairness metrics, the optimal fair classifiers are GWTRs” is not common knowledge to me. Thus I would suggest adding more introduction and discussion about the GWTR.
3. The experiments are not convincing to me. For baselines, one simple way is using the equation in Definition 3.3 as a regularizer. However, this paper does not compare any baselines, which can not show the effectiveness of the proposed method.

Overall, this paper is not well motivated and the experiments are not convincing. This paper in its current form is not ready to publish. Thus I recommend rejection at this time. And I believe this paper is a good addition to the fairness community if the author fixed the concerns.

questions: 1. This paper should provide more reasons why the proposed method is suitable for this problem.
2. I would suggest adding more introduction and discussion about the GWTR.
3. This paper should explore baselines to demonstrate the effectiveness of the proposed method.

limitations: None
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: The authors investigate the Bayes-optimal classifier for the fair classification with the predictive parity as a fairness constraint. They analyze whether the Bayes-optimal classifier forms a group-wise thresholding rule. As a result, they reveal the sufficient condition under which the Bayes-optimal classifier forms a GWTR. They also develop the algorithm for constructing a GWTR under the predictive parity constraint. The experimental results demonstrate that the proposed algorithm achieves fairer classifications than the unconstrained one.
strengths_and_weaknesses: 
(Strengths)
- Clearly written and technically sound.
- The condition of forming the Bayes-optimal classifier as a GWTR is interesting and crucial for understanding the predictive parity constraint.
- The authors give a reasonable algorithm for learning a GWTR while ensuring predictive parity.

(Weakness)
- Similar works investigating the fair Bayes-optimal predictor are motivated to clarify the cost of enforcing the fairness definitions, including the demographic parity and equalized odds. This work is somewhat weak because it cannot reveal the cost of the predictive parity.
- The result is just a sufficient condition is not a necessary and sufficient condition. The complete characterization of this phenomenon is still unfulfilled.
- Empirical comparison is somewhat weak. It lacks comparison with the existing sufficiency-based fair learning techniques.


This paper is clearly written and technically sound. The condition of forming the Bayes-optimal classifier as a GWTR is an interesting direction for understanding the predictive parity constraint. My current recommendation is acceptance.


The motivation of the existing works investigating the fair Bayes-optimal classifiers mostly comes from clarifying the cost of enforcing a fairness constraint. To this end, these works reveal the difference in accuracy between the unconstrained and constrained versions of the Bayes-optimal classifier. While clarifying the cost is well-motivated, the analyses in this paper are insufficient to reveal the cost of enforcing the predictive parity. It is better to include a discussion about this point.


The proposed method, FairBayes-DPP, is constructed reasonably. However, I am concerned about its statistical efficiency. Some researchers reveal the statistical efficiency of fair learning with the sufficient-based fairness definitions, including
- C. Jung et al. Moment Multicalibration for Uncertainty Estimation. COLT2021.
- E. Shabat et al. Sample Complexity of Uniform Convergence for Multicalibration.

I wonder whether the proposed method significantly improved from the methods analyzed in these papers. The problem setting of these papers might be somewhat different from this paper. Nevertheless, it is better at least to discuss the differences.

In the experiment, the authors only compare their method with the unconstrained one. I thus have concern that the proposed method underperforms the existing ones, including those introduced in this paper as "sufficient-based" ones, and additionally one in the following paper:
- U. Hebert-Johnson et al. Multicalibration: Calibration for the (Computationally-Identifiable) Masses. ICML2018.


Minor issues:
- Line 537 in the appendix: I cannot follow the inequality. Why the function $\tau \to (w_{a1}(t)+\tau v_{a1}(t))/(w_a(t)+ \tau v_a(t))$ is non-decreasing?
- Line 542 in the appendix: The definitions of $T_0$ and $T_1$ looks the same. Maybe, it is typo.

questions: See strengths and weaknesses. 
limitations: From the viewpoint of potentially negative impact, it is better to include the suggestion of the other fairness definition, which should be chosen when Condition 4.1 is not satisfied.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: The authors propose FairBayes-DPP, a post-processing method to achieve the Predictive Parity Fairness metric while maintaining accuracy levels that are comparable to unconstrained classifiers. They also propose a sufficient condition under which all Bayes-optimal classifiers that achieve predictive parity are Group-Wise Thresholding Rules (GWTR), and show that when the condition doesn't hold, it is possible that no Bayes-optimal classifier achieving predictive parity is GWTR, which they argue could lead to within-group unfairness.
strengths_and_weaknesses: Strengths: 
* The paper is well-written, and does a good job with describing its main findings: connecting DPP with Bayes-optimality, and proposing an efficient post-processing algorithm for achieving DPP without meaningfully trading off accuracy. They further explain their sufficiency condition, and incorporate it directly into their proposed algorithm, FairBayes-DPP.

Weaknesses: 
* One might question the novelty and significance of this work in relation to other works studying Bayes-optimality under fairness criteria, post-processing method (in particular FairBayes), and especially given the knowledge we have about calibration error being already bounded by the excess risk for unconstrained classifier (Liu et al. 2019 The Implicit Fairness Criterion of Unconstrained Learning).  I can see the last point being the main challenge to the significance of this work. 
* At the moment, the authors suggest that the reason sufficiency measures are understudied in the fairness literature could be the complexity of such constraints or the lack of label information. They seem to completely ignore other considerations such as the impossibility result of Kleinberg et al. (Inherent Trade-Offs in the Fair Determination of Risk Scores), Chouldechova et al. (Fair prediction with disparate impact: A study of bias in recidivism prediction instruments) etc; the more explicit warnings in Pleiss et al. (On fairness
and calibration); or the result showing calibration is favoured by unconstrained optimization. To me, this suggest further consideration of the context and implications of this work could be useful and strengthen this manuscript.
* Some of the implications of the finding could be better discussed: assume the sufficiency condition 4.1 does not hold. Does one necessarily need to look for other fairness criteria? Or is this just another type of fairness-accuracy tradeoff one should consider? What is the relation to Separation measures (Equalized odds, Equality of Opportunity, etc.)? And to Demographic parity? When should one prefer one over the other?
* I believe the authors wrote the manuscript assuming familiarity with post-processing and thresholding works within the fairness literature. I will make suggestions below about how to make it more accessible to those less familiar with this corpus. 
* Details such as choice of cost parameter c, thresholds t, etc. could be made clearer.
questions: Section 1
1. line 21: "Due to historical bias, vulnerable groups..." Sounds like the authors attribute algorithmic bias necessarily to "problems with the data", and historical biases. However, there are works and ongoing debates about sources of bias that can come from both data, representation, algorithms, etc., so overall there is evidence to suggest it may arise throughout the ML pipeline. You may want to make the phrasing more general.
2. line 34: this may be my ignorance, but why is GWTR a *minimal* requirement for within-group fairness? Could there be any stronger requirement?
3. lines 34-37: these lines already assume some familiarity with post-processing fairness, but no explicit connection or mention of this is included. You may want to explain such connection and provide a little more context.
4. lines 40-41: "sufficiency-based measures such as predictive parity are less commonly considered, possibly due to the complexity of their constraints...". As mentioned above, I see this as a serious omission and lack of consideration of the rest of the literature -- works such as the impossibility result and Pleiss et al. likely deterred researchers from looking to achieve both sufficiency and separation measures in any sense, and separation measures were likely preferred since sufficiency is already favoured by unconstrained optimization. I really do believe a further discussion of such arguments is needed, as well as good replies to why and when one should prefer DPP if at all, and why isn't unconstrained optimization good enough on its own for sufficiency
5. lines 42-45: Following my comment above, I think one of the main arguments against the significance of your work is in Liu et al. (which the authors cite as [30]). Could you provide a more direct answer to the question why isn't unconstrained optimization enough and when would FairBayes-DPP even be useful?

Section 2
6. lines 89-90: "...allowing for perfect predictions that equal the label". This sentence can be made clearer. What do you mean by equal the label?
7. line 91: "...the label information is often unknown for some groups...". Could you provide a citation for this argument? It's a point that was made before. Furthermore, one could presumably use the Y labels used in the training data and held-out-splits. Could you be clearer when making this argument?
8. line 109: "and the later tries to minimize". later should be latter.

Section 3
9. Definition 3.2 is from previous works, and mentioned in Zeng et al. (Bayes-Optimal Classifiers Under Group Fairness) as a classical result. Adding a citation here and discussing its connection to previous works could help.

Section 4
10. Some discussion of cost parameter c and its importance for condition 4.1 could be extended and made earlier (I know you did include some discussion in lines 157-160, but it took me time to realize it is the same c featured above Eq. 2). For example, how should one choose or tune such c?
11. lines 153-155: I'm not sure I understood why you interpret condition 4.1 to mean group performance varies only moderately, or why you discuss average performance, when what is being compared is simply the worst preforming group in terms of positive predictive value against the group with the most positive label presence? I may just be slow, but I think this intuition could be stronger if rephrased.
12. line 183-4: "has positive probability to be strictly larger than c, which is a technical condition needed in the proof". This line could be more convincing if you discussed the implications of this condition and how reasonable it is.

Section 5
13. after step 2: "for all t for which is it defined". Did you discuss anywhere whether you are looking for t values with a grid search in [0,1]? Where are these t values taken from?
14. footnote 4: "perform statistical hypothesis test of our sufficient condition". It may be helpful if you added some guidelines or suggestion on how to perform such a test (e.g., in the appendix), making it easier for others to use directly.

limitations: The authors did not specifically discuss limitations of their work. However, they did think carefully through a condition under which they may advise to not proceed with the use of their algorithm. I believe a broader context could have been considered in terms of suggesting when and how to use their proposed approach, in particular in relation to other possible fairness criteria. I think the manuscript could be strengthened by further discussion of relation to alternative fairness measures, but do not see it as a major concern.
review_title: null

Meta-review: metareview: The author considers fair Bayes-optimal classifiers under predictive parity. The authors show that under some sufficient conditions all such classifiers are groupwise threshold rules. They also show that htis is not necessarily the case when the condition does not hold. Some empirical results are also provided. The reviewers have made several important suggestions; in particular the authors should provide better context as well as discuss related work using other sufficiency metrics. As the changes are mainly about prior work, I'm inclined to recommend acceptance, but the authors should aboslutely implement all the changes they promised in the responses to the reviews.
confidence: Certain
Decision: Accept