Venue: NeurIPS 2022 Conference

Reviews:

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: The paper considers the problem of robust sparse mean estimation. In this problem, we observe samples from a heavy-tailed distribution whose mean is a sparse vector. This distribution is assumed to have bounded variance and is assumed to satisfy a weaker form of bounded 4th moment assumption. In addition, it is assumed that a constant fraction of the samples are arbitrarily corrupted by a malicious adversary. For this problem, the authors propose a mean estimator which achieves convergence rates of the order $O(\sqrt{\epsilon} + \sqrt{k^2\log{d}/n} + \sqrt{\log(1/\tau)/n})$, where epsilon is the fraction of corruptions, k is the sparsity, d is the dimension, tau is the failure probability. The algorithm is based on the popular filtering algorithm and involves an additional truncation step for ensuring the samples satisfy the stability condition. 
strengths_and_weaknesses: First of all, I have been asked to review the paper at the last minute. So I didn't have time to read the proofs in the appendix. But, I have gone through the main paper. 

The paper addresses two corruption models simultaneously: malicious adversary model and heavy-tailed model. In addition, the paper tries to do sparse mean estimation. The heavy-tailed part in the paper looks interesting and could be useful to the community (especially given that there is no prior work which can get computationally efficient estimators for this problem). However, it is not immediately clear if the results for malicious adversaries are optimal, and is debatable (see below for more details). The core algorithmic ideas are not novel (except for the truncation step). The main novelty is probably in the analysis of the truncation step. Nonetheless, I believe the pros of the paper marginally outweigh the cons.

$$\textbf{Theoretical Results}.$$ 
1. $\epsilon\  \textbf{dependence}.$  It is not clear if the derived error bounds have optimal dependence on $\epsilon$. For bounded $4^{th}$ moment distributions, the optimal rates have $\epsilon^{3/4}$ dependence [1,3]. I understand that the paper considers a weaker condition than bounded $4^{th}$ moment. But the lower bounds presented in the paper don't clearly show what the optimal dependence should be. The current lower bounds only hold for $k>\epsilon^{-1/2}.$  For smaller $k$, will the lower bounds still be $\epsilon^{1/2}$? At least for the hard instance created in the proof, it looks like the lower bounds will be $\epsilon^{3/4}$ when $k=1$. Given this, it is hard to judge if the rates are optimal in $\epsilon$ for all $k$. 
2. $4^{th}$ $\textbf{moment condition}$. The $4^{th}$ moment condition in the paper looks weird. It is not a rotational invariant condition. Let's say I have a distribution which satisfies this condition. Now, I create another distribution by rotating this distribution such that the new distribution doesn't satisfy the moment condition. The algorithm works for the first distribution but not the second distribution. This naturally raises the question if this assumption can be further relaxed or totally removed. It'd be great if the authors try to relax this condition.

$$\textbf{Other comments}.$$
1. Some relevant work hasn't been cited [1,2]. The current work is certainly not the first to study sparse mean estimation in heavy-tailed settings with outliers. [1] considers the same problem as the one considered in this work and provides an optimal estimator, albeit they provide a computationally inefficient estimator. These works should cited and discussed in the paper.
2. At a number of places it is claimed that for robust mean estimation of Gaussian distribution, the error rates will scale as $O(\sqrt{\epsilon})$ (for example, Fact 1.2). This is not correct and needs to be fixed. The optimal error rates will scale as $O(\epsilon)$ [3]. 
3. Why is $||\cdot||\_{2,k} $ norm used instead of $||\cdot||\_{2}$ norm, if they are both equivalent upto constant factors?

[1] A Robust Univariate Mean Estimator is All You Need. https://proceedings.mlr.press/v108/prasad20a.html 

[2] A Unified Approach to Robust Mean Estimation. https://arxiv.org/pdf/1907.00927.pdf

[3] Recent Advances in Algorithmic High-Dimensional Robust Statistics. https://arxiv.org/pdf/1911.05911.pdf


-------------------------------------------------------------------------------------------------------------------------------------------
Update after discussion with other reviewers: I believe the heavy tailed results in the paper are useful, especially given that this is the first computationally efficient estimator in this setting. So I'm increasing my score.

questions: See above
limitations: See above
review_title: null

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 outlier-robust sparse mean estimation for heavy-tailed distributions. Prior work has considered robust sparse mean estimation for the light-tailed distribution (such as sub-Gaussian). The sample complexity for the proposed algorithm scales with k^2 log d, which is near optimal, and the assumption for the underlying heavy tailed distribution is mild. 

However, the technical contribution of this paper is incremental: the usage of coordinate MOM estimators for heavy tailed distribution is standard, and the filtering analysis basically follows from [BDLS17], which involves a time-consuming sparse PCA relaxation. Hence, given the theoretical guarantees of prior algorithmic result, the remaining challenge is to show that a large subset of the uncorrupted heavy tailed samples satisfies the “stability” condition.
strengths_and_weaknesses: Strength:

-- The introduction of the related work is comprehensive, and the theoretical presentation is clear. 
-- The theoretical guarantees matches the best-known results.

Weakness:

-- The theoretical innovation is quite limited.
-- The actual running time for the algorithm is very time consuming compared to other robust sparse mean estimators.
-- Provided vast literatures in robust sparse mean estimation ([BDLS17, DKK+19]), this paper does not have experimental comparisons to show potential superior performance than these baselines.
questions: The presentation of Algorithm 1 is confusing. It would be great if authors can present the algorithmic box in a self-consistent fashion.
limitations: Please refer to the Strengths And Weaknesses session.
review_title: null

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: This paper considers robust mean estimation problem with sparsity constraint for heavy-tailed distribution. The proposed estimator is claimed to achieve the first sample complexity which has a logarithmic dependence on the dimension and tightly matches with other parameters.
strengths_and_weaknesses: I appreciate authors' effort in the paper. But to be honest, this paper is out of my expertise, and I found it hard for me to write a review which makes some sense. The system also keeps failing to process my request for a change in reviewers. To keep a high quality of review, I will just make an educational guess, authors and other reviewers may just skip my review.

Thank you for the effort.

Reviewer
questions: N/A
limitations: Yes.
review_title: null

final_score: rating: 3: Reject: For instance, a paper with technical flaws, weak evaluation, inadequate reproducibility and incompletely addressed ethical considerations.
review_content: summary: The paper study robust mean estimation in a sparse high-dimensional setting. Specifically, the goal is to exhibit an estimator that verify the following properties: the estimator has a sub-gaussian concentration  around the true mean when the data are heavy-tailed, the error due to a proportion epsilon of corrupted data can be controlled and is of order $O(\sqrt(\epsilon))$. 

The authors use the $\ell_2$ norm of the $k$ largest coordinates of a vector in magnitude to define a sparse distance and they show how to construct an estimator verifying the aforementioned properties with respect to this distance. Thanks to this sparse notion of distance they replace the usual dimension-dependent error by an error that depends on $k$ which can be a lot larger when the data are truly sparse.
strengths_and_weaknesses: Strengths: This is mostly clear and states the assumptions and results properly. In general finding an estimator exhibiting optimal sub-gaussian rate and optimal corruption error is hard and this is the first algorithm I know that manage this in the sparse setting.

Weaknesses: The paper claims that the algorithm used can be used in practice but I have doubts about that (more details in the questions). Some of the constants are hidden and it would be interesting the magnitude of these constant clearly. The paper is not very original and the theoretical results are not very surprising for an untractable algorithm.
questions: 
- The estimator does not seem computable, which contrast with the author's claim that it is. The theorems provided in the article guarantee a polynomial complexity, however this does not guarantee that the estimator is computable in practice. Moreover, the choice of constants given in Section C.1 does not seem to be practical. Finally, no experiment were given with the article which seems to indicate that it is not usable in practice. Could the authors comment on that ?

- Would the analysis still work with only two finite moments  ? Is a fourth finite moment something that is needed for the algorithm to work ?

- The algorithm for now needs to know $\epsilon$. Is there a hope to give an algorithm that does not need the knowledge of $\epsilon$ ? For example the Tukey median does not need the knowledge of $\epsilon$ but it is not computable.

- The constants are hidden even though it can be very important to have tight constants in front of the leading term (See Catoni "Challenging the empirical mean and empirical variance: a deviation study" (2012) and the more recent work of S.Minsker "U-statistics of growing order and sub-Gaussian mean estimators with sharp constants" (2022) investigating this problem in dimension 1). If the constants are very far from being tight, it should be said in the article.

- Even though the authors claim that $O(\sqrt{\varepsilon})$ is optimal in your setting, this does not seem to be true. When the data have a finite fourth moment as in Theorem, $O(\varepsilon^{3/4})$ and more generally when the data have $q$ finite moments, the optimal error is $O(\varepsilon^{1-1/q})$ (see S. Minsker "Uniform bounds for robust mean estimators" for example). This discrepancy seems to be due to the requirement of $k \ge 1/\sqrt{\varepsilon}$ in Lemma E.1. When $\varepsilon$ goes to $0$, this requirement is very strong. On the other hand, when $\varepsilon$ is larger than some constant $\varepsilon_0$, then we can say that $\sqrt{\varepsilon}\le \varepsilon/\varepsilon_0$ and hence $O(\sqrt{\varepsilon})=O(\varepsilon)$ which makes me think that the interesting case is when $\varepsilon$ goes to $0$. Could the authors comment about that ?

limitations: No potential societal impact.
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: Algorithmic robust statistics is concerned with building efficient algorithms for statistical estimation problems when the observed data contains adversarial or heavy-tailed noise. 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 the problem of heavy-tailed mean estimation under the strong contamination model, one observes $n$ data points generated in the following manner:

1. First $n$ ``good'' data points are generated from the true underlying heavy-tailed distribution $D$. Note that assumptions on $D$ are usually very mild -- often only that its variance exists. 
2. An adversary then inspects the generated samples and corrupts an arbitrary set of $\epsilon n$ points in a completely unconstrained manner.

Given a target failure probability $\delta$ and corrupted dataset  $X = \left\\{x_i\right\\}_{i = 1}^n \subset \mathbb{R}^d$, the goal is to optimally recover the mean of $D$ generating the good data points. Here, optimality is measured in terms of the relevant parameters of interest $n, d, \delta, \epsilon$. With no further assumptions, computationally efficient algorithms have been designed achieving the information theoretically optimal rate of:
\begin{equation*}
    O \left(\sqrt{\frac{d}{n}} + \sqrt{\frac{\log (1 / \delta)}{n}} + \sqrt{\epsilon}\right).
\end{equation*}
Note that this rate is optimal upto constants -- in fact, a family of Gaussians witness the terms depending on $d$ and $\delta$ despite making no assumptions on the higher-order moments of $D$. 

The paper considers the sparse setting where the mean, $\mu$, of $D$ is $k$-sparse. In typical sparse estimation problems, this usually allows an improvement of the sample complexity to depending polynomially only on $k$ and poly-logarithmically on $d$. In this paper, the authors construct an algorithm for sparse heavy-tailed mean-estimation achieving optimal recovery when $n \gg (k^2 \log (d) + \log (1 / \tau)) / \epsilon$ which is optimal under the conjectured statistical computational gap (information theoretic recovery is possible with $(k \log (d) + \log (1 / \delta)) / \epsilon$ samples). The paper imposes a mild assumption on the higher order moments and assumes additionally that $\mathbb{E} [(X_i - \mu_i)^4] = O(1)$.

Technically, the paper uses a well-established stability based framework for robust estimation with some minor modifications. Specifically, the data points are truncated in the $\ell_\infty$ norm (using a coarse estimate of the true mean using the coordinate-wise median-of-means estimate) to remove spikes along sparse directions and utilizing a standard median-of-means pre-processing technique. Having established these stability conditions, the algorithm follows largely from the prior work. 

In the dense setting, the goal is to establish a set of well-spread weights $w$ such the empirical covariance of the data points weighted by $w$, $\Sigma_w$, is small in spectral norm. Intuitively, $w$ would ideally be the uniform distribution over the good data points. Formally, one requires:

$$
    \min_w \lVert \Sigma_w \rVert = \min_w \max_{M \succcurlyeq 0, \mathrm{Tr} M = 1} \langle \Sigma_w, M \rangle = \max_{M \succcurlyeq 0, \mathrm{Tr} M = 1}  \min_{w} \langle \Sigma_w, M \rangle = O(1)
$$

where the inversion of the min and max is guaranteed by von-Neumann's min-max inequality. The last step is crucial since it suffices to design a set of weights depending on the ``direction'' $M$. Through a clever rounding argument from [DL 22], it suffices to only consider the case where $M$ is rank $1$ up to appropriate adjustments in constants. Therefore, one only requires $d$ data points to effectively cover the set of plausible directions as opposed to the $d^2$ sized cover of $M$.

In the sparse setting, it suffices to only search for sparse directions leading to the following modification of the above equation:

$$
    \min_{w} \lVert \Sigma_w \rVert = \min_{w} \max_{M \succcurlyeq 0, \mathrm{Tr} M = 1, \lVert M \rVert_1 \leq k} \langle \Sigma_w, M \rangle = \max_{M \succcurlyeq 0, \mathrm{Tr} M = 1, \lVert M \rVert_1 \leq k}  \min_{w} \langle \Sigma_w, M \rangle = O(1)
$$

To prove the stability condition, the authors proceed through a similar rounding argument as [DL 22] with the additional difficulty that it is not clear how to round such a $M$ to a sparse vector/matrix. In the dense case, it suffices to draw a zero-mean Gaussian with covariance $M$. Inspired by [Li 18] (where a decomposition of such a matrix into a sum of sparse matrices is carried out in Lemma 3.4.4), the authors design a careful probabilistic decomposition of $M$ to carry out this approach.

[DL 22] J. Depersin and G. Lecué. Robust sub-Gaussian estimation of a mean vector in nearly linear time.

[Li 18] J. Li. Principled Approaches to Robust Machine Learning and Beyond.

**** POST REBUTTAL UPDATE ****

I acknowledge the authors' response and will retain my current evaluation.
strengths_and_weaknesses: This paper makes significant progress the problem of building robust estimators for sparse mean estimation under heavy tailed and adversarial noise. Prior results only held for dense setting or under extremely strong distributional assumptions such as sub-gaussianity. However, one downside to the paper is the lack of technical novelty the design and analysis of the estimator. The algorithm follows naturally from well-established frameworks and its subsequent analysis is based on a rounding approach from prior work. However, the decomposition of sparse matrices for the rounding step to go through is novel and interesting.
questions: My main question to the authors is the requirement of higher-order moments. In the example provided in the paper, they construct a distribution centered at $0$ with identity covariance that when $\ell_\infty$ truncated at $\sqrt{k}$, whose covarince increases in spectral norm to $O(d / k)$. However, this is along an extremely dense direction oriented along the all 1s vector. It still remains the case that if one were only looking along sparse directions, the variance would remain small. In this case, it is not obvious to me that higher order moments are required. It would be immensely helpful if the authors could comment further on the necessity of these assumptions.

limitations: Yes
review_title: null

Meta-review: metareview: The paper studies the problem of sparse mean estimation in presence of heavy tailed noise. The result of the paper are novel and  interesting. Improvement over work of Prasad et al is significant as the paper is able to provide a computationally efficient method for the problem. Claims about Huber contamination model should be toned down, as it is not clear if the result is optimal. 

The paper generated a fair bit of discussion, and as mentioned above there are concerns about some of the claims of the paper, and they should be toned down or should explicitly highlight issues like dependence on epsilon. 
Nonetheless, reviewers agree that the paper represents significant improvement in SOTA owing to computationally efficient method. 
confidence: Certain
Decision: Accept