Equal Improvability: A New Fairness Notion Considering the Long-term Impact
Authors: Ozgur Guldogan
Yuchen Zeng
Jy-yong Sohn
Ramtin Pedarsani
Kangwook Lee
Venue: ICLR 2023 poster (2023)
Keywords: Fairness and Bias in Artificial Intelligence
Machine Learning

Abstract: Devising a fair classifier that does not discriminate against different groups is an important problem in machine learning. Although researchers have proposed various ways of defining group fairness, most of them only focused on the immediate fairness, ignoring the long-term impact of a fair classifier under the dynamic scenario where each individual can improve its feature over time. Such dynamic scenarios happen in real world, e.g., college admission and credit loaning, where each rejected sample makes effort to change its features to get accepted afterwards. In this dynamic setting, the long-term fairness should equalize the samples’ feature distribution across different groups after the rejected samples make some effort to improve. In order to promote long-term fairness, we propose a new fairness notion called Equal Improvability (EI), which equalizes the potential acceptance rate of the rejected samples across different groups assuming a bounded level of effort will be spent by each rejected sample. We analyze the properties of EI and its connections with existing fairness notions. To find a classifier that satisfies the EI requirement, we propose and study three different approaches that solve EI regularized optimization problems. Through experiments on both synthetic and real datasets, we demonstrate that the proposed EI-regularized algorithms encourage us to find a fair classifier in terms of EI. Finally, we provide experimental results on dynamic scenarios which highlight the advantages of our EI metric in achieving the long-term fairness. Codes are available in anonymous GitHub repository.

Published as a conference paper at ICLR 2023
EQUAL IMPROVABILITY: A NEW FAIRNESS NOTION CONSIDERING THE LONG-TERM IMPACT
Ozgur Guldogan"! Yuchen Zeng":
Jy-yong Sohn' 1 Ramtin Pedarsani! Kangwook Lee
University of California, Santa Barhara
Yonsei University 9 University of Wisconsin-Madison
ABSTRACT
Devising fair classifier that does not discriminate against different groups is an important problem in machine learning, Recently, effort-based fairness notions are getting attention, which considers the scenarios of each individual making effort to improve its feature over time. Such scenarios happen in the real world, e.g., college admission and credit loaning, where each rejected sample makes effort to change its features to get accepted afterward. In this paper, we propose a new effort- based fairness notion called Equal Improvability (EI), which equalizes the potential acceptance rate of the rejected samples across different groups assuming bounded level of effort will be spent by each rejected sample. We also propose and study three different approaches for finding classifier that satisfies the EI requirement. Through experiments on both synthetic and real datasets, we demonstrate that the proposed El-regularized algorithms encourage
find a fair classifier in terms of EI. Additionally, we ran experiments on dynamic scenarios which highlight the advantages of our EI metric in equalizing the distribution of features across different groups, after the rejected samples make some effort to improve. Finally, we provide mathematical analyses of several aspects of El: the relationship between El and existing fairness notions, and the effect of EI in dynamic scenarios. Codes are available a GitHub repository
INTRODUCTION
Over the past decade, machine learning has been used in wide variety of applications. However, these machine learning approaches are observed to be unfair to individuals having different ethnicity, race, and gender. As the implicit bias in artificial intelligence tools raised concerns over potential discrimination and equity issues, various researchers suggested defining fairness notions and develop- ing classifiers that achieve faimess. One popular fairness notion is demographic parity (DP), which requires the decision-making system to provide output such that the groups are equally likely to be assigned to the desired prediction classes, e.g., acceptance in the admission procedure. DP and related fairness notions are largely employed to mitigate the bias in many realistic problems such as recruitment. credit lending, and university admissions (Zafar et al. 2017b] Hardt et al., Dwork
Dwork
et al. 2012 Zafar et al. 2017a).
However, most of the existing fairness notions only focus on immediate fairness, without taking potential follow-up inequity risk into consideration. In Fig. [ we provide an example scenario when using DP fairness has long-term fairness issue, in simple loan approval problem setting. Consider two groups (group 0 and group 1) with different distributions, where each individual has one label (approve the loan or not) and two features (credit score, income) that can be improved over time. Suppose each group consists of two clusters (with three samples each), and the distance between the clusters is different for two groups. Fig. [ visualizes the distributions two groups and the decision boundary of classifier / which achieves DP among the groups We observe that the rejected samples beft-hand-side of the decision boundary) in group are located further away from the decision boundary than the rejected samples in group O. As a result, the rejected applicants group need to make more effort to cross the decision boundary and get approval. This improvability gap between the two groups can make the rejected applicants in group less motivated improve their features, which may increase the gap between different groups in the future.
" 'Equal Contribution. Emails: ozgurqqulooann@ucssst edu yzeng wwwwsc sc.udu
1 Work done at the University of Wisconsin-Madisen htaps///ghhhb.cmmmlllgaaanazuuu faimess

---

Published as a conference paper at ICLR 2023
(x (xx) 2 0.5)
This motivated the advent of fairness notions that consider dynamic scenarios when each rejected sample makes effort to improve its
Ax
Group O Group
feature, and measure the group fairness after
Hard to Cross the Boundary
such effort is made Gupta et al. (2019): HHei- dari et al. (2019): Von Kügelgen et al. (2022).
Decision Boundary of Classiifier
However, as shown in Table [ they have vari-
Figure I: Toy example showing the insufficiency of fairmess notion that does not consider improv- ability. We consider the binary classification (ac- cept/reject) on 12 samples (dots), where is the fea- ture of the sample and the color of the dot represents the group. The given classifier f is fair in terms of a popular notion called demographic parity (DP), but does not have equal improvability of rejected samples (f(x) < 0.5) in two groups; the rejected samples in group needs more effort Åx to be accepted, i.e., f(x + Ax) > 0.5, compared with the rejected sam- ples in group 0.
ous limitations e.g., vulnerable to imbalanced group negative rates or outliers.
In this paper. we introduce another fair- ness notion designed for dynamic scenarios, dubbed Equal Improvability (EI), which does not suffer from these limitations. Let be the feature of sample and f be score- based classifier, e.g. predicting a sample as accepted if f(x)= 2 0.5 holds and as rejected otherwise. We assume each rejected individ- ual wants to get accepted in the future, thus improving its feature within a certain effort budget towards the direction that maximizes its score fxx). Under this setting, we define EI fairness as the equity of the potential acceptance rate of the different rejected groups, once each individual makes the best effort within the predefined budget. This prevents the risk of exacerbating the gap between different groups in the long run.
Our key contributions are as follows:
We propose a new group fairness notion called Equal Improvability (EI), which aims to equalize the probability of rejected samples being qualified after a certain amount of feature improvement, for different groups. El encourages rejected individuals in different groups to have an equal amount of motivation to improve their feature to get accepted in the future. We analyze the properties El and the connections of EI with other existing fairness notions.
We provide three methods to find classifier that is fair in terms of EI, each of which uses a unique way of measuring the inequity in the improvability. Each method is solving a min-max problem where the inner maximization problem finding the best effort to measure the El unfairness, and the outer minimization problem is finding the classifier that has the smallest feimaess-regularized loss. Experiments on synthetic/real datasets demonstrate that our algorithms find classifiers having low EI unfairness.
We run experiments on dynamic scenarios where the data and the classifier evolve over multiple rounds, and show that training a classifier with El constraints is beneficial for making the feature distributions of different groups identical in the long run.
2 EQUAL IMPROVABILITY
Before defining our new fairness notion called Equal Improvability (EI), we first introduce necessary notations. For an integer n, lct [n] = {o...... n - 1}. We consider a binary classification setting where each data sample has input feature vector E X' C Rd and label particular, we have a sensitive attribute z E 2 = [Z]. where Z is the number of sensitive groups As suggested by Chen et al. (2021), we sort d features features X₁ E _d4, manipulable features XM E Rdx,, and immutable features XIM E RRdus, where di + dvr drv- dl holds. Here, improvable features Xı refer the features that be improved and can directly affect the outcome, e.g., salary in the credit lending problem, and GPA in the school's admission problem. In contrast, manipulable features XM can be altered, but are not directly related to the outcome, e.g., marital status in the admission problem, and communication type in the credit lending problem. Although individuals may manipulate these manipulable features to get the desired outcome, we do not consider it as way to make efforts as it does not affect the individual's 's true qualification status. Immutable features XIM are features that cannot be altered, such as race, age, or date of birth. Note that if sensitive attribute Z is included in the feature vector, then it belongs to immutable features. For ease of notation, we write x = (x) XM. XiM). ). Let F= {f [f:
y {0, 1}. In
Idd into three categories: improvable
X + 00 1] be the set of classifiers, where each classifier is parameterized by w. i.e., f= fw- Given f E F. we consider the following deterministic prediction: ý x = 1xf(() 2 0.5) where 1(A} = 1 if condition A holds, and 1 ()) 0 otherwise. We now introduce new fairness notion.
2

---

Published as a conference paper at ICLR 2023
Se
Group
Group
[x (.000 0.5, max fix + áx) 0.5) ACAN/1)
[x-Ji((0) < 0.5. max f(x Ax) < 0.5)
Classifier fa schieving FI
(1) Original definition
(b) Aherrative definition
Figure 2: Visualization of ET fairness. For binary classification on 12 samples (dots) in two groups (red/blue), we visualize the fairness notion defined in this paper: (a) shows the original definition in Def. 2.1 and (b) shows an equivalent definition in Prop. [.2 Here we assume two-dimensional features (both are improvable) and Lo norm for p(x) |o The classifier fEI achieves equal improvability (EI) since the same portion (1 out of 3) of unqualified samples in each group can be improved to qualified samples.
Definition 2.1 (Equal Improvability), Define a norm μ RR + [0, 2o). For given constant 5 > 0, a classifier f is said to achieve equal improvability with d-effort if
P
max f(x + Ax) 2 0.5| <0), (xx))=05,,2))))- ((Ax))5
=P max f(x + Ax) 0.5 f(x) < 0.5 {((
holds for all = E 2, where Ax; is the effort for improvable features and Ax = (Ax,, 0)
Note that the condition f(x) < 0.5 represents that an individual is unqualified, and f(x + Ax) 2 0.5 implies that the effort Ax allows the individual to become qualified. The above definition of fairness in equal improvability requires that unqualified individuals from different groups 2 E [Z] are equally case-by-case cost matrix that is
likely to become qualified if appropriate effort is made. Note that j can be defined
basis. For example, we can use ||x||| = /x, Cx2, where C E Rdxx diagonal and positive definite. Here, the diagonal terms of C' characterize how difficult to improve each feature. For instance, consider the graduate school admission problem where X₁ contains features "number of publications" and "GPA". Since publishing more papers is harder than raising the GPA, the corresponding diagonal term for the number of publications feature in C should be greater than that for the GPA feature. The constant d in Definition 2. can be selected depending task and the features. Appendix B. contains the interpretation of each term in Def. 2.1 We introduce an equivalent definition of EI fairness below.
the classification
Proposition 2.2. The El fairness notion defined in Def. 2. has an farm classifier f achieves equal improvability with 5-effort if and only if
IP(x xelmp x E X_,22,222 P(x E x!!P x (xEX_
holds for all E Z where X- = fx: f(x) < 0.5} is the set features for unqualified samples, and ximp (x f(x) < 0.5, maxp( f(x + Ax) 2 0.5) is the set of features for unqualified samples that can be improved to qualified samples by adding Ax satisfying μó u(Ax:) S 8.
The proof of this proposition is trivial from the definition of X- and xiimp Note that Pxx X x E X-) in the above equation indicates the probability that unqualified samples can be improved to qualified samples by changing the features within budget 8. This how we define the "improvability" of unqualified samples, and the El fairness notion is equalizing this improvability for all groups.
Visualization of EI. Fig. [ shows the geometric interpretation of EI faimess notion in Def. 221 [ and Prop. 2.2 for simple two-dimensional dataset having 12 samples in two groups 2 E {red, blue}. Consider linear classifier fEI shown the figure, where the samples the right-hand-side of the decision boundary is classified as qualified samples (fEI(x) 2 0.5). In Fig. 2 we have L.o ball at each unqualified sample, representing that these samples have chance to improve their feature in a way that the improved feature x + Ax allows the sample to be classified as qualified, i.e., fri(x
Ax) > 0.5. One can confirm that P (max;(ax))<& 58 f(x + Ax) > 0.5| f(x) < 0.5, z 2) = holds for each group 2 E (red, blue), thus satisfying equal improvability according to Def. 2.1 In Fig. P2b, we check this in an alternative way by using the El fairness definition in Prop. 2.2 Here, instead of making a set of improved features at each sample, we partition the feature domain X' into three parts: (i) the features for qualified samples X4 (x fEI(X) Z 0.5). (ii) the features for unqualified samples that can be improved ximp {x (x) < 0.5, max f(x
Ax) 2 0.5). and (iii) the features for unqualified samples that cannot be improved {x: fei(x) < 0.5, max,((x)) f(x + Ax) < 0.5}. In the figure, (ii) is represented as the green region and (iii)
shown as the yellow region. From Prop. 2.2 EI fairness means that samples (ii) samples in (iil) is identical at each group E (red, blue), which is true for the example in Fig. 2b.
# samples in (ii)
3

---

Published as a conference paper at ICLR 2023
Table 1: Comparison of our EI fairness with existing fairness notions.
Name of fiirnes
Definition
Cuussler effees?
Limitation
Equal Improvability (Ours)
Mar Ax)205
Melee ((x 2x)2 cas)
Yes
Denographic Paris
Pifle) 2055 - 2.55
No.
Equil Operciunic Haok ot 2016
Pilt 200020000 L-mLa-sj 21/1 2.
No No
Equalized cods
pirrr ar p0
PUD0 200022000 syspaeaa (a (U00) 2.0 1obly=
Bounded Frout
Besaan at 2019
(uoe ftx+ Ax) 2 (00 < [===)
max [xx Ax) 0.5. < 05)
Yo
Cannot imbalanced
hurale gropp
Tegaina ratre
(Ap-
pendis
Earel Receure Cuppa et 2019
Jarraiggu ((Ax) (00) < <. ]]
R wit alAx) <0))
Yos
Volterable to cut-
lien LApoendia am1
B3
Indioaltntel and Crasel Remnune Von Kigelgen etal. 2022
min
olx
xi2, M3)
min alxt xxix ui) for latest vuriatte u, groupa
Yes
Limitation: coun-
terfacoual faimes
Comparison of El with other fairness notions. The suggested fairness notion equal improvability (EI) is in stark difference with existing popular fairness notions that do not consider dynamics, i.e. demographic parity (DP), equal opportunity (EO) (Hardt et al., 2016). and cqualized odds (EOD) (Hardt et al.] 2016), which can be "myopic" and focuses only on achieving classification fairness in the current status. Our notion instead, aims at achieving classification fairness in the long run when each sample improves its feature over time.
On the other hand, EI also has differences with existing fairness notions that capture the dynamics of samples (Heidari et al. 2019 Huang al. 2019. Gupta al. 2019 Von Külgelgen et al. 2022). comparess our fairness notion with the related existing notions. In particular, Bounded Effort
(BE) fairness proposed by Heidari et al. (2019) equalizes "the available reward after each individual making a bounded effort" for different groups, which is very similar to EI when we set proper reward function (see Appendix B.2). To be more specific, the BE fairness can be represented as in Table [ Comparing this BE expression with EI in Definition 2. one can confirm the difference: the inequality f(x) < 0.5 is located at the conditional part for EI, which is not true for BE. EI and BE are identical if the negative prediction rates are equal across the groups but in general. they are different. The condition [() < 0.5 here is very important since only looking into the unqualified members makes more sense when we consider improvability. More importantly, the BE definition is based on reward functions and we are presenting BE in a form that is closest to our EI fairness expression. Besides, Equal Recourse (ER) fairness proposed by Gupta et al. (2019) suggests equalizing the average effort of different groups without limiting the amount of effort that each sample can make. Note that ER is vulnerable to outliers. For example, when we have an unqualified outlier sample that is located far way from the decision boundary, ER disparity will be dominated by this outlier and fail to reflect the overall unfairness. |Von Kügelgen et al. (2022) suggested Individual-Level Fair Causal Recourse (ILFCR), a fairness notion that considers a more general setting that allows causal influence between the features. This notion aims to equalize the cost of recourse required for a rejected individual to obtain an improved outcome if the individual is from a different group. Individual-level equal recourse shares a similar spirit with El since both of them are taking care of equalizing the potential to improve the decision outcome for the rejected samples. However, introducing individual-level fairness with respect to different groups inherently requires counterfactual fairness, which has its own limitation, as described in Wu et al. 2019), and it is also vulnerable to outliers. [Huang et al. (2019) proposed a causal- based fairness notion to equalize the minimum level of effort such that the expected prediction score of the groups is equal to each other. Note that, their definition is specific to causal settings and it considers the whole sensitive groups instead of the rejected samples of the sensitive groups. In addition fairness notions, we also discuss other related works such as fairness-aware algorithms in Sec. 5)
Compatibility of EI with other fairness notions. Here we prove the compatibility of three fairness notions (EI, DP, and BE), under two mild assumptions. Assumption (..ioonnn..e.eseeee enssurs that El is well-defined, while Assumption 2.4jimplies that the norm μ and the effort budget ó are chosen such that we have nonzero probability that unqualified individuals can become qualified after making efforts.
Assumption 2.3. For any classifier S. the probability of unqualified samples for each demographic group is not equal to O, i.e., P ([[(x)= < 0.5, z = z) _ 0 for all 2 E Z.
Assumption 2.4. For any classifier f, the probability of being qualified after the effort for unqualified samples is not equal O, i.e., IP (max f(x + Ax) 2 0.5, f(x) 0.5) * O.
Under these assumptions, the following theorem reveals the relationship between DP, El and BE. Theorem 2.5. If classifier f achieves two of the following three fairness notions, DP, El, and BE; then it has to achieve the remaining fairness notion as well.
The proof of the Theorem 2.5 is provided in Appendix A.I This theorem immediately implics the following corollary, which provides a condition such that El and BE conflict with each other.
4

---

Published as a conference paper at ICLR 2023
Corollary 2.6. The above theorem says that if classifter f achieves EI and BE, it has to achieve DP. Thus, by contraposition, if f does not achieve DP, then it cannot achieve El and BE simultaneously
Besides, we also investigate the connections between EI and ER in Appendix A.2
3 ACHIEVING EQUAL IMPROVABILITY
In this section, we discuss methods for finding classifier that achieves El fairness. Following existing un-processing techniques (Zaaar et al., 2017c Donini et al. 2018 Zafar et al. 2017a| Cho et al.. 2020), we focus finding a fair classifier by solving To be specific, we first derive differentiable penalty term Us that approximates the unfairness with respect EI, and then solve regularized empirical minimization problem having the unfairness as the regularization term. This optimization problem can be represented as
celrmess-regulanne
optimization problem.
(I A)
min JEF
Σ fly,, (xx)) + XU8
(1)
where y+) is the given dataset, L: {0, x [0. R is the loss function, F is the set of classifiers we are searching over, and À E [0, 1) is hyperparameter that balances fairness and prediction loss. Here we consider three different ways of defining the penalty term Ug. which are (a)
covariance-based, (b) kernel density estimator (KDE)-based, and (c) bass- methods. We first introduce how we define Us in each method, and then discuss how we solve (
Covariance-based El penalty. Our first method is inspired by Zafar et al. 2017c). which measures the unfairness of a score-based classifier by the covariance of the sensitive attribute z and the score (x), when the demographic parity (DP) fairness condition (P
0.5/z = 2) P(f(x) > 0.5) holds for all 2) is considered. The intuition behind this idea of measuring the covariance is that a perfect fair DP classifier should have zero correlation between and f(x). By applying similar approach to our fairness notion in Def. 2.1 the El unfairness is measured by the covariance between the sensitive attribute and the maximally improved score of rejected samples within the effort budget. In other words, (Cov(z, max Ax f(x + Ax) f(x < 0.5))² represents the El unfairness of a classifier f where we took the square to penalize negative correlation case as well. Let I_ = {i fxx)) 0.5) be the set of indices of unqualified samples, and Ž ΣiEl_ 2-/1T-I- Then, EI unfairness can be approximated by the square of the empirical covariance, i.e.,
2
Us+
(2: -
max f(x: + Axi) ||xx,
Σ
max f(x, + = Axi;
iET_
JEL_
Since EvEr_ zZ) (EjEL. max AM, || f(x; + Ax2) / //,))/1(11)) = 0 from Eiel (z, 2) = 0.
we have Us-
EiEL (z+ 2) max 21 f(x; + Axx)
KDE-based EI penalty. The second method is inspired by Cho et al. (2000), which suggests to first approximate the probability density function of the score f(x) via kernel density estimator (KDE) and then put the estimated density formula into the probability term in the unfairness penalty, Recall that given m samples Y1. .......Y... the true density By on is estimated by KDE as Jy (5) e m
mh Dist 9k
8-Yz
where Is is kernel function and h is a smoothing parameter.
Let y A (65 f(x Ax2) be the maximum score achievable by improving feature x, within budget 5, and T- = {i: f(x)) < 0.3, = 2} be the set of indices of unqualified samples of group Then, the density of ym for the unqualified samples in group 2 can be approximated as
Here we apply this KDE-based method for estimating the El penalty term in Def. 2.T
yymay| 50,55 (gmaax) A 1
Σ
max
9k
SEI
Then, the estimate on the left-hand-side (LHS) probability term Def. 2.1 is represented as = Jos gymes fox) Jd
(maxp(Ax))s fx + Ax) 2 0.5| f(x) < 0.5, 25 =
2This term is differentiable with respect model parameters, since Os is differentiable w.r.t max and
y max maxiax, 156 f(x: Ax,) differentiable w.r.t. model parameters from (Danskin 1967
5

---

Published as a conference paper at ICLR 2023
where GR(() _ Jr= g) gx(y)dy. Similarly, we can estimate the right- hand-side (RHS) probability term in Def. 2.1 and the El-penalty Us is computed as the summation of the absolute difference of the two probability values (LHS and RHS) among all groups 2.
0..5 m TT Eiel... Gk
(0.5-1)- (0.3-
h
dif- Loss-based EI penalty. Another common way of approximating the faimess violation ferentiable term is to compute the absolute difference of group-specific losses (Roh et al.) [002] Shen et al. 2022). Following the spirit of EI notion in Def. 2.1 we define EI loss of group 2 as
L2 [T_.al LiEr. e (1, maxjjxx, fx; + Axx)). Here, L, measures how far the rejected samples in group z are away from being accepted after the feature improvement within budget 8. Similarly, El loss for all groups is written as L - EvEz L. Finally, the El penalty term is
defined as Ug - ExEz I.g E
Solving (1. For each approach defined above (covariance-based KDE-based and loss- loss-based), the penalty term Us is defined uniquely. Note that in all cases, we need to solve a maximization problem max |s f(x Ax) in order to get Ug- Since (1) is a minimization problem containing Us in the cost function, it is essentially a minimax problem. We leverage adversarial training techniques to solve [[]. The inner maximization problem is solved using one of two methods: (i) derive the closed-form solution for generalized linear models, (ii) use projected gradient descent for general settings. The details can be found in Appendix B.4
4 EXPERIMENTS
This section presents the empirical results of our EI fairness notion. To measure the fairness violation, we use El disparity= ma [P [[(maxp(Ax)=< f(x + Ax) 2 0.5 f(x) < 0.5,
2) - P0-aX < f(x + Ax) 2 0.5| fx) < 0.5).. First, in Sec. 4.1 we show that our methods suggested in Sec. B] achieve EI fairness in various real/synthetic datasets. Second, in Sec. 4.2 focusing on the dynamic scenario where each individual can make effort to improve its outcome, we demonstrate that training an El classifier at each time step promotes achieving the long-term fairness, i.e., the feature distribution of two groups become identical in the long run. In Appendix C.4] we put additional experimental results comparing the robustness of EI and related notions including ER and BE. Specifically, we compare (i) the robuier-roustnnsss of EI and ER, and (ii) the robustness of El and BE to imbalanced group negative rates.
4.1 SUGGESTED METHODS ACHIEVE EI FAIRNESS
Recall that Sec. 3 provided three approaches for achieving fairness. Here we check whether such methods successfully find a classifier with a small El disparity, compared with ERM which does not have fairness constraints. We train all algorithms using logistic regression (LR) in this experiment. Due to the page limit, we defer the presentation of results for (1) two-layer ReLU neural network with four hidden neurons and (2) a five-layer ReLU network with 200 hidden neurons per layer to Appendix C.3, and provide more details of hyperparameter selection in Appendix C.2
Experiment setting. For all experiments, we use the Adam optimizer and cross cross-entropy loss. We perform roos-validattonn on the training set find the best hyperparameter. We provide statisties for five trials having different random seeds. For the KDE-based approach, we use the Gaussian kernel.
Datasets. We perform the experiments on one synthetic dataset, and two real datasets: German Statlog Credit (Dua & Graff 2017), and ACSIncome-CA (Ding et al. (021). The synthetic dataset has two non-sensitive attributes
(X1, X2), one binary sensitive attribute z, and binary label y. Both features 11 and X2 are assumed to be improvable. We generate 20,000 samples where (x, y, pair of each sample is generated independently as below. We define and (ylz 2) as Bernoulli random variables for all E {0, 1). and define (xly y, z) as multivariate Gaussian random variables for all y; 2 E (0, 1). The numerical details are in Appendix C. The maximum effort 8 for this dataset is set to 0.5. The ratio of the training versus test data is 4:1.
German Statlog Credit dataset contains 1,000 samples and the ratio of the training versus test data is 4:1. The task is to predict the credit risk of an individual given its financial status. Following Jiang & Nachum 2020), we divide the samples into two groups using the age of thirty as the boundary, i.e.
1 for samples with age above thirty. Four features x considered improvable: checking account. saving account, housini ing and occupat t ion, all of which are ordered categorical features. For example, the occupati in feature has four levels: (1) unemployed, (2) unskilled, (3)

---

Published as a conference paper at ICLR 2023
Table 2: Error rate and EI disparities of ERM and three proposed El-regularized methods on logistic regression (LR). For each dataset, the lowest EI disparity (disp.) value is in boldface. Classifiers obtained by our three methods have much smaller El disparity values than the ERM solution, without having much additional error.
METRODS
DATASET
METRIC
ERM
COVARIANCE BASED
KDE-BASED
BASS-BASED
SYNTHETIC
EUROR RAID())
EI D1S
.221 = .001
.007
.003
.203
.001
.003
.50 + .001
003
.002 + .001
.24 + .001
GERMAN STAT.
ERROR RaTI())
El DISP
.041 = .008
.220 = .009
.021
.262 .009
.019
.033 + 026
.23 .04
.015 + .009
.008
ACSINCOME-CA
ERROR RATE())
EI DISP.()
.031 .001
.000
.200
.008
.000
.001
.005 1: .001
.198
.000
.006 1 .001
113 .000
skilled, and (4) highly qualified. We set the maximum effort 8 = meaning that an unskilled man (with level 2) can become a skilled man, but cannot be a highly qualified man.
ACSIncome-CC CA dataset consists of data for 195,665 people and is split into training/test sets in the ratio of 4:1. The task is predicting whether a person's 's income would exceed 50K USD per year. We use sex as the sensitive attribute; we have two sensitive groups, male and female. We select education level (ordered categorical feature) as the improvable feature. We set the maximum effort 8 = 3.
Results. Table 2 shows the test er- for rate and test EI disparity (disp.)
Senthatic
German
ACSDnrees.C
1.30
for ERM and our three El-regularized methods (covariance-basse,
Brror Rate
0.244
0.19
KDE- based, and loss-based) suggested in Sec. For all three datasets, our EI- regularized methods successfully re- duce the El disparity without increas- ing the error rate too much, compared with ERM. Figure 3 shows the trade- off between the error rate and EI dis- parity of our El-regularized methods. We marked the dots after running each method multiple times with different penalty coefficients X, and plotted the frontier line. For the synthetic dataset with the Gaussian feature, we numerically obtained the per- formance of the optimal EI classifier, which is added in the yellow line at the bottom left corner of the first column plot. The details of finding the optimal EI classifier in Appendix [B.] One can confirm that our methods of regularizing El are having similar tradeoff curves for the synthetic dataset. Especially, for the synthetic dataset, the tradeoff curve of our methods nearly achieves that of the optimal El classifier. For German and ACSIncome-CA datasets, the loss-based method is having a slightly better tradeoff curve than other methods.
Optinal
1.26
0.18
0.22
1.20
0.00
0.005
0.10
0.00
0.05
0.00
0.02
EI Disparioy
EL Dispority
HI Disparity
Figure 3: Tradeoff between EI disparity and error rate. We run three El-regularized methods suggested in Sec. B for different regularizer coefficient À and plot the frontier lines. For the synthetic dataset, the tradeoff curve for the ideal classifier is located at the bottom left corner, which is similar to the curves of proposed El-regularized methods. This shows that our methods successfully find classifiers balancing EI disparity and error rate.
4.2 EI PROMOTES LONG-TERM FAIRNESS IN DYNAMIC SCENARIOS
Here we provide simulation results on the dynamic setting, showing that El classifier encourages the long-term fairness, i.e., equalizes the feature distribution of different groups in the long run 4.2.1 DYNAMIC SYSTEM DESCRIPTION
We consider a binary classification problem under the dynamic scenario with T rounds, where the improvable feature x, E R.. and the label y: E (0, 1) of each sample well as the classifier fa evolve at each round t E {0, ... T - 1}. We denote the sensitive attribute as z E {0, 1}. and the estimated label as 9r- We assume z Bern(0.5) and (x,
pf*)) ~N(n( (=) {o (2)) To mimic the admission problem, we only accept a fraction a E (0, 1) of the population, Le,, the true label is
2)
modeled as y, 1 [xx 2 { where x is the (1 a) percentile of the feature distribution round L. We consider z-aware linear classifier outputting 8, - 1(x, 2 -("), which is parameterized by the thresholds (7(") 7, ()) for two groups. Note that this classification rule is equivalent to defining
score function fz 2) = 1/ (exp(r(()
(x) - x) + 1) and y, = 1f z) 2 0.5].
Updating data parameters (pl (a)). (²)). At each round f, we allow each sample can improve its feature from x to x + exx). Here we model e(x)) v(x;;)
- 1xx
(
2 AApeendix D provides analysis on the effect of fairness notions on the long- term fairess when a single step of feature improvement is applied, for toy examples. Our results show that El better equalizes the feature distribution (compared with other fairness notions), which coincides with our empirical results in Sec. 4.2
7

---

Published as a conference paper at ICLR 2023
Longllen Unteiinos
ERM
UP
0.4
04
0.50
6.2
ER
02
I.FER
(Curs)
Roumi
P(D)) at each round / for various algorithms. Con- sider the binary classification problem over two groups, under the dynamic scenario where the data distribution and the classifier for each group evolve over multiple rounds. We plot how the long-term unfairness (measured by the total variation distance between two groups) changes as round increases. Here, each column shows the result for different initial feature distributions, details of which are given in Sec. [42.2] The long-term unfairness of EI classifier reduces faster than other existing fairness notions, showing that El proposed in this paper is helpful for achieving long-term fairness.
Figure 4: Long-term unfairness drv (P()), (0)
for a constant 3 > O. In this model, the rejected samples with larger gap (T.( - x) with the decision boundary are making less effort Az, which is inspired by the intuition that a rejected sample is less motivated to improve its feature if it needs to take large amount of effort to get
accepted in one scoop. More detailed justification of the e(-) selection is provided in Appendix C.5 C.5
After such effort is made, we compute the mean and standard deviation of each group: 12+1
(2)
(x + v(x; ();; Pi ,o! )dx and of41 V (xr + v(a;=) where <(; ju, o) is the pdf of NV,,, o²). We assume that the feature X in the next round follows a Gaussian distribution parameterized by (1141;
(z) ) 2 p4 (=) o )d,
(=)
(41) (1(41:0(41) for ease of simulation.
Updating classifier parameters (7(")) (TT (.) At each round t, we update the classifier depending
on the current feature distribution x₃. The El classifier considered in this paper updates (T²") ())
as below. Note that the maximized score max] 58 f(x + Ax) in Def. 2.1 can be written as
fe(xx + 5t, z). and the equation max |Ax]|ss f(x + Ax) 2 0.5 equivalent to X + 5 > Tt
Consequently, El classifier obtains (T Tt by solving
(0) (1)
min pxx 7 Tt |z z 0,x, < (0) P(x + 12 12= 1,x, <T( s.t. P(,, xy)) Sc,
where c E [0, 1) is the maximum classification error rate we allow, and d; is the effort level at iteration f. In our experiments, & is chosen as the mean efforts the population makes, i.e., &
v(2:2))(z) 24 [ )dz. Meanwhile, we can similarly obtain the classifier for DP. E l
BE, ER, and ILFCR constraints, details of which are in Appendix C.6 In the experiments, we numerically obtain the solution of this optimization problem.
4.2.2 EXPERIMENTS ON LONG-TERM FAIRNESS
We first initialize the feature distribution in way that both sensitive groups have either different mean (i.e., Pb # 10 (1))) or different variance (i.e., (00) * of ()) At each round E {1.-.. ,T). we update the data parameter (n(,), ,o (+)) for group E {0. and the classifier parameter (T,(0) -T follow- ing the rule described in Sec. 1.2. At each round E {I..... T). we measure the long-term unfair- ness defined as the total variation distance between the two group distributions: drv (Pv()) p(())=
1 (0(2; Mz az
(0) (0)
10-(x;;)) (1) ot (1) [dr. We run experiments on four different initial feature dis-
tributions: (i) (16) 00 .40 )))
(0) (0) (1) (1)
1, 0,0,), (ii) (n) ,00 :o0 _)0)) (0, 1, 1), (iii) (0) (1)
(0) (0) (1)
(n6 0 M0 00
(0) (1) (1) = (0, 2, 0, 1). and (iv) (40 o P0 (()) = (0, 0.5, 1, 1.5,,, respectively.
We set = 0.2, 0.1, = 0.25.
Baselines. We compare our El classifier with multiple baselines, including the empirical risk minimization (ERM) and algorithms with faimess constraints: demographic parity (DP), bounded effort (BE) (Heidari et al. 2019), equal recourse (ER) (Gupta et al., 2019). and individual-lever fair causal recourse (ILFCR) (Von Kügelgen al. 2022). In particular, we assume a causal model for solving the ILFCR classifier for this specific data distribution, which is described in detail in Appendix C.6.
Results. Fig. shows how the long-term unfairness (P p(()) changes as a function of round for cases (i) (iv) having different initial feature distribution. Note that except ILFCR, other fairness notions (DP, BE, ER, and El) yield lower long- term unfairness compared with ERM, for cases (i), (ii), and (iv). More importantly, EI accelerates the process of mitigating long-term unfairness,
8

---

Published as a conference paper at ICLR 2023
Idital dateiloiioo
ERM
DF
BR
ER
ILFOR
1.5
MALZI
Go
0.1
0.0
0.5
Fry SAL
Fry B3
Ary a.3
Koy in
Hey 2.0
0.1
0.0
0.5
dis in 1i24
Hyy 28
An will
For in tol
Hvy LiL
0.1
0.0
0.22
Sry-
Hry
Ary
Kry
Mry 101
0.1
0.00
Figure 5: Evolution of the feature distribution, when we apply each algorithm for / = 3 rounds. At each row, the leftmost column shows the initial distribution and the rest of the columns show the evolved distribution for each algorithm, under the dynamic setting. Compared with existing fairness notions (DP, BE, ER, and ILFCR), El achieves a smaller feature distribution gap between groups.
compared to other fairness notions. This observation highlights the benefit of El in promoting true equity of groups in the long run. Fig. 5 visualizes the initial distribution (at the leftmost column) and the evolved distribution at round t = 3 for multiple algorithms (at the rest of the columns). Each row represents different initial feature distribution, for cases (i) - (iv). One can confirm that El brings the distribution of the two groups closer, compared with baselines. Moreover, in Appendix C.7 we explore the long-term impact of fairness notions on a different dynamic model, where most existing methods have an adverse effect on long-tern fairness, while EI continues to enhance
5 RELATED WORKS
Fairness-aware algorithms. Most of the existing fair learning techniques fall into three categories:
pre-processing approaches (Kamiran & Calders 2012] 2010; Gordaliza et al. 2019 Jiang &
Nachum 2020), which primarily involves massaging the dataset to remove the bias; ii) in-processing
approaches (Fukuchi et al. 20133 Kamishima et al. 2012; Calders & Verwer 2010 Zafar et al.
2017c a Zhang et al.) 2018 Cho al.) 2020: Roh et al. 2020 [021] et al.
2022). adjusting
the model traiiigg for fairness; ini) post- processing approaches (Calders & Verwer 2010: Alghamdi
ct al. 2020 Wei al. 2020, Hardt et al. 2016) which achieve fairnsss by modifying given unfair
classifier. Prior work (Woodworth et al. 2017 showed that the in-processing approach generally
outperforms other approaches due to its flexibility. Hence, we focus on the in-processing approach and propose three methods to achieve EI. These methods achieve El by solving fairness-regularized optimization problems. In particular, our proposed fairness regularization terms are inspired by Zatar
et al.
[2017c; Cho et al. 22200;; ; Roh et al. 2021 Shen et al. (2022).
Fairness notions related with EI
See Table and the corresponding explanation given in Sec.
Fairness dynamics. There are also few attempts study the long-term impact of different fairness policies (Zhang et al., 2020: Heidari et al.) 2019 Hashimoto et al. 2018). In particular, Hashimoto et al. (2018) studies how ERM amplifies the unfairness of a classifier in the long run. The key idea is that if the classifier of the previous iteration favors a certain candidate group, then the candidate groups will be more unbalanced since fewer individuals from the unfavored group will apply for this position. Thus, the negative feedback leads to a more unfair classifier. In contrast, (Heidari et al.] (2019) and Zhang et al. (2020) focus more on long-term impact instead of classification fairness. To be specific. of evenness, central
Heidari Heidari et al. (2019) studies how fairness intervention affects the different groups in terms centralization....mcmocco lzztiinn, and clustering by simulating the population's ' response through effort. Zhang et al. (2020) investigates how different fairness policies affect the gap between the qualification rates of different groups under a partially observed Markov decision process. Besides, there are few works which study how individuals may take strategic actions to improve their outcomes given classifier (Chen et al., (02T). However, [Chen et al.) (202T) aims to address this problem by designing an optimization problem that is robust strategic manipulation, which is orthogonal to our focus.
6 CONCLUSION
In this paper, we introduce Equal Improvability (EI), group fairness notion that equalizes the potential acceptance of rejected samples in different groups when appropriate effort made by the rejected samples. We analyze the properties of El and provide three approaches to finding a classifier that achieves EI. While our experiments demonstrate the effectiveness of the proposed approaches in reducing EI disparity, the theoretical analysis of the approximated El penalties remains open. Moreover, we formulate a simplified dynamic model with one dimensioaa features and binary sensitive attribute to showcase the benefits of EI in promoting equity in feature distribution across different groups. We identify extending this model to settings with multiple sensitive attributes and high-dimensional features as interesting future direction.
9

---

Published as a conference paper at ICLR 2023
ACKNOWLEDGEMENT
Yuchen Zeng was supported in part by NSF Award DMS-2023239, Ozgur Guldogan and Ramtin Pedarsani were supported by NSF Award CNS-2003035, and NSF Award CCF-1909320. Kangwook Lee was supported by NSF/Intel Partnership on Machine Learning for Wireless Networking Program under Grant No. CNS- the University of Wisconsin Mandisn,,,, Office of the Vice Chancellor for Research and Graduate Education with funding from the Wisconsin Alumni Research Foundation. The authors would also like to thank the anonymous reviewers and AC for their valuable suggestions.
and by the Understanding and Reducing Inequalities Initiative of
REFERENCES
Wael Alghamdi, Shahab Asoodeh, Hao Wang. Flavio P. Calmon, Dennis Wei, and Karthikeyan Nate- san Ramamurthy. Model projection: Theory and applications to fair machine learning. In 2020 IEEE International Symposium Information Theory (ISIT), pp. 2711-2716, 2020. doi: 10.1 109/111144444422000011111
Toon Calders and Sicco Verwer. Three naive bayes approaches for discrimination--fee free classification.
Data Mining and Knowledge Discovery, 21 2010. doi: 10.1007/s10618-00000
URL https: / wwt.ooo.orr............0.......0 1tt.:/10..00/1/111 httpp:://ao...ggg/00000010101111
010-0190-2
Yatong Chen, Jialu Wang, and Yang Liu. Linear classifiers that encourage constructive adaptation, 2021.
Valeriia Cherepanova, Vedant Nanda, Micah Goldblum, John P Dickerson, and Tom Goldstein. Technical challenges for training fair neural networks. arXiv preprini urXiv:2102.06764 2021.
Jaewoong Cho, Gyeongjo Hwang, and Changho Suh. A fair classifier using kernel density estimation. Advances in Neural Information Processing Systems (NeurIPS), 33:15088 50888-199,,,, 2020.
John Danskin. The theory of max-min and its application to weapons allocation problems. In Springer, 1967.
Frances Ding, Moritz Hardt, John Miller, and Ludwig Schmidt. Retiring adult: New datasets for fair machine learning. Advances in Neural Information Processing Systems, 34, 2021.
Michele Donini, Luca Oneto, Shai Ben-David, John Shawe-Taylone and Massimiliano Pontil. Empiri- cal risk minimization under fairness constraints. In Advances in Neural Information Processing Systems (NeurIPS), volume 31, pp. 2796-2806, 2018.
Dheeru Dua and Casey Graff. UCI machine learning repository, 2017. URL http:://rcc/iieeee
ics. wci.ccic.. ucs.uuci eddumm
Cynthia Dwork, Moritz Hardt, Toniann Pitassi, Omer Reingold, and Richard Zemel. Fairness through awareness. In Proceedings of the 3rd Innovations Theoretical Computer Science Conference, ITCS 12, pp. 214-226, 2012. ISBN 9781450311151, doi: 10.114522002236.200025. URL https: org/ 10. wet..11119222225.. 2090255
Kazuto Fukuchi, Jun Sakuma, and Toshihiro Kamishima. Prediction with model- based neutrality, In Machine Learning and Knowledge Discovery Databases, pp. 499-514, 2013. ISBN 978-3-642- 40991-2.
Paula Gordaliza, Eustasio Del Barrio, Gamboa Fabrice, and Michel Loubes. Obtaining faimess using optimal transport theory. In Proceedings of the 36th International Conference on Machine Learning (ICML), volume 97 of Proceedings of Machine Learning Research, pp. 2357-2365, 2019. URL http::://pocceeee///eeee ngs mlr wrwss/ssssss.... /ttp wwtpp//e////////aaaaraaa.. 1tt.ia.ttmmlll
Vivek Gupta, Pegah Nokhiz, Chitradeep Dutta Roy, and Suresh Venkatasubraamanian. Equalizing recourse across groups. arXiv preprint 1eXiv:1909.000
2019.
Moritz Hardt, Eric Price, and Nati Srebro. Equality of opportunity in supervised learning. In Advances in Neural Information Processing Systems (NIPS), volume 29, pp. 3315-3323, 2016.
10

---

Published as a conference paper at ICLR 2023
Tatsunori Hashimoto, Megha Srivastava, Hongseok Namkoong, and Percy Liang. Fairness without demographics in repeated loss minimization. In Proceedings of the 35th International Conference on Machine Learning (ICML), volume 80 of Proceedings Machine Learning Research, pp. 1929- 1938, 2018.
ngs ml press hat/00//aahimmmaa
8a html
Hoda Heidari, Vedant Nanda, and Krishna P. Gummadi. On the long-term impact of algorithmic decision policies: Effort unfairness and feature segregation through social learning, 2019.
Wen Huang, Yongkai Wu, Lu Zhang, and Xintao Wu. Fairness through equality of effort, 2019.
Heinrich Jiang and Ofir Nachum. Identifying and correcting label bias machine learning. In
Proceedings the Twenty Third International Conference Artificial Intelligence and Statistics, volume 108 of Proceedings of Machine Learning Research, pp. 702-712, 2020. URL http:
//proceedings mlr press sitress/vv080 v108/ (aai00//aaag20ae html
Kamiran and T.G.K. Calders. Classification with no discrimination by preferential sampling.
In Informal proceedings of the 19th Annual Machine Learning Conference of Belgium and The Netherlands, pp. 1-6, 2010.
Faisal Kamiran and Toon Calders. Data preprocessing techniques for classification without discrimi- nation. Knowledge and Information Systems, 33:1-33, 2012.
Toshihiro Kamishima, Shotaro Akaho, Hideki Asoh, and Jun Sakuma. Fairness-aware classifier with prejudice remover regularizer. In Machine Learning and Knowledge Discovery in Databases, pp. 35-50, 2012. ISBN 978-3-642-334866
Dragoslav Mitrinovic and Petar M Vasic. Analytic inequalities, volume 1. Springer, 1970.
Yuji Roh, Kangwook Lee, Steven Whang, and Changho Suh. FR-train: A mutual information- based approach to fair and robust training. Proceedings of the 37th International Conference Machine Learning (ICML), volume 119 of Proceedings of Machine Learning Research, pp. 8147-8157, 2020. httlltttp//prceeeiiiiii
.mlr mwl..press/vise (ateesssvv19/ooh00aa roh20a. attoh20a.hhllll
Yuji Roh, Kangwook Lee, Steven Fuijong Whang, and Changho Suh. Fairbatch: Batch selection for model fairness. In International Conference on Learning Representations (ICLR), 2021. URL
https: http://wwwweeeeetteeeeeeeeee
net
Aili Shen, Xudong Han, Trevor Cohn, Timothy Baldwin, and Lea Frermann. Optimising equal opportunity fairness in model training. arXiv preprint arXiv:2205.02393, 2022.
Julius Von Kügglggen, Amir-Hossein Karimi, Umang Bhatt, Isabel Valera, Adrian Weller, and Bernhard Schölkopf. On the fairness of causal algorithmic recourse. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 36, pp. 9584-9594, 2022.
Dennis Wei, Karthikeyan Natesan Ramamurthy, and Flavio Calmon. Optimized score transformation for fair classification. In International Conference on Artificial Intelligence and Statistics (AIS- TATS), volume 108 of Proceedings of Machine Learning Research, pp. 1673-1683, 2020. URL
http://prroeeddinga mlr. siteess/vl000 wwwp///wwwwww....o.. www.wa. html
Blake Woodworth, Suriya Gunasekar, Mesrob I. Ohannessian, and Nathan Srebro. Learning non-discriminatory predictors. In Proceedings of the 2017 Conference on Learning The- ory, volume 65 of Proceedings of Machine Learning Research, pp- 1920-1953, 2017. URL http::/proceediing www.mmrr..mmmm www.:essww.pp.er.eeemmme.me htlppp/eeee///////oootttttt
Yongkai Wu, Lu Zhang, and Xintao Wu. Counterfactual fairness: Unidentification. bound and algorithm. In Proceedings of the
International Joint Conference on Artificial
Intelligence, 2019.
Muhammad Bilal Zafar, Isabel Valera, Manuel Gomez Rodriguez, and Krishna Gummadi. Faireess beyond disparate treatment & disparate impact: Learning classification without disparate mistreat- ment. In Proceedings of the 26th International Conference on World Wide Web, pp. 1171-1180, 2017a.
11

---

Published as a conference paper at ICLR 2023
Muhammad Bilal Zafar, Isabel Valera, Manuel Gomez Rodriguez, Krishna P. Gummadi, and Adrian Weller. From parity to preference- notions of faimesss in classification. Advances in Neural Information Processing Systems (NIPS), NIPS' 17, pp. 228 238, 2017b. ISBN 11866964
Muhammad Bilal Zafar, Isabel Valera, Manuel Gomez Rogriguez, and Krishna Gummadi. Fair- ness Constraints: Mechanisms for Fair Classification. In International Conference on Artificial Intelligence and Statisties (AISTATS), volume 54, pp. 962-970, 2017c.
Brian Hu Zhang, Blake Lemoine, and Margaret Mitchell. Mitigating unwanted biases with adversarial learning. In Proceedings of the 2018 AAAT/ACM Conference on Al, Ethics, and Society, pp. 335-340, 2018.
Xueru Zhang, Ruibo Tu, Yang Liu, Mingyan Liu, Hedvig Kjellström, Kun Zhang, and Cheng Zhang. How do fair decisions fare in long-term qualification?, 2020.
12

---

Published as a conference paper at ICLR 2023
A THEORETICAL RESULTS
A.1 CONNECTIONS BETWEEN EI, DP, AND BE
In this section, we provide the proof of Theorem 2.3 and Corollary 2.6
Proof of Theorem 2.5 All we need to prove are three statements:
1. Prove that El and BE imply DP
2. Prove that DP and El imply BE
3. Prove that BE and DP imply EI
Below we prove each statement.
EI, BE
DP
Suppose a classitier achievess EI and BE. Recall that classifier achieves EI if
P
max S6
Axx 0.5| f(x) (0,, =P
max m(Ax))S
Axx <.5
(2)
and a classifier achieves BE if
P
max f(x Ax) 2.5, f(x) <0.5 =P
max (a(Ax))
f(x Ax) (x), <0.
((Ax))S
(3)
By dividing both sides of 3 by the both sides of
2 we have
P
f(x + Ax 0.5, 00. (0.5) ((Ax))55
max
P
max Ax)+ <0.5
u(Dxi)S
PP
max [(x+Ax) 0.5 f(x) < 0.5,2=2
max [xx+Ax)200 2.5 f(x) < <0.
{(
((AX)SS
Then, can be simplified as
(f(() < 0.5 z= = 0.5),
which implies that the classifier achieves demographic parity,
(f((x) 2 0.5 = 2) = (f(x) 2 0.5)
DP, EI = BE Suppose classifier f achieves DP and El. Recall that a classifier achieves DP (f 2 0.5 z = 2) = (f(x) 2 0.5),
which implies
(((()) < 0.5 2) (J(x) < 0.5).
(4)
Recall that a classifier achieves EI if
TP max f(x Ax) (8
0.5| f(x) < 0.5,
=P
max
f(x Ax) <0.
(5)
By multiplying both sides of [ we have
max f(x Ax) 2 0.5 f(x) < <0.52==2 P(f(x) 2== ((AX))5
=P PP
f(x + Ax) 0.5 f(x) < <0..) P(f(x) < <0.))
max 4(AxiSS8
Then, it can be simplified as
P max f(x + Ax) Ax) <0.
=P max f(x 0x) ((AA))SS
((AN))S
which implies that the classifier f a'chieves BE.
13

---

Published as a conference paper at ICLR 2023
3. BE, DP El
Suppose classifier f achieves BE and DP. Recall that classifier achieves DP if P ((f(x) 2 0.5 Z z) = P (f(x) 2 0.5),
which implies
(f((x) < 0.5 Z = 2) = (f(x) < 0.5)
(6)
Recall that a classifier achieves BE
P
max #(Ax))g
Ax) < 0.5 = =P
max f(x (xx, (((xx)g
(7)
By dividing both sides of by the both sides of 6 we have
IP
max f(x + Ax) Ax) f ((
z=
max f(x (x++Ax) 20., MAXI)S
(((()) 0-5
P(((x) 0.5)
Then, can be simplified as
max f(x 3x) 2 0.5 (00) =P
max (a(Ax))
(x) f(x) < 0.5
((Ax))5
which implics that the classifier f achieves EI.
Proof of Corollary 2.6 The Corollary 2.6 can be proved directly from Theorem 2.3
A.2 CONNECTIONS BETWEEN EI AND ER
In this part, we investigate the connections between EI and ER.
Lemma A.1. Consider x z characterized by two accepting thresholds (To: TI), where To, TI E TR. If classifier satisfies EI, then it satisfies ER.
( for E {0.1). 12,0 E R. and classifiers
Proof. Here we use = 1 - Q and é to denote the CDF and PDF standard Gaussian distribution, respectively. We consider the cost function --
Recall the definition of El disparity and ER disparity
El Disparity
|P
max ((Ax) <5
f(x + Ax) > 0.5 fx) 0.5,
xST0
x3-T0-
P
max p(
Ax) > 0.5 f(x) 0.5,
ER Disparity
E
min
p(Ax)
f(x) 0.5, 0)
(xx+Ax)20.5
AST0
-
E
min
m(Ax) [(x) < 0.5,7
flx+As)205
Consequently, the EI constraint and ER constraint can be written as El Disparity (7o. m)) + - 5 -
To
PAg
8
M1
T1
P1
0,
(8)
TT
t μg
ER Disparity (To,T)) T Mo)/o) /r)
(T) 1)
dl
1 lkl
(71 t)p
dt
0 (9)
Φ( 11)
14

---

Published as a conference paper at ICLR 2023
In this proof, will first show that achieving EI is equivalent to Tu Ao 71 A1, and then show that the classifier with To Po = T1 - P1 satisfies the ER constraint.
1. constraint.
Let pp(x) (0(====00 0(=--)/0(() First, show that yp is strictly increasing function. Note that
(1(x) oΦ (#)
+
x
6
Φ
Therefore, show that to strictly increasing, it is sufficient show that
x
1
x
(10)
We show that (10) is equivalent as the following inequality by dividing both the left-hand side and right-hand side by Φ( (==6) ))()))
/0 d
(11)
Note that 1-+(1 o(1
is known literatures as Mills' ratio MMirinovvic & Vasic 1970), which is
strictly decreasing on R. Therefore,
+6 øc is strictly increasing on R. Since 2-8
holds, thereby (TO) holds and is strictly increasing.
Given that (p(x) $ ==
( is strictly increasing function on R.
= ppp - po) ς -1111 = 0
yields that
140 141-
2. ER constraint.
We first note that
[
(To t)o ( 110 dt d'=t-mn
To-Po
(To Ho - t) (m) dt
Let (xx) = 0(5/o]] 1_ (x - --)@( L dt. It is clear that ER constraint is equivalent to
|1b(ro no) </ - -11)
Therefore, the classifier with To 140 μl clearly satisfies the ER constraint.
Combining all the discussion above completes the proof.
B SUPPLEMENTARY MATERIALS ON THE FAIRNESS NOTIONS
Recall that in Sec. 2 and Sec. this paper proposes a new fairness notion called equal improvability (EI), compares it with other existing effort-based fairness notions, and finds a classifier by solving El-constrained optimization which is formulated as minimax problem. In Sec. B.I. we first explain what each term in the definition of El means. Then, we provide more details of reward function selection of bounded effort (BE) (Heidari et al. 2019) and discuss the vulnerability of equal recourse (ER) (Gupta et al. 2019) in Sec. B.2 and B.3, respectively Then in Sec. B.4 we provide how we solved the inner maximization problem in the El-constrained optimization. Finally, in Sec. [B.5] provide numerical methods for finding the optimal solution for the El-constrained problem, under simple synthetic dataset setting.
15

---

Published as a conference paper at ICLR 2023
B.1 MEANING OF EACH TERM IN THE DEFINITION EI
To help readers better understand our El definition, here we explain what each term means in El definition means. Let the data sample (x, y, z) follows the distribution P(x.y.)- The meaning each term of EI defined in Def. is detailed below.
P x.y.2 ~ 11022Pxx Px.x
max (x + 2 0.5 (8
[(x < 0.5,
Randomacss is over the data distribution
Event in which the sample comes group and gets rejected
Maximum after improvement
Event which the sumple accepted after impreveeeent
P Xx,, Px,y.
max f(x (( 156
Ax)
2
0.5
f(x)
< 0.5
Randornness the data distribution
Event which sample gets rejocted
score improvement
Event in which the sample accepted after improvement
B.2 SPECIFYING THE REWARD FUNCTION FOR BE
In this part, we introduce how we set the reward function so that we can connect BE with EL. Recall that the reward function in Heidari et al. (2019) is defined the benefit gained by changing individual's 's characteristics from w (x, y) to = 3"):
R(w, w/ b(f(x'), bxf()),
where is the benefit function, and x' Ax the updated feature. If we set the benefit function as 6( ((f(x),)) v) 1xf(x) 2 0.5}, then the reward function becomes:
R(w, w') 1[f(x Ax) 2 0.5) 1(f(x) 2 0.5}
Then, the bounded effort fairness is defined as:
max R(w, w') s.t. m(Ax)= < ,|z = = E max Ax
R(w, wo) st. u(Ax) < <o] for all
Ax
Consequently,
max R(w, w') s.t. ((Ax) < <)
if maxx(Ax)<d f(x + Ax) 2 0.5 and f(x) < 0.5
Ax
otherwise
Therefore, we can write expectation as probability:
P max f(x Ax) Z 0.5, 0.5 z z= -P
max f(x Ax) 2 0.5, f(x) < 0.5)
(M(Ax)58
(((Ax)SS
which is in Table i
B.3 VULNERABILITY ER OUTLIERS
As mentioned in Table ER is vulnerable to outliers. Here provide simple analysis. Suppose an outlier, having feature-attribute pair (x, z). added to the dataset with n samples. Let the outlier is misqualified f(x) 0.5, and requires effort y (((x)
M to achieve f(x Ax) 0.5. In such case, the EI disparity increases at most since EI measures the portion of samples with improved outcomes after making efforts. On the other hand, the ER disparity increases by Mr since ER measures the minimum required efforts averaged over all samples. Note that a single outlier with a large M can significantly increase the ER disparity, which does not happen for EI. Thus, much more robust to outliers, compared with ER. We conduct a numerical experiment Sec. C.4.1 to further highlight the robustness of EI outliers.
observe that EI
16

---

Published as a conference paper at ICLR 2023
B.4 SOLVING THE INNER MAXIMIZATION PROBLEM FOR EI
As explained in Sec 3 finding a EI classifier can be formulated as a minimax problem (T). where solving the inner maximization problem max Ax [(x + Ax) is required compute Us in the regularization term, and the outer problem is the regularized-loss minimization finding the optimal model parameter w for the classifier = fw. In this section, we provide two ways of solving the inner maximization problem. In particular, in Sec. B.c.I we give the explicit expression of the optimizer Ax when generalized linear model is considered. Sec. B.4.2 we solve the problem under more general setting via adversarial training.
B.4.1 CLOSED-FORM SOLUTION FOR GENERALIZED LINEAR MODEL
Consider a Generalized Linear Model (GLM) written as f(x) = g Tx), where g: [0, + R is strictly increasing link function, and the model parameter. Denote the weights corresponding to X1 as wy Then, the inner maximization problem can be written as:
max f(x + Ax) max 9 g (x + Ax)) |
max |xxillS
9 (w x + wi Axi)
( Ax = (Axı,0,0))
-- w x max wi ||
Axi
( g is strictly increasing)
S8
When ||-|| = ||- the maximum achieved by letting Ax₁ = ösign w1), w T "xx =
When |.||| = |1-1|2- the maximum can be achieved by letting Ax| = /wn | 1| w Ax|
||
w1
B.4.2 ADVERSARIAL TRAINING BASED APPROACH FOR GENERAL SETUP
Here we discuss how we solve the inner maximization problem under more general setting. Following popular adversarial training methods, we apply projected gradient descent (PGD) for multiple times to update Ax₁, i.e., set
Axi = P(Axi + /VAn,(X
Ax)),
(12)
where 7 > 0 is the step size, and P is the projection onto the constrained space || S 8. For instancee P is equivalent to the clipping process when we use foo norm. Denote the maximizer the inner maximization problem Ax" (Axi*, ,0, 0,0) 0). Then, from Danskin's 's theorem Danskin (1967) we have V. Axx]sx Sw (x Ax) V /w (x + Ax*). We can use this derivative update w in the outer loss minimization problem. The pseudocode of this adversarial training based method
is shown in Algorithm !
Algorithm 1 Pseudocode for achieving
Input Daaaaset D
Output: Model parameter for the classifier f. Initialize w;
for each iteration do
for each (x&, y,) E 'D do Initialize Ax;; for each PGD) iteration do Update Ax; according to 12
Update w according to the regularized loss function defined in
B.5 DERIVATION OF OPTIMAL EI CLASSIFIER FOR SYNTHETIC DATASET
This section shows how we obtain the optimal El classifier (that minimizes the cost function in II) for a synthetic dataset having two features x = [xg Xy] sampled from a Gaussian distribution N(pyy Ezy) where the mean fuyyy and the standard deviation Σg,y depends on the label y {0. 1} and the group attribute z E {0.1}. Note that the performance curve of the optimal Ei classifier obtained in this section is provided in the yellow line in Fig.
17

---

Published as a conference paper at ICLR 2023
The optimal EI classifier is obtained in the following steps: (i) define mathematical notations used
for analysis (Sec. (.5.II, (ii) compute the error probability (Sec. [B.52), (ii) compute El disparity (Sec. B.5.3) and (iv) solve the El-regularized optimization problem and find the optimal EI classifier
(Sec. B.5.4)
B.5.1 NOTATIONS
We consider finding z-aware linear classifier which predicts the label y from two features X1, X2 and one sensitive attribute z. In other words, given x and z, the output model is represented as fxx) = w1x1 + x22x + wyz + b where [W1, W2, wzl is the weight vector, b is the bias.
For group Z 0,
fi if wIx + u2X2 > -b
y =
to else
For group 1,
[1 if W1X1 + W2X2 10
0 else
Without the loss of generality, V w + wn = 1, parameterize them as w1 = sin 0, 02 cos Then, for group = 0,
[ if (sin 0)x1 (cos 0)x² bo
o clse
and for group 1,
1 if (sin 0)x: + (cos 0)x² > bi
o clse
where by -b and b ww3 b. Since the linear combination multivariate Gaussian is univariate Gaussian, have
wo (ww Mzy wg Σz.y Ws)
(13)
where we [sin 0, cos 0). The decision rules can be written in terms of the For group 0,
1 we x > bn
ÿ
0 else
For group z 1,
1 if wo x > b1
9 =
0 else
Now, the question is, what is the optimal parameters 0, by, by that solve the optimization problem in ( In order to answer this question, need to understand how the equal improvability condition is represented in terms of the model parameters. Suppose we use 0-1 loss function I, and use lac norm μ(x) |x| From the result in Sec. B.4 given the effort budget 5, the maximum score f(x Ax) f fx)) S||wy||| 5[ sin Ø + cos 0)) where wy is the weights for improvable features X1, X2. Thus, if we denote the max as the estimated label after the improvement, we have
improvement (max,,
1 (sin + (cos0)x2 > bo 8(1 sin 0| + cos 01) = big
max
to else
for group 7. = 0 and
[ if (sin + (cos8)xg b, 8[[sin + cos 81) b4
max
0 else
for group == 1.
'In this case, the decision boundary is fx f(x) 0} instead of (x fxx) 0.5) used in the main paper.
18

---

Published as a conference paper at ICLR 2023
B.5.2 COMPUTE ERROR PROBABILITY
The error probability can be written as,
Pr(j F)) Σ Pr(z- yy|z= -) k=0
We can derive the term Pr(ý # y|z 0) as below:
Pr(ý + y|z 0) Pr(y 0) 1yy = 0, 0) Pr(y = 1/2 - Pr(y = 0ly 1,2 = 0)
We can look each term Pr(ý 1 0, 0), Pr(y 0ly 1, 0) and write those terms in terms of Q-functions because.
Pr(ý- 1ly 0, = 0) = Pr(ws x > boly 0, 0) Pr(ý = 0ly = = = 0) = Pr(w x < buly = 1, 0)
From
13
we have
bo w 1000
Pr(ý = 11y = 0, 0) = Pr(wpx x boly = 0, Q
Veo w 20,0200
w 11.0 bo
Pr(ý 0ly 1, - 0) = Pr(w x < boly 1,2 0) =
(1ng E1,000
One can derive the error rates for group z
similarly. So, the total error rate can be written as
bo w 10.0
Pr(ý # = -Pr(z= = 0) Pr(y = =0z-0/==0 = 0]
Ven E0,0
Wg M1.0 bu
+ +Pr(y =0Q
/1n) Σ1,
bi ww 11.0
+Pr(z=1] 1)
Pr(y Pr(y= =0z== 1)Q
Vwo u0 Er,000
Th M1.1 b1 Σ1, wo
+Pr(y 1/2 1)Q
We have three parameters optimize the error rate 0, bu, dj All the other terms are known.
B.5.3 COMPUTE EI DISPARITY
To compute El disparity, we start with computing
Pr(y Prrymax 1. = 0/z 0)
Pr(ymax= 1ly 0, 0)
(14)
Pr(ý = 0|z = 0)
The denominator of [4) can be expanded as
Pr(ý 0|z 0) -rr(y = 0/z 0) Pr(ý 0ly 0.z=00
+ Pr(y 1|z 0) Pr(y = 0ly = 1, = 0).
We can look each term Pr(ý = 0ly 0,2 0), Pr(y 0ly =1,z 0) and write those terms in terms of Q-function because,
Pr(ý = 0ly 0, Pr(w, x < ooly 0. 0)
19

---

Published as a conference paper at ICLR 2023
Pr(y = 0ly 1, Pr(ws) x buly 1, 0)
From
13
we have
w 14000 bo
Pr(ý - 0ly 0, 0) Pr(w < boly 0,2 = Q
w Eo,020
wig 11.0 bo
Pr(ý = Gly = 1, = 0) = Pr(wp x boly = 1, = 0) = Q
Veo 1/b 1,00000
Then,
wy M0.0 bo
Pr(O - 0z = Pr((y 0/z - =)Q
w Eo,owa
Wg 11.00 60
+ Pr(y 1
100 E1,000
The numerator of [4 can be expanded as Pr(ymax 1, 0/z 0) Pr(y 0|z Pr 1, 0ly-0-0y---00
Pr(y = 1|z 0) Pr(y max
L.ý 0ly 1,z 0).
We can look each term Pr(y = y = 0ly = 0, 0), Pr(jmaxx max = 1,ý = 0ly = 1, = 0) and
write those terms terms of Q-function because.
Pr(jmax = 1, = 0ly = 0, 0) = Pr(bó < w < boly = 0,z=
Pr(fmax= = =
0l = 0) = Pr(16 < wg < =
From 13
we have
Pr(ymax 1, = 00y- 00y= 0,2 0) Pr(k/ < w. < boly 0, 0)
wi 10.0 - bp
WA 140.0 1/
Q
W. E0,0
2 E0,0
Pr(ymax 1, Oly = 1, 0) Pr(b/ < wi x < boly 1,2 0)
w 11,0 bo
Wa 11,0 16
w E1,0
Vwg 2 Σ1,0
Then,
w 10.0 - bo
wp 10,0 16
Pr(ymuxx = 1, -00== 0) = Pr(y = 0/z 0)
Q
Q
wi Eu,0
v wo Ev,0
wi 11.0 bo
w 11.0 16
Pr(y 1/2 0)
V w Σ
Vwn Σ1,0
It can be derived for group similarly. So, derived El disparity in terms of 0, bo, bi-
20

---

Published as a conference paper at ICLR 2023
B.5.4 SOLVE THE OPTIMIZATION PROBLEM
In the previous two sections, we derived the error rate and El disparity in terms of Q-functions containing parameters 0, bo, b1. Therefore, we can construct an El-constrained optimization problem (which is essentially same as (T::
min 0.
Pr(ý # y)
s.t.
max Pr((ymax= 1 = 0, Pr(y 1 = 0) < (0,1)
where è is hyperparameter can choose to balance error rate and El disparity.
After writing error rate and El disparity terms of Q-functions (using the derivations in Sec. [B..22 and Sec. B.5.3), we numerically solve the constrained optimization problems above with a popular python module scipy. opt iotimize. To get the experimental results in Fig. 3 we numerically solved the above problem for 20 different values, where the maximum is picked the EI disparity of the unconstrained optimization problem.
C SUPPLEMENTARY MATERIALS ON EXPERIMENTS
In this section, we provide the details of the experiment setup and additional experimental results.
C.I SYNTHETIC DATASET GENERATION
We define y, feature x follows the conditional distribution (x |y = y,z = 2) ~ N Ey.z) where the mean of each cluster is
Bern(0.4), (y z 0) Bern(0.3). and (y 2 1) Bern(O.5). The
N0.0 = 0.1, -0.),, N0.1 = [-0.2, 0.33], 11.0 = [0.1, 0.4], M1, = [0.4, 0.3]
and the covariance matrix of each cluster is
0.4
0.0
0.2 0.0
0.1
0.0
Σ,
Σ E0,1
Σ1,
0.0 0.4
0.0
0.2
0.0
0.1
C.2 HYPERPARAMETRA SELECTION
The selected hyperparameter for each experiment is provided in our anonymous Github. In all our experiments, we perform cross- validation to select the learning rate from (0.0001, 0.001, 0.01, 0.1)- In addition, for each penalty term we did two-step rrossvvaliationn to choose A. In the first step, we used a set E {0, 0.2, 0.4, 0.6, 0.8, 0.9). , In the second step, we generate a second set around the best X found in the first step, i.e., the second set is {max(>* ( + E, 0} E {-0.1, -0.05, O, 0.05, 0.1) For example, A f0.3, 0.35, 0.4, 0.45, 0.5}.
X* = 0.4 is the best at the first step, then at the second step we use the set
C.3 ADDITIONAL EXPERIMENTAL RESULTS ON ALGORITHM EVALUATION
Table 3 shows the performance of ERM baseline and our three approaches (covariance-based, KDE- based, loss-based) introduced in Sec. 3 for multi-layer perceptron (MLP) network having one hidden layer with four neurons. Similar to the result in Table 2 for the logistic regression model, our methods can reduce the EI disparity without losing the classification accuracy (i.e., increasing the enror rate) much.
Meanwhile, according to previous work (Cherepanova et al. 2021 large deep learning models are observed to overfit to fairness constraints during training and therefore produce unfair predictions on the test data. To confirm whether our method is also having such limitations, we investigate the performance of our algorithms on wer-paramettrizee models. Specifically, we conduct experiments on a five-layer ReLU network with 200 hidden neurons per layer, which is over war-paraaeterizedd for German dataset. Table 4 reports the performance of El-constrained classifiers such KDE-based, loss-based)
parameterized setting. One can confirm that our methods (covariance-basse perform well in both training and test dataset, and we do not observe the overfitting problem.
21

---

Published as a conference paper at ICLR 2023
Table 3: Comparison of error rate and El disparities of ERM baseline and proposed methods on the synthetic, German Statlog Credit and ACSIncome-CA datasets Multi-Layer Perceptron (MLP). For each dataset, we boldfaced the lowest El disparity value. Compared with ERM, all three methods proposed in this paper enjoys much lower El disparity without losing the accuracy much. All reported numbers are evaluated on the test set.
METHODS
DATASET
METRIC
ERM
COVARIANCE-
BASS-BASED
ERROR RATE(L)
.205 = .003
.242 1: .006
.227 .008
.229 .012
SYNTHETIC
EI ()SP.()
.141 = -036
.004 2 .002
.011 .00
.018 .009
GERMAN
ERROR RATE(L)
1221 = .010
.23
.238 .035
STAT.
EI DiSE(()
.059 = .0.1
.013 .025
.011 .025
.013
.019
ACSINCOME
RATE(L)
.181
.002
.182
.185
BI (isP.()
.042 1 .002
.010 1: .006
.010 1 .002 .006 + .003
CA
Table Error rate and EI disparities for ERM baseline and proposed methods, for an over- parameterized neural network on German Statlog Credit dataset. Performances train/test dataset are presented. Note that we don't observe the overfitting issue in the wverpparameterized setting.
METHODS
DATASET
METRIC
ERM
COVARIANCE-BASEL
KDE-BASED
LOSS-BASED
TRAIN (RR.(()
.117 + .004
.133 + .003
.125 + .008
.132 .011
GERMAN STAT.
TEST ERR.())
.117 + .010
.118 + .010
.11 + 010
.130 .009
TRAIN EI (IsP
.022 .017
.018 1011
.018 1009
.015 .013
TEST BI (1)P.()
.060 + 082
.049 + .024
.057 + 028
.017 = .225
In addition, in Table 5, we include ER and BE as baselines for the synthetic dataset experiment
We leverage the algorithm suggested by Gupta et al. (2019) for mitigating ER disparity. We extend the loss-hased approach to reduce BE disparity, by redefining the BE loss of group
provided in Table 2
T.BE A
Σ TET
e(1, max f(x; + Ax:)),
number of samples in group
|Axi
where
EE
Σ
{(1, max f(x: + Ax;)):
number of rejected samples in group 2 iEI_,= HA
and I_, is the set of rejected samples in group for E [Z].
Table
shows shoow that the minimum EI disparity is achieved by our methods. Hence, if the EI fairness needs to be achieved, then it cannot be replaced with the existing other faimesss notions for some datasets.
Table 5: Comparison of error rate and EI disparities of ERM, ER, and BE baseline and proposed methods on the synthetic dataset. We boldfaced the lowest EI disparity value. The three El-regularized approaches achieve the lowest El disparity while maintaining low error rates. All reported numbers are evaluated on the test set.
METHONS
DATASET
METRIC
ERM
GUPIA BX
ER
2019
BE (LOSS-HASHD)
COVARIANCE BASSED
KDE: BASED
LOSS-BASED
SYNTHETIC
EnRoO RATE(L) DiSP.())
.221 + .001
.036
235 + .009
.222 4 .006
.233 + 003
250 + .001
.002 - .001
.246 #: .001
C.4 EVALUATING ROBUSTNESS OF EI
In this section, we highlight the advantages of El over BE and ER in terms of robustness to outliers and imbalanced negative prediction rates. In doing so, we consider certain data distributions and follow the method discussed in Sec. B.5 for solving the classifiers.
22

---

Published as a conference paper at ICLR 2023
C.4.1 EI VERSUS ER: ROBUSTNESS TO OUTLIERS
As we discussed in Sec. B.3 ER is vulnerable outliers. In this experiment, we systematically study the robustness of El and ER to outliers.
Data distributions (Clean) Let sensitive attribute z Bern(0.5) and label y ~ (0.5( be independent of sensitive attribute z. Given the sensitive attribute and label y, feature follows the N (H My,s). where the mean and covariance of the
conditional distribution x y, 2 four Gaussian clusters are
M0,0 [1, (6,, M4.1 = 1-11-2) 11.0 = [2, 1.5), M1,1 [1, 2.5].
and
0.25
0.0
E0.0= = E1,0 Σn, = Σ1,
0.0
0.25
(Contaminated) We contaminate the distribution by introducing additional 5% outliers to group z = 0. The outliers follow Gaussian distribution with mean and covariance matrix
0.05
0.0
Moutierr
[-1,-220 -20], Eoutier, 0.0
0.05
Clean Data
Data with Outliers
10
0-
-5-
-5-
10
15
Gompp
Bourday Pherdary
20
20
Figure 6: Visualizations of the El and ER decision boundaries without and with the presence of outliers. We observe that the decision boundary of ER changes lot in the presence of outliers, while the decision boundary of EI is not affected. This phenomenon implies the robustness of to outliers.
Results The decision boundaries of El and ER for both the clean dataset and contaminated dataset are depicted in Fig. 6 These decision boundaries are the optimal linear decision boundaries based on the distributional information, we followed the same procedure as we mentioned in B.5 The ó for the El classifier is picked as 1.5. We observe that the introduction of outliers makes the ER decision boundary rotate a lot, leading to drop in classification accuracy and ER disparity w.r.t the clean data distribution. Moreover, we note that the newly added outliers fail to destroy classifier, which implies the robustness of EI to outliers. The Table also presents the accuracy, EI, and ER disparity of each classifier. These metrics are computed after excluding the outliers. It shows that the El and ER disparities have higher values under the dataset with the outliers for the ER classifier.
Table 6: Error rate and El and ER disparities of linear EI and ER classifiers.
METHODS
DATASET
METRIC
CLASSIFIER
ER CLASSIFER
ERROR RATE(()
.001 + .001
.001 + .001
DATASET
DisP.()
.001
ER DISP(()
.004 1 .001
.001 1 .001
ERROR RATE(J)
.001 + .001
.020 + .001
DAFASET WITH OUTLIERS
El (1)
.017 + .001
.318 = .001
DIse(()
.020
23

---

1.5. The huge Published as a conference paper at ICLR 2023
C.4.2 EI VERSUS BE: ROBUSTNESS TO IMBALANCED GROUP NEGATIVE RATE
In this experiment, we investigate the robustness of EI and BE to an imbalanced negative rate.
Same Negalive Rate
Differen Negative Rate
Goag 0
Graup
B1 Dockce Bezaday
Dwates Benedry
Figure 7: Visualizations of the El and BE decision boundaries given the data distribution with the same negative rates and different negative rates. The decision boundary of BE rotates lot when the negative rate of the dataset becomes different, implying the sensitivity of BE to imbalanced negative rates. In contrast, the consistency of EI decision boundaries showcases the robustness of El w.r..imbllanced negative rates.
Data Distributions (Same Negative Rate) We consider the distribution with balanced subgroups. In other words, let sensitive attribute (0.5. and label y ~ (0r5( be independent of sensitive attribute Given the sensitive attribute z and label feature, feature follows the Gaussian distribution (x = y, Z = 2) ~ N (u yy.z) where the mean each cluster is
Mo.0 1- -1,, Mo,1 [-1, 22,, 11.0 [1, 14,1 [2, 1]
and the covariance matrix of each cluster is
0.25
0.0
Eo,o = E1.0 Σo.1 = E1.
0.0
0.25
(Different Negative Rate) We manipulate the distribution of label for constructing data distribution
with different negative rates. To be more specific, we let y z = 0 ~ Bern(0.7). and z = 1 Born(..3).
Results Figure shows the decision boundaries of EI and BE when (i) the dataset has the same negative rate, and (ii) the dataset has different negative rate. These decision boundaries the optimal linear decision boundaries based on the distributional information, we followed the same procedure we mentioned in B.5 The 5 for the EI and BE classifiers is picked difference in BE decision boundaries under the two cases verifies our claim that BE cannot handle imbalanced negative prediction rates, In contrast, the decision boundaries of EI learned with two datasets with different group proportions are consistent.
C.5 DYNAMIC MODELING
Here we justify the dynamic model we used our experiments in Sec. 4.2, for updating individual's features and for updating the classifier. Specifically, Sec. C.5.1 explains the choice of c(x), the
amount of effort a sample (having feature x), while Sec. C.5.2 explains the choice of (7) (1) defining the classifier at round l..
C.5.1 UPDATING INDIVIDUAL'S FEATURES (CHOICE OF E(x))
At first, designed model by assuming that each individual makes effort, where the amount of the effort he/she makes (1) proportional to the reward (the improvement on the outcome) it will get by making such effort, and (2) inversely proportional the required amount of efforts to improve the
24

---

Published as a conference paper at ICLR 2023
outcome, shown in the below equation:
improvement on the outcome
Realized eftort (<x) A
required efforts for improving the outcome"
1 Ti
(T) x))
where 7/ is the accepting threshold for the individuals from group 2 at round t, and x is the feature.
This equation can be interpreted as follows: an individual that unqualified (æ 7, (+) is willing to make positive effort, but he/she is less motivated if the distance o. I' to the decision boundary is too large.
In order to upper bound the amount of reward, we added small constant , > 0 in the numerator, thus having the final form:
1fx < T (2) (Te (2) B)2
<(x:)
C.5.2 UPDATING THE CLASSIFIER
Note that at each round 6, each individual's features are updated. Accordingly, we also update the classifier (having parameters 7 and (!) in the same round. We update the EI classifier based on the following constrained optimization problem:
min (EI Disparity)
s.t. error rate S threshold,
which implies that we aim to find classifier that guarantees good accuracy and small disparity. This optimization can be rewritten
El Disparity
min Te
PP
X1 +
8:
(0)
z
0, < Tt (0)
P(x:
+
-( 1,x, < "
outcome improved
rejected
error rale
s.t. P().
Given the data distribution at each round 4, we numerically solve the constrained optimization problems using a popular python module scipy. optimize.
C.6 OBTAINING BASELINE CLASSIFIERS FOR DYNAMIC SCENARIOS
Continued from Sec. 4.2 this section describes how we compute the classifiers that satisfy demo- graphic parity (DP), bounded effort (BE) (Heidari et al., 2019) equal recourse (ER) (Gupta et al.. 2019) and individual-lews Similar to El classifier, we obtain the best DP classifier by considering the following constrained optimization problem:
fairness causal recourse (ILFCR) (Von Kügelgen et al. 2022) respectively.
min P(y, = 1 z= - = z= 1|
s.t. P(Y * Sy)sc Sc
The best BE classifier be obtained by solving the following problem:
min P(T(()) (0) 8, < 7 = 0) - ((T 8 <
z iz=1)
s.t. st., # yx) S
Similarly, the optimization problem for obtaining the best classifier written as:
min
P
X T (0) (0)
E
Tt
11)
1]
s.t. F y.) Sc.
While the computation of ILFCR classifier less straightforward, we first describe the setting considered in Von Kügelgen al. (2022) This paper assumes that each observed variable x; is
25

---

Published as a conference paper at ICLR 2023
determined by (i) its direct causes (causal parents) which include the sensitive attribute and other observed variables z,, and (ii) an unobserved variable u, Since our dynamics experiment considers only oie-dimensional variable it is determined by the sensitive attribute and latent variable Therefore, we write x as function of 2 and u, i.e., 202, u).
Before describe how compute ILFCR in experiments, introduce the definition of causal recourse and ILFCR in more detail. Given a model and a sample with feature I, the causal recourse C(x) of the sample is the minimum cost of changing the features, in order to alter the decision of the model. Let r(*) IR be the acceptance threshold of group E {0, 1} and μ ((Ax) |rr be the cost of improving the feature by Ar. Let x' denote the improved feature. In our one-dimensional dynamic setting, the causal recourse is defined
C(x(2, u)) min pl=' x(2, u)) = max(7(*) - u(z,u),07, x'2rte)
for 0, 1. ILFCR requires different groups have the same causal recourse for all realizations of the latent variable u:
max [C(x(0,, u)) C(x(1, ([([(,,,))) 4))l = O.
Now we describe how compute ILFCR disparity. Recall that for dynamic experiments, we assumed the feature x follows Gaussian distribution for each group 2 {0, 1), i.e.,
(N o2). This
can be represented as notation used in Von Kügelgen et al. (2022): the latent variable is u ~ No, 1)
and the feature is represented as x[=, u) = Ps u.u. u. We measure the ILFCR disparity a decision boundary pair (7o, T1) by
ILFCR Disparity(7 (()) max (x u)) C(x(1,u))
max max (7(0) - 20, max (7()) - -2(1, u))
(0)) - oou, 0) max (7(1) - pM -00200)
max
max
=(r(0) -po (aa- 01 01) + when aI
Note that the ILFCR disparity is infinity if we take the maximum over all u. Therefore, we instead ignore the tail distribution and focus on the samples with x [M= 30 Us= + 30=] for group 0, 1. In order to find classifier with small ILFCR disparity, we numerically solve the following constrained optimization problem
ILFCR Disparity (7))), s.t. eтror rate < a/2.
min 00)
Given the data distribution each round t, we numerically solve all the constrained optimization problems above using popular python module scipy inptimize
C.7 PERFORMANCE COMPARISON BETWEEN FAIRNESS NOTIONS UNDER OTHER DYMANIC MODELS
Here provide one example in which El improves long-term fairness, while some other methods (EO, BE, and ER) harm long-term fairness.
Long term CoRamess
0.75
ERM
In this example, from <(x)
modified the effort function
(T) ( - 1f < =(²)} to <(x)
BE
0.50
ER
log max(
(7) ( ー 1)
1fx (()) that the re-
El (Ours)
0.25
jected individuals make less improvement than the setting in the original manuscript. Here -!() is the acceptance threshold for group at iteration f, and 8 > 0 small constant to avoid zero denominators. We set 3 0.2 and the true acceptance rate a = 0.5. Figure g reports how long-term unfaireess changes when the intiial dis- tribution is x = 0 (0.00,3. 3.0²) for group and (1.00, 1.02) for group
10
Round
Figure 8: Long-tern term unfaimeess
drv (P! (()) at each round for var- ious algorithms in the setup described in Sec. C.7
26

---

f(x) = [112 2 rhh 11 2 m 1, Published as a conference paper at ICLR 2023
D EXAMPLES: INVESTIGATING THE ONE-STEP IMPACT OF FAIRNESS NOTIONS VIA MATHEMATICAL ANALYSIS
examples better understand how EI improves long-term fairness compared to existing fairness notions. We first introduce basic setup for the mathematical analysis and then apply it to two examples to compare El with BE, ERM, and ER in terms of their one-step impact on data distributions.
In this section, conduct mathematical analysis
D.1 BASIC SETUP AND PRELIMINARIES
D.1.1 CLASSIFTERS
We consider the z- aware classifier, having
== 0,
which is parameterized by the threshold pair (To, 71). We assume the effort budget is 5 where m is defined in the dataset.
Recall the zero equal improvability (EI) disparity condition is:
f(x An) 0.5 f(x) 0-5 P ((Ar)5)
f( 0.5 f()) < 05, ((Az)55
max
where u(Ar) = Ar This condition is equivalent to
- Po
To
1- 5 (rr)dr
(15)
1 Po(x)dr
5 pı (x)dx
We denote the improvability ratio of each group as
T0 m Po(
ro(To)
(16)
- Po(x)dr
S p1(x)dz
(1)
(17)
p Pr (x:)dx
The classifier that satisfies this zero EI disparity condition and minimizes the error rate is denoted as the optimal EI classifier. Recall that the bounded effort (BE) fairness constraint is:
max f(x + Ar) 2 0.5, fx) 0.5 ==0 =P (((a))s
max f(x (A))) 2 0.5, f(x) 0.5 0.5 2= p(A2)58
(18)
where p(Ax)= = |rl Meanwhile, the Equal Recourse (ER) constraint is defined as
min Ma+AAa)20.5
min u(Az) f(x) 0.5, [[(++22220.5
p(Ar) f(x) 0.5, 2
(19)
D.1.2 DYNAMIC SCENARIO
Suppose each rejected sample improves its feature by
8 1 E (To 8, ro)),
if = 0, if =
<(x)
5. 1 [T 7)),
Note that depending the classifier formulation for E(x) also changes. Here, we use E BRM (x) to denote the improvement of features given ERM classifier, and similarly define e ( BE (xr) and & (R))
using, the threshold pair (To. 71) changes, thus the
27

---

Published as a conference paper at ICLR 2023
Let Pa P (2) p2 + E ERRM (x)) for E (0,1), which represent the data distribution after the
features are improved based on ERM classifier. Similarly, we define Flll (x), p (z) and pz FR (x) for
EI/BE/ER classifiers, respectively. In the upcoming sections, measure the total-variation (TV) distance
dr (po. Pi) = 2 |mo(2)) - -P (x)
between two groups after a single step of feature improvement, and provide how this measurement differs for various classifiers.
D.2 EI VERSUS BE & ERM
D.2.1
FINDING THE OPTIMAL CLASSIFIER FOR EACH FAIRNESS CRITERION
Setup Let (=(x) be the data distribution each group 2 E {0. 13, shown Fig. the case of each sample having feature x, and the label is assigned as
We consider
1 fx 2 m/2), (xr 0},
if = =
Note that we have Ply 0|z 0) 3. Ply 1|= 0)
Ply 0/2 1) 2.4 and
Fyy 1/2 = 1) = 1.- We set P(2 0) | and P(2 1) 3
Po(x)
X
3nz
2
P((x)
X
m
Figure 9: The data distribution (2( for each group E f0, 1}. Samples with (+) sign have the true label y 1, while samples with (-) sign have the true label y 0.
ERM classifier
We have
ERR ERM (TO .1
m 2
=
since this threshold pair has zero classification error.
BE classifier We have
(TO
BE
BE
(20)
since this threshold pair has zero classification error and satisfy the BE condition in (18
El classifier The optimal El classifier for dataset in Fig. fig.9i is
(T El - = (0.
(21)
Proof. Note that (7 [)rrrr) = 1) having error rate less than TO
E1 -1) = (0. 0) has error rate Peerrro) = P(z () 0) + PP
3 0 = 1 +
Te. We prove that no other classifier satisting El condition in 15
1 Note that when [ > w. the error rate is larger than 3/ Thus is
sufficient consider cases when
m Combining this with the fact that
28

---

Published as a conference paper at ICLR 2023
(T()T) in 16 and 71 (T1) in (17
monotonically decreasing.
El condition in (15) satisfied when ro(Ta) = (1(1)) holds,
ro(T)) = 1i (71) holds for To =
m 2
that the optimal EI classifier satisfies To ग and |T| Σ The error rate for these classifiers is represented as PP(error) [P(z () 0) + P((z = 1))P(error'a = 1)
G
тo)
[r|| - Plugging in 7o 71 and optimizing the error probability over
2m
n m completes the proof.
D.2.2 TOTAL-VARIATION DISTANCE BETWEEN TWO GROUPS
For the dataset given in Fig. 9 the vatil-variation distance between two groups for each classifier is:
drv ERM -PRM = 0.5,
dr BE pp = 0.5, drv EI p 0.125.
Proof. Since ERM solution is identical to BE solution, proving the above equation for BE and EI is sufficient. Recall that the expression of BE/EI classifiers are 20 and (11 Using this expression, can derive the distribution of each group:
Im
if & E m
T m
i E
-mm 0)
Pu
BE
(x)
2mm
if (m,
if x E [0,
m
or x: 4 m.,
3m
2
if E [0, m
P1 (3)
BE
if [-m,
m
2m
0,
if E 1- or x 1-m, m, m
if [0, T
if I-m, -
Po
El (z)
2mm
4m
i if
E m 3m
22
0,
m 2
or
[-m,
3m
P1 (z)
pl
(E))
Vx
From this expression, we can derive the voraa-variation distance, which completes the proof.
D.3
EI VERSUS ER
D.3.1 FINDING THE OPTIMAL CLASSIFIER FOR EACH FAIRNESS CRITERION
Setup Let p2(x) be the data distribution of each group {0, }. show in Fig. 10 We consider case of each sample having one feature x, and the label is assigned as
1 2 0}, 1 2 0},
if =
y/
=
Note that have Pyy 0 0) P(y 0 1)
P(y =
0)
Ply 1 2
1) = 2.
set P(2 = 0) = (2 = 11
ER classifier
The optimal ER classifier for the dataset in Fig. 10
ERR ER (70
71
(-9m, 0).
(22)
29

---

Published as a conference paper at ICLR 2023
10n
P(G0
Figure 10: The data distribution p=(x;) for each group E {0, 1). Samples with (+) sign have the true label y = 1, while samples with (-) sign have the true label = O.
Proof. Note that the accepting thresholds 19mm, 0) has error rate P(error) = P(error = = 0)P(2 0) Perrrrr 1)P(2 1)
+ 0 2 We prove that no other classifier satisfying ER constraint 19 is having error rate less than :.
The necessary condition for the classifier have an error rate less than 1 is To. T1 E (- 2). Note that when To E (- m
6
) we have the recourse of the group 0:
2
min ((Ax) f(x) < 0.5, = Al)+-0)20.5
E [To
x x < To: 2 = 0]
To E [ To: 2 0
(23)
(P(T))
where
(T(T)) E [z]
< To =
0]
(24)
10m, 19 1
19
x E
To 2 = 0
x
x E
10m,
m
A
+
P
To
To:
0
E
m
To
2
2
2
1-X
for
all
To
E
[-
m
2: 2
m
where À
E 1].
Since E | x E
[010m
1m m] = == =0 <
x
[
m
2 = 0].
24 is decreasing function. Consequently.
2
19
m
2 0] To 2
<
E
r
E
-10m,
m
2 = 0
+
x
E
2
39
To
41
12 m.
12
6
3
Thus, the recourse of group is
2To
41
37
23
m
>
12 m
(25)
12
30

---

Published as a conference paper at ICLR 2023
Mcanwhile, when E (- 2 )) we have the recourse of the group 1:
min p(Ar)
f(z) 0.5, 2
faa+An)20 20.
E [ x
T1: 0]
TI - [ <<< TI: = 0]
11
2
+
m
(26)
2
Therefore, combining 25 and 26) implies that when To, 71 (- m
2 the ER constraint 19
cannot satisfied. Thus, the way for achieving error rate < is To
and 71 = 0. Note that
the recourse of group 0 which is written in (23) is strictly increasing function when To
Therefore, there exists a unique classifier that achieves both El while maintaining error rate 8 One
can easily verify that (-9m, 0) is the optimal ER classifier.
El classifier We have
; (0,0)
(27)
since this threshold pair has zero classification error and satisfies the El constraint 15
D.3.2 TOTAL-VARIATION DISTANCE BETWEEN TWO GROUPS
For the dataset given in Fig. T0 the total variation distance between two groups for El and ER classifier is
ERR) 2
ER drv (pb .P
El (p) = drv(po
3
Proof. By 27 and 22
i E
19m
8m
2
Po
ER
3m
if E
2
0,
O.W.
if 2
E
[-m,-
2
P1
FR
x E [0,
3m
0,
O.W.
if 2
E 1-10m
19m
Pb
ET (x)
3m
x E [0,
0g
O.W.
if
E [-m.
P1 FT
(z)
if
E [0,
3m
0,
O.W.
For this expression, we can derive the total-variation distance, which completes the proof.
31


Reviews:
[{"review_id": "vrFvbHQCTF", "reviewer": "Reviewer_q7oe", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper studies the delayed impact of fairness. The authors introduce a notion of fairness called \\emph{equal improvability}, which, subject to a bounded amount of improvement, equalizes the probability of acceptance for the rejected members across all populations. The authors aim to solve the typical loss minimization problem of classification subject to the equal improbability constraint. Since the constraint is non-convex, the paper proposes 3 different approaches to solve the constrained optimization. The paper concludes with empirical analysis both in the one-shot game as well as the repeated setting.", "summary_of_the_review": "Overall, I enjoyed reading the paper. I think it is a nice addition to the growing literature on the delayed impact of fairness. Though the technical contributions are not strong, it can be a welcome addition to the ICLR's program.\n\n------------------------\nPost rebuttal:\n------------------------\nI want to sincerely thank the authors for answering my questions thoroughly. I have also read the other reviews and author responses. I think we all feel that this work can go either way. I am still (slightly) in favor of acceptance though.", "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. The delayed impact notion of fairness is natural and sensible.\n\n------------------------------------------\nWeaknesses:\n------------------------------------------\n-- The main technical contribution of the paper is the definition. Hence, the technical novelty (when enforcing the equal improvability constraint) is limited. \n\n-- Section 4.2 contains the most interesting part of the paper, though some of the details are hard to follow/justify. It would be great to justify the choice of $\\epsilon(x)$ as well as describe in more detail how the updates to the classifier are done.\n\n------------------------------------------\nMinor Comments:\n------------------------------------------\n-- Theorem 2.5 and Corollary 2.6 show that equal improvability and bounded effort are mathematically different. It would be nice to \ndescribe this in more detail as it is not clear to me how to set the reward function in Heidari et al., 2019 to connect the two works.\n\n-- Are there deeper connections between equal recourse and equal improvability that are overlooked? If not, is not it surprising that these two methods work exactly the same in the experiments in section 4.2?\n\n-- Please stop using the Adult dataset: https://proceedings.neurips.cc/paper/2021/hash/32e54441e6382a7fbacbbbaf3c450059-Abstract.html\n\n-- The Y value in Figure 4 should be bounded by 1. Why is it above one in the left two sub-figures?\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": "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": "tcKpdwVHryo", "reviewer": "Reviewer_Eon1", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "The paper proposes a new notion of fairness called Equal Improvability (EI) that requires a binary classifier to be equally difficult to change predictions for each sensitive attribution group. To achieve this property, three different penalizations are discussed: covariance-based EI penalty, KDE-based EI penalty, and loss-based EI Penalty. The authors empirically showed that the three penalization methods achieve EI disparity. In addition, they claimed that EI promotes long-term fairness in dynamic scenarios using synthetic data.", "summary_of_the_review": "I think the main issue of the current submission is the lack of novelty and comprehensive experiments. I am happy to revise my reviews if there is anything trivial I miss something.\n\n", "strength_and_weaknesses": "- Strength\n  - The paper considers a timely important problem: training a fair machine learning model.\n\n- Weaknesses\n  - **Novelty:** It seems the novelty is weak. Specifically, the author proposed EI  \n$$\n\\mathbb{P}\\left( \\max_{  \\mu( \\Delta \\mathbf{x}_1 ) \\leq \\delta} f(\\mathbf{x} + \\Delta\\mathbf{x}) > 0.5 \\mid f(\\mathbf{x}) < 0.5, \\mathbf{z}=z \\right) = \\mathbb{P}\\left( \\max_{  \\mu( \\Delta \\mathbf{x}_1 ) \\leq \\delta} f(\\mathbf{x} + \\Delta\\mathbf{x}) > 0.5 \\mid f(\\mathbf{x}) < 0.5 \\right) \n$$\nwhich is equivalent to\n$$ \\mathbb{E} \\left[  \\mathbf{1} \\set{ \\max_{  \\mu( \\Delta \\mathbf{x}_1 ) \\leq \\delta} f(\\mathbf{x} + \\Delta\\mathbf{x}) > 0.5 }  \\mid f(\\mathbf{x}) < 0.5, \\mathbf{z}=z \\right] = \\mathbb{E} \\left[  \\mathbf{1} \\set{ \\max_{  \\mu( \\Delta \\mathbf{x}_1 ) \\leq \\delta} f(\\mathbf{x} + \\Delta\\mathbf{x}) > 0.5 }  \\mid f(\\mathbf{x}) < 0.5 \\right]. $$\nGiven that the same conditional distributions are considered in Equal Resource (ER) by Gupta et al. (2019), it seems the current idea might be a naive variant of the previous idea:\n$$\n\\mathbb{E} \\left[ \\min_{f(\\mathbf{x}^{\\prime})>0.5} \\mu( \\mathbf{x}^\\prime - \\mathbf{x})  \\mid f(\\mathbf{x}) < 0.5, \\mathbf{z}=z \\right] = \\mathbb{E} \\left[  \\min_{f(\\mathbf{x}^{\\prime})>0.5} \\mu( \\mathbf{x}^\\prime - \\mathbf{x})  \\mid f(\\mathbf{x}) < 0.5 \\right].\n$$\nAlso, using a fairness regularization function is not a new idea as the authors mentioned in section 3. To be fair, I believe the work can still have strengths even with these similarities. However, it is not clear why the proposed idea is powerful without comprehensive comparisons with ER. The authors explained the limitation of ER in section 2, but the behavior of EI on outliers is not explicitly examined. \n\n  - **Mismatch:** Mismatch between the motivation and the proposed method: the authors discussed the long-term fairness in Abstract and Introduction, but the proposed method is not directly solving the dynamics of distribution shifts. In section 4.1, the dynamic setting is considered, but it is not clear how the objective function in section 4.1.1 is related to the equation (1) in section 3.\n\n  - **Experiments:** Most of experiments consider fairly simple settings ($\\mathbf{x}_t \\in \\mathbb{R}$, $\\mathcal{Z}=\\{0,1\\}$, and $T$ is small) that are not realistic. The real problems should be higher dimensionality on $\\mathbf{x}$ and have more sensitive classes. Moreover, it is not clear why achieving EI helps to improve long-term fairness.\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": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "csUg9Z06hI", "reviewer": "Reviewer_dcYV", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This work proposes a notion of long-term impact called equal improvability (EI) that equalizes the \"effort required to improve\" of rejected individuals belonging to different sensitive groups. This metric is theoretically compared to three other long-term metrics: Bounded Effort and Equal Recourse---conditions for meeting each of these notions of fairness (in relation to each other) are derived. Three fairness-based regularization methods are proposed to find policies that mitigate unfairness wrt EI, each with a unique differentiable penalty term. These methods are empirically tested against synthetic and real-world data. In the first set of experiments, the three mitigation strategies are tested against a fairness-unaware algorithm over two real-world datasets (non-dynamic). In the second set of experiments, results for a simple dynamical setting are shown.  ", "summary_of_the_review": "I make a recommendation to accept. \n\n- The approach seems well-motivated, and the authors take care to show that their metric is distinct from other current methods in the longterm fairness space. \n- The paper also does not over-state its claims, e.g., the three optimization algorithms introduced offer no guarantees on the solutions found will actually mitigate EI unfairness. This limitation is well-known in regards to soft constraints but is still important to address in the main body (see weaknesses for an elaboration). \n- There are also a few clarifying points from the experiments I would like addressed, such as the choice of baselines for the non-dynamic experiments, as well as the statistics being presented in the experiments. \n\n--- post rebuttal --- \nI thank the authors for the detailed response! The authors agreed to address many of my concerns in their next iteration, which I think will make the work more straightforward. After discussion with other reviewers, I still lean towards acceptance. ", "strength_and_weaknesses": "Strengths / comments: \n- I enjoyed reading the introduction and the (first) related work section, where the authors pinpoint the importance of their metric and show how it is distinct from current known metrics in the field. \n- Concepts are elaborated on in the appendix or figures are provided to help readers better understand material. The example of $\\mu(\\Delta \\mathbf{x_1})$ in the para underneath Defn 2.1 was very helpful. \n- The authors did not over-state the results of their fairness-based regularization algorithms, e.g., acknowledged that these methods can mitigate EI unfairness and do not provide further guarantees on solutions found. \n- The organization of section 3 was straightforward and well-written. \n\nWeaknesses / comments: \n\n- Why don't the authors compare the other long-term fairness metrics to the long-term fairness-unaware metrics in the first set of experiments? ERM is a very simple baseline, and arguably the three datasets provided are three more datasets over which other long-term fairness baselines can be used as a comparison. We could consider this a single-step episode, which is a subset of an n-step episode. The paper that presents ER also presents a fairness-based regularization method to find solutions that mitigate ER. \n\n- How easy is it to find policies that mitigate unfairness when there are multiple groups, as is the case in many real-world applications? (For example, in applications where one might consider race, gender, or relevant proxies.)  One of the issues with just adding a (fairness-based) penalty to the objective is that the alg is only given incentive to satisfy fairness, but has the freedom to violate fairness if that results in a more improvement to the original objective. Qualitatively, it seems that scaling the importance of each of the additional pair-wise penalties wrt the primary objective would not be simple or insightful for users. \n\n- Adding on to the previous point, the Zafar paper that inspired the covariance-based EI penalty creates proxies to the original fairness constraint, but does not show (theoretically) that solutions found by the new proxy-objective solve the original objective. The covariance-based EI method also has no guarantees on the solution found by the algorithms (perhaps the KDE-based penalty as well though I am unfamiliar with the work which inspired it, and did not take the time to read through the work). Ultimately this is a weakness of using fairness-based regularization to mitigate unfairness. I suggest that the users address this as a weakness in the main body. \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": {}}, {"review_id": "-wUmaE-yhq", "reviewer": "Reviewer_Zw9H", "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 proposes a new notion of group-level fairness, i.e., Equal Improvability (EI). The intuition behind the notion is that, by considering those who are rejected but are not too far away from the decision border, the effort taken by those to recourse should not vary among groups. The paper provides three empirical ways to (approximately) enforce EI in classification tasks. Empirical results in the simulated dynamics are also provided.", "summary_of_the_review": "The paper proposes a new group-level fairness notion and three ways to empirically enforce it in classification. There are some worries about the claimed advantages of EI, as well as the formulation of the definition of EI itself (as detailed in \"Strength and Weakness\"). It would be greatly appreciated if authors can kindly provide additional clarifications.\n\n====== Post rebuttal =========\n\nThank authors for the response. I have updated my evaluation.", "strength_and_weaknesses": "## Strength\n\nThe proposed EI notion combines advantages of previous notions of a similar flavor (as summarized in Table 1), and makes an effort to avoid (some) problems of previous group-level fairness notions. Three different ways to (approximately) enforce EI are also provided. The authors demonstrate the benefit of considering EI in the dynamic setting in the experiments.\n\n## Weakness\n\n### 1. w.r.t. the distinction between zero-order vs. first-order fairness\n\nI am wondering what is the \"order\" over here. Roughly, I think the paper is pointing out the fact that EI (among others, e.g., Equal Recourse, Bounded Effort) cares about the ability to change the status quo. However, since it is a shared characteristics among some previous notions, I am not sure what specific benefit is unique to EI. Also, this distinction is only made in the beginning of the paper, and was not mentioned after Section 2. It would be very helpful if authors can share some insight over here, especially for the purpose of long-term fairness, as claimed in the paper.\n\n### 2. the unmentioned connection between individual-level recourse fairness and EI\n\nIf I understand it correctly, the central claim w.r.t. the advantage of EI compared to other notions is the potential to \"equally\" improve decision outcome for those who are currently rejected. This intuition is shared by, as pointed out in the paper, effort-based fairness notions. In my opinion, the intuition is actually more aligned with individual-level recourse fairness, e.g., von Kügelgen et al. (2022) \"On the Fairness of Causal Algorithmic Recourse\". EI claims to be more focused on those who are potentially able to recourse. However, the fact that EI remains a group-level fairness notion indicates that individual-level recourse fairness is more fine-grained and can better serve the intended purpose laid out by the authors. Additional discussion on the connection and difference would be very helpful.\n\n### 3. w.r.t Definition 2.1 EI\n\nI am wondering why we should limit our consideration to $\\Delta x$ such that $\\Delta_M x = 0$. According to the notion, by definition mutable features do not contribute to the cost of effort but can still alter the final prediction outcome. Then, I think it is more reasonable to encode such detail in the measurement of cost instead of forcing $\\Delta_M x = 0$, since this will implicitly limit the possibility to recourse for certain individuals and in turn affect the estimation of recourse probability.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: poster