# Differentially Private Post-Processing for Fair Regression

Ruicheng Xian  University of Illinois Urbana-Champaign
<EMAIL_ADDRESS>Qiaobo Li  University of Illinois Urbana-Champaign
<EMAIL_ADDRESS>Gautam Kamath  University of Waterloo and Vector
Institute
<EMAIL_ADDRESS>Han Zhao  University of Illinois Urbana-Champaign
<EMAIL_ADDRESS>
###### Abstract

This paper describes a differentially private post-processing algorithm for
learning fair regressors satisfying statistical parity, addressing privacy
concerns of machine learning models trained on sensitive data, as well as
fairness concerns of their potential to propagate historical biases. Our
algorithm can be applied to post-process any given regressor to improve
fairness by remapping its outputs. It consists of three steps: first, the
output distributions are estimated privately via histogram density estimation
and the Laplace mechanism, then their Wasserstein barycenter is computed, and
the optimal transports to the barycenter are used for post-processing to
satisfy fairness. We analyze the sample complexity of our algorithm and
provide fairness guarantee, revealing a trade-off between the statistical bias
and variance induced from the choice of the number of bins in the histogram,
in which using less bins always favors fairness at the expense of error.

##  1 Introduction

Prediction and forecasting models trained from machine learning algorithms are
ubiquitous in real-world applications, whose performance hinges on the
availability and quality of training data, often collected from end-users or
customers. This reliance on data has raised ethical concerns including
fairness and privacy. Models trained on past data may propagate and exacerbate
historical biases against disadvantaged demographics, and producing less
favorable predictions (Bolukbasi et al., 2016; Buolamwini and Gebru, 2018),
resulting in unfair treatments and outcomes especially in areas such as
criminal justice, healthcare, and finance (Barocas and Selbst, 2016; Berk et
al., 2021). Models also have the risk of leaking highly sensitive private
information in the training data collected for these applications (Dwork and
Roth, 2014).

While there has been significant effort at addressing these concerns, few
treats them in combination, i.e., designing algorithms that train fair models
in a privacy-preserving manner. A difficulty is that privacy and fairness may
not be compatible: exactly achieving group fairness criterion such as
statistical parity or equalized odds requires precise (estimates of) group-
level statistics, but for ensuring privacy, only noisy statistics are allowed
under the notion of differential privacy. Resorting to approximate fairness,
prior work has proposed private learning algorithms for reducing disparity,
but the focus has been on the classification setting (Jagielski et al., 2019;
Xu et al., 2019; Mozannar et al., 2020; Tran et al., 2021).

In this paper, we propose and analyze a differentially private post-processing
algorithm for learning attribute-aware fair regressors under the squared loss,
with respect to the fairness notion of statistical parity. It can take any
(privately pre-trained) regressor and remaps its outputs (with minimum
deviations) to improve fairness. At a high-level, our algorithm consists of
three steps: estimating the output distributions of the regressor from data,
computing their Wasserstein barycenter, and the optimal transports (Chzhen et
al., 2020; Le Gouic et al., 2020; Xian et al., 2023). To make this process
differentially private, we use private histogram density estimates (HDE) for
the distributions via the Laplace mechanism (Diakonikolas et al., 2015; Xu et
al., 2012), followed by re-normalization, which introduces additional
complexity in our analysis. The choice of the number of bins in the HDE
induces a trade-off between the statistical bias and variance for the cost of
privacy and fairness. Our theoretical analysis and experiments show that using
less bins always improves fairness at the expense of higher error.

#### Paper Organization.

In Section 2, we introduce definitions, notation, and the problem setup.
Section 3 describes our private post-processing algorithm for learning fair
regressors, with finite sample analysis of the accuracy-privacy-fairness
trade-offs in Section 3.4. Finally in Section 4, we empirically explore the
trade-offs achieved by our post-processing algorithm on Law School and
Communities & Crime datasets.

###  1.1 Related Work

#### Differential Privacy.

Under the notion of differential privacy (Dwork et al., 2006) and subsequent
refinements such as Rényi DP (Mironov, 2017), a variety of private learning
algorithms are proposed for settings including regression, classification, and
distribution learning. There are private variants of logistic regression
(Papernot et al., 2017), decision trees (Fletcher and Islam, 2019), and linear
regression (Wang, 2018; Covington et al., 2021; Alabi et al., 2022). The
problem of private distribution learning has been studied for finite-support
distributions (Xu et al., 2012; Diakonikolas et al., 2015) and parameterized
families (Bun et al., 2019; Aden-Ali et al., 2021). Lastly, private
optimization algorithms including those based on objective perturbation
(Chaudhuri et al., 2011; Kifer et al., 2012) and DP-SGD (Song et al., 2013;
Bassily et al., 2014; Abadi et al., 2016) are proposed for solving convex and
general optimization problems.

#### Algorithmic Fairness.

In parallel, the study of algorithmic fairness revolves around the
formalization of fairness notions and design of bias mitigation methods
(Barocas et al., 2023). Fairness criteria include those that focus on
disparate impact of the model, such as individual fairness (Dwork et al.,
2012), which asks the model to treat similar inputs similarly, or group-level
statistical parity (Calders et al., 2009) and equalized odds (Hardt et al.,
2016); and, those on performance inequality, e.g., accuracy parity (Buolamwini
and Gebru, 2018; Chi et al., 2021), predictive parity (Chouldechova, 2017),
and multi-calibration (Hébert-Johnson et al., 2018). Fair algorithms are
categorized into pre-processing, by removing biased correlation in the
training data (Calmon et al., 2017); in-processing, that turns the original
learning problem into a constrained one (Kamishima et al., 2012; Zemel et al.,
2013; Agarwal et al., 2018, 2019); and post-processing, which remaps the
predictions of a trained model post-hoc to meet the fairness criteria (Hardt
et al., 2016; Pleiss et al., 2017; Chzhen et al., 2020; Zhao and Gordon, 2022;
Xian et al., 2023).

#### Fairness and Privacy.

Private fair learning and bias mitigation algorithm are proposed and studied
in prior work (Jagielski et al., 2019; Xu et al., 2019; Mozannar et al., 2020;
Tran et al., 2021), but they have so far been focused on the classification
setting. It remains an open question on how to achieve private fair
regression, and what are the trade-offs between privacy, fairness, and
accuracy.

Cummings et al. (2019) and Agarwal (2020) showed that fairness and privacy are
incompatible in the sense that no $\varepsilon$-DP algorithm can generally
guarantee group fairness on the training set (from which population-level
guarantees can be derived via generalization), unless the hypothesis class is
restricted to constant predictors. The argument is that a predictor $f$ that
is fair on $S$ may not be fair on its neighbor $S^{\prime}$, so an
$\varepsilon$-DP algorithm that outputs $f$ on $S$ with nonzero probability
may also output $f$ on $S^{\prime}$, which is unfair. Work on private fair
algorithms circumvent this incompatibility by relaxing to high probability
guarantees for fairness. Bagdasaryan et al. (2019) showed that the performance
impact of privacy may be more severe on underrepresented groups, resulting in
accuracy disparity.

##  2 Preliminaries

A regression problem is defined by a joint distribution $\mu$ of the
observations $X\in\mathcal{X}$, sensitive attribute $A\in\mathcal{A}$ (which
has finite support), and the response $Y\in\mathbb{R}$. We will use upper case
$X,A,Y$ to denote the random variables, and lower case $x,a,y$ instances of
them. The goal of this paper is to develop a privacy-preserving post-
processing algorithm for learning (randomized) fair regressors. We consider
the attribute-aware setting, i.e., the sensitive attribute $A$ is available
explicitly during both training and prediction and can be taken as input by
the regressor, $f:\mathcal{X}\times\mathcal{A}\rightarrow\mathbb{R}$.

The risk of a regressor is defined to be mean squared error, and its excess
risk is defined with respect to the Bayes regressor,
$f^{*}(x,a)\coloneqq\operatorname{\mathbb{E}}[Y\mid X=x,A=a]$:

$\displaystyle R(f)$
$\displaystyle:=\operatorname{\mathbb{E}}[(f(X,A)-Y)^{2}],$ (2)
$\displaystyle\operatorname{\mathit{ER}}(f)$
$\displaystyle:=R(f)-R(f^{*})=\operatorname{\mathbb{E}}[(f(X,A)-f^{*}(X,A))^{2}]$
(3)

by the orthogonality principle, where $\operatorname{\mathbb{E}}$ is taken
with respect to $\mu$ (and the randomness of $f$).

Given a (training) dataset $S$ consisting of $n$ i.i.d. samples of $(X,A,Y)$,
a private learning algorithm minimizes the leakage of any individual’s
information in its output. We use the notion of differential privacy (Dwork et
al., 2006), which limits the influence of any single training sample:

######  Definition 2.1 (Differential Privacy).

A randomized (learning) algorithm $\mathscr{A}$ is
$\varepsilon$-differentially private (DP) if for all pairs of nonempty
neighboring datasets $S,S^{\prime}$,

$\operatorname{\mathbb{P}}(\mathscr{A}(S)\in O)\leq
e^{\varepsilon}\operatorname{\mathbb{P}}(\mathscr{A}(S^{\prime})\in
O),\quad\forall O\subseteq\operatorname{\mathrm{range}}(\mathscr{A}),$ (4)

where $\operatorname{\mathbb{P}}$ is taken with respect to the randomness of
$\mathscr{A}$.

We say two datasets are neighboring if they differ in one entry by
substitution (our result also covers insertion and deletion operations, which
may have lower sensitivity). Note that privacy is guaranteed with respect to
both $A$ and $X$.

For fairness, we consider statistical parity (Calders et al., 2009), which
requires the output distributions of $f$ conditioned on each group to be
similar. The similarity between distributions is measured in
Kolmogorov–Smirnov distance, defined for probability measures $p,q$ supported
on $\mathbb{R}$ by

$D_{\textnormal{KS}}(p,q)=\sup_{t\in\mathbb{R}}\left|\int_{-\infty}^{t}\left\lparen
p(x)-q(x)\right\rparen\mathop{}\\!\mathrm{d}x\right|.$ (5)

######  Definition 2.2 (Statistical Parity).

A (randomized) regressor $f:\mathcal{X}\times\mathcal{A}\rightarrow\mathbb{R}$
satisfies $\alpha$-approximate statistical parity (SP) if

$\Delta_{\textnormal{SP}}(f)\coloneqq\max_{a,a^{\prime}\in\mathcal{A}}D_{\textnormal{KS}}(r_{a},r_{a^{\prime}})\leq\alpha,$
(6)

where $r_{a}$ is the distribution of regressor output $f(X,A)$ conditioned on
$A=a$.

##  3 Fair and Private Post-Processing

Figure 1: Illustration of the private fair post-processing steps 1–3 performed
in Algorithm 1. The (randomized) transports to the barycenter are represented
by (sparse) $k\times k$ matrices, and the value at the $(i,j)$-th entry is the
probability of transporting to bin $j$ given bin $i$.

We describe a private post-processing algorithm such that, given an unlabeled
training dataset $S=\\{(x_{i},a_{i})\\}_{i\in[n]}$ sampled from $\mu$, and a
(privately) pre-trained regressor $f$ (e.g., learned using the algorithms
mentioned in Section 1.1), the algorithm learns a mapping $g$ that transforms
the output of $f$ (a.k.a. post-processing) so that $\bar{f}\coloneqq g\circ f$
is fair, while preserving differential privacy with respect to $S$.

Compared to in-processing approaches for fairness, post-processing decouples
the conflicting goals of fairness and error minimization, since the regressor
$f$ can be trained to optimality without any constraint, and then post-
processed to satisfy fairness. We show that this decoupling does not affect
the optimality of the resulting fair regressor $\bar{f}$—the optimal fair
regressor can be recovered via post-processing if the algorithm in the pre-
training stage learns the Bayes regressor $f^{*}$ (Theorem 3.1). Moreover,
post-processing has low sample complexity and only requires unlabeled data
(Theorem 3.3), so labeled data (that may be scarce in some domains) can be
dedicated entirely to error minimization, which is typically a more difficult
problem.

###  3.1 Fair Post-Processing with Wasserstein-Barycenters

Exact statistical parity ($\alpha=0$) requires all groups to have identical
output distributions, so finding the fair post-processing mapping $g$ that
incurs minimum deviations from the original outputs of $f$ amounts to the
following steps (Chzhen et al., 2020; Le Gouic et al., 2020):

  1. 1.

Learn the output distributions of $f$ conditioned on each group, $r_{a}$, for
all $a\in\mathcal{A}$.

  2. 2.

Find a common (fair) distribution $q$ that is close to the original
distributions (i.e., their barycenter).

  3. 3.

Compute the optimal transports $g_{a}$ from $r_{a}$ to the barycenter $q$.

The (randomized) transports are then applied to post-process $f$ to obtain a
fair attribute-aware regressor $\bar{f}(x,a)=g_{a}\circ f(x)$, so that every
group has the same output distribution equal to $q$.

Formally, $q$ is called the Wasserstein barycenter of the $r_{a}$’s, which is
a distribution supported on $\mathbb{R}$ with minimum total distances to the
$r_{a}$’s as measured in Wasserstein distance:

$q\in\operatorname*{arg\,min}_{q^{\prime}:\operatorname{supp}(q^{\prime})\subseteq\mathbb{R}}\sum_{a\in\mathcal{A}}w_{a}W_{2}^{2}(r_{a},q^{\prime}),$
(7)

where $w_{a}\coloneqq\operatorname{\mathbb{P}}(A=a)$,

$W_{2}^{2}(r_{a},q)=\min_{\pi_{a}\in\Pi(r_{a},q)}\int_{\mathbb{R}\times\mathbb{R}}(y-y^{\prime})^{2}\mathop{}\\!\mathrm{d}\pi_{a}(y,y^{\prime}),$
(8)

and
$\Pi(p,q)=\\{\pi:\operatorname{supp}(\pi)\subseteq\mathbb{R}\times\mathbb{R},\int\pi(x,y^{\prime})\mathop{}\\!\mathrm{d}y^{\prime}=p(x),\int\pi(x^{\prime},y)\mathop{}\\!\mathrm{d}x^{\prime}=q(y),\forall
x,y\\}$ is the collection of probability couplings of $p,q$. The value of
$W_{2}^{2}(r_{a},q)$ naturally represents the squared cost of transforming
$r_{a}$ into $q$, i.e., the minimum amount of output deviations (in squared
distance) required to post-process $f$ for group $a$ so that its output
distribution is transformed to $q$ (which is a consequence of Lemma A.4);
specifically, this optimal post-processor is given by the optimal transport
from $r_{a}$ to $q$.

###  3.2 Generalization to Approximate Statistical Parity

To handle approximate statistical parity ($\alpha>0$), in step 2, we first
replace the barycenter in Eq. 7 by a KS ball of radius
$\nicefrac{{\alpha}}{{2}}$ and relax the problem to finding target output
distributions $q_{a}$ for each group $a$ inside the ball with minimum
$W_{2}^{2}$ distance to the original distribution $r_{a}$. Then in step 3, we
find the optimal transports $g_{a}$ from $r_{a}$ to $q_{a}$. So, the problem
in Eq. 7 is generalized to the approximate SP case with

$\displaystyle\quad\hypertarget{eq:p}{\mathrm{P}}(\\{r_{a}\\}_{a\in\mathcal{A}},\\{w_{a}\\}_{a\in\mathcal{A}},\alpha):$
$\displaystyle\operatorname*{arg\,min}_{\begin{subarray}{c}q:\operatorname{supp}(q)\subseteq\mathbb{R}\\\
\\{q_{a}\\}_{a\in\mathcal{A}}\subset
B_{\textnormal{KS}}(q,\nicefrac{{\alpha}}{{2}})\end{subarray}}\sum_{a\in\mathcal{A}}w_{a}W^{2}_{2}(r_{a},q_{a}),$

where
$B_{\textnormal{KS}}(q,\nicefrac{{\alpha}}{{2}})=\\{p:D_{\textnormal{KS}}(p,q)\leq\nicefrac{{\alpha}}{{2}}\\}$
is a KS ball centered at $q$ on the space of probability distributions
supported on $\mathbb{R}$.

When learning from finite samples $S$ (non-privately), we replace
$r_{a},w_{a}$ in P with the respective empirical distributions/estimates.
Computationally, solving P on the empirical distributions is as hard as the
finite-support Wasserstein barycenter problem $(\alpha=0)$, which can be
formulated by a linear program of exponential size in $|\mathcal{A}|$ (Anderes
et al., 2016; Altschuler and Boix-Adserà, 2021). To reduce the complexity, we
restrict the support of the barycenter $q$ via discretization; this fixed-
support approximation is common in prior work (Cuturi and Doucet, 2014; Staib
et al., 2017).

The validity of the post-processing algorithm described above is supported by
the fact that, if the regressor being post-processed is Bayes optimal, then
the resulting fair regressor is also optimal. This has been established for
the exact SP case in prior work (e.g., Le Gouic et al., 2020, Theorem 3), and
here we provide a more general result for approximate SP:

######  Theorem 3.1.

Let a regression problem be given by a joint distribution $\mu$ of $(X,A,Y)$,
denote $w_{a}=\operatorname{\mathbb{P}}(A=a)$, the Bayes regressor by
$f^{*}(x,a)=\operatorname{\mathbb{E}}[Y\mid X=x,A=a]$, and its output
distribution conditioned on group $a$ by $r^{*}_{a}$. Then

$\min_{f:\Delta_{\textnormal{SP}}(f)\leq\alpha}\operatorname{\mathit{ER}}(f)=\min_{\begin{subarray}{c}q:\operatorname{supp}(q)\subseteq\mathbb{R}\\\
\\{q_{a}\\}_{a\in\mathcal{A}}\subset
B_{\textnormal{KS}}(q,\nicefrac{{\alpha}}{{2}})\end{subarray}}\sum_{a\in\mathcal{A}}w_{a}W^{2}_{2}(r^{*}_{a},q_{a}).$
(9)

This shows that the excess risk of the optimal fair regressor is indeed the
value of the Wasserstein barycenter problem (P) discussed above, and can be
achieved by $f^{*}$ post-processed using the optimal transports to the
barycenter. All proofs are deferred to Appendices A and B; this result follows
from an equivalence between learning regressors and learning post-processings
of $f^{*}$.

###  3.3 Privacy via Discretization and Private PMF Estimation

Algorithm 1 Fair and Private Post-Processing (Attribute-Aware)

1:Regressor $f:\mathcal{X}\times\mathcal{A}\rightarrow\mathbb{R}$, samples
$\\{x_{i},a_{i}\\}_{i\in[n]}$, interval $[s,t]$, number of bins $k$, fairness
tolerance $\alpha$, privacy budget $\varepsilon$

2:Let $v_{j}=\nicefrac{{(j-1/2)(t-s)}}{{k}}$ for all $j\in[k]$$\triangleright$
midpoints of the bins

3:Define $h(y)=\operatorname*{arg\,min}_{j\in[k]}|y-v_{j}|$ $\triangleright$
discretizer

4:Define
$\hat{p}(a,v_{j})=\nicefrac{{1}}{{n}}\sum_{i\in[n]}\operatorname{\mathds{1}}[h\circ
f(x_{i},a_{i})=v_{j}]$ $\triangleright$ empirical joint distribution

5:Define
$\check{p}(a,v_{j})=\hat{p}(a,v_{j})+\mathrm{Laplace}(0,\nicefrac{{2}}{{n\varepsilon}})$

6:$\triangleright$ Laplace mechanism to get private joint distribution

7:for $a\in\mathcal{A}$ do

8: $\tilde{w}_{a}\leftarrow\max(\sum_{j=1}^{k}\check{p}(a,v_{j}),0)$
$\triangleright$ private group marginal distribution

9: Define
$\widecheck{F}_{a}(v_{j})=\nicefrac{{1}}{{\tilde{w}_{a}}}\sum_{\ell=1}^{j}\check{p}(a,v_{\ell})$
$\triangleright$ scaled partial sums

10: Define
$\widetilde{F}_{a}(v_{j})=\begin{cases}\operatorname{\mathrm{proj}}_{[0,1]}(\nicefrac{{1}}{{2}}(\widecheck{F}_{a}(v_{l_{j}})+\widecheck{F}_{a}(v_{r_{j}})))&\text{if
}j<k\\\ 1&\text{else}\end{cases}$

11: where $(l_{j},r_{j})=\operatorname*{arg\,max}_{l\leq j\leq
r}(\widecheck{F}_{a}(v_{l})-\widecheck{F}_{a}(v_{r}))$

12:$\triangleright$ $L^{\infty}$ isotonic regression and clipping to get
private CDF

13: Define
$\tilde{p}_{a}(v_{j})=\widetilde{F}_{a}(v_{j})-\widetilde{F}_{a}(v_{j-1})$
$\triangleright$ private group conditional PMF

14:$(\\{\pi_{a}\\}_{a\in\mathcal{A}},\tilde{q},\\{\tilde{q}_{a}\\}_{a\in\mathcal{A}})\leftarrow\hyperlink{eq:lp}{\mathrm{LP}}(\\{\tilde{p}_{a}\\}_{a\in\mathcal{A}},\\{\tilde{w}_{a}\\}_{a\in\mathcal{A}},\alpha)$

15:$\triangleright$ compute barycenter and get optimal transports

16:for $a\in\mathcal{A}$ do

17: Define $g_{a}(v_{j})=\begin{cases}v_{\ell}\textrm{ w.p.
}\nicefrac{{\pi_{a}(v_{j},v_{\ell})}}{{\tilde{p}_{a}(v_{j})}},\;\;\forall\ell\in[k]&\textrm{if
}\tilde{p}_{a}(v_{j})>0\\\ v_{j}&\textrm{else}\end{cases}$ $\triangleright$
post-processing mappings

18:return $(x,a)\mapsto g_{a}\circ h\circ f(x,a)$ $\triangleright$ privately
post-processed fair regressor

To make the fair post-processing algorithm in Section 3.1 private with respect
to $S$, it suffices to perform step 1 of estimating the output distributions
privately. This is because the subsequent steps 2 and 3 of computing the
barycenter (including the target distributions) and the optimal transports
only depend on the estimated distributions, so privacy is preserved by the
post-processing immunity of DP.

To estimate the distributions, one could construct a family of distributions
(a.k.a. hypotheses) and (privately) choose the most likely one (Bun et al.,
2019; Aden-Ali et al., 2021), or use non-parametric estimators. For
generality, we adopt the latter approach and use (private) histogram density
estimator (Diakonikolas et al., 2015; Xu et al., 2012).

Altogether, our fair and private post-processing algorithm is detailed in
Algorithm 1 and illustrated in Fig. 1. It takes as inputs the regressor $f$
being post-processed, the samples $S$, the fairness tolerance $\alpha$, and
the privacy budget $\varepsilon$. For performing HDE, it also requires
specifying an interval111This is necessary for pure $(\varepsilon,0)$-DP, due
to a lower bound by Hardt and Talwar (2010) using a packing argument. (using
prior/domain knowledge) that contains the image of the regressor
$[s,t]\supseteq f[\operatorname{supp}(\mu_{X,A})]$, and the number of bins
$k$. We describe the algorithm in details below:

#### Step 1 (Estimate Output Distributions).

On line 4, we compute the empirical joint distribution of $A$ and $h\circ
f(X,A)$, the discretized regressor output (the support is
$v\coloneqq(\\{\nicefrac{{(j-1/2)(t-s)}}{{k}}\\}_{j\in[k]})$). Then, we make
this statistics private via the Laplace mechanism on line 6, noting that the
$L^{1}$-sensitivity to $\hat{p}$ is at most $\nicefrac{{2}}{{n}}$ (Remark
B.1).222The Laplace mechanism could be replaced by, e.g., the Gaussian
mechanism, to relax the pure $(\varepsilon,0)$-DP guarantee to approximate
$(\varepsilon,\delta)$-DP.

With the private joint distribution, we get a private estimate of the group
marginal distribution $\tilde{w}_{a}$’s (clipping negative values to zero) on
line 8, and the private group conditional discretized output distribution
$\tilde{p}_{a}$’s (with re-normalization) on lines 9–13. The re-normalization
on $\tilde{p}_{a}$ (could also be applied to $\tilde{w}_{a}$), required for
defining the optimal transport problem in the subsequent step, is done by
performing isotonic regression on the partial sums (so that its values are
non-decreasing) with clipping to get a valid CDF.

We analyze the accuracy of the private estimates:

######  Theorem 3.2.

Let $p_{a}(v_{j})=\operatorname{\mathbb{P}}(h\circ f(X,A)=v_{j}\mid A=a)$ and
$w_{a}=\operatorname{\mathbb{P}}(A=a)$ for all $a\in\mathcal{A}$, $j\in[k]$,
and let $\tilde{p}_{a}$, $\tilde{w}_{a}$ denote their privately estimated
counterparts in Algorithm 1. Then for all
$n\geq\Omega(\max_{a}\nicefrac{{1}}{{w_{a}}}\ln\nicefrac{{1}}{{\beta}})$, with
probability at least $1-\beta$, for all $a\in\mathcal{A}$,

$|w_{a}-\tilde{w}_{a}|\leq
O\left\lparen\frac{\sqrt{k}}{n\varepsilon}\ln\frac{k|\mathcal{A}|}{\beta}\right\rparen,$
(10)

and

$\displaystyle\|p_{a}-\tilde{p}_{a}\|_{1}$ $\displaystyle\leq
O\left\lparen\sqrt{\frac{k}{nw_{a}}\ln\frac{k|\mathcal{A}|}{\beta}}+\frac{k}{nw_{a}\varepsilon}\ln\frac{k|\mathcal{A}|}{\beta}\right\rparen,$
(11) $\displaystyle\|p_{a}-\tilde{p}_{a}\|_{\infty}$ $\displaystyle\leq
O\left\lparen\sqrt{\frac{1}{nw_{a}}\ln\frac{|\mathcal{A}|}{\beta}}+\frac{\sqrt{k}}{nw_{a}\varepsilon}\ln\frac{k|\mathcal{A}|}{\beta}\right\rparen,$
(12) $\displaystyle D_{\textnormal{KS}}(p_{a},\tilde{p}_{a})$
$\displaystyle\leq
O\left\lparen\sqrt{\frac{k}{nw_{a}}\ln\frac{k|\mathcal{A}|}{\beta}}+\frac{\sqrt{k}}{nw_{a}\varepsilon}\ln\frac{k|\mathcal{A}|}{\beta}\right\rparen.$
(13)

The private estimation of PMFs with the Laplace mechanism has been analyzed in
prior work (Diakonikolas et al., 2015; Vadhan, 2017), but our algorithm
performs an extra re-normalization (lines 9–13) after adding Laplace noise to
ensure that the PMF returned is valid. This makes the analysis of Theorem 3.2
more involved, because the noise added to each bin can interact during re-
normalization.

The rate of
$\widetilde{O}(\sqrt{\nicefrac{{k}}{{n}}}+\nicefrac{{k}}{{n\varepsilon}})$ for
TV distance is consistent with existing results (Diakonikolas et al., 2015).
For KS distance, the rate is improved by a $\sqrt{k}$ factor, which is not
surprising as KS is a weaker metric than TV. We note that our analysis in
attaining this improvement is made easier with the $L^{\infty}$ isotonic
regression CDF re-normalization scheme, because KS distance is also defined
via the CDF.

#### Steps 2 and 3 (Compute Barycenter and Optimal Transports).

With the output distributions $\tilde{p}_{a}$ estimated privately, we now
compute their barycenter and the optimal transports to obtain the fair post-
processing mappings $g_{a}$, i.e., solving
$\hyperlink{eq:p}{\mathrm{P}}(\\{\tilde{p}_{a}\\}_{a\in\mathcal{A}},\\{\tilde{w}_{a}\\}_{a\in\mathcal{A}},\alpha)$.
Since the $\tilde{p}_{a}$’s are distributions supported on $v$, by restricting
the support of the barycenter to $v$,333This approximation reduces the size of
the barycenter problem to polynomial, at $O(\nicefrac{{t-s}}{{k}})$ error, the
same as that from discretizing the outputs. the barycenter and the optimal
transports can be computed by solving a linear program with
$O(k^{2}|\mathcal{A}|)$ variables and constraints (cf. P and Eq. 8):

$\displaystyle\quad\hypertarget{eq:lp}{\mathrm{LP}}(\\{p_{a}\\}_{a\in\mathcal{A}},\\{w_{a}\\}_{a\in\mathcal{A}},\alpha):$
$\displaystyle\\!\operatorname*{arg\,min}_{\begin{subarray}{c}\\{\pi_{a}\\}_{a\in\mathcal{A}}\geq
0\\\ q,\\{q_{a}\\}_{a\in\mathcal{A}}\geq 0\end{subarray}}\;\;$
$\displaystyle\sum_{\mathclap{a\in\mathcal{A}}}\;\,w_{a}\sum_{j,\ell\in[k]}(v_{j}-v_{\ell})^{2}\,\pi_{a}(v_{j},v_{\ell})$
$\displaystyle\mathrm{s.t.}$
$\displaystyle\sum_{\mathclap{\ell\in[k]}}\;\pi_{a}(v_{j},v_{\ell})=p_{a}(v_{j}),$
$\displaystyle\forall a\in\mathcal{A},\,j\in[k],$
$\displaystyle\sum_{\mathclap{j\in[k]}}\;\pi_{a}(v_{j},v_{\ell})=q_{a}(v_{\ell}),$
$\displaystyle\forall a\in\mathcal{A},\,\ell\in[k],$
$\displaystyle\left|\sum_{j\leq\ell}\left\lparen
q_{a}(v_{j})-q(v_{j})\right\rparen\right|\leq\frac{\alpha}{2},$
$\displaystyle\forall a\in\mathcal{A},\,\ell\in[k].$

The constraints enforce that the $\pi_{a}$’s are couplings, and the target
output distributions $\tilde{q}_{a}$’s are valid PMFs satisfying the fairness
constraint of
$\max_{a,a^{\prime}}D_{\textnormal{KS}}(\tilde{q}_{a},\tilde{q}_{a^{\prime}})\leq\alpha$.

#### Post-Processed Fair Regressor.

On 16, 17 and 18, the (randomized) optimal transports $g_{a}$ from
$\tilde{p}_{a}$ to $\tilde{q}_{a}$ are extracted by reading off from the
optimal couplings $\pi_{a}$ (represented by $k\times k$ matrices), and are
used to construct the fair regressor, $\bar{f}(x,a)=g_{a}\circ h\circ f(x,a)$.

Given an input $(x,a)$, the fair regressor $\bar{f}$ obtained from Algorithm 1
calls $f$ to make a prediction $y=f(x,a)$, discretizes it to get
$\tilde{y}=h(y)$, and then uses the optimal transport $g_{a}$ of the
respective group to post-process and return a fair prediction,
$\bar{y}=g_{a}(\tilde{y})$.

###  3.4 Statistical Analysis

Algorithm 1 is $\varepsilon$-DP by the post-processing theorem of DP (Dwork
and Roth, 2014, Proposition 2.1), because its output depends on $S$ only via
the private statistics $\tilde{p}$ on line 6 that is $\varepsilon$-DP.2

We analyze the suboptimality (or fair excess risk) of the post-processed fair
regressor and provide fairness guarantee:

######  Theorem 3.3.

Let regressor $f$ be given along with samples
$S=\\{(x_{i},a_{i})\\}_{i\in[n]}$ of $\mu_{X,A}$. Denote $L=t-s$, assume
$L\leq 1$, and $Y,f(X,A)\in[s,t]$ almost surely. Let $\bar{f}$ denote the fair
regressor returned from Algorithm 1 on $(f,S,[s,t],k,\alpha,\varepsilon)$.
Then for all
$n\geq\Omega(\max_{a}\nicefrac{{1}}{{w_{a}}}\ln\nicefrac{{|\mathcal{A}|}}{{\beta}})$,
with probability at least $1-\beta$,

$\displaystyle R(\bar{f})-R(\bar{f}^{*})\leq
O\left\lparen\sqrt{\frac{k|\mathcal{A}|}{n}\ln\frac{k|\mathcal{A}|}{\beta}}+\frac{k|\mathcal{A}|}{n\varepsilon}\ln\frac{k|\mathcal{A}|}{\beta}\right\rparen+\frac{8}{k}+5\operatorname{\mathbb{E}}\left[\left|f(X,A)-f^{*}(X,A)\right|\right]$
(14)

where
$\bar{f}^{*}=\operatorname*{arg\,min}_{f^{\prime}:\Delta_{\textnormal{SP}}(f^{\prime})\leq\alpha}R(f^{\prime})$
is the optimal fair regressor, $f^{*}$ is the (unconstrained) Bayes regressor,
and

$\displaystyle\Delta_{\textnormal{SP}}(\bar{f})\leq\alpha+\max_{a\in\mathcal{A}}O\left\lparen\frac{\sqrt{k}}{nw_{a}\varepsilon}\ln\frac{k|\mathcal{A}|}{\beta}+\sqrt{\frac{k}{nw_{a}}\ln\frac{k|\mathcal{A}|}{\beta}}\right\rparen.$
(15)

The risk bound reflects four potential sources of error: the first term is
finite sample estimation error, the second term is due to the noise added for
$\varepsilon$-DP, the third term is the error introduced by discretization,
and the last term is the $L^{1}$ excess risk of the regressor $f$ being post-
processed (carrying over the error of the pre-trained regressor).

The first three terms of the risk bound (and last two in the fairness bound)
are attributed to the accuracy of the private distribution estimate using HDE
(cf. Theorem 3.2). In particular, a trade-off between the statistical bias and
variance is incurred by the choice of $k$, the number of bins:

$\widetilde{O}\Bigg{(}\underbrace{\sqrt{\frac{k}{n}}+\frac{k}{n\varepsilon}}_{\textrm{variance}}+\underbrace{\frac{1}{k}}_{\textrm{bias}}\Bigg{)}.$
(16)

Using too few bins leads to a large discretization error (statistical bias),
whereas using too many suffers from large variance due to data sampling and
the noise added for privacy.

The cost of privacy is dominated by the estimation error as long as
$n\gtrsim\max_{a}\nicefrac{{k}}{{w_{a}\varepsilon^{2}}}\geq\nicefrac{{k|\mathcal{A}|}}{{\varepsilon^{2}}}$.
In which case, the choice of $k=\widetilde{\Theta}(n^{1/3})$ is optimal for
MSE, which is consistent with classical non-parametric estimation results of
HDE (Rudemo, 1982).

The fairness bound, on the other hand, only contains variance terms but not
the statistical bias, therefore using fewer bins is always more favorable for
fairness at the expense of MSE (e.g., in the extreme case of $k=1$, the post-
processor outputs a constant value, which is exactly fair). This suggests that
when $n$ is small, $k$ can be decreased to reduce variance for higher levels
of fairness.

The optimal choice of $k$ (in combination with $\alpha$) is data-dependent,
and is typically tuned on a validation split, however; extra care should be
taken as this practice could, in principle, violate differential privacy. In
our experiments, we sweep $\alpha$ and $k$ to empirically explore the trade-
offs between error, privacy and fairness attainable with our Algorithm 1. This
is common practice in differential privacy research (Mohapatra et al., 2022).
Regarding the selection of hyperparameters while preserving privacy, we refer
readers to Liu and Talwar (2019); Papernot and Steinke (2022).

##  4 Experiments

In this section, we evaluate the private and fair post-processing algorithm
described in Algorithm 1.

We do not compare to other algorithms because we are not aware of any existing
private algorithms for learning fair regressors. Although it may be possible
to adopt some existing algorithms to this setting, e.g., using DP-SGD as in
(Tran et al., 2021), making them practical and competitive requires care, and
is hence left to future work. Our post-processing algorithm is based on
(Chzhen et al., 2020); their paper is referred to for empirical comparisons to
in-processing algorithms under the non-private setting ($\varepsilon=\infty$).

#### Setup.

Since the excess risk can be decomposed according to the pre-training and
post-processing stages (Theorem 3.3, where
$\operatorname{\mathbb{E}}[|f-f^{*}|]$ is carried over from the suboptimality
of the regressor $f$ trained in the pre-training stage), we will simplify our
experiment setup to isolate and focus on the performance and trade-offs
induced by post-processing alone. This means we will access the ground-truth
responses and directly apply Algorithm 1 (i.e., $X=Y$ and $f=\mathrm{Id}$,
whereby $\operatorname{\mathbb{E}}[|f-f^{*}|]=0$).444Code is available at
https://github.com/rxian/fair-regression.

#### Datasets.

The datasets are randomly split 70-30 for training (i.e., post-processing) and
testing.

Communities & Crime (Redmond and Baveja, 2002). It contains the socioeconomic
and crime data of communities in US, and the task is to predict the rate of
violent crimes per 100k population ($Y\in[0,1]$). The sensitive attribute is
an indicator for whether the community has a significant presence of a
minority population ($|\mathcal{A}|=2$). The total size of the dataset is
1,994, and the number of training examples for the smallest group is 679
($\approx nw_{a}$).

Law School (Wightman, 1998). This dataset contains the academic performance of
law school applicants, and the task is to predict the student’s undergraduate
GPA ($Y\in[1,4]$). The sensitive attribute is race ($|\mathcal{A}|=4$), and
the dataset has size 21,983. The smallest group has 628 training examples.

###  4.1 Results

Figure 2: Error-privacy-fairness trade-offs achieved by Algorithm 1 by
sweeping $\alpha$ under the indicated number of bins $k$, with different
privacy budgets $\varepsilon$. Fairness violation is measured in KS distance
as defined in Definition 2.2 ($\Delta_{\textnormal{SP}}$). Average of 50
random seeds (also for Figs. 4 and 4).

In Fig. 2, we show the MSE and fairness trade-offs (in KS distance;
$\Delta_{\textnormal{SP}}$, Definition 2.2) attained with Algorithm 1 under
various settings of $\alpha$. The main observations are:

  1. 1.

The cost of discretization (indicated by the horizontal distance from $0$ to
the top-left starting points of the curves) can be expected to be
insignificant compared to fairness, unless the model is already very fair
without post-processing.

  2. 2.

Although the amount of data available for post-processing is small by modern
standards, the results are very insensitive to the privacy budget until the
highest levels of DP are demanded or very large $k$ is used.

This is because according to Theorem 3.3, the error attributed to DP noise is
dominated by estimation error when
$n\gtrsim\max_{a}\nicefrac{{k}}{{w_{a}\varepsilon^{2}}}$. Note that in our
experiments, we have $n\gg\nicefrac{{k|\mathcal{A}|}}{{\varepsilon^{2}}}$ on
both datasets except for $\varepsilon=0.1$, and $\varepsilon=0.5$ when
$k=180$. Using more bins increases the cost of privacy due to variance, as we
will show in Fig. 4.

  3. 3.

The right end of each line is obtained with setting $\alpha=0$. Relaxing it to
larger values could give better trade-offs, especially when $n,\varepsilon$
are small, because in these cases the estimated distributions can be
inaccurate due to estimation error and the noise added, so aiming for exact SP
may fit to data artifacts or the noise rather than the true signal, causing
MSE to increase without actual improvements to fairness.

Figure 3: Error-fairness trade-offs achieved by Algorithm 1 on the Law School
dataset by sweeping $\alpha$ and $k$ for $\varepsilon=0.1$. The black line is
the lower envelope, and ends on the right at $(0.6772,0)$ (outside the cropped
figure).

Figure 4: Error-privacy-fairness trade-offs achieved by Algorithm 1 on the Law
School dataset by sweeping $\alpha$ and $k$ and taking the lower envelope. The
line for $\varepsilon=0.1$ is the black line in Fig. 4. All lines meet and end
on the right at $(0.6772,0)$.

#### Trade-off Between Statistical Bias and Variance.

Recall from the analysis and discussion in Section 3.4 that the MSE of
Algorithm 1 exhibits a trade-off between the statistical bias and variance
from the choice of $k$: using more bins lowers discretization error but
suffers from larger estimation error and more noise added for DP, and vice
versa. On the other hand, the fairness only depends on the variance. Hence,
one can decrease $k$ to achieve higher levels of fairness at the expense of
MSE.

In Fig. 4, we plot the trade-offs on the Law School dataset for
$\varepsilon=0.1$ under different settings of $k$. On the right extreme, exact
SP ($\Delta_{\textnormal{SP}}=0$) is achieved by setting $k=1$, but with a
high $0.6772$ MSE. As expected:

  1. 1.

Smaller settings of $k$ lead to smaller $\Delta_{\textnormal{SP}}$, but it
comes with higher discretization error, as reflected in the rightward-shifting
starting points (i.e., results with $\alpha=\infty$, i.e., not post-processed
for fairness).

  2. 2.

Using more bins may result in worse trade-offs compared to less bins due to
large variance. Note that the trade-offs with $k=60$ bins are almost
completely dominated by those with $k=36$ bins.

  3. 3.

The general trend is that, to achieve the best trade-offs (i.e., the lower
envelope), use smaller $(\alpha,k)$ when aiming for higher levels of fairness,
and larger $(\alpha,k)$ for smaller MSE (but less fairness).

#### Error-Privacy-Fairness Trade-Off.

The black line in Fig. 4 shows the optimal error-fairness trade-offs
attainable with Algorithm 1 for $\varepsilon=0.1$ from sweeping $\alpha$ and
$k$ and taking the lower envelope (segments of the line not reached by any $k$
can be achieved by combining two regressors via randomization, although
obtaining them via post-processing requires double the privacy budget).

We repeat this experiment for all settings of $\varepsilon$ on the Law School
dataset, and plot their lower envelopes in Fig. 4. This illustrates the Pareto
front of the error-privacy-fairness trade-offs achieved by Algorithm 1.
Demanding stricter privacy degrades the trade-offs between error and fairness.

Lastly, we remark that while Figs. 2, 4 and 4 illustrate the trade-offs that
can be possibly attained with our post-processing algorithm from varying the
hyperparameters $\alpha$ and $k$, selecting the desired trade-off requires
tuning them (privately) on a validation set. Readers are referred to (Liu and
Talwar, 2019; Papernot and Steinke, 2022) on the topic of differentially
private hyperparameter tuning.

##  5 Conclusion and Future Work

In this paper, we described and analyzed a private post-processing algorithm
for learning attribute-aware fair regressors, in which privacy is achieved by
performing histogram density estimates of the distributions privately, and
fairness by computing the optimal transports to their Wasserstein barycenter.
We evaluated the error-privacy-fairness trade-offs attained by our algorithm
on two datasets.

Although we only studied the attribute-aware setting, that is, we have
explicit access to $A$ during training and when making predictions, our post-
processing algorithm could be extended to the attribute-blind setting, where
$A$ is only available in the training data. This requires training an extra
predictor for the sensitive attribute,
$\widehat{P}_{A}=\widehat{\operatorname{\mathbb{P}}}(A\mid
X)\in\Delta^{|\mathcal{A}|-1}$, to estimate the joint distribution of
$(\widehat{Y},\widehat{P}_{A})$ (vs. the joint of $(\widehat{Y},A)$ estimated
in Algorithm 1 for the attribute-aware setting), and modifying P (and LP) to
use predicted group membership $\widehat{P}_{A}$ rather than the true $A$.
This has a higher sample complexity, and the fairness of the post-processed
regressor will additionally depend on the accuracy of $\widehat{P}_{A}$. We
leave the implementation and analysis of this extension to future work.

## Acknowledgements

GK is supported by a Canada CIFAR AI Grant, an NSERC Discovery Grant, and an
unrestricted gift from Google. HZ is partially supported by a research grant
from the Amazon-Illinois Center on AI for Interactive Conversational
Experiences (AICE) and a Google Research Scholar Award.

## Broader Impacts

This paper continues the study of privacy and fairness in machine learning,
and fills the gap in prior work on private and fair regression. Since the
setting is well-established, and we have theoretically analyzed the risk of
our algorithm, we do not find outstanding societal consequences for
discussion.

## References

  * Abadi et al. (2016) Martín Abadi, Andy Chu, Ian Goodfellow, H. Brendan McMahan, Ilya Mironov, Kunal Talwar, and Li Zhang.  Deep Learning with Differential Privacy.  In _Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security_ , 2016.
  * Aden-Ali et al. (2021) Ishaq Aden-Ali, Hassan Ashtiani, and Gautam Kamath.  On the Sample Complexity of Privately Learning Unbounded High-Dimensional Gaussians.  In _Proceedings of the 32nd International Conference on Algorithmic Learning Theory_ , 2021.
  * Agarwal et al. (2018) Alekh Agarwal, Alina Beygelzimer, Miroslav Dudík, John Langford, and Hanna Wallach.  A Reductions Approach to Fair Classification.  In _Proceedings of the 35th International Conference on Machine Learning_ , 2018.
  * Agarwal et al. (2019) Alekh Agarwal, Miroslav Dudík, and Zhiwei Steven Wu.  Fair Regression: Quantitative Definitions and Reduction-Based Algorithms.  In _Proceedings of the 36th International Conference on Machine Learning_ , 2019.
  * Agarwal (2020) Sushant Agarwal.  Trade-Offs between Fairness and Privacy in Machine Learning.  In _IJCAI 2020 Workshop on AI for Social Good_ , 2020\.
  * Alabi et al. (2022) Daniel Alabi, Audra McMillan, Jayshree Sarathy, Adam Smith, and Salil Vadhan.  Differentially Private Simple Linear Regression.  _Proceedings on Privacy Enhancing Technologies_ , 2022.
  * Altschuler and Boix-Adserà (2021) Jason M. Altschuler and Enric Boix-Adserà.  Wasserstein Barycenters can be Computed in Polynomial Time in Fixed Dimension.  _Journal of Machine Learning Research_ , 22(44), 2021.
  * Anderes et al. (2016) Ethan Anderes, Steffen Borgwardt, and Jacob Miller.  Discrete Wasserstein Barycenters: Optimal Transport for Discrete Data.  _Mathematical Methods of Operations Research_ , 84(2), 2016\.
  * Bagdasaryan et al. (2019) Eugene Bagdasaryan, Omid Poursaeed, and Vitaly Shmatikov.  Differential Privacy Has Disparate Impact on Model Accuracy.  In _Advances in Neural Information Processing Systems_ , volume 32, 2019.
  * Barocas and Selbst (2016) Solon Barocas and Andrew D. Selbst.  Big Data’s Disparate Impact.  _California Law Review_ , 104(3), 2016.
  * Barocas et al. (2023) Solon Barocas, Moritz Hardt, and Arvind Narayanan.  _Fairness and Machine Learning: Limitations and Opportunities_.  The MIT Press, 2023.
  * Bassily et al. (2014) Raef Bassily, Adam Smith, and Abhradeep Thakurta.  Private Empirical Risk Minimization: Efficient Algorithms and Tight Error Bounds.  In _IEEE 55th Annual Symposium on Foundations of Computer Science_ , 2014.
  * Berk et al. (2021) Richard Berk, Hoda Heidari, Shahin Jabbari, Michael Kearns, and Aaron Roth.  Fairness in Criminal Justice Risk Assessments: The State of the Art.  _Sociological Methods & Research_, 50(1), 2021.
  * Bolukbasi et al. (2016) Tolga Bolukbasi, Kai-Wei Chang, James Zou, Venkatesh Saligrama, and Adam Kalai.  Man is to Computer Programmer as Woman is to Homemaker? Debiasing Word Embeddings.  In _Advances in Neural Information Processing Systems_ , volume 29, 2016.
  * Bun et al. (2019) Mark Bun, Gautam Kamath, Thomas Steinke, and Steven Zhiwei Wu.  Private Hypothesis Selection.  In _Advances in Neural Information Processing Systems_ , volume 32, 2019.
  * Buolamwini and Gebru (2018) Joy Buolamwini and Timnit Gebru.  Gender Shades: Intersectional Accuracy Disparities in Commercial Gender Classification.  In _Proceedings of the 2018 Conference on Fairness, Accountability, and Transparency_ , 2018.
  * Calders et al. (2009) Toon Calders, Faisal Kamiran, and Mykola Pechenizkiy.  Building Classifiers with Independency Constraints.  In _2009 IEEE International Conference on Data Mining Workshops_ , 2009.
  * Calmon et al. (2017) Flavio P. Calmon, Dennis Wei, Bhanukiran Vinzamuri, Karthikeyan Natesan Ramamurthy, and Kush R. Varshney.  Optimized Pre-Processing for Discrimination Prevention.  In _Advances in Neural Information Processing Systems_ , volume 30, 2017.
  * Chaudhuri et al. (2011) Kamalika Chaudhuri, Claire Monteleoni, and Anand D. Sarwate.  Differentially Private Empirical Risk Minimization.  _Journal of Machine Learning Research_ , 12(29), 2011.
  * Chi et al. (2021) Jianfeng Chi, Yuan Tian, Geoffrey J. Gordon, and Han Zhao.  Understanding and Mitigating Accuracy Disparity in Regression.  In _Proceedings of the 38th International Conference on Machine Learning_ , 2021.
  * Chizat et al. (2020) Lénaïc Chizat, Pierre Roussillon, Flavien Léger, François-Xavier Vialard, and Gabriel Peyré.  Faster Wasserstein Distance Estimation with the Sinkhorn Divergence.  In _Advances in Neural Information Processing Systems_ , volume 33, 2020.
  * Chouldechova (2017) Alexandra Chouldechova.  Fair Prediction with Disparate Impact: A Study of Bias in Recidivism Prediction Instruments.  _Big Data_ , 5(2), 2017.
  * Chzhen et al. (2020) Evgenii Chzhen, Christophe Denis, Mohamed Hebiri, Luca Oneto, and Massimiliano Pontil.  Fair Regression with Wasserstein Barycenters.  In _Advances in Neural Information Processing Systems_ , volume 33, 2020.
  * Covington et al. (2021) Christian Covington, Xi He, James Honaker, and Gautam Kamath.  Unbiased Statistical Estimation and Valid Confidence Intervals Under Differential Privacy, 2021.  _arxiv:2110.14465 [stat.ME]_.
  * Cummings et al. (2019) Rachel Cummings, Varun Gupta, Dhamma Kimpara, and Jamie Morgenstern.  On the Compatibility of Privacy and Fairness.  In _Adjunct Publication of the 27th Conference on User Modeling, Adaptation and Personalization_ , 2019.
  * Cuturi and Doucet (2014) Marco Cuturi and Arnaud Doucet.  Fast Computation of Wasserstein Barycenters.  In _Proceedings of the 31st International Conference on Machine Learning_ , 2014.
  * Diakonikolas et al. (2015) Ilias Diakonikolas, Moritz Hardt, and Ludwig Schmidt.  Differentially Private Learning of Structured Discrete Distributions.  In _Advances in Neural Information Processing Systems_ , volume 28, 2015.
  * Dwork and Roth (2014) Cynthia Dwork and Aaron Roth.  The Algorithmic Foundations of Differential Privacy.  _Foundations and Trends® in Theoretical Computer Science_ , 9(3–4), 2014.
  * Dwork et al. (2006) Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith.  Calibrating Noise to Sensitivity in Private Data Analysis.  In _Theory of Cryptography_ , 2006.
  * Dwork et al. (2012) Cynthia Dwork, Moritz Hardt, Toniann Pitassi, Omer Reingold, and Richard Zemel.  Fairness Through Awareness.  In _Proceedings of the 3rd Innovations in Theoretical Computer Science Conference_ , 2012.
  * Fletcher and Islam (2019) Sam Fletcher and Md. Zahidul Islam.  Decision Tree Classification with Differential Privacy: A Survey.  _ACM Computing Surveys_ , 52(4), 2019.
  * Hardt and Talwar (2010) Moritz Hardt and Kunal Talwar.  On the Geometry of Differential Privacy.  In _Proceedings of the Forty-Second ACM Symposium on Theory of Computing_ , 2010.
  * Hardt et al. (2016) Moritz Hardt, Eric Price, and Nathan Srebro.  Equality of Opportunity in Supervised Learning.  In _Advances in Neural Information Processing Systems_ , volume 29, 2016.
  * Hébert-Johnson et al. (2018) Úrsula Hébert-Johnson, Michael P. Kim, Omer Reingold, and Guy N. Rothblum.  Multicalibration: Calibration for the (Computationally-Identifiable) Masses.  In _Proceedings of the 35th International Conference on Machine Learning_ , 2018.
  * Jagielski et al. (2019) Matthew Jagielski, Michael Kearns, Jieming Mao, Alina Oprea, Aaron Roth, Saeed Sharifi-Malvajerdi, and Jonathan Ullman.  Differentially Private Fair Learning.  In _Proceedings of the 36th International Conference on Machine Learning_ , 2019.
  * Kamishima et al. (2012) Toshihiro Kamishima, Shotaro Akaho, Hideki Asoh, and Jun Sakuma.  Fairness-Aware Classifier with Prejudice Remover Regularizer.  In _Machine Learning and Knowledge Discovery in Databases_ , 2012.
  * Kifer et al. (2012) Daniel Kifer, Adam Smith, and Abhradeep Thakurta.  Private Convex Empirical Risk Minimization and High-dimensional Regression.  In _Proceedings of the 25th Annual Conference on Learning Theory_ , 2012.
  * Le Gouic et al. (2020) Thibaut Le Gouic, Jean-Michel Loubes, and Philippe Rigollet.  Projection to Fairness in Statistical Learning, 2020.  _arxiv:2005.11720 [cs.LG]_.
  * Li and Tkocz (2023) Jiawei Li and Tomasz Tkocz.  Tail Bounds for Sums of Independent Two-Sided Exponential Random Variables.  In _High Dimensional Probability IX_ , 2023.
  * Liu and Talwar (2019) Jingcheng Liu and Kunal Talwar.  Private Selection from Private Candidates.  In _Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing_ , 2019.
  * Mironov (2017) Ilya Mironov.  Rényi Differential Privacy.  In _IEEE 30th Computer Security Foundations Symposium_ , 2017\.
  * Mohapatra et al. (2022) Shubhankar Mohapatra, Sajin Sasy, Xi He, Gautam Kamath, and Om Thakkar.  The Role of Adaptive Optimizers for Honest Private Hyperparameter Selection.  _Proceedings of the AAAI Conference on Artificial Intelligence_ , 36(7), 2022.
  * Mozannar et al. (2020) Hussein Mozannar, Mesrob I. Ohannessian, and Nathan Srebro.  Fair Learning with Private Demographic Data.  In _Proceedings of the 37th International Conference on Machine Learning_ , 2020.
  * Papernot and Steinke (2022) Nicolas Papernot and Thomas Steinke.  Hyperparameter Tuning with Renyi Differential Privacy.  In _The Tenth International Conference on Learning Representations_ , 2022.
  * Papernot et al. (2017) Nicolas Papernot, Martín Abadi, Úlfar Erlingsson, Ian Goodfellow, and Kunal Talwar.  Semi-supervised Knowledge Transfer for Deep Learning from Private Training Data.  In _The Fifth International Conference on Learning Representations_ , 2017.
  * Pleiss et al. (2017) Geoff Pleiss, Manish Raghavan, Felix Wu, Jon Kleinberg, and Kilian Q. Weinberger.  On Fairness and Calibration.  In _Advances in Neural Information Processing Systems_ , volume 30, 2017.
  * Redmond and Baveja (2002) Michael Redmond and Alok Baveja.  A data-driven software tool for enabling cooperative information sharing among police departments.  _European Journal of Operational Research_ , 141(3), 2002\.
  * Rudemo (1982) Mats Rudemo.  Empirical Choice of Histograms and Kernel Density Estimators.  _Scandinavian Journal of Statistics_ , 9(2), 1982.
  * Song et al. (2013) Shuang Song, Kamalika Chaudhuri, and Anand D. Sarwate.  Stochastic gradient descent with differentially private updates.  In _IEEE Global Conference on Signal and Information Processing_ , 2013.
  * Staib et al. (2017) Matthew Staib, Sebastian Claici, Justin Solomon, and Stefanie Jegelka.  Parallel Streaming Wasserstein Barycenters.  In _Advances in Neural Information Processing Systems_ , volume 30, 2017.
  * Stout (2017) Quentin F. Stout.  $L_{\infty}$ Isotonic Regression for Linear, Multidimensional, and Tree Orders, 2017.  _arxiv:1507.02226 [cs.DS]_.
  * Tran et al. (2021) Cuong Tran, Ferdinando Fioretto, and Pascal Van Hentenryck.  Differentially Private and Fair Deep Learning: A Lagrangian Dual Approach.  _Proceedings of the AAAI Conference on Artificial Intelligence_ , 35(11), 2021.
  * Vadhan (2017) Salil Vadhan.  The Complexity of Differential Privacy.  In _Tutorials on the Foundations of Cryptography: Dedicated to Oded Goldreich_. Springer International Publishing, 2017\.
  * Wang (2018) Yu-Xiang Wang.  Revisiting differentially private linear regression: Optimal and adaptive prediction & estimation in unbounded domain.  In _Proceedings of the 34th Uncertainty in Artificial Intelligence Conference_ , 2018.
  * Weissman et al. (2003) Tsachy Weissman, Erik Ordentlich, Gadiel Seroussi, Sergio Verdu, and Marcelo J. Weinberger.  Inequalities for the $L_{1}$ Deviation of the Empirical Distribution.  Technical Report HPL-2003-97R1, Hewlett-Packard Laboratories, 2003\.
  * Wightman (1998) Linda F. Wightman.  _LSAC National Longitudinal Bar Passage Study_.  Law School Admission Council, 1998.
  * Xian et al. (2023) Ruicheng Xian, Lang Yin, and Han Zhao.  Fair and Optimal Classification via Post-Processing.  In _Proceedings of the 40th International Conference on Machine Learning_ , 2023.
  * Xu et al. (2019) Depeng Xu, Shuhan Yuan, and Xintao Wu.  Achieving Differential Privacy and Fairness in Logistic Regression.  In _Companion Proceedings of the 2019 World Wide Web Conference_ , 2019.
  * Xu et al. (2012) Jia Xu, Zhenjie Zhang, Xiaokui Xiao, Yin Yang, and Ge Yu.  Differentially Private Histogram Publication.  In _IEEE 28th International Conference on Data Engineering_ , 2012.
  * Zemel et al. (2013) Richard Zemel, Yu Ledell Wu, Kevin Swersky, Toni Pitassi, and Cynthia Dwork.  Learning Fair Representations.  In _Proceedings of the 30th International Conference on Machine Learning_ , 2013.
  * Zhao and Gordon (2022) Han Zhao and Geoffrey J. Gordon.  Inherent Tradeoffs in Learning Fair Representations.  _Journal of Machine Learning Research_ , 23(57), 2022.

##  Appendix A Excess Risk of the Optimal Fair Regressor

This section proves Theorem 3.1, that the excess risk of the optimal
attribute-aware fair regressor can be expressed as the sum of Wasserstein
distances from the output distributions $r^{*}_{a}$ of the Bayes regressor
$f^{*}$ conditioned on each group $a\in\mathcal{A}$ to their barycenter $q$.
We will cover the approximate fairness setting using the same analysis in
(Xian et al., 2023).

The result is a direct consequence of Lemma A.4—but before stating which,
because the fair regressor is randomized, to make the discussions involving
randomized functions rigorous, we provide a formal definition for them with
the Markov kernel.

######  Definition A.1 (Markov Kernel).

A Markov kernel from a measurable space $(\mathcal{X},\mathcal{S})$ to
$(\mathcal{Y},\mathcal{T})$ is a mapping
$\mathcal{K}:\mathcal{X}\times\mathcal{T}\rightarrow[0,1]$, such that
$\mathcal{K}(\cdot,T)$ is $\mathcal{S}$-measurable, $\forall T\in\mathcal{T}$,
and $\mathcal{K}(x,\cdot)$ is a probability measure on
$(\mathcal{Y},\mathcal{T})$, $\forall x\in\mathcal{X}$.

######  Definition A.2 (Randomized Function).

A randomized function
$f:(\mathcal{X},\mathcal{S})\rightarrow(\mathcal{Y},\mathcal{T})$ is
associated with a Markov kernel
$\mathcal{K}:\mathcal{X}\times\mathcal{T}\rightarrow[0,1]$, such that $\forall
x\in\mathcal{X},T\in\mathcal{T}$, $\operatorname{\mathbb{P}}(f(x)\in
T)=\mathcal{K}(x,T)$.

######  Definition A.3 (Push-Forward Distribution).

Let $p$ be a measure on $(\mathcal{X},\mathcal{S})$ and
$f:(\mathcal{X},\mathcal{S})\rightarrow(\mathcal{Y},\mathcal{T})$ a randomized
function with Markov kernel $\mathcal{K}$. The push-forward of $p$ under $f$,
denoted by $f\sharp p$, is a measure on $\mathcal{Y}$ given by $f\sharp
p(T)=\int_{\mathcal{X}}\mathcal{K}(x,T)\mathop{}\\!\mathrm{d}p(x)$, $\forall
T\in\mathcal{T}$.

Now, we state the lemma of which Theorem 3.1 is a direct consequence; it says
that given any (randomized) regressor $f$ with a particular shape $q$, one can
derive a regressor $g\circ f^{*}$ from the Bayes regressor $f^{*}$ that has
the same shape and excess risk ($g$ is a randomized function with Markov
kernel $\mathcal{K}(y,T)=\nicefrac{{\pi(y,T)}}{{\pi(y,\mathbb{R})}}$ where
$\pi$ is given in Eq. 17):

######  Lemma A.4.

Let a regression problem be given by a joint distribution $\mu$ of $(X,Y)$,
denote the Bayes regressor by $f^{*}:\mathcal{X}\rightarrow\mathbb{R}$ and
$r^{*}=f^{*}\sharp\mu_{X}$, and let $q$ be an arbitrary distribution on
$\mathbb{R}$. Then, for any randomized regressor $f$ with Markov kernel
$\mathcal{K}$ satisfying $f\sharp\mu_{X}=q$,

$\pi(y^{*},y)=\int_{{f^{*}}^{-1}(y^{*})}\mathcal{K}(x,y)\mathop{}\\!\mathrm{d}\mu_{X}(x)$
(17)

(where ${f^{*}}^{-1}(y^{*})\coloneqq\\{x\in\mathcal{X}:f^{*}(x)=y^{*}\\}$) is
a coupling $\pi\in\Pi(r^{*},q)$ that satisfies

$\operatorname{\mathit{ER}}(f)=\int(y^{*}-y)^{2}\mathop{}\\!\mathrm{d}\pi(y^{*},y).$
(18)

Conversely, for any $\pi\in\Pi(r^{*},q)$, the randomized regressor $f$ with
Markov kernel

$\mathcal{K}(x,T)=\frac{\pi(f^{*}(x),T)}{\pi(f^{*}(x),\mathbb{R})}$ (19)

satisfies $f\sharp\mu_{X}=q$ and Eq. 18.

###### Proof.

For the first direction, note that

$\displaystyle\operatorname{\mathit{ER}}(f)$
$\displaystyle=\operatorname{\mathbb{E}}[\lparen f^{*}(X)-f(X)\rparen^{2}]$
(20)
$\displaystyle=\int_{\mathbb{R}\times\mathbb{R}}(y^{*}-y)^{2}\operatorname{\mathbb{P}}(f^{*}(X)=y^{*},f(X)=y)\mathop{}\\!\mathrm{d}(y^{*},y)$
(21)
$\displaystyle=\int_{\mathbb{R}\times\mathbb{R}}(y^{*}-y)^{2}\left\lparen\int_{\mathcal{X}}\operatorname{\mathbb{P}}(f^{*}(X)=y^{*},f(X)=y,X=x)\mathop{}\\!\mathrm{d}x\right\rparen\mathop{}\\!\mathrm{d}(y^{*},y)$
(22)
$\displaystyle=\int_{\mathbb{R}\times\mathbb{R}}(y^{*}-y)^{2}\left\lparen\int_{{f^{*}}^{-1}(y^{*})}\operatorname{\mathbb{P}}(f(X)=y,X=x)\mathop{}\\!\mathrm{d}x\right\rparen\mathop{}\\!\mathrm{d}(y^{*},y)$
(23)
$\displaystyle=\int_{\mathbb{R}\times\mathbb{R}}(y^{*}-y)^{2}\left\lparen\int_{{f^{*}}^{-1}(y^{*})}\operatorname{\mathbb{P}}(f(X)=y\mid
X=x)\mathop{}\\!\mathrm{d}\mu_{X}(x)\right\rparen\mathop{}\\!\mathrm{d}(y^{*},y)$
(24)
$\displaystyle=\int_{\mathbb{R}\times\mathbb{R}}(y^{*}-y)^{2}\pi(y^{*},y)\mathop{}\\!\mathrm{d}(y^{*},y)$
(25)

as desired, where line 4 is because
$\operatorname{\mathbb{P}}(f^{*}(X)=y^{*},f(X)=y,X=x)=\operatorname{\mathds{1}}[f^{*}(x)=y^{*}]\operatorname{\mathbb{P}}(f(X)=y,X=x)$
as $f^{*}$ is deterministic. We also verify that the constructed $\pi$ is a
coupling:

$\displaystyle\int_{\mathbb{R}}\pi(y^{*},y)\mathop{}\\!\mathrm{d}y$
$\displaystyle=\int_{\mathbb{R}}\int_{{f^{*}}^{-1}(y^{*})}\mathcal{K}(x,y)\mathop{}\\!\mathrm{d}\mu_{X}(x)\mathop{}\\!\mathrm{d}y$
(26)
$\displaystyle=\int_{{f^{*}}^{-1}(y^{*})}\int_{\mathbb{R}}\mathcal{K}(x,y)\mathop{}\\!\mathrm{d}y\mathop{}\\!\mathrm{d}\mu_{X}(x)$
(27)
$\displaystyle=\int_{{f^{*}}^{-1}(y^{*})}\mathop{}\\!\mathrm{d}\mu_{X}(x)$
(28) $\displaystyle=\operatorname{\mathbb{P}}(f^{*}(X)=y^{*})$ (29)
$\displaystyle=r^{*}(y^{*})$ (30)

by Definitions A.1 and A.3, and

$\displaystyle\int_{\mathbb{R}}\pi(y^{*},y)\mathop{}\\!\mathrm{d}y^{*}$
$\displaystyle=\int_{\mathbb{R}}\int_{{f^{*}}^{-1}(y^{*})}\mathcal{K}(x,y)\mathop{}\\!\mathrm{d}\mu_{X}(x)\mathop{}\\!\mathrm{d}y^{*}$
(31)
$\displaystyle=\int_{\mathcal{X}}\mathcal{K}(x,y)\mathop{}\\!\mathrm{d}\mu_{X}(x)$
(32) $\displaystyle=\int_{\mathcal{X}}\operatorname{\mathbb{P}}(f(X)=y\mid
X=x)\mathop{}\\!\mathrm{d}\mu_{X}(x)$ (33)
$\displaystyle=\operatorname{\mathbb{P}}(f(X)=y)$ (34) $\displaystyle=q(y)$
(35)

by Definition A.2 and the assumption that $f\sharp\mu_{X}=q$.

For the converse direction, it suffices to show that the Markov kernel
constructed for $f$ satisfies the equality in Eq. 17, which would immediately
imply $f\sharp\mu_{X}=q$, and Eq. 18 with the same arguments in Eq. 25. Let
$y,y\in\mathbb{R}$ and $z\in{f^{*}}^{-1}(y^{*})$ be arbitrary, then

$\displaystyle\pi(y^{*},y)$
$\displaystyle=\frac{\pi(y^{*},y)}{\pi(y^{*},\mathbb{R})}\pi(y^{*},\mathbb{R})$
(36)
$\displaystyle=\frac{\pi(f^{*}(z),y)}{\pi(f^{*}(z),\mathbb{R})}\pi(y^{*},\mathbb{R})$
(37) $\displaystyle=\mathcal{K}(z,y)\pi(y^{*},\mathbb{R})$ (38)
$\displaystyle=\mathcal{K}(z,y)r^{*}(y^{*})$ (39)
$\displaystyle=\mathcal{K}(z,y)\int_{{f^{*}}^{-1}(y^{*})}\mathop{}\\!\mathrm{d}\mu_{X}(x)$
(40)
$\displaystyle=\int_{{f^{*}}^{-1}(y^{*})}\mathcal{K}(z,y)\mathop{}\\!\mathrm{d}\mu_{X}(x)$
(41)
$\displaystyle=\int_{{f^{*}}^{-1}(y^{*})}\mathcal{K}(x,y)\mathop{}\\!\mathrm{d}\mu_{X}(x),$
(42)

where line 3 is by construction of $\mathcal{K}$, line 4 by the assumption
that $\pi\in\Pi(r^{*},q)$, and the last line is because
$\mathcal{K}(x,y)=\mathcal{K}(z,y)$ for all $x\in{f^{*}}^{-1}(y^{*})$, also by
construction. ∎

This lemma allows us to formulate the problem of finding the optimal regressor
under a shape constraint $q$ as that of finding the optimal coupling
$\pi\in\Pi(r^{*},q)$ with the squared cost (and $\pi$ can be used to derive
the regressor $g\circ f^{*}$ that achieves the minimum of the original
problem). Because statistical parity is a shape constraint on the regressors,
we can leverage this lemma to prove Theorem 3.1:

###### Proof of Theorem 3.1.

Because we are finding an attribute-aware fair regressor,
$f:\mathcal{X}\times\mathcal{A}\rightarrow\mathbb{R}$, we can optimize the
components corresponding to each group independently, i.e., $f_{a}\coloneqq
f(\cdot,a)$, $\forall a\in\mathcal{A}$. Denote the excess risk conditioned on
group $a$ by
$\operatorname{\mathit{ER}}_{a}(f_{a})=\operatorname{\mathbb{E}}[(f_{a}(X)-Y)^{2}\mid
A=a]$, and the marginal distribution of $X$ conditioned on $A=a$ by
$\mu_{X\mid a}$, then

$\displaystyle\min_{f:\Delta_{\textnormal{SP}}(f)\leq\alpha}\operatorname{\mathit{ER}}(f)$
$\displaystyle=\min_{f:D_{\textnormal{KS}}(f_{a}\sharp\mu_{X\mid
a},f_{a^{\prime}}\sharp\mu_{X\mid a})\leq\alpha}\operatorname{\mathit{ER}}(f)$
(43)
$\displaystyle=\min_{f:D_{\textnormal{KS}}(r_{a}(f),r_{a^{\prime}}(f))\leq\alpha}\sum_{a\in\mathcal{A}}w_{a}\operatorname{\mathit{ER}}_{a}(f_{a})$
(44)
$\displaystyle=\min_{\\{f_{a}\\}_{a\in\mathcal{A}}:D_{\textnormal{KS}}(f_{a}\sharp\mu_{X\mid
a},f_{a^{\prime}}\sharp\mu_{X\mid
a^{\prime}})\leq\alpha}\sum_{a\in\mathcal{A}}w_{a}\operatorname{\mathit{ER}}_{a}(f_{a})$
(45)
$\displaystyle=\min_{\\{q_{a}\\}_{a\in\mathcal{A}}:D_{\textnormal{KS}}(q_{a},q_{a^{\prime}})\leq\alpha}\sum_{a\in\mathcal{A}}w_{a}\min_{f_{a}:f_{a}\sharp\mu_{X\mid
a}=q_{a}}\operatorname{\mathit{ER}}_{a}(f_{a})$ (46)
$\displaystyle=\min_{\begin{subarray}{c}q:\operatorname{supp}(q)\subseteq\mathbb{R}\\\
\\{q_{a}\\}_{a\in\mathcal{A}}\subset
B_{\textnormal{KS}}(q,\nicefrac{{\alpha}}{{2}})\end{subarray}}\sum_{a\in\mathcal{A}}w_{a}\min_{f_{a}:f_{a}\sharp\mu_{X\mid
a}=q_{a}}\operatorname{\mathit{ER}}_{a}(f_{a})$ (47)

(the proof that $D_{\textnormal{KS}}(\mu,\nu)\leq\alpha\iff\exists q\text{
s.t.\ }\mu,\nu\in B_{\textnormal{KS}}(q,\nicefrac{{\alpha}}{{2}})$ is omitted;
a hint for the forward direction is that such a $q$ can be constructed by
averaging the CDFs of $\mu,\nu$), where, by Lemma A.4 and the definition of
Wasserstein distance,

$\displaystyle\min_{f_{a}:f_{a}\sharp\mu_{X\mid
a}=q_{a}}\operatorname{\mathit{ER}}_{a}(f_{a})=\min_{\pi_{a}\in\Pi(r^{*}_{a},q_{a})}\int(y^{*}-y)^{2}\mathop{}\\!\mathrm{d}\pi_{a}(y^{*},y)=W_{2}^{2}(r^{*}_{a},q_{a}),$
(48)

and the theorem follows by plugging this back into the previous equation. ∎

##  Appendix B Proofs for Section 3

We analyze the $L^{1}$ sensitivity for our notion of neighboring datasets
described in Section 2, and provide the proofs to Theorems 3.2 and 3.3, in
that order.

######  Remark B.1.

For nonempty neighboring datasets $S,S^{\prime}$ that differ in at most one
entry by insertion, deletion or substitution, the $L^{1}$ sensitivity to the
empirical PMF is at most $\nicefrac{{2}}{{n}}$.

Let $\hat{p},\hat{p}^{\prime}$ denote the empirical PMFs of $S$ and
$S^{\prime}$, respectively, assume w.l.o.g. that they have two coordinate, and
the insertion/deletion takes place in the first coordinate. Denote $n=|S|$,
$n_{1}=n\hat{p}_{1}$, and $n_{2}=n\hat{p}_{2}$.

  * •

(Insertion). The sensitivity is

$\displaystyle\|\hat{p}-\hat{p}^{\prime}\|_{1}$
$\displaystyle=\left|\frac{n_{1}}{n}-\frac{n_{1}+1}{n+1}\right|+\left|\frac{n_{2}}{n}-\frac{n_{2}}{n+1}\right|$
(49)
$\displaystyle=\left|\frac{n_{1}(n+1)-(n_{1}+1)n}{n(n+1)}\right|+\left|\frac{n_{2}(n+1)-n_{2}n}{n(n+1)}\right|$
(50)
$\displaystyle=\left|\frac{n_{1}-n}{n(n+1)}\right|+\left|\frac{n_{2}}{n(n+1)}\right|$
(51) $\displaystyle=2\left|\frac{n_{2}}{n(n+1)}\right|$ (52)
$\displaystyle\leq\frac{2}{n}.$ (53)

  * •

(Deletion). Similarly,
$\|\hat{p}-\hat{p}^{\prime}\|_{1}=|\nicefrac{{n_{1}}}{{n}}-\nicefrac{{n_{1}-1}}{{n-1}}|+|\nicefrac{{n_{2}}}{{n}}-\nicefrac{{n_{2}}}{{n-1}}|=2|\nicefrac{{n_{2}}}{{n(n-1)}}|\leq\nicefrac{{2}}{{n}}$,
because $n_{2}\leq n-1$.

  * •

(Substitution).
$\|\hat{p}-\hat{p}^{\prime}\|_{1}=|\nicefrac{{n_{1}}}{{n}}-\nicefrac{{n_{1}-1}}{{n}}|+|\nicefrac{{n_{2}}}{{n}}-\nicefrac{{n_{2}+1}}{{n}}|=|\nicefrac{{1}}{{n}}|+|\nicefrac{{1}}{{n}}|=\nicefrac{{2}}{{n}}$.

For the proofs of the theorems, several technical results are required. First,
a concentration bound of i.i.d. sum of Laplace random variables based on the
following fact (Li and Tkocz, 2023), which is due to
$\sqrt{2Y_{j}}Z\sim\mathrm{Laplace}(0,1)$ and
$\sum_{j=1}^{k}a_{j}Z_{j}\sim\mathcal{N}(0,\sum_{j=1}^{k}a^{2}_{j})$ for
$Z_{1},\dots,Z_{k}\sim\mathcal{N}(0,1)$ and $a_{1},\dots,a_{k}\geq 0$:

######  Proposition B.2.

Let $X_{1},\dots,X_{k}\sim\mathrm{Laplace}(0,1)$,
$Y_{1},\dots,Y_{k}\sim\mathrm{Exponential}(1)$, and $Z\sim\mathcal{N}(0,1)$
all be independent, then $\sum_{j=1}^{k}X_{j}$ has the same distribution as
$\lparen 2\sum_{j=1}^{k}Y_{j}\rparen^{1/2}Z$.

######  Lemma B.3.

Let independent $X_{1},\dots,X_{k}\sim\mathrm{Laplace}(0,1)$, then for all
$t\geq 0$, with probability at least $1-\beta$, $|\sum_{j=1}^{k}X_{j}|\leq
2\sqrt{k}\ln\nicefrac{{2k}}{{\beta}}$.

###### Proof.

Using Proposition B.2, we bound $\sum_{j=1}^{k}X_{j}$ by analyzing
$\sqrt{\sum_{j=1}^{k}Y_{j}}|Z|$. For all $t\geq 0$,

$\displaystyle\operatorname{\mathbb{P}}\left\lparen\sum_{j=1}^{k}Y_{j}\geq
t\right\rparen$ $\displaystyle\leq\operatorname{\mathbb{P}}\left\lparen\exists
j\text{ s.t.\ }Y_{j}\geq\frac{t}{k}\right\rparen\leq
k\operatorname{\mathbb{P}}\left\lparen Y_{1}\geq\frac{t}{k}\right\rparen\leq
k\exp\left\lparen-\frac{t}{k}\right\rparen.$ (54)

On the other hand, the Chernoff bound implies that
$\operatorname{\mathbb{P}}(|Z|\geq t)\leq 2\exp(-\nicefrac{{t^{2}}}{{2}})$.
With a union bound, with probability at least $1-\beta$,

$\displaystyle\left|\sqrt{2\sum_{j=1}^{k}Y_{j}}Z\right|$
$\displaystyle=\sqrt{2\sum_{j=1}^{k}Y_{j}}|Z|\leq
2\sqrt{k}\ln\frac{2k}{\beta}.\qed$ (55)

Next, an $L^{1}$ (TV) convergence result of empirical distributions with
finite support, which follows from the concentration of i.i.d. sum of
Multinoulli random variables:

######  Theorem B.4 (Weissman et al., 2003).

Let $p\in\Delta^{d-1}$ the $(d-1)$ simplex and
$\hat{p}_{n}\sim\nicefrac{{1}}{{n}}\mathrm{Multinomial}(n,p)$, then with
probability at least $1-\beta$,
$\|p-\hat{p}_{n}\|_{1}\leq\sqrt{{\nicefrac{{2d}}{{n}}\ln\nicefrac{{2}}{{\beta}}}}$.

######  Lemma B.5.

Let independent $x_{1},\dots,x_{n}\sim p$ with finite support $\mathcal{X}$,
and denote the empirical distribution by
$\hat{p}_{n}=\nicefrac{{1}}{{n}}\sum_{i=1}^{n}\beta_{x_{i}}$, then with
probability at least $1-\beta$,
$\|p-\hat{p}_{n}\|_{1}\leq\sqrt{\nicefrac{{2|\mathcal{X}|}}{{n}}\ln\nicefrac{{2}}{{\beta}}}$.

For the proof of Theorem 3.2, we need two technical results:

######  Lemma B.6.

Let independent $x_{1},\dots,x_{n}\sim p$ supported on $[k]$, and denote the
empirical PMF by
$\hat{p}_{j}=\nicefrac{{1}}{{n}}\sum_{i}\operatorname{\mathds{1}}[x_{i}=j]$,
for all $j\in[k]$. Let $E\subseteq[k]$ be a subset of size $\ell$, denote
$w_{E}=\operatorname{\mathbb{P}}(x\in E)$, the PMF conditioned on the event
$x\in E$ by $p_{\mid E}$, and its empirical counterpart by $\hat{p}_{j\mid
E}=\nicefrac{{1}}{{n_{E}}}\sum_{i}\operatorname{\mathds{1}}[x_{i}=j]$, where
$n_{E}=\sum_{i}\operatorname{\mathds{1}}[x_{j}\in E]$. Then for all
$n\geq\nicefrac{{8}}{{w_{E}}}\ln\nicefrac{{8}}{{\beta}}$, with probability at
least $1-\beta$,

$\displaystyle\|p_{\mid E}-\hat{p}_{\mid E}\|_{\infty}$
$\displaystyle\leq\sqrt{\frac{1}{nw_{E}}\ln\frac{8\ell}{\beta}},$ (56)
$\displaystyle D_{\textnormal{TV}}(p_{\mid E},\hat{p}_{\mid E})$
$\displaystyle=\frac{1}{2}\|p_{\mid E}-\hat{p}_{\mid
E}\|_{1}\leq\sqrt{\frac{\ell}{4nw_{E}}\ln\frac{8}{\beta}},$ (57)
$\displaystyle D_{\textnormal{KS}}(p_{\mid E},\hat{p}_{\mid E})$
$\displaystyle\leq\sqrt{\frac{1}{nw_{E}}\ln\frac{8\ell}{\beta}}.$ (58)

###### Proof.

By Chernoff bound on the Binomial distribution, for all
$n\geq\nicefrac{{8}}{{w_{E}}}\ln\nicefrac{{2}}{{\beta}}$, with probability at
least $1-\beta$,

$\frac{nw_{E}}{2}\leq n_{E}\leq 2nw_{E}.$ (59)

Order the samples so that the ones with $x_{i}\in E$ are at the front (or,
consider first sample $n_{E}$, then sample the first $n_{E}$ samples from
$p_{\mid E}$). Conditioned on Eq. 59, by Hoeffding’s inequality and a union
bound, for all $j\in E$, with probability at least $1-\beta$,

$\displaystyle|p_{j\mid E}-\hat{p}_{j\mid E}|$
$\displaystyle=\left|\frac{1}{w_{E}}\operatorname{\mathbb{P}}(X=j)-\frac{1}{n_{E}}\sum_{i=1}^{n_{E}}\operatorname{\mathds{1}}[x_{i}=j]\right|$
(60)
$\displaystyle=\frac{1}{w_{E}}\left|\operatorname{\mathbb{P}}(X=j)-\frac{1}{n_{E}}\sum_{i=1}^{n_{E}}w_{E}\operatorname{\mathds{1}}[x_{i}=j]\right|$
(61)
$\displaystyle\leq\frac{1}{w_{E}}\sqrt{\frac{w_{E}^{2}}{2n_{E}}\ln\frac{2\ell}{\beta}}$
(62) $\displaystyle\leq\sqrt{\frac{1}{nw_{E}}\ln\frac{2\ell}{\beta}}.$ (63)

Next, by Lemma B.5, with probability at least $1-\beta$,

$\displaystyle D_{\textnormal{TV}}(p_{\mid E},\hat{p}_{\mid E})$
$\displaystyle=\frac{1}{2}\sum_{j\in E}\left|p_{j\mid E}-\hat{p}_{j\mid
E}\right|$ (64) $\displaystyle=\frac{1}{2}\sum_{j\in
E}\left|\frac{1}{w_{E}}P(X=j)-\frac{1}{n_{E}}\sum_{i=1}^{n_{E}}\operatorname{\mathds{1}}[x_{i}=j]\right|$
(65)
$\displaystyle\leq\frac{1}{2}\sqrt{\frac{\ell}{2n_{E}}\ln\frac{2}{\beta}}$
(66) $\displaystyle\leq\sqrt{\frac{\ell}{4nw_{E}}\ln\frac{2}{\beta}}.$ (67)

Lastly, $D_{\textnormal{KS}}$ computes the $L^{\infty}$-distance between two
CDFs, so similar to the $\ell_{\infty}$ bound, by Hoeffding’s inequality and a
union bound, with probability at least $1-\beta$,

$\displaystyle D_{\textnormal{KS}}(p_{\mid E},\hat{p}_{\mid E})$
$\displaystyle=\max_{j\in
E}\left|\frac{1}{w_{E}}\operatorname{\mathbb{P}}(X\leq
j)-\frac{1}{n_{E}}\sum_{i=1}^{n_{E}}\operatorname{\mathds{1}}[x_{i}\leq
j]\right|$ (68)
$\displaystyle=\frac{1}{w_{E}}\left|\operatorname{\mathbb{P}}(X\leq
j)-\frac{1}{n_{E}}\sum_{i=1}^{n_{E}}w_{E}\operatorname{\mathds{1}}[x_{i}\leq
j]\right|$ (69)
$\displaystyle\leq\frac{1}{w_{E}}\sqrt{\frac{w_{E}^{2}}{2n_{E}}\ln\frac{2\ell}{\beta}}$
(70) $\displaystyle\leq\sqrt{\frac{1}{nw_{E}}\ln\frac{2\ell}{\beta}}.$ (71)

The result follows by taking a final union bound over the four events during
the analysis and rescaling $\beta\leftarrow\beta/4$. ∎

######  Lemma B.7.

Let constants $a_{1},\dots,a_{k}\geq 0$, and independent
$\xi_{1},\dots,\xi_{k}\sim\mathrm{Laplace}(0,b)$. Denote
$S_{j}=\sum_{\ell=1}^{j}a_{j}$, $s=S_{k}$, and let $t\geq 0$. Define for all
$j\in[k]$,

(add noise) $\displaystyle x_{j}\coloneqq{}$ $\displaystyle a_{j}+\xi_{j},$
$\displaystyle F_{j}={}$ $\displaystyle\sum_{k=1}^{j}x_{k},$ (isotonic
regression) $\displaystyle y_{j}={}$ $\displaystyle G_{j}-G_{j-1},$
$\displaystyle G_{j}\coloneqq{}$ $\displaystyle\frac{1}{2}\left\lparen
F_{l_{j}}+F_{r_{j}}\right\rparen,$ (clipping) $\displaystyle z_{j}={}$
$\displaystyle H_{j}-H_{j-1},$ $\displaystyle H_{j}\coloneqq{}$
$\displaystyle\begin{cases}\operatorname{\mathrm{proj}}_{[0,t]}G_{j}&\text{if
}j<k\\\ t&\text{else},\end{cases}$

where

$(l_{j},r_{j})=\operatorname*{arg\,max}_{l\leq j\leq r}(F_{l}-F_{r}).$ (72)

Then with probability at least $1-\beta$,

$\displaystyle\|a-z\|_{1}$ $\displaystyle\leq 3|s-t|+74bk\ln\frac{4k}{\beta},$
(73) $\displaystyle\|a-z\|_{\infty}$ $\displaystyle\leq
2|s-t|+32b\sqrt{k}\ln\frac{4k}{\beta},$ (74) $\displaystyle\|S-H\|_{\infty}$
$\displaystyle\leq|s-t|+12b\sqrt{k}\ln\frac{4k}{\beta}.$ (75)

###### Proof.

Our analysis for proceeds by using the triangle inequality to decompose into
and bounding each of the following terms (shown here for $\|\cdot\|_{1}$,
analogously for $\|\cdot\|_{\infty}$ and the partial sums):

$\|a-z\|_{1}\leq\|a-x\|_{1}+\|x-y\|_{1}+\|y-z\|_{1}.$ (76)

We will use the following concentration result of Laplace random variables: by
Lemma B.3, with probability at least $1-\beta$, for all $0\leq\ell\leq m\leq
k$,

$\left|\sum_{j=\ell+1}^{m}\xi_{j}\right|\leq
4b\sqrt{m-\ell}\ln\frac{2(m-\ell)k^{2}}{\beta}\leq
12b\sqrt{m-\ell}\ln\frac{2k}{\beta}.$ (77)

#### First Term in Eq. 76.

By the CDF of the exponential distribution (of which the Laplace distribution
is the two-sided version), with a union bound, with probability at least
$1-\beta$,

$|a_{j}-x_{j}|=|\xi_{j}|\leq 2b\ln\frac{k}{\beta},\quad\forall j\in[k],$ (78)

and it follows that

$\|a-x\|_{1}=\sum_{j=1}^{k}|a_{j}-x_{j}|\leq 2bk\ln\frac{k}{\beta}.$ (79)

For the partial sums, by Eq. 77,

$\displaystyle\|S-H\|_{\infty}=\max_{j}\left|S_{j}-F_{j}\right|=\max_{j}\left|\sum_{\ell=1}^{j}\xi_{\ell}\right|\leq\max_{j}12b\sqrt{j}\ln\frac{2k}{\beta}=12b\sqrt{k}\ln\frac{2k}{\beta}.$
(80)

#### Second Term in Eq. 76.

Note that for any $\ell\leq m$ such that $F_{\ell}\geq F_{m}$ (i.e., a
violating pair for isotonic regression),

$G_{\ell}-G_{m}=F_{\ell}-F_{\ell}-\sum_{j=\ell+1}^{m}a_{\ell}-\sum_{j=\ell+1}^{m}\xi_{\ell}\leq-\sum_{j=\ell+1}^{m}\xi_{\ell}\leq
12b\sqrt{m-\ell}\ln\frac{2k}{\beta},$ (81)

because $a_{j}\geq 0$. So for all $j\in[k]$,

$\displaystyle 0\leq|x_{j}-y_{j}|$
$\displaystyle=\left|G_{j}-G_{j-1}-(F_{j}-F_{j-1})\right|$ (82)
$\displaystyle\leq\left|G_{j}-F_{j}\right|+\left|G_{j-1}-F_{j-1}\right|$ (83)
$\displaystyle=\begin{rcases}\begin{dcases}G_{j}-F_{j}&\text{if
}G_{j}>F_{j}\\\
F_{j}-G_{j}&\text{else}\end{dcases}\end{rcases}+\begin{rcases}\begin{dcases}G_{j-1}-F_{j-1}&\text{if
}G_{j-1}>F_{j-1}\\\ F_{j-1}-G_{j-1}&\text{else}\end{dcases}\end{rcases}$ (84)
$\displaystyle=\begin{rcases}\begin{dcases}G_{j}-\frac{G_{l_{j}}+G_{r_{j}}}{2}&\text{if
}G_{j}>F_{j}\\\
\frac{G_{l_{j}}+G_{r_{j}}}{2}-G_{j}&\text{else}\end{dcases}\end{rcases}+\begin{rcases}\begin{dcases}G_{j-1}-\frac{G_{l_{j-1}}+G_{r_{j-1}}}{2}&\text{if
}G_{j-1}>F_{j-1}\\\
\frac{G_{l_{j-1}}+G_{r_{j-1}}}{2}-G_{j-1}&\text{else}\end{dcases}\end{rcases}$
(85)
$\displaystyle\leq\begin{rcases}\begin{dcases}G_{j}-\frac{G_{j}+G_{r_{j}}}{2}&\text{if
}G_{j}>F_{j}\\\
\frac{G_{l_{j}}+G_{j}}{2}-G_{j}&\text{else}\end{dcases}\end{rcases}+\begin{rcases}\begin{dcases}G_{j-1}-\frac{G_{j-1}+G_{r_{j-1}}}{2}&\text{if
}G_{j-1}>F_{j-1}\\\
\frac{G_{l_{j-1}}+G_{j-1}}{2}-G_{j-1}&\text{else}\end{dcases}\end{rcases}$
(86)
$\displaystyle=\frac{1}{2}\begin{rcases}\begin{dcases}G_{j}-G_{r_{j}}&\text{if
}G_{j}>F_{j}\\\
G_{l_{j}}-G_{j}&\text{else}\end{dcases}\end{rcases}+\frac{1}{2}\begin{rcases}\begin{dcases}G_{j-1}-G_{r_{j-1}}&\text{if
}G_{j-1}>F_{j-1}\\\ G_{l_{j-1}}-G_{j-1}&\text{else}\end{dcases}\end{rcases}$
(87) $\displaystyle\leq 12b\sqrt{\max(r_{j}-j,j-l_{j})}\ln\frac{2k}{\beta}\leq
12b\sqrt{\max(k-j,j)}\ln\frac{2k}{\beta},$ (88)

where line 5 is because $G_{r_{m}}\leq G_{m}\leq G_{l_{m}}$ for all $j$, and
line 7 by Eq. 81. It then follows that

$\|x-y\|_{1}=\sum_{j=1}^{k}|x_{j}-y_{j}|\leq 24bk\ln\frac{2k}{\beta}.$ (89)

Lastly, using the fact that the $L^{\infty}$ error of $L^{\infty}$ isotonic
regression is $\nicefrac{{1}}{{2}}\max_{\ell\leq m}(G_{\ell}-G_{m})$ (Stout,
2017), and by Eq. 81 again,

$\displaystyle 0\leq\|F-G\|_{\infty}=\frac{1}{2}\max_{\ell\leq
m}(G_{\ell}-G_{m})\leq 6b\sqrt{k}\ln\frac{2k}{\beta}.$ (90)

#### Third Term in Eq. 76.

Note that because $a_{j}\in[0,s]$, by Eq. 77,

$\displaystyle\min_{j}G_{j}$
$\displaystyle=\min_{j}\frac{1}{2}(F_{l_{j}}+F_{r_{j}})\geq\min_{j}F_{j}=\min_{j}\sum_{m=1}^{j}\left\lparen
a_{m}+\xi_{m}\right\rparen$ (91)
$\displaystyle\geq\min_{j}\sum_{m=1}^{j}\xi_{m}\geq-\max_{j}\left|\sum_{j=1}^{k}\xi_{j}\right|\geq-12b\sqrt{k}\ln\frac{2k}{\beta},$
(92)

and similarly,

$\max_{j}G_{j}\leq\max_{j}\sum_{m=1}^{j}\left\lparen
a_{m}+\xi_{m}\right\rparen\leq s+12b\sqrt{k}\ln\frac{2k}{\beta}.$ (93)

Since $G$ is nondecreasing after isotonic regression, clipping only affects
its prefix and/or suffix. For the prefix, let ${l}=\max\\{j\in[k]:H_{j}=0\\}$.
If ${l}$ does not exist, then no clipping to zero has occurred. Otherwise, for
all $j\leq{l}$, by Eq. 92,

$|G_{j}-H_{j}|=\max(-G_{j},0)\leq 12b\sqrt{k}\ln\frac{2k}{\beta},$ (94)

and

$|y_{j}-z_{j}|=|G_{j}-G_{j-1}-(H_{j}-H_{j-1})|\leq-G_{j}-G_{j-1}\leq
2\max\left\lparen-\min_{j}G_{j},0\right\rparen\leq
24b\sqrt{k}\ln\frac{2k}{\beta}.$ (95)

For the suffix, let $r=\min\\{j\in[k]:H_{j}=t\\}$, then for all $r\leq j<k$,
by Eq. 93,

$|G_{j}-H_{j}|=G_{j}-t\leq|s-t|+12b\sqrt{k}\ln\frac{2k}{\beta},$ (96)

and

$|y_{j}-z_{j}|\leq\left\lparen G_{j}-t\right\rparen+\max(G_{j-1}-t,0)\leq
2\max\left\lparen\max_{j}G_{j}-t,0\right\rparen\leq
2|s-t|+24b\sqrt{k}\ln\frac{2k}{\beta};$ (97)

for $j=k$,

$\displaystyle|G_{k}-H_{k}|\leq\begin{cases}G_{k}-t&\text{if }G_{k}\geq t\\\
t-G_{k}&\text{else}\end{cases}=\begin{cases}G_{k}-t&\text{if }G_{k}\geq t\\\
t-\left\lparen
s+\sum_{m=1}^{k}\xi_{m}\right\rparen&\text{else}\end{cases}\leq|s-t|+12b\sqrt{k}\ln\frac{2k}{\beta},$
(98)

and

$\displaystyle|y_{j}-z_{j}|$
$\displaystyle\leq\left|G_{j}-t\right|+\max(G_{j-1}-t,0)\leq
2|s-t|+24b\sqrt{k}\ln\frac{2k}{\beta}.$ (99)

Finally, for $\|\cdot\|_{1}$,

$\displaystyle\left\|y-z\right\|_{1}$
$\displaystyle=\sum_{j=1}^{l}|G_{j}-G_{j-1}-(H_{j}-H_{j-1})|+\sum_{j=r}^{k}|G_{j}-G_{j-1}-(H_{j}-H_{j-1})|$
(100) $\displaystyle=\sum_{j=1}^{l}\lparen
G_{j}-G_{j-1}\rparen+|y_{r}-z_{r}|+\sum_{j=r+1}^{k-1}\lparen
G_{j}-G_{j-1}\rparen+|y_{k}-z_{k}|$ (101)
$\displaystyle=G_{l}-G_{1}+|y_{r}-z_{r}|+G_{k-1}-G_{r}+|y_{k}-z_{k}|$ (102)
$\displaystyle\leq-G_{1}+|y_{r}-z_{r}|+G_{k-1}-t+|y_{k}-z_{k}|$ (103)
$\displaystyle\leq
12b\sqrt{k}\ln\frac{2k}{\beta}+2\left\lparen|s-t|+12b\sqrt{k}\ln\frac{2k}{\beta}\right\rparen+\left\lparen
s+12b\sqrt{k}\ln\frac{2k}{\beta}\right\rparen-t$ (104) $\displaystyle\leq
3|s-t|+48b\sqrt{k}\ln\frac{2k}{\beta},$ (105)

keep in mind that $1\leq l$ and $r\leq k-1,k$ on line 3 and onward.

The result follows by taking a final union bound over the two events above and
rescaling $\beta\leftarrow\beta/2$. ∎

###### Proof of Theorem 3.2.

Because $w_{a}\geq 0$, by Lemma B.3, with probability at least $1-\beta$,

$\displaystyle|w_{a}-\tilde{w}_{a}|$
$\displaystyle=\left|w_{a}-\max\left\lparen
w_{a}+\sum_{j=1}^{k}\mathrm{Laplace}(0,\nicefrac{{2}}{{n\varepsilon}}),0\right\rparen\right|$
(106)
$\displaystyle=\left|\max\left\lparen\sum_{j=1}^{k}\mathrm{Laplace}(0,\nicefrac{{2}}{{n\varepsilon}}),-w_{a}\right\rparen\right|$
(107)
$\displaystyle\leq\left|\sum_{j=1}^{k}\mathrm{Laplace}(0,\nicefrac{{2}}{{n\varepsilon}})\right|$
(108) $\displaystyle\leq
O\left\lparen\frac{\sqrt{k}}{n\varepsilon}\ln\frac{k|\mathcal{A}|}{\beta}\right\rparen.$
(109)

Next, define

$\displaystyle\hat{p}_{a}(v_{j})=\frac{1}{n_{a}}\sum_{i=1}^{n}\operatorname{\mathds{1}}[h\circ
f(x_{i},a_{i}),a_{i}=a],\quad\check{p}_{a}(v_{j})=\frac{1}{\tilde{w}_{a}}\tilde{p}(a,v_{j}),$
(110)

where
$n_{a}=\nicefrac{{1}}{{n}}\sum_{i=1}^{n}\operatorname{\mathds{1}}[a_{i}=a]$.
Note that $\widecheck{F}_{a}(v_{j})=\sum_{\ell=1}^{j}\check{p}_{a}(v_{\ell})$.
By triangle inequality,

$\displaystyle\|p_{a}-\tilde{p}_{a}\|_{\infty}$ (111)
$\displaystyle\leq\|\tilde{p}_{a}-\check{p}_{a}\|_{\infty}+\|\check{p}_{a}-\hat{p}_{a}\|_{\infty}+\|\hat{p}_{a}-p_{a}\|_{\infty}$
(112)
$\displaystyle=\left\|\tilde{p}_{a}-\frac{1}{\tilde{w}_{a}}\check{p}(a,\cdot)\right\|_{\infty}+\left\|\frac{1}{\tilde{w}_{a}}\check{p}(a,\cdot)-\frac{1}{\hat{w}_{a}}\hat{p}(a,\cdot)\right\|_{\infty}+\|\hat{p}_{a}-p_{a}\|_{\infty}$
(113)
$\displaystyle\leq\left\|\tilde{p}_{a}-\frac{1}{\hat{w}_{a}}\check{p}(a,\cdot)\right\|_{\infty}+2\left\|\frac{1}{\tilde{w}_{a}}\check{p}(a,\cdot)-\frac{1}{\hat{w}_{a}}\check{p}(a,\cdot)\right\|_{\infty}+\left\|\frac{1}{\hat{w}_{a}}\check{p}(a,\cdot)-\frac{1}{\hat{w}_{a}}\hat{p}(a,\cdot)\right\|_{\infty}+\|\hat{p}_{a}-p_{a}\|_{\infty}$
(114)
$\displaystyle=\frac{1}{\hat{w}_{a}}\left\|\hat{w}_{a}\tilde{p}_{a}-\check{p}(a,\cdot)\right\|_{\infty}+\frac{2}{\hat{w}_{a}}\left|\hat{w}_{a}-\tilde{w}_{a}\right|+\frac{1}{\hat{w}_{a}}\|\check{p}(a,\cdot)-\hat{p}(a,\cdot)\|_{\infty}+\|\hat{p}_{a}-p_{a}\|_{\infty}$
(115)
$\displaystyle\leq\begin{multlined}\frac{1}{\hat{w}_{a}}\left\|\tilde{w}_{a}\tilde{p}_{a}-\hat{w}_{a}\tilde{p}_{a}\right\|_{\infty}+\frac{1}{\hat{w}_{a}}\left\|\tilde{w}_{a}\tilde{p}_{a}-\check{p}(a,\cdot)\right\|_{\infty}+\frac{2}{\hat{w}_{a}}\left|\hat{w}_{a}-\tilde{w}_{a}\right|\\\
+\frac{1}{\hat{w}_{a}}\|\check{p}(a,\cdot)-\hat{p}(a,\cdot)\|_{\infty}+\|\hat{p}_{a}-p_{a}\|_{\infty}\end{multlined}\frac{1}{\hat{w}_{a}}\left\|\tilde{w}_{a}\tilde{p}_{a}-\hat{w}_{a}\tilde{p}_{a}\right\|_{\infty}+\frac{1}{\hat{w}_{a}}\left\|\tilde{w}_{a}\tilde{p}_{a}-\check{p}(a,\cdot)\right\|_{\infty}+\frac{2}{\hat{w}_{a}}\left|\hat{w}_{a}-\tilde{w}_{a}\right|\\\
+\frac{1}{\hat{w}_{a}}\|\check{p}(a,\cdot)-\hat{p}(a,\cdot)\|_{\infty}+\|\hat{p}_{a}-p_{a}\|_{\infty}$
(118)
$\displaystyle\leq\frac{1}{\hat{w}_{a}}\left\|\tilde{w}_{a}\tilde{p}_{a}-\check{p}(a,\cdot)\right\|_{\infty}+\frac{3}{\hat{w}_{a}}\left|\hat{w}_{a}-\tilde{w}_{a}\right|+\frac{1}{\hat{w}_{a}}\|\check{p}(a,\cdot)-\hat{p}(a,\cdot)\|_{\infty}+\|\hat{p}_{a}-p_{a}\|_{\infty}$
(119) $\displaystyle\leq
O\left\lparen\frac{1}{\hat{w}_{a}}\left\lparen\left|\hat{w}_{a}-\tilde{w}_{a}\right|+\frac{\sqrt{k}}{n\varepsilon}\ln\frac{k|\mathcal{A}|}{\beta}+\frac{1}{n\varepsilon}\ln\frac{k|\mathcal{A}|}{\beta}\right\rparen+\sqrt{\frac{1}{nw_{a}}\ln\frac{k|\mathcal{A}|}{\beta}}\right\rparen$
(120) $\displaystyle\leq
O\left\lparen\frac{1}{\hat{w}_{a}}\left\lparen\frac{\sqrt{k}}{n\varepsilon}\ln\frac{k|\mathcal{A}|}{\beta}+\frac{\sqrt{k}}{n\varepsilon}\ln\frac{k|\mathcal{A}|}{\beta}+\frac{1}{n\varepsilon}\ln\frac{k|\mathcal{A}|}{\beta}\right\rparen+\sqrt{\frac{1}{nw_{a}}\ln\frac{k|\mathcal{A}|}{\beta}}\right\rparen$
(121) $\displaystyle\leq
O\left\lparen\frac{\sqrt{k}}{n\hat{w}_{a}\varepsilon}\ln\frac{k|\mathcal{A}|}{\beta}+\sqrt{\frac{1}{nw_{a}}\ln\frac{k|\mathcal{A}|}{\beta}}\right\rparen$
(122) $\displaystyle\leq
O\left\lparen\frac{\sqrt{k}}{nw_{a}\varepsilon}\ln\frac{k|\mathcal{A}|}{\beta}+\sqrt{\frac{1}{nw_{a}}\ln\frac{k|\mathcal{A}|}{\beta}}\right\rparen$
(123)

by Eqs. 109, B.6 and B.7; the bound on the
$\|\check{p}(a,\cdot)-\hat{p}(a,\cdot)\|_{\infty}$ follows the same analysis
in the proof of Lemma B.7 for the first term.

Similarly,

$\displaystyle\|p_{a}-\tilde{p}_{a}\|_{1}$
$\displaystyle\leq\frac{1}{\hat{w}_{a}}\left\|\tilde{w}_{a}\tilde{p}_{a}-\check{p}(a,\cdot)\right\|_{1}+\frac{3}{\hat{w}_{a}}\left|\hat{w}_{a}-\tilde{w}_{a}\right|+\frac{1}{\hat{w}_{a}}\|\check{p}(a,\cdot)-\hat{p}(a,\cdot)\|_{1}+\|\hat{p}_{a}-p_{a}\|_{1}$
(124) $\displaystyle\leq
O\left\lparen\frac{{k}}{nw_{a}\varepsilon}\ln\frac{k|\mathcal{A}|}{\beta}+\sqrt{\frac{k}{nw_{a}}\ln\frac{|\mathcal{A}|}{\beta}}\right\rparen,$
(125)

and

$\displaystyle D_{\textnormal{KS}}(p_{a},\tilde{p}_{a})$
$\displaystyle\leq\begin{multlined}\frac{1}{\hat{w}_{a}}\max_{j}\left|\sum_{\ell=1}^{j}\left\lparen\tilde{w}_{a}\tilde{p}_{a}(v_{\ell})-\check{p}(a,v_{\ell})\right\rparen\right|+\frac{3}{\hat{w}_{a}}\left|\hat{w}_{a}-\tilde{w}_{a}\right|\\\
+\frac{1}{\hat{w}_{a}}\max_{j}\left|\sum_{\ell=1}^{j}\left\lparen\check{p}(a,\cdot)-\hat{p}(a,\cdot)\right\rparen\right|+D_{\textnormal{KS}}(\hat{p}_{a},p_{a})\end{multlined}\frac{1}{\hat{w}_{a}}\max_{j}\left|\sum_{\ell=1}^{j}\left\lparen\tilde{w}_{a}\tilde{p}_{a}(v_{\ell})-\check{p}(a,v_{\ell})\right\rparen\right|+\frac{3}{\hat{w}_{a}}\left|\hat{w}_{a}-\tilde{w}_{a}\right|\\\
+\frac{1}{\hat{w}_{a}}\max_{j}\left|\sum_{\ell=1}^{j}\left\lparen\check{p}(a,\cdot)-\hat{p}(a,\cdot)\right\rparen\right|+D_{\textnormal{KS}}(\hat{p}_{a},p_{a})$
(128) $\displaystyle\leq
O\left\lparen\frac{\sqrt{k}}{nw_{a}\varepsilon}\ln\frac{k|\mathcal{A}|}{\beta}+\sqrt{\frac{k}{nw_{a}}\ln\frac{k|\mathcal{A}|}{\beta}}\right\rparen.\qed$
(129)

For the proof of Theorem 3.3, we need the following technical result for the
difference of $W_{2}^{2}$ distances:

######  Lemma B.8 (Chizat et al., 2020).

Let $\mu,\mu^{\prime},\nu,\nu^{\prime}$ be distributions whose supports are
contained in the centered ball of radius $R$ in $\mathbb{R}^{d}$, then

$\displaystyle\left|W_{2}^{2}(\mu,\nu)-W_{2}^{2}(\mu^{\prime},\nu^{\prime})\right|$
(130)
$\displaystyle\leq\begin{multlined}\left|\int\|x\|_{2}^{2}\mathop{}\\!\mathrm{d}(\mu-\mu^{\prime})(x)\right|+\left|\int\|x\|_{2}^{2}\mathop{}\\!\mathrm{d}(\nu-\nu^{\prime})(x)\right|\\\
+2R\sup_{\textnormal{convex }f\in\mathrm{Lip}(1)}\left|\int
f(x)\mathop{}\\!\mathrm{d}(\mu-\mu^{\prime})(x)\right|+2R\sup_{\textnormal{convex
}g\in\mathrm{Lip}(1)}\left|\int
g(x)\mathop{}\\!\mathrm{d}(\nu-\nu^{\prime})(x)\right|\end{multlined}\left|\int\|x\|_{2}^{2}\mathop{}\\!\mathrm{d}(\mu-\mu^{\prime})(x)\right|+\left|\int\|x\|_{2}^{2}\mathop{}\\!\mathrm{d}(\nu-\nu^{\prime})(x)\right|\\\
+2R\sup_{\textnormal{convex }f\in\mathrm{Lip}(1)}\left|\int
f(x)\mathop{}\\!\mathrm{d}(\mu-\mu^{\prime})(x)\right|+2R\sup_{\textnormal{convex
}g\in\mathrm{Lip}(1)}\left|\int
g(x)\mathop{}\\!\mathrm{d}(\nu-\nu^{\prime})(x)\right|$ (133)
$\displaystyle\leq 4RW_{1}(\mu,\mu^{\prime})+4RW_{1}(\nu,\nu^{\prime}).$ (134)

The last line follows from the dual representation of $W_{1}$ distance for
distributions with bounded support:

$W_{1}(\mu,\nu)=\sup_{f\in\mathrm{Lip}(1)}\left|\int
f(x)\mathop{}\\!\mathrm{d}(\mu-\nu)(x)\right|,$ (135)

and the fact that $x\mapsto\|x\|_{2}^{2}$ is $2R$-Lipschitz on the centered
ball of radius $R$.

Also, recall the fact that the $W_{1}$ distance of distributions supported on
a ball of radius $R$ can be upper bounded by total variation distance:

$\displaystyle W_{1}(\mu,\nu)$ $\displaystyle=\inf_{\pi\in\Pi(\mu,\nu)}\int
d(x,y)\mathop{}\\!\mathrm{d}\pi(x,y)$ (136) $\displaystyle\leq
2R\inf_{\pi\in\Pi(\mu,\nu)}\int\operatorname{\mathds{1}}[x\neq
y]\mathop{}\\!\mathrm{d}\pi(x,y)$ (137) $\displaystyle=2R\left\lparen
1-\sup_{\pi\in\Pi(\mu,\nu)}\int\operatorname{\mathds{1}}[x=y]\mathop{}\\!\mathrm{d}\pi(x,y)\right\rparen$
(138) $\displaystyle=2R\left\lparen
1-\int\min\left\lparen\mu(x),\nu(x)\right\rparen\mathop{}\\!\mathrm{d}x\right\rparen$
(139) $\displaystyle=2R{\int\max\left\lparen
0,\nu(x)-\mu(x)\right\rparen\mathop{}\\!\mathrm{d}x}$ (140)
$\displaystyle=R{\int\left|\nu(x)-\mu(x)\right|\mathop{}\\!\mathrm{d}x}$ (141)
$\displaystyle\eqqcolon R\|\mu-\nu\|_{1}$ (142) $\displaystyle\eqqcolon
2RD_{\textnormal{TV}}(\mu,\nu),$ (143)

where line 6 is because
$\int\lparen\mu(x)-\nu(x)\rparen\mathop{}\\!\mathrm{d}x=0$.

And, note the following simple fact regarding optimal transports
$T^{*}:\mathbb{R}\rightarrow\mathbb{R}$ under the squared cost; in the special
case where $T^{*}$ is a Monge transportation plan, the lemma is equivalent to
saying that $T^{*}$ is a nondecreasing function (see the last panel of Fig. 1
for a picture):

######  Lemma B.9.

Let $p,q$ be two distributions supported on $[k]$, and
$\pi\in\operatorname*{arg\,min}_{\pi^{\prime}\in\Pi(p,q)}\sum_{m,\ell}(m-\ell)^{2}\pi(m,\ell)$,
then for all $j\in[k]$,

$f(m)\coloneqq\sum_{\ell=1}^{j}\frac{\pi(m,\ell)}{p(m)}\begin{cases}=1&\text{if
}m<l_{j}\\\ \in[0,1]&\text{if }m=l_{j}\\\ =0&\text{if }m>l_{j},\\\
\end{cases}\quad\forall m\textrm{ s.t. }p(m)>0,$ (144)

for some $l_{1},\dots,l_{k}\in[k]$.

###### Proof.

Let $j\in[k]$ be arbitrary. Suppose to the contrary that $\nexists l_{j}$ such
that Eq. 144 holds, then either $f$ as a function of $m$ is not non-
increasing, i.e., $f(m+1)>f(m)$ for some $m$, or $0<f(m+1)\leq f(m)<1$. We
show that either of these contradicts the optimality of $\pi$.

In both cases, there must exists $l\leq j<r$ such that
$\pi(m,r),\pi(m+1,l)\geq q$ for some $q>0$, because
$\sum_{\ell=1}^{j}\pi(m+1,\ell)=p(m+1)f(m+1)>0$ and
$\sum_{\ell=j+1}^{k}\pi(m,\ell)=p(m)(1-f(m))>0$. Then a coupling $\gamma$ with
a lower cost can be constructed by (partially) exchanging the two entries:

$\gamma(i,\ell)=\begin{cases}\pi(m,r)-q&\text{if }i=m,\ell=r\\\
\pi(m,l)+q&\text{if }i=m,\ell=l\\\ \pi(m+1,r)+q&\text{if }i=m+1,\ell=r\\\
\pi(m+1,l)-q&\text{if }i=m+1,\ell=l\\\ \pi(i,\ell)&\text{else}.\\\
\end{cases}$ (145)

We verify that it has a lower cost than $\pi$:

$\displaystyle\sum_{i,\ell}(i-\ell)^{2}(\gamma-\pi)(i,\ell)$
$\displaystyle=-q(m-r)^{2}+q(m-l)^{2}+q(m+1-r)^{2}-q(m+1-l)^{2}$ (146)
$\displaystyle=2q(l-r)$ (147) $\displaystyle<0.\qed$ (148)

###### Proof of Theorem 3.3.

This proof also relies on properly applying the triangle inequality to
decompose into comparable terms. We list the terms that will be compared here:

  * •

Denote the Bayes regressor by $f^{*}$, and recall that $f$ is the regressor
being post-processed. Denote the output distribution of $f^{*}$ conditioned on
group $a$ by $r^{*}_{a}\coloneqq f^{*}(\cdot,a)\sharp\mu_{X\mid a}$, which
will be compared to that of $f$, $r_{a}\coloneqq f(\cdot,a)\sharp\mu_{X\mid
a}$.

  * •

Given a discretizer $h$, the discretized conditional output distribution of
$f^{*}$ is denoted by $p^{*}_{a}\coloneqq h\sharp r^{*}_{a}$, and that of $f$
by $p_{a}\coloneqq h\sharp r_{a}$. We will compare $r^{*}_{a}$ to its
discretized version $p^{*}_{a}$, and $p_{a}$ to $\tilde{p}_{a}$, the empirical
conditional discretized output distributions of $f$ estimated privately.

  * •

Denote the private group marginal distribution estimated from the samples by
$\tilde{w}_{a}$, which will be compared to the ground-truth
$w_{a}\coloneqq\operatorname{\mathbb{P}}(A=a)$.

  * •

Let
$(\cdot,\\{\tilde{q}^{\prime}_{a}\\}_{a\in\mathcal{A}})\leftarrow\hyperlink{eq:p}{\mathrm{P}}(\\{\tilde{p}_{a}\\}_{a\in\mathcal{A}},\\{\tilde{w}_{a}\\}_{a\in\mathcal{A}},\alpha)$
and
$(\cdot,\cdot,\\{\tilde{q}_{a}\\}_{a\in\mathcal{A}})\leftarrow\hyperlink{eq:lp}{\mathrm{LP}}(\\{\tilde{p}_{a}\\}_{a\in\mathcal{A}},\\{\tilde{w}_{a}\\}_{a\in\mathcal{A}},\alpha)$.
The difference between $\tilde{q}^{\prime}_{a},\tilde{q}_{a}$ is that the
support of the latter is restricted to $v$.

Recall that the fair regressor returned from Algorithm 1 has the form
$\bar{f}=g_{a}\circ h\circ f$, where $g_{a}$ is the optimal transport from
$\tilde{p}_{a}$ to $\tilde{q}_{a}$. The $\tilde{q}_{a}$’s will be compared to
the $\tilde{q}^{\prime}_{a}$’s, which are in turn compared to the output
distributions $q^{*}_{a}$ of an optimal $\alpha$-fair regressor, denoted by
$\bar{f}^{*}$ (note that
$(\cdot,\\{q^{*}_{a}\\}_{a\in\mathcal{A}})\leftarrow\hyperlink{eq:p}{\mathrm{P}}(\\{r^{*}_{a}\\}_{a\in\mathcal{A}},\\{w_{a}\\}_{a\in\mathcal{A}},\alpha)$).

#### Error Bound.

Note that
$R(\bar{f})-R(\bar{f}^{*})=\operatorname{\mathit{ER}}(\bar{f})-\operatorname{\mathit{ER}}(\bar{f}^{*})$.
We begin with analyzing the first term. By the orthogonality principle,

$\displaystyle\operatorname{\mathit{ER}}(\bar{f})$
$\displaystyle=\operatorname{\mathbb{E}}\left[\left\lparen\bar{f}(X,A)-f^{*}(X,A)\right\rparen^{2}\right]$
(149)
$\displaystyle=\sum_{a\in\mathcal{A}}w_{a}\operatorname{\mathbb{E}}_{X\sim\mu_{X\mid
a}}\left[\left\lparen\bar{f}(X,a)-f^{*}(X,a)\right\rparen^{2}\right]$ (150)
$\displaystyle=\sum_{a\in\mathcal{A}}w_{a}\operatorname{\mathbb{E}}_{X\sim\mu_{X\mid
a}}\left[\left\lparen\bar{f}(X,a)-f(X,a)+\left\lparen
f(X,a)-f^{*}(X,a)\right\rparen\right\rparen^{2}\right]$ (151)
$\displaystyle=\begin{multlined}\sum_{a\in\mathcal{A}}w_{a}\Big{(}\operatorname{\mathbb{E}}_{X\sim\mu_{X\mid
a}}\Big{[}\left\lparen\bar{f}(X,a)-f(X,a)\right\rparen^{2}+\left\lparen
f(X,a)-f^{*}(X,a)\right\rparen^{2}\\\\[-5.0pt]
+2\left\lparen\bar{f}(X,a)-f(X,a)\right\rparen\left\lparen
f(X,a)-f^{*}(X,a)\right\rparen\Big{]}\Big{)}\end{multlined}\sum_{a\in\mathcal{A}}w_{a}\Big{(}\operatorname{\mathbb{E}}_{X\sim\mu_{X\mid
a}}\Big{[}\left\lparen\bar{f}(X,a)-f(X,a)\right\rparen^{2}+\left\lparen
f(X,a)-f^{*}(X,a)\right\rparen^{2}\\\\[-5.0pt]
+2\left\lparen\bar{f}(X,a)-f(X,a)\right\rparen\left\lparen
f(X,a)-f^{*}(X,a)\right\rparen\Big{]}\Big{)}$ (154)
$\displaystyle\leq\sum_{a\in\mathcal{A}}w_{a}\operatorname{\mathbb{E}}_{X\sim\mu_{X\mid
a}}\left[\left\lparen\bar{f}(X,a)-f(X,a)\right\rparen^{2}\right]+\underbrace{3\operatorname{\mathbb{E}}\left[\left|f(X,A)-f^{*}(X,A)\right|\right]}_{\mathcal{E}_{1}},$
(155)

where line 5 is because of the assumption that the images of $\bar{f},f$ are
contained in $[0,1]$. The second term on the last line is the $L^{1}$ excess
risk of $f$; for the first term,

$\displaystyle\operatorname{\mathbb{E}}_{X\sim\mu_{X\mid
a}}\left[\left\lparen\bar{f}(X,a)-f(X,a)\right\rparen^{2}\right]$ (156)
$\displaystyle=\operatorname{\mathbb{E}}_{X\sim\mu_{X\mid
a}}\left[\left\lparen g_{a}\circ h\circ f(X,a)-f(X,a)\right\rparen^{2}\right]$
(157) $\displaystyle=\operatorname{\mathbb{E}}_{X\sim\mu_{X\mid
a}}\left[\left\lparen g_{a}\circ h\circ f(X,a)-h\circ f(X,a)+\left\lparen
h\circ f(X,a)-f(X,a)\right\rparen\right\rparen^{2}\right]$ (158)
$\displaystyle\leq\operatorname{\mathbb{E}}_{X\sim\mu_{X\mid
a}}\left[\left\lparen g_{a}\circ h\circ f(X,a)-h\circ
f(X,a)\right\rparen^{2}+3\left|h\circ f(X,a)-f(X,a)\right|\right]$ (159)
$\displaystyle\leq\operatorname{\mathbb{E}}_{X\sim\mu_{X\mid
a}}\left[\left\lparen g_{a}\circ h\circ f(X,a)-h\circ
f(X,a)\right\rparen^{2}\right]+\frac{3}{2k}$ (160)
$\displaystyle=\sum_{j=1}^{k}p_{a}(v_{j})\operatorname{\mathbb{E}}\left[\left\lparen
g_{a}(v_{j})-v_{j}\right\rparen^{2}\right]+\frac{3}{2k}$ (161)
$\displaystyle=\sum_{j=1}^{k}\tilde{p}_{a}(v_{j})\operatorname{\mathbb{E}}\left[\left\lparen
g_{a}(v_{j})-v_{j}\right\rparen^{2}\right]+\sum_{j=1}^{k}(p_{a}(v_{j})-\tilde{p}_{a}(v_{j}))\operatorname{\mathbb{E}}\left[\left\lparen
g_{a}(v_{j})-v_{j}\right\rparen^{2}\right]+\frac{3}{2k}$ (162)
$\displaystyle\leq
W_{2}^{2}(\tilde{p}_{a},\tilde{q}_{a})+\left\|p_{a}-\tilde{p}_{a}\right\|_{1}+\frac{3}{2k}$
(163) $\displaystyle\leq
W_{2}^{2}(\tilde{p}_{a},\tilde{q}_{a})+O\left\lparen\sqrt{\frac{k}{nw_{a}}\ln\frac{k|\mathcal{A}|}{\beta}}+\frac{k}{nw_{a}\varepsilon}\ln\frac{k|\mathcal{A}|}{\beta}\right\rparen+\frac{3}{2k},$
(164)

where line 4 is because $h$ discretizes the input to the midpoint of the bin
that it falls in, which displaces it by up to
$\nicefrac{{L}}{{2k}}=\nicefrac{{1}}{{2k}}$; line 5 is because
$p_{a}(v_{j})=\operatorname{\mathbb{P}}(h\circ f(X,a)=v_{j})$; the first term
on line 7 is because $g_{a}$ is the optimal transport from $\tilde{p}_{a}$ to
$\tilde{q}_{a}$. Then, combining the above, by Theorem 3.2, with probability
at least $1-\beta$,

$\displaystyle\operatorname{\mathit{ER}}(\bar{f})$
$\displaystyle\leq\sum_{a\in\mathcal{A}}\left\lparen
w_{a}W_{2}^{2}(\tilde{p}_{a},\tilde{q}_{a})+O\left\lparen\sqrt{\frac{kw_{a}}{n}\ln\frac{k|\mathcal{A}|}{\beta}}+\frac{k}{n\varepsilon}\ln\frac{k|\mathcal{A}|}{\beta}\right\rparen\right\rparen+\mathcal{E}_{1}+\frac{3}{2k}$
(165)
$\displaystyle\leq\sum_{a\in\mathcal{A}}w_{a}W_{2}^{2}(\tilde{p}_{a},\tilde{q}_{a})+\mathcal{E}_{1}+\underbrace{O\left\lparen\sqrt{\frac{k|\mathcal{A}|}{n}\ln\frac{k|\mathcal{A}|}{\beta}}+\frac{k|\mathcal{A}|}{n\varepsilon}\ln\frac{k|\mathcal{A}|}{\beta}\right\rparen}_{\mathcal{E}_{2}}+\frac{3}{2k}$
(166)
$\displaystyle\leq\sum_{a\in\mathcal{A}}\left\lparen\tilde{w}_{a}W_{2}^{2}(\tilde{p}_{a},\tilde{q}_{a})+\left|\tilde{w}_{a}-w_{a}\right|W_{2}^{2}(\tilde{p}_{a},\tilde{q}_{a})\right\rparen+\mathcal{E}_{1}+\mathcal{E}_{2}+\frac{3}{2k}$
(167)
$\displaystyle\leq\sum_{a\in\mathcal{A}}\left\lparen\tilde{w}_{a}W_{2}^{2}(\tilde{p}_{a},\tilde{q}_{a})+\left|\tilde{w}_{a}-w_{a}\right|\right\rparen+\mathcal{E}_{1}+\mathcal{E}_{2}+\frac{3}{2k}$
(168)
$\displaystyle\leq\sum_{a\in\mathcal{A}}\tilde{w}_{a}W_{2}^{2}(\tilde{p}_{a},\tilde{q}_{a})+\mathcal{E}_{1}+\mathcal{E}_{2}+\frac{3}{2k}$
(169)
$\displaystyle\leq\sum_{a\in\mathcal{A}}\tilde{w}_{a}W_{2}^{2}(\tilde{p}_{a},h\sharp\tilde{q}^{\prime}_{a})+\mathcal{E}_{1}+\mathcal{E}_{2}+\frac{3}{2k}$
(170) $\displaystyle\leq\sum_{a\in\mathcal{A}}\tilde{w}_{a}\left\lparen
W_{2}(\tilde{p}_{a},\tilde{q}^{\prime}_{a})+W_{2}(\tilde{q}^{\prime}_{a},h\sharp\tilde{q}^{\prime}_{a})\right\rparen^{2}+\mathcal{E}_{1}+\mathcal{E}_{2}+\frac{3}{2k}$
(171) $\displaystyle=\sum_{a\in\mathcal{A}}\tilde{w}_{a}\left\lparen
W^{2}_{2}(\tilde{p}_{a},\tilde{q}^{\prime}_{a})+2W_{2}(\tilde{p}_{a},\tilde{q}^{\prime}_{a})W_{2}(\tilde{q}^{\prime}_{a},h\sharp\tilde{q}^{\prime}_{a})+W^{2}_{2}(\tilde{q}^{\prime}_{a},h\sharp\tilde{q}^{\prime}_{a})\right\rparen+\mathcal{E}_{1}+\mathcal{E}_{2}+\frac{3}{2k}$
(172)
$\displaystyle\leq\sum_{a\in\mathcal{A}}\tilde{w}_{a}W_{2}^{2}(\tilde{p}_{a},\tilde{q}^{\prime}_{a})+\mathcal{E}_{1}+\mathcal{E}_{2}+\frac{3}{k}$
(173)
$\displaystyle\leq\sum_{a\in\mathcal{A}}\tilde{w}_{a}W_{2}^{2}(\tilde{p}_{a},q^{*}_{a})+\mathcal{E}_{1}+\mathcal{E}_{2}+\frac{3}{k},$
(174)

where line 6 follows by noting that
$\\{h\sharp\tilde{q}^{\prime}_{a}\\}_{a\in\mathcal{A}}$ is a feasible solution
to LP, as it can be verified that
$D_{\textnormal{KS}}(h\sharp\tilde{q}^{\prime}_{a},h\sharp\tilde{q}^{\prime}_{a^{\prime}})\leq\alpha$
given that
$D_{\textnormal{KS}}(\tilde{q}^{\prime}_{a},\tilde{q}^{\prime}_{a^{\prime}})\leq\alpha$,
$\forall a,a^{\prime}\in\mathcal{A}$ (hence restricting the support of the
barycenter to $v$ introduces an additional error of $\nicefrac{{3}}{{2k}}$ as
discussed in footnote 3), and the last line is because
$\\{\tilde{q}^{\prime}_{a}\\}_{a\in\mathcal{A}}$ is a minimizer of
$\hyperlink{eq:p}{\mathrm{P}}(\\{\tilde{p}_{a}\\}_{a\in\mathcal{A}},\\{\tilde{w}_{a}\\}_{a\in\mathcal{A}},\alpha)$.

So for the suboptimality of $\bar{h}$, by Theorem 3.1,

$\displaystyle\operatorname{\mathit{ER}}(\bar{f})-\operatorname{\mathit{ER}}(\bar{f}^{*})$
$\displaystyle\leq\sum_{a\in\mathcal{A}}\tilde{w}_{a}\left\lparen
W_{2}^{2}(\tilde{p}_{a},q^{*}_{a})-W_{2}^{2}(r^{*}_{a},q^{*}_{a})\right\rparen+\mathcal{E}_{1}+\mathcal{E}_{2}+\frac{3}{k}$
(175) $\displaystyle\leq\sum_{a\in\mathcal{A}}\tilde{w}_{a}\left\lparen
W_{2}^{2}(\tilde{p}_{a},q^{*}_{a})-\left\lparen
W_{2}(q^{*}_{a},p^{*}_{a})-W_{2}(r^{*}_{a},p^{*}_{a})\right\rparen\right\rparen^{2}+\mathcal{E}_{1}+\mathcal{E}_{2}+\frac{3}{k}$
(176) $\displaystyle\leq\sum_{a\in\mathcal{A}}\tilde{w}_{a}\left\lparen
W_{2}^{2}(\tilde{p}_{a},q^{*}_{a})-W_{2}^{2}(p^{*}_{a},q^{*}_{a})+2W_{2}(p^{*}_{a},q^{*}_{a})W_{2}(p^{*}_{a},r^{*}_{a})\right\rparen+\mathcal{E}_{1}+\mathcal{E}_{2}+\frac{3}{k}$
(177) $\displaystyle\leq\sum_{a\in\mathcal{A}}\tilde{w}_{a}\left\lparen
W_{2}^{2}(\tilde{p}_{a},q^{*}_{a})-W_{2}^{2}(p^{*}_{a},q^{*}_{a})\right\rparen+\frac{1}{k}+\mathcal{E}_{1}+\mathcal{E}_{2}+\frac{3}{k},$
(178)

where the last line is because $h$ is a transport from $r^{*}_{a}$ to
$p^{*}_{a}$ with displacements of at most $\nicefrac{{1}}{{2k}}$; for the
first term, by Lemmas B.8 and 143,

$\displaystyle\sum_{a\in\mathcal{A}}\tilde{w}_{a}\left\lparen
W_{2}^{2}(\tilde{p}_{a},q^{*}_{a})-W_{2}^{2}(p^{*}_{a},q^{*}_{a})\right\rparen$
(179) $\displaystyle\leq
4\sum_{a\in\mathcal{A}}\tilde{w}_{a}W_{1}(\tilde{p}_{a},p^{*}_{a})$ (180)
$\displaystyle\leq 4\sum_{a\in\mathcal{A}}\tilde{w}_{a}\left\lparen
W_{1}(\tilde{p}_{a},p_{a})+W_{1}(p_{a},r_{a})+W_{1}(r_{a},r^{*}_{a})+W_{1}(r^{*}_{a},p^{*}_{a})\right\rparen$
(181) $\displaystyle\leq
4\sum_{a\in\mathcal{A}}\tilde{w}_{a}\left\lparen\left\|\tilde{p}_{a}-p_{a}\right\|_{1}+\frac{1}{2k}+\operatorname{\mathbb{E}}_{X\sim\mu_{X\mid
a}}\left[\left|f^{*}(X,a)-f(X,a)\right|\right]+\frac{1}{2k}\right\rparen$
(182) $\displaystyle\leq
4\sum_{a\in\mathcal{A}}\tilde{w}_{a}\operatorname{\mathbb{E}}_{X\sim\mu_{X\mid
a}}\left[\left|f^{*}(X,a)-f(X,a)\right|\right]+\mathcal{E}_{2}+\frac{4}{k}$
(183) $\displaystyle\leq 4\sum_{a\in\mathcal{A}}\left\lparen
w_{a}-w_{a}+\tilde{w}_{a}\right\rparen\operatorname{\mathbb{E}}_{X\sim\mu_{X\mid
a}}\left[\left|f^{*}(X,a)-f(X,a)\right|\right]+\mathcal{E}_{2}+\frac{4}{k}$
(184) $\displaystyle\leq
4\sum_{a\in\mathcal{A}}w_{a}\operatorname{\mathbb{E}}_{X\sim\mu_{X\mid
a}}\left[\left|f^{*}(X,a)-f(X,a)\right|\right]+4\sum_{a\in\mathcal{A}}\left|\tilde{w}_{a}-w_{a}\right|+4\mathcal{E}_{2}+\frac{4}{k}$
(185) $\displaystyle\leq 4\mathcal{E}_{1}+\mathcal{E}_{2}+\frac{4}{k},$ (186)

the third inequality is because the joint distribution of
$(f(X,a),f^{*}(X,a))$ is a valid coupling belonging to $\Pi(r_{a},r^{*}_{a})$
that incurs a transportation cost of

$\displaystyle\operatorname{\mathbb{E}}[|f^{*}(X,a)-f(X,a)|]=\int\left|y-y^{*}\right|\mathop{}\\!\mathrm{d}\operatorname{\mathbb{P}}(f(X,a)=y,f^{*}(X,a)=y^{*})\geq
W_{1}(r_{a},r^{*}_{a}).$ (187)

Putting everything together, and with a union bound over the two events above,
gives the result in the theorem statement.

#### Fairness Guarantee.

Let $\bar{p}_{a}$ denote the output distribution of the post-processed
regressor $\bar{f}$ conditioned on group $a$. Using triangle inequality, for
any $a,a^{\prime}\in\mathcal{A}$,

$D_{\textnormal{KS}}(\bar{p}_{a},\bar{p}_{a^{\prime}})\leq
D_{\textnormal{KS}}(\tilde{q}_{a},\tilde{q}_{a^{\prime}})+D_{\textnormal{KS}}(\bar{p}_{a},\tilde{q}_{a})+D_{\textnormal{KS}}(\bar{p}_{a^{\prime}},\tilde{q}_{a^{\prime}})\leq\alpha+D_{\textnormal{KS}}(\bar{p}_{a},\tilde{q}_{a})+D_{\textnormal{KS}}(\bar{p}_{a^{\prime}},\tilde{q}_{a^{\prime}}),$
(188)

where

$\displaystyle D_{\textnormal{KS}}(\bar{p}_{a},\tilde{q}_{a})$
$\displaystyle=\max_{j}\left|\sum_{\ell=1}^{j}\left\lparen\bar{p}_{a}(v_{\ell})-\tilde{q}_{a}(v_{\ell})\right\rparen\right|$
(189)
$\displaystyle=\max_{j}\left|\sum_{\ell=1}^{j}\left\lparen\operatorname{\mathbb{P}}(\bar{f}(X,a)=v_{\ell}\mid
A=a)-\tilde{q}_{a}(\ell)\right\rparen\right|$ (190)
$\displaystyle=\max_{j}\left|\sum_{\ell=1}^{j}\left\lparen\sum_{m=1}^{k}p_{a}(v_{m})\operatorname{\mathbb{P}}(g_{a}(v_{m})=v_{\ell}\mid
A=a)-\sum_{m=1}^{k}\tilde{p}_{a}(v_{m})\operatorname{\mathbb{P}}(g_{a}(v_{m})=v_{\ell}\mid
A=a)\right\rparen\right|$ (191)
$\displaystyle=\max_{j}\left|\sum_{m=1}^{k}\left\lparen
p_{a}(v_{m})-\tilde{p}_{a}(v_{m})\right\rparen\sum_{\ell=1}^{j}\operatorname{\mathbb{P}}(g_{a}(v_{m})=v_{\ell}\mid
A=a)\right|$ (192)
$\displaystyle\leq\max_{j}\left\lparen\left|\sum_{m=1}^{v_{\iota_{j}-1}}\left\lparen
p_{a}(v_{m})-\tilde{p}_{a}(v_{m})\right\rparen\right|+\left|\left\lparen
p_{a}(v_{\iota_{j}})-\tilde{p}_{a}(v_{\iota_{j}})\right\rparen\operatorname{\mathbb{P}}(g_{a}(v_{\iota_{j}})\leq
v_{j})\right|\right\rparen$ (193) $\displaystyle\leq
D_{\textnormal{KS}}(p_{a},\tilde{p}_{a})+\max_{j}\left|p_{a}(v_{\iota_{j}})-\tilde{p}_{a}(v_{\iota_{j}})\right|$
(194) $\displaystyle\leq
O\left\lparen\frac{\sqrt{k}}{nw_{a}\varepsilon}\ln\frac{k|\mathcal{A}|}{\beta}+\sqrt{\frac{k}{nw_{a}}\ln\frac{k|\mathcal{A}|}{\beta}}\right\rparen;$
(195)

line 3 is because $g_{a}$ is a transport from $\tilde{p}_{a}$ to
$\tilde{q}_{a}$, line 5 uses Lemma B.9 and the fact that
$\sum_{\ell=1}^{j}\nicefrac{{\pi_{a}(v_{m},v_{\ell})}}{{\tilde{p}_{a}(v_{m})}}=\operatorname{\mathbb{P}}(g_{a}(v_{m})\leq
v_{j})$, and line 7 is by Theorem 3.2. ∎