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 authors consider the problem where, given a symmetric matrix $M$ and a vector of eigenvalues $\lambda$, we want to privately estimate a matrix that shares the same set of orthogonal unit eigenvectors as $M$ and has eigenvalues $\lambda$. They obtain new bounds for this problem thanks to a novel interpretation of the Gaussian noise as a Dyson Brownian motion. They apply their results to obtain bounds for covariance estimation, low-rank approximation and subspace recovery.
strengths_and_weaknesses: Strength: The interpretation of the Gaussian mechanism as an SDE is novel to the best of my knowledge and the way it is leveraged to obtain new bounds for these classic problems in private statistics is interesting.

Weakness: My main issue with the paper is that I feel that Assumption 2.1 is contrived. The authors argue that this condition is satisfied whp by Wishart matrices. However, other works I've read e.g., on the topics of PCA or subspace recovery assume that we have a range of eigenvalues (say the top $k$ eigenvalues) which are similar in magnitude, whereas there are gaps between them and the smaller eigenvalues. Judging based on that, I feel it's unnatural to assume the existence of additive gaps among the ``large" eigenvalues.

Comment: I have not gone through the proofs in the appendix in detail, because I am not too familiar with SDEs, so I can't really follow their low-level aspects. However, the high level picture described in the main body seems reasonable and I couldn't find any obvious faults.
questions: The thing I mainly want to ask from the authors it to justify Assumption 2.1 in the context of the problems they are considering e.g., by giving pointers to other papers with similar assumptions that are from the covariance estimation/PCA literature. Currently, I am leaning towards rejecting the paper, but I am willing to raise my score if the authors can convince me that their assumption is justified within the context of the problems considered and has not simply been imported from SDEs/random matrix theory.

=== UPDATE ===

After taking into account the rebuttal and discussion with other reviewers and the AC, I decided to raise my score from 4 to 6.
limitations: This is a purely theoretical paper, so it doesn't have an obvious societal impact.
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 gives a new analysis of the Gaussian noise mechanism for approximating covariances matrices with differential privacy. The basic mechanism is quite simple: given a private covariance matrix $M$, add a Gaussian noise matrix $E$ to form $\hat{M} = M + E$. For an appropriate choice of the variance of the Gaussian, $\hat{M}$ preserves differential privacy. Then one can use post-processing to compute some function of $f(\hat{M})$ and hope that this approximates $f(M)$. For example, $f( . )$ could be projection on the span of the top $k$ eigenvalues, or the best rank $k$ approximation.

The performance of the Gaussian noise mechanism for this class of problems was analyzed in an important prior paper of Dwork, Talwar, Thakurta, and Zhang. They also showed that, for some problems, the mechanism is worst-case optimal, and gave improved guarantees when the input matrix satisfies some spectral assumptions (large gaps between eigenvalues). 

The present paper gives a different analysis of the Gaussian noise mechanism, based on viewing the $\hat{M}$ as the value of a matrix-valued Brownian motion at some time $T$, where the Brownian motion starts at $M$. This induces an Ito process on the eigenvalues and eigenvectors of the matrix, and allows using Ito calculus to bound the error of the Gaussian noise mechanism for problems of the type described above. Generally, the bounds are better than prior work, but, as far as I understand, require stricter assumptions on the spectrum of $M$.
strengths_and_weaknesses: The new method of analysis via stochastic calculus is, in my opinion, the strongest point about this paper. This is a new approach, and may prove fruitful for other problems, or for deriving tighter error bounds.

On the other hand, the results themselves are hard to compare with prior work, since they require significantly stronger spectral assumptions. The authors also don’t clarify why these types of results cannot be proved using the techniques of reference [15]. This makes it hard to appreciate what is gained by adopting the machinery of stochastic calculus. It would be nice to have at least one application where the new analysis gives better results than prior work, without making any additional assumptions.

I also don’t understand how the results in this paper can be used for covariance approximation. The algorithm seems to require public knowledge of the eigenvalues of the input covariance matrix, but this is private information. The authors make one cryptic comment about this, but I still don’t understand how their framework can be used for this problem to get an actual differentially private algorithm.
questions: Can you give an argument why the stochastic calculus techniques give results that could not be proved with the techniques of [15], even under the stronger assumptions made in this paper? An informal argument would also be helpful. 

How can one use your analysis to give error bounds for covariance approximation, given that the eigenvalues of $M$ are private information and should not be used in post-processing without adding noise to them?
limitations: I don’t have concerns.
review_title: null

final_score: rating: 3: Reject: For instance, a paper with technical flaws, weak evaluation, inadequate reproducibility and incompletely addressed ethical considerations.
review_content: summary: This paper discusses a matrix approximation in the context privacy using Dyson Brownian motion. By assuming a gap in eigenvalues, the authors established an error bound in privacy.
strengths_and_weaknesses: The paper is well-written, easy to understand, and scientifically correct. In addition, it is the first time I have seen that DBM is used to prove results in privacy setting.
However, I have two concerns. First the paper is not that relevant to ML community, and it is essentially a problem of matrix approximation, and privacy just provides some possible context. Second the results in the paper are conceptually easy, and not too profound (most based on well known properties of stochastic calculus and DBM).
questions: The paper is well written and I don’t have questions.
limitations: NA
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 provides a new upper bound on the Frobenius-distance utility of the Gaussian mechanism for the general matrix approximation problem under differential privacy. The analysis utilize Dyson Brownian motion to track the evolution of the utility, which is, to my best knowledge, the first application of this mathematical tool. 
strengths_and_weaknesses: Strengths:
Originality: This paper's contribution is original given that this is the first improvement of the utility bound of Gaussian mechanism. It is very interesting to see the application of stochastic differential equations together with dyson brownian motion to be applied in the proof.
Quality: I briefly checked the proof, it looks sound to my best knowledge.
Clarity: Overall the paper is well organized. The problem studied, existing results, the major contribution are clearly stated. I have no difficulty in reading the paper.
Significance: From my own perspective, I would value this improvement of the utility bound. First, the matrix recovery problem and its privacy problem are critical in applications such as recommender systems. Second, existing result is definitely not tight and thus an improvement should be expected.

Weakness:
Significance: My major concern is on the assumption 2.1. It requires very specific eigengap conditions. Though the paper proves that Wishart matrices  satisfy this condition. It would be better to provide more justifications and examples on the assumption.
questions: 1. Can the author provide more examples and concrete justification  on the assumption 2.1?
2. The bound achieved in [15] is high probability bound while Theorem 2.2 is an expectation bound? Is it fair to direct compare these results?
limitations: The major limitation is the assumption seems to be too strong.
review_title: null

Meta-review: metareview: This paper brings new mathematical tools (Dyson Brownian motion) to analyze the utility of a new mechanism, which improves over existing techniques when certain conditions on the original matrix spectrum is met. Although the conditions can be restrictive, the novelty of the idea can open new doors to differential private mechanism design. 
confidence: Less certain
Decision: Accept