Venue: NeurIPS 2022 Conference

Reviews:

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: Summary

The paper studies the connection between robustness and privacy. The paper begins by observing that the group privacy implies robustness, and group privacy follows by the standard (eps)-pure privacy as long as the failure probability of the (eps,0)-pure DP mechanism is small. A corresponding argument for the (eps,delta)-approximate DP also holds as long as delta is exponentially small.

This observation/meta-theorem allows the paper to borrow both computational and/or information-theoretic lower bounds from recent advances in high-dimensional robust statistics. The paper then derives various results for important statistical problems of the following flavor:  Consider the task A, then there is no (eps,0)-pure DP algorithm for task A that succeeds with probability delta, unless it either takes n >> n_0(eps,delta) samples (which is much larger than the sample complexity), or it does not run in polynomial time (under widely believed conjectures).

The main focus of the paper is on the problem of (Gaussian) sparse mean estimation. From [DKS17,BB20] it is known that the efficient algorithms for robust (Gaussian) sparse mean estimation requires quadratically more samples than the sample complexity. Combining this with the proposed meta theorem, the paper derives computational lower bounds for (eps,0)-pure DP mechanism that succeeds with high probability.

The main technical result of the paper is an efficient algorithm for private sparse mean estimation that matches the given computational lower bounds in the regime k \in [d^{0.4}, d^{0.5}]. The proposed algorithm is based on sum-of-squares and builds on the recent work of [HKM21]. 
strengths_and_weaknesses: # Strengths 

I believe the paper makes important first steps in formalizing the connections between efficient algorithms for robustness and privacy. 

The conceptual idea behind the meta theorem is simple and natural, which allows the paper to derive guarantees for many kinds of problems by borrowing results from algorithmic robust statistics.

I liked the paper, and thus I recommend acceptance. 

# Weakness

+ The polynomial time algorithm for private sparse mean estimation works in a restricted parameter of regime.


questions:  The computational lower bounds of this paper hold only for those private algorithms that admit an exponentially small failure probability. I understand that there might be problems that admit private and polynomial-time algorithms with optimal sample complexity in constant-failure-probability regime but not in exponential-failure-probability regime (as shown by the paper, sparse mean estimation). 
But even if a problem was hard in the constant failure probability regime (if there is such a problem), the meta-theorem of the paper will not be applicable. Do the authors have any comments on this limitation of their framework? Are there any candidates for private estimation tasks that might be hard even in the constant failure probability regime?


limitations: N/A
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 initiates a study of how privacy, success probability and computation resources are trade-offed in DP sparse mean estimation problem. Firstly, the paper establishes a simple connection between robust and differentially-private algorithms: private mechanisms which perform well with very high probability are automatically robust in the sense that they retain accuracy even if a constant fraction of the samples they receive are adversarially corrupted. By this connection and assuming the Brennan Bresler secret-leakage planted clique conjecture, this paper has provided a lower bound for this problem given the computation constraints. Meanwhile, an efficient algorithm based on SOS is proposed in this work.
strengths_and_weaknesses: Strengths:
1. The paper has revealed a connection between DP algorithms and robust algorithms. I think it is a simple but interesting observation which may lead to more information-theoretic bounds for both fields.
2. The sparse mean estimation algorithm based on SOS seems to have made a sound algorithmic contribution to the community.

Weakness:
1. The constraints in the connection between DP and robustness is relatively stringent: it requires either the DP algorithm succeeding with a super high probability or the robust algorithm having theoretical guarantees for relatively low $\eta$.
2. The lower bound of sparse mean estimation depends on one conjecture, and meanwhile the upper bound only works for some range of parameters. There is still a non-trivial amount left before closing the gap for all parameter ranges.
questions: 1. line 221, $\Omega$ should be $O$.
2. line 306, $\alpha <<1$.
limitations: NA
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 works with differential privacy and a specific notion of robustness, namely the $\eta$-contamination. The authors show that DP mechanisms can be robust as well, and characterize a trade-off between computational efficiency and privacy for sparse mean estimation. Furthermore, more efficient mechanisms are proposed.
strengths_and_weaknesses: The paper is clearly organized and sound as far as I can tell. The problems are important to work with and the improvement (from Table 1) is significant in the sense of poly time and robustness.

I think this paper is making a concrete contribution by proposing an actual mechanism that achieves the optimal tradeoff. However, my main concern is the motivation of the sparse mean estimation. See my questions below.
questions: While I understand the goal of sparse mean estimation as described in line 58-60, could the authors elaborate what is the application of sparse mean estimation? If such an application is empirically verifiable, the authors should experiment on it.
limitations: The authors have adequately addressed the limitations.
review_title: null

Meta-review: metareview: This work further explores the connection between outlier-robustness and differential privacy.
The first contribution of the paper is the following natural observation: group privacy implies robustness, 
and group privacy follows by the standard pure privacy as long as the failure probability is small. 
This allows the authors to derive lower bounds (information-computation tradeoffs and information-theoretic sample lower bounds)
for private estimation, as long as similar lower bounds are known in the robust setting. This includes Gaussian 
sparse mean estimation (the focus of this work) and several others. The technical contribution of the paper is an efficient
algorithm for private sparse mean estimation that matches the lower bounds in a restricted parameter regime. This builds
on recent work by Hopkins et al. (STOC'22).  The reviewers agreed that this work is conceptually interesting and recommended
acceptance.

confidence: Certain
Decision: Accept