Statistical inference for individual fairness
Authors: Subha Maity
Songkai Xue
Mikhail Yurochkin
Yuekai Sun
Venue: ICLR 2021 Poster (2021)

Abstract: As we rely on machine learning (ML) models to make more consequential decisions, the issue of ML models perpetuating unwanted social biases has come to the fore of the public's and the research community's attention. In this paper, we focus on the problem of detecting violations of individual fairness in ML models. We formalize the problem as measuring the susceptibility of ML models against a form of adversarial attack and develop a suite of inference tools for the adversarial loss. The tools allow practitioners to assess the individual fairness of ML models in a statistically-principled way: form confidence intervals for the adversarial loss and test hypotheses of model fairness with (asymptotic) non-coverage/Type I error rate control. We demonstrate the utility of our tools in a real-world case study.

Published as a conference paper at ICLR 2021
STATISTICAL INFERENCE FOR INDIVIDUAL FAIRNESS
Subha Maity
Songkai Xue
Mikhail Yurochkin
Department of Statistics University of Michigan smaity@umi ch. edu
Department of Statistics
IBM Research MIT-IBM Watson Al lab mi khail www.yakiiiiiiiie.e com
University of Michigan sxue@ume uui ch. edu
Yuekai Sun
Department of Statistics University of Michigan yueka i @umi ch. edu
ABSTRACT
As we rely on machine learning (MI.) models to make more consequential decisions, the issue of MI. models perpetuating or even exacerbating undesirable historical biases (e.g. gender and racial biases) has come to the fore of the public's ' attention. In this paper, we focus on the problem of detecting violations of individual fairness in ML models. We formalize the problem as measuring the susceptibility of ML models against a form of adversarial attack and develop suite of inference tools for the adversarial cost function. The tools allow auditors to assess the individual faimess of ML models in a vatistically-princippe for the worst-case performance differential between similar individuals and test hypotheses of model fairness with (asymptotic) non-coverage/Tyy I error rate control. We demonstrate the utility of our tools in real-world case study.
way: form confidence intervals
INTRODUCTION
The problem bias in machine learning systems at the forefront contemporary MI. research. Numerous media outlets have scrutinized machine learning systems deployed in practice for violations of basic socictal equality principles (Angwin et al. 2016; Dastin 2018; Vigdor 2019). In response researchers developed many formal definitions of algorithmic fairness along with algorithms for enforcing these definitions in ML models (Dwork et al., 2011 Hardt et al. 2016 Berk et al. 2017]
Kusner et al.) 2018 Ritov et al.) 2017; Yurochkin et al.) 2020). Despite the flurry of ML fairness research, the basic question of assessing fairness of a given ML model in a statistically principled way remains largely unexplored.
In this paper we propose a statistically principled approach to assessing individual fairness (worrk al., (01I) of ML models. One of the main benefits of our approach is it allows the investigator to calibrate the method; i.e. it allows the investigator to prescribe Type I error rate. Passing test that has guaranteed small Type error rate the usual standard of proof scientific investigations because it guarantees the results are reprodueible (to a certain degree). This is also highly desirable in detecting bias in ML models because it allows us certify whether an ML model will behave fairly at test time. Our method for auditing ML models abides by this standard.
There are two main challenges associated with developing a hypothesis test for individual fairness. First, how to formalize the notion of individual fairness in an interpretable null hypothesis? Second, how to devise test statistic and calibrate so that auditors can control the Type error rate? In this paper we propose a test motivated by the relation between individual fairness and adversarial robustness YYurochkin et al. 2020). At a high-level, our approach consists of two parts:
1. generating unfair examples: by unfair example we mean an example that is similar to a training example, but treated differently by the ML models. Such examples are similar to adversarial examples (Goodfellow et al.] 22014), except they are only allowed to differ from a training example in certain protected sensitive ways.

---

Published as a conference paper at ICLR 2021
2. summarizing the behavior of the ML model on unfair examples: We propose loss-ratio based approach that is not only ceale-free, but also interpretable. For classification problems, we propose variation of our test based the error rates ratio.
1.1 RELATED WORK
At a high level, our approach is to use the difference between the empirical risk and the distributionally robust risk as test statistic. The distributionally robust risk is the maximum risk of the MI. model on similar training examples. Here similarity is measured by a fair metric that encodes our intuition of which inputs should be treated similarly by the ML model. We note that DRO has been extensively studied the recent literature (Duchi et al., 2016 Blanchet & Murthy 2016 Hashimoto et al. 2018),
however outside of the fairness context with the exception of Yurochkin et al. (2020); Xue et al. (2000) Yurochkin et al. (020)) focus on training fair or robust ML models instead of auditing ML models.
Xue et al. (2020) also use the difference between the empirical and distributionally robust risks test statistic, but their test is only applicable ML problems with finite feature spaces. This limitation severely restricts the applicability of their test. On the other hand, our test is suitable for ML problems with continuous features spaces. We note that the technical exposition in Xue al. (220)) is dependant on the finite feature space assumption and in this work we develop a novel perspective of the problem that allows us to handle continuous feature spaces.
2 GRADIENT FLOW FOR FINDING UNFAIR EXAMPLES
In this section, we describe a gradient flow-based approach to finding unfair examples that form the basis of our suite of inferential tools. Imagine an auditor assessing whether an ML model fair or not. The auditor aims to detect violations of individual faimess in the ML model. Recall Dwork et al.) 12 definition of individual fairness. Let C IRd and y C Rd be the input and output spaces respectively, and f X > y be an ML model to audit. The ML model f is known individually fair if
d,(f(z)), S Listedg((1, x2) for all T1, 22 E X
(2.1)
for some Lipschitz constant Liair > O. Here d, and dy are metrics on X' and ) respectively. Intuitively, individually fair ML model treats similar samples similarly, and the fair metric d, encodes our intuition of which samples should be treated similarly. We should point out that d, (x1, x2) being small does not imply 2i and x2 are similar all aspects. Even if d. (21, 22) is small, 2i and 22 may attributes.
differ much in certain attributes, e.g., protected/sensittee
Before moving on, we comment on the choice of the fair metric dg. This metric is picked by the auditor and reflects the auditor's intuition about what is fair and what is unfair for the ML task at hand. can be provided by a subject expert (this is Dwork et al. (201T)s I's original recommendation) or learned from data (this is recent approach advocated by [Ivento (2019); Wang al. (2019); 4 provides details of picking a fair metric in our empirical studies.
Mukherjee et al. 22020) ). Section
To motivate approach, recall the distributionally robust optimization (DRO) approach to training individually fair ML models (Yurochkin et al. 2020)). Let f X - y be an MI. model and (x), y) 2 TR+ be any smooth loss (e.g. cross-entropy loss). To search for differential treatment in the ML model, Yurochkin et al. (2020) solve the optimization problem
max (.W.P.P.) S [ (((()))))dP(())
(2.2)
where Wi is the Wasserstein distance probability distributions on feature space induced by the fair metric, P., is the empirical distribution of the training data, and e is moving budget that ensures the adversarial examples are close to the (original) training examples in the fair metric. Formally, this search for differential treatment checks for violations of distributionally robust fairness.
Definition 2.1 (distributionally robust fairness (DRF) (Yurochkin et al. 2020 An ML model h X + y is (e, 8) -ditriibution robustly fair (DRF) WRT the fair metric d, if
supp.wcp...se S2 h) S2 ((2, ()) S
(2.3)
2

---

Published as a conference paper at ICLR 2021
The optimization problem (2.2) is Blanchet & Murthy show that the dual of (.22 is
problem, but its dual is more tractable.
max (P..)s))
[p((([(x).
min + Ep, (2, v)l X20
(2.4)
(x1,
max max((([(zr) - #EX
(2.5)
In practice, since (2.5) is highly non-convex in general, auditors use gradient- based optimization algorithm to solve it and terminate the algorithm after few iterations. As a result, one can not guarantee optimality of the solution. However, optimality is required to establish convergence guarantees for DRO algorithms. This issue is typically ignored in practice when developing training algorithms, e.g. as in Yurochkin et al. (2020), but should be treated with care when considering limiting distribution of the related quantities required to calibrate a test. We note that Xue et al. (2020) needed discrete feature space assumption due to the aforementioned concern: when the feature space is discrete, it is possible to solve (2.5) optimally by simply comparing the objective value all points of the sample space. In this paper we adapt theory to practice, i.e. analyze the limiting distribution of (2.5) optimized for fixed number of gradient steps.
The effects of early termination can be characterized by a contimuous- approximation of adver- sarial dynamics, which called gradient flow atlack. Given sample (2o, yo). the gradient flow attack solves continuous time ordinary differential equation (ODE)
(1) V=(e((((()))
(X),,
(2.6)
(x(0) = -.,,
over time 2 0. For fixed penalty parameter and stopping time T > 0, 4 : X' y - X' is the unfair map
((ro. 9o) & X(T).
(2.7)
Here the map T is well-defined long ((x) - V (e(((()), yo) (2, is Lipschitz, i.e., (1g(x1) g(x2))) ll2 S. L||=1 z2/12 for some L > 0. Under this assumption, the autonomous Cauchy problem (2.6) has unique solution and thus 4- X'
X' is one-to-one function. We call & an unfair map because it maps samples in the data to similar areas of the sample space that the ML model performs poorly on. We note that data in this case is an audit dataset chosen by the auditor to evaluate individual fairness of the given model. The audit data does not need to be picked carefully and could be simply an iid sample (e.g. testing data). The unfair map plays the key role as allows us to identify areas of the sample space where model violates individual fairness, even if the audit samples themselves reveal no such violations.
In the rest of the paper, we define the test statistic in terms of the unfair map instead of the optimal point of 2.5 This has two main benefits:
computational tractability: evaluating the unfair map computationally tractable because integrating initial value problems (IVP) is a well-developed area of scientific computing (Heath) 2018). Auditors may appeal to any globally stable method for solving IVP's to evaluate the unfair map.
reprodueibility: the non-convex nature 2.5 means the actual output of any attempts at solving (2.5 is highly depend on the algorithm and the initial iterate. By defining the test statistic algorithmically, we avoid ambiguity in the algorithm and initial iterate, thereby ensuring reproducibility.
Of course, the tractability and reproducibility of the resulting statistical tests comes at cost: power. Because we are not exactly maximizing (2.5). the ability of the test statistic to detect violations of individual fairness is limited by the ability of (2.7) to find (unfair) adversarial examples.
2.1 EVALUATING THE TEST STATISTIC
Solving IVP's is well-studied problem in scientific computing, and there many methods for solving IVP's. For our purposes, it is possible to use any globally stable method to evaluate the unfair map. One simple method is the forward Fuler method with sufficiently small step size. Let
3

---

Published as a conference paper at ICLR 2021
0 < t1 < ... <NN = T be partition of [0, 7], and denote the step size by 7 tk-1 for k , N. Initialized at (1(0) Zo, the forward Euler method repeats the iterations
x (k) = x k- TJ V V=((([(((--)) vo) X ( ro)]
(2.8)
for k = ...................... N. The validity of discretizations of the forward Fuler method is guaranteed by the following uniform bounds.
Theorem 2.2 (Global stability of forward Euler method). Consider the solution path (t) JOSEST given by (2.6) and the sequence (2:(k) 1==0 given by (28). Let the maximal step size be h max (m,...., JN Suppose that (z)())(( S m, where Vx - mo)} and Jg is the Jacobian matrix of g. Then have
hmvdd (e - -1).
max k=....,,N
(x((x) 122 S
(2.9)
2L
Theorem 2.2 indicates that the global approximation error (.. decreases linearly with h, the maximal step size. Therefore by taking small enough h, the value of the unfair map & can be approximated by (N) with arbitrarily small error.
3 TESTING INDIVIDUAL FAIRNESS OF AN ML MODEL
Although gradient flows are good ways of finding unfair examples, they do not provide an interpretable summary of the ML model outputs. In this section, we propose a loss-ratio based approach to measuring unfairness with unfair examples. Given a sample point (ro, yo) E 2, gradient flow attack (.66 always increases the regularized loss in (255), that is,
((((x)): yo) S ((f(X(T)) mo) - (X(),, S (T((())).
(3.1)
Therefore the unfair map 4 Z + X' always increases the loss value of the original sample. In other words, the ratio
((f((zz, w)).u) 2 for all (2.8) E Z.
(3.2)
(((()))))
Recall that the unfair map moves sample point to its similar points characterized by the fair metric dz. The fair metric d, reflects the auditor's particular concern of individual fairness so that the original sample (æ, y) and the mapped sample (#(x, y), y) should treated similarly. If there is no bias/unfairnes in the ML model, then expect the ratio {(f (f((fz (z, y)), v) a)/((f(x)))) y) to be close to 1. With this intuition, to test the ML model is individually fair or not, the auditor considers hypothesis testing problem
(()( {(f(x).v)
(()())))))) {(f(x),))
Ho : Ep
< versus
H1 Ep
> 8,
(3.3)
where P is the true data generating process, and 5 > 1 is constant specified by the auditor. Using the ratio of losses in (.3) has two main benefits:
1. scale-free: changing the loss function by multiplying a factor does not change the interpretation of the null hypothesis.
2. The test is interpretable: the tolerance 8 is the maximum loss differential above which we consider an ML model unfair. In applications where the loss can be interpreted as a measure of the negative impact of an ML model, there may be legal precedents on acceptable levels of differential impact that is tolerable. In our computational results, we set 6 according to the four-fiftht rule in US labor law, Please see Section 3.2 for further discussion regarding å and interpretability.
We note that using the ratio of losses the test statistic is not without its drawbacks. If the loss is small but non zero, then the variance of the test statistic is inflated and and the test loses power, but Type I error rate control is maintained.
4

---

Published as a conference paper at ICLR 2021
3.1 THE AUDIT VALUE
The auditor collects set of audit data {(z,, M and computes the empirical mean and variance of the ratio (( y)). ())((())))()))))))))
1 (fs( Sn
(L(( Sn ) (3.4)
2
and V
((f(z)).
[(f(z)).))
by solving gradient flow attack (.6). The first two empirical moments, Sn and V22 sufficient for the auditor to form confidence intervals and perform hypothesis testing for the population mean Ep(e(f(#xx, v)). ()/e(f(z) (z), (z),y)], y)], the audit value.
Theorem 3.1 (Asymptotic distribution). Assume that V Ve(l(f(z),)) y) - (d, ÿ)} is Lipschitz in and ( a)), /))((((x), 2) has finite first and second moments. If the ML model f is Pizi then
independent of { yb) )
(110(1)0)) 3 1(
VVV= Ep
Ep (((()).))
(3.5)
in distribution, 00.
The first inferential task to provide confidence intervals for the audit value. The two-sided cqual-tailed confidence interval for the audit value Er(e(f v) v)((((((() y)] with asymptotic coverage probability is
21-a/2 Vns Sn 21 21-a/2 V
CI Clwwosided
Sn
(3.6)
Vn
vn
where by is the y-th quantile of normal distribution N(,0 1).
Corollary 3.2 (Asymptotic coverage of two-sided confidence interval). Under the assumptions in
Theorem 3.7
lim P 12
EP
(Lf((((z.))).)2) {(f()),)
S, 21-a/2 Vn
Vn, V1..//Vn..... Sn
21 21-a/2 Vn
= a. (3.7)
Vn
The second inferential task is to test restrictions on the audit value, that is, considering the hypothesis testing problem (3.3). Similar the two-sided confidence interval (3.6). we may also have one-sided confidence interval for the audit value [p[[(f( (z. probability a, i.e.,
with asymptotic coverage
Clone-sided
Sn
21 Vn
Vn, Vn,, 20)
(3.8)
The one-sided confidence interval
3.8) allows us to test simple restrictions of the form
((((((z,))).))
E,
(3.9)
{(f(x).v)
by checking whether d falls in the (1 - a level confidence region. By the duality between confidence intervals and hypothesis tests, this test has asymptotic Type I error rate at most a. With this intuition, valid test is:
Reject Ho Tf 8, T, A S. 21-a Vn.
(3.10)
Vn
where T, the test statistic.
Corollary 3.3 (Asymptotic validity of test). Under the assumptions in Theorem 3.1
( ()) v)] < we have lim,-+00 IP,, > 8) $3300 a;
2. (TT v)) have lim PPTT, 5) 1.
5

---

Published as a conference paper at ICLR 2021
3.2 TEST INTERPRETABILITE TEST TOLERANCE AND AN ALTERNATIVE FORMULATION
To utilize our test, auditor should set a tolerance (or threshold) parameter ò. It is important that a auditor can understand and interpret the meaning of the threshold they choose. Appropriate choice of 5 can vary based on the application, however here we consider a general choice motivated by the US Equal Employment Opportunity Commission's 's four-fifths rule, which states "selection rate for any race, sex, or ethnic group [must be at least] four-fifths (4/5) (or eighty percent) of the rate for the group with the highest rate"[ Rephrasing this rule the context of the loss ratio, we consider the following: the largest permissible loss increase on an individual should be at most five-fourth (5/4) of its original loss. This corresponds to the null hypothesis threshold ö 1.25.
The aforemenniooed wording of the four-fifth rule is based the demographic parity group fairness definition, however can be generalized to other group fairness definitions as follows: "performance of the model any protected group must be at least four-fitth fifth of the best performance across groups". Depending on what we mean by performance, we can obtain other group fairness definitions such as accuracy parity when auditing an MI classification system. In our test, the loss is a general measure of performance of an ML. system. However, in the context of supervised learning, the loss is often mathematically convenient proxy for the ultimate quantity of interest, error rate. For classification problems, it is possible to modify our test statistic based on the ratio of error rates instead of losses (maintaining 1.25 according the five-fourth rule).
the loss ratio because
Let 1 be the 0-1 loss. Naively, we could consider the mean of the ratio (f as a test (f statistic, but this is problematic because the ratio is not well-defined when the classifier correctly classifies x. To avoid this issue, we propose considering the ratio of means (instead of the mean of the ratio) as a test statistic. Formally, we wish to test the hypothesis
Eplea,1 (f(() > 8, Ho : (f v)). < versus H1 (f) v)]
(3.11)
Er Ef(Co,1((2)) (f(),
We emphasize that the gradient flow attack is still performed with respect to smooth loss function; merely the 0-1 loss function to evaluate the accuracy of the classifier on the original and adversarial examples.
The auditor collects set of audit data {(r,, yz) v:)] and computes the ratio of empirical risks
1 E (o.()((((r and V,, & Co ( (i). u:) S,
[ooa (f U:)), 9:) lo.1 (f(z), Mi)
E lo,1 (J vk)
(f
(3.12)
by performing the gradient flow attack (2.6). Let An and B, be the numerator and denominator of S.. Parallel to the intuition of (3.10), here the proposed test is:
A2 + BB(V.).. 2.,.B..(v)... (3.13)
Reject Ho if if,
T, Sn
21-a
B²
where T, is the test statistic. Please see Appendix error guarantees.
C for the asymptotic normality theorem and Type I
INDIVIDUAL FAIRNESS TESTING IN PRACTICE
In our experiments we first verify our methodology in simulations and then present case-study of testing individual faimess on the Adult t dataset (Dua & Graff 2017).
auditor performing the testing would need to make three important choices: fair metric dz +). testing threshold ö to have concrete null hypothesis and level of significance (maximum allowed type error of hypothesis testing, i.e. p-value cutoff) to make a decision whether the null (classifier is fair) should be rejected. The fair metric can be provided by a subject expert, as considered in our simulation studies, or estimated from data using fair metric learning techniques proposed in the literature, we do in the Adult experiment. Following the discussion in Section 3.2 we set
Uniform Guidelines on Employment Selection Procedures, 29 C.F.R. $1607.4(D) (2015).

---

Published as a conference paper at ICLR 2021
-1
-2
-3 8:
1.0
1.0
Figure 1: Heatmaps of the test statistic T, (3.10) for logistic regression classifier grid of coefficients (01, 02). Individually fair classifier corresponds to 01 close to and any 82. Black line in each plot represents the null hypothesis rejection decision boundary T, > 1.25. Blue color represents acceptance region, whereas the red corresponds to unfair coefficients regions. The true fair metric discounts any differences along the first coordinate (left); (center,right) are results with misspecified fair metric, i.e. discounting direction is rotated by 5" and 10 respectively.
6 = 1.25. For the significance level, typical choice in many sciences utilizing statistical inference is 0.05, which we follow in our experiments, however this not a universal rule and should be adjusted in practice when needed.
4.1 STUDYING TEST PROPERTIES WITH SIMULATIONS
We first investigate the ability of our to identify an unfair classifier, explore robustness fair metric misspecification verifying Theorem A. and discuss implications of the choice of null hy- pothesis parameter We simulate a 2 2-dimensional binary classification dataset with two subgroups of observations that differ only in the first coordinate (we provide additional details and data visu- alization in Appendix E One of the subgroups is underrepresented in the training data yielding corresponding logistic regression classifier that overfits the majority subgroup and consequently differentiates data points
(i.e. "individuals") along both coordinates. Recall that a pair of points that only differ in the first coordinate considered similar by the problem design, i.c. their fair distance and prediction for such points should be the same to satisfy individual fairness.
Fair metric Our expert knowledge of the problem allow to specify fair metric d ((11, (z1, = (xz - 2² Evidently, an individually fair logistic regression should have coefficient of the first coordinate A = 0, while intercept and 6g can be arbitrary. The more 0, differs from 0, the larger is the individual fairness violation. In Figure (left) we visualize the heatmap of the test statistic (3.10) for each coefficients pair). Recall that when this value exceeds 8 = 1.25 our test rejects the null (fairness) hypothesis (red heatmap area). Our test well-aligns with the intuitive interpretation of the problem, i.c. test statistic increases as 0, deviates from O and is independent of the 0g value.
grid of (01, 02) values (intercept estimated from the data
Metric misspecification We also consider fair metric misspecification in the center and right heatmaps of Figure [ Here the discounted movement direction in the metric is rotated, i.c. d' ((111x2). (a1 22)) 2) (sin" ()( x1) (cos² 3)(x; - x22)² for 52 (center) and 10 (right). We see that the test statistic starts to reject fairness of the models with larger 0₂ magnitudes due to misspecification of the metric, however it remains robust in terms identifying 01 as the fair model.
Null hypothesis threshold Finally we assess the null hypothesis choice = 1.25. We saw that the test permits (approximately) 0, < 1.5 whether this causes minor severe individual fairness violations depends on the problem at hand. A auditor that has access to an expert knowledge for defining the fair metric and desires stricter individual faimess guarantees may consider smaller values of 8. In this simulated example, we see that as 8 approaches I, the test constructed with the correct fair metric (Figure left) will reject all models with 0, * 0, while permitting any 02 values.
7

---

Published as a conference paper at ICLR 2021
4.2 REAL DATA CASE-STUDY
We present scenario of how our test can be utilized in practice. To this end, we consider income classification problem using Adult t dataset (Dua & Gratt 2017). The goal is to predict if a person is earning over $50k per year using features such as education, hours worked per week, etc. (we exclude race and gender form the predictor variables; please see Appendix and code in the supplementary materials for data processing details).
Learning the fair metric In lieu of an expert knowledge to define a fair metric, we utilize technique by |Yrrcchkin et al. (2020) learn fair metric from data. They proposed fair metric of the form: (æ, x²) = (x= x,, P(x x²)), where P is the projection matrix orthogonal to "sensitive" subspace. Similar to their Adult experiment, we learn this subspace by fitting two logistic regression classifier to predict gender and race and taking span of the coefficient vectors (i.e. vectors orthogonal to decision boundary) as the sensitive subspace. The intuition behind this metric is that this subspace captures variation in the data pertaining to the racial and gender differences. A fair metric should treat individuals that only differ gender and/or race as similar, therefore it assigns O distance to any pair of individuals that only differ by vector in the sensitive subspace (similar to the fair metric we used in simulations discounting any variation along the first coordinate). Our hypothesis test is an audit procedure performed at test time, so we learn the fair metric using test data to examine fairness of several methods that only have access to an independent train set to learn their decision function.
Results We perform testing of the 4 classifiers: baseline NN, group faimess Reductions (Agarwal itt al.] 2018) algorithm, individual fairness SenSR (Yurochkin et al. 2020) algorithm and a basic Project algorithm that pre-processes the data by projecting out "sensitive" subspace. For SenSR fair metric and Project we use training data to learn the "sensitive" subspace. All methods are trained to account for class imbalance in the data and we report test balanced accuracy as performance measure following prior studies of this dataset (Yurochkin et al. 22200] Romanov et al. 2011)) Results of the 10 experiment repetitions are summarized in Table I (see Table 3 in Appendix [:6 for the standard deviations). We compare group fairness using average odds difference (AOD) (Bellamy al., 2018) for gender and race. Significance level for null hypothesis rejection is 0.05 and 1.25 (see Appendix F and code for details regarding the algorithms and comparison metrics).
Baseline exhibits clear violation of both individual (T,, >>>>>>> 1.25 and rejection proportion is 1) and group fairness (both AOD are far from 0). Simple projection pre-prcessiing improved individual fairness, however the null is still rejected in the majority experiment repetitions (balanced accuracy improvement is accidental). A more sophisticated individual fairness algorithm SenSR does perform well according to our test with test statistic close to 1 (ideal value) and the test fails to reject individual fairness of SenSR every time. Lastly we examine the trade-off between individual and group fairness. Enforcing group fairness with Reductions leads to best AOD values, however it worsens individual fairness (comparing to the baseline) as measured by the test statistic. On the contrary, enforcing individual fairess with SenSR also improves group fairness metrics, however at the cost of the lowest balanced accuracy. We present a similar study of the COMPAS dataset in Appendix G Results there follow the same pattern with the exception of Reductions slightly improving individual fairness in comparison to the baseline, but still being rejected by our test in all experiment repetitions.
Both loss-ratio test Tn and error-rate ratio test Fn results are almost identical. The only difference is that loss ratio test rejected Project in 9 out of 10 trials, while error-rate ratio test in 8 out of 10 trials.
Setting stopping time T. Recall that the test statistic Tr, depends on the number of steps T of the gradient flow attack (2.6). Corollary 3.3 guarantees Type I error control for any T, i.c. it controls the error of rejecting a fair classifier regardless of the stopping time choice. Theoretical guarantees for Type error, ie. failing to reject an unfair classifier, are hard to provide in general (one needs to know expected value of the loss ratio for a given I' and a specific model). In practice, we recommend running the gradient flow attack long enough (based on the available compu- tation budget) to guarantee small Type II error. In our Adult experiment we set 7 500. In Figure
Reduction
Baseline
Project
10.
SenSR T, 1.25
10
20
40
60
160
320
640
1280
2560
steps
(7)
Figure 2: T, as a function of stopping time T Adu data (log-log scale)
8

---

Published as a conference paper at ICLR 2021
Table 1: Results Adult t data over 10 experiment repetitions
Entropy loss
0-1 loss
bal-acc
AOD gen
AOD
Tp
rejection prop
rejection prop
Baseline 0,817
-0.151
-0,061
3.676
1.0
2.262
1.0
Project 0.825
-0.147
-0.053
1.660
0.9
1.800
0.8
Reduction
0.800
0.001
-0.027
5.712
1.0
3.275
1.0
SenSR 0.765
-0.074
-0.048
1.021
0.0
1.081
0.0
(note the log-log scale) we present an empirical study of the test statistic Tr as a function of stopping time T. see that our test fails to reject SenSR, classifier we found individually fair, for any value of T verifying our Type error guarantees in prac- tice. Rejection of the unfair classifiers requires sufficiently large T. supporting our recommendation for Type II error control in practice.
DISCUSSION AND CONCLUSION
We developed a suite of inferential tools for detecting and measuring individual bias in ML models. The tools require access to the gradients/parameters of the ML model, they's re most suitable for internal investigators. We hope our tools can help auditors verify individual fairness of ML models and help researchers benchmark individual fairness algorithms. Future work learning flexible individual fairness metrics from data will expand the applicability range of our test.
We demonstrated the utility of our tools by using them to reveal the gender and racial biases in income prediction model. In our experiments, we discovered that enforcing group fairness may incur individual bias. In other words, the algorithm may sacrifice individual fairness order to preserve parity of certain metrics across groups. For example, one of the earliest methods for enforcing group fairness explicitly treated examples from the majority and minority groups differently (Hardt et 2016). We conjecture that the even the more modern methods for enforcing group fairness could be forcibly balancing outcomes among demographic groups, leading to instances where similar individuals in different demographic groups treated differently. The possible trade-off between individual and group fairness warrants further investigation, but is beyond the scope this paper.
ACKNOWLEDGEMENTS
This paper is based upon work supported by the National Science Foundation (NSF) under grants 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 of the NSF.
REFERENCES
Alekh Agarwal, Alina Beygelzimer, Miroslav Dudík, John Langford, and Hanna Wallach. A Reductions Approach Fair Classification. 1rXiv:180300245 [cs], July 2018.
Julia Angwin, Jeff Larson, Surya Mattu, and Lauren Kirchner. Machine Bias. wiweiiiin---i--ii----eea -ws.rrisssssssmettsseee.. wwwpeatt-----iiimiiaa--eeeeteeee May 2016.
Rachel K. E. Bellamy, Kuntal Dey, Michael Hind, Samuel C. Hoffman, Stephanic Houde, Kalapriya Kannan, Pranay Lohia, Jacquelyn Martino, Sameep Mehta, Aleksandra Mojsilovic, Seema Nagar, Karthikeyan Natesan Ramamurthy, John Richards, Diptikalyan Saha, Prasanna Sattigeri, Moninder Singh, Kush R. Varshney, and Yunfeng Zhang. AI Fairness 360: An Extensible Toolkit for Detecting, Understanding, and Mitigating Unwanted Algorithmic Bias. arXiv:1810.019. [cs], October 2018
Richard Berk, Hoda Heidari, Shahin Jabbari, Michael Kearns, and Aaron Roth. Fairness in Criminal Justice Risk Assessments: The State of the Art. arXiv: 077770309000 [stat], March 2017.

---

Published as a conference paper at ICLR 2021
Jose Blanchet and Karthyek R. A. Murthy. Quantifying Distributional Model Risk via Optimal Transport. arXiv:1604.01446 [math, [aat].pril 2016.
Jeffrey Dastin. Amazon scraps secret Al recruiting tool that showed bias against women. Reaters, October 2018.
Dheeru Dua and Casey Graff. UCI machine learning repository, 2017. URL httt:://ttchh/ee
ics. www.cic..o www.uuu/.........mmmm
John Duchi, Peter Glynn, and Hongseok Namkoong. Statistics of Robust Optimization: A Generalized Empirical Likelihood Approach. arXiv:1610.03425 [stat], October 2016.
Cynthia Dwork, Moritz Hardt, Toniann Pitassi, Omer Reingold, and Rich Zemel. Faimess Through Awareness. arXiv: 104.3913 [cs], April 2011.
lan J. Goodfellow, Jonathon Shlens, and Christian Szegedy. Explaining and Harnessing Adversarial Examples. December 2014.
Moritz Hardt, Eric Price, and Nathan Srebro. Equality of Opportunity in Supervised Learning. 1rX.0:1610002413 [cs], October 2016.
Tatsunori B. Hashimoto, Megha Srivastava, Hongseok Namkoong, and Percy Liang. Fairness Without Demographics in Repeated Loss Minimization. arXiv:18006 1806.080000 [cs, stat], June 2018.
Michael T Heath. Scientific Computing: An Introductory Survey, Revised Second Edition. SIAM, 2018.
Christina Ilvento. Metric Learning for Individual Fairness. arXiv:1906.00255 [cs, staf], June 2019.
Matt J. Kusner, Joshua R. Loftus, Chris Russell, and Ricardo Silva. Counterfactual Fairness. arXiv::703.06856 [es, stat), March 2018.
Jeff Larson, Surya Mattu, Lauren Kirchner, and Julia Angwin. How we analyzed the compas recidivism algorithm. ProPublica (5 2016), 9(1), 2016.
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.
Ya' acov Ritov, Yuekai Sun, and Ruofei Zhao On conditional parity as a notion of non-discrimination in machine learning. arXiv:1706.0880 [cs, stat]. June 2017.
Alexey Romanov, Maria Dr-Artaaga, Hanna Wallach, Jennifer Chayes, Christian Borgs, Alexandra Chouldechova, Sahin Geyik, Krishnaram Kenthapadi, Anna Rumshisky, and Adam Tauman Kalai. What's in a name? reducing bias in bios without access protected attributes. arXiv preprint arXhv:1904.0523: 2019.
Neil Vigdor. Apple Card Investigated After Gender Discrimination Complaints. The New York Times, November 2019. ISSN 0362-4331.
Hanchen Wang, Nina Hlaic, Preethi Lahoti, Krishna P. Gummadi, and Adrian Weller. An Empirical Study Learning Faimess Metrics for COMPAS Data with Human Supervision. arXiv:1910.1022 [cs], October 2019.
Songkai Xue, Mikhail Yurochkin, and Yuekai Sun. Auditing ML Models for Individual Bias and Unfairness. In International Conference on Artificial Intelligence and Statistics, pp. 4552 4562,
June 2020.
Mikhail Yurochkin, Amanda Bower, and Yuckai Sun. Training individually fair ML models with sensitive subspace robustness. In International Conference on Learning Representations, Addis Ababa, Ethiopia, 2020.
10

---

Published as a conference paper at ICLR 2021
A ROBUSTNESS OF TEST STATISTIC TO THE CHOICE OF FAIR METRIC
Since the fair metric dz is picked by an expert's 's domain knowledge or in a data-driven way, the auditor may incur the issue of fair metric misspecification. Fortunately, the test statistic (3.10) is robust to small changes in fair metrics. Let d1, d2 X X + R4 be two different fair metrics on X. Let 1 22 assumptions:
X x ) + X be the unfair maps induced by d1, d2. We start by stating the following
(A1) v=(e([()), - (d, f)} is I--Lipschitz in a with respect to || 112:
(A2) supx,r'ex || - x' D < oo;
(A3) ((f(z),)) y) is Lo-Liscchitz in x with respect to || 12, and lower bounded by c >> 0;
(A4) supz,r'ex' (2, vz 222 2 S D6g for some constant 6d 2
Assumption A1 1 is always assumed for the existence and uniqueness of ODE solution. Assumption A2, that the feature space X' is bounded, and the first part of Assumption A3 are standard in the DRO literature. The second part of Assumption A3 is to avoid singularity in computing loss ratio. Assumption A4 is worthy of being discussed. The constant 8, in A4 characterizes the level of fair metric misspecification. Moreover, Assumption A4 is mild under Assumption A2. For example, let
dz x²) = (x- x', Eexact (r - z²)) and d=(x,²') = (r - x', Emis (x: - x²)) be the exact and misspecified fair metric respectively. Then sup [2,d((x,2)) 2') vr 122 sup ||2Exxact (I x') 2- (x x )l2 2
(A.1)
(A.2)
< sup 2 Eexectt Emiall2 ||x - x'112 z,''EX'
(A.3)
S D- 2/eexctt - Emiall2.
(A.4)
The level of fair metric misspecification da vanishes long Emia estimates Dexect consistently. Theorem A.1 (Robustness of test statistic). Suppose that the support of data distribution P satisfies for any (Io, yo) E sPpp(P), the solution path of ODE (2.6) corresponding to (Zo. yo) and d2 (or d2)
lies in X. Under Assumptions Al A4, we have
((S(F, (30o mo)), L(S(D2(00, vo)), vo) ((fo)) Ho)
Nōa DeLT
(A.5)
{(f(zo).30 30)
for any (ro, vo) E supp((P) P).
The first assumption in Theorem A.1 is mild since we always perform early termination in gradient flow attack.
In the literature, the fair metric can be learned from additional dataset different from the training, test, and audit dataset. In this case, the constant óa, which characterizes the goodness-of- fit of the estimated fair metric to the exact fair metric, shrinks to 0 as co. Then Theorem A.1 provides two key insights.
First, long 8a tends to O, we ultimately test the same null hypothesis since
( pa)), vo) Ep
((f((P2( vo)). yo)
Xda De
Ep
(A.6)
((f(r))
((f(zo). 3o)
c
as 5 + 0.
Second, the error of test statistic induced by the misspecification of fair metric is negligible long as d = (( This is due to the fact that the fluctuations of test statistic are Op( (1))) so Voa must
vanish faster than O (1))) to not affect the test statistic asymptotically.
B PROOFS
B. PROOF OF THEOREM IN SECTION 2
Proof of Theorem 2.2 Let X(1) = (X)))),, (I)) For 1,...,, and = 1,..., .....,, N,
we have
(tx()) = (tx + (to2)) + x2x(00((())
(B.1)
11

---

Published as a conference paper at ICLR 2021
for some 7(0) k-1 1 Lu]. Compactly, have
((x)) = (tx-11) + mh (tx- + 2 (*".)))....."
(B.2)
For = 1,..., N, we let
T3 - X(tx)= (((tk=1) (tx-t)))))
(B.3)
1 (X(l)) - -(le--)-ma (1=-())x)))))))))))))))))))
(B.4)
7k
Note that
[|x())) x11 Sm.
(B.5)
and 77 S h, we have
1
/|
1
2
(B.6)
$ 2 5 yuvall Vd
1
(x.))
(B.7)
hmvd
(B.8)
Let e = ((x)) - ((h) for k = .,... NN, we have
ek X(4x-1) x (K-1) + mh (9(X(1=-1)) - -g(x((-11)) + m:
(B.9)
ck-1 + 17 (9(X(tx-1)) g(x(h-11)) + mrTk.
(B.10)
Since g is L-Lipschitz, have
leul12 S ||ee-1ll2 + melllee-1l12 + 7k hmvd 2
(B.11)
Then,
hmvd
[1ea-1ll2 + hmvd
lex +
S (1+ + Life)
(B.12)
2T.
2T.
hnva (lea-1lle
S cnee
(B.13)
2L
For 1, I,...,,.
hm/d
lmndd
S IT humdd
|ea 2|2 +
S e
(B.14)
2T.
2T.
2T.
Therefore.
hmvd d
max ||X(1x) - x00 max K=
||a/|| <
(c 1).
(B.15)
k=I....N
2I.
B.2
PROOF OF THEOREMS AND COROLLARIES IN SECTION 3
Proof of Theorem
3.1
By central limit theorem (CLT),
(f v)).u)
((f((((z, (L((D(x.)).))) V)).) $ 10,01 e(f(x).))
Vn
Varp
Sn Ep
(B.16)
{(f()).v)
12

---

Published as a conference paper at ICLR 2021
Since
(z.(((z.))).)) ((f(z).))
V2 S Varp
(B.17)
by Slutsky's theorem, we conclude that
[()(((
EEp VTV,'' Sn Ep Proof of Corollary
{(f(x).v) ((f(0).)))))
(B.18)
By asymptotic distribution given by Theorem
3.1
((f(((r w)), v)
E Sn 21-022
21-a/21 Vn
P
Ep
Vna Sn
(B.19)
[(f(z).)) y)
vn
vn
s ==100/2 [(r(((,,)))
=P
Ea/2 I VnVn''
Sn Er
{(f(x).)) {(f())))))
-1aa
(B.20)
+ 00. Proof of Corollary 3.3 Let
as 12
())l)))))))()(()...))))))))()(() u)] By asymptotic distribution given
by Theorem 3.1
P(T, > 8) = P
Sn 21-0 Vn =6)
(B.21)
Vn
= 1 P (VnV 1 (S, -7) 21 + vnV; (6 (6-r)) -))
(B.22)
n
O, T 8
a = 6
(B.23)
1, if
B.3
PROOF OF THEOREM APPENDIX A
Proof of Theorem A./ For any (2o, E Z, let (X)()) solve
(t) = (f). - (t)( [x(()= Du,
(B.24)
and (X2(1) solve
X²(() V v=(e(f(X2(()) -x6 -x)( (x2(0) = Jn-
(B.25)
Consider
s(t) = (xx(t) - X2(t)1 AD28
(B.26)
L
we have
AD28 s(0) L
y(t) 20,
(B.27)
and
6(1) = (() - X2(1), X, - X2(1))
(B.28)
< (t) (2)12 11)
X2(1)12
(B.29)
< (t)) -x2(0)22 (1))) X2(t) + AD63
(B.30)
AD28
$ 2L [|x(()) x2(1 +
(B.31)
L
= 2L vtt)
(B.32)
By Gronwall's inequality,
v(T) < 2LT v()),
(B.33)
13

---

Published as a conference paper at ICLR 2021
that is,
AD [xx(7) - X2(T))
(12LT- -1),
(B.34)
L
which implies
A
1 yo) - #2 (0)ll1 = =1x((T) X2(TT)la I De
(B.35)
By Assumption A3, we have
( (No: vo)). v0) {(f (x)) yo)
(( (())) ((f())), yo)
Ad De L
(B.36)
C ASYMPTOTIC NORMALITY AND ASYMPTOTIC VALIDITY OF THE -ATOR-RATES RATIO TEST
The auditor collects set of audit data {(r,, w:) and computes the ratio of empirical risks
S, ni E (f Us)
1
fo.1 (f U.)). vi)] (f.)(((z)).))
(fo((f(((,,) Wc)) v:) lo. (f ys)
and V,, A
EE (f(:), v.)
(C.1)
by performing the gradient flow attack 2.6 Let A, and B,, be the numerator and denominator of S..
First we derive the limiting distribution of a calibrated test statistic for the error-rates ratio test.
Theorem C.1 (Asymptotic distribution). Assume that V v=((([(x),)) - Ad2 (x. v) is Lipschitz in If the ML model f is independent of {II, y))) then
BBB
Sn Epllo, (f 4 1N0,1
Ep(oo_(((x).))
V A2(Vn)22 BR(V.,,,
(C.2)
in distribution,
Type error rate control is formalized in the following:
Corollary C.2 (Asymptotie validity of test). Under the assumptions in Theorem C.1
1. p( (z( w))///(o, (f(x), y)] ( (f( v)))))))EEeeeee (f(x), v) > we have lim PTT,, > 5) = 1.
have lim P( 2) < a;
Proof of Theorem
C.7 By central limit theorem (CLT),
Va
([
A B
1)
4 NOO, E),
(C.3)
-
My
for finite Mas My. and E with finite entries. Let g( y) = x/y. then Vg(Mz, Mv) = p.y (1y: px)) By continuous mapping theorem, we have
vā (g(An, Br) - g(uns My)) $ NO00, Vg(uz: Myy T EV VVg(un Hy)); (C.4)
which implies
Er (r 4 N 0. 22 + 22 - 2p
Vn 5
(C.5)
Ep Ep
or
Vmpy
S. Ep((o,(((((z,,))).)))
$1 11
(C.6)
Ep(lo,
12 + 1,,1111 24
14

---

Published as a conference paper at ICLR 2021
Since An 4 p2z Bn B My and Vn 4 E, we therefore conclude by Slutsky's Theorem that
Sn ( $ $0000
[p)))
A2((2)2, (2 Bn
Proof of Corollary C.2 Let (F
By asymptotic distribu-
tion given by Theorem C.1
AP((n)2.2 + (2((n)1.1 - 24, B,, s
P(T, > 8) = I
Sn 21-a
B
n
VnB
=1 IP
(Sn -T)
A A2 + B%((.)..1 - 2A, Bn BVn)1..
VnBBB
$ 31-a
(6 (0-7) 7)
A2.(V))2.2 B2(V)),,1
B,,
0, if <
a, if
1, if >
as 72 + 00.
D IMPLEMENTATION OF THE PROPOSED TEST
The algorithm provides a step-by-step procedure for calculating the lower bound. For a choice of (threshold for null hypothesis, see equation 3.3). a level of significance 0.05, we reject the null hypothesis if lower bound is greater than 5.
Algorithm 1 Individual fairness testing
Input: ML model f; loss &; data {(X,, Y=) fair-distance da: regularization parameters A; number of steps T: and step size (T
Require: f provides class probabilities; 6, is decreasing
for i , do Initialize X - X;
for 1, 1,..., T do X + X V (e(f(x)), Y.) - Xx)
end for
r; + {((()))))
end for
Output: lower bound mean(r)
1.645
std(r)
vn
E SUPPLEMENTARY DETAILS FOR SIMULATIONS
Here we provide further details for the experiment with simulated data.
E. DATA
We considered one one group variable G with two labels. The dimensional features were generated with the idea that they will differ in first co-ordinate. We present the detailed model for generating
15

---

Published as a conference paper at ICLR 2021
1.00
Label 0
Label 1
0.75
Group
Group x
0.50
0.25
X2
0.00
xoox
-0.25
x
x
0.75
-2.0
-1.5
-1.0
-0.5
0.0
0.5
1.0
1.5
2.0
X1
Figure 3: Simulated data for synthetic experiment. We have two groups; group being the minority group. The features for these two groups differ mainly by first co-ordinate. So, the discounted movement direction is O)
the data.
G, ~ iid Bernoull((0.1)
X, N (1- (1-G+)
1.5
+ G
1.5
(0.25)*1)
0
0
(E.1)
== 1 (1 G:)
-0.2
+ G.
1) 0.001
0.2
X, N (0, 10 N -00 00}
0.01
for i = 1..... 400.
The data is plotted in Figure 3 As seen in the figure, feature vectors for two groups mainly differ in the first co-ordinate. So, the discounted movement direction is (1, O)".
E.2 CLASSIFIERS
For comparison purpose we consider logistic model of the form
fb, ww (x) expit (b w X!"" + wz x
(E.2)
where expit(x)) A e" (w1, W2) the bias b is chosen as:
Ite7 and the weights are chosen as (wi,w2) (-4, -36., ..... .4)2. For given
400
bwi, w2) e arg min
Σ
(Xi)), Vi),
where é is the logistic loss.
E.3 LOWER BOUND
To calculate the lower bounds Algorithm I with the following choices: the choices of & and provided in the previous subsection. The choice of fair distances are provided in Section We choose regularizer À 100, number of steps T 400 and step sizes 6, 0.02
16

---

Published as a conference paper at ICLR 2021
Table 2: Choice of hyperparameters for Baseline and Project
Parameters learning rate batch_s size
num steps
Choice
10
250
8K
F ADDITIONAL ADULT EXPERIMENT DETAILS
F.1 DATA PREPROCESSING
The continuous features Adult are: Age, fnlwgt, capital-gain, capital-loss, hours-per-weei and education-num. The categorical features are: work-class, education, marital-status, occupation, relationship, race, sex, native-country. The detailed descriptions be found in Dua & Graff (2177). We remove fnlwgt, education, nat i ve-countryy from the features. race and sex are considered protected attributes and they not included in feature vectors for classification. race is treated as binary attribute: White and non-White. We remove any data-point with missing entry and end up having 45222 data-points.
F.2
FAIR METRIC
To learn the sensitive subspace, we perform logistic regression for race and sex on other features, and use the weight vectors as the vectors spanning the sensitive subspace (H). The fair metric is then obtained as
(x1, = [I(I -1l)a1 -22ll2-
F.3 HYPERPARAMETERS AND TRAINING
For each model, 10 random train/test splits of the dataset is used, where we use 80% data for training purpose. All compared methods are adjusted to account for class imbalance during training.
F.3.1 BASELINE AND PROJECT
Baseline is the obtained by fitting layer fully connected neural network with 50 neurons for the hidden layer. It doesn't I enforce any fairness for the model. Project also uses similar architecture, except pre-processing layer for projecting out sensitive subspace from features. So, Project model simple and naive way enforce fairness. For both the models same parameters are involved: tearning_rate for step size for Adam optimizer, batch_size for mini-batch size at training time, and rum_stepp for number of training steps to be performed. We present the choice of hyperparameters in Table
F.3.2 SENSR
Codes for SenSR YYurochkin al. 2020) is provided with submission with a demonstration for fitting the model, where the choice of hyperparameters are provided.
F.3.3 REDUCTION
We provide codes for reduction (Agarwal al. 2018) approach. We also provide a demonstration for fitting reduction model with the choice of hyperparameters for this experiment. The codes can also be found https: github...b//gg///gg com/ fa www.raaarraaaaaaaaaaaaaaaaaaaaal fairlearn We used Equalized Odds fairness constraint (Hardt et al. 2016) with constraints violation tolerance parameter = 0.03.
F.4 LOWER BOUND AND TESTING
To calculate the lower bounds use Algorithm The loss & is the logistic loss. Test data is provided as an input, whereas the fair metric is also learnt from the test data. For each the models we choose regularizer À = 50, number of steps T 500 and step size e 0.01.
17

---

Published as a conference paper at ICLR 2021
Table 3: Full results ADULT data over 10 experiment repetitions
Baseline
Project
Reduction
SenSR
bal-ace AQD
0.817=0.007 -0.151+00006
0.825+000003
0.800++0.005
0.765+-0.012
-0.147==0.015
0.001++0.021
-0.074++0.033
gen
AOD race
-0.061+00005
-0.053+0.015
-0.027+00013
-0.048++00008
3.676=22114
1.660-00.355
5.712+42.264
1.021+0.008
Entropy loss
reject-prop
1.0
0.9
1.0
0.0
T reject-prop
2.352
1.800:10.884
3.245
1.81400.041
0-1 loss
1.0
0.8
1.0
0.0
F.5
COMPARISON METRICS
Let be the set of classes. Let Y and Y be the observed and predicted label for data-point, respectively. The balanced accuracy is defined as
Performance
Balanced Acc
Σ Ep - =c-Y ccY= =c) CEC
[C]
Group fairness Let G be the protected attribute taking values in (0, 1}. The average odds difference (AOD) (Bellamy et al. 2018) for group G is defined as
AODG 2 [P( 1|Y 1,G = -) 1|Y 1,G=0))
+ (P(Ý = 0, -)
P(P = 1|Y = 0, G 0))
F.6
FULL TABLE
In Table 3 we present extended results the Adult t experiment with standard deviations computed from 10 experiment repetitions.
G COMPAS EXPERIMENT
In COMPAS recidivism prediction dataset (Larson al., 2016) the task is predict whether criminal defendant would recidivate within two years. We consider race (Caucasian or not- Caucasian) and sex (binary) the sensitive attributes. The features in COMPAS are: sex, race, priors_count age_cat= 25 to 45, age_cat= Greater than 45, age_cat= Less than 25, and
pripr_rooum is standardized.
As before we perform testing on four classifiers: baseline NN, group fairness Reductions (Agarwal algorithm and a basic
al. 2018) algorithm, individual fairness SenSR (Yurochkin et al. 2020) " subspace. Baseline and Project algorithm that pre-processes the data by projecting out the "senstive" Project have same architecture and parameters as in the experiment with Adult t dataset. For SenSR fair metric and Project we use train data to learn the "senstive" subspace. A further detail for choice of parameters provided in the code. For Reduction we used Equalized Odds fairness constraint 0.16.
(ardd et al. 2016) with constraints violation tolerance parameter
All methods are trained account for class imbalance in the data and we report test balanced accuracy summarized in Table 4 We
performance measure. Results of the 10 experiment repetitions compare group fairness using average odds difference (AOD) (Bellamy et al. 2018 for gender and race. Significance level for the null hypothesis rejection is 0.05 and 8 1.25.
Baseline exhibits clear violations of both individual (test is rejected with proportion 1) and group fairesss (both AODs are big in terms of absolute magnitude). Reductions method achieves significant group fairness improvements, but is individually unfair. Simple pre-pre pro-crocssiing is more efficient (comparing to the Adult experiment) with rejection proportion of 0.2. SenSR is the most effective
18

---

Published as a conference paper at ICLR 2021
Table 4: Results COMPAS data 10 experiment repetitions
Balanced Acc
AOD gen
AOD race
Tp
Rejection Prop
Baseline
0.675--0.013
0.208+0.001
0.260++0.026
2.385+002662
1.0
Project
0.641+0.011
0.039
0.227+0.0221
1.161+0.145
0.2
Reduction
0.652+10.012
-0.01410.054
0.037=000339
1.763110069
1.0
SenSR
0.64011.0022
0.046=1.031
0.237
1.09810.001
0.0
and our test fails to reject its individual fairness in all experiment repetitions. Examining the trade- off between individual and group fairness, we see that both SenSR and Reductions improve all fairness metrics in comparison to the baseline. However, improvement of individual fairness with Reductions marginal. SenSR provides a sizeable improvement of gender AOD, but only a marginal improvement of race AOD.
19


Reviews:
[{"review_id": "twqwvfTQeF6", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "The paper introduces a framework to statistically test whether a given model is individually fair or not. In particular, given a model, a distance metric over individuals, and a data point z, the authors propose an algorithm that finds a new data point z' such that z' is similar to z but their corresponding losses are different under the model -- if the model is not individually fair. They provide experimental results to show how their proposed method can detect unfairness in practice.\n\nI think the paper tackles an interesting problem and has nice results, both theoretically and experimentally. My major concern about this paper is a fundamental one: what do you exactly mean by \"individual fairness\"? I think there should be a formal definition for the fairness notion you have in mind. According to the Individual Fairness notion of Dwork et al., even one couple of similar examples on which the given model performs differently constitutes unfairness. But it looks like the fairness notion in this paper requires that *on average over the input data distribution* the model is treating similar individuals similarly which is different/weaker than the notion proposed by Dwork et al.. Please clarify if I'm missing something, or else formally define the fairness notion you used in this work.\n\nOther comments which are mostly about the technical development early on in the paper that I find hard to follow:\n\n-I don't quite understand Eq. 2.2 and how it is solving an individually fair learning problem. Isn't that just the maximum expected loss on distributions that are epsilon far from the empirical distribution? If so, how does this help with fairness? Should W(P,P_n) be defined somewhere?\n\n-Also, how is the dual problem obtained in Eq. 2.3? The authors say “it is known” but I think this requires more explanation/derivation.\n\n-In Eq. 2.4, the function \\ell_\\lambda^c is defined as getting f(x_i) (a label) as input, but looking at the right hand side of the equation, this function actually depends on x_i itself, not f(x_i).\n\n-How is the gradient flow attack related to the dual problem in Eq. 2.3 and 2.4? What happened to “epsilon” in this continuous formulation? It looks like that the primary objective now is to solve Eq. 2.4, and not the actual dual problem in 2.3, right? If that’s the case then what happened to primal and dual problems?\n\n-How should one pick the stopping time T in Eq. 2.6 and how that affects the proposed method for finding the unfair map? Shouldn’t there be a theoretical statement about X(T), or the unfair map?\n\nOverall I found section 2 of the paper very confusing. I will raise my score if the issues raised above are addressed.", "extra_scores": {}, "extra_text": {}}, {"review_id": "4pohPhBBts2", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper proposes a test to determine whether an ML model violates individual fairness. The main contribution beyond existing work is that this method allows for continuous feature spaces.\n\nConceptually, this paper rests on the \"gradient flow attack,\" which produces a mapping that, given an example, produces another example which violates the inviddual fairness constraint. Thus, given a distribution, one can compute the change in loss between the original distribution and the mapped distribution. The ratio of these quantities is what the authors use for their hypothesis testing problem: is it below a the limit of tolerance or not?\n\nFor the most part, the paper is farily well-written, though it gets a little more difficult to understand towards the end. The basic premise is interesting -- using a gradient flow attack to discover pairs of elements that are similar but have different predicted outcomes.\n\nI don't fully understand the motivation behind the loss ratio statistic. Why compare $\\ell(f(\\Phi(x, y)), y)$ and $\\ell(f(x), y)$ instead of simply $f(\\Phi(x, y))$ and $f(x)$? Does this become very sensitive when $\\ell(f(x), y)$ is close to 0? If so, then it seems as though worse models might more easily pass the test, since the denominator of the loss ratio would generally be larger. I think the gradient flow attack is promising here, but I'm not convinced that this is the right test to run.\n\nI'm not completely convinced by the claim that this test is interpretable: while the authors point to the 4/5 rule as a measure of impact, the loss ratio proposed here is clearly measuring something quite different from what a disparate impact test would traditionally measure. I don't see this as making the test results interpretable.\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "0c6451Ms2Ad", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper focuses on detecting \"individual unfairness\" in supervised learning.\n\nThe main contributions are:\n1.  A method to generate \"adversarial\" examples, that is, the examples that are very close to the original input, but get a very different outcome. An optimization problem is used formulated by leveraging the DRO framework. The authors then point out the difficulty in solving the problem (specially with continuous features) and propose an ODE based solution to find the adversarial examples.\n2. After finding the adversarial examples, a hypothesis testing framework is proposed to test the model for individual unfairness. The main idea here to compute the mean and variance of the test statistic on a given set of data points and then construct the confidence intervals using the Normality assumption.\n\nOn a high level, the idea of testing for individual unfairness is an interesting one, specially given that there aren't many metrics of it individual unfairness out there. However, it feels like many important design choices are not very clear. For these reasons, this reviewer is split between a weak accept and a weak reject. See the detailed comments below:\n\n1. Intuitively, it seems like the need for hypothesis testing arises when one is working with a small test set (if the test set is large enough, then assuming IID samples, one could already be quite confident of the point estimate of the amount of individual unfairness as measured in Eq. 3.2). However, the paper then assumes that the distance metric is learnt from the test set. Now if the test set is already quite small, how good a metric do we expect to learn? It is not clear how to reconcile these two problems. \n\n2. How much \"interpretability\" does the hypothesis test really add? The test statistic does really provide a whole lot more interpretability on on top of the quantity measured in Eq. 3.2 (which itself it very closely related to that in Eq. 2.4). Essentially, the main insight seems to be to monitor the change in loss from an example to an adversarial version of it. So that additional benefit does the hypothesis testing bring here, specially when working with reasonably sized test sets (also, see the point about the need for hypothesis testing above)? Given that the paper does not offer any discussion into the tradeoff between type I and II errors, it is not clear that advantages does the hypothesis testing bring for us.\n\n3. Perhaps it would be worth discussing how the scale of the loss (<<0) might make the ratio in Eq. 3.2 unstable in practice.\n\n4. This reviewer is a bit confused about the Normality result derived in Theorem 3.1. True that the distribution here tends to a Normal when $n \\to \\infty$. However, with small test sets, how well does this assumption hold? If it does not, the interval constructed in Eq. 3.6 may not be very accurate. In general, an empirical analysis of the intervals as in (https://arxiv.org/pdf/2007.05124.pdf) would be a great addition to the paper.\n\n5. The paper seems to take the assumption that the distance metric specified by the user is differentiable (for solving the problem in Section 2). Is that true? It is quite possible for domain experts to specify distance metrics with discontinuities in them (e.g., if education level of x1 is higher than education level of x2, upweigh the distance by 1). Can such user-specified metrics be handled by the methods in the paper?\n\n6. This reviewer is not very sure about the usage of four-fifth rule for the hypothesis test. While I am not a legal expert, the four-fifth rule seems to apply to groups instead of individuals as suggested by the paper. Moreover, applying the four-fifth rule on well-understood and well-bounded quantities (acceptance rate of the two groups), as is done in the group fairness literature, indeed makes sense. However, applying the same ratio threshold on a quantity such as loss that can be arbitrarily high or low might not be very interpretable (also see point 3). For instance, if the original loss is very low (<<0) or very high (in the order of 10's), does it make sense to apply the ratio test. Similarly, the test might lead to very different behavior when the loss changes from say hinge loss to squared loss to logistic loss. Is this behavior indeed desirable? Some explanation here would be greatly helpful in convincing the readers of the usefulness of the ratio test. \n\n------------------\n\nPost-rebuttal comments: Thanks for the detailed answers. Many of my concerns were addressed, and I am increasing my score as a result. A follow-up thought: It would be nice to add some discussion on the runtime of the proposed framework.", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper studies how to statistically test if a given model violates the constraint of individual fairness. This is an interesting and novel problem, and the paper leverages the technique of gradient flow to identify a "witness" pair for individual fairness violation. 
During the rebuttal, the authors have addressed many concerns raised in the reviews. The author should also consider discussing the runtime and improving the exposition to resolve some of the presentation issues raised in the reviews.
Decision: Accept (Poster)