New Lower Bounds for Private Estimation and a Generalized Fingerprinting Lemma
Authors: Gautam Kamath
Argyris Mouzakis
Vikrant Singhal
Venue: NeurIPS 2022 Accept (2022)
Keywords: Differential Privacy
Learning
Machine Learning
Data Privacy
Statistics
Gaussians
Covariance Estimation
Lower Bounds
Mean Estimation

Abstract: We prove new lower bounds for statistical estimation tasks under the constraint of $(\varepsilon,\delta)$-differential privacy. First, we provide tight lower bounds for private covariance estimation of Gaussian distributions. We show that estimating the covariance matrix in Frobenius norm requires $\Omega(d^2)$ samples, and in spectral norm requires $\Omega(d^{3/2})$ samples, both matching upper bounds up to logarithmic factors. We prove these bounds via our main technical contribution, a broad generalization of the fingerprinting method to exponential families. Additionally, using the private Assouad method of Acharya, Sun, and Zhang, we show a tight $\Omega(d/(\alpha^2 \varepsilon))$ lower bound for estimating the mean of a distribution with bounded covariance to $\alpha$-error in $\ell_2$-distance. Prior known lower bounds for all these problems were either polynomially weaker or held under the stricter condition of $(\varepsilon,0)$-differential privacy.

New Lower Bounds for Private Estimation and a Generalized Fingerprinting Lemma*
Gautam Kamath
Argyris Mouzakis
Cheriton School of Computer Science
Cheriton School of Computer Science University Waterloo Waterloo, ON N2L 3G1, Canada amouzaki @uwaterloo. ca
University of Waterloo
Waterloo, ON N2L 3G1, Canada gocsail weieaall..i..m mmm.medee
Vikrant Singhal
Cheriton School of Computer Science
University of Waterloo Waterloo, ON N2L 3G1, Canada vikrant, wwwhnngha@wwaatrrreeoo ca
Abstract
We prove new lower bounds for statistical estimation tasks under the constraint of (c, -differrrntia privacy. First, we provide tight lower bounds for private covariance estimation of Gaussian distributions. We show that estimating the covariance matrix Frobenius norm requires (dd²) samples, and spectral norm requires (dd3/2 samples, both matching upper bounds up to logarithmic factors. We prove these bounds via our main technical contribution, a broad generalization of the fingerprinting method [BV114 to exponential families. Additionally, using the private Assouad method of Acharya, Sun, and Zhang [ASZ21], we show tight (dd((a²)) lower bound for estimating the mean of distribution with bounded covariance to a-error in f--distance. Prior known lower bounds for all these problems were either polynomially weaker or held under stricter condition (e, diffifferlttial privacy.
Introduction
The last several years have seen a surge of interest in algorithms for statistical estimation under the constraint of Differential Privacy (DP) [DMNS06]. We now have rich algorithmic toolbox for private estimation of mean, covariance, and entire distributions, in a variety of settings.
While the community has enjoyed much success designing algorithms for estimation tasks, lower bounds have been much harder to come by, and consequently, the existing literature lacks a rigorous understanding of some core problems. Lower bounds against the strong privacy constraint of pure DP (i.e.. (e, 0)-DP) are generally not too challenging to prove, most often relying upon the well-known packing technique [HTTO]. Such packing lower bounds are optimal broad range of settings (see, e.g., [BKSWI9)), and thus are frequently effective at providing tight minimax sample complexity lower bounds.
However, pure DP is a very strong privacy constraint: in most practical circumstances, suffices to only require the weaker privacy notion of approximate DP (i.e., (c, ()D)) [DKM+06] in which case packing lower bounds are no longer applicable. Proving lower bounds under approximate DP
Authors are listed in alphabetical order.
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

is much more challenging, and accordingly, the state of affairs is less satisfying. There exist only couple of techniques which apply in this setting, including the fingerprinting method [BVV14 and differentially private analogues of Le Cam's 8 method and Assouad's s lemma [ASZI8] AS721] These techniques can be quite brittle and thus unable to prove lower bounds for some fairly basic settings. For example, both techniques generally require that the underlying distribution has independent marginals and are thus ineffective at proving tight lower bounds for problems involving correlations such as private covariance estimation. Furthermore, the fingerprinting method often needs the distribution's 's marginals to have a precise functional form, such as Gaussian or Bernoulli. These restrictions make the approaches somewhat brittle for proving lower bounds which differ too much from existing results. Consequently, we lack approximate DP lower bounds for some fundamental settings which seem to qualitatively differ, including Gaussian covariance estimation and mean estimation of heavy-tailed distributions.
1.1
Our Results
We circumvent these barriers and fill number of gaps in the literature by providing tight lower bounds for several estimation tasks under the constraint of approximate differential privacy. Specifically, we address problems including covariance estimation for Gaussians and mean estimation with heavy-tailed data. Our main technical tool for covariance estimation is novel generalization of the fingerprinting method to exponential families, while we prove our mean estimation lower bound via DP Assouad's 's lemma.
Our first result is a lower bound for covariance estimation in Frobenius norm
Theorem 1.1 (Informal). For any a = O (1), any (E, 6DD mechanism with e, ô E [0, and 8 < Omin (1/n, d' / log(n/d²)))) that takes n samples from an arbitrary d-dimensional Gaussian N (0, Σ) and outputs M (X) satisfying
I X.M
[IIM (X) - >1/]] - S a² requires n 2
d
We point out that the above lower bound also implies a lower bound for density estimation of Gaussians with known mean and unknown covariance (see Theorem 1.1 of (DMR18). This nearly matches the O (d²) upper bound of [KLSU19] up to polylogarithmic factors Previously, Ω (df) lower bounds for Gaussian covariance estimation were only known under the more restrictive constraint of pure differential privacy [KLSU19 BKSW19).
Our result for Gaussian covariance estimation in Frobenius norm implies the following result for spectral estimation.
Theorem 1.2 (Informal), For any = O11/V(1))))) any (c, 6)-D mechanism with E, E [o, 1], and 8 < Omin { (1/n, d / log(n//(1)) that takes n samples from an arbitrary d-dimensional Gaus- sian N (0, Σ) and outputs M (X) satisfying E X,M [[IM (XI (X) - [||] < a² requires n. 2 Ω d
In Theorem 3.8 of [KLSU19, the authors give guarantees for an individual iteration of a private recursive preconditioner. In each iteration, the data is rescaled, resulting in constant-factor progress in privately reducing the condition number of the underlying covariance matrix to a constant. Identifying the preconditioning matrix necessitates performing spectral estimation of the underlying covariance matrix. Thus, the sample complexity upper bound of (d3/2) which comes up in the guarantees of the preconditioning steps also an upper bound for spectral estimation for a = O (1). This implies that our lower bound is tight up to polylogarithmic factors in the regime = (1/vVd).
Recall that the Mahalanobis norm of M with respect to Σ || - 1/3 For the lower
bound constructions consider, 52 [ < < O (1)I. In this regime, the Mahalanobis and Frobenius distances are equivalent up to a constant factor. Thus, we will often use them interchangeably and our lower bound for Frobenius estimation also implies a lower bound for Mahalanobis estimation.
"We note that all our lower bounds in this work stated in terms of mean squared error, while most of the In many natural cases (such
upper bounds guarantee error at most a with probability 1 for some as when the estimator's 's range is naturally bounded), lower bounds against MSE can be converted to constant probability statements via a boosting argument (outlined, e.g., in the proof of Theorem 6.1 of [LSUU9)). The details of such conversion generally standard when applicable and do not discuss it further here.

---

Note that the sample complexity of the same problem sans privacy constraints is O (d), and thus the cost of privacy is polynomial in the dimension This is in contrast to Gaussian mean estimation in f2-norm and covariance estimation in Frohenius norm, which maintain their non- non-private sample complexities of (d) and (dd)), respectively.
(sdPp)) lower bounds for approximate DP covariance estimation in spectral norm were previ- ously known for worst-case distributions [DTZZ14). Our work relaxes this assumption significantly to the Gaussian case while maintaining the same lower bound. A priori, it was not clear that such result was even true, as there are frequently gaps between the sample complexity of private estimation for worst-case versus well-behaved distributions for even basic settings, including distributions over the hypercube (see, c.g., Remark 6.4 of (BKSWI9).
This lower bound has implications for estimation tasks with scale-dependent error. For example, consider Gaussian mean estimation in Mahalanobis distance. A natural way to approach this problem is to first estimate the covariance matrix spectrally, and then estimate the mean after an appropriate rescaling (see, e.g., (KLSU19). ). Our lower bound shows that any such approach must incur the ((d32) cost of spectral estimation, which is greater than the O (d) minimax sample complexity of the problem. Indeed, some recent works [BGS 21 [KO2[] manage to circumvent this roadblock by adopting more direct (but computationally inefficient) methods.
Finally, we prove new lower bounds for mean estimation of distributions with bounded second moments (the definition is in Appendix A).
Theorem 1.3 (Informal). For any S 1, any (E.D) mechanism with 8 S that takes n samples from an arbitrary distribution over Rdd with second moments bounded by and outputs M (X) satisfying
[IM (X) - =16] S a² requires n 2 Ω 4
X,M
Similar (dd((a))) upper and lower bounds were previously known for distributions with bounded second moments under the stricter constraint of pure differential privacy [BD14KSU22 HKM21 Also, similar bound is shown in [KLZ2I] for concentrated DP, but under a weaker moment assumption which involves only coordinate-ve holds under the weaker constraint of approximate DP for distributions satisfying the stronger moment assumption, and thus no savings can be obtained by relaxing the privacy notion. In contrast to our other results, show this lower bound via the DP Assouad method of [ASZ2I], thus demonstrating the promise of different approaches for proving lower bounds for differentially private estimation.
projections. Our result shows that the same bound
1.2 Related Work
The fingerprinting technique for proving lower bounds was introduced by Bun, Ullman, and Vad- han [BVV14. which relied on the existence of fingerprinting codes [BS98] Tar08). Since then, the technique has been significantly simplified and refined in a number of ways [SU17a DSS 15 SUI7b KLSU19 CWZ19), including the removal of fingerprinting codes and distilling the main technical component into the fingerprinting lemma. Beyond the aforementioned settings of mean estimation of Gaussians and distributions over the hypercube [BUV14 S015 DSS 15 KLSU19) fingerprinting lower bounds have also been applied in settings including private empirical risk min- imization [BST14 and private spectral estimation (DTTZ14.. Differentially private analogues of Fano, Le Cam, and Assouad were first considered in the local DP setting [DJW 13) and more recently under the constraint of central DP ASZI8 ASZ21
On the upper bounds side, the most relevant body of work is that which focuses on mean and co- variance estimation for distributions satisfying a moment bound, see, e.g., [BD14 KVI8 BKSW19
BS19 KLSU19|
CWZ19
KSU20 WXDX20] DFM 20 BDKU20 AAK2I BGS+21 KLZ21
HLY21
KMS+
AL2I. Our lower bounds nearly match these upper bounds for Gaussian co-
variance estimation KLSU19 and heavy-tailed mean estimation [KS220 HKM21J Previously, these bounds were conjectured to be optimal, albeit on somewhat shaky grounds including evidence from lower bounds proven under pure DP or non-rigorous connections with lower bounds in re- lated settings. Our results rigorously prove optimality and confirm these conjectures. Other works study private statistical estimation in different and more general settings, including mixtures of Gaussians [KSSU19 AAL2T], graphical models [2 discrete distributions [DHS15) and
median estimation [AMB 19 TVGZ20). Some recent directions involve guaranteeing user-level
3

---

privacy LSY 20
211, or a combination of local and central DP for different users [ADK]] 19.
See KU20 for further coverage of DP statistical estimation.
1.3 Organization
We start by providing our generalized fingerprinting technique in Section 2 Then we show its novel application for proving the lower bound for covariance estimation of Gaussians in Mahalanobis norm, followed by the lower bound for spectral norm estimation in Section [ Finally, we sketch the proof
of the lower bound for mean-estimation of heavy-tailed distributions Section [4] We describe the notations and preliminaries for privacy and exponential families in Appendix A. After that, we detail the missing proofs from Sections]] 2 3 and in Appendices B. C, and D, respectively. Furthermore. we state facts from linear algebra and geometry in Appendix E, and facts from probability and
statistics in Appendix F. Finally, in Appendix G, we include the proofs of older results obtained in [KLSU19] but using our generalized results in the language of exponential families 4
2 Fingerprinting Proofs for Exponential Families
This section is split into three parts. Section 2.1 provides an overview of existing fingerprinting proof's and motivation for our result, and introduces all the necessary notation. Then, in Section [.2 our new fingerprinting lemma stated. Finally, in Section 2.3 we give a general recipe for applying
2.1 Overview of Fingerprinting Proofs and Intuition for Our Result
At the heart of fingerprinting proof's lies the trade-off between accuracy and privacy. For simplicity, assume have univariate data- generating distribution and coming from a family parameterized by its mean fe, which we want to estimate. In contrast to minimax lower bounds in classical statistics (which are commonly obtained by constructing hard testing instances), fingerprinting proofs assume the existence of a subset of the domain of lu (commonly an interval [ Rl) and that a value is drawn μ 2/
Xi:..., ...... Xx, are drawn from Dy-- Now, given an estimator f _2" + [+ Rt for μ. we consider the quantity Z; == c(Ri p)) (f (X) (1) (X; 11), Vi E [n]. which measures the correlation between the output of ʃ and the i-th sample (c(R. > is scaling factor that exists for purely technical reasons). Defining Z == Exem Z, all proofs first show
([= Rl). Then, n. independent samples X₁
a lower bound L on 2[Z + (X)- )) implying that our estimator cannot at the same time be accurate (with respect to the Sraan-Squared-Emee (MSB) and exhibit low correlation with individual samples. This component of the proof is traditionally called the fingerprinting lemma.
Privacy comes up in the second step of the proof, where we upper-bound the correlation terms E [Z.].
We assume that f is private mechanism with MSE at most L/2. Due privacy, all correlation terms 2i should be poper-bounded by the same U = U (c, 8). Applying this for each sample leads to an inequality of the form nl > L/2 + n L/(2U) so the only thing that remains is to identify the appropriate parameter range for 8 to prove the desired bound.
Our work is motivated by fundamental weakness of existing fingerprinting proofs. To prove lower distributions via fingerprinting. past works have assumed that the
bounds for high-dimension underlying distribution is product distribution. This made it possible to work component wise using techniques for single-dimensional distributions. This assumption somewhat restrictive and makes it difficult to generalize the approach to settings with a richer correlation structure.
Our main technical contribution is providing broad generalization of the celebrated fingerprinting method to exponential families (the definition is in Appendix A). Distributions belonging in the same exponential family are parameterized by their natural parameter vector n), instead of their mean μ., for which it is uncommon to have a general closed-form expression. Given samples XI...., Xx, from p,, it suffices to know the values of the sufficient statisties T (X1) ..... T (X,,, instead of the samples ves in order to estimate 17 (see, e.g., [o). We denote the mean and covariance of T by μT and Σr, respectively.
*The bounds we recover in Appendix G are all from KLSU19 These include one lower bound for mean estimation of binary product distributions, and one for Gaussian mean estimation. In the process of proving the latter, we identified a bug in the original proof from [KLSU19, which we correct in this manuscript. This resulted in a slightly different range for ó than the one given in the original theorem and proof.

---

Based on the above remarks, our fingerprinting lemma provides lower bounds for estimating instead of μ. We assume the existence of vectors n7 ,n(()) with my S n Vj [k], and define the intervals 1 = 72 :nj ((22) for each coordinate j E [k]] Assuming that the hyperrectangle j 1 subset of H. we draw natural parameter vector 1) uniformly at random from Observe that I may not be centered around the origin, which poses a minor technical difficulty. To deal with this, assume that from the midpoint m = (1)1) ) + +7( 2)2))) The two problems are equivalent because any estimator
estimator does not estimate itself, but rather the deviation of
(2) "i )/2 for the latter problem can be transformed to estimator for the former, simply by adding to it (and vice-versa). Defining R to be the width vector (2 1)(2), the correlation between the estimate for fij and the sample X; becomes 7 [R] (11 m (x) (n) mT)](T) (X,) (TJ)), Vi [m],] E [A]]
f 5 + 25 JEjnN] (1,) - 1/j (/ (1)
Observe that now, Z measures the correlation between f and the sufficient statistics of the samples. This is in contrast to older fingerprinting proofs, in which the z measure correlation between f and the samples themselves. We consider this to be natural in the context of exponential families. Indeed, we know that, if we want to estimate the natural parameter vector of distribution that belongs to an exponential family given dataset = (X1,..., X,), suffices to know the values T (X1).... ..... T (X,,) instead of the samples themselves (see [0)) Thus, despite receiving X, correlation ends up being measured with respect to T (X,) i E [n]]
In addition to the above, we introduce three more correlation terms:
2,
Σ
Z
Σ
R2/44 (1) mf (X) (ny mm)] (T, (X;) (T.)),
JE[K]
jE[K]
7
Σ
7
RR] / (nj 11f (X) - (n3 - -m;)] Σ (T, (X,) - 1T5),
kE|n]
iE|m]
7
Σ 74 = Σ お!.
iE|m]
jE(A:
We motivate each of the above. Z; describes the correlation between X; and our estimates for rj. Moreover, Z describes the correlation between our estimate for n₁ and X. Finally, Z describes the total correlation between the output of f and X. Our fingerprinting lemma for exponential families
will involve upper and lower-bounding the quantity
Z + I (X) (n m)
n.X
2.2
The Main Lemma and Our Approach to Lower Bounds
We prove our new fingerprinting lemma in two parts. First, we assume we have distribution pv, that belongs to an exponential family and we want to estimate n); whereas 7/j fixed (Lemma 2.1). This setting is similar to the ones considered in [BS117 KLSU19, which feature similar lemmas. We then leverage I Lemma to to get a result when the goal is to estimate all of n (Lemma 2.2).
Let be a distribution over S C TR. belonging to an exponential family & (T, with natural parameter vector E 7 C IR* We assume that 1; is non-degenerate and that nī is randomly generated by drawing yj ~ U (I₃), whereas 11 is fixed. Then, for any function fz: S - [22
Lemma 2.1.
that takes as input dataset X = "K,...,,,,] P.
2 we have:
E X
Z + +ff - (ng mm)) 2 R2/110 12.
Proof. gjt X jEEM Ij - [2 with Øj (1)) B8 UGs (X)). 9o can equivalently be written as:
9 (7) =
II
Py (2:)) fo (I) dxy .... dæy,
Rd Rd
(iE(m)
5

---

Observe that:
exp (
II EE
Py (1+)
II h (at)
< T(x))
- nz (n)
=
kE(n)
(E(M]
0 Tm
II Pr (a;) (E(n))
II VE(m]
Pn (24)
Σ
Tj (xx)
(Z (n))
mmg
iE(m]
II VE(m)
Pn
(2r)
Σ
(T) (x:)) pPTs)
kE(M]
Calculating the partial derivative 9, with respect to my and changing the order of differentiation and integration, we get:
0 any
(g) (n))
II iE mg]
Py (Ix) f3 (A1....,, Fnn)
Σ
(T, (x:) pT dx1 dr
Bd
Rd
kE[m]
13
fj (X)
(Tj (Xi) MTU)
1E/n]
(
fg (X) Σ (Xi) - -TT,s)
E
(11 - -my)
Σ
(T, (X,) pTJ)
x
kE(x)
sE(m]
- -
Σ iE|n]
(T, (X:) - ((x)))17T))) mTTs))
where (a) relies the observation that, conditioned on ÿy. nj m, and Σie(n] (T, (X,) PT.))
are independent and
E x
Eie(m) (T, (X:) (X.))) = O.
We proceed to define the function Gy: x jE(K] Ij + R as:
G2 (n) = E [2'] = R23/4 (ng (ny) E
Iff (X) (ng -my)] Σ sE|n]
(Tg (X,) - wTS))
x
x
Ogi (1))
[n2/4 (m - -m,)²² m
=
Ori
Calculating the expectation of G, with respect to ny yields:
Ogi ani
E EGG, (n)) = E
R2/44 - (n - m3)²
(n)
f
1
Ogs (m
R2/4 (ng mm,)²)
Mj.... ..)) dnp
[1,1
Oms
(0)
R2/ /4 (n3 -m,) m 29 13((1 tm ................................ ... nk)
[1,1
my=ug"" (1)
(3
+2 2 [4, m
(ng m,) 95 ( ......,. nk) dt
2E
(1n my) gj (n))
n;

---

where (a) uses integration by parts that that my has been defined to be equal to (1²5) + +1/ (2) //2
)/2
Based on this, we remark that the inequality we wish prove can be written in the form:
2 my) (X) + (X) - (n, - m,)1 2 R
(I)
0/ x
Appealing to linearity of expectation, we focus on the second term and get:
E
[ - (ng m3)]²
E n2.
ff (X) 2 (11 m2) f3 (X) + (nz [0mm-,)² m2)²
n/
2 E (nn my) f (X)] + E Aia
(13 m₂)²
Tij
2 I Un m2) ʃ3 (X)] + Var (1;)
2 E ((n my) f (X)] + R2 12/
Substituting this ① yields the desired result.
We now generalize the previous lemma in the setting where all the components of y are drawn independently and uniformly at random from intervals.
Lemma 2.2. Let Pn be a distribution over S IR belonging to an exponential family E (T, with natural parameter vector rj E H C IR. We assume that 1) is randomly generated by drawing independently na ~ U (1z), Vj [k]. Then, for any function f: S + 2 JE(K] [ /2] that takes
as input dataset X (XI,.... Xn.)
Pij
8 we have:
E n
+ (x) (1) - m)]l (
2 2|
The proof is merely component-wise application of Lemma 2.1 and deferred to Appendix B.
2.3 From the Lemma to Lower Bounds
We leverage Lemma 2.2 to give general recipe for proving lower bounds for private estimation. The overall structure of our argument is similar to that of past fingerprinting proofs but, along the way, uses specific properties of exponential families to deal with the fact that we do not have a product distribution.
We assume the existence of ODP mechanism M: Sth
jEE(H) [2 with e [0, 1] and z 0 such that, for any distribution Pa with r) X jE(M] L5. we have for ~ pt
X "
M (X) (1 m)ll s a² < | /44
(2)
X.M
For the above, Lemma 2.2
with f = M yields:
7
E M
E
7
|||
12
[IM - (n - [0-m)]1 > || /24 M.X.M
E
(3)
M.
Thus, intent is upper-bound the LHS by function of using the definition of privacy, which will allow us to identify a lower bound to get the desired accuracy. To do so, we first need to upper-bound E [Z.].
M.X.M
Lemma 2.3. Conditioning on 1), for any e E [0,1],8 2 0, and T it holds that:
E. [Z] < 28T + 25 X.M
[s T s) +
P X,
[[T - prll2 > (4 VE) dt,
V X...M
where
R with 82 = [R/ 4- (17 m2 (Xwi) - (17) mm))),, [k].
7

---

The proof involves splitting Z, in its positive and negative components and applying the definition of DP each of them. The argument standard and has appeared in previous works (e.g., see [SU17b]. but we need to apply specific properties of exponential families to deal with the fact that we don't have a product distribution. The proof lengthy so we omit and is deferred to Appendix B.2.
Combining Lemma 2.3 with 3 yields the main result of this section (see Appendix B for the full proof):
Theorem 2.4. Let Py be a distribution over S C TR belonging to an exponential family & (T, h)) with (2) natural parameter vector rj E H. _ R Also, let (1 s7(2) E H. and let 15 = [] , n Vj E [R]
be collection of intervals and R == r/2) n10) == (n + 1222) be the corresponding
width and midpoint vectors, respectively. Assume that 8 JE(K 1 C H and that yj is drawn from
the distribution U(O SE[k] I5)- Moreover, assume that we have a dataset X ~ Pu
" and an inde-
pendently drawn point X ~ Py and X denotes the dataset where X, has been replaced with
X!. Finally, let M: 5 - 8 jE(R] [ R2/2]
2] be an (e, DDP mechanism with E [0, 1,,1 2 0 with
E X.M
(X) - (n- ml
I a² I
|R] /4.. Then, for any T > O, it holds that:
+ f- P J x.
4t
| 24
25T + 2cE
E V X
T Erss
(T())) - HTll2
dt
2
||
3
In order to apply the above theorem, the main idea is to identify values for T and such that 8T 2 P. (X.) pril2 > (41)/(I vk) dt, and 35Tn
|| 48
The reasoning behind this is that the first and third terms of (.4) both depend on T, with the latter term becoming smaller as ''' increases. Thus, balancing these two terms involves identifying a value for I' that is as small as possible and results in 8T' dominating the other term, At the same time, we want the sum of those two terms to be smaller than the half of the RHS, so that we get a lower bound that is as tight as possible, leading to the constraint on 5.
The above result in the inequality nE [V
E
[s
Ers]
> || (96E).
X.r,M
Consequently, obtaining the desired sample complexity lower bounds boils down to upper-bounding the term Xw sy In the applications we will see, the upper bounds will be worst-case in
terms of 17, the outer expectation E [-] will be largely ignored.
?)
We point the reader to the end of Appendix B for three remarks. The first notes the rotationally invariant nature of Theorem 2.4 with respect to the parameter space H (Remark B.2), the second details how to upper-bound the last term of (2.4) when ō is (Remark B.3), and the third Theorem 2.4 for 8 = 0 (Remark B.4).
3 Lower Bounds for Private Gaussian Covariance Estimation
Here, we provide lower bounds for covariance estimation of high figh-dimensional Gaussians with respect to the Mahalanobis and spectral norms under the constraint of (s, 6DDP.
3.1 Estimation with Respect to the Mahalanobis Norm
In this section, we characterize the sample complexity of private Gaussian covariance estimation with respect to the Mahalanobis norm under (c, 8D-D. Previous lower bounds either assumed stricter notion of privacy (e.g., eDDP see [KLSU19) or exhibited significant gaps with known upper bounds (see Section 1.1.1 of [AAKI]] for further discussion). We start by stating our main result.
I Σ 21 such that, given Σ ~ 'D and X ~ N (0, x) @ r) for any a (1) and any (c, 6)DD mechanism M: Baxd + Rdxd with E, E [), and 5 < O Omin { (1/n, d log(n/d?)) that satisfies
Theorem 3.1. There exists a distribution over covariance matrices Σ E Raxd with I
[IM (X) - 21 < a² it must hold that n 2 Ω X.M
E
8

---

Instead of giving the full proof, we give a sketch. The full argument can be found in Appendix C.I.
Proof Sketch. The outline of the proof involves (I) writing the Gaussian distribution / (0, Σ) as an exponential family, (2) defining a distribution from which v is drawn, (3) showing that estimating the deviation of the natural parameter vector from the midpoint reduces covariance estimation (so lower bounds for the former also apply for the latter), (4) upper-boundigg the term E Srs], and
(5) applying Theorem 2.4 described at the end of the previous section.
Step (1) is non-trivial because the standard way to write N (0, Σ) as an exponential family involves setting 17 to be equal the canonical flattening of the precision matrix (Σ-1)² (Fact F.3). However, we cannot use this representation, because E-1 symmetric, preventing the components of from being generated independently, as is required by Theorem 2.4 Thus, we consider an alternative parameterization. This involves identifying an upper-triangular matrix U such that Σー1 U + U and setting the parameter vector to be equal to 2U". The two parameterizations are equivalent (see Lemma C.I).
Step (2) employs a variant of construction that has appeared in [LSUU1 (see Algorithm 1). The process consists of sampling the elements of the precision matrix uniformly at random from intervals of width 1/(2d). For the diagonal elements, these intervals are centered at 3/4, whereas for the non-diagonal elements they are centered at the origin. The process is analyzed in Lemma C.2.
Step (3) requires us to describe an algorithm which, given oracle access to (s, 6)- estimate of E that is o-accurate in Mahalanobis norm, produces (e, 6)-PP estimate of the natural parameter vector that is O (a) -accurate in fo-nmm. The idea is to calculate Σ-1, obtain a projection Σ-1 of onto the support of the output of the algorithm described in step (2), find an upper-triangular matrix Algorithm 2, and for the propositions that formally establish the reduction see Lemma C.4 and Corollary C.5.
U such that Σ-1 U + U and output 27 m. For the full algorithm,
Step (4) is given in Lemma C.7. The calculation involves appealing to technical result from DKK*16 (Proposition C.6).
Step (5) requires us to upper-bound the tail of [X;) - urllz- This is done in Lemma C.8. The strategy we follow is the one described in Remark B.3. We use a bet-based argument (see Definition E. and an application of the Hanson- Hanson-Wright inequality (see Fact F.7). Then, we proceed to identify the appropriate range for 8 and obtain our sample complexity lower bound by working as described at the end of Section 2.3
3.2 Estimation with Respect to the Spectral Norm
Here, we prove a lower bound for covariance estimation of high-dimensional Gaussians in spec- tral norm under the constraint of approximate DP. Employing a reduction-based approach from Mahalanobis estimation to spectral estimation, we directly leverage the results of Section [.1]
Theorem 3.2. There exists distribution over covariance matrices Σ, E Raxd with I I Σ such that, given E D and ~ N (0, Σ) @n for any a = O(I/Vd) and any (s, 0)DP mechanism M: Raxd + ddxd with 5, E [0, 1}. and 8 < O(min {1/n, d? (innnd/(nooon (n//nnooll//n (ong//n//// ()) that satisfies
(M ΣンΣー S a², must hold that n 2
27
41.6
X.M
The proof is reduction via the property |||]| S vd[|AA12. We defer it to Appendix C.2.
4 Lower Bound for Private Heavy-Tailed Mean Estimation
In this section, we state the lower bound for mean-estimation of distributions with bounded second moment with respect to the & norm and sketch its proof, but defer the details to Appendix D. Theorem 4.1. Let 'D be a distribution over Rdd with second moments bounded by 1 and unknown mean μ. Then, for any S 1, any (c, 5)-DP mechanism with 5 S that takes X ~ D& as input and outputs M (X) satisfying E X.M || (X) m1 < a² requires n 2 Ω a

---

Proof Sketch. We use the DP Assouad lemma of [ASZ2I]. To apply the method, we construct a family of distributions indexed by the points of the binary hypercube E == { 1-11 1)a Define
p (2a²) /d and t = Vā/(v2a). Then for each v E Eg, we define a distribution D. over IR such that for X ~ D., the following holds.
x; = 1,t, with probability
Vi E [d].
0, with probability 1 1-p"
It can be shown that the second moment of D, is at most pt² 1.
For u. Ed, we define the loss function between D, and D, to be ((0(D.), (D.)) ||0 (Dw) - 8 (D+) This implies that (as defined in Lemma A.4) T = 2p = 2p. On rearranging the terms in Lemma A.4, the above gives D 0.04/(= 5).
The final task is to show that there exists a coupling (X; Y) between the mixture distributions p+ and p-; (as defined in Lemma A.4) with the appropriate value of D) = IE [dHam (X,Y)) Y)]. Here, we
just construct such a coupling, but verify the bound on D in the appendix. Let (X, Y) be follows. For every row X, X, if X * O, then Vj = -Xj.. otherwise Y; X For all other coordinates k * i, Y X We show that in this case. D np. This gives us D/p = n 2 d/150(= + +))a)) which proves the theorem.
5 Conclusions and Open Problems
In this work, we gave nearly tight lower bounds for private covariance estimation with respect to the Frobenius and spectral norms under the Gaussian distribution and for mean estimation with respect to the f2-norm under distributions with bounded second moments. This constitutes important progress in the lower bounds literature under approximate differential privacy. On technical level, we significantly generalized the fingerprinting method. An obvious question is whether the fingerprinting method can further generalized and what are its limitations. A second obvious question is to generalize Theorem 4. for higher-order moments.
Another question involves expanding upon the results of Theoreems 3.1 and 3.2 to hold in the regimes ((Vd) and a O (1), respectively. For Frobenius estimation, the condition a O (1) is consequence of the distribution over covariance matrices that we used to prove the result, whereas for spectral estimation the condition a = O11/V)) is an artifact of our reduction-based approach. Especially in the latter case, would be interesting come up with "direct" way to obtain the lower bound, instead of reducing from Frobenius estimation.
Finally, interesting open question may be to obtain lower bounds for the problems considered here in the high-probability regime. Specifically, the guarantees in our lower bounds are expressed in terms of the MSE and in Section 1.1 we sketched the argument convert them constant probability guarantees. It would be interesting to come up with techniques to prove tight lower bounds when the probability of success is 3 for 3 (0, 1). This was done in the context of pure differential privacy in [HKM21]
Acknowledgments
The authors would like thank Jonathan Ullman for helpful feedback the manuscript, Haoshu Xu for identifying a bug in the proof of Lemma 2.3 which affected how the range of 8 is identified in Theorems 3.1 and G.4, as well as the anonymous reviewers NeurlPS for their comments.
GK was supported by an NSERC Discovery Grant, an unrestricted gift from Google, and a University of Waterloo startup grant. AM was supported by NSERC Discovery Grant and a David R. Cheriton Graduate Scholarship. VS was supported by an NSERC Discovery Grant.
References
[AAK21] Ishaq Adi.-Ali, Hassan Ashtiani, and Gautam Kamath. On the sample complexity of privately learning unbounded gigh-dimensional gaussians. In Proceedings of the 32nd International Confer- Algorithmic Learning Theory, ALT '21, pages 126..16. JMLR, Inc., 2021.
10

---

[AAL2I] Ishaq Aden-Ali, Hassan Ashtiani, and Christopher Liaw. Privately learning mixtures of axis- aligned gaussians. In Advances in Neural Information Processing Systems 34, NeurIPS '21. Curran Associates, Inc., 2021.
[ADK19] Brendan Avent, Yatharth Dubey, and Aleksandra Korolova. The power of the hybrid model for mean estimation. Proceedings on Privacy Enhancing Technologies, 2020(4):48- 68, 2019.
[AL21] Hassan Ashtiani and Christopher Liaw. Private and polynomial time algorithms for learning Gaussians and beyond. arXiv preprint arXiv:2111.11320 2021.
[AMB19] Marco Avella-Medina and estimators, arXiv preprint arXiv: arrivvI906.111 1923, 2019.
Brunel. Differentially private sub-Gaussian location
[ASZ18] Jayadev Acharya, Ziteng Sun, and Huanyu Zhang. Differentially private testing of identity and closeness of discrete distributions. In Advances in Neural Information Processing Systems 31, NeurlPS 18, pages 1578-6891. Curran Associates, Inc., 2018.
[ASZ21] Jayadev Acharya, Ziteng Sun, and Huanyu Zhang. Differentially private Assouad, Fano, and Le Cam. In Proceedings of the 32nd International Conference on Algorithmic Learning Theory, ALT 221, pages 48 78-78. JMLR, Inc., 2021.
[BD14] Rina Foygel Barber and John C Duchi. Privacy and statistical risk: Formalisms and minimax bounds. arXiv preprint arxiv: (tfi::441.445555 2014.
[BDKU20] Sourav Biswas, Yihe Dong. Gautam Kamath, and Jonathan Ullman. Coinpress: Practical private mean and covariance estimation. Advances in Neural Information Processing Systems 33, NeurlPS '20, pages 14475-14485. Curran Associates, Inc., 2020.
[BG Gavin Brown, Marco Gaboardi, Adam Smith, Jonathan Ullman, and Lydia Zakynthinou. Covariance-awart private mean estimation without private covariance estimation. arXiv preprint arXiv:2106.13329 2021.
[BKSW19] Mark Bun, Gautam Kamath, Thomas Steinke, and Zhiwei Steven Wu. Private hypothesis selection. In Advances in Neural Information Processing Systems 32, NeurIPS '19, pages 156-167. Curran Associates, Inc., 2019.
[BS98] Dan Boneh and James Shaw. Collusion-secure fingerprinting for digital data. IEEE Transactions Information Theory, 44(5); 1897-1959 1998.
[BS19] Mark Bun and Thomas Steinke. Average-case averages: Private algorithms for smooth sensitivity and mean estimation. In Advances in Neural Information Processing Systems 32, NeurIPS '19, pages 191- Curran Associates, Inc., 2019.
[BST14] Racf Bassily, Adam Smith, and Abhradecp Thakurta. Private empirical risk minimization: Efficient algorithms and tight error bounds. In Proceedings of the 55th Annual IEEE Symposium Foundations of Computer Science, FOCS '14, pages 464 473, Washington, DC, USA, 2014, IEEE Computer Society.
[BSU17] Mark Bun, Thomas Steinke, and Jonathan Ullman. Make up your mind: The price of online queries in differential privacy. In Proceedings of the 28th Annual ACM-SIAM Symposium on Discrete Algorithmss SODA '1, pages 1306-1325, Philadelphia, PA, USA, 2017. SIAM.
[BUV14] Mark Bun, Jonathan Ullman, and Salil Vadhan. Fingerprinting codes and the price of approxi- mate differential privacy. In Proceedings of the 46th Annual ACM Symposium on the Theory of Computing, STOC 14, pages 1-10, New York, NY, USA, 2014. ACM.
[CWZ19] T. Tony Cai, Yichen Wang, and Linjun Zhang. The cost of privacy: Optimal rates of convergence for parameter estimation with differential privacy. arXiv preprint (oXXvv/992..44// 2019.
[DFM+20) 20) Wenxin Du, Canyon Foot, Monica Moniot, Andrew Bray, and Adam Groce Diffcrentially private confidence intervals. arXiv preprint arXiv:2001. 002285, 2020.
[DHS15] Ilias Diakonikolas, Moritz Hardt, and Ludwig Schmidt. Differentially private learning of structured discrete distributions. In Advances in Neural Information Processing Systems 28, NIPS '15 pages 2566-2574 Curran Associates, Inc., 2015.
[D/W13] John C. Duchi, Michael Jordan, and Martin J. Wainwright. Local privacy and statistical minimax rates. In Proceedings of the 54th Annual IEEE Symposium on Foundations of Computer Science, FOCS 13, pages 429 438, Washington, DC, USA, 2013. IEEE Computer Society.
11

---

[DKK* 16] Tlis Diakonikolas, Gautam Kamath, Daniel M. Kane, Jerry Li, Ankur Moitra, and Alistair Stewart. Robust estimators in high dimensions without the computational intractability. In Proceedings of the 57th Annual IEEE Symposium on Foundations of Computer Science, FOCS '16, pages 655-664, Washington, DC, USA, 2016, IEEE Computer Society.
[DKM*00] Cynthia Dwork, Krishnaram Kenthapadi, Frank McSherry, llya Mironov, and Moni Naor. Our data, ourselves: Privacy via distributed noise generation. Proceedings of the 24th Annual International Conference on the Theory and Applications of Cryptographic Techniques, EUROCRYPT '06, pages 486-503, Berlin, Heidelberg, 2006. Springer.
[DMNS06] Cynthia Dwork, Frank McSherry Kobbi Nissim, and Adam Smith. Calibrating noise to sensitivity in private data analysis. In Proceedings of the 3rd Conference on Theory of Cryptography, TCC '06, pages 265-284, Berlin, Heidelherg, 2006. Springer.
[DMR18] Luc Devroye, Abbas Mehrabian, and Tommy Reddad. The total variation distance between high-dimensional Gaussians. arXiv preprint arXiv: 181000060, 2018.
[DSS 15] Cynthia Dwork, Adam Smith, Thomas Steinke, Jonathan Ullman, and Salil Vadhan. Robust trace- ability from trace amounts. In Proceedings of the 56th Annual IEEE Symposium on Foundations of Computer Science, FOCS '15, pages 650 669, Washington, DC, USA, 2015, IEEE Computer Society.
[DTTZ14] Cynthia Dwork, Kunal Talwar, Abhradcep Thakurta, and Li Zhang. Analyze Gauss: Optimal bounds for privacy-presevingg principal component analysis. In Proceedings of the 46th Annual ACM Symposium on the Theory of Computing, STOC '14, pages 11-20, New York, NY. USA. 2014. ACM.
[HKM21] Samuel Hopkins. Gautam Kamath, and Mahbod Majid. Efficient mean estimation with pure differential privacy via a cum-of-squaress exponential mechanism. arXiv preprint a11iv:2111.12981, 2021.
[HLY21] Ziyue Huang, Yuting Liang, and Yi. Instance-optimal mean estimation under differential privacy. In Advances in Neural Information Processing Systems 34, NeurlPS '21. Curran Associates, Inc., 2021.
[HT10] Moritz Hardt and Kunal Talwar. On the geometry of diffcrential privacy, In Proceedings of the 42nd Annual ACM Symposimm on the Theory of Computing, STOC '10, pages 705-714, New York, NY, USA, 2010. ACM.
[Jor10] Michael Jordan. Lecture notes for Bayesian modeling and inference, 2010.
[KLSU19] Gautam Kamath, Jerry Li, Vikrant Singhal, and Jonathan Ullman. Privately learning high- dimensional distributions. In Proceedings of the 32nd Annual Conference on Learning Theory, 2019.
COLT 19, pages
[KLZ21] Gautam Kamath, Xingtu Liu, and Huanyu Zhang. Improved rates for diffcrentially private stochastic convex optimization with heavy-tailed data. arXiv preprint arXiv:2106.0133 2021.
[KM Gautam Kamath, Argyris Mouzakis. Vikrant Singhal, Thomas Steinke, and Jonathan Ullman. A private and computationally-effiiee estimator for unbounded gaussians. arXiv preprint 1oxXv:21111.06600 2021.
[KSSU19] Gautam Kamath, Or Sheffet, Vikrant Singhal, and Jonathan Ullman. Differentially private algo- rithms for learning mixtures of separated Gaussians. In Advances in Neural Information Processing Systems 32, NeurlPS '19, pages 168-180. Curran Associates, Inc., 2019.
[KSU20] Gautam Kamath, Vikrant Singhal, and Jonathan Ullman. Private mean estimation of heavy-tailed distributions. In Proceedings of the 33rd Annual Conference on Learning Theory, COLT '20, pages 2204 2235, 2020.
[KU20] Gautam Kamath and Jonathan Ullman. A primer on private statisties. arXiv preprint trXiv:2005.00010 2020.
[KV18] Vishesh Karwa and Salil Vadhan. Finite sample differentially private confidence intervals. In Proceedings of the 9th Conference on Innovations in Theoretical Computer Science. ITCS '18. pages 44:1 44:9, Dagstuhl, Germany, 2018. Schloss Dagstuhi-Leibniz-zzen
fuer Informatik.
[LKO21] Xiyang Liu, Weihao Kong, and Sewoong Oh. Differential privacy and robust statistics in high dimensions. arXiv preprint arXiv:2111.06578. 2021.
12

---

[LSA+21] Daniel Levy. Ziteng Sun, Kareem Amin, Satyen Kale, Alex Kulesza, Mehryar Mohri, and Ananda Theertha Suresh. Learning with user-level privacy. In Advances in Neural Informa- tion Processing Systems 34, NeurIPS '21. Curran Associates, Inc., 2021.
[LSY+200 Yuhan Liu, Ananda Theertha Suresh. Felix Yu, Sanjiv Kumar, and Michael Riley. Learning discrete distributions: User item-level privacy. In Advances Neural Information Processing Systems 33, NeurIPS '20. Curran Associates, Inc., 2020.
[SU15] Thomas Steinke and Jonathan Ullman. Interactive fingerprinting codes and the hardness of preventing false discovery. In Proceedings of the 28th Annual Conference on Learning Theory, COLT 15, pages
2015.
[SU17a] Thomas Steinke and Jonathan Ullman, Between pure and approximate differential privacy. The Journal of Privacy and Confidentiality, 7(2)3 22, 2017.
[SU17b] Thomas Steinke and Jonathan Ullman. Tight lower bounds for differentially private selection. In Proceedings of the 58th Annual IEEE Symposium on Foundations of Computer Science, FOCS '17, pages 552-563, Washington, DC, USA, 2017. IEEE Computer Society.
[Tar08] Gabor Tardos. Optimal prohabilistic fingerprint codes. Journal of the ACM, 55(2), 2008.
[TVGZ20] Christos Tzamos, Emmanouil- Vasileios Matakis-GGaragkoon and Ilias Zadik. Optimal private median estimation under minimal distributional assumptions. In Advances in Neural Information Processing Systems 33, NeurIPS '20, pages 3301-333 3311. Curran Associates, Inc., 2020.
[WXDX20] Di Wang, Hanshen Xiao, Srinivas Devadas, and Jinhui Xu. On differentially private stochastic convex optimization with heavy-tailed data. In Proceedings of the 37th International Conference on Machine Learning, ICML '20, pages (0081-1009) JMLR, Inc., 2020.
[ЛККW20] Huanyu Zhang, Gautam Kamath, Janardhan Kulkarni, and Zhiwei Steven Wu. Privately learning Markov random fields. In Proceedings of the 37th International Conference on Machine Learning, ICML '20, pages 11129-11 1119111140,.1111011111111-111111 JMLR, Inc., 2020.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] See Section 5
(c) Did you discuss any potential negative societal impacts of your work? [N/A]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes] See Appendices A-G.
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or as URL)? [N/A]
(b) Did you specify all the training details (e.g.. data splits, hyperparameters, how they were chosen)? [N/A]
(c) Did you report error bars (e.g., with respect to the random seed after running experi- ments multiple times)? [N/A]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [N/A]
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
13

---

(d) Did you discuss whether and how consent was obtained from people whose data you' re using/curating? [N/A]
(c) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
14


Reviews:
[{"review_id": "w7nsNcnudux", "reviewer": "Reviewer_eSVJ", "summary": "This paper provides new tight lower bounds for private estimating the covariance matrix of a Gaussian and private mean estimation of heavy-tailed distributions over $\\mathbb{R}^d$.\nPrevious results gave similar lower bounds under simplified assumptions (e.g., pure DP or product distributions). This paper fills a number of gaps by presenting lower bounds for non-product distributions under approximate DP.\nMost of the presentation is devoted to the former lower bound (covariance matrix estimation), which is achieved using a new generalized “Fingerprinting Lemma” for exponential families.\n\nThe fingerprinting lemma [Bun, Steinke, Ullman, SODA 17] gives a way to sample n codewords in dimension $d=O(n^2)$ such that every algorithm that estimates the average of the points “too well”, must be “too correlated” with one of the codewords, and thus cannot be private.\nThe main bottleneck of the above approach is that the codewords are sampled from product distribution, and therefore provide lower bounds only for that cases.\n\nThis paper provides a new FP lemma (Lemma 2.2) that extends the original one to exponential families which capture a wider range of distributions. Moreover, it does not focus on estimating the average of the points, but on estimating the “natural parameter vector” $\\eta$ of the family, which captures the parameters of a specific family (E.g., if the family is all the Gaussians of the form $N(0,\\Sigma)$, then $\\eta$ is essentially a vector representation of the covariance matrix $\\Sigma$). \n\nThe new FP lemma is used to prove a new lower bound for privately estimating the natural parameter vector of a distribution from a general exponential family (Thm 2.5). \nApplying Thm 2.5 to the problem of estimating the covariance matrix yields (with some additional work) a tight $\\tilde{\\Omega}(d^2)$ lower bound for estimating the covariance matrix in Frobenius norm (Thm 3.1). The latter is then used for proving a tight lower bound of $\\tilde{\\Omega}(d^1.5)$ for estimating the covariance matrix in the Spectral norm.\n\nFinally, in section 4 (page 9), the $\\tilde{\\Omega}(d)$ lower bound for private mean estimation of heavy-tailed distributions is given, which is based on a different known method of Assouad (rather than fingerprinting).\n", "questions": "1) In lines 56-59, you mention that the lower bound in Frobenius norm (Thm 1.1) matches the non-private sample complexity, while the lower bound in Spectral norm (Thm 1.2) does not (there is a $\\sqrt{d}$ gap). First, can you explain (or provide reference) why the sample complexity of estimating the covariance matrix in spectral norm without privacy is $O(d)$? \nSecond, how can it be that Thm 1.1 is tight (w.r.t. d) also for non-private algorithms while Thm 1.2 is not? I’m asking because Thm 1.2 is proven directly from Thm 1.1, so why the same arguments do not follow in the non-private case (providing a non-private analog of Thm 1.2)? What am I missing?\n\n2) Can you please explain how Thm 1.3 is different from other known lower bounds for DP mean estimation? For example, [Kamath, Li, Singhal, Ullman, COLT 19] proved that an approximate DP algorithm that accurately estimates the mean of a Gaussian $N(\\mu,I_{dxd})$ must incur an additive error of $\\tilde{\\Omega}(d)$. Since $N(\\mu,I_{dxd})$ has a second moment bounded by 1, it seems stronger than your statement. Is that correct?\n\nMinor issues/typoes:\n1) In the second equality after line 192: should $\\eta_j$ be t?\n2) In line 203: change Lemma 2.2 to Lemma 2.1. \n3) In Lemma 2.3: I think that $s$ is not defined at this point (only later).\n", "limitations": "In the “Conclusion and Open Problems” section (section 5), the authors address the limitations of their results.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n1) First tight lower bounds for the important problem of estimating the covariance matrix of a Gaussian under approximate DP.\n2) Interesting FP lemma for exponential families that can find other applications.\n3) New lower bound for mean estimation using Assouad’s method.\n4) Overall, good writing quality, well-organized, and looks sound (all missing proofs are given in the appendix).\n\nWeaknesses:\n1) The proof of the FP lemma for exponential families, which seems like the main technical contribution of this paper, is achieved using a natural extension of the proof of the original FP lemma [Bun, Steinke, Ullman, SODA 17]. This extension is definitely not straightforward and requires some technical work, but I don’t see something conceptually new in the proof technique. This similarity is currently not mentioned at all. It should be emphasized in the paper for making the presentation fairer, and for helping the reader to understand all the long calculations (which look much nicer in the simpler setting of [BSU17]).\n2) A comparison of the mean estimation lower bound (Thm 1.3) with previous lower bounds is missing. It is not clear to me if the statement itself is new or only the proof technique (Assouad’s method rather than FP lemma). See my second question in the next part.\n\nOverall, the strengths (especially the end results for covariance matrix estimation) seem to outweigh the weaknesses, and therefore I lean towards accepting this paper.\n", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "rDomioTuPax", "reviewer": "Reviewer_dVh8", "summary": "The goal of this paper is to prove lower bounds on the sample complexity needed for private statistical estimation. In the case of pure eps-DP, one can often use packing lower bounds to prove lower bounds. Lower bounds for approximate (eps, delta)-DP are often much more involved with one well-developed technique being the fingerprinting lemma. However, past works using the fingerprinting lemma required that underlying distribution be a product distribution. This left open lower bounds for some fundamental distributions such as Gaussian distributions.\n\nThe main technical contribution of this paper is a generalized fingerprinting lemma for exponential families. As an important application, they apply this new tool to derive Omega(d^2/alpha * eps) lower bound on the sample complexity needed to learn a single d-dimensional Gaussian, thus closing the gap for this distribution. As a second application, they provide a lower bound for mean-estimation of distributions with bounded second moments.", "questions": "I only have a couple of rather minor comments.\n- The paragraph around line 146 and line 164 has some repetition w.r.t. discussion about T. Also T is not defined here and it is only defined in the appendix.\n- Line 154: The second line is confusing to me: the authors say they assume the existence of vectors eta^1, eta^2 but for what purpose? What properties do these vectors need to satisfy? Is the eta drawn from some distribution that is supported between these two vectors?", "limitations": "Limitations discussion is fine.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths.**\nThis is a very fundamental problem and the literature was clearly missing a key tool that would allow us to prove optimal results in this area. This paper provided an important contribution in this area by giving us a new tool (based on fingerprinting) which allowed us to answer some fundamental questions in this area. Personally, I would like to dive further and learn more about the techniques in this paper.\n\n**Weaknesses.**\nNo concrete 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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "WtwOtppAaJT", "reviewer": "Reviewer_KYiN", "summary": "This paper generalizes the fingerprinting method of BUV14 to exponential families, and uses this result to prove lower bounds on approximate DP Gaussian covariance estimation and heavy-tailed mean estimation. ", "questions": "Heavy-tailed mean estimation: \n-Can you clarify what you mean by second moment bounded by 1? (e.g. coordinate-wise? central??) Also, the work https://arxiv.org/pdf/2106.01336.pdf gave a lower bound for strongly convex DP SCO (under zCDP -- not quite approximate DP) that seems to essentially be a reduction to mean estimation. So is your main contribution on this problem to be a strengthening of their construction from zCDP to approximate DP? Or am I misunderstanding something here? \n", "limitations": "Limitations - yes \nSocietal impacts - not addressed ", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths: \n\n-The results are very interesting and seem to expand the DP lower bound toolbox. \n\nWeaknesses: \n\n-Insufficient clarity on the distinction between the proposed method and existing methods. It is explained at a high level in the introduction, but still not as clear or precise as I would like. For example: I don't think it's made clear enough in what sense you generalize the fingerprinting method. Your method applies to exponential families, but what class did the method of prior works apply to? Also, a comparison/discussion of your lemmas and theorems with corresponding results in prior work would be very helpful. \n\n-Related to the above, I'm not sure I understand the main challenge in proving your results and how your proof approach/techniques differs from prior work. \n\n-Minor: Notation with $\\eta^i$ is a bit confusing at first glance because it looks like you're raising a vector to the power $i$. Subscript or parenthetical superscript would be clearer. \n\n", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept