Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: summary: New algorithms for estimating Gaussian means that are both robust and differentially private. 
main_review: This paper provides two new results on estimating the mean of a distribution via algorithms that are both robust (to an $\alpha$ fraction of corruptions) and differentially private. 

There are two new algorithms: 

1. An exponential-time algorithm that samples from the "exponential mechanism" (Gibbs distribution) over a rough bounding box for the distribution. The score function for the exponential mechanism is the Tukey depth of a point in the data set. The authors observe that this empirical Tukey depth is close to the analogous population quantity on correctly distributed data. (A similar reasoning underlies the simplest nonprivate robust estimation algorithm, which returns a point of maximimum Tukey depth. However, analyzing the randomized version requires understanding how the volumes of the level sets of the Tukey depth change with the depth.)

2. A polynomial-time algorithm based on the (nonprivate) matrix-multiplicative-weights-based robust of Dong, Hopkins and Li. It was a little hard for me to understand what the real technical insight here was, but it seems like an important contribution, and one that provides a good starting point for future investigations. 

The paper is clearly written and lays out its contributions succinctly. I think the authors could have done more to spell out dependencies on hidden parameters like R (the side-length of the bounding box from which the mean is drawn), and also to discuss how sensitive the results are to unknown co-variance structures. (For example, suppose we know a PSD matrix A such that the true covariance lies between $A$ and $cA$. Do the algorithm discussed here have sample complexity that scales polynomially with $c$? Logarithmically?) For what it's worth, I don't think it's fair to swallow dependencies on $R$ into the $\tilde O(\cdot)$ notation, since we don't know _a priori_ how $R$ relates to other quantities like $d$.

I view the contributions of the paper largely in formulating the problem and laying out initial solutions. I think it should be accepted based on those. That said, it would have been nice to understand what the technical roadblocks were to analyzing the noisy version of the MMW-based algorithm of Hopkins et al, and also to see some discussion of whether there are fundamental relationships between robust and private estimation in high dimensions—for example, is some automatic conversion between the two possible, along the lines of the work of Dwork and Lei (STOC 2009)? 


limitations_and_societal_impact: See main review for technical limitations. The work is theoretical and doesn't directly address (or imply) social impact.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: The paper proposes an algorithm which is both DP and robust for "poisoning attacks" for mean estimation. Namely, it can deal with an adversary corrupting \alpha*n many points and still produces a mean which is fairly close to the true mean (of the remainder of the points); and do which without directly looking at the point but rather statistical properties that are randomly perturbed in order to preserve DP. In addition to the theoretical work, there was also a few experiments conducted on the output of the mechanism.
main_review: I think this is an interesting paper that tackles DP-mean estimation from a new angle -- dealing with robustness and removing outliers. It is likely that it has implications - in terms of outlier detection - beyond what is discussed in paper and I am very fond of the idea of DP outlier detection/removal, as it means that the approach is likely to work even without some outlier.

On the flip side, I think that (a) the paper is poorly written (some mistakes are just plain embarrassing) and (b) I am baffled about the experiments. Firstly, as a theory-focused paper, I see little contribution in adding figures showing "the math works"; and more importantly, the first two figures are based on a very large \eps value (unless I misunderstood the experiment section) so they are of very little importance. So I am left with the rightmost figure (pun intended), in which the error doesn't decay to 0 as \eps increases. Is this a result of the fact that the robust mean estimation tends to be somewhat "off" even without privacy? A comparison to the non-private baseline would have helped here.

Still, all in all I think this is an interesting paper and I advocate acceptance. 

Typos:
* Line 110: The Lap-noise is to the power k, as each coordinate is perturbed.
* Line 121: \forall v.
* Line 139: The current set S_t (not S_0)
* Line 212: What's S'? Is this a general lemma for any S' or just for neighboring datasets?
* U_t^{(s)} has a completely unclear definition. You sum over r yet you do not use the index r at all! The summation -- should it be in the numerator? Is it in the right place in the denominator? (Maybe I am missing something here...)
* Section 2.3.2 needs a lot of work (at the expense of the discussion post Thm 6 + Sec. 5 which is mostly repetitive to the intro). What's the intuition for this \rho? Where did the 0.31 factor come from?
* Def 4.2: Don't get why S' has size (1-2\alpha) rather than (1-\alpha) and T should have size >= |S'|-\alpha*n, no? Some discussion as to the bounds in the resilience score would be much appreciated here.
* Line 351: Theta *inside* big O definition???


limitations_and_societal_impact: Irrelevant.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper shows results on robust and differentially private mean estimation of sub-Gaussian and covariance bounded distributions. So far, work has mostly been done in the direction of either robustness or of differentially private statistics, but this paper puts both of them together. Specifically, it provides near-optimal (but exponential time) algorithm and sub-optimal (but polynomial time) algorithms for mean estimation of the aforementioned types of distributions.

For their polynomial-time algorithm, PRIME, they use an MMW filter-based approach, which they privatise in a novel filtering algorithm (which they call, "DP-Threshold"). This reduces the iteration complexity of the filter and the number of database accesses in each iteration.

Their exponential-time algorithm exploits the resilience property of the distributions to bound the sensitivity of the robust mean.

Finally, they provide experimental results to back their theoretical results.
main_review: Update: Upon the authors' response, I have decided to update my final evaluation.

Strengths:
1. The paper is very technical, and clearly a lot of work went into it.
2. The paper is also quite well-written. It's organised and explains the background well enough.
3. It is the first paper to give results for robust and differentially private mean estimation of sub-Gaussians and covariance bounded distributions. So, there's novelty in it.
4. Their exponential-time algorithms are nearly optimal.
5. The experimental results indicate significant improvements over any kinds of prior work in differential privacy. However, it is important to note that the comparison with the prior work of [KLSU'19] is a bit apples-to-oranges, as their work does not focus on robustness at all.

Weaknesses:
1. Their polynomial-time algorithms have $O(d^{3/2})$ sample complexity. The authors do highlight this deficiency in their work. New techniques altogether may be required to solve this problem, it seems, since going via the route of private PCA would incur such big costs.
2. It is a bit surprising to see $(\varepsilon,\delta)$-differentially private algorithms needing a range on the mean $[-R,R]^d$. I say this because of the existence of stability-based methods in privacy. Is there a way to remove that dependence completely?
3. This is kind of a nitpick, and the authors discuss this, too. The third graph in Figure 1. The accuracy of their algorithm is worse than the differentially private prior methods for value of $\varepsilon$ less than $0.05$. This raises the question: are these algorithms really practical?

Comments:
1. Typo: Figure 1 - second graph - y axis should be labelled as $||\hat{\mu}-\mu||_2$.
2. Line 355 should read as: We show that robustness can be achieved...
limitations_and_societal_impact: Limitations have been mentioned in the detailed review. There doesn't seem to be any negative societal impact of this work.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: The paper considers the problem of robust mean estimation under adversarial contamination in the differentially private setting. In the canonical setting of robust mean estimation, one is given access to $n$ i.i.d samples from a well-behaved distribution over $\mathbb{R}^d$ and the goal is to estimate the mean of the distribution. The catch is that an adversary is allowed to inspect the samples and arbitrarily corrupt an $\alpha$ fraction of them. Standard assumptions on the distribution include assuming a spectral bound on the covariance matrix of the distribution although the optimal recovery guarantees improve under additional assumptions such as gaussianity. The key difference in the setup considered in this paper is that the algorithm is also required to be differentially private with respect to the data points. The problems of building robust and differentially private algorithms have received much attention in the recent part in isolation and building ones which satisfy both of these properties is a natural one. 
main_review: The paper considers the problem of robust mean estimation under adversarial contamination in the differentially private setting. In the canonical setting of robust mean estimation, one is given access to $n$ i.i.d samples from a well-behaved distribution over $\mathbb{R}^d$ and the goal is to estimate the mean of the distribution. The catch is that an adversary is allowed to inspect the samples and arbitrarily corrupt an $\alpha$ fraction of them. Standard assumptions on the distribution include assuming a spectral bound on the covariance matrix of the distribution although the optimal recovery guarantees improve under additional assumptions such as gaussianity. The key difference in the setup considered in this paper is that the algorithm is also required to be differentially private with respect to the data points. The problems of building robust and differentially private algorithms have received much attention in the recent part in isolation and building ones which satisfy both of these properties is a natural one. 

The paper proposes two main algorithms for the problem. The first is an algorithm which runs in polynomial time but suffers a sub-optimal sample complexity of $O(d^{3/2} / \alpha^2)$ (as opposed to the information theoretically optimal rate of $O(d / \alpha^2)$). The second is an exponential time algorithm which nevertheless obtains the optimal sample complexity up to log factors ($O(d / \alpha^2)$). The efficient algorithm itself seems to be largely an adaption of the filtering based approach to robust mean estimation where one first obtains a spectral certificate determining which data points are likely to be outliers and uses this certificate to either remove corrupted data points or downweighting them in the computation of the mean estimate. The looseness in the sample complexity is due to the differentially private singular vector computation step that is used to compute the spectral certificate. The in-efficient algorithm in the paper essentially computes a noisy estimate of the solution to a direction wise trimmed mean problem. Roughly speaking, one searches for a mean estimate whose projection onto any direction $v$ is close to the trimmed mean of the data points when projected onto $v$ where the trimming eliminates the top and bottom $O(\alpha)$ percentiles of the data points respectively. While this geometric insight existed in prior work as well, the adaptation to the differentially private setting (as done in Algorithm 2 of this paper) seems quite clever and novel even if it isn't emphasized as much. 

Overall, the contributions of the paper are valuable and interesting as the first work at the intersection of robustness and differential privacy. While the efficient algorithm is sub-optimal in terms of sample complexity, there seem to be clever insights in the construction of the inefficient algorithm which may enable future work on the topic. 

limitations_and_societal_impact: Yes
review_title: null

Meta-review: The reviewers agreed that this is a strong and interesting technical work. The authors are advised to address dependence on the range parameter R, since this is often important in DP estimation tasks, as well as some related work mentioned by reviewers. Some weaknesses identified by reviewers include experiments (which is not the main contribution of the paper) and the suboptimal sample complexity of the efficient algorithm (which seems like a significant open problem), which can both be overlooked.
Decision: Accept (Poster)