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: The paper considers the problem of privately estimating the covariance matrix that corresponds to a dataset. Two algorithms are given, with each of them attaining better performance depending on the regime. The first algorithm is *trace sensitive*, in the sense that the error rate depends on the trace of the sample covariance matrix, which is equal to $\frac{1}{n} \sum_{i = 1}^n ||X_i||^2$. This algorithm yields a new worst-case upper bound on the error rate of $\frac{d^{\frac{1}{4}}}{\sqrt{n}}$ when $n^{\frac{2}{3}} \le d \le n^2$. The second algorithm is a *tail-sensitive* algorithm, in the sense that the error rate becomes worse when we have more data-points whose $\ell_2$-norm is close to $1$ (all points are assumed to exist in the unit ball).
strengths_and_weaknesses: Strength: The problem considered in this work is central to private statistics. Out of the $2$ algorithms proposed in the paper, the one that I found of greater interest was the tail-sensitive one. I found the way SVT was employed in the context of the algorithm to be quite interesting.

Weaknesses: I did not identify any obvious flaws or weaknesses.
questions: None for the time being.
limitations: The paper is a theoretical work and has no obvious societal impact.
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: This paper revisits the problem of differentially private (DP) covariance estimation. It provides bounds for three settings of the problem: (1) worst-case setting, (2) trace-sensitive setting, and (3) tail-sensitive setting. Several improvements are made for certain parameter regimes and types of DP notions over the prior work on this problem, and the algorithms provided are computationally efficient.

In the worst-case setting, in the high-dimensional case ($d>n^{2/3}$), a separation between the bounds is shown between pure DP and zCDP.

In the trace-sensitive setting, improvements in both pure DP and zCDP are shown via algorithms that are also more computationally efficient than those of the prior work.

The tail-sensitive setting also sees some improvements.

Both theoretical and experimental results are provided in this work, with the latter showing improvements on both synthetic and real-world datasets.

Edit: Updated my score.
strengths_and_weaknesses: Strengths:
1. Improvements are made upon the prior work in all the three listed settings, which I would say is important. Polynomial improvements in the results over prior work in the listed parameter regimes look quite decent, I think.
2. The separation in the worst-case setting for the high-dimensional setting between pure DP and zCDP regimes is somewhat significant. It means that for a decent range of parameters, there are newer and better tools at our disposal. I'm not fully convinced though that this regime is the most important one in terms of the significance of the contributions.
3. The algorithms (SeparateCov and AdaptiveCov) look simple enough, and easy to understand. It is surprising that such simple algorithms are able to improve upon existing work.
4. The experimental results are also in favour of their work for both synthetic and real-world datasets (MNIST and news commentary). In each, different variations are considered according to different parameters like $n$, $tr$, $d$, and $\rho$. AdaptiveCov seems more consistent in the experiments on the latter maybe because it seems to be choosing the best of (truncated) SeparateCov and GaussCov.

Weaknesses:
1. My main complaint with this work is the writing quality. In many places, the notations are unclear, broad statements are made, and things are ill-defined. I will elaborate all of these in later sections of this review.
2. I'm a little concerned that in the trace-sensitive setting, the SeparateCov algorithm is not able to improve upon the existing work for all settings. For lower trace, SeparateCov is better than GaussCov, but otherwise, it is not. So, it seems to be of limited utility to some extent.
3. The above seems to be a general concern for me for the entire paper, to be honest. Yes, for a decent range, the worst-case bounds are nicer and give a separation between two forms of DP. I'm not sure how strong the results are owing to these constraints on the dimension.
questions: I do have a few questions.

1. Where are the results for the worst-case setting? I would expect a theorem or something in the main body or somewhere about it. I read a subsection about it in the introduction, but that's pretty much it.
2. Section 1.2, Line 39. What is $\Sigma$? Are you defining a notation here, or referencing something else?
3. Line 41. Is $A = (X_1,\dots,X_d)$? Or is $A$ the normalised, empirical covariance matrix? Please, be clear about your notations! It's not the responsibility of the reader to infer them.
limitations: 1. Please, explain what you mean by things like "worst-case", "trace-sensitive", and "tail-sensitive". These terms don't mean anything by themselves, as far as I know. It may be obvious to the authors, but even a one-liner for each in the main body would make it so much easier to distinguish among these settings. It is a little unpleasant as a reviewer and a reader, to be getting into the manuscript without knowing what the context is.
2. The first part of Lines 29-30 is a bit misleading. The lower bound from [KLSU19] is under a distributional assumption of a Gaussian with an almost identity covariance. The setting in this paper seems more empirical and under bounded norm assumption for the data.
3. In the second half of Section 1.3 (mostly from Line 75 onward), things don't make a lot of sense here without any context about what these settings are. The results are just stated without any meaning.
4. In the first paragraph of Section 2, there are really broad statements about the prior work without stating any specific error metrics and range bounds for the data. I would be more specific here.
5. In the related work about low-rank approximations under DP, I would also state the recent work of Singhal-Steinke 2021 on private subspace estimation.
6. Also, for the citation of DP with Definition 1, along with [DR14], please use [DMNS06]. The latter is the most important citation for the subject.
review_title: null

final_score: rating: 8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.
review_content: summary: The paper gives improved error bounds for releasing an approximation of a covariance matrix $\Sigma$ under approximate differential privacy/zCDP, breaking lower bounds that hold under pure DP for dimension d between n^2/3 and n^2, where n is the number of data points. (Privacy is relative to changing one data point, a d-dimensional *unit vector*.) The new bounds improve both existing worst-case bounds and bounds expressed in terms of the trace of the covariance matrix (generalizing the worst-case bounds) measured in terms of *Frobenius norm* of the error.

The approach is surprisingly simple, and also more computationally efficient than previous work: Release the eigenvalues with DP by adding noise to the exact eigenvalues. Estimate the eigenvectors by doing an eigendecomposition of the covariance matrix made private using the Gaussian mechanism. Then put everything together. (The paper also has a more sophisticated approach that improves on the simple method in a data-dependent way by carefully clipping data.)

Practicality of the methods is investigated through experimental comparison with the Gaussian mechanism and EMCov (NeurIPS '19). Good improvements are demonstrated on synthetic data as well as two real-world datasets. 
strengths_and_weaknesses: Strengths
* A polynomial improvement in error (for sufficiently large dimension) compared to EMCov (NeurIPS '19) as well as the Gaussian mechanism
* The mechanism is very neat --- it is surprising that it pays off to estimate eigenvalues and eigenvectors separately in different ways
* Experimental evidence of practicality

Weaknesses
* It is not clear how the bounds achieved relate to what can be achieved using general query release methods, for example simhash combined with methods for release of 2-way marginals
* There is no experimental comparison to CoinPress (NeurIPS '20), since CoinPress optimizes a Manahalobis distance and in general performs poorly in terms of Frobenius error; however there are covariance matrices for which these distance measures coincide, and where a comparison would make sense
* Arguably, for the real-world data sets used in experiments it does not seem natural to be interested in computing the covariance matrix
questions: * You assume vectors are unit length --- can you say something about to what extent this is a limitation of the approach, or whether (say) you can generalize to vectors with lengths in some fixed range?
* In the case of vectors from {$-1/\sqrt{d}, 1/\sqrt{d}$}$^d$ one can apply results on release of 2-way marginals to estimate the covariance matrix. How do your results compare to that approach?
* Do you have a use case/justification why one might be interested in the covariance matrix for the data sets you study? If not, are there other data sets with a more compelling use case you could try?

Comments
* It would be good to describe GaussCov together with Algorithm 1, rather than hidden in the preliminaries
* Line 263: Do you mean $10^{-10}$ rather than $1e^{-10}$?
limitations: I am satisfied with the paper discussion of limitations. Since this is a very general question it seems unlikely that there are negative societal impacts (and the authors do not discuss this).
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 authors consider the problem of releasing the empirical covariance matrix under concentrated differential privacy. Assuming a boundedness assumption on the l2 norms of the data points, they propose a new algorithm for the problem and show theoretically that it has a better error bound compared to the previous work in the regime where d is very large. They also give a trace-sensitive guarantee to exploit the situations where an average point has a small norm, as well as a tail-sensitive guarantee. 

The first algorithm is a combination of learning the eigenvalues and running PCA. I believe both of these individual steps are known in the literature. The tail sensitive result has more subtleties in order to pick the right threshold to clip the further points. 
strengths_and_weaknesses: Strength:

+ contributions to a well-defined and well-motivated theoretical problem in the DP literature
+ simple and intuitive algorithm which is implemented by the authors
+ empirical results demonstrating the effectiveness of the method

Weaknesses:

+ The problem of mean estimation has been mentioned throughout the text many times but the exact definition is missing. Do you mean estimation w.r.t. l2 error? It will help to define the problem of mean estimation and even covariance estimation formally.
+ The error bounds are only stated in terms of dimension and number of samples. The dependence on the privacy parameter is not explicit in these results
+ As far as I can tell, the experiments results also don't mention the value of epsilon either
+ It is assumed that all data points lie in a unit l2 ball. If we relax this to a ball of radius R, then I believe the authors error bound grows linearly with R. It is not clear if this linear dependence is optimal. Some discussion of the dependence on R will be useful. 
+ in some experiments the error increases with the number of samples, which seems odd.

questions: + It is somewhat strange that in some experiments the Frobenius error increases with n. Can you elaborate on that?

+ How does your method compare to the previous work in terms of dependence on the privacy parameters?

+ How did you pick epsilon in the experiments?


limitations: N/A
review_title: null

Meta-review: metareview: The reviewers all concurred that the main result of this paper is quite interesting. It privately estimates the covariance better than established methods in particular parameter regimes. Given the clear accept sentiments towards this paper, there was little additional discussion.
confidence: Certain
Decision: Accept