Venue: NeurIPS 2022 Conference

Reviews:

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 studied generalization error of 3-layer neural networks with two caveats (1) only the middle layer weights are trained (2) only a class of regression functions are considered. An upper bound is provided in Theorem 1, with interesting dependence on the second hidden layer width. 

Overall, I had some trouble reading the paper and trying to understand the contributions. I hope the authors can join me during the discussion period and help me clarify some of my questions, after which I would be happy to raise my scores if we reach a clearer understanding. 
strengths_and_weaknesses: # Strengths 
1. The generalization error bound contains an interesting dependence on layer width, which may be of interest for understanding deeper networks outside of the kernel regime. 

# Weaknesses 
1. I had some trouble reading the paper and understanding the contributions. 
2. The results the authors achieved contain enough caveats that I'm not sure if we can really draw strong conclusions as the authors have claimed. 
questions: I understand this work is highly technical and perhaps not the easiest to present in a straight forward manner. So I hope the authors can help clarify many of my questions, as I cannot make a confidence judgement based on my first read of the paper. 

# Major Questions

1. The authors did not precisely define the training dynamics considered, in particular the variable $\overline{\Delta W}$ on line 140 is undefined. Can the authors clarify this part? I believe this is really important. 

2. The authors introduced some heavy notation, which is possibly well motivated, but I am having a lot trouble interpreting. Can the authors give a high level intuition and motivation behind the following definitions? 

2.(a) For weight matrices and hidden layers, why do the authors avoid using regular matrix multiplication? That why define $h^{RF}_{V,x}[ j ]$ based on $x^\top V[j] $ instead of just using $ ( V x )_+ $? Is there a distinct advantage for treating the elements separately? 

2.(b) How should I interpret $h^{Three}_{V, W_0, x}[k]$? This object contains a first layer random feature, but also the activation pattern of the next layer as well? 

3. Perhaps because of the previous question, I don't understand why "overfitted gradient descent" converges to the min $\ell_2$-norm solution defined by $\Delta W^\{\ell_2}$. At the same time, can the authors motivate the $\Delta$ notation here? It seems me that this is just the optimal weights? This is also confusing because if we train the second layer weights, wouldn't the activation pattern on the next layer also change as a result, therefore leading to a non-linear model? 

4. The authors defined $\mathcal{F}^{\ell_2}_{(3)}$ as the set of learnable functions. Maybe I'm misunderstanding this, can the authors explain if this definition is motivated by heuristics, or if there is a concrete learnability statement somewhere in the paper? 

5. I have several questions about the upper bound in Theorem 1. 

5.(a) It appears that the product of term D and E gets larger as $n$ increases, which leads to the question: is there a step that is loose, or does $p_1$ need to significantly larger than $n$ in order for the bound to vanish? 

5.(b) In Ghorbani et al. (2019), the paper showed that polynomials of higher degrees require a higher sample complexity to learn for random feature models. However, in the current work, the authors suggested that the learnable set of functions contains all polynomials of finite degrees. Can the authors explain which part is the key difference in the settings that led to this discrepancy? 

5.(c) The authors drew the conclusion that the second hidden layer is more important from this upper bound. However, do the authors authors have any insights towards whether or not this upper bound is tight in terms of $p_1,p_2$? Otherwise, I'm sure the authors understand, I can always make an upper bound worse to draw the opposite conclusion following this line of logic. 

6. The authors showed that the learnable set is strictly larger than $\mathcal{F}^{\ell_2}_{(2)}$, which is for the two layer NTK. Do the authors have any insights towards a negative result, i.e. are there actually functions contained in $\mathcal{F}^{\ell_2}_{(3)}$ such that a three layer network can learn, but a two layer NTK cannot? Because otherwise again, I'm sure the authors understand, I can modify the definitions to draw the opposite conclusion. 

# Minor Questions

1. Can the authors motivate the uniform distribution assumptions made on the weights, and explain what roles this plays in the proof? This seems pretty non-standard, and adds towards my concern on how useful the conclusions are given an additional caveat. 

2. The authors defined $K^{RF}, K^{Two}, K^{Three}$ based on the RF kernel and NTK kernel, however with extra factors of $d$ in the definitions. Is this important? 

3. In equation 7, what is the measure $\mu$? 
limitations: N/A
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: In this work, the authors investigate three-layer ReLU networks, in the regression setting to shed greater light on the behavior of practical DNNs, by capturing the hidden layer interactions. Specifically, the work focuses on determining how the (hidden) layer interactions influence the phenomenon of _double-descent_ and consequently investigate any improvement in the generalization performance with the increase in depth over a similar two-layer model.

The authors showcase that in the case of having only the middle-layer trained, the test error of the setup in concern is upper-bounded by the sample complexity $n$, and the hidden layer widths $p_1$ and $p_2$ and analyze the relevance of these entities in maximally affecting the test performance. 

In this particular effort, the work demonstrates that while equivalent two-layer networks (with bias), possess the same expressiveness as the three-layer network (without bias) in focus, its generalization performance is dependent on the bias choice itself. Following this demonstration, the authors then subsequently put forth a novel bias choice in terms of the input vector norm which can alleviate the robustness issue of the two-layer model.
strengths_and_weaknesses: **Strengths**: 
- This work takes an important step toward gaining an understanding of the behavior of DNNs by theoretically analyzing three layer NN models

- It provides a formal bound, albeit under specific input data & fixed layer weights' distribution choice, on the test performance of the concerned three-layer model in terms of the training set size and the widths of the hidden layers, and consequently concludes that the width of the 2$^\text{nd}$ hidden-layer plays the greatest role in the reduction of the test error within the chosen setup

- While possibly indicative due to the presence of the extra-layer, it establishes that the three-layer network _without_ a bias term and with only the middle-layer trained is at least as expressive as its two-layer _biased_ counterpart and strictly more expressive as the two-layer unbiased one

**Weaknesses**:
- It is unclear to me why the authors chose to use the **NTK** terminology in their title and the paper itself for classifying the operational regime of their network given the fact that the hidden-layer widths of their model do not $\to\infty$ as what is strictly required to be in the NTK regime

- While it is acknowledged that a primary objective for the authors has been to understand the concerned network setup in the _practical_ finite-width regime, a truer to the title endeavor would have been to study and compare the NT Kernel for the two models in the asymptotic regime

- It appears that the setup to train the middle layer only was chosen on the seemingly weak premise stated in _Remark 1_, rather than through a formal argument based upon _lazy_ parameterization or taking the widths $\to\infty$

- Variable definitions seem to be incomplete. For e.g. in Eq. (7), $z$ and $g$ seem to be not defined. Same for the caption in Figure 2.

- One of the main claims by the authors is that the middle layer width plays a more central role in decreasing the model test error based upon their upper bound result. It is not justified why such behavior cannot be an artifact of their very choice of the model setup i.e. the middle layer itself is trained


questions: - In Line 141, how do the authors justify the assumption that the movement of the middle-layer weights during training, is indeed infinitesimal given the network's weights do _not_ $\to\infty$ and the model parameterization is not accordingly chosen to be in the lazy regime

- While understood that it was performed for the sake of mathematical simplicity, the authors assume a uniform distribution of the inputs, bottom, and middle layer weights. Can the authors provide a reasoning and qualitative formulation of what might happen for the more standard Gaussian assumption?

- While stated in **Definition 1** to be the **learnable set of 3-layer NTK**, it is not totally evident that the stated set encompasses the entire learnable function space of the chosen model

- In Theorem 1, the authors claim that the result holds with a **high probability**? Can they provide a formal estimation of the probability in question?

- Can the authors explain the observation of essentially zero reduction in the test error for $\sigma^2 = 0.1, 0.4$ in Fig 2 (b)?
limitations: Please see **Questions** and **Weaknesses**
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 paper studies the generalization performance of a neural network with two hidden layers when only the intermediate hidden layer is trained under the NTK assumption (Trained weights are not too far from initialized weights and the hidden layer activation pattern does not change). They show that the the position of hidden layer is crucial for the generalization performance by comparing existing results of 2-NTK with their 3-NTK model.
strengths_and_weaknesses: The paper offers fresh and quantitative insights on the effect of the hidden position of hidden layers on the performance of the neural network. While there is a long list of works exclusively looking at single hidden layer networks, the effect of the intermediate hidden layer has not been well studied in the literature. 

The effect of noise is somewhat counterintuitive. As of now, it seems that generalization worsens as the number of samples increases in presence of noise. This might suggest that upper bound on generalization has some room for improvement.
questions: Regarding lower bounds of the eigenvalue of $HH^T$: I see that it depends on $\mathcal{J}$. When is this bound useful? I see the discussion about it when $p_1p_2 \to \infty$. In a quantitative sense, how big should $p_1, p_2$ be? How would that compare to your experiments in Fig 2?

Also, can you relate these experiments to the effect of noise?
limitations: NA
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 paper studies the generalization performance of overparameterized 3-layer NTK models. A learnable set of ground-truth functions is defined for characterizing the generalization error with regard to the number of samples and the number of two hidden layers. The results provide insights into which hidden layer plays a more important role and how the bias affects the size of the learnable set. Some interesting comparisons are made between 3-layer NTK and 2-layer NTK. Overall the paper is good, especially in its excellent theoretical work, but I still have some concerns. I am willing to increase the score if the responses can solve my questions.
strengths_and_weaknesses: Strengths:
1. The insights are interesting, especially the discussion about how the bias affects the size of the learnable set. The results are also verified by the experiments.
2. The proof seems to be solid. 
3. From my understanding and my knowledge about NTK, the assumptions in this paper are mild and the size of the learnable set is large.

Weaknesses:
1. Although the experiment verifies this, the conclusion that the second hidden layer is more important than the first hidden layer seems weak since only the second hidden layer is trained. More theoretical explanations are required. In line 164, it states that it is to "avoid violating NTK assumption" to do so, but papers such as "Learning and generalization in overparameterized neural networks, going beyond two layers" by Z. Allen-Zhu et al. (Neurips 2019) and "Generalization Guarantee of Training Graph Convolutional Networks with Graph Topology Sampling" by H. Li et al. (ICML 2022) consider training both two hidden layers in 3-layer NTK. Some discussions and comparisons might be needed here with regard to these papers.
2. Some parts of writing can be improved. For example, from equations 1 to 3, I think the authors mainly want to give a result of the trained model. I think it is better to make this part a subsection to let people know what this part is intended to cover. Otherwise, readers may feel strange and difficult to follow because the authors suddenly start to derive many equations when introducing the problem formulations and the setup.
questions: Q1: I would like to know more about the comparison between this paper and the papers I mentioned in Weakness 1. What does NTK with/without overfitting mean?

Q2: Is the trained model irrelevant to the step size and the number of iterations? If so, why is that?
limitations: The authors adequately addressed the limitations and potential negative societal impact of their work.
review_title: null

Meta-review: metareview: This paper studies the generalization error of three-layer relu neural networks, when only the middle layer weights are trained. 
The focus is the regression setting, and the goal is to capture the hidden layer interactions. The paper aims to determine how the (hidden) layer interactions influence the double-descent curve. The generalization error bound established depends on the layer width in an interesting manner, which may shed light on understanding deeper networks outside of the kernel regime.

All reviewers rated this work above the bar. As such, I recommend accepting this paper.

There were a few parts that the reviewers found unclear/needs improvement. In particular, some of the clarifications made by the authors in their rebuttal can help make this paper more clear for its future readers.



confidence: Certain
Decision: Accept