Asymptotic Optimality of the High-Dimensional Gaussian Mechanism and Improved Low-Dimensional Mechanisms for Differential Privacy

Unknown

Conceptio › Archive › arXiv CS

arXiv CSopen access

Asymptotic Optimality of the High-Dimensional Gaussian Mechanism and Improved Low-Dimensional Mechanisms for Differential Privacy

Unknown · 2026 · arxiv_cs

arXiv CS · Papers · License: Open Access · 2026

Open Source ↗Direct PDF ↓

cryptography, security, privacy, cybersecurity

Asymptotic Optimality of the High-Dimensional Gaussian Mechanism and Improved Low-Dimensional Mechanisms for Differential Privacy

Yu Wei 1 2 Alexander Bienstock 3 Antigoni Polychroniadou 3

arXiv:2606.08681v1 [cs.CR] 7 Jun 2026

Abstract

Many applications of DP, including the above, involve protecting real-valued T -dimensional vector queries Q(D) ∈ RT over private datasets D. In this setting, we want to obfuscate any addition or removal of a single data record from D, which may perturb Q by any µ ∈ RT . Typically, the size ||µ|| of µ is bounded by some scalar s, the sensitivity of the query. The standard way to achieve DP in this setting is by using the seminal additive noise mechanism (Dwork et al., 2006b). This mechanism simply adds T -dimensional noise X sampled from some distribution D to the query: b = Q + X. The typical distribution used is the multiQ variate Gaussian distribution (Dwork et al., 2006a; Dwork & Roth, 2014), i.e., X ∼ N (0, σ 2 IT ), where σ ∝ s. This Gaussian mechanism has several appealing properties, including (i) privacy with respect to ℓ2 -sensitivity, as opposed to e.g., ℓ1 -sensitivity, which is important to retain utility of high-dimensional queries (ii) spherical symmetry, which means that privacy does not depend on the direction of the query sensitivity, (iii) tight, closed-form privacy analysis (Balle & Wang, 2018b), and (iv) tight composition guarantees (Dong et al., 2022; Bun et al., 2018).

The additive noise mechanism is a foundational tool for differential privacy (DP) of T dimensional real-valued vector queries. The Gaussian mechanism, utilizing Gaussian noise, is the mostly widely used such mechanism, due to its simplicity and strong privacy guarantees. In this work, we provide justification for this choice, showing that as the dimension T → ∞, no additive-noise mechanism can asymptotically improve on the Gaussian mechanism’s privacy– utility tradeoff for the strong privacy settings typically used.We also develop a new family of Spherical Generalized Gamma DP mechanisms, which contains both the Gaussian mechanism and the recently studied ℓ2 mechanism (Joseph et al., ICML 2025). We identify members of this family that outperform both the Gaussian and ℓ2 mechanisms in certain low-dimensional settings, and show tight composition of all mechanisms in this family, answering an open question of Joseph et al. regarding the ℓ2 mechanism.

Even though the Gaussian mechanism has these desirable properties and has found wide use in practice (Bittau et al., 2017; Apple, 2016; Google, 2023), one may wonder whether it is the best mechanism for privately answering real-valued vector queries. Indeed, prior work has explored alternative mechanisms for such queries: It was recently shown that the so-called ℓ2 -mechanism (Joseph et al., 2025) (essentially, a high-dimensional version of the Laplace mechanism (Dwork et al., 2006b) for ℓ2 sensitivity) outperforms the Gaussian mechanism in certain lowdimensional settings, while appearing to obtain similar performance in higher dimensions.

1. Introduction Differential Privacy (DP) (Dwork et al., 2006b) is a powerful tool that can be utilized to extract aggregate insights from data, while retaining individuals’ privacy. Differential privacy has myriad privacy-preserving applications, including training deep learning models (Abadi et al., 2016), generating synthetic data (Kurakin et al., 2024; Zhang et al., 2021; Torkzadehmahani et al., 2019; Yoon et al., 2019; Mckenna et al., 2019), publishing aggregate statistics (Dwork et al., 2006b), and more.

However, these two questions remain to be answered:

(Q1) Is the Gaussian mechanism optimal in high dimensions?

Georgia Institute of Technology, Atlanta, Georgia, USA Work partially done while an intern at JPMorgan 3 JPMorgan AI Research & AlgoCRYPT CoE, New York, New York, USA. Correspondence to: Alexander Bienstock <[email protected]>, Yu Wei <[email protected]>.

(Q2) Are there mechanisms that outperform both the Gaussian and ℓ2 mechanisms in low dimensions?

Our Contributions. In this paper, we answer both questions affirmatively, through the lens of (ε, δ)-DP (Dwork 1

Optimality of the High-Dimensional Gaussian Mechanism and Improved Low-Dimensional Mechanisms for DP

y x

Figure 1. A Spherically Symmetric random variable X = RU has independent (scalar) radial component R and directional component U . Left: The directional component U is uniformly distributed on the unit sphere. Right: The density functions of one family of radial components R that we study: the Spherical Generalized Gamma distribution with varying shape parameter α, rate β, and tail control p.

improved upon in the sense of achieving a strictly smaller limiting worst-case optimal delta at the same MSE. We can thus deduce the following (since larger error yields stronger privacy):

et al., 2006a). Along the way, we provide additional insights, including answering an open question from (Joseph et al., 2025). To answer (Q1), we first show that one only need focus on spherical symmetric noise distributions (see Figure 1); they perform at least as well as all other additive noise distributions. Indeed, spherical symmetric noise distributions satisfy rotational invariance and are thus a natural choice for the worst-case nature of DP, in which a single data record could perturb the query in any direction; both the Gaussian and ℓ2 mechanisms use spherical symmetric distributions. A bit more formally, spherical symmetric random variables are of the form X = RU , where R ∈ R≥0 is a radial random variable and U ∼ Unif(S T −1 ) is an independent random T -dimensional unit vector.

Theorem 1.1 (Informal version of Theorem 3.1). As the dimension of query Q ∈ RT , T → ∞, using Gaussian b = Q+X yields noise X in the additive noise mechanism Q lowest error among all noise distributions, for all strong enough privacy requirements. This result is of particular relevance to training deep learning models with DP (Abadi et al., 2016), in which T is the number of model parameters, which can be quite large. To answer (Q2), we consider for the first time a broad and expressive subfamily of spherical symmetric distributions that contains those of both the Gaussian and ℓ2 mechanisms, amongst many others: the Spherical Generalized Gamma Distributions (see right of Figure 1). We begin by demonstrating how to numerically evaluate the DP guarantees of these mechanisms. Indeed, by leveraging the radial decomposition perspective — where the spherical noise is separated into its magnitude and directional components — we reduce the privacy analysis to a one-dimensional integration over a smooth, absolutely continuous radial random variable. This structure allows the privacy loss to be evaluated efficiently and with arbitrary precision using standard numerical integration techniques. We furthermore bound the error that can arise from such numerical evaluation to obtain formal DP guarantees.

Now, consider the Gaussian privacy function gε,s (σ 2 ), which for fixed privacy level ε > 0 and ℓ2 sensitivity s > 0, outputs the optimal δG of the Gaussian mechanism with per-coordinate variance σ 2 (Balle & Wang, 2018b; Lu et al., 2023). We show that for any Mean Squared fixed Error (MSE) constraint e = Ex R2 and any spherical noise X = RU , as T → ∞, the optimal δ that X can achieve for (ε,s) is lower bounded, up to an o(1) term, by Ex g(R2 /T ) , the average over R of the Gaussian privacy function evaluated at the normalized radial energy R2 /T . This value R2 /T for the Gaussian mechanism is exactly equal to the per-coordinate variance σ 2 = e/T in the highdimensional limit. Next, for large enough e, we show that g satisfies certain properties that allow for a Jensen-like inequality Ex g(R2 /T ) ≥ g(Ex R2 /T ) = g(e/T ) = δG .

We leverage this ability in order to find settings and mechanisms for those settings that have less error than both the Gaussian and ℓ2 mechanisms. The spherical generalized gamma distribution is characterized by three parameters:

Thus, the Gaussian mechanism cannot be asymptotically 2

Optimality of the High-Dimensional Gaussian Mechanism and Improved Low-Dimensional Mechanisms for DP

the shape parameters α and p, and the scale parameter β. We provide an optimization algorithm that finds the parameters which minimize the error of the corresponding additive noise mechanism, for a particular privacy level. Our evaluation shows that in low dimensions, we are able to find α, p, β that result in a mechanism with error up to 15% less than both the Gaussian and ℓ2 mechanisms.

The work of (Alghamdi et al., 2023) studies the (ε, δ)-DP composition of real valued vector queries. They show that as the number of sequential compositions, k, trends towards infinity, additive, spherical symetric mechanisms are optimal for ℓ2 sensitivity. They also provide an optimization algorithm to find the best such mechanism, but only in this asymptotic sense as k → ∞. They provide some empirical evidence for small k of their mechanism’s superiority over the Gaussian mechanism for T = 10, but only for very small δ = 10−8 (note: it is already known that the Gaussian mechanism cannot perform well as δ → 0, and cannot achieve δ = 0.). We on the other hand study the standalone (no composition) setting and show superior mechanisms to the Gaussian for more realistic values of δ like δ = 10−3 .

As a bonus, we study tight composition of all Spherical Generalized Gamma Mechanisms using differential privacy accounting techniques. This demonstrates the compatibility of these mechanisms with existing DP frameworks and answers an open question regarding tight composition of the ℓ2 mechanism (Joseph et al., 2025).1 Related Work. Previous works have studied the optimality of the Gaussian mechanism: (Dong et al., 2021) show that a restricted class of additive noise mechanisms all converge to the Gaussian mechanism as T → ∞ (in terms of Gaussian DP (Dong et al., 2022)), and that across all mechanisms in this class, the Gaussian mechanism performs best for all dimensions T . However, this class of additive noise mechanisms is quite restrictive, since we know, for example, that the ℓ2 mechanism outperforms the Gaussian mechanism for low T . Moreover, Gaussian DP is tailored towards the Gaussian mechanism and is a “relaxation” (Dong et al., 2022) of the classical approximate DP that we study.

2. Preliminaries 2.1. Differential Privacy We consider a dataset space X ∗ equipped with a neighboring relation ≃ (add/remove of one record). A randomized mechanism M : X ∗ → RT is (ε, δ)-differentially private (Dwork & Roth, 2014) if for all neighboring G ≃ G′ and all set S ⊆ RT , Pr [M(G) ∈ S] ≤ eε Pr [M(G′ ) ∈ S] + δ

Works that study the non-optimality of the Gaussian mechanism include (Geng & Viswanath, 2016), who only study integer valued (vector) queries in terms of ℓ1 sensitivity, and (Geng et al., 2020), who only study real valued scalar queries. The ℓ2 mechanism extends (Hardt & Talwar, 2010), which only studies pure DP, to approximate DP. Buliding off the family of Generalized Gaussian Mechanisms from (Liu, 2019), (Rinberg et al., 2025) provide empirical evidence that the Gaussian is optimal within this family. However, we are able to show notable improvements of non-Gaussian mechanisms in our Spherical Generalized Gamma Mechanism over the Gaussian mechanism. Moreover, Generalized Gaussian Mechanisms, specified by only two parameters, are a proper subset of our Spherical Generalized Gamma Mechanisms, specified by three parameters.

(1) def

Hockey-stick divergence and optimal δ. Let (t)+ = max{t, 0}. For random variables X, Y taking values on the same support RT and ε ≥ 0, define the hockey-stick divergence at level ε (Balle et al., 2018)) (a.k.a., α-divergence with α = eε ) by def Hε (X, Y ) = sup Pr[X ∈ S] − eε Pr[Y ∈ S] , +

S∈RT

In the context of differential privacy, for a fixed neighboring pair G ≃ G′ , we interpret Hε (M(G), M(G′ )) as the optimal (minimal) δ for the (one-sided) DP inequality Pr [M(G) ∈ S] ≤ eε Pr [M(G′ ) ∈ S] + δ holding for all measurable S. Accordingly, we define the (one-side) optimal delta (Lu et al., 2024) at privacy level ε

The Rank-1 Singular Multivariate Gaussian (R1SMG) mechanism introduced in (Ji & Li, 2024), is a special case within our broader family of spherical generalized gamma mechanisms. The authors claim that RS1MG has error an order of magnitude lower than the Gaussian mechanism; however, we discover a bug in their proof (see Appendix E). Indeed, our numerical evaluation reveals that the privacy guarantees of R1SMG are substantially weaker than those of the standard multivariate Gaussian mechanism.

def

δG,G′ (ε) = Hε (M(G), M(G′ ))

(2)

and the (worst-case) optimal delta (a.k.a., privacy profile (Balle et al., 2018)) of the mechanism at privacy level ε as def

δM (ε) = sup δG,G′ (ε).

As per the review discussion: https://openreview. net/forum?id=ypeehAYK7W.

(3)

G≃G′

By construction, M is (ε, δ)-DP if and only if δM (ε) ≤ δ. 3

Optimality of the High-Dimensional Gaussian Mechanism and Improved Low-Dimensional Mechanisms for DP 2

Radial r.v. R

Radial density fR (r)

Noise density fX (x) = g(∥x∥2 ) (with y = ∥x∥2 )

Shape fX (x) ∝

GGamma(α, β, p)

pβ (α+1)/p α −βr p r e Γ( α+1 p )

Γ(T /2) pβ (α+1)/p α+1−T −βy p y e 2π T /2 Γ( α+1 p )

y α+1−T e−βy

GGamma T − 1, 2σ1 2 , 2

(Gaussian in RT )

GGamma T − 1, θ1 , 1

(ℓ2 -Laplace in RT )

r T −1 T 2 2 −1 Γ( T2 )σ T

e− 2σ2

r T −1 − θr e θ T Γ(T )

− 2σ2 1 (2πσ 2 )T /2

e− 2σ2

y Γ(T /2) e− θ 2π T /2 θ T Γ(T )

e− θ

Table 1. Radial random variables R and the induced spherically symmetric densities fX (x) = g(∥x∥22 ) for noise random variable X = RU , obtained via Theorem 2.1. The last column reports g(∥x∥22 ) up to a normalization constant.

T vector U uniformly distributed on the unit sphere S++ such that X can be decomposed as:

2.2. Gaussian Mechanism We consider the T -dimensional vector-valued query q : X ∗ → RT with ℓ2 sensitivity

X = RU,

def

s = sup ∥q(G) − q(G′ )∥2 .

where R and U are independent. Equivalently, X is spherically symmetric if its density function fX (x) exists and depends only on the norm of x, that is,

G≃G′

For u > 0, the Gaussian mechanism (Dwork et al., 2006b; Balle & Wang, 2018b) with per-coordinate variance u is def

MG,u (G) = q(G) + G,

G ∼ N (0, uIT ) .

fX (x) = g(∥x∥2 ),

(4)

for some deterministic function g : [0, ∞) → R≥0 .

Notice that the mechanism’s mean-squared error is

Denote by Φ(·) the standard normal CDF. According to the literature (Balle & Wang, 2018a; Lu et al., 2023), the optimal delta of MG,u at privacy level ε is

The decomposition X = RU separates radial (R) and direction (U ) random variables. Theorem 2.1 shows how to convert a radial density into the induced spherically symmetric density. Table 1 lists some spherical random variables and the corresponding radial random variables studied in the paper.

δMG,u (ε) = g(u) √ √ s ε u s ε u def + √ − eε Φ − − √ . (6) = Φ − s s 2 u 2 u

Theorem 2.1 (Radial-to-Spherical Density Transformation (Fang, 2018)[Thm 2.9). Let X = RU be a spherically symmetric random variable. If the random variable R has a density over R≥0 and denote its pdf as fR (·), then,

max∗ Ex ∥MG,u (G) − q(G)∥22 = Ex ||G||22 = T u. (5)

G∈X

In particular, for fixed (ε, δ, s), the minimal Gaussian variance achieving (ε, δ)-DP is def

u0 (δ) = inf{u > 0 : g(u) ≤ δ}.

fX (x) = g(∥x∥2 ) =

Γ( T2 ) 2π

T 2

1−T

∥x∥2

fR ∥x∥2 .

In Section A, we give Proposition A.1 that characterizes the distribution of cos Θ, where Θ is the angle between the random direction vector U and a fixed reference direction.

(7)

We will repeatedly use Equation (6) as the baseline privacy–utility tradeoff to compare against other additivenoise mechanisms.

3. Gaussian Optimality in High Dimensions

2.3. Spherical Symmetric Distribution

We study the optimality of the Gaussian noise distribution for additive-noise differentially private mechanisms in high dimensions. A natural utility measure for this class is the mean-squared error (MSE), equivalently, the second moment of the additive noise (with zero-centered mean). Our notion of optimality asks which mechanism provides the strongest privacy guarantee under a fixed MSE budget. Concretely, we compare mechanisms at a fixed privacy level ε and sensitivity s by their optimal delta δM (ε) (cf. Equation (3)); smaller δM (ε) yields stronger privacy.

We begin by defining spherically symmetric random vectors X ∈ RT , which are the main noise distributions studied in this paper. Definition 2.1 (Spherically Symmetric Distribution (Fang, 2018) 2 ). A random vector X ∈ RT is spherically symmetric if there exists a random variable R ≥ 0 and a random 2 The first characterization can be found in Thm 2.1 and the second appears in equation 2.7 of the book (Fang, 2018)

Optimality of the High-Dimensional Gaussian Mechanism and Improved Low-Dimensional Mechanisms for DP Table 2. Numerical lower bounds on δ⋆ in Theorem 3.1 (for some ε with fixed sensitivity s = 1).

Theorem 3.1 states our main optimality result. Informally, for a fixed privacy level ε and sensitivity s and a target high-privacy regime with δ sufficiently small, Theorem 3.1 says that, as the query dimension T → ∞, the Gaussian mechanism is asymptotically optimal among all additivenoise mechanisms with the same MSE: if an additive-noise mechanism matches the Gaussian error budget, then its optimal delta at privacy level ε cannot be smaller than δ. Theorem 3.1 (Asymptotic Gaussian optimality among additive noises). Fix ε ≥ 0 and s > 0. There exists δ⋆ ∈ (0, 1) such that for all δ ∈ (0, δ⋆ ] the following holds.

δ⋆

0.25 0.50 1.00 2.00

0.736670 0.706970 0.649185 0.549133

4.00 8.00 16.00

0.416972 0.292170 0.197615

We first focus our discussion on spherically symmetric noises, a natural yet broad class in the DP worst-case model: since neighboring datasets can induce sensitivity in arbitrary directions, it is natural to consider perturbations that treat all directions uniformly. We define the class of additive-noise mechanism adding spherically symmetric noises as spherical additive-noise mechanisms, and formally state it in Definition 3.1.

Let u0 = u0 (δ) be the minimal Gaussian variance for which the Gaussian mechanism MG,u0 is (ε, δ)-DP. For def

each T ≥ 2, let MT,u0 (µTh) = µTi+ XT be any additive2

noise mechanism with Ex ∥XT ∥2 = T u0 . Then, lim inf δMT ,u0 (ε) ≥ δMG,u0 (ε) = δ. T →∞

Definition 3.1 (Spherical additive-noise mechanism). Fix T ≥ 2 and an ℓ2 -sensitive query with sensitivity s > 0 under the add/remove neighboring relation. A spherical additive-noise mechanism is any mechanism of the form

Equivalently, for every η > 0, for all sufficiently large T , δMT ,u0 (ε) ≥ δ − η. Numerical lower bounds on the threshold δ⋆ . Theorem 3.1 is stated in the privacy regime δ ≤ δ⋆ , where δ⋆ ∈ (0, 1) is a constant. To demonstrate that this regime is non-vacuous and, in particular, includes δ-values typically used in practice, Table 2 reports numerically verified lower bounds on δ⋆ for some ε (with sensitivity fixed to s = 1). The values in Table 2 provide evidence that the privacy regime δ ≤ δ⋆ covers standard privacy choices such as δ ≤ 10−3 (in fact, the range is much bigger), thereby highlighting the practical relevance of Theorem 3.1. Our computation is based on a numerical verification of the tangentsupport conditions for the Gaussian privacy function g, explained below (cf. Proposition 3.1).

def

MRT ,T (µT ) = µT + RT UT , where µT ∈ RT is the dataset query result, UT ∼ Unif(S T −1 ) is uniform on the unit sphere, and RT ∈ R>0 is independent of UT . Lemma 3.1 states our first observation that, when the query dimension T is sufficiently large, the optimal δ of any spherical additive-noise mechanism MRT ,T,u0 can be lower bound, up to an asymptotically vanishing error term, in terms of the Gaussian privacy function g(·) (cf. Equation (6)). Specifically, letting RT denote the radial random variable of the spherical noise, theh optimal 2 iδ at priR vacy level ε is lower bounded by Ex g TT , which is the Gaussian privacy expression evaluated at the normalized radial energy RT2 /T and averaged over its randomness. This reduction turns the comparison between the Gaussian mechanism and an arbitrary spherical mechanism into a one-dimensional question: under the mean preserving constraint Ex RT2 /T = u0 (the MSE bud- 2 2 get), can any randomization 2 RT /T make Ex g(RT /T ) smaller than g(Ex RT /T ) = g(u0 )? We note that for Gaussian benchmark, its corresponding RT2 /T equals to u0 · χ2T /T , which converges to u0 as T → ∞.

Finite-dimensional convergence. Theorem 3.1 is an asymptotic statement in the dimension T . In particular, it does not provide a concrete threshold T0 or a convergence rate for how quickly the Gaussian’s asymptotic optimality kicks in. The only asymptotic loss in the proof enters through Lemma 3.1, where the distribution of a suitably scaled coordinate of a uniform random direction is approximated by a standard normal distribution. Making the result quantitative would require replacing this o(1) aproximation gap by an explicit normal-approximation bound and propagating that error through the distinguishing test used in the proof. We leave such finite-T rates as an interesting direction for future work.

Lemma 3.1 (Proof is in Section B). Fix ε ≥ 0 and s > 0. For each T ≥ 2, let UT ∼ Unif(S T −1 ) and let RT ∈ R>0 be independent of UT . For any deterministic µT ∈ RT with ∥µT ∥2 = s, define XT = RT UT and YT = XT + µT . Let δ be the optimal delta with respect to XT , YT at privacy

3.1. Proof sketch of Theorem 3.1 In this section, we provide a proof sketch of Theorem 3.1. Full details are deferred to Section B. 5

Optimality of the High-Dimensional Gaussian Mechanism and Improved Low-Dimensional Mechanisms for DP

level ε. Then, as T → ∞, it holds that 2 RT δ ≥ Ex g + o(1). T

point such that g(u0 (δ)) = δ (i.e., the minimal Gaussian variance shown in Equation (7)). Denote the tangent line function at u0 (δ) by ℓδ (u) (cf. Equation (8)). Then there exists δ⋆ ∈ (0, 1), such that for every δ ∈ (0, δ⋆ ] the following hold:

Intuitively, to prove Lemma 3.1, we lower bound the optimal δ between XT and YT by constructing a set ST and bounding Pr [X ∈ ST ] − eε Pr [Y ∈ ST ] from below. We choose ST to be a threshold region — an affine test with a mild radius-dependent correction — designed to mirror the affine test for distinguishing Gaussian shifts. Conditioning on RT = r, we analyze the membership probabilities Pr [XT ∈ ST | RT = r] and Pr [YT ∈ ST | RT = r], and show that as T → ∞, they converge to the two Gaussian CDF terms that define the Gaussian privacy function evaluated at u = r2 /T . Averaging over RT then yields the stated asymptotic lower bound in Lemma 3.1.

1. g is convex on [u0 (δ), ∞); 2. g(u) ≥ ℓδ (u) for all u ∈ [0, u0 (δ)]. Intuitively, to prove Lemma 3.2, our first step is an asymptotic analysis of g(u) as the MSE budget u → ∞ (equivalently, δ = g(u) → 0): using Mills-type bounds for Φ, we obtain the expansion 1 ε2 −3/2 1+O , g(u) = Cε,s u exp − 2 u 2s u which implies that g is eventually convex, i.e., there exists uright such that g is convex on [uright , ∞). To control the lower part, we study the tangent-line intercept L(u) = g(u) − ug ′ (u). The same asymptotics show that L(u) → 0 as u → ∞. Since g is decreasing, we can choose a sufficiently large point u⋆ ≥ uright so that the tangent line at u⋆ has intercept below minu∈[0,uright ] g(u); this ensures the tangent line at u⋆ lies below g on [0, uright ], while convexity guarantees the supporting-line inequality on [uright , u⋆ ].

Proposition 3.1 answers the one-dimensional question induced by Lemma 3.1: if the Gaussian privacy function g(·) satisfies an appropriate supporting-line property at the MSE budget u0 , then any mean-preserving randomization of the effective variance cannot improve privacy relative to the Gaussian benchmark. Concretely, the supporting-line property requires that g is convex on [u0 , ∞) and that g lies above its tangent line at u0 on [0, u0 ]. This is a tailored Jensen-type condition without requiring global convexity: convexity on the upper side enables a Jensen argument, while the additional lower-side tangent bound ensures the same supporting line remains valid even where g need not be convex. A formal proof appears in Section B.

def

Defining δ⋆ = g(u⋆ ) yields the desired supporting-line property at (u⋆ , δ⋆ ). Finally, we use the downward-closure argument (Proposition B.1) to extend the property from δ⋆ to all δ ≤ δ⋆ . Combining Lemmas 3.1 and 3.2 and proposition 3.1 yields the conclusion that, in the high-privacy regime, the Gaussian mechanism is asymptotically optimal among all spherical additive-noise mechanisms with the same MSE. To extend this optimality beyond spherical noises, Lemma 3.3 formalizes the last piece. The idea is to reduce an arbitrary additive noise X to a spherically symmetric one X ′ via Haar symmetrization.

Proposition 3.1 (Proof is in Section B). Let ε ≥ 0, δ ∈ (0, 1) and s > 0, and recall the Gaussian privacy function g(·) defined in Equation (6). Let u0 > 0 be the unique point such that g(u0 ) = δ (i.e., the minimal Gaussian variance shown in Equation (7)). Define the tangent line function at u0 by def

ℓδ (u) = g(u0 ) + g ′ (u0 )(u − u0 ).

(8)

Lemma 3.3 says that the symmetrization preserves the MSE and cannot increase the worst-direction optimal delta over shifts of ℓ2 norm at most s. The proof uses convexity of hockey-stick divergence under mixtures together with orthogonal invariance. Therefore, under a fixed MSE budget, the optimal privacy achievable by additive-noise mechanisms is no better than that achievable by spherical additive-noise mechanisms.

If g is convex on [u0 , ∞) and g(u) ≥ ℓ(u) for all u ∈ [0, u0 ], then for every random variable U ≥ 0 with Ex [U ] = u0 , Ex [g(U )] ≥ g(u0 ). Lemma 3.2 asserts that, in the high-privacy regime (i.e., for sufficiently small δ), the Gaussian privacy function g(·) satisfies the supporting-line property required by Proposition 3.1. Concretely, for all δ in this regime, the corresponding minimal MSE level u0 (δ) lies in a wellbehaved region of g: the function is convex on [u0 (δ), ∞) and, moreover, the tangent line at u0 (δ) lower bounds g throughout the interval [0, u0 (δ)].

Lemma 3.3 (Haar symmetrization (Proof is in Section B)). Fix T ≥ 2, ε ≥ 0, and s > 0. Let M be a Haaruniform random matrix over the group of all T × T orthogonal matrices and independent of a random vecdef tor X ∈ RT . Define the symmetrized noise X ′ = def def M X. Let δ = sup∥v∥2 ≤s Hε (X, X + v) and δ ′ = ′ ′ sup∥v∥2 ≤s Hε (X , X + v) denote the worst-direction op-

Lemma 3.2 (Proof is in Section B). Let ε ≥ 0, s > 0, and recall the Gaussian privacy function g(·) defined in Equation (6). For each δ ∈ (0, 1), let u0 (δ) > 0 be the unique 6

Optimality of the High-Dimensional Gaussian Mechanism and Improved Low-Dimensional Mechanisms for DP

Lemma 4.1 (Proof is in Section C.1). Fix T ≥ 2 and parameters α ∈ (−1, T − 1], β > 0, and p > 0. Let X = RU ∼ SGG(α, β, p) and let µ ∈ RT be a shift vector ⟩ with s = ∥µ∥2 . Let W = cos Θ = ⟨µ,U ∥µ∥2 ∈ [−1, 1], with CDF FW . Then the optimal δµ∗ (ε) for the neighboring pair (X, X + µ) satisfies n Z ∞ δµ∗ (ε) = max 0, fR (r) 1 − FW (w∗ (r, −ε)) dr Z ∞0 o fR (r) FW (w∗ (r, ε)) dr , − eε

timal deltas at privacy level ε over the ℓ2 ball of radius s (cf. Equation (2)). Then X ′ is spherically symmetric, and h i h i 2 2 Ex ∥X ′ ∥2 = Ex ∥X∥2

δ ′ ≤ δ.

Lemmas 3.1 to 3.3 and proposition 3.1 yields Theorem 3.1 immediately. We defer a formal wrap-up to Section B.

4. Spherical Generalized Gamma Mechanism

where fR is the density of R ∼ GGamma(α, β, p), and for each y ∈ R and r > 0, w∗ (r, y) ∈ [−1, 1] denotes the unique solution in w to

In this section, we study the question of additive-noise design in finite (especially low) dimensions, where the shape of the noise can materially affect privacy–utility tradeoff. Concretely, we formalize the Spherical Generalized Gamma (SGG) noise family and its use as an additive DP primitive for ℓ2 -sensitive vector queries.

y= h i α+1−T 2sw s2 ln 1 + + 2 + β rp − (r2 + 2swr + s2 )p/2 . 2 r r

Definition 4.1 defines the three-parameter generalizedgamma family, denoted by R ∼ GGamma(α, β, p), which we use to model the radial component of our noise. Intuitively, α controls the near-zero behavior (shape), β sets the overall scale (noise magnitude), and p tunes tail decay; see Figure 1 (right) for a visual. Definition 4.1. A three-parameter generalized-Gamma R ∼ GGamma(α, β, p) is defined with the density function: fα,β,p (r) =

Informally, the proof follows by observing that under the radial–directional decomposition X = RU , the privacy loss can be expressed as a function of two independent onedimensional random variables: the radial component R and the directional statistic W (the cosine of the angle between U and µ). Moreover, monotonicity in W converts the resulting two-dimensional inequality involving (R, W ) into a one-dimensional threshold condition on W given a fixed R, allowing us to integrate over R and obtain the claimed one-dimensional representation.

p β (α+1)/p α r exp (−βrp ) , α > −1, p > 0, β > 0. Γ α+1 p

Proposition 4.1 shows that for α ≤ T − 1 the SGG density is non-increasing with the radius: points farther from the origin receive no larger probability density.3

Definition 4.2 defines the spherical generalized-gamma (SGG) family, induced by a generalized-gamma radial distribution. The SGG family includes several standard spherical noises. For instance: (i) setting (p, α) = (2, T − 1) and β = 1/(2σ 2 ) yields X ∼ N 0, σ 2 IT (Gaussian noise); (ii) setting (p, α) = (1, T −1) and β = 1/θ yields spherical (i.e., ℓ2 -) Laplace noise with scale θ.

Proposition 4.1 (Proof is in Section C.1). Fix a dimension T ≥ 2 and parameters α ∈ (−1, T − 1], β ≥ 0, p > 0. Let X ∼ SGG(α, β, p), and let g : [0, ∞) → [0, ∞) denote 2 the density generator such that fX (x) = g(∥x∥2 ). Then 2 y 7→ g(y ) is non-increasing for y > 0. Building on this, Lemma 4.2 shows that, for the neighboring pair (X, X + µ), the optimal delta δµ∗ (ε) is monotone in the shift magnitude ∥µ∥2 . In particular, larger shifts are easier to distinguish and hence induce larger divergence, so the worst-case divergence over all shifts is attained at the largest feasible ∥µ∥2 .

Definition 4.2 (Spherical generalized-gamma (SGG) noise). Fix a dimension T ≥ 2 and parameters α > −1, β > 0, p > 0. A random vector X ∈ RT follows a Spherical Generalized-Gamma (SGG) distribution, denoted by X ∼ SGG(α, β, p), if X = R U, where R ∼ GGamma(α, β, p) and U ∼ Unif(S T −1 ) are independent.

Lemma 4.2 (Proof is in Section C.1). Fix T ≥ 2 and parameters α ∈ (−1, T − 1], β > 0, and p > 0, and let X ∼ SGG(α, β, p). For any shift vector µ ∈ RT , let δµ∗ (ε) denote the optimal δ for the neighboring pair (X, X + µ) at point ε. Then for any µ1 , µ2 ∈ RT with ∥µ1 ∥2 ≤ ∥µ2 ∥2 and any ε > 0, δµ∗ 1 (ε) ≤ δµ∗ 2 (ε).

4.1. Privacy Analysis Lemma 4.1 shows that the optimal delta at privacy level ε between SGG noise X and its shift X +µ admits an explicit one-dimensional integral representation. In particular, the optimal δµ∗ (ε) can be evaluated by integrating a smooth integrand over r ∈ (0, ∞), which yields an efficient and numerically stable procedure (in contrast to a direct exponentially expensive computation over RT ).

We note this concerns fX (x) over RT , not the radial density fR (r): due to the surface-area factor r−(T −1) in fX (x), fR (r) need not be decreasing even if fX (x) decreases with r = ∥x∥2 . 3

Optimality of the High-Dimensional Gaussian Mechanism and Improved Low-Dimensional Mechanisms for DP

Lemma 4.1, together with the monotonicity result in Lemma 4.2, indicates that calibrating an additive SGG mechanism for ℓ2 -sensitive real-vector queries is, a numerical task: given parameters (α, p) and sensitivity s, one can evaluate δs∗ (ε) as a function of the noise multiplier β, and then choose β to meet a target (ε, δ) guarantee.

while preserving the same privacy constraint. 4.2.1. F INDING O PTIMAL PARAMETERS We next provide Algorithm 5 (c.f. Section C.2), that numerically tunes the Spherical Generalized Gamma Mechanism by searching for parameters (α, β, p) that minimize the mean-squared error (MSE) c subject to a target (ε, δ)privacy constraint. It proceeds by running a binary search over MSE values c. At each binary-search step, it solves the two-dimensional problem of selecting α∗ , p∗ to minimize the achieved optimal delta δ ⋆ under the fixed noise budget c. For each candidate (α, p), Algorithm 4 determines whether there exists a noise multiplier β ⋆ that satisfies the MSE constraint c and returns the corresponding δ ⋆ ; we implement the (α, p) search using standard Bayesian optimization. If δ ∗ ≤ δ, the target parameter, then the noise is decreased in the next iteration; otherwise it is increased. The algorithm uses in the mechanism output the parameters α∗ , β ∗ , p∗ for the distribution of radial component R that minimize the MSE c subject to δ ∗ ≤ δ.

However, a naïve implementation of Lemma 4.1 may incur numerical errors (e.g., from truncating an improper integral). Since our goal is to have a provable differentially private primitive, we abstract these numerical subtleties through the oracle interface in Definition 4.3. Concretely, given (α, p, β, ε) and a shift magnitude s, the oracle outputs an η-tight upper bound on δµ∗ (ε), for all shifts µ with ∥µ∥2 ≤ s. Lemma 4.3 says that such an oracle exists. Definition 4.3. Fix a dimension T ≥ 2 and parameters α ∈ (−1, T − 1], β > 0, p > 0, and ε ≥ 0. Let X ∼ SGG(α, β, p). Fix an ℓ2 -sensitivity bound s ≥ 0 and a target slack η ≥ 0. An algorithm OracleSGG : (α, p, β, ε, s) 7→ δb is called an η-tight upper-bound oracle (for δµ∗ (ε)) if, for every ε ≥ 0 and every µ ∈ RT with ∥µ∥2 ≤ s, it outputs δb satisfying

4.3. Advantage over Gaussian and ℓ2 Mechanisms

δµ∗ (ε) ≤ OracleSGG (α, p, β, ε, ∥µ∥2 ) ≤ δµ∗ (ε) + η.

Based on Algorithm 5, we use the SGG family as a search space to identify selected low-dimensional regimes where an SGG mechanism outperforms both the Gaussian and ℓ2 mechanisms. The purpose of this experiment is to demonstrate that there is a low dimensional regimens that we could have improvement over both gaussian and ℓ2 ; it is not intended to show that SGG uniformly or systematically dominates Gaussian and ℓ2 across privacy parameters or dimensions.

Lemma 4.3 (Proof is in Section C.2). There exists a (determinstic) η-tight upper-bound oracle. Lemma 4.3 follows by an explicit construction. The oracle reduces the one-dimensional integrals defining δµ∗ (ε) to expectations under a standard Γ(k, 1) measure via the change of variables Z = βRp (with k = (α + 1)/p), so that Gamma tail probabilities can be computed in closed form. It then (i) truncates the integral at a data-independent threshold zmax chosen to make the discarded tail contribute at most ηtail , and (ii) estimates the remaining trucated expectations using a standard binning scheme.

We know that the ℓ2 mechanism (high-dimensional version of Laplace) is best suited for δℓ2 → 0, while the Gaussian mechanism is suited for δG > 0. Thus, we hypothesize that the SGG Mechanism will have the best advantage at some δ ∗ that is not too small or too big, for fixed privacy parameter ε > 0, dimension T , and sensitivity s. Based on this intuition, we develop Algorithm 6 (in Section C.4) that takes in ε, T, s and performs a binary search (using Algorithm 5) to find the δ ∗ at which the MSE of the SGG mechanism has the biggest advantage compared to the smaller of the MSEs of the Gaussian and ℓ2 mechanisms.

We then in Section C.2 provide a parameterized differentially private mechanism Mα,p SGG (cf. Algorithm 4) for vector-valued queries. For fixed (α, p), the mechanism uses an intuitive bracketing-and-bisection search via OracleSGG to calibrate the noise: it finds (up to tolerance τ ) the largest feasible rate parameter β — equivalently, the smallest noise magnitude under the parameterization — subject to the target (ε, δ) constraint, and then outputs the noisy answer q(G) + X with X ∼ SGG(α, β, p).

Using Algorithm 6, we identify realistic settings in which the optimal SGG distribution is much different from the Gaussian and ℓ2 mechanisms (p far from 1 and 2), and has MSE up to 15% lower than them. In Figure 2 we demonstrate our findings. Unsurprisingly given Theorem 3.1, the improvements are larger for small dimension T and get smaller as T increases.

4.2. Utility-Optimized SGG Mechanism Algorithm 4 shows that for any fixed (α, p), we can calibrate the rate parameter β so that Mα,p SGG satisfies the target (ε, δ) guarantee. However, the same privacy level can typically be achieved by many different pairs (α, p), and these choices can lead to different accuracy. This motivates selecting (α, p) to minimize a prescribed error metric (MSE)

Scope of the low-dimensional improvement. The gains in Figure 2 should be interpreted as a principled existence 8

Optimality of the High-Dimensional Gaussian Mechanism and Improved Low-Dimensional Mechanisms for DP

anisms). Consider k independent invocations of SGG additive mechanisms, each calibrated for an ℓ2 -sensitivity bound. Let Z1 , . . . , Zk denote their worst-case one-step PRVs, as characterized in Lemma D.1. Then the composed privacy profile at level εtot is " !! # k X δk (εtot ) = Ex 1 − exp εtot − Zi . i=1

Consequently, any upper bound δbk (εtot ) ≥ δk (εtot ) provides that the k-fold composition is (εtot , δbk (εtot ))-DP. The proof and the SGG-specific reduction of the PRV CDF to a one-dimensional radial integral are given in Section D. Algorithm 7 implements the resulting accountant by discretizing the single-step PRV distribution and computing the k-fold convolution by FFT. Since the ℓ2 mechanism is a special case of SGG, the same accounting framework also gives a tight accountant for composed ℓ2 mechanisms.

Figure 2. MSE reduction of the SGG mechanism over the ℓ2 and Gaussian baselines with ε = 0.1 and sensitivity s = 1. Each group shows the dimension T , the δ at which this advantage occurs, and the optimal SGG shape parameter p∗ .

result rather than as a uniform recommendation to replace the Gaussian mechanism in concrete dimensional mechanism design. Our study does not show strong evidence that non-Gaussian SGG mechanisms consistently yield significant improvements over Gaussian across all dimensions and privacy parameters. In our experiments, the advantage is concentrated in selected low-dimensional regimes and shrinks rapidly as the dimension increases. Thus, SGG is best viewed as a useful design space for finite-dimensional additive-noise mechanisms, while the Gaussian mechanism remains the asymptotically justified default in high dimensions.

5. Conclusion We show that as T → ∞, the standard Gaussian mechanism is asymptotically best among all additive noise mechanisms. Also, we provide a new family of SGG mechanisms and specific choices within this family that outperform both the Gaussian and recent ℓ2 mechanism in certain low-dimensional settings. These low-dimensional improvements should be viewed as an existence result: they demonstrate nontrivial finite-dimensional design space, but do not show that non-Gaussian SGG consistently provide meaningful improvement over all parameters, dimensions, or downstream applications. Furthermore, we show tight composition of the SGG mechanisms under the (ε, δ)-differential privacy, and answering an open question of (Joseph et al., 2025) regarding the ℓ2 mechanism. We view extending the studies beyond additive noise — for example, to data-dependent noise and to non-additive mechanisms — as an important direction for future work.

This distinction is also important for interpreting the practical implications of the mechanism-level comparison. When the additive vector release itself is the private primitive, the MSE reduction in Figure 2 directly corresponds to improved accuracy in the stated parameter regimes. Examples include low-dimensional mean estimation and lowdimensional vector releases under composition. By contrast, when the additive noise mechanism is used as part in a larger algorithmic design, the same mechanism-level gain need not automatically imply an end-to-end improvement. For high-dimensional private learning methods such as DPSGD, additional work is needed to determine whether any low-dimensional SGG gains translate into improved training utility

Acknowledgements We thank the reviewers for their careful reading and insightful comments, which helped us clarify the scope and presentation of the paper. We are also grateful to Hubert Chan for several helpful discussions on the direction and formulation of our main asymptotic optimality result in Theorem 3.1.

4.4. Privacy Accounting of SGG Mechanisms Since additive-noise primitives are often invoked repeatedly in DP computations, we study tight composed privacy for multi-call SGG mechanisms. The key observation is that the privacy loss random variables (PRVs) add under independent composition. Thus, once the single-step PRV distribution of an SGG mechanism can be evaluated, the composed privacy profile can be computed by convolution.

Disclaimer This paper was prepared for informational purposes in part by the Artificial Intelligence Research group of JPMorgan Chase & Co. and its affiliates ("JP Morgan”) and is not

Proposition 4.2 (Composition accounting for SGG mech9

Optimality of the High-Dimensional Gaussian Mechanism and Improved Low-Dimensional Mechanisms for DP

a product of the Research Department of JP Morgan. JP Morgan makes no representation and warranty whatsoever and disclaims all liability, for the completeness, accuracy or reliability of the information contained herein. This document is not intended as investment research or investment advice, or a recommendation, offer or solicitation for the purchase or sale of any security, financial instrument, financial product or service, or to be used in any way for evaluating the merits of participating in any transaction, and shall not constitute a solicitation under any jurisdiction or to any person, if such solicitation under such jurisdiction or to such person would be unlawful.

holm, Sweden, July 10-15, 2018, volume 80 of Proceedings of Machine Learning Research, pp. 403–412. PMLR, 2018a. URL http://proceedings.mlr. press/v80/balle18a.html. Balle, B. and Wang, Y.-X. Improving the gaussian mechanism for differential privacy: Analytical calibration and optimal denoising. In International Conference on Machine Learning (ICML), 2018b. Balle, B., Barthe, G., and Gaboardi, M. Privacy amplification by subsampling: Tight analyses via couplings and divergences. In Advances in Neural Information Processing Systems (NeurIPS), 2018.

Bittau, A., Úlfar Erlingsson, Maniatis, P., Mironov, I., Raghunathan, A., Lie, D., Rudominer, M., Kode, U., Tinnes, J., and Seefeld, B. Prochlo: Strong privacy for analytics in the crowd. In Proceedings of the Symposium on Operating Systems Principles (SOSP), pp. 441–459, 2017. URL https://arxiv.org/abs/ 1710.00901.

Impact Statement Our work studies theoretical and algorithmic tools for analyzing and calibrating additive-noise mechanisms under (ε, δ)-differential privacy. The primary intended impact is to enable practitioners to obtain tighter privacy accounting and, consequently, to add less noise for a given privacy target or to certify stronger privacy for a fixed utility level.

Bun, M., Dwork, C., Rothblum, G. N., and Steinke, T. Composable and versatile privacy via truncated CDP. In Diakonikolas, I., Kempe, D., and Henzinger, M. (eds.), 50th ACM STOC, pp. 74–86. ACM Press, June 2018. doi: 10.1145/3188745.3188946.

We do not anticipate negative societal impacts beyond the general risk that differential privacy may be misapplied in a manner that is inappropriate to the application, threat model, and sensitivity of the data. Additionally, we emphasize that our methods do not prescribe a universal “safe” choice of (ε, δ); users should select privacy parameters in consultation with domain requirements and established guidance, and should report these choices transparently.

Dong, J., Su, W. J., and Zhang, L. A central limit theorem for differentially private query answering. In Proceedings of the 35th International Conference on Neural Information Processing Systems, NIPS ’21, Red Hook, NY, USA, 2021. Curran Associates Inc. ISBN 9781713845393.

References

Dong, J., Roth, A., and Su, W. J. Gaussian differential privacy. Journal of the Royal Statistical Society Series B, 84(1):3–37, February 2022. doi: 10.1111/ rssb.12454. URL https://ideas.repec.org/ a/bla/jorssb/v84y2022i1p3-37.html.

Abadi, M., Chu, A., Goodfellow, I. J., McMahan, H. B., Mironov, I., Talwar, K., and Zhang, L. Deep learning with differential privacy. In Weippl, E. R., Katzenbeisser, S., Kruegel, C., Myers, A. C., and Halevi, S. (eds.), ACM CCS 2016, pp. 308–318. ACM Press, October 2016. doi: 10.1145/2976749.2978318.

Dwork, C. and Roth, A. The Algorithmic Foundations of Differential Privacy. Foundations and Trends in Theoretical Computer Science, 2014.

Alghamdi, W., Asoodeh, S., Calmon, F. P., Felipe Gomez, J., Kosut, O., and Sankar, L. Optimal multidimensional differentially private mechanisms in the largecomposition regime. In 2023 IEEE International Symposium on Information Theory (ISIT), pp. 2195–2200, 2023. doi: 10.1109/ISIT54713.2023.10206658. Apple. Differential privacy, 2016.

Dwork, C., Kenthapadi, K., McSherry, F., Mironov, I., and Naor, M. Our data, ourselves: Privacy via distributed noise generation. In Vaudenay, S. (ed.), EUROCRYPT 2006, volume 4004 of LNCS, pp. 486–503. Springer, Berlin, Heidelberg, May / June 2006a. doi: 10.1007/11761679_29.

Balle, B. and Wang, Y. Improving the gaussian mechanism for differential privacy: Analytical calibration and optimal denoising. In Dy, J. G. and Krause, A. (eds.), Proceedings of the 35th International Conference on Machine Learning, ICML 2018, Stockholmsmässan, Stock-

Dwork, C., McSherry, F., Nissim, K., and Smith, A. Calibrating noise to sensitivity in private data analysis. In Halevi, S. and Rabin, T. (eds.), TCC 2006, volume 3876 of LNCS, pp. 265–284. Springer, Berlin, Heidelberg, March 2006b. doi: 10.1007/11681878_14. 10

Optimality of the High-Dimensional Gaussian Mechanism and Improved Low-Dimensional Mechanisms for DP

Fang, K. W. Symmetric multivariate and related distributions. Chapman and Hall/CRC, 2018.

Lu, Y., Magdon-Ismail, M., Wei, Y., and Zikas, V. Eureka: A general framework for black-box differential privacy estimators. In 2024 IEEE Symposium on Security and Privacy (SP), pp. 913–931. IEEE, 2024.

Geng, Q. and Viswanath, P. Optimal noise adding mechanisms for approximate differential privacy. IEEE Transactions on Information Theory, 62(2):952–969, 2016. doi: 10.1109/TIT.2015.2504972.

Mckenna, R., Sheldon, D., and Miklau, G. Graphicalmodel based estimation and inference for differential privacy. In Chaudhuri, K. and Salakhutdinov, R. (eds.), Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pp. 4435–4444. PMLR, 09– 15 Jun 2019. URL https://proceedings.mlr. press/v97/mckenna19a.html.

Geng, Q., Ding, W., Guo, R., and Kumar, S. Tight analysis of privacy and utility tradeoff in approximate differential privacy. In Chiappa, S. and Calandra, R. (eds.), Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics, volume 108 of Proceedings of Machine Learning Research, pp. 89–99. PMLR, 26–28 Aug 2020. URL https://proceedings.mlr. press/v108/geng20a.html.

Rinberg, R., Shumailov, I., Singhal, V., Cummings, R., and Papernot, N. Beyond laplace and gaussian: Exploring the generalized gaussian mechanism for private machine learning, 2025. URL https://arxiv.org/abs/ 2506.12553.

Google. Learn how gboard gets better, 2023.

Torkzadehmahani, R., Kairouz, P., and Paten, B. DPCGAN: Differentially Private Synthetic Data and Label Generation . In 2019 IEEE/CVF Conference on Computer Vision and Pattern Recognition Workshops (CVPRW), pp. 98–104, Los Alamitos, CA, USA, June 2019. IEEE Computer Society. doi: 10.1109/CVPRW.2019.00018. URL https://doi.ieeecomputersociety.org/ 10.1109/CVPRW.2019.00018.

Gopi, S., Lee, Y. T., and Wutschitz, L. Numerical composition of differential privacy. J. Priv. Confidentiality, 14(1), 2024. doi: 10.29012/JPC.870. URL https: //doi.org/10.29012/jpc.870. Hardt, M. and Talwar, K. On the geometry of differential privacy. In Schulman, L. J. (ed.), 42nd ACM STOC, pp. 705–714. ACM Press, June 2010. doi: 10.1145/ 1806689.1806786.

Yoon, J., Jordon, J., and van der Schaar, M. PATE-GAN: Generating synthetic data with differential privacy guarantees. In International Conference on Learning Representations, 2019. URL https://openreview. net/forum?id=S1zk9iRqF7.

Ji, T. and Li, P. Less is more: Revisiting the gaussian mechanism for differential privacy. In Balzarotti, D. and Xu, W. (eds.), USENIX Security 2024. USENIX Association, August 2024. URL https://www.usenix.org/conference/ usenixsecurity24/presentation/ji.

Zhang, Z., Wang, T., Li, N., Honorio, J., Backes, M., He, S., Chen, J., and Zhang, Y. PrivSyn: Differentially Private Data Synthesis. In 30th USENIX Security Symposium (USENIX Security 21), pp. 929–946. USENIX Association, August 2021. ISBN 9781-939133-24-3. URL https://www.usenix. org/conference/usenixsecurity21/ presentation/zhang-zhikun.

Joseph, M., Kulesza, A., and Yu, A. Approximate differential privacy of the ℓ2 mechanism. In International Conference on Machine Learning (ICML), 2025. Kurakin, A., Ponomareva, N., Syed, U., MacDermed, L., and Terzis, A. Harnessing large-language models to generate private synthetic text, 2024. URL https: //arxiv.org/abs/2306.01684. Liu, F. Generalized gaussian mechanism for differential privacy. IEEE Transactions on Knowledge and Data Engineering, 31(4):747–756, 2019. doi: 10.1109/TKDE. 2018.2845388. Lu, Y., Magdon-Ismail, M., Wei, Y., and Zikas, V. The normal distributions indistinguishability spectrum and its application to privacy-preserving machine learning, 2023. URL https://arxiv.org/abs/2309. 01243. arXiv:2309.01243. 11

Optimality of the High-Dimensional Gaussian Mechanism and Improved Low-Dimensional Mechanisms for DP

A. Additional Preliminaries Proposition A.1 characterizes the distribution of cos Θ, where Θ is the angle between the random direction vector U and a fixed reference direction. This random variable appears repeatedly in our analysis. We write Unif(S T −1 ) for the uniform distribution on the T -dimensional unit sphere. Proposition A.1. Let random variable Θ be the angle between a fixed T -dimensional vector and a T -dimensional random vector U ∼ Unif(S T −1 ). The density function fcos Θ for the random variable cos Θ is with the form fcos Θ (u) = √

Γ( T2 ) T −3 (1 − u2 ) 2 , T −1 πΓ( 2 )

u ∈ [−1, 1],

and its CDF is with the form 4 Pr [cos Θ ≤ u] = I u+1 ( 2

T −1 T −1 , ). 2 2

∈ [0, 1] so that cos Θ = 2X − 1. Applying the change of variable formula for Proof. Let random variable X = cos Θ+1 2 pdf, we have Γ( T )2T −2 T −3 Pr [X = x] = 2 Pr [cos Θ = 2x − 1] = √ 2 T −1 (x(1 − x)) 2 . πΓ( 2 ) Using Legendre’s duplication formula, we observe that Γ(

√ T T −1 )Γ( ) = 22−T πΓ(T − 1), 2 2

√ 22−T πΓ(T − 1) T . Γ( ) = 2 Γ( T −1 2 )

Plugging it in the expression of the PDF of X, we have

Pr [X = x] =

√ 22−T πΓ(T −1) T −2 2 T −3 T −3 Γ( T −1 ) x 2 (1 − x) 2 √ 2 T −1 πΓ( 2 )

T −3 Γ(T − 1) T −3 x 2 (1 − x) 2 2 ) Γ( T −1 2 T −1 T −1 1 = x 2 −1 (1 − x) 2 −1 , T −1 B( T −1 , ) 2 2

T −1 which is the density function of beta distribution with parameter α = T −1 2 ,β = 2 .

Finally, using the CDF of the beta distribution, we have u+1 T −1 T −1 Pr [cos Θ ≤ u] = Pr [2X − 1 ≤ u] = Pr X ≤ = I u+1 ( , ). 2 2 2 2

B. Proof of Theorem 3.1 Proof of Lemma 3.1. Recall the definition of optimal δ ( Equation (2)) between X, Y at privacy level ε as δ = sup Pr [X ∈ S] − eε Pr [Y ∈ S] . +

S⊆RT

h 2 i R We will explicitly find a set ST such that Pr [X ∈ S] − eε Pr [Y ∈ S] approaches Ex g TT . +

Γ(a+b) R x a−1 Ix (a, b) = Γ(a)Γ(b) t (1 − t)b−1 dt is the regularised incomplete beta function. 0

Optimality of the High-Dimensional Gaussian Mechanism and Improved Low-Dimensional Mechanisms for DP

By rotational invariance of UT ∼ Unif(S T −1 ), WLOG, set µT = se1 (where e1 = (1, 0, . . . , 0)). Then, we set XT = RT UT ,

YT = RT UT + se1 .

We then define the set ST as the following 2 n s ε∥x∥2 o ST = x ∈ RT : ⟨e1 , x⟩ ≤ − . 2 sT

By definition of δ, we know that δ ≥ Pr [X ∈ ST ] − eε Pr [Y ∈ ST ] . In the rest of the proof, we will study the asymptotics of the expression Pr [X ∈ ST ] − eε Pr [Y ∈ ST ]. First, look at the asymptotics of the first coordinate of a random direction ⟨e1 , UT ⟩. Define √ WT =

T ⟨e1 , UT ⟩.

Using the Gaussian representation UT = G/∥G∥2 with G ∼ N (0, IT ), we have that WT = ∥G∥G/1 √T converges in 2

distribution to a standard normal distribution N (0, 1). By Pólya’s theorem, we have that lim sup |Pr [WT ≤ t] − Φ(t)| = 0,

(9)

T →∞ t∈R

where Φ is the standard normal cdf. Then, we study the asymptotics of the term Pr [XT ∈ ST | RT = r]. Condition on RT = r, we observe that XT = rUT 2 and ∥X∥2 = r2 is deterministic given r. Therefore, by the definition of ST , XT ∈ ST ⇐⇒ r⟨e1 , U ⟩ ≤

s ε r2 − · ⇐⇒ WT ≤ a 2 s T

2 r , T

where we denote function a(u) for u > 0: √ ε u s a(u) = − + √ . s 2 u Using Equation (9), we have that 2 r Pr [XT ∈ ST | RT = r] = Φ a + o(1), T where the o(1) is uniform in r. Similarly, look at the asymptotics of the term Pr [YT ∈ ST | RT = r]. Recall YT = rUT + se1 and ⟨e1 , YT ⟩ = rUT,1 + s. Then, 2

∥Y ∥2 r2 + s2 + 2rs⟨e1 , UT ⟩ = T T r2 s2 2rs WT = + + ·√ T T T T r2 1 = + Op T T 2 r = + op (1) , T

Optimality of the High-Dimensional Gaussian Mechanism and Improved Low-Dimensional Mechanisms for DP

where Op , op is the standard notation for asymptotic stochastic boundedness. Therefore, by the definition of ST , s ε r2 1 YT ∈ ST ⇐⇒ r⟨e1 , U ⟩ ≤ − − · + Op 2 s T T 2 r 1 ⇐⇒ WT ≤ b + Op √ T T 2 r ⇐⇒ WT ≤ b + op (1), T where we denote function b(u) for u > 0: √ ε u s b(u) = − − √ . s 2 u Using Equation (9), we have that 2 r Pr [YT ∈ ST | RT = r] = Φ b + o(1), T where the o(1) is uniform in r. Taking expectation of Pr [YT ∈ ST | RT = r] and Pr [XT ∈ ST | RT = r] over RT and plugging into Pr [X ∈ ST ] − eε Pr [Y ∈ ST ] gives Pr [X ∈ ST ] − eε Pr [Y ∈ ST ] 2 2 RT RT ε = Ex Φ a −e Φ b + o(1), T T 2 2 R R where the expression Φ a TT − eε Φ b TT is exactly the optimal delta of the Gaussian mechanism MG,u at privacy level ε (cf. Equation (6)). Finally, recall that δ ≥ Pr [X ∈ ST ] − eε Pr [Y ∈ ST ] , we finish the proof. +

Proof of Proposition 3.1. By convexity of g on [u0 , ∞), the tangent line at u0 is a global under-estimator on the right, namely, for all u ≥ u0 , g(u) ≥ g(u0 ) + g ′ (u0 )(u − u0 ) = ℓδ (u), Since we assume that g(u) ≥ ℓδ (u) for all u ∈ [0, u0 ] in the statement, we have g(u) ≥ ℓδ (u) for all u ≥ 0. Taking expectation with respect to any U ≥ 0 yields Ex [g(U )] ≥ Ex [ℓδ (U )] = Ex [g(u0 ) + g ′ (u0 )(U − u0 )] = g(u0 ) + g ′ (u0 )(Ex [U ] − u0 ) = g(u0 ).

Proposition B.1 (Downward closure of the tangent-support conditions). Fix ε ≥ 0, δ ∈ (0, 1), s > 0, and let g : (0, ∞) → R be differentiable and strictly decreasing. For any δ ∈ (0, 1), Let u(δ) > 0 be the unique point such that g(u(δ)) = δ and define the tangent line function at t > 0 by ℓt (u) = g(t) + g ′ (t)(u − t). If there exists a δ0 ∈ (0, 1) and u0 = u(δ0 ) such that: g is convex on [u0 , ∞); and g(u) ≥ ℓu0 (u) for all u ∈ [0, u0 ]. Then the two conditions hold is downward closed for all δ ∈ (0, δ0 ). 14

Optimality of the High-Dimensional Gaussian Mechanism and Improved Low-Dimensional Mechanisms for DP

Proof. Fix any δ ∈ (0, δ0 ) and let u1 = u(δ). Since g is strictly decreasing and g(u0 ) = δ0 > δ = g(u1 ), it follows that u1 > u0 . It is easy to see that the first condition holds on u1 . Because [u1 , ∞) ⊆ [u0 , ∞) and g is convex on [u0 , ∞), it is convex on the subset [u1 , ∞) as well. To show the second condition holds, we split the interval [0, u1 ] into two parts and consider each case separately. For any fixed u ∈ [0, u0 ], define function F (t) = lt (u) for t ≥ u, whose output is the tangent line function at t evaluating at a fixed point u. Differentiating F (t) with respect to t, we have F ′ (t) = g ′ (t) + g ′′ (t)(u − t) − g ′ (t) = g ′′ (t)(u − t). On [u0 , ∞) we have g ′′ (t) ≥ 0 by convexity, and since t ≥ u we have u − t ≤ 0. Hence F ′ (t) ≤ 0 for all t ≥ u0 , so F is nonincreasing on [u0 , ∞). Because u1 ≥ u0 , ℓu1 (u) = F (u1 ) ≤ F (u0 ) = ℓu0 (u). By assumption, g(u) ≥ ℓu0 (u) for all u ∈ [0, u0 ], thus g(u) ≥ ℓu0 (u) ≥ ℓu1 (u),

∀u ∈ [0, u0 ].

For the second case, where u ∈ [u0 , u1 ], h(u) = g(u)−ℓu1 (u). We know that h′ (u) = g ′ (u)−g ′ (u1 ). Since g is decreasing and convex on [u0 , ∞), its derivative g ′ is nondecreasing there. For any u0 ≤ u ≤ u1 , this implies g ′ (u) ≤ g ′ (u1 ), hence h′ (u) ≤ 0 on [u0 , u1 ]. Therefore h is nonincreasing on [u0 , u1 ], and for all u ∈ [u0 , u1 ] we have h(u) ≥ h(u1 ) = 0, i.e., g(u) ≥ ℓu1 (u). Combining both cases yields g(u) ≥ ℓu1 (u) for all u ∈ [0, u1 ], completing the proof for the second condition. 2

Proof is in Lemma 3.2. Denote function ϕ(x) = √12π e−x /2 as the standard normal density. We start from the case where ε > 0. Our first step is to give an asymptotic form for function g(u), in which the asymptotics is in terms of u. Concretely, ε2 1 g(u) = Cε,s u−3/2 exp − 2 u 1+O , (10) 2s u ε/2 3

e s with Cε,s = √ . 2π ε2 √ ε Let x = x(u) = ε s u , and d = d(u) = 2√s u = 2x . We rewrite g(u) as g(u) = Φ −(x − d) − eε Φ −(x + d) . The standard Mills bounds says that for all z > 0,

1 Φ(−z) 1 ≤ ≤ . z + z −1 ϕ(z) z Then we have 0≤

1 Φ(−z) 1 1 1 1 − ≤ − = 3 ≤ 3, z ϕ(z) z z + z −1 z +z z

1 −3 which gives us Φ(−z) ) as z → ∞. ϕ(z) = z + O(z ε Define F (z) = Φ(−z) ϕ(z) . Using Φ(−z) = ϕ(z)F (z) and the identity ϕ(x − d) = e ϕ(x + d), we express g(u) as g(u) = ϕ(x − d) F (x − d) − F (x + d) .

Applying the asymptotic form of F (z) at z = x ± d, and use that d = ε/(2x) = O(1/x) as x → ∞: 1 1 d 1 F (x − d) − F (x + d) = − +O 3 · x−d x+d x x 1 2d +O 5 = 2 x − d2 x 1 ε = 3 +O 5 . x x 15

Optimality of the High-Dimensional Gaussian Mechanism and Improved Low-Dimensional Mechanisms for DP

Moreover, 1 (x − d)2 ϕ(x − d) = √ exp − 2 2π 2 1 x ε d2 = √ exp − + − 2 2 2 2π ε/2 2 1 e = √ e−x /2 1 + O 2 . x 2π Plugging these into g(u) = ϕ(x − d) F (x − d) − F (x + d) yields 2 eε/2 g(u) = √ e−x /2 2π

ε 1 + O . x3 x5

Finally, substitute x and d in terms of ε, u, s back, we obtain the asymptotic form of g(u) as expressed in Equation (10). We then show that for the case ε > 0, there exists uright > 0 such that g is convex on [uright , ∞). Let k = ε2 /(2s2 ) > 0, we first rewrite g(u) = f (u)(1 + η(u)), where f (u) = Cε,s u−3/2 e−ku and η(u) = O(1/u) by Equation (10). Differentiating (log g)(u) = (log f )(u) + log(1 + η(u)) with respect to u, we have 3 1 (log g)′ (u) = − k − +O 2u u2 1 3 (log g)′′ (u) = 2 + O 3 . 2u u

(11)

Using the identity g(u) = exp (log g(u)), and differentiate both side with respect to u twice, we have g ′′ (u) = g(u) (log g)′ (u)2 + (log g)′′ (u) . Plugging Equation (11) into the expression of g ′′ (u) above, we have 1 . g (u) = g(u) k + O u

′′

Since g(u) > 0 for all u > 0, it is clear to see that there exists uright > 0 such that g ′′ (u) > 0 for all u ≥ uright , i.e. g is convex on [uright , ∞). Next, we define the function L(u) as the y-intercept of the tangent line at u (recall the tangent line is defined in the statement ℓδ (u), and u is the u0 (δ) as defined). Concretely, L(u) = g(u) − ug ′ (u) = g(u) 1 − u(log g)′ (u) . Plugging Equation (11) into the above, we have L(u) = g(u)(1 + ku + O(1)). Since g(u) decays like u−3/2 e−ku , we have lim L(u) = 0.

u→∞

We now are ready to show that for the case ε > 0, there exists a u⋆ that satisfies both conditions. Let m = g(uright ), and since g is a decreasing function, we know that m ≤ g(u) for all u ∈ [0, uright ]. Choose u⋆ ≥ uright large enough that L(u⋆ ) ≤ m. Let δ⋆ = g(u⋆ ) ∈ (0, 1) and define the intercept function at u⋆ as ℓ⋆ (u) = g(u⋆ ) + g ′ (u⋆ )(u − u⋆ ). 16

Optimality of the High-Dimensional Gaussian Mechanism and Improved Low-Dimensional Mechanisms for DP

We claim that g(u) ≥ ℓ⋆ (u) for all u ∈ [0, u⋆ ]. First, for u ∈ [0, uright ], since function ℓ⋆ (u) is decreasing in u, we have that ℓ⋆ (u) ≤ ℓ⋆ (0) = g(u⋆ ) − u⋆ g ′ (u⋆ ) ≤ m ≤ g(u). Second, for u ∈ [uright , u⋆ ], convexity of g on [uright , ∞) implies that g(u) ≥ ℓ⋆ (u). Therefore we prove that for the case ε > 0, there exists a point u⋆ such that g(u) ≥ ℓ⋆ (u) on [0, u⋆ ], and g is convex on [u⋆ , ∞). We notice that the existence also holds for the case ε = 0. Using Taylor expansion of Φ at 0, we can derive an asymptotic form for function g(u) when ε = 0: g(u) = 2

s 1 + ϕ(0)t + O(t3 ) − 1 = √ u−1/2 + O(u−3/2 ). 2 2π

Also, we have L(u) = g(u) − ug ′ (u) = 2√3s2π u−1/2 + o(u−1/2 ) → 0 as u → ∞. The rest will follow directly from the proof for the case ε > 0. To finish the proof, we then apply the downward-closure argument ( Proposition B.1), and observe that the two conditions that hold at u⋆ also hold at u0 ≥ u⋆ : g is convex on [u0 , ∞) and g(u) ≥ ℓδ (u) for all u ∈ [0, u0 ]. This proves the lemma. Combining Lemmas 3.1 and 3.2 and proposition 3.1 yields the conclusion that, in the high-privacy regime, the Gaussian mechanism is asymptotically optimal among all spherical additive-noise mechanisms with the same MSE. Theorem B.1 formlizes this. Theorem B.1 (Asymptotic Gaussian optimality among spherical noises). Fix ε ≥ 0 and s > 0. There exists δ⋆ ∈ (0, 1) such that for every δ ∈ (0, δ⋆ ] the following holds. Let u0 = u0 (δ) be the minimal Gaussian variance for which the Gaussian mechanism MG,u0 is (ε, δ)-DP. For each T ≥ 2, let MRT ,T,u0 be any spherically symmetric additive-noise mechanism with Ex RT2 = T u0 . Then lim inf δMRT ,T ,u0 (ε) ≥ δMG,u0 (ε) = δ. T →∞

Equivalently, for every η > 0, for all sufficiently large T , δMRT ,T ,u0 (ε) ≥ δ − η. Proof. Fix ε ≥ 0, s > 0, and let δ⋆ be as in Lemma 3.2. Fix any δ ∈ (0, δ⋆ ], and let u0 = u0 (δ) > 0 be the (unique) solution to g(u0 ) = δ. Recall that, we define Gaussian privacy function g for u > 0 (cf. Equation (6)), √ √ s ε u s ε u + √ − eε Φ − − √ . g(u) = Φ − s s 2 u 2 u Now consider the spherical mechanism MRT ,T,u0 (µT ) = µT + RT UT with Ex RT2 = T u0 . Let µT ∈ RT be any shift with ∥µT ∥2 = s, and define neighboring output distribution XT = RT UT ,

YT = XT + µT .

Let δThid (ε) denote the optimal delta at level ε for the pair (XT , YT ). By definition of δε (MRT ,T,u0 ) as the worst-case delta over neighboring databases, we know that for every choice of µT with ∥µT ∥2 = s, we have that δε (MRT ,T,u0 ) ≥ δThid (ε). We compare the privacy parameter δThid (ε) to that of the Gaussian benchmark MG . 17

Optimality of the High-Dimensional Gaussian Mechanism and Improved Low-Dimensional Mechanisms for DP

Let U = RT2 /T . By Lemma 3.1, we have δThid (ε) ≥ Ex [g(U )] + o(1) 2 RT + o(1), = Ex g T

T → ∞,

where o(1) → 0 as T → ∞ for fixed (ε, s). h 2 i h 2i R R It remains to lower bound Ex g TT under the second-moment constraint Ex TT = u0 . Apply Proposition 3.1 with the random variable U. By Lemma 3.2 (with δ ≤ δ⋆ ), the function g satisfies the convexity and tangent-line conditions at u0 , hence Proposition 3.1 yields Ex [g(U )] ≥ g(u0 ) = δ.

(12)

Combining the above two inequalities gives δThid (ε) ≥ Ex [g(U )] + o(1) ≥ g(u0 ) + o(1) = δ + o(1). Therefore, lim inf δε (MRT ,T,u0 ) ≥ lim inf δThid (ε) ≥ δ, T →∞

T →∞

which is exactly the claimed statement. Proof of Lemma 3.3. Recall that, by Lemma 3.3’s definition, M is a Haar-uniform random matrix over the group of all T × T orthogonal matrices and independent of a random vector X ∈ RT . Let X ′ = M X. d

We first show that X ′ is spherically symmetric. Fix any deterministic T ×T orthogonal matrix Q. We know that QM = M by Haar-uniform random matrix’s property. Therefore, we have d

QX ′ = QM X = M X = X ′ , which, by definition, says that X ′ is spherically symmetric. Since orthogonal transformations preserve the Euclidean norm, so ∥X ′ ∥2 = ∥M X∥2 = ∥X∥2 , and therefore h i h i 2 2 Ex ∥X ′ ∥2 = Ex ∥X∥2 . It remains to prove δ ′ ≤ δ. Fix any µ ∈ RT with ∥µ∥2 ≤ s. Let ν denote Haar measure over the orthogonal group. For each orthogonal matrix O, define PO , QO as the distribution of OX and OX + µ, respectively. By convexity of hockey-stick divergence under mixtures, Z ′ ′ Hε (X , X + µ) ≤ Hε (PO , QO ) dν(O). For every fixed orthogonal matrix O, applying the bijection x 7→ O⊺ x to both distributions gives Hε (OX, OX + µ) = Hε (X, X + O⊺ µ) . Since ∥O⊺ µ∥2 = ∥µ∥2 ≤ s, the definition of δ gives Hε (X, X + O⊺ µ) ≤ δ. Therefore, Hε (X ′ , X ′ + µ) ≤ δ. Taking the supremum over all µ with ∥µ∥2 ≤ s gives δ ′ ≤ δ. To finish the proof of Theorem 3.1, we further use Lemma 3.3, which formalize that, under a fixed MSE budget, the optimal privacy achievable by additive-noise mechanisms is no better than that achievable by spherical additive-noise mechanisms. 18

Optimality of the High-Dimensional Gaussian Mechanism and Improved Low-Dimensional Mechanisms for DP

Proof of Theorem 3.1. Fix ε ≥ 0 and s > 0, and let δ⋆ be as in Lemma 3.2. Fix any δ ∈ (0, δ⋆ ], and let u0 = u0 (δ) > 0 be the unique solution to g(u0 ) = δ, where (cf. Equation (6)) √ √ ε u ε u s s − eε Φ − . g(u) = Φ − + √ − √ s s 2 u 2 u Now fix any T ≥ 2 and consider an arbitrary additive-noise mechanism MT,u0 (µT ) = µT + XT , h i 2 where XT ∈ RT is a random vector satisfying the MSE constraint Ex ∥XT ∥2 = T u0 . Let def

δT (ε) =

sup Hε (XT , XT + v) . ∥v∥2 ≤s

By definition of the worst-case optimal delta for the additive-noise mechanism, δMT ,u0 (ε) = δT (ε). Let XT′ = MT XT be the symmetrized noise of XT , where MT is the Haar-uniform random matrix over the group of all T × T orthogonal matrices. Define def

δT′ (ε) =

sup Hε (XT′ , XT′ + v) .

∥v∥2 ≤s

By Lemma 3.3, we know XT′ is spherically symmetric, has the same MSE as XT , and moreover δT′ (ε) ≤ δT (ε).

(13)

Since XT′ is spherically symmetric, there exists a nonnegative random variable RT > 0 and an independent UT ∼ d Unif(S T −1 ) such that XT′ = RT UT , and Ex RT2 = T u0 . Therefore, the spherical optimality result Theorem B.1 applies to the spherical mechanism µT + XT′ and yields lim inf δT′ (ε) ≥ δMG,u0 (ε) = δ.

(14)

T →∞

Combining Equation (13) and Equation (14) gives lim inf δMT ,u0 (ε) = lim inf δT (ε) ≥ lim inf δT′ (ε) ≥ δ. T →∞

T →∞

This is exactly the claimed statement.

C. Supplementary Material for Spherical Generalized Gamma Mechanism C.1. Numerical Bound Proof of Lemma 4.1. Let Y0 , Y1 , X be i.i.d. with X = RU ∼ SGG(α, β, p), where R ∼ GGamma(α, β, p) and U ∼ Unif(S T −1 ) are independent. Define Θ the angle between µ and U , and recall W = cos Θ ∈ [−1, 1], whose CDF FW given in Proposition A.1. d

Let fX denote the density of X. Since Y0 = X and Y1 +µ = X +µ, we have fY0 (x) = fX (x) and fY1 +µ (x) = fX (x−µ). By the privacy-loss random variable characterization of the optimal δ(ε) by a fixed ε ( (Balle & Wang, 2018a)), h i δ ∗ (ε) = Pr Lneg (X) ≤ −ε − eε Pr Lpos (X) ≥ ε , +

where fX (X − µ) fY1 +µ (X) = ln , fY0 (X) fX (X) fY0 (X + µ) fX (X + µ) Lneg (X) = ln = ln . fY1 +µ (X + µ) fX (X) Lpos (X) = ln

Optimality of the High-Dimensional Gaussian Mechanism and Improved Low-Dimensional Mechanisms for DP

Spherical symmetry reduces the PLRV to a function of (R, W ). By Theorem 2.1, the SGG density is spherically 2 symmetric, i.e., fX (x) = g(∥x∥2 ) for a suitable generator g. Therefore, 2

Lpos (X) = ln

g(∥X − µ∥2 )

Lneg (X) = ln

g(∥X + µ∥2 )

2 g(∥X∥2 )

= ln

g(R2 − 2RsW + s2 ) , g(R2 )

= ln

g(R2 + 2RsW + s2 ) . g(R2 )

2 g(∥X∥2 ) d

Moreover, since U ∼ Unif(S T −1 ) implies W = −W , we have Lpos (R, W ) = Lneg (R, −W ) and hence Lpos (X) = Lneg (X). Consequently, we may work with the single privacy loss L(X) = Lneg (X), and write h i δ ∗ (ε) = Pr [L(X) ≤ −ε] − eε Pr [L(X) ≥ ε] . +

For X ∼ SGG(α, β, p), Table 1 yields α+1−T −β∥x∥p 2

fX (x) ∝ ∥x∥2

g(t) ∝ t

α+1−T 2

e−βt

p/2

2 2 Substituting this g into L(X) = ln g(∥X + µ∥2 )/g(∥X∥2 ) gives

L(X) = ℓ(R, W ), where for r > 0 and w ∈ [−1, 1], ℓ(r, w) =

h i α+1−T 2sw s2 ln 1 + + 2 + β rp − (r2 + 2swr + s2 )p/2 . 2 r r

Monotonicity in w (for α ≤ T − 1). Since the lemma assumes α ∈ (−1, T − 1], we have α + 1 − T ≤ 0. Let q(r, w) = r2 + 2swr + s2 > 0. A direct calculation yields i p sr h ∂ℓ α+1−T −1 2 = (r, w) = sr − βp q(r, w) (α + 1 − T ) − βp q(r, w)p/2 . ∂w q(r, w) q(r, w) Because sr/q(r, w) > 0, βp q(r, w)p/2 > 0, and (α + 1 − T ) ≤ 0, the bracketed term is strictly negative for all r > 0 and w ∈ [−1, 1]. Hence ∂ℓ/∂w(r, w) < 0 on (0, ∞) × [−1, 1], so for each fixed r > 0 the map w 7→ ℓ(r, w) is strictly decreasing on [−1, 1]. Therefore, for any y ∈ R and r > 0 there is a unique threshold w∗ (r, y) ∈ [−1, 1] satisfying ℓ(r, w∗ (r, y)) = y. One-dimensional integral expressions.

Fix y ∈ R. By strict monotonicity, conditional on R = r,

{ℓ(r, W ) ≤ y} ⇐⇒ {W ≥ w∗ (r, y)},

{ℓ(r, W ) ≥ y} ⇐⇒ {W ≤ w∗ (r, y)}.

Using independence of R and W , Z ∞ Pr(L(X) ≤ −ε) = Z0 ∞ Pr(L(X) ≥ ε) =

fR (r) 1 − FW (w∗ (r, −ε)) dr, fR (r) FW (w∗ (r, ε)) dr.

0 ∗

Substituting into δ (ε) = Pr(L ≤ −ε) − eε Pr(L ≥ ε) + yields the desired one-dimensional representation stated in Lemma 4.1. 20

Optimality of the High-Dimensional Gaussian Mechanism and Improved Low-Dimensional Mechanisms for DP

Proof of Proposition 4.1. By Theorem 2.1 and Definition 4.1, for y = ∥x∥2 > 0 we have fX (x) = g(y 2 ) = Cα,β,p,T y α+1−T exp −βy p , for a constant Cα,β,p,T > 0 that does not depend on y. Differentiate with respect to y: d g(y 2 ) = g(y 2 ) dy

α+1−T p−1 − βp y . y

Since α ≤ T − 1 implies α + 1 − T ≤ 0, and since βp y p−1 ≥ 0 for y > 0, the bracketed term is non-positive for all d g(y 2 ) ≤ 0 for all y > 0, i.e., y 7→ g(y 2 ) is non-increasing. This is equivalent to t 7→ g(t) being y > 0. Therefore dy non-increasing on (0, ∞) under the change of variables t = y 2 . Proof of Lemma 4.2. Write Pµ for the distribution of X + µ and P0 for the distribution of X. Since X is spherically symmetric, the quantity δµ∗ (ε) depends on µ only through s = ∥µ∥2 ; hence it suffices to prove monotonicity in s. Let f denote the density of X and note that Pµ has density fµ (x) = f (x − µ). Recall that the optimal δ at level ε can be expressed as δµ∗ (ε) =

Z RT

f (x) − eε f (x − µ) + dx.

Equivalently, let c = eε and using (a − b)+ = a − min{a, b} for a, b ≥ 0, we may rewrite δµ∗ (ε) = 1 −

Using the identity min{a, b} =

R∞ 0

Z min{f (x), cf (x − µ)} dx. RT

1{a ≥ t}1{b ≥ t} dt for a, b ≥ 0, we have

Z ∞ min{f (x), cf (x − µ)} dx = λ {x : f (x) ≥ t} ∩ {x : cf (x − µ) ≥ t} dt RT Z0 ∞ = λ At ∩ (µ + At/c ) dt,

where λ(·) denotes Lebesgue measure and At = {x : f (x) ≥ t}. 2

By Proposition 4.1, the radial profile y 7→ g(y 2 ) is non-increasing for α ∈ (−1, T − 1]. Since f (x) = g(∥x∥2 ) depends only on ∥x∥2 and is non-increasing in the radius, each superlevel set At is a (possibly empty) Euclidean ball centered at the origin: there exists a radius ρ(t) ∈ [0, ∞] such that At = B(0, ρ(t)). Likewise, At/c = B(0, ρ(t/c)). Therefore, for each t > 0, λ At ∩ (µ + At/c ) = λ (B(0, ρ(t)) ∩ B(µ, ρ(t/c))) . A standard geometric fact is that, overlap of two balls decreases as their center separate. Formally, for fixed radii r1 , r2 ≥ 0, the function λ (B(0, r1 ) ∩ B(se1 , r2 )) µ is a fixed reference direction. Since λ(B(0, r1 ) ∩ B(µ, r2 )) depends on µ is non-increasing in s ≥ 0, where e1 = ∥µ∥ 2 only through s = ∥µ∥2 , it R follows that λ At ∩ (µ + At/c ) is non-increasing in s = ∥µ∥2 for every t. Plugging this shows that the overlap integral min{f (x), cf (x − µ)} dx is non-increasing in s.

Finally, δµ∗ (ε) is therefore non-decreasing in s = ∥µ∥2 . Hence, if ∥µ1 ∥2 ≤ ∥µ2 ∥2 , then δµ∗ 1 (ε) ≤ δµ∗ 2 (ε), as claimed. 21

Optimality of the High-Dimensional Gaussian Mechanism and Improved Low-Dimensional Mechanisms for DP

Algorithm 1 η-tight upper-bound oracle OracleSGG 1: Input: Parameters (T, α, p, β, ε) with α ∈ (−1, T − 1], p > 0, β > 0, sensitivity bound s ≥ 0, target slack η ≥ 0. 2: Output: δb = OracleSGG (α, p, β, ε, s). 3: k ← (α + 1)/p, ηtail ← η/3, ηint ← η − ηtail 4: Compute (by bisection) any zmax > 0 such that (1 + eε ) Q(k, zmax ) ≤ ηtail .

Adaptive probability binning on [0, zmax ] to bracket the truncated integrals. 5: P ← {[0, zmax ]} // current partition into bins 6: while true do 7: // For each bin Ii = [zi , zi+1 ], compute its Gamma mass and a binwise bracket on ge± . 8: Initialize accumulators: A ← 0, A ← 0, B ← 0, B ← 0. 9: Initialize bin-score list (for refinement): score(I) ← 0 for all I ∈ P. 10: for each Ii = [zi , zi+1 ] ∈ P do 11: πi ← P (k, zi+1 ) − P (k, zi ) //P denotes regularized lower incomplete gamma function 12: [g −,i , g −,i ] ← EncloseG Ii , −ε; T, α, p, β, ε, s 13:

[g +,i , g +,i ] ← EncloseG Ii , ε; T, α, p, β, ε, s

14:

A ← A + πi g −,i ; A ← A + πi g −,i

B ← B + πi g +,i ; B ← B + πi g +,i 16: score(Ii ) ← πi (g −,i − g −,i ) + eε πi (g +,i − g +,i ) 17: end for 18: if (A − A) + eε (B − B) ≤ ηint then break 19: // Refine the partition by splitting the bin with largest contribution to the bracket width. 20: Let I ⋆ = [zL , zU ] ∈ P be a bin maximizing score(I). 21: zM ← (zL + zU )/2. 22: P ← (P \ {I ⋆ }) ∪ {[zL , zM ], [zM , zU ]}. 23: end while 15:

// Add the tail bound and output an upper bound on δµ∗ (ε). 24: τ ← Q(k, zmax ) // Q denotes regularized upper incomplete gamma function ε b 25: δ ← max{0, (A + τ ) − e B} b 26: Output: δ.

C.2. Provable DP Guarantee and Mechanism We first provide intuition for the proof of Lemma 4.3 (existence of an η-tight upper-bound oracle OracleSGG ). It follows by an explicit construction. At a high level, the oracle reduces the one-dimensional integrals defining δµ∗ (ε) to expectations under a standard Γ(k, 1) measure via the change of variables Z = βRp (with k = (α + 1)/p), so that Gamma tail probabilities can be computed in closed form. It then (i) truncates the integral at a data-independent threshold zmax chosen to make the discarded tail contribute at most ηtail , and (ii) brackets the remaining truncated expectations by an adaptive probability-binning scheme: on each bin, the integrand is provably upper and lower bounded by an an interval [g, g], and these bounds are aggregated with the bin masses πi to obtain global lower/upper bounds whose total width is provably controlled. We now give the formal proof. Proof of Lemma 4.3. We prove the lemma constructively by showing that Algorithm 1 implements an η-tight upper-bound oracle defined in Definition 4.3. Fix any dimension T ≥ 2, parameters α ∈ (−1, T − 1], p > 0, β > 0, privacy level ε ≥ 0, and any shift vector µ ∈ RT with ∥µ∥2 = s. Let X ∼ SGG(α, β, p). By Lemma 4.1, the optimal δ for the neighboring pair (X, X + µ) can be written as δµ∗ (ε) = max{0, A − eε B},

(15)

where A = Ex [g− (R)] and B = Ex [g+ (R)] are expectations under R ∼ GGamma(α, β, p), and g± (·) ∈ [0, 1] are the 22

Optimality of the High-Dimensional Gaussian Mechanism and Improved Low-Dimensional Mechanisms for DP

Algorithm 2 E NCLOSE G: Binwise bounds on ge± (z) over I = [zL , zU ] 1: Input: Bin I = [zL , zU ], target y ∈ {ε, −ε}, parameters (T, α, p, β, ε), sensitivity bound s 2: Parameter: bisection tolerance τw > 0. e(z) ∈ [g, g] for all z ∈ I. 3: Output: Bounds [g, g] such that g 4: rL ← (zL /β)1/p ,

rU ← (zU /β)1/p ,

wlo ← −1,

whi ← 1, okh← true i 2sw s2 p 2 2 p/2 ln 1 + + + β r − (r + 2swr + s ) on r ∈ [rL , rU ]. // Interval-bisection in w for Φ(r, w) = α+1−T 2 2 r r

5: while whi − w lo > τw do 6: wmid ← (wlo + whi )/2. 7: [Φ, Φ] ← EnclosePhi [rL , rU ], wmid ; T, α, p, β, s . 8: if Φ ≤ y ≤ Φ then ok ← false; break // Cannot decide the sign of Φ(r, wmid ) − y uniformly on this bin within τw . 9: if Φ > y then wlo ← wmid else whi ← wmid 10: end while 11: if ok = false then Return: [0, 1] 12: if y = ε then g ← FW (wlo ), g ← FW (whi ) else g ← 1 − FW (whi ), g ← 1 − FW (wlo ) 13: Output: [g, g].

bounded angle-probability functions defined in Lemma 4.1, i.e. g− (R) = 1 − FW (w∗ (R, −ε)),

g+ (R) = FW (w∗ (R, ε)).

We now show that Algorithm 1 outputs a value δb satisfying δµ∗ (ε) ≤ δb ≤ δµ∗ (ε) + η.

(16)

Rewriting Under a Standard Gamma Measure. Let k = (α + 1)/p and define the change of variables Z = βRp . Then Z ∼ Gamma(k, 1) (shape k, unit scale), with density fZ (z) = Define ge± (z) ∈ [0, 1] by ge± (z) = g±

1/p z β

1 k−1 −z z e , Γ(k)

z > 0.

. A direct substitution yields

A = Ex [e g− (Z)] ,

B = Ex [e g+ (Z)] .

Truncation and a Closed-form Tail Bound. Let zmax > 0 and set τ = Pr[Z > zmax ] = Q(k, zmax ), where Q(·, ·) is the regularized upper incomplete gamma function. Define the truncated integrals Z zmax Z zmax A≤zmax = fZ (z)e g− (z) dz, B≤zmax = fZ (z)e g+ (z) dz. 0

Since 0 ≤ ge± ≤ 1, the discarded tails satisfy 0 ≤ A − A≤zmax ≤ τ,

0 ≤ B − B≤zmax ≤ τ. Consequently,

|(A − eε B) − (A≤zmax − eε B≤zmax )| ≤ (1 + eε )τ. In Algorithm 1, we choose zmax (by bisection on Q(k, ·)) so that (1 + eε )τ ≤ ηtail . This guarantees that truncation contributes at most ηtail additive error to the linear form A − eε B. Probability binning and Brackets on the Truncated Integrals. Fix any partition 0 = z0 < z1 < · · · < zm = zmax , Ii = [zi , zi+1 ]. Let πi = Pr[Z ∈ Ii ] = P (k, zi+1 ) − P (k, zi ), where P (·, ·) is the regularized lower incomplete gamma function. Suppose that for each bin Ii we have a provable lower and upper bound ge± (z) ∈ [g ±,i , g ±,i ], 23

∀z ∈ Ii .

Optimality of the High-Dimensional Gaussian Mechanism and Improved Low-Dimensional Mechanisms for DP

Algorithm 3 E NCLOSE P HI: Interval bound for Φ(r, w) over r ∈ [rL , rU ] 1: Input: interval [rL , rU ] with 0 < rL ≤ rU , scalar w ∈ [−1, 1], parameters (T, α, p, β, s) 2: Output: [Φ, Φ] s.t. Φ(r, w) ∈ [Φ, Φ] for all r ∈ [rL , rU ]. 3: c1 ← (α + 1 − T )/2

// Bound q(r) = r2 + 2swr + s2 on [rL , rU ] (convex quadratic). 4: r ⋆ ← min{rU , max{rL , −sw}} {projection of the vertex −sw} 2 2 5: qL ← rL + 2swrL + s2 , qU ← rU + 2swrU + s2 , q⋆ ← (r⋆ )2 + 2swr⋆ + s2 6: q ← min{qL , qU , q⋆ }, q ← max{qL , qU } 2 2 // Bound c1 ln(q(r)/r2 ) using q, q and r2 ∈ [rL , rU ]. 2 2 7: u ← q/rU , u ← q/rL 8: if u ≤ 0 then ℓ ← −∞ else ℓ ← ln(u) 9: ℓ ← ln(u) 10: if c1 ≥ 0 then L ← c1 ℓ, L ← c1 ℓ else L ← c1 ℓ, L ← c1 ℓ // Bound rp − q(r)p/2 (monotone for r ≥ 0, q ≥ 0). p p 11: a ← rL , a ← rU p/2 12: b ← (q) , b ← (q)p/2 13: D ← a − b, D ← a − b // Combine: Φ = L + β · D (with β > 0). 14: Φ ← L + β D 15: Φ ← L + β D 16: Output: [Φ, Φ].

Multiplying by the nonnegative density and integrating over Ii yields A=

m−1 X

πi g −,i ≤ A≤zmax ≤

i=0

m−1 X

πi g −,i = A,

i=0

πi g +,i ≤ B≤zmax ≤

i=0

m−1 X

πi g +,i = B.

i=0

Therefore the truncated linear form is bracketed as A − eε B ≤ A≤zmax − eε B≤zmax ≤ A − eε B, and the bracket width satisfies m−1 i X h A − A + eε B − B = πi (g −,i − g −,i ) + eε (g +,i − g +,i ) , i=0

which is exactly the quantity tracked by line 18 in Algorithm 1. It remains to justify that ge± (z) ∈ [g ±,i , g ±,i ] is true for all i ∈ [m], z ∈ Ii , and that the adaptive refinement loop terminates once A − A + eε B − B falls below ηint . Correctness of E NCLOSE P HI and E NCLOSE G. We first recall the (binwise) privacy-loss threshold function used in Lemma 4.1. For r > 0 and w ∈ [−1, 1], define h i α+1−T 2sw s2 Φ(r, w) = ln 1 + + 2 + β rp − (r2 + 2swr + s2 )p/2 . 2 r r Because α ≤ T − 1, the coefficient (α + 1 − T )/2 ≤ 0, and since q(r, w) = r2 + 2swr + s2 increases with w, both terms in Φ(r, w) are non-increasing in w. Hence, for each fixed r > 0, the map w 7→ Φ(r, w) is non-increasing on [−1, 1]. For a target level y ∈ {ε, −ε}, define the threshold w∗ (r, y) = sup{w ∈ [−1, 1] : Φ(r, w) ≥ y}, 24

Optimality of the High-Dimensional Gaussian Mechanism and Improved Low-Dimensional Mechanisms for DP

with the convention that sup ∅ = −1. By monotonicity in w, we have that for every r > 0, Φ(r, w) ≥ y ⇐⇒ w ≤ w∗ (r, y). Recall that g− (r) = 1 − FW (w∗ (r, −ε)),

g+ (R) = FW (w∗ (r, ε)), and ge± (z) = g±

1/p z β

Correctness of E NCLOSE P HI. Fix w ∈ [−1, 1] and an interval r ∈ [rL , rU ] with 0 < rL ≤ rU . Algorithm 3 computes bounds for Φ(r, w) by interval arithmetic: (1) it bounds the quadratic q(r, w) = r2 +2swr+s2 on [rL , rU ] using convexity, 2 2 (2) it bounds ln(q(r, w)/r2 ) using monotonicity of ln together with q(r, w) ∈ [q, q] and r2 ∈ [rL , rU ], and (3) it bounds p p p p/2 p/2 p r − q(r, w) using monotonicity of x 7→ x on R≥0 and r ∈ [rL , rU ]. Combining these bounds linearly yields an interval [Φ, Φ] satisfying Φ(r, w) ∈ [Φ, Φ]

∀r ∈ [rL , rU ].

Correctness of E NCLOSE G. Fix a z-bin I = [zL , zU ] and let r ∈ [rL , rU ] be its corresponding r-range with r = (z/β)1/p . WLOG, assume now 0 < rL ≤ rU . Algorithm 2 performs bisection on w ∈ [−1, 1] to enclose w∗ (r, y) for all r ∈ [rL , rU ]. At each bisection step with midpoint wmid , it calls E NCLOSE P HI to obtain an interval [Φ, Φ] satisfying Φ(r, wmid ) ∈ [Φ, Φ]. If Φ > y, then Φ(r, wmid ) > y for all r in the bin; since Φ(r, ·) is non-increasing, this implies w∗ (r, y) ≥ wmid for all r, so updating wlo ← wmid is sound. Similarly, if Φ < y. If neither condition holds (i.e., the interval straddles y), the routine returns [0, 1], which again is sound. When the routine terminates without the fallback, it has produced wlo ≤ whi such that w∗ (r, y) ∈ [wlo , whi ], Applying the monotonicity of the CDF FW yields FW (w∗ (r, ε)) ∈ FW (wlo ), FW (whi ) ,

∀r ∈ [rL , rU ].

, 1 − FW (w∗ (r, −ε)) ∈ 1 − FW (whi ), 1 − FW (wlo ) ,

which is exactly what Algorithm 2 outputs. Composing with r = (z/β)1/p , we justify that ge± (z) ∈ [g ±,i , g ±,i ] is true for all i ∈ [m], z ∈ Ii . Termination of the Adaptive Refinement Loop. eventually constructs a partition such that

We show that the refinement loop in Algorithm 1 terminates, i.e., it

(A − A) + eε (B − B) ≤ ηint . Over the compact interval [0, zmax ], the functions ge± (z) take values in [0, 1] and are Borel-measurable (indeed, they are continuous except possibly at z = 0, and bounded everywhere). Hence, for every error bound η > 0 there exists a partition of [0, zmax ] such that the oscillation of ge± on each bin is at most η, except possibly on bins that touch 0. For bins touching 0, even the trivial enclosure [0, 1] contributes at most their Gamma mass to the error accumulator; since k > 0 the Gamma measure of [0, ζ] tends to 0 as ζ ↓ 0, so by refining near 0 we can make the total contribution of such bins arbitrarily small. We also note that the accumulated bracket width is a probability-weighted sum of binwise oscillations, and hence does not scale with the number of bins. Formally, pick η > 0 such that (1 + eε )η ≤ ηint /2. Choose ζ ∈ (0, zmax ) so that (1 + eε ) Pr[Z ∈ [0, ζ]] ≤ ηint /2. On [ζ, zmax ], bounded (and continuous) functions are uniformly continuous, so there exists a finite partition of [ζ, zmax ] in which each bin has oscillation at most η for both ge− and ge+ . Using the correctness property of E NCLOSE G on those bins then yields X πI (g −,I − g −,I ) + eε (g +,I − g +,I ) ≤ (1 + eε )δ ≤ ηint /2. I⊆[ζ,zmax ]

For bins contained in [0, ζ], even the trivial enclosure [0, 1] gives X πI (g −,I − g −,I ) + eε (g +,I − g +,I ) ≤ (1 + eε ) Pr[Z ∈ [0, ζ]] ≤ ηint /2. I⊆[0,ζ]

Optimality of the High-Dimensional Gaussian Mechanism and Improved Low-Dimensional Mechanisms for DP

Algorithm 4 Parameterized SGG Mechanism Mα,p SGG 1: Input: A vector-valued query q(G) ∈ RT with ℓ2 sensitivity s > 0, privacy parameters (ε, δ), fixed (α, p) with

α ∈ (−1, T − 1], p > 0, η-tight upper-bound oracle OracleSGG (Definition 4.3), tolerance τ > 0. 2: β lo ← 1 3: while OracleSGG (α, p, β lo , ε, s) > δ do β lo ← β lo /2 4: β hi ← β lo 5: while OracleSGG (α, p, β hi , ε, s) ≤ δ do β hi ← 2β hi 6: while β hi /β lo > 1 + τ do 7: β mid ← (β lo + β hi )/2. 8: if OracleSGG (α, p, β mid , ε, s) ≤ δ then β lo ← β mid else β hi ← β mid 9: end while 10: β ← β lo . 11: Output: q(G) + X, where X ∼ SGG(α, β, p).

Adding the two contributions gives (A − A) + eε (B − B) ≤ ηint . Since Algorithm 1 refines by repeatedly splitting the bin with largest contribution to (A − A) + eε (B − B), its mesh size tends to 0 and it must eventually reach a refinement at least as fine as the existence argument above; therefore it terminates. Conclusion.

Let D = A − eε B and let b = (A + τ ) − eε B, D

δµ∗ (ε) = max{0, D}.

b δb = max{0, D},

b ≥ D (hence δb ≥ δ ∗ (ε)). This is because We first show D µ A = A≤zmax + (A − A≤zmax ) ≤ A + τ,

B ≥ B≤zmax ≥ B,

b and therefore D = A − eε B ≤ (A + τ ) − eε B = D. b − D. Using the decompositions A = A≤z Next, we upper bound D max + A>zmax and B = B≤zmax + B>zmax with 0 ≤ A>zmax , B>zmax ≤ τ , we have b − D = (A − A≤z ) + (τ − A>z ) + eε (B≤z D − B) + eε B>zmax max max max ≤ (A − A) + eε (B − B) + (1 + eε )τ ≤ ηint + ηtail = η. b − D ≤ η, which is exactly Equation (16). So we Finally, since x 7→ max{0, x} is 1-Lipschitz, 0 ≤ δb − δµ∗ (ε) ≤ D conclude that Algorithm 1 is an η-tight upper-bound oracle, and such an oracle exists. With Lemma 4.3 in hand, we show some supplementary statements needed for our mechhanism in Algorithm 4. Lemma C.1 states that, for fixed (α, p), changing the rate parameter β simply rescales the SGG noise by a factor λ = β −1/p . Equivalently, SGG(α, β, p) is the distribution of λ X1 for X1 ∼ SGG(α, 1, p). Lemma C.1. Fix T ≥ 2, α > −1, p > 0, and β > 0, and define λ = β −1/p . Let R1 ∼ GGamma(α, 1, p) and U ∼ Unif(S T −1 ) be independent, and let X1 ≜ R1 U ∼ SGG(α, 1, p). Then R ∼ GGamma(α, β, p)

⇐⇒

R = λR1 ,

and consequently, X ∼ SGG(α, β, p)

⇐⇒

X = λX1 .

Proposition C.1 (Monotonicity in the rate parameter β). Fix T ≥ 2, α ∈ (−1, T − 1], p > 0, and ε ≥ 0. For β > 0, let Xβ ∼ SGG(α, β, p) and let δµ∗ (ε; β) denote the optimal delta for the neighboring pair (Xβ , Xβ + µ) at level ε. Then, for any fixed shift µ ∈ RT , the mapping β 7→ δµ∗ (ε; β) is non-decreasing. Equivalently, for 0 < β1 ≤ β2 , δµ∗ (ε; β1 ) ≤ δµ∗ (ε; β2 ). 26

Optimality of the High-Dimensional Gaussian Mechanism and Improved Low-Dimensional Mechanisms for DP d

Proof. Let λ(β) = β −1/p . By Lemma C.1, we may write Xβ = λ(β) X1 where X1 ∼ SGG(α, 1, p). Consider the invertible map φλ (x) = x/λ. Since hockey-stick divergence (and hence δµ∗ (ε)) is invariant under bijective transformations, we have δµ∗ (ε; β) = δ ∗ ε; Xβ , Xβ + µ = δ ∗ ε; φλ(β) (Xβ ), φλ(β) (Xβ + µ) ∗ = δ ∗ ε; X1 , X1 + µ/λ(β) = δµ/λ(β) (ε; 1). Now fix 0 < β1 ≤ β2 . Then λ(β1 ) ≥ λ(β2 ), hence µ µ ≤ . λ(β1 ) 2 λ(β2 ) 2 Applying the shift monotonicity result Lemma 4.2 to the base distribution X1 ∼ SGG(α, 1, p) yields ∗ ∗ (ε; 1). (ε; 1) ≤ δµ/λ(β δµ/λ(β 2) 1)

Substituting back proves δµ∗ (ε; β1 ) ≤ δµ∗ (ε; β2 ). Algorithm 5 Spherical Generalized Gamma Mechanism 1: Input:

• T ∈ N>0 , the query dimension, s > 0, the query’s ℓ2 sensitivity • ε > 0, δ ∈ [0, 1], the desired privacy parameters • q(G) ∈ RT , query result • OracleSGG which on input T, α, p, β, ε outputs an upper bound for δ. • err : [0, T − 1] × R>0 × R>0 7→ R>0 , the error function for generalized gamma distribution 2: Parameters:

• α ∈ [0, T − 1], β > 0, p > 0 the parameters of the generalized gamma distribution 3: Set the noise budget upper bound cupp such that the standard Gaussian mechanism that achieves (ε, δ)-DP introduces

error cupp . Also set cmid ← 1. 4: δ ∗ ← ∞ 5: // Perform a binary search over c ∈ [1, cupp ] to find the smallest feasible noise level 6: while δ ∗ > δ ∨ (|δ ∗ − δ| > atol ∧ clow − cupp > atol) do 7: if δ ∗ ≤ δ then set cupp ← cmid else set clow ← cmid 8: cmid ← (clow + cupp )/2 9: Solve the 2-dimensional optimization problem α∗ , p∗ ← arg min OracleSGG (T, α, β, p, ε) α,p

// β and β ∗ below computed via Algorithm 4 on input s, ε, α, p and target δ̂, constrained to noise budget cmid 10: δ ∗ ← OracleSGG (T, α∗ , β ∗ , p∗ , ε) 11: end while 12: Output: q(G) + RU, where R ∼ GGamma α∗ , h(α∗ , p∗ , cmid ), p∗ and U ∼ Unif(S T −1 ). Theorem C.1. The mechanism Mα,p SGG (Algorithm 4) is (ε, δ)-differentially private. Proof. Fix neighboring databases G ∼ G′ . Let µ = q(G) − q(G′ ) ∈ RT , and we know ∥µ∥2 ≤ s by the assumption on q(·). The mechanism in Algorithm 4 outputs Mα,p SGG (G) = q(G) + Xβ ,

′ ′ Mα,p SGG (G ) = q(G ) + Xβ ,

where Xβ ∼ SGG(α, β, p) and β is the value returned by the bracketing-and-bisection procedure. 27

Optimality of the High-Dimensional Gaussian Mechanism and Improved Low-Dimensional Mechanisms for DP α,p ′ By translation invariance, distinguishing Mα,p SGG (G) from MSGG (G ) is equivalent to distinguishing Xβ from Xβ + µ. Thus, the optimal δ at level ε for the pair of the mechanism outputs equals δµ∗ (ε; β), the optimal δ(ε) between Xβ and Xβ + µ.

By the shift monotonicity result Lemma 4.2, the map µ 7→ δµ∗ (ε; β) is non-decreasing in ∥µ∥2 , hence for any µ with ∥µ∥2 ≤ s and any fixed β, δµ∗ (ε; β) ≤ δµ∗ s (ε; β)

for any µs ∈ RT with ∥µs ∥2 = s.

Applying the oracle guarantee in Definition 4.3 to µs gives δµ∗ s (ε; β) ≤ OracleSGG (α, p, β, ε, ∥µs ∥2 ) = OracleSGG (α, p, β, ε, s). The chosen β is feasible for the target (ε, δ). By construction, the algorithm maintains a feasible lower bracket β lo with OracleSGG (α, p, β lo , ε, s) ≤ δ and an infeasible upper bracket β hi with OracleSGG (α, p, β hi , ε, s) > δ. The update rule in the bisection step relies on the monotonicity in β (Proposition C.1) to preserve feasibility/infeasibility of the brackets. At termination the algorithm sets β ← β lo , and therefore OracleSGG (α, p, β, ε, s) ≤ δ. Combining the last two inequalities, we conclude that for every neighboring G ∼ G′ , the output distributions satisfy the (ε, δ)-DP inequality. Formally, δµ∗ (ε; β) ≤ OracleSGG (α, p, β, ε, s) ≤ δ, i.e., Mα,p SGG is (ε, δ)-differentially private. C.3. Finding Optimal Parameters of the SGG Mechanism Finally, based on Algorithm 4 that finds best β for fixed (ε, δ, α, p), we provide Algorithm 5, which finds the parameters (α∗ , β ∗ , p∗ ) with minimal MSE given target privacy (ε, δ). C.4. Finding Settings where SGG Dominates Here we present Algorithm 6, which for a given T, s, ε, finds the δ in which the SGG has the biggest advantage over both the Gaussian and ℓ2 mechanisms. Algorithm 6 Finding Optimal Advantage 1: Input: T ∈ N>0 , the query dimension, s > 0, the query’s ℓ2 sensitivity, and ε > 0, the desired privacy parameter. 2: Set δ low ← 0, δ upp ← 0.1. 3: // Perform a binary search over δ ∈ [δ low , δ upp ] to find the largest advantage 4: while δ upp − δ low > atol do 5: δ mid ← (δ low + δ upp )/2 6: Use Algorithm 5 to find (α∗ , β ∗ , p∗ ) achieving minimal MSE c∗ of the SGG for T -dimensional query with sensitivity

s and privacy parameters (ε, δ). 7: Compute MSE cℓ2 and cG of ℓ2 and Gaussian mechanisms, respectively for the above setting. 8: if (cG − c∗ )/cG < (cℓ2 − c∗ )/cℓ2 then set δ upp ← δ mid else set δ low ← δ mid 9: end while 10: Output: (α∗ , β ∗ , p∗ ), c∗ .

D. Privacy Accounting of SGG Mechanisms In this section, we study tight composed privacy for SGG mechanisms under multiple invocations. Our approach follows the FFT-based accountant developed by (Gopi et al., 2024). Their work casts privacy accounting in terms of the privacy-loss random variable (PRV). The central benefit is that privacy losses add: the PRV of a k-fold 28

Optimality of the High-Dimensional Gaussian Mechanism and Improved Low-Dimensional Mechanisms for DP

Algorithm 7 Privacy Accounting for Mα,p SGG under k invocations 1: Input: Dimension T , sensitivity s, SGG parameters (α, β, p), composition count k, target ε 2: Discretization parameters: truncation L > 0, step size h > 0, odd grid size M = 1 + ⌈2L/h⌉ 3: Numerical parameters: radial quadrature size K, angular grid size Nw , arithmetic precision prec

// Discretize the single-step PRV 4: Define grid centers zi ← −L + ih for i = 0, 1, . . . , M − 1 and bin edges bi ← zi − h2 . 5: For each edge bi , approximate Pr [Z ≤ bi ] using a K-node Gauss–Laguerre quadrature (cf. Equation (17)). 6: Set the pmf πi ← Pr [Z ≤ bi+1 ] − Pr [Z ≤ bi ]

// Compose by FFT convolution 7: Compute the k-fold convolution π (∗k) using FFTs, cropping back to the support [−L, L] after each multiplication

(per (Gopi et al., 2024)) // Output the composed privacy guarantee PM −1 (∗k) 8: Compute δk (ε) ← i=0 πi · 1 − eε−zi + 9: Return (ε, δk (ε)) composition is the sum of k single-step PRV. This reduces tight (ε, δ) accounting to (i) characterizing the distribution of the single-step PRV and (ii) computing the distribution of its k-fold sum via repeated convolution. These two observations allows computing tight composed privacy efficiently by using FFTs after discretizations of single-step PRV. We follow (Gopi et al., 2024) along its theoretical analysis, and tailor the missing SGG-specific component: an efficient discretization of the single-step PRV using the one-dimensional integral reduction from Section 4.1. To discretize the single-step PRV Z for an SGG mechanism, we use the standard approach of placing a grid on the privacy-loss axis and computing bin masses from CDF differences at grid edges. Thus, efficient discretization amounts to evaluating the PRV CDF Pr [Z ≤ z] at many grid points. Lemma D.1 makes this feasible: it expresses Pr [Z ≤ z] as a one-dimensional raidal integral via the same technique used in Section 4.1. Lemma D.1. (Proof is below) Adopt the setup and notation of Lemma 4.1. Let X ∼ SGG(α, β, p) and define the PRV for the pair (X, X + µ) by def

Z = log

fX (X) . fX (X + µ)

Then, for every z ∈ R, Z ∞ Pr [Z ≤ z] =

fR (r)FW w⋆ (r, −z) dr,

where fR and FW are as in Lemma 4.1, and w⋆ (r, ·) denotes the corresponding threshold map. The next step is to increase the efficiency of evaluations of Pr [Z ≤ z] over the discretization grid. The efficiency tricks exploit the independence between random variable R and the monotonicity of w 7→ ℓ(r, w). First, we approximate the one-dimensional radial (r) integral by a K-node Gauss–Laguerre quadrature after the change of variables t = βrp , leading K fixed radii {rk }K k=1 and weights {ωk }k=1 such that Pr [Z ≤ z] ≈

K X

ωk FW w∗ (rk , −z) .

(17)

k=1

Second, for each quadrature node rk we precompute a dense lookup table of the strictly decreasing map w 7→ ℓ(rk , w) on a grid over w ∈ [−1, 1]; thereafter, each threshold w∗ (rk , −z) is computed as a table lookup followed by linear interpolation. Third, we evaluate FW (·) in vectorized form and complete each CDF query with a single dot product against the cached weights. With these caches, computing Pr [Z ≤ z] costs essentially O(K) floating-point operations per z. We also (re)use parallel workers to amortize overhead in practice. Algorithm 7 describes the full SGG-tailored accounting algorithm. We also note that as the ℓ2 mechanism is a special case of SGG (e.g., (α, p) = (T − 1, 1) with an appropriate scale), this yields a practical tight accountant for its composed approximate-DP guarantees as well; more broadly, the same pipeline applies to any (α, β, p) and to mixed compositions by convolving the corresponding discretized PRVs. 29

Optimality of the High-Dimensional Gaussian Mechanism and Improved Low-Dimensional Mechanisms for DP

Figure 3. MSE Required for privacy target (εtot , δtar ) = (1, 10−5 ) under k invocations: sequential composition versus Algorithm 7.

Experimental Evaluation. Figure 3 compares the noise level (measured by the mean-squared error (MSE) of the SGG mechanisms) required to meet a fixed composed privacy target under two accounting methods: (i) the baseline sequential composition bound and (ii) our SGG-tailored FFT accountant in Algorithm 7. Concretely, we fix a total privacy target (εtot , δtar ) = (1, 10−5 ) and consider k ∈ {2, 4, 8, 16, 32} invocations of the same SGG mechanism Mα,p SGG in dimension T = 10 (with fixed shape parameter α = 9 and p = 1). For each k and for each accountant, we compute the minimal per-invocation MSE such that the k-fold composition satisfies δk (εtot ) ≤ δtar . For the sequential baseline, we allocate a per-step budget (εtot /k, δtar /k) and solve for the smallest noise meeting this single-step guarantee (cf. Algorithm 4); for the FFT accountant, we instead solve for the smallest noise such that the computed composed optimal delta from Algorithm 7 meeting δtar at the privacy level εtot . Figure 3 shows a clear and growing gap as k increases between the the baseline accountant and our SGG-tailored FFT accountant. It illustrates the practical impact of tight accounting Proof of Lemma D.1. Write X = RU with R ∼ GGamma(α, β, p) independent of U ∼ Unif(S T −1 ), and let W =

⟨µ, U ⟩ ∈ [−1, 1]. ∥µ∥2

By the spherical form of the SGG density (see the derivation in the proof of Lemma 4.1), the log-density ratio (−Z) Lneg (X) = log

fX (X + µ) fX (X)

can be written as a deterministic function of (R, W ): Lneg (X) = ℓ(R, W ), where for each r > 0 the map w 7→ ℓ(r, w) is strictly decreasing on [−1, 1] (again, proved in Section C.1). Hence, for every y ∈ R and r > 0, there is a unique threshold w∗ (r, y) ∈ [−1, 1] such that ℓ(r, w∗ (r, y)) = y, and {ℓ(r, W ) ≥ y} ⇐⇒ {W ≤ w∗ (r, y)}. Now note that the PRV in this lemma is the negative of Lneg (Z = −Lneg (X) = −ℓ(R, W )). Therefore, conditioning on R = r and using the monotonicity property, Pr [Z ≤ z | R = r] = Pr [ℓ(r, W ) ≥ −z] = Pr [W ≤ w∗ (r, −z)] = FW w∗ (r, −z) . 30

Optimality of the High-Dimensional Gaussian Mechanism and Improved Low-Dimensional Mechanisms for DP ε

δclaimed

σ⋆

δtrue (ε)

0.1 1.0 2.0 4.0 8.0

−5

0.798721 0.798721 0.798721 0.798721 0.798721

25.040031 2.504003 1.252002 0.626001 0.313000

0.813284 0.983594 0.995020 0.998804 0.999755

10 10−5 10−5 10−5 10−5

Table 3. Testing (Ji & Li, 2024, Theorem 5) calibration for R1SMG at T = 128 and s = 1 with δclaimed = 10−5 . We compute ψ and the prescribed σ⋆ from the theorem, then evaluate the resulting privacy δtrue (ε) via Lemma 4.1. The computed δtrue (ε) is vastly larger than 10−5 , contradicting the claimed guarantee.

Finally, since R is independent of W , integrating over R yields Z ∞ Z ∞ Pr [Z ≤ z] = fR (r) Pr [Z ≤ z | R = r] dr = fR (r)FW w∗ (r, −z) dr, 0

which is exactly the claim.

E. Error in Proof of (Ji & Li, 2024, Theorem 5) Here we identify an error in the proof of Theorem 5 in (Ji & Li, 2024). The proof attemtps to analyze the Privacy Loss Random Variable (PRV) of their (spherical) R1SMG mechanism. One important fact about the PRV is that it is defined over the randomness of only the random variable M(q(G)), and not the randomness of the random variable M(q(G′ )) def

(where G′ is an allowed neighbor of G). Indeed, consider random variable Y = M(q(G)); the PRV is the function fM(q(G)) (Y ) def L(Y ) = ln , fM(q(G′ )) (Y ) where fM(q(G)) is the density of M(q(G)) and likewise for fM(q(G′ )) . However, the proof of (Ji & Li, 2024) defines the PRV L as a function of some unspecified vector s and analyzes the PRV over the randomness of both M(q(G)) and M(q(G′ )). Indeed, they bound the distribution of the angle between the uniformly random directions of the noises used in M(q(G)) and M(q(G′ )), and conclude that this angle must be close to π/2. However, the more appropriate distribution to def

analyze would be the angle between the noise used in M(q(G)) and the difference vector µ = q(G) − q(G′ ). By similar analysis, it is actually this angle that is close to π/2. This is much different than the angle between the directions in which the noises in M(q(G)) and M(q(G′ )) must point to hit Y , which the authors seem to attempt to study when considering the ratios of the densities fM(q(G)) and fM(q(G′ )) on Y ; this angle actually can be far from π/2 since the direction of the noise from q(G′ ) to hit Y will be quite different than the direction of the difference vector µ. E.1. Numerical contradiction of the claimed R1SMG calibration According to (Ji & Li, 2024, Theorem 5), the R1SMG mechanism is (ε, δ)-DP if its corresponding rank-1 noise parameter σ⋆ satisfies ψ(T, δ) =

δclaimed Γ T −1 2 √ π Γ T2

σ⋆ (ε) ≥

2s2 . ε ψ(T, δclaimed )

2 ! T −2

We test this claim in dimension T = 128 with sensitivity s = 1 at target δ = 10−5 , for ε ∈ {0.1, 1, 2, 4, 8}. For each 2s2 ε, we instantiate the R1SMG mechanism using the minimal value σ⋆ (ε) = ε ψ(T,δ) defined above, and then compute the instantiated mechanism’s actual optimal delta δtrue (ε) via Lemma 4.1. This is because the R1SMG noise is a member of the SGG noise family, so we can use Lemma 4.1 to analyze its privacy. Concretely, the R1SMG noise is rank-1 Gaussian √ along a random direction; equivalently, it is spherical with half-normal radius R = σ⋆ |Z| for Z ∼ N (0, 1). In SGG’s 31

Optimality of the High-Dimensional Gaussian Mechanism and Improved Low-Dimensional Mechanisms for DP

parameterization, this corresponds to an SGG mechanism with parameters α = 0,

p = 2,

β=

1 . 2σ⋆

Table 3 show a dramatic violation: across ε ∈ {0.1, 1, 2, 4, 8}, the computed δtrue (ε) ranges from 0.813 to 0.9998, vastly larger than the claimed δ = 10−5 .

Record · ID 267581 · SHA-256 88991b41ab79c1e8
Retrieved via Conceptio — every document is proof-bundled with source, license, and retrieval metadata.