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: This paper focuses on sparse mean and covariance estimation in corrupted datasets. In particular, the authors focus on the strong contamination model of Diakonikolas et al ‘16, where an adversary is allowed to arbitrarily corrupt an $\epsilon$-fraction of points after observing the sample. In this regime, the authors develop new nonconvex optimization programs for sparse mean and covariance estimation. The stationary points of these programs recover good estimates of the underlying mean under generic stability conditions on the uncorrupted data.
strengths_and_weaknesses: Strengths:
- The authors present novel optimization programs for the tasks of robust sparse mean estimation and robust sparse PCA.
- The algorithms are generic in that one can use any algorithm to find a first-order stationary point, such as gradient descent. 
- The stability conditions hold for more than just Gaussian inliers, although the only model of data that the authors' show satisfies this condition is sub-Gaussian.
- Overall, the paper is clear and well-written.

Weaknesses:
- The paper could do a better job of explaining the intuition behind the methods, which seems to be hidden in Lemmas 3.2 and 3.4. As it stands, the optimization programs seem to come out of nowhere.
- In practice, one typically would only find an approximate stationary point. As far as I can tell, there is no discussion of how this affects the approximation results of the algorithm.
- It is unclear how general the deterministic stability conditions are, and if they extend past sub-Gaussian data.
- For the practical gradient descent method, there is no iteration complexity bound given.
- The experiments are quite limited, and there only seems to be a marginal improvement over the RME_sp method. Furthermore, I am left wondering what the optimization landscape of the objective looks like, and what convergence properties it exhibits.

Update: through the clarification of the authors on the intuition behind the method as well as the novelty of the energy landscape, I have decided to raise my score.
questions: - Should the sparsity of $\hat{\mu}$ and u in Theorems 1.2 and 1.3 be mentioned in the Theorem statement?
- Given a dataset, is it possible to check if the stability condition (for either mean or covariance estimation) holds?
- Why is the result for Robust Sparse PCA worse for Gaussian data? Can this be rectified or is it a limitation of the analysis?

limitations: There appears to be no clear discussion of limitations, outside of the discussion in 104-111 which states the worse bound under Gaussian data.
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: 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 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 distribution $D$.
2. An adversary then inspects the generated samples and corrupts an arbitrary set of $\epsilon n$ points in a completely unconstrained manner.

Given a 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. With no further assumptions, computationally efficient algorithms have been designed achieving the information theoretically optimal rate.

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$. The paper relies on the existence of a stability condition introduced in prior work on building robust estimators in the sparse regime. However, unlike previous algorithms exploiting this condition which often utilize intricate filtering techniques or solve large convex programs, the algorithm proposed in the paper is a simple gradient descent on a natural non-convex objective. Furthermore, they show that any approximate stationary point of this non-convex objective is can be used to obtain a good estimate of the mean. 

In the dense setting, the stability stability condition required is the existence of a set of well-spread weights, $\left\\{w_i\right\\}_{i \in [n]}$ such that the empirical covariance of the data points weighted by $w$, $\Sigma_w$, is small in spectral norm. Furthermore, any set of weights guaranteeing this condition can be used to get a good estimate of the mean. Formally, one would like a $w$ such that $f(w) = \lVert \Sigma_w\rVert$ is small. While prior algorithms constructed a good set of weights through complex filtering techniques or by solving large convex programs, it was then subsequently shown that all approximate stationary points of $f$ also produce such a set [ZJS 20]. Thus, one can perform robust mean estimation by simply running gradient descent on the function $f$ without resorting to elaborate approaches from prior work.

The main contribution of the paper is the identification of a novel stability condition for the sparse regime where an analogously defined optimization function $f$ has similar nice properties; that is, its approximate stationary points yield a valid solution to our mean estimation problem. For sparse mean estimation, the specific function chosen by the paper is that $f(w) = \lVert \Sigma_w - I \rVert_{F, k, k}$ where $\lVert A \rVert_{F, k, k}$ denotes the maximum Frobenius norm of the matrix $A$ restricted to any $k^2$ entries with the constraint that these $k^2$ entries must be chosen from $k$ distinct rows with $k$ entries from each row. The paper also proposes a variant for Robust Sparse PCA. Finally, the paper shows that under nice distributional assumptions such as sub-Gaussianity, such a stability condition holds with high probability. 

**** POST REBUTTAL UPDATE ****

I acknowledge the authors' response and have decided to retain my current evaluation. While the new sparsity encouraging objective functions are interesting, the technical contributions seem somewhat limited in comparison to landscape results already known in the dense setting preventing me from strongly recommending this paper for acceptance. 
strengths_and_weaknesses: The paper introduces a natural objective for robust sparse estimation and show that it recovers previously known results in this domain. Furthermore, the analysis is simple and easy to follow. Having said this, one of the main drawbacks with the result is that it is not clear how such a stability condition would hold for distributions not satisfying strong tail bounds for which we already know good estimators. Ensuring such a condition is currently the main bottleneck in extending prior approaches for robust sparse estimation to other potentially heavy-tailed distributions. Secondly, the condition itself is not significantly insightful as it is well-known that exploiting sparsity essentially involves reducing the search space for violating behavior to a smaller set of sparse directions which has underlain all prior approaches for this problem. 

Despite this, the paper makes a nice contribution to the growing literature on robust sparse estimation. Furthermore, any subsequent work establishing such a stability condition for more general distributions will now immediately yield a simple gradient descent based algorithm achieving optimal performance.
questions: It would be great if the authors could have a discussion on when the stability conditions required by the are satisfied beyond the settings where efficient approaches to efficient sparse estimation are already known.
limitations: Yes
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 authors demonstrate that standard first-order methods lead to robust and efficient algorithms for sparse mean
estimation and sparse PCA. Their main contribution consists of non-convex formulations for  these robust estimation tasks in the presence of outliers in high-dimensional data.
strengths_and_weaknesses: Strengths:
1) The paper is well written and organized.
2) The non-convex formulations for  robust estimation are novel and well detailed making them reproducible.

Weaknesses:
The authors indicated applications of the proposed non-convex formulations for  robust sparse PCA and robust PCA. But they should also indicate applications in computer vision of robust sparse PCA and robust PCA.
questions: Can you provide a list of computer vision applications in which the proposed methods can be applied?
limitations: The authors have well addressed the limitations of their non-convex formulations.
review_title: null

Meta-review: metareview: This paper proposed a non-convex formulation for outlier robust sparse estimation which is an extension of existing work. The key point is to construct new objective functions to capture sparsity and at the same time satisfy the nice properties identified for nonconvex optimization formulations in the past for high dimensional parameter estimation in the non-sparse setting. The paper is well written and the math is solid. 
confidence: Less certain
Decision: Accept