Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: This manuscript analyses the neural tangent kernel in the regime of minimum over-parameterization. In detail, the authors prove the lower bound about the NTK eigenvalue for deep nets with minimum over-parameterization. Then, they apply the theorems to the aspects of networks' memorization and training.
strengths_and_weaknesses: Pros:

This manuscript deeply investigate the question of minimum over-parameterization;

The proofs are solid;

Two application are proposed based on theorems.

Cons:

This paper is very theoretical and focuses on the minimum over-parameterization in deep learning. I am not an expert about the NTK research, so I mainly give some comments and suggestion on writting. For me, it is neccesary to clearly and comprehensively illustrate the backgroud and significance on investigating the problem of minium over-parameterizatio, please see Questions below.

Some minor writing suggestions:

1. Line 60: the full name of PSD should be proposed;
questions: 1. The modern deep learning foucses on "super" over-parameterization, why do the paper research the minimum over-parameterization? For completing the NTK theorem? How the research on the minimum over-parameterization help understand the success of deep nets?

2. What is the mean of "to be conditioned"?

3. About the experiments of Figure 2, are the used labels random? If yes, Can we get the similar results with normal label (or normal dataset with low complexity, compared to the complex random datasets)? 

limitations: Please the Questions.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: This submission studies the problem of minimum over-parameterization in deep neural networks. More specifically, the authors investigated the settings with sublinear layer width and provides the lower bound in terms of the smallest NTK eigenvalue.
strengths_and_weaknesses: I must first say that this paper is much beyond my expertise, and the evaluation of this submission should depend on other reviewers with necessary background.

Strength:
As the authors claimed, this paper gives an affirmative answer regarding whether NTK is well-conditioned in the sublinear setting. The theoretical results from Theorem 3.1 match the claim. The authors also provide details proof to cover the main steps.

Weakness:
Some clarification regarding the assumptions would be helpful to understand the major conclusion. For example, if \alpha >= 1 in Eq. (4), does it mean that the number of neurons would exceed the sublinear case? 

Another case is regarding the proof for the smallest NTK eigenvalue: how does it depend on the optimizer? Since NTK changes with updated parameters (which may explode if optimization failed), does the proof depend on any hidden assumptions for the optimizer?  
questions: See above
limitations: Yes
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: For an $L$-layer (loosely) pyramidal network, this paper gives a probabilistic lower bound on the smallest eigenvalue of the empirical neural tangent kernel Gram matrix, which is proportional to the product of the width of the last two hidden layers. When combined with known results on NTK, this lower bound implies that $\sim \sqrt{N}$ neurons are enough to learn a solution (via GD) that memorizes $N$ copies of data. 
strengths_and_weaknesses: I do not have anything major against the acceptance of this paper. The paper is well written and the theoretical contributions are clear (up to my knowledge). I especially appreciate the proof-technical innovation in the paper---the three-stage centering argument may be quite useful for the future works in this direction.

Nevertheless, I do have some minor concerns:

- Assumption 2.4 restricts the setup to neural networks with "loose pyramidal topology," which seems to be much weaker than the strict pyramidal topology in the sense that the layer width need only be smaller than a constant times the preceding layer's width. While this looks very easy to satisfy, this also suggests that actually many "constants" are being hidden inside the big-O notation of Theorem 3.1. Could you briefly describe the what the hidden terms of Theorem 3.1 are, and how they behave with respect to the assumption?

- The probability of event at Theorem 3.1. is $1 - C \exp(-c\sqrt{N}) - CN\exp(-c\log^2 n_{L-1})$. I am particularly worried about the last term, which is proportional to the sample size $N$. Could you explain in more detail, why, and under what condition such $N$-proportionality does not really make the probabilistic bound meaningless?

- I do not find Figure 1 to be very meaningful---any curve can look linear when we select a nice interval.
questions: My questions are basically the same as the weaknesses described above:

- Could you describe what the hidden terms of Theorem 3.1. are?

- Please explain when and why $CN\exp(-c\log^2 n_{L-1})$ would be small enough for event in Theorem 3.1 would happen with a sufficiently large probability.
limitations: Limitations are well-addressed.
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 shows that NTK can be well-conditioned in a sub-linear setup. In particular, they proved that roughly  $\Omega (N)$ parameters are needed to get a good NTK matrix, and also $O(N)$ parameters are enough to memorize the training data. Based on those NTK bounds, they further provide results on the memorization capacity and the optimization via gradient descent and square loss.  
strengths_and_weaknesses: It is interesting to study the neural network in a sub-linear setup. For square loss, the authors provided valuable sight for the training data memorization as well as the optimization. This paper is well-written and clear for the technique part. However, I have several concerns about the significance and the limitation of the results. Besides,  I think this paper can improve the clarity of their results by making a comparison with the setting for the classification. 
questions: 1. Requirement 4 in Assumption 2.5 implies that the total number of neurons should be larger than $\Omega(N^{(1+\alpha)/2})$. This violates the statement after Theorem 3.1 in line 175. 

2. The authors argue that when all the widths have the same scaling, the upper bound matches the lower bound. In this case, the training data size $N$ should be smaller than $d^{2/(1+\alpha)}$ according to Assumption 2.5, where d is the dimension of the input. This is a fairly strong condition for the training data set, which may limit the significance of the results.  

3. Under certain margin assumptions on the training data, [1] showed that a polylogarithmic width condition suffices for two-layer ReLU networks to converge and generalize. Later [2] studied how much over-parameterization is sufficient to learn deep ReLU networks and showed that under certain assumptions on the training data, polylogarithmic width is sufficient. Since these papers have milder overparameterization conditions of the NNs, the authors may want to make a comparison with those results. 

[1] Ji, Ziwei, and Matus Telgarsky. "Polylogarithmic width suffices for gradient descent to achieve arbitrarily small test error with shallow ReLU networks." International Conference on Learning Representations. 2019.

[2] Chen, Zixiang, et al. "How Much Over-parameterization Is Sufficient to Learn Deep ReLU Networks?." International Conference on Learning Representations. 2020.
limitations: The authors have addressed their work's limitations and potential negative social impact.
review_title: null

Meta-review: metareview: solid contribution to ntk theory
confidence: Certain
Decision: Accept