Meta Optimality for Demographic Parity Constrained Regression via Post-Processing
Authors: Kazuto Fukuchi
Venue: ICML 2025 poster (2025)
Keywords: fairness
minimax optimal
regression
demographic parity
Primary area: theory->learning_theory

Abstract: We address the regression problem under the constraint of demographic parity, a commonly used fairness definition. Recent studies have revealed fair minimax optimal regression algorithms, the most accurate algorithms that adhere to the fairness constraint. However, these analyses are tightly coupled with specific data generation models. In this paper, we provide meta-theorems that can be applied to various situations to validate the fair minimax optimality of the corresponding regression algorithms. Furthermore, we demonstrate that fair minimax optimal regression can be achieved through post-processing methods, allowing researchers and practitioners to focus on improving conventional regression techniques, which can then be efficiently adapted for fair regression.

Meta Optimality for Demographic Parity Constrained Regression via Post-Processing
Kazuto Fukuchi 12
Abstract
issue of unfairness in machine learning.
We address the regression problem under the con- straint of demographic parity, a commonly used faimess definition. Recent studies have revealed fair minimax optimal regression algorithms, the most accurate algorithms that adhere to the fair- ness constraint. However, these analyses are tightly coupled with specific data generation mod- els. In this paper, we provide meta-theorems that can be applied to various situations to val- idate the fair minimax optimality of the corre- sponding regression algorithms. Furthermore, we demonstrate that fair minimax optimal regression can be achieved through post- post-processing methods, allowing researchers and practitioners to focus on improving conventional regression techniques, which can then be efficiently adapted for fair re- gression.
To mitigate unfair bias, researchers have developed di- verse methodologies for constructing accurate predictors that ensure certain fairness definitions. These method- ologies can be categorized into three main types: pre- processing techniques that modify the training data (Feld- man et al., 2015), in-processing methods that incorpo- rate fairness constraints during model training (Chuang Mrouch, 2020; Zhang et al., 2018; Du et al., 2021; Cotter et al., 2019; Khalili et al., 2023; Jovanović et al., 2023), and post-processing approaches that adjust the model's out- puts (Menon & Williamson, 2018; Chzhen et at, 2019; Jiang et al., 2020; Schreuder & Chzhen, 2021; Chen et al., 2023; Xu & Strohmer, 2023; Xian et al., 2023; Zhao & Gordon, 2019; Chzhen et al., 2020). Methodologies of each type have been proposed for various faimess definitions, includ- ing demographic parity (Pedreshi al., 2008), equalized odds (Hardt et al., 2016), multicalibration (Kleinberg et al., 2017), and individual fairness (Dwork et al., 2012). Each of these fairness criteria aims to address different aspects of algorithmic bias. These diverse methodologies have signifi- cantly advanced the field of fair machine learning, enabling researchers and practitioners to address fairness concerns in various contexts and applications.
1. Introduction
Machine learning systems have become increasingly preva- lent in decision-making across various domains, including healthcare, finance, and criminal justice. While these sys- tems promise more efficient and data-driven decisions, they also raise significant concerns regarding fairness and eq- uity. As machine learning models learn from historical data, they can inadvertently perpetuate or even exacerbate exist- ing societal biases, leading to unfair outcomes for certain social groups Numerous instances of unfair behaviors in real-world machine learning systems have been reported, including biased recidivism risk prediction (Angwin al., 2016), discriminatory hiring practices (Dastin, 2018), in- equitable facial recognition performance (Crockford, 2020; Najibi, 2020), and biased credit scoring (Vigdor, 2019). These reports underscore the urgent need to address the
Recent advancements in fair learning algorithms have led to the development of methods that achieve the best possible predictive accuracy while adhering to specific fairness defini- tions, particularly demographic parity. Such advancements were achieved by constructing fair learning algorithms and proving their minimax optimality under regression (Chzhen & Schreuder, 2022; Fukuchi & Sakuma, 2023) and classifi- cation (Zeng et al., 2024) setups. The fair minimax optimal algorithm is an algorithm that satisfies the faimess definition and minimizes the worst-case error taken over a certain set of data generation models. No fair algorithm can outper- form the fair minimax optimal algorithm in the sense of the worst-case error, as the minimization is taken over all the fair algorithms.
'Inttittee of Systems and Information Engineering, University of Tsukuba Ibaraki, Japan "RIKEN AIP, Tokyo, Japan. Correspon- dence to: Kazuto Fukuchi <fukuchi @cs tsukuba..c.jp>.
While these optimal methods represent significant progress, they are often tightly coupled with specific data generation models, limiting their applicability to a broader range of real-world scenarios. For example, Chzhen & Schreuder
Proceedings of the ndnd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Meta Optimality for Demographic Parity Constrained Regression via Post-Processing
(2022) and Fukuchi & Sakuma (2023) each employ certain linear models of the outcome with Gaussian features, albeit with different specific formulations. Zeng et al. (2024) work under assumptions including that the regression function is within the Hölder class and that both the margin and strong density conditions are satisfied. The dependence on these particular data distributions and model assumptions can restrict the applicability of these approaches, potentially hindering their adoption in diverse applications where the underlying data characteristics may differ significantly from these specific conditions.
Notations For positive integer m, let [m]] {1, m] and Am denote the probability simplex over [m]] We de- note the indicator function by 1. For real values a and b, we define a V b = max a. b} and A b = minfa, b). For a sequence az indexed by t E T, we represent the family (aT) as a. The first derivative of a function f RR - R is denoted by Df. Given an event & E 3 in probability space (Z, 3. v). we denote its complement by E and its probabil- ity by PE{ For random variable X from (2,3, v) to measurable space (X, X)), we denote its expectation and variance by [x] and V. [X]] respectively.
2. Problem Setup and Preliminaries
2.1. Fair Regression Problems
Our contributions (Meta-optimmlltty We address the limitations of existing analyses for fair regression by es- tablishing a meta-theorem that applies to a wide range of scenarios. This weta-theorem provides a connection be- tween the minimax optimal error for fair regression and that for conventional regression, allowing for rates tailored to various situations by leveraging well-established results re- garding the minimax optimality in conventional regression. Our approach can combine with minimax optimal regres- sions under diverse smoothness assumptions (e.g., Hölder, Sobolev, and Besov spaces (Donoho & Johnstone, 1998: Giné & Nickl, 2015)) and minimax optimal deep learning methods (Schmidt-Hieber 2020; Suzuki, 2018; Suzuki & Nitanda, 2021; Nishimura & Suzuki, 2023).
Consider a fair regression problem with M 2 2 social groups. Let X' and 5 C I be the domains of fea- tures and outcomes, respectively, where we assume P is open and bounded. For each social group E [M] (e.g., male and female for gender), let X(s) E X and (*) E Q be random variables on a probability measure space (2, 3. (s),, representing the features and outcomes of an individual in group 8, respectively. The goal of the regression problem to construct a (group-wise) regres- sor f., mappings from X' to Ω indexed by s E [M], that accurately predicts (() based on X The ideal regres- sor, known as the Bayes-optimal regressor, is defined as J.. = arg min, E,, ((f((()))) - Y {()) and is given by (X(e)) By, (Y(s) x We use ,',, and ,xx, to denote the laws of (s) and ((),, respectivelyy. Additionally, we denote the law of fj..s (X(6)) by Hf.s-
(Optimal fair regression by post-processing) We pro- pose a post-procsssing algorithm that leverages an opti- mal conventional regression algorithm. Guided by our meta-theorem, this construction ensures minimax optimal- ity under the assumptions employed by the conventional regression algorithm. Since the proposed algorithm is post- processing, practitioners can concentrate on refining con- ventional regression methods, which can then be seamlessly adapted for fair regression.
Given samples consisting of n, i.idd copies of (X(()) y(s),, the objective of the learning algorithm is to construct a regressor fr. that maximizes accuracy while satisfying a fairness constraint. Let n = -.e n2 for notational con- venience. We now introduce the definition of fairness, define measure of accuracy, and provide the definition of the fair optimal algorithm.
(Convergence rate analysis for optimal transport map estimation in Wasserstein barycenters) A key compo- nent of our algorithm is optimal transport map estimation within the Wasserstein barycenter problem, which seeks distribution (often called the barycenter) that minimizes the (Wasserstein) distances to a set of distributions. The opti- mal transport map is a mapping between distributions that achieves the minimum cost. One of our main contributions to provide a convergence rate analysis of a transport map estimator for the Wasserstein barycenter problem, which may be of independent interest. The analyzed estimator is based on Korotin et al. (2020), but they did not provide a convergence rate analysis. The detailed discussion will appear in Section 7.
Fairness We employ demographic parity (Pedreshi et al., 2008) as our fairness criterion. A regressor f. satisfies de- mographic parity if its output distribution remains invariant across all groups s E [M].
Definition 2.1. A regressor f: satisfies (strict) demo- graphic parity if, for all 8, E [M] and for all events E, P H. (X(()) E E3 = PM,,, (x(6)) E E}.
Let F(ux,)) denote the set of all regressors satisfying de- mographic parity for given laws ,x.--
Instead of enforcing strict demographic parity in Def- inition 2.1, we adopt the concept of fairness consis- tency (Chzhen et al., 2020; Fukuchi & 2023).
All the missing proofs can be found in Appendix A.
2

---

Meta Optimality for Demographic Parity Constrained Regression via Post-Processing
Definition 2.2, A learning algorithm is consistently fair if fn. converges in probability an element of F(ux,)) "",,. RM approach infinity.
transport map 0 R R that realizes the infimum
/ (==== 0:0fN=w
(2(),'') inf
Definition 2.2 implies that consistently fair learning algo- rithm eventually constructs regressor that satisfies strict demographic parity given a sufficiently large sample size.
where dit denotes the pushforward measure of v/ by 1 Given probability measures Vi...., Mk. the Wasserstein barycenter problem with weights w, E D is defined as
Accuracy We evaluate the accuracy of a given regressor by measuring its expected squared distance from the fair Bayes-optimal regressor. Given probability measures v, a measurable space (2,3) indexed by [M] and weights w; E AM (known to the learner), we define the squared distance de, between functions fa: Z - IR indexed by E [M]] as
inf Σ W (Mi.
(2)
RE[A]
We refer to the unique solution of Equation (2) the barycenter of v. with weights w.. The optimal transport map from vi to the barycenter of is is denoted by &5. Building on these concepts, the fair Bayes-optimal regressor is obtained as follows:
&y (1,
E ws (U.(t) (c())) (dz) NE(M Wadb, (for
Theorem 2.3 (Chzhen et al. (2020)). Assume that p* ad- mits a density for all E [M]. Then, the fair Bayes-optimal regressor is given by
Σ SE[M]
(x) (0pp, o (x)))
The fair Bayes-optimal regressor is defined as the regressor that satisfies strict demographic parity and minimizes the deviation from the Bayes-optimal regressor:
Theorem 2.3 reveals that the fair Bayes- regressor characterized by the Bayes-optimal regressor fū, and the optimal transport maps 0r oy Throughout the paper, we assume yyy, admits a density for all μ. P and s E [M] so that the condition of Theorem 2.3 holds.
f arg min (f fa.) (.E()
The accuracy of regressor f. is then evaluated by &x (f., fi.).
2.3. Potential Minimization and Optimal Transport Maps
The transport maps in Wasserstein barycenter problems are characterized by the minimizer of multiple correla- tion over congruent potentials (Korotin et al., 2020). Con- gruent potentials with weights w: E A are convex and lower coni-continuous functions u : R + E such that Σiety (z) = z for all = E Ω where ul = sup, (zx - u(x)) is the convex conjugate of u. Given probability measures v,, the multiple correlation of v. with weights w. for congruent potentials u; is defined as
Optimality The fair minimax optimal algorithm for a set of distributions P is consistently fair algorithm that achieves the fair minimax optimal error over P. The fair minimax optimal error over P is defined as
(p)
inf sup Ey Ldxx. fai H.EP
(1)
where the infimum is taken over all consistently fair learning algorithms, and Eg.- denotes the expectation over samples. Thus, no consistently fair learning algorithm can outperform the fair minimax optimal algorithm in terms of worst-case expected deviation.
C(u:u.) =
Σ w/s KE(A]
u,dyy
Let u," denote the optimal congruent potentials that mini-
2.2. Fair Bayes-Optimal Regressors and Optimal Transport Maps
mize v.) Through the analyses by Aguch & Carlier (201 Álvarez Esteban et al. (2016), we obtain the follow- ing characterization of the optimal transport maps:
Recent analyses have characterized fair Bayes-optimal re- gressors using optimal transport maps that arise in the Wasserstein barycenter problem (Chzhen et al., 2020; Chzhen & Sehreuder, 2022). Given two probability mea- sures V/ and v', the optimal transport map with a quadratic cost function is the unique solution of Monge's formulation of the optimal transportation problem between and v', i.e.,
Corollary 2.4 (Agueh & Carlier (2011); Álvarez Esteban et al. (2016)). Let 8r be the optimal transport maps from v. to the barycenter of v. with weights w. Suppose that for all E [b]] admits densities. Then, 0f Du,; for i E [Rt].
We use the notation W2 hecause W2 is known as the 2- Wasserstein distance.
3

---

Meta Optimality for Demographic Parity Constrained Regression via Post-Processing
By Corollary 2.4, can obtain the optimal transport maps 0. by solving inf, u congruent v.))
Note that similar assumptions Assumption 3.2 are also employed in studies on transport map estimation, including Hütter & Rigollet (2021); Divol et al. (2024).
3. Main Result
We use the following complexity measure of the class of transport maps + based on metric entropy. Given c > 0, the e-covering number of a set A C X with a metric space (X, d) is denoted as Ne, A, d); namely, N N(c, A, d) denotes the minimum number of balls whose union covers A. Let In+ (x) 0 In(x). The complexity measure is defined as
Our main result is a meta-theorem that characterizes the fair minimax optimal error (see Equation (I)), showing how its convergence rate depends on P. We begin by introducing several technical assumptions on P before presenting our main meta- theerem..
follows:
For convenience, we introduce several notations. We use notations Py= = {UY, 14. E P). Px = {ux,: : us E P}, and P/ = {uz= : H. E P). We denote P. = {Hs : M. E P for & E [M. Let Fp = [s+.: Mr: E P), and let Fp.s =
Definition 3.3. The complexity of P is (a, 3) for > 0
and 3 2 0 if there exist constants C, C" > 0 and ε >> 0, and
sequence of subsets O C O2 S ... S ( n E P/} such that for any integer j 2 0,
[M]. Let Op = (00y,: μ4 E P). We omit P in the subscript of these notations if P is clear
[fp.s : 14 E P) for
1. supner, inf (0,, v.,) S C2-aij
from the context.
2. supuer, NN, (e, dv,) S C22 In (1/e) for e e (0,
Assumptions We begin with our first assumption.
In our main theorem, we will assume the complexity is (a,, 3) for some a and B.
Assumption 3.1. P satisfies the following three conditions:
1. Py x xx S ((UY:: (xx,)) Mr: E PP:
2. for any permutation π over [AM), (T()) Piff E EP,
Meta-theorem We now characterize the fair minimax op- timal error (P) in terms of the conventional minimax optimal error. Specifically, for a given group 8 [M], the group s's conventional minimax optimal error is defined as
3. F, is convex, meaning for any f. f F and (0, If + (1 1) F.,
Intuitively, the first and second conditions imply that the learner has no prior knowledge about (i) how the distribu- tions of (*) and (+) are related, nor (ii) how the distri- butions { differ. These conditions are naturally satisfied in many real-world scenarios. Note that the third condition does not require the regression functions them- selves to be convex but rather that the set F, is convex, which can still accommodate non-convex functions.
& (Ps)) = inf sup Eng [dxx. (JksS Si.s)) Sk p.EP.
where the infimum taken over all regression algorithms that take i.i.d. copies of (X(*), y()) as the observed sample. Let ñ = min,e]M] ng/w.,
Theorem 3.4. Assume Assumptions 3.1 and 3.2 and that the complexity Py is (ax, B3 for some a >> O and B3 '2 O. Then, there exists consistently fair learning algorithm such that
Next, we impose assumptions on ff to facilitate the estima- tion of the optimal transport maps " First, we assume that : are elements of Lipschitz and strictly increasing
(p1) < (P) SC
functions M 2. Specifically, Mr. is defined as the set of functions 2: Ω + 52 satisfying
-a/(a+99)
L2 Σ Egen, (P.) +
ñt [I((a)
- (y x) < (x) 0(y) S
- L(y-x) Vx > y- (3)
M
Second, we assume that ftss satisfies the Poincaré-typp type inequality: there exists a constant Cp > 0 such that for any function g Ω + Q with an L-Lipschitz continuous gradient,
for some constant C> 0.
We highlight several implications of Theorem 3.4:
1. Assuming there exists constant e > 0 such that 2 cw.n for all E [M]. Theorem 3.4 shows that the optimal rate with respect to n is (Pi)) ) (note that E, = =... = E,, (PM)) whenever (Pi) is larger than n (m(m)) aa/((++))) In such cases, the rate of (P)
Vn. [ SCRE (x)(xx)))
(4)
Assumption 3.2. There exists a constant for all 1a. E P and all E [M]. 1) 8r oh E MM and 2) ps,s satisfies the Poincaré-type inequality in Equation (4).
such that
can vary with P along with (P1).
2. In general, Theorem 3.4 implies that if the conventional regression problem is more difficult than the transport map estimation problem, then the optimal fair regression
iI is worth noting that any transport map over the real line is non-decreasing function due to the convexity the potential.
4

---

Meta Optimality for Demographic Parity Constrained Regression via Post-Processing
error is dominated by the conventional minimax error. This situation commonly arises in high-dimensional set- tings for X' (e.g., image, text, or audio regression). 3. Chzhen et al. (2020) also established similar upper bound on the error under the demographic parity con- straint. However, their result has two notable limita- tions. First, their analysis requires stronger assumptions than ours. For instance, they assume that the conven- tional regression algorithm admits a sub- Gaussaan high- probability error bound, whereas our results only require bound on the expected squared error. Furthermore, while they require uniform upper and lower bounds on the density of jff.= we only assume the Poincaré-type inequality. These differences broaden the applicability of our meta meta-theorem relative to their findings.
again up to logarithmic factors, provided that there exists constant c > 0 such that n, 2 cw.n for all [M].
An important insight from this example is that if the smooth- ness of the regression components and the transport maps are comparable (i.e., / x ?), then the minimax error is dominated by the regression term whenever 4, > 1 for some i. Here, i, reflects the intrinsic dimensionality of the essen- tial intermediate data representation. In practical situations, the intermediate representations may be nulti-dimensional (4: > 1), and thus the overall rate is determined by the conventional regression problem.
4. Optimal Algorithm and Upper Bound
In this section, we present our fair regression algorithm. Its core structure is similar algorithms proposed by Chzhen et al. (2020); Chzhen & Schreuder (2022). Leveraging The- orem 2.3, we obtain the fair Bayes-optimal regressor by composing the optimal transport maps or from J(, to the barycenter of μt, with the conventional Bayes-optimal re- gressor fū.. Let fn.: and on.: be estimators of fü. and Hy.er respectively. We define the estimator of f as or
4. The second limitation of Chzhen et al. (2020) is that their results cannot achieve convergence rate faster than n 1-11/2, since their upper bound on the estimation error of n.:: is n -1/2 and dominates the other terms. In contrast, our result can achieve rate faster than n -1/2 by exploiting the smoothness structure of 0r #.:"
Illustrative Example To concretely demonstrate the im- plications of our theoretical results, we consider a represen- tative scenario in which the regression function Jü, is a composition of multiple functions, as studied by Schmidt- Hieber (2020), and the optimal transport map di., lies within a Sobolev function class. Specifically, let fi... belong to the class
(=) (Un. (x)) This procedure can be viewed as post-processing since we first construct fn,: using con- ventional learning algorithm and then refine its outputs using On..-
We employ a camiimx--pptiman conventional regression al- gorithm for the model P as the estimator fn,:- Our main methodological contribution, distinguishing our work from earlier approaches, is the introduction of a suitable estimator for 0 0n,.- To estimate o uy we utilize the strategy proposed by Korotin et al. (2020) (see Section 2.3). We also provide a novel analysis of the convergence rate for the estimation error of dn.:, which was not addressed in Korotin et al. (2020).
9q o o 90
9: = (9r))s : Ja,, b,1 + [ast1, bet1]
gij E Cft (laz, (1asbb)))) bi)")
where Cf denotes the Hölder class of functions with smooth- ness parameter 3 and r-dimensional input, d, is the input dimension of 9t. and f, < d, indicates that each Bty depends on only 4; out of d; variables. This structure captures the notion of compositional functions with sparse dependencies, which is prevalent in high-dimensional statistical learning.
We first describe the construction of on,: and then demon- strate the overall procedure of our fair regression algorithm along with analyses of its accuracy and faimess.
Barycenter estimation As discussed in Section 2.3, one can obtain the optimal transport maps the Wasserstein barycenter problem by finding congruent potentials that minimize the multiple correlation C(u., v.). In the fair re- gression setting, our goal is to estimate the transport maps in the Wasserstein barycenter problem for Mf. However, the learner cannot directly observe μf, since neither fü.. nor px.: is known. Instead, we substitute fn. for ft. and use empirical measures from the observed samples in place of px... Specifically, let f/.. be the law of fn. (x()()())) for s e [M], and let Pn,f.s be the corresponding empirical mea- sure induced by a sample of size ns- Then, the estimator
For regression functions of this form, the mini- max optimal error for group satisfies (P.)
θ max; T1g 87 /22/(227 +t)) up to logarithmic factors, where 3 = 3 11 (3, A 1). Also, for the class of transport maps &-.-- taken to be the Sobolev class of smoothness
7 >> 0, Definition 3.3 is satisfied with a = 2y and 1 by choosing θ as the span of the first j wavelet basis functions. Consequently, the fair minimax error is obtained as
(P) = 0 ( maxx /7/ /2/(207 +5,) + nn= - -22/(2+11)).
5

---

Meta Optimality for Demographic Parity Constrained Regression via Post-Processing
Algorithm 1 Optimal fair regression
Algorithm 1 to the estimation error of the estimated trans- port maps &n,:- Specifically, we demonstrate the connection of Algorithm I's error and unfairness with di (dn,.s in wu)) through the following propositions:
input Samples (Y(*) 1 xx")),____. (Y2n), x
output Jn.
1: Construct fn. using minimax optimal conven- tional regression algorithm with halves of samples (Y,(0) (x((,,x(()) xx()),... (Y:1,) 5 x
Proposition 4,4. Let J.. be regressor obtained by Algo- rithm 1. Under the same conditions as in Theorem 3.4, there exists universal constant C. > O such that
2: Construct Un.: by Equation (5) with the remaining sam- ples fx, (X++)) (....).. (X2,))
En [o (nnss
3: (x) = (Dn, (2)
E.wen E.en, (Ps)+ Eug. [oby, (Un. S (up)))
C
L2 E SE[MS
nn. defined as the minimizer of
where Byy, denotes the expectation over the samples used for constructing 1 In,:- Proposition 4.5. Let fn. be regressor obtained by Algo- rithm 1. Under the same conditions as in Theorem 3.4, we have
inf o.E0,
C(uo.:Ho.ff))
(5)
where ua, denotes the potential functions corresponding to the transport maps 0,, and θ is a sequence of subsets of θ described in Definition 3.3.
inf max (2 sE(M]
We require a specific construction of ugg.: for technical reasons. We extend the input and output domains of any function & 52 + St to E while preserving the property in Equation (3) by defining d(2) = 2 + Caup for
Remark 4.1.
M MWmin duzo (nnss Duje) a.s.,
large= = and (=) = z + Cinf for small with appropriate constants Caup, Cinf E R.. We interpret functions in θ as their extended versions. Letting (z) = So " we define u as the convex conjugate of uhy ; i.., (2)= sup - (x)).
where Wmin [ Wg.
By Proposition 4.4, we obtain an upper bound on the regression error by deriving an upper bound on E ldy, (0 01 "iy.::)l Additionally, Proposition 4.5 im- plies that Algorithm achieves fairness consistency in Def- inition 2.2 if Ppp
{ (duy, (Pn,s (....) = o(1) 1 -o)( o(1) We will provide upper bounds on the error duj, (0n.:, Opp) through the analyses shown in the next section.
Overall algorithm Algorithm I summarizes the overall procedure of our fair regression algorithm. For simplicity, we assume that the sample size for group 8 is 2n,, the first step, we execute a kinimax-optimal conventional regres- sion algorithm with half of the samples to obtain fn.. By definition, fn,, achieves an error of (P.). In the second step, we estimate the transport map i)..: via Equation (5) using the remaining samples. As shown in the next corollary, Algorithm achieves the desired properties.
5. Transport Maps Estimation in Wasserstein Barycenter
In this section, we investigate the convergence rate of our estimator for transport maps estimation in the Wasserstein barycenter. We conduct our analyses under the general setup of transport maps estimation in the Wasserstein barycenter for real-valued probability measures. We first describe the general setup and demonstrate the convergence rate of our estimator, which is the main result of this section. We then provide detailed analyses to support the convergence rate.
Corollary 4.2. Under the same conditions as in Theo- rem 3.4, Algorithm I achieves the upper bound in Theo- rem 3.4 and is consistently fair.
Remark 4.3 (Limitation). The minimization over congruent potentials may present computational challenges. Korotin et al. (2020) proposed adding a penalty term to enforce con- gruency instead of handling the constraint directly, which may be more practical. Analysis of convergence rates under approximate satisfaction of congruency remains an impor- tant direction for future work.
Setup Consider the problem of estimating the transport maps that arise in the Wasserstein barycenter problem. Let v. E Q be probability measures indexed by [M] on a mea- surable space (2, Recall that the Wasserstein barycenter problem involves finding the minimizer of the following optimization problem:
Connection between fair regression and transport maps estimation in Wasserstein barycenter To prove Corol- lary 4.2, we relate the regression error and unfairness of
inf Σ w. Wr, SE[M]
6

---

Meta Optimality for Demographic Parity Constrained Regression via Post-Processing
Let be the minimizer of the above optimization problem, Le., the Wasserstein barycenter. Recall that denote o2 as the optimal transport map from Vs to for each E [M]. Given M samples each ii.d. from V3, the analyst's goal to estimate v We denote the estimator of &h as nn,:- According to Propositions 4.4 and 4.5, we assess the error of the estimated transport maps by
Theorem 5.1 shows that a larger or and smaller 3 result in faster convergence rate.
To establish the upper bound in Theorem 5.1, we follow the convergence rate analysis for the sieved M-estimator (see, e.g., Van Der Vaart & Wellner, 2023), since our estimator in Equation (5) can be regarded as a sieved -estimatto. The main analytical challenge is that the process 0. + C(us,;; Vn.:) ) is not a standard empirical process, and thus standard concentration inequalities do not directly apply. In the following subsection, we present the analysis of on,: including a concentration inequality for the process 0, + C(ua,:: Vna).
dy (m. = Σ
Wydyy (Un,ss (2,s)
SE[M]
Σ M[[M]
We (0m ((,a))))))==))) (z)) v.(2)) (dzz.
5.1. Error Analysis for dn..:
Note that de. (Dn,:; (%.) is a random variable with random- ness stemming from the samples. The goal of the analyses is thus to provide an upper bound on the expectation of the error or a probabilistic upper bound on the error.
In this subsection, we present the error analysis for dn.-- We begin by formally defining the processes associated with the populational and empirical multiple correlations. The expectation operator E, defined as Ev = (2() for function integer n, the empirical expectation operator Ev,n is given by Ev,n = J - (Zz),, where Zi,..., Zn are drawn i..d. from v. For measurable functions u, Z + R indexed by [MJ, we define the following operators:
Z + R and Z V. For a positive
Estimator Our estimator in,: is constructed by minimiz- ing the empirical multiple correlation over a sieved subset of transport maps. Let è = {0c. : M E 2} represent the set of all possible transport maps. Denote by Vn; the empirical measures corresponding v., as determined by the observed samples. Assume that the complexity of Q is (a, 3) for some > 0 and 3 2 O, and let {0i} be sequence of subsets of θ as specified in Definition 3.3. The estimator dn is then defined as the solution to the following optimization problem:
Ev, U. = Σ
w. Ev,
Us: Us:
En,e, u: = Σ
W. EnE,, Us.
SE[M]
SE[M]
The populational and empirical multiple correlations are then expressed as
inf C(uo,s Kng)s J
Cluo, v.) = Eu, Clup, Un.)) = En,u, Ud,;:
where j is chosen appropriately.
Concentration of the process We now establish the con- centration inequality for the process Fn,,, - Fy,- We first present a Bernstein-type concentration inequality for fixed potentials u6...- For E [M]. let v, be a probability measure on a measurable space (2, 3). Let Z²²) denote a random variable distributed according to v/- Let U be class of functions u, Z + P indexed by E [M].
Estimation Error Bound Our main results in this sec- tion are expected and probabilistic upper bounds on dv, (On., (..).
Theorem 5.1. Let Un.- = arg ming,ee, C(uo.; Vn.)) be the estimated transport maps, with satisfying 2 S 1/(x+()) < 22+1. Suppose that 0h,a E M, some L> 1, and that v, satisfies the Poincaré-type inequality in Equation (4) for all v. E Q. Also, suppose that the complex- ity of Q is (a, (3) for some a > 0 and B 2 O. Then, there exists a constant C > O, possibly depending on L, and M,
Proposition 5.2. Given u, E U such that ExE[M] W. (u,,uu S o2 and max (fa
E,, M,l S b almost surely, we have
nt² 2 + lb
P[ Ev,u, > 8 S exp
such that
ñ
-a/(a+0)
Building on Proposition 5.2, we derive the maximal inequal- ity over the set of functions U. For E U, define
Eyn (Un., )
In(
o (v.) Σ
W Vr, ua (z)((())]
Moreover, for all 2 1, with probability at least 1 - -t,
SE[M]
-a/(a+8)
& (0... 02.) Ct π In(ū)
by (u.) = inf
b max sE(M
u, (z((())) Ev,, us S <b bas..
7

---

Meta Optimality for Demographic Parity Constrained Regression via Post-Processing
It is worth noting that both oy, and by satisfy the triangle inequality. As complexity measures for U, we introduce Dudley integral-type metrics, defined for d >> 0 as
Relationship between potentials and transport maps To apply existing analyses of sieved M-estimators to our setting, we establish the relationship between the potential uo. and the transport map d.. Specifically, we prove the following:
6 J Vin(N((,(,,ou)ddd
Ho,, (5:()) =
Proposition 5.6. Let v. be probability measures indexed by [M] such that oh E MMy for some > Then, for all
Hb.w(6:U1 /-¹ In(N(e, Dde.
0, E EM such that ExE(M] w.0= = z for all E Ω2
This leads to the following maximal inequality: Proposition 5.3. Given a fixed uf EU, o > 0, and b > 0, define
2L de. (0,,0%)) S Eve (uo. - -uo.)) )
1
L de (0. S2.).
Proof Sketch of Theorem 5.1 The application of Proposi- tion 5.3, together with Lemma 5.4 and Lemma 5.5, demon-
U(o,b;u.)
strates that for all & 2 1 and 2 1,
(u: - u.) S o, a, (u: (u.) S bb.. {u: E uu ov, ow,(u.
P Pu (ktr² S de (Un... 0J.) S (k + 1)tr"} S exp(-kt),
Then, there exists a universal constant C > 0 such that for all t >>0 O,
and Dj. denotes the min- imizer of C(uo,,. 14.) over D, O, Subsequently, employ- ing the peeling argument in conjunction with Proposition 5.6 leads to the desired results.
where 7² = ((()m())))))))))))))))))))
= )-/(at))))
Pam
sup El((obbur)
Vñ(Enp Ev.) - u.))
> C How (0; (H:
1 +
Hom (b; + :
6. Lower Bound
Vn
VFr²
To establish our lower bound, we develop a technique based on reducing the fair regression estimation problem to a conventional regression estimation problem. Specifically, let fi:.: be the optimal fair regression algorithm satisfying
S exp
Vioo (-iio> + tb
Analyses for Dudley integral-type metrics To utilize Proposition 5.3, we establish upper bounds on Ho.v (6:4) and H₂,,, (5:21) In the context of analyzing & in we pro- vide upper bounds for U = {uor : E 2). where is the set of probability measures with complexity (a, 33 for some a > 0 and 3 2 O, as specified in Definition 3.3.
sup Ey, Lo (Fris Fi.))] (P), S.P
(6)
We demonstrate that we can construct a conventional regres- sion algorithm using ft.-- The error of this conventional regression algorithm is bounded below by En (Pa). which consequently provides a lower bound on En (P) in terms of (P.).
Lemma 5.4. Suppose that or. satisfies the Poincaré-type inequality in Equation (4) for all v: E Q, and that the complexity of Q is (ax, for some a > 0 and 3 2 0, as in Definition 3.3. Then, for all j 2 and all E ( and d' >>0 O,
Consider the scenario where distributions Pi..... HM are identical, and fü, is constructed using samples compris- ing n, i.i.d. points from μl.. Under these conditions, we can construct a regressor for fü.1 as fa = => Ws, Wr The error of this regressor provides a lower bound on Equa- tion (6) follows:
Ho., (Cpo: (2o.- uor.::00 E 2 dr (0., (r.
S (
Theorem 6.1. Under the conditions stated in Theorem 3.4, we have
where Cp is the constant in Equation (4), and é and C' are the constants in Definition 3.3.
(Pi)
En, dd (in)) finx)]
Lemma 5.5. Suppose that Sr, E M, some L > 1 and all v. E Q. Then, there exists a constant C. > 0, possibly depending on M, such that for all b O,
sup VIEPiVeEEMM ,, mm
< sup E,, Sax. (Fri (p.t) M.P
Ho.r, {u. - uug.:: : U. E U. by, (u, u05.:) S bb})
This result directly establishes a lower bound on E, (P) in Theorem 3.4.
S Covb.
8

---

Meta Optimality for Demographic Parity Constrained Regression via Post-Processing
7. Related Work: Optimal Transport Map Estimation
Acknowledgements
This work was partly supported by JSPS KAKENHI Grant Numbers JP23K13011.
The problem of optimal transport map estimation in the Wasserstein distance has been extensively studied (Hütter & Rigoller, 2021; Divol et al., 2024; Rigollet & Stromme, 2025; Pooladian et al., 2023; Pooladian & Niles-Weed Weed, 2024; DEB et al., 2021; del Barrio et al., 2023; Manole et al., 2024). The objective of this estimation problem is to estimate the transport map in W2(j,, p²) between two distributions μ and p', given samples from both distribu- tions. Several approaches have been proposed: Manole et al. (2024); DEB et al. (2021); Rigollet & Stromme (2025) uti- lize plug-in estimators, where they first estimate the joint distribution of (Z, 8 (Z)) for ~~ ju and subsequently con- struct a transport map by minimizing the expected error between Z and 0( ( Alternative estimators proposed by Hütter & Rigollet (2021); Divol et al. (2024); del Barrio et al. (2023); Pooladian et al. (2023); Pooladian & Niles-Weed (2024) employ potential minimization techniques. While these studies provide convergence rate analyses for their estimators, their methods cannot be directly applied to opti- mal transport map estimation in the Wasserstein barycenter problem, as sample from the barycenter distribution are not observable.
Impact Statement
This paper presents work whose goal is to advance the field of Machine Learning. There are many potential societal consequences our work, none which we feel must be specifically highlighted here. Rather, this paper aims at addressing societal issue of unfairness that may arise in conventional learning algorithms.
References
Agueh, M. and Carlier, G. Barycenters in the Wasser- stein Space. SIAM Journal Mathematical Anal- ysis, (112))904-924 2011. ISSN 0036-1410, doi: 10.1137/100805741.
Angwin. J., Larson, J., Mattu, S., and Kirch- ner, L. Machine Bias, 2016. URL https: meachiiiemmmeee--eeeee bias-risk- aww.sasssssssssse wtwpeeeeennttittt-teeee in-criminal- sentencing.
Several researchers have developed methods specifically for optimal transport maps estimation in the Wasserstein barycenter problem, although these methods lack accom- panying convergence rate analyses. Korotin et al. (2020)
Chen, W., Klochkov, Y., and Liu, Y. Post-hoc bias scoring is optimal for fair classification. In The Twelfth Interna- tional Conference Learning Representations, 2023.
proposed an estimator based on potential minimization, as detailed in Section 2.3. Fan al. (2021) introduced an esti- mator utilizing minimax optimization. Korotin et al. (2022) developed iterative algorithm grounded in the fixed-point theorem established by Álvarez Esteban et al. (2016). Kim et al. (2025) proposed an approach employing a primal-dual coordinate gradient algorithm to estimate the transport maps. Visentin & Cheridito (2025) developed an estimator for the transport maps leveraging the conditional normalizing flow, also demonstrating the application of their estimator to the fair regression problem. While empirical evaluations have shown that these methods achieve low estimation errors, theoretical analyses of their convergence rates remain an open problem.
Chuang, C.-Y. and Mrouch, Y. Fair Mixup: Fairness via Interpolation. In International Conference on Learning Representations, 2020.
Chzhen, E. and Schreuder, N. A minimax framework for quantifying risk-faimess trade-off in regression. The An- nals of Statistics, 50(4):2416-2442, 2022. ISSN 0090- 5364. doi: 10.1214222-A022199
Chzhen, E., Denis, C., Hebiri, M., Oneto, L., and Pontil, M. Leveraging Labeled and Unlabeled Data for Consistent Fair Binary Classification. In Advances in Neural Infor- mation Processing Systems, volume 32, pp. 12739-12750. 2019.
8. Conclusion
Chzhen, E., Denis, C., Hebiri, M., and Pontil, M. Fair Regression with Wasserstein Barycenters. In Advances in Neural Information Processing Systems, volume 33, pp. 7321 Curran Associates, Inc., 2020.
We have presented minimal optimal fair regression algo- rithm based on post-processing. Our algorithm achieves minimax optimality across various scenarios by leveraging the extensive body of research on minimax optimal con- ventional regression. Our analysis demonstrates that prac- titioners can focus their efforts on improving conventional regression methods, which can then be effectively adapted for fair regression applications.
Cotter, A., Jiang, H., Gupta, M., Wang, S., Narayan, T., Mobility Scongnam-si. K., and Korea Karthik Sridharan, S. Optimization with Non Diffeeerrentia Constraints with Applications to Fairness, Recall, Churn, and Other Goals. Journal of Machine Learning Research, 20:1 2019.

---

Meta Optimality for Demographic Parity Constrained Regression via Post-Processing
Crockford, K. How is Face Recognition Surveil-
Proceedings of the 21th ACM SIGKDD International Conference Knowledge Discovery and Data Mining, pp. 259-268, Sydney, NSW, Australia, 2015. ACM. doi:
lance Technology Racist?, 2020. http:///www.ccll.ooor///////////
URL
00.1144/278325822883331
Fukuchi, K. and Sakuma, J. Demographic parity constrained minimax optimal regression under linear model. In Ad- vances in Neural Information Processing Systems, vol- ume 36, pp. 8653-8689, 2023.
Dastin, J. Amazon scraps secret AI recruiting tool that showed bias against women, 2018. URL
ammpzoonccoomppaas--atttttttt--- amazon
Giné, E. and Nickl, R. Mathematical Foundations of Infinite- Dimensional Statistical Models. Cambridge Series in Sta- tistical and Probabilistic Mathematics. Cambridge Univer- sity Press. Cambridge, 2015. ISBN 978- 1-107-04316-9, doi: 10.1017/CB099881073337778
hood--bat--showee------gggg-sss- id0SKCN1MKC8G.
DEB, N., Ghosal, P., and Sen, B. Rates of Estimation of Optimal Transport Maps using Plug-in Estimators via Barycentric Projections. In Advances in Neural Informa- fion Processing Systems, volume 34, pp. 29736-29753. Curran Associates, Inc., 2021.
Hardt, M., Price, E., and Srebro, N. Equality of Opportunity in Supervised Learning. In Lee, D. D., Sugiyama, M., Luxburg, U. V., Guyon, I., and Garnett, R. (eds.), Ad- vances in Neural Information Processing Systems 29, pp. 3315-3323, Barcelona, Spain, 2016. Curran Associates, Inc.
del Barrio, E.,, Sanz, A. G., Loubes, J.-M., and Niles-Weed, J. An Improved Central Limit Theorem and Fast Con- vergence Rates for Entropic Transportation Costs. SIAM Journal on Mathematics of Data Science, 5(3):639-669, 2023. doi: 10.1137/22M1499260.
Hütter, J.-C. and Rigollet, P. Minimax estimation of smooth optimal transport maps. The Annals of Statistics, 49(2): 1166-1 194,, 2021. ISSN 0090-5364, 2168-8966. doi: 10.1214/20-AOS/
Divol, V., Niles-Weed, J., and Pooladian, A.-A. Optimal transport map estimation in general function spaces. 2024. doi: 10.48 (0.488550/rxXx2222200722
Jiang, R., Pacchiano, A., Stepleton, T., Jiang, H., and Chi- appa, S. Wasserstein Fair Classification. In Proceedings of The 35th Uncertainty in Artificial Intelligence Confer- ence, volume 115, pp. 862-872. PMLR, 2020.
Donoho, D. L. and Johnstone, I. M. Minimax estimation via wavelet shrinkage. The Annals of Statistics, 26(3): 879-921, 1998. ISSN 0090-5364, 2168-8966. doi: 10. 121 1214//0//0246610811.
Jovanović, N., Balunovic, M., Dimitrov, D. I., and Vechev, M. FARE: Provably Fair Representation Learning with Practical Certificates. In Proceedings of the 40th Inter- national Conference Machine Learning, pp. 15401- 15420. PMLR, 2023.
Du, M., Mukherjee, S., Wang, G., Tang, R., Awadallah, A., and Hu, X. Fairness via Representation Neutralization. In Advances in Neural Information Processing Systems, volume 34, pp. 12091-12103. Curran Associates, Inc., 2021.
Khalili, M. M., Zhang, X., and Abroshan, M. Loss Balanc- ing for Fair Supervised Learning, In Proceedings of the 40th International Conference on Machine Learning, pp. 16271-16290 PMLR, 2023.
Dwork, C., Hardt, M., Pitassi, T., Reingold, O., and Zemel, R. Fairness through awareness. In Goldwasser, S. (ed.), Proceedings of the 3rd Innovations Theoretical Com- puter Science Conference, pp. 214,226, Cambridge, MA, USA, 2012. ACM.
Kim, K., Yao, R., Zhu, C., and Chen, X. Optimal Transport Barycenter via Sinrconvex-Concave Minimax Optimiza- tion. In Proceedings of the 42st International Conference on Machine Learning, 2025.
Fan, J., Taghvaci, A., and Chen, Y. Scalable Computa- tions of Wasserstein Barycenter via Input Convex Neural Networks. In Proceedings of the 38th International Con- ference on Machine Learning, pp. 157 1571 1511. PMLR, 2021.
Kleinberg, J., Mullainathan, S., and Raghavan, M. In- herent Trade-Offt in the Fair Determination of Risk Scores. In 8th Innovations in Theoretical Computer Sci- ence Conference (ITCS 2017), Leibniz International Pro- ceedings in Informatics (LIPlcs), pp. 43:1-43:23. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017. doi: 10.4 D0.42300.Piee..ITSS..2010
Feldman, M., Friedler, S. A., Moeller, J., Scheidegger, C.,
and Venkatasubramanian, S. Certifying and Removing Disparate Impact. In Cao, L., Zhang, C., Joachims, T., Webb, G. I., Margineantu, D. D., and Williams, G. (eds.),
10

---

Meta Optimality for Demographic Parity Constrained Regression via Post-Processing
Korotin, A., Li, L.., Solomon, J., and Burnaev, E. Continuous Wasserstein-2 Barycenter Estimation without Minimax Optimization, In International Conference on Learning Representations. 2020.
Schmidt-Hieber, J. Nonparametric regression using deep neural networks with ReLU activation function. The Annals of Statistics, 48(4): 2020, ISSN 0090- 5364,
doi: 10.1214/19-ASS180
Korotin, A., Egiazarian, V., Li, L.., and Burnaev, E. Wasser- stein Iterative Networks for Barycenter Estimation. In Advances in Neural Information Processing Systems, vol- ume 35, pp. 15686, 2022.
Schreuder, N. and Chzhen, E. Classification with abstention but without disparities. In Proceedings of the Thirty- Seventh Conference on Uncertainty in Artificial Intelli- gence, pp. 1227-1236. PMLR, 2021.
Suzuki, T. Adaptivity of deep ReLU network for learning in Besov and mixed smooth Besov spaces: optimal rate and curse of dimensionality. In International Conference on Learning Representations, 2018.
Manole, T., Balakrishnan, S., Niles- Weed, J., and Wasser- man, L. Plugin estimation of smooth optimal transport maps. The Annals of Statistics, 52(3):966 998, 2024. ISSN 0090-5364,
doi: 10. 10.1224/24-A002339
Suzuki, T. and Nitanda, A. Deep learning is adaptive to in- trinsic dimensionality of model smoothness in anisotropic Besov space. In Advances in Neural Information Process- ing Systems, volume 34, pp. 3609-3621. Curran Asso- ciates, Inc., 2021.
Menon, A. K. and Williamson, R. C. The cost of fairness in binary classification. In Proceedings of the Ist Con- ference on Fairness, Accountability and Transparency, volume 81, pp. 107-118. PMLR, 2018
Najibi, A. Racial Discrimination in Face Recognition Tech- nology, 2020. URL httpt: hms. harvard. nat on-
Van Der Vaart, A. W. and Wellner, J. A. Weak Conver- gence and Empirical Processes: With Applications to Statistics. Springer Series Statistics. Springer Interna- tional Publishing, Cham, 2023. ISBN 978- --71----0--2008-11 978-3-031-29040-4, doi: 10. 10.1007/988-3-031-29000
Nishimura, Y. and Suzuki, T. Minimax optimality of con- volutional neural networks for infinite dimensional input- output problems and separation from kernel methods. In The Twelfth International Conference on Learning Repre- sentations, 2023.
Vigdor, N. Apple Card Investigated After Gender Dis- crimination Complaints. The New York Times, 2019. ISSN 0362-4331. URL https:/ http::://www.ttt.t.. 1t1/2///////////uuuueeeseee card investigation...mmmmm
Park, J. and Muandet, K. Towards Empirical Process Theory for Vector- fector-Valued Functions: Metric Entropy of Smooth Function Classes. In Proceedings of The 34th Interna- tional Conference on Algorithmic Learning Theory, pp. 1216-1260. PMLR, 2023.
Visentin, G. and Cheridito, Computing Optimal Transport Maps and Wasserstein Barycenters Using Conditional Normalizing Flows. In Proceedings of the 42st Interna- tional Conference Machine Learning, 2025.
Xian, R., Yin, L.,, and Zhao, H. Fair and Optimal Clas- sification via Post-Processing. In Proceedings of the 40th International Conference on Machine Learning, pp. 37977-38012. PMLR, 2023.
Pedreshi, D., Ruggieri, S., and Turini, F. Discrimination- aware data mining. In Proceeding of the 14th ACM SIGKDD international conference on Knowledge discov- ery and data mining- KDD 08. pp. 360-568, 2008 ISBN 978-1-60558-199 193-4. doi: 10.1145 /4114/4441880014095555
Xu, S. and Strohmer, T. Fair Data Representation for Ma- chine Learning at the Pareto Frontier. Journal of Machine Learning Research, 24(331):1-63, 2023. ISSN 1533- 7928.
Pooladian, A.-A and Niles-Weed. Entropic estimation of optimal transport maps. 2024. doi: 10.48550 12004.
Zeng X., Cheng, G., and Dobriban, E. Minimax Optimal Fair Classification with Bounded Demographic Disparity. 2024. doi: 10.4 10.445550/2Xiw.2403.115 18216.
Pooladian, A.-A., Divol, V., and Neles-Weed, J. Minimax estimation of discontinuous optimal transport maps: The semi-discrete case. In Proceedings of the 40th Inter- national Conference on Machine Learning, pp. 28128- 28150. PMLR, 2023.
Zhang, B. H., Lemoine, B., and Mitchell, M. Mitigating Un- wanted Biases with Adversarial Learning. In Proceedings of the 2018 AAAI/ACM Conference on AI, Ethics, and Society, AIES '18, pp. 335-340, New York, NY, USA, 2018. Association for Computing Machinery. ISBN 978- 1-4503-6012-8 doi: 10.1145/3278721 33278779.
Rigollet, P. and Stromme, A. On the sample complexity of entropic optimal transport. The Annals of Statistics, 53 (1), 2025. ISSN 0090-5364 doi: 10.1224/24 A0024455.

---

Meta Optimality for Demographic Parity Constrained Regression via Post-Processing
Zhao, H. and Gordon, G. Inherent Tradeoff's in Learning Fair Representations, In Advances in Neural Information Processing Systems, volume 32, Curran Associates, Inc., 2019.
Álvarez Esteban, C., del Barrio, E., Cuesta-Albertos, J. A., and Matrán, C. A fixed-point approach to barycenters in Wasserstein space. Journal of Mathematical Analysis and Applications, 441(2):744-763 2016. ISSN 0022-247X. doi: 10. 10166006.jjaaa 2016.04.45.
12

---

Meta Optimality for Demographic Parity Constrained Regression via Post-Processing
A. Missing Proofs
A.1. Error Analysis for General Sieved M M-Estimator
In this subsection, we present an error bound for general sieved M-cstimators. Let E and En denote the expectation and empirical process indexed by U, respectively, where n the sample size. Let Ô be a parameter space and O' S 6 a sieved subset. For family ug U parameterized by 0 E θ the sieved M-estimator is defined
On = arg min En
leer
Let 0o ④ denote the ideal parameter such that Eug, inface Eug, and let 0g E O' be the ideal parameter within the sieved set, i.., Eug, inf Eug. The estimation error of 0, is measured by d(O,, Bo), where d is a distance function on θ
Within this framework, we derive an error bound for sieved Meestimators under the following assumptions on the processes E and En. Assumption A.I. There exist constants Kup; Klow such that for any E O
Koo Elug uo.) - de (0, S Kup Eluo - u..).
Assumption A.2. Let E (1, be constant, and let ao,z: a1.n 02,n bn be sequences of positive numbers associated with n. Suppose H R IR is non-decreasing function such that for all / O,
t2 + bott) )
P um
sup 000r
(En E'ouo -ugr) ao.n + 01,x + aznt j S cxp
and σ- + Haa)/a" is non-increasing for > 0.
The following theorem provides the error bound for sieved M M-estimators.
Theorem A.3. Suppose that Assumption A.I and Assumption A.2 hold. Define
= V4Kup (v (22E(um, - uo.) uoo)) + vai. + 22h..) + +1 A005, + az,bb,)
where hn is a sequence such that 0,, H (8 S for all n. Then, for all t t 1,
Pun (On, 00) 2 1(2 + (0%, 0o)) } s 2e
Furthermore,
Ene (d 6o)] s llm + 2d 2d 0o).
By establishing Theorem A.3, one can obtain an error bound for a sieved M-estimator by verifying Assumption A. and Assumption A.2.
1. PROOF OF THEOREM A.3
To establish Theorem A.3, we present the following supporting lemma.
Lemma A.4. Assume there exists
such that for all k and t 2 1,
Pun ( ktt s (0, 8%) s (k: 1)tr²} } s exp(-kt).
Then, for all 2 1,
P (0(0000) 2 t(272 + 2d (0% 0b)) } < -t
Furthermore,
En (0.000)) < 41ln()))²+ 2d 00) 0o)
13

---

Meta Optimality for Demographic Parity Constrained Regression via Post-Processing
Proof of Lemma A.4. Let > 0 and 7 > Define
(x(() = 10 E 0', kl' $ s (k 1)67
By employing the peeling argument,
Pu { (0,0) 2 2r2
0 E en(0)
P.
(9)
k=1
By assumption, for all & 2 1,
Pur Por E @u(1) s exx((-kl).
(10)
Combining Equations (9) and (10) results in
e
Pun (d.(0, () 2 tr²
exp( -kt)
1- e- S 2e
where the last inequality holds for 2 In(2). By the triangle inequality,
(() s 2d 6)) + 2d 6o).
(11)
Therefore, for t 2 ln(,),
Pur (0(0,0) 2 217 + 2d (0. s 2t
For f 2 since 2d 0o) (0,, 0o), it follows that
P m
(0, 0n) 2 =(22² + 2d Bn)) s 2e-1.
For the expectation bound, for any to > 0,
Eyn (0.
00
Pur
(8 P 0o) 2 2ddr
=
J0
10 +
Por (0,00) 2 x-²² Jds
72
F Uu { E 0x(z)) Jdzz 72
to
+
t0
k=1
00
10
kw dr
7²
ta
k=1
kig
to
72
k=
(lo In(1 - - 10) )
Choosing to In(2) yields
E, [2(0. 66)] 22
Again, by Equation (11),
En (00000)) < <41n(2)7² 20 (0) 0o)
14

---

Meta Optimality for Demographic Parity Constrained Regression via Post-Processing
The proof of Theorem A.3 established by confirming the condition of Equation (8), thereby applying Lemma A.4.
Proof of Theorem A.3. By assumption and the triangle inequality, for 0 E e',
dc (0) 52d (0, 06) 2d (0: 0o)
22Kup Eug ue,) + 4K E(ue, - u0o)
= 2u E - Eu - -uo,) + up Elug - -og) + up E(uo, - ugo))
up () ugg) 4K Eluer ug.):
where the last inequality uses the fact that & minimizes Eus over 0 E O'. For notational convenience, let Up = Eluog - -2o) Then, the left-hand side of Equation (8) can be bounded as
P klr² s (0,0%) s (I+ 1)(7
ktt
<P u.
d0, ()) 1 (k: + 1)t+² (E - (ug -uo)) 2 2K
-
2U/
ktr²
SPu u.
sup @Eer (8 (k+ l)tt²
(E E) -wo)) 2
2U
(12)
2 k up
By the concentration inequality assumption and Equation (12), letting
(T) =
T
200
a1, a2nkkt
a0, ag
H(v ( 1)tr),
22.
ktt
the condition in Equation (8) holds if
(T) (1 + 1) + (T) 2 1,
(13)
provided (T, > O.
We now seek such that Equation (13) and (x,x(T) > 0 are satisfied, For e, b > 0, the function x + c+ for x 2 0. Thus, Equation (13) holds if lower bound ( 2 5(T) satisfies
non-decreasing
(T)
21.
(1 + ) + bn 7 (T)
Since a + H(a)/o* is non-increasing, H(aa)/(ao)² < H(o)/o" for all 2 1 and 5 > 0. Therefore, for k 2 1 and t 12 1,
(T,(T))
2V0
a1,
ao 1)6) H(T)
2k
02, klr
20
a1,
200.
H(T):= ((T).
2K a2,
a2,n
a2,
a
We rewrite 7(7)
7(7) -
-2-7
20p
a1,n
200.
H(())
2K
02,n7
02,7
02,
Since + H(r)/a" is non-increasing, 7(r) is product of two non-decreasing functions in and thus is non-decreasing in when these functions are non-negative, Let T" > 0 satisfy
20
01n
200.2
H( 2
(14)
2K up
15

---

Meta Optimality for Demographic Parity Constrained Regression via Post-Processing
Then, for 7", 7(7) is non-decreasing in and for any 0. 0,7(T" up 2 Noting that 7(7)/T 2kup
Equation (13) holds if (T) 2 2Kupaz,n
Therefore, for T" satisfying Equation (14), Equation (13) holds with
T 88 a² + 2K
It remains to derive r" satisfying Equation (14). Since H()//o" is non-increasing, for any 7 E (0, r"),
H(r")
T" +²((T')
7 S
7'2
Define
T
v 4K up 2VU + /a1. + 22hn)
where nn is defined in the statement. Then,
r²
2V0
ain
200.. H(T")
2k up
7"
T²
4Up
201.
4hn
20
01,
2k
+
|
uu
+
2Kup
V
2 2U
uu /01,
2ag H ( (8kphh))
v /KKpp (V200 + vain + 22hn
8Kuphin
2
V2
2
2Vn 2Kup
+
(v2-
2
aln 2K
+ (V2
2hn ukup
2 0,
/2
V2
V2
where we use the assumption of ao (oonH((8KKin) (88Kupht) S hn to derive the last inequality. The resulting t then coincides with Tn as defined in Equation (7), verifying Equation (8) with Tn Application of Lemma A.4 completes the proof.
A.2. Proofs for Section 5
1. PROOF OF THEOREM 5.1
Proof of Theorem 5.1. the context of Appendix A.1, we identify Fry, E, En uig wa and d du. Furthermore, we set 0g = 02.. On = 0n,:, and 6 0j.,. where 03 denotes the minimizer of C(ua,; v.) over 0. θ,. To apply Theorem A.3, it is necessary verify Assumption A. and Assumption A.2.
By Proposition 5.6, the processes E Ev, and E, En... satisfy Assumption A.1 with Klow 1 and Kup 4. By 2I the Poincaré-type inequality assumption, if D. E O, satisfies du, (1., (2,) I then Eg, (uo,: Mot.) ) S Cro. Since Ω bounded, for 0. O2 S M there exists a constant smoothness of u, and uos.. Therefore, by applying Proposition 5.3 together with Lemma 5.4 and Lemma 5.5, these processes satisfy Assumption A.2 with
such that by, (ug.: - uo; ) S which follows from the
CCPV 85/81/2
Vi
CCPVb
01, ñ
C
22 Vn
bn Vn
(( -(1 AO) 11 11
16

---

Meta Optimality for Demographic Parity Constrained Regression via Post-Processing
where C' is the constant in Proposition 5.3. With the choice of stated, have
ñ aa In 0/2
on, I CCPVC'
Set hn = =cIn((i)/m)//te-> /n)a//aaaja// for some e > 0 such that 4 I 1. Then,
40
4C'L In (n) S <CCP
2( + B3 In( In (ALeInaTs (n))
(15)
hn
The right-hand side of Equation (15) is monotonically decreasing in and ñ. Hence, for sufficiently large c independent of à, we have ag. (LLhi.)
S 1. Thus, by applying Theorem A.3, we obtain the error bound with
bn
CCb
In())
a/(a+3)
4C
CCb
Tn V2L
22Euu03 uoz,)) + + 2c
ñ
From Proposition 5.6 and Definition 3.3, it follows that
Ev, (wag. u0;;:) =inf Ev, (ue, us;s))
52I inf dh (0:, (2.)) s 2LC2-
and
L
& 02,) - Ev. (u33, -uo;)) S 22-
With the choice of j as stated, we have
-a/la+3))
2 2
2a In(n)
Therefore,
-a/(at8)
2/ =0
ñ
In(
-a/(a+0)
ñ
d (0),,, 02.) =0
In(
which establishes the claim.
A.2.2. PROOF OF LEMMA 5.4 AND LEMMA 5.5 Here, we present the proofs of Lemma 5.4 and Lemma 5.5.
Proof of Lemma 5.4. By the Poincaré-type inequality,
(e ung.: 0. EE)) SN Cp
According to Definition 3.3, we have
Nn (0. 0. E ,, du (V., 02,) s du.) s C'2 10 m1/c)
17

---

Meta Optimality for Demographic Parity Constrained Regression via Post-Processing
e o' A,, and the log-covering number is zero if o'. Therefore,
Hov. (Cpo; {uo.: - uog.: 0, 3, du (0:, 8z. R2.) od)))
Cen
VInN(e: wozn U, j du ,0,, )2,) S o')
Colono')
10200 (Cr/een
<CPVC'20113 rano'
Vln((1/e)de.
By the Cauchy-Schwarz inequality, for any z E (0,1),
f /m(11/)dde s % ide J In(1/c)de
= =V2(=ln(1/2)+ s ==1++1n(1/2)
Thus,
How, (Cpo: { us, uaz, : d. E &9, (0., 02,) (.))))))))))))))) (oNosCCCCCCPPPuooo/o//oaaaiaaaaa
Proof of Lemma 5.5. Let I1-1l.o denote the oc-norm over Q. For any u, W(c,44,b,) (4, since v Q supported only on Q. For any d. E M ug,s belongs to the Hölder class with smoothness Interpreting uy, as a valued function, it follows from Park Muandet (2023) that there exists a constant 0, possibly depending on M, such that In N(c, {u, -ug, u, 44. lx)) S 1/21 Therefore,
bb) - ( CE- 1e-
Ho. (b; {u, uoz.: : u, E U1 by, (u: u.
=
which establishes the claim.
A.2.3. PROOF OF PROPOSITION 5.2
Proof of Proposition 5.2. We derive high probability upper bound through bounding the cumulant generating function.
Given random variable X probability space (2, 3, v)), define the cumulant generating function of X as for À E R,
<(>; X) In [n(E,(exp(AX]])
The Chernoff bound implies that for À A20 0,
P t) < exp(-Xt + x():
(16)
Hence, an upper bound on the cumulant generating function yields the corresponding high probability upper bound.
Let z(a) .... ((e) be n. i.i.d. copies of Z(x), Let o² Vr, Vu,lu,(Z())) and let b, be the minimum real such that (z()))))
E,, [u, (Z(+)) I b, almost surely. For > 0, we derive an upper bound on the cumulant generating function of (En,, Ey,) Ju. By the independence among (, we have
(uo(Z())) - uo(())s(dz)) )
<(>: (En.v. - Ev )u.) =
Σ n. In Ev, exp
X _ nt.
a .E[M]
Noting that the Bernstein's condition is satisfied for bounded random variable, we obtain
Ey, exp X w. n2
u, (z(()))) - ff (u(())ss(e (dz) (1))
M1
Ti
<
1 b
18

---

Meta Optimality for Demographic Parity Constrained Regression via Post-Processing
provided that A
S
b," Hence,
x w m2
0
<(A; (Bn. Ev.)u.) S
Σ n1
bg we
+E|M!
as long as
A Mi
S J
for all [M].
tx
Define x² = Exe[M]
wi0²2 na
x² a
and b max
1nbb 1 8.
Set X
which satisfies 0 X mh
S
1 for all
nhe
0-4th"
b,
8 E [M.. Then, we have
(En,p Ev)u.) - At
12 2520
t²
Σ ME[M]
2(0² + 1b)
02 1b
2a mh
Σ n MEMM]
m
2(0² + tb)
[ th
w.b.
σ2 +
n1
22 2 0
8²
82
itt²
11
<
(17)
2 tb)
52 + tb
2( + tb)
2(o² + 1b)
M
The claim follows by applying the Chernoff bound in Equation (16) with the upper bound derived in Equation (17).
A.2.4. PROOF OF PROPOSITION 5.3
Proof of Proposition 5.3. The desired claim obtained by applying Van Der Vaart & Wellner (Theorem 2.2.19 and Lemma 2.2.15 2023) with Proposition 5.2 and
1 (u: v.)).
dz(u, v() = o2 (u. u() d((
vn
A.2.5. PROOF OF PROPOSITION 5.6
Proof of Proposition 5.6. Let O, E M be arbitrary. We begin by expressing
Ev, u0
Σ We / (o,o()))s(d)))
SE(M]
= Σ we (ueLale) + ub. (Vi., (x)) Us vz(d))- -
Σ Ws / ubb (o).
ME(M]
ME[M]
Σ ws (uaolte ub. (1), (3)) us (ddz)) SE(M]
Σ
waubb (2)
ME(M]
where the last equality follows from the change variables vs = 3r- tv. By the assumption that Eve(an) wz)=+(=) = for all 2 52, we obtain
JΣ
Σ M
wout, (=)u(dz)= =
Σ
Ws L' (1
ME[M]
19

---

Meta Optimality for Demographic Parity Constrained Regression via Post-Processing
= | Jo Σ w.Dg (.0_"(x)dxv(((
sE[M]
/ I rdav(dz)
1 2/ 222(d2).
Therefore, we have
E ws / (o,o()))s(da)
sE[M]
1 Σ wis (ueule) + u/ (0 us (d(2)) - 2 / =²v((dz).
=
(18)
SE[M]
Next, for any 0. E M we derive upper and lower bounds for (z) + u/y, (0.. by employing the approach of Hütter Rigollet (2021). Since 0. M the function uø is L-smooth and 1/ Lsstonyyy convex. Thus, for all 2, x R. it holds that
L ア xx|2 x12 S (z) ua, - (x))(= -x) S
21
2
We first establish the lower bound. For 2, x E R, define
L
gu (x(2) (x) (z) 0,) x)) + 2/2 12 x²?
The convex conjugate of Oz at 1², (x:) is given by
1
(x)())) = (x, +x0
2L (1, 0x()))
Since for convex functions f.g. f S 9 implies ft 11208 gt, it follows that for all E R and any 0,, O. e M.
1 (2)) + up (v,())) 20.(2)) + (0,(2) 0,(2))²
(19)
2L
The upper bound is obtained analogously by considering
1
(x)=) (x) + 0(x)(2 x))
2T 2 x²²
leading to
(2) + (0,())) & 22) + L -
(20)
We now combine Equations (18) (20) to establish the claim. From Equation (18), we have
Ev, (uo. - uoz+)
Σ ws / (uecolt) + ub. (U), u2).0(2) + us (O (es))))ood))) vo(d)).
(21)
.E(M]
Observe that Duoi = (z), and the equality case of the Young-Fenchel inequality gives
Uerr (2) + w/y,,, (.,(()) (2).
(22)
Applying Equations (19) and (22) with D! 07,5 in Equation (21), we obtain
Fry (uo, udz..)
20

---

Meta Optimality for Demographic Parity Constrained Regression via Post-Processing
W / (J,(z) 22,0 (z)) (d))
ME[M]
wody (0.. (2 = dy (0., F2,)
2L
2L
#EIM
Similarly, by using Equation (20) place of Equation (19), we have
L Ey, uoz;) - (0..
A.3. Proofs for Section 4
A.4. Proof of Corollary 4.2
Proof of Corollary 4.2. According to Theorem 5.1 and Proposition 4.5, there exists decreasing sequence 7n and constant
C' > O such that, for all t 2 1,
Par inf max Wa > Ctr Seet.
ME(M]
By choosing t = Tn 11/ follows that
P Fu inf max Wn p) > o(1) s o(1). aE[M]
Therefore, inf,, maX (M, 14) converges to inf, max (n (u) 0, holds that Iux,I
probability. In the case where Mn,Muux.M which satisfies (strict) demo- graphic parity. Consequently, fn.: is consistently fair. The error upper bound can be established directly by combining Theorem 5.1 and Proposition 4.4.
A.4.1. PROOF OF PROPOSITION 4.4
Proof of Proposition 4.4. We begin by applying the triangle inequality, which yields
dux. (Fnor Pa.)) s dux. (Jm.: Upgs fn.) dux. (Diz. Snas Oyys Sūs) dux. (Digo Shnz Paa). (23)
The first term in (23) represents the estimation enror of the optimal transport map:
/ (1Ono fn,e(()) (0 (0 o fnro) fm))(()) pxx (dx)
dxx, Un.:0mpp o Sni) = Σ ws
3E M
Σ ws (Pnale) 0 1 (dz) dz (On,s 07
SE
M)
For the second term in (23), we establish the L-Lipschitz continuity of ox 0" By the first assumption in Assumption 3.1, fn,: F implies fn,: Py, which ensures that "y O. The L-Lipschitz continuity of 0r pjj. then follows from Assumption 3.2. Therefore, we can bound the second term as
Eyan 1i (x.: (0 o Sn Dpyn o Si:) S I.
(Jnor (Ixis sand
$12 122 Σ (P.).
SE(M]
For the third term in (23), we utilize Proposition 5.6 obtain
d2 (Wmgi o Spr.. Si.)) = (Fe Oprs)
21

---

Meta Optimality for Demographic Parity Constrained Regression via Post-Processing
<2LEpsa uopg" uozzy1)
521 (F - -Fugi) (w0z.= woz,"
S2L (Bus. -Euge)
+ 2L ( (Eys. - Engi w0
Let sp: be mappings such that f. = Ms.s. For 0: = -pyy: or
0x "gg we have
( (Fwy.o- - Figr0) uoo.
=Iʃ (u0 (z)s(
/ J. ( dx(r)dri (d)))
- / 2 (Pp(x)) v))
L W (US.0.H1..)
L 1. de (fnnssfs)))
$
2
where we use the identity ua.,(x) - (v) J 0.(2)dz for all v. y E IR, which follows from Taylor's theorem, to obtain the second equality. Taking expectations, we obtain
E E [oxx. (Dig: Spsn
s 2T.
Σ
WeEpp EE, (P.)) 2T.
Σ
Wren, (Po)-
*E MM[M]
sE[M]
By combining the above results, we have
Eng0 ux, (Fn Pins)
3T 3Rp
(Dn..
) + 91, sE[M]
Σ WgEn, (Pe):
where Jensen's inequality is applied. Finally, due to the mutual independence between fn. and i (k.. resulting from sample splitting, we have Epen
de (xx, (On.. 0 [ Eny, ( (Dn... 07 )- This completes the proof.
A.4.2. PROOF OF PROPOSITION 4.5
Proof of Proposition 4.5. Let j be the barycenter of Hf with weight w.. For any probability measure have
W) W₂ (0n,.tt1 SW2 (n 9r (113, + Wa (202) (1))..E(
Sdup, (nner 0pg.e) + W2 (Mz.v).
Therefore, we obtain
max Wo (F s max dyy., (Dmsr Dr 0ig.)) + Wz (19212) sE[M
sE(M
dpe. (Bn.s 0igz)) + We (1zz.))
M Wumin
Consequently, it follows that
inf max Wa ( S sv Mummi day. (Bn., Diya)) inl W2 (ug.v) = V Mumin day. (Dnir 2r ppp.).
i xE[M]
22

---

Meta Optimality for Demographic Parity Constrained Regression via Post-Processing
A.5. Proofs for Section 6
Proof of Theorem 6.1. We begin by noting that, by definition, fn.s Fs. According the second requirement in Assumption 3.1, it holds that Fi fn Fi. Therefore, fn can be interpreted as the standard regression estimator for P1 based sample of size By the definition of the minimax error, we have
Far. Furthermore, the third requirement in Assumption 3.1 ensures that
Eup [ [exx (frs 2 (PI).
sup A EE (M)
Next, utilizing the convexity of de, we obtain
Bye ( (Jns shail
Σ
Wr de uxx. (Jr firz)
sup W.EP
sup
sE(M]
sup MI M sE
Σ
w. pot (ux
When #1 =... JuM, the transport map S... becomes the identity function for all s. Thus.
W' W.yEug ( (Piss
Σ E.g (oex (Fr Pin)))
sup MeP
sE[M]
SE(M]
E dP ( Piit))
sup
Moreover, by the second requirement Assumption 3.1, for any Pı. the tuple (H....,,)) belongs to P. Therefore,
M times
Eyp dh dex (
S sup Euy [d2 dxx Unin:pp M.P
sup MM),
F1
23


Reviews:
[{"review_id": "FF9lpIH4bU", "reviewer": "Reviewer_pMTi", "summary": "This paper investigates the theoretical properties of fair regression problems by leveraging optimal transport techniques. It provides important theoretical bounds in the context of fair regression, and designs regression algorithm matching the upper bound.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their positive feedback and for recognizing the importance of our theoretical contributions in fair regression.", "claims_and_evidence": "Yes.  The overall structure of this paper is logical and sound, with the logic flow clear.", "methods_and_evaluation_criteria": "Not applicable. This is a theoretical paper.", "theoretical_claims": "Not in detail - looks reasonable.", "experimental_designs_or_analyses": "Not applicable", "relation_to_broader_scientific_literature": "This paper provides new theoretical analysis for the problem of fair regression.", "essential_references_not_discussed": "N/A", "other_strengths_and_weaknesses": "N/A", "other_comments_or_suggestions": "N/A", "questions_for_authors": "N/A", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "bBful6uBgs", "reviewer": "Reviewer_TX3y", "summary": "This paper studied the fair regression problem with demographic parity as a constraint. It claimed that existing minimax optimal regression algorithms are coupled with data generation methods, and proposed meta-theorems to validate the fair minimax optimality. Then they demonstrated that the optimal regression can be achieved through post-processing methods, which thus can be efficiently and flexibly achieved.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate the reviewer's comprehensive feedback and would like to address their main concerns:\n\nW1: Rawlsian Fairness\n\nWe wish to clarify that Rawlsian fairness is fundamentally different from equality-based fairness concepts like demographic parity and equalized odds. Rawlsian fairness focuses on minimizing adverse effects on the most disadvantaged group, whereas equality-based fairness aims for equal treatment across groups. Due to these fundamental differences, results from Rawlsian and equality-based fairness approaches are not directly comparable.\n\nFurthermore, we emphasize that minimax optimality is a well-established concept in statistical literature, used to define the best estimator for a statistical estimation problem. In our context, \"minimax\" involves maximizing over all possible underlying distributions and minimizing over all estimation algorithms. This concept differs from Rawlsian fairness, as we can define a minimax optimal Rawlsian fair learning algorithm that minimizes the worst-case error, considering both underlying distributions and groups.\n\nRegarding data generation models, they represent potential underlying distributions in nature. Considering a specific set of data generation models is not a limitation of the learner's ability but rather reflects prior knowledge about the data. The sample complexity varies based on this prior knowledge. Extensive research in statistical literature has shown how prior knowledge fundamentally influences sample complexity. Our meta-theorem can accommodate various prior knowledge assumptions by leveraging these existing results.\n\nW2: Group-wise Regressor\n\nWe use a group-wise predictor because it is commonly employed in fairness literature. Developing an optimal post-processing method for an unaware predictor is an important area for future research.\n\nW3: Classification\n\nIn the context of minimax optimality, regression problems are often considered more fundamental than classification problems, as the minimax optimal error for classification is typically derived using regression techniques. Extending our work to classification problems is a significant direction for future research.", "claims_and_evidence": "The claim that existing analyses are coupled with data generation is not clear. I saw it was mentioned in introduction while I cannot connect it in the main methodology.", "methods_and_evaluation_criteria": "This is a theoretical paper which provides analyses instead of new methods.", "theoretical_claims": "I read through the theoretical analyses but only understand some parts of them.", "experimental_designs_or_analyses": "No experiments were presented in the paper.", "relation_to_broader_scientific_literature": "I checked the related papers about OT map estimation in Wasserstein barycenter problems and minimax optimality under regression research. However, I cannot immediately get the corresponding improvements over these works although the authors have highlighted their differences.", "essential_references_not_discussed": "I have related comments below.", "other_strengths_and_weaknesses": "Strengths: I think the three listed contributions are important if they are correct. The meta-optimality connects the minimax optimal error for fair regression and traditional regression. They demonstrated that optimal regression models can be fair through post-processing method. And they provide convergence rate analysis for the transport map estimation. \n\nWeaknesses:\n1. The first thing I felt confused is that in fairness research, minimax optimality also refers to minimizing the risk of the worst group [1], which is under the Rawlsian fairness concept.  I found the authors are working at a different area after I checked the work of Chzhen& Schreuder (2022) and Zeng (2024). The authors mentioned the worst-case error taken over a certain set of data generation models, while I did not understand how this limitation is addressed in this paper.\n2. I found regressor f is group-wise (line 75). Then a conventional regressor may be group unaware. How to do post-processing in this case? Maybe I am questioning in an incorrect way.\n3. I realised this work and some earlier ones focus on regression analyses. I am curious why regression is considered only? Will these analyses be true for classification as well? A recent paper [2] pointed out loss/error is more sensitive than discrete perditions when considering risk distributions. Is this paper sharing a similar insight?\n\n\n[1] Minimax Pareto Fairness: A Multi Objective Perspective. ICML 2020.\n[2] Towards Harmless Rawlsian Fairness Regardless of Demographic Prior. NeruIPS 2024.", "other_comments_or_suggestions": "Is the proposed post-processing algorithm a new method compared with existing post-processing fairness work? Then would the experiments on it help justify the advances?", "questions_for_authors": "I would consider it is a good paper if authors can address my above concerns.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "jHwTVwZsLw", "reviewer": "Reviewer_vUCB", "summary": "This paper considers fair regression with respect to statistical parity under the attribute-aware setting. The main focus/contribution is on obtaining a minimax rate for learning fair regressors:\n\n1. Taking the post-processing perspective/approach to achieving fairness, and leveraging the error decomposition result in prior work, this paper bound the minimax rate for fair regression as (minimax rate of the unconstrained regression problem) + (sample complexity of learning the fair post-processor); the fair post-processor is the optimal transports to the barycenter of the output distributions of the unconstrained regressors.\n2. The authors cast the problem of learning the barycenter/optimal transports as optimizing over the congruent potentials.\n3. A sample complexity bound for learning the barycenter/optimal transports.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate the reviewer’s detailed feedback. Here, we address the main concerns:\n\nW1:\n\nA pertinent example is when $f^*_{\\mu,s}$ is a composition of multiple functions, i.e., $f^*_{\\mu,s} = g_q \\circ ... \\circ g_0$, within the Holder class as used by Schmidt-Hieber (2020), and $\\vartheta^*_{\\mu,s}$ belongs to the Sobolev space. In this scenario, $\\mathcal{E}_{n_s}(\\mathcal{P}_s) = \\Theta(\\max_i n_s^{-2\\beta^*_i/(2\\beta^*_i + t_i)})$, where $\\beta^*_i$ represents the cumulative smoothness for $g_q, ..., g_i$, and $t_i$ indicates the dimensionality of the input of $g_i$. For the Sobolev space with smoothness $\\gamma > 0$, Definition 3.3 is satisfied with $\\alpha = 2\\gamma$ and $\\beta = 1$ by selecting $\\Theta_j$ as a set of functions spanned by the first $j$ wavelet bases. The rate becomes $\\max_i n^{-2\\beta^*_i/(2\\beta^*_i + t_i)} + n^{-2\\gamma/(2\\gamma + 1)}$, up to logarithmic factors, under the assumption $n_s \\ge cw_s n$. If $g_i$ and $\\vartheta^* _{\\mu,s}$ share the same level of smoothness, i.e., $\\beta^* \\approx \\gamma$, the first term dominates the second if $t_i > 1$ for some $i$. Here, $t_i$ denotes the dimensionality of the essential intermediate data representation. Such an intermediate representation may have multiple dimensions, i.e., $t_i > 1$, causing the first term from the conventional regression problem to dominate the rate.\n\nWe will incorporate this example after discussing the implications of the main theorem in the revised version.\n\nW2, W4:\n\nOur results offer significant advantages over the error bounds presented by Chzhen et al. (2020). Firstly, our results are derived under weaker assumptions. Their results necessitate the conventional regression algorithm to have a sub-Gaussian high-probability error bound, whereas our results only require a bound on the expected square error. Additionally, while they demand constant upper and lower bounds on the density of $\\nu_i$, we only assume the Poincare-type inequality. This broadens the applicability of our meta-theorem compared to their findings.\n\nSecondly, their results cannot achieve a rate faster than $n^{-1/2}$, as their upper bound on the estimation error of $\\vartheta^*_{\\mu,:}$ is $n^{-1/2}$ and dominates other terms. However, our results can achieve a rate faster than $n^{-1/2}$ by leveraging the smooth structure of $\\vartheta^*_{\\mu,:}$.\n\nThus, our results can demonstrate a faster rate under weaker assumptions compared to those provided by Chzhen et al. (2020). We will include this discussion as an implication of our main theorem in the revised version.\n\nW3:\n\nWe wish to clarify that our results do not contradict those of (Woodworth et al., 2017), as their results pertain to equalized odds, not demographic parity. Our findings show that concerning sample size, post-processing can be optimal. However, it may be suboptimal for other parameters, such as the Lipschitz constant $L$ and the number of groups $M$. Analyzing optimality for these parameters is an important direction for our future work.", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "N/A", "theoretical_claims": "Did not check proof in detail, but the presented results are reasonable/expected.", "experimental_designs_or_analyses": "N/A", "relation_to_broader_scientific_literature": "- Paper adopts the \"post-processing\" perspective of [Chzhen et al., 2020] and [Le Gouic et al., 2020] for fair regression, and leveraged its error decomposition to derive the minimax rate (of which there are also prior work, even though are limited to specific data generation processes; see weakness 1).\n- The barycenter/optimal transport estimator used in this paper is inspired by [Korotin et al., 2022], for which the authors derived the sample complexity bound.", "essential_references_not_discussed": "Le Gouic et al.  Projection to Fairness in Statistical Learning.  2020.", "other_strengths_and_weaknesses": "Weaknesses.\n\n1. Theorem 3.4 states a minimax rate in terms of the minimax rate of the unconstrained regression problem plus the sample complexity of learning the barycenter/optimal transports.  A heuristic interpretation of the result is given in remark 3, which says that if the regression problem is *harder* than that of learning the transports (\"Such a\nsituation may frequently happen\"), then the minimax rate would be dominated by that of the regression problem.  Unfortunately, no concrete examples is provided to show when would the minimax rate be dominated by the first term.\n\n\tIn particular, the reviewer is curious about the complexity of learning the barycenter/optimal transport as conveyed in the second term.  For example, on synthetic problems constructed in prior work that analyzes minimax optimality of fair regression, what does the constants $\\alpha$ and $\\beta$ instantiate to, and does the second term decay faster than the first?\n\n2. Because Theorem 3.4 is derived from the *post-processing* perspective, the second term could have been replaced by any sample complexity bound for learning the barycenter/optimal transports.  How does the derived bound compare (or why incomparable) to that in section 4 of [Chzhen et al., 2020], which was derived for a nonparametric estimate?\n\n3. The result in Theorem 3.4 is obtained by taking the *post-processing* perspective, rather than analyzing the fair regression problem in an *end-to-end* manner (i.e., in-processing), so the caveats of post-processing vs. in-processing applies.  In particular, post-processing can be suboptimal if the class of regressor is constrained, that is, constraining the $\\inf_{f_n}$ in $\\mathcal E_{n_s}$; see [Woodworth et al., 2017].\n\n4. The algorithm in Section 4 basically takes the same form of that in [Chzhen et al., 2020], except that here the barycenter/optimal transports are estimated by optimizing the congruent potentials on the empirical problem.  It is unknown how it compares to the original nonparametric estimator, and there is no experiment results in this paper, so the contributions in this section is unclear.  What are the benefits of using the new formulation compared to the original?", "other_comments_or_suggestions": "- line 180: incomplete sentence\n- line 301: Dodley -> Dudley", "questions_for_authors": "See weaknesses.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper addresses the problem of fair regression under demographic parity, with a focus on providing minimax optimality guarantees in an attribute-aware setting. The core contribution is a theoretical framework that decomposes the minimax risk for fair regression into two components: the minimax rate of the unconstrained regression problem and the sample complexity of learning a fair post-processor, which is an optimal transport map to a Wasserstein barycenter. The authors frame this estimation problem through congruent potentials and provide convergence guarantees for the barycenter estimator.

Strengths:

The paper contributes to the theoretical understanding of fair regression by clarifying the statistical cost of post-processing methods relative to unconstrained learning. The meta-theorem and decomposition offer a structured lens for analyzing fair learning under distributional constraints, and extend existing results by [Chzhen et al., 2020] and [Le Gouic et al., 2020]. The authors provide sample complexity bounds for the post-processing component, drawing from recent developments in optimal transport theory (e.g., [Korotin et al., 2022]).

Weaknesses:

Both reviewers noted ambiguity in the claim that existing analyses are tightly coupled with specific data generation processes. Some conceptual issues were raised around the applicability and limitations of post-processing, particularly when the function class of the unconstrained regressor is restricted. There is no direct comparison to related results in [Chzhen et al., 2020] on nonparametric estimation, nor examples illustrating when the regression component dominates the learning cost.

Overall, this is a conceptually valuable and mathematically interesting contribution to the theory of fair regression. It clarifies the statistical limits of fairness through post-processing and advances the literature on minimax optimality in constrained learning. However, the paper would be substantially strengthened by clearer exposition, more thorough justification of certain claims, and concrete examples or experiments that ground the theory.
Decision: Accept (poster)