Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 4: Borderline reject: Technically solid paper where reasons to reject, e.g., limited evaluation, outweigh reasons to accept, e.g., good evaluation. Please use sparingly.
review_content: summary: This paper studies differential private estimation by taking advantage of some public data. It has been shown that some improvements on the sample complexity can be made when given a certain amount of public data.
strengths_and_weaknesses: Strengths: The targeted problem is interesting. The idea of taking advantage of public data is good. This paper is easy to follow. 

Weakness: 
(1) The organization of this paper should be improved. There are more than thirty pages appendix. The appendix is too long.

(2) This paper simply assumes the public comes from a Gaussian distribution. This assumption is too strong in realism. For example, the data in the economy and biology domain can usually be heavy-tailed. Is that possible to extend the current assumption to be a general one?

(3) In Algorithm 1, using only d+1 samples $\tilde{X}_i$ to obtain the covariance $\widehat{\Sigma}$ leads to inconsistent estimation, especially when the dimension d is large. Would this make the output inefficient in a certain case?

(4) Similarly, in Lemma 2.5, how could you make sure the matrix $\Sigma_Y=\frac{1}{L}\widehat{\Sigma}^{-1/2}\Sigma\widehat{\Sigma}^{-1/2}$ is positive definite?

(5) In Lemma 2.5, is the probability at least 1-$\beta$ going to 1 with the increasing of the dimension d? In the current presentation, it seems $\beta$ is an arbitrary constant greater than 0.

(6) No numerical performance is conducted to demonstrate the effectiveness of the proposed method.
questions: (1) This paper simply assumes the public comes from a Gaussian distribution. This assumption is too strong in realism. For example, the data in the economy and biology domain can usually be heavy-tailed. Is that possible to extend the current assumption to be a general one?

(2) In Algorithm 1, using only d+1 samples $\tilde{X}_i$ to obtain the covariance $\widehat{\Sigma}$ leads to inconsistent estimation, especially when the dimension d is large. Would this make the output inefficient in a certain case?

(3) Similarly, in Lemma 2.5, how could you make sure the matrix $\Sigma_Y=\frac{1}{L}\widehat{\Sigma}^{-1/2}\Sigma\widehat{\Sigma}^{-1/2}$ is positive definite?

(4) In Lemma 2.5, is the probability at least 1-$\beta$ going to 1 with the increasing of the dimension d? In the current presentation, it seems $\beta$ is an arbitrary constant greater than 0.
limitations: Yes
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 work studies differentially private estimation of Gaussian distributions and mixtures of Gaussians with additional public non-private data. For Gaussian estimation, the authors demonstrate that with a small amount of public data, the number of private samples required no longer depends on the bound on $\ell_2$ norm of the mean and condition number of the covariance matrix, and instead depends logarithmically on the discrepancy between public and private data distributions. For Gaussian mixtures, similar results are shown when the public and private distributions are the same.
strengths_and_weaknesses: Strengths:
- Understanding the performance of DP algorithms with public data is an important problem both in theory and in practice. The authors proved meaningful results in the context of estimating Gaussian distributions, which is a fundamental statistical estimation problem.
- For Gaussian mixtures, the improvement on $k$ is significant.
- The results are comprehensive. The paper studies both standard Gaussian estimation and mixture of Gaussian. Algorithms are designed for various scenarios.
- Overall, the writing is clear and well structured. The authors did a good job by motivating the algorithm ideas with a simple Gaussian mean estimation problem.

Weakness:
- For Gaussian estimation: considering that the dependence on dimensionality remains the same, removing the logarithmic dependence on range parameters might seem a weak improvement. The improvement can also be achieved by using approximate DP, which is often used in practice, so the practical implication of the result seems limited.
- I wonder if at least some of the results can be implied by the range-independent results for approximate DP. For $(\epsilon, \delta)$-DP, in the worst case roughly $\delta$ fraction of the dataset could be released as-is, which might be viewed equivalently as "public dataset". It would be great if the authors could discuss the connections.

---
Update: raised my score to 6 because the authors addressed the concern about the relation to $(\epsilon, \delta)$-DP.

questions: Questions regarding the results have already been stated in the Weakness section.

Suggestion on writing:
- The algorithm description for Gaussian mixture only consists of high-level ideas. Perhaps the technical contribution could stand out more if the authors could highlight a few important intermediate results or claims?
- Add a brief description about the problem formulation of estimating high-dimensional Gaussian and Gaussian mixtures.
limitations: Limitations and negative impacts are adequately addressed.
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 paper studies estimation a setting in which there are two sets of samples available: A "public" dataset, and a "private" dataset whose elements must be protected with differential privacy. This is studied for two classes of distributions: 1) d-dimensional Gaussians, and 2) mixtures of d-dimensional Gaussians. In case 2) the public dataset must come from the same distribution as the private one, but for 1) it suffices that it is a Gaussian that is "not too far" from the same distribution. In both settings it is shown that a small amount of public data (much less than what is needed for estimation) can be used to gear the utility of the private sample, lowering the sampling complexity.
In terms of techniques the algorithm for 1) uses the public data to do a parameter range estimation and then apply a private estimator that needs these parameters, a fairly natural (and generally applicable) idea. For 2) the public data is used to improve various steps in an existing algorithm [KSSU19], which is more involved.
strengths_and_weaknesses: Strengths:
- Addresses a timely and significant question (how to leverage public data) in two classical settings
- Adds to the theory of an approach that has shown great promise empirically, but where there is still only a limited theoretical understanding
- The fact that public samples from an "almost entirely dissimilar" distribution can help is intriguing and worth investigating in other settings (could lead to follow-up work)
- As far as I can tell, the technical contribution is solid (I am not familiar with all the past work on which this builds)
- The writing is clear and of high quality

Weaknesses:
- In setting 1) it was already known how to get results of a similar flavor without public data in the setting of *approximate* DP, so the advance lies only in obtaining pure DP, which is mainly of theoretical interest
- In setting 2) the public data must come from the same distribution as the private data, which is arguably a strong assumption. (I would guess it can be relaxed along the lines of case 1), but this is not worked out in the paper.)

questions: - Given the prior work, what do you mean more precisely by "we initiate the study" in the abstract?
- In Theorem 1.2, does $\gamma$ need to be known to the algorithm, or can the sample size somehow be adapted to how well the public distribution approximates the private one?
limitations: There is an adequate discussion of limitations. Potential negative societal impacts are unlikely, so not discussed.
review_title: null

Meta-review: metareview: This paper studies private estimation with a small amount of public data. The idea is that the small public dataset may allow for significantly stronger positive results (e.g., in terms of sample complexity of private data). The authors study two fundamental settings in this direction -- estimating a Gaussian and a Gaussian mixture -- and provide interesting and technically non-trivial positive results. The consensus from the reviews and subsequent discussion is that this work is both conceptually and technically interesting.
confidence: Certain
Decision: Accept