Training individually fair ML models with sensitive subspace robustness
Authors: Mikhail Yurochkin
Amanda Bower
Yuekai Sun
Venue:  (2020)
Keywords: fairness
adversarial robustness

Abstract: We consider training machine learning models that are fair in the sense that their performance is invariant under certain sensitive perturbations to the inputs. For example, the performance of a resume screening system should be invariant under changes to the gender and/or ethnicity of the applicant. We formalize this notion of algorithmic fairness as a variant of individual fairness and develop a distributionally robust optimization approach to enforce it during training. We also demonstrate the effectiveness of the approach on two ML tasks that are susceptible to gender and racial biases. 

Published as a conference paper at ICLR 2020
TRAINING INDIVIDUALLY FAIR ML MODELS WITH SNSSIIIVE SUBSPACE ROBUSTNESS
Mikhail Yurochkin
Amanda Bower!, Yuckai Sun Department of Mathematics'
IBM Research
MIT-IBM Watson Al Lab
Department of Statistics University of Michigan {amandarg, yuekai @umii ch. edu
mi khail, 1.. yurochk n 1.m.ccom com
ABSTRACT
We consider training machine learning models that are fair in the sense that their performance invariant under certain sensitive perturbations to the inputs. For example, the performance of resume screening system should be invariant un- der changes to the gender and/or ethnicity of the applicant. We formalize this notion of algorithmic fairness as variant of individual fairness and develop dis- tributionally robust optimization approach to enforee it during training. We also demonstrate the effectiveness of the approach on two MI tasks that are susceptible to gender and racial biases.
INTRODUCTION
Machine learning (ML) models are gradually replacing humans in high-stakes decision making roles. For example, in Philadelphia, an ML model classifies probationers as high or low-risk (Metz & Satariano| 2020). In North Carolina, "analytics" is used to report suspicious activity and fraud by Medicaid patients and providers (Metz & Satariano 2020). Although ML models appear to elim- inate the biases of a human decision maker, they may perpetuate or even exacerbate biases in the training data (Barocas & Selbst] 2016). Such biases especially objectionable when it adversely affects underprivileged groups of users (Barocas & Selbst 2016).
In response, the scientific community has proposed many mathematical definitions of algorithmic fairness and approaches to ensure ML models satisfy the definitions. Unfortunately, this abundance of definitions, many of which are incompatible (Kleinberg et al., 2016; Chouldechoval 2017). has hindered the adoption of this work by practitioners. There are two types of formal definitions of algorithmic fairness: group fairness and individual fairness. Most recent work on algorithmic fair- ness considers group fairness because it is more amenable to statistical analysis (Ritov et al. (017)-
Despite their prevalence, group notions of algorithmic fairness suffer from certain shortcomings. One of the most troubling is there many scenarios in which an algorithm satisfies group faireess, but its output is blatantly unfair from the point of view of individual users (Dwork et al. 2011).
individually In this paper, consider individual faimess instead of group faimeess. Intuitively, fair ML model treats similar users similarly. Formally, an ML model is a map h : X - V, where X' and y are the input and output spaces. The leading notion of individual faimess is metric fairness (Dwork et al. 2011); it requires
dy (h(zz)), h(x2)) S Ldg(21, x2) for all 1 x2 E X,
(1.1)
where d, and dy are metrics on the input and output spaces and 2 0 is a Lipschitz constant. The fair metric de encodes our intuition of which samples should be treated similarly by the ML model. We emphasize that d, (#1, x2) being small does not imply Ij and x2 are similar in all respects. Even if d, (11, 22) is small, 21 and D2 may differ in certain problematic ways, e.g. in their protected/sensitive attributes. This is why we refer to pairs of samples 21 and x2 such that (2) is small as comparable instead of similar.
Despite its benefits, individual faimess was dismissed as impractical because there is no widely accepted fair metrie for many MI. tasks. Fortunately, there is line of recent work learning the

---

Published as a conference paper at ICLR 2020
Wang al. 2019). In this paper, consider two data-driven choices of the fair metric: one for problems in which the sensitive attribute is reliably observed, and another for problems in which the sensitive attribute is unobserved (see Appendix [B).
fair metric from data (IIvento] 2019
The rest of this paper is organized as follows. In Section 2 we cast individual fairness as a form of robustness: robustness to certain sensitive perturbations to the inputs of an ML model. This allows us to leverage recent advances in adversarial ML to train individually fair ML models. More concretely, develop an approach audit ML models for violations of individual fairness that is similar to adversarial attacks (Goodfellow et al. (2014) and an approach to train ML models that passes such audits (akin adversarial training (Madry et al. 2017)). We justify the approach theoretically (see and empirically (see Section
Section 3)
2 FAIRNESS THROUGH (DISTRIBUTIONAL) ROBUSTNESS
To motivate our approach, imagine an auditor investigating an ML model for unfairness. The auditor collects a set of audit data and compares the output of the ML model comparable samples in the audit data. For example, to investigate whether resume screening system is fair, the auditor may collect stack of resumes and change the names the resumes of Caucasian applicants to names more common among the African-Amerian the edited resumes, then the auditor may conclude the model treats African-American applicants unfairly, Such investigations are known as correspondence studies, and a prominent example is Bertrand & Mullainathan celebrated investigation of racial discrimination in the labor market. In correspondence study, the investigator looks for inputs that are comparable to the training examples (the edited resumes in the resume screening example) on which the MI. model performs poorly. In the rest of this section, we formulate an optimization problem to find such inputs.
population. If the system performs worse on
2.1 FAIR WASSERSTEIN DISTANCES
Recall X' and y are the spaces of inputs and outputs. keep things simple, we assume that the ML task at hand is classification task, y is discrete. We also assume that have a fair metric dz of the form
(z1, x2) (z) 22, E(x =22))
where E E sdxd For example, suppose we are given set of K "sensitive" directions that we wish the metric to ignore; L.e. d(I1, < for any x1 and 22 such that x 22 falls in the span of the sensitive directions. These directions may be provided by domain expert or learned from data (see Section and Appendix B). In this case, we may choose Σ as the orthogonal complement projector of the span of the sensitive directions. We equip X' with the fair metric and Z - X' x y with
da (211,,1)) v1), (22,82)) d.e (21, + x 1 (y1 + y.
We consider df as transport cost function on Z. This cost function encodes our intuition of which samples are comparable for the MI. task at hand. We equip the space of probability distributions on Z with the fair Wasserstein distance
Q)).Q) = inf J2xz c(21, 22 )dI 22),
where Q) is the set of couplings between P and Q. The fair Wasserstein distance inherits our intuition of which samples are comparable through the cost function; i.e. the fair Wasserstein distance between two probability distributions is small if they are supported on comparable areas of the sample space.
2.2 AUDITING ML MODELS FOR ALGORITHMIC BIAS
To investigate whether an ML model performs disparately on comparable samples, the auditor col- lects set of audit data ((r,, yi)) and solves the optimization problem
maxp.w(PPP..s- Jz {(2, ((2 h))P(2),
(2.1)
where é: x 7L R., is a loss function, h is the ML model, P, is the empirical distribution of the audit data, and e > 0 is a small tolerance parameter. We interpret e as a moving budget that the au- ditor may expend to discover discrepancies in the performance of the MI. model. This budget forces
2

---

Published as a conference paper at ICLR 2020
the auditor to avoid moving samples to incomparable areas of the sample space. We emphasize that equation 2. detects aggregate violations of individual fairesss. In other words, although the violations that the auditor's problem detects are individual in nature, the auditor's problem is only able to detect aggregate violations. We summarize the implicit notion of faimess in equation 2.1 in definition.
Definition 2.1 (distributionally robustly fair (DRF)). An ML. model h. X + y is (c, distributionally robustly fair (DRF) WRT the fair metric du iff
maxp. h))(a) S
(2.2)
Although equation 2.1 is an infinite-dimensionall optimization problem, it is possible to solve exactly by appealing to duality. Blanchet & Murthy showed that the dual of equation 2.1 is
sup SUPP.W(P.R.)s Ep [e(Z, h)] infx d Ep, hZ,])) (5,(( yi), h) _ suPzex {( ): 0) (x.
(2.3)
This is univariate optimization problem, and is amenable to stochastic optimization. We describe stochastic approximation algorithm for equation 2.3 in Algorithm] | Inspecting the algorithm, we see that it similar to the PGD algorithm for adversarial attack.
Algorithm stochastic gradient method for equation 2.3
2.3
Require: starting point dτ step sizes at
1: repeat
2: draw mini-batch (It, 1/., Vr.),.... (Iin Bta) Pn
3: F7, + arg max, ( Voo), h) Ad I), [B]
4: λc+1 < max(0, de- - ar(e - 1 Ei= dz (It, 21,))
5: until converged
is known that the optimal point of equation 2.1 is the discrete measure 1,2 Er= (x.))))) where
T X - X' is the unfair map
Tx(x;) + arg max max, ((), h) Xdh 2z).
(2.4)
We call T3 an unfair map because it reveals unfairness the ML model by mapping samples in the audit data to comparable areas of the sample space that the system performs poorly on. We note that T3 may map samples in the audit data to areas of the sample space that are not represented in the audit data, thereby revealing disparate treatment in the ML. model not visible in the audit data alone. We emphasize that Tx more than reveals disparate treatment in the ML model; it localizes the unfairness to certain areas of the sample space.
We present a simple example to illustrating fairness through robustness (a similar example appeared in Hashimoto et al. (2018)). Consider the binary classification dataset shown in Figure 1 There are two subgroups of observations in this dataset, and (sub)group membership is the protected attribute (e.g. the smaller group contains observations from minority subgroup). In Figure la decision heatmap of a vanilla logistic regression, which performs poorly on the blue minority sub- group. The two subgroups are separated in the horizontal direction, the horizontal direction is the sensitive direction. Figure [b] shows that such classifier is unfair with respect to the corresponding fair metric, i.e. the unfair map equation 2.4 leads significant loss increase by transporting mass along the horizontal direction with very minor change of the vertical coordinate.
the
Comparison with metric fairness Before moving on to training individually fair MI. models, we compare DRF with metric fairness equation 1.1 Although we concentrate on the differences between the two definitions here, they are more similar than different: both formalize the intuition that the outputs of a fair ML model should perform similarly comparable inputs. That said, there are two main differences between the two definitions. First, instead of requiring the output of the ML model to be similar all inputs comparable to a training example, be similar to the training label. Thus DRF not only enforces similarity of the output on comparable inputs, but also accuracy of the MI model the training data. Second, DRF considers differences
require the output to
3

---

Published as a conference paper at ICLR 2020
(a) unfair classifier
(h) unfair map
(c) classifier from SenSR
Figure I: Figure (a) depicts a binary classification dataset in which the minority group shown on the right of the plot is underrepresented. This tilts the logistic regression decision boundary in favor of the majority group on the left. Figure (b) shows the unfair map of the logistic regression decision boundary. It maps samples in the minority group towards the majority group. Figure (c) shows an algorithmically fair classifier that treats the majority and minority groups identically.
between datasets instead of samples by replacing the fair metric on inputs with the fair Wasserstein distance induced by the fair metric. The main benefits of this modifications are (i) is possible optimize equation 2. efficiently, (ii) we can show this modified notion of individual fairness generalizes.
2.3 FAIR TRAINING WITH SENSITIVE SUBSPACE ROBUSTNESS
We cast the fair training problem as training supervised learning systems that are robust to sensitive perturbations. We propose solving the minimax problem
inf sup NEW (P..).)
Ep [p[e(Z, M)]
inf inf Ac Ep, [Z)]
(2.5)
NEW X20
where f is defined in equation 2.3 This is an instance of distributionally robust optimization (DRO) problem, and it inherits some of the statistical properties of DRO. To see why equation 2.5 encourages individual fairness, recall the loss function is a measure of the performance model. By assessing the performance of an ML model by its worse-case performance ical populations of users with perturbed sensitive attributes, minimizing equation 2.5 ensures the system performs well all such populations. In toy example, minimizing equation 2.5 implies learning classifier that is insensitive to perturbations along the horizontal (i.e. sensitive) direction. In Figure Ic this achieved by the algorithm describe next.
the ML
hypothet-
To keep things simple, we assume the hypothesis class is parametrized by 0 E e C Rd and replace the minimization with respect
by minimization with respect 9. In light of the similarities between the DRO objective function and adversarial training, we borrow algorithms for adversarial training (addr et al. 2017) to solve equation 2.5 (see Algorithm(2 2
Algorithm Sensitive Subspace Robustness (SenSR)
Require: starting point 01, step sizes at, Br 0
1: repeat
2: sample mini-batch (21, 8/1 ), (EB, BB) P.
27, +- arg max, ((2, V1, ). ( x), [B]
4: det1 max (0, d ar(E B mm de (Tt, 17,
5: 0.+1 - 0, 2. f ΣB 0gl((xt, v,,),,))
6: until converged
Related work Our approach to fair training an instance distributionally robust optimization (DRO). In DRO, the usual sample-average approximation of the expected cost function is replaced
by LDRO (0) & sup Ep [2( 0)]. where 2/ is (data dependent) uncertainty set of probability distributions. The uncertainty set may defined by moment or support constraints (Chen et al,
2007 Delage & Ye. 2010; Goh & Sim 2010). -diieeggences (Ben-Tal et al. 2012 Lam & Zhou
4

---

Published as a conference paper at ICLR 2020
2013
Miyato al. 2015 Namkoong & Duchi 2016), and Wasserstein distances (Shafieezadeh-
Abadeh et al. 2015; Blanchet et al. 2016 Esfahani & Kuhn 2013 Lee & Raginsky 2017] Sinha
et 2017). Most similar
work is Hashimoto et al. (2018); they show that DRO with x -eiihhhborroo of the training data prevents representation disparity, i.e. minority groups tend
to suffer higher losses because the training algorithm ignores them. One advantage of picking Wasserstein uncertainty set is the set depends on the geometry of the sample space. This allows
us encode the correct notion of individual fairness for the ML task at hand in the Wasserstein distance.
Our approach to fair training also similar to adversarial training (aaryy et al. 2017), which hardens ML models against adversarial attacks by minimizing adversarial losses of the form supeet {(= + u. O), where 2/ set of allowable perturbations (Szegedy et al. [013 Goodfel- low et al. 2014 Papernot et al. 2015 Carlini & Wagner 2016; Kurakin et al. (016). Typically, 77
a scaled t noro ball: 27 {u | p S cj. Most similar to our work Sinha al. (017)) they
consider uncertainty set that is a Wasserstein neighborhood of the training data.
There are a few papers that consider adversarial approaches to algorithmic fairness. Zhang et al. (2188) propose adversarial learning method that enforces equalized odds in which the ad adversary learns to predict the protected attribute from the output of the classifier. [Ewwards & Storkey (2015) propose an adversarial method for learning classifiers that satisfy demographic parity. |Madras et al. (2018) generalize their method to learn classifiers that satisfy other (group) notions of algorithmic fairness. Garg et al. (2019) propose
adversarial logit pairing (Kannan et al., 2018 achieve fairness in text classification using a pre-specified list of counterfactual tokens.
SENSR TRAINS INDIVIDUALLY FAIR ML MODELS
One of the main benefits of our approach is it provably trains individually fair ML models. Further, it is possible for the learner to certifyy that an ML model is individually see, both are consequences of uniform convergence results for the DR loss class. More concretely, we study how quickly the uniform convergence eтror
fair posteriori. As we shall
6n A supoee sup.....rr...... Er [((Z,)) supy:w(r.P.ss Br [M(
(3.1)
where W. is the Wasserstein distance on A(Z) with transportation cost function c. that is possibly different from c, vanishes. We permit some discrepancy in the (transportation) cost function to study the effect of a data-driven choice of e. In the rest of this section, we regard e, as the exact cost function and assumptions on the ML task:
cost function learned from human supervision. We start by stating our
(A1) the feature space X' is bounded: D & mix diam. < oo; (A2) the functions in the loss class L = {E(., 0) 0 E Q} are non-negative and bounded: S ((z,0) S M for all E and 0 E θ and L-LLipschitz with respect to dz:
suPaee (sup (w..)..)).))
[e(( v), 0) (((22,)). 0), < Ld (œ1, x2);
(A3) the discrepancy in the (transportation) cost function is uniformly bounded: (e2 (e(( v), (I2, v)) c. ((x1, v), (#2, v))l S D.D
Assumptions Al and A2 are standard (see (Lee & Raginsky 2017 Assumption 1, 2, 3)) in the DRO literature. We emphasize that the constant L in Assumption A2 not the constant L in the definition of metric fairness; it may be much larger. Thus most models that satisfy the conditions of the loss class are not individually fair in meaningful sense.
Assumption A3 deserves further comment. Under A1, A3 is mild. For example, if the exact fair metric is
x2) = (z) x22) '' Σ, (x) x2)
then the error in the transportation cost function is at most
Jo((2), v), v)) - c. (. (22.
= |xx x22) T - x2) (#1 - x2) Ty, (x) -2)l
< D2 -ل
Amina (E.)
5

---

Published as a conference paper at ICLR 2020
We that the error in the transportation cost function vanishes in the large-sample limit as long as is a consistent estimator of Σ..
We state the uniform convergence result in terms of the entropy integral of the loss class: C(C) Jo Vlog No (F, where Noc (C, as the r-covering number of the loss class in the uniform metric. The entropy integral is a measure of the complexity of the loss class.
Proposition 3.1 (uniform convergence). Under Assumptions A1-A3, equation 3.1 satisfies
48E(C)
4SLD²
LS
log 2
MM
(3.2)
Vn
Vne
VE
2n
with probability at least 1-
We note that Proposition is similar to the generalization error bounds by Lee & Raginsky (017)) The main novelty in Proposition 3.1 is allowing error in the transportation cost function. We see that the discrepancy in the transportation cost function may affect the rate which the uniform convergence error vanishes: it affects the rate if 6, is wp(
A consequence of uniform convergence is SenSR trains individually fair classifiers (if there are such classifiers in the hypothesis class). By individually fair ML model, we mean an ML model that has a small gap
supp.w. (P.P.)) Ep [[(2,0) 0)] - Ep, [{(),))]
(3.3)
The gap the difference between the optimal value of the auditor's 's optimization problem equa- tion 2. and the (non-robust) risk. A small gap implies the auditor cannot significantly increase the loss by moving samples from P. to comparable samples.
Proposition 3.2. Under the assumptions AI-A3, as long as there is 0 E θ such that
supr:w.(r.n.s Ep [(Z 0)] 8*
(3.4)
for some 8* > 0, 0 E arg argmingge supr.w(D,P..s Bp [Z h)] satisfies
supp.w. [e(,0 Ep. [e ) -6" + 28
where 6, is the uniform convergence error equation 3.1
Proposition 3.2 guarantees Algorithm trains an individually fair ML model. More precisely, there are models in HH that (i) individually fair and (ii) achieve small test error, then Algorithm trains such a model. It is possible to replace equation (34 with other conditions, but a condition to its effect cannot be dispensed with entirely. If there are no individually fair models in H. then is not possible for equation (.55to learn an individually fair model. If there are individually fair models in H. but they all perform poorly, then the goal of learning an individually fair model is futile.
Another consequence of uniform convergence is equation 3.3 is close to its empirical counterpart
supr:w(r.n..se Ep [Z( 0)] E [((Z,)]]
(3.5)
In other words, the gap generalizes. This implies equation 3.5 is a certificate of individual fairness; i.e. it is possible for practitioners check whether an ML model is individually fair by evaluating equation 3,5
Proposition 3.3. Under the assumptions A 1-A3, for any c <> 0.
supoce { (supr:wer, Ep [[( (p( Er, [[(2,0) - Bapp..Cr.P)seEe111..... Ep [((,0)) - -E,, [((,,))))) < 28n w.p. at least - L.
4 COMPUTATIONAL RESULTS
In this section, we present results from using SenSR to train individually fair ML models for two tasks: sentiment analysis and income prediction. We pick these two tasks to demonstrate the efficacy of SenSR on problems with structured (income prediction) and unstructured (sentiment analysis) in- puts and in which the sensitive attribute (income prediction) observed and unobserved (sentiment analysis). We refer to Appendix C and D for the implementation details.

---

Published as a conference paper at ICLR 2020
Table 1: Sentiment prediction experiments over 10 restarts
Polacttd Alrrlaute
Acc.,% %
Race gap
Gend. gap
Cuis. gap
Gender Hale
Gender Female
SenSR
94
0.30+1.05
0.19-1.03
0.23-1.05
s4rtmman
SenSR-E
93+11
0.11#.04
0.04+.03
1.11
Bascline
95
7.01
5.592.37
4.10#.44
Project
94
1.00
1.99
1.70#t41
Sinha+
94
3.88
1.42
1.
Bolukb.+
9411
6.85+.53
4.33+.46
3.44
Susid ine Bolokbzari
Project
Santur
SerS
SentiiE
Figure 2: Box-plots of sentiment scores
4.1 FAIR SENTIMENT PREDICTION WITH WORD EMBEDDINGS
Problem formulation We study the problem of classifying the sentiment of words using positive (e.g. 'smart') ) and negative (e.g. 'anxiety") words compiled by Hu & Liu (2004). We embed words using 300-dimensional GloVe (Pennington et al.) 2014) and train 1000 hidden units. Such classifier achieves 95% test accuracy, however it entails major individual fairness violation. Consider application of this sentiment elassifier summarizing customer views, tweets or news articles. Human names are typical in such texts and should not affect the sentiment score, hence we consider fair metric between any pair of names be O. Then sentiment score for all names should be the same to satisfy the individual fairness. To make a connection to group fairness, following the study of Caliskan et al. (2017) that reveals the biases in word embed- dings, we evaluate the fairness of our sentiment classifier using male and female names typical for Caucasian and African-Amerien the sentiment of any name should be the same.
layer neural network with
ethnic groups We emphasize that to satisfy individual fairness,
Comparison metrics To evaluate the gap between two groups of names, No for Caucasian (or female) and NG for Afrrcan-American (or male), we report | Σner; (h(n); h(n)))) Not [A1] Enex, (h(n); - h(n)o), where h(n)& is logits for class i of name (k = is the positive class). We use list of names provided in Caliskan et al.] (2017), which consists of 49 Caucasian and 45 African-American names, among those 48 are female and 46 are male. The gap between African-American and Caucasian names is reported as Race gap, while the gap between male and female names is reported as Gend. gap in Table [ As in SSeer (0117), we also compare sentiment difference two sentences: "Let's go get Italian food"' and "Let's go get Mexican food", i.e. cuisine gap (abbreviated Cuis. gap in Table TT. as a test of generalization beyond names. To embed these sentences we average their word embeddings.
Sensitive subspace We consider embeddings of 94 names that we use for evaluation as sensitive directions, which may be regarded as utilizing the expert knowledge, i.e. these names form a list of words that an expert believes should be treated equally. Fair metric then defined using an orthogonal complement projector of the span of sensitive directions we discussed in Section 2. When expert knowledge is not available, or we wish to achieve general fairness for names, we utilize side dataset of popular baby names in New York City The dataset has 1 11 names, however only 32 overlap with the list of names used for evaluation. Embeddings of these names define a group of comparable samples that we use learn sensitive directions with SVD (see Appendix [.2 and Algorithm 3 for details). We take top 50 singular vectors to form the sensitive subspace. It is worth noting that, unlike many existing approaches in the fairness literature, we do not use any protected attribute information. Our algorithm only utilizes training words, their sentiments and vanilla list of names.
Results From the box-plots Figure we see that both race and gender gaps are significant when using the baseline neural network classifier. It tends to predict Caucasian names as "positive", while the median for African-American names is negative; the median sentiment for female names is higher than that for male names. We considered three other approaches to this problem: the algo- rithm of Bolukbasi et al. (2016) for pre- pre-processing word embeddings; pre-processing via projecting
titled "Popular Baby Names" and available from https:///taattat data. dww.aaago//daaaeeeeee.oo

---

Published as a conference paper at ICLR 2020
Table Summary of Adult classification experiments over 10 restarts
B-Acc,%
S-Con.
GR-Con.
Gape
RMS
Gapı
IMS
Gap
max
Gap
max
SenSR
78.9
.934
984
.068
.055
.087
.067
Baseline
82.9
.848
8655
.179
.089
.216
.105
Project
82.7
.868
1.00
.145
.064
.192
.086
Adv. Debias.
81.5
.807
.841
.082
.070
.110
.078
CoCL 79.0
.163
.080
.201
.109
out the sensitive subspace that we used for training SenSR (this is analogous to Prost et al. (2019); training distributionally robust classifier with Euclidean distance cost (Sinha al.) (017)) All approaches improved upon the baseline, however only SenSR can be considered individually fair.
Our algorithm practically eliminates gender and racial gaps and achieves the notion of individual fairness as can be seen from almost equal predicted sentiment score for all names. We remark that using expert knowledge (i.e. evaluation names) allowed SenSR-E (E for expert) to further improve both group and individual faimess. However we warn practitioners that if the expert knowledge is too specific, generalization outside of the expert knowledge may not be very good. In Table | we report results averaged across 10 repetitions with 90%/10% train/test splits, where also verify that accuracy trade-off with the baseline is minor. the right column we present the generalization check, i.e. comparing pair of sentences unrelated to names. Utilizing expert knowledge led to a fairness over-fitting effect, however we still see improvement over other methods. When utiliz- ing SVD of larger dataset of names we observe better generalization. Our generalization check suggests that fairness over-fitting is possible, therefore datasets and procedure for verifying fairness generalization are needed.
4.2 ADULT
Problem formulation Demonstrating the broad applicability of SenSR outside of natural language processing tasks, we apply SenSR to classification task on the Adull (Dua & Graff, (017)) data set to predict whether an individual makes at least $50k based on features like gender and occupation for approximately 45,000 individuals. Models that predict income without fairness considerations can contribute to the problem of differences in pay between genders or races for the same work. Throughout this section, gender (male female) and race (Caucasian con-Caucasian) are binary.
Comparison metries Arguably classifier is individually unfair if the classifications for two data points that are the same on all features except demographic features are different. Therefore, to assess individual fairness, report spouse consistency (S-Con.) and gender and race consistency (GR-Con.),, which are measures of how often classifications change only because differences in demographic features. For S-Con (resp. GR-con), we make (resp. 4) copies of every data point where the only difference is that one is a husband and the other is a wife (resp. difference is in gender and race). S-Con (resp. GR-Con) is the fraction of corresponding pairs (resp. quadruples) that have the same classification. We also report various group fairness measures proposed by De-Arteagal al. (2019) with respect race or gender based on true positive rates, i.e. the ability of classifier to correctly identify a given class. See Appendix D.5 for the definitions. We report Gap RMS Gap RMS Gap max and Gap mix where Rt refers to race, and G refers to gender. We use balanced accuracy (B- acc) instead of accuracy to measure predictive ability since only 25% of individuals make at least $50k.
Sensitive subspace Let (( ). be the of features 3; RD of the data except the coordinate for gender is zeroed and where Zg. indicates the gender of individual i. For & > O, let Wy arg min
Fz..
-== -Fg, (w 2;)) log(1 e= "="",) + 7||l]|2, i.e. Wy is the learned hyperplane that classifies gender given by regularized logistic regression. Let eg E RD (resp. e,) be the vector that is 1 in the gender (resp. race) coordinate and 0 elsewhere. Then the sensitive subspace is the span of [Mig. Eg. e, See Appendix B.I for details.
Accuracy reported in Table in Appendix D
8

---

Published as a conference paper at ICLR 2020
Results See Table 2 for the average of each metric the test splits for Baseline, Project (projecting features onto the orthogonal complement of the sensitive subspace before training). CoCL (De-Arteaga et al., 2019), Adversarial Debiasing (Zhang et al. 2018), and SenSR. With the exception of CoCL. (De- et al, 2019), each classifier is a 100 unit single hidden layer neural network. The Baseline clearly exhibits individual and group fairness violations. While SenSR has the lowest B-acc, SenSR is the best by large margin for S-Con. and has the best group fairness measures. We expect SenSR do well on GR-consistency since the sensitive subspace includes the race and gender directions. However, SenSR's ' individually fair performance generalizes: the sensitive directions do not directly use the husband and wife directions, yet SenSR performs well S-Con. Furthermore, SenSR outperforms Project on S-Con and group fairness measures illustrating that SenSR does much more than just ignoring the sensitive subspace. CoCL. only barely improves group fairness compared to the baseline with significant drop in B- acc and while Adversarial Debiasing also improves group fairness, it is worse than the baseline on individual fairness measures illustrating that group fairness does not imply individual fairness.
ten 80%/20% train/test
SUMMARY
We consider the task of training ML systems that are fair in the sense that their performance is invariant under certain perturbations of individual fairness (Dwork et al. (011). One of the main barriers to the adoption of individual fairness the lack of consensus on a fair metric for many MI tasks. To circumvent this issue, we consider two approaches to learning a fair metric from data: one for problems in which the sensitive attribute is observed, and another for problems in which the sensitive attribute is unobserved. Given data-driven choice of fair metric, provide algorithm that provably trains individually fair ML models.
sensitive subspace. This notion of fairness is variant
ACKNOWLEDGMENTS
This work was supported by the National Science Foundation under grants DMS-1830247 and DMS-1916271.
REFERENCES
Solon Barocas and Andrew Selbst. Big Data's Disparate Impact. SSRN Electronic Journal, 2016.
ISSN 1556-5068. doi: 10.2139/sm.2477899
Rachel K. F. 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, Monin- der Singh, Kush Varshney, and Yunfeng Zhang. AI Fairness 360: extensible toolkit for detecting, understanding, and mitigating unwanted algorithmic bias, October 2018. URL https: /tttps://arxiie owg/oogg///so..ooooooooe abs /1800 01943
Aharon Ben-Tal, Dick den Hertog, Anja De Waegenaere, Bertrand Melenberg, and Gijs Rennen. Robust Solutions of Optimization Problems Affected by Uncertain Probabilities. Management Science, (92)3441-335, November 2012. ISSN 1025-1909, doi: 10. 12872mssc.. 1 22....1666 1641.
Marianne Bertrand and Sendhil Mullainathan. Are Emily and Greg More Employable Than Lakisha and Jamal? A Field Experiment on Labor Market Discrimination. American Economic Review, 94(4))991-1011 September 2004. ISSN 0002-8282. doi: 10. 00.1237/000232324200256
Jose Blanchet and Karthyek R. Murthy. Quantifying Distributional Model Risk via Optimal Transport. arXiv:1604.01444 [math, stat], April 2016.
Jose Blanchet, Yang Kang, and Karthyek Murthy. Robust Wasserstein Profile Inference and Appli- cations to Machine Learning. urXiv:1610.0500
[math, stat], October 2016.
"The standard error is reported in the supplement. Each standard error within 10%

---

Published as a conference paper at ICLR 2020
Tolga Bolukbasi, Kai- Wei Chang. James Y Zou, Venkatesh Saligrama, and Adam T Kalai. Man is to computer programmer as woman to homemaker? debiasing word embeddings. In Advances in neural information processing systems, pp. 3349-4357, ,357,2016
Aylin Caliskan, Joanna Bryson, and Arvind Narayanan. Semanties derived automatically from language corpora contain human-like biases. Science, 456(6333):183-11)) April 2017. ISSN 0036-8075, 9993. doi: 10.1 1..116/siencc..aa42233.
Nicholas Carlini and David Wagner. Towards Evaluating the Robustness of Neural Networks. 1608. 04644 [cs], August 2016.
Xin Chen, Melvyn Sim, and Peng Sun. A Robust Optimization Perspective on Stochastic Program- ming. Operations Research, 55:1058-1071, 2007. doi: (0.1287/opre.1070.00
Alexandra Chouldechova. Fair prediction with disparate impact: A study of bias in recidivism prediction instruments. arXiv: 1703,00000 (cs, stat], February 2017.
Maria De-Arteaga, Alexey Romanov, Hanna Wallach, Jennifer Chayes, Christian Borgs, Alexan- dra Chouldechova, Sahin Geyik, Krishnaram Kenthapadi, and Adam Tauman Kalai. Bias in bios: A case study semantic representation bias a high-stakes setting. arXiv preprint 19X1v:1901.09451, 2019.
Erick Delage and Yinyu Ye. Distributionally Robust Optimization Under Moment Uncertainty with Application to Data-Driven Problems. Operations Research, 58:595-612, 2010. doi: 10.1287/
opre.1090.0741.
Dheeru Dua and Casey Graff. UCI machine learning repository, 2017. UtLtttp://archivee
Res.uci.. eddumml
Cynthia Dwork, Moritz Hardt, Toniann Pitassi, Omer Reingold, and Rich Zemel. Fairness Through Awareness. arXiv: 3913 [cs], April 2011.
Harrison Edwards and Amos Storkey. Censoring Representations with an Adversary. arX1v:1511.05897 [cs, stat], November 2015.
Peyman Mohajerin Esfahani and Daniel Kuhn. Data-driven Distributionally Robust Optimization Using the Wasserstein Metric: Performance Guarantees and Tractable Reformulations, May 2015.
Sahaj Garg, Vincent Perot, Nicole Limtiaco, Ankur Taly, Ed Chi, and Alex Beutel. Counter- factual fairness in text classification through robustness. In Proceedings of the 2019 AAAI/ACM Conference on AI, Ethics, and Society, pp. 219-226. ACM, 2019.
Joel Goh and Melvyn Sim. Distributionally Robust Optimization and Its Tractable Approximations. Operations Research, (8(4-part-1):2)) 1):902 917, August 2010. ISSN 0030-364X, 1526-5463. doi: 10. 10.1287/opre.10900077
Ian J. Goodfellow, Jonathon Shlens, and Christian Szegedy. Explaining and Harnessing Adversarial Examples. December 2014.
Tatsunori B. Hashimoto, Megha Srivastava, Hongseok Namkoong, and Percy Liang. Fairness With- out Demographics Repeated Loss Minimization. 1806:00000 [cs, stat), June 2018.
Minqing Hu and Bing Liu. Mining and summarizing customer reviews. In Proceedings of the tenth ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 168-177. ACM, 2004.
Christina Ilvento. Metric Learning for Individual Fairness. arXiv:1906.0023: [cs, stat], June 2019.
Harini Kannan, Alexey Kurakin, and Ian Goodfellow. Adversarial logit pairing. arXiv preprint arXiv:1803.06373. 2018
Diederik Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint 1:Xiv:14/2.69000 2014.
10

---

Published as a conference paper at ICLR 2020
Jon Kleinberg, Sendhil Mullainathan, and Manish Raghavan. Inherent Trade-Offss in the Fair Deter- mination of Risk Scores. arXiv:1609.05807 [cs, stat], September 2016.
Alexey Kurakin, Ian Goodfellow, and Samy Bengio. November 2016.
Adversarial Machine Learning at Scale.
H. Lam and Enlu Zhou. Quantifying uncertainty in sample average approximation. 20/5 Win- ter Simulation Conference (WSC), pp. 3846-3857, December 2015. doi: 10.1109/WSC.201.. 7408541.
Jacho Lee and Maxim Raginsky. Minimax Statistical Learning with Wasserstein Distances. 1705.0170 [es], May 2017.
David Madras, Elliot Creager, Toniann Pitassi, and Richard Zemel. Learning Adversarially Fair and Transferable Representations. 1XXi::8822.0630 [cs, stat], February 2018.
Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. Towards Deep Learning Models Resistant to Adversarial Attacks. arXiv: 06003 [cs, stat), June 2017.
Cade Metz and Adam Satariano. An Algorithm That Grants Freedom, or Takes It Away The New York Times, February 2020. ISSN 0362-4331.
Takeru Miyato, Shin-ichi Maeda, Masanori Koyama, Ken Nakae, and Shin Ishii. Distributional Smoothing with Virtual Adversarial Training. arXiv:1507.00677 [cs, stat], July 2015.
Hongseok Namkoong and John C. Duchi. Stochastic Gradient Methods for Distributionally Robust Optimization with F-divergences. In Proceedings of the 30th International Conference on Neu- ral Information Processing Systems, NIPS' 16, pp. 2216-2224, Barcelona, Spain, 2016. Curran Associates Inc. ISBN 978-1-5108-38811
Nicolas Papernot, Patrick McDaniel, Somesh Jha, Matt Fredrikson, Z. Berkay Celik, and Ananthram Swami. The Limitations of Deep Learning in Adversarial Settings. November 2015.
Jeffrey Pennington, Richard Socher, and Christopher Manning. Glove: Global vectors for word representation. In Proceedings of the 2014 conference on empirical methods in natural language processing (EMNLP), pp. 1532-1543, 2014.
Flavien Prost, Nithum Thain, and Tolga Bolukbasi. Debiasing embeddings for reduced gender bias in text classification. arXiv preprint arXiv: /90.//9088888 02810, 2019.
Ya acov Ritov, Yuekai Sun, and Ruofei Zhao. On conditional parity as a notion non- discrimination in machine learning. 1706:07706.08.. [cs, star], June 2017.
Soroosh Shatiezzadeh-Abadeh. Peyman Mohajerin Esfahani, and Daniel Kuhn. Distributionally Robust Logistic Regression. September 2015.
Aman Sinha, Hongseok Namkoong, and John Duchi. Certifying Some Distributional Robustness with Principled Adversarial Training. arXiv:1710. 10551 [cs, stat], October 2017.
Robyn Speer. How to make a racist ai without really trying, 2017.
Christian Szegedy, Wojciech Zaremba, Ilya Sutskever, Joan Bruna, Dumitru Erhan, Ian Goodfellow, and Rob Fergus. Intriguing properties of neural networks. December 2013.
Hanchen Wang. Nina Grgic-Hlaca, Preethi Lahoti, Krishna Gummadi, and Adrian Weller. An Empirical Study on Learning Fairness Metrics for COMPAS Data with Human Supervision. arXiv:1910. 10255 [es], October 2019.
Brian Hu Zhang, Blake Lemoine, and Margaret Mitchell. Mitigating Unwanted Biases with Adver- sarial Learning. / [cs], January 2018.
11

---

Published as a conference paper at ICLR 2020
A PROOFS
A.1 PROOF OF PROPOSITION 3.1
By the duality result of Blanchet & Murthy 2016), for any > O,
Er(e(Z,0) P.W(P.P))
Ep [p[
sup (...(P..))s
sup
inf (de + Ep. [1 (2, 0)] - An + Rp, [ (2.0) A20
$ Ep. [ (2,0) - Ep. [ (2,0)
where An E arg me + Ep,
(2, By assumption A3,
1x (2, Ex (2,
- sup (((12, v). 0) - LaEE
- sup {((22,)),0) - 2)) x2x
s sup An|e, ((x, y). (22, u)) - c(( (l) (x2,3)))
mIEt
S dn D²
This implies
Ep [(Z,6)]
Ep [(2 0)
sup (P..(P.P)S.
sup P.W(P.P,)Sc
< Ep. [ (Z, 0) - EE,, (x (2 + A2
This bound is crude; it possible obtain sharper bounds under additional assumptions on the loss and transportation cost functions. We avoid this here to keep the result as general as possible. Similarly.
Ep[{(2,0)]
Ep[e(2,0) 0]]
sup P.W(P.P.)Se
sup P.P.(F...).:
$ Ep [RS. (Z, -Ep. (x.
$ Ep. 1x (Z,0) - Ep. 1 (2,0) + AxS.DD2
where X, arg min (e Ep, [ex (2, 0)]}
Lemma A.1 (Lee& & Raginsky 2017).. Let Ā arg min + Ep (Z,0)) As long the function in the loss class are L-Lisschitz with respect to dy (see Assumption A2), s VE
Proof. By the optimality of X,
de < de + Ep
sup E((22, (), - - EEE
λe + Ep [ (Z, 0) [(2,0)
< dE + Ep Ep (2, 0) - [(2,0)
Ae + Epl sup E((22, Y), -) xGE
for any 2 0. By Assumption A2, the right side is at most
de 5 de Ep sup Ld, (X, (X, 2gE
S de + sup Lt 2t2
120
We minimize the right side WRT (set t
2x) and (set A 2 to obtain de < Lve.
12

---

Published as a conference paper at ICLR 2020
By Lemma A.1
we have
Lå
Ep []]
Ep [(2,0) < Ep. ( (2,0) - Ep, ( (2,0))
sup (...(...))s
sup P.W(P,Pa)se
VE
L5
sup (P..
Ep [(2,))
sup P.W.(P...)s
(5,02),) Ep [(2 - Ep, [2 (2, 0)] Er (2,
Ve
We combine the preceding bounds to obtain
Ep [p(e(Z,))] sup P.W.(P.P...
Ep [p(e(Z,))]
sup (c.)
LS.D²
$ sup
1l2 ( -P)(2)) sec-
Vt
where L. - (3,00 X E [0, 11, E O) is the DR loss class. In the rest of the proof, we bound sep 1s f())d(P. - (=)( with standard techniques from statistical learning theory. Assumption A2 implies the functions in F are bounded:
f ((((1)(11))) v1). 0) Ad - (21.0) sup (((22. M.
22EX
This implies has bounded differences, so 5, concentrates sharply around its expectation. By the boufded-differences inequality and symmetrization argument,
log 2 2m
sup 1l f(:)d(P, - P.)(z) (C M fec
1)
WP least t, where (F) is the Rademacher complexity F:
1
(F) E
sup = Σ oz)) LEEF n 1=1
Lemma A.2. The Rademacher complexity of the DR loss class most
24C(C)
24LD²
(c)) Vn
Vnc
Proof. To study the Rademacher complexity of L we first show that the Ln-indexed Rademacher
process X, A SE=19, (Zz) is sub-Gaussian WRT to a pseudometric. Let fi = (3 and
fe = (, (2))). Define
de-(Si, A [[((-01) 0(.102)llo + D21Ai -22/-
We check that Xy uub-Gaussian WRT des:
exp((((Xx; - -x1))
t
E [exp
a1, (Z,, 01) Cx (2,)
= =expx _ (Cs, (Z) Ex (2, (2,62)))!"
n
-Exexp -o( sup inf (((21, 01) -1,, -(((2, Y),02) + x2, x2
"
=Elexp( - sup A((01, Y),0,) E((21, ()00) 022 (21, MEx
Let N(C STCC,dge,6 c) be the c-covering number of (L", dg:). We observe
N(C <N(C. ||,o $ N(0, 41111 2
(A.1)
13

---

Published as a conference paper at ICLR 2020
By Dudley's 's entropy integral,
12
(c9) v
log (Cc,
Vn
12
(log N(C, 11 +) +e111 25=z) $ de
vn
12
NCC, -1.0, 5) + Joe N(10, tel:l 11 2552 ) )
log
Vn
(4)(C)
24LD²
L 1 log(? )de
vn
Vnc
where recalled equation A. in the second step. We evalaute the integral the right side to arrive at the stated bound: Jo log( )d 1.
By Lemma A.2
1l2 [()d(() P.)(2)) S 48E(C) Vn
48LD² Vne
log 2 L )
sup fec
+ M
2n
which implies
Ep [p(2(2,0)]
Ep (e(2 01]
sup (.
sup r.W.(P,P.)s
48E(C)
4
D
log 2
+ M
)
vn
VNE
Ve
2n
WP at least
A.2 PROOFS PROPOSITIONS 3.2
AND 3.3
Proof of Proposition 3.2
It is enough to show
(B [p( 0 + 28,
because the loss function non-negaeive. We have
Ep [((2,0]] 5 sup (:W(P.P))
Ep ((2, 0)] + 6n
sup (F.P.).
sup P.W (P.PaSe
Ep [22 0)] + +6,
Ep [(, 0) + 28,
(.,.(F,P.)s
< 8" + 28,.
Proof of Proposition 3.3
[Ep[[[Z,0]] - -Ep, [[(2,)]])
(Ep 0) -Ep, [e(Z, 0))
sup P.W.(P.P.)s
sup P.W(P.P.)s. [p[[(Z,0] Ep, [[(Z,0) Ep, [{(2,0)
(PP.js.P.jSe Ep [p([(Z))]
sup
sup (.P.a.P
<6,- - Ep. ((2,0)) - E.p, [((2,))
The loss function is bounded, so it is possible to bound E,, [[(Z,)) - Er, [?(Z,6)] by standard uniform convergence results on bounded loss classes.
14

---

Published as a conference paper at ICLR 2020
B DATA-DRIVEN FAIR METRICS
B.1 LEARNING THE FAIR METRIC FROM OBSERVATIONS OF THE SENSITIVE ATTRIBUTE
Here we assume the sensitive attribute is discrete and observed for small subset of the training data. Formally, we assume this subset of the training data has the form f(X,, K2, Yi)), where K; is the sensitive attribute of the i-th subject. To learn the sensitive subspace, we fit softmax regression model to the data
exp(a X, + bi) Σ exp(a X; b1)
P(K: = x1)
1= L...,,k
and take the span of A (ai ... as) as the sensitive subspace define the fair metric
d (2,, = (a1 - x2 (ran(A))( -22)-
(B.1)
This approach readily generalizes sensitive attributes that not discrete-valued: replace the softmax model by an appropriate generalized linear model.
In many applications, the sensitive attribute is part of user's demographic information, may not be available due to privacy restrictions. This does not preclude the proposed approach because the sensitive attribute is only needed to learn the fair metric and is neither needed to train the classifier nor at test time.
B.2 LEARNING THE FAIR METRIC FROM COMPARABLE SAMPLES
In this section, we consider the task of learning fair metric from supervision form compa- rable samples. This type of supervision has been considered in the literature on debiasing learned representations. For example, method of Bolukbasi et al. (2016) for removing gender bias word embeddings relies on sets of words whose embeddings mainly vary in gender subspace (e.g. (king, queen)).
To keep things simple, we focus on learning generalized Mahalanobis distance da (x1, x2) (v((x)) - (xx2)) E(p(x1) - (
(B.2)
where c(()): X - Rd is known feature map and Σ E s is covariance matrix. Our approach based on factor model
6 A.u, + B_v; + Ei.
where P; E Rd the learned representation of IG u; E R (resp. v; E R4) is the sensi- tive/irrelevant (resp. relevant) attributes of x; the task at hand, and e; an error term. For example, in [Bolubasi et al. (2016), the learned representations are the embeddings of words in the vocabu- lary, and the sensitive attribute the gender bias of the words. The sensitive and relevant attributes are generally unobserved.
Recall our goal is obtain E so that equation B.2 3.2ix is small whenever 01 U2. One possible choice of Σ is the projection matrix onto the orthogonal complement of ran(A), which we denote by Pran(A)- Indeed,
de dx(, = (11 122) Pran(1))((p1 - .p2) -
(B.3)
2 (21-v2) Dºd A) B. 22))
(B.4)
which is small whenever i1 U2 Although ran(A) is unknown, it is possible estimate it from the learned representations and groups of comparable samples by factor analysis.
The factor model attributes variation in the learned representations to variation in the sensitive and relevant attributes. We consider two samples comparable if their relevant attributes are similar. In other words, I [n] is (the indices of) group of comparable samples, then
H HUZAT HFz. # HU HVB.
(B.5)
15

---

Published as a conference paper at ICLR 2020
where H ||z [2] 1zz is the centering or de-meaning matrix and the rows of dx (resp. Uz, Vz) are Pi (resp. u4 0z). If this group of samples have identical relevant attributes, i.c. Vz = 1z1 for some v, then HVz vanishes exactly. As long as and are uncorrelated (e.g. B B[ure]] 0),
equation B.3 implies
E 2 H = HE + HE]],
This suggests estimating ran( from the learned representations and groups of comparable samples by factor analysis. We summarize our approach in Algorithm 3
Algorithm 3 estimating Σ for the fair metric
I: Input: (- comparable groups I1, ,,....,
2: A E arg minw,.at 1 Eg=1 H - W, 11
D factor analysis
3: Q t (A)
> get orthonormal basis of ran(AA
4: Σ t la - QQ"
C SENSR IMPLEMENTATION DETAILS
This section is to accompany the implementation of the SenSR algorithm and is best understood by reading along with the code implemented using TensorFlow We discuss choices learn- ing rates and few specifies of the code. Words in italics correspond to variables in the code and following notation in parentheses defines corresponding name in Table where we summarize all hyperparameter choices.
Handling class imbalance Datasets study have imbalanced classes. To handle it, every epoch(F) (i.e. number of epochs) we subsample batch size( training samples enforcing equal number of observations per class. This procedure can be understood data augmentation.
Perturbations specifies Our implementation of SenSR algorithm has two inner optimization prob- lems - subspace perturbation and full perturbation (when e > 0). Subspace perturbation can be viewed initialization procedure for the attack. We implement both using Adam optimizer (Kingma & Ba| 2014) inside the computation graph for better efficiency, i.e. defining correspond- ing perturbation parameters Variables and re-setting them zeros after every epoch. This is in contrast with a more common strategy in the adversarial robustness implementations. where pertur- bations (i.e. attacks) are implemented using tf if..gradeets with respect to the input data defined Placeholder.
Learning rates As mentioned above, in addition to regular Adam optimizer for learning the pa- rameters invoke rate of 0.001 for the parameters optimizer, however different learning rates across datasets for sub- space_step(s) and full_step(f), Two other related parameters are number of steps of the inner opti- mizations: subspace epoch(se) and full cellleepoc((e) We observed that setting subspace perturbation learning rate too small may prevent our algorithm from reducing unfairness, however setting big does not seem to hurt. On the other hand, learning rate for full perturbation should not be set too big as it may prevent algorithm from solving the original task. Note that full perturbation learning rate should be smaller than perturbation budget eps(e) we always use //10. In general, malfunction- ing behaviors are immediately noticeable during training and can be easily corrected, therefore we did not need to any hyperparameter optimization tools.
for the inner optimization problems of SenSR. We same learning
htttp::/giitie com/ HBM wwwsienniiiiie.ee www.tteeeesspeeeeeeeeeeeeeeee
16

---

Published as a conference paper at ICLR 2020
Table SenSR hyperparameter choices in the experiments
E
B
fe
Sentiment
4K
1K
0.1
0.01
Adult
12K
IK
10
50
10-3
10
40
Table Summary of Adult classification experiments over 10 restarts
Accuracy
B-TPR
Gapg
RMS
Gap
RMS
Gap
max
Gap
max
SenSR
.7872.003
.7894.003
.068..004
.055..003
.087=.005
.067:.004
Baseline
.8131.001
.8991.001
.179=.004
.089:1003
.216-0003
.105=+.003
Project
.813+.001
827+-001
.04
0064+-003
.192= .00
.086+-004
Adv. Debias.
.812+.001
.815+0002
.082+.005
.070==006
.110=.006
.078++005
CoCL
.790
.163
.080
.201
.109
D ADDITIONAL ADULT EXPERIMENT DETAILS
D.1 PREPROCESSING
The continuous features in Adult are the following: age, fnlwgt, capital-gain capital-loss, hours-per-week, and education-num. The categorical features the following: workclass, education,
occupation. relat ionship, See Dua & Graff (2017) for description of each feature. We
race, sex, native- remove wgtt and education but keep educat i oon-num which is a integer representation of education. We do not use vetivveccuutry. but
and sex predictive features. We treat race as binary: individuals are either White or non-White. For every categorical feature, use hot encoding. For every continuous feature, we standardize, i.c., subtract the mean and divide by the standard deviation. We remove anyone with missing data leaving 45 2,22 individuals.
This data is imbalanced: 25% make least $50k per year. Furthermore, there is demographic imbal- ance with respect to race and gender as well as class imbalance on the outcome when conditioning on race or gender: 86% of individuals are white of which 26% make least $50k year; 67% of individuals are male of which 31 % make at least $50k a year; 11% of females make at least $50k year; and 15% of non-whites make at least $50k a year.
D.2 FULL EXPERIMENTAL RESULTS
See Tables 4 and for the full experiment results. The tables report the average and the standard emrrr for each metric on the test set for 10 train and test splits.
D.3 SENSITIVE SUBSPACE
To learn the hyperplane that classifies females and males, we use our implementation of regularized logistic regression with a batch size of 5k, 5k epochs, and .1 & regularization.
Table Summary individual fairnsss metrics in Adult classification experiments over 10 restarts
Spouse Consistency
Gender and Race Consistency
SenSR
934=.012
.98++.000
Baseline
848 +40
8855+.004
Project
.868 .005
1::0
Adv. Debias.
807=.002
84 8412
17

---

Published as a conference paper at ICLR 2020
D.4 HYPERPARAMETERS AND TRAINING
For each model, we use the same 10 train/test splits where use 80% of the data for training. Because of the class imbalance, each minibatch is sampled so that there are equal number of training points from both the "income at least $50k class" and the "income below S50k class."
D.4.1 BASELINE, PROJECT, AND SENSR
See Table B the hyperparameters we used when training Baseline, Project, and SenSR (Baseline and Project use subset). Hyperparameters are defined in Appendix C
D.4.2 ADVESARIAL DEBIASING
We used Zhang et al. 2018) advensarial debiasing implementation in IBM's AIF360 package (Bel-) lamy et al., 2018) where the source code was modified so that each mini-batch is balanced with respect the binary labels just did with experiments and dropout not used. Hyperpa- rameters are the following: adversary loss weight = ,001, num epochs = 500, batch size = 1000, and privileged groups are defined by binary gender and binary race.
D.5 GROUP FAIR METRICS
Let C be a set of classes, A be a binary protected attribute and Y, E C be the true class label and the predicted class label. Then for {0, 1) and c E C define TPR,,c P(Ý c = a, Y = c);
GaPA,- TPRo, TPR1, Gap
RMS = 1 [C| Eeer Gap Gap arg max Gap A,cl:
Balanced Acc [CT Enec P(Ý c|Y c)..
For Adult, we report Gap Gap that correspond to whether someone made at least $50k, R. refers to race, and G' refers to gender.
RMS Gap and Gap mapman where C is composed of the two classes
18


Reviews:
[{"review_id": "r1xmBTKkqH", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "\nSummary\nThe authors propose training to optimize individual fairness using sensitive subspace robustness (SenSR) algorithm.\n\nDecision\nOverall, I recommend borderline as the paper seems legit in formulating the individual fairness problem into a minmax robust optimization problem. The authors show improvement in gender and racial biases compared to non-individual fair approaches. However, I think some sections are hard to follow for people not in the field.\n\nSupporting argument:\n1. End of P3, it is not clear to me why solving the worst case is better.\n2. Though this paper studied individual fairness, can it also work for group fairness? I am not sure whether this is the only work in this direction (baselines are not for individual fairness).\n3. Some of the metrics in the experiments are not precisely defined such as Race gap, Cuis. gap, S-Con, GR-Con. It is hard to follow from the text description. \n4. Some baseline models are not clearly defined such as “Project” in Table 1.\n5. Not sure how Section 3 connects with the rest of the paper.\n\n\nAdditional feedback:\n1. Missing reference: https://arxiv.org/abs/1907.12059\n2. What’s TV distance in introduction?\n", "extra_scores": {"experience_assessment": "I do not know much about this area.", "review_assessment:_thoroughness_in_paper_reading": "I made a quick assessment of this paper.", "review_assessment:_checking_correctness_of_experiments": "I did not assess the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I did not assess the derivations or theory."}, "extra_text": {}}, {"review_id": "Syx0-bXNcB", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "General:\nThe authors propose a method to train individually fair ML models by pursuing robustness of the similarity loss function among the comparable data points. The main algorithmic tool of training is borrowed from the recent adversarial training, and the paper also gives the theoretical analyses on the convergence property of their method. \n\nPros:\n1. They make the point that the individual fairness is important. \n2. The paper proposes a practical algorithm for achieving the robustness and the indivdual fairness. Formulating that the main criterion for checking the fainess is Eq.(2.1), the paper takes a sensible route of using dual and minimax optimization problem (2.4).\n3. The experimental results are compelling – while the proposed method loses the accuracy a bit, but shows very good individual fairness under their used metric. \n\nCons & Questions:\n1. What is the empirical convergence property of the algorithm? How long does it take to train for the experiments given?\n2. It seems like the main tools for algorithm and theory are borrowed from other papers in adversarial training e.g., (Madry 2017). Are their any algorithmic alternatives for solving (2.4)?\n3. Why do you use d_z^2 instead of d_z for defining c(z_1,z_2)?\n4. What happens when you use more complex models than 1 layer neural net?", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "SJlzds52FS", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper proposes a new definition of algorithmic fairness that is based on the idea of individual fairness. They then present an algorithm that will provably find an ML model that satisfies the fairness constraint (if such a model exists in the search space). One needed ingredient for the fairness constraint is a distance function (or \"metric\") in the input space that captures the fact that some features should be irrelevant to the classification task. That is, under this distance function, input that differ only in sensitive attributes like race or gender should be close-by. The idea of the fairness constraint is that by perturbing the inputs (while keeping them close with respect to the distance function), the loss of the model cannot be significantly increased. Thus, this fairness constraint is very much related to robustness.\n\n---\n\nOverall, I like the basic idea of the paper but I found the presentation lacking.\n\nI do think their idea for a fairness constraint is very interesting, but it gets too bogged down in the details of the mathematical theory. They mention Dwork et al. at the beginning but don't really compare it to their idea in detail, even though I think there would be a lot of interesting things to say about this. For example, the definition by Dwork et al. seems to imply that some labels in the training set might be incorrect, whereas the definition in this paper does not seem to imply that (which I think is a good thing).\n\nThe main problem in section 2 is that the choice of distance function is barely discussed although that's what's most important to make the result fair. For all the mathematical rigor in section 2, the paragraph that is arguing that the defined constraint encourages fairness is somewhat weak. Here a comparison to other fairness definitions and an in-depth discussion of the distance function would help.\n\n(In general I felt that this part was more trying to impress the reader than trying to explain, but I will try to not hold it against this paper.)\n\nAs it is, I feel the paper cannot be completely understood without reading the appendix.\n\nThere is also this sentence at the bottom of page 5: \"A small gap implies the investigator cannot significantly increase the loss by moving samples from $P_*$ to comparable samples.\" This should have been at the beginning of section 2 in order to motivate the derivation.\n\nIn the experiments, I'm not sure how useful the result of the word embedding experiment really is. Either someone is interested in the sentiment associated with names, in which case your method renders the predicted sentiments useless or someone is not interested in the sentiment associated with names and your method doesn't even have any effect.\n\nFinal point: while I like the idea of the balanced TPR, I think the name is a bit misleading because, for example, in the binary case it is the average of the TPR and the TNR. Did you invent this terminology? If so, might I suggest another name like balanced accuracy?\n\nI would change the score (upwards) if the following things are addressed:\n\n- make it easier to understand the main point of the paper\n- make more of a comparison to Dwork et al. or other fairness definitions\n- fix the following minor mistakes\n\nMinor comments:\n\n- page 2, beginning of section 2: you use the word \"regulator\" here once but everywhere else you use \"investigator\"\n- equation 2.1: as far as I can tell $M$ is not defined anywhere; you might mean $\\Delta (\\mathcal{Z})$\n- page 3, sentence before Eq 2.3: what does the $\\#$ symbol mean?\n- page 3, sentence before Eq 2.3: what is $T$? is it $T_\\lambda$?\n- Algorithm 2: what is the difference between $\\lambda^*_t$ and $\\hat{\\lambda}_t$?\n- page 7: you used a backslash between \"90%\" and \"10%\" and \"train\" and \"test\". That would traditionally be a normal slash.\n- in appendix B: the explanation for what $P_{ran(A)}$ means should be closer to the first usage\n- in the references, you list one paper twice (the one by Zhang et al.)\n\nEDIT: changed the score after looking at the revised version", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper addresses individual fairness scenario (treating similar users similarly) and proposes a new definition of algorithmic fairness that is based on the idea of robustness, i.e. by perturbing the inputs (while keeping them close with respect to the distance function), the loss of the model cannot be significantly increased.
All reviewers and AC agree that this work is clearly of interest to ICLR, however the reviewers have noted the following potential weaknesses: (1) presentation clarity -- see R3’s detailed suggestions e.g. comparison to Dwork et al, see R2’s comments on how to improve, (2) empirical evaluations -- see R1’s question about using more complex models, see R3’s question on the usefulness of the word embeddings. 
Pleased to report that based on the author respond with extra experiments and explanations, R3 has raised the score to weak accept. All reviewers and AC agree that the most crucial concerns have been addressed in the rebuttal, and the paper could be accepted - congratulations to the authors! The authors are strongly urged to improve presentation clarity and to include the supporting empirical evidence when preparing the final revision.
Decision: Accept (Spotlight)