A Central Limit Theorem for Differentially Private Query Answering
Authors: Jinshuo Dong
Weijie J Su
Linjun Zhang
Venue: NeurIPS 2021 Spotlight (2021)
Keywords: differential privacy
central limit theorem
uncertainty principle
Cramer-Rao lower bound

Abstract: Perhaps the single most important use case for differential privacy is to privately answer numerical queries, which is usually achieved by adding noise to the answer vector. The central question is, therefore, to understand which noise distribution optimizes the privacy-accuracy trade-off, especially when the dimension of the answer vector is high. Accordingly, an extensive literature has been dedicated to the question and the upper and lower bounds have been successfully matched up to constant factors (Bun et al.,
2018; Steinke & Ullman, 2017). In this paper, we take a novel approach to address this important optimality question. We first demonstrate an intriguing central limit theorem phenomenon in the high-dimensional regime. More precisely, we prove that a mechanism is approximately Gaussian Differentially Private (Dong et al., 2021) if the added noise satisfies certain conditions. In particular, densities proportional to $\mathrm{e}^{-\|x\|_p^\alpha}$, where $\|x\|_p$ is the standard $\ell_p$-norm, satisfies the conditions. Taking this perspective, we make use of the Cramer--Rao inequality and show an "uncertainty principle"-style result: the product of privacy parameter and the $\ell_2$-loss of the mechanism is lower bounded by the dimension. Furthermore, the Gaussian mechanism achieves the constant-sharp optimal privacy-accuracy trade-off among all such noises. Our findings are corroborated by numerical experiments.

A Central Limit Theorem for Differentially Private Query Answering
Jinshuo Dong
Weijie J. Su Department of Statistics and Data Science University of Pennsylvania suw@wharton upenn edu
Department of Computer Science Northwestemn University and IDEAL* Inshuo@mottwesterr..ee
Linjun Zhang
Department of Statistics
Rutgers University
linjun un. whangouuters..com edu
Abstract
Perhaps the single most important use case for differential privacy is to privately answer numerical queries, which is usually achieved by adding noise to the answer vector. The central question is, therefore, to understand which noise distribution optimizes the privacy-accuracy trade-off, especially when the dimension of the answer vector is high. Accordingly, an extensive literature has been dedicated to the question and the upper and lower bounds have been successfully matched up constant factors [BVV88 (U17]. In this paper, we take a novel approach to address this important optimality question. We first demonstrate theorem phenomenon in the nigh-dimensional regime. More precisely. we prove that mechanism approximately Gaussian Differentially Private [DRS2I] if the added noise satisfies certain conditions. In particular, densities proportional to e || where ||>||p is the standard f--norm, satisfies the conditions. Taking this perspective, we make use the Cramer-Rar inequality and show a "uncer- tainty principle" -style result: the product of privacy parameter and the f2-loss of the mechanism is lower bounded by the dimension. Furthermore, the Gaussian mechanism achieves the constant-sharp optimal privacy-accuracy trade-off among all such noises. Our findings are corroborated by numerical experiments.
intriguing central limit
Introduction
Introduced in [DMNS06]. to date differential privacy (DP) is perhaps the most popular privacy definition. One of the most important applications differential privacy answer numeric queries. Given function f of interest, which is also termed query, our goal is to evaluate this (potentially vector-valued) query f on the sensitive data. To preserve privacy, DP mechanism M working on dataset D, in its simplest form, is defined as
M(D) = f(D) +
(1)
Above, X denotes the noise term and t is a scalar, which together are selected depending on the properties of the query f and the desired privacy level. Among these, perhaps the most popular examples are the Laplace mechanism and the Gaussian mechanism where the noise follows the Laplace distribution and the Gaussian distribution, respectively.
the Institute for Data, Econometrics, Algorithms, and Learning
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

Aside from privacy considerations, the most important criterion of an algorithm is arguably the estimation accuracy the face of choosing, for example, between the Laplace mechanism or its Gaussian counterpart for a given problem. To be concrete, consider a real-valued query f with sensitivity 1-that is, A ff = supp, D' If(D) - [(') = 1, where the supremum is over all neighboring datasets D and D'. Assuming (e, ODDP for the mechanism M, we are interested in minimizing its E loss defined as
err(M) == ((M((D) ( = PEX².
This question commonly
p addressed by setting X to a standard Laplace random variable and t= e [MNS06]. This gives err(M) 2s Moving forward, we relux the privacy constraint from (e, D to (E, 6D- for some small 8. The canonical way. which was born together with the notion of (e, 8) DP, is to add Gaussian noise (6) A well-known result demonstrates that Gaussian mechanism with X being the standard normal and f ! /2loglll111 (1.2g(1.256- is (c, 6)-DP (see,
e.g.. (RR44). The f2-loss is err(M) = (2 = 2x- log((1 (1.255-))
A quick comparison between the two errors reveals a surprising message. The latter error 2: 2z-2. log((.256 ) is larger than the former 2=- In fact, the extra factor log (g(2125881)) is al- ready greater than 10 when = 10-5 At least on the surface, this observation contradicts the fact that (c, 5)- is relaxation of (e, O)-DP. Put differently, moving from Laplace to Gaussian, both privacy and accuracy get worse. Nevertheless, this contradiction suggests that we need a better alter- native to the Gaussian mechanism instead of giving up the notion of (E, 6)-DP. Indeed, the truncated Laplace mechanism has been proposed as a better alternative to achieve (e, o)-DP [GDGK20). which outperforms the Laplace mechanism in terms of estimation accuracy
Motivated by these facts concerning the Laplace, Gaussian, and truncated Laplace mechanisms, one cannot help asking:
(Q1) Why was the truncated Laplace mechanism not considered in the first place? Are there any insights behind the design of such mechanisms?
(Q2) More importantly, are these insights inherent for answering one-dimensional queries, or can we extend them to high-dimensional setting?
In this paper, we tackle these fundamental questions, beginning with explaining in Section 2 from the recision-theorede perspective of DP [WZ10] KOV17 DRS21]. However, main focus (22) In addressing this question, we uncover a seemingly surprising phenomenon - it is impossible to utilize the (s, 6) privacy budget in tighedimensional problems the same way as the truncated Laplace mechanism utilizes in the one-dimensional problem. More specifically, we show a central limit behavior of the additin mechanism in high dimensions, which, roughly speaking, says that for general noise distributions, the corresponding mechanisms all behave like a Gaussian mechanism. The formal language of "a mechanism behaves like the Gaussian mechanism" has been set up in (DRS21) where a notion called Gaussian Differential Privacy (GDP) was proposed. Roughly speaking, a mechanism is GDGDP if offers as much privacy as adding N (0, μ 2) noise a sensitivity-I query. As in the (s, 6DD case, the smaller μ is, the stronger privacy is offered.
To state our first main contribution, let f be ne-dimensional query and assume that its Ez-sensitivity is 1. Consider the noise addition mechanism M(D) = f(D) + tX where X has a log- concave density & e -xx) on R". Let Ix := ((xx( be the n x n Fisher information matrix and |I 212 be its operator norm. Theorem 1.1 (Central Limit Theorem (Informal version of Theorem 3.1 Under certain conditions on y,, for I = 1-1 /IIxx (|2, the corresponding noise addition mechanism M defined in Eq.(T) is asymptotically y-GDP as the dimension n. + oa except for an o(1) fraction of directions of F(D) ((D)-((D)) f(D).
In particular, the norm power functions x<x)= = | (p, a > 1) satisfy these technical conditions. Note that this class already contains correlated noise, so the results in [DRS2T] do not apply here. Numerical results in Figure shows that the convergence occurs for dimension as small as 30.
"If f is intgee-vvalued then the doubly geometric distribution is better choice and yields an loss of sinh -2 5 < 2. -2 In the so-called high privacy regime, i.e. 0, the two lossosses have the same order in the sense that their ratio goes to 1.
'One may blame the sub- cubboptimality of the choice of t, but the problem remains even if the smallest possible
t from BWI8 is applied.

---

(x(x)
| l|
sp(x)
||/||
(=(x)
0.58 | 11::3
GDP
GDP
GDP
Numerical
Numerical
Numerical
0.8
ope elerrot
oypa e1
syper e
00.6
0.6
0.6
0.4
0.4
0.4
0.2
0.2
0.2
0.00
0.25
0.50
0.75
1.00
0.00
0.25
0.50
0.75
1.00
0.00
0.25
0.50
0.75
1.00
type exror
type ervor
type ecror
Figure 1: Fast convergence to GDP as claimed in Theorem 1.1 Blue solid curves indicate the true privacy (i.e. ROC functions, see Section for details) of the noise addition mechanism considered in Theorem L.1 Red dashed curves are GDP limit predicted by our CLT. In all three panels the
dimension n = 30. Numerical details can be found in the appendix.
We then elaborate on the condition "o(1) fraction of ((D)- Following the original definition, DP or GDP is a condition that needs to hold for arbitrary neighboring datasets 1 and D'. This worst case perspective exactly what prevents us to observe the central limit behavior. For example, consider a certain pair of datasets with J(D) = (0, O......... 0) and f(D") = (1, O.... 0), then privacy completely determined by the first marginal distribution of X, and the dimension n plays no role here. The "o(1) fraction of fDD f(D)"" rules out the essentially low-dimension cases and reveals the truly high-dimensional behavior.
In summary, Theorem 1.1 suggests that when the dimension is high, a large class of noise addition mechanisms behave like the Gaussian mechanism, and hence are doomed to a poor use of the given (s, 6) privacy budget, in the same fashion as we have seen in the one-dimensional example.
However, admitting the central limit phenomenon, our second theorem turns the table and charac- terizes the optimal rrivac--accurae trade-off and justifies the Gaussian mechanism. To see this, recall that the noise addition mechanism defined in Equation (T) is determined by the pair (t, X). Both privacy and accuracy are jointly determined by t and X. Ädopting the central limit theorem 1.1 it is convenient to take an equivalent parametrization, which is X), where μ is the desired (asymptotic) GDP parameter. Given X, the two parametrizations are related by = p Z 2 Using parameters (p, X), the corresponding mechanism M,,xx is given by
Mp, = f(D) +
I X
By Theorem 1. it asymptotically μ-GDP. The following theorem states in an "uncertainty principle" fashion that the privacy parameter and the error cannot be small at the same time.
Theorem 1.2. As long as the Fisher information of X is defined, we have
1²² eer( M p,,x) E n.
The equality holds if X is n- r-ddmmensionl standard Gaussian.
Combining Theorems 1.I and 1.2 among all the noise that satisfies the conditions of Theorem 1.1 Gaussian yields the constant-she -harp optimal privacy-accurac trade-off. As far as we know, this is the first result characterizing optimality with the sharp constant when the dimension is high.
The privacy conclusion of Theorem T.T does not work for every pair of neighboring datasets, so is worth noting that we do NOT intend to suggest this as a valid privacy guarantee. Instead, we present it as an interesting phenomenon that has been largely overlooked in the literature. Furthermore, this central limit theorem admits an elegant characterization of crivacy-accurae trade-off that is sharp in constant. From a theoretical point of view, the proof of Theorem i.1 as we shall see in later sections, involves non-linear functionals of high dimensional distributions. This type of results are, to the best of our knowledge, quite underexplored compared to linear functionals, so our results may serve as an additional motivation to study this type of questions.
3

---

Related work There is a large body of literature on the characterization of privacy-accuracy trade- off for query answering mechanisms. For the -ieeemmesionnal case, the constant- sharp optimal noise for (e, 0)-DP was shown to have piece-wise constant density by [GV16]. This complements our discussion in Figure When the dimension is high, only up-to-constant- factor optimality was known. In particular, [BVIIS] 18, SU17 confirm that Gaussian mechanism is minimax rate optimal under (e, 6)- DP by a novel lower bound technique. In addition, [ENU20] also confirms the minimax optimality of Gaussian mechanism for linear queries with a refined notion of sensitivity. Our work extends this direction by taking the CLT perspective and providing an elegant constant-sharp optimality result. There are also works studying the appto-constant-toe factor minimax optimality in other models, such as the (sparse) linear regression [CWZ21]] generalized linear models [CWZ20, SSTT21], Gaussian mixtures [KSSU20 [ZZ21] and on. In our work, initialize the investigation in the (simpler) mean estimation problem, and leave the constant-sharp optimality in other problems for future work.
2 GDP and the ROC Functions
The decision theoretic interpretation of DP was first proposed in [WZ1)] and then extended by [OOII]. More recently, [DRS2I] systematically studied this perspective and developed various tools. In this section we take this perspective and introduce the basics of [DRS21] This will allow us to give an intuitive answer to (QI)
Suppose each individual's 's sensitive information is an element in the abstract set X. A dataset D of k people is then an element in X². Let a randomized algorithm M take a dataset as input and let D and D' be two neighboring datasets, i.e. they differ by one individual. Differential privacy seeks to limit the power of an adversary identifying the presence of an arbitrary individual in the dataset. That is, with the output as the observation, telling apart D and D' must be hard for the adversary. Decision theoretically, the quality of an attack is measured by the errors it makes. The more error it is forced to make, the more privacy M provides.
To breach the privacy, the adversary performs the following hypothesis testing attack:
Hu : output M(D vs H1 : output M(D)..
By the random nature of M, (D) and M(D) are two distributions. We emphasize this point by denoting them by P and Q. The errors mentioned above are simply the probabilitics confusing D and D', which are commonly known false positive and false negative rates. Because of the symmetry of the neighboring relation, there is no need to worry about which is which.
ROC function. For simplicity assume M outputs vector in R". A general decision rule for testing Ho against H, has the form é Ip" > {0,1}, Observing v E TR", hypothesis H, is accepted if ((v)= = for i E (0, 1). The false positive rate (type error) of ø. i.e. mistakenly accepting H1 v ~ M(D') = Q while actually e ~ M(D) = P, is ag == P Pe)r(((v) = 1) = (r)
Similarly, the false negative rate (type II error) of Φ Bg 1 EQ (6). Note that both errors are in
[0, 1]. Consider the function fP.Q : [0, - [o, 1] defined as follows:
fP.e(a)= == inf (Ø)) ob satisfies Ep(() E a).
That is, (a) equals the minimum false negative rate that one can achieve when false negative is at most a. The graph of fPQQ is exactly the flipped ROC curve of the family of optimal tests (which, by Neyman-Pearson lemma, are the likelihood ratio tests). We call it the ROC function of the test P vs Q. The same notion is called trade-off function of P and Q in [RS21] and is denoted by T[P, Q] trade-off,
We avoid this name because in our paper "trade-off" mainly refers the but we will keep their notation.
DP and ROC function Plugging in the privacy context where p= M(D, -M(D), from the discussion above, we see that T(M(D) (D), MD)) measures the optimal error distinguishing MDD and MD'). Therefore, a lower bound on (D). (DD) implies privacy of M. Indeed,
[WZ10, KOVI7I showed that M is (E, -DP if and only if T(M (D), MD') > fe.s pointwise in
0, for any neighboring dataset D, D'. The graph of fe.8 is plotted in the left panel of Figure 2
Compared to single (s, 8) bound, the ROC function (D), M(D)) provides a more refined
picture of the privacy of M. In fact, [DRS2T] shows that the ROC function is equivalent to an infinite
family of (e, 6) bounds, which is called privacy profile in BBG20).

---

1.0
intercept =
(s.0) Laplace
(5.8)
0.8
fe
Truncated
Iudistingnsshabble
Laplare
tppe 1I arror
Gaussian
0.6
0.4
slope
0.00
0.25
01.50
0.75
1.00
type error
Type I
error
type I crear
Figure 2: Left: fe,5 which recovers the classical (e, 8)-DP definition. Middle: Laplace mechanism is
(e, DD Right: Gaussian mechanism and truncated Laplace mechanism are both (z, 8)-DP
Truncated Laplace vs Gaussian through the lense of ROC function Now we use ROC function to answer (QI))n in the introduction. Namely, we want to explain the embarrassing situation of the Gaussian mechanism that the privacy budget is not fully used, and the success of the truncated Laplace mechanism.
When M is the Laplace mechanism which is designed to be (e, D)- it is not hard to determine (DM (D') via Neyman-Pearson Pearson lemma and verify that it indeed lower bounded by fe.o (see the middle panel of Figure(). In fact, T[M M (D') mostly agrees with fe.o. In other words, the (s. 0) privacy budget is almos fully utilized.
When M is the Gaussian mechanism with (s, 6)-DP gaurantee, (D), M(D)) is naturally lower bounded by fe.s, however, there a large gap between the two curves (see the right panel of Figure 2) The (e, 8) privacy budget is poorly utilized by the Gaussian mechanism. This explains why the 12- of Gaussian mechanism is not satisfactory.
For noise addition mechanism. if the noise is bounded, say a uniform [-1, 1] distribution, then (D), (D)) fo.s for some 8 E (0,1). 1). This suggests us to consider bounded noise if we want add 8 slack in privacy to the Laplace mechanism. The obvious attempt then truncate Laplace noise. Indeed, the corresponding ROC function is as close to fe.5 that of the Laplace mechanism to fe.o (also see the right panel of Figure 2. This not only explains the success of the truncated Laplace mechanism, but also points us to the right direction in searching for such mechanism.
In hindsight, this achievement for one-dimensional mechanisms is due to the following fact: change the noise distribution, the corresponding ROC functions are significantly different. Hence we can pick the one that best utilizes our privacy budget. However, in the next section we will argue that this no longer works when the dimension is high many (if not all) choices of noise distribution yield the same ROC function, which is the ROC of Gaussian mechanism.
ROC function of the Gaussian mechanism For μa > 0, let G₂ := (o, 1), (p, 1)] where & denotes the cumulative distribution function (CDF) of the standard normal distribution. Consider query f with sensitivity I and let Lap(0. 1) be the standard Laplace noise. Just like e-DP captures the privacy of the mechanism (D) f(D) + L0p(O. 1). the function G2 captures the privacy of M(D) f(D) + - N(O, 1). In fact, if f(D) fD) 1, then M(D) N(f and M(D) ((f(D),,=3) By its hypothesis testing construction, T'P,, Q] remains invariant when an invertible transformation is simultaneously applied to P and Q, resulting in
T(M(D), (M(D),((D)) = "(
([N 1), N(J, Gy
Therefore, the privacy of Gaussian mechanism precisely captured by the ROC function G,,- A general mechanism M is said to be Gaussian differentially private (GDP) if it offers more privacy than a Gaussian mechanism. More specifically,
Definition 2.1 (GDP). An algorithm M is μ-GDP if (DM, M(D') > G₁ for any pair of neighboring datasets D and D'.
If the query valued, then (c, 0) privacy budget can be saturated by adding doubly geometric noise.
5

---

Alternatively, M is μ-GDP if and only if p, (D), M()) ROC functions is interpreted pointwise, and the infimum is taken over all neighboring datasets D and D' This inequality says M offers more privacy than the corresponding Gaussian mechanism. If the equality holds, i.e.
> Gμ where the infimum of
inf T(M(D). M(D') G D.D
then it means the mechanism M offers exact the same amount of privacy as the corresponding Gaussian mechanism. In fact, the CLT to be presented in the next section has this flavor of conclusion.
3 Central Limit Theorem
In the following two sections we turn to addressing (Q2) This section is dedicated the rigorous form of the CLT and the discussion.
The experience with the CLT for i.i.d. random variables suggests that the statement for the normalized special case is usually the most comprehensible. Therefore, we will state the normalized version as Theorem 3.1 and derive the general case as Corollary 3.2 which is also the rigorous version of our informal theorem 1.I mentioned in the introduction.
Consider n-dimensional query ʃ su (I) - f(D')ll2 = Suppose IR - is convex and e is integrable on R=. The log-concave random vector with density x ee px() will be denoted by Xg. Define the function class
X
RR.. We assume it has fz-sensitivity 1, i.e.
3n = {pp R R convex [x(x) -((==), e (R"),, ,1 +o0, E Vx((X,) < +oo}.
The regularity conditions guarantee that X₂ has finite second moments and Fisher information matrix defined as I, = E, (X, (xx(X.)) J. Furthermore, we also have EX2, by symmetry and (V,((Xp) by standard theory of Fisher information (c.g. [VdVoOJ). We will focus this class of functions for the rest of paper.
The n-dimensional noise addition mechanism of interest takes the form M(D) = S(D) + tX The parameter is only for the convenience of tuning and can be absorbed into sp In fact, tXp has log-concave density x = so it distributed as X3 where (pxx) = s(x/t). (). For the normalized CLT, we set / = 1 and assume I.p is the n x n identity matrix Inx--
Since what we are going to present an asymptotic result where the dimension n + oo, the above objects necessarily appear with an index n, i.c. we have fa, Pa, Xxn and Ip..- The latter two are often denoted by X,, and I, for brevity. With normalization, the n-dimensional mechanism of interest is M,, (D) = (D) X,, For clarity, we choose to state the theorem first, and then present the details of the technical conditions.
Theorem 3.1. If the function sequence Sn, satisfies conditions (DI) (D)) (D2) then there is sequence
of positive numbers on with Cn + as n + 0o and a subset E, S Sth with P Pa--n-1 (U E En)) >
1 Cn such that
|| inf TIM,(D), M,(D') D,D'
-Gil)e en
where the infinum is taken over D, D' such that 1=(D')-/a()) E Fn.
[,(0")-
Here ~ S means comes from uniform distribution of the unit sphere Sn-1 C RR.. The conclusion is basically that in T[M,, (D), )), M, (D') - G1, i.e. Ma asymptotically GDP. Similar to the interpretation of (3) it means the mechanism M,, provides the same amount of privacy as Gaussian mechanism in the limit of + 0o. However, a fraction of neighboring datasets has to be excluded. More specifically, the limit holds if the direction of the difference (D() fn. (D) falls in En, an "almost sure" event as the dimension n - xc As we remarked in the introduction, directions in E, can exhibit low dimensional behavior and hence must be ruled out for any high high-dimensiooal observation.
For vector v E R" and & Sn, let Pf RR" + IR be defined as (x(x) = p(< + v) ((r)) I For two random variables X and Y. their Kolmogorov-Smirno defined as the lx distance of their CDFs. A sequence of random variables is denoted by op(1) if they converge in probability to O. The technical conditions for the CLT are as follows. Note that each of them are conditions on the function sequence Pr..
distance KS(X, Y) is

---

(DI) KS(P.. Vx,((,,) = o(1) with probability at least 1 o(1) over v ~ Sn-1
(D2) [V,n(X))]l vn + op([))
Remark 1. Dropping the cumbersome subscripts n. (D1) (DI)roughly roughly asks that
Pf ( + u) (xX 202²t 2 I of (X)
Since Zp is the expectation of the Hessian of ip, we see that (DD is basically a regularity condition stating that the Taylor expansion of &p holds on average up to the second order.
Remark Condition (D2) basically says that Vx(X) mostly falls on spherical shell of radius vn
(as it should since I E (XX) is assumed to be identity). A deeper understanding is provided by an alternative interpretation of condition (D1) using new notion we propose called
"likelihood projection".
Likelihood Projection. The function P defined above is called the "likelihood projection" along direction v. It is (up to an additive constant) the log likelihood ratio of Xx and its translation X, In fact, X has density 1 Z - and X has density 1 - ==-((++)) where 7up is the common Z
normalizing constant. The log likelihood ratio is (((++)) (px)). This explains the word "likelihood", To observe its nature as a "projection", consider the special case (fx)) = ž -| Straightforward calculation suggests that I.p is identity and (x)) v² x. So it is indeed generalization of the linear projection along direction e.
The alternative interpretation of condition (DI) is that when the dimension is high, the "likelihood projection" Pf (X) is roughly linear projection the direction v. Condition (D2) then the
"thin-shell" condition proposed in Sudakov's 's theorem [Sud7]] which we state in the appendix as necessary tool for the proof of our CLT.
For the general case, consider (D) (D) + p,,, where in --1
v | 2| The factor
VIIa l2 normalizes the Fisher information to the identity, and the factor μ controls the final privacy level. For this mechanism, have
Corollary 3.2. If the function sequence ( = pp (In x)) satisfies conditions (DI) and (D2)
and that In =I[Zmp ||2 (1 + o(1)) ))) Inxm. then there is a sequence of positive numbers On and subset En. S for each n. with P Pu En) > such that
inf (MM,(D), (D') - Gulloc & On D.D'
where the infinum is taken over D, D' such that f=(D")-((()) E,, [=(0))-11(D)=
In particular, when and a belong to [1, +oo), norm powers |>:1| satisfy the above conditions.
Lemma 3.3. For p E +o0), E [1, +o0), let Cp.a ap-ap-aaa -p- I(2
tte sequence
of functions (x.( = n 1 3 Cp,a satisfies conditions (DI) and (D2) and that I, = 1Zm|122
(1 + o(1)) Inxx-
The parameter Cp.a and the power of are determined by the Fisher information, which can be found in Lemma 4.2 More generally, we conjecture that
Conjecture 3.4. All functions in 3n, satisfy (DI) and (2)
Recall that y E 3n lead to log-concave distributions. We limit the scope of our conjecture to log-concave distributions because of an interesting lemma involved in the proof of the central limit theorem 3.1 Consider the mechanism MD(D) = S(D) + tX, with the emphasis on the scaling parameter f. As f increases, M obviously loses accuracy regardless of log-concavity of X. On the other hand, when comes to privacy, we have
Lemma 3.5. When X has log lon-concave distribution and t 0, the function (D), (pointwise) monotone increasing in for any D, D'.
Since larger ROC function means more privacy, this lemma confirms that M gains privacy as I increases. In other words, confirms the existence of "privacy-aceuracy trade-off" given the log- concavity of X. Note that without log-concavity, monotonicity in the lemma need not hold. For
7

---

one-dimensional example, consider an X that supports on even numbers and f(D) - 0,f(D" = 2. When t 2. T[M'(M) (D') T2X,, 2X + T + 1]. There is no privacy in this case as X and X + 1 has completely disjoint support. On the other hand, when 1 1, (D), (D') = T X 2] and incurs some privacy. That is, more noise does not imply more privacy, hence violating the conclusion of Lemma 3.5
In summary, results in this section show that mechanisms adding noise that satisfies (DI) and (D2)
(e.g. densities -11 ( behave like a Gaussian mechanism. Changing the noise in this class does not change the ROC function by much. Hence we cannot repeat the success at fully utilizing the
(e, 6) privacy budget as in Section 2
On the other hand, our CLT involves Fisher information, and hence gives us the opportunity to relate to the (arguably) most successful tool for constant-shan lower bound the Cramer-Rao inequality. This will be the content of the next section.
4 Privacy-Accuracy Trade-off via Cramer-Rao Inequality
The central limit theorem in the previous section suggests that we use GDP parameter j to measure privacy. Adopting this, we will show that the privacy-accuracy trade-off is naturally characterized by the Cramer-Ras Rao lower bound. The conclusion has a similar flavor to the uncertainty principles.
Recall that the mechanism M(D) S(D) + 1X2, is determined by two "parameters": the shape parameter y E 3, which determines the distribution of X,, and the scale parameter If yp also satisfies the conditions of Theorem 3.1 then we can use the desired (asymptotic) GDP parameter to determine the scale parameter, i.e. = p=! T Using the equivalent parametrization (u, sp), the corresponding mechanism My..o is given by
My.0 (D) (
/11lll2-Xx
As we have explained in the introduction, one way to measure the accuracy of the mechanism is the mean squared error of the noise
err(M E||tX x- II 11
(5)
The following theorem characterizes the privacy-accuracy trade-off the product of the mean squared error err err(MH..p) and privacy parameter μ²².
Theorem 4.1 (Restating Theorem 1.2p. For any E 3n and Myse defined as in we have
e (or(MMpp))
In addition, the equality holds if the added noise X is n-dimensional standard Gaussian.
Proof of Theorem 4.1 To simplify notations will drop the subscript yp in X. We first claim that it
suffices to show the following ceerttaint--rincciple like result
Var [X] Var [Vp()] > n
(6)
where the notation Varl-] is slightly abused to denote the mean squared distance random vector from its expectation, i.e. Var[X] B[J|X EX EX]])
To see why (6) suffices, notice that by 55. the interested quantity can be simplified as
n²= cm)(M X| ||
Recall that we have EX = by symmetry of 3o and EV yz (X) by basic Fisher information theory.
So Var[V = E V (x)i3 Tr ( = TrIp. That is, eq. (6) implies
B II > n
(8)
Since I,p is positive semi-definite, by 7 and ( we have
4² e
x Il
>
E
LTYI, >
8

---

Table 1: Explicit expressions of Fisher information and mean squared error.
Density
Ipl2
X
E
E
X
E. E
E. XX
Ip
2
2n
2n
(logn)²
"(log n)
|
(2 + 1)
Y + 1
2n log
~2oog n
C
|
2 n
7
log n
~ ~loog
X e
Lemma 4.2
Lemma 4.2
Cp
Appendix
C% C% n)
Next we foeus on the proof of ( Consider the location family {X + 0 E R"). The Fisher information of this family is Iap at all O. The random vector itself is unbiased estimator of the location. Therefore, by the Cramer-Rao inequality (c.f. (Vdv00)), we have that Cov(X) - Ixp" is positive semi-definite. As a consequence.
Var [X] = Tr Cov(X) > TzZz'= +
where A .... An > 0 are the eigenvalues of Ipp. We already see that Var [xp(X) = Tr by Cauchy-Schward inequality,
Var[X] Var[V > + +1, (, + + An) > n²
The proof of the inequality is complete. For standard Gaussian, we have Cov( = Ipp = Inxn- and we have μ² err(M = || ||Z,|l2 = Tr Iax
Note that although Theorem 4.1 holds true for very general yp (only integrability conditions are im- posed in 3.). the interpretation that μ is the asymptotic privacy parameter only holds for distributions that satisfy (D1) and (D2) Therefore, let us consider the special case where ypxx) = ||=|| The corresponding X will denoted by Xp.aa and Ip by Ip.a- In this special case, we compute the quantities in ( exactly. the following lemma, we write an ~ by for the two sequences an and by DC.
if On 1
bn
Lemma 4.2. For <p < 0o and
X0, as > 00, we have < <
E X p.a
n
= a ap. pr (())/T(())))
Ip
2 2 n
p² r(2 / Inxn-
This result put Theorem 4.1 into a more concrete context. Some important cases with specific values of p and worked out in Table [ Remarkably, in the last row, the products that characerize aavvac--accrrag trade-off are asymptotically independent a. As by-product of this calculation, also derive the expression for the isotropic constant of the n-dimensional fp ball, which is an important concept in convex geometry fc.f. (BGVV14). ). See the appendix for more results and discussion.
Alternatvelly, we may want to measure the accuracy by the expected squared foo -nom the noise. A similar argument suggests to consider the following quantity 11 || By Theorem 4.1
and the fact that || > Vn ||/||, we have
E x
12
4BIX,113
|I
We would like point out connection to recently resolved open problem proposed in [SU17]. asking if there is a DP algorithm that answers a high-dimensional query with fz-sensitivity 1 with O(1) error in foo norm. In particular, the recent solution (DK20) GKM20) provides strong evidence that the lower bound in is tight up to a constant factor.
An Analogy with Uncertainty Principles There are various mathematical manifestations of the uncertainty principle. The one behind Hesenberg uncertainty principle is that function and its Fourier transform cannot both localized simultaneously. Specifically, for a function f E 1,2 (RR"). its Fourier transform is defined as f(E) = f c- -22ri((,a) f(x) dr. Fourier transform is unitary, ie.
Lf L In particular, if 2 is probability density, then is 1 Our previous

---

abuse of notation also applies here, for example, Var[]f = f(x a)² (z) dz where
(x)) dr. For I| = 1, we have the following resul (c.f. Corollary 2.8 of [FS97]
Var[If]?] Var[If]]]
(10)
16n²
The similarity between 6 and (10) suggests that Theorem can be considered as yet another manifestation of the uncertainty principle.
5 Conclusions and Future Works
In this work, we study constant-sharp optimality of noise addition algorithms for high-dimensional query answering with differential privacy. We demonstrate that the ROC function offers good insight in comparing the "actual spend vs budget" of differential privacy and hence in the design of one-dimensional algorithms. However, when the dimension is high, CLT shows that (s, 6) privacy budget cannot be fully spent for a large class of noise addition mechanisms as they all behave like Gaussian mechanism. On the other hand, Fisher information naturally arises in these high- nigh-dimensional mechanisms, and the simple and fundamental quantity "privacy parameter x error" automatically manifests itself as the quantity "information x error" in the Cramer- lower bound. Using this, we are able to show an elegant characterization of the precise arivcc-accuracyy trade-off, and justify the constant-sharp optimality of the Gaussian mechanism. We believe the insights offer a novel perspective to the long-lived privacy-accuracy trade-off question.
Various extensions possible. An immediate one extend the CLT to broader class of noise
distributions, such as log-concave distributions as specified in Conjecture 3.4 Another condition imposed by 8. (implicitly) is that the noise must supported on the whole space. The difficulty in
removing the condition lies in the lack of a definition of Fisher information for noise with bounded support. particular, one may consider extending the theories to cover the noise used in [DK20) and prove a corresponding lower bound like (9). For non-log-concar
noise, Lemma 3.5 suggests us believe that a corresponding log-concave noise with no less privacy and accuracy exists. For algorithms beyond noise addition or problems beyond query answering, we believe that they still exhibit some universal behavior as long as the dimension is high. a cireumstantial evidence, [DKTT12 shows that generic algorithms for query answering can be reduced to noise addition one with better accuracy and slightly worse privacy.
Acknowledgements
We thank Jason Hartline, Yin-Tat Lee, Haotian Jiang, Qiyang Han, Sasho Nikolov, Aravindan Vijayaraghavan and Yuansi Chen for helpful comments on earlier versions of the manuscript. J. D. was supported by the NSF HDR TRIPODS award CCF-1934931, W. J. S. was supported in part by NSF through CCF-176331 14 and CAREER DMS-184741 an Alfred Sloan Research Fellowship, and Facebook Faculty Research Award. L. Z. supported in part by NSF through DMS-2015377
Societal Impact
Private data analysis has positive societal impacts. The major negative concern is that too much utility is sacrificed for privacy. This work is intended to improve theoretical understanding of such trade-off between privacy and utility.
References
[BBG20] Borja Balle, Gilles Barthe, and Marco Gaboardi. Privacy profiles and amplification by subsampling. Journal of Privacy and Confidentiality, 10(1). 2020.
[BDKT12] Aditya Bhaskara, Daniel Dadush, Ravishankar Krishnaswamy, and Kunal Talwar. Un- conditional differentially private mechanisms for linear queries. In Proceedings of the forty-fourth annual ACM symposium on Theory of computing, pages 1269-1284, 2012.
'Hessenberg uncertainty principle is a direct consequence of Equation 10 and the fact that the position operator and momentum operator conjugate of each other via Fourier transform.
10

---

[BGVV14] Silouanos Brazitikos, Apostolos Giannopoulos, Petros Valettas, and Beatrice- Vritsiou. Geometry of isotropic convex bodies, volume 196. American Mathematical Soc., 2014.
[BUV18] Mark Bun, Jonathan Ullman, and Salil Vadhan. Fingerprinting codes and the price of approximate differential privacy. SIAM Journal on Computing. 47(5):1888 (((5):1888-1935)) 1938,, 2018.
[BW18] Borja Balle and Yu-Xiang Wang. Improving the gaussian mechanism for differential privacy: Analytical calibration and optimal denoising. In International Conference on Machine Learning, pages 403-412, 2018.
[CW720] T "Tony Cai, Yichen Wang, and Linjun Zhang. The cost of privacy in generalized linear models: Algorithms and minimax lower bounds. arXiv preprint arXiv:201 1.03900, 2020.
[CWZ21] T Tony Cai, Yichen Wang, and Linjun Zhang. The cost of privacy: Optimal rates of convergence for parameter estimation with differential privacy. The Annals of Statistics, 2021.
[DK20] Yuval Dagan and Gil Kur. A bounded-noise mechanism for differential privacy. arXiv preprint 201.22012.03817, 2020.
[DKM+06] Cynthia Dwork, Krishnaram Kenthapadi, Frank McSherry, Ilya Mironov, and Moni Naor. Our data, ourselves: Privacy via distributed noise generation. In Annual International Conference on the Theory and Applications of Cryptographic Techniques, pages 486- 503. Springer, 2006.
[DMNS06] Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise to sensitivity in private data analysis. In Theory of cryptography conference, pages 265-284. Springer, 2006.
[DR14] Cynthia Dwork and Aaron Roth. The algorithmic foundations of differential privacy. Foundations and Trends in Theoretical Computer Science, 9(3 & 4):21 1-77,, 2014.
[DRS21] Jinshuo Dong, Aaron Roth, and Weijie J Su. Gaussian differential privacy. Journal of the Royal Statistical Society, Series B, 2021. to appear.
[ENU20] Alexander Edmonds, Aleksandar Nikolov, and Jonathan Ullman. The power of factor- ization mechanisms in local and central differential privacy. In Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, pages 425-438, 2020.
[FS97] Gerald B Folland and Alladi Sitaram. The uncertainty principle: a mathematical survey, Journal of Fourier analysis and applications, 3(3):207-238. 1997.
[GDGK20] Quan Geng, Wei Ding, Ruiqi Guo, and Sanjiv Kumar. Tight analysis of privacy and utility tradeoff in approximate differential privacy. In International Conference on Artificial Intelligence and Statistics, pages 89-99. PMLR, 2020.
[GKM20] Badih Ghazi, Ravi Kumar, and Pasin Manurangsi. On avoiding the union bound when answering multiple differentially private queries. arXiv preprint arXiv:2012.09) 16, 2020.
[GV16] Quong Geng and Pramod Viswanath. The optimal noise-adding mechanism in differen- tial privacy. IEEE Transactions on Information Theory, 62(2))922-951, 2016.
[KOV17] Peter Kairouz, Sewoong Oh, and Pramod Viswanath. The composition theorem for differential privacy. IEEE Transactions Information Theory, 63(6) 2017.
[KSSU20] Gautam Kamath, Or Sheffict, Vikrant Singhal, and Jonathan Ullman. Differentially private algorithms for learning mixtures of separated gaussians. In 2020 Information Theory and Applications Workshop (ITA), pages 1-62. IEEE, 2020.
[SSTT21] Shuang Song, Thomas Steinke, Om Thakkar, and Abhradeep Thakurta. Evading the curse of dimensionality unconstrained private glms. International Conference on Artificial Intelligence and Statistics, pages
PMLR, 1021.

---

[SU17] Thomas Steinke and Jonathan Ullman. Between pure and approximate differential privacy. Journal of Privacy and Confidentiality, 7(2):-22, 2017.
[Sud78] Vladimir Nikolaevich Sudakov. Typical distributions of linear functionals finite- dimensional spaces of higher dimension. In Doklady Akademii Nauk, volume 243, pages 1402-1405. Russian Academy of Sciences, 1978.
[Vdvoo] Aad W Van der Vaart. Asymptotic statistics, volume 3. Cambridge university press, 2000.
[WZ10] Larry Wasserman and Shuheng Zhou. A statistical framework for differential privacy. Journal of the American Statistical Association, 105(489):375-389 2010.
[ZZ21] Zhe Zhang and Linjun Zhang. High-dimensional differenttilll- prrivvttlly- em algorithm: Methods and near-optimal statistical guarantees. arXiv preprint (edi::2/440002 2021.
12


Reviews:
[{"review_id": "yx6xwZLIUl8", "reviewer": "Reviewer_Dzvr", "summary": "Within the framework of f-DP, the paper establishes a CLT for high-dimensional additive noise mechanims, demonstrating that as the dimension increases, adding independent noise to the coordinates has a privacy loss similar to Gaussian noise. This result addresses the question of what noise mechanism is best applied, indicating that Gaussian noise offers the best privacy-utility tradeoff. The privacy-utility tradeoff is communicates through an \"uncertainty principle\", which shows that the product of the privacy parameter and a measure of utility are bounded, indicating that both quantities cannot be simultaneously small. They show that Gaussian noise makes this uncertainty inequality tight. \n", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "\nOriginality:\nThe notion of a CLT in terms of the privacy guarantee when many mechanisms are composed was previously established in [DRS21]. The setting considered in this paper is similar to that of [DRS21], but slightly different. For composition of mechanisms, a privacy mechanism is applied sequentially to each statistic of interest, and quantities such as sensitivity are usually evaluated for each statistic separately. In the high-dimensional setting of this paper the L_2 sensitivity of the statistic vector is assumed to be bounded, and a noise vector is simultaneously added to the statistic vector. While the setting does not seem to be contained within the setup of [DRS21], it is still fairly similar. As such, the result that the tradeoff function converges to that of a Gaussian is not very surprising. \n\nHowever, besides the work [DRS21], this paper is one of few to use classical statistics techniques (such as CLT, FIsher Information) to analyze privacy problems. As such the techniques of the paper are fairly unique among DP works. \n\n\nQuality:\nThe claims are supported with mostly theoretical results, demonstrating the CLT phenomenon and a unique privacy-utility tradeoff. Some simulations are also given to illustrate the convergence of the ROC curve to that of a Gaussian for the statistic dimension n=30. \n\n\n\nSignificance:\nDetermining privacy mechanisms that optimize the privacy/utility tradeoff are a common and important problem in DP. This paper approaches this problem from a unique perspective, looking at the privacy cost of i.i.d. additive noise as the dimension of the statistic increases. They argue from their framework that if i.i.d. additive noise is used for privacy, then Guassian noise is the ideal distribution as it makes the privacy/utility tradeoff tight. \n\nAn unfortunate problem of CLT arguments in terms of privacy cost is that the results often cannot be used for rigorous privacy guarantees. The authors note this fact, and state that the purpose of the CLTs is to highlight an interesting phenomenon, which shows that Gaussian noise offers a sharp privacy-utility tradeoff. While this makes sense, it does limit the appeal of the CLT results, since they cannot be used to argue the privacy cost of additive noise.\n\nA limitation of the scope of the paper is that the additive mechanisms considered are assumed to be i.i.d. for each entry of the noise vector. This removes the possibility of adding correlated noise. I suspect that if correlated noise were an option, then it would be possible to construct additive mechanisms whose tradeoff functions do not approach G_mu. For example, consider the K-norm mechanisms:\n\nHardt, Moritz, and Kunal Talwar. \"On the geometry of differential privacy.\" Proceedings of the forty-second ACM symposium on Theory of computing. 2010.\n\nAwan, Jordan, and Aleksandra Slavković. \"Structure and sensitivity in differential privacy: Comparing k-norm mechanisms.\" Journal of the American Statistical Association (2020): 1-20.\n\nClarity: \nThe presentation of the paper is somewhat difficult to read. Some of the mathematical results and conditions are difficult to parse (such as (D1) and (D2), as well as Theorem 3.1 and Corollary 3.2. The exposition does help in certain cases, such as in Remarks 1 & 2. \n\nHowever, in other places the exposition is also difficult to understand. For example Lines 188-191, it is not clear what is meant at this point in the text by \"the normalized version\". Lines 306-314 is also a confusing exposition about uncertainty principles, which seems to be tangent to the main discussion (It might be helpful to put this discussion into a remark, or to postpone it to discussion of Section 5). \n\nAnother point that is not made very clear in the exposition is that the additive mechanisms considered in the paper are only those that add i.i.d. noise to the entries of the statistic vector. This rules out correlated noise such as discussed under \"Significance\". \n\nThere are two missing equation numbers on page 8.\n\nThe parentheses in (D1) are unbalanced.\n\nConclusions:\nThe paper builds off of [DRS21] to develop similar CLT results for additive mechanisms in high dimensions. These results are interesting in that they show that as the dimension goes to infinity, adding i.i.d. noise often results in a privacy cost similar to Gaussian noise. A related result shows that the privacy-utility tradeoff is optimized by using Gaussian noise. However, these results are very similar to those of [DRS21] (in fact, if L_infinity sensitivity were used in place of L_2, then the framework would fit within that of [DRS21]). Due to this, the conclusions are not very surprising. \n\nFurthermore, these results are mostly of theoretical interest, and do not result in many practical results. One takeaway is that if i.i.d. noise is to be added, then the Gaussian mechanism is optimal in some sense. However, this is already a commonly used mechanism, so the results do not result in any new DP mechanisms. Furthermore, as the authors mention in Line 92-99, the CLT cannot be used to rigorously quantify the privacy loss when using additive noise (from non-Gaussian distributions). \n\nAnother issue with the paper is the presentation. While the main ideas came across, the paper was difficult to read, with some sections very difficult to parse. The paper would benefit from additional revision. \n\nIn its present form, the paper is marginally below the acceptance threshold (5).\n\n=======\nUpdate: Thanks to the authors for clarifying that the paper allows for correlated noise, and is significantly different from the results of DRS21. I update my score from 5 to 6. I encourage the authors to revise the exposition to improve clarity, if the paper is accepted.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "No issues.", "review_text": "", "extra_scores": {"ethical_concerns": "No issues.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2.5"}, "extra_text": {}}, {"review_id": "wwNEnTPX2J0", "reviewer": "Reviewer_od6Q", "summary": "This paper considers Differential Privacy on multidimensional query responses and in particular considers the hypothesis testing interpretation of Differential Privacy.  The authors rely heavily on results derived in the cited paper DRS21 to derive bounds on highdimensional queries", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The authors place their work in the framework of f-DP and the Gaussian Differential Privacy defintion.  They claim to show that a new interpretation of noise addition and the hypothesis testing approach when the query dimensions are very high.  In particular they show that a large class of noise addition mechanisms fall in the Gaussian mechanism framework when the dimension is large. The novelty here is not clear.  The authors should show why the previous resutls (from DRS21 for example) do not extend to this case, since the framework from DRS21 is quite large.\n\nWhile the result on high dimensions is nice, the paper leaves a gap in practical understanding.  Some experiments that show how the theoretical results manifest would be needed.\n\nThe authors make some comments on similarity to Uncertainty Principles, but this section is unclear - why is this important and what's the significance?  This is a different approach to the privacy-accuracy tradeoff, and how does the interpretation of the Uncertainly Principle help here?\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "jk_RA-5uLd", "reviewer": "Reviewer_S8w3", "summary": "This paper studies the privacy-accuracy trade-off of answering a single n-dimensional query with ell-2 sensitivity 1, under differential privacy. This problem has been studied and the optimal noise distribution the Gaussian, and its upper and lower error bounds match up to constant factors. This paper however studies optimality in the limit n->infty and shows that the Gaussian mechanism is optimal even with respect to constant factors. \n\nA central quantity to the approach and intuition in this work is the ROC function: using a known hypothesis testing view of DP, the ROC function T[M(D),M(D′)] measures the optimal error distinguishing M(D) and M(D’) for two neighboring datasets D, D’ and we say that M is (epsilon, delta)-DP if this function is above a fixed function f_(epsilon, delta) pointwise. Let G be the ROC function of the Gaussian mechanism (omitting privacy parameters).\n\nStarting from the 1-dimensional case, the authors demonstrate that the optimal curve f_(epsilon, delta) and G are far whereas for example the ROC function of the truncated Laplace mechanism is closer to the optimal tradeoff, which they use to stress that the Gaussian mechanism is wasteful in 1-dimension and ask whether this is also the case for n->infty.\n\nThe main contribution of the paper is a central limit type of theorem that demonstrates that this is not the case: for all distributions of noise that satisfy a certain set of conditions, as n->infty, inf_{D,D’} T[M_n(D),M_n(D’)] -> G pointwise. That is, the sequence of mechanisms with the specified noise distributions approach the tradeoff of the Gaussian mechanism. This holds for almost all neighboring pairs of datasets, with the probability of the event that it does not happen going to 0, as n->infty. These conditions are satisfied for example by noise distributions of the form exp(-||x||^a_p) for any ell-p norm and power a. For these and more generally noise distributions of the form exp(-φ) where φ has finite second moments and Fisher information matrix, the authors also prove that the privacy parameter times the ell-2 error of any mechanism is lower bounded by the dimension n, with the inequality being tight when we choose the n-dimensional Gaussian as the noise distribution.", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "*Strengths:*\n- The paper takes a novel creative perspective to the privacy-accuracy trade-off and the study of the optimal noise addition mechanism for high-dimensions. \n- It is hard to tell which parts of the proofs might be useful for future research, but most of the proofs are not trivial and more importantly there are a few ideas and quantities/notions that seem potentially useful (such as the “likelihood projection”).\n\n*Weaknesses:*\n- The results would be described as being of “purely” theoretical nature as they study the asymptotic behavior of the ROC curve of DP mechanisms. It is not straightforward to derive insights as to which noise distributions are constant-sharp optimal for finite -but high- dimensions and we already knew that the Gaussian mechanism is the right choice (up to constants). But the problem itself is important and the paper includes several insights (beyond the main ones described above), so I would not consider this to be an argument for rejection.\n\n\n*Detailed comments:*\n- Although there are explanations in the paper, the regularity conditions are hard to interpret. Are there more examples of phi (leading to known noise distributions that have been used in the literature) that satisfy these conditions?\n- How does this work extend ENU? The latter refers to factorization mechanisms and not more generally noise addition mechanisms but the result is stated as a characterization of the the sample complexity rather than an asymptotic result. It might be beneficial to add more discussion on this in the related work section.\n- I found that the presentation of the main paper was successful in conveying the high level picture and rationale behind the contributions. The proofs however were not as easy to read, as not all proofs and/or lemma statements are close to where they are used. I would suggest adding subsections to group results that are combined in previously stated proofs or use Claims/Propositions within the proofs of Lemmas for results that are needed. The current write-up seems to state both the “small” and the “big” lemmas one after the other.\n-Abstract: perhaps add “for some alpha, p” as one would expect to have seen the variables before the relevant statement\n- line 37: Put it differently -> Put differently\n- line 96: sharp in constant -> sharp with respect to constants (?)\n- line 119: privcacy -> privacy\n- line 146: explain the embarrassing failure of  Gaussian mechanism: perhaps this is a bit excessive…?\n- line 172: N(f(D),…) -> N(f(D’),…)\n- line 188: suggests, the -> suggests that the\n- line 305,318: broken reference\n- line 464: I think the left parenthesis should be before 1+…\n- line 527: I did not understand why we also need the opposite of the bad sets of vectors -Theta_n and -Omega_n in the event E_n.\n- There is a mismatch in almost all the appendix, where references are for section C,D,E but really refer to sections B,C,D, respectively.\n- line 708: I assumed o_P is as defined in the main body but P has a different font in the appendix.\n- line 720: equation should be split\n\n\n==========\n \n\nThanks to the authors for their response and for providing examples. I still support acceptance.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "I think that the potential negative societal impact section is not very informative as is (it actually doesn't include any potential negative societal implications) and might suggest removing it altogether as it does not seem applicable to this work.\n\nLimitations are discusses.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "7"}, "extra_text": {}}, {"review_id": "Tq_n5sZdWfp", "reviewer": "Reviewer_JiKW", "summary": "The paper offers a central limit theory perspective to study two commonly used algorithms in the DP community Gaussian and Laplace for query answering. They consider two scenarios: when the dimension is one (that is there is only one query to answer) and very high dimension (when the answer vector is very hight dimensional). As I understand this, the theory tries to explain the optimality of the Gaussian mechanism in the high dimensional setting even thought it seems to be suboptimal in the one dimensional case in terms of l-2 error. ", "questions": "", "limitations": "", "rating": 7, "confidence": 1, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "\nThe show that a large number of noise addition mechanisms behave like the Gaussian mechanism and they prove that the Gaussian mechanism achieves the optimal sharp-constant private-accuracy trade-off. I find the analysis and the insights in this paper very interesting although it did not understand all the claims. \n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "1"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The authors theoretically analyze optimal privacy-utility tradeoffs when answering an n-dimensional query under differential privacy as n grows large, and provide new evidence pointing to the optimality of the Gaussian mechanism. Four expert reviewers voted accept, with scores 6, 7, 7, 8, and made overall very positive comments about the paper. Two reviewers described raised questions about the relationship between this paper and [DRS21]. The authors clarified that this paper considers correlated noise, while [DRS21] considers only independent noise, which satisfied the concerns of one reviewer, who raised their score. This point is probably worth clarifying in the final revision.
Decision: Accept (Spotlight)