Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The paper studies the convergence properties of the gradient descent (GD) algorithm for training two layers neural networks. The convergence is established wrt the population loss and under essentially no constraint on the underlying data distribution. Moreover, the simplicity of a given data distribution is determined by measuring the complexity of infinite-width random feature models which approximate the underlying distribution. It is shown then that less complex is the data the less samples, network nodes and iterations are needed.

main_review: One of the current great challenges in deep learning is to understand the ability of GD to converge to models which exhibit good generalization capabilities--despite the nonconvexity of the training loss. Thus, the strong convergence results established in this work are rather interesting. In addition, tying the convergence properties of GD to the structure of the underlying data distribution seems to be a step in the right direction of abandoning\refining the distribution-free paradigm presently governing the machine learning literature, and I find it very it encouraging. 

To me, the two main issues are: 1. large parts of the analysis seem rather incremental when compared to previous works. 2. The positioning of early-stopping, the main selling point of the paper, are not entirely clear: the negative result (possible failures of DL learning in the interpolation regime) addresses a nearly-negligible part of the regime to which the positive result (convergence rates of GD) applies. Thus, I believe that the analysis of early-stopping in the paper cannot be regarded as conclusive. 

Assorted comments:
* I feel that, due to their importance in the paper, the very notion of early-stopping and interpolation regime (the phenomenon of double descent, in particular) should be introduced and discussed more explicitly. 

* L41, the predictor function f is not explicitly introduced.

* Perhaps discuss the implications of the modeling choice of drawing the weights of the second layer at random more thoroughly. In particular, can you characterize a large deterministic set of 2nd-layer weights to which similar convergence results apply?

* Theorem 1.1, use of n instead of m (above L96).

* Theorem 1.1, is there a practical way of estimating the quantities involved in the upper and lower bound presented in the theorem for a number of interesting settings to see if they behave nicely? In the nearby realm of sample complexity, bounds are, by and large, vacuous when instantiated to practical settings. See, e.g., https://arxiv.org/abs/1703.11008 (and references therein).

* L151 "recent works whose width"

* L284 : 
-- What other models can be used to measure simplicity instead of the infinite-width random features model? 
-- What are the upsides and downsides of the current choice? 
-- Quantitively, how 'simple' are MNIST, CIFAR and other conventional datasets in ML when measured using the method proposed in the paper?  
limitations_and_societal_impact: Yes, the authors have adequately addressed the limitations and potential negative societal impact of their work.
review_title: null

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: summary: The paper studies 1-hidden layer ReLU networks trained with SGD and logistic loss on arbitrary classification tasks, showing optimality given that early-stopping is adopted. An interesting complexity measure for the underlying mapping is shown to play a key role in how the generalization error is affected by relevant factors such as number of iterations and network neurons. Insights on interpolation capacity of networks are given along with new and exciting questions.
main_review: The paper is very well-written, clear, and the discussion on both implications and limitations of the analysis is impeccable.

I see the main Theorem as a strong contribution, showing optimality of shallow ReLU networks w.r.t. the population loss under very mild assumptions. The need for early-stopping for the main result is thought-provoking, and the provided discussion on its relation to the interpolation regime and NTK (where both have gained a lot of attention recently) draw exciting connections and open new questions for future research.

The complexity measure presented here is also exciting, as it seems to interact in a very desirable way with the relevant model & training factors and is also seems intuitive and is strongly connected to the NTK. A key question is how much the behavior changes once actual learning is taking place, but I can see this analysis requiring considerable additional technical effort and it being appropriate to leave it completely to future work.

Although I haven't checked the proofs in detail, it seems that there is considerable technical contribution as well.

I believe this is a strong submission, with a solid contribution which is presented extremely well and raises interesting questions, therefore I recommend acceptance. However, I would like to note that I am not very familiar with the topic and might have missed possible limitations / concerns.
limitations_and_societal_impact: Yes.
review_title: null

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: summary: This work shows that a certain neural network learning procedure
(a single trainable layer, trained via gradient descent)
is consistent, meaning it asymptotically converges to the Bayes optimal classifier.
Although certain algorithms on neural networks were known to be consistent before, this result was not know for *gradient descent*
from random initialization.
This paper thus contributes to our fundamental understanding
of the power of gradient methods on neural networks.
main_review: ## Recommendation

I recommend acceptance.
The result is clean, the paper is very well-written,
and the conclusion is significant.

As a disclaimer, I did not get a chance to check all of the proofs.
However, the overall proof strategy appears sound.

## Strengths

- The writing is clear, and outlines the proof strategy.
- The result is, as far as I know, not known before.
(Although the tools involved are used in many related papers, as is acknowledged).
- The result is "good to know": gradient methods are often used in practice, and having such consistency results can be a first step towards justifying them.
- The theoretical requirement of early-stopping may be related to certain relevant practical phenomenon, and could shed light on differences between interpolating and non-interpolating classifiers.

## Weaknesses

- As with all consistency results, it is not clear how much this result says about why neural networks
are actually successful in practice.
(For example, k-nearest-neighbors are also asymptotically consistent...). The quantitative bounds on generalization may very well diverge exponentially fast, depending on the problem setting.
In general, "consistency" is a fairly weak property, but it is still good to establish.

- The results on "adaptivity to data simplicity" does not seem like a major contribution, since results of this form were already known in the past (as the paper indeed cites), for various notions of "simplicity." And it is not clear how this result contributes beyond what is already known in the area.

### Relevant Citations

The following empirical paper shows that, complementary to your results, interpolating networks are *not* consistent on noisy distributions:
https://arxiv.org/abs/2009.08092

This in particular addresses your stated open question of
"Do neural networks fail on noisy data if care is not taken with temperature and early stopping?"

Theorem 1 in the above paper may also be seen as a certain analogue of your Proposition 1.2, for the case of nearest-neighbor classifiers.
In general, the fact that 1-nearest-neighbors is not asymptotically consistent is related to your claims about local interpolation rules.


----
Edit after rebuttal: score increased from 7 to 8.
limitations_and_societal_impact: Suggestions on limitations are in the "weakness" section above.
Societal impacts N/A.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper gives a theoretical analysis of the neural networks under the logistic loss on binary classification task. It considers the setting of training a shallow two-layer neural network with ReLU activation, and proves a core theorem that gives a high probability bound on the difference between population risk and Bayes risk. The obtained results imply consistency, since all parameters can be made arbitrarily small. It also proves a proposition related to 1d datasets, where if the neural network interpolates the training data perfectly and is not too wild between training points, then it is guaranteed to perform badly on noisy test data.
main_review: Strength:

1. This paper gives a very strong theoretical result regarding the impact of early-stopping on training a shallow neural network. Specifically, it associates a multiplicative factor on the term R(\overline U_\infty), suppose this term is smaller than eps_gd then \tau_0 can be ignored and the KL divergence term is also smaller than eps_gd. This recovers a result for data separable setting [Ji and Telgarsky, ICLR’2020] but generalizes it into the non-separable setting.

2. The technical lemma regarding comparing a neural network to a local linear approximation has been improved, rather than an additive error term as in prior works, it yields a multiplicative error term. This is the key to ensure this paper to get a similar result as in data separable setting.

3. To prove the linearization approximation, it bounds an expression \langle \nabla f(x;W)-\nabla f(x;W_0), W \rangle for all \|x\| \leq 1. This is in contrast to the standard practice where the quantity f(x;V)-f(x;W)- \langle \nabla f(x;W), V-W \rangle for a fixed data point x and use a union bound. The technique employed in this paper is novel and from a different perspective compared to the convergence analysis of gradient descent on over-parametrized neural networks [Allen-Zhu, Li and Song, ICML’2019]. This co-VC dimension inspired technique has potentially to be used in other analysis, e.g., the convergence analysis of NTK and other variants.

Weakness:

1. The paper layout is a bit unusual and hard to follow. It spends a very small amount of paragraphs to set up the problem tentatively, then discuss the major contributions. These contributions are discussed in more details later with some of the notations left undefined until a later section. Section 2 and 3 are dedicated to present the essentials of the proof. It might be better to first introduce the problem background, its formal setup and some of the related literature on this problem in more detail. Then present a preliminary version of the main result. More details of the result can be laid out after introducing the notations.

2. It might be better to summarize and compare the results obtained in this paper with various previous works under different settings. For example, this paper obtains a similar popular risk loss result for data non-separable setting as some early works addressing data separable setting. Also, what’s the difference between the results obtained using the co-VC dimension technique compared with the standard analysis which makes use of the fact that weights are not far away from the initialization?

3. The early-stopping discussion in this paper is very preliminary. It is suggested on line 132 that this is due to technical reasons in the proof of Theorem 1.1, however, I don’t see an explicit mention or discussion related to early-stopping for this Theorem. A negative 1d result is also discussed as in Proposition 1.2. Due to the limited paragraphs involving this topic, it is hard to understand the importance and impact of early-stopping. 

If authors can address the above 2 and 3, and provide further clarification on the subject, I can raise the score.

Typos: On line 144, the definition of {\cal F}_n should be f: \R\rightarrow \R since the proposition considers 1d data.

Minor:

Some missing NTK citations:

Quadratic suffices for over-parametrization via matrix Chernoff bound.

On the Convergence Rate of Training Recurrent Neural Networks.

Training (over-parameterized) neural network in near linear time.

limitations_and_societal_impact: Yes, it discusses limitations. It does not discuss societal impact, however, since it's a pure theory paper, it does not have a direct impact.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper studies the training of single layer neural networks trained with gradient descent. The authors provide an upper bound on the logistic loss function using a reference infinite-width random feature model (which does not depend on the sampling of the training set). They also show that if a classifier in the 1-dimensional setting is in the interpolating regime, then the classification error is (depending on the number of consecutive wrong labeled samples) large. 

The proof is lengthy and quite involved and in appendix. On the one hand, a sketch of each result is provided in the main paper: it sheds light on the novel ingredients and technicalities used in the proof, which is useful (and explains for instance why the paper is restricted to logistic losses). On the other hand, the paper could make a better job to explain the gist behind the main result in (Theorem 1, which is half a page long just to be stated) in Section 1, by complementing the interesting remark 1.1 with a more practical discussion on how the parameters $m,\rho, R, \delta, \epsilon_{gd}$ are to be chosen as a function of $n, d$ to bring the three terms of the bound close to zero (simultaneously), and how the reference model $\overline{U}_\infty$ is obtained from the data. An interesting feature of this bound is indeed that it decomposes in three errors (on the model, optimization convergence, and generalization).

While the results are definitely worth publishing, I wonder if a journal in ML theory (where enough time is given to review the proofs in appendix) might not be a more appropriate venue than a conference for such a purely theoretical paper.
main_review: The proof of Theorem 1.1, as stated in line 107, lets the training iterations increase. Yet the classifier chosen in Theorem 1.1 is the one with the lowest empirical (training) loss ($R(W_{\leq t})$). The authors refer to this as the early stopped model, but the model is more the best model obtained on the training data up to time $t$. However, in practice an early stopped model does not have the lowest training loss: a low training loss is avoided by early stopping, which should not interpolate all the training samples and therefore the noise that could be present in the training set. Could you make the connection between the model $W_{\leq t}$ and early stopping?

Minor nit: In the equation between the lines 41 and 42: $l(r)$ should be $l(z)$.


limitations_and_societal_impact: Not relevant, the paper is purely mathematical on a theoretical model.
review_title: null

Meta-review: The paper is very well-written, clear, and the reviewers found the main theorem a strong contribution.

Please take into consideration the reviewers comments and suggestions in the final version.
Decision: Accept (Spotlight)