SenSeI: Sensitive Set Invariance for Enforcing Individual Fairness
Authors: Mikhail Yurochkin
Yuekai Sun
Venue: ICLR 2021 Oral (2021)
Keywords: Algorithmic fairness
invariance

Abstract: In this paper, we cast fair machine learning as invariant machine learning. We first formulate a version of individual fairness that enforces invariance on certain sensitive sets. We then design a transport-based regularizer that enforces this version of individual fairness and develop an algorithm to minimize the regularizer efficiently. Our theoretical results guarantee the proposed approach trains certifiably fair ML models. Finally, in the experimental studies we demonstrate improved fairness metrics in comparison to several recent fair training procedures on three ML tasks that are susceptible to algorithmic bias.

Published as a conference paper at ICLR 2021
SENSEI: SENSITIVE SET INVARIANCE FOR ENFORC- ING INDIVIDUAL FAIRNESS
Mikhail Yurochkin
Yuekai Sun
IBM Research
Department of Statistics University of Michigan yueka @umi ch, edu
MIT-IBM Watson Al
mi khail, yurochk n fom.com
ABSTRACT
In this paper, we cast fair machine learning as invariant machine learning. We first formulate version of individual fairness that enforees invariance certain sensitive sets. We then design a transport-based regularizer that enforces this version of individual faimess and develop an algorithm to minimize the regularizer efficiently. Our theoretical results guarantee the proposed approach trains certifiably fair ML models. Finally, in the experimental studies we demonstrate improved fairness metrics in comparison to several recent fair training procedures on three ML tasks that are susceptible algorithmic bias.
INTRODUCTION
As machine learning (ML) models replace humans in high-stakes decision-making and decision- support roles, concern regarding the consequences of algorithmic bias is growing. For example, ML models are routinely used in criminal justice and welfare to supplement humans, but they may have racial, class, or geographic biases (Metz & Satariano, 2020). In response, researchers proposed many formal definitions of algorithmic fairness as first step towards combating algorithmic bias.
Broadly speaking, there two kinds of definitions of algorithmic fairness: group fairness and individual fairness. In this paper, we focus on enforcing individual fairness. At high-level, the idea of individual fairness is the requirement that a fair algorithm should treat similar individuals similarly. Individual fairness was dismissed as impractical because there is no consensus on which users are similar for many ML tasks. Fortunately, there is a flurry of recent work that addresses this issue (Ilvento, 2019; Wang et al., 2019; Yurochkin et al., 2020; Mukherjee et al., 2020). In this paper, we assume there is a similarity metric for the MI. task at hand and consider the task of enforcing individual fairness. Our main contributions are:
1. we define distributional individual fairness, a variant of Dwork et al. 's original definition of individual fairness that (i) more amenable to statistical analysis and (ii) easier to enforce by regularization;
we develop stochastic approximation algorithm to enforce distributional individual fairness when training smooth ML models;
we show that the stochastic approximation algorithm converges and the trained ML model generalizes under standard conditions;
4. we demonstrate the efficacy of the approach on three ML tasks that are susceptible to algorithmic bias: income-level classification, occupation prediction, and toxic comment detection.
2 ENFORCING INDIVIDUAL FAIRNESS WITH SENSITIVE SET INVARIANCE (SENSEI)
TRANSPORT-BASED DEFINITION OF INDIVIDUAL FAIRNESS
Let X and ) be the space of inputs and outputs respectively for the supervised learning task at hand. For example, in classification tasks, y may be the probability simplex. An ML model a function h X y in space of functions H (e.g. the set of all neural nets with certain architecture).

---

Published as a conference paper at ICLR 2021
Dwork et al. (2011) define individual fairness as L-Lipschitz continuity of an ML model h with respect to appropriate metrics on X' and V:
dy(h(x), h(x')) & (x,
(2.1)
for all 2, x' E X. The choice of dy is often determined by the form of the output. For example, if the ML model outputs vector of the logits, then we may pick the Euclidean norm dy (Kannan et al., 2018; Garg et al., 2018). The metric dx is the crux of (2.1) because it encodes our intuition of which inputs similar for the MI. task at hand. For example, in natural language processing tasks, dx may be metric on word/sentence embeddings that ignores variation in certain sensitive directions. In light of the importance of the similarity metric in (2.1) enforeing individual fairness, there is also line of work on learning the similarity metric from data (Ilvento, 2019; Wang et al., 2019; Mukherjee al., 2020). In our experiments, we adapt the methods from Yurochkin al. (2020) to learn similarity metrics.
Although intuitive, individual fairness is statistically and computationally intractable. Statistically, it is generally impossible to detect violations of individual fairness on zero measure subset of the sample space. Computationally, individual fairness is a Lipschitz restriction, and such restrictions are hard to enforce. In this paper, we address both issues by lifting (2. to the space of probability distributions on to obtain an "average case" version individual fairness. This version (i) is more data-dependent regularizer,
amenable to statistical analysis, (ii) is easy to enforce by minimizing and (iii) preserves the intuition behind Dwork et al. (2011)'s original definition of individual faimess.
Definition 2.1 (distributional individual fairness (DIF)). Let > 0 be tolerance parameters and A (X' x X) be the set of probability measures on X' x X. Define
Em (d))((()), En (X)) Se
suPпES(Xxx))
R(h) &
subject to
(2.2)
II(,, X') Px
where Px is the (marginal) distribution of the imputs in the ML task at hand. An ML model is (c, disttribbuti individually fair (DIF) iff R(h) S 6.
We remark that DIF only depends on h and Px. It does not depend on the (conditional) distribution of the labels Py|x, so it does not depend on the performance of the ML model. In other words. it is possible for a model to perform poorly and be perfectly DIF (e.g. the constant model h(x) = 0).
The optimization problem in (2.2) formalizes correspondence studies in the empirical literature (Bertrand & Duflo, 2016). Here is a prominent example.
Example 2.2. Bertrand & Mullainathan studied racial bias in the US labor market. The investigators responded to help-wanted ads in Boston and Chicago newspapers with fictitious resumes. To manipulate the perception of race, they randomly assigned African-American or white sounding names to the resumes. The investigators concluded there is discrimination against African-American Americans because the resumes assigned white names received 50% more callbacks for interviews than the resumes.
We view Bertrand & Mullainathan's 's investigation as evaluating the objective in (2.3) at a special T. Let X be the space of resumes, and h X > {0. 1 be the decision rule that decides whether resume receives a callback. Bertrand Mullainathan implicitly pick the T that reassigns the name on resume from an African-American sounding name to white one (or vice versa) and measures discrimination with the difference between callback rates before and after reassignment:
[1((( + M(T(X))) = P(((X) + M(T(X))
We consider distributional individual fairesss a variant of Dwork et al.'s original definition. is not a fundamentally new definition of algorithmic fairness because it encodes the same intuition as Dwork et al. 's original definition. Most importantly, it remains an individual notion of algorithmic fairness because it compares individuals to similar (close in dxx) individuals.
2.2 DIF VERSUS INDIVIDUAL FAIRNESS
is hard to directly compare Dwork et al. 's original definition of individual faimess and DIF directly. First, they are parameterized differently: the original definition (2.1) is parameterized by a Lipschitz
2

---

Published as a conference paper at ICLR 2021
constant L, while DIF is parameterized by an (c, pair. Intuitively, (2.1) enforces (approximate)
invariance at all scales (at any e >> 0), while DIF only enforces invariance at one scale (determined by the imput tolerance parameter). Second, (2.1) enforces invariance uniformly on X' while (2.2) enforces invariance on average. Although DIF seems a weaker notion of algorithmic fairness than (2.1) (average fairesss vs uniform fairness), DIF is actually more stringent in some ways because the constraints in (2.2) are looser. This is evident in the Mongé version of the optimization problem in (2.2):
Ep (P(d)(((X),
s
(2.3)
subject to Ex(dx(X,T(XX)) c.
The map corresponding to (2.1)
Tir(x) - arg max (x (xx
maps each x to its worse-case counterpart x' in (2.1). It is not hard to see that Tip is feasible map for (2.3), but it may not be optimal. This is because (2.3) only restricts T transport points by at most on average; the optimal 7 may transport some points by more than e.
To make the definitions more comparable, consider 6-ô version of individual fairness. A model h X' + y satisfies (e, -)-individual fairness at æ E X' if and only if
dy (((())
(u.)x().=)ss dy (h(),,, h(z')) S
(2.4)
To arrive at (2.4), we start by observing that (2.1) is equivalent to
supzex (y(ha)), (xTrr()))) < Le for any E X a'and 0.
We fix x and e and re-parameterize the right side with to obtain (2.4). is possible to show that if is (c, 5)-DIF, then there exists 5' such that it satisfies 8',8)) (c,d')-individua faimesss for "most" x's. We formally state this result in proposition.
Proposition 2.3. If h X + y is (c, 6)-E),, then
(x(d)(M()) 2 2) - for any T 0.
2.3 ENFORCING DIF
There are two general approaches to enforcing invariance conditions such as (2.2). The first is distributionally robust optimization (DRO):
mingEH Ladv (h) - supp:wa(P.P')s. Ep [e(Y[ M(X))),
(2.5)
where f is loss function and (P, Q) the Wasserstein distance between distributions on X x y induced by the transport cost function e( (I, y). (z'y')) & (x(xxx²)) oo i + s/). This approach is very similar to adversarial training, and it was considered by Yurochkin et al. (2020) for enforcing (their modification of) individual fairness. In this paper, we consider a regularization approach to enforcing (2.2):
(2.6) where p 0 is regularization parameter and the regularizer R is defined in (2.2). An obvious advantage of the regularization approach is it allows the user to fine-tune the trade-off between goodness-of-fit and faimess by adjusting p (see Figure 1; in Figure 3 of Appendix D we show the lack of such flexibility in the method of Yurochkin et al. (2020)). As we shall see, although the two approaches share many theoretical properties, we show in Section 4 that the regularization approach has superior empirical performance. We defer a more in-depth comparison between the two approaches to subsection 2.4.
mingeH L(h) + pR(h), L(h) & E[((Y,((X))]]
At first blush, the regularized risk minimization problem (2.6) is not amenable to stochastic opti- mization because R is not an expected value of function of the training examples. Fortunately, by appealing to duality, it is possible to obtain a dual formulation of R that is suitable for stochastic optimization.
Theorem 2.4 (dual form of R). (fd)((())) Adx(2, x') is continuous (in (x, x() for any 2 0, then
R(h) ine + Epx [ra(k, rx X) sudpeexdy -xd()))
3

---

Published as a conference paper at ICLR 2021
(a) = 0.1
(b) p=
(c) =
(d) p p=
Figure 1: The decision surface of a one hidden layer neural network trained with SenSel as the fair regularization parameter varies. In this ML task, points on a horizontal line (points with identical y-values) are similar, but the training data biased because Pyix is not constant on horizontal lines. We see that fair regularization (eventually) corrects the bias in the data.
We defer the proof of this result to Appendix A. In light of the dual form of the fair regularizer, the regularized risk minimization problem is equivalently
minseH infa2o Ep [e(Y, h(X)) p(Ae [))]]
(2.7)
where T is defined in Theorem 2.4, which has the form of minimizing an expected value of function of the training examples. To optimize with respect h, we parameterize the function space H with a parameter 0 E + C Rd and consider a stochastic approximation approach to finding the best parameter. Let to - (0 and Z (X,Y) Y). The stochastic optimization problem we wish to solve is
miD F(w) Ep [f,, Z)], f(w, Z) A hoY, + p(Ac + rx X)).
(2.8)
not hard to see that (2.8) stochastic optimization problem. We summarize Sensitive Set Invariance (SenSel) for stochastic optimization of (2.8) in Algorithm
Algorithm SenSel: Sensitive Set Invariance
inputs: starting point (0o. πo). step sizes (m)) repeat
(Xt, ...,...., (Xeg Vig) P
sample mini-batch from
Tt1, + arg m Ex (dy (X1.), Ng, (x¹)) - Nxdx(Xx, 2'),. [B]
t generate
worst-case examples
det1 + max(0, 7τ ppp(- B Σm dx(X 1/,)).
0(+1 +- 0, - - Eb (g h (X1,)) pàla (dy (Xw), (x,,))
until converged
2.4 ADVERSARIAL TRAINING FAIR REGULARIZATION
Adversarial training is popular approach to training invariant ML models. It was originally developed defend ML models against adversarial examples (Goodfellow al., 2014: Madry al., 2017). There are many versions of adversarial training; the Wasserstein distributionally robust optimization (DRO) version by Sinha et al. (2017) is most closely related to (2.5). The direct goal of adversarial training is training ML models whose risk is small on adversarial examples, and the robust risk that adversarial training seeks to minimize (2.5) is exactly the risk on adversarial examples.
An indirect consequence of adversarial training is invariance to imperceptible changes to the inputs. Recall an adversarial example is training example with the same label as non-adversarial training example whose inputs differ imperceptibly from those of training example. Thus (successful) adversarial training leads to ML models that ignore such imperceptible changes and are thus invariant in "imperceptible neighborhoods" of the training examples.
Unlike adversarial training, which leads to invariance as an indirect consequence of adversarial robustness, fair regularization enforces faimess by explicitly minimizing fair regularizer. A key benefit of invariance regularization it permits practitioners fine-tune the trade-off between goodness-offfi -ffttt and invariance by adjusting the regularization parameter (see Figure 1).
4

---

Published as a conference paper at ICLR 2021
2.5
RELATED WORK
There are three lines of work on enforcing individual fairness. There is line of work that enforces group fairness with respect to many (possibly overlapping) groups avoid disparate treatment of individuals (Hébert-Johnsel et al., 2017; Kearns et al., 2017; Kim et al., 201 8a;b). At a high-level, these methods repeatedly find groups in which group fairness is violated and updates the ML model to correct violations. Compared to these methods that approximate individual fairness with group fairness, we directly enforce individual fairness.
There is another line of work on enforcing individual fairness without knowledge of the similarity metric. Gillen al. (2018); Rothblum & Yona (2018); Jung et al. (2019) reduce the problem of enforcing individual fairness to supervised learning problem by minimizing the number of violations. Instead of a similarity metric, these algorithms rely on an oracle that detects violations of individual fairness. Garg et al. (2018) enforce individual fairness by penalizing the expected difference in predictions between counterfactual inputs. Instead of a similarity metric, this algorithm relies a way of generating counterfactual imputs. Our approach complements these methods by relying similarity metric instead of such oracles. This allows us to take advantage of recent work on learning fair metrics (IIvento, 2019; Wang et al., 2019; Yurochkin al., 2020; Mukherjee et al., 2020).
Most similar to our work is SenSR (Yurochkin et al., 2020) that also assumes access to a similarity metric. SenSR is based adversarial training, i.e. it enforces risk-based notion of individual fairnsss that only requires the risk of the MI. model to be similar on similar inputs. In contrast, our method is based on fair regularization, i.c. it enforces notion of individual fairness that requires the outputs of the ML model to be similar. The latter is stronger (it implies the former) and is much closer to Dwork et al.'s 's original definition. In addition, the risk-based notion of SenSR ties accuracy to fairness. Our approach separates these two (usually conflicting) goals and allows practitioners to more easily adjust the trade-off between accuracy and fairness as demonstrated in our experimental studies.
Finally, there is a line of work that proposes pre-processing techniques to learn a fair representation of the individuals and training an MI model that accepts the fair representation as input (Zemel et al., 2013; Bower et al., 2018; Madras et al., 2018; Lahoti et al., 2019). These works are complimentary to ours propose an in-processing algorithm.
3 THEORETICAL PROPERTIES OF SENSEI
In this section, we describe some thcoretical properties of SenSel. We defer all proofss to Appendix A. First, Algorithm 1 is an instance of a stochastic gradient method, and its convergence properties well-studied. Even if f (w; Z) is non-convex in w, the algorithm converges (globally) to a stationary point (see Appendix for rigorous statement). Second, the fair regularizer is data-dependent, and it is unclear whether minimizing its empirical counterpart (3. enforces distributional fairness. We show that the fair regularizer generalizes under standard conditions. Consequently,
1. is possible for practitioners to certify that an ML model h is DIF a posteriori by checking R(h) (even if h was trained by minimizing Ri;
2. fair regularization enforces distributional individual fairesss (as long as the hypothesis class includes DIF ML models);
Notation Let {(,,, Y.) be the training set and Px be the empirical distribution of the inputs. Define L: H + R as the empirical risk and R H + R as the empirical counterpart of the fair regularizer (2.2):
maxπιa((xx))
En (xx)
R((h) A
subject to
En (X, Se
(3.1)
IT(-2)) Px:
Define the loss class and its counterpart for the fair regularizer as
L A (ln Z + R E H}, (x(2) & ((h()).))
D 2 (dn X x X + R+ h E H}, da(zx²)) e dy(h(x), n(22)).
5

---

Published as a conference paper at ICLR 2021
We measure the complexity of D and C with their entropy integrals with respect to the uniform metric: [(D/C) - Jo log [( <)) where N(D, Il Il is the e-covering number of D in the uniform metric. The main benefit of using entropy integrals instead of Rademacher or Gaussian complexities to measure the complexity of D and is does not depend on the distribution of the training examples. This allows us to obtain generalization error bounds for counterfactual training sets that are similar the (observed) training set. Finally, define the diameter of X' in the dx metric, that of y in the dy metric Dx - ''xx,='Ex dx(xx, x'), Dy - first result shows that the fair regularizer R(h) generalizes. We assume Dx, Doy < cc. This is boundedness condition on X' x V/ and it is a common simplifying assumption in statistical learning theory. We also assume JDD < oc. This is a standard assumption that appears many uniform convergence results.
dy y²). The
Theorem 3.1. As long as Dx. Dy, and J(G) are all finite, with probability at least 1 t:
SUPдEи R(hh) R(h) I 18(J(D)+ ( Dy) + -Dy(
log
vn
2m
Theorem 3.1 implies is possible to certify that an ML model h satisfies distributional individual fairness (modulo error terms that vanish in the large-sample limit) by inspecting R(h)) This is important because a practitioner may inspect R(h) after training to verify whether the trained ML model h is fair enough. Theorem 3.1 assures the user that R(h)) is close to R(h).
4 COMPUTATIONAL EXPERIMENTS
In this section we present empirical evidence that SenSel trains individually fair ML models in practice and study the trade-off between accuracy and fairness parametrized by p (defined in (2.6)).
Baselines We compare SenSel to empirical risk minimization (Baseline) and two recent approaches for training individually fair ML models: Sensitive Subspace Robustness (SenSR) (Yurochkin et al., 2020) that uses DRO to achieve robustness to perturbations a fair metric, and Counterfactual Logit Pairing (CLP) (Garg et al., 2018) that penalizes the differences in the output of an MI model on training examples and hand-crafted counterfactuals. We provide implementation details of SenSeI and the baselines in Appendix B.
4.1 TOXIC COMMENT DETECTION
We consider the task of training classifier to identify toxic comments, i.e. rude or disrespectful messages in online conversations. Identifying and moderating toxic comments is crucial for facili- tating inclusive online conversations. Data available through the "Toxie Comment Classification Challenge" Kaggle competition. We utilize the subset of the dataset that is labeled with range of identity contexts (e.g. "muslim", "white", "black", "homosexual gay or lesbian") Many of the toxic comments in the train data also relate to these identities leading classifier with poor test performance on the sets of comments with some of the identity contexts (group fairness violation) and prediction rule utilizing words such as "gay" to flag a comment as toxic (individual fairness violation). To obtain good features we use last layer representation of BERT (base, uncased) (Devlin al., 2018) fine tuned on separate subset of 500k randomly selected comments without identity labels. We then train 2000 hidden units neural network with these BERT features.
Counterfactuals and fair metric. CLP (Garg et al., 2018) requires defining set of counterfactual tokens. The training proceeds by taking an input comment and if it contains counterfactual token replacing it with another random counterfactual token. For example, if "gay" and "straight" are among the counterfactual tokens, comment "Some people are gay" may be modified to "Some people are straight". Then difference in logit outputs of the classifier on the original and modified comments used as regularizer. For toxicity classification Garg et al. (2018) adopted set of 50 counterfactual tokens from (Dixon et al., 2018). Counterfactuals allow for a simple fair metric learning procedure via factor analysis: since any variation in representation of data point and its counterfactuals is considered undesired, Yurochkin et al. (2020); Mukherjee et al. (2020) proposed to use a Mahalanobis metric with the major directions of variation among counterfactuals projected out. We utilize this

---

Published as a conference paper at ICLR 2021
Table 1: Summary of Toxicity classification experiment over 10 restarts
BA
CTF score
PC
BA STD
ACC STD
Baseline
0.80710.002
0.072=00002
0.621=00014
0.044=0.003
0.081=0.004
SenSel 0.791=0.005
0.029=0.005
0.773
0.035=0.003
0.052-10.003
SenSR
0.794=10.003
0.043=00005
0.036=0.002 0.763:+0.048
0.729=10004
0.059=10.004
CLP
0.795=00.006
0.032=00006
0.038=0.003
0.056=000004
Table 2: Summary of Bios classification experiment over 10 restarts
BA
CTF score
PC
Gap RMS
Gap ABS
Baseline
0.842:1:0002
0.028=00.001
0.942:40.001
0.120=0.00
0.080=10.003
SenSel
0.843
0.003=0.000
0.977=10001
0.086=0.005
0.05410.003
SenSR
0.842:1:.003 0.004
0.976=10.001
0.087=0.004
0.054-10.003
CLP
0.841=000003
0.005=0.000
0.974
0.087=0.005
0.056=10.004
approach here to obtain fair metric for training SenSR (Yurochkin et al., 2020) and SenSel. See Appendix B.1 for additional details regarding the fair metric construction in the experiments.
Comparison metrics. To evaluate individual fairness of the classifiers we use test data and 50 counterfactuals to check if the classifier toxicity decision varies across counterfactuals. For example, is prediction for "Some people are gay" same as for "Some people are straight"? An intuitive fair metric should be 0 on a pair of such comments and prediction of the classifier should not change based on the Dwork et al. 's individual fairness definition. We report Counterfactual Token Fairness (CTF) score (Garg et al., 2018) that quantifies variance across counterfactuals of the predicted probability that comment is toxic, and Prediction Consistency (PC) equal to the portion of test comments where prediction is the same across all 50 counterfactual variations.
For goodness-of-fit fit we use balanced accuracy due to class imbalance. To quantify group fairness we follow accuracy parity notion (Zafar et al., 2017; Zhao et al., 2019). Here protected groups correspond to the identity context labels available in the data and accuracy parity quantifies whether classifier is equally accurate on, c.g., comments labeled to have "white" context and those labeled with "black". There are 9 protected groups and report standard deviation of the accuracies and balanced accuracies across them. We present mathematical expressions for each of the metrics in Appendix C for completeness.
Results. We repeat our experiment 10 times with random 70-30 train-test splits, every time utilizing random subset of 25 counterfactuals during training. Results are summarized in Table 1. SenSel on average outperforms other fair training methods on all individual and group fairness metrics at the cost of slightly lower balanced accuracy. SenSR has the lowest prediction consistency score suggesting that our fair regularization is more effective in enforcing individual fairness than adversarial training. This observation aligns with the empirical study by Yang al. (2019) comparing various invariance enforcing techniques for spatial robustness in image recognition.
SenSel also outperforms CLP: our approach uses optimization to find worst case perturbations the data according to fair metric induced by counterfactuals, while CLP chooses a random perturbation among the counterfactuals. SenSel searching for perturbation on every data point that potentially allows to generalize to unseen counterfactuals, while CLP only perturb comments that explicitly contain a counterfactual known during training time. In Figure 2 we verify that both SenSeI and CLP allow "trade" fairness and accuracy by varying the regularization strength p (in the table we used = 5 for both). We also notice the effect of worst case optimization opposed to random sampling: SenSel has higher prediction consistency the cost of balanced accuracy.
4.2 OCCUPATION PREDICTION
Online professional presence via dedicated services or personal websites is the common practice in many industries. ML systems can be trained using data from these sources to identify person's 's occupation and used by recruiters to assist in finding suitable candidates for the job openings. Gender imbalances in occupations may trigger biases such ML systems exacerbating societal incquality. De-Arteaga et al. (2019) proposed Bias in Bios dataset to study fairness in occupation prediction from
7

---

Published as a conference paper at ICLR 2021
Predict cogeistess
0.910
SenSel
0.66
pedrdion omagke
Dast
0:75
gase
galonces
0.70
SenSel
Sen
Sen
CLP
6.766
0.000
CLP
CLP
0834
Regularization strength p
Regulariziiin strength
Regillatzationn strength
Regularizatinn Strengtt
(a) Toxicity PC
(b) Toxicity BA
(c) Bios PC
(d) Bios BA
Figure 2: Balanced accuracy (BA) and prediction consistency (PC) trade-off.
Table 3: Adult experiment over 10 restarts. Prior methods are duplicated from Yurochkin al. (2020)
BA, %
S-Con.
GR-Con.
Gap
RMS
Gap
RMS
Gap
Gap max
SenSR
78.9
994
.94
.068
.055
.087
.067
Baseline
82.9
.888
.865
.179
.089
.216
.105
Project
82.7
.688
1.00
.145
.064
.192
.086
Adv. debiasing
81.5
.807
.841
.082
.070
.110
.078
CoCL
79.0
.163
.080
.201
.109
SenSel (p- 40)
76.8
.945
.963
.043
.054
.053
.064
a person's bio. The dataset consists of 400k textual bio descriptions and the goal is to predict one of the 28 occupations. We again BERT fine-tuned the train data obtain bio representations and then train a 2000 hidden neurons neural networks using each of the fair training methods.
Counterfactuals and fair metric. Counterfactuals definition for this problem is the gender analog of the Bertrand & Mullainathan (2004) investigation of the racial bias in the labor market. For each bio we create counterfactual bio by replacing male pronouns with the corresponding female ones and vice a versa. For the fair metric we use same approach as in the Toxicity study.
Comparison metrics. We use the same individual fairness metrics. To compare group fairness we report root mean squared gap (Gap RMS) and mean absolute gap (Gap ABS) between male and female true positive rates for each of the occupations following prior studies of this dataset (Romanov et al., 2019; Prost et al., 2019). For performance we report balanced accuracy due to imbalance in occupation proportions in the data.
Results. We the experiment 10 times with 70-30 train-test splits and summarize results in Table 2 (for SenSel and CLP we set p = 5). Comparing to the Toxicity experiment, we note that individual fairness metrics are much better. In particular, attaining prediction consistency is easier because there only one type of counterfactuals. Overall, fairness metrics are comparable across fair training methods with slight SenSel advantage. It is interesting to note mild accuracy improvement: learning a classifier invariant to gender can help to avoid spurious correlations between occupations and gender present in the data. We present fairness accuracy "trade-off" in Figure increasing regularization strength has clear upward trend in terms of the prediction consistency without decreasing accuracy. This experiments an example where fairness can be improved without "trading" performance.
We note two prior group fairness studies of the Bios dataset: Romanov et al. (2019) and Prost al. (2019). Both reported worse classification results and fairness metrics. Better classification performance in our work is likely attributed to using BERT for obtaining bios feature vectors. For the group fairness, we note that relative baseline improvement with SenSel is more significant.
4.3 INCOME PREDICTION
The Adult dataset (Bache & Lichman, 2013) is a common benchmark in the group fairness literature. The task is to predict if person carns more than $50k per year using information about their education, gender, race, marital status, hours worked per week, etc. Yurochkin et al. (2020) studied Adult by considering prediction consistency with respect to demographic features: race and gender (GR-Con.) and marital status (S-Con,, i.e spouse consistency). To quantify group fairness they used RMS gaps and maximum gaps between true positive rates across genders (Gap RMS and max and races (Gap
individual faimess
RMS and Gap max). Due to class imbalance, performance is
8

---

Published as a conference paper at ICLR 2021
quantified with balanced accuracy (B-Acc). For the fair metric they used Mahalanobis distance with race, gender and a logistic regression vector predicting gender projected out. We note that CLP was proposed fair training method for text classification (Garg et al., 2018) and is not applicable on Adult because it is not clear how to define counterfactuals. We compare SenSel to results reported in Yurochkin al. (2020). In Table 3 we show that with sufficiently large regularization strength 40 SenSel is able to further reduce all group faimess gaps and improve one of the individual fairness metries, however trading off some accuracy.
SUMMARY AND DISCUSSION
In this paper, we studied regularization approach enforeing individual fairness. We defined distributional individual fairness, a variant of Dwork et al,'s original definition of individual fairness and a deteddentedd regularizer that enforces this distributional fairness (see Definition 2.1). We also developed stochastic approximation algorithm to solve regularized empirical risk minimization problems and showed that trains MI. models with distributional fairness guarantees. Finally, we showed that the algorithm mitigates algorithmic bias on three MI. tasks that are susceptible to such biases: income-level classification, occupation prediction, and toxic comment detection.
ACKNOWLEDGEMENTS
This paper is based upon work supported by the National Science Foundation (NSF) under grants no. 1830247 and 1916271. Any opinions, findings, and conclusions or recommendations expressed in this paper are those of the authors and do not necessarily reflect the views the NSF.
REFERENCES
K. Bache and M. Lichman. UCI machine learning repository. 2013.
Marianne Bertrand and Esther Duflo. Field Experiments on Discrimination. Technical Report w22014, National Bureau of Economic Research, Cambridge, MA, February 2016.
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-1013, September 2004. ISSN 0002-8282. doi: 10. (0.1257/00292344202566.1
Jose Blanchet and Karthyek R. Murthy. Quantifying Distributional Model Risk via Optimal Transport. arXiv:1604.00 0144..4604. [math, stat], April 2016.
Amanda Bower, Laura Niss, Yuekai Sun, and Alexander Vargo. Debiasing representations by removing unwanted variation due to protected attributes. 1 [cs], July 2018.
Maria De-Arteaga, Alexey Romanov, Hanna Wallach, Jennifer Chayes, Christian Borgs, Alexandra Chouldechova, Sahin Geyik, Krishnaram Kenthapadi, and Adam Tauman Kalai. Bias in Bios: A Case Study of Semantic Representation Bias in a High-Stakes Setting. Proceedings of the Conference on Fairness, Accountability, and Transparency. FAT* '19, pp. 128,128, 2019. doi: 10.1 00.114//288560032885555
Jacob Devlin, Ming- Wei Chang, Kenton Lee, and Kristina Toutanova. BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding. arXiv:1810.04805 [cs], October 2018.
Lucas Dixon, John Li, Jeffrey Sorensen, Nithum Thain, and Lucy Vasserman. Measuring and Mitigat- ing Unintended Bias in Text Classification. In Proceedings of the 2018 AAAI/ACM Conference on AI, Ethics, and Society AIES 18, pp. 67-73, New Orleans, LA, USA, 2018. ACM Press. ISBN 978-1-4503-6012-8 doi: 10. 10.1145/3278721.327887
Cynthia Dwork, Moritz Hardt, Toniann Pitassi, Omer Reingold, and Rich Zemel. Fairness Through Awareness. 1r04v:1104.399 [cs], April 2011.
Sahaj Garg, Vincent Perot, Nicole Limtiaco, Ankur Taly, Ed H. Chi, and Alex Beutel. Counterfactual Fairness in Text Classification through Robustness. arXiv: /809. 106/0 (cs, stat], September 2018.

---

Published as a conference paper at ICLR 2021
Saeed Ghadimi and Guanghui Lan. Stochastic First- and Zeroth-order Methods for Nonconvex Stochastic Programming. arXiv:1309.5544 [cs, math, stat], September 2013.
Stephen Gillen, Christopher Jung, Michael Kearns, and Aaron Roth. Online Learning with an Unknown Fairness Metrie. arXiv: 06336660066666 [es), February 2018.
lan J. Goodfellow, Jonathon Shlens, and Christian Szegedy. Explaining and Harnessing Adversarial Examples. December 2014.
Ürsula Héhert-Johnson, Michael P. Kim, Omer Reingold, and Guy N. Rothblum, Calibration for the (Compuaiionaly-lleniiiaaaa Masses. arXiv: 1.08513 [cs, stat], November 2017.
Christina Ilvento. Metric Learning for Individual Fairness. arXiv:1906.00230 [cs, staf], June 2019.
Christopher Jung, Michael Kearns, Seth Neel, Aaron Roth, Logan Stapleton, and Zhiwei Steven Wu. Eliciting and Enforcing Subjective Individual Fairness. arXiv: 10660 [es, stat], May 2019.
Harini Kamnan, Alexey Kurakin, and lan Goodfellow. Adversarial Logit Pairing. arXiv:/803.0637) [cs, stat), March 2018 8.
Michael Kearns, Seth Neel, Aaron Roth, and Zhiwei Steven Wu. Preventing Fairness Gerrymandering: Auditing and Learning for Subgroup Fairness. 17Xiv:1711.05144 [cs], November 2017.
Michael P. Kim, Amirata Ghorbani, and James Zou. Multiaccuracy: Black-Box Post-Processing for Fairness in Classification.
[cs, stat], May 2018a.
Michael P. Kim, Omer Reingold, and Guy N. Rothblum. Fairness Through Computationally-Boundde Bounded Awareness. 0r03vv/803.0322. [cs]. March 2018b.
Preethi Lahoti, Krishna P. Gummadi, and Gerhard Weikum. iFair: Learning Individually Fair Data Representations for Algorithmic Decision Making. 1806.00000010555 [cs, star), February 2019.
Jaeho Lee and Maxim Raginsky. Minimax Statistical Learning with Wasserstein Distances. arXiv:1705.07815 [cs], May 2017.
David Luenberger. OPTIMIZATION BY VECTOR SPACE METHODS. John Wiley & Sons, 1968.
David Madras, Elliot Creager, Toniann Pitassi, and Richard Zemel. Learning Adversarially Fair and Transferable Representations. arXiv:1802.06309 [cs, stat], February 2018.
Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. Towards Deep Learning Models Resistant to Adversarial Attacks. arXiv: 176600700 [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.
Debarghya Mukherjee, Mikhail Yurochkin, Moulinath Banerjee, and Yuekai Sun. Two simple ways to learn individual fairness metrics from data. In International Conference on Machine Learning, July 2020.
Flavien Prost, Nithum Thain, and Tolga Bolukbasi. Debiasing Embeddings for Reduced Gender Bias in Text Classification. arXiv:1908.02880 [cs, stat), August 2019.
R. Tyrrell Rockafellar and Roger J.-B. Wets. Variational Analysis. Number 317 in Grundlehren Der Mathematischen Wissenschaften. Springer, Berlin, corr. 2nd print edition, 2004. ISBN 978-3-540-66777222
Alexey Romanov, Maria De-Arteaga, Hanna Wallach, Jennifer Chayes, Christian Borgs, Alexan- dra Chouldechova, Sahin Geyik, Krishnaram Kenthapadi, Anna Rumshisky, and Adam Tau- man Kalai. What's in a Name? Reducing Bias in Bios without Access Protected Attributes. 1rXiv:1904.05233 {es, stat), April 2019.
Guy N. Rothblum and Gal Yona. Probably Approximately Metric-Fair Learning. arXiv:1803.02241 fes), March 2018.
10

---

Published as a conference paper at ICLR 2021
Aman Sinha, Hongseok Namkoong, and John Duchi. Certifying Some Distributional Robustness with Principled Adversarial Training. arXiv:1710.1057) [cs, stat], October 2017.
Hanchen Wang, Nina Grgic-Hlaca, Preethi Lahoti, Krishna P. Gummadi, and Adrian Weller, An Empirical Study Learning Fairness Metrics for COMPAS Data with Human Supervision. arXiv:1910. 10255 [cs], October 2019.
Fanny Yang, Zuowen Wang, and Christina Heinze-Deml. Invariance-inducing regularization using worst-case transformations suffices boost accuracy and spatial robustness. arXiv: /906. 1235 [cs, stat], June 2019.
Mikhail Yurochkin, Amanda Bower, and Yuekai Sun. Training individually fair ML models with sensitive subspace robustness. In International Conference on Learning Representations, Addis Ababa, Ethiopia, 2020.
Muhammad Bilal Zafar, Isabel Valera, Manuel Gomez Rodriguez, and Krishna Gummadi. Fairness Beyond Disparate Treatment & Disparate Impact: Learning Classification without Disparate Mistreatment. Proceedings of the 26th International Conference on World Wide Web WWW '17,
1171-1180, 2017. doi: 10.1 00.11453303812.3055660
Rich Zemel, Yu Wu, Kevin Swersky, Toni Pitassi, and Cynthia Dwork. Learning Fair Representations. In International Conference on Machine Learning, pp. 325-333, February 2013.
Han Zhao, Amanda Coston, Tameem Adel, and Geoffrey J. Gordon. Conditional Learning of Fair Representations. In International Conference Learning Representations, September 2019.

---

Published as a conference paper at ICLR 2021
A THEORETICAL PROPERTIES
We collect the proofs of all the theoretical results in the paper here. We restate the results before proving them for the reader's convenience. We assume that (x, and ()), dy) are complete and separable metric spaces (Polish spaces).
A.1 DIF AND INDIVIDUAL FAIRNESS
Proposition A.1 (Proposition 2.3). If x (c,8)-DIR, then
Px (s h(r) h(x')) 2 r) 1
Proof. Recall
Tip _ arg (x(,x")) dy (1(x)) h(x))(x))))))))))))))))) ))
feasible for (the Mongé version of) (2.2). Thus R(h) 6 implies Epx [dy Tix(X))] s Markov's inequality implies (x (i)())) 2 7) < for any T > O.
A.2 CONVERGENCE PROPERTIES OF SENSEI
Algorithm is instance of stochastic gradient method, and its convergence properties well- studied. Even if f(w, Z) is non-convex in w, the algorithm converges (globally) to a stationary point. This well-knows result stochastic approximation, and we state it here for completeness. Theorem A.2 (Ghadimi Lan (2013)). Let
2 2 E + O Iw. Z,) - OF
be an upper bound of the variance of the stochastic gradient. As long as L-strongly smooth, F(w') I F(w) (0F(w), w/ - -w) + _ || w'1
for any w, w' E x R4, then Algorithm with constant step sizes tp Lo T E[ where ty is any upper bound of the suboptimality of ww-
2Bc
)
satisfies
8Leg BT
In other words, Algorithm finds an e-stationary point of (2.8) in at most ((+) iterations. If F has more structure (e.g. convexity), then Algorithm may converge faster.
A.3 PROOF OF DUALITY RESULTS IN SECTION
Theorem A.3 (Theorem 2.4), If dy(((()),M(z')) Ad (x, x²) is continuous (in (I,x')) for any 0, then
R(h) = inf Epx (x, }. Adx (X,((xx))}
(h, X) A sup (h(x),,
Proof. We abuse notation and denote the function dy (xx),, h(z))) dy h. We recognize the optimization problem in (2.2) as an (infinite dimensional) linear optimization problem:
suPma(Xxxx)
(II, dy h) En (d)()(),,
R(h) A
subject to
(II, dx) = Em [dx Se
II:: = Px,
is not hard check Slater's condition: dil(xxx') = 1(x = x' cd)(P)) is strictly feasible. Thus we have strong duality (see Theorem 8.7.1 in (Luenberger, 1968)):
R(h) supp.n(,xx)=>> in dy o h) + X(E - (11,xx)) suPm. inf A20 de + (II, dy h Xdx)
saw x (1I, -
Adx)h
remains to show
suPpan,,)==p(d h Adx, IT) Ep sup (x)
Adx(X,,'))]- (A.1)
12

---

Published as a conference paper at ICLR 2021
I direction The integrands in (A.1) satisfy (z)ph-)d))(< (h((t))hha))) (dx(xx, S supzex h(()) xdx((x, so the integrals satisfy the V version of (A.1).
2 direction Let Q be the set of all Markov kernels from X to X. We have
x) Adx, II) suPQEe S xxX
dy(b(x)),(x')) - Xdx(e,=")dQ(( 1x)dP(s)
suprxx-x / (
where we recalled Q(A a) = 1(T(x) E A] is Markov kernel in the second step. (Technically, in the second step, we only sup over 7 that are decomposable (see Definition 14.59 in Rockafellar Wets (2004)) with respect to P, but we gloss over this detail here.) We appeal to the technology of integrands (Rockafellar Wets, 2004) to interchange integration and maximization. We assumed dy o h ->dxx is continuous, so it is normal integrand (see Corollary 14.34 in Rockafellar & Wets (2004)). Thus it is OK to interchange integration and maximization (see Theorem 14.60 in Rockafellar & Wets (2004)):
/ dy(h(z), -Ad (2, T()))P((a) = supwex (x)
SUPT-X-XX
This shows the 2 direction (A.1).
We remark that not necessary to rely on the technology of normal integrands to interchange expectation and maximization in the proof of Theorem 2.4. For example, Blanchet & Murthy (2016) prove a similar strong duality result without resorting to normal integrands. We so here to simplify the proof.
A.4 PROOFS GENERALIZATION RESULTS SECTION 3
Theorem A.4 (Theorem 3.1), As long as Dx, Dy. J(G) are all finite,
suP Ep[f(Z)] [f[](Z)]] 48(J(D)+ (
log f
Dy
Vn
with probability at least 1- t.
Proof. Let
En (d())(()) En (X, Se II(,,)) Px,
max]ia((XXR)
R(h) &
subject to
where Px is the empirical distribution of the inputs in the training By Theorem 2.4, we have
R(h) R(h)= infxzofAe EER, (x, x)] - inf A h Epx (h, X)]} -inf EEpy [rx(h, x)]} - A.E Epy (h, S EE [Tx, x)]} Epx [rx. (h, X)],
(A.2)
where X, arg mig Epx [rx (h, X)]. The infimum is attained because
infazo de + Epx (4),
an strictly feasible (infinite-dimennionaa)) linear optimization problem (see proof of Theorem 2.4). To bound X, observe that r. (h,, X) > for any h H, ' 0:
rx (h, X) (up))
Adx (X,x'))
2 (o(h(X),n(x)) - (X)
13

---

Published as a conference paper at ICLR 2021
This implies
R(h) X + Epx [rx. (h, X)] 2 due.
We rearrange obtain a bound on A,:
X, - R(h) S Dy Dy =
(A.3)
This is admittedly a crude bound, but it is good enough here. Similarly,
R(h) R(h)= = Epx [rx. (h, x)]} Ep, [rx, X)], where 2r arg mingmnnsse A2 d + Epy (h, (h, x)]. and X S A. Combining (A.2) and (A.4), we obtain
(A.4)
(R(h)-R(H) - S SU [p[ Ep [p[s(Z)]
where F (rx h H. A13. It possible bound ye [E{[[(2] - Ex with results from statistical learning theory. First, we observe that the functions in F are bounded:
1 6
ra X) sup dy(y.8').
Thus su EE [[2)
- Ep [[() has bounded differences inequality, so it concentrates sharply around its expectation. By the counded-differences inequality and standard symmetrization argu- ment,
log 2n
sup Ep [[(2]] - Ep [[[)][]]]]] S 29R,, + Dy
)
with probability at least - f, where (F) is the Rademacher complexity of F::
(J) E [[supJEF 1. Ei= (Z,)
remains to study R, (F). First, we show that the F-indexed Rademacher process X3 A Eim (Z,) is aub-Gaussian with respect to to the metric
d, ((h1 A1), A2) A
E ex - X x2))
E E[exp( L Ei (rx, (h1, X,) rxo (12, X,)))]
o (h1, Xi) - (22 x;)))
[( (sup,, ex inf (X),, hz(()) -1dx -xoxx))ddd(((hhl dy(ha(X,),, h2(zz)) + xX,
E ( o ex (x) (b))) + (A2 (r)x
I (h1,
Let N(F, be the e-covering number F in the df metric. We observe N(F,dr,c) S [(D, 1l 5) N(O, A1,1 -..... 2
(A.5)
By Dudley's 's entropy integral,
12
RR,
log dr, |( e)
Vn
12
(log N(D, || +1) A1.1 ... 26x
fn
12
log NDD, || lloc, 5) 10 (110, 2/xxxx1 à de
2DJ(D)
+ xADxÀ A
/ log(t)de.
Vn
Vn
We check that 1 log( < arrive at Theorem 3.1.
14

---

Published as a conference paper at ICLR 2021
The chief technical novelty of this proof is the bound on X, in terms of the diameter of the output space. This bound allows us to restrict the relevant function class in a way that allows us to appeal to standard techniques from empirical process theory obtain uniform convergence results. In prior work (e.g. Lee & Raginsky (2017)), this bound relies on smoothness properties of the loss, but this precludes non-smooth dy in our problem setting.
Corollary A.5. Assume there is ho E H such that I(hho) + < ôg- As long Dx, Dy, J(C) and ( are all finite, any global minimizer 1 E arg min [(h) + pP((h) satisfies
L(h) + pR(h) S 60 + 24J(CC + (8)(J(D) + + with probability at least 2f.
log
(T. pDy)
2
vn
2n
Proof. Let F(h) A L(h) + pl(hh) and F be its empirical counterpart. The optimality of h implies
F(h) F()) 1 (h)) (h) F(ho) + F(ha) (ho) - 6u + 2 (F(h) - F(h)].
We have
SuPдcи (P(h) F(h) suPлEи (T(hh) I(h)] P sup [R(h) R(b)]- kEH
(A.6)
We assumed & is bounded, so SuPREи [b(h) L(h)l has bounded differences inequality, so concentrates sharply around its expectation. By the bounded-differences inequality and standard symmetrization argument,
log 2 2n
SUPBCи (Z(h) T.(h)] 22), T
with probability at least 1-t, where (C) is the Rademacher complexity of L. By Dudley's entropy integral,
12
/ log N (1,,, c)
(C) S
Vn
so the first term on the right side of (A.6) is at most
24J(C)
log
2 7
suPдEи (Σ(h) L(h))
L(
Vn
2n
with probability at least most
Theorem 3.1 implies second term on the right side of (A.6) is at
48(J(D) ( D> + Dy((
log
SUPNEH RR(h) R(A) <
Vn
2n
with probability at least J. We combine the bounds arrive the stated result.
B SENSEI AND BASELINES IMPLEMENTATION DETAILS
In this section we describe implementation details of all methods and hyperparameter selection to facilitate reproducibility of the experimental results reported in the main text.
Improving balanced accuracy All three datasets we consider have noticeable class imbalances: over 80% comments in toxicity classification are non-toxic; several occupations in the Bias in Bios dataset are scarcely present (see Figure in De-Arteaga al. (2019) for details); about 75% of individuals in the Adult dataset make below $50k year. Because of this class imbalance we choose to report balanced accuracy to quantify classification performance of different methods. Balanced accuracy is simply
average of true positive rates of all classes. To improve balanced accuracy for all methods we use balanced mini-batchee batches following Yurochkin et al. (2020), i.c. when sampling a mini-batch we enforce that every class is equally represented.
15

---

Published as a conference paper at ICLR 2021
Fair regularizer distance metric Recall that fair regularizer in Definition 2.1 of the main text requires selecting a distance metric on the classifier outputs dy (h(x),, h(x")) This distance is also required for the implementation of Counterfactual Logit Pairing (CLP) (Garg et al., 2018). In K-class problem, let ((x) E R denote a vector of K logits of a classifier for an observation a, then for both SenSel and CLP we define dy (h(a;, h(x²)) K [|h(())) h(=')1l?
Il3. i.e. mean squared difference between logits of z and x'. This is one of the choices empirically studied by Yang et al. (2019) for image classification. We defer exploring alternative fairesss regularizer distance metrics for future work.
Data processing and classifier architecture Data processing and classifier are shared across all methods in all experiments. In Toxicity experiment we utilized BERT (Devlin et al.. 2018) fine- tuned on a random 33% subset of the data. We downloaded the fine-tuned model from one of the Kaggle kernels." In the Bios experiment for each train-test split fine-tuned BERT-Base, Uncased for 3 epochs with mini-batch size 32, learning rate 2e-5 and 128 maximum sequence length. In both Toxicity and Bios experiments we obtained 768-dimensional sentence representations by average-pooling token embeddings of the corresponding fined-tuned BERTs. Then we trained fully connected neural network with one hidden layer consisting of 2000 neurons with ReLU activations using BERT sentence representations as inputs.
For Adult experiment we followed data processing and classifier choice (i.e. 100 hidden units neural network) as described in Yurochkin et al. (2020).
Hyperparameters selection In Table 4 for each hyperparameter we summarize its meaning, ab- breviation, name in the code provided with the submission' and methods where is used.
To select hyperparameters for each experiment we performed grid search on an independent train-test split. Then we fixed selected hyperparameters and ran 10 experiment repetitions with random train test splits (these results are reported in the main text). Hyperparameter choices for all experiments summarized in Tables 5, 7. For the Adult experiment duplicated results for all prior methods from Yurochkin et al. (2020).
Table 4: Hyperparameter names and notations
notation
name in code
relevant methods
Number of optimization steps
E
epoch batch_size Ir adv step adv_ eed_eepoch 12 22_attack adv five__poch_ulll TO fair_reg
All
Mini-batch size
B
All
Parameter learning rate y Subspace attack step size
!]
All
SenSel, SenSR
Number of subspace attack steps
se
SenSel, SenSR
Full attack step size
SenSel, SenSR
Number of full attack steps Attack budget e Fair regularization strength p
fe
SenSel, SenSR
SenSel, SenSR
SenSel, CLP
Table 5: Hyperparameter choices in Toxicity experiment
E
B
?
S
se
f
fe
P
Baseline
100k
256
le-5
SenSR
100k
256
le-5
0.1
10
0
0
0
SenSel
100k
256
le-5
0.1
10
0
0
5
CLP
100k
256
le-5
5
'tttps: wwww. kaggle. com/ / www.innwwwwbrreeeeeeeeeee
Phttp:://ithub.com wwt..ccc/ooooeeeeeeeeeheeeeeeeee We will open-source the code and merge variable names with their abbreviations
16

---

Published as a conference paper at ICLR 2021
Table 6: Hyperparameter choices in Bios experiment
E
B
1
se
fe
Baseline
100k
504
1e-6
SenSR
100k
504
le-5
0.1
50
0.01
10
0.1
SenSel
100k
504
1e-5
0.1
50
0.01
10
0.1
CLP
100k
504
le-5
Table 7: Hyperparameter choices in Adult experiment
B
1]
86
f
fe
P
SenSel
200k
1000
le-5
5
50
0.001
50
0.01
40
B.1 FAIR METRIC LEARNING DETAILS
Following Yurochkin et al. (2020); Mukherjee et al. (2020) we consider the fair metric of the form dx dx(xxx - x')²
E(x x²). We utilize their sensitive subspace idea writing - Pran(A))
i.e. an orthogonal complement projector of the subspace spanned by the columns of A E Rdxk Here A encodes the & directions of sensitive variations that should be ignored by the fair metric (d is the data dimension), such as differences sentence embeddings due to gender pronouns in the Bios experiment or due to identity (counterfactual) tokens in the Toxicity experiment.
Synthetic experiment In the synthetic experiment in Figure we consider fair metric ignoring variation along the r-axis coordinate, i.e. = [1 0J=.
Toxicity experiment To compute A we utilize FACE algorithm of Mukherjee et al. (2020) (see section 2.1 and Algorithm in their paper). Here groups of comparable samples are the BERT embeddings of sentences from the train data and their modifications obtained using 25 counterfactuals known the training time. For example, suppose have sentence "Some people gay" in the train data and the list known counterfactuals is "gay", "straight" and "muslim". Then we can obtain comparable sentences: "Some people straight" and "Some people muslim". BERT embeddings the original and two created sentences constitute a group of comparable sentences. Embeddings of groups of comparable sentences the inputs Algorithm I of Mukherjee al. (2020), which consists of per-group centering step followed by singular value decomposition. Taking the top metric.
singular vectors gives us matrix of sensitive directions A defining the fair
Bios experiment We again utilize FACE algorithm of Mukherjee et al. (2020) to obtain the fair metric. Here the counterfactual modification is based on male and female gender pronouns. For example, sentence "He went to law school" is modified to "She went to law school". As result, each group of comparable samples consists of pair of bios (original and modified). Let X E [Raxd be the data matrix of BERT embeddings of the train bios, and let X" E Rna be the corresponding modified bios. Here Algorithm 1 of Mukherjee et al. (2020) is cquivalent to performing SVD on X - X'. We take the top k 25 singular vectors obtain sensitive directions A and the corresponding fair metric.
Adult experiment In this experiment A consists three vectors: a vector of zeros with in the gender coordinate; vector of zeros with in the race coordinate; and vector of logistic regression coefficients trained to predict gender using the remaining features (and 0 in the gender coordinate). This sensitive subspace construction replicates the approach Yurochkin al. (2020) utilized in their Adult experiment for obtaining the fair metric. Please see Appendix B. and Appendix D in their paper for additional details.
17

---

Published as a conference paper at ICLR 2021
C FAIRNESS EVALUATION METRICS DEFINITIONS
Individual fairness To compare individual fairness we used two metries: prediction consistency and Counterfactual Token Fairness (CTF) score of Garg et al. (2018). The idea behind these metrics is to quantify changes in prediction when modifying original data in ways that intuitively should not change behavior of an individually fair classifier.
For Toxicity experiment an individually fair classifier should not change its prediction when word "gay" in a comment is replaced with a word "straight". For example, we expect toxicity predictions on "Some people are gay" and "Some people are straight" to be the same. Following prior work (Dixon et al., 2018; Garg et al., 201 8) we considered a set of 50 tokens* that should not affect the classifier when interchanged. For any comment that contains at least one of these 50 tokens 49 versions of it via simple word replacement and evaluate classifier prediction and probability of being toxic for each of the 50 variations (including the original). Prediction consistency is the proportion of comments (with at least one of the 50 tokens) where prediction is the same on all 50 variations. CTF score the average (across all comments with at least one of the 50 tokens) standard deviation of the toxicity probability across 50 variations.
create
We use similar individual fairness metrics for the Bios experiment. We create a single variation of each bio by interchanging "he" and "his" and "her"; "him" and "hers"; "himself" and "herself"; "mr" and "ms" or "mrs"; original name with random name from different gender sampled among those present in the data. Prediction consistency is computed as before using 2 variations (including the original one) each bio. Note that although there are fewer variations, there are significantly more classes in the Bios dataset. CTF score in the average (across all bios) squared Euclidean distance between the vectors of class probabilities for the 2 bio variations.
In the Adult experiment we compute same individual fairness metries in Yurochkin al. (2020), S-Con. (spouse consistency) is the prediction consistency when creating data variations by altering marital status feature. GR-Con (gender and race consistency) is the prediction consistency when creating data variations by altering race and gender features.
Group fairness In our experiments we observed that enforcing individual fairness also has positive effect on group faimess metrics.
In the Toxicity experiment we used accuracy parity (Zafar et al., 2017; Zhao et al., 2019) to quantify group faimess. There are multiple protected groups in the Toxicity dataset (e.g. "muslim", "white". "black", "homosexual or leshian") that correspond to human annotated identity contexts (not necessar- ily mutually exclusive). To account for this when evaluating accuracy parity we computed accuracies for each of the protected groups and reported their standard deviation. Large standard deviation implies that classifier significantly more accurate on some protected groups than on the others. Because of the class imbalance we also reported standard deviation of the corresponding balanced accuracies.
For the Bios experiment we used same group fairness metrics as in the prior works studying this dataset (Romanov al., 2019; Prost et al., 2019). Here protected attribute is binary: male or female genders. Let TPRo, and TPR1, denote true positive rates for class & for protected attributes 0 and 1. Then TPR gap for class is Gap; = , ,, The summary statisties we report are Gap
RMS = V K Σ Gap%, and Gap ABS K Σ Gap,-
For the Adult experiment we used same group faimess metrics in Yurochkin al. (2020), which correspond to Gap RMS described above and Gap MAX = max, Gap,, evaluated with respect to race and gender (both are binary protected attributes in the dataset).
D ADDITIONAL FAIRNESS-ACCURAGE TRADE-OFF RESULTS
Synthetic data experiment In Figure we demonstrated how SenSel allows to control fairness- accuracy trade-off in simulations by plotting the decision boundary of the corresponding classifier for
'https: //g thub. com coneemsatteaaiiioo inai //////nnnnneddee biiiass--- bbias-analle lysis/bli/ master/un http:///unnneeeedddeeee _m_ www.bbaaa/bbssaassea i ibs_data/adjectt ves_people.
18

---

Published as a conference paper at ICLR 2021
(a) 6
(b) 0.001
(c) 6 0.01
(d) c 0.1
Figure 3: The decision surface of hidden layer neural network trained with SenSR (Yurochkin et al., 2020) as the DRO radius varies. Problem setting is the same as in Figure 1. Even for O, SenSR prioritizes fairness over accuracy producing horizontal decision surface. It is unable to achieve intermediate behaviors of SenSel trading accuracy and faimess as in Figure (a.b,c).
varying p. In Figure show the lack of such flexibility in SenSR (Yurochkin et al., 2020): varying the radius of the DRO ball c in their definition of individual fairness results a horizontal decision SenSR ties loss fairness its objective, and in this experiment loss can
boundary even for be increased significantly for anything but horizontal decision boundary (fair metric allows free movement along the x-axis and a data-point can be perturbed in horizontal direction even for 0).
Toxicity and Bios experiments In Figure 2 we presented trade-offs between prediction consistency and balanced accuracy for SenSel and CLP (Garg al., 2018) for the Toxicity and Bios experiments. For completeness Figure 4. As with the prediction consistency, we see that increasing fair regularization strength allows to train classifiers with better individual fairness properties. SenSel outperforms CLP trains classifiers with lower CTF score across all values of p.
also present corresponding CTF score and balanced accuracy trade-off's in
0.:
SenSel
CLP
0.816
CLP
6.225
SerSei
0.846
(0.000
6.225
M64223
0.750
Sen
50923
Regularization Strength
Regularization 5t Strength
Regularizatinn 2ad on strength
Regularization 30 Strnghh
(a) Toxicity CTF score
(b) Toxicity BA
(c) Bios CTF score
(d) Bios BA
Figure 4: Balanced accuracy (BA) and CTF score trade-off on Toxicity and Bios experiments
19


Reviews:
[{"review_id": "Qf5x2FfdJOG", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper proposes a variant of individual fairness, develops an algorithm to enforce this definition, and evaluates it. The fairness definition is based on transport, considering the maximum difference in outcomes for individuals drawn from a distribution \"close\" to the original data distribution in terms of a similarity metric.\n\nThe paper is well-written and thorough. The technical definition of individual fairness is a natural one, and it is amenable to stochastic optimization. Compared to other methods, SenSeI enforces the fairness constraint more strongly, at the cost of accuracy.\n\nSenSeI comes with reasonably strong theoretical guarantees, which I appreciate.\n\nThe individual fairness constraints used in the experiments are all essentially counterfactual in nature -- certain pairs or groups of examples should get the same outcome, and there are no other constraints. Are there scenarios (even synthetic) where one could use more continuous similarity metrics?\n\nThis may be outside the scope of this work, but it would be interesting to dig deeper into which examples lead to fairness violations. For example, in the toxicity classifier, could an investigation into fairness violations tell us something about which counterfactuals are hard to treat equally, and therefore something about the way language is used?", "extra_scores": {}, "extra_text": {}}, {"review_id": "MgPJj7aCLsf", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "############# Summary of contributions ##############\n\nThis paper tackles the problem of enforcing individual fairness. They define a notion of “distributional individual fairness” (DIF) which related to Dwork et al. 2011’s definition of individual fairness. They then provide an algorithm that enforces their DIF definition of individual fairness. They take as given the similarity metric required for evaluating individual fairness. \n\nSpecifically, contributions include:\n\n- Theoretical: This paper proposes an “average case” definition for individual fairness which they call “distributional individual fairness” (DIF) (Definition 2.1). They theoretically compare DIF to the previous definition of individual fairness from Dwork et al. (Equation 2.1). DIF has the advantage of being computationally easier to enforce.\n\n- Algorithmic: This paper proposes an algorithm for enforcing DIF using stochastic gradient methods.\n\n- Theoretical: They provide a generalization bound for their algorithm (Theorem 3.1).\n\n- Empirical: Using three real-world datasets, they evaluate their algorithm’s ability to satisfy both individual and group-based fairness constraints. \n\n############# Strengths ##############\n\n- The experiments are well set up and reflect real-world problems. The toxic comment detection experiment includes a counterfactual individual fairness metric that is reasonable and has precedent. \n\n- Experiments evaluate group-based fairness metrics in addition to individual fairness metrics. These metrics are all relevant to their respective datasets and problem setups. \n\n- The paper also discusses the theoretical relationship between their definition of “distributional individual fairness” (DIF) and the existing individual fairness definition proposed by Dwork et al. (Equation 2.1). This comparison is presented well. \n\n- The paper provides theoretical analysis of the proposed algorithm. Theorem 3.1 provides a generalization bound for the SenSeI algorithm. Theorem 2.3 provides the dual form of the DIF regularizer which is used to solve their optimization problem for enforcing distributional individual fairness. \n\n- The related work is well organized. It covers related work in enforcing individual fairness and learning similarity metrics.\n\n- The hyperparameter selection procedure is well documented in Appendix B. \n\n############# Weaknesses ##############\n\n- It would be nice to have a clearer picture of the cases in which satisfying DIF actually leads to satisfying the individual fairness definition of Dwork et al. (Equation (2.1)), and vice versa. Currently, the theoretical comparison of DIF and Equation (2.1) feels a bit abstract and difficult to translate into real-world applications. Are there some distributional assumptions under which satisfying DIF implies satisfying Equation (2.1) (or vice versa)? \n\n############# Recommendation ##############\n\nOverall, my recommendation is 7: Good paper, accept. This paper provides a theoretically-backed algorithm for enforcing their definition of “distributionally individual fairness.” Their analysis is understandable, and their experiments appear detailed enough to be reproducible. My only major ask is for a more concrete and practically actionable description of the difference between DIF and Dwork et al.’s individual fairness.\n\n############# Questions and clarifications ##############\n\n- After Equation (2.3) on page 2, the authors state that the T(x) map corresponding to Equation (2.1) may not be an optimal point of Equation (2.3). Can the authors give a concrete example of a probability distribution P in Equation (2.3) when this T(x) is not optimal? This would give us further intuition for the difference between DIF (Definition 2.1) and Dwork et al.’s individual fairness (Equation (2.1)). \n\n- The notation in Equation (2.4) is unclear. Is x’ a random variable with distribution P’, and if so, why is x’ lowercase (it seems that up to this point the paper has kept the convention that random variables are upper case and fixed values are lowercase)? What about the random variable Y? Is P’ the joint distribution of X’, Y’? If that’s the case, why does it say that W_{dX}(P, Q) is the Wasserstein distance between distributions on \\mathcal{X}? It seems there are some typos here that the authors should clarify.\n\n- In Definition 2.2, Is \\Delta(\\mathcal{X} \\times \\mathcal{X}) supposed to represent the set of all probability distributions over \\mathcal{X} \\times \\mathcal{X}? I don’t see this defined explicitly anywhere.\n\n- Is the \\hat{h} notation really necessary at the top of page 6 in the last sentence before Section 4? The \\hat{h} notation has not been defined or used up to this point. It seems that it would be sufficient to just use h in this sentence, as h has already been referred to as the trained ML model. \n\n- Figure 1 is hard to read. The red/blue dots are not colorblind-friendly -- maybe you can use different symbols in addition to different colors, e.g. x’s for the red dots and o’s for the blue dots. The x and y axis labels are also extremely tiny.\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "InJSxPoP9ev", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 2, "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": "\nQuality\n- This paper is largely well-written with clearly stated theoretical results, and a range of experiments on three datasets.\n\nClarity\n- What is the notation $\\Delta(\\mathcal{X} \\times \\mathcal{X})$?\n- In the experiments section, SenSeI is compared with CLP, which is a method that uses hand-crafted counterfactuals. However, it appears that SenSeI’s implementation of individuals crucially requires hand-crafted counterfactuals as well? It was not clear to what the distance metric used in the experiments was. If the SenSeI implementation also uses the same counterfactuals, please comment on whether this is a fair comparison with CLP, and if other implementations of SenSeI (with different metrics) would yield the same results.\n- Why are group fairness metrics compared in the experiments section? None of the methods studied target group fairness in general so the connection and relevance of group fairness should be elaborated upon.\n\nOriginality/Significance\n- This paper’s original contribution is variant definition of Dwork et al’s “individual fairness” notion, that circumvents its computational intractability, by making it smooth. This is a significant enough contribution to the study of individual fairness, that makes it more applicable in practice.", "extra_scores": {}, "extra_text": {}}, {"review_id": "6BnYRVb4cC6", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper extends the individual fairness definition in order to (i) do statistical analysis (e.g., generalization bound) (ii) have the form of regularization so the practitioner can tune the parameter. Theorem 2.3 shows how to do stochastic optimization on the new definition, and Theorem 3.1 shows that that the new definition generalizes. \n\nThe paper is extremely well written, it was effortless to follow the arguments, and I enjoyed reading it. The theory part is sound and interesting, and the authors did a thorough experimental analysis on three datasets and compared their work with two baselines.\n\n\nThe authors motivate this work as a new formulation of individual fairness that decouples accuracy and fairness with a regularization term, enabling the practitioner to tune the parameter. I found this argument unconvincing. It is much easier for the practitioner to tune epsilon and delta, and the algorithm finds the minimum error while satisfying DIF. Tuning \\ro after setting epsilon and delta is not very intuitive for practitioners. \n\nMinor concerns:\nIn the related work, the authors argue that their work is different from previous extensions of the IF since they use the metric instead of the oracle. What is the big difference between using oracle and having access to metric? Can one serve instead of the other?\nIn the experiment section, the number reported for CLP is very different from their paper on comment toxicity detection. \nI think having a few sentences on how to learn the individual metrics would be really good. (Right now, you refer to many work on learning metrics multiple times, but it’s never clear how they learn the similarity metric).\nComparing equation 2.1 and definition 2.1 is somewhat confusing. I think it would be more clear if you say 2.1 and 2.2 instead.", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: All of the reviewers agree that this paper is well-written, and provides sound theoretical analyses and comprehensive empirical evaluations. Overall, this paper makes a useful contribution in the direction of individual fairness. The authors have also addressed the concerns raised by the reviewers in their response.
Decision: Accept (Oral)