Year: 2021

Abstract:
Gaussian differential privacy (GDP) is a single-parameter family of privacy notions that provides coherent guarantees to avoid the exposure of individuals from machine learning models. Relative to traditional ( , δ)-differential privacy (DP), GDP is more interpretable and tightens the bounds given by standard DP composition theorems. In this paper, we start with an exact privacy profile characterization of ( , δ)-DP and then define an efficient, tractable, and visualizable tool, called the Gaussian differential privacy transformation (GDPT). With theoretical property of the GDPT, we develop an easy-to-verify criterion to characterize and identify GDP algorithms. Based on our criterion, an algorithm is GDP if and only if an asymptotic condition on its privacy profile is met. By development of numerical properties of the GDPT, we give a method to narrow down possible values of an optimal privacy measurement μ with an arbitrarily small and quantifiable margin of error. As applications of our newly developed tools, we revisit some established ( , δ)-DP algorithms and find that their utility can be improved. We additionally make a comparison between two single-parameter families of privacy notions, DP and μ-GDP. Lastly, we use the GDPT to examine the effect of subsampling under the GDP framework.

heading: 1 INTRODUCTION
text: 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 (Miller, 1969), the concept of privacy is often perceived as “vague and difficult to get into a right perspective” (Shils, 1966). 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 (Narayanan & Shmatikov, 2006; 2008; Barbaro & T. Zeller, 2006).
Differential privacy (DP) first gained traction as it met the urgent need for rigour and quantifiability in privacy protection (Dwork et al., 2006). 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 (Dwork et al., 2006) A randomized algorithm A, taking a dataset consisting of individuals as its input, is ( , δ)-differentially private if, for any pair of datasets S and S′ that differ in the record of a single individual and any event E,
P [A(S) ∈ E] ≤ e P [A (S′) ∈ E] + δ. When δ = 0, A is called -differentially private ( -DP).
While the notion of ( , δ)-DP has wide applications (Dankar & El Emam, 2012; Erlingsson et al., 2014; Cormode et al., 2018; Hassan et al., 2019), there are a few notable drawbacks to this framework. One is the poor interpretability of ( , δ)-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 ( , δ)-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 ( , δ)-DP, leading to very loose composition theorems.
To overcome the drawbacks of ( , δ)-DP, numerous variants have been developed, including the hypothesis-testing-based f -DP (Wasserman & Zhou, 2010; Dong et al., 2019), the momentsaccountant-based Rényi DP (Mironov, 2017), as well as concentrated DP and its variants (Bun & Steinke, 2016; Bun et al., 2018). Despite their very different perspectives, all of these DP variants can be fully characterized by an infinite union of ( , δ)-DP guarantees. In particular, there is a two-way embedding between f -DP and the infinite union of ( , δ)-DP guarantees: any guarantee provided by an infinite union of ( , δ)-DP can be fully characterized by f -DP and vice visa (Dong et al., 2019). 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
H0 : the underlying dataset is S versus H1 : the underlying dataset is S′
and given an output of an algorithm A, where S and S′ are neighbouring datasets. The harder this testing problem is, the less privacy leakageA has. To see this, consider the dilemma that the attacker is facing. The attacker must reject either H0 or H1 based on the given output of A: this means the attacker must select a subset R0 of Range(A) and reject H0 if the sampled output is in R0 (or must otherwise reject H1). The attacker is more likely to incorrectly reject H0 (in a type I error) when R0 is large. Conversely, if R0 is small, the attacker is more likely to incorrectly reject H1 (in a type II error). We say that an algorithm A is f -DP if, for any α ∈ [0, 1], no attacker can simultaneously bound the probability of type I error below α and bound the probability of type II error below f(α). The function 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 µ and use the trade-off function f(α) = Φ ( Φ−1(1− α)− µ ) , where Φ 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(µ, 1) on the basis of a single observation. Aside from its visual interpretation, GDP also has unique composition theorems: the composition of a µ1- and µ2-GDP algorithm is, as expected, √ µ21 + µ 2 2-GDP. This property can be easily generalized to n-fold composition. GDP also has 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 Dong et al. (2019) for more information.
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 ( , δ)-DP framework, this trade-off is often characterized in a form of σ = f( , δ): to achieve ( , δ)-DP, the utility parameter (usually the scale of noise) needs to be chosen as f( , δ). We will further discuss this formulation with examples in the next section.

heading: 1.1 OUR CONTRIBUTION
text: The general goal of this paper is to provide both a deeper theoretical understanding of and powerful practical tools for the GDP framework. To this end, we start with the analysis of privacy profiles
under the condition of traditional ( , δ)-DP, where we point out an often-overlooked partial order on ( , δ)-DP conditions via implication. We choose this as the starting point for our work because ignoring this partial order will lead to problematic asymptotic analysis and compromised utility.
Next, we broken down the GDP into two parts: a head condition and a tail condition and define an efficient, tractable, and visualizable tool, called the Gaussian differential privacy transformation (GDPT). We first used the GDPT on the identification of GDP algorithms. Through the intermediate property of GDPT that we develop, we find an easy-to-verify criterion that can distinguish GDP mechanisms from non-GDP mechanisms. For GDP algorithms, this criterion provides a lower bound for the privacy protection parameter µ. This criterion can help researchers widen the set of available GDP algorithms and also gives an interesting characterization of GDP without an explicit reference to the Gaussian distribution.
Following the identification of a GDP algorithm, the logical next step is to measure the exact value of µ. By development of numerical properties of the GDPT, we give a method to narrow down possible values of an optimal µ with an arbitrarily small and quantifiable margin of error.
Lastly, we give three more applications of our newly developed tools. In the first, we revisit some established ( , δ)-DP algorithms and improve their utility by accounting for the overlooked partial order on ( , δ)-DP conditions provided by logical implication. In the second application, we make a comparison between -DP and µ-GDP and find that any -DP algorithm must be also µ-GDP. In the last application, we discuss the effect of subsampling using the GDPT.

heading: 2 BACKGROUND
text: An algorithm can be ( , δ)-DP for multiple pairs of and δ: the union of all such pairs provides a complete image of the algorithm under the ( , δ)-DP framework. In particular, an ( , δ)-DP mechanismA is also ( ′, δ′)-DP for any ′ ≥ and any δ′ ≥ δ. The infinite union of ( , δ) pairs can thus be represented as the smallest δ associated with each . This intuition is formulated as a privacy profile in Balle & Wang (2018). The privacy profile corresponding to a collection of ( , δ)-DP guarantees Ω is defined as the curve in [0,∞)× [0, 1] separating the space of privacy parameters into two regions, one of which contains exactly the pairs in Ω. The privacy profile provides as much information as Ω itself. Many privacy guarantees and privacy notions, including ( , δ)-DP, Rényi DP, f -DP, GDP, and concentrated DP, can be embedded into a family of privacy profile curves and fully characterized (Balle et al., 2020a). 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 (Dwork et al., 2006). 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 ∆, the value of b needs to be chosen as f( , 0) = ∆/ in order to provide an ( , 0)-DP guarantee. Despite its long history, the Laplace mechanism has remained in use and study in recent years (Phan et al., 2017; Hu et al., 2019; Xu et al., 2020; Li & Clifton, 2021).
Our second example is a family of algorithms in which a noise parameter has the form σ = A −1 √ log(B/δ). Examples include
• the goodness of fit algorithm (Gaboardi et al., 2016), • noisy stochastic gradient descent and its variants (Bassily et al., 2014; Abadi et al., 2016;
Feldman et al., 2018), and • the one-shot spectral method and the one-shot Laplace algorithm (Qiao et al., 2021).
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 (Ishai et al., 2006) is ( , δ)-DP if m > 10 log(n/( δ)) (Ghazi et al., 2019). See also (Balle et al., 2020b; Ghazi et al., 2020) for other analysis of ICEA.
For figures and numerical demonstrations in this paper, we use b = 2/∆ for the Laplace mechanism; A = 2,B = 1, and σ = 2 for the second example, which we refer to as SGD; andm = 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 (Balle et al., 2020a), privacy guarantees are given in the form of a privacy–utility trade-off equation σ = f( , δ). Given σ, it is tempting to derive the privacy profile by inverting the trade-off equation (i.e., as δA( ) = min{δ | σ = f( , δ)}). 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 ( , δ)-DP conditions, which we discuss below.
3 PRIVACY PROFILES AND AN EXACT PARTIAL ORDER ON ( , δ)-DP CONDITIONS
An ( 0, δ0)-DP algorithm is trivially ( , δ)-DP for any ≥ 0 and δ ≥ δ0. However, this statement does not give a full picture of the relationships between different ( , δ)-DP conditions.
Theorem 3.1 Assume that 0 ≥ 0 and 0 ≤ δ0 < 1. The ( 0, δ0)-DP condition implies ( , δ)-DP if and only if δ ≥ δ0 + (1− δ0)(e 0 − e )+/(1 + e 0).
Corollary 3.1 Assume that ≥ 0 ≥ 0 and δ ≤ [(1 + e )δ0 − e + e 0 ]/(1 + e 0). An ( , δ)-DP algorithm is ( 0, δ0)-DP.
Corollary 3.2 Let A be an ( 0, δ0)-DP algorithm with the privacy profile δA. Then
δA( ) ≤ δ0 + (1− δ0)(e 0 − e )+
1 + e 0 . (1)
We remark that the bound given in (1) is tight in the following sense: there is a specific ( 0, δ0)-DP algorithm A such that δA( ) is exactly δ0 + (1− δ0)(e 0 − e )+/(1 + e 0).
Corollary 3.1 states the exact partial order of logical implication on ( , δ)-DP conditions. Taking this partial order into account, the privacy profile derived from the naive inversion of the trade-off function can be refined into
δA( ) = min ({ δ | σ = f( 0, δ0) and δ ≥ δ0 + (1− δ0)(e 0 − e )+
1 + e 0
}) .
Intuitively, the refined privacy profile not only considers ( , δ)-DP provided directly by the trade-off function but also takes all pairs ( , δ) inferred by Corollary 3.1. Theorem 3.2 can itself be used as a tool to improve some DP results: we will discuss this improvement in Section 5. With this approach, we can derive the privacy profile of our second example to be δSGD( ) = min(δ2 + (1− δ2)(e
2 − e )+/(1 + e 2), exp{− 2}), where 2 ≈ 1.187 and δ2 ≈ 0.244. The privacy profile of our third example is δICEA( ) = min(δ3 + (1− δ3)(e 3 − e )+/(1 + e 3), K/ }), where K = 4/e2, 3 ≈ 1.159, and δ3 ≈ 0.468. Notice that δSGD and δICEA share a similar form: both are the smaller of two terms, one derived from Corollary 3.1 from a particular ( , δ)-DP pair and the other from inverting the trade-off function. This is no coincidence. We leave the derivation to Appendix B.
We next show the connection between GDP and the privacy profile: briefly, Gaussian differential privacy can be characterized as an infinite union of ( , δ)-DP conditions.
Theorem 3.2 A mechanism is µ-GDP if and only if it is ( , δµ( ))-DP for all ≥ 0, where
δµ( ) = Φ ( − µ + µ 2 ) − e Φ ( − µ − µ 2 ) . (2)
This result follows from properties of f -DP and is formulated as Corollary 2.13 in Dong et al. (2019). Prior to this general form, a similar expression for a special case appeared in Balle & Wang (2018). From the definition of the privacy profile, it follows immediately that an algorithm A with the privacy profile δA is µ-GDP if and only if δµ( ) ≥ δA( ) for all non-negative . 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 pane illustrates the privacy profiles of our examples. That of the Laplace mechanism
is derived in Balle et al. (2020a) as Theorem 3: given a noise parameter b and a global sensitivity ∆, the privacy profile of the Laplace mechanism is δ( ) = max(1 − exp{ε/2 −∆/(2b)}, 0). For the second and the third examples, we compare the naive privacy profiles obtained by inverting the trade-off function and the refined privacy profiles. The refined and naive privacy profiles take on notably different values around = 0. The inverted trade-off functions suggest that (0, δ) cannot be achieved by any choice of parameter σ. However, this is clearly not true, considering Theorem 3.1.
As shown in the right pane 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 µ-GDP for µ ∈ {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 . These examples illustrate that we cannot draw conclusions simply by looking at a graph. A privacy profile is defined on [0,∞), so it is hard to tell if an inequality is maintained as increases. Previous failures of ad hoc attempts at privacy have taught that privacy must be protected via tractable and objective means (Narayanan & Shmatikov, 2006; 2008; Barbaro & T. Zeller, 2006).
Performing this check via numerical evaluation yields similar problems: we cannot consider all values of on an infinite interval (or even a finite one, for that matter). Turning to closed forms for privacy profiles and δµ is also difficult: even if a given privacy profile is easy to handle, δµ presents some technical hurdles. The profile δµ and Φ are transcendental with different asymptotic behaviors for different values of µ and . This is clear from the right pane of Figure 1: near = 0, δµ is concave for µ = 4 but convex for µ = 1. As a further complication, both the first and second terms in the definition of δµ converge to 1 as → ∞, 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 (Malcolm, 1971; Cuyt et al., 2001). Due to the risk of catastrophic cancellation, a good approximation of Φ does not guarantee a good approximation of the GDP privacy profile. These problems make it difficult to tightly bound δµ 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 algorithmA with the privacy profile δA is ( h, µ)-head GDP if and only if δA( ) ≤ δµ( ) when ≤ h.
Definition 3.2 (Tail condition) An algorithm A with the privacy profile δA is ( t, µ)-tail GDP if and only if δA( ) ≤ δµ( ) when > t. In particular, we define A as (+∞, µ)-tail GDP if A is ( t, µ)-tail GDP for some t < +∞ and define A as ( t,+∞)-tail GDP if A is ( t, µ) for some µ < +∞.
The head condition checks the µ-GDP condition for near zero and the tail condition checks the µGDP condition for far away from zero. As such, the combination of ( , µ)-head GDP and ( , µ)-tail GDP is equivalent to µ-GDP.

heading: 4 THE GAUSSIAN DIFFERENTIAL PRIVACY TRANSFORMATION
text: In this section, we propose a new tool called the Gaussian Differential privacy transformation (GDPT). We start by establishing a link between the GDPT and the head and tail conditions and discuss how the GDPT can identify GDP algorithms and measure the value of µ.
Definition 4.1 (GDPT) Let f be a non-increasing, non-negative function defined on [0,+∞) satisfying f(0) ≤ 1. The Gaussian differential privacy transformation (GDPT) of f is the function Gf mapping [0,∞) to [0,∞) such that Gf ( ) = µGDP( , f( )), where µGDP(x, y) is the implicit function defined by the equation δµ(x) = y.
We highlight two critical features of the GDPT.
• The GDPT is order preserving: if f( ) ≥ g( ), then Gf ( ) ≥ Gg( ). • The GDPT of δµ is Gδµ( ) = µ, a constant function.
The first of these two features derives from the monotonicity of δµ( ). Given a fixed µ, δµ( ) is a strictly decreasing continuous function of . Given a fixed , δµ( ) is a strictly increasing continuous function of µ. Therefore, µ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 µGDP .
By taking advantage of the order-preserving property, direct comparisons between δµ and δ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δA to the constant function µ. The following theorems formalize this insight.
Theorem 4.1 An algorithm A with the privacy profile δA is ( h, µ)-head GDP if and only if µ ≥ sup({GδA( ) | ∈ [0, h]).
Theorem 4.2 An algorithm A with the privacy profile δA is ( t, µ)-tail GDP if and only if µ ≥ sup({GδA( ) | ∈ ( t,∞)).
Corollary 4.1 An algorithm A with the privacy profile δA is µ-GDP if and only if µ ≥ sup({GδA( ) | ∈ [0,∞)}).
Without the above results, we would be forced to search through an uncountably-large family of functions for a single δµ that never crosses δA anywhere on [0,∞) and has µ as small as possible. Now, with Theorem 4.1, we need only consider one function: the GDPT of δA. The tightest value µ is sup {GδA( )}. Using the GDPT framework, a condition for identifying GDP algorithms (that does not specify the exact value of µ) is simple to formulate. We do so in the following theorems.
Theorem 4.3 An algorithm A is GDP if and only if A is (+∞,+∞)-tail GDP.
Theorem 4.4 Let f be a non-increasing, non-negative function defined on [0,+∞) satisfying f(0) ≤ 1. Then
lim →+∞ Gf ( ) =
√ lim
→+∞
2
−2 log f( ) .
Theorems 4.3 and 4.4 give a useful criterion characterizing GDP and deepen our understanding of GDP. Putting the exact value of µ aside, a GDP algorithm must provide an infinite union of ( , δ)-DP conditions, where δ must be O(e− 2
) as → ∞. Refer to Appendices A.3 and A.4 for proofs of Theorems 4.3 and 4.4, respectively.
Using these newly-developed tools, we revisit our previous three examples for which the limit in Theorem 4.4 is 0, √ 1/2, and +∞, respectively. From these evaluations, we can conclude that the Laplace mechanism and SGD are GDP for some µ and that the privacy profile of the ICEA algorithm crosses every µ-GDP curve regardless of how large µ is, indicating that the ICEA algorithm is not GDP.
The left pane of Figure 2 shows the GDPTs of the three examples considered in this paper. All three GDPTs converge to a finite value as → 0+. This can be attributed to the fact that any algorithm providing some non-trivial ( , δ)-DP guarantee is (0, δ)-DP for some δ ∈ [0, 1). For larger values of , 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 diverging. These observations are consistent with the values of 0, √ 1/2, and∞ obtained from Theorem 4.4. 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.
Once an algorithm is confirmed to be GDP via Theorems 4.3 and 4.4, it is natural to be interested in the exact level of privacy protection, quantified by µ. 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 µ such that A is ( , µ)-head GDP.

heading: 4.1 MEASURING THE HEAD
text: Without additional knowledge, finding sup{GδA( ) | ∈ [0, h]}, even for a finite h, seems computationally infeasible as there are uncountably many real numbers in any non-empty interval and it is impossible to iterate through an infinite set. To solve this problem, we take advantage of the fact that µGDP has a bounded partial derivative.
Theorem 4.5 One of the partial derivatives of µGDP is uniformly bounded. Specifically, 0 ≤ ∂µGDP ( ,δ)
∂ ≤ √ 2π 2 .
Theorem 4.6 Given h ≥ 0, let D = h/n and xi = iD + h for i ∈ {0, . . . , n + 1}. The GDPT of A, denoted by GA( ), is bounded between the two staircase functions
G−δA( ) = n+1∑ i=0 µGDP(xi, δA(xi+1))× 1 ∈[xi,xi+1)
and
G+δA( ) = n+1∑ i=0 µGDP(xi+1, δA(xi))× 1 ∈[xi,xi+1).
Specifically,
max i∈{0,...,n} G−δA(xi) ≤ max ∈[0, h] GA( ) ≤ max i∈{0,...,n+1} G+δA(xi) ≤ maxi∈{0,...,n}
G−δA(xi) + √ 2πD. (3)
Refer to Appendix A.5 and A.6 for proofs of Theorem 4.5 and 4.6, respectively.
For any h < +∞, we can now bound any GDPT GδA to any precision on [0, h] without full pointwise evaluation because GδA is bounded between G + δA
and G−δA and each staircase function takes on only finitely many values. The inequalities in (3) provide a viable way to estimate maxGδA( ): maxi∈{0,...,n}G − δA (xi) and maxi∈{0,...,n+1}G + δA
(xi) can be computed by choosing the maximum value among 2n+ 2 evaluations of µGDP . For the completeness, we provide a detailed description of an efficient algorithm with a time complexity of O( h/D + log2(D) log( h)) in Appendix D.

heading: 4.2 CUTTING THE TAIL
text: With Theorem 4.6, one can verify ( h, µ)-head GDP conditions for arbitrarily large h and an arbitrarily precise approximation of µ. While the error in µ can be quantified by D, one gap remains: h can be arbitrarily large but can never truly be +∞. In this subsection, we discuss the gap between ( h, µ)-head GDP and true GDP (which is equivalent to (+∞, µ)-head GDP). Before giving a solution, we intuitively illustrate the gap between ( h, µ)-head GDP and true GDP. Consider the following two cases:
• GDP with catastrophic failure, where with probability 1 − p, A1 functions properly and exact µ-GDP is guaranteed, but with probability p,A1 malfunctions and discloses the entire dataset; and
• head-GDP with -DP, where A2 is both ( h, µ)-head GDP and ( h, 0)-DP.
The µ-GDP privacy guarantee lies strictly between those of A1 and A2: specifically, δA1( ) < δµ( ) < δA2( ).
In practice, µ is rarely above six in GDP and is rarely above 10 in -DP because more-extreme values provide almost no privacy protection (Dong et al., 2019). If we verify the head condition up to h = 100 (which is not difficult because the time required for verification grows linearly) and take µ = 6, then p = δµ( h) will be on the order of 10−43. If h is increased to 200, then p will be smaller than 10−202. Hence, we conclude that the gap won’t make any notable difference in practice with a proper choice of µ and h.
However, in some cases, one may still wish to fully mend the gap theoretically. This can also be achieved under the GDPT framework. A GDPT is a fixed function that inherits smoothness properties from the corresponding privacy profile. The maximum value of a GDPT can be analysed using standard functional tools. We give an example of such an analysis in Section 5. If the privacy profile is not given in a manageable closed form or the analysis is infeasible, we provide the following “clip and retify” procedure that can turn any ( h, µ)-head GDP algorithm into a µ-GDP one at the cost of some utility.
Theorem 4.7 LetA be a ( h, µ)-head GDP algorithm with a numerical output. Assume that−∞ < y− < y+ < +∞. Define C(y) = max(min(y, y+), y−) and R(z) = z + v, where v is sampled from Laplace(b) with b = (y+ − y−)/ h. ThenR ◦ C ◦ A is µ-GDP.
Refer to Appendix A.7 for proof of Theorem 4.7. We remark that, in order to minimize the utility loss, the bounds y− and y+ should be properly chosen and the head condition should be verified to an h that is as large as possible.

heading: 5 APPLICATIONS

heading: 5.1 GDPT OF -DP ALGORITHMS AND THE LAPLACE MECHANISM
text: By our previous analysis of the GDPT, we know that being GDP means that a privacy profile has a quickly vanishing tail (i.e., δ( ) must be O(e− 2
)). It is remarkable that another single parameter family of DP conditions, the -DP conditions, is also a property that pertains to the tail of privacy profiles. For any 0-DP algorithm, the privacy profile must be exactly 0 after 0. This suggests that 0-DP is stronger than GDP. Next, we will quantify this intuition using the tools developed in this paper.
By Theorem 3.2, we know if A is 0-DP, then in the worst case, δA( ) = (e 0 − e )+/(1 + e 0). We consider the GDPT of δA, denoted by GδA . It is easy to see that, for ≥ 0, GδA( ) = 0: we need only consider ∈ [0, 0). Let GδA( ) be denoted by µ . Using using the partial derivative of GδA derived in Appendix A.5, we know that
∂ ∂ GδA( ) =√ 2π exp {( µ2 + 2 )2 /(8µ2 ) }[ Φ(−µ
2 +2 2µ )− Φ(−µ02 ) ] . Then sign( ∂∂ GδA( )) = sign(µ − µ0 −
2 /µ0). We can conclude that µ ≤ µ0 and, further, that GδA( ) is strictly decreasing on [0, 0). By Theorem 4.1, we know that A is µ0-DP. This finding can be more generally formulated as the following theorem.
Theorem 5.1 Any ( , 0)-DP algorithm is also µ-GDP for µ ≥ −2Φ−1(1/(1 + e )).
Dong et al. (2019) pointed out that the DP guarantees of the Laplace mechanism are stronger than those correspondingly provided by -DP. We reaffirm this difference by showing that it still exists under the GDP framework. The Laplace mechanism satisfies µ-GDP for µ smaller than the bound given in Theorem 5.1. The GDPTs presented in Appendix E.1 illustrate this difference.

heading: 5.2 UTILITY REFINEMENT
text: 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 Feldman et al. (2018) is ( , δ)-DP and the trade-off function is σ = −C log(δ0)/ 0. To achieve (0.2, e−2)-DP, it appears that σ needs to be chosen as −C log(e−2)/0.2 = 10C. By Corollary 3.1, ( , δ)-DP implies (0.2, e−2)-DP when δ+ (1− δ)(e − e0.2)+/(1 + e ) = e−2. Numerical methods suggest that, by choosing ≈ 0.334 and δ ≈ 0.067, ( , δ)-DP implies (0.2, e−2)-DP but σ = −C log(δ)/ ≈ 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. For the general case and details of this derivation, refer to Appendix C.

heading: 5.3 EFFECT OF SUBSAMPLING
text: It is well known that a mechanism can be improved from a privacy perspective by adding extra steps to perturb its input or output. One popular approach is the subsampling technique (Balle et al., 2020a). We omit the details of this method and use the following result from Balle et al. (2020a).
LetA be an ( , δ)-DP algorithm and Sγ the Poisson subsampling procedure wherein each data point is retained with probability γ. Then A ◦ Sγ is (log(1 − γ + γe ), γδ)-DP when two datasets are considered differ in one element if one dataset equals to the other dataset plus one additional element. Combining this result with the partial derivatives of µGDP , the Poisson subsampling procedure can significantly decrease the value of µ around = 0 but has no effect on the GDPT’s tail. Therefore, in the worst case, a subsampling procedure does not improve the value of µ for a GDP algorithm. For detailed plots, refer to Appendix E.2.

heading: 6 CONCLUSION AND DISCUSSION
text: In this paper, we provided both an analytical understanding of and engineering tools for the GDP framework. Using the new notions we proposed, we gave solutions to two problems in GDP: identification and measurement. We further provided many applications of the proposed tools.
Our developments in this paper suggest numerous interesting directions for future work. The “clip and retify” procedure can be extended to provide more versatility to methods for privacy amplifications by utilizing more advanced composition and post-processing results. GDPT is generalizable to other parameterized DP notions such as RDP and cDP and enriches the DP literature with its tractability and visualizability.
Ethics Statement. Our work is majorly development of mathematical tools for the differential privacy framework. We cannot foresee any immediate real-world impact and believe those mathematical tools will contribute to the developments of privacy-aware technologies.
Reproducibility Statement. For all our theoretical results, we confirm that all necessary assumptions are properly addressed, and all proofs are provided unless trivial. No datasets and interactive virtual environments are involved in this paper. There are no experimental results in this work. Figures are only for demonstrative reasons as main results are supported by proofs.

heading: A APPENDIX: PROOFS
text: Proof A.1 Proof of Theorem 3.1:
Sufficiency:
When ≥ 0, the sufficiency is trivial as δ = δ0. When < 0, given that A is ( 0, δ0)-DP, by the definition, for any pair of datasets S and S′ that differ in the record of a single individual and any event E,
P [A(S) ∈ E] ≤ e 0P [A (S′) ∈ E] + δ0.
When P [A (S′) ∈ E] ≤ 1−δ01+e 0 := c0,
P [A(S) ∈ E] ≤ e 0P [A (S′) ∈ E] + δ0 ≤ (e 0 + e − e )P [A (S′) ∈ E] + δ0 + δ − δ ≤ e 0P [A (S′) ∈ E] + δ + (e 0 − e )c0 + δ0 − δ
≤ e P [A (S′) ∈ E] + δ + (e 0 − e )c0 − (1− δ0)(e 0 − e )
1 + e 0
≤ e P [A (S′) ∈ E] + δ.
When c0 ≤ P [A (S′) ∈ E] ≤ 1,
P [A(S) ∈ E] = 1− P [A(S) ∈ Ec] ≤ 1− e− 0(P [A (S′) ∈ Ec]− δ0) = 1− e− 0(1− P [A (S′) ∈ E]− δ0) = 1− e− 0 + e− 0P [A (S′) ∈ E] + e− 0δ0 = 1− e− 0 + e− 0δ0 + δ − δ + (e− 0 + e − e )P [A (S′) ∈ E] = e P [A (S′) ∈ E] + δ + 1− e− 0 + e− 0δ0 − δ + (e− 0 − e )P [A (S′) ∈ E] ≤ e P [A (S′) ∈ E] + δ + 1− e− 0 + e− 0δ0 − δ + (e− 0 − e )c0
= e P [A (S′) ∈ E] + δ + (1− δ0)( e− 0 − e
1 + e 0 − e− 0) + 1− δ
≤ e P [A (S′) ∈ E] + δ + (1− δ0)( e− 0 − e
1 + e 0 − e− 0 + 1 + e − e 0 1 + e 0 )
= e P [A (S′) ∈ E] + δ.
Necessity:
We prove the necessity by giving a specific ( 0, δ0)-DP algorithm A such that δA( ) is exactly δ0 + (1−δ0)(e 0−e )+
1+e 0 .
Define Ωe = {1, 2, 3, 4} and ΩS = {0, 1}. Let ≥ 0, 0 ≤ δ0 ≤ 1 and denote e 0 1+e 0 as α0. Let A be a randomized algorithm that take a single point from ΩS and generate output as follows: P (A(S) = 1 | S = 0) = δ0, P (A(S) = 2 | S = 0) = 0, P (A(S) = 3 | S = 0) = (1− δ0)α0, P (A(S) = 4 | S = 0) = (1− δ0)(1− α0),  P (A(S) = 1 | S = 1) = 0, P (A(S) = 2 | S = 1) = δ0, P (A(S) = 3 | S = 1) = (1− δ0)(1− α0), P (A(S) = 4 | S = 1) = (1− δ0)α0.
By definition, δ( ) is the smallest δ such that P (A(S) ⊂ E | S = s) ≤ e P (A(S) ⊂ E | S = 1−s)+δ holds true for all E ⊂ Ωe and s ∈ ΩS . By checking all 64 combinations, we can conclude that δA( ) = δ0 + (1−δ0)(e 0−e )+ 1+e 0 .
We present a key lemma underlying much of the theoretical analysis and may be of use for future developments.
Lemma A.1 Define δ̃µ( ) = µe −a2/2 √ 2πa2 , where a = − µ + µ 2 . It follows that lim →+∞ δµ( ) δ̃µ( ) = 1.
Proof A.2 Proof of Lemma A.1:
It is well known that (Abramowitz et al., 1988), for t < 0:
1
−t+ √ t2 + 4 <
√ π
2 exp
( t2
2
) Φ(t) <
1 −t+ √ t2 + 8π .
Let a = ( − εµ + µ 2 ) and b = ( − εµ − µ 2 ) ,
lim →∞ δµ( ) = lim →∞
Φ (a)− e Φ (b)
≤ √ 2
π lim →∞
exp ( −a2 2 ) −a+ √ a2 + 8π − exp ( −b2 2 + ) −b+ √ b2 + 4 .
=
√ 2
π lim →∞ exp
( −a2
2 ) 1 −a+ √ a2 + 8π − 1 −b+ √ b2 + 4  . ≤ √ 2
π lim →∞ exp
( −a2
2 )( −1 a ) .
= 0.
lim →∞ δµ( ) = lim →∞
Φ (a)− e Φ (b)
≥ √ 2
π lim →∞
exp ( −a2 2 ) −a+ √ a2 + 4 − exp ( −b2 2 + ) −b+ √ b2 + 8π .
=
√ 2
π lim →∞ exp
( −a2
2 ) 1 −a+ √ a2 + 4 − 1 −b+ √ b2 + 8π  . ≥ √ 2
π lim →∞ exp
( −a2
2 )( −1 b ) .
= 0.
Therefore,
lim →∞ δµ( ) = 0. (4)
It is easy to see that,
lim →∞ δ̃µ( ) = lim →∞
µe−a 2/2
√ 2πa2 = 0 (5)
By L’Hospital’s rule:
lim →∞
δ̃µ( ) δµ( ) = lim →∞
δ̃′µ( ) δ′µ( )
= lim →∞
− e−
a2
2 ( a2 + 2 ) √
2πa3
/ e Φ(b)
= lim →∞
e− b2
2 Φ(b)√ 2πb
= lim b→−∞
e− b2
2 Φ(b)√ 2πb
= 1.
Proof A.3 Proof of Theorem 4.3:
It is easy to see that A is (+∞,+∞)-tail GDP if and only if lim →+∞ GδA( ) < +∞.
Sufficiency:
If A is µ-GDP. Then lim →+∞ GδA( ) ≤ lim →+∞Gδµ( ) = µ.
Necessity:
If lim →+∞ GδA( ) = µ < +∞, there must be a t > 0 such that A is ( t, µ0 + 1)-tail GDP.
Notice that lim µ→∞ δµ( t) = 1, we can pick µ1 > µ0 large enough such that δµ1( t) > δA(0).
This is possible because by Theorem 3.1, δA(0) < 1. Then for ∈ [0, t), δA( ) ≤ δA(0) ≤ δµ1( t) ≤ δµ1( ). A is both ( t, µ)-head and tail GDP for µ = µ0 + µ1 + 1. A is GDP as desired.
Proof A.4 Proof of Theorem 4.4:
Let lim →+∞ Gf ( ) = µt.
First we show that lim →∞
2
−2 log δA( ) ≤ µ 2 t :
By the definition the limit, for any µ0 > µt, for sufficient large , Gf ( ) < µ0 and further δA( ) ≤ δµ0( ). Hence, lim
→∞ δA( ) δµ0 ( ) ≤ 1. By Lemma A.1, lim →∞ δA( ) δ̃µ0 ( ) ≤ 1.
Then lim →∞
2 −2 log δA( ) ≤ lim →∞ 2 −2 log δ̃µ0 ( ) = µ20.
lim →∞
2
−2 log δA( ) ≤ µt as desired as we take µ0 → µt.
Next we show that lim →∞
2
−2 log δA( ) ≥ µ 2 t :
If lim →∞
2
−2 log δA( ) = µ 2 0 < µ 2 t , then by Lemma A.1,
lim →∞
2
−2 log δA( ) −
2
−2 log δµt( ) = lim →∞
2
−2 log δA( ) − lim →∞
2
−2 log δ̃µt( ) < µ20 − µ2t
Then for a sufficiently large 0,
20 −2 log δA( 0) − 2 0 −2 log δµ0( 0) < 0.
Since log is an increasing function, it follows that δA( 0) < δµ0( 0). Then lim →+∞ Gf ( ) ≤ µ0 < µt, which is a contradiction.
Proof A.5 Proof of Theorem 4.5:
Let Gµ( ) = F ( , δµ( )) and F (x, y) = µGDP(x, y).
By definition of µGDP , Gµ( ) = µ.
On one hand,  ∂Gµ( ) ∂ = ∂µ ∂ = 0, ∂Gµ( )
∂µ = ∂µ ∂µ = 1.
On the other hand, by chain rule,  ∂Gµ( ) ∂ = ∂F ∂x + ∂F ∂y ∂δµ( ) ∂ , ∂Gµ( )
∂µ = ∂F ∂y ∂δµ( ) ∂µ .
Therefore,  ∂F ∂y = ( ∂δµ( ) ∂µ )−1, ∂F
∂x = −(∂δµ( ) ∂µ )−1 ∂δµ( ) ∂ .
Using the close forms, ∂δµ( )∂ and ∂δµ( ) ∂µ can be directly computed: ∂δµ( ) ∂ = −e Φ(−µ 2 + 2 2µ ), ∂δµ( )
∂µ = e − (
µ2−2 ) 2
8µ2 √ 2π .
Hence,  ∂F ∂x = √ 2πe (µ2+2 ) 2 8µ2 Φ(−µ 2 + 2 2µ ) ≤ √ 2πe µ2 8 Φ(−µ 2 ) ≤ √ 2π 2 , ∂F
∂y = √ 2πe (µ2−2 )
2
8µ2 > 0.
Notice that ∂F∂x = √ 2πe (µ2+2 )
2
8µ2 Φ(−µ 2+2 2µ ) > 0, combined with the fact that ∂F ∂x ≤ √ 2π 2 , we can
conclude that 0 ≤ ∂µGDP ( ,δ)∂ ≤ √ 2π 2 . By ∂F ∂y > 0, we can see GDPT is order preserving.
Proof A.6 Proof of Theorem 4.6:
We now consider the gap between maxi∈{0,··· ,n}{G−δA(xi)} and maxi∈{0,··· ,n+1}{G + δA (xi)} bound the length of [µ−, µ+] in two cases.
Case 1: If maxi∈{0,··· ,n+1}{G+δA(xi)} = G + δA (x0), then maxi∈{0,··· ,n+1}{G+δA(xi)} = G+δA(x0) = µGDP(D, δA(0)) ≤ µGDP(0, δA(0)) + √ 2πD 2 . Therefore,
max ∈[0, h]
G( ) ≤ G+δA(x0) ≤ {G − δA (x0)}+ √ 2πD
2 .
Case 2: If maxi∈{0,··· ,n+1}{G+δA(xi)} 6= G + δA (x0), then by the order preserving property, the optimal µ lies in [µ−, µ+], where µ− = max(µh,maxi∈{0,··· ,n}{G−δA(xi)}) and µ + = max(µh,maxi∈{1,··· ,n+1}{G+δA(xi)}). Notice that max
i∈{0,··· ,n} {G−δA(xi)} = maxi∈{0,··· ,n} {µGDP(xi, δA(xi+1))} = max i∈{1,··· ,n+1} {µGDP(xi−1, δA(xi))}
≥ max i∈{1,··· ,n+1}
{µGDP(xi+1, δA(xi))− √ 2πD}
≥ max i∈{1,··· ,n+1}
{G+δA(xi)} − √ 2πD.
In both cases the gap is no greater than √ 2πD as desired.
Proof A.7 Proof of Theorem 4.7:
By the definition of C, C ◦ A is bounded in [y−, y+]. Therefore the global sensitivity of C ◦ A is no greater than y +−y−. Then R ◦ C ◦ A is a special case of the Laplace mechanism. By Balle et al. (2020a),R ◦ C ◦ A is h-DP. Then δR◦C◦A( ) = 0 < δµ( ) for any ≥ h. In addition, because of the post-processing property, δR◦C◦A( ) ≤ δA( ) < δµ( ) for any < h. Therefore,R ◦ C ◦ A is µ-GDP.

heading: B APPENDIX: REFINING THE PRIVACY PROFILE
text: Given a trade-off function σ = f( , δ) and a fixed parameter σ. From definition of the trade-off function it is instant that the for any ( , δ)∈ Ω = {( , δ) | σ = f( , δ)}, ( , δ)-DP is guaranteed. Then, ( , δ)-DP is also guaranteed if there is a ( 0, δ0) ∈ Ω such that ( 0, δ0)-DP implies ( , δ)-DP. Therefore,
δA( ) = min ( {δ | σ = f( 0, δ0) and δ ≥ δ0 + (1− δ0)(e 0 − e )+ 1 + e 0 } ) .
Notice that by Corollary 3.2, ( 0, δ0)-DP implies ( , δ) with δ < δ0 only if < 0, we rewrite the δA( ) as:
δA( ) = inf 0∈[ ,∞) g( , 0),
where g( , 0) := (1− δ̂A( 0)) e 0−e e 0+1 + δ̂A( 0) and δ̂A is the naive privacy profile defined implicitly by σ = f( 0, δ0). For continuously differentiable f , the minimum value of the right-hand side can be found be take the derivative:
∂g( , 0)
∂ 0 =
1 + e
(1 + e 0)2
[ δ̂A ′ ( 0) + e 0(1− δ̂A( 0) + δ̂A ′ ( 0)) ] .
We remark that the sign of ∂δA( )∂ 0 does not depend on . For both of our example 2 and 3, we both find a particular value i such that Sign(∂g( , 0)∂ 0 ) = −Sign( − i). This means for ≥ i, δA( ) = δ̂A( ) and otherwise δA( ) equals to the δ value derived from ( , δ̂A( )).
C APPENDIX: REFINING THE σ
Given a trade-off function σ = f( , δ) and desired ( , δ). From definition of the trade-off function, ( , δ)-DP is guaranteed when σ = f( , δ). We treat the σ as the noise parameter and without loss of generality we assume a smaller value of σ is preferred. Notice that ( , δ)-DP is also guaranteed if there is a ( 0, δ0) ∈ Ω such that ( 0, δ0)-DP implies ( , δ)-DP. Therefore, σ can be chosen as,
σ− = min ( {f( 0, δ0) | δ ≥ δ0 + (1− δ0)(e 0 − e )+ 1 + e 0 } ) .
Notice that by Corollary 3.2, ( 0, δ0)-DP implies ( , δ) with δ < δ0 only if < 0, we rewrite the σ− as:
σ− = inf 0∈[ ,∞) g( , 0),
where g( , 0) := f( 0, (1 − δ̂A( 0)) e 0−e e 0+1 + δ̂A( 0)) and δ̂A is the naive privacy profile defined implicitly by σ = f( 0, δ0). For continuously differentiable f , the minimum value of the right-hand side can be found be take the derivative:
∂g( , 0)
∂ 0 =
1 + e
(1 + e 0)2
[ δ̂A ′ ( 0) + e 0(1− δ̂A( 0) + δ̂A ′ ( 0)) ] ∂f ∂δ | = 0,δ=δ0 + ∂f ∂ | = 0,δ=δ0 .
We remark that the sign of ∂δA( )∂ 0 does not depend on and the zero point can be effectively solved numerically.

heading: D A SELF-CONTAINED EFFICIENT HEAD MEASUREMENT ALGORITHM
text: First we formalise the binary search algorithm to find µGDP :
Algorithm 1: Binary search Input: , δ, µmax, b ; Output: µ−, µ+ (lower and upper bound of µ).; µ− ← 0; µ+ ← µmax; while µ+ − µ− > b do
µ = µ ++µ−
2 ; if δµ( ) > δ then
µ+ ← µ0; else
µ− ← µ0; end
end return µ+, µ−.
Given a proper searching range [0, µmax], the algorithm 1 yields µ+ and µ− such that µ− ≤ µGDP( , δ) ≤ µ+ and µ+−µ− < b. We denote µ+ as µ+GDP( , δ, µmax, b) and µ − as µ− GDP
( , δ, µmax, b). When searching for µ via privacy profiles, the µmax can chosen as µGDP(µt, δA(0)) because µGDP will not exceed this value on [0, t] (refer to Theorem 4.3 for the value of µt). Alternatively, µmax can be set to a large constant for convenience, for example 10. In this case, if the outputted µ+ equals to the preset value (10) then the privacy profile fails to imply 10-GDP. In practice, GDP with µ ≥ 6 provides almost no privacy protection Dong et al. (2019).
With the formal definition of binary search we use, the exhaustive iteration method to bound the staircase functions outlined in Theorem 4.6 can be formally written as follows:
Algorithm 2: Finding µ with privacy profiles (Naive). Input: δA, h, µt, c, µmax. (Privacy profile, the end point of searching h, µ given by Theorem
4.3, reciprocal of error margin, searching range); Output: µ−, µ+ (lower and upper bound of µ).; i← 0; n← d √ 8cπ he+ 1; D ← hn−1 ; µ− ← max(µh, µt); µ+ ← µmax; while i ≤ n+ 1 do
x− ← iD + h; x+ ← (i+ 1)D + h; µ+ ← max(µ+, µ+GDP(x −, δA(x +), µmax, 1 2c )); µ− ← max(µ−, µ−GDP(x +), δA(x −, µmax, 1 2c ));
i← i+ 1 end return µ+, µ−.
Algorithm 2 naively go thorough all G−δA(xi) and G + δA
(xi). By the choice of D, the true gap between maxG−δA( ) and maxG + δA
( ) is less than 12c and the binary search estimate the µGDP with an error less than 12c . Combined together, the overall gap between estimated µ
+ and µ− is less than 1 c . However, there is still room for optimization:
We take µ+ ← max(µ+, µ+GDP(x −, δA(x +), µmax, 1 2c )) for example, same optimization can be applied to µ− ← max(µ−, µ−GDP(x +, δA(x −, µmax, 1 2c ))) as well. The naive operation, µ+ ← max(µ+, µ + GDP (x−, δA(x +), µmax, 1 2c )) can be optimized into ”If δµ+(x −) < δA(x +), then µ+ ← µ+ GDP (x−, δA(x +), µmax, 1 2c )). To see this, we list all three possibilities as follows:
• Case 1: µ+ < µGDP(x −, δA(x +)) ≤ µ+ GDP (x−, δA(x +), µmax, 1 2c )). • Case 2: µGDP(x −, δA(x +)) ≤ µ+ ≤ µ+ GDP (x−, δA(x +), µmax, 1 2c )). • Case 3: µGDP(x −, δA(x +)) ≤ µ+ GDP (x−, δA(x +), µmax, 1 2c )) < µ +.
In case 1, both of the naive operation and the optimized operation will update µ+ to µ+
GDP (x−, δA(x +), µmax, 1 2c )).
In case 2, the optimized operation will do nothing, because the test δµ+(x−) < δA(x+) will fail. The naive operation will update µ+ due to the error of binary search, which should be avoided.
In case 3, the optimized operation will do nothing, because the test δµ+(x−) < δA(x+) will fail. The naive operation will also do nothing because the max operator will choose µ+.
To sum up, the optimized operation always give a more accurate update.
Besides, we want to avoid case 1 because only in that case a binary search is needed. Notice that case 1 happens only if δµ+(x−) < δA(x+), which is equivalent to µ+ < µGDP(x −, δA(x +)). In the k + 1 round of loop, the condition µ+ < µGDP(x −, δA(x
+)) holds true only if for all j ∈ {0, · · · , k}, µGDP(x−j , δA(x + j )) < µGDP(x −, δA(x +)), where x−j and x + j are the values of x
− and x+ in the round j. This inspire us to shuffle xi before iteration because after shuffling, the probability of ”µGDP(x − j , δA(x + j )) < µGDP(x −, δA(x +)) for all j ∈ {0, · · · , k}” will be 1k+1 . The expected
occurrence of case 1 will be ∑n+1 k=0 1 k+1 = O(log(n)). We present the complete optimized algorithm as follows:
Algorithm 3: Finding µ with privacy profiles (optimized). Input: δA, h, µt, c, µmax. (Privacy profile, the end point of searching h, µ given by Theorem
4.3, reciprocal of error margin, searching range); Output: µ−, µ+ (lower and upper bound of µ).; i← 0; n← d √ 8cπ he+ 1; D ← hn−1 ; µ− ← max(µh, µt); µ+ ← µmax; S = [0, 1, · · · , n+ 1]; Shuffle S; while i ≤ n+ 1 do
x− ← S[i]D + h; x+ ← S[i+ 1]D + h; if δµ+(x−) < δA(x+) then
µ+ ← µ+ GDP (x−, δA(x +), µmax, 1 2c ));
end if δµ−(x+) < δA(x−) then
µ− ← µ− GDP (x+, δA(x −), µmax, 1 2c ));
end i← i+ 1
end return µ+, µ−.
The time complexity of shuffling S is O(n) = O( hc). Each binary search has a time complexity of O(log(c)) and the expected number of binary searches is O(log( hc)). The overall time complexity of the optimized algorithm is therefore O( hc+ log2(c) log( h)).

heading: E APPENDIX: PLOTS
text: E.1 THE LAPLACE MECHANISM UNDER GDP
E.2 THE EFFECT OF SUBSAMPLING

Review summaries:
## Summary of Contributions  This paper considers Gaussian differential privacy (GDP) notion which is an extension of $(\epsilon, \delta)$-differential privacy (DP). Roughly speaking, an algorithm is $\mu$-GDP if it is "at least as private as Gaussian mechanism with noise multiplier $1/\mu$". The main advantages of GDP are that (i) it has a simple and sharper composition theorem than $(\epsilon, \delta)$-DP and (ii) it has only a single parameter $\mu$ leading to simpler/more efficient computation compared to other DP notions that provide good composition (e.g. $f$-DP or Privacy Loss Distribution (PLD)).  This paper develops tools that can help understand/deploy GDP more easily. Specifically: - They propose Gaussian Differential Privacy Transformation (GDPT) which roughly speaking is the curve $\mu: \mathbb{R} \to \mathbb{R}$ where $\mu(\epsilon)$ is the smallest $\epsilon$ for which the algorithm is at least as private as Gaussian mechanism of noise multiplier $1/\mu(\epsilon)$ at this particular value of $\epsilon$. - With the above notion, they derive (in Theorems 4.3, 4.4) the condition for an algorithm to be $\mu$-GDP for some finite $\mu$: it must be $(\epsilon, \delta(\epsilon))$-DP where $\limsup \frac{\epsilon^2}{-\log \delta(\epsilon)}$ is finite. - They then show how to approximately check whether an algorithm is GDP. Specifically, they show that it suffices to check a certain condition on a finite number of points (corresponding to an upper staircase in Figure 2 right). They show that if this condition holds the algorithm is $(\epsilon_h, \mu)$-head GDP, roughly meaning that it is "GDP" for all $\epsilon < \epsilon_h$. - They argue that in practice taking $\epsilon_h$ to be sufficiently large should be enough. But they also give a "clip and noise" procedure to turn an $(\epsilon_h, \mu)$-head GDP algorithm into one which is actually $\mu$-GDP.    Along the way, the paper also shows a new implication between $(\epsilon, \delta)$-DP and $(\epsilon', \delta')$-DP. Previously, it was known that the former implies the latter if $\epsilon' \geq \epsilon$ and $\delta' \geq \delta$. In Theorem 3.1 of this paper, the authors show that the implication may even hold when $\epsilon > \epsilon'$ but $\delta'$ also has to be larger than $\delta$ by a certain amount (depending on $\delta, \epsilon, \epsilon'$). The authors give some example in Section 5 where this relation gives non-trivial implications for some known algorithms.

The paper develops tools for analyzing private algorithms in the framework of Gaussian Differential Privacy (GDP). GDP is a strengthening of approximate differential privacy, similar in spirit to concentrated differential privacy (CDP): both GDP and CDP capture the privacy guarantees of the Gaussian noise mechanism, but generalize them in different directions. GDP has a number of nice analytical properties but analyzing the GDP guarantees of an algorithm can be difficult, as it involves comparing two different functions on $[0,\infty)$. The paper proposes a method to reduce this problem to comparing a function against a fixed constant function, making numerical or analytical GDP analysis of a given algorithm easier.

This work is an investigation into the newly proposed Gaussian Differential privacy (GDP) in the context of existing formulations of epsilon, delta differential privacy (DP). Authors propose a novel framework for GDP transformation (GDPT) that analyses the properties of GDP and contrasts it to DP through the lens of the adversarial (head/tail composition) analysis, showing both theoretically and empirically that it results in better algorithmic utility. Authors provide a list of applications for GDPT and outline the benefits of this approach (primarily through tighter privacy bounds).