Approximate Differential Privacy of the $\ell_2$ Mechanism
Authors: Matthew Joseph
Alex Kulesza
Alexander Yu
Venue: ICML 2025 poster (2025)
Keywords: differential privacy
Primary area: social_aspects->privacy

Abstract: We study the $\ell_2$ mechanism for computing a $d$-dimensional statistic with bounded $\ell_2$ sensitivity under approximate differential privacy. Across a range of privacy parameters, we find that the $\ell_2$ mechanism obtains error approaching that of the Laplace mechanism as $d \to 1$ and approaching that of the Gaussian mechanism as $d \to \infty$; however, it dominates both in between.

Approximate Differential Privacy of the lg Mechanism
Matthew Joseph
Alex Kulesza"
Alexander Yu"
Abstract
1.1. Contributions
For arbitrary dimension d and privacy parameters e and 8, we provide an algorithm for choosing to obtain l mechanism that satisfies (s, 6)-DP. The resulting Eg mecha- nism can be efficiently sampled in parallel and empirically dominates both the Laplace mechanism and the analytic Gaussian mechanism terms of mean squared & error (left plot in Figure/ 1). Moreover, unlike the Gaussian mecha- nism, the & mechanism always satisfies a pure DP guarantee (right plot in Figure 1).
We study the & mechanism for computing a d- dimensional statistic with bounded lg sensitivity under approximate differential privacy. Across a range of privacy parameters, we find that the & mechanism obtains lower eπror than the Laplace and Gaussian mechanisms, matching the former at d = 1 and approaching the latter as d + co.
Our algorithms bound relevant quantities of the privacy loss random variable for the lg mechanism. Balle & Wang (2018) showed that mechanism M is (c, 5)-DP if and only
1. Introduction
P [eM.x,x 2 - P [fM.X', S -c] $ 5
(1)
Computing d-dimensional statistic with bounded & sensitivity is fundamental task in differential privacy (DP) (Dwork et al., 2006). It underlies standard algorithms like private stochastic gradient descent (Song et al., 2013; Abadi et al., 2016), the binary tree mechanism (Chan et al., 2011; Dwork et al., 2010), and the projection (Nikolov et al., 2013; Nikolov, 2023), matrix (Li et al., 2015; McKenna et al., 2018), and factorization mechanisms (Edmonds et al., 2020; Nikolov & Tang. 2023). The canonical approxi- mate DP algorithm for this problem is the Gaussian mech- anism (Dwork et al., 2006). To compute statistic T(X), the Gaussian mechanism samples an output according to 9x (y) & cxp(-1lly - T(X) ( for an appropriate value of a; in particular, the analytic Gaussian mecha- nism (Balle& & Wang. 2018) chooses the smallest possible o sufficient for the desired approximate DP guarantee.
where M x is the privacy loss associated with M on arbi- trary neighboring databases X and X' (Section 2). Proving (s, 8DP therefore reduces to upper bounding the first term and lower bounding the second. We show that the first term is defined by the mass that M (X) places on region of Rd determined by certain spherical caps, while the second term is defined by the mass that M (X') places on the same region. We then provide algorithms to approximate the first term from above and the second term from below. Because these approximations are provably upper and lower bounds, they yield formal differential privacy guarantee. Exper- iments suggest that, for reasonable algorithm parameter values, these approximations are tight (Section 4.1).
1.2. Related Work
Ganesh & Zhao (2021) also spherical caps analyze what they call "generalized Gaussians", which have densi- ties proportional to exp(-ily - T (())lp// for integers 2 1. A few features separate their work from ours: they study a statistic with bounded Eo2 sensitivity; their results do not cover the l mechanism, which uses norm p = 2 but exponent p' 1; they work with a sufficient condition for (c, 8)-DP, which only bounds the first term in Equation (1) by 5. leading to looser results; and since their goal is an asymptotic utility guarantee, their results rely on asymp- totic concentration inequalities that are less precise than the approach used here.
In this paper, we analyze the fg mechanism. Given pa- rameter a, this mechanism samples an output according to density fx fx(y) & exp(-lly~ - (22)))/ As an in- stance of the K -norm mechanism (Hardt & Talwar, 2010) using the & norm, the & mechanism immediately satisfies (pure)) DP and can be sampled efficiently. However, its approximate DP guarantees are not well understood.
'qqual contribution 'Google Research New York. Correspon- dence to: Matthew Joseph <mtjoseph @ wwtpccpph@goog..coooo google.com>>.
Proceedings of the 42nd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).
A few authors have studied the & mechanism, primarily in

---

Approximate Differential Privacy of the &g Mechanism
normalized error
mechanism pure DP guarantees
normalized mean squared I, error
2.50
DP parameter
2.25
2.00
1.75
1.50
laplace
gaussian
1.25
1.00
0
20 40 60
80 100
20
40
60
80
100
dimension
dimension d
Figure 1. Left: normalized mean squared & emror. At each d, compute squared &2 emrrr for the (1, 10 D-DP Laplace, analytic Gaussian (Balle & Wang, 2018), and &2 mechanisms. Quantities are normalized so that the analytic Gaussian mechanism error is always 1. Note that truneate the Laplace mechanism d after which its relative the analytic Gaussian mechanism continues grow. See Section 4.2 for details. Right: the pure DP guarantee of the (1, 10 3-DPP & mechanism as d grows.
the context of objective perturbation (Chaudhuri et al., 2011; Kifer et al., 2012; Yu et al., 2014). However, they all use pure DP rather than approximate DP.
Gamma (d 1, the Gamma distribution with shape d + and scale 2) uniformly sample Bd; and 3) output T(X) +z.
2. Preliminaries
3. l2 Mechanism
We use the formulation of (c, 6D- given by Balle & Wang (2018). It is defined in terms of the privacy loss random variable. Our results apply for either the add-remow swap notions of neighboring databases.
This section provides an algorithm for computing to achieve an d)-P) f2 mechanism (Section 3.1) and then describes simple method for sampling the &g mechanism in parallel (Section 3.2). Without loss of generality, we assume that our statistic T has & sensitivity A₂ = 1. If A * 1, we can run the algorithm on T/A2 and rescale.
Let M be mechanism whose output den- sity given input database X is fx- Then for neighbor- ing databases X, X', the privacy loss of M at point y is (x)) In fx((y) (x.(2) ). Its privacy loss random vari- able is (M, where Y ~ fx.
Definition 2.1.
3.1. Privacy Analysis
The overall goal is to translate an (e, 8DD privacy budget to the minimum a such that the & mechanism M with parameter a satisfies (e, 8)DD.. To do this, we focus on a subroutine that determines whether or not M satisfies (e, 8)- DP and then binary search over
The following results relate the privacy loss random variable to differential privacy.
Lemma 2.2. Mechanism M is e-DP if and only if. for any neighboring X', 1.M.x.x (Y) S
Recall from Lemma 2.3 that M is 8E if and only if P [fM,x,'' 2 c] - e [fM,x S -s] S 8. The next subsections will provide algorithms that upper bound the first term and lower bound the second term, and thus err on the side of a conservative privacy guarantee.
Lemma 2.3 (Balle & Wang (2018).. Mechanism M is OEP if and only if. for any neighboring X X',
P [[M.X.XX 2 e [fM.x.X -e 8.
Since the & mechanism can be viewed as an instance of the K-norm mechanism (Hardt & Talwar, 2010), we recall some relevant results about the K-norm mechanism.
Before starting our privacy analysis, we consider simpler (but, as will see, significantly worse) approach. The & mechanism, and the K- K-norm mechanism more broadly, can be viewed as instances of the exponential mechanism (Mc- Sherry & Talwar, 2007). The exponential mechanism ad- mits a few possible approximate DP analyses. For example, the D-DP exponential mechanism satisfies e" --concentrated DP (Cesar & Rogers, 2021), and a concentrated DP guaran- tee can be converted to an approximate DP guarantee (Bun
Lemma 2.4 (Hardt & Talwar (2010)). Civen norm || - [|. scale purameter a, statistic T with I|-sensitivity A, and database X, the K-norm mechanism has output den- sity fy) & cxp cxp(-lly T(X))//o and satisfies A ADP. Moreover, letting Bdd denote the unit ball for ||. the follow- ing procedure samples this mechanism: sample radius
8
2

---

Approximate Differential Privacy of the & Mechanism
& Steinke, 2016; Canonne al., 2020; Asoodeh al., 2020; Zhu al., 2022). However, any such analysis also applies to the Laplace mechanism, and the s-DP Laplace mechanism is only ( 8 for E' ~ E (()) (Lemma A.2 in the Appendix). This is a negligible improvement for realistic 6, so a different privacy analysis is necessary.
3.1.1. FIRST TERM UPPER BOUND
For the privacy guarantee to hold, Equation (1) must hold for arbitrary neighboring databases X and X'. Since the & ball is spherically symmetric, without loss of generality we consider statistic 7 where T(X) 0 and T(X))
Figure 2. An illustration of for a = 1/(2s). We draw the projection of V onto span(e1, 62) as the shaded region.
(1, .0). Shorthand the respective mechanisms as (() and M Then
Lemma 3.3. Ifa S and d = 1, then IP Po-ar(o) lu E VV
1 1 2 exp ( !)).
[x(
(M) = In
[xx((v)
Proof. M has the same noise density as the Laplace mech- anism (a), and ly ei |y| 2 as if and only if σE). For x 2 0, the Lap CDF is F(z)
expl- |/ 1 //2
in
expp-|13 e1 [2/
y I }
exp )) so by oe 2 0. F M(0) by E Vl exp ( H)).
(lly ei |||2 l1v|12)
so we want to upper bound
This leaves the case a S and d 2 2. We proceed under that assumption.
t (llv filleelle- (1ull)) 2
P Po-M(O)
(2)
Assumption 3.4. Statistic T has dimension 2 2, and
We shorthand the relevant region in Equation (2) as V. Definition 3.1. Define V {v 1 (11u-eal1--1llll e), M's 's high privacy loss region.
When d 2 2, the level sets of M are spheres, and will show that the the high privacy loss portions of level sets are spherical caps.
A simple case is o 2
Definition 3.5. For r > and z E Rd, define Sr.= = (ar E IRd || - 2||2 = r). the sphere of radius r centered at 2. For any sphere Sr. where z Oc.O......) 0). the spherical cap of Sr. of height is the set of points Sr, ((11..., E Rdd | - =|12 = r and #1 S c - r + h). See Figure 3 for an illustration.
Lemma 3.2. 2 if and only iP M()) (v E =|=0 0.
Proof. The equation I|ly ei || ||v||el ae defines hyperboloid with foci 0 and e and constant difference as. If we instead consider ||y e ||2 llv/l2 2 ae, removing the absolute value restricts the hyperboloid to the -e facing component, and moving to inequality yields the convex hull of that component. An illustration appears in Figure
If 1. then lyy eıll2 llvllz de has solution because the triangle inequality means |yy e ||vla < ||ez]]. Thus V = 0, so Py~a((o) [y E V] = 0. I = ; then Ily-en 2arlll-210 ||yl|2 2 ae only holds for contained in the -ei axis. This set has measure 0, so Py)M(() [y e V = O. Finally, o < J. then |/y - ell - llylla 2 ae determines a -e1 facing component of the hyperboloid that is non- degenerate, so convex hull has positive measure, i.e. O
Figure 3. The unit circle in gg² with spherical cap (thick purple arc) of height 0.5. In Rd, the sphere and spherical cap are both (d 1) dimeesssion objects.
Py>M(()) [y E V]>0. 0.
Lemma 3.6. Define height
The rest of this subsection considers a < 2 When d= 1, all 4p norm mechanisms are identical. In particular, the lg mechanism is equivalent to the Laplace mechanism.
h(r) = min (r(1 (r(1-c0) ca)+
1 - (EO)²
2r
2
3

---

Approximate Differential Privacy of the & Mechanism
Then S,,0,1(r) V n Sn,0
then h(()) [0, 2r] and S,0,0(r) = V S,,0 Since r(1
Eσ) + - > 2r for < 1-ea this piecewise function is
2 equivalent to h(r) min (r(1 Eσ) + 1-(e0)" 2r)
Proof. Orient the 2-dim plane span(e1, e2) so that the posi-
tive direction is right and the positive e2 direction is up. Consider the points O, é1, and some y E Sr,0 n H where H is the upper half of the span(e1, 62) plane (i.e., 1/2 2 0). Let be the clockwise angle from y to et. Proofs of the follow- ing claim (and others omitted in this subsection) appear in Appendix A.1.
We showed in the above proof that, for small r, the entirety of S,o lies in V. Corollary 3.7. If 1-50, then S,,0 C V.
It remains to analyze the high privacy loss region for larger r. Our analysis will repeatedly reason about the fraction of sphere occupied by cap.
Claim 3.6.1. |V - e1 e1ll2 - lly decreases as decreases.
We want to identify a function h(()) for all r > 0 such that Sr,0,6r)) = V n Sy.0- Assumption 3.4 means o < g. so by Lemma 3.2, V n S,,0 is nonempty. The analysis splits into cases.
Definition 3.8. Let Fr.h denote the fraction of the surface of Sr occupied by cap Sr.o.--
Lemma 3,9 ((ii, 2010)). Let Iz(a, b) = 12 p- (1-1) de
Jo 10-1
denote the regularized incomplete beta function. Let be the height function defined in Lemma 3.6. If h((r) S r, then
Case 1: S & V. Since _ (Ilp- en 1l2 - lIpl(2) changes monotonically by Claim 3.6.1 then there exists p (P1. 0.....)) 0) E Srp at the base of S,,0,(r)) such that < e1 lIlll))
Fr,M(r) 2 M())())) (d-1 22) hfr > then Fr.h(r) = 1 P+2r-N(r)
Then h(r) satisfies (r- +
p = r², and we get P2 / /2(())r h(r)?.
There is no closed-form expression for [a but it is standard function in mathematical libraries like SciPy (SciPy, 2024).² We can therefore use Lemma 3.9 to compute the fraction of any S,00 that lies in V UVER+S,,,M0 (Lemma 3.6). It remains extend these results about individual spheres to results about V as whole.
We can now derive the desired expression for h(r).
Claim 3.6.2. (lpp - ell22 - lIpll2) = E is equivalent to M()) = r(1 - co) + 1-5²0²
Moreover, we show that with the above definition of h(r), the constraint fi(r) E [0, 2r| is equivalent to a constraint on the radius given by 2 2
The next lemma shows that the high-loss cap fraction de- creases with r. It combines Lemma 3.6 and Lemma 3.9 to show directly that the appropriate (=, b) is monotone in in the desired direction. Since the proof is again mostly calculation, it also appears in Appendix A.1.
1-20
1-000² 20² E [0, 2r] if and only if
Claim 3.6.3. r(1 - cσ) + r
2
1-8a 2
Lemma 3.10. Fr,0(r) is monotone decreasing in
In summary, Sn,0 & V if and only if 2 " and for such r, we have S, S,,0,(r)) V y Sr when h(r) is defined as in Claim 3.6.2.
This suggests the following approach: if ( samples y with ||y||2 > r with probability p. then pF,,,(r) is an upper bound on (0) [y E V, ||yll2 > r]. The following result gives closed form for p. The expression uses the lower incomplete gamma function and the gamma function, which are also standard functions in mathematical libraries. The proof is mostly calculation and appears in Appendix A.1.
Case 2: Sp C V. By the above, Sr,0 C V if and only 1-54
r < 2 The statement Sr.0 C V is equivalent to dllp ei || (|p||2) (v 1)2 2h(r) -)) 2 for all p S,,o. and this inequality is equivalent to h(r) < r(1 -11-a- ((1-Ea)+ + 1- by replacing equality with inequalities in the proof of Claim 3.6.2. By Claim 3.6.3, r < 1- is equivalent to r(1 -E0- 1-g"o² > 2r. Then defining h(r) = 2r suffices to satisfy h(r) I r(1 - ca) + 1-e20"
Definition 3.11. For 2 0, the Gamma function is T(2) f - è 'dt, the lower incomplete Gamma function is 72, fe" t- dt, and the upper incomplete Gamma
2
function is [(2 = T(2) (2,
for all r < 1-re
Lemma 3.12. For r > ( ||ll|2 S = I(d)
/d).//o)
In summary, if we define (((r) as
The preceding results yield the following upper bound.
((1 eσ) + 1-530²
i > 1-e0
((())
Note that the analytic Gaussian mechanism (Balle & Wang, 2018) depends similarly on the standard Gaussian CDF.
2r
if r < 1-r0
4

---

Approximate Differential Privacy of the & Mechanism
Lemma 3.13. Suppose Assumption 3.4 holds. Let vı < Tn, where 1-ea_ Then, for y (0).
The second case the same argument Lemma 3.3.
Lemma 3.15. If S and d P Py~(()) [y V exp [ =])
then
(d,r r(d)
P PlyE
Proef. M11) has the same noise density the Laplace mechanism Lap (1, o), and /// e1 - lyl 2 oe if and only
(dd - -(d, Mr.) -
((d)
if y 5 - -oe). For < 1, the Lap (1, CDF F(z)
1=1
zYz exp
so by 1 - dE 2 0, F ( y V]
[(d, on) M((nn))
----- +.
2 exp
I(d)
We therefore work under Assumption 3.4 for the rest of this section. The remaining analysis reasons about specific spheres 5R,1-
Proof. The first term is the mass placed on the ball lying entirely in the high privacy loss region (Corollary 3.7 and Lemma 3.12); the second term is a (left) Riemann sum that upper bounds the mass placed on the high privacy loss region between balls of radius rı and In, (Lemma 3.9, Lemma 3.12, and Lemma 3.10); and the last is up- per bound on the mass placed on the high privacy loss region outside the ball of radius Tn,-- More specifically, is a Riemann sum in which the jth approximating rectangle has base length as the jth interval on the grid 0, /ad.r//)) ((d.Rn./o) o0 and height Fry))(r)) D [(d]
Definition 3.16. For R > O, define UR to be the fraction of SR,1 contained in V.
We start by identifying when UR = 0. Lemma 3.17. IfO < R < Itea 2
then UR = O.
Proof. Shorthand T = sO for neatness. By Corollary 3.7, Fr,Mer) = 1 for r I 2
1-r Let 1ı = 1-r denote the largest radius such that Fr,) the point with the largest e1 e1-coordinate e--coordinate for < r S rı. For > r1, the point with the largest 61 coordinate in S,,S, has e1 ccoordiinte -r + ((r) = -r + 1-+² which is monotonically de- creasing as r increases. Overall, the point with the largest e -c-oordiinate V n SS,o is increasing for 0 r S rı and decreasing for r Fl, so ri the maximum e -coordinate of this point over all radii.
1. This shows that
I(d)
V S, has
Algorithm provides overall upper bound pseudocode.
Algorithm 1 Terml UpperBound
2
1: Input: Dimension d; scale parameter a; privacy param- eter e; largest radius r"; number of radii nt
2: if o >> 1/E then
3: Return (Lemma 3.2)
4: end if
It follows that 0 < R < 1 implies Sn,1 O Sr.0 0 for all r > 0, and since V C UrER+Sr.o we get UR = 0.
5: d then
6:
Return 1 exp ( [s 2] (Lemma 3.3)
7: end if
It remains to handle the large R case. We will show that, as was the case in the upper bound analysis, each Sn,1 nV is spherical cap on SR,1- The first result proves that SR, n V has this form. This result not technically necessary for the rest of the argument, but it explains why we attempt to solve for SR, O V cap later.
8: Define 11 <- 1-sa In, r", and T2:..., Pn, regu-
larly spaced between 1n and In. Return upper bound from Lemma 3.13
9:
3.1.2. SECOND TERM LOWER BOUND
Lemma 3.18. For R 20 SR,1 n V is spherical cap $ SR,
It remains to lower bound P. M()) [eM,x(.(V)) < -e]. By the same logic used to derive Equation (2), we rewrite it as
['x(x) fx (v)
Proof. Shorthand 7 = EG. Recall from Lemma 3.2 that V is the convex hull of the -ej facing component a hyperboloid with foci 0 and e₁ and with constant difference т. To see why SR, O V is spherical cap, observe that both the hyperboloid bounded region V and SR,1 are symmetric around é1, so their intersection must be symmetric around ej as well. Let Pe,,, denote projection onto span U1, U2). Then (V) Par.es (SR,1) is a 1-dimensional spherical cap of some height H in Per.ez (SR,)). Since V SR,1 is symmetric around 61, the previous sentence also holds if we
P Py)M()
In
1 (lly eıll2 11all2) 26
= =P)~M(1)
The level sets of (1) are spheres centered at e1- As in the upper bound analysis, there are a few simple cases. The first follows from the same reasoning used for Lemma 3.2. Corollary 3.14. If 2 1. then Pyma(() [y V] = O.
e:
5

---

Approximate Differential Privacy of the & Mechanism
replace Pe Per.ez with Per,e for any v orthogonal to e1. Thus VnSk11 = Per n (S),)(Snn) = SRI,H- D
interval on the grid
2(d.R./o) [(d) ... I(4) 00 and has
7(d. Rug /a)
height (())) The proof of the following result uses
similar logic as the proof of Lemma 3.13.
It remains identify the H referenced in Lemma 3.18. To do so, we start with an arbitrary y SR,1 and solve for an 61 coordinate X such that y1 S X if and only if y1 S --llll + h(lly/l2) (Lemma 3.6). The bulk of the proof beyond this idea is algebraic manipulation, so it appears in Appendix A.2.
Lemma 3.21. Suppose Assumption 3.4 holds. Let R1 < Rax where R1 -22 Thee for y ~~ M11),
A A--1
2d, (dd,R,+1 1/)1/0) (dd, F(n.
P
I(d)
r(d, Rnnlo)
Lemma 3.19. Define X = 1 R - and (R) =
+
F (Bonn)
2 R- - 1 1+ X. Then cap HR,1,H(M) = SR,I
I(d)
where we reused the definition of F from Definition 3.8.
Lemma 3.20. R Ltea, then Un is monotone increas- ing in R.
2
Algorithm 2 provides overall lower bound pseudocode.
Algorithm Term2LowerBound
Proof. Shorthand = EG. Lemma 3.17 established that
Un 0 for R < 1+r so it remains to show that Un is
1: Input: Dimension d; scale parameter or; privacy param- eter E; largest radius R"; number of radii na
3 1+r. The proof of Lemma 3.19
increasing in R for Rt 2
2
established that (R) E [ò, Rj, so we apply Lemma 3.9 2: if o 2 1/s then
to get that (R,1,H(R) occupies a fraction of SR,1 given by (22 (())))))) ( 2 2). By the same logic used in the proof of Lemma 10, we can show that Un is monotone
Return 0 (Corollary 3.14)
end if
5: if d -8=1 then
6: Return 1/2 exp (1 [-s 1 (Lemma 3.15)
increasing by verifying that the expression in the / subscript nonnegative and increasing in R.
7: end if
8: Define R₁ + L+c RAR <- R", and Rg,..., R
2
The first condition follows from the aforementioned result H (R) < R. For the second condition.
regularly spaced between R1 and Rnn
Return lower bound from Lemma 3.21
2 1+ X]
R
1 X|2
R²
3.1.3. OVERALL ALGORITHM
R²
1 + 2X-
-X2
Algorithm upper bounds the first term in the inequality in Lemma 2.3 and Algorithm lower bounds the second term. This upper bounds the LHS of the inequality, so if it is at most 8, then the mechanism is (s, 0D-D.
R²
X 1
2
R
x2 - 2 - 2
The last step is choosing R.., r", nR. and R" Our experi- ments suggests that setting n, = nn = 1000 yields a rea- sonably tight approximation for < 100 (see Section 4.1); larger values should only be tighter, at the cost of speed. We choose f" using Lemma 3.12 so P Py)M(()) [lly/la r*] 1 in the context of Lemma 3.13, we use M(r,,) to upper bound the cap fraction for all Sr.0 with r 2 Tn,, so we choose r* to make the effect of this approximation negligible. By the same logic, we use R r*.
2R
We wanted to prove that this expression is increasing in R. so we show that the second term is decreasing in R. Taking its derivative with respect to R yields
2T
2R( (T)) 2(72 2- R 1)
2
2R
4R²
2- 27 R - 1
1 - 72
Algorithm 3 collects the entire process into pseudocode.
R
21²
3.2. Parallel Sampler
Because R. > 0 and 0 < < 1, the numerator of the first term is negative, and the remaining terms are positive, the entire quantity is negative.
The sampler described here is simple consequence of Lemma 2.4 and well-known statistical facts, and similar samplers have appeared for related mechanisms (Yu et al., 2014; Steinke & Ullman, 2016). We collect the relevant information here, with proofs in Appendix A.3 for com- pleteness.
Since we want to lower bound the mass on these UR. we use Lemma 3.12 and employ left Riemann sum in which the jth approximating rectangle has base length as the jth
6

---

Approximate Differential Privacy of the & Mcchanism
Algorithm 3 CheckApproximmleeDP
analysis of Section 3, Equation (3) is equivalent
1: Input: Dimension d: scale parameter o; privacy param-
_ (ller vll2- - -1vll2)) 2 e
eters E, 6; numbers of radii ny, DR
IP (0)
2: Compute r* such that Py)a(()) [llvila > rd]
6
100
(Lemma 3.12)
e -e-Pywari (lle - yll2 - l1vll2) 2 S 6.
3: Ti < Term I Upppeuuudddddddd.ss r,r"", n.)
4: T- < Temm2LowerBound (d, (,, ,7R)
5: Return (T1 - T $ 6)
We can estimate the value of this expression by drawing n samples from (0) and n samples from M1), counting the fraction e₁ satisfying the first inequality and the fraction 22 satisfying the second inequality, and then compuring C1 - E C2. Binary searching over a to find the smallest value where this computation is upper bounded by å leads to an empirical estimate of the minimum o yielding a (1, 0.01)- DP lg mechanism.
By Lemma 2.4, sample rz where Gamma (d + o, and ~u By. In a parallel setting, suppose we have worker for each of d coordinates and central manager. We first sampler. r.
Lemma 3.22. Let U1....,UAR ridd 1) be uni- form random samples. Then -o -it log(U:) Gamma (d + 1,
dd+1
The second method computes its using the analysis of Sec- tion 3. As shown in Figure 4, our algorithm closely tracks the empirical values. This provides empirical evidence that the resulting privacy analysis is both sound and (with the chosen ny = n 1000 and range for d) tight.
By Lemma 3.22, each worker i can sample log(U:), and the manager can add the combined sum to their own sample and scale the result by- -a to obtain r. It remains to sample z. Lemma 3.23. Let XI,..., Xd iid NO..1). 1), and ler Y 1)) be uniform sample from [0, Then yl/d. (a) is a uniform sample from Bq.. VEL X?
empirical privacy analysis tightness
1.0
empirical
0.9
algorithmic
0.8
To apply Lemma 3.23, each worker samples a standard Gaussian and reports its square in the same combine used
parameter
0.6
to compute r in Lemma 3.22. The manager samples Y and
0.5
publishes it along with r and the sum of squares. At this point, each worker can compute their coordinate of r2.
0.4
0.3
4. Experiments
20
40
60 dimension d
80
100
This section discusses experiments evaluating the tightness of our privacy analysis (Section 4.1) ) as well as the E, mech- anism's 's error (Section 4.2) and speed (Section 4.3). All experiments use the f2 mechanism with nt, = nn = 1000. Experiment code may be found on Github (Google, 2025).
Figure 4. A comparison of empirical (dotted) and algorithmic (solid) estimates of privacy loss. At each d. the empirical method uses = 1000/6 = 10 samples.
4.1. Privacy
4.2. Error
Our first experiments attempt to measure the tightness of our privacy analysis. To do so, we compare two methods for estimating P [ 2 c] - T eP [fM,xi,x -e], the quantity that must be upper bounded by 8 for M to satisfy (E, 6)-DP (Lemma 2.3).
We first derive some basic results about the mean squared la error of the Laplace, l2. and Gaussian mechanisms used in experiments. The Laplace and &g results are corol- laries of the following lemma. The lemma is extension of a previous result about the mean squared & norm of a sample from an bp ball (Joseph et al., 2025) and is proved in Appendix A.4.
We fix E = 1, 5 = 0.01, and vary d = 1,,,.... 100. At each d, the first method empirically estimates the smallest such that
Lemma 4.1. The mean squared &o error of the d- dimensional E, mechanism with parameter a is
IP [fM.X,x 2 1] e -PP [f S -1] S 5, (3)
T (())((+))
where M is the fg mechanism with parameter o, and (X) centered at 0 while M(X) is centered at 1. By the
(do)(d+1)
7

---

Approximate Differential Privacy of the &g Mechanism
Since d-dimensional statistic with & sensitivity has & sensitivity vd, substituting p 1 and parameter v into Lemma 4.1 yields the following result for the Laplace mechanism.
lg computation is binary search where each evaluation iterates over n,, + nt 2000 radii. Nonetheless, we note that the l2 computation still runs in R 0.1 seconds, this time does not increase with d, and the calculation only needs to be performed once for each setting of (e, 6, d).
Corollary 4.2. The Laplace mechanism with parameter / has mean squared l2 error 2d o².
a computation time
The le mechanism uses p- 2 and parameter Corollary 4.3. The l mechanism with parameter has mean squared l2 error d(d++ 1 1)o2.
10-1
1072
similar result for the Gaussian mechanism is easy to prove directly (see Appendix A.4 for proof). Lemma 4.4. The Gaussian mechanism with parameter o has mean squared lg ervor do?.
time
10-3
laplace gaussian
10 9
10
For range of d, we solve for the smallest possible for each mechanism to achieve (e, 6DP and plot the mean squared &g error according to the preceding results. The Laplace mechanism uses a = (s + 8)², the Gaussian mechanism binary searches over a as described by Balle & Wang (2018), 8), and the l2 mechanism binary searches over using the algorithms from Section 3. Throughout, binary searches use tolerance 0.001 and we use (1, -DDD..
40
60 dimension d
8D
100
Figure 5. A plot of time in seconds to compute the minimum to achieve (1, 10 11,,10---D- 3J-DP. The & mechanism line jumps after 1 because that case uses Lemma 3.3 instcad of approximating the spherical cap region.
The time to draw 1000 mechanism samples is less varied (Figure 6). The & mechanism is again slowest, but it is within a factor of two of the other mechanisms, and no mechanism takes more than R 0.01 seconds.
This produces the left plot in Figure in the introduction. The Laplace mechanism obtains lower error than the ana- lytic Gaussian mechanism for small d, the analytic Gaussian mechanism obtains lower error than the Laplace mechanism for larger d, and the & mechanism dominates both. The gap between the & mechanism and the better of the Laplace mechanism and analytic Gaussian mechanism is 0 at d = 1 (when the Laplace and l2 mechanism are identical) and peaks at 50% at = 7 before gradually shrinking, to 5% at d= 100 and < 1% at d = 500 (not pictured).
sampling time
0.010
laplace gaussian
0.008
f2
0.006
0.004
Analogous plots for a high-privacy regime of 10-7- DP and low-privacy regime of (10, 10010-0 3)-D are essen-
0.002
tially the same.
0.000
4.3. Speed
dim ension d
The last set of experiments evaluates the speed of the & mechanism, as executed on typical personal computer. This runtime is split into two operations: the time to com- pute a and the time to sample the mechanism.
Figure 6. This plot uses the same setup Figure 5 but records sampling time.
The largest gap appears in the time to compute a (Figure 5). The Laplace computation is z 100x faster than the Gaussian computation, which is 100x faster than the la computa- tion. This may be expected, as the Laplace computation is single arithmetic expression, the Gaussian computation is binary search over the standard normal CDF, and the
Note that the smallest possible for which the Laplace mech- anism is (e, 8)-DP is provably negligibly smaller than the one used here. See Appendix A.4 for details.
8

---

Approximate Differential Privacy of the & Mechanism
Impact Statement
Ganesh, A. and Zhao, Privately answering counting
queries with generalized gaussian mechanisms. Founda- tions of Responsible Computing (FORC), 2021.
This paper presents work whose goal to advance the field of Machine Learning. There are many potential societal consequences of our work, none which feel must be specifically highlighted here.
Google.
https://github.c. htt.r//eeearcceooooeeeeeeeeeeeee master/dp_12, 2025.
dp.12.
References
Hardt, M. and Talwar, K. On the geometry of differential pri- vacy. In Symposium on the Theory of Computing (STOC), 2010.
Abadi, M., Chu, A., Goodfellow, I., McMahan, H. B., Mironov, I., Talwar, K., and Zhang, L. Deep learning with differential privacy. In Conference on Computer and Communications Security (CCS), 2016.
Joseph, M., Ribero, M., and Yu, A. Privately Counting Partially Ordered Data. In International Conference Learning Representations (ICLR), 2025.
Asoodeh, S., Liao, J., Calmon, F. P., Kosut, O., and Sankar, L. A better bound gives hundred rounds: Enhanced privacy guarantees via f-divergences. In International Symposimm on Information Theory (ISIT), 2020.
Kifer, D., Smith, A., and Thakurta, A. Private Convex Empirical Risk Minimization and High-dimensional Re- gression. In Conference on Learning Theory (COLT), 2012.
Balle, B. and Wang, Y.-.. Improving the gaussian mecha- nism for differential privacy: Analytical calibration and optimal denoising. In International Conference on Ma- chine Learning (ICMI.), 2018
Li, C., Miklau, G., Hay, M., McGregor, A., and Rastogi, V. The matrix mechanism: optimizing linear counting queries under differential privacy. The VLDB Journal, 2015.
Bun, M. and Steinke, T. Concentrated differential privacy: Simplifications, extensions, and lower bounds. In Theory of Cryptography Conference (TCC), 2016.
Li. S. Concise formulas for the area and volume of hyper- spherical cap. Asian Journal of Mathematics & Statistics, 2010.
Canonne, C. L., Kamath, G., and Steinke, T. The discrete gaussian for differential privacy. Neural Information Processing Systems (NeurIPS), 2020.
McKenna, R., Miklau, G., Hay, M., and Machanavajjhala, A. Optimizing Error of Biggh-Dimnsional Statistical Queries under Differential Privacy. The VLDB Journal, 2018.
Cesar, M. and Rogers, R. Bounding, concentrating, and truncating: Unifying privacy loss composition for data analytics. Algorithmic Learning Theory (ALT), 2021.
McSherry, F. and Talwar, K. Mechanism design via dif- ferential privacy. In Foundations of Computer Science (FOCS),200)
Chan, T.-H. H., Shi, E., and Song, D. Private and continual release of statistics. Transactions on Information and System Security (TISSEC), 2011.
Nikolov, A. Private query release via the johnson- lindenstrauss transform. In Symposium on Discrete Algo- rithms (SODA), 2023.
Chaudhuri, K., Monteleoni, C., and Sarwate, A. D. Differ- entially private empirical risk minimization. Journal of Machine Learning Research (JMLR), 2011.
Nikolov, A. and Tang, H. Gaussian Noise is Nearly Instance Optimal for Private Unbiased Mean Estimation. arXiv preprint arXiv:2301.33850 2023.
Dwork, C., McSherry, F., Nissim, K., and Smith, A. Cal- ibrating noise to sensitivity in private data analysis. In Theory of Cryptography Conference (TCC), 2006.
Nikolov, A., Talwar, K., and Zhang, L. The geometry of differential privacy: the sparse and approximate cases. In Symposium on the Theory of Computing (STOC), 2013.
Dwork, C., Naor, M., Pitassi, T., and Rothblum, G. N. Differ- ential privacy under continual observation. In Symposium on the Theory of Computing (STOC), 2010.
SciPy, scipy.special betainc, 2024.
Edmonds, A., Nikolov, A., and Ullman, J. The power of factorization mechanisms in local and central differen- tial privacy. In Symposium on the Theory of Computing (STOC), 2020.
Song, S., Chaudhuri, K., and Sarwate, A. D. Stochastic gradient descent with differentially private updates. In Global Conference on Information and Signal Processing (GlobalSIP), 2013.

---

Approximate Differential Privacy of the & Mechanism
Steinke, T. and Ullman, J. Between pure and approximate differential privacy. Journal of Privacy and Confidential- it,, 2016.
Yu, F., Rybar, M., Uhler, C., and Fienberg. S. E. Differentially-rrivate logistic regression for detecting multiple-SNP association in GWAS databases. In Privacy in Statistical Databases, 2014.
7hu, Y. Dong. J., and Wang, Y.-.. Optimal accounting of differential privacy via characteristic function. Artifi- cial Intelligence and Statistics (AISTATS), 2022.
10

---

Approximate Differential Privacy of the & Mechanism
A. Appendix
A.I. Omitted Proofs From Upper Bound
Claim 3.6.1. |y - e1ll2 - llvl2 decreases as decreases.
Proof. By the law of cosines,
1y e1ll2 = V Ilyll || l1 2 20
/ r2 + 2r cos(
so as y moves clockwise through St,0 n from =1 to 61. A decreases from to cos(#) grows from -1 to and lyy ei || shrinks from + to -r- 1.. Since ||y|| remains constant, ||y l| ||v||2 decreases 0 decreases. The
same conclusion holds if we choose y in the lower half plane and consider the analogous counterelockwise angle.
Claim 3.6.2. (1pp
eull2 [|p|2)) equivalent h(r) r(1 50) + 1-630²
Proof.
11 =V - h(r)²
+
= + 1 2h(r)
and
1
(lp 112 - (|p|12)
(V + 2h(r) r)
(ge r)3 =(r + 1)2 -2h(r)
2h(r) =2r + -(aE)² 2ra8
1 0²0²
h(r) =r(1 =0) +
2
r(1- Claim 3.6.3. - =a) + م= 2
E [0, 2r] if and only ifr 2 1-sa
Proof. The upper constraint of r(1 - 50) 1-e3a² 2r is equivalent to 1-sa follows
0²
r(1 - (0)-0) +
<
2r
2
- 202
< r(1 + +80
2
50
<r.
2
The lower constraint of r(1 sa) + 1-c2a² 2 0 is satisfied for any since 1 ca 2 0 implies
1 1-
-EO) r+ + ca
r(1 -1--0) 20) + 2
=(1 (11 -
2 0.
2
Lemma 3.12. For > 0, P My-M()) Illella < r] r(d.r/o) [(d)

---

Approximate Differential Privacy of the & Mechanism
Proof. The density for Y is f'w) x exp (-1lvll2/o), we compute the distribution's 's normalization factor Z. We two facts. First, a (d - -p-shee i.e., sphere in R with radius has surface area r(d/2) with s/o.
2x s Second, by z-substitution
% s/a ga d ds 0000 e e_m.n" dddu r(d)o"
since [==) - So 1d We compute the integral Z using hyperspherical coordinates 8, 0,02,.,,00- where & 2 01 [0, 2m), and 0g =0 for S s Let
V(0,,...0a-1 = sin find-2(0 sin= sin sind-3(22)) sin).
be the angle dependent terms of the hyperspherical volume element. Then
Z
e s/a 5/agd (00 0,0s
2/12
a-1o 0s
e
T(d/2)
200
T(d/2) [dd).
This gives
1 2md/2
Py ||ll|| S r| = 7 T(d/2)
e//0 c-
1 2n1/
= Z T(d/2) (ddT///
7ddr//o)
T(d)
Lemma 3.10. Frader monotone decreasing in r.
Proof. Shorthand T Ea. By Corollary 3.7, Fr,h()) for S h((r) r(1 (1-1) 1--". Case 1: < 2r suffices to show that Fr22-h(r) increases with r. By Lemma 3.9,
1-r 2
Suppose
> 1-r 2
Then by Lemma 3.6,
1- Then M()) > and Fr,ne)) = - F, (rr)) Since we want to prove that F, Fr, decreases with it
d- 1
Fr.2--(r)) 112)
2 2 (-22
We expand the subscript for I
2r(2r h(r)) (2r (2r-h(r)) h(r))² 4r (2-rrr((r) (4r² 4rh(r) + h(r)²)
n2
y22
2rh(r) - 1((r)2
(4)
y2
Since h(r) E [0, 2r] (Lemma 3.6), 2rh(r) h(r)2 2 Because Iz (a, b) increases with x for x 2 0, enough to show
that (2rh(r) h(r)))/rr /r2 increases with r. Expanding yields
1²(1 7)2 r(1 7) 72) + (1-73y3
2rh(r) - h(r)2 2r(1 7) (1- 72)
72
22
12

---

Approximate Differential Privacy of the & Mechanism
We drop terms that don't depend on r to get
1 1- 1-T² +²
(1 - r) - =2)
(1 -1-7" (1-
J
(1
(1 (1-
4r2
4r
Differentiating the second term with respect to r gives
1-2 and this is positive exactly when r < 2r
1-r² 27
Case 2:
1-r2 Then h()) S r, and
2r
1 Frr((r) =((arb(r)-MG)P9)>
d d-1
2
By similar logic, it suffices to show that (2rh(r) - h(r)))/r²² is nonincreasing in r for r 2 1-r². analysis of the previous case.
2r This follows from the
A.2. Omitted Proofs From Lower Bound
Lemma 3.19. Define X = [+(sa)² R and (RR) = R 1 1 X. Then cap SR.I.(()) SR,1 nv.
Proof. Shorthand 7 = Eα for neatness. To verify the claim, we start with an arbitrary y E SR,1 and attempt to determine a cutoff X E IR such that y E V iff y1 I X. For any two points y: y/ E SR,1 such that y1 = ví- is true that y E V iff y/ E since V is spherically symmetric around e1. If y' - MI11 + v for some orthogonal to et, then by SR. 's spherical symmetry around e₁, the point y = e + |elez is also in SR,1. Therefore, our goal is to find the minimum cutoff X for the point y = (y1, 1/2, 0, ..., 0) such that y E V iff 91 S X.
We know y E S,r00 for some r' > 0. Since vi + vI r22 and y E SR,1 implies (11 1)2 + vI R2, then
combining these yields r' = / R2 2y1 1. Thus we have y V if and only if y1 S --r + h(r'). By Lemma 3.6,
-r' + h(r')==))))))r)))) min( minn--rr'+ 1-- 2 2r'). We have -rr L-r² -T R + 2y + 1-s" so we solve for the largest
X where X < min(- 2X - 1 1-+² 2 2V R -x-1x) 1).
Solving for X under the first constraint yields
1 72
2
X
2 27 -1
--227 + - 27 + 47 20
X² X(1 72)
4
7 + 27 + ++ 472 R²
X X(1 + +²²) +
0.
(5)
The roots of the LHS are given by
X 1 1+ + (1 + -
47 R2)
1 1 +² + 2TR
Let 11 = 1+-2 and x2 = 420R As the LHS of Equation (5) is a convex parabola, the inequality is satisfied on the
intervals ( (-00, U [x2, oo). But the first constraint on X also implies the weaker inequality X < -بب² so X & [x2, oo). Then 21 is the largest value that satisfies the first constraint.
For any X (2), we have X - R 22 II -يا =
2X
2V +2X 1).
So if we can show that 21 < 2 R -P=+2 2x - I, then I1 will indeed be the desired cutoff. We actually prove a stronger inequality
31 5 / R22 2x1
1 1+ -- -
< R-
2
(1 (1+7)² < 2R + +T)
1 <R R
2
13

---

Approximate Differential Privacy of the & Mechanism
which follows from our starting assumption on R. So X height
-+r2-2rR is the desired cutoff. This leads a cap on SR,1 1 of
= - - 1 + T² 2T R R(1 -)
1 1-7²
2
The last step verifying that this is a valid height lying [0, 2R). The lower bound follows from R(1 - 7) 2 1- rearranging into the starting assumption R _+I We prove stronger upper bound of R by rearranging
R(1-7) 1 7- S
R
2
72
STR
2
which uses 0 < 7 < 1 and R > O.
A.3. Omitted Proofs From Sampler
Lemma 3.22. Let UI...., U441 Mid (0, 1) be uniform random samples. Then - Ex=1 log(U;) Gamma (d + 1, 1,
Proof. We first show that lolllol (0, 1)) ~ Expo (1), exponential random variable. Let f be the CDF of Expo (1). Then Pff (v) I t| P'U < f()) ftt) so f (U) ~ Expo (1). Since (t) - log(1 f) for 0 s t S 1, and
U ~ (1 - U). we get log(U) ~ Expo (1).
Note that Expo (1) corresponds to a random variable that measures the time required for the first arrival from a Poisson process with rate Moreover, Gamma (d + 1.)) ~ oGamma (d 1) and Gamma (d + 1, corresponds a random variable that measures the time of the (d + 1)th arrival of Poisson process with rate 1. The random variable of the (d 1)th arrival is equal to the sum of the random variables of interarrival times for the first (d 1) arrivals. Since Poisson process has stationary increments, each of these interarrival times are i.idd as Expo (1). It follows that Gamma (d + 1, Eit1 Eg Ei+l log(U4) where E, Expo (1).
Lemma 3.23. Let XI,.... ................................ Xa rid (0, 1), and let Y (0, 1) be uniform sample from [0, 1]. Then 1/dd (X1 is a uniform sample from By.
VVA X?
Proof. The term (N is a normalized draw from a d-dimensional multivariate Gaussian with an identity covariance
matrix. As this distribution is spherically symmetric, normalizing the draw to have unit length produces a uniform draw from the unit sphere. Define the function f to be the CDF of the random variable of the &g norm of uniform sample from B Then f(r) ,d We show that is also the CDF of y1/d, We have P|y1/d (P 1)2/d s r] = (0, < r rd and the lemma follows.
A.4. Omitted Proofs From Experiments
The following result about the expected squared & norm of E, balls will be useful. Lemma A.1 (Joseph et al., 2025)). Let (X) denote the expected squared Eg norm of a uniform sample from X, and let r BB denote the d-dimensional Ep bull of radius Then (r( = =
3d
2+2
Lemma 4.1. The mean squared l2 error of the d-dimensional Ep mechanism with parameter a is
(
(do) (d+))
Proof. Consider the mechanism releasing noisy version of T(X) = O. Call this mechanism Mf. Recall from Lemma 2.4 that can sample it by sampling Gamma (d + 1, o), sampling Bdd and outputting rz. The distribution Gamma (d + 1, 1, has density
de a/a
f(x) [(d 1)o4+1
(6)
14

---

Approximate Differential Privacy of the & Mechanism
SO
L
B B
[19112]
(r
r
d
3d
m (())((
dr
I 1)od+T
3
d d+2
r rgre)
3d
, e -r/ dr
3T + 1)od+1
d+
(())))))
3d
r(dd + 3)3 d+3
3r + 1)odt1
d (
r (2))
(())))))
= (d
(()))(
p
Lemma 4.4. The Gaussian mechanism with parameter has mean squared Eg error do
Proof. Denote the mechanism by No. Then by linearity of expectation and the fact that the Gaussian mechanism has independent Gaussian marginals,
E Ey-N.
[1
E
= dI' dIE=~((O,07) [2]]
= do²
where the last equality used
E2-N(o. [>-] = Var(2)
+ E [2] = o².
The following result provides evidence that, with reasonable parameters, approximate DP does yield meaningful utility improvements over pure DP for the Laplace mechanism. A result like this is likely folklore, but include it here for completeness.
Lemma A.2. The Laplace mechanism with parameter < 1/s does not satisfy (e < 21n(1 6) + J.
Proof. Let T(X) = 0 and let T(X') E1. Then [T[(X) T(X')ll 1, and
fx(
P Py~M())
In
2 8
= P ( llly - ei - ||y|| 2 σs] = P())(()) |M - 1| 1|-|y11 2 as).
Tx (v)
Mechanism M equivalent the spherical Laplace distribution where each dimension is drawn from Lap This distribution has CDF F(x) in } oε), the probability of drawing such y
i/2 exp(-z/o) for æ 2 0. Condition 1y1 18 2 or holds if and only
1
1 1
06) = =1 exp 2
1 1
exp -
2
1 2
Therefore P [fM.X.X' 2 = = exp
We now analyze P [LM,X',X S -e). Because (M.X'X = log(/x (x))fx())) = -1v1l
1y/1 - 1(), we get
P PlMM,'' S -e] PymM(1)) (lee 1| - 1/1 2 oel
15

---

Approximate Differential Privacy of the & Mechanism
where (1) denotes the d-dimensional Laplace mechanism centered 61. By the same logic used above, 11/1 1|-1 2 if and only if yn (1 oe). For y M(1), this event has the same probability yí S [1 oe) 1 2 σe) when y' M Furthermore, Lap (a) has CDF F(x) exp(x/o) for 0. Thus P [(Mx'' S - exp ( - =]).
Combining these results and applying + x S e yields
c- 1
1
1
))
PlM,x, 2 2 - EP (
2 exp
c
exp
2
2
EE
exp
By Lemma 2.3, this last quantity must be upper bounded by for M to (e,6)-DP. Rearranging yields the expression in the claim.
16


Reviews:
[{"review_id": "oM4ldRscNb", "reviewer": "Reviewer_sZuF", "summary": "The authors consider a specific instantiation of the K-norm mechanism using an L2 norm.  They establish conditions for achieving approximate DP as opposed to pure DP as was done in the original K-norm paper. Theory and experiments are provided.", "questions": "", "limitations": "", "rating": 1, "confidence": null, "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": "Thanks for the review!\n\n> I checked some of the early lemmas and the results seemed sound. However, the communication of the theory I found to be unpleasant. I'm not sure I've ever seen so many lemmas without a single theorem. The bulk of the paper reads more like an appendix … [t]he theory of the paper is also very unpleasant to read. Major theorems should be organized and presented as the key results. Especially novel lemmas certainly can as well, but the rest should be in the appendix.\n\nThe paper's current presentation attempts to highlight the main conceptual ideas of the privacy analysis in the main body while deferring most of the calculations to the appendix. We chose this presentation because direct approximate DP analyses of additive noise mechanisms are rare in the existing literature, and we believe the form of the analysis is interesting. Since the overall analysis has a single end goal (an approximate DP guarantee), describing the constituent results as lemmas seemed appropriate. If it seems helpful, we can add an overall privacy theorem.\n\n> The related work section was quite lacking. 4 papers are mentioned in field that has existed for 20 years. I understand that the authors are working with approximate DP, where as a lot of related methods work on pure, but the authors should still do a better job placing their work within the context of the broader literature.\n\nTo the best of our knowledge, this section discusses all of the existing work on the $\\ell_2$ mechanism, and the Laplace and Analytical Gaussian Mechanisms discussed elsewhere are the most relevant baselines. Do you have other references in mind?\n\n> While the mechanism looks like it is wrapped up in an exponential type mechanism, it can also be viewed as an additive perturbation where $\\tilde T(X) = T(X) + Z$ where $Z$ is distributed as an \"l2\" random variable. In that sense, there are a lot of options available for pure/approximate DP that can be discussed.\n\nThe suggested additive noise perspective is also valid (and appears in the discussion of the $K$-norm mechanism in Lemma 2.4). We agree that other additive noise mechanisms exist, and as mentioned above, to the best of our knowledge the most common mechanisms in theory and practice for computing an $\\ell_2$ sensitive statistic are the variants of Laplace and Gaussian noise featured in the paper (though additional references are welcome!).\n\n> In fact, the distribution used in the paper has been viewed as a multivariate version of the Laplace distribution (there are multiple extensions).\n\nCan you elaborate on this? The multivariate Laplace distribution depends on $\\ell_1$ distance to the true statistic, but the $\\ell_2$ mechanism depends on $\\ell_2$ distance. In what sense is the $\\ell_2$ mechanism a multivariate version of the Laplace distribution?\n\n> In general the paper is a very narrow contribution as they study a very specific type of DP for a very specific mechanism that doesn't seem to be used much in the literature.\n\nWe agree that the $\\ell_2$ mechanism is not currently common in the literature, in part because our paper is the first to prove a (nontrivial) approximate DP guarantee for it. As the results in the paper show, this approximate DP analysis enables the $\\ell_2$ mechanism to obtain lower error than the Laplace and Gaussian baselines, which appear in most DP papers. Approximate DP is the most common notion of DP in the literature and in practice. For example, it is the primary definition used in usability studies of DP [1, 2] as well as industry deployments [3, 4, 5]. Can you elaborate on why it might be considered \"a very specific type of DP\"?\n\n[1] https://arxiv.org/abs/2302.11775\n\n[2] https://arxiv.org/abs/2406.12103\n\n[3] https://journalprivacyconfidentiality.org/index.php/jpc/article/view/782\n\n[4] https://arxiv.org/abs/1909.01917\n\n[5] https://arxiv.org/abs/2201.11603", "claims_and_evidence": "Yes, the paper provides both theory and simulations to demonstrate the improvement.", "methods_and_evaluation_criteria": "Yes, both theory and simulations are provided to demonstrate the work.", "theoretical_claims": "I checked some of the early lemmas and the results seemed sound.  However, the communication of the theory I found to be unpleasant.  I'm not sure I've ever seen so many lemmas without a single theorem.  The bulk of the paper reads more like an appendix.", "experimental_designs_or_analyses": "Experiments seemed fine.", "relation_to_broader_scientific_literature": "The related work section was quite lacking.  4 papers are mentioned in field that has existed for 20 years.  I understand that the authors are working with approximate DP, where as a lot of related methods work on pure, but the authors should still do a better job placing their work within the context of the broader literature.", "essential_references_not_discussed": "While the mechanism looks like it is wrapped up in an exponential type mechanism, it can also be viewed as an additive perturbation where $\\tilde T(X) = T(X) + Z$ where $Z$ is distributed as an \"l2\" random variable.  In that sense, there are a lot of options available for pure/approximate DP that can be discussed.  In fact, the distribution used in the paper has been viewed as a multivariate version of the Laplace distribution (there are multiple extensions).", "other_strengths_and_weaknesses": "In general the paper is a very narrow contribution as they study a very specific type of DP for a very specific mechanism that doesn't seem to be used much in the literature.  The theory of the paper is also very unpleasant to read.  Major theorems should be organized and presented as the key results.  Especially novel lemmas certainly can as well, but the rest should be in the appendix.", "other_comments_or_suggestions": "None.", "questions_for_authors": "None.", "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": "", "extra_scores": {}}, {"review_id": "hqYY8MBnG3", "reviewer": "Reviewer_xaZ5", "summary": "The paper studies the L2 mechanism with bounded L2 sensitivity in d dimensions, demonstrating improvements over the Laplace and Gaussian mechanisms under approximate differential privacy. It presents algorithms for computing approximation bounds for privacy loss random variables and introduces a parallel sampler for generating noise from the resulting distribution.\n\n## update after rebuttal\nI will keep my score unchanged.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "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": "Thanks for the review!\n\n> One missing aspect is the composition of the L2 mechanism. The Gaussian mechanism is widely used in DP-SGD due to the availability of numerical composition analysis. To better demonstrate the practicality of the proposed L2 mechanism, its composition must be studied.\n\nWe agree that analyzing composition is the logical next step for studying the $\\ell_2$ mechanism. A basic approach can use existing generic composition results for pure and approximate DP algorithms, but this is unlikely to obtain better error than the Gaussian mechanism beyond a very small number of compositions. Possible alternative approaches include:\n\n1) Investigating advanced composition for mechanisms that satisfy simultaneous (and nontrivial) pure and approximate DP guarantees. For example, at $d=50$, at $\\sigma \\approx 0.5$ the $\\ell_2$ mechanism is both $(1, 10^{-5})$-DP and $\\approx 2$-DP. We are not aware of advanced composition bounds that can take advantage of both guarantees.\n\n2) Analyzing the moment generating function of the privacy loss random variable. Such an analysis could provide better privacy accounting using CDP or RDP or FFT-based privacy accounting. As demonstrated in the paper, even deriving tail bounds for the privacy loss distribution is already involved, but it is possible that some kind of moment analysis can be done.\n\nWe suggest that results in this direction are a good candidate for future work. \n\n> In Figure 1, the L2 mechanism exhibits a similar error to the Gaussian mechanism when d >100. In DP-SGD, where the dimensionality often exceeds 1000, does this imply that the L2 mechanism has comparable error to the Gaussian mechanism? If so, what is the advantage of using the L2 mechanism? It appears that the L2 mechanism achieves lower error for moderate d, but this benefit may not be significant in applications like DP-SGD.\n\nYes, our experiments show that the $\\ell_2$ mechanism's error converges to the Gaussian mechanism's error as $d$ grows, and at $d=1000$, the gap is essentially 0 (a short discussion of intuition for this effect appears in our response to Reviewer Vdrp). We therefore agree that the $\\ell_2$ mechanism does not meaningfully improve over the Gaussian mechanism in very high-dimensional settings. However, we suggest that the moderate-$d$ setting covers many practical problems and is therefore still worth studying. If desired, we can add a short discussion highlighting this guidance for the dimension ranges where $\\ell_2$ noise is most useful.\n\n> A related concern arises in Figure 6, where the sampling process for the L2 mechanism appears less stable. If d >1000, will the sampling time increase compared to the Gaussian mechanism? If so, this could be a notable limitation, as the additional computational overhead may not be negligible.\n\nThe $\\ell_2$ mechanism is a constant factor (in $d$) slower in our implementation. However, we note that both the $\\ell_2$ and Gaussian mechanism sampling algorithms are parallelizable, and the parallelized runtime is independent of $d$. The experiments provided here do not attempt this parallelization, which is why their runtime increases with $d$. As described in Section 3.2, in a parallel setting, the $\\ell_2$ sampler adds one more map and combine step over the Gaussian sampler. In a parallelized system, we expect that this cost is mild.", "claims_and_evidence": "The approximation bounds for privacy loss random variables are novel, providing new results for achieving differential privacy in d dimensions.", "methods_and_evaluation_criteria": "The experiment support the claims. The sampling is efficient.", "theoretical_claims": "I checked most of the proofs in the main paper, they make sense to me.", "experimental_designs_or_analyses": "The experiment shows the proposed mechanism is tight and can be efficient.", "relation_to_broader_scientific_literature": "The paper reduces the error of dp mechanism in d dimension case.", "essential_references_not_discussed": "No.", "other_strengths_and_weaknesses": "One missing aspect is the composition of the L2 mechanism. The Gaussian mechanism is widely used in DP-SGD due to the availability of numerical composition analysis. To better demonstrate the practicality of the proposed L2 mechanism, its composition must be studied.", "other_comments_or_suggestions": "No.", "questions_for_authors": "In Figure 1, the L2 mechanism exhibits a similar error to the Gaussian mechanism when d >100. In DP-SGD, where the dimensionality often exceeds 1000, does this imply that the L2 mechanism has comparable error to the Gaussian mechanism? If so, what is the advantage of using the L2 mechanism? It appears that the L2 mechanism achieves lower error for moderate d, but this benefit may not be significant in applications like DP-SGD.\n\nA related concern arises in Figure 6, where the sampling process for the L2 mechanism appears less stable. If d >1000, will the sampling time increase compared to the Gaussian mechanism? If so, this could be a notable limitation, as the additional computational overhead may not be negligible.", "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": "", "extra_scores": {}}, {"review_id": "UTaoDO5LMo", "reviewer": "Reviewer_Vdrp", "summary": "This paper studies the $\\ell_2$ mechanism for releasing a $d$-dimensional statistic with bounded $\\ell_2$ sensitivity under approximate differential privacy.\nTo release a $d$-dimensional statistic $T(x)$, the $\\ell_2$ mechanism samples an output $f_X(y)\\propto \\exp(-\\lVert y - T(x)\\rVert_2 / \\sigma)$ for suitable $\\sigma$.\nThis can be compared to the Gaussian mechanism which outputs $f_X(y)\\propto \\exp(-[\\lVert y - T(x)\\rVert_2 / \\sigma]^2)$, i.e., where the norm comes in squared.\nThe $\\ell_2$ mechanism can be viewed as an instantiation of the $K$-norm mechanism (Hardt & Talwar, 2010), and so it is known to satisfy $\\frac{1}{\\sigma}$-DP.\nIts approximate DP properties, however, are not well understood, and exploring these is the main topic of the paper.\n\nTo prove that the $\\ell_2$ mechanism supports approximate DP, they use the fact that a mechanism $M$ is $(\\varepsilon, \\delta)$-DP iff $\\Pr[\\ell_{M, X, X'} \\geq \\varepsilon] - e^{\\varepsilon}\\Pr[\\ell_{M, X', X} \\leq -\\varepsilon] \\leq \\delta$ where $\\ell_{M, X', X}$ is the privacy loss of $M$ on arbitrary neighboring datasets $X, X'$ (Balle & Wang, 2018).\nUpper bounding the first term and lower bounding the second in the left-hand side becomes a means to computing a $\\delta$ for a given $\\epsilon$.\nThe authors show that both terms can be defined by the probability mass that $M(X)$ and $M(X')$ respectively assigns to regions in $\\mathbb{R}^d$ defined by specific spherical caps.\nThey give algorithms for bounding both terms, which, when combined in Algorithm 3, allows for checking if a $(\\varepsilon, \\delta)$-guarantee holds for a given $d$ and $\\sigma$.\n\nEmpirically, they demonstrate that binary searching over $\\sigma$ using Algorithm 3 allows for tight privacy analysis of the mechanism (Figure 4).\nThey also demonstrate that analytically computing the optimal $\\sigma$ for the $\\ell_2$ mechanism is feasible and does not scale with $d$ (Figure 5), even if it is slower than the corresponding computations for Laplace and Gaussian mechanisms for a $\\ell_2$ guarantee.\nThey further show that sampling the $\\ell_2$ mechanism takes roughly only a factor ~2 more time than the Laplace/Gaussian counterpart (Figure 6).\nFigure 1 makes the point that the $\\ell_2$ mechanism can meaningfully improve on the mean squared error over the Gaussian mechanism for $d$ up to $100$ (for $\\varepsilon=1, \\delta=10^{-5}$).\n\n## update after rebuttal\n\nThe authors answered my questions adequately. I stand by my score.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "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": "Thanks for the review!\n\n> Some parameter ranges for the experiments could need more motivation, e.g. why $d=100$ everywhere?\n\nOur experiments focus on the $d \\leq 100$ setting to highlight the range where the $\\ell_2$ mechanism offers the largest improvement over both Laplace and Gaussian noise. As noted at the end of Section 4.2, the gap between $\\ell_2$ and Gaussian noise shrinks to $<1$% at $d=350$ (and essentially vanishes for larger $d$). If desired, we can add more language highlighting this behavior.\n\n> Connected to the preceding point, the improvement over the Gaussian/Laplace mechanism seems concentrated to moderately small $d$ for reasonable $(\\varepsilon, \\delta)$.\n\nWe agree that the $\\ell_2$ mechanism's improvement is concentrated to moderate $d$ (e.g., $d < 500$, and most notably on $d < 100$). Regarding the privacy regime, we note that the curve in the left plot of Figure 1 looks essentially the same in higher ($(0.1, 10^{-7})$-DP) and lower ($(10,10^{-3})$-DP) privacy settings, as mentioned at the end of Section 4.2.\n\n> From the discussion in Section 4 regarding Figure 1, it seems as if the mean squared error of the $\\ell_2$ mechanism approaches that of the Gaussian as $d$ increases for general settings of $(\\varepsilon, \\delta)$. Is this true in general, and if so, is there a simple argument for why that is? I think the improvement for small $d$ is interesting in its own right, but it would be useful to know if there is any benefit to using the mechanism for larger $d$.\n\nOur experiments demonstrate that the $\\ell_2$ mechanism error converges to Gaussian mechanism error as $d$ increases, irrespective of the $(\\varepsilon, \\delta)$ regime. However, we do not have a formal proof that this holds. A possible intuitive explanation is that the $(\\varepsilon, \\delta)$-DP $\\ell_2$ mechanism ``spends its $\\delta$'' violating $\\varepsilon$-DP close to the origin, while the Gaussian mechanism continues doing so arbitrarily far into its tails (and thus can incur arbitrarily high privacy loss). The result is that the $\\ell_2$ density peaks at a smaller $\\ell_2$ distance than the Gaussian density at the same $(\\varepsilon, \\delta)$-DP guarantee, but this difference shrinks as $d$ grows. This partially explains why the $\\ell_2$ mechanism error approaches the Gaussian mechanism error as $d$ grows, though it does not explain why the chosen $\\sigma$s necessary for DP lead to this behavior.\n\n> Does the computation in Figure 5 meaningfully depend on $(\\varepsilon, \\delta)$? I could believe that $d$ has no influence, but it is not clear to me if the computation becomes prohibitive for certain regimes of $(\\varepsilon, \\delta)$.\n\nWe do not believe that the ($\\sigma$) computation in Figure 5 meaningfully depends on the exact privacy parameters within typical ranges. We tested this computation at more extreme privacy levels ($(0.1, 10^{-7})$-DP and $(10,10^{-3})$-DP) and did not encounter numerical issues. However, this might change as $e^\\varepsilon$ and $\\delta$ near the limits of conventional floating point accuracy.", "claims_and_evidence": "Yes.", "methods_and_evaluation_criteria": "Yes.", "theoretical_claims": "Yes, I read through the proofs in the main part of the paper. I did not check every detail, but it seemed convincing to me. I did not check the appendix however.", "experimental_designs_or_analyses": "Yes, all the listed experiments look sound to me.\nI have minor questions regarding the parameter ranges listed later.", "relation_to_broader_scientific_literature": "The paper gives the first useful (in the sense of efficiently computable) approximate DP guarantee for the $\\ell_2$ mechanism.\nThis mechanism is already known as an instantiation of the $K$-norm mechansim (Hardt & Talwar, 2010), but the approximate DP analysis is novel.\nIn (Ganesh & Zhao, 2021) they also used spherical caps to bound the privacy loss of \"generalized Gaussians\", but these are (1) different probability distributions and (2) they give looser bounds.", "essential_references_not_discussed": "Not that I am aware of.", "other_strengths_and_weaknesses": "Strengths:\n1. Well-written paper with clearly stated contributions.\n2. The privacy analysis of the $\\ell_2$ mechanism appears to be tight (Figure 4), and the fact that it can (at least sometimes) beat Gaussian noise in mean squared error is interesting (and potentially practically useful).\n3. As demonstrated by Figure 5 and 6, it also appears as if the $\\ell_2$ mechanism is scalable with respect to time.\n\nWeaknesses:\n1. Some parameter ranges for the experiments could need more motivation, e.g. why $d=100$ everywhere?\n2. Connected to the preceding point, the improvement over the Gaussian/Laplace mechanism seems concentrated to moderately small $d$ for reasonable $(\\varepsilon, \\delta)$.", "other_comments_or_suggestions": "I think the paper could benefit from a more thorough investigation of when the $\\ell_2$ mechanism improves over the Gaussian mechanism. Figure 1 (Left) shows what happens up to $d=100$ for a fix choice of $(\\varepsilon, \\delta)$, but it would be interesting to see what happens for larger $d$ and other privacy regimes.", "questions_for_authors": "I ask the following questions to better understand the results. I do not expect my score to change dramatically based on answers to these questions in isolation.\n\nQuestions:\n1. From the discussion in Section 4 regarding Figure 1, it seems as if the mean squared error of the $\\ell_2$ mechanism approaches that of the Gaussian as $d$ increases for general settings of $(\\varepsilon, \\delta)$. Is this true in general, and if so, is there a simple argument for why that is? I think the improvement for small $d$ is interesting in its own right, but it would be useful to know if there is any benefit to using the $\\ell_2$ mechanism for larger $d$.\n2. Does the computation in Figure 5 meaningfully depend on $(\\varepsilon, \\delta)$? I could believe that $d$ has no influence, but it is not clear to me if the computation becomes prohibitive for certain regimes of $(\\varepsilon, \\delta)$.", "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": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: In this paper, the authors give the first approximate differential privacy analysis for a version of the K-norm mechanism in which the norm is the standard Euclidean one. They also empirically show the mechanism is adds less error than the Gaussian noise mechanism for moderate dimensions, but this advantage disappears as the dimension increases. This somewhat limits the impact of the results. Another limiting factor is the lack of tight composition guarantees - fairly tight composition analyses of the Gaussian noise mechanism through tools like Gaussian differential privacy are available, and important for applications like private stochastic gradient descent. Nevertheless, this is an interesting contribution and can be accepted if there is space in the program.
Decision: Accept (poster)