On Adversarial Bias and the Robustness of Fair Machine Learning
Authors: Hongyan Chang
Ta Duy Nguyen
Sasi Kumar Murakonda
Ehsan Kazemi
Reza Shokri
Venue: ICLR 2022 Submitted (2022)
Keywords: Robustness
Algorithmic fairness

Abstract: Optimizing prediction accuracy can come at the expense of fairness. Towards minimizing discrimination against a group, fair machine learning algorithms strive to equalize the error of a model across different groups, through imposing fairness constraints on the learning algorithm. But, are decisions made by fair models trustworthy? How sensitive are fair models to changes in their training data? By giving equal importance to groups of different sizes and distributions in the training set, we show that fair models become more fragile to outliers. We study the trade-off between fairness and robustness, by analyzing the adversarial (worst-case) bias against group fairness in machine learning and by comparing it with the effect of similar adversarial manipulations on regular models. We show that the adversarial bias introduced in training data, via the sampling or labeling processes, can significantly reduce the test accuracy on fair models, compared with regular models. Our results demonstrate that adversarial bias can also worsen a model's fairness gap on test data, even though the model satisfies the fairness constraint on training data. We analyze the robustness of multiple fair machine learning algorithms that satisfy equalized odds (and equal opportunity) notion of fairness.

Under review as a conference paper at ICLR 2022
ON ADVERSARIAL BIAS AND THE ROBUSTNESS OF FAIR MACHINE LEARNING
Anonymous authors Paper under double-blind review
ABSTRACT
Optimizing prediction accuracy can come at the expense of fairness. Towards minimizing discrimination against a group, fair machine learning algorithms strive to equalize the error of model across different groups, through imposing faimees constraints on the learning algorithm. But, are decisions made by fair models trustworthy? How sensitive are fair models to changes in their training data? By giving equal importance to groups of different sizes and distributions the training set, we show that fair models become more fragile to outliers. We study the trade-off between fairness and robustness, by analyzing the adversarial (worst- case) bias against group fairness in machine learning and by comparing it with the effect of similar adversarial manipulations on regular models. We show that the adversarial bias introduced in training data, via the sampling or labeling processes, can significantly reduce the test accuracy on fair models, compared with regular models. Our results demonstrate that adversarial bias also worsen model's s fairness gap on test data, even though the model satisfies the faimess constraint on training data. We analyze the robustness of multiple fair machine learning algorithms that satisfy equalized odds (and equal opportunity) notion of fairness.
INTRODUCTION
Trustworthiness is crucial requirement of machine learning algorithms in critical decision making processes, as highlighted by many Al regulations and policies as well as technical research papers. Algorithmic fairness is at the core of trust requirements for automated decision making in sensitive domains. Group fairness measures, such equal opportunity and equalized odds (Hardt al., 2016) which is the focus of this paper, suggest equalizing the model's behavior across groups identified based protected attribute (e.g., race) avoid systemic discrimination against protected groups (Agarwal et al., 2018; Calders et al., 2009; Hardt et al., 2016; Madras et al., 2018).
The main question that robust with respect to changes to their training data. In this paper, we study if and how achieving group fairness can increase the susceptibility of machine learning models small fraction of adversarially-samplee outliers in the training set.
interested in is whether fair models are trustworthy, and in particular
large body of work shows machine learning is vulnerable to noisy and adversarial data (Biggio et al., 2012; Chen et al., 2017; Jagielski et al., 2018; Koh & Liang, 2017; Li et al., 2016; Mei & Zhu, 2015a: Shafahi al., 2018: Steinhardt et al., 2017: Suciu et al., 2018). Recent work studies the performance of fair machine learning in the presence of noisy training data with under-representation and labeling bias (Blum & Stangl, 2020; Calders & Žliobaité, 2013; De-Arteaga et al., 201 8; Jiang & Nachum, 2020; Kallus& & Zhou, 2018: Lamy et al., 2019). Under the assumptions of uniform noise and in the theoretical setting of having an unlimited number of training data, these works analyze the effect of noisy/biased training data on fair models. Interestingly, Blum Stangl (2020) show that ERM with equal opportunity can recover the Bayes-optimal classifier from biased data. In other words, fair algorithms are more robust to certain types bias in the training dataset than standard learning algorithms (without fairness constraints). However, there has been little quantitative analysis of the interaction between group fairness and robustness of the model under realistic settings (finite training data and non-uniform noise). In this paper, we quantitatively measure the impact of group fairness on the robustness of the model under worst-case (adversarial) bias, which exactly aims minimizing the chance of recovering from biased data. To the best of our knowledge, this paper

---

Under review as a conference paper at ICLR 2022
provides the first quantitative analysis for the robustness of fair machine learning algorithms in the adversarial setting.
We assume the training data is biased, through adding small fraction of outliers that are adversarially sampled (and labeled) to degrade the test accuracy of fair models. We exploit the fact that algorithms with group-fairness, constraints approximately equalize the influence of different groups, in the training set, on the model. Equality of the group influence would consequently change the influence of individual data samples across different groups in a disproportionate way due differences in size and distribution of the groups. Thus, the model's susceptibility to worst-case outliers is largely dependent on how the outliers are distributed across different subgroups.
We extensively evaluate the robustness of fair machine learning on multiple fairness algorithms (Hardt et al., 2016; Agarwal et al., 2018; Rezaci et al., 2020; Cotter et al., 2019; Zhang et al., 2018) and benchmark datasets (Dua & Graff, 2017; Larson et al., 2017: mep: ahr) to investigate how, why, and under what circumstances models with group fairness are more fragile with respect to adversarial bias compared to unconstrained models. We show that group fairness reduces robustness. Models trained using various fair machine learning algorithms are all more susceptible to adversarial bias compared with unconstrained models. We can observe this effect even for the case of the most limited scenario of adversarial data sampling for a small fraction of the training set, without manipulating the data features and labels. We notice this is because that adversarial bias amplifies the cost of fairness on model accuracy by placing the outliers into the smallest group with the least frequent label. It effectively reduces the best achievable accuracy for the smallest subgroup, limiting the fair models' accuracy on the minority. In this case, the model sacrifices its accuracy over the majority group to satisfy the fairness constraint. results significant accuracy on the overall dataset. Furthermore, we present the potential trade-offs between robustness and fairness. Finally, adversarial manipulation of the training data prevents the model from generalizing its fairness to clean test data even though it is guaranteed on training data. This results in models that, according to the faimess measure, are even more discriminatory than unconstrained models, but on a different part of the population.
This work introduces significant challenge towards designing trustworthy machine learning algo- rithms. We emphasize that, as shown in our results, the fair models trained under noisy data could be significantly unfair (with respect to the same fairness measures). Thus, sensitivity to changes in data undermines both fairness and accuracy of models. This calls for designing new fairness measures which are not inherently susceptible to noise.
BACKGROUND AND PROBLEM STATEMENT
Machine learning. Consider a classifier fo : X + V, that maps the feature space X' labels ). The model is represented by its parameters 0 taken from a parameter space O. The model is trained to minimize a loss function É θ X x y - R2+, over its training set D. We let X and Y denote the random variables associated with the features and the labels, and (X, Y) to denote the underlying distribution of the data. We obtain the model parameters by solving minøge [D)
1 C(0; D),
where C(0; DD- E(..)eD ((0;z, y) is the cumulative loss of the model over the training set D.
Fairness. We assume all data points are split into groups based on a protected attribute S E S (e.g., gender). This attribute could be part of the feature set Y. We focus on equalized odds, which is a widely-used notion for group fairness (Hardt et al., 2016). Following previous works (Agarwal et al., 2018; Donini et al., 2018), we say classifier fe is 8-fair under equalized odds if
A == max VEY,a,bES
Pr(fo(X) D
# y/S Y y| - Pr(ff(() # v/S = =b, b, = u)
<6, (1)
where the probabilities are computed empirically over the training data set D. We refer to A as the model's empirical fairness gap. A model satisfies exact equalized odds fairness when 0. In practice, fairness is usually achieved by ensuring d- f-fiimnsss empirically on the model's training set, e.g., through minimizing the model's empirical loss under 8-faimess as a constraint (Agarwal et al., 2018) or post-processin (Hardt et al., 2016). We define the constraint C(O, D) == A(, D) 8 < 0 as a fairness constraint. We refer to the models learned with the fairness constraint as fair models,
Exteesson and analysis for other group faimness metrics (i.c., equal opportunity (Hardt al., 2016)) can be found in Appendix E.7.
2

---

Under review as a conference paper at ICLR 2022
to distinguish them from unconstrained models that are learned without any faimess constraint. We quantify the performance of a model based on its test accuracy, and its fairness gap on the test dataset.
Problem statement. The primary research question we investigate in this paper is whether, how, and why models with (equalized odds) group fairness are less robust to adversarial bias, compared with unconstrained models. We consider model robust if changing a small fraction of the training set does not significantly downgrade the predictive power of the model.
Towards quantifying the robustness, we assume the biased training set D is composed of the clean dataset De of size n, and the adversarially chosen dataset Dp of size en. The clean training set De and test set D Diest are sampled from the same underlying distribution (X, Y). So, we investigate the effect of the bias in the training set, which is introduced through Dp. We consider two variations of bias: adversarial sampling, and adversarial labeling. These are the worst-case sampling and labeling bias, where Dp is chosen to maximize the loss of model. Let Dj be dataset sampled from (X, ), similar to the clean data. In adversarial sampling, we choose outliers D, C Du. and in adversarial labeling, we choose them also with the possibility of crafting their labels Dp C. {(x, : (I. y) E Dx v' E } Based on this setting, the maximum vulnerability of a fair model in the presence of adversarial bias can be formulated as bi-level optimization problem subject the fairness constraint C(O, (D) S 0:
[(0; D. UD))) DEE (De D
max BX X, Y),, where i == argmin Dy
st. C(O, (DD,) S 0, (2)
where the expectation is taken over the underlying (clean) data distribution. The outer maximization
searches for the strongest D, that maximizes the expected loss of the fair model (given by 6). This fair model is obtained by solving the inner constrained minimization on the biased training dataset D. Up- The expected loss can be measured on a test set Duest sampled from the data distribution (X,Y).
To generate the strongest Dp. we assume the knowledge of the learning algorithm (e.g., logistic regression, SVM) and the clean training dataset De available when generating Dp. but the exact fair learning algorithm is unknown. It allows us to obtain upper bound on the performance degradation incurred by the adversarial bias and serves as a starting point towards understanding the maximal vulnerability. Besides, for investigating the effect of faimess constraints on the model robustness, evaluate the robustness of unconstrained models as a baseline. Adversarial bias against unconstrained models is equivalent to the problem of data poisoning attacks (we discuss more in Section 6).
3 ADVERSARIAL BIAS
To find the strongest D, for evaluating the robustness of fair models, we need to solve the bi-level optimization problem (2), which non-convex and intractable (Bard, 1991; Hansen et al., 1992: Deng, 1998). The fairness constraint makes the problem even more difficult." 2 In this section, we explain how to approximate problem (2) design effective adversarial strategies.
In the problem (2), it is hard to track the influence of Dp on the test loss as it can only affect the test loss via the model's parameters. To make progress, we first approximate the loss on the test data by the loss on the clean training data, following the approximations used for designing poisoning attacks against unconstrained models (Steinhardt et al., 2017). Specifically, let Ô be the solution to the inner optimization problem and we have L(O; Desst) ( long as the model has enough capacity to fit but does not overfit the training dataset (which can be achieved by appropriate regularization), the loss on the biased training dataset (i.e., RHS of the inequality) provides a good approximation for the test loss, which allows us to explicitly measure the impact of the poisoning data. Therefore, we replace the objective of the inner minimization in Eq. (2) with L10:D,UD,)/, where n = /Del. The resulting optimization problem is hard to solve due to the bi-level optimization and the constraints in the inner optimization. To resolve this, we then relax the inner constrained optimization by introducing a Lagrange multiplier X E RR::
L(O; ( < L(0; De U Dp) DDll As
s.t. C(O, D) 0 = =min max L(0: D)
[(0; D)
> max min [(0; D) + AC(O.D))
min dgo
AC(0,
DEE AER
XER, BEB
We would like to point out that, for the unconstrained model, under the convex assumption of the loss function, it is possible to find the approximate solution by replacing the inner optimization with its stationarity (KKT) condition (Biggio al., 2012; Koh & Liang, 2017).
3

---

Under review as a conference paper at ICLR 2022
where D カ= DDuDDp The inequality follows from the weak duality theorem. We can now find Dp by maximizing lower bound provided by the Lagrangian function mingee ( (C(e:D)/n + (0, D) for fixed À E R.,. Indeed, maximizing the lower bound provided by the Lagrangian function would result in a solution with a high loss (which is guaranteed to be at least equal to the loss for the lower bound) for the original problem. In this optimization procedure, we can also replace the fairness constraint C(O, D)= == A(0, D) ô with the faireess gap A(0, D), because the constant value d > 0 does not affect the solution for the Lagrangian. Finally, by considering all the above-mentioned steps, the new optimization problem is:
[[O: + (., n
max min Dp dg@
Thus, solve the problem (2), the alternative goal find Dp that maximizes a linear combination of the training loss and the model's violation from the fairness constraint, where À controls the penalty for the violation. In the light of those approximations, we design two algorithms to generate Dp-
An Approximation for the Fairness Gap. Finding Dp is an intractable combinatorial optimization problem because the fairness gap could not be split into separate functions of individual data points. It is still hard to track the influence of individual data points. To resolve it, we first find an additive proxy for fairness gap. We substitute the fairness gap A by the average of an approximate contribution of each training data point to the fairness gap. This allows to design an efficient sequential policy. More specifically, let ((x. y) jd be a multi-set with la repetitions of a data point (I., y). Consequently, DU {(xr, })}* is equivalent to adding k copies of (ar, v) to D. In this setting, for any data point (xc, y) E Dp. the fairness gap cn (0, D. U ((x,)) y)) is a proxy for measuring the contribution of that data point to the fairness gap A(0, DD,) In other words, it measures how the faimess gap changes if en copies of (z, y) is added to the clean data. Also, the maximum of A (0. D. U {(x, ") over all data points (x. y) E Dp provides an upper bound on the fairness gap of the model, when the size of Dp is en. Given this proxy for the contribution of each data point to the faimess gap, we obtain the following approximation: A (0, De DD) ~ E(r.)), en A (0, De U {(x y) ")) By substituting the fairness gap with its proxy, now we can solve the following optimization problem:
max min [- (0; (D:D.
Σ ((T.)) = max (Dp) = M (4)
2o 0EB
D
(z,g)ED,
where (Dp) is the loss incurred by a poisoning set D, on the fair model, and M is the maximum loss of the fair model under any choices of Dp. Algorithm variant of the no-regret online gradient descent methods (Hazan, 2016), presents solution to problem (4). It initializes a model 0 O, and identifies en points for Dp iteratively. The feasible set of points F(Dx) is determined by the adversarial bias setting. For adversarial sampling, have F(Dx) = DE. and for adversarial labeling, F(Dx) = ((x, (x. y) E Dx. y E Y}. The algorithm iteratively performs the following steps:
Data point selection. (Algorithm 1, line 5): It selects data point with the highest impact weighted sum of the loss function and the faimess gap with respect to the model parameter 0²1
Parameter update. (Algorithm 1, line 7): The parameters are updated minimize the penalized loss function based on the selected data point (x', y²). In this way, the algorithm (through the approximations made by the Lagrange multiplier and the surrogate function) keeps track of the fair model under the set of already selected data points for Dp.
In Theorem 1, by following the approach proposed by (Steinhardt et al., 2017), we relate the performance of Algorithm with the maximum loss in Eq. (4). Moreover, in Appendix C.2, we prove that under some reasonable conditions (e.g., by using similar assumptions made by (Donini et al., 2018) to approximate the fairness gap), our algorithm finds the (nearly) optimal solution for Eq. (4). Theorem 1. Let D; be the data set produced by Algorithum 1. Let Regret(en) be the regret of this online learning algorithm after en steps. The performance of the algorithu is guaranteed by
M MD))) Regret(en)
(5)
en
where M and (D;) are the loss of the fair model under the optimal Dp and D;, respectively."
'hhe regret of decision-maker is defined as the difference hetween the total cost incurred and that of the hest-fixed decision in hindsight.
4

---

Under review as a conference paper at ICLR 2022
Algorithm 1 Online Gradient Descent Algorithm for Generating pp for Fair Models
Input: Clean data ee. n Del. feasible set F(Dx), en (the size of Pp). penalty parameter (L.agragge multiplier) X, learning rate 17-
2: Output: Dp-
3: Initialize 0 E +
4: for t = 1...,, en do
5: (x', y²)
(a
+ A (("")..
6: Dp + Pp ((x',
0 t gt (VC00 V -1:) u ((1))()))))))
7:
8:
end for
The proof for the theorem is deferred to Appendix C. From the theorem, it is clear that when the average regret Regret(en)/en is small, the Algorithm will result in a nearly optimal Dp.
Surrogate Function for the Fair Model. The parameter update step Algorithm provides an approximation (through adding the fairness constraint as penalty and approximating the faimess gap) for the fair model. Differently, our Algorithm 2 approximates the fair model using the unconstrained model. More specifically, Algorithm 2 iteratively adds data points that maximize combination of the loss and the fairness gap. however, over the unconstrained model. The reason for this approach is that we hope the points with the largest weighted sum of the loss and the fairness gap the unconstrained model may still have a large weighted sum on the fair models. Algorithm in Appendix C.3 presents the pseudo-code of this algorithm. An advantage of Algorithm 2 is that it reduces the chance of getting stuck in local minima because, in each parameter update, it makes a step towards the negative gradient of the exact unconstrained loss. This is in contrast with Algorithm 1, where due to the difficulty of approximating a constrained max-min problem, it might converge to some parameters not close to the fair model at all. We should point out that the algorithm and objectives are similar to the data poisoning attacks against unconstrained models when À 0 (Steinhardt et al., 2017). In this case, the fairness constraints are not exploited to introduce adversarial bias. In Section 5, we empirically show that Dp generated by exploiting the fairness gap (i.e., À >> 0) can incur higher test loss of fair models compared with the case where À = O.
4 EVALUATION SETUP
Datasets and models. We conduct experiments on the COMPAS dataset (Larson al., 2017), Adult dataset (Dua & Graff, 2017), Medical Expenditure Panel Survey (MEPS) dataset (mep; ahr), as well as synthetic data generated with the same setting as in (Zafar al., 2019). We use the binary protected features in those datasets. We present the results on COMPAS, Adult and synthetic datasets in this section, and the results on all datasets are deferred to Appendix On all datasets, we train logistic regression models. The accuracy of classification models on the three real-world datasets is low and close to predicting the most frequent label in the set. This does not help to understand the behavior of models in the presence of adversarial bias. Hence, we perform data pre- processing to separate hard examples from the rest of the data. Hard examples are data points with a large loss on a trained model the entire dataset. We will use hard examples as of our baselines. We also add hard examples to the attack dataset. We refer the reader to Appendix E. for more details.
Fair machine learning algorithms. We evaluate the robustness of existing learning algorithms that achieve equalized odds to show that the susceptibility to adversarial bias is a common issue for all of them. Thus, train logistic regression models with the equalized odds fairness constraint, by using the post-processing approach (Hardt et al., 201 20, the reductions approach (Agarwal et al., 2018), and fair algorithms proposed (Zhang al., 2018: Rezaei al., 2020; Cotter et al., 2019). Details about these fair algorithms are presented in Appendix D.
Adversarial bias. The data points in Dp are selected from F(Dx) using Algorithm (with À = e on COMPAS and synthetic, and X = 0.1e on Adult), and Algorithm 2 (with À 100e). We use Algorithm 2 with = 0 to generate biased data for unconstrained models (which is the same as the algorithm for poisoning attacks against unconstrained models (Steinhardt et al., 2017)). In all the cases, we select points in Dp without repetition in order to measure the robustness in a realistic setting. See Appendix E.2 for discussion choosing and the implementation details.
5

---

Under review as a conference paper at ICLR 2022
Table 1:
Test accuracy and fairness gap of unconstrained models and fair models trained on biased training data - COMPAS, Adult and synthetic datasets. When = 0, the models are trained on De.. When = 0.1, we show the accuracy of unconstrained models when the adversarial bias is introduced by Algorithm 2 with À = 0 (Steinhardt et al., 2017) and the worst accuracy of fair models when Dp is generated by either A Algorithm or Algorithm 2, along with the corresponding test fairness gap A defined in (I). The relative accuracy drop is shown in parentheses (defined in Section 4). Table 7 in Appendix E.3 shows the all results.
Benign (c = 0)
Adv.
Adv. Labeling (c = 0.1)
Dutaset
Model
Sampling = 0.1)
Test Ace
Atest
Test Acc
Ateet
Test Acc
Acst
Unconstrained
87.6
0.18
87.4 (0.2.)
0.11
85.1 (2.9%.
0.24
Fair (Hardt et al., 2016)
80.0
0.03
77.2 (3.5%)
0.08
70.9 (11.9.))
0.04
Fair (Agarwal et al., 201 8)
84,9
0.03
80.9 (4.7%)
0.07
68.0 (20.%
0.14
Synthetic
Fair (Rezaci et al., 2020)
76.1
0.02
70.2 (7.8%)
0.03
58.3 (23.5:.)
0.02
Fair (Cotter al., 2019)
85.5
0.04
84.5 (1.2%)
0.09
77.8 (9.0%:L)
0.16
Fair (Zhang et al., 2018)
78.1
0.11
75.0 (4.0%
0.16
63.0 (19.95))
0.27
Unconstrained
94.3
0.21
87.6 (7.1%)))
0.26
84.7 (10.5t.)
0.28
Fair (Hardt al., 2016)
87.4
0.07
70.8 (19.%.)
0.27
68.2 (22.9%)
0.25
Fair (Agarwal et al., 2018)
93.6
0.06
73.1 (22.%))
0.37
67.7 (28.9
0.39
COMPAS
Fair (Rezaci et al., 2020))
84.5
0.06
63.2 (25.96L
0.09
60.6 (28.9FL)
0.09
Fair (Cotter al., 2019)
91.9
0.08
79.6 (13.9%
0.27
76.2 (17.9FL
0.31
Fair (Zhang ct al., 2018)
81.0
0.09
66.0 (19.%.L
0.14
64.1 (21.
0.12
Unconstrained Fair (Hardt et al., 2016)
94.3
0.07
94.0 (0.3%
0.06
89.3 (5.3%
0.06
92.7
0.03
89.6 (3.3%)
0.16
81.1 (13.%gL
0.09
Fair (Agarwal ct al., 2018)
93.8
0.04
91.7 (2.2%
0.12
80.9 (14.%
0.09
Adult
Fair (Rezaci et al., 2020)
84.5
0.03
78.1 (7.6%
0.03
64.9 (23.%)))
0.08
Fair (Cotter al., 2019)
92.7
0.04
90.3 (2.6%
0.07
83.8 (9.6%.1
0.44
Fair (Zhang al., 2018)
89.7
0.18
85.7 (4.4%-L
0.28
44.9 (50.%
0.06
Baseline algorithms and robustness evaluation. Besides comparing with prior data poisoning attacks against unconstrained models (Steinhardt et al., 2017), we consider the following baselines for augmenting the training dataset. Random sampling: randomly selecting data points from Dx. Label flipping: randomly selecting data points from Dr and flipping their labels. Hard examples: randomly selecting data points from the set of hard examples. To measure the robustness, we compute the relative test accuracy drop of the model trained on biased data versus the benign model 0) trained exclusively on clean data. A smaller drop in relative test accuracy implies stronger robustness.
EVALUATION RESULTS
In this section, first quantify and compare the robustness of fair models and unconstrained models, then show how the adversarial bias affects fair models. By examining the impacts of adversarial bias on the majority and minority groups, we identify the causes of the vulnerability of fair models. Finally, we present the trade-off between fairness and robustness and other effects of adversarial bias.
Fairness deteriorates robustness. Table I presents the test accuracy and fairness gap of uncon- strained models and fair models on all the datasets. We observe large relative accuracy drop for all fair models on all the datasets compared with unconstrained models, even in the adversarial sampling setting where data labels are not changed (only clean data are being added but in an adversarially biased manner). On the synthetic dataset, the relative accuracy drop of fair models trained using the reductions approach (Agarwal et al., 2018) is even more than 10 times larger than that of unconstrained models. The results also imply that the robustness issue is more likely caused by faimess notions instead of fair algorithms. Note that our algorithms serve approximations of the best algorithm for generating Dp- We can expect an even larger accuracy drop for fair models under stronger algorithms for adversarial bias. Besides, Figure 1 compares the test accuracy of unconstrained models and fair models when e varies. The baselines, e.g., adding randomly selected hard examples, do not have much effect on the test accuracy of fair models. However, when trained

---

Under review as a conference paper at ICLR 2022
Uncototraized Model Adv. Sumplin
Fair (Htuk et 2016) Adv. Sampling
Fair (Agarwal sl, 2015) Adv. Sampling
Text Acamcy
0.7
0.7
0.6
0.5
0.6
0.5
0.5
0.5
0.06
1.1
0.15
0.2
0.06
0.1
0.15
0.2
0
0,05
0.1
0.15
0.2
Unconstraited Model Adv. Labeling
Fair (Starok 2015) Adv. Labeling
Fair (Aganwal 2018) Adv. Labeling
Alg 2 UI
Acomcy
0.9
2lg. 2 1883
0.5
0.5
0.5
Ale. (A 1000))
Label Eipping
0.7
0.7
0.7
Random sampling
0.6
0.5
0.6
Hard examples
Constant prediction
0.5
0.05
111
0.35
0.2
0.5
0.05
011
0.15
0.2
0
0,055
11.1
0.35
0.2
Figure 1: Test accuracy of unconstrained and fair models in the presence of adversarial bias COMPAS dataset. The x-axis e is the ratio of the size of Dp to the size of clean dataset De. and reflects the contamination level of the training set. We compare the impact of adversarial bias with baselines and poisoning attacks against unconstrained models, for various The difference between test accuracy at 6 = (benign setting) and a larger value reflects the impact of the bias. Constant prediction always outputs the majority label in a clean dataset. The enforced fairness level 5 is 0 and 0.01 for the fair model (Hardt et al., 2016) and fair model (Agarwal al., 2018), respectively.
Adv. Sampling
Adv. Labeling
0.7
Alg. 2 0)
Pairess gap
0.6
Alg. 2 (A 100e)
0.5
0.5
Alg. 1 1000e)
Random sampling
0.4
0.4
Hard examples
0.3
0.3
Label fipping
0.2
0.2
0
0.05
0.1
0.05
0.2
Figure 2: Fairness gap on the unconstrained model with respect the training data COMPAS dataset. An unconstrained model is learned on the training data that includes Dp generated by various algorithms. The fairness gap is defined in (I). The numbers reflect how unfair this unconstrained model is with respect to the protected group on the training data.
(a) Overall Adv. Sampling
(b) Majarity group Adv. Sumpling (c) Minority group Adv. Sampling
Text Accuncy
0.9
0.8
0.8
0.8
Uncomninedd modd
0.7
0.7
Far - D.1)
0.6
0.6
0.6
Fai 0.05)
0.5
0.05
0.1
0.15
0.2
0
0.05
0.1
0.15
0.2
0
0.08
0.1 0.15 0.2
(d) Overall Adv. Labeling
Majority group Adv. Labeling
(0
Minority group- Adv. Labeling
Accuracy
0.9
0.9
0.9
0.8
0.8
0.8
0.7
0.7
0.7
0.6
0.6
0.6
0.5
0.5
0.05
0.1
0.15
0.2
0.05
0.1
0.15
0.2
0.05
0.1
0.15
0.2
Figure 3: Effect of fairness level 8 on robustness across groups in the presence of adversarial bias CÓMPAS dataset. For a given e, training dataset is the same for all the algorithms and 'Dp generated using Alg. 2 with X = 100G. Fair models are trained using reduction approach (Agarwal et al., 201 8). The majority group contributes 61% of the test data.
on adversarially biased data, fair models have much larger relative accuracy drop compared with unconstrained models. At 0.2, the test accuracy of fair models approaches what can be achieved by constant classifier. These results strongly imply that fair models are noticeably less robust against adversarial bias than unconstrained models.
Adversarial bias amplifies the cost of fairness on model accuracy by increasing the accuracy disparity. Figures 3(a) & (d) compare the test accuracy of fair models and unconstrained models when trained on the same training dataset. The gap in the accuracy between unconstrained models and fair models reflects the cost of faimess on model accuracy. Notably, as e increases, this cost increases significantly. For fair model with 5 0.001, the cost is 0.003 when e 0 and is increased by more
7

---

Under review as a conference paper at ICLR 2022
(8) Majority Adv. Sampling(b) Minority - Adv. Sumpling (c) Majority Adv. Labeling (d) Minority - Adv. Labeling
Uncoeanited
Accuracy
0.9
har 0.
0.8
Par 9.3))
Far (6 0.03
0.7
0.6
0.5
0.05
0.1
0.15
0.2
0.05
0.15
0.2
0.05
0.1
0.15
0.2
0
0.05
0.1
0.15 0.2
Figure 4: Effect of fairness level 8 on training accuracy across groups in the presence of adversarial bias- COMPAS dataset. For a given e, Pp is the same for all algorithms (generated using Alg. 2 with = 100c).
Adv. Sampling
Adv. Labeling
1
Accuracy
0.9
0.8
0.8
0.7
U.7
Minority
0.6
0.6
Majority
0.5
0.5
0
0.05
0.1
0.15
0.2
0.05
0.1
0.15 0.2
Figure 5: Training accuracy for group-based classifier COMPAS dataset. We train models only on the majority or minority training data and compare their training accuracy. For a given e, Dp is generated using Alg. 2 (A = 100c).
than 200 times when = 0.2 (0.254). It implies that adversurial bias significantly amplifies the cost of fairness on model accurucy. We further find that the increase in this cost is positively correlated with the increase in the fairness gap of unconstrained models on training data (which reflects the "unfairness" of unconstrained models on the training data) as shown in Figure 2. It is intuitive unconstrained models,
that when training accuracy disparity across groups more significant fairness constraints have a stronger impact on model performance, thus incurs a more substantial cost of fairness
model accuracy. In addition, on biased training data generated with Algorithm 2 (A = 100e) at e = 0.1, the fairness gap is 0.54, which is much larger than that of the random sampling baseline (0.3). This indicates that adversarial bias notably increases the fairness gap, which, in turn, increases the cost of fairness.
Implications of adversarial bias for majority vs. minority groups. Figures (c)))) show the test accuracy of models on the majority and minority groups We observe that on fair models, adversarial bias is significantly more impactful on the majority group. However, on the unconstrained model, the minority group is the one that incurs a larger loss. We find that the large loss on the minority group for the unconstrained model mainly caused by Dp. Because the most effective Dp (generated by Algorithm 2 with À 100e) mostly belong to the smallest subgroup, i.e., the smallest sensitive group 8 with the least frequent label y (see the distribution of Dp across groups in Figure 23 in Appendix E). Consequently, the unconstrained model learns wrong pattern on the minority group; thus, the accuracy drops significantly for the minority while barely changing on the majority group. On the other hand, the large accuracy drop of fair models on the majority group is primarily due to the fairness constraint. Fair models are enforced to equalize the accuracy across groups on the training dataset. Hence, even though most of the data from the majority group is clean, the training accuracy of fair models on the majority group drops due to the low accuracy on the minority group, as demonstrated in Figure 4. This accuracy drop ultimately translates from train data test data.
Adversarial bias increases the inherent "hardness" disparity. To equalize the accuracy across groups, fair models can increase the accuracy on the minority (the group that has lower accuracy) or decrease the accuracy on the majority. However, as shown in Figure 4, fair models do not increase the accuracy on the minority but decrease the training accuracy on the majority. We discover that is related to the best achievable accuracy for two groups (which reflects the inherent "hardness" of classifying positive samples and negative samples). We train group-based (unconstrained) models only using majority or minority training data. The training accuracy approximates the best achievable accuracy on each group for a given training dataset (and for a given type of model). The results are shown in Figure 5. We can that increases, the best accuracy does not change group but decreases significantly on the minority (from 0.95 to 0.7 with e = 0.2). Moreover, we find that the training accuracy of fair models the minority (Figure 4 (d)& is close to the best
the majority
8

---

Under review as a conference paper at ICLR 2022
achievable accuracy for the minority (Figure 5). It indicates that a small fraction of outliers can reduce the best achievable accuracy on the minority significantly, which limits the increase of the accuracy of fair models on the minority. Consequently, fair models have to sacrifice accuracy on the majority to satisfy the fairness constraint. To conclude, equalizing the accuracy across groups without considering their best achievable accuracy worsens the model's robustness against adversarial bias.
Trade-off between fairness and robustness. A fairer model on the training data is less robust against adversarial bias. In Figures 3(a) & (d), fair models with different ó have similar accuracy when = 0, (benign setting). As increases, the model with a stricter fairness constraint (i.e.. smaller 6) has a larger relative accuracy drop. On the other hand, more robust fair model is less likely to generalize its fairnsss on the test dataset. In Table 1, the fair algorithm proposed in (Cotter et al., 2019), which is the most robust algorithm against adversarial bias, fails to achieve fairness on the test data. Interestingly, when the unconstrained model is more discriminatory, fair models are less robust. In Table 1, fair models trained using the reduction approach (Agarwal et al., 2018) have a 22% relative accuracy drop COMPAS dataset, which is 10 times larger than that of fair models trained using the same algorithm on Adult datasets. We observe that this relative accuracy drop is positively correlated with the fairness gap of the unconstrained model in the benign setting (c = 0). It means that when there is more need for a fairness mechanism, fair models are less robust.
Other effects of adversarial bias. Fair machine learning aims to achieve faimess for the future data by satisfying fairness constraints on the training data. However, adversarial bias can jeopardize the fairness generalizability of the fair model. In the presence of adversarial bias, the lower the fairness level 6 on training data is, the higher the fairness gap on test data becomes. Moreover, we find that when the adversarial bias is introduced in the training dataset, the models trained with fairness constraints can become even more discriminatory than unconstrained models. The detailed results are presented in Appendix E.3. Besides, to approximate the maximal vulnerability, we assume Dp is generated with the knowledge about the learning algorithm and clean training dataset. Interestingly, the adversarial bias can still be effective even without this knowledge. See Appendix E.6 for details.
6 RELATED WORK AND CONCLUSION
Related Work We briefly review the related work here and provide extensive discussion in Ap- pendix B. Adversarial bias against unconstrained models is also known as untargeted data poisoning attacks where the adversary's s objective is to degrade the overall test accuracy of the model (Biggio et al., 2012; Mei & Zhu, 2015a; Jagielski et al., 2018; Li et al., 2016; Mei & Zhu, 2015b; Koh et al.. 2018; Koh & Liang, 2017: Steinhardt al., 2017) by adding a small fraction of poisoning data. However, most existing poisoning attacks manipulate the features and labels for the poisoning data. While, our case, the features of adversarial-chosen data points are clean. Recently, Solans et al. (2021) and Mehrabi et al. (2021b) develop poisoning attacks to increase the "unfairness" of unconstrained models. Differently, our focus is to evaluate the robustness of fair models. Multiple works in the literature study the impact of noisy and biased data on machine learning (Calders & Žliobaité, 2013; Fogliato et al., 2020; Kallus& & Zhou, 2018) but they did not cover adversarial (worst- case) bias. Under varying assumptions, multiple works (Blum & Stangl, 2020; Jiang & Nachum, 2020; De-Arteaga et al., 2018: Lamy et al., 2019; Friedler et al., 2019; Rambachan & Roth, 2019) have proposed strategies to account for rederrrepresentation bias and mislabeling while learning models. However, all the above works assume that the noise and bias in the training data is uniform distribution of under-representatioonnne httprrsseenatioommmlllllllinnnni over a subspace of points. Thus, these results may not translate proposed to achieve different robustness properties (Wang et al., 2020; Rezaei et al., 2020; Taskesen al., 2020; Roh et al., 2020; Cotter et al., 2019). However, those algorithms might not achieve robustness in our setting where the adversary controls the labels of a small fraction of samples, and the learner has no additional knowledge about the clean dataset.
case of adversarial (worst-case) bias. Several fair learning algorithms have been
Conclusion We have introduced adversarial bias against fair machine learning for quantifying the robustness of models with group fairness. Our algorithms exploit the tension between fairness and accuracy and the fact that fair models try to equalize the accuracy on groups with different sensitive attributes. Our experiments show that adding a small percentage of adversarially sampled/labeled data points to the training set can significantly reduce the best accuracy fair models can get on the minority. As the results, a small fraction of the adversarially sampled/labeled data points reduces the model accuracy beyond what they can impose on unconstrained models.

---

Under review as a conference paper at ICLR 2022
REFERENCES
EPRS_ART (4026663))6413331311 (P1
pdf.
Agency for Healthcare Research and Quality, http://.t.ttp/////.a.rr....o//
Medical Expenditure Panel Survey, http:///////gg......oo.///////es
Tameem Adel, Isabel Valera, Zoubin Ghahramani, and Adrian Welle. One-network adversarial fairness. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pp. 2412- 2420, 2019.
Alekh Agarwal, Alina Beygelzimer, Miroslav Dudik, John Langford, and Hanna Wallach. A reductions approach to fair classification. 2018.
Jonathan F Bard. Some properties the bilevel programming problem. Journal of optimization
theory and applications, 68(2):371-378 1991.
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. AI Fairness 360: An extensible toolkit for detecting, understanding, and mitigating unwanted algorithmic bias, October 2018. URL https: //arxiv.orge abs/ / 1810.000 01943.
Battista Biggio, Blaine Nelson, and Pavel Laskov. Support vector machines under adversarial label noise. In Asian Conference Machine Learning, pp. 97- 2011.
Battista Biggio, Blaine Nelson, and Pavel Laskov. Poisoning attacks against support vector machines. In Proceedings of the 29th International Coference on International Conference on Machine Learning, pp. 1467-1474, 2012.
Avrim Blum and Kevin Stangl. Recovering from biased data: Can fairness constraints improve accuracy? In Symposium on Foundations of Responsible Computing (FORC), volume 1, 2020.
Stephen Boyd, Stephen P Boyd, and Lieven Vandenberghe. Convex optimization. Cambridge university press, 2004.
Lars Buitinck, Gilles Louppe, Mathieu Blondel, Fabian Pedregosa, Andreas Mueller, Olivier Grisel, Vlad Niculae, Peter Prettenhofer, Alexandre Gramfort, Jaques Grobler, Robert Layton, Jake VanderPlas, Arnaud Joly, Brian Holt, and Gaël Varoquaux. API design for machine learning software: experiences from the seikit-learn project. In ECML PKDD Workshop: Languages for Data Mining and Machine Learning, pp. 108-122, 2013.
Cody Burkard and Brent Lagesse. Analysis of causative attacks against syms learning from data streams. In Proceedings of the 3rd ACM on International Workshop on Security And Privacy Analytics, pp. 31-36, 2017.
Toon Calders and Indré Żliobaité. Why unbiased computational processes can lead to discriminative decision procedures. In Discrimination and privacy in the information society, pp. 43-57, Springer, 2013.
Toon Calders, Faisal Kamiran, and Mykola Pechenizkiy. Building classifiers with independency constraints. In 2009 IEEE International Conference on Data Mining Workshops, pp. 13-18. IEEE, 2009.
L. Elisa Celis, Anay Mehrotra, and Nisheeth K. Vishmoi. Fair classification with adversarial perturba- tions. ArXiv,
2021.
10

---

Under review as a conference paper at ICLR 2022
Xinyun Chen, Chang Liu, Bo Li, Kimberly Lu, and Dawn Song. Targeted backdoor attacks on deep learning systems using data poisoning. arXiv preprint arXiv: arxiv:1712.05526, 2017.
Sam Corbett- Emma Pierson, Avi Feller, Sharad Goel, and Aziz Huq. Algorithmic decision making and the cost fairness. In Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 797-806, 2017.
Andrew Cotter, Maya Gupta, Heinrich Jiang, Nathan Srebro, Karthik Sridharan, Serena Wang, Blake Woodworth, and Seungil You. Training well gelerreerl classifiers for fairees metrics and other data-dependent constraints. In International Conference on Machine Learning, pp. 1397-1405, 2019.
Maria Dr-Artaa Artur Dubrawski, and Alexandra Chouldechova. Learning under selective labels in the presence of expert consistency. arXiv preprini 1oXiv:/807.00005. 2018.
Xiaotie Deng. Complexity issues in bilevel linear programming. In Multilevel optimization: Algo- rithms and applications, pp. 149-164. Springer, 1998.
Michele Donini, Luca Oneto, Shai Ben-David, John S Shawe-Taylor, and Massimiliano Pontil. Empirical risk minimization under fairness constraints. In Advances in Neural Information Processing Systems, pp. 2791-2801, 2018.
Dheeru Dua and Casey Graff. UCI machine learning repository, 2017. URL http://archive. ics. uci. edu/ml.
Sanghamitra Dutta, Dennis Wei, Hazar Yueksel, Pin- Yu Chen, Sijia Liu, and Kush Varshney. Is there a trade-off between fairness and accuracy? a perspective using mismatched hypothesis testing. In PMLR, 2020.
International Conference Machine Learning, pp.
Cynthia Dwork, Moritz Hardt, Toniann Pitassi, Omer Reingold, and Richard Zemel. Fairness through awareness, In Innovations in Theoretical Computer Science (ITCS), pp. 214-226, 2012.
Cynthia Dwork, Nicole Immorlica, Adam Tauman Kalai, and Max Leiserson. Decoupled Classifiers for Group-Fair and Efficient Machine Learning. In Fairness, Accountability and Transparency (FAT), pp. 119-133, 2018.
Riccardo Fogliato, Alexandra Chouldechova, and Max G Gell. Fairness evaluation in presence of biased noisy labels. In International Conference on Artificial Intelligence and Statistics, pp- 2325-2336. PMLR, 2020.
Sorelle A Friedler, Carlos Scheidegger, and Suresh Venkatasubraamanian. On the (im) possibility of fairness. arXiv preprint 10Xiv:1609.07236, 2016.
Sorelle A Friedler, Carlos Scheidegger, Suresh Venkatasubbamaniian Sonam Choudhary, Evan P Hamilton, and Derek Roth. A comparative study of fairness-enhin fairness-enhancnng interventions in machine learning. In Proceedings of the conference on fairness, accountability, and transparency, pp. 329-338, 2019.
Tianyu Gu, Brendan Dolan-Gavitt and Siddharth Garg. Badnets: Identifying vulnerabilities in the machine learning model supply chain. arXiv preprint 1708::1170006773 2017.
Pierre Hansen, Brigitte Jaumard, and Gilles Savard. New branch-and- bound rules for linear bilevel programming. SIAM Journal scientific and Statistical Computing, 13(5): 194--117, 1992.
Moritz Hardt, Eric Price, Nati Srebro, et al. Equality of opportunity in supervised learning. In Advances in neural information processing systems, pp. 3315-3323, 2016.
Elad Hazan. Introduction to online convex optimization. Foundations and Trends in Optimization, (3-4):157-325, 2016.
Ling Huang, Anthony D Joseph, Blaine Nelson, Benjamin IP Rubinstein, and Doug Tygar. Ad- versarial machine learning. In Proceedings of the 4th ACM workshop on Security and artificial intelligence, pp. 43-58, 2011.
11

---

Under review as a conference paper at ICLR 2022
Matthew Jagielski, Alina Oprea, Battista Biggio, Chang Liu, Cristina Nita- Rotar,, and Bo Li. Manipulating machine learning: Poisoning attacks and countermeasures for regression learning. In 2018 IEEE Symposium Security and Privacy (SP), pp. 19-35. IEEE, 2018.
Heinrich Jiang and Ofir Nachum. Identifying and correcting label bias machine learning. In International Conference Artificial Intelligence and Statistics, pp. 702-712. PMLR, 2020.
Nathan Kallus and Angela Zhou. Residual unfairness in fair machine learning from prejudiced data. In International Conference on Machine Learning, pp. 2439-242222222 2448. PMLR, 2018.
Faisal Kamiran and Toon Calders. Data preprocessing techniques for classification without discrimi- nation. Knowledge and Information Systems, 33(1):1-33, 2012.
Toshihiro Kamishima, Shotaro Akaho, and Jun Sakuma. Fairess--waaee learning through regular- ization approach. In 2011 IEEE 1th International Conference on Data Mining Workshops, pp. 643-650. IEBE, 2011.
Jyrki Kivinen and Manfred K Warmuth. Exponentiated gradient versus gradient descent for linear predictors. information and computation, 132(1):1-66 1997.
Jon Kleinberg. Sendhil Mullainathan, and Manish Raghavan. Inherent trade-offs in the fair determi- nation of risk scores. arXiv preprint arXiv: 2016.
Jon M. Kleinberg, Sendhil Mullainathan, and Manish Raghavan. Inherent trade-off' in the fair determination of risk scores. In Innovations in Theoretical Computer Science (ITCS), pp. 43:1- 43:23, 2017.
Pang Wei Koh and Percy Liang. Understanding black-box predictions via influence functions. In Proceedings of the 34th International Conference on Machine Learning-Volee Volume 70, pp. 1885-1894. JMLR. org, 2017.
Pang Wei Koh, Jacob Steinhardt, and Percy Liang. Stronger data poisoning attacks break data sanitization defenses. arXiv preprint arXiv: 1.00741, 2018.
Junpei Komiyama, Akiko Takeda, Junya Honda, and Hajime Shimao. Nonconvex optimization for regression with fairness constraints. In International Conference on Machine Learning, pp. 2751-2751, 2018.
Nikola Konstantinov and Christoph Lampert. Robust learning from untrusted sources. In International conference on machine learning, pp. 3488-3498, PMLR, 2019.
Matt J Kusner, Joshua Loftus, Chris Russell, and Ricardo Silva. Counterfactual fairness. In Advances in Neural Information Processing Systems, 4066-4076, 2017.
Alex Lamy, Ziyuan Zhong, Aditya K Menon, and Nakul Verma. Noise-tolerant fair classification. In Advances in Neural Information Processing Systems, pp. 294-305, 2019.
Jeff Larson, Surya Mattu, Lauren Kirchner, and Julia Angwin COMPAS dataset. https://
github. www. wwtpaa//pppbbicccccocmmm cwwpppubicccccppassseeeeseaaaeee compas- anapaass, 2017.
Bo Li, Yining Wang, Aarti Singh, and Yevgeniy Vorobeychik. Data poisoning attacks on factorization- based collaborative filtering. Advances neural information processing systems, pp. 1885-1893, 2016.
David Madras, Elliot Creager, Toniann Pitassi, and Richard Zemel. Learning adversarially fair and transferable representations. In International Conference Machine Learning, pp. 33933. PMLR, 2018.
Debmalya Mandal, Samuel Deng, Suman Jana, Jeannette M Wing. and Daniel Hsu. Ensuring faimess beyond the training data. arXiv preprint "xXx:20077000029 2020.
Ninarch Mchrabi, Fred Morstatter, Nripsuta Saxena, Kristina Lerman, and Aram Galstyan. A survey bias and fairness in machine learning. ACM Computing Surveys (CSUR), 54(6):1355, 2021a.
12

---

Under review as a conference paper at ICLR 2022
Ninareh Mehrabi, Muhammad Naveed, Fred Morstatter, and Aram Galstyan. Exacerbating algorith- mic bias through faimess attacks. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pp.
2021b.
Shike Mei and Xiaojin Zhu. The security of latent dirichlet allocation. In Artificial Intelligence and Statistics, pp. 689, 2015a.
Shike Mei and Xiaojin Zhu. Using machine teaching identify optimal training-set attacks on machine learners. In Twenty-Ninth AAAI Conference on Artificial Intelligence, 2015b.
Mehryar Mohri and Andres Munoz Medina. New analysis and algorithm for learning with drifting distributions. In International Conference on Algorithmic Learning Theory, pp. 124-138. Springer, 2012.
Luis
Battista Biggio, Ambra Demontis, Andrea Paudice, Vasin Wongrassamee, Emil C Lupu, and Fabio Roli. Towards poisoning of deep learning algorithms with back-gradient optimization. In Proceedings of the 10th ACM Workshop on Artificial Intelligence and Security, pp. 27-38. ACM, 2017.
Vedant Nanda, Samuel Dooley, Sahil Singla, Soheil Feizi, and John P Dickerson. Fairness through robustness: Investigating robustness disparity in deep learning. In Proceedings of the 2021 ACM Conference on Fairness, Accountability, and Transparency, pp. 466-477, 2021.
Arvind Narayanan. Translation tutorial: 21 fairness definitions and their politics. In Proc. Conf. Fairness Accountability Transp., New York, USA, 2018.
Ashesh Rambachan and Jonathan Roth. Bias in, bias out? evaluating the folk wisdom. arXiv preprint arXiv:1909.085/8, 2019.
Ashkan Rezaei, Rizal Fathony, Omid Memarrast, and Brian D Ziebart. Fairness for robust log loss classification. In AAAI, pp. 5511-5518, 2020.
Yuji Roh, Kangwook Lee, Steven Euijong Whang, and Changho Suh. Fr-train: mutual information- based approach to fair and robust training. In International Conference on Machine Learning, 2020.
Yuji Roh, Kangwook Lee, Steven Euijong Whang, and Changho Suh. Sample selection for fair and robust training. ArXiv, abs/2110.14222. 2021. 2021.
Ali Shafahi, W Ronny Huang, Mahyar Najibi, Octavian Suciu, Christoph Studer, Tudor Dumitras, and Tom Goldstein. Poison frogs! targeted clean-label poisoning attacks neural networks. In Advances in Neural Information Processing Systems, pp. 6103-6113, 2018
D Solans, B Biggio, and C Castillo. Poisoning attacks on algorithmic fairness. In European Conference on Machine Learning and Knowledge Discovery Databases, ECML PKDD 2020, volume 12457, pp. 177. Springer Science and Business Media Deutschland GmbH, 2021.
Jacob Steinhardt, Pang Wei W Koh, and Percy $ Liang. Certified defenses for data poisoning attacks. In Advances in neural information processing systems, pp. 3517-3529, 2017.
Octavian Suciu, Radu Marginean, Yigitcan Kaya. Hal Daume III. and Tudor Dumitras. When does machine learning (FAIL)? generalized transfcrability for evasion and poisoning attacks. 27th (USENIX) Security Symposium (UUSENIX) Security 18), pp. 1299-1316, 2018
Bahar Taskesen, Viet Anh Nguyen, Daniel Kuhn, and Jose Blanchet. A distributionally robust approach to fair classification. arXiv preprint arXiv:2007.095300 2020.
Hao Wang, Hsiang Hsu, Mario Diaz, and Flavio Calmon. To split not split: The impact of disparate treatment in classification. IEEE Transactions on Information Theory, 2021.
Serena Wang. Wenshuo Guo, Harikrishna Narasimhan, Andrew Cotter, Maya Gupta, and Michael I Jordan. Robust optimization for fairness with noisy protected groups arXiv preprint arXiv:2002.099 09343, 2020.
13

---

Under review as a conference paper at ICLR 2022
Michael Wick, Jean- Baptiste Tristan, et al. Unlocking fairess:: a trade-off revisited. In Advances in Neural Information Processing Systems, pp. 8783-8792, 2019.
Han Xiao, Huang Xiao, and Claudia Eckert. Adversarial label flips attack on support vector machines. In ECAI, pp. 870-875, 2012.
Huang Xiao, Battista Biggio, Gavin Brown, Giorgio Fumera, Claudia Eckert, and Fabio Roli. Is feature selection secure against training data poisoning? In International Conference on Machine Learning, pp. 1689-1698, 2015a.
Huang Xiao, Battista Biggio, Blaine Nelson, Han Xiao, Claudia Eckert, and Fabio Roli, Support vector machines under adversarial label contamination. Neurocomputingg 160:53 62, 2015b.
Mikhail Yurochkin, Amanda Bower, and Yuekai Sun. Training individually fair ml models with sensitive subspace robustness. In International Conference on Learning Representations, 2019.
Muhammad Bilal Zafar, Isabel Valera, Manuel Gomez Rodriguez, and Krishna P Gummadi. Faimess beyond disparate treatment & disparate impact: Learning classification without disparate mistreat- ment. In Proceedings of the 26th international conference on world wide web, pp. 1171-1180,
2017a.
Muhammad Bilal Zafar, Isabel Valera, Manuel Gomez Rogriguez, and Krishna P Gummadi. Faireess constraints: Mechanisms for fair classification. In Artificial Intelligence and Statistics, pp. 962-970. PMLR, R, 20170 7b..
Muhammad Bilal Zafar, Isabel Valera, Manuel GodezzRodriguez, and Krishna P. Gummadi. Fairness constraints: flexible approach for fair classification. Journal of Machine Learning Research, 20 (75):1-42) 2019. URL http: / jmlr.
v20 2-26222222222 html.
Rich Zemel, Yu Wu, Kevin Swersky, Toni Pitassi, and Cynthia Dwork. Learning fair representations. In International Conference on Machine Learning, pp. 325-333, 2013.
Brian Hu Zhang, Blake Lemoine, and Margaret Mitchell. Mitigating unwanted biases with adversarial learning. In Proceedings of the 2018 AAAI/ACM Conference AI, Ethics, and Society, pp. 335- 340, 2018
Han Zhao and Geoff Gordon. Inherent tradeoffss in learning fair representations. In Advances in neural information processing systems, pp. 15649-1555 15659, 2019.
Chen Zhu, W Ronny Huang, Hengduo Li, Gavin Taylor, Christoph Studer, and Tom Goldstein. Transferable clean-label poisoning attacks deep neural nets. In International Conference Machine Learning, pp. 7614-7623, 2019.
14

---

Under review as a conference paper at ICLR 2022
LIST OF TABLES
Accuracy and fairness gap of unconstrained models and fair models on test data COMPAS, Adult and synthetic dataset
2 List of Notations
17
3
Distribution of data points COMPAS dataset
23
4
Distribution of data points Adult dataset
23
5
Distribution of data points Synthetic dataset
24
6
Distribution of data points MEPS dataset
24
7
Test accuracy all the algorithms on all the datasets
30
8 Fairness gap on test data all the datasets
31
9 Test accuracy of the models when D. is unknown COMPAS dataset
32
LIST OF FIGURES
Test accuracy COMPAS dataset
2 Fairness gap on the unconstrained model - COMPAS dataset
3 Effect of fairness guarantee on robustness across groups COMPAS dataset
4 Effect of fairness guarantee on training accuracy across groups COMPAS dataset
5
Training accuracy for group-based model COMPAS dataset
6
Test accuracy COMPAS dataset
29
7
Test accuracy Adult dataset
32
8
Test accuracy Synthetic dataset
33
9
Test accuracy MEPS dataset
33
10
Effect of fairness level on robustness across groups COMPAS dataset
34
11
Effect of fairness level d robustness across groups Adult dataset.
35
12
Effect fairness level on robustness across groups Synthetic dataset
36
13
Effect of fairness level 5 robustness across groups MEPS dataset
37
14
Test accuracy of unconstrained and fair models with respect to equal opportunity COMPAS dataset
38
15
Accuracy on training data for the minority group- COMPAS dataset
39
16
Accuracy on training data for the minority group Adult dataset
40
17
Accuracy on training data for the minority group - SSnthhtic dataset
18
Accuracy on training data for the minority group MEPS dataset
42
19
Fairness gap on the unconstrained model COMPAS dataset
43
20
Fairness gap on the unconstrained model Adult dataset
43
21
Fairness gap on the unconstrained model Synthetic dataset
44
22
Fairness gap on the unconstrained model MEPS dataset
44
23
Distribution of D, COMPAS dataset
45
24
Distribution of D, Adult dataset
46
25
Distribution of D, Synthetic dataset
47
15

---

Under review as a conference paper at ICLR 2022
26
Distribution of D, MEPS dataset
48
16

---

Under review as a conference paper at ICLR 2022
A
TABLE OF NOTATIONS
Table 2: List of Notations
Symbol
Description
Where it defined
X
Features space
Section
Label space
Section
X
Random variable associated with features
Section
Random variable associated with lables
Section
(X.Y)
Underlying distribution of the data
Section
Training dataset
Section
N
Size of the training dataset
Section
Clean training dataset
Section
Size of the clean training dataset
Section
Pr
The odversarially- etsarially-choseu poisening dataset of the
Section
D,
the training
Prp
Compating probability empirically over a dataset T)
Section
Dr
A data points where feature vectors of D, are sampled from
Section
Piss
Test dataset
Section
Sensitive/proteected attribute
Section
Scositive/protcctac attribute Space
Section
Guaranteed fairess level on training data
Section
Fairness gap
Ago
Fairness gap under equalized odds
Section
C)
Fairness constraint fo on dutaset
Section
Model parameters
Section
Parameter space
Section
fo
Classification model parameterized Loss of fa on data [2: g)
Section
Section
((
fy on
Optimal model parameters
constrained
Eq. (2)
Lagrange multiplier (penalty parameter)
Section
ou ((r)))))
Adding copies of the data point (z. to
Section
M
Maxinum loss under the uptimal
Eq.
M (P))
The imposed loss hy poisoning dataset D2 the fair model
Fig. (4)
The data point selected by Algorithm at step
Section
The model parameter chosen by Algorithm step
Section
F(DL)
Fensible set of IDp
Section
n
Learning
Algorithm
The dataset produced by Algorithm for introducing adversarial bias into the training dataset
Section
Regreu(T)
Regret of Algorithm after steps Loss of model fo under the optimal attack
Section
U()))
Appendix C.1
U
Minimum loss under the optimal adversarial bias minf_1 U'(0)
Appendix C.1
g.10)
The loss function for online learning algorithm step
Appendix
Optimal model parameters for minimizing the curmulative loss - Learning
((f)
Appendix C.1
time Algorithm used in the proof Corollary
Appendix C.I
Upper bound on the diameter of Upper bound
Appendix C.I
subgradients
Appendix
The relaxation for the fairness gap of equalized odds Lincur loss of model Ja on data point (2.3)
Appendix C.2
Gid:
Appendix C.2
pa
data points from group with The numher of data points in Dv.
Appendix
Appendix C.2
R0, (D)
Average linear loss fo for data points
Appendix C.2
A Spog
Fairness gap under equal opportunity
Appendix E.7
17

---

Under review as a conference paper at ICLR 2022
B RELATED WORK
In this paper, we aim to analyze the effect of achieving group faimess on the robustness of the model against the adversarially chosen outliers. Thus, in the following, we review the fair machine learning, the robustness of the unconstrained model against outliers, and the recent study about learning fair models under the noisy training data, along with the studies about the trade-off between accuracy and fairness.
Fairness in Machine Learning A classifier that is learned by minimizing the overall cumulative loss might not perform well on one sensitive group (usually the minority group) when the distribution of features per each class is different across groups. In order to address this problem, multiple definitions of fairness are proposed in the literature. Examples include metric equality across sensitive groups (Hardt et al., 2016; Calders et al., 2009), individual fairness (Dwork al., 2012), causality (Kusner et al., 2017), and many techniques to satisfy group- based fairnsss (which is the focus of this paper) such as pre-processing methods (Zemel et al., 2013; Madras al., 2018), in-processing methods (Kamishima et al., 2011: Zafar et al., 2017a;b; Agarwal et al., 2018), and post- processing methods (Hardt al., 2016). Pre-processing methods aim finding a new representation of data such that it retains as much information of input features as possible, except those which can lead bias. In-processing methods enforce fairness during the training process, for example, by incorporating the fairness constraints into the objective function as regularization term. Post- processing methods correct the predictions of given trained model, without modifying the training data or the training process. A slightly different approach from these three to achieve fairness is adversarial training (Zhang et al., 20, where the learning objective is formulated as a game between two players with one player trying to optimize for accuracy and the other strives to achieve fairness. Please refer to (Mehrabi ct al., 2021a) for a recent survey on methods to achieve fairness. In this work, we foeus the notion of Equalized odds (Hardt al., 2016) and train fair models using in-processing approaches (Agarwal et al., 2018; Cotter et al., 2019; Rezaei et al., 2020; Zhang et al., 2018 8), post-processing (Hardt et al., 2016).
Data poisoning attack Adversarial bias against unconstrained models is also known in the literature as data poisoning attacks when the appearance of an adversary in the system is emphasized. Machine learning systems are susceptible to data poisoning attacks. The adversary's 's objective is to degrade the overall test accuracy of the model (Biggio et al., 2012: Mei & Zhu, 2015a; Jagielski et al., 2018; Li et al., 2016; Mei & Zhu, 201 5b; Koh et al., 2018: 8; Koh & Liang, 2017) or to increase the loss on specific test data points or small sub-populations (Gu et al., 2017; Chen et al., 2017; Burkard Lagesse, 2017; Shafahi et al., 2018; Koh & Liang. 2017; Suciu et al., 2018). In our paper, we study the impact of adversarial bias on the overall accuracy of fair models without considering the role of an adversary (capacity, knowledge, etc). Steinhardt et al. (2017) propose an optimal algorithm for poisoning attacks on (unconstrained) convex models, given a set of feasible poisoning data points. The algorithm relies on the assumption that test loss of the target model can be approximated as training loss of the model on clean data (assuming Drest. is drawn from the same distribution as the clean training data D.). Our algorithm is inspired by this work and uses the same online learning framework. Note that, when À = 0 in Algorithm 2, it is equivalent to the algorithm in (Steinhardt al., 2017).
In our setting of adversarial sampling bias, both the feature vectors and the labels are not modified. In clean-label data poisoning attacks (Shafahi et al., 2018), the attacker manages reduce the accuracy of target examples via injecting the correctly labeled data with modified features. Another typical data poisoning attack allows the attacker to change both features and labels of the poisoning data. This is first studied in the context of SVMs by Biggio et al. (2012), and has subsequently been extended to linear and logistic regression (Mei & 7hu, 2015b), topic modeling (Mei & Zhu, 2015a), collaborative filtering (Li et al., 2016). and neural networks (Koh & Liang, 2017). In our setting, we assume the features cannot be modificd, as we focus on the most practical scenario in decision-making processes that move toward automation. An interesting future direction would be to allow changes of features and introduce adversarial bias using the gradient- based algorithm. Given a larger space for finding the adversarial bias, it is likely that we would observe a larger accuracy drops for fair models.
Instead of reducing the accuracy, Solans et al. (2021) and Mchrabi et al. (2021b) develop poisoning attacks where the attacker's objective is to increase the disparity in the performance of the model
18

---

Under review as a conference paper at ICLR 2022
across different groups i.e., increase the unfairmess. The key difference in our work is that adversarial bias is introduced to degrade test accuracy of fair models, whereas the algorithms in (Solans et al., 2021; Mchrabi et al., b021b) degrade the fairness of models trained without any fairnsss constraints.
Learning Fair Models from Noisy Training Data In most practical scenarios, the training data used for learning models might be biased (under-representation bias) and/or noisy (with mis-labeling). The mis-labeling phenomenon can be random or adversarial. Mislabeling can be seen as a specific case of adversarial labeling bias, where labels of data points from only certain part of the population are flipped with some probability. Similarly, under-representaaion bias can be considered as a specific case of adversarial sampling bias. Multiple works in the literature study the impact of noisy and biased data on machine learning.
Calders & Žliobaité (2013) show that learning an unconstrained model from training data with under-representation and mislabeling bias results in biased predictions test data. Fogliato et al. (2020) show the effect of noise in labels on predictive bias and the evaluation of faimess metrics of the unconstrained model without any assumption on the structure of noise. Kallus & Zhou (2018) () consider the case of systematic censoring in training data (a form of sampling bias) due to which, the classifier that seeks to achieve fairness by equalizing fairness metrics across sensitive groups can still be unfair on the population. We also show similar result in Table I that learning models on training data with adversarial bias increases their fairness gap on the test data.
Under varying assumptions, multiple works (Blum & Stangl, 2020; Jiang & Nachum, 2020; De- Arteaga et al., 2018; Lamy et al.. 2019; Friedler et al., 2019; Rambachan & Roth, 2019) have proposed strategies to account for under-representtaiin bias and mislabeling while learning models. De-Arteaga et al. (2018) study selective label bias, where true outcomes corresponding to a certain label cannot be learned, such examples cannot be added to the training data. The authors propose a method for augmenting the dataset with human expert predictions to mitigate this kind of bias. Jiang & Nachum (2020) propose re- re-weighting strategy for recovering the optimal classifier on unbiased data from training data with labeling bias. When uniform random noise is present in the sensitive attribute, it is shown that demographic parity (DP) gap of a fair classifier test data increases (Lamy et 2019). The authors propose a method to compute the exact level of DP gap that needs to be imposed on training data, for achieving a target DP gap on the test data. Blum & Stangl (2020) consider a training set corrupted by under-representatioo and/or labeling bias. Assuming access to an infinite number of samples and learning different classifiers for different sensitive groups, this work shows that ERM with Equal Opportunity constraint on the biased data can recover the Bayes-optimal classifier for the true data distribution. Friedler et al. (2019) show a slight variation in the fraction of examples from each group can affect the performance of a fair classifier. Rambachan & Roth (2019) consider a specific sampling bias against group which results in the selection of more samples from that group in the training data. In this case, the more biased the decision-maker is against a group, the more the algorithmic decision rule favors that group.
All the above works (Blum& & Stangl, 2020; Jiang & Nachum, 2020; De-Arteage et al., 2018; Lamy et al., 2019; Friedler et al., 2019; Rambachan & Roth, 2019) assume that the noise and bias in the training data is uniform distribution of mnder-represennatioommissaaaa
over subspace of points and study the consequences of learning from training data with such bias. These results cannot translate our case of adversarial bias we consider non-uniform bias over the input space, and bias is introduced with the specific intention of reducing test accuracy.
Several fair learning algorithms have been proposed achieve different robustness properties. Wang et al. (2020) and Celis et al. (2021) propose algorithms robust to noise in the sensitive attribute, which violates our assumption on unchanged feature vectors. Distributionally robust algorithms studied in (Rezaci et al., 2020; Taskesen et al., 2020) output classifiers that are fair when the true data distribution is slightly different from the estimated one. These approaches might fail to defend in the worst-case adversarial bias as the assumptions on data distributions are not satisfied; we show this observation for the algorithm proposed in (Rezaci et al., 2020) in the evaluation. Similarly, Mandal et al. (2020) study fair and robust algorithms that minimize distributionally robust loss and are fair with respect to a class of distributions. This class of distributions are weighted perturbations of the training samples. Roh et al. (2020) propose GAN-based robust and fair learning algorithm assuming an additional clean dataset is available. It aims to achieve robustness and fairness at the same time but lacks theoretical guarantees for both robustness and fairness. For better generalization of fair
19

---

Under review as a conference paper at ICLR 2022
algorithms, Cotter et al. (2019) propose to separate validation set during the training process to measure and account for fairesss. From Table I, we observe that this algorithm has a smaller accuracy drop in the presence of adversarial bias yet fails to be fair on test data. Nanda et al. (2021) study robust and fair machine learning algorithm with respect to the adversarial perturbation at the test time which differs from our setting. The concurrent work by Roh et al. (2021) proposes a robust and fair machine learning algorithm that might be used to solve the issues raised by our paper.
Pairness-Accurae Trade-offs Imposing fairness constraints might come at cost the model's performance. The effect of fair classification accuracy and the compatibility of various definitions with each other have been studied in some related works (Corbett- Davies et al., 2017; Kleinberg et al., 2017). Kleinberg et al. (2017) show that it is impossible to achieve equal calibration, false positive rate, and false negative rate if the fraction of positive labeled examples is different across sensitive groups. Corbett-Davies decision rules that satisfy fairness definitions (statistical parity, conditional statistical parity, predictive equality). Thus, imposing fairness constraints has cost model accuracy. In Section 5, we show that adversarial bias amplifies the cost of fairness. We believe that this observation would motivate further study about the trade-off between faimess and accuracy in the worst-case bias setting.
al. (2017) show that the optimal decision rule is different from the fair
Under certain assumptions on bias in data and the underlying data distribution, fairness and accuracy are not always in tension discussed in (Wick al., 2019; Dutta al., 2020). These works (Wick et al., 2019; Dutta et al., 2020) argue that the reason for the seeming existence of trade-off between fairness and accuracy is due measuring the wrong or biased datasets (which is the only information that is available). Had there been an unbiased dataset available, classifiers could achieve both fairness and accuracy simultaneously without any trade-off. The sampling bias and labeling bias are particularly highlighted in (Wick et al., 2019) and it is mentioned that measuring the fairness and accuracy on datasets with such bias will reflect a trade-off. It was shown in (Dutta et al., 2020) that there exists distribution for which classifier learned on (biased) observed data can be both perfectly fair and accurate. In our paper, we do not have any assumptions about bias already existing in the data set. We introduce adversarial bias on the given training data (potentially already biased) and study the robustness of the fair models in the presence of the adversarial bias setting by measuring the relative accuracy drop on the test data (without adversarial bias).
20

---

Under review as a conference paper at ICLR 2022
C SUPPLEMENTARY THEORETICAL RESULTS
C.I PROOF FOR THEOREM
Proof. We should point out that in this proof we follow the approach of (Steinhardt al., 2017). Assume T en is the time horizon. We have Dj = "l),""")." (x" y²)}} as the data set produced by Algorithm 1, Also, 0f is the parameter chosen by the algorithm at the 1-th step. First, from max-min inequality we have:
M def max min Dp
D(0:DeUDp))
A. en (x.))Epp
E ((0.De
7
min max Dp
=(,) en
Σ (a.j)E,,
A ((,
TI
Furthermore, for given we define:
((0)
def
max
C(0; (DD,)
Σ
Dp
(2,))ED,
[():
max [e (C-((0xx,)) + A (0, ((x,))) (2.))EF(D.)
n2
We define U = min U(t"). Note that for any given 8, we have M S (t). More specifically, we have M - U*
From the definition of M for any set, including D we have
C(0, ((; A
min
Σ
A0, U (()
M(DP) s M
n
en (a.y)Ep;
Let us define T different functions
(0) 1 C.) +e E(0:x'+1 11att,,,,11
+1(t))+ + A(0, D. U Ul(xtt1 (1())))
(6)
for 0 < < T. Let us define
T
Ø = argmin DE0
9c(
Note that we have
2219
M(D)) s M2 SU < Σ ((0)
T
Finally, from the definition of regret have:
-- (0')
1- (0)
Regret
T
T
T
which consequently completes the proof of the theorem.
C.2 OPTIMALITY CONDITIONS FOR THE SOLUTION OF PROBLEM (4)
In this section, we show under which conditions, our algorithm finds the (nearly) optimal solution for problem (4). We first state direct consequence of Theorem for no-regret algorithm which results from a convexity assumption for functions ge (#). We then explain under what conditions this convexity assumption is valid.
21

---

Under review as a conference paper at ICLR 2022
Corollary 1. Under the assumption that (i) loss function E is convex in 8, (ii) A D) is convex in and (iii) Ti GVi for 1 S $ Algorithm 1 produces the near optimal dataset D.. such that
d
3Gd
M M S Ven
(7)
where Tt step size at time t. is an upper bond on the diameter of O and G is an upper bound on the norm of the subgradients of 9t over Q i.e., V. (0)l S G.
Proof. First note that Algorithm I exactly runs online gradient descent algorithm for go func- tions. From the assumptions and (ii), we conclude that functions gr (0) are convex. The theoretical guarantee of the online gradient descent algorithm for convex functions (Hazan, 2016) allows us to bound the average regret
Regret(T) T
3Gd VT
where is an upper bond on the diameter of θ and G is an upper bound on the norm of the subgradients of 9r over θ, i.e., [[V], S G. Finally, the proof is concluded from this bound for the regret and the result of Theorem 1.
Next, we discuss the optimality conditions for linear classifiers with a convex loss, e.g., {(;; x, v) max(0, x)) for SVM. In paper, we focus equalized odds which is non-convex. We adopt simplification proposed by Donini et al. (2018) to reach convex relaxations of loss and fairness constraint. Instead of balancing prediction error, Donini al. (2018) propose fairness definition as balancing the risk among two sensitive groups Following the same idea. we define the linear loss as (e.g., 4 = (1 - fo(x)) /2 for SVM). Based on the linear loss, the convex relaxation for the fairness gap of equalized odds is defined as follows:
Í(0,D) = Rt (0, D) R+ R D) - RR - (0, -R- -
2
for Ra.*(A, (0, = n.. (( 4(0;; x. y) where D is the set of data points from group with label y in DD and Ny.s = [D..>] To find the optimal Dp for the EO fair model, in Eq. (4), we replace loss with a convex loss (e.g. Hinge loss) l and replace A (fo; D) with the convex relaxation ( D). Hence, Algorithm produces the nearly optimal data set D such that has the maximal damage the fair model under approximations.
As a future research direction, one could try to design new online algorithms that achieve small regrets in the non-convex setting under better approximations of the fairness constraint. Our framework can then utilize such online algorithms to further investigate the effect of adversarial bias on the robustness of models with fairnsss constraints.
C.3 PSEUDOCODE FOR THE ALGORITHM FROM SECTION 3
For the sake of completeness, we present the full pseudo-code for our algorithm proposed in Section 3,
Algorithm
1: Input: Clean data De. n = DDll. feasible set F(Dx), en (the size Dp,), penalty parameter (Lagrange multiplier) X, learning rate 1)-
2: Output: D
3: Initialize 8
4: for t 1,... en do
5:
(x', v.) t argmax (a.))FF(D)) [c- [C-E(8--11)) ((0--1;I,8) + A A ( 10 ((x
6:
Dp Dp U ((x",
7: g¹ - gt-1 (C(0--1 te- Ve(0t-1 ('''='),'',''))
8: end for
22

---

Under review as a conference paper at ICLR 2022
Table 3: Distribution of data points in clean training dataset and Dx
COMPAS dataset.
Clean
Dx
y
y
+
0
28.5%
31.8%
0
29.0%
31.1%
8
32.5%
7.2%
8
16.0%
23.9%
Table 4: Distribution of data points in clean training dataset and Dr
Adult dataset.
Clean
Dr y
y
y =
y =
+
8 0
48.5%
16.5%
8 = 0
45.0%
23.4%
32.3%
2.6%
5
1
27.2%
4.4%
D FAIR MACHINE LEARNING ALGORITHMS
The post-processing approach is the first proposed algorithm to achieve equalized odds (Hardt et al., 2016). The fair model obtained by adjusting a trained unconstrained model so as to remove the discrimination according equalized odds. The outcome of this approach is randomized classifier that assigns to each data point a probability of changing the prediction output by the unconstrained model, conditional on its protected attribute, and predicted label. These probabilities are computed by a linear program that optimizes the expected loss.
Many methods have been proposed to achieve fairness in machine learning (see (Mehrabi al., 2021a) for recent survey). The reductions approach proposed by (Agarwal et al., 2018) trains fair randomized classifier over a hypothesis class by reducing the constrained optimization problem to learning a sequence of cost-sensitive classification models. Cost-sensitive classification is used in this as an oracle to solve classification problems resulted from two-player game: one player (primal variables) minimizes the loss function; the other player (dual variables) maximizes the fairness violation (constraints). Similarly, the fair learning algorithm proposed (Cotter et al., 2019) is also based two-player game. One player optimizes the model parameters training dataset to minimize the loss, and the other player enforces the constraints on an independent validation dataset instead of training data. Different from the fair algorithms based the two-play game, adversarial debiasing (Zhang et al., 2018) is proposed to learn a classifier to maximize prediction accuracy and simultaneously reduce adversary's ability determine the protected attribute from the predictions. This approach leads to a fair classifier as the predictions cannot carry any group discrimination information that the adversary can exploit. (Rezaci et al., 2020) trains fair classifier that is (distributionally) robust when the true data distribution is different from the distribution estimated on training data but their statistics match. The method is applied particularly for classifier using logarithmic loss, where due to the strong duality of the optimization problem, closed-form solution can be derived.
E SUPPLEMENTARY EXPERIMENTAL RESULTS
For the following section, we present the detailed experimental results COMPAS, Adult, Medical Expenditure Panel Survey (MEPS) and synthetic datasets. All the results on COMPAS dataset are averaged over 100 runs with different random seeds. On Synthetic, MEPS and Adult datasets, all the results are averaged over 50 runs with different random seeds.
E. DETAILS OF DATASETS
We use four datasets in our evaluation, their details are described below.
COMPAS COMPAS (Larson et al., 2017) dataset contains 5278 data samples. The classification task is to predict recidivism risk from criminal history and demographics. We consider race as the sensitive attribute and include records only with white/black as race. There are 3175 records (60.2%) for the sensitive attribute as white. Among the white group. 52.3% have positive labels while among the black group, this number is 41.9% Overall, there 2483 records (47%) are labeled positive.
23

---

Under review as a conference paper at ICLR 2022
Table Distribution of data points in clean training dataset and Dx Synthetic dataset.
Clean
Dx
y
y =
+
0
18.1%
36.3%
0
18.1% 1%
36.5%
8 31.9%
13.7%
8
31.9%
13.5%
Table 6: Distribution of data points in clean training dataset and Dx MEPS dataset.
Clean
Dr. 1/
y
y
y y= +
0 8.2%
30.7%
8
=
0
13.0%
45.7%
8 = 1 13.1%
28.0%
8
17.6%
23.7%
Pre-processing A model trained with the original dataset can only achieve low accuracy (66.6% for the Logistic regression model, compared to the constant prediction classifier that can achieve 53% accuracy). which does not help the understanding of the model's behavior in the presence of adversarial bias. To get rid of the noise that exists in the dataset, we pre-process the dataset as follows: we train an SVM model with RBF kernel on the entire dataset and only keep 60% of the data points which have the smallest loss. To create the training data, test data Drest and DR. we randomly split the clean data in the corresponding ratio 4:1:1. Hard examples (the left-out data points) are added to De.
Data distribution The data distribution of points in the clean training dataset and Dr. after pre- processing are presented in Table 3. The numbers are the average values over all the datasets we evaluated on. On average, the training data contains 2111 samples, Diest 528 samples. Dx consists of 2639 samples out of which 2112 are hard examples. A Logistic regression model trained on the clean data achieves on average 94% accuracy on test data.
UCI Adult (Census Income) Adult dataset (Dua & Graff, 2017) includes 48,842 records with 14 attributes such as age, gender, education, marital status, occupation, working hours, and native country. The (binary) classification task predict if a person makes over $50K a year based on the census attributes. We consider gender (male and female) as the sensitive attribute. In this dataset, 66.8% are males, and 23.9% are labeled one, i.e having an income over $50K a year, Among male samples, 30.4% are positive samples; for the females, this number is 10.9%.
Pre-processing model trained on this dataset generally achieves below 90% accuracy (Logistic regression: 85.3%, 2-layer fully connected neural network with 32 hidden units each layer: 85.3% on training data, compared a constant prediction classifier that can achieve 76. accuracy). To enhance the model accuracy,
apply similar pre- rre-processing steps on COMPAS: SVM model with Linear kernel on the entire dataset and keep 90% of the data points which have the smallest loss. The number of females with income above $50K is small; hence randomly split 1/2 of the data for Dx. Of the remaining data, 70% are used for training data and 30% for D Hard examples (the left-out data points) added to Dx.
train an
Data distribution The data distribution of the points in the clean training dataset and Dj after pre- processing presented in Table 4. The numbers the average values over all the datasets evaluated on. On average, the training data contains 15385 samples, Drest 6594 samples. Dx consists of 26863 samples. The training data maintains approximately the same fractions of males and females as in the original dataset. A Logistic regression model trained on the clean data achieves on average 94% accuracy on test data.
MEPS dataset Medical Expenditure Panel Survey (MEPS) dataset(mep; ahr) includes 15.675 records with 44 attributes. The classification task is to predict annual hospital utilization (positive label indicates at least 10 visits). We use the same preprocessing in IBM's AI Fairness 360 (Bellamy et al., 2018) and use race (white or noi-white) as the sensitive attribute.
Pre-processing The dataset contains 83% positive samples and 17% negative samples. A logistic regression classifier trained on this data achieves low balanced accuracy (96% for the positive class, and 36% for the negative). Hence, subsample and keep only 50% of the positive class (for both
24

---

Under review as a conference paper at ICLR 2022
groups). We further proceed to train SVM model with Linear kernel and keep 80% of the data points which have the smallest loss. We randomly split 3/4 of the data for Dx. Of the remaining data, 75% are used for training and 25% for Dust The left-out data points are added to 2x.
Data distribution The data distribution of points in the clean training dataset and Dr. after pre- processing presented in Table 6. The numbers are the average values over all the datasets evaluated on. On average, the training data contains 1372 samples, Drest 458 samples. Dr consists of 7321 samples out of which 1381 are hard examples. A Logistic regression model trained on clean data achieves on average 93% accuracy on test data.
As described before, the real-world datasets can be noisy and unbalanced. Hence, we generate a synthetic dataset which does not affect by unbalancing and pre-processing. We used the settings proposed in (Zafar et al.. 2019). Specifically, we sample data from two following Guassian distributions p(zly = -) each feature vector x, the sensitive attribute is generated by a Bernoulli distribution: p(s = 1) p(>' = +)/(p(a'ly ly = +) + p(>'|y = ))), where x' is a rotated version of a.. We generate for each label class 1000 training data points, 500 test points and 2000 points for Dic- A Logistic regression model trained on the generated data achieves on average 87.6% accuracy on test data. We do not consider the Hard examples baseline for this dataset.
Synthetic data
N [2: 2]. [5, 1; 1; 5l) and p(ælyy +) [[[ -2], [10, 1: 31). For
Data distribution The data distribution of points in the clean training dataset and Dr after pre- processing are presented in Table 5.
E.2 IMPLEMENTATION AND PARAMETERS SELECTION
In Algorithm 1 we test with A E {c, 100c, 1000c} and show the results when = 1000c for all datasets. In Algorithm 2, we use Logistic regression models. Since measure the exact A of the model and want that A to have large impact on finding a new data point in each iteration. We choose {e, 10e, 100e) and use X 100 in the evaluation for Synthetic, COMPAS and Adult, and X = é for MEPS. For both algorithms, we use 0.001 as the learning rate.
To train fair model, we use the post-processig method (Hardt et al., 2016) and reductions ap- proach (Agarwal et al., 2018) and also fair algorithms proposed in (Zhang et al., 2018; Rezaei et al., 2020; Cotter et al., 2019). For post-procet post-processing method (Hardt et al., 2016) and reductions approach (Agarwal et al., 2018), we use the implementation of these algorithms provided in (Agarwal et al., 2018)*. For the fair algorithm proposed in (Rezaei et al., 2020), we use the implementation provided in (Rezaei et al., 2020).. We use the implementation from AI Fairness 360 library (Bellamy et al., 2018) for the fair algorithm proposed in (Zhang et al., 2018) 6, We implement the fair algorithm proposed in (Cotter al., 2019) based on TensorFlow Constrained Optimization library" 7.
Note that while the post-processing approach allows achieving exact fairness on the training data, the implementation of the fair algorithms (Cotter et al., 2019; Agarwal et al., 2018) requires strictly positive 6. We set 5 = O for the fair algorithm (Cotter et al., 2019). However, the fair algorithms (Rezaci et al., 2020; Zhang al., 2018; Cotter al., 2019) does not have strict fairness constraint that contains 8. We use default values for all hyper-parameters from the available implementation. For the fair algorithm (Zhang et al., 2018), we set the adversary loss weight to which is a hyperparameter that chooses the strength of the adversarial loss. See Eq. (1) in (Zhang al., 2018). is important to note that, the output of reduction, post-processing approaches, and fair algorithm (Cotter et al., 2019) is a randomized classifier. We, therefore, use the expected accuracy to measure the classification performance, given by
Acc(0; D)
1
[fo(z) v/. (2,0)ED
Σ
D
where fo(x) is the expected prediction of randomized classifier fo. For the unconstrained models, So the deterministic prediction.
hhttps://glt http://hhbb..mmmaaaaaaaaaaaaaaaa
http://ggghhbb..cmmmr/rttta///// "https: httpap////..ttbocooooooooooererr
zat
25

---

Under review as a conference paper at ICLR 2022
E.3 ROBUSTNESS EVALUATION
In this section, we provide the detailed results about the test accuracy and fairness gap of the target models for all datascts, as discussed in Section 5. We show that the fair models are more vulnerable to adversarial bias than the unconstrained model. In addition, the test accuracy and the faireess property of fair models are both compromised.
Test accuracy In the Table 7, we compare the effect of adversarial bias unconstrained models (without fairness constraint) with fair models trained with different fair algorithms on all datasets when the amount of bias equals 10% of the training data i... 0.1. On all the datasets, we observe a larger relative accuracy drop for all fair models compared with unconstrained models. This implies that, under the adversarial bias setting, the fairness constraints hurt the robustness of the model.
Fairness gap In Table 8, we compare the effect adversarial bias on unconstrained model (without fairess constraint) with different fair models at different ô on all datasets, when 0.1. We notice that the faireess gap of fair models trained on the biased data is larger than those of fair models trained on clean data (as shown in "Benign" row) (this observation is particularly pronounced on COMPAS, Adult, and Synthetic datasets). This implies fair models trained on biased data become less fair on the test dataset when biases are present in both adversarial sampling bias and adversarial labeling bias setting. This shows that not only does adversarial bias can cause accuracy drops, but it also able to make fair models more discriminatory on test data.
E.4 CONFLICT BETWEEN FAIRNESS AND ROBUSTNESS
In Figure 1, Figure 7, Figure 8 and Figure 9 compare the test accuracy of target model at different fractions of adversarial bias selected using all the strategies on COMPAS, Adult, Synthetic and MEPS datasets respectively. The x-axis is the ratio of the size of Dp to the size of the clean dataset and reflects the contamination level of the training set. We compare the impact of adversarial bias with baselines and adversarial bias against unconstrained models, for various e. The difference between test accuracy at 0 (benign setting) and a larger e values reflects the impact of the biasing strategy. Constant prediction always outputs the majority label in the clean dataset.
For the Adult dataset, notice that the Constant prediction baseline has good accuracy (>80%). Hence, the relative accuracy drop on the Adult dataset not as significant as that on the COMPAS dataset. However, we can still observe similar results that compared to the unconstrained models, the fair models suffer a greater accuracy drop, with our proposed algorithms perform significantly better than the baselines. The three algorithms have similar results both when the fair models are trained with (Hardt et al., 2016) and (Agarwal et al., 2018).
For the Synthetic and MEPS datasets, adversarial sampling hardly influences the unconstrained models, while some small effect is observed on the fair models. On the other hand, on Synthetic data, adversarial labeling bias has much stronger effect on the fair models than the unconstrained models. For MEPS, the difference in accuracy is smaller, yet we can still observe the accuracy drop is larger for the fair models. This is another evidence for the claim that fair models are less robust to bias than unconstrained models.
E.5 EFFECT OF FAIRNESS LEVEL ON IMPACT OF ADVERSARIAL BIAS
In Figure 10, Figure 11, Figure 12 and Figure 13, we show the effect of fairness level 8 on impact of adversarial sampling bias and adversarial labeling bias for COMPAS, Adult, Synthetic and MEPS dataset respectively. To measure the influence of fairness level 8, we generate bias using Algorithm and Algorithm 1 for both adversarial labeling and adversarial sampling settings.
We measure the test accuracy of models learned with different values of fairness level on the same biased dataset. We can observe that the drop in accuracy for the same fraction of bias is higher for models with stricter fairness constraints (smaller 5). This shows that the more fair a model tries to be, the more vulnerable becomes to adversarial bias. We also present the majority (the protected group with a larger number of samples) accuracy and minority accuracy. It is clear that the accuracy drop for the majority is more significant than that for minorities for all the cases.
26

---

Under review as a conference paper at ICLR 2022
In the Appendix E.10, we show that the algorithms choose the points with large loss from the smallest subgroup (subgroups are determined by the protected attribute and the label). As a result, in order to achieve fairness on the biased dataset, fair models are more likely to reduce the accuracy of the majority group.
On Synthetic dataset, this observation is not clear the size of the majority is not much bigger than that of the minority (54.4% vs. 45.6%). On MEPS dataset, the accuracy drop for the majority and minority is similar. From Figure 26, we notice that Dp generated by Algorithm 2 with À and Algorithm 2 with À = has a similar fraction of samples from the each group. This is because the fairmess gap of the unconstrained model on MEPS is small. In addition, the selected for MEPS is relatively small. As result, data points that have large loss also have a large weighted sum of the loss and the fairness gap. As a consequence, Dp generated by Algorithm with X = 0 and Alghorithm& 2 with À = c has a similar effect on the majority and minority of the fair models.
E.6 TRANSFERABILLTE OF ADVERSARIAL BIAS.
Table 9 shows the test accuracy of fair models when we generate poisoning data without the knowledge of the exact data points in the clean training data D. or the target model's 's architecture. Instead, we use a substitute model and a substitute dataset drawn from the same distribution. The target model's architecture used in the unconstrained model and the fair models trained with (Agarwal et al., 2018) and (Hardt et al., 2016) is the decision tree. However, to generate poisoning data, we use a logistic regression model instead of decision tree in Algorithm 1 and Algorithm 2. We observe that for both adversarial sampling and adversarial labeling, there is a similar pattern in the model performance and impact of the bias compared to the results in Table 1, where we used the knowledge of the clean training data to generate the poisoning data. This implies that the adversarial bias can still be effectively transferred to the more realistic scenarios where knowledge of the target's model and clean training data is not available to an adversary. It means, in practice, an adversary who only knows the fairness notion that the target model aims to satisfy can successfully reduce the overall accuracy of the resulting model significantly.
E.7 OTHER NOTIONS OF GROUP FAIRNESS
We present experimental results for equal opportunity to show the vulnerability of fair models under other notions of group faimess. Without loss of generality. we consider positive prediction as the advantaged outcome. Equal opportunity, relaxation of equalized odds, enforces non-discrimination among groups with "advantaged" prediction, i.e. it requires the true positive rate to be equal among all groups. We use a relaxed notion of equal opportunity, formally defined as follows:
Definition (Equal opportunity). A binary classifier fe 8-fair under equal opportunity if
A00pp (0)
Pr(fa(X) + fylS = 0, = +|- Pr(fo(X) + y/s - 1, +1 S 5, (10)
D
where, the probabilities computed empirically over the training set D. We refer Aopp as the model's empirical fairness gap under equal opportunity. A model satisfies exact fairness under equal opportunity when 8 O.
Algorithm and Algorithm 2 can be modified accordingly for equal opportunity by replacing A with A Emppp- In Figure 14, we compare the test accuracy of unconstrained model and fair models with respect to equal opportunity when varies for the reduction approach (Fair (Agarwal al., 2018), 6 = 0.01) and post-processing approach (Fair (Hardt et al., 2016), 5 0) on COMPAS dataset. We observe the same pattern as in Figure that at the same e, the accuracy drop of the fair models is significantly more than that of the unconstrained models. We can come to the conclusion that fair models trained with equal opportunity are noticeably less robust than unconstrained models. In addition, comparing the unconstrained model with fair models, as e increases, shows that the cost of fairness increases. Hence, for equal opportunity fairness notion, adversarial bias amplifies the cost of fairness.
E.8 ACCURACY ON TRAINING DATA FOR MINORITY GROUP
In Figure 15, Figure 16, Figure 17 and Figure 18, the accuracy of the unconstrained model on Dp from the minority group is compared with the corresponding accuracy of fair models with different
27

---

Under review as a conference paper at ICLR 2022
faireess level å on COMPAS, Adult, Synthetic and MEPS datasets. All fair models are trained with the reductions approach (Agarwal et al., 2018). Pp is selected using Algorithm with = for the unconstrained model for both adversarial labeling and adversarial sampling settings. On all datasets, we can observe that, for the fair model using (Agarwal et al., 2018), as the value of & decreases, the accuracy of the model increases on Dp and decreases clean training data. This implies adversarial bias reduces fair models' ability to learn from clean data on the minority group.
E.9 FAIRNESS GAP OF THE UNCONSTRAINED MODEL ON BIASED TRAINING DATA
To investigate the effect of adversarial bias, we train an unconstrained classifier without any fairness constraints and measure the faimess gap A (0; D. U (D))) p) of the poisoned training dataset generated by different algorithms. Figure 19, Figure 20, Figure 21 and Figure22 show the results for all datasets. We observe correlation between the effect of the bias and the corresponding fairness gap on the training data. For the baselines (Label flipping, Random sampling, Hard examples), the slight increase in A corresponds to small accuracy drop on the test data. For our biasing strategies, A is much larger and at the same time, the corresponding test accuracy is also significantly lower than observed for the baselines.
E.10 DISTRIBUTION OF Dp
In Figure 23, Figure 24, Figure 25, and Figure 26 we show group membership based on the protected attribute and labels of the data which are generated via different biasing strategies. The number of samples with y of labels and the protected attribute. As shown in each figure, the biasing algorithms in the first two rows more effective compared with baselines in the second row. As shown in sub-figures (a)-(f), in more effective strategies, most data points in Dp are from the smallest subgroup (positive labeled points from the minority).
(s 0, y
for MEPS) is the smallest among the four combinations
E.11 PERFORMANCE OF ALGORITHM WITH 100e ON ADULT DATASET
We notice that there are accuracy fluctuations for the fair models evaluated on the 'Dp selected by Algorithm with 100c on the Adult dataset. Recall that, the algorithm selects data from the Dx without replacement. In each iteration, it selects the data point that maximizes the classification loss plus the fairness gap (as at Line Algorithm 2 with À 100c has significant preference to select data that would result in large fairness gap. Thus, it chooses data that would fall into the smallest subgroup in the training set. This shown to be very effective in the case of COMPAS dataset and can lead a sharp decrease in the model accuracy even for small 6 (see Figure 1). However, this greedy algorithm in the case of small Dx. and no repetition in the Dp. can result in the degradation of the impact of the adversarial bias for larger values, as we see in Figure 7.
Algorithm 2). As shown in Figure 23, Figure 24 and Figure 25,
In more detail, the reason behind the Algorithm 2 with À 100e for larger on the Adult dataset is the following. In the adversarial sampling setting, the size of the smallest subgroup (y = + and 1) in the D& only equivalent to 7.69% of Dp. For larger values of Algorithm 2 with A = 100c will choose data from other subgroups, which cannot further harm the model accuracy, thus reduces the effect of the adversarial bias.
In the adversarial labeling setting, with large c, the number of Dr is larger than the size of subgroups with positive labels (y = +) in De; typically when c = 0.2. ID,l > 3000 whereas the number of samples with y in D. is 2943 on average. Relying on choosing points to select data points to maximize A results in the possibility of choosing points from any subgroups with positive labels (as shown in Figure 16(b)), since data points can dominate any of these subgroups.
In summary, the fluctuation in the figures is due to the significant effect of maximizing the fairness gap. In fact, in both adversarial sampling and labeling settings, Algorithm 2 (A = 100e) achieves the same performances with a smaller e as the other algorithms with larger e. These results, in effect, reflect the effectiveness of the algorithm.
28

---

Under review as a conference paper at ICLR 2022
Unconsttrainel Model Adv. Sampling
Fair (Hardt al. 2016) Adv. Sampling
Fair (Agarwal al, 20138) Adv. Sempling
Tett Accescy
0.5
0
0.15
0.1
0.15
0.2
0.05
0.1
0.15
0.2
0.03
11.1
0.15
Unconstrained Model Adv. Labeling
Fair (llad al. 2016) Adv. Labeling
Fair (Agorwal er al. 2018) Adv. Labeling
0.9
Accursyy
0.8
0.7
0.5
0.05
0.1
0.15
0.2
0.05
0.1
0.15
0.2
0.05
0.1
0.15
0.2
Alg. ()- 0) (Steinhardt et al., 2017)
Alc. 2 100c)
Alg. CA 1000c)
Label tipping
Randon sampling
Hard examples
Constan prodiction
Figure 6: Test accuracy of unconstrained and fair models under adversarial bias COMPAS dataset. The x-axis is the ratio of the size of biasing dataset DD to the size of clean dataset, and reflects the contamination level of training set. We compare the impact of adversarial bias with baselines and poisoning attacks against unconstrained models, for various e. The difference between test accuracy (benign setting) and larger e values reflects the impact of the biasing strategy. Constant prediction always outputs the majority label in clean dataset. The enforced fairness level 5 is 0 and 0.01 for the fair model (Hardt et al., 2016) and fair model (Agarwal al., 2018), respectively.
29

---

Under review as a conference paper at ICLR 2022
Table Test accuracy of unconstrained models and fair models (Hardt al., 2016; Agarwal et al., 2018; Rezaci et al., 2020; Cotter et al., 2019; Zhang et al., 2018) in the presence of adversarial bias all datasets, for 0.1. We report and compare the accuracy of the unconstrained models and fair models in the benign (c 0) and adversarial bias setting. When = 0, the models are trained on De. For each result in the adversarial bias setting, we report the relative accuracy drop compared with the accuracy in the henign setting (e 0). The smaller relative accuracy drop reflects the stronger robustness the model. The numbers bold are the largest relative accuracies drop of the target models against different algorithms.
Datavet
Target Model
Adversarial Sampling (t 0.1)
Adversarial Labeling 0.1)
Alg.2
Alg. 2
Alg.
Alg.
Alg. 2
Alg.
(A 0)
(A=
Unconstrained
87.6
87.4
85.1
(0.2.))
(2,9%)
Synthetic
Fair (Hardi et al., 2016)
80.0
77.2
78.9
79.9
71.0
71.1
70,9
(3.5%..)
(1.4%))
(0.1%))
(11,86L)
(I (11.%L.
(11.%-)
Fair (Agarwal 2018)
84.9
80.9
82.8
81.7
75.2
68.0
68.0
(4.7%)
(2.5%))
(3.8%))
(11.%))
(20.%.))
(20.%).)
Fair (Rezaei al., 2020)
76.1
70.2
71.4
74.2
60.9
60.1
(7.8% L)
(6.2%%)
(2.5%)
(20.98L))
(23.%
(21.%))
Fair (Cotter el al., 2019))
85.5
84.5
84,5
84.9
80.3
79.7
77.8
(1.25%))
(1.2%%
(0.7%)
(6.1%)
(6.8%)
(9.0%))
Fair (Zhang et al., 2018)
78.1
75.0
75.1
76.4
66.1
63.0
65.3
(4.0% ()
(3.8%)
(2.2%)
(15.%8
(19.%.)
(16.%1)
Unconstrained
94.3
87.6
84.7
(7.1 %..))
(10.%..)
COMPAS
Fair (Hardt al., 2016)
87.4
70.8
71.6
75.2
68.2
69.8
72.9
().))
(18.%L)
(14.%.)
(...)
(20.%))
(17.%4
Fair (Agarwal et al., 2018)
93.6
77.8
73.1
79.0(16.55
73.0
67.7
76.2
(17.56L)
(22.%
(22.%)L)
(28.%)4
(19.%64)
Fair (Rezaei et al., 2020)
84.5
63.2
64.7
68.2
60.9
60.6
66.2
(25. %))
(23.%))
(19.%..)
(28, S-L)
(28, %..%
(22.5)))
Fair (Cotter et al., 2019)
91.9
79.6
81.2
82,9
76.2
76.7
79.3
(13.%)
(12.9L)
(10.%)))
(17.%)
(17.%g
(14.%).)
Fair (Zhang et al., 2018)
81.0
70.0
66.0
72.3
67.4
64.1
70.9
(14.56
(19.%)
(11.%)
(17.%L)
(21.%)
(12.%-)
Unconstrained
94.3
94.0
89.3
(0.3% [)
(5.3% L)
Adult
Fair (Hardt et al., 2016)
92.7
89.6
90.1
91.4
84.6
(3.3%
(2.8%L)
(1.4%))
(8.7%))
(13.%
(8.5%))
Fair (Agarwal et al., 2018)
93.8
91.7
92.2
92.4
83.9
80.9
86.1
(2.2 ()-
(1.7%)
(1,5%)
(11.%)
(14.%)
(8.2%)
Fair (Rezaei et al., 2020)
84,5
78.1
79.1
78.9
70.4
64.9
76.1
(7.6%).
(6.4%)
(6.6%)
(17 (17,88)
(23.%)
(9.9%).)
Fair (Cotter al., 2019)
92.7
91.2
91.1
90.3
84.0
83.8
86.8
(1.6%))
(1.7%)
(2.6%
(9.1%)]
(9.6%..)
(6.4%.))
Fair (Zhang et al., 2018)
89.7
85.7
86.1
88.7
82.6
$1.9
(4.4% ())
(4.0%)
(L.1%)
(7.9%)
(50.%.)
(42.%
Unconstrained
92.8
91.2
88.8
(1.7% L)
(4.3% ()
MEPS
Fair (Hardt et al., 2016)
91.3
88.6
87.8
90.4
85.0
85.2
90.1
(3.05+L)
(3.8%))
(1.0%)
(6.9%)
(6.7%
(1.3%)
Fair (Agarwal et al., 2018)
92.6
89.8
88.9
91.1
85.9
86.0
90.7
(3.0%-
(4.0%
(1.6%))
(7.2%
(7.1%))
(2.0%))
Fair (Rezaei al., 2020)
88.6
75.7
76.0
86.5
74.8
74.5
86.0
(15. %)
(14,%))
(2.4%))
(16. Sk.)
(16.%).
(2.9%))
Fair (Cotter et al., 2019)
91.4
89.1
88.2
89.9
86.9
89.4
(2.5%))
(3.5%)L
(1.6%))
(4.9%)
(5.0%)
(2.2%))
Fair (7hang et al., 2018)
78.6
67.2
66.8
75.9
63.7
74.2
(15.9&
(15.%)
(3.4%))
(18.%.)
(5.6%)
30

---

Under review as a conference paper at ICLR 2022
Table 8: Fairness gap of target models on test data for 0.1. Fair models are trained using the reduction approach (Agarwal et al., 2018). The fairness gap A is defined in (1). The numbers reflect how unfair the model is with respect to the protected group in the test data. For fair models, compare numbers with (the guaranteed fairness gap on training data). The farther apart and & are, the less the fairness generalization is test data.
Dataset
Strategies
Unconstrained
Fair
Fair
Fair
Model
(6 0.1)
(6 = 0.05)
(5 = 0.01)
Benign
0.18
0.141:0.05
0.08
0.03.1:0022
Random Sampling
0.18110.0
0.14.10.04
0.08110.04
0.03
Label flipping
0. 0.004
0.07+00.4
0.07++0.02
0.10++0.03
Adv. sampling (Alg. 2, À 0)
0.17+00.0
0.08+
0.08++0.04
0.07++0.04
Synthetic
Adv. sampling (Alg. 1, À = 1000c)
0.05+10.03
0.04+10.03
0,04
Adv. sampling (Alg. 2, À = 100c)
0.0710000
0.09
0.09110.04
Adv. labeling (Alg. 2, 0)
0.2910.10
0.07100.0
0.1010004
0.11
Adv. labeling (Alg. 1, 1000c)
0.08+0.03
0.15+10.03
0.141:0.06
Adv. labeling (Alg. 2, 100c)
0.12+00.5
0.15++0.05
0.14+00.07
Benign
0.21
0.11100.06
0.08
0.06110.04
Random Sampling
0.19:10.07
0.08=0.03
0.10+0.03
0.11=00.05
Hard examples
0.19:00.8
0.09=00.03
0.11
0.13
Label flipping
0.23
0.09110.04
0.08
0.07.10.04
Adv. sampling (Alg. 2, À 0)
0.26.10.08
0.1910.07
0.2510.07
0.30.10.07
COMPAS
Adv. sampling (Alg. 1, À = 1000c)
0.16:00.05
0.20
0.22
Adv. sampling (Alg. 2, À 100c)
0.29:10.06
0.33+0.08
0
Adv. labeling (Alg. 2,
0.28
0.13
0.15
0.19
Adv. labeling (Alg. 1, À 1000e)
0.14
0.17=0007
0.16+
Adv. labeling (Alg. 2, 100c)
0.28
0.31
0.39100008
Benign
0.07
0.07
0.06+0003
0.04
Random Sampling
0.07+:0.03
0.07=00.03
0.06++0.03
0.03
Hard examples
0.08+-0.33
0.06+00.33
0.06++0.03
0.04
Label flipping
0.081:004
0.10:10.04
0.17
0.24
Adult
Adv. sampling (Alg. 2, À 0)
0.06::0.03
0.03=00.22
0.07+0.03
0. 0.12330.03
Adv. sampling (Alg. 1, X = 1000e)
0.03=00.02
0.05+0002
0.09
Adv. sampling (Alg. 2, À = 100e)
0.06++0.03
0.07+0002
0.07+00.02
Adv. labeling (Alg. 2,
0.06
0.07++0.03
0.13+00.04
0.21+-0.04
Adv. labeling (Alg. 1, À 1000e)
0.140.04
0.16:10.04
0.0
Adv. labeling (Alg. 2, 100c)
0.18=0.06
0.1660.06
0.09
Benign
0.09+00.6
0.08+10.05
0.08+L0.05
0.08
Random Sampling
0.09
0.09110.0
0.07100.05
0.08
Hard examples
0.11100.0
0.08
0.07110.04
0.08
Label flipiig
0.08+0005
0.07
0.07+00.05
0.07
MEPS
Adv. sampling (Alg. 2, İ 0)
0.09+00.5
0.10+00.6
0.20
0.14+00.08
Adv. sampling (Alg. 1, X = 1000c)
0.08
0.09
0.08
Adv. sampling (Alg. 2, À = c)
0.09
0.20
0.13
Adv. labeling (Alg. 2,
0.0810.07
0.0910.07
0.10110.07
0.09110.07
Adv. labeling (Alg. 1, À 1000c)
0.07+00.0
0.07+0005
0.07=10.04
Adv. labeling (Alg. 2,
0.11+00.8
0.10
0.09-+0.07
31

---

Under review as a conference paper at ICLR 2022
Table 9: Test accuracy of unconstrained models and fair models in the presence of adversarial bias COMPAS for 0.1. We report and compare the accuracy of the unconstrained models and fair models in adversarial bias setting when the clean training data and the target model's 's architecture are unknown. Instead, substitute dataset and a substitute model are used Algorithm and Algorithm 2. We also report the relative accuracy drop in parenthesis.
Target Model
Adv. Sampling 0.1)
Adv. Labeling 0.1)
Unconstrained
92.2 (4.6%.)
91.7 (5. (%.)
Fair (Hardt et al., 2016) (Ō = =0)
83.6 (13%%.)
82.6 (14.%.)
Fair (Agarwal et al., 2018) (Ō 0.01)
84.1 (13, %.))
82.0 (15.%4)
Uncomstrained Model Adv. Sumpling
Fair (Hlrdit et al., 2016) Adv. Sampling
Fair (Agurwal et al., 2018) Adv. Sumpling
Tes Accunicy
0.7
0.7
0.7
Unconstrained Model Adv. Labeling
Fair (Hardt al., Adv. Labeling
Fair (Agarwal et 2018) Adv. Labeling
Test Acsuracy
0.9
0.9
0.9
0.8
0.05
0.1
0.15
0.2
0.05
0.1
0.15
0.2
0.05
0.1
0.15
0.2
() (Steinhardt et al., Hard examples
2A 100x)
Alg. (A 1000k)
Random sampling
Label flipping
Constant prediction
Figure 7: Test accuracy of unconstrained and fair models under adversarial bias Adult dataset. The enforced fairness level is and 0.01 for the fair model (Hardt al., 2016) and fair model (Agarwal et al., 2018), respectively.
32

---

Under review as a conference paper at ICLR 2022
Uncoustrained Model Adv. Sampling
Für (Hardt al., 2016) Adv. Sampling
Fair (Agarwal et al. 2018) Adv. Sampling
0.9
0.9
0.9
0.8
0.8
0.8
Test
0.7
0.7
0.7
0
0.05
0.1
0.15
0.2
0.05
0.1
0.15
0.2
0
0.05
0.1
0.15
0.2
Unconstrained Model Adv, Labeling
Fair (Hardr et al., 2016) - Adv. Labeling
Fair (Agarwal et al,, 2018) Adv, Labeling
0.9
0.9
0.9
Text Accuracy
0.6
0.5
0.5
0.5
0
0.05
0.15
0.2
0.05
0.1
0.15
0.2
0.05
0.15
0.2
Alg. 2 (A () (Steinhardi et al., 2017) -- Alg. (A 1006) Alg. (A 1000c) -a- Label flipping
Random sampling
Figure 8: Test accuracy of unconstrained and fair models under adversarial bias Synthetic dataset. Constant prediction has 50% accuracy. The enforced fairness level ó is 0 and 0.01 for the fair model (Hardt et al., 2016) and fair model (Agarwal al., 2018), respectively.
Uncoustrained Model Adv. Sampling
Fair (Hardt al., 2016) Adv. Sampling
Fair (Agarwal et al., 2018) Adv. Sampling
Accurcyy
0.9
0.9
0.9
0.8
0.8
0
0.05
0.1
0.15
0.2
0.05
0.1
0.15
0.2
0
0.05
0.1
0.15
0.2
Unconstrained Model Adv. Labeling
Fair (Hardt et al., 2016)-Ade Adv. Labeling
Fair (Agarwal ot al., 2018) Adv. Labeling
0.9
0.9
0.9
Text
0.7
0.7
0.7
0
0.05
0.15
0.2
0.05
0.1
0.15
0.2
0.05
0.15
0.2
Alg. 2 (A 0) (Steinbardi et al., 2017) - Alg. 2 (A Random sampling
Alg. ( 1000e) - Label flipping Constant prediction
Hard examples
Figure 9: Test accuracy of unconstrained and fair models under adversarial bias MEPS dataset. The enforced fairness level is 0 and 0.01 for the fair model (Hardt et al., 2016) and fair model (Agarwal al., 2018), respectively.
33

---

Under review as a conference paper at ICLR 2022
Overall Adv. Sampling
Majority group Adv. Sampling
Minusity group- Adv. Sampling
Toxt Accinacy
0.8
0.8
0.7
0.7
0.7
Uncoustrained model
0.1)
0.6
Fuir (f 0.05)
0.6
0.6
0.01)
0.5
0.5
0.5
0.15
0.15
0.05
0.15
Overall Adv. Labeling
Majority group Adv. Labeling
Minutity group Labeling
0.9
0.0
0.9
Test Accuney
0.5
0.8
0.7
0.7
0.5
0.5
0.05
0.1
0.15
0.2
0.05
0.1
0.15
0.2
0.05
0.1
0.15
0.2
(a) Alg. 2 (A = 100c)
Overall Adv. Sampling
group Adv. Sampling
group Adv. Sampling
0.9
0.0
0.9
Tel Accutay
0.8
0.8
0.7
0.7
0.6
0.6
0.5
0.5
0.05
0.1
0.35
0.2
11.05
0.1
0.15
0.2
1100
0.1
0.15
0.2
Overall Adv. Labeling
Majority group Adv. Labeling
Minority group - Adv. Labeling
0.9
0.9
0.9
Ted Asnuncy
0.5
0.88
0.8
0.7
0.7
0.7
0.6
0.6
0.05
0.1
0.15
0.05
0.1
0.15
0.05
0.15
(b) Alg. (A 1000c)
Figure 10: Effect of fairness level 8 on robustness across groups under adversarial sampling and adversarial labeling bias COMPAS dataset. The reductions approach (Agarwal et al., 2018) is used to train fair models. The majority group (whites) contributes 61 % of the test data.
34

---

Under review as a conference paper at ICLR 2022
Ovenill Adv. Sampling
Majority group- Adv. Sampling
Minority group Adv. Sampling
Tex. Accuracy
Unconstrained model = 0.1)
Fair (8 0.05)
Fair (6 0.01)
0.7
0.05
0.1
0.15
0.2
0.05
0.1
0.15
0.2
0.05
0.1
0.15
0.2
Overall Adv. Labeling
Majority group- Adv. Labeling
Minority group- Labeling
Test Accuracy
0.9
0.9
0.9
0.8
0.8
0.8
0.7
0..7
0.05
0.1
0.15
0.2
0
0.05
0.1
0.15
0.2
0.05
0.1
0.15
0.2
(a) Alg. 2 (A 100c)
Adv. Sampling
Majority group Sampling
Minority group Sampling
Tedt Accaracy
0.9
0.9
0.9
0.8
0.8
0.8
0.7
0.7
0.7
0.05
0.1
0.15
0.2
0.05
0.1
0.15
0.2
0.05
0.1
0.15
0.2
Overall Adv. Labeling
Majority group Adv. Labeling
Minority group Adv. Labeling
Text Accuracy
0.7
0.05
0.1
0.15
0.05
0.1
0.15
0.2
0.05
0.1
0.15
0.2
(b) Alg. (A 1000c)
Figure 11: Effect of fairness level 8 on robustness across groups under adversarial sampling and adversarial labeling bias Adult dataset. The majority group (males) contributes 66% of the test data. The reductions approach (Agarwal et al., 2018) is used to train fair models.
35

---

Under review as a conference paper at ICLR 2022
Overall Adv. Sampling
Majority Adv. Sampling
Minerity group Adv. Sampling
0.9
0.9
0.9
Test Accurscy
0.8
0.7
Unconstrained model
0.1)
Fair (6 0.05)
Fair (8 0.01)
0
0.05
0.1
0.15
0.2
0
0.05
0.1
0.15
0.2
0
0.05
0.1
0.15
0.2
Adv. Labeling
Majority group Labeling
Minority group Labeling
Text Accuniy
0.8
0.8
0.8
0.7
0.7
0.7
0.6
0.6
0.6
0.5
0.5
0.5
0.1
0.1
0.1
(a) Alg. (A 100e)
Overall Adv. Sampling
Majority group Sampling
Minority group Sampling
0.9
Text Accuracy
0.8
0.8
0.8
0.7
0.7
0.7
0.6
0.6
0.6
0.5
0.5
0.5
0.05
0.1
0.15
0.05
0.1
0.15
0.2
0.05
0.1
0.15
0.2
Overall Adv. Labeling
Majority group Adv. Labeling
Minority group Adv. Labeling
Text Accuracy
0.6
0.6
0.5
0.5
0.5
(b) Alg. 1000c)
Figure 12: Effect of fairness level 8 on robustness across groups under adversarial sampling and adversarial labeling bias Synthetic dataset. The majority group contributes 54.4% of the test data. The reductions approach (Agarwal et al., 2018) is used to train fair models.
36

---

Under review as a conference paper at ICLR 2022
Ovenill Adv. Sampling
Majority group- Adv. Sampling
Minority Adv. Sampling
Teu Accuracy
Unconstrained model = 0.1)
Fair (8 0.05)
Fair (5 0.01)
0.05
0.1
0.15
0.2
0.05
0.1
0.15
0.2
0.05
0.1
0.15
0.2
Overall Adv. Labeling
Majority group- Adv. Labeling
Minority group- Labeling
0.9
0.9
0.9
Test Accuracy
0..8
0.8
0.88
0.7
0.7
0.7
0.6
0.6
0.6
0.5
01.3
0
0.05
0.1
0.15
0.2
0
0.05
0.1
0.15
0.2
0.05
0.1
0.15
0.2
(a) Alg. (A 6)
Overall Adv. Sampling
Majority group Adv. Sampling
Minority group Adv. Sampling
0.9
0.9
0.9
Test Accuracy
0.8
0.8
0.8
0.7
0.7
0.7
0.6
0.6
0.5
0.05
0.1
0.15
0.2
0
0.05
0.1
0.15
0.2
0.05
0.1
0.15
0.2
Overall Adv. Labeling
Majority group Adv. Labeling
Minority group Adv. Laheling
Text Accuracy
0.7
0.7
0.7
0.6
0.6
0.6
0.5
0.5
0.5
0.05
0.1
0.15
0.05
0.1
0.15
0.05
0.1
0.15
0.2
(b) Alg. (A 1000c)
Figure 13: Effect of fairness level 6 on robustness across groups under adversarial sampling and adversarial labeling bias MEPS dataset. The majority group contributes 58.9% of the test data. The reductions approach (Agarwal et al., 2018) is used to train fair models.
37

---

Under review as a conference paper at ICLR 2022
Unconstmined
Sampling
Fair (Hardt al., 2016) Adv. Sampling
(Agarwal et al., 2018) Sampling
0.8
0.7
0.7
0.7
0.6
0.6
0.6
0.5
0.5
0.5
0.15
0.05
0.15
Unconstrained Model Adv. Laheling
(Hardi 2016) Adv. Labeling
Fair (Agarwal al,, 2018) Adv. Laheling
0.9
0.9
Aceuncy
0.8
0.8
0.8
0.7
0.7
0.7
0.6
0.6
0.5
0.5
0.05
0.1
0.15
0.2
0.05
0.1
0.15
0.2
0.05
0.15
0.2
Alg. (A (Steinhurdi al. 2017)
Alg.
100lc)
Alg. 1000c) c flipping
Random sampling
Hard examples
Constant prediction
Test accuracy of unconstrained and fair models with respect to equal opportunity in the presence of adversarial bias - COMPAS dataset. The x-axis is the ratio of the size of Dp to the size of clean dataset De and reflects the contamination level of the training set. We compare the impact of adversarial bias with baselines and adversarial bias against unconstrained models, for various e. The difference between test accuracy at of the bias. Constant prediction always outputs the majority label in the clean dataset. The enforced fairness level is and 0.01 for the fair model (Hardt et al., 2016) and fair model (Agarwal al., 2019 8), respectively.
Figure 14:
(benign setting) and a larger value reflects the impact
38

---

Under review as a conference paper at ICLR 2022
D. Minority Adv. Sampling
D3 Minority Adv. Sampling
0.8
0.8
Training Accuracy
0.6
0.6
0.4
0.4
Unconstrained model
Fair (Ó = 0.1)
0.2
Fair (5 0.05)
0.2
Fair (4 0.01)
0.05
0.1
0.15
0.2
0.05
0.1
0.15
0.2
De Minority Adv. Labeling
Dp Minority Adv. Labeling
0.8
0.8
Training Accuracy
0.2
0.2
0.05
0.1
0.15
0.2
0.05
0.1
0.15
0.2
(a) Alg. 2 (A 100c)
D. Minority Adv. Sampling
D, Minority Adv. Sampling
0.8
0.8
Training Accuracy
0.6
0.6
0.4
0.4
0.2
0.05
0.1
0.15
0.2
0.05
0.1
0.15
0.2
D. Minority Adv. Labeling
DD, Minority Adv. Laheling
0.8
Triiing Accuracy
0.6
0.6
0.4
0.4
0.2
0.2
0
0.05
0.1
0.15
0.2
0.05
0.1
0.15
0.2
(b) Alg. (A = 1000c)
Figure 15: Accuracy of clean training data and Dp under adversarial sampling and adversarial labeling bias COMPAS dataset. The reductions approach Agarwal et al. (2018) used to train all fair models.
39

---

Under review as a conference paper at ICLR 2022
De Minority Adv. Sampling
Dj Minority Adv. Sampling
0.8
0.8
Training Accurucy
0.6
0.6
0.4
Unconstrained model
Fair (8 0.1)
Fair (6 0.05)
0.2
Fair 0.01)
0.05
0.15
0.2
0.05
0.1
0.15
0.2
De Minority-
Adv. Labeling
Dp Minority Adv. Labeling
0.8
0.8
Trannin Accuracy
0.6
0.6
0.4
0.4
0.2
0.2
0.05
0.1
0.15
0.2
0.05
0.1
0.15
0.2
(a) Alg. 2 (A 100c)
Minority Adv. Sampling
D, Minority Adv. Sampling
0.8
0.8
Training Accuracy
0.6
0.4
0.4
0.2
0.2
0
0.05
0.1
0.15
0.2
0
0.05
0.1
0.15
0.2
D. Minioryyyy Adv. Labeling
D, Minority Adv. Labeling
1
0.8
0.8
Training Accuracy
0.6
0.6
0.4
0.2
0.2
0
0.05
0.1
0.15
0.2
0.05
0.1
0.15
0.2
(b) Alg. 1000c)
Figure 16: Accuracy of clean training data and D, under adversarial sampling and adversarial labeling bias Adult dataset. Fair models are trained using reduction approach (Agarwal et al., 2018).
40

---

Under review as a conference paper at ICLR 2022
De Minority Adv. Sampling
D3 Minority Adv. Sampling
0.8
0.8
Training Accuracy
0.6
0.6
0.4
0.4
Unconstrained model
Fair (Ó = 0.1)
0.2
Fair (5 0.05)
0.2
Fair (4 0.01)
0.05
0.1
0.15
0.2
0.05
0.1
0.15
0.2
De Minority Adv. Labeling
Dp Minority Adv. Labeling
0.8
0.8
Training Accuracy
0.2
0.2
0.05
0.1
0.15
0.2
0.05
0.1
0.15
0.2
(a) Alg. 2 (A 100c)
D. Minority Adv. Sampling
D, Minority Adv. Sampling
0.8
0.8
Training Accuracy
0.6
0.6
0.4
0.4
0.2
0.05
0.1
0.15
0.2
0.05
0.1
0.15
0.2
D. Minority Adv. Labeling
DD, Minority Adv. Laheling
0.8
Triiing Accuracy
0.6
0.4
0.4
0.2
0.2
0
0.05
0.1
0.15
0.2
0
0.05
0.1
0.15
0.2
(b) Alg. (A = 1000c)
Figure 17: Accuracy of clean training data and Dp under adversarial sampling and adversarial labeling bias Synthetic dataset. Fair models trained using reduction approach (Agarwal al., 2018).
41

---

Under review as a conference paper at ICLR 2022
D. Minority Adv. Sampling
D3 Minority Adv. Sampling
0.8
0.8
Training Accuracy
0.6
0.6
0.4
0.4
Unconstrained model
Fair (Ó = 0.1)
0.2
Fair (5 0.05)
0.2
Fair (4 0.01)
0.05
0.1
0.15
0.2
0.05
0.1
0.15
0.2
D. Minority Adv. Labeling
DP Minority Adv. Labeling
0.8
0.8
Training Accuracy
0.2
0.2
0.05
0.1
0.15
0.2
0.05
0.1
0.15
0.2
(a) Alg. (A c)
D. Minority Adv. Sampling
D, Minority Adv. Sampling
0.8
0.8
Training Accuracy
0.6
0.6
0.4
0.4
0.2
0.05
0.1
0.15
0.2
0.05
0.1
0.15
0.2
D. Minority Adv. Labeling
DD, Minority Adv. Laheling
0.8
Triiing Accuracy
0.6
0.4
0.4
0.2
0.2
0
0.05
0.1
0.15
0.2
0.05
0.1
0.15
0.2
(b) Alg. (A = 1000c)
Figure 18: Accuracy of clean training data and Dp under adversarial sampling and adversarial labeling bias MEPS dataset. Fair models are trained using reduction approach (Agarwal et al., 2018).
42

---

Under review as a conference paper at ICLR 2022
Unconstrained Model Adv. Sampling
Unconstrained Model Adv. Labeling
0.6
0.6
Faimess gep traiming
0.4
0.4
0.2
0.2
0
0.05
0.1
0.15
0.2
0
0.05
0.1
0.15
0.2
Alg. 2 (A 0) - Alg. 2 (A 100c) Alg. (A 1000e)
Random sampling
Hard examples
Label flipping
Figure 19: Fairness gap on the unconstrained model with respect to the training data COMPAS dataset. An unconstrained model is learned on the training data that includes adversarial bias generated by Alg. (A = 100c). The fairness gap A is defined in (1). The numbers reflect how unfair this unconstrained model is with respect to the protected group the training data.
Unconstrained Model Adv. Sampling
Unconstrained Model Adv. Laheling
Fuimess gap training data
0.4
0.4
0.2
0.2
0.05
0.1
0.15
0.2
0.05
0.1
0.15
0.2
Alg. 2 (A 0) Alg. 2 (A= 100c) Alg. (A 1000c)
Random sampling
Hard example
Label flipping
Figure 20: Fairness gap on the unconstrained model with respect the training data Adult dataset. An unconstrained model is learned on the training data that includes adversarial bias generated by Alg. (A 100c). The faimesss gap A is defined (1).
43

---

Under review as a conference paper at ICLR 2022
Unconstrained Model Adv. Sampling
Uncoostrained Model - Adv. Labeling
Fairnsss gap training data
0.6
0.6
0.4
0.4
0.2
0.2
0.05
0.1
0.15
0.2
0.05
0.1
0.15
0.2
Alg. (A (Steinhardi al., 2017) Alg. 100c) Alg. 1000e)
Random sampling
Label flipping
Figure 21: Fairness gap on the unconstrained model with respect to the training data Synthetic dataset. An unconstrained model is learned on the training data that includes adversarial bias generated by Alg. 2 (A 100e).
Unconstrained Model Adv. Sampling
Unconstrained Model Adv. Labeling
Faimesss gap training data
0.6
0.6
0.4
0.4
0.2
0.2
0.05
0.1
0.15
0.2
0.05
0.1
0.15
0.2
Alg. 2 (A = 0) (Steinhardt et al., 2017) Hard examples
- Alg. 2 (A = e) - Alg. (A = 1000e)
Random sampling
Label flipping
Figure 22: Fairness gap the unconstrained model with respect the training data MEPS dataset.
unconstrained model learned on the training data that includes adversarial bias generated by Alg. 2 (A e).
44

---

Under review as a conference paper at ICLR 2022
(8) Adv. sampling (Alg. 2, 0)
(b) Adv. sampling (Alg. 2, 100e)
(c) Adv. sampling (Alg. 1. 1000l)
100
100
100
80
80
80
Procenage
60
60
60
-40
40
40
20
20
20
0.05
0.1
0.15
0.2
0.05
0.1
0.15
0.2
0.05
0.15
0.2
Adv. labeling
()
(e) Adv. labeling (Alg. 100e)
Adv. labeling (Alg. 1, 1000e)
100
100
100
Porcealage
40
20
0.05
0.1
0.15
0.05
0.1
0.15
0.05
0.2
Random sampling
(b) Hard examples
(i) Label flipping
100
100
100
80
80
80
Percentage
60
60
00
40
10
10
20
20
20
0.05
0.1
0.15
0.2
0.05
0.1
0.15
0.2
0.05
0.1
0.15
0.2
Figure 23: Distribution of Dp COMPAS dataset. We report the protected attribute whites and s = for blacks) and labels of data points in Dp for various c. For every value of the number for each combination of the protected attribute and label reflects the percentage of points with this combination in Dp Algorithm 2 with À = 0 is the same the attack algorithm proposed in Steinhardt al. (2017).
0 for
45

---

Under review as a conference paper at ICLR 2022
(a) Adv. sampling (Alg.
sampling (Alg.
(c) sampling (Alg. 1),
100
80
Porceatgge
60
60
-40
40
40
20
20
20
0.05
0.1
0.15
0.2
0.05
0.1
0.15
0.2
0.05
0.15
0.2
(d) Adv. labeling (Alg. 2, 0)
(e) Adv. labeling (Alg. 2, A 100c)
(1) Adv. labeling (Alg. 1),
1000c
100
100
100
80
80
Perceraao
60
0.05
0.1
0.15
0,2
0.05
0.1
0.15
0.2
0.05
0.15
0.2
Random sampling
(h) Hard examples
(i) Label flipping
1010
100
100
80
80
80
Preeutage
60
60
60
40
40
40
20
20
20
0.05
0.1
0.15
0.2
0.05
0.1
0.15
0.2
0.05
0.2
Figure 24: Distribution of Dp Adult dataset. We report the protected attribute (s for males and $ = 1 for females) and labels of data points in Dp for various c. Algorithm with = is the same the attack algorithm proposed in Steinhardt al. (2017).
46

---

Under review as a conference paper at ICLR 2022
(a) Adv. sampling (Alg. A
Adv. sampling 100e)
(c) Adv. sampling (Alg. 1), A 1000le
100
Porcentage
20
20
0.05
0.05
(d) Adv. labeling (Alg. 0)
(e) Adv. labeling (Alg. 2, 100k)
(1) Adv. labeling (Alg. 1), 1000c
100
100
100
80
80
80
Percentage
60
60
60
40
10
10
20
20
0.05
0.1
0.15
0.2
0.05
0.1
0.15
0.2
0.05
0.1
0.15
0.2
Random sampling
Label flipping
Pereantage
40
40
20
20
0.05
Figure 25: Distribution of the Dp Synthetic dataset. Algorithm 2 with À = 0 is the same as the attack algorithm proposed in Steinhardt et al. (2017).
47

---

Under review as a conference paper at ICLR 2022
(a) Adv, sampling (Alg. 2, A 0)
(b) Adv. sampling (Alg 2, -
(6) Adv. sampling (Alg. 1), 1000
1000
1001
1001
80
80
80
Percentago
60
60
60
40
40
40
20
0.05
0.1
0.15
0,2
0.05
0.1
0.15
0.2
0.05
0.1
0.15
0.2
Adv. labeling
0)
labeling
e)
Adv. labeling (Alg.
1000c
80
Porcentage
610
40
40
40
20
20
20
0.05
0.05
(g) Random sampling
(b) Hard examples
() Label flipping
100
100
100
80
80
Percentage
60
60
0.05
0.1
0.15
0.2
0.05
0.1
0.15
0.2
0.05
0.1
0.15
0.2
Figure 26: Distribution the D, MEPS dataset. We report the protected attribute (s 0 for non-white and = for white) and labels of data points in 2, for various e. For this datasct, (s 0, = -) represents the smallest subgroup.
48


Reviews:
[{"review_id": "zF4sldtFsRi", "reviewer": "Reviewer_oMrk", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths:\n\n1. It investigates an important issue that arises in trustworthy machine learning. \n2. Overall the paper is well-written and easy to follow. \n3. It provides a theoretical guarantee for the approximated algorithm (Algorithm 1). \n\nWeaknesses:\n\n1. The evaluation is done only under certain algorithms (Algorithms 1 and 2) and under particular fairness algorithms (even assumpting somewhat strict logistic regression models). In addition, the evaluation is based solely upon experiments, although some intuitive remarks are provided along with the experimental results. This reviewer wonders if the key message (fairness degrades accuracy more significantly than the unconstrained model) holds fundamentally. Otherwise, the claim may hold only under certain settings.\n\n2. It considers only one fairness measure, equalized odds. What about another prominent measure like demographic parity?\n\n3. It would be more informative and useful if the challenge that this paper claims can be well addressed by some recent fair-&-robust training algorithms. Actually, if that is the case, I am wondering if the raised issue is really a challenge.\n", "summary_of_the_paper": "This paper explores the robustness against certain adversarial train-data poisoning (sampling or label flipping) for some prior fair machine learning algorithms, under equalized odds. Experimental results conducted on some synthetic and benchmark real datasets under logistic regression models demonstrate that the employed fairness constraints yield more performance degradation relative to unconstrained models.", "summary_of_the_review": "The claims are based mainly on experiments even under some particular algorithms and models. So it is hard to make a scientific judge as to whether the claims are really the case.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "rr4JTNqaJa4", "reviewer": "Reviewer_tNTd", "summary": "", "questions": "", "limitations": "", "rating": 3, "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": "Major comment:\n\nThe paper completely dismisses the recent advances made in the literature.  In particular, the authors ignore (and/or misunderstand) the prior works on \"robust fair learning\" by writing \"Although several fair learning algorithms have been proposed to achieve different robustness properties (Wang et al., 2020; Rezaei et al., 2020; Taskesen et al., 2020; Roh et al., 2020; Cotter et al., 2019), those algorithms do not consider the adversarial bias and fail to be robust against adversarial bias.\" \n\nUnfortunately, this is clearly false.  To see this, consider [Wang et al. 2020].  Their algorithm and theoretical guarantees do hold for any \"perturbation\" including adversarial perturbation. More specifically, the only assumption they have on the poisoned data distribution is that it is within a certain Total Variation distance from the true distribution, which does not distinguish random noise and adversarial noise.\n\nAnother instance is [Roh et al. 2020], which indeed performed an adversarial label flipping attack proposed in [\"Label sanitization against label flipping poisoning attacks\", Paudice et al.]. They showed that the fair learning algorithms can be made robust against such adversarial data poisoning attacks. Also, the same observation that \"fair learning algorithms are more vulnerable than vanilla training algorithms\" was also made in this work.\n\nGiven these prior studies on robust fair learning algorithms, the authors should have discussed how their proposed attack algorithms perform against such robust fair learning algorithms. \n\n\nOther comments:\n\n-- The algorithmic novelty is marginal: the proposed algorithm is an immediate application of Steinhardt et al. with a different objective function.  \n\n-- It is also unclear how effective the proposed approximation for the fairness penalty (shown in (4)) is.  The authors may want to report how good this approximation is.  In particular, for a fixed dataset, one can measure the original fairness penalty value and the proposed approximation.  By repeating these measurements for various classifiers, one can see how these two values are related by plotting a scatter plot.  \n\n-- All the tables and figures show how much test accuracy drops.  What about their fairness violations?  Also, what happens when one simply performs an attack based on the prediction loss term alone without considering the fairness constraint term?  How does the attack performance change?", "summary_of_the_paper": "Intuitively, the same amount of data poisoning will have a larger impact when the learner is solving a constrained optimization problem than an unconstrained one.  This paper proposed an attack algorithm specifically designed for such fair learners and showed that fair learning algorithms are more vulnerable to adversarial data poisoning attacks.  The problem studied in this paper is of high importance.", "summary_of_the_review": "The paper studies an interesting problem.  However, it is unclear whether their proposed attack algorithm is still valid given that researchers have already proposed various robust fair learning algorithms.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "1: The contributions are neither significant nor novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "d95K4vfAHwP", "reviewer": "Reviewer_iCR1", "summary": "", "questions": "", "limitations": "", "rating": 8, "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": "Overall, the paper is well written, covers a lot of literature review from recent papers and is a recent and important topic with lots of interesting analysis and experiments.\n\nStrengths: \n1. The paper covers an important issue that is also timely.\n2. It covers relevant previous work.\n3. Lots of experimental results which are interesting.\n\nWeaknesses:\nThese are not necessarily weaknesses but some points that I think can make the paper more complete and interesting:\n1. It would be interesting to see results for other fairness notions like statistical parity and its comparison with equality of op and equalized odds results along with different methods that satisfy statistical parity for instance specifically that are different than methods optimized for equality of op. Would we still see this trend?\n2. Is robustness related to fairness notion that we have in mind or the method that we use it to optimize for it? I think these are interesting questions that this type of work can answer by expanding on some experiments and discussion.\n3. It would also be interesting to see results from applying existing data poisoning attacks on fairness in addition to the methods authors used in this paper and see how results would fare under those attacks as well...", "summary_of_the_paper": "In this paper, authors study the trade-offs between fairness and robustness in the adversarial setting. From the results, authors show that fair models are more likely to have lower accuracy in the adversarial setting where fairness is targeted in the training data compared to regular models.", "summary_of_the_review": "I think the paper has lots of interesting points and its merits outweighs the points I noted under weaknesses which are not really weaknesses but some suggestions that can further improve the work. With that being said, the paper has already enough content for publication which are interesting and informative and the suggestions can maybe considered as a followup work. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "3uM4pGwow9", "reviewer": "Reviewer_bW76", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The strength of the paper is the particular problem considered. I think it is an important problem to make fair models robust before they can be reliably deployed in practice. Additionally, I thought the paper was well-written and I could follow most of the arguments.\n\nWeaknesses:\n1. Although the problem of designing fair and robust classifier is interesting, this problem now has been looked into by several papers. I would mention three papers [1,2,3] that were not cited by the paper (in addition to the paper Rezaei et.al. 2020) So, I think the paper does not provide a significant contribution to this problem. In addition, I think some observation made by the authors have already been highlighted by several papers in the past. For example, the fact that adversarial training increases accuracy disparity has been observed by [4].\n2. In the experimental section, the choice of fair classifiers is not exhaustive. I would have expected the authors to include at least one pre-processing based classifiers. Furthermore, the choice of datasets is not exhaustive either. If I have to accept the paper based on its empirical observation then it should include additional datasets of different kinds e.g. law-school and communities.\n3. In terms of proposed algorithm, I am not sure why the authors chose the current design in algorithm 1. There are many ways to make an existing fair classifier robust. The authors have not provided any justification for the proposed approach. \n4. A significant drawback of the algorithm is the linear approximation of the term $\\Delta(\\theta, \\mathcal{D}_c \\cup \\mathcal{D}_p)$. This assumes that the contribution of each datapoint can be summed independently to get the overall effect. However, I could imagine a setting where new points have very low marginal contribution to the fairness gap when added to a set of $\\mathcal{D}_p$ with reasonable number of points. \n5. Finally, the related work section of the paper does not provide a detailed description of the latest work. I found several missing references that are quite relevant to the current work.\n\nReferences:\n1. Fair Classification with Adversarial Perturbations (NeurIPS-2021)\n2. Ensuring Fairness beyond the Training Data (NeurIPS-2020)\n3. Sample Selection for Fair and Robust Training (NeurIPS-2021)\n4. Fairness Through Robustness: Investigating Robustness Disparity in Deep Learning (FAccT-2021)", "summary_of_the_paper": "\nThis paper studies the problem of fair classification when the dataset is adversarially perturbed. In particular, the authors considers two models of adversarial perturbation -- (1) adversarial sampling (outlier data points are chosen adversarially), and (2) adversarial labeling (labels of a fraction of data points are chosen adversarially). Based on no-regret online gradient descent algorithm, the authors propose an algorithm that uses existing fair classifier as an oracle and produces a classifier that is both fair and robust to adversarial perturbations.\n\nThe main contribution of the paper is evaluation of robustness of fair classifiers. The main message of the empirical evaluation is the following. First, there is a large relative drop in accuracy for all fair models because of adversarial perturbations. Second, adversarial bias increases the accuracy gap across different groups, and thereby further increases the cost of fairness.", "summary_of_the_review": "In summary, I think the authors considered an interesting problem. However, the both the proposed algorithm and empirical evaluation have limitations. The main message of the paper is that robustness increases the cost of fairness. This fact has been observed by other papers before. Additionally, in comparison to several recent papers on fair and robust classification, I don't think the paper makes a major contribution to the problem.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "1: The contributions are neither significant nor novel."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The authors consider the impact of designing fair algorithms on adversarial robustness. The particular focus is on poisoning attacks. They show experimentally that for some datasets and models/algorithms that using "fair" algorithms increase adversarial vulnerability compared to the standard training procedure (ignoring fairness criteria). The reviews have raised questions about whether the experimental results are extensive enough and I share their concerns. Most importantly, the authors have not addressed the question regarding to the quality of approximation at all.
Decision: Reject