Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: 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. 
strengths_and_weaknesses: Strengths: 

-The results are very interesting and seem to expand the DP lower bound toolbox. 

Weaknesses: 

-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. 

-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. 

-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. 


questions: Heavy-tailed mean estimation: 
-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? 

limitations: Limitations - yes 
Societal impacts - not addressed
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: 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$.
Previous 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.
Most 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.

The 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.
The main bottleneck of the above approach is that the codewords are sampled from product distribution, and therefore provide lower bounds only for that cases.

This 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$). 

The 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). 
Applying 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.

Finally, 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).

strengths_and_weaknesses: Strengths:
1) First tight lower bounds for the important problem of estimating the covariance matrix of a Gaussian under approximate DP.
2) Interesting FP lemma for exponential families that can find other applications.
3) New lower bound for mean estimation using Assouad’s method.
4) Overall, good writing quality, well-organized, and looks sound (all missing proofs are given in the appendix).

Weaknesses:
1) 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]).
2) 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.

Overall, the strengths (especially the end results for covariance matrix estimation) seem to outweigh the weaknesses, and therefore I lean towards accepting this paper.

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)$? 
Second, 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?

2) 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?

Minor issues/typoes:
1) In the second equality after line 192: should $\eta_j$ be t?
2) In line 203: change Lemma 2.2 to Lemma 2.1. 
3) In Lemma 2.3: I think that $s$ is not defined at this point (only later).

limitations: In the “Conclusion and Open Problems” section (section 5), the authors address the limitations of their results.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: 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.

The 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.
strengths_and_weaknesses: **Strengths.**
This 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.

**Weaknesses.**
No concrete weaknesses.
questions: I only have a couple of rather minor comments.
- 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.
- 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.
review_title: null

Meta-review: metareview: This paper establishes improved and near-optimal lower bounds for private statistical estimation, specifically for private covariance estimation of a Gaussian and heavy-tailed mean estimation. The first result leverages a novel technical result, proved in this paper: a generalization of the fingerprint lemma (Bun, Steinke, Ullman' 17) to exponential families. The second result relies on a private version of Assouad's lemma (developed in recent work). The reviewers agreed that this is a technically novel and interesting work that clearly merits acceptance.
confidence: Certain
Decision: Accept