Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 6: Marginally above acceptance threshold
review_content: The paper studies optimization and generalization properties of deep relu networks trained with (stochastic) gradient descent on the logistic loss in the neural tangent kernel (NTK) regime. By using a new analysis that makes the "linearized" approximation as well as the L2 norm of the model in the approximate "random feature" kernel more explicit, the authors obtain results where the width only depends poly-logarithmically on the number of samples and 1/epsilon, for a test 0-1 loss of epsilon. This improves on previous analysis for deep networks, although it is similar to the two-layer result of Ji & Telgarsky.

I find the analysis interesting, more intuitive and practically relevant than previous studies, thanks to assumptions on the norm of the linearized model and the explicit bound on the approximation from linearization. The obtained guarantees are somewhat incremental are they are in large part similar to Ji & Telgarsky for the two-layer case, and remain in the NTK regime which only provides a limited picture of deep learning performance, but the extension to multiple layers and potentially other activations may be useful for the community, thus I remain on the accept side.

comments/questions:
- how do the dependencies of m and n on R or gamma compare to Ji & Telgarsky? more discussions on this comparisons at the end of sections 3.1 and 3.2 would be welcome
- the gap in sample complexity between GD and SGD is somewhat surprising (both the 1/eps^2 and the exponential dependency on L), is this just an artefact of the GD analysis in the generalization bound?
- in section 2, is the factor m^1/2 in the definition of f_W standard? how does this parameterization compare to previous works? (it seems like it may compensate the m^{-1/2} from the initialization of the first layer, which is often not present in other works, but this should be further discussed)
- in prop 4.4, it would be interesting to compare the obtained results to a simple linear model in the class NTRF, to see the cost of ensuring good linear approximation: does linear approximation require a larger m than what is needed just for good approximation of the infinite width kernel?


review_title: some useful but somewhat incremental improvements to finite-width NTK results

final_score: rating: 7: Good paper, accept
review_content: - Overview

This paper greatly relaxed the rate of over-parametrization for deep neural networks.
Previously, shallow networks required fewer parameters (polylog(eps)), while deep networks required a large number of parameters (\Omega (eps^{-14})).
This paper shows that faster rates can be achieved in deep networks.
The key result is the analysis around the initial values using the Taylor approximation, which is independent of the shallowness of the layers.
This result allows the paper to achieve rates similar to existing shallow neural networks.

- Comment.

The results are impactful, showing that global convergence can be said to be possible with over-parametrization, even in deep neural networks with smaller number of nodes.
The paper is carefully written and the differences from existing research and the place of novelty are easy to see.

My question is what difference does this make to the smooth activation function case?
Lemma 5.1 doesn't seem to make much use of the ReLU property, is the result similar to the smooth case in this case?

Another question relates to optimality.
Is it possible to give an additional analysis of the theoretical limitations of the rates obtained here to see if they can be further improved?

The other one, which is not that important, is the value of 4^L that appears in Theorem 3.4.
This value will be a major obstacle to thinking about deep neural nets, but I wonder if it can be explained.
review_title: Nice result

final_score: rating: 6: Marginally above acceptance threshold
review_content: The paper extends an existing proof for the sufficiency of polylogarithmic width for sharp learning guarantees of ReLU networks trained by (stochastic) gradient descent from shallow networks to deep networks. The theoretical analysis links the convergence of GD and SGD to the width of the network. The paper shows that polylogarithmic width is enough to give reasonable guarantees also for deep neural networks. It furthermore provides a generalisation bound in terms of network width.

The paper states a clearly formulated contribution and provides rigorous proofs for the claims stated. The analysis highly relies on the radius R of the NTRF function class and the authors provide a discussion showing the connection of the requirements on data separability to the values that R can take. The main lemma behind the proof and the sketch of the proof is also presented and explained.

The paper lacks a discussion of the applicability of the theory (e.g., how limiting are the assumptions of  the equal width layers, normalization by square root of m and the input norms being bounded by 1?), including a discussion on how the results could be generalized would be required. Also, since the paper extends a result on shallow networks to deep networks it should be discussed how depth affects the results. The generalization guarantees provided in this paper are vacuous without strict assumptions on data separability, as the authors state. However, it remains unclear whether the guarantee is non-vacuous for separable data. Could the authors argue whether the bound is non-vacuous for separable data?

But overall the contribution deems to be interesting still, so I suggest to accept the paper. 
review_title: Overparametrisation Generalisation Results for Deeper Networks

final_score: rating: 8: Top 50% of accepted papers, clear accept
review_content: The paper analyses the generalization properties of deep neural networks for classification tasks. The authors focus on the Neural Tangent Random Features (NTRF) class of functions to investigate these generalization properties.
In particular, the authors study the convergence of gradient descent (and its stochastic version). They establish that the training loss decreases until a certain level of the order of the best they can expect in the NTRF class. Then, the authors establish interesting generalization results with respect to the 0-1 loss. 
This problem has been tackled recently in many papers. However, to establish similar results as those proved in this paper, the previous papers required a number of neurons per hidden layer to be polynomial with respect to the number of samples n. The authors shows here that a logarithmic (to a certain power) is actually sufficient when working with the NRTF class. Such results have been obtained recently in Ji and Telgarski (2020) but only for shallow network. In this paper, the results are generalized for deep neural networks. 

The paper is clearly written and the comparison with the literature is complete and well-organized. The authors have worked hard to present, in a concise way and clearly their results. I appreciate it. The paper is fluid and nice to read. 

Here are some remarks that might improve the presentation of the paper:

- It would be nice to recall the function $\sigma$ in Section 2

- In my opinion the remark: 
" Moreover, while Ji and Telgarsky (2020)
essentially required all training data to be separable by a function in the NTRF function class with a
constant margin, our result does not require such data separation assumptions, and allows the NTRF
function class to misclassify a small proportion of the training data points",
is a big advantage of your analysis. Probably, you should spotlight it more clearly.

- Page 12 in the proof of Theorem 3.4. In the last inequality of the page, could you add that it holds because $-\ell'(x) \geq \ell(x)$ for all $x \in \mathbb R^d$. 

- Proposition 4.2: you use two notations for the proportion of data not satisfying the margin assumption. You should replace all the $\sigma$ by $\rho$. 

- Page 18: "where the equation follows from the fact that" --> $W^{0}$ should be $W^{t}$

- Before Equation (C.7). Could you add parenthesis around the product with  respect to $l$. Otherwise it is not very clear. 

- Could you explain a bit more Assumption 4.1. Is it a strong assumption ? Do you have any insight wether it is verified in practice ? 


To summarize, I enjoyed to review this paper. The results are clear and interesting. The paper deserves to be accepted for publication.

review_title: Well written paper with nice results but requiring precisions

Meta-review: The paper studies the convergence rate and generalization of deep ReLU networks trained with gradient descent and SGD in the NTK regime. Although the analysis technique is not really novel and heavily relies on past results, the paper is easy to follow and does provide some nice improvements compared to prior work (e.g. it require less overparametrization, and the NTRF function class is allowed to misclassify a fraction of the training data). Some of the results are very incremental, e.g. the generalization bound for GD seems to simply combine existing bounds on the Rademacher complexity from Bartlett et al. 2017 and from Cao et al. 2019. Nevertheless, the paper does have the potential to yield further improvements in the field and I therefore recommend acceptance as a poster.
Decision: Accept (Poster)