Fair Bayes-Optimal Classifiers Under Predictive Parity
Authors: Xianli Zeng
Edgar Dobriban
Guang Cheng
Venue: NeurIPS 2022 Accept (2022)
Keywords: Fair Bayes-optimal classifier
Predictive parity
Group-wise thresholding rule
Fair-Bayes-DPP algorithm

Abstract: Increasing concerns about disparate effects of AI have motivated a great deal of work on fair machine learning. Existing works mainly focus on independence- and separation-based measures (e.g., demographic parity, equality of opportunity, equalized odds), while sufficiency-based measures such as predictive parity are much less studied. This paper considers predictive parity, which requires equalizing the probability of success given a positive prediction among different protected groups. We prove that, if the overall performances of different groups vary only moderately, all fair Bayes-optimal classifiers under predictive parity are group-wise thresholding rules. Perhaps surprisingly, this may not hold if group performance levels vary widely; in this case, we find that predictive parity among protected groups may lead to within-group unfairness. We then propose an algorithm we call FairBayes-DPP, aiming to ensure predictive parity when our condition is satisfied. FairBayes-DPP is an adaptive thresholding algorithm that aims to achieve predictive parity, while also seeking to maximize test accuracy. We provide supporting experiments conducted on synthetic and empirical data.

Fair Bayes-Optimal Classifiers Under Predictive Parity
Xianli Zeng NUS (Chongqing) Research Institute Chongqing, China com
Edgar Dobriban"
University of Pennsylvania
Philadelphia, PA 19104
dobriban&wharton, upenn edu
Guang Cheng?
University of California, Los Angeles
Los Angeles, CA 90095
guangchengâucla.edd
Abstract
Increasing concerns about disparate effects of AI have motivated great deal of work on fair machine learning. Existing works mainly focus on independence and separation eobadd measures (c.g., demographic parity, equality of opportunity, equalized odds), while sufficiency-basee measures such as predictive parity are much less studied. This paper considers predictive parity, which requires the same probability of success given a positive prediction, among different protected groups. We prove that, if the overall performances of different groups vary only moderately, all fair Bayes-optimal classifiers under predictive parity are grsep-wise thresholding rules. Perhaps surprisingly, this may not hold if group performance levels vary widely; in which case we find that predictive parity among protected groups may lead to within-group unfairness. We then propose an algorithm we call FairBayes-DPP aiming to ensure predictive parity when our condition is satisfied. FairBayes-DPPP is adaptive thresholding algorithm that aims achieve predictive parity, while also seeking to maximize test accuracy. We provide supporting experiments conducted on synthetic and empirical data.
Introduction
Due to the increasing ability to handle massive data with extraordinary model accuracy, machine learning (ML) algorithms have achieved remarkable success in many applications, such as computer
vision [4 46 23 47 and natural language processing [45] 49 55). However, empirical studies have also revealed that MI algorithms may incorporate bias from the training data into model predictions. Due to historical biases, vulnerable groups are often under-tepresented in available data 48 Moreover, risk minimization may further inadvertently introduce biases that not in the data [60] 24]. As consequence, without fairness considerations, ML algorithms can be systematically biased against certain groups defined by protected attributes such race and gender.
As algorithmic decision-making systems are now widely integrated in high-stakes decision- making processes, such as in healthcare [21] and criminal prediction [27], fair machine learning has grown rapidly over the last few years into key area of trustworthy AI. A main task fair machine learning is to design efficient algorithms satisfying fairness constraints with small sacrifice in model accuracy. This field has made substantial progress recent years, as many effective approaches have been
proposed to mitigate algorithmic bias [5 33 52 9 35
10 25 58
hattp:///stttistiic. wut.:sttsiiiccaaaattouuuuuuum wwwppppwwww.oooooeee//oooooeeoea
http://www.stat.t edua"aeduuu"e
hww.:/awwcccccccccccunuaagnnnnne guangchengggg//
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

An important fundamental benchmark for fair classification is provided by fair Bayes-optimal classifiers, which maximize accuracy subject fairness 36 [38. A key class of classifiers is group-wise thresholding rules (GWTRs) over the feature-conditional probabilities of the target label, for each protected group (e.g., probability of repaying a loan given income). Intuitively, being GWTR is minimal requirement for within-group fairness: the most qualified individuals are selected in every group. [8] 36 7 43 58) have studied fair Bayes-optimal classifiers under various fairness constraints and proved that, for many fairness metrics, the optimal fair classifiers are GWTRs.
Moreover, the associated thresholds can be learned efficiently [36 588.
Current literature on Bayes-optimality focuses mainly on the independence- and separation based fairmess measures (e.g,, demographic parity, equality of opportunity, equalized odds; see Section 2.1 for definitions and a review). However, the theoretical benchmark for some sufficiency- based measures such as predictive parity are not well understood, possibly due to the complexity of their constraints. Liu et al. [31] show that particular sufficiency-band -based measure, group calibration, is implicitly favored by unconstrained optimization: calibration error is bounded by the excess risk over the unconstrained Bayes-optimal classifier. Hebert-Johnson et al. (24) proposed a multicalibration method that guarantees calibrated predictions for several subpopulations. For selective classification, Lee et al. [30] find that sufficiency-basee representation learning leads to faimess. In this paper, we consider predictive parity, which requires that the positive predictive value (probability a successful outcome given positive prediction) be similar among protected groups. In credit lending, for example, predictive parity requires that, for individuals who receive the loans, the repayment rates in different protected groups the same. Although predictive parity is often applied assess an algorithm in recidivism prediction 199 13 6. little is known about (1) what are the optimal fair classifiers under predictive parity and (2) how to learn them effectively. In this paper, we aim to answer these two questions. We first study fair Bayes-optimal classifiers under predictive parity. Perhaps surprisingly, our theoretical results reveal that the optimal fair classifiers may may not be a GWTR, depending on the data distribution. We identify a sufficient condition under which all fair Bayes-optimal classifier are GWTRs. Without this condition, we show that fair Bayes-optimal classifiers may not be a GWTR when the minority group is more qualified than the majority group. In these cases, predictive parity may have limitations as a fairness measure, as it can either lead to within aethin group unfairness for the minority group or results in accuracy loss. Our findings are reminder that the improper use of fairness measures may result in severe unintended consequences. Careful analysis before applying fairness measures is necessary.
We then develop algorithm, FairBayes-DPP, aiming for predictive parity. Our method is two- stage plug-in method. In the first step, we use standard learning algorithms to estimate group-wise conditional probabilities of the labels. In the second step, we first check our sufficient condition, and then apply plug-in method for estimating the optimal threshoids under fairness for each protected group.
We summarize our contributions as follows.
We show that Bayes-optimal classifiers satisfying predictive parity may or may not be group-wise thresholding rules (GWTRs), depending on the data distribution.
We identify sufficient condition under which all fair Bayes-optimal classifiers are GWTRs. However, when the sufficient condition is not satisfied, the fair Bayes-optimal classifier may lead to within-group unfairness for the minority group.
We propose the FairBayes-DPP algorithm for binary fair classification. The proposed FairBayes-DPP is computationally efficient, showing a solid performance in our experiments.
2
Related Literature
2.1 Fairness Measures
Various faimesss metrics have been proposed to measure aspects of disparity in ML. Group fairness
2 [5] 22 targets statistical parity across protected groups, while individual faimess 26 29 41 aims to provide nondiscriminatory predictions for similar individuals. In general, group faimesss measures be categorized into three categories.
The first group consists of independence-basee measures, which require independence between predictions and protected attributes; this includes demographic parity [28] 57 and conditional
2

---

statistical parity 8 I. In credit lending, independence means that the proportion of approved candidates the same across different protected groups. However, as discussed in [2]], independence- based measures have limitations; and applying them often leads to substantial loss of accuracy.
The second group consists of separation-basees measures, which require conditional independence between predictions and protected attributes, given label information. Typical examples in this group are equality of opportunity [22] (59] and equalized odds [22 (6). In credit lending, separation- based measures require, that the individuals who will pay back (or default on) their loan have an equal probability of getting the loan, despite their race or gender. Compared to independence- based measures, separation-basee based measures take label information into account, allowing for perfect predictions that equal the label. However, these measures are hard to validate in certain applications as the label information is often unknown for some groups. For example, the repayment status is missing for individuals whose loan application declined.
As a result, measuring predictive bias is more widely applicable. This leads to the third class, sufficiency-baan bbased measures [39 [I], where the label is required to be conditionally independent of the protected attributes, given the prediction. In credit lending, this requires that among the approved applications, the proportion of individuals who pay back the loan is equal across different groups. Unlike independence- and separation-based measures that are well studied with solid theoretical benchmarks and efficient algorithms, some sufficiency- bassd measures, such as predictive parity, are less commonly investigated. A possible reason is that conditioning on the prediction leads to a complex constraint, which is thus challenging study and enforce algorithmically.
2.2 Algorithms Aimed at Fairness
Literature on algorithms for fairness has grown explosively over the past decade. Existing algorithms for fairness can be categorized broadly into three categories. The first category is pre-processing algorithms aiming to remove biases from the training data. Examples include transformations
17
25 fair representation learning (57 33 10] and fair data generation [53] 42 [4
40
The second group is in-processing algorithms, which handle fairness constraints during the training process. Two common strategies are penalized optimization [20 38 5 and adversarial training [59] 50 52 4) The former incorporates fairness measures as regularization term into the
optimization objective and the latter tries minimize the predictive ability of the model with respect to the protected attribute.
The third group is post-procees processooggg algorithms, aiming remove disparities from the model output.
The most common post-pre post-proesssing algorithm is the thresholding method [8] 36 I 43 [58], adjusting thresholds for every protected group to achieve fairness. In this paper, we propose a post-processing algorithm, FairBayes-DPP, to estimate the fair Bayes-optimal classifier under predictive parity.
3 Problem Formulation and Notations
In this paper, we consider classification problems where two types of feature are observed: the usual feature X E X', and the protected feature A E A. For example, in loan applications, X may refer to common features such as education level and income, and A may correspond to the race gender of a candidate. As multiclass protected attributes are often encountered in practice, we allow AA to have any number |A| 2 1 of classes, and let A {1, 2, ..., |Al]. We denote by Y the ground truth label. In credit lending, Y may correspond to the status of repayment or defaulting on loan. The output Ý of the classifier aims to predict Y based on observed features. We consider randomized classifiers defined as follows:
Definition 3.1 (Randomized classifier). A randomized classifier is measurable function X' x A- [0, 1), indicating the probability of predicting V = 1 when observing X and A We denote by Y, Y2(2, the prediction induced by the classifier f.
Group-wise thresholding rules 88 (GWT rules/classifiers or GWTRs over conditional probabilities of special importance. Consider an appropriate dominating sigma-finite measure μ on X (such as the Lebesgue measure for measurable subsets of R d 2 1, or the uniform measure for finite
We assume that, whenever needed, the sets considered are endowed with appropriate aggaa-algebas, and all functions considered measurable with respect to the appropriate algmara.
3

---

sets), and suppose that for all E A and E V, the features X have a conditional distribution Ja.y Pxja.y given A a. y with a density dPx (a.ay with respect j. For all & and a E A, let (a(x) - P(Y 1|X z, A= a).
Definition 3.2 (GWT classifier). A classifier f is a GWTR if there are constants ta a E A, and functions X - [0. 1]. E A. such that for all X and E A f(z, a) = Ina (x) > ta) + (z)) ta),
(1)
where I(.) is the indicator function.
Clearly, GWTRs choose individuals with the highest conditional probability in each group. This property is a minimal requirement for within-group faimesss. For example, a GWT recruitment tool ensures that the most qualified candidates are approved in every protected group. For many independence- and separation- baasd fairness metrics, the connection between Bayes-optimality and GWTRs has been well-documented in the literature. Corbett-Daviee et al. [8] proved that, under demographic parity and predictive equality, the fair Bayes-optimal classifiers are GWTRs with unspecified thresholds. By linking demographic parity and equality of opportunity with cost-sensitive risks, Menon and Williamson [36] further derived the thresholds for fair Bayes optimal classifiers under these two fairness measures. Under perfect demographic parity and equality of opportunity, exact forms of fair Bayes-optimal classifiers were derived in [7] and 43 respectively. More recently, by leveraging the Neyman Pearson argument from hypothesis testing. Zeng et al. [58] proposed general framework for deriving fair Bayes-optimal classifiers under independence-ans based fairness measures. They have elucidated a direct dependence of the optimal fair thresholds on the level of disparity.
Neyman-Pearson
separation-
In this paper, we consider predictive parity, which aims ensure the same positive predictive value among protected groups:
Definition 3.3 (Predictive Parity). A classifier f satisfies predictive parity for all A,
P(Y 18, 1, A = a) = P(Y 119;=11
We follow 55 to use the difference between positive predictive values to measure the degree of unfairness, defining the Difference in Predictive Parities (DPP) of a classifier f as
DPP(f) Σ P(Y = 1|8; 1, = a) - P(Y =18;, 1)1.
4 Fair Bayes-optimal Classifiers under Predictive Parity
Since predictive parity is commonly considered under the scenarios where false positives are par- ticularly harmful (30], we study cost-sensitive classification. For cost parameter e E [0, the
cost-sensitive 0-1 risk of the classifier f is defined as
Re( = c- P(C, 1, 0) + c1 =
An unconstrained Bayes-optimal classifier for the cost-sensitive risk is any minimizer f E argmin, Ro(.). classical result is that all Bayes-optimal classifiers have the form f*(x,a)
(T)(a) > c) + (1 (x) = c). where J e [0, 1] is arbitrary [6 36).
In the literature, Liu et al. 33 proved that group calibration can be achieved by unconstrained optimization. In fact, the Bayes-optimal score function na is clearly calibrated with respect to any collection of groups. As a result, when (z) is consistently estimated (which can be achieved by unconstrained optimization), the calibration error is well bounded by the excess risk. However, when the training data is biased, we can have
P(Y 1/nn(()) > c, A a) + P(Y 1|nar (X) > c,A==') a') for a a'
In other words, even though the Bayes score 7a satisfies perfect multicalibration, it does not satisfy predictive parity. Taking DPP constraint, a fair Bayes-optimal classifier is any minimizer of the cost-sensitive risk among fair classifiers:
firv argmin Re( f:DPP(f)=0
"To be precise, this conditional density is defined for r-almost every x E X: however for simplicity we say for all x E X. We use this convention without further mentioning through the paper.
When 1/2, cost- sensitive risk reduces the usual zero-one risk.

---

4.1 GWT Fair Bayes-Optimal Classifiers under Predictive Parity
We first identify a sufficient condition under which all fair Bayes-optimal classifier under predictive parity are GWTRs.
Condition 4.1 (Sufficient condition for Bayes-optimal classifiers to be GWTRs). min P(Y = (X) 2 e, 2 max P(Y = 1|A = a). acA
aeA
The sufficient condition 4.1 requires that the minimal group-wise positive predictive value P(Y- 2 ()aa())
A = a) of the unconstrained Bayes-optimal classifier is lower bounded by the maximal proportion of positive labels P(Y 1|A = a) among groups. In other words, the performances of different groups vary only moderately: with respect to the unconstrained Bayes optimal classifier, the positive predictive value of the worst be greater than the overall performance P(Y 1|A a) of the best group. Condition 4.1 holds if
the proportion of x such that 77 (z) > c should
P(Y = 1|A = a) I c for all a E A. because P(Y = 1 na (X) 2 c, A = a) 2 c.
These conditions are applicable in settings where e is large, such as in credit lending where false positives are more harmful than false negatives, or if pyla. a E A are small, such as in job recruitment or school admissions where the number of slots is much smaller than the number of applications. Under this condition, we present our main result.
Theorem 4.2 (Main result). Consider the cost-sensitive 0-1 risk with cost parameter c. If Condition 4.1 holds, then all fair Bayes-optimal classifiers under predictive parity are GWTRs. Thus, for all Pp from ( there are (tx) E [0, 1]11) and functions Tā (x)
X + [o, 1] such that, for all
E X and E A,
SPpv(s, a) I (m (x) > (5) + + (x) (1a (x) 12)
Unlike for demographic parity or for equality of opportunity, where the fairness constraint is linear with respect to the probability predictions of the classifier f (36), the DPP constraint is non-linear with respect to f- As a consequence, previously used theoretical tools such as the Neyman- Pearson argument from hypothesis testing [58] are longer valid in this case. Instead, using a novel constructive argument. When Condition 4. is satisfied, for any classifier satisfying predictive parity, which is not GWTR, we construct GWTR that satisfies predictive parity and achieves smaller classification error. As a result, under Condition 4.1 all fair Bayes-optimal classifiers are GWTRs. Overall, the proof of Theorem 4.2 is quite involved, and requires lot of careful casework and analysis.
prove the result
4.2 Fair Bayes-optimal Classifiers under Predictive Parity do not Need to be Thresholding Rules
Next, we consider the case when the sufficient condition 4.1 does not hold. For simplicity, we consider a binary protected attribute E {0. }} with
P(Y 1 n (x) 2 c, 1) P(Y 1|A 0).
(3)
Our result shows that, under condition B}. there exist class probabilities Pas a E A, such that no Bayes-optimal classifier under predictive parity is a GWTR.
Theorem 4.3. Suppose that condition (3) holds. Denote t inf P(Y 1l 2 t
1) > P(Y = 1|A 0)}. Suppose there exist ,,,02 > 0 such that P(c 81 < πΛ(X) f 1)= 82 0. Then. all p1 > 32 no fair Bayes-optimal classifier under predictive parity is GWTR.
The condition involving the constants 81, 82 > 0 ensures that 77 (X) has positive probability to be strictly larger than which is a technical condition needed in the proof. Theorem (43 shows that predictive parity may lead to within-group unfairness, whereby the most qualified individuals are predicted to be unqualified, for a better overall accuracy. By definition, predictive parity requires that the qualifications of selected individuals are similar across the protected groups. Suppose there exists a highly qualified minority group in which most individuals are qualified. Selecting the most qualified individuals in this group leads to very high standard. As a result, many qualified individuals in other majority groups may be predicted to be unqualified using this standard, leading to accuracy loss. Conversely, if we select less qualified individuals in the highly qualified group, the lower standard allows more qualified individuals from the other groups to be selected, and increases accuracy.
5

---

Algorithm 1 FairBayes-DPP
Input: Datasets S U Sa with S (mi 4 De and Sa (1,]0) ,jj j==1-
) Cost parameter
E [0, I].
Step 1: Estimate (2) by n = fg. with @ from
Step 2: Find the optimal thresholds.
Define, for all t, (tV = 2 M6,, 1.
P(Y 1/A = a) =
(a)
1 (o)
==1
if min, PPV max, P(Y = 1|A a) then
Warning: Applying FairBayes-DPP may lead to accuracy loss.
else
Let min = minft: PPV, (t) 2 max, P(Y = 1|A=
for t E T [mi;: max, in (z² do
for AA {1} do
Find (t) such that PPV (f)( ~ (t). end for
Let fax a, t) = f (x, (1) (1)) = (fa(t) f.(t).
Let Re(t)= n Ei= cll-vi)( vi) 8) (m # f(z,,
end for Find f = argminR.(t).
IET,
Output: fPP(I, a) (ffa(()) (0)
end
5 Dai: Adaptive Thresholding for Fair Baycs-optimality
In this section, we propose the FairBayes-DPP algorithm (Algorithm [ for fair Bayes-optimal classification under predictive parity. As mentioned, the DPP constraint is non-linear with respect the classifier f, and is also highly non-convex with respect the model parameters, even if both the classifier f and the risk function are convex with respect to these parameters. In such cases, incorporating fairness constraints
penalty in the training objective may be hard due to potential local minima. Therefore, we consider a different approach, developing new two-step plug-in method based on Theorem 4.2 Suppose we observe data points (Iz ai y:) drawn independently and identically from distribution 'D over the domain X' x A x V
Step 1. In the first step, we apply standard machine learning algorithms to learn the feature- and group-conditional label probabilities 1) based on the whole dataset. Consider a loss function L(---) and the function class F {ʃe 0 E θ) parametrized by 0. The estimator of ry is obtained by minimizing the empirical risk, na (2) == fā( a), where
x L(yr, a.)).
â argmin lE0
(4)
n
Here we use the cross-entropy loss, as minimizing the empirical 0-1 risk is generally not tractable. At the population level, the minimizers of the risks induced by the 0-1 and cross-entropy losses are both the true conditional probability function [37].
Step 2. In the second step, we first check the empirical version of Condition 4.1 for the classifier derived in the first step. To be more specific, we divide the data into |AA parts, according to the value
(z)50) Mij (a) nn where af0) a. Let, for all for which is defined,
of A: for A, S.
PPV. = E T(,) (a) 1, iia (1. (0) 2 1)
and P(Y = 1=11 1
Σ/= 1 (2.1)) 2 t)
We only divide by nonzero quantities here and below. To ensure that the quantities we divide by nonzero, we restrict to to [0, max, (fa (z,55)) })] when evaluating ,PV, We check whether

---

min, PPVa(c) 2 max, P(Y = 1|= - a) If this is not satisfied, we provide warning message that applying FairBayes-DPP may lead to accuracy loss, see the discussion after Theorem 4.3 If it is satisfied, we then adjust the thresholds of the classifier aiming for predictive parity. Based on Theorem 4.2 we consider the following deterministic classifiers:
a)
(zz a; &1, ....... ((A1) = 1 (Na 2 to):
(5)
where r is the estimate of 7) from the first step, and ta a E A, are parameters to learn.
We use the following strategy to estimate ta E A: First, we fix the threshold for the group with
1, say I. The positive predictive value for this group can then be estimated by PPV, (1). To achieve predictive parity, we need to find thresholds for the other groups such that the positive group-wise predictive values are the same i.e., find La
2.3..... ... |Al, such that PPV (ta) s (t), for a = 2, ...., LAl.
(6) As stated in Lemma A.I the positive predictive value for each group in the population is always non-decreasing with the thresholds ta increases. As consequence, we can search over tas = 2.3..... |A), efficiently via, for instance, the bisection method Correspondingly, we consider the following range of t: T = [tmins max, m (22) with
min min (PV)(t)) 2 max P(Y 1|A 1|}=
We denote by (t) a 2, ... |A), the estimated thresholds given by (6). writing (1()) for convenience. We consider the classifier (5) with these thresholds:
f(x, = f (z, a; (t), (())))) (7) 2 fa))
Lastly, we find & that minimizes the cost-sensitive risk on the training data by searching over grid Tn within
i = argmin TET,
uil (1 Ilys + f(z
f( an.t))
Our final estimator of the fair Bayes-optimal classifier is fpp ft. The FairBayes-DDe DPP algorithm related to the algorithms proposed for other fairness measures in [58). where a binary protected attribute is considered and closed-fome optimal thresholds are derived. In contrast, FairBayes-DPP can handle multi-class protected attributes and does not rely on closed-form thresholds. Similar to [58]. algorithm enforces fairness only in the fast second step, where gradient-based based technique is applied. Thus, is computationally efficient and the non-convexity of fairness constraint is no longer problematic. Our experimental results demonstrate that our method removes disparities and preserves accuracy.
Experiments
6.1 Synthetic Data
We first study a synthetic dataset to compare our method with the true Bayes-optimal fair classifier derived analytically using the true data distribution.
Statistical model. Let X (X1, X2) E 2 be a generic feature, A {0, be the protected attribute and Y E {0, 1} be the label. We generate A and Y according to the probabilities P(A = 1). P(Y = 1|A = 1) and P(Y 1 = 0), specified below. Conditional on = a and Y y. X is generated from bivariate Gaussian distribution N((2a 1, 2y 1)T 2 12). where I is the p-dimensional identity covariance matrix. In this model, 7/o (x) has a closed form, and we use it to find the true fair Bayes-optimal classifier numerically under the Condition 4.1 More details about this synthetic model can be found in Section C Appendix.
6 One could modify this to allow some slack; and perform formal statistical hypothesis test our sufficient condition.
Since sample mean Σi= Z: of iid random variables has a variability of order (p(n (m(3)))) even the true predictive parities are equal, empirical versions may differ by Or(n -1/2). However, in our case we simply find the values fa, t for which they are as close as possible.
TThe empirical PPV only approximately monotonic. but this does not problems.
7

---

Table 1:
Classification accuracy and DPP of the true fair Bayes-optimal classifier and our estimator
trained via logistic regression on a synthetic data example. See Section 6. for details.
THEORETICAL VALUE
LOGISTIC REGRESSION UNCONSTRAINED
FAIR
UNCONSTRAINED
FAIRBAYES- DPP
ACC
DPP
ACC
DPP
ACC
DPP
ACC
0.2
0.814
0.000
0.814
0.049 (0.036)
0.813 (0.005)
0.046 (0.037)
0.813 (0,005)
0.3
0.794
0.024
0.794
0.037 (0.029)
0.794 (0.006)
0.040 (0.033)
0.794 (0.005)
0.4
0.781
0.050
0.781
0.035 (0.029)
0.781 (0.006)
0.054 (0.029)
0.782 (0.005)
0.5
0.775
0.078
0.777
0.042 (0.032)
0.775 (0.006)
0.081 (0.036)
0.777 (0.006)
0.6
0.778
0.113
0.781
0.038 (0.031)
0.778 (0.006)
0.113
0.781 (0.006)
Experimental setting. We randomly sample 50, 000 training data points and 5, 000 test data points. In the Gaussian case, the Bayes-optimal classifier is linear in x and thus we employ logistic regression to learn 7/1 (-) and (.).). We then search over a grid with spacings equal to 0.001 over the range we identified in Section 5 for the empirically optimal thresholds under fairness. We denote f and frrv the estimators of the unconstrained and fair Bayes-optimal classifiers, respectively.
We first evaluate the FairBayes-D DDP algorithm under the Condition 4.1 We set the cost parameter 0.5, while P(A = 1) 0.3 and P(Y 1 A = 0) 0.2. It can be calculated that P(Y 1 (X) > 0.5, A 0) x 0.613, using (23 in the Appendix. To consider settings with varied 1|A = from 0.2 to 0.6, with the DPP of unconstrained Bayes-optimal classifier grows from 0 to 0.113.
levels of fairness in the population, we vary p = P(Y
Table 1 presents the classification accuracy and DPP of the true fair Bayes-optimal classifier and FairBayes- trained via logistic regression over 100 simulations" [9] Our first observation is that, under predictive parity, the accuracy of true unconstrained and fair Bayes-optimal classifiers is almost identical, indicating that predictive parity under Condition 4.1 requires a very small loss of accuracy.
Second, our FairBayes-DPP method closely tracks the behavior of the fair Bayes-optimal clas- sifier, controlling the accuracy metric ACC and unfairness metric DPP on the test data effec- tively. When P(Y = 1|4- = 1) P(Y = 1|A = =0] is small, FairBayes-DPP performs similarly to the unconstrained classifier. However, when the data is biased against protected groups and [P(Y = 1 = 1) P(Y - 1|A 0) is large. FairBayes-DPP mitigates the disparity of the un- constrained classifier effectively, while preserving model accuracy. We further conduct extensive simulations to evaluate the FairBayes-DPP algorithm with different model and training setups, as shown in the Appendix. In particular, we also consider the multi-class protected attribute case.
6.2 Empirical Data Analysis
Dataset. We test FairBayes-DPP on two benchmark datasets for fair classification: "Adult" [1] and "COMPAS" (27). For each dataset, we randomly sample (with replacement) 70%, 50% and 30% as the training, validation and test set, respectively. To further test the performance of our algorithm on a large-scale dataset, we conduct experiments on the CelebFaces Attributes (CelebA) Dataset 32
Adult: The target variable Y is whether the income of an individual is more than $50,000. Age, marriage status, education level and other related variables are included in X, and the protected attribute A refers to gender.
COMPAS: In the COMPAS dataset, the target is to predict recidivism. Here Y indicates whether or not a criminal will reoffend, while X includes prior criminal records, age and an indicator of misdemeanor. The protected attribute A is the race of an individual, "white-vs-non-whitte"
CelebA: CelebA dataset is large-scale dataset with more than 200,000 face images, each with 40 attributes (including protected attribute "gender" and other 39 different attributes for prediction tasks). Our goal is predict the face attributes Y based on the images X and remove bias with respect to gender A from the output.
Here, the randomness of the experiment is due the random generation of the synthetic data.
8

---

Accuracy on Adult and COMPAS datasets
DPP on Adult and COMPAS datasets
0.175
FairBayes-DPP
0.150
Unconstrained
0.125
Accuracy
FairBayes-DPP Unconstrained
DDP
0.100
0.075
0.70
0.050
0.025
0.65
0.000
Adult
COMPAS
Adult
COMPAS
Figure 1: Accuracy and difference in predictive parity the Adult and COMPAS datasets.
Experimental setting. As algorithms for predictive parity are rarely considered in the literature. use unconstrained learning baseline for our experiments. For the "Adult" and "COMPAS" datasets, we adopt the same training setting as in S [58]. The conditional probabilities are learned a three-layer fully connected neural network architecture with 32 hidden neurons per layer. For "CelebA", we apply the training setting from (5I). We learn the conditional probabilities by training ResNet50 model (23). pretrained on ImageNet [TT]. For all the datasets, Over the course of training the model on the training set, we select the one with best performance on the validation set. In addition, we learn the optimal thresholds over the validation set avoid overfitting. All experiments use Py PyTorch. We refer readers to the Appendix for more training details, including optimizer, learning rates, batch sizes and training epochs. We repeat the experiment 100 times for the Adult and COMPAS datasets and 10 times for the CelebA dataset 10
Figure T presents the average performances of FairBayes-DPP and unconstrained learning the Adult and COMPAS datasets. Our method achieves almost the same accuracy as the unconstrained classifier. and has smaller disparity. To better compare our fair classifier with the unconstrained one, we use the paired t-test to compare the DPP of the proposed algorithm (DPP Fair) and of unconstrained learning IDPPBasch We consider the following one sided test:
Ho DPP fair DPP Base
V.S.
Hi DPP fair DPP Base
The values the tests are 3.90 10-4 for the Adult dataset and 3.09 10-8 for the COMPAS dataset. In both cases, these results provide evidence that our FairBayes-DPP achieves a smaller disparity than unconstrained learning.
Finally, we test FairBayes- DPP on the CelebA dataset, Here, we only consider 27 attributes with 0.01 P(Y = 1|M), P(Y 1|F) < 0.99 in the training, validation, and test to ensure that the training, validation and test sample sizes are large enough for each subgroup. We further identify one attribute. "Young". that violates Condition 4.1 We calculate the per-attribute accuracies and DPPs on the test set. Table ppresenns the results of the first six attributes; the remaining results are in the Appendix. As we can see, even for the large-scale CelebA dataset with high dimensional image features, our algorithm mitigates the gender bias effectively, with almost no loss of accuracy.
Forr the Adult and COMPAS datasets, the randomness of the experiment training, validation test data, as well as the stochasticity of the batch selection in the optimization algorithm. For the CelebA dataset, the randomness is caused by the stochasticity of the optimization method.
from the random selection
"mmong the 39 attributes, 12 heavily skewed with min( P(Y 1JM), P(Y 1|F)) < 0.01 max(P 1[M), P(Y 1 F)) 0.99 (where represents Male and represents Female) training, validation or test set. They are: "5 o' Clock Shadow", "Bald", "Double Chin", "Goatee", "Gray Hair", "Heavy Makeup", "Mustache", "No Beard",, "Rosy Checks", "Sideburns". "Wearing Lipstick" and "Wearing Necktie"..

---

Table 2: Per-attribute accuracy and DPP of the FairBayes-DPP algorithm and unconstrained opti-
mization.
PER-ATTRIBUTE ACCURACY
PER-ATTRIBUTE DPP
ATTRIBUTES
FAIRBAYES-DAA DPP
UNCONSTRAINED
FAIRBAYES-DIA DPP
UNCONSTRAINED
ARCHED EYEBROWS
0.838(0.003)
0.838(0.003)
0.027(0.015)
0.099(0.041)
ATTRACTIVE
0.825(0.002)
0.826(0.003)
0.075(0.011)
0.169(0.016)
BAGS UNDER EYES
0.853(0.002)
0.852(0.002)
0.024(0.015)
0.056(0.034)
BANGS
0.959(0.001
0.959(0.001)
0.007(0.007)
0.069(0.029)
BIG LIPS
0.706(0.009) 002)
0.717(0.003)
0.023(0.015)
0.115(0.027)
BIG NOSE
0.845(0.002)
0.847(0.003)
0.083(0.020)
0.145(0.023)
7 Summary and Discussion
In this paper, investigate fair Bayes-optimal classifiers under predictive parity. We prove that when the overall performances of different protected groups vary only moderately, all fair Bayes-opting classifiers under predictive parity are GWTRs. We further propose post-processing algorithm to estimate the optimal GWTR. The derived post-processing algorithm removes the disparity in unconstrained classifiers effectively, while preserving similar test accuracy.
However, when our sufficient condition is not satisfied, the fair Bayes-optimal classifier under predictive parity may lead to within-group unfairness for the minority group. In the current literature, many algorithms directly apply penalized/constrainee optimization to impose fairness. Our negative finding, however, is important reminder that careful analysis is required before employing fairness measure. The improper use measure may result in severe unintended consequences.
Acknowledgements
Xianli Zeng would like to acknowledge the supported from Shenzhen Research Institute of Big Data (SRIBD); Edgar Dobriban supported in part by the NSF under award DMS 2046874 (CAREER) and the NSF-Simons Collaboration on the Mathematical and Scientific Foundations Deep Learning (NSF 29819 Guang Cheng was supported part by ONR grant N00014-22-1-2680 and NSF- SCALE MoDL (2134209).
References
[1] Ibrahim Alabdulmohsin. Fair classification via unconstrained optimization, 2020.
[2] Toon Calders, Faisal Kamiran, and Mykola Pechenizkiy. Building classifiers with independency constraints. In 2009 IEEE International Conference Data Mining Workshops, pages 13-18. 2009.
[3] Flavio Calmon, Dennis Wei, Bhanukiran Vinzamuri, Karthikeyan Natesan Ramamurthy, and Kush R Varshney. Optimized pre-processing for discrimination prevention. In Advances in Neural Information Processing Systems, volume 30. Curran Associates, Inc., 2017.
[4] L. Elisa Celis and Vijay Keswani. Improved adversarial learning for fair classification, 2019.
[5] Jaewoong Cho, Gyeongjo Hwang, and Changho Suh. A fair classifier using kernel density estimation. In Advances in Neural Information Processing Systems, volume 33, pages 15088 15099. 2020.
[6] A. Chouldechova. Fair prediction with disparate impact: A study of bias in recidivism prediction instruments. Big data, 5(2):153-163, 2017.
[ Exgenii Chzhen, Christophe Denis, Mohamed Hebiri, Luca Oneto, and Massimiliano Pontil. Leveraging labeled and unlabeled data for consistent fair binary classification. Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019.
10

---

[8] Sam Corbett- Davett, Emma Pierson, Avi Feller, Sharad Goel, and Aziz Huq. Algorithmic decision making and the cost of faimess. In Proceedings of the 23rd ACM SIGKDD Interna- tional Conference on Knowledge Discovery and Data Mining, pages 197-806. Association for Computing Machinery, 2017.
[9] A. Cotter, M. R. Jiang. H.and Gupta, S. Wang, T. Narayan, S. You, and K. Sridharan. Optimiza- tion with nonfdifferentiable constraints with applications to fairness, recall, churn, and other goals. Journal of Machine Learning Research, 20(172):1-55 2019.
[10] Elliot Creager, David Madras, Joern-Henrik Jacobsen, Marissa Weis, Kevin Swersky, Toniann Pitassi, and Richard Zemel. Flexibly fair representation learning by disentanglement. In Pro- ceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pages 1436-1445, PMLR, 2019.
[11] Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei. Imagenet: A large- scale hierarchical image database. In 2009 IEEE Conference Computer Vision and Pattern Recognition, pages 248-255, 2009.
[12] Jacob Devlin, Ming- Wei Chang, Kenton Lee, and Kristina Toutanova. Bert: Pre-training of deep bidirectional transformers for language understanding, 2018
[13] W. Dieterich, C. Mendoza, and T. Brennan. Compas risk scales: Demonstrating accuracy equity and predictive parity, Northpointe Inc, 7(4), 2016.
[14] Dheeru Dua and Casey Graff. UCI machine learning repository, 2017.
[15] Cynthia Dwork, Moritz Hardt, Toniann Pitassi, Omer Reingold, and Richard Zemel. Fairness through awareness. In Proceedings of the 3rd Innovations in Theoretical Computer Science Conference, ITCS 12, pages 214-226, 2012.
[16] Charles Elkan. The foundations of cost-sensitive learning. In In Proceedings of the Seventeenth International Joint Conference on Artificial Intelligence, pages 973-978, 2001.
[17] Michael Feldman, Sorelle A. Friedler, John Moeller, Carlos Scheidegger, and Suresh Venkata- subramanian. Certifying and removing disparate impact. Proceedings of the 21th ACM SIGKDD International Conference Knowledge Discovery and Data Mining, pages 259-268. Association for Computing Machinery, 2015.
[18] Benjamin Fish, Jeremy Kun, and Ádám Dániel Lelkes. A confidence-based approach for balancing faimess and accuracy. In Proceedings of the 2016 SIAM International Conference Data Mining, Miami, Florida, USA, May 5-7, 2016, pages 144-152. SIAM, 2016.
[19] A. W. Flores, K. Bechtel, and C. T. Lowenkamp. False positives, false negatives, and false analyses: A rejoinder to machine bias: There's software used across the country to predict future criminals. and it's biased against blacks. Fed. Probation, 80:38, 2016.
[20] Gabriel Goh, Andrew Cotter, Maya Gupta, and Michael Friedlander. Satisfying real-world goals with dataset constraints. In Advances in Neural Information Processing Systems, vol- ume 29, Curran Associates, Inc., 2016.
[21] Megh Gupta and Qasim Mohammad. Advances in ai and ml are reshaping healthcare, 2017.
[22] Moritz Hardt, , Eric Price, and Nati Srebro. Equality opportunity supervised learning. In Advances in Neural Information Processing Systems, volume 29, 2016.
[23] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition, 2015.
[24] Ursula Hebert-Johnson, Michael Kim, Omer Reingold, and Guy Rothblum. Multicalibration: Calibration for the (Computationaaly-ddennfff national Conference on Machine Learning, volume 80 Proceedings of Machine Learning Research, pages 1399-1948. PMLR. 10-15 Jul 2018.
masses. In Proceedings of the 35th Inter-

---

[25] J. E. Johndrow and K. Lum. An algorithm for removing sensitive information: application to race-independent recidivism prediction. The Annals of Applied Statistics, 13(1):189-22 220, 2019.
[26] Matthew Joseph, Michael Kearns, Jamie H Morgenstern, and Aaron Roth. Faimess in learn- ing: Classic and contextual bandits. In Advances in Neural Information Processing Systems, volume 29, Curran Associates, Inc., 2016.
[27] Surya Mattu Julia Angwin, Jeff Larson and Lauren Kirchner. Machine bias there's software used across the country to predict future criminals. and it's biased against blacks, 2016.
[28] Kamiran and T. Calders. Data preprocessing techniques for classification without discrimina- tion. Knowledge and Information Systems, 33(1):1-33) 2012.
[29] Preethi Lahoti, Krishna P. Gummadi, and Gerhard Weikum. ifair: Learning individually fair data representations for algorithmic decision making. In 35th IEEE International Conference on Data Engineering, ICDE 2019, Macao, China, April 8-11, 2019, pages 1334-1345. IEEE, 2019.
[30] Joshua K Lee, Yuheng Bu, Deepta Rajan, Prasanna Sattigeri, Rameswar Panda, Subhro Das. and Gregory W Wornell. Fair selective classification via sufficiency. In Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pages 6076-6086. PMLR, 18-24 Jul 2021.
[31] Lydia T. Liu, Max Simchowitz, and Moritz Hardt. The implicit fairness criterion of uncon- strained learning. In Proceedings of the 36th International Conference on Machine Learning. volume 97 of Proceedings of Machine Learning Research, pages 4051-4060. PMLR, 09-15 Jun 2019.
[32] Ziwei Liu, Ping Luo, Xiaogang Wang, and Xiaoou Tang. Deep learning face attributes in the wild. In 2015 IEEE International Conference on Computer Vision (ICCV), pages 3730-3738, 2015.
[33] Christos Louizos, Kevin Swersky, Yujia Li, Max Welling, and Richard S. Zemel. The variational fair autoencoder. In 4th International Conference on Learning Representations, ICLR 2016, San Juan, Puerto Rico, May 2-4, 2016, Conference Track Proceedings, 2016.
[34]
Kristian Lum and James Johndrow. statistical framework for fair predictive algorithms, 2016.
[35] David Madras, Elliot Creager, Toniann Pitassi, and Richard Zemel. Learning adversarially fair and transferable representations. Proceedings of the 35th International Conference on Machine Learning. volume 80 of Proceedings of Machine Learning Research, pages 3384-3393.
PMLR, 10-15 Jul 2018
[36] Aditya Krishna Menon and Robert C Williamson. The cost of faireess in binary classification. Proceedings of the 1st Conference on Fairness, Accountability and Trunspurency, volume 81 of Proceedings of Machine Learning Research, pages 107-118. PMLR, 23 Feb 2018.
[37] John W Miller, Rod Goodman, and Padhraic Smyth. On loss functions which minimize to conditional expected values and posterior probabilities. IEEE Transactions on Information Theory, (9(:):1400 4404-4408, 1993.
[38] Harikrishna Narasimhan. Learning with complex loss functions and constraints. In Proceedings of the Twenty-First International Conference on Artificial Intelligence and Statistics, volume 84 of Proceedings of Machine Learning Research, pages 1646-1654. PMLR, 2018.
[39] Geoff Pleiss, Manish Raghavan, Felix Wu, Jon Kleinberg, and Kilian Q Weinberger. On fairness and calibration. In Advances in Neural Information Processing Systems, volume 30. Curran Associates, Inc., 2017.
[40] Vikram V. Ramaswamy, Sunnie S. Y. Kim, and Olga Russakovsky. Fair attribute classification through latent space de-biasing. 2021 IEEF/CVF Conference on Computer Vision and Pattern Recognition (CVPR), pages 9297-9306. 2021.
12

---

[41] Anian Ruoss, Mislav Balunovic, Mare Fischer, and Martin Vechev. Learning certified in- dividually fair representations. In Advances Neural Information Processing Systems 33, 2020.
[42] P. Sattigeri, S. C. Hoffman, V. Chenthamarakshan, and K. R. Varshney. Fairness gan: Generating datasets with fairesss properties using a generative adversarial network. IBM Journal of Research and Development, 63(4/5):3:1-3:9 2019.
[43] Nicolas Schreuder and Evgenii Chzhen. Classification with abstention but without disparities. In Proceedings of the Thirty-Seventh Conference Uncertainty in Artificial Intelligence, volume 161 of Proceedings of Machine Learning Research, pages 1227-1236. PMLR, 27-30 Jul 2021.
[44] Karen Simonyan and Andrew Zisserman. Very deep convolutional networks for large-scale image recognition, 2014.
[45] Ilya Sutskever, Oriol Vinyals, and Quoc V Le. Sequence to sequence learning with neural networks. In Advances in Neural Information Processing Systems, volume 27. Curran Associates, Inc., 2014.
[46] Christian Szegedy, Wei Liu, Yangqing Jia, Pierre Sermanet, Scott Reed, Dragomir Anguelov, Dumitru Erhan, Vincent Vanhoucke, and Andrew Rabinovich. Going deeper with convolutions. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), June 2015.
[47] Christian Szegedy, Vincent Vanhoucke, Sergey Ioffe, Jon Shlens, and Zbigniew Wojna. Re- thinking the inception architecture for computer vision. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), June 2016.
[48] Songül Tolan, Marius Miron, Emilia Gómez, and Carlos Castillo. Why machine learning may lead to unfairness: Evidence from risk assessment for juvenile justice in catalonia. In Proceedings of the Seventeenth International Conference on Artificial Intelligence and Law, ICAIL 2019, Montreal, QC. Canada, June 17-21, 2019, pages 83 92. ACM, 2019.
[49] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, ukasz Kaiser, and Illia Polosukhin. Attention is all you need. In Advances in Neural Information Processing Systems, volume 30. Curran Associates, Inc., 2017.
[50] Christina Wadsworth, Francesca Vera, and Chris Piech. Achieving faimess through adversarial learning: application to recidivism prediction, 2018.
[51] Zeyu Wang, Klint Qinami, loannis Karakozis, Kyle Genova, Prem Nair, Kenji Hata, and Olga Russakovsky. Towards fairness in visual recognition: Effective strategies for bias mitigation. In IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), 2020.
[52] Depeng Xu, Yongkai Wu, Shuhan Yuan, Lu Zhang, and Xintao Wu, Achieving causal fairness through generative adversarial networks. In Proceedings of the TiwentyFFihtth International Joint Conference on Artificial Intelligence, IJCAI-19, pages 1452-1458. International Joint Conferences on Artificial Intelligence Organization, 2019.
[53] Depeng Xu, Shuhan Yuan, Lu Zhang, and Xintao Wu. Fairgan: Fairness-aware generative adversarial networks. In 2018 IEEE International Conference on Big Data (Big Data), pages 570-575, 2018
[54] Depeng Xu, Shuhan Yuan, Lu Zhang, and Xintao Wu. Fairgan<sup>+<<sup>> Achieving fair data generation and classification through generative adversarial nets. In 2019 IEEE International Conference on Big Data (Big Data), pages 1401-1406, 2019.
(55) Zhilin Yang, Zihang Dai, Yiming Yang, Jaime Carbonell, Russ R Salakhutdinov, and Quoc V Le. Xlnet: Generalized autoregressive pretraining for language understanding. In Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019.
[56] Muhammad Bilal Zafar, Isabel Valera, Manuel Gomez Rodriguez, and Krishna P. Gummadi. Fairness beyond disparate treatment and disparate impact: Learning classification without disparate mistreatment. In Proceedings of the 26th International Conference on World Wide Web, pages 1171-1180 International World Wide Web Conferences Stecring Committee, 2017.
13

---

[57] Rich Zemel, Yu Wu, Kevin Swersky. Toni Pitassi, and Cynthia Dwork. Learning fair representa- tions. In Proceedings of the 30th International Conference on Machine Learning, volume 28 of Proceedings of Machine Learning Research, pages 325-333. PMLR, 2013.
[58] Xianli Zeng, Edgar Dobriban, and Guang Cheng. Bayes-optimal classifiers under group faimesss 2022.
[59] Brian Hu Zhang, Blake Lemoine, and Margaret Mitchell. Mitigating unwanted biases with adversarial learning. In Proceedings of the 2018 AAAI/ACM Conference on AI, Ethics, and Sociery, AIES 18, pages 335-340. Association for Computing Machinery, 2018.
[60] Jieyu Zhao, Tianlu Wang, Mark Yatskar, Vicente Ordonez, and Kai- Wei Chang. Men also like shopping: Reducing gender bias amplification using corpus-level constraints. In Proceedings of the 2017 Conference on Empirical Methods in Natural Language Processing, pages 2941-22 2941-2951,
2017.
14


Reviews:
[{"review_id": "sLuTRtCoi5", "reviewer": "Reviewer_aL3t", "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.", "questions": "Section 1\n1. 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.\n2. line 34: this may be my ignorance, but why is GWTR a *minimal* requirement for within-group fairness? Could there be any stronger requirement?\n3. 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.\n4. 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\n5. 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?\n\nSection 2\n6. 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?\n7. 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?\n8. line 109: \"and the later tries to minimize\". later should be latter.\n\nSection 3\n9. 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.\n\nSection 4\n10. 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?\n11. 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.\n12. 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.\n\nSection 5\n13. 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?\n14. 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.\n", "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.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths: \n* 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.\n\nWeaknesses: \n* 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. \n* 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\nand 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.\n* 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?\n* 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. \n* Details such as choice of cost parameter c, thresholds t, etc. could be made clearer.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "ZvhPImbcUMZ", "reviewer": "Reviewer_m8AG", "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.", "questions": "### Q1: can authors share some insights regarding the potential necessary condition (or, the difficulty behind such analysis)?\n\n(as detailed in Section `Strengths and Weakness`)\n\n### Q2: w.r.t. the term \"within-group fairness\"\n\nWhile 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.\n\n### Q3: Equation 3\n\nIs 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.\n\n### Q4: w.r.t. recommended action in Algorithm 1\n\nIn 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. \n\nMinor typo: line 310 [man] algorithms", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "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.\n\nThe 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.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "RDA5f39acyk", "reviewer": "Reviewer_AKkJ", "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.", "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.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "\n(Strengths)\n- Clearly written and technically sound.\n- The condition of forming the Bayes-optimal classifier as a GWTR is interesting and crucial for understanding the predictive parity constraint.\n- The authors give a reasonable algorithm for learning a GWTR while ensuring predictive parity.\n\n(Weakness)\n- 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.\n- The result is just a sufficient condition is not a necessary and sufficient condition. The complete characterization of this phenomenon is still unfulfilled.\n- Empirical comparison is somewhat weak. It lacks comparison with the existing sufficiency-based fair learning techniques.\n\n\nThis 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.\n\n\nThe 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.\n\n\nThe 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\n- C. Jung et al. Moment Multicalibration for Uncertainty Estimation. COLT2021.\n- E. Shabat et al. Sample Complexity of Uniform Convergence for Multicalibration.\n\nI 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.\n\nIn 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:\n- U. Hebert-Johnson et al. Multicalibration: Calibration for the (Computationally-Identifiable) Masses. ICML2018.\n\n\nMinor issues:\n- 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?\n- Line 542 in the appendix: The definitions of $T_0$ and $T_1$ looks the same. Maybe, it is typo.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ["I don’t know"]}, "extra_text": {}}, {"review_id": "9k1daA_AtDm", "reviewer": "Reviewer_rrxc", "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.", "questions": "1. This paper should provide more reasons why the proposed method is suitable for this problem.\n2. I would suggest adding more introduction and discussion about the GWTR.\n3. This paper should explore baselines to demonstrate the effectiveness of the proposed method.\n", "limitations": "None", "rating": 4, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths**\n1.The fairness studied in the paper is interesting. The predictive parity is of practical significance.\n2. 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.\n3. This paper is easy to follow.\n\n**Weaknesses**\n1. The motivation of this paper is not clear. \n    - 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.  \n    - 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. \n    - The proposed methods FairBayes-DPP is not well motivated. This paper should provide more reasons why the proposed method is suitable for this problem.\n2. 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.\n3. 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.\n\nOverall, 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.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ["I don’t know"]}, "extra_text": {}}]

Author rebuttal:

Decision: Accept