Fairness Guarantees under Demographic Shift
Authors: Stephen Giguere
Blossom Metevier
Bruno Castro da Silva
Yuriy Brun
Philip S. Thomas
Scott Niekum
Venue: ICLR 2022 Poster (2022)
Keywords: Fairness and Bias in Artificial Intelligence
Machine Learning

Abstract: Recent studies have demonstrated that using machine learning for social applications can lead to injustice in the form of racist, sexist, and otherwise unfair and discriminatory outcomes. To address this challenge, recent machine learning algorithms have been designed to limit the likelihood such unfair behaviors will occur. However, these approaches typically assume the data used for training is representative of what will be encountered once the model is deployed, thus limiting their usefulness. In particular, if certain subgroups of the population become more or less probable after the model is deployed (a phenomenon we call demographic shift), the fair-ness assurances provided by prior algorithms are often invalid. We consider the impact of demographic shift and present a class of algorithms, called Shifty algorithms, that provide high-confidence behavioral guarantees that hold under demographic shift. Shifty is the first technique of its kind and demonstrates an effective strategy for designing algorithms to overcome the challenges demographic shift poses. We evaluate Shifty-ttest, an implementation of Shifty based on Student’s 𝑡-test, and, using a real-world data set of university entrance exams and subsequent student success, show that the models output by our algorithm avoid unfair bias under demo-graphic shift, unlike existing methods. Our experiments demonstrate that our algorithm’s high-confidence fairness guarantees are valid in practice and that our algorithm is an effective tool for training models that are fair when demographic shift occurs.

Published as a conference paper at ICLR 2022
FAIRNESS GUARANTEES UNDER DEMOGRAPHIC SHIFT
Stephen Giguere Department of Computer Science, University of Texas Austin sgiguere&cs. exas edu
Blossom Metevier, Yuriy Brun, Bruno Castro da Silva, & Philip S. Thomas College Information and Computer Sciences, University Massachusetts
Scott Niekum
Department of Computer Science, University of Texas at Austin
ABSTRACT
Recent studies found that using machine learning for social applications can lead to injustice in the form of racist, sexist, and otherwise unfair and discriminatory outcomes. To address this challenge, recent machine learning algorithms have been designed to limit the likelihood such unfair behavior occurs. However, these approaches typically assume the data used for training is representative of what will be encountered in deployment, which is often untrue. In particular, if certain subgroups of the population become more or less probable in deployment (a phenomenon call demographic shift), prior work's fairness assurances often invalid. In this paper, we consider the impact of demographic shift and present a class of algorithms, called Shifty algorithms,, that provide high-con- fidence behavioral guarantees that hold under demographic shift when data from the deployment environment is unavailable during training. Sh fty, the first technique of its kind, demonstrates an effective strategy for designing algorithms to overcome demographic shift's challenges. We evaluate Shi i fty using the UCI Adult Census dataset (Kohavi and Becker] 1996). as well as real-world dataset university entrance exams and subsequent student success. We show that the learned models avoid bias under demographic shift, unlike existing methods. Our experiments demonstrate that our algorithm's 's high-confidence fairness guarantees are valid in practice and that algorithm is an effective tool for training models that are fair when demographic shift occurs.
INTRODUCTION
As machine learning (ML) algorithms continue to be used aid decisions in socially impactful applications (Angwin et al. 2016; Goodall| (0166] Olson 2011), is becoming increasingly important ensure that trained models able avoid bias and discrimination. Observations that the use of ML algorithms might have unexpected social implications, such as racial bias, have led to the creation of algorithms that provide high-confidence fairness guarantees (Thomas et al., 2019 Agarwal et al. 2018). These guarantees rely on the assumption that the data the model is trained with and the data encountered after deployment follow the same distribution. However, this assumption is false for many real-world problems (Zhuang et al. 2021). and, as we demonstrate, models often violate fairness guarantees and exhibit unfair bias when evaluated on data from a different distribution.
As an example, consider model that uses university entrance exam scores to predict subsequent success. Because student demographics, such as race or sex, can shift over time, the distribution of applicants may change between model training and deployment. As a result, even if the model trained to protect a disadvantaged group. if the learning algorithm assumes the training and deployment distributions
the same, many faimnsss guarantees will not hold (Section empirically verifies this). We refer to such distribution change as demographic shift.. Specifically, demographic shift occurs when the difference between the training and deployment distributions can be explained

---

Published as a conference paper at ICLR 2022
by shift in the marginal distribution of single random variable, such as race sex. Furthermore, demographic shift can often occur after a predictive model has been trained, so it is often the case that such shift must be accounted for without access to data from the deployment distribution.
We present Shifty, the first strategy for designing ML algorithms that provide high-confidence guarantees that one more user-specified fairness constraints will hold despite demographic shift between training and deployment without using data from the deployment environment. We design Shi fhf algorithms to work in two scenarios based on what the user knows at training time about the demographic shift: (1) the old and new demographic proportions are known, or (2) the demographic proportions are bounded in known intervals.
We evaluate Shifty on the UCI Adult Census dataset (Kohavi and Becker 1996). as well as a real-world dataset of students' college entrance exam scores and their subsequent grade point average (GPA) in the Brazilian university system (da Silva, 2019). We compare Shifty to three families of existing algorithms: Fairness Constraints (Zafar et al. 2017), does not provide fairness without guarantees, Seldonian algorithms (Thomas al. 2019) and Fairlearn (Agarwal et al. 2018), both of which provide high-confidence fairness guarantees, and RFLearn (Du and Wu 2021
Shi f allows the user to provide (one or multiple simultaneous) fairness definitions from large class appropriate to the application domain, such as demographic parity, disparate impact, equalized odds, predictive equality, and individual faireess. Unlike all prior algorithms, Shift y algorithms provide high-contidence guarantces that the learned model satisfies these fairness constraints even when deployed on a distribution different from the training one. We demonstrate empirically that models learned by previous algorithms do, at times, violate the desired properties under demographic shift, while Shi fty's models do not. If there is insufficient training data, or if the specified fairness properties are simultaneously unsatisfiable, Shi fty algorithms are designed to return no solution, but we show that this rarely happens in practice. Finally and crucially. we demonstrate empirically that, in our evaluated domain, Shifty is able to learn models that exhibit no loss of accuracy compared to the models that do not guarantee fairness, as long as sufficient training data exists.
Our main contributions are: (1) the first classification algorithms that provide high-confidence f'armees guarantees under demographic shift, (2) a constructive proof of the guarantees, and method for creating such algorithms, (3) an evaluation on real-world data, and (4) an open-source Shi implementation and a release of all our data.
BACKGROUND AND RELATED WORK
We illustrate our approach for fair classification, although the methods we propose are easily extended to other problem settings (Thomas et al.) 2019, Metevier et al.) 2019). In this setting, a data instance consists of a set of features and associated label. When considering the fairness of classifier, each instance can be augmented with a fairness altribute. This information is often not used for prediction (e.g., some laws prohibit the use of race or in hiring decisions), but is assumed to be available for determining if the classifier exhibits bias.
We denote features by X X, labels by Y V, and the fairness attribute by S E S. We assume that (X, Y, S) is sampled from some joint probability distribution defined over X' x x x S. While S generally represents categorical protected attribute, such as race or sex, our formulation does not require that S be discrete. The naïve classification setting ignores the fairness attribute, and the goal is to accurately predict the label associated with X when its true label is unknown. These predictions are generated using model, 0: X - y) A loss function, such as expected classification error, measures the quality of 0. To obtain an accurate classifier, one typically selects training algorithm, a, designed to minimize the chosen loss, and supplies it with a dataset consisting of observations sampled independently from the joint distribution that is, D = {X,, Y,, S,) where Pr(X,, Y,, S.) ;= Pr(X, Y,S) for all i E (1....n))
To assess the fairness of an algorithm, the user specifies a function, g. which accepts a model and is calibrated that g(0) > 0 if and only if 0 behaves unfairly. Typically, g depends on the fairesss attribute, S. For example, to assess if a classifier is biased based on race, g might measure the difference in the classifier's accuracy for individuals of one race compared to another.
2

---

Published as a conference paper at ICLR 2022
Importantly, g can be defined based on the particular faimess requirements of given applica- tion. Here, we consider the illustrative case where g(0) is based on conditional expected value. (Appendix C.2 extends our approach to handle more general definitions of g.) Concretely, let H := h ((x, ,,S00) define some choice of real-valued observable, let & == c(X, Y.5, 0) be some event, and let т represent real-valued tolerance. We then assume that g is defined by g(0) = E H { T. For example, if for binary classification problem, the fairness attribute is sex, and the user wants to ensure that the false-positiin rate of the model is below 20% for females, one might set g(0) E ((X) |Y=0, S=femalel
0.2. While this form of g is not flexible enough to represent many widely used notions of faimess, it illustrate our strategies for accounting for demographic shift, which can easily be applied to more sophisticated definitions (see Appendix
Given a definition for g. we say that a training algorithm, o, is fair with high confidence if
Pr (g(a(D) 20) 2 21-5,
(1)
for some confidence threshold, 8 E [0, 1J. Allowing the user to set å during training overcomes the problem that guaranteeing fairness with absolute certainty often impossible (Thomas et al. 2019).
It is possible that for some 9 provided by the user, there is no model @ that satisfies g S 0 and, consequently, no algorithm a that satisfies (I). To address this, we adopt the convention described by [Thomas et al.] (2019) and permit algorithms to return NO SOLUTION FOUND (NSF), which assumed to be fair by definition predictive model cannot be found, such algorithms are permitted to abstain from outputting an unfair predictive model, instead alerting the user that the fairness constraints could not be enforced with the required probability using the data provided. Since the trivial algorithm, a(D) NSF satisfies (I) by definition, we seek algorithms that satisfy IT) but return useful predictive models as frequently as possible, and we explicitly evaluate this consideration in our experimental designs.
is, we assume that (NSF)) 0. Intuitively, if a fair
Fair Classification under Demographic Shift: To reason about differences between the training and deployment data distributions, augment each data instance with a random variable representing a demographic attribute, denoted by T E T. The demographic attribute is often distinct from the other variables defining each observation, but does not need to be. For example, user might seek model that avoids unfair bias against individuals of a particular sex, even if the distribution of the individuals' race differs from the training distribution. In this case, S would represent the sex of an individual, while T would represent their race.
Given the demographic attribute, we let (X, S, T)) represent an instance observed during training and let (X', Y', S", S') represent an instance encountered once the model is deployed. To formalize the effect of demographic shift, we assume that the demographic attribute's marginal distribution may change between training and deployment, but that the pre- and post-shift joint distributions over the instances are otherwise identical. This can be summarized by the following two conditions, which we refer to as the demographic shift assumptions:
BIET T s.t. Pr(T = * Pr(TT =), and (x,
(2)
(3)
Because the fairness of a model that is, the value of g(0))((m)l))) implicitly depends on X, Y. and S, it follows that guarantees of faimess based on g may fail hold after the model is deployed, which corresponds to replacing these random variables with X', Y' and S' Formally, if H' h(X', (") and e = o(X', (X',Y", Y',S", 0), so that g0( E [H' unfair behavior after 0 is deployed, then the challenge presented by demographic shift is summarized by the observation that, for all training algorithms a,
measures the prevalence of
Pr (g(a(D)) S 0) 1-5 +
Pr (r(g(a((D) 50) 2 1-8.
Property A
Property B
Therefore, address the following problem:
Given a user's description of possible demographic shift that might be present between the training and deployment environments as well one more definitions of faimess, design an algorithm, a, that provides high-confidence fairness guarantees that a returned model will behave fairly once the model is deployed that is, algorithm that satisfies Property B.
Problem Statement:
3

---

Published as a conference paper at ICLR 2022
In this paper, assume the user's deseription of the demographic shift is defined by a set of upper and lower bounds on the marginal probability of each value of the demographic attribute after deployment. Specifically, the user provides an input, Q {(a,, bx) HET, encoding the assumption that Pr( E [at. be] for all & E T. However, the approach used by Shi fiy is general and can be applied for other descriptions of demographic shift as well. Given Q of this form, identify two settings in which y can be applied. In the case of known demographic shift, which occurs when the user knows the exact post-deployment distribution over the demographic attribute, the user sets ag b, = Pr(T"=t) for each t T. and Shi Ety will be guaranteed not to output unfair models under the specified deployment distribution. In the second setting, the user does not know the exact demographic shift that will occur and instead specifies non-singleton intervals for each Pr( We refer to this as the unknown demographic shift setting.
While many strategies promote fairnsss in ML models, most do not offer fairness guarantees, and none provide guarantees under demographic shift. Appendix [A] discusses existing approaches in detail. These approaches include methods based on enforcing hard constraints (Irani
Related Work:
2015), soft constraints (Zafar et al.] 2017; Smits and Kotanchek 2005), chance-constrained pro-
gramming techniques (Charnes and Cooper 1959 Miller and Wagner 1965 Prékopa 1970), or
by pre- or post- post-procsssing training dataset and model predictions (Verma et al. 2021 Salimi et al.
2019 Awasthi et al.] 2020). The closest approaches to ours are Seldonian algorithms (Thomas et al. 2019), which allow the user to specify the fairness definition and provide high-confidence guarantees- that is, they satisfy Property A. Various approaches have been proposed to promote fairness in under particular types of distribution that differ from demographic shift (Lipton et al. 2018), such as concept shift (Schumann et al.) 2019), label shift and label bias (Dail 2020p, and prior probability shift (Biswas and Mukherjee| 2021). The most similar problem setting to demographic shift is covariate shift, which occurs when the distribution of fairness attributes and feature vectors changes between training and deployment, but the conditional distribution over labels is unchanged. In addition to the differences between covariate shift and demographic shift (see Appendix (A). the approaches that overcome covariate shift not proven to satisfy Property B and, unlike Shifty algorithms, require access to either data from the deployment distribution or a complete causal model of the problem setting (Rezaei et al., 2021 Coston al. 2019 Singh et al. 2021). One exception to this is RFLearn, which promotes fair outcomes under covariate shift without access to data from the deployment environment, but does not provide fairness guarantees (Du and Wu 2021).
3 METHODOLOGY
Candidate Selection arg ((0, D.)
Faimess Test
0
An overview of Shifty is shown in Figure [ Motivated by the design principles of previ- ous Seldonian algorithms (Thomas et al. 2019), which are effective at designing algorithms that satisfy Property A, Shifty algorithms consist of three core components: data partitioning, candidate selection, and fairness test. First, the data partitioning step splits the input dataset into two parts, which are used to perform the candidate selection and fairness test steps, re- spectively (see Appendix C.T). Next, candi- date model is trained. In practice, this can be performed using any existing classification al- gorithm, as the candidate selection step is not responsible for establishing the fairness guaran- tees Shi Ety provides. Once a candidate model is found, Shi fty performs fairness test by computing high-confidence upper bound on the prevalence of unfair behavior when the can- didate model is deployed in an environment af- fected by the demographic shift described by Q. If this high-confidence upper bound is below zero, the candidate model is likely to behave fairly once deployed, and the candidate is re-
HCUB g')).
S
(g. 8)
6. or NSF
Figure 1: Shifty accepts training data, D, one more fairness specifications (cach consisting of a definition of unfair behavior, 9. and tolerance, 8), and a description of possible demographic shifts, Q. It first partitions D into D, and Dy. and uses De to select a candidate model, 0.. Then, it uses Q and D, compute (1- -probbiiiyyyyl high- confidence upper bound (HCUB) on the value of g(O.) after deployment, for each fairness definition. If these upper bounds are below zero, Shi fty returns fz. and otherwise returns NSF
Algorithm 1 Shifty (D.g.8. Q)
1: De. Dy + Partition(D)
2: 0. + TrainCanddddtee(
Q)
3: u 4- HighConfUB(Onr, D,, Q)
4: return f if u < else NSF
4

---

Published as a conference paper at ICLR 2022
tumnd.. However, if the value of the high-confidence upper bound is greater than zero, then Shi y cannot show that the candidate model will behave fairly with the required confidence, and returns NSF instead. Because Shifty only returns candidate models if they can be shown to be fair with high confidence on the demographic-shifted deployment distribution, it is guaranteed to satisfy Property B.
Algorithm| I prresents high-level pseudocode for classification algorithms that provide high-confidence faimnsss guarantees under demographic shift. TrainCandi date implements the candidate selec- tion step, and Hi Hign fUB implements the high-confidence upper bound on g' (0.)) that is used to
determine the output of the algorithm and to establish its theoretical guarantees. In the following sections, we describe the candidate selection and fairness test steps detail. Because is the fairnsss test that causes Shi Shifty to satisfy Property B, we outline this component first.
3.1 THE SHIFTY FAIRNESS TEST
Given a candidate model, Oz- Shi fty's fairness test computes a (1-6)-confidence upper bound on g' g((e), which measures the prevalence of unfair behavior once 0g is deployed. Therefore, the primary challenge associated with designing an algorithm that satisfies Property B is computing a valid high-confidence upper bound on g' (0z) given Q, the description of the possible demographic distributions that might be encountered upon deployment.
Here, we propose strategy for computing tigh-confidence upper bounds on g' (02), starting with the simpler case in which the exact demographic shift is known and then extending this approach to the case in which the shift unknown. In both settings, we show how compute these bounds using ap- propriate confidence intervals. Our strategy is general and can be applied starting with many different confidence intervals. For illustrative purposes, we derive bounds based on inversion of the Student's t-test (Student 1908), leading to an implementation of Shifty which we call Shi Importantly, our use of the Student's 's t-test implies that the resulting high-confidence upper bounds only hold exactly if Pr(H' (g) is a normal distribution.
3.1.1 KNOWN DEMOGRAPHIC SHIFT
To begin, we consider the task of assessing unfair behavior when there is no demographic shift. Given n i.idd samples {(H, &,) ) where H, h(X,, S,, f) and &, c(X,, Y, S, f), one can derive Uttest. a function that computes a high-confidence upper bound on E[H[E), by inverting the commonly-used Student's t- Test (Student 1908):
Pr [[ S Uctest (g. D,0,8) 1-5.
Specifically, if I5 are the indices of the samples for which & True and N: [Tg]. then
o (gg, D.0)
ULtest Dg,
"HH, VET
6,N,-11
NE
VNg
where 61-6,N5-1 is the 1-6 quantile of the Student's distribution with N₂ degrees of freedom, and a computes the sample standard deviation using Bessel's correction. As (0) E H[g] т, follows that in the absence of demographic shift, Property A is satisfied if algorithm a only returns models satisfying ULtest (g. D, 6) T S O. and otherwise returns NSF.
To provide fairness guarantees that hold under demographic shift, we require strategy for testing whether or not g0) < with high probability, where g0) = E| [']] -. However, H' and g defined with respect to the demographic- shifted distribution, for which samples are available. Thus, we seek new random variable, H. that can be computed from X, Y, and S, but which satisfies E [LA ['H")''). Under the demographic shift assumptions, the reweighted variable defined by स = (T) H satisfies these requirements, where Φ is an importance weight derived in Appendix B
Pr(T"=t(E') Pr(T=11E) Pr(T=(() Σ P(GTTT
Pr(E(T=t)
((1)
(5)
PET
for all t E T. Specifically, (TT) acts as a scaling factor that reweights samples obtained during training that their sample mean is unbiased estimator of E(H' shown by Theorem
5

---

Published as a conference paper at ICLR 2022
Theorem 1. Assume that Pr(T=t) 2 for all t T. the demographic shift properties hold, then the random variable H = ( satisfies E[HT[(] EE("'(""), where is defined by ()) Proof.
See Appendix B
Because H is defined with respect to pre-shift random variables, it possible to generate i.i.d. samples of H during training, even when no samples from the deployment distribution are available. In particular, set of i.i.d. observations of H is obtained by computing {H, (Hs), where each H; d(Ti)h((, ,,, Yi, Using (Hi).e:. we apply the inversion of the Student's t-test to derive Üctost (g, 0)0,6) which satisfies Pr(E[[][] I Ütreat (g. (2,,0)) > 1-ô. Specifically, if à denotes the sample standard deviation of the reweighted observations, (Hi).ez; then
8gg, D. VNE
(g. = Ne
Σ TE
H
(6)
Since E[H = E[H by Theorem I it follows that Üttes: is also a high-confidence upper bound suitable for assessing fairness after demographic shift:
Pr E [E[A|S] S Üttest (g. D,0,6) = Pr (E(H)S) S Ütrest (,,
1-6. (7)
it follows that g0) < 0 with high confidence if Uttest (g, D,0,8) - s O, where each H, implicitly depends 9 by the definition, H, = (TT,)((X, S,, From 77. is clear that if the pre-shift conditionals, Pr({(T=t) and Pr(T--(E). can be computed from the training data for all & T, and if the post-shift demo- graphic marginals, Pr( are provided by the user during training, then (1-o)-confidence upper bound g0(0) can be computed even when data from the post-shift distribution unavailable.
Recalling that (0) = E[H
3.1.2 UNKNOWN DEMOGRAPHIC SHIFT
It is often unrealistic to assume that the post-shift marginal distribution is known exactly during training. To address this, we consider the setting in which the user provides a set, Q = (at, be) heT. that contains non-empty intervals describing marginal distributions over T that might be encountered after deployment. Given Q, we compute high-confidence upper bounds on g (0) by determining the largest value of the high-confidence upper bound attained for any q E Q.
First, we parameterize the high-confidence upper bound in 7 to explicitly depend on a particu-
lar choice of post-shift demographic distribution, Formally, we define ULees: (g. D, 0, 8; q) by replacing all occurrences of (Ti) in (6) with (TT; q). given
Pr(E/T=t)q
(t: g) = Pr(T=t(() ΣveT Pr(f(T==')a''
(8)
where a: = Pr(T'=t) for one possible demographic-shiffe
demographic distribution. While the true post-shift marginal distribution, q², is assumed to be unknown, it is clear that if g" Q, then Üttest (g, D,0,0;001
supgee Üttest (g. D, 0, 6). It follows that,
Pr E E(H S sup Ücreat (g. D, 0,0,8:01 8:4) > Pr E[H''E S Üttest D.0, 2 5- qE@
Consequently, if g0)))= == E - then an algorithm, a, can be designed to satisfy Prop- erty B by following Algorithm and defining the fairness test to only return models when s Uttest (g, 0,0, - O. We propose to use a numerical optimizer to approximate the supremum of Üttest over E Q. In our implementations, we use simplicial homology optimization (Endres et al.] 2018), which converges the global optima of non-smooth functions subject to equality and inequality constraints such those defined by the condition g Q.
3.2 CANDIDATE SELECTION
Because is ultimately the fairness test that causes Shifty Ety to satisfy Property B, candidate selection can be implemented using any procedure for training classifier without impacting the theoretical

---

Published as a conference paper at ICLR 2022
provided by Shi yty. However, it is advantageous to select candidate model that appears behave fairly. If model accuracy is correlated with unfair behavior, a candidate selection procedure that solely optimizes accuracy will tend to select models that will fail the faimess test. To mitigate this, we perform candidate selection by minimizing a loss consisting of two terms: one that estimates the worst-case classification error the deployment distribution, and another that penalizes models that appear to be unfair. Specifically, if L[-] denotes the indicator function that returns 1 if its argument is true and 0 otherwise, then the candidate model is found by minimizing,
fthi (g. De: 8, 8; 2) Error 2) + Penalty(g D., 0,8; 2),
(9)
where Error 0; Q) estimates the wort case classification error using Theorem
Error(De,
inf qea |Del
Σ
[[(=))u))(())
(a.g.))E
and Penalty(g Do,0, 2) penalizes models that are likely to be unfair after deployment,
Penalty(s, 0,8; = max 0, sup Ütcest (g. Do. 0, 0,)0))
4 EVALUATION
We evaluate the fairness and performance of Shi fty-ttest, Shi Shifty fty algorithm based the results derived in Section 3 Specifically, Shi fty-ttest. which is designed according to Algorithm where the subroutine TrainCandidate minimizes (9). and HighConfUE computes
s Üttest (g, D, ó; - Additional implementation details are provided in Appendix C
Our evaluation answers three central research questions (RQ). [RQI] In practice, do the models trained using Shifty-teest or prior approaches adhere to nigh-probability fairness guarantees under demographic shift? [RQ2] Is Shi Shifty-ttess able to train models whose accuracy is comparable to those produced by prior approaches that do not account for demographic shift? [RQ3] Does Shifty-ttet avoid returning NSF when reasonably sized training datasets are available?
Answering these questions requires multiple pairs of datasets sampled from the same distribution and exhibiting consistent demographic shift. We generate multiple training and deployment datasets by resampling from fixed population using known distributions. This ensures that failures- instances in which algorithm returns unfair models with larger frequency than guaranteed- are properly attributed to a failure of the algorithm instcad of a violation of the user's ''''s assumptions on the demographic shift. In addition, knowledge of the training and deployment distributions used to compute exact values for accuracy, g g(),, and g' (0) during evaluation. We uniformly sample training datasets from the population, train models using each algorithm, and evaluate fairness after deployment by using a new distribution over the population that satisfies the user's assumptions about the demographic shift. We conducted experiments using using two datasets, described below.
be
UCI Adult Census Dataset: This dataset includes various features, including race and sex, describing 48842 individuals taken during the 1994 US census (Kohavi and Becker 1996). Specifically, we consider the subset of the dataset corresponding to black or white individuals. Using this dataset, we train classifiers to predict whether or not an individual earns above $50,000 each year. To assess fairness under demographic shift, we define the fairnsss attribute, S, to be the race of each individual, and define the demographic shift to be over T,, the sex of each individual.
UFRGS Entrance Exam and GPA Dataset: This dataset describes academic records for 43,303 students from a university in Brazil (da Silva 2019). For each student, the dataset includes a vector of entrance exam scores, binary label representing if the student's 's GPA, between 0 and 4.0, was above 3.0, and labels for the student's 's race and sex, which we treat as the demographic attribute and the fairness attribute, respectively. We discuss the results of these experiments in Appendix
We use Shifty- esst Seldonian algorithms, Fairlearn, Fairness Constraints, and RFLearn to enforce disparate impact and demographic parity constraints (see Appendix D.2)p Importantly, while Fairleam was not designed to avoid disparate impact, and Fairness Constraints was not designed to enforce disparate impact or demographic parity, we include them for illustrative purposes.
7

---

Published as a conference paper at ICLR 2022
(a) Disparate Impact
Py/to err.oo0uttoo.. (UUD)
1.00
Accuner
(Dhigiaa)
Falure Rute
(Origial)
100%
0.75
0%
10K
20K
30K
20K
SUK
<0k
0:25
0.50
Acrnney
(Duployed)
Training Samples
Faiure Rate
[Dugloped]
100%
Training Samples
0.00
0%
10K
20K
30K
40K
50K
10K
20K
30K
40K
b0K
10K
20K
30K
40K
30K
Trining Samples
Training Samples
Training Samples
(b) Demographic Parity
Pc(j0 300000031000 FD300
1
Accurity
(Grignal)
80%
Faikur Rate
(Crggnal)
0.75
75%
0:25
0.30
Accuraty
(Duployed)
10K
20K
Training Samples
30K
40K
S0K
Fallur Rate
(Duployod)
100%
10K
X0K
Training Samples
30K
40K
50K
0%
10K
20K
30K
40K
50K
10K
20K
30K
40K
50K
13K
23K
30K
40K
50K
Training Samples
Training Samples
Training Samples
Shilly
RFLearn
Soldonian
Quas Sukd-SSk
Fairnes Consirainis
Faitharnn
Figure 2: Results using the UCI Adult Census dataset under known demographic shift. For the experiments using disparate impact, RFLearn, Fairness Constraints, and Fairlearn all produce failure rates of 100% before and after deployment. In the experiments using demographic parity impact, RFLearn and Fairness Constraints both produce failure rates of 100% before and after deployment.
4.1 EXPERIMENTS: KNOWN DEMOGRAPHIC SHIFT
To assess the impact of demographic shift on the fairness, we simulated a single illustrative example demographic shift shown in Figure of Appendix [D3] For each experiment, we conducted 25 trials while varying the amount of training data in order to identify dependencies on the training dataset's size. For each trial, we uniformly sampled training dataset and trained models using each algorithm. After training, we recorded whether each algorithm produced a model or NSF, as well as the average accuracy and prevalence of unfair behavior for each trained model both before and after deployment.
Figure 2 shows the results of these experiments using the UCI Adult Census dataset. For each definition of fairness, the leftmost plot shows the probability with which each algorithm returns NSF. To the right are two rows of plots showing evaluations of each algorithm on the training and deployment distributions, respectively. Within each row, the left plot displays the accuracy of models returned by each algorithm when trained using various amounts of data. The right plot in each row displays the frequency with which each algorithm returns an unfair model, which we call the failure rate. The horizontal dashed line shows the tolerance for unfair outcomes, 8=0.05, set when training Shifty-ttest and Seldonian algorithms. Finally, shaded regions denote standard error bars.
Our experiments confirm that Shi Et algorithms effectively avoid unfair behavior after demographic after demographic shift
shift while prior algorithms do not. The failure rates of Shifty occurs (bottom right plots in Figure 2 always below the tolerance set during training. However, while Seldonian algorithms were fair during training, they, along with the other baselines, frequently violate that fairness constraint after deployment. Interestingly, despite being designed promote fairness with respect to demographic parity under covariate shift, RFLearn consistently violated the demographic parity constraints both before and after deployment. We found that the average value of (0) for RFLearn models was 0.0175, which highlights the observation that many fair classification algorithms find models that are reasonably fair, but do not provide righ-confidence guarantees.
Next, we found that Shi mrifty-ttest provided guarantees of fairness with only a minor loss in accuracy compared to the baselines that do not provide any fairness guarantees. The plots in the middle column of Figure show show that Shifty-ttest produced models that achieved the same accuracy as those trained using standard Seldonian algorithms, with performance approaching that of the most accurate baselines for sufficiently large training datasets. This pattern is consistent with the results of our additional experiments in Appendix E.I which show that for fairness constraints that not excessively strict, Shifty-tt required slightly more training data than standard Seldonian algorithms
returns models with competitive accuracy. Finally,
found that Shi to consistently avoid returning NSF (left plots in Figure 2
8

---

Published as a conference paper at ICLR 2022
(a) Disparate Impact
Pvjto ewr.000uttt... (OUD)
1.00
Accuner
(Chignna)
Falure Rute (Originl)
100%
0.75
70%
0%
0:35
0:30
Acruneyy
(Duyloyed)
80%
Training Samples
Faiture Rate
[Duployedd
100%
Training Samples
0.00
0%
20K
40K
60K
20K
40K
b0K
20K
40k
50K
Trining Samples
Training Samples
Training Samples
(b) Demographic Parity
Pc(j0 20000003100 FD300
1
Accunaty
(Grijnal)
80%
Faikur Rate
(Crggna))
0.75
75%
0:25
0.30
Accuraay
(Duployel)
28%
Training Samplas
60K
Fallue Rate
(Duployod)
100%
Teaining Samples
50K
0%
40K
60K
40K
62K
40k
50K
Training Samples
Training Samples
Training Samples
Shinly
Saldonian
Q Qulo-inni
Fairmes Constrainis
Fairbarn
RFLearn
Figure 3: Results when enforcing fairness constraints using the UCI Adult Census dataset under unknown demographic shift. Note that for the experiments using disparate impact, RFLearn, Fairness Constraints, and Fairlearn all produce failure rates of 100% both before and after deployment.
4.2 EXPERIMENTS: UNKNOWN DEMOGRAPHII SIIFT
Next, conduct experiments assuming that the user has provided upper and lower bounds on the marginal probability of encountering individuals of each race after deployment instead of specifying the shift exactly. The example bounds used in our experiments
discussed in Appendix [D.3] Using these bounds as the specification for demographic shift, we trained models using the same procedure as described in Section 4.1 To evaluate each model's performance after demographic shift, we performed a worst-case analysis and selected the deployment distribution over the population to satisfy the user's assumptions, but otherwise maximize the prevalence of unfair behavior when using that model to generate predictions (See Appendix [DI)). As in Section 4.1 we report results for each experiment using five plots that show the probability of each algorithm returning NSF, as well as average accuracy and the failure rate of each al algorithm before and after deployment.
Figure J results for disparate impact and demographic parity (additional results are provided in Appendix [E). which confirm that thiffy-ttee provides guarantees of fair behavior that hold when the post-shift demographic distribution is not exactly known. While Seldonian algorithms are fair during training (Figure E top right), they often unfair after demographic shift. Furthermore, Shifty-tted generally produced models that achieved similar accuracy as those trained existing algorithms that do not satisfy Property B, although some fairness constraints were as harder satisfy and caused Shi fty-ttest to frequently return NSF (see Appendix
E. These results indicate that Shi way-yyyttte effective when fairness guarantees critical, and is capable of training models that obtain comparable accuracy to those trained using unfair basclines.
5 CONCLUSION
We proposed Shi thifty, strategy for designing classification algorithms that provide high-confidence fairness guarantees that hold when the distribution of demographics changes between training and deployment. This setting poses significant challenges for existing fair ML algorithms, as the fairness guarantees they provide generally assume a constant data distribution. In contrast, Shi Shifty algorithms allow the proportions of demographics to change after training, provided the user has information describing this change. Shi fty algorithms can be used when the new demographic proportions known, or when these proportions are bounded in known intervals. Finally, evaluated Shifty-ttest, an implementation of Shift based on the Student's s t-test, and found that the faimess guarantees it provides empirically valid, wherein models trained using existing fair algorithms consistently produced unfair outcomes.

---

Published as a conference paper at ICLR 2022
ACKNOWLEDGMENTS
This work is supported by the National Science Foundation under grants no. CCF-1763423 and CCF-2018372, by the DEVCOM Army Research Laboratory under Cooperative Agreement W911NF- 17-2-0196 (ARL IoBT CRA), and by Adobe, Google Research, Kosa.ai, and Meta Research.
ETHICS STATEMENT
The primary goal of this research is identify and overcome practical challenges, namely demo- graphic shift, that might cause current algorithms to produce unfair outcomes. Our contributions provide tools needed for data scientists and ML practitioners to use ML in conscientious, ethical ways. However, we note that, when applying algorithms such as Shifty: , it is important to carefully select the definition of unfair behavior be appropriate for the problem hand. While we evaluate Shifty using five standard definitions of unfair behavior for illustration, many definitions have been proposed and studied (Verma and Rubin 2018), some which cannot be simultaneously enforced (Chouldechova 2017 Corbett-Davies et al., 2017 Kleinberg et al., 2017). Consequently, while Shifty offers a valuable tool for enforcing fairness constraints, ML practitioners should carefully study their target application, idcally working with domain experts and stakeholders, to ensure that the definitions they select mcaningfully capture the unfair behaviors they wish to avoid.
Next, note that the fairness guarantees provided by Shifty may fail to hold if one more assumptions made by the algorithm do not hold. Most notably, if the demographic shift assumptions, (2) and (3). do not hold for the user's choice of demographic attribute T, then the guarantees provided by Shi Shifty may not hold in practice. Similarly, the user's specification of possible demographic shift, defined by the input Q, does not accurately represent the demographic shift that occurs, then the guarantees provided by our algorithms may be invalidated. Thus, it is important that ML practitioners study the application domain order to ensure that the inputs they supply to Shifty are appropriate.
test is based on inversion of the Student's t-test, which only holds exactly the observations, H, are not normal. While this approximation error becomes smaller as more samples are used for training, the high-confidence guarantees provided by Shyfty may not hold with 1 probability when trained on very small datasets. Therefore, in applications for which very few training observations are available, ML practitioners should employ Shi fty algorithms based on other, non-approximate confidence intervals.
Finally,
REPRODUCIBILITY STATEMENT
To support efforts to reproduce our results, all code and data used in this paper will be made pub- licly available upon publication. Proofs of our theoretical results can be found in Appendix B and
implementation details for our algorithms can be found in Section 3 and Appendix C In addition, experimental details can be found in Section 4 full descriptions of the fairness definitions we tested are shown in Appendix D.2 and additional experimental details and results are included in Appendix DD and Appendix EL, respectively. The UCI Adult Census dataset is available for down- load from the UCI Machine Learning Repository (Kohavi and Becker 1996), and the UFRGS Entrance Exam and GPA dataset is available at Intttts:: /tt:::/dooooie org 10. 7910 /035FF (da Silva, 2019). Code for reproducing our experiments can be found at http::httttttcccccoottt -eweeesunndd--eeee www.honggraaiii--hhaaaaaa-
doi
thub wub.bcc... com/ which includes in- structions for adding the UCI Adult Census and UFRGS GPA datasets to the codebase.
aagiquere/S htt///aarrsssuaaaaaaaaaa
REFERENCES
Alekh Agarwal, Alina Beygelzimer, Miroslav Dudík, John Langford, and Hanna Wallach. 2018. A reductions approach to fair classification. In International Conference Machine Learning (ICML), Vol. PMLR 80. Stockholm, Sweden, 60-69.
Julia Angwin, Jeff Larson, Surya Mattu, and Lauren Kirchner. 2016. Machine ProPublica (23 May 2016).
httpabllaaa.....aaa.eeeeeeoeeeee arg/article/ machine-bias-re www.-risssssseeneeeee.....ee iin.rsmmmmetti---n--iiiinnnna -nn-arrmmmal-senteeniinnnn
Bias.
10

---

Published as a conference paper at ICLR 2022
Pranjal Awasthi, Matthäus Kleindessner, and Jamie Morgenstemn 2020. Equalized odds postprocess- ing under imperfect group information. In International Conference on Artificial Intelligence and Statistics (AISTATS). Palermo, Italy.
Arpita Biswas and Suvam Mukherjee. 2021. Ensuring fairness under prior probability shifts. In Proceedings of the 2021 AAAI/ACM Conference on Al, Ethics, and Society. 414-424.
Lorenzo Bruzzone and Mattia Marconcini. 2009. Domain adaptation problems: A DASVM classifi- cation technique and circular validation strategy. IEEE Transactions Pattern Analysis and Machine Intelligence 32, 5 (2009), 770-787.
Toon Calders and Sicco Verwer. 2010. Three naive Bayes approaches for discrimination-free classification. Data Mining and Knowledge Discovery 21, 2 (2010), 277-292.
A. Charnes and W. W. Cooper. 1959. Chance-constrained programming. Management Science 6, 1 (1959), 73-79.
Alexandra Chouldechova, 2017. Fair prediction with disparate impact: A study of bias in recidivism prediction instruments. Big Data 5, 2 (2017), 153-163.
Sam Corbett-Davies, Emma Pierson, Avi Feller, Sharad Goel, and Aziz Huq. 2017. Algorithmic decision making and the cost of fairness. In ACM Conference on Knowledge Discovery and Data Mining (KDD). 797-806.
Amanda Coston, Karthikeyan Natesan Ramamurthy, Dennis Wei, Kush Varshney, Skyler Speakman, Zairah Mustahsan, and Supriyo Chakraborty, 2019. Fair transfer learning with missing protected attributes. Proceedings of the 2019 AAAI/ACM Conference on AI, Ethics, and Society. 91-98.
Bruno Castro da Silva. 2019. UFRGS Entrance Exam and GPA Data. bttps://doi.org
7910/DVN/035FMF
Jessica Dai. 2020. Label Bias, Label Shift: Fair Machine Learning with Unreliable Labels.
Wei Du and Xintao Wu. 2021. Fair and Robust Classification Under Sample Selection Bias. In Proceedings of the 30th ACM International Conference on Information & Knowledge Management. 2999-3003.
Miroslav Dudik, Steven J Phillips, and Robert E Schapire. 2006. Correcting sample selection bias in maximum entropy density estimation. In Advances in Neural Information Processing Systems. 323-330.
Cynthia Dwork, Moritz Hardt, Toniann Pitassi, Omer Reingold, and Richard Zemel. 2012. Fairness through awareness. In Innovations in Theoretical Computer Science Conference. ACM, 214-226.
Stefan C Endres, Carl Sandrock, and Walter W Focke. 2018. A simplicial homology algorithm for Lipschitz optimisation. Journal of Global Optimization 72, (2018), 181-217.
Basura Fernando, Amaury Habrard, Marc Sebban, and Tinne Tuytelaars. 2014. Subspace alignment for domain adaptation. arXiv preprint 10Xiv:1409.524) (2014).
Boqing Gong, Yuan Shi, Fei Sha, and Kristen Grauman. 2012. Geodesic flow kernel for unsupervised domain adaptation. In 2012 IEFE Conference on Computer Vision and Pattern Recognition. IEEE, 2066-2073.
Noah J. Goodall. 2016. Can you program ethics into self-driving car? IEEE Spectrum 53, 6 (June 2016), 28-58. hattps:/ 1r1/10.1109//MPPP 2016. 7473149
Ian Goodfellow, Yoshua Bengio, and Aaron Courville. 2016. Deep Learning. MIT Press.
Raghuraman Gopalan, Ruonan Li, and Rama Chellappa. 2011. Domain adaptation for object recognition: An unsupervised approach. In International Conference on Computer Vision. IEEE, 999-1006.
Griggs v. Duke Power Co. 1971. 401 U.S. 424. hattps://uupeeet last://urrreeeesttaaaaaaaa federa /us/ 40 00/s/001/42//
justia. wwnstia.com/aee. com/ cases/

---

Published as a conference paper at ICLR 2022
M. Hardt, E. Price, and N. Srebro. 2016. Equality of Opportunity in Supervised Learning. In Conference on Neural Information Processing Systems (NIPS). Barcelona, Spain, 3323-3331.
Jiayuan Huang, Arthur Gretton, Karsten Borgwardt, Bernhard Schölkopf, and Alex Smola. 2006. Correcting sample selection bias by unlabeled data. Advances in Neural Information Processing Systems 19 (2006), 601-608.
Arja John Irani. 2015. Utilizing Negative Policy Information to Accelerate Reinforcement Learning. Ph.D. Dissertation. Georgia Institute of Technology.
Jon M. Kleinberg, Sendhil Mullainathan, and Manish Raghavan. 2017. Inherent Trade-Off's in the
Fair Determination of Risk Scores. In Innovations in Theoretical Computer Science Conference (ITCS), Vol. 67. Berkeley, CA, USA, 43:1 43:23..
htips://doi. org/ 10. 4230/LIPIcs
IICS.2017.43
Ronny Kohavi and Barry Becker. 1996. Uci machine learning repository: adult data set. Avaliable: htlps://urciive ics. uci.
(1996).
Zachary C Lipton, Yu-Xiang Wang, and Alex Smola. 2018. Detecting and correcting for label shift (2018).
with black box predictors. arXiv preprint
Blossom Metevier, Stephen Giguere, Sarah Brockman, Ari Kobren, Yuriy Brun, Emma Brunskill, and Philip S Thomas. 2019. Offline Contextual Bandits with High Probability Fairness Guarantees. In Advances in Neural Information Processing Systems. 14922-14933.
L. B. Miller and H. Wagner. 1965. Chance-constraineed programming with joint constraints. Operation Research 13 (1965), 930-945.
Parmy Olson. 2011. The Algorithm That Beats Your Bank Manager. CNN Money March 15 (2011).
A. Prékopa. 1970. On probabilistic constrained programming. In Princeton Symposium on Mathe- matical Programming. 113-138.
Ashkan Rezaei, Anqi Liu, Omid Memarrast, and Brian Ziebart. 2021. Robust Fairness Under Covariate Shift. Proceedings of the AAAI Conference Artificial Intelligence 35, 11 (May 2021), 9419-9427. https:// aaai. org/ / index. php
Babak Salimi, Luke Rodriguez, Bill Howe, and Dan Suciu. 2019. Interventional Fairness: Causal
Database Repair for Algorithmic Fairness. In International Conference on Management of Data (SIGMOD). Association for Computing Machinery, Amsterdam, Netherlands, 793-810, https
(/dol.org/110.115522288888
9901
Candice Schumann, Xuezhi Wang, Alex Beutel, Jilin Chen, Hai Qian, and Ed H Chi. 2019. Transfer of machine learning fairness across domains. arXiv preprint arXiv: 0006009688888 (2019).
Harvineet Singh, Rina Singh, Vishwali Mhasawade, and Rumi Chunara. 2021. Fairness violations and mitigation under covariate shift. In Proceedings of the 2021 ACM Conference on Fairness, Accountability, and Transparency. 3-13.
Guido F Smits and Mark Kotanchek. 2005. Pareto-front exploitation in symbolic regression. In Genetic Programming Theory and Practice II. Springer, 283-299
Student. 1908. The probable error of mean. Biometrika (1908), 1-25.
Philip S. Thomas, Bruno Castro da Silva, Andrew G. Barto, Stephen Giguere, Yuriy Brun, and Emma Brunskill, 2019. Preventing undesirable behavior of intelligent machines. Science 366, 6468 (2019), 999-1004.
Sahil Verma, Michael Ernst, and René Just. 2021. Removing biased data to improve faimess and accuracy. CoRR abs/2102.03054 (2021). attps://aaxivv http://bb/2222...02 03054
Sahil Verma and Julia Rubin. 2018. Faimess definitions explained. In 2018 JEEE/ACM International Workshop Software Fairness (FairWare). IEFE, 1-7.
12

---

Published as a conference paper at ICLR 2022
Bianca Zadrozny. 2004. Learning and evaluating classifiers under sample selection bias. In Proceed- ings of the Ehenty-First International Conference on Machine learning. 114.
Muhammad Bital Zafar, Isabel Valera, Manuel Gomez Rodriguez, and Krishna P. Gummadi. 2017. Fairness constraints: Mechanisms for fair classification. In International Conference on Artificial Intelligence and Statistics (AISTATS). 797-806.
Xiang Zhang and Yann LeCun. 2017. Universum prescription: Regularization using unlabeled data. In Thirty- First AAAI Conference on Artificial Intelligence.
Fuzhen Zhuang. Zhiyuan Qi, Keyu Duan, Dongbo Xi, Yongchun Zhu, Hengshu Zhu, Hui Xiong, and
Qing He. 2021. A Comprchensive Survey on Transfer Learning. Proc. IEEE 109, 1 (2021), 43-76.
httpps:/ddat http:///............././////////
www.:/ 2020 200....0..........
Daniel Zwillinger and Stephen Kokoska. 1999. CRC standard probability and statistics tables and formuaee. CRC Press. 31 pages.
A ALTERNATIVE APPROACHES FOR ACHIEVING FAIR OUTCOMES
Designing algorithms that meet fairness requirements with high-confidence can be seen as a type of constrained optimization problem. Algorithms that enforce hard constraints search for a predictive model within feasible set of models satisfying the user's fairesss constraints (Irani 2015). Soft constraints on the objective function used to guide the search for model can achieve fairness empiri- cally (Zafar et al., 2017). and multi-objective methods can be used to satisfy multiple, potentially conflicting fairness objectives (Smits and Kotanchek (2005). Unfortunately, algorithms based on hard or soft constraints alone do not provide high- cogh-confieeecee fairness guarantees. Fair algorithms can be designed based on contncceoonstraineed programming (Charnes and Cooper 1959; Miller and Wagner 1965 Prekopa 1970). in which an objective function is optimized subject to a set of constraints. This formulation can provide high-confidence fairness guarantees but typically requires knowledge of the distribution of each variable used quantify fairness, which is often impractical. In contrast, our methods provide assurances of fair behavior without these limiting assumptions.
In our work, we consider the problem of establishing high-confidence fairness guarantees that hold under demographic shift, specifically when no samples are available from the deployment distribution. While Shift y is, our knowledge, the first to provide high-confidence guarantees of fairness in this setting, there are several existing strategies for promoting fair outcomes under various forms of distribution shift, which leverage a variety of assumptions. For example, approaches have been proposed to promote fair outcomes under concept shift, which occurs when the distribution over safety attributes and feature vectors changes between training and deployment. [Schumann et al.) (2019) derive bounds describing how well fairness properties can be transferred from a source to target domain, and use them to propose training procedures that can improve the transferability of fairness properties. While this approach could be applied to overcome demographic shift, it does not provide guarantees that the resulting models will meet specific fairness tolerances, and it assumes that data is available from the deployment distribution and therefore cannot be applied in the setting we consider. contrast to methods for overcoming concept shift, many works on promoting faimess under distribution shift assume that the shift has particular structure. For example. Dai (2020) propose a fairness-aware model for label shift and label bias, which occur when the distribution over the fairness attribute and feature vector is the same during training and after deployment, but the conditional distribution over true labels differs. Similarly, Biswas and Mukherjee (202T) propose an algorithm for promoting fair outcomes under prior probability shift, which occurs when the marginal distribution of true labels changes between training and deployment, using proportional equality to measure fairness. Unfortunately, the assumptions of label shift, label bias, and proportional equality contrary to the assumptions of demographic shift, so that these approaches cannot be applied to the problem setting we consider.
Among the problem settings considered in prior work, the most similar setting to demographic shift is covariate shift, which occurs when the distribution of faimess attributes and feature vectors changes between training and deployment, but the conditional distribution over labels is unchanged. Indeed, if, in addition to the demographic shift assumptions, the user assumes that the distribution of true labels is conditionally independent of the demographic attribute given the features and safety attributes,
13

---

Published as a conference paper at ICLR 2022
then demographic shift can be viewed as form of covariate shift. Several approaches have been proposed for promoting fair outcomes under covariate shift and various definitions of fairesss, but these approaches cannot be applied to our problem setting because they make the assumption that samples are available from the deployment distribution. Furthermone, these approaches are not proven to satisfy Property B (Rezaei al.) 2021] Coston et al.] (019)). [Singh et al. (2021) propose a training algorithm that ensures that fairness properties of the resulting model are invariant to covariate shift by exploiting a causal graph of the problem that is provided by the user. While this approach can be applied without samples from the deployment distribution, the causal graph required by the algorithm often unknown, and the algorithm does not provide faimess guarantees. Finally, Du and Wu (2021) propose an algorithm, RFLearn, that promotes fair outcomes under covariate shift without access to data from the deployment environment. While this approach does not provide fairness guarantees, and despite the differences between demographic shift and covariate shift, we include RFLearn in our experimental designs for illustration.
We propose algorithms that produce fair models following the design principles outlined by Sel- donian ML (Thomas et al., 2019) while accounting for demographic shift. Other ways to account for demographic shift incluch augmenting training data with synthetically generated variations or antagonistic examples, or explicitly regularizing the training objective using unlabeled data from the deployment distribution, which improves the models' generalization (Goodfellow et al. 2016 Zhhng and LeCun (017). However, these approaches do not tackle fairness and cannot be directly applied to provide fairness guarantees under demographic shift. the change in distribution can be addressed by a transformation of either the features or response variables, methods can learn this transformation using access data from the deployment distribution combined with assumptions, such as that the transformation is linear (Fernando et al. 2014| Gong et al.) 2012 Gopalan et al., (011), or by iteratively assigning predicted labels to unlabeled data from the deployment environment (Bruzzone and Marconcini 2009). However, such approaches are ill-suited for establishing high-confidence fairness guarantees under demographic shift.
Approaches can account for the differences between the training and deployment environments by reweighting the contribution of cach training observation according to the relative probability of encountering that observation. Such methods are effective at improving performance in classification (Zarrozny 2004 Huang et al. 2006), density estimation (Dudik et al. 2006), and regression (Huang et al., 2006). While most of these approaches focus accuracy, some have focused on safety constraints, such as fairness. Lipton et al.] (2018) proposed correcting for covariate shift by using a
reweighting scheme compute intervals a classifier's confusion rates and applying correction step based on these intervals. This approach produces empirically fair models but does not provide high-confidence guarantees. An algorithm's 's fairness can be improved by manipulating the underlying data, c.g., by removing data that violates fairness properties (Verma et al. (222)) or inserting data inferred using fairness properties (Salimi et al. 2019). These methods, however, do not provide guarantees. Fairness can also be enforced in post- procpssocssing (Awasthi et al. 2020) but, again, without guarantees.
B PROOF OF THEOREM
Theorem I Assume that Pr(T=t) 2 0 for all t T. If demographic shift properties hold, then the random variable ft = ((T) satisfies E H' [*] = E A E., where & is defined by
Proof. First, we write E[H as a sum over expected values conditioned on the value of the demographic attribute by applying the law of total probability (Zwillinger and Kokoska 1999..
E|H' = Σ E', Pr(T"=1S)
ET
Σ T PT(T' E
(Using 3
Here, the second line follows from the second demographic shift assumption which states that for
all t E T and x, v. s E X x y x S, Pr Y'=y, - ='==(["=t) = Pr(X=z, Y=y, S=s[T=t)) Next, multiply each term by (((T==(()/PP((TT/// = reorganize terms, and write the sum
14

---

Published as a conference paper at ICLR 2022
over E T as single expected value:
Pr(T-11E) Pr(T"=11')
B
=
E E T-1
Pr(T-t(()
LET
Pr(TT=t(()
E T T=
Pr()=1(()
Pr(T-((()
LET
E H(E)
where
Pr(T"-((k)) 6(1) Pr(T=t(()
Finally, we rewrite d(t) to depend on the post-shift marginal distribution, Pr(T"=t), and the pre-shift
conditional distributions, Pr(T'=t({) and Pr(C for each t T:
Pr(T"=115')
<(t) = Pr(T-t|E)
(Using Bayes' Theorem)
Pr(E))
(r()
(Using (3)
Pr(T=((E) Pr(5))
Pr(T'e))
Pr(T=t(() ΣVET Pr(E((T=='' Pr(T'=t)
Pr(E(T=t) Pr(T'=t)
(Using (3)
Pr(T==((E) Pr("'=t))
C ADDITIONAL IMPLEMENTATION DETAILS FOR SHIFTY
C.I DATA PARTITIONING
The data partitioning step ensures that the outcome of the candidate selection step is independent of the outcome of the fairness test, which is necessary to guarantee that the overall algorithm satisfies ① under demographic shift.
To illustrate the requirement for this step, consider algorithm that accepts observations, D, uses D to select a candidate model, lz. and finally uses D again to evaluate the high-confidence upper bound on g' (0,.) perform fairness test. While this algorithm might appear to be fair, is not guaranteed to satisfy Property B because the output of candidate selection, 0., is correlated with the outcome of the fairness test because the same input data, D, is used to perform both steps. Consequently, it is possible that candidate selection can consistently select models that cause the high-confidence upper bound used by the fairness test to under-estimate the value of g' (fa). By ensuring that candidate selection and the fairness test use independent sets of observations, this correlation is eliminated, causing the probability of the high-confidence upper bound failing to be no more than å as required by Property B.
of training
Finally, we note that one area of future research might consider the optimal way to split an input dataset into parts used for candidate selection, D.., and for evaluating the faimess test, D,. Specifically, increasing the size of D. improves the ability of the candidate selection step to identify models that accurate and generalize well, but reduces the size of Dj and makes the fairness test more difficult to pass. our experiments, we split the input data evenly between D. and D but we hypothesize that there may be more effective techniques for determining the optimal splitting proportion.
15

---

Published as a conference paper at ICLR 2022
C.2 ENFORCING COMPLEX FAIRNESS DEFINITIONS
In Section 3 we assume that the user-specified definition of unfair behavior, is defined by,
g = {]
(10)
However common fairness definitions such as the 80% rule (Griggs v. Duke Power Co., 1971) and equalized odds (Hardt al., 2016) do not have the same form as (10). Nonetheless, these definitions can often be described by known expressions of multiple terms, where each term is a conditional or marginal expected value. Consider, for example, the definition of bias codified by disparate impact
(Griggs v. Duke Power Co. 1971; Chouldechova 2017 Zafar et al. 2017):
(0) 0.8 min [[((x)]S=femaale E[0(X)]S-male) [[
(
This definition is clearly not of the form described by (T0;; furthermore, it is challenging to estimate because i.idd. samples of E E(((X))S=male) and E JS= cannot be simultaneously computed given a single observation. Regardless, it is possible to compute valid high-confidence upper bounds on (0)(0) by leveraging the recursive poundppropagation described by Metevier et al. (2019). Importantly, we evaluate our proposed algorithms using complex but realistic fairness definitions by leveraging this strategy, and as consequence. our results are influenced by this decision.
While we refer the reader to Metevier al. (2019) for more complete discussion of this strategy, we present a brief intuition here. First, we assume that the user's definition of can be written as,
s = 10000((0p
where each o; for i E {1,...,kk k} denotes a parameter of the joint distribution of (X, Y, S), and f is some function of l: arguments specified by the user. In our work, we assume that these parameters are each expressed as a conditional expected value analogous to (TO) and that the expression defining is provided by the user as text.
Following (Metevier et al. 2019), the expression for f is parsed into a tree structure representing the recursive application various predefined operations. To construct a high-confidence upper bound on g(0) or in this work, g²(0) we first construct a set of confidence intervals on each parameter using the methods described in Section Importantly, we apply the union bound ensure that the set of confidence intervals on the parameters hold jointly with probability 1-6. Next, these intervals are recursively propagated through the expression for S. where at each node of the computation tree, the interval for that node is computed by applying interval arithmetic, which describes the image of certain mathematical operations given intervals as their arguments. Since the root of the computation tree denotes the quantity g' (0), the result of this recursive system is interval containing the true value of g' (f) with at least probability 1 5-
A drawback of this approach is that it assumes that the intervals describing each parameter independent, which is often false when considering demographic shift. However, it is important to note that violation of this assumption does not impact the validity of the resulting confidence interval on g()) Instead, when the input parameters are not dependent, the resulting confidence interval on g'()) is larger than it would be if the dependence between each parameter were known and accounted for. For example, suppose is defined to measure bias based on sex, and consider two races. If, for individuals of one race, a certain sex is encountered much more often than other sexes, while for individuals of the second race, all sexes are encountered equally often, then a demographic shift that makes the first race more likely may cause certain parameters defining fairness to be highly correlated with others. By ignoring these dependencies, the approach presented in (Metevier et al. 2019) may produce significantly larger confidence intervals for g' g((0) compared to alternative approaches that leverage this dependency. For this reason, consider this problem to be strong candidate for future work, as it has the potential to improve the data efficiency of our methods as well as those proposed in existing work (Metevier al. 2019 Thomas al. 2019)
16

---

Published as a conference paper at ICLR 2022
D ADDITIONAL EXPERIMENTAL DESIGN DETAILS
D.1 A STRATEGY FOR SIMULATING AND EVALUATING DEMOGRAPHIC SHIFT
Here, we describe our procedure for simulating the impact of demographic shift given a fixed population dataset when the exact deployment distribution is unknown. Intuitively, after generating a training dataset, we antagonistically select a new, non-uniform distribution over the population that satisfies the user's demographic shift assumptions that is, that the marginal distribution over demographics is contained in Q Q-but but otherwise maximizes the prevalence of unfair behavior. Since the population and sampling distributions are known during evaluation, this oracle knowledge can be used to compute exact values for various statistics, such as expected classification accuracy. To make this procedure formal, let the population dataset be denoted by D Dyopi
Poop == {Ir, V/, 8,, tz)
Note that do not refer to this set using the standard notation for random variables because in our experimental context the population is treated as a fixed, non-random population. To generate random training dataset, D, we sample observations uniformly from D Dpop with replacement. Specifically, if denotes the uniform distribution over the observations in D Ppop. then training datasets defined by D {(x,, Y,, Sj, T
T where each (Xj. Sj, T2) ~
Next, we generate a new distribution over the population that satisfies the user's assumptions but otherwise maximizes the prevalence of unfair behavior for given model, which we denote by Q- However, to comply with the user's ' assumptions about the demographic shift, Q must be selected carefully. The following theorem provides the conditions that Q must satisfy to achieve this.
Theorem 2. Let P denote uniform distribution over Pop ((11, Yi, 8ú, (=));= j=1-- Assume that the demographic attribute takes values in some set T and that each demographic t E T occurs at least once in the population. Next, let each q E Q denote a marginal distribution over where qe denotes the probability of encountering demographic t. Finally, let Nyppop [x. y, f) denote the number of observations Dpop that are equal (z. y, s.t) and let Do [t] denote the number of observations that have demographic attribute equal to t. follows that Q2 defined below, is a distribution over Dop that satisfies both of the demographic shift assumptions, and has a marginal distribution over demographics that is contained in Q:
NDpop [x, U,
Q(x=z, Y=y
ND [t]
qt.
Proof. To show this result, we derive an expression for Q that has these properties by construction. First, we expand the post-shift joint distribution using the laws of conditional probability:
Q(x=r, Y=y, T-1)
Next, we apply the second demographic shift assumption:
P(X=x, T=),)
Then, we represent the conditional Y,X,Y,STTE as ratio using laws of conditional probability:
Y = P(X=x, Y=y, S=s, Q(T
P(T-1)
Because P is a uniform distribution over D Dpop. it follows that the value of YY S=s, simply the number of occurrences of (z, y, 8, in divided by the total number of samples in the population, n. Similarly. P(T=t) is equal to the number of observations that have demographic attribute equal to I, divided by n. Since we assume that each demographic observed in the population, it follows that P(T=l) > 0 for all L T. Let ND. [I., y, 8, (] denote the number of observations in Dpop equal to (x. y. s, t) and let No,.,.. [t] denote the number observations that have demographic attribute equal to t. It follows that for all observations, (I, y, s, D Prop. have
ND [x, U. 8, t
S=x, T=1)
Q(T-1).
ND pop
17

---

Published as a conference paper at ICLR 2022
Finally, we define the marginal distribution of Q over demographics to be given by q:
Q(X=,.Y=y,S-s,T-- = ND [r, y, 8, 1
D [4]
Since Q has the same conditional distribution given the demographic as by construction, satisfies the demographic shift assumptions. Furthermore, since the marginal distribution of Q demographics is defined to be given by it also satisfies the user's assumptions.
Theorem 2 shows that, given a y E 2, straightforward to construct distribution over population which satisfies the demographic shift assumptions. Therefore, to select distribution that maximizes the prevalence of unfair behavior for given model, 0, we numerically optimize g'(0) over Q using simplical homology optimization (Endres al. 2018) to determine the maximizing marginal distribution, q and then define the final distribution over Dpop using Theorem 2
Theorem can also be used to compute exact values for various statistics of interest during eval- uation, such as expected classification accuracy or the value of g(()). Consider estimating the post-deployment classification accuracy of model, given by [o{[)(()==]] If pop denotes the set of unique observations in D pop. then we have
Eq [I] E (s..ee.))DDppp pop
Y S=s T-t)
Nayap [..V...t] -1)
Σ
n[([=]y]]
NDpap 1t)
(x..
D.2 FAIRNESS DEFINITIONS USED IN EXPERIMENTS
We evaluate the performance and fairness of various algorithms for several definitions of fairness, shown below. These definitions were specified as text input to Shi fty and were bounded using recursive technique used by prior Seldonian algorithms (Metevier et al. 2019) (See Appendix C.2)
Demographic Parity (Dwork et al. 2012 Calders and Verwer 2010):
9Dr (0)
E [[)(S) E[0(X){S=s)
EDP
Disparate Impact (Griggs v. Duke Power Co.,
1971 Chouldechoval 2017
Zafar et al., 2017):
E[((X)]S=so) S[((S)
(0) = EDI
min
E[0(X){S=s1) E(0(X)]S==o)
Equal Opportunity (Hardt et al. 2016: Chouldechova 2017):
g0Op (0) =0, =00 EBOp
Equalized Odds (Hardt et al., 2016):
(0) [00X)YY=0--==0)-00000000--- S-sa]
11--,)=))=11,-500E--1------- S=s1]
-60d
Predictive Equality (Chouldechova 2017:
Corbeti-Davies et al. 2017):
gPF(() (0) = E11-0())x=11, S= - -E]1-(()))=1,55- -PF
18

---

Published as a conference paper at ICLR 2022
Sex Pr(T-t)
Pt(T-=t)
Q
Race
Pr(T-t)
Pr(T==t)
Q
sex1
0.324
0.150
(0.162, 0,661)
race1
0.006
0.300
(0.004, 0.304)
seX2
0.676
0.850
(0.338, 0.838)
race2
0.871
0.600
(0.610, 0.909)
race3
0.054
0.050
(0.038, 0.338)
race1 0.067
0.048
(0.047, 0.347)
races
0.002
0.002
(0.002, 0.301)
(a) Marginal distributions of the demographic attribute (b) Marginal distributions of the demographic attribute for the UCI Adult Census experiments. The demo- for the UCI Adult Census experiments. The demo- graphic attribute represents the anonymized sex. graphic attribute represents anonymized student race.
Figure 4: Marginal distributions over the demographic attribute, T. for the UCI Adult Census experiments (left) and the UFRGS GPA experiments (right). In each table, the left column shows the distribution of the demographic attribute during training, the middle column shows the deployed marginal distribution used in our experiments for known demographic shift (Section [4.]. and the right column shows the bounds on the marginal distribution used in our experiments for unknown demographic shift (Section 4.2
For both the UCI Adult Census dataset and the UFRGS GPA dataset, we conducted separate experi- ments for each definition. For both sets of experiments, the fairness attribute, S, was allowed to take one of two possible values, 8n or 81. Specifically, in our experiments using the UCI Adult Census dataset, S represents the race of each individual (i.e., So = black and $1 = white) whereas in our experiments using the UFRGS GPA dataset (i.c., 80 = female and $1 = male). Finally, the tolerances for each definition of fairness were set <pp = 0.05, <pi 0.8, <EOp = 0.15, 6pоa = 0.2 and CPr. = 0.025 for our experiments using the UCI Adult Census dataset, and <DP = 0.1, <DI = 0.8. CEOp = 0.05, Gpod 0.1 and (pp 0.05 for our experiments using the UFRGS GPA dataset. While the choice of tolerance for each definition impacts how strict the resulting faimesss constraint it, we note that Shifty algorithms will satisfy their high-confidence fairness guarantees regardless of how these tolerances are chosen. The tolerances used in experiments are for illustrative purposes, and in practice, will be set based on the specific requirements of the user's application.
D.3 SIMULATED DEMOGRAPHIC SHIFTS USED IN EXPERIMENTS
In our evaluations, we conduct separate experiments using the UCI Adult Census dataset and the UFRGS GPA dataset. In addition, for each dataset, we conduct experiments testing a single, known demographic shift, as well as an unknown demographic shift described by set Q as described in Section 3.1.2. Here we discuss the specific simulated demographic shifts for each experiment.
Figure describes the marginal distributions over the demographic attribute T used for each experi- ment. Figure 4a provides the marginal distributions used in our experiments using the UCI Adult Census dataset, while Figure 4b) provides the marginal distributions used in our experiments using the UFRGS GPA dataset. Within each table, the lefumost column shows the marginal probabilities of each value of T during training. Next, the middle column of each table shows the distribution of the demographic attribute during deployment, which we simulate using the procedure described in Appendix [.I] Finally, the rightmost column each table shows the bounds on the marginal distribution of the demographic attribute for each experiment that we
specification of Q in experiments on overcoming unknown demographic shift. We generated these bounds by interpolating race
between the interval (0, 1) and the singleton interval containing the marginal distribution under the training distribution, using an interpolation factor of 0.25 for our experiments using the UCI Adult Census dataset, and 0.3 for our experiments using the UFRGS GPA dataset. We note that this interpolation scheme and the choice of interpolation factors were chosen for illustrative purposes in our experiments. while in practice, will be specified by the user based on domain knowledge that is available during training.
E ADDITIONAL EXPERIMENTAL RESULTS
In this section, we present results for additional experiments conducted using the UCI Adult Census dataset (Kohavi and Becker 1996) and the UFRGS GPA dataset (da Silva 2019) evaluate the
19

---

Published as a conference paper at ICLR 2022
effectiveness of Shitttttest and various baseline algorithms enforcing faimess constraints under demographic shift. While Section 4.1 provides results of our experiments using the UCI Adult Census dataset for enforcing disparate impact and demographic parity constraints, this section augments these results in two ways. First, for both known and unknown demographic shifts, we provide results of experiments using the UCI Adult Census dataset enforce fairness constraints based on the concepts of equal opportunity, equalized odds, and predictive equality. Second, for both known and unknown demographic shifts, we provide results for experiments based on enforcing these same definitions using the UFRGS GPA dataset. Similarly to Section 4 we first present result for known demographic shift in Section E. and then provide results for our experiments using unknown demographic shift in Section E.2
E. KNOWN DEMOGRAPHIC SHIFT
Additional results for experiments using the UCI Adult Census dataset are shown in Figure 5 and full results for the experiments using the UFRGS GPA dataset are shown in Figure First, we found that in all of our experiments, Shi fty-ttest satisfied Property B, as evidenced by the fact that the green curves in the bottom rightmost plots of Figure 5 and Figure 6 are never above the dashed black line that denotes the 0.05 tolerance. On the other hand, Fairlearn, Fairness Constraints, and RFLearn all produced unfair models frequently, with some exceptions. For example, in our experiments using the UCI Adult Census dataset, Fairlearn was consistently fair when enforcing equal opportunity constraints (Figure 5 top right). In other experiments, such as our experiments using the UFRGS GPA dataset to enforce disparate impact, demographic parity, equalized odds, and predictive equality, we found that RFL earn and Fairlearn were often fair empirically, as evidenced by failure rates close to the 8 = 0.05 tolerance, but frequently exceeded the 0.05 threshold after deployment. These findings show that, while existing fair algorithms can be effective at training models that are fair, they do not provide fairness guarantees that hold under demographic shift. Therefore a user cannot assume that the models produced by these methods will be fair in practice.
Next, our results using the UCI Adult Census dataset show that Shi thifty-ttess attained competitive accuracy compared to the best tess-perfonmig baseline algorithms (middle column plots in Figure 5
Consequently, Shifty-ttest suffered very little loss in accuracy in order to enforce fairness constraints that hold under demographic shift for this experiment. Results were comparable in our experiments using the UFRGS GPA dataset, with the exception that, when enforcing equal opportunity, equalized odds and predictive equality with the tolerances described in Appendix [.2) the resulting constraints were too strict for thiffy-ttes to reliably return models that are fair after demographic shift. Therefore, we conclude that, if suitably fair models exist, Shi fty-ttess is effective at them when provided with sufficient training data, and that in many cases the models found by Shi fty have comparable accuracy to those found by algorithms that do not provide fairness guarantees.
Finally, we note that Shi ftyt-ttttst was typically able to avoid returning NO DOL_OLUUTIO_FOOUU in most experiments. The exceptions to this pattern were our experiments using the UFRGS GPA dataset to enforce equal opportunity, equalized odds, and predictive equality. In these experiments, the fairness constraints were more strict than in other experiments. Consequently, Shi fty-ttest However, in these experiments, all baselines produced models that were unfair above the d 0.05 frequency threshold. illustrating the difficulty in satisfying these fairness constraints.
tended to return NO.SOLUTION.FOUNT
E.2 UNKNOWN DEMOGRAPHIC SHIFT
Here, we provide additional results evaluating the impact of unknown demographic shift on the fairness properties of trained models. As in the experiments described in Section 3.1.2 we conducted these experiments by uniformly sampling a training dataset from an underlying population (i.e., either the UCI Adult Census dataset or the UFRGS GPA dataset, depending on the experiment), and then evaluate the worst-case impact of unknown demographic shift by considering all possible shifts that agree with the user's input assumptions, as specified by the set Q (see Section 3). Specifically, the set Q of possible demographic shifts is given by a set of bounds on the marginal distribution of the demographic attribute after deployment, and the specific bounds used in these experiments are provided in Figure 4. The additional results for experiments using the UCI Adult Census dataset
20

---

Published as a conference paper at ICLR 2022
(a) Equal Opportunity:
Pr(Mi FOUD)
1.0
Accurnyy
(Ongiual)
80%
Fallur Hate [Ongiaa))
0,8
0%
0.6
20K
30K
40K
50K
10K
20K
S0K
40K
0.4
Accunnty
[Duylayed]
Training Samples
Fallur Rate [Docpoyed)
Thaining Samples
0.2
0%
20K
50K
20K
30K
40K
50K
10K
20K
90K
40K
Towiring Samples
Training Samples
Trxining Samples
(b) Equalized Odds:
Preji PrORtRmaaTOO. FOND)
1.0
Accunnyy
(Digiual)
Fallur stace [Onggaal)
0,8
78%
0%
0.6
10K
20K
30K
40K
50K
10K
20K
30K
40K
50K
0.4
Accunny (Duplogel)
Training, Samples
Fallare Hate [Doppoyed]
Training Samples
0.2
78%
50%
0%
Training Samplee
Training Samples
Trxining Samples
(c) Predictive Equality:
PromsguuaT F3310
1.0
Accunayy
(Diigtal)
00%
Fallur Bare (Orgguul)
0.8
78%
0%
0.6
10K
20K
30K
40K
52K
10K
20K
30K
40K
50K
0.4
Accunaty (Duplogel)
Training, Samples
Failure Rate [Duplogeul]
Training Samples
78%
0%
Training Samples
Training, Samples
Training Samples
Shifly
RFLearn
Seldonian
Saldeiiinn
Fattharn
Figure 5: Additional results when enforcing fairness constraints under known demographic shift using the UCI Adult Census dataset.
shown in Figure 7 and full results for the experiments using the UFRGS GPA dataset are shown in Figure
First, we find that the results of these experiments are similar to the results of our experiments using known demographic shift, with the exception that constraints based on unknown demographic shift are more strict than those based on known shift. In all experiments, the output of Shi fty-ttest was consistently fair, demonstrating that Shi Shifty algorithms satisfy Property even under unknown demographic shift. However, Shifty-tter all experiments than in the experiments with known demographic shift. This is reasonable, since in almost every experiment, we found that models trained using existing baseline algorithms could, in the worst case, be made to behave unfairly depending on the observed demographic shift.
was more likely to return
COLUUION_FOOO
With regards to model accuracy, found that long the faimness constraints were not overly strict, Shi thiffy-tted
was able to identify models that were fair and achieved comparable accuracy to baselines, and in some cases, identify models that exceeded the accuracy of baselines by large margin (see the bottom center plots for the equalized odds experiments Figure 7 This can be explained by noting that, unlike the baseline algorithms, Shifty-tee selects a candidate model by optimizing an estimate of accuracy after the model is deployed, even if that model performs worse than the baselines the training data distribution.
21

---

Published as a conference paper at ICLR 2022
(a) Disparate Impact
PriMu (U)e))
1.0
Accurnty
(Oiginal)
60%
Fallure Bace
(Onijnal)
0.8
60%
0%
0.6
bok
Training Samples
Training Samples
0.4
Accuney
(Daglopel)
Faskare Rate (Dogloped)
100%
0.2
0%
coK
Training Samples
Training Samples
Training Samples
(b) Demographic Parity
PrIMLSRUTTON mone)
Acuuraty
(Onginul)
Fallure Bace (Orijina)
100%
0.8
60%
0%
0.6
Training Samples
Texining Samples
0.4
Acroncy
(Duployel)
65%
Faikire Bate (Duployed)
100%
0.2
80%
0%
Triining Samples
Training Samples
Training Samples
(c) Equal Opportunity:
PriMLSUUTIOU mDnB)
1.0
Aquuney
(Orgina)
63%
Failur Bate (Orijnal)
100%
60%
0.8
0%
0.6
60K
0.4
Accuracy
(Duployel)
65%
Training Samples
Faikire Rate [Cuployed]
100%
Texining Samples
0.2
65%
0%
Trvining Samples
Training Samples
Training Samples
(d) Equalized Odds:
1.0
Accuensy
(Orijnal)
Faiter Rate (Crijinal)
100%
60%
0.8
50%
0%
0.6
60K
Training Samples
Trxining Samples
0.4
Acruacy
[Duylayed]
Exiure Rate [Duployed]
100%
0.2
60%
0%
60K
Trwining Samples
Training Samples
Texining Samples
(e) Predictive Equality:
Prite Prito Swu.TTr...o.oooo FOUD)
1.0
Accurnyy
(Orijnal)
65%
Falure Rate (Original)
100%
60%
0.8
0%
0.6
60K
Training Samples
Trxining Samples
0.4
Accuency
[Duylaged]
85%
Faiture Rate (Duulloped]
100%
0.2
60%
0.0
0%
40K
60K
4DK
Trwining Samples
Training Samples
Trxining Samples
Shint
Quaei
Faimnes
Figure 6: Results when enforcing fairness constraints under known demographic shift using the UFRGS GPA dataset.
22

---

Published as a conference paper at ICLR 2022
(a) Equal Opportunity:
PrIMLSRUTTON (ome)
1.0
Acuuraty
(Ongjnul)
Fallure Bace (Crijina))
100%
0.8
0%
0.6
Training Samples
Trxining Samples
0.4
Acconcy
(Duplogel)
85%
Faikire Bate (Cuployeel)
100%
0.2
00%
Training Samples
Training Samples
Training Samples
(b) Equalized Odds:
PriMUSRUTION (DND)
1.0
Aquuney
(Onijnal)
00%
Failur Base (Orijnal)
100%
0.8
78%
0%
0.6
Training Samples
Trxining Samples
0.4
Acrrncy
(Duployel)
Faikire Bate [Coullyeed]
100%
0.2
Triining Samples
Training Samples
Training Samples
(c) Predictive Equality:
Pr(ML FOND)
1.0
Accunaty
(Orijnal)
Fallue Stats (Onigiaal)
30%
0.8
78%
0%
0.6
60K
Training Samples
Trxining Samples
0.4
Acraray [Duylagee]
Fxiurr Rate [Cuulloyed]
100%
0.2
75%
0%
Trwining Samples
Training Samples
Texining Samples
Shiny
Seldenian
Duwi-Seldeniann
Figure 7: Additional results when enforcing fairness constraints under unknown demographic shift using the UCI Adult Census dataset.
23

---

Published as a conference paper at ICLR 2022
(a) Disparate Impact
Prikt Priti (U)e))
1.0
Accunnty
(Onginal)
60%
Fallure Bave
(Onginal)
0.8
60%
0%
0.6
bok
Training Samples
Training Samples
0.4
0.2
Accuncy
(Daglopel)
60%
Faskure Rate (Dogloped)
100%
50%
0%
c0K Training Samples
Training Samples
Training Samples
(b) Demographic Parity
PrIMLSRUTTON (D))))
Acureay
(Onginul)
65%
Fallure Bace (Crijinu))
100%
0.8
0%
0.6
Training Samples
Texining Samples
0.4
Accuney
(Duployel)
65%
Faikire Bate (Duployed)
100%
0.2
53%
0%
<0K
Training Samples
Training Samples
Training Samples
(c) Equal Opportunity:
PriMURUUTIOO rone)
1.0
(Onjinal
Failur Bate (Orijnal)
100%
60%
0.8
0%
0.6
60K
0.4
Acrunay
(Duployed)
Training Samples
Faikure Rate [Duployed]
100%
Texining Samples
0.2
80%
0%
Trwining Samples
Training Samples
Training Samples
(d) Equalized Odds:
PriNL FOnD)
1.0
Accurnay
(Orijnal)
Faiter Rate (Crijinal)
100%
60%
0.8
0%
0.6
40K
60K
Training Samples
Trxining Samples
0.4
Acrunay
[Duylaged]
68%
Fxiure Rate [Duployed)
100%
0.2
53%
0%
Trwining Samples
Training Samples
Texining Samples
(e) Predictive Equality:
Prite Prito www.TTTTTOo.... FOUD)
1.0
Accurnty
(Orijnal)
Falure Rate (Original)
100%
67%
0.8
60%
0%
0.6
40K
60K
Training Samples
Training Samples
0.4
Accuracy
[Duylaged)
65%
Faiture Rate (Duulloped]
100%
0.2
0.0
60%
0%
40K
60K
4DK
Trwining Samples
Training Samples
Trxining Samples
Shinty
Quavi Selii-Sedoniann
Faimnes Constraints
Figure 8: Results when enforcing fairness constraints under unknown demographic shift using the UFRGS GPA dataset.
24


Reviews:
[{"review_id": "xNKqbmzBhCv", "reviewer": "Reviewer_fKm7", "summary": "", "questions": "", "limitations": "", "rating": 5, "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": "The paper tackles an interesting and challenging problem. The idea of separating the tasks in a parallel sense is interesting as they divide the problem into the candidate selection and searching for the high-confidence upper bound. The main issue, however, is the data distribution part that it seems that they didn’t describe its procedure, hence, I am not sure whether it was a fair sample selection in which both of the Df and Dc are representative of the source data.\n\nIn the introduction, the authors claimed that they allow users to select fairness notion(s) from a large class depending on the application domain. However, according to their approach, it is not clear how they can account for individual fairness. Can the authors elaborate on this?\n\nFurthermore, the authors acknowledge in section D of supplementary material, there is an assumption that each parameter’s intervals are independent, which is often false. Can the authors explain such justifications.\n\nTheir method of identifying the distribution shift in both known and unknown shifts relies on user-provided information. Indeed, it is an assumption to the problem which may hold untrue.  Would it be possible to detect distribution shift at the deployment and change the model accordingly? Why there is a need to train models for various unknown distribution shifts? ( It is obvious that considering various shifts has a huge impact on the performance (according to their results in Section 4.2)? \n\nThe structure of the evaluation section is not convincing to me, and the comparison with in-processing fairness approaches does not seem fair. The only valid comparison is wrt to the fairness guarantees. However, it is not clear to me why the authors compared their approach under distribution shift with other methods that do not claim to be fair when the distributions of the train and test sets are different. Also, given the results presented for the experiment with unknown distribution shift,  it seems the Seldonian algorithm performs better that their approach. I'd suggest the authors to compare their approach with methods proposed for concept shift, also it will be useful to add at-least one more dataset for the evaluation to make sure that these results are consistent in various contexts.", "summary_of_the_paper": "The authors propose an approach called SHIFTY that provides high-confidence fairness guarantees when the distribution of training and deployment is different. They proposed two approaches to tackle the problem, one based on known distribution shift and another one for when the distribution shift is unknown. They evaluated their approach on a dataset for student success prediction and compared their approach with SOTA in-processing fairness approaches. ", "summary_of_the_review": "I have found the main idea of the paper interesting, however, I have some doubts about their proposed method and the way that they evaluated their approach and compared it with other methods (see previous section). \nAlso, I suggest the authors to focus only on group fairness as it is not clear how their approach can be used for individual fairness methods. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}, {"review_id": "tMxaHGNmQdz", "reviewer": "Reviewer_8AcS", "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": "Comments: \n\n-I found the formal definition of demographic shift (page 3) somewhat hard to parse and understand intuitively. \n\n-On top of the previous comment, it is not clear to me why the authors make a distinction between fairness attribute and demographic attribute. What if the college wants to take into account both race and gender as a fairness, legally protected, attribute? Also why is it reasonable to assume that T changes (eq. 2) but the conditional probability (eq. 3) does not? In particular, in what settings it is justified to assume that eq. 3 holds?\n\n-Section 3.1.2 assumes a more realistic scenario. It is hard to think of scenarios where Q would be exactly known so I think this section should be presented as part of the main setup (and not as an extension). However, the description of the method is not very precise. How do the numerical approximation and simplicial homology optimization exactly work in this setting?\n\n-Current appendix A and related work on pages 3-4 could be improved. How does Shifty provide guarantees that the other algorithms cannot? Would it require significant modification of the existing algorithms (and how, if possible) to account for demographic shifts (property B)?\n\n-In terms of writing, the paper is quite clearly written. There are some repetitions in certain places (e.g., section 2)\n\n-In the main contributions list (page 2), I think that the theoretical contribution (#2) is an overstatement. Theorem 1 is rather obvious and no guarantees are provided for the unknown demographic shift case (maybe obtaining distribution-dependent bounds would be possible?)\n\n-Why was only this dataset chosen? Have the authors tried (potentially synthetic) experiments with other datasets (e.g., the law admissions dataset used often in fair ML)?\n\n-How is such a dramatic demographic shift explained in Brazil (fig. 2)?\n\n-The sentence “To evaluate each model’s… E)” about evaluation in Section 4.2 is not very clear. \n", "summary_of_the_paper": "The paper focuses on algorithmic fairness in machine learning (ML) and in particular on the problem of demographic shift. The motivation comes from the fact that the distribution of the underlying population might change between training and deployment -- the papers defines this as a shift in the marginal distribution of a single random variable (race, sex, etc.).\n\nThe setup considers a classification task, where sensitive information (the “fairness attribute”) might not be legal to use, but is available information. Given a certain event of interest and a target tolerance value \\tau (e.g., with respect to sex, the false-positive rate of the model must below \\tau% for female), an algorithm is defined to be fair if the algorithm achieves the target value \\tau with high probability (given by some \\delta parameter). To account for demographic shift, the model further includes a “demographic attribute” T; the distribution of T can change over time, but the conditional distribution must remain the same (by assumption).\n\nGiven this setup, the paper introduces Shifty, an ML algorithm that provides high-confidence guarantees that a fairness property will hold even when a demographic shift has occurred. Shifty works as follows. It takes as input a training datasets, some required fairness constraints and a description of demographic shifts. Then, it partitions the dataset to two subsets, finds a model based on the first dataset. Then, it uses Q and the second dataset to build an upper confidence bound for the model after deployment and given demographic shift. It returns only models that are unfair after deployment with probability at most \\delta.\n\nThe experiments use test scores data from the Brazilian university system and show the satisfactory performance of the proposed algorithm.\n", "summary_of_the_review": "I think the paper touches upon an important practical challenge not only in fair ML, but ML models used for decision-making in general. The analysis is natural, straightforward, and technically sound; the most technical aspect is the computation of the upper confidence bound which is standard, so I think there is no particular novelty in its methodological contribution. \n\nThat said, I think the conceptual contribution of the paper is still quite new and useful. In the light of the novel application, I thus think the algorithm is quite novel -- nevertheless, it would be helpful if the authors provided a clearer comparison to the most related works and explained how their approach is novel. \n\nFinally, I found the evaluation section convincing and well-executed. I would appreciate additional experiments on -- other widely used in fair ML -- datasets (even synthetic experiments).\n", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "HSEpS7bXmRr", "reviewer": "Reviewer_D4Vj", "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": "Positives:\n\n1. The paper is generally well-written and easy to follow.\n2. The problem studied is definitely interesting to the community and one of the main challenges with the deployment of models in practical settings. \n3. The high-confidence upper bounds on unfairness in the deployment setting present an interesting approach to ensuring fairness guarantees in the deployment setting.\n\nNegatives:\n1. The authors are missing some parallel works with ensuring fairness guarantees with general distribution shift [1,2,3]. \n2. Certain design choices are missing clear explanations such as how was the interpolation factor of 0.3 decided?\n\nAdditional concerns:\n1. Can the assumptions about $g(\\theta)$ be extended to settings where there needs a comparison with respect to another demographic group rather than ensuring it to be under some threshold? \n2. It is not exactly clear how the approach can be extended to definitions such as individual fairness. \n3. In order to better assess the quality of the fair predictions in the deployment setting, it would be helpful to have some empirical analysis when multiple definitions of fairness that may not be compatible are suggested by the user.\n\nReferences:\n1. Singh, H., Singh, R., Mhasawade, V., & Chunara, R. (2021, March). Fairness violations and mitigation under covariate shift. In Proceedings of the 2021 ACM Conference on Fairness, Accountability, and Transparency (pp. 3-13).\n2. Du, W., & Wu, X. (2021). Robust Fairness-aware Learning Under Sample Selection Bias. arXiv preprint arXiv:2105.11570.\n3. Dai, J., & Brown, S. M. Label Bias, Label Shift: Fair Machine Learning with Unreliable Labels.", "summary_of_the_paper": "The paper presents a class of algorithms for ensuring fairness guarantees when the deployment data is susceptible to a demographic shift, termed as a marginal shift in demographic attributes such as gender or race, in comparison to the training data. Results are provided for two settings, 1) when the exact demographic shift in the deployment setting is known and 2) when the demographic shift in the deployment environment is unknown. This is done by computing a high-confidence upper bound on the prevalence of unfair behavior in the deployment environment, presently done using the Student's t-Test. Comparisons are made with Seldonian and Quasi-Seldonian algorithms, Fairlearn, and Fairness Constraints. The empirical analysis is performed on the university dataset to predict GPA using scores, with gender as the fairness attribute and student's race as the demographic attribute, the marginal distribution of which changes across the training and deployment settings. ", "summary_of_the_review": "The contributions of the paper are clear. As the paper is missing some related works, the baseline comparisons can be further extended to assess other factors as suggested. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "1StqYrlhM6", "reviewer": "Reviewer_3Aub", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The work provides a conceptually clear and flexible framework for learning fair classifiers under demographic shifts. The organization of the concepts (Seldonian framework, problem description, fairness tests) is great and the writing is clear. Isolating the problem to performing the fairness test under an unknown distribution helps to understand the proposed method. The flexibility of the framework to accommodate different fairness measures is an advantage. The probabilistic guarantee for fairness violation is a good feature absent from many fair learning approaches for this particular problem. \nMy main issues are (1) with the setup of controlling only fairness and not the accuracy, and (2) the seemingly large number of samples required for good accuracy for the method. Some related work is also missing which can be easily addressed. Few details on the scope of the demographic variable (discrete vs continuous) and relation to covariate shifts need clarity. I mention these issues in detail below.\n\n---\n  \n## Questions to address in the response:\n\n1. Why is the objective of controlling test unfairness while controlling train error justified, as opposed to attending to both quantities for test set? As pointed out, determination of the fairness test is impacted by demographic shift. So, is the classification loss at deployment time that is to be computed for the shifted distribution. Does this accounted somehow in the algorithm? One strategy is similar to the proposed fairness test procedure to note that loss conditional on T remains the same and somehow importance weighting or bounding the loss. I am wondering if I am missing this important detail in the algorithm on how training and deployment error are related to each other. \n\n2. Does the demographic shift assumption rely on demographic attribute space \\mathcal{T} to be discrete? The specification of marginal shift in terms of lower-upper bounds on each probability of each value of T suggests that. Similarly, conditioning set \\zeta around Eq (4) is assumed to be discrete, thus, excluding some fairness metrics, which is fine, but the allowed domains for variables should be specified. Please mention if discreteness is a limiting assumption for the proposed algorithm.\n\n3. Accuracy of Shifty seems to be severely impacted even with known shifts when there are <100K data points in middle plots of Figure 3. Under known shift, the test fairness constraint is not harsher than the fairness constraint on the train set. What is the reason for the drop? Also, it is more practical to have much fewer data points such as of the order of 10K. At least, the sizes of fairness datasets used in literature are in the same or lower range. Does the severe drop in accuracy observed in only this particular dataset of exam scores or others too? It would be worthwhile to either include results for lower sample sizes on this and preferably other datasets, or empirically study and discuss issues limiting the sample efficiency for future work to address.\n\n---\n\n## Minor questions that do not affect my review:\n4. In Algorithm 1, does the candidate model \\thetha_c in step 2 appear in inputs to fairness testing in step 3?\n\n5. I missed the description of how the candidate models are enumerated and tested one by one. Can you please clarify what is the output of the candidate model selection step 2 in Algorithm 1.\n\n---\n\n## Related work\n\nThere have been multiple studies on fairness guarantees under shifts which have been omitted. They are making somewhat different, in some cases weaker, assumptions and have different guarantees. It would be good to discuss differences from these works.\n\n- Biswas and Mukherjee 21 https://dl.acm.org/doi/abs/10.1145/3461702.3462596\n- Rezaei et al. 21 https://arxiv.org/abs/2010.05166\n- Schumann et al. 19 https://arxiv.org/abs/1906.09688\n- Coston et al. 19 https://dl.acm.org/doi/abs/10.1145/3306618.3314236\n- Singh et al. 21 https://arxiv.org/abs/1911.00677\n- Dai and Brown 20 https://dynamicdecisions.github.io/assets/pdfs/29.pdf\n\nIf any of these works have the same problem setup such as Rezaei et al. 21, please consider comparing against them.\n  \n---\n\n## Suggestions\n\nPlease mention if the demographic shift assumption is a type of covariate shift, which is a better known term in literature or how does it differ.\n\nPlease describe how the result in Theorem 2 is important and used to support the method.\n\nPlease add the reason for choosing the particular numerical optimizer from Endres et al. 2018. Is U_ttest a non-smooth function?\n\nA possible dataset to experiment is the new Adult dataset derived from US Census which has distribution shifts, perhaps demographic and other shifts. See Folktables package https://github.com/zykls/folktables.", "summary_of_the_paper": "The paper proposes a method for controlling unfairness of a model when the test distribution may differ in the marginal distribution of a feature such as gender, race. It derives a statistical test for checking unfairness on the unknown test distribution via importance weighting combined with user-input on extent of the shift. Experiments on an academic performance dataset shows that the approach achieves low failure rate of learning an unfair classifier.", "summary_of_the_review": "The work presents a novel and clear approach to the problem of fair learning under shifts. There are some open issues on the problem setup and experimental results, which I would like authors to respond to. In total, the work is a technically strong contribution to the nascent literature on the problem.\n\n---\nFrom the newly made changes and clarifications in the response, my concerns are addressed. I highly encourage authors to move the results on new dataset, discussion on related work and continuous demographic attributes to the main text.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper studies the setting of group-based fairness under the so-called demographic shift, where the marginal distribution of the data remains the same conditional on the subgroup but the subgroup distribution can change. It provides a class of algorithms which give high confidence guarantees under demographic shift in both the known and unknown shift setting.

Overall the paper is a worthwhile contribution: it provides a new angle to the important problem of group-based fairness with good theoretical and empirical results.
Decision: Accept (Poster)