Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: summary: The paper studies algorithms for sparse regression and principle component analysis using Huber loss in the presence of overwhelming oblivious noise.
In particular, the fraction of inliers, $\alpha$, is going to $0$ but it is still possible to achieve consistency as the noise model is benign (oblivious, symmetric noise).
The paper obtains optimal error rates and dependence on $\alpha$ for a wide range of distribution assumptions.
These rates are achieved by using regularized Huber loss (nuclear norm for the matrix case and $\ell_1$-norm for regression case).


main_review: I think the paper makes significant contributions for sparse (and rank-constrained) models in the presence of overwhelming noise. The proof strategy follows the standard analysis of regularized high-dimensional models [Wai19], in combination with a recent line of work on Huber regression for optimal error in robust regression ([SFZ19, PJL20, SF20, dNS21]). The paper is also well-written and usually clear. 

I thus recommend "accept". Some comments and suggestions are attached below:

**Main Comment**


+ Citations to several existing works on robust linear linear regression that use Huber loss are missing: [SFZ19, PJL20, SF20]. (Surprisingly [SFZ19] is listed in references but not mentioned in the paper. [SFZ19] is not even cited in the full paper attached as the supplementary material.)  These papers also follow the same proof strategy. In particular, regarding Line 201: The (non-sparse version of) well-spreadness condition looks very similar to the weak stability of [PJL20] (also see [PJL20, Theorem 3.1] ). Although the aforementioned works are looking at a different corruption model, there seems to be a strong relation in techniques, and thus should be discussed.

**Other Comments**

+ Please make it explicit early on that the regression setting only allows corruption in responses (and not the covariates). Assuming clean covariates simplifies the problem considerably.

+ Lines 48-55: It says that the error will be mentioned in $\|\cdot\|$ but the following text in Section $1$ mentions rates for error in $\|\cdot\|^2$.

+ Footnote 3: The second sentence should make it explicit that the reduction is for Gaussian design. I found it confusing at first.

+ Line 123: Define maximum norm. It is less standard than the others.

+ Lines 204-209: it is not clear from these lines that the condition on $\alpha$ is optimal. Please add more details for clarity.

+ When referencing to books, please mention the specific result being used (or a chapter for a broad topic).

**References**

+ [SF20] Sasai, T. & Fujisawa, H. Robust estimation with Lasso when outputs are adversarially contaminated. arXiv:2004.05990 (2020).
+ [PJL20] Pensia, A., Jog, V. & Loh, P. Robust regression with covariate filtering: Heavy tails and adversarial contamination. arXiv:2009.12976 (2020).
+ [SFZ19] Sun, Q., Zhou, W. & Fan, J. Adaptive Huber Regression. arXiv:1706.06991 (2019).

---
After the Author Feedback

I thank the authors for their thoughtful response. I am maintaining my score and thus recommend acceptance of the paper.
limitations_and_societal_impact: Yes
review_title: null

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: summary: The authors study PCA and sparse regression in the presence of an oblivious adversary. The observation model is as follows: the observations may have symmetric, independent, additive noise. Each noise term is bounded by $\zeta$ with probability at least $\alpha$ which can be much smaller than 1. The authors show that the estimators which minimize Huber loss with appropriate $\ell_1$ penalty achieve optimal error rates.


main_review: The authors explain the implications of their results in detail. They give intuition to setup sketch their proofs. Assumptions about the design matrix and the noise are weaker than those in related prior work.

Line 205: \alpha should be \alpha^2
Line 208: use appropriate placeholder constants in front of = and <= 

limitations_and_societal_impact: No concerns.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper studies sparse regression and principal component analysis under 
oblivious perturbations. 

Main contributions:
1. The authors propose estimators that achieve the optimal error guarantees for PCA and sparse regression under oblivious perturbations separately, by minimizing the Huber loss function with some regularization. For sparse regression the estimator also achieves the optimal sample complexity. 
2. This machinery has the potential to be applied to other estimation problems.

Post rebuttal: I acknowledge that I have read the authors responses and other reviewers' comments.
main_review: This paper is reasonably well-written, with clear introduction of the problem and comparison with the related work. The result of the paper improves over the state-of-the-art. Some comments on improving the paper:

1. Current version of the paper is very theoretical, it will be better if some experimental results could be added. 
2. The well-spreadness property at line 181 could is not clear: in the current statement it sounds to me like this property is satisfied as long as it holds for any arbitrary choice of $m$. But according to my understanding you do need the $m$ here to have some lower bound (otherwise setting $m = 0$ is trivial). What is the desired size of $m$? 
3. Typos in the paper: (1) At line 57, "preturbations" should be "perturbations".
limitations_and_societal_impact: N/A
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: The authors have proved non-trivial estimation error bounds for one type of robust estimate for sparse linear regression and PCA. Specifically, the estimate is constructed by minimizing the Huber Loss function with L1 regularization.  
main_review: I think overall the paper is well written. For each problem analyzed in this paper, there are sufficient comparisons with the prior work in terms of the sharpness of the error bound and shows when the error bounds derived in this paper are tighter. The discussion of the techniques looks clear. My major concerns of the paper are:
1) While the authors have claimed that their techniques provide a general framework that proves tight error bound for Huber loss-based robust estimate. However, besides the proof details specific to the two problems studied in the paper, I do not find anything new in the approach. To claim a general framework, I am expecting a statement that as long as the problem satisfies certain general properties, then there is a tight error bound for a type of robust estimate.
2) Related to the above point, it is unclear to me why the authors only looked at the Huber loss function. It would be nice and more general to say that as long as the loss function satisfies some assumptions, the error bounds hold. Then point out that Huber loss is one example and hopefully the authors can show a second example of the robust loss function.   

Overall, despite the concerns, I think it is a good paper to be accepted.    
limitations_and_societal_impact: It is a theoretical paper and the main limitation is that the paper mainly looks at two specific problems.
review_title: null

Meta-review: This paper studies the fundamental problems of Principal Component Analysis (PCA) and Sparse Linear Regression (SLR) in the presence of oblivious outliers. In the oblivious noise model, a fraction of the labels can be adversarially corrupted and the corruptions are assumed to be independent of the covariates. This corruption model is significantly weaker than other models studied in the recent literature. In particular, recovery is information-theoretically possible even when the fraction of inliers is close to zero. Prior work had developed efficient algorithms for linear regression in the oblivious noise model. The current work extends these previous ideas to PCA and SLR, obtaining efficient algorithms with near-optimal statistical guarantees under a range of distributional assumptions. The reviewers agreed that the contributions are significant and the paper should appear in NeurIPS.
Decision: Accept (Poster)