Estimating and Controlling for Equalized Odds via Sensitive Attribute Predictors
Authors: Beepul Bharti
Paul Yi
Jeremias Sulam
Venue: NeurIPS 2023 poster (2023)
Keywords: fairness
sensitive attributes
equalized odds
missing data
proxies

Abstract: As the use of machine learning models in real world high-stakes decision settings continues to grow, it is highly important that we are able to audit and control for any potential fairness violations these models may exhibit towards certain groups. To do so, one naturally requires access to sensitive attributes, such as demographics, biological sex, or other potentially sensitive features that determine group membership. Unfortunately, in many settings, this information is often unavailable. In this work we study the well known equalized odds (EOD) definition of fairness. In a setting without sensitive attributes, we first provide tight and computable upper bounds for the EOD violation of a predictor. These bounds precisely reflect the worst possible EOD violation. Second, we demonstrate how one can provably control the worst-case EOD by a new post-processing correction method. Our results characterize when directly controlling for EOD with respect to the predicted sensitive attributes is -- and when is not -- optimal when it comes to controlling worst-case EOD. Our results hold under assumptions that are milder than previous works, and we illustrate these results with experiments on synthetic and real datasets.

Estimating and Controlling for Equalized Odds via Sensitive Attribute Predictors
Beepul Bharti Johns Hopkins University bbharti1@jhu. edu
Paul Yi University of Maryland pyi gyimsom. umaryland edu
Jeremias Sulam Johns Hopkins University J jsulam1 @uu edu
Abstract
As the use machine learning models in real world high-stakes decision settings continues to grow, it is highly important that for any potential fairness violations these models may exhibit towards certain groups. To do so, naturally requires access sensitive attributes, such demographics, biological sex, or other potentially sensitive features that determine group membership. Unfortunately, in many settings, this information is often unavailable. In this work we study the well known equalized odds (EOD) definition of fairness. In setting without sensitive attributes, we first provide tight and computable upper bounds for the EOD violation of predictor. These bounds precisely reflect the worst possible EOD violation. Second, we demonstrate how one can provably control the worst-case EOD by new post-processing correction method. Our results characterize when directly controlling for EOD with respect to the predicted sensitive attributes is and when is not optimal when it comes to controlling worst-case EOD. Our results hold under assumptions that are milder than previous works, and we illustrate these results with experiments synthetic and real datasets.
able audit and control
1 Introduction
Machine learning (ML) algorithms increasingly used in high stakes prediction applications that can significantly impact society. For example, ML models have been used to detect breast cancer in mammograms (37, inform parole and sentencing decisions [14], and aid in loan approval decisions [1.. While these algorithms often demonstrate excellent overall performance, they be dangerously unfair and negatively impact under-represented groups
(38). Some of these unforeseen negative consequences can even be fatal, e.g. deep learning models for chest x-ray disease classification exhibit under diagnosis bias towards certain sensitive groups
(36). Recommendations
to ensure that ML systems do not exacerbate societal biases have been raised by several groups,
including the White House, which in 2016, released report on big data, algorithms, and civil rights 31] It is thus critical to understand how to rigorously evaluate the faimess of ML algorithms and control for unfairness during model development.
These needs have prompted considerable research in the area of Fair ML. While there exist many definitions of algorithmic faimess (7), common notions of group fairness consider different error rates of predictor across different groups: males and females, white and non-white, etc. For example, the equal opportunity criterion requires the true positive (TPR) be equal across both groups, while equalized odds requires both TPR and false positive rate (FPR) to be the same across groups [21]. across
Obtaining predictors that fair therefore requires enforcing these constraints on groups during model development, which can be posed as a constrained (or regularized) optimization problem 35 42
3 16 Alternatively, one can devise post-sson strategies to modify certain predictor to correct for differences in TPR and FPR 22 18 or even include data
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

pre- pre-proeessing steps that ensure that unfair models could not be obtained from such data to begin with 39 g
Naturally, all these techniques for estimating or enforcing fairness require access to a dataset with features, X, responses, Y, and sensitive attributes, A. However, in many setrings this is difficult or impossible, as datasets often do not include samples that have all these variables. This could be because the sensitive attribute data was withheld due privacy concerns, which is very common with medical data due to HIPAA federal law requirements, or simply because it was deemed unnecessary to record 40 43 A real-world example of this is in the recent Kaggle-hoster hosted RSNA Chest X-Ray Pneumonia Detection Challenge [3]. Even though this dataset of chest x-rays was painstakingly annotated for pneumonia disease by dozens of radiologists, it did not include sensitive attributes (e.g., age, sex, and race), precluding the evaluation of fairness of the models developed as part of the challenge. In settings like this, where there is limited or no information on the sensitive attribute of interest, it is still important to be able to accurately estimate the violation of fairness constraints by MI. classifier and to be able to alleviate these violations before deploying in a sensitive application
This leads to the natural question:
How can one assess and control the fairness of a classifier without having access to sensitive attribute data?
In other words, how can we measure and potentially control the fairness violations of a classifier for
Y with respect sensitive attribute A, when we have no data that jointly observes A and Y?
1.1 Related Work
Estimating unfairness and, more importantly, developing fair predictors where there is no- partial information about the sensitive attribute has only recently received increasing attention. The recent work by Zhao et al. [44] explores the perspective of employing features that are correlated with the sensitive attribute, and shows that enforcing low correlation with such "fairness related features" can lead to models with lower bias. Although these techniques are promising, they require domain expertise to determine which features are highly correlated with the sensitive attribute. An appealing alternative that has been studied is the use proxy sensitive attributes that are created by a second predictor trained on a different data set that contains only sensitive attribute information 20
- or only
25 10 5) This strategy has been widely adopted in many domains such as healthcare [17], finance 6 and politics (23]. While using sensitive attribute predictors has proven to be an effective and practical solution, it must be done with care, as this opens new problems for estimating and controlling for fairness. The work by Prost et al. [34] considers the estimation of fairnsss in setting where one develops predictor for an unobserved covariate, but it does not contemplate predicting the sensitive attribute itself. On the other hand Chen et al. [10] study the sources of error in the estimation of fairness via predicted proxies computed using threshold functions, which are prone to over-estimation.
The closest to our work are the recent results by Kallus et al. (25). and Awasthi et al. 5 4. Kallus et al. (25) study the identifiability of fairness violations under general assumptions on the distribution and classifiers. They show that, in the absence of the sensitive attribute, the faimess violation of predictions, Y, is unidentifiable unless strict assumptions are made if there is some common observed data over A and Y. Nonetheless, they show not all hope is lost and provide closed form upper and lower bounds of the fairness violations of Y under the assumption that one has two datasets: one that is drawn from the marginal over (X, A) and the other drawn from the marginal over (X, Y, Y). Their analysis, however, does not consider predictors Ý = f(X) or À = h(X), and instead their bounds depend explicitly on the conditional probabilities, IPA X) and P(PP X), along with the distribution over the features, P(X). Unfortunately, with this formulation, is unclear how the bounds would change if the estimation of the conditional probabilities was inaccurate (as is the case when developing predictors Å in the real world). Furthermore, in settings where X is high dimensional (as for image data), calculating such bounds would become intractable. Since the fairness violation cannot be directly modified, they then study when these bounds can be reduced and improved. However, they do so in settings that impose smoothness assumptions over (X, A, A,Y, y)
Kallus et al. (25 show that if, 8, 1L A X, then the fairness violations are identifiable.

---

which clearly are not-verifialle without data over the complete joint distribution. As a result, their results do not provide any actionable method that could improve the bounds.
Awasthi et al. (5), on the other hand, make progress in understanding properties of the sensitive attribute predictor, A, that are desirable for easy and accurate faimess violation estimation and control of classifier Y. Assuming that Y 11 Ā (A, Y), they demonstrate that the true fairness violation is in fact proportional to the estimated fairness violation (the fairness violation using À in lieu of A). This relationships yields the counter-intuitive result that given a fixed error budget for the sensitive attribute predictor, the optimal attribute predictor for the estimation of the true fairness violation is one with the most unequal distribution of errors across the subgroups of the sensitive attribute. However, one is still unable actually calculate the true fairness violation as it unidentifiable. Nonetheless, the relationship does demonstrates that if one can maintain the assumption above while controlling for fairness with respect to A, then doing will provably reduce the true fairesss violation with respect to A. Unfortunately, while these rather strict assumptions can be met in some limited scenarios (as in [4). these are not applicable in general and cannot even be tested without access to data over (A,Y) Y).
Overall, while progress has been made in understanding how to estimate and control fairness violations in the presence of incomplete sensitive attribute information, these previous results highlight that this can only be done in simple settings (e.g., having access to some data from the entire distribution, or by making strong assumptions of conditional independence). Moreover, it remains unclear whether tight bounds can be obtained that explicitly depend on the properties of the predictor Y, allowing for actionable bounds that can provably mitigate for its fairness violation without having an observable sensitive attribute or making stringent assumptions.
1.2 Contributions
The contributions of our work can be summarized as follows:
We study the well known equalized odds (EOD) definition of fairness in a setting where the sensitive attributes, A, are not observed with the features X and labels Y. We provide tight and computable bounds on the EOD violation of a classifier, ÿ f(X). These bounds represent the worst-case EOD violation of f and employ a predictor for the sensitive attributes, A h(X), obtained from a sample over the distribution AX,
We provide a precise characterization of the classifiers that achieve minimal worst-case EOD violations with respect to unobserved sensitive attributes. Through this characterization, we demonstrate when simply correcting for fairness with respect to the proxy sensitive attributes will yield minimal worst-case EOD violations, and when instead it proves to be sub-optimal.
We provide a simple and practical post-procedd pro-ppocessiig technique that provably yields classifiers that maximize prediction power while achieving minimal worst-case EOD violations with respect to unobserved sensitive attributes.
We illustrate our results on a series of simulated and real data of increasing complexity.
2 Problem Setting
We work within a binary classification setting and consider a distribution Q over (X' x AAx )) where X C R" is the feature space, y {0, 1} the label space, and A = {0, 1} the sensitive attribute space. Furthermore, and adopting the setting of (5), we consider datasets, Dj and D2. The former drawn from the marginal over (X, A) of while D:, is drawn from the marginal (X, y) of Q. In this way, D2 and D, contain the same set of features, D2 contains sensitive attribute information and D2 contains label information. The drawn samples in D1 and D2 are i.idd over their respective marginals and different from one another.
Similar to previous work T0 5l we place ourselves in demographically scarce regime where there is designer who has access to Dj to train a sensitive attribute predictor h X' + A and a developer, who has access to D2. the sensitive attribute classifier h, and all computable probabilites P(h(X), ), A) that the designer of l can extract from D, In this setting, the goal of the developer is to learn classifier f X + y (from D2) that is fair with respect A utilizing A. The central idea is
3

---

to augment every sample in D2, (Is, by (2,, 3h, a.), where à; = h(zz). Intuitively, if the error of the sensitive attribute predictor, denoted herein by U ((((X) * A). is low, we could hope that fairness with respect to the real (albeit unohserved) sensitive attribute can be faithfully estimated. Our goal is to thus estimate the error incurred measuring and enforcing fairness constraints by means of Á = ()),, and potentially alleviate or control for it.
Throughout the remainder of this work we focus on equalized odds (EOD) as our faimess metric 21] of interest as it is one of the most popular notions of fairness. Thus moving forward, the term
fairness refers specifically to EOD. We denote Y = f(X) for simplicity, and for i,j E (0, 1} define the group conditional probabilities
رiم =P= = A = i, j)-
These probabilities quantify the TPR (when j = 1) and FPR (when j = 0), for either protected group = 0 or i = 1). We assume that the base rates, ri,; P(A= = = j) > 0 so that these quantities are not undefined. With these conditionals probabilities, we define the true fairness violation of f, with the two quantities
ASP(( = 01,1 00,1 and AFPR 01,0 0k0,0
(2)
which respectively quantify the absolute difference in TPR and FPRs among the two protected groups.
We also need to characterize the performance of the sensitive attribute classifier, h. The miss- classification error of h can be decomposed as, U = Uo + U1 where U, = P(Ā i, A + i), for i {0. 1). We define the difference errors to be
AU Un- U1.
In a demographically scarce regime, the rates Ti and more importantly the quantities of interest, (fp and AFPR()) cannot be computed because samples from A and Y are not jointly observed. However, using the sensitive attribute classifier h, we can predict Ā on D2 and compute
f. = P(Ā = i, Y = j) and ãr, = pÝ = 1 À = i, Y = j),
which serve as the estimates for the true base rates and group TPRs and FPRs.
3 Theoretical Results
With the setting defined, we will now present our results. The first result provides computable bounds on the true fairness violation of f with respect the true, but unobserved, sensitive attribute A. The bounds precisely characterize the worst-case fairness violation of f. Importantly, as we will explain later, this first result will provide insight into what properties must satisfy so that its worst-case fairness violation is minimal. In turn, these results will lead to a simple post-processing method that can correct pretrained classifier f into another one, f, that has minimal worst-case fairness violations. Before presenting our findings, we first describe the key underlying assumption we make about the pair of classifiers, h and f, so that the subsequent results are true.
Assumption 1. Fo E 10, the classifiers y f(X) and Ā = h(X) satisfy
U,
U²
fjj < ã.j S 1 Pi.
(4)
To parse this assumption, it is easy show that this is met when a) h is accurate enough for the setting, namely that (PA = i, A + i) < PPAAAA = i = j), and b) the predictive power of h is better than the ability of ff predict the labels, Y more precisely, PPA = i, A + i) S P(Ý- -. -- # j). We refer the reader to Appendix A for a thorough explanation for why this is true. While this assumption may seem limiting, this milder than those in existing results: First, accurate predictors h can be developed 6 7 23 19, thus satisfying the assumption (our numerical results will highlight
this fact as well). Second, other works 5 9 require assumptions on Á and Ý that are unverifiable in a demographically scarce regime. Our assumption, on the other hand, can always be easily verified because all the quantities are computable. Furthermore, this assumption can be also be relaxed if one desires partial guarantees. More specifically, if the above is true for E {0, 1} and only for j = 1, then all subsequent results for ATPr hold. Similarly, if it only holds for j = 0, the results for APPR hold. Therefore, one only cares about the equal opportunity definition of fairness, as an example, then this only needs to hold for i {0, 1} and j 1.
4

---

3.1 Bounding Fairness Violations with Proxy Sensitive Attributes
With Assumption in place, we present our main result.
Theorem (Bounds on (fr and (f)) Under Assumption 7 we have that
(tpR(f) - (f _ max + Co.1l, [B - C₁,l3 (FFR(f) & Bfrk(f) e max{ Bb + Co,ul. |Bu C2,l1
(5)
where
fi.j =y= fij + AU" 01j
fo.j
fo.j - AU āos and Ots = =U; fi.s + AU
+ fo.j - AU
Furthermore, the upper bounds for [TPR(()) and (FPR(f) are tight.
The proof, along with all others in this work, are included in Appendix A We now make few remarks on this result. First, the bound is tight in that there exists settings (albeit unlikely) with particular marginal distributions such that the bounds hold with equality. Second, even though AAPRR (f)l and AFpR (f)l cannot be calculated, a developer can still calculate the worst-case faimess violations, BTRR(J and BFPR( because these depend quantities that are all computable in practice. Thus, if (fP and BFFR (f)) are low, then the developer can proceed having a guarantee on the maximal fairness violation of even while not observing | (J)l and |APR (/) On the other hand, if these bounds are large, this implies a potentially large fairesss violation over the protected group by of and the developer should not proceed in deploying and instead seek to learn another classifier with smaller bounds. Third, the obtained bounds are linear in the parameters ōz.j. which the developer can adjust as they are properties of f:: this will become useful shortly.
3.2 Optimal Worst-Case Fairness Violations
Given the result above, what properties should classifiers / satisfy such that BYPR (J) and BEPr (J) are minimal? Moreover, are the classifiers f that are fair with respect to Å, the ones that have smallest (f) and BFPR (f)? We now answer these questions in the following theorem.
Theorem 2 (Minimizers of BTPR (J) and (FFR())). Let Ā = h(X) be fixed sensitive attribute classifier with errors Uo and U1 that produces rates Pi. P(Ā i,Y =]). Let F be the set of all predictors of Y, parameterized by rates āig that, paired with h, satisfy Assumption [ Then, BY E F with group conditional probabilities, Das P(Y 1 Ā i j) that satisfies the following condition,
Po.5 fo.j AU
AU
20.5
+ AU
2
Aij + AU Po.j AU
(6)
Furthermore, any such Y has minimal maximal fairness violation, i.e. vÝ E F.
(Pra( S (IPR( S ( and |APR S BYPR (Y) s BYpR(").
(7)
This result provides precise characterization of the conditions that lead to minimal worst-case fairness violations. Observe that AU * O, the classifier with minimal BTPR (f) and BFPR (f) involves ā., such that ā1, + āo. i.c it not fair with respect to Å. On the other hand, if the errors of h are balanced (AU = 0), then minimal bounds are achieved by being fair with respect to Å.
3.3 Controlling Fairness Violations with Proxy Sensitive Attributes
Now that we understand what conditions must satisfy so that it's worst case fairness violations are minimal, what remains is a method to obtain such a classifier. We take inspiration from the post-processing method proposed by Hardt et al. (1). which derives a classifier Y = f(X) from γ -(X) that satisfies equalized odds with respect to a sensitive attribute A while minimizing an expected missclassification loss only applicable if one has access to A, which not true in our setting. Nonetheless, since our method will generalize this idea, we first briefly comment on this
5

---

approach. The method they propose works as follows; given sample with initial prediction y and sensitive attribute A a, the derived predictor with group conditional probabilities ]i =(Y=1 A= Y, = predicts Y 1 with probability Pa.g P(Y A= a.Y = 9). The four probabilities po.0, Po.0-Po.1-Ph P0,1-PP,00 P1,1 be then calculated so that Y satisfies equalized odds and the expected loss between Y and labels Y, i.e. EYL(Y, Y)]. is minimized. The fairness constraint, along with the objective to minimize the expected loss, give rise to the linear program:
Equalized Odds Post- Post-Processing (Hardt et al. (21)
min
EIL(Y, Y)] subject to Co.j = æij for jE 10,
(8)
E(0.1
Returning to our setting where we do not have access to A but only proxy variables À (X)), we seek classifiers f that are fair with respect to the sensitive attribute A. Since these attributes not available, (thus rendering the fairness violation to be unidentifiable (25)). a natural alternative minimize the worst-case fair violation with respect to A, which can be computed as shown in Theorem[] [ Of course, such an approach will only minimize the worst case faireess and one cannot certify that the true fairness violation will decrease because explained above it is unidentifiable. Nonetheless, since we know what properties optimal classifiers must satisfy (as per Theorem 2 we can now modify the above problem construct a corrected classifier, f. as follows. First, we must employ Á in place of A, which amounts to employing Øs.j in lieu of as,y To this end, denote the (corrected) group conditional probabilities of to be ب.j Second, the equalized odds constraint is replaced with the constraint in Theorem 2
Lastly, also enforce the additional constraints detailed in Assumption on the Czب. With these modifications in place, we present the following generalized linear program:
Worst-case Fairness Violation Reduction
min E(U1)
B[L(Y,))
subject to
fo.
AU
Po.j + AU 2o.j
+
fi.j
AU
2
f1,j AU
fo.j AU
U;
U
S ã.j S
for
E0,
Pi,j
Pij
The solution to this linear program will yield a classifier f that satisfies Assumption 1 has minimal (f and (frx(f), and has minimal expected loss. Note. that AU 0, then the coefficients of 0o and Ø will equal one. and so the first set of constraints simply reduces to Co.j 21,j for j e {0, 1} and the linear program above is precisely the post-processing method of with A in place of A (while enforcing Assumption Ip.
Let us briefly recap the findings of this section: We have shown that demographically scarce regime, one can provide an upper bound on the true fairness violation of classifier (Theorem [ Second, we have presented precise characterization of the classifiers with minimal worst-case fairness violations. Lastly, we have provided a simple and practical post-processing method (a linear program) that utilizes a sensitive attribute predictor to construct classifiers with minimal worst-case fairness violations with respect to the true, unknown, sensitive attribute.
4 Experimental Results
We now illustrate our theoretical results on synthetic and real world datasets. The code and data necessary to reproduce these experiments are available at htttts:://githiii httphuu..oooomcaooo Somm/Sulan Sullam-al Group/ EOD-vith-Proxies
4.1 Synthetic Data
We begin with a synthetic example that allows us to showcase different aspects of our results. The data consists of features, X1, X2, X3 E R, sensitive attribute A e {0, 1}, and response Y e {0, 1).

---

0.25
Amn
0.150
0.160
0.15
0.125
0.158
Fakness
0.100
0.075
0.150
0.05
6,145
0.000
far
fet
far
fape
(a) ATPR and BYPR
(b) AFPR and BYAR
(c) Expected loss
Figure 1: Synthetic data (AU = 0): true fairness violations, worst-case faireess violations, and expected loss for f. fin and fapt
The features are sampled from (X1, X2, Xz) ~ N (1,, Σ), with
1
0.05
p and Σ
0.05
1
0
0
0
0.05
The sensitive attribute, A, response Y, and classifier J, are modeled as
A T[(3 + 0.1) 0]
YI Bermouli( X2 X3 + =0 - A) + +c1A))
f(X;c1, I(S((,(())))))) c2X2 c3 0.5)
where I1()) is the indicator function, 5(.) is the sigmoid function and C1. C2, C3 (1, 0.01). Fur- thermore, 6o ~ [O,, 1), (0, 0.5) are independent noise variables placed on the samples belonging the groups A and A = to ensure there is trivial fairness violation. Specif- ically, Var(co) > Var((r) makes f(X; c1, C2, 0a) unfair with respect to A = 0. Lastly, to measure the predictive capabilities of f. we use the loss function, L(Y # y, Y = y) IP(Y * y), as this maximizes the well known Youden's Index
4.1.1 Equal Errors (AU = 0)
We model the sensitive attribute predictor as
h(X;5) = T((X3 + + 0.1 0)
where 8 NO o²). We choose o² that h(X) has total error U 0.04 distributed so that AU Re O with Un sJ Un R 0.02. We generate 1000 classifiers ʃ and for each one, calculate AIPR. APPR. BIPR. BYPR, and E[L(JYY) Then, each f. we run the (naive) equalized odds post processing algorithm correct for fairness with respect Å to yield a classifier f and we also run post-processing algorithm to yield optimal classifier fapt- For both sets of classifiers we again calculate the same quantities.
The results in Fig. present the true fairness violations, worst-case fairness violations, and expected loss for the sets different classifiers. Observe that both BIPR and ByrR are significantly lower for f and fort and that these values for both sets of classifiers are approximately the same. This is expected Ug U1 and so performing the fairness correction algorithm and our proposed algorithm amount to solving nearly identical linear programs. We also show the true fairness violations, 4TPR and AFPR for all the classifiers to portray the gap between the bounds and the true values. As mentioned before, these true values cannot be calculated in a real demographically scarce regime. Nonetheless, the developer observe that the expected loss for fe; and fop are naturally higher compared to that of f. however increase loss is minimal.
f now knows, post correction, that |APR| [APR S 15. Lastly,
4.1.2 Unequal Errors (AU + 0)
We model the sensitive attribute predictor in the same way as in the previous experiment except with 5 c, for constant e so that the sensitive attribute classifier still has the same total error of
One show that B[L(fY)) = P(Y 1)F(Y 0)(1 Yy) where Yy is the Youden's Index of f.
7

---

0.30
Bie Amn
6ux 2m
0.25
Falmass Villadan
0.165
0.100
0.10
0.150
0.05
0.00
0,140
far
fere
(a) TTPR and BYPR
(h) ATPR and BIyR
(c) Expected loss
Figure 2: Synthetic data (AU * 0): true fairness violations, worst-case faimeess violations, and
expected loss for f. fin and fopt
se 0.04 but distributed unevenly so that AU = -0.04 with Uo = and U1 s 0.04. As in the previous experiment generate classifiers f. and perform the same correction algorithms to yield far and fogt and present the same metrics as before.
The results in Fig. 2 depict the worst-case faimess violations and expected loss for the sets of different classifiers. Observe that our correction algorithm yields classifiers, fups- that have significantly lower BTeR and BFPR. Furthermore, observe that the f that results from performing the naïve fairness correction algorithm in fact have higher BFPR the original classifier f! Even though the total error U has remained the same, its imbalance showcases the optimality of our correction method. Lastly, observe that there a trade-off, albeit slight, in performing our correction algorithm. The expected loss for fopt is higher than that of f and f.
4.2 Real World Data
We will now showcase our results on various real world datasets and prediction tasks. We provide brief description of each task below and further experimental details are included in Appendix
FIFA 2020 (Awasthi et al. [5]): The task is to learn a classifier f. using FIFA 2020 player data 29 that determines if soccer players wage is above (Y 1) or below (Y = 0) the median wage based on the player's s age and their overall attribute. The sensitive attribute is player nationality and the player's name used learn the sensitive attribute predictor h. We consider two scenarios, when A E {English, Argentine) (Englise iigglssh- 0) and A E [French, Spanish) (French=0) =))
ACSPublieCoverage (Ding et al. 15 )): The task is to learn classifier f. using the 2018 state census data, that determines a low-income individual, not eligible for Medicare, has coverage from public health insurance (Y 1) does not (Y 0). The sensitive attribute A sex (Female 0) and with a separate dataset (containing the same features used to learn f (disregarding sex)), we learn the sensitive attribute predictor h. We work with the 2018 California census data.
CheXpert (Irvin et al. (24)): CheXpert is large public dataset for chest radiograph interpretation, consisting of 224,316 chest radio graphs of 65,240 patients, with labeled annotations for 14 observa- tions (positive, negative, or unlabeled) including cardi corgaly, atelec atelectasis consol1 idation, and several others. The task is to learn classifier f to determine if an X-ray contains annotation for any abnormal condition (Y 0) and with separate set of X-rays (different from those used to learn f) we learn the sensitive attribute predictor h.
or does not (Y = 0). The sensitive attribute is sex (Female
4.2.1 Verification Assumption
In Appendix C we provide Table [ which demonstrates that Assumption Iaaiiiionnhhhssss hoolds for the settings described above. The Actual Value column of Table I lists the rates āæ, and the left and right columns list Uz and 1 Uz respectively. From Table it is clear that the ã, lie in between Uz and Fay required by Assumption Notice, only list the estimated group TPRs, ã. 1 for the ACSPublicCoverage 2018 California dataset. This is because Assumption [] for j = 0, does not hold for this state: even though Á is a very accurate predictor for A, the label classifier f has very low estimated group FPRs, 0;,0. As result, our thcoretical results for APPR cannot be used.
F
Fa.s

---

0.10
0.35
de 5m
0.30
Expected
Fainess
0.02
0.00
0.00
(a) ATPR and BYPr
(b) AFPR BYPR
(c) Expected loss
Figure 3: CheXpert data: true fairesss violations, worst-case fairness violations, and expected loss for f. fin and Fopt
4.2.2 Results on CheXpert
The task is to measure and correct for any fairness violations that f may exhibit towards the sex attribute assuming we do not have the true sex attribute and instead have a sensitive attribute predictor, h. On test dataset, we generate our predictions ý f and Å = h to yield a dataset over (Á, Y, Y), for which the sex predictor, h, achieves an of U 0.023 with Uo 0.008 and U1 x 0.015. We utilize the bootstrap method to generate 1000 samples of this dataset and for each sample, perform the same correction algorithms before to yield f and Sapt and calculate the same metrics as done in the previous experiments.
The results in Fig. 3 show that proposed correction method performs the best in reducing PIRR and BYPR. Even though very small, since U1 20,, simply correcting for fairness with respect to Å is suboptimal reducing the worst-case fairness violations. In particular, the results in Fig. noteworthy they depict how proposed correction method and bounds allow the user certify that the obtained classifier has a fairness violation in TPRs of no more than 0.06 without having access to the sensitive attributes. Moreover, the improvement is significant, since before the correction one had ATPR| S 0.10. In a high-stakes decision setting, such as this one where the model could be used aid in diagnosis, this knowledge could be vital. Naturally, the expected loss is highest for fope but that the increase is minimal. We make no claim as to whether this (small) increase in loss is reasonable for this particular problem setting, and the precise trade-offs must be defined in the context of broader discussion involving policy makers, domain experts and other stakeholders.
5 Limitations and Broader Impacts
While our results are novel and informative, they come with limitations. First, our results are limited EOD (and its relaxations) definitions of fairness. Fairness is highly context-specific and in many scenarios one may be interested in utilizing other definitions of faireess. One can easily extend our results to other associative definitions of fairness, such as demographic parity, predictive parity, and others. However, extending our results to counter-factual notions of fairness [28] trivial and matter of future work. We recommend thoroughly assessing the problem and context in question prior to selecting definition. It is crucial to ensure that the rationale behind choosing a definition based on reasoning from both philosophical and political theory, as each definition implicitly make distinct set of moral assumptions. For example, with EOD, we implicitly assert that all individuals with the same true label have the same effort-basee utility [22]. More generally, other statistical definitions of fairness such demographic parity and equality of accuracy
32 is non
be thought of as special instances of Rawlsian equality of opportunity and predictive parity, the other hand, can be thought of as instance of egalitarian equality of opportunity 22 30 3]. We refer the reader to
22 to understand the relationship between definitions of fairness in machine learning and models of Equality of opportunity (EOP) extensively studied ideal of faimess in political philosophy.
second limitation our results Assumption] This assumption relatively mild, as met for accurate proxy sensitive attributes (as illustrated in the chest X-rays study). Yet, we conjecture that one can do away with this assumption and consider less accurate proxy sensitive attributes with the caveat that the worst case fairness violations will no longer be linear in the TPRs and FPRs. Thus, the

---

characterization of the classifiers with minimal worst-case bounds would be more involved and the method to minimize these violations will likely be more difficult. Furthermore, while we proposed simple post-processing correction method, it would be of interest to understand how one could train a classifier - from scratch - to have minimal violations. Lastly, in our setting we assume the sensitive attribute predictor and label classifier are trained on marginal distributions from the same joint distribution. As a next step, it would be important to understand how these results extend to settings where these marginal distributions come from (slightly) different joint distributions. All of this constitutes matter of future work.
Finally, we would like to remark the positive and potentially negative societal impacts of this work. Our contribution is focused on a solution a technical problem estimating and correcting for fairness violations when the sensitive attribute and responses are not jointly observed. However, we understand that fairness is a complex and multifaceted issue that extends beyond technical solutions and, more importantly, that there can be disconnect between algorithmic fairness and fairness in broader socio-technical context. Nonetheless, we believe that technical contributions such as ours can contribute to the fair deployment of machine learning tools. In regards to the technical contribution itself, our results rely on predicting missing sensitive attributes. While such a strategy could be seen controversial - e.g. because it could involve potential negative consequences such as the perpetuation of discrimination or violation of privacy this is necessary to build classifiers with minimal worst-case fairness violations in a demographically scarce regime. On the one hand, not allowing for such predictions could be seen as one form of "fairness through unawareness", which has been proven to be an incorrect and misleading strategy in fairness (2 [0]. Moreover, processing algorithm, similar to that of Hardt et al. (11). admits implementations in a differentially private manner as well, since it only requires aggregate information about the data. As result, our method, which uses an analogous formulation with different constraints, can also be carried out in a manner that preserves privacy. Lastly, note that if one does not follow our approach of correcting for the worst-case fairness by predicting the sensitive attributes, other models trained on this data can inadvertently learn this sensitive attribute indirectly and base decisions of it with negative and potentially grave consequences. Our methodology prevents this from happening by appropriately correcting models have minimal worst-case fairness violations.
post-
Conclusion
In this paper we address the problem of estimating and controlling potential EOD violations towards an unobserved sensitive attribute by means of predicted proxies. We have shown that under mild assumptions (casily satisfied in practice, as demonstrated) the worst-case fairness violations, ByP and BFPR. have simple closed form solutions that are linear in the estimated group conditional probabilities ā.g. Furthermore, we give an exact characterization of the properties that classifier must satisfy so that BIPR and BypR are indeed minimal. Our results demonstrate that, even when the proxy sensitive attributes proxy attributes might be suboptimal in regards to minimizing the worst-case fairness violations. To this end, present simple processrcsssing method that can correct pre-trained classifier f to yield an optimally corrected classifier, J. i.e. one with with minimal worst-case fairness violations.
highly accurate, simply correcting for fairness with respect these
Our experiments on both synthetic and real data illustrate our theoretical findings. We show how, even if the proxy sensitive attributes are highly accurate, the smallest imbalance in Ug and U1 renders the naïve correction for fairness with respect to the proxy attributes suboptimal. More importantly, our experiments highlight our method's ss ability to effectively control the worst-case fairness violation of classifier with minimal decrease in the classifier's 's overall predictive power. On a final observation on our empirical results, the reader might be tempted to believe that the classifier f (referring to, e.g., Fig. 3 is better because it provides lower "true" fairness than that of fapt. Unfortunately. these true fairness violations are not identifiable in practice, and all one can compute are the provided upper bounds, which sop minimizes. In conclusion, our contribution aims to provide better and more rigorous control over potential negative societal impacts that arise from unfair machine learning algorithms in settings of unobserved data.
A Acknowledgments and Disclosure of F Funding
This work was supported in part by NIH award R01 RO1C428742
10

---

References
[1] Philip Adler, Casey Falk, Sorelle A Friedler, Tionney Nix, Gabriel Rybeck, Carlos Scheidegger, Brandon Smith, and Suresh Venkatasubramanian. Auditing black-box models for indirect influence. Knowledge and Information Systems, 54:95-122, 2018.
[2] Alekh Agarwal, Alina Beygelzimer, Miroslav Dudik, John Langford, and Hanna Wallach. A reductions approach to fair classification. In International conference on machine learning. pages 60-69. PMLR, 2018.
[3] Larry Alexander. Fair equality of opportunity: John rawls' (best) forgotten principle. Philoso- phy research archives, 11:197-208, 1985.
[4] Pranjal Awasthi, Matthäus Kleindessner, and Jamie Morgenstern. Equalized odds postprocessing under imperfect group information. In International conference on artificial intelligence and statistics, pages 1770-1780. PMLR, 2020.
[5] Pranjal Awasthi, Alex Beutel, Matthäus Kleindessner, Jamic Morgenstern, and Xuezhi Wang. Evaluating fairness of machine learning models under uncertain and incomplete information. In Proceedings of the 2021 ACM Conference on Fairness, Accountability, and Transparency, pages 206-214, 2021.
[6] Arthur P Baines and Marsha Courchane. Fair lending: Implications for the indirect auto finance market. Study Prepared for the American Financial Services Association, 2014.
[7] Solon Barocas, Moritz Hardt, and Arvind Narayanan. Fairness and Machine Learning: Limita- tions and Opportunities. fairmlbook.org, 2019. http::/www. http://www.aarrmlooookk org
[8] Flavio Calmon, Dennis Wei, Bhanukiran Vinzamuri, Karthikeyan Natesan Ramamurthy, and Kush R Varshney. Optimized pre- pre-processing for discrimination prevention. Advances in neural information processing systems, 30, 2017.
[9] Elisa Celis, Lingxiao Huang, Vijay Keswani, and Nisheeth K Vishnoi. Fair classification with noisy protected attributes: A framework with provable guarantees. In International Conference on Machine Learning, pages 1349-1361. PMLR, 2021.
[10] Jiahao Chen, Nathan Kallus, Xiaojie Mao, Geoffry Svacha, and Madeleine Udell. Fairness under unawareness; Assessing disparity when protected class unobserved. In Proceedings of the conference on fairnes,,, accountability, and transparency, pages 339-348, 2019.
[11] Silvia Chiappa. Path-specific counterfactual faimess.. In Proceedings of the AAAI conference on artificial intelligence, volume 33, pages 7801-7808, 2019.
[12] Exgenii Chzhen, Christophe Denis, Mohamed Hebiri, Luca Oneto, and Massimiliano Pontil. Leveraging labeled and unlabeled data for consistent fair binary classification. Advances in Neural Information Processing Systems, 32, 2019.
[13] Andrew Cotter, Maya Gupta, Heinrich Jiang. Nathan Srebro, Karthik Sridharan, Serena Wang, Blake Woodworth, and Seungil You. Training well well-generalizing classifiers for fairness metrics and other data-dependent constraints. In International Conference on Machine Learning, pages 1397-1405. PMIR, 2019.
[14] Swarup Dhar, Vanessa Massaro, Darakhshan Mir, and Nathan C Ryan. Uncertainty in criminal justice algorithms: simulation studies of the pennsylvania additive classification tool. arXiv preprint arXiv:2112.0030// 2021.
[15] Frances Ding, Moritz Hardt, John Miller, and Ludwig Schmidt. Retiring adult: New datasets for fair machine learning. Advances in neural information processing systems, 34:6478 (66647--6490 2021.
[16] Michele Donini, Luca Oneto, Shai Ben-David, John S Shawe-Taylor, and Massimiliano Pon- til. Empirical risk minimization under fairness constraints. Advances neural information processing systems, 31, 2018.

---

[17] Mare N Elliott, Peter A Morrison, Allen Fremont, Daniel F McCaffrey, Philip Pantoja, and Nicole Lurie. Using the census bureau's surname list improve estimates of race/ethnicity and associated disparities. Health Services and Outcomes Research Methodology, 9:69-83, 2009.
[18] Michael Feldman, Sorelle A Friedler, John Moeller, Carlos Scheidegger, and Suresh Venkata- subramanian. Certifying and removing disparate impact. In proceedingy of the 2 ACM SIGKDD international conference on knowledge discovery and data mining, pages 259-268, 2015.
[19] Judy Wawira Gichoya, Imon Banerjee, Ananth Reddy Bhimireddy, John L Burns, Leo Anthony Celi, Li-Ching Chen, Ramon Correa, Natalie Dullerud, Marzyeh Ghassemi, Shih-Cheng Huang, al. Ai recognition of patient race in medical imaging: modelling study. The Lancet Digital Health, 4(6):e406e441 4, 2022.
[20] Maya Gupta, Andrew Cotter, Mahdi Milani Fard, and Serena Wang. Proxy faimess, 2018.
[21] Moritz Hardt, Eric Price, and Nati Srebro. Equality of opportunity in supervised learning. Advances in neural information processing systems, 29, 2016.
[22] Hoda Heidari, Michele Loi, Krishna P Gummadi, and Andreas Krause. A moral framework for understanding fair ml through economic models of equality of opportunity. In Proceedings of the conference on fairness, accountability, and Iransparency, pages 181-190, 2019.
[23] Kosuke Imai and Kabir Khanna. Improving ecological inference by predicting individual ethnicity from voter registration records. Political Analysis, 24(2):263-272, 2016.
[24] Jeremy Irvin, Pranav Rajpurkar, Michael Ko, Yifan Yu, Silviana Ciurea-Ileus, Chris Chute, Henrik Marklund, Behzad Haghgoo, Robyn Ball, Katie Shpanskaya, et al. Chexpert: A large chest radiograph dataset with uncertainty labels and expert comparison. In Proceedings of the AAAI conference artificial intelligence, volume 33, pages 590-597, 2019.
[25] Nathan Kallus, Xiaojie Mao, and Angela Zhou. Assessing algorithmic faimess with unobserved protected class using data combination. Management Science, 68(3):1959-1981, 2022.
[26] Jacob Devlin Ming-Woi Wei Chang Kenton and Lee Kristina Toutanova. Bert: Pre-training of deep bidirectional transformers for language understanding. In Proceedings of naacL-HLT, volume 1, page 2019.
[27] Diederik Kingma and Jimmy Ba. Adam: A method for stochastic optimization, In International Conference Learning Representations (ICLR), San Diega, CA, USA, 2015.
[28] Matt Kusner, Joshua Loftus, Chris Russell, and Ricardo Silva. Counterfactual fairness. Advances in neural information processing systems, 30, 2017.
[29] Stefano Leone. Fifa 21 complete player dataset, Oct 2020. URL httph:ttp:////t http//ww..kggg// com/ Batasstt//stefaanleeeee//////// www-o-oo-eeeeeeeapeeeeeeeee dataset
[30] Andrew Mason. Levelling the playing field: The idea of equal opportunity and its place in egalitarian thought. OUP Oxford, 2006.
[31] Cecilia Munoz, DJ Patil, and Megan Smith. Big data: A report on algorithmic systems, opportunity, and civil rights. Executive Office of the President, 2016.
[32] Razieh Nabi and Ilya Shpitser. Fair inference on outcomes. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 32, 2018.
[33] Radiological Society of North America. Rsna pneumonia detection challenge, kaggle competi- tion. 2018.
[34] Flavien Prost, Pranjal Awasthi, Nick Blumm, Aditee Kumthekar, Trevor Potter, Li Wei, Xuezhi Wang, Ed H Chi, Jilin Chen, and Alex Beutel. Measuring model fairness under noisy covariates: theoretical perspective. In Proceedings of the 2021 AAAI/ACM Conference on AI, Ethics, and Society, pages 873-883, 2021.
12

---

[35] Yaniv Romano, Stephen Bates, and Emmanuel Candes. Achieving equalized odds by resampling sensitive attributes. Advances neural information processing systems, 33:361-371, 2020.
[36] Laleh Seyyed-Kalantart Haoran Zhang, Matthew BA McDermott, Irene Chen, and Marzyeh Ghassemi. Underdiagnosis bias of artificial intelligence algorithms applied to chest radiographs in under-served patient populations. Nature medicine, 27(12):2176-22 2182, 2021.
[37] Li Shen, Laurie R Margolies, Joseph H Rothstein, Eugene Fluder, Russell McBride, and Weiva Sieh. Deep learning to improve breast cancer detection screening mammography. Scientific reports, 9(1): 2019.
[38] Kush R Varshney and Homa Alemzadeh. On the safety of machine learning: Cyber-physical systems, decision sciences, and data products. Big data, 5(3):466-255, 2017.
[39] Dennis Wei, Karthikeyan Natesan Ramamurthy, and Flavio Calmon. Optimized score transformation for fair classification. Proceedings of Machine Learning Research, 108, 2020.
[40] Joel S. Weissman and Romana Kesmain-Wyyite Advancing health care equity through improved data collection. New England Journal of Medicine, 364, 2011.
[41] Xiaojiao Yu. Machine learning application in online lending risk prediction. arXiv preprint arXiv:1707.0483/ 2017.
[42] Muhammad Bilal Zafar, Isabel Valera, Manuel Gomez Rogriguez, and Krishna P Gummadi. Fairness constraints: Mechanisms for fair classification. In Artificial intelligence and statistics, pages 962 970.. PMLR, 2017.
[43] Yan Zhang. Assessing fair lending risks using race/ethnicity proxies. Management Science, 64 1197 2018.
[44] Tianxiang Zhao, Enyan Dai, Kai Shu, and Suhang Wang. Towards fair classifiers without sensitive attributes: Exploring biases in related features. In Proceedings of the Fifteenth ACM International Conference Web Search and Data Mining, pages 1433-1442, 2022.
13

---

A Proofs
A.1 Explanation of Assumption !
Assumption
For i,j {0, 13, the classifiers & == (X) and Ā = h(X) satisfy
U; و.j S
Uj
Pi.
We now expand on the implications of this assumptions Recall that U; = -P(Ā = i, + i), P P A = i, Y j), and 0ú. PP A= i, j)- Thus Assumption states.
P i. i) S P( = 1.A=i,Y j) - PA i, Y = -) i (10)
Immediately, it is clear that Eq.
10p implies
P(A=i,A
IP A = i, Y -
(11)
PP パ = i i) و 1
(12)
Now, the left inequality of Eq.
10 states
PPÁ = i, A
(13)
and the right inequality of Eq. 10 states
P(P = 1, -, = -AA= i
which implies
(14)
= = -
(15)
If j = 1, then this implies
(16)
P(Å = P
(17)
and if j O,
P(A = i, =
=
(18)
P(Á i S
= PP
-,y =0)
(19)
Any reasonable classifier y would have the properties
P( 0, - 1) = = 1, -
(20)
र = 1,A = 0) s IP( = -, 0)
(21)
Thus, Assumption [ is met when
P(A-iAA00) -
(22)
14

---

A.2 Proof of Theorem
1
We only prove the result for [f)] as the proof for |Arr ( completely analogous.
Proof. The rules of conditional probability and the law of total probability allow us to decompose 01,1 and 0,,1 in the following manner,
011 = P(V =1 - P(Ý = -1==1Y
(23)
(24)
P(A= (AA=1Y==1)
EiE(o.1) P( =LA=-LY=
(25)
Σje(o.1) Cie(o.1) PY -Y=
EiE(o.1) P(Ý -LAA-,Y=1|A- =
(26)
Eje(o.1) Eie(o.1) PP -j==jA==yy=11 -AAAA)
and
00.1 = =PL = -=
(27)
P(Y 1,A=
(28)
P(A=0,Y=1)
= -A P(Y = -1)-[[1-P-
(29)
PPÝ = -1, -iEeOoo..) P( = 1, I,Y = = 1) i)
(30)
P(V = 1) [Ee(a.1) Eie P( = - Y =1 1 PP(A = =)
Therefore, ATPR (f) = 01,11 - -0,1 a function of the four probabilities given by
P(Ý = j, A 1,Y = 1 À [-=i) i)
(31)
which are unidentifiable demographically scarce regime and therefore not computable.
The Fréchet incqualities tell us that for i,j j E 1)
PPC j, A 1, Y À i) max (P(( j, Y 1 Ā = 1) PAA 0 Ā 1)
(32)
P-C = -, = Å 1) (P j,Y Á 1). P(A A 1)
(33)
Observe that, AIPR is an increasing function with respect to the two probabilities
P(Ý = 1, = 1,Y = 1
(34)
and a decreasing one with respect to the two probabilities,
P( 0, 1 = y 1 | A= =).
=
(35)
As result, APpR() (f) maximal when P(Ý- = 1, = = achieve their maximum values and IP = 0, A = 1, = À = i) achieve their minimum values. On the other hand, (fPR(f) is minimal when P(ý = 1,A = 1,Y = 1 === i) achieve their minimum values and P(Y- 0, = 1, = 1, Á = i) achieve their maximum values. With these facts, we now provide the upper bound. Recall from Appendix A.T that Assumption T Timplies
P(Å = i, (
P -
(36)
2
P(Ā = i, < P( = A= s
= - =))
(37)
(38)
15

---

With Assumption 1 we first provide the values of min PP(Y = 0, - = 1, A= =i]]. First,
P( = 0, = 1,1 - -(A A= =) P(Ý
=0,A=1,Y=1]
U1
(39)
P(A=1)
P(A 1)
20
(40)
because P( = 0, = 1,Y = 1) - U1 2 0. Second.
P(ř = P(Å
P(A - - = 0)
P(Y - 1, = 0) - P(A = 0 | À = 0)
P(A = 0)
(41)
P(ř 0, A = 0, =1 P(Å = 0) - Up
P(A=0)
P(A 0)
(42)
P( 0, D,Y =1)
PPA = 0) Uo
P(Á=
P(Á 0)
(43)
P(Ý = 0,A
Uo 1
P(Á=0)
P(A = 0)
(44)
Now note that,
P(C = =0 P = O,Y - PP- = -,
(45)
< = =
Up
(46)
where the second equality is due to Assumption
| As result
P(Ý = A 0,
Up P(Á=0) P(A=0)
15 PIA = 0, = 1) Up
Uo
1
(47)
P(A= =0) 0)
P(A = 0)
F(Á = 0,
=1 0,)= -55
(48)
P(Á = 0)
Therefore,
min [IP(Ý- 0,A = 1,Y =1 1|] = -, 1, Å = 1) - P(A = 0 Á A= 1)
(49)
min [P() = 0, 10 = 1,Y = 1 1|)= 0
(50)
Now we provide the values of max [I(( = =1,A= = 1, -= 0). First,
P(A= = A 1= P(A = 1)
(51)
P(Á = 1)
P(Å- = 1) -
(52)
P(A 1)
P(A = 11Y=1)-U;
(53)
P(A= 1))
-)) P(d = 1)) PPý = 0, À = 1,Y=1)
(54)
IPÁ 1)
P(C = 1, = P(Ý = 1, =1 1|A=1)
(55)
P(A=1)
Second,
P(A 1, 0)
PPA 1/ | Ā= 0)
(56)
P(A = 0)
P( = 1,A=
0,Y
P(ý = 1, = 1|A= 0)
(57)
P(A=
16

---

Therefore,
max [P(Ý = 1, A 1, = 1 - 1, A=1)
(58)
max [P(YY = - = - 0)] =PA- = A
(59)
Plugging these 4 values into ATPR will yield the upper bound.
F1,1 1I
f..
Bi + Co.1
0o,1 + Uo
(60)
11,1 AU
FO
AU
FI, AU
f0.1 AU
One can similarly use the assumptions to derive the lower bound,
f1,1
fo.1
B1 - C1,1 = fI + AU
fo,1 AU 00,1 - U1
( AU
+
(61)
fo.1
AU
and thus TPRR < maxx + Co.1l:
B8 - Ci,1 One can use same arguments to derive the upper
bound for APPR
A.3 Proof of Theorem 2
prove the result for |TPR (f),. We first start by proving the existence portion the theorem.
Let A h(X) be a sensitive attribute classifier with errors Uo and U1 that produces rates fr. F(Ā = i, Y j). Let F be the set of classifiers for Y such that vʃ E F, f and h satisfy Assumption Consider any f E F with group conditional probabilities, 0g. = P(V = 1 Ā i, Y = j). Since we are only proving the result for (TPR(() set = 1. Consider the zy plane, with the æ-axis being ão,1 and the y-axis being Ø1,1- We know,
U, P211
U
U
< Ō.,1 <
(62)
A1
R11
2
The two equations above define rectangular region in the zy plane with a center (2 2) meaning any classifier f E F, has ās that are in this region.
Now, denote to be a the set of classifiers for Y, with group conditional probabilities ã. that satisfy the condition,
f..1 f0.1 AU
AU
CO.1
(63)
ÅI
AU
2
f111 AU iu,1 AU
This condition defines a line in the xy plane meaning any classifier in F has ã that are on this line. Now observe that the classifier / E F with a
z. satisfy the above condition because,
Pu,1
!
f11
f0.1
f1.1
(64)
i., AU
2
11,1 + AU
2
2
io,1 AU
F1,1 + AU
1
fo,1
AU
+ +AU
fI, + +AU - AU
(65)
f0, AU
ÅI, + AU
AU
AU
1+
(66)
fo,1 -
AU
f1.1 + AU
AU
1
(67)
FI,1 + AU
F0.1 AU
This implies that the line defined by Eq. (63) intersects the rectangular region that Assumption defines. As a result, F F is not empty, meaning there exists a classifier f E FF with group conditional probabilities T., that also satisfies the condition.
in f0.1 AU
ÅI PI + AU
AU
( fr1 + AU fu,1 AU
CO.1
(68)
2
17

---

Now we prove that such a classifier has minimal bounds. Theorem tells us that for f E F
(TPR(() & BYPR - max Co.1l, [B] C1,1
Note that B₁ is linear in ã1, and 1 and that Co. and C₁,1 are constants such that B₁ + Co 2 B1 C1,1 simply because B1 + Co,1 is the upper bound for ÅTPR and B, Co,1 is the lower bound. Since these bounds are affine functions shifted by constant, then min max [ 1.1.. [B] C
necessarily occurs when
B1 + -1 11,1
(69)
meaning
2B = -C + Co,1)
(70)
have minimal upper bounds on AtpR) After rearranging terms, this condition is precisely
fa.1
f1,1
AU
1
1
00,11
(71)
AU
ÅI,
AU
2
f1,1 AU
AU
B Experimental Details
FIFA 2020 (Awasthi et al. [5): The task is learn a classifier f, using FIFA 2020 player data 29, that determines if soccer players wage is above (Y = or below (Y = 0) the median wage player nationality based on the player's s age and their overall attribute. The sensitive attribute
and the player's name is used to learn the sensitive attribute predictor h. We consider two scenarios, Spanissh) (French 0).
when A (English, Argentine) (English 0) and E To learn the sensitive attribute predictor h, we train a Bidirectional Encoder Representations from Transformers (BERT) model [26] using an Adam optimizer [27] for 5 epochs. To learn the label classifier f. we train Random Forest classifier. On a test dataset, we generate our predictions = =(X) and Å = h(X) to yield dataset over (, We utilize the bootstrap method to generate 1,000 samples of this dataset and, for each sample, perform the same correction algorithms as before yield / and fug and calculate the same metrics done in the synthetic data experiments. For A E (English, English) the nationality predictor, h, achieves an error of U 0.033 with Un = 0.008 and U1 == 0.015. For A E {French, Spanish] the nationality predictor, h, achieves an error of U 0.053 with Uo ~ 0.025 and U1 = 0.028. The results for both experiments are displayed in Fig. C.I and Fig. C.2, In addition, we include Fig. .... Fig. C.Iee Fig. C.2d and Fig. CC2c. which display the difference between BYPR( (fin) and BTPR (Tpa(Japs) and between 13PR fair) and Byer (Jopu) These figures depict that the bounds of Jape are smaller than the bounds
of f because the histograms
of BYPR(fER) fair? - BYpR (Fpp) and BYPR (f farr - BYPR( (fap)) are strictly to the right of the dashed green vertical line at O, indicating that both differences
greater than equal to 0.
CCSPublicCoverage (Ding et al. [5)): The task learn classifier f. using the 2018 state census data, that determines if a low-income individual, not eligible for Medicare, has coverage from public sex (Female 0) and
health insurance (Y = 1) or does not (Y 0). The sensitive attribute with separate dataset (containing the same features used to learn / (disregarding sex)), we learn the sensitive attribute predictor h. We work with the 2018 California census data. To learn the sensitive attribute predictor h and label classifier f. we train two Random Forest classifiers. On test dataset, generate our predictions y fXX) and Å = h(X) yield dataset over (Å, Y. Y.Ý). We utilize the bootstrap method to generate 1,000 samples of this dataset and, for each sample, perform the same correction algorithms before to yield frr and fog and calculate the same metrics as done in the previous experiments. The sex predictor, ht achieves an error of U = 0.07 with Un Rv 0.05 and Un Rs 0.02. The results for this experiment are in Fig. C.3 In addition, we include Fig. C.3b which displays the difference between BTPR (f and (Tpp)) This figures depict that the TPR bounds of fapt are smaller than the TPR bounds of f because the histogram (I
BIrR(fog) is
strictly to the right of the dashed green vertical line at O, indicating that this difference is greater than
CheXpert (Irvin et al. (4 consisting of 224,316 chest radio graphs of 65,240 patients, with labeled annotations for 14 observa- tions (positive, negative, or unlabeled) including cardicmegaly, atelectasis consolidation.
CheXpert is large public dataset for chest radiograph interpretation,
18

---

and several others. The task is to learn a classifier f to determine if an X-ray contains annotation for any abnormal condition (Y 1) or does (Y 0). The sensitive attribute sex (Female =0) and with separate set of X-rays (different from those used to learn !) we learn the sensitive attribute predictor To learn both and h we use DenseNet12) 21 convolutional neural network architecture. Images are fed into the network with size 320 x 320 pixels. We use the Adam optimizer [27 with default 6-parameters of 3 0.9, B2 0.999 and fixed learning rate of 10-4 Batches are sampled using fixed batch size of 16 images and we train for 5 epochs. On a test dataset, generate predictions Y and Á h to yield dataset over (Á, Y.Y. We utilize the bootstrap method to generate 1,000 samples of this dataset, and for each sample, perform the same correction algorithms before yield f and fop and calculate the same metries done in the previous experiments. The sex predictor, h, achieves an error of U = 0.023 with Uo R 0.008 and U1 0.015. The results for this experiment in Fig.
C Additional Figures & Results
Table I: Verification of Assumption |
Dataset
ūijj
Cr
Actual Value
PL.1
01.1
0.03
0.80
0.97
00.1
0.02
0.78
0.98
CheXpert
01,0
0.17
0.22
0.83
00.0
0.11
0.19
0.89
01,1
0.07
0.93
0.94
FIFA 2020 (English &
0
0.05
0.67
0.95
0.13
0.26
0.87
Argentina)
0g.0
0.03
0.05
0.97
@1,1
0.08
0.86
0.92
FIFA 2020 (French
00,1
0.13
0.83
0.87
& Spanish)
Æ1,0
0.11
0.13
0.89
0,,0
0.10
0.10
0.95
ACSPublicC.verage
@1,1
0.13
0.39
0.87
(California)
00.1
0.24
0.33
0.76
0.40
8mm
0.34
0.35
0.30
Binsss Vilaale
Expected ted Laxe
6.12
0.25
0.4
0.20
0.3
0.30
0.15
0.10
0.08
0.05
0.00
0.0
for
tws
for
fet
(a) ATPR and BTPR
(b) AFFR and ByFR
(c) Expected loss
224
0.12
6.16
2//9
1.6
322
800
6.00
Pow/Sal Rrad
(d) Difference between BYeR(Ees and BYFR (foz)
(e) Difference between Beve and BppR(fop))
Figure C.I: Results for FIFA 2020 dataset with A E (English, Argentine).
19

---

0.40
Falmess Villatian
0.2
0.08
0.15
0.07
0.10
0.05
0.05
0.00
0.04
fAF
Feer
Aat
(a) ATPR and BYeR
(b) ATTR and BITR
(c) Expected loss
033
6.36
0.00
8.04
0.02
0.50
0.00
335
(d) Difference between BITR (fmm and BIPR (fex)
(e) Difference between BEvR(S Fair and (FpR(fop))
Figure C.2: Results for FIFA 2020 dataset with E {French, Spanish].
0.6
0.19
0.5
0.95
Expected
Famest
0.3
0.2
0.168
3.02
6.166
0.0
CODE 0U0S
0300
100
(a) ATPR and ByeR
(b) Difference between (fmr) and Broe(fop))
(c) Expected loss
Figure C.3: Results for ACSPublicCoverage 2018 California census data
20


Reviews:
[{"review_id": "BbPvprUdx0", "reviewer": "Reviewer_XmGE", "summary": "The paper proposes a tight upper bounds for the equalized odds violation of a predictor in a setting without sensitive attributes.\nIt also presents a post-processing correction method to control the worst-case equalized odds violation and presents results on a variety of synthetic and real datasets.\n", "questions": "1. Could you provide more insight into the limitations of Assumption 1 and how these might be addressed?\n\n2. Could you elaborate on how the proposed post-processing correction method could be implemented in real-world scenarios?\n\n3. How could your results be extended to other definitions of fairness, and what challenges might be encountered in this process?\n\n", "limitations": "The paper relies on Assumption 1, which may limit its applicability in scenarios where the proxy sensitive attributes are not accurate. \nDespite this limitation, this work is a nice contribution.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "1. The paper addresses a critical issue in fair ML. \n\n2. The tight and computable upper bounds for equalized odds (EOD) violation is a valuable contribution as it allows for a precise understanding of the worst-case EOD violation of a predictor.\n\n3. The proposed post-processing correction method for controlling worst-case EOD is interesting.\n\n4. The paper is backed by experiments on both synthetic and real datasets, strengthening the validity of the results.", "weaknesses": "1. Assumption 1 may limit its applicability in scenarios where the proxy sensitive attributes are not accurate.\n\n2. The paper's results are limited to EOD and its relaxations as definitions of fairness. Extending the results to other notions of fairness may be non-trivial and deserves further consideration.\n\n3. The paper does not consider how one could train a classifier from scratch to have minimal violations, which could be an important \n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Comment/Concern 1: Limitations of Assumption 1 and how they might be addressed**\n\nAnswer: Absolutely. For clarity, we re-write Assumption 1 below:\n\nFor $i,j \\in \\\\{0,1\\\\}$  the classifiers $\\hat{Y} = f(X)$ and $\\hat{A} = h(X)$, with errors $U_i = P(\\hat A = i, A \\neq i)$, rates $r_{i,j} = P(\\hat A = i, Y = j)$, and conditional errors $\\hat {\\alpha}\\_{i,j} = P(\\hat Y = 1 | \\hat{A}=i, Y = j )$ satisfy \n\n$$\\frac{U_i}{\\hat{r}\\_{i,j}} \\leq {\\hat \\alpha}\\_{i,j} \\leq 1 - \\frac{U_i}{\\hat{r}\\_{i,j}}$$\n\nIn short, this assumption says that the estimated-group conditional errors of $\\hat A$ are not higher than (relatively) to the errors of $\\hat Y$. Naturally, all works that focus on using proxy sensitive attributes to measure fairness make some assumptions, and our work is no different in this regard. However, our assumption is significantly milder than those in existing results. For example, [Awasthi et al., 2021] assume that $\\hat{Y} \\perp \\hat{A} \\mid A,Y$,  which is strict and not verifiable in demographically scarce regimes. Our assumption is directly verifiable in practice, and does not require independence -- it simply requires $\\hat{A}$ to be reasonably accurate. In fact, it has been shown in many settings that accurate $\\hat{A}$ can be developed [Baines and Courchane, 2014, Elliott et al., 2009, Imai and Khanna, 2016, Gichoya et al., 2022], as required by Assumption 1. Lastly, we would like to point out that if Assumption 1 holds for $i \\in \\\\{0,1\\\\}$ and $j = 1$ (only), then all the results for $\\Delta_{TPR}$ hold (similarly for $j = 0$, and $\\Delta_{FPR}$). Thus, if one only cares about the equal opportunity definition of fairness, the assumption only needs to hold for $i \\in \\\\{0,1\\\\}$ and $j = 1$ and one only needs to add this constraint to the post-processing algorithm.\n\nLimitations: When the features $X$ are not predictive of $A$, yielding a poor $\\hat{A}$, Assumption 1 may not hold. In these settings, we can still derive a tight upper bounds. However, they are no longer linear in the group estimated TPRs and FPRs. Thus, the characterization of classifiers with minimal worst-case bounds is more involved and the methods to minimize these violations will likely not be as succinct and elegant as the results we presented. We will include this comment in the revised version of our manuscript.\n\nLastly, we performed additional experiments to demonstrate Assumption 1 holds in various settings. We refer the reviewer to the global author rebuttal for the details of these experiments along with results in the attached **pdf**. \n\n**Comment/Concern 2: Post-processing method in the real world**\n\nAnswer: We envision our method being used in a scenario where one does not have access to $A$ but requires $\\hat{Y}$ to have an Equalized Odds (or its relaxations) violation no greater than a budget $\\epsilon$ (for example, as determined by regulatory agencies). In this scenario, with the use of $\\hat{A}$ and our Theorem 1, one can still compute the worst case fairness violation of $\\hat{Y}$. Furthermore, by means of Theorem 2 and our post-processing algorithm, one can reduce this quantity. Note, this provides a provable certificate, since if the worst case fairness violation is less than epsilon, so is the true fairness violation.\n\n**Comment/Concern 3: Extension to other definitions of fairness**\n\nAnswer: Our results apply to equalized odds, equal opportunity, predictive equality, and can be trivially extended to demographic parity. While this is a restriction, note that this is a main set of fairness definitions considered in many previous works. Extending our results to other definitions, such as causal or individual fairness, is challenging for a variety of reasons.\n\nFor example, in causal fairness, a key quantity of interest is the average treatment effect (ACE), $E[Y(A=1)] - E[Y(A=0)]$, where $Y(A)$ is a counterfactual quantity. Under certain assumptions on the data generating process, techniques from causal inference can be used to identify the ACE [Pearl, 2009]. However, in all such scenarios, the treatment $A$ (i.e. the sensitive attribute) is **observed**. In our setting, $A$ is not observed, and so the way to apply techniques from causal inference remains an unclear but interesting research direction. \n\nAs another example, considering individual fairness requires that \"similar\" individuals are classified \"similarly\" by $\\hat{Y}$. Similarity is measured with respect to a fair metric, $d_x$. If $d_x$ does not involve $A$, then one can easily check if individual fairness holds. If $d_x$ does involve $A$, then evaluating individual fairness relies on how $d_x$ changes when proxies $\\hat{A}$ are used in place of $A$. These are indeed interesting research avenues that will constitute future work.\n\n**Comment/Concern 4: Training a classifier from scratch to have minimal worst-case fairness violations**\n\nAnswer: Empirically, one could do this by an in-processing training method where one is trying to minimize the expected loss of a classifier with the constraints we provide in Assumption 1 and Theorem 2. In doing this, in principle, one would end up with a classifier $\\tilde{Y}$ with minimal worst-case fairness violations and expected loss, potentially smaller than that of classifier $\\overline{Y}$ returned from our post-processing algorithm. This is because in the post-processing algorithm, the set of classifiers one is optimizing over is constrained by the initial predictor $\\hat{Y}$, meaning $\\overline{Y}$ cannot have smaller expected loss than $\\hat{Y}$. The in-training optimization problem would have no such restriction. However, note that our post-processing algorithm is computationally inexpensive and provably optimal, whereas the in-processing counterpart could be computationally expensive and not be necessarily guaranteed (e.g. it would result in an non-convex optimization problem if the classifier is a deep neural net). We will add these discussions to the revised version of our manuscript.\n"}, {"review_id": "6cjucLG9BJ", "reviewer": "Reviewer_RpWQ", "summary": "The paper explores the fairness problem in machine learning when sensitive attributes (e.g., demographics and gender) are unavailable for practitioners. The authors focus on the Equalized-Odds (EOD), a well-known definition of fairness for classifiers. The authors provide bounds for EOD violation in a setting where sensitive attributes are unavailable. Additionally, they propose a post-processing method to control the worst-case EOD. Finally, the authors illustrate their results via synthetic and real-world datasets experiments. ", "questions": "* Is it possible to extend this worst-case analysis to other post-processing methods? Combining it with the optimized method proposed in [1] would be very interesting.\n\n* In Theorem 2 the authors assume that $\\mathcal{F}$ is such that $ \\forall f \\in \\mathcal{F}$ the Assumption 1 is followed. After that, they conclude that then, there exists a fair model in $\\mathcal{F}$. This doesn’t seem correct. For example, take $\\mathcal{F} = \\{f_0\\}$ where $f_0$ follows Assumption 1 but is not worst-case optimal. Then, there is no fair model in $\\mathcal{F}$. Perhaps, the authors mean $\\mathcal{F}$ to be the set of *all* models that follow Assumption 1. However, in this case, assuming knowledge of $\\mathcal{F}$ does not sound reasonable. Could the authors clarify this point?\n\n* Could you describe (in the main paper) when the worst-case bound is achieved?\n", "limitations": "The authors discuss their work limitations. I also suggest discussing the ethics of predicting users' sensitive attributes. ", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "* The paper is very well written. Particularly the related work section is very informative.\n\n* The authors explore an interesting problem for the community and propose a different view of the problem, i.e., a worst-case optimization. \n\n* The theoretical guarantees provide a method for practitioners to access the quality of the method (assuming a worst-case scenario).\n\n* The proposed method is simple, intuitive, and computationally inexpensive. \n", "weaknesses": "* The evaluation in the main paper is limited. The authors only apply their method to one real-world example. I suggest adding at least two more examples and as many examples as possible in the appendix. These examples can convince us that: (i) Assumption 1 is followed in multiple scenarios and (ii) your method helps to improve fairness. \n\n*  The fact that the Naïve approach had a better \"true\" EOD is interesting, and it might indicate that your method is not very efficient, i.e., using the sharp upper bound as a proxy for the true value is too pessimistic. Performing more experiments in real-world datasets can help the authors and readers understand when minimizing the upper bound is better than the naïve approach. \n\n* It needs to be clarified how to extend the approach to a setting where the sensitive attribute is not binary. In the introduction, the authors list examples of sensitive attributes as \"demographics and gender,\" which are not binary. A subsection is recommended to discuss how your results would change when $A$ is not binary. \n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Comment/Concern 1: More real-world experiments to convince us that Assumption 1 is followed in many scenarios and your method helps to improve fairness.**\n\nAnswer: Thank you for the suggestion. We have performed additional experiments to show that Assumption 1 holds in multiple scenarios and showcase the utility of our results. We refer the reviewer to the global author rebuttal which provides details of the experiments and an attached **pdf** which contain the results.\n\nWe would also like to comment on the point the reviewer made that our method \"helps to improve fairness\". It actually improves the worst-case fairness violation and we make no claim that it reduces the true violation. As we explain in our paper, doing so is impossible in general: one cannot claim that performing any correction of $\\hat Y$ with respect to $\\hat A$ provably reduces the true violation unless strict and unverifiable assumptions are made about $\\hat A$ and $\\hat Y$ (See Awasthi et al. [2021] and Kallus et al. [2022] for further details)\n\n**Comment/Concern 2: Naïve approach had a better true EOD**\n\nWe thank the reviewer for bringing this up. On one hand, improvements on the real fairness are not verifiable (as explained above). On the other hand, Awasthi et al. [2019] study the properties of a classifier $\\tilde{Y}$ that comes from using the post-processing method by Hardt et al. [2016] with noisy sensitive attributes $\\hat A$ in lieu of $A$ (i.e. the \"naive\" approach). They provide conditions on $\\hat A$ that are necessary for $\\tilde{Y}$ to have a smaller true fairness violation than the original classifier, $\\hat{Y}$. One is that $\\hat{Y} \\perp \\hat{A} \\mid A,Y$, which is strict and not verifiable in demographically scarce regimes. So when this condition does not hold, no guarantees exist that show that correcting with respect to $\\hat{A}$ reduces the true fairness violation. While our post-processing method also does not provide any guarantee about the true violation, it is guaranteed to provably reduce the worst-case violation.\n\n**Comment/Concern 3: Extending the result to settings with non binary sensitive attributes**\n\nWe agree that cases where $A$ is not binary are interesting. Definitions of fairness can be extended to these situations. For simplicity, suppose one wants to enforce Equal Opportunity and $A \\in \\{1, \\dots, k\\}$. Then one can require $P(\\widehat{Y} = 1 \\mid A = i, Y = 1) = P(\\widehat{Y} = 1 \\mid A = j, Y = 1)$ for all $i \\neq j$. Enforcing this using the method in Hardt et al. [2016] would mean including $\\frac{k(k-1)}{2}$ constraints. In our setting, to reduce the worst-case violations using $\\hat{A}$ we would also have to include $\\frac{k(k-1)}{2}$ constraints since there are that many bounds to reduce. While this can be done, it will naturally result in the expected loss to increase since there are more constraints.\n\n**Comment/Concern 4:  Extending worst-case analysis to other post-processing methods/Combining it with the optimized method in [1].**\n\nIn Theorem 2 we provide necessary conditions for $\\hat Y$ to have minimal worst-case fairness violations. As long we can add these constraints to other post-processing methods, we believe we can combine our analysis with other methods. The reviewer mentions a method proposed in [1] without a citation. We will gladly answer any questions about combining our results with this method once the reviewer clarifies which work they are referencing.\n\n**Comment/Concern 5: Clarity of Theorem 2**\n\nWe thank the reviewer for pointing out this inaccuracy in our original statement of Theorem 2 -- we meant that $\\mathcal F$ simply parametrizes estimators for the random variable $Y$. Here is the rewritten version of the result in its correct form.\n\nTheorem 2: Let $\\hat{A} = h(X)$ be a fixed sensitive attribute classifier with errors $U_0$ and $U_1$ that produces rates $\\hat{r}\\_{i,j} = P(\\hat{A} = i, Y = j)$. Let $\\mathcal{F}$ be the set of all predictors of $Y$ parametrized by the rates $\\hat{r}\\_{i,j}$ that, paired with $h$, satisfy Assumption 1. Then, $\\exists \\overline{Y} \\in \\mathcal{F}$ with group conditional probabilities, $\\widehat{\\underline{\\alpha}}_{i,j} =  P(\\overline{Y} = 1 \\mid \\hat{A} = i, Y = j)$ that satisfy the following condition, \n\n$$\\frac{\\hat{r}\\_{0,j}}{\\hat{r}\\_{0,j} - \\Delta U}\\widehat{\\underline{\\alpha}}\\_{0,j} - \\frac{\\hat{r}\\_{1,j}}{\\hat{r}\\_{1,j} + \\Delta U}\\widehat{\\underline{\\alpha}}\\_{1,j} = \\frac{\\Delta U}{2}\\\\left(\\frac{1}{\\hat{r}\\_{1,j} + \\Delta U} + \\frac{1}{\\hat{r}\\_{0,j} - \\Delta U}\\\\right)$$\n\nFurthermore, any such $\\overline{Y}$ has minimal maximal-fairness violation:\n\n$$|\\Delta\\_{TPR}(\\overline{Y})| \\leq B\\_{TPR}(\\overline{Y})  \\leq {B}_{TPR}(\\hat{Y}) \\quad \\text{and} \\quad |\\Delta\\_{FPR}(\\overline{Y})| \\leq B\\_{FPR}(\\overline{Y}) \\leq {B}\\_{FPR}(\\hat{Y})$$\n\nThis states that any predictor of $Y$ that satisfies Assumption 1 AND the condition above, has a worst case fairness violation that is less than or equal to any predictor of $Y$ that only satisfies Assumption 1. In other words, this condition is a necessary condition for the worst case fairness violation to be minimal.\n\n**Comment/Concern 5: Could you describe when the worst-case bound is achieved?**\n\nAnswer: Certainly, we will add this in the revised version of the paper. Under Assumption 1, for $\\Delta_{TPR}$, the bound is achieved when for $i \\in \\\\{0,1\\\\}$ the unobserved quantities $P(\\hat{Y} = 1, A = 1, Y = 1 \\mid \\hat{A} = i)$ and $P(\\hat{Y} = 0, A = 1, Y = 1 \\mid \\hat{A} = i)$ achieve their feasible maximal and minimal values respectively. To be more precise, when:\n$$P(\\hat{Y} = 1 , A = 1 , Y = 1 \\mid \\hat{A} = 1) = P(\\hat{Y} = 1 , Y = 1 \\mid \\hat{A} = 1)$$\n$$P(\\hat{Y} = 1 , A = 1 , Y = 1 \\mid \\hat{A} = 0) = P(A = 1 \\mid \\hat{A} = 0)$$\n$$P(\\hat{Y} = 0 , A = 1 , Y = 1 \\mid \\hat{A} = 1) = P(\\hat{Y} = 0 , Y = 1 \\mid \\hat{A} = 1) - P(A = 0 \\mid \\hat{A} = 1)$$\n$$P(\\hat{Y} = 0 , A = 1 , Y = 1 \\mid \\hat{A} = 0) = 0$$\n\nA similar result holds for $\\Delta\\_{FPR}$"}, {"review_id": "juXC2yIVrE", "reviewer": "Reviewer_ntnH", "summary": "This work provides tight and computable bounds on the EOD violation of a classifier in a setting where the sensitive attributes are unknown. In addition, a post-processing technique is proposed to provably yield classifiers that maximize prediction power while achieving minimal worst-case EOD violations with respect to unobserved sensitive attributes. Experiments are done on both synthetic and real data.", "questions": "Q1: can you elaborate on the potential bad outcome of applying $f_{opt}$ yields a less accurate and more biased (in terms of $\\Delta_{FPR}$) model as in Figure 3?\n\nQ2: Is that possible to use a different dataset of similar features (but not the same features as in the experiments) to learn $\\hat{A} = h(X)$ (in some form of transfer learning)?  ", "limitations": "Results on the CheXpert data shows that, although the proposed method successfully reduces the worst case scenario TPR and FPR, it may actually increase the true TPR or FPR. Figure 3b shows an increase of $\\Delta_{FPR}$ of $f_{opt}$ over $f$. This should be discussed as the potential outcome of applying $f_{opt}$ can be a less accurate and more biased model.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "Significance: The problem under study is interesting and important. It would be useful to be able reduce the upper bound of certain fairness violation in models when sensitive attributes are unknown.\n\nOriginality and quality: the proposed solution is novel and technically sound.\n\nClarity: the presentation is clear with limitations analyzed in details.", "weaknesses": "1. One assumption of the proposed approach is that there exists a dataset of (X,A) to learn $\\hat{A} = h(X)$ from. This could limit the use of the approach and should be discussed.\n\n2. It would be beneficial to demonstrate the verification of Assumption 1 on the two datasets.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Comment/Concern 1: Assumption of the proposed approach is that there exists a dataset of $(X,A)$ to learn $\\widehat{A} = h(X)$. This could limit the use of the approach and should be discussed**\n\nAnswer: We completely agree. All the contributions of our work rely on there being a dataset of $(X,A)$ to learn $\\widehat{A} = h(X)$. As we explain in the Introduction, this is a milder assumption (or often alternative assumption) to having a dataset from the entire joint distribution over $(X,Y,A)$. Our results are limited to such cases, however, so they do not apply when a predictor $\\widehat{A}$ for $A$ cannot be constructed.\n\n**Comment/Concern 2: Verification of Assumption 1 on the two datasets**\n\nAnswer: We thank the reviewer for mentioning that we do not formally demonstrate that Assumption 1 holds on the datasets used in our experiments.  We refer the reviewer to the global author rebuttal where there is **pdf** attached. In this pdf we provide Table 1 that demonstrates that Assumption 1 (or its relaxations) holds for the datasets in the paper along with new data sets (descriptions of the new datasets/experiments are detailed in the global author rebuttal).\n\n**Comment/Concern 3: Can you elaborate on the potential bad outcome of applying $f_{opt}$ yields a less accurate and more biased**\n\nAnswer: Certainly. The reviewer is correct: it it clear from Figure 3 that applying $f_{opt}$ yields a less accurate and more biased (in terms of $\\Delta_{FPR}$) model. Using such a model could thus be seen as controversial because it might perpetuating unfairness. However, in some settings, one may have the goal of constructing a classifier, $f$, that has a fairness violation that does not exceed a budget $\\epsilon$ (for example, as required by regulatory agencies). In these cases, our method allows one to potentially achieve this goal by reducing the worst-case violation so that it is less than $\\epsilon$.  Nonetheless, we recommend thoroughly assessing the problem at hand with domain experts to assess if the potential (small) bias introduced by our method constitutes a manageable risk. This is because in a demographically scarce setting one cannot calculate the true fairness violation, and thus, one cannot have an idea of how the true violation ultimately changes as $f$ is modified.\n\n**Comment/Concern 4: Is it possible to use a different dataset of similar features (but not the same features as in the experiments) to learn $\\widehat{A} = h(X)$ (in some form of transfer learning)**\n\nAnswer: In some restricted sense, yes: one could learn a $\\widehat{A} = h(X)$ from $\\mathcal{D}_1$ using whatever features that are available to the user. However, these features must be present in the dataset $\\mathcal{D}_2$ over $(X,Y)$ that is used to learn $\\widehat{Y} = f(X)$. If this is not the case, then the user with access to $\\mathcal{D}_2$, would not be able to impute proxy sensitive attributes $\\widehat{A}$ in lieu of $A$ and compute the bounds on the true fairness violations. However, the features in $\\mathcal{D}_1$ might include more features than those present in $\\mathcal{D}_2$\n"}]

Author rebuttal:
We would like to thank all the reviewers for the insightful questions about our work. All the reviewers had questions about and wanted to see a verification of Assumption 1. For clarity, we re-write Assumption 1 below:

For $i,j \in \\{0,1\\}$  the classifiers $\widehat{Y} = f(X)$ and $\widehat{A} = h(X)$, with errors $U_i = P(\hat A = i, A \neq i)$, rates $r_{i,j} = P(\hat A = i, Y = j)$, and conditional errors $\hat {\alpha}\_{i,j} = P(\hat Y = 1 | \hat{A}=i, Y = j )$ satisfy 

$$\frac{U_i}{\hat{r}\_{i,j}} \leq {\hat \alpha}\_{i,j} \leq 1 - \frac{U_i}{\hat{r}\_{i,j}}$$

We first would like to point out that the assumption can be relaxed, meaning, if it holds for $i \in \\{0,1\\}$ and for $j = 1$ (only), then all the results for $\Delta_{TPR}$ still hold. Similarly, if these hold for $j = 0$, the results for $\Delta_{FPR}$ hold true. As a result, if one only cares about the equal opportunity definition of fairness, one only needs a relaxation of the assumption to hold (it just needs to hold for  $i \in \\{0,1\\}$ and $j = 1$) and only this constraint needs to be added to the post-processing algorithm.

In the attached **pdf**, the results in Table 1 verifies that Assumption 1 (or its relaxations) indeed holds for various datasets. We also present Figures 1 and 2, which extend our results for these new datasets.  We will discuss the table and figures in more detail, but we first provide a brief summary of the new experiments below:

**FIFA Experiment** (Adopted from Awasthi et al. [2021]): We use the FIFA 20 player dataset and aim to predict whether a soccer player’s wage is above ($Y = 1$) or below ($Y = 0$) the median wage based on the player’s age and their overall attribute. We consider nationality as the sensitive attribute $A$ and use the player's name to predict this attribute. Assumption 1 holds for various pairs of nationalities and in Table 1 we demonstrate this for the Argentine/English and France/Spain pairs.

**ACSPubCov** Experiment (Adopted from Ding et al. [2021]): The task is to predict, using 2018 state census data, whether a low-income individual, not eligible for Medicare, has coverage from public health insurance . We consider sex to be sensitive attribute $A$. We determine that for 28 out of 50 states, Assumption 1 holds for $\Delta_{TPR}$ while the assumption for $\Delta_{FPR}$ does not hold for any. We showcase that Assumption 1 holds for the state of Illinois.

We now discuss the figures and tables.

**Table 1**

We provide Table 1, which demonstrates that Assumption 1 (or its relaxations) holds for a variety of experiments/datasets. The *Actual Value* column of Tables 1a and 1b lists the ${\hat \alpha}\_{i,j}$ and the left and right columns list $\frac{U_i}{\hat{r}\_{i,j}}$ and $1 - \frac{U_i}{\hat{r}\_{i,j}}$ respectively for all the datasets. From Table 1, it is clear that the ${\hat \alpha}\_{i,j}$ lie in between $\frac{U_i}{\hat{r}\_{i,j}}$ and $1 - \frac{U_i}{\hat{r}\_{i,j}}$ as is required by Assumption 1. Notice, we only list the estimated group TPRs, ${\hat \alpha}\_{i,1}$ for the ACSPubCov Illinois dataset. This is because, as mentioned, Assumption 1 fails to hold for $\Delta_{FPR}$ for all 50 states. The reason for this is that, while $\widehat{A}$ is indeed very accurate (e.g. $U \approx 0.08$ on the Illinois data), the label classifier $\widehat{Y}$ has very low estimated group FPRs ${\hat \alpha}\_{i,0}$.

In conclusion, these new results show that our assumption holds in several real datasets and cases, while also showcasing when (and why) it doesn't. 

**Figures 1 and 2** 

In Figure 1, we present the results for the FIFA 2020 player dataset restricted to English and Argentine nationalities. Similar to the experiments in the manuscript, we learn a sensitive attribute predictor $\hat{A} = h(X)$ which achieves an error of $U = 0.025$ with $U_1 \approx 0.02$ and $U_0 \approx 0.005$ and we learn a label classifier $\hat{Y} = f(X)$. On a test data set, we generate our predictions $\hat{Y} = f$ and $\hat{A} = h$ to yield a dataset over $(\hat{A}, Y, \hat{Y})$ and utilize the bootstrap method to obtain to generate 1000 samples from this dataset and for each sample, perform the correction algorithms to yield $f_{\widehat{\textrm{fair}}}$ and $f_{\textrm{opt}}$. Figure 1a and 1b display $B\_{TPR}$ and $\Delta\_{TPR}$ (not identifiable) for the various classifiers. We additionally add Figure 1d and 1e which are normalized histograms constructed from the bootstrapped samples of $B\_{TPR}(f_{\widehat{\textrm{fair}}}) - B\_{TPR}(f_{\textrm{opt}})$ and $B\_{FPR}(f_{\widehat{\textrm{fair}}}) - B\_{FPR}(f_{\textrm{opt}})$. Observe how both quantities are greater than or equal to 0, indicating that $B\_{TPR}(f_{\textrm{opt}})$ and $B\_{FPR}(f_{\textrm{opt}})$ are smaller than $B\_{TPR}(f_{\widehat{\textrm{fair}}})$ and $B\_{FPR}(f_{\widehat{\textrm{fair}}})$ respectively. This indicates that our post-processing method is better than simply correcting with respect to $\hat A$ in regards to reducing the worst-case fairness violation (in fact our method is optimal as noted in Theorem 2). Lastly, Figure 1c shows that the expected loss increases for $f_{\textrm{opt}}$ but that the increase is minimal.

We perform the same experimental process on the ACSPubCov Illinois dataset and the results for the TPR quantities are depicted in Figure 2. Note we do not show FPR related quantities because Assumption 1 fails to hold.


Meta-review: After some discussion, all reviewers agreed that the paper should be accepted. The authors should incorporate their reply to the reviewers that further justified Assumption 1.
Decision: Accept (poster)