Venue: NeurIPS 2022 Conference

Reviews:

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: The paper addresses the problem of PAC learning a single neuron under the Massart noise model. For various activation functions, including ReLUs, the authors show that no efficient Statistical Query (SQ) algorithm can approximate the optimal error within any constant factor. The key technical innovation is a new SQ-hardness construction for learning neurons with a sign activation on the Boolean hypercube.

strengths_and_weaknesses: The paper is well-written and the results coherently presented. The paper can benefit from a separate conclusion / potential open problems section.

questions: Can the case $\eta=1/2$ in the noise model be addressed within this framework?
limitations: I do not foresee any potential negative societal impact of this work.
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: This work deals with the problem of PAC learning a single neuron with Massart noise. For this task for various activation functions, the authors provide super-polynomial SQ lower bounds. In particular, it is proved that no efficient SQ algorithm can approximate the optimal error within any constant factor.
strengths_and_weaknesses: The main question of the paper is whether there exists an efficient constant approximate learning algorithm for distribution-independent learning of a single neuron with Massart noise for various activation functions. The authors rule out the existence of efficient SQ algorithms with constant factor approximation for the above problem for the ReLU activation.

Next the authors introduce a second variant of the Massart noise model for real-valued functions and give another SQ lower bound for this model and a general family of activations (including ReLUs).

I believe that the most interesting result is Theorem 1.6 which gives an SQ hardness result for low-weight Massart halfspaces on the Boolean hypercube. The fact that this problem remains SQ-hard is quite nice and justifies the difficulties when dealing with the Massart noise model.

In general, the paper is clear and the results are well presented.


questions: Theorem 1.2 captures the ReLU activation function and other functions with a "threshold" behavior. Is there some intuition on why the result holds only for these activations? Do we expect similar hardness results for other activations? 
limitations: This is a theoretical work. The authors describe the limitations of this work.
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 studies the question of distribution-free, improper learning of single neurons when a random fraction of the labels in the training data have been corrupted. The objective is to output a predictor whose squared loss over the clean data is as close to that achieved by the optimal neuron. They show that no statistical query algorithm with polynomial query complexity or inverse polynomial tolerance can always achieve a constant factor approximation to the optimal squared loss in the worst case. They additionally show hardness in a different setting that they call "L_2-Massart noise" in which the labels are given by perturbing the true label by heterogeneous noise of bounded variance.

They also show a new SQ lower bound for distribution-free learning of halfspaces in the presence of Massart noise. Unlike the previous lower bounds of Chen et al. '20 and Diakonikolas and Kane '20, their bound applies to halfspaces over the hypercube whose coefficients are from {1, -1}. 

The hard instance they construct to prove these lower bounds closely follows the approach of Diakonikolas and Kane '20, with the main technical twist that they need to handle discrete rather than Gaussian inputs. They design a joint distribution over $(x,y)$ such that 1) conditioned on $y = -1$ or on $y = 1$, the distribution over $x$ is iid random bits outside of a hidden subset of $m$ coordinates over which it is symmetric and such that the 1D distribution of the sum of these $m$ coordinates approximately moment-matches $\text{Bin}(m,1/2)$, 2) these 1D distributions for $y = 1$ and $y = -1$ don't overlap by much, and 3) the joint distribution can be realized as an instance of whatever learning problem their lower bound applies to.
strengths_and_weaknesses: The topic of this paper feels a bit like smashing a bunch of well-studied topics together. Arguably the main reason to be interested in extending existing lower bounds for learning halfspaces under Massart noise to learning ReLUs would be that real-valued regression problems tend to require new techniques for showing hardness. But the architecture of the proof in this work builds heavily on Diakonikolas and Kane '20, and the hard joint distribution exhibited ultimately has binary labels as before (they've gone from the PTFs of Diakonikolas and Kane '20 to certain ReLUs of polynomials which take on binary values over the hypercube). The main technical difference is that it's important that the x's are over the hypercube instead of $\mathbb{R}^d$, so one needs some discrete analogue of the usual non-Gaussian component analysis setup. But this discrete analogue is precisely the one developed in Diakonikolas, Kane, and Sun '22. That being said, the actual moment-matching construction is new and requires a number of clever moves, in particular Lemma 3.8, that are specific to the setting at hand.
questions: *Questions*:
- A priori isn't it possible that ReLU regression under Massart noise isn't constant-factor-approximable even when the covariates are *uniform* over the hypercube?
- Can one hope for a common generalization of this work together with Diakonikolas and Kane '20 to show hardness for a more general family of activations than just {sign} + {"relu-like" functions that are injective over the positive part}? Perhaps any activation that is far from the identity function?

*Minor comments*:
- Technical overview is quite hard to read for a general audience as it assumes close familiarity with [DK20]. Also it uses notation that is not defined previously in the paper (see below)
- P. 2 Line 58-60: While this is true for binary classification, this point doesn't seem very relevant for the real-valued regression problems studied in this submission.
- P. 4 Line 147: The relevant document doesn't appear to be available, though the associated talk slides which are available online don't seem to mention this as an open problem
- P. 4 Line 168: s not defined
- P. 4 Line 171: n not defined
- P. 4 Line 152: LTF and PTF should be defined
- P. 9: would be helpful to include a sentence on why it's more convenient to work with $\widehat{\text{ReLU}}$ rather than $\text{ReLU}$
- Lemma 3.7: confusing as Condition 3.3 is phrased in terms of distributions, whereas Lemma 3.7 is about an unnormalized measure, and this is exacerbated by the expectation notation used in the proof. also, isn't $\mathcal{R}$ also unnormalized? if so, the use of the word "pmf" is similarly confusing.
- Some of the technical writing is rather hard to read, e.g. the block of text in Section 3.3, though this might be due to space constraints.
- It seems more accurate to call Definition 1.1 Huber contamination rather than Massart noise.
limitations: The authors give a pretty comprehensive answer to the question they set out to solve, so I don't see any limitations per se. I also don't see any potential negative societal impact, as they are proving a hardness result for a theoretical problem.
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: The authors consider the problem of (distribution-free) PAC learning of single neuron neural nets in the presence of Massart noise, with the aim off finding a constant factor approximation error. They prove a super polynomial lower bound in the statistical query model (a restricted family of algorithms). This is proved for ReLU and also a broader class of activation function: those that output zero for negative parts and any injective function for the positive part. They establish a hardness gap that is super-constant and scales with the dimensionality of the problem. This lower bound shows a barrier to improve the existing upper bounds (i.e., one cannot hope to use algorithms based on statistical queries to get an efficient method with constant approximation guarantee) 

Technical overview:
•	The proof starts by finding a SQ hard instance for the Boolean case based on recent results for continuous case.
•	The recent result is for continuous case and finds instances for one-dimensional Gaussian like distributions and extend it to high dimensions.
•	They need the case for discrete and it is not easy to extend that Gaussian like results to this case
•	They start by constructing the binomial distribution conditioned on X being 0 mod s and then change the distributions so that (1) conditioned on X being far from n/2 the probability of Y=1 is larger than Y=-1 (2) conditioned on Y=1 and Y=-1, the distributions have less overlap and (3) the conditional distributions have moments close to binomial.
•	Use recent result to extend this to high dimensions.
•	Construct an instance of ReLU that produces the desired classifier for the Boolean case

strengths_and_weaknesses: Strengths:

+ The authors offer a SQ lower bound for learning neural nets with 1 neurons under Massart noise. This is a solid technical contribution and an important step towards understanding the barriers for improving regression algorithms under noise conditions.

Weaknesses:

+ The generalization of the Massart noise model to the real-valued case (Definition 1) seems somewhat unnatural. In the real valued extension the y-values are kept "exactly the same" with some probability and changed otherwise. Yes, this coincides with Massart noise for binary case, but in the continuous case is rather odd. Some more motivations can help.

+ The paper does not provide enough background and motivations, has missing/vague notations, missing explanations that can glue different technical results, and sometimes not rigorous in the statements of the results. Overall, the paper is hard to read or assess, and in my opinion is not ready for publication. The presentation can be greatly improved. Some concrete points:

+ Many notations are unclear, vague, or even undefined. Here are some examples:
+  Definition 3.2. The notation (X_i )_(i∈S) is confusing and has not been properly defined or explained. Also, what is a symmetric distribution in this case? Parsing this definition with these notations 
+  Definition 3.4. What does sampling from (P_S^A,a) mean? Does it mean that we sample a point x from P_S^A   and return (x,a)? The notation is quite confusing.
+ Proposition 3.5. although rather standard, it would help to define the X^2 distribution and its notation.
+ When you use a measure as a function, do you assume it has some kind of (unnormalized) density?
+ Related to the previous point, the notations D_+ and D_- are not consistently used. Sometimes they refer to the function as used D_+=0 on J and sometimes they are used with reference to the input as D_+ (x). Also, it would help to define the ell_1 norm of D in this context.
+ would help to explicitly define (±1)-weight half-space

+ The introduction of the paper does not motivate the setting. Adding some more motivations such as explaining why a statistical query lower bound is important can help the non-expert reader. The structure of the literature review and the background does not help the non-expert reader either.
+ Some lemmas and propositions appear in the main paper without enough context or explanations about where they are going to be used. 
+ The technical proofs are quite hard to follow. The different parts of the proofs are not introduced with intuitive introductions and explanations. It is difficult for the reader to obtain a general understanding of the problem without diving into the technical proofs of theorems, which are also hard to understand considering the missing notations and definitions.

questions: N/A
limitations: N/A
review_title: null

Meta-review: metareview: The paper shows an SQ lower bound for learning a single neuron with a known activation function (functions that includes the rectifier) under Massart noise. The paper makes a sufficiently novel contribution; however, I also agree with the various presentation issues made by the two more critical reviews. The authors must address all of these adequately for the revision
confidence: Less certain
Decision: Accept