Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.
review_content: summary: This work considers list-decodable mean estimation: a small fraction (say 10%) of the data are iid draw from D, while the rest are adversarial. The goal is to output a finite number of estimates such that one of them approximates the mean of D. This had been broadly studied since [CSV17]. The main contribution of the current work is two-folds: 1) consider the sample complexity when the mean of D is sparse; and 2) design a new algorithm that runs in manageable time (in some regimes, polynomial time).

Overall, I think this is a solid work.
strengths_and_weaknesses: 
1. Understanding the sample complexity of sparse mean estimation is important, and the work presents an algorithm with sample size poly(k, log(n)). This significantly improves prior results which attained poly(n) (though without the sparsity condition).

2. The use of sparsity in SoS system is interesting.

3. The developed difference-of-pairs filtering algorithm looks interesting, which did not appear in the literature. That being said, it is unclear whether such technique is vital to tackling the underlying problem under bounded moment condition. For example, a concurrent work shows similar results under Gaussian distribution without the new filtering approach:

- List-Decodable Sparse Mean Estimation, Zeng & Shen, arXiv:2205.14337

4. An SQ lower bound is also established and is useful to understand the fundamental limits of statistical estimation. I think it will be helpful to expand a bit on technical innovation to derive such SQ lower bound. How does it differ from [DKS17]? 

5. While the SQ-type lower bound has been widely studied, it is weaker than information-theoretic bound. Can the authors comment on the challenge of characterizing the latter?

6. The description on sum-of-squares proof is rather short. I suggest authors include more background to make the paper self-contained. In particular, I saw that SoS is a useful tool to certify bounded moments, but is this the only purpose? Does it imply that for *any* general problems, SoS can be used in such a way as certification?
questions: See above.
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 studies the problem of list-decodable mean estimation in the sparse setting. For distributions that have certifiable bounded t-th moment in any k-sparse directions, it proposes an algorithm that achieves error of (1/alpha)^{O(1/t)} in a sample and computationally-efficient manner. For Gaussian distribution, it achieves error rate \sqrt{log(1/alpha)} with quasi-polynomial complexity. The work leverages a technique called the “difference of pairs filter”, which filters on the difference between pairs of points instead of the points themselves, and a rounding scheme that recovers a reasonably good estimation of the underlying distribution.

strengths_and_weaknesses: Strengthes: The problem of list-decodable learning has addressed a flurry of recent interest in the machine learning community. It concerns learning from modern data that is usually corrupted with a high amount of noise, thus is considered to be significant and relevant. The proposed technique “DoP filter” is quite novel, which elegantly leverages the fact that the differences between the good points are close to zero. The performance of the algorithms are near-optimal.

Weaknesses: The structure and the presentation of the paper can be better. For example, the introduction seems to take up to 4.5 pages of the main text, while the algorithms, theorems, and proofs take the rest, making it harder to appreciate the contribution of this work. 

questions: The structure of the paper can be improved (see Q2). It would be better if the technical highlights (probably for each algorithm) can be placed more evenly into the text, thus leaving the overview more concise. The paper can add more discussions on the merit of the “difference of pairs” technique and probably any other problems that could benefit from this new technique. 

limitations: The work seems not have any negative societal impact as it is purely theoretical.
review_title: null

final_score: rating: 8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.
review_content: summary: The field of algorithmic robust statistics is concerned with the development of efficient algorithms for statistical estimation problems in settings where the observed data is extremely (often adversarially) noisy. For the canonical problem of mean estimation, a single grossly corrupted data point can completely invalidate the performance of the sample average as a natural estimate of the population mean. In settings usually considered in this domain, one assumes that the algorithm observes $n$ data points generated in the following manner:

1. First $\alpha n$ ``good'' data points are generated from the true underlying distribution $D$.
2. An adversary then inspects the generated samples and adds an arbitrary set of $(1 - \alpha) n$ points to the dataset. Note that the algorithm is given no knowledge of where the corrupted data points are. 

Restricting to the specific problem of mean estimation in high dimensions where the data set $X = \left\\{x_i\right\\}_{i = 1}^n \subset \mathbb{R}^d$, the goal is to recover the mean of the distribution $D$ generating the good data points. This task is made complicated by the fact that the algorithm does not actually know which points these are and natural approaches such as distance based thresholding yield sub-optimal results. In the standard setting when $\alpha \in (1/2, 1]$, approximate identification of $\mu$ is possible with error (in Euclidean norm) ranging between $\sqrt{1 - \alpha}$ to $\alpha$ and computationally and statistically efficient estimators have been designed. In the more challenging list decoding setting when $\alpha < 1/2$, even approximate identification is not possible and one instead returns a list of $1 / \alpha$ estimates one of which is guaranteed to be close to $\mu$. Note that a list of this size is necessary by considering the special case where the data is generated from a mixture of $1 / \alpha$ well behaved distributions. Efficient estimators have also been proposed in this setting with the guarantee that at least one of the elements in the list is close to $\mu$. The degree of closeness ranges between $1 / \sqrt{\alpha}$ when only second moment assumptions are placed on $D$ with improvements possible when stronger restrictions are placed on the distribution. Typically, these involve higher order moments of the distribution and the recovery error correspondingly improves to $(1 / \alpha)^{O (1 / t)}$ if $t$ moments are available. 

This paper considers the list decodable setting in the sparse regime where $\mu$ is assumed to be $k$-sparse and $D$ is a distribution centered at $\mu$. In line with prior work on sparse estimation, the goal of the paper is to build an estimator whose sample complexity depends very mildly on the ambient dimension. All prior work incur sample complexity at least $d / \alpha$ which while optimal under no additional assumptions may be prohibitive when the ambient dimension is too large. The paper constructs a polynomial-time estimator which achieves sample complexity $\mathrm{poly} (k \log d)^{O(t)} / \alpha$ achieving recovery error of $(1 / \alpha)^{O(1 / t)}$ which is essentially optimal up to constants in the exponent when the distribution has $t$ certifiably good moments in sparse directions. Furthermore, the paper proposes a novel conceptually simpler approach to list-decodable estimation which avoids the more intricate filtering techniques used in prior work. 

In the ``multi-filter'' framework for building estimators in the list decodable setting, one starts with a candidate set of good data points and infers one of the following:

- The dataset is well behaved (in terms of its moments) and the empirical mean is a good estimate
- Alternatively, the dataset is poorly behaved but a certificate of this fact (usually a direction along which moments are not well concentrated) can be used to refine (remove bad points from) the dataset. One then constructs a set of subsets of the original dataset which are better behaved.

At the conclusion of this process, the empirical means of all the refined datasets are returned as candidates in the returned list. Carrying out this approach requires careful design of the filtering and pruning mechanisms to avoid exponential growth in the number and sizes of subsets obtained in the leaves. The intricacies of this approach make reasoning and analysis of these algorithms difficult motivating simpler alternatives. 

In the paper, the authors propose a novel approach where the start by constructing the difference of all pairs of of points in $X$ to construct a new $n^2$ sized dataset $T$. Crucially, all points $y = x_i - x_j$ when both $x_i$ and $x_j$ are drawn from $D$ have zero mean and have well-behaved moments around $0$. Furthermore, these points comprise a substantial $\alpha^2$ fraction of the dataset $T$. The authors then devise a one dimensional filter that given searches for points significantly increasing the sparse-directional moments of the set of datapoints $T$. Formally, one searches for a solution to the following set of polynomial constraints:
\begin{equation*}
    \\left\\{z_i^2 = z_i\\right\\}\_{i \\in [d]} \\cup \\left\\{v_i z_i = v_i\\right\\}\_{i \\in [d]} \cup \\left\\{\sum_{i \in [d]} z_i = k\\right\\} \cup \\left\\{\sum_{i \in [d]} v_i^2 = 1\\right\\} \cup \\left\\{\sum_{x \in T} \langle x, v \rangle^t \geq 6M|T| \\right\\}.
\end{equation*}
The first four encode a sparsity constraint in the direction $v$ while the last searches for a direction with large directional moment. Since, the above polynomial optimization is non-convex and in general NP-Hard, the paper instead solves a sum-of-squares relaxation. If no solution to the above set of equations is found, the process terminates with a well behaved set of points. Otherwise, the algorithm uses the solution to prune the points in $T$ to a smaller set with better moment behavior. A large good set exists because the $(\alpha n)^2$ sized subset consisting of pairs from the true distribution exists in $T$ and these points are very rarely removed. This step is conceptually similar to simple filtering strategies for the conceptually simpler iterative filtering setting where $\alpha > 1/2$.

Having pruned $T$ to a set with well-defined moments, the authors then design an intuitive procedure to identify a large subset of $X$ with substantial overlap with the good set and well-behaved moments. To do this, they note that $T$ induces a graph with vertices $X$ and pairs retained by the pruning process. The good set is expected to form an approximate clique within this graph. However, identifying a large clique is a hard problem in general. However, the authors observe that the graph has several nice properties. The first being that one can add edges between points $(x_i, x_j)$ whose neighborhoods have substantial overlap which also results in a larger corresponding difference set with well-behaved moments. The authors then show that if a random point from the set of good points is chosen and its neighborhood set is pruned based on the number of neighbors within the set, this yields a set of points with well behaved moments and large overlap with the set of good points. The mean of these points then yields a good approximation to the true mean $\mu$ from these two properties. Finally, selecting a point at random results in an point in the good set with probability at $\Omega (\alpha)$. Thus repeating this procedure $O(1 / \alpha)$ times results in a list of size $O(1 / \alpha)$ one of which is a good approximation to the true mean.

**** POST REBUTTAL UPDATE ****

I acknowledge the authors response and have decided to retain my current evaluation.
strengths_and_weaknesses: The paper makes good progress on the important problem of building robust estimators in the sparse regime. Furthermore, the natural framework proposed in the paper is substantially simpler than prior approaches to list-decodable estimation. However, it is not clear from the current draft the implications of this framework for other settings where much fewer moments are available in the good planted distribution. In particular, it is not clear if the exponent in the recovery guarantees are optimal when one is concerned with the heavy tailed regime. 

questions: One question I have for the authors is the implications of these results for list-decodable sparse mean estimation with fewer moments. For example, in the setting where the underlying distribution only has $2$ moments (bounded covariance), does this approach achieve the optimal recovery of $O(1 / \sqrt{\alpha})$ with say $\mathrm{poly} (k, \log d, 1/\alpha$ samples? This is in line with prior work on list decodable estimation which yield conceptually simpler algorithms in the bounded covariance setting albeit with worse recovery guarantees due to the milder moment requirements.

limitations: Yes
review_title: null

Meta-review: metareview: This work considers list-decodable mean estimation: a small fraction (say 10%) of the data are iid draw from D, while the rest are adversarial. The goal is to output a finite number of estimates such that one of them approximates the mean of D. This had been broadly studied since [CSV17]. The main contribution of the current work is two-folds: 1) consider the sample complexity when the mean of D is sparse; and 2) design a new algorithm that runs in manageable time (in some regimes, polynomial time).

The referees are unanimous in recommending acceptance. The review of Ymm8 had to be disregarded due to a COI.
confidence: Certain
Decision: Accept