Identification, Amplification and Measurement: A bridge to Gaussian Differential Privacy
Authors: Yi Liu
Ke Sun
Bei Jiang
Linglong Kong
Venue: NeurIPS 2022 Accept (2022)
Keywords: Differential privacy
Gaussian differential privacy
Privacy profile

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.

Identification, Amplification and Measurement: A bridge to Gaussian Differential Privacy
Liu
Ke Sun Department of Mathematical and Statistical Sciences University of Alberta SaunbQualbertar
Department of Mathematical and Statistical Sciences University of Alberta yliu16@ualbertar
Bei Jiang Department of Mathematical and Statistical Sciences University of Alberta bei heil@ualberta.c ca
Linglong Kong Department of Mathematical and Statistical Sciences University of Alberta 1kongQualberta. ca
Abstract
Gaussian differential privacy (GDP) is a single-parameter family privacy notions that provides coherent guarantees to avoid the exposure of sensitive individual information. Despite the extra interpretability and tighter bounds under composi- tion GDP provides, many widely used mechanisms (e.g., the Laplace mechanism) inherently provide GDP guarantees but often fail to take advantage framework because their privacy guarantees were derived under different back- ground. this paper, we study the asymptotic propertics of privacy profiles and develop 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, μ with arbitrarily small and quantifiable margin error. For non GDP algorithms, we provide post-prose pos--prcessing procedure that can amplify existing privacy guarantees meet the GDP condition. As applications, we compare two Lingle-paramete families of privacy notions, e-DP, and 4-GDP, and show that all 6-DP algorithms are intrinsically also GDP. Lastly, show that the combination of our measurement process and the composition theorem of GDP powerful and convenient tool handle compositions compared the traditional standard and advanced composition theorems.
this new
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 privacy concerns can be traced back early as 1969 [27). the concept of privacy is often perceived as "vaguee and difficult to get into right perspective" [34]. Through its alluring convenience and promise 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 no protection against the exposure of individual data, as evidenced by the AOL search log and Netflix Challenge dataset controversies
30
6
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

Differential privacy (DP) first gained traction as it met the urgent need for rigour and quantifiability in privacy protection [14. 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 (44] A randomized algorithm A, taking a dataset consisting of individuals as its input, is (e, 8) diffeerrenlyl private if. for any puir of datasets S and S' that differ in the record of a single individual and any event E,
P[A(S) E S ( E +
E
When 6 = 0, A is called c-differentially private (c-DP).
While the notion of (e, 8D- has wide applications T2 16 10 21]. there are few notable drawbacks to this framework. One is the poor interpretability of (c, DD- unlike other concepts in machine learning, DP should not remain 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 (e, 8 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 building block. It natural to expect that a DP learning versions of these components. However, the DP
algorithm can be built using differentiallly-rriee composition properties cannot generally be well characterized within the framework of 6D-P) leading to very loose composition theorems.
To overcome the drawbacks of (c, 5)-DP, numerous variants have been developed, including the the -ocmentt-accouutant based Rényi DP [28], as well as
hypothesis- tiiiis-tttttnnnnsiiie -ased f-DP [3 13
concentrated DP and its variants 99 g Despite their very different perspectives, all of these DP
variants can be fully characterized by an infinite union of (e, 8)-DP guarantees. In particular, there is a two-way embedding between f-DP and the infinite union of (e, 6DD guarantees: any guarantee provided by an infinite union of (e, dDD can be fully characterized by f-DP and vice visa [13). Consequently, f-DP has the versatility to treat all of the above notions as special cases.
In addition to its versatility, fDD is more interpretable than other DP paradigms because it considers privacy protection from an attacker's perspective. Under f-D,, an attacker is challenged with the aypothesis-testingg problem
Ho the underlying dataset is S
versus
H1 the underlying dataset is S'
and given output of an algorithm A, where S and S' are neighbouring datasets. The harder this testing problem is, the less privacy leakage AA has. To see this, consider the dilemma that the attacker is facing. The attacker must reject either Hg or H, based on the given output of A: this means the attacker must select subset Ro of Range(A) and reject Ho if the sampled output is in Ro (or must otherwise reject H1). The attacker is more likely to incorrectly reject Ho (in a type error) when Ro is large. Conversely, if Ro is small, the attacker is more likely incorrectly reject H₁ (in type II error). We say that an algorithm A is f-DP if, for any a E [0, 1]. no attacker can simultancously bound the probability of type error below a and bound the probability of type II error below f(a). Such f is called trade-off function and controls the strength of the privacy protection.
The versatility afforded by 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 repre- senting safety levels as a curve amenable to human interpretation. Gaussian differential privacy (GDP), as a parametric family of /-DP guarantees, provides a balance between interpretability and versatility. GDP guarantees are parameterized by single value μ and use the trade-off function f(a) = Φ (1-1(11- -a- a) /4), 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 1) and N N(u, 1) on the basis of a single observation. Aside from its visual interpretation, GDP also has unique composition theorems: the composition of a f41- and
JtDP algorithm is, as expected, Vp² + DDPG This property can easily generalized to n-fold composition. GDP also has a special central limit theorem implying that all sypothesis-testing-aee definitions of privacy converge to GDP terms of a limit the number of compositions. Readers referred to [3] for more information.
2

---

1.1 Outline
The goal of this paper is to provide bridge between GDP and algorithms developed under other DP frameworks. We start by presenting often-overlooked partial order on (e, 6DD conditions induced by logical implication. Ignoring this partial order will lead to problematic asymptotic analysis.
We then break down GDP into two parts: head condition and a tail condition. We show that the latter, through single limit of mechanism's 's privacy profile, is sufficient to distinguish between GDP and non-GDP algorithms. For GDP algorithms, this criterion also provides lower bound for the privacy protection parameter ş 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 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 μ 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 e-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 8)-P conditions
The benefits of DP come with a price. As outlined in the definition of DP, any DP algorithm must be randomized. This randomization 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 higher level of privacy protection, stronger utility compromise should be made. This leads to the paramount problem of the "privacy-utility trade-off". Under the (c. 6DD framework, this trade-off is often characterized in form of o f(c, 5): to achieve (c, -D- the utility parameter (usually the scale of noise) needs to be chosen as f(c. 6). Therefore, an algorithm can be (e, 6DP for multiple pairs of and 8: the union of all such pairs provides a complete image of the algorithm under the (c, 6)-DP framework. In particular, an (r, 5)DP mechanism is also (c', dD) for any 22 c and any 8' 2 5. The infinite union of (c, 8) pairs can thus be represented as the smallest 8 associated with each c. This intuition is formulated as privacy profile in (5) The privacy profile corresponding to a collection of (c, dD-DP guarantees 12 is defined as the curve in [0, oo) x [0, IJ separating the space of privacy parameters into two regions, one of which contains exactly the pairs in Q. The privacy profile provides as much information as P itself. Many privacy guarantees and privacy notions, including (c. DD,, Rényi DP, f-DP, GDP, and concentrated DP, can be embedded into a family of privacy profile curves and fully characterized 3 A privacy profile can be provided derived by algorithm's 's designer 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 [14). The level of privacy that the Laplace mechanism can provide is determined by the scale of the added Laplacian noise. Given a global sensitivity A, the value of b needs to be chosen as [(e, 0) A/e in order to provide an (e, O)-DP guarantee. Despite its long history, the Laplace Our second example is a family of algorithms in which a noise parameter has the form o = AE- *Vlog(B/5) Examples include: the goodness of fit algorithm [18], noisy stochastic gradient descent and its variants [ 17 and the one-shot spectral method and the one-shot Laplace algorithm (33]. Our third example comes from the field of federated learning: given users and the number of messages m, the invisibility
mechanism has remained in use and study in recent years [32 22 36 25
cloak encoder algorithm (ICEA) from 23 is (c, DD if m > 10 10log(n/((o)) 20 See also 19 for other analysis of ICEA.
For figures and numerical demonstrations in this paper, we use b 2/A for the Laplace mechanism; 2 for the second example, which refer to as SGD; and 20
A 2, B- 1, and
3

---

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 [3.. privacy guarantees are given in the form of privacy-utility trade-off equation a g(e, 6). Given a, it is tempting to derive the privacy profile by inverting 9 (i.e., as d = min (6 = g(c,,))) because an (Fo, 60) DDP algorithm is trivially (c, 6DD for any 2 60 and 6 2 dg- However, in most cases, a privacy profile naively derived 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 (e, -DP conditions below.
Theorem 2.1 Assume that eo 2 0 and 60 1. The (Eo, 6DP condition implies (e, if and only if 2 6g + 50) - 10/(11+00
Theorem 2.1 states the exact partial order of logical implication (c. 8)-DP conditions. Though not being explicily discussed in this form previous literature on DP, this partial order can be implicitly derived from other results (c.g. proposition 2.11 of [13]). Taking this partial order into account, the privacy profile derived from the naive inversion of the trade-off function can be refined into
(c(e) min ((010= g(ea, do) and 5 2 80 + (1 - (1-do)(e" do)(e
-69 -
1 14.50 e
Intuitively, the refined privacy profile not only considers (e. 0)-DP provided directly by the trade-off'
function but also takes all pairs (e, inferred by corollary 2.1 See figure [ for comparison 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 (e, 8)DD) conditions.
Theorem 3.1 ([Corollary 2.13 < 2 0, where
(3) mechanism μ-GDP if and only if (c,5)(c))-DP for all
(c) 1 (--
(- 11 4 2
12 2
e
(1)
This result follows from properties of f-DP. Prior to this general form, a expression for special case appeared in [5). From the definition of the privacy profile, it follows immediately that an algorithm A with the privacy profile & is μ μ-GDP if and only if (c) 2 (c(c) for all non-negative c. 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 few visual examples in Figure 1 The left side ofT illlstraaes the privacy profiles of our examples. That of the Laplace mechanism is derived in 3 as Theorem 3: given a noise parameter b and a global sensitivity A, the privacy profile of the Laplace mechanism is d(e) = max(1 exp(s/2 - A (26)). 0). For the second and the third examples, 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 0. The inverted trade-off functions suggest that (0, 5) cannot be achieved by any choice of parameter a. However, this is clearly not true, considering Theorem 2.1
As shown in right side of Figure 1 the Laplace mechanism's 's privacy profile is below the 2-GDP and 4-GDP curves but crosses the 1-GPP 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 GDGD for μ E {1, 2, 2). It is hard to tell whether or not the SGD curve crosses the I-GDP curve and we cannot say if it will cross the 2-GDP even the 4-GDP curve at large value of 6. These examples illustrate that we cannot draw conclusions simply by looking at a graph. A privacy increases. Previous
profile is defined on [0, )o), so it is hard to tell if an inequality is maintained failures of ad hoc attempts at privacy have taught that privacy must be protected via tractable and objective means 30 61
Performing this check via numerical evaluation yields similar problems: we cannot consider all values of e on an infinite interval (or even finite one, for that matter). Turning to closed forms for privacy profiles and 5, is also difficult; even if given privacy profile easy to handle, 6, presents some technical hurdles. The profile 6, and de are transcendental with different asymptotic behaviors for

---

10
550
ICEA Retied
Laplace
Rodi
Leplece
0.4
burgte d
1.0
1.5 3.5
3.0
1.5 7.5
0.0
Figure 1: Left: Examples of privacy profiles obtained by inverting the trade-off function (naive) and by Theorem 2.T (refined). Right: Comparison I-GDP and 2-GDP privacy profiles against those for three examples.
different values of μa and c. This is clear from the Figure 1 near 0, 6, is concave for 4 but convex for μ As further complication, both the first and second terms the definition of 8 converge to of two nearby numbers may cause phenomenon called catastrophic cancellation and lead to very bad approximations [26] [... 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 difficult to tightly bound oμ by function with simple form.
oc, but the difference between them vanishes. Subtracting good approximations
To address the problem of differing asymptotic behaviours, we define the following two notions.
Definition 3.1 (Head condition) An algorithm A with the privacy profile 8 is (Ens 11)- GDP if and only if ((() S 5p(() when 6 S Ch-
Definition 3.2 (Tail condition) An algorithm A with the privacy profile 6 is (Et, po-tail GDP if and only if (()) & (c) when 6s.
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 (c, pi)-eaa GDP and (c, ())tail GDP is equivalent μ-GDP. For now, we put the exact value of μ aside and consider only the qualitative question how to identify GDP algorithm by its privacy profile. The following theorem answers this question.
Theorem 3.2 An algorithm A is GDP if and only if A is (e, 1t-tail GDP for any finite and
Interestingly, only the tail condition figures into the identification problem. The reason for this stems from theorem 2.1 Any nontrivial (c. 6D algorithm must be (0, 8DP for some 8 < 1 and therefore must satisty head condition for some sufficiently large μ. The only problem left the tail. However, it is not possible to check whether d(e) < 6,((c for all values of c. To circumvent this issue, we present key lemma that underlies much of the theoretical analysis this section and may continue to be useful in future developments.
Lemma 3.1 Define (c(()
pe 2/2
V2nu² where a = + 2. It follows that lim 8.(e)
= 1.
6-0 (c)
Using the key lemma above, a condition for identifying GDP algorithms is simple to formulate: Theorem 3.3 Let He
lim logg An algorithm A with the privacy profile dc(c) is c-++to
μ-GDP if and only 14 4 oo and μ is no smaller than μ4.
Theorems 3.2 and 3.3 give useful criterion characterizing GDP and deepen understanding of GDP. Putting the exact value of µæ aside, GDP algorithm must provide an infinite union of (e, DDD conditions, where 8 must be ( 30. Refer to Appendices B.3 for proofs of Theorems.
5

---

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 e: intuitively, all (et, μu) -taial conditions are weaker than the corresponding ep-DP condition, and the latter provides almost privacy when é, > 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, +00) satis- fying f(0) < The Gaussian differential privacy transformation (GDPT) of f is the function G mapping [0, oo) to [0, o0) such that ( Haw f()). where Paw (I, y) is the implicit function defined by the equation (x) y.
We highlight two critical features the GDPT.
The GDPT is order preserving: if [(( 2 g(t), then Gy(e) 2 GG(e).
TThe GDPT of oμ Gs, (c) = μ. a constant function.
The first of these two features derive from the monotonicity of (c). Given a fixed (e) is a strictly decreasing continuous function of Given fixed 6, 5p (c) is strictly increasing continuous function of μ.. Therefore, Paur (z. y) is an increasing function of y: this leads to the order-preserving property. The second property follows immediately from the definition of Pare
property, direct comparisons between 6, and Đ 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 to the constant function μ. The following theorems formalize this insight.
By taking advantage of the order-preservvie
Corollary 4.1 An algorithm A with the privacy profile A is y-GDP and only if sup((GA(e) E [0, o))
Theorem 4.1 An algorithm A with the privacy profile 8 is (Ehs p)-head GDP or (Ee, p)-tail GDP if and only if 2 sup((GA(e) e [0, exl) or 2 sup([G e (E2,00) respectively.
Without the above results, we would be forced to search through large family of functions for single 5n that never crosses Å anywhere [0, oo) and has p. as small as possible. Now, with Theorem
4.1 we need only consider one function: the GDPT of 6 The tightest value is sup, s (G))
Now we revisit our previous three examples for which the limit in Theorem 3.3 is O. 1/2,, and +oc, 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 GDGDP curve regardless of how large μ is, indicating that the ICEA algorithm is not GDP.
eg id aas)
2.0
- 62 i) -.5)
1.
62
15
07
1.4
12
6DR 1)
ICEA
SED
0.0
Figure 2: Left: Examples of GDPTs. Right: Plot of G and G with different values of d.

---

Left side of figure 2 shows the GDPT's of the three examples considered in this paper. All three GDPTs converge to a finite value as 0 This can be attributed the fact that any algorithm providing some non-trivial (e, 8)-DP guarantee is (0, 6D for some å E [o, 1) (by theorem 2.1 For larger values of e, 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, 11/2, and oo obtained from Theorem 3.3 Once an algorithm is confirmed to be GDP via Theorems 3.2 and 3.3 is natural to be interested in the exact level of privacy protection, quantified by μ.. Nonetheless, plots only good for visualization and are not sufficient proof when verifying GDP. We still need objective and tractable methods for obtaining bounds on GDPTs.
shows
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 μ such that A is (e, phedd GDP. Without additional knowledge, finding sup[G e [0, e,]). even for finite Eh, seems computationally infeasible. To solve this problem, we take advantage of the fact that Peor has uniformly bounded partial derivative.
Opapp (c,8)
Theorem 4.2 0
<
de
The first half of the inequality above is no surprise to us: the GDP privacy measurement is expected be larger when larger. However, the second half allow only conduct the search finite list of e without the concern of spikes in between. We formulate this insight as the following theorem:
Theorem 4.3 Given En 0, let d = en/n and x, = id for tO...., + 1}. For S ch. the GDPT of A, denoted by GAlc), is bounded between the two staircase functions
a+1 Σ
n+1
()
Hew (2, 8x(x++1)) (ee and Gt(()=
Σ
Poan (4(21))((())) Leffsr &eelvi) 1)-
Specifically,
max (7(2)) S max GA(c) :E(O....))
max
Gt(z;)) S max G7(x)) + 22rd.
(2)
iE (0]
c (0....))
Refer to Appendix B.5 and B.6 for proofs of Theorem 4.2 and respectively.
For any c < +0c, we can now bound any GDPT G to any precision on [0, without full pointwise evaluation because GA is bounded between G and G and each staircase function takes on only finitely many values. For any > the inequalities in (2) provide a viable way to bound max.e[o.ea] GA(E) in an interval with length no greater than 1/c.
First, a binary search algorithm (algorithm in Appendix D can yield ju+ and μr" such that a S Peor d) S ju and μ= μ < b. For future references, we use th (e, 0, b) and p (e, b) represent such outputs of f+ and µ respectively. Therefore, (a.) and G (2:)) By picking = [VVTTC]]]]]] and max G (c) is less than ze and the error margin of the binary search estimate the Pen is also 1. Therefore, the overall gap is bounded by 1. As for complexity, each binary search has a time Ze
naively go thorough all and 2c the true gap between max (c)
complexity of (log(c)) and the number of binary searches is 2n + 2 O(E,C). The overall time complexity of this naive approach O(c,clog(c)) ). For complete pseudocode of this naive approach, refer to algorithm B in Appendix
By leveraging some properties of Peor and shuffling, the expected number of binary searches needed can be reduced from linear (2n + 2 (FA) to logarithmic (O(log(cx))) Such reduction will eliminate the logarithmic term the time complexity from the naive algorithm. The improved algorithm is given as Algorithm 1 below.
7

---

Algorithm I: Finding y with privacy profiles (optimized).
Input: A,, Ehe He, c, (Privacy profile, searching range E/, reciprocal of error margin)
VSCTEN|
d 5h
μ- +
44 t 0
$= . +1
Shuffle
for 0 to n do
J <- Slild
xt - (S|i] 1)d
it | (x)) < (a(xt) then
n² + M (x (x(x)), )
end
if ppp (at) < (x(x)) then
" t- Me (x _d(xx)); )
end if end for Output:μ--, M4 (lower and upper bound of μ4).
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 Appendix D for detailed explanation of this algorithm.
4.2 Understanding the tail
With Theorem 4.3 one can verify (E,,,) -hedd GDP conditions for arbitrarily large en and an μ.. While the error μ can be quantified by D, one gap remains: éi, can be arbitrarily large but can never truly be +oc. In this subsection, we discuss the gap between (cn, heed GDP and actual GDP (which is equivalent to (+o0, phehe GDP). Before giving a solution, intuitively illustrate the gap between (en, pc-head GDP and actual GDP. Consider the following two cases:
arbitrarily precise approximation
GDP with catastrophic failure, where with probability 1 - Ai functions properly as H-GDP, with probability p. Ar malfunctions and discloses the entire dataset; and
head-GDP with e-DP, where A is both (Ek. head GDP and (eh. D)-
The head GDP privacy guarantee lies strictly between those of Ar and Ag: specifically, S (e) < 5(e) < (e). As an interpretation of this inequality, 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 e-DP condition, the head GDP will be stronger than the actual GDP. In practice, is rarely above six in GDP, and é is rarely above in cDD because more extreme values provide almost no privacy protection [3] If we verify the head condition up c, 100 (which is not difficult because the time required for verification grows linearly) and take = 6, then = 6y (cn) will be on the order of 10 10-43, Also, DP guarantee for this large is rarely considered to provide real protection. Hence, we conclude that the gap will not make any notable difference in practice with proper choice of μ and C₁-
4.3 Amplification
In some cases, one may wish to thcoretically mend the gap discussed in the last subsection. This can be achieved by adding extra steps perturb the output of the algorithm (i.e., via post-pron post-processing). We propose the following "clip and rectify" procedure that can turn any (Ch, phed GDP algorithm into a GDG algorithm some utility cost.

---

Theorem 4,4 Let A be an (eh. 1h)-had GDP algorithm with a numeric outpur. Assume that -oo < y < y² <000 Define C(y) max(min(y, y ). and R(2) + U, where v sampled from Laplace(b) (b) with b = (y+ y / Then R o C o A is μ-GDP.
Refer to Appendix [3.7 for a proof of Theorem 4.4 We remark that, in order to minimize the utility loss, the bounds y and yt should be properly or dynamically chosen and the head condition should be verified to a value of 6n that is as large as possible.
On the other hand, the performance (μ) 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 [3]. The resulting privacy profile explicitly given in Theorems 8-10 of 33. With the help of the GDPT, we can select different subsample ratios and measure For instance, the Laplace example in this paper was originally 1.80-GDP. If we introduce 50%- or 10%- Poisson subsampling before the Laplace mechanism, j will be reduced to 0.98 or 0.28, respectively. Refer to E.2 for complete graph of the new GDPTs.
While one could turn other algorithms design 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 casily accessible. In other cases, the DP mechanism might be inaccessible. This is particularly common for users of proprictary 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 c-DP and the Laplace mechanism
By our previous analysis of the GDPT, we know that being GDP means that privacy profile has a quickly vanishing tail (i.e., 8(e) must be O(e-r)). family of DP conditions, the e-DP conditions, is also property that pertains to the tail of privacy profiles. For any DD algorithm, the privacy profile must be exactly 0 after Eg. This suggests that e-DP is stronger than GDP. Next, we will quantify this intuition using the tools we developed above.
remarkable that another single parameter
By Theorem 2.1 we know if is DD- then in the worst case, dc(c) = (e - e5)+/(1= + c*)).
We consider the GDPT of 8,A, denoted by GA. It is easy to see that, for e 2 co. (A = O: we need only consider e E (o)) Let Gāλ(e) be denoted by pa- Using the partial derivative of G. derived in Φ }
Appendix B.5 we know that de Gr = V2T exp (12 + 2c)² /(8u2)
2²+20 2pc
Then sign( de Goa(t)) = =iinn) - P40 2e/Ho). We can conclude that μe S Ho and, further, that Ga(ee) is strictly decreasing on [0, e0). By Theorem 4.1 we know that A is μo GDDP This finding
can be more generally formulated as the following theorem.
Theorem 5.1 Any (e, algorithm is also μ-GDP for p= 22 1eaa-1(1/)) -11(1+)))) VT
13 pointed out that the DP guarantees of the Laplace mechanism are stronger than those correspond- ingly provided by e-DP. We reaffirm this difference by showing that it still exists under the GDP framework. The Laplace mechanism satisfies G-GD for j smaller than the bound given in Theorem The GDPTs presented in Appendix E. illustrate this difference.
5.1
5.2
Handling composition with GDP
In practice, is rare for dataset 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 privacy parameter for the ensemble. However, not only is exact composition an intrinsically (#P-)hard problem (29, but the conclusions of composition theorems are also often problematic. Take traditional (e, 5)D as example. [24] gives an optimal
composition theorem, but the composition of two (c. 8)- algorithms cannot be characterized under the (e, d)DP framework. This result damages interpretability because the representation of

---

8
10-1
10-2
10-3
10-4
Method
Adaatoed
Basic
9.89
9.99
10
10
CDP Narfeeel
Advanced
5.25
6.51
7.47
8.28
04.
Optinal
RDP
12.14
17.17
21.03
24.28
07
GDP
3.1
5.06
6.47
7.62
GDP (Lap)
2.87
4.74
6.09
7.19
60
Optimal
2.12
3.64
4.76
5.28
GDP summary
2.14
3.73
4.87
5.80
Figure 3: The plot of privacy guarantee under different methods.
Table 1: Minimum values of to achieve correspond- ing (c, D).
composition will no longer be in two parameters. This type of flaw is the major motivation for GDP characterization of algorithms derived under other DP frameworks. The composition of GDP algorithms is easy, exact, and closed: the composition of a μ11 and H2-GDP algorithm is simply VII + + -DP. GDP also has special central limit theorem which implies that, for all privacy definitions that retain hypothesis testing with proper scaling, the privacy guarantee of composition converges to GDP in the limit. In this subsection, we demonstrate that GDP is 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 [14, advanced composition [15] and Rényi-DP 28)..
We consider the 50-fold composition of 0.2-DP algorithms. In this setting, the basic composition pessimistic and says that the composition will be 10-DP, which means there next to no privacy guarantee. According to corollary of (28] the bound given by RDP is even looser. Refer to Figure for the results of other theorems.
We next consider composition using the proposed measurement method. According to Theorem 5.1 0.2-DP algorithm D.2505-GDP. If the algorithm is the Laplace mechanism, then the algorithm in Appendix D can tighten μ to 0.2391. To compute for a 50-fold composition, we simply multiply the original by /50. The result is 1.771-GDP (1 (1.691 for the Laplace mechanism). In neighbouring datasets is hard distinguishing between N(0, 1) and (1.771, 1) on the basis of a single observation.
this case, distinguishing
In this particular case, the ground truth can be derived from the optimal composition theorem 24 We present the results from the optimal composition theorem in Table 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 (c, 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 [3] which yields = /2 (with an unknown asymptotic approximation error) in the same setting, the tractable numerical procedure of GDPT provides 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.
10

---

References
[1] Martin Abadi, Andy Chu, lan 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 subsam- pling. 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 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 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: Effi- cient 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. Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, pages 74 14-86,,22 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 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-33 -200009--202220 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! 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- prevevypres ordinal response. 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. IEBE, 2018
[18] Marco Gaboardi, Hyun Lim, Ryan Rogers, and Salil Vadhan. Differentially private chi-squared hypothesis testing: Goodness of fit and independence testing. International Conference on Machine Learning, pages 2111-2120. PMLR, 2016.
11

---

[19] Badih Ghazi, Pasin Manurangsi, Rasmus Pagh, and Ameya Velingker. Private aggregation from fewer anonymous messages. Advances Pryptoloyy-EUROCHHE 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:/906. 08320, 2019.
[21] Muneeb U1 Hassan, Mubashir Husain Rehmani, and Jinjun Chen. Differential privacy techniques for cyber physical systems: 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: 1rXiv:190.007735, 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 Moating-poing summation. Communications of the ACM, 14(11):731-76, 1971.
[27] Arthur R Miller. Personal privacy in the computer age: The challenge of a new technology in an intommation-oriendee society. Michigan Law Review, 67(6): 1969.
[28] lyaa Mironov. Rényi differential privacy. In 2017 IEEE 30th Computer Security Foundations Symposium (CSF), pages 263-275. IEBE, 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-anonnymzzaton of large sparse datasets. In 2008 IEEE Symposium 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 20/7 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 8681. PMLR, 18 Jul 2021.
[34] Edward Shils. Privacy: Its constitution and vicissitudes. Law and Contemporary Problems, (1)2)281-3366 1966.
[35] Larry Wasserman and Shuheng Zhou. A statistical framework for differential privacy. Journal of the American Statistical Association, 105(489) 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.
12

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] The limitations are given as
conditions of theorems and properties.
(c) Did you discuss any potential negative societal impacts of your work? [N/A] This work is development of mathematical tools for the DP framework and does not have immediate real-world impact.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes] The complete proofs are provided the appendix.
3. If you experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental 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 main results are supported by proofs.
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [N/A]
(c) Did you report error bars (c.g., with respect to the random seed after running experi- ments multiple times)? [N/A] There is randomness involved.
(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 negligible.
4. If you using existing assets (e.g., code, data, models) curating/releasing assets...
(a) If your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material as URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [N/A] No such data used.
(c) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A] No such data used.
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A] No human subjects involved.
(b) Did you describe any potential participant risks, with links Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
13


Reviews:
[{"review_id": "pqdhTigdHld", "reviewer": "Reviewer_vcSa", "summary": "The authors in this paper extend the study of Gaussian differential privacy, an intuitive, single parameter privacy guarantee that exactly captures the privacy of the Gaussian mechanism. The authors introduce head and tail GDP, and provide conditions under which algorithms with given privacy curves/profiles satisfy these modes of GDP. The authors then show that algorithms, such as the Laplace mechanism, that satisfy pure DP also satisfy Gaussian DP. They demonstrate computationally that, by casting these algorithms under GDP, one can obtain tighter composition results than basic or advanced composition would permit.", "questions": "Nothing additional.", "limitations": "The authors say that the limitations are given as preconditions of theorems. It would helpful to the reader to also have the limitations separately addressed in conclusion, for instance, as this could motivate future work. For instance, one limitation is that the conversion to GDP is inherently lossy, and thus for many composition problems Fourier-based accounts can actually outperform the results in this paper, approximating the true privacy profile/curve to arbitrary precision. ", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths: Gaussian differential privacy is a simple and important concept for characterizing private algorithms. The authors demonstrate that, by furthering the study of GDP, one can obtain improved composition results for commonly used private algorithms. The authors also give computational techniques for characterizing the head GDP of algorithms, making the work practical. The work is original as it is the first to cast purely differentially private algorithms as GDP algorithms --- an approach that yields tighter composition results.\n\nWeaknesses: Many of the algorithms considered in this work can have their exact privacy curve efficiently approximated using Fourier-based methods. While the results surrounding GDP offer improvements over baselines such as advanced composition, converting pure DP to GDP is still lossy. Since the paper contains many technical results, it may also be helpful to either provide sketches or explain intuitions to the reader.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "mQ-Kl-KA0nC", "reviewer": "Reviewer_ipZH", "summary": "This work shows the relationship between the common DP and GDP metric in privacy. GDP's good interpretability makes it clear than traditional DP with privacy profiles. The work follows the equivalence of GDP and DP with function $\\delta_{\\epsilon}$ and specifies the function characteristics to bridge DP and GDP. Besides the identification of DP to GDP, a  GDPT method is proposed to clearly show the relationship between DP and GDP in combination with head and tail analysis. The GDPT can also be that can be easily estimated supported by the theoretical analysis in the work. Finally, the authors show some applications in privacy compositions with the understanding of the GDP and DP.", "questions": "Some questions:\n1. How is the cost/utility of GDP compared with other mechanisms? Some theoretical/magnitude results can be provided if possible.\n2. Can GDPT help us design a new privacy mechanism with lower cost/ utility?\n3. For the other algorithm with the privacy profile tail larger than $e^{-\\delta^2}$, can we measure it with GDP approximately?\n4. How is the proposed framework related to the privacy loss random variable? According to GDPT, $\\mu$ gives a uniform description for the structure of the output's measurable space. The distribution/ the moments of privacy loss random variable might provide the detailed description, which may help the specification of the tail of GDPT. \n5. Can Theorem 2.1 be stronger in dependence on actual algorithms? It may make the following analysis more concise.\n6. In Theorem 4.3, is $x_i\\in[0,\\epsilon_h]$ or not?\n\nSome suggestions:\n1. Some detailed settings for the experiments should be shown. (Like dataset,or other settings)\n2. It is better to restate the subsampling process to make it friendly to readers.\n3. Some intuitive examples/ figures can be provided to show the tail larger than $e^{-\\delta^2}$ can not be $\\mu-$GDP.", "limitations": "The authors should mention some limitations for heavy tails and head $\\epsilon_h$ choices in the main context more clearly.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Pros:\n1. The work gives a powerful tool to bridge GDP and DP. It clearly reveals the relationship and provides a better understanding of GDP, which can make traditional DP more interpretable through GDP.\n2. The good organization of the paper makes the readers easy to understand the proposed structure and corollaries.\n\nCons:\n1. The practical application of DP to GDP is not clear. Can the proposed mechanisms help us to design a better privacy mechanism? Or how to quantify the interpretability?  How to show more effectiveness for GDP compared with DP?\n2. The technical challenges/novelty should be stated clearly. The work is based on Theorem 3.1 a lot but the it is from [Dong et al. 2021].\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ["I don’t know"]}, "extra_text": {}}, {"review_id": "EBOlptCm4Av", "reviewer": "Reviewer_cu8x", "summary": "The paper studies the asymptotic properties of privacy profiles and propose an efficient method for GDP algorithms to reduce the set of possible optimal privacy measurement. As an application to the main result, all pure-DP algorithms are also GDP.", "questions": "N/AN/", "limitations": "N/A", "rating": 6, "confidence": 2, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Disclaimer: I was unable to read through the proof, but the results seems plausible. My comments are based on first 9 pages.\n\nStrengths:\n-- The paper presents analytic methods to deal with Gaussian DP, the one parameter privacy definition that captures entirety of approx-DP.\n-- Gives an algorithm to find \\mu with privacy profiles.\n\n\nWeakness:\n-- I found motivation of the paper and results a little bit difficult to understand. \n-- There are couple of places where it is mentioned: nontrivial (\\eps,\\delta)-DP algorithm must be (0,\\delta)-DP for some \\delta <1. I really do not get this statement. Why is this true? \n-- Which key lemma are the authors referring to on line 194.\n-- I would suggest having the algorithm for finding \\mu in the main 9 pages. It is very interesting algorithm.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "BmVh3zs9iQ", "reviewer": "Reviewer_GwbN", "summary": "Gaussian DP is known as an exact privacy accountant with hypothesis-testing-based interpretation.\nThe paper studies a significant problem --- converting algorithms developed under other DP accountants into the GDP framework.\nSpecifically, \n1. The authors study the connection between GDP and the privacy profile, and use the asymptotic properties of privacy profiles to identify the GDP property.\n\n2. For non-GDP algorithms, the authors propose the ``clip and rectify'' procedure to convert these algorithms into a mu-GDP algorithm. ", "questions": "Theorem3.3 is about the asymptotic property. It only provides a lower bound of GDP, but the derived GDP may not be as tight as the original privacy profile. It would be more interesting if the authors could plot both the original privacy profile and the converted GDP in a trade-off figure and compare the two curves.", "limitations": "Yes, they have addressed it.", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Limitations: Though the conversion to GDP is solid, \nthe paper lacks empirical comparison or theoretical evidence to demonstrate that such conversion is tight. Other DP accountants might provide tighter privacy characterization if the conversion is loose.\n\n\nComments:\n\n1. ``we show that all epsilon-DP algorithms are also GDP'' might be overclaimed. [13] has shown that the trade-off function of epsilon-DP will be lower bounded by the randomized response mechanism, which satisfies GDP. \n\n2. The section 5.2 (handling composition with GDP) is not the contribution of this paper. It will be better to move it to the preliminary/related work section. \n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ["I don’t know"]}, "extra_text": {}}]

Author rebuttal:

Decision: Accept