Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: summary: This paper consider the robust regression problem with adversarial corruption, including linear regression, generalized linear models (GLMs) and Moreau envelopes of Lipschitz GLMs. Leveraging recent advances in robust mean estimation and proximal point methods, they provide improved algorithms in terms of optimization convergence rates and statistical error rates.
main_review: This paper consider the robust regression problem with adversarial corruption, including linear regression, generalized linear models (GLMs) and Moreau envelopes of Lipschitz GLMs. Leveraging recent advances in robust mean estimation and proximal point methods, they provide improved algorithms in terms of optimization convergence rates and statistical error rates.

Specifically, their contributions include:

1) Following the noisy gradient oracle framework in [PSBR20], they use tools from [DHL19] to show that such an oracle can be implemented in near-linear time. Furthermore, they show that the accelerated proximal point algorithm in [MS13] is robust to the noise in the above oracle. Combining these results allows them to develop accelerated algorithms whose convergence rates feature better dependence on the condition number without sacrificing the statistical error rates.

2) In the context of robust linear regression, they leverage the identifiability proof in [BP21] to develop a non-SOS algorithm that achieves better statistical error rates.

This paper is a solid contribution to the problem of robust estimation/regression, improving upon existing work in several aspects and in particular answering the question left open in [PSBR20] on whether robust gradient descent can be accelerated.

Other comments:

- In the statement of all theoretical results, the authors should clearly speak out the dependence on all relevant problem parameters including the condition number $\kappa$, the dimension $d$ and the error $\epsilon$.
- The authors may consider providing a summary (say as a table) of their quantitative results and those from prior work for ease of comparison. 
- Line 64: should be $\gamma: \mathbb{R}^2 \times \mathbb{R} \to \mathbb{R}$


===================

I acknowledge that I have read the rebuttal and other comments. I maintain my score.
limitations_and_societal_impact: This work is theoretical oriented.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: The paper develops fast algorithms for robust stochastic optimization in the presence of strong contamination model, where the objective function belongs to one of the following: linear regression, (regularized) generalized linear models, and (regularized) Moureau Envelope. The main contributions of the paper are as follows:
1. Building on the gradient descent framework of [PSBR20], the paper develops accelerated gradient descent method using a noisy gradient oracle. This allows them to get better dependence on the condition number in the all of the mentioned models (with similar statistical rate as existing works).
2. Inspired by the identifiability proof of [BP21], the paper gives a practical algorithm for linear regression that has better statistical rates than existing works (at the cost of additional sample complexity). This is the first work that achieves this rate without certifiable hypercontractivity. 



main_review: I believe the paper is a good contribution to the field of robust stochastic optimization, showing that proximal accelerated methods are amenable to noisy gradient oracles. Thus I recommend "accept" for the paper with the following changes.

**Main Comments**

1. As $\kappa$, the condition number, is an important parameter in this project, the dependence on $\kappa$ must be mentioned in the sample complexities in main theorems. (For example, value of $\alpha$ from Line 316 + Proposition 1 suggests that there is a quadratic dependence on $\kappa$ in Theorem 4).

2. Independence of noise: It must be mentioned in the main paper that the noise distribution is independent of the covariates  in Theorem 3 and 4 (Model 3 and Model 4 in the supplementary material). This is a critical modeling assumption.

3. The paper should clearly state the contributions of their work. In particular, while comparing with [CAT+20], the focus should be on the number of calls to robust mean estimation. Removing $O(\epsilon^{-6})$ in runtime from [CAT+20] is a blackbox benefit from [DHL19] or [DL19]. It is not obvious from reading the paper.

4. Paper claims multiple times that there are only two approaches for robust linear regression: (i) sum-of-squares based approaches and (ii) Gradient based approaches. The paper is missing the "covariate filtering" approach of [PJL20].

5. Theorem 3 and 4 have different upper bounds on $\epsilon$ in terms of $\kappa$. What is the main reason behind this?

**Other Comments**

1. Line 144: Dependence on $d$ is improved but is worse on $\epsilon$.

2. Line 36: What is "highly robust regression"?

3. Line 99: [Dep20] also provides a near linear time algorithm.

4. Line 64: Typo in defining the domain and range of $\gamma$.

5. Line 165: In [BDLS17], apart from Gaussianity, the identity covariance assumption is critical too.

6. Line 206: what is $c$ here? 

7. Footnote 7: What depends polylogarithmically on failure probability? Time complexity.

8. Line 363: The last expression should be $2\alpha/\epsilon^2$ instead of $\epsilon^2/2 \alpha$.

**References**

[Dep20] J. Depersin. A spectral algorithm for robust regression with subgaussian rates. CoRR abs/2007.06072. (2020)

[DL19] J. Depersin & G. Lecué. Robust subgaussian estimation of a mean vector in nearly linear time. CoRR abs/1906.03058, (2019)

[PJL20] A. Pensia, V. Jog, & P. Loh. Robust regression with covariate filtering: Heavy tails and adversarial contamination. CoRR abs/2009.12976, (2020)

===============UPDATE After Author Response====================

I thank the authors for their thoughtful response, and answering my questions. I maintain my score and recommend 'acceptance'. 
limitations_and_societal_impact: Yes
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper resolves an open question of the recent work [PSBR 20], which uses robust gradient descent for robust estimation tasks, to achieve faster accelerated convergence rate and better statistical accuracy. This is done via a clever modification to the accelerated proximal point framework of [MS13] with the gradient step replaced by noisy gradient. 
main_review: This paper extends the recent work [PSBR 20], which uses robust gradient descent for robust estimation tasks, to achieve faster accelerated convergence rate and better statistical accuracy. This is done via a clever modification to the accelerated proximal point framework of [MS13] with the gradient step replaced by noisy gradient. 

The authors proposed a clean formulation of robust gradient estimators as an oracle, and showed how to implement this oracle in near linear time which improves from prior works. Next, the author showed that the algorithm of [MS13], is "stable" to the noise in the gradient oracle and can achieve a smaller statistical error via a iterating halving argument. Finally, the author showed how the proposed methodology can be applied to robust linear regression with strong statistical guarantee and practical computational complexity, without resorting to the costly Sum-of-square estimators.

Overall, this paper is well-written and it solved an important open question elegantly. I recommend a clear accept.

The only minor drawback of this approach, is that it requires a larger number of samples comparing to the SoS-based estimators (and other slightly stronger assumptions) - there is a d^2 factor in the O(1/eps) term. I am curious about the necessity about this - is there some fundamental limit of the robust GD-based approach that strictly separates it from SoS?   
limitations_and_societal_impact: -
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The proposed new algorithms for robust regression problems with improved runtime and estimation guarantees. 
main_review: I think it is important to have fast algorithms that optimize a generalized linear model (GLM) given corrupted samples. The new algorithm in the paper has improved the running time and estimation error comparing to prior work. However,  I am not familiar with the related work and it is unclear to me how significant the contribution is. One suggestion is that the authors can present a table that summarizes the error estimation bound and running time of prior works and the work in this paper so that we have a better understanding of how much improvements have been made. In addition, as a paper aiming to improve running time, it would be great to have some experiments to show that the improvements do exist.
limitations_and_societal_impact: This is mainly a theoretical paper while I would prefer some simulations or experiments to show the improvements of the new algorithm do exist.
review_title: null

Meta-review: The reviewers all agree that this paper makes solid contributions to the robust estimation problem and improves upon existing work in several aspects. The authors should incorporate the reviewers' suggestions into the final version of the paper.
Decision: Accept (Poster)