# Differentially Private Fair Binary Classifications

Hrad Ghoukasian, Shahab Asoodeh
Department of Computing and Software, McMaster University
{ghoukash<EMAIL_ADDRESS>

###### Abstract

In this work, we investigate binary classification under the constraints of
both differential privacy and fairness. We first propose an algorithm based on
the decoupling technique for learning a classifier with only fairness
guarantee. This algorithm takes in classifiers trained on different
demographic groups and generates a single classifier satisfying statistical
parity. We then refine this algorithm to incorporate differential privacy. The
performance of the final algorithm is rigorously examined in terms of privacy,
fairness, and utility guarantees. Empirical evaluations conducted on the Adult
and Credit Card datasets illustrate that our algorithm outperforms the state-
of-the-art in terms of fairness guarantees, while maintaining the same level
of privacy and utility.

##  I Introduction

Machine learning algorithms are increasingly utilized in high-stake decision-
making processes, highlighting the need to thoroughly assess their
trustworthiness. Two main topics in the context of trustworthy machine
learning are privacy and fairness. Machine learning models are required to, on
the one hand, protect the privacy of individuals in the training datasets, and
on the other hand, avoid leading to discrimination against any demographic
subgroups. Differential privacy (DP) [1, 2] is the de-facto standard for
privacy-preserving machine learning algorithms deployed in practice (e.g., [3,
4, 5, 6]). Informally speaking, a randomized algorithm is differentially
private if its output distribution does not significantly change by changing
an entry in the dataset (yielding a pair of neighboring datasets). However,
unlike privacy, there is no universal definition of fairness. Therefore, how
fairness is defined or algorithmically enforced depends on the particular
context of the problem. A widely recognized concept of fairness is statistical
parity [7], also known as demographic parity. This definition implies that
predictions of a classification model should be independent of the sensitive
attributes, e.g., gender or race. While privacy and fairness have been
extensively studied separately in the literature, the intersection of them has
recently gained attention.

In the literature on fair classification algorithms, incorporating sensitive
attributes is known as “fairness through awareness” [8]. While the choice to
use or not use sensitive attributes is specific to each problem, [9]
demonstrated that in scenarios where it is legally and ethically tenable to
use these attributes, training separate classifiers (decoupled classifiers)
for each group can outperform the performance of a single optimal classifier
in terms of both accuracy and fairness (without privacy included). [10] also
showed that employing decoupled classifiers does not negatively impact any
group in terms of average performance metrics in the information-theoretic
regime where the underlying data distribution is known. However, a significant
challenge emerges when considering privacy. It has been empirically
demonstrated that differentially private mechanisms can exacerbate unfairness
[11, 12]. This necessitates the implementation of specific strategies to
mitigate the negative effects of DP on fairness guarantees. Combining the
above idea of decoupled classification with differential privacy, [13]
proposed a “stratification” technique to reduce the disparity in
differentially private mechanisms. This technique involves applying a DP
mechanism separately to different subgroups and then recombining the
respective results to derive overall statistics for the entire dataset. It was
demonstrated that a naive stratification approach can produce highly accurate
estimates for population-level statistics without requiring an extra privacy
budget. Building on this foundation, our pipeline is structured to first apply
DP and subsequently address fairness using a post-processing step. This order
of application is crucial because DP methods introduce random noise into the
process, which can alter the predictions of our model. If the model met
fairness standards before we applied DP, the introduction of this noise could
lead to a situation where those fairness standards are no longer met.

One line of work explores the relationship between DP and different notions of
fairness, examining their compatibility and determining how fairness
deteriorates DP guarantees and vice versa[11, 14, 15, 16, 12, 17, 18]. Another
research direction at the intersection of privacy and fairness centers around
developing classification algorithms that simultaneously guarantee DP and a
specific notion of fairness. Despite these remarkable recent advances, most
such works suffer from inherent limitations. For instance, some of these
methods are tailored only to certain types of classification models, such as
logistic regression, and are not universally applicable to all desired
models[19, 20, 21]. Other studies focus exclusively on providing privacy with
respect to sensitive attributes of individuals in the dataset, neglecting the
privacy of other features. More specifically, some methods ensure that an
individual’s sensitive attributes remain confidential, but they do not provide
the same guarantees for non-sensitive attributes, leaving them potentially
vulnerable to leakage [20, 22, 23, 24]. For instance, [22] introduced two
effective differentially private fair classification algorithms which provide
privacy guarantees only with respect to the sensitive attributes. This was
achieved through the use of randomized response for sensitive attributes. They
used randomized response mechanism (for achieving the local version of DP),
and thus their method does not seem to naturally adapt to provide privacy
guarantees for all features, especially when dealing with continuous and
potentially high-dimensional non-sensitive attributes. Lastly, although most
of these methods have shown practical effectiveness, they often lack
theoretical guarantees regarding utility and the extent of fairness violation
[19, 21, 25, 26, 23, 24, 27, 28, 29]. A summary of the characteristics of
these methods can be found in Table I.

Our objective is to develop a binary classification algorithm with provable DP
and fairness guarantees that addresses the limitations highlighted in Table I.
Inspired by the success of decoupled classifiers and the effectiveness of
stratification in reducing disparate impact in differentially private
mechanisms (as noted in [10, 9, 13]), our approach involves training separate
classifiers for each sub-population. These classifiers then go into a post-
processing step to generate a single classifier. Following the method used in
[30], our goal is to apply a post-processing technique that achieves
statistical parity, ensuring that only minimal changes are made to the
predictions of the original classifiers. We begin by slightly modifying the
approach described in [31], initially developed for non-private settings
(Algorithm 1). Then, we introduce Algorithm 2, a new method for binary
classification that is both differentially private and fair. This new
algorithm comes with theoretical guarantees for utility, fairness, and
differential privacy. More precisely, our contributions are as follows:

  * •

We establish a lower bound for the sum of prediction changes across a pair of
subgroups under statistical parity (without privacy) and propose an algorithm
(based on [31, Algorithm 1]) that attains it (Algorithm 1). Theoretical
guarantee of this algorithm is given in Theorem 2.

  * •

We then propose a differentially private version (Algorithm 2) of Algorithm 1
and derive its theoretical guarantees for fairness and utility —both with high
probability and in expectation— in Theorem 3 and Proposition 4.

  * •

Through several experiments on two well-known datasets (namely, Adult and
Credit Card), we empirically demonstrate that Algorithm 2 achieves competitive
accuracy when compared to the state-of-the-art DP-Fair classification method,
DP-FERMI [28]. In particular, we show that for a given level of accuracy and
privacy, our algorithm provides a significantly better fairness guarantee
across both datasets.

TABLE I: Benchmark methods in DP-Fair classification Reference |  Applicable to any model |  Theoretical guarantee |  Privacy w.r.t. all features
---|---|---|---
[19] |  ✗ |  ✗ |  ✓
[20] (post-proc.) |  ✓ |  ✓ |  ✗
[20] (in-proc.) |  ✗ |  ✓ |  ✓
[21] |  ✗ |  ✗ |  ✓
[22] |  ✓ |  ✓ |  ✗
[25] |  ✓ |  ✗ |  ✓
[26] |  ✓ |  ✗ |  ✓
[23] |  ✓ |  ✗ |  ✗
[24] |  ✓ |  ✗ |  ✗
[27] |  ✓ |  ✗ |  ✓
[28] |  ✓ |  ✗ |  ✓
[29] (FairDPSGD) |  ✓ |  ✗ |  ✓
[29] (FairPATE) |  ✓ |  ✗ |  ✓
This Work |  ✓ |  ✓ |  ✓

##  II Notation and Basic Definitions

We consider a binary classification setting where there is a joint
distribution $\mu$ over the triplet $T=(X,A,Y)$, where
$X\in\mathcal{X}\subset\mathbb{R}^{d}$ is the feature vector of non-sensitive
attributes, $A\in\\{0,1\\}$ is the sensitive attribute, and $Y\in\\{0,1\\}$ is
the target output. We use $\mu(Y)$ to denote the marginal distribution of $Y$
from a joint distribution $\mu$ over $Y$ and some other random variables.
Denote the marginal distribution of input $X$ by $\mu^{X}$. For
$a\in\\{0,1\\}$, we use $\mu_{a}$ to mean the conditional distribution of
$(X,Y)$ conditioned on $A=a$, and $\mu^{X}_{a}$ to mean the marginal
distribution of input $X$ given $A=a$. For any group-aware classifier
$h:\mathcal{X}\times\\{0,1\\}\rightarrow\\{0,1\\}$ and $a\in\\{0,1\\}$, we
also use $h_{a}(\cdot)$ to denote the restriction of $h$ on $A=a$,
respectively, i.e., $h_{a}(\cdot):=h(\cdot,a)$. Finally, the probabilistic
inequality $X\leq_{\eta}Y$ for a pair of random variables $(X,Y)$ denotes the
mathematical statement that $\mathbb{P}(X>Y)\leq\eta$.

We now formally define differential privacy and statistical parity.

######  Definition 1.

(Differential privacy). A randomized mechanism
$M:\mathcal{D}\rightarrow\mathcal{R}$ with domain $\mathcal{D}$ and range
$\mathcal{R}$ is $(\varepsilon,\delta)$-differentially private
($(\varepsilon,\delta)$-DP) if for any pair of neighboring datasets $D$ and
$D^{\prime}$ that differ in exactly one record, and for any subsets of outputs
$S\subseteq\mathcal{R}$, we have,

$\mathbb{P}(M(D)\in S)\leq e^{\varepsilon}\mathbb{P}(M(D^{\prime})\in
S)+\delta.$

######  Definition 2.

(Statistical parity). Given a joint distribution $\mu$, the statistical parity
gap of a binary classifier $\hat{Y}=\hat{h}(X,A)$ with
$\hat{h}:\mathcal{X}\times\\{0,1\\}\rightarrow\\{0,1\\}$ is

$\Delta_{SP}(\hat{h}):=|\mu_{0}(\hat{Y}=1)-\mu_{1}(\hat{Y}=1)|.$

We say that $\hat{Y}=\hat{h}(X,A)$ satisfies $\gamma$-statistical parity if

$\Delta_{SP}(\hat{h})\leq\gamma.$

##  III Main Results

In this section, we develop a framework for designing a binary classification
algorithm with provable DP and fairness guarantees. We begin in Section III-A
by detailing our approach to achieve fairness and the specified utility target
in a non-private setting. Then in Section III-B, we expand this framework to
include DP. Regardless of private or non-private settings, as outlined in
Introduction, our framework involves partitioning the dataset according to
sensitive attributes. We first develop a separate classifier for each
subgroup. We then implement a post-processing technique that carefully
combines those decoupled classifiers in a way to achieve statistical parity,
with the objective of minimally perturbing the original classifiers’
predictions.

We consider two classifiers, $h_{0}^{*}:\mathcal{X}\rightarrow\\{0,1\\}$ and
$h_{1}^{*}:\mathcal{X}\rightarrow\\{0,1\\}$, each trained on subgroups
specified by the sensitive attribute $A$ with values 0 and 1, respectively.
These classifiers are designed to maximize accuracy without initially
considering fairness constraints. In a non-private setting, $h_{0}^{*}$ and
$h_{1}^{*}$ are standard classifiers, whereas in private settings, they are
considered classifiers learned by DP guarantees. Our post-processing method
aims to derive a fair classifier
$\hat{h}:\mathcal{X}\times\\{0,1\\}\rightarrow\\{0,1\\}$ from $h_{0}^{*}$ and
$h_{1}^{*}$. Following the methodology of [30], our objective is to achieve
this goal by minimally perturbing the predictions of the original classifiers.
We thus seek fair $\hat{h}$ that optimizes the utility measured in terms of
the sum $\mathbb{P}_{\mu^{X}_{0}}(\hat{h}_{0}(X)\neq
h^{*}_{0}(X))+\mathbb{P}_{\mu^{X}_{1}}(\hat{h}_{1}(X)\neq h^{*}_{1}(X))$. The
reason for adopting the prediction changes over $\mu^{X}_{0}$ and
$\mu^{X}_{1}$ (as opposed to the combined distribution $\mu^{X}$) is as
follows: when the demographic subgroups are imbalanced in the overall
population, relying only on prediction changes across the combined
distribution $\mu^{X}$ can be misleading. This approach may hide significant
prediction shifts of the less-represented group, which would be more apparent
if we examined the sum of the prediction changes within each subgroup’s
distribution ($\mu_{0}^{X}$ and $\mu_{1}^{X}$). In other words, it might be
possible to have small overall prediction changes across the combined
distribution $\mu^{X}$ while minority groups are experiencing substantial
changes in their predictions [31].

In Section III-A, we explore the non-private scenario, discussing Algorithm 1
that ensures statistical parity and optimal utility. In Section III-B, we
extend the algorithm to take privacy into consideration. In particular, we
propose Algorithm 2, which outputs a classifier that guarantees DP and
achieves statistical parity while maintaining minimal changes in the
predictions of the original classifiers, both in expectation and with high
probability. To discuss our utility metric under the constraint of statistical
parity, we rely on the following proposition.

######  Proposition 1.

Let $h_{0}^{*}:\mathcal{X}\rightarrow\\{0,1\\}$ and
$h_{1}^{*}:\mathcal{X}\rightarrow\\{0,1\\}$, be arbitrary classifiers trained
on subgroups specified by the sensitive attribute $A=0$ and $A=1$,
respectively. If a predictor $\hat{Y}=\hat{h}(X,A)$ satisfies
$\gamma$-statistical parity, then

$\begin{split}\mathbb{P}_{\mu^{X}_{0}}(\hat{h}_{0}(X)\neq
h^{*}_{0}(X))+\mathbb{P}_{\mu^{X}_{1}}(\hat{h}_{1}(X)\neq
h^{*}_{1}(X))\geq\left|\mathbb{P}_{\mu^{X}_{0}}(h^{*}_{0}(X)=1)-\mathbb{P}_{\mu^{X}_{1}}(h^{*}_{1}(X)=1)\right|-\gamma.\end{split}$

###  III-A Fair Post-Processing Without Privacy

Let $h_{0}^{*}:\mathcal{X}\rightarrow\\{0,1\\}$ and
$h_{1}^{*}:\mathcal{X}\rightarrow\\{0,1\\}$ be decoupled classifiers, that is
they are trained on subgroups associated with the sensitive attribute $A=0$
and $A=1$, respectively. $h_{0}^{*}$ and $h_{1}^{*}$ can be any arbitrary
classifiers. In the context of our analysis, they can be considered as the
best available classifiers trained on $\mu_{0}$ and $\mu_{1}$. Our goal is to
develop an optimal fair classifier
$\hat{h}:\mathcal{X}\times\\{0,1\\}\rightarrow\\{0,1\\}$ using $h_{0}^{*}$ and
$h_{1}^{*}$. More precisely, we seek $\hat{h}$ that satisfies
$\Delta_{SP}(\hat{h})=0$ while attaining the lower bound in Proposition 1 for
$\gamma=0$:

$\begin{split}\mathbb{P}_{\mu^{X}_{0}}(\hat{h}_{0}(X)\neq
h^{*}_{0}(X))+\mathbb{P}_{\mu^{X}_{1}}(\hat{h}_{1}(X)\neq
h^{*}_{1}(X))=\left|\mathbb{P}_{\mu^{X}_{0}}(h^{*}_{0}(X)=1)-\mathbb{P}_{\mu^{X}_{1}}(h^{*}_{1}(X)=1)\right|.\end{split}$

We present Algorithm 1 to address this objective. This algorithm, which is a
slightly modified version of the algorithm in [31], constructs the fair
classifier $h^{*}_{\text{Fair}}$. The original algorithm in [31] builds a fair
optimal classifier assuming oracle access to the Bayes optimal classifiers
$h_{0}^{*}$ and $h_{1}^{*}$. Our ultimate goal, to be discussed in the next
section with Algorithm 2, is to identify a classifier that is both private and
fair. However, the assumption of having access to Bayes optimal classifiers is
not practical in DP settings, primarily due to the necessity of introducing
noise. Consequently, in Algorithm 1, $h_{0}^{*}$ and $h_{1}^{*}$ are
considered to be any arbitrary classifiers trained on subgroups specified by
the sensitive attribute $A=0$ and $A=1$ (not necessarily the Bayes optimal
classifiers).

Algorithm 1 Optimal Fair Binary Classifier

1:Input: Classifiers $h_{0}^{*}$ and $h_{1}^{*}$

2:Output: A randomized classifier
$h^{*}_{\text{Fair}}:\mathcal{X}\times\\{0,1\\}\rightarrow\\{0,1\\}$

3:Compute $\alpha=\mathbb{P}_{\mu^{X}_{0}}(h^{*}_{0}(X)=1)$ and
$\beta=\mathbb{P}_{\mu^{X}_{1}}(h^{*}_{1}(X)=1)$. W.L.O.G. assume
$\alpha\geq\beta$

4:For $(x,a)$, randomly sample $s$ from the uniform distribution $U(0,1)$

5:Construct $h^{*}_{\text{Fair}}$ as follows:

6:$h_{\text{Fair }}^{*}(x,a):=\begin{cases}a=0:&\begin{cases}0&\text{if
}h_{0}^{*}(x)=0\text{ or }h_{0}^{*}(x)=1\text{ and
}s>\frac{\alpha+\beta}{2\alpha}\\\ 1&\text{if }h_{0}^{*}(x)=1\text{ and
}s\leq\frac{\alpha+\beta}{2\alpha}\end{cases}\\\ a=1:&\begin{cases}0&\text{if
}h_{1}^{*}(x)=0\text{ and }s>\frac{\alpha-\beta}{2(1-\beta)}\\\ 1&\text{if
}h_{1}^{*}(x)=1\text{ or }h_{1}^{*}(x)=0\text{ and
}s\leq\frac{\alpha-\beta}{2(1-\beta)}\end{cases}\end{cases}$

7:return $h^{*}_{\text{Fair}}$

######  Theorem 2.

The classifier $h^{*}_{\text{Fair}}$ constructed by Algorithm 1 satisfies
perfect statistical parity ($\Delta_{SP}(h^{*}_{\text{Fair}})=0$) and is
optimal in terms of the sum of prediction changes compared to classifiers
$h_{0}^{*}$ and $h_{1}^{*}$, that is

$\begin{split}\mathbb{P}_{\mu^{X}_{0}}({h^{*}_{\text{Fair}}}_{0}(X)\neq
h^{*}_{0}(X))+\mathbb{P}_{\mu^{X}_{1}}({h^{*}_{\text{Fair}}}_{1}(X)\neq
h^{*}_{1}(X))=\left|\mathbb{P}_{\mu^{X}_{0}}(h^{*}_{0}(X)=1)-\mathbb{P}_{\mu^{X}_{1}}(h^{*}_{1}(X)=1)\right|.\end{split}$

###  III-B Fair Post-Processing With Privacy

Next, we delve into a private version of Algorithm 1. It is worth noting that
achieving $(\varepsilon,0)$-DP is incompatible with non-trivial guarantees of
fairness and utility (see, e.g., [14, 18] for more details). As a result, our
objective is to design an $(\varepsilon,\delta)$-DP version of Algorithm 1
with comparable fairness and utility guarantees, provided that $\delta>0$.

First, notice that this goal is not feasible just by replacing the input
classifiers $h_{0}^{*}$ and $h_{1}^{*}$ with some differentially private
decoupled classifiers $h^{*}_{\varepsilon_{0},\delta_{0}}$ and
$h^{*}_{\varepsilon_{1},\delta_{1}}$. These classifiers can be learned by
applying an existing differentially private learning method —most notably,
differentially private stochastic gradient descent (DP-SGD) [32]— to each
demographic subgroup. This is because Algorithm 1 involves some computations
over the dataset (e.g., in computing $\alpha$ and $\beta$ in line 1). This
therefore necessitates some changes in Algorithm 1 for constructing its
differentially private version. Thus, our goal can be formulated as follows:
Given decoupled classifiers $h^{*}_{\varepsilon_{0},\delta_{0}}$ and
$h^{*}_{\varepsilon_{1},\delta_{1}}$, that are
$(\varepsilon_{0},\delta_{0})$-DP and $(\varepsilon_{1},\delta_{1})$-DP,
respectively, we wish to generate a fair classifier
$h^{*}_{\varepsilon,\delta,\text{Fair}}$ with the following properties:

  1. 1.

$h^{*}_{\varepsilon,\delta,\text{Fair}}$ is $(\varepsilon,\delta)$-DP with
some $\varepsilon$ and $\delta$ (depending on
$\varepsilon_{0},\varepsilon_{1},\delta_{0}$, and $\delta_{1}$),

  2. 2.

$h^{*}_{\varepsilon,\delta,\text{Fair}}$ satisfies $\gamma$-statistical parity
with $\gamma$ being a positive value close to zero with high probability and
in expectation,

  3. 3.

Among all classifiers satisfying the same level of statistical parity gap as
$h^{*}_{\varepsilon,\delta,\text{Fair}}$, the classifier
$h^{*}_{\varepsilon,\delta,\text{Fair}}$ performs comparably with the optimal
classifier in terms of utility, both with high probability and in expectation.
Optimality here is defined based on minimizing the total number of prediction
changes across the distributions $\mu_{0}^{X}$ and $\mu_{1}^{X}$, relative to
the predictions made by $h^{*}_{\varepsilon_{0},\delta_{0}}$ and
$h^{*}_{\varepsilon_{1},\delta_{1}}$.

To this goal, we present Algorithm 2 for learning such
$h^{*}_{\varepsilon,\delta,\text{Fair}}$. Recall that Algorithm 1 requires
estimates of the proportions of data points in each subgroup classified as
label one (denoted by $\alpha$ and $\beta$). Algorithm 2 is designed to
privately estimate these quantities using the Laplace mechanism, whose privacy
guarantee is well-understood. The following theorem delineates the performance
of Algorithm 2 in terms of its achievable privacy and fairness guarantees as
well as bounds on its utility.

Algorithm 2 Private and Fair Binary Classifier with Utility Gap Guarantee

1:Input: Classifiers $h_{\varepsilon_{0},\delta_{0}}^{*}$ and
$h_{\varepsilon_{1},\delta_{1}}^{*}$, datasets
$D_{0}=(X_{i},A_{i}=0,Y_{i})_{i=1}^{n_{0}}$ and
$D_{1}=(X_{j},A_{j}=1,Y_{j})_{j=1}^{n_{1}}$,

2:privacy parameters $\varepsilon_{2}$, and $\varepsilon_{3}$

3:Output: Classifier
$h^{*}_{\varepsilon,\delta,\text{Fair}}:\mathcal{X}\times\\{0,1\\}\rightarrow\\{0,1\\}$
with $\varepsilon=\sum_{i=0}^{3}\varepsilon_{i}$ and
$\delta=\delta_{0}+\delta_{1}$

4:Compute
$\bar{\alpha}=\frac{1}{n_{0}}\sum_{i=1}^{n_{0}}h_{\varepsilon_{0},\delta_{0}}^{*}(X_{i})$
and
$\bar{\beta}=\frac{1}{n_{1}}\sum_{j=1}^{n_{1}}h_{\varepsilon_{1},\delta_{1}}^{*}(X_{j})$

5:Add noise to $\bar{\alpha}$ and $\bar{\beta}$:

6:Sample $l_{0}$ from $\text{Lap}\big{(}\frac{1}{n_{0}\varepsilon_{2}}\big{)}$
and $l_{1}$ from $\text{Lap}\big{(}\frac{1}{n_{1}\varepsilon_{3}}\big{)}$.
Define $\tilde{\alpha}=\left[\bar{\alpha}+l_{0}\right]_{0}^{1}$ and
$\tilde{\beta}=\left[\bar{\beta}+l_{1}\right]_{0}^{1}$, where
$\left[\cdot\right]_{0}^{1}$ denotes the projection onto $[0,1]$.

7:For $(x,a)$, randomly sample $s$ from the uniform distribution $U(0,1)$

8:Construct $h^{*}_{\varepsilon,\delta,\text{Fair}}$ as follows:

9:if $\tilde{\alpha}\geq\tilde{\beta}$, then

10:
$h^{*}_{\varepsilon,\delta,\text{Fair}}(x,a):=\begin{cases}\mathds{1}[h_{\varepsilon_{0},\delta_{0}}^{*}(x)=1]\mathds{1}[s\leq\frac{\tilde{\alpha}+\tilde{\beta}}{2\tilde{\alpha}}]&\text{if
}a=0\\\
\mathds{1}[h_{\varepsilon_{1},\delta_{1}}^{*}(x)=0]\mathds{1}[s\leq\frac{\tilde{\alpha}-\tilde{\beta}}{2(1-\tilde{\beta})}]+\mathds{1}[h_{\varepsilon_{1},\delta_{1}}^{*}(x)=1]&\text{if
}a=1\end{cases}$

11:if $\tilde{\alpha}<\tilde{\beta}$, then

12:
$h^{*}_{\varepsilon,\delta,\text{Fair}}(x,a):=\begin{cases}\mathds{1}[h_{\varepsilon_{1},\delta_{1}}^{*}(x)=1]\mathds{1}[s\leq\frac{\tilde{\alpha}+\tilde{\beta}}{2\tilde{\beta}}]&\text{if
}a=1\\\
\mathds{1}[h_{\varepsilon_{0},\delta_{0}}^{*}(x)=0]\mathds{1}[s\leq\frac{\tilde{\beta}-\tilde{\alpha}}{2(1-\tilde{\alpha})}]+\mathds{1}[h_{\varepsilon_{0},\delta_{0}}^{*}(x)=1]&\text{if
}a=0\end{cases}$

13:return $h^{*}_{\varepsilon,\delta,\text{Fair}}$

######  Theorem 3.

The classifier
$h^{*}_{\varepsilon,\delta,\text{Fair}}:\mathcal{X}\times\\{0,1\\}\rightarrow\\{0,1\\}$
constructed by Algorithm 2 satisfies the following three properties:

  * •

(Privacy guarantee) $h^{*}_{\varepsilon,\delta,\text{Fair}}$ satisfies
$(\varepsilon,\delta)$-DP with $\varepsilon=\sum_{i=0}^{3}\varepsilon_{i}$ and
$\delta=\delta_{0}+\delta_{1}$,

  * •

(Fairness guarantee) We have:

$\Delta_{SP}(h^{*}_{\varepsilon,\delta,\text{Fair}})\leq_{\eta_{0}+\eta_{1}}\frac{\log(1/\eta_{0})}{n_{0}\varepsilon_{2}}+\frac{\log(1/\eta_{1})}{n_{1}\varepsilon_{3}},$

  * •

(Utility guarantee) Let
$\text{err}^{*}(h^{*}_{\varepsilon_{0},\delta_{0}},h^{*}_{\varepsilon_{1},\delta_{1}})$
be defined as:

$\begin{split}\min_{\begin{subarray}{c}\hat{h}:\mathcal{X}\times\\{0,1\\}\rightarrow\\{0,1\\}\\\
\Delta_{SP}(\hat{h})\leq\Delta_{SP}(h^{*}_{\varepsilon,\delta,\text{Fair}})\end{subarray}}\biggl{[}\mathbb{P}_{\mu^{X}_{0}}(\hat{h}_{0}(X)\neq
h^{*}_{\varepsilon_{0},\delta_{0}}(X))+\mathbb{P}_{\mu^{X}_{1}}(\hat{h}_{1}(X)\neq
h^{*}_{\varepsilon_{1},\delta_{1}}(X))\biggr{]}.\end{split}$ (1)

Then, we have:

$\begin{split}\mathbb{P}_{\mu^{X}_{0}}({h^{*}_{\varepsilon,\delta,\text{Fair}}}_{0}(X)\neq
h^{*}_{\varepsilon_{0},\delta_{0}}(X))&+\mathbb{P}_{\mu^{X}_{1}}({h^{*}_{\varepsilon,\delta,\text{Fair}}}_{1}(X)\neq
h^{*}_{\varepsilon_{1},\delta_{1}}(X))\\\
&\leq_{\eta_{0}+\eta_{1}}\text{err}^{*}(h^{*}_{\varepsilon_{0},\delta_{0}},h^{*}_{\varepsilon_{1},\delta_{1}})+\frac{5}{2}\Big{(}\frac{\log(1/\eta_{0})}{n_{0}\varepsilon_{2}}+\frac{\log(1/\eta_{1})}{n_{1}\varepsilon_{3}}\Big{)}.\end{split}$

The privacy guarantee of $h^{*}_{\varepsilon,\delta,\text{Fair}}$ has two
components: the privacy guarantees of the input classifiers and the Laplace
mechanism employed to privately estimate $\bar{\alpha}$ and $\bar{\beta}$
(line 2 in Algorithm 2). Thus, the privacy guarantee in the above theorem
follows directly from a composition result (e.g., basic composition [33]).
However, the analysis pertaining to fairness and utility guarantees is rather
long and thus deferred to the appendix. The fairness guarantee demonstrates,
as expected, that perfect statistical parity can no longer be achievable when
requiring privacy as well. Nevertheless, the theorem shows that
$h^{*}_{\varepsilon,\delta,\text{Fair}}$ satisfies $\gamma$-statistical parity
where $\gamma>0$ is a small constant provided that $n_{0}$ and $n_{1}$ are
sufficiently large (compared to $1/\varepsilon_{2}$ and $1/\varepsilon_{3}$).
We remark that the assumption of large $n_{0}$ and $n_{1}$ was implicitly made
in [31], in which they ignored the error in estimating the proportion of label
one in each subgroup. Finally, the utility guarantee presented in the theorem
indicates that the necessary perturbations in the final prediction by
$h^{*}_{\varepsilon,\delta,\text{Fair}}$ is almost identical to what is
expected by the optimal classifier having the same level of statistical
parity.

Rather than aiming to achieve a small statistical parity gap and a small
utility gap with high probability, we could alternatively focus on the average
guarantees for fairness and utility, as expounded by the next result.

######  Proposition 4.

The classifier
$h^{*}_{\varepsilon,\delta,\text{Fair}}:\mathcal{X}\times\\{0,1\\}\rightarrow\\{0,1\\}$
constructed by Algorithm 2 satisfies the following two properties:

  * •

(Fairness guarantee)
$\mathbb{E}\big{[}\Delta_{SP}(h^{*}_{\varepsilon,\delta,\text{Fair}})\big{]}\leq\frac{1}{n_{0}\varepsilon_{2}}+\frac{1}{n_{1}\varepsilon_{3}},$

  * •

(Utility guarantee) We have

$\begin{split}\mathbb{E}\Bigl{[}\mathbb{P}_{\mu^{X}_{0}}({h^{*}_{\varepsilon,\delta,\text{Fair}}}_{0}(X)\neq
h^{*}_{\varepsilon_{0},\delta_{0}}(X))&+\mathbb{P}_{\mu^{X}_{1}}({h^{*}_{\varepsilon,\delta,\text{Fair}}}_{1}(X)\neq
h^{*}_{\varepsilon_{1},\delta_{1}}(X))\Bigr{]}\leq\mathbb{E}\bigl{[}\text{err}^{*}(h^{*}_{\varepsilon_{0},\delta_{0}},h^{*}_{\varepsilon_{1},\delta_{1}})\bigr{]}+\frac{5}{2}\Big{(}\frac{1}{n_{0}\varepsilon_{2}}+\frac{1}{n_{1}\varepsilon_{3}}\Big{)},\end{split}$

where $\text{err}^{*}(\cdot,\cdot)$ was defined in (1).

##  IV Experiments

In this section, we seek to empirically compare Algorithm 2 with the current
state-of-the-art differentially private fair classifier, namely, DP-FERMI
[28]. To this goal, we focus on two benchmark datasets from the UCI machine
learning repository [34]: the Adult and Credit Card datasets, both with binary
sensitive attributes and target labels.

In our experiments, we assessed two privacy configurations:
$(\varepsilon=3,\delta=10^{-5})$ and $(\varepsilon=9,\delta=10^{-5})$. When
applying Algorithm 2 to the Adult and Credit Card datasets, we set
$\varepsilon_{2}=\varepsilon_{3}=0.05$ and
$\varepsilon_{2}=\varepsilon_{3}=0.1$, respectively. We then feed Algorithm 2
with the decoupled classifiers, $h_{\varepsilon_{0},\delta_{0}}^{*}$ and
$h_{\varepsilon_{1},\delta_{1}}^{*}$ with parameters
$(\varepsilon_{0},\delta_{0})$ and $(\varepsilon_{1},\delta_{1})$ chosen in a
way as to satisfy $\varepsilon=\sum_{i=0}^{3}\varepsilon_{i}$ and
$\delta=\delta_{0}+\delta_{1}$ for each specified $(\varepsilon,\delta)$ pair.
We trained these classifiers via DP-SGD. The training was conducted using
Opacus [35], an open-source PyTorch library designed for training deep
learning models with differential privacy. Accordingly, we chose the standard
deviations of Gaussian noise in DP-SGD to be $4.17$ and $2$ for the Adult
dataset, and to $5.92$ and $3.31$ for the Credit Card dataset, in order to
achieve their respective privacy parameters $(\varepsilon=3,\delta=10^{-5})$
and $(\varepsilon=9,\delta=10^{-5})$. Across all experiments of DP-SGD, we
consistently applied a clipping constant of $2$ and a learning rate of $0.01$.
To achieve the most precise computation of privacy parameters, we utilized the
PRV accountant [36], the state-of-the-art accounting method, to determine the
values for $(\varepsilon_{0},\delta_{0})$ and $(\varepsilon_{1},\delta_{1})$
for the classifiers $h_{\varepsilon_{0},\delta_{0}}^{*}$ and
$h_{\varepsilon_{1},\delta_{1}}^{*}$. Additionally, to evaluate the variance
in accounting methodologies, we conducted privacy parameter computations using
two alternative methods: moments accountant method [32] and GDP accountant
[37, 38], as detailed in the appendix.

For comparability with DP-FERMI, we employed logistic regression models. DP-
FERMI utilizes a loss function with a regularization constant $\lambda$ to
limit statistical parity violations. A higher $\lambda$ imposes stricter
penalties for fairness violations, often at the cost of reduced accuracy. DP-
FERMI sets the desired $\varepsilon$ and $\delta$, and determines the
necessary noise levels to achieve these privacy guarantees. All models,
including Algorithm 2 and DP-FERMI, were trained for 50 epochs, except the
Credit Card models using $(\varepsilon=9,\delta=10^{-5})$ parameters, which
were trained for 100 epochs. Within DP-FERMI, learning rates were set at
$\eta_{\theta}=0.005$ and $\eta_{W}=0.01$. We chose these parameters mainly
because they were empirically shown in [28] to be optimal for the datasets
under consideration. A uniform batch size of 1024 was maintained for all
experiments.

While our theoretical framework focuses on the sum of prediction changes
across subgroup distributions, for comparison purposes with DP-FERMI, we used
overall accuracy as a utility metric. The final results are presented in
Tables III, III, V, and V. All of the results are averages over 10 trials. We
remark that DP-FERMI offers two privacy options: one for sensitive attributes
and another for all features. We used noise parameters for all-feature privacy
in DP-FERMI to compare fairly with Algorithm 2.

TABLE II: Adult Dataset ($\varepsilon=3,\delta=10^{-5}$) - PRV Accountant Method |  Accuracy |  Statistical Parity Gap
---|---|---
Algorithm 2 |  0.7766 |  0.0089
DP-FERMI ($\lambda=0.5$) |  0.7998 |  0.1020
DP-FERMI ($\lambda=1$) |  0.7859 |  0.0462
DP-FERMI ($\lambda=1.5$) |  0.7822 |  0.0267
DP-FERMI ($\lambda=1.8$) |  0.7770 |  0.0182
DP-FERMI ($\lambda=2.5$) |  0.7673 |  0.0099

TABLE III: Adult Dataset ($\varepsilon=9,\delta=10^{-5}$) - PRV Accountant Method |  Accuracy |  Statistical Parity Gap
---|---|---
Algorithm 2 |  0.7782 |  0.0095
DP-FERMI ($\lambda=0.5$) |  0.8091 |  0.0944
DP-FERMI ($\lambda=1$) |  0.7923 |  0.0413
DP-FERMI ($\lambda=1.5$) |  0.7810 |  0.0152
DP-FERMI ($\lambda=1.7$) |  0.7785 |  0.0130
DP-FERMI ($\lambda=2.5$) |  0.7693 |  0.0030

TABLE IV: Credit Card Dataset ($\varepsilon=3,\delta=10^{-5}$) - PRV Accountant Method |  Accuracy |  Statistical Parity Gap
---|---|---
Algorithm 2 |  0.7893 |  0.0093
DP-FERMI ($\lambda=0.1$) |  0.7899 |  0.0212
DP-FERMI ($\lambda=0.25$) |  0.7826 |  0.0195
DP-FERMI ($\lambda=0.5$) |  0.7777 |  0.0185
DP-FERMI ($\lambda=1$) |  0.7759 |  0.0105
DP-FERMI ($\lambda=2.5$) |  0.7669 |  0.0110

TABLE V: Credit Card Dataset ($\varepsilon=9,\delta=10^{-5}$) - PRV Accountant Method |  Accuracy |  Statistical Parity Gap
---|---|---
Algorithm 2 |  0.7969 |  0.0046
DP-FERMI ($\lambda=0.25$) |  0.7996 |  0.0188
DP-FERMI ($\lambda=0.3$) |  0.7971 |  0.0182
DP-FERMI ($\lambda=0.5$) |  0.7912 |  0.0172
DP-FERMI ($\lambda=1$) |  0.7895 |  0.0105
DP-FERMI ($\lambda=2.5$) |  0.7884 |  0.0066

In the Adult dataset, as shown in Table III, Algorithm 2 achieves accuracy
0.7766. Setting $\lambda$ at 1.8, DP-FERMI achieves a comparable accuracy
(0.7770) but exhibits a statistical parity gap twice as large as Algorithm 2’s
guarantee. Table III illustrates that Algorithm 2 and DP-FERMI with
$\lambda=1.7$ achieve a similar accuracy, yet Algorithm 2 exhibits a smaller
statistical parity gap (0.0095) compared to DP-FERMI (0.0130). Altogether,
these tables empirically underscore that applying Algorithm 2 to the Adult
dataset results in a better fairness guarantee while maintaining similar
privacy and accuracy guarantees.

Similar trends are observed in the Credit Card dataset. Table V displays
Algorithm 2 achieving an accuracy of 0.7893, closely matched by DP-FERMI with
an accuracy of 0.7899 at $\lambda=0.1$. However, the statistical parity gap of
Algorithm 2 is less than half that of DP-FERMI (0.0093 compared to 0.0212). As
shown in Table V, Algorithm 2 and DP-FERMI with $\lambda=0.3$ attain similar
accuracy, yet Algorithm 2 exhibits a statistical parity gap of 0.0046, nearly
a fourth of DP-FERMI’s 0.0182. We provide comprehensive descriptions of the
datasets, training processes, and additional results in Appendix B.

## References

  * [1] Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith.  Calibrating noise to sensitivity in private data analysis.  In Theory of Cryptography: Third Theory of Cryptography Conference, TCC 2006, New York, NY, USA, March 4-7, 2006. Proceedings 3, pages 265–284. Springer, 2006.
  * [2] Cynthia Dwork.  Differential privacy.  In International colloquium on automata, languages, and programming, pages 1–12. Springer, 2006.
  * [3] Úlfar Erlingsson, Vasyl Pihur, and Aleksandra Korolova.  Rappor: Randomized aggregatable privacy-preserving ordinal response.  In Proceedings of the 2014 ACM SIGSAC conference on computer and communications security, pages 1054–1067. ACM, 2014.
  * [4] Differential privacy team Apple.  Learning with privacy at scale, 2017.
  * [5] Daniel Kifer, Solomon Messing, Aaron Roth, Abhradeep Thakurta, and Danfeng Zhang.  Guidelines for implementing and auditing differentially private systems.  ArXiv, abs/2002.04049, 2020.
  * [6] Ryan Rogers, Subbu Subramaniam, Sean Peng, David Durfee, Seunghyun Lee, Santosh Kumar Kancha, Shraddha Sahay, and Parvez Ahammad.  Linkedin’s audience engagements api: A privacy preserving data analytics system at scale.  arXiv preprint arXiv:2002.05839, 2020.
  * [7] Michael Feldman, Sorelle A Friedler, John Moeller, Carlos Scheidegger, and Suresh Venkatasubramanian.  Certifying and removing disparate impact.  In proceedings of the 21th ACM SIGKDD international conference on knowledge discovery and data mining, pages 259–268, 2015.
  * [8] 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, pages 214–226, 2012.
  * [9] Cynthia Dwork, Nicole Immorlica, Adam Tauman Kalai, and Max Leiserson.  Decoupled classifiers for group-fair and efficient machine learning.  In Conference on fairness, accountability and transparency, pages 119–133. PMLR, 2018.
  * [10] Hao Wang, Hsiang Hsu, Mario Diaz, and Flavio P Calmon.  To split or not to split: The impact of disparate treatment in classification.  IEEE Transactions on Information Theory, 67(10):6733–6757, 2021.
  * [11] Eugene Bagdasaryan, Omid Poursaeed, and Vitaly Shmatikov.  Differential privacy has disparate impact on model accuracy.  Advances in neural information processing systems, 32, 2019.
  * [12] David Pujol, Ryan McKenna, Satya Kuppam, Michael Hay, Ashwin Machanavajjhala, and Gerome Miklau.  Fair decision making using privacy-protected data.  In Proceedings of the 2020 Conference on Fairness, Accountability, and Transparency, pages 189–199, 2020.
  * [13] Lucas Rosenblatt, Julia Stoyanovich, and Christopher Musco.  A simple and practical method for reducing the disparate impact of differential privacy.  arXiv preprint arXiv:2312.11712, 2023.
  * [14] 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, pages 309–315, 2019.
  * [15] Paul Mangold, Michaël Perrot, Aurélien Bellet, and Marc Tommasi.  Differential privacy has bounded impact on fairness in classification.  In International Conference on Machine Learning, pages 23681–23705. PMLR, 2023.
  * [16] Hongyan Chang and Reza Shokri.  On the privacy risks of algorithmic fairness.  In 2021 IEEE European Symposium on Security and Privacy (EuroS&P), pages 292–303. IEEE, 2021.
  * [17] Tom Farrand, Fatemehsadat Mireshghallah, Sahib Singh, and Andrew Trask.  Neither private nor fair: Impact of data imbalance on utility and fairness in differential privacy.  In Proceedings of the 2020 workshop on privacy-preserving machine learning in practice, pages 15–19, 2020.
  * [18] Sushant Agarwal.  Trade-offs between fairness, interpretability, and privacy in machine learning.  UWSpace, 2020.  http://hdl.handle.net/10012/15861.
  * [19] 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, pages 594–599, 2019.
  * [20] Matthew Jagielski, Michael Kearns, Jieming Mao, Alina Oprea, Aaron Roth, Saeed Sharifi-Malvajerdi, and Jonathan Ullman.  Differentially private fair learning.  In International Conference on Machine Learning, pages 3000–3008. PMLR, 2019.
  * [21] Jiahao Ding, Xinyue Zhang, Xiaohuan Li, Junyi Wang, Rong Yu, and Miao Pan.  Differentially private and fair classification via calibrated functional mechanism.  In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pages 622–629, 2020.
  * [22] Hussein Mozannar, Mesrob Ohannessian, and Nathan Srebro.  Fair learning with private demographic data.  In International Conference on Machine Learning, pages 7066–7075. PMLR, 2020.
  * [23] Cuong Tran, Ferdinando Fioretto, and Pascal Van Hentenryck.  Differentially private and fair deep learning: A lagrangian dual approach.  In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pages 9932–9939, 2021.
  * [24] Cuong Tran, Keyu Zhu, Ferdinando Fioretto, and Pascal Van Hentenryck.  Sf-pate: scalable, fair, and private aggregation of teacher ensembles.  arXiv preprint arXiv:2204.05157, 2022.
  * [25] Depeng Xu, Wei Du, and Xintao Wu.  Removing disparate impact on model accuracy in differentially private stochastic gradient descent.  In Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining, pages 1924–1932, 2021.
  * [26] Cuong Tran, My Dinh, and Ferdinando Fioretto.  Differentially private empirical risk minimization under the fairness lens.  Advances in Neural Information Processing Systems, 34:27555–27565, 2021.
  * [27] M. S. Esipova, A. A. Ghomi, Y. Luo, and J. C. Cresswell.  Disparate impact in differential privacy from gradient misalignment.  In The Eleventh International Conference on Learning Representations, 2023.
  * [28] Andrew Lowy, Devansh Gupta, and Meisam Razaviyayn.  Stochastic differentially private and fair learning.  In International Conference on Learning Representations, 2023.
  * [29] Mohammad Yaghini, Patty Liu, Franziska Boenisch, and Nicolas Papernot.  Learning with impartiality to walk on the pareto frontier of fairness, privacy, and utility.  arXiv preprint arXiv:2302.09183, 2023.
  * [30] Ray Jiang, Aldo Pacchiano, Tom Stepleton, Heinrich Jiang, and Silvia Chiappa.  Wasserstein fair classification.  In Uncertainty in artificial intelligence, pages 862–872. PMLR, 2020.
  * [31] Han Zhao and Geoffrey J Gordon.  Inherent tradeoffs in learning fair representations.  The Journal of Machine Learning Research, 23(1):2527–2552, 2022.
  * [32] Martin 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, pages 308–318, 2016.
  * [33] Cynthia Dwork, Aaron Roth, et al.  The algorithmic foundations of differential privacy.  Foundations and Trends® in Theoretical Computer Science, 9(3–4):211–407, 2014.
  * [34] M. Lichman.  Uci machine learning repository, 2013.
  * [35] Ashkan Yousefpour, Igor Shilov, Alexandre Sablayrolles, Davide Testuggine, Karthik Prasad, Mani Malek, John Nguyen, Sayan Ghosh, Akash Bharadwaj, Jessica Zhao, Graham Cormode, and Ilya Mironov.  Opacus: User-friendly differential privacy library in pytorch.  2021\.
  * [36] Sivakanth Gopi, Yin Tat Lee, and Lukas Wutschitz.  Numerical composition of differential privacy.  Advances in Neural Information Processing Systems, 34:11631–11642, 2021.
  * [37] Jinshuo Dong, Aaron Roth, and Weijie J Su.  Gaussian differential privacy.  arXiv preprint arXiv:1905.02383, 2019.
  * [38] Zhiqi Bu, Jinshuo Dong, Qi Long, and Weijie J Su.  Deep learning with gaussian differential privacy.  Harvard data science review, 2020(23):10–1162, 2020.

This appendix is organized into two sections: Appendix A, containing proofs of
our theoretical results; and Appendix B, providing in-depth information about
the experimental setup, datasets used, and supplementary experiments.

## Appendix A

###### Proof of Proposition 1.

We have classifiers $h_{0}^{*}:\mathcal{X}\rightarrow\\{0,1\\}$ and
$h_{1}^{*}:\mathcal{X}\rightarrow\\{0,1\\}$ trained on subgroups specified by
the sensitive attribute $A$ with values 0 and 1, respectively. We can combine
classifiers $h_{0}^{*}$ and $h_{1}^{*}$ to have a group aware classifier
$h^{*}:\mathcal{X}\times\\{0,1\\}\rightarrow\\{0,1\\}$. Basically,
$h^{*}(x,0)=h_{0}^{*}(x)\hskip 5.69046pt\forall x\in\mathcal{X}$ and
$h^{*}(x,1)=h_{1}^{*}(x)\hskip 5.69046pt\forall x\in\mathcal{X}$. Let
$Y^{*}=h^{*}(X,A)$ and $\hat{Y}=\hat{h}(X,A)$. Then for $a\in\\{0,1\\}$, we
have:

$\displaystyle d_{TV}(\mu_{a}(Y^{*}),\mu_{a}(\hat{Y}))$
$\displaystyle=\left|\mu_{a}(Y^{*}=1)-\mu_{a}(\hat{Y}=1)\right|$
$\displaystyle=\left|\mathbb{E}_{\mu_{a}^{X}}[h^{*}_{a}(X)]-\mathbb{E}_{\mu_{a}^{X}}[\hat{h}_{a}(X)]\right|$
$\displaystyle\leq\mathbb{E}_{\mu_{a}^{X}}\left[\left|h^{*}_{a}(X)-\hat{h}_{a}(X)\right|\right]$
$\displaystyle=\mathbb{P}_{\mu_{a}^{X}}\left(Y^{*}\neq\hat{Y}\right).$ (2)

Therefore, from (2) it follows:

$d_{TV}(\mu_{a}(Y^{*}),\mu_{a}(\hat{Y}))\leq\mathbb{P}_{\mu_{a}^{X}}\left(Y^{*}\neq\hat{Y}\right).$

We assumed $\hat{Y}=\hat{h}(X,A)$ satisfies $\gamma$ statistical parity
($\Delta_{SP}(\hat{h})\leq\gamma$). Thus, we have:

$\displaystyle
d_{TV}(\mu_{0}(\hat{Y}),\mu_{1}(\hat{Y}))=\left|\mu_{0}(\hat{Y}=1)-\mu_{1}(\hat{Y}=1)\right|=\Delta_{SP}(\hat{h})\leq\gamma.$

Since $d_{TV}(\cdot,\cdot)$ is symmetric and satisfies the triangle
inequality, we have:

$\displaystyle d_{TV}(\mu_{0}(Y^{*}),\mu_{1}(Y^{*}))$ $\displaystyle\leq
d_{TV}(\mu_{0}(Y^{*}),\mu_{0}(\hat{Y}))+d_{TV}(\mu_{0}(\hat{Y}),\mu_{1}(\hat{Y}))+d_{TV}(\mu_{1}(\hat{Y}),\mu_{1}(Y^{*}))$
$\displaystyle\leq
d_{TV}(\mu_{0}(Y^{*}),\mu_{0}(\hat{Y}))+\gamma+d_{TV}(\mu_{1}(Y^{*}),\mu_{1}(\hat{Y})).$
(3)

Combining (3) with (2), we have:

$\displaystyle d_{TV}(\mu_{0}(Y^{*}),\mu_{1}(Y^{*}))$
$\displaystyle\leq\mathbb{P}_{\mu_{0}^{X}}\left(Y^{*}\neq\hat{Y}\right)+\mathbb{P}_{\mu_{1}^{X}}\left(Y^{*}\neq\hat{Y}\right)+\gamma$
$\displaystyle=\mathbb{P}_{\mu^{X}_{0}}(\hat{h}_{0}(X)\neq
h^{*}_{0}(X))+\mathbb{P}_{\mu^{X}_{1}}(\hat{h}_{1}(X)\neq
h^{*}_{1}(X))+\gamma.$

Therefore, we can obtain:

$\displaystyle\Bigl{|}$
$\displaystyle\mathbb{P}_{\mu_{0}^{X}}(h_{0}^{*}(X)=1)-\mathbb{P}_{\mu_{1}^{X}}(h_{1}^{*}(X)=1)\Bigr{|}\leq\mathbb{P}_{\mu^{X}_{0}}(\hat{h}_{0}(X)\neq
h^{*}_{0}(X))+\mathbb{P}_{\mu^{X}_{1}}(\hat{h}_{1}(X)\neq
h^{*}_{1}(X))+\gamma.$

Thus, we have:

$\begin{split}&\mathbb{P}_{\mu^{X}_{0}}(\hat{h}_{0}(X)\neq
h^{*}_{0}(X))+\mathbb{P}_{\mu^{X}_{1}}(\hat{h}_{1}(X)\neq
h^{*}_{1}(X))\geq\left|\mathbb{P}_{\mu^{X}_{0}}(h^{*}_{0}(X)=1)-\mathbb{P}_{\mu^{X}_{1}}(h^{*}_{1}(X)=1)\right|-\gamma.\end{split}$

which concludes the proof of Proposition 1. ∎

###### Proof of Theorem 2.

Let $s$ in Algorithm 1 be the realization of the random variable $S$. First,
we compute the statistical parity gap of the classifier $h^{*}_{\text{Fair}}$.

$\displaystyle\mathbb{P}_{\mu}\left(h^{*}_{\text{Fair}}(X,A)=1|A=0\right)=\mathbb{P}_{\mu_{0}^{X}}(h_{0}^{*}(X)=1)\mathbb{P}(S\leq\frac{\alpha+\beta}{2\alpha})=\alpha\left(\frac{\alpha+\beta}{2\alpha}\right)=\frac{\alpha+\beta}{2}.$
$\displaystyle\mathbb{P}_{\mu}\left(h^{*}_{\text{Fair}}(X,A)=1|A=1\right)$
$\displaystyle=\mathbb{P}_{\mu_{1}^{X}}(h_{1}^{*}(X)=1)+\mathbb{P}_{\mu_{1}^{X}}(h_{1}^{*}(X)=0)\mathbb{P}\left(S\leq\frac{\alpha-\beta}{2(1-\beta)}\right)$
$\displaystyle=\beta+(1-\beta)\left(\frac{\alpha-\beta}{2(1-\beta)}\right)$
$\displaystyle=\frac{\alpha+\beta}{2}.$

Hence, we have:

$\Delta_{SP}(h^{*}_{\text{Fair}})=\left|\frac{\alpha+\beta}{2}-\frac{\alpha+\beta}{2}\right|=0.$

Therefore, perfect statistical parity is satisfied. Now we show that
$h^{*}_{\text{Fair}}$ is optimal.

$\displaystyle\mathbb{P}_{\mu^{X}_{0}}({h^{*}_{\text{Fair}}}_{0}(X)\neq
h^{*}_{0}(X))=\mathbb{P}_{\mu_{0}^{X}}(h^{*}_{0}(X)=1)\mathbb{P}\left(S>\frac{\alpha+\beta}{2\alpha}\right)=\alpha\left(\frac{\alpha-\beta}{2\alpha}\right)=\frac{\alpha-\beta}{2}.$
$\displaystyle\mathbb{P}_{\mu^{X}_{1}}({h^{*}_{\text{Fair}}}_{1}(X)\neq
h^{*}_{1}(X))$
$\displaystyle=\mathbb{P}_{\mu_{1}^{X}}(h^{*}_{1}(X)=0)\mathbb{P}\left(S\leq\frac{\alpha-\beta}{2(1-\beta)}\right)$
$\displaystyle=(1-\beta)\left(\frac{\alpha-\beta}{2(1-\beta)}\right)=\frac{\alpha-\beta}{2}.$

Thus, we have:

$\begin{split}\mathbb{P}_{\mu^{X}_{0}}({h^{*}_{\text{Fair}}}_{0}(X)\neq
h^{*}_{0}(X))+\mathbb{P}_{\mu^{X}_{1}}({h^{*}_{\text{Fair}}}_{1}(X)\neq
h^{*}_{1}(X))&=\frac{\alpha-\beta}{2}+\frac{\alpha-\beta}{2}=\alpha-\beta=\left|\alpha-\beta\right|\\\
&=\left|\mathbb{P}_{\mu^{X}_{0}}(h^{*}_{0}(X)=1)-\mathbb{P}_{\mu^{X}_{1}}(h^{*}_{1}(X)=1)\right|.\end{split}$

Therefore, $h^{*}_{\text{Fair}}$ satisfies perfect statistical parity and
attains the utility lower bound of Proposition 1. ∎

###### Proof of Theorem 3.

  * •

Computing $\tilde{\alpha}$ and $\tilde{\beta}$ is done using the Laplace
mechanism followed by a post-processing (projection). Therefore, these two
mechanisms will satisfy $\varepsilon_{2}$-DP and $\varepsilon_{3}$-DP [33].
Also, learning $h_{\varepsilon_{0},\delta_{0}}^{*}$ and
$h_{\varepsilon_{1},\delta_{1}}^{*}$ was done with privacy parameters
$(\varepsilon_{0},\delta_{0})$ and $(\varepsilon_{1},\delta_{1})$. By basic
composition, we have $h^{*}_{\varepsilon,\delta,\text{Fair}}$ satisfies
$(\varepsilon,\delta)$-DP with
$\varepsilon=\sum\limits_{i=0}^{3}\varepsilon_{i}$ and
$\delta=\delta_{0}+\delta_{1}$.

  * •

Let $\alpha=\mathbb{P}_{\mu^{X}_{0}}(h^{*}_{\varepsilon_{0},\delta_{0}}(X)=1)$
and $\beta=\mathbb{P}_{\mu^{X}_{1}}(h^{*}_{\varepsilon_{1},\delta_{1}}(X)=1)$.
Let $\bar{\alpha}=\alpha+e_{0}$ and $\bar{\beta}=\beta+e_{1}$. Following the
methodology in [31], we assume $e_{0}$ and $e_{1}$ are sufficiently small,
i.e., we have sufficiently large samples to empirically approximate the true
value of $\alpha$ and $\beta$ precisely. To prove the claims in the theorem,
we assume $\tilde{\alpha}\geq\tilde{\beta}$. For the case that
$\tilde{\alpha}<\tilde{\beta}$, we will have the same results by symmetry.
Also, let $L_{0}\sim\text{Lap}\big{(}\frac{1}{n_{0}\varepsilon_{2}}\big{)}$
and $L_{1}\sim\text{Lap}\big{(}\frac{1}{n_{1}\varepsilon_{3}}\big{)}$. In
Algorithm 2, we sample $l_{0}$ from $L_{0}$ and $l_{1}$ from $L_{1}$. Similar
to the proof of Theorem 2, let $s$ in Algorithm 2 be the realization of the
random variable $S$. By definition, we have:

$\displaystyle\Delta_{SP}(h^{*}_{\varepsilon,\delta,\text{Fair}})=\bigl{|}$
$\displaystyle\mathbb{P}_{\mu_{0}^{X}}\left(h^{*}_{\varepsilon,\delta,\text{Fair}}(X,0)=1\right)-\mathbb{P}_{\mu_{1}^{X}}\left(h^{*}_{\varepsilon,\delta,\text{Fair}}(X,1)=1\right)\bigr{|}.$

We first compute
$\mathbb{P}_{\mu_{0}^{X}}\left(h^{*}_{\varepsilon,\delta,\text{Fair}}(X,0)=1\right)$:

$\displaystyle\mathbb{P}_{\mu_{0}^{X}}\left(h^{*}_{\varepsilon,\delta,\text{Fair}}(X,0)=1\right)$
$\displaystyle=\mathbb{P}_{\mu^{X}_{0}}(h^{*}_{\varepsilon_{0},\delta_{0}}(X)=1)\mathbb{P}\left(S\leq\frac{\tilde{\alpha}+\tilde{\beta}}{2\tilde{\alpha}}\right)$
$\displaystyle=\alpha\frac{\tilde{\alpha}+\tilde{\beta}}{2\tilde{\alpha}}$
$\displaystyle=\frac{\alpha}{\tilde{\alpha}}\left(\frac{\tilde{\alpha}+\tilde{\beta}}{2}\right).$

We then compute
$\mathbb{P}_{\mu_{1}^{X}}\left(h^{*}_{\varepsilon,\delta,\text{Fair}}(X,1)=1\right)$:

$\displaystyle\mathbb{P}_{\mu_{1}^{X}}\left(h^{*}_{\varepsilon,\delta,\text{Fair}}(X,1)=1\right)$
$\displaystyle=\mathbb{P}_{\mu^{X}_{1}}(h^{*}_{\varepsilon_{1},\delta_{1}}(X)=1)+\mathbb{P}_{\mu^{X}_{1}}(h^{*}_{\varepsilon_{1},\delta_{1}}(X)=0)\mathbb{P}\left(S\leq\frac{\tilde{\alpha}-\tilde{\beta}}{2(1-\tilde{\beta})}\right)$
$\displaystyle=\beta+(1-\beta)\left(\frac{\tilde{\alpha}-\tilde{\beta}}{2(1-\tilde{\beta})}\right)=\beta+\frac{(1-\beta)}{(1-\tilde{\beta})}\left(\frac{\tilde{\alpha}-\tilde{\beta}}{2}\right).$

For each realization of $\tilde{\alpha}$ and $\tilde{\beta}$, let
$\bar{\alpha}=\alpha+e_{0}$ , $\tilde{\alpha}=\bar{\alpha}+d_{0}$,
$\bar{\beta}=\beta+e_{1}$ , $\tilde{\beta}=\bar{\beta}+d_{1}$. Thus, we have:

$\displaystyle\Delta_{SP}(h^{*}_{\varepsilon,\delta,\text{Fair}})=\left|\frac{\alpha}{\tilde{\alpha}}\left(\frac{\tilde{\alpha}+\tilde{\beta}}{2}\right)-\left[\beta+\frac{(1-\beta)}{(1-\tilde{\beta})}\left(\frac{\tilde{\alpha}-\tilde{\beta}}{2}\right)\right]\right|$
$\displaystyle\hskip
56.9055pt=\Biggl{|}\frac{\tilde{\alpha}-e_{0}-d_{0}}{\tilde{\alpha}}\left(\frac{\tilde{\alpha}+\tilde{\beta}}{2}\right)-\Biggl{[}\tilde{\beta}-e_{1}-d_{1}+\frac{(1-\tilde{\beta}+e_{1}+d_{1})}{(1-\tilde{\beta})}\left(\frac{\tilde{\alpha}-\tilde{\beta}}{2}\right)\Biggr{]}\Biggr{|}$
$\displaystyle\hskip
56.9055pt=\Biggl{|}\left(\frac{\tilde{\alpha}+\tilde{\beta}}{2}\right)-(e_{0}+d_{0})\left(\frac{\tilde{\alpha}+\tilde{\beta}}{2\tilde{\alpha}}\right)-\tilde{\beta}+e_{1}+d_{1}-\left(\frac{\tilde{\alpha}-\tilde{\beta}}{2}\right)-(e_{1}+d_{1})\left(\frac{\tilde{\alpha}-\tilde{\beta}}{2(1-\tilde{\beta})}\right)\Biggr{|}$
$\displaystyle\hskip
56.9055pt=\left|(e_{1}+d_{1})\left(1-\frac{\tilde{\alpha}-\tilde{\beta}}{2(1-\tilde{\beta})}\right)-(e_{0}+d_{0})\left(\frac{\tilde{\alpha}+\tilde{\beta}}{2\tilde{\alpha}}\right)\right|$
$\displaystyle\hskip
56.9055pt\leq\left|(e_{1}+d_{1})\left(1-\frac{\tilde{\alpha}-\tilde{\beta}}{2(1-\tilde{\beta})}\right)\right|+\left|(e_{0}+d_{0})\left(\frac{\tilde{\alpha}+\tilde{\beta}}{2\tilde{\alpha}}\right)\right|$
$\displaystyle\hskip
56.9055pt\leq\left|(e_{1}+d_{1})\right|+\left|(e_{0}+d_{0})\right|$
$\displaystyle\hskip 56.9055pt\leq|e_{0}|+|e_{1}|+|d_{0}|+|d_{1}|.$ (4)

The last line follows from the fact that $0\leq\tilde{\alpha}\leq 1$,
$0\leq\tilde{\beta}\leq 1$, and $\tilde{\alpha}\geq\tilde{\beta}$.

Assuming sufficiently large number of samples for each subgroup, which implies
that $e_{0}$ and $e_{1}$ are sufficiently small, the values of $|e_{0}|$ and
$|e_{1}|$ become negligible. Let $l_{0}$ and $l_{1}$ be the realization of the
Laplace noises in Algorithm 2. We know that $|d_{0}|\leq|l_{0}|$ and
$|d_{1}|\leq|l_{1}|$ since $d_{0}$ and $d_{1}$ are computed after projection.
On the other hand, from [33], we know that if
$L\sim\text{Lap}(\frac{\Delta_{1}^{q}}{\varepsilon})$, then:

$\mathbb{P}\left[|L|\geq\left(\log{\frac{1}{\eta}}\right)\left(\frac{\Delta_{1}^{q}}{\varepsilon}\right)\right]\leq\eta.$

where $\Delta_{1}^{q}$ is the $\ell_{1}$-sensitivity of the query to which we
add noise.

Given $L_{0}\sim\text{Lap}\left(\frac{1}{n_{0}\varepsilon_{2}}\right)$ and
$L_{1}\sim\text{Lap}\left(\frac{1}{n_{1}\varepsilon_{3}}\right)$, we have:
$|L_{0}|\leq_{\eta_{0}}\left(\log{\frac{1}{\eta_{0}}}\right)\left(\frac{1}{n_{0}\varepsilon_{2}}\right)$
and
$|L_{1}|\leq_{\eta_{1}}\left(\log{\frac{1}{\eta_{1}}}\right)\left(\frac{1}{n_{1}\varepsilon_{3}}\right).$
Thus, with probability at least $(1-\eta_{0})(1-\eta_{1})$, we have:

$|L_{0}|+|L_{1}|\leq\left[\left(\log{\frac{1}{\eta_{0}}}\right)\left(\frac{1}{n_{0}\varepsilon_{2}}\right)+\left(\log{\frac{1}{\eta_{1}}}\right)\left(\frac{1}{n_{1}\varepsilon_{3}}\right)\right].$

Since $(1-\eta_{0})(1-\eta_{1})\geq 1-(\eta_{0}+\eta_{1})$ for
$0\leq\eta_{0},\eta_{1}\leq 1$, we have:

$|L_{0}|+|L_{1}|\leq_{\eta_{0}+\eta_{1}}\left[\left(\log{\frac{1}{\eta_{0}}}\right)\left(\frac{1}{n_{0}\varepsilon_{2}}\right)+\left(\log{\frac{1}{\eta_{1}}}\right)\left(\frac{1}{n_{1}\varepsilon_{3}}\right)\right].$
(5)

Combining (• ‣ Proof of Theorem 3.) and (5), it can be shown:

$\Delta_{SP}(h^{*}_{\varepsilon,\delta,\text{Fair}})\leq_{\eta_{0}+\eta_{1}}\frac{\log\left(\frac{1}{\eta_{0}}\right)}{n_{0}\varepsilon_{2}}+\frac{\log\left(\frac{1}{\eta_{1}}\right)}{n_{1}\varepsilon_{3}}.$

  * •

We have:

$\displaystyle\mathbb{P}_{\mu^{X}_{0}}({h^{*}_{\varepsilon,\delta,\text{Fair}}}_{0}(X)\neq
h^{*}_{\varepsilon_{0},\delta_{0}}(X))+\mathbb{P}_{\mu^{X}_{1}}({h^{*}_{\varepsilon,\delta,\text{Fair}}}_{1}(X)\neq
h^{*}_{\varepsilon_{1},\delta_{1}}(X))$ $\displaystyle\hskip
48.36958pt=\mathbb{P}_{\mu^{X}_{0}}\Bigl{(}(h^{*}_{\varepsilon_{0},\delta_{0}}(X)=1)\hskip
2.84544pt\text{and}\hskip
2.84544pt({h^{*}_{\varepsilon,\delta,\text{Fair}}}_{0}(X)=0)\Bigr{)}+\mathbb{P}_{\mu^{X}_{1}}\Bigl{(}(h^{*}_{\varepsilon_{1},\delta_{1}}(X)=0)\hskip
2.84544pt\text{and}\hskip
2.84544pt({h^{*}_{\varepsilon,\delta,\text{Fair}}}_{1}(X)=1)\Bigr{)}$
$\displaystyle\hskip
48.36958pt=\alpha\left(\frac{\tilde{\alpha}-\tilde{\beta}}{2\tilde{\alpha}}\right)+(1-\beta)\left(\frac{\tilde{\alpha}-\tilde{\beta}}{2(1-\tilde{\beta})}\right)=\frac{\alpha}{\tilde{\alpha}}\left(\frac{\tilde{\alpha}-\tilde{\beta}}{2}\right)+\frac{(1-\beta)}{1-\tilde{\beta}}\left(\frac{\tilde{\alpha}-\tilde{\beta}}{2}\right)$
$\displaystyle\hskip
48.36958pt=\frac{\tilde{\alpha}-e_{0}-d_{0}}{\tilde{\alpha}}\left(\frac{\tilde{\alpha}-\tilde{\beta}}{2}\right)+\frac{(1-\tilde{\beta}+e_{1}+d_{1})}{1-\tilde{\beta}}\left(\frac{\tilde{\alpha}-\tilde{\beta}}{2}\right)$
$\displaystyle\hskip
48.36958pt=(\tilde{\alpha}-\tilde{\beta})+(e_{1}+d_{1})\left(\frac{\tilde{\alpha}-\tilde{\beta}}{2(1-\tilde{\beta})}\right)-(e_{0}+d_{0})\left(\frac{\tilde{\alpha}-\tilde{\beta}}{2\tilde{\alpha}}\right).$

Therefore, we have:

$\displaystyle\begin{split}&\mathbb{P}_{\mu^{X}_{0}}({h^{*}_{\varepsilon,\delta,\text{Fair}}}_{0}(X)\neq
h^{*}_{\varepsilon_{0},\delta_{0}}(X))+\mathbb{P}_{\mu^{X}_{1}}({h^{*}_{\varepsilon,\delta,\text{Fair}}}_{1}(X)\neq
h^{*}_{\varepsilon_{1},\delta_{1}}(X))-\text{err}^{*}(h^{*}_{\varepsilon_{0},\delta_{0}},h^{*}_{\varepsilon_{1},\delta_{1}})\\\
&\qquad\qquad=(\tilde{\alpha}-\tilde{\beta})+(e_{1}+d_{1})\left(\frac{\tilde{\alpha}-\tilde{\beta}}{2(1-\tilde{\beta})}\right)-(e_{0}+d_{0})\left(\frac{\tilde{\alpha}-\tilde{\beta}}{2\tilde{\alpha}}\right)-\text{err}^{*}(h^{*}_{\varepsilon_{0},\delta_{0}},h^{*}_{\varepsilon_{1},\delta_{1}}).\end{split}$

From previous part, we know that:

$\Delta_{SP}(h^{*}_{\varepsilon,\delta,\text{Fair}})\leq|e_{0}|+|e_{1}|+|d_{0}|+|d_{1}|.$

From Proposition 1, we know that if $\Delta_{SP}(\hat{h})\leq\gamma$, then:

$\begin{split}&\mathbb{P}_{\mu^{X}_{0}}(\hat{h}_{0}(X)\neq
h^{*}_{\varepsilon_{0},\delta_{0}}(X))+\mathbb{P}_{\mu^{X}_{1}}(\hat{h}_{1}(X)\neq
h^{*}_{\varepsilon_{1},\delta_{1}}(X))\geq\left|\mathbb{P}_{\mu^{X}_{0}}(h^{*}_{\varepsilon_{0},\delta_{0}}(X)=1)-\mathbb{P}_{\mu^{X}_{1}}(h^{*}_{\varepsilon_{1},\delta_{1}}(X)=1)\right|-\gamma.\end{split}$

For all classifiers $\hat{h}:\mathcal{X}\times\\{0,1\\}\rightarrow\\{0,1\\}$
that satisfy
$\Delta_{SP}(\hat{h})\leq\Delta_{SP}(h^{*}_{\varepsilon,\delta,\text{Fair}})$,
we have $\Delta_{SP}(\hat{h})\leq|e_{0}|+|e_{1}|+|d_{0}|+|d_{1}|$. Thus, for
all those classifiers we have:

$\begin{split}&\mathbb{P}_{\mu^{X}_{0}}(\hat{h}_{0}(X)\neq
h^{*}_{\varepsilon_{0},\delta_{0}}(X))+\mathbb{P}_{\mu^{X}_{1}}(\hat{h}_{1}(X)\neq
h^{*}_{\varepsilon_{1},\delta_{1}})\\\
&\qquad\qquad\qquad\geq\left|\mathbb{P}_{\mu^{X}_{0}}(h^{*}_{\varepsilon_{0},\delta_{0}}(X)=1)-\mathbb{P}_{\mu^{X}_{1}}(h^{*}_{\varepsilon_{1},\delta_{1}}(X)=1)\right|-\bigl{(}|e_{0}|+|e_{1}|+|d_{0}|+|d_{1}|\bigr{)}\\\
&\qquad\qquad\qquad=\left|\alpha-\beta\right|-\bigr{(}|e_{0}|+|e_{1}|+|d_{0}|+|d_{1}|\bigl{)}.\end{split}$

Therefore, by definition of
$\text{err}^{*}(h^{*}_{\varepsilon_{0},\delta_{0}},h^{*}_{\varepsilon_{1},\delta_{1}})$,
we have:

$\text{err}^{*}(h^{*}_{\varepsilon_{0},\delta_{0}},h^{*}_{\varepsilon_{1},\delta_{1}})\geq|\alpha-\beta|-\left(|e_{0}|+|e_{1}|+|d_{0}|+|d_{1}|\right).$

Therefore, it follows:

$\displaystyle\mathbb{P}_{\mu^{X}_{0}}({h^{*}_{\varepsilon,\delta,\text{Fair}}}_{0}(X)\neq
h^{*}_{\varepsilon_{0},\delta_{0}}(X))+\mathbb{P}_{\mu^{X}_{1}}({h^{*}_{\varepsilon,\delta,\text{Fair}}}_{1}(X)\neq
h^{*}_{\varepsilon_{1},\delta_{1}}(X))-\text{err}^{*}(h^{*}_{\varepsilon_{0},\delta_{0}},h^{*}_{\varepsilon_{1},\delta_{1}})$
$\displaystyle\qquad\qquad\leq(\tilde{\alpha}-\tilde{\beta})+(e_{1}+d_{1})\left(\frac{\tilde{\alpha}-\tilde{\beta}}{2(1-\tilde{\beta})}\right)-(e_{0}+d_{0})\left(\frac{\tilde{\alpha}-\tilde{\beta}}{2\tilde{\alpha}}\right)-|\alpha-\beta|+\left(|e_{0}|+|e_{1}|+|d_{0}|+|d_{1}|\right)$
$\displaystyle\qquad\qquad\leq\frac{1}{2}|e_{1}+d_{1}|+\frac{1}{2}|e_{0}+d_{0}|+(\tilde{\alpha}-\tilde{\beta})-|\alpha-\beta|+\left(|e_{0}|+|e_{1}|+|d_{0}|+|d_{1}|\right)$
$\displaystyle\qquad\qquad\leq(\tilde{\alpha}-\tilde{\beta})-|\alpha-\beta|+\frac{3}{2}\left(|e_{0}|+|e_{1}|+|d_{0}|+|d_{1}|\right)$
$\displaystyle\qquad\qquad=(\tilde{\alpha}-\tilde{\beta})-|\tilde{\alpha}-e_{0}-d_{0}-\tilde{\beta}+e_{1}+d_{1}|+\frac{3}{2}\left(|e_{0}|+|e_{1}|+|d_{0}|+|d_{1}|\right)$
$\displaystyle\qquad\qquad\leq\frac{5}{2}\left(|e_{0}|+|e_{1}|+|d_{0}|+|d_{1}|\right).$

Assuming $e_{0}$ and $e_{1}$ are sufficiently small, and by the same argument
of the second part, we can conclude that:

$\displaystyle\mathbb{P}_{\mu^{X}_{0}}({h^{*}_{\varepsilon,\delta,\text{Fair}}}_{0}(X)\neq
h^{*}_{\varepsilon_{0},\delta_{0}}(X))$
$\displaystyle+\mathbb{P}_{\mu^{X}_{1}}({h^{*}_{\varepsilon,\delta,\text{Fair}}}_{1}(X)\neq
h^{*}_{\varepsilon_{1},\delta_{1}}(X))$
$\displaystyle\leq_{\eta_{0}+\eta_{1}}\text{err}^{*}(h^{*}_{\varepsilon_{0},\delta_{0}},h^{*}_{\varepsilon_{1},\delta_{1}})+\frac{5}{2}\left(\frac{\log\left(\frac{1}{\eta_{0}}\right)}{n_{0}\varepsilon_{2}}+\frac{\log\left(\frac{1}{\eta_{1}}\right)}{n_{1}\varepsilon_{3}}\right).$

∎

###### Proof of Proposition 4.

Let $\alpha=\mathbb{P}_{\mu^{X}_{0}}(h^{*}_{\varepsilon_{0},\delta_{0}}(X)=1)$
and $\beta=\mathbb{P}_{\mu^{X}_{1}}(h^{*}_{\varepsilon_{1},\delta_{1}}(X)=1)$.
Also, let $\bar{\alpha}=\alpha+e_{0}$ and $\bar{\beta}=\beta+e_{1}$. Similar
to the proof of Theorem 3, following the strategy in [31], we assume $e_{0}$
and $e_{1}$ are sufficiently small, i.e., we have sufficiently large samples
to empirically approximate the true value of $\alpha$ and $\beta$ precisely.
Let $L_{0}\sim\text{Lap}\big{(}\frac{1}{n_{0}\varepsilon_{2}}\big{)}$ and
$L_{1}\sim\text{Lap}\big{(}\frac{1}{n_{1}\varepsilon_{3}}\big{)}$. We sample
$l_{0}$ from $L_{0}$ and $l_{1}$ from $L_{1}$. In fact, $l_{0}$ and $l_{1}$
are realizations of the Laplace noise. From proof of Theorem3, we know that
for each realization of the noise we have:

$\begin{split}\Delta_{SP}(h^{*}_{\varepsilon,\delta,\text{Fair}})\leq\left[|e_{0}|+|e_{1}|+|l_{0}|+|l_{1}|\right].\end{split}$

And

$\begin{split}\Biggl{[}\mathbb{P}_{\mu^{X}_{0}}({h^{*}_{\varepsilon,\delta,\text{Fair}}}_{0}(X)\neq
h^{*}_{\varepsilon_{0},\delta_{0}}(X))+\mathbb{P}_{\mu^{X}_{1}}({h^{*}_{\varepsilon,\delta,\text{Fair}}}_{1}(X)\neq&h^{*}_{\varepsilon_{1},\delta_{1}}(X))-\text{err}^{*}(h^{*}_{\varepsilon_{0},\delta_{0}},h^{*}_{\varepsilon_{1},\delta_{1}})\Biggr{]}\leq\frac{5}{2}\left[\left(|e_{0}|+|e_{1}|+|l_{0}|+|l_{1}|\right)\right].\end{split}$

We have:

$\mathbb{E}\left[\Delta_{SP}(h^{*}_{\varepsilon,\delta,\text{Fair}})\right]\leq\mathbb{E}\left[|e_{0}|+|e_{1}|+|L_{0}|+|L_{1}|\right].$

And

$\begin{split}\mathbb{E}\Biggl{[}\mathbb{P}_{\mu^{X}_{0}}({h^{*}_{\varepsilon,\delta,\text{Fair}}}_{0}(X)\neq
h^{*}_{\varepsilon_{0},\delta_{0}}(X))+\mathbb{P}_{\mu^{X}_{1}}({h^{*}_{\varepsilon,\delta,\text{Fair}}}_{1}(X)\neq&h^{*}_{\varepsilon_{1},\delta_{1}}(X))-\text{err}^{*}(h^{*}_{\varepsilon_{0},\delta_{0}},h^{*}_{\varepsilon_{1},\delta_{1}})\Biggr{]}\leq\\\
&\qquad\qquad\qquad\qquad\frac{5}{2}\mathbb{E}\left[\left(|e_{0}|+|e_{1}|+|L_{0}|+|L_{1}|\right)\right].\end{split}$

Where both expectations are over the randomness of the Laplace noise. For
$L\sim\text{Lap}(\frac{\Delta_{1}^{q}}{\varepsilon})$, we have
$\mathbb{E}\left[|L|\right]=\frac{\Delta_{1}^{q}}{\varepsilon}$. Since
$L_{0}\sim\text{Lap}\left(\frac{1}{n_{0}\varepsilon_{2}}\right)\text{ and
}L_{1}\sim\text{Lap}\left(\frac{1}{n_{1}\varepsilon_{3}}\right)$, assuming
$e_{0}$ and $e_{1}$ are sufficiently small, we have:

$\mathbb{E}\left[\Delta_{SP}(h^{*}_{\varepsilon,\delta,\text{Fair}})\right]\leq\left(\frac{1}{n_{0}\varepsilon_{2}}\right)+\left(\frac{1}{n_{1}\varepsilon_{3}}\right).$

And

$\begin{split}\mathbb{E}\Biggl{[}\mathbb{P}_{\mu^{X}_{0}}({h^{*}_{\varepsilon,\delta,\text{Fair}}}_{0}(X)\neq
h^{*}_{\varepsilon_{0},\delta_{0}}(X))&+\mathbb{P}_{\mu^{X}_{1}}({h^{*}_{\varepsilon,\delta,\text{Fair}}}_{1}(X)\neq
h^{*}_{\varepsilon_{1},\delta_{1}}(X))\Biggr{]}\leq\mathbb{E}\Bigl{[}\text{err}^{*}(h^{*}_{\varepsilon_{0},\delta_{0}},h^{*}_{\varepsilon_{1},\delta_{1}})\Bigr{]}+\frac{5}{2}\left(\frac{1}{n_{0}\varepsilon_{2}}+\frac{1}{n_{1}\varepsilon_{3}}\right).\end{split}$

∎

## Appendix B

In this section, we provide additional details on our experiments, including
datasets, pre-processing approach, and additional experimental results.

Adult Dataset: This dataset contains census information about individuals. The
prediction task is to determine whether a person earns over $50K a year. In
this dataset, gender is considered as a sensitive attribute. For all
experiments, we followed a pre-processing approach similar to [28]. After pre-
processing, the dataset contains a total of 102 input features. The size of
the dataset is around 48,000 entries.

Credit Card Dataset: This dataset includes financial data from bank users in
Taiwan. The prediction task is to assess whether a person defaults on their
credit card bills, essentially evaluating client credibility. Gender is taken
as a sensitive attribute. We applied the same pre-processing method as in [28]
for all experiments. After pre-processing, the dataset contained 85 input
features, with a total of 30,000 entries.

For DP-FERMI experiments, datasets were split into $75\%$ training and $25\%$
testing. However, for Algorithm 2, we needed to train two initial classifiers
$h_{\varepsilon_{0},\delta_{0}}^{*}$ and $h_{\varepsilon_{1},\delta_{1}}^{*}$,
followed by a post-processing step. For this, we divided the dataset into
three parts: $50\%$ for training the initial classifiers, and $25\%$ each for
post-processing and testing.

To calculate the statistical parity gap of output classifiers in all
experiments, we refer to Definition 2. We need to compute:

$\Delta_{SP}(\hat{h}):=|\mu_{0}(\hat{Y}=1)-\mu_{1}(\hat{Y}=1)|.$

In practice, where we do not have access to true distributions $\mu_{a}$, we
use their empirical counterparts. Specifically, we calculate the empirical
version of $\mu_{a}(\hat{Y}=1)$, i.e., we compute
$\hat{\mathbb{P}}\bigl{[}\hat{Y}=1|A=a\bigr{]}$. Thus, the empirical version
of the statistical parity gap is defined as:

$\widehat{\Delta_{SP}}(\hat{h}):=\Biggl{|}\hat{\mathbb{P}}\Bigl{[}\hat{Y}=1|A=0\Bigr{]}-\hat{\mathbb{P}}\Bigl{[}\hat{Y}=1|A=1\Bigr{]}\Biggr{|}.$

In this expression, $\hat{\mathbb{P}}\bigl{[}\hat{Y}=1|A=0\bigr{]}$ and
$\hat{\mathbb{P}}\bigl{[}\hat{Y}=1|A=1\bigr{]}$ are computed on the test split
of the dataset. The statistical parity gap values listed in the column of all
tables are derived using the empirical statistical parity gap calculation.

We present the results of our experiments with privacy parameters computed
using both the moments accountant and GDP accountant methods. For moments
accountant method, we selected the standard deviations of Gaussian noise in
DP-SGD to be $4.4$ and $2.08$ for the Adult dataset, and $6.2$ and $3.46$ for
the Credit Card dataset. These values were chosen to achieve their respective
privacy parameters of $(\varepsilon=3,\delta=10^{-5})$ and
$(\varepsilon=9,\delta=10^{-5})$. To achieve the target privacy parameters
using GDP accountant in Algorithm 2, we set specific noise variances for the
Adult and Credit Card datasets. For the Adult dataset, with privacy parameters
$(\varepsilon=3,\delta=10^{-5})$ and $(\varepsilon=9,\delta=10^{-5})$, the
standard deviation of the Gaussian noise were set to $4$ and $1.94$,
respectively. In the case of the Credit Card dataset, under identical privacy
parameters, we used a Gaussian noise with a standard deviation of $5.7$ and
$3.24$ in DP-SGD. All other parameters, including $\varepsilon_{2}$,
$\varepsilon_{3}$, learning rate, number of epochs, batch size, and clipping
constant, were kept consistent with those used in the experiments where the
privacy guarantee was calculated using PRV accountant method (the experiments
detailed in Tables III, III, V, and V).

The results corresponding to moments accountant method are presented in Tables
VII, VII, IX, and IX. Additionally, the results corresponding to GDP
accountant method are available in Tables XI, XI, XIII, and XIII. Note that
the DP-FERMI experiment results remain the same; the only difference lies in
the line corresponding to Algorithm 2.

It can be concluded that across all these experiments, similar to what was
noted in Section IV, Algorithm 2 consistently offers a substantially better
(smaller) statistical parity gap compared to DP-FERMI for fixed privacy and
accuracy, regardless of varying privacy parameters, datasets (Adult and Credit
Card), and privacy accounting methods employed.

TABLE VI: Adult Dataset ($\varepsilon=3,\delta=10^{-5}$) - Moments Accountant Method |  Accuracy |  Statistical Parity Gap
---|---|---
Algorithm 2 |  0.7754 |  0.0054
DP-FERMI ($\lambda=0.5$) |  0.7998 |  0.1020
DP-FERMI ($\lambda=1$) |  0.7859 |  0.0462
DP-FERMI ($\lambda=1.5$) |  0.7822 |  0.0267
DP-FERMI ($\lambda=1.9$) |  0.7749 |  0.0126
DP-FERMI ($\lambda=2.5$) |  0.7673 |  0.0099

TABLE VII: Adult Dataset ($\varepsilon=9,\delta=10^{-5}$) - Moments Accountant Method |  Accuracy |  Statistical Parity Gap
---|---|---
Algorithm 2 |  0.7769 |  0.0078
DP-FERMI ($\lambda=0.5$) |  0.8091 |  0.0944
DP-FERMI ($\lambda=1$) |  0.7923 |  0.0413
DP-FERMI ($\lambda=1.5$) |  0.7810 |  0.0152
DP-FERMI ($\lambda=1.8$) |  0.7769 |  0.0113
DP-FERMI ($\lambda=2.5$) |  0.7693 |  0.0030

TABLE VIII: Credit Card Dataset ($\varepsilon=3,\delta=10^{-5}$) - Moments Accountant Method |  Accuracy |  Statistical Parity Gap
---|---|---
Algorithm 2 |  0.7891 |  0.0108
DP-FERMI ($\lambda=0.1$) |  0.7899 |  0.0212
DP-FERMI ($\lambda=0.25$) |  0.7826 |  0.0195
DP-FERMI ($\lambda=0.5$) |  0.7777 |  0.0185
DP-FERMI ($\lambda=1$) |  0.7759 |  0.0105
DP-FERMI ($\lambda=2.5$) |  0.7669 |  0.0110

TABLE IX: Credit Card Dataset ($\varepsilon=9,\delta=10^{-5}$) - Moments Accountant Method |  Accuracy |  Statistical Parity Gap
---|---|---
Algorithm 2 |  0.7951 |  0.0060
DP-FERMI ($\lambda=0.25$) |  0.7996 |  0.0188
DP-FERMI ($\lambda=0.35$) |  0.7950 |  0.0174
DP-FERMI ($\lambda=0.5$) |  0.7912 |  0.0172
DP-FERMI ($\lambda=1$) |  0.7895 |  0.0105
DP-FERMI ($\lambda=2.5$) |  0.7884 |  0.0066

TABLE X: Adult Dataset ($\varepsilon=3,\delta=10^{-5})$ \- GDP Accountant Method |  Accuracy |  Statistical Parity Gap
---|---|---
Algorithm 2 |  0.7801 |  0.0088
DP-FERMI ($\lambda=0.5$) |  0.7998 |  0.1020
DP-FERMI ($\lambda=1$) |  0.7859 |  0.0462
DP-FERMI ($\lambda=1.5$) |  0.7822 |  0.0267
DP-FERMI ($\lambda=1.7$) |  0.7795 |  0.0215
DP-FERMI ($\lambda=2.5$) |  0.7673 |  0.0099

TABLE XI: Adult Dataset ($\varepsilon=9,\delta=10^{-5})$ \- GDP Accountant Method |  Accuracy |  Statistical Parity Gap
---|---|---
Algorithm 2 |  0.7813 |  0.0048
DP-FERMI ($\lambda=0.5$) |  0.8091 |  0.0944
DP-FERMI ($\lambda=1$) |  0.7923 |  0.0413
DP-FERMI ($\lambda=1.5$) |  0.7810 |  0.0152
DP-FERMI ($\lambda=1.8$) |  0.7769 |  0.0113
DP-FERMI ($\lambda=2.5$) |  0.7693 |  0.0030

TABLE XII: Credit Card Dataset ($\varepsilon=3,\delta=10^{-5})$ \- GDP Accountant Method |  Accuracy |  Statistical Parity Gap
---|---|---
Algorithm 2 |  0.7884 |  0.0070
DP-FERMI ($\lambda=0.1$) |  0.7899 |  0.0212
DP-FERMI ($\lambda=0.25$) |  0.7826 |  0.0195
DP-FERMI ($\lambda=0.5$) |  0.7777 |  0.0185
DP-FERMI ($\lambda=1$) |  0.7759 |  0.0105
DP-FERMI ($\lambda=2.5$) |  0.7669 |  0.0110

TABLE XIII: Credit Card Dataset ($\varepsilon=9,\delta=10^{-5})$ \- GDP Accountant Method |  Accuracy |  Statistical Parity Gap
---|---|---
Algorithm 2 |  0.7961 |  0.0068
DP-FERMI ($\lambda=0.25$) |  0.7996 |  0.0188
DP-FERMI ($\lambda=0.35$) |  0.7950 |  0.0174
DP-FERMI ($\lambda=0.5$) |  0.7912 |  0.0172
DP-FERMI ($\lambda=1$) |  0.7895 |  0.0105
DP-FERMI ($\lambda=2.5$) |  0.7884 |  0.0066