Fair Classification with Adversarial Perturbations
Year: 2022

Abstract:
We study fair classification in the presence of an omniscient adversary that, given an η, is allowed to choose an arbitrary η-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.

heading: 1 Introduction
text: 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, it is 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, 63, 62, 48, 24, 27, 1, 13]. At a high level, a classifier f is said to be “fair” with respect to a protected attribute Z if it has a similar “performance” with respect to a given metric on different protected groups defined by Z. Given a 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 fairness constraints, these approaches need protected attributes of training data to be known.
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” [18, 36, 16], but this can also introduce errors [12]; further, imputation by machine-learning-based methods is known to be fragile to imperceptible changes in the inputs [29] and to have correlated errors across samples [49]. Perturbations in 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 (NeurIPS 2021).
independent of the labels (and of each other). [14] consider the setting where each sample’s protected attribute is independently flipped to 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 are 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 following worst-case adversarial perturbation model: Given an η > 0, after the training samples are independently drawn from a true distribution D, the adversary with unbounded computation power sees all the samples and can use this information to choose any η-fraction of the samples and perturb their protected attributes arbitrarily. This model is a straightforward adaptation of the perturbation model of [31] to the fair classification setting and we refer to it as the η-Hamming model. Unlike perturbation models studied before, this model can capture settings where the perturbations are strategic or arbitrarily 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 a 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, a fairness metric Ω, and a desired fairness 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 a fairness value, ΩD(f), of at least τ with respect to the true distribution D. Our contributions. We present an optimization framework (Definition 4.1) that outputs fair classifiers for the η-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 linear-fractional fairness metrics (that capture most fairness metrics studied in the literature); see Definition 3.1 and [13]. The framework provably outputs a classifier whose accuracy is within 2η of the accuracy of f? and which violates the fairness constraint by at most O(η/λ) additively (Theorem 4.3), under the mild assumption that the “performance” of f? on each protected group is larger than a known constant λ > 0 (Assumption 1). Assumption 1 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 1 is necessary for fair classification in the η-Hamming model: If λ 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 guarantee under Assumption 1: No algorithm can guarantee to output a classifier with accuracy closer than η 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.21). Finally, we also extend our framework’s guarantees to the Nasty Sample Noise model (Supplementary Material A.1.5). The Nasty Sample Noise model is a generalization of the η-Hamming model, which was studied by [11] in the context of PAC learning (without any fairness considerations), where the adversary can choose any η-fraction 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 performance on COMPAS [3], Adult [23], and a synthetic dataset (Section 5). We generate perturbations of these datasets admissible in the η-Hamming model and compare the performance of our approach to several baselines [44, 6, 59, 14, 40] with statistical rate and false-positive rate as fairness metrics.1 On the synthetic dataset, we compare against a method developed for fair classification under stochastic perturbations [14] and demonstrate the comparative strength of the η-Hamming model; our results show that [14]’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 framework 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) fairness-accuracy trade-off compared to all baselines we consider in a variety of settings, and is not dominated by any other approach (Figure 1 and Figures 7 and 8 in Supplementary Material E.2).
1Let q`(f,SR) (respectively q`(f,FPR)) be the fraction of positive predictions (respectively false-positive predictions) by f in the `-th protected group. f ’s statistical rate (respectively false-positive rate) is the ratio of the minimum value to the maximum value of q`(f,SR) (respectively q`(f,FPR)) over all protected groups.
Techniques. The starting point of our optimization framework (Definition 4.1) is the “standard” optimization program for fair classification in the absence of any perturbations: Given a fairness metric Ω and a desired fairness threshold τ as input, find f? ∈ F that maximizes the accuracy on the given data Ŝ constrained to a fairness value at least τ on the given data. However, when Ŝ is given to us by an η-Hamming adversary, this standard program, which imposes the fairness constraints with respect to the perturbed data Ŝ, may output a classifier with an accuracy/fairness-value worse than that of f? when measured with respect to D. But, observe that the difference in accuracies of a classifier when measured with respect to the given data Ŝ and data sampled fromD is at most η. Thus, if f? ∈ 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 2η 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 τ 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 ∈ F is said to be s-stable with respect to a fairness metric if for any Ŝ that is generated by an η-Hamming adversary, the ratio of fairness value of f with respect to D and with respect to Ŝ is between s and 1/s (see Definition 4.7). It follows that any s-stable classifier that has fairness value τ ′ > 0 with respect to Ŝ, has fairness value at least s · τ ′ 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 τ ′ > 0 with respect to Ŝ, comes with a guarantee that any feasible classifier has a fairness value at least s · τ ′ (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.9). 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 a “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 1. Overall, modifying Program (2) to include this constraint (Equation (5)) with a suitable value of s, and setting an appropriate fairness threshold τ so that f? remains feasible, leads us to our framework.

heading: 2 Related work
text: 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., on fair classification in the absence of protected attributes) are presented in Supplementary Material D.1.
[44] give a 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 [32] improves the fairness value of the accuracy-maximizing classifier with respect to equalized-odds on the true distribution with a binary protected attribute. [59] consider a nonbinary protected attribute. In their “soft-weights” 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.2 [14] give provable guarantees on the accuracy and fairness value of output classifiers for multiple non-binary protected attributes and the class of linear-fractional metrics. All of the aforementioned works [44, 6, 59, 14] consider stochastic perturbation models, which are weaker than the model considered in this paper. Further, compared to [44, 6], our approach (and that of [14]) can handle multiple categorical protected attributes and multiple linear-fractional metrics (which include statistical rate and can ensure equalized-odds constraints). Compared to [6, 59], our work (and those of [44, 14]) 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 Nasty Sample Noise model [11, 4], and hence, than the model considered in this paper. Further, our
2Supplementary Material D.2.3 gives an example where [59]’s distributionally robust approach outputs a classifier whose accuracy is arbitrarily close to 1/2.
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 linear-fractional 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, 11, 15, 5]; see also [4]. In particular, [11] 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 a classifier. Our framework Program (ErrTolerant) finds empirical risk minimizing classifiers that satisfy fairness constraints on the perturbed data, and that are also “stable” for the given fairness metric. While both frameworks show that the accuracy of the respective output classifiers is within 2η of the respective optimal classifiers when the data is unperturbed, the optimal classifiers can be quite different. For instance, while [11]’s framework is guaranteed to output a classifier with high accuracy, it can perform poorly on fairness metrics; see Section 5 and Supplementary Material D.2.1.

heading: 3 Model
text: Let the data domain be D := X × {0, 1} × [p], where X is the set of non-protected features, {0, 1} is the set of binary labels, and [p] is the set of p protected attributes. Let D be a distribution over D. Let F ⊆ {0, 1}X×[p] be a hypothesis class of binary classifiers. For f ∈ F , let ErrD(f) := Pr(X,Y,Z)∼D[f(X,Z) 6= Y ] denote f ’s predictive error on draws fromD. In the vanilla classification problem, the learner L’s goal is to find a classifier with minimum error: argminf∈F ErrD(f). In the fair classification problem, the learner is restricted to pick classifiers that have a “similar performance” conditioned on Z = ` for all ` ∈ [p]. We consider the following class of metrics. Definition 3.1 (Linear/linear-fractional metrics [13]). Given f ∈ F and two events E(f) and E ′(f), that can depend on f , define the performance of f on Z = ` (` ∈ [p]) as q`(f) := PrD[E(f) | E ′(f), Z = `]. If E ′ depends on f , then q`(f) is said to be linear-fractional, otherwise linear.
Definition 3.1 captures most of the performance metrics considered in the literature. For instance, for E := (f = 1) and E ′ := ∅, we get statistical rate (a linear metric).3 For E := (f = 1) and E ′ := (Y = 0), we get false-positive rate (also a linear metric). For E := (Y = 0) and E ′ := (f = 1), we get false-discovery rate (a linear-fractional metric). Given a performance metric q, the corresponding fairness metric is defined as
ΩD(f) := min`∈[p] q`(f)
max`∈[p] q`(f) . (1)
When D is the empirical distribution over samples S, we use Ω(f, S) to denote ΩD(f). The goal of fair classification, given a fairness metric Ω and a threshold τ ∈ (0, 1], is to (approximately) solve:
minf∈F ErrD(f) s.t., ΩD(f) ≥ τ. (2)
If samples from D are available, then one could try to solve this program. However, as discussed in Section 1, we do not have access to the true protected attribute Z, but instead only see a perturbed version, Ẑ ∈ [p], generated by the following adversary. η-Hamming model. Given an η ∈ [0, 1], letA(η) denote the set of all adversaries in the η-Hamming model. Any adversary A ∈ A(η) is a randomized algorithm with unbounded computation resources that knows the true distribution D and the algorithm of the learner L. In this model, the learner L queries A for N ∈ N samples from D exactly once. On receiving the request, A draws N independent samples S := {(xi, yi, zi)}i∈[N ] from D, then A uses its knowledge of D and L to choose an arbitrary η · N samples (η ∈ [0, 1]) and perturb their protected attribute arbitrarily to generate Ŝ := {(xi, yi, ẑi)}i∈[N ]. Finally, A gives these perturbed samples Ŝ to L. Learning model. Given Ŝ and the η, the learner L would like to (approximately) solve Program (2). Definition 3.2 ((ε, ν)-learning). Given bounds on error ε ∈ (0, 1) and constraint violation ν ∈ (0, 1), a learner L is said to (ε, ν)-learn a hypothesis class F ⊆ {0, 1}X×[p] with perturbation rate η ∈ [0, 1] and confidence δ ∈ (0, 1) if for all
3We overload the notation f to denote both the classifier as well as its prediction, and the terms, statistical rate and false-positive rate, to refer to both the linear/linear-fractional metric q and the resulting fairness metric Ω.
• distributions D over X × {0, 1} × [p] and • adversaries A ∈ A(η),
there exists a threshold N0(ε, ν, δ, η) ∈ N, such that with probability at least 1− δ over the draw of N ≥ N0(ε, ν, δ, η) iid samples S ∼ D, given η and the perturbed samples Ŝ := A(S), L outputs f ∈ F that satisfies ErrD(f)−ErrD(f?) ≤ ε and ΩD(f) ≥ τ − ν, where f? is the optimal solution of Program (2) (i.e., f? := argminf∈F ErrD(f), s.t., ΩD(f) ≥ τ ).
Given a finite number of perturbed samples, Definition 3.2 requires the learner to output a classifier that violates the fairness constraints additively by at most ν and that has a predictive error at most ε smaller than that of f?, with probability at least 1− δ. Like PAC learning [56], for a given hypothesis class F , Definition 3.2 requires the learner to succeed on all distributions D. Problem 1 (Fair classification with adversarial perturbations). Given a hypothesis class F ⊆ {0, 1}X×[p], a fairness metric Ω, a threshold τ ∈ [0, 1], a perturbation rate η ∈ [0, 1], and perturbed samples Ŝ, the goal is to (ε, ν)-learn F for small ε, ν ∈ (0, 1).

heading: 4 Theoretical results
text: In this section, we present our results on learning fair classifiers under the η-Hamming model. Our optimization framework (Program (ErrTolerant)) 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 a classifier’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 1, imposing the fairness constraint on Ŝ guarantees (approximate) fairness on the true distribution D. The accuracy guarantee follows by ensuring that the optimal solution of Program (2), f? ∈ F , is feasible for our framework. To ensure this, we require Assumption 1 that also appeared in [14]. Assumption 1. There is a known constant λ > 0 such that min`∈[p] PrD[E(f?), E ′(f?), Z = `] ≥ λ.
It can be shown that this assumption implies that λ is also a lower bound on the performances q1(f ?), . . . , qp(f ?) that depend on E and E ′. We expect λ to be a non-vanishing positive constant in applications. For example, if q is statistical rate, the minority protected group makes at least 20% of the population (i.e., min`∈[p] PrD[Z = `] ≥ 0.2), and for all ` ∈ [p], Pr[f? = 1 | Z = `] ≥ 1/2, then λ ≥ 0.1. In practice, λ is not known exactly, but it can be set based on the context (e.g., see Section 5 and [14]). We show that Assumption 1 is necessary for the η-Hamming model (see Theorem 4.4). Definition 4.1 (Error-tolerant program). Given a fairness metric Ω and corresponding events E and E ′ (as in Definition 3.1), a perturbation rate η ∈ [0, 1], and constants λ,∆ ∈ (0, 1], we define the error-tolerant program for perturbed samples Ŝ, whose empirical distribution is D̂, as
minf∈F ErrD̂(f), (ErrTolerant) (3) s.t., Ω(f, Ŝ) ≥ τ · (
1− (η + ∆)/λ 1 + (η + ∆)/λ
)2 , (4)
∀ ` ∈ [p], PrD̂ [E(f), E ′(f), Ẑ = `] ≥ λ− η −∆. (5)
∆ acts as a relaxation parameter in Program (ErrTolerant), which can be fixed in terms of the other parameters; see Theorem 4.3. Equation (4) ensures all feasible classifiers satisfy fairness constraints with respect to the perturbed samples Ŝ. Equation (5) ensures that all feasible classifiers are (1 − O(η/λ))-stable (see Definition 4.7). As mentioned in Section 1, this suffices to 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? is feasible for Program (ErrTolerant); 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 (ErrTolerant).
Before presenting our result we require the definition of the Vapnik–Chervonenkis (VC) dimension. Definition 4.2. Given a finite set A, define the collection of subsets FA := {{a ∈ A | f(a) = 1} | f ∈ F}. We say that F shatters a set B if |FB | = 2|B|. The VC dimension of F , VC(F) ∈ N, is the largest integer such that there exists a set C of size VC(F) that is shattered by F .
Our first result bounds the accuracy and fairness of an optimal solution fET of Program (ErrTolerant) for any hypothesis class F with a finite VC dimension using O(VC(F)) samples. Theorem 4.3 (Main result). Suppose Assumption 1 holds with constant λ > 0 and F has VC dimension d ∈ N. Then, for all perturbation rates η ∈ (0, λ/2), fairness thresholds τ ∈ (0, 1], bounds on error ε > 2η and constraint violation ν > 8ητ/(λ−2η), and confidence parameters δ ∈ (0, 1) with probability at least 1− δ, the optimal solution fET ∈ F of Program (ErrTolerant) with parameters η, λ, and ∆ := O (min {ε− 2η, ν − 8ητ/(λ−2η), λ− 2η}), and N = poly(d, 1/∆, log(p/δ)) perturbed samples from the η-Hamming model satisfies ErrD(fET)− ErrD(f?) ≤ ε and ΩD(fET) ≥ τ − ν.
Thus, Theorem 4.3 shows that any procedure that outputs fET, given with a sufficiently large number of perturbed samples, (ε, ν)-learns F for any ε > 2η and ν = O((η·τ)/λ). Theorem 4.3 can be extended to provably satisfy multiple linear-fractional metrics (at the same time) and work for multiple non-binary protected attributes; see Theorem B.2 in Supplementary Material B.1. 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.1.5. Finally, Program (ErrTolerant) only requires an estimate of one parameter, λ. (Since η is known, τ is fixed by the user, and ∆ can be set in terms of the other parameters.) If for each ` ∈ [p], we also have estimates of λ` := PrD [E(f?), E ′(f?), Z = `] and γ` := PrD[E ′(f?), Z = `], then we can use this information to “tighten” Program (ErrTolerant) to the following program:
minf∈F ErrD̂(f), (ErrTolerant+) (6) s.t., Ω(f, Ŝ) ≥ τ · s,
∀ ` ∈ [p], PrD̂ [E(f), E ′(f), Ẑ = `] ≥ λ` − η −∆.
where the scaling parameter s ∈ [0, 1] is the solution of the following optimization program
min η1,η2,...,ηp≥0 min `,k∈[p] 1− η`/λ` 1 + (ηk − η`)/γ` · 1 + (η` − ηk)/γk 1 + η`/λk , s.t., ∑ `∈[p] η` ≤ η + ∆. (7)
If the classifiers in F do not use the protected attributes for prediction, then we can show that Program (ErrTolerant+) has a fairness guarantee of (1−s)+4ητ/(λ−2η) (which is always smaller than 8ητ/(λ−2η)) and an accuracy guarantee of 2η. We prove this result in Supplementary Material B.2. Thus, in applications where one can estimate λ1, . . . , λp and γ1, . . . , γp, Program (ErrTolerant+) offers better fairness guarantee than Program (ErrTolerant) (up to constants).
The proof of Theorem 4.3 appears in Supplementary Material A.1.
As for computing fET, note that in general, Program (ErrTolerant) is a nonconvex optimization problem. In our simulations, we use the standard solver SLSQP in SciPy [57] to heuristically find fET; see Supplementary Material E.1. Theoretically, for any arbitrarily small α > 0, the techniques from [13] can be used to find an f ∈ F that has the optimal objective value for Program (ErrTolerant) and that additively violates its fairness constraint (4) by at most α by solving a set of O(1/(λα)) 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 1). For all perturbation rates η ∈ (0, 1], thresholds τ ∈ (1/2, 1), confidence parameters δ ∈ [0, 1/2), and bounds on the error ε ∈ [0, 1/2) and constraint violation ν ∈ [0, τ − 1/2), if the fairness metric is statistical rate, then it is impossible to (ε, ν)-learn any hypothesis class F ⊆ {0, 1}X×[p] that shatters a set of 6 points of the form {xA, xB , xC} × [2] ⊆ X × [p] for some distinct xA, xB , xC ∈ X .
Suppose that τ = 0.8, say to encode the 80% Then, Theorem 4.4 shows that for any η > 0, any F satisfying the condition in Theorem 4.4 is not (ε, ν)-learnable for any ε < 1/2 and ν < τ − 1/2 = 3/10. Intuitively, the condition on F avoids “simple” hypothesis classes. It is similar to the conditions considered by works on PAC learning with adversarial perturbations [11, 39], and holds for common hypothesis classes such as decision-trees and SVMs (Remark A.28 in Supplementary Material A.5). Thus, even if η is vanishingly small, without additional assumptions, any F satisfying mild assumptions is not (ε, ν)-learnable for any ε < 1/2 and ν < 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 is optimal up to a constant factor). For all perturbation rates η ∈ (0, 1], confidence parameter δ ∈ [0, 1/2), and a (known) constant λ ∈ (0, 1/4],
if the fairness metric is statistical rate and τ = 1, then given the promise that Assumption 1 holds with constant λ, for any bounds ε < 1/4− 2η/5 and v < η/(10λ) · (1− 4λ)−O ( η2/λ2 ) it is impossible to (ε, ν)-learn any hypothesis class F ⊆ {0, 1}X×[p] that shatters a set of 10 points of the form {xA, xB , xC , xD, xE} × [2] ⊆ X × [p] for some distinct xA, xB , xC , xD, xE ∈ X .
Suppose that λ < 1/8 and η < 1/2, then Theorem 4.5 shows that for any η > 0, any learner L that has a fairness guarantee ν < η/(20λ) − O(η2/λ2), must have a poor error bound, of at least ε ≥ 1/4 − 2η/5 ≥ 1/20, to (ε, ν)-learn any F that satisfies a mild assumption. When η/λ is small, this shows that any learner with a fairness guarantee ν = o(η/λ) must have an error guarantee at least 1/4 − 2η/5 2η. 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 2η to 1/4 − 2η/5. Like Theorem 4.4, the condition on F in Theorem 4.5 avoids “simple” hypothesis classes and holds for common hypothesis (Remark A.28 in Supplementary Material A.5). Finally, complementing our accuracy guarantee, we prove that for any ε < η, no algorithm can (ε, ν)-learn 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 (ErrTolerant) and how they connect with the proof of Theorem 4.3. Our goal is to construct error-tolerant constraints using perturbed samples Ŝ such that the classifier fET, that has the smallest error on Ŝ subject to satisfying these constraints, has accuracy 2η-close to that of f? and that additively violates the fairness constraints by at most O(η/λ). Step 1: Lower bound on the accuracy of fET. This step relies on Lemma 4.6. Lemma 4.6. For any bounded function g : {0, 1}2 × [p] → [0, 1], δ,∆ ∈ (0, 1), and adversaries A ∈ A(η), givenN = poly(1/∆,VC(F), log 1/δ) true samples S ∼ D and corresponding perturbed samples A(S) := {(xi, yi, ẑi)}i∈[N ], with probability at least 1− δ, it holds that
∀ f ∈ F , ∣∣∣ 1N ∑i∈[N ] g(f(xi, ẑi), yi, ẑi)− E(X,Y,Z)∼D [g(f(X,Z), Y, Z)]∣∣∣ ≤ ∆ + η.
The proof of Lemma 4.6 follows from generalization bounds for bounded functions (e.g., see [54]) and because the η-Hamming model perturbs at most η ·N samples. Let g be the 0-1 loss (i.e., g(ỹ, y, z) := I [ỹ 6= y]), then for all f ∈ F , Lemma 4.6 shows that the error of f on samples drawn from D and samples in Ŝ are close: |ErrD(f)− Err(f, Ŝ)| ≤ ∆ + η. Thus, intuitively, minimizing Err(f, Ŝ) could be a good strategy to minimize ErrD(f). Then, if f? is feasible for Program (ErrTolerant), we can bound the error of fET: Since fET is optimal for Program (ErrTolerant), its error on Ŝ is at most the error of f? on Ŝ. Using this and applying Lemma 4.6 we get that
ErrD(fET) ≤ Err(fET, Ŝ) + η + ∆ ≤ Err(f?, Ŝ) + η + ∆ ≤ ErrD(f?) + 2(η + ∆). (8) Step 2: Lower bound on the fairness of fET. One could try to bound the fairness of fET using the same approach as Step 1, i.e., show that for all f ∈ F : |ΩD(f)− Ω(f, Ŝ)| ≤ O(η/λ). Then ensuring that f has a high fairness on Ŝ implies that it also has high fairness on S (up to an O(η/λ) factor). However, such a 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 ∈ F is said to be s-stable for fairness metric Ω, if for all adversaries A ∈ A(η) and confidence parameters δ ∈ (0, 1), given polylog(1/δ) samples S ∼ D, with probability at least 1− δ, it holds that ΩD(f)/Ω(f,Ŝ) ∈ [s, 1/s], where Ŝ := A(S).
If an s-stable classifier f has fairness τ on Ŝ, then it has a fairness at least τ · s on D with high probability. Thus, if we have a condition such that any feasible f ∈ F satisfying this condition is s-stable, then any classifier satisfying this condition and the fairness constraint, Ω(·, Ŝ) ≥ τ/s, must have a fairness at least τ on D with high probability. The key idea is coming up such constraints. Lemma 4.8. Any classifier f ∈ F that satisfies min`∈[p] PrD [E(f), E ′(f), Ẑ = `] ≥ λ+ η + ∆, is ( 1−(η+∆)/λ1+(η+∆)/λ ) 2-stable for fairness metric Ω (defined by events E and E ′).
Step 3: Requirements for the error-tolerant program. Building on Steps 1 and 2, we prove: Lemma 4.9. If the following conditions hold then, ErrD(fET) − ErrD(f?) ≤ 2η and ΩD(fET) ≥ τ −O(η/λ): (C1) f? is feasible for Program (ErrTolerant), and all f ∈ F feasible for Program (ErrTolerant) are (C2) s-stable for s = 1−O(η/λ), and (C3) satisfy Ω(f, Ŝ) ≥ τ · (1−O(η/λ)).
Thus, it suffices to find error-tolerant constraints that satisfy conditions (C1) to (C3). Condition (C3) can be satisfied by adding the constraint Ω(·, Ŝ) ≥ τ ′, for τ ′ = τ · (1−O(η/λ)). From Lemma 4.8, condition (C2) follows by using the constraint in min`∈[p] PrD [E(f), E ′(f), Ẑ = `] ≥ λ′, for λ′ ≥ Θ(λ). It remains to pick τ ′ and λ′ such that condition (C1) also holds. The tension in setting τ ′ and λ′ is 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 τ ′ := τ · ( 1−(η+∆)/λ1+(η+∆)/λ )
2 and λ′ := λ− η −∆ suffice to satisfy conditions (C1) to (C3) (this is where we use Assumption 1).
Overall the main technical idea is to identify the notion of s-stable classifiers and sufficient conditions for a classifier to be s-stable; combining these conditions with the fairness constraints on Ŝ, ensures that fET has high fairness on S, and carefully tuning the thresholds so that f? is likely to be feasible for Program (ErrTolerant) ensures that fET has an accuracy close to f?.
Proof overviews of Theorems 4.4 and 4.5. Our proofs are inspired by [39, Theorem 1] and [11, Theorem 1] which consider PAC learning with adversarial corruptions. In both Theorems 4.4 and 4.5, for some ε, ν ∈ [0, 1], the goal is to show that given samples perturbed by an η-Hamming adversary, under some additional assumptions, no learner L can output a classifier that has accuracy ε-close to the accuracy of f? and that additively violates the fairness constraints by at most ν. Say a classifier f ∈ F is “good” if it satisfies these required guarantees. The approach is to construct two or more distributions D1,D2, . . . ,Dm that satisfy the following conditions: (C1) For any `, k, given a iid draw S from D`, an η-Hamming adversary can add perturbations such that with high probability Ŝ is distributed according to iid samples from Dk. Thus L, who only sees Ŝ, with high probability, cannot identify the original distribution of S and is forced to output a classifier that is good for all D1, . . . ,Dm. The next condition ensures that this is not possible. (C2) No classifier f ∈ F is good for all D1, . . . ,Dm, and for each Di (i ∈ [m]), there is at least one good classifier fi ∈ F . (The latter-half ensures that the fairness and accuracy requirements are not vacuously satisfied.) Thus, for every L there is a distribution in D1, . . . ,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 key idea in the proofs is to come up with distributions satisfying the above conditions. [39, 11] 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.

heading: 5 Empirical results
text: We implement our approach using the logistic loss function with linear classifiers and evaluate its performance on real world and synthetic data.
Metrics and baselines. The selection of an appropriate fairness metric is 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 (ErrTolerant+)), Err-Tol, with stateof-the-art fair classification frameworks for statistical rate under stochastic perturbations: LMZV [44] and CHKV [14]. LMZV and CHKV take parameters δL, τ ∈ [0, 1] as input; these parameters control the desired fairness, where decreasing δL or increasing τ increases the desired fairness. We also compare against KL [40], which controls for true-positive rate (TPR) in the presence of a Malicious adversary, and AKM [6] that is the post-processing method of [32] and controls for equalized-odds fairness constraints. We also compare against the optimal unconstrained classifier, Uncons; this is the same as [11]’s algorithm for PAC-learning 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 E.
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 a (known) perturbation rate η. 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 η and uses the SLSQP solver in SciPy [57] to solve Program (ErrTolerant+). To advantage the baselines in our comparison, we provide them with even more information as needed by their approaches: LMZV and CHKV are given group-specific pertur-
bation rates: for each ` ∈ [p], η` := PrD[Ẑ 6= Z | Z = `], and KL is given η and for each ` ∈ [p], the probability PrD[Z = `, Y = 1]; where D is the empirical distribution of S. Err-Tol implements Program (ErrTolerant+) which requires estimates of λ` and γ` for all ` ∈ [p]. As a heuristic, we set γ` = λ` := PrD̂[Z = `], 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 η-Hamming adversaries (which we call ATN and AFN); each one computes the “optimal fair classifier” f?, which has the highest accuracy (on S) subject to having statistical rate at least τ 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?’s statistical rate. The adversary’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, we 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 η-Hamming 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 x1, x2 ∈ R, and a binary label. Conditioned on the protected attribute, (x1, x2) 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 a near-perfect accuracy (> 99%) and a statistical rate of 0.8 on S. Similar to Uncons, we consider a fairness constraint of τ = 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.4
Results. The fairness and statistical rate averaged over 50 iterations are reported in Table 1 as a function of the perturbation η. At η = 0, both CHKV and Err-Tol nearly-satisfy the fairness constraint (SR ≥0.79) and have a near-perfect accuracy (acc ≥0.98). However, as η 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 (acc ≥0.99 and SR ≥0.79) for all η considered. Hence, this shows that stochastic approaches may fail to satisfy their guarantees under the η-Hamming model.
Simulations on real-world data. In this simulation, we show that our framework can outperform each baseline with respect to the accuracy-fairness 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,172 samples with 10 binary features and a label that is 1 if the individual did not recidivate and 0 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 τ = 0.9 for Err-Tol and all baselines. We consider both adversaries ATN and AFN, and a perturbation rate of η = 3.5%, as 3.5% is roughly the smallest value for η necessary to ensure that the optimal fair classifier f? for τ = 0.9 (on S) has a statistical rate less than 0.78 on Ŝ.
Results. The accuracy and statistical rate (SR) of Err-Tol and baselines for τ ∈ [0.7, 1] and δL ∈ [0, 0.1] and averaged over 100 iterations are reported in Figure 1. For both adversaries, Err-Tol attains a better statistical rate than the unconstrained classifier (Uncons) for a small trade-off in accuracy. For adversary ATN (Figure 1(a)), Uncons has statistical rate (0.80) and accuracy (0.67). In contrast,
4We also attempted to compare against AKM, KL, and LMZV. But they did not converge to f? even on the unperturbed synthetic data, and hence, we did not include these results as it would be an unfair comparison.
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 a lower statistical rate (0.87), and other baselines have an even lower statistical rate (≤ 0.84) with accuracy comparable to AKM. For adversaryAFN (Figure 1(b)), Uncons has statistical rate (0.80) and accuracy (0.67), while Err-Tol 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 in accuracy to (0.57). In this case, Err-Tol has similar accuracy to statistical rate trade-off as LMZV, but achieves a lower maximum statistical rate (0.91). Meanwhile, Err-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 E (specifically, against the perturbation model of [14]) and observe similar statistical rate and accuracy trade-offs as approaches [14, 44] tailored for stochastic perturbations. Remark 5.1 (Range of fairness parameters in the simulation). Among baselines, AKM, KL, and Uncons do not take the desired-fairness value as input, so they appear as points in Figure 1. For all other methods (CHKV, Err-Tol, and LMZV), we vary the fairness parameters starting from the tightest constraints (i.e., τ = 1 and δL = 0) and relax the constraints until all algorithms’ achieved statistical rate matches the achieved statistical rate of the unconstrained classifier (this happens around τ = 0.7 and δL = 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 τ ≤ 0.7 and δL ≥ 0.1).

heading: 6 Limitations and conclusion
text: This work extends fair classification to real-world settings where perturbations in the protected attributes may be correlated or affect arbitrary subsets of samples. We consider the η-Hamming model and give a framework that outputs classifiers with provable guarantees on both fairness and accuracy; this framework works for categorical protected attributes and the class of linear-fractional 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 a 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 a 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 efficacy will depend on an appropriate choice of parameters; e.g., an overly conservative λ can decrease accuracy and an optimistic λ can decrease fairness. A careful assessment both pre- and post-deployment would be important to avoid negative social implications in a misguided attempt to do good [45].
Finally, we note that discrimination is 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 (IIS2045951), a J.P. Morgan Faculty Award, and an AWS MLRA Award.

Review summaries:
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.  **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.

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. 

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.  

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.   They show an optimization problem that ensures fairness and accuracy guarantees under a mild assumption and show a mild assumption is necessary for those guarantees.   Finally, they have some experiments in which they consider two well thought out adversaries.