Conditional Learning of Fair Representations
Authors: Han Zhao
Amanda Coston
Tameem Adel
Geoffrey J. Gordon
Venue:  (2020)
Keywords: algorithmic fairness
representation learning

Abstract: We propose a novel algorithm for learning fair representations that can simultaneously mitigate two notions of disparity among different demographic subgroups in the classification setting. Two key components underpinning the design of our algorithm are balanced error rate and conditional alignment of representations. We show how these two components contribute to ensuring accuracy parity and equalized false-positive and false-negative rates across groups without impacting demographic parity. Furthermore, we also demonstrate both in theory and on two real-world experiments that the proposed algorithm leads to a better utility-fairness trade-off on balanced datasets compared with existing algorithms on learning fair representations for classification. 


Published as a conference paper at ICLR 2020
CONDITIONAL LEARNING OF FAIR REPRESENTATIONS
Han Zhao' & Amanda Coston Machine Learning Department Carnegie Mellon University han. zhacccs cmu. edu acostonBandrew. cmu edu
Tameem Adel
Department of Engineering
University of Cambridge
tah478 7ac....c.m.mmmmmmmmmmmmmmmm.m ac. uk
Geoffrey J. Gordon
Microsoft Research, Montreal Machine Learning Department
Carnegie Mellon University
geoff. www..ooommmiooooo..ooooooo
ABSTRACT
We propose a novel algorithm for learning fair representations that can simultane- ously mitigate two notions of disparity among different demographic subgroups in the classification setting. Two key components underpinning the design of our algorithm are balanced error rate and conditional alignment of representations. We show how these two components contribute to ensuring accuracy parity and equalized false-positive and felse-negative rates across groups without impacting demographic parity. Furthermore, we also demonstrate both in theory and on two real-world experiments that the proposed algorithm leads to a better duility-firness. trade-off on balanced datasets compared with existing algorithms on learning fair representations for classification.
INTRODUCTION
High-stakes settings, such loan approvals, criminal justice, and hiring processes, use machine learning tools to help make decisions. A key question in these settings is whether the algorithm makes fair decisions. In settings that have historically had discrimination, we are interested in defining fairness with respect to a protected group, the group which has historically been disadvantaged The rapidly growing field of algorithmic fairness has a vast literature that proposes various fairness metrics, characterizes the relationship between fairness metrics, and describes methods to build classifiers that satisfy these metrics (Chouldechova & Roth 2018: CCrbett-
& Goel 2018)
Among many recent attempts to achieve algorithmic fairness (Dwork et al. 2012 Hardt et al. 2016
Zemel et al. 2013: Zafar et al. 2015). learning fair representations has attracted increasing attention due to its flexibility in learning rich representations based advances in deep learning (Edwards) & SSorkey
2013 Louizos et al.) 2015; Beutel et al. 2017 Madras et al. 2018). The backbone idea underpinning this line of work is very intuitive: if the representations of data from different groups are similar to each other, then any classifier acting on such representations will also be agnostic to the group membership.
However, it has long been empirically observed (Calders et al. 2009) and recently been proved (Zhao Gordon| 2019) that fairness is often at odds with utility. For example, consider demographic parity, which requires the classifier to be independent of the group membership attribute. It is clear that demographic parity will cripple the utility if the demographic group membership and the target variable are indeed correlated. To escape such inherent trade-off, other notions of fairness, such as equalized odds (Hardt et al.) 2016). which asks for equal false positive and negative rates across groups, and accuracy parity (Zafar et al. 2017), which seeks equalized error rates across groups, have been proposed. is a well-known result that equalized odds is incompatible with demographic parity (Barocas et al. 2017) except in degenerate cases where group membership is independent Part of this work was done when Han Zhao was visiting the Vector Institute, Toronto.

---

Published as a conference paper at ICLR 2020
of the target variable. Accuracy parity and the so-called predictive rate parity (c.f. Definition 2.4 could be simultaneously achieved, e.g., the COMPAS tool (Dieterich et al. 2016). Furthermore. under some conditions, it is also known that demographic parity can lead to accuracy parity (Zhao)
& Gordon, 2019). However, whether it is possible to simultaneously guarantee equalized odds and accuracy parity remains open question.
In this work, we provide an affirmative answer to the above question by proposing an algorithm to align the conditional distributions (on the target variable) of representations across different demographic subgroups. The proposed formulation is a minimax problem that admits a simple reduction sost-sensitive learning. The key component underpinning the design of our algorithm is the balanced error rate (BER, c.f. Section ( (Feldman et al., 2015 Menon & Williamson 2018). over the target variable and protected attributes. We demonstrate both in theory and on two real-world experiments that together with the conditional alignment, BER helps our algorithm to simultaneously ensure accuracy parity and equalized odds across groups. Our key contributions are summarized as follows:
We prove that BER plays a fundamental role in ensuring accuracy parity and a small joint emror across groups. Together with the conditional alignment of representations, this implies that we can simultancously achieve equalized odds and accuracy parity. Furthermore, we also show that when equalized odds is satisfied, BER serves of each subgroup. These results help to justify the design of our algorithm in using BER instead of the marginal error as our loss functions.
upper bound on the error
We provide theoretical results that our method achieves equalized odds without impacting demographic parity. This result shows that we can preserve the demographic parity gap for free while simultaneously achieving equalized odds.
Empirically, among existing fair representation learning methods, we demonstrate that our algorithm is able to achieve a better utility on balanced datasets. On an imbalanced dataset, our algorithm is the only method that achieves accuracy parity; however it does so at the cost of decreased utility.
We believe our theoretical results contribute to the understanding on the relationship between equal- ized odds and accuracy parity, and the proposed algorithm provides an alternative in real-world scenarios where accuracy parity and equalized odds are desired.
2 PRELIMINARY
We first introduce the notations used throughout the paper and formally describe the problem setup and various definitions of fairness explored in the literature.
Notation We use X' C Rd and y {0, 1) denote the input and output space. Accordingly, we use X and Y to denote the random variables which take values in X' and V, respectively. Lower case letters x and y are used to denote the instantiation of X and Y. To simplify the presentation, we use A E {0, }} as the sensitive attribute, c.g., race, gender, etc. Let 7. be the hypothesis class of classifiers. In other words, for h E H. h : X + y is the predictor that outputs a prediction. Note that even if the predictor does not explicitly take the sensitive attribute A as input, this fairness through blindness mechanism can still be biased due to the potential correlations between X and A. In this work we study the stochastic setting where there is a joint distribution DD over X, Y and A from which the data are sampled. To keep the notation consistent, for a, y E {0, 1]. we use D. to mean the conditional distribution of D given A = a and DV to mean the conditional distribution of D given Y = y. For an event E, D(E) denotes the probability of E under D. In particular, in the literature of fair machine learning. we call D(Y 1) the base rate of distribution D and use ABR D') ;= [D(Y = 1) - DY = 1) to denote the difference of the base rates between two distributions D and D' over the same sample space.
Given a feature transformation function g X + Z that maps instances from the input space X' to feature space 2, we define 9DD : Do - be the induced (pushforward) distribution of D under g. i.c., for any event E' C 2. (EE == D(g 1 '(E') D({z X' 9(x) E'}). To measure the discrepancy between distributions, we use drv (Dv D') to denote the total variation between
Our main results could also he straightforwardly extended to the setting where A is categorical variable.
2

---

Published as a conference paper at ICLR 2020
them: drv (D, D') sups (D(E) - (E)). In particular, for binary random variable Y, it can be readily verified that the total variation between the marginal distributions D(Y) and (Y) reduces to the difference of their base rates, ABn (') To see this, realize that (EV, (Y)) max ( [DD = 1) D'(Y = 1), (D(Y = 0) - D'(Y = O)B = |D(Y = D' = 1) ABR (D, D by definition.
Given a joint distribution D, the error of a predictor under D is defined as ErrD (h) == Ep |Y h.)]]. Note that for binary classification problems, when h(X) E {0, 1}, Errp(h) reduces to the true error rate of binary classification. To make the notation more compact, we may drop the subscript D when it is clear from the context. Furthermore, we use CEp(Y ( || Y) to denote the cross- entropy loss function between the predicted variable y and the true label distribution Y over the joint distribution D. For binary random variables Y. we define BER Y) to be the balanced error rate of predicting Y using Y, e.g., BERp(Y || Y) == D(Ý = Y = 1) + +(P = Y 0). Realize that D(Y 0 Y = 1) is the false negative rate (FNR) of Y and D( = - corresponds to the false positive rate (FPR). So the balanced error rate can also be understood as the sum of FPR and FNR using the predictor Y. We can similarly define B A) as well.
Y 0)
Problem Setup In this work focus on group fairness where the group membership is given by the sensitive attribute A. We assume that the sensitive attribute A is available to the learner during training phase, but not inference phase. As a result, post-processing techniques ensure fairness are not feasible under our setting. In the literature, there are many possible definitions of fairness (Narayanan 2018), and in what follows we provide brief review of the ones that are mostly relevant to this work.
Definition 2.1 (Demographic Parity (DP)). Given a joint distribution D, a classifier satisfies demographic parity if Y is independent of A.
When Ý is deterministic binary classifier, demographic parity reduces to the requirement that DY = 1) Di 1). i.e., positive outcome is given to the two groups at the same rate.
Demographic parity is also known as statistical parity, and it has been adopted as the default
definition of fairness in a series of work (Calders & Verwer 2010 Calders et al. 2009 Edwards &
Storkey 2015 Johndrow et al. 2019; Kamiran & Calders] 2009; Kamishima et al. 2011 Louizos |
et al. 2015 Zemel et al. 2013; Madras et al. 2018; Adel et 2019). It is not surprising that
demographic parity may cripple the utility that we hope to achieve, especially in the common scenario
where the base rates differ between two groups (Hardt et al.) 2016). Formally, the following theorem characterizes the trade-off in terms of the joint eπrоr across different groups:
Theorem 2.1. (Zhao Gordon 2019) Let Ý h(g(X)) be the classifier. Then Err (h o g) + EIrD, (h e g) > ABR (Do, (Do, D1) (g: 9:
In this case of representations that are independent of the sensitive attribute A, then the second term drv(g;Do, 9: D)) becomes and this implies:
Errp, (h g) + Errp, (h 2 ABR (Do. D1).
At a colloquial level, the above inequality could be understood as an uncertainty principle which says:
For fair representations, it is not possible to construct predictor that simultane- ously minimizes the errors on both demographic subgroups.
More precisely, by the pigeonhole principle, the following corollary holds:
Corollary 2.1. If dry (g) Do. 9; D2) = 0, then for any hypothesis ht max (Er (h o g), Errp, (h g)} 2 ABR (Po, D2)
In words, this means that for fair representations in the demographic parity sense, at least one of the subgroups has to incur a prediction error of at least ABR (Do, D1)/2 which could be large in settings like criminal justice where ABR (Do D2) is large. In light of such inherent trade-off, alternative definition is accuracy parity, which asks for equalized error rates across different groups:
Definition 2.2 (Accuracy Parity). Given joint distribution D, classifier Y satisfies accuracy parity if DY #Y) ( + YY)
3

---

Published as a conference paper at ICLR 2020
A violation of accuracy parity is also known as disparate mistreatment Zafar et al. 2017). Different from the definition of demographic parity, the definition of accuracy parity does not eliminate the perfect predictor even when the base rates differ across groups. Of course, other more refined definitions of fairness also exist in the literature, such as equalized odds (Hardt et al. (016).
Definition 2.3 (Equalized Odds, a.k.a. Positive Rate Parity). Given joint distribution D, a classifier Y satisfies equalized odds if Y is independent of A conditioned on Y.
The definition of equalized odds essentially requires equal true positive and false positive rates between different groups, hence it is also known as positive rale parity. Analogous to accuracy parity, equalized odds does not eliminate the perfect classifier (Hardt al., al.) 2016)), and we will also justify this observation by formal analysis shortly. Last but not least, we have the following definition for predictive rate parity:
Definition 2.4 (Predictive Rate Parity). Given joint distribution D, classifier Y satisfies predictive rate parity if (Y
y = c) = DY = 1 = c). Vc E [0, 1].
Note that in the above definition we allow the classifier Y be probabilistic, meaning that the output of Y could be any value between 0 and 1. For the case where ÿ is deterministic, Chouldechova (2017) 7) showed that no deterministic classifier can simultaneously satisfy equalized odds and predictive rate parity when the base rates differ across subgroups and the classifier is not perfect.
ALGORITHM AND ANALYSIS
In this section we first give the proposed optimization formulation and then discuss through formal analysis the motivation of our algorithmic design. Specifically, we show in Section [3.1 why our formulation helps to escape the utility-fairnet
trade-off. We then in Section formally prove that the BERs in the objective function could be used to guarantee a small joint error across different demographic subgroups. In Section 3.3 we establish the relationship between equalized odds and accuracy parity by providing an upper bound of the error gap in terms of both BER and the equalized odds gap. We conclude this section with a brief discussion on the practical implementation of the proposed optimization formulation in Section 3.4 Due to the space limit, we defer all the proofs to the appendix and focus explaining the high-level intuition and implications of our results.
As briefly discussed in S5ction a dominant approach in learning fair representations is via adversar- ial training. Specifically, the following objective function is optimized:
min max CEp(h(g(X)) || Y)- - A CEp(h' (x())) 4)
hg h
In the above formulation, the first term corresponds to minimization of prediction loss of the target variable and the second term represents the loss incurred by the adversary h Overall this minimax optimization problem expresses a trade-off (controlled by the hyperparameter À > 0) between utility and faimness through the representation learning function g: on one hand g needs to preserve sufficient information related to Y in order to minimize the first term, but on the other hand also needs to filter out information related to in order to maximize the second term.
3.1 CONDITIONAL LEARNING OF FAIR REPRESENTATIONS
However, as we introduced in Section 2 the above framework is still subjective to the inherent trade-off between utility and fairness. To escape such a trade-off, we advocate for the following optimization formulation instead:
mim max h.
(ERx(b()(X)) |]Y) A (BER (l' (o(X)) || A) + BER (Ii (x(()) ())
(2)
Note that here we optimize over two distinct adversaries, one for each conditional distribution D9, y E {0, 13. Intuitively, the main difference between ? and (I) is that we use BER as our objective function in both terms. By definition, since BER corresponds to the sum of Type-I and Type-Il errors in classification, the proposed objective function essentially minimizes the conditional errors instead of the original marginal error:
D(ÿ + Y)- D(Y = Oy 4Y Y = 0) DDY = 1)D(& +
(3)
|| BE y
x / D(Y +Y| = 0) + 2 D(ÿ #Y| Y =1,,
4

---

Published as a conference paper at ICLR 2020
which means that the loss function gives equal importance to the classification error from both groups.
Note that the BERs in the second term of (2) are over DV, y E {0. 10. Roughly speaking, the second term encourages alignment of the the conditional distributions 9; 9;D and g,D4 for y {0, 1]. The following proposition shows that a perfect conditional alignment of the representations also implies that any classifier based the representations naturally satisfies the equalized odds criterion:
Proposition 3.1. For g X 2, if drv (gg Di 9: D 0, Vy {0,1), then for any classifier h: 2 + {0, 13. h a satisfies equalized odds.
To understand why we aim for conditional alignment of distributions instead of aligning the marginal feature distributions, the following proposition characterizes why such alignment will help to escape the previous trade-off:
Proposition 3.2. For g : X + 2, if drv dry(g,DD..;DD - Vy {0, 13, then for any classifier h: 2 + {0, 1}. drv ((h 9)4Du, (h g):D1) S ABR (Do: D1).
As corollary, this implies that the lower bound given in Theorem align the conditional distributions of representations:
2.1 now vanishes if we instead
Errp, (h o g) + Errp, (h - g) 2 ABR (Do, Di) - drv((h g): Do. (h g); = 0,
where the first inequality is due Lemma 3.1 (Zhao Gordon 2019) and the triangle inequality by the drv(:.)) distance. Of course, the above lower bound can only serve necessary condition but not sufficient to ensure a small joint error across groups. Later (c.f. Theorem 3.2) we will show that together with small BER on the target variable, it becomes sufficient condition as well.
3.2 THE PRESERVATION OF DEMOGRAPHIC PARITY GAP AND SMALL JOINT ERROR
In this section show that learning representations by aligning the conditional distributions across groups cannot increase the DP gap as compared to the DP gap of Y. Before we proceed, we first introduce a metric to measure the deviation of predictor from satisfying demographic parity:
Definition 3.1 (DP Gap). Given a joint distribution 2, the demographic parity gap of a classifier Φ is ADP ( |Do(Y = 1) - 1 1)].
Clearly, if DP P 0, then f satisfies demographie parity. To simplify the exposition, let %a == DY = 0), Va (0. We first prove the following lemma:
Lemma 3.1. Assume the conditions in Proposition
3.1 hold and let f h(g(X)) be the classifier,
then (D = y) D ( y)1 < Iro -ml (D
DD y)), Vy E 1).
Lemma 3.1 gives an upper bound on the difference of the prediction probabilities across different subgroups. Applying Lemma 3.1 twice for y = 0 and y = 1, we can prove the following theorem:
Theorem 3.1. Assume the conditions in Proposition 3.1 hold and let Ý = h(g(X)) be the classifier,
then Apr ( ABn(Do, D,) ADr(Y).
Remark Theorem 3.1 shows that aligning the conditional distributions of representations between groups will not add more bias in terms of the demographic parity gap. In particular, the DP gap of any classifier that satisfies equalized odds will be at most the DP gap of the perfect classifier. This is par- ticularly interesting as it is well-known in the literature (Barocas et al., 2017) that demographic parity is not compatible with equalized odds except in degenerate cases. Despite this result, Theorem 3.1 says that we can still achieve equalized odds and simultancously preserve the DP gap.
In Section 3.1 we show that aligning the conditional distributions of representations between groups helps reduce the lower bound of the joint error, but nevertheless that is only a necessary condition. In the next theorem we show that together with a small Type-I and Type-II error in inferring the target variable Y. these two properties are also sufficient to ensure a small joint error across different demographic subgroups.
Theorem 3.2. Assume the conditions in Proposition 3.1 hold and let & -= =h(g(X)) be the classifier, then Errp, ( + ErrD, (9) 2BERp( Y).).
5

---

Published as a conference paper at ICLR 2020
The above bound means that in order to achieve small joint error across groups, it suffices for to minimize the BER if a classifier satisfies equalized odds. Note that by defimition, the BER in the bound equals to the sum of Type-I and Type-Il classification errors using Y as a classifier. Theorem 3.2 gives an upper bound of the joint error across groups and also serves motivation for us to design the optimization formulation 2 that simultaneously minimizes the BER and aligns the conditional distributions.
3.3 CONDITIONAL ALIGNMENT AND BALANCED ERROR RATES LEAD TO SMALL ERROR
In this section we will see that a small BER and equalized odds together not only serve as guarantee of small joint error, but they also lead a small error gap between different demographic subgroups. Recall that we define == DY 0), Va E {0, 1}. Before we proceed, we first formally define the accuracy gap and equalized odds gap of a classifier Y:
Definition 3.2 (Error Gap). Given joint distribution D, the error gap of a classifier Y is AEre (Y) [Do(Y # Y)- - ( / Y)).
Definition 3.3 (Equalized Odds Gap). Given a joint distribution D, the equalized odds gap of a classifier Ý is Ago (9) == (0.1) (D = D = =
By definition the error gap could also be understood as the accuracy parity gap between different subgroups. The following theorem characterizes the relationship between error gap, equalized odds gap and the difference of base rates across subgroups:
Theorem 3.3. For any classifier y, ABrr ( z ABR Di) BERD(
As a direct corollary of Theorem 3.3 if the classifier Y satisfies equalized odds, then ABO ( = 0. In this case since ABn (Do, D1) is constant, minimizing the balanced error rate BER (Y Y also leads to minimizing the error gap. Furthermore, we combine Theorem 3.2 and Theorem 3.3 together, we can guarantee that each of the errors cannot be too large:
Corollary 3.1. For any joint distribution D and classifier Y, if Ý satisfies equalized odds, then max(Errg) (Y), ErrD, (Y)} S ABR Di) BYR || Y)/2 + BER Y)
Remark It is a well-known fact that out of the three fairness criteria, i.e., demographic parity, equalized odds, and predictive rate parity, any two of them cannot hold simultaneously (Barocas) jct al. (017)) except in degenerate cases. By contrast, Theorem [33 suggests it is possible to achieve both equalized odds and accuracy parity. In particular, among all classifiers that satisfy equalize odds, it suffices minimize the sum of Type-I and Type-Il error BER Y') in order to achieve accuracy parity. It is also worth pointing out that Theorem 3.3 provides only an upper bound, but not necessarily the tightest one. In particular, the error gap could still be 0 while BER (Y || Y) is greater than O. To see this, we have
ERTD, (P) = Do = 0) D = Y = 0) 0) Do -)) Do(P 0 1) ERTD, ( (Y 0) DI 1 Y 0) DiY = -. = Y
Now if the predictor y satisfies equalized odds, then
Do Y 0) ( = Y = -) 1 = 0),
Do = 0 Y = 1) = DD 0 = 1) = = =
Hence the error gap A ()) admits the following identity:
AErr (8) D(P = Y (P = 0) - DD = 0)) +D( = - 1) = - =1)
A Di) D(P
= -))== = =
Y
= ABR D1)
FPR - FNR(
In other words, if the predictor Ý satisfies equalized odds, then in order to have equalized accuracy, Y only needs to have equalized FPR and FNR globally when the base rates differ across groups This is much weaker condition to ask for than the one asking BER ( Y| 0.

---

Published as a conference paper at ICLR 2020
3.4 PRACTICAL IMPLEMENTATION
We cannot directly optimize the proposed optimization formulation (2) since the binary 0/1 loss is NP- hard to optimize, or even approximately optimize over wide range of hypothesis classes (Ben-David ct al. 2003). However, observe that for any classifier Y and y E {0, 1). the log-loss (cross-entropy
loss) CEpu (Y) || Y) is a convex relaxation of the binary loss:
D( + Y y) D( # Y = v)
CEpN (? Y)
(4)
D(Y y)
D(Y = y)
Hence in practice relax the optimization problem
cost-sensitive cross-entropy loss
minimization problem, where the weight for each class given by the inverse marginal probability of the corresponding class. This allows us equivalently optimize the objective function without explicitly computing the conditional distributions.
EMPIRICAL STUDIES
In light of our theoretic findings, in this section we verify the effectiveness of the proposed algorithm in simultancously ensuring equalized odds and accuracy parity using real-world datasets. We also analyze the impact of imposing such parity constraints on the utility of the target classifier, as well as its relationship to the intrinsic structure of the binary classification problem, e.g., the difference of base rates across groups, the global imbalance of the target variable, etc. We analyze how this imbalance affects the mullity-farrest trade-off. As we shall
shortly, will empirically demonstrate that, in many cases, especially the ones where the dataset is imbalanced in terms of the target variable, this will inevitably compromise the target utility. While for balanced datasets, this trend is less obvious: the proposed algorithm achieves a better Mairness-utilii trade-off when compared with existing fair representation learning methods and we can hope to achieve fairness without sacrificing too much on utility.
Table 1: Statisties about the Adult and COMPAS datasets.
Train / Test
Do(Y 1)
Di(Y= 1)
ABR D:)
D(Y 1)
D(A 1)
Adult
30, 1/166/15 122//5,0000 060 4,320/1 152
0.310
0.113
0.196
0.246
0.673
COMPAS
0.400
0.529
0.129
0.467
0.514
4.1 EXPERIMENTAL SETUP
To this end, we perform experiments two popular real-world datasets in the literature of algorithmic fairness, including an income-prediction dataset, known as the Adult dataset, from the UCI Machine I Learning Repository (Dua & Graff 2017). and the Propublica COMPAS dataset (Dieterich et al. 2016). The basic statistics of these two datasets are listed in Table
Adult Each instance in the Adult dataset describes an adult, e.g., gender, education level, age, etc, from the 1994 US Census. In this dataset we use gender the sensitive attribute, and the processed data contains 1 114 attributes. The target variable (income) is also binary: if 2 5OK/year otherwise 0. For the sensitive attribute A, A 0 means male otherwise female. From Table we can see that the base rates are quite different (0.310 vs. 0. 0.1 across groups in the Adult dataset. The dataset is also imbalanced in the sense that only around 24.6% of the instances have target label 1. Furthermore, the group ratio is also imbalanced: roughly 67 3% of the data are male.
The goal of the COMPAS dataset is binary classification whether criminal defendant will recidivate within two years or not. Each instance contains 12 attributes, including age, race, gender, number of prior crimes, etc. For this dataset, iff recidivism. The base rates are different across
COMPAS
the race (white A 0 vs. black A 1)
as our sensitive attribute and target variable groups, but the COMPAS dataset is balanced in both the target variable and the sensitive attribute.

---

Published as a conference paper at ICLR 2020
To validate the effect of ensuring equalized odds and aceuracy parity, for each dataset, perform controlled experiments by fixing the baseline network architecture so that shared among all the fair representation learning methods. We term the proposed method CFAIR (for conditional fair representations) that minimizes conditional errors both the target variable loss function and adversary loss function. To demonstrate the importance of using BER in the loss function of target variable, we compare with variant of CFAIR that only uses BER in the loss of adversaries, denoted CFAIR-EO. To the relative effect of using cross-entropy loss vs L1 loss, we also show the results of LAFTR (Madras et al., 2018), a state-of-the seffthe-art art method for learning fair representations. Note that LAFTR is closely related to CFAIR -FAIR-EOOAE but slightly different: LAFTR uses global cross- entropy loss for target variable, but conditional L1 loss for the adversary. Also, there is only one adversary LAFTR, while there are two adversaries, one for Do and one for DD. both CFAIR and CFAIR-EO. Lastly, we also present baseline results of FATR (Edwards & Storkey 2015), which aims for demographic parity representations, and NODEBIAS, the baseline network without any fairness constraint. For all the fair representation learning methods, we use the gradient reversal layer (Ganin et al. 2016) to implement the gradient descent ascent (GDA) algorithm to optimize the minimax problem. All the experimental details, including network architectures, learning rates, batch sizes, etc. are provided in the appendix.
4.2 RESULTS AND ANALYSIS
we show the error gap ÅEr equalized odds gap Ago, demographic parity gap ADP and the joint error across groups ErTp + ErT, of the aforementioned fair representation learning algorithms on both the Adult and the COMPAS datasets. For each algorithm and dataset, we also gradually increase the value of the trade-off parameter À and compute the corresponding metrics.
In Figure 1 and Figure 2
Figure 1: The error gap Agre, equalized odds gap Ago, demographic parity gap Apr and joint error Eryg Err, on the Adult dataset with À {0.1, 1.0, 10.0, 100.0, 1000.0).
3.
Figure 2: The error gap Aerr equalized odds gap AEO, demographic parity gap App and joint error Erro Err, on COMPAS dataset with E 1.0,, 10.0).
Adult Due to the imbalance of A in the Adult dataset, in the first plot of Figure I we can see that all the algorithms except CFAIR have large error gap around 0.12. that the error gap of CFAIR when X = 1e3 almost reduces to O, confirming the effectiveness of our algorithm in ensuring accuracy parity. From the second plot, we can verify that all the three methods, including CFAIR, CFAIR-BO and LAFTR successfully ensure small equalized odds gap, and they also decrease demographic parity gaps (the third plot). FAIR the most effective one in mitigating App since its objective function directly optimizes for that goal. Note that from the second plot we can also confirm that CFAIR- BO is more effective than LAFTR reducing Apo- The reason two-fold. First, CFAIR- EO uses two distinct adversaries and hence it effectively competes with
comparison, observe
8

---

Published as a conference paper at ICLR 2020
stronger adversaries than LAFTR. Second, CFAIR-EO EO uses the cross-entropy loss instead of the L1 loss for the adversary. and it is well-known that the using the cross-entropy loss) is asymptotically efficient and optimal. On the other hand, since the Adult dataset is imbalanced (in terms of Y), using BER in the loss function of the target variable can thus to large extent hurt the utility, and this is also confirmed from the last plot, where show the joint error.
likellooo estimator (equivalent to
The first three plots of Figure 2 once again verify that CFAIR successfully leads to reduced error gap, equalized odds gap and also demographic parity gap. These experimental results are consistent with our theoretical findings where we show that if the representations satisfy equalized odds, then its ADP cannot exceed that of the optimal classifier, as shown by the horizontal dashed line in the third plot. In the fourth plot of Figure 2 we can see that as we increase X, all the fair representation learning algorithms sacrifice utility. However, in contrast to Figure [ here the proposed algorithm CFAIR has the smallest trade-off: this shows that CFAIR is particularly suited in the cases when the dataset is balanced and we would like to simultaneously ensure accuracy parity and equalized odds. As a comparison, while CFAIR-EO is still effective, it is slightly worse than CFAIR in terms of both ensuring parity and achieving small joint error.
COMPAS
RELATED WORK
Algorithmic Fairness In the literature of algorithmic fairness, two key notions of fairness have been
extensively proposed and explored, i.e., group fairness, including various variants defined in Section 2 and individual fairness, which means that similar individuals should be treated similarly. Due the complexity in defining a distance metric to measure the similarity between individuals (Dwork et al.
2012), most recent research focuses on designing efficient algorithms to achieve group fairess (Zemel
et al. 2013 Zafar et al. 2015 Hardt et al. 2016: Zafar et al. 2017 Madras et al. 2018 Creager et al. 2019 Madras et al./ 2019). In particular, Hardt et al. (2016) proposed post-processing technique to achieve equalized odds by taking as input the model's 's prediction and the sensitive attribute. However, the post-processing technique requires access to the sensitive attribute during the inference phase, which is often not available in many real-worle scenarios. Another line of work uses causal inference
to define notions of causal fairness and to formulate procedures for achieving these notions (Zhang al. 2018 Wang et al.) 2019 Madras et al. 2019 Kilbertus et al.) 2017 Kusner et al. 2017 Nabi & Shpitser 2018). These approaches require making untestable assumptions. Of particular note is the observation in Coston et al. (2019) that faimess-adjjsttmen adjustment procedures based on Y in settings with treatment effects may lead to adverse outcomes. To apply our method in such settings, we would need match conditional counterfactual distributions, which could be a direction of future research.
Theoretical Results on Fairness Theoretical work studying the relationship between different kinds of fairness notions are abundant. Motivated by the controversy of the potential discriminatory bias in recidivism prediction instruments, [houldechova (2017) showed an intrinsic incompatibility between equalized odds and predictive rate parity. In the seminal work Kleinberg et al. (2016), the authors demonstrated that when the base rates differ between different groups, then non-perfect classifier cannot simultancously be statistically calibrated and satisfy equalized odds. In the context of cost-sensitive learning, Menon & Williamson (2018) show that if the optimal decision function is dissimilar to a fair decision, then the fairness constraint will not significantly harm the target utility. The idea of reducing fair classification to cost-sensitive learning is not new. (Agarwal et al. (2018) explored the connection between fair classification and a sequence of cost-sensitive learning problems where each stage corresponds to solving linear minimax saddle point problem. In recent work (Zhao & Gordon 2019), the authors proved a lower bound on the joint error across different groups when classifer satisfies demographic parity. They also showed that when the decision functions are close between groups, demographic parity also implies accuracy parity. The theoretical results in this work establish a relationship between accuracy parity and equalized odds: these two fairness notions are fundamentally related by the base rate gap and the balanced error rate. Furthermore, we also show that for any predictor that satisfies equalized odds, the balanced error rate also serves an upper bound on the joint error across demographic subgroups.
Fair Representations Through the lens of representation learning, recent advances in building fair algorithmic decision making systems focus using adversarial methods to learn fair representations

---

Published as a conference paper at ICLR 2020
that also preserve sufficient information for the prediction task (Edwards & Storkey 2015 Beutel eet al. 20177 [ et al., 2018; [Mdrras et al. 2018 Adel et al. 2019). In nutshell, the key idea is to frame the problem of learning fair representations
two- -lo-peayer game, where the data owner is competing against an adversary. The goal of the adversary is to infer the group attribute as much possible while the goal of the data owner is remove information related to the group attribute and simultancously to preserve utility-related information for accurate prediction. Apart from using adversarial classifiers enforce group fairness, other distance metrics have also been used to learn fair representations, e.g., the maximum mean discrepancy (Louizos et al., 2015), and the Wasserstein- 1 distance (Jiang et al. 2019). In contrast to these methods, in this paper we advocate for optimizing BER on both the target loss and adversary loss in order to simultaneously achieve accuracy parity and equalized odds. We also show that this leads to better utility-fairness trade-off for balanced datasets.
CONCLUSION AND FUTURE WORK
In this paper we propose a novel representation learning algorithm that aims to simultaneously ensure accuracy parity and equalized odds. The main idea underlying the design of our algorithm is to align the conditional distributions of representations (rather than marginal distributions) and use balanced error rate (i.e., the conditional error) on both the target variable and the sensitive attribute. Theoretically, we prove how these two concepts together help to ensure accuracy parity and equalized odds without impacting demographic parity, and we also show how these two can be used to give guarantee on the joint error across different demographic subgroups. Empirically, we demonstrate on Two real-world experiments that the proposed algorithm effectively leads to the desired notions of fairness, and also leads to better utility-faimest trade-off on balanced datasets.
Calibration and Utility Our work takes step towards better understanding the relationships between different notions of fairness and their corresponding trade-off with utility. In some scenarios, e.g., the COMPAS tool, desired to have a decision making system that also well calibrated. While it is well-known that statistical calibration is not compatible with demographic parity or equalized odds, from a theoretical standpoint it is still not clear whether calibration will harm utility and if what is the fundamental limit of a calibrated tool on utility.
Fairness and Privacy Future work could also investigate how to make use of the close relationship between privacy and group fairness. a colloquial level, fairness constraints require a predictor to be (to some extent) agnostic about the group membership attribute. The membership query attack in privacy asks the same question is it possible to guarantee that even an optimal adversary cannot steal personal information through inference attacks. Prior work (Dwork et al. 2012) has described the connection between the notion of individual fairness and differential privacy. Hence would be interesting to exploit techniques developed in the literature of privacy to develop more efficient fairness-aware learning algorithms. On the other hand, results obtained the algorithmic fairness literature could also potentially lead to better privacy-preservine preserving machine learning algorithms (Zhao et al. 2019).
ACKNOWLEDGMENTS
HZ and GG would like to acknowledge support from the DARPA XAI project, contract #FA87501720152 and an Nvidia GPU grant. HZ would also like thank Richard Zemel, To- niann Pitassi, David Madras and Elliot Creager for helpful discussions during HZ's visit to the Vector Institute.
10

---

Published as a conference paper at ICLR 2020
REFERENCES
Tameem Adel, Isabel Valera, Zoubin Ghahramani, and Adrian Weller. One-network adversarial fairness. In 33rd AAAI Conference on Artificial Intelligence, 2019.
Alekh Agarwal, Alina Beygelzimer, Miroslav Dudik, John Langford, and Hanna Wallach. A reductions approach to fair classification. In International Conference on Machine Learning, pp. 60-69; 2018.
Solon Barocas, Moritz Hardt, and Arvind Narayanan. Fairness in machine learning. NIPS Tutorial, 2017.
Shai Ben-David, Nadav Eiron, and Philip M Long. On the difficulty of approximately maximizing agreements. Journal of Computer and System Sciences, 66(3):496-514, 2003.
Alex Beutel, Jilin Chen, Zhe Zhao, and Ed H Chi. Data decisions and theoretical implications when adversarially learning fair representations. arXiv preprint arXiv:1707.00075 2017.
Toon Calders and Sicco Verwer. Three naive bayes approaches for discrimination-fiee free classification.
Data Mining and Knowledge Discovery, 21(2):277-292, 2010.
Toon Calders, Faisal Kamiran, and Mykola Pechenizkiy. Building classifiers with independency constraints. 2009 IEEE International Conference on Data Mining Workshops, pp. 13-18. IEEÉ, 2009.
Alexandra Chouldechova. Fair prediction with disparate impact: A study of bias in recidivism prediction instruments. Big data, 5(2):153-163, 2017.
Alexandra Chouldechova and Aaron Roth. The frontiers of faimess in machine learning. arXiv 2018.
preprint
Sam Corbett-Davies and Sharad Goel. The measure and mismeasure of fairnss:: A critical review of fair machine learning. arXiv preprint arXiv: /808.00003000 2018.
Amanda Coston, Alexandra Chouldechova, and Edward H Kennedy. Counterfactual risk assessments, evaluation, and fairness. arXiv preprini arXiv: (ee1//99900000 2019.
Elliot Creager, David Madras, Joern-Henrik Jacobsen, Marissa Weis, Kevin Swersky, Toniann Pitassi, and Richard Zemel. Flexibly fair representation learning by disentanglement. In International Conference on Machine Learning, pp. 1436-1445, 2019.
William Dieterich, Christina Mendoza, and Tim Brennan. Compas risk scales: Demonstrating accuracy equity and predictive parity. Northpoint Inc, 2016.
Dheeru Dua and Casey Graff. UCI machine learning repository, 2017. URL http:://rcchive ics. www.cciceo edu/ml
Cynthia Dwork, Moritz Hardt, Toniann Pitassi, Omer Reingold, and Richard Zemel. Faireess through awareness. In Proceedings of the 3rd innovations in theoretical computer science conference, pp. 214-226. ACM, 2012.
Harrison Edwards and Amos Storkey. Censoring representations with an adversary. arXiv preprint arXiv:1511.08897, 2015.
Michael Feldman, Sorelle A Friedler, John Moeller, Carlos Scheidegger, and Suresh Venkatasubra- manian. Certifying and removing disparate impact. In Proceedings of the 21th ACM SIGKDD International Conference Knowledge Discovery and Data Mining, pp. 259-268. ACM, 2015.
Yaroslav Ganin, Evgeniya Ustinova, Hana Ajakan, Pascal Germain, Hugo Larochelle, François Laviolette, Mario Marchand, and Victor Lempitsky. Domain-adversarial training of neural networks. The Journal of Machine Learning Research, 17(1):2096-000 2030, 2016.
Moritz Hardt, Eric Price, Nati Srebro, et al. Equality of opportunity in supervised learning. In Advances in neural information processing systems, pp. 3315-3323, 2016.

---

Published as a conference paper at ICLR 2020
Ray Jiang, Aldo Pacchiano, Tom Stepleton, Heinrich Jiang, and Silvia Chiappa. Wasserstein fair classification. arXiv preprint IrXiv:197..1209, 2019.
James E. Johndrow, Kristian Lum, et al. An algorithm for removing sensitive information: application to race-independent recidivism prediction. The Annals of Applied Statistics, 13(1):189-22 2019.
Faisal Kamiran and Toon Calders. Classifying without discriminating. In 2009 2nd International Conference on Computer, Control and Communication, pp. 1-6. IEEE, 2009.
Toshihiro Kamishima, Shotaro Akaho, and Jun Sakuma. Fairness- learning through regular- ization approach. In 2011 IEEE Ith International Conference on Data Mining Workshops, pp-
643-650. IEBE, 2011.
Niki Kilbertus, Mateo Rojas Carulla, Giambattista Parascandolo, Moritz Hardt, Dominik Janzing, and Bernhard Schölkopf. Avoiding discrimination through causal reasoning. Advances in Neural Information Processing Systems, pp. 656-666 2017.
Jon Kleinberg, Sendhil Mullainathan, and Manish Raghavan. Inherent trade-offs in the fair determi- nation of risk scores. arXiv preprint arXiv: M.Xiv::609.0000 /609.05807 2016.
Matt J Kusner, Joshua Loftus, Chris Russell, and Ricardo Silva. Counterfactual fairness. In Advances in Neural Information Processing Systems, pp. 4066-4076, 2017.
Christos Louizos, Kevin Swersky, Yujia Li, Max Welling, and Richard Zemel. The variational fair autoencoder. arXiv preprint arXiv: 1.000000 2015.
David Madras, Elliot Creager, Toniann Pitassi, and Richard Zemel. Learning adversarially fair and transferable representations. In International Conference on Machine Learning, pp. 3381 3381-3390, 2018.
David Madras, Elliot Creager, Toniann Pitassi, and Richard Zemel. Faimess through causal awareness: Learning causal latenl-variable models for biased data. Proceedings of the Conference on Fairness, Accountability, and Transparency, pp. 349-358. ACM, 2019.
Aditya Krishna Menon and Robert C Williamson. The cost of fairesss in binary classification. In Conference on Fairness, Accountability and Transparency, pp. 107-118, 2018
Razich Nabi and Ilya Shpitser. Fair inference outcomes. In Thirty-Second AAAI Conference Artificial Intelligence, 2018.
Arvind Narayanan. Translation tutorial: 21 fairness definitions and their politics. Proc. Conf.
Fairness Accountability Transp., New York, USA, 2018.
Yixin Wang, Dhanya Sridhar, and David M Blei. Equal opportunity and affinmative action via counterfactual predictions. arXiv preprint arXiv: 1905. 10870, 2019.
Muhammad Bilal Zafar, Isabel Valera, Manuel Gomez Rodriguez, and Krishna P Gummadi. Fairness constraints: Mechanisms for fair classification. arXiv preprint arXiv: /507005259, 2015.
Muhammad Bilal Zafar, Isabel Valera, Manuel Gomez Rodriguez, and Krishna P Gummadi. Fairness beyond disparate treatment & disparate impact: Learning classification without disparate mistreat- ment. In Proceedings of the 26th International Conference on World Wide Web, pp. 1171-1180. International World Wide Web Conferences Steering Committee, 2017.
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 adversarial learning. In Proceedings of the 2018 AAAI/ACM Conference on AI, Ethics, and Society, pp. 335- 340. ACM, 2018.
Han Zhao and Geoffrey J Gordon. Inherent tradeoff's in learning fair representations. In Advances in neural information processing systems, 2019.
Han Zhao, Jianfeng Chi, Yuan Tian, and Geoffrey Gordon. Adversarial privacy preservation under attribute inference attack. arXiv preprint arXiv: 199999009222. 2019.
12

---

Published as a conference paper at ICLR 2020
A PROOFS
A.1 PROOF OF PROPOSITION 3.1
Proposition 3.1. For g X x 2, if drv ,;Dy) Vy {0, 1}, then for any classifier h: 2 + {0, 1}. h g satisfies equalized odds.
Proof. To prove this proposition, we first show that for any pair of distributions D, D' over and any hypothesis h 2 - (0, 1), drv (h,,2, D2) S (Dv Note that since h is hypothesis, there are only two events in the induced probability space, i.e., h(-) = 0 or h(-) = 1. Hence by definition of the induced (pushforward) distribution, we have:
drv(hgD, hyD')
(D(E) (EE)
max E (0). or (1)
sup E measurable subset of 2
D(E) (E))
dD, D').
Apply the above inequality twice for y E 10:
S drv((h D) (h D)) & drv (rv(g; = 0,
meaning
drv((h g) (h g)) = 0,
which further implies that h(x()) is independent of A given Y since h(g()) is binary.
A.2 PROOF OF PROPOSITION
Proposition 3.2. For g X + 2, if dlv Dg.g = O, Vy {0, 1}, then for any classifier
h: Z + {0, 11. drv ((h o g)4Du, (h g) D1) < ABR (Do Dz).
Proof. Let γ = (h o (X) and note that Ý is binary, we have
1 d o Do. (h D1) 1/ (Do 0) (F = -0]+ + = 11) = =1))
Now, by Proposition 3.1 if drv (g) Dj DY) = 0, vy E {0, 1}. follows that drv ((h o g) (ho
D) = 0, Vy E { as well. Applying Lemma 3.1 know that by E {0.
Po(( - -) = = < Do 0) D2Y = 0)1 (D = w) + + = -))
Hence,
drv((h o (ho
1 (Do 0) - -2 =
= 1) - =1]) - 0)]
DolY 0)
- Di = 0)]
(DD' +D 0)) (D = 1) = =1))
2 Doo( 0) - (Y = 0)1
(DD' 0) + DD = 1)) (D = 0) + D 1))
2
(Do(Y 0) - Dí (Y= 0)1
2
2
IDo(Y- 0) -Y 0)l
ABn (Do, D1).
A.3 PROOF OF LEMMA 3.1
Recall that we define 7a PY 0), Va (0,
Lemma 3.1. Assume the conditions in Proposition 3.1 hold and let γ -h(g(X)) be the classifier,
then ( v) - ( v) < Imm mml. (Do v) DD =w)), Vy E (0,1).
13

---

Published as a conference paper at ICLR 2020
Proof.
To bound (Do(Y- () -Dy- v)l. for y {0,1), 13, by the law of total probability,
have:
IDo(P- = -y)- -D = -))l =
=I(D8(8 DD =0) =0) +D(PP ->)((>==)Dpp) y)) = =1) - -D) y) + +D 0)
UY = =1)]
I <110D0(8 = =)) -7I = =
y) -1 (1- = y
where the above inequality is due to the triangular inequality. Now apply Proposition know that y satisfies equalized odds,
3 we
have D8 y) DP( y) D Do y) and
D8 =y) = DP = v) = DD = y). leading to:
70 - -- -D0 y) + (1 70) (1 n) D ( = v)
=1o 1 (D" -) + ( -))
which completes the proof.
A.4 PROOF OF THROREM 3.1
Theorem 3.1. Assume the conditions in Proposition 3.1 hold and let y = h(g(X)) be the classifier,
then pPr S (B, D1) = (Y)
Proof. To bound ADP((Y) realize that |Do 0) - - 1)). so we can rewrite the DP gap as follows:
ADP = 2 (IDo =0 -D = =0] + 11) = 1)1)
Now apply Lemma 3.1 twice for y = 0 and y = 1, we have:
[D =0 - D1 ( = 0)] S Ioo - ml (D = =0 + DD =0)
[P =) 1) D, =1] S I/o ml (D"(P =1) + DDP = 1))-
Taking sum of the above two inequalities yields
[Do( 0) - ( 0) + 1Po(P - D - = 11]
S Yo m1 (DD =0 + D 0)) + (D' =1))
70 n1 (DD = + D 1)) -) -1))
2/10 71
Combining all the inequalities above, we know that
ADp(A) (IDa(F = =) 10 Di = 0] Po(E 1) -D 1))
- 170 71|
= iDo = 0) - Di(Y = 0)1
IDo(Y =1) - -Di(Y- = 1)
(Do, Di) = (Y),Y),
completing the proof.
A.5 PROOF OF THEOREM 3.2
Theorem 3.2. Assume the conditions in Proposition 3.1 hold and let 8 - =h(g(X)) be the classifier,
then Erro, ( + ErrD, (9) < 2B Y).).
14

---

Published as a conference paper at ICLR 2020
Proof. First, by the law of total probability,, we have:
EITD, ( ErrD, (Y) Du * Y) + D1 + P)
= DP = O)Do = 1) + D8 = 1)Do(Y 0) 0) DQ 1)D)) =0)
=
Again, by Proposition 3.1 the classifier 4 (h o (X) satisfies equalized odds, so we have
(Y 0) = D2 DD 0). D8( 1) Do(Y 1). D1(P = 0) DI 0) and
D9(Y- 1) -D 1):
= =D'(P = 0)Do(Y = 1) + D = 1)Db(Y = 0) D = 0)D = =)) 1)D =0)
-D 0) (Do = =1) 1)+ Di 1)) DD (Do(Y = + D2 =0)
- ( = 0) + 2D 1)
2 ( || (),),
which completes the proof.
A.6 PROOF OF THEOREM 3.3
Theorem 3.3. For any classifier Y, A (Y) S ABR Di) BER II + 2Y)
Before we give the proof of Theorem 3.3 first prove the following two lemmas that will be used in the following proof.
Lemma A.1. Define Vaa := Da = 0), Va E {0, 1}. then D8 = 1) - DP = 1) s
ho ml -D = 1) + 70 = 1)Aao(()) 7 = (Y).
Proof. In order to prove the upper bound in the lemma, it suffices if we could give the desired upper bound for the following term
Do0 = 1) D1 18 = 1) - 10%0 - D = 1)|
$ (10 = =1 - DD9 = 1)) (1o - nD)D = 1)|
= (P =1 - -p = 1))
(D = =1) - DD = 1))
following which we will have:
hoD 1) n DP =1] $ 16 - Df 1)1
(P 1) -D Dy 1)) - 71 -1) (0(8=11))) 1))/-
1)
and an application of the Bayes formula could finish the proof. To do so, let us first simplify
D 1) DÝ = =). Applying the Bayes's 's formula, we know that:
DP = - -y =1) = (D) = 1) - D8 = (A (A=0)) - -)
DP 1) (D 14 = 0) + DPPP = 1YD
DP( = (A = 1)
(A - (=AAA=1) -1)
DP(E =1)).
Similarly, for the second term DP = 1) - D' 1), we can show that:
DI 1) 1)
- Df = 1) = (A=
= 0) () = 1) -D = =1).
Plug these two identities into above, we can continue the analysis with
(P = 1) - - = 1)) - 71 (D = -) -f = 1
= 1o00 (A = 1P = 1) DP = =1)) - 74=
= 1) - - =1))
< (A = 18 1) DI = =1)| + (A= = =1) - -8 = =1)
< (A = l)ABo + +
D' (A 0)ABo
The first inequality holds by triangular inequality and the second one holds by the definition of equalized odds gap.
15

---

Published as a conference paper at ICLR 2020
Lemma A.2. Define "aa == Da 0), va {0, 1), then (1 (11--000 (o) 0) (1- (1
0)1 S 170- 7il D (Y = 0) + (1 - -00 (A
l)ABo 1)) (A (Y)
Proof. The proof of this lemma is symmetric to the previous one, so we omit it here.
Now we are ready to prove Theorem 3.3
Proof of Theorem 3.3 holds for (0. J:
First, by the law of total probability, it is easy to verify that following identity
Da +Y) D.YY = -1-77) 0) 7) =1).
=)
Using this identity, to bound the error gap, we have:
IDo(Y # 8) Di # 9) = ((1 (0) = 0) 7o 18 = 1)) - ((1 -(1-))2 =) + + = 1))
$ 1 1) 7 1) + (L) = -) =
Invoke Lemma A. and Lemma A.2 to bound the above two terms:
IDo(Y # 8)- D2 + 8)1
s 1 y = -1)-71 1
[A= s (A 11)rro (V) + (A)=
+ - 10) (A 1) 1)A (1-7))0'(A (A=0)
+ ho 11 1D 1) + +/1 - 1D = =0),
Realize that both 70. 71 E [0, 1]. we have:
$ D = 10 ( +
+ D* = 1)Amo(P) + (D = 0)Ano
+ +1100 71 DD (8- 1) 110 1D (8 =0)
-4 (8) + t/ - 1/ = + 11000011 7 DD (f(=0)) =0)
2AEo ( ABRRDDD Di) -BER ||Y,,
which completes the proof.
We also provide the proof of Corollary 3.1
Corollary 3.1. For any joint distribution and classifier Y. if y satisfies equalized odds, then max(Frre (P), Errp, ( < ABn,D,, Dj) (ER || Y)/2 + BER Y).
Proof. We first invoke Theorem 3.3
if Y satisfies equalized odds, then AgO ( O, which implies: AEre ( ErrD, (Y) ErTp, ( I ABR (Do, Dz) BER ( Y).
On the other hand, by Theorem 3.2 we know that
Errp, ( + Ertp, (9) < 2BER ( Y)
Combine the above two inequalities and recall that max(a, b) = (/a + b) + -l) Va yielding:
max (ETTD,(()) EIT,,, (8)) |ETD, (P) EITD (i) | + EITD, (9) + ErTZ, (8)
2
ABR (Do, Di) BBRD y || + 2BER ||Y)
2
(BR(Do, D1) BERD( || Y)/2 + BERD |lY)
completing the proof.
16

---

Published as a conference paper at ICLR 2020
B EXPERIMENTAL DETAILS
B.1 THE ADULT EXPERIMENT
For the baseline network NODEBIAS, we implement a three-layer neural network with ReLU as the hidden activation function and logistic regression the target output function. The input layer contains 114 units, and the hidden layer contains 60 hidden units. The output layer only contain one unit, whose output is interpreted as the probability D(Ý = X = z).
For the adversary in FAIR and LAFTR, again, the input layer of the adversary is the hidden representations of the baseline network that contains 60 units. The hidden layer of the adversary network contains 50 units, with ReLU activation. Finally, the output the adversary also contains one unit, representing the adversary's 's inference probability
three-layer feed-forward network. Specifically,
D(Ā= = 1 Z = z). The network structure of the adversaries in both CFAIR and CFAIR-EO are exactly the same as the one used FAIR and LAFTR, except that there are two adversaries, one for
(² = Z = 2) and one for D' (A Z z).
The hyperparameters used in the experiment are listed in Table 2
Table 2: Hyperparameters used in the Adult experiment.
Optimization Algorithm
AdaDelta
Learning Rate
1.0
Batch Size Training Epochs X A {0.1, 1.0, 10.0, 100.0, 1000.0}
512
100
B.2 THE COMPAS EXPERIMENT
Again, for the baseline network NODEBIAS, we implement a three-layer neural network with ReLU as the hidden activation function and logistic regression as the target output function. The input layer contains 11 units, and the hidden layer contains 10 hidden units. The output layer only contain one unit, whose output is interpreted as the probability of D(Ý = - | z).
For the adversary in FAIR and LAFTR, again, the input layer of the adversary is the hidden representations of the baseline network that contains 60 units. The hidden layer of the adversary network contains 10 units, with ReLU activation. Finally, the output the adversary also contains one unit, representing the adversary's 's inference probability
three-layer feed-forwatt network. Specifically,
D(Ā = 1 Z = 2). The network structure of the adversaries in both CFAIR and CFAIR-EO are exactly the same as the one used FAIR and LAFTR, except that there are two adversaries, one for
(A = | Z = 2) and one for D3 D²(AA Z = z).
The hyperparameters used in the experiment are listed in Table 3
Table 3: Hyperparameters used in the COMPAS experiment.
Optimization Algorithm Learning Rate
AdaDelta
1.0
Batch Size
512
Training Epochs À E {0.1, 1.0]
20
Training Epochs À 10.0
15
17


Reviews:
[{"review_id": "rJe6njy0KH", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "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 focuses on learning representations which can simultaneously achieve equalized odds and accuracy parity without impacting demographic parity. The authors show both theoretically and empirically that the proposed algorithm show better utility-fairness tradeoff on balanced datasets. This is indeed a useful result. Overall, I liked the presentation of the paper including motivation and background of other methods. Theory is sound, and experiments are sufficient.   Therefore, I do not have any major concern. Some of minor concerns are mentioned below:\n\n1. I see some ambiguity in the definition of the classifiers. h is defined to be deterministic in section 2; whereas, later \\hat{Y}, which I believe is treated at h(g(x)) for some h, is taken to be randomized. Also, the theorems are mentioned with respect to h making them specific to deterministic classifiers according to the current definition.\n\n2. I am not sure why the last statement of the second last paragraph on page 2 is true. Can you please explain? There should be an additional condition on distribution D, which is not clear at that moment in the paper.\n\n3. I am wondering if the utility can be maintained for imbalanced datasets by taking two parameters \\lambda_1 and \\lambda_2 for BER_{D^0} and BER_{D^1} in equation 2. Did the authors check when we have different regularization parameters for both terms? If yes, then what was the conclusion?\n\n4. Please write theorems as fully independent statements. \"Assume the conditions in Proposition 3.2\" is probably not the right way to start a theorem. Other way is to mention the conditions separately and then use it throughout the paper.\n\n5. Can you please write or elaborate the final optimization problem after section 3.4?\n\n6. How did the authors construct the optimal classifiers in the experiments for real data? Can you provide some details?\n\nTypo: \"sensitive attribute A, then the second term\" --> remove then\n\n----  After Rebuttal ---\n\nI thank the authors for providing response to my questions. At this point, I am going to keep the same score.", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "r1gh9fvAYB", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "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: Authors extend on work that attempts to learn fair data representation (features) and propose an algorithm (which is a modification of a loss essentially) and show that it allows to achieve accuracy and equalized odds parity, and show that while achieving equalized odds they don't hurt demographic parity. The experiments demonstrate utility of the algorithm for balanced datasets (without sacrificing performance to fairness)\n\nDisclaimer: I am completely out of this area\nBut it is an easy read and an interesting angle. Authors show that simple modification of the loss makes it more fair (in a sense).  The experiments are somewhat thin.\n\nMin max problem in Section 3 - I think it requires more intro for people outside. I assume you use an architecture that extracts the representation and has two head (outputs) - h and h'. For a modified loss, do you have 3 outputs - h, h' and h''? A pic with an architecture would be really helpful\n\nProbably more datasets are required to have a more convincing empirical story\n\nSection 3.4: Even though you can't directly optimize for BER, there are ways that can work, instead of just replacing it with CE, for example this https://arxiv.org/pdf/1608.04802.pdf\n\nOne critique is based on 3.4 I don't understand  how can this be extended to multiple axis of intersecting groups- e.g. not just mutually exclusive race values, but also gender for example. ", "extra_scores": {"experience_assessment": "I do not know much about this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "S1e9hdUBcS", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "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": "Update:\n\nThanks for providing additional results on the Adult dataset. I have increased my score. However I'd be nice to also see the balanced accuracy (i.e. sum of TPRs for each class divided by 2) results and compare to baseline trained with oversampling or re-weighted loss.\n\nI would suggest authors to add more extensive comparisons to other methods using Adult dataset. There are quite a lot of papers in the fairness literature that experiment with the Adult dataset. They focus on different metrics and there is probably no method that is uniformly the best. Your paper demonstrated that your approach can succeed in achieving accuracy parity, but it would be good to also show tradeoffs with other metrics (in addition to DP). I was able to do some back-of-the-envelop calculations and your results seem fine, but a clear comparison would be good.\n\nBelow are some examples of the papers studying Adult dataset from the fairness angle:\n[1] Mitigating unwanted biases with adversarial learning. Zhang et al., 2018. (already cited, but no comparison)\n[2] What’s in a Name? Reducing Bias in Bios without Access to Protected Attributes. Romanov et al., 2019.\n[3] Learning fair predictors with Sensitive Subspace Robustness. Yurochkin et al., 2019.\n\n\n---------------------------------------------------------------------------------------------------------------------------------------------------------\n\nThis paper proposes an adversarial representation learning approach. The key difference with prior work is that the objective function is built around balanced error rates, one for classes, that is eventually used for classification, and two adversarial for predicting each of the protected attributes. Authors argue that proposed approach can simultaneously achieve accuracy parity and equalized odds.\n\nThe notion of accuracy parity does not seem to be very meaningful. For example, predicting uniformly at random seems like an intuitively fair classifier with EO gap 0 and DP gap 0. However it will not necessarily have error gap of 0 (i.e. satisfy accuracy parity), making me wonder if the notion of accuracy parity makes much sense.\n\nI am not really sure what is the Err0 + Err1 metric used in Figures 1 and 2. Is it not normalized and can vary between 0 and 2? In which case it seems counterintuitive for performance quantification. If it is normalized, then results on COMPAS do not make sense. Err0 + Err1 of all methods is above 60%, which is worse than predicting uniformly at random.\n\nPlease report your TPRs for classes grouped by protected attribute when reporting the results in the context of group fairness. Further for Adult dataset, reporting balanced TPR as a measure of accuracy seems to make more sense given the class imbalance.\n\n", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper provides a new algorithm for learning fair representation for two different fairness criteria--accuracy parity and equalized odds. The reviewers agree that the paper provides novel techniques, although the experiments may appear to be a bit weak. Overall, this paper gives new contributions to the fair representation learning literature.

The authors should consider citing and discussing the relationship with the following work:
A Reductions Approach to Fair Classification., ICML 2018
Decision: Accept (Spotlight)