The Cost of Privacy in Fair Machine Learning
Authors: Songkai Xue
Yuekai Sun
Venue: Submitted to ICLR 2023 (2023)

Abstract: A common task in fair machine learning is training ML models that preserve certain summary statistics across subpopulations defined by sensitive attributes. However, access to such sensitive attributes in training data is restricted and the learner must rely on noisy proxies for the sensitive attributes. In this paper, we study the effect of a privacy mechanism that obfuscates the sensitive attributes from the learner on the fairness of the resulting classifier. We show that the cost of privacy in fair ML is a decline in the generalizability of fairness constraints.

Under review as a conference paper at ICLR 2023
THE COST OF PRIVACY IN FAIR MACHINE LEARNING
Anonymous authors
Paper under double-blind review
ABSTRACT
A common task in fair machine learning is training ML models that preserve certain summary statistics across subpopulations defined by sensitive attributes. However, access to such sensitive attributes in training data is restricted and the learner must rely on noisy proxies for the sensitive attributes. In this paper, we study the effect of privacy mechanism that obfuscates the sensitive attributes from the learner on the fairness of the resulting classifier. We show that the cost of privacy in fair ML is decline in the generalizability of fairness constraints.
INTRODUCTION
The fairness of machine learning systems is gaining increasing attention in recent years, Among the numerous fairness objectives is ensuring that machine learning model does not discriminate against subpopulations that are typically identified by sensitive attributes (e.g., race, gender). When training a fair model and evaluating model bias, it is necessary to possess sensitive attributes; however, access to and use of such sensitive data is frequently prohibited by laws and regulations. Credit card companies, for instance, are not permitted to inquire about person's 's race when they apply for credit, yet they must demonstrate that their decisions are not discriminatory (Chen et al.) 2019).
Ideally, sensitive personal information should not be disclosed during the training of ML models. However, it is impossible to ensure exact notions of fairness (such demographic parity or equality of opportunity) without any knowledge of the sensitive data. Fortunately, differential privacy (Dwork) jet al. 2006) is promising workaround, which
offer graceful compromise between privacy and utility. Mozannar et al. (2020) propose to release sensitive attributes in a locally differentially private way: adding noise the sensitive data so that adversaries cannot infer any information with high confidence about single record.
The advantage of the privacy mechanism proposed by Mozannar al. (2020) is an invariance prop- erty: exact notions of fairness with regard to true sensitive attributes and noisy sensitive attributes are equivalent. An implication the invariance property is that the optimal model of fairness can be learned at the population level. Nonetheless, it remains unclear what the precise statistical impact of privacy on fairness is.
In this work, we study the statistical cost of privacy fairness in the task of learning fair ML models with differentially private sensitive attributes. The main benefits of the developed theory are
1. statistically principled:
We propose statistically principled metric to characterize the cost of privacy on fairness. A restricted notion of statistical efficiency precisely quantifies the privacy cost asymptotically.
2. interpretable: Privacy leads to a decline in the statistical efficiency. Such efficiency loss is interpretable: explicitly depends on the privacy budget, the subpopulation imbalance level, and few other problem-specific parameters.
The rest of this paper is organized as follows. In Section we formalize the problem setup, which consists of the constrained stochastic optimization problem for fair machine learning, the local dif- ferential privacy mechanism for releasing sensitive attributes, the learning procedure of fair model using private sensitive attributes, and the definition of asymptotic relative efficiency in terms of fair- ness violations. In Section 3] we develop theory for the privacy cost under a single exact fairness constraint and then generalize this theory to some extent. By simulating risk-parity linear regres- sion problem Section 4 we validate our theory and illustrate the utility of our tools. Finally, we summarize work in Section and point out interesting avenue of future work.

---

Under review as a conference paper at ICLR 2023
1.1 RELATED WORK
The interaction between fairness and privacy has been investigated from three perspectives: learn- ing approximately fair models without sensitive attributes (Hashimoto al.] 2018: Lahoti et al. 2020), learning approximately fair models with wildly noisy sensitive attributes (Kallus et al. 2019 Awasthi et al. 2020 Wang et al. 20200, and learning exactly fair models with structured noisy sen- sitive attributes (Lamy et al. 2 Mozannar et al. 2020). This paper focuses on the third aspect.
The works that are most pertinent to ours are Lamy al. 2020) and Mozannar al. (2020) Lamy et al. (2020) assume that the sensitive attributes are subject to noise from the mutually contami- nated learning model. Under such a structured noise mechanism, the noise rates can be consistently estimated, and when enforcing fairness with regard to noisy groups, scaling the fairness tolerance parameter more tightly all that is required. |Moznnnar et al. (2020) suggest a differentially pri- vate model to release the sensitive attributes, which is special type of the mutually contaminated learning model. Under such a designed noise mechanism, Mozannar et al. (2020) show that if the classifier is independent of the sensitive attributes, then exact fairness with regard to noisy sensitive attributes is equivalent to that with regard to true sensitive attributes. The idea of the equivalence can be found in Lamy et al. (2020) while Mozannar et al. (2020) put it into formal statement.
We basically study the statistical cost of privacy on the generalizability of fairness when using Lamy et al. 20200's method under Mozannar al. (2020)'s privacy mechanism.
PROBLEM SETUP
2.1 FAIR MACHINE LEARNING CONSTRAINED STOCHASTIC OPTIMIZATION
In In-processing fair machine learning is typically supervised learning problem with faimesss con- straints (afar et al.] 2017; Agarwal et 2018). Such problem can most often be formulated as a constrained stochastic optimization problem: (empirical) risk minimization subject to (empirical) fairness constraints.
Consider a fair binary classification problem. Let X' C Rdd be the input space, y = =0, 1} be the set of possible labels, and A be the set of possible values of the protected/sensitive attribute. this setup, training and test examples are tuples of the form (X, A, E X x A x V and classifier is a map f X' - {0, 1). Two popular definitions of algorithmic fairness for binary classification are demographic parity (Dwork et al. 2011) and equality of opportunity (Hardt et al. 2016).
Definition 2.1 (Demographic parity). Let V -(X) be the output of the classifier. Demographic parity entails p = A = a) = p( = A= a'} for all a, a' E A.
Demographic parity, also known statistical parity, means that the prediction Ý f(X) is statis- tically independent of the protected attribute A.
Definition 2.2 (Equality of opportunity). Let Y = 1 be the advantaged label that is associated with a positive outcome and Y = f(X) be the output of the classifier. Equality of opportunity entails Y
P( - A = a, Y = 1} = P(Ý = A = a' a = 1 for for all a, a' E A.
Equality of opportunity, also known as true positive rate parity, means that the prediction f= = fX) conditioned on the advantaged label Y 1 is statistically independent of the protected attribute A.
Given a parametric model space H = {fo(-) : E θ) and loss function é x X x y + R+ (where θ C IRd is Enite-dimensional parameter space), an in-processing fair ML routine is to minimize the (empirical) risk IE [e(0; x, Y)] while satisfying some fairness constraints. To keep things simple, we assume there are only two demographic groups; i.e. |A] = 2. Without loss of generality, we refer to one group as advantaged (A = 1) and the other as disadvantaged (A = 0).
Consider fair learning with demographic parity as an example. At the population level, the goal to solve the problem:
arg mingen subject to B[1(,f((X)=
X[{(0;x,y)]
1)|A 1] - [[(((( = 1}14 = 11 } (2.1)
0- E
2

---

Under review as a conference paper at ICLR 2023
where the expectation is with respect to the distribution of tuple (X, The true underlying distribution is unknown, so we cannot solve (2.1) directly. Instead, we observe IID training samples {(X,, A,
Y)] 1= from the true distribution and solve the empirical version of 2.1
arg mingge
Σ i= ((0; X;,
,, E
(2.2)
subject to
-( 1(A=I
ET
[( 1[4,0)
S On
where 0 < On ol +a) )
is slackness term shrinking to zero at rate faster than 7
Through the
rest of the work, we always let an be positive number of order of +
2.2 LOCAL DIFFERENTIAL PRIVACY MECHANISM FOR RELEASING SENSITIVE ATTRIBUTES
Consider the randomized response mechanism privatized sensitive attribute:
(Waner
1965
Kairouz et al.
2014 for releasing
if a
Q = = = a)
A 1+
lte
(2.3)
if F
for all 0, E A. where > 0 controls the privacy level. The privatized sensitive attribute Z of defined as Z =Q A). In addition, the sampling mechanism Q requires % TL X, Y A. Then the private dataset {X,,, Zz, Y.) is generated from the original dataset {(X,, A., Y:) )== via the transition kernel Q.
the true sensitive attribute
The randomized response mechanism 2.3 is a locally g-differentially private mechanism (ucchi et al. 2013), that is
= = A=
max 2,0,0' E Q = A= <e.
Here smaller parameter & indicates a stronger privacy guarantee. Moreover, the mechanism Q considered optimal for distribution estimation under local differential privacy constraints (Kairouz
al. 2014 2016).
From this point forward (with the exception of the general theory presented in Section 3.1 we assume that there are only two demographic groups, i.e. |A| = 2. The mechanism
(.33 becomes
1-7 =
Q(Z = z A =
(2.4)
=
for f0, 1}. where 7 [0, 0.5). The parameter y 0 (or equivalently oo) signifies complete lack of privacy, whereas 7 + 0.5 (or equivalently E + 0) corresponds to perfect privacy.
2.3 FAIR MACHINE LEARNING WITH PRIVATE SENSITIVE ATTRIBUTES
The privatized sensitive attribute Z can be served as noisy proxy for the true sensitive attribute A. One may wish to learn a fair classifier by directly enforcing fairness notion on Z, 's the proxies for A,ss. This approach is feasible and justifiable (at the population level) due the invariance of exact fairness under local differential privacy.
Proposition 2.3 (Proposition 1 in Mozannar et al. (2020). Consider any exact fairness notion among demographic parity and equality of opportunity. Let Y = s(X) be binary classifier. Then Y is fair with respect to A if and only if Y is fair with respect to Z.
Proposition 2.3 requires ÿ is only function of X. Mozannar et al. (200)) shows by construction the existence of a classifier Y f(X, Z) which is fair with respect to Z but unfair to A.
Now we consider fair ML with private sensitive attributes by (empirical) risk minimization subject to fairesss constraints with respect to Z. Take fair learning with demographic parity as example. At the population level, the goal is to solve the problem
arg mingee subject
B[e(0;; Y))
E [[ 1)|2 1] -E [[((f(( 1}|2 = =0 - )
0" E
(2.5)
3

---

Under review as a conference paper at ICLR 2023
where the expectation is with respect to the distribution of tuple (X, Z. Here Z is the proxy sensitive attribute but the true sensitive attribute A is unobservable. The true underlying distribution is unknown, cannot solve (2.5) directly. Instead, observe IID (private) training samples from the true distribution and solve the empirical version of (2.5):
{(X,, Ze, y))
arg minseo
E i= X,,;X;,Y)) X,)
0n E
(2.6)
E.= ((fo(X))=1.
EL 1(6((.))1122)) E 1[2,=0}
subject to
Σi-1 112,11;
On
A direct corollary of Proposition 2.3 is that 2.1 and 2.5 have exactly the same solution 0* (as-
suming uniqueness of the solution). One also show that under regularity conditions both 8, and On. the solution (2.2) and to (2.6). are /nn-consistent for 0*, We wish to compare the estimating quality of nn and On. and quantify the quality difference in terms of the privacy level parameter ? (or é) and few other problem-specile parameters.
2.4 ASYMPTOTIC RELATIVE EFFICIENCY
In statistics, consistency and efficiency are popular notions to evaluate the performance estimators.
Definition 2.4 (Consistency). An estimator 9n is consistent for 9 if 3 lr as n + oc.
Suppose that we have two consistent estimators 0, and 0n. Both of them are reasonable, but which one should be preferred? To answer this question, we can employ the notion of efficiency, i.e. measuring how spread out about 6n (or 0,)) is the sampling distribution of the estimator. In light of this, we now adapt the concept of statistical efficiency to fair machine learning.
In fair MI., the most important metric evaluate the performance of a classifier is fairness violation. Let c: θ + RR. be the constraint function. For example, demographic parity constraint corresponds ({) 1}14 0]. Since the exact fairness notion entails classifier fe is fair if c(f) O, we define the (signed) fairness violation of 0 as c(f) itself.
(() IE (X)
A
Definition 2.5 (Efficiency terms of constraint violations). Suppose that we have two consistent estimators 8, and 8n satisfying
vπ(c((n)) -(00))00033- 4 N((,,0 and vT((c(0)) - -(00))) $ (0,,00
as T2 + DC We say that the estimator On is more efficient (in terms of constraint violations) than 0,. if 0² < G2. The asymptotic relative efficiency (ARE) of On to 0n is
ARE(O O..) - 0²
g2
In other words, the estimator 0, is more efficient than 8, if ARE(O,, 0.)) S
Another way examine the efficiency loss is to look at the asymptotic joint distribution of c(O,.) and c(0,.. Let p be the asymptotic correlation between c(θ,)) and c(O... The faimesss violations of the two estimators can be compared using the ratio of c(θm.) to c(θm), which converges in distribution to Cauchy random variable U:
3 c(0m) $ ~ po(u) γ (u - au= 32 with a pa c(0%)
π , V
Constraint violation inflates if we observe a value of the ratio (c(θ,)) / ((.) less than one. Assume 0, is more efficient than 0,, i.e. o² < x². Since lp| S 1, the median and mode of U, satisfies Ja| 1, which indicates high likelihood of constraint violation inflation. Precisely, the asymptotic probability of constraint violation inflation is
c(Om)) c((
1
σ pa 0 12
T po
lim IP 72 100
tan
+ tan
π
0 0²
2
In the rest of the paper, the asymptotic relative efficiency (ARE) is the key quantity of interest, which compares the asymptotic variances of two estimators by ARE lim (.)
4

---

Under review as a conference paper at ICLR 2023
3 PRIVACY COST IN FAIR MACHINE LEARNING
In this section, we wish to study ARE(On, On), the asymptotic relative efficiency (ARE) of 0n to on given by solving (2.6) and (..2). To this end, we extend the notion of demographie parity and equality of opportunity to a more general form: we say that is fair (with respect to A) if
=
Elg(0; x, Y) 0 ((XX, 0]
c
0.
(3.1)
E ( =
The fairness notion
3.1 is known as linear-freet ineaa--faactonal fairness constraint (Celis et al. 2021). Note
that demographic parity is special case of (3.1) if take g(0: Y) fo()
and h 1.
Besides, (3.1) becomes equality of opportunity if we take g(t: X, X) = ((f 1, = 1} and
h(X, Y) 1(Y = 1}. When 1, (3.1 degenerates linear fairness (see Appendix A
Let the marginal distribution of A and conditional distribution of (X, (),Y)& given be
[F(A = 0) - no, (X, 1) Qo:
P(A 1)=
(3.2)
Then the distribution of (X, A, uniquely identified by (.2). Moreover, ().Y) ~ Q
mixture of Qo and Qı weighted by ao and T1 Denote the marginal distribution of and
conditional distribution of (X, K Y) given Z by IP = k) = a (X, Y)IZ Qs for E (0, 1].
Enforcing faimess notion 3.1 with respect to Z is
a(0) - [g(0; X, 2)
E[g(0;X,Y)L 0
E [((,, Y)IZ = E(b(X,Y) = = 0.
By some algebra, we find that the proxy constraint function a(0) is equal to the true constraint function c(0) up to scaling factor: a(0) = Vhtaao (7, To, T1, mo, m1) c(0), where
(1 mom
mo momm
Uiraee (7, T1, Ma, m2)
{ + (1 m)) {(1 mo + m
as well mg A Eqa [4(X, Y)] and my A Eq, (xx Y) This also implies c(0) = and only a(0) 0, offering an alternative proof for Proposition 2.3 and extending Proposition 2.3 to linear- fractional fairness notions (3.
Now we are ready to show the privacy cost in Enear-fractions fairness let the true parameter 0', i.e. the solution to the population problem, be
3.1 aware learning. First,
arg mig
X[{(0;X,Y)]
0"
E [[g(0; X, +)/==1] X EI
(3.3)
subject to
=o
E[M(,Y)] =]
where the expectation with respect to the underlying distribution of tuple (X, Y). Then, let the estimator O, be the solution to the empirical problem given the true sensitive attribute,
arg mingge
1 E. e(0; X Y,)
0,, E
(0 EL SEL X. EE Y.
subject to
< an
Finally, let 8n be the solution to the empirical problem given the proxy sensitive attribute.
arg min subject to
1 Σn ((0;X,,
0, E
M 11 Di (11
< <an
SHH AXX;
We made the following technical assumptions the population problem
3.3
5

---

Under review as a conference paper at ICLR 2023
1. smoothness and concentration: E and are twice continuously differentiable with respect to 8, and XX Y) VE(Ø"; X, g : Vg(0"; : Y), h(X, Y) are Sau-saasn
2. uniqueness: the stochastic optimization problem with single expected value constraint (3.3)
has unique optimal primal-dual pair (0", X*) and 8* belongs to the interior of the compact set Q
3. positive definiteness: The Hessian of the Lagrangian evaluated (0*, X*) is positive definite.
The preceding assumptions are not the most general, but they are easy to interpret. The smoothness conditions l and with respect to 0, the concentration conditions of E(0"). g(0*) and h, and the uniqueness condition facilitate the use standard tools from asymptotic statistics to study the large sample properties of the constraint value. The positive definiteness condition postulates the Lagrangian of the equality constrained optimization problem is locally strongly convex at (*))
The main technical result characterizes the efficiency of 6n and 6,, (see proof in Appendix C
Theorem 3.1 (Privacy cost in linear-fractional fairness (3.1 -aware learning). Under the standing assumptions, let estimators 6, and 0,, be consistent for 0", then
vn(c(O,) -c(0 $ _N o²) and vn((c(0,) --(00)) 4 (0(,00
where
Varq,19 ; x)(X,
Varq, TI (I [x( Y)12
k
To (Bo [n(X, Y)))²
Varg. (0 ;x,0
X,Y) k)((X, Varg, (g(0): X,Y) - -Kh(X, (1(X
0²
trac
To (E [)(x
#1 (E (xXX
and
BQ. 100; X, X,Y Eq, (1x,Y) Y))
Eo, E0, (00,,00;X,,)) XY
Eq, 1(X, Y)]
The asymptotic relative efficiency (ARE) of on to 0n is
ARE(Or, 10 (7, Tomo garig(0": ;X; XY xh(X, Y) = 01/mo) mmm1 Varig(O"; X,Y) xh(X, Y)JA = 11/mi)
(3.4)
where
(1 27) 2 (ri +2)
((7,,1,
A
fyr + (1--)))2(11 7)rr + ) + {(1 7)r + 7 + (1-
Recall that demographic parity corresponds to h 1 and equality of opportunity corresponds to MXX, Y)- = 1(Y = 1}. In order to interpret (3.4p. we therefore take h(x, Y) = 1{E(X,)) Y)).
where E(XYY is event of and Y. Then the ARE (3.4) becomes
ARE(On, 0..) = (1 ()
() 0) Varig(O*; X, Y () Y), A=
Varlg(O*; X, () Y),
Note that the ARE is jointly determined by the level of privacy, ratio of marginal probabilities of the minor- ity and majority groups, and a ratio of their conditional variances. Theorem B.I demonstrates that the cost of privacy is the efficiency loss in terms of fairness viola- tions. For fixed ratios
1.0
4-1:1,6-1:1
1-1:9.-=1:11
4-1:99.
agymptoiic elatvve efticency (ANE)
0.8
4-1:1.0=2:3
4=1:9:1222:3
4-1:99.6-233
r1 A Y),(X,Y), 0) Y), =
401:1:0=3:2
4-1:0.6=3:2
0,
4-1:99.0-312
0.4
and
r2 x 4= > 0,
0.2
function (07, (1,71112) 12) is decreasing in 7. In the absence means no efficiency loss.
of privacy, (0,0 r1, r2)
0.1
0.2
0.3
0.4
0.5
Under perfect privacy, (0..5,, r2) = 0 indicates total loss of efficiency. Moreover, 0, is always more efficient than 0z because ARE(O,, 0m) < 1.
Figure 1: Asymptotic relative efficiency curve of for varying ri and r2-

---

Under review as a conference paper at ICLR 2023
Figure demonstrates the asymptotic relative efficiency (ARE) curve of privacy level for varying ratios "1 and 72. The ARE is always upper bounded by (1 -2y)², which achieved only if = 1. Therefore for any fixed Y and r2, the ARE achieves its maximum only if the dataset is balanced in the sense that P(E(X, (X, Y), A = 0) = ( V), A = 1). Moreover, for any fixed y and r2. the ARE is strictly increasing in ii (assuming
Σ 1). This implies the effect of subpopulation size imbalance: demographic group imbalance degrades the efficiency loss in privately fair learning. In the literature, the effect of group size imbalance on the difficulty of learning fair classifier from contaminated data (note that private sensitive attribute is particular type of data contamination) was also reported in Konnstanntinov Lampert (2022) and the references therein. Lastly, the ARE is strictly increasing in the problem-specific parameter r2, given fixed yy and < 1.
3.1 GENERAL THEORY
In this subsection, discuss some extensions to the established theory.
Multiple demographic groups. It is natural to extend our theory of two demographic groups to general number of groups. Suppose we have K + 1(K 2 2) groups indexed by 0, l,.... K. The notion of linear-fractional fairness (3.1) can be adapted to more than two groups: we say 0 is fair if
E [o((: X, Y)J4 k]
E[g(e:X,))JA= 0] =0 for E [K],
(3.5)
E[ = k]
E[M(XY))AA
where group 0 is referred to as reference group. Let the marginal distribution of A and conditional distribution of (X, Y) given be
P(A k) = The (X, Y) 1~~ Qs for & E {0) U [K].
(3.6)
Then the distribution of A, uniquely identified by
3.6 Moreover, the distribution of (C,Y~~E* E Qx Q. a mixture of Qs's weighted by TT's..
Let the private mechanism Q be
K+e2 Ky
é'' A 11-Ky
if
Q(Z = -
2
if +
K+ee
where 7 E ( The mechanism Q perturbs the membership of a group to a different group
that is evenly picked random from the other groups The parameter 7 0 (or equivalently & oo) signifies complete lack of privacy, whereas - K-I (or equivalently E + 0) means perfect privacy.
The joint distribution of (X, Z) is uniquely identified by the marginal distribution and conditional distribution as follows:
IPZ k)) 7 + (1 AAl)TT n
for k E {0) U [K]. (3.7)
(X,Y) y+(1 11 Q+ + 7+(1-
A-1 Q: A
Q
Let the true parameter 6*, i.e. the solution to the population problem, be
arg miggee
K
0* E
E [[ X, =
=
E[g(0: X,Y 0] B[A(X, Y 0
subject to
E E(((X,Y)
k=1
where the expectation is with respect to the underlying distribution of tuple (X, Y)
Then, let the estimator O,, be the solution to empirical problem given the true sensitive attribute,
arg mingee
1 Σi 1 E(O; X1, Yi) NO:X..N.IIA
On E
subject to
EN 1000 E. ((
K S ann
k=1
7

---

Under review as a conference paper at ICLR 2023
Finally, let 8, be the solution to the empirical problem given the proxy sensitive attribute,
arg mingee
E i== ((0:X;; Yi)
0n
(1)1X, Lim1 (2
subject to
- On k=1
The true fairness constraint function c(0) RR. l R is defined as
E g(( X, Y)(A= k]
E|,(0;X, E (
c(() cx (0)) with (0)
, E [K].
E Y)
Under the same assumptions as the two-group problem, we have the main technical result as follows (see Appendix for a complete treatment to the general-numberrof-groo problem).
Theorem 3.2 (Privacy cost in linear-fractional fairness (3.5) -aware learning). Under the standing
assumptions, let estimators 6, and 6, be consistent for 8", then
v - c(0r) 3 E) and vn(c((m)) - c(0 4 NO, Wirli EV D
where
Varqulo(00 X,Y) xx(X, To (B2, (M(X,
+ (Varoula(0r; ;x,,, x((X,
Ent
1 =--=0
(Bq, [1(X, ())2
Var 1g(;;; X, X,Y) khi(X, YY]
Vars, (0 ;X,Y) xh((X,1]
Est
1 1 1
(B 3 11XX, Y))2
Th (B (6XXY)]1
for k, E [K], and
lo 00; X. XYY Eo, [b,X, Y)]
Eo ; X,Y)] Eq, (i(X,
EQR [g ; XY Eox [h(X, Y)]
Missing sensitive attributes. Some users may choose not to disclose their demographic identities during data collection due to privacy concerns. We investigate how the absence of sensitive attributes impacts the generalizability of fairnsss constraints. Consider the following missing data mechanism for sensitive attributes:
P = P(R= - WA.
(3.8)
where R 1 corresponds response (i.e., is observed) and otherwise R = 0 corresponds to non-response (i.e., missing). The missingness mechanism (3.8) is particular type of missing random (MAR) at the population level and missing completely at random (MCAR) within each subpopulation. One common approach for analyzing data with missing values is to just use the completely observed samples (i.e., samples with all features observed) and discard the samples with some missing features. We employ this strategy by solving the following empirical problem:
arg minnge
(1, Y2)
0.. E
E XIX (IA E. M.I.A.A
subject to
S On
of which the empirical risk function computed with all samples while the fairness constraint function is calculated with samples that include the sensitive attribute. With the same assumptions as the two-group problem and further assuming that the response probability non-vanishing, i.e.,
wa > 0 for a E (0. 1), we have the asymptotic relative efficiency (ARE) of 6,, to 9, as follows (see Appendix E for a complete treatment the missing sensitive attributes problem):
ARE((O,, win r2 + wi
r2 +
To
Varlg(O*; X, Y) xh(X, Y)J4 = 0)/ma
m
.2
Varlg(0*; X,Y xh(X, Y)JA 11/m;
This indicates that any probability of missing data degrades the asymptotic efficiency of the estima- tor inversely proportionally.
8

---

Under review as a conference paper at ICLR 2023
4 SIMULATIONS
We simulate the asymptotic relative efficiency (ARE) for the risk-parity linear regression problem:
minsee subject to [[ 3 - BY
E (Y - 3Y--B-X
(4.1)
=
where we generate n E (300, 3000) samples by the following data generating process:
A ~ Bernoulli(1 no); X a (M Σ.) and Y|X, A A - x.
for a E {0, We pick μi0 = (1, -11 = - 12
and investigate
two scenarios: imbalanced subgroups with To 0.3 and balanced subgroups with To 0.5. The goal of the optimization problem (4.1) is to minimize the population risk (in least square) while satisfying the parity of subpopulation risks (in least square) of group A = 0 and group A 1.
In Figure 2 we plot relative efficiency curves for To = 0.3 and To = 0.5, all of which are averaged over 500 replicates. For large sample size n, the relative efficiency curves are close to the theoretical line of asymptotic relative efficiency curve, validating our theory in the large sample regime. As a by-product, our theory can visualize the fairness-privant trade-off without retraining models with varying privacy budgets.
sumppl
5xm2p 10
6:5
AMC
AAE
0:35
0:5
0.0
0.34
Figure 2: Relative efficiency curves for To = 0.3 (left) and mo 0.5 (right).
SUMMARY AND DISCUSSION
In this work, study the statistical impact of privacy on fairness under the task of learning fair machine learning models with private sensitive attributes. We define a restricted notion of asymptotic statistical efficiency in order to examine such impact. Quantitatively, the cost of privacy on fairness generalizability is represented by relative decline in statistical efficiency. The relative efficiency loss is interpretable: it explicitly depends on the privacy budget, subpopulation imbalance level, and a number of other problem- -epssciiiiicccccccceeeeeeeeeeeee quantities. We validate and demonstrate the utility of our theory by a synthetic task of risk-pant fiskitarity linear regression with private group membership.
For the sake of clarity, we consider h = 1. Denote the loss vectors with regard to the true sensitive attribute A and the noisy sensitive attribute Z, and the Markov transition matrix induced by the privacy mechanism Q (2.4) by
TP. O0; X, A =
IE X0 = 3] Lz(0)
Te. (0; X,I
E3 (0; = = and M M 1--7
--,]
(0)
Further, let b (1,-1)7 Noiseless, noisy, and debiased constraints are equivalent to each other the population level in the way that b (0) = - lzz(() = < b b 0. Consider their empirical counterparts, we note that 6 (0) Combined with our theory, this empirical level equivalence of two constraints implies that using the inverse of the empirical transition matrix to match the noisy constraint to the noiseless constraint cannot improve the efficiency of the in processing training procedure. Developing a principled in- processing method to increase the statistical efficiency is intriguing direction for future research.
- b 3TM-17 (0,,00
0.

---

Under review as a conference paper at ICLR 2023
REFERENCES
Alekh Agarwal, Alina Beygelzimer, Miroslav Dudík, John Langford, and Hanna Wallach, Re- ductions Approach to Fair Classification. arXiv:1803.0243 [cs], July 2018.
Pranjal Awasthi, Matthäus Kleindessner, and Jamie Morgenstemn. Equalized odds postprocessing under imperfect group information. a9Xiv 0928943060084441 [cs, stat], March 2020.
L Elisa Celis, Lingxiao Huang, Vijay Keswani, and Nisheeth K Vishnoi. Fair classification with noisy protected attributes: A framework with provable guarantees. In International Conference on Machine Learning, pp. 1349-1361. PMLR, 2021.
Jiahao Chen, Nathan Kallus, Xiaojie Mao, Geoffry Svacha, and Madeleine Udell. Fairness Under Unawareness: Assessing Disparity When Protected Class Unobserved. Proceedings of the Conference on Fairness, Accountability, and Transparency FAT '19, pp. 339-348, 2019, doi:
N0.1145/3287560.22875555
John C Duchi, Michael Jordan, and Martin J Wainwright. Local privacy and statistical minimax rates. In 2013 IEEE 54th Annual Symposium on Foundations of Computer Science, pp. 438. IEEE, 2013.
Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise to sensitivity in private data analysis. In Theory of cryptography conference, pp. 265-284. Springer, 2006.
Cynthia Dwork, Moritz Hardt, Toniann Pitassi, Omer Reingold, and Rich Zemel. Fairness Through Awareness. 1w0.vv1104.391 [cs], April 2011.
Moritz Hardt, Eric Price, and Nathan Srebro. Equality of Opportunity in Supervised Learning. arXiv:1610.02413 [cs], October 2016.
Tatsunori B. Hashimoto, Megha Srivastava, Hongseok Namkoong, and Percy Liang. Fairness With- out Demographics in Repeated Loss Minimization. arXiv: arXiv:1806.08000 08010 [cs, stat), June 2018.
Peter Kairouz, Sewoong Oh, and Pramod Viswanath. Extremal mechanisms for local differential privacy. Advances in neural information processing systems, 27, 2014.
Peter Kairouz, Sewoong Oh, and Pramod Viswanath. Extremal mechanisms for local differential privacy. The Journal of Machine Learning Research, 17(1):422-542, 2016.
Nathan Kallus, Xiaojie Mao, and Angela Zhou Assessing Algorithmic Fairness with Unobserved Protected Class Using Data Combination. arXiv:1906.0028: [cs, math, stat), June 2019.
Nikola Konstantinov and Christoph H Lampert. On the impossibility of fairness-aware learning from corrupted data. In Algorithmic Fairness through the Lens of Causality and Robustness workshop, pp. 59-83. PMLR, 2022.
Preethi Lahoti, Alex Beutel, Jilin Chen, Kang Lee, Flavien Prost, Nithum Thain, Xuezhi Wang, and Ed Chi. Fairness without demographies through adversarially reweighted learning. Advances in neural information processing systems, 33:728-740, 2020.
Alexandre Louis Lamy, Ziyuam Zhong, Aditya Krishna Menon, and Nakul Verma. Noise-tolerant fair classification. veXiv:/901. 10837 [es, stat), January 2020.
Hussein Mozannar, Mesrob I. Ohannessian, and Nathan Srebro. Fair Learning with Private Demo- graphic Data. arXiv:2002.1 1651 [cs, stat), February 2020.
Reuven Y Rubinstein and Alexander Shapiro. Discrete event systems: Sensitivity analysis and stochastic optimization by the score function method, volume 13. Wiley, 1993.
Serena Wang, Wenshuo Guo, Harikrishna Narasimhan, Andrew Cotter, Maya Gupta, and Michael Jordan. Robust Optimization for Fairness with Noisy Protected Groups. Advances in Neural Information Processing Systems, 33:5190-5203, 2020.
Stanley L Warner. Randomized response: A survey technique for eliminating evasive answer bias. Journal of the American Statistical Association, 603309):63-69, 1965.
10

---

Under review as a conference paper at ICLR 2023
Muhammad Bilal Zafar, Isabel Valera, Manuel Gomez Rodriguez, and Krishna P. Gummadi. Fair- ness Beyond Disparate Treatment & Disparate Impact: Learning Classification without Disparate Mistreatment. In Proceedings of the 26th International Conference World Wide Web, WWW '17, pp. 1171-11 180, Perth, Australia, April 2017. International World Wide Web Conferences Steering Committee. ISBN 978-1 978-1-4503-4913-00 doi: 10. 10.1 145/3038912.305222
A LINEAR FAIRNESS CONSTRAINT
We extend the notion of demographic parity to a more general form: we say that is fair (with respect A) if
E [o( (0)xX) - Y =
(A.1)
The fairness notion A. known linear fairness constraint [elis al. (2021). Note that demo- graphic parity is a special case of (A.I if we take g(0; X, Y) = (X) = 1}.
On the one hand, enforeing fairness notion (A.1 with respect is
(x(x)) Y)]
B(x, (9 [X Y)] 0
or equivalently
Eq, [0(0: X, Eqo [g(: 0: X, Y)] = 0.
On the other hand, enforcing fairness notion A.. with respect to Z is
E, |xx,r]j==1 X,Y)
Exx,y] g X,; Y) 0
or equivalently
E
770
(->)m Qo (10+(11117
Q x,)0 E
(1-7)mg 11-3
2 Qo (1-1
Qi (9(0;x, 0.
Therefore, the true faimess constraint function is
- Jxxy o(ex,,)d((1--u))x:.))
c(0)
while the proxy fairness constraint function is
7
(1-7)mo
(1 (1-17 7)
/ Xxx g(0:0, - (z,
[(0) =
7n + - 7)-
(1 - 7) + 7T12
(1 - -7)=1
7
g(0:2
v) -o) v)
(A.2)
YTo + (1 7)
(1 - 7) t
xxY
uhin To, TI) c(0).
By A.2h. the proxy constraint function ē(0) is equal to the true c(0) up to scaling factor
Viin (7,7TO, no, mI) A
ToT
+ (1 (1-7) 7)
7To (1 7)
(1-7)mm mo 7
(1 7)
7/71
(A.3)
TToo + - (1-7)
(1 (1- -T->))T-- + +
(1 27)
(T + (1 - 7) } {(1 - 7o + }
This also implies c(0) 0 if and only if E(0) providing an alternative proof for Proposition 2.3
Now are ready to show the privacy cost linear fairness
A.I aware learning. First, let the true
parameter 8*, i.e. the solution to the population problem, be
arg min subject to
{[{(0; Y)] = - =0
of
(A.4)
where the expectation is with respect to the underlying distribution of tuple (X, A.Y)
11

---

Under review as a conference paper at ICLR 2023
Then, let the estimator 8n be the solution to the empirical problem given the true sensitive attribute, arg mingge subject to
1 Σ e(0; X2,
On
(1 EE g00:A.,.14 EL [(A=D))
1(A==))
S On
Finally, let the estimator 0n be the solution the empirical problem given the proxy sensitive tribute,
arg minggo
ΣE X(,; N 1 EiS 1(2
02 E
subject to
E
(0 1[7 0)
an
We made the following technical assumptions on the problem A.4
smoothness and concentration: é and g are twice continuously differentiable with respect to 0, and ((0";,, Y), ve(0"; X, Y), 9 X, Y), Vg(0"; X, Y are sub-Gaussian random variables. uniqueness: the stochastic optimization problem with a single expected value constraint (A.4) has a unique optimal primal-dur pair (0*, X*), and 0 belongs to the interior of the compact set O
3. positive definiteness: The Hessian of the Lagrangian evaluated at (0)
) is positive definite.
We have the main technical result as follows.
Theorem A.1 (Privacy cost in linear fairness A..I-aware -aware learning). Under the standing assump- tions, let estimators On and On be consistent for 0*, then
va(c((m)) - -00 3 (N(0,0²) and vn((((n) c(0 $ NN(0
where
o² Varqula(0"; X, XYY]
Varq, Ig(;;; X, Y)]
To
and
Var [9(0"; X, Y)) Var 1o(0"; X, Y)
62 = =/?
x
The asymptotic relative efficiency (ARE) of 0n On is ARE(O,, 0m) s0 (7, To Varlg(O*; X, )
T1 Varlg(O Y) = 11
where
(1 2x) (r +
p(7,)1,72) A
{yr + (1 +11-++11)1111) 7))2 - 7)rr2 + +} + {(1 - 7)r + 22 + (1-
Proof of Theorem A. Note that Theorem 3.1 implies Theorem A. by letting ((X, Y)
There-
fore, it is sufficient prove Theorem 3.1 whose proof can be found in Appendix C
Theorem A.I demonstrates that the cost of privacy is the efficiency loss in terms of fairness viola- tions. For fixed ratios F1 è no/T1 > 0 and r2 å Varlg(O*; X, XXYYY)L |) = 0]/ Varlg Y = 1] 0, Plin (7, r1, r2) is a decreasing function in y. In the absence of privacy, Plin (0, 72, means no efficiency loss. Under perfect privacy, PPim (0.5, r1, r2) = 0 indicates total loss of effi- ciency. Moreover, 0, is always more efficient than 0,, because ARE(On, 0..) 1.
Figure 3 demonstrates the asymptotic relative efficiency (ARE) curve of privacy level y for varying ratios and r2. The ARE is always upper bounded by (1 - 2y)² which is achieved only if mn π 0.5. Recall that m = (PA 0) and I = (AA = 1). Therefore for any fixed 7 and r2, the ARE achieves its maximum only if the dataset is balanced in the sensitive attribute A. Moreover, for any fixed y and r2, the ARE is strictly increasing in To (assuming To < 0.5). This implies the effect of subgroup size imbalance: demographic group imbalance degrades the efficiency loss in privately fair learning. Lastly, the ARE is strictly increasing in the mobleem-spciine parameter r2, given fixed y and ri < 1.
12

---

Under review as a conference paper at ICLR 2023
ma 1: Var1 1:1
fl: = 1: Varo Varı = 1:1
1 99, Var. :arn =1:1
asymptatic relative efficiency (ARE)
0.8
no m = 1, Varo 2a:
Nl ft 9. Var Var1 22:3
No m
Var Vari
Ne Rt 1: Varo Vary= =3:
0.6
No m 1: Var Var, = 3:2
No m 1:99, Varo Var 3:2
0.2
0.0
0.0
0.1
0.2
0.3
0.4
0.5
Figure 3: Asymptotic relative efficiency curve of y for varying ratios of To T and
Var[g(O"; x, Y)A = 0] to
B LINEAR-FRACTIONAL FAIRNESS CONSTRAINT
We provide further discussion supplement Section ditional distributions in (3.2) and
Recall the marginal distributions and con-
PlZ = 0) To.
P(Z = 1) = म1
(X,Y) Qo.
(X Q1
Under the private mechanism Q 2.4p. we have
m (1 - 7 )Tp 1 11 = 7 + (1 7)
d (1 7
Q0 (1-2)=0 + Qo + [1 (1-2)xo+7m) Q1
(B.1)
Q 71 マ)=) Qo +
(1 (1-4)m1 Q1
The marginal distribution and conditional distribution [B.l uniquely identify the joint distribution of (X, Z, Y).
On the one hand, enforcing fairness notion
3.1 with respect to A is
Ex.Y [9(0: X, Y)
Ex [000
E 1 [xx,
(x [hxX, Y)]
or equivalently
<()) A Eq, [g; X,Y)
Equ [9(0; X, Y) Eq. 1(X, Y) = 0.
Eq. 1( Y)]
On the other hand, enforcing fairness notion
3.1
with respect to Z is
E Exx.r ( X,
Exxrr ((; X)] Exx 11( X Y)]
E. Ex 1/ X,
equivalently
Yoo (9; X, Y)] + (1 7) Eo, [g(0; X, X,)
1..l [1(X,, Y)] + (1 - 7)= Eg, [))
Z(0) A
0.
(1 (1-7)mobB Eo [g(0: X, Y)]
+ + Eq, [g(0: X, X.Y)
(1 7) EQ h/ X, Y)]
E [h( Y)]
13

---

Under review as a conference paper at ICLR 2023
By some algebra, we find that the proxy constraint function a(0) is equal to the true constraint function c(O) up to a scaling factor: a(d) = Virac (7, To, T1, mo, m1) c(0), where
(1 2y) 1
Vitrao To, RI, mo; mi)
(B.2)
(ympri + (1 - m) {(1 - momm + 7
as well mg
Eqo [b] and A Eq, [)]
By comparing the scaling factor [.2)) with the functional form of A.3 we can rewrite (htrac()) by
Virac (7: Fu, #1, mo, mi) = (7an momo Tim1).
Therefore, interpret the scaling factor eltrac() (-) by treating Tomo and mi whole, allowing us to understand the privacy cost from a different perspective. Note that for equality of
opportunity, have mmmaa (A PY 1|A a) P(Y 1, A a) for {0, 1).
For equality of opportunity,Not Mozannar et al. (2020) show sample complexity bound for the fairness violation of the estimator i,;
c(Om) - -00 C1(1-7) CC2 CC2+ (F) + (1 27)
C₁
(B.3)
Vnóp
with probability least 6, where p = min (P(Y 1, 0). P(Y 1, R.))) the Rademacher complexity, and Cp's (1 S i 4) are some universal constants. Not precisely, the upper bound (B.3) reflects the effect of privacy level via y and the effect of dataset imbalance through p. Comparing to this, theory states that
1)},
Varlc(O,.) c(A7)
Var(c(O..) c(AM) = 4p (1 P(Y = 1, -
P(Y 1, = 0)
lim
100
which is depicted by Figure
1.0
MoMo n.m; = 1::1
Mome n.m; 1:9
Mo/o ntm; 1::9
asymptotic relative efficiency (ARE)
0.4
0.0
0.0
0.1
0.2
0.3
0.4
0.5
Figure 4: Asymptotic relative efficiency curve of y for varying ratio of PPYY = 1, = 0) to
P(Y 11A=1.
C PROOF OF THEOREM 3.1
First, we prove the case when a, = for all n. For this case both the population problem and the empirical problem subject equality constraints.
14

---

Under review as a conference paper at ICLR 2023
Consider stochastic optimization problem with finear-fraction constraint
arg mingee subject to (Po) 0*
E [[e(0: X))
g( (11 Y)
E g x, X) (
E [[
where the expectation with respect to the underlying distribution of tuple (X, AY. The corresponding empirical problem given the true sensitive attribute is
arg minlage
E(0; X1, Yi)
(Pn): On E
g(0; X Y)) MX,, [ 11
subject to
Σ h(X,, [;)
The corresponding empirical problem given the proxy sensitive attribute is
arg millage
E(0; Xi, Yi)
(Pn): On E
12
g(0; Xi, 12)1 =1 E 90, K) 0
subject to
1(X, = 1(x; K,)({Z =0
We denote
= E[g(0; X)JAA=11 E[g(8:X,
Σ
F(0) =
E[I(X, B[M(X, ()JA=
and
(0) E 00; X, Y2) (A; =1
E K(,
Σ N(X,, (AA =1 E h (A)
Note that (-) and G.)s's are random functions serving approximations F(-) and G(-)'s. Consider the Lagrangian functions
A) F(0) + AG and = Fo) +G
of the programs (Po) and (Px) respectively.
Lemma C.1 (A version of Theorem 6.6.2 in Rubinstein & Shapiro (1933) Suppose that:
(i) The functions F(0) and G(O) are twice continuously differentiable.
(i) The true program (Po) has unique optimal solution 9 and unique Lagrange multiplier X with 6* being an interior point of θ.
(ii)) The Hessian matrix 22L(0* X*) is positive definite.
(iv) The random functions G ( [K], are Lipschitz continuous in neighborhood of 6* and
differentiable 6* with probability I.
(v)
A 112 (1- i i= 1,2,3
and there is a neighborhood U of t* such that
A (0) A (8* 112
sup BEU
(p()), i= 1,2,.
1/2
1|0 8+ 10112
Here define random mappings (1n (F, VF (2) = G.) G(Ø), and As, (0) VG. (f) VG(A).
(vi) Random vectors /nl (f, (f*)) converge in distribution to = -Y,, as n Do, where Y1 is random vector and Yg is random variable.
15

---

Under review as a conference paper at ICLR 2023
Let On be an optimal solution of (Pn)) converging in probability - 0o to 8". Then
vn - --) - xY)
where I- =YY) is the optimal solution to the quadratic programming problem
minimize subject to VG(0*) x Y2 =
x: Y 5 (=T'0",'')
Recall the standing assumptions, (i), (iv), (v) are guaranteed by the smoothness and concentration assumption, (ii) is postulated by the uniqueness assumption, and (iii) is made by our assumption.
Now we derive the limiting distribution of random vectors /n( V >²), G. (0*)) required in (vi).
For {0,1), 1,. we have
E XX IP =)) = T..5o.99
and
= -1
( =}}}
TTLLQ. - -
Na (EQ, |09) (Eq. [g]) + (Ta - x0- (BQ.
=Ta Varq. [g] + T (Ee, [g])
Similarly, for a E {0, 1}, have
[[M(X, ()1(A = a}] = T. 1..1 and
= To Varq. (Eq.
Moreover, have
x, 1t10::/KAAAAAAA.,00000011111-111
NOtI TO. Eq, [9]
and similarly we can derive
CortHKX_))J1//-1,,xx011111-----1 = - Bqu [1] [h] a}) Ta Cov 1g, hl गo Eq, (g Eq. [h]
and
; Xx);) - = a))) - Eq, [g] B2, [4]
a E 10.
Let m ; Y) 772 -E [g(0"; and 77 TBEQo vg(0r;X,))) By central limit theorem,
Ve(0";X,,)))
Vg00:X;,Y)1(AA==1
np
n
X,
ns
(0.
[2n
P12
Vn
n
Tt Eqq [g]
N
U2i
122
X;
To Ee [g]
क IQq
h
n
h(X,,)))((L
(C.1)
where Qn E Raadx3d 921 E RA33d Ω12 = 22 S2z is given by
Ti TiQl + क (2 T QogQ1g
- QogQ To Qigl | + no (Qug)² To Q
m Qigg hi + गo QigQih
TT QohQig To To h) + no + QugQph
m Q ToTT Q कoक (Q1h)² - -oo Qhh
T h1 To Q19hh
- 1h To Q8[h + noक (Qoh)²
- Qoh
m h]] To QogQoh
16

---

Under review as a conference paper at ICLR 2023
Let function R x R
R
R
R
R
Rd+1 be
122
03
81
82
w(vi, v1, U2 Vg $1 $2 S3. S1)
U1 + X
$3
31
33
$4
The gradient of function evaluated at (V1, 22 03) = (71 72. 175)
and
(s1, $2, $2, s1) = ( Bq, [g), To To [g), TT Bq, [b] To [h])
given by
#3dxd
03dx1
I2 (333444)((4+1)
VW
#4xd
{4x1
where
1
1
Q1g
Qog
1 Q
To Qoh"
hQih)²
(Q)))
Applying delta method to (C.I) with w()), we have
vn (0+,(0));)) (0+)
$ W
0. Tw
Q11
1211
S222
12
Vw
d
N
0,
Σn
E21
E1z
o²
where
(Qog)
2Q 1|Qu9
a² = ET
To (Quh3
To(Qh))+
(Qoh3
(C.2)
Qigg
209 h|19 (Q19)
(Q1h)3
m (Q1h)
Note that KKT condition implies
772
713
Qig
Qog &
and
(C.3)
Ti Qıg
To Qo9
Q1h
Quh
Combining (C.2) and C.3
we have
Varqol9) + Varq. [wh] 2 Covoolo. lo, Varq, [o] + Varq, [sh]] 2 Co
To (EQo [h])
T
(EQ,
(C.4)
Varq, kh] To [h]]²
Varq, [g nh]
Therefore, we conclude that the limiting distribution of (L, (0*, (OT) is
(2) ~ 00
En
E
En o²
By Lemma C.I, we have
Vn(0,. - 00) ب x.
where z is given by the linear system
VG(OM)
Yi
0,
En
En
)
VG(BN)
0
À
Y2
N
Ee
o²
AB
or
T
Σ1
_
N
0.
B-1
Σ21
0²
(C.5)
which implies On, 0*)
No, Σ) for some j and Σ, determined by
C.5
17

---

Under review as a conference paper at ICLR 2023
By delta method, we have
- G( -
N(O VG(0*) EVG
Now we calculate (C(OO)TEVG("""
For notation simplicity, we denote L = V2L10", X*), VG VG(00) and H (PPL)-VG[VVG' ( (V | By block matrix inversion, have
B (V21)-11 HVG HVGT(V=
H
v (VD1)-1G)-11
Note that VG H = and VG (VV
0. We have
VG(00) T (0)
=VG [[(V-L)---VCC IVG (VV شل + |111 (V-) VG
+ VG ((v2L)-1 HVG E H H
=0?
Therefore, we conclude that
vrlc((n) c(00) = v)G((n)
$ SN(0,07 _N (((0
Varqu [g - kh)
Varq, [g - kihl
xa TE [2])2
#1 (E [T]]
By similar argument, we have
Vntvinae x c(On) d'une x c() 4 N (0.
No (IE [1/])2 (0.
Var lg - kh]
Var 1g kct]] म. (EE [h]]2
which implies
Varg 69 kh] To (E [h])
Var [g - kh]
का (Bg, [h])2 })
x xnxc(0m) 4 N(1,0 1 N 0, Viaac x
Now, we prove the case when an of v For this case note that the equality constraint for the population problem can be rewritten as two inequality constraints:
arg mingge
[[[(0; Y)]
E [[g(O; X,, Y) =
E (Y)
(Po): f+ E subject
5O
E [XX, (||==
E {X, (XXXXY)A==0)
E (0; Y)AA=
IE YY)AA
<0
E Y)A=
E [X Y)JA=
where the expectation is with respect to the underlying distribution of tuple (X, A, Y). The corresponding empirical problem given the true sensitive attribute is
arg mingee
8(0 Yi)
(Pa): 0₂ E subject to
g(O; X. 1)1(A;11)
E
On 50
1(X,, []][A,=1]
Σ M(X,, Y,){(A, =
g(0: X2, (;)
E Y,)144,
Σ 1(X,, Y,)1(A; an 50
h(X,, Y)1(A, =
18

---

Under review as a conference paper at ICLR 2023
The corresponding empirical problem given the proxy sensitive attribute is
arg millage
E(0; Yi)
(Pa): 0n E
g(0; X,, [1]1[2;=1] E Y;)122,, 0n SO
subject to
1=1 h(,,, (2) =1
E h(x;, [,)1(2==]]
g(0; X [2,
Ex= g(0; X,, ())1[2;
h(X;, X:)1[2;-11 50
1 h(X,, ())[Z, = 0}
We denote
F(0) B[e(0; X,, Y) (0) 1 Σ (00; Y.)
(0
([ Elo(::X,))A=11
O]
E[g(0;XX))]A== 0
(2
Y[b(X,
B[h(X,
Σ "
i= 8(0; X,, (1) =1
Em=9(0; X,, ())
(0)
h(X,, 1)) =
E ()) =
On
and
(0) i= g(0; X, 1)) =0}
E -0 f)) =
Σ h(X,, Y) 1(4
EL h(X,, 1, =1
Consider the Lagrangian functions
L(O, A) = F(0) + A1G1(0) + (0) and =x = of the programs (Pu) and (Px) respectively.
+ A Gn (0) + 22)
Lemma C.2 (A version of Theorem 6.6.2 in Rubinstein & Shapiro (993)),
Suppose that:
(i) The functions F()), (f) and G2( are twice continuously differentiable.
(i) The true program (Po) has unique optimal solution 6* and a unique Lagrange multiplier X* with 6 being an interior point O.
(ii) The Hessian matrix L( X²) is positive definite.
(iv) The random functions Gl) and Gzn (0),k [K], are Lipschitz continuous in a neighbor- hood of 6* and differentiable at 6* with probability 1.
(v)
An (0") = 0p 112), i= 1,2233
and there is a neighhorhood U of 6* such that
in (0) (0 1|2
sup BEU
n 1/2 + 1 1+112 Op()), i= 1,,233
Here we define random mappings AIn vF. VF(O), (0) G. G(Ø), and (0) Vद, (0) ((().
(vi) Random vectors V (V, (0* X²), G)n()))), (z)( converge in distribution to Y (Y,, Y2, Y2) as n + oo, where Y1 is a random vector and Y2 and Y2 are random variables.
Let On be an optimal solution of (P.) converging in probability as + oo to 0*, Then Vn(O,. - -0- - oYY)
-
where & =YYY is the optimal solution the quadratic programming problem
minimize
x: Y + ": T >t
subject to
(O') x + Y2 < 0
(G² x + Y3 5
19

---

Under review as a conference paper at ICLR 2023
Note that
VGI x+ = VG(0") +
and
52 - +
Therefore the last quadratic programming problem with inequality constraints reduces to the quadratic programming problem with single equality constraint when on = 0. The limiting distri- butional results thus persist as we proved for the a₂ case.
Lastly, we calculate the asymptotic relative efficiency (ARE) of On to mn.
Recall that
a² Varqo l9 kh]]
+ Varq, bg k/]]
To (oQ [h])2
T1 (EQ, [h]]2
Var 3o [g - kih]
Tol (Bq. [h])2 + Var [g kh)
0² Virac x
11 (Ex [h])
7) Varqo (g kh] + y Varq, ki))
Virac x
((1 - 7 [h] + TTTE [h]]
YTo Varq, 10 xh] (1 7 Varq, [g kh)
{T [b] + 7) 12 [1
and
(1 - 27) wo I Eqg [h] [h]
Frac
m7 Reo [1] + (1 m) Ro, [b]] {(1 Bo (h) y Eeq, [h]]
Therefore, have
σ² 02
?, To [h] Varq, : X,Y) (Y) /EE
ARF(OO, 0m)
=
क Eq, [
Vare, I9(0"; X,Y) xx(XX))))
Tomo Varlg(A'; X, X,Y) -))(X 01/mo
40
n mim Varlg(O*; ;1,,((0xx,)))) =k((X, = 11/m1
where
(1 21
p(7)11,12) {y + (1) {(1 (11-7)1 7)r + (10mir2+(11100)
Hence we complete the proof of Theorem 3.1
D MULTIPLE DEMOGRAPHIC GROUPS
We provide further discussion to supplement Section 3.1
Note that the fairness notion 3.5) uses group 0 as reference group. One can also define a fairness notion by
(0; k
E [[g(0; 0 for k E (0) [K]
(D.1)
E Y),
E(((X
which is symmetric in group indices. Due to the equivalence of D.1 and 3.5 for comparison with two-group theory.
we opt to use
3.5
Theorem is a direct extension of Theorem 3.1 and follows the same proof procedure as of Theo- faimess (3.5) degenerates into linear fairness:
rem 3.1 Moreover, let h the
E [[g((: X, Y Re] E[g(O: X, X)J 0] 0 for k [K].
(D.2)
By Theorem 3.2
we immediately have the following corollary.
20

---

Under review as a conference paper at ICLR 2023
Theorem D.1 (Privacy cost in linear faimess (D. aware learning). Under the standing assump- tions, let estimators 0n and On be consistent for 0*, then
vrl(c(0)) c(7) $ (0(,E) Σ) and vT(c((nn) c(00) 4, N(0, Vi Vin EEN
lin )
where
Varq, xx))
Esl
1 =
50
T
Var Qn 19(00; ;X,;
Var (g(0;; X1,;;,,, Y)
EN
1 1 = 1)
no
1-Ky
2
T ifk=
V lin
No
7 i
for k. E [K].
E MISSING SENSITIVE ATTRIBUTES
Under the missingness mechanism (.8). the probability of observing a complete sample from group is
P(A = a, R = 1) = WaTe
for a E (0. 13. By the intermediate conclusion of Theorem 3.1 we have
v -000 3 Ar( Ar(0. (0. Varq, (g(0"; X, Y) kh(X,, Y) Varq, (g(0;; ; kk(XX, To (B.o [h(X, (h(xY))) Y)
I1 (Eq, [x(X, Y)))
and
v 3 A/( 65(0, 1000; - =h(X, Varq, -000xX,V) -x)(XxXX))) oo QEQ [A(X, Y)])
WI (EQ, [h(X, 8)1)2
Comparing the two asymptotic variances, we conclude that
ARF(On,, wp
12 + 71
12 + wi 'r2
where
To
Varlg(0"; ;x,1) - kh(X, Y) = 01/mo
and 72
m
Varlg X,Y) xh(X, Y) = 11/m1
21


Reviews:
[{"review_id": "wqFY0Oj2lnq", "reviewer": "Reviewer_gE91", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper characterizes the cost of privacy on exact notions of fairness; exact demographic parity and exact equality of opportunity. The authors use asymptotic relative efficiency.  ", "summary_of_the_review": "The paper extends previous work and provides theoretical insight into the cost of sensitive attribute differential privacy. While I did not find anything technically wrong with the paper, the presentation of the paper can be significantly improved with more clarity, better motivation, and more discussion. It could be that there was just not enough space to fully motivate and describe the authors' ideas, I guess I am not sure that ICLR is the best venue for this work. ", "strength_and_weaknesses": "Strengths: \n1. Extends analysis to the multi-group setting. \n2. The authors include simulated experiments to demonstrate the privacy cost. \n3. Characterizing the cost of protecting sensitive attributes can be useful in many real-world settings. \n\nWeaknesses: \n1. Implicit assumption that demographic features $A$ are independent of the $X$. In many real-life datasets, there is almost an exact correlation between $A$ and some $X_i$. E.g. Race and Zip Code. 2. It would be beneficial to directly state these assumptions. \nThe threat model is not clear. From what I gather, privacy is not guaranteed for $X$ only for $A$. This departs from usual formulations and warrants discussion. \n3. Setting exact fairness as the goal could be better motivated. The authors follow previous work in this set of assumptions. But since the privacy mechanism is randomized anyways, investigating approximate notions of fairness seems natural. Another issue is for certain distributions $\\theta^*$ simply does not exist since the optimization problem is subject to exact fairness constraints. \n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "RZJySvSLgt", "reviewer": "Reviewer_YkN8", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper considers the problem of learning a fair classifier from a sanitized dataset. This sanitized dataset is obtained by applying a local DP mechanism to the original data to obfuscate the sensitive attributes. This paper provides a precise characterization of the utility reduction in terms of statistical efficiency. The authors also consider several extensions of their theory (e.g., multiple groups, missing sensitive attributes). Simulations have been done on an artificial dataset, created by the authors. ", "summary_of_the_review": "Interesting paper but I have several concerns that require clarification and additional results ", "strength_and_weaknesses": "The problems studied in this paper (i.e., characterizing the effect of privacy cost in terms of group fairness) are important and significant. This paper, including its appendix, is well-written and the notations are very clear. The theoretical results look solid. \n\nMy main concerns about this paper are listed below. \n\n**Privacy mechanism**: it is unclear to me why the privacy mechanism is only applied to the sensitive attributes (S). When S is correlated with the rest of the features, an adversary can potentially reconstruct it from the rest of the features. Hence, I think it is crucial to apply the local DP mechanism to the entire data point instead of the sensitive attributes only.\n\n**Usefulness and assumptions**: Group fairness constraints are often non-convex w.r.t. the model parameters. Hence, from a practical perspective, it is unclear to me that studying the consistency of the *global* optimal solutions of empirical risk minimization is meaningful. From a theoretical perspective, it is unclear to me how to validate the assumptions in this paper. For example, Assumption 2 requires the uniqueness of the optimal primal-dual solution. This assumption makes a lot of sense in convex analysis but once again group fairness constraints are often non-convex. I would love to see some examples to clarify these assumptions.\n\n**Experiments**: The authors only validate their theoretical results on an artificial dataset. The authors may consider demonstrating their results through some real-world datasets (e.g., adult, compas). These datasets can also help validate the assumptions made in this paper.\n\nOther comments:\n\n**Fairness measures**: the authors may consider including a discussion on what group fairness measures can be covered by their analysis. For example, can the analysis cover false discovery rate and calibration error?\n\n**Related work**: this paper is missing some references. For example, the problem of learning from noisy observations of (or missing) sensitive attributes have been studied in fair ML by a line of works and I think it is worth acknowledging these references in the paper. \n\n**Intersectionality**: what if there are intersection sub-groups? Can the analysis in this paper extend to such settings?", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "1: The contributions are neither significant nor novel."}, "extra_text": {}}, {"review_id": "EExNgr2H-G", "reviewer": "Reviewer_iTev", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper concentrates on fair machine learning (ML), specifically studying the \"sub-optimality\" caused when the design phase of a fair estimator is forbidden to have access to the sensitive attributes which it should protect in order to provide fairness. To this end, the authors take the setting where the design phase instead has access to locally-perturbed $\\varepsilon$-differentially private versions of the protected attributes, where privacy is ensured via a standard randomized response mechanism. The authors then define and quantify how the resulting estimator deviates from the estimator that has access to the sensitive attributes in terms of statistical efficiency.", "summary_of_the_review": "The paper studies a modern and interesting topic, and the analysis provided is thorough. I am not sure about how interesting the findings are, and I am concerned about the current presentation of the materials.", "strength_and_weaknesses": "**Strength:** I believe the literature is well summarized. The question asked is clear and very relevant to the research our community is conducting. The proofs look correct and the results are intuitive.\n\n**Weaknesses:** \n*I list my major and minor concerns that made me recommend marginally below the acceptance threshold. However, I still think the paper has some novelty, hence I hope that my comments would be found useful by the authors to improve the paper's quality. I am also going to stay active during the discussion period in case the authors have updates or questions regarding my review.*\n\n***Major Weaknesses/Questions***\n- My biggest concern is that the quantified \"efficiency loss\" does not tell much. I do not know how the community can use this result in practice. Despite sound mathematical analysis, I think it is not surprising that the efficiency loss is driven by the privacy budget and the (im-)balance between different sensitive attribute groups. If, for example, the quantified loss would be compared with some alternative to the DP attributes + fairness-constrained optimization setting, then perhaps this would guide decision-makers. But right now, the paper defines several assumptions and then expresses the already-imaginable efficiency loss in terms of the (nationally heavily introduced) problem parameters.\n- The numerical experiments are not adding anything new to the paper. It is not clear what this tells the reader. \n- The paper is hard to follow, because lots of assumptions and notations are introduced before giving the results. Some sentences are objective/personal or unclear. I will list some of them next.\n\n***Minor Weaknesses/Questions***\n- Introduction: The second paragraph is not fitting well after the first one. It is not clear without reading the rest of the paper where DP is used. Mozannar et al. (2020) citation is said to propose some technique, but it is not stated in which context this will be useful. \n- Page 1, \"interpretable\" item: The listed reasons for efficiency loss are already known.\n- Page 2: We basically study -> maybe we can avoid 'basically'? \n- Section 2: In the beginning $\\mathcal{Y} := \\{ 0,1\\} $ is not defined if I am not wrong.\n- Section 2 Suggestion: Maybe discuss what happens when some $A$ can be interpreted from $\\mathcal{X}$. There is a big literature on this if I am not wrong. Simply saying \"we assume $A$ is not included in $X$\" might also work.\n- $\\hat{Y} \\triangleq f(X)$ is re-defined more than once\n- After Definition 2.1 and 2.2 the notation $\\hat{Y} = h(X)$ is used, but $h(\\cdot)$ is never defined before.\n- When defining the parametric space $\\mathcal{H}$, could you maybe show the domain and range of $f_\\theta(\\cdot)$? Because later on, you will distinguish the cases where these functions can and cannot access $Z$ (private counterpart of $A$).\n- \"To keep things simple\" -> what things? Could you please be more specific here? Because later on you will extend $|\\mathcal{A}| = 2$. Is this assumption here for intuition?\n- Equation (2.2) and similar problems onward: The use of $\\alpha_n$ is not discussed. This is important in my view -- could the authors cite relevant papers (*e.g.*, why why the ERM setting forces us to use such a slack, whether there is a known result on the effect of this parameter on the consistency, etc.)?\n- Section 2.2: \"In addition, the sampling mechanism $Q$ requires $Z \\perp X, Y | A$\". What does this mean? \n- When \"local\"-DP is first mentioned, maybe a clarification of what this means would be great. As the DP component of this paper is light, the readers might lack knowledge of DP, hence may be confused about the local DP terminology.\n- The last paragraph of Section 2.2 is redundant -- equation (2.4) is obvious, especially after equation (2.3)\n- Page 3, $\\tilde{f}$ is used for the first time.\n- \"A direct corollary of Proposition 2.3 is that (2.1) and (2.5) have exactly the same solution $\\theta^\\star$\" -> I don't agree with this. Proposition 2.3 is about the feasibility of a solution in the fairness constraints, but the solution to the underlying optimization problems might be different. Please correct me if you disagree with me and please also clarify this in the paper as the \"uniqueness of the solution\" explanation might sound vague.\n- Please define $\\sqrt{n}$-consistent terminology, and the notations of convergence in probability/distribution.\n- Section 2.4 \"both of them are reasonable\" -> What does reasonable mean?\n- Question: Is \"constraint function\" name for $c$ suitable? Typically constraints are defined with their right-hand sides and maybe here we can instead say something as \"(signed) fairness violation\"?\n- Definition 2.5: $\\hat{\\theta}$ uses $\\sigma^2$ however $\\tilde{\\theta}$ uses $\\tilde{\\sigma}^2$\n- The last two paragraphs of Section 2 are very hard to understand and follow for me. The sentences are using formal notation but the explanations are informal. How can we formally argue that only how close $\\hat{\\theta} $ converges to $\\theta^\\star$ is what drives the efficiency: e.g., we still have an inner product with $\\nabla c(\\theta^\\star)$ and it is not very clear. \n- Section 3: Please highlight that this generalization extends to regression as well, since before the reader was restricted to classifiers.\n- Before defining (3.1) I think we need to discuss $g$ and $h$ as they are not defined.\n- Page 5 overall introduces much notation and is not a fun page to read. Can we somehow compress the definitions? Some ideas and further comments: I think (3.3) should be clear from the context and can be moved to Appendix. Defining $\\tilde{c}(\\theta)$ right after (3.3) looks a bit unnecessary, this is a definition that we keep repeating many times throughout the paper. The same goes for (3.4) and the optimization problems at the end of page 5 -- these are already known and probably there is no need to add the exact same problems only by changing $A$ to $Z$.\n- Page 6: In my view, these assumptions should be explained a bit further. Especially, the sub-Gaussian assumption. Is this something used in the related settings? Maybe some citations would \"reassure\" the reader? The second assumption is very high-level, and such duality/uniqueness arguments can be ensured with simpler lower-level assumptions. As for the third assumption, maybe \"Lagrangian\" can be clarified further as \"Lagrangian dual\" and \"Lagrangian function\" may both be referred to as \"Lagrangian\".\n- Page 7: \"the mechanism $Q$ perturbs ...\" these are all defined before and I cannot see any benefit of re-stating these with an additional \"K\".\n- Why do the simulations compare a few $n$? Not much intuition is given in the experiments. Why are we ensuring fairness wrt the 'estimation error's? Could you show the linear regression problem satisfies the assumptions that were necessary for the analysis?\n- In the Conclusion section referring back to previous mathematical notation such as $h \\equiv 1 $ or providing further analysis and introducing new notation is not very usual in my view and it is hard to digest at the end of the paper.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "9__5xHnvq7z", "reviewer": "Reviewer_MtpY", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper proposes a cost measure that connects privacy to model fairness. Given that sensitive attributes are private and protected using differential privacy, the main contribution is the introduction of asymptotic relative efficiency (ARE), which measures how much the convergence to a fair model is \"slowed down\" compared to when not injecting the noise by comparing the variances of estimators. The derivation is first performed in a binary sensitive group setup and then generalized to multiple groups. A simple simulation is performed followed by a discussion.", "summary_of_the_review": "The paper proposes an interesting novel measure to quantify how differential privacy noise on a sensitive attribute influences model fairness convergence. While the mathematical derivation looks sound, it is not clear how widely applicable the measure is. In addition, the repetition of content between the binary versus general theories seems to be unnecessary. Finally, the experiments can be improved in several ways.", "strength_and_weaknesses": "Strengths\n- First or one of the first works to make a theoretical connection between a differentially-private sensitive attribute and model fairness convergence.\n- The metric is statistically principled and provides interpretability.\n- The mathematical derivations are straightforward.\n- Simulations show a fairness-privacy trade-off as expected.\n\nWeaknesses\n- While ARE can be quite useful in connecting privacy and fairness, it is not clear how practically it can be applied. The authors state three technical assumptions - smoothness and concentration, uniqueness, and positive definiteness - without much justification other than they give interpretability. It is not clear how reasonable they are for various fairness applications. For example, if a company is using ML for hiring, how can it be confident that the properties hold without actually proving them? A good measure is one that everyone can use to evaluate any technique, so IMHO the applicability is critical.\n- Another question is whether ARE is too complicated for its purpose. A simple approach would be to look at the $\\epsilon$ value of differential privacy and fairness violation $c$ together to see the privacy-fairness tradeoff. There should be some justification through simulations or experiments on why much simpler approaches do not capture the tradeoff as well as ARE. \n- Section 3.1 (General Theory) extends the two demographic groups theory to multiple groups, but the results look quite similar and thus redundant. How about discussing the general theory from the start and focus more on why the measure is practical by introducing various use cases? Also for the general theory, it is not clear if the same three technical assumptions are sufficient. \n- The simulations are definitely helpful, but seem too thin to convincingly demonstrate ARE. Here are some potentially-interesting experiments that could strengthen the paper:\n  - A comparison with some baselines that also capture the privacy-fairness tradeoff (e.g., any combinations of $\\epsilon$ and $c$) to clearly see the benefits of ARE. \n  - A demonstration that users actually think ARE is interpretable through user studies.\n  - An experiment on real datasets.\n  - An experiment that involves the constraint violation inflation.\n  - An experiment that assumes missing sensitive attributes.\n- In Section 5, there is some more analysis where $h \\equiv 1$, but it is not clear if this belongs in the summary and discussion.\n\n\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "1: The contributions are neither significant nor novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject