Demographic Parity Constrained Minimax Optimal Regression under Linear Model
Authors: Kazuto Fukuchi
Jun Sakuma
Venue: NeurIPS 2023 poster (2023)
Keywords: demographic parity
regression
minimax optimal

Abstract: We explore the minimax optimal error associated with a demographic parity-constrained regression problem within the context of a linear model. Our proposed model encompasses a broader range of discriminatory bias sources compared to the model presented by Chzhen and Schreuder. Our analysis reveals that the minimax optimal error for the demographic parity-constrained regression problem under our model is characterized by $\Theta(\frac{dM}{n})$, where $n$ denotes the sample size, $d$ represents the dimensionality, and $M$ signifies the number of demographic groups arising from sensitive attributes. Moreover, we demonstrate that the minimax error increases in conjunction with a larger bias present in the model.

Demographic Parity Constrained Minimax Optimal Regression under Linear Model
Kazuto Fukuchi Jun Sakuma 2.3 University of Tsukuba 2 Tokyo Institute of Technology fukuchi@cs tsukuba.ac.. sakuma@c. Eikuma@c.titech. atttechh...J........ Jc.
RIKEN
Abstract
We explore the minimax optimal error associated with a demographic parity- constrained regression problem within the context of linear model. Our proposed model encompasses a broader range of discriminatory bias sources compared to the model presented by Chzhen and Schreuder [6]. Our analysis reveals that the minimax optimal error for the demographic under our model is characterized by O (dM//x). where denotes the sample size, d represents the dimensionality, and M sigmifies the number of demographic groups arising from sensitive attributes. Moreover, we demonstrate that the minimax error increases in conjunction with larger bias present in the model.
suritycoontrriieed regression problem
1 Introduction
Machine learning techniques have been incorporated into numerous automated decision-making systems, spanning critical domains such employment, credit assessment, insurance, and security. Nevertheless, these systems can exhibit discriminatory behavior towards specific demographic groups, including gender, race, and ethnicity, potentially causing significant societal ramifications. This issue, known as the fairness problem, has attracted substantial attention within the machine learning research community. The growing focus on the fairness problem primarily arises from reported instances of unfair behavior in real-world systems, encompassing recidivism risk prediction [3], hiring practices [10], facial recognition [9, 17], and credit scoring [24].
Motivated by these concerns, a considerable body research has explored regression problems subject to fairness constraints [13, 25, 16, 2, 8, 14, 18]. Numerous regression algorithms incor- porating various fairness constraints have been developed to accommodate diverse contexts, with demographic parity [21] and equalized odds [11] being the predominant fairness constraints adopted by these methods.
In this study, we focus the regression problem under the fairness constraint of demographic parity [21]. Existing literature primarily concentrates on the development of fair regression algorithms, and their performance evaluation predominantly relies empirical analyses. Such evaluations, however, only offer performance guarantees for specific scenarios explored in the experiments, which may result in poor performance in unexamined situations. To ensure the algorithm's robust performance across a wider range of contexts and obtain a comprehensive understanding of the fair regression problem, theoretical analysis of statistical efficiency indispensable.
Several studies have introduced fair regression algorithms accompanied by theoretical analyses of their statistical efficiency in terms of accuracy and fairness. Agarwal et al. [2] designed demographic parity- based fair regression algorithm using reduction methods [l] and established upper bounds on its empirical approximation errors for accuracy and fairness using Rademacher complexity. Chzhen
"Corresponding author.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

Table 1: Comparison between Chzhen and Schreuder [6]'s ss and our models. Each checkmark signifies the presence of an influence exerted by the sensitive attribute on the respective variable.
partial coefficients
non-sensitive features
intercept
Chzhen and Schreuder [6] ours
al. [8] proposed discretization- fair regression algorithm, deriving upper bounds on the mean squared excess risk for accuracy and a Kolmogorov distance-based score for demographic parity as fairness guarantees. Chzhen et al. [7] derived the Bayes optimal regressor under demographic parity constraint, providing upper bounds the mean absolute deviation from the Bayes optimal regressor for accuracy and Kolmogorov distance-based score for demographic parity as fairness guarantees. Despite ensuring low error and fair treatment even in non-linear models, it remains unclear if these guarantees represent optimal performance among possible algorithms.
Minimax optimal fair regression. Numerous researchers have investigated minimax optimal regression algorithms, the best possible algorithm, without addressing fairness considerations [22, 23, 19, 15]. In contrast to standard regression problems, minimax optimality in fair regression problems remains relatively unexplored, with notable exception being the recent work by Chzhen and Schreuder [6]. They examine minimax optimality in fair regression problems, incorporating demographic parity constraints within the following linear model:
Y = ( + bs + where X ().
(I)
In this model, Y, X, and S represent the outcome, non-sensitive features, and sensitive attribute, respectively. ( denotes the inner product, & represents zero-mean noise, and Σ is an arbitrary covariance matrix. For example, in salary calculations, X and S correspond to working hours and gender, respectively. with by and 3 signifying the base salary and hourly wage. In Eq (I), the salary Y is determined by the base salary by and the product of working hours X and an hourly wage S*.
The model in Eq (1) exhibits limitations pertaining its applicability across various scenarios. We elucidate these limitations by discussing the notion of direct discrimination and indirect discrimina- tion, summarized succinctly in the second row of Table 1. Direct discrimination occurs when the sensitive attribute influences the outcome, regardless of non-sensitive features. The model in Eq (1) can treat direct discrimination resulting from the dependency of the intercept by on S: for example, can capture discrimination due to basing base salary on gender (third column in Table 1). However, it is imperative to underscore that the model in Eq (1) fails handle direct discrimination arising from the partial (regression) coefficients 8 as these are independent of S; for instance, it cannot accommodate discrimination due to gender-dependent hourly wages (second column Table 1).
Indirect discrimination (or redlining effect [4]) constitutes another source of unfair bias, arising when the sensitive attribute influences the outcome through its correlation with non-sensitive features. The presence of the dependency between non-sensitive features and the sensitive attribute signifies indirect discrimination. In the model in Eq (I), non-sensitive features X independet from the sensitive attribute S, thereby implying an absence of indirect discrimination (forth column in Table 1).
Chzhen and Schreuder [6] effectively revealed the minimax optimal error for fair regression prob- lems involving direct discrimination due to varying intercepts associated with sensitive attributes. However, their research does not address direct discrimination from partial coefficients and indirect discrimination through non non-sensitive features.
Our model and contributions. In this study, we investigate the minimax optimality of the fair regression problem in the context of the following model:
Y (Bg, X) + E where X N(us.ox])
(2)
where x > 0. and I denotes the identity matrix. The subscript in 33 and μı signifies that our model varies regression coefficients and the mean of non-sensitive features based the sensitive attribute.
Compared to the model proposed by Chzhen and Schreuder [6], our model accommodates a broader range of direct and indirect discrimination. These discriminations can be characterized as follows:

---

(Direct discrimination) Our model accommodates direct discrimination through discrepancies in S'g concerning S, as the regression coefficients 53 hinge on the sensitive attribute S (second and third columns on the third row in Table 1). This includes, for instance, discrimination arising from varying base salaries and hourly wages. Divergent partial coefficients yield varied outcome variance amongst S, while disparate intercepts relative to S merely alter the outcome's ' mean. Hence, our model introduces an additional challenge of attenuating direct discrimination through disparate variance, alongside mitigating direct discrimination through disparate mean. This presents stark contrast to Chzhen and Schreuder [6]'s model, which solely focuses on mitigating discrimination via the mean without considering the variance.
(Indirect discrimination) The sensitive attribute affects the mean of non-sensitive features X, denoted by the subscript of p.s. Our model thereby introduces indirect discrimination through variations in μ4l with respect to S (e.g.. disparate working hours by gender). To alleviate this form of indirect discrimination, ls needs to be estimated adjust the learned regressor, thereby ensuring its output remains invariant to differing jAs. Therefore, our model presents an additional complexity in estimating ji for mitigating indirect discrimination.
Overall, our model demonstrates an expanded dependency of partial coefficients (direct discrimina- tion) and non-sensitive features (indirect discrimination) the sensitive attribute (second and fourth columns of Table 1).
The principal contribution of this paper lies in the establishment of matching upper and lower bounds on the minimax optimal error (i.e., the error corresponding the minimax optimal regression algorithm) and the proposition of a regression algorithm that achieves this optimal error under Eq (2). The optimal error elucidates several insights:
(Direct discrimination) The optimal error comprises a term reflecting the outcome's variance heterogeneity but excludes that of the outcome's mean. This insight implies that mitigating direct discrimination due to the outcome's 's variance sacrifices statistical efficiency, whereas addressing direct discrimination due the outcome's 's mean does not entail this cost. This term effectively quantifies the cost of mitigating direct discrimination in variance and is absent from the optimal error of the Chzhen and Schreuder [6]'s model. Its identification, thus, sigmifies a crucial contribution of
our research.
(Indirect discrimination) Our lower bound independent of the term associated with indirect discrimination. Although this evidence is not definitive, it hints at the potential for mitigating indirect discrimination without additional costs under certain conditions. This observation sets the stage for future research focused on developing cost-effective strategies to tackle indirect discrimination.
Our technical contributions to establish these bounds are detailed in Section 4.
Notations. Given positive integer m, define [m] m.). For finite set A, denote its cardinality by [A]. Given an event E, its complement is represented as E and its probubility is denoted by P(E). For a random variable X, its expectation is E[X]. and its associated sigma-algeera is oXX). For two real values a and b, the notations a V b = max(a, b} and a A = min ma, (,, b} are used. For a square matrix Amax((A and Amin (A), respectively, and its transpose is represented by A The set of unit vectors is given by S.-1- For a sequence a, indexed by E T, the notation a. denotes the sequence (at)ee..
Rdxdd its maximum and minimum eigenvalues are denoted by
Problem Setup
2.1 Model and Learning Algorithm
Model. The proposed model, described in the introduction, is formulated according to Eq (2). We
consider X E Id and S E [M] where M > 2. The noise variable, &. is assumed to follow Gaussian distribution with zero mean and variance of > We define ps PSS 5 s) for all [M], and the optimal regression function denoted as (*(
(3)..).
Learning algorithm. Given i.i.d. copies of the tuple (X, Y). denoted as Dn {(XI, Si) (Xn, Sn, Yn)), the goal is to construct a regression function that maps (X,S) to Y, represented as fn- The learner seeks to optimize the accuracy of fn while satisfying fairness constraint. The definitions of faimess and accuracy are provided in subsequent subsections.
3

---

2.2 Fairness
Demographic parity. We utilize demographic parity [21] as our fairness criterion. regressor adheres to demographic parity if its output distribution is invariant when conditioned on 5 = 8.
Definition 1. A vegressor f satisfies (strong) demographic parity if. for all s, E [M], and for all E E (J((, (()(X,S) E E|S =} -P(((X E E|S=
Denote the set of all regressors fulfilling demographic parity for given distribution of X, parameter- ized by μ.., as (D.(
Fairness consistency. Instead of enforcing strict demographic parity (Definition 1), which results in the regressor be constant function due to the unknown (X, S) distribution, we introduce fairness consistency (Definition 2). This concept demands the learned regressor to converge fair regressor as the sample size n approaches infinity.
To define "convergence", we introduce the unfairness score U()) 2 O, where a lower UJ) indicates higher fairness level. U(f) if and only if f achieves demographic parity (Definition 1). We claim the learned regressor fn converges to an exactly fair regressor when (ff) + as n - oo. Definition 2. learning algorithm (a, cconsistenlyy fair for an unfairness score U ifthrr exist }
constants no 2 O and C > 0, independent of n, such that ((U(fn) > Cn Cn-a < 6 for all n 2 no. with randomness arising from the training sample via fn-
Note that an (a, connsistetyyy fair regressor fn exhibits (a',8)-consisten fairness for any a' (0, a).
We adopt specific unfairness score using the Wasserstein distance. Given two probability measures and / over R. [1, v²) denotes the set of all coupling measures и satisfying x(A x x = (A) and (RR x A') = (A(') for every measurable sets A, A' C IR. The Wassersstein distance W2 between v and // expressed as (v, = inf [(z 22)2 dz'). Our unfairness
score is then formulated as:
U(f)
(2(
s, E.M)
where Pyls represents the distribution of fXX conditioned on s. Prior works, including [2, 7, 8, 6], have adopted different unfairness scores (see the appendix for details?).
2.3 Accuracy
Under the fairness consistency constraint, the learner's objective is to obtain fair approximation of f", denoted as fūp, which is the closest regressor to f within FDP(p.) using the L distance:
JDP arg min E -( fEFor(a.)
To evaluate the inaccuracy of regressor f, we compute the mean squared deviation from Söp:
8(f: p.)
(Xxx))
Chzhen et al. [7, 8] employ similar definitions, differing only in the choice deviation metric.
This paper aims to identify the minimax optimal regression algorithm, which minimizes Eq (3) while maintaining fairness consistency. Given parameters formulated as:
and e (0, 1), the optimal error is
(a,
inf fa:(a,6)-connn cecossisttty fair 8 P...E.MM.............MMM......
sup E[ ,,),
where the infimum is taken over all (a, connsisstyy fair algorithms, and B and M represent the sets possible 3r and p., respectively.
A version of this paper including appendices is available in the supplementary material.

---

3
Main Results
Our main result to establish the minimax optimal error bound, delineating the dependency on the diversity of conditional outcome variances concerning the sensitive attribute. This diversity of the variances is quantified via a parameter B > 0, which defined such that it satisfies:
C Pa1 M
max |
B and
Σ
S B
The left-hand side of the second inequality in Eq (4) forms as a product of two factors: the weighted As the norms increase, the first factor (weighted average norms) has the propensity to grow, while the second factor (averaged inverse norms) tends to rise when the norms decrease. Maximizing the product of these two elements involves a delicate balaneing act: the norms of some groups need to be large, while the norms of other groups need to be smaller. As such, the left-hand side of the second incquality in Eq (4) can increase when the norms || display diversity.
average norms, (E, Ps [1) and the averaged inverse norms, I E. ||3;||2 1112
We adopt mild assumptions on 3 and μa. Let B denote the set of 3: satisfying Eq (4), Assume there exists finite universal constant
0 such that || S U for all s E [M], leading to M (u. E RddMM Vs [M,, I|,ss|| I| I U}. Our analysis relies on these assumptions.
Our main results are as follows:
Theorem 1. Given
10, and 8 E (0,1), suppose M(d - 1) > 16 and 12(3d V
4 4l((M/6)// minge[M] Ps- Then, there exist universal constants C > 0 and e >> O such that
B2
B² V ox B² V B
1 12
O
SE 12
C
n
n
Theorem illustrates that the optimal error is o up a constant factor which may potentially depend on ax and U. The implications of Theorem can be summarized as follows:
1. The optimal error for the standard linear regression problem can be denoted as 4/n [15]. The dependency on n and d is consistent with the standard case, provided a E (0, 1/2].
The term dM denotes the number of unknown parameters in Eq (2), comprising ,",.., PM. R
and μl. PM E Rd. This dependency on the number of unknown parameters is a common characteristics observed in statistical estimation problems.
(Direct discrimination) The minimax error delineated in Theorem demonstrates a dependency on parameter B. As the variation of || with respect to s increases, so does the magnitude of B. Hence, B serves as a measure of the difficulty in mitigating direct discrimination due to the outcome's 's variance. This unique quantification of difficulty is absent in standard regression problems and specific to fair regression problems.
4. (Indirect discrimination) The lower bound precludes parameters associated with indirect dis- crimination. It is conceivable that biases arising from indirect discrimination can be reduced without extra costs, provided the dependence of X on S exists only in its mean. Investigating and clarifying this aspect offers a promising direction for future rescarch.
5. The minimax error is invariant to a and 6, implying that the learning process does not introduce unfair bias for a E (0, 1/2). However, the case for a 2 1/2 remains unexplored and poses a significant research challenge.
6. The gap between the upper and lower bounds regarding a and U remains, making narrowing this gap an essential future research direction.
Remark 1. Direct comparison of the minimax error between our model and that of Eq (1) is not feasible due to the differing fōp across the models. However, the emergence of the quimess-speciff term B can be unequivocally identified as a novel contribution in our study. Notably, the minimax error validated by Chzhen and Schreuder [6] is congruent with the minimax optimal error of standard linear regression within their model, a contrast to our findings.
To prove Theorem 1, we initiate by constructing the estimator detailed in Section 5. We then prove in Section 6 that the estimator satisfies 1) (a, fa-rrirn consistency for E (0, 1/2). and 2) the error aligns with the upper bound specified in Theorem Subsequently, we present a sketch of the proof for the lower bound in Theorem in Section 7, All omitted proofs can be found in the appendices.
5

---

Technical Difficulties in Minimax Optimality Analyses
In this section, we expound on the challenges arising from the analysis of minimax optimality for our problem. First, we introduce the closed-form expression for the Bayes optimal fair regressor fDp- We then outline the technical difficulties encountered during the analysis.
Bayes optimal fair regressor under Eq (2). Chzhen et al. [7] present a characterization regression error and the corresponding regressor minimizing the mean squared error under the demographic parity constraint. Building upon the results from Chzhen et al. [7], we derive the closed-form expression for Dr in the following lemma.
Lemma 1. Given the model in Eq (2), the Bayes optimal regressor udhering to the demogruphic purity constraint can be formulated as
fi - -1,3.11
x Ms ) DD
(5)
|1:
where ||3-|| E [M Ps 1111
Technical difficulty in deriving the upper bound in Theorem 1. To obtain the upper bound in Theorem we first construct an estimator for the regression function in Eq (5) and analyze its regression error. This entails developing estimators for individual components in Eq (5) (e.g.. || 8:/118;1 Ma. etc.) and substituting them into Eq (5). The upper bound on & (a, 5) is derived by combining estimation error bounds for each component's estimator. However, to our best knowledge, no existing estimators provide bounds for the norm ([] and direction (0//11551) II) of regression coefficients. A direct approach involves computing the norm and direction the OLS estimator, but standard analyses for OLS do not yield bounds on the estimation errors.
The main challenge in deriving the upper bound of Theorem 1 lies in analyzing the following problem: given X following non-isotropic Gaussian distribution with mean find upper bounds on || ? and [| [|]])) Solving this problem provides estimation errors for the norm and direction estimators, as the OLS estimator is an unbiased estimator with noise following the non-isotropic Gaussian distribution. Our key technical contribution is the derivation of these
bounds (Theorems 4 and 5).
Technical difficulty in deriving the lower bound in Theorem 1. The minimax optimal error characterizes the intrinsic complexity of the regression problem, as no algorithm can surpass this error. In our analysis of the lower bound presented in Theorem 1, we demonstrate that the fair regression problem's 's complexity, under the model Eq (2), is characterized by the complexity in estimating the direction 81/118 JI. The primary challenge lies in establishing this characterization.
To overcome this challenge, we investigate the geometric structure the error term (f p.) concerning the parameters 3 and μ... We then reveal that the geometric structure of (f; p.) is characterized by the geometric structure of the direction 97/113;1 (Theorem 7).
Estimator
In this section, we present detailed construction of the estimators that attain the minimax error as delineated in Theorem 1. Existing theoretical results, such as those found in Agarwal et al. [2]. Chzhen al. [7. 8), are incapable of addressing unbounded non-sensitive features X unbounded outcomes Y. rendering them inapplicable to our problem. Consequently, we have developed a novel estimator accompanied by rigorous analytical techniques.
Estimator construction. In constructing the optimal regressor for model Eq (2), we leverage the results from Lemma and employ plugin estimator. The method involves estimating the components of terms Eq (5) and substituting the obtained estimates into the same equation. Concretely, we derive estimators ||3]]] ||. 3.. fe.. P.. 8.. and j' with the following correspondence:
8
139
1
1.99
p.
['E(M]]
Bar
8,

---

Table 2: Estimator construction. In this table, Bn and B%,, denote OLS estimands obtained from subsets ab and D respectively, "Sample" refers to the subset utilized for estimand calculation, while "Definition" provides the corresponding estimator's definition. "Sample" in || is left empty, as it derived from P. and ||
Estimator
Sample
Definition
P
n..
p. "o/n
B&
11,
| 11, |l if nf > 18d, and || 0 otherwise
3
|| || = >>e [Mr) Pa 1..1.3a11
B
D2.-
B. /2.5/118..0
n. > 18d, and B, 0 otherwise
P.
Da,-
jg us.a
Σxe X3,5,1
3%
D1,
B. 3 if n, 12d, and 3 = 0 otherwise
D2,,
P. 22 E
2. X X2,
For technical reasons, we partition the sample to calculate each estimand. Each estimator is assigned a corresponding subset, as shown in Table 2. Under specific conditions, n, >> 18d or ni 12d, estimators may exhibit altered behavior, primarily as technical considerations for subsequent analyses. We detail the partitioning process as follows. First, we create histogram of the sensitive attribute S, denoted n. (M1...., mar). with n. i [n] S. *)|. Simultaneously. we form group-wise samples D2 = {(X,, Y.)
[n], = s). For each s E [M]] we partition D, into D1,s, a2 and D3.s. ensuring [Do.l = nb, 2 [n./3] for b [3]. Using n.., Di,e, D2.e, and Da we estimate P.. [| 3., and fs.. respectively. The combination of p. and || yields [| []. Furthermore, we generate duplicate of D., denoted as D', and partition it into Dí., and D2... satisfying 12/.ll == n/,, 2 [n./2] for E [2]. We then use Dí.s and D22,, to estimate & and i'. Precise definitions of the estimator construction and subset partitioning can be found in the appendices.
Incorporating the derived estimators, we construct the final regressor as:
fa(r, |1..1 (3., P.0) + Σ pe De
s'E[M]
6
Upper Bound Analyses
In this section, we demonstrate the achievability of the upper bound presented in Theorem utilizing the estimator delineated in Section 5. Initially, we conduct an analysis of the estimator's fairness guarantee, subsequently progressing an examination of the estimator's mean squared deviation.
6.1 Analysis of Fairness
For our fairness guarantee on f.. demonstrate the following theorem. Theorem 2. If n 48 (n(M/8)/ min, Pa. we have for (0.
48 (81/(M
max
Wy (Via)a) >=Box))))>BBoxxX E[
S 6.
mingre(M] up,""
By proving Theorem 2, we can immediately confirm that the estimator adheres (a, 8) fairness consistency with a E (0, 1/2].
6.2 Analysis Estimation Error
In this subsection, we derive an upper bound for the estimation error presented in Theorem 1, focusing on the estimator introduced in Section To derive the upper bound Theorem 1, we begin by decomposing the mean squared deviation of the estimator in Eq (6) as follows:
7

---

Theorem 3. For the estimator defined in Eq (6), the mean square deviation from fDP is bounded above by
1/2
1/2
2
1/2
Σ
P.E
E
|
n2
BB. Ms - (1o)
n.
+ tox
[13.
113+1)
72.
+
#E .M]]
7
1/2
1 E
Por (B Bz. 11.) ))
x
11 E
3.
92/11.3111
Σ
n.
+
s'E(ar]
1/2
) (7)
E
Σ N'EM
Per (32 113,,/0 Har)
+
(psr Pe 1B3 Hor)
#'EMM
In Eq (7), the terms correspond to the estimation errors of As. || 1l. Bz. By, Plg and p., respectively, Standard techniques for the OLS estimator and empirical average yield upper bounds for the first, fourth, fifth, and sixth terms. Nevertheless, the second and third terms in Eq (7) involve non-linear transformations of the OLS estimator (i.e., taking the norm or dividing by the norm), complicating their error analysis. This section's 's primary technical contributions involve establishing tight upper bounds for the second and third terms in Eq (7).
Estimation error of norm and direction of 3r. Consider XI...., X, iid N(u, I) 8r e R with || < B for some B > 0, and ,I, Sn ~ N(0, of). Define Y; = (B" + The OLS estimator
of 8 is given by 3 = ( X X) (xx where X = (XI,..X,)) and Y = (Y ... Y.)
The direction estimator is // while the norm estimator is ||
We present the estimation errors for direction and norm in Theorems 4 and 5: Theorem 4. For > 6d, we have
9
8r
84c
20 odd x
6 71
E
1+
|181|
1|3*
3-
1:21
6
Theorem 5. For >> 6d, we have
E (1111 (131))
202
6
1
n
The direction's estimation error (Theorem 4) is 0 13)) while the norm's estimation eгror (Theorem 5) is 0/)32)) Integrating Theorems 3 to 5 yields the B term in the upper bound in Theorem 1. The remaining part, Uog/n, arises from the estimation error of 3 (the third term in Eq (7)), dominating other terms in Eq (7).
7 Lower Bound Analyses
In this section, we provide proof sketch for the lower bound, outlined in Theorem 1. To facilitate clear and concise presentation of the proof sketch, we introduce several notations. Let denote the tuple of distribution parameters (9., Jr.), and let θ represent the set of all such parameters, defined as M. We use P, and Eg to denote the probability and expectation operators, respectively, given X (us,,0311 and Y (Bs, X)) + &. where & N0, oZ). We adopt the shorthand 0(f:0) E(f: p.) for 0 (z.. Moreover, 0 p.). For two probability distributions æ and n', the Kullback-Leibler (KL) divergence d= (z)). Finally, we denote the set of all L integrable
define fo arg min R(f: B.,, p.) for
is denoted (RL(T, T') I du functions f : Rd [M] R as L
di
By utilizing Fano's 's inequality, we establish lower bound for the minimax error as presented in Theorem 1. Due to the invariance of the distribution of Si,.., Sn under parameter alterations 0,

---

Fano's inequality can be applied after conditioning on Si,..., equivalently, n.. Consequently, we derive the following theorem:
Theorem 6. Let θ _ ④ be a finite set of the parameters such that there exists > 0 such that for any 0, o E Ô i E(f:0) 8) V E(f: 8') 2 e, where θ and e is possibly dependent on n.. Let |6] = K.
Then, for arbitrary
and (0,1), we have
E (
inf K Eoce DKI, x) + + ]
En (a, 8)
In(K)
where ae denotes the distribution of D,, conditioned on n. with parameter 6, and the expectation is taken over n...
As demonstrated Theorem 6, the lower bound for minimax error can be obtained by constructing
é such that: 1) inf y (ff VE 8*) 2 e for any 0, 0' E é, and 2) inf K Eoe DKL ( (To)j, : S
ln(K/4)/2. With the construction of such Ô, lower bound of E [ is attained.
We present a theorem that establishes a tight lower bound on inf E(f:0) E(f;
Theorem Let 0 and 6' be the parameters of the distributions such that 203 for all [M]. Then, have
I|,s
1'lll dg <1
ee-
1..1133 ||8
|3:113
2
dg
1+$
inf E(::0) E(J:0)) N FeC
Σ SE[M]
Ps
1 +
4
||
2
| ull characterizes the lower bound, which is different from the The term || |1.
characteristic term in standard linear regression, || - -11
We next present the construction of é. We construct é such that each of its elements corresponds to an index from the set V = 1- M (x denoted by 8, = {.... Mv..1 E Ô, where Bu, is controlled such that its norm is equivalent to specified value B,, i.e., 18 = B,. This construction ensures that Ô C B x M. Given positive values 61, m.; 6M and BI..., BA, we construct Ô as follows:
Bu,,,1 -1-e3. and Bo,sii
|| Ba,
for i 2, ... d.
(8)
[Bo,o]]
1
vd
We demonstrate the following properties for Ô defined in Eq (8).
Theorem 8. Given C1,.., > O and Bi...., By > let θ θ represent the set of parameters defined in Eq (8). Let Tojn. be the distribution of the sample Dr, conditioned n. with the distribution parameter 6. Then, we have for any v, v' E V.
2
x
inf E(f:0w) V VE(S00)) fect
Σ Ps SE[M]
Σ (E(M
De Dr By
(vs, vl 8),
and 2) for v, e V.
20 Brnsez af(d 1)
DKL (Te.In TT,r (m.) = Σ
der (v.,
SE(M]
By integrating Theorems 6 to 8 and employing the renowned Varshamov-Gilben bound, derive the lower bound in Theorem 1.
8 Conclusion
This paper investigates a regression problem with (a,, -airiiess consistency fairness constraint. Specifically, we demonstrate that, under the constraint of (a, -)--ffrneess the minimax optimal error

---

scales as dM/n up to constant factor, when E (0, 1/2). Additionally, we provide the fair regressor that achieves this optimal error.
Potential negative societal impacts. Our study aims to mitigate the negative impact of regression models social groups, rather than cause harm. However, results are only valid for linear mod- cls, as defined in Eq (2), Misapplication of our findings to other models may result in discriminatory treatment, which should be avoided.
Acknowledgments and Disclosure of Funding
This work was partly supported by JSPS KAKENHI Grant Numbers JP23K13011 and JP23H00483.
References
[1] Alekh Agarwal, Alina Beygelzimer, Miroslav Dudík, John Langford, and Hanna Wallach. A Reductions Approach to Fair Classification. In the 35th International Conference on Machine Learning, pages 60-69, 2018.
[2] Alekh Agarwal, Miroslav Dudik, and Zhiwei Steven Wu. Fair Regression: Quantitative Definitions and Reduction-based Algorithms. In 36th International Conference on Machine Learning, ICML 2019, volume 2019-June, pages 120-129. International Machine Learning Society (IMLS), 2019.
[3] Julia Angwin, Jeff Larson, Surya Mattu, and Lauren Kirchner. Machine Bias, 2016. URL http:///wwww.pppbliicccc.c org/ siiminal-sentenciing
[4] Toon Calders and Sicco Verwer. Three naive Bayes approaches for discrinination-free classification. Data Mining and Knowledge Discovery, 21(2):277-292, 2010.
[5] M. T. Chao and W. E. Strawderman. Negative Moments of Positive Random Variables. Journal of the American Statistical Association, 67(38))422, 1972. ISSN 01621459. doi: 10.2307/2284399.
[6] Evgenii Chzhen and Nicolas Schreuder. A minimax framework for quantifying risk-fairnes trade-off in regression. The Annals of Statistics, 50(4):2416-2442 2022. ISSN 0090-5364. doi: 10. (0.121422--A021199
[7] Evgenii Chzhen, Christophe Denis, Mohamed Hebiri, and Massimiliano Pontil. Fair Regression with Wasserstein Barycenters. In Advances in Neural Information Processing Systems, volume 33, pages 7321-7331. Curran Associates, Inc., 2020.
[8] Evgenii Chzhen, Christophe Denis, Mohamed Hebiri, and Massimiliano Pontil. Fair Regression via Plug-In Estimator and Recalibration. In Advances Neural Information Processing Systems, volume 33, pages 19137-19148. Curran Associates, Inc., 2020.
[9] Kade Crockford. How is Face Recognition Surveillance Technology Racist?, 2020. URL wtwp://www...aaa/eeaaaaaaaeeeeea http://///ooo-i----acerreeeeette surveillanee-eechollo---eee
[10] Jeffrey Dastin. Amazon scraps secret Al recruiting tool that showed bias against women, 2018.
URL http://wwwwwwttt.eee wtt.://eee...oommtt....ceeeeeeee amazon- com- jobs-oossooooo wwws-aototatiioon.ooo husigahh/mmazoooscccp---eeeeeeee
[11] Moritz Hardt, Eric Price, and Nathan Srebro. Equality Opportunity in Supervised Learning. In DD Lee, M Sugiyama, U V Luxburg, I Guyon, and R Garnett, editors, Advances in Neural Information Processing Systems 29, pages 3315-3323, Barcelona, Spain, 12 2016. Curran Associates, Inc
10

---

[12] Dragana Jankov Maširević. On New Formulas for the Cumulative Distribution Function of the Noncentral Chi-Square Distribution. Mediterranean Journal of Mathematics, 14(2):1-13, 2017. ISSN 16605454. doi: 10. 10.10777500000007-072-11111111 URL https://lint http://iiinnee.rinnn... springer www.//attieeeeiooooooooooo 1007 1ttp:////00.000//0000000000-0000 ottp://w.........r.r///////..oor
[13] Jumpei Komiyama, Akiko Takeda, Junya Honda, and Hajime Shimao. Nonconvex Optimization for Regression with Fairness Constraints. In Jennifer Dy and Andreas Krause, editors, Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pages 2737-2746, Stockholmsmässan, Stockholm Sweden, 2018. PMLR.
[14] Jeremie Mary, Clément Calauzènes, and Noureddine El Karoui. Fairness-Aware Learning for Continuous Attributes and Treatments. In Kamalika Chaudhuri and Ruslan Salakhutdinov, editors, Proceedings of the 36th International Conference on Machine Learning. volume 97 of Proceedings of Machine Learning Research, pages 4382-4392 Long Beach, California, USA.
2019. PMLR.
[15] Jaouad Mourtada. Exact minimax risk for linear least squares, and the lower tail of sample covariance matrices. The Annals of Statisticx,, 50(4):2157-2178, 2022. ISSN 0090-5364. doi: 10.1214/2-A0022181 URL https: httpp:::pprjjecteuuuuue
org/ journals/ oounalssannaal--e.. awwaaanallllll. for--lnnea-reeae
snnares-and-the-B21 1ttp:////111111222a2211 http://ee....eee///////////////0
[16] Daniel Moyer, Shuyang Gao, Rob Brekelmans, Greg Ver Steeg, and Aram Galstyan. Invariant Representations without Adversarial Training. Advances in Neural Information Processing Systems, volume 31, pages 9084-9099 9093, 2018.
[17] Alex Najibi. Racial Discrimination in Face Recognition Technology, 2020. URL attps://sita: hms
iin--in--- -n--in--ffee face-
[18] Harikrishna Narasimhan, Andrew Cotter, Maya R Gupta, and Serena Wang. Pairwise Fairness for Ranking and Regression. In The Thirty-Fourth AAAI Conference Arlificial Intelligence, pages 1248-5255. AAAI Press, 2020.
[19] Roberto Imbuzeiro Oliveira. The lower tail of random quadratic forms with applications to ordinary least squares. Probability Theory and Related Fields, 166(3-4):1175-111 1194, 12 2016. ISSN 01788051. doi: 10. 10.1007//00444-011-00333 073899//..IIISS.
[20] I. Olkin and F. Pukelsheim. The distance between two random vectors with given dispersion matrices. Linear Algebra and its Applications, 48(C):257-263, 12 1982. ISSN 0024-3795. doi: 10. 10.1016/0024-375588))000) 12-4.
[21] Dino Pedreshi, Salvatore Ruggieri, and Franco Turini. Discrimination-awe aware data mining, In Proceeding of the 14th ACM SIGKDD international conference on Knowledge discovery and data mining- KDD 08, pages 560-568, 2008. ISBN 9781605581934, doi:
10.1145/1401890. 1401959.
[22] Charles Stone. Optimal rates of convergence for nonparametric estimators. The annals of Statistics, pages 1348-1360, 1980.
[23] Alexandre B. Tsybakov. Optimal rates of aggregation. Lecture Notes in Artificial Intelligence (Subseries of Lecture Notes Computer Science), 2777:303-313, 2003. ISSN 03029743. doi:
[24] Neil Vigdor. Apple Card Investigated After Gender Discrimination Complaints, 2019. URL https://ww, nytimes. httm///////1////ussio/aoaoo wwwp:eessspppeeeee-eeeeeeeeeeeee investigation. html.
[25] Qizhe Xie, Zihang Dai, Yulun Du, Eduard Hovy, and Graham Neubig. Controllable Invariance through Adversarial Feature Learning. In Advances in Neural Information Processing Systems, volume 30, pages 585-596, 2017.

---

D n
n.
Ps S
11B.11
D1,s
D 1,s
1
D'
3'
1,
D
D 2, 2,s
As D'¹
s
D
D 3, ,
2,
pls
P!s
2,
Copy
Figure
Sample splitting for constructing estimators.
A Comparison of Existing and Our Unfairness Scores
This section compares our unfairness score with existing ones. Recall that our unfairness score is defined as the maximum Wasserstein distance between any two distributions Uy|s and Uyjer all pairs of groups and s', follows:
U(f) max 22( a.
In contrast, Agarwal al. [2], Chzhen et al. [7, 8] the Kolmogorov distance DKol measure unfairness, which is defined as:
Uko(ff) max S,8'
The difference between our score and (f) is solely the choice of distance metric. Our score utilizes the Wasserstein distance, while Uko((f) uses the Kolmogorov distance. This difference arises mainly from technical reasons.
In addition, Chzhen and Schreuder [6] proposed another unfairness score, denoted by UAveW2 (f), which is defined as the average of the Wasserstein distance, as follows:
UAvgW, = inf Σ P (v
SE[M]
Here, the score places more emphasis on the major groups, as reflected by the weight of p.. This may not be desirable if the unfaimesss is more prevalent in the minority groups, which may be common in real-world scenarios.
B Estimator Details
This section describes the construction of our optimal estimator in detail. Recall that our estimator is plugin estimator in which we first estimate the parts of the terms in Eq (5) and then substitute them into Eq (5). Specifically, we construct estimators for B.11, B., per, By,, and pye where they correspond to the terms in Eq (5) as follows:
8
1
1be
Σ
1
1.99
p.
s'E(M
Bar
8_
12

---

Algorithm 1: Algorithm of the proposed optimal estimator.
Input :Tee sample Dn {(x,, S; Yi)
Output: The regressor fn-
for < 1 to M do
Calculate nt, and construct the group-wise sample Da and its duplicate D'= Partition D2 into equal-sized subsets: Di,s, D2,5, and D3
Compute the estimands P. from n.,, || from 11,,, 3g from D2 and üig from D3.a Partition D' equally into Dí,, and 2/,=
Compute the estimands 3 from Dí.s and jlg from 2,,;
end
Calculate fn using Eq (6);
return fr.
For analysis purposes, we split the sample into several subsets and pass each subset to the corre- sponding estimator (the correspondence is explained later). Figure shows an overview of sample splitting and the correspondence between the subsets and estimators. We construct the histogram of the sensitive attribute St from the sample D,. denoted as n. = (n....., RM), where n. Ki E [n] S: = s}| (upper left in Figure 1). We also construct group-wist samples D = (X,, Yi) : iiE S; = s). For each & E [M]. we divide D, into D D2.., and Da.a such that [Do.s] nb.s 2 [n./3] for b [3] (lower left in Figure 1). We n.,, D1,s, D2.s. and Da., to estimate ps. 1.3.11. B.. and A... respectively, where || is the estimator for ||B* We obtain ||3.1| from the combination of f. and ||3.|| (middle in Figure 1). Furthermore, for each s [M]] we create copy of D,,, denoted as D's, and divide it into D'1, and D'2, such that D'b, s| = n n/b, 8 2 [n./2]
for b [2]. We use D'1, and D2,, to estimate 31 and Ki respectively (right in Figure 1).
We describe the construction of each estimator below. We first define some notations. Let the ith element of Db., and D/,s be denoted as (Xt,s,i Yb,sii and (X) (.s, Yo,.)) respectively. We use the matrix notations Xt,s (Xb,,,1 ... XD,o,n,, X%,a (X,,,, ... X.,.n,,)) ) Yo,+
(Yr,,,1 mo.) and Yr,-- = (Y,,s.1 "Y, K.,.ni..) )T. We define the ordinary least square estima- tors for the subset of the sample Do,s and D/ as follows:
B {11xx
((1 Xo Vooe
Xb.s
1bb,
Tbb
( (Xxxx))
1 (Xb.0)
86.-
Xb.0
1bb.5
construct each estimator as follows:
(ps) We use the empirical mean defined as p. ne/n.
([8,1)) )
We use the norm of the OLS estimator. We define ||A = 1| if ng 18d, and |,3.|| otherwise.
([ I))
Since | E [.E[M] Pel1 we construct its estimator as ||3.|| E EeE[M] P. 1
(3.)
We use the normalized ordinary least square estimator; B. 32.e/ /1,32 if n, > 18d, and
3, otherwise.
((.)
We use the empirical mean; A #s,
E X3.
(3)) We employ the ordinary least square estimator; 3 Bi.0 if n. > 12d, and B otherwise.
( We use the empirical mean; P' -
th. E X2,,,
22, nf 12d, and Pl 0 otherwise.
Some estimators change their behavior based on the condition n, 18d or n, > 12d, which is done for technical purposes in later analyses.
13

---

Recall that the final regressor is constructed as follows:
fa, s) = |3.1 (3 Po) + E
(B..
o e'E[M]
Algorithm shows the algorithm for our estimator.
C Bayes Optimal Regressor under Our Modell
This section presents the proof of Lemma I, demonstrating the Bayes optimal regressor under the model Eq (2). To establish this, make use of key result from the work of Chzhen et al. [7]: Theorem (Chzhen et al. [7]. Assume, for each E [M], My has density. Then,
inf E F:D
= inf Σ P. sEIM
where the infimum is taken over all the regressors that satisfy the demographic parity. Moreover, letting DD and v" be the minimizer of the Ihs and rhs, respectively, we have Vii = V and
<E J'EM
fbp(x,s)
F Pe M/
o (r-((((e,)))
(9)
Here, we denote vy. as the distribution of f (X, Ffis as the cumulative distribution function of f(X, S) conditioned on = 8, and Fiss as the inverse cumulative distribution function, given by (t) inffy R f)= (v) 2 t}.
Building upon the results of Theorem 9, we establish the proof of Lemma
Proof of Lemma J. Building upon Theorem 9, we can derive the Bayes optimal regressor under the model Eq (2) by obtaining closed expressions the cumulative and inverse cumulative distribution functions Fy-1= and F is To obtain these closed forms, apply certain transformations f"'(X, S) that render it a random variable following standard normal distribution. Let & and d-1 be the CDF and inverse CDF of the standard normal distribution, respectively. Through elementary calculations,
we have:
S s) =P([8, X) StS s} (t)
(3t (3, X - -Ma) S ox |8:1|
(8) p.)1s
ox ||
Here, we can readily observe that ox]|s]]| (Br, X (a)) follows the standard normal distribution under conditioned on S = X ~ -NN( N(H,, ox.) conditioned on S = Consequently, we have
Fr-1o(t) = + σ | (t (3) p.))
(10)
The inverse function of F (t) can be obtained by equating the right-hand side to and solving the resulting equation for I, which leads to
F F (p) ox 2 + (B),
(11)
By substituting Eqs (10) and (11) into Eq (9) in Theorem 9, we obtain the desired claim.
D Details of Fairness Analysis
In this section, we provide evidence the guarantee of our estimator's fairness consistency. Specifi- cally, we present the following theorem.
14

---

Theorem 10. For any 8 E (0, 1]. the regressor in Eq (6) is (1/2, consistently fair.
We prove the above claim by utilizing Theorem which is shown in the main body, as follows:
Proof of Theorem 10. We can confirm the claim by comparing the bound obtained in Theorem with the definition of (2. connsistttt fairness in Definition 2. In particular, we can set C'
48 and no = n 2 481n(M/6)/ min, Ps to satisfy the definition of (g. conssisst x V min.e(M fairness.
Next, we provide the proof of Theorem 2. To this end, we prove the following two theorems:
Theorem 11. Let fn be the estimator of fDP defined in Eq (6). Then, almost surely. we have
W2 Bals: (isnl))) - 2B ( i.)) 1 KBei i..) -Ma)
Theorem 12. I 2 (48 (18ln(M/8) - -36d)/ ming Ps, we have for d E (0,
P 3s E wM1 (Bs. -1m) > /
P
48 48|n(M/5)
S 8.
min, nps
36d
Combining Theorems 11 and 12 immediately yields Theorem 2.
Proof of Theorem 11. This proof investigates the distribution of fflss" It is straightforward to verify that, conditioned on S = fx, S) follows the Gaussian distribution with mean
|| l1 BB. 1a0) + Σ par (B2. )
s'E[ad]
and variance
11
We thus evaluate the Wasserstein distance between the distributions Vfnis and vfnls' using the Wasserstein distance between Gaussian distributions. Given two Gaussian distributions N(u, o²) and (u'', o²²), the 2-Wasserstein distance between them obtained [20]
ON,
(u -4')²²² + (a 0a-
Therefore, have
W (y 1o V F()))) = =13.11 ((3s. (181)((((,) P..) -Barr Hoo - (is') )
<AB² (1 - ii) v/ (B 11)
which concludes the claim.
Proof of Theorem 12. We start by deriving the concentration inequality for (Bs, Ps)) conditioned on B. and n. Note that 3, 0 if < 18d. Conditioning on B, and n., we observe that (B., Ms (---)a)) pi,) follows a Gaussian distribution with mean zero and variance ox /n.,.. Therefore, for any E [M] and
(B.. (a) > E B,, n. < 1 (n, > 18d} exp
nz,at?
20
Taking the expectation with respect to 3. and using the fact that n3, 2 |n,/3| 2 n,, for n, 2 we obtain the following inequality for [M] and > O:
PP( (B... Ms - P.) t/m } < 1nn > 18d) exp
n252
120 x
15

---

Using the union bound for t >> O, we have
(- n2t²
P(3s [M,] (Bes Ba) > 1/m
Σ .E[M]
1 [n,
18d) exp
(- 120
(12)
We now derive sufficient condition on t such that the expectation of the right-hand side in Eq (12) is less than First, we note that
ngt
1 [(n > 18d] exp
120
(n, + 18d)t²
n2
< 1 < > 18d] exp
12o
+ 18d
(ng + 18d)
expp
240
Taking the expectation and substituting the moment-generating function of the binomial distribution, we obtain
(n, + 18d)12 )
exp
240
18dt²
(1 1 + P&G
<exp
24x
24
18df2
S <xxp
nps 1-c 200
240
Since 1 - 2 (1 - 1 l for
[0, 11, if t2 1//200x I 1, we have
(n, + 18d)t²
)
exp
24
18dt²
(1 - 1mp.t
S exp
24
24
Hence, E( E(exp(- + 18d)1²
)1 S 6/M if 2 Ø [1---)uu,- +18d I oxV
24
In( M/() because
2
min, np, +36d
(1- 2 1/2. To ensure 12/240x < 1, we require n 2 (18ln(M/8)3366)) min, Ps.
E Proofs for Norm and Direction Estimators
This section presents the proofs for Theorem 4 and Theorem 5. Our strategy for proving these theorems is to use the hyperellipsoid to interpret the distribution the OLS estimator. Specifically, we begin by defining E, 1 T and expressing the OLS estimator 9 as
( xTxe) m2
8 3 -,,!!
(13)
where & follows a zero-mean Gaussian distribution. Eq (13) shows that, conditioned X, B of " We
follows multivariate Gaussian distribution with mean 3 and covariance matrix establish that, under the condition || 9 is supported on hyperellipsoid E(r, 3: 22
En). where
of F(r; A) {a: Rd (x T A(x c) < r) denotes the hyperellipsoid with 0, Rd and symmetric and positive-definite matrix A E Rdxdd
To prove Theorem 4 and Theorem we adopt the following strategy. First, we provide an approxi- mation of the hyperellipsoid E(r, A) using the maximum eigenvalue of A A-1, -,,ie., Amax (AA our context, A oz Σn, and we then focus the concentration inequalities regarding >max (2,, )).
In
Finally, combine these tools prove both theorems.
Lemmas regarding hyperellipsoid. We present two lemmas that relate to the approximation of the hyperellipsoid E(r, A). Specifically, we demonstrate the following two lemmas:
16

---

Lemma 2. For r > 0, c E Rd, and a symmetric and Dasitive-definis matrix A E Rddd we have
E(r, A) _ Er
c,,,,)
Lemma 3. For > 0, c R., and a symmetric and positive- matrix A Rdxd if Tdmax (mnax(A1)) (A-) < ||e]? we have
inf #EB(r.C,)
| Amax (A-1).
|ell
a
These lemmas provide insight into the approximation of the hyperellipsoid E(r,, c, A) for given positive value of r, vector in Rd, and positive-definite symmetric matrix in Rddd Lemma states that the hyperellipsoid Err; A) is contained within hyperellipsoid E(r>max ((r)max(A-)) (A-1), I). Lemma shows that, under certain conditions, the minimum angle between a point in E(r, c, A) and the vector is bounded below by quantity that depends r, and A.
Proof of Lemma 2. It is trivial that Amin (A)T is positive semi-definite. Equivalently, we have for any x E Rd,
T Amia (A))( 2 0
x AAx Ax 2 x Amiu (A)
(14)
From Eq (14), for any a E E(r, c, A), we have
x Ami (A)Ix x Ar Sr.
Hence, for any x E E(r, c, A), we have
1x S
Amax (A (A-)rr
Amin (A)
which indicates I E ErrAmax (A-1),c,1)
Proof of Lemma 3. Let č = c/|lell, and define set E(r, C,,,e,, A) = (x E Sd 1 By > 0, yr E
E(r, A) Then, x E E(r, A) if and only if
inf (1x c) A(yx - c) Sr. 7>0
(15)
We can rewrite the left-hand side of Eq (15) as
(r, Ax) (c Az) + Ac)
= (z, Az) (x (2-
(c, Ax)
(x, Ac)²
+ (c)
(x, Ax)
(x, Ax)
Hence,
((x, Ac) V 00 (x, Ax)
inf (7xx - c)T A(yx - c) = (c, Ac) 720
Consequently, c(r,c, A) if and only if
(x, Ax)
(c, (c.
r
S ((x, Ac) 00
(16)
||
From Lemma 2, we have
I
( ||>||
inf =EB(r.
C
inf ze E 1)s...)) inf =EBumaalA 2)no.))
|x
x).
(17)
By Eq (16), x E F.(Amax (A (A- )r,)) C, T) and only if
1 ||c|2 Amax (A-1) s ((z, 0)3.
(18)
Combining Eqs (17) and (18) and the assumption yields the claim.
17

---

Least eigenvalue of the empirical covariance matrix. The previous lemmas, Lemmas 2 and 3, provide valuable insight into analyzing the randomness regarding Ç. However, to account for the randomness of X, we must also control the lower bound on the least eigenvalue of A in Lemmas 2 and 3, which corresponds to the least eigenvalue of 1 XX X in our context. To this end, we leverage the high probability bound presented by Mourtada [15] based on the small-ball condition. We state the following probabilistic bound and expectation bound.
Lemma For μ Ra and xxx O, let X1,..., Xn iid (H, (x ox-I, and let X (X1 (X1...X), ...)
Then, for > 6d, we have
L (xxxx) stje
21e
4/6
P Amin
x
Lemma For μ Rd and ox O, let X1 Xn iid Then, n. > 6d, we have
~ N 0x ox1), 1), and let X (XI.... T...
((xxxx)))
21e o
1+ -6)
E
Xmmax
To prove Lemma 4, we utilize Corollary 3 in Mourtada [15]. Specifically, use the following theorem.
Theorem 13 (Corollary 3 in Mourtada [15]). Let X be a random vector in TRd such that E|||X]?? < too, and let Σ ] Ler Σn +/ Ei=1 X,X,, where X, are i...d copies of X. Given C > 0 and a E 1I, assume that for every 0 E Rd {00 and > 0,
p(10,)) s 2
S (Ct)
(19)
Then, 7/ S a/s, for every t 0.
Σn ż t3 +
with probability at least 1 - (C't)un/o, where C" = 30 14%%
Eq (19) is known as the small-ball condition.
Proof of Lemma 4. To take an advantage of Theorem 13, we need to ensure that X, satisfies the small-ball condition in Eq (19). Let Σ,, _ X. Then, the expected value of E,, is equal to o T+ = Σ, ie.. E E = Given 9 E [(). (8. /o |0]| follows the non-central x² distribution with degree of freedom 1 and centratral parameter (0, μ1² / [1012. Consequently, we verify the satisfication of the small-ball condition of X, by confirming that for a random variable Z following the non-central x2 distribution with degree of freedom 1 and non-centrality parameter 2 there exists C' and (0, 1] such that
P(ZsP) (Ct)
The cumulative distribution fucntion of the non-central x² distribution with degree of freedom has a closed-form using the error function (See [12] and references therein). Specifically, letting erf(s) be the error function, defined as
2 VT 0
erf(2)
dx,
the cumulative distribution function of Z is obtained as
1
t 8-
(+
V2 ))
P(Z < t erf
+ erf
2
V2
Since = an even function, we have
Pfz < t2
1
Sprte
Atte
e
2/3 dr
p-- c /122//
2
18

---

1
--2 +
I. e-
2t
A
1
Att
V2T
1
phte
/2
22 A-t
Noting that 1/3 Se
(0w(A-ti)
for x. E (A
1, + 1), we have
A+t
(OVLA- 6)
P(Z S
dx
L.
(20)
2T J
We verify that X, satisfies the small-ball condition by utilizing Eq (20). Recall that (0,x,))/o3)) 11112 follows the non-central x2 distribution with degree of freedom and non-centrality parameter X (0, / for any 0 R \ {0}. By Eq (20), we have
K0, X.X 2 x
2
(DV
1012
Noting that ||> = xx 110122 + (0, 1)² we have
pf ((10.x10 S 22012 |1]
2
(0, p
covia-e)) e))²
1 +
x 10
π
(ov(A-01
(1 + X2)e
t.
(21)
We divide into two cases, À > and À S f, to derive an upper bound on Eq (21).
(Case À > Since (A +)² x² 2\t + 2 2 2 + X2 - t?, upper bound on Eq (21)
is obtained as
10V(A-1)22
(1 + A²)e
π
2
(1 + x2)e L
For positive numbers and b, va + S Va+ + Vb. Using this fact, we have
(0VeA
(1 + (1+
π
V 2 tee 22_
Since function
+ xe 2/- 1/2 admits maximum on E (0, (0, of -/2, we have
vx= - Fe Se 1/2 Consequently, we have
V (1+ 101
16
i
(1 + t2)t,
(22)
πe
where we use the fact (1 + e 1//222 < 8e
(Case E t) We can easily verify that
2 (1 + X2)e
10v13 m
2 (1 12+ 12)
1 <
(23)
7
19

---

Combining Eqs (22) and (23), we have for every & > 0,
P
(0, x.)
16 πe
(1 + t2)t.
For t2 E E0,, (0,-
3
me 4
we have
16 (1
8
Te
12)1 S
V
+
+
ne
me
4
For 1 2 - +
8
1 +
+
ne
t
4
(
[
Te
1.
4
πe
Hence, for every > O, have
R (0, x
<(10,x>)=<000
=2
-
V
+ V
1 1+
xe
S 7//4
te
4
confirms X; satisfies the small-ball condition with C' 7//4 and a = 1. Application of Theorem 13 yields the desired claim.
Proof of Lemma 5, For a positive random variable X, we can express the expected value of X as E[
00 P > t)dt. Applying this to problem, obtain
((xXTx)
))) -
(xxXx)
E
Amax
P
Amax
dl
n
(xxTx))
P
Amin
16- dl.
Now, let us set C =
20e.0
Using the previous result, we can rewrite the expectation of interest
0x
((2xTx)
-) -C+ [ I (mmin ((xx)x) <t < at
E
Amax
sC+
(Ct-l)"/dt dt
=0 - =c+0%((1-
n -1 7 (-01--00 の)
-o 1 =0
6
n
which yields the claim.
Proofs of theorems. By utilizing the results of Lemmas 2 to 5, we provide the complete proofs for both Theorem 4 and Theorem 5.
Proof of Theorem 4. We begin by demonstrating that obtaining an upper bound on the expected eтror the direction estimator can be reduced to finding lower bound on the inner product Specifically, straightforward calculation yields
A.
g"
|
3*
3"
))-
E
-2 1
E
(24)
||
|| 115
Therefore, it suffices to establish lower bound on E[An].
20

---

Taking advantage of Lemma 3, we derive a lower bound on An. Let = ( o From Lemma 3, it follows that
-8))
oēr
An 2 /
118-1122 Amax (Im
provided that r S 11118*11///0 min (Ix²). Since vI x for [0, 1], it follows that
oer
- An S
||8 1, Amax (>n)))
as long as r S 11|13~12 Amax [in))
Next, derive an upper bound the expectation of 1 An. Noting that conditioned X, follows the x² distribution with degree of freedom d, we have
E[1 An X
n11/8/12 of Xmax
11
} (1
E
1
+1
A,.)
X
En
of Amax (Im'
n2 n21.3 11
E
Amax Ezn
X
+P
X
||3
1:2n
o max 2:m
Ler
<2
Amax 2
X
(25)
|| 22
2d
Amax (2mz))
(26)
113*
where we use the Markov inequality to obtain Eq (25).
By utilizing Eq (24), upper bound on the expected error be obtained by deriving upper bound on the expectation of Eq (26). The random variable in Eq (26) is Amax (2,²), which allows us derive the upper bound the expected error by obtaining upper bound on the expectation
of Amax 1 To accomplish this, we apply Lemma 5. The upper bound from Lemma 5 can be substituted into Eq (26), resulting in the claimed upper bound.
Proof of Theorem 5. We first utilize Lemma 2 to get an upper bound on the squared error of the norm estimator. Let r = (B 8*) m (3 (*). From Lemma 2, we have
B 30 1|
oer Amax [mm])
n Application of the triangle and reverse triangle inequality yields
oer Amax EEp
|1
Amax [In! = |||| = |1 +
equivalently
or Amax 1m
(1 [1
s n
Taking expectation conditioned on X yields
E
[|3|]| - 11,311) X
E
Xmaa (Im=)) X
2 d
Amax
(2
(27)
11.
where we use the fact that r follows the x distribution with degree freedom d to obtain the last line. Again, application of Lemma into expectation of Eq (27) yields the claim. D
21

---

Details of Upper Bound Analyses
This section presents a detailed proof of the upper bound stated Theorem 1, which is achieved through analysis of the estimator constructed in Section Specifically, we establish the following theorem:
Theorem 14. Let Bn be the estimator constructed in Section 5. Then, there exists a universal constant C > 0 such that for any 8 (0, 1) and n 2 12(3d v Al(MM/6)) [ Pa.
S &C- B.B en (2))
L
V B B
To establish the validity of Theorem 14, we begin by proving Theorem 3, which demonstrates that the estimation eиrог can be decomposed into the sum of errors associated with individual components. Subsequently, we derive upper bounds for the estimation errors of each component. Finally, we synthesize these results provide a proof of Theorem 14.
F1 Proof of Theorem 3
commence the error analysis of our estimator by decomposing the estimation error, as presented in Theorem 3. Recall the statement of Theorem' 3
Theorem 15. For the estimator defined in Eq (6), the mean square deviation from fop is bounded above by
1/2
1/2
Σ P.E.
E
E
|
E
(Bs Ma
n.
xoxE
(113.1
11511)
71
+
ME
1/2
1 |2]
1/2
(B' B3, -3. )
x 8: E
3. - 3t 32/113311
[2.
+ E
Σ
Der
n.
+
*'E(MN]
2
1/2
2 (po. - Pp Hor)
)
Σ S'E(M)
por Po (82,
P/. Mer)
n.
+
Σ
.E(M]
We provide proof of Theorem 15 as follows:
Proof of Theorem 15. We begin by decomposing f.(X,S) (X, into six terms. Recall the
definitions of fn(x,s) s) and (2, 8):
fa(x, 8) =113.11
Ba, (.))
Σ
Per (os
s'E(MN)
3r
(B -1B3-]
[
x p4
+ Σ
Per (B3r,
Through elementary calculations, obtain:
- ( = -133-11 Bs, us - (ss)
||.3.| - [|8:11) (Bs. X- us)
+ +1135|1 33s - 833
X us) + Σ P. (3's - Bz (los)
||33
d'E(M
Σ
Des (82, Ml )sst + Σ (E- P (28)
s'E(M]]
s'E(M
22

---

By the Cauchy-Schwarl inequality, for two random variable Z1 and Zz, we have E - -2) = E| + E[ By applying this fact into the expectation of Eq (28) conditioned on S and n. multiple times, we have
(n((X - (x)
E
(fx(X,)))-Bp(X. (BP( (
Σ P.E.
E
- /BP
5= =8= n.
S 8
<M[M]
1/2
$
Σ P&E
E
(113-11 Bs. ps pss)) 5= s.
(29)
+E[M]]
((13)) - 11.8.11 [ X ps))
E
S
83
X - μss ))
E
|18t111
3s
S
|1
2
Por (B - B Alo) 1
+ E
Σ
S = 8, n2
MEIM
2
1/2
E
Σ
per Po (B2 R'. med)
S 8, n.
S'E[M
1/2
2
+ E
Σ (6s - Pb.) S'EIM]
S = 8, n2
S
In the subsequent analyses, we derive upper bounds for each term in Eq (29).
(First term in Eq (29)) Due to the splitting of the sample, || [|. 8., and As are independent conditioned on n.. Thus, we have:
1/2
[|3-|] 3s us - ius) iis))
E
8, n.
(113.1)
Bos p6. -(as)) 21 )2121
1/2
E
1/2
1/2 Dis)
E
|
(Bas {
E
This term matches the first term of the desired bound.
(Second term Eq (29)) Since [|3.11. 3s. and are independent conditioned on n., we have
[| | (3.. X - xxx))-m)) s = s,
E
= x (1 - |18.11 [
where we use the fact that X
(4 ~ N N(,, o²x11 conditioned on S s, and Bg Sa-1 almost surely. This result corresponds to the second term of the desired bound.
(Third term in Eq (29)) Since
14 N NO. I). we have
1
1s ))
E
13.
3.
X
s,
| ||
23

---

8
1
3,
|
which corresponds the third term of the desired bound.
(Forth and fifth terms in Eq (29)) These terms are independent of S, so we can omit s from the condition, resulting in the fourth and fifth terms of the desired bound.
(Sixth term in Eq (29)) This term does not contain any random variable when n. is fixed. Thus, can remove the expectation, yielding the sixth term the desired bound.
F.2 Estimation Error Analyses for Each Component
This subsection presents an analysis of the estimation errors associated with each component estimator. In particular, we investigate the estimation errors j... [|.. 3s, 8/ and jbg.
F2.1
Estimation Error Analysis for jis
Here, presents the proof of the following theorem. Theorem 16. Given E [M]. n,, > 18d, have
60x
E (U, paa)2
sup
vES9
ns
Proof of Theorem 16. Given v S4-1, we have
(V. He Pa) n. (v,, (u,E((Hs Ao) - As) n. nn]o).
According to the definition, jr, is an average of na,s i...d. random variables following N(us, 03 I). <²1)) I). which implies Ei(us PO)(H Pa)) [n.]] = x I.
Hence, we have He P. N(, ma..
n3,
Consequently, obtain:
xx Iv
E (U,14s Mss (uo) P20)2m1))
v.
n3,s
0
(v,0) v)
113,8
113,
Since 13,, 2 [n./3] ng/6 for n. 2 6, claim follows.
F.2.2 Estimation Error Analysis for |331||
Here, we present the proof of the following theorem.
Theorem 17. For any [M], we have
E
-1311-111111
2 n
1/2
10
1 [n < 18d]
ns + n
(p.
p
.E(M)
ME[M]
Proof Theorem 17. By combining the definitions of [3.]] and |3 and utilizing the Cauchy- Schwarz inequality, obtain
1/2
E
[|3.]] - 13+1
n.
1/2 n.
=E
Σ <C[M]]
p. (1821) 13:11 + Σ (p. - ps p
Sc(M]

---

1/2
S
Σ sE|M]
Ps
[|3.11
11
(6.
ps)l1
(30)
sE[M
Next, we derive an upper bound for the first term in Eq (30). Applying Jensen's inequality, we have:
E
Σ
Da
[|3.1|
|1531] 11
+E[M]
f1g E
[188.]
(2.
M
Σ
ng
1 1 > 18
(122.
11::1]
n. + Im S |
ME[M]
Using the fact that n1,s 6d for n, 18d and employing Theorem 5, obtain:
2
E
Σ Ps
[1B.11
|5
KE[M]
21c 21c200.d o2d
| 1 n.
ns
1+ 11 6
+ Σ
1(n,
S 18d]
n 111,8
n
sE[M]
.E[M]
189e 10 o2 Md
B
Σ Ii S 18d)
sE[M]
where the last line follows from the fact that 11, 2 [n,/3| 2 n,/6 for n, 2 6, - S 1/2 for
6
ns 2 18, and || < B.
F.2.3 Estimation Error Analysis for 3,
Here, we will prove the following theorem. Theorem 18. For any [M], we have
756 10 oodd
8
ifn, > 18d,
E
3,
x 11
1
otherwise.
8- Proof of Theorem 18. If n, < 18d, 3, = O, and we thus have E[I
|ل
|1
=
8- |3:
||
For n, > 18d, we have 122 6d. Application of Theorem 4 yields
8
84c o0 oRd
E
3.
<
1 122 6
|
x
3 P1z
We get the claim in the same manner as the proof of Theorem 17.
F.2.4 Estimation Error Analysis for 3r Here, we will prove the following theorem. Theorem 19, Given E [M]. let E. E[X.X]]ffo for X. N(us, L). Then, if n 12d, have
22 B3 - 8:) 1:)1²²m
2
4dd 2
+ 504c oe
nx
25

---

To prove Theorem 19, we utilize the following theorem presented by Mourtada [15]. Theorem 20 (Theorem 3 in [15]), Let be random vector in Rd such that statisfies the small-
ball condition of Eq (19) and B[1ı=~/=x11]] S kd for some > O. where Σ E|X XXX Let
E.n 11 E X,X,, where X, are i..d copies of X. If 2 -a- 12a 12o-1111100 (n110_1))
L [E(T((Sn)>))
d + 8C"K K
d
where a and C' are as Theorem 13.
Proof of Theorem 19. We can easily confirm that 3 ~ N(5 _
ni,, (Ei,,) )1) conditioned on nt. and of
X where Σi 1,,0
X1 (Xi,)) T. Noting that E[(3' B3) 53) nx
(=)
ni..
we have
E
1//2 m.
B3' - p:)]1 [1.
( - (2)) (B'r - :3:) { mm
Tr
Σ. E
2 E Tr Eg (E),)) -1) m
(31)
We apply Theorem 20 the expected trace term in Eq (31). To do so, we need check X1,s satisfies the small-ball condition of Eq (19) and the kurtosis condition E|||2, 4/3
xi "|||=,,>ii,>,, [1 S kd.
The small-ball condition is confirmed by the same manner in the proof of Lemma 5, with C 71/ and a 1. Here, we prove the satisfication of the kurtosis condition. For a multivariate Gaussian random variable X ~ N (14 A) such that Amin > 0, Σ = E 1414 + A, and || x| =
1/2 x
E (X, Σ x
=Var (x, + (B((X,-
Since we have
E (X, M x)]
+ +)) d
Var (X, x>] -211(2-1A~~1 (mM) + +A)) 111-----A--1 m4
-2TH(E-1A) + +2TTE=222=-E1111
-2Th(E- (up + +A)) - T
=2d - 20-22///11/(1/ (1, 11) 2d.
Hence, the kurtosis condition satisfies with 3.
Application of Theorem 20 into Eq (31) yields
E
E (3 8:
| n.
< odd n
+ 504c
d n1,0)
)²²
provided that n, 2 12d. We get the claim from the fact that n/,, 2 [n,/2] 2 n,/4 /4 for n, 2 4.
F.2.5 Estimation Error Analysis for A Here, we will prove the following theorem. Theorem 21. Given
[M] and Rd, if,, > 12d, we have
4o ||
(u. RC po) p [m]]] <
E
n
26

---

Proof of Theorem 21. By definition, have f'g (
l)
conditioned on n. for n2 12d.
m2
Hence, we have
1e12
E (v, Plg
Me) [2.
n222.
We get the claim following the same manner of the proof of Theorem 19.
F.3 Some Auxiliary Lemmas
This subsections introduce some auxiliary lemmas for use to prove Theorem 14. Specifically, we demonstrate the following lemmas:
Lemma 6. Let a1 any E R be arbitrary numbers. Then, we have
]
E
Σ [EIMM]
ae
ppa²
1
Varlas].
Lemma 7, For a constant e 0, we have for any E [M]
E n, 1nn, > ct} < 1
po(n +
Lemma 8. Let e 0 be constant. If 2c/ min Pe have for any [M]
P(n, S sc
Proof of Lemma 6. Since np. follows the multinomial distribution with the parameters n and p., using the variance and covariance of the multinomial distribution, have
2
E
ap. P&) M
agps(11 Ps)
ag0s PsPs
n
71
SE[M]
8,6 taMls
O.Ps
Σ ag
0g
SE[M]
e
Let ESEAA Psa.. Then, we have
Σ
aspo(a, - ā)
.E[M]
Σ (s - -a)2 + Σ
ap, - σ.
.E(M)
sE[M]
Σ (a a)²= Var[os].
.E(M)
Hence,
27
1
E
Σ
a. po)
Var[ag].
sE(M]
27

---

Proof of Lemma 7. For a random variable X following the binomial distribution with the parameters
and p. El E pin+iy(1 (1 -1 p)=+) [5]. Since n, follows the binomial distribution with the
parameters n and Ps. we have We have
n
1
(ns
> c]]
1
E
1+
1( > cf
14 +
< + [1+cc1pe )E
T4 + 1
1
(1 - - -p.) < 1
Pa(n+1
Ps(n 1)
Proof of Lemma 8. From the Chernoff bound, we have
( Ps)
P(n, S sc) S exp
2p.
Under the assumption, we have S npp/2. Then, we have claim.
( - -pa) 2 n/8, which gives the 3p,
n
F.4 Proof of Theorem 14
Proof of Theorem 14. We begin by characterizing the estimation error by each component's 's estima- tion error shown in Theorems 16 to 19 and 21. Specifically, we characterize the estimation error using the following error terms:
mean,s
sup vES,-1
E
(v. Ms (a)
||3. 11)²2 m.
Br
-E113,
||3:11 11 |m.
coef,x
//////
3% 33 113
Cooef'
E
E [[( Ms: m/
mean'
sup
oES
12
proh
Σ
(por - (B
s' <'EMM]
where Σ E[ for X, Nus, We analyze each in Eq (7) one by one. (First term in Theorem 3) Recall the first term Theorem
1/2
3.
n.
(B Ms
From the Cauchy- -echhar-Scwarrrcooo inequality, we have
1/2
1/2
1/2
E
3.
E
E
|8
[iB.1]
B
+ Cnorm
28

---

By definition, 3, = -0 for n, S 18d, which indicates that
1/2
(Be1tts - (b.)
E
0.
In the case of n, 18d, by utilizing the fact B, and fta are independent conditioned on due the sample spilitting and Bg Sa-1, we obtain
(B..1s - pa) mm S sup E
(v, (ao)
)aa)) n. 6 mean,
HEB
Consequently, have
E
3.
1/2
(Bs Bs 10:11-1i, ir.
>
|m 1 S (B Cnarm emman, [n, 18d]. (32)
1/2
(Second term in Theorem 3) Recall the second term in Theorem
2 n
1/2
ax E
[
Using the notation Cuorm, we have
2
1/2
E
|13
[8:11
n.
x Cnorm
(33)
(Third term in Theorem 3) Recall the third term in Theorem 3
3
8.
E
B.
71
B
Substituting Ecoef,s yields
1/2
8g
x
B.
3,
x
|: Ccoef,
(34)
||::1|
(Fourth term in Theorem Recall the fourth term in Theorem
2
1/2
E
Σ Pa (3 ME[M]
8r 8%.
n.
Due the sample splitting, 8 and it are mutually independent. Also, we have EK 100--3,,40 -3, 0. Hence,
E
Σ
Do (3 -3- 17
n2.
M
= Σ
1 E
(3) - 8r 11.)
n.
Σ .
E
(B2- - Br p.) nh.
1 [n, 12d].
Since E((A)(1))
-x I = E, (1
12 )o I, we have
2
E Σ
(B Br, 11.)
n.
RE[M]
29

---

1/2
Σ
E E
ox21
(3) (8%- B:)
n.
L(ns >> 12d]
n/2,3/
M
Σ
E
Σ/' B3 8:) 8:)11(m1
n.
1 1(n > 12d
P 1nn, 12d}, (35)
sE[M]
ME
where the fact Σg 2 E, (1- xig.. )o I, and for symmetric matrices A and B such that
A - B, Av) 2 (u, Bv) for any R. For 18d, the error is zero because ni =
(Fifth term in Theorem 3) Recall the fifth term in Theorem
2
1/2
E
Σ +E[M]
Do(32
P1,
(a))
71
Since R' are independent, we have
E
Σ
P.
(S f/.
-1s)
n.
sE|Mi
Σ
p E
(3t, Rl, moi? n.
1[n. 12d}
.E[M]
+ Σ
PoPor l(m, < 12d, ns < 12d) 12d)(32, (B), (33, pw)
[
144d M
11
sup E (v. R'. ma) n.
Line 12d]
n2
SE[M]
DESA-1
Bd 2
m is In,, 12d) +
(36)
xE[M)
(Sixth term in Theorem 3) Recall the sixth term in Theorem 3
Σ J'E(M]
(pe - ps (38) Hor)
which is equivalent to Eproh-
By combining Theorem and Eqs (32) to (36), we get
E (f) ( -1xxx)))))BB(x.s))
S Σ P.E .E[M]
(B Cnorm Cmean, 1 1n, 18d} + x a 3 Ceaef,s
1/2
Σ Br o 1fn. > 12d}
J'EMM]
1/2 (2))
(2) 12
27
Σ
B2 B e ss 1fns > 12d} + o
+ @prob
8 M
The triangle inequality gives that
30

---

E -FBxx)))
S Σ 7ps
B e mean, 1in 18d}]
E
[uorm E E[e meaan,s Lnn, > 18d]]
.E[M]
2 E x
( + xx 1180 E (ccect.o)
Σ
E Pp 1 12d]]
sE(ad]
E
B2
e mean's 1m > 12d]]]
+ TE +E[ (prool +
By applying Theorem 16 and Lemma 7, we have
6 Line > 18d}
60x Pn 1)
1+ 1
E 2 meann, [n > 18d}]
E
T1s
18d
Also, from Theorem 17 and Lemmas and 8, we have
27
189c2002M4
E
Horm
S
ox
E
Lin,
18d]
1ls
Σ (Øs 11)311111 sE|M
n
SE(M
378c 27
of
Σ E
lime
S 18d}
2n
+ 2
Var Var(1 (1161)))
378c 37.c
36d
2 max, || 11
Σ
Pfn, I 18d]
+
n
n
.E[M]
378c o2
36d
2B²
+
np,/ +
n
ME[M]
378c 27.
o
2B2
n
provided that n 36d/ min Ps. By utilizing Theorem 18 and Lemmas 7 and have
756e ag
E
<E
lin, > 18d}
+ +Pfm S 18d}
xx 193 122
756c 10 ofd
1 18d
-np./8
p |195 13
756e 10 ofd
1+
x |
18d
provided that 36d/ min Ps. Application of Theorem 19 gives
[dd
2
E Pppe e 1 l(n, > 12d}}]
<
540e +
oe 10
1in, > 12d}
n
n2a
40y
40
E
1 (n,
> 12d)
+0
ps
+
n,
n
By Theorem 21, we have
no 40
S Ps 40
E De eeean's 1( 12d)
<
1 In. > 12d}
n n
n
Application of Lemma with a₂ = (B) Me) into eprob yields
E [pro s Var( S 1212
n
31

---

Synthesizing the results so far, there exists an universal constant C' >> 0 such that
E
B²
Md
Σ sE[M]
Cps
+
Palt
n
n
|| &pp
Poo
P
U²
+
Σ
C
+
+ C
+ 0
n
+E[M]
Consequently, there exists universal constant C
0 such that
E
-brr)))))
B2
Md RBB² Bd
0x
B
+
n
n
n
Then, the dominating terms match the claim.
G Details of Lower Bound Analyses
This section provides the proofs of the lower bound analyses results.
G.1 Proof Lower Bound Theorem
Theorem 22. Md 16, there exists universal constant C > O such that for any >> 0 and 8 (0,1). 1).
(, 6) 2 C o BM
Proof of Theorem 22. The Varshamov-Gilbenn bound guarantees that there exists a subset V C V such that | 2 (d-118 and du (w,, v.)) 2 - (d-1)/8 for any v, E V. With the choice of 16 M / 2 B²n,, we confirm by Theorem 8 that inf a K Evew DKL (TT.lI : 1)
< = d+1
max..vev DKL (Ta n TT) S In((21/44/2 2 M 1)/16 - 1. From Theorem 8 and the
fact (V,; v()) 2 (d 1)/8, we can apply Theorem with -EOEMN) Ps (Evcii B.).² dd-1 16
M )o /2n From the fact that E
((t1) (1-p))))) due [5]. there exists an universal (EVEIn B,,
n2,
adArd o(2)) We can get the
constant C such that E 2
C(
2 ExE(M
B²
n
Eve P. = B and
claim by confirming that there exists Bı,.., B& such that (1 Σ
EE(M
EVeei B,))
B. < B. Because for Bg =.. BM = B, tending Bj to 0 results in M Exe(M) goes infinity, it is confirmed.
G.2 Proof of Theorem 6
Proof of Theorem 6. Since the distribution of n. invariant against 0 E O, we have
sup Eg 0)
0c
sup Eg [((h=:)) |r]] Lece
max Eg E(fm: 0) 00
32

---

Σ
Eu
E(Jn: 0) [m]
DEG
Given possibly dependent n., application of the Markov inequality yields
sup e
Eg
>
Po
AEG
If in f E(; 0) ()) 2 e for any 0,0' E (J; < implies EJJ 2 e for any 0' ê such that O * 8'. Hence, there exists partion (Felage of all the measurable functions f IR x [M] IR
such that E < e) S Fg for all 0 Ô. Consequently, we have
Pof E =a/na))]
sup AE
Eg E(fni:) 0)
2 E
Σ AE
O
Application of the Fano's inequality and data processing inequality yields the claim.
G.3 Proof Theorem
To prove Theorem 7, we show the following more tight lower bound.
Theorem 23. Let 0 and 6' be the parameters of the distributions such that 1 llp for all [M]. Then, have
11,11 dg <
20x
inf E(J;0) ( E(J;0) SEC
de
|..|BB B2
| 1/ (1
11 16111
1+
Σ aE(M]
Pe
xx
1,3.11
||
40
|| 1
|1,3
||
1)
1/4 11' 122
Σ De (Bs--2s. B') (Bx 12, M'EM]
2
40
Theorem 23 immediately gives Theorem
We utilize the sufficient condition for the constrained optimization problem over Banach space. Let Z be Banach space. We say function f 7 IR. is Gateaux differentiable if the limit limy- f(=+ru)-f(s) exists for any open set U C Z, any z E U, and any u E We denote Gateaux derivative of ff at Z, linear mapping from E Z lim, f(2tru)- (2f(2). We abuse 0 to denote the mapping that always outputs 0.
Proof of Theorem 23. Let qs and q' be the density function of X, with the parameters (B., and (8', p!), respectively, regarding the base measure X. Since X, follows the Gaussian distribution, can choose as the Lebesgue measure. Given E [0, 1]. we have
&.) ((): 2n + (1 (
-E Ps / (n(((x,)) fa (2. 8)) g)())))))))))))))))())))))))(( (1- (f) fe. (z, +))² (((()) X(dx). SE[M]
33

---

Because (1) p!) is convex for f, and L is Banach space, it is minimized for any u E C
dr (nE(f yu; + n)E(f ye. S. 7=0
0.
The dominated convergence theorem gives
d (n ru, B. + + -)) Tu; 1 d7
= E (x) Sa (z, 8))u((, 8))((()
SE(M]
+ + (1-1n) (1_m))((z,s)) - (a s))u(z, s)g,())) Ndxz)
E Ps (1 SE[M]
(nfo. n (x, (x) + (1- 11-n)s (2x, (t) s)A(dx).
Consequently, (f.:B....) + - (]] ; Bi, v() is minimized
(sx,8) nSa. (Ir, s) (x) (1 v))Ssr (x, (x)
ng. (z) + (1 7))((x)
Hence,
nE(F yu; (1., n){(f ru; B¹, (/)
Σ Ps I
(g) + (x) (fa. (I, for (z, s)) 2) Mdx)).
11 - (z),(())((()))
With 77 3/2, we have
11 (11-n)9s (1))))) (z) + (1-1))/(1
4 (.(=)
2V
(x(2)
1 (z)
4 cosh(
{ In (.(xr
(x)
Let n1 = (1, + (%).
Then, we have
(1)())
exp
40 ||
1s/122
|| - 1''11
V (2
40x
1
1
1
M4 11/1 1
exp
||
11s112
(2T)
20
20
2
((
11/
11.
11/
2
1
Jsa,
2
2
1
1/s 1/ 1
cxp
||
11
(2
20
20
2
Also, we have
(x(
(z)
34

---

exp
|
Hell
|| 1''l"
20 X
20
11g
14g
1/g
exp
1
x
2
2
exp
(a
sl Ms - [U/1)
x
Let X2 N(ps xx 1). Then, we have
E(i: 1. V 8(fiB', v!)
(fa.... (X..
fer (Xes 8))²
2 Σ
P.e x
cosh( 1 (X, M4g |b. 1k/))
sE[M]
200
- 12
(fe. (X,, 5) fBr s))2
Σ
P&e
20
(37)
cosh
[,, - M/. Ra|11pbs 14%
.E[M]
20x
where the last line is obtained from the Cauchy-Schwarz inequality. By definition, we have
Ja. (Ir, 8)
J (xr, 8)
|.B.
IIB. ||
1/.
||
|1:5%11
||3211
2
Me Hla
Σ Ps (1.5
Byy (xr)
Ber + Bzg
2
of E|I
Conditioned on ||X - P.ll for > 0, Xx follows the uniform distribution over the (d 1p-spe centered p.. For random variable U uniformly distributed over the 1p-spe centered at origin with the radius ElU] 0 and E[UUT)= =//aT. Hence, for vector Rd and scalar E IR, we have
((u, ((u,Xe X. -Me) +c) Rell poll=r]
E
||l|| + c².
An elementary analysis yields that ||XX, Ho 2| Gamma g 20 ). where Gamma(k, 0) denotes the Gamma distribution with the shape parameter i and scale parameter 0. From the upper bound of the hyperbolic cosine cosh(x) < -²2/2 for a vector Rd scalars E R and c' > 0, and random variable y ~ Gamma(k; 0), we have
(1001 + c
E
cosh(c'
v7)
|1ll c2)
22
2m m
EE
2
2m
||aa|2
T(k: + m +1+11
r(k: + m)
gm
n
m!
d
I(k)
[(k)
m=0
22
Iík +
m)
[(k: + m)
+
2
m!
d
r(k +1)
I(k)
m=0
k| m| 2
22
k+1
20
1
+
2
1+
d
2
35

---

where we use the fact that the hypergeometric function 2 (F,
Em=
Fla+m) g [(o]
md
(1 =) for some b, provided |a| < By setting
1.3.1
|
||3 ||
||
||:55 ||5
|
14
1
+
||
11
2
Us. U/'s ))
+
Σ
pe
(Bx B'y. + Be + B'
2
<'EM
d' 1|1s- - 1',1l
20
k 2
and = 20
have
(f (X,,8) 8) fst (X.: $))2
E
cosh
X, Ph Ba|l||Ma - Hllll)
20x
|.3.133. ||
1/:11133
|-
|22
(1+ |1ke 111l(3)
1t
+ (<{
13.1
1
1/
=
+
||3611
4
1|Bal1
11,3111
2
-Be + (Ber 3er + B
He Hla 1))
2
11
Σ Ps <'(M
1
2
4
(38)
Combining Eqs (37) and (38) yields the claim.
G.4 Proof of Theorem Proof of Theorem 8. It is easy to check that d, = O, and for any v, of E V.
1, 1,,.
B
1,Ber
Bu,
Ber
Σ
Porl1Bun Du.11B
1
3'E(M]
2
Per Bun *
Σ
Σ
(Va.i -v'e)'
d
vE(d-1)
2 de (V,,
Σ d'E[M]
Pe Bg
d-1
Since the density function of the Gaussian distribution is I integrable, E(ʃ;0) = oo if is not 1 integrable. Hence, inf, E(f;0,) E(J;0w) = inc (ff:0.) v (Ef;;w)) and we thus can apply Theorem 7. Then, we have
inf inF 1
Σ P.
Σ B, YEIW
du (v., vc)
M
Conditioned on n., the KL-divergence between kn. and IT Jn. is obtained as
ox
Σ n
Ilvi - 1=
18,
Blr + 20 Nur.orBu. Ber
20 ME|M]
20
36

---

Hence, we have
20 B²
DKL. (Toola ; mB = Σ
oř(d-1) dH (V,, U.).
SE(M/
37


Reviews:
[{"review_id": "OrINhAT1Ew", "reviewer": "Reviewer_okbq", "summary": "This paper studies the statistical minimax error of building a linear regression model under the constraint of demographic parity. \nIt generalizes the result in Chzhen and Schreuder [5] by allowing the slope coefficients to change with sensitive attribute rather than just\nthe intercepts. The authors provide both upper and lower bounds of the minimax error, and show that they match in the dependency on $n$.", "questions": "1. The statement made in line 136-137 should be explained more clearly. In particular, why does enforcing strict demographic parity result in a constant function?\n\n2. The authors consider $(\\alpha, \\delta)$-consistently fair regressor while Chzhen and Schreuder [5] consider $(\\alpha, t)$-valid estimators (see DEFINITION 5.2 in [5]). Are they equivalent? If not, why do the authors consider a different type of fair regressor in the definition of the minimax error. \n\n3. Equation (4) needs to be explain, especially the second inequality. Also, I think $\\beta$ here should be $\\beta^*$. ", "limitations": "See weaknesses above. ", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "Although this paper uses a framework similar to  Chzhen and Schreuder [5], it covers a very important setting where there exists both direct and indirect discriminations. The analysis begins with Lemma 1, which can be easily derived from Chzhen and Schreuder [5]. However, to obtain the upper bound of the minimax error, the authors need to characterize the errors of approximating each component in (5), which is one of the main challenges in this paper. They develop new techniques in Theorems 4 and 5 to handle this challenge. I think it has made significant contribution on top of   Chzhen and Schreuder [5].", "weaknesses": "1. This paper assumes the covariance matrix of X is an identity matrix for each $s$. It will be better to allow a more general matrix $\\Sigma_s$. \n2. It only covers the case where $\\alpha\\leq 1/2$. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> The statement made in line 136-137 should be explained more clearly. In particular, why does enforcing strict demographic parity result in a constant function?\n\nThank you for your query regarding the explanation provided in lines 136-137. The occurrence of this particular phenomenon can be better understood by considering the learning algorithm's limited ability to access the underlying distribution. Here, we can conceptualize the learning algorithm as a mapping from a sample $D_n$ to a regressor $\\hat{f}_n$. It is important to understand that, given a particular sample, the algorithm is designed to yield a particular regressor.\n\nFor a specific sample, $D_n$, we see that the density it perceives is non-zero across all underlying distributions. This is due to the inherent nature of a Gaussian distribution, which, irrespective of its parameters, is supported on the entire real vector space. Despite the probability being small, there is still the potential for a specific sample, $D_n$, to be observed across all underlying distributions.\n\nViewing the situation from this perspective, it is clear that a corresponding regressor $\\hat{f}_n$, learned from $D_n$, must adhere to the strict demographic parity constraint across all distributions. This obligation is based on the premise that any given distribution has a non-zero likelihood of producing the sample $D_n$. This understanding can be generalized to all samples that are processed by the algorithm. Thus, it follows that the algorithm should generate a regressor that upholds the strict demographic parity constraint for every underlying distribution. The sole function that consistently satisfies this stringent demographic parity constraint is a constant function. We hope this elaboration addresses your query satisfactorily.\n\n> The authors consider $(\\alpha,\\delta)$-consistently fair regressor while Chzhen and Schreuder [5] consider $(\\alpha,t)$-valid estimators (see DEFINITION 5.2 in [5]). Are they equivalent? If not, why do the authors consider a different type of fair regressor in the definition of the minimax error.\n\nThank you for drawing a comparison between our proposed $(\\alpha,\\delta)$-consistently fair regressor and the $(\\alpha,t)$-valid estimators as defined by Chzhen and Schreuder. While these two concepts are interconnected, they are not equivalent and possess nuanced differences. To clarify the difference between these definitions, we use $(\\gamma, t)$-validness to represent Chzhen and Schreuder's definition.\n\nSpecifically, when we choose an appropriate unfairness score, an $(\\alpha,\\delta)$-consistently fair regressor transforms into a $(Cn^{-\\alpha},\\delta)$-valid entity for some constant $C > 0$. Similarly, a $(Cn^{-\\alpha},t)$-valid estimator, given a particular $C > 0$, can be redefined as an $(\\alpha,t)$-consistently fair entity.\n\nThe distinguishing factor here is the treatment of $\\gamma$: while the $(\\gamma,t)$-validity allows $\\gamma$ to remain constant, our proposed concept of consistent fairness necessitates a diminishing $\\gamma$ as $n$ increases. Although our definition of fairness consistency may be more constrained than that proposed by Chzhen and Schreuder, the feature of converging towards a strictly fair regressor is a favorable attribute in practical applications.\n\nAdditionally, it is pertinent to mention the disparity in the unfairness scores we use compared to Chzhen and Schreuder. Our approach measures the disparity between the worst-case pair of groups, whereas their method averages the disparity across all groups. Our method of measurement is not unique but is endorsed by other researchers as well, as demonstrated in [2,7,8] where similar unfairness scores have been used. In comparison, the average-type unfairness score [6] could unintentionally favor the majority group, which may not always be an optimal approach as it often overlooks the greater unfairness experienced by minority groups. This is an important consideration as such situations frequently occur in real-life contexts.\n\n> Equation (4) needs to be explain, especially the second inequality. \n\nThank you for your inquiry regarding Equation (4), particularly the second inequality. We'd be pleased to provide further clarification.\n\nThe second inequality found in Equation (4) illustrates the variability of the norms $\\|\\beta^*_s\\|$ under the restriction set forth by the first inequality. More specifically, a higher value for $B$ allows a more diverse values for the norm $\\|\\beta^*_s\\|$.\n\nWe can interpret the left-hand side of the second inequality in Equation (4) as a product of two factors: the weighted average norms, $\\sum_sp_s|\\beta^*_s|$, and the averaged inverse norms, expressed as $\\frac{1}{M}\\sum_s\\frac{1}{\\|\\beta^*_s\\|}$. As the norms increase, the first factor (weighted average norms) has the propensity to grow, while the second factor (averaged inverse norms) tends to rise when the norms decrease. Maximizing the product of these two elements involves a delicate balancing act: the norms of some groups need to be large, while the norms of other groups need to be smaller. As such, the left-hand side of the second inequality can increase when the norms $|\\beta^*_s|$ display diversity. I hope this explanation clarifies your doubts."}, {"review_id": "XcCrUFdZdN", "reviewer": "Reviewer_6KUa", "summary": "The authors study the problem of minimax optimality for the linear regression model under demographic parity constraints from the fairness literature. They provided matching upper and lower bounds for the model that is considered in the paper. ", "questions": "Please check the cons. Slightly lower score because of lack of experimental work.", "limitations": "N/A", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "Overall:\n\nThe paper is well-motivated by presenting both direct and indirect discrimination that occurs in real-world settings and the proposed model accounts for it. The theory is well-laid out and the difficulty is elucidated in the main paper with details left to the appendices. However, there isn't any experimental work.\n\nPros:\n\n(A) The model differs from the prior literature (Chzhen and Schreuder) and is well motivated in Section 1 and Table 1. \n(B) The technical difficulty of both the norm estimators and the direction estimators is presented in equation 7. \n(C) The key takeways that the optimal error is independent of mean but depends on the variance is intriguing.\n", "weaknesses": "(1) How does this compare to the results of Chzen and Schreuder is unclear. There is no unified setting which captures both models.\n(2) Also, there is no experimental work which would help us know the tightness of the proposed upper bounds (constants). \n(3) Some of the writing can be sharpened and there are multiple typos.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> (1) How does this compare to the results of Chzen and Schreuder is unclear. There is no unified setting which captures both models. \n\nThank you for drawing attention to the comparison between our work and that of Chzen and Schreuder. Your observation is astute, and we appreciate the opportunity to clarify. \n\nTo provide a comparative perspective, we have detailed a side-by-side analysis of our model with that of Chzen and Schreuder's in Lines 77-91. The fundamental difference lies in how each model approaches direct and indirect discrimination.\n\nFor direct discrimination, our model is crafted to address disparities originating from the entire regression coefficient. On the other hand, Chzen and Schreuder's model is specialized to address discrimination stemming exclusively from the intercept. When it comes to indirect discrimination, their model, due to its design constraints, doesn't fully capture the indirect discrimination arising from the interdependencies of non-sensitive features with the sensitive attribute. In contrast, our model acknowledges such potential interdependencies, allowing for a more nuanced handling of indirect discrimination through group-dependent means. These distinctions are concisely summarized in Table 1.\n\nYou've correctly identified the discrepancy in the settings of our model compared to Chzen and Schreuder's. This distinction primarily arises from the metrics chosen for measuring unfairness. Our method evaluates disparity by focusing on the worst-case pair of groups, whereas Chzen and Schreuder's methodology calculates the average disparity across all groups. Our approach is consistent with prior studies, as seen in references [2,7,8]. An average-based unfairness score might inadvertently favor the majority group, potentially underrepresenting the unfairness faced by minority groups — a situation often observed in real-world contexts. We contend that our method, backed by existing literature, provides a more equitable assessment, specifically reducing undue favoritism towards majority groups.\n\nWe are grateful for your thoughtful inquiry and hope this explanation brings added clarity to our approach.\n\n\n> (2) Also, there is no experimental work which would help us know the tightness of the proposed upper bounds (constants). \n\nThe core of our paper lies in the theoretical insights related to minimax optimality for demographic parity-constrained regression within a linear model. We are of the strong conviction that these theoretical revelations, irrespective of any accompanying experimental evidence, offer substantial contributions in their own right.\n\nIn relation to the multiplicative constant in the upper bounds, we agree that its current value, $C=37044 e^{10}$, may suggest a potential for further refinement. Nonetheless, our study's primary emphasis remains on the exploration of parameters' influence on minimax risk, rendering the precise tightness of the multiplicative constant a secondary concern in this context. Your thoughtful attention to this detail is genuinely appreciated, and we assure you that we will consider delving into this aspect in more detail in our future research endeavors."}, {"review_id": "JHTuXu6PFg", "reviewer": "Reviewer_TKh2", "summary": "This paper investigates the minimax error in regression under the constraint of demographic parity (DP). In contrast to earlier works, this paper studies both direct and indirect discrimination and their effects on the estimator. In addition to proposing an algorithm to construct a regressor achieving a desirable error, they provide extensive theoretical analysis characterizing upper and lower bounds under the DP constraint.", "questions": "In your model, you mentioned that indirect discrimination mainly impacts $\\mu_S$ while direct discrimination is reflected via $\\beta_S^*$. My understanding is that, direct discrimination is for the “model” itself, i.e. $\\beta$, while indirect discrimination has influence on the data set. Is my description accurate?", "limitations": "The authors addressed them at the end of Section 8.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "1. The paper is nicely written, with a clear structure and a comprehensive explanation of a large number of notations.\n\n2. It studies a simple but interesting, important problem, which indeed catches attention and makes a good contribution to the community.\n\n3. The introduction of direct and indirect discrimination is novel and realistic, and the examples are helpful for readers to understand those notions.\n\n4. The theoretical analysis is comprehensive. The discussion in Section 4 is interesting to read and may provide insights for future work in this area.", "weaknesses": "I did not find particular weaknesses for this paper.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> In your model, you mentioned that indirect discrimination mainly impacts $\\mu_S$ while direct discrimination is reflected via $\\beta^*_S$. My understanding is that, direct discrimination is for the \"model\" itself, i.e. $\\beta$, while indirect discrimination has influence on the data set. Is my description accurate?\n\nYou are largely correct in your understanding. The distinction between direct and indirect discrimination hinges on how the sensitive attribute affects the predicted outcome.\n\nDirect discrimination arises when there's a change in the model parameters due to the sensitive attribute, leading to varying predicted outcomes across different groups. Conversely, indirect discrimination occurs even if the model parameters remain unchanged or independent of the sensitive attribute. \n\nTo illustrate using a linear regressor, let's consider $f(x,s) = \\mbox{address} \\times \\beta$, where $\\beta$ represents a regression coefficient. At first glance, it might appear that the predicted outcome remains consistent irrespective of the sensitive attribute because $\\beta$ is independent of the sensitive attribute. However, if we consider a scenario where the \"address\" variable is influenced by the sensitive attribute (a phenomenon often seen with race, largely due to historical factors), the predicted outcomes will indeed vary based on the sensitive attribute. We refer to this phenomenon as indirect discrimination.\n"}, {"review_id": "OWDxGtMQeS", "reviewer": "Reviewer_1oyt", "summary": "This paper studies the linear regression problem under a new definition of $(\\alpha, \\delta)$-fairness consistency as a fairness constraint.\nIn particular, the authors derived that under the constraint of $(\\alpha, \\delta)$-fairness, the minimax optimal error is $dM/n$ when $\\alpha$ is less than 1/2. Moreover, they provided an estimator that achieves this optimal rate of convergence. ", "questions": "It would be great if the authors could discuss and provide more understanding on how restrictive the assumption that $\\alpha <= 1/2$ is. \nIs it a necessary condition for achieving the minimax rate of dM/n? \nAlso, how should one think about solving for the case that $\\alpha > 1/2$? \nHow does the fairness score proposed in the paper compare with other fairness scores in the existing literature?\nThe authors mentioned that misapplication of the findings in the paper to other models might result in discriminatory treatment. Any discussion on the robustness of the proposed algorithms, especially under misspecified models?\n", "limitations": "The authors have pointed out the restriction of the proposed models and cautioned against misusing the algorithms for non-linear models. ", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "This paper established matching upper and lower bounds on the minimax optimal error and proposed a regression algorithm that achieves this optimal error for the linear regression model under a specific fairness constraint. The theory and method extends the current literature to cover partial coefficients and non-sensitive features on the sensitive attribute. The paper is well presented and articulated. The authors also provided detailed proofs which hightlighted the technical difficulties in the minimax analysis, as well as a novel estimator for achieving the minimax optimal bound. ", "weaknesses": "It would be great if the authors could discuss and provide more understanding on how restrictive the assumption that $\\alpha <= 1/2$ is. Also, how should one think about solving for the case that $\\alpha > 1/2$? \nThe paper is lacking empirical study/examples which I feel would be nice given the subject under study. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> It would be great if the authors could discuss and provide more understanding on how restrictive the assumption that $\\alpha\\le 1/2$ is. Is it a necessary condition for achieving the minimax rate of dM/n? Also, how should one think about solving for the case that $\\alpha > 1/2$? \n\nThank you for raising these important inquiries regarding the condition that $\\alpha \\le 1/2$. To shed light on your questions, I'd like to begin by assuring you that our lower bound result is indeed applicable to scenarios where $\\alpha > 1/2$. Therefore, it should be noted that the minimax rate of dM/n might still be affected even when $\\alpha > 1/2$. Furthermore, we should consider the potential for the minimax rate to exceed dM/n if $\\alpha > 1/2$.\n\nDiving deeper into the challenges associated with the $\\alpha > 1/2$ case, they primarily arise from the necessity to manage the non-linear regressor. Given that the estimation error of the mean of the non-sensitive features stands at the order of $n^{-1/2}$, the outcome distribution similarly deviates at a scale of $n^{-1/2}$ when a linear regression function is implemented. Consequently, achieving an $n^{-\\alpha}$ deviation for $\\alpha > 1/2$ calls for the use of a non-linear regressor. This, however, complicates the analysis process. We hope this provides a clearer understanding of the issues at hand.\n\nWe are currently continuing our research in the case that $\\alpha > 1/2$ and have yet to fully understand it. One potential approach to understanding the minimax risk for $\\alpha > 1/2$ might be to examine the bias introduced during training. Although our present analyses offer a comprehensive lower bound on the sample bias, there could be additional refinement regarding the bias originating from the training process. We are eager to explore this further in our upcoming work.\n\n> How does the fairness score proposed in the paper compare with other fairness scores in the existing literature? \n\nThank you for your question regarding the comparison between the fairness score proposed in our study and other fairness scores that are currently available in the literature.\n\nWhen we consider references [2,7,8], the primary distinction is situated in the selection of the divergence measure. In the context of our work, we have chosen to employ the 2-Wasserstein distance, whereas these studies have favored the use of the Kolmogorov distance. This difference in selection can be associated with the distinct norms embraced in our respective outcome spaces. To clarify, our fairness score is constructed upon the foundation of the $\\ell_2$-norm, while their scores are based on the $\\ell_\\infty$-norm. However, I would like to stress that the underlying principles of these methods are largely congruous.\n\nMoving onto the comparison with the method proposed in reference [6], our score is identified from the pair of groups that exhibits the most pronounced differences. In contrast, their methodology evaluates an average of the divergences of outcome distributions across all groups. This methodological choice inherently gives precedence to the majority group, which might only be suitable in some contexts. We have often noticed, particularly in real-world circumstances, that unfairness tends to be more conspicuous within minority groups. Therefore, our approach aims to address this concern more effectively.\n\nFor a more comprehensive comparison, please refer to Appendix A in the supplementary material.\n\n> The authors mentioned that misapplication of the findings in the paper to other models might result in discriminatory treatment. Any discussion on the robustness of the proposed algorithms, especially under misspecified models?\n\nYour viewpoint on the robustness of model misspecification is certainly thought-provoking. We must admit, however, that our current algorithm might not be completely resilient against model misspecification. For instance, if the sensitive attribute influences the variance of non-sensitive features, our algorithm may risk compromising the fairness guarantee. Hence, further investigating the robustness against model misspecification is undeniably an important area for our future work."}]

Author rebuttal:
We would like to express our gratitude to all the reviewers for dedicating their time to providing such careful reviews. We also greatly appreciate the high evaluations that our papers received from the reviewers. Please refer to the individual responses for our answers to the questions the reviewers raised.

Meta-review: The paper extends the Chzhen and Schreuder's framework to address both direct and indirect discrimination in linear regression models under demographic parity. It innovatively establishes matching upper and lower bounds on the minimax optimal error through theorems and introduces an algorithm that achieves this optimal error. While the work is theoretically strong, it lacks empirical validation as no experimental results are included. I suggest the authors consider adding some experiments if possible.
Decision: Accept (poster)