Impossibility results for fair representation
Authors: Tosca Lechner
Nivasini Ananthakrishnan
Sushant Agarwal
Shai Ben-David
Venue: NeurIPS 2021 Submitted (2021)
Keywords: Fairness
learning
data representation
theory
sample complexity

Abstract: With the growing awareness to fairness in machine learning and the realization of the central role that data representation has in data processing tasks, there is an obvious interest in notions of fair data representations. We provide a formal framework for examining the fairness of data representations through the lens of their effect on decisions (mainly classification) made based on data represented that way.  Using that framework, we prove that several desiderata for fair representations cannot be achieved. While some of our conclusions are intuitive, we formulate (and prove) crisp statements of such impossibilities, often contrasting impressions conveyed by many recent works on fair representations.

Impossibility results for fair representations
Anonymous Author(s)
Affiliation Address email
Abstract
With the growing awareness to fairesss in machine learning and the realization of the central role that data representation has in data processing tasks, there is obvious interest in notions of fair data representations. We provide formal framework for examining the fairness of data representations through the lens of their effect on decisions (mainly classification) made based data represented that way. Using that framework, we prove that several desiderata for fair representations cannot be achieved. While some of our conclusions are intuitive, we formulate (and prove) crisp statements of such impossibilities, often contrasting impressions conveyed by many recent works on fair representations.
2
Introduction
10
Automated decision making has become more and more successful over the last few decades and
12 has therefore been used in an increasing number of domains, either as stand alone, or to support human decision makers. This includes many sensitive domains which significantly impact people's livelihoods, such as loan applications, university admissions, recidivism predictions, or insurance rate settings. It has been found that many such decision tools have, often unintentionally, biases against minority groups, and therefore lead to discrimination. learning research community has been devoting effort developing clear notions of fair decision making, and coming up with algorithms for implementing fair machine learning.
14
16
response to these concerns, the machine
17
18
19
20
common approach to address the important issue of fair algorithmic decision making is through fair data representation. The idea is that some regulator responsible data curator transforms collected
22 data to format (or representation), that can then be used for solving downstream classification tasks providing guarantees of fairness. This approach was proposed by the seminal paper of Zemel et 24 al. [5). In their words: "our intermediate representation can be used for other classification tasks (i.e., transfer learning is possible)" ... "We further posit that such an intermediate representation is fundamental to progress in fairness in classification, since it is composable and not ad hoc; once 27 such a representation is established, it can be used in blackbox fashion turn any classification
26
28 algorithm into a fair classifier, by simply applying the classifer to the sanitized representation of
29 the data". Many followup papers aim realize this paradigm, solving technical and algorithmic
30 issues I00 T 14 3 (to mention just a few). The main contribution of this paper is showing that,
31 basically, it is impossible achieve this goal. Namely, no data representation can guarantee that for
32 every classification task classifier trained on data under the given representation will be fair for
33 that task. This impossibility applies even if one restricts the downstream tasks in question to share
34 the same labeling rule, or for fairness notions like Odds Equality, to share the same marginal data distribution with the data on which the representation was trained. Our results answer negatively the main two questions posed in the discussion section of Creager et al. 3
35
37
While many papers in this domain propose algorithmic solutions fairness related issues, the main contributions of this paper are conceptual. We believe that, to a much larger extent than many other
38
Submitted to 35th Conference on Neural Information Processing Systems (NeurIPS 2021). Do not distribute.

---

facets of machine learning, fundamental concepts of fairness in machine learning require better 39
40
understanding. Some basic questions are still far from being satisfactorily elucidated; What should be considered fair decision making? (various mutually incompatible notions have been proposed, but how to pick between them for a given real life application far from being clarified). What is fair data representation? To what extent should accuracy or other practical utilities be compromised for achieving fairness goals? and so on. The answers to these questions are not generic. They vary with the principles and the goals guiding the agents involved (decision makers, subjects of such a decision, policy regulators, etc.), as well as with what can be assumed regarding the underlying learning setup. We view these as the primary issues facing the field, deserving explicit research attention (in addition to the more commonly discussed algorithmic and optimization aspects). This is a theoretical work, our discussion is grounded in definitions and proofs rather than heuristics and experimental results.
41
42
43
44
45
46
48
49
50
1.1
What is fair representation?
The term 'fair data representation' encompasses wide range of different meanings. When word 52 embeddings results in smaller distance between the vectors representing 'woman' and 'nurse" relative
51
53 to the distance between the representations of 'woman' and 'doctor' and the other way around for
54 'man', is it an indication of bias in the representation or is it just a faithful reflection of a bias in
55 society? Rather than delving into such issues, we discuss an arguably more concrete facet of data
56 representation; We examine representation fairness from the perspective of its effect on the fairness
57 of classification rules that agents using data represented that way may come up with. Such a view takes into consideration two setup characteristics:
58
59
The objective of the agent using the data We distinguish three types of classification prediction agents (formal definitions of these aspects of fairness are provided in section 3.2g:
60
61
Malicious - driven by a bias against a group of subjects. To protect against such an agent, a fair representation (or feature set) should be such that every classifier based data represented that way is fair. This is apparently the most common approach to fair representations in the literature e.g., [5]] [O].
62
69
64
65
Accuracy Driven focusing on traditional measures of learning efficiency, ignoring fair- ness considerations. A representation is accuracy-driven fair if every loss minimizing classifier based on that representation fair.
66
67
68
Fairness Driven aiming to find decision rule that is fair while maintaining meaningful accuracy. A representation is fairness-driven fair if there exists loss minimizing (or an approximate minimizer) classifier based on that representation fair.
69
70
71
The notion of group fairness applied to the classification decisions The wide range of group fair- ness notions (for classification) can be taxonomized along several dimensions: Does the notion depend on the ground truth classification or only on the agents decision (like demo- graphic parity)? Is perfectly accurate decision (matching the ground truth classification) always considered fair (like in odds equality)? Does the fairness notion depend on unobserv- able features (like intention or causality)? In this work we focus on faimess notions that are ground-truth- truth--ependdent, view the ground truth classification as fair and depend only on observable features. The decision which notion of faimess one wishes to abide by depends on societal goals and may vary from one task to another and is outside the scope of this paper. Just the same, let us briefly explain why the requirements listed above are natural in many situations.
72
73
74
75
78
77
78
79
80
81
The dependence on the ground truth classification is almost inevitable from utilitarian perspective - taking into account the probability that a student succeed or fail when making acceptance decisions should not be considered unfair. Put more formally, when- ever there is any correlation between membership and the ground truth classification, any classifier that is fair w.r.t. notion that ignored the ground truth (like demographic parity) is bound to suffer prediction error proportional to that correlation.
89
85
86
87
88
Viewing perfectly accurate decisions as fair can be viewed as a distinction between no- tions that do or do not try to inflict affirmative action. It makes lot of sense in tasks like conviction in a crime - if you convict all criminals and no one else, you should not be accused on unfairness.
89
90
91
82
Relying only on observable features fosters objectivity and allows scrutiny of the decisions made. Our running example of such notion is odds equality [8], however our results
2

---

94
hold as well for other common notions of fairness that meet the above conditions (like Calibrations Within Groups
95
96
1.2
Our results
97
We prove the following inherent limitations of notions of fair representations (under the above taxonomy):
98
1.
The impossibility to be task independent. There is host of literature proposing methods of coming up with data representation that guarantees the faimess of classifier based on that representation (e.g., [8 3 TO [2]). We elaborate on these works in our Previous Work section. Contrasting the impression conveyed by many such papers, we show that the ability to guarantee multi-task fairness is inherently limited. Much of that work ad- dresses Demographic parity (DP). We prove that if two tasks have different marginal data distributions (that is, the distribution of unlabeled instances) and different success rates of the protected group, then no representation can guarantee that any non-trivial classifier trained it satisfies DP for both. We show that the only classifiers that are guaranteed to satisfy any significant level of DP fairess w.r.t. all marginal distributions are the redundant constant functions. From a practical point of view, since DP fairness of some decision (say, acceptance to some university program) requires the ratio of positive decisions between groups to match the ratio of applicants from those groups, a representation that guarantees DP fairness cannot be a priory constructed it must have access to the distribution of groups among applicants for that specific program. Furthermore, we prove that for every fixed marginal data distribution, if two ground truth classifications differ with non-zero probability over it, there can be no data representation that enjoys Odds Equality fairness and accuracy with respect to both tasks over that shared marginal distribution (except for the redundant case where the success rates both groups are equal for both tasks). These results answer negatively the main two open problems posed in the Discussion section of [3].
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
117
119
2. The impossibility to evaluate the fairness contribution of given feature devoid of the other features used (again, for each agent objective and several common group fairness notions).
120
121
3. The inherent dependence of the effect on fairness of udding/deleting a feature on the type of agent using the representation (on top of the above mentioned dependence other features), even when the feature question does not correlate with membership in the protected group.
122
123
124
(These come on top of the obvious dependence the notion of fair classification sought).
125
We cannot foresee any potential negative societal impact of our work. The main message of this paper is cautionary statement. We alert potential users that approaches based on task independent fair representations cannot guarantee the fairness of arbitrary predictors based on them. As such, we are only guarding against potential negative impact of previously published work.
Concerning potential negative societal impact:
126
127
129
130
Our paper is organized as follows: Section 2 gives an overview of the related work. Section 3 introduces our setup including our taxonomy for fair representations. Section 4 contains our main results on the impossibility of generic faimess of a representation. Section 5 addressed the impos- sibility of defining the fairness effect of single feature without considering the other components of a representation. Section 6 briefly shows the impossibility of having fair representations w.r.t.
131
132
133
134
135
Predictive Rate Parity. Section is our concluding remarks.
136
We defer proofs to the appendix.
137
2
Related Work
138
Since our paper goes against messages conveyed by many previous papers, we wish to address in detail more related works than space here allows. We therefore provide more elaborate section previous work in the supplementary material.
140
Much of the recent work on fair representation for learning classifiers focuses on algorithms. (and
142
demonstrating the viability of those algorithms though experimental results) 15
As explained before, our focus is different. We discuss what should be considered fair representation in
10 17 16)
3

---

144
that context, what is the scope of such notions and what are the inherent limitations of defining such
145
representations.
146
Almost all the work on fair representations focuses on the demographic parity (DP) notion of faimess
147
6 10 15 14. Not having take ground truth into account makes this notion independent of the classification task carrying both advantages and limitations. However, any positive result in these papers assumes that the marginal data distribution available the designer of the fair representation. Such an assumption severely restricts the applicability of such representations. To achieve DP fairness, a classifier has to induce success ratio between the two groups that match the ratio between these groups in the input data. However, that ratio, say a set of applicants for a bank loan or to some university program varies from one application to another and cannot be determined priori. Our results on this inherent limitation of fair representation for DP (see section 4 do not seem to have been stated before.
148
149
150
151
152
153
154
155
156 W hen the data marginal distribution is fixed, and available to the designer of a representation, DP fairness is possible. However, in such a setup, we show that fairness with respect notions of fairness that do rely on the correct ground truth, such as equalized odds (EO) (8) cannot be guaranteed for arbitrary tasks (see Section 4. This fact also has not been explicitly stated (and proved) before, although it seems that some of the previous work worried about it. Instead, previous work either focus only on DP fairness, or, when it comes to discuss other notions of faireess, the algorithms that design the representations are assumed to have access to task specific labeled data (e.g. [16] 2 [1] 5], which defies the goal of having a fixed representation that guarantees fairness for many tasks.
157
158
159
160
161
162
163
164
The effect of the motivation of the decision maker using the representation on the fairness of the resulting decision rule has been considered by Madras al. (10) and Zhang et al. [16]. These papers identify two motivations. The first is malicious, which is the intent to discriminate without regard for accuracy. The second is accuracy-driven, which is the intent to maximize accuracy. We address these effects as part of our taxonomy of notions of fair representations. Additionally, we discuss fuirness-driven agents that aim achieve fairness while maintaining some level of accuracy.
165
186
167
168
169
170 A natural question that arises in this context is about the inherent trade-offs between fairness and accuracy. When the notion of faimess is demographic parity, such trade-offs are clearly expected they surface whenever there exists correlation between membership in the protected group and the ground truth classification. Zhao et al. [18] and Menamara et al. 11] analyze such scenarios and demonstrate situations in which there exists a more accurate and more fair classifier based on an original representation than any classifier built using learnt representation.
172
173
174
175
176
The question of feature deletion has also been considered in real world examples, such as in the "ban the box" policy which disallowed employers using criminal history in hiring decisions 4. The effect of allowing or disallowing features on fairness has been studied before, for example in Grgic-Hlase Hlaca et al. [7]. However in previous works, the effect of a feature faimesss, has been discussed in isolation.
178
180 In contrast, we show that fairness of a feature should not be considered in isolation, but should also take into account the remaining features available.
182
3
Formal Setup
183
We consider a binary classification problem with label set (0, 1} over domain X of instances we wish to classify, c.g. individuals applying for a loan. We assume the task to be given by some distribution P over X x {0, 1} from which instances are sampled i.i.d. We denote the ground-truth labeling rule as : X + [0, 1]. We will think of the label I as denoting 'qualified' and the label 0 as "unqualified' and t(x) = P(y = 1|x]]. For concreteness, we focus here on the case of deterministic
184
185
186
188
labeling (that ist X + {0, 1}). Most of our discussion can readily be extended to the probabilistic
labeling case. In slight abuse of notation we will sometimes use t(w) to indicate the label coordinate
190
of an instance w E X x {0.1]
A data representation is determined by a mapping F: X + Z, for some set Z, and the learner only sees F(x) for any instance æ (both in the training and the test/decision stages). We denote the hypothesis class of all feature based decision rules as Hp = (h: Z + {0, 1)). As a loss function

---

we consider weighted sum of false positives and false negatives, i.e.
(9, I, y) = 1 a
{{
((x) = 0,y=1
a, if h()))) = 1,y=
otherwise
191
for some weight a E (0, 1). We denote the true risk with respect to this loss as Lp and the empirical
192
risk as Lg.
198
3.1
Notions of group fairness
194
For our faimess analysis we assume the population X to be partitioned into two subpopulation A and D (namely, restrict discussion the case of one binary protected attribute). We sometimes use function notation G X - {A, D} to indicate the group-membership of an instance. Of course in
195
196
197
reality there are often many protected attributes with more than two values. However, as our goal is show limitations and impossibility results for fair representation learning, it suffices to only consider one binary protected attribute the same impossibilities readily follow for the more complex settings.
198
199
200
We now define two widely used notions of namely, equalized odds and demographic parity. In the following will denote with Xg, the subset
that we will refer to throughout the paper,
of X with label I and group membership g. i.e. X,, = (t)
202
203
Definition (Group fairness; Equalized odds) The notion of group-faimness we will focus on in this paper is the ground-truth-depnnde notion of odds equality as introduced by [8].
204
A classifier h is considered fair w.r.t. to odds equality (LEO) ) and distribution P if for we have the statistical independence h(x) 1L (( For g E [A, let the false positive rate and the false negative rate be defined as FPR, (h, -P
P
1| E Xg,0) and FN Rg (h, L, P)) = (Pz-phh(s = 0f & X9a) respectively. The EO unfairness is given then by the sum of differences in false positive rate indfass negative rate between groups:
SATRA-FNRA, FNRD + -IINRAIN--FAAAA L (h) -
+ 1 LIPRA
FPRp).
If say classifier is fair, without referring any particular group-faimess notion, mean fairness w.r.t. equalized odds.
206
207
Definition (Demographic parity) classifier considered fair w.r.. to demographic parity (LPP) and a distribution P if h(x) 1L G(x). The respective unfairness is given by difference in positive classification rates between groups
208
209
LP (h) (PP-p(h(z)) = 1 G(r) = A] P P.-p(h(r) = 1|G(z) = D]I.
210
211
3.2
The role of the agent's objective
We will phrase definitions of representation fairness in terms of a general group fairness notion ffir with unfairness measure L fair
213
214
We start by considering a malicious decision maker who tries to actively discriminate against one group To protect against this kind of decision maker, need give guarantee such that based on the feature set it is not possible to discriminate against one group. This corresponds to the notion of adversarial fairness.
215
216
Definition 3 (Adversarial fairness) A representation F is considered to be adversarial fair w.r.t the distribution P and group fairness objective of if every classifier Hr is group-fair. We define the adversarial unfairness of representation by Uadv(F) = maxne [aar (h).
219
220
Furthermore, we consider an accuracy-driven decision maker, who aims label instances correctly and is agnostic about fairness. For this kind of decision maker, we only need to make sure that optimizing for correct classification results in fair classifier. The following definition ensures that the Bayes optimal classifier for a representation is fair.
222
223
224
225
Definition 4 (Accuracy-driven fairness) representation is considered to be accuracy-driven
fair w.r.t. the fairness objective _fesr and distribution P. for every threshold E (0, 1), every classi-
5

---

227 fier h E H. with (h) = minKeR [h) is group-fair The accuracy-driven unfaimess for a par- ticular threshold parameter is given by U (F) m pa (h) h arg mi (h)).
The general accuracy-driven unfairness is given by FF) = maX U (F).
229
230
We note that in cases where the decision maker does not have access to the distribution P. but only a labelled sample, this requirement is might sufficient for guaranteeing that an accuracy- driven decision maker arrives at a fair decision. In the Appendix we propose another fairness notion (A-robustness) that formalizes the desired fairness guarantee for this scenario.
232
233
234
Lastly, we also consider a fairees--driee decision maker who actively tries to find a fair and accurate decision rule, while maintaining some accuracy guarantees. For such decision maker a representation should allow for fair and accurate decision rules. If a representation fulfills this requirement, call it fairness-enabling
236
238
Definition 5 ((e, rj) -ir--aaieeseeaabliii representation) A representation F is considered to be (c. n) fairness-enablingg w.r.t. a fairesss objective Lfair, if there exists a classifier E Hp that such that (h) S and L.p fer (h) S n.
239
241
Our discussion focuses primarily on the case malicious and indifferent decision makers. These notions of fair representation can be defined with respect to any group-faimess notion. In our paper we will mainly focus on the equalized odds notion of fairness (8. We also note that all the above definitions can be given with respect fixed model H in continuous space.
243
4
Can there be generic fair representation?
245
246
We address the existence of multi-task fair representation. We prove that for the adversarial agent scenario (which is the setup that most fairness representation previous work concerned with), it is impossible to have generic non-trivial fair representations no useful representation can guarantee fairness for all "downstream" classification that are based on that representation (even the ground truth classification remains unchanged and only the marginal may change between tasks).
247
249
251
We start by considering scenarios in which only the marginals shift between two tasks, c.g. two openings for different jobs, requiring similar skills, for which different pools of people would apply. Such a distribution shift can likely affect one group more than another and would thus affect the classification rates of both groups differently. We show that we cannot guarantee fairness of fixed data presentation for general shifts of this kind, even for the simplest case of demographic parity.
252
253
254
255
256
Pick any domain set X and any partition of X into non-empty subsets A, D. For every non-constant function f X -> {0, 1) there exists a probability distribution P over X such that is arbitrarily DP-unfair w.r.t. (say, T.P. (h) > 0.9).
Claim:
258
259
In particular, when a shift in marginal occurs between tasks, fairness for previous tasks does not imply fairness guarantee for new task.
260
If is constant on any of the groups A D then, since f is not constant over X there is are points in the other group on which I has the opposite value. Let P assigns probability 0.5 to the group on which f is constant and probability 0.5 to the set of points which f assigns the other value. Clearly f fails DP w.r.t. this P. Otherwise, both values are assigned in both groups, so let P
Proof:
282
263
284
285
assign probability 0.5 to {x A: f(x) 0} and probability 0.5 {o D f(x) 1}. Clearly, fails DP w.r.t this P.
267
No data representation can guarantee the DP fairness of any non-trivial classifier w.r.t. all possible data generating distributions (over any fixed domain set with any fixed partition into non-empty groups). That is, any non-constant representation F, cannot be adversarially fair with respect to L DP and any arbitrary task P.
Corollary
268
269
270
271
Pick any domain set X and any partition of X into non-empty subsets A, D. For every non-constant function J X ~ [0,1} and every classifier h h: X {0. 1) such that h # f there exists probability distribation P over X such that is arbitrarily EO-unfair w.r.t P, P, say
Claim:
273
L.. > 0.9.

---

275
Corollary 2 No data representation can guarantee EO fairness of any non-constant predictor based on that representation for all "downstream"" classification learning tasks. That is, any non-constant representation F, cannot be udversarially fair with respect to T,EO and any arbitrary task P. This holds even if one restricts the claim to tasks sharing a fixed marginal data distribution.
278
278
279
We will now look at a slightly more restricted setting and analyse the case of multi-task learning, where instead of asking for representation that fair for every task, we only consider fairness with
280
281
respect to a fixed (finite) set of tasks that we want to learn. We find that for the adversarial case, even this less ambitious goal is not achievable for generic tasks and the equalized odds notion of fairness.
282
We say a distribution has equal success rates if P(XA.)) P(XD..) P(D)
283
P(A)
Lemma Let Pi and P2 be the distributions defining two different tasks with the same marginal Px
285
PI.x P2.x such that at least one of the tasks does not have equal success rates. Let h1 h2 X + 10 be such that Lp, (h1) T,,, (h2)= 0, and assume that tasks are non-negligibly different (namely, Lp, (12) # 0). Then, it cannot be the case that both h1 and hz are EO fair w.r.t.
287
both Pi and P2.
289
The proof (in the appendix) has a similar flavour as the proof of incompetability of different fairness notions of (9]
290
Theorem There can be data representation F such that for some Pt, P2 as above, the following criteria simultaneously hold:
292
293
1. F is adversarially fair w.r.t P1 and EO
294
2. F is adversarially fair w.r.t. P2 and EO
295
3. F allows for perfect accuracy w.r.f. to P1 and Pz. i.e. there are h1, h2 both expressible over the representation F, such that Lp, (h1) = Lp, (h2) =
296
297
This result follows directly from Lemma [ Therefore. if the goal is prevent discrimination from a possibly adversarial decision maker, while also enabling accurate prediction, each task requires its task specifcc feature representation.
298
299
5
Fairness of a feature set vs. fairness of a feature
In this section we discuss feature deletion and its impact on the faimess of representation. For this we assume our representation to consist of finitely many features f; X -> Y, i.e. for every E X F(z)= (z)..... (x))) and Z Yi x... x Yn. We limit our discussion to cases where all Y; are finite. While this assumption facilitates our analysis, we do not expect our results to be different in the cases of continuous features. We will denote the set of features as F = (fi.....ff. } and will denote by (F) and (F) the adversarial and eecuracy-driver fairness of the representation induced by the feature set F respectively. We show that it is in general not possible to determine the effect a single feature has on the fairness of representation without considering the full representation. This is the case even if our considered feature is not correlated with the protected attribute.
302
304
306
308
310
5.1
Opposing effects of feature for accuracy-driven fairness of representation
312
We start our discussion with accuracy-driven fairness w.r.t. equalized odds. In this case we show that the deletion of feature can lead to an increase in accuracy-driven unfairness for some set of other given features F and that the deletion of the same feature f can lead to a decrease in accuracy-driven unfaimess for another set of other available features F'. This implies that the fairness of the feature
313
314
315
316
cannot be evaluated without context. We show that this phenomena holds for general class of features that satisfy some non-triviality properties (That on the one hand do not reveal too much
317
information about group membership and labels (non-commitiing) and on the other hand does not
319
reveal identity when label and group information given (k-anonymity 13 The exact definitions
of these properties can be found in the appendix.
7

---

321
Theorem (Context-relevance for fairness of features) For every 6-anonymous non con-committing
322
feature there exists a probability function P over X and and feature sets F and F such that:
The accuracy-driven faimess w.r.t LPO, Paddd 0.5 of F FU is greater than that of
324
F, i.e.
(F (FU(F) ( (F)
325
Thus, deleting f in this context will increase unfairness.
The accuracy-driven fairness w.r.t EO, P Pndd a = 0.5 of is less than that of F', i.e.
326
Uhe (Fc(F'OR ((U (F)
Thus, deleting f in this context will decrease unfairness.
This phenomenon happen even if {f) is adversarially fair w.r.t to P and equalized odds.
330
5.2
The fairness of feature for different notions of fairness
331
We will now briefly discuss the effect of a single feature on fairness for the cases of a malicious or fairness-driven decision makers. In contrast to the accuracy-driven case, adding features has
332
333
monotone effect on the fairness of a mairness-driven and the malicious decision maker. As Theorem 3
334
adding any feature in the malicious case, will only give the decision maker more information and thus give the decision maker more chances of discrimination. Similarly in the fairness driven case, any feature will only give the decision maker another option for fair decision making (Theorem ) However, the quantitative effect of adding a feature on the unfairness can still range from having no effect to achieving perfect fairness/unfarrness for both the fairness-driven and the malicious case.
335
336
338
As in the accuracy-drive case, we will show (Theorem and Theorem B that it is impossible to evaluate the quantitative effect of a feature on the fairness a representation without considering the context of other available features.
340
Theorem 3
1. For every distribution P feature f. there exists feature set F. such that adding f will not impact the fairness of the distribution, e.g. Uade = Undo U(ff()
343
344
2.
There exist distributions P, f.feuuures f and F', such that Uado = and Unde ((fT) = 0. but Undu (J U (f))= 1.
Theorem
1. For any feature and any featureset F we have Undu (F) S Undv (F (FU U (.3). Similarly, if the representation F is (e. (e-n)-fairness-ennbbing the representation F U { is also (e, () fairnesssss-sss fairness-enabling.
347
348
2. For every distribution and every feature f. there exists a feature set F, such that FU {f} is (n, ffairness-enabling if and only if F is (c. fairnesssssss----eeer tiirness-ennbling Furthermore, there exists a distribution P, a feature and a feature set F', such that both F' and {f} are not
349
350
351
(e, -inieiiiisss for any e,7 < 2) but such that F U ( is (0, 0)-fairness-enablin
353
While this section focused on fairness with respect to equalized odds, we note that many of these results can be replicated for other notions of fairness. For a more general version of Theorem 3 which takes into account other fairness notions, like demographic parity, we will refer the reader to the Appendix.
354
356
Impossibility of adversarially fair representations with respect to predictive rate parity
357
358
We now show that not all acceptable notions of group fairness always allow adversarially fair representation, even in a single-task setting. One such notion is predictive rate parity.
360
361
Definition 6 (Predictive rate parity (PRP)) A classifier h is considered PRP fair w.r.. to a marginal data distribution P and true classification t if the random variable t(x) is independent of the group membership. G(x) given the classification h(z). We denote this fairness objective with L Pred
8

---

Theorem 5 Adversarial fairness w.r.f. P and L Pred is only possible, if P has equal success rates for both groups.
384
385
366
This theorem results from the fact that the classifier which maps every instance to label 1 is not fair w.r.t. to T, Pred if P does not have equal success rates. The quantitative version of predictive rate parity as well as a more general version of Theorem giving a characterization of adversarial fairness in the case of equal success rates can be found in the appendix.
367
368
7
Conclusion
370
In this paper we introduced a general taxonomy of notions of fair representation, taking into considera- tion both different objectives of decision makers using the representation, and different group fairness notions. Within this taxonomy we showed several impossibility results about fair representation learning.
372
374
375
Our main result addressed the existence of generic fair representations and of fair transfer learn- ing. We show that even seemingly task-independent fairness notions like demographic parity are vuinerable to shifts in marginals between tasks. We conclude the impossibility of having generic data representations that guarantee (even just) DP fairness with respects to tasks whose marginal distributions are not considered when designing the representation. Furthermore, we show that it is impossible to have an adversarially fair representation with respect to several tasks and the equalized odds notion of fairness, if those tasks do not all fulfill statistical parity. These insights stand in contrast to the impression arising from recent papers T0 that claim to learned transferable fair decisions.
376
377
378
380
382
383
We also considered the question of "fairness of a feature", which has been used in legal scenarios. We showed that for notions of fecision-making fairness other than demographic parity, the fairness of single feature is an ill defined notion. Namely, the impact of feature on the fairness of a decision cannot be determined without considering the other features of the representation.
384
385
386
387
Lastly, we show that some fairness notions, like predictive rate parity, do not always allow an adversarially fair representation, even if is just for single task.
388
References
389
390
[1] Tameem Adel, Isabel Valera, Zoubin Ghahramani, and Adrian Weller. One-networt adversarial fairness. In AAAI, 2019.
392
[2] Alex Beutel, Jilin Chen, Zhe Zhao, and Ed H. Chi. Data decisions and theoretical implications when adversarially learning fair representations. CoRR, 0ass/777.00007 2017.
394
[3] Elliot Creager, David Madras, Kbern-Henrik Jacobsen, Marissa Weis, Kevin Swersky, Toniann Pitassi, and Richard Zemel. Flexibly fair representation learning by disentanglement, In ICML, 2019.
396
[4] Jennifer L. Doleac and Benjamin Hansen. Does "ban the box" help or hurt low-skilled work- ers? statistical discrimination and employment outcomes when criminal histories are hidden. Technical report, National Bureau of Economic Research, 2016
396
400
[5] Flávio du Pin Calmon, Dennis Wei, Bhanukiran Vinzamuri, Karthikeyan Natesan Ramamurthy, and Kush R. Varshney. Optimized pre-processing for discrimination prevention. In Advances in Neural Information Processing Systems 30.
402
66]
Harrison Edwards and Amos J. Storkey. Censoring representations with an adversary. In ICLR, 2016.
404
7
Nina Grgic-Hlaca, Muhammad Bilal Zafar, Krishna P. Gummadi, and Adrian Weller. Beyond distributive fairness in algorithmic decision making: Feature selection for procedurally fair learning. In AAAI, 2018
406
408
(8] Moritz Hardt, Eric Price, and Nathan Srebro. Equality of opportunity in supervised learning. In NIPS, 2016.

---

410
[9] Jon M. Kleinberg, Sendhil Mullainathan, and Manish Raghavan. Inherent trade-offs in the fair determination of risk scores. CoRR, (tss/1609.058077 2016.
411
412
[10] David Madras, Elliot Creager, Toniann Pitassi, and Richard Zemel. Learning adversarially fair and transferable representations. In ICML, 2018.
[11] Daniel McNamara, Cheng Soon Ong, and Robert C Williamson. Costs and benefits of fair representation learning. In Proceedings of the 2019 AAAI/ACM Conference on AI, Ethics, and Society, pages 263-270, 2019.
415
416
417
[12] Luca Oneto, Michele Donini, Andreas Maurer, and Massimiliano Pontil. Learning fair and transferable representations. arXiv preprint arXiv: 10673, 2019.
418
[13] Pierangela Samarati and Latanya Sweeney. Protecting privacy when disclosing information: k-anonymity and its enforcement through generalization and suppression. Technical report, 1998.
420
422
[14] 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, pages 2164-2173, 2019.
423
425
[15] Rich Zemel, Yu Wu, Kevin Swersky, Toni Pitassi, and Cynthia Dwork, Learning fair representa- tions. In ICML, 2013.
428
[16]
Brian Hu Zhang, Blake Lemoine, and Margaret Mitchell. Mitigating unwanted biases with adversarial learning. In AAAI/ACM Conference on AI, Ethics, and Sociery, 2018.
428
429
117]
Han Zhao, Amanda Coston, Tameem Adel, and Geoffrey J. Gordon. Conditional learning of fair representations. CoRR, abs/1910.07162, 2019.
430
431
[18] Han Zhao and Geoffrey J. Gordon, Inherent tradeoffs in learning fair representations. CoRR,
432
abs/1906.08386, 2019.
Checklist
433
1. For all authors...
435
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes] We provide theorems with proofs for all claims made in the introduction and appendix
436
437
(b) Did you describe the limitations of your work? [Yes]] The introduction clearly details the scope of our paper
439
440
(c) Did you discuss any potential negative societal impacts of your work? [Yes] We discuss potential negative societal impacts at the end of the introduction.
441
442
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
444
2. If you are including theoretical results...
445
(a) Did you state the full set of assumptions of all theoretical results? [Yes] Every result clearly states the assumptions used. In one instance (Theorem 2 refer to detailed definition of the assumptions in the appendix.
447
448
(b) Did you include complete proofs of all theoretical results? [Yes] Many of them were refered to the appendix
449
450
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or as a URL)? [N/A]
452
453
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [N/A]
454
455
(c) Did you report error bars (e-g., with respect to the random seed after running experi- ments multiple times)? [N/A]
10

---

457
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [N/A]
458
4. If you using existing assets (e.g., code, data, models) curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
462
(c) Did you include any new assets either in the supplemental material as a URL? [N/A]
463
(d) Did you discuss whether and how consent was obtained from people whose data you'le 're using/curating? [N/A]
465
486
(e) Did you discuss whether the data you are using/curating contains personally identifiable information offensive content? [N/A]
5. If you used crowdsourcing conducted research with human subjects...
489
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
470
471
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A]
473
(c) Did you include the estimated hourly wage paid participants and the total amount spent on participant compensation? [N/A]
474


Reviews:
[{"review_id": "zIl585nRiHZ", "reviewer": "Reviewer_58vf", "summary": "This paper formalizes impossibility results for fair representation learning. The authors present a series of settings where various desirable properties cannot be achieved.", "questions": "", "limitations": "", "rating": 6, "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": "I think this paper makes a valuable contribution. Some of the results are fairly intuitive, but it's helpful to see them formally specified.\n\nThere's a sense in which the results, particularly in Section 4, aren't really about representations per se. It would've been helpful to see a general version of the step from Lemma 1 to Theorem 1 -- something like, if $h_1$ and $h_2$ don't satisfy some property w.r.t. both $P_1$ and $P_2$, there is no representation that can in the adversarial case.\n\nI found the results on \"fairness of a feature\" to be fairly interesting.\n\nI'd also appreciate a bit of caution in stating these results. They're in some sense worst-case, since they're about the existence of an alternate marginal under which a learned representation would perform poorly. But this doesn't say anything about real-world cases, which may be better than the worst case.\n\n- l. 289: \"incompetability\" -> \"incompatibility\"\n- l. 350: $\\eta$ and $\\epsilon$ are reversed\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "uD19DT4z-as", "reviewer": "Reviewer_qgAQ", "summary": "This work establishes a formal framework for exploring impossibility questions related to fair data representations. Impossibility results are proven within this framework with an emphasis on challenging prior work in this area.", "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": "The paper takes an interesting and important stance, critiquing a popular approach to fair classification (fair representations) and exploring its limitations. However, the claims seem a bit exaggerated with respect to prior work in relation to the perspective studied in the paper. The results here are narrowly tailored to a specific setting that assumes objective access to ground truth and appears opposed to the notion of demographic parity. E.g., the paper claims to resolve two open questions from [4], but it only resolves them under certain assumptions. This ground-truth-dependent perspective is useful for theoretical analysis and insights, but is unrealistic and fails to capture the complexity of fairness problems. These issues aside, I still feel the paper makes relevant contributions, including reining in overblown claims in prior work such as the promise of task independence.\n\nAs the paper notes, many of the results are straightforward and not necessarily technically complicated or surprising. Nevertheless, a lot of work has gone into defining and understanding a new perspective on an area of research. So the perspective, framework, and results shown are novel and have significance.\n\nThe clarity is okay, but could be improved and I found the paper hard to follow at times. The introduction could be condensed and restructured to decrease length and reduce redundancy. This would improve readability/clarity and give more room for exposition elsewhere or more discussion of related work as currently appears in the appendix.\n\nOverall, I would like to see the claims toned down and the limitations of the ground-truth-dependent perspective acknowledged more. The paper makes valuable contributions that are hampered by the writing and limitations of the framework. It is a borderline accept in my opinion.\n\n\nAdditional comments:\n\nThe focus on ground truth leads to some questionable implications, which may be due in part to unfortunate phasing. On page 2, for example, assuming correlation between group membership and ground truth as stated in the paper is different from assuming correlation between group membership and labels in a training set. The latter allows for sample bias, label bias, etc. The former is a little too close to assuming inherent differences between the groups.\n\nLikewise, the section on “Viewing perfectly accurate decisions as fair” says, “It makes a lot of sense in tasks like conviction in a crime - if you convict all criminals and no one else, you should not be accused on unfairness.” \nCriminal justice is a problematic example here given the high-profile issues with inaccuracy and discrimination in this area that many fairness studies attempt to address. Further, the goals of criminal justice are often one-sided rather than aiming for the impossible goal of perfect accuracy (either minimizing the risk of false conviction at the expense of releasing criminals or alternatively, minimizing the risk of releasing criminals at the expense of false conviction).\n\nGrammar: \n“A representation is fairness-driven fair if there exists a loss minimizing (or an approximate minimizer) classifier based on that representation is fair”\n“we restrict our discussion the case of one binary protected attribute”\n“…this requirement is might not sufficient for guaranteeing that an accuracy232\ndriven decision maker arrives at a fair decision”\n“…since f is not a constant over X there is are points in the other group on which f has the opposite value.”\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The paper gives somewhat of a non-answer to the question of potential negative social impact. I’d like to see more discussion of limitations and potential negative impact such as how this work could potentially be misconstrued in a harmful way.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5 hours"}, "extra_text": {}}, {"review_id": "iVLfYYuYeby", "reviewer": "Reviewer_1FfL", "summary": "This paper demonstrates two impossibilities raised in a fair machine learning context: (i) the impossibility of achieving a generic fair data representation; (ii) the impossibility of achieving fairness notions (except disparate parity) in the case of manipulating a single feature. The paper also answers the two questions raised in Creager et. al. [3] via theoretical analysis under binary classification setting w.r.t. varying fairness notions. ", "questions": "", "limitations": "", "rating": 5, "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": "The paper raises important and practically relevant questions concerning multiple fairness notions. Nevertheless, several points need to be clarified. First, as demonstrated in 1.1, what is the difference between malicious and fairness-driven agents? The clear distinguishment between the three groups of agents should be stated through rich prior works; this also holds for the criteria of group fairness notions.  There are also significant problems with the presentation of this paper. For example, it is not clear why the authors looked into adversarial fairness (malicious decision-maker) and then multi-task setting afterward. Lastly, while the proof of Claim 1 does not have any significant technical contributions, Claim 2 and Collorary 1 are rather straightforward. Additionally, Theorem 3 only demonstrates a feature set that can lead to the worsening of unfairness; there can be certain cases in which adding or subtracting a feature improves fairness and performance. To conclude, the overall presentation is difficult to follow. Organizations and descriptions of the proofs can be improved. In addition, the authors used the same lines from Zemel et. al. [15]. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "A clear discussion of societal impacts is provided in the paper. In spite of the numerous questions raised, however, this paper does not adequately address limitations and previous works, especially regarding multi-task fairness problems. See the 1st point in “Main Review”.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}, {"review_id": "Bwk1VxUwQq0", "reviewer": "Reviewer_NE9z", "summary": "In this work authors analyzed the transferability of fair representations and showed that it is impossible to train a classifier using fair representations that can achieve the fairness goal for all the cases.", "questions": "", "limitations": "", "rating": 5, "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": "The paper targets an interesting concept that is also timely and new; however, there are some concerns:\n1. As authors also point out, having fair representation can mean different things. I do not think that the taxonomy that the authors gave here are accurate or general enough to be able to get to a general conclusion. As authors ground their work based on these definitions, I find it difficult to draw any significant conclusions based on the results.\n\n2. In addition, the paper is written and organized very poorly. Some major proofs are not placed in the main text which make it hard to follow the paper. The paper also has some writing issues as well some pointed below, but the organization is something that needs more work. Some grammar issues:\nline 231: is might not sufficient -> is not sufficient. line 382: that claim to learned -> that claim to learn.\n\n3. The paper also jumps from one definition to another without clear reason. I would suggest authors to maybe focus on DP as many work in fair representation learning focuses on DP and put all the major discussions along with the proofs for DP in the main text and put discussion about equalized odds in the appendix. As authors also point out work in DP is more so it would make more sense to put the focus on DP instead of Eqodds.\n\n4. I am also curious to see what authors think about information theoretic work in this area. Maybe some brief discussion should be provided on different types of techniques people use and where they fall under according to their taxonomy. I again generally find their taxonomy narrow and have difficulties about figuring out which work may fall under which section, so maybe some clarity or even changing the taxonomy can be beneficial.\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Authors mentioned that they do not see negative societal impacts related to their work and also did not provide sufficient discussion about the limitations of their work. Authors can maybe talk about limitations associated to their narrowed taxonomy.  ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3 hours"}, "extra_text": {}}]

Author rebuttal:

Meta-review: Reviewers thought that the paper addresses an important question in Fair-ML (that is, conditions under which fair data representation leads to fair predictions), and offers potentially significant insights. That said, reviewers found the paper challenging to follow and suggested several concrete steps to improve readability and crystalize the core message. In particular, they suggested authors:
(1) elaborate on the conditions under which their results can be applied to real-world datasets (for example, if the so-called ground-truth label in the training data is itself the result of biased decisions and practices, are the results still applicable? 
(2) Avoid making blanket statements about highly nuanced and controversial topics, such as fairness of automated decision-support tools in the criminal justice context---as expressed in the passage “if you convict all criminals and no one else, you should not be accused of unfairness.”. 
(3) Strengthen the connection between different parts of the paper (e.g., between sections 4 and 5, definitions of adversarial vs. fairness-aware vs. accuracy-aware agents, various fair representation formulations).
(4) acknowledge the worst-case nature of some of the results and their implications (or lack thereof) for real-world settings.
Considering the authors' responses to their suggestions, several reviewers expressed doubt that authors will revise their paper appropriately if accepted. The area chair re-assessed several key points of disagreement between authors and reviewers and concurred with the reviewers that while the paper has the potential for impact, authors need to enhance clarity and accessibility before their work is ready for publication in top-tier venues.
Decision: Reject