Attainability and Optimality: The Equalized-Odds Fairness Revisited
Authors: Zeyu Tang
Kun Zhang
Venue:  (2021)
Keywords: algorithmic fairness

Abstract: Fairness of machine learning algorithms has been of increasing interest. In order to suppress or eliminate discrimination in prediction, various notions as well as approaches to impose fairness have been proposed. However, in different scenarios, whether or not the chosen notion of fairness can always be attained, even if with unlimited amount of data, is not well addressed. In this paper, focusing on the Equalized Odds notion of fairness, we consider the attainability of this criterion, and furthermore, if attainable, the optimality of the prediction performance under various settings. In particular, for classification with a deterministic prediction function of the input, we give the condition under which Equalized Odds can hold true; if randomized prediction is acceptable, we show that under mild assumptions, fair classifiers can always be derived. Moreover, we prove that compared to enforcing fairness by post-processing, one can always benefit from exploiting all available features during training and get better prediction performance while remaining fair. However, for regression tasks, Equalized Odds is not always attainable if certain conditions on the joint distribution of the features and the target variable are not met. This indicates the inherent difficulty in achieving fairness in certain cases and suggests a broader class of prediction methods might be needed for fairness.

Under review as a conference paper at ICLR 2021
ATTAINABILITY AND OPTIMALITY: THE EQUALIZED-ODDS FAIRNESS REVISITED
Anonymous authors Paper under double-blind review
ABSTRACT
Fairness of machine learning algorithms has been of increasing interest. In order to suppress or eliminate discrimination in prediction, various notions as well as approaches impose fairness have been proposed. However, different scenar- ios, whether not the chosen notion of fairness can always be attained, even if with unlimited amount of data, is not well addressed. In this paper, focusing on the Equalized Odds notion of fairness, we consider the attainability of this criterion, and furthermore, attainable, the optimality of the prediction performance under various settings. In particular, for classification with deterministic prediction function of the input, we give the condition under which Equalized Odds can hold true; if randomized prediction is acceptable, we show that under mild assump- tions, fair classifiers can always be derived. Moreover, we prove that compared enforcing fairness by post-processing, one can always benefit from exploiting all available features during training and get better prediction performance while remaining fair. However, for regression tasks, Equalized Odds is not always at- tainable if certain conditions on the joint distribution of the features and the target variable are not met. This indicates the inherent difficulty in achieving fairness certain cases and suggests a broader class of prediction methods might be needed for fairness.
INTRODUCTION
As machine learning models become widespread in automated decision making systems, apart from the efficiency and accuracy of the prediction, their potential social consequence also gains increasing attention. To date, there is ample evidence that machine learning models have resulted in discrimina- tion against certain groups of individuals under many circumstances, for instance, the discrimination in ad delivery when searching for names that can be predictive of the race of individual (Sweeney, 2013); the gender discrimination in job-related ads push (Datta et al., 2015); stereotypes associated with gender in word embeddings (Bolukbasi et al., 2016); the bias against certain ethnicities in the assessment of recidivism risk (Angwin et al., 2016).
The call for accountability and faireess in machine learning has motivated various (statistical) no- tions of fairness. The Demographic Parity criterion (Calders et al., 2009) requires the independence between prediction (e.g., of classifier) and the protected feature (sensitive attributes of an indi- vidual, e.g., gender, race). Equalized Odds (Hardt et al., 2016), also known as Error-rate Balance (Chouldechova, 2017), requires the output of model be conditionally independent of protected feature(s) given the ground truth of the target. Predictive Rate Parity (Zafar et al., 2017a), on the other hand, requires the actually proportion of positives (negatives) the original data for positive (negative) predictions should match across groups (well-calibrated).
On the theoretical side, results have been reported regarding relationships among fairness notions. It has been independently shown that if base rates of true positives differ among groups, then Equal- ized Odds and Predictive Rate Parity cannot be achieved simultaneously for non-perfect predictors (Kleinberg al., 2016; Chouldechova, 2017). Any two out of three among Demographic Parity, Equalized Odds, and Predictive Rate Parity are incompatible with each other (Barocas et al., 2017). At the interface of privacy and faimess, the impossibility of achieving both Differrnntial Privacy (Dwork et al.. 2006) and Equal Opportunity (Hardt et al., 2016) while maintaining non- aon-trivial accu- racy is also established (Cummings et al., 2019).

---

Under review as a conference paper at ICLR 2021
In practice, one can broadly categorize computational procedures to derive fair predictor into three types: pre-processing approaches (Calders et al., 2009; Dwork et al.. 2012: Zemel et al., 2013; Zhang et al., 2018; Madras et al., 2018; Creager et al., 2019; Zhao et al., 2020), in in-processing ap- proaches (Kamishima et al., 2011 I; Pérez-Suay et al., 2017; 7afar et al., 201 7a;b; Donini et al., 2018; Song et al., 2019; Mary al., 2019; Baharlouei et al., 2020), and post-processing approaches (Hardt et al., 2016; Fish et al., 2016; Dwork et al., 2018). In accord with the fairness notion of interest, a pre-processing approach first maps the training data tory information between protected feature and target, and then pass on the data to make prediction. In direct contrast, poss-procsssing approach treats the off off-th predictor(s) as uninterpretable black-box(es), and imposes fairness by outputting a function of the original prediction. For in- processing approaches, various kinds of regularization terms are proposed so that one can optimize the utility function while suppressing the discrimination at the same time. Approaches based on estimating/bounding causal effect between the protected feature and final target have also been pro- posed (Kusner et al., 2017: Russell et al., 2017; Zhang et al., 2017; Nabi & Shpitser, 2018; Zhang & Bareinboim, 2018; Chiappa, 2019; Wu et al., 2019).
transformed space to remove discrimina-
Focusing the Equalized-Odds criterion, although various approaches have been proposed to im- pose the fairness requirement, whether or not it is always attainable is not well addressed. The attainability of Equalized Odds, namely, the existence of the predictor that can score zero violation of fairness in the large sample limit, is an asymptotic property of the fairness criterion. This char- acterizes completely different kind of violation of fairness compared the empirical error bound of discrimination in finite-sample cases. If utilizing a "fair" predictor which is actually biased, the discrimination would become snake in the grass, making hard to detect and eliminate. Actually, as we illustrate in this paper, Equalized Odds is not always attainable for regression and even clas- sification tasks, if we use deterministic prediction functions. This calls for alternative definitions in the same spirit as Equalized Odds that can always be achieved under various circumstances. Our contributions are mainly:
For regression and classification tasks with deterministic prediction functions, we show that Equalized Odds is not always attainable if certain (rather restrictive) conditions on the joint distribution of the features and the target variable are not met.
Under mild assumptions, for binary classification we show that if randomized prediction is taken into consideration, one can always derive non-trivial Equalized Odds classifier.
Considering the optimality of performance under fairness constraint(s), when exploiting all available features, we show that the predictor derived via an in in-processing approach would always outperform the one derived via post-processing approach (unconstrained optimization followed by a post-processing step).
PRELIMINARIES
In this section, we first illustrate the difference between prediction fairness and procedure fairness, and then, we present the formal definition of Equalized Odds (Hardt et al., 2016).
2.1 HIERARCHY OF FAIRNESS
Before presenting the formulation of fairness, it important to see the distinction between different levels of faireess when discussing fair predictors. When evaluating the performance of the proposed fair predictor, it is a common practice to compare the loss (with respect to the utility function of choice, e.g., accuracy for binary classification) computed on target variable and the predicted value. There is an implicit assumption lying beneath this practice: the generating process of the data, which is just describing real-world procedure, is not biased in any sense (Danks & London, 2017). Only when we treat the target variable (recorded in the dataset) as unbiased can we justify the practice of loss evaluation and the conditioning on target variable when imposing fairness (as shall see in the definition of Equalized Odds in Equation 1).
One may consider music school admission example. The music school committee would decide if they admit a student to the violin performance program based on the applicant's 's personal informa- tion, educational background, instrumental performance, and When evaluating whether not
2

---

Under review as a conference paper at ICLR 2021
the admission is "fair", there are actually two levels of fairess. First, based the information hand, did the committee evaluate the qualification of applicants without bias (How committee eval- uate the applicants)? And second, is committee's 's procedure of evaluating applicants qualification reasonable (How other people view the evaluation procedure used by the committee)?
In this paper, consider prediction faimesss namely, assuming the data recorded is unbiased, the prediction (made with respect to current reality) itself should not include any biased utilization of information. The fairness with respect to the data generating procedure well as the potential future influence of the prediction are beyond the scope of this paper.
2.2 EQUALIZED-ODDS FAIRNESS
Hardt et al. (2016) proposed Equalized Odds which requires conditional independence between prediction and protected feature(s) given ground truth of the target. Let us denote the protected feature by A, with domain of value A, additional (observable) feature(s) by X, with domain of value X, target variable by Y, with domain y (not necessarily fair) predictors by Y, and fair predictors
by Y. Srqualized-Odds fairness requires
Y L A Y.
(1)
For classification tasks, one can conveniently use the probability distribution form:
Va E A:: =t = a, y) = p( t Y = y), or more concisely, PAJAY (1.,),)) = Py (1 11).
(2)
For better readability, we also the formulation in Equation in cases without ambiguity. In the context of binary classification (Y = {))1}), Equalized Odds requires that the True Positive Rate (TPR) and False Positive Rate (FPR) of each certain group match population positive rates. Throughout the paper, without loss of generality we assume there is only one protected feature for the purpose of simplifying notation. However, considering the fact that the protected feature can be discrete (e.g., race, gender) or continuous (c.g., the ratio of ethnic group in the population for certain district of city), we do not assume discreteness of the protected feature. Due the space limit, we will focus on the illustration and implication of our results and defer all the proofs to the appendix.
3 FAIRNESS IN REGRESSION MAY NOT BE ATTAINED
In this section we consider the attainability of Equalized Odds for regression tasks, namely, whether or not is possible to find a predictor that is conditionally independent from the protected fea- ture given true value of the target. For linearly Gaussian cases, can attain Equalized Odds by constraining zero partial correlation between the prediction and the protected feature given target variable (Woodworth al., 2017). Various regularization terms have also been proposed to suppress discrimination when predicting a continuous target (Berk et al., 2017; Mary et al., 2019). However, whether or not one can always achieve O-discrimination for regression, even if with an unlimited amount of data, is not clear yet.
"fair" predictors are deployed without carefully checking the attainability of fairness, the discrim- ination would become a hidden hazard, making it hard to detect and climinate. Actually we will show in this section, even in the simple setup of linearly correlated continuous data, Equalized Odds is not always attainable.
3.1 UNATTAINABILITY OF EQUALIZED ODDS IN LINEAR NON- GAUSSSANN REGRESSION
As stated in Section 2. I, in this paper we consider prediction fairness, and therefore any possible bias introduced by the data generating procedure itself is beyond the scope of the discussion. Consider the situation where the data is generated as following (H is not measured in the dataset):
X = q + Ex,
H bA + En,
(4)
Y = ex + dHl + Ey,
3

---

Under review as a conference paper at ICLR 2021
where (A, Ex, EH Ey) are mutually independent. In fact, if at most one of Ex and E := Ey + dEH is Gaussian, then any linear combination of and X with con-zero coefficients will not be conditionally independent from A given Y. meaning that it not possible to achieve Equalized-Odde fairness. Let Z be a linear combination of A and X, i.e., = a + 3X = (a + q A + Ex, with linear coefficients and 3, where B * 0. In Theorem 3.1, we present the general result in linear non-Gaussian cases, where one cannot achieve the conditional independence between Z and A given Y.
Theorem 3.1. (Unattainability of Equalized Odds in the Linear Non-Gaussian Case)
Assume that feature X has a causal inftuence on Y, i.e., C + 0 in Equation 4, and that the protected feature A and Y are not independent, i.e., qc + bd + O. Assume PEx and PE are positive l. PA. fz == logPex pxx, and fs. == log Pg. Further assume that f2 and fs are third-order differentiable. Then if at most of Ex and E is Gaussian, Z is always conditionally dependent on A given Y.
Let fi == IogPA.
From Theorem 3.1, we see that in linear non-Gaussian cases, any non-zero linear combination of the feature (which is a deterministic function of the input) will not satisfy Equalized Odds. One may wonder whether Equalized Odds can be achieved by nonlinear regression, instead of a linear model. Although a proof with general nonlinear models is rather complicated, our simulation results in Sec- tion 5.1 strongly suggest that the unattainability of Equalized Odds persists in nonlinear regression cases.
In light of the unattainability of Equalized Odds for prediction with deterministic functions of A and X, it is desirable to develop general, nonlinear prediction algorithms to produce probabilistic prediction (i.e., with a certain type of randomness in the prediction). One possible way follows the framework of Generative Adversarial Networks (GANs) (Goodfellow al., 2014): standard Gaussian noise, in addition to AA and X, as input, such that the output will have a specific type of randomness. The parameters involved are learned by minimizing prediction error and en- foreing Equalized Odds on the "randomized" output at the same time. Given that this approach is not essential to illustrate the claims made in this paper and that theoretical properties of such non- linear regression algorithms with randomized output are not straightforward to establish, this is left as future work.
random
FAIRNESS IN CLASSIFICATION
In this section, consider the attainability of Equalized Odds for binary classifiers (with deter- ministic or randomized prediction function), and furthermore, if attainable, the optimality of per- formance under the fairness criterion. Admittedly, is already pointed out by Woodworth et al. (2017), we generally cannot have O-discriminatory predictors with a finite number of samples; in- stead, one should consider imposing 5-discrimination in practice (6 is the violation of Equalized Odds). However, this does not guarantee nor rule out the possibility of attaining O-discrimination on population when the sample size goes to infinity.
4.1 CLASSIFICATION WITH DETERMINISTIC PREDICTION
We begin with considering cases when the classification is performed by a deterministic function of the input. In particular, we derive the condition under which Equalized Odds can possibly hold true.
Theorem 4.1. Assume that the protected feature A and Y are dependent and that their joint proba- bility P(A,Y) Y) (for discrete A) or joint probability density p(A, Y) (for continuous A) is positive for every combination of possible values of and Y. Further assume that Y is not fully determined by A, and that there are additional features X that are not independent Y. Y Let the output of the clas- sifier Y be deterministic function f A x X + Y. Let S = {a Rr X s.I. (a,xx) = t}, and s(t) x|a := {x f(),x)= = t}. Equalized Odds holds true if and only if the following two conditions
satisfied:
(0) VI VIEY: 500 A.
(ii) V Va, a' E A (for continuous X, replace summation with integration accordingly): PXJAY (x) a' a',y).
Σ 2es( PxJAr (x a,y) -xes(e) Xia! Xla
4

---

Under review as a conference paper at ICLR 2021
Let us take a look the two conditions. Condition (i) says that within each class determined by the classification function f. A should be able to take all possible values in A. While condition (i) is already pretty restrictive, condition (ii) specifies even stronger constraint on the relation between the conditional probability Px (araa, y) (or the conditional probability density Px Ay y) for continuous X) and the set s()) (which determined by the function ʃ). By definition s(t) has X|a
X/a
X|a s 0; (2) for any fixed value of a A. Ulgy S X. Condition (ii) says that the set ((() and the conditional distribution Ay y) are coupled in some specific way so that they happen to satisfy the specified equality.
following properties: (1) for any fixed value of E A, if t + t', then ((t)
In special cases when X TT A Y, if f is function of only X, condition (ii) would always hold true. In general situations, if there does not exist any subsets Ka Ke S X for different values of a, a' E A such that ΣxEk, Pxeay (z|a, y) Ezek,' (xjav(z]aa' lllla.... y), then condition (ii) can never hold true (i.e., we cannot find a deterministic function f(A, X) that satisfies Equalized Odds). Generally speaking, in order score a better classification accuracy, one would like make P (tla,,>) .² as close as possible to PYI (y/a, I), and the set s(t) not strictly coupled, condition (ii) would be violated.
Xla and (z)a, y) are
4.2 CLASSIFICATION WITH RANDOMIZED PREDICTION
In this section, we consider cases when randomized prediction is acceptable, namely, the classifier would output class labels with certain probabilities. We first derive the relation between positive rates (TPR and FPR) of binary classifiers before and after the post-processing step, i.e., Yap (the unconstrainedly optimized classifier) and Ypost (the fair classifier derived by post-processing Yopt). and show that under mild assumptions, one can always derive non-trivial moualized-Odee (on population level) Y Ypoc via a post-processing step. Then, from the ROC feasible area perspective, we prove that post-processing approaches are actually equivalent to in- un-processing approaches but with additional "pseudo" constraints enforced. Therefore, using the same loss function, post-processing approaches can perform no better than in-processing approaches.
4.2.1 THE POST- PROS--SREESSING STEP
The post-processing step of a predictor Ý (here we drop the subscript if without ambiguity) only utilizes the information in the joint distribution (A,YÝ)) A fair predictor Ypost derived via post- processing step. for instance, the shifted decision boundary (Fish al., 2016). the derived predictor (Hardt et al., 2016), or the (monotonic) joint loss optimization over decoupled classifiers (Dwork et al., 2018), is then fully specified by a (possibly randomized) function of (A, Y). This implies the conditional independence Ypost IL Y A.Y. Since we can denote the positive rates of Ý as PyIAY (1|a, y)', positive rates of Y (here we drop the subscript for readability) as PYIAY (1/a |a, y). the relation between positive rates of binary classifiers before and after a post-processing step would satisfy (for every a E A, u, y E V)):
PYJAY (1/a v) Evey (6()) (ulaa y), where B(()) := P( = - u).
=
(5)
Notice that Equation 5 is just a factorization of probability under the conditional independence (between Ypon and given A and Y). Therefore, post-processing an existing predictor boils down to optimizing parameters (for discrete A) functions (for continuous A) a(ah)
4.2.2 ROC FEASIBLE AREA
On the Receiver Operator Characteristic (ROC) plane, a two-dimensional plane with horizontal axis denoting FPR and vertical axis denoting TPR, the performance of any binary predictor y (not
Recall that (ulay,ua, w) = P( u A a, Y v). When = 1, Pe (1|a, v) P( = 1
A = a, Y y) represents positive rates of 8; When a = 0, Prlar (0/a, y) = P(F = 0 A = a, Y =)) represents positive rates of 1 & (the classifier that flips the prediction of 9).
5

---

Under review as a conference paper at ICLR 2021
10
0.8
P18 1
A.
0.4
0.0
2.02
00
1..00
2,25
0.75
100
1000
0.25
075
100
P(Y
00
(9) Diserote protected Renture (b) Continaous protected feature
(6) Fezssible arens Yuu Fpose and Eape
(6) (2)))) with "pscudo" constraints
Figure I: ROC feasible area illustrations. Panels (a)-(b): Attainability of Equalized Odds for bi- nary classifiers with discrete or continuous protected feature. Panels (c)-(d): ROC feasible areas comparison between (2(Ym), 2((ppm)), ((Vopu). and (2(Ym))
necessarily fair one) with certain value of protected feature A a corresponds point Yo (Y) (FPR, TPR) on the plane. Denote each coordinate according to the value of as Yay (Y):
Va (a (760 (Y), 7aa (P)) = (PyJAr (1)a, 0), PAY (1/a, 1)).
Further denote the corresponding convex hull of & on the ROC plane as Ca using vertices:
C. C convhull (0, (Y),, (a V), (1,
and then, already stated in Hardt al. (2016). the (FPR, TPR) pair corresponding to post- processing predictor falls within (including the boundary of) C.a (V).
Definition 4.1. (ROC feasible area) The feasible area of a predictor (2YY), specified by the hypothesis space of available predictors Ý. is the set containing all attainable (FPR, TPR) pairs by the predictor on the ROC plane satisfying Equalized Odds.
In Hardt et al. (2016) proposed that the post-processing fair predictor can derived by solving a linear programming problem on the ROC plane. However, it is not clearly stated whether or not such problem always has a non-trivial solution. Following Hardt et al. (2016), we analyze the relation between the (FPR, TPR) pair of predictors of the non-trivial Equalized- Odds predictor. Actually as we shall see in Theorem 4.2, under mild assumptions, an Equalized-O0 -ddds predictor Ypost derived via post-processing y (a (rediictor optimized without fairness concern) always has non-empty ROC feasible area.
the ROC plane and formally establish the existence
Theorem 4.2. (Attainability of Equalized Odds)
Assume that the feature X. is not independent from Y, and that Y a function of and X. Then for binary classification, if Y non-trivial predictor for Y. there always least one non-trivial (possibly randomized) predictor Ypost derived by post-processing Y that can attain Equalized Odds:
2(Ypor)) pon) 0.
Here Yposs is possibly randomized function of only A and Ý, trading off TPR with FPR across groups with different value protected feature. From the panels (a) and (b) Figure we can also see that 12(Poss), the ROC feasible area of Yposs is the intersection Q2 (P), indicating that although Equalized Odds is attained, the performance of Yposs is always worse than the weakest performance across different groups, which is obviously suboptimal.
4.2.3 OPTIMALITY PERFORMANCE AMONG FAIR CLASSIFIERS
In this subsection we discuss the optimality of performance of fair classifiers derived via different approaches. Considering the fact that recent efforts to impose Equalized Odds in the pre-processing manner (Madras et al., 2018; 8 Zhao et al., 2020) approach the problem from representation learning perspective, where the main focus is to learn fair representations that the same time preserve sufficient information from the original data, we omit pre-prreeeee processoc approaches from the discussion and compare the performance of post-process procesrccssiigg and in-processing fair classifiers.

---

Under review as a conference paper at ICLR 2021
-10
200 give (1) on diortvatio
glees 1-022
gaee C 9.g
Liiare Listtrr cueriaatie
Noniinaar Canmrtan durshation
(d) Nowimaora Careruz dianhattoo
Figure 2: Illustration of unattainable Equalized Odds for regression tasks. Panel (a)-(b): Linear gression on the data generated with linear transformations and non-Gaussian distributed exogenous terms (following Laplace, Uniform distribution respectively). Panel (c)-(d): Nonlinear regression with a neural net regressor (Mary et al., 2019) on the data generated with nonlinear transforma- tions and Gaussian exogenous terms. We can observe obvious dependencies between Y and A on small interval of Y. This indicates the conditional dependency between Y and A given Y, i.e., the Equalized Odds is not achieved.
Admittedly, when only the information about joint distribution of (A,Y, Y) available, post- processing is the best we can do. However, this is not the case when we have access to additional available features during training. For any predictor specified by parameters 0 E e, the derivation of the in-processing fair predictor Yn and the unconstrained statistical optimal predictor V take following forms respectively:
min BEB
E[ [IU X:0),
min BEB where
(;; POR = f(A,X,))
S.L.
( a,y) = P (1 v)
(8)
Yn (A,);;0) It is natural to wonder, now that one can always directly solve for Ynn from Equation 8, how is it related to Ypost. which is derived by post post-processing the Yop solved from Equation 9? Interestingly, although Y,_ and Ypost are solved separately using different constrained optimization schemes, one can draw connection between them by utilizing Yopt as bridge and reason about the relation summarize in the following theorem.
where
between their ROC feasible areas ?(Y..) and 1( (wap))),
Theorem 4.3. (Equivalence between ROC feasible areas)
Let (( pas)) denote the ROC feasible area specified by the constraints enforced Y post. Then (Ypp is identical to the ROC feasible area ((Yr that is specified by the following set of con- straints:
(i) constraints enforced on Yo.:
(i)) additional "pseudo" constraints: Va A, (00 = -0 2 a, X = P(X = x A Y
-8(1) where
a(a) EZEx
y opr u).
As we can see from panels (c) and (d) of Figure 1, if the additional "pseudo" constraints are intro- duced when optimizing Y; we have S2(Y,)) 2 ?((poss) ?(Y())) The ROC feasible area is fully specified by the hypothesis class and the fairness constraint. Therefore, with the same objective function and fairness constraint, the fair classifier derived from an in-processing approach always outperforms the one derived from a post-processing approach. We can see that when we have ac- cess to additional features and choose post-processing approach, we lose performance (compared to Y.T) by unintentionally introducing "pseudo" constraints during optimization. These "pseudo" constraints actually offset the henefit of utilizing additional features (in the hope to score a better performance while remaining fair).
EXPERIMENTS
In order to intuitively illustrate the claims, we provide numerical results for various settings. We first present the result for (linear non-Gaussian and nonlinear) regression tasks when Equalized Odds is not attained. We demonstrate the dependence between the prediction and the protected feature given true value of the target variable. Then for classification tasks compare the performance of several

---

Under review as a conference paper at ICLR 2021
Adalt (Gender)
Adult (Race)
Bank
COMPAS
1156
German Credit
*
0.35
Teet
1.16
9.06
0.34
0,00
0.05
2.64 0.06 8.66
300
0.04
0.6 0.12
0000 8,02 3.04 RUS 0,63 0.10
(.0) 0.03 0.10 0.18
0.20
0.20
0,00
0.26 I. 6.20 0:25
EOdds Viclation
EOlds Viclation
EDdds Villtion
EOdd Vidlation
EOods Vislation
Logisic Regression
Banarlouei et al 2020
Rezael 2000
Aggonoal et al. 2010
+
Zafor
20172
36
Hardt ot al 2016
0.19
Adult (Gender)
0..8
Adull (Rane)
Rank
COMPAS
0.34
German Credit
0.33
0.17
0.30
(:95
2 0.16
0.31
0.15
0.55
0.32
0.15
0:18
FOppo Vialation
EDpao Vislation
FOppo Vielation
POppo Volation
EOppo
Log Regrovice
Eduricani 2009
Puzao et 2008
Agannel et 26,3
Zale dt 2017>
Hast at 2016
Durei al 2038
Figure 3: Results for classification with Equalized Odds/Equal Opportunity criterion.
existing methods in the literature on the Adult, Bank, COMPAS, and German Credit data sets. The detailed description of the data sets is available in the appendix.
5.1 REGRESSION WITH LINEAR NON-GAUSSIAN AND NONLINEAR DATA
In Section 3.1 we showed the unattainability of Equalized Odds for regression with linear non- Gaussian data, Although proof for similar results in nonlinear cases does not seem straightforward, as strongly suggested by numerical illustrations, the unattainability of Equalized Odds persists in nonlinear regression cases. In Figure 2 we present scatter plots of Y versus A for Y in small (compared to its support) interval, for linear non-Gaussian as well as nonlinear regression cases.
For linear cases, the data is generated as stated in Equation 4, with non-Gaussian distributed exoge- nous terms (Ex, EH, and Ey). We use linear regression with the Equalized Correlations constraint (Woodworth et al., 2017), weaker notion of Equalized Odds for linearly correlated data, as the predictor. For nonlinear cases, the data is generated using a similar scheme but with nonlinear transformations (e.g.. combinations of sin(.), sig()).log()) and polynomials) and Gaussian distributed ex- ogenous terms. We use neural net regressor with an Equalized Odds regularization term (Mary et al., 2019) to perform nonlinear fair regression. we can see Figure 2, for nonlinear regression tasks, Equalized Odds may not be attained even if every exogenous term is Gaussian distributed.
5.2 FAIR CLASSIFICATION
In Figure 3, we compare the performance under Equalized Odds of multiple methods proposed the literature. Hardt al. (2016) propose post-processing approach where the prediction random- ized to minimize violation of fairness; Zafar et al. (2017a) use a covariance proxy measure as the regularization term when optimizing classification accuracy; Agarwal et al. (2018) take the reduc- tions approach and reduce fair classification into solving sequence of cost-sensitive classification problems; Rezaei et al. (2020) minimize the worst-case log loss using an approximated regular- ization term; Baharlouei et al. (2020) propose to use Rényí correlation as the regularization term to account for nonlinear dependence between variables. To measure the violation of the fairness criterion, we use Equalized Odds (EOdds) violation, defined as max a,''EA PPyAy (1|a, v)
PylAy (1|a,, w)]. Following Agarwal et al. (2018), we pick 0.01 as the default violation bound that the EOdds violation does not exceed (if practically achievable for the method) during training. For each method we plot the testing accuracy versus the violation of Equalized Odds. Although a prob- abilistic classification model is used across each method (here is logistic regression), if an algorithm output the class label where the prediction likelihood maximized, the prediction is in essence performed by deterministic function of input features (c.g., Rezaci et al. (2020); Baharlouei et al. (2020)). As we have shown in Section 4.1, for classification with deterministic function. in general cases the conditions specified in Theorem 4.1 are easily violated, i.e., Equalized Odds may not be
8

---

Under review as a conference paper at ICLR 2021
attained even if there is unlimited amount of data. Therefore, although here considering finite data cases, we can still anticipate lower level of fairness violation with a randomized pre- diction. This is validated by the numerical experiment: while the approach by Hardt al. (2016) does not score the lowest test error, the violation of Equalized Odds is the lowest compared to other approaches. The benefit of introducing randomization can also be witnessed by the Pareto frontier presented in Agarwal et al. (2018), where the approach can potentially achieve any desired fairness- accuracy trade-off between that of the post-proessinng approach and that of the unconstrainedly optimized classifier". In some scenarios people tend to only care about equal TPR (e.g., the rate of acceptancce/admission) across groups, i.e., the Equal Opportunity (Hardt et al., 2016) notion of fairness. The related numerical result on real-world data sets is also presented.
CONCLUSION AND FUTURE WORK
In this paper, we focus on the Equalized-Odie Oddds criterion and consider the attainability of fairnsss and furthermore, if attainable, the optimality of the prediction performance under various settings. We first show that, for fair regression, one can only achieve Equalized Odds when certain conditions on the joint distribution of the features and the target variable are met. Then for classification tasks with deterministic classifiers, we give the condition under which Equalized Odds can hold true; we also show that under mild assumptions, ized) predictor, even with a continuous protected feature; in terms of the optimality of performance, one always (if conditions permit) benefit from exploiting all available features during training. Future work would naturally consider nonlinear regression algorithms with randomized output and fairness guarantees, and the attainability of more fine- ane-grained (compared to group fairness) criteria of fairness (e.g., individual fairness) as well as the procedure fairness in the fairness hierarchy.
always find a non-trivial Equalized-ONl -adlidzeddOdds (random-
REFERENCES
Alekh Agarwal, Alina Beygelzimer, Miroslav Dudik, John Langford, and Hanna Wallach. re- ductions approach to fair classification. In International Conference on Machine Learning, pp- 60-69, 2018
Julia Angwin, Jeff Larson, Surya Mattu, and Lauren Kirchner. Machine bias: There's software used across the country to predict future criminals, and it's biased against blacks. ProPublica, 2016.
Sina Baharlouei, Maher Nouiehed, Ahmad Beirami, and Meisam Razaviyayn. Rényi fair inference. In International Conference on Learning Representations, 2020.
Solon Barocas, Moritz Hardt, and Arvind Narayanan. Fairness in machine learning. NIPS Tutorial, 2017.
Richard Berk, Hoda Heidari, Shahin Jabbari, Matthew Joseph, Michael Kearns, Jamie Morgen- stern, Seth Neel, and Aaron Roth. A convex framework for fair regression. arXiv preprint arXiv:1006.02409, 2017.
Tolga Bolukbasi, Kai-Wei Chang, James Y Zou, Venkatesh Saligrama, and Adam T Kalai. Man is to computer programmer as woman homemaker? debiasing word embeddings. In Advances in neural information processing systems, pp. 4349-4357, 2016.
Toon Calders, Faisal Kamiran, and Mykola Pechenizkiy. Building classifiers with independency constraints. In 2009 IEEE International Conference Data Mining Workshops, pp. 13-18.
IEEE, 2009.
Silvia Chiappa. Path-specific counterfactual fairness. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pp. 7801-7808, 2019.
II the approach proposed by Agarwal et al. (2018), the randomization can come in two folds: the first kind of randomization comes from picking a classifier from the distribution of multiple available classifiers: the second kind of randomization comes from the prohabilistic prediction (if the hypothesis class contains prohabilistic prediction models).

---

Under review as a conference paper at ICLR 2021
Alexandra Chouldechova. Fair prediction with disparate impact: A study of bias in recidivism prediction instruments. Big data, 5(2):153-163, 2017.
Elliot Creager, David Madras, Joern-Hentt Jacobsen, Marissa Weis, Kevin Swersky, Toniann Pitassi, and Richard Zemel. Flexibly fair representation learning by disentanglement. In In- lernational Conference on Machine Leurning, pp. 1436-1445, 2019.
Rachel Cummings, Varun Gupta, Dhamma Kimpara, and Jamie Morgenstern. On the compatibil- ity of privacy and fairness. In Adjunct Publication of the 27th Conference on User Modeling, Adaptation and Personalization, pp. 309-315, 2019.
David Danks and Alex John London. Algorithmic bias in autonomous systems. In IJCAI, pp- 4691 4697, 2017.
Amit Datta, Michael Carl Tschantz, and Anupam Datta. Automated experiments on ad privacy settings: A tale of opacity, choice, and discrimination. Proceedings on privacy enhancing tech- nologies, 2015(1):22-122 2015.
Michele Donini, Luca Oneto, Shai Ben-David, John S Shawe-Taylor, and Massimiliano Pontil. Em- pirical risk minimization under fairness constraints. Advances in Neural Information Process- ing Systems, pp. 2791-2801, 2018.
Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise to sensitivity in private data analysis. In Theory of cryptography conference, pp. 265-284. Springer, 2006.
Cynthia Dwork, Moritz Hardt, Toniann Pitassi, Omer Reingold, and Richard Zemel. Fairness through awareness. In Proceedings the ence, pp. 214-226, 2012.
the 3rd innovations theoretical computer science confer-
Cynthia Dwork, Nicole Immorlica, Adam Tauman Kalai, and Max Leiserson. Decoupled classifiers for group-fair and efficient machine learning. In Conference on Fairness, Accountabilityy and Transparency, pp. 119-133, 2018
Benjamin Fish, Jeremy Kun, and Ádám D Lelkes. A confidence-based approach for balancing fair- ness and accuracy. Proceedings of the 2016 SIAM International Conference on Data Mining, pp. 144-144555 152. SIAM, 2016.
lan Goodfellow, Jean Pouget-Abadie, Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron Courville, and Yoshua Bengio. Generative adversarial nets. In Advances in Neural Infor- mation Processing Systems, pp. 2672-2680, 2014.
Moritz Hardt, Eric Price, and Nati Srebro. Equality of opportunity in supervised learning. In Advances in Neural Information Processing Systems, pp. 3315-3323, 2016.
Toshihiro Kamishima, Shotaro Akaho, and Jun Sakuma. Faimess-awart learning through regular- ization approach. In 2011 IEEE 11th International Conference Data Mining Workshops, pp. 643-650. IEEE, 2011.
Jon Kleinberg, Sendhil Mullainathan, and Manish Raghavan. Inherent trade-offs in the fair determi- nation of risk scores. arXiv preprint 3rXiv:1609.05880) 2016.
Matt Kusner, Joshua Loftus, Chris Russell, and Ricardo Silva. Counterfactual fairness. In Advances in Neural Information Processing Systems, pp. 4066-4076, 2017.
David Madras, Elliot Creager, Toniann Pitassi, and Richard Zemel. Learning adversarially fair and transferable representations. arXiv preprint arXiv:1802. 10330918000000000 2018.
Jérémie Mary, Clément Calauzenes, and Noureddine El Karoui. Fairess-aware learning for contin- uous attributes and treatments. In International Conference on Machine Learning, pp. 4382-43911, 2019.
Razich Nabi and Ilya Shpitser. Fair inference on outcomes. In Thirty-Second AAAI Conference on Artificial Intelligence, 2018.
10

---

Under review as a conference paper at ICLR 2021
Adrián Pérez-Suay, Valero Laparra, Gonzalo and Gustau Camps- Valls. Fair kernel learning. In Joint European Conference on Machine Learn ing and Knowledge Discovery in Databases, pp. 339-355. Springer. 2017.
Jordi Muñoz-Mari, Luis Gómez-Chova,
Ashkan Rezaei, Rizal Fathony, Omid Memarrast, and Brian Ziebart. Fairness for robust log loss classification. In Thirty-Fourth AAAI Conference on Artificial Intelligence, 2020.
Chris Russell, Matt J Kusner, Joshua Loftus, and Ricardo Silva. When worlds collide: integrating different counterfactual assumptions in fairness. In Advances in Neural Information Processing Systems, pp. 6414-6423, 2017.
Jiaming Song, Pratyusha Kalluri, Aditya Grover, Shengjia Zhao, and Stefano Ermon. Learning controllable fair representations. In The 22nd International Conference on Artificial Intelligence and Statistics, pp. 21732177,,,,,11 2019.
Latanya Sweeney. Discrimination in online ad delivery. Queue, 11(3):10-29, 2013.
Blake Woodworth, Suriya Gunasekar, Mesrob Ohannessian, and Nathan Srebro. Learning non- discriminatory predictors. In Conference on Learning Theory, pp. 1920-1953, 2017.
Yongkai Wu, Lu Zhang, Xintao Wu, and Hanghang Tong. Pe-fairesss: A unified framework for measuring causality-barn -bseed fairness. In Advances in Neural Information Processing Systems, pp- 3399-3409, 2019.
Muhammad Bilal Zafar, Isabel Valera, Manuel Gomez Rodriguez, and Krishna P Gummadi. Fair- ness beyond disparate treatment & disparate impact: Learning classification without disparate mistreatment. In Proceedings of the 26th international conference on world wide web, pp. 1171
1180, 2017a.
Muhammad Bilal Zafar, Isabel Valera, Manuel Gomez Rogriguez, and Krishna P Gummadi. Fair- ness constraints: Mechanisms for fair classification. In Artificial Intelligence and Statistics, pp. 962-970, 2017b.
Rich Zemel, Yu Wu, Kevin Swersky, Toni Pitassi, and Cynthia Dwork. Learning fair representations. In International Conference on Machine Learning, pp. 325-333, 2013.
Brian Hu Zhang, Blake Lemoine, and Margaret Mitchell. Mitigating unwanted biases with adver- sarial learning. In Proceedings of the 2018 AAAI/ACM Conference on AI, Ethics, and Sociery, pp- 335-340, 2018.
Junzhe Zhang and Elias Bareinboim. Fairness in decision-making the causal explanation formula. In Thirty-Secome AAAI Conference on Artificial Intelligence, 2018.
Lu Zhang, Yongkai Wu, and Xintao Wu. A causal framework for discovering and removing di- rect and indirect discrimination. In Proceedings of the 26th International Joint Conference Artificial Intelligence, pp. 3929-3935, 2017.
Han Zhao, Amanda Coston, Tameem Adel, and Geoffrey J. Gordon. Conditional learning of fair representations. International Conference on Learning Representations, 2020.

---

Under review as a conference paper at ICLR 2021
A APPENDIX
A.1 PROOF FOR THEOREM 3.1
To prove the unattainability of Equalized Odds in regression, we will need the following lemma, which provides a way to characterize conditional independenneldependeeee with conditional or joint distributions.
Lemma A.1. Variables V1 and V2 are conditionally independent given variable V3 if and only if there exist functions h(v1, V3) and g(v2; V3) such that
1//V/ (V1, 02 03) h(v1, vz) g(02, vz).
(10)
Proof. First, if Vi and 1/2 are conditionally independent given variable Va. then Equation 10 holds: Vai, (U1, 1/2 U3) = Iv. (01 v/) Pvslu, (v2 vz).
We then let h(v3)= == h(1,, va)de and g(vs) J g(v2, uy doz. Take the integral of Equation 10 w.r.t Un and U2, we have:
Pvs/ss (02 (3) h(vs)) ( 03), Pv (11 03) = 5(vs) h(v1 13),
respectively. Bearing in mind Equation 10, one can see that the product of the two equations above
PValv (22 0z) Pvilvs (v1 v3) h(vs) g vz) g(vs) h(v2, uz)
= h(va) g(va) Vaivs (01, 02 v3).
Take the integral of the equation above w.r.t 01 and U2 gives h(vz)) 5(v)) 1. The above equation then reduces to
Pvş Va (12 Uz) (v) e3) Pv. va (U,, 2/2 0z).
That is, V12 and V2 are conditionally independent given Vg-
Now we are ready to prove the unattainability of Equalized Odds in linear non- non-Gaussian regression: Theorem. (Unattainability of Equalized Odds in the Linear Non-Gaussian Case)
Assume that feature X has causal influence on Y, i.e., C + in Equation 4, and that the protected feature A and Y are not independent, i.e., qc + bd + O. Assume PEx and pe are positive on R. Let fi := log PA. f2 == log Pex, and fs := Pg.
pg. Further assume that f2 and fs are third-order differentiable. Then if at most one of Fxx and E is Gaussian, Z is always conditionally dependent on A given Y.
Proof. According to Equation 4, we have
A
0 0
A Ex E
Z
=
α + 9 gC hd
3 C
(11)
Y
The determinant of the above linear transformation is 3, which relates the probability density func- tion of the variables on the LHS and that of the variables on the RHS of the equation. Therefore, according to Equation 11, we can rewrite the joint probability density function by making use of the Jacobian determinant and factor the joint density into marginal density functions (A, Ex are mutually independent according to the data generating process). Further let
ā == a + 93
co
C
;:= bd
and ē:=
(12)
3
3
3
Then we have Ex 1 - ãA, E- = Y FA EZ, and
PA, (0, = PA.E.. E PA,,.,EEa,
ex. e)/13
-1 (es (p(
1
(A) (32 =a)
āa)pe(y - Fa ē2).
12

---

Under review as a conference paper at ICLR 2021
On its support, the log- dog-density be written
J = log P,,,,y (0, 2,
1
logpA(a) + loggEx (32 = +logpE(y Fa ē2) - logl
(13)
= =((a) + 12( (aa) + fz( - ia ēz) log |.3
According to Lemma A.I, A 1L Z Y if and only if PA,ZY (a, 2 y) is a product of a function of and y and function of and y- (a, 2, y) and a function of only y. This property, under the conditions in Theorem 3.1, is equivalent to the constraint
is further product of the above function
J_J 0A0Z
= 0.
(14)
According to Equation 13, we have
0J
f2
2 Ea) -. f2.ff Fa- - -čz)
0z
B
3
(15)
JJ
S2 B
,a) + Fē. f3 (y - Fa - ēz).
Oadz
B
Combining Equations 14 and 15 gives
rē 13 Fa ēz) = 3 552 āa).
(16)
Further taking the partial derivative of both sides of the above equation w.r.t. y yields
Fc: I (y Fa Ł2) = O.
(17)
There are three possible situations where the above equation holds:
(i ē = 0, which is equivalent to = and contradicts with the theorem assumption.
F 0. Then according Equation 16, we have ( 2- āa) = 0, implies either å
or ( āa) = O. If the latter is the case, then f2 is a linear function and, accordingly, cxp(f2) is not integrable and does not correspond to any valid density function. If the former true, i.e., = 0, then according to Equation 12, we have a -93, which further implies F bd
bel + qc. Therefore, in this situation, bd + qc 0, which again contradicts with the theorem assumption.
(iii) f3 (y Fa- - čz) = O. That is, f3 is a quadratic function with a nonzero coefficient for the quadratic term (otherwise fa does correspond to the logarithm of any valid density function). Thus E follows Gaussian distribution.
Only situation (iii) is possible, i.c., 7e # and E follows a Gaussian distribution. This further tells us that the RHS of Equation 16 is a nonzero constant. Hence f2 is quadratic function and Ex also IL Z Y were to true, then Ex and E are both
follows Gaussian distribution. Therefore Gaussian. Its contrapositive gives the conclusion of this theorem.
L
Corollary. Suppose that both Ex and E are Gaussian, with variances ox and oz. respectively. (The feature feature A is not necessarily Gaussian.) Then Z IL A Y if and only if
a bdc of - -q -
(18)
B
²² Rx + oz
Proof. Under the condition that Fx and E are Gaussian, their log-density functions third-order differentiable. Then according to the proof of Theorem 3.1, the Equalized Odds condition A ll 2 Y equivalent to Equation 16, which, together with Equation 12 well as the fact that f d
and f" = o yields Equation 18.
13

---

Under review as a conference paper at ICLR 2021
A.2 PROOF FOR THEOREM 4.1
Theorem. Assume that the feature A and Y are dependent and that their joint probability P)A,Y) (for discrete A) or joint probability density p(A, Y) (for continuous A) is positive for every combination of possible values of A and Y. Further assume that Y is not fully determined by A. and that there are additional features X that are not independent of Y. Let the output of the classifier A = {a Er E X s.t. f(a, = t), and 8111= : {ir f(a,x)) = 13. Equalized Odds holds true if and only if the following two conditions are satisfied:
Y be a deterministic function f A x X + V. Let S(t)
(i) VEE:: 5 A.
(ii) VIEV, Ya, a' E A. a.a x d'
Σ P(X = = A= a)
=)
E P ZES X/e'
A ==
v).
ZESX X|4
Proof. We begin by considering the case when A and X are discrete (for the purpose of readability).
The Equalized Odds criterion can be written in terms of the conditional probabilities:
Ya E A, 4, EY: P( A a u) P( = = y)-
(19)
Expand the LHS of Equation 19:
P(Y = A a, Y= y)
Σ P(Y = A= a, x x, P(X A= a, y), =E
and bear in mind that y == fAA X) is deterministic function of (A, X). we have:
((f(A,X) = A = 0, X = Y = y) P(f(A,X) =t A = a, X = 2) E {0,1). (20)
From Equation 20 we can see that the conditional probability P(X r A = a. = y) can contribute to the summation only when fa, x) = L. We can rewrite the LHS Equation 19:
P( t A = a, v) Σ P(X = x A= = v) (a) v).
resto X|a
Similarly, for the RHS of Equation 19, we have:
P( = = = v) = Σ Σ P( =1 a
= Y = =
E Σ P(X A y) Y v)
Σ (c.))) Y y aES
Since Equalized Odds holds true if and only if Equation 19 holds true, then the LHS of the equation does not involve a (as the case for the RHS), i.e., ((+) (a, y) does not change with a. Then Equation 19 becomes:
(a,)) = Σ (a. Y y) (a.v) E P Y v), aES
DEST
which gives the condition (i) that s contains all possible values of A, i... A = = (otherwise
Σ Eassto P(A a = y) 1). Since ((1) (a, y) does not change with a, we have:
Va,a' E A,a d': 2
Σ P(X= x A a, Y y) Σ P(X = x A AI d. v), ( Xin"
which gives the condition (ii). Therefore, Equalized Odds implies conditions (i) and (ii). On the other hand, it is easy to that when conditions (i) and (ii) are satisfied, Equation 19 holds true, i.e. Equalized Odds holds true.
When A and X are continuous,
replace the summation with integration accordingly. n
14

---

Under review as a conference paper at ICLR 2021
A.3 PROOF FOR THEOREM 4.2
Theorem. (Attainability of Equalized Odds)
Assume that the feature X is not independent from Y, and that Y is a function of A and X. Then for binary classification, if Y is non-trivial predictor for Y, there is always at least one non- non-trivial predictor poss derived by post-processing Y that attain Equalized Odds, i.e.
2(Ypon)) + 0.
Proof. Since is a function of XA and X Y, Y is not conditionally independent from Y given protected feature A. Furthermore, since Y is non-trivial estimator of the binary target Y, there exists positive constant c > 0, such that:
P( =
- P(P =
a, = 2 Va E.
(21)
positive rate of the non-trivial predictor is always strictly larger than its false positive rate*. As illustrated in panels (a) and (b) of Figure 1, the (FPR, TPR) pair of the predictor Y when A = a. i.c., the point % (Y) on ROC plane, will never fall in the gray shaded area, and its coordinates are bounded away from the diagonal by at least e. Therefore,
Equation 21 implies that for each value of A, the corresponding
intersection all C. (P) would always form a parallelogram with non-empty area, which corresponds to attainable non- conttrivial post-processing fair predictors Ypost-
A.4 PROOF FOR THEOREM 4.3
Theorem. (Equivalence between ROC feasible areas)
Let (2mmps)) denote the ROC feasible area specified by the constraints enforced on Yposs. Then (V poa) is identical to the ROC feasible area ()(M)) that is specified by the following set of con- straints:
(i) constraints enforced on Y
(ii) additional "pseudo" constraints: Va A, (00 P. 3111
-111 where
a(a) = ExEx = A a. x. = P(X = x 1 = Y Y u).
Proof. Since the post-processing predictor Ypsst is derived by optimizing over parameters or functions (of A) pl.h). Therefore, considering the fact that Pr Ar PeylAAY (1/a,3) v) Tay (Fop). we have the relation between Tay (Y post) and Tay (Yap)):
Yag (Ypoa))
Yay (Y poos) (((0) Pay Papi) +((L) Pay (Fop)),
(0))
p(Ý post 1 A V 0),
(22)
A a, V 1). ((1)) P(Ý post
Similarly, consider the relation between positive rates Yin and those of Poyi. i.e., Pr. PYnlAY (1)a,)) and Ps I (1la, y). by factorizing A ()ayy)) over X and Yopi
(1),,) I
Py PAX (1)a, XXIAY (2lo, v. Py (ula
(23)
WEY
FEX
Therefore, we have the relation between Yay (Ym) and Yay (Pop):
Yag (Ym)) ((0)) Tay Yupu) + s(1) Yay (Pop)):
Pay = Exsx P(ym 1 A = a, X = P(X = A a.Y = opt = 0),
(24)
(11) ExEX P(V =1
0, = P(X = A a, Y y, V = 1).
II the TPR of the predictor is always smaller than its FPR, one can simply flip the prediction (since the target binary) and then Equation 21 holds
15

---

Under review as a conference paper at ICLR 2021
If there is more than one variable in X in Equation 24, expand the summation if needed; if some variables are continuous, one may also substitute the summation with integration accordingly.
From Equation 24, pay and ((1) depend on the value of Y:
( P(Y,. A a, Y = y, Popt = 1),
ag
(25)
a P(y A a, Y y, Vopt 0)-
Apart from Equalized Odds constraints (which are shared by Yin and Ypoa), when enforcing addi- 3((0) =Pat and 3 - conditional independence Yin L AA, Popt enforced, making B and Beg no longer depend on Y. This is exactly the inherent constraint post satisfies. Therefore the stated equivalence between ROC feasible areas p2sypos) (specified by the constraints enforced on Ypea) and (2((i)) (specified by the constraints enforced on Y,, together with the additional "pseudo" constraints) hold true.
tional "pseudo" constraints @00 =
A.5 DESCRIPTION OF THE DATA SETS
(1) Adult': The UCI Adult data set contains 14 features for 45,222 individuals (32,561 sam- ples for training and 12,661 samples for testing). The census information includes gender, marital status, education, capital gain, etc. The classification task is to predict whether a person's 's annual income exceeds 50,000 USD. We use the provided testing set for evalua- tions and present the result with gender and race (consider white and black people only) set as the protected feature respectively.
(2) Bank3; The UCI Bank Marketing data set is related with marketing campaigns of a banking institution, containing 16 features 45,211 individuals. The assigned classification task is to predict if client will subscribe (yes/no) to term deposit. The original data set is very unbalanced with only 4,667 positives out of 45,211 samples. Therefore, we combine "yes" points with randomly subsampled "no" points and perform experiments the down- sampled data set with 10,000 data points. The protected feature is the marital status of the client.
(3) COMPAS (Angwin et al., 2016): The COMPAS data set contains records of over 11,000 defendants from Broward County, Florida, whose risk (of recidivism) was assessed using the COMPAS tool. Each record contains multiple features of the defendant, including de- mographic information, prior convictions, degree of charge, and the ground truth for recidi- vism within two years. Following Zafar al. (2017a); Nabi & Shpitser (2018), limit our attention to the subset consisting of African-American and Caucasians defendants. The features we use include age, gender. race, number of priors, and degree of charges. The task is to predict the recidivism of the defendant and we choose race as the protected feature.
(4) German Credit The UCI German Credit data contains 20 features numerical, 13 categorical) describing the social and economical status of 1,000 customers. The prediction task is to classify people as good bad credit risks. We use the provided numerical version of the data and choose gender as the protected feature.
A.6 ADDITIONAL DISCUSSION
For classification, while randomization can ensure group level of fairness, there is still some inher- shortcoming of the criterion that should pay attention to. For example, in the FICO case study in Hardt et al. (2016), for a specific client from certain demographic group, the decision of approve/deny the loan actually comes in two folds: if his/her credit score above (below) the upper (lower) threshold, the bank approve (deny) the application for sure; if the score falls in the interval between two thresholds, the bank would flip a coin make decision. Then we can imagine the following situation when a client whose credit score falls within the interval between the upper and
wei. wwt.:es..c...etuuaaaaaattaaaaaee http:////////eeeoee/////a///////
'nttp://archive hhttps://archive.iiss "https://acchvee iss usi wtw.eed/dd///aaaedeeeeeeeeeeeeee stattelsssstttttsso// log ( (germantcredi t+data)
16

---

Under review as a conference paper at ICLR 2021
lower thresholds goes to a bank to apply loan. Helshe ask (if conditions permit) the bank to run the model multiple times until the decision is approval. This would make the randomization that was built into the system for the sake of fairness no longer effective, and the system in essence only has one fixed threshold (i.e., the original lower threshold).
17


Reviews:
[{"review_id": "oLq0Qn3RqyX", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "The paper studies the attainability of the equalized-odd fairness criteria introduced by Hardt et al'16 in classification and regression tasks. In particular, the paper claims that under certain conditions EQ is not even attainable. They proved the claim for the regression task but I could not find exactly where they discuss the classification attainability.  In fact, the (non)attainability claim about EQ is confusing to me since by definition, a *perfect* predictor (which is non-trivial) satisfies EQ. Intuitively, their result is meaningful for the task of linear regression as a perfect predictor may not exist. But as we consider classification or non-linear regression it becomes less believable. For instance as the authors mentioned, in a previous work, Woodworth et al.'17 showed that even checking a predictor is fair w.r.t. EO notion is not possible when we use *finite* many samples. \n\nThe results on classification with deterministic prediction seems restrictive as condition (i) seems very strong. Assuming condition (i), Theorem 4.1 seems straightforward to prove. Also, what is the difference between Theorem 4.2 and the previous results on the existence of fair predictor w.r.t. EQ in Hardt et al.'16 (e.g., Proposition 4.4.). Please elaborate on this. Lastly, Theorem 4.3 seems very interesting.\n\nMinor comments:\n- The figure 1 which has been referred to several times of the paper is missing.\n- Hardt et al. entry in References has typo.\n- page 2: outputing -> outputting, utiziling ->utlizing\n- page 3: Eqaulized -> Equalized\n- page 4: Eqalized -> Equalized\n- page 6: unconstrianed -> unconstrained, seperately -> separately\n- page 8: convariance -> covariance, appximated -> approximated, numerial -> numerical\n- page 13: quadractic -> quadratic\n- page 15: insection -> intersection\n\n=====POST-REBUTTAL COMMENTS========\nI would like to thank authors for their clarifications. Accordingly, I have increased my score to 6.", "extra_scores": {}, "extra_text": {}}, {"review_id": "oAjXhGK461C", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "\n# Main claims and contributions\n\nThe authors study if Equalized Odds (EO) definition of fairness is attainable for regression and classification problems. In their paper, the authors make several contributions:\n1. They provide an example of linear regression problem, for which EO can never be satisfied (Theorem 3.1)\n2. For classification problem, the authors prove in Theorem 4.1 that if the predictor is deterministic, then EO is satisfied only under strict assumption on data distribution. In contrast, if the predictor is randomized, the authors show in Theorem 4.2 that EO is attainable under mild assumptions.  \n3. The authors compare different techniques for obtaining EO-satisfying predictors. Namely, they compare in- and post-processing techniques. They prove in Theorem 4.3 that in-processing allows for better classification accuracy compare to the post-processing technique from Hardt et al. (2016).\n\nThe authors, perform numerical experiments to support their claims. For regression task, they learn linear and non-linear predictors on data with gaussian and non-gaussian noise and observe that EO is essentially impossible to satisfy in non-linear regression even if exogenous terms are gaussian. For classification problem, they compare different in-processing techniques with a post-processing technique from Hardt et al. (2016).\n\n# Novelty\n\nTo the best of my knowledge, the question of attainability of EO for regression/classification for deterministic clarifier is novel in the literature.\n\nOn the other hand, the same question for randomized predictor (Section 4.2) seems to be already answered in the literature by Hardt et al. In particular, Theorem 4.2 seems already known and I did not understood clearly what is the contribution of 4.2.3.\n\n# Clarity and soundness\n\nThe paper is relatively easy to follow, apart from Section 4.2.3 (and in general the discussion about the ROC curve, and the role of Figure 1). The assumption of infinite data allows the authors to simplify the exposition. Some details:\n\n1. Lemma A.1. looks like a known fact. \n2. Theorem 3.1: make clear transitions steps by justifying what properties of random vectors are used.\n3. Theorem 4.1: proof seems to be fine, no comments\n4. Theorem 4.2: in Hardt et al. (2016), they show that the resampling probabilities can be calculated by solving an LP, need to justify the novelty of the result / emphasize the increment.\n5. Theorem 4.3: to me, both the statement and the proofs are hard to parse.\n\n# Reasons to accept\n\nThe authors ask an important question of whether the standard definition of fairness (EO) is attainable for any instance of problems even with infinite data. They provide a counterexample for regression problem. The authors give a condition under which EO is attainable for classification. The authors compare in- and post-processing techniques in terms of their efficiencies.\n\n# Reasons to reject\n\nThe authors are encouraged to make clear which statements are novel and which were already known in the literature. For example, the result in Theorem 4.2 seems to be contained in Hardt et al. (2016).\n\nThe authors mention pre-, in- and post-processing techniques for fair classification/regression. However, only in- and post-processing are compared. It would be interesting to include also the pre-processing to the discussion.\n\nThe authors compare deterministic algorithms (Zafar et al. (2017a) , Rezaei et al. (2020)…) with a probabilistic algorithm from Hardt et al. (2016), which does not seem to be a fair comparison. \n\n## minor Typos:\n\nP.4 Equalized Odds\nP.5  Equalized Odds\nP.6 separately\nP.7 covariance, approximated\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "n3DP1V5RrnC", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "Summary: \n\nThis paper studies the attainability of Equalized Odds fairness criterion in both the classification and regression problems. When the prediction function is deterministic, it shows that Equalized Odds may not be attainable under certain conditions. In contrast, if the prediction function is randomized, then Equalized Odds classifiers can always be achieved under some conditions. Moreover, it shows that the performance attained using the in-processing approach after exploiting all available features is always better than attained using the post-processing approach. \n\nStrengths:\n\n1. The conditions under which perfect Equalized Odds can be attained are identified under various settings, including both regression and classification, and cases when prediction mapping is deterministic and randomized. \n\n2. Utilizing ROC feasible area, the paper builds a connection between two approaches used to achieve fairness: in-processsing approach and post-processing approach. Specifically, the constraint enforced by post-processing consists of the constraint enforced by in-processing and an additional constraint.  \n\nComments: \n\n1. In the experiments (Figure 3), how is the level of fairness violation selected? Are they the best attainable level? Because of the tradeoff between accuracy and fairness, it is possible to improve accuracy by adjusting the fairness guarantee. For example, according to Figure 1 in Agarwal et al. 2018, for many datasets, the reduction approach (in-processing) can achieve any desired fairness level between fairness of post-processing (Hardt et al. 2016) and fairness of unconstrained classifier. It means that it is possible to achieve perfect Equalized Odds using Agarwal et al. 2018. I hope the authors can explain this point. Moreover, the reduction approach returns a randomized classifier, rather than the deterministic function of features as mentioned in the paper. It is necessary to make clarifications in the paper. \n\n2. Related work: the attainability of perfect fairness (in addition to Equalized Odds) has been studied in the literature, which is highly related to this work. I suggest authors including them in related work. For example, \"Cummings, R.; Gupta, V.; Kimpara, D.; and Morgenstern, J. On the compatibility of privacy and fairness, 2019\". It shows that it’s impossible to train a differentially private classifier (a randomized classifier) that satisfies exact (perfect) Equal opportunity fairness and achieves a higher accuracy than a constant classifier.\n\n3. It would be better if authors can add some explanations/intuitions of theorems, e.g., in Thm 3.1, how strong the assumption is that $f_2$ and $f_3$ are third-order differentiable.  \n\n4. Conditions given in Theorem 4.1 seems to be the necessary and sufficient condition. It would be better if authors can clearly state it in the theorem (e.g., Equalized Odds holds if and only if conditions are satisfied).\n\n5. Typos: in Eqn (5), $P_{\\hat{Y}|AY}(1|a,y) —> P_{\\hat{Y}|AY}(u|a,y)$ \n\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "jujUslS96Hs", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "This paper studies under what conditions a classifier can satisfy the condition of equalized odds. The authors first prove an impossibility result which shows that (under linear non-gaussian case) any deterministic classifier\tcannot achieve equalized odds across the protected groups. This leads to the question of randomized classifier. We can always satisfy equalized odds with randomized classifier  with a trivial classifier. However, the authors show two interesting results — (1) using the post-processing framework developed in Hard et. al. (2016) it is possible to obtain a non-trivial randomized classifier that satisfies EO, and (2) in-processing based classifiers are better than the post-processing based fair classifiers if we compare them in terms of accuracy.\n\nI didn’t find the result about deterministic classifier to be surprising. However, it is interesting that the authors think that a similar result holds for non-linear regression. The experiments definitely suggests that but I am wondering if the authors have more intuition regarding this direction. At least, I don’t see how the proof for the linear case extends for the general non-linear setting.\n\nThe results for the randomized classifiers are interesting, however I think they are expected. Several prior papers have observed that in-processing based classifiers do perform better than the post-processing classifiers in practice (e.g. see experimental section in Agarwal et. al. 2018). But it is nice to see a formal proof of this fact. I have two questions regarding this result —\n\n1. The result only proves weak inclusion of the Omega() sets. Is there any interpretable conditions when the inclusion is strict and in-processing is strictly better than post-processing?\n2. I understand the focus of this paper is EO constraint, but does a similar result can be proven for other fairness constraints, perhaps extending the proof technique presented here?\n\nWeaknesses:\n\nEven though the results in this paper are interesting, the main weakness of the paper is that  the techniques are not novel. In fact, the proof relies on the ROC plane characterization of post-processing classifiers established in earlier papers. Additionally, I think a more interesting question to consider would have been the trade-off between EO fairness and accuracy. In fact, the plots in figure 3 does show such trade-offs. \n\nIn summary, I think the paper makes interesting contributions in understanding the attainability of the EO fairness constraints. However, the results are not complete in its current setup and also the techniques are limited to the particular notion of fairness considered in this paper.\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "AcNSJBncVa2", "reviewer": "AnonReviewer5", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "This paper examines the conditions under which equalized odds can be achieved from a theoretical perspective. The authors show that in general, equalized odds cannot be achieved in linear regression and clasisication tasks. However, when randomized prediction is allowed, they show that equalized odds can be achieved in binary settings.\n\nOverall, I don't really see the motivation for this paper. Equalized odds isn't typically considered in linear regression tasks, and moreover, the generalization given in this paper is particularly restrictive -- it requires matching distributions across sensitive attributes conditioned on the target variable. One could imagine a less restrictive generalization like matching expectations, i.e., $E[\\tilde Y | Y, A = a_1] = E[\\tilde Y | Y, A = a_2]$.\n\nIn general, equalized odds can always be achieved with trivial, constant classifiers, so the authors specify that they're only interested in non-trivial classifiers. This paper only considers the question of whether classifiers can exactly satisfy equalized odds -- presumably, given that trivial classifiers satisfy equalized odds, something epsilon-close to a trivial classifier will satisfy an epsilon-approximation of equalized odds. What this paper doesn't answer, and what would in my mind be a far more interesting result, is the converse: if the conditions specified in the paper are not met, is it still possible to get an epsilon-approximation of equalized odds? If so, then this would imply that the conditions derived here are in a sense qualitatively necessary. If not, then these results would seem more brittle.\n\nThe techniques used to derive the positive result (that equalized odds can be satisfied with randomized classification) appear to just be a formal statement of the algorithm given by Hardt et al. (2016).\n\nThe paper itself is a little difficult to parse at times. Section 2.1 appears to be an attempt to specify a qualitative relationship between ideas about fairness, but I find it difficult to understand what the purpose is.\n", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper study under which condition a classifier can respect the condition of equalized odds. The reviewers find the paper interesting but they also raise some important concerns about it.

First, multiple reviewers pointed out that the results are not particularly novel or surprising and, even after discussing the rebuttal, they consider the result a bit incremental.

Second, the motivation of the paper are also questioned by multiple reviewers that suggested to study the tradeoff between trade-off between EO fairness and accuracy.

Overall, the paper contains some interesting ideas but it is below the high acceptance bar of ICLR.
Decision: Reject