Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This work studies the convergence of gradient descent in the regime of learning ReLU activations agnostically for a class of distributions that contains the standard high dimensional normal distribution. In contrast with previous results, they consider the case where bias exists and apply gradient descent on the weight vector+bias. Their approach essentially connects the analysis of [1] and [2].

[1]: Spencer Frei, Yuan Cao, and Quanquan Gu. Agnostic learning of a single neuron with gradient descent.
[2]: Gal Vardi, Gilad Yehudai, and Ohad Shamir. Learning a single neuron with bias using gradient descent
strength_and_weaknesses: Pros:
1. This is an important problem. Previous results have focused on the unbiased case, so this is somehow the first result for biased ReLU activations.
2. The gradient descent happens in bias and the weight vector, which means that the naive idea of extending the dimension works

Cons:
1.  The authors state in the abstract that this is the first algorithm based on gradient descent that achieves these guarantees when the bias is zero. But [3,4] apply gradient descent and achieve $O(OPT)$. The first work does gradient descent on a surrogate loss which differs from this work, where the gradient descent is applied to the standard objective. Meanwhile, the second work uses gradient descent on the same objective and achieves $O(OPT)$. So, I believe this sentence should be removed from the abstract. 
2.  This work considers the case where the ratio between $||w||_2$ and $b_w$ is bounded by a constant. The title and the abstract leave the impression that this work provides a theorem for any value of bias which is not the case. One of the main difficulties of learning ReLU activations is to sample enough points so that $\sigma'(w^Tx+b)>0$  and $\sigma(u^Tx+b')>>0$ ($u,b'$ are the best parameters for this instance) for a large portion of the points (see [5] theorem 4.2 for the intuition); with these assumptions, this is somehow easily satisfied (for standard Gaussian) with a good initialization (Section 5) because the mean and variance of the RV $u^Tx+b'$ is bounded by constants. 




[3]: Ilias Diakonikolas, Surbhi Goel, Sushrut Karmalkar, Adam R. Klivans, Mahdi Soltanolkotabi. Approximation Schemes for ReLU Regression
[4]: Ilias Diakonikolas, Vasilis Kontonis, Christos Tzamos, and Nikos Zarifis. Learning a single neuron with adversarial label noise via gradient descent
[5]: Gilad Yehudai, and Ohad Shamir. Learning a Single Neuron with Gradient Methods

clarity,_quality,_novelty_and_reproducibility: The work is sound and well-written.

p.9 has a broken reference.
summary_of_the_review: I think the contributions of this work are not sufficient for acceptance in ICRL.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper provides a convergence analysis of gradient descent for learning a single ReLU function under Gaussian feature distributions. The paper focuses on the mean squared loss between the single ReLU function the label, but allows updating both the weight vector and the bias parameter of the ReLU function.

The main contribution is proving that the gradient descent algorithm starting from a random initialization converges to within a constant factor of the global minimum of the loss within polynomial (in input dimension) number of iterations.

Besides the case of Gaussian feature distributions, the analysis can also be generalized to the O(1)-regular marginals.
strength_and_weaknesses: Strength:
- The result of this paper improves upon a previous result for learning a single ReLU function by additionally incorporating the bias in the analysis. Further, the analysis shows that the convergent iterate is within a constant factor of the optimum, whereas prior result requires an additional factor of d (i.e., input dimension).

Weakness:
- The feature distribution is assumed to be drawn from a Gaussian distribution. While this can be relaxed to the case of (1)-regular marginals, generalizing further seems challenging (e.g., does the condition hold for mixture of Gaussians or anisotropic Gaussians?)
- There are related works that consider the realizable setting of learning ReLU networks, which should perhaps also be discussed in the related work, e.g., here’s one:

“Learning Distributions Generated by One-Layer ReLU Networks.” Shanshan Wu, Alexandros G. Dimakis, Sujay Sanghavi. 2019.
clarity,_quality,_novelty_and_reproducibility: The paper is well-written and easy to follow for the reviewer. Though there’re minor aspects that could be fixed, e.g., equation (14) and (16) are both over length.

The technical novelty could be better highlighted in the analysis. For example, how the analysis incorporate the bias and improve the approximation factor of the optimum value could be better emphasized during the proofs.
summary_of_the_review: Overall I think this is a solid paper that contributes to the learning of nonlinear ReLU functions. It expands prior result and clearly states the limitations too (i.e., limited to one node) for future work. As noted above there is some concerns related to missing several related works in the literature.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The paper studies the problem of agnostically learning a ReLU function via gradient descent using samples drawn from Gaussian (or even a more general class of) distributions.  The main result states that under a suitable random initialization, if gradient descent is run for sufficiently many iterations on the population risk loss function, then it outputs a ReLU function the error for which is within a constant factor of the optimal error, i.e., the minimum value of the population risk (referred to as: OPT). This result does not necessarily need the bias of the ReLU to be zero and improves existing guarantees for gradient descent (Frei et al. 2020).
strength_and_weaknesses: Pros: The paper has the following strengths.

1. The exposition is in general clear and easy to follow. The problem setup and related work are detailed nicely that makes it convenient for the reader.

2. The analysis is an improvement over that of (Frei et al. 2020) since this latter work assumes zero-bias ReLU's and achieves an error bound of $O(\sqrt{d \ OPT})$ when the samples are drawn from a Gaussian distribution.

Cons: 

1. I believe that the related work is incomplete for gradient descent learning of ReLU functions. The work of Soltanolkotabi [1] considers this problem in the realizable setting (with zero-bias) with the inputs drawn from a Gaussian and derives error bounds for recovering the unknown parameter. It is not clear to me how easy it is to extend this analysis to the noisy teacher setting. Since [1] is well cited, it would be good to check other related works that cite [1] in order to be more complete in the literature review. 

2. I find it is a bit restrictive to analyze gradient descent on the population risk. While this is natural to do as a first step in the analysis and certainly non-trivial, I believe the main theoretical result should ultimately be the one for the finite sample setting and should ideally be presented in the main text. This analysis is currently relegated to Appendix D as Theorem D.1. I also have a question regarding Theorem D.1 later below.

[1] M. Soltanolkotabi, Learning relus via gradient descent, NeurIPS 2017.

Further comments:

1. In the statement of Theorem D.1, it is not clear to me how $|y| \leq B_Y$ can be assumed since the input $\tilde{x}$ is generated from a Gaussian. For instance, isn't this violated in the realizable setting where y is defined as a ReLU?

2. I was trying to understand whether in the special case of the "noisy teacher" setting (or "realizable" setting) the analysis says something about the convergence of the gradient descent iterates to the ground truth parameter. However from Section 4.1, it seems to me that this is not the case since it is only mentioned that the iterates lie within a ball of radius $O(\sqrt{OPT})$ around the ground truth parameter. But we know from [1] that iterates of projected gradient descent (on the empirical loss) converge linearly to the ground truth in the realizable setting.  Some more explanation in this regard would be helpful.

3. In Section 1.1 just above Theorem 1.1, $\tilde{v}$ is introduced but has not been defined till then. There is a small typo towards the bottom of page 3 in "Vardi et al."

clarity,_quality,_novelty_and_reproducibility: The paper is written quite clearly in general and is easy to follow. The quality of the result is good as it improves upon the existing work of (Frei et al. 2020). There seem to be new ideas used in the analysis for gradient descent along with a novel initialization scheme which are to my knowledge novel. 
summary_of_the_review: I think the contributions of the paper are decent and improve upon the analysis of (Frei et al. 2020) for learning ReLUs. The paper is also written cleanly and is easy to follow. As mentioned under "weaknesses" and in "further comments", I do have some comments regarding some closely related work and other technical aspects which need clarification.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This paper studies the behavior of a single ReLU neuron in the gradient descent training process. The main results include that first, a new class of distributions (called O(1)-regular marginals) is proposed to characterize the regularity of the input space distributions. This class includes multivariate Gaussian distributions, and does not require compact support. Second, under the proposed O(1)-regularity, and with constant step-size, Theorem 1.1 claims that in polynomial (of the input space dimension, and the error threshold) number of iterations, the expected loss converges to the optimal value subject to a small error threshold.

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

update after the discussion session: we find that most of our concerns have been resolved. We are therefore happy to recommend acceptance of this paper.
strength_and_weaknesses: Strength:
1. the introduction of O(1) regularity
2. the better convergence results

Weakness:
1. For Lemma 4.3, please specify the limit process for the big-O notation.
2. When we read Section 1.2, a natural question is whether the O(1) regular marginal conditions can be induced from a sufficient condition: the distribution Dx has a continuous and compactly supported density function, which takes a positive value at the origin? Whether, subject to scaling x|-> ax for a specific a>0 because of (iii), this density condition is also necessary? If not, would the O(1) regularity contain any meaningful application scenario that is excluded from the C0 density assumption?
3. For the simplification right before Section 4, would the analysis be different if the optimizer \tilde{v} appears at the boundary of H?
4. Please provide the Appendix as cited in the paper. For the time being, we are using the arXiv version of this paper to review the Appendix, and the comments are made accordingly.
5. Please specify the limit process for the notations \Omega(1) and O(1), below Equation (9). The same problem is in (1), and at the beginning of Section 4.1.
6. Since in the proof Lemma 4.2 is cited, please add the O(1) regularity assumption to Lemma 4.3
7. The constant c2 plays no role in Lemma 4.2. I guess this constant can be removed.
8. For the arXiv version (dated August 04, 2022, same as below). The last inequality of (11) of the arXiv version: the O(1) distribution is replaced by the Normal distribution. The same mistake is observed in Equation (20) of the arXiv version.
10. The O(1) regularity assumption just assumes beta_4 is positive, which could be very small. So, in the last two paragraphs, from beta<q^(1/4)/beta_4 one can not derive |b_u|>1/2.
11. The claim (page 10 of the arXiv version) "Observe that when (b) holds Lemma 4.4 implies the loss is O(OPT)" requires the specification of the definition of "O(OPT)", to be further checked. Also, why would this lead to Lemma 4.5?
12. Lemma 4.6 (the arXiv version) is different from the cited source. In Lemma d.4 in [VYS21], the underlying distribution is assumed compactly supported, and the bound c of the distribution support is changed to the square root of d (space dimension) in Lemma 4.6. In this paper, the O(1) regularity does not guarantee compact support. I guess that such a difference may not affect the conclusion, but then the new lemma should be proved separately.
13. The O(1) regularity should be assumed for Lemma 4.5, since in the proof Lemma 4.2 is employed. Also, the boundedness of w_t and v should either be proved or assumed.
14. Line -3 on page 11 of the arXiv version: according to Assumption (i) in O(1) regularity, the bound should be beta_2, not 2.
15. Line 9 on page 12 of the arXiv version: there should be a factor $\sqrt{beta_2}$ on the right-hand side.
16. Line -4 of page 12 of the arXiv version: if C_2 is larger than C_1 C_p^2, then C' is negative.
17. Line 3 of page 15 of the arXiv version: C_G is not elsewhere claimed to be greater than sqrt(2).
18. Line -5 of page 6 of the ICLR version: the existence of such w_t (in particular, w_0) should be assumed. In particular, if v=0, such existence is violated.
clarity,_quality,_novelty_and_reproducibility: The paper is written in a clear style that is not difficult to follow. I doubt the quality of the paper because of the problems found above. There is a novelty since this paper claims better convergence analysis. Since this paper studies the theoretical behavior of algorithms, reproducibility is not applied.
summary_of_the_review: There are some mathematical mistakes. Appendix is claimed but missing.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: This paper studies the problem of learning generalized linear models with a ReLU activation in the presence of adversarial label noise.
Their main result is that gradient descent on the natural $L_2^2$ objective efficiently converges to a solution with error within a constant factor from optimal, under Gaussian marginals (or slightly weaker distributional assumptions). What distinguishes this paper from prior work is that they can handle some non-centered ReLU activations, namely functions of the form $ReLU(w \cdot x+t)$, for some non-zero values of the threshold $t$. Most prior work had studied the case $t=0$. 

A disadvantage of this work is that the algorithm/analysis does not cover "general ReLU activations", as stated in the abstract. As pointed out by the reviewers, the paper considers the case where the ratio between the 2-norm of the weight vector and the threshold is bounded by a constant. This is a non-trivial restriction but the work still makes a contribution to this line of research.


justification_for_why_not_higher_score: The main disadvantage of the paper is that the main result relies on a strong assumption. In particular, the assumption that the ratio between the 2-norm of the weight vector and the threshold is bounded by a constant is critical to the analysis. It is not clear that the ideas here will contribute to extending the result beyond this assumption. 

justification_for_why_not_lower_score: The contribution is reasonable and extends an important line of work.
Decision: Accept: poster