Enforcing Delayed-Impact Fairness Guarantees
Authors: Aline Weber
Blossom Metevier
Yuriy Brun
Philip S. Thomas
Bruno Castro da Silva
Venue: Submitted to ICLR 2023 (2023)

Abstract: Recent research has shown that seemingly fair machine learning models, when used to inform decisions that have an impact on people's lives or well-being (e.g., applications involving education, employment, and lending), can inadvertently increase social inequality in the long term. Existing fairness-aware algorithms consider static fairness constraints, such as equal opportunity or demographic parity, but enforcing constraints of this type may result in models that have a negative long-term impact on disadvantaged individuals and communities. We introduce ELF (Enforcing Long-term Fairness), the first classification algorithm that provides high-confidence fairness guarantees in terms of long-term, or delayed, impact. Importantly, ELF solves the open problem of providing such guarantees based only on historical data that includes observations of delayed impact. Prior methods, by contrast, require prior knowledge (or an estimate) of analytical models describing the relationship between a classifier's predictions and their corresponding delayed impact. We prove that ELF satisfies delayed-impact fairness constraints with high confidence and that it is guaranteed to identify a fair solution, if one exists, given sufficient data. We show empirically, using real-life data, that ELF can successfully mitigate long-term unfairness with high confidence.

Under review as a conference paper at ICLR 2023
ENFORCING DELAYED-IMPACT FAIRNESS GUARANTEES
Anonymous authors Paper under double-blind review
ABSTRACT
Recent research has shown that seemingly fair machine learning models, when used to inform decisions that have an impact on people's lives or well-being (e.g.. applications involving education, employment, and lending), inadvertently increase social inequality in the long term. Existing fairnes--wware algorithms consider static fairness constraints, such as equal opportunity or demographic parity, but enforcing constraints of this type may result in models that have a negative long-term impact on disadvantaged individuals and communities. We introduce ELF (Enforcing Long-term Fairness), the first classification algorithm that provides high-confidence fairness guarantees in terms of long-term, or delayed, impact. Importantly, ELF solves the open problem of providing such guarantees based only on historical data that includes observations delayed impact. Prior methods, by contrast, require prior knowledge (or estimate) of analytical models describing the relationship between a classifier's predictions and their corresponding delayed impact. We prove that ELF satisfies delayed- -mpptcttt fairness constraints with high confidence and that it is guaranteed to identify fair solution, if one exists, given sufficient data. We show empirically, using real-life data, that ELF can successfully mitigate long-term unfairness with high confidence.
INTRODUCTION
Using machine learning (ML) for high-stakes applications, such as lending, hiring, and criminal sentencing, may potentially harm historically disadvantaged communities (Flage 2018 Blass 2019) Bartlett et al.) (222I) For example, software meant to guide lending decisions has been shown to exhibit racial bias (Bartlett et al. 202T). Extensive research has been devoted to algorithmic approaches that promote fairness and ameliorate concerns of bias and discrimination for socially impactful applications. Most of this research has focused on the classification setting, in which an ML model must make predictions given information about person community.
Most fairness definitions studied in the classification setting are static: they do not consider how a clas- sifier's predictions impact the long-term well-being of community (Liu al.. 2018). In their seminal paper, Liu et al. show that classifiers' predictions that appear fair with respect to static faimess criteria can nevertheless negatively impact the long-term wellness of the community it aims to protect. Impor- lantly, [iu et al.) and others investigating long-tern fairness (see Section b assume that the precise analytical relationship between a classifier's prediction and its long-term impact, or delayed impact (DI), is known. Designing classification algorithms that mitigate negative delayed impact when this relationship is not known, or cannot be computed analytically, has remained an open problem.
We introduce ELF (Enforcing Long-term Fairness), the first classification algorithm that solves this open problem. ELF, unlike existing methods, does not require access to an analytic model of the delayed impact of classifier's predictions. Instead, it works under the less strict assumption that the method only has access to historical data containing observations of the delayed impact that resulted classifier. Below, illustrate this setting with example.
from predictions of greviously-deploye
Loan repayment example. As a running example, consider a bank that wishes to increase its profit by maximizing successful loan repayments. The bank's 's decisions informed by classifier that predicts repayment success. These decisions may have a delayed impact in terms of the financial well-being of loan applicants, such their savings rate or debt-to-income ratio, two years after lending decision is

---

Under review as a conference paper at ICLR 2023
made. Taking this delayed impact into account is important: when subset of the population is disad- vantaged, the bank may want (or be required by law) to maximize profit subject to a faimess constraint that considers the disadvantaged group's 's long-term well-being; e.g., constraint requiring improve- ment in savings rates two years after a lending decision. Unfortunately, existing methods that address this problem can only be used if analytical models of how repayment predictions affect long-term fi- nancial well-being are available. Constructing such models is challenging; many complex factors (e.g.. social, economic) influence how different demographic groups may be affected by financial decisions.
ELF, by contrast, can ensure delayed-impact fairness with high confidence as long as the bank can collect data about the delayed impact resulting from predictions made by a previously-deployer classifier. Suppose the bank deployed a classifier, which informed lending decisions. and logged the real-valued savings rate of each client two years later (i.e., logged the observed delayed impact associated with that client). ELF uses this historical data to train new classifier with high-confidence Importantly, ELF works with all
fairness guarantees in terms of long-term, or delayed, impact [ measures of delayed impact that can be empirically observed or quantified. Appendix describes other real-life problems where ELE could be applied.
Contributions. We present ELF, the first method capable of enforcing DI fairness when the ana- lytical relationship between predictions and DI is not known. To accomplish this, we simultaneously formulate the fair classification problem as both classification and reinforcement learning wroblmm-llasificca
for optimizing the primary objective (a measure of classification loss) and reinforcement learning when considering DI. We prove that 1) the probability that ELF returns fair model (in terms of DI) is at least (1 - o). where ö is user-specified confidence level; and 2) given sufficient training data, ELF is able find and return solution that is fair if one exists. We empirically analyze ELF's performance on data from the National Data Archive on Child Abuse and Neglect (NDACAN, 202I), while varying both the amount of training data and the influence that a classifier's 's predictions have on delayed impact.
Limitations and future work. ELF requires access representative historical data-i.c, a dataset with observations of the delayed impact resulting from different predictions. For example, consider a college making admission decisions informed by predictions of students' academic performance. Such predictions may have delayed impact, e.g., on whether a student will be employed after graduation. The college would only have access to this information about admitted students; in this case, ELF would not be applicable. However, in many important real-life settings it is possible to observe the delayed impact of different decisions (see Appendix [A). In our lending example, for instance, the bank can observe the delayed impact of lending decisions both for clients who received a loan and those who did not. In Appendix B, we further discuss ELF'S limitations.
ELF be extended in many ways. Section 6 discusse existing methods that address alternative long-term faimess settings; e.g., when multiple prediction steps are involved. Importantly, all of these methods require an analytic expression of the relationship between predictions and delayed impact, while ELF requires access only to historical data. As future work, ELF could be extended to tackle these alternative settings.
2 PROBLEM STATEMENT
We now formalize the problem of classification with delayed-impace fairness guarantees. As in the standard classification setting, a dataset consists of n data points. Each hh data point contains X,, a feature vector describing, e.g.. a person, and label Y. It also contains a set sensitive attributes, such as race and gender. ELF supports an arbitrary number of sensitive attributes, but for brevity our notation
single attribute, T, We assume each data point also contains prediction, Y made by stochastic classifier, B. We call the behavior model, defined as ((x, 9)= -()
Let T be a real-valued delayed-impact observation (DIO) resulting from deploying / for the person described by the 7th data point. In running example, 1e corresponds to the empirically-ohservee savings rate two years after the prediction 8,5 used to decide whether the 7th client should get loan. We assume that larger values of I correspond to better DI. We append I to each data point and
In A Appendix F we show how R.F can he easily extended to enforce long-term and static fairness constraints simultancously.
2

---

Under review as a conference paper at ICLR 2023
thus define the dataset to be sequence of independent and identically distributed (i.i.d)) data points:
D== Y, Tr V,", (,,1)) )= We denote an arbitrary data point in D by suppressing the subscripts.
Our goal is to construct classification algorithm that takes input dataset, D, and outputs new model, Ta, that is as accurate as possible while enforcing relayed-impace constraints The new model is of the form na( ú) = Pr(P"* X= where xo parameterized by vector Q (e.g.. weights of neural network), for some feasible set θ, and where y the prediction made by me given X. Like 1,", 1,10 is the delayed impact observation if the model outputs the prediction Y
We consider the standard classification setting where predictions depend only on the feature vector X (Assumption J. Furthermore, we assume that the delayed impact of prediction does not depend on how the prediction support vector machine made a loan-repayment prediction (Assumption 2).
made. For example, it makes difference whether a neural network
Assumption 1. model's s prediction Y is conditionally independent of and T given X. That is, for all x. t, and G. Assumption 2. For all x. y, t. G. and i, y., =g) = = - (1,,""=)))
X-r, Y T-)) = Pr((**=-jj) -(x=r)
Our problem setting can alternatively be described from the reinforcement learning (RL) perspective, where feature vectors are the states of Markov decision process, predictions the actions taken by an agent, and DIO is the reward received after the agent takes an action (makes a prediction) given a state (feature vector). From this perspective, Assumption [ asserts that rewards given an action do not depend on the particular policy that selected the action.
To define long-term fairness, we consider k delayed-impact objectives, 9i : O R.j E (1,..., kj, that take as input the parameters, 0, of a classifier, and return a real-valued measurement of fairness in terms of delayed impact. Then, we say that classifier is fair in the long term iff gj all j. To simplify notation, we assume there exists only a single DI objective (i.c., k = 1) and later show how enforce multiple DI objectives (see Algorithm 3). We focus on the case in which each DI objective is based on a conditional expected value having the form
S 0 for
g(0)= == E (eX,Y,TT)
where E IR is tolerance and c(X,, 7) 7) is Boolean conditional relevant to defining the objective. Notice that this form of DI objective allows us to represent DI fairness notions studied in the literature such as Liu et a long-term improvement To make ( more concrete, consider our running example, where a bank wishes to enforce a fairness definition that protects a disadvantaged group, A. In particular, the bank wishes to ensure that, for model no being considered, the future financial well- being-in terms of savings rate- of applicants in group A (impacted by To 's repayment predictions) does not decline relative to those induced by the prepiously-deployed model, B. In this case, T is the financial well-being of an applicant months after the loan application, and e(X, T) is the Boolean event indicating if an applicant in group A. Lastly, 7 could represent a threshold on which the bank would like to improve, such as the average financial well-being of type A applicants given historical data collected using B; i.e.,
>n IT, A]. where [-] denotes the Iverson bracket and n. = Ei [Ta All is the number of applicants of type A. In this setting, the bank is interested in enforcing the following delayed-impact objective: E T A) 2 т. Then, defining g(f) = т - | = A] ensures that g(0) < 0 iff the new model Tq satisfies the DI objective. Notice that an additional constraint of the same form can be added to protect other applicant groups.
2.1 ALGORITHMIC PROPERTIES OF INTEREST
As discussed above, to enforce long-term fairness we should ensure that g(0) S 0, since this delayed- impact objective implies that 0 (the model returned by classification algorithm) is fair with respect to DI. However, this is often not possible, as it requires extensive prior knowledge of how predictions influence DI. Instead, we aim to create an algorithm that uses historical data to reason about its confidence that g(o) S 0. That is, we wish to construct a classification algorithm, a, where oDD) E O the solution returned by a when given dataset D as input, that satisfies DI constraints of the form
Pr(g(a(D)) < 0) 2 8,
(2)
"Our algorithm works with arbitrary performance objectives, not just accuracy.
ELF can also provide high-confidence guarantees for other forms of DI objectives (Appendix
3

---

Under review as a conference paper at ICLR 2023
where 5 E (0, 1) limits the admissible probability that the algorithm returns unfair model with respect to the DI objective. Algorithms that satisfy (2) are called Seldonian (Thomas et al. 2019).
In practice, there may be constraints that impossible to enforce simultaneously (Kleinberg et al. 2016), or there may be insufficient data to ensure fairness with high confidence. Then, the algonithm should be allowed return "No Solution Found" (NSF) instead of a solution it does not trust. Let NSF E ④ and g(NSF) = 0. indicating it is fair for the algorithm to say "I am unable to ensure faimess with the required confidence." " Note that fair algorithm can trivially satisfy (2) by always returning NSF instead of a model. Ideally, if a nontrivial fair solution exists, the algorithm should be able to identify it given enough data. We call this property consistency and formally define in Section
Our goal is to design a fair classification algorithm that satisfies two properties: 1) the algorithm satisfies (2) and 2) the algorithm is consistent, i.c., if nontrivial fair solution exists, the probability that the algorithm returns a fair solution (other than NSF) converges to one as the amount of training data increases. Section 4 we prove that our algorithm, ELF, satisfies both properties.
METHODS FOR ENFORCING DELAYED IMPACT
According to our problem statement, fair algorithm must ensure with high confidence that g(0) S O, where 0 is the returned solution and g(0) = T E| to historical data, D, only samples of Is (the delayed impact induced by predictions made by 3) are available. In this section, we show how one can construct i.idd estimates of _ using samples collected using B. Then, we show how confidence intervals can be used to derive high-confidence upper bounds on gf). Lastly, we provide pseudocode for our algorithm, ELF, which satisfies (2)
|et_ lc(X, Y. T) Because ELF only has access
3.1 DERIVING ESTIMATES OF DELAYED IMPACT
First, notice that the distribution of delayed impact observations in D results from predictions made by the model B. However, our goal is to evaluate the delayed impact of a different model, πe. This is challenging: given data that includes the DIO resulting from predictions of a previously-deployed model, 3, how to estimate what would the delayed impact be if To were used instead? One naive solution is to run my on held-out data. However, this would only produce predictions y not their corresponding delayed impact; that is, each sample's DIO would still be in terms of 3, not Te.
We solve this problem using off-policy evaluation methods from the RL literature; these use data from running one policy (decision-making model) to predict what would happen if different policy had been used. Specifically, we use importance sampling (Precup et al. 2001) to obtain a new random variable, i=0, constructed using data from 3, such that 1 is an unbiased estimator of F=:;
E E |o(X (X E Y(X,Y,T))
In particular, for each data point in D, the importance sampling estimator, f weights the observed delayed impacts 1 based on how likely the prediction Y is under Ty. If T. would make the label ÿ.8 more likely, then Id is given a larger weight (at least one), and if To would make G less likely, then n given a smaller weight (positive, but less than one). Formally, the importance sampling estimator is fT = (X, & 3Xx, -1,, where the term (X, / ys) is called the importance weight.
Next, we introduce a common assumption in the importance sampling literature: predictions that are possible under π. also have non-zero probability of occurring under the behavior model (Assump- tion 3. In Section 3.3 we discuss a practical way in which this can be ensured. Theorem [ then establishes that the importance sampling estimator is unbiased, i.e., it satisfies (3).
Assumption (Support). For all x and y. we (x, y) > 0 implies that 3(z, y) > O.
Theorem 1. Under assumptions
E f c( X, Y, T)] = T |c(X, Y.T).. Proof. Appendix C
In Appendix H we further discuss the intuition underlying Assumption B and others introduced later, and show that they common in prior work and reasonable in many real-life settings.
4

---

Under review as a conference paper at ICLR 2023
3.2 BOUNDS ON DELAYED IMPACT
This section discusses how to use unbiased estimates of g together with confidence intervals to derive high-confidence upper bounds on g()). While different confidence intervals for the mean can be used to derive these bounds, to make our method concrete, we consider the specific cases of Student's t-test (Student [908) and Hoeffding's inequality (Hoeftding) I963). Consider vector of m i..d. samples (2+) of a random variable Z; let the sample mean be Z Σ Z,, the sample standard deviation be oZi,.... Zm)
Ei=1 (Z, 2)2, and 8 E (0,1) be a confidence level.
Property 1. Ef Zi is normally distributed, then
Pr E[Z.] Z abrr,.. L.n) 11 (1-8m-))) 21 8,
Vmn
where 51-5m-1 is the 1 - å quantile of the Student's 's t distribution with m -1 degrees of freedom Proof. See the work of [Studenn 1908).
Property [ can be used to obtain a high-confidence upper bound for the mean of Z:
Utcase Zi,... Zm) Z 2(2))))2m) f1-d.m=-1. Let be vector of i.i.d. and unbiased estimates of g(0). Once these are computed (using importance sampling: see Section 3.1), they can be provided to ULcon derive high-confidence upper bound on g(0): Pr(r [ Y, T)] S ULian (g) 2 1- Our strategy for deriving nigh-confidence upper bounds for delayed-impan objectives is general and other confidence intervals for the mean can be used. Student's 's t-test may be used and holds exactly if the distribution of Σ Zi is normal
Vm
4 A Alternatively, in Appendix D we describe bound based on Hoeffding's s inequality (Hoeffding] 1963), which replaces the normality assumption with the weaker assumption that is bounded. This results in different function for the upper bound, Unoetr.
3.3 COMPLETE ALGORITHM
Algorithm 1 ELF
Input: 1) D = {(X,, Y,, T, 9.s 12)) 2) confidence level 8; 3) tolerance value т; 4) behavior model ;;; and 5) Bound E {Hoeff, ttest).
Output: Solution 0. NSF.
I: De, < (D)): nD, length(Dr); 2: 0. + mingge cost(e, De, 8, T, Bound, no,)
3: for E (1,..., nD, do
Let (X3, Y,, F P/ .19) the 8hh data point in Dy
(X, 8.9) 83
5: if Y, T3) is True then g.append T
end if
6: end for
Bound is Hoeff then U (ū) else if Bound is ttest then U UELost (g) end 8: if U 2 0 then return NSF else return 6
Algorithm provides pseudocode for ELF. Our algorithm has three main steps. First, the dataset D is divided into two datasets (line 1). In the second step, candidate selection (line 2), the first dataset, De. used find and train model, called the candidate solution, 6g. This step detailed in Algorithm 2 (see Appendix mp. In the fairness test (lines 3-8), the dataset D, is used to compute unbiased estimates of g(O.) using the importance sampling method described in Section 3.11ion3..1 These estimates are used to calculate (1-8)-confidence upper bound, U, on g(f.), using Hoeffding's 's inequality or Student's s 1-test (line 7). Finally, U is used to determine whether 0, or NSF returned.
Recall that for importance sampling to produce unbiased estimates of g(O.), Assumption must hold. To ensure this, we restrict to only include solutions that satisfy Assumption
Assumption 4. Every 0 Q satisfies Assumption
This can be achieved by ensuring that 3 has full support: for all and g. B(x, () >0. Many supervised learning algorithms already place non-zero probability on every label (e.g.. when using Softmax layers in neural networks); in these commonly-occurtin
cases, Assumption is trivially satisfied.
By the central limit theorem, this approximation is reasonable for sufficiently large m.
5

---

Under review as a conference paper at ICLR 2023
4 THEORETICAL RESULTS
This section shows that 1) ELF ensures delayed impact fairness with high confidence; that is, is guaranteed to satisfy DI constraints defined in ② and 2) given reasonable assumptions about the DI objectives, ELF is consistent. To begin, we make an assumption related to the confidence intervals used bound g(0.), where 0g is returned by candidate selection. Specifically, we assume that the requirements related to Student's ' t-test (Property I or Hoeffding's 's inequality (Property 2 see Appendix D are satisfied. Let Avg(Z)= n2 Σ Z, be the average of a size nz vector Z.
Assumption 5. If Bound is Hoeff, then for all {i,..., k), each estimate in 95 (in Algorithm is bounded in some interval [aj, by]. If Bound is ttest, then each Avg(ū;) is normally distributed
Theorem 2. Let ( be a sequence of DI constraints, where 9j O R, and let (5,) be the corresponding confulence levels, where each 63 E (0,1). Under Assumptions 77 and if algorithm is Algorithm 3 then for all j E k). (r()) < 0) 2 8y. Proof. See Appendix F O
ELF satisfies Theorem 2 if the solutions it produces satisfy 2 i.e., if E (1...., k}. (a())(((D) <
0) 2 1 -1-60 6,. where is Algorithm 3 Because Algorithm 3 is extension of Algorithm I multiple constraints, it suffices to show that Theorem 2 holds for Algorithm 3 Next, we show that ELF is consistent, i.e., that when a fair solution exists, the probability that the algorithm returns solution other than NSF converges to 1 as the amount of training data goes to infinity:
Theorem (Consistency guarantee). If Assumptionss 71 [ are given in Appendix G hold, then lima- Pr(a(D) NSF,g(a(D)) s 0) 1. Proof. Metevier et al. provide similar proof for Seldonian contextual bandit algorithm. Appendix G adapts their proof.
Proving Theorem 3 requires mild assumptions: 1) that the cost function used to evaluate classifiers is smooth; 2) that at least one fair solution exists that is not on the fair-unfair boundary; and 3) that the sample performance of a classifier converges to its true expected performance given enough data.
EMPIRICAL EVALUATION
We empirically investigate three research questions: RQ1: Does ELF enforce DI constraints with high probability, while existing fairness- aware algorithms do not? RQ2: What is the cost (e.g.. in terms of accuracy) of enforcing constraints? RQ3: How does ELF perform when predictions have little influence on DI relative to other factors outside of the model's control?
We consider classifier tasked with making predictions about people in the United States foster care system; for example, whether youth currently in foster care are likely to get a job in the near future. These predictions may have a delayed impact on the person's life if, for instance, they influence whether that person receives additional financial aid. Here, the goal is ensure that a classifier is fair with respect to DI when considering race. Our experiments use two data sources from the
$ 'ELF works with any confidence intervals for the mean. Assumption 5 reasonable in many real-life settings, and Hoeffding's inequality and Student's 's t-test are effective and commonplace in the sciences (Appendix H.
Failure Rate of Constraint 1
100%
Failure Rate of Constraint 2
80%
Nintur with Dr
Nahharm with Egpidd
60%
Nimress Constrants
60%-
Nedmam Admbvable Presubility Lenarnss
40%
QSA with Eedop
40%
QRA with Ft
QSA with Dalms
20%
20%
0%
0%
10a
10a
10*
10a
10a
10a
Amount of Training Data (n)
Amount of Training Data (n)
Figure 1: Methods' failure rates w.r.t. DI constraints associated with White people (left) and Black people (right). Black lines show the maximum admissible probability of unfaimess, dp 01
10%.

---

Under review as a conference paper at ICLR 2023
National Data Archive on Child Abuse and Neglect (NDACAN, 2021]: 1) the Adoption and Foster
Care Analysis and Reporting System, containing demographic and foster care-related information about youth; and 2) the National Youth in Transition Database (Services and Outcomes), containing information about the financial and educational status and well-being of youth over time and during their transition from foster care to independent adulthood.
In this setting, the feature vector X contains five attributes related to the job and educational status of a person in foster care. The sensitive attribute, T, corresponds race-whether a person identifies as White or Black. The classifier is tasked with predicting a binary label. Y. denoting whether person has a full-time job after leaving the program. We modify this dataset by resampling the original labels in way that ensures the likelihood of being employed after leaving the program depends on both X and T. The behavior model, B3, corresponds to logistic regression classifier.
To investigate our research questions, we evaluate ELF in settings where predictions made by a classifier may have different levels of influence on DI. We model such settings by constructing a parameterized and synthetic definition of DI. Let 1," be the delayed impact observation for person i a classifier & outputs the prediction Y:¹ given X., Here, (1x, D) == Pr(Y;-=)) X.= We define 1 as
(aP + (1 -1 (2, if =
If = aa + (1- (1),
(4)
1,
where a regulates whether DI is strongly affected by classifier's predictions or if predictions have little to no delayed impact. We refer to the former setting as one with high prediction- DI dependency and to the latter setting as one with low prediction-DD DI dependency. As a goes to zero, predictions made by the classifier have no DI. In our experiments, we vary a from zero to one in increments of 0.1; for each value of a, we construct a corresponding dataset by using (4) to assign a DIO to each instance in the foster care dataset. When doing so, &b is defined as the behavior model, S.
We wish to guarantee with high probability that the DI caused by a new classifier, Rg, is better than the DI resulting from the currently deployed classifier, 3. This guarantee should hold simultaneously for both races: White (instances where T = 0) and Black (instances where = 1). We model this requirement via two DI objectives, go and g1- Let t {0, 1} and go) T E [ t), where T: - Ei L [Ta '] is the average DIO caused by 8 on people of race T = t and where Toe
T2 = EE [Ta = t]. The confidence levels ón and ô1 associated with these objectives are set to 0.1.
RQ1: Preventing delayed-impact unfairness. To study RQ1, we evaluate whether ELF can prevent DI unfairness with high probability, and whether existing algorithms fail. ELF is the first method capable of ensuring delayed-impact fairness when an analytical model describing the relationship between predictions and DI is not known, and the algorithm only has access to historical data. To the best of our knowledge, no other method in the literature ensures DI fairness in this setting (see Section (6. Thus, we compare ELF with the closest fairness-aware methods that do not require model of the prediction-DD DI dependency nor assume that one can be estimated. In particular, we consider three state-of of thethhe-rt tatrness-awann algorithms that are designed to enforce static constraints: 1) Fairleam (Agarwal et al.] 22018). 2) Fairness Constraints (Zafar et al. (017)) and 3) quasi-Seldonin Seldonian algorithms (QSA) (Thomas et al. 2019). We consider five static fairness constraints: demographic parity (DP), equalized odds (EqOdds), disparate impact IDisImp), equal opportunity (EaOpp), and predictive equality (PE) (Chouldechoval 2017 Dwork et al. 2012] Hardt al. 2016) We also compare ELF with a baseline faimess-unawwre unaware algorithm: logistic regression (LR).
This section studies how often each fairness-aware algorithm returns an unfair model (with respect to the DI constraints) as function of the amount of training data, n. We refer to the probability that an algorithm returns an unfair model as its failure rate. To measure the failure rate, we compute how often the classifiers returned by each algorithm are unfair when evaluated on significantly larger dataset, to which the algorithms do not have access during training time. To investigate how failure rates are influenced by the level of prediction-D) DI dependency, we vary between 0 and 1. Due to space constraints, below we discuss one representative experiment conducted by setting a = 0.9. The qualitative behavior of all algorithms for other values of a is similar. The complete set of results and details about our ELF implementation can be found in Appendix
Figure I presents the failure rate of each algorithm as function of the amount of training data. We computed all failure rates and corresponding standard errors over 500 trials. Notice that the solutions
We task each competing method with enforcing the constraints analyzed in those methods' original papers.
7

---

Under review as a conference paper at ICLR 2023
100%
100%
Probabliit babbbblllyy of Solution
80%
80%
Accuracy
Lt
60%
Paiream with
60%
Parream Exoccs
40%
Parmesa Corptr
40%
20%
whth
20%
0SA Diamp
0%
0%
10a
10a
10
10a
10a
Amount of Training Data (n)
Amount of Training Data (n)
(a) Accuracy.
(b) Probability of returning solution.
Figure 2: On the left, the accuracy of solutions returned by algorithms (subject different fairness constraints) as function of n. On the right, the probability that these algorithms return solution.
returned by ELF are always fair with respect to the DI constraints This is consistent with ELF's theoretical guarantees, which ensure with high probability that the solutions returns satisfy all fairness constraints. Existing methods that enforce static faimess criteria, by contrast, either 1) always fail to satisfy both constraints; or 2) always fail to satisfy one the constraints- one related to delayed impact on Black youth-while often failing to satisfy the other constraint.
RQI: Our experiment supports the hypothesis that with high probability ELF is fair with respect to DI objectives, and that comparable fairness-aware aware techniques do not ensure delayed impact fairness.
The cost of ensuring delayed-impact fairness. Previously, showed that ELF is capable of satisfying DI constraints with high probability. Depending on the data domain, this may come at a cost. First, there may be trade-off between satisfying fairness constraints and optimizing accuracy. In Appendix bounding accuracy loss. Here, we investigate the impact that enforcing DI constraints has accuracy. Figure 2a presents the accuracy of classifiers returned by different algorithms as a function of n. In these experiments, we bound accuracy loss via additional constraint requiring that ELF's solutions have accuracy of at least 75%. Under low-data regimes (n=1,000), ELF's 's accuracy is 83%, while competing methods (with no DI fairness guarantees) have accuracy higher than 90%. Importantly, however, notice that whenever competing methods have higher accuracy than ours, they consistently return unfair solutions. ELF, by contrast, ensures that all fairness constraints are satisfied with high probability and always returns solutions with accuracy above the specified threshold (see Figure Furthermore, notice that as n increases, ELF's accuracy approaches that of the other techniques.
RQ2:
E we show how ELF can be tasked with satisfying DI fairness constraints while also
Second, there may be trade-off between the amount of training data and the confidence that fair solution has been identified. Recall that some methods (including ELF) may not return a solution they cannot ensure faimess with high confidence. Here we study how often each algorithm identifies a candidate solution as a function of n. Figure 2b shows that ELF returns solutions with 91% probability when given just n=4,096 samples. As increases, the probability of ELF returning solutions increases rapidly. Although three competing techniques (Fairlearn, Fairness Constraints, and LR) always return solutions, independently of the amount of training data, these solutions never satisfy both DI constraints (see Figure[] QSA often returns candidate solutions with less training data than ELF; these solutions, however, also fail to satisfy both DI constraints simultaneously.
While there is cost to enforcing DI constraints depending on the data domain, ELF succeeds in its primary objective: to ensure DI fairness with high probability, without requiring unreasonable amounts of data, while also bounding accuracy loss.
RQ2:
RQ3: Varying prediction-Dt dependency. Finally, we investigate ELF's performance (in terms of failure rate, probability of returning solutions, and accuracy) settings with varied levels of prediction-DI dependency. These include challenging cases where predictions have little influence on DI relative to other factors outside of the model's control.
7 ELEE' does not return solutions with n < 1,000 bocause it cannot ensure DI fairness with high confidence. As before, we use a=0.9 and 500 trials. Results for other values of Appendix
8

---

Under review as a conference paper at ICLR 2023
100%
1:1
Probabal of Solution
80%
80%
80%
Falture Rate
Accuracy
600
Musmum Admizaable Prodeslll Unthiiness
40%
40%
40%
20%
0%
0%
0%
10:
10a
Amount Waining Data (n)
Amount Training Data (n)
Amount of Training Data [n]
(a) Failure rate.
(h) Prohability of returning solution.
(c) Accuracy.
Figure 3: ELF's performance in settings with different levels of prediction-D dependency.
We first study ELF's failure rate (probability that the returned model is unfair) for different values of a. Figure Ba shows that ELF never returns unfair models, independent of a, confirming empirically that ELF's high-probability fairness guarantees hold in settings with a wide range of qualitatively different DI characteristics. Next, investigate how often ELF identifies and returns solution for various values a. We expect that if the predictions made by a classifier have little to no DI (i.e., for low values of a), becomes harder-if not impossible-for ELF to be confident that it has identified a model satisfying all DI constraints. This is because it becomes harder to differentiate the small delayed impact predictions from noise. In these cases, we expect it would be less likely for ELF to return solutions. Figure (3b] illustrates this behavior. Notice that ELF returns solutions under all > if given sufficient training data. However, as expected, the probability that it returns a solution decreases as approaches zero. Lastly, we investigate how the amount of prediction-DI dependency affects the accuracy of ELF's 's solutions. Figure 3e shows the model accuracy, for various values of a, as function of n. The accuracy trade-off is more evident when ELF must satisfy challenging DI objectives, as a approaches zero. In such cases, accuracy decreases from 90% to 84%. Importantly, however, even though trade-off exists, notice that method is successful at bounding the accuracy of returned solutions while ensuring DI fairness constraints with high confidence.
RQ3: Our experiments confirm that ELF performs well in wide range of settings, with various levels of prediction-DI dependency. Even though ensuring fairness may impact accuracy and the probability of finding solutions, these unavoidable, domain--pecific trade-offs do not affect ELF'S fairness guarantees. In our experiments, all returned models satisfy both DI constraints.
RELATED WORK
Most prior work on the social implications of ML study static fairness without considering the
long-term impact of model decisions (Dwork et al. 2012 Hardt et al. 2016; Zafar et al., 2017). Recent research, however, has focused on long-term fairness (Hu & Chen 2018a b) Liu et al. 2018
D' D'Amuur al.) 2020 Heidari al.) 2019 Zhang et al.) 2020a We build upon this work and present the first method that provides high-confident delayed- -imacet fairness guarantees when only historical data is available, and the relationship between predictions and delayed impact is not known.
We now briefly discuss the methods that are most similar to ELF. These, and other related techniques, detailed in Appendix K Wen et al. (2019) introduce method that ensures that static fairness constraints (e.g., demographic parity) hold for all time during sequence of decisions. We study the orthogonal problem of ensuring fairness with respect user-defined delayed impact measures. The method proposed by TTng et al. (2020) considers the online multi-armed bandit setting; this algorithm does not differentiate individuals within a group while making decisions. We. by contrast, tackle the problem of high-confic coghhcoofideece fairness in the classification setting. ZZhang et al. (0020b) investigate the long-term effects of repeatedly deploying myopic policies that optimize static fairness constraints. Importantly, they assume knowledge of analytical models characterizing whether an individual will be qualified (e.g., likely to repay a loan) at a given time. Ge et al. (202I) and Hu Zhang (2022) train classifiers that satisfy static fairness constraints in non-stationary settings (e.g.. recommendation systems where a person's s interests may change over time). Importantly, however, both Ge et al. (2021) and Hu & Zhang (2022) require knowledge of analytic models of the environment. ELF, by contrast, does not require a model or simulator of the environment, nor prior knowledge about the relationship between classifier's predictions and the resulting delayed impact.

---

Under review as a conference paper at ICLR 2023
REFERENCES
Alekh Agarwal, Alina Beygelzimer, Miroslav Dudik, John Langford, and Hanna Wallach. A reductions approach fair classification. 35th International Conference on Machine Learning. pp. 60-69, 2018. URL/attts::/pproeeeee ngs mmlr. www.sppesssseee wwtppp/ssssssseepeepeepppe wwtp/////aaaaaaaaaaaaaaa 8a a. html
Jason Altschuler, Victor-Emmmnuel Brunel, and Alan Malek. Best arm identification for contaminated bandits. Journal of Machine Learning Research, 20(91):1-39, 2019. URL https:://mll
orc/papers/v20/15
Robert Bartlett, Adair Morse, Richard Stanton, and Nancy Wallace. Consumer-lending discrimination in the FinTech era. Journal of Financial Economics, 145(1):30-56 2021. doi: 111101666.ffinece 2021.05. 2021.05.047.
Joseph Blass. Algorithmic advertising discrimination. Northwestern University Law Review 114:415 468, 2019. htttps://schhllrlyycoomms law. www.noortwwstere..co. nulr/vol111 11 1ss2/3/
Toon Calders, Faisal Kamiran, and Mykola Pechenizkiy. Building classifiers with independency constraints. In 2009 IEEE International Conference on Data Mining Workshops, pp. 13-18. IEEE, 2009. doi: 10. 101110//CDM..0000
Yash Chandak, Scott Nickum, Bruno Castro da Silva, Erik Learned-Miller Emma Brunskill, and Philip S Thomas. Universal off- off-policy evaluation. arXiv preprint arXiv:2 /2820, 2021.
Jianfeng Chi, Jian Shen, Xinyi Dai, Weinan Zhang, Yuan Tian, and Han Zhao. Towards return parity in markov decision processes. In International Conference on Artificial Intelligence and Statistics, AISTATS, volume 151, pp. 1161-1178, 2022.
Children's 's Bureau, Administration on Children, Youth and Families. National Data Archive on Child Abuse and Neglect (NDACAN). 2021. URL https: //wtp. www.annannn...mm acf. hhs gov/
Alexandra Chouldechova. Fair prediction with disparate impact: A study of bias in recidivism prediction instruments. Big Data, 5(2)) 2017. doi: 10. 2..1009/i..2016.0044
Sam Corbett-Davies, Emma Pierson, Avi Feller, Sharad Goel, and Aziz Huq. Algorithmic decision making and the cost of faimess.. In Proceedings of the 23rd ACM International Conference Knowledge Discovery and Data Mining, pp. 797-806, 2017.
Alexander D' Amour, Hansa Srinivasan, James Atwood, Pallavi Baljekar, D Sculley, and Yoni Halpern. Fairness is not static: Deeper understanding of long term fairness simulation studies. In Proceedings of the 2020 Conference on Fairness, Accountability, and Transparency, pp. 525-534, 2020. doi: 10. 145/335 1095.3372878
Cynthia Dwork, Moritz Hardt, Toniann Pitassi, Omer Reingold, and Richard Zemel. Fairness through awareness. In Proceedings the 3rd Innovations in Theoretical Computer Science Conference, pp. 214-226, 2012. doi: 10.1 1,2114//990336229992555
Alexandre Flage. Ethnic and gender discrimination in the rental housing market: Evidence from meta-analysis of correspondence tests, 2006-2017. Journal of Housing Economics, 41:251-273, 2018. doi: 10.1016/j. 2018.........777.
Yingqiang Ge, Shuchang Liu, Ruoyuan Gao, Yikun Xian, Yunqi Li, Xiangyu Zhao, Changhua Pei, Fei Sun, Junfeng Ge, Wenwu Ou, et al. Towards long-term fairness in recommendation. In Proceedings of the 14th ACM International Conference on Web Search and Data Mining, pp- 445-453, 2021.
Nikolaus Hansen and Andreas Ostermeier. Completely derandomized self-adaptation in evolution strategies. Evolutionary Computation. 9(2::159-195, 2001. doi: 10.1162/
11382355.
Moritz Hardt, Eric Price, and Nati Srebro. Equality of opportunity in supervised learning. In Advances in Neural Information Processing Systems 29, pp. 3315-3323, 2016.
10

---

Under review as a conference paper at ICLR 2023
Hoda Heidari, Vedant Nanda, and Krishna Gummadi. On the long-term impact of algorithmic decision policies: Effort unfaimesss and feature segregation through social learning. 36th International Conference Machine Learning, pp.
2019. URL https:/pprrceedgggggg mllr
preas/v97/he dari i 9a. html
Wassily Hoeffding. Probability inequalities for sums of bounded random variables. Journal of the American Statistical Association, 58(301):13-30, 1963. doi: 10. 1459.1963 10500830.
Lity Hu and Yiling Chen. A short-term intervention for long-term faimess in the labor market. In Proceedings of the 2018 World Wide Web Conference, pp. 1389-1398, 2018a. doi: 10.1145/ 7778876.3186444
Lily Hu and Yiling Chen. Welfare and distributional impacts of fair classification. arXiv preprint arXiv:1807.01 1344. 2018b.
Yaowei Hu and Lu Zhang, Achieving long-term fairness in sequential decision making. In 36th AAAI Conference on Artificial Intelligence, 2022.
Ramtin Keramati, Christoph Dann, Alex Tamkin, and Emma Brunskill. Being optimistic to be conservative: Quickly learning a CVaR policy. Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pp. 4436-4443, 2020. doi: 10. 10.6/0/aa 20.16992aai.v44444..55 v34104.5870.
Jon Kleinberg. Sendhil Mullainathan, and Manish Raghavan. Inherent trade-offs in the fair determi- nation of risk scores. arXiv preprint arXiv: 2016.
Lydia Liu, Sarah Dean, Esther Rolf, Max Simchowitz, and Moritz Hardt. Delayed impact of fair machine learning. In 35th International Conference Machine Learning, pp. 3150-3158, 2018. URL
mlr httpp//eed.aaaa......rreeea//a/a
poress/va0/Iiulee html
Blossom Metevier, Stephen Giguere, Sarah Brockman, Ari Kobren, Yuriy Brun, Emma Brunskill, and Philip Thomas. Offline contextual bandits with high probability fairness guarantees. In Advances in Neural Information Processing Systems 32, 2019.
Hussein Mouzannar, Mesrob Ohannessian, and Nathan Srebro. From fair decision making to social equality. In Proceedings the Conference on Fairness, Accountability, and Transparency, pp. 359-368, 2019. doi: 10.1 00.1145/2875500.2277573
Doina Precup, Richard S. Sutton, and Sanjoy Dasgupta. Off-policy temporal-diiference learning with function approximation. In 18th International Conference on Machine Learning, pp. 417-424, 2001.
Babak Salimi, Luke Rodriguez, Bill Howe, and Dan Suciu. Interventional faimess: Causal database repair for algorithmic fairness. International Conference on Management of Data (SIGMOD), pp. 793-810, 2019. doi: 10. 145/3299869.331999
Pranab K. Sen and Julio M. Singer. Large Sample Methods Statistics: Introduction with Applications. Chapman & Hall, Boca Raton, FL., 1993.
Student. The probable error mean. Biometrika, 6(1):1-25, 1908. doi: 10.2307/2331554.
Wei Tang, Chien-Ju Ho, and Yang Liu. Bandit learning with delayed impact of actions. arXiv preprint arXiv:2002. 103 2020.
Philip S Thomas, Bruno Castro da Silva, Andrew G Barto, Stephen Giguere, Yuriy Brun, and Emma Brunskill. Preventing undesirable behavior intelligent machines. Science, 366(6468))999-1000)) 2019. doi: wt.1126/siencc..aag
Sahil Verma, Michael Emsst, and René Just. Removing biased data to improve faimess and accuracy. arXiv preprint arXiv: 202.00000 2021.
Min Wen, Osbert Bastani, and Ufuk Topcu. Fairness with dynamics. arXiv preprint arXiv:1901.0850 2019.
11

---

Under review as a conference paper at ICLR 2023
Muhammad Bilal Zafar, Isabel Valera, Manuel Gomez Rogriguez, and Krishna P Gummadi. Faimess constraints: Mechanisms for fair classification. In 20th Artificial Intelligence and Statistics, pp. 962-970, 2017. URL httt:tt:pprrceednnng/ .ml...ssmm.r............mm.
Xueru Zhang, Mohammad Mahdi Khalili, and Mingyan Liu. Long-term impacts of fair machine learning. Ergonomics in Design, 28(3):7-11, 2020a. doi: 10. 10.1177/1044804419884111
Xueru Zhang, Ruibo Tu, Yang Liu, Mingyan Liu, Hedvig Kjellstrom, Kun Zhang, and Cheng Zhang. How do fair decisions fare in long-term qualification? In Advances in Neural Information Processing Systems, volume 33, pp. 18457-18469, 2020b.
A OTHER MOTIVATING EXAMPLES FOR ELF
In our paper discussed two important real-life examples where method could be applicd. First, we introduced a motivating problem where a bank wishes to take into account the delayed impact of lending decisions a disadvantaged group. Secondly, in our empirical evaluation considered the delayed impact of providing financial aid to youth in foster care. Here, we discuss three additional examples of possible applications of ELF in real-life settings:
Consider a university that has a 1-on-1 tutoring program. However, the university has limited resources and cannot offer tutoring for all students. To select which students should participate the program, the university's 's decision is based on GPA predictions. Receiving tutoring (or not) can influence the chances of student graduating from college. In this case, the delayed impact observation could be whether a student graduated or not. The university has access to this DIO both for students that received tutoring and for those who did not.
Consider police department deciding which crime prevention strategy to use in each district of a city, based on predictions about crime recidivism. DI could be the average incarceration rate in each district two years after this decision; it could indicate, e.g., that people of particular race are unfairly affected by the strategies deployed by the policy department.
Assume that medical decisions are influenced by predictions whether person qualifies for high-risk care management. These predictions may have DI on a person's health; e.g.. the severity of chronic illnesses two years the future. Different demographic groups may be affected differently in the long term.
B LIMITATIONS
ELF requires access representative historical data-i.e. a dataset with observations of the delayed impact resulting from different predictions. For example, consider a college whose admissions decisions are informed by a classifier predicting students' academic performance. These predictions may have a delayed impact, e.g., on whether the student will be employed after graduation. However, the college would only have access to this information about admitted students; this case, ELF would not be applicable. Nonetheless, in many important real-life settings it is possible to observe the delayed impact of different decisions (see Appendix [A). For instance, the lending example described in the paper, the bank can observe the delayed impact of lending decisions both for clients who received a loan and those who did n
Furthermore, ELF's high probability fairness guarantees only hold if the world has not changed between the time training data was collected and the time the trained classifier is deployed. While this (stationarity) assumption is common in ML, it may be challenging in our setting since gathering data that includes measures of long-term impact requires that a correspondingly long duration of time
Even though ELF may be affected by this limitation, argue that the assumption that our algorithm has access to representative dataset significantly less strict than the requirements and assumptions made by all existing techniques. Current state-of ofte-off-the-rr methods require access to complete and accurate models of the environment. Ensuring access to complete models, in practical applications, is qualitatively harder than ensuring access to representative datasets. Constructing models of this type could involve, e.g., designing analytic expressions descrihing how economic and social factors (both observed and latent) might affect given person's financial well-heing the future.
12

---

Under review as a conference paper at ICLR 2023
has passed. While providing guarantees when nonstationarity occurs is important future work, in this paper we focus on the important first step providing the first classification algorithm that provides gelayed-impact fairness guarantees in the stationary setting.
C PROOF OF THEOREM 1
Proof. At high level, we start with E[i" |c(X, Y,] and, through series of transformations
involving substitution, laws of probability, and Assumptions [+3] obtain E (c(X, Y)]. To simplify notation, throughout this proof we let C c(X, Y, T). Also, for any random variable Z, let supp(Z) denote the support of Z (e.g., is discrete, then supp(Z) = {a: Pr(Z = 2) > 0}). To begin, we substitute the definition of T and expand this expression using the definition of expected value:
To(X, P.
E 0 EE
1 C
3(X, Y3)
Σ Pr(X-x, Y T-,, -i()) Te (z. 0 [1x, y)
i.
(5)
Using the chain rule repeatedly, we can rewrite the joint probability in (5) as follows:
Pr( Pr
= =ttp::/.............000000111111
Under Assumption 0, P:(0))PP(P=))-=-- which is the definition of (xx, 9). We perform this substitution and simplify by cancelling out the 3 terms:
PX-xx, Y T-t[C) (I,
E E C (P=
f(x
- Pr Y- T (X (x,,)) (6)
Note that under Assumption (2r, 9) can be rewritten the multiplication rule of probability, we can combine this term with the Assumption 2 we term in 66) to obtain the joint probability Pr(X Y F"* By
Using X= X, T=t
substitute Pr[I==i]XXx, Y=y, T=t, " C) for Pr
T==,, T y C).
substitute these terms into (6) and apply the multiplication rule of probability once more:
1LiT0 = Σ Pr(1""=iXX== T y ne -
0)
8 J.1 7 =
(7)
(es..t.0.)))supp(X......
Finally, notice that by Assumption supp Fe) S supp ( and supp( S supp( So. we can rewrite as
T n. Pi f - =C)),
(a.y.t....) (aa.tt...eesmupp (supp( PT.,
By the definition of expectation, this is equivalent E _ [C] Therefore, we have shown that E Bi [ [C)
13

---

Under review as a conference paper at ICLR 2023
D BOUNDS ON DELAYED IMPACT USING HOEFFDING'S S INEQUALITY
This section focuses on how one can use the unbiased estimates of g together with Hoeffding's inequality (Hoeflding, 1963) derive high-confidence upper bounds on g(0). Given vector of m i.i.d. samples (2 1 of random variable Z, let = - Z; be the sample mean, and let 8 E (0, 1) be confidence level.
Property 2 (Hoeffding's Inequality). IfPr(Z [a, bl) then
In(1/6)
Pr
E
Z+ 2 2 (b- a)v
2 21-
2m
Proof. See the work of Hoeffding 1963).
Property 2 can be used to obtain high-confidence upper bound for the mean of Z:
log(1/6)
Unders (Z,, Lz.... Zm) = Z (b a)
(2m)
Let 9 be vector of i.idd and unbiased estimates of g(0). Once these are procured (using importance sampling as deseribed Section 3.1 they can provided Undeft to derive high-confidence upper bound on g(0):
Pr (T
is0 c(X, XX) < UH) 1
Notice that using Hoeffding's inequality to obtain the upper bound requires the assumption that is bounded.
E EXTENSIONS OF ELF
In this section we diseuss how ELF can be extended to provide similar high-confidence guarantees for the regression setting. for the classification setting with static fairness constraints, and for definitions of delayed impact objectives beyond the form assumed in
E. DELAYED-IMPACH FAIRNESS GUARANTEES IN THE REGRESSION SETTING
In our problem setting, we study fairness with respect delayed impact in the classification setting, in which the labels Y produced by a model are discrete. However, our method can also be applied in the regression setting, where (stochastic) regression model produces continuous predictions Y. instead of discrete labels. To use ELF in this setting, one may adapt Algorithm@ so that it uses a loss function suitable for regression; e-g., sample mean squared error. Furthermore, notice that the importance sampling technique described in Section 3. is still applicable in the regression setting, requiring only minor changes so that it can used in such a continuous setting. In particular, the importance sampling technique described can be adapted by replacing summations with integrals, probability mass functions with probability density functions, and probabilities with probability densities. By doing so, all results presented in work (e.g., regarding the unbiasedness of the importance sampling estimator) carry to the continuous case. Notice, finally, that in order to apply ELF in the regression setting, the behavior model, 3, and the new candidate model, πe. must be stochastic regression models-this is similar to the assumption we made when addressing the classification setting (see the discussion in Section
E.2 ENFORCING STATIC FAIRNESS CONSTRAINTS OR CONSTRAINTS MODEL PERFORMANCE
In Section 3 we showed how users can construct and enforce Selayed-impace fairness constraints. However, might also be interested in simultancously enforcing additional behavior- for instance, enforcing static fairness constraints or constraints on the primary objective (i.e., on the classification regression performance). Assume, for example, that the bank from running example has
14

---

Under review as a conference paper at ICLR 2023
constructed a sellaydd-imaace fairesss constraint of the form in I and that it is also interested in specifying an additional constraint that lower- bounds the model's performance in terms of accuracy. This could be represented by the following objective:
(PF = TPERF E[ACC,];
where TPERF E (0, 1) represents the minimum required accuracy, and ACC, is a random variable representing the accuracy of the model 0, i.e., the fraction of predictions that are correct given random dataset D.
Continuing the example, assume that the bank would also like to enforce static fairness constraint: false positive enror rate balance (FPRB) (Chouldechoval 2017), also known as predictive equal- ity (Corbett- et al. 2017). Recall that classifier satisfies an approximate version of FPRB the absolute difference between the false positive rates of two demographic groups of loan applicants, and B, below some user-specified threshold. The bank could specify this static fairness objective as:
OFPRB E y = =1/Y=0,T 0 A
E yT 11===1y- - 0, B
GPRBB
where EFPRB E (0, 1) is the threshold of interest.
Notice that-unlike delayed-impact objectives-gpeer and @FPRB can be directly computed using only labels Y. predictions yTHe and the sensitive attribute T: that is, information already available in the dataset or directly obtained from the model. In other words, the importance sampling method introduced in Section 3 would not be needed to obtain high-confidence bounds for these metrics. Metevier et al. (2019) and Thomas et al. (2019) present methods to compute high-confidence upper bounds on static fairness constraints and constraints on performance. Notice that SPERE and OFPRB are just examples of this type of constraints; the techniques introduced by Metevver et al. (2019) and Thomas et al. (2019) are applicable to more general objectives and constraints. We refer the reader to their work for more details.
To conclude our discussion of this example, notice that-once camputeddhigh--cmme high-confidence upper bounds on OPERF and @FprB may be used to determine whether candidate solution should be returned. Similar to line 11 of Algorithm if all computed upper bounds (with respect to the accuracy objective, the predictive equality objective, and the delayed-impact objectives) less than or equal to zero, then the candidate solution should be returned. Otherwise, NSF should be returned.
E.3 ALTERNATIVE DEFINITIONS OF DELAYED-IMPACY ORJECTIVES
Until now, we have assumed that the telayed-impace objective takes the form of ① Below, we discuss how users of ELF may construct other definitions of delayed-impan objectives, and how our formulation of delayed-impace objective (shown in (1) is related the definitions introduced in the work of Liu et al. (2018).
Connections to the work of Liu et al. (2018). Our DI objective (1) has the form g(0)
E [c(x, Y. Y.]) This is similar to long-term improvement, one of the notions of delayed impact introduced by Liu al. (2018). Specifically, Liu et al. (2018) define long-term improvement as Ap, > O, where for group J. Any is the difference between the DI induced by a previously-deplooe model and a new model. In their work, [iu et al. (2018) consider DI to be credit score. To enforee this type of long-term improvement in our framework, we can set T to be group j is average credit score under the current model (i.e., under the behavior model, (3) and
No T = j] to be the expected credit score of group j under the new model, a.. Then, Au;; E T T ý] - r. In our framework, a model is fair if g(0) < O. Setting g0) = T E [ [T = j] implies that the model is fair (i.e., g(0) < 0) if and only if 0 leads to long-term improvement (i.e., iff Aui 0).
We can also use ELF to enforce constraints similar to the remaining definitions of delayed-impact objective introduced by Liu et al. (2018); c.g., long-term decline (Apr 0) and long-tem stagnation (Ap, = 0). Notice that long-term decline has a form similar to long-term improvement: Âμd < 0 0 E 8 [ jl T. Alternatively, to enforce long-term stagnation users set = j. Moreover, to enforce approximate long-term stagnation, i.e., Adl < for some non-negative threshold e, users may set (0) |T E [7 TT j]
((0) T E |T E
15

---

Under review as a conference paper at ICLR 2023
Finally, notice that the definitions of long-term decline and stagnation do not have the same form as I nonetheless, these definitions can be enforced using the methods introduced in our work we discuss how to achieve this in the next section.
Enforcing general definitions of delayed-imp -impact objectives To enforce constraints beyond ( one can combine the importance sampling technique introduced in Section with techniques presented in the work of Metevier et al. (2019). Assume, for example, that the bank in our running example interested in enforcing that the resulting expected delayed impact
classifier's predictions is approximately equal for loan applicants of group A and group B. This can be represented by the DI
[1"0 = B] - e. To enforce the DI constraint considered in this paper (i.e., the one shown in 2 on the more general types of DI objectives discussed in this appendix (such as IDI), one may combine the techniques we introduced in this paper and the bound-propagation methods introduced by Metevier et al. case, first compute (as before) unbiased estimates of E
objective (0) = E -
A]
E
(019). At high-level, ELF would, in this 1 = A] and E [ B] using the Then, would use the gound-propaggan methods introduced by MMetevirr et al. (2019) to obtain high-confidence upper bounds on (D). Notice that the diseussion above corresponds to just one example of how to deal with alternative delayed-img -impeet objective definitions; in this particular example, 9DI- The same general idea and techniques can, however, also be used to deal with alternative definitions of DI objectives that users of ELF may be interested in 10 All other parts of the algorithm would remain the same-e.g- the algorithm would still split the dataset into two, identify a candidate solution, and check whether passes the fairness test.
importance sampling technique described in Section 3.1
Beyond conditional expectation. In Section 2 we assume that g is defined in terms of the condi- tional expected value of the delayed-impact measure. However, other forms of fairness metrics might be more appropriate for different applications. For example, conditional value at risk (Keramati et al. 2020) might be appropriate for iiskssensitive applications, and the median might be relevant for appli- cations with noisy data (Altschuler et al. (019)). Chandak et al. (202I) introduce off-policy evaluation methods that produce estimates and tigh-confidence bounds for different distributional parameters of interest, including value at risk, conditional value at risk, variance, median, and interquantile range. These techniques can also be combined with ours to obtain high-confidence upper bounds for metrics other than the conditional expected value of 1
F PROOF OF THEOREM 2 FAIRNESS GUARANTEE
This section proves Theorem 2 which is restated below, along with the relevant assumptions.
Assumption 1 A model's prediction P: is conditionally independent of Y and 7 given X. That is, for all x, t, y. and g.
Assumption For all x, y. f. G. i
= Pr(1==iXX Y y-,,T-I, 8 11,,-11888-1) - Y|X=rrY-n, T-1 8=00
Assumption (Support): For all x and y. (I y) > 0 implies that ((x, y) > 0. Assumption
4 Every 0 @ satisfies Assumption 3
Assumption bounded in some interval (ay, by]. If Bound is ttest, then each Avg(ū;) is normally distributed.
If Bound is Hoeff, then for all E {1,..., k). each estimate in O is
Thhis statement holds assuming that the objective interest satisties the requirements for the bound- propagation technique to be applicable; for example, that the DI objective can be expressed using elementary arithmetic operations (e.g., addition and subtraction) over base variables for which we know unbiased estima- tors (Metevier et al. 2019). In the case of the DI objectives discussed in this paper, for instance, we obtain unbiased estimates of the relevant quantities using importance sampling, discussed in Section 3.1
16

---

Under review as a conference paper at ICLR 2023
Theorem Let (0z) be sequence of DI constraints, where 9; θ - R, and let ( be a corresponding sequence of confidence levels, where each òz E (0, 1). If Assumptions and 5 hold. then for all j {I...., k}.
Pr(g)(a(D)) 0) > 8z.
We first provide three lemmas that will be used when proving Theorem 2
Lemma 1. Let 93 be the estimates of constructed in Algorithm 3 and let Ds be subdataser of Dy such that data point (X, K,Y,T, yo, 18) is only in Dj. c(X, T) is true. Then, for all 0 O the elements in Gj are i.i.d. samples from the conditional distribution of 9J given (X.YYT)
Proof. To obtain Φj. each data point in Dso is transformed into an estimate of g(0) using the importance sampling estimate _x 7 (Algorithm 3. lines 5-8). Since each element of وز 3(X,Y=)
is computed from single data point in Dr and the points in D are conditionally independent given c(X, T),,, it follows that each element of Ô is conditionally independent given c(X, Y, T). So, each element of Ú, can be viewed as an i.i.d. sample from the conditional distribution of 9, given c(X, Y,T).
Lemma 2. Let 9, be the estimates of g constructed in Algorithm 3 If Assumptionss 7 then for all E θ each element in 9J is an unbiased estimate of 9, (0).
2 and hold,
Proof. We begin by considering the expected value of any element in 9j:
To(X, c(X,Y,T)
To(X,
E
= -
E
c c(X,
88)
B(X,
=T E
pmo c(x, V,T)
=T E
_1 ((XXYYYT)
(8)
(g)
Expression (8) follows from Theorem ! which relies on Assumptions and Therefore, for all 0 E O, the elements of C, are unbiased estimates of gj (0).
Let fg be the model returned by candidate selection in Algorithm 3 (line 2), and let U, be the value of U at iteration j of the for loop (lines 4-10).
Lemma 3. Asssmmptss satisfy Vj E (L...., k). Pr(g U. U,
7 2
and 5 hold, then the upper bounds Uj calculated in Algorithm
Proof. We begin by noting that by Lemma I the data points used to construct each (1-6,) (1-6. prrobbbiiiyy bound, i.e., the data points in each Új. are (conditionally) i.i.d. Because 0, O, by Lemma (which uses Assumptions I and and 4p. Therefore, Hoeffding's s incquality or Student's t-test can be applied to random variables that are (conditionally) i.i.d and unbiased estimates of gj (0.). Moreover, under Assumption 5 when Bound is Hoeff, the requirements of Hoeffding's 's inequality are satisfied (Property ( and when Bound is ttest, the requirements of Student's f-test are satisfied (Property []] Therefore, the upper bounds calculated in Algorithm satisfy Pr(gz (O.) > U,) < 65.
know that each element in 9j is unbiased estimate of gj (P.).
Proof of Theorem
Samples that are conditionally i...d given some event E' can be viewed as i.i.d. samples from the conditional distribution. Applying the confidence intervals these samples therefore provides high-confidence bounds on the conditional expected value given the event F., which is precisely what aim to bound.
17

---

Under review as a conference paper at ICLR 2023
Proof. To show Theorem 2 prove the contrapositive, i..,, Vj (l....,,,, P), 0) - 6y.
Consider the event Vj {L,..., 9,
(a( g, that a(D) o NSF (by definition, g (NSF) = 0). That is, a nontrivial solution was returned by the
0. When this event occurs, it is always the
algorithm, and for all j. Ug (line 11 of Algorithm B. Therefore, (9) (shown below) holds.
Pr(g)(((D) > 0) = Pr (a(D)) 0,U, 50)
(9)
Sri(g (a()) > U,)
(10)
= =Pr(g, (0.) Uj)
(11)
(12)
Expression (1O) is result of the fact that the joint event in ( implies the event (g)(a(D)) > U2).
We substitute 0g for a(D) ) in (TT) because the event vj E {I...,,k k), g))g;((DD) > 0 implies that
nontrivial solution, solution that Lemma This implies that (r(g)(a(D) > > 0) s 5, Vj E {i,..., k}, completing the proof.
NSF, was returned: a(D) 8e. Lastly, (12) follows from
G PROOF OF THEOREM
This section proves Theorem restated below, Metevier al. (2019) provide a similar proof for Seldonian contextual bandit ggritthmm which we adapt to our Seldonian classification algorithm. Extending their proof to our setting involves the following minor changes:
1. Changes related the output of the function used to calculate the utility of solution: Metevier et al. 2019) consider a utility function that returns the sample reward of a policy, Instead, our utility function (Algorithm 2 outputs the sample loss of model.
2. Changes due to the form of the fairness constraints: The form of our delayed- relayed-impact con- straint differs from the more general form of the fairness constraints considered by Metevier et al. 2019). This results in simplified argument that our algorithm consistent,
Rather than reword their proof with these minor changes, below we provide their proof with these minor changes incorporated.
Theorem
Assumptions
8 hold, then lim Pr(a(D) # NSF, g(a(D)) s 5)== =
We begin by providing definitions and assumptions necessary for presenting our main result. To simplify notation, we assume that there exists only single delayed-impac constraint and note that the extension of this proof multiple delayed-impac constraints is straightforward.
Recall that the logged data, D, is a random variable. To further formalize this notion, let (Ω, p) be probability space on which all relevant random variables are defined, and let D, : Ω2 - D be random variable, where D is the set of all possible datasets and D, D. U Dy. We will discuss convergence as n -> co. (w(w) a particular sample of the entire set of logged data with n data points, where E Ω2
Definition (Piecewise Lipschitz continuous). We say that function f M + R on metric space (M, d) is piecewise Lipschitz continuous with Lipschitz constant and with respect to a countable partition, MM,,MM2..... of M if is Lipschitz continuous with Lipschitz constant K on all metric spaces in d)
Definition 2 (ō-covering). (M, d)) is metric space, set X C M is d-covering of (M,d) d) if and only if max min d(z, y) < 8.
JEM x
Let 6(8, D.) denote the output of a call to Algorithm 2 and let c(0) : Lmax + g The next assumption ensures that and are piecewise Lipschitz continuous. Notice that the 8-covering requirement straightforwardly satisfied is countable or θ C R.m for any positive natural number m.
18

---

Under review as a conference paper at ICLR 2023
Assumption 6. The feasible set policies, O is equipped with metric. de, such that for all De(w) there exist countable partitions of θ, e = {of. ). and @ { of...... where c(.) and d(:)).( are piecewise Lipschitz continuous with respect to H and e respectively with Lipschitz constants K and K. Furthermore, for all i No and all 0 there exist countable å-covers of o and e.
Intuitively, Assumption 6 states that (!) the cost function used to evaluate classifiers is smooth: similar classifiers have similar costs/performanees; and (2) each classifier can be described by a set of real-valued parameters, as is the case with all parametric supervised learning algorithms.
Next, we assume that a fair solution, 0*, exists such that g(0) is not precisely on the boundary of fair and unfair. This can be satisfied by solutions that are arbitrarily close to the fair-unfair boundary.
Assumption 7. There exists an > & and a 0 E θ such that g( S -E.
Intuitively, Assumption 7 states that the space of classifiers is not degenerate: at least one fair solution exists such that if we perturb its parameters infinitesimally, it would not become arbitrarily unfair. Next, we assume that the sample loss, É, converges almost surely to e, the actual expected loss.
Assumption 8. YO E O, D.) - ((0).
Intuitively, Assumption states that the sample performance of a classifier converges to its true expected performance given enough data. This is similar to the usual assumption, e.g., in the regression setting, that model's sample Mean Squared Error (MSE) converges to its true MSE given sufficient examples.
We prove Theorem B by building up properties that culminate with the desired result, starting with variant of the strong law of large numbers:
Property (Khintchine Strong Law of Large Numbers). Let {X.] be independent and identi- cally distributed random variables. Then ( Ei= X,) is a sequence of random variables that converges almost surely to E(X1). [[x] exists, iee, + X, a.s. E[Xi].
Proof. See Theorem 2.3.13 of Sen & Singer 1993).
Next, we show that the average of the estimates of g(0) converge almost surely to g(0):
Property 4. If Assumptions and hoold, then 40 E Avglg) as. g(o).
and Lemmas and hold, i.c., estimates in are i..d., and each estimate in ğ an unbiased estimate g(0) Also, recall that if ng the number of elements in j. Avg(ū)= = 1 Σ mg 0.. Then, by Property 3 we have that Avg(ū) as, g(0). ng
Proof. Recall that given Assumptions
In this proof, we consider the set θ C θ, which contains all solutions that are not fair, and some that fair but fall beneath certain threshold: θ (0 E θ g(0) > -// At high level, will show that the probability that the candidate solution, O.. viewed as a random variable that depends on the candidate data set D.. satisfies 0g & Ô converges to one as + oo, and then that the probability that 0- is returned also converges to one as n
Cc.
First, we will show that the upper bounds U (constructed in candidate selection, i.e., Algorithm 2 and U (constructed in the fairness test, i.c., Algorithm|] I converge to g(0) for all 0 E θ. To clarify notation, we write (+, D.) and (0, D2) to emphasize that each depends on 0 and the datasets D. and Dy, respectively.
Property 5. If Assumptions U(O, D,) a.s. (()).
and 5 hold, then for all 0 E O, (0, as, g(f) and
Proof. Given Assumption 5, Hoeffding's 's inequality and Student's f-test construct high-confidence upper bounds the mean by starting with the sample mean of the unbiased estimates (in case, Av)( and then adding an additional term (a constant the case of Hoeffding's 's inequality). Thus, U0, Dy) can be written A Avg(ū) (ğ) + Zm, where Z, is sequence of random variables that converges
19

---

Under review as a conference paper at ICLR 2023
(surely for Hoeffding's inequality, almost surely for Student's t-test) zero. So, Z, a.. 0, and need only show that Avg(O u.s. g(0), which follows from Assumptions and Property We therefore have that
(
The same argument can be used when substituting (0, De) for ((0,D)) Notice that the only difference between the method used to construct confidence intervals in the fairness test (that is, U+) and in Algorithm 2 (that is, U) is the multiplication of Z, by constant A. This still results in sequence random variables that converges (almost surely for Student's t-test) to zero.
Recall that we define č(0, (c) to be the output of Algorithm 2 Below, we show that given a fair solution / and data De, e(0*. Dz) converges almost surely to E(('). ). the expected loss 0*.
Property 6. If Asssmmptiins
and 8 hold, 8(0", Do) " e(0").
Proof. By Property 5 (which holds given Assumptions
and 5) we have that U+ as
g(0*). By Assumption 7
we have that g(0)) I -e. Now, let
A tw Ω: lim U+(0", Do(w)) g(07)}.
So, w is in A almost surely, i.e., Pr(w E A) = 1. Consider any w A. From the definition of limit and the previously established property that g(0*) S -6, we have that there exists an ng such that for all 2 no. Algorithm 2 will return Do) (this avoids the discontinuity of the if statement in Algorithm 2 for values smaller than no).
Recall that U- (B*, D.) " g(0)) means that pr U (0'' -
Furthermore, we have from Assumption that i(0', Da) - E(0*). Let
B = {w Ω: lim (e(w)) {(0))).
n-000
From Assumption 8 we have that is in B almost surely, i.e., Pr(w E B) 1, and thus by the countable additivity of probability measures, Pr(w E (An =
Consider now any E (AnB). We have that for sufficiently large n, Algorithm 2 will return 8(00, Dz) (since w E A), and further that Ê(0', De)) + e(0") (since w E B). Thus, for all w E (A B), the output of Algorithm| [ converges to {(0*), i.e., "(0', Da(w)) + E(0t). Since Pr(w E (An B)) we conclude that e(0", De(w)) as (00).
We have now established that the output of Algorithm 2 converges almost surely to E(0*) for the 0* assumed to exist in Assumption 7 We now establish a sumilar result for all E ehthat the output of Algorithm 2 converges almost surely to c(f) (recall that c(f) is defined as lmax + (()).
Property 7. If Assumptions
and 5 hold, then for all I E O, Dc) ax c(f).
Proof. By Property (which holds given Assumptions
and 5). we have that U (0, D.) ".,
g(0). If O, then we have that g(0) > -//2. We now change the definition of the set from its definition in the previous property to similar definition suited to this property. That is, let:
(w E Ω: lim U U+t00, (O,w)( = g(0))-
n-000
Recall that U+ (0. D.)
g(0) means that Pr(lim, 500 U+ D.) g(0)) 1. So, w is in
A almost surely, i.e., Pr(w A) = 1. and the previously established property that g(0) > -E/2, we have that there exists an such that for all 2 no Algorithm will return lmax + U (0, Do(w)). By Property 5 (which holds given Assumptions
Consider any w E А. From the definition of limit
2 and 5p. ( (O.DD.()) as g()). So, for all w E A. the output of
2 converges almost surely to &mxx + 9();; that is, 8(0, De(w)) ass Emox + (B), and since c(0) Lmax =()), therefore conclude that e(0 De(w)) "3, c(0).
Algorithm
20

---

Under review as a conference paper at ICLR 2023
By Property and one of the common definitions of almost convergence,
v 6 Vc 0,
lim inf(w E 52 |ē(0, D..(w)) c(0) < ct =1.
12-+00
Because ④ is not countable, it is not immediately clear that all 0 E Q converge simultaneously to their respective c(0). We show next that this is the case due to our smoothness assumptions.
Property 8. If Assumptions 7
5 andl@hold, then Ve' > 0.
Pr lim inf E Q VO E 10(0, n-000
(,,0 Delw)) c() < <t)) =
Proof. Let C()) denote the union of all the points in the 6-covers of the countable partitions of θ assumed to exist by Assumption 6 Since the partitions are countable and the d-covers for each region are assumed to be countable, we have that C(o) is countable for all 8. Then by Property (which holds given Assumptions simultaneously:
and 5) for all 8, we have convergence for all 0 C(0)
vg 0, VE O, lim inf Q: 4o C(o), 1600 (.(w)) c(0) et =1 no
(13)
Now, consider a 0 & C(o). By Definition 2 and Assumption 6 3 E 6 d(, S Moreover,
because and are Lipschitz continuous on O and O (by Assumption 6 respectively, we have that lc(0) - c(0') < Kō and |ē(0, De(w)) a(0', (w))) I K8. So. c(0 (w)w) c(0) S
Jē(0, De(w)) c(0') + Kō < |ē(0', (e(W) c(f') 5(K + R). This means that for all ō 0:
(V8 E C()), |8(0, (w))) c(0) < = (vo (00 D.(w)) - c(0) < < 8(K + KR)
Substituting this into (3 we get:
AA > 0, Yc Pr lim inf E Ωt 40 E θ, |6(0, Dw(w)) - c(0) < <(K5(K + R)1) 1.
n-+
Now, let 8 = e/(K + K) and e' 2e. Thus, we have the following:
Ve' > 0, Pr
lim inf E Ω v0 E O 16 Da(w)) - c(0) < <tt) = 1. -2000
So, given the appropriate assumptions, for all 0 E Q we have that 600 Do(w)) 25, cl0) and that a(0*, (w)) - E((*). Due to the countable additivity property of probability measures and Property g we have the following:
Pr ([vO E θ, lim a(0, D(O)) [(0)] lim c(0', ((('),(ww) =((00)) 1, (14) n-+00
where Pr(A, B) denotes the joint probability of A and B.
Let H denote the set of w E such that (14 is satisfied. Note that fmax defined as the value always
greater than E()) for all 0 E O and g 2 - for all 0 E Ô. So, for all w E H, for sufficiently large n, candidate selection will not define 0g to be in θ. Since w is Hf almost surely (Pr(w E H) = 1),
we therefore have that 1om Pr(O. & +) 1.
The remaining challenge is to establish that, given 0g g θ, the probability that the fairness test returns 9g rather than NSF converges to one as n -> cc. By Property 5 we have that U(e., Dy) u.s. g(O.). Furthermore, by the definition of é, when 0g & é we have that g(2)) < -E/2. So, U( Dạ) converges almost surely UO,,, Dy) < E/44 and U UOo. Dy) converges almost surely to a value less than - /2, it follows that the probability that U (0., Dy) < - converges to one. Hence, given that 0. & θ, the probability that 0g is returned rather than NSF converges to one.
value less than -/22. Since the fairness test returns O. rather than NSF if
We therefore have that 1) the probability that 0g & ê converges to one as n + do and 2) given that 8_ & O the probability that 0 is returned rather than NSF converges to one. Since 0g è implies that 0_ is fair, these two properties imply that the probability that a fair solution is returned converges one + co.
21

---

Under review as a conference paper at ICLR 2023
H A DISCUSSION ON THE INTUITION AND IMPLICATIONS OF OUR ASSUMPTIONS
The theoretical results in this paper, which ensure ELF's convergence and high-confidence fairness guarantees, are based on Assumptions 1-8. In this section, we provide an intuitive, high-level discussion on the meaning and implications of these assumptions. Our goal is to show that they are standard in the machine learning literature and reasonable in many real-life settings.
Assumption 1. This assumes the commonly-occurtie depends only on an input feature vector, X. It is formal characterization of the classic supervised learning setting; that is, that machine learning models should predict the target variable of interest, Y. based only on an input feature vector, X. In other words, we are dealing with a standard classification problem.
setting in which classifier's prediction
Assumption 2. While the delayed impact observation, 1, depends on the prediction, Y, it does not depend on how the prediction was made. For example, it makes no difference whether neural network or a support vector machine made a loan-repayment prediction.
Assumptions 3 and 4. These assumptions can be trivially satisfied when our algorithm uses standard modern stochastic classifiers that place non-zero probability on all outputs: for instance, when using Softmax layers in neural network. This assumption is common in the offline RL literature- for example, in methods that evaluate new policies given information from previously-deployed policies.
standard statistical tools, common in the machine learning literature, to compute confidence bounds: Hoeffding's inequality and Student's t-test. Hoeffding ' inequality can be applied under mild assumptions. In our running example, lending decisions made by a bank may have a delayed impact, e.g., on an applicant's 's future savings rate. Hoeffding's 's inequality holds if the bank knows the minimum and maximum savings rate possible (i.e., the DI is bounded in some interval [a, b)). Bounds produced by Student's t-test hold exactly if the sample mean is normally distributed, and in the limit (as the number of samples increases) the sample mean follows a different distribution. With few samples, bounds based on Student's t-test may hold approximately. Despite this, their use remains effective and commonplace in the sciences, including, e.g., in high-risk medical research (Thomas et al. 2019).
Assumption 5. Our algorithm
Assumption 6. The cost function used to evaluate classifiers is smooth: similar classifiers have similar costs/performances. Smoothness assumptions of this type are common the machine learning literature. Also, each classifier can be described by set of real-valued parameters (0 E IT,,, as is the case with all parametric supervised learning algorithms.
The space of classifiers not degenerate: at least one fair solution exists such that we perturb its parameters infinitesimally, it would not become arbitrarily unfair.
Assumption 7.
Assumption 8. The sample performance of a classifier converges to its true expected performance given enough data. This is similar to the usual assumption, e.g., in the regression setting, that model's 's sample Mean Squared Error (MSE) converges to its true MSE given sufficient examples.
I FULL ALGORITHM
Algorithm 2 presents the cost function used in candidate selection (line 3 of Algorithm D where strategy like the one used in the fairnsss test is used to calculate the cost, or utility, of potential solution 0. Again, unbiased estimates of g(0) are calculated, this time using dataset D. (lines 2-4). Instead of calculating a high-confidence upper bound on g()) using Usonft or Uttest we calculate an infiated upper bound U Specifically, we inflate the width of the confidence interval used to compute the upper bound (lines 5-10). This is to mitigate the fact that multiple comparisons are performed on the same dataset (D.) during the search for a candidate solution (see line 3 of Algorithm I]. which often leads candidate selection to overestimate its confidence that the solution it picks will pass the fairness test. Our choice inflate the confidence interval in this way, i.e., considering the size of the dataset Dj used in the fairness test and the use of scaling constant X, is empirically driven and was first proposed for other Seldonian algorithms (Thomas al. 2019
22

---

Under review as a conference paper at ICLR 2023
Algorithm 2 cost
Input: 1) the vector that parameterizes model m; 2) D. {(x,, Vi, T; P. 1)))== confidence
level o; 4) tolerance value r; 5) the behavior model [3; 6) Bound E {Hoeff, ttest]; and 7) the number of data points in Dy, denoted DDy- Output: The cost of π.
1: 9 + ()
2: for E {I,..., m) do
3: if o(X, Y, Ti) is True then g.append (T P.9) B(X.),))
I,) end if
4: end for
5: L = 2; n = length(i)
6: if Bound is Hoeff then
7: a +- upper and lower bounds of
1 8: U+ = ng
(C 0.) + A(b )(b-a)// log(1/6) (2nD,)
9: else if Bound is ttest then U+
(2 0c) + > ald)
VaD, 1 8,nD
ng
10: end if
lmax ge i(0', De)
12: if - return E(0, Do) else return (Lmax + U+)
Algorithm 3 ELF with Multiple Constraints
Input: 1) dataset D {(X,, Y,, Tú Y r')) 2) the number of delayed- impact constraints wish satisfy, k; 3) sequence of Boolean conditionals (c,) such that for {l,..., k). ej (X,, Y, T,) indicates whether the event associated with the data point Y., Tr, Y, I,²) occurs; 4) confidence levels 8 = (6,) where each ō, E (0, 1) corresponds to delayed-imp constraint (T,))=1, where each Ty is the tolerance associated with delayed- impact
gy: 5) tolerance values constraint gj: 6) the behavior model B; and 7) an argument Bound {Hoeff, ttest) indicating which method for calculating upper bounds to use. Output: Solution 0g2 or NSF.
De. D + partition(D)
2: 0g < arg minaee cost (0, De, k. 5, T. Bound, length(D,))
3: U ()
4: for [1,....k, k} do
5: Oj + ()
6: for E {1, [I...., do
7: if cx(X,, Ti) is True then append Th, (X.,
1f) end if
3(X.
8: end for
9: if Bound Hoeff then ('append(unceee(@j) else Uappend(UUttesr()))) end
10: end for
11: fjj E {1...., (L....,k).U. Uy S then return 0g else return NSF
U < -E/4, a small negative constant, the cost associated with the loss of is returned. Otherwise, the cost of 0 is defined as the sum of U and the maximum loss that can be obtained on dataset De (lines 11-1).. This discourages candidate selection from returning models unlikely to pass the fairness test. We consider -E/4. instead of 0 the fairness threshold in ELF to ensure consistency. This is discussed in more detail in Appendix G
Algorithm 3 shows ELF with multiple constraints. The changes relative Algorithm I are relatively small: instead of considering only a single constraint, the fairness test loops over all & constraints and only returns the candidate solution if all & nigh-confidence upper bounds are at most zero. Similarly, the cost function, Algorithm 4 changes relative to Algorithm in that when predicting the outcome of the fairness test it includes this same loop over all delayed-impact constraints.
23

---

Under review as a conference paper at ICLR 2023
Algorithm 4 cost with Multiple Constraints
Input: 1) the vector 0 that parameterizes classification model æ; 2) candidate dataset De ((X,, Y, Tú P; )= 3) the number of delayed-impaet constraints we wish to satisfy, k; 4) a sequence of Boolean conditionals (cz))=1 such that for j (1,..,,k,, ki), cy(X, Yú, T;) indicates
whether the event associated with the data point (X,, Y,, Tú, V,P I!.) occurs; 5) confidence levels
5 { ) where each 63 E (0, corresponds with constraint 9j: tolerance values (T, ) - where each Tj is the tolerance associated with delayed-impact constraint gj: 7) the behavior model 3; 8) argument Bound {Hoeff, ttstt) indicating which method for calculating upper bounds to use; and 9) the number of data points in dataset Dj. denoted T.D Output: The cost associated with classification model mTa
for j E (1...., k) do
2: 9j + ()
3: for E [I,...,m) do
4:
cx(X, Yú, Ti) True then 9.. ap.end (Ty
To(X, Pi") ((X.)P))
1
end
5:
end for
6:
Let x= 2; n4 = Length((f)
7:
if Bound Hoeff ff then
8:
Let a. be the lower and upper bounds of g,
9:
UJ = ma
(
" (_)()))) + A(b-a()))) \(b-a)
log(1/6,) (2nD,)
10: else if Bound is ttest then
11: UJ* 1
- 2
(0,).) + X c
t -1 mD
ma
VMD,
12: end if
13: end for
14: lmax me 8(0', Dz)
15: if E k). s E/4 then return Ê(0, D.) else return (emax + E3 Uniillatdd
J OTHER EXPERIMENTS
In our experiments, we consider classifier that predicts whether youth in foster care will have job after leaving the program. (4) indicates that if they are predicted to get a job, they are more likely to receive financial aid, which may lead to positive (higher) delayed impact observation-1? increases when P.D
Whether DI strongly affected by classifier's predictions is regulated by a. DI is also affected by Gaussian noise representing stochasticity in the environment. Different means and variances indicate that the DI on youth of different races may (due social biases) differ. Changing the noise distribution would affect how youth of different races are affected by predictions, thus modeling different type of society.
In all experiments, our implementation of ELF used CMA-ES (Hansen & Ostermeier 2001) to search over the space of candidate solutions and the ttest concentration inequality. We partitioned the dataset D into D. and Dy using stratified sampling approach where D, contains 60% of the data and Dy contains 40% of the data.
In this section, we present the complete set of results for RQ1 and RQ2: does ELF enforce DI constraints, with high probability, when existing fairness-aware algorithms often fail; and what the cost of enforcing DI constraints. In particular, we show the performance of the five algorithms being compared, in terms of failure rate, probability returning solution, and accuracy, for different values of a and as a function of Notice that Figures 4and 5 observations made in Section the qualitative behavior of considered algorithms remains the same for all values of
present results consistent with the
24

---

Under review as a conference paper at ICLR 2023
0.0
1305
105
205
30"
301
37
32
30"
221
13
32"
12
3375
110%
110.0
40%
100
28%
20%
22"
15/
15
Teining
Arout Thann Delaini
< 0.2
80%
80%
20%
40%
40%
45%
Afcuut laainn 31
Aevouu Taiking E0ta
AT Trminn tota
0.3
100
20%
28%
205
20%
117
207
160
22
28
11
207
122
327
16
1100
1160
50%
66%
20%
25%
204
152
AYcur
Aev Taiking DAED
ARToATT 12.00 310
Avear Tranng Lata
Figure 4: Algorithms' performances in terms of failure rate (leftmost two columns), probability of returning a solution (second from the right column), and accuracy (right column), as a function of n and for different values of The black horizontal lines indicate the maximum admissible probability
of unfairness, &n 81 10%. All plots use the following legend: ELF with DP QSA with EqOdds
- LR
QSA
QSA with EqOpp Fairleam with EqOdds
QSA with PE ........... QSA with
Dislmp - Fairleam with DP
Fairness Constraints.
25

---

Under review as a conference paper at ICLR 2023
3.755
100%
2374
115.5
40%
10:
28%
20%
20
12/
15
Thamn Delatei
d 0.5
80%
20%
60%
40%
46%
ATcurt Saliing Daca
Aevoaa Taiiing tota
A Traiing tora
0.7
100
205
357
207
22
22
15"
227
12"
22"
12
110%
1100
65%
20%
104
150
15
Arcur:
Aevouct Trkking tuta
Arouet Takknng
AYaar Trning totari
d 0.9
60%
50.5
40%
45%
Atcuat Tal D0
DNCS
ATo Taming toda
1.0
120
20%
28%
20%
20%
117
107
12
11/
207
157
327
10
307
Figure 5: Algorithms' performance in terms of failure rate (leftmost two columns), probability of returning a solution (second from the right column), and accuracy (right column), as a function and for different values of The black horizontal lines indicate the maximum admissible probability
of unfairness, ōn = 8, 10%. All plots use the following legend:
ELF
LR
QSA
with DP -.... QSA with EqOdds -..... QSA with EqOpp Dislmp Fairleam with DP
QSA with PE ....... QSA with
Fairleam with EqOdds
Fairness Constraints.
26

---

Under review as a conference paper at ICLR 2023
K RELATED WORK
Most prior work on the social implications of ML study static fairness without considering the
long-term impact of model decisions (Calders et al. 2009) Zatar et al., 2017 Hardt et al. 2016 Dwork et al., 2012). However, there exists a growing body of work that examines the long- -erm impact of fairness in ML D'mmour et al. 2020 Hu & Chen 2018a bj Liu et al. 2018 8 Heidari et al. 2019 Zhang al. 2020a| Mouzannar al. 2019). In this paper, we build upon this prior work and present the first method that uses historical data to train a classifier with high-confidence delayed-impar fairness guarantees when the analytic model of the relationship between classifiers'
predictions and delayed impact is not known a priori.
Wen al. (2019) and Tang al. (2020) present work similar to ours. Wen et al. (2019) propose modeling delayed impact using a Markov decision process (MDP) with two different reward functions: one for the seecision-maee,, e.g., a bank, and another for each individual, e.g., loan applicant. WWnn et al.) (2019) introduce algorithms that are able to estimate near-optimal policies (in terms of cumulative reward of the decision-maker) while enforcing static fairness constraints (e.g., demographic parity and equal opportunity). Importantly, /Wen et al. (2019) introduce a method that ensures that static fairness constraints hold for all time during a sequence of decisions. We, by contrast, study the orthogonal problem of ensuring fairness with respect to user-defined delayed-impaci measures. The method proposed by [Tang et al. (2020), unlike ELF, considers the online multi-armed bandit learning setting in which there are features- the algorithm does not differentiate individuals within group while making decisions. We, by contrast, tackle the problem of high-confidence fairness in the classification setting.
Work by Ge et al. 2221)) and Hu & Zhang 2022) study similar but orthogonal problem settings. Ge et al. (2021) and Hu & Zhang (2022) train classifiers that satisfy static fairness constraints in non-stationary settings (e.g., a recommendation system where a person's 's interests may change over time). Importantly, both [ie et al. (021) and & Zhang (2022) require prior knowledge of analytic, accurate models of the environment- for example, in the form of probabilistic graphical models. Our method, by contrast, does not require a model or simulator of the environment, nor prior knowledge about the relationship between a classifier's 's predictions and the resulting delayed impact.
Zhang et al. (2020b) investigate the long-term effects of repeatedly deploying myopic policies that optimize static fairness constraints. They rely on knowledge of analytical models of "user qualification" - modelss characterizing whether an individual will be qualified (e.g.. likely to repay loan) at given time. ELF, by contrast, ensures long-term fairness with high confidence without requiring access to any models. Chi et al. (2022) introduce new fairness definition in multi-step problems where different demographic groups are represented as different Markov decision processes. The goal of the proposed method is to identify policies that satisfy an alternative type of constraint; in particular, their method's objective is to identify policies that result in return parity between groups This technique assumes an agent that can repeatedly interact with its environment until orthogonal setting: ELF addresses the
fair policies are identified. We, by contrast, investigate classification setting where a fixed dataset of historical observations is available (based on which fair solution should be identified with high confidence), but in which the agent/algorithm cannot further interact with its environment to collect more data. Furthermore, ELF was not designed to tackle any one particular type of constraint; it is compatible with wide range of (user-specified) constraints. D' Amour et al. (2020)'s 's goal is not to propose a new method; instead, they evaluate the DI resulting from a given classiner's 's predictions, under the assumption that an accurate simulator of the environment is available. By contrast, we propose new method for training classifiers that ensure that DI fairness constraints are satisfied, without requiring accurate simulators.
In another line of work, researchers have shown that the fairness of MI. algorithms can be improved by manipulating the training data, rather than the learning algorithm. This goal can be achieved, for example, by removing data that violates fairness properties (Verma et al. (02I) or by inserting data inferred using fairness properties (Salimi et al. 2019). Again, while these methods can improve the fairness of learned models, they were designed enforce static faimess constraints and do not enforce fairness with respect to the delayed impact resulting from deploying such learned models.
Lastly, this paper introduces method that extends the existing body of work Seldonian algo- rithms (Thomas et al. 2019). Seldonian algorithms provide fairness guarantees with high probability and have been shown perform well in real-world applications given reasonable amounts of training
27

---

Under review as a conference paper at ICLR 2023
data (Thomas al. 2019 Metevier et al., 2019). They also also-by by construction- provide straight- forward way for users to define multiple notions of faimeess that can be simultancously enforced
(Thomas et al. 2019). The technique introduced in this paper (ELF) is the first supervised-learinng Seldonian algorithm capable of providing high-probability fairness guarantees terms of delayed impact.
28


Reviews:
[{"review_id": "xDYy4jSUaq", "reviewer": "Reviewer_ABty", "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": "", "summary_of_the_paper": "The paper studies the delayed impact of fairness in machine learning and provides a new model that models this effect as opposed to the commonly studied static notions of fairness. The paper introduces an algorithm called ELF (Enforcing Long-term Fairness) to provide high confidence delayed impact fairness guarantees (when possible). The authors demonstrate the effectiveness of ELF empirically.\n", "summary_of_the_review": "While I think the paper tackles an interesting problem, it is hard to justify the proposed modeling and practicality of the results. ", "strength_and_weaknesses": "------------------------------\nStrengths\n------------------------------\n-- The delayed impact of fairness in machine learning has not received much attention in the community (mainly due to the hardness of modeling this impact) so in that sense, it is great to see papers on this topic.\n\n--The paper is pretty well written and it is clear to follow the high-level ideas of the paper.\n\n------------------------------\nWeaknesses\n------------------------------\n--Assumption 3 is strong. While it is common in the RL community to have this assumption, this is less realistic in the algorithmic fairness literature and a possible source of bias. How can this assumption be justified?\n\n-- The theoretical analysis of the paper is rather straightforward. \n\n-- The experimental analysis is not convincing. \n(a) None of the baselines considers the delayed impact into consideration. Is it surprising to see that ELF will have a much lower failure rate compared to the baselines? \n(b) How did you come up with the form of delayed impact in Equation (4)? In general, having access to such data is a major challenge in the practicality of this work.\n(c) The number of data points needed for ELF so that it outputs a solution is very large. Does this problem become less severe when looking at lower-confidence solutions? What is the dependency on the confidence parameter? \n(d) The accuracy of the ELF is significantly lower than the baselines. \n\n", "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": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "hXqZdaArUfZ", "reviewer": "Reviewer_51vQ", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper investigates the fair classification problem in the long term. It introduces a new algorithm, ELF, to solve the fair classification problem as both a classification and a reinforcement learning problem — classification for optimizing the main objective (a measure of classification loss) and reinforcement learning when taking DI into account. ", "summary_of_the_review": "This paper presents a solution to classification with long-term fairness constraints. A new setting is considered where the relationship between the delayed impact and prediction is unknown. To handle this challenge, the paper introduces a few assumptions and infers the delayed impact from prediction using a reinforcement learning method. Then the inferred DI is used for classification.\n\nThe method seems meaningful but the formulation is not clear. The statements about DI and fairness are confusing. It is not clear why Eq 2<0 is necessary for model fairness. \n\nAssumption 2 is contrary to the setting of the analytic relationship between DI and prediction.", "strength_and_weaknesses": "+ The setting is interesting where the relationships between the delayed impact and prediction are unknown. A reinforcement learning solution is developed to infer the delayed impact from the observation using importance sampling.\n+ Given the inferred delayed impact, a classification is built to ensure DI.\n+ The theoretical analysis seems convincing.\n\n- The variable of delayed impact observation and the formulation of long-term fairness is unclear. Eq 1 defines g(theta) for DI but it is not clear why a fair algorithm must ensure Eq 1. Usually, fairness means the absence of disparity between two groups. But variable I is an observation, e.g., the rate. It is unclear why the larger I corresponds to better DI. In brief, DI and DI fairness is not well defined. The confusion makes Sec 2 hard to understand.\n- The setting of no analytic relationship between DI and prediction is controversial. Assumption 2 assumes the relationship. Otherwise, the off-policy learning cannot infer the delayed impact. In addition, it is unclear how the performance of importance sampling affects the downstream classification.", "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": "SwHJthwgft6", "reviewer": "Reviewer_Sy63", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper looks at how to guarantee fairness when the impact of the decisions we make today is only seen in the long term. The paper provides a counter-factual approach to predict future impact from historical data that may be coming from a different policy than the one we aim to deploy, and aims to find a policy that does not have an unfair long-term impact across populations. ", "summary_of_the_review": "I think the topic of the paper is interesting. However, I think I feel that much of what makes delayed-impact fairness hard in practice is in the details and specific assumptions made about the problem (non i.i.d. data and data from a single population that cannot be interpolated to a different population), and I think the assumptions of the current work are a bit naive. As such, I think the paper is a bit under the bar in its current form", "strength_and_weaknesses": "Strengths:\n- the topic of the paper is important. I.e., how do we guarantee fairness across different individuals or groups, especially when we cannot observe labels about the individuals we make decisions on and update our model immediately?\n- the approach is technically interesting: it is counterfactual in flavor and relies on learning from historical data. This data comes from previously deployed policies that may have been unfair, and the observed outcomes are informed by the previously deployed policy itself. \n- the idea of moving away from having to model a specific analytical relationship between a classifier's prediction and its observed impact is nice\n\nWeaknesses:\n\nI have the following concerns about the paper:\n\ni) Exposition and scope-wise, I am not sure whether there is anything in the paper that is specific to delayed impact and but not to counterfactual learning. Here, unless I missed something about the paper, it seems that the only way the delayed impact really comes in is that compared to a standard ML/fairness model, the observed label is defined as being, say, 2 years after the decision has been made. But the time dimension here does not actually play a role in the model:\n- the dataset itself is static, coming from a single previously deployed policy. \n- The problem is, in fact, formulated as a static problem of counterfactual learning given historical i.i.d. data. There isn't a real time dimension/aspect in which the model is updated over time and more data is collected over time. \n\nIn turn, it seems to be more of a traditional counterfactual learning problem where the delayed impact part feels \"gimmicky\" and does not impact the paper beyond its motivation. \n\nii) Assumption 1 seems to essentially say that we look at models whose predictions do not depend on group identity. This is a \"sensitive attribute-blind\" approach which contradicts much of what is known in the space of fairness. I.e., the same features may mean different things for different populations, and not taking the sensitive attribute into account is a surefire way to promote unfairness. This seems like a bit of a naive assumption which says that we can take the lessons from one population and apply it to another directly.\n\niii) I think the assumptions that the historical data is well-behaved (i.i.d and having observations of the full support) may be a bit hard to believe. What I think may be hard and interesting about time-dynamics in the space of fairness is that the deployed rule influences the observed data, and the observed data influences the deployed rule, often leading to feedback loop with a long-term negative impact. \n\nAs an example: if we only historically gave loans to wealthy white people, a naive model will learn to still only give loans to wealthy white people, and we will only collect repayment data from wealthy white people. In this case, we do not have access to i.i.d., full support data that is representative of the entire population, and have a missing data problem. It is then impossible (without collecting more data) to predict the outcomes on a different population that we have observed (almost) nothing about in the past. \n\n\n", "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": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject