Optimal Fair Learning Robust to Adversarial Distribution Shift
Authors: Sushant Agarwal
Amit Deshpande
Rajmohan Rajaraman
Ravi Sundaram
Venue: ICML 2025 poster (2025)
Keywords: Fairness
Randomization
Classification
Bayes-Optimal
Robustness
Distribution Shift
Adversarial Noise
Corrupted Data
Primary area: social_aspects->fairness

Abstract: Previous work in fair machine learning has characterised the Fair Bayes Optimal Classifier (BOC) on a given distribution for both deterministic and randomized classifiers. We study the robustness of the Fair BOC to adversarial noise in the data distribution. Kearns & Li (1988) implies that the accuracy of the deterministic BOC without any fairness constraints is robust (Lipschitz) to malicious noise in the data distribution. We demonstrate that their robustness guarantee breaks down when we add fairness constraints. Hence, we consider the randomized Fair BOC, and our central result is that its accuracy is robust to malicious noise in the data distribution. Our robustness result applies to various fairness constraints---Demographic Parity, Equal Opportunity, Predictive Equality. Beyond robustness, we demonstrate that randomization leads to better accuracy and efficiency. We show that the randomized Fair BOC is nearly-deterministic, and gives randomized predictions on at most one data point, hence availing numerous benefits of randomness, while using very little of it.

Optimal Fair Learning Robust to Adversarial Distribution Shift
Sushant Agarwal
Amit Deshpande
Rajmohan Rajaraman !
Ravi Sundaram
Abstract
tions in optimal fair classification (Menon & Williamson, 2018b). In group-fair classification, each data point has cer- tain sensitive attributes indicating the demographic group(s) to which it belongs (e.g,, race, gender). Popular notions of group-fairness such as statistical or demographic par- ity, equal opportunity, equalized odds, and predictive parity are all motivated by the binary fair classification setting. Demographic parity prescribes the positivity rates to be equal across different groups (e.g., race, gender), whereas equal opportunity prescribes the true positive rates to be equal across different groups (Dwork et al., 2012; Hardt et al., 2016). Previous work has looked at various trade-offs between accuracy and fairness as well as the difficulty in sat- isfying multiple fairness constraints simultaneously (Celis et al., 2020). Previous work has also mathematically charac- terized the Fair Bayes Optimal Classifier (BOC), namely, the optimal deterministic classifiers for maximizing accuracy subject to group-fairness constraints based such as demo- graphic parity and equal opportunity (Menon & Williamson, 2018 8a; Chzhen et al., 2019; Celis et al., 2021; Zeng et al., 2022). Pre-processing or re-weighing for training data im- balances, in-processing by caintas-constrainee training loss, and post-processing a model's predictions for balanced out- comes three known ways to realize fair and accurate classifiers in practice (Kamiran & Calders, 2012; Agarwal et al., 2018; Barocas et al., 2019).
Previous work in fair machine learning has char- acterised the Fair Bayes Optimal Classifier (BOC) on given distribution for both deterministic and randomized classifiers. We study the robustness of the Fair BOC adversarial noise in the data distribution. Kearns& & Li (1 (1988) implies that the accuracy of the deterministic BOC without any fairness constraints is robust (Lipschitz) to mali- cious noise in the data distribution. We demon- strate that their robustness guarantee breaks down when we add fairness constraints. Hence, we consider the randomized Fair BOC, and our cen- tral result is that its accuracy is robust to mali- cious noise in the data distribution. Our robust- ness result applies to various fairness constraints- Demographic Parity, Equal Opportunity, Predic- tive Equality. Beyond robustness, we demonstrate that randomization leads to better accuracy and efficiency. However, show that the random- ized Fair BOC is nearly-deterministic, and gives randomized predictions on at most one data point, hence availing numerous benefits of randomness, while using very little of it.
Biased or corrupted training data is a primary cause of unfair- ness in model predictions or outcomes. Moreover, robust- ness of a machine learning model under bias or corruption in the data distribution has been a more pragmatic concemn that predates the research on fair machine learning. Learning robust classifiers is important because training and test dis- tributions are not always identical and the training data may contain noise and malicious corruptions during data collec- tion, curation, and annotation. Robustness of fair classifiers under bias/shift in the data distribution is a well studied is- sue in fair machine learning literature. Akpinar al. (2022) empirically study the robustness of BOC and Fair BOC on synthetic data distributions and provide sandbox tool for stress- testing fair classifiers. Sharma et al. (2023) and Ghosh et al. (2023) empirically study robustness of fair classifiers under data bias on semi-synthetic real-world datasets (i.e., real-world datasets with synthetically injected bias/shift). In both these papers, Exponentiated Gradient Reduction
1. Introduction
The effectiveness of machine learning models has resulted in improved efficiency across multiple domains but has also raised concerns about their fairness and possible amplifica- tion of biases in their training data (Barocas et al., 2019). When machine learning models are used to make decisions that skew the distribution of important economic resources or reinforce stereotypes, they compound disparities to cause social and economic harm. Fair classification has been an important topic of research, and binary fair classification where the model makes yes/no decisions algorithmically is simple yet challenging setting to study foundational ques-
NNottheastern University *Microsoft Research. Correspon- dence to: Sushant Agarwal <agarwal. northeastem.edux>
Proceedings of the nrnd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 20255 by the author(s).

---

Optimal Fair Learning Robust to Adversarial Distribution Shift
(EGR) or ExpGrad (Agarwal al., 2018) stands out for its better robustness under data bias/shift, and it is inherently randomized classifier.
adversarial distribution shift, which in turn is the focus of this paper.
1.1. Overview of Our Results
A particularly compelling and illustrative practical exam- ple for fair binary classification with maliciously corrupted training data is that of hate speech classifiers. Hate speech classifiers are known to exhibit biases against the same vulnerable demographics they were supposed to protect in online forums. For example, text in African American En- glish (AAE) has higher likelihood of being misreported as hate speech and even proper mentions of group identifiers such as "gay" or 'black' get misreported as toxic or preju- diced. Moreover, the training data taken from online forums that is used to train hate speech classifiers contains societal biases of novice human annotators as well malicious at- tempts made to bypass existing classifiers filters used in data collections and annotation process (Davani et al., 2023; Davidson, 2023). Maliciously corrupted training data makes it difficult to train fair hate speech classifiers with robust accuracy and fairness guarantees that would be retained af- ter real-world deployment (Davani et al., 2023; Davidson, 2023; Hartvigsen al., 2022; Harris al., 2022).
We summarize our key contributions.
We demonstrate in Claim (Section 3.1) that the de- terministic Fair BOC is not robust to adversarial noise, corroborating Konstantinov & Lampert (2022).
Our main results prove the robustness of randomized Fair BOC's.
We prove in Theorems 1 (Section 3.2), 2 and (Sec- tion 4) that the accuracy of the randomized Fair BOC robust to malicious noise across three popular fairness notions (Demographic Parity, Equal Opportunity, and Predictive Equality). This robustness is characterized by a (local) Lipschitz property, where the Lipschitz con- stant depends on the distribution (Yang et al., 2020).
Toward this end, we first prove in Claims 2, 3, and 7 (Sections 3.2 and 4) that fixed hypothesis maintains comparable accuracy and fairness across two similar distributions. This, however, does not imply our main results since the Fair BOC may change significantly for neighboring distributions. We establish the Lipschitz property using a more sophisticated analysis of the specific structure of the randomized Fair BOC.
Classification under malicious noise is theoretically chal- lenging direction on its own, even without any fairness constraints. Balcan & Haghtalab (2020) survey research di- rections that originate from the work of Kearn& & Li (1988), but focus on the hardness of learning linear classifiers un- der malicious noise and recent results that get around it.
Unlike previous works on learning from malicious noise that consider any hypothesis class specific one such as linear classifiers, we consider the hypothesis class of all binary classifiers, deterministic as well as randomized. Although previous work in fair machine learning has exten- sively studied the Fair BOC and fair pre-fin-/post-preeee methods to achieve best possible fairness-aceuracy trade- offs. their fairness and accuracy guarantees may not hold when training data is biased or contaminated and does not match test data. Adversarial or unknown bias in data makes it important to study the robustness of fairness and accuracy guarantees of the Fair BOC.
In addition to robustness, randomization confers multiple advantages.
Claim I demonstrates that the Randomized Fair BOC outperform its deterministic counterpart in accu- racy by 0.5 (for any e >> 0). We complement this with tightness result in Claim 6 (Appendix A).
The Randomized Fair BOC can be computed in poly- nomial time, whereas we prove in Claim 5 (Appendix A) that computing the deterministic Fair BOC is NP- complete.
The seminal work of Kearn& & Li (1988) shows the robust- ness (of accuracy) to malicious noise of any deterministic hypothesis class (without fairness constraints) in terms of Lipschitz condition, i.e., given two similar distributions, the accuracy of the optimal classifier on each distribution is also similar. In particular, their robustness guarantee also car- ries over to the deterministic BOC. In contrast, more recent findings by Konstantinov & Lampert (2022) reveal a con- cerning vulnerability: incorporating fairness constraints can render certain deterministic hypothesis classes non-robust to adversarial noise. This gap in understanding necessitates an investigation into the robustness of Fair BOC's under
Randomization is a very natural and useful resource for fair- ness as ties are often broken by a random coin toss. However, when brings arbitrariness to critical decisions, it needs to be used judiciously and sparingly (Creel & Hellman, 2021; Rosenblatt & Witter, 2024; Cooper al., 2024). A key property of the randomized Fair BOC is that it is nearly deterministic, being randomized at most on a single point in the domain and deterministic elsewhere. Thus, in a sense, we have the best of both worlds, preserving the benefits of randomization, while using very little of it.
2

---

Optimal Fair Learning Robust to Adversarial Distribution Shift
We present the problem formulation in Section 2. More detailed comparison with most relevant previous work is given in Section 5.1, and we conclude in Section 5.2.
point (v, 2), and formally define it below.
Definition 2 (Score). The score S of point (z,, 2) is the probability that it has label 1, i.e., S(x,z) = Pr(Y
| (X = x, =)]]
2. Problem Formulation
The BOC basically accepts a point if its score is 2 2.2 and rejects it otherwise. Note that the BOC as described above is deterministic, and allowing for randomized classifiers will not provide any increase in accuracy. However, when faimess constraints are involved, the picture is more com- plicated, and it turns out that allowing for randomization actually can lead to a big jump in accuracy. To see how randomized Fair BOC's can improve the accuracy of their deterministic counterparts, let us look at an example from Agarwal & Deshpande (2022).
We are given a discrete distribution P over X' x 2 x V. where Z {A, represents the protected group mem- bership (A denotes the advantaged group, and D denotes the disadvantaged group)', X' represents all the other fea- tures, and 3 = {0, 1) represents the binary label set (we adopt the standard convention of associating the label 1 with success or acceptance). A randomized classifica- tion rule ʃ is a function ʃ : X' x 2 - [0, 1], where (a),2) denotes the probability of feature vector or in- stance (z, z) E X x Z being mapped to A determin- istic classifier is defined similarly, however the output of (xx, is restricted to {0, 1}. We consider the standard 0-1 loss function f whose expected value is given by L(S.P) = ([6)1(()] = Pr[J(X,2) A Y]. where the probability is over (X, 2, Y) ~ Pi. As is standard, we define accuracy as Acc(f, P) = P)
Example 1 (Accuracy jump in Randomized Fair BOC's), Consider the following distribution Pp over X' x 2 x V where X = {2) (P,S(1, 2) = (p,4) denotes that P(x, = p. and S(x, 2) = q).
P,S(I1, A) = (0.5,0.75)
P, P,S(I,, D) = (0.25, 0.5) P,S(22, D) = (0.25, 0)
P,S A) = (0, 0)
In a fairness-aware learning problem, we want find accurate classifier on a given distribution that also satisfies some fairness constraints. Our work considers 3 of the most popular notions of fairness (Demographic Parity, Equal Opportunity, Predictive Equality). We present our proofs for Demographic Parity in the main body, and defer the proofs of the other 2 notions to Appendix 4. We state the Demographic Parity definition below (Dwork et al., 2012).
There are only deterministic classifiers satisfying DP, ei- ther the constant 1 classifier f1. or the constant 0 classi- fier So. with L(Ji) = L(So) = 1.- On the other hand, consider the following randomized classifier f. where A)) = 2. f(1,, D) 1, (12, f D) = O. It is easy to see that ʃ satisfies DP, and L(J) = 3. hence improving over the accuracy of the deterministic far BOC's fo and ft.
Definition 1 (Demographic Parity). Denote the selection rate for group z by (f, P) = Px[ Z) = 1| z = 2). f satisfies Demographic Parity" if the selection rates are equal across both groups, i.e., r (f, P)- = (J P). We quantify the unfairness of f as the difference in selection rates across groups i.e., Unf PP
Given a distribution P, Agarwal & Deshpande (2022) char- acterize the DP-Fair BOC (the optimal classifier subject to DP constraints) on given distribution, which we now describe. We first present some of their terminology.
Definition 3 (Cell). Consider a randomized partition of the feature space X' x Z into multiple disjoint components. We call these components cells, and denote a cell by C.
|ra(f. P) - (ff,
2.1. Fair Bayes Optimal Classifier
One can also define the score of cell, in the same way as we had defind the score of point. We have already seen the BOC that thresholds based on scores. Randomized classifiers give us the ability to threshold by probability mass, instead of just thresholding by scores. To explain this better, we introduce the notion of group group-wise sorted cells. Definition 4 (Group-wise Sorted Cells). Define C2 U Cs where the component cells of CA and Cp are øE arranged in descending order of scores S. If two more cells from the same group have the same score, any ordering within them is acceptable.
Given a distribution P, the optimal (accuracy-maximiza classifier f (the BOC) is given by (a(x,,) = Ty (Pr(Y 1 ||X = xr, Z = z)), where (3) is the threshold function that outputs 1 if B 2 7, and 0 otherwise. We call the term 3 in the expression above the score or success probability of
OOr results also hold when there are multiple groups, but for ease of exposition, we restrict our analysis to the case of 2 groups Using the same proof techniques, our results also hold for the more general loss function fa. known in literature as cost-sensing sensitive risk (Menon& & Williamson, 2018b), that assigns a weight a to False Positive errors, and a weight (1 a)) to False Negative errors. However, for simplicity, we restrict our analysis here fo-1. "Henceforth, all prohabilities will be over (X, ZY ~ P, unless explicitly stated.
NNote that specifying distribution over X x Z x 3 is equiva- lent to specifying distribution over X' Z along with the scores for every instance (zz, 2) E X x Z.
*Classifiers satisfying DP will be often he referred to as DP-fair.
3

---

Optimal Fair Learning Robust to Adversarial Distribution Shift
By C2()), denote the topmost cells of C2 comprising of t fraction of the total probability mass of C.. Note that this may involve splitting a cell into 2 parts randomly. For example, in Example 1, CA(()) would involve splitting CA,,A into two equal parts randomly. However, in the deterministic setting, only (0) and (1) are defined, and not C2())) By Tr, we denote the mass threshold classifier that accepts exactly (t) for E 2. In Example I, the randomized classifier I' is the mass-threshold classifier 74.
3. Robustness to Adversarial Distribution Shift
We study the robustness of the DP-Fair BOC to adversarial distribution shift. We show that given 2 similar distributions P, P' (similarity measured by TV distance), the accuracy of the DP-Fair BOC on the respective distributions is similar (satisfies local Lipschitzness). Note that DP-Fair BOC in the deterministic case does not exhibit such a robustness property, as we demonstrate in the following example.
Definition 5 (Score Boundaries), Consider the component cells of groupwise sorted CA and Then, the score bound- aries denote the set I = IA U UDD where I, consists of all the boundary points between component cells in C..
3.1. Non- Non-Robustness of the Deterministic Fair BOC
Claim 1 NNon-Robustness of Deterministic Fair BOC's). Given e. > O, there exist P, P'' with (P, P') S c, such that the deterministic DP-Fair BOC's f. on P,P', re- spectively, satisfy |Ace[J, - Acc( ( P') 2 211).
Definition (Merged Cells), Consider any ry E I in sorted order, and define a merged cell C, as C, = where A(f) denotes the instances accepted by f. and ri- denotes the element in I preceding r;.
Proof. Consider the following distribution P, with X' [2)
Characterization Given distribution P over X x 2 x D, the DP-Fair BOC fp is given by the mass-threshold classifier Tyr, where r' = ri E I is the unique i such that S(C,) 2 0.5, and S(C,-) < 0.5, where Ti+ denotes the element in I after rú. Note that the DP-Fair BOC needs to use randomization on at most one cell in the whole domain, since the candidate r' values lie in I. Hence, to evaluate the Fair BOC, instead of considering the hypothesis class of all randomized classifiers, it is sufficient to consider the hypothesis class of classifiers that are randomized on at most one element in the domain.
P,S(f A) = (0.25. 1)
P. S(n D) = (0.25, 1) P, P,S(22, D) = (0.25, 0)
P,S(22, A) = (0.25,0) 0)
Consider the (deterministic) classifier f. with f A) [(, D) = 1, [112, A)= [s2,, D) 0. It is easy to see that f satisfies DP, and Acc(f) = 1, implying that f is the DP-Fair BOC in both the deterministic and randomized set- tings. Consider the neighboring distribution P' as follows, for small c.
P', S",S(z A) = (0.25, 1) P', D) = (0.25 + c, 1) 8',5(12, A) (0.25,0) 8 D) (0.25 c,
There are only deterministic classifiers satisfying DP, ei- ther the constant 1 classifier f1, or the constant 0 classifier fo. with C(fi) = 1 + t, and (((o)) = 1 e, implying that fi is the DP-Fair BOC in the deterministic setting. Hence, the difference in accuracy of the deterministic DP-Fair BOC on arbitrarily close P, P' is almost 0.5, demonstrating the non-robustness of deterministic classifiers to distribution shift.
(1.11)
(0,000)
3.2. Robustness of the Randomized Fair BOC
Now we state our main result.
Theorem 1 (Robustness of DP-Fair BOC). Given distribu- tions P, P' with TV, = we have
Figure 1. If the feature space X Z has cardinality n, then the hypothesis class of all randomized classifiers H is the hypercube [0, 1j".. Similarly, the hypothesis class all deterministic classi- fiers is {0, 11". A fairness criterion is a linear constraint (this may not true of all fairnsss criteria, but is true the well-known ones that we study in this paper). which can be represented by hyperplane J. Also, accuracy A is a linear objective, implying that the Fair BOC is the point in H n F maximizing A. We illustrate this 3-dimensions here.
|Aco(FPP (PP P) Acc(fpr P')
(1+ max (P(A), P' (A)) max (P(D), P'())) min( P(A)) min (Pn)) P'(D))
Remark. Note that the Lipschitz constant will blow up if the masses of either group becomes very small. Similar terms in the denominator will naturally feature in all our bounds. As such, robustness is not satisfied at such extremal points.
4

---

Optimal Fair Learning Robust to Adversarial Distribution Shift
We first prove Lemmas 1 and 2, and Claim 2 that will help us prove Theorem 1. Lemma 1 shows that one can decom- pose a transition from distribution P to distribution P' with distance e into a sequence of elementary transitions from P.-1 to Pa with distance 6, such that e = Σ 6 and for every i, the only difference between P:-1 and P; is that mass is transferred from exactly one element of the domain to another.
m < n distributions P = Po: Pi...... .m. P' satisfying the decomposability and monotonicity properties. Again, appending the elementary transition P + P to the above sequence yields the desired sequence for P and P' with the decomposability and monotonicity properties.
Claim 2 roughly states that given 2 similar distributions P. the accuracy and DP-unfairness of any fixed hypothe- sis is similar on both P, P Such a property is useful when we want a guarantee that if we train a classifier on the cor- rupted distribution P', the performance of the classifier on the actual distribution P will be similar to that on P'.
Lemma 1 (Decomposition into Elementary Transitions). Given distributions P. P' with TV(P, P') = c, there exist distributions Pu, Pl...., ; Pn (for some n, with P Pu. P' = Pn), such that the following two conditions hold:
Claim 2 (Accuracy, DP Shift for Fixed Hypothesis). Given distributions P, P', such that TV (P,P') S any hypothe- sis f satisfies the following two properties:
1. Decomposability: (V P:) - E -==9= and in the transition P:-1- - Pi. E mass moves from some instance a, to some by (a,, b, E X x 2, all other elements remain constant).
1. | P) Acc(J,P') Se
2. Monotonicity: P(A) S PAA),, then for every 1 1 < n, (P(AA < (A) and P.(D) 2 (P+)(D); otherwise, (A(AA) 2 (A) and (D) < (D)1(D).
2. [Unfor(f: (f Unfor S') < (mlu(P(A)))'(A) mil(P(D))PP(D))
Proof of Claim 2. We first establish the desired statements for the special case where the transition from P to P' is elementary in that the only difference between the two dis- tributions is that there are two elements a and b that have e more mass and e less mass, respectively, in P as compared to P' (all other elements have the same mass in the two dis- tributions). At the end, we invoke Lemma 1 and transitivity to establish the general claim.
Proof of Lemma We will prove the desired claim for n equal to number of elements q for which P(g) * P(g'). Our proof is by induction on For the base case, we have = 0, in which case P = P' and the claim trivially holds. For the induction step, let a be an element such that P(a) * Pa).. Suppose P(a)= > P'(a) and a is in group A: the arguments for the other scenarios are analogous. We consider two cases. The first case is when there exists b E A such that P(b)- P'(b). We define P as the same as P except that
Accuracy: Divide the domain into 4 parts based on whether a point falls in categories TP, FP, TN, or FN ac- cording to f. Denote the probability mass of elements in category E under ʃ by P(E). We know that Acc(J, P) = P(TP TN). Doing a simple case by case analysis, we observe that in the worst case, a belongs to TP U TN, and b belongs to FP U FN. This transition leads to loss in accuracy of e, i.e., Acc(J, P') Ace(J, P) e. We note that it is enough to consider a loss in accuracy, since we can reverse the roles of the distributions and use the same argument for gain as that for loss.
P(a) = P(a) - min - P'(1), - -(()} Pbb) = P(b)= + min (P()) - P()
-
Note that either p(a) = P'(a) or P(b)= = =P'(b), which implics that the number of elements for which p and p differ is less than n. Furthermore, P(A)= = P(A) and P(D)= = P(D). By induction, there exist sequence of m distributions P = Po, Pi,..., P... = P' satisfying the decomposability and monotonicity properties. Append- ing the elementary transition P + P to the above sequence yields the desired sequence for P and P' with the decom- posability and monotonicity properties.
Demographic Parity:
First we notice the following
Unnfne(/ - Unfn
[IIA(f,P) - rD(sP)) (I' - -D,
The second case is when there does not exist any b E A such that P(b)= < P' P((b. So, we have P(A) ('A). Furthermore, there exists We define P in the same way as for the first case. Again, we have that either P(a)= (a) or P(b)= = Pb(6), which implies that the number of elements for which P and P' differ is less than n. Furthermore, P(A) > ((A) and P(D) < P(D). By induction, there exist sequence of
I (TA(F)P) - -rD(f.P) - (ra(F, -app'-nmp" (D. P'))
(Triangle inequality)
D such that P(b) < Pbb)..
-(tA(f:P)-rA(.P)))) - -r.ff + (In(f. - < (ra(s,)) P') +
(f.
(1)
The above argument breaks up the change in unfairness into two terms: (i) Ara & |r)(f,P) - vA(FP'). which the
5

---

Optimal Fair Learning Robust to Adversarial Distribution Shift
difference in selection rates of I for P, and P' A and (ii) ArD _ ItD(S;P) P) rD(f, P')], which is the difference in selection rates of f for P and P' on D.
Plugging Equations 2 and into Equation 1, we get that
|Unfos([; UUnDD(J.P')
1
1 min(PP(),
We proceed to bound ARA. and an identical argument can be used to bound Arp- In our argument, we divide the domain into parts based on the group membership and la- beling according to f. Let the probability mass of elements in group 2 with label y under classifier f be denoted by P(.. fy). If a, b lie in the same group 2 then P(A) remains unchanged, and it is easy to see that the maximum value of A A is P(Aj. when P'(A, = fi) = In case E A, and b E D, then ('(A)- P(A) e. We know that (A'(A) (A,, + P'(A, fo). Either lies completely in (A, fi), completely in (A, fo). or in both (if we are ran- domizing over the cell containing a). We first consider the first case, where P' (1) = fi) -
(nin(P(A),P'AA))
From elementary to arbitrary: Consider a general tran- sition of distance from P to P., We invoke Lemma to ob- tain intermediate distributions {P,} with (P: P.) = e satisfying the decomposability and monotonocity proper- ties. We apply the above proof for each elementary transi- tion P:-1 - P: of mass 6G- For accuracy, we derive
[Acc(f. Acc(f, P')| - Σ
|Acc(f P(-1)) - Ace(f.
Σ c2
S
(ra()P) P) - rr((P = P(A, P(A,fi) -
=
P(A) P(A)
P(A)E-P(AL) - -ijE
For Demographic Parity, we derive
(P(A) c)
Unnfp
(ffior(f.75) (f. P) Unf (f)P') 5
Σ (f, - Unfpp (fP.))) S
P(A)
<6 min(P(A), P'(A))
Ea a 1
(D),
We now consider the second case, where Jo), P(A, E.
Σ G (min min(P(D),
P(A,Si) P(),Si)
(F((f,)) - -IA(FP')))
P(A) P(A)=
min (min(P()),PPAA) + (in))
P(A,
(PA)(((A)) c))
where the second inequality follows from monotonocity and the last equation follows from decomposability. This completes the proof of the claim.
Se
- P(A)
1
Sc (nin(P(A), (()))
We also use Lemma 2 (proof in Appendix A) for our main result.
easy to see that in the third case, where a lies in both (A, fi) and (A, fo), Ara is bounded by the max value of Ara of cases 1 and 2.
Lemma 2. Given any P.J, and P', such that TV(P, P') = c, if f'(g) differs from f(g) by Af(g) (and is identical elsewhere), then
Here we argued for when A loses mass. Using symmetry, we can similarly argue the case where A gains mass, i.e., a E D. and b E A, leading to (AAA) = P(A) + e. Hence, we conclude that
[eeeff P) Ace([f' P'I S -))
Now we move on the proof of our main theorem.
(A(. - (
S
(2)
Proof of Theorem Armed with these lemmas, we first es- tablish the claim of the theorem for the special case where the transition from P to P' is elementary in that the only difference between the two distributions is that there are two elements a and b that have e more mass and e less mass, respectively, in P as compared to P' (all other elements have the same mass in the two distributions). At the end,
(min(P(A)),P'(A) P'(A))
Also, here we argued for group A, and an identical argument for D shows that
Ir P) (D(ff Se min(P P'())
(3)
6

---

Optimal Fair Learning Robust to Adversarial Distribution Shift
we invoke Lemma and transitivity to establish the general theorem statement.
we see that after the transition, the boundary of p in- tersecting q is ÖUnfDP away from the boundary in group A. To modify fpr + fp we therefore need to move to move the boundary at q by òUnfDe so that the bound- aries in both groups align and DP is satisfied (the clas- sifier remains the same apart from its action on q). The change in function value on element q, which we denote by A is bounded by JUnfpe P(D) after scaling (since P())
Consider the transfer of mass from a to b in continuous manner. During this process, either the cell corresponding to element a will monotonically increase in score or mono- tonically decrease in score". The same holds for the cell corresponding to element b. The scores of all other cells will remain the same. In the following argument, we assume that the score of the cell of decreases monotonically and that of b increases monotonically, All of the arguments are analogous for the remaining three cases.
PDD)Unnfpp = ا사ʃ(ه) P(4)). At the end of the mass transfer, by Lemma 2. the change in accuracy of the optimal fair classifier is given by
We break down the mass transfer into smaller increments. At any point, let P be the distribution at the start of this increment (so, p= P initially) and P be the distribution at the end of this increment (so, P P' finally). For an incremental mass transfer, analyze how the DP BOC changes from f to fpP. Since the mass transfer is from
Acc DD P) - Acc poP P\) P.
- (P())(2(() - 1) 1)} +
min(P(A),PP((A) + P(D)) - -1] S dc (1+ max (P(D),P'(D)
S de (1+ P(D) (25(()) -
min(((D),PP(D)
element a to b, it follows that both P((A) and (a(AA) lie between P(A) and ('(A) while both P(D) and P'( lie between PDD) and (D). We consider the largest mass transfer de until one of the two following events occur.
min(P(A),PPP()) + max (P(D),
min min(P(D))
where the last inequality follows from the facts that
((S(g)) - -1) S 1, P(A) and P'(A) both lie between P(A)
1. Equal-score event: The cell of a has the same score the adjacent cell lower in the sorted order or the cell of b has the same score as the adjacent cell higher in the sorted order.
and (A) and P(D)) and P'(D) both lie between P(D) and (D).
In Appendix A.4, we derive a better upper bound on (2S(()) - 1) and derive the following:
2. Threshold event: The score of a merged cell containing or b becomes exactly 0.5.
Acc(Spr PDP PD) - Acc(Spp SDP PT) =
5c (1+ max (P(A), P'(A)
max (P(A), P'
min (P(D), P'(D))
Bounding the accuracy change for de: Note that by the choice of dc, during the transfer dc, all the cells remain in the same order both groups; furthermore, all masses and scores of all cells other than the ones containing or b remain the same during the transfer. By part 2 of Claim 2,
Putting the two upper bounds together yields the following:
ACc(SPP. P)) - -Ace(ppp PT) (
dc (1+ max (P(A), P'())) max (P(D), min(P((A),P((A)) + min min(P (P(D),
pUnfpe = ( (DDP P)- - Unfor ( |P1
S 86
1 (Pin( (A)) +
1
Handling the equal-score and threshold events: We now describe how to handle the two events.
min(P P((D)) 1
1
< _E
minn(P(A), (A)) (ii(P(D),P((D))
Equal-score event: If the cell of has the same score as the adjacent cell lower in the sorted order, then we swap the two cells that the cell of is lower in the order. Similarly, if the cell of b has the same score as the adjacent cell higher in the order, then we swap the two cells so that the cell of b is higher in the order. We update the classifier f and note that this change has no impact on the accuracy of f.
Since Unfie ppp P) 0. know that jUnfpp Unfie(SPP (
P.). - the cell 9 that is split in the middle by the threshold cor- responding to rDP (for now, assume & E D). Since nei- ther the equal-score event nor the 0,5-score event occur,
Consider
2. Threshold event:
The score of a merged cell containing a or b becomes exactly 0.5. We include the merged cell in the classifier f. again without changing accuracy.
'In case the cell corresponding to has score of 0 or 1, it's score will remain unchanged, and this case is trivially covered by our argument.
7

---

Optimal Fair Learning Robust to Adversarial Distribution Shift
Thus, in sense, between any two occurrences of these events, the change in accuracy is bounded by amount proportional to the mass transfer; when we reach these occurrences, the mass transfer is paused, the BOC changes without any change in accuracy. Furthermore, at every occurrence of the event, one of these three events happen: the cell containing a moves down in the order, the cell containing& moves up in the order, or an additional merged cell is placed above the threshold. Since the number of times these events can occur is upper bounded by the number of cells in the two groups, this process is finite. Therefore, adding over all the de mass transfers, we obtain the desired upper bound on the change in accuracy between the BOC's for P and P'.
4. Equal Opportunity and Predictive Equality
Earlier, we presented results for Demographic Parity. Our results also extend to the popular fairness notions of Equal Opportunity and Predictive Equality (Hardt et al., 2016; Barocas et al., 2019). We state the results here, and defer the proofs to Appendix B. We first define the fairness notions.
Definition (Equal TPR, or Equal Opportunity). Denote the true positive rate of on group by
TP, Pr[[(X, = 1 = 1, = 2].
f satisfies Equal Opportunity if the true positive rates are equal for both groups, i.e. TPR TPRo(f, P). We quantify the unfairness of ʃ as the difference in true positive rates across groups i.c.,
6 (1+ max (P(A),P(AA) min(P((),PP(A)) + max (P(D).P'(D) (P(())))PP(PD)
Unfgo P) (TPRR P) (PRD(f.P)
From elementary to arbitrary: Consider a general tran- sition of distance from P to P'. We invoke Lemma 1 to ob- tain intermediate distributions {P,} with (V(::-1.P.) = e, satisfying the decomposability and monotonocity proper- ties. We apply the above proof for each clementary transi- tion P + P; of mass G. For accuracy, we derive
Definition 8 (Equal FPR, or Predictive Equality). Denote the false positive rate of of f on group 2 by
(T Pr 2) =) Y Y
7= =].
f satisfies Predictive Equality if the false positive rates are equal for both groups i.c. (f. = F P). We quantify the unfairness of f as the difference in false positive rates across groups i.e.,
|Ac(FF (Pp PP) Acc( DD, P') s
Σ Acce (DP : Pi-1) Aco PPP P.) S Σ GX
(A), + (D))
Unfye(f. P) = FF, P) (f.
min(P:-.(A)) (A))
(.())
Σ E/ 1+ max(P((A), P'(A)) + max(P(D), (D)) Remark. Classifiers satisfying these notions of fairness will miin, (()))
min(P(D),PP'(D)
be referred to as EO-fair, and PE-fair respectively. The results for PE follow using the same proof techniques as that of EO (since we can just reverse the roles of the labels 0 and in EO to get results for PE). We state the analogous results for PE in Appendix B.3. In addition, previous work has also considered equal False Negative rate (FNR) and equal True Negative rate (TNR) as notions of fairness. Obtaining equal TPR is equivalent obtaining equal FNR, and obtaining equal TNR is equivalent to obtaining equal FPR, and hence results for these notions of faimess also follow.
=e -c(1+ max (P(), max(P(D),PP'(D)) min (P(A),
min(P(D), (P())))P(())
where the third inequality follows from monotonocity and the last equation follows from decomposability. This com- pletes the proof of the theorem.
We now state the following corollary, which follows from Claim 2 and Theorem 1. It roughly states that given 2 closeby distributions P, PP,, the accuracy of the respective DP-Fair BOC's is similar on P. Such a property is useful when we want a guarantee that intuitively says that if we train on the corrupted distribution P', we get a similar out- come what we would have gotten had trained on the true distribution P.
We now state the results for EO.
Claim 3 (EO Shift for a Fixed Hypothesis). Given distribu- tions P,P' P', with (V(P, S and any hypothesis f, it holds that
Unfeo Unfeo (f. P') cC(P,P'),
Corollary 1. Given distributions P, P' with TV we have
where 150 3500 are the EO-Fair BOC's on P, p' respec- lively, and K(P, P')=
[Ace pDP P) - AP-ccc(fP,,p) P)|
max (P(A), P'(A))
max (P(D),P'(D))
1 1))(P((.)))P(AA.1)) min(P(D,1), P' ((D,))
1
6 12 (PnAP P'AA) minn(PDD),P'ID) P')))
8

---

Optimal Fair Learning Robust to Adversarial Distribution Shift
Theorem 2 (Robustness of EO-Fair BOC), Given distribu- tions P, P', such that (P; P') = 6, we have that
case of perfect fairness). We prove a stronger Lipschitz- ness guarantee, where the excess risk goes to 0 as distance between the distributions becomes arbitrarily small. Further- more, they do not provide description of the Randomized Fair BOC in the case of discrete domains, whereas we pro- vide a complete characterization of the same, show that it is minimally random. In addition, our algorithm (to output the Fair BOC on a distribution) is very simple and efficient, run- ning in O( log( (())) time, while their algorithm solves large linear program with ((2)) constraints in (((z)) variables, requiring much higher complexity.
|Ace[ P) Acc(J P')|s
( P' (U))K(P)P))
where fp. spp tively, and K(P,P) P') is as defined in Claim
p50 are the EO-Fair BOC's on P,P' respec-
Corollary 2. Given distributions
P, P,P', such that
(V P") 6, we have that
|Ace(JP; P) - Acc( P)l S
2e + (PX() (ILL),P((L)))) P'())K(PP (P)),
Chen et al. (2024) contains a similar sensitivity analysis as Xian & Zhao (2024), for the same setting except binary group and binary class. Unlike us, they do not deal with ad- versarial distributions shifts, but only label distribution shifts and/or group distribution shifts. In addition, our setups fundamentally different, theirs being the continuous case, and ours being the discrete case. Moreover, their sensitivity analysis (Theorem 2) is looser, and has an extra additive error term, unlike ours and that of Xian & Zhao (2024). Besides, they do not deal with the case of perfect fairness, and require ō > O. Chen et al. (2022) also consider fair- ness under distribution shift. Their result is fundamentally different, and essentially shows that the fairness of fixed hypothesis class on two similar distributions is similar. This is essentially what we show in Claims 2/3/7, however, they only deal with label and covariate shifts, while we tackle the more general case of adversarial distribution shifts.
where fp. sEO J.p are the EO-Fair BOC's on P, P respec- tively, and K(P,P") is as defined in Claim
5. Discussion
5.1. Comparison with Related Work
We now present detailed comparison with relevant previous work. In Blum et al. (2024), they aim to avoid the non- robustness phenomena highlighted in Konstantinov & Lam- pert (2022), as follows. Given any deterministic hypothesis class H. and distributions P, D' with (V,P, P') = e, they construct randomized closure of H called PQ(H). Denote by J.J' l' the optimal classifiers (subject to DP constraints) on P, P' restricted to H. (H) respectively. They show that this satisfies a one-directional Lipschitzness constraint, i.e. A'c( P') > Acc(f, P) (e)) They also show analogous results for EO and PE. Our setup has some key differences. We do not consider any arbitrary H. but the BOC setting which includes all deterministic classifiers (and the I-skeleton of their convex closure). More crucially, our robustness guarantee is stronger, their Lipschitzness guar- antee is only one-directional. In addition, in most cases, their output hypothesis incorporates a lot of randomness, outputting& a randomized decision on all elements in the do- main, whereas our output hypothesis is randomized on at most one element.
5.2. Future Work
Some directions for further work include extending our re- sults for binary classification to multi-class classification, and regression. Another direction could be to look at re- laxed or approximate versions of the faimess notions we considered. One could even look at other popular notions of fairness, or satisfying multiple fairness notions simultane- ously. It would also be valuable to experimentally validate our theoretical claims. In addition, note that our results hold for adversarial noise, but might be possible to strengthen the bounds if the noise came from a particular distribution.
In the concurrent work of Xian & Zhao (2024), the sensi- tivity analysis (Theorem 3.1) bounds the drop in accuracy of the optimal fair classifier under a shift in distribution, for the multiclass and multigroup setting, focusing on continu- ous domains. However, their sensitivity analysis only holds for either a shift in the label distribution, or in the group membership distribution, whereas our robustness guaran- tee works for adversarial distribution shifts. Adversarial or arbitrary distribution shifts are strictly more general than la- bel/covariate shifts, and moreover, they cannot be simulated by any combination of label/covariate shifts. In addition, in their sensitivity analysis (Theorem 3.1, 2nd result), the change in accuracy due to group distribution shift, is a con- stant independent of the amount of distribution shift (in the
Impact Statement
This paper presents work towards advancing theoretical un- derstanding of fair machine learning under adversarial or malicious distribution shift. Our results provide normative principles in the debate on pros and cons of randomized algorithmic decisions with societal consequences, Our work underlines the need to compare and contrast different ways to rectify biases in algorithmic decision-making with soci- etal consequences.
9

---

Optimal Fair Learning Robust to Adversarial Distribution Shift
References
Chzhen, E., Denis, C., Hebiri, M., Oneto, L.., and Pontil, M. Leveraging labeled and unlabeled data for consistent fair binary classification. Advances in Neural Information Processing Systems, 32, 2019.
Agarwal, A., Beygelzimer, A., Dudík, M., Langford, J., and Wallach, H. A reductions approach to fair classification. In International Conference on Machine Learning, pp. 60-69. PMLR, 2018.
Cooper, A. F., Lee, K., Choksi, M. Z.., Barocas, S., De Sa, C., Grimmelmann, J., Kleinberg, J., Sen. S., and Zhang, B. Arbitrariness and social prediction: the confound- ing role of variance in fair classification. In Proceed- ings of the Thirty-Eight AAAI Conference on Artifi- cial Intelligence and Thirty-Sixth Conference on Inno- vative Applications of Artificial Intelligence and Four- teenth Symposium on Educational Advances in Artificial Intelligence, AAAI'2MIAAIT2WAAA'2 AAAI Press, 2024. ISBN 978-1-57735-88774 doi: 10. 10.9 v38120.30203, URL htt.::tttp////om http:p::///o..ogg////////o/ 1609/ aaai. 1238120.30200
Agarwal, S. and Deshpande, A. On the power of ran- domization in fair classification and representation. In Proceedings of the 2022 ACM Conference on Fair- ness, Accouniability, and Transparency. FAccT '22, pp. 1542-1551, New York, NY. USA, 2022. Associa- tion for Computing Machinery. ISBN 978145039335 doi: 10. 1 14..53333311 URL https: org/10
3533209.
Akpinar, N.-J., Nagireddy, M., Stapleton, L., Cheng, H.-
F., Zhu, H., Wu, S., and Heidari, H. sandbox tool to bias(stress)-test fairness algorithms, 2022. URL https:
Creel, K. and Hellman, D. Arbitrariness, fairness, and opportunity in algorith- mic decision making systems. In Proceedings of the 2021 ACM Conference Fairness, Accountabil- ity. and Transparency, FAccT '21, pp. 816, New York, NY, USA, 2021. Association for Computing Machinery. ISBN 9781450383097. 3442188..445942. URL 1145/3442182 3445942.
The algorithmic leviathan:
//arxiv. org/ 2204. 10233.
Balcan, M.-F. and Haghtalab, N. Noise in classification.
In Beyond the Worst-Case Analysis of Algorithms, 2020. URL https: / arxiv. org/ abs/ 2010.0000000000000000002200022 05080.
Barocas, S., Hardt, M., and Narayanan, A. Fairness and Machine Learning. fairmlbook.org, 2019. http:// www. fai fairmboook.org
doi: 10.1145/
Blum, A., Okoroafor, P., Saha, A., and Stangl, K. M. On the vulnerability of fairness constrained learning to malicious noise. In Dasgupta, S., Mandt, S., and Li. Y. (eds.), Proceedings of The 27th Interna- tional Conference on Artificial Intelligence and Statis- tics, volume 238 of Proceedings of Machine Learn- ing Research, pp. 4104 PMLR, 02-04 May 2024. URL https: http:p:://rrcceeee /pwpceeedogggs..c//eeppppp mlr. ppres// v238 /bl/bmmmmmm/ 4a. html.
Davani, A. M., Atari, M., Kennedy, B., and Dehghani, M. Hate speech classifiers learn normative social stereotypes. Transactions of the Association for Computational Lin- guistics, 11:300-319 -19 03 2023. ISSN 2307-387X. doi: (tto:222acllaa005555000 URL htwph::t////e/t //o:://///o.eee/ /to.s/////o.or//1.... org/10. 1162/taci 1_00a5050__00000___11
Davidson, T. R. Hate speech detection and bias in super- vised text classification. In The Oxford Handbook of the Sociology of Machine Learning. Oxford University Press, 2023, ISBN 9780197653609, doi: 10.1093/oxfordhb/ 0780197653699.013.16 URL https: hwt.dddiiooooooo 10.
Celis, L. E., Huang, L., Keswani, V., and Vishnoi, N. K. Classification with faimess constraints: A meta-algorithm with provable guarantees, 2020.
16.
Celis, L. E., Huang. L., Keswani, V., and Vishnoi, N. K. Fair classification with noisy protected attributes: A frame- work with provable guarantees. In International Con- ference on Machine Learning, pp. 1361. PMLR, 2021.
Dwork, C., Hardt, M., Pitassi, T., Reingold, O., and Zemel, R. Fairness through awareness. In Proceedings of the 3rd Inmovations in Theoretical Computer Science (ITCS) Conference, pp. 214-226. Association for Computing Ma- chinery, 2012. URL https: : /ttp///oiio/////// wow.i.oorg/1000 1145/ 2090236. 2090255.
Chen, W., Klochkov, Y., and Liu, Y. Post-hoc bias scoring is optimal for fair classification, 2024. URL https: // Tarxiiv.eo www.i.org///.ooooo....oo. abs/ 2231 0 05725.
Ghosh, A., Kvitca, P., and Wilson, C. When fair clas- sification meets noisy protected attributes. In Pro- ceedings of the 2023 AAAI/ACM Conference on AI, Ethics, and Society, AIES '23, pp- 679-690, New York, NY, USA, 2023. Association for Computing Machinery. ISBN 9798400702310. doi: 10.1145/ 3600211.3604707. URL https: /ttp::///ooooo//.//// 1145/3600211 36047777.
Chen, Y., Raab, R., Wang, J., and Liu, Y. Faimess trans- ferability subject to bounded distribution shift. In Pro- ceedings of the 36th International Conference on Neu- ral Information Processing Systems, NIPS '22, Red Hook, NY, USA, 2022. Curran Associates Inc. ISBN 9781713 778.783871088.
10

---

Optimal Fair Learning Robust to Adversarial Distribution Shift
Hardt, M., Price, E., Price, E., and Srebro, N. Equality of opportunity in supervised learning. In Advances in Neural Information Processing Systems, vol- ume 29, 2016. URL
23-24 Feb 2018b. URL https: https://procedding: mi mir.press/ver prtress/88//mmen// /menonl 8a html.
Rosenblatt, L. and Witter, R. T. Fairlyuncertain: A
comprehensive benchmark of uncertainty algorithmic fairness, 2024. URL https::/arxiss org/ /abs//////// 02005.
cc. /uarrppp..c/ppppr//2/////// 9226225113335eefccc1112222211173 Paper. pdf.
Sharma, M., Deshpande, A., and Shah, R. R. On comparing fair classifiers under data bias, 2023, URL https: arxiv org/ abs 200.2332222222 05906.
Harris, C., Halevy, M., Howard, A., Bruckman, A., and Yang, D. Exploring the role of grammar and word choice in bias toward african american english (aae) in hate speech classification. In Proceedings of the 2022 ACM Conference Fairness, Account- ability, and Transparency, F2ccT'22, pp. 789-798, New York, NY, USA, 2022. Association for Comput- ing Machinery. ISBN 978 9781450393522. doi: 10.1
Xian, R. and Zhao, H. A unified post-processing framework for group fairness in classification, 2024. URL https:
/ //arxiv. org/ abs /bwp////.55. 2405. 04025.
Yang, Y.-.,, Rashtchian, C., Zhang, H., Salakhutdinov, R., and Chaudhuri, K. A closer look at accuracy vs. robust- ness. In Proceedings of the 34th International Confer- ence on Neural Information Processing Systems, NIPS '20, Red Hook, NY, USA, 2020. Curran Associates Inc. ISBN
3531146.3533144. URL https://doi.orq/// 1145/3531145 3533144.
Hartvigsen, T., Gabriel, S., Palangi, H., Sap, M., Ray, D., and Kamar, E. ToxiGen: large-scale machine- generated dataset for adversarial and implicit hate speech detection. In Muresan, S., Nakov, P., and Villavicen- cio, A. (eds.), Proceedings of the 60th Annual Meet- ing of the Association for Computational Linguistics (Volume I: Long Pupers), pp. 3309-3326, Dublin, Ire- land, May 2022. Association for Computational Linguis- tics. doi: 10. 10.18653/w122022.alllogng 234. URL ht hps: //aclanthology org/ acl paollloon..2444 234/.
Zeng, X., Dobriban, E., and Cheng, G. Fair bayes-optimal classifiers under predictive parity. Advances in Neural Information Processing Systems, 35:27692-27705,, 2022.
Kamiran, F. and Calders, T. Data preprocessing techniques for classification without discrimination. Knowledge and Information Systems, 33(1):1-33, 2012.
Kearns, M. and Li, M. Learning in the presence of malicious errors. In Proceedings of the Twentieth Annual ACM Symposium on Theory of Computing, pp. 267-280, 1988.
Konstantinov, N. and Lampert, C. H. On the impossi- bility of fairness-aware learning from corrupted data. In Schrouff, J., Dieng, A., Rateike, M., Kwegyir- Aggrey, K., and Farnadi, G. (eds.), Proceedings of The Algorithmic Fairness through the Lens of Causal- ity and Robustness, volume 171 of Proceedings of Ma- chine Learning Research, pp. 59-83. PMLR, 13 Dec 2022. URL htt.ttss:/prrreedding www.mmll.s.......... v wttl//oosstatnnnoo2222 html.
Menon, A. K. and Williamson, R. C. The cost of faimness in binary classification. In Conference on Fairness, account- ability and transparency, pp. 107-118. PMLR, 2018a
Menon, A. K. and Williammon, R. C. The cost of fairness in binary classification. In Friedler, S. A. and Wilson, C. (eds.), Proceedings of the 1st Conference on Fairness, Accountability and Transparency, volume 81 of Proceed- ings of Machine Learning Research, pp. 107-118. PMLR,

---

Optimal Fair Learning Robust to Adversarial Distribution Shift
A. Missing Results from Section 3
A.I. Non-Robustness of the Deterministic Fair BOC (approximate fairness)
We show through the example below that the non-robustness phenomenon highlighted in Claim also holds when we only require approximate fairness'. In particular, this can hold in the case where sensitive group populations are highly imbalanced, for example when the mass of group A is much larger than the mass of group D, i.e. P(A) > P(D). We set 5 0.25, and slightly modify the example in Claim where we skew the probability mass towards Group A (in Claim 1, the group masses are balanced).
Claim 4 NNnn-Rbuustnes of Deterministic Fair BOC (approximate fairness)). There exist distributions P.P' with TV(P,P) PP) 6, such that the deterministic DP-Fair BOC's I, on P, P',, respectively, satisfies |Aco(f. P)
2 (11).
Proof. Consider a distribution P. where P. = - -
=
= (0.4,0) -
P. (12,, D) (0.1, 0) Consider the (deterministic) classifier f. with f(11, A)=
= f(1) D) =1 f( A) f(2 D) = O. satisfies DP, and Ace(f) 1. Consider the neighboring distribution P" differing only on (α), D), (x2, D), as follows.
P. S(,(1 D) (0.1 + 0.05, 1) P', Szz, D) = (0.1 0.05, 0)
If we apply f on P", it does not satisfy approximate DP for any 5 < 0.25, even though TV(P, Pt) is small (0.05). There are only 2 deterministic classifiers satisfying approximate DP for any 5 < 0.25, either the constant 1 classifier fi, or the constant 0 classifier fo. with Ace fi) ) = 1/2 + 0.05, and Acc(fo) = 1/2 0.05. Hence, the difference in accuracy of the deterministic (approximate) DP-Fair BOC on closeby P, P' is almost 0.5, demonstrating non-robustness.
A.2. NP-Completeness of Deterministic Fair Bayes Optimal Classifiers
Claim 5 (NP-Completeness of Deterministic DP-Fair BOC). Given a distribution P, the problem of computing the deterministic DP-Fair BOC is NP-complete.
Proof. We formalize the deterministic DP-Fair BOC decision problem as follows: Given probability distribution P and a score function S over a domain X x Z and an accuracy determine whether there exists a deterministic fair classifier with accuracy at least a.
easy to see that the above problem is NP since one can guess the 0-1 classification for each item in the domain and check in polynomial time that the resulting classifier is fair and satisfies the accuracy bound by verifying two linear inequalities. We now show that the problem is NP-hard via a polynomial-tine -imm reduction from the NP-complete Partition problem, which state below.
Partition problem: Given a set S of n positive integers a1 Q2, O, summing to 2s, determine whether there exists a subset of S that sums to 8.
The reduction from Partition to the deterministic DP-Fair BOC problem as follows. Given an instance of Partition,
we create an instance I' of the deterministic fP-rair BOC problem. Instance I' has n items (#1, A) with mass 1/4 and score 1, item (12, A) with mass 1/4 and score 0, and then n items (y,, D) with mass a:/ (4s) and score 0.5 ask whether there is deterministic DP-Fair classifier with accuracy a 2 3/4. It is clear that there are most 3 kinds of deterministic DP-fair classifiers: (i) the all-O classifier that classifies all items as O, (ii) the all-1 classifier that classifies all items as 1, and (iii) if and only f I is yes-instance with S partitioned into S₁ and S₂ of equal sums, then the classifier that accepts exactly one of (I1, A) or (x22, A) and accepts all items in (yi, D) with ag E S1 and rejecting all items in (ys, D) with a; E Sz. The first two classifiers have accuracy 1/2 while the third, if exists, has accuracy 3/4 if (z1, A) is accepted and less than 3/4 otherwise. Thus, there exists a deterministic Fair BOC for instance I' with 3/4 accuracy if and only if I is yes-instance for the Partition problem. Clearly, the reduction is of time polynomial in the size of the deterministic DP-Fair BOC instance, thus establishing its NP-completeness.
Since determining the existence of a deterministic fa- classifier with accuracy at least 3/4 is NP-complete it follows immediately that finding a deterministic DP-Fair BOC is also NP-complete.
"W define 6-approximately fair classifier as follows, "If denotes selection rate, classifier f is 6-approximately DP-fair if |r(,, A) - rff D)1 < 5".
12

---

Optimal Fair Learning Robust to Adversarial Distribution Shift
A.3. Maximal Accuracy Gain for Randomized Classifiers
Consider the example in Claim and consider the following randomized classifier f', where
(z) -1,
4e, f' D) = 0.
It is easy to see that f' satisfies DP on P', and Aco(f))= -- -. Hence, the randomized DP-fair BOC improves over the accuracy of its deterministic counterpart by 0.5 2c, where c > 0 can be made arbitrarily small (so the gain in accuracy approaches 0.5). In the following claim, we argue that this example is tight, i.e., we cannot hope to achieve an improvement over 0.5.
Claim 6 (Bound in Accuracy Gain for Randomized classifiers), Given any distribution P, the difference in accuracy of the Randomized and Deterministic DP-Fair BOC's 's on P is strictly lesser than 0.5.
Proof. Note that the constant classifiers fo. fi always satisfy DP, and Acc(fo) = 1 Acc(fi). Hence, the minimum accuracy of the optimal DP-fair deterministic classifier is 0.5. The maximum accuracy of its randomized counterpart is bounded by hence bounding the difference in accuracy by 0.5. It suffices show that these 2 events cannot occur simultaneously. Note that if some classifier has perfect accuracy, then all cells in the domain have score of either 0 or 1. In particular, this also holds if the optimal DP-fair randomized classifier has accuracy 1. However, observe that if we randomize over any cell with score of 0(1,, we are accepting (rejecting) a part of it, leading to loss in accuracy. This implies that any classifier with accuracy has to be deterministic, concluding our proof.
A.4. Completion of the Robustness Analysis for Demographic Parity
In this section, we present the argument that was deferred in the proof of Theorem 1. This argument concerns a better upper bound on (2S(g) - 1| than the vacuous bound of 1, where is the element that is split by the threshold corresponding to the classifier f. Notice that since by assumption, splits q in the middle, we know that there is a portion of that is rejected. Hence, the weighted score a merged cell involving q (say C₂) has score below the threshold of 0.5. Let C2 contain some element from group A. We are able to bound the score of S(q) by the following chain of inequalities.
S(C,)) $ 0.5
( < 0.5 (P(D) (PD) P(A)) ( P(A))
P(())
25(g)- - - P(D)
(4)
Since ff splits q in the middle, there is also a portion of that is accepted. Hence, the weighted score of merged cell involving (say C,) has score above the threshold of 0.5. Let C2 contain some element / from group A. We are able to bound the score of Sgg) by the following chain of inequalities.
S(C,)) 0.5
(l))(())+(()22055)))))) +P(A))
S()P(0)200(P(D)-P(M)
28(g) - -12 P(A)
(5)
P(D)
Combining Equations and we get
(2S(g) 1/5 P(A)
(6)
P(D)
13

---

Optimal Fair Learning Robust to Adversarial Distribution Shift
Using Equation get that
Acc(Fpp
(DP P) - Acc((pp:: PP)
1 min(P(A), P'())) min(P(D), P'(D))
P(D) P(A)
S 6c
+ 8c
P(D)
6e
P(A)+ +
miin(P(A),
(An(P())PP(D))
max (P(A), PA()) max (P(A), P')))
S 8c 1+
miin))(), (in(P(D)PP'(D)
The last equation follows by monotonicity, This completes the missing argument in the proof of Theorem 1.
A.5. Proof of Lemma 2
Proof. The contribution to accuracy of an element q is given by
P(a)S())(()) -()) = P(1) -
If P changes by and f()) changes by Ag (and remains constant elsewhere), then split the process into two
parts: (i) f() changes by Ag( (and remains constant elsewhere) while p remains constant, and (ii) P changes by while remains constant. We consider each of the parts.
If P remains fixed, and f() changes by A4( to give (4), then change in accuracy on q (and also overall accuracy) is given by
( PP))) |P()) 1)AA(())
If P changes by e, and f' remains constant, then by Claim 2 the change in accuracy is bounded by Thus, the total change in accuracy is bounded as follows.
|Ace(S. P) Acc(S",P') < (P())25()) - 1)4f(2) +c.
B. Equal Opportunity and Predictive Equality (continued)
B.1. Fair Bayes Optimal Classifier
When discussing the DP-Fair BOC, we considered mass mass-thresher threshold classifiers Te, that select Cs (t), and reject C2 C, (t), for both 2 = A, and D. Ti applies the same threshold t to both groups A and D. In this section, we consider groupwise mass-threshold classifiers Teato that apply different thresholds lA and Ip to groups A and D respectively.
Denote the True Positive rate of classifier f restricted to a cell C by TP)(f(C)). Given r E (0, 1], there is a unique classifier Tea.,s such that TPR(Te..1D (Ca)) TPR(Tr... (CD)) r. Denote this classifier by fr- Given 0, Tex.to need not be unique as there could exist cells with score In that case, define fo be the unique groupwise mass-threshold classifier accepting exactly the cells with score 1. Denote the groupwise thresholds of by r and rD respectively, i.e., fr -TAA, .D.. We now introduce some terminology, before detailing the EO-Fair BOC as characterized in Agarwal & Deshpande (2022).
Definition 9 (TP-Boundaries). Recall the set of score-boundaries I. We then define the set of TP-boundaries ITp as
Ipp = {r | II, or D EZ,
Lrp essentially consists all the true positive rates r, such that, the corresponding groupwise threshold classifier fr T has a threshold a point the set of score boundaries I.
As with DP, we define the notion of merged cell, but notice that differs from the notion of merged cell in the case DP.
14

---

Optimal Fair Learning Robust to Adversarial Distribution Shift
Definition 10 (Merged cell (EO)), Consider ry E Lrp, and define merged cell C,, where
- C, = - A(fr.).
where ri- denotes the element in I preceding
Characterization Given distribution over X' Z x V, the EO-Fair BOC 120 given by the mass-threshold classifier is given by the group wise mass-threshole classifier fr', where r' E I is the unique i such that S(C,) 0.5, and ((C+)) < 0.5, where ri+ denotes the element in Trp after Vi.
B.2. Robustness to Adversarial Distribution Shift
We study the robustness of the EO-Fair BOC to adversarial distribution shift. We show that given two similar distributions P, P', the accuracy of the FO-Fair BOC on the respective distributions is similar (satisfies local Lipschitzness). Before proving the main result (Theorem 2), we prove Claim 3, which analyzes the change in unfairness, with respect to EO, of a fixed classifier due to a distribution shift. Such a property useful when we want a guarantee that if we train a classifier on the corrupted distribution P', the performance of the classifier on the actual distribution P will be similar to that on P'.
Proof of Claim As in the proof of Claim 2, follows from Lemma and transitivity that enough to prove the statement of the claim for elementary transitions. We consider a transition b of mass e. We first derive
[nnfgo P)- Unfeo (f. P')) = |PPR P) (PRD(f.P)) a P') - D (f. P'Ill
< (T,P) (1))( - (TPRA
- TPR P'))
(Triangle inequality)
((TPRA ( (TPRR((J)P)) - DP, S (P.) TFR P')] [TPRD(f, (f, -f
(8)
This breaks up the change in unfairness into two terms, which correspond to the difference in true positive rates of f for P and P' on A, D respectively (denoted by ATPR,, p Divide the domain into 8 parts based on the group membership and whether point falls in TP, FP, TN, or FN according to f. Denote the probability mass of elements in group in category E under f by P( P.E.). We know that P (AA) P(A, 1) + P(4, 0) (P(TP) A) + P(FN A)) (P(TN,) A) P(FPA)).
We proceed to bound ATPRA, and an identical argument can be used to bound ATPR,, n) If a, b lie in P(A, 1). it remains unchanged, and it is easy to see that the maximum value of ATPRA is P(A.T) when P P'(TPA) a) = P(TPA) + e. In case (A, 1), and b & (A, 1), then P' ('(A,)) PA,, We know that (' ('(P)A) P'(FN Either lies completely in TP A. completely in FNA, A, in both (if we are randomizing over the cell containing a). We first consider the first case, where P'(TPA) = A(TPA)
P(TPA) P(TPA) c
( P) TPR ( P')
1)A,1) P(A,1)-
P(TPA)P(A,1) - -P(TPA) (PPPADE-((TA)(AAA)) 1(A
P(A.1))((A)))-
P(A,1)c-P(TPAA) e)
P(FNA)
P(A, 1) (P(,)))
1
1(A,1) -
1
('(A, 1)
1
Se
[iinn(((A)) 1), 1'(A
15

---

Optimal Fair Learning Robust to Adversarial Distribution Shift
We now consider the second case, where A'(FNA) P(ENA)) A)
P(TPA) A) P((PPA)
(J. TPR (/)
P(A) 1'(A,1)
P(TPA) P(TPA)
P(A,1) P(A,1)
PAA -
(P(,1) -c)
P(TPA)E
1(A.1)
1
P(A,1)
1
P'(A,1)
1
Se (A,, 1))
is easy to see that in the third case, where a lies in both TPA and FNA, A is bounded by the max value of ATPRA of cases and
Here argued for when (A, 1) loses mass. We can similarly argue the case where (A, 1) gains mass, giving identical bound. Also, here we argued for group A, and an identical argument for D shows that
TP; P) - (PRA SE ( ((D,))))))P(DD..))
(10)
Plugging Equations 9 and 10 into Equation 8, we get that
[Unfro P) (n, PJ) Se (mI(()D..),PP(,,I1) + (,
Now we prove our main result (Theorem 2).
Proof of Theorem 2. Following the proof of Theorem 1, by Lemma and transitivity, it suffices to show the theorem statement for the case where the transition from P to P' is elementary in that the only difference between the two distributions is that there are two elements a and that have e more mass and e less mass, respectively, in P as compared to p' (all other elements have the same mass in the two distributions). So, in the remainder of the proof, we only consider elementary transitions.
Consider the transfer of mass from a to b in continuous manner. During this process, either the cell corresponding to element will monotonically increase in score monotonically decrease in score The same holds for the cell corresponding to element b. The scores of all other cells will remain the same. In the following argument, we assume that the score of the cell decreases monotonically and that b increases monotonically. All of the arguments are analogous for the remaining three cases.
Let f denote the EO-fair BOC for the current distribution P at any instant this mass transfer process ending in distribution P'. As the mass transfer proceeds, analyze how the EO-fair BOC changes from fE0 to fE0. We consider the largest mass transfer de until one of the two following events occur.
1. Equal-score event: The cell of has the same score the adjacent cell lower in the sorted order the cell of b has the same score as the adjacent cell higher in the sorted order.
'In the cell corresponding has of 0 or 1, it's will remain unchanged, and this is trivially covered by argument.
16

---

Optimal Fair Learning Robust to Adversarial Distribution Shift
2. Threshold event: The score of a merged cell containing or becomes exactly 0.5.
Note that by the choice of òe, during the transfer de, all the cells remain in the same order in both groups; furthermore, all masses and scores of all cells other than the ones containing a or b remain the same during the transfer. By Claim 3,
dUnfEo = [nfEoOsP E0 P)
Unfgo 50 ,P))
1
S de
1(A,1) P(D,1)
Since Unfgo ( (P)) =0, O. we know that 8Unfgo Unfeo P') = A (f)), -PP)-TPR-( 50 P')]- Consider the cell q that split by the threshold corresponding that after the transition, f has OUnfgo difference in TPR between groups. To modify 1 + fpr, we therefore need to move to move the boundary at that TPR in both groups align and EO is satisfied (the classifier f remains the same apart from its action on q). The change in function ((f((g)) of element is bounded P(D.1)
(for now, assume q D). Since neither the equal-score event nor
the 0.5-score event occur,
by JUnfgo p(4) after scaling (since P(D, 1 (1) (q)) If f' denotes the EO-Fair BOC for the distribution at the end of the mass transfer (just prior to any of the two events), then by Lemma 2, the change accuracy
of the optimal fair classifier is bounded by
|Ace(S , P)- - Acc( PP) - (25(() - 1)4 + Ōe
1
P(D,1) -1)
$ 8c
(11)
min(P(A, 1), P'),
min(P(D,11,, P'(), 1
S(q)
1
P(D)
S 6E minn(P(A, 1), P)(A,1) min(P(D,1),,P'I))) P",, 1))
+ òe,
(12)
S(g)
where the last equation follows by monotonicity. Note that S(q) can potentially blow up, and would like to bound it. Notice that since by assumption, splits q the middle, we know that there a portion of q that accepted. Hence, the weighted score of a merged cell involving 9 (say Cg)) has score above the threshold of 0.5. Let Cg contain some element t from group A, and denote length of group in C. by 1z. Since the TPR of both components are equal, we know that
P(A)LS(() P(D))D(()) P(A.1)
(13)
P(D,1)
Also, since S(C,) 0.5, we know that
P(A) + P(D)))S()) 2 P(A)AA P(A)IA+ P(D)LD
(14)
2
Combining Equations 13, and 14, and after bunch of simplification, we get that
S(q) < 2P(1)
1(A,1) P(D,1)S(()
(15)
P(D,1)
2P(1)
(16)
1(D,1)
Where the second equation follows because S(t) 0. Plugging Equation 16 into Equation 12, we get that
1
1
|Ace[ - Acc((", S
min((P(D,)) P'D,)))) min(P(A, 11,),P((AA11) +
2P(1) + de
1
1
< de
2 (max de (monotonicity)
(n,, P'(A min(P(DD,),PP(,,)))
The handling of the equal-score and threshold events identical to that in the proof of Theorem We repeat here for convenience.
17

---

Optimal Fair Learning Robust to Adversarial Distribution Shift
1. Equal-score event: If the cell of has the same score the adjacent cell lower in the sorted order, then swap the cells so that the cell of is lower in the order. Similarly, if the cell of has the same score the adjacent cell higher in the order, then we swap the two cells so that the cell of 6 is higher in the order. We update the classifier f and note that this change has no impact on the accuracy of f.
2. Threshold event: The score of merged cell containing b becomes exactly 0.5, We include the merged cell in the classifier again without changing accuracy.
Thus, between any two occurrences of these events, the change in accuracy bounded by an amount proportional to the mass transfer; when we reach these occurrences, the mass transfer is paused, the BOC changes without any change in accuracy. Furthermore, every occurrence of the event, one of these three events happen: the cell containing a moves down in the order, the cell containing b moves up in the order, number of times these events can occur is upper bounded by the number of cells in the two groups, this process is finite. Therefore, adding over all the òc mass transfers, we obtain the desired bound on the change in accuracy between the BOC's s for P and p', thus completing the proof of the theorem.
additional merged cell is placed above the threshold. Since the
B.3. Predictive Equality
We can obtain analogous results for Predictive Equality from the same proof techniques as that of Equal Opportunity (since we can just reverse the roles of the labels 0 and in EO to get results for PE). Hence, we only discuss the proofs for EO, and state the analogous results for PE below without proof.
Claim (PE Shift for a Fixed Hypothesis). Given distributions P, P,P', such that TV(P, Pt) S and any hypothesis J. it holds that
Unfre P) Unfrelf, P') S
(), + min(P((DO), P' (((,0))
Theorem 3 (Robustness of PE-Fair BOC). Given distributions P, P', such that TV(P, P') = we have that
Acc(fp CPE P) - Ac P']] e [1+ ( maxx)
1
1
min (AN(((A,))PPAAAAA)))
min (P(D,O),P'(D,
where fPF .pt are the PE-Fair BOC's on P, P' respectively.
Corollary 3. Given distributions P, P', such that TV(P, we have that
1 |Ace[fE P) Apc P) < 2E 1 max)) (ni, (A(,)) (Pn(P(D..),P((,..))
1
+
where f50 :50 are the FO-Fair BOC's on P, respectively
18


Reviews:
[{"review_id": "XSwZZxL6tE", "reviewer": "Reviewer_xC67", "summary": "The authors study the robustness of the Fair Fair Bayes Optimal Classifier (BOC) to adversarial noise in the data distribution.  They show that the robustness guarantee for BOC breaks down when fairness constraints are aded and propose a randomized Fair BOC that is robust to malicious noise in the data distribution.  They demonstrate this with various fairness constraints such as Demographic Parity, Equal Opportunity and Predictive Equality.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your insightful feedback, and for appreciating the importance of our contribution, and the clarity of presentation. We respond to your comments below. \n\n\n**1. Experiments:** We emphasise that the focus of our paper is to advance the theoretical foundations of robust fair learning, building upon the theoretical works of Konstantinov-Lampert (2022) and Blum et al. (2024). While experiments would be valuable, we leave that as future work.\n\n**2. Randomization:** It is established that on most distributions, (exact) fairness is non-trivially achievable only by randomized classifiers [Agarwal et al, Hardt et al.]. In addition, the randomization in our result is almost nil, and is the minimum amount required (only on one element). If we strictly enforce determinism, the drop in accuracy is significant, as demonstrated in Claim 1. Hence, there is a clear tradeoff between randomization and accuracy (subject to fairness), and for a tiny amount of randomness, we obtain a big jump in accuracy.\n\n1. Moritz Hardt, Eric Price, and Nathan Srebro. Equality of Opportunity in Supervised Learning. NeurIPS 2016\n2. Alekh Agarwal, Alina Beygelzimer, Miroslav Dudík, John Langford, and Hanna Wallach. A Reductions Approach to Fair Classification, ICML 2018.\n\n\nWe hope that our response has addressed your concerns, and if so, kindly request you to consider increasing your score, and support towards a consensus for acceptance of our paper.", "claims_and_evidence": "The proofs for the theoretical claims are thorough.  I would like to see additional empirical results as well to solidify the claims.", "methods_and_evaluation_criteria": "Yes", "theoretical_claims": "Yes, I reviewed the proofs and claims but it is possible that I missed something.", "experimental_designs_or_analyses": "There is no direct experimental design.  An empirical analysis is missing.", "relation_to_broader_scientific_literature": "Yes, fairness issues have grown in importance and ensuring that adding fairness constraints preserves robustness is an important contribution.", "essential_references_not_discussed": "Not that I noticed.", "other_strengths_and_weaknesses": "The motivation and the writing are very clear and easy to follow.  The theoretical contributions and proofs are also clear.", "other_comments_or_suggestions": "I would suggest validating the contributions with empirical results as this would make the paper stronger.", "questions_for_authors": "While the randomized Fair BOC is shown to be nearly deterministic, the existence of stochasticity may limit it's applicability over BOC.  Is this a concern?", "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": "", "extra_scores": {}}, {"review_id": "ccspuPrqIy", "reviewer": "Reviewer_A37v", "summary": "The paper studies the fairness-aware classification problem, where the goal is to maximize accuracy subject to the demographic parity or equal opportunity fairness constraint. The paper first discusses Claim 1 that a deterministic classification rule can have high sensitivity to perturbations to the data distribution. An example is discussed under Claim 1 to support this claim. Next, the discussion focuses on evaluating the sensitivity of the randomized fair classifier and the main result in Theorem 1 (and Corollary 1) shows an $\\epsilon$ TV-perturbation to the data distribution leads to a worst-case $\\epsilon$-times-a sensitive attribute probability constant difference in the accuracy of the optimal fair classifier.", "questions": "", "limitations": "", "rating": 2, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your time and insightful feedback. We respond to your comments below. \n\n\n**1. Real-world datasets:** Our setup assumes a distribution over a discrete domain space $X$, which is a standard assumption for real-world tabular datasets (e.g., COMPAS) with features such as age, race, DoB, prior counts etc. We do not make any other assumptions on $X$. In particular, $X$ could be large, and multidimensional. The same holds for the non-robustness phenomenon is Claim 1. While experiments could be insightful, we emphasise that the focus of our paper is to establish the theoretical foundations of robust fair learning, building upon the theoretical papers of Konstantinov-Lampert (2022), and Blum et al. (2024).\n\n\n\n**2. Larger, non-degenerate example:** In Claim 1, we provided a small example, independent of the sensitive attribute, just to demonstrate the phenomenon of non-robustness that occurs in optimal fair *deterministic* classifiers. The example can be made much larger (in fact, it can be made arbitrarily large). In addition, $X$ can also be multidimensional, and can depend on the sensitive attribute. The below example assumes $|X| = 10$, with $X$ also depending on the sensitive attribute. Consider the following distribution $P$.\n\n\n$P,S(x_1, A) = (0.055, 0.9)$  | $P, S(x_1, D) = (0.045, 0.91)$ |\n$P, S(x_2, A) = (0.055, 0.8)$  | $P, S(x_2, D) = (0.05, 0.78)$ |\n$P, S(x_3, A) = (0.045, 0.73)$ | $P, S(x_3, D) = (0.045, 0.71)$ |\n$P, S(x_4, A) = (0.04, 0.67)$ | $P, S(x_4, D) = (0.06, 0.63)$ |\n$P, S(x_5, A) = (0.055, 0.53)$ | $P, S(x_5, D) = (0.05, 0.51)$ |\n$P, S(x_6, A) = (0.045, 0.45)$ | $P, S(x_6, D) = (0.05, 0.46)$ |\n$P, S(x_7, A) = (0.055, 0.33)$ | $P, S(x_7, D) = (0.06, 0.32)$ |\n$P, S(x_8, A) = (0.04, 0.28)$ | $P, S(x_8, D) = (0.04, 0.24)$ |\n$P, S(x_9, A) = (0.06, 0.17)$ | $P, S(x_9, D) = (0.055, 0.15)$ |\n$P,S(x_{10}, A) = (0.05, 0.09)$ | $P, S(x_{10}, D) = (0.045, 0.7)$ \n                           \n                            \nConsider $f$, which classifies $\\{x_1,..., x_5\\} \\times \\{A, D\\}$ as $1$, and $\\{x_6,...,x_{10}\\} \\times \\{A, D\\}$ as $0$. $f$ satisfies $DP$, and has accuracy much more than $0.5$. Consider the neighboring $P^′$ which differs with $P$ on $(x_5, A)$, and $(x_5, D)$, as follows.\n\n\n$P', S(x_5, A) = (0.055 + \\epsilon, 0.53)$ | $P', S(x_5, D) = (0.05 - \\epsilon, 0.51)$,\n\nwhere $\\epsilon > 0$ is arbitrarily small. There are only 2 deterministic classifiers satisfying DP on $P’$, either the constant 1 classifier $f_1$, or the constant 0 classifier $f_0$, both with accuracy close to 0.5. Hence, the difference in accuracy of the deterministic DP-fair BOC on arbitrarily close $P, P^′$ is large, demonstrating non-robustness. \n\n\n**3. Proof length:** Perhaps the proof can be shortened, we will try and simplify it to aid readability. Lemma 1 played a crucial role in simplifying the proof overall, but it can be done without Lemma 1 as well.\n\n\n**4. Approximate fairness:** We show through the example below that the non-robustness phenomenon highlighted in Claim 1 also holds when we only require approximate fairness. In particular, this can hold in the case where sensitive group populations are highly imbalanced, for example when the mass of group $A$ is much larger than the mass of group $D$, i.e., $P(A) >> P(D)$. We define a $\\delta$-approximately fair classifier as follows, “If $r$ denotes selection rate, a classifier $f$ is $\\delta$-approximately DP-fair if $|r(f, A)−r(f, D)| < \\delta$\". We set $\\delta=0.25$, and slightly modify the example in Claim 1, where we skew the probability mass towards Group $A$ (in Claim 1, the group masses are balanced). Consider a distribution P, where\n\n$P, S(x_1, A) = (0.4, 1)$ | $P, S(x_1, D) = (0.1, 1)$ |\n$P, S(x_2, A) = (0.4, 0)$ | $P, S(x_2, D) = (0.1, 0)$\n\nConsider the (deterministic) classifier $f$, with $f(x_1, A) = f(x_1, D) = 1, f (x_2, A) = f (x_2, D) = 0$. $f$ satisfies DP, and $\\text{Acc}(f) = 1$. Consider the neighboring distribution $P^′$ differing only on $(x_1, D), (x_2, D)$,  as follows.\n\n\n$P', S(x_1, D) = (0.1 + 0.05, 1)$ | $P', S(x_2, D) = (0.1 - 0.05, 0)$\n\nIf we apply $f$ on $P’$, it does not satisfy approximate DP for any $\\delta <  0.25$, even though $TV(P, P’)$ is small ($0.05$). There are only 2 deterministic classifiers satisfying approximate DP for any $\\delta <  0.25$, either the constant 1 classifier $f_1$, or the constant 0 classifier $f_0$, with $\\text{Acc}(f_1) = 1/2 + 0.05$, and $\\text{Acc}(f_0) = 1/2 − 0.05$. Hence, the difference in accuracy of the deterministic (approximate) DP-fair BOC on closeby $P, P^′$ is almost 0.5, demonstrating non-robustness. \n\nWe will also discuss fairness regularizers based on mutual information, Pearson correlation, HGR correlation, and f-mutual information. These are relevant for broader literature review but not directly related to the problem we study.\n\nWe hope we have addressed all your concerns, and we sincerely request you to reconsider our rating.", "claims_and_evidence": "Only partially. My main concern with this submission is that the authors do not present any numerical and enough theoretical evidence that their theoretical claims are relevant to real non-synthetic data distributions. As I said, the paper does not provide any numerical evaluation of the claim that \"deterministic fair classifiers are sensitive to adversarial noise\".\n\nConcerning the theory results, I think Claim 1 gives a rather degenerate setting where the deterministic fair classifier is sensitive to noise. The example discussed in the proof of Claim 1 focuses on a Binary input $X$, and from the construction of the example, it seems to me that the case is degenerate and highly depends on a binary input $x$ that is independent of the sensitive attribute variable $Z$ and then perturbed to exhibit correlation with the sensitive attribute $Z$. \n\nI am wondering if such an example would be the case for a standard fairness-aware classification setting, such as COMPAS and Adult data. A significant difference in those real-world examples is that the input variable $X$ is multi-dimensional and the cardinality of possible input vector $x$ is much greater than the binary setting in Claim 1. Therefore, I am highly unsure if the issue highlighted in Claim 1 would be relevant to actual fairness-aware tasks. I believe the paper should provide enough evidence that this issue is more significant than a degenerate scenario, particularly because the entire paper is dedicated to showing the issue exists in the deterministic case, while it is not the case with randomized classifiers.", "methods_and_evaluation_criteria": "The paper has no numerical experiments on fairness-aware classification. Regarding the evaluation criteria in the analysis, the paper is missing the discussion of approximately fair classifiers. In practice, the demographic parity condition is not fully enforced in the classification, and instead a dependence quantity, such as mutual information or correlation metric, is regularized in the fairness-aware learning process. Therefore, the independence condition in DP does not strictly hold in real-world applications. \n\nStudying the paper's main results and argument, it seems to me that the Binary-input $X$ example in Claim 1 can be easily addressed by relaxing the DP constraint to a bounded mutual information or maximal correlation. As said above, this has not been discussed in the paper.", "theoretical_claims": "The main text includes the proof of Claim 1 and Theorem 1, and I think the theorems are correct. Still, I was wondering if the proof of Theorem 1 could have been shorter. On another note, I was wondering why the authors use about 3 pages to prove Theorem 1 before stating the result. I suggest discussing the theorem right after Claim 1 and postponing the proof to the supplementary material. The saved space can be used for numerical evaluation of the results and further theoretical discussion.", "experimental_designs_or_analyses": "The paper presents no experimental results on fairness-aware classification.", "relation_to_broader_scientific_literature": "I think the literature review and paper's discussion is missing a large body of related works on approximate fairness in fairness-aware classification. This includes references suggesting to replace the hard demographic parity constraint with regularizing dependence measures such as mutual information, Pearson correlation, HGR correlation, $f$-mutual information, and its special cases. In practice, the demographic parity and equal opportunity are not enforced with hard constraints, and instead there is an optimization constraint or regularization penalty term to penalize significant values of dependence between the variables. I understand that the paper focuses on the extreme case of completely fair classifier, but the discussion should still include some clues on how the results would theoretically or empirically relate to more practical scenarios.", "essential_references_not_discussed": "Please see my answer to the above question.", "other_strengths_and_weaknesses": "Please see my previous answers.", "other_comments_or_suggestions": "Please see my previous answers.", "questions_for_authors": "1- Can the authors provide standard fairness-aware classification settings (like COMPAS and Adult) where the observation in Claim 1 would be relevant?\n\n2- Why the example in the proof of Claim 1 can hold in non-degenerate scenarios where the space of variable $X$ can include a large number of outcomes?\n\n3- Can the proof of Theorem 1 be shortened and is Lemma 1 necessary to prove the lemma?", "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": "", "extra_scores": {}}, {"review_id": "RsBxJBtGKU", "reviewer": "Reviewer_9j8M", "summary": "This paper analyzes/bounds the robustness of the optimal fair classifier $f$ (w.r.t. a distribution $\\mathcal P$) under distribution shifts in terms of both accuracy and performance.  The specific setting considered is binary class, binary group, in the attribute-aware setting, and the fairness criteria considered are SP, EO, EOpp (can be extended to other similar metrics).\n\nIn other words, what would the increase in the accuracy and unfairness of $f$ be if we evaluate it on $\\mathcal P' \\neq\\mathcal P$?", "questions": "", "limitations": "", "rating": 2, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your time and insightful feedback. We will cite and discuss the novel results in the papers you pointed out. However, our results are incomporable to those of the papers mentioned. Fundamentally, the underlying settings are different, and these results complement each other.\n\n**1. Comparison with [Xian & Zhao, 2024]:** \n\nSignificantly, our setup assumes $P_X$ is a *discrete* distribution (over either a discrete or continuous domain $X$), and we will make this explicit in our revision (note that this is a standard assumption for realistic tabular datasets with features like height, income, race, etc.). On the other hand, [Xian & Zhao, 2024] implicitly assume $X$ is a *continuous* domain, and their results in general hold only for continuous distributions $P_X$ over $X$. See Remark 2.4 (fail cases of Assumption 2.2) in [Xian & Zhao, 2024], where the results don’t hold when the push-forward distribution $r\\#P_X$ contains atoms and the randomized Fair BOC splits their mass, corresponding to the case our paper deals with, i.e., discrete distributions (See Claim 1 in our paper).\n\nThere exist many examples of discrete distributions where the optimal fair classifier must be randomized, and resorting to a deterministic classifier must necessarily come with a sharp drop in accuracy (even with the perturbation step described in Proposition 2.3 of [Xian & Zhao, 2024]); see the example in Claim 1 in our paper, where perturbing the scores/risks of each point would not do away with the need for randomization. The technical challenges in the discrete setup are very different from those in the continuous setup. For example, in most discrete distributions, the optimal fair classifier must be randomized, whereas in continuous distributions a deterministic classifier suffices under Assumption 2.2 in [Xian & Zhao, 2024]. Unlike the continuous setting, enforcing determinism in the discrete setting typically leads to non-robustness, for example in Claim 1. \n\nWe also note that the approach mentioned in Remark 2.4 of [Xian & Zhao, 2024] to handle discrete distributions, i.e., smoothing the discrete distribution and then applying the algorithm in the paper with a deterministic classifier, does not apply to discrete domains; furthermore, for continuous domains it will almost certainly lead to a drop in accuracy.\n\nTo summarize, while our submission and [Xian & Zhao, 2024] share the focus on robustness and fairness, our respective underlying frameworks are fundamentally different and complementary. \n\nFinally, we emphasize that our robustness guarantees (Theorems 1, 2, & 3) cover adversarial distribution shifts over $X\\times Z \\times Y$, whereas the sensitivity analysis in Theorem 3.1 of [Xian & Zhao, 2024] covers either a shift in label distribution over $X\\times Y$, or a shift in group distribution over $X \\times Z$.\n\n**2. Comparison with [Chen et al., 2024]:** Unlike us, they do not deal with adversarial distributions shifts, but only label distribution shifts and/or group distribution shifts. In addition, our setups are fundamentally different, theirs being the continuous case, and ours being the discrete case. Moreover, their sensitivity analysis in Theorem 2 is looser, and has an extra additive error term, unlike ours and that of [Xian & Zhao, 2024]. Besides, they do not deal with the case of perfect fairness, and require $\\delta > 0$. \n\n**3. Comparison with [Chen et al., 2022]:** Their result is fundamentally different, and essentially shows that the fairness of a fixed hypothesis class on two similar distributions is similar. This is essentially what we show in Claims 2/5/6, however, they only deal with label and covariate shifts, while we tackle the more general case of adversarial distribution shifts.\n\nWe hope that our response has addressed your concerns, and if so, we respectfully request you to consider increasing your rating.", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "N/A", "theoretical_claims": "Proofs are not checked, but the theorem statement/results are reasonable.", "experimental_designs_or_analyses": "N/A", "relation_to_broader_scientific_literature": "This paper considers the robustness of fair classifiers subject to distributional shifts; the exact contribution is the bound/sensitivity analysis for accuracy and unfairness of an optimal fair classifier evaluated on a shifted distribution.\n\nBut the reviewer is aware of similar results in prior publications that appear to subsume the results in this paper: see \"Other Strengths And Weaknesses\"", "essential_references_not_discussed": "See Other Strengths And Weaknesses.", "other_strengths_and_weaknesses": "Weaknesses.\n\nWhile the results are concrete and rigorously established, the reviewer would like the authors to comment on the similarities/differences between these results and the sensitivity analysis in prior work for optimal fair classifiers:\n\n- [Xian & Zhao, 2024]: Theorem 3.1 in Section 3.2 Sensitivity Analysis bounds the accuracy and unfairness of a classifier that is optimal and fair under a different distribution (specified via $\\hat r\\neq r$ for a shift in the label distribution, and $\\hat g\\neq g$ for a shift in the group membership distribution); this analysis applies to SP, EO and EOpp under attribute-blind setting for multigroup and multiclass classification, which is more general than the setting considered in this paper.  They also seem to show that their bound has a matching lower bound by an example.\n- [Chen et al., 2024]: Section E contains a similar sensitivity analysis, for the same setting except binary group and binary class.\n- [Chen et al., 2022]: They also consider fairness under distribution shift, with a similar result that involves a Lipschitz condition.  Could the authors comment on any similarities/differences between the two works?\n\n[Xian & Zhao, 2024] A Unified Post-Processing Framework for Group Fairness in Classification  \n[Chen et al., 2024] Post-hoc Bias Scoring Is Optimal For Fair Classification  \n[Chen et al., 2022] Fairness Transferability Subject to Bounded Distribution Shift", "other_comments_or_suggestions": "N/A", "questions_for_authors": "See Other Strengths And Weaknesses", "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": "", "extra_scores": {}}, {"review_id": "HqgiimhleH", "reviewer": "Reviewer_Am5P", "summary": "This paper demonstrates that randomized fairness-aware classifiers have the local Lipschitz property, which makes them (somewhat) robust to adversarial perturbations of their training data. The authors demonstrate that randomization is crucial for this property (confirming a previously known result), but also demonstrate that it may be confined to a single point; finally, they bound the Lipshitz constant for several popular fairness criteria.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your thoughtful feedback and for appreciating the novelty of our results and the clarity of presentation. We recognize the importance of making the intuition in Section 1.2 as clear as possible for better readability of the rest of our paper. Acting on your suggestion, we will update our manuscript with a diagram (similar to the visualization here https://cococubed.com/images/raybox/five_shapes.pdf).\n\nWe provide a brief verbal explanation here: The hypercube represents the space of all classifiers, with each dimension corresponding to a data point. The fairness constraint is modeled as a hyperplane. The intersection of any hyperplane with the hypercube results in a bounded region whose vertices are either (i) vertices of the hypercube itself or (ii) points formed by the intersection of the hyperplane with an edge of the hypercube. In other words, all vertices of this intersection lie on the 1-skeleton (or polytope graph) of the hypercube. Accuracy can be understood as a directional objective, and the fair BOC corresponds to an extremal point in that direction on the intersection of the hyperplane and the hypercube. Since, in every direction, an extremal point must be a vertex, and all vertices lie on the 1-skeleton, it follows that the fair BOC necessarily lies on the 1-skeleton of the hypercube.\n\nWe hope that our response adequately addresses your questions, and we sincerely request your support towards a consensus for acceptance of our paper.", "claims_and_evidence": "Yes.", "methods_and_evaluation_criteria": "There are no experiments in this paper.", "theoretical_claims": "Yes; I did not find any issues.", "experimental_designs_or_analyses": "There were no experiments.", "relation_to_broader_scientific_literature": "The key contributions present some properties of randomized fairness-aware classifiers that, as far as I know, are novel. As such, this work adds to the literature that studies randomized fairness-aware classifiers and demonstrates their advantages over deterministic ones in cases of fairness thresholds.", "essential_references_not_discussed": "None, to my knowledge.", "other_strengths_and_weaknesses": "I really appreciated the mostly clear writing of the paper and the intuitions provided. The authors’ positioning of their work in a sociological context by discussing the advantages and disadvantages of randomized classifiers vis-a-vis the sociological goals was also very nice.", "other_comments_or_suggestions": "The intuition in Section 1.2. was not immediately very clear, it would have been helpful to have more explanation for how the 1-skeleton of the intersection of the hyperplane and the hypercube relates to the classifier and the datapoints.", "questions_for_authors": "None", "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": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: The papers study the robustness of fair Bayes optimal classifiers under malicious noise.

There was a good amount of discussion between us about the pros and cons of this paper. Some reviewers appreciated the clear motivation of the paper and highlighted the importance of randomness in the robustness of fair qualifiers. Other reviewers, on the other hand, found the example provided in Claim 1 to be unrealistic or requested empirical study. After going back and forth, I sided with the former group. I consider the example to demonstrate solely the claim that randomness is necessary. Also, this is a theory paper, and ICML papers are not required to contain an experimental section. Therefore, I would be happy to recommend this paper for acceptance.

Finally, although the work of Xian-Zhao 24 pointed out by Reviewer 9j8M counts as concurrent work based on ICML policy, I recommend the authors cite this paper as concurrent work and describe the similarities and differences now that they are aware of it.
Decision: Accept (poster)