Fair Classification with Adversarial Perturbations
Authors: L. Elisa Celis
Anay Mehrotra
Nisheeth K Vishnoi
Venue: NeurIPS 2021 Poster (2021)
Keywords: Fair classification
Algorithmic fairness
Adversarial data

Abstract: We study fair classification in the presence of an omniscient adversary that, given an $\eta$, is allowed to choose an arbitrary $\eta$-fraction of the training samples and arbitrarily perturb their protected attributes. The motivation comes from settings in which protected attributes can be incorrect due to strategic misreporting, malicious actors, or errors in imputation; and prior approaches that make stochastic or independence assumptions on errors may not satisfy their guarantees in this adversarial setting. Our main contribution is an optimization framework to learn fair classifiers in this adversarial setting that comes with provable guarantees on accuracy and fairness. Our framework works with multiple and non-binary protected attributes, is designed for the large class of linear-fractional fairness metrics, and can also handle perturbations besides protected attributes. We prove near-tightness of our framework's guarantees for natural hypothesis classes: no algorithm can have significantly better accuracy and any algorithm with better fairness must have lower accuracy. Empirically, we evaluate the classifiers produced by our framework for statistical rate on real-world and synthetic datasets for a family of adversaries.

Fair Classification with Adversarial Perturbations
L. Elisa Celis Yale University
Anay Mehrotra Yale University
Nisheeth K. Vishnoi Yale University
Abstract
We study fair classification in the presence of omniscient adversary that, given an T) is allowed to choose an arbitrary v--fraction of the training samples and arbitrarily perturb their protected attributes. The motivation comes from settings which protected attributes can be incorrect due to strategic misreportig, malicious actors, or errors in imputation; and prior approaches that make stochastic or independence assumptions errors may not satisfy their guarantees in this adversarial setting. Our main contribution is an optimization framework to learn fair classifiers this adversarial setting that comes with provable guarantees on accuracy and fairness. Our framework works with multiple and non-binary protected attributes, is designed for the large class of fineao-fractional fairesss metrics, and can also handle perturbations besides protected attributes. We prove near-tightness our framework's 's guarantees for natural hypothesis classes: algorithm significantly better accuracy and any algorithm with better fairness must have lower accuracy. Empirically, evaluate the classifiers produced by our framework for statistical rate on real-world and synthetic datasets for a family of adversaries.
have
Introduction
It is increasingly common to deploy classifiers to assist in decision-making in applications such as criminal recidivism [50), credit lending (21). and predictive policing [34]. Hence, imperative to ensure that these classifiers are fair with respect to protected attributes such as gender and race.
Consequently, there has been extensive work on approaches for fair classification (32 26
28 17
62
I 13]. At high level, classifier f is said to be "fair" with respect to protected attribute if has similar "performance" with respect to given metric on different protected groups defined by Z. Given fairness metric and a hypothesis class F, fair classification frameworks consider the problem of finding a classifier f* F that maximizes accuracy constrained to being fair with respect to the given fairness metric (and Z) [8] To specify faimess constraints, these approaches need protected attributes of training data to be known.
48
24 27
However, protected attributes can be erroneous for various reasons; there could be uncertainties during data collection or data cleaning process 20 52], or the attributes could be strategically misreported [46]. Further, protected attributes may be missing entirely, as is often the case for racial and ethnic information in healthcare
20 or when data is scraped from the internet as with many image datasets [22 66 35 In these cases, protected attributes can be "imputed" [88 36 [6], but this can also introduce errors [2; further, imputation by machine-leaminng based methods is known be
fragile to imperceptible changes in the inputs [29] and to have correlated errors across samples [49] Perturbations protected attributes, regardless of origin, have been shown to have adverse effects on fair classifiers, affecting their performance on both accuracy and fairness metrics; see e.g., [16] (7]
Towards addressing this problem, several recent works have developed fair classification algorithms for various models of errors in the protected attributes. 44 consider an extension of the "mutually contaminated learning model" [53] where, instead of observing samples from the "true" joint distribution, distributions of observed group-conditional distributions are stochastic mixtures of their true counterparts. [6] consider a binary protected attribute and Bernoulli perturbations that are
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

independent of the labels (and of each other). [14] consider the setting where each sample's protected attribute is independently flipped a different value with a known probability. (59] considers two approaches to deal with perturbations. In their "soft-weights" approach, they assume perturbations follow a fixed distribution and one has access to an auxiliary data containing independent draws of both the true and perturbed protected attributes. In their distributionally robust approach, for each protected group, its feature and label distributions in the true data and the perturbed data are a known total variation distance away from each other. Finally, in an independent work, [40] study fair classification under the Malicious noise model [56] 39] in which a fraction of the training samples chosen uniformly at random, and can then be perturbed arbitrarily.
Our perturbation model. We extend this line of work by studying fair classification under the fol- lowing worst-case adversarial perturbation model: Given an 17 > 0, after the training samples are in- dependently drawn from a true distribution DD the adversary with unbounded computation power sees all the samples and can use this information to choose any ry-fraction of the samples and perturb their protected attributes arbitrarily. This model a straightforward adaptation of the perturbation model of 31 to the fair classification setting and we refer to it the 1--Hamming model. Unlike perturbation models studied before, this model can capture settings where the perturbations are strategic or arbitrar- ily correlated as can arise in the data collection stage or during imputation of the protected attributes, and in which the errors cannot be "estimated" using auxiliary data. In fact, under this perturbation model, the classifiers outputted by prior works can violate the fairness constraints by large amount or have an accuracy that is significantly lower than the accuracy of f*; see Section 5 and Supplementary Material D.2 Taking these perturbed samples, fairness metric Ω, and desired faureess threshold as input, the goal is to learn a classifier f with the maximum accuracy with respect to the true distribution D subject to having faimess value, (J) of at least 7 with respect to the true distribution D.
Our contributions. We present an optimization framework (Definition 4.1) that outputs fair clas- sifiers for the 1--Hamming model and comes with provable guarantees on accuracy and fairness (Theorem 4.3) Our framework works for multiple and non-binary protected attributes, and the large class of finea-fractional fairness metrics (that capture most fairness metrics studied in the literature); see Definition and [13.. The framework provably outputs a classifier whose accuracy is within 20 of the accuracy of f* and which violates the fairness constraint by at most ((1/x) additively (Theorem 4.3). under the mild assumption that the "performance" of f* on each protected group is larger than known constant À >> 0 (Assumption[[] Assumption is drawn from the work of [14 for fair classification with stochastic perturbations. While it is not clear if the assumption is necessary in their model, we show that Assumption i necessary for fair classification in the H--Hmminng model: If A is not bounded away from 0, then no algorithm can give a non-trivial guarantee on both accuracy and fairness value of the output classifier (Theorem 4.4). Moreover, we prove the near-tightness of our framework's s guarantee under Assumption [ No algorithm can guarantee to output a classifier with accuracy closer than 17 to that of f* and any algorithm that violates the fairness constraint by less than */(20>) additively has an accuracy at most 19/20 (Theorems 4.5 and [A.2].. Finally, we also extend our framework's guarantees the Nasty Sample Noise model (Supplementary Material 15...)). The Nasty Sample Noise model is a generalization of the 17- 7-Hamming model, which was studied by 11 in the context of PAC learning (without any fairness considerations), where the adversary can choose any frarcction of the samples, and can arbitrarily perturb both their labels and features.
We implement our framework for logistic loss function with linear classifiers and evaluate its perfor- mance on COMPAS 3. Adult (23). and a synthetic dataset (Section 5) We generate perturbations of these datasets admissible in the 7J-Hamming model and compare the performance of our approach to several baselines 44 6 59 4 40) with statistical rate and false-positive rate as fairness metrics [ On the synthetic dataset, we compare against a method developed for fair classification under stochastic perturbations [14] and demonstrate the comparative strength of the 17- y-Hamming model; our results show that [4] 's framework achieves a significantly lower accuracy than our framework for the same statistical rate. Empirical results on COMPAS and Adult show that the classifier output by our frame- work can attain better statistical rate and False-positive rate than the accuracy maximizing classifier on the true distribution, with a small loss in accuracy. Further, our framework has a similar (or better) trade-off compared to all baselines we consider in a variety of settings, and is not dominated by any other approach (Figure T and Figures 7 and g in Supplementary Material E.2
'Let (f, SR) (respectively (f, FPR)) be the fraction of positive predictions (respectively false- false-positive predictions) by f in the E-th protected group. f's statistical rate (respectively false- cosss---iiivee rate) is the ratio of the minimum value to the maximum value of ge (e) (respectively qe(f, FPR)) over all protected groups
2

---

Techniques. The starting point of our optimization framework (Definition 4.1 is the "standard" optimization program for fair classification the absence of any perturbations: Given faimnsss metric Ωt and desired fairness threshold T as input, find f E F that maximizes the accuracy on the given data S constrained to a fairness value at least 7 on the given data. However, when S given to us by an 17- 1-Hamming adversary, this standard program, which imposes the fairness constraints with respect to the perturbed data S, may output a classifier with an accuracy/fairees-valle than that of f when measured with respect to D. But, observe that the difference in accuracies of classifier when measured with respect to the given data S and data sampled from D is at most v). Thus, if f E F is feasible for the standard optimization program, this observation (used twice) implies that the accuracy of the output classifier measured with respect to D is within 27j of the accuracy of f* measured with respect D (Equation (8). However, without any modifications, the classifier output by the standard optimization program could still have a fairness value much lower than r with respect to D (see Example A.27). To bypass this, we introduce the notion of s-stability that allows us to lower bound the fairness value of a classifier with respect to D given its fairness value on S. Roughly, f E F is said to be s-stable with respect to a fairnsss metric if for any S that is generated by an 17-Hamming adversary, the ratio of fairness value of f with respect to DD and with respect to S is between and 1/2 (see Definition 4.7). It follows that any s-stable classifier that has fairness value r' > 0 with respect to S. has faimess value at least s 7' with respect to D. Hence, an optimization program that ensures that all feasible classifiers are s-stable (for a suitable choice of s) and have fairness value at least 7' > 0 with respect to S, comes with guarantee that any feasible classifier has a fairness value at least s 7' (with respect to D). If such an optimization program could further ensure that f is feasible for it, then by arguments presented above, the classifier output by this optimization program would satisfy required guarantees on both fairness and accuracy (Lemma 4.9p. The issue is that, to directly enforce s-stability, one needs to compute the fairness values of classifiers with respect to D, but this is not possible in the absence of samples from D. We overcome this by present "proxy" constraint on the classifier (Equation (5) that involves only S and ensures that any classifier that satisfies it is s-stable. Moreover, f* satisfies this constraint under Assumption [ Overall, modifying Program (2) to include this constraint (Equation (5)) with suitable value of and setting an appropriate fairness threshold J so that f* remains fcasible, leads us to our framework.
worse
2 Related work
In this section, we situate this paper in relation to lines of work which also consider fair classification with perturbed protected attributes; additional related work (e.g., fair classification in the absence of protected attributes) are presented in Supplementary Material D.I
44 give framework which comes with provable guarantees on the accuracy and fairness value of output classifiers for a binary protected attribute and either statistical rate or equalized-odds fairness metrics. (6] identify conditions on the distribution of perturbations under which the post-processing algorithm of 332 improves the fairness value of the accuracy- maximmiiiiaiiiizinggg classifier with respect to cqualized-odds
the true distribution with a binary protected attribute. [59] consider a non- binary protected attribute. In their seighwseihtt"" approach, they give provable guarantees on the accuracy (with respect to f*) and fairness value of the output classifier in expectation and in their distributionally robust approach, they give provable guarantees on the fairness value of the output classifiers [14] give provable guarantees on the accuracy and fairness value of output classifiers for multiple non-binary protected attributes and the class of linear-fractions fractional metrics. All of the aforementioned works [44] 6 59 [4] consider stochastic perturbation models, which are weaker than the model considered in this paper. Further, compared to [4] 6), our approach (and that of [14] can handle multiple categorical protected attributes and multiple fineto-fractional metrics (which include statistical rate and can ensure squalized-odde constraints). Compared to 6 59 our work (and those of [4 [4] give provable guarantees on the accuracy (with respect to f*) and fairness value of output classifiers with high probability. In another related work, 40) give an algorithm for a binary protected attribute which, under the realizable assumption (i.e., assuming there exists a classifier with perfect accuracy), outputs a classifier with guarantees on accuracy and fairness value with respect to the true-positive rate fairness metric. They study the Malicious noise model, which can modify a uniformly randomly selected subset of samples arbitrarily; this is weaker than the and hence, than the model considered in this paper. Further, our
Nasty Sample Noise model
'Supplementary Material D.2.3 gives an example where [59 's distributionally robust approach outputs classifier whose accuracy arbitrarily close 
3

---

framework works without the realizable assumption (i.e., in the agnostic setting), can handle multiple and non-binary protected attributes, and can ensure fairness with respect to multiple fractffractional metrics (which include true-positive rate).
Another line of work has studied PAC learning in the presence of adversarial (and stochastic) perturbations in the data, without considerations of fairness [39 2 15 5: see also A.. In particular, (TT) study PAC learning (without fairness constraints) under the Nasty Sample Noise model. They use the empirical risk minimization framework (see, e.g., (54)) run on the perturbed samples to output classifier. Our framework Program (ErrT Tolerant) finds empirical risk minimizing classifiers that satisfy fairness constraints on the perturbed data, and that are also "stable" for the given faimess metric. While both frameworks show that the accuracy of the respective output classifiers is within 27 of the respective optimal classifiers when the data is unperturbed, the optimal classifiers can be quite different. For instance, while [I]'ss 's framework is guaranteed to output a classifier with high accuracy, it can perform poorly on fairness metrics; see Section ann Supplementary Material 1
3 Model
Let the data domain be D = X' x 10. x [p]. where X' is the set of non-protected features, {0, 1} is the set of binary labels, and [p] is the set of protected attributes. Let 'D be a distribution over D. Let F S f0. 1 x be hypothesis class of binary classifiers. For f F, let Erry(f) = Pr(x.Y2))=D(((X 2) + Y] denote s's predictive error on draws from D. In the vanilla classification problem, the learner L's goal is to find a classifier with minimum error: argmin (fr In the fair classification problem, the learner is restricted to pick classifiers that have "similar performance" conditioned on Z = l for all i E [p]. We consider the following class of metrics.
Definition 3.1 ([inear/inear-fractio)
metrics [3). Given f E F and two events E()) and (f), that can depend on f. define the performance of f on Z = e E [p]) qe(f) = Prp E()) {()), 2 =
f.. Ef depends on f, then (f(f) is said to be linear-fractional, otherwise linear.
Definition 3.1 captures most of the performance metries considered in the literature. For instance, for 3 = f = 1) and E' == V. we get statistical rate (a linear metric) P For m == (f = and 3' (Y 0). we get false-positive rate (also linear metric). For 3 == (Y = 0) and E' (f= we get false-discovery rate (a linear-frattion metric). Given a performance metric q. the corresponding fairness metric is defined as
minge(o) (e(s)
Pp(f)=
max qe)
When D is the empirical distribution over samples S. we use {) to denote (f The goal of fair classification, given fairness metric Ω and threshold (0, 1]. is to (approximately) solve:
minsez (f) s.t., (D( T
If samples from DD are available, then one could try to solve this program. However, as discussed in Section I we do not have access to the true protected attribute Z, but instead only see a perturbed version, E [p], generated by the following adversary.
H-Hamming model. Given an r) E [0, 1). let A(r) denote the set of all adversaries in the Hammingg model. Any adversary A E A(n) is a randomized algorithm with unbounded computation resources that knows the true distribution DD and the algorithm of the learner L. In this model, the learner L queries A for N E N samples from D exactly once. On receiving the request, A draws N independent samples S == {[x; Mä: 2;) ==)EE[])] from D. then A uses its knowledge of D and L to choose an arbitrary 17- -N samples (n E [0, 1)) and perturb their protected attribute arbitrarily to generate S = [ Di, 2,) h)) Finally, A gives these perturbed samples S to L.
Learning model. Given S and the 17, the learner L. would like to (approximately) solve Program
Definition 3.2 ((5, /eeanning, Given bounds on error E (0,1) and constraint violation v e (0, 1), a learner L is said to (E, -lean a hypothesis class F C {0, 1 x 17 E [0, 1] and confidence ó E (0, 1) if for all
x(pll with perturbation rate
'ee overload the notation f to denote both the classifier as well as its prediction, and the terms, statistical rate and palse-positive rate, refer to both the linear/linear fractional metric g and the resulting faimess metric ft.

---

distributions 'D over X' x {0,1} x [p] and
adversaries A E A(n).
there exists threshold No(s, v, 6. 6.1) E IN such that with probability at least 1- - å over the draw of
N No(e, v, 6, iid samples S ~ D, given ni and the perturbed samples S == A(S), & outputs f E F that satisfies Errp(f) - [fr S & and QD( [ 2 T - V, where f is the optimal solution of Program 2 fi.e.. f == frg Errp(f), s.t., Qp(f) 2 TT.
Given finite number of perturbed samples, Definition 3.2 requires the learner to output classifier that violates the fairness constraints additively by at most v and that has predictive error at most smaller than that of S* with probability at least 1 - 6. Like PAC learning [56). for given hypothesis class F, Definition 3.2 requires the learner to succeed on all distributions DD
Problem 1 (Fair classification with adversarial perturbations). Given a hypothesis class F C {0, 1)xx(p)) xpl, a fairness metric Q a threshold r & [0, 11, perturbation rate E [0, 1}, and perturbed samples S, the goal is to (e.v)-learn F for small E, V E (0, 1).
4 Theoretical results
In this section, we present our results on learning fair classifiers under the n--Hamming model. Our optimization framework (Program (Flernte) is a careful modification of Program (2). The main difficulty is that, unlike Program 2). it only has access to the perturbed samples S. and the ratio of classifier's 's fairness with respect to the true distribution D and with respect to S can be arbitrarily small (see Example A.27 in Supplementary Material A.5). To overcome this, our framework ensures that all feasible classifiers are "stable" (Definition 4.7) Then, as mentioned in Section imposing the fairness constraint S guarantees (approximate) fairness on the true distribution D. The accuracy guarantee follows by ensuring that the optimal solution of Program (2), f E F. is feasible for our framework. To ensure this, we require Assumption [ that also appeared in [1].
Assumption 1. There is a known constant À > 0 such that minre(p] (frpE(""). 2= 42
can be shown that this assumption implies that À is also a lower bound on the performances ai (i()),..... 4p (f*) that depend on & and E', We expect À to be non-vanishing positive constant in applications. For example, y statistical rate, the minority protected group makes at least 20% of the population (i.e., min Pro|Z E] 2 0.2), and for all & E [p]. Pr[f* 1 Z l 1/2, then 2 0.1, In practice, is not known exactly, but it can be set based on the context (c.g., see Section and [4).. We show that Assumption D is necessary for the 17- Haamming model (see Theorem 4.4
Definition 4.1 (Error-tolerant program). Given fairness metric Ω and corresponding events & and E' (as in Definition 3.1, a perturbation rate n E [0, 1), and constants X, A E (0, 1). we define the error-tolerant program for perturbed samples S, whose empirical distribution is D, as
minser Efrz(f):
(EnrTolerant) (3)
1 (1- (1-0+
s.t., 2)
(4)
I+ (+
AéE (p). Pro (8)1))))))))) 1
(5)
acts as a relaxation parameter in Program EEr Tolerantt which can be fixed in terms of the Equation ensures all feasible classifiers satisfy fairness constraints with respect to the perturbed samples S. Equation 5 ensures that all feasible classifiers are (1 ((1/)))-stabe
other parameters; see Theorem 4.3
(see Definition 4.7p. As mentioned Section I this suffices ensure that all feasible classifiers are fair with respect to S. Finally, to ensure the accuracy guarantee the thresholds in the RHS of Equations 4 and (5) are carefully tuned to ensure that f* feasible for Program [Err Toleratt) see Lemma 4.9 We refer the reader to the proof overview of Theorem 4.3 at the end of this section for further discussion of Program (Enr'ooerant)
Before presenting our result we require the definition of the Vapnik-CCheronenkiss (VC) dimension.
Definition 4.2. Given a finite set A, define the collection of subsets FA := {aa E A A f(a) = =1} F). We say that F shatters set B if Frl = Bl The VC dimension F,, VC(F) E N, the largest integer such that there exists set C of size VC(F) that is shattered by F.
5

---

Our first result bounds the accuracy and faimess of an optimal solution fET of Program (Err Tolerant) for any hypothesis class F with a finite VC dimension using O(VC(F)) samples.
Theorem 4.3 (Main result). Suppose Assumption holds with constant X >> 0 and F. has VC dimension d E N. Then, for all perturbation rates 1| E (0, fairness thresholds t E (0, 11, bounds on error > 2n and constraint violation v >> 8/7/(x (x-2),,, and confidence parumeters 5 E (0, 1) with probability at least 1 - 6, the optimal solution FET E F of Pregram
(arraam(EErroreeee (EryTolerant) with parameters X, and A == O (min { 2n, S47/(x-20) À 2n}) ). and N poly d. 1/2, log(r/6)) perturbed samples from the 17- n-Hamminn model satisfies EIrp(fET)
Errp [)= S E and lt (fET) 2 T
Thus, Theorem 4.3 shows that any procedure that outputs SET: given with sufficiently large number of perturbed samples, (c, v)-learns F for any > 2nj and = (((77)/)). Theorem 4.3 can be extended to provably satisfy multiple fineao-fractiona metrics (at the same time) and work for multiple non-binary protected attributes; see Theorem [.2 in Supplementary Material
Moreover,
Theorem 4.3 also holds for the Nasty Sample Noise model. The proof of this result is implicit in the proof of Theorem 4.3] we present the details in Supplementary Material A...5] Finally, Ooogram(Erroonn
Program (Err Tolerant) only requires an estimate of one parameter, A. (Since r) is known, is fixed by the user, and A can be set in terms of the other parameters.) If for each & E [p]. we also have estimates of X Prp [E()", E' (f*) Z f and " == Pro(E"(f"), Z f), then information to "tighten" Program (Err Tolerattt to the following program:
use this
minser
ErT Errp(f),
(EnrTolerant+)) (6)
8.1., (( :
4 E [p]. Pro (E()) =
-
where the scaling parameter & E [0, 1] is the solution of the following optimization program
1 - m// ne/>> de
1 + (T mx)/
min min 711 T1-92 20 E.k[pp] + (nk n
S.L.,
Σ Insm A. (7) EE(P)
1 1+ n/>x
If the classifiers in F do not the protected attributes for prediction, then we can show that
Program Tolerant+) a fairness guarantee of (1 -)= Anr/(2-2n) (which is always smaller than
89r/(x-20) and an accuracy guarantee of 2n/. We prove this result in Supplementary Material B.2
Thus, in applications where one can estimate Ai..... X, and 71,---, 7pp Program (En Tolerrre
offers better fairness guarantee than Program (EnTTolerant) (up to constants).
The proof of Theorem 4.3 appears in Supplementary Material A.I
As for computing fET, note that in general, Program (Err Tolerant) is a nonconvex optimization problem. our simulations, we use the standard solver SLSQP in SciPy (57) to heuristically find fET; see Supplementary Material E. Theoretically, for any arbitrarily small a > O, the techniques from [3] can be used to find an f E that has the optimal objective value for Program (oggram[Errrian (Fleraal)rat)) and that additively violates its fairness constraint (4) by at most a by solving set of (()(A))) convex programs; details appear in Supplementary Material C
Impossibility results. We now present results complementing the guarantees of Theorem 4.3
Theorem 4.4 (No algorithm can guarantee high accuracy and fairness without Assumption I.. For all perturbation rates E (0, 1), thresholds E (1/2, confidence parameters ő E [0, 1/2), and bounds on the error e E [0, 1/2) and constraint violation E [0, 1/2), if the fairness metric is statistical rate, then it impossible to (E, vl-aar any hypothesis class S {0, 1
2'x ip) that shatters a set of 6 points of the form {IA TB, mc } x [] C X x [p) for some distinct A, BB, DC E X.
Suppose that - 0.8, say encode the 80% Then, Theorem 4.4 shows that for any 1) any F satisfying the condition in Theorem |.4 is not (E, velemmalee for any & < 1/2 and v < -- 1/2 = 3/10. Intuitively, the condition on J avoids "simple" hypothesis classes. is similar the conditions considered by works on PAC learning with adversarial perturbations [3] and holds for common hypothesis classes such as decision-trees and SVMs (Remark AA28 in Supplementary Material A.5 Thus, even if is vanishingly small, without additional assumptions, any F satisfying mild assumptions is not (c, ve)llaanabll for any & < 1/2 and v < 3/10, justifying Assumption 1 The proof of Theorem 4.4 appears in Supplementary Material A.2
Theorem 4.5 (Fairness guarantee of Theorem 4.3 optimal up to a constant factor). For all perturbation rates 7) e (0, 1], confidence parameter 6 [0, 1/2), and a (known) constant X E 3/4].

---

if the fairness metric is statistical rate and r = 1, then given the promise that Assumption hools
with constant X. for any bounds E < 1/4-2n/s 2n/s and v < n/(20x]- (1-40(11))))))) - (1 jx²) is impossible
to (e, -leam any hypothesis class F C {0, (0,1] that shatters a set of 10 points of the form (B,, IC; DD σF} [2] C X x for some distinct BB, IE E X.
Suppose that À 1/8 and 1) < 1/2, then Theorem 4.5 shows that for any 17 > O, any learner L that has a faimess guarantee V < 1/(20A) - O(v'/x²) must have a poor error bound, of at least e 2 1/1- 1//s/ 2 1/20, to (e)aar any F that satisfies a mild assumption. When 7/> is small, this shows that any learner with a fairness guarantee v = o(*/A) must have an error guarantee at least 1/4 - 2n/3 >>>>>>>>>>>> 21j. Thus, Theorem 4.5 shows that one cannot improve the fairness guarantee in Theorem 4.3 by more than a constant amount without deteriorating the error guarantee from 2n to 1/4- 1 Like Theorem 4.4] the condition on F in Theorem 4.5 avoids "simple" hypothesis classes and holds for common hypothesis (Remark A..88 in Supplementary Material A.5). Finally, complementing our accuracy guarantee, we prove that for any e < 1/. no algorithm can (e. -lerr any hypothesis classes F satisfying mild assumptions (Theorem A.21 in Supplementary Material A.4);
its proof appears in Supplementary Material A.4 Thus, the accuracy guarantee in Theorem 4.5 is
optimal up to a factor of 2. The proof of Theorem 4.5 appears in Supplementary Material A.3
Proof overview of Theorem 4.3 We explain the key ideas behind Program (EnrTolerant) and how they connect with the proof of Theorem 4.3 Our goal is to construct error-tolerane constraints using perturbed samples S such that the classifier fET, that has the smallest error on S subject to satisfying these constraints, has accuracy 21-close to that of f and that additively violates the fairness constraints by at most (1/2)..
Step 1: Lower bound on the accuracy of SET- This step relies on Lemma 4.6
Lemma 4.6. For any bounded function g: {0, (0, x [p] 1). 6, A E (0, and adversaries A E A(n). given N = =poly(//,, VC(F), log 1/6) true samples S ~ D and corresponding perturbed
samples A(S)= = (11,11 Vi. 2,) 2,)3)x( [EE[M]. with probability at least 1 8, it holds that
VfEF, N EIEIN of 2), yt, 2,) EXx,Y,2)= (f Z). Y. 2)] S
The proof of 4.6 because the 7--Hamming model perturbs at most - samples. Let be the 0-1 loss (i.e., G(V. y, 2) = N
from generalization bounds for bounded functions (e.g., see 554 and
I [ F y)), then for all f E F, Lemma shows that the error of f on samples drawn from D and samples in S are close: [frrp(f) Err(f. S) < A + n. Thus, intuitively, minimizing Err (f. S) could be a good strategy minimize Erro()). Then, if f is feasible for Program (Enroolerant we can bound the error of SET: Since fET is optimal for Program [oleaalerant]] its error on S is at most the error of f S. Using this and applying Lemma 4.6 we get that
Exrp (fET) S Sir(fET,SS) + 77 A < ErT(J", S) + 17 A S Errp(f*) + 2(1 + A). (8) Step 2: Lower bound on the fairness of fET. One could try to bound the faimess of FET using the same approach as Step 1. i.e. show that for all f E F: [Stpff) - 2(f. S) < O11/2). Then ensuring that f has a high fairness on S implies that it also has high fairness on S (up to an O(7/x) factor). However, such bound does not hold for any F satisfying mild assumptions (see Example A.27]. The first idea is to prove a similar (in fact, stronger multiplicative) bound on a specifically chosen subset of F (consisting of "stable" classifiers). Toward this, we define:
Definition 4.7. A classifier f E F is said to be s-stable for fairness metric Q, for all adversaries A E A(T) and confidence parameters ō (0, 1), given polylog( (1/8) samples S ~ D, with probability at least - 5, it holds that Ro(f)/a(t E [s, 1/s), where S == A(S).
If an s-stable classifier f has fairness T on S, then it has a fairness at least T s on D with high probability. Thus, if we have a condition such that any feasible f E F satisfying this condition is s-stable, then any classifier satisfying this condition and the fairness constraint, ()( 2 7/s, must have a fairness least + on D with high probability. The key idea is coming up such constraints.
Lemma 4.8. Any classifier f E F that satisfies minse Pro [&()) 2 = A 2 A A, (1-0+A)/A 2 for fairness metric Qt (defined by events E and E').
Step 3: Requirements for the error-tolerant program. Building on Steps I and 2, we prove:
Lemma 4.9. If the following conditions hold then, Errp (fer) FFrD(f") S 2n and Do > T - O(n/x): (CI) f is feasible for Program ( (ErrTolerant) and all f F feasible for Program (Er. Tooeeantt) are (C2) s-stable for 1 - O(%/x), and (C3) satisfy Q(f,S) S) 2 T (1 O(1/x)).
7

---

Thus, it suffices to find error- arror-tolerant constraints that satisfy conditions (CI) to (C3). Condition (C3)
can be satisfied by adding the constraint O)., 2 r', for T' ='= = (1/x)) From Lemma 4.8 condition (C2) follows by using the constraint in minge[p] Pro (E(f),E'()), 2 - 2 X, for X
(A). It remains to pick T' and X such that condition (CI) also holds. The tension in setting r' and X that if they are too large then condition (C1) does not hold, and if they are too small, then conditions
(C2) and (C3) do not hold. In the proof we show that r' == 7 - (1+(++A/
A1/+- 2 and X = À 17 - A
suffice to satisfy conditions (C1) (C3) (this is where we use Assumption
Overall the main technical idea is to identify the notion of s-stable classifiers and sufficient conditions for classifier to be s-stable; combining these conditions with the fairness constraints on S, ensures that SET has high fairness on S, and carefully tuning the thresholds so that f is likely to be feasible ensurres
for Program (ErrTolerant) ensures that fET has an accuracy close f
Proof overviews of Theorems 4.4 and 4.5 Our proofs are inspired by (39 Theorem 1] and Theorem 1] which consider PAC learning with adversarial corruptions. In both Theorems and 4.5 for some E, V/ E [0. 1]. the goal is to show that given samples perturbed by an 17-Hamming adversary, under some additional assumptions, no learner L can output classifier that has accuracy e-close to the accuracy of f and that additively violates the faimess constraints by at most v. Say a classifier I F is "good" if it satisfies these required guarantees. The approach is construct two more distributions 1 D2,..., 'Din that satisfy the following conditions: (C1) For any E, k, given a iid draw S from Dr, v--Haminng adversary can add perturbations such that with high probability S is distributed according to iid samples from Dz- Thus L. who only sees S, with high probability, cannot identify the original distribution of S and is forced output classifier that is good for all Di,..., "i....,,...... Dm for all D,, 1...... Dm and for each D, (i E [m], there is at least one good classifier f. E F. (The latter-half ensures that the fairness and accuracy requirements are not vacuously satisfied.) Thus, for every there is distribution in Di...., , Dm for which L outputs a bad classifier. (Note that even if the learner is randomized, it must fail with probability at least 1/m.) Finally, the assumptions on F ensure that condition (C2) is satisfiable. For instance, if F has less than m hypothesis, then condition (C2) cannot be satisfied.
The next condition ensures that this is not possible. (C2) No classifier f E F is good
The key idea in the proofs is to come up with distributions satisfying the above conditions. 39 follow the same outline in the context of PAC learning, however, as we also consider fairness constraints, our constructions end up being very different from their constructions. Our constructions are specific to the statistical rate fairness metric. However, one can still apply the general approach outlined above to other fairness metrics by constructing a suitable set of distributions. Full details appear in Supplementary Materials A.2 and A.3
Empirical results
We implement our approach using the logistic loss function with linear classifiers and evaluate its performance on real world and synthetic data.
Metries and baselines. The selection of an appropriate fairness metric context-dependent and beyond the scope of this work (55]; ; for illustrative purposes we (arbitrarily) consider the statistical rate (SR) and compare an implementation of our framework (Program (Err (oleraatt)t))) Trr-Tol, with state- of-the-art art fair classification frameworks for statistical rate under stochastic perturbations: LMZV (4] and CHKV [1]. LMZV and CHKV take parameters ,τ, 7 E [0. 1] as input; these parameters control the desired fairness, where decreasing òr. or increasing 7 increases the desired fairness. We also compare against KL 44), which controls for true-positive rate (TPR) in the presence of a Malicious adversary, and A AKM 6 that is the processccssing method of (32) and controls for equalized-odds fairness constraints. We also compare against the optimal unconstrained classifier, Uncons; this is the same as (1I's ss algorithm for PAC-Icarnig in the Nasty Sample Noise Model without fairness constraints. We provide additional comparisons using our framework with false-positive rate as the fairness metric with additional baselines and using the Adult data 23 in Supplementary Material B
Implementation details. We use a randomly generated 70-30 train (S) test (T) split of the data, and generate the perturbed data S from S for (known) perturbation rate 17. We train each algorithm on S, and report the accuracy (acc) and statistical rate (SR) of the output classifiers on the (unperturbed) test data T. Err-Tol is given the perturbation rate 7) and uses the SLSQP solver in SciPy [57] to solve Program ) To advantage the baselines our comparison, we provide them with even more information as needed by their approaches: LMZV and CHKV are given group-specinn pertur-
8

---

Table I:
Simulation on synthetic data: We run CHKV and Err-Tol with r = 0.8 on synthetic data and report their average accuracy (acc) and statistical rate (SR) with standard deviation in parentheses. The result shows that prior approaches can fail to satisfy their guarantees under the ry Ha-Hmminng model.
acc (1p=0%)
SR (17=0%)
acc (11=%)
SR (7)=3%
acc (1755%)
SR (11=5%)
Unconstrained
1.00 (.001)
.799 (.001)
1.00 (.000)
.799 (.002)
1.00 (.001)
.800 (.001)
CHKV (7=.8)
1.00 (.001)
800 (.002)
.859 (.143)
.787 (.015)
.799 (.139)
.795 (.049)
Err-Tol (T=.8) .855 (.065)
.800 (.001)
1.00 (.001)
.799 (.002)
.999 (.002)
.799 (.004)
bation rates: for each / E [p]. T = PrD(2 + Z | Z 2]. and KL is given 7j and for each & E [p], the probability PrplZ = e,Y = I]: where D is the empirical distribution of S. Err-Tol implements Program (Erroolerant++
requires estimates of A and "/e for all & E [p]. As a heuristic, we set Ve = X ProlZ Z = E]. where D is the empirical distribution of S. We find that these estimates suffice, and expect that a more refined approach would only improve the performance of Err-Tol.
Adversaries. We consider two g--Hamming adversaries (which we call ATN and ApN); each one computes the "optimal fair classifier" f", which has the highest accuracy (on S) subject to having statistical rate at least 7 on S. ATN considers the set of all true negatives of f* that have protected attribute Z = 1, selects the - |S| samples that are furthest from the decision boundary of f", and perturbs their protected attribute to Z = 2. AFN is similar, except that it considers the set of false negatives of f*. Both adversaries try to increase the performance of f on Z = 1 in S by removing the samples that f predicts as negative; thus, increasing f* statistical rate. The adversary's 's hope is that choosing samples far from the decision boundary would (falsely) give the appearance of a high statistical rate on S. This would make a fair classification framework output unfair classifiers with higher accuracy. Note that these are not intended to be "worst-case" adversaries; as Err-Tol comes with provable guarantees, expect it to perform well against other adversaries while other approaches may have even poorer performance.
Simulation on synthetic data. We first show empirically that perturbations by the 17- g--mmiingg adversary can be prohibitively disruptive for methods that attempt to correct for stochastic noise. We consider synthetic data with 1,000 samples from two equally-sized protected groups; each sample has a binary protected attribute, two continuous features I T2 E R, and a binary label. Conditioned on the protected attribute, (#1, 222) are independent draws from a mixture of 2D Gaussians (see Figure 4. This distribution and the labels are such that a) one group has a higher likelihood of a positive label than the other, and b) Uncons has near- near-perfect accuracy (> 99%) and statistical rate of 0.8 on S. Similar to Uncons, we consider a fairness constraint of 7 = 0.8. Thus, in the absence of noise, this is an "easy case:" where Uncons satisfies the fairness constraints. We generate S using ATN, and compare against CHKV, which was developed for correcting stochastic perturbations
Results. The fairness and statistical rate averaged over 50 iterations are reported in Table as func- tion of the perturbation 77. 7) = 0, both CHKV and Err-Tol nearly-satisfy the fairness constraint (SR > 0.79) and have a near-perfect accuracy (acc 2 0.98). However, 1j increases, while CHKV retains the same statistical rate (~ 0.8), it loses a significant amount of accuracy (~ 20%). In contrast, Err-Tol has high accuracy and fairness (ace 0.99 and SR 2 0.79) for all n considered. Hence, this shows that stochastic approaches may fail to satisfy their guarantees under the 17- n--aamiig model.
Simulations on real-world data. In this simulation, we show that our framework can outperform each baseline with respect to the accuracy-fairnes trade-off under perturbations from the adversaries we consider, and does not under-perform compared to baselines under perturbations from either adversary. The COMPAS data in [9] contains 6, 122 samples with 10 binary features and a label that is I if the individual did not recidivate and O otherwise; the statistical rate of Uncons on COMPAS is 0.78. We take gender (coded as binary) as the protected attribute, and set the fairness constraint on the statistical rate to be 7 = 0.9 for Err-Tol and all baselines. We consider both adversaries ATN and ApN, and a perturbation rate of r = 3.5%, as 3.5% is roughly the smallest value for 1) necessary to ensure that the optimal fair classifier f for = 0.9 (on S) has statistical rate less than 0.78 on S.
Results. The accuracy and statistical rate (SR) of Err-Tol and baselines for r E |0.7, 1] and òr, E [0, 0.1] and averaged over 100 iterations are reported in Figure For both adversaries, Err-Tol attains a better statistical rate than the unconstrained classifier (Uncons) for small tra in accuracy. For adversary ATN (Figure I a)), Uncons has statistical rate (0.80) and accuracy (0.67). In contrast,
"We also attempted to compare against AKM. KL, and LMZV. But they did not converge to f even on the unperturbed synthetic data, and hence, did not include these results as it would be an unfair comparison.

---

Unconstrained
KL
AKM
En-Tol (This work)
CHKV LMZV
0.70
0.70
Accuracy
0.65
Accuracy
0.65
0.60
0.60
0.55
0.58
0.707
0.85
0.90
0.95
1.00
8.70
0.55
0.90
0.95
1.00
(less fair)
Statistical rate
(more (air)
(less fair)
Statistical rate
(more (morefair)
(a) ATN
(b) AFN
Figure 1: Simulations on COMPAS data: Perturbed data is generated using adversary ATN (a) and APN (b) as described in Section 5 with r = 3.5%. All algorithms are run on the perturbed data varying the fairness parameters (T E [0.7, 1 and og E [0. 0.1]). The y-axis depicts accuracy and the r-axis depicts statistical rate (SR); both values are computed over the unperturbed test set. We observe that for both adversaries our approach Err-Tol, attains a better fairness than the unconstrained classifier with natural trade-off in accuracy. Further. Err-Tol achieves a better bainess-accurann trade-off' than each baseline on at least one of (a) or (b). Error bars represent the standard error of the mean.
Err-Tol achieves high statistical rate (0.92) with a trade-off in accuracy (0.60). In comparison, AKM has a higher accuracy (0.65) but lower statistical rate (0.87), and other baselines have an even lower statistical rate (S 0.84) with accuracy comparable to AKM. For adversary ApN (Figure lb)). Uncons has statistical rate (0.80) and accuracy (0.67), while Err-To has a significantly higher SR (0.91) and accuracy (0.61). This significantly outperforms AKM which has statistical rate (0.83) and accuracy (0.58). LMZV achieves the highest statistical rate (0.97) with a natural reduction accuracy to (0.57). In this case, Err-Tol Tol has similar accuracy statistical rate off as LMZV, but achieves lower maximum statistical rate (0.91). Meanwhile, Err-To Tol has a significantly higher statistical rate trade-off than CHKV at the same accuracy. We further evaluate our framework under stochastic perturbations in Supplementary Material (sperrial(((eeciffcccllll against the perturbation model of [14) and observe similar statistical rate and accuracy trade-offss as approaches [14 44 tailored for stochastic perturbations.
Remark 5.1 (Range of fairness parameters in the simulation). Among baselines, AKM, KI, and Uncons do not take the desired-fairness value as input, they appear as points in Figure 7 For all other methods (CHKV, Err-Tol, and LMZN), we vary the fairness parameters starting from the tightest constraints (i.e.. T 1 and ,n = 0) and relax the constraints until all algorithms'' achieved statistical rate matches the achieved statistical rate of the unconstrained classifier (this happens around T 0.7 and òG 0.1). We do not relax the fairness parameters further because the resulting problem is equivalent to the unconstrained classification problem. (This is because the unconstrained classifier, which has the highest accuracy, satisfies the fairness constraints for T S 0.7 and & 2 0.1).
Limitations and conclusion
This work extends fair classification to wealdworld settings where perturbations in the protected attributes may be correlated or affect arbitrary subsets of samples. We consider the 17- Ha-mminng model and give a framework that outputs classifiers with provable guarantees on both faimeess and accuracy; this framework works for categorical protected attributes and the class of fairness metrics. We show near-tightness of our framework's guarantee and extend it to the Nasty Sample Noise model, which can perturb both labels and features. Empirically, classifiers produced by our framework achieve high fairness at small cost to accuracy and outperform existing approaches.
Compared to existing frameworks for fair classification with stochastic perturbations, our framework requires less information about the perturbations. That said, in few applications, e.g., the randomized response procedure [60), where the perturbations are independent across samples and identically distributed according to a known distribution, frameworks for fair classification with stochastic perturbations can perform better. Further, like existing frameworks, our framework's 's efficacy will depend on an appropriate choice of parameters; e.g., overly conservative À can decrease accuracy and an optimistic Ả can decrease fairness. A careful assessment both pre- and post-deployment would be important avoid negative social implications in a misguided attempt do good [45].
Finally, we note that discrimination a systematic problem and our work only addresses one part of it; this work would be effective as one piece of a broader approach to mitigate and rectify biases.
Acknowledgements. This research was supported in part by an NSF CAREER Award (IIS- 2045951), a J.P. Morgan Faculty Award, and an AWS MLRA Award.
10

---

References
[1] Alekh Agarwal, Alina Beygelzimer, Miroslav Dudík, John Langford, and Hanna M. Wallach. Reductions Approach to Fair Classification. In ICML, volume 80 of Proceedings of Machine Learning Research, pages 60-69, PMLR, 2018.
[2] Dana Angluin and Philip D. Laird. Learning from noisy examples. Mach. Learn., 2(4):343-370, 1987.
[3] Julia Angwin, Jeff Larson, Surya Mattu, and Lauren Kirchner. COMPAS recidivism risk score data and analysis, 2016.
[4] Peter Auer. Learning with Malicious Noise, pages 1086-1089. Springer New York, New York, NY, 2016.
[5] Peter Auer and Nicolo Desa-Bianchi. On-line learning with malicious noise and the closure algorithm. Annals of mathematics and artificial intelligence, 23(1):83-99, 1998.
[6] Pranjal Awasthi, Matthäus Kleindessner, and Jamie Morgenstern. Equalized odds postprocessing under imperfect group information. In International Conference on Artificial Intelligence and Statistics, pages 1770-1780. PMLR, 2020.
[7] Eugene Bagdasaryan, Omid Poursaeed, and Vitaly Shmatikov. Differential privacy has disparate impact on model accuracy. Advances in Neural Information Processing Systems, 32:15479- 15488, 2019.
[8] Solon Barocas, Moritz Hardt, and Arvind Narayanan. Fairness and Machine Learning. fairml- book.org, 2019. htttp://ww. fai book.
[9] Rachel K. E. Bellamy, Kuntal Dey, Michael Hind, Samuel C. Hoffman, Stephanie Houde, Kalapriya Kannan, Pranay Lohia, Jacquelyn Martino, Sameep Mehta, Aleksandra Mojsilovic, Seema Nagar, Karthikeyan Natesan Ramamurthy, John Richards, Diptikalyan Saha, Prasanna Sattigeri, Moninder Singh, Kush R. Varshney, and Yunfeng Zhang. AT Fairness 360: An extensible toolkit for detecting, understanding, and mitigating unwanted algorithmic bias, October 2018.
[10] Avrim Blum and Kevin Stangl. Recovering from biased data: Can fairness constraints improve accuracy? In FORC, volume 156 of L/Plcs, pages 3:13:: Schloss Dagstuhl Leibniz-Zentrum für Informatik, 2020.
[11] Nader H Bshouty, Nadav Eiron, and Eyal Kushilevitz. PAC learning with nasty noise. Theoreti- cal Computer Science, 288(2):255-275, 2002.
[12] Joy Buolamwini and Timnit Gebru. Gender shades: Intersectional accuracy disparities in commercial gender classification. In FAT, volume 81 of Proceedings of Machine Learning Research, pages 77-91. PMLR, 2018.
[13] L. Elisa Celis, Lingxiao Huang, Vijay Keswani, and Nisheeth K. Vishnoi. Classification with Fairness Constraints: A Meta-Algorithm with Provable Guarantees. In FAT, pages 319-328. ACM, 2019.
[14] L. Elisa Celis, Lingxiao Huang, Vijay Keswani, and Nisheeth K. Vishnoi. Fair classification with noisy protected attributes. In ICML, volume 120 of Proceedings of Machine Learning Research. PMLR, 2021.
[15] Nicolo Cesa-Bianchi, Eli Dichterman, Paul Fischer, Eli Shamir, and Hans Ulrich Simon. Sample-efficient strategies for learning in the presence of noise. Journal of the ACM (JACM), (6(5):684-719, 1999.
[16] Jiahao Chen, Nathan Kallus, Xiaojie Mao, Geoffry Svacha, and Madeleine Udell. Fairness under unawareness: Assessing disparity when protected class is unobserved. In FAT, pages 339-348. ACM, 2019.
[17] Alexandra Chouldechova. Fair prediction with disparate impact: study of bias in recidivism prediction instruments. Big data, 5(2):153-163, 2017.

---

[18] Andrew J Coldman, Terry Braun, and Richard P Gallagher. The classification of ethnic status using name information. Journal of Epidemiology Community Health, 42(():3900 1988.
[19] Amanda Coston, Karthikeyan Natesan Ramamurthy, Dennis Wei, Kush R. Varshney, Skyler Speakman, Zairah Mustahsan, and Supriyo Chakraborty. Fair transfer learning with missing protected attributes. In AIES, pages 91-98. ACM, 2019.
[20] N.R. Council, D.B.S.S. Education, C.N. Statistics, P.D.C.R.E. Data, E. Perrin, and M.V. Ploeg. Eliminating Health Disparities: Measurement and Data Needs. National Academies Press, 2004.
[21] Bill Dedman. The color of money. Atlanta Journal- Coimaaa--Cnstituiionn pages 1-4, 1988.
[22] Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai L., and Li Fei-Fei. Imagenet: A large- scale hierarchical image database. 2009 IEEE conference on computer vision and pattern recognition, pages 248-255 Icce, 2009.
[23] Dua Dheeru and E Karra Taniskidou. UCI machine learning repository, 2017. http://archiv
e. iis.cs uci. edu/ml
[24] Cynthia Dwork, Nicole Immorlica, Adam Tauman Kalai, and Mark D. M. Leiserson. Decoupled classifiers for group-fair and efficient machine learning. In FAT, volume 81 of Proceedings of Machine Learning Research, pages 119-133. PMLR, 2018.
[25] Michael Feldman, Sorelle A. Friedler, John Moeller, Carlos Scheidegger, and Suresh Venkata- subramanian. Certifying and removing disparate impact. In KDD, pages 259-268. ACM, ACM, 2015.
[26] Benjamin Fish, Jeremy Kun, and Ádám D Lelkes. A confidence-based approach for balancing fairness and accuracy. In Proceedings of the 2016 SIAM International Conference on Data Mining, pages 442-152. SIAM, 2016.
[27] Naman Goel, Mohammad Yaghini, and Boi Faltings. Non-discriminatory machine learning through convex fairness criteria. In AAAI 2018, 2018.
[28] Gabriel Goh, Andrew Cotter, Maya R. Gupta, and Michael P. Friedlander. Satisfying real-world goals with dataset constraints. In Advances in Neural Information Processing Systems 29: Annual Conference on Neural Information Processing Systems 2016, December 5-10, 2016, Barcelona, Spain, pages 2415 1221,222232222 2016.
[29] Ian J. Goodfellow, Jonathon Shlens, and Christian Szegedy. Explaining and harnessing adver- sarial examples. In ICLR (Poster), 2015.
[30] Maya R. Gupta, Andrew Cotter, Mahdi Milani Fard, and Serena Wang. Proxy fairness. CoRR, abs/1 806. 1212, 2018.
[31] Richard W Hamming, Error detecting and error correcting codes. The Bell system technical journal, 1660 1950.
[32] Moritz Hardt, Eric Price, and Nati Srebro. Equality of opportunity in supervised learning. In Daniel D. Lee, Masashi Sugiyama, Ulrike von Luxburg, Isabelle Guyon, and Roman Garnett, editors, Advances in Neural Information Processing Systems 29: Annual Conference on Neural Information Processing Systems 2016, December 5-10, 2016, Barcelona, Spain, pages 3315- 3323, 2016.
[33] Tatsunori B. Hashimoto, Megha Srivastava, Hongseok Namkoong, and Percy Liang. Fairness without demographics in repeated loss minimization. In ICML, volume 80 of Proceedings of Machine Learning Research, pages 1934-1943. PMLR, 2018
[34] Mara Hvistendahl. Can "predictive policing" prevent crime before it happens. Science Magazine, 28, 2016.
[35] Vidit Jain and Erik Learned-Miller. Fddb: A benchmark for face detection in unconstrained settings. Technical Report
University of Massachusetts, Amherst, 2010.
12

---

[36] Nathan Kallus, Xiaojie Mao, and Angela Zhou. Assessing algorithmic fairesss with unobserved protected class using data combination. FAT*, page 110. ACM, 2020.
[37] Faisal Kamiran and Toon Calders. Classifying without discriminating. In 2nd International Conference on Computer, Control and Communication, 2009, IC4 2009., pages 1-6. IEEE, 2009.
[38] Faisal Kamiran and Toon Calders. Data preprocessing techniques for classification without discrimination. Knowledge and Information Systems, 33(1):1-33, Oct 2012.
[39] Michael J. Kearns and Ming Li. Learning in the presence of malicious errors. SIAM J. Comput., 22(4):807-88) 837, 1993.
[40] Nikola Konstantinov and Christoph H. Lampert. Fairness-awaee learning from corrupted data. CoRR, abs/2102.06004, 2021.
[41] D. Kraft. software package for sequential quadratic programming. Deutsche Forschungs- und Versuchsanstalt für Luft- und Raumfahrt Köln: Forschungsbericht Wiss. Berichtswesen d. DFVLR, 1988.
[42] Emmanouil Krasanakis, Eleftherios pnyyrmitros-Xiouufi Symeon Papadopoulos, and Yiannis Kompatsiaris. Adaptive sensitive reweighting mitigate bias fairness-aware classification. In Proceedings of the 2018 World Wide Web Conference on World Wide Web, WWW 2018, Lyon, France, April 23-27, 2018. International World Wide Web Conferences Steering Committee, 2018.
[43] Preethi Lahoti, Alex Beutel, Jilin Chen, Kang Lee, Flavien Prost, Nithum Thain, Xuezhi Wang, and Ed Chi. Fairness without demographics through adversarially reweighted learning. In NeurlPS, 2020.
[44] Alexandre Louis Lamy and Ziyuan Zhong. Noise-tolerant fair classification. NeurlPS, pages 994-305, 2019.
[45] Lydia T Liu, Sarah Dean, Esther Rolf, Max Simchowitz, and Moritz Hardt. Delayed impact of fair machine learning. In International Conference on Machine Learning, pages 3150-3158. PMLR, 2018
[46] Elizabeth Luh. Not so black and white: Uncovering racial bias from systematically misreported trooper reports. Available at SSRN 3357063, 2019.
[47] Binh Thanh Luong, Salvatore Ruggieri, and Franco Turini. k-nn as an implementation of situation testing for discrimination discovery and prevention. In KDD 2011, pages 502-510. ACM, 2011.
[48]
Aditya Krishna Menon and Robert C. Williamson. The cost of fairness in binary classification. In FAT 2018, pages 107-118, 2018
[49] Vidya Muthukumar, Tejaswini Pedapati, Nalini Ratha, Prasanna Sattigeri, Chai-Wah Wu, Brian Kingsbury, Abhishek Kumar, Samuel Thomas, Aleksandra Mojsilovic, and Kush R Varshney. Understanding unequal gender classification accuracy from face images. arXiv preprint arXiv: 2018.
[50] Northpointe, Compas risk and need assessment systems. lttp://www.nrrbppineenen om/ 1iilles/dovm1oads/FAA00
pdf 2012.
[51] Geoff Pleiss. Manish Raghavan, Felix Wu, Jon M. Kleinberg, and Kilian Q. Weinberger. On fairness and calibration. In Advances in Neural Information Processing Systems 30: Annual Conference Neural Information Processing Systems 2017, 4-9 December 2017, Long Beach, CA, USA, pages 5684-5693, 2017.
[52] Catherine Saunders, Gary Abel, Anas El Turabi, Faraz Ahmed, and Georgios Lyratzopoulos. Accuracy routinely recorded ethnic group information compared with self-reported ethnicity: Evidence from the english cancer patient experience survey. BMJ open, 3, 06 2013,
13

---

[53] Clayton Scott, Gilles Blanchard, and Gregory Handy. Classification with asymmetric label noise: Consistency and maximal denoising. In Conference on learning theory, pages 489-511. PMLR, 2013.
[54] Shai Shalev-Shwart and Shai Ben-David. Understanding machine learning: From theory to algorithms. Cambridge university press, 2014.
[55] Megha Srivastava, Hoda Heidari, and Andreas Krause. Mathematical notions vs. human perception of faimess: A descriptive approach to fairesss for machine learning. In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pages 2459-2468, 2019.
[56] Leslie G Valiant. theory of the learnable. Communications of the ACM, 27 1984.
[57] Pauli Virtanen, Ralf Gommers, Travis E. Oliphant, Matt Haberland, Tyler Reddy, David Cournapeau, Evgeni Burovski, Pearu Peterson, Warren Weekesser, Jonathan Bright, Stéfan J. van der Walt, Matthew Brett, Joshua Wilson, K. Jarrod Millman, Nikolay Mayorov, Andrew R. J. Nelson, Eric Jones, Robert Kern, Eric Larson, C Carey, ilhan Polat, Yu Feng, Eric W. Moore, Jake VanderPlas, Denis Laxalde, Josef Perktold, Robert Cimrman, Ian Henriksen, E, A. Quintero, Charles R. Harris, Anne M. Archibald, Antônio H. Ribeiro, Fabian Pedregosa, Paul Mulbregt, and SeiPy 1.0 Contributors. SciPy 1.0: Fundamental Algorithms for Scientific Computing in Python. Nature Methods, 17:261-272, 2020.
[58] Jialu Wang, Yang Liu, and Caleb Levy. Fair classification with group-dependent label noise. In FAceT, pages 526-536. ACM, 2021.
[59] Serena Wang, Wenshuo Guo, Harikrishna Narasimhan, Andrew Cotter, Maya Gupta, and Michael I. Jordan. Robust optimization for fairness with noisy protected groups. In NeurIPS, 2020.
[60] Stanley I.. Warner. Randomized response: survey technique for eliminating evasive answer bias. Journal of the American Statistical Association, 60(309):63-69, 1965. PMID: 12261830.
[61] Blake E. Woodworth, Suriya Gunasekar, Mesrob I. Ohannessian, and Nathan Srebro. Learning non-discriminatory predictors. In COLT 2017, pages 1920-1953, 2017.
[62] Muhammad Bilal Zafar, Isabel Valera, Manuel Gomez Rodriguez, and Krishna P Gummadi, Fairness beyond disparate treatment & disparate impact: Learning classification without dis- parate mistreatment. In Proceedings of the 26th International Conference on World Wide Web, pages 1171-1180 International World Wide Web Conferences Steering Committee, 2017.
[63] Muhammad Bilal Zafar, Isabel Valera, Manuel Fairness constraints: Mechanisms for fair classification. In A/STATS, volume 54 of Proceedings of Machine Learning Research, pages 962-970. PMLR, 2017.
and Krishna P. Gummadi.
[64] Richard Zemel, Yu Wu, Kevin Swersky, Toniann Pitassi, and Cynthia Dwork. Learning fair representations. In Proceedings of the 30th International Conference International Conference on Machine Learning- Volume 28, ICML' 13, pages (1-325--I11 I1I-333. JMLR.org. 2013.
[65] Brian Hu Zhang, Blake Lemoine, and Margaret Mitchell. Mitigating unwanted biases with adversarial learning. In Proceedings of the 2018 AAAI/ACM Conference on AI, Ethics, and Society, pages 335-340. ACM, 2018
[66] Xiangxin Zhu and Deva Ramanan. Face detection, pose estimation, and landmark localization in the wild. In 2012 IEEE Conference on Computer Vision and Pattern Recognition, pages 2879-2888 2012.
14


Reviews:
[{"review_id": "ayYOTy7M6nX", "reviewer": "Reviewer_qeE2", "summary": "In this paper, the authors study fair classification in the presence of an adversary who is capable of choosing an arbitrary-fraction of the training samples and arbitrarily perturbing the corresponding protected attributes. Theoretically, the authors propose an optimization framework to learn fair classifiers with provable guarantees on accuracy and fairness in the adversarial settings. Empirically, the authors evaluate the classifiers produced by our framework for statistical rate on real-world and synthetic datasets against different adversaries. \n", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "\nOverall, I think the paper is well written and the theoretical results are solid and impressive. The proposed problem setup is also important and practical. Assumption 1 also sounds reasonable to me. \n\nHowever, there exists some problems in the empirical evaluations. First of all, I think the author should provide more justifications in the synthetic experiments. For example, I think the experiment results would be more convincing if the sizes of the protected group are varied by the authors. Besides, more different values of fairness constraint $\\tau$ would be more convincing. \n\nMoreover, if the authors could add one more dataset in the empirical evaluation, such as the Adult dataset, which has more data instances than COMPAS, the results would be more convincing.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors have described the limitations of the work and discuss the potential negative societal impacts. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "aJGL6EG83yC", "reviewer": "Reviewer_EtYP", "summary": "This work studies learning fair classification under the assumption that an arbitrary eta-fraction of training samples are perturbed on the protected attributes. The authors propose an optimization framework for eta-Hamming model which has the provable guarantees on accuracy and fairness. The experiments with linear models on synthetic and real-world datasets are used to evaluate the proposed approach. ", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Originality: The problem setting of this paper is a bit different from existing ones, that is the eta-fraction of perturbations are arbitrary. The main thought of the techniques seems  inspired by Richard 1950 that has been properly cited.\n\nQuality: I am not knowledgeable enough to check the correctness of every theory result, so I can only basically understand what each theoretical result is used for.  By reading the whole paper, I have the following major concerns:\n1. The authors claim their results extend to the case of perturbing both labels and features. This leads me to think about the connection between the proposed setting and eta-fraction over training sample labels. Is the latter one an alternative assumption for learning fair classifier?\n2. I know targeting the worst-case adversary makes a strict guarantee on theory. However, for a real case the perturbation type is not known. From this view, should expectation formulation is a better choice for the generalization consideration?\n3. I found that eta is a small value in experiments to ensure the optimal fair classifier. For works that are dealing with noisy feature/label, eta might be bigger than used in this work. Back to the setting, when and why is a small proportional perturbations for adversary reasonable?\n\nClarity: The submission is clearly written and well organized. \n\nSignificance: The theoretical results are interesting, while the experimental results seem only comparable. Generally, as the problem setting is not identical with the existing ones,  some modified methods are applied as baselines. But it is fine with me. \n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors have discussed the limitation of their work, but the further explanation about the above concerns are also needed.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4h"}, "extra_text": {}}, {"review_id": "CEO2-iLBMHE", "reviewer": "Reviewer_bYbu", "summary": "This paper presents an optimization framework to learn fair and accurate classifiers in the setting where an adversary can perturb the protected attributes. The contribution is mainly theoretical and focuses on Theorem 4.3, which gives guarantees on fairness and accuracy from a solution to their ErrorTolerant program, along with additional impossibility results (4.4, 4.5) which provide tightness and optimality guarantees for the proposed approach. There are also results from a small set of experiments on one simulated and one real dataset showing that the proposed approach generally outperforms baseline methods under the perturbation model.\n\n**Update**: I have read the author response, and it addresses my concerns. Looking at the other reviews and the responses as well, I will keep my initial rating.", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Overall: In general, while the paper is somewhat dense and covers a lot of ground, I found it to be a solid contribution to a problem of great relevance to the community -- versions of this particular problem has the potential to arise in many applied contexts. The paper is generally well-written and the theoretical contributions are made clear enough. I think that the paper could use some reorganization, but absent an issue with the proofs (which I was only able to briefly review) I think there is a good case for acceptance. Detailed comments are below.\n\nMajor Comments:\n\n* In general, I found the paper difficult to read at times due to the confusing order of presentation. Many terms are used far in advance of their definitions, and the authors refer to definitions (such as 4.7) many pages before they are introduced. I would suggest to introduce all definitions earlier in the paper, in particular, and to introduce the model itself earlier as well. This will make it much easier to assess the contribution and understand what some ambiguous terms (such as \"error\") mean when used in context.\n\n* The prior work section is also particularly difficult to read, since the authors mostly focus on immediately defending their territory relative to prior works. Please clearly describe the contributions of these prior works *separate* from your discussion of how the current work is different from them. \n\nMinor Comments:\n\n* The authors' claims about the fragility of imputation methods on L32 seem to me to assume a very specific imputatoin strategy (namely, one based on deep learning). This is certainly not the case for all imputation strategies, such as mean/mode/constant imputation which are sometimes used in practice. Please clarify your claim, or perhaps soften it.\n\n* I am not sure whether SR is ever actually defined in the paper.\n\n* It isn't clear from my reading how the authors actually find the solution to Program ErrTolerant in practice; it would be useful to comment more on how to solve this problem and give more details regarding complexity of this solution, particularly in the sections with experimental results on actual datasets.\n\nTypos etc.\n\nThere are several minor typos in the paper; I only list a few here.\n\n* L39: the distribution of --> the distributions of\n* L70 -- could \"performance\" simply be error?\n* L80-82 incomplete sentence\n* L103: as measured \\Omega --> as measured by \\Omega", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "1.5"}, "extra_text": {}}, {"review_id": "8fVEDhymcz", "reviewer": "Reviewer_PbrT", "summary": "They consider the problem offFair classification in the adversarially perturbed setting — that is, the adversary gets to choose eta fraction of the sample arbitrarily and change their protected attributes arbitrarily. \n\nThey show an optimization problem that ensures fairness and accuracy guarantees under a mild assumption and show a mild assumption is necessary for those guarantees. \n\nFinally, they have some experiments in which they consider two well thought out adversaries.", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "To my knowledge, this is the first paper that considers fair machine learning with a full adversary that can arbitrarily corrupt the protected attributes of the data unlike previous work that focused on stochastic corrpution. \n\nThe solution that the paper proposes is pretty intuitive and hence, it's very easy to follow. For instance, the overall paper is very clear in its description of the problem and its explanation of the solution/proof techniques (e.g. at the end of section 4). \n\nHowever, the paper only shows an optimization problem that has nice guarantees (Thm 4.3) but doesn't actually show how to solve the optimization problem. More specifically, there isn't a discussion on how to actually solve ErrTolerant regardless of whether it's just a heuristics to solve the problem or an actual algorithm with guarantees. At a glance, the constraints seem convex so one can replace the objective term with a surrogate loss and use any convex optimization approach? In the experiment, it seems that the authors have \"solved\" ErrTolerant, so some discussion on how to solve and how they were solved in the experiment would be helpful.\n\nFinally, the experiments do show to some extent that the proposed method in the paper is better or observe similar performance as other methods. However, I do have some questions:\n\n-For the synthetic dataset set, why are other methods besides CHKV not tried out? Is it because it's hard to tune the parameters of the other algorithms to have a meaningful comparison?\n\n-I think the easiest way to compare fair-accuracy tradeoffs is by drawing out the pareto curve, so is it possible to just try out much larger sets of parameters for all these algorithms to see a bigger pareto curve instead of the current one that seems to concentrate on a small region? \n\nQuestions/Comments on the impossibility results (Thm 4.4, 4.5, and D.1)\n-Are the proofs of the impossibility results specific to SR or can one easily generalize the proofs to other fairness metrics? \n\n-Maybe, because it's hard to parse the sentence in line 265 (when eta/gamma is small ... ), it's not clear to me how Thm 4.5 shows that the constants in Thm 4.3 are tight. It would be helpful to have a couple more sentences showing how they are tight.\n\n-Lastly, how dependent are the proofs of Theorem 4.5 and D.1 on tau=1 which requires the fairness metric is exact for any group? \n\n\n\n\n\nMinor questions/comments:\n\n-Delta = O(blah, blah, blah). Is this supposed to be max with constants hidden? \n\n-definition 4.7 (stability definition) is has not quantified the high probability. \n\n-For adversaries in the Empirical results section A_TN and A_FN, how was f^* obtained? \n\nTypos:\nline 265. It's hard to understand what this sentence is saying because I think it's a run-on sentence?\nline 270: learnable ⇒ learn", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes, the authors have addressed the limitations and potential negative societal impact of their work.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper provides novel theoretical results regarding fair classification in the presence of adversarial perturbations of the training examples, as well as supporting experiments on real world datasets. The reviewers found the problem formulation to be well motivated by application, and they deemed the theoretical results to be sound, novel, and interesting. Therefore, I recommend acceptance of the paper.

Throughout the discussion there are a number of concerns that should be addressed in the next version of the paper, and I strongly encourage the authors to do so. To name a few: (1) definitions and terminology should be defined early and clearly, (2) the additional experiments discussed in the responses should be added to the paper, and (3) the implementation strategy of solving the proposed programs in practice should be described clearly for the paper to be self-contained.
Decision: Accept (Poster)