Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: summary: The authors study exact parameter recovery in ReLU regression under a generalization of the semi-random Massart noise model. Assuming certain distributional anti-concentration, the authors propose and analyze an algorithm that runs in polynomial time and recovers the exact parameters with high probability, given a sample of size polynomial in the input dimension and the (inverse of) the Massart parameter. Along the way, they also provide similar guarantees for the simpler case of linear regression.
main_review: The paper is a joy to read. The study is important and relevant to the NeurIPS community. To the best of my knowledge, the results are novel and significant. I checked the proofs only at a high level, but the claims seem sound to me.

A couple of comments/questions:
1. The algorithm design as well as the proofs -- both in linear/ReLU regression -- leverage insights and techniques from the work of Hopkins et al. 2020. While this paper is cited in the appendix, there is no reference to it in the main text. I urge the authors to discuss this reference in the main text.
2. Given suitable anti-concentration assumptions, what are the main challenges in extending the results from linear regression to ReLU regression? The guarantees in Theorems 1.2 and 1.3 are very similar, and under the anti-concentration assumption for ReLU regression, proof of 1.3 seems like a straightforward extension of 1.2.

limitations_and_societal_impact: Yes
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The aim of this work is to propose a computationally efficient algorithm for linear and ReLU regression in the presence of a bounded adversarial Massart noise model. It has been tried to make the assumptions on the underlying data distribution as mild as possible, not to mention that (as claimed by the author(s)) some assumptions are necessary from an information-theoretic point of view.

The core idea is to consider the unknown corrupted samples as outliers which do not follow the simple linear or ReLU rules between their features and corresponding labels. This should be added to the fact that (based on the paper's assumption) the fraction of corrupted samples is less than 1/2, so the clean data points have the majority. This way, author(s) have proposed a linear transformation on the samples in order the make them "Radially Isotropic", so (with high probability) the ratio of outliers to clean samples remain as low as possible in *every direction* of the space. Then, some existing robust estimators such as sum of $\ell_0$ or $\ell_1$ models have been shown to remove the effect of outliers and acquire the true parameters. I haven't completely checked the proofs, however, the overall idea makes sense to me and is, in fact, quite interesting. In any case, I am not completely familiar with this line of research so I wait to see other reviews in order to assess the novelty of techniques that have been utilized in this work.

With respect to weaknesses, paper lacks proper discussion at some points which I have explained in the "Main review" section. Also, author(s) have assumed a completely clean and noise-free model except for the adversarial part which still includes more than half of the samples. This assumption is a little worrisome in practice, where some minimum levels of, for example, additive noise are *always* present. How robust or sensitive is the proposed method and its theoretical guarantees when the presumed ideal noise-free environment is minimally perturbed?

Overall a well-motivated and fairly well-written paper with some interesting theoretical achievements (as far as I am aware). My vote at this stage is weak-accept.

main_review: 
My main concerns are as follows:

Author(s) seem to have a good grasp of existing literature in this area, but it hasn't been completely reflected in the Introduction section. Some discussions and comparisons are still vague and need clarification. I believe the classification of prior advancements in terms of: achieved guarantees, distributional assumptions and etc. can be improved by some reorganization, which also helps the reader to position the current work w.r.t. others, more effectively.

The adversary described in Definition 1.1 does not match with the one that has been explained in Lines (117:119). In Def 1.1, adversary is allowed to alter (at will) each point $\left(x_i,f\left(x_i\right)\right)$, with probability $\eta\left(x_i\right)\leq\eta$. No information regarding $\eta\left(\cdot\right)$ has been given except that it is bounded by the constant $\eta$. That means the function $\eta\left(\cdot\right)$ can also be chosen by an adversary. That is different from the explanation given in Lines (117:119): "we consider a more restricted adversary that is presented with a uniformly random $\eta$ fraction of the points, which can be corrupted arbitrarily at will". So a natural question would be which of them is finally considered in this work?

Also, more discussion w.r.t. the adversarial perturbation model considered in this work would be helpful. It is not as strong as the "contamination model", but obviously hurt more than a purely random noise. What is the intuition behind this particular noise model?

In Section 1.2, the transition from ReLU and linear regression in the presence of Massart noise to $\ell_0$ or $\ell_1$-regression is not smooth. More explanations are needed here, otherwise the core idea behind the results become somehow ambiguous and hard to understand.


------------------------------------------------
Minor comments:

-(Line 107): What author(s) mean by "It remains an interesting open problem whether similar PAC learning guarantees can be obtained for the case of ReLU regression."? Aren't the results from Theorem 1.3 associated with the most general case? Or author(s) are referring to a more general adversarial noise model rather than Massart noise here? 

-(Line 144): I guess it should be $w=A^Tw'$, right? It might not be important since $A$ is later assumed to be symmetric. However, it may confuse the readers.

-(Definition 1.4): What is $\mathcal{S}^{d-1}$? Is it the surface of $d$-dimensional unit sphere?
limitations_and_societal_impact: No problem here.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: The paper considers the problem of linear and ReLu regression in the Massart noise model, where an adversary is allowed to change the label to an arbitrarily value with some probability at most $\eta <1/2$. The work develops an efficient algorithm that achieves exact parameter recovery in this model under mild assumptions on the underlying distribution. 
main_review: **Quality and Clarity**: 

-  One of the strong points if the paper is that it is very well-written and well organized. The ideas are presented clearly with intuitive explanations, and the proofs are rigorous. 

- The authors are careful in evaluating the strengths/weaknesses of their work. The work seems to be built upon an established literature and the review of related works are informative. 

- Minor comments: 
  - Definition 1.1: "and after inspecting which samples can be corrupted, it may change the label to an arbitrary value" --> I interpreted this as "change each label to an arbitrary value" or "change the labels to arbitrary values". Please clarify.
  - bit complexity of the parameters and samples: this is mentioned a few time but are not defined
  - the sentence starting at Line 140 is very difficult to read

**Originality**: 

-  The paper consider a slightly weakened model (in comparison to the the contamination model), but leads to more generality in the underlying data distribution.

- The result of the work is significantly different (stronger) from the closest comparisons ([32] and [10]), and the methods are designed specifically to address the limitation of those works.

- The generalization of the approach from linear to ReLU regressions are non-trivial in both technical analysis and algorithmic designs. 


**Significance**:

- As stated in the Originality section, the result of the work is significantly different (stronger) from the closest comparisons ([32] and [10]) and seems to extend existing works in a demonstrable way.

- On the other hand, I'm unfamiliar with some pieces of related work and don't have a strong conviction in how it will impact the field, and would leave the judgement up to other reviewers. 

limitations_and_societal_impact: n/a
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper studies regression problems in presence of Massart (bounded) noise, where for each sample x_i, the adversary is allowed to change its label/response f(x_i) to an arbitrary value with probability less or equal to eta. Specifically, the authors focus on two problems: linear regression and ReLU regression. For both cases, they make a ``mild yet necessary assumption on the data, that the distribution is not concentrated entirely on any linear subspace; and provide algorithms which exactly recover the true function in polynomial time with constant probability. 
main_review: I feel the paper is well-written but I have a few concerns on the theoretical guarantee.

- In Theorem 1.2, it turns out that the sample complexity for robust linear regression is suboptimal. In particular, even when the noise rate eta = 0, it is given by O(d^3) which is worse than that of noiseless regression. It also seems unpleasant to have bit complexity dependence in running time.

- In Theorem 1.3, I cannot follow the assumption that $P( w \cdot x \geq 0 ) \geq \lambda$ for all w.

- What is the computational cost to obtain a radial-isotropic transformation matrix A? This turns out to be a crucial algorithmic component but I did not find a concrete discussion. Note that since you require unit data norm and identity covariance simultaneously, finding such transformation is nontrivial.

- The distributional assumption is informally stated throughout. Can you provide a fews examples that satisify the condition, say Gaussian distributions or uniform distributions?

- I may miss some important messages, but if the data distribution were uniform, then would it be necessary to perform radial-isotropic transformation? My understanding is not being necessary, in which case the technical novelty appears vacuous. 
limitations_and_societal_impact: yes
review_title: null

Meta-review: This paper considers the problem of ReLU regression under the Massart noise model that has recently been studied extensively for classification problems. The main result of the paper is an algorithm that does exact parameter learning under certain distributional assumptions. 

All the reviewers appreciated the results of the paper. While it builds on prior techniques in the area, the technical novelty in the work is high enough. Certain technical questions raised by the reviewers were subsequently resolved by the authors' response. Overall this is a solid theory paper and I recommend acceptance.
Decision: Accept (Poster)