Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: summary: This paper studies the list-decodable mean estimation problem and proposes an algorithm that runs in nearly $k$-PCA time, which can be seen as a natural barrier to this problem. 
main_review: This paper studies the list-decodable mean estimation problem: that is, if only $\frac{1}{\alpha}$-fraction of the data is the good point, we want to output a list of $O(\frac{1}{\alpha})$ solutions, one of which is guaranteed to be close to the true mean of the distribution. This problem can be seen as an extended to the outlier robust mean estimation problem and has received significant attention in recent years. 
In this work, the authors give a new algorithm for the bounded covariance distribution that runs in $\tilde{O}(\frac{nd}{\alpha})$ time, which nearly matches the time to perform $k$-PCA on the data, which can be seen a natural bottleneck of this problem. This result is better than the previous one in [CMY20](FOCS 2020)(runs in time $\tilde{O}(\frac{nd}{\alpha^C})$ where $C \ge 6$) and only increase the error by logarithmic factor.

This paper first gives a simple version of the algorithm that runs in $\tilde{O}(\frac{n^2 d}{\alpha})$ but is conceptually new. Then, following the result in [DHL19], the author uses the matrix multiplicative weights regret minimization framework to reduce the runtime to $\tilde{O}(\frac{nd}{\alpha})$. One technical contribution here is to give a Ky Fan k-norm generalization of MMW.

This paper is technically very strong and the writing is well. The authors provide a lot of intuition for the proofs. This paper is a pure theory paper. However, a set of accompanying experiment results would be also nice.

Some minor questions:

- For the second "=" in the equation which starts in line 211, is it should be "$\le$" instead of "="?



limitations_and_societal_impact: See the "Main Review".
review_title: null

final_score: rating: 10: Top 5% of accepted NeurIPS papers, seminal paper
review_content: summary: This paper studies the fundamental task of list-decodable mean estimation in high dimensional space. This paper proposes a novel algorithm for bounded covariance distributions with optimal sample complexity and near-optimal error guarantee, running time in nearly-PCA time.

main_review: Strength: This paper improved all the previous results (e.g. [Charikar, Steinhardt, Valiant, STOC’17], [Diakonikolas, Kane, Kongsgaard NeurIPS’20], [Cheapanamjeri, Mohanty, Yau
FOCS’20]) running time. This paper is a truly breakthrough result.

More impressively, this paper proposed a super fancy technique called Subspace Isotropic FilTering
(SIFT) . To the best of my knowledge, I have never seen such a thing before, this is completely new. 

Clearly, this paper should be at least an oral presentation at NeurIPS.

Minor: 

In Reference, [AK+05], should be [AK05], the et al should be removed. This might be a bug of google scholar citation. Clearly, this paper only has two authors.

In Reference, the [DKK20] conference information is missing. It is a NeurIPS 2020 paper.

In Reference, the [LY20] conference information is missing. It is a NeurIPS 2020 paper.

In Reference, the [JLT20] conference information is missing, it is a NeurIPS 2020 paper.

This paper mentioned SDP in a number of places. Several recent, state-of-art SDP solvers should be cited ``A Faster Interior Point Method for Semidefinite Programming’’ and “Solving Tall Dense SDPs in the Current Matrix Multiplication Time”.

limitations_and_societal_impact: Limitations are not mentioned. However, this paper is a super fancy theory paper, in order to make it more practical might take more efforts. Societal impact is not mentioned and since this paper is pure theory, it does not have a direct societal impact.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This article is abound list-decodable learning in which we consider the mean estimation problem when more than half of the data are corrupted data. In this framework, the mean cannot be recovered exactly but one can obtain a list of $k$ potential mean and say that the mean of the inliers is among these $k$ values. This article exhibit an algorithm that attain optimal statistical bounds (up to log factors) in a linear running time (linear in the sample size but also the dimension and in $k$). 
main_review: The article is quite significant because it exhibit a considerable faster algorithm than previous works for the same optimal error guarantees.  The article is clear and the quality of the redaction is ok.

Remark : I would ask the authors to be more mindful of the abbreviations they use. Their are a lot of abbreviations that are not transparent, for instance the notation PCA is never made clear in  the article : what algorithm does it represent exactly ?  Also SIFT is not transparent and in fact there already exist a SIFT algorithm in image processing so this might not be the best choice of name for the algorithm. Similarly the reader also have to remember what is MMW...
limitations_and_societal_impact: The article would greatly benefit from some practical experiments. The theory is stated up to a constant and in practice if the constant in the big O are large, then even though the algorithm is nearly PCA time, it may not be computable. Please provide a proof of concept, even on a corrupted mixture of spherical Gaussian this would already be a good illustration to show that the algorithm work in practice.
review_title: null

Meta-review: This paper gives a nearly "PCA" time algorithm for the problem of list-decodable mean estimation. There are two relevant parameters in the problem: the underlying dimension d, the number of samples n, and the fraction of inliers \alpha. There's a significant history of works on this problem -- starting with polynomial (but large exponent) running time in both d and 1/\alpha. A significant leap was made in a recent work that gave linear time algorithm in nd but a large polynomial (1/\alpha^5) dependence on \alpha. This paper resolves the issue completely and gives an algorithm with a quasi-linear dependence in nd/\alpha. 

List-decodable mean estimation is a fundamental question in algorithmic robust statistics (it generalizes mean estimation and spherical mixture clustering problems) and finding efficient algorithms for the problem is an important research direction. This paper makes a foundational contribution to this area by giving a nearly optimal algorithm for the problem. While there were concerns of whether the nearly optimal running time in this paper translates into practical gains, the authors' response convincingly clarified that a provably linear time algorithm paves the way for a practically fast one. 

We recommend acceptance. 


Decision: Accept (Spotlight)