On the Generalization Power of the Overfitted Three-Layer Neural Tangent Kernel Model
Authors: Peizhong Ju
Xiaojun Lin
Ness Shroff
Venue: NeurIPS 2022 Accept (2022)

Abstract: In this paper, we study the generalization performance of overparameterized 3-layer NTK models. We show that, for a specific set of ground-truth functions (which we refer to as the "learnable set"), the test error of the overfitted 3-layer NTK is upper bounded by an expression that decreases with the number of neurons of the two hidden layers. Different from 2-layer NTK where there exists only one hidden-layer, the 3-layer NTK involves interactions between two hidden-layers. Our upper bound reveals that, between the two hidden-layers, the test error descends faster with respect to the number of neurons in the second hidden-layer (the one closer to the output) than with respect to that in the first hidden-layer (the one closer to the input). We also show that the learnable set of 3-layer NTK without bias is no smaller than that of 2-layer NTK models with various choices of bias in the neurons. However, in terms of the actual generalization performance, our results suggest that 3-layer NTK is much less sensitive to the choices of bias than 2-layer NTK, especially when the input dimension is large.

On the Generalization Power of the Overfitted Three-Layer Neural Tangent Kernel Model
Peizhong Ju Department of ECE The Ohio State University Columbus, OH 43210 ju.171@osu. edu
Xiaojun Lin School of ECE Purdue University West Lafayette, IN 47906 Linx@purdue.cr edu
Ness Shroff Department of ECE The Ohio State University Columbus, OH 43210 shroff. 11@osu. edu
Abstract
In this paper, we study the generalization performance of overparameterized 3- layer NTK models. We show that, for specific set of ground-truth functions (which we refer to as the "learnalle set"), the test error of the overfitted 3-layer NTK is upper bounded by an expression that decreases with the number of neu- rons of the two hidden layers. Different from 2-layer NTK where there exists only one hidden-layer, the 3-layer NTK involves interactions between hidden- layers. Our upper bound reveals that, between the two hidden-layers, the test error descends faster with respect the number of neurons in the second hidden-layer (the one closer to the output) than with respect to that in the first hidden-layer (the one closer the input). We also show that the learnable set of 3-layer NTK with- out bias is no smaller than that of 2-layer NTK models with various choices of bias in the neurons. However, in terms of the actual generalization performance, our results suggest that 3-layer NTK is much less sensitive to the choices of bias than 2-layer NTK, especially when the input dimension large.
Introduction
Neural tangent kernel (NTK) models (Jacot al., 2018) have been recently studied impor- tant intermediate step to understanding the exceptional generalization power of overparameterized deep neural networks (DNNs). Deep neural networks (DNNs) usually have so many parameters that they can perfectly fit all train data, yet they still have good generalization performance (Zhang et al., 2017: Advani al., 2020). This seems contradicting to the classical wisdom of "bias variance- tradeoff" in the statistical machine learning methods (Bishop, 2006; Hastie et al., 2009; Stein, 1956; James Stein, 1992; LeCun al., 1991; Tikhonov, 1943). To understand this distinct behavior of DNNs, recent line of work studies the so-called "double-descent" phenomenon, beginning with overfitted linear models. These results on linear models suggest that the test error indeed decreases again in the overparameterized region, the model complexity increases beyond the number of sam- ples (Belkin et al., 2018, 2019; Bartlett et al., 2020; Hastic et al., 2019; Muthukumar et al., 2019; Ju et al., 2020; Mei & Montanari, 2019). However, these studies tures such as Gaussian or Fourier features, and hence they fail to capture the con-linearity in neural networks. In contrast, NTK models adopt features generated by non-linear activation functions (i.e., neurons of DNNs), and thus they can be viewed as an intermediate step between simple linear mod- els and DNNs. Along this line, the work in Ju al. (2021) studies 2-layer NTK models, and shows that the 2-layer NTK model indeed exhibits better and different descent behavior in the overparam- eterized region, which might be closer to that of actual neural network.
linear models with simple fea-
Motivated by Ju et al. (2021), it is of great interest to understand whether similar insights extend to deeper NTK models. In particular, in this paper study NTK models with 3 layers. Although
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

both 2-layer and 3-layer NTK models share similar assumptions (e.g., trained weights do not change much from initialization, and features are linearized around the initial state), their difference in struc- ture leads to completely different feature formation. Compared with 2-layer NTK models that only contain one hidden-layer of neurons, 3-layer NTK models have two hidden-layers, which interact in more complex ways not observed in 2-layer NTK models. Specifically, let P1 and P2 denote the number of neurons in the two hidden layers. Then, the ultimate features of the 3-layer NTK models depend both pl and p2. This dependency leads to the following questions. First, the width of which layer is more important in governing the descent behavior, pi or p2? Further, to get better descent behaviors, should p1 and P2 grow at the same speed, or should one of them grow faster than the other? Second, do 3-layer NTK models have any performance advantage over 2-layer NTK models?
To answer these questions, in this paper we study the generalization performance of overfitted min- 22-norm solutions for 3-layer NTK models where the middle layer is trained. For a set of learnable functions (which we refer to as the "learnable set"), we provide an upper bound on the test error for finite values of pl and p2. To the best of our knowledge, this upper bound is the first result that can reveal the dependency of the descent behavior on p1 and p2 separately. We then compare 3-layer NTK with 2-layer NTK with respect to the corresponding learnable set and the actual generalization performance. Our comparison reveals several important differences between 3-layer NTK and 2- layer NTK, in terms of the descent behavior, the size of the learnable set, and the sensitivity of the generalization performance to the choice of bias of the neurons.
Analyzing the Generalization Error: First, we show that the generalization error (denoted by the absolute value of the difference between the model output and the ground-truth for a test input) is up- per bounded by the sum of several terms on the order of O(1 / /n) (n denotes the number of training data), O(1/p2) (p2 denotes the number of neurons in the second hidden-layer). O( //log P1 /p1) (p1 denotes the number of neurons in the first (adden-layer), plus another term related to the magnitude of noise. Similar to 2-layer NTK (Arora al., 2019; Ju et al., 2021; Satpathi & Srikant, 2021). our upper bound suggests that when there are infinitely many neurons, the generalization error decreases with the number of samples at the speed of v and will approach zero when n - in the noise- less situation. Further, the noise term will not explode when the number of neurons goes to infinity, which is also similar that for 2-layer NTK. However, our upper bound also reveals new insights that are different from the results for 2-layer NTK. Specifically, our upper bound decreases slower with respect to the number of neurons in the first hidden-layer P1 at the speed of // t(log p1 //1/ and decreases faster with respect to the number of neurons in the second' hidden-layer at the speed of 1/ pp. Further, our upper bounds hold regardless of how fast pı and p2 increase relative each other (e.g., they could increase at the same speed, or one could increase faster than the other).
Characterizing the Learnable Set: We then show that, even if we only train the middle-layer weights, the learnable set (i.e., the set of ground-truth functions for which the above upper bound holds) of the 3-layer NTK without bias contains all finite degree polynomials, which is strictly larger than that of the 2-layer NTK without bias and is at least as large as the 2-layer NTK with bias. Recently, Geifman et al. (2020); Chen & Xu (2020) show that when all layers trained, 3-layer NTK leads to exactly the same reproducing kernel Hilbert space (RKHS) as 2-layer NTK with biased ReLU (although they assumed an infinite number of neurons, and did not characterize the descent behavior of the generalization error). Combining with their results, we can draw the conclusion that training only the middle-layer weights is at least as effective as training all layers in 3-layer NTK, in terms of the size of the learnable set.
Sensitivity to the Choices of Bias: Even though a similar learnable set can be attained by 3-layer NTK (with or without bias) and 2-layer NTK (with bias), our results suggest that the actual gener- alization performance can still differ significantly in terms of the sensitivity especially when the input dimension d is large. One type of bias setting commonly used in litera- ture (Ghorbani et al., 2021a; Satpathi & Srikant, 2021) is that the bias has a similar magnitude as each element of the input vector, which we refer to as "normal bias". However, we show that such a normal bias setting has a negative impact on the generalization error for overfitted 2-layer NTK when d is large. To avoid this negative impact, it is important to use another type of bias setting where the bias has a similar magnitude as the norm of the whole input vector, which we refer as
the choice of bias,
In this paper, the first hidden- layer denotes the one closer to the input layer, while the second hidden-layer denotes the one closer to the output layer.
2

---

output
Wh
top layer weights w 2nd hidden-layer: P2 ReLU
W
W Wo[4] mid layer weights Wo 1st hidden-layer; p1 ReLU bottom- Mittom-layeraoee weights V imput æ
v[1]
V[3]
[2] #22
21
22
Figure 1: A fully-connected three-layer neural network where input dimension d = the number of neurons of the first hidden-layer p1 = 3, and the number of neurons of the second hidden-layer P2 4.
"balanced bias". In contrast, for 3-layer NTK, different bias settings do not have obvious effect on the generalization performance. In summary, compared with 2-layer NTK, the use of an extra non-linear layer in 3-layer NTK appears to significantly reduce the impact due the choice of bias, and therefore makes the learning more robust.
Our work is related to the growing literature on the generalization performance of such shallow and fully-connected neural network. However, most of these studies focus on 2-layer neural net- works. Among them, they differ in which layer to train. For example, Mei & Montanari (2019); d'Ascoli et al. (2020); Mei et al. (2022) consider the "random fcature" (RF) model that only trains the top-layer weights and fixes the bottom-layer weights, while 2-layer NTK trains the bottom-layer weights. In contrast, our work on 3-layer NTK neither trains the bottom-layer or top-layer weights. Instead, train the middle-layer weights, since the middle-layer of 3-layer model involves the interaction between two hidden-layers, which does not exist in 2-layer models. The above studies of 2-layer network also differ in how the number of neurons/features p, the number of training samples n, and the input dimension grow. Mei & Montanari (2019); Mei et al. (2022) study the generaliza- tion performance of the RF model where the number of neurons p, the number of training data n, and the input dimension grow proportionally to infinity. While Ghorbani et al. (2021b) focuses on the approximation error (i.c., expressiveness) of both RF and NTK models, their analysis on general- ization error is only on the limit n or + oc. All of these studies are quite different from ours with fixed n and finite p. Other works such as Arora et (2019); Satpathi & Srikant (2021); Fiat et al. (2019) study the situation where the number of training samples is given and the number of neu- rons p is larger than a threshold, which closer to our setup. However, these studies usually do not quantify how the generalization performance depends on the number of neurons p. Specifically, they usually provide an upper bound on the generalization error when the number of neurons p is greater than threshold, while the upper bound itself does not depend on p. Thus, such upper bound cannot explain the descent behavior of NTK models. The work Ju al. (2021) does study the descent behavior with respect to p. and is therefore the closest to our work. However, as we have explained carlier, there are crucial differences between 2 and layers in both the descent behavior and the learnable set of ground- truth functions. In addition to the above references, also related to Allen-Zhu et al. (2019) (which studies NTK without overfitting) and Ji & Telgarsky (2019) (which studies classification by NTK). Their settings however different from ours in that we consider overfitted solutions for regression. In summary, our paper is the first to provide a high- probability upper bound the generalization error of the overfitted 3-layer NTK (where only its middle layer weights are trained), and to characterize how the generalization error decreases with the number of neurons p1 and p2.
work is
2 System Model
Let f Rd + R denote the ground-truth function. Let (X,, f(X,) + +;), i 1,2, ,n denote n pieces of training data, where E Rnx is the matrix, each column of which is the input of one training sample, E Rax1 denotes the noise in the output of training data. We define the training output vector generated by the ground-truth function as F(X)= == [f(X) f(X2) ... s(X,)) R"
3

---

We use alj] to denote the j-th part (sub-vector) of the vector a. The part size depends on Specifi- cally, If a has p1 elements, then each part has elements. If has dp1 elements, then each part has d elements. If a has P1P2 elements, then each part has p1 elements.
We consider fully-connected 3-layer neural network illustrated in Fig. 1, which consists of normalized d-dimensional input æ E S (a unit hyper-sphere), P1 ReLUs (rectifier linear units max(-, 0)) the first hidden-layer, p2 ReLUs the second hidden-layer, bottom-layer weights (between input and 1xt hidden-layer) V R((id)x middle-layer weights (between 1st hidden-layer and 2nd hidden-layer) Wo R(P1Pa)x1 and top-layer weights E R (between 2nd hidden- layer and output).
2.1 Overfitted NTK solution
In this subsection, we will derive the overfitted solution for this 3-layer neural network using the NTK approximation. Let hE ,a RR x1 denote the output the first hidden-layer. We then have
RF h hV.
bi] == (x"V (aVViil) (=)) j 1,2, PI
(1)
(We use the superscript "RF" because &E is indeed the feature vector of random feature model (Mei & Montanari, 2019).) After training the middle-layer weights, Wo changes W1 AW. Then, the change of the output is
Wo
Σ wx IW 20) Wi [M] RF
wk m A Wo(k)T hV
The NTK model (Jacot al., 2018) assumes that AW is very small and thus the activation pattern does not change much. other words, we can approximate [W](N) 203 by 1(Wo(A) >0>-
Define AW E (PIP))) as [W = wk AW = 1.2.-.... .p. Define hV
Three
Wo, E
R (pipp) such that
h
Three Wo.a
[k:] == (h )TT 1 (00 ) (W
(2)
where k = 1,2, P2. Therefore, the change of the output can be approximated by
we (Wo AW 1)
T RE =
Thrse by W...... AW.
We thus obtain linear model in AW, We provide an illustration of the formation and structure of these vectors in Fig. 4, Appendix A. in Supplementary Material. Define the design matrix Three
He E x (piPs) such that its i-th row is H, = hV.W..XX Notice that overfitted gradient descent on linear model converges to the min f--nrmm solution", which is denoted by
A == arg min
||l||| subject to Hw = F(X) +
wER(P1r2)x1
When H is full row-rank (which holds with high probability under certain conditions), the trained model is then
(x)
Three h WV.Wo.
W.W.
A
-vy
Three W..
H (HHH") +e).
(3)
Notice that the trained model is determined by multiple random variables.
In order to analyze the generalization performance of the trained model, we have make assump- tions on the distribution of those random variables. Let pl-), X(-), and 7(-) denote the probability density function of V[j), and W, (k), respectively. For simplicity, make the following assump- tion that all random variables follow uniform distribution.
2 As suggested other prior works Satpathi Srikant (2021): Hastie al. (2019); Ju al. (2021), if perform gradient descent training on linear model from zero initial point until the training error zero (i.e., overfitting), then the solution will be exactly the min form solution. Note that we do not need to be concerned about the training dynamics here, because the min fz fornorm overfitted solution can be written down exactly as in Eq. (3).

---

Assumption 1. The imput a and the bottom-layer initial weights V (j = 1.2. P1) are i..d. and uniformly distributed in S In other words, pl.) and X()) are both unif(S The middle- layer initial weights Wolk]'s 's (k- = 1, 2, ..... P22) are ii.d. and uniformly distributed in Sm Sm-11 In other words, 7(-) is unif(S
The top-layer weights w are all non-zero'.
Remark Readers may be curious why we only train the middle-layer weights. Part of the reason is technicality: if the bottom layer is also trained, the aggregate output of the first hidden-layer may have changed so much that the second hidden-layer 's inputs and ReLU activation patterns change significantly from initialization, which may violate the NTK assumption. The work in Geifman et al. (2020); Chen & Xu (2020) is not concerned about this difficulty, since they are mostly interested in wish to
the expressive power of the RKHS, assuming an infinite number of neurons. In contrast, capture the effect of finite width, and thus train only the middle layer to avoid this difficulty. More importantly, the middle-layer weights interact with both the first hidden layer and the second hidden- layer, and are the major structural distinction compared with 2-layer NTK. This setting thus helps us answer the following interesting question: will training the middle layer alone already achieve the same (potential) benefit as training all layers (especially given that the latter encounters more technical difficulty)?
3 Generalization Performance
In this section, we will show our main results about the generalization performance of the aforemen- tioned 3-layer NTK model for a specific set of functions. We first introduce a set of ground-trute functions that may be learnable and then provide high-probability upper bound on the test error. We then discuss some useful implications of our upper bound.
3.1 A set of ground-trute functions that may be learnable
We define kernel functions KRF, KTToo and Thhree be explained soon):
[-1, 1] R as follows (whose meanings will
RR (a) == v1 a²
(T arccos(a))
(4)
2d K Two (a) == a arccos(a)
(5)
2T
K Taree (a) K Two (2d K RRF (a))
(6)
2d
(Notice that 2d- K RF (a) E 10, 1] for all a [-1, by Lemma 43 in Supplementary Material,
Appendix I, and hence K TTmnoe)) (.) is well defined.) We define a set F of ground-truth functions based on those kernels:
Definition (learnable set of 3-layer NTK).
F/8 { [g: S + R [g(xt) [ K Thhme (x²2))(=)dn(()) 1loll < <oo. (7)
SSu
where |1g]lo = supzese-1 19(2)1.
To see why functions in Ffg may be learnable, can check what the learned result f in Eq. (3) should look like. When there are infinite number of neurons and there is no noise (i.e.. = 0), what remains on the right-hand-side of Eq. (3) can be viewed as the product of two Three H" and (HH*) F For the first term h Three HJ note that each row of WV.Wa.
terms, V W...
H is given by h Three W.. for = 1,2, n. Thus, when P1,P2 + co, the i-th element of W...W..e W.. .HT, which is the inner product between h Three W... and h VV W..xx converges in proba- bility to TThree Three Three ) (tV.W...
W,, )² which exactly the kernel function of 3-layer NTK. By representing the second term (HH"))-F(X with a certain g(-). f must then approach the form
We do not need to specify the distribution w, since w is absorbed into the regressor A AW by definition A W[K] = we [kkk) k- 2, .p2.
5

---

in Eq. (7). (See Supplementary Material, Appendix B for details.) Intuitively, K Three can be thought of the composition of the kernels of each of the two layers, which are Two and R given in Eq. (5) and Eq. (4). Specifically, suppose that we fix the output of the first hidden layer (i.e., h xe) and regard it as the input of 2-layer NTK formed by the top two layers of the 3-layer neural net- work. By letting P2 - 0o, we can show that the inner product between V.W... Wo. and h Three VV. Wo.X. hT X, (with necessary normalization of h and hV x. where K KTwo is exactly the kernel of 2-layer NTK in Ju et al. (2021). Second, when P1 - 0o, we can show that (hR,,e) x² h x, x, approaches KRF (xx x;), where KRF exactly the kernel of the random-feature model (Mei & Montanari, 2019). In summary,
approaches K TTw ( at )T
be approxi- mated by (-). However, note that the above deviation is only about the expressiveness of 3-layer NTK and it does not precisely reveal its generalization performance.
expect that functions in F
3.2 An upper bound on the generalization error
We now present the first main result of this paper, which is an upper bound that quantifies the relationship between the generalization performance and system parameters.
Theorem 1. For any ground-truth function f(x) = (x() E F(ayy when d is fixed and pi are
much larger than (with high probability) we have
(x) - -[(x)] =
1191loo vn
0
119112 VP2
+
Term
o (101l
log
|
|illl
+
12
log n2
(8)
P1
VR
Term
Term
A more precise version of the upper bound and the condition of Theorem as well as its derivation can be found in Supplementary Material, Appendix C.
As we can see, Eq. (8) captures how the test error depends on finite values of parameters n, Pl, P2. ||e||2, and g. Later in this section we will examine more closely how n, Pi, and p2 affect the value of the upper bound. Regarding the dependency finite Intuitively, the norm of y represents the complexity of the ground-truth function in F(a, When the norm of g is larger, then the right-hand side of Eq. (8) becomes larger, which indicates that such ground function is harder to learn. A simple example is that if we enlarge a ground truth function fg E F(3,, by 2 times (which means g is 2 times larger), then since the model is linear,
9. Eq. (8) works as long as ||g]|1 and I| are
the test error If of functions satisfy the condition of finite norm of g in Section 4.
f(x) will become times larger. We will discuss more about which types
Next, we will discuss some implications of this upper bound of 3-layer NTK. While some of them are similar to 2-layer NTK, others are significantly different, revealing the complexity due to having more layers.
3.3 Interpretations similar to 2-layer NTK
Based on the upper bound in Theorem 3, we have the following insights for 3-layer NTK, which are similar to those for 2-layer NTK shown in et al. (2021). These similarities may reveal some intrinsic properties of the NTK models regardless of the number of layers.
Zero test error with n - oo in the ideal situation: In the ideal situation where there are infinitely many neurons and no noise, the only remaining term in Eq. (8) is Term A. Notice that Term A decreases to zero as n + xc, which indicates that the generalization error decreases zero when
'Indeed, as long ||g||> sc, then [|g/] < oo. That is why we only include the condition ||gl|> < oo in Eq. (7). Notice that the assumption || < oo can be relaxed to l|g]]a < oo by similar methods showing in Ju et al. (2021). However, as shown in Ju et al. (2021), such relaxation leads to a different upper bound with slower descent speed with respect

---

both change
(c) fix P; 200
(d) 200
10a1
10*
o'
0.04
10
*
0.00
10"1
MSE
10
d' 0
10-1
o² 10
10-4
10-2
10-4
10-2
10-1
10
10
10
10
10a
10"
10
10a
207
Px. =
Figure 2: Curves of MSE for 3-layer NTK (no-bias) with respect to P1 or P2 when there exists
Gaussian noise whose mean is zero and the variance is o². The ground-trun truth function is f(x)
(x T e2) 2 + +1x++ e;) where = 3. Sample size is n = 200. Every curve is the median of 20 random
simulations.
more training data are provided in the ideal situation. Term A suggests that such decreasing speed is at least 1/ Vn. Such result is consistent with that of 2-layer NTK, e.g., in Arora et al. (2019).
3.4 Insights that are distinct compared with 2-layer NTK
Compared with 2-layer NTK, an important difference for 3-layer NTK is that there are more than one hidden-layers. Therefore, the speed of the descent of 3-layer NTK involves the interaction between two hidden-layers.
Descent with respect to the number of neurons: In Eq. (8), Term B and Term C contain p1 and P2. respectively. For any given n and noise level ||e||2, Terms and D do not change, and Term E decreases with and P2- (More discussion about Term E can be found in Supplementary Material, Appendix D, where we discuss the noise effect.) Therefore, by increasing P1 and p2, Term B and Term C keep decreasing. In summary, right- hand--e of Eq. (8) decreases as the number of neurons P1 and pa increases, which validates the descent in the overparameterizet region of 3-layer NTK.
Different descent speed: As shown in Eq. (8), Pi and p2 play different roles in the descent of the generalization error. Comparing Term B and Term C of Eq. (8), can see that the upper bound of the test error f (2x) - [xx) decreases faster with respect to P2 (at the speed of //2) and slower with respect to P1 (at the speed of /pi/log P1). We emphasize that this difference is not due to the number of weights/parameters contributed by the number of neurons in each hidden-layer of p1 and p2 5. Instead, we conjecture that such difference in the speed of descent may be due to the different positions in this 3-layer neural network structure, where the second hidden-layer takes the trained middle-layer weights as its input (and thus utilizes the trained weights better than the first hidden-layer).
We use numerical results to illustrate the different roles of pı and p2 in reducing the generalization error. We fix P2 200 and plot the MSE with respect to pl in Fig. 2(b). Although the test error decreases when increases, the decreasing speed is slow, especially for the noisy situation. Such a slow decreasing speed with P1 remains even when P2 is fixed in Fig. 2(b), we fix P2 = oc, we still observe the similarly slow decreasing speed with P1 as shown by Fig. 2(c). In contrast, the descent with respect to p2 should be casier observe and can reach a lower test MSE. In Fig. 2(d), we fix P1 = 200 and increase P2 (i.e., we exchange the values of P1 and P2 in Fig. dd)) As we can see, all three curves Fig. 2(d) have a more obvious descent and decrease to lower MSE compared with those in Fig. 2(c), which validates our conjecture that the descent speed with respect the number of neurons of the second hidden-layer faster.
much higher value. For example,
Notice that our upper bound Eq. (8) also suggests a descent when both and p2 increase simultane- ously. We use simulation result by Fig. 2(a) support this point. We fixed n 200 and let p1 = P2 increase simultaneously. The ground-truth model in this figure is f(xr) = (ax e)² + (xx" e where (no noise), o² 0.01,
3. The green, orange, and blue curves denote the situations of o² and o² 0.04, respectively. Every point in this figure is the median of 20 simulation runs. We also
"Specifically, the number of weights that get trained equals to P1Pz and the total number of weights for bottom, middle, and top layers equals to dp: + P1P2 + Pz. In other words, the number of weights (either for the middle layer for all layers) does not increase faster by increasing p2 instead of p1.
7

---

provide the box plot of the situation of o² = 0.01 (correspond to the orange curve). It is obvious that all three curves descend, which verifies that the generalization error of the overfitted 3-layer NTK model decreases when p1 and p2 increase simultaneously at the same speed. By observing the box plot for the situation o² = 0.01 (the orange curve), we also notice that when p1 = P2 becomes large, the variance becomes small. This is because all initial weights are i.i.d. random and large number of weights may reduce the variance of the model due to the law of large numbers. Our upper bound in Theorem 3 also suggests such reduced variance as the probability in Theorem 3 increases as pi increases.
4 Types of Ground-True Functions
Are 3-layer (i.e., deeper) networks better than 2-layer networks in any way for generalization per- formance? In the last section, we have seen that both 3-layer NTK and 2-layer NTK can achieve zero test eπror when π + 3o in the ideal noiseless situation, when the ground-truth functions are in their respective learnable set". natural question is then to compare the learnable sets between these two models, and to compare the generalization performance when the ground-truth function belongs to both learnable sets. In this section, we provide some answers by studying various types of ground-truth functions and their effects on the generalization performance.
4.1 Size of the learnable set
For 2-layer NTK, as shown in Ju et al. (2021), when no bias is used in ReLU, the corresponding learnable set F(2) contains all even polynomials and linear functions, but does not contain other odd polynomials. In order to learn both even and odd polynomials, it is critical that bias is added to ReLU (Satpathi & Srikant, 2021; Ju et al., 2021). In contrast, we prove the following result:
Proposition 2. (3) (with unbiased ReLU, middle layer being trained) already contains all polyno- mials with finite degree (i.e., including both even and odd polynomials). Further, the learnable set Fla of 3-layer NTK is strictly larger than that of the 2-layer NTK with unbiased ReLU, and is at least as large as that of the 2-layer NTK with biased ReLUU.
This independence to bias shown by Proposition 2 can be seen as one performance advantage of 3- layer NTK compared to 2-layer NTK. Details (including more precise statement) about this result in Supplementary Material, Appendix J. Notice that Geifman et al. (2020); Chen & Xu (2020) show that when training all layers, 3-layer NTK leads to the same RKHS as 2-layer NTK with biased ReLU. However, it is unclear whether training one layer is already sufficient for achieving the same RKHS as training all layers. Our result in Proposition answers this question positively, i.e., only training the middle layer has already achieved all benefits of training all layers in terms of the size of the learnable set. (In other words, training all three layers will not expand the learnable set over training only the middle layer.)
4.2 Different bias settings with high input dimension
Even when a ground-truth function belongs to both Fi2,s and F'2)- their generalization performance may still exhibit some differences, In this subsection, we will show that when the input dimension is high, some specific choice of bias of the 2-layer NTK has better generalization performance than others. contrast, the 3-layer NTK is less sensitive to different bias settings.
Notice that adding bias to each ReLU in 2-layer NTK is equivalent to appending a constant to æ while still using ReLU without bias. Specifically, the input vector for biased 2-layer NTK
B3 : Vi- a
E Rd+1
'From bottom to top, the five horizontal lines of each marker of box plot represent the minimum (ex- cluding outliers), first quartile (25%). median (50%), third quartile (75%), and maximum (excluding outliers). respectively. See (McGill et al., 1978) for more details.
We illustrate the generalization performance of ground-trun -tuth functions outside the learnable set in Supple- mentary Material, Appendix J.3.
8

---

Model
Learnable functions set
Category
3-layer NTK, no-bias
F/
Uge-1 Klhree (x² 2)g(z)du(())
(i)
2-layer NTK, no-bias
F
Uss-= K <o''''' 2)g( 2)g(z)du(z))
(ii)
2-layer NTK, normal-bias
SSo 1KT00 T+ x² + ae )=(=)du(()) (/sa-1 K (3
(i)
NLB
2-layer NTK, balanced-bias
Fl
(2)
(2)
Table I: Learnable functions for different NTK models. Category: (i) can learn both even- and odd-power polynomials; (ii) cannot learn other odd-power polynomials except linear functions. (We omit the condition | oc oo in the expression of learnable sets to save space.)
(a) d=
(b) d = 15
4
10
3
3-NTK no bias
3-NTK normal-bias
M55
10-4
20-2
balanced-bias
2-NTK no-blas
10-9
10
NTK nomall-baas
6 10
balanced
10a
10a
10a
10a
10a
10a
Figure 3: Comparison of test MSE with respect to n between different NTK models when the num-
ber of neurons is infinite and without noise. The ground-truth function is f(x) d+2 (x"ei)² x e1. Every curve is the average of random simulations.
where b E (0, 1) denotes the initial bias. We also normalize the first d elements of by v1 ba | = 1. Under this biased setting, the 2-layer NTK model has the (2),6 == (s--1 Two (1=-9)==* z + b²) g(z)d/(z),
in Eq. (9) to make sure that ||
learnable set Flg
|| < cc}.
common setup for the initial magnitude of the bias of each ReLU is to use a value that is close equal to the average magnitude of each element of input æ, e.g., Satpathi & Srikant (2021); Ghorbani et al. (2021a). Specifically, we let b = VatI in Eq. (9), and denote the corresponding
learnable set by F (2).NLB We refer to this setting as the "normal-bias" setting. Alternatively, the initial magnitude the bias can be chosen to be close or equal to ||a:||2- Specifically, we let = -
in Eq. (9) and denote the corresponding learnable set by (2). We refer to this second setting as "balanced-bias"" The specific expression of F(2)- Ffa (L), and F (2),88 can derived by using similar methods shown in Section 3.1 (results are listed in Table 1).
We now discuss how the two different bias settings could affect the generalization performance when d is large. For 2-layer NTK under the normal-bias setting, the kernel is Two (24) x 4 Although it contains both even and odd power polynomials, we notice that when increases,
K Two approaches its no-bias counterpart K <=To z), which only contains even power polynomials and linear term. Thus, conjecture that, by increasing d, the generalization performance of 2- layer NTK with normal-bias will deteriorate for those ground-truth functions inside F(2), (2) but far
away from F(2) (e.g., odd-degree non-linear polynomials). In contrast, for 2-layer NTK under the balanced- bias setting, the kernel is K TTo (1x²= 1). which does not change with d. Therefore, we expect that such deterioration should not happen. Note that 3-layer NTK, although normal- bias setting still approaches no- bias setting when d increases, there does not exist such performance deterioration, because F/2 (the learnable set of 3-layer NTK without bias) already contains both and odd power polynomials. These insights will be verified by the numerical results below.
We now use simulation results in Fig. validate the conjecture that 3-layer NTK models are less sensitive to different bias settings than 2-layer NTK models. We let the ground-truit -ruth function be f(x) d=2 ex) x²' e1, which orthogonal to F(aj. In Fig. 3(a) when have similar performance except 2-layer NTK without bias, whose test error is always above the null risk. In Fig. 3(b) when d 15, the purple curve of 2-layer NTK with normal bias gets closer to the
2, all settings

---

red curve of 2-layer NTK without bias (and thus the generalization performance becomes worse), while other curves are still close each other. This validates our conjecture that 3-layer NTK models are less sensitive to different bias settings than 2-layer NTK models. Further simulations can be found in Appendix A.2.
Conclusion
In this paper, we studied the generalization performance of overfitted 3-layer NTK models. Com- pared with 2-layer NTK models, 3-layer NTK is less sensitive different bias settings. Further, training only the middle layer can get most of the performance advantage of 3-layer NTK, in terms of the learnable set. Possible future directions include: (i) studying whether training other layers will get the same benefit training the middle layer; (ii) approximating the actual neural network where the learned result far away from the initial state; (iii) investigating deeper network as well as other structures such as convolutional neural network (CNN) and recursive neural network (RNN).
Acknowledgments and Disclosure of Funding
This work has been supported part by NSF grants: 2112471 (also partly funded by DHS), CNS- 2 2106933, CNS-1901057, CNS-2113893, and the Bilsland Dissertation Fellowship at Purdue Univer- sity, and grant from the Army Research Office: IN--11---1
References
Advani, M. S., Saxe, A. M., and Sompolinsky, H. High-dimensional dynamics of generalization error in neural networks. Neural Networks, 132:428-446, 2020.
Allen-Zhu, Z., Li, Y., and Liang, Y. Learning and generalization in overparameterized neural net- works, going beyond two layers. In Advances in neural information processing systems, pp. 6158- 2019.
Arora, S., Du, S., Hu, W., Li, Z., and Wang, R. Fine-grained analysis of optimization and generaliza- tion for overparameterized two-layer neural networks. In International Conference Machine Learning, pp. 322-332, 2019.
Bartlett, L., Long, M., Lugosi, G., and Tsigler, Benign overfitting in linear regression. Proceedings of the National Academy of Sciences, 2020.
Belkin, M., Ma, S., and Mandal, S. To understand deep learning we need to understand kernel learning. International Conference on Machine Learning, pp. 541-549, 2018
Belkin, M., Hsu, D., and Xu, J. Two models of double descent for weak features. arXiv preprint arXiv: 1.XXv:9903.0771, 2019.
Bell, H. E. Gershgorin's theorem and the zeros of polynomials. The American Mathematical Monthly, 72(3):292-299 295, 1965.
Bishop, C. M. Pattern recognition and machine learning. Springer, 2006.
Chaudhry, M. A., Qadir, A., Rafique, M., and Zubair, S. Extension of euler's beta function. Journal of computational and applied mathematics, 78(1):19-33 32, 1997.
Chen, C.-P. and Qi, F. The best bounds in wallis' inequality. Proceedings of the American Mathe- matical Society, pp. 397-401, 2005.
Chen, L. and Xu, S. Deep neural tangent kernel and laplace kernel have the same rkhs. arXiv preprint arXiv:2009.10688 2020.
Dokmanic, I. and Petrinovic, D. Convolution on the r-sphere with application to pdf modeling. IEEE transactions on signal processing, 58(3):1157-11777 2009.
Dutka, J. The incomplete beta function-a -a historical profile. Archive for history of exact sciences, pp. 11-29, 1981.
10

---

d' Ascoll, S., Refinetti, M., Biroli, G., and Krzakala, F. Double trouble in double descent: Bias and variance (s) in the lazy regime. In International Conference on Machine Learning. pp. 2280-2290. PMLR, 2020.
Fiat, J., Malach, E., and Shalev-Shwartz, S. Decoupling gating from linearity. arXiv preprint OrXiv:1906.05000 2019.
Geifman, A., Yadav, A., Kasten, Y., Galun, M., Jacobs, D., and Ronen, B. On the similarity between the laplace and neural tangent kemnels. Advances in Neural Information Processing Systems, 33: 1451-1461, 2020.
Ghorbani, B., Mei, S., Misiakiewicz, T., and Montanari, A. Linearized two-layers neural networks in high dimension. The Annals of Statistics, 49(2): 1029-104, 2021a.
Ghorbani, B., Mei, S., Misiakiewicz. I., and Montanari, Linearized two-layers neural networks in high dimension. The Annals of Statistics, 49(2):1029-1055: 2021b.
Hastie, T., Tibshirani, R., and Friedman. J. The elements of statistical learning: data mining, infer- ence, and prediction. Springer Science & Business Media, 2009.
Hastie, T., Montanari, A., Rosset, S., and Tibshirani, R. J. Surprises in high-dimensional ridgeless least squares interpolation. arXiv preprint 1903 190.00090,.08560, 2019.
Jacot, A.,
Gabriel, F,, and Hongler, C. Neural tangent kernel: Convergence and generalization in neural networks. In Advances in neural information processing systems, pp. 8571-8580, 2018.
James, W. and Stein, C. Estimation with quadratic loss. In Breakthroughs in Statistics, pp. 443-460. Springer, 1992.
Ji, Z. and Telgarsky, M. Polylogarithmic width suffices for gradient descent achieve arbitrarily small test error with shallow relu networks. arXiv preprint arXiv:1909. 12292, 2019.
Ju, P., Lin, X., and Liu, J. Overfitting can be harmless for basis pursuit, but only to degree. Advances in Neural Information Processing Systems, 33, 2020.
Ju, P., Lin, X., and Shroff, N. On the generalization power of overfitted two-layer neural tangent kernel models. In International Conference on Machine Learning, pp. 5137-5147. PMLR, 2021.
Laha, R. and Rohatgi. V. Probability Theory. Wiley Series in Probability and Statistics. Wiley, 1979. ISBN 9780471032625, URL pesttps://bookee google.
AAAAMAAJ.
LeCun, Y., Kanter, I., and Solla, S. A. Second order properties of error surfaces: Learning time and generalization. In Advances in Neural Information Processing Systems, pp. 918-924, 1991.
Li, Concise formulas for the area and volume of a hyperspherical cap. Asian Journal of Mathe- matics and Statistics, 4(1):66-700 000;6667,2200 2011.
Li, Y. and Wong, R. Integral and series representations of the dirac delta function. arXiv preprint arXiv: 1303. / 1943, 2013.
McGill, R., Tukey, J. W., and Larsen, W. A. Variations of box plots. The american statistician, 32 (1):12-16, 1978.
Mei, S. and Montanari, A. The generalization error of random features regression: Precise asymp- totics and double descent curve. arXiv preprint 1XXiv:990..05338 2019.
Mei, S., Misiakiewicz, T., and Montanari, A. Generalization error of random feature and kernel methods: Hypercontractivity and kernel matrix concentration. Applied and Computational Har- monic Analysis, 59:3-84, 2022.
Muthukumar, V., Vodrahalli, K., and Sahai, A. Harmless interpolation of noisy data in regression. In 2019 IEEE International Symposium on Information Theory (ISIT), pp. 2303. IEEE, 2019.
Satpathi, S. and Srikant, R. The dynamics of gradient descent for overparametrized neural networks. In Learning for Dynamics and Control. pp. 373-384, PMLR, 2021.

---

Stein, C. Inadmissibility of the usual estimator for the mean of multivariate normal distribution. Technical report, Stanford University Stanford United States, 1956.
Tikhonov, A. N. On the stability of inverse problems. In Dokl. Akad. Nauk SSSR, volume 39, pp. 195-198, 1943.
Vilenkin, N. Y. Special functions and the theory of group representations, providence: American mathematical society. sfip, 1968.
Wainwright, M. Uniform laws of large numbers, 2015. https://wwa stat. baeaatebreley...... edu/ mnjjain/sttt210b. Chapp// wttp:///CChhAAnnniomnaaaaaa Uniform_Febe 2015. pdf, Accessed: Feb. 7, 2021.
Zhang, C., Bengio, S., Hardt, M., Recht, B., and Vinyals, O. Understanding deep learning requires rethinking generalization. In 5th International Conference Learning Representations. ICLR 2017,2017
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] E.g., see Remark 1.
(c) Did you discuss any potential negative societal impacts of your work? [No] This work
on the learning theory and should have potential negative societal impacts.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes]
3. If you ran experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main ex- perimental results (either in the supplemental material or as URL)? [No] As this mainly a theoretical paper.
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes]
(c) Did you report error bars (c.g., with respect the random seed after running experi- ments multiple times)? [Yes] See Fig. 2.
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [No] As this is mainly a theoretical paper.
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're re using/curating? [N/A]
(c) Did you discuss whether the data you are using/curating contains personally identifi- able information or offensive content? [N/A]
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review
Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid participants and the total amount spent participant compensation? [N/A]
12


Reviews:
[{"review_id": "szkFSLCRh4o", "reviewer": "Reviewer_2rdZ", "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.", "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?\n\nQ2: 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.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n1. 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.\n2. The proof seems to be solid. \n3. From my understanding and my knowledge about NTK, the assumptions in this paper are mild and the size of the learnable set is large.\n\nWeaknesses:\n1. 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.\n2. 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.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "adhRVAbNtiS", "reviewer": "Reviewer_RBFS", "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.\n\nThe 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. \n\nIn 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.", "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\n\n- 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?\n\n- 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\n\n- 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?\n\n- 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**", "rating": 6, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths**: \n- This work takes an important step toward gaining an understanding of the behavior of DNNs by theoretically analyzing three layer NN models\n\n- 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\n\n- 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\n\n**Weaknesses**:\n- 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\n\n- 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\n\n- 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$\n\n- 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.\n\n- 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\n\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "P86aui5Incj", "reviewer": "Reviewer_6CH3", "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.", "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?\n\nAlso, can you relate these experiments to the effect of noise?", "limitations": "NA", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "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. \n\nThe 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.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ["I don’t know"]}, "extra_text": {}}, {"review_id": "5ELUtsamv3Y", "reviewer": "Reviewer_sEV3", "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. \n\nOverall, 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. ", "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. \n\n# Major Questions\n\n1. 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. \n\n2. 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? \n\n2.(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? \n\n2.(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? \n\n3. 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? \n\n4. 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? \n\n5. I have several questions about the upper bound in Theorem 1. \n\n5.(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? \n\n5.(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? \n\n5.(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. \n\n6. 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. \n\n# Minor Questions\n\n1. 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. \n\n2. 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? \n\n3. In equation 7, what is the measure $\\mu$? ", "limitations": "N/A ", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "# Strengths \n1. 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. \n\n# Weaknesses \n1. I had some trouble reading the paper and understanding the contributions. \n2. 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. ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept