Gaussian Differential Privacy Transformation: from identification to application
Authors: Yi Liu
Ke Sun
Bei Jiang
Linglong Kong
Venue: ICLR 2022 Submitted (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 individuals from machine learning models. Relative to traditional $(\epsilon,\delta)$-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 $(\epsilon,\delta)$-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 $\mu$ with an arbitrarily small and quantifiable margin of error. As applications of our newly developed tools, we revisit some established \ed-DP algorithms and find that their utility can be improved. We additionally make a comparison between two single-parameter families of privacy notions, $\epsilon$-DP and $\mu$-GDP. Lastly, we use the GDPT to examine the effect of subsampling under the GDP framework.

Under review as a conference paper at ICLR 2022
GAUSSIAN DIFFERENTIAL PRIVACY TRANSFORMA- TION: FROM IDENTIFICATION TO APPLICATION
Anonymous authors Paper under double-blind review
ABSTRACT
Gaussian differential privacy (GDP) a single-parameter family of privacy no- tions that provides coherent guarantees avoid the exposure of individuals from machine learning models. Relative to traditional (c, ( diffffeeret privacy (DP), GDP is more interpretable and tightens the bounds given by standard DP composi- tion theorems. In this paper, we start with an exact privacy profile characterization of (e, 8)DDP and then define efficient, tractable, and visualizable tool, called the Gaussian differential privacy transformation (GDPT). With theoretical property of the GDPT, develop an easy-to-verilyy criterion 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 j with an arbitrarily small and quantifiable margin of error. As applications of our newly developed tools, we revisit some established (c, 6DP algorithms and find that their utility can be improved. We additionally make comparison between two single-parann parameer families of privacy notions, DP and j--DP. Lastly, we use the GDPT to examine the effect of subsampling under the GDP framework.
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 indi- vidual 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). concept of privacy 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 ag- gregated 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. Zelelr
2006).
Differential privacy (DP) first gained traction 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 dataset under an alteration of one data point. The following definition formalizes this notion.
Dwork et al. 2006) A randomized algorithm A. taking dataset consisting of indi- viduals as its imput, is (c, (c,0) diifferrntyal private if. for any pair of datasets S and S' that differ in the record of single individual and any event E,
Definition 1.1
P\A(S) E E] < P(A((S) E
When A is called e-differentially private (e-DP).
While the notion of (c. DD has wide applications DDankar & El Emam 2012 Erlingsson al. 2014 Cormode et al.) 2018 Hassan et al.) 2019). there are few notable drawbacks to this frame- work. One is the poor interpretability of 8D- unlike other concepts in machine learning, DP

---

Under review as a conference paper at ICLR 2022
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 (c. 8) -)'s inferior composition properties and lack of versatility. Here, "composition" refers 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 differeettalll--priate versions of these components. However, the DP composition properties cannot generally be well characterized within the framework of (c, 8D-,, leading to very loose composition theorems.
To overcome the drawbacks of (e, 8D-D, numerous variants have been developed, including the hypothesis- -estine--aineeeeee f-DP (Wasserman & Zhoo 2010: Dong et al. 2019), the moments- accountant- becoedtant-based Rényi DP (Mironov] 2017). as well as concentrated DPP and its variants (Bun) & Steinke, 2016, [unn et al. 2018). Despite their very different perspectives, all of these DP vari- ants can be fully characterized by an infinite union of (e, 6)-DP guarantees. In particular, there is a two-way embedding between f-DP and the infinite union of Ō)-P) guarantees: any guarantee provided by infinite union of (c, 5D-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 prpthesiistestingg 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 A 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 AA: this means the attacker must select a subset Rg of (ango(A) and reject Hg if the sampled output is in Ry (or must otherwise reject H)). The attacker is more likely to incorrectly reject Hg (in type error) when Ro is large. Conversely, if Ro is small, the attacker is more likely to incorrectly reject H1 (in a type Il error). We say that an algorithm A is f-DP if, for any a E [0, 1]. no attacker can simultaneously bound the probability of type I error below a and bound the probability of type II error below f (a). 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, is not convenient for repre- senting 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 single value μu and use the trade-off function f(a) = 2 (11 - a)- -n), where & is the cumulative distribution function of the standard nor- mal distribution. With this choice of f. the hypothesis- hard as distinguishing between (O, 1) and N(u, 1) on the basis of a single observation. Aside from its visual interpretation, GDP also has unique composition theorems: the composition of /i- and Ha-GDP algorithm is, as expected, Vu² + H2-GDP. This property can be easily gener- alized to n--old composition. GDP also has has a special central limit theorem implying that all prpothesi-teesing-baaee based definitions of privacy converge GDP in terms of a limit in the number of compositions. Readers are referred to Dong et al. (2019) for more information.
problem faced by the attacker is as
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 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 (e,5 framework, this trade-off is often characterized in form of a = f(e, 6): to achieve (c, ODDP, the utility parameter (usually the scale of noise) needs to be chosen as f(e, 8). We will further discuss this formulation with examples in the next section.
1.1 OUR CONTRIBUTION
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
2

---

Under review as a conference paper at ICLR 2022
under the condition of traditional (c, 6),P, where point out offen-overlooked partial order on (c. 6)-PP 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 jr. 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 j with 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 (e, 8) algorithms and improve their utility by accounting for the overlooked partial order on (e, -DP conditions provided by logical implication. In the second application, we make a comparison between e-DP and μ-GDP and find that any e-DP algorithm must be also μ--DP. In the last application, we discuss the effect subsampling using the GDPT.
BACKGROUND
An algorithm can be 6c for multiple pairs of and ō: the union of all such pairs provides complete image of the algorithm under the 5)PP) framework. In particular, an (c. 6)DD mecha- nism A is also (c', DDD for any c' 2 c and any 5' 2 5. The infinite union of (c, pairs thus be represented as the smallest ó associated with each e. This intuition is formulated as privacy profile in Balle & Wang 2018). The privacy profile corresponding to a collection of (e, 6DD guarantees Z is defined as the curve in [0, oo) x [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 Q itself. Many privacy guarantees and privacy notions, including (c, 6)DDP, Rényí 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 derived by algorithm's '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 diseussed 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 global sensitivity A, the value of needs to be chosen as f(c 0) = A/c in order to provide an (c, O)-DP guarantee. Despite its long history, the Laplace mechanism has remained in use and study in recent years (Phan al.,
2017 Hu et al. 2019 Xu et al. 2020 Li & Clifton| 2021).
Our second example is family of algorithms in which noise parameter has the form Ae / log(BB8) 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 QQia 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 8c,8)-DP if m > 10 log(n/ (c6)) (Ghazi et al. 2019). See also (Balle et al. 2020bb Ghazi et al. 2020) for other analysis of ICEA.
For figures and numerical demonstrations in this paper, we use = 2/A for the Laplace mechanism;
A = 2, B = 1, and for the second example, which refer to as SGD; and m 20 and
3

---

Under review as a conference paper at ICLR 2022
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), given in the form of a privacy-utility trade-off equation a, it is tempting to derive the privacy profile by inverting the trade-off equation (i.e., as (c(e) = min
privacy guarantees
f(e, d). Given
f(e, f(e,d))) However, in most cases, privacy profile naively derived in this way is not tight and will lead to problematic asymptotic analysis, especially near the origin, because of a frequently overlooked partial order between (e, dDD conditions, which we discuss below.
PRIVACY PROFILES AND AN EXACT PARTIAL ORDER ON 6)-P CONDITIONS
An (Eo, do) DDP algorithm is trivially (c. 6)-DP for any E 2 6o and 8 2 60. However, this statement does not give a full picture of the relationships between different (c, 6)-DP conditions.
Theorem 3.1 Assume that 2 0 and 0 S 60 <1 1. The (co, 5D) condition implies (c,5)-DP if and only 6 z 60 + (1 (e - - /(1 + e²
Corollary 3.1 Assume that z eo and d s [(1 + E00 e- + +e00/((1+ +ee)). An (e, 8)DP algorithm is (ca, 6o)
Corollary 3.2 Let be an (co. -DP algorithm with the privacy profile d Then
(c(c) v 5n + - 50) -0) -5)
1 650
We remark that the bound given in 4 tight in the following sense: there a specific (co, DDP algorithm A such that (e((e) is exactly 8n
50) - ee) /(1 + c
states the exact partial order of logical implication on (e, 6)DD conditions. Taking this partial order into account, the privacy profile derived from the naive inversion of the trade-off function can be refined into
Corollary 3.1
(c(c) = min ((810= f(eo, ((elo=((eobb) 50) and 2 60 -8)0 - 1))
1 1 1te5 e0
Intuitively, the refined privacy profile not only considers (e, 6)-DP provided directly by the trade-off
function but also takes all pairs (c, inferred by Corollary 3.1 Theorem 3.2 can itself be used a tool to improve some DP results: approach, we can derive the privacy profile of our second example to be dSGD(E) min(52 + (1 (e - e + e²²), exp(-e²)), where 62 1.187 and 82 Rs 0.244. The privacy profile of our third example is (c) = min(d3 + (1 11-6yy (e + +1111100 t K/e}), where K = 4/e², <3 1.159, and d3 0.468. Notice that dsGD and ÒICEA share a similar form: both are the smaller of two terms, one derived from Corollary 3.1 from a particular (e, DDP pair and the other from inverting the trade-off function. This no coincidence. We leave the derivation to Appendix B
will discuss this improvement in Section 5 With this
We next show the connection between GDP and the privacy profile: briefly, Gaussian differential privacy can be characterized as an infinite union of (e, DP conditions.
Theorem 3.2 A mechanism H-GDP if and only if it (e, (p(5)) for all 2 0, where
(e( +
E
2 - e e
E
This result follows from properties of f-DP and is formulated Corollary 2.13 in Dong et al. (019)) 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 algorithm A with the privacy profile 5 is μ-GDP if and only if (c) 2 (c(c) for all non-negative c. However, this observation does not automatically lead meaningful way to identify μ-GDP algorithms.
Before proceeding with an analysis of privacy profiles, we give a few visual examples Figure The left pane illustrates the privacy profiles of our examples. That of the Laplace mechanism
4

---

Under review as a conference paper at ICLR 2022
is derived in [allee al. (2020a) as Theorem 3: given noise parameter b and global sensitivity A, the privacy profile the Laplace mechanism is ō(c) = max - exp(=/2- (2b2)), 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, 8) cannot be achieved by any choice of parameter a. However, this is clearly not true, considering Theorem 3.1
As shown in the right pane of Figure the Laplace mechanism's 's privacy profile is below the 2-GDP and 4-GDP curves but crosses the I-GDP curve, indicating that the Laplace mechanism in this case 2-GDP and 4-GDP but not I-GDP. The ICEA curve intersects all of the displayed GDP curves, so the algorithm is not GDGDP for E {1,2, 4}. It is hard to tell whether or not the SGD curve crosses the 1-GDP curve and we cannot say if will cross the 2-GDP or even the 4-GDP curve at large value of 6. These examples illustrate that we cannot draw conclusions simply by looking at graph. A privacy profile is defined on [0, 00), so it is hard tell if an inequality maintained as e increases. Previous failures of ad hoc attempts at privacy have taught that privacy must be protected via tractable and objective means (Naaayanan & Shmatikov 2006 2008 Barbaro & T. Zeller 2006).
10-
KZA
0.8
KCEA Acteed
0.6
Refree
Laphoe
CDP
0.1
(DPg)
02-
0.2
00
2.0
0.3
1.
2.5
Figure 1: (Left) Examples of privacy profiles obtained by inverting the trade-off function (naive) and by Theorem 3.1 (refined). (Right) Comparison of 1-GDP and 2-GDP privacy profiles against those for our three examples.
Performing this check via numerical evaluation yields similar problems: cannot consider all values of e on an infinite interval (or even a finite one, for that matter). Turning to closed forms for privacy profiles and 6, is also difficult: even if given privacy profile is easy to handle, 6p presents some technical hurdles. The profile 6μ and d are transcendental with different asymptotic behaviors for different values of μ and e. This is clear from the right pane of Figure T near e O, 5n is concave for μ 4 but convex for μ = 1. As further complication, both the first and second terms in the definition of 6, converge 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 good approximation the GDP privacy profile. These problems make it difficult to tightly bound 8, by function with simple form.
as c >> 00, but the difference between them
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 (En, peehead GDP if and only A S 6y(E) when e S. Eh-
Definition 3.2 (Tail condition) An algorithm A with the privacy profile 5 is (cr,p))tal GDP if
and only if (c) I 5,(c) when c.. In particular, define A as (+oc, ())pi)ttiil GDP if A is (Ee, (1) tail GDP for some &, < +00 and define A as (c,, -ta)- GDP if A (Gt, p)) for some J 400.
5

---

Under review as a conference paper at ICLR 2022
The head condition checks the j-GDP condition for near and the tail condition checks the jı- GDP condition for far away from zero. As such, the combination of (e, (4) GDP and (c, pt)-tail GDP is equivalent to f-GDP.
THE GAUSSIAN DIFFERENTIAL PRIVACY TRANSFORMATION
In this section, we propose
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 μ.
Definition 4.1 (GDPT) Let f be non-increasing non-negative function defined on [0, +0o) satis- fying f(0) - 1. The Gaussian differential privacy transformation (GDPT) of f is the function G mapping [0, 00) to [0, 20) such that G How (c, f()), where Pow (I. V) the implicit function defined by the equation (x) y-
We highlight two critical features of the GDPT.
The GDPT is order preserving: if f(e) 2 g(e), then Gy(e) 2 Gg(e).
The GDPT 6, Gs,, (c) = 14, a constant function.
The first of these two features derives from the monotonicity of (e). Given a fixed μa, 6x(e) is a strictly decreasing continuous function of Given fixed c, (c) is strietly increasing continuous function of μs. Therefore, Pear (z. y) is an increasing function of y: this leads to the order- prder-preserving property. The second property follows immediately from the definition of Pawe
By taking advantage of the order- preserving property, direct comparisons between 6, and ò are longer necessary: instead, it is sufficient to compare their corresponding GDPTs. Furthermore, appealing to the second property above, we need only compare Ga to the constant function μ. The following theorems formalize this insight.
Theorem 4.1 An algorithum A with the privacy profile 8 is (Ch, heed GDP if and only if μ Z sup({Ga, (c) c e (x).
Theorem 4.2 An algorithm A with the privacy profile A is (Ee, p)-tail GDP if and only if 2 sup([Gs, (e) E (4,,0)) oo)).
Corollary 4.1 An algorithm A with the privacy profile 5 is μ-GDP if and only if p 2 sup((Ga_ (o)).)
Without the above results, we would be forced to search through an uncountably-large family of functions for single 5, that never crosses 8 anywhere on [0, oo) and has f as small as possible. Now, with Theorem 4.1 we need only consider one function: the GDPT of 6 The tightest value μ is sup, (c)).
Using the GDPT framework, condition for identifying GDP algorithms (that does not specify the exact value of μ) is simple formulate. We do in the following theorems.
Theorem 4.3 An algorithm A is GDP if and only if A is (+o0, +oo)- GDP.
Theorem 4.4 Let f. be non-increasinn, non-negative function defined [0, +00) satisfying ((0) & 1. Then
2²
lim Gy(c)= to
Tim c -2 log f(c)
V
Theorems 4.3 and 4.4 give a useful criterion characterizing GDP and deepen our understanding of
GDP. Putting the exact value of μ aside, GDP algorithm must provide an infinite union (e, 8DP conditions, where must be ((e -(") as e - co. Refer to Appendices A.3 and A.4 for proofs of Theorems 4.3 and 4.4 respectively.

---

Under review as a conference paper at ICLR 2022
Using these newly-developed tools, we revisit our previous three examples for which the limit in Theorem is 0, 11/2, and +-0, respectively. From these evaluations, we 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 j is, indicating that the ICEA algorithm is not GDP.
2.2
6g -
2.0
9g 10-00
% (00.)
15-
%. 10-3))
1.4
12-
6DR 10
ICEA
SGD
0.0
Figure 2: (Left) Examples of GDPTs. (Right) Plot of G+ and G with different values of D.
The left pane of Figure 2 shows the GDPTs of the three examples considered in this paper. three GDPT's converge to finite value as - 0+ This can be attributed to the fact that any algorithm providing some non-trivial (e, -DD guarantee (0, dDP for some å [0, 1). For larger values of e, the GDPT of the Laplace mechanism takes SGD converges to a value that is approximately 0.7, and the GDPT the ICEA seems to diverging.
constant value of O, the GDPT of
These observations are consistent with the values of O, /1/2, and oo obtained from Theorem 4.4 Nonetheless, plots are only good for visualization and are sufficient proof when verifying GDP. We still need objective and tractable methods for obtaining bounds on GDPT's
Once 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 (e, hhede GDP.
4.1 MEASURING THE HEAD
Without additional knowledge, finding sup (G)((e) | putationally infeasible as there are uncountably many real numbers in any non-empty interval and it impossible iterate through an infinite set. To solve this problem, take advantage of the fact that Mon has bounded partial derivative.
en]) even for finite ey, seems com-
Theorem 4.5 One of the partial derivatives of Pave uniformly bounded. Specifically, S Op (e.6)
V2n
nn. Theorem 4.6 Given Ch 2 0, let D cn/n and x; = iD + On for i E (O...., n +++1. 1}. The GDPT of A, denoted by G(),), is bounded between the staircase functions
G7, (E)
Mew (2,, (x(4411) 1cg(0.044)
and
G (c)
Σ Poo (#=41,0A(z1)) 1eg(x.0)))
Specifically,
max (E.......))
G5 (xi) S max Ga(e) <
max
G (T:) S
max G7 (x:) + V2 (3)
cE(0.o)
ie te(00....7+1
iE(0....m)

---

Under review as a conference paper at ICLR 2022
Refer to Appendix A.5 and for proofs of Theorem 4.5 and 4.6 respectively.
For any En < +00, we can now bound any GDPT G5 to any precision on [0, e,] without full point- wise evaluation because Ga bounded between G and 3 and each staircase function takes
on only finitely many values. The inequalities in 3 provide a viable way to estimate max Ga (e): бд
max.e m (0......) Gb (I+) and (0...-1 G (x:) can be computed by choosing the maximum value among 2n + 2 evaluations of Morr- For the completeness, we provide a detailed description of an efficient algorithm with a time complexity of O(En/ D - log"(D) log(ex)) in Appendix D
4.2 CUTTING THE TAIL
With Theorem 4.6 one can verify (ch. jhedd GDP conditions for arbitrarily large с₁ and an arbi- trarily precise approximation of jr. While the error in j can be quantified by D, gap remains: en can be arbitrarily large but can never truly be +oc. In this subsection, we discuss the gap be- tween (en. p)-head GDP and true GDP (which equivalent to (+o0, ju)-head GDP). Before giving a solution, we intuitively illustrate the gap between (eh: uh-h GDP and true GDP. Consider the following two cases:
GDP with catastrophic failure, where with probability 1 p. A functions properly and exact Jt-GPP is guaranteed, but with probability p. AA malfunctions and discloses the entire dataset; and
head-GDP with e-DP, where A is both (eh, -hed GDP and (en, 0)-DP.
The μ-GDP privacy guarantee lies strictly between those of A and Ay: specifically, dA, (E) (e(e) (e).
<
In practice, ll is rarely above six in GDP and e is rarely above 10 in e-DP because more-extreme values provide almost no privacy protection (Dong et al. 2019). we verify the head condition up to 100 (which is not difficult because the time required for verification grows linearly) and take μ = 6, then p (e)( will be on the order of 10-13, If en, is increased to 200, then p will be smaller than 10 202 Hence, we conelude that the gap won't make any notable difference in practice with a proper choice of μ and Eh.
However, in some cases, one may still wish fully mend the gap theoretically. This can also be achieved under the GDPT framework. A GDPT is fixed function that inherits smoothness proper- ties from the corresponding privacy profile. The maximum value of GDPT can be analysed using standard functional tools. We give example of such an analysis in Section 5 If the privacy profile not given in a manageable closed form or the analysis infeasible, we provide the following "clip and retify" procedure that can turn any (ea, pheh GDP algorithm into GDGDP one at the cost of some utility.
Theorem 4.7 Let A be a (Eh, head GDP algorithm with a numerical output. Assume that -o y < y+ < +o0. Define C(y) = max (min y ),y²) and R(z) + v, where v is sampled from Laplace(b) with b (y y c/ Then R C GDGPP.
Refer to Appendix A.7 for proof of Theorem 4.7 We remark that, in order minimize the utility loss, the bounds y and y should be properly chosen and the head condition should be verified to an en that is as large as possible.
APPLICATIONS
5.1 GDPT OF cDP ALGORITHMS AND THE LAPLACE MECHANISM
By our previous analysis of the GDPT, we know that being GDP means that privacy profile has quickly vanishing tail (i.e., ō(e) must be O(e-=")). )). It is remarkable that another single parameter family of DP conditions, the c-DP conditions, is also a property that pertains to the tail of privacy profiles. For any c cD algorithm, the privacy profile must be exactly 0 after ég. This suggests that 6 is stronger than GDP. Next, we will quantify this intuition using the tools developed in this paper.
8

---

Under review as a conference paper at ICLR 2022
By Theorem 3.2 we know if A is cu-DP, then in the worst case, da(e) = -e0= t
We consider the GDPT of dλ. denoted by Gsa- It is easy to see that, for e 2 co. Gea(e) 0: we need only consider
[0, Let Gdg(c) be denoted by Me: Us-
ing using the partial derivative of Gb derived in Appendix A.5 we know that à de Goa(1) =
22T exp { (u² + 26)² /(8u²)] [ ( -it2)) B( Then sign( GG)(e) = sign(Me PD
2pe.
2c/Mu): We can conclude that je I Ho and, further, that G (c) strictly decreasing on [0, cu).
By Theorem 4.1 we know that A is No Po-DP. This finding can be more generally formulated as the
following theorem.
Theorem 5.1 Any Oe-D) algorithm is also μ-GDP for μ -2 2 + t)))
Dong et al. (2019) pointed out that the DP guarantees of the Laplace mechanism are stronger than those correspondingly provided by e-DP. We reaffirm this difference by showing that still exists under the GDP framework. The Laplace mechanism satisfies y-GDP for μ smaller than the bound The GDPTs presented Appendix E.1 illustrate this difference.
given in Theorem 5.1
5.2 UTILITY REFINEMENT
There is an interesting byproduct or the privacy profile refinement. Theoretically, the privacy profile refinement can also be used to improve an algorithm's 's utility. For example, the projected noisy SGD algorithm in Feldman et 2018 (c, 5)-DP and the trade-off function is CC log( ( To achieve eD. it appears that needs to be chosen -Clog 3) 10C. By Corol- lary 3.1 (e, DDP implies (0.2, e --DP when + (1 - (e - e
= Numerical methods suggest that, by choosing R 0.334 and ó ~ 0.067, (e, DDP implies (0.2, but -Cloo(6))ee = 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
o =
5.3 EFFECT OF SURSAMPLING
It is well known that a mechanism can be improved from privacy perspective by adding extra steps to perturb its input or output. One popular approach is the subsampling technique (Balle al.) 2020a). We omit the details of this method and use the following result from Balle et al. (2020a).
Let A be an (c. 5)-DP algorithm and S., the Poisson subsampling procedure wherein each data point is retained with probability 7. Then A o S. is (log(1 7 + 78) 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 Peor. the Poisson subsampling procedure can significantly decrease the value of μ around
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
CONCLUSION AND DISCUSSION
In this paper, we provided both an analytical understanding of and engineering tools for the GDP framework. Using the notions we proposed, gave solutions two problems in GDP: iden- tification 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 amplifica- tions by utilizing more advanced composition and proc-psoessiing results. GDPT is generalizable to other parameterized DP notions such as RDP and cDP and enriches the DP literature with its tractability and visualizability.
9

---

Under review as a conference paper at ICLR 2022
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 mathe- matical tools will contribute to the developments of privacy-aware technologies.
Reproducibility Statement. For all our theoretical results, confirm that all necessary assump- tions are properly addressed. and all proofs are provided unless trivial. No datasets and interactive virtual environments involved in this paper. There experimental results in this work. Figures are only for demonstrative reasons as main results are supported by proofs.
REFERENCES
Martin Abadi, Andy Chu, Ian Goodfellow, Brendan McMahan, llya Mironov, Kunal Talwar, and Li Zhang. Deep learning with differential privacy. In Proceedings of the 2016 ACM SIGSAC conference on computer and communications security, pp. 408-318, 2016.
Milton Abramowitz, Irene A Stegun, and Robert H Romer. Handbook of mathematical functions with formulas, graphs, and mathematical tables, 1988.
Borja Balle and Yu- Yu-Xiang Wang. Improving the gaussian mechanism for differential privacy: Ana- lytical calibration and optimal denoising. In International Conference on Machine Learning, pp- 394-403. PMLR, 2018.
Borja Balle, Gilles Barthe, and Marco Gaboardi. Privacy profiles and amplification by subsampling. Journal of Privacy and Confidentialityy 10(1), 2020a.
Borja Balle, James Bell, Adria Gascón, and Kobbi Nissim. Private summation in the multi-message shuffle model. In Proceedings of the 2020 ACM SIGSAC Conference on Computer and Commu- nications Security, pp. 657-676, 2020b.
M. Barbaro and Jr. T. Zeller. A face is exposed for aol searcher no. 4417749, New York Times (Aug, 9, 2006), 2006.
Raef Bassily, Adam Smith, and Abhradeep Thakurta. Private empirical risk minimization: Efficient algorithms and tight eтror bounds. In 2014 IEEE 55th Annual Symposium on Foundations of Computer Science, pp. 464-472 IEEE, 2014.
Mark Bun and Thomas Steinke. Concentrated differential privacy: Simplifications, extensions, and lower bounds. volume 9985, pp. 635-658, 11 2016. ISBN 978-3-662-53640-7, doi: 10.1007/ 978-3-662-536411 24.
Mark Bun, Cynthia Dwork, Guy N Rothblum, and Thomas Steinke. Composable and versatile privacy via truncated edp. Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, pp. 74-86. 2018.
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, pp. 1655-1658, 2018.
Annie Cuyt, Brigitte Verdonk, Stefan Becuwe, and Peter Kuterna. A remarkable example of catas- trophic cancellation unraveled. Computing, 66(3):309-320, 2001.
Fida Kamal Dankar and Khaled El Emam. The application of differential privacy to health data. In Proceedings of the 2012 Joint EDBT/ICTT Workshops. pp. 158 166, 2012.
Jinshuo Dong, Aaron Roth, and Weijie J Su. Gaussian differential privacy. To appear in Journal of the Royal Statistical Society: Series (Statistical Methodology). 2019.
Cynthia Dwork, Krishnaram Kenthapadi, Frank McSherry, Ilya Mironov, and Moni Naor. Our data, ourselves: Privacy via distributed noise generation. In Anmual International Conference on the Theory and Applications of Cryptographic Techniques, pp. 486-503. Springer, 2006.
10

---

Under review as a conference paper at ICLR 2022
Úlfar Erlingsson, Vasyl Pihur, and Aleksandra Korolova. Rappor: Randomized aggregatable privacy- preseevin ordinal response. In Proceedings of the 2014 ACM SIGSAC conference on computer and communications security, pp. 1054-1067, 2014.
Vitaly Feldman, Ilya Mironov, Kunal Talwar, and Abhradeep Thakurta. Privacy amplification by iteration. In 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS), pp. 521-532. IEEE, 2018.
Marco Gaboardi, Hyun Lim, Ryan Rogers, and Salil Vadhan. Differentially private chi-squared hypothesis testing: Goodness of fit and independence testing. In International Conference on Machine Learning, pp. 2111-2120 PMLR, 2016.
Badih Ghazi, Rasmus Pagh, and Ameya Velingker. Scalable and differentially private distributed 2019.
aggregation in the shuffled model. arXiv preprint
Badih Ghazi, Pasin Manurangsi, Rasmus Pagh, and Ameya Velingker. Private aggregation from
fewer anonymous messages. Advances in Crynology-EURoCCYYY 2020, 12106:798, 2020.
Muneeb UI Hassan, Mubashir Husain Rehmani, and Jinjun Chen. Differential privacy techniques for cyber physical systems: a survey. IEEE Communications Surveys Tutorials, 22((): 2019.
Yaochen Hu, Peng Liu, Linglong Kong, and Di Niu. Learning privately over distributed features: An admm sharing approach. arXiv preprint 1oXiv:/907.000 1.0000.0773,,01111
Yuval Ishai, Eyal Kushilevitz, Rafail Ostrovsky, and Amit Sahai. Cryptography from anonymity, In 2006 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS 066, pp. 239- 248. IEEE, 2006.
Tao Li and Chris Clifton. Differentially private imaging via latent space manipulation. arXiv preprint arXiv:2103.05472, 2021.
Michael A Malcolm. On accurate floating- point summation. Communications of the ACM, 14(11): 731-736, 1971.
Arthur R Miller. Personal privacy in the computer age: The challenge new technology in an information-oriented society. Michigan Law Review, (7(6):108--1244 1969.
llya Mironov. Rényi differential privacy. In 2017 IEEE 30th Computer Security Foundations Sym- posium (CSF), pp. 263 275.. IEEE, 2017.
Arvind Narayanan and Vitaly Shmatikov. How to break anonymity of the netflix prize dataset. arXiv preprint cs/0610105, 2006.
Arvind Narayanan and Vitaly Shmatikov. Robust de-anonymization of large sparse datasets. In 2008 IEEE Symposium on Security and Privacy (sp 2008), pp. 111-125. IEBE, 2008.
NhatHai Phan, Xintao Wu, Han Hu, and Dejing Dou. Adaptive laplace mechanism: Differential privacy preservation in deep learning. In 2017 IEEE International Conference on Data Mining
(ICDM), pp. 385-394. IEEE, 2017.
Gang Qiao, Weijie Su, and Li Zhang. Oneshot differentially private top-k selection. In Marina Meila and Tong Zhang (eds.), Proceedings of the 38th International Conference Machine Learning, volume 139 of Proceedings of Machine Learning Research, pp. 6672-8681. PMLR, 18-24 Jul 2021.
Edward Shils. Privacy: Its constitution and vicissitudes. Law and Contemporary Problems, 31(2): 281-306, 1966.
Larry Wasserman and Shuheng Zhou. A statistical framework for differential privacy. Journal of the American Statistical Association, 105(489):375-38) 2010.
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 Secu- rity, pp. 317-330. Springer, 2020.
11

---

Under review as a conference paper at ICLR 2022
A
APPENDIX: PROOFS
Proof A.1 Proof of Theorem 3.1
Sufficiency:
When 2 60, the sufficiency is trivial as 8 = ōg-
When ca, given that is (Co: 6D) by the definition, for any pair of datasets and S that differ in the record of single individual and any event E,
P(A(S) E E] S P(A(()) 80-
When P [A(S') E E]
1-6n
= Co.
T4050
PIA(S) (
S (6)(A((((((S)) E F. + 60 + 8
E (e E )0 60 5
SEPIA(S) E E|]00+ (e e00 (1
6p (e e
+ e
E
When co S P[A(8)) 1
PIA(S) E = PiA(S) E E"I
$ 1 (PIAA(()) E 60)
11 -1- PSA(S") E 60)
-1- -0 +e ((
+ 50
- +e +d-
(()))
=
50 8n + to -E)P(A(S) E
60 80
8 + (e _0 -e'
E0
5o)
(0) +1
1 e
50 e
( dn)
+ +1+ 1+
1 e
1 ee0
=EPIA(S)) E ER +
Necessity:
We prove the necessity by giving specific (Eo, 8D) algorithm A such that ( is exactly do + 1--60)669 +
Ite
Define Qg 2, 4} and f2g (0, 1). Ler e 2 0,0 80 < and denote I+e5a as aup- Let A be a randomized algorithm that take a single point from G2g and generate output as follows:
P(A(S) = 1| 5 = 0) = 5p:
P(A(S) = 1 S = 1) = 0,
P(A(S) 5 0) 0,
P(A(S) 2 $ 1) -0o
P(A(S) = 3 5 0) = =(1 -1-60m (1-56)oc 500
-11-50)
P(A(S) $ = =1==1--000 -11- - on);
P(A(S) S 0) (1-5o)(1 ao),
P(A(S) - =1 -(1-dg)an-
By definition, 8(e) is the smallest 8 such that P(A(S) C E S = S c S
1-8) 8) + holds true for all E. Sh and E Uss By checking all 64 combinations, we can conclude that (e) 6o [1- (1-66)("00-=7)
14650
12

---

Under review as a conference paper at ICLR 2022
We present key lemma underlying much of the theoretical analysis and may be of use for future developments.
Jec 12 V2na² where a = - + 2. It follows that lim 5p(e) 1. kp(c)
Lemma A.1 Define (c(
Proof A.2 Proof of Lemma
It is well known that (Abramowitz et al.
1988,
for I. < 0:
1
π
exp
t2
o(t)
<
1
t+ V2 +
2
2
-1
-t+ +
12
Let a (-E + () and (-5 1
-2/ }
lim (c) = lim o (a) e (b)
exp -a²
bb² +e
2 Tim
exp
S
π 700
+ /
a2
+
8
-b+ vb2 +4
-aa
1
lim exp 500
2
-a +
a² + 8
-b+ vB2 +
2
-a2
lim exp π 6000
(22
0.
lim (c( lim 4 (a) e ( (b)
c-020
=a²
-ba
2 lim
exp
exp
2 +
π
a + va² + 4
b +
1/2 5
-a²²
1
lim
exp
2
a
v 2 +
_ +
1/2
+
8
2
-a=
2
-1
lim +
exp
2
b
= 0.
Therefore,
lim (e(() = 0. 6+00
(4)
It is easy to see that,
ue a²/2
lim 5,((e) = lim
v 2 = 0
(5)
8000
13

---

Under review as a conference paper at ICLR 2022
By L'Hospital's 's rule:
(c(c) lim
(c)
lim
<-000
(c()
c-00 (c)
c 4 (a² + 2)
= lim
c ((6))
1-000
V
e x ((b)
lim
12
e T (b)
lim
64-00
v2Tb
1.
Proof A.3 Proof of Theorem 4.3
is easy to see that A is (+o0, +o0)- GDP if and only if lim
Gox(c) t00.
6-+
Sufficiency:
A is μ-GDP. Then lim Gar(() S lim (c n.
+1++00
Necessity:
If him +-0000
G5)(c) = too, there must be c > 0 such that A is (ct, + 1)-tail GDP.
Notice that lim (x(()) = 1, we can pick f1 > Po large enough such that 6 (4) > 8A(
p-500
This is possible because by Theorem 3.1
(0 1. Then for c E [0,G), 8x(c) S 5A(0) <
Sps (4) I 5p, (c). A is both (Ce, (h)d and tail GDP for p. no + #1 +1. A is GDP as desired.
Proof A.4 Proof of Theorem 4.4
Let hm Gy(c) Pt-
First we show that lim
2 2 log a(e) S n.:
20000
By the definition the limit, for any HO Pt. for sufficient large e, Gy(e) No and further 8 s
(e). Hence, lim Sale) < 1. By Lemma A.1 e-000 (c)(c)
lim ba(e) < 1.
6-000 ong (e)
Then lim
+00 -2 22og (alc) I lim
6-000 -2log (r)(() (c)
-00 lim - 22og Ea(e] S 14 as desired as we take pr -> Ft.
Next we show that lim 600
2
-2 2oog (c(c)
lim -logdale)
H < nr: then by Lemma A.I
2
2
2 2 log 8,, (c)
lim 60000
lim
lim
2 2og (c)
log pp, (6)
61000
2 2lo (c())
60000
1
Then for a sufficiently large eo.
<0
log ((())
22 2oog 8 (Cv)
Since log is increasing function, it follows which is contradiction.
that ( < Opo(e0) Then Tim Gy(() S no bs.
14

---

Under review as a conference paper at ICLR 2022
Proof A.5 Proof of Theorem 4.3
Let F(e, (c) and F F(x,y) y) = Mewr (I,z). y)-
By definition of Moor Gu(E) μ.
(G Op O,
dc
Ōe
On one hand,
(G,(c)
Op
1.
Op
(G,(()
OF
OF dōp(e)
dx +
de
dy de
On the other hand, by chain rule.
@G,((E)
OF 08 (t)
0q.
Oy 0p
OF (6
dy 0p (c) pc)(()
Therefore,
OF
dr
0u
de
(c)
and (6,(e) can be directly computed:
Using the close forms,
de
@6,((e)
1
+ 20
-
de
2p
(2²-22)²
(6,(())
0p
2T
OF
(u²+2e)
112 1
2e
14
22m
2TT
S
VoTe
dx
24
2 2
Hence,
(2²-20)²
0F
2Te
Bu²
0.
Öy
(22122))²
Notice that
OF v 22Te 0z
Buz
+2
0, combined with the fact that OF 0z
2/2 we can
Ven
2p
conclude that 0 <
Bven (c,5)
22x
By
oF
0, we can see GDPT is order preserving.
de
By
Proof A.6 Proof of Theorem 4.6
We consider the gap between max,e (0. mn) GG (2:) and maxie (o. nt (G (a:)) bound
the length of [1t .1+*] in two cases.
Case 1: If (- (G (2:))
G (2o). then maxie (0, m 1 (G (x:))
G (zo) = Mann (0)) Mar (0))(()) + -2rD Therefore,
max G(c) S G (2o) S (GT (ao)) V2nD cE(0,em]
Case 2: If max m+11 (Gt (xi)) G (2a), then by the order preserving property, the optimal μ lies in [,=",t" ,,tt), where μt= = max(pu, (0... (G (2i)3) and μ* max(pn, maxie ( (x:))). Notice that
max (07, (x:)) iE(o.--,m) .n) s0)
max (Pon ( (1(#41))) (G(1...,t1) (
(Pone (1:+1, 5a(x:)) - 22
max 16 se(1.- .+11)
max
{G) (x:)) - D.T
i5 EE(1. (1.-. (+11
15

---

Under review as a conference paper at ICLR 2022
In both cases the gap is greater than V2 desired.
Proof A.7 Proof of Theorem 4.7
By the definition of C, o A is bounded in ly, .y+l. Therefore the global sensitivity of C o A is no greater than y + y Then R o C o A is special case of the Laplace mechanism. By Balle et al. 2020a), C ca-DP Then (R = 0 < 6p(c) for any 2 Ch.
In addition, because of the post-processing property, &Rocoa(t) S da(c) < 6p(c) for any < ch. Therefore, R a A is μ-GDP.
B APPENDIX: REFINING THE PRIVACY PROFILE
Given a trade-off function f(e, and fixed parameter From definition of the trade-off function it is instant that the for any (e, E) Ω = (( Then, (c, 5)-DP is also guaranteed if there is (co, do) Ω such that (co, DoD implies (c, 6)-P. Therefore,
f(e, 6)}. (e, 6)DD is guaranteed.
Ac(c) min (88 (8810= 1 f(co, 50) and 8 2 60
(1 - (1-60)(e
1
Notice that by Corollary 3.2 (Eo. -DP implies (e, 6) with d do only if < ED. we rewrite the (c) as:
Ac(c) inf g(c, coEle,20)
where g(c, co) = (1- (1-))( -0 ((((E) and 6Λ is the naive privacy profile defined implicitly by f(o,, do). For continuously differentiable f. the minimum value of the right-hand side can be found be take the derivative:
0g(E,60)
te (1 610 ( c 6x (co))
5A
deo
We remark that the sign of (6 does not depend on For both of our example and 3, we Beo
both find a particular value c such that Sign (ole,eu)) = Sign(c c²). This means for 2 d.
8eo
(c) 5c(c) and otherwise (c) equals to the value derived from (c, (c()))
C APPENDIX: REFINING THE O
Given trade-off function f(c, 8) and desired 8), From definition of the trade-off function, (e, 6)DP -D is guaranteed when o = f(e, 5). We treat the a as the noise parameter and without loss of generality we assume smaller value of is preferred. Notice that (e, 8)-D is also guaranteed if there is (co. dg) E such that (cu. DDP implies (c, 8)-D. Therefore, o can be chosen as,
min [f(co: 60) 222200 5n (1 (e -E9)
+ e
Notice that by Corollary 3.2 (eo, dDP implies (e, 8) with 5 do only if < cg. we rewrite
inf g(e, 60),
eaEle.00)
where g(c, 60) f(Eo, (1 - ((o)) - + 6((()) and o' is the naive privacy profile defined implicitly by s(en, do). For continuously differentiable f. the minimum value of the right-hand side can be found be take the derivative:
àg(e,6o) deg
1+
Ea (4((0)) + (1 (((c)) + 6x (e())) 05 le=cu, +
0f
of De le=co,ō=ōu
(1 (1+ E00
16

---

Under review as a conference paper at ICLR 2022
We remark that the sign of (5a(e) does not depend on and the point can be effectively solved numerically.
D A SELF-CONTAINED EFFICIENT HEAD MEASUREMENT ALGORITHM
First we formalise the binary search algorithm to find /eepp*
Algorithm 1: Binary search
Input: E, 6, Amax. b;
Output: H4 (lower and upper bound of po):;
4-- f 0;
44 < Mmaxi
while f 1 >>
b do
J = a tp:;;
( > then
n² puu
else
p t No:
end
end
return nt, p5
Given a proper searching range [0, [max], the algorithm 1 yields at and μ such that f Mane (e S 1t and - < b. We denote 1= p (e, 6, Pmax, b) and μe as M (e, Mmax When searching for via privacy profiles, the Mmax can chosen as Hrae (ft,, 50)) because Pene will not exceed this value on [0, e (refer to Theorem for the value of pr). Alternatively, Mmmx can be set to a large constant for convenience, for example 10. In this case, if the outputted f= equals to the preset value (10) then the privacy profile fails to imply 10-GDP. practice. GDP with μ 2 provides almost 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 be formally written as follows:
Algorithm 2: Finding μ with privacy profiles (Naive).
Input: A, Ch. Me, c, Mmax- (Privacy profile, the end point of searching <h. / given by Theorem reciprocal of error margin, searching range);
4.3
Output: μe,, 14 (lower and upper bound of p).;
i + 0:
n + VBCTER + 1;
D th;
__ + max(un:P Pc);
& Umax'
while I n + do
&- iD + Eni
x + (i+ (i+1)D+ + eni
1+ + max(u4, M (x xx (x+xx Mmax: 2c ));
a_ t max(u=, Map (x 5, (x (x Mmaxx x()) ));
1 < 11
end
return pt
Algorithm 2 naively go thorough all G7 (x:) and G (zi). By the choice of D. the true gap between max G7 (e) and max G (6) is less than za and the binary search estimate the Pow with an error less than z Combined together, the overall gap between estimated f and nm is less than However, there is still room for optimization:
17

---

Under review as a conference paper at ICLR 2022
We take M4 max(f4 M (x ,0((xt), Mmax. 2r for example, same optimization can be applied p.- t- max(fl- Har (x+ 6 (x Mmax 1)) well. The naive operation, p4+ max(f4 Mo044.-tee More (2
Mmax: 2)) can be optimized into "If (x+((=)) < (2(x)), ) then ja u (x , ,,((xx)) Mmux: 2).. To see this, we list all three possibilities as follows:
. Case I: at < Mave (a, ,6((xt)) S u (A Mmaxx 2e2 ))
1. Case Meop (x ;0a(0)))))))) S n+= S p ,6 (aatt;; (mmaxs 2c 1x) Case 3: Menr (x (d((=))) S M , ( Mmax: 2) < ptt.
.
In case 1, both of the naive operation and the optimized operation will update x++ to t (0 (x(xx)) (mmx: ))
In case 2, the optimized operation will do nothing, because the test 6x+(x0 (x=) < (x(x)) will fail. The naive operation will update 1z* due to the error of binary search, which should be avoided.
In case 3, the optimized operation will do nothing, because the test 6xt (x-) < <a(xt) will fail. The naive operation will also do nothing because the max operator will choose ut.
To sum up, the optimized operation always give a more accurate update.
Besides, we want to avoid case 1 because only in that case binary search is needed. Notice that case I happens only if o (ar) < (x+)), which is equivalent to 1x < M' (x ( the
In
round of loop, the condition jtt < Menr ( (a(x+)) holds true only for all j E Manp (x. _5x())) < Pram (x " .da(x*)); where zj and xÿ are the values of x and x in the round j. This inspire to shuffle 2; before iteration because after shuffling, the probability of "Mum (=j- (xx))) < Mane (x ,6 (x+)) for all E (0.... k)" will be - The expected
... .k), {0.-..
K+I'
occurrence of case will be 2nt1 K+I Ollo((n). We present the complete optimized algorithm follows:
Algorithm 3: Finding μ with privacy profiles (optimized).
Input: A Cho Me, C. Pmax- (Privacy profile, the end point of searching ca. μ given by Theorem 4.3 reciprocal of error margin, searching range);
Output: μt., 144. (lower and upper bound of p).;
i + 0:
+ [8CTCC| + 1;
D <a
__ + max (1n: Me);
14 <- /mmax:
= 10. 1..., n + 1);
Shuffle S;
while 5 n 1 do
+ S D + Chi
xt + S [ii+1]D= 1]D+ Ehi
6 (x < <d((xt) then
a= + Mtt ,81(xt), Mmax: 2/2 });
end
if 11,5,((r" (x+) < 6 (x=) then
n < Ma (x+ 6A(x Amax: )
end i i+1
end
return nt, 14
The time complexity of shuffling S O(n) O(c,). Each binary search has time complexity of Ollg((c) and the expected number of binary searches is (log((Ac)). The overall time complexity of the optimized algorithm is therefore O(eAc + log log(ex)).
18

---

Under review as a conference paper at ICLR 2022
E
APPENDIX: PLOTS
E.1
THE LAPLACE MECHANISM UNDER GDP
Laplace 0.5 DP
Laplace 1.0 DP
2.0
Laplace 2.0 DP
0.5 DP
1.- DP
1.5
2.0 DP
1.0
0.5
0.0
0.0
0.5
1.0
1.5
2.0
2.5
3.0
3.5
4.0
Figure 3: The plot of GDPT e-DP privacy profiles and the Laplace mechanisms with the same c-DP guarantee.
19

---

Under review as a conference paper at ICLR 2022
E.2
THE EFFECT OF SUBSAMPLING
2y
Labacc 2y-05
500 7
130
S60 00
1.50
125
0.2
08
4.0
2.0
4.5
5.
4.0
00
0.5
11
Figure 4: (Left) GDPT of the Laplace mechanism for various of (Right) GDPT of the SGD for various of y.
1.5
1..
y=03
.000 y=0
600 0.2
2.0
Figure 5: (Left) GDPT of the ICEA for various of 7. (Right) GDPT of the &, for various of 7
20


Reviews:
[{"review_id": "jRMpOmylwdR", "reviewer": "Reviewer_H1fA", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "## Strengths\n- This paper proposes a transformation and several auxiliary lemmas that may help make GDP more practical and more widely applicable.\n- The non-trivial relationship between $(\\epsilon, \\delta)$-DP's is interesting.\n\n## Weaknesses\n- I do not believe that GDPT yields significant insight that cannot be drawn from the privacy profile curve itself. Specifically, almost all the applications can be derived via the latter as well. (More details are presented below in \"Detailed Comments for Authors\".)\n- Although the paper claims to provide \"engineering tools\" for GDP, no evaluation is given. On this front, I think it is important to show e.g. how tight & how efficient GDP tools presented here are compared to other methods in literature such as Privacy Loss Distributions [Sommer et al., PETS 2019].\n- The \"utility improvement\" from the non-trivial relationship between $(\\epsilon, \\delta)$-DP's does not seem that appealing. Specifically, the examples in the paper uses very high $\\delta$ (all of them larger than $0.05$) which is not a value used anywhere in practice. (I have not seen any practical application where $\\delta > 10^{-4}$.) Indeed, this does not seem like a coincidence: the new relation only seem useful for $\\epsilon, \\epsilon_0$ relatively close and $\\delta, \\delta_0$ relatively large (otherwise the additive term in $\\delta_0$ would be too large).\n- The non-trivial relationship between $(\\epsilon, \\delta)$-DP's also seems to be implicit in previous work. As an example, the paper \"Optimal Accounting of Differential Privacy via Characteristic Function\" by Zhu et al. has a characterization that says that the privacy curve must be convex (Lemma 11) when the x-axis is changed from $\\epsilon$ to $e^{\\epsilon}$. Using this convexity on $0, \\epsilon_0, \\epsilon$ also yields this characterization. I think this is a minor weakness since it is good for the statement to be written down in a more explicit form as is done here anyway.\n\n## Detailed Comments for Authors\n- *Regarding GDPT:*\n  - Theorem 4.4 can be easily derived from Lemma A.1 by setting up $f(\\epsilon) \\leq \\delta_\\mu(\\epsilon)$ for some $\\mu$.\n  - For Theorem 4.6, the staircase functions taken are equivalent to rounding up or down $\\delta(\\epsilon)$ in the privacy profile for all $\\epsilon \\in [x_i, x_{i + 1}]$ in each $i$. So the entire proof of Theorem 4.6 can also be derived as easily via the privacy profile curve as well.\n  - Overall, I think it'd be better if you show an application of GDPT that would be much harder to derive under the privacy profile notion. Otherwise, I'm not sure why we should define yet another privacy curve in addition to the already many curves.\n\n### Other More Minor Comments:\n- Definition 1.1: missing $\\leq$ in the equation.\n- Page 2, paragraph before Section 1.1: $\\sigma$ is not yet defined?\n- Page 3, second example: isn't the Gaussian mechanism itself also an example of such a tradeoff?\n- Page 3, third example: the ICEA algorithm of Ghazi et al. (2019) was actually proposed much earlier by Ishai et al. [FOCS 2006] in the paper \" Cryptography from anonymity\". See also the papers \"Private Aggregation from Fewer Anonymous Messages\" by Ghazi et al. [EUROCRYPT 2020] and \"Private Summation in the Multi-Message Shuffle Model\" by Balle et al. [CCS 2021] which give better analysis of ICEA compared to Ghazi et al. (2019).\n- Page 3, third example: m in the ICEA algorithm is *not* maximum error but the number of messages (i.e. additive shares) per user.\n- Page 5 Definition 3.2: it doesn't seem like the tail condition is used in a meaningful way (at least in the main body)? If so, then maybe there is no need to define it (at least in the main body).\n- Page 6 before Theorem 4.1: \"... the following theorems *formalizes* ...\" -> \"... the following theorems *formalize* ...\"", "summary_of_the_paper": "## Summary of Contributions\n\nThis 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)).\n\nThis paper develops tools that can help understand/deploy GDP more easily. Specifically:\n- 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$.\n- 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.\n- 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$.\n- 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. \n\n\nAlong 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.", "summary_of_the_review": "## Recommendation\n\nOverall, although I think this paper advances the understanding of GDP, I am unconvinced that GDPT yields significant novel insight that cannot be achieved otherwise and more empirical evaluations have to be made in order to determine the practicality of the tools proposed here. Due to this, I recommend rejection.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "gukBh4sbrv0", "reviewer": "Reviewer_qUya", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "GDP is an elegant framework for analyzing private algorithms, due to its nice composition properties. A wider application of the framework, however, would benefit from automated tools for deriving tight GDP guarantees for a given algorithm. The main strength of the paper is in giving one such tool, and showing how it can ease the privacy analysis of several algorithms. The visualizations of the privacy profiles transformed by GDPT in the paper provide some insight on the privacy guaranteed by several basic algorithm. The main weakness of the paper for me is in the strength of the applications mentioned at the end: \n* the analysis of the Laplace noise mechanism is simple, and probably not the best illustration of the power of the methods here; \n* the analysis of SGD is limited to giving guarantees for some constant $\\varepsilon$ and $\\delta$, in particular, a value of $\\delta$ that is too high for deployment; the illustration that the partial order on $(\\varepsilon, \\delta)$ can help improve an algorithm's error analysis is interesting, however;\n* I am not sure what the takeaway is from the analysis of subsampling?\n\nSo GDPT may end being a useful tool in a privacy toolbox built around GDP, but the paper does not quite manage to make a strong case for it. Because of this, I will be ok if the paper were accepted to ICLR, but I will not push for it.\n\nSome further minor comments:\n* DP definition has a typo - missing less than or equal to sign.\n* Concentrated DP was first proposed by Dwork and Rothblum (https://arxiv.org/abs/1603.01887).\n* The references for DP SGD should contain Bassily, Smith, Thakurta, FOCS 2014\n* Is $\\mu_{\\text{GDP}}(x,y)$ well-defined: what about existence and uniqueness of $\\mu$?", "summary_of_the_paper": "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.", "summary_of_the_review": "The paper makes a contribution to automating the privacy analysis of algorithms within the elegant GDP framework, but doesn’t manage to make a strong case for the usefulness and applicability of the new tool it develops.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "QSQxEEMEREm", "reviewer": "Reviewer_RPM2", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "The work presents a comprehensive overview of the GDP in the context of privacy profiling, that is attempting to reduce the detrimental effects of DP on the results of algorithmic training. \n\nThere are many interesting insights presented based on the results of a closer analysis of GDP in regards to its behaviour around the head/tail composition of the function through the lens of the novel formulation of GDPT (including experimentally shown tighter privacy analysis, resulting in better utility of the algorithm).\n\nThe motivation is very clear to me, as the existing formulations of DP are notoriously difficult to interpret by a non-specialist, require multiple parameters that are not easily defined in practise and provide guarantees that can be difficult to put into perspective. In addition, DP is known to be detrimental to the utility of the trained model, which a more carefully selected formulation (such as GDP) can partially mitigate. Therefore, I believe that this work is a needed step towards democratisation of privacy-preserving ML and a timely investigation into mitigations of DP’s detrimental effects to algorithmic training performance.\n\nMajor comments:\n\nWhile the motivation behind the analysis of GDP is clear, the potential applications of the work (in general) are too, the take-home message of the findings is not. Is the key message of the paper that GDP gives tighter guarantees? Or that existing DP formulations are pessimistic and detrimental to utility? It is very difficult to assess the impact of the work, when there is no clear message on how and why it needs to be integrated into the existing workflows. To alleviate some of these issues I would suggest being much more explicit in the conclusion and contributions: in my eyes GDPT on its own is difficult to put into practical context. I do, however, acknowledge that Section 5 introduces how GDPT can be applied to existing notions, but in my opinion, this comes very late and the conclusions are very ad-hoc. There is no clear direction of how the insights from this work are meant to be interpreted and what the main message of the manuscript is.\n\nIn terms of content, my main concern here is the overall novelty of the work and the insights presented. There exists a similar line of work on the interpretation of GDP by Asoodeh et al. [1], that was published in March 2021 and presents an argument about the properties of GDP along with its relation to DP, and the associated effects on the privacy-utility trade-off. This work, however, was not cited or addressed in this manuscript. Similar things can be said about Bu et al.[2], which considers the application of GDP in the context of deep learning. Many of the insights seen in this work (e.g. the interpretation of GDP and its relation to DP in general) have already been presented in these two works and are thus hardly novel. While the goals of this work and [1] are tangential, and GDPT being based on DP analysis through the head/tail behaviour and not on a reinterpretation of other DP formulations and authors here consider Laplace mechanism rather than Gaussian, the conclusions these works present are very similar. \nI would like, therefore, to request that reviewers compare their contributions to the work by [1] and specify the novel conclusions that can be drawn from their work in comparison to the prior work. I am open to changing my review should the authors present a sound argument that their work derives additional insights when compared to the literature I linked and particularly, their implications for the wider scientific community.\n\n[1] - Asoodeh, Shahab, et al. \"Three variants of differential privacy: Lossless conversion and applications.\" IEEE Journal on Selected Areas in Information Theory 2.1 (2021): 208-222.\n[2] - Bu, Zhiqi, et al. \"Deep learning with Gaussian differential privacy.\" Harvard data science review 2020.23 (2020).\n\nAnother concern I have is a lack of any discussion on the Gaussian mechanism. As this paper is positioned to be applicable for ML practitioners, I find the scope of these findings rather limiting (especially if we were to consider deep learning) if only the Laplacian mechanism is considered due to its unfavourable composition properties. Moreover, I am unsure if it is enough to only assess Laplacian in the work that considers Gaussian DP and completely disregard the Gaussian mechanism. In general, I would like to see justification on why Laplace is the suitable choice here, as otherwise I am struggling to see the broader impact of this work and would, therefore, encourage authors to include some concrete applications of their work.\n\nOn this note, I would have expected a more detailed discussion on the applications of this work (or of DP in general) in the domain of ML specifically. I would encourage authors to expand their Section 5 and provide explicit applications of their work in this domain. \n\nThe experimental results (Figure 1) could be explained better. The results are relatively straightforward, but the subsection comes unannounced and following the method of obtaining these was not straightforward.\n\nMinor comments:\nThe actual novelty of the paper is not very clearly presented, the abstract contains a lot of information about GDPT’s details, so the actual contributions are diluted (and the same thing can be said about the introduction).  As a result, it is very difficult to determine the actual novel contributions that the work contains. I would suggest trimming the technical details down to make the contributions of the paper more convincing. \n\nMultiple issues with Definition 1.1:\n missing a less than or equals sign.\n does not specify the condition of ‘differ’: is this an add/remove a record or is it a replace a record?\n", "summary_of_the_paper": "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).\n", "summary_of_the_review": "Overall, while I do believe that this paper tries to address a very important problem and is formally sound, I am not fully convinced that there is enough novelty in the existing manuscript to justify the acceptance and therefore I believe that this paper is just below the bar of acceptance.\n", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "Q12sZsyLHED", "reviewer": "Reviewer_ZW49", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "This paper attempts to identify a class of DP algorithms they call GDP algorithms. It is largely unclear what is the motive of the paper and what is the application. I will list down some of the issues below:\n\n1. The theorems in section 3 are either results of previous works or are at best trivial facts. \n\n2. The theorems in section 4 are just basic algebraic manipulations. This paper thus lacks technical novelty.\n\n3. The purpose of the introduction of the transform is unclear to me. There is no formal result showing the improvement in utility for a class of algorithms. The abstract claims their technique refines the utility, but this is illustrated using only 1 example and some basic calculations.\n\n4. The abstract claims they study the effect of subsampling on the GDPT, but the only thing mentioned about subsampling is that it doesn't give any amplification.\n\nLargely, I don't see any applicability of the transformation introduced in this paper.", "summary_of_the_paper": "In this paper, the authors propose the Gaussian Differential Privacy Transformation to identify which algorithms fall under the framework of of GDP.", "summary_of_the_review": "The paper lacks technical novelty and makes no real contribution/improvement to support the new transformation for characterizing introduced. Thus, I think it is not good enough for publication.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "1: The contributions are neither significant nor novel.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}]

Author rebuttal:

Meta-review: We thank the authors for their response. The reviewers agree that this paper provides contributions in automating privacy analyses under the Gaussian differential privacy (GDP) framework. The reviewers also pointed out several drawbacks of the paper. Most importantly, the reviewers do not find the presented applications to be convincing. In particular, the presented result can be much strengthened if the proposed method can lead to improved privacy analysis for more sophisticated algorithms such as DP-SGD across a wide regime of epsilon and delta. (In general, the privacy guarantee is very weak with delta bigger than 1/n.) Overall, the paper does not seem to provide enough evidence to showcase the usefulness of their proposed method.
Decision: Reject