A Central Limit Theorem for Differentially Private Query Answering
Year: 2021

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 [BUV18, SU17]. 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 [DRS21] if the added noise satisfies certain conditions. In particular, densities proportional to e−‖x‖ α p , where ‖x‖p is the standard `p-norm, satisfies the conditions. Taking this perspective, we make use of the Cramer–Rao inequality and show a “uncertainty principle”-style result: the product of privacy parameter and the `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.

text: α p , where ‖x‖p is the standard `p-norm, satisfies the conditions. Taking
this perspective, we make use of the Cramer–Rao inequality and show a “uncertainty principle”-style result: the product of privacy parameter and the `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.

heading: 1 Introduction
text: Introduced in [DMNS06], to date differential privacy (DP) is perhaps the most popular privacy definition. One of the most important applications of differential privacy is to answer numeric queries. Given a function f of interest, which is also termed a query, our goal is to evaluate this (potentially vector-valued) query f on the sensitive data. To preserve privacy, a DP mechanism M working on a dataset D, in its simplest form, is defined as
M(D) = f(D) + tX. (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 X follows the Laplace distribution and the Gaussian distribution, respectively.
∗the Institute for Data, Econometrics, Algorithms, and Learning
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
Aside from privacy considerations, the most important criterion of an algorithm is arguably the estimation accuracy in 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, ∆f = supD,D′ |f(D) − f(D′)| = 1, where the supremum is over all neighboring datasets D and D′. Assuming (ε, 0)-DP for the mechanism M , we are interested in minimizing its `2 loss defined as err(M) := E(M(D)− f(D))2 = E(tX)2 = t2EX2. This question is commonly2 addressed by setting X to a standard Laplace random variable and t = ε−1 [DMNS06]. This gives err(M) = 2ε−2. Moving forward, we relax the privacy constraint from (ε, 0)-DP to (ε, δ)-DP for some small δ. The canonical way, which was born together with the notion of (ε, δ)-DP, is to add Gaussian noise [DKM+06]. A well-known result demonstrates that Gaussian mechanism withX being the standard normal and t = 1ε √ 2 log(1.25δ−1) is (ε, δ)-DP (see, e.g., [DR14]). The `2-loss is err(M) = t2 = 2ε−2 · log(1.25δ−1). A quick comparison between the two errors reveals a surprising message. The latter error 2ε−2 · log(1.25δ−1) is larger than the former 2ε−2. In fact, the extra factor log(1.25δ−1) is already greater than 10 when δ = 10−5. At least on the surface, this observation contradicts the fact that (ε, δ)-DP is a relaxation of (ε, 0)-DP. Put differently, moving from Laplace to Gaussian, both privacy and accuracy get worse. Nevertheless, this contradiction suggests that we need a better alternative to the Gaussian mechanism instead of giving up the notion of (ε, δ)-DP. Indeed, the truncated Laplace mechanism has been proposed as a better alternative to achieve (ε, δ)-DP [GDGK20], which outperforms the Laplace mechanism in terms of estimation accuracy 3.
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 (Q1) in Section 2 from the decision-theoretic perspective of DP [WZ10, KOV17, DRS21]. However, our main focus is (Q2). In addressing this question, we uncover a seemingly surprising phenomenon — it is impossible to utilize the (ε, δ) privacy budget in high-dimensional problems the same way as the truncated Laplace mechanism utilizes it in the one-dimensional problem. More specifically, we show a central limit behavior of the noise-addition 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 µ-GDP if it offers as much privacy as adding N(0, µ−2) noise to a sensitivity-1 query. As in the (ε, δ)-DP case, the smaller µ is, the stronger privacy is offered.
To state our first main contribution, let f be an n-dimensional query and assume that its `2-sensitivity is 1. Consider the noise addition mechanism M(D) = f(D) + tX where X has a log-concave density ∝ e−ϕ(x) on Rn. Let IX := E[∇ϕ(X)∇ϕ(X)T ] be the n × n Fisher information matrix and ‖IX‖2 be its operator norm. Theorem 1.1 (Central Limit Theorem (Informal version of Theorem 3.1)). Under certain conditions on ϕ, for t = µ−1 · √ ‖IX‖2, the corresponding noise addition mechanism M defined in Eq.(1) is asymptotically µ-GDP as the dimension n → ∞ except for an o(1) fraction of directions of f(D)− f(D′). In particular, the norm power functions ϕ(x) = ‖x‖αp (p, α > 1) satisfy these technical conditions. Note that this class already contains correlated noise, so the results in [DRS21] do not apply here. Numerical results in Figure 1 shows that the convergence occurs for a dimension as small as 30.
2If f is integer-valued, then the doubly geometric distribution is a better choice and yields an `2-loss of 1 2 sinh−2 ε 2 < 2ε−2. In the so-called high privacy regime, i.e. ε → 0, the two `2-losses have the same order in the sense that their ratio goes to 1. 3One may blame the sub-optimality of the choice of t, but the problem remains even if the smallest possible t from [BW18] is applied.
We then elaborate on the condition “o(1) fraction of f(D)−f(D′)”. Following the original definition, DP or GDP is a condition that needs to hold for arbitrary neighboring datasets D and D′. This worst case perspective is exactly what prevents us to observe the central limit behavior. For example, consider a certain pair of datasets with f(D) = (0, 0, . . . , 0) and f(D′) = (1, 0, . . . , 0), then privacy is completely determined by the first marginal distribution of X , and the dimension n plays no role here. The “o(1) fraction of f(D)− 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 (ε, δ) 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 characterizes the optimal privacy-accuracy trade-off and justifies the Gaussian mechanism. To see this, recall that the noise addition mechanism defined in Equation (1) is determined by the pair (t,X). Both privacy and accuracy are jointly determined by t and X . Adopting 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 t = µ−1 · √ ‖IX‖2. Using parameters (µ,X), the corresponding mechanism Mµ,X is given by
Mµ,X(D) = f(D) + µ −1 · √ ‖IX‖2 ·X
By Theorem 1.1, it is 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
µ2 · err(Mµ,X) > n. The equality holds if X is n-dimensional standard Gaussian.
Combining Theorems 1.1 and 1.2, among all the noise that satisfies the conditions of Theorem 1.1, Gaussian yields the constant-sharp optimal privacy-accuracy 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 1.1 does not work for every pair of neighboring datasets, so it 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 privacy-accuracy trade-off that is sharp in constant. From a theoretical point of view, the proof of Theorem 1.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.
Related work There is a large body of literature on the characterization of privacy-accuracy tradeoff for query answering mechanisms. For the one-dimensional case, the constant-sharp optimal noise for (ε, 0)-DP was shown to have a piece-wise constant density by [GV16]. This complements our discussion in Figure 2. When the dimension is high, only up-to-constant-factor optimality was known. In particular, [BUV18, SU17] confirm that Gaussian mechanism is minimax rate optimal under (ε, δ)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 up-to-constant-factor minimax optimality in other models, such as the (sparse) linear regression [CWZ21], generalized linear models [CWZ20, SSTT21], Gaussian mixtures [KSSU20, ZZ21] and so on. In our work, we initialize the investigation in the (simpler) mean estimation problem, and leave the constant-sharp optimality in other problems for future work.

heading: 2 GDP and the ROC Functions
text: The decision theoretic interpretation of DP was first proposed in [WZ10] and then extended by [KOV17]. More recently, [DRS21] 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 (Q1).
Suppose each individual’s sensitive information is an element in the abstract set X . A dataset D of k people is then an element in X k. 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:

heading: H0 : output ∼M(D) vs H1 : output ∼M(D′).
text: By the random nature of M , 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 probabilities confusing D and D′, which are commonly known as 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 a vector in Rn. A general decision rule for testing H0 against H1 has the form φ : Rn → {0, 1}. Observing v ∈ Rn, hypothesis Hi is accepted if φ(v) = i, for i ∈ {0, 1}. The false positive rate (type I error) of φ, i.e. mistakenly accepting H1 : v ∼ M(D′) = Q while actually v ∼ M(D) = P , is αφ := Pv∼P (φ(v) = 1) = EP (φ). Similarly, the false negative rate (type II error) of φ is βφ := 1− EQ(φ). Note that both errors are in [0, 1]. Consider the function fP,Q : [0, 1]→ [0, 1] defined as follows:
fP,Q(α) := inf{1− EQ(φ) : φ satisfies EP (φ) 6 α}. (2) That is, fP,Q(α) equals the minimum false negative rate that one can achieve when false negative is at most α. The graph of fP,Q 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 [DRS21] and is denoted by T [P,Q]. We avoid this name because in our paper “trade-off” mainly refers to the privacy-accuracy trade-off, but we will keep their notation.
DP and ROC function Plugging in the privacy context where P = M(D), Q = M(D′), from the discussion above, we see that T [M(D),M(D′)] measures the optimal error distinguishing M(D) and M(D′). Therefore, a lower bound on T [M(D),M(D′)] implies privacy of M . Indeed, [WZ10, KOV17] showed that M is (ε, δ)-DP if and only if T [M(D),M(D′)] > fε,δ pointwise in [0, 1] for any neighboring dataset D,D′. The graph of fε,δ is plotted in the left panel of Figure 2. Compared to a single (ε, δ) bound, the ROC function T [M(D),M(D′)] provides a more refined picture of the privacy of M . In fact, [DRS21] shows that the ROC function is equivalent to an infinite family of (ε, δ) bounds, which is called privacy profile in [BBG20].
Truncated Laplace vs Gaussian through the lense of ROC function Now we use ROC function to answer (Q1) 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 (ε, 0)-DP, it is not hard to determine T [M(D),M(D′)] via Neyman–Pearson lemma and verify that it is indeed lower bounded by fε,0 (see the middle panel of Figure 2). In fact, T [M(D),M(D′)] mostly agrees with fε,0. In other words, the (ε, 0) privacy budget is almost4 fully utilized.
When M is the Gaussian mechanism with (ε, δ)-DP gaurantee, T [M(D),M(D′)] is naturally lower bounded by fε,δ , however, there is a large gap between the two curves (see the right panel of Figure 2). The (ε, δ) privacy budget is poorly utilized by the Gaussian mechanism. This explains why the l2-loss of Gaussian mechanism is not satisfactory.
For noise addition mechanism, if the noise is bounded, say a uniform [−1, 1] distribution, then T [M(D),M(D′)] = f0,δ for some δ ∈ (0, 1). This suggests us to consider bounded noise if we want to add a δ slack in privacy to the Laplace mechanism. The obvious attempt is then to truncate Laplace noise. Indeed, the corresponding ROC function is as close to fε,δ as that of the Laplace mechanism to fε,0 (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 a mechanism.
In hindsight, this achievement for one-dimensional mechanisms is due to the following fact: as we 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 µ > 0, let Gµ := T [N (0, 1),N (µ, 1)] where Φ denotes the cumulative distribution function (CDF) of the standard normal distribution. Consider a query f with sensitivity 1 and let Lap(0, 1) be the standard Laplace noise. Just like ε-DP captures the privacy of the mechanism M(D) = f(D) + ε−1 · Lap(0, 1), the function Gµ captures the privacy of M(D) = f(D) + µ−1 ·N(0, 1). In fact, if f(D′)− f(D) = 1, then M(D) = N(f(D), µ−2) and M(D′) = N(f(D′), µ−2). 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′)] = T [N(f(D), µ−2), N(f(D′), µ−2)] = T [N(0, 1), N(µ, 1)] = Gµ
Therefore, the privacy of a Gaussian mechanism is 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 T [M(D),M(D′)] > Gµ for any pair of neighboring datasets D and D′.
4If the query is integer-valued, then (ε, 0) privacy budget can be saturated by adding doubly geometric noise.
Alternatively, M is µ-GDP if and only if infD,D′ T [M(D),M(D′)] > Gµ where the infimum of 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.
inf D,D′
T [M(D),M(D′)] = Gµ (3)
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.

heading: 3 Central Limit Theorem
text: In the following two sections we turn to addressing (Q2). This section is dedicated to 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.1 mentioned in the introduction.
Consider an n-dimensional query f : X k → Rn. We assume it has `2-sensitivity 1, i.e. supD,D′ ‖f(D)− f(D′)‖2 = 1. Suppose ϕ : Rn → R is convex and e−ϕ is integrable on Rn. The log-concave random vector with density ∝ e−ϕ(x) will be denoted by Xϕ. Define the function class

heading: Fn := {ϕ : Rn → R convex | ϕ(x) = ϕ(−x), e−ϕ ∈ L1(Rn),E‖Xϕ‖22 < +∞,E‖∇ϕ(Xϕ)‖22 < +∞}.
text: The regularity conditions guarantee that Xϕ has finite second moments and Fisher information matrix defined as Iϕ = E[∇ϕ(Xϕ)∇ϕ(Xϕ)T ]. Furthermore, we also have EXϕ = 0 by symmetry and E∇ϕ(Xϕ) = 0 by standard theory of Fisher information (e.g. [VdV00]). We will focus on this class of functions for the rest of paper.
The n-dimensional noise addition mechanism of interest takes the form M(D) = f(D) + tXϕ. The parameter t is only for the convenience of tuning and can be absorbed into ϕ. In fact, tXϕ has log-concave density ∝ e−ϕ(x/t), so it is distributed as Xϕ̃ where ϕ̃(x) = ϕ(x/t). For the normalized CLT, we set t = 1 and assume Iϕ is the n× n identity matrix In×n. Since what we are going to present is an asymptotic result where the dimension n→∞, the above objects necessarily appear with an index n, i.e. we have fn, ϕn, Xϕn and Iϕn . The latter two are often denoted by Xn and In for brevity. With normalization, the n-dimensional mechanism of interest is Mn(D) = fn(D) +Xn. 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 ϕn satisfies conditions (D1) and (D2), then there is a sequence of positive numbers cn with cn → 0 as n→∞ and a subset En ⊆ Sn−1 with Pv∼Sn−1(v ∈ En) > 1− cn such that
‖ inf D,D′ T [Mn(D),Mn(D ′)]−G1‖∞ 6 cn
where the infimum is taken over D,D′ such that fn(D ′)−fn(D)
‖fn(D′)−fn(D)‖2 ∈ En.
Here v ∼ Sn−1 means v comes from a uniform distribution of the unit sphere Sn−1 ⊆ Rn. The conclusion is basically that infD,D′ T [Mn(D),Mn(D′)] → G1, i.e. Mn is asymptotically GDP. Similar to the interpretation of (3), it means the mechanism Mn provides the same amount of privacy as a Gaussian mechanism in the limit of n→∞. However, a fraction of neighboring datasets has to be excluded. More specifically, the limit holds if the direction of the difference fn(D′)− fn(D) falls in En, an “almost sure” event as the dimension n→∞. As we remarked in the introduction, directions in En can exhibit low dimensional behavior and hence must be ruled out for any high-dimensional observation.
For a vector v ∈ Rn and ϕ ∈ Fn, let Pϕv : Rn → R be defined as Pϕv (x) = ϕ(x + v) − ϕ(x) − 1 2v TIϕv. For two random variables X and Y , their Kolmogorov–Smirnov distance KS(X,Y ) is defined as the `∞ distance of their CDFs. A sequence of random variables is denoted by oP (1) if they converge in probability to 0. The technical conditions for the CLT are as follows. Note that each of them are conditions on the function sequence ϕn.
(D1) KS ( Pϕnv (Xn), v T∇ϕn(Xn) ) = o(1) with probability at least 1− o(1) over v ∼ Sn−1 (D2) ‖∇ϕn(Xn)‖2 = √ n · (1 + oP (1))
Remark 1. Dropping the cumbersome subscripts n, (D1) roughly asks that
Pϕv (X) = ϕ(X + v)− ϕ(X)− 12vTIϕv ≈ vT∇ϕ(X) Since Iϕ is the expectation of the Hessian of ϕ, we see that (D1) is basically a regularity condition stating that the Taylor expansion of ϕ holds on average up to the second order. Remark 2. Condition (D2) basically says that ∇ϕ(X) mostly falls on a spherical shell of radius √n (as it should since Iϕ = E[∇ϕ(X)∇ϕ(X)T ] is assumed to be identity). A deeper understanding is provided by an alternative interpretation of condition (D1), using a new notion we propose called “likelihood projection”.
Likelihood Projection. The function Pϕv defined above is called the “likelihood projection” along direction v. It is (up to an additive constant) the log likelihood ratio of Xϕ and its translation Xϕ − v. In fact, Xϕ has density 1Zϕ e −ϕ(x) and Xϕ − v has density 1Zϕ e −ϕ(x+v) where Zϕ is the common normalizing constant. The log likelihood ratio is ϕ(x+v)−ϕ(x). This explains the word “likelihood”. To observe its nature as a “projection”, consider the special case ϕ(x) = 12‖x‖22. Straightforward calculation suggests that Iϕ is identity and Pϕv (x) = vTx. So it is indeed a generalization of the linear projection along direction v.
The alternative interpretation of condition (D1) is that when the dimension is high, the “likelihood projection” Pϕv (X) is roughly a linear projection to the direction v. Condition (D2) is then the “thin-shell” condition proposed in Sudakov’s theorem [Sud78] which we state in the appendix as a necessary tool for the proof of our CLT.
For the general case, consider Mn(D) = fn(D) + tnXϕn where tn = µ −1 · √ ‖In‖2. The factor√
‖In‖2 normalizes the Fisher information to the identity, and the factor µ−1 controls the final privacy level. For this mechanism, we have
Corollary 3.2. If the function sequence ϕ̃n(x) = ϕn(‖In‖− 1 2
2 x) satisfies conditions (D1) and (D2) and that In = ‖In‖2 · (1 + o(1)) · In×n, then there is a sequence of positive numbers cn → 0 and a subset En ⊆ Sn−1 for each n with Pv∼Sn−1(v ∈ En) > 1− cn such that
‖ inf D,D′ T [Mn(D),Mn(D ′)]−Gµ‖∞ 6 cn
where the infimum is taken over D,D′ such that fn(D ′)−fn(D)
‖fn(D′)−fn(D)‖2 ∈ En.
In particular, when p and α belong to [1,+∞), norm powers ‖x‖αp satisfy the above conditions. Lemma 3.3. For p ∈ [1,+∞), α ∈ [1,+∞), let cp,α = α−1 · p−α+ α p · (
Γ(2− 1p ) Γ( 1p )
)−α2 , the sequence
of functions ϕn(x) = n1− α p · cp,α‖x‖αp satisfies conditions (D1) and (D2) and that In = ‖In‖2 · (1 + o(1)) · In×n.
The parameter cp,α and the power of n 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 Fn satisfy (D1) and (D2).
Recall that ϕ ∈ Fn 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 M t(D) = f(D) + tX , with the emphasis on the scaling parameter t. As t increases, M t obviously loses accuracy regardless of log-concavity of X . On the other hand, when it comes to privacy, we have Lemma 3.5. WhenX has log-concave distribution and t > 0, the ROC function T [M t(D),M t(D′)] is (pointwise) monotone increasing in t for any D,D′.
Since larger ROC function means more privacy, this lemma confirms that M t gains privacy as t increases. In other words, it confirms the existence of “privacy-accuracy trade-off” given the logconcavity of X . Note that without log-concavity, monotonicity in the lemma need not hold. For a
one-dimensional example, consider an X that supports on even numbers and f(D) = 0, f(D′) = 2. When t = 2, T [M t(D),M t(D′)] = T [2X, 2X + 2] = T [X,X + 1]. There is no privacy in this case as X and X + 1 has completely disjoint support. On the other hand, when t = 1, T [M t(D),M t(D′)] = T [X,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 (D1) and (D2) (e.g. densities ∝ e−‖x‖αp ) 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 (ε, δ) 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-sharp lower bound — the Cramer–Rao inequality. This will be the content of the next section.

heading: 4 Privacy-Accuracy Trade-off via Cramer–Rao Inequality
text: The central limit theorem in the previous section suggests that we use GDP parameter µ to measure privacy. Adopting this, we will show that the privacy-accuracy trade-off is naturally characterized by the Cramer–Rao lower bound. The conclusion has a similar flavor to the uncertainty principles.
Recall that the mechanism M(D) = f(D) + tXϕ is determined by two “parameters”: the shape parameter ϕ ∈ Fn which determines the distribution of Xϕ, and the scale parameter t. If ϕ also satisfies the conditions of Theorem 3.1, then we can use the desired (asymptotic) GDP parameter µ to determine the scale parameter, i.e. t = µ−1 · √ ‖Iϕ‖2. Using the equivalent parametrization (µ, ϕ), the corresponding mechanism Mµ,ϕ is given by
Mµ,ϕ(D) = f(D) + µ −1 · √ ‖Iϕ‖2 ·Xϕ. (4)
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ϕ‖22 = µ−2 · ‖Iϕ‖2 · E‖Xϕ‖22. (5) The following theorem characterizes the privacy-accuracy trade-off as the product of the mean squared error err(Mµ,ϕ) and privacy parameter µ2.
Theorem 4.1 (Restating Theorem 1.2). For any ϕ ∈ Fn and Mµ,ϕ defined as in (4), we have
µ2 · err(Mµ,ϕ) > n. In addition, the equality holds if the added noise X is n-dimensional standard Gaussian.
Proof of Theorem 4.1. To simplify notations we will drop the subscript ϕ in X . We first claim that it suffices to show the following uncertainty-principle-like result
Var[X] ·Var[∇ϕ(X)] > n2. (6) where the notation Var[·] is slightly abused to denote the mean squared distance of a random vector from its expectation, i.e. Var[X] = E[‖X − EX‖22]. To see why (6) suffices, notice that by (5), the interested quantity can be simplified as
µ2 · err(Mµ,ϕ) = E‖X‖22 · ‖Iϕ‖2. (7) Recall that we have EX = 0 by symmetry of ϕ and E∇ϕ(X) = 0 by basic Fisher information theory. So Var[∇ϕ(X)] = E‖∇ϕ(X)‖22 = TrE∇ϕ(X)∇ϕ(X)T = Tr Iϕ. That is, eq. (6) implies
E‖X‖22 · Tr Iϕ > n2. (8) Since Iϕ is positive semi-definite, by (7) and (8) we have
µ2 · err(Mµ,ϕ) = E‖X‖22 · ‖Iϕ‖2 > E‖X‖22 · 1nTr Iϕ > n.
Next we focus on the proof of (6). Consider the location family {X + θ : θ ∈ Rn}. The Fisher information of this family is Iϕ at all θ. The random vector itself is an unbiased estimator of the location. Therefore, by the Cramer–Rao inequality (c.f. [VdV00]), we have that Cov(X)− I−1ϕ is positive semi-definite. As a consequence,
Var[X] = Tr Cov(X) > Tr I−1ϕ = λ−11 + · · ·+ λ−1n .
where λ1 > · · · > λn > 0 are the eigenvalues of Iϕ. We already see that Var[∇ϕ(X)] = Tr Iϕ, so by Cauchy–Schwarz inequality,
Var[X] ·Var[∇ϕ(X)] > (λ−11 + · · ·+ λ−1n )(λ1 + · · ·+ λn) > n2
The proof of the inequality is complete. For standard Gaussian, we have Cov(X) = Iϕ = In×n, and we have µ2 · err(Mµ,ϕ) = E‖X‖22 · ‖Iϕ‖2 = Tr In×n · 1 = n.
Note that although Theorem 4.1 holds true for very general ϕ (only integrability conditions are imposed in Fn), 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 ϕ(x) = ‖x‖αp . The corresponding Xϕ will be denoted by Xp,α and Iϕ by Ip,α. In this special case, we can compute the quantities in (8) exactly. In the following lemma, we write an ∼ bn for the two sequences an and bn if anbn → 1 as n→∞. Lemma 4.2. For 1 6 p <∞ and 1 6 α <∞, as n→∞, we have
E‖Xp,α‖22 ∼ n 2 α− 2 p+1 · α− 2α · p 2p · Γ( 3p ) / Γ( 1p );
Ip,α ∼ n 2 p− 2 α · α 2α · p2− 2p · Γ(2− 1p ) / Γ( 1p ) · In×n.
This result put Theorem 4.1 into a more concrete context. Some important cases with specific values of p and α are worked out in Table 1. Remarkably, in the last row, the products that characerize privacy-accuracy trade-off are asymptotically independent of α. As a by-product of this calculation, we also derive the expression for the isotropic constant of the n-dimensional `p ball, which is an important concept in convex geometry (c.f. [BGVV14]). See the appendix for more results and discussion.
Alternatively, we may want to measure the accuracy by the expected squared `∞-norm of the noise. A similar argument suggests to consider the following quantity E‖Xϕ‖2∞ · ‖Iϕ‖2. By Theorem 4.1 and the fact that ‖x‖∞ > 1√n‖x‖2, we have
E‖Xϕ‖2∞ · ‖Iϕ‖2 > 1nE‖Xϕ‖22 · ‖Iϕ‖2 > 1. (9) We would like to point out a connection to a recently resolved open problem proposed in [SU17], asking if there is a DP algorithm that answers a high-dimensional query with `2-sensitivity 1 with O(1) error in `∞ norm. In particular, the recent solution [DK20, GKM20] provides strong evidence that the lower bound in (9) 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 a function and its Fourier transform cannot both be localized simultaneously. Specifically, for a function f ∈ L2(Rn), its Fourier transform is defined as f̂(ξ) = ∫ e−2πi〈ξ,x〉f(x) dx. Fourier transform is unitary, i.e.
‖f‖L2 = ‖f̂‖L2 . In particular, if |f |2 is a probability density, then so is |f̂ |2. Our previous
abuse of notation also applies here, for example, Var[|f |2] = ∫
(x − a)T (x − a)|f(x)|2 dx where a = ∫ x|f(x)|2 dx. For ‖f‖L2 = 1, we have the following result5 (c.f. Corollary 2.8 of [FS97])
Var[|f |2] ·Var[|f̂ |2] > n216π2 . (10) The similarity between (6) and (10) suggests that Theorem 4.1 can be considered as yet another manifestation of the uncertainty principle.

heading: 5 Conclusions and Future Works
text: 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, a CLT shows that (ε, δ) privacy budget cannot be fully spent for a large class of noise addition mechanisms as they all behave like a Gaussian mechanism. On the other hand, Fisher information naturally arises in these high-dimensional mechanisms, and the simple and fundamental quantity “privacy parameter × error” automatically manifests itself as the quantity “information × error” in the Cramer–Rao lower bound. Using this, we are able to show an elegant characterization of the precise privacy-accuracy 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 are possible. An immediate one is to extend the CLT to a broader class of noise distributions, such as log-concave distributions as specified in Conjecture 3.4. Another condition imposed by Fn (implicitly) is that the noise must be 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. In 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-concave noise, Lemma 3.5 suggests us to 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. As a circumstantial evidence, [BDKT12] shows that generic algorithms for query answering can be reduced to a noise addition one with better accuracy and slightly worse privacy.

heading: Acknowledgements
text: 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-1763314 and CAREER DMS-1847415, an Alfred Sloan Research Fellowship, and a Facebook Faculty Research Award. L. Z. was supported in part by NSF through DMS-2015378.
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 our theoretical understanding of such trade-off between privacy and utility.

Review summaries:
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.   A 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).  Starting 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.  The 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.

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.  

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.