Costs and Benefits of Fair Regression
Authors: Han Zhao
Venue: Accepted by TMLR ()

Abstract:     Real-world applications of machine learning tools in high-stakes domains are often regulated to be fair, in the sense that the predicted target should satisfy some quantitative notion of parity with respect to a protected attribute. However, the exact tradeoff between fairness and accuracy with a real-valued target is not entirely clear. In this paper, we characterize the inherent tradeoff between statistical parity and accuracy in the regression setting by providing a lower bound on the error of any attribute-blind fair regressor. Our lower bound is sharp, algorithm-independent, and admits a simple interpretation: when the moments of the target differ between groups, any fair algorithm has to make an error on at least one of the groups. We further extend this result to give a lower bound on the joint error of any (approximately) fair algorithm, using the Wasserstein distance to measure the quality of the approximation. With our novel lower bound, we also show that the price paid by a fair regressor that does not take the protected attribute as input is less than that of a fair regressor with explicit access to the protected attribute. On the upside, we establish the first connection between individual fairness, accuracy parity, and the Wasserstein distance by showing that if a regressor is individually fair, it also approximately verifies the accuracy parity, where the gap is again given by the Wasserstein distance between the two groups. Inspired by our theoretical results, we develop a practical algorithm for fair regression through the lens of representation learning, and conduct experiments on a real-world dataset to corroborate our findings.

Published in Transactions on Machine Learning Research (02/2023)
Costs and Benefits of Fair Regression
Han Zhao
hanzhao illinois, edu
Department of Computer Science
University of Illinois Urbana- Chanaaagnn
Reviewed on http::///gpaaerreaaaaa/////////a
Abstract
Real-world applications of machine learning tools in high-stakes domains are often regulated to be fair, the sense that the predicted target should satisfy some quantitative notion of parity with respect to a protected attribute. However, the exact tradeoff between fairness and accuracy with real-valued target is not entirely clear. In this paper, characterize the inherent tradeoff between statistical parity and accuracy in the regression setting by providing lower bound on the error of any attribute- blind fair regressor. Our lower bound is sharp, simple interpretation: when the moments of the target differ between groups, any fair algorithm has to make an error on at least one of the groups. We further extend this result to give a lower bound on the joint error any (approximately) fair algorithm, using the Wasserstein distance to measure the quality of the approximation. With our novel lower bound, we also show that the price paid by fair regressor that does not take the protected attribute as input is less than that of fair regressor with explicit access the protected attribute. On the upside, establish the first connection between individual fairness, accuracy parity, and the Wasserstein distance by showing that if a regressor is individually fair, it also approximately verifies the accuracy parity, where the gap is again given by the Wasserstein distance between the two groups Inspired by our theoretical results, we develop a practical algorithm for fair regression through the lens of representation learning, and conduct experiments on yeal-worlh dataset corroborate our findings.
and admits a
1 Introduction
High-stakes domains, c.g., loan approvals, and credit scoring, have been using machine learning tools to help make decisions. A central question in these applications is whether the algorithm makes fair decisions, in the sense that certain sensitive data does not influence the outcomes or accuracy of the learning algorithms. For example, as regulated by the General Data Protection Regulation (GDPR, Article 22 Paragraph 4) (gdp). "decisions which produce legal importe, effects concerning him or her or of similar importance shall not be based on certain personal data", including race, religious belief, etc. As result, using sensitive data directly in algorithms is often prohibited. However, due to the redundant encoding, redlining, and other problems, this "fairness through blindness" is often not sufficient ensure algorithmic fairness in automated decision-making processes.
Many works have produced methods aiming at reducing unfairness (Calmon et al. 2017 Chi et al. 2021 Hardt et al. 2016 Agarwal et al., 20199] Feldman et al.) 2015 Beutel et al. 2017 Lum & Johndrow 2016) under various contexts. However, the question of the price that we need to pay for enforcing various fairness definitions in terms of the accuracy of these tools is less explored. In this paper, we attempt to answer this question by characterizing tradeoff between statistical parity and accuracy in the regression setting, where the regressor is prohibited to the sensitive attribute directly, dubbed in the literature, statistical parity asks the predictor to be statistically independent of predefined protected attribute, e.g., race, gender, etc. While empirically it has long been observed that there is an underlying tension between accuracy and statistical parity (Calders et al. 2013 Zliobaite, 20155] Berk et al. 2017] Agarwal et al. 2019) in both classification and regression settings, theoretical understanding of this tradeoff regression is limited. In the case of classification,
attribute-blind regressor (predictor). Among many definitions of fairness (Verma & Rubin 2018)
Menon Williamson (2018) explored such tradeoff in terms of the fairness frontier function under the context of cost-sensitive binary classification. Zhhao & Gordon 2019) provided a characterization of such etradeoff in binary

---

Published in Transactions on Machine Learning Research (02/2023)
classification. Recently, Chzhen et al. (2020a) and Le Gouic et al. (2020) concurrently with each other derived analytic bound to characterize the price of statistical parity in regression using Wasserstein barycentres when the learner can take the sensitive attribute explicidly as an input.
In this paper, we derive the first lower bound to characterize the inherent tradeoff between faimess and accuracy in the regression setting under general Ep loss when the regressor is prohibited to use the sensitive attribute directly during the inference stage. Our main theorem can be informally summarized as follows:
For any fair algorithm satisfying statistical parity, it has to incur a large error on at least one of the demographic subgroups when the moments of the target variable differ across groups. Furthermore, if the population of the two demographic subgroups is imbalanced, the minorities could still suffer from the reduction in accuracy even if the global accuracy does not seem to reduce.
We emphasize that the above result holds in the noiseless setting well, where there exist (unfair) algorithms that are perfect on both demographic subgroups. Hence it highlights the inherent tradeoff due to the coupling between statistical parity and accuracy in general, not due to the noninformativeness of the input. We also extend this result to the general noisy setting when only approximate fairness is required. Our bounds are digorithm-independee distributional assumptions. To illustrate the tightness of the lower bound, we also construct a problem instance where the lower bound is attained. In particular, is easy to see that in an extreme case where the group membership coincides with the target task, a call for exact statistical parity will inevitably remove the perfect predictor. At the core of our proof technique is the use of the Wasserstein metric and its contraction property under certain Lipschitz assumptions on the regression predictors.
and do not make any
On the positive side, we establish the first connection between individual faimess ( (Dwork et al. 2012) more fine- grained notion of fairness, and accuracy parity (Buolamwini & Gebru 2018 (Bagassayynn et al. 2019 Chi et al.] 202I). Roughly speaking, an algorithm is said to be individually fair if it treats similar individuals similarly. We show that if a regressor individually fair, then it also approximately verifies the accuracy parity. Interestingly, the gap in this approximation exactly given by the Wasserstein distance between the distributions across groups. Our proof techniques are very simple but general, and we expect them to have broader applications in other learning scenarios with real targets, e.g., domain adaptation for regression problems (Ganin et al. [2016] Courty et al. 2017: Zhao al.
2019b) and counter-factur inference (Johansson et al. 2016 Shalit et al. 2017 Johansson et al. 2020).
Although our main focus is to understand the costs and benefits of fair regression, our analysis also naturally suggests a practical algorithm to achieve statistical parity and accuracy parity simultaneously in regression by learning fair representations. The idea is relatively simple and intuitive: suffices if we can ensure that the representations upon which the regressor applies are approximately fair (measured by Wasserstein distance). Finally, we also conduct experiments real-world dataset to corroborate our theoretical findings. Our results highlight the role of the Wasserstein distance in both the theoretical analysis and algorithm design of fair regression, which complements the existing results for fair classification using TV-distance (Zhao & Gordon 2022).
2 Preliminaries
Notation We consider a general regression setting where there is a joint distribution j over the triplet T = (X, A, Y), where X E X C Rd is the input vector, E 10 is the protected attribute, e.g., race, gender, etc., and Y E Hence, the joint distribution μ defined over the product space X x (0,1) x y. Lower case letters x, and y are used to denote the instantiation of X. A and Y. respectively. Let H be hypothesis class of predictors from input to output space. Throughout the paper, we focus on the setting where the regressor cannot directly use the sensitive attribute A to form its prediction. However, note that even if the regressor does not explicitly take the protected attribute A as input, this fairness through blindness mechanism can still be biased due to the redundant encoding issue (Barocas et al. 2017). To keep the notation uncluttered, for a E {0, 1}. we use 2l to mean the conditional distribution of ju given A = a. The zero-one entropy of A (Grünwald et al. 2004 Section 3,5.3) is denoted as Ho-1 (A) 1 (0,1) Pr(A- = a). Furthermore, we use Fy to represent the cumulative distribution function of a distribution v over IR, i.e., for 1 E R, (t): == ((-((_ f)). In this paper, we assume that the density of μi; and
Y [-1,1] is the target output]] [
'Our main results could he extended the case where A can take finitely many values.
2

---

Published in Transactions on Machine Learning Research (02/2023)
its corresponding pushforward under proper transformation (w..t. the Lebesgue measure A) is universally bounded above, i.e., ||dlo//A||lo S C, Vi E {0.1}. Given a feature transformation function g X - 2 that maps instances from the imput space X' to feature space 2, we define 8:M4 := } mo---1 to be the induced distribution (pushforward) of μ under 8, i.e., for any measurable event E' C 2, Prgzu( (F') == (r
Pry X 8x() E E')). We also use Y2 to denote the marginal distribution of Y from the joint distribution j. i.c., projection of μu onto the Y coordinate. Throughout the paper, we make the following assumption:
Assumption 2.1. There exists constant C such that the density of every p' (w.rt. the Lebesgue measure A) is universally bounded above, i.e., ||dy' oo S C.
Fairness Definition We mainly focus on group fairness where the group membership is given by the protected attribute A. In particular, statistical parity asks that the predictor should be statistically independent of the protected attribute. In binary classification, this requirement corresponds to the notion of equality of outcome (Holzer & Neumark 2006), and says that the outcome rate should be equal across groups.
Definition 2.1 (Statistical Parity). Given a joint distribution μt, a classifier Y = h()), satisfies statistical parity if Y is independent of A.
Since Y is continuous, the above definition implies that pr ( E E) = Pry, (Y E E) for any measurable event E C IR. Statistical parity has been adopted as a definition of fairness series of work (Calders et al., 2009 Edwards & Storkey 2015 Johndrow et 2019 Kamiran & Calders 2009 Kamishima et al.) [001 Louizos et al. 2015 Zemel
et al. 2013 Madras al. 2018), both under the classification and regression settings.
Fair Regression Given a joint distribution Jr, the weighted lp error of predictor γ h(X) under μ for p 2 1 is defined
Epp (Y) (Pr(A=a) Ep,na (2) = -EP((A=a) (En, [|8- xPP) 1/p
(1)
Note that the definition above on weighted lp error is not the as the Ep error over the joint distribution μ. Instead, it is the weighted sum of Ep errors each sub-group, where the weighted combination is given by the ratio of the sub-grouph in the overall population. In fact, these two losses can be related by the following observation. Let Pu = pr (A = a), we have
Epa Eyg [18-XXp] 1/v
|| Yllep(n) := Ep [18- [ -YPP)) -ECo
2 Epa (By [18- xp1) 1/p = =pp
where the inequality is due to Jensen's 's inequality since g(t) = //P for p 2 1 is concave over 2 0. The above inequality means that the l, error over the joint distribution j is an upper bound of our weighted Ep error over subgroups, which is the main focus of this paper. Conceptually, as we shall shortly see in Section 3.1 since we are more interested in understanding the tradeoff between the so-called balanced error rate and statistical parity, where each sub-group has the same weight towards the whole population, it is natural to treat each sub-group as separate distribution and define the corresponding error over it separately.
As two notable special cases, when 2. the above definition reduces to the weighted sum of the square root of the usual mean- wean-squared-error (MSE) over each sub-group; when p 1. ( becomes the weighted sum of the mean-absolutee-rrro (MAE) of the predictor overall each sub-group. To make the notation more compact, we may drop the subscript jl when it is clear from the context. The main departure from prior works on classification that both Y and (k))) are allowed to be real-valued rather than just categorical. Under statistical parity, the problem of fair regression can be understood as the following constrained optimization problem:
minimize lE7
Ep. (
(2)
subject to
Pr(I((X) 1) - Pr(l((X) S $1 V. Pd
P1
3

---

Published in Transactions on Machine Learning Research (02/2023)
Note that since Y = h()) E IR is real-valued random variable and A is binary, the constraint in the above optimization formulation asks that the conditional cumulative distributions of Y are approximately equal across groups, which is an
additive approximation to the original definition of statistical parity. Formally, the constraint in 2 is known as the Dolmogonv--mmrnoo distance:
Definition 2.2 (Kolmogorov-Snirrov distance). For two probability distributions je and p' over IR, the Kolmogorov- Smirnov distance K (1,,, H²) is K(N, n²) == supZer [z) (z)].
With the Kolmogorov-Sminn Smirroovv distance, we can define the e-statistical parity for a regressor h::
Definition 2.3 (e-Statistical Parity). Given a joint distribution y and S e S 1, a regressor Y = h(X), satisfies e-statistical parity if (hhgHo hg4h) c.
Clearly, the slack variable controls the quality of approximation and when 0 it reduces to asking exact statistical parity defined in Definition 2.1
Wasserstein Distance Given two random variables T and T with the corresponding distributions rr and p', let [ju, n²) denote the set of all couplings y of and p', i.e., Yr = j and "r = p². The Wasserstein distance between the pair of distributions 4 and y' is defined as follows:
(p(up() = ( inf
/ /IT T'PP dr dy)) 1/8
(3)
(TE(()A))
where 2 1 and throughout this paper we fix ||-I| to be the l2 norm. For the special case where both μt and μí' are distributions over IR, the Wasserstein distance Wp (14, n() admits the following equivalent characterization (Kolouri
et al. 2017):
(p( (5
L/P
(4)
where Fy (f) denotes the generalized inverse of the cumulative distribution function, i.e., F,, (t) = infze F(z) > f). The above closed-form formulation will be particularly useful in our later analysis. When p 1, the Wasserstein distance is also called the Earth Mover distance, and it admits dual representation in variational form using sup rather than inf: W1 (H,, μ²) = sup usl |f' du - J' f dp'), where ll := supx If(x) ( fx') x is the Lipschitz seminorm of f. It is well-known that convergences of measures under the Wasserstein distance imply weak convergence, i.e., convergence in distribution (Gibbs & Su 2002). Furthermore, compared with other distance metrics including total variation (TV), Shasenn-hhanon distance, etc. that ignore the geometric structure of the underlying space, Wasserstein distance often allows for more robust applications, e.g., the Wasserstein GAN (Arjovsky et al.) 2017), domain adaptation (Courty et al., 2017). etc., due to its Lipschitz continuous constraint in the dual representation. Moreover, unlike the KL divergence, the Wasserstein distance between two measures is generally finite even when neither measure is absolutely continuous with respect to the other, a situation that often arises when considering empirical distributions arising in practice. Furthermore, unlike the TV-distance, the Wasserstein distance inherently depends on the geometry of the underlying space, whereas the TV distance is invariant under any bijective mapping.
3 Main Results
Recently, Agarwal
Recently,Agarwallco et al. 2019) proposed reduction based approach to tackle 22) by solving a sequence of cost- cest-sensitive problems. By varying the slack variable e, the authors also empirically verified the unavoidable tradeoff between statistical parity and accuracy in practice. However, to the best of our knowledge, quantitative characterization of the exact tradeoff between fairness and accuracy is still missing, In this section, we seek to answer the following intriguing and important question:
In the setting of regression, what is the minimum error that any attribute fair algorithm has to incur, and how does this error depend on the coupling between the target and the protected attrübute?
In what follows we shall first provide a simple example to illustrate this tradeoff. This example will give readers flavor of the kind of impossibility result we interested in proving. We then proceed formally present our first theorem
4

---

Published in Transactions on Machine Learning Research (02/2023)
which exactly answers the above question, even if only approximate fairness is satisfied. We conclude this section with some discussions on the implications of our results.
A Simple Example As a warm-up, let us consider an example to showcase the potential tradeoff between statistical parity and accuracy. But before our construction, it should be noted that the error Ep, (Y) bears an intrinsic lower bound for any deterministic predictor Y = ht( (X), i.e., the noise in the underlying data distribution J. Hence to simplify our discussions, in this example, we shall construct distributions such that there no noise in the data, i.c., for {0, 1].
there exists snound-truth labeling function h such that Y = kg (X) on Ila- Realize that such simplification will only make it harder for us to prove the lower bound on EpNe since there exist predictors that are perfect.
Example 3.1 (Target coincides with the protected attribute). For a E {0,1). let the marginal distribution XyH4 be uniform distribution over {0,1}. Let Y = a be constant. Hence by construction, the joint distribution, we have Y A hold. Now for any fair predictor y h hxX), the statistical parity asks Y to be independent of A. However, no matter what value h (x) takes, we always have [11xx) + [x(x) 1 2 1. Hence for any predictor ht X - IR:
1 Ik(0) - 01 + 11,1o (h) + 1,11 (h) -0011111000
1 (1(1) 01 +
1 (h(1) - 1 Ih(0) 1| +
1 1
+ =1 1. 2
This shows that for any fair predictor h, the sum of L errors of h on both groups has to be at least 1. On the other hand, there exists trivial unfair algorithm that makes no error both groups by also taking the protected attribute into consideration: Vx E (0,1),"*xx 0f A 0 clse h² (x) 1.
3.1 The Cost of Statistical Parity under Noiseless Setting
The example in the previous section corresponds to a worst case where Y = A. On the other hand, it is also clear that when the target variable Y is indeed independent of the protected attribute A, there will be no tension between statistical parity and accuracy. The following theorem exactly characterizes the tradcoff between fairness and accuracy by taking advantage of the relationship between Y and A:
Theorem 3.1. Let Y h(() be predictor. If γ satisfies statistical parity, then Vpp 2 1,
Ep,jo ( + Eppi ( Z Wy YyM1).
(5)
We provide a proof by picture illustrate the high-level idea of the proof in Fig. 1 For the special case of p and p = 2, Theorem 3.I gives the following lower bounds on the sum of MAE and MSE on both groups respectively:
Corollary 3.1. If y satisfies statistical parity, then 1 (8) + E1,1 (8) 2
E - E,, [X] and 222 (Y) +
2 E M - [M12.
2,m
First of all, the lower bound Wp (Y=Mo, Y;H1) corresponds to a measure of the distance between the marginal distributions of Y conditioned on = 0 and A 1 respectively. Hence when A is independent of Y, we will have Y,HD = = that the lower bound gracefully reduces 0, i.e., no essential tradeoff between fairness and accuracy. On the other extreme, consider Y = cA, where > O. In this case, A fully describes Y and it is easy to verify that (Y:Ho, Y;/11)= C, which means the lower bound also takes into account the magnitude of the target variable Y. For protected attribute A that takes more than 2 values, we could extend Theorem 1.1l)rem3.10p by considering all possible pairwise lower bounds and averages over them. Furthermore, the lower bound is sharp. in the sense that for every p 2 1, there exist problem instances that achieve the above lower bound, e.g., Example 3.1 To see this, consider the Ep error for any predictor ht we have
Remark
{ (h0) 0l" +
1
1/P
+ (n() 11p + + -1(2) 1/F
1
Ep.ta (h) + Ep, (11
2 (1)) 0/P)
2
1
1
1
1
2 (00) 01 +
(11 01 + [h(0) 11 + 2
hh(1)
2
1 + - =1
Wy Y:H1),
2 2
5

---

Published in Transactions on Machine Learning Research (02/2023)
where the first inequality follows from Jensen's inequality and the fact that g(t) f//r for p N 1 is concave over 2 O. On the other hand, it can be readily verified that the fair predictor h h(X) = 1/2 attains the lower bound. As another example, consider the following Gaussian case for p = 2:
Example 3.2 (Gaussian case). For E {0, 1/. let the marginal distribution XzM4a be standard Gaussian distribution (O, La) and assume A 1 X. Fix w E Rd with || = 1, and construct Yo- = w and Y = w X + Now for any regressor Y = (x), due to the data-processing inequality, Y I A so Y is fair. However, consider the & error of h on both groups:
#2, (h) 22,11 (h) - - + (2)) 14)
- 5x (xx) - Yoll + [x) -Y1] Ex Yill =
where the first inequality is due to Jensen's 's inequality. On the other hand, note that the distributions of Yo and Y1 are (-11,1) and N (1,1), respectively. The analytic formula (Givens et al. 1984 Proposition 7) for the W2 distance between two Gaussians N (mo, Σo) and N (m,, is
(o)) Eo), (m,,, ||mo- m1 m1112+ Ir Io +2 -2 2 /2 1/2)
which shows that (Y,,,, Y1) -1-1-111 2. Further, consider 8 = --1 (X) = w" X, then
22,00 (1i*) 82,11 (h** = E (x)* 1 +3 - Y1) = 11+1= 2. =2
Hence h* achieves the lower bound and the lower bound is verified.
It worth pointing out that the lower bound in Theorem 3.1 is Aggorithm-independdee and it holds on the population distribution. That being said, by using recent tail bounds (Lei et al. 2020)) Weed al. (019)) on the expected Wasserstein distance between the empirical distributions and its population counterpart, it is not hard to extend Theorem 3.1 to obtain finite sample high probability bound of Theorem 3.1
Theorem 3.2. Let γ h (x) be the predictor and A be an empirical distribution induced from sample of size n drawn from y. If γ satisfies statistical parity, then there exists an absolute constant C > such that for 1, with probability at least
over the draw of the sample,
22 ( + =2m ( 2 10 ( + 11 ( 2 Wi Y:R1) (2c) + v 2 2log(218)
/ /
(6)
Remark It is possible to obtain better lower bounds for the l error in Theorem 3.2 but that requires making more assumptions on the underlying distribution Jt, e.g., strongly log- log-concave density. The first term in the lower bound, (Y Y2 could be efficiently computed from the data by solving a linear program (Cuturi & Doucet 2014 Problem (3)). Furthermore, it is worth pointing out that the lower bound in Theorem 3.2 applies to all the predictors Y and is insensitive the marginal distribution of A. As comparison, let Pa := (r, a). then Ep (Y) p. (Y) + p1m (9). In this case, if the group ratio is imbalanced, the overall error Ep (Y) could still be small even if the minority group suffers a large error. Using Theorem 3.1. we can also bound the joint error over all the population:
Corollary 3.2. Let Ý = h(X) be predictor. If y satisfies statistical parity, then Vp 2 1, the joint error has the following lower bound:
Ep, ( ( (A) Wy Y5H1).
(7)
Compared with the one in Theorem 3.1 the lower bound of the joint error in Corollary 3.2 additionally depends on the zero-one entropy of A. In particular, if the marginal distribution of A is skewed, then Ho-1 (A) will be small, which means that fairness will not reduce the joint accuracy too much. In this case, even if Wp (YsHo, YgHt) is large, it might seem like that the joint error (P) need not be large. However, this is due to the fact that the price terms of the drop in accuracy is paid by the minority group. Our observation here suggests that the joint error Ep,.() is not necessarily

---

Published in Transactions on Machine Learning Research (02/2023)
Distributions over X'
Distributions over y
Y111
(hi)
hfair
14
YEuO
Ea(ho)
Figure 1: Proof by picture. Under the constraint of statistical parity, the predictor hair (-) Po and ji induces the same predictive distributions over V. Applying a triangle inequality (with Wp(+-)) )) to the triangle in the right circle and using the fact that the Wasserstein distance is a lower bound of the regression error completes the proof.
the objective to look at in high-stakes applications, since it naturally encodes the imbalance between different subgroups into account. Instead, a more appealing alternative to consider is the balanced error rate:
Balanced Error Rate y := 2 (Epooo (2) + Ep,p1 (9).
(8)
which applies balanced weights to both groups in the objective function. Clearly, ( could be reduced to the so-called cost-sensitive loss, where data from group a E {0, 1] multiplied by a positive weight that is reciprocal to the group's population level, i.e., 1/ Pr(A a).
Comparisons with Related Lower Bounds is instructive to compare the above lower bound for the population error with the one of (Chzhen et al. 2020a Theorem 2.3), where the authors a Wasserstein barycenter characterization to give lower bound on the special case of squared f2 error (p 2) when the regressor can explicitly take the protected attribute as its input. As a comparison, our results apply to the general ép loss. To provide a more formal and detailed comparison, we first state the theorem for the mean- equan-s error the setting where the regressor has explicit access to the protected attribute from Chzhen et al. (2020a) (using adapted notation for consistency):
Theorem 3.3 (Chzhen al. 2020a) Theorem 2.3). Assume, for each a E (0,1}, that the univariate measure Y:H4, has density and let pa Pr( A a). Then,
min g satisfies statistical parity
- - = min Σ Pa (2 v), aE(0,13
where f*(X, is the Bayes optimal regressor and is a distribution over IR
Remark First, the quantity of interest Theorem 3.3 is the discrepancy between fair predictor g(>.) and the Bayes optimal predictor ())... On the other hand, the cost we are interested in this work is the excess risk (c.f. Definition 3.1) of a fair predictor. These two terms not the same in general. However, in the noiseless setting, know that Y f* (X, A) and the excess risk reduces the emror 2 In this case, the costs of faimess in Theorem 3.1
and Theorem 3.3 has the following relationship:
E E((Y
())
Σ
Pa 25 (Y)
ac (011
Σ
Pa 2 (8)
Σ Pa
(E(0.1)
(E(0.1) 2
Σ
VPa Vo
=
(E
7

---

Published in Transactions on Machine Learning Research (02/2023)
Furthermore, although in both Theorem 3.1 and Theorem 3.3 require the predictor be fair in the sense of statistical parity, the class of feasible predictors in Theorem 3.3 is still larger than that of Theorem 3.1 To see this, note that in Theorem 3.1 beyond asking for /t(-) to be fair, the same attribute-blind predictor h has to be used in both groups. On the other hand, although the attribute-awe aware predictor g(.,-) is constrained to be fair, different predictors g(, , a) could be applied over different groups indexed by A a. Last but not least, the noiseless case with p = 2, one can use Theorem 3.3 to obtain Theorem 3.1 as follows. Let W W2 Y/H1).
Σ Pa 2,, (Y)
min satisfies statistical parity
E [(((X) - 1)
ae (0,1)
min 8 satisfies statistical parity
E[(g(X, - Y)2]
(g(+.) has additional access to A)
min satisties statistical parity
EXU((X,AA) - -(X, A))
(Noiseless setting, so Y = (x(
min
Σ Pa (Y 2E(0,1}
(Theorem 333
min Pot + Pı (W -)2 f)2 IE [.W]
(W
(Barycenter property of W2)
= PoP1 W
Now, since the above incquality holds for every Po- P1 such that pa + p1 1, we can choose po and p1 as follows.
2,00
2,1 (
Po
P1
2, (Y) + 2,11 (Y)
(Y) + 2,14 (Y) 2,,0
Under this choice, from 2 (9) + 2,1 (Y) 2 PoP1 W we immediately obtain 6, (9) + 22,41 (Y) W
(2 Y211) as desired. Note that the above relationship between Theorem 3.1 and Theorem 3.3 only holds for
p = 2 under the noiseless assumption. is not clear such relationships continue to hold under the noisy setting and
general p 2
Another related result in the literature is Theorem 3.1 of of et al. (2021), which we restate as follows:
Theorem 3.4 (Chi al. 2021) Theorem 3.1). Let V h(X) be predictor, then
20 (8) + 2
2 2 ([Wi(YgRo. - W1 (1yH0,
where [+]+ max (.
Remark When ht-) satisfies the statistical parity exactly, the above lower bound reduces to Wi (Y Ygu1) Again, Theorem 3.4 is not directly comparable to Theorem 3.1 due to the same reason that Theorem 3.1 and Theorem 3.3 are not directly comparable. However, we can compare Theorem 3.4 and Theorem 3.3 directly since both costs are measured by the mean-squared error. To do so, realize that for the special case of W2 with || ||2 as the underlying metric, we know that the Wasserstein barycenter lies on the Wasserstein geodesic between Y;#o and Y//41 (Villani 2009). Let y* = arg min Lag(o,1) Pa (2 v). i.e., v* is the Wasserstein barycenter. Now since W2(-.) is metric and y² lies on the geodesic, we know
W2 W2(Y v*) + (YGG(1))"*) = W2(Y, YgH1)-
By using this fact, it is straightforward to verify that the following chain of inequalities holds:
1 = -1 WY (Y))) 2 W7( Y/H1),
(2 v* (2 2 2 (W2(YgHo,v") + W2(Yg)1,
where the first inequality is due to the AM-GM inequality and the last one due to the monotonicity of the (>.)) metric. Hence, the special case of p with mean -quared error, the lower bound in Theorem 3.3 is tighter than the
one in Theorem 3.4
8

---

Published in Transactions on Machine Learning Research (02/2023)
3.2 Extension to Approximate Fairness under Noisy Setting
In the previous section, we show that there is an inherent tradeoff between statistical parity and accuracy when predictor exactly satisfies statistical parity, and in particular this holds even if there is perfect (unfair) regressor in both groups, i.e., there is no noise in the underlying population distribution. However, as formulated in (2). in practice, we often only ask for approximate fairness where the quality of the approximation is controlled by the slack variable e. Furthermore, even without the fairness constraint, in most interesting problems we often cannot hope to find perfect predictors for the regression problem of interest. Hence, it natural ask what is the tradeoff between fairness and accuracy when our predictor only approximately satisfies fairness (e-SP, Definition 2.3 over general distribution μu?
In this section, we shall answer this question by generalizing our previous results to prove lower bounds on both the sum of conditional and the joint target errors that also take the quality of such approximation into account. Due to potential noise in the underlying distribution, we first define the excess risk pp, (P) of a predictor Y, which corresponds to the reducible error:
Definition 3.1 (Excess Risk). Let Y = Ix(X) E R be a predictor. The ép excess risk of Y is defined as pp.u( (Y) == Ep.x Epgo where Ep. == e (X)) is the optimal error over all measurable functions.
Assuming the infimum is achievable, we use f.r denote an optimal regressor without faimess constraint over H4, E {0, 1). i.e., f E arg E (X)) Then have the following hold:
Proposition 3.1. Let Y = h(X) be predictor. Under Assumption 2.1 for p 2 1. if there exists e > such that Wp (happon S e, then
pppo (9) + pppp (9) Z
flfozMorfitt distance between optimal unfair predictors across groups
-E + +Eppet
(9)
and Y satisfies 2 SP.
Remark It is easy verify that Proposition 3.1 is generalization of the lower bound presented in Theorem 3.1 when fi are perfect predictors, we have Yg44; f MM; and Ep.u, O, for i E {0,1). Hence in this case the excess risk Tp., (9) reduces to the error E.,, (9). Furthermore, if 0, i.e., Y satisfies the exact statistical parity condition, then the lower bound recovers the lower bound (5) As separate note, Proposition 3.1 also implies that one can use the Wasserstein distance between the predicted distributions across groups as a proxy to ensure approximate statistical parity. This observation has also been shown in Dwork et al. (2012 Theorem 3.3) in classification. Finally, similar to Corollary [.2 the lower bound in Proposition 3.1 for the excess risks could also be extended to give a lower bound for the weighted joint risk when approximate statistical parity (e-SP) is enforced as a constraint. The proof is exactly the same the one for Corollary 3.2 so we omit it here.
3.3 Individual Fairness, Accuracy Parity and the Wasserstein Distance
In the previous section, we show that the Wasserstein distance between the output distributions across groups could be used as a proxy to ensure approximate statistical parity. Nevertheless, Theorem 3.1 and Proposition 3.1 show that statistical parity is often at odds with the accuracy of the predictor, and many real-world scenarios SP is insufficient to be used as a notion of fairness (Dwork et al., 2012] Section 3.1). Alternatively, in the literature, separate notion of fairness, known individual fairness, has been proposed in Dwork al. (2012). Roughly speaking, under the framework of individual fairness, for the classification task T of interest at hand, the learner will have access to (hypothetical) task-specific metric dr(-,-) for determining the degree to which individuals are similar w.r.t. the task T. We emphasize here that the metric dr(:,)) should be task-specific, and in practice, it is often hard (or infeasible) to determine this task specifcc metric. Nevertheless, in this section, we are mainly interested in understanding the relationship between the notion of individual fairness and its connection to accuracy parity, where we use the Wasserstein distance bridge to connect these two. In particular, we say that a predictor is individually fair if treats similar individuals (measured by (r(.-)) similarly:
Definition 3.2 (Individual Fairness, DDwork et al. 2.12 For the task T with task-specific metric dr(+,)) regressor h satisfies p-individual faimess if ''x E X, [x(x h(x') pdr(x,x').
9

---

Published in Transactions on Machine Learning Research (02/2023)
Essentially, individual fairness puts a Lipschitz continuity constraint the predictor with respect to the task-specific metric dr -..) Note that in the original definition (Dwork et al. 2012 Definition 2.1) the authors use general metric dr(+,-) as a similarity measure between individuals, and the choice of such similarity measure is at the center of related applications. In this section, we use . || in Definition 3.2 mainly for the purpose of illustration, but the following results can be straightforwardly extended for any metric dr(...) that is upper bounded by the norm || |l, i.e., there exists > 0, such that Vx, x' E X, (x, S c||x x11 Another notion of group fairness that has gained increasing
attention (Buolamwini & Gebru 2018 Bagdasaryan al. 2019 Chi et al., 202I) is accuracy parity:
Definition 3.3 (e-Accuracy Parity). Given a joint distribution je and 0 S S 1, regressor Y = hXX) satisfies
e-accuracy parity if |+ (8) 11,11 ( S e.
Accuracy parity calls for approximately equalized performance of the predictor across different groups. The following proposition states the relationship between individual fairesss, accuracy parity and the W1 distance between the distributions p4 and 11 of different groups:
Proposition 3.2. If h-) is g-individually fair, then h satisfies vp² + Wi (Ho, H41 accuracy parity.
Together with Lemma A.I in the appendix, Proposition 3.2 suggests that in order to achieve approximate accuracy parity, one can constrain the predictor be Lipschitz continuous while the same time try to decrease the W1 distance between the distributions across groups, via learning representations. In the case where the groups are similar and the Wasserstein distance is small, individual faimess provides some guidance towards approximate accuracy parity. However, in cases where the groups are different (disjoint), representation learning becomes more important.
3.4 Fair Representations with Wasserstein Distance
From the previous discussion, we know that the Wasserstein distance between the predicted distributions and the input distributions can be used to control both statistical parity and accuracy parity, respectively. Is there way to sinultaneously achieve both goals? In this section we shall provide an affirmative answer to this question via learning fair representations. The high-level idea is quite simple and intuitive: given input variable X, we seek to learn a representation = 8(x X) such that W1 (g: 8:/41) is small. If furthermore the predictor acting on the representation Z is individually fair, we can then hope to have small statistical and accuracy disparity simultaneously.
One potential benefit of learning fair representations for statistical parity over other methods based constrained optimization (Agarwal et al. 2019) is that we can release the learned fair representations so that different kinds of downstream tasks could build on top of it without worrying about the faireess constraint anymore. Due to the broceprocsssiig inequality, no matter what predictors for the downstream tasks are placed over the released fair representations, we can guarantee that the predictors on top of the released fair representations are also going to satisfy the statistical parity constraint. As a comparison, for constrained- based optimization methods, one often needs to establish different objective function when working with a different downstream task.
Concretely, the following proposition says if the Wasserstein distance between feature distributions from two groups, Wi (g:Mo. is small, then as long as the predictor is individually fair, it also satisfies approximate statistical parity:
Proposition 3.3. Let Z = =X) be the features from input X. If (8) < e and = h(Z) is p-Lipschitz, then Ý o ( (X) verifies 2/C SCpe-SP.
In practice since we only have finite samples from the corresponding distributions, we will replace all the distributions with their corresponding empirical versions. Furthermore, instead of using the joint error as our objective function, as we discussed in the previous section, we propose to use the balanced error rate instead:
min I
max filss1
(52,po (h g) + E2,, (h g)) + + | (f [f(Z)] Eggi If(z))
(10)
where T >> 0 is hyperparameter that trades off the Ep error and the Wasserstein distance and p is the Lipschitz constant of the predictor. The above problem could be optimized using the gradient aescent-ascentt algorithm (Edwards & Storkey [2055] Zhang et al., 2018). To implement the Lipschitz constraints, we apply weight clipping to the parameters of both the adversary as well as the target predictor. More specifically, we use the projected gradient descent algorithm to ensure the Eg norm of the discriminator and the target predictor are bounded by the preset values.
10

---

Published in Transactions on Machine Learning Research (02/2023)
Comparisons with Related Fair Representation Learning Method One closely related approach that uses the Wasserstein distance as penalty term in representation learning is from Chi et al. (2021), where the authors also formulated a minimax approach to encourage accuracy disparity between different groups. Compared with Eq. (10), from a model perspective, the main difference between our formulation and the one in Chi et al.] (2021) is that the discriminator in Eq. (TO) only takes the features Z. from different groups as input whereas the corresponding discriminator in Chi et al. (202T) takes both the features Z and the label Y as input. Because of this difference, the
motivations of these two approaches are quite different. In our case, we use the Wasserstein distance to penalize the discrepancy between the marginal feature distributions in order to (approximately) achieve statistical parity, whereas the Wasserstein metric used in Chi et al. (202T) is used to align the conditional feature distributions (conditioned on the label Y) between different groups, in order to minimize the accuracy disparity. To encourage accuracy parity, in Eq. (10), we also constrain the predictor to be Lipschitz continuous, following Proposition 3.2
4 Experiments
Our theoretical results imply that even if there is no significant drop in terms of the overall population error when a model is built to satisfy the statistical parity, the minority group can still suffer greatly from the reduction in accuracy. On the other hand, by using the balanced error rate as the objective function, we can mitigate the disparate drops in terms of accuracy between these two groups. Furthermore, by minimizing the Wasserstein distance of the feature distributions across groups, we can hope to achieve both approximate statistical and accuracy parity. To verify these implications, we conduct experiments on a real-world benchmark dataset, the Law School dataset (Wightman 1998). to present empirical results with various metrics. We refer readers to Appendix B for further details about the dataset, our pre-processing pipeline and the models used in the experiments.
Experimental Setup To demonstrate the effect of using Wasserstein distance to regularize the representations with adversarial training, perform a controlled experiment by fixing the baseline model to be a three hidden-layer feed-forward network with ReLU activations, denoted as MLP. To verify the effect of the balanced error rate on reducing the accuracy disparity, we further study two variants of it, where one is using the weighted joint error rate (first row in Table M as the objective function whereas the other (second row in Table D uses the balanced error rate as the objective function. We use W-MLP to denote the model with Wasserstein constraint for representation learning. In the experiment, all the other factors are fixed to be the same across these two methods, including learning rate, optimization algorithm, training epoch, and also batch size. To see how the Wasserstein regularization affects the joint error, the conditional errors as well the statistical parity and accuracy parity, we vary the coefficient T for the adversarial loss between 0.1, 1.0, 5.0 and 10.0. For each setup, we repeat the experiment 5 times and report both the mean and the standard deviation.
To further study the role of the Lipschitz. constant in achieving statistical parity as well as reducing the accuracy disparity, in the second set of experiments we fix the coefficient т = 0.01 and vary the value of p by changing the weight clipping value of the model parameters of both the adversary as well as the target predictor. More specifically, we vary the clipping value for the parameters between 0.01, 0.1, 1.0 and 10.0. Again, for each setup, we repeat the experiment 5 times and report both the mean and the standard deviation.
Results and Analysis Kolmogoroy-Smirno distance of the predicted distribution across groups, which is also the value of approximate statistical parity. From the table, it is then clear that with increasing T, both the statistical disparity and the accuracy disparity are decreasing. Interestingly, the overall error Ey (sensitive to the distribution of A) and the sum of group errors Eno + Epr (insensitive to the imbalance of A) only marginally increase. In fact, for = 1.0, we actually observed better accuracy. We conjecture that the improved performance stems from the implicit regularization via weight clipping of the target predictor. With 10.0, the last row shows that this method could effectively reduce both the statistical and accuracy disparity to value very close to 0, although at the cost of increasing errors. Comparing the two variants of MLP with weighted joint error and the balanced error rate, we can see that the balanced error rate helps to reduce both the Kolmogorov-Sming
The experimental results are listed in Table In the table, we use K P1) to denote the
distance of the predicted distribution across groups as well as the accuracy disparity, at the price of a higher joint error rate as well as the sum of group errors.
The impact of the Lipschitz constant p shown in Table 2 As can be observed from the table, as p decreases, both the Kolmogorov- Smirnov distance of the predicted distribution across groups and the accuracy disparity also decreases. In
11

---

Published in Transactions on Machine Learning Research (02/2023)
Table 1: Fair representations with Wasserstein regularization on the Law School dataset with different values of the regularization coefficient T. We report the overall error, group-wise error, statistical disparity, and accuracy disparity.
Eyo + Em
K(Yo, R1)
eppo (Y) Ex1 (8)
MLP (weighted joint error)
N/A
0.069 0.004
0.296=0.044
0.011
MLP (balanced error rate)
N/A
0.0377+0.005 +00005
0.072
0.283.
0.010
W-MLP
0.1
0.004
0.067 10.008
0.22210.037
0.011
W-MLP
1.0
0.030+0.000
0.059+0.001
0.11640.032
0.011+0.002
W-MLP
5.0
0.03440..00
0.067
1.007
0.008
W-MLP
10.0
0.035+0.001
0.06940.003
0.048
0.006
Table 2: Fair representations with Wasserstein regularization on the Law School dataset with different values of the Lipschitz constant p. We report the overall error, group-wise wise error, statistical disparity, and accuracy disparity.
P
Ex
Ejg + Exg
K(Y), R7)
|xyo (Y) Egg (Y)
W-MLP
10.0
0.000+0.006
0.159+0..02
0.011+0.005
W-MLP
1.0
0.03610.003
0.071 1.000
0.155++0.034
0.01110:005
W-MLP
0.1
0.035
0.069 10.005
0.002
0.008
W-MLP
0.01
0.037 10.002
0.073
0.00310.005
0.006
particular, when p is set to be 0.01, K KYY, 91) can be mitigated 0.003, a value that is very close O. This means that adjusting the Lipschitz constant value p can potentially have larger impact than in controlling the (approximate) statistical parity. Note, however, in this case, both the joint weighted error as well as the balanced error rate are also larger, showing evidence of the trade-off between accuracy and statistical parity again. To conclude, all the empirical results are consistent with our theoretical findings.
5 Related Work
Fair Regression Two central notions of fairness have been extensively studied, i.e. individual fairness and group fairness. [Dwork et al. (20T2) defined individual fairness as Lipschitz constraint of the underlying (randomized) algorithm. However, this definition requires priori distance metric compute the similarity between pairs of individuals, which is often hard construct or design in practice. Group faimess is a statistical definition, and it includes family of definitions which essentially ask some statistical scores to be equalized between different subgroups. Typical examples include statistical parity, equalized odds (Hardt et al., 2016),, and accuracy parity (Buolamwini & Gebru 2018). In this work we focus on an extension of statistical parity to regression problems and study its theoretical tradcoff with accuracy when the regressor cannot directly take the protected attribute as input during both training and inference stages. We also investigate the relationship between individual fairness and accuracy parity and provide a bound through the Wasserstein distance. The line of work on fair regression through regularization techniques dates at least back to Calders al. 2013), where the authors enforce first-order moment requirement between the predicted distributions. More recent works include (Komiyama et al. 2018) that use coefficient of determination faimess when there are multiple sensitive attributes. When the sensitive attribute is continuous, generalized definition
notion of
using the Rényi correlation coefficient exists (Mary et al., 2019). In a recent work, Agarwal et al. (2019) proposed a reduction approach from fair regression to a sequence of cost-sensitive minimization problems. Other approaches include a two-stage recalibration procedure (Chzhen et al.) 2020b) and robust optimization techniques (Narasimhan) et al. 2020). Our definition of statistical parity in the regression setting is stronger than the one Cf al. (2013). which proposed to use the difference of means as the metric. When the output dimension is one, definition also coincides with the one proposed by Agarwal et al. (2019), which amounts to the Kolmogorov-Smingg
distance.
Tradeoff between Fairness and Accuracy Although it has long been empirically observed that there is an inherent tradeoff between accuracy and statistical parity both classification and regression problems (Calders et al., 2009 Zafar et al. 2015 Zliobaite 2015 Berk al. 2017 Corbett-Davies et al. 2017 Zhao et al. 2019a), precise characterizations
12

---

Published in Transactions on Machine Learning Research (02/2023)
such tradcoff's are less explored. |Berk et al. (2017) defined the price of fairness (PoF) under their convex framework for linear and logistic regression problems as the ratio between the loss of the optimal (approximately) fair regressor and the Bayes optimal loss. Under this PoF definition, the authors then explored the accuracy-fairness frontier by changing the approximate coefficient of the fairess constraint, Menon & Williamson 2018 Proposition 8) explored such tradeoff in terms of the fairness frontier function under the context of cost-sensitive binary classification. /Zaao & Gordon 2022) proved a lower bound on the joint error that has to be incurred by any fair algorithm satisfying statistical parity, Our negative result is similar that of Zhao & Gordon (2022) in nature, and could be understood a generalization of their results from classification to regression. Chzhen et al. (2020a) and Le Gouic al. (2020) concurrentyy with each other derived an analytic bound to characterize the price of statistical parity in regression when the learner can take the sensitive attribute explicitly as an input for E loss. In this case, the lower bound is given by the optimal transport distance from two group distributions to a common one, characterized by the W2 barycenter. Our results differ in that in our setting the learner cannot use the sensitive attribute directly as an input, and our results hold for the general p loss. Note that this is significant because is not clear how to extend the results to space with Wp as metrie, since the proof depends on the use of the Pythagoras' decomposition, which only holds under the l2 distance.
On the upside, under certain data generative assumptions of the sampling bias, there is line of recent works showing that fairness constraints could instead improve the accuracy of the predictor (Dutta et al. 2020 Blum & Stangl 2020). In particular, Blum & Stangl (2020) prove that if the observable data are subject to labeling bias, then the Equality of Opportunity constraint could help recover the Bayes optimal classifier. Note that this does not contradict our results, since in this work we do not make any assumptions about the underlying training distributions.
6 Conclusion
In this paper, we show that when the target distribution differs across different demographic subgroups, any attribute- blind fair algorithm in the statistical parity sense has to achieve a large error on at least one of the groups. In particular, we give a characterization of such a tradeoff using the Wasserstein distance. On the other hand, we also establish a connection between individual fairness and accuracy parity, where again, the accuracy disparity gap characterized by the Wasserstein distance. Besides the theoretical contributions, our analysis using Wasserstein distance also suggests practical algorithm for fair regression through learning representations for different demographic subgroups that are close in the sense of Wasserstein distance. Empirical results on real-world dataset also confirm our findings.
Acknowledgements
We would like thank the anonymous reviewers for their helpful comments in improving the technical presentation of the paper. The work of H.Z. was supported in part by Facebook Research Award and Amazon AWS Cloud Credit.
References
General data protection regulation. 2021].
[Online; accessed 13-May-
Alekh Agarwal, Miroslav Dudik, and Zhiwei Steven Wu. Fair regression: Quantitative definitions and reduction-based algorithms. In International Conference on Machine Learning, pp. 120-129, 2019. 2019.
Martin Arjovsky, Soumith Chintala, and Léon Bottou. Wasserstein gan. arXiv preprint
2017.
Eugene Bagdasaryan, Omid Poursaeed, and Vitaly Shmatikov. Differential privacy has disparate impact on model accuracy. Advances in Neural Information Processing Systems, 32: 15499-15588, 2019.
Solon Barocas, Moritz Hardt, and Arvind Narayanan. Fairness in machine learning. NIPS Tutorial, 2017.
Richard Berk, Hoda Heidari, Shahin Jabbari, Matthew Joseph, Michael Kearns, Jamie Morgenstern, Seth Neel, and Aaron Roth. A convex framework for fair regression. arXiv preprint arXiv: 2017.
Alex Beutel, Jilin Chen, Zhe Zhao, and Ed H Chi. Data decisions and theoretical implications when adversarially learning fair representations. arXiv preprint arXiv: 2017.
13

---

Published in Transactions on Machine Learning Research (02/2023)
Avrim Blum and Kevin Stangl. Recovering from biased data: Can fairness constraints improve accuracy? In Symposium Foundations of Responsible Computing (FORC), volume 1, 2020.
Joy Buolamwini and Timnit Gebru. Gender shades: Intersectional accuracy disparities in commercial gender classifica- tion. In Conference on fairesss. accountabilityy and transparency, pp. 77-91. PMLR, 2018.
Toon Calders, Faisal Kamiran, and Mykola Pechenizkiy. Building classifiers with independency constraints. In 2009 IEEE International Conference on Data Mining Workshops, pp. 13-18. IEEE, 2009.
Toon Calders, Asim Karim, Faisal Kamiran, Wasif Ali, and Xiangliang Zhang. Controlling attribute effect in linear regression. 2013 IEEE 13th International Conference on Data Mining, pp. 71-80. IEEE, 2013.
Flavio P Calmon, Dennis Wei, Bhanukiran Vinzamuri, Karthikeyan Natesan Ramamurthy, and Kush Varshney. Optimized pre-processing for discrimination prevention. In Proceedings of the 31st International Conference on Neural Information Processing Systems, pp. 3995-40044, 2017.
Sourav Chatterjee. Lecture notes in stein's 's method and applications, August 2007.
Jianfeng Chi, Yuan Tian, Geoffrey Gordon, and Han Zhao. Understanding and mitigating accuracy disparity in regression. In International Conference Machine Learning, 2021.
Evgenii Chzhen, Christophe Denis, Mohamed Hebiri, Luca Oneto, and Massimiliano Pontil. Fair regression with wasserstein barycenters. arXiv preprint arXiv:2006.07286, 2020a.
Evgenii Chzhen, Christophe Denis, Mohamed Hebiri, Luea Oneto, and Massimiliano Pontil. Fair regression via plug-in estimator and recalibration with statistical guarantees. Advances in Neural Information Processing Systems, 33: 19137-19148, 2020b.
Sam -avies, Emma Pierson, Avi Feller, Sharad Goel, and Aziz Huq. Algorithmic decision making and the cost of fairness. In Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining,, pp. 797-806. ACM, 2017.
Nicolas Courty, Rémi Flamary, Amaury Habrard, and Alain Rakotomamonjy. Joint distribution optimal transportation for domain adaptation. In Advances in Neural Information Processing Systems, pp. 3730-3739, 2017.
Marco Cuturi and Arnaud Doucet. Fast computation of wasserstein barycenters. In International conference on machine learming, pp. 685-693, PMLR, 2014.
Sanghamitra Dutta, Dennis Wei, Hazar Yueksel, Pin- Yu Chen, Sijia Liu, and Kush Varshney. Is there a trade-off between faimess and accuracy? a perspective using mismatched hypothesis testing. International Conference on Muchine Learning, pp- 2803-2813. PMIR, 2020.
Cynthia Dwork, Moritz Hardt, Toniann Pitassi, Omer Reingold, and Richard Zemel. Fairness through awareness. In Proceedings of the 3rd innovations in theoretical computer science conference, pp. 214-226. ACM, 2012.
Harrison Edwards and Amos Storkey. Censoring representations with adversary. arXiv preprint arXiv: 1rX.v.7511.05897, 2015.
Michael Feldman, Sorelle A Friedler, John Moeller, Carlos Scheidegger, and Suresh Venkatasabramanian Certifying and removing disparate impact. In proceedings of the 2/th ACM SIGKDD international conference on knowledge discovery and data mining, pp. 259 259-2688220 2015.
Yaroslav Ganin, Evgeniya Ustinova, Hana Ajakan, Pascal Germain, Hugo Larochelle, François Laviolette, Mario Marchand, and Victor Lempitsky. Domain-adversarial training of neural networks. The Journal of Machine Learning Research, 17(1):2096-200 2016.
Alison L Gibbs and Francis Edward Su. On choosing and bounding probability metrics. International statistical review, 70(3):419-433 2002.
Clark R Givens, Rae Michael Shortt, al. A class of wasserstein metrics for probability distributions. The Michigan Mathematical Jourmal, (12)2331-224, 1984.
14

---

Published in Transactions on Machine Learning Research (02/2023)
Peter D Grünwald, A Philip Dawid, al. Game theory, maximum entropy, minimum discrepancy and robust bayesian decision theory. Annals of statistics, 3264):136 2004.
Moritz Hardt, Eric Price, Nati Srebro, et Equality of opportunity in supervised learning. In Advances neural information processing systems, pp. 3315-3323, 2016.
Harry Holzer and David Neumark. Affirmative action: What do we know? Journal of Policy Analysis and Management, 25(2):463-490, 2006.
Fredrik Johansson, Uri Shalit, and David Sontag. Learning representations for counterfactual inference. In International conference on machine learning, pp. 3020-3029, 2016.
Fredrik D Johansson, Uri Shalit, Nathan Kallus, and David Sontag, Generalization bounds and representation learning for estimation of potential outcomes and causal effects. arXiv preprint urXiv:2001.07420 2020.
James E Johndrow, Kristian Lum, al. An algorithm for removing sensitive information: application race-
independent recidivism prediction. The Annals of Applied Statistics, 13(1):189-220) 2019.
Faisal Kamiran and Toon Calders. Classifying without discriminating. In 2009 2nd International Conference on Computer, Control and Communication, pp. 1-6. IEEE, 2009.
Toshihiro Kamishima, Shotaro Akaho, and Jun Sakuma. Fairness-awan learning through regularization approach. In 2011 IEEE 1 11th International Conference Data Mining Workshops, pp. 643-650. IEEE, 2011.
Soheil Kolouri, Se Rim Park, Matthew Thorpe, Dejan Slepcev, and Gustavo K Rohde. Optimal mass transport: Signal processing and machine-learning applications. IEEE signal processing magazine, 34(4):43-59, 2017.
Junpei Komiyama, Akiko Takeda, Junya Honda, and Hajime Shimao. Nonconvex optimization for regression with fairness constraints. In International conference machine learning, pp. 2737-2746. PMLR, 2018.
Thibaut Le Gouic, Jean-Michel Loubes, and Philippe Rigollet. Projection to fairness in statistical learning. arXiv e-prints, pp. arXiv-20033 2020.
Jing Lei et al. Convergence and concentration of empirical measures under wasserstein distance in unbounded functional spaces. Bernoulli, 26(1):767-798, 2020.
Christos Louizos, Kevin Swersky, Yujia Li, Max Welling, and Richard Zemel. The variational fair autoencoder. arXiv preprint arXiv:/511.008850 2015.
arXiv preprint Kristian Lum and James Johndrow. A statistical framework for fair predictive algorithms.
arXiv:1610.0807 2016.
David Madras, Elliot Creager, Toniann Pitassi, and Richard Zemel. Learning adversarially fair and transferable representations. In International Conference Machine Learning, pp.
2018.
Jérémie Mary, Clément Calauzenes, and Noureddine El Karoui. Faimess-aware learning for continuous attributes and treatments. In International Conference on Machine Learning, pp.
PMLR, 2019.
Aditya Krishna Menon and Robert C Williamson. The cost of fairness in binary classification. In Conference Fairness, Accountability and Transparency, pp. 107-118, 2018.
Harikrishna Narasimhan, Andrew Cotter, Maya Gupta, and Serena Wang. Pairwise faimess for ranking and regression. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pp. 5248-5255, 2020.
Uri Shalit, Fredrik D Johansson, and David Sontag. Estimating individual treatment effect: generalization bounds and algorithms. In Proceedings of the 34th International Conference on Machine Learning- Volume 70, pp. 000760008555 JMLR. org, 2017.
Sahil Verma and Julia Rubin. Fairness definitions explained. In 2018 IEEE/ACM International Workshop on Software Fairness (FairWare). pp. 1-7. IEEE, 2018.
15

---

Published in Transactions on Machine Learning Research (02/2023)
Cédric Villani. Optimal transport: old and new, volume 338. Springer, 2009.
Jonathan Weed, Francis Bach, et al. Sharp asymptotic and finite-sample rates of convergence of empirical measures wasserstein distance. Bernoulli, 25(4A):2620-264) 2019.
Linda F Wightman. Lsac national longitudinal bar passage study. Isac research report series. 1998.
Muhammad Bilal Zafar, Isabel Valera, Manuel Gomez Rodriguez, and Krishna P Gummadi. Fairness constraints: Mechanisms for fair classification. arXiv preprint arXiv:1507.0522 2015.
Rich Zemel, Yu Wu, Kevin Swersky, Toni Pitassi, and Cynthia Dwork. Learning fair representations. In International Conference on Machine Learning, pp. 325-333, 2013.
Brian Hu Zhang, Blake Lemoine, and Margaret Mitchell. Mitigating unwanted biases with adversarial learning. In Proceedings of the 2018 AAAI/ACM Conference on AI, Ethics, and Society, pp. 335-340. ACM, 2018.
Han Zhao and Geoffrey J Gordon. Inherent tradcoffss in learning fair representations. In Advances in neural information processing systems, 2019.
Han Zhao and Geoffrey Gordon. Inherent tradeoff's in learning fair representations. Journal of Machine Learning Research, 23(57):1-26, 2022. URL /ttp:/// http:///wwm.rrrrr/ppppee////////
httml
Han Zhao, Amanda Coston, Tameem Adel, and Geoffrey J. Gordon. Conditional learning of fair representations. arXiv preprint arXiv:1910.07162, 2019a.
Han Zhao, Remi Tachet Des Combes, Kun Zhang, and Geoffrey Gordon. On learning invariant representations for domain adaptation. In International Conference on Machine Learning, pp. 7523-7532, 2019b.
Indre Zliobaite. On the relation between accuracy and fairness in binary classificatton. arXiv preprint arXiv:1505.05723, 2015.
16

---

Published in Transactions on Machine Learning Research (02/2023)
A
Missing Proofs
In this section we provide all the missing proofs in the main text. For the ease of the readers, in what follows we shall first restate the theorems that appear in the main text and then provide the corresponding proofs.
A.1 Proofs of Theorem 3.1 and Corollary 3.1
Theorem 3.1. Let Y h()) be predictor. If y satisfies statistical parity, then v/p 1,
Ep.oo (9) + Eppus (9) Wp(YyNo. YyH1).
(5)
Proof.
First, realize that Wp(+.) is metric of probability distributions, the following chain of triangle inequalities
holds:
WY YgH1) < WY hyHo) + (h11) + Wp(hsp4i Y:H41.
Now due to the assumption that = (X) ) is independent of A, the second term, hyH1). is O, leading to:
Wp (Y Y/Hi S (Yy))oo + Wp(hepki, Y9H1).
(11)
Next, for a E {0,1), by definition of the Wasserstein distance,
(YPaaaa = (nn ( (Iy "pr)""== (F
1/P
Eppli (8),
(12)
where we use the fact that the pushforward distribution of Na under It is particular coupling between Y and Y to establish the above inequality. Applying the inequality (12) for both a 0 and = and combining it with inequality (11) completes the proof.
Corollary 3.1. If Y satisfies statistical parity, then 1, (9) E1,4g (8) 2 Epp M E,, [+] and 22240 (Y) + 22 Epo [ E,, [Y]
Proof. We first prove the first inequality in Corollary 3.1 identity map, i.e., Id(y) y, vy E IR. Clearly Id(, is -Lipschitz. Using the sup characterization of the Wasserstein distance, we have:
Apply Theorem 3.1 by setting p 1. Let Id y y be the
Eyg 1 Y| E [|8 Yll (Y YsH1)
(Theorem 3.1
/ f dY - (((Y)1n)
sup
1
/ ld d(Y;)H)) - [Idd(YsH)) (
(Id 1-Lipschitz)
/ Y dho |f x amd
(Change of Variable)
E [ E MM
(13)
where the second to last equation follows from the definition of pushforward distribution.
17

---

Published in Transactions on Machine Learning Research (02/2023)
To prove the second inequality in Corollary 3.1 again set p 2 in Theorem 3.1 and realize that for a, b, we have
a² + 12 2 (a + /2 by the AM-GM inequality. Hence when p 2, we have
Eyo - + M, || YP1 2
E Ao
8 - YI] + E || - YI]
(Jensen's inequality)
EhO Enoll 1 -Y|] + Emg 11 Y1
22 2
(AM-GM inequality)
2
1 (Epol18- - YI]+ + Eqg 118 -11) 2
2
Epp MM -pp [M]
(Eq. (3
2
Note that for the last equation we apply the lower bound Eyo [| - YI] + Epp 1| - Y]] 2 |Exo M Eyn [X] we proved in the first inequality.
A.2 Proof of Theorem 3.2
Before provide the proof of Theorem 3.2 first recall some useful results about the Wasserstein distance (Weed et al. 2019 Lei et al. 2020).
Proposition A.1 (Proposition 20, (Weed et al. 2019)). For all 2 0 and p > 1, let & be empirical distribution induced from z with sample size n. Then,
Pr(W (H, ()) 2 EW (M, (M,AA) An) + s exp(-2nt))
(14)
Proposition A.1 gives a concentration incquality of W (c, around its mean. Note that the expectation in (44 over
the draw of the sample size n. This inequality is particularly useful when p = 1 since it reduces to W1( and gives convergence rate of (n)
Theorem 3.1), which bounds the rate of IEW, (14, Rt)): Theorem A.1 (Theorem 3.1, (Lei et al. 2020)). Let Å be an empirical distribution induced from j with sample size n, p > 1 and recall that y [-11, 1, Then
The following theorem is special case of (Lei et al.
2020
Ygp) S cp n #,
(15)
where Cp is positive constant that only depends on p.
Again, the interesting case here is when p = 1, which gives the same rate of O(1//)/// that coincides with the one in Proposition A.I
Theorem 3.2. Let Y = I(X) be the predictor and á be an empirical distribution induced from sample of size n drawn from μ.. If Y satisfies statistical parity, then there exists absolute constant Ci 0 such that for 0 5 < 1, with probability at least 1 8 over the draw of the sample,
1
2, ( + em ( 10 ( 1im ( 2 Wi Y;RI) (201 + / 22go((21))
V
(6)
Proof. We first prove the finite sample lower bound w.r.t. the &j error. Realize that W1 (- is metric, the triangle inequality gives us
W1 (Yμ Y241 < (Y,Ro, YuMo) + W1 + (YGH4, X9p)).
Combined with Theorem 3.1 the above inequality leads to
1,HOo (8) + 1 (8)= 2 (Yg Y₂p1) (Wi YsHo) W1 (YgH1, Y;f1))
18

---

Published in Transactions on Machine Learning Research (02/2023)
Hence it suffices if could provide high probability bound further lower bound Wi (YgM,, YgPi). for i {0,1}.
To this end, we first apply Proposition A. with p 1: let exp(-2nf=) 8/2 and solve for f, we have (log(2/8)/2x, which means that with probability at least 1 - 8/2.
log(2/0) (2/6)
Wi (YG9A, S TEW (Yg Y244;) +
2n
12g(2/5)
cpl
(Theorem A.
2n
Now apply the above inequality twice, one for i E {0,1), 1}. With a union bound, we have shown that w.p. 2 1- 8,
10 (9) + E114 (2) 2 WY Xgp1) - 22c + 2 (2log(2/0) V=
1
To prove the second lower bound w.r.t. the &g error, simply realize that 82, ( 2 1,m ( for i E {0,1), which completes the proof.
A.3 Proof of Corollary 3.2
Corollary 3.2. Let Y = l(X) be predictor. If y satisfies statistical parity, then Vp 2 1. the joint error has the following lower bound:
p (9) (o) Wy(YpMo, Y(H1).
Proof. To simplify the notation used in the proof, define == Ep (), Eo :- Eppi (Y) and E == Epm, (Y). Let
Pa = pry (A a). By Theorem 3.1 we know that Eo + E1 2 Wp (Y=NNO Y/111.. By definition the joint error:
g = Poso + 118 2 min (eo + +1) 2 (A-) Wy Y(H1).
A.4 Proof of Proposition 3.1
As comparison to the Kolmogorov-Smimet distance, the W1 distance between distributions R could be equivalently represented as:
Proposition A.2 Gibbs & Su (2022). For two distributions μt j¹ over IR (1 n²) fR (y((z) (z)( dz.
Proposition A.2 was stated as fact without proof in (Gibbs & Su 2002) but it is not hard to see that it could be proved using the equivalent characterization of W₁ in (4) by changing the integral variable. Furthermore, in regression both ş and z' are continuous distributions, then the following well-known result (Chatterjee, 2007 Lemma 2) serves as a bridge to connect the Wasserstein distance (-.-) and the Kolmogorov-Smin -mirnov distance K(,,)):
Lemma A.1. If there exists a constant C such that the density of μ' (w.r.t the Lebesgue measure A) is universally bounded above, i.e., ||dy' / | < C, then K(μ, p²) < 2/C (H,
Using Kolmogorov-Smiroov distance, the constraint in the optimization problem could be equivalently expressed K(hgHo, hy/41) < Now with Lemma A.1 we ready prove Proposition 3.1
Proposition 3.1. Let Y h(X) be predictor. Under Assumption 2.1 for p 2 1. if there exists > such that W, (hypo, < then
Ty ( + Fp (Y)=
WploozHo. fi (1)
2E P.o + +ppm) E,
distance optimal unfair predictors across groups
and & satisfies CP.S.
19

---

Published in Transactions on Machine Learning Research (02/2023)
Proof.
First, for E 10, by definition of the Wasserstein distance, for any predictor Y h(X):
(yHHyaan = (in LinfEE,IIYY 11
1/p
1/p
Eptio (
(16)
Applying the above inequality to both h and fū, we have:
(p YzHa) +
(aaHa S E (9) + Ep,io (f(()) = Epilo (8) + Epp
Aa E {0.1).
(17)
On the other hand, by the triangle incquality,
Wp h131))
Σ
(hyhglrr YzHo) + (YtHar 2 (i
aE(0,1}
Now by the assumption Whyho hyH1) S and Eq. we have:
e
Σ Eppr ( + EpNa 2 Mo
(0.1)
By the definition of the excess risk, rearranging and subtracting 2 Eu (0.1) Epp from both sides of the inequality then completes the proof of the first part.
To show that Y is Ce-SP, first note that Y h(X) f-SP iff K(hg hxH1) I t. Now apply Lemma A.1 under the assumption that Wp (hyguo, h1H1) S e:
K(hgHo, h1 S v CWi h1111)
(Lemma A.
< 2 (Wp((4Ho.
(Monotonicity of the Wp (p())))
< Ce,
completing the proof.
A.5 Proof of Proposition 3.2
Proposition 3.2. If h()) is p-individually fair, then / satisfies vp² +1 1- W1 (41 aaccuray parity.
Proof. Define g(X, Y) 18- Y| [n(x) Y/- We first show that if lx() is p-Lipschitz, then g(X, Y) is
pp + 1-Lipschitz: for Vx, x, x':
1g(x,1)) 8(',,//))
|1((x) y1 - 11(x)) y'll
< [x(x) 1(x') y y
(Triangle inequality)
S 11(x) 1(x') + +1y-+ly-- -1y-1/ -vl
s pl|x - x'1l + ly w-yl 1/l
(h is p-Lipschitz) (Cauchy-Schwar)
S v 02 + 1. v|x x112 ly - y'12
v +1 [xxx,)) (x/y/)1l
Let p' = vp2 I. Now consider the error difference:
1, (8) E1,M (8) |E (x)()) Yl] -Ep [lx(x) YIII
= E 1g(X, (X, Y) - Ey (x,,)((X,Y)) Y)]
S sup |E Is' (x, Yi] - Epg ig' (X, Y)]
1pp
=p' sup |Eo (x, Y)] - E Ig' (X, Y)]
I
= p' (Ha,
(Kantorovich duality)
which completes the proof.
20

---

Published in Transactions on Machine Learning Research (02/2023)
A.6 Proof of Proposition 3.3
Proposition 3.3. Let Z g(X) be the features from input X. If Wi (8:M0 S é and Y = h(Z) is p-Lipschitz, then Y = (h o (X) verifies 2 2 Cpe-SP.
Proof. We first show that (h g) (h g)444) is small if h is p-Lipschitz. To simplify the notation, define Mo == 8:Ho and 11 == 8:/41 Consider the dual representation of the Wasserstein distance:
/ a(hap') - f a(bep()
Wi(k marl) = sup 11
(Kantorovich duality)
f f - f oo
/
= sup |
(Change of Variable formula)
/ I / duh
sup I|
(h is p-Lipcchitz)
p W1 m()
p. Wi (8 8:/41
S pe,
where the first inequality is due to the fact that for If S 1, 1lf ktll S ll |Ml = p. Applying Lemma A.1 to W1 (he Mpp() then completes the proof.
B
Further Details about the Experiments
B.1
Dataset
The Law School dataset contains 1,823 records for law students who took the bar passage study for Law School Admission The features in the dataset include variables such as undergraduate GPA, LSAT score, full-time status, family income, gender, etc. In the experiment, we use gender as the protected attribute and undergraduate GPA as the target variable. We use 80 percent of the data as our training set and the rest 20 percent as the test set. The data distribution for different subgroups the Law School dataset could be found in Figure 2 In the Law School dataset, Pr(A 1) 0.452, which a quite balanced dataset. All the experiments are performed on Titan 1080 GPU.
B.2 Network Architectures
We fix the baseline model to be a three hidden-layer feed-forward network with ReL.U activations. The number of units in each hidden layer is 50 and 20, respectively. The output layer corresponds to linear regression model. This baseline is denoted as MLP. To verify the effect of the balanced error rate on reducing the accuracy disparity, we further study two variants of it, where one using the weighted joint error rate (first row in Table [T] as the objective function whereas uses the balanced error rate the objective function. For learning with Wasserstein
the other (second row in Table TD regularization, the adversarial discriminator network takes the feature from the last hidden layer input and connects it to a hidden-layer with 10 units, followed by auditor whose goal is output score function in distinguishing the features from the two different groups. This model is denoted as W-MLP. Compared with MLP, the only difference of W-MLP in terms of the objective function is that besides the & loss for target prediction, the W-MLP also contains a loss from the auditor to distinguish the sensitive attribute A.
B.3 Hyperparameters used in Experiments
In this section, report the detailed hyperparameters used in experiments to obtain the results in Table T Throughout the experiments, we fix the learning rate to be 1.0 and use the same networks as well random seeds. One
We the edited public version of the dataset which be downloaded here: https:: /t/gt//tttiii com http:ttwww..oomoloaattteeeeeeeee http:/aataccpeee/////rrattt
blob/mester/on awwwscoo csv
21

---

Published in Transactions on Machine Learning Research (02/2023)
350
A-0
A-1
300
of Examples
250
200
150
100
50
0
.050
.150
.250
.350
.450
.550
.650
.750
.850
.900
Figure The data distributions of different groups in the Law School dataset.
important aspect in the implementation of the Wasserstein adversary is the choice of the clipping parameter for the weights in the adversary network. The values used in our experiments shown below in Table 3
Table 3: Clipping parameters used in training the Wasserstein adversary.
T
Clipping Value
W-MLP
0.1
0.1
W-MLP
1.0
1.0
W-MLP
5.0
5.0
W-MLP
10.0
10.0
22


Reviews:
[{"review_id": "JeXazZYjQm", "reviewer": "Reviewer_o86N", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Weaknesses\n1. This paper basically finds a characteristic for random variables without taking into account the learning problem. Basically, given that $\\hat{Y}$ is independent of $A$, it finds a lower bound for $E\\{|Y-Y|^p|A=0\\}^{\\frac{1}{p}} + E\\{|Y-Y|^p|A=1\\}^{\\frac{1}{p}}$. For the bounds found in this paper, it really does not matter what objective function we are minimizing or what model (linear, quadratic, DNN) we are considering. The bounds basically follow by the Wasserstein distance definition (it has an infimum operator in the definition, which leads to a lower bound). \nIf I am using a linear model or quadratic model, or if I am minimizing MSE or MAE, the bound remains the same. \n\n2. several theorems find a lower bound for $\\epsilon_{p,\\mu_0} + \\epsilon_{p,\\mu_1} $ (e.g.m theorem 3.1). I really do not understand why we need a lower bound for $\\epsilon_{p,\\mu_0} + \\epsilon_{p,\\mu_1} $. A lower bound for $\\epsilon_{p,\\mu_0} + \\epsilon_{p,\\mu_1} $ does not give us any lower bound for the overall loss or the loss of each group. \nSo my question is that if $\\epsilon_{p,\\mu_0} + \\epsilon_{p,\\mu_1}\\geq L $, can we find a lower bound for $\\epsilon_{p,\\mu_0}  $ and $\\epsilon_{p,\\mu_1}$, $\\epsilon_{p,\\mu}$ and $l_p$ error?\n\n3. The paper claims that it finds the privacy accuracy tradeoff. However, there is no theorem that find a lower bound for weighted lp error pr lp error that when $\\hat{Y}$ satisfies $\\epsilon$-SP. Proposition 3.1 tries to find an upper bound for the fairness level and a lower bound for $r_{p,\\mu_0} + r_{p,\\mu_1}$. However, having a lower bound for  $r_{p,\\mu_0} + r_{p,\\mu_1}$ does not tell us anything about the lower bound on the overall loss. \nMy question: if the $\\hat{Y}$ satisfies $\\epsilon$-SP, what would be the lower bound for $\\epsilon_{p,\\mu}$ and $l_p$ error?\n\n4. The results do not give any insight into any practical learning problem. Some bounds do not seem useful. \n\nStrengths:\n\nMost of the results are mathematically correct. \n \n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper tries to understand the fairness and accuracy trade-offs in a learning problem. The bounds are based on Wasserstein distance. ", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "The authors should add the answer to the following questions to the paper:\n\n1. How does the model complexity (e.g., linear or quadratic) or objective function (e.g., MSE, MAE, MSE+l_2norm, MAE+l_2norm, etc.) affect the lower bounds found in the paper? In the current form, the lower bounds remain the same no matter what the optimization problem is. \n\n2. How the lower bounds can give us insight into practical problems? Since the lower bounds do not depend on the nature of the learning problem, they seem loose in general. For example, when there is an imbalanced population, the lower bound in equation 7 is close to zero. \n\n3.  If $\\epsilon_{p,\\mu_0} + \\epsilon_{p,\\mu_1}\\geq L $, can we find a lower bound for $\\epsilon_{p,\\mu_0}  $ and $\\epsilon_{p,\\mu_1}$, $\\epsilon_{p,\\mu}$ and $l_p$ error?\n\n4. if the $\\hat{Y}$ satisfies $\\epsilon$-SP, what would be the lower bound for $\\epsilon_{p,\\mu}$ and $l_p$ error?\n\n5. The last equation on page 7 and the first equation on page 8 are not contradicting each other. Could you please double-check them?", "broader_impact_concerns": "None", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "8WkiU8lhPh", "reviewer": "Reviewer_rDyX", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths\n- Study an important topic in fair ML and the writing is mostly clear\n- Provide several interesting lower bounds when the predictor satisfies statistical parity, and the lower bounds are tight\n- Comparison to existing bounds are clear and informative\n\nWeaknesses\n- There is a gap between the theory and the proposed algorithm\n- The experiment results are limited\n\nDetailed comments:\n\n1. The proof in Fig.1 is confusing. First of all, due to statistical parity (Def.2.1), the image of $\\mu_1$ and $\\mu_2$ should be the same. Then a single triangle inequality suffices. Second, making the distinction between $h_1$ and $h_0$ doesn’t seem to provide any more useful discussion for the problem. Finally, it would be more clear to define $\\epsilon_{p,\\mu_0}$ and $\\epsilon_{p,\\mu_1}$ explicitly. Equation (1) is for the joint \\mu.\n\n2. (8) is not very well-motivated. The theorems in Sec.3.1 discuss what happens when the predictor $\\hat{Y}$ satisfies statistical parity (SP). However, there is not much discussion about why objective (8) can lead to SP. In other words, it remains unclear whether small (8) is a sufficient condition for SP. We have a similar situation for (10). Prop.3.3 suggests that small Wasserstein distance + Lipschitz predictor are sufficient for SP, then why do we need the balanced error objective (first term in (10))? \n\n3. Experiment\n\n- What if we only use the balanced objective for the MLP? If it is already using the balanced objective (8), then what’s the performance using the joint (unbalanced) error instead? This would be useful to see the effects of the two terms in (10).\n- It would be important to see the effect of $\\rho$ since Prop.3.2 and 3.3 suggest that small $\\rho$ leads to better accuracy parity and SP.\n- In Table 1, the trend in K is nice but does not really verify the theory. Again, the discussion in Sec.3.1 does not say anything about small Wasserstein distance can result in a better SP.\n\nMinor comments:\n- Page 5, last paragraph, the first inequality holds not because $l_p$ norm is convex, but because $x^{1/p}$ is concave. This is the same as the middle derivation on Page 3.\n- Page 2 Sec.2: why does $F_\\mu$ take a scalar as input? $mu$ is the joint distribution over the product space $X\\times A\\times Y$ which is multivariate.\n- Page 6: “reduce the joint accuracy too much”, but the current paper focuses on regression. The same happens for many other occurrences of “accuracy” in the paper (e.g., the first few sentences in Sec.4).", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This work provides several theoretical analyses on the relation between Wasserstein distance (of two groups specified by a binary protected attribute) and various fairness definitions, in the regression setting. Specifically, Sec.3.1 & 3.2 provide several lower bounds on the errors (Thm. 3.1 & 3.2) or risks (Prop. 3.1) when the regressor satisfies statistical parity (Def. 2.1). Comparisons to other similar bounds or algorithms are also discussed throughout the paper. The proposed optimization (10) minimizes the balanced error rate and Wasserstein distance. Finally, empirical studies on the Law School dataset show that smaller Wasserstein distance can lead to better statistical parity and accuracy parity.", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "1. Discuss why (8) can lead to SP as mentioned above.\n2. Additional experiments as mentioned above.", "broader_impact_concerns": "This work studies fair ML algorithms and thus intrinsically could have a great impact for practical applications. It would be helpful for the authors to discuss it (at least briefly) in the paper.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "np0q9RxLrc", "reviewer": "Reviewer_HaYk", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n-The lower bound results are quite crisp and easy to understand intuitively. \n-The lower bound results provide insight into what happens in error disparity when enforcing fairness constraints. With this insight, the authors encourage using a balanced error rate and hence using a more of a cost-sensitive  approach. \n-Instead of relying on the structure of the function to describe the lower bounds (i.e. linear regressor), it’s nice that the lower bounds are described in terms of the characteristic of the underlying distribution, meaning these results are resistant to what kind of regressor is being used.\n\nWeaknesses/Questions/Concerns:\n-Although it’s stated that the individual fairness with respect to other metric can be easily taken care of, it’s not clear that this is actually the case. It seems like the result depends on the Kantorovich duality and its special case when the underlying metric is some Lp norm. \n\n-It’s stated that the results here are algorithm-independent, but I think the term algorithm and model are conflated here: I think the authors mean that the results are with respect to any arbitrary function f, not an algorithm that was used to come up with such f’s, right? \n\n-I think it’s possible that readers may not be convinced of optimizing for equation (10) in order to get statistical/error disparity, as this algorithm encourages statistical/error parity in a slightly round about way. So I think it would be good to include other algorithms for comparison.\n\n-Throughout the paper, the results seem to be talking about any arbitrary function f as opposed to think about a family of functions (e.g. linear regressor). Is my understanding correct? \n\n-It seems like an example showing the tightness of the lower bound is only for the noiseless setting, but is there any thing that can be said in the approximate & noisy setting?\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper studies the tradeoff between accuracy and statistical parity constraint, which asks that the prediction be independent of the underlying predictor. in the regression setting. \n\nThe main results include\n(1) Lower bounds on the sum of squared loss (and risk) on two groups can be bounded by the wasserstein distance between the groups' label distributions (Theorem 3.1, Proposition 3.1)\n(2) Relationship between individual fairness and error parity (Proposition 3.2)\n\nThey perform experiments on a real world dataset to corroborate their theoretical results.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "-Explanation as to how the individual fairness with respect to Lp norm can be generalized to arbitrary metric.\n-The authors state the minimax objective can be optimized via stochastic gradient descent, and I think it would be helpful to go into a little more detail about how such objective can be optimized via gradient descent: i.e. is it just alternating between the min player doing stochastic gradient descent and the max player doing stochastic gradient ascent?\n", "broader_impact_concerns": "I don't have any concern on the ethical implication of the work. ", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: 
In this paper, the author investigated the essential tradeoff between accuracy and fairness. Specifically, the author provided an algorithm-independent lower bound with intuitive explanation. The author also extend the results for noise setting in terms of Wasserstein distance, and proposed a fair representation learning inspired by the theoretical understanding. Preliminary experimental study has been conducted to verify the proposed algorithm. 

All the reviewers agree that the paper is theoretical solid and provides new insights, especially Reviewer HaYk, who acknowledges the importance of the algorithm-independent lower bound. The major discussion is about the practical implication of the theoretical results (Reviewer o86N) and the insufficiency in empirical study (Reviewer rDyX). 

Therefore, I recommend acceptance with minor revision. The authors should take the suggestions from reviewers, especially Reviewr rDyX, to add more comprehensive empirical comparison as the author promised. 
Decision: Accept (poster)