capbtabboxtable[][]

# Identification, Amplification and Measurement: A bridge to Gaussian
Differential Privacy

Yi Liu
Department of Mathematical
and Statistical Sciences
University of Alberta
<EMAIL_ADDRESS>
&Ke Sun
Department of Mathematical
and Statistical Sciences
University of Alberta
<EMAIL_ADDRESS>Bei Jiang
Department of Mathematical
and Statistical Sciences
University of Alberta
<EMAIL_ADDRESS>&Linglong Kong
Department of Mathematical
and Statistical Sciences
University of Alberta
<EMAIL_ADDRESS>
###### Abstract

Gaussian differential privacy (GDP) is a single-parameter family of privacy
notions that provides coherent guarantees to avoid the exposure of sensitive
individual information. Despite the extra interpretability and tighter bounds
under composition GDP provides, many widely used mechanisms (e.g., the Laplace
mechanism) inherently provide GDP guarantees but often fail to take advantage
of this new framework because their privacy guarantees were derived under a
different background. In this paper, we study the asymptotic properties of
privacy profiles and develop a simple criterion to identify algorithms with
GDP properties. We propose an efficient method for GDP algorithms to narrow
down possible values of an optimal privacy measurement, $\mu$ with an
arbitrarily small and quantifiable margin of error. For non GDP algorithms, we
provide a post-processing procedure that can amplify existing privacy
guarantees to meet the GDP condition. As applications, we compare two single-
parameter families of privacy notions, $\epsilon$-DP, and $\mu$-GDP, and show
that all $\epsilon$-DP algorithms are intrinsically also GDP. Lastly, we show
that the combination of our measurement process and the composition theorem of
GDP is a powerful and convenient tool to handle compositions compared to the
traditional standard and advanced composition theorems.

##  1 Introduction

Recent years have seen explosive growth in the research and application of
data-driven machine learning. While data fuels advancement in this
unprecedented age of “big data”, concern for individual privacy has deepened
with the continued mining, transportation, and exchange of this new resource.
While expressions of privacy concerns can be traced back as early as 1969
miller1969personal , the concept of privacy is often perceived as “vague and
difficult to get into a right perspective” shils1966privacy . Through its
alluring convenience and promise of societal prosperity, the use of aggregated
data has long outstripped the capabilities of privacy protection measures.
Indeed, early privacy protection protocols relied on the ad hoc enforcement of
anonymization and offered little to no protection against the exposure of
individual data, as evidenced by the AOL search log and Netflix Challenge
dataset controversies narayanan2006break ; narayanan2008robust ;
Barbaro2006expose .

Differential privacy (DP) first gained traction as it met the urgent need for
rigour and quantifiability in privacy protection dwork2006our . In short, DP
bounds the change in the distribution of outputs of a query made on a dataset
under an alteration of one data point. The following definition formalizes
this notion.

###### Definition 1.1

dwork2006our  A randomized algorithm $\mathcal{A}$, taking a dataset
consisting of individuals as its input, is $(\epsilon,\delta)$-differentially
private if, for any pair of datasets $S$ and $S^{\prime}$ that differ in the
record of a single individual and any event $E$,

$P[\mathcal{A}(S)\in E]\leq
e^{\epsilon}P\left[\mathcal{A}\left(S^{\prime}\right)\in E\right]+\delta.$

When $\delta=0$, $\mathcal{A}$ is called $\epsilon$-differentially private
($\epsilon$-DP).

While the notion of $(\epsilon,\delta)$-DP has wide applications
dankar2012application ; erlingsson2014rappor ; cormode2018privacy ;
hassan2019differential , there are a few notable drawbacks to this framework.
One is the poor interpretability of $(\epsilon,\delta)$-DP: unlike other
concepts in machine learning, DP should not remain a black box. Privacy
guarantees are intended for human interpretation and so must be understandable
by the users it affects and by regulatory entities. A second drawback is
$(\epsilon,\delta)$-DP’s inferior composition properties and lack of
versatility. Here, “composition” refers to the ability for DP properties to be
inherited when DP algorithms are combined and used as building blocks. As an
example, the training of deep learning models involves gradient evaluations
and weight updates: each of these steps can be treated as a building block. It
is natural to expect that a DP learning algorithm can be built using
differentially-private versions of these components. However, the DP
composition properties cannot generally be well characterized within the
framework of $(\epsilon,\delta)$-DP, leading to very loose composition
theorems.

To overcome the drawbacks of $(\epsilon,\delta)$-DP, numerous variants have
been developed, including the hypothesis-testing-based $f$-DP
wasserman2010statistical ; dong2019gaussian , the moments-accountant-based
Rényi DP mironov2017renyi , as well as concentrated DP and its variants
dwork2016concentrated ; bun2018composable . Despite their very different
perspectives, all of these DP variants can be fully characterized by an
infinite union of $(\epsilon,\delta)$-DP guarantees. In particular, there is a
two-way embedding between $f$-DP and the infinite union of
$(\epsilon,\delta)$-DP guarantees: any guarantee provided by an infinite union
of $(\epsilon,\delta)$-DP can be fully characterized by $f$-DP and vice visa
dong2019gaussian . Consequently, $f$-DP has the versatility to treat all of
the above notions as special cases.

In addition to its versatility, $f$-DP is more interpretable than other DP
paradigms because it considers privacy protection from an attacker’s
perspective. Under $f$-DP, an attacker is challenged with the hypothesis-
testing problem

$H_{0}:\text{ the underlying dataset is }S\text{ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
versus\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ }H_{1}:\text{ the underlying dataset is }S^{\prime}$

and given output of an algorithm $\mathcal{A}$, where $S$ and $S^{\prime}$ are
neighbouring datasets. The harder this testing problem is, the less privacy
leakage $\mathcal{A}$ has. To see this, consider the dilemma that the attacker
is facing. The attacker must reject either $H_{0}$ or $H_{1}$ based on the
given output of $\mathcal{A}$: this means the attacker must select a subset
$R_{0}$ of $\mathrm{Range}(\mathcal{A})$ and reject $H_{0}$ if the sampled
output is in $R_{0}$ (or must otherwise reject $H_{1}$). The attacker is more
likely to incorrectly reject $H_{0}$ (in a type I error) when $R_{0}$ is
large. Conversely, if $R_{0}$ is small, the attacker is more likely to
incorrectly reject $H_{1}$ (in a type II error). We say that an algorithm
$\mathcal{A}$ is $f$-DP if, for any $\alpha\in[0,1]$, no attacker can
simultaneously bound the probability of type I error below $\alpha$ and bound
the probability of type II error below $f(\alpha)$. Such $f$ is called a
trade-off function and controls the strength of the privacy protection.

The versatility afforded by $f$ can be unwieldy in practice. Although $f$-DP
is capable of handling composition and can embed other notions of differential
privacy, it is not convenient for representing safety levels as a curve
amenable to human interpretation. Gaussian differential privacy (GDP), as a
parametric family of $f$-DP guarantees, provides a balance between
interpretability and versatility. GDP guarantees are parameterized by a single
value $\mu$ and use the trade-off function
$f(\alpha)=\Phi\left(\Phi^{-1}(1-\alpha)-\mu\right)$, where $\Phi$ is the
cumulative distribution function of the standard normal distribution. With
this choice of $f$, the hypothesis-testing problem faced by the attacker is as
hard as distinguishing between $N(0,1)$ and $N(\mu,1)$ on the basis of a
single observation. Aside from its visual interpretation, GDP also has unique
composition theorems: the composition of a $\mu_{1}$\- and $\mu_{2}$-GDP
algorithm is, as expected, $\sqrt{\mu_{1}^{2}+\mu_{2}^{2}}$-GDP. This property
can be easily generalized to $n$-fold composition. GDP also has a special
central limit theorem implying that all hypothesis-testing-based definitions
of privacy converge to GDP in terms of a limit in the number of compositions.
Readers are referred to dong2019gaussian  for more information.

###  1.1 Outline

The goal of this paper is to provide a bridge between GDP and algorithms
developed under other DP frameworks. We start by presenting an often-
overlooked partial order on $(\epsilon,\delta)$-DP conditions induced by
logical implication. Ignoring this partial order will lead to problematic
asymptotic analysis.

We then break down GDP into two parts: a head condition and a tail condition.
We show that the latter, through a single limit of a mechanism’s privacy
profile, is sufficient to distinguish between GDP and non-GDP algorithms. For
GDP algorithms, this criterion also provides a lower bound for the privacy
protection parameter $\mu$ and can help researchers widen the set of available
GDP algorithms. This criterion furthermore gives an interesting
characterization of GDP without an explicit reference to the Gaussian
distribution.

The next logical step is to measure the exact privacy performance.
Interestingly, while the binary “GDP or not” question can be answered solely
by the tail, the actual performance of a DP algorithm is determined by the
head. We define and apply the Gaussian Differential Privacy Transformation
(GDPT) to narrow the set of potential optimal values of $\mu$ with an
arbitrarily small and quantifiable margin of error. We further provide
procedure to adapt an algorithm to GDP or improve the privacy parameter when
results from the GDP identification and measurement procedures are
undesirable.

Lastly, we demonstrate additional applications of our newly developed tools.
We first make a comparison between DP and GDP and show that any $\epsilon$-DP
algorithm is automatically GDP. We then show that the combination of our
measurement process and the GDP composition theorem is a more powerful and
convenient tool for handling compositions relative to traditional composition
theorems.

##  2 Privacy profiles and an exact partial order on $(\epsilon,\delta)$-DP
conditions

The benefits of DP come with a price. As outlined in the definition of DP, any
DP algorithm must be randomized. This randomization is usually achieved by
perturbing the intermediate step or the final output via the injection of
random noise. Because of the noise, a DP algorithm cannot faithfully output
the truth like its non DP counterpart. To provide a higher level of privacy
protection, a stronger utility compromise should be made. This leads to the
paramount problem of the “privacy–utility trade-off”. Under the
$(\epsilon,\delta)$-DP framework, this trade-off is often characterized in a
form of $\sigma=f(\epsilon,\delta)$: to achieve $(\epsilon,\delta)$-DP, the
utility parameter (usually the scale of noise) needs to be chosen as
$f(\epsilon,\delta)$. Therefore, an algorithm can be $(\epsilon,\delta)$-DP
for multiple pairs of $\epsilon$ and $\delta$: the union of all such pairs
provides a complete image of the algorithm under the $(\epsilon,\delta)$-DP
framework. In particular, an $(\epsilon,\delta)$-DP mechanism $\mathcal{A}$ is
also $(\epsilon^{\prime},\delta^{\prime})$-DP for any
$\epsilon^{\prime}\geq\epsilon$ and any $\delta^{\prime}\geq\delta$. The
infinite union of $(\epsilon,\delta)$ pairs can thus be represented as the
smallest $\delta$ associated with each $\epsilon$. This intuition is
formulated as a privacy profile in balle2018improving . The privacy profile
corresponding to a collection of $(\epsilon,\delta)$-DP guarantees $\Omega$ is
defined as the curve in $[0,\infty)\times[0,1]$ separating the space of
privacy parameters into two regions, one of which contains exactly the pairs
in $\Omega$. The privacy profile provides as much information as $\Omega$
itself. Many privacy guarantees and privacy notions, including
$(\epsilon,\delta)$-DP, Rényi DP, $f$-DP, GDP, and concentrated DP, can be
embedded into a family of privacy profile curves and fully characterized
balle2020privacy . A privacy profile can be provided or derived by an
algorithm’s designer or users.

Before proceeding with detailed discussions, we first give three examples of
DP algorithms that are used throughout the paper. The first example we
consider is the Laplace mechanism, a classical DP mechanism whose prototype is
discussed in the paper that originally defined the concept of differential
privacy dwork2006our . The level of privacy that the Laplace mechanism can
provide is determined by the scale $b$ of the added Laplacian noise. Given a
global sensitivity $\Delta$, the value of $b$ needs to be chosen as
$f(\epsilon,0)=\Delta/\epsilon$ in order to provide an $(\epsilon,0)$-DP
guarantee. Despite its long history, the Laplace mechanism has remained in use
and study in recent years phan2017adaptive ; hu2019learning ; xu2020deep ;
li2021differentially . Our second example is a family of algorithms in which a
noise parameter has the form $\sigma=A\epsilon^{-1}\sqrt{\log(B/\delta)}$.
Examples include: the goodness of fit algorithm gaboardi2016differentially ,
noisy stochastic gradient descent and its variants bassily2014private ;
abadi2016deep ; feldman2018privacy  and the one-shot spectral method and the
one-shot Laplace algorithm pmlroneshot . Our third example comes from the
field of federated learning: given $n$ users and the number of messages $m$,
the invisibility cloak encoder algorithm (ICEA) from ishai2006cryptography  is
$(\epsilon,\delta)$-DP if $m>10\log(n/(\epsilon\delta))$ ghazi2019scalable .
See also balle2020private ; ghazi2020private  for other analysis of ICEA.

For figures and numerical demonstrations in this paper, we use $b=2/\Delta$
for the Laplace mechanism; $A=2$, $B=1$, and $\sigma=2$ for the second
example, which we refer to as SGD; and $m=20$ and $n=4$ for the ICEA. We omit
the internal details of these methods and focus on their privacy guarantees:
other than for the classical Laplace mechanism, whose privacy profile is known
balle2020privacy , privacy guarantees are given in the form of a
privacy–utility trade-off equation $\sigma=g(\epsilon,\delta)$. Given
$\sigma$, it is tempting to derive the privacy profile by inverting $g$ (i.e.,
as
$\delta_{\mathcal{A}}(\epsilon)=\min\\{\delta\mid\sigma=g(\epsilon,\delta)\\}$)
because an $(\epsilon_{0},\delta_{0})$-DP algorithm is trivially
$(\epsilon,\delta)$-DP for any $\epsilon\geq\epsilon_{0}$ and
$\delta\geq\delta_{0}$. However, in most cases, a privacy profile naively
derived in this way is not tight and will lead to a problematic asymptotic
analysis, especially near the origin, because of a frequently overlooked
partial order between $(\epsilon,\delta)$-DP conditions below.

###### Theorem 2.1

Assume that $\epsilon_{0}\geq 0$ and $0\leq\delta_{0}<1$. The
$(\epsilon_{0},\delta_{0})$-DP condition implies $(\epsilon,\delta)$-DP if and
only if
$\delta\geq\delta_{0}+(1-\delta_{0})(e^{\epsilon_{0}}-e^{\epsilon})^{+}/(1+e^{\epsilon_{0}})$.

Theorem 2.1 states the exact partial order of logical implication on
$(\epsilon,\delta)$-DP conditions. Though not being explicitly discussed in
this form in previous literature on DP, this partial order can be implicitly
derived from other results (e.g. proposition 2.11 of dong2019gaussian ).
Taking this partial order into account, the privacy profile derived from the
naive inversion of the trade-off function can be refined into

$\delta_{\mathcal{A}}(\epsilon)=\min\left(\left\\{\delta\mid\sigma=g(\epsilon_{0},\delta_{0})\text{
and
}\delta\geq\delta_{0}+\frac{(1-\delta_{0})(e^{\epsilon_{0}}-e^{\epsilon})^{+}}{1+e^{\epsilon_{0}}}\right\\}\right).$

Intuitively, the refined privacy profile not only considers
$(\epsilon,\delta)$-DP provided directly by the trade-off function but also
takes all pairs $(\epsilon,\delta)$ inferred by corollary 2.1. See figure 1
for comparsion before and after this refinement.

##  3 The identification of GDP algorithms

We next show the connection between GDP and the privacy profile: briefly,
Gaussian differential privacy can be characterized as an infinite union of
$(\epsilon,\delta)$-DP conditions.

###### Theorem 3.1

([Corollary 2.13 dong2019gaussian ) A mechanism is $\mu$-GDP if and only if it
is $(\epsilon,\delta_{\mu}(\epsilon))$-DP for all $\epsilon\geq 0$, where

$\delta_{\mu}(\epsilon)=\Phi\left(-\frac{\epsilon}{\mu}+\frac{\mu}{2}\right)-\mathrm{e}^{\epsilon}\Phi\left(-\frac{\epsilon}{\mu}-\frac{\mu}{2}\right).$
(1)

This result follows from properties of $f$-DP. Prior to this general form, a
expression for a special case appeared in balle2018improving . From the
definition of the privacy profile, it follows immediately that an algorithm
$\mathcal{A}$ with the privacy profile $\delta_{\mathcal{A}}$ is $\mu$-GDP if
and only if $\delta_{\mu}(\epsilon)\geq\delta_{\mathcal{A}}(\epsilon)$ for all
non-negative $\epsilon$. However, this observation does not automatically lead
to a meaningful way to identify GDP algorithms.

Before proceeding with an analysis of privacy profiles, we give a few visual
examples in Figure 1. The left side of1 illustrates the privacy profiles of
our examples. That of the Laplace mechanism is derived in balle2020privacy  as
Theorem 3: given a noise parameter $b$ and a global sensitivity $\Delta$, the
privacy profile of the Laplace mechanism is
$\delta(\epsilon)=\max(1-\exp\\{\varepsilon/2-\Delta/(2b)\\},\ 0)$. For the
second and the third examples, we compare the naive privacy profiles obtained
by inverting the trade-off function with the refined privacy profiles. The
refined and naive privacy profiles take on notably different values around
$\epsilon=0$. The inverted trade-off functions suggest that $(0,\delta)$
cannot be achieved by any choice of parameter $\sigma$. However, this is
clearly not true, considering Theorem 2.1.

As shown in right side of Figure 1, the Laplace mechanism’s privacy profile is
below the 2-GDP and 4-GDP curves but crosses the 1-GDP curve, indicating that
the Laplace mechanism in this case is 2-GDP and 4-GDP but not 1-GDP. The ICEA
curve intersects all of the displayed GDP curves, so the algorithm is not
$\mu$-GDP for $\mu\in\\{1,2,4\\}$. It is hard to tell whether or not the SGD
curve crosses the 1-GDP curve and we cannot say if it will cross the 2-GDP or
even the 4-GDP curve at a large value of $\epsilon$. These examples illustrate
that we cannot draw conclusions simply by looking at a graph. A privacy
profile is defined on $[0,\infty)$, so it is hard to tell if an inequality is
maintained as $\epsilon$ increases. Previous failures of ad hoc attempts at
privacy have taught that privacy must be protected via tractable and objective
means narayanan2006break ; narayanan2008robust ; Barbaro2006expose .

Figure 1: Left: Examples of privacy profiles obtained by inverting the trade-
off function (naive) and by Theorem 2.1 (refined). Right: Comparison of 1-GDP
and 2-GDP privacy profiles against those for our three examples.

Performing this check via numerical evaluation yields similar problems: we
cannot consider all values of $\epsilon$ on an infinite interval (or even a
finite one, for that matter). Turning to closed forms for privacy profiles and
$\delta_{\mu}$ is also difficult: even if a given privacy profile is easy to
handle, $\delta_{\mu}$ presents some technical hurdles. The profile
$\delta_{\mu}$ and $\Phi$ are transcendental with different asymptotic
behaviors for different values of $\mu$ and $\epsilon$. This is clear from the
Figure 1: near $\epsilon=0$, $\delta_{\mu}$ is concave for $\mu=4$ but convex
for $\mu=1$. As a further complication, both the first and second terms in the
definition of $\delta_{\mu}$ converge to $1$ as $\epsilon\rightarrow\infty$,
but the difference between them vanishes. Subtracting good approximations of
two nearby numbers may cause a phenomenon called catastrophic cancellation and
lead to very bad approximations malcolm1971accurate ; cuyt2001remarkable . Due
to the risk of catastrophic cancellation, a good approximation of $\Phi$ does
not guarantee a good approximation of the GDP privacy profile. These problems
make it difficult to tightly bound $\delta_{\mu}$ by a function with a simple
form.

To address the problem of differing asymptotic behaviours, we define the
following two notions.

###### Definition 3.1

(Head condition) An algorithm $\mathcal{A}$ with the privacy profile
$\delta_{\mathcal{A}}$ is $(\epsilon_{h},\mu)$-head GDP if and only if
$\delta_{\mathcal{A}}(\epsilon)\leq\delta_{\mu}(\epsilon)$ when
$\epsilon\leq\epsilon_{h}$.

###### Definition 3.2

(Tail condition) An algorithm $\mathcal{A}$ with the privacy profile
$\delta_{\mathcal{A}}$ is $(\epsilon_{t},\mu)$-tail GDP if and only if
$\delta_{\mathcal{A}}(\epsilon)\leq\delta_{\mu}(\epsilon)$ when
$\epsilon>\epsilon_{t}$.

The head condition checks the $\mu$-GDP condition for $\epsilon$ near zero and
the tail condition checks the $\mu$-GDP condition for $\epsilon$ far away from
zero. As such, the combination of $(\epsilon,\mu)$-head GDP and
$(\epsilon,\mu)$-tail GDP is equivalent to $\mu$-GDP. For now, we put the
exact value of $\mu$ aside and consider only the qualitative question of how
to identify a GDP algorithm by its privacy profile. The following theorem
answers this question.

###### Theorem 3.2

An algorithm $\mathcal{A}$ is GDP if and only if $\mathcal{A}$ is
$(\epsilon,\mu)$-tail GDP for any finite $\epsilon$ and $\mu$.

Interestingly, only the tail condition figures into the identification
problem. The reason for this stems from theorem 2.1. Any nontrivial
$(\epsilon,\delta)$-DP algorithm must be $(0,\delta)$-DP for some $\delta<1$
and therefore must satisfy a head condition for some sufficiently large $\mu$.
The only problem left is the tail. However, it is not possible to check
whether $\delta(\epsilon)<\delta_{\mu}(\epsilon)$ for all values of
$\epsilon$. To circumvent this issue, we present a key lemma that underlies
much of the theoretical analysis in this section and may continue to be useful
in future developments.

###### Lemma 3.1

Define $\tilde{\delta}_{\mu}(\epsilon)=\frac{\mu
e^{-a^{2}/2}}{\sqrt{2\pi}a^{2}}$, where
$a=-\frac{\epsilon}{\mu}+\frac{\mu}{2}$. It follows that
$\lim\limits_{\epsilon\rightarrow+\infty}\frac{\delta_{\mu}(\epsilon)}{\tilde{\delta}_{\mu}(\epsilon)}=1$.

Using the key lemma above, a condition for identifying GDP algorithms is
simple to formulate:

###### Theorem 3.3

Let
$\mu_{t}=\sqrt{\lim\limits_{\epsilon\rightarrow+\infty}\frac{\epsilon^{2}}{-2\log{\delta_{\mathcal{A}}(\epsilon)}}}$.
An algorithm $\mathcal{A}$ with the privacy profile
$\delta_{\mathcal{A}}(\epsilon)$ is $\mu$-GDP if and only if $\mu_{t}<\infty$
and $\mu$ is no smaller than $\mu_{t}$.

Theorems 3.2 and 3.3 give a useful criterion characterizing GDP and deepen our
understanding of GDP. Putting the exact value of $\mu$ aside, a GDP algorithm
must provide an infinite union of $(\epsilon,\delta)$-DP conditions, where
$\delta$ must be $O(e^{-\epsilon^{2}})$ as $\epsilon\rightarrow\infty$. Refer
to Appendices B.3 for proofs of Theorems.

##  4 The Gaussian differential privacy transformation

While the binary “GDP or not” question can be answered solely by the tail
condition, the actual performance of a DP algorithm is determined by the value
of its privacy profile for small values of $\epsilon$: intuitively, all
$(\epsilon_{t},\mu)$-tail conditions are weaker than the corresponding
$\epsilon_{t}$-DP condition, and the latter provides almost no privacy when
$\epsilon_{t}>10$. A more detailed discussion will be presented in 4.2. To
solve the measurement problem, we first propose a new tool—the Gaussian
differential privacy transformation (GDPT).

###### Definition 4.1

(GDPT) Let $f$ be a non-increasing, non-negative function defined on
$[0,+\infty)$ satisfying $f(0)\leq 1$. The Gaussian differential privacy
transformation (GDPT) of $f$ is the function $G_{f}$ mapping $[0,\infty)$ to
$[0,\infty)$ such that
$G_{f}(\epsilon)=\mu_{{}_{\text{GDP}}}(\epsilon,f(\epsilon))$, where
$\mu_{{}_{\text{GDP}}}(x,y)$ is the implicit function defined by the equation
$\delta_{\mu}(x)=y$.

We highlight two critical features of the GDPT.

  * •

The GDPT is order preserving: if $f(\epsilon)\geq g(\epsilon)$, then
$G_{f}(\epsilon)\geq G_{g}(\epsilon)$.

  * •

The GDPT of $\delta_{\mu}$ is $G_{\delta_{\mu}}(\epsilon)=\mu$, a constant
function.

The first of these two features derive from the monotonicity of
$\delta_{\mu}(\epsilon)$. Given a fixed $\mu$, $\delta_{\mu}(\epsilon)$ is a
strictly decreasing continuous function of $\epsilon$. Given a fixed
$\epsilon$, $\delta_{\mu}(\epsilon)$ is a strictly increasing continuous
function of $\mu$. Therefore, $\mu_{{}_{\text{GDP}}}(x,y)$ is an increasing
function of $y$: this leads to the order-preserving property. The second
property follows immediately from the definition of $\mu_{{}_{\text{GDP}}}$.

By taking advantage of the order-preserving property, direct comparisons
between $\delta_{\mu}$ and $\delta_{\mathcal{A}}$ are no longer necessary:
instead, it is sufficient to compare their corresponding GDPTs. Furthermore,
appealing to the second property above, we need only compare $G_{\mathcal{A}}$
to the constant function $\mu$. The following theorems formalize this insight.

###### Corollary 4.1

An algorithm $\mathcal{A}$ with the privacy profile $\delta_{\mathcal{A}}$ is
$\mu$-GDP if and only if
$\mu\geq\sup(\\{G_{\mathcal{A}}(\epsilon)\mid\epsilon\in[0,\infty)\\})$.

###### Theorem 4.1

An algorithm $\mathcal{A}$ with the privacy profile $\delta_{\mathcal{A}}$ is
$(\epsilon_{h},\mu)$-head GDP or $(\epsilon_{t},\mu)$-tail GDP if and only if
$\mu\geq\sup(\\{G_{\mathcal{A}}(\epsilon)\mid\epsilon\in[0,\epsilon_{h}])$ or
$\mu\geq\sup(\\{G_{\mathcal{A}}(\epsilon)\mid\epsilon\in(\epsilon_{t},\infty))$,
respectively.

Without the above results, we would be forced to search through a large family
of functions for a single $\delta_{\mu}$ that never crosses
$\delta_{\mathcal{A}}$ anywhere on $[0,\infty)$ and has $\mu$ as small as
possible. Now, with Theorem 4.1, we need only consider one function: the GDPT
of $\delta_{\mathcal{A}}$. The tightest value $\mu$ is
$\sup_{\epsilon}\\{G_{\mathcal{A}}(\epsilon)\\}$. Now we revisit our previous
three examples for which the limit in Theorem 3.3 is $0$, $\sqrt{1/2}$, and
$+\infty$, respectively. From these evaluations, we can conclude that the
Laplace mechanism and SGD are GDP and that the privacy profile of the ICEA
algorithm crosses every $\mu$-GDP curve regardless of how large $\mu$ is,
indicating that the ICEA algorithm is not GDP.

Figure 2: Left: Examples of GDPTs. Right: Plot of $G^{+}_{\mathcal{A}}$ and
$G^{-}_{\mathcal{A}}$ with different values of $d$.

Left side of figure 2 shows the GDPTs of the three examples considered in this
paper. All three GDPTs converge to a finite value as $\epsilon\rightarrow
0^{+}$. This can be attributed to the fact that any algorithm providing some
non-trivial $(\epsilon,\delta)$-DP guarantee is $(0,\delta)$-DP for some
$\delta\in[0,1)$ (by theorem 2.1). For larger values of $\epsilon$, the GDPT
of the Laplace mechanism takes on a constant value of $0$, the GDPT of SGD
converges to a value that is approximately $0.7$, and the GDPT of the ICEA
seems to be diverging. These observations are consistent with the values of
$0$, $\sqrt{1/2}$, and $\infty$ obtained from Theorem 3.3. Once an algorithm
is confirmed to be GDP via Theorems 3.2 and 3.3, it is natural to be
interested in the exact level of privacy protection, quantified by $\mu$.
Nonetheless, plots are only good for visualization and are not sufficient
proof when verifying GDP. We still need objective and tractable methods for
obtaining bounds on GDPTs.

###  4.1 Measuring the head

Following the intuition outlined by definition 3.1 and 3.2, we decompose the
GDP condition into head and tail conditions and first focus on finding $\mu$
such that $\mathcal{A}$ is $(\epsilon,\mu)$-head GDP. Without additional
knowledge, finding
$\sup\\{G_{\mathcal{A}}(\epsilon)\mid\epsilon\in[0,\epsilon_{h}]\\}$, even for
a finite $\epsilon_{h}$, seems computationally infeasible. To solve this
problem, we take advantage of the fact that $\mu_{{}_{\text{GDP}}}$ has a
uniformly bounded partial derivative.

###### Theorem 4.2

$0\leq\frac{\partial\mu_{{}_{\text{GDP}}}(\epsilon,\delta)}{\partial\epsilon}\leq\frac{\sqrt{2}\pi}{2}.$

The first half of the inequality above is no surprise to us: the GDP privacy
measurement $\mu$ is expected to be larger when $\epsilon$ is larger. However,
the second half allow us to only conduct the search on a finite list of
$\epsilon$ without the concern of spikes in between. We formulate this insight
as the following theorem:

###### Theorem 4.3

Given $\epsilon_{h}\geq 0$, let $d=\epsilon_{h}/n$ and $x_{i}=id$ for
$i\in\\{0,\dots,n+1\\}$. For $\epsilon\leq\epsilon_{h}$, the GDPT of
$\mathcal{A}$, denoted by $G_{\mathcal{A}}(\epsilon)$, is bounded between the
two staircase functions

$G_{\mathcal{A}}^{-}(\epsilon)=\sum\limits_{i=0}^{n+1}\mu_{{}_{\text{GDP}}}(x_{i},\delta_{\mathcal{A}}(x_{i+1}))\times\displaystyle
1_{\mathrm{\epsilon\in[x_{i},x_{i+1})}}\text{ \leavevmode\nobreak\
and\leavevmode\nobreak\
}G_{\mathcal{A}}^{+}(\epsilon)=\sum\limits_{i=0}^{n+1}\mu_{{}_{\text{GDP}}}(x_{i+1},\delta_{\mathcal{A}}(x_{i}))\times\displaystyle
1_{\mathrm{\epsilon\in[x_{i},x_{i+1})}}.$

Specifically,

$\max_{i\in\\{0,\dots,n\\}}{G_{\mathcal{A}}^{-}(x_{i})}\leq\max_{\epsilon\in[0,\epsilon_{h}]}G_{\mathcal{A}}(\epsilon)\leq\max_{i\in\\{0,\dots,n+1\\}}{G_{\mathcal{A}}^{+}(x_{i})}\leq\max_{i\in\\{0,\dots,n\\}}{G_{\mathcal{A}}^{-}(x_{i})}+\sqrt{2}\pi
d.$ (2)

Refer to Appendix B.5 and B.6 for proofs of Theorem 4.2 and 4.3, respectively.

For any $\epsilon_{h}<+\infty$, we can now bound any GDPT $G_{\mathcal{A}}$ to
any precision on $[0,\epsilon_{h}]$ without full pointwise evaluation because
$G_{\mathcal{A}}$ is bounded between $G_{\mathcal{A}}^{+}$ and
$G_{\mathcal{A}}^{-}$ and each staircase function takes on only finitely many
values. For any $c>0$, the inequalities in (2) provide a viable way to bound
$\max_{\epsilon\in[0,\epsilon_{h}]}G_{\mathcal{A}}(\epsilon)$ in an interval
with a length no greater than $1/c$.

First, a binary search algorithm (algorithm 2 in Appendix D) can yield
$\mu^{+}$ and $\mu^{-}$ such that
$\mu^{-}\leq\mu_{{}_{\text{GDP}}}(\epsilon,\delta)\leq\mu^{+}$ and
$\mu^{+}-\mu^{-}<b$. For future references, we use
$\mu_{{}_{\text{GDP}}}^{+}(\epsilon,\delta,b)$ and
$\mu_{{}_{\text{GDP}}}^{-}(\epsilon,\delta,b)$ to represent such outputs of
$\mu^{+}$ and $\mu^{-}$, respectively. Therefore, we can naively go thorough
all $G_{\mathcal{A}}^{-}(x_{i})$ and $G_{\mathcal{A}}^{+}(x_{i})$. By picking
$n=\left\lceil\sqrt{8}c\pi\epsilon_{h}\right\rceil+1$ and $b=\frac{1}{2c}$,
the true gap between $\max G_{\mathcal{A}}^{-}(\epsilon)$ and $\max
G_{\mathcal{A}}^{+}(\epsilon)$ is less than $\frac{1}{2c}$ and the error
margin of the binary search estimate the $\mu_{{}_{\text{GDP}}}$ is also
$\frac{1}{2c}$. Therefore, the overall gap is bounded by $\frac{1}{c}$. As for
complexity, each binary search has a time complexity of $O(\log(c))$ and the
number of binary searches is $2n+2=O(\epsilon_{h}c)$. The overall time
complexity of this naive approach is $O(\epsilon_{h}c\log(c))$. For a complete
pseudocode of this naive approach, refer to algorithm 3 in Appendix D.

By leveraging some properties of $\mu_{{}_{\text{GDP}}}$ and shuffling, the
expected number of binary searches need can be reduced from linear
($2n+2\approx c\epsilon_{h}$) to logarithmic $(O(\log(c\epsilon_{h})))$. Such
reduction will eliminate the logarithmic term in the time complexity from the
naive algorithm. The improved algorithm is given as Algorithm 1 below.

Algorithm 1 Finding $\mu$ with privacy profiles (optimized).

Input: $\delta_{\mathcal{A}}$, $\epsilon_{h}$, $\mu_{t}$, $c$. (Privacy
profile, searching range $\epsilon_{h}$, reciprocal of error margin)

$n\leftarrow\left\lceil\sqrt{8}c\pi\epsilon_{h}\right\rceil+1$

$d\leftarrow\frac{\epsilon_{h}}{n-1}$

$\mu_{-}\leftarrow 0$

$\mu_{+}\leftarrow 0$

$\mathcal{S}$ = [0, 1, $\cdots$, $n+1$]

Shuffle $\mathcal{S}$

for $i=0$ to $n+1$ do

$x^{-}\leftarrow S[i]d$

$x^{+}\leftarrow(S[i]+1)d$

if $\delta_{\mu^{+}}(x^{-})<\delta_{\mathcal{A}}(x^{+})$ then

$\mu^{+}\leftarrow\mu_{{}_{\text{GDP}}}^{+}(x^{-},\delta_{\mathcal{A}}(x^{+}),\frac{1}{2c}))$

end if

if $\delta_{\mu^{-}}(x^{+})<\delta_{\mathcal{A}}(x^{-})$ then

$\mu^{-}\leftarrow\mu_{{}_{\text{GDP}}}^{-}(x^{+},\delta_{\mathcal{A}}(x^{-}),\frac{1}{2c}))$

end if

end for

Output:$\mu_{-}$, $\mu_{+}$ (lower and upper bound of $\mu$).

We remark that this algorithm also has better accuracy than the naive
algorithm because the lower and upper bounds will be closer while maintaining
coverage. Refer to Appendix D for an detailed explanation of this algorithm.

###  4.2 Understanding the tail

With Theorem 4.3, one can verify $(\epsilon_{h},\mu)$-head GDP conditions for
arbitrarily large $\epsilon_{h}$ and an arbitrarily precise approximation of
$\mu$. While the error in $\mu$ can be quantified by $D$, one gap remains:
$\epsilon_{h}$ can be arbitrarily large but can never truly be $+\infty$. In
this subsection, we discuss the gap between $(\epsilon_{h},\mu)$-head GDP and
true GDP (which is equivalent to $(+\infty,\mu)$-head GDP). Before giving a
solution, we intuitively illustrate the gap between $(\epsilon_{h},\mu)$-head
GDP and true GDP. Consider the following two cases:

  * •

GDP with catastrophic failure, where with probability $1-p$, $\mathcal{A}_{1}$
functions properly as $\mu$-GDP, with probability $p$, $\mathcal{A}_{1}$
malfunctions and discloses the entire dataset; and

  * •

head-GDP with $\epsilon$-DP, where $\mathcal{A}_{2}$ is both
$(\epsilon_{h},\mu)$-head GDP and $(\epsilon_{h},0)$-DP.

The head GDP privacy guarantee lies strictly between those of
$\mathcal{A}_{1}$ and $\mathcal{A}_{2}$: specifically,
$\delta_{\mathcal{A}_{1}}(\epsilon)<\delta(\epsilon)<\delta_{\mathcal{A}_{2}}(\epsilon)$.
As an interpretation of this inequality, a head GDP privacy guarantee is safer
than the original GDP guarantee but with a minuscule probability of failure,
and when combined with a very weak $\epsilon$-DP condition, the head GDP will
be stronger than the actual GDP. In practice, $\mu$ is rarely above six in GDP
and $\epsilon$ is rarely above $10$ in $\epsilon$-DP because more-extreme
values provide almost no privacy protection dong2019gaussian . If we verify
the head condition up to $\epsilon_{h}=100$ (which is not difficult because
the time required for verification grows linearly) and take $\mu=6$, then
$p=\delta_{\mu}(\epsilon_{h})$ will be on the order of $10^{-43}$. Also, DP
guarantee for $\epsilon$ this large is rarely considered to provide real
protection. Hence, we conclude that the gap won’t make any notable difference
in practice with a proper choice of $\mu$ and $\epsilon_{h}$.

###  4.3 Amplification

In some cases, one may still wish to theoretically mend the gap discussed in
the last subsection. This can be achieved by adding extra steps to perturb the
output of the algorithm (i.e., via post-processing). We propose the following
“clip and rectify” procedure that can turn any $(\epsilon_{h},\mu)$-head GDP
algorithm into a $\mu$-GDP algorithm at the cost of some utility.

###### Theorem 4.4

Let $\mathcal{A}$ be an $(\epsilon_{h},\mu)$-head GDP algorithm with a numeric
output. Assume that $-\infty<y^{-}<y^{+}<+\infty$. Define
$\mathcal{C}(y)=\max(\min(y,y^{+}),y^{-})$ and $\mathcal{R}(z)=z+v$, where v
is sampled from $\mathrm{Laplace}(b)$ with $b=(y^{+}-y^{-})/\epsilon_{h}$.
Then $\mathcal{R}\circ\mathcal{C}\circ\mathcal{A}$ is $\mu$-GDP.

Refer to Appendix B.7 for a proof of Theorem 4.4. We remark that, in order to
minimize the utility loss, the bounds $y^{-}$ and $y^{+}$ should be properly
or dynamically chosen and the head condition should be verified to a value of
$\epsilon_{h}$ that is as large as possible.

On the other hand, the performance ($\mu$) of a GDP algorithm may be
bottlenecked by the value of its privacy profile near the origin. This problem
can be remedied by subsample pre-processing, the impact of which on privacy
profiles has been thoroughly examined in balle2020privacy . The resulting
privacy profile is explicitly given in Theorems 8–10 of balle2020privacy .
With the help of the GDPT, we can select different subsample ratios and
measure $\mu$. For instance, the Laplace example in this paper was originally
$1.80$-GDP. If we introduce a $50\%$\- or $10\%$\- Poisson subsampling before
the Laplace mechanism, $\mu$ will be reduced to $0.98$ or $0.28$,
respectively. Refer to E.2 for a complete graph of the new GDPTs.

While one could turn to other algorithms or design a new GDP mechanism in
unfavourable cases where a candidate algorithm is incompatible with GDP from
the start, rectifying these incompatibilities via pre- and post-processing may
be more effective and efficient. This is especially true in cases where raw
data is not easily accessible. In other cases, the DP mechanism might be
inaccessible. This is particularly common for users of proprietary software.
While they cannot identify and change the algorithm distributed in binary
code, users can still control sensitive information by only approving a subset
for release.

##  5 Applications

###  5.1 The Gaussian nature of $\epsilon$-DP and the Laplace mechanism

By our previous analysis of the GDPT, we know that being GDP means that a
privacy profile has a quickly vanishing tail (i.e., $\delta(\epsilon)$ must be
$O(e^{-\epsilon^{2}})$). It is remarkable that another single parameter family
of DP conditions, the $\epsilon$-DP conditions, is also a property that
pertains to the tail of privacy profiles. For any $\epsilon_{0}$-DP algorithm,
the privacy profile must be exactly $0$ after $\epsilon_{0}$. This suggests
that $\epsilon$-DP is stronger than GDP. Next, we will quantify this intuition
using the tools we developed above.

By Theorem 2.1, we know if $\mathcal{A}$ is $\epsilon_{0}$-DP, then in the
worst case,
$\delta_{\mathcal{A}}(\epsilon)=(e^{\epsilon_{0}}-e^{\epsilon})^{+}/(1+e^{\epsilon_{0}})$.

We consider the GDPT of $\delta_{\mathcal{A}}$, denoted by $G_{\mathcal{A}}$.
It is easy to see that, for $\epsilon\geq\epsilon_{0}$,
$G_{\mathcal{A}}(\epsilon)=0$: we need only consider
$\epsilon\in[0,\epsilon_{0})$. Let $G_{\delta_{\mathcal{A}}(\epsilon)}$ be
denoted by $\mu_{\epsilon}$. Using using the partial derivative of
$G_{\mathcal{A}}$ derived in Appendix B.5, we know that
$\frac{\partial}{\partial\epsilon}G_{\delta_{\mathcal{A}}(\epsilon)}=\sqrt{2\pi}\exp\left\\{\left(\mu_{\epsilon}^{2}+2\epsilon\right)^{2}/(8\mu_{\epsilon}^{2})\right\\}\left[\Phi(-\frac{\mu_{\epsilon}^{2}+2\epsilon}{2\mu_{\epsilon}})-\Phi(\frac{-\mu_{0}}{2})\right]$.
Then
$\mathrm{sign}(\frac{\partial}{\partial\epsilon}G_{\delta_{\mathcal{A}}(\epsilon)})=\mathrm{sign}(\mu_{\epsilon}-\mu_{0}-2\epsilon/\mu_{0})$.
We can conclude that $\mu_{\epsilon}\leq\mu_{0}$ and, further, that
$G_{\mathcal{A}}(\epsilon)$ is strictly decreasing on $[0,\epsilon_{0})$. By
Theorem 4.1, we know that $\mathcal{A}$ is $\mu_{0}$-GDP. This finding can be
more generally formulated as the following theorem.

###### Theorem 5.1

Any $(\epsilon,0)$-DP algorithm is also $\mu$-GDP for
$\mu=-2\Phi^{-1}(1/(1+e^{\epsilon}))\leq\sqrt{\pi/2}\epsilon$.

dong2019gaussian  pointed out that the DP guarantees of the Laplace mechanism
are stronger than those correspondingly provided by $\epsilon$-DP. We reaffirm
this difference by showing that it still exists under the GDP framework. The
Laplace mechanism satisfies $\mu$-GDP for $\mu$ smaller than the bound given
in Theorem 5.1. The GDPTs presented in Appendix E.1 illustrate this
difference.

###  5.2 Handling composition with GDP

In practice, it is rare for a dataset to go through DP algorithms only once.
Multiple statistics may be of interest or one statistic may require multiple
inquiries to acquire. DP algorithms applied to the same dataset multiple times
are usually still DP but with worse privacy parameters. Composition theorems
quantitatively trace privacy loss and provide a privacy parameter for the
ensemble. However, not only is exact composition an intrinsically (#P-)hard
problem murtagh2016complexity , but the conclusions of composition theorems
are also often problematic. Take traditional $(\epsilon,\delta)$-DP as an
example. kairouz2015composition  gives an optimal composition theorem, but the
composition of two $(\epsilon,\delta)$-DP algorithms cannot be characterized
under the $(\epsilon,\delta)$-DP framework. This result damages
interpretability because the representation of a composition will no longer be
in two parameters. This type of flaw is the major motivation for a GDP
characterization of algorithms derived under other DP frameworks. The
composition of GDP algorithms is easy, exact, and closed: the composition of a
$\mu_{1}$\- and $\mu_{2}$-GDP algorithm is simply
$\sqrt{\mu_{1}^{2}+\mu_{2}^{2}}$-GDP. GDP also has a special central limit
theorem which implies that, for all privacy definitions that retain hypothesis
testing with proper scaling, the privacy guarantee of a composition converges
to GDP in the limit. In this subsection, we demonstrate that GDP is a powerful
tool for composition by unifying other notions under the GDP framework and
then using the GDP composition theorem. As baselines, we select basic
composition dwork2006our , advanced composition dwork2010boosting  and Rényi-
DP mironov2017renyi .

We consider the 50-fold composition of $0.2$-DP algorithms. In this setting,
basic composition is pessimistic and says that the composition will be
$10$-DP, which means there is next to no privacy guarantee. According to
corollary 1 of mironov2017renyi , the bound given by RDP is even more loose.
Refer to Figure 3 for the results of other theorems.

We next consider composition using the proposed measurement method. According
to Theorem 5.1, a $0.2$-DP algorithm is $0.2505$-GDP. If the algorithm is the
Laplace mechanism, then the algorithm in Appendix D can tighten $\mu$ to
$0.2391$. To compute $\mu$ for a 50-fold composition, we simply multiply the
original $\mu$ by $\sqrt{50}$. The result is $1.771$-GDP ($1.691$ for the
Laplace mechanism). In this case, distinguishing two neighbouring datasets is
as hard as distinguishing between $N(0,1)$ and $N(1.771,1)$ on the basis of a
single observation.

Figure 3: The plot of privacy guarantee under different methods.

Method $\delta$ | $10^{-1}$ | $10^{-2}$ | $10^{-3}$ | $10^{-4}$
---|---|---|---|---
Basic | 9.89 | 9.99 | 10 | 10
Advanced | 5.25 | 6.51 | 7.47 | 8.28
RDP | 12.14 | 17.17 | 21.03 | 24.28
GDP | 3.1 | 5.06 | 6.47 | 7.62
GDP (Lap) | 2.87 | 4.74 | 6.09 | 7.19
Optimal | 2.12 | 3.64 | 4.76 | 5.28
GDP summary | 2.14 | 3.73 | 4.87 | 5.80

Figure 4: Minimum values of $\epsilon$ to achieve corresponding
$(\epsilon,\delta)$-DP.

In this particular case, the ground truth can be derived from the optimal
composition theorem kairouz2015composition . We present the results from the
optimal composition theorem in Table 1 and Figure 3 for comparison, but we do
not consider the optimal composition theorem to be generally superior because
the ground truth is not easy to compute and because the former method is not
as interpretable and only works for algorithms whose DP guarantees are fixed
at $(\epsilon,\delta)$. However, by applying the GDPT, the privacy guarantee
of the optimal composition theorem can be summarised as $1.420$-GDP . Compared
to the central limit theorem in dong2019gaussian  which yields $\mu=\sqrt{2}$
(with an unknown asymptotic approximation error) in the same setting, the
tractable numerical procedure of GDPT provides a satisfying result.

##  6 Conclusion and Future Work

In this paper, we provided both an analytic perspective of and engineering
tools for the GDP framework. By using the new notions we proposed, we devised
solutions to three aspects of GDP: identification, amplification, and
measurement. The developments in this paper suggest numerous interesting
directions for future work. First, the more refined methods can be derived to
expand the toolbox of rectification for more versatility. Second, the
measurement procedure can be combined with the rectification procedure.
Incrementally introducing more pre- and post-processing steps and dynamically
checking whether privacy guarantees are already satisfactory can also be
explored. Lastly, the idea underlying the GDPT can be generalized to other
parameterized DP notions like CDP or RDP to enrich tractability and
visualizability in the DP literature.

## References

  * [1] 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\.
  * [2] Milton Abramowitz, Irene A Stegun, and Robert H Romer.  Handbook of mathematical functions with formulas, graphs, and mathematical tables, 1988.
  * [3] Borja Balle, Gilles Barthe, and Marco Gaboardi.  Privacy profiles and amplification by subsampling.  Journal of Privacy and Confidentiality, 10(1), 2020.
  * [4] Borja Balle, James Bell, Adria Gascón, and Kobbi Nissim.  Private summation in the multi-message shuffle model.  In Proceedings of the 2020 ACM SIGSAC Conference on Computer and Communications Security, pages 657–676, 2020\.
  * [5] Borja Balle and Yu-Xiang Wang.  Improving the gaussian mechanism for differential privacy: Analytical calibration and optimal denoising.  In International Conference on Machine Learning, pages 394–403. PMLR, 2018.
  * [6] M. Barbaro and Jr. T. Zeller.  A face is exposed for aol searcher no. 4417749.  New York Times (Aug, 9, 2006), 2006.
  * [7] Raef Bassily, Adam Smith, and Abhradeep Thakurta.  Private empirical risk minimization: Efficient algorithms and tight error bounds.  In 2014 IEEE 55th Annual Symposium on Foundations of Computer Science, pages 464–473. IEEE, 2014.
  * [8] Mark Bun, Cynthia Dwork, Guy N Rothblum, and Thomas Steinke.  Composable and versatile privacy via truncated cdp.  In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, pages 74–86, 2018.
  * [9] Mark Bun and Thomas Steinke.  Concentrated differential privacy: Simplifications, extensions, and lower bounds.  volume 9985, pages 635–658, 11 2016.
  * [10] Graham Cormode, Somesh Jha, Tejas Kulkarni, Ninghui Li, Divesh Srivastava, and Tianhao Wang.  Privacy at scale: Local differential privacy in practice.  In Proceedings of the 2018 International Conference on Management of Data, pages 1655–1658, 2018.
  * [11] Annie Cuyt, Brigitte Verdonk, Stefan Becuwe, and Peter Kuterna.  A remarkable example of catastrophic cancellation unraveled.  Computing, 66(3):309–320, 2001.
  * [12] Fida Kamal Dankar and Khaled El Emam.  The application of differential privacy to health data.  In Proceedings of the 2012 Joint EDBT/ICDT Workshops, pages 158–166, 2012.
  * [13] Jinshuo Dong, Aaron Roth, and Weijie J Su.  Gaussian differential privacy.  Journal of the Royal Statistical Society: Series B (Statistical Methodology), 2021.
  * [14] Cynthia Dwork, Krishnaram Kenthapadi, Frank McSherry, Ilya Mironov, and Moni Naor.  Our data, ourselves: Privacy via distributed noise generation.  In Annual International Conference on the Theory and Applications of Cryptographic Techniques, pages 486–503. Springer, 2006\.
  * [15] Cynthia Dwork, Guy N Rothblum, and Salil Vadhan.  Boosting and differential privacy.  In 2010 IEEE 51st Annual Symposium on Foundations of Computer Science, pages 51–60. IEEE, 2010.
  * [16] Ú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, 2014.
  * [17] Vitaly Feldman, Ilya Mironov, Kunal Talwar, and Abhradeep Thakurta.  Privacy amplification by iteration.  In 2018 IEEE 59th Annual Symposium on Foundations of Computer Science, pages 521–532. IEEE, 2018.
  * [18] Marco Gaboardi, Hyun Lim, Ryan Rogers, and Salil Vadhan.  Differentially private chi-squared hypothesis testing: Goodness of fit and independence testing.  In International Conference on Machine Learning, pages 2111–2120. PMLR, 2016.
  * [19] Badih Ghazi, Pasin Manurangsi, Rasmus Pagh, and Ameya Velingker.  Private aggregation from fewer anonymous messages.  Advances in Cryptology–EUROCRYPT 2020, 12106:798, 2020.
  * [20] Badih Ghazi, Rasmus Pagh, and Ameya Velingker.  Scalable and differentially private distributed aggregation in the shuffled model.  arXiv preprint arXiv:1906.08320, 2019.
  * [21] Muneeb Ul Hassan, Mubashir Husain Rehmani, and Jinjun Chen.  Differential privacy techniques for cyber physical systems: a survey.  IEEE Communications Surveys & Tutorials, 22(1):746–789, 2019.
  * [22] Yaochen Hu, Peng Liu, Linglong Kong, and Di Niu.  Learning privately over distributed features: An admm sharing approach.  arXiv preprint arXiv:1907.07735, 2019.
  * [23] Yuval Ishai, Eyal Kushilevitz, Rafail Ostrovsky, and Amit Sahai.  Cryptography from anonymity.  In 2006 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS’06), pages 239–248. IEEE, 2006.
  * [24] Peter Kairouz, Sewoong Oh, and Pramod Viswanath.  The composition theorem for differential privacy.  In International Conference on Machine Learning, pages 1376–1385. PMLR, 2015.
  * [25] Tao Li and Chris Clifton.  Differentially private imaging via latent space manipulation.  arXiv preprint arXiv:2103.05472, 2021.
  * [26] Michael A Malcolm.  On accurate floating-point summation.  Communications of the ACM, 14(11):731–736, 1971.
  * [27] Arthur R Miller.  Personal privacy in the computer age: The challenge of a new technology in an information-oriented society.  Michigan Law Review, 67(6):1089–1246, 1969.
  * [28] Ilya Mironov.  Rényi differential privacy.  In 2017 IEEE 30th Computer Security Foundations Symposium (CSF), pages 263–275. IEEE, 2017.
  * [29] Jack Murtagh and Salil Vadhan.  The complexity of computing the optimal composition of differential privacy.  In Theory of Cryptography Conference, pages 157–175. Springer, 2016.
  * [30] Arvind Narayanan and Vitaly Shmatikov.  How to break anonymity of the Netflix prize dataset.  arXiv preprint cs/0610105, 2006.
  * [31] Arvind Narayanan and Vitaly Shmatikov.  Robust de-anonymization of large sparse datasets.  In 2008 IEEE Symposium on Security and Privacy (sp 2008), pages 111–125. IEEE, 2008.
  * [32] NhatHai Phan, Xintao Wu, Han Hu, and Dejing Dou.  Adaptive laplace mechanism: Differential privacy preservation in deep learning.  In 2017 IEEE International Conference on Data Mining, pages 385–394. IEEE, 2017.
  * [33] Gang Qiao, Weijie Su, and Li Zhang.  Oneshot differentially private top-k selection.  In Marina Meila and Tong Zhang, editors, Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pages 8672–8681. PMLR, 18–24 Jul 2021.
  * [34] Edward Shils.  Privacy: Its constitution and vicissitudes.  Law and Contemporary Problems, 31(2):281–306, 1966.
  * [35] Larry Wasserman and Shuheng Zhou.  A statistical framework for differential privacy.  Journal of the American Statistical Association, 105(489):375–389, 2010.
  * [36] Xuefeng Xu, Yanqing Yao, and Lei Cheng.  Deep learning algorithms design and implementation based on differential privacy.  In International Conference on Machine Learning for Cyber Security, pages 317–330. Springer, 2020.

## Checklist

  1. 1.

For all authors…

    1. (a)

Do the main claims made in the abstract and introduction accurately reflect
the paper’s contributions and scope? [Yes]

    2. (b)

Did you describe the limitations of your work? [Yes] The limitations are given
as conditions of theorems and properties.

    3. (c)

Did you discuss any potential negative societal impacts of your work? [N/A]
This work is a development of mathematical tools for the DP framework and does
not have a immediate real-world impact.

    4. (d)

Have you read the ethics review guidelines and ensured that your paper
conforms to them? [Yes]

  2. 2.

If you are including theoretical results…

    1. (a)

Did you state the full set of assumptions of all theoretical results? [Yes]

    2. (b)

Did you include complete proofs of all theoretical results? [Yes] The complete
proofs are provided in the appendix.

  3. 3.

If you ran experiments…

    1. (a)

Did you include the code, data, and instructions needed to reproduce the main
experimental results (either in the supplemental material or as a URL)? [Yes]
There are no experimental results in this work. Figures are only for
demonstrative reasons as main results are supported by proofs.

    2. (b)

Did you specify all the training details (e.g., data splits, hyperparameters,
how they were chosen)? [N/A]

    3. (c)

Did you report error bars (e.g., with respect to the random seed after running
experiments multiple times)? [N/A] There is no randomness involved.

    4. (d)

Did you include the total amount of compute and the type of resources used
(e.g., type of GPUs, internal cluster, or cloud provider)? [N/A] The amount of
computing resource needed is negligible.

  4. 4.

If you are using existing assets (e.g., code, data, models) or
curating/releasing new assets…

    1. (a)

If your work uses existing assets, did you cite the creators? [N/A]

    2. (b)

Did you mention the license of the assets? [N/A]

    3. (c)

Did you include any new assets either in the supplemental material or as a
URL? [N/A]

    4. (d)

Did you discuss whether and how consent was obtained from people whose data
you’re using/curating? [N/A] No such data used.

    5. (e)

Did you discuss whether the data you are using/curating contains personally
identifiable information or offensive content? [N/A] No such data used.

  5. 5.

If you used crowdsourcing or conducted research with human subjects…

    1. (a)

Did you include the full text of instructions given to participants and
screenshots, if applicable? [N/A] No human subjects involved.

    2. (b)

Did you describe any potential participant risks, with links to Institutional
Review Board (IRB) approvals, if applicable? [N/A]

    3. (c)

Did you include the estimated hourly wage paid to participants and the total
amount spent on participant compensation? [N/A]

##  Appendix A Appendix

##  Appendix B Appendix: Proofs

###### Proof B.1

Proof of Theorem 2.1:

Sufficiency:

When $\epsilon\geq\epsilon_{0}$, the sufficiency is trivial as
$\delta=\delta_{0}$.

When $\epsilon<\epsilon_{0}$, given that $\mathcal{A}$ is
$(\epsilon_{0},\delta_{0})$-DP, by the definition, for any pair of datasets
$S$ and $S^{\prime}$ that differ in the record of a single individual and any
event $E$,

$P[\mathcal{A}(S)\in E]\leq
e^{\epsilon_{0}}P\left[\mathcal{A}\left(S^{\prime}\right)\in
E\right]+\delta_{0}.$

When $P\left[\mathcal{A}\left(S^{\prime}\right)\in
E\right]\leq\frac{1-\delta_{0}}{1+e^{\epsilon_{0}}}:=c_{0}$,

$\displaystyle P[\mathcal{A}(S)\in E]$ $\displaystyle\leq
e^{\epsilon_{0}}P\left[\mathcal{A}\left(S^{\prime}\right)\in
E\right]+\delta_{0}$
$\displaystyle\leq(e^{\epsilon_{0}}+e^{\epsilon}-e^{\epsilon})P\left[\mathcal{A}\left(S^{\prime}\right)\in
E\right]+\delta_{0}+\delta-\delta$ $\displaystyle\leq
e^{\epsilon_{0}}P\left[\mathcal{A}\left(S^{\prime}\right)\in
E\right]+\delta+(e^{\epsilon_{0}}-e^{\epsilon})c_{0}+\delta_{0}-\delta$
$\displaystyle\leq e^{\epsilon}P\left[\mathcal{A}\left(S^{\prime}\right)\in
E\right]+\delta+(e^{\epsilon_{0}}-e^{\epsilon})c_{0}-\frac{(1-\delta_{0})(e^{\epsilon_{0}}-e^{\epsilon})}{1+e^{\epsilon_{0}}}$
$\displaystyle\leq e^{\epsilon}P\left[\mathcal{A}\left(S^{\prime}\right)\in
E\right]+\delta.$

When $c_{0}\leq P\left[\mathcal{A}\left(S^{\prime}\right)\in E\right]\leq 1$,

$\displaystyle P[\mathcal{A}(S)\in E]$ $\displaystyle=1-P[\mathcal{A}(S)\in
E^{c}]$ $\displaystyle\leq
1-e^{-\epsilon_{0}}(P\left[\mathcal{A}\left(S^{\prime}\right)\in
E^{c}\right]-\delta_{0})$
$\displaystyle=1-e^{-\epsilon_{0}}(1-P\left[\mathcal{A}\left(S^{\prime}\right)\in
E\right]-\delta_{0})$
$\displaystyle=1-e^{-\epsilon_{0}}+e^{-\epsilon_{0}}P\left[\mathcal{A}\left(S^{\prime}\right)\in
E\right]+e^{-\epsilon_{0}}\delta_{0}$
$\displaystyle=1-e^{-\epsilon_{0}}+e^{-\epsilon_{0}}\delta_{0}+\delta-\delta+(e^{-\epsilon_{0}}+e^{\epsilon}-e^{\epsilon})P\left[\mathcal{A}\left(S^{\prime}\right)\in
E\right]$
$\displaystyle=e^{\epsilon}P\left[\mathcal{A}\left(S^{\prime}\right)\in
E\right]+\delta+1-e^{-\epsilon_{0}}+e^{-\epsilon_{0}}\delta_{0}-\delta+(e^{-\epsilon_{0}}-e^{\epsilon})P\left[\mathcal{A}\left(S^{\prime}\right)\in
E\right]$ $\displaystyle\leq
e^{\epsilon}P\left[\mathcal{A}\left(S^{\prime}\right)\in
E\right]+\delta+1-e^{-\epsilon_{0}}+e^{-\epsilon_{0}}\delta_{0}-\delta+(e^{-\epsilon_{0}}-e^{\epsilon})c_{0}$
$\displaystyle=e^{\epsilon}P\left[\mathcal{A}\left(S^{\prime}\right)\in
E\right]+\delta+(1-\delta_{0})(\frac{e^{-\epsilon_{0}}-e^{\epsilon}}{1+e^{\epsilon_{0}}}-e^{-\epsilon_{0}})+1-\delta$
$\displaystyle\leq e^{\epsilon}P\left[\mathcal{A}\left(S^{\prime}\right)\in
E\right]+\delta+(1-\delta_{0})(\frac{e^{-\epsilon_{0}}-e^{\epsilon}}{1+e^{\epsilon_{0}}}-e^{-\epsilon_{0}}+1+\frac{e^{\epsilon}-e^{\epsilon_{0}}}{1+e^{\epsilon_{0}}})$
$\displaystyle=e^{\epsilon}P\left[\mathcal{A}\left(S^{\prime}\right)\in
E\right]+\delta.$

Necessity:

We prove the necessity by giving a specific $(\epsilon_{0},\delta_{0})$-DP
algorithm $\mathcal{A}$ such that $\delta_{\mathcal{A}}(\epsilon)$ is exactly
$\delta_{0}+\frac{(1-\delta_{0})(e^{\epsilon_{0}}-e^{\epsilon})^{+}}{1+e^{\epsilon_{0}}}$.

Define $\Omega_{e}=\\{1,2,3,4\\}$ and $\Omega_{S}=\\{0,1\\}$. Let
$\epsilon\geq 0$, $0\leq\delta_{0}\leq 1$ and denote
$\frac{{e^{\epsilon_{0}}}}{1+{e^{\epsilon_{0}}}}$ as $\alpha_{0}$. Let
$\mathcal{A}$ be a randomized algorithm that take a single point from
$\Omega_{S}$ and generate output as follows:

$\left\\{\begin{aligned} P(\mathcal{A}(S)=1\mid S=0)&=\delta_{0},\\\
P(\mathcal{A}(S)=2\mid S=0)&=0,\\\ P(\mathcal{A}(S)=3\mid
S=0)&=(1-\delta_{0})\alpha_{0},\\\ P(\mathcal{A}(S)=4\mid
S=0)&=(1-\delta_{0})(1-\alpha_{0}),\\\ \end{aligned}\right.$
$\left\\{\begin{aligned} P(\mathcal{A}(S)=1\mid S=1)&=0,\\\
P(\mathcal{A}(S)=2\mid S=1)&=\delta_{0},\\\ P(\mathcal{A}(S)=3\mid
S=1)&=(1-\delta_{0})(1-\alpha_{0}),\\\ P(\mathcal{A}(S)=4\mid
S=1)&=(1-\delta_{0})\alpha_{0}.\\\ \end{aligned}\right.$

By definition, $\delta(\epsilon)$ is the smallest $\delta$ such that
$P(\mathcal{A}(S)\subset E\mid S=s)\leq{e^{\epsilon}}P(\mathcal{A}(S)\subset
E\mid S=1-s)+\delta$ holds true for all $E\subset\Omega_{e}$ and
$s\in\Omega_{S}$. By checking all 64 combinations, we can conclude that
$\delta_{\mathcal{A}}(\epsilon)=\delta_{0}+\frac{(1-\delta_{0})(e^{\epsilon_{0}}-e^{\epsilon})^{+}}{1+e^{\epsilon_{0}}}$.

###### Proof B.2

Proof of Lemma 3.1:

It is well known that [2], for $t<0$:

$\frac{1}{-t+\sqrt{t^{2}+4}}<\sqrt{\frac{\pi}{2}}\exp\left(\frac{t^{2}}{2}\right)\Phi(t)<\frac{1}{-t+\sqrt{t^{2}+\frac{8}{\pi}}}.$

Let $a=\left(-\frac{\varepsilon}{\mu}+\frac{\mu}{2}\right)$ and
$b=\left(-\frac{\varepsilon}{\mu}-\frac{\mu}{2}\right)$,

$\displaystyle\overline{\lim_{\epsilon\rightarrow\infty}}\delta_{\mu}(\epsilon)$
$\displaystyle=\overline{\lim_{\epsilon\rightarrow\infty}}\Phi\left(a\right)-\mathrm{e}^{\epsilon}\Phi\left(b\right)$
$\displaystyle\leq\sqrt{\frac{2}{\pi}}\overline{\lim_{\epsilon\rightarrow\infty}}\frac{\exp\left(\frac{-a^{2}}{2}\right)}{-a+\sqrt{a^{2}+\frac{8}{\pi}}}-\frac{\exp\left(\frac{-b^{2}}{2}+\epsilon\right)}{-b+\sqrt{b^{2}+4}}.$
$\displaystyle=\sqrt{\frac{2}{\pi}}\overline{\lim_{\epsilon\rightarrow\infty}}\exp\left(\frac{-a^{2}}{2}\right)\left(\frac{1}{-a+\sqrt{a^{2}+\frac{8}{\pi}}}-\frac{1}{-b+\sqrt{b^{2}+4}}\right).$
$\displaystyle\leq\sqrt{\frac{2}{\pi}}\overline{\lim_{\epsilon\rightarrow\infty}}\exp\left(\frac{-a^{2}}{2}\right)\left(\frac{-1}{a}\right).$
$\displaystyle=0.$

$\displaystyle\operatorname*{\underline{lim}}_{\epsilon\rightarrow\infty}{\delta_{\mu}(\epsilon)}$
$\displaystyle=\operatorname*{\underline{lim}}_{\epsilon\rightarrow\infty}\Phi\left(a\right)-\mathrm{e}^{\epsilon}\Phi\left(b\right)$
$\displaystyle\geq\sqrt{\frac{2}{\pi}}\operatorname*{\underline{lim}}_{\epsilon\rightarrow\infty}\frac{\exp\left(\frac{-a^{2}}{2}\right)}{-a+\sqrt{a^{2}+4}}-\frac{\exp\left(\frac{-b^{2}}{2}+\epsilon\right)}{-b+\sqrt{b^{2}+\frac{8}{\pi}}}.$
$\displaystyle=\sqrt{\frac{2}{\pi}}\operatorname*{\underline{lim}}_{\epsilon\rightarrow\infty}\exp\left(\frac{-a^{2}}{2}\right)\left(\frac{1}{-a+\sqrt{a^{2}+4}}-\frac{1}{-b+\sqrt{b^{2}+\frac{8}{\pi}}}\right).$
$\displaystyle\geq\sqrt{\frac{2}{\pi}}\operatorname*{\underline{lim}}_{\epsilon\rightarrow\infty}\exp\left(\frac{-a^{2}}{2}\right)\left(\frac{-1}{b}\right).$
$\displaystyle=0.$

Therefore,

$\lim_{\epsilon\rightarrow\infty}\delta_{\mu}(\epsilon)=0.$ (3)

It is easy to see that,

$\lim_{\epsilon\rightarrow\infty}\tilde{\delta}_{\mu}(\epsilon)=\lim_{\epsilon\rightarrow\infty}\frac{\mu
e^{-a^{2}/2}}{\sqrt{2\pi}a^{2}}=0$ (4)

By L’Hospital’s rule:

$\displaystyle\lim_{\epsilon\rightarrow\infty}\frac{\tilde{\delta}_{\mu}(\epsilon)}{\delta_{\mu}(\epsilon)}$
$\displaystyle=\lim_{\epsilon\rightarrow\infty}\frac{\tilde{\delta}^{\prime}_{\mu}(\epsilon)}{\delta^{\prime}_{\mu}(\epsilon)}$
$\displaystyle=\lim_{\epsilon\rightarrow\infty}-\frac{e^{-\frac{a^{2}}{2}}\left(a^{2}+2\right)}{\sqrt{2\pi}a^{3}}\bigg{/}e^{\epsilon}\Phi(b)$
$\displaystyle=\lim_{\epsilon\rightarrow\infty}\frac{e^{-\frac{b^{2}}{2}}\Phi(b)}{\sqrt{2\pi}b}$
$\displaystyle=\lim_{b\rightarrow-\infty}\frac{e^{-\frac{b^{2}}{2}}\Phi(b)}{\sqrt{2\pi}b}$
$\displaystyle=1.$

###### Proof B.3

Proof of Theorem 3.2:

Sufficiency:

If $\mathcal{A}$ is $\mu$-GDP. Then
$\varlimsup\limits_{\epsilon\rightarrow+\infty}G_{\mathcal{A}}(\epsilon)\leq\varlimsup\limits_{\epsilon\rightarrow+\infty}G_{\delta_{\mu}}(\epsilon)=\mu$.

Necessity:

If
$\varlimsup\limits_{\epsilon\rightarrow+\infty}G_{\mathcal{A}}(\epsilon)=\mu<+\infty$,
there must be a $\epsilon_{t}>0$ such that $\mathcal{A}$ is
$(\epsilon_{t},\mu_{0}+1)$-tail GDP.

Notice that $\lim\limits_{\mu\rightarrow\infty}\delta_{\mu}(\epsilon_{t})=1$,
we can pick $\mu_{1}>\mu_{0}$ large enough such that
$\delta_{\mu_{1}}(\epsilon_{t})>\delta_{\mathcal{A}}(0)$.

This is possible because by Theorem 2.1, $\delta_{\mathcal{A}}(0)<1$. Then for
$\epsilon\in[0,\epsilon_{t})$,
$\delta_{\mathcal{A}}(\epsilon)\leq\delta_{\mathcal{A}}(0)\leq\delta_{\mu_{1}}(\epsilon_{t})\leq\delta_{\mu_{1}}(\epsilon)$.
$\mathcal{A}$ is both $(\epsilon_{t},\mu)$-head and tail GDP for
$\mu=\mu_{0}+\mu_{1}+1$. $\mathcal{A}$ is GDP as desired.

###### Proof B.4

Proof of Theorem 3.3:

Let $\varlimsup\limits_{\epsilon\rightarrow+\infty}G_{f}(\epsilon)=\mu_{t}$.

First we show that
$\varlimsup\limits_{\epsilon\rightarrow\infty}\frac{\epsilon^{2}}{-2\log{\delta_{\mathcal{A}}(\epsilon)}}\leq\mu_{t}^{2}$:

By the definition the limit, for any $\mu_{0}>\mu_{t}$, for sufficient large
$\epsilon$, $G_{f}(\epsilon)<\mu_{0}$ and further
$\delta_{\mathcal{A}}(\epsilon)\leq\delta_{\mu_{0}}(\epsilon)$. Hence,
$\varlimsup\limits_{\epsilon\rightarrow\infty}\frac{\delta_{\mathcal{A}}(\epsilon)}{\delta_{\mu_{0}}(\epsilon)}\leq
1.$ By Lemma 3.1,
$\varlimsup\limits_{\epsilon\rightarrow\infty}\frac{\delta_{\mathcal{A}}(\epsilon)}{\tilde{\delta}_{\mu_{0}}(\epsilon)}\leq
1$.

Then
$\lim\limits_{\epsilon\rightarrow\infty}\frac{\epsilon^{2}}{-2\log{\delta_{\mathcal{A}}(\epsilon)}}\leq\lim\limits_{\epsilon\rightarrow\infty}\frac{\epsilon^{2}}{-2\log{\tilde{\delta}_{\mu_{0}}(\epsilon)}}=\mu_{0}^{2}$.

$\lim\limits_{\epsilon\rightarrow\infty}\frac{\epsilon^{2}}{-2\log{\delta_{\mathcal{A}}(\epsilon)}}\leq\mu_{t}$
as desired as we take $\mu_{0}\rightarrow\mu_{t}$.

Next we show that
$\varlimsup\limits_{\epsilon\rightarrow\infty}\frac{\epsilon^{2}}{-2\log{\delta_{\mathcal{A}}(\epsilon)}}\geq\mu_{t}^{2}$:

If
$\varlimsup\limits_{\epsilon\rightarrow\infty}\frac{\epsilon^{2}}{-2\log{\delta_{\mathcal{A}}(\epsilon)}}=\mu_{0}^{2}<\mu_{t}^{2}$,
then by Lemma 3.1,

$\displaystyle\varlimsup\limits_{\epsilon\rightarrow\infty}\frac{\epsilon^{2}}{-2\log{\delta_{\mathcal{A}}(\epsilon)}}-\frac{\epsilon^{2}}{-2\log{\delta_{\mu_{t}}(\epsilon)}}$
$\displaystyle=\varlimsup\limits_{\epsilon\rightarrow\infty}\frac{\epsilon^{2}}{-2\log{\delta_{\mathcal{A}}(\epsilon)}}-\varlimsup\limits_{\epsilon\rightarrow\infty}\frac{\epsilon^{2}}{-2\log{\tilde{\delta}_{\mu_{t}}(\epsilon)}}$
$\displaystyle<\mu_{0}^{2}-\mu_{t}^{2}$

Then for a sufficiently large $\epsilon_{0}$,

$\frac{\epsilon_{0}^{2}}{-2\log{\delta_{\mathcal{A}}(\epsilon_{0})}}-\frac{\epsilon_{0}^{2}}{-2\log{\delta_{\mu_{0}}(\epsilon_{0})}}<0.$

Since $\log$ is an increasing function, it follows that
$\delta_{\mathcal{A}}(\epsilon_{0})<\delta_{\mu_{0}}(\epsilon_{0})$. Then
$\varlimsup\limits_{\epsilon\rightarrow+\infty}G_{f}(\epsilon)\leq\mu_{0}<\mu_{t}$,
which is a contradiction.

###### Proof B.5

Proof of Theorem 4.2:

Let $G_{\mu}(\epsilon)=F(\epsilon,\delta_{\mu}(\epsilon))$ and
$F(x,y)=\mu_{{}_{\text{GDP}}}(x,y)$.

By definition of $\mu_{{}_{\text{GDP}}}$, $G_{\mu}(\epsilon)=\mu$.

On one hand, $\left\\{\begin{aligned} \frac{\partial
G_{\mu}(\epsilon)}{\partial\epsilon}&=\frac{\partial\mu}{\partial\epsilon}=0,\\\
\frac{\partial
G_{\mu}(\epsilon)}{\partial\mu}&=\frac{\partial\mu}{\partial\mu}=1.\\\
\end{aligned}\right.$

On the other hand, by chain rule, $\left\\{\begin{aligned} \frac{\partial
G_{\mu}(\epsilon)}{\partial\epsilon}&=\frac{\partial F}{\partial
x}+\frac{\partial F}{\partial
y}\frac{\partial\delta_{\mu}(\epsilon)}{\partial\epsilon},\\\ \frac{\partial
G_{\mu}(\epsilon)}{\partial\mu}&=\frac{\partial F}{\partial
y}\frac{\partial\delta_{\mu}(\epsilon)}{\partial\mu}.\\\ \end{aligned}\right.$

Therefore, $\left\\{\begin{aligned} \frac{\partial F}{\partial
y}&=(\frac{\partial\delta_{\mu}(\epsilon)}{\partial\mu})^{-1},\\\
\frac{\partial F}{\partial
x}&=-(\frac{\partial\delta_{\mu}(\epsilon)}{\partial\mu})^{-1}\frac{\partial\delta_{\mu}(\epsilon)}{\partial\epsilon}.\end{aligned}\right.$

Using the close forms,
$\frac{\partial\delta_{\mu}(\epsilon)}{\partial\epsilon}$ and
$\frac{\partial\delta_{\mu}(\epsilon)}{\partial\mu}$ can be directly computed:

$\left\\{\begin{aligned}
\frac{\partial\delta_{\mu}(\epsilon)}{\partial\epsilon}&=-e^{\epsilon}\Phi(-\frac{\mu^{2}+2\epsilon}{2\mu}),\\\
\frac{\partial\delta_{\mu}(\epsilon)}{\partial\mu}&=\frac{e^{-\frac{\left(\mu^{2}-2\epsilon\right)^{2}}{8\mu^{2}}}}{\sqrt{2\pi}}.\end{aligned}\right.$

Hence, $\left\\{\begin{aligned} \frac{\partial F}{\partial
x}&=\sqrt{2\pi}e^{\frac{\left(\mu^{2}+2\epsilon\right)^{2}}{8\mu^{2}}}\Phi(-\frac{\mu^{2}+2\epsilon}{2\mu})\leq\sqrt{2\pi}e^{\frac{\mu^{2}}{8}}\Phi(-\frac{\mu}{2})\leq\frac{\sqrt{2}\pi}{2},\\\
\frac{\partial F}{\partial
y}&=\sqrt{2\pi}e^{\frac{\left(\mu^{2}-2\epsilon\right)^{2}}{8\mu^{2}}}>0.\end{aligned}\right.$

Notice that $\frac{\partial F}{\partial
x}=\sqrt{2\pi}e^{\frac{\left(\mu^{2}+2\epsilon\right)^{2}}{8\mu^{2}}}\Phi(-\frac{\mu^{2}+2\epsilon}{2\mu})>0$,
combined with the fact that $\frac{\partial F}{\partial
x}\leq\frac{\sqrt{2}\pi}{2}$, we can conclude that
$0\leq\frac{\partial\mu_{{}_{\text{GDP}}}(\epsilon,\delta)}{\partial\epsilon}\leq\frac{\sqrt{2}\pi}{2}.$
By $\frac{\partial F}{\partial y}>0$, we can see GDPT is order preserving.

###### Proof B.6

Proof of Theorem 4.3:

We now consider the gap between
$\max_{i\in\\{0,\cdots,n\\}}\\{{G_{\mathcal{A}}^{-}(x_{i})}\\}$ and
$\max_{i\in\\{0,\cdots,n+1\\}}\\{{G_{\mathcal{A}}^{+}(x_{i})}\\}$ bound the
length of $[\mu^{-},\mu^{+}]$ in two cases.

Case 1: If
$\max_{i\in\\{0,\cdots,n+1\\}}\\{{G_{\mathcal{A}}^{+}(x_{i})}\\}=G_{\mathcal{A}}^{+}(x_{0})$,
then
$\max_{i\in\\{0,\cdots,n+1\\}}\\{{G_{\mathcal{A}}^{+}(x_{i})}\\}=G_{\mathcal{A}}^{+}(x_{0})=\mu_{{}_{\text{GDP}}}(D,\delta_{\mathcal{A}}(0))\leq\mu_{{}_{\text{GDP}}}(0,\delta_{\mathcal{A}}(0))+\frac{\sqrt{2}\pi
D}{2}$. Therefore,

$\max_{\epsilon\in[0,\epsilon_{h}]}G(\epsilon)\leq
G_{\mathcal{A}}^{+}(x_{0})\leq\\{{G_{\mathcal{A}}^{-}(x_{0})}\\}+\frac{\sqrt{2}\pi
D}{2}.$

Case 2: If
$\max_{i\in\\{0,\cdots,n+1\\}}\\{{G_{\mathcal{A}}^{+}(x_{i})}\\}\neq
G_{\mathcal{A}}^{+}(x_{0})$, then by the order preserving property, the
optimal $\mu$ lies in $[\mu^{-},\mu^{+}]$, where
$\mu^{-}=\max(\mu_{h},\max_{i\in\\{0,\cdots,n\\}}\\{{G_{\mathcal{A}}^{-}(x_{i})}\\})$
and
$\mu^{+}=\max(\mu_{h},\max_{i\in\\{1,\cdots,n+1\\}}\\{{G_{\mathcal{A}}^{+}(x_{i})}\\})$.
Notice that

$\displaystyle\max_{i\in\\{0,\cdots,n\\}}\\{{G_{\mathcal{A}}^{-}(x_{i})}\\}$
$\displaystyle=\max_{i\in\\{0,\cdots,n\\}}\\{\mu_{{}_{\text{GDP}}}(x_{i},\delta_{\mathcal{A}}(x_{i+1}))\\}=\max_{i\in\\{1,\cdots,n+1\\}}\\{\mu_{{}_{\text{GDP}}}(x_{i-1},\delta_{\mathcal{A}}(x_{i}))\\}$
$\displaystyle\geq\max_{i\in\\{1,\cdots,n+1\\}}\\{\mu_{{}_{\text{GDP}}}(x_{i+1},\delta_{\mathcal{A}}(x_{i}))-\sqrt{2}\pi
D\\}$
$\displaystyle\geq\max_{i\in\\{1,\cdots,n+1\\}}\\{G_{\mathcal{A}}^{+}(x_{i})\\}-\sqrt{2}\pi
D.$

In both cases the gap is no greater than $\sqrt{2}\pi D$ as desired.

###### Proof B.7

Proof of Theorem 4.4:

By the definition of $\mathcal{C}$, $\mathcal{C}\circ\mathcal{A}$ is bounded
in $[y^{-},y+]$. Therefore the global sensitivity of
$\mathcal{C}\circ\mathcal{A}$ is no greater than $y^{+}-y^{-}$. Then
$\mathcal{R}\circ\mathcal{C}\circ\mathcal{A}$ is a special case of the Laplace
mechanism. By [3], $\mathcal{R}\circ\mathcal{C}\circ\mathcal{A}$ is
$\epsilon_{h}$-DP. Then
$\delta_{\mathcal{R}\circ\mathcal{C}\circ\mathcal{A}}(\epsilon)=0<\delta_{\mu}(\epsilon)$
for any $\epsilon\geq\epsilon_{h}$.

In addition, because of the post-processing property,
$\delta_{\mathcal{R}\circ\mathcal{C}\circ\mathcal{A}}(\epsilon)\leq\delta_{\mathcal{A}}(\epsilon)<\delta_{\mu}(\epsilon)$
for any $\epsilon<\epsilon_{h}$.

Therefore, $\mathcal{R}\circ\mathcal{C}\circ\mathcal{A}$ is $\mu$-GDP.

##  Appendix C Appendix: Refining the privacy profile

Given a trade-off function $\sigma=f(\epsilon,\delta)$ and a fixed parameter
$\sigma$. From definition of the trade-off function it is instant that the for
any
$(\epsilon,\delta)$$\in\Omega=\\{(\epsilon,\delta)\mid\sigma=f(\epsilon,\delta)\\}$,
$(\epsilon,\delta)$-DP is guaranteed. Then, $(\epsilon,\delta)$-DP is also
guaranteed if there is a $(\epsilon_{0},\delta_{0})\in\Omega$ such that
$(\epsilon_{0},\delta_{0})$-DP implies $(\epsilon,\delta)$-DP. Therefore,

$\delta_{\mathcal{A}}(\epsilon)=\min\left(\\{\delta\mid\sigma=f(\epsilon_{0},\delta_{0})\text{
and
}\delta\geq\delta_{0}+\frac{(1-\delta_{0})(e^{\epsilon_{0}}-e^{\epsilon})^{+}}{1+e^{\epsilon_{0}}}\\}\right).$

Notice that by theorem 2.1, $(\epsilon_{0},\delta_{0})$-DP implies
$(\epsilon,\delta)$ with $\delta<\delta_{0}$ only if $\epsilon<\epsilon_{0}$,
we rewrite the $\delta_{\mathcal{A}}(\epsilon)$ as:

$\delta_{\mathcal{A}}(\epsilon)=\inf_{\epsilon_{0}\in[\epsilon,\infty)}g(\epsilon,\epsilon_{0}),$

where
$g(\epsilon,\epsilon_{0}):=(1-\hat{\delta_{\mathcal{A}}}(\epsilon_{0}))\frac{{e^{\epsilon_{0}}}-{e^{\epsilon}}}{{e^{\epsilon_{0}}}+1}+\hat{\delta_{\mathcal{A}}}(\epsilon_{0})$
and $\hat{\delta_{\mathcal{A}}}$ is the naive privacy profile defined
implicitly by $\sigma=f(\epsilon_{0},\delta_{0})$. For continuously
differentiable $f$, the minimum value of the right-hand side can be found be
take the derivative:

$\frac{\partial
g(\epsilon,\epsilon_{0})}{\partial\epsilon_{0}}=\frac{1+{e^{\epsilon}}}{(1+{e^{\epsilon_{0}}})^{2}}\left[\hat{\delta_{\mathcal{A}}}^{\prime}(\epsilon_{0})+{e^{\epsilon_{0}}}(1-\hat{\delta_{\mathcal{A}}}(\epsilon_{0})+\hat{\delta_{\mathcal{A}}}^{\prime}(\epsilon_{0}))\right].$

We remark that the sign of $\frac{\partial
g(\epsilon,\epsilon_{0})}{\partial\epsilon_{0}}$ does not depend on $\epsilon$
when $\epsilon>\epsilon_{0}$. For both of our example 2 and 3, we both find a
particular value $\epsilon^{i}$ such that $Sign(\frac{\partial
g(\epsilon,\epsilon_{0})}{\partial\epsilon_{0}})=-Sign(\epsilon-\epsilon^{i})$.
This means for $\epsilon\geq\epsilon^{i}$,
$\delta_{\mathcal{A}}(\epsilon)=\hat{\delta_{\mathcal{A}}}(\epsilon)$ and
otherwise $\delta_{\mathcal{A}}(\epsilon)$ equals to the $\delta$ value
derived from $(\epsilon^{i},\hat{\delta_{\mathcal{A}}}(\epsilon^{i}))$.

There is an interesting byproduct or the privacy profile refinement.
Theoretically, the privacy profile refinement can also be used to improve an
algorithm’s utility. For example, the projected noisy SGD algorithm in [17] is
$(\epsilon,\delta)$-DP and the trade-off function is
$\sigma=-C\log(\delta_{0})/\epsilon_{0}$. To achieve $(0.2,e^{-2})$-DP, it
appears that $\sigma$ needs to be chosen as $-C\log(e^{-2})/0.2=10C$.
$(\epsilon,\delta)$-DP implies $(0.2,e^{-2})$-DP when
$\delta+(1-\delta)(e^{\epsilon}-e^{0.2})^{+}/(1+e^{\epsilon})=e^{-2}.$
Numerical methods suggest that, by choosing $\epsilon\approx 0.334$ and
$\delta\approx 0.067$, $(\epsilon,\delta)$-DP implies $(0.2,e^{-2})$-DP but
$\sigma=-C\log(\delta)/\epsilon\approx 8.086C<10C$. Therefore, the desired
level of DP can be achieved with a lower noise parameter. However, this type
of refinement majorly affects privacy profile around the origin and therefore
minor in practice.

##  Appendix D Behind efficient head measurement algorithm

First we formalize the binary search algorithm to find
$\mu_{{}_{\text{GDP}}}$:

Algorithm 2 Binary search

Input: $\epsilon$, $\delta$, $b$. (The $(\epsilon,\delta)$-pair, searching
range, error margin)

$\mu_{-}\leftarrow 0$

$\mu_{+}\leftarrow\mu_{\text{max}}$

repeat

$\mu=\frac{\mu^{+}+\mu^{-}}{2}$

if $\delta_{\mu}(\epsilon)>\delta$ then

$\mu^{+}\leftarrow\mu$

else

$\mu^{-}\leftarrow\mu$

end if

until $\mu^{+}-\mu^{-}<b$

Output: $\mu_{-}$, $\mu_{+}$ (lower and upper bound of $\mu$).

It is possible to drop the need for the searching range $\mu_{\text{max}}$ for
this algorithm (e.g., exponentially search for an upper bound first or conduct
a binary search on $\arctan\mu$ instead). We keep this input for clarity and
simplicity. $\mu_{\text{max}}$ can be set to a large constant for convenience,
for example, $10$. If the outputted $\mu^{+}$ equals the preset value (10),
the privacy profile fails to imply $10$-GDP. In practice, GDP with $\mu\geq 6$
already provides almost no privacy protection [13].

With the formal definition of binary search, an exhaustive iteration method to
bound the staircase functions outlined in Theorem 4.3 can be formally written
as follows:

Algorithm 3 Finding $\mu$ with privacy profiles (naive).

Input: $\delta_{\mathcal{A}}$, $\epsilon_{h}$, $c$. (Privacy profile,
searching range, reciprocal of error margin)

$n\leftarrow\left\lceil\sqrt{8}c\pi\epsilon_{h}\right\rceil+1$

$d\leftarrow\frac{\epsilon_{h}}{n-1}$

$\mu_{-}\leftarrow 0$

$\mu_{+}\leftarrow 0$

for $i=0$ to $n+1$ do

$x^{-}\leftarrow id$

$x^{+}\leftarrow(i+1)d$

$\mu_{+}\leftarrow\max(\mu_{+},\mu_{{}_{\text{GDP}}}^{+}(x^{-},\delta_{\mathcal{A}}(x^{+}),\frac{1}{2c}))$

$\mu_{-}\leftarrow\max(\mu_{-},\mu_{{}_{\text{GDP}}}^{-}(x^{+},\delta_{\mathcal{A}}(x^{-}),\frac{1}{2c}))$

$i\leftarrow i+1$

end for

Output: $\mu^{+}$, $\mu^{-}$.

To transform this naive algorithm into the optimized one. The first key
observation is that the reassignment of $\mu_{+}$ and $\mu_{-}$ can be
optimized.

We take
$\mu_{+}\leftarrow\max(\mu_{+},\mu_{{}_{\text{GDP}}}^{+}(x^{-},\delta_{\mathcal{A}}(x^{+}),\frac{1}{2c}))$
for example, same optimization can be applied to
$\mu_{-}\leftarrow\max(\mu_{-},\mu_{{}_{\text{GDP}}}^{-}(x^{+},\delta_{\mathcal{A}}(x^{-},\frac{1}{2c})))$
as well. The naive operation,
$\mu_{+}\leftarrow\max(\mu_{+},\mu_{{}_{\text{GDP}}}^{+}(x^{-},\delta_{\mathcal{A}}(x^{+}),\frac{1}{2c}))$
can be optimized into “If
$\delta_{\mu^{+}}(x^{-})<\delta_{\mathcal{A}}(x^{+})$, then
$\mu^{+}\leftarrow\mu_{{}_{\text{GDP}}}^{+}(x^{-},\delta_{\mathcal{A}}(x^{+}),\frac{1}{2c}))$”
without lost of accuracy. To see this, we list all three possibilities as
follows:

  * •

Case 1:
$\mu^{+}<\mu_{{}_{\text{GDP}}}(x^{-},\delta_{\mathcal{A}}(x^{+}))\leq\mu_{{}_{\text{GDP}}}^{+}(x^{-},\delta_{\mathcal{A}}(x^{+}),\frac{1}{2c})).$

  * •

Case 2:
$\mu_{{}_{\text{GDP}}}(x^{-},\delta_{\mathcal{A}}(x^{+}))\leq\mu^{+}\leq\mu_{{}_{\text{GDP}}}^{+}(x^{-},\delta_{\mathcal{A}}(x^{+}),\frac{1}{2c})).$

  * •

Case 3:
$\mu_{{}_{\text{GDP}}}(x^{-},\delta_{\mathcal{A}}(x^{+}))\leq\mu_{{}_{\text{GDP}}}^{+}(x^{-},\delta_{\mathcal{A}}(x^{+}),\frac{1}{2c}))<\mu^{+}.$

In case 1, both of the naive operation and the optimized operation will update
$\mu^{+}$ to
$\mu_{{}_{\text{GDP}}}^{+}(x^{-},\delta_{\mathcal{A}}(x^{+}),\frac{1}{2c}))$.

In case 2, the optimized operation will do nothing, because the test
$\delta_{\mu^{+}}(x^{-})<\delta_{\mathcal{A}}(x^{+})$ will fail. The naive
operation will update $\mu^{+}$ due to the error of binary search, which
should be avoided.

In case 3, the optimized operation will do nothing, because the test
$\delta_{\mu^{+}}(x^{-})<\delta_{\mathcal{A}}(x^{+})$ will fail. The naive
operation will also do nothing because the max operator will choose $\mu^{+}$.

To sum up, the optimized operation always give a more accurate update.

The second insight is that we want to avoid case 1 because only in case 1 a
binary search is needed. Notice that case 1 happens only if
$\delta_{\mu^{+}}(x^{-})<\delta_{\mathcal{A}}(x^{+})$, which is equivalent to
$\mu^{+}<\mu_{{}_{\text{GDP}}}(x^{-},\delta_{\mathcal{A}}(x^{+}))$. In the
$k+1$ round of loop, the condition
$\mu^{+}<\mu_{{}_{\text{GDP}}}(x^{-},\delta_{\mathcal{A}}(x^{+}))$ holds true
only if for all $j\in\\{0,\cdots,k\\}$,
$\mu_{{}_{\text{GDP}}}(x^{-}_{j},\delta_{\mathcal{A}}(x^{+}_{j}))<\mu_{{}_{\text{GDP}}}(x^{-},\delta_{\mathcal{A}}(x^{+}))$,
where $x^{-}_{j}$ and $x^{+}_{j}$ are the values of $x^{-}$ and $x^{+}$ in the
round $j$. This inspire us to shuffle $x_{i}$ before iteration because after
shuffling, the probability of
“$\mu_{{}_{\text{GDP}}}(x^{-}_{j},\delta_{\mathcal{A}}(x^{+}_{j}))<\mu_{{}_{\text{GDP}}}(x^{-},\delta_{\mathcal{A}}(x^{+}))$
for all $j\in\\{0,\cdots,k\\}$” will be $\frac{1}{k+1}$. The expected
occurrence of case 1 will be $\sum_{k=0}^{n+1}\frac{1}{k+1}=O(\log(n))$.

The time complexity of shuffling $\mathcal{S}$ is $O(n)=O(\epsilon_{h}c)$.
Each binary search has a time complexity of $O(\log(c))$ and the expected
number of binary searches is $O(\log(\epsilon_{h}c))$. The overall time
complexity of the optimized algorithm is therefore
$O(\epsilon_{h}c+\log(c)\log(c\epsilon_{h}))$=$O(\epsilon_{h}c)$.

##  Appendix E Appendix: Plots

###  E.1 The Laplace mechanism under GDP

Figure 5: The plot of GDPT of $\epsilon$-DP privacy profiles and the Laplace
mechanisms with the same $\epsilon$-DP guarantee. From the figure we can see
the privacy protection provided by the Laplace mechanisms is slightly better
than $\epsilon$-DP.

###  E.2 The effect of subsampling

Figure 6: (Left) GDPT of the Laplace mechanism for various of $\gamma$.
(Right) GDPT of the SGD for various of $\gamma$.

Figure 7: (Left) GDPT of the ICEA for various of $\gamma$. (Right) GDPT of the
$\delta_{\mu}$ for various of $\gamma$. The Poisson subsampling procedure can
significantly decrease the value of $\mu$ around $\epsilon=0$ but has little
effect on the GDPT’s tail.