A NON-PARAMETRIC REGRESSION VIEWPOINT : GENERALIZATION OF OVERPARAMETRIZED DEEP RELU NETWORK UNDER NOISY OBSERVATIONS
Authors: Namjoon Suh
Hyunouk Ko
Xiaoming Huo
Venue: ICLR 2022 Poster (2022)
Keywords: Overparametrized Deep Neural Network
Neural Tangent Kernel
Minimax
Non-parametric regression

Abstract: We study the generalization properties of the overparameterized deep neural network (DNN) with Rectified Linear Unit (ReLU) activations.
Under the non-parametric regression framework, it is assumed that the ground-truth function is from a reproducing kernel Hilbert space (RKHS) induced by a neural tangent kernel (NTK) of ReLU DNN, and a dataset is given with the noises. Without a delicate adoption of early stopping, we prove that the overparametrized DNN trained by vanilla gradient descent does not recover the ground-truth function. It turns out that the estimated DNN's $L_{2}$ prediction error is bounded away from $0$. As a complement of the above result, we show that the $\ell_{2}$-regularized gradient descent enables the overparametrized DNN achieve the minimax optimal convergence rate of the $L_{2}$ prediction error, without early stopping. Notably, the rate we obtained is faster than $\mathcal{O}(n^{-1/2})$ known in the literature.

Published as a conference paper at ICLR 2022
A NON-PARAMETRIC R VIEWPOINT GEN- ERALIZATION OF OVERPARAMETRIZED DEEP RELU NETWORK UNDER NOISY OBSERVATIONS
Namjoon Suh, Hyumouk Ko, Xiaoming Huo
H.Milton Stewart School of Industrial and Systems Engineering
Georgia Institute of Technology Atlanta, GA, USA (namjsuh, hko39, huo ( (eggeeh.aeeeeeee..e.eeeee..e..ee
ABSTRACT
We study the generalization properties of the overparameterized deep neural net- work (DNN) with Rectified Linear Unit (RcLU) activations. Under the non- parametric regression framework. it is assumed that the ground-truth function is from a reproducing kernel Hilbert space (RKHS) induced by a neural tangent kernel (NTK) of ReLU DNN, and dataset is given with the noises. Without a delicate adoption of early stopping, we prove that the overparametrized DNN trained by vanilla gradient descent does recover the ground-truth function. It turns out that the estimated DNN's L2 prediction error is bounded away from O. As complement of the above result, we show that the fz-regularized gradient descent enables the overparametrized DNN to achieve the minimax optimal con- vergence rate of the L prediction error, without early stopping. Notably, the rate we obtained faster than O(n 1/2) known in the literature.
INTRODUCTION
Over the past few years, Neural Tangent Kernel (NTK) [Arora et al., 2019b; Jacot al., 2018; Lee et al.. 2018; Chizat & Bach, 2018] has been one of the most seminal discoveries in the theory of neural network. The underpinning idea of the NTK-type theory comes from the observation that in a wide-enough neural net, model parameters updated by gradient descent (GD) stay close to their initializations during the training, so that the dynamics of the networks can be approximated by the first-order Taylor expansion with respect to its parameters at initialization. The linearization of learning dynamics on neural networks has been helpful showing the linear convergence of the training error both overparametrized shallow [Li & Liang, 2018; Du et al., 2018] and deep neural networks [Allen-Zhu et al., 2018; Zou et al., 2018; 2020), as well as the characterizations of generalization error both models [Arora al., 2019a; Cao & Gu, 2019]. These findings clearly lead to the equivalence between learning dynamics of neural networks and the kernel methods in reproducing kernel Hilbert spaces (RKHS) associated with NTK. Specifically, Arora et al. [2019a] provided the 1/2) generalization bound of shallow neural network, where denotes the training sample size.
Recently, in the context of nonparametric regression, two papers, Nitanda & Suzuki [2020] and Hu et al. [2021]. showed that neural network can obtain the convergence rate faster than O(n-1/2) by specifying the complexities of target function and hypothesis space. Specifically, Ni- landa & Suzuki [2020] showed that the shallow neural network with smoothly approximated ReLU (swish, see Ramachandran al. [2017]) activation trained via fz-regularized averaged stochastic gradient descent (SGD) can recover the target function from RKHSs induced from NTK with swish activation. Similarly, Hu al. [2021] showed that shallow neural network with ReLU activation trained via bg erregulariied GD can generalize well, when the target function (i.c., f7) is from HNTK
Henceforth, we denote HATK and HTTK as RKHSs induced from NTK of shallow L. = and deep neural networks I, > with ReI.U activations, respecitvely.

---

Published as a conference paper at ICLR 2022
Notably, the rate that the papers Nitanda & Suzuki [2020] and Hu et al. [2021] obtained is minimax optimal, meaning that no estimators perform substantially better than the lz fz-regularized GD or averaged SGD algorithms for recovering functions from respective function spaces. Nevertheless, these results are restricted to shallow neural networks, and cannot explain the generalization abilities of deep neural network (DNNN). Similarly with Arora al. [2019a], Cao & Gu [2019] obtained the (/2) generalization bound, showing that the SGD generalize well for fp HN when fo has a bounded RKHS norm. However, the rate they obtained is slower than the minimax rate can actually achieve. Furthermore, their results become vacuous under the presence of additive noises on the data set. Motivated from these observations, the fundamental question in this study is follows:
When the noisy dataset is generated from function from H does the overparametrized DNN obtained via (fz-regularized) GD provably generalize well the unseen data?
We consider a neural network that has I. 2 2 hidden layers with width m > (i.e., over- parametrized deep neural network.) We focus on the least-quuares loss and assume that the acti- vation function is ReLU, A positivity assumption of NTK from ReLU DNN imposed, meaning that Aoo > O, where Ase denotes the minimum eigenvalue of the NTK. We give a more formal math- ematical definition of ReLU DNN in the following Subsection 2.2. Under these settings, we provide an affirmative answer to the above question by investigating the behavior of Le-prediction error of the obtained neural network with respect to GD iterations.
1.1 CONTRIBUTIONS
Our derivations of algorithm-dependent prediction risk bound require the analysis training dy- namics of the estimated neural network through (regularized) GD algorithm. We include these results as the contributions of our paper, which can be of independent interests well.
In an unregulaized case, under the assumption A > O, we show that the training loss con- verges at a linear rate. As will be detailed in subsection 3.3, this the different result from the seminal work of Allen-Zhu et al. [2018), where they also prove a linear conver- gence of training loss of ReLU DNN, but under different data distribution assumption.
We show that the DNN updated via vanilla GD does not recover the ground truth function fr E HNTK under noisy observations, if the DNN is trained for either too short or too long: that is, the prediction error is bounded away from by some constant as goes to infinity.
In regularized case, prove the mean-squared error (MSE) of DNN is upper bounded by some positive constant. Additionally, we proved the dynamics of the estimated neural network get close to the solution of kernel ridge regression associated with NTK from ReLU DNN.
We show that the lzrreuularization can be helpful achieving the minimax optimal rate of the prediction risk for recovering f E H., under the noisy data. Specifically, it is shown that after some iterations fg-regularized GD, the minimax optimal rate (which is On zd-1), where d is a feature dimension.) can be achieved.
Note that our paper is an extension of Hu et al. [2021] to DNN model, showing that the fz-regularized DNN achieve minimax optimal rate of prediction error for recovering f HNTK However, we would like to emphasize that our work is not a trivial application of their work from at least two technical aspects. These aspects are more detailed in the following subsection.
1.2 TECHNICAL COMPARISONS WITH HU ET AL. [2021]
Firstly, in the analysis of training loss of regularized shallow neural-net, Hu et al. [2021] begin the proof by decomposing the difference between two individual predictions into two terms: one that is related with the gram matrix evaluated at each iteration of the algorithm and the perturbation term. Henceforth, we name this decompostion as "Gram+Pert" decomposition. This decomposition can be checked with the equality (E.2) in the supplementary PDF of Hu al. [2021]. The key ingredients for the decomposition are (i) the simple gradient structure of the shallow neural net, and (ii) the partitioning of the nodes in the hidden-layer into two sets: set of nodes whose activation
2

---

Published as a conference paper at ICLR 2022
patterns change from their initializations during training, and the complement of the set. This construction of the sets peels off the ReLU activation in the difference so that the GD algorithm can be involved in the analysis. However, because of the compositional structure of the network, the same nodes partitioning technique cannot be applied for obtaining the decomposition in the DNN setting with ReLU activation. To avoid this difficulty, we employ specially designed diagonal matrix Σ and this matrix can peel off the ReLU function for each layer of the network. (See the definition of Σ in the proof of Theorem 3.5 in the Appendix.) Recursive applications of this diagonal matrix across the entire hidden layers enable the Gram+Pert decomposition in our setting. It should be noted that the diagnoal matrix Σ had been employed in Zou et al. [2020], which analyzed the behavior of training loss of classification problem via ReLU DNN under logistic loss. However, since their result is dependent on different data distribution assumption under the different loss function from ours, they didn't t employ the Gram+Pert decomposition. Thus their technical approaches are different from ours.
Secondly, Hu et al. [2021] directly penalized the weight parameter W by adding | to the objective function. The fz-regularization solely on the W has an effect of pushing the weight towards the origin. This makes [|W(4) - w S (1)) allowing most activation patterns of the nodes in the hidden layer can change during the training, even in overparametrized setting- Here, ((() denotes the updated weight parameter at kth itertaion of algorithm, and ||- denotes the spectral norm of the matrix. Nonetheless, this doesn't 't affect the analysis on obtaining the upper-bound of MSE in shallow neural net, since the network has only a single hidden layer. In contrast, in the DNN setting, we allow the non-convex interactions of parameters across the hidden layers. To the best of our knowledge, a technique for controlling the size of f2-norm of network gradient has not been developed under this setting, yet. We circumvent this difficulty by regularizing the distance between the updated and the initialized parameter, instead by directly regularizing the updated parameter. This ensures that the updated parameter by fz-regularized GD stays in a close neighborhood to its initialization, so that with heavy over-parametrization the dynamics of network becomes linearized in parameter and we ignore the non-convex interactions of parameters across the hidden layers. Specifically, under suitable model parameter setting, we prove that (|w(()) ( ll2 S O² (+()))) over all f {1, (l,..., L}. Here, Öx(-) hides the dependencies on the model parameters; L, w. and n. This result allows us adopt the so-called "Forward Stability" argument developed by Allen-Zhu et al. [2018], and eventually leads to the control of network gradient under & sense.
1.3 ADDITIONAL RELATED WORKS
There has been another line of work trying to characterize the generalizabilities of DNN under noisy observation settings. Specifically, it has been shown that the neural network model can achieve minimax style optimal convergence rates of Ing-prediction risk both in regression [Bauer& & Kohler, 2019; Liu et al., 2019; Schmidt-Hieber. 2020] and classification [Kim et al., 2021] problems. Nonetheless, a limitation of the aforementioned papers is that they assume an adequate minimizer of the empirical risk can be obtained. In other words, the mathematical proofs of their theorems do not correspond to implementable algortihms.
Recently, several papers, which study the generalization properties of neural network with algorithmic guarantees, appear online. Specifically, Kohler & Krzyzak [2019] showed that the data interpolants obtained through DNN by vanilla GD is inconsistent. This result is consistent with our result, but they consider the overparametrized DNN that is linear combination of (2(n2dd' smaller neural network, and the activation function they consider is sigmoid function, which is smooth and differentiable. Along this line of research, Kuzborskij & Szepesvári [2021] (regression) and Ji et al. [2021] (classification) showed that when training overparametrized shallow neural network, early stopping of vanilla GD enables to obtain consistent estimators.
This was empirically shown to true in paper Wei et al. [2019]. See Figure 3 in their paper. We provide a brief mathematical explanation on why this result is hard to be shown in Appendix C. Readers can find the proof of this result in Appendix G.
3

---

Published as a conference paper at ICLR 2022
Notation. We the following notation for asymptoties: For sufficiently large write f(n) (()(n)) if there exists a constant >> 0 such that f(n) S Kg(n), and f(n) = [(g(n)) if f(n) 2 (')(n) for some constant K' > 0. The notation [(n ((g(n)) means that f(n) (g((n) and f(n) = ((g(n)). Let (A, B) Tr = Tr( B3 for the two matrices A, B E Rd xds, We adopt the shorthand notation denoting [n] [1,2,--- - for N.
2
PROBLEM FORMULATION
2.1 NON-PARAMETRIC REGRESSION
Let X' C R' and y C be the measureable feature space and output space. We denote as a joint probability measure the product space X' x y. and let px be the marginal distribution of the feature space X. We assume that the noisy data-set D == ((x;, Vi) are generated from the non-parametric regression model y; (x,) + Es where E, iid. N(O, 12) for 1,..., n. Let (: be the value of neural network evaluated with the parameters W at the k-th iterations of GD update rule. At = O. we randomly initialize the weight parameters in the model following He ini- tialization [He et al., 2015] with slight modification. Then, the L2 prediction risk is defined as the difference between two expected risks (i.e., excess risk) (()(())) = Ep-(xx))((x (w) (x)) ' and R(fz) = E (xx - fx()) where (x) == E|y/x]. Then, we can easily show the prediction risk has following form:
R R(fu 53) R(wwas) - R(5) = Exps (Frra)(x) 15x)))
Note that the expectation is taken over the marginal probability measure of feature space, Pxs and the noise of the data, E. However, the (1) is still a random quantity due to the randomness of the initialized parameters (W(") Eml,..,,
2.2 DEEP NEURAL NETWORK WITH RELU ACTIVATION
Following the setting introduced in Ahu et al. [2018], we consider a fully-connected deep neural networks with L hidden layers and m network width. For L 2 2, the output of the network fw(() E I with input data x E X can be formally written as follows:
fw(x) = /m v owo(WWnn (W..1 ... o (wxx)...))
(2)
where Sd-1 is a unit sphere in d-dimensional euclidean space, o()) is an entry-wise activation function, W1 Raxd W W, E mmxx denote the weight matrices for hidden layers and v E mx denote the weight vector for the output layer. Following the existing literature, we will consider ReLU activation function o (xx) max(x, 0), which is the most commonly used activation function by practitioners.
Random Initialization. Each entries of weight matrices in hidden layers are assumed to be generated from (Wis)
(O, 2), and entries of the output layer are drawn from Vj ~ (O, د. This initialization scheme helps the forward propagation neither explode nor vanish at the initialization, seeing Allen-Zhu et al. [2018]; Zou et al. [2018; 2020). Note that we initialize the parameters in the last layer with variance 2 where w 1 model parameter to be chosen later for technical convenience.
m
Unregularized GD update rule. D:
We solve following lossoss function with the given dataset
1 n
(y (v.-x(xx))) Σ
Es W) -
(3)
i=1
Let (0) ((
& be the initialized weight matrices introduced above, and we consider follow- ing gradient descent update rule:
w! wik-1) W (f l E (T), k
(4)
4

---

Published as a conference paper at ICLR 2022
where W. (Cs(-)) is partial gradient of the loss function (s(+) with respect the f-th layer parameters We. and 1) > 0 is the learning rate of the gradient descent.
Ez-regularized GD update rule. function;
The estimator is obtained by minimizing a lz-regularized
L
d W) = Ls (WD)
1 2
Σ
W
w D
(5)
8=1
Naturally, we update the model parameters { D2t E= via modified GD update rule:
w: Di = (1-
(1-k1) Vw, LCs Wws ( (-)]""")== + T2 (0) DE
VeE [4], vk (6)
D.E
The notations '/1 7/2 are step sizes, and l 0 is a tuning parameter on regularization. We adopt the different step sizes for the partial gradient and regularized term for the theoretical conveniences. Furthermore, we add the additional subscript D to the update rule (6) to denote the variables are under the regularized GD update rule. Recall that the W the unregularized case. For simplicity, we fix the output layer, and train T, hidden layers for both unregularized and regularized cases.
D.g are initialized parameters same with
MAIN THEORY
First, we describe the neural tangent kernel (NTK) matrix of (2), which first proposed by Jacot et al. [2018] and further studied by Arora et al. [2019b]; Du et al. [2019]; Lee et al. [2018]; Yang kernel matrix, whose entries are the infthite-width limit of the gram matrix. Let Vw. [fw(o) (-] be the gradient of the ReLU DNN (2) with respect to the weight matrix in the hidden layer at random initialization. Note that e R= Then,
[2019]. NTK matrix of DNN is a L-times recursively defined n
when l = 1. Vw, [-) E mxd and when l {2...., L}. [fw (-) as m - 0C.
1 m Σ V [f Vw Vwe (w.(fooo)(x)))),
H(0):
H
nxn
where H말 = [er((x; (x; x,) i- > Here, Ker(s.) denotes a NTK function of (2) to be defined as follows:
Definition 3.1. (NTK function of (2)). For any x, x' E X and l E [L], define
$ (0) Xx x') = (x,x',
( (x, x') (((-11) (x
(xt-1)(x,x)
E R22x
11(e-1)
(x,x)
((C-1) 1) (x'x'))
1 (x, x') =
E
(a(u) (v)), and
(1.
E (0) xxxx') (1.
[ā(u): (v)),
where d(u) 1u 2 0). Then, we can derive the final expression of NTK function (2) as follows:
Ker(x, 2
1 (x,))))
II (5 (xxx) E'
(8)
The expression in (8) is adapted from Cao & Gu [2019]. As remarked in Cao & Gu [2019], coef- ficient in (( and $(9) remove the exponential dependence on the network depth in the NTK function. However, when compared with the NTK formula in Cao & Gu [2019], (8) is different from two aspects: (i) An additional factor in (8)) comes from the difference in initialization settings of the output layer, in which Cao & Gu [2019] considers vú ~ NO, 1,) whereas we consider
ny .O, )) (ii) (LL) is not added in the final expression of (8)), whereas it is added in the
5

---

Published as a conference paper at ICLR 2022
definition provided in Cao & Gu [2019]. This is because only train the L hidden layers but fix the output layer, while Cao & Gu [2019] train the entire layers of the network including the output layer.
As already been pointed by several papers, Cho & Saul [2009] and Jacot et al. [2018], it can be proved that the NTK function (8) is a positive semi-definite kernel function. Furthermore, Cho & Saul [2009] prove that the expectations in & and & have closed form solutions, when the covariance matrices have the form (1 with [4] S 1:
1
E (0,))~((0,0000
[o(u) [[))]
1. ( arccos(t)) (rrcccoos))) + VI- -1-
2T
(9)
E (0,0)~)((0
[ō(u) o(u)]
(T arccos(t)).
2m
Clearly, (8) is symmetric and continuous on the product space X' x X, from which it can be implied
that Ker(-..) :) is a Mercer kernel inducing an unique RKHS. Following Ghorbani et al. [2020], we define the RKHS induced by (8)
Definition 3.2. (NTK induced RKHS). For some integer E N, set of points 18 C X, and weight vector == {ai....., pp} E IR", define a complete vector space of functions, f X + R.
P H = dl ((1()==) Σ KarKer (or())()))))))
(10)
==1
where cl(.) denotes closure.
In the remaining of our work, we assume the regression function fx(x) = E[y[x] belongs to H
3.1 ASSUMPTIONS.
In this subsection, we state the assumptions imposed on the data distribution with some remarks.
(A1) px is uniform distribution S == {x Rd ||*|| 1}. and noisy observations are assumed to be bounded. (i.e., Px Unif y. y; O(1), Vi e [m].)
(A2) Draw n i.i.d. samples {xi, (x:)] from the joint measure p. Then, with probability least 6, we have Amin H = Aoo > 0. Remark 3.3.
When the feature space is restricted on the unit sphere, the NTK function in (8) becomes rotationally invariant zonal kernel. This setting allows to adopt the results of spectral decay of (8) in the basis of spherical harmonic polynomials for measuring the complexity of hypothesis space, 72 See the subsection 3.2 and references therein.
Assumption (A2) is commonly employed in NTKK related literature for proving global con- vergence of training error and generalization error of both deep and shallow neural net- work, Du et al. [2018: 2019]; Arora et al. [2019a]. Note that the (A2) holds as long as no two x; and x, are parallel to each other, which is true for most of the real-world distribu- tions. See the proof of this claim in Du et al. [2019].
3.2 MINIMAX RATE FOR RECOVERING f E HNNK
The obtainable minimax rate of Le Le-prediction error is directly related with the complexity of func- tion space of interest. In setting, the complexity of RKHS HNTK can be characterized by the eigen-decay rate of the NTK function. Since Ker(x, x') is defined on the sphere, the decomposition can be given in the basis of spherical harmonics as follows:
N(d.k)
Ker(x, x') = Σ mk Σ (x)(())
R=0
j=1

---

Published as a conference paper at ICLR 2022
where Yk.j. I..... Ndd, k) are spherical harmonic polynomials of degree k and { 1 are non-negative eigenvalues. Recently, several researchers, both empirically [Basri et al., 2020] and theoretically [Chen & Xu, 2020: Geifman et al., 2020; Bietti & Bach, 2021], showed that, for large enough harmonic function frequency k, the decay rate of the eigenvalues Uk is in the order of (kk-)) 4. Given this result and the fact N(d, = 2k+d-3 (k+d-
grows as kd-2 for
d-2
large k; it can be easily shown Xj- = -jj==')) when xer(x,x') = 2j=1 (x))(x) for eigen-values A 2 A2 2 ... 2 0 and orthonormal basis {0t { Furthermore, it is well known fact that if the eigenvalues decay at the rate X, O(j-2)), then the corresponding minimax rate for estimating function in RKHS is O(n IP+I
2y [Raskutti et al., 2014; Yuan & Zhou, 2016; Hu et al., 2021]. By setting 2v = 2-1' we can see the minimax rate for recovering S3 E 2 is O =d=
d
Remark 3.4. We defer all the technical proofs of the Theorems in subsections 3.3 and 3.4 in the Ap- pendix for conciseness of the paper. We also provide numerical experiments which can corroborate our theoretical findings in the Appendix A.
3.3 ANALYSIS OF UNREGULARIZED DNN
In this subsection, we provide the results on the training loss of DNN estimator obtained via mini- mizing unregularized fz-loss (3) and on the corresponding estimator's L2 Ez-prediction risk R(f
Theorem 3.5. (Optimization) For some ō E [0, set the width of the network as
m
(m))
8( wnn" inn= A ). and set the step-size of gradient descent as 17 = (x74tmm)) Then, with probability at
least 1 - E over the randomness of initialized parameters Wi()) = { (w W Tem with w( we have for k 0, 1,,,2.....
L++
L+1 = v,
Ls (s(())) S ((10))(11101
1mmmmdo)) &
Ls (MVi)))
(11)
2
In other words, the training loss drops to 0 at linear rate.
We acknowledge a series of past works Allen-Zhu et al. [2018]; Du et al. [2019] have similar spirits with those in Theorem 3.5. However, it worth noting that their results are not applicable in our problem settings and data assumptions. Specifically, the result of Du et al. [2019] is based on the smooth and differentiable activation function, whereas the Theorem 3.5 is about the training error of ReLU activation function, which is not differentiable at O. Furthermore, the result of Allen-Zhu et al. [2018] relies on @-separateness assumption stating that the every pair of feature vectors {x,, xj } cff is apart from each other by some constant @ > O in Euclidean norm. In our work, the positivity assumption on the minimum eigenvalue of the NTK is imposed (i.c., Aoe > 0).
Remark 3.6. Reducing the order of network width is definitely another line of interesting research direction. We are aware of some works in literature, but we chose not to adopt the techniques since this can make the analysis overly complicated. To the best of our knowledge. the paper that most neatly summarizes this line of literature is Zou & Gu (2019]. See the table in page 3 in their paper. The order of width they obtained is 21 (=",²²) where they impose e-separateness assumption. 63
Remark 3.7. There has been an allempt to make a connection between the positivity and Φ- separateness assumptions. Recently, Zou & Gu [2019] proved the relation Aoe = 22 5 in a shallow-neural net setting. See Proposition 3.6. of their work. However, is still an open ques- tion on whether this relation holds in DNN setting as well. The results in Theorem 3.5 suggest positive conjecture on this question. Indeed, plugging the relation Aso (n 2) in (11) and in
the n = ( n 1.
yield the discount factor (1-9(2me) umd) k and step-size 1) 0 (,....)) which
'In shallow neural network with ReLU activation without bias terms, is shown that μu satisfy poo > 0. Me = if h 2j + 1 with; j 2 1, and otherwise μ4 O (k--), See Bietti & Mairal [2019]. However, in ReLU DNN, it is shown that these parity constraints can be removed even without bias terms and μ4 achieves ((- decay rate for large enough kt. Readers can refer Bietti & Bach [2021] for this result.
'ee conjecture that this is not the tightest lower bound on X Recently, Bartlett et al. [2021] proves that A E d/n in shallow neural net setting. See Lemma 5.3 their paper.
7

---

Published as a conference paper at ICLR 2022
exactly the same orders presented in Allen-ZIo et al. [2018]. See Theorem 1 of their ArXiv version paper for the clear comparison. We leave the proof of this conjecture as a future work.
Theorem 3.8. (Generalization) Let J' E C,Y, Fix a failure probubility å E [o, 1]. Set the width of the network as [mg)(m)
2( (0="n0 the step-size of gradient descent as b 0 ( I. ) 15
Then, if the GD iteration k 2 Q 1/11 or k v ( (mm))) with probability at least 1 over the randomness of initialized parameters W(O) we have
and the variance parameter S
log(n))
R =
This theorem states that if the network trained for too long or too short, the L2-prediction error of Swas is bounded away from 0 by some constant factor. Specifically, the former scenario indicates that the overfitting can be harmful for recovering J2 H given the noisy observations.
Remark 3.9. Readers should note that the Theorem 3.8 does not consider if the GD algorithm can achieve low prediction risk (((xff)) over the range of iterations (1m76))-1 X k S ( In the numerical experiment be followed Appendix A, we observe that for some algorithm iterations k", the risk indeed decreases to the same minimum as low as the lz Vz-regularized algorithm can achieve, and increases again. This observation implies that the unreg- ularized algorithm can achieve the minimax rate of prediction risk. However, analytically deriving a data- detendennddntt stopping time k* in our scenario requires further studies, since we need a sharp characterization of diee-diittibbtion of NTK matrix of ReLU DNN, denoted H in this paper. Readers can refer the Theorem 4.2. of Hu et al. [2021] in shallow neural network and equation (6) in Raskulti al. [2014] in kernel regression context on how compute k- with the given eigen- values of the associated kernel matrices.
3.4 ANALYSIS OF f2- 42-REGULARIZED DNN
In this subsection, we study the training dynamics of fz-regularized DNN and the effects the reg- ularization for obtaining the minimax optimal convergence rate of Lg-prediction risk. In the results to be followed, we set the orders of model parameters Th, 1/2 in (6), and a variance parameter of output layer, follows:
1 2
1
+
1 m
1/2 e 1
n
O
1 L3/2
(12)
Theorem 3.10. (Optimization) Suppose minimize fg-regularized objective function (5) via mod- ifsed GD (6). Set the network width [og"(m] 2 (
22 24 -/) and model parameters as (12). Then,
vn
with probability at least 6, the mean-squared error follows
(s(W (1-naut) & (s(W)))
(13)
for k > O. Additionally, after k > O, we have
iterations of (6), for some constant
(k())) H Cy
Cu. I
H
y
5 7
(14)
where we denote (k)) = (x1)) Pwrgy (xx.)
Several comments are in sequel. Theorem 3.10 is, to our knowledge, the first result that rigorously shows the training dynamics of fz-regularized ReLU DNN in overparametrized setting. Observe that the first term the right-hand side of the inequality (13) converges linearly to 0, and the second term is some positive constant that bounded away from 0. This implies that the MSE of regularized DNN is upper-bounded by some positive constant. Note that only provide the upper
8

---

Published as a conference paper at ICLR 2022
bound, but the results of our numerical experiments indicate that the MSE is lower-bounded by (1( as well. We leave the proof of this conjecture for the future work.
The inequality (14) states that the trained dynamics of the regularized neural network can approximate the optimal solution (denoted gT,) of the following kernel ridge regression problem:
yh f(xx)) + CH 2 IIff
min FEHNIK
(15)
2
where 1laęT<< denotes NTK-induced RKHS norm. Note that the optimization problem in (15) is not normalized by sample size The incquality (14) states that after approximately (NzuL) iterations of (6), the error rate becomes (+))). The approximation error is computed at the training data points under l2 norm. This should be compared with the Theorem 5.1 of Hu et al. [2021], where they showed that the similar approximation holds "within" a certain range of algorithm in shallow neural network setting. In contrast, show that the approximation holds "after" & 2 (((22)L)) log(n3/2)) in deep neural network. It should be noted that the difference of results comes from the regularization scheme, where we penalize the Σl I w ||p whereas Hu et al. [2021] regularized the term Wills
As another important comparison, Hu et al. [2019] showed the equivalence of solution of kernel ridge regression associated with NTK and the first order Taylor expansion of the regularized neural network dynamics; note, however, that the uk(k) in (14) is a full neural network dynamics. (t) ft) be the Le-prediction risk of the regularized estimator w
Let R(
fwi)
(8) via modified GD (6).
Next theorem states the result of generalization ability of f Swo.
Theorem 3.11. (Generalization) Let f HNTK Suppose the network width Tog [m] and model parameters are set as suggested in (12). Then, with probability tending to 1, we have
2 2
( f2) Oz 20
The resulting convergence rate is O x with respect to the training sample size n. Note that the rate is always faster than 1/2) and turns to be the minimax optimal [Caponnetto & De Vito, 2007; Blanchard Mücke, 2018] for recovering fž E HNTK in the following sense:
lim lim inf inf sup R (f. > rn z = =1, + n-000 f
(16)
where P is data distribution class satisfying the Assumptions (A1), (A2) and fo HDTK and infimum is taken over all estimators D - f. It is worth noting that the minimax rate in (16) is same with the minimax rate for recovering f E HNTK, (i.e., Hu et al. [2021]) This result can be derived from the recent discovery of the equivalence between two function spaces, H.TK = HNTK See Geifman et al. [2020] and Chen & Xu (2020).
Remark 3.12. A particular choice of μ (nnii) in (12) for obtaining an optimal minimax rate for prediction error in Theorem 3.11. Specifically, the order of μ. determines the L2 distance between the f and the kernel regressor 9h. That is, Ilf 1 (). With the result H HNTK the same proof of Lemma D.2. in Hu et al. [2021] can be applied for proving this result.
CONCLUSION
We analyze the convergence rate of Le-prediction error of both the unregularized and the regular- ized gradient descent for overparameterized DNN with ReLU activation for a regression problem. Under positivity assumption of NTK, we show that without the adoption of early stopping, the Izz-prediction error of the estimated DNN via vanilla GD is bounded away from 0 (Theorem 3.5), whereas the prediction error of the DNN via lz-regularized GD achieves the optimal minimax rate (Theorem 1.).). The minimax rate O n .ह)) ) is faster than the Onn11/2 by specifying the com- plexities of target function and hypothesis space.

---

Published as a conference paper at ICLR 2022
ACKNOWLEDGMENTS
This project is partially supported by the Transdisciplinary Research Institute for Advancing Data Science (TRIAD), http:/triad.attcch.o. which is part of the TRIPODS program at NSF and lo- cates at Georgia Tech, enabled by the NSF grant CCF-1740776. Authors are also partially supported by NSF grant DMS-2015363.
REFERENCES
Zeyuan Allen-Zhu, Yuanzhi Li, and Zhao Song. A convergence theory for deep learning via over- parameterization. arXiv e-prints. pp. arXiv-1811, 2018.
Zeyuan Allen-Zhu, Yuanzhi Li, and Yingyu Liang. Learning and generalization in overparame- terized neural networks, going beyond two layers. Advances in Neural Information Processing Systems, 32:6158-61 6169,66666111 2019.
Sanjeev Arora, Simon Du, Wei Hu, Zhiyuan Li, and Ruosong Wang. Fine-grained analysis of op- timization and generalization for overparameterized two-layer neural networks. In International Conference on Machine Learning, pp. 322-332. PMLR, 2019a.
Sanjeev Arora, Simon S Du, Wei Hu, Zhiyuan Li, Russ R Salakhutdinov, and Ruosong Wang. On exact computation with an infinitely wide neural net. Advances in Neural Information Processing Systems, 32:8141-818 2019b.
Peter L. Bartlett, Andrea Montanari, and Alexander Rakhlin. Deep learning: statistical viewpoint. Acta Numerica, 30:87-201, 2021. doi: 10. 10.1017/500024499220000027
Ronen Basri, Meirav Galun, Amnon Geifman, David Jacobs, Yoni Kasten, and Shira Kritchman. Frequency bias in neural networks for input of non-uniform density. International Conference on Machine Learning, pp. 685-694, PMLR, 2020.
Benedikt Bauer and Michael Kohler. On deep learning remedy for the curse of dimensionality in nonparametric regression. Annals of Statistics, 47(4):2211-2285, 2019.
Alberto Bietti and Francis Bach. Deep equals shallow for ReLUU networks in kernel regimes. In ICLR 202 1021-Inae J-nteennatiilll Conference on Learning Representations, pp. 1-22, 2021.
Alberto Bietti and Julien Mairal. On the inductive bias of neural tangent kernels. In NeurIPS 201t-Thirt--hhird Conference on Neural Information Processing Systems, volume 32, pp. 12873- 12884, 2019.
Gilles Blanchard and Nicole Mücke. Optimal rates for regularization of statistical inverse learning problems. Foundations of Computational Mathematics, 18(4):971-1013, 2018.
Yuan Cao and Quanquan Gu. Generalization bounds of stochastic gradient descent for wide and deep neural networks. Advances in Neural Information Processing Systems, 12:10836-10846, 2019.
Andrea Caponnetto and Ernesto De Vito. Optimal rates for the regularized least-squares algorithm. Foundations of Computational Mathematics. 7(3):331-36,, 2007.
Lin Chen and Sheng Xu. Deep neural tangent kernel and Laplace kernel have the same RKHS. In International Conference on Learning Representations, 2020.
Lénaïc Chizat and Francis Bach. On the global convergence of gradient descent for over- parameterized models using optimal transport. In Proceedings of the 32nd International Con- ference on Neural Information Processing Systems, pp. (040-3050, 2018.
Youngmin Cho and Lawrence Saul. Kernel methods for deep learning. Advances in Neural Infor- mation Processing Systems, 22:342-350, 2009.
Simon Du, Jason Lee, Haochuan Li, Liwei Wang, and Xiyu Zhai. Gradient descent finds global minima of deep neural networks. International Conference on Machine Learning, pp. 1675- 1685. PMLR, 2019.
10

---

Published as a conference paper at ICLR 2022
Simon S Du, Xiyu Zhai, Barnabas Poczos, and Aarti Singh. Gradient descent provably optimizes over-parameterized neural networks. In International Conference on Learning Representatiins, 2018.
Amnon Geifman, Abhay Yadav, Yoni Kasten, Meirav Galun, David Jacobs, and Ronen Basri. On the similarity between the Laplace and neural tangent kernels. arXiv preprint arXiv:200..01580, 2020.
Behrooz Ghorbani, Song Mei, Theodor Misiakiewicz, and Andrea Montanari. When do neural networks outperform kernel methods? arXiv preprint arXiv:2006. 2020.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Delving deep into rectifiers: Surpassing human-level performance on Imagenet classification. In Proceedings of the IEEE international conference on computer vision, pp. 1026-1034, 2015.
Tianyang Hu, Wenjia Wang. Cong Lin, and Guang Cheng. Regularization matters: A nonparamet- ric perspective overparametrized neural network. In International Conference on Artificial Intelligence and Statistics, pp. 829-837. PMLR, 2021.
Wei Hu, Zhiyuan Li, and Dingli Yu. Simple and effective regularization methods for training on noisily labeled data with generalization guarantee. In International Conference Learning Rep- resentations, 2019.
Arthur Jacot, Clément Hongler, and Franck Gabriel. Neural tangent kernel: Convergence and gen- eralization in neural networks. In NeurlPS, 2018.
Ziwei Ji, Justin Li, and Matus Telgarsky. Early-stopped neural networks are consistent. Advances in Neural Information Processing Systems, 34, 2021.
Yongdai Kim, Ilsang Ohn, and Dongha Kim. Fast convergence rates of deep neural networks for classification. Neural Networks, 138: 19-1977 2021.
Michael Kohler and Adam Krzyzak. Over-parametrized deep neural networks do not generalize well. arXiv preprint arXiv: 191..0392,.0.... 2019.
Пí Kuzborskij and Csaba Szepesvári. Nonparametric regression with shallow overparameterizee neural networks trained by GD with early stopping. In Conference on Learning Theory, pp- 2853-2890 PMLR, 2021.
Jachoon Lee, Yasaman Bahri, Roman Novak, Samuel S Schoenholz, Jeffrey Pennington, and Jascha Sohl-Dickstein. Deep neural networks as Gaussian processes. In International Conference on Learning Representations, 2018.
Yuanzhi Li and Yingyu Liang. Learning overparameterized neural networks via stochastic gradient descent on structured data. In NeurIPS, 2018
Ruiqi Liu, Ben Boukai, and Zuofeng Shang. Optimal nonparametric inference via deep neural network. arXiv preprint arXiv: 1002x0:902.01633 2019.
Atsushi Nitanda and Taiji Suzuki. Optimal rates for averaged stochastic gradient descent under neural tangent kernel regime. In International Conference on Learning Representations, 2020.
Prajit Ramachandran, Barret Zoph, and Quoc V Le. Searching for activation functions. arXiv preprint arXiv: 2017.
Garvesh Raskutti, Martin J Wainwright, and Bin Yu. Early stopping and poramaraettiic regression: an optimal data-dependent stopping rule. The Journal of Machine Learning Research, 15(1): 335-366, 2014.
Johannes Schmidt-Hieher. Nonparametric regression using deep neural networks with ReL.U acti- vation function. Annals of Statistics, 1874))1875-1897 2020.
Richard Varga. GerSgorin-type theorems for partitioned matrices. In Gersgorin and His Circles, pp. 155-187. Springer, 2004.
11

---

Published as a conference paper at ICLR 2022
Roman Vershynin. High-dimensional probability: An introduction with applications in data science, volume 47. Cambridge university press, 2018.
Colin Wei, Jason D Lee, Qiang Liu, and Tengyu Ma. Regularization matters: Generalization and optimization of neural nets their induced kernel. Advances in Neural Information Processing Systems, 32, 2019.
Greg Yang. Scaling limits of wide neural networks with weight sharing: Gaussian process behavior, gradient independence, and neural tangent kernel derivation. arXiv preprint arXiv:1902.04760, 2019.
Ming Yuan and Ding-Xuam Xuan Zhou. Minimax optimal rates of estimation in high dimensional additive models. Annals of Statistics, 44(6):2564-255) 2592333,,--9,, 2016.
Difan Zou and Quanquan Gu. An improved analysis of training over-parameterized deep neural networks. Advances in neural information processing systems, 2019.
Difan Zou, Yuan Cao, Dongruo Zhou, and Quanquan Gu. Stochastic gradient descent optimizes over-parameterized deep ReLU networks. arxiv e-prints, art. arXiv preprint urXiv:/8/ Ttt::/8/1..88000 1.08888, 2018.
Difan Zou, Yuan Cao, Dongruo Zhou, and Quanquan Gu. Gradient descent optimizes over- parameterized deep ReLU networks. Machine Learning, 109(3):467-492, 2020.
12

---

Published as a conference paper at ICLR 2022
A
NUMERICAL ILLUSTRATIONS
(a) Optimization
(b) Generalization Error
Generalization Error
0.6
0.15
100, Unieg
300
p- Reg
0.15
Error
550
0.14
1000
Predictoo RES
0.4
Preditionn llee
0.12
0.10
0.3
0.08
Moin
0.06
0.1
200
400
600
800
1000
200
4.00
600
800
1000
1000
2000
3000
4000
5000
Epochs
Epochs
Sample Size
Figure I: Results on synthetic data.
In this section, we use synthetic data to corroborate our theoretical findings. We use the He initialization [He al., 2015] and employ (&2 (egurauul))) GD introduced in subsection 2.2. For the experiments, run 1000 epochs of GD and use fixed step size, setting and generate y; from (x! with
7/2 = 0.001. We
uniformly generate n feature data x; trin from Sd-1 with
Ex ~ (0, 1). To create a function f E H. we use the definition in (10) with E U and with p fixed points { C 1 where p is simply set as 1. Note that Ker(:)) in (10) can be calculated via the formulas (8) and (9) with specified network depth L. We consider a scenario where have network with depth L and width 2000. The variance parameter of the output layer (w) is set as for unregularized and 0.001 for regularized cases.
In Fig I.(a), we record the training errors of regularized networks over the GD epochs k < 1000, where we have E {100, 300, 500, 1000, 5000] training samples. This aims verify the inequal- ity (13) that the MSE of regularized network is bounded away from 0 by some constant. In Fig I.(b), the prediction risks of both unregularized and regularized networks are displayed. We approximate the risk with I Σラ=1 (fu())"))) f (x)")) ))² with a new test data set {x|tat, f
(x))=) ))550 over < 1000 for both unregularized and regularized cases. In both cases, they reach the same minimal risks, but the risk of unregularized network increase after it hits the minimal point, whereas the risk of regularized network stays stable. Theorem 3.6 tells us that for the iteration less than the order O( ) the prediction error is bounded away from 0. In the experiment for unregularized case, we set 7) = 0.01, m 2000, L 8, and w 1. Plugging in these parameters in the bound says that the minimum can be achieved within a very few iterations. Note that the optimal risk is non-zero as long as we have finite sample sizes n, but converges to the rate O(n z--)). In Fig 1.(c), we verify that the more training sample sizes we have, the closer the risks of the regu- larized networks get The risk is evaluated at the sample sizes n [100,300, 500, 1000, 5000).
500
We have to acknowledge that there is discrepancy between our experiment setting and the- ory. Specifically, due to the limited computing power, could not the experiment under the regime of width (mg) by our theorems, which can be a partial evidence that the statement in theorems still holds in the narrower width of the network.
m
2( ("""",
>e 82 ). But the prediction risk behaves similarly as expected
B PRELIMINARY NOTATIONS
Before presenting the formal proof's of Lemmas and main results, introduce several notations used frequently throughout the proofs. First, we denote Xx,; the output of the 9th hidden layer with the input data x; after applying entry-wise ReLU activation function.
X (Wro oa WW-1- ... a (W (xx))...)) ..)))
Denote (w) value of neural network (2) evaluated at the collection of network parameters ((k) (W(()) Je and w denotes the 9th hidden layer parameter updated by keth GD
13

---

Published as a conference paper at ICLR 2022
iterations.
Partial gradient of fw(() (z). We employ the following matrix product notation which was used in several other papers [Zou et al., 2018; Cao & Gu, 2019]:
[A, Ar, Ae, if l 12 otherwise.
11
A,
(17)
I
Then, the partial gradient of (w(2)()) with respect to w for S S I. has a following form: for i E nL.
Vw, (fw()))))) vm.
Xi-1.
(K)
II D
w(
E
(k)
e [4]
(R) where Σ(6e] == Diag (( (,1 x x(11)) 2 ,),,..,I(((!!!) x 2 0)) E mm and wij
t.
denotes jth column of the matrix W()) (K)
Gram matrix H(k.. Each entries of empirical gram matrix evaluated at the kth GD update are defined as follows:
1 Σ (Vw, [/w,(/())(x)))] Vw, (wwc)))))))
H (b)
Note that H(0) > H m oo which is proved in Jacot et al. [2018]; Yang [2019]; Lee al. [2018]; Arora et al. [2019b].
Perturbation region of weight matrices.
Consider
collection of weight matrices
W (We) such that
W E B(w(()))) .)) = W. I/ 1 ve e
(18)
For all E [I....,n} and I..... L. we denote Xt,s and Xe,s as the outputs the L-th layer of the neural network with weight matrices W and W, and Σg, and Σe, diagonal matrices with (Ee.),, = ((w x.) 2 0) and (Ee,)) i3 = (( i 1.) 2 0). respectively.
C WHY IS IT HARD TO PROVE W
(k) Dæ
w < O())
In this subsection, provide heuristic argument why it is hard prove || (k) (1), where (() regularize solely on the model parameter, instead the relative to the initialization. In this case, can write the update rule as follows:
w p.ella I
D.t
D. is the model parameter of ćth layer in kth iteration of algorithm. Here,
(k) (k) D (1 - T2F) w D.t
7n Vw, (Ws((W
V1 < SESL
and Vk 2 1.
(19)
(k) By recursively applying above equation (4.3), can write (k) D with respect to W (0)
D. follows:
w (k) D. (1 72/4 w (0) D.E. m
(1- )atn VV [s (W(--t1)))
t=
Then, we can control the bound as follows:
| (8) D
())
D.ela 12 1- 11-11 maa)) () ||
71
Vw, [Cs (1----1)))
max
Taf t
14

---

Published as a conference paper at ICLR 2022
We know under the initialization setting in our paper, [[ D.ell2 O(1) with high-probability (see Vershynin [2018]), and as long can prove the fo-norm of gradient is bounded, then can conclude |W D w D & O1). However, we are not aware of works which they control the size of || Vw, C& (W where the non-convex interactions between model parameters across the hidden layers allowed. To the best of our knowledge, know the work Allen-Zhu et al. [2019] deals with the three layer case under this setting. But we need further investigations on whether the techniques employed in their paper can be generalized arbitrary L-hidden layer setting.
(k)
D USEFUL LEMMAS
A simplefact Suppose vj expl [mm)) 11v12 (ww).
Lid NO,,, =) for j E [m]] Then, with probability at least 1
( =) j E [m]] where ||,,, denotes sub-exxonential norm, Bern- stein's inequality for i.i.d. centered sub-exponential random variables can be employed For any t t2 O,
Proof. Since v3 v1
P
2t
2xx (-
--emin
(20)
m j=1
max,
[V3 v
where O is absolute constant. Note that used the fact centering does not hurt the sub- exponentiality of random variable. Choosing t = (w) concludes the proof.
Lemma 4.1 (Lemma 7.1. Allen-Zhu et al. [2018]). With probability at least 1 O(L)) (0)
expl-S(m/L)) L)), 3/4 < [|x l|a s for all (I....,n) and & (1,...; L..
Lemma 4.2 (Lemma B.1. Cao & Gu [2019]. If < [/) ")), then with probability at least 1 - O(nL) expl- 2(m L), 1/2 < |Bæ I 3/2 for all W E B(W(0), T), e (1..... n} and E (I.......)) L).
Lemma 4.3 Allen-Zhu et al. [2018]). Uniformly over i E (1.....,n} and < s l2 S I, the following results hold:
1. (Lemma. 7.3, Allen-7hu et al. (2018]) Suppose m 2 2[nT then with probability at least, 1 (nL2) (xxp--2(m7211))) L)],
πI r=
Σ
sO(VL).
2
2. (Lemma.7.4, Alen-ZZh et al. (2018]) Suppose m 2 (nnnI then with probability at least, 1 (nL) exp! exp[- (Q(m/L)
(
L
v
II
W
50(v1).
3. (Lemma.8.2, Allen-Zhu et al. (2018)) Suppose S (l. For all W B(W("),7) with probability at least, 1 - 0 expl- L)},
X
< OT Vlog(m)).
11.4
4. (Corollary.8.4, Allen-Thu et al. [2018]) Suppose S OT..-(9/(0g////// (/000//)))()))))) then with probability at least, 1 O(L expl 2 ESn
(0)
5 50mmr2/3L)
15

---

Published as a conference paper at ICLR 2022
5. (Lemma.8.7, Allen Zhu al. [2018]) For all é E [L]. let En |-3, 3|mxm be the diag. onal matrices with at most ( L) non-zero entries. For all W E B((10) where O f.ss), with probability at least 1 0 ( expl- log(m)))
L (E + 2/3 Wrs
vJ
II
(E + +2/1 v
II r=fit1
Σ w
r.
r=1+1
$ 0 log(m))
Lemma 4.4 (Lemma B.3. Cao & Gu [2019]). There exists an absolute constant such that, with probability at least 1 - (nT22) expl 2 2/3)2 E 1,..., and & E .,.... I, and for all We E (( r). with r v KL "LL=%(loggo [log(m)] holds uniformly that
Vww,ff (w - <O(w/))
Lemma 4.5. Suppose W E ((W .)) and S 1 [lo(((mm))) For all u E 18 with cardinality Ilullo I s, for any - & 4 L and i E fl.....
......, n). with probability at least ([L))
exp ( - 22s log(m))) - OnI.) exp ( (mmr2/11)).
ws (ms))(mm)
II W S
(1uu12).
m
Proof. Recall Lemma 4.2. For any fixed vector a Rm with probability at least 1 - O(Il.) (0m=-2mmm2/// L)] for (0g(mm)) for any 1 s é & L and i (1....,n), have the event T,
1 ( E.. Wry vl
</112|22-
(21)
Conditioned on this event happens, it easy to see the random variable v (II Eng Wr.)u [/]ll)). Based on this observation, we have the probability,
SG
Sw
P(
ws log(m)
P
T
E W E r=
r.s
u 2
(11ul2))
T
II S
ws log(m)
O ((lul12) (T) + +P(TO)
w
2
m
r=t
I ((LL) exp
U log(m))) + O(L)) exp ( - 2(m72/31) L)),
where in the last inequality, union bounds over the indices and i, and over the vector u E R" with [allo S taken.
Lemma 4.6. Suppose S (om)"]og[()) for some constant C > O. Then, for all i E [n] and l E [T), with probability at least (nT.) 2(pp-(((m22/3)))) we have
Vw. [fwoo s s0(71317 /wm (og(m))))
16

---

Published as a conference paper at ICLR 2022
Proof. By using the results from Lemma 4.3, control the term
VW, [x,] - Vw, [w/[/w/o) ll2
L
=
(k) v X
πI
w
-x,- x
II
E 1
w
r=f+1
1=
S Vm
| (b)
1-1
1l2
v
II
D
(k)
W
(A)
r=t+1
50(>L5/3 /log(me))
so(v@)
+ vm
x
VJ
II r=t-1
(k) W!(k) (k)
vT
II
Σ
(0)
w
1
(0)
r=t+1
20(1)
10
s <0( 71/3 wm log(m))
where, in the last inequality, used the condition on CL 1.
Remark 4.7. Note that the results in Lemmas 6.3 (second and fifth items), 6.4, 6.5, 6.6 are in the setting of by NNO,, = for j E [m].
(k:) and let u(k) == For the notational convenience, in following Lemmas we denote fw(x) (x;) u; [u (k),..., un (k)) for k 2 0. Lemma 4.8. For some ō [0, 1). if (((:log(nT/00) then with probability at least 6, []u(k)]l2 S ( for any k 2 O.
Proof. Recall the Lemma 4.2 stating that
(()) for any input data x; for E [n]. Also x L
(k)
XL ~ ((.,O(w)) Then, recall that Vy ~ NO, =) for j E [m], x2.5 E R and u, (k) = /mv Xx,
have following via simple Markov inequality: for any
P( [1((k)]l2 21)
E [1)]]]]]]
R [[[lu(())12]
O O(vna) n
Lemma 4.9. For some 5 E [0, if m 2 ((T.lo((TT./6)) then with probability at least 1 8, we have
[u(0) y212 - 0 ( 7
Proof. By Markov's inequality, for any 8 0,
B.,w(o.v [|u(0) -yl
( ( y120
y11 21 (111(0)->1b
PP
(22)
12
Note that the expectation in the nominator of (22) taken over the random noise & and initialized parameter WO)), v. We can expand the nominator as follows:
Eg woo vo [|u(0)
v Ew l/ ||]( E. 1lyll 2E, w(o).v y u(o)]
(23)
For the convenience of notation, let y = (x)) (x,)) and e = [e ex] Recall that we have y = =y" + c, and ||>*|3 = O(n). Also note that by Lemma 4.1, with probability at (0)
least 1 OnT..) Samp[-((m//))))) for any 1,...,n | 2 112 O(1). Then, we have random
17

---

Published as a conference paper at ICLR 2022
variable u, (0) /mv Torxxx XL, (O(0, Now, ready to derive the orders of three terms on the RHS of (23).
Ew [(0)]l3 O()),
E. E = E. |ly"11 ||ell2 2y T O(n),
W,, (())) = E,,, (yy + [u()] O.
Combining the above three equalities, we conclude the proof.
Lemma 4.10. Suppose = O av/
For some ā E [0, such that 8 2 ((LL)
expl-Q(mx223) L)}, then with probability at least 6, we have
[H(A) H())l2 S o (1 4/3
log2(m) máxa
Proof. By the definition of gram matrix (k) for any 0, have
H Hi (k) (o)(
www.l//wo/xx))).ww//oo - -WW. Vw, (ww)))))),,,loool333 (w][oooo(2))))) Tr
m
(ww w., [/wro) [w:o0/ Ttl
m
Vw. [wwp:///w///)l/vvv///vv)v)))))) - (wwl/wwco)xxx)) /twp://///
Vw. [f Vw. [fw(() - Vw. [f (tt (x)]ll)
2o
50(F11912//m log
(w.(/w(o|(x)))) V/V.l
Vw. [/wa) - Vw, (wwo//ooxxi))
so(vwm)
(m))
s 5o T/6, 1/3
moX2
In the second inequality, Lemmas 4.4 and 4.6 used, and in the last inequality, T 0 ( plugged in. With this, using the fact that Frobenius norm of a matrix is bigger than the operator norm, bound the term |[H(k) H(O)]la follows:
nyw 7mms
H(k)- - H(O)), < (k) H())) s 5 o log (m)
mdd2
Lemma 4.11. For some 8 E [0, 1]. with probability at least 1-6 8.
H(O))l2 s 0 (0wnI1//2 / log(nL/8))
h
Proof. For some 5' E [0, 1J. set 13/2 v/ 1og(L/6') from Theorem 3.1. of Arora et al. [2019b]. For any fixed j [n]. have
m
IP H H,,((0) so (wt,,110 1/ V 1og(L/68)
2 1 5'
18

---

Published as a conference paper at ICLR 2022
After applying the union bound over all i.j E [n], setting 8 = & and using the fact that Frobenius norm of matrix is bigger than the operator norm, we conclude the proof.
For two positive semi-definite matrices A and B, if we write A = B, then it means A B is positive semi-definit matrix. Similarly, if we write A B, then it means A B is positive definite matrix. With these notations, we introduce a following Lemma.
Lemma 4.12 (Lemma D.6. Hu et al. [2021]). For two positive semi-definite matrices and B,
1. Suppose A is non-singular, then A
B A mas (BA-1) S 1 and A > B 3 Amaz [BA+ 1) < 1, where )mma()) denotes the maximum eigenvalue of the input matrix.
2. Suppose A, B and Q are positive definite matrices, A and B are exchangeable, then A - B AQA = BQB.
E PROOF OF THEOREM 3.5
For the convenience of notation, denote (k)))
(w()(x)) and let u(k)
[ur (lk) .... un (+)]]. In order to achieve linear convergence rate of the training error, [b)())) v12 we decompose the term as follows:
||u[k + 1) 212 |lu(k) + (u(k 1) u(
-l(u(k) 21ا - ( v) (u(k uk)- + ||u(k: + 1) - u(k)l
Equipped with this decomposition, the proof consists of the following steps:
1. Similarly with Du et al. [2019], a term (u(k + 1) - u(k)) is decomposed into two terms, where we denote them as T((²) and 1(()), respectively. We note that the first term I(() is related with gram matrix HKk) and second term (k) can be controlled small enough in & sense with proper choices of the step size and the width of network.
2. A term |lu(k 1) u(+)]l2 needs to be controlled small enough to ensure 2(u(k) -
w) (u(k +))))())) > lu(k + 1) - u(k) ll so that the loss decreases.
3. It is shown that the distance between the gram matrix H(k) and the NTK matrix H is close enough in terms of operator norm.
4. Lastly, we inductively show that the weights generated from gradient descent stay within perturbation region B ((V(()), 7), irrespective with the number of iterations of algorithm,
We start the proof by analyzing the term u(k: + 1) - ukk).
Step 1. Control on u(k + 1) - u(k). Recall (M())) = ((w2, x
2 0) and we
introduce a diagonal matrix (k) "i whose jth entry is defined follows:
(k+1) (k+1)) (w x;,
(K ) = - (b+1)) ((k))
(w
(k+1) (k+1) (w 1,
With this notation, the difference
x x can rewritten via the recursive applications of (k+1) (k)
5(0),
(I+1)
(k)
(M())
(k+1) -
(k) (k)
LL
x L,$
x
S
(x x (Σ/1)) - (w(++1) w( (4)
L
Σ
II
( + x
w((++1)
( (
(b)
(W!++1) -w()))_W(())))) (2)
1=1 r=#+1
(24)
19

---

Published as a conference paper at ICLR 2022
Then, introduce following notations
II
D
II
E(at) wh(t!) (2 + -
r=f+1
r=t+1
Now, we can write (k + 1) - (k)))) by noting that u;(k) = mm x
u, + 1) (k) = vm v (x,,
(k+1)
(k)
L
v Σ
w ( - -w(
x/-1,
(K)
(25)
6m1
= --ivm
Σ
(c) t,
Vw [cs (Cw () 1;
-mym v
Σ
D
D
Vw. [cs (W(())
8=1
22
Here, (k) can be rewritten as follows:
I 1. -I/m v
(k)(k) w)) Vw. (Ww())())) (x;)] x
t=1
j=1
-1
(ug (k) - wi)
(vm
v D Es
Vw, [w. (x)a
(=1
L
Σ (1)()) - vi)
Vw. [w/[/w(])xx)]] Vw, (F
= =-mn
2=1
-m
Σ
(ug(k) - 45) H,,
j=1
For 2, we need more careful control. First, we pay our attention on bounding the term follows: By triangle inequality, we have
(k)
V/v
(1) D 1. lla
(k)
(k)
| ( [
D
(9)
I1, s V I (k) 1
11 + V
||
(D 2,
(
-
D 23
(26)
We control the first term of the right-hand side (R.H.S) in (26). By the fourth item of the Lemma 4.3, > S 1 for j E [m]. Then, we can plug Σ" D (8) (0) in the inequality of the fifth item of Lemma 4.3. So, the first term of the r. r.
we know (k) Σ (0)
|lo < Ommr2/31.) and (5
R.H.S in (26) can be bounded by (33 / log(m)).
The second term of the R.H.S in (26) can be similarly controlled the first term. Observe that (x)( (()) < 1, then we have (A) (k)
r. F. -=00) S 2 for all j E [m]] Note that by the
definition of Σ r.j we have (5(4) lo
|| 1 [ (k+1) (k) r. [lo < | (b+1)
Σ (0) llo 1o++1 || Σ [ llo <
(mm 2/3 T... Thus, by the triangle inequality, we have || |>
r. + (
(k)
(0) llo 0 (m12/311)
These observations enable us to plug Σ
x + (k)
(0) in the inequality of the fifth item
of Lemma 4.3, and give the bound on the second term as O 1/331/322 log(m)).
20

---

Published as a conference paper at ICLR 2022
We have (D l2 s 0(71/812 loy(m)) Now, we control the 4--norm of the 12a as follows:
S mvmm
T
D 2,
- D
Vw, [cs (W(((W)))))) ا
1=1
Lemma 4.2 (0(
10(1771/3 - log(mm))
< 00 mLL31/33 / log(m)
Vw: (w:
< 0 mmL5/22133 wm log(m)
[C [W
S 0 mLL5/2 v wm log(m)
Σ (uz(k)) - -,,)²
V Vw. (xw]))))))))]]]
t=1
00 1 wm v (lo(mm)
|lu((k) yll2-
(27)
Step 2. Control on llu(k + 1) -u(k)) Recall that by (25), L,;
(k+1)
(k) L,
can be written as follows:
(k+1)
(b)
D
(k) t,
W
- -
(1(+))
xx-1,
(A)
8=1
L
-1
V Vw:
[Cs( (W(()) (K)
t=1
is worth noting that,
Vw. [Cs(((())
Σ
(u)(b)= - -,,V Vw. (x((f(()(xx))) (x,)
=
2
(u,(k) - -2,)² Σ
Vw. (WW())
/=1
O (mmw) |lu(k) v112-
(28)
53 S 1 for all j E [m], so by Lemma A.3 of Zou et al. [2020], we know | O(VL). Combining all the facts,
Also, observe that 1(>!)) + -
conclude:
||u(k= + 1) ukk)]l
(k+1) L
xx (K)
1=1
A 5m/ ||v12
2
x
(k+1)
x L
1=1
smi 1|v12
D
11 ||
Vw. (Cs [[s((()))]]]
||=201111
t=1
<06p2~'1mm3u' llu(k) v12
< <0(p?n2>?m |lu(k) v12
(29)
21

---

Published as a conference paper at ICLR 2022
where in the third inequality, we additionally used the fact ||v O(w) with probability at least exp(-I((m)), and the inequality (28). In the last inequality, we used the assumption w S 1.
Step 3. Amin (K)) 2
Age 2
with sufficiently large m. Denote p(A) as a sprectral radius of a
matrix A. Then, we have
[H(K) - -H ll 2 (H(()) - H
Amin (())) H
2 Amia (H2) Amin (H()))
A0 Xmin (K))),,
(30)
where, in the second inequality, we used triangle inequality, Amin
+
min H
Amin (H:)) By Lemmas 4.10 and 4.11, setting m 2 52 w 8 1 (mn) 230
and Ö
VI
13/3133
S 1, we have
12 I H()) - H()l + (H())) (k) H
H ll2
log"(m)
(og(nL/8)
0
w 4/3
O
w 1,52
wn
mód2
m
log²
w/ 1/3 n/33 1
7/6
md
Axc
$ 2
(31)
Thus, combining (30) and (31) yields that Amin (H():) 2 Aze
Step 4. Concluding the proof. Recall that 1(() mmn (({)( v). Then observe
that
(u(k) v) (
(k) -1m (u(k) 3) (u()(
S 17m Amin H(k)) |lu(k) - v112
A ||(kk) e1
mmm
(32)
We set the step size 77, radius of perturbation region and network width as follows,
Ase
11 = Ω
1²
n
T = O
Vmddd
2 Ω nn 1 log (m) Ag_ 8
With the above settings, we can control the ||u(k: + 1) vl12 by combining (27), (29) and (32) as follows,
||u(k + 1) - - 1012=11ux =|((k) y + (u(k 1) u(k)) (k)) l
=Ilu(k) vl22 27m- (u(k) 3) H())(u(k)) v)
- (u(kk) v) T (k) + |u(k 1) u(k)
- mmmso + O () 1/3 3/3mm Tog(m) On7"n L(m²) ||u(A) v1l
1mmodxx)
|lu(k)) v12
2
22

---

Published as a conference paper at ICLR 2022
So far, we have shown from Step to Step 4 that given the radius of perturbation region has the order O Vima. ), then we can show the training error drops linearly to 0 with the discount factor
(1 2mAx=) along with the proper choices of v) and m. It remains us to prove the iterates w for all l E [4] generated by GD algorithm indeed stay in the perturbation region ((V(0), .7) over k 2 0 with 7 O
NyW
Step 5. The order of the radius of perturbation region. for the proof. The induction hypothesis is Vs E
We employ the induction process
+ 1}. [k
w w
00 | In. 0
Vnmw
nmmdoc
(V 8 S 00 Vmmodoo
nyw
(33)
2
==
First, it is easy to see it holds for s Now, suppose it holds for s 0, 0.....h, Ns, we consider = k + 1.
( - w = Vw. [Cs (C(((()))]))
Σ (u,(k) v0) V 35)
[Fw(a)(zs)]]
=
a V [/Wrcs
Σ (1g(k:) y3)²
S 1) o (Viimw) /2Cs(
S 0 (Vrems
1 17
(34)
where in the second inequality, we used Lemmas 4.4. Note that since it is assumed that w(()) E ((W the Lemma is applicable with m 2 Ω @TwTn 8 1 log (m) X
Simi-
larly, since it is assumed that the induction hypothesis holds for O,...,k. k. we [l((k) v12 I (1 - >m>=>>>)) ([u(()) - v112. This inequality plugged in the last inequality with Lemma 4.9.
By combining the inequalities (33) for s E [k] and (34), and triangle inequality, we conclude the proof:
11, S |W -w!
o Vnmm
Σ (11-
k
mmmdoo
n S so (V33)
0
mvv {
Vmoddo
2
Proposition 5.1. For some d E [0, 1], set the width of the network as m 2 M(w 8 1 log)((1)) and the step-size of gradient descent as 1 O (....)). Then, with probability least ô over the randomness of initialized parameters W(()), we have for k = 0,,1,2.....
u(k) = - (I (u(()) 3) + E(k).
where
[l(()))l2 = (6(1 myridoo k-1 ( 1pm- w 4/3 4/3 d log (m)
Ily u(0)ll2
2
mX2 5
Proof. Define (k)k) = fw(c)) (x;). then we have
u(k + 11 u(k) -ym H(k)(u(H)) v) + I
= =-rm H (u(k) y) -mm (H(k) H H)))()))( (u(k) -) + (())
=-nm H (u(k) v) + e(k).
23

---

Published as a conference paper at ICLR 2022
By recursively applying the above equality, easily derive following for any k 2 0,
u(k) - y (1-mmHH) (u(0) v) mm- t)
(35)
=(()
Now, we want to show (kk can be controlled in arbitrarily small number. First, e(k) needs to be bounded in an & norm:
[|e(k)]l2 & qmm HH H())l [|u(k:) vll2 + |
mm. O (
log (ml m2 0
|u((k) - vll2
where, in the second inequality, 7 o n/a
is plugged in (27). Equipped with the bound on
vindd
[ee(k)ll2 we can easily bound the [|E(A:)]l2 as follows:
H,H) c(k- 1 t)
1-mmHH lle(A: - 1 -1)l2
log (m)
1
mmnd0o
0
1mm n//3
||u(k: - 1- 1) - v112
mx
log (m) m220
(1- mmnos k-1
1 - mpmooo
0
mm 7/6 4/3
[lu(0) ull2
2
t=
h-1
bogg(mo (m) m2 03
mmm 7/6 4/3 L3
|lu(0) 8112
(36)
2
Note that in the third inequality, we used the result from Theorem 1.
PROOF OF THEOREM 3.8
We begin the proof by decomposing the error fw)) (xx) for any fixed x e Uni into two terms as follows:
(w) -f = (x) - (x)) -
(37)
Here, we denote the solution of kernel regression with kernel H& as g (æ), which mini- mum RKHS norm interpolant of the noise-free data set (x,, (x, } To avoid the confu- sion the notation, we write Ker(æ, X) = (Hz x1), H (I, x,)) R" and let y = (x1)........ (x.)))) Then, we have following closed form solution (z) as,
g" (x) = Ker(z, ()( y
24

---

Published as a conference paper at ICLR 2022
With the decomposition (37), the proof sketch of Theorem 3.8 is follows.
1. Note that for any [Z]], have fwa, (ax) (vec(V Vw, [ww()))))]), vee vee(we (W!*)) ))
We can write the term vee vec(W, (W(() with respect to vee (W(") ), HE. and the residual term via recursive applications of GD update rule and the result from proposition 2.1. Readers can refer (38). Using the equality (38), can further decompose A into three terms. That is, A = An + A12 + 113. Then, using the boundedness f2-norm network gradient and the fact that the size of (l5(2))l2 can be controlled with wide enough network, we can control the size of || and || 1a/22 aribtarily small.
2. In the term 22. the 9* is an interpolant based on noiseless data. For large enough data points, 9* converges fastly to f at the rate Or( )
3. Lastly, the Aur the only term that is involved with random error e, and we show that AAull2 is bounded away from 0 for small and large GD iteration index k.
Step I. Control on D1. For n data points (x1, (X1....,X,, xn) and for the 1thh updated parameter W(k), denote:
vec Vw, (fw((a)xxi)) vec Vw, [Frra(tsa))) Note that when f 1, Vw, ([w())(X)) Rmdxn and when 2, ....... L, Vw, [X)())(X]] Rmn xn With this notation, can rewrite the Gradient Descent update rule as
Vw. Vw. [ww[f(()(X)
vee( (e(W((tt)) = vee vee(w(h)) V/V (FWrs (u(k) - y): k 220
Applying Proposition 3.8, can get:
vec w (k))
vec )
vec vec(W(++))) vee (w:())
Σ
Vw. (X) (u(i) - y)
1=
k-1
1-1 Vw. (fw()
Vw. (1
( u(0)) - 17.
17
=
1=0
Vw, [w. (X)) (I) (1-)) u(0)) - n Σ Vwe (W)]((
n
Σ
[w, [w.[frro] (1 (1- (1-mmH2)) u(O)
+ n
1-1
Vw, (X) (1 (y)u)())) + (K).
(38)
First, we control &oom of the first term of g (k) as follows: Note that Vw, (ww/ O ((vvnn (mm) by Lemma 4.4 for 0 < j < k 1. Then, we have
Vw. (fW()
2
1 1/ namm
(0((1-
0
1mmoo 5-1) )(1))
0 mm 4//
log (m)
|ly
m(0)ll2
2
mx2
1=0
n1 11/6 n111/61,3.5/3 5/3
<
/1lg(m))
|ly
-u(0))l
(39)
m323
X 8//6
25

---

Published as a conference paper at ICLR 2022
In the second inequality, ز j(1 amd )d =0(mmm²' is used. Then, we control E--norm of the second term of (k) follows:
Vw, Vw (w.)) - [X) (I (-mmH,7) (y -()))
7
n 77 I mm 12 u00u())12
Vw, (fwL)) Vw, (w (x,,
222 L2 n 12
1 1o
v Vlog(m) ((v)) -y-ufph u0)ll
8//8
5/6 2/3
00
Vlog(m)) 118 u00)l:
(40)
22 82/6
4/3
where in the second inequality, we used Lemmas 4.6 with 0
nva
Vino....
Now, we are ready to control A term. By using the equality (38), we can decompose the term A
Ek-1 as follows: Let denote G₁ Eÿ=o nm mmH Note that for any l [4], fwos(
(vee( Vw. (z)() vee vee vee(w(() (w(+)) and recall that y y" + c. Then, for any fixed E E [Z]. have:
A [vve((Vw, [#)), vee vec(w!")) vecc:)))))eee))))))) Ker(z, X)G Ker(æ, X)G&y
Ker(i, (H -
Ker(x,X) G) (H2.) "Jy" + XAEE
Σ vee V w. (fw( T Vww, [f)(o) Ker(a, x) Gay
+
Σ vec(Vwel(wccs(()) Fww Gay
m
-A12
+
(vec( [fw()) vee (ec(w + vee(Vw, (fw(c(()))))) ((())
(41)
veel Vee(Vw, (x)))) Vw, [f (X) Gau())
m
Our goal in this step is to control ||1 and || |1a/|2 Then, in the third step, we will show ||n ||2 the term, which governs the behavior of the prediction risk with respect algorithm iteration k.
26

---

Published as a conference paper at ICLR 2022
First, we bound the & norm of the first term in A12
b
Gay
vec
VW:
[/w(H)))))) Vw, [[w[o)(X]] Ker(s, x) GRY
m
1
vec We (sw(s)(z))) - vec(Vw (Vw. [fwro] Vw: (wro (X)lle |G
mL
20(111313 /wmm log(m))
Lemma 4.6
so Vunm
Lemmma 4.4
n
(Ww (/W( Vw. (w:[/xo)())))) Ker(ur, xi)
||Gkyll2
L
m
n//6 n L/
log(m) + +0 wn wn 12 o
ToR(nE//2
|G&illa l|yll2
m2/682/6 1/3
w/7/6
log(nL//) wn 12n1/23//
log(m) -111112)) 0
[1rl2))
(42)
1 4/3
Ax
m
where, in the second inequality, plugged 0 ny@
in the result of Lemma 4.6 and used Similarly, we can control the &
Vmbd...
Lemma 4.11. In the last inequality, we used ||Gxll2 I O norm of the second term in A12 follows:
vee (V,, [fw(a(())) Vww, [fwro] [f) GAy Edpe!
veee Vw, [w Vw,, [S (X) 1r |G |
Eiege
so(vwm
so( (o(wm)))
so +
whr/1 Xxo
I 0
|lyll2.
(43)
We turn our attention to controlling || The first term in A1s: Recall that vee w, [[w()(+))) S O(vmw) by Lemma 4.4. Then, the random variable
vec(V [/ (x))) vee(w") ( is simply NN O(w)) for 1 t L. A straightforward application of Chernoff bound for normal random variable and taking union bound over the layer S l < L yield that: with probability least 1 1-8. 8,
vee Vw, [fw() vec(w())
s ((n
s(yvuue { (
1 )1))
(44)
The & norm of the third term A13 can be bounded as follows:
vec Vw, (z))) Vw, (X)
1
vee vec(Vw, [fwr Fw, [ (X)
|| < 0 (na012)
(45)
2
20(ymo)
sol (Wmmm))
27

---

Published as a conference paper at ICLR 2022
In the last inequality, used the Lemma 4.8 and ||Gxll2 ing (39), (40), (44), (45) with [/w(owo]))(]]]] - 50(mmw) we have a following:
(
By combin-
ااالا S Vlvv Vw, [[w(a) vee(w, vee (2)) >>| +| (vec (fwroo (<()))
-
(vcc [fwro] Vw, [/wio]] (X) G)u(()))
+
m
S 0
L 3
+ +
n22/6 n21//6 18/6 y u(O)lle Vlog(m)
wlog log
m 4/3 82/6
n,5/6,2 7/6 1 -u(0)) v /log(m)
nw3322
+ +
+0
m 1/6 7/3 8/1/6
Axo
n 13 13/6
Jy u(0)llz Vlog(m) + +0
n 5/6
L 7/6
l u(0))l2
Vlo((m)
m 4/3
1/381/6
m
1/16120 1/3 7/381/6
nw3/2
O
(46)
Step 2. Control on 42. First, note that there is recent finding that the reproducing kernel Hilbert spaces of NTKs with any number of layers (i.e., 2 1) have the same set of functions, if kernels are defined on Sd-1, See Chen & Xu [2020]. Along with this result, we can apply the proof used in Lemma.D.2. in Hu et al. [2021] for proving a following:
A2ll2 = Oz
(47)
Step 3. The behavior of L2 risk is characterized by the term An1. Recall the decompositions (37) and (41), then we have:
(z) = A11 + (A12 + A13 + A2) = An + O.
(48)
Our goal in this step is mainly two-folded: (i) Control Eg || arbitrarily small with proper choices
of step-size of GD y7 and width of the network m. (ii) Show that how Eg 112 affect the behavior of prediction risk over the GD iterations k. First, note that we have
Ee 11 = E. lly" + =11 < 2(y)) y + 2 11 = (().
(49)
Second, recall Lemma 4.9 and note that over the random initialization, with probability at least 1- 6,
Eg lly - u(0) < O
n 8
(50)
Now, by combining the bounds (42), (46) and (47), we have
Eg ||01| < 3
|12 + || 112 + 2|2))
log(nL/0)
s E
log(m) |1y113
-1y111
mm1/3 1//3 81/3
X2
m
n11/3 1 13/3
lyy
m00)
5/3 I w/3 7/3
1 u(0) 12
log(m)
+0
(mg(m)
m 1/3 x 8/3 81/3
1/3
1/33////33 11/3//31// 81/3
+
X2 82
2 3
log(nL//0)
n 1,///// log(m)) +0
n2/3 1/
5 0
log(m)
m
//3/3/8/384/3
11
14/33////8/// 8//3
+0
+ 0
(51)
22 8
28

---

Published as a conference paper at ICLR 2022
where in the third inequality, we used (49) and (50).
Case I. When l is large, the L2 risk is bounded away from zero by some constant.
Now we control Eg 1 12- Recall the definitions I1
1XESS-1 1x(x) and
Gy = Ei= pm (I ? Let us denote S = =yy² Then, we have
-f J Ker(x, X)
( (Go (Hr) y'y" T ( -Ga- (BE) + G Ker Ker(Xxx))e x)
E. 1
/ JESSN-1 Ker(z, X) Mr (H Ker(X, x)d2
where
M₂- = (I 1m S([ mpm Hm & + (I- (I -I- Hm 4y²
[[I myHH (S (S+ IS+ (I- mmH
(S -
For the algorithm iterations
ln)(n) pmdd
Co with some constant Co > L, we have
(I-nmBH Hm- 3 (1 mm) I exp( hap(-mmaae mm) I cxp(pcCop log(n)) = nCo I.
Since 1 + 11y11² I Cnn for some constant C1, we have
Amax
1 Co
( (z)
1+ |yyl
Co-1 <I 1.
C1
(52)
Co
Using the first item of Lemma (4.12) with the inequality (52), we have
1
- (m-)mHT)*
I x (S + +2)
(53)
Co
The above inequality (53) lead to following result:
(S + z) (I- - )
(S + +I)
n I.
(54)
It is obvious that both (S + -1 (I - )mHH)) and (S)
1 I are positive definite matrices due to (54), and is also easy to see that they are exchangeable. By using the second item of Lemma 12), we have
n
Mr = [[ H)) &
(S (S+ [ (S (1-m))t))))))))))))))))))))))
(S + -)- +I IS)
- [S I)
1
I] + D) [S$
no I + - (S+
1
Co
1 S (1-
Co I
20%
Then, we have
2C A+ (1- A+
1
Eg
A
B z caB,
no
where co E (0, is constant and
A
- Ker(x, (HA) y dz. and B
Ker(z, (H?))
-172ds dx.
Jxesa-1
(55)
By triangle inequality with the decomposition (48) and the bound on Egg ||01[2 in (51), we have:
Eg |Twe 5r === E. | 11 +
2 2 Ee ||اا||
- EE ||012
> C0 B 0
1 0
-
(m poly w, I, 1 )) (56)
2
n
X2 82
X
29

---

Published as a conference paper at ICLR 2022
For the third term in (56), we can choose w S C2 (x 2 for some constant C2 > such that (HF:)
2/3 3
the term can be bounded by en
Similarly, the width m can be chosen large
enough such that the fourth term in (56) is upper-bounded by Ker(; X) above choices of k, w, and m, we can further bound (56):
I Using the
Ker(: X) (HE) 112 0 (-))
B. (w())) f
co
(57)
Note that Eellfa - g013 = Ker (HE) '13 where g" == and Foo denotes the noise interpolator. Then, by Theorem 4.2, of Hu al. [2021], we know that E. Iffc g0 2 cj for some constant o₁ > 0. Then, 8 and finish the proof.
take n large enough such that the term ( is upper- hoper-bounded by
Case 2. When is small, the L2 risk is bounded away from zero by some constant.
Recall the definition of A1 in the decomposition (41),
A 1 Ker(x, G [y +e] Ker(x, y'
Aj Ker(æ, X)Hīy".
(58)
We denote the sigen-decompositionn of the matrix HE > Zi=1 AviiV T, then we can easily see following:
Gx = mpm
Σ
Σ pmmm) mm
Vivi nynk I.
1=0
1=1
By using the above inequality, we have
Eg ||11l
Ker(æ,
ZESS--1
Ker(I, X)y"] dr (eer(-x)1 -0 -
S mr2m2k²
22ES--1
Recall the decompositions (37) and (41), then we have:
Eg [wit - lrd |
Eg | + θ Ker(- X)Hr
IV IV
1
Ker( (on((,))H;7) X) y 112
E. | + 0112
Ker( X) y"
2 A i1 1/2 2F, 11012
2
1
1
1V
Ker( (X) y
17"m²
k2
0 1
2
1
12 mn13 poly w. w.n,L, L, Xox
(59)
For some constant Cj > 0, let & < Ci ()mes such that the second term in the bound (59) can be bounded by Ker(: (H?)
"= For the fourth term in (59), we can choose
I (2m2 2/3 for some constant C² 0 such that the term can be bounded by
Ker(, x) ( y* I| Similarly, the width m can be chosen large enough such that the fifth
term in (59) is upper- bounded by j () (H)) y Ilg- Using the above choices of k, w, and m, we can further bound (59):
Eg - 1 Ker(: X) () (1 o (H)
2 C' 11:1122 o (
(60)
In the second inequality, used (47) with triangle inequality. In the third inequality, we can C take large enough such that the term ( is upper-bounded by 2 || 11 Lastly, by using the assumption that f is square-integrable function, finish the proof.
30

---

Published as a conference paper at ICLR 2022
G PROOF OF THEOREM 3. 3.10-TRAINING ERROR
For the convenience of notation, we denote up.((k) = (wi)) and let up(k) = (k). un))(H)]
order to analyze the training error of lg-regularized estimator, [ -vl2. we decompose the term follows:
| + +) - vll2 = l|u (A + 1) - - (b))) + II(1 - (2HL)un(() - vll2
- 2y - (11-)u))uD((k) (uD(k + 1) (1 - m2nL)uu (61)
Equipped with this decomposition, the proof consists of the following steps:
1. We decompose the decayed prediction difference up(k + 1) (1 NgHL)up (k) into two terms. We note that the first term is related with a gram matrix (k) and denote a second term as I D
2. The term 1 can be further decomposed into three terms, where denote them 2, (k) 3,D and 5.D- The crux for controlling the f--norm of the above three terms is to utilize the results from the Appendix A.4. The applications of Lemmas in the Appendix A.4 is possible, since we can inductively guarantee that ||W W sufficiently small enough for large enough m.
(k)
3. Given the decomposition (61), we further decompose it into four terms follows:
(61) = |1(1 maLT)un(k)) v12 + | + 1) (1 72 (m
T
T
2mm (y - (1 mpLL)uD(() HD(k)(uD(k)
T2
2( -1- mppLupp (k)) (R)
(62)
In this step, we obtain the upper-bound |Ty 2| for 1, obtained in Step 4. 2, in step 3 and obtain the bound on [u + 1) - yll2 with respect to | (k) yll and ||vll2.
4. We combine the upper-bounds of ||T; |12 for
5. Lastly, we inductively show that the weights generated from regularized gradient descent stay within a perturbation region ((V((),, .T), irrespective with the number of iterations of algorithm.
We start the proof by analyzing the term u(k: + - -(1 - (122L)))(()))
(k) Step 1. Dynamics of up + 1) 11-(1-111) 1)-(1112L) up (k). Recall (E)),)) 1 ((WD. x D.c-1, 2
(k)
0) and we introduce a diagonal matrix D. whose jth entry is defined follows:
(w (k+1)
S (0)) be
(I(++)) D,E
(R)
D.e.j DDI-1,1
(w
(k+1)
(++1)
(k) (w (wDj D.1
D.e.j
(k)
With this notation, the difference x DD,,
I can be rewritten via the recursive applications of
(sk))
Then, we introduce following notations
D
1.
1.
D (()
II
D (( Der D.r D.
(K)
D
II
(M)) + 5(0)
w(K+1) D.r
(I)) + (K))
D,t.i =
D.e.i
r=t+1
r=t+1
31

---

Published as a conference paper at ICLR 2022
Now, we can write un, (k: + 1) (k, by noting that un,((k) vm. / (R)
up + +1) (b,((k)
=Vm- v (x.b...
(k)
= =Vm v² t=1
(R) D
W
D2e
-Vm- v
D
(k)
(K) V.. -2a D.e + maw D.b x
D
= =-mvm
Σ
D
(k)
Vw.
[Cs [w (1)
Des
t=1
1,
L
-mmm
D D.et
-D
D
Vw, Vw, (Cs((2 |x >
-T2PY/ T
D (k)
D (k)
(wbb)
w.O. (1)
D.L
D.E
D.E XD
b,b.i
L m m v T
D
D
W
(K) (N)
D.
F=1
1,
+1phy m V
D
(0
(K) D,--1
(63)
DAA
G.D. where in the second equality, we used the recursive relation (24), and in the third equality, modified GD update rule (6) applied.
Furthermore, 1,D,; can be rewritten as follows:
1 (k) 1.D,, = - m
(R)
(uD - Vw: (x)
D
j=1
--
(uD,s(K) - -vi)
vmm
DDD (k)
(K) D.L.i Vw. [S (x,) x D. 1.8
I.
(KD - -15)
Vw. Vw. [wwgg Vw. If (wwg)(()))))
=-m
j=l
=-mn
(kD -y)) (k).
(64)
With ((0) = (-n2pL) (k) and (64), we can rewrite (63) as follows:
uD + 1) - (1- - (kk = -mm Σ (kD -
vz) (D) + (K)
2.D. + 3,D, + I,D,s
(65)
32

---

Published as a conference paper at ICLR 2022
Step 2. Control of the size
2
Let D
D.1
(k)
+
[(k)
3,0,1 + (k)
5,0,1
2,0.n + I.D. + 1 b.
Now, we control the
2
bound on the
Recall that in Eq. (27), we have
2
( S 00
(nnL wm log(m) (lng(k) 3/122
(66)
(2) 3.D 2
Similarly,
can be bounded:
3.D
(1)
(k) 3,
I T2uVm
Σ
v
((k Dei
-Db.e.
Ww (0)
D.C
D.e
x
D
50(177113 /2w
ST
10(1)
< <0 12 wm log(m)
(67)
(k) s,D
Lastly
can be bounded:
(k)
5.D
2
1=1
12//mm
Dee
(b)
w
(b)
D.E
D.
+ +
72 m
D
(M)
DeL.
w
D,E
x
x.
t=1
1=1
8=1
$ nauL
(k))((b)ll mouurm
|v||
(k) D
/
-w
(0)
(x)
(k)
D.L.s
D.e
50(v
So(VE)
St
50(1)
<0 manun /oogm//wlog(L/))) + 0 m2uun
3/2 m/w
(68)
where in the last inequality, employed the same logic used in (44) with the Lemma 4.2 to obtain the upper-boun on the [kk) We set the orders of the parameters μ4, th T2, T, and w as follows:
d-1
1
3d-2
ad
θ
n2
24-1
11
θ
24-1
112
θ
7
24-1
m
LVw
T= O
0
2
(69)
/moo"
1,3/2
Plugging the choices of parameters (69) with sufficiently large m in (66), (67) and (68) yields
1 so
137/12 <
ad-e Iog(m))
(k)p(k) - vll, + Or
(70)
m 1/681/3
7ス
Step 3. Upper-bound of [T]|| on i 1,2,3,4
First, work getting the upper-bound Amax (HD())). By the Gershgorin's circle the- orem [Varga, 2004], we know the maximum eigenvalue of symmetric positive semi-definite matrix upper-bounded by the maximum absolute column of the matrix. Using this fact,
33

---

Published as a conference paper at ICLR 2022
bound the Amax (HD(k)) as:
Amax
HD(())
Σ
H (k)
Vw, (f (x))] Vw, [ (3)
max
==
t=1
Vw. [f (xx)]
(xx)
(wo
max
m
1=1
50(ymw)
5o(ymL)
S
<O(TTw).
(71)
Recall the decomposition (62). Our goal is obtain the upper-bound on T, for i = 1, 1, 4.
Control on T₁. By using the inequality 21 (1-2)uL))) T (y-w )auL)² |yy - (A))l we have
nauu 11l12 12
lly - (1 (t-mppL)u (1) = 1|(11 - m2 uD(k)) + 72HLy|1
=1 12plT²² 2 11y (b))) 1221² I.2 ||
+ +2rauI(1 111111000 m2pL)y (v- un ub))
(121ll + +13 I1v122 (1 + m22l)) (1 m2pp)) lly uu--up(p) (k)
(72)
Control on Tg. Recall the equality (65). Then, through applications of the Young's inequality ||a + b1ll s ||al12 + |bbl for a, E Rh,"" we have
-mm: mn (k)k((un())))) v) +1/ 1/
[u 1) (1 mapL)un (+)
S 2mm211 2 Amaa >mnx (H)( 11 (b( +2 | 2
2 (73)
Similarly with T2 and T2, we can control Ty and T4 as follows:
Control on T3. Recall (k) is Gram matrix by definition. Then, by using the fact Amio (HD(k) and Cauchy-Schwarz inequality, we have
2mmm (y- - (1 (2D H (k) - v)
2mm (1 Ma un (1:) (k) - uD(K)) + (2mmunull) y (uD y) < (2mm)/auL)) Amaa (k)) IIv - up ( + (2mm)nauL) (HD)))))))))))))))))))))))))) Ilvil2 l1 - (k)
21r0n Amin (k)) || (
(Ammyauu.) >max (H)(k) ||y up 11 (4mmnyul.)) Amax (HD(k)) 11v12- (74)
Control on TT By simple Cauchy-Schwarz.a and Young's inequality, have
2(y (1 - n2nL)uu(()) (/
-21 (72 (v up (k)) T 1 + 2muL y (k)))
< 2(1 - (2He) 11 (k))l (k) ||, + mau 11vll2 + maul (K) 2
(75)
34

---

Published as a conference paper at ICLR 2022
Step 4. Upper-bound of the decomposition training error (62).
Before getting the upper bound of the decomposition (62), we first work on obtaining the bound of (76). Set x = ( and notice yapL = (+)) by (69), then we have
(k) 2 D
+ 2(1 - m2uu)) 11 ( un) [T
|1
+ 7/2 ((0)
(76)
2
|
||2
2 + neuL)
+ +2r (1((1_ 11v - un un (A))l22
ID
2
2
1
122
2 + mepT.
+
1
+ n²211 (1 mauut) u
x22
|T>b
|_
|
+ (1- m2pL) 1 (1)))
+
R²
0 1,37/8n == log(m)
11y up + x²(1 -12b))²
+ x2
O₂
R2
1//382/3
n
S
- ()) I1y un (k))12 + 12pL. 11
(77)
where in the second inequality, the Eq. (70) is used with (a + b)) < 2a² + 26 for a, b E R, and in the last inequality, we used ||y|| (n) and the sufficiently large m to control the order of the coefficient terms of || un (1) Specifically, choose m 2 S2 [[1111 19 log (m)
Now, by combining the inequalities (72), (73), (74), (75), (71) and (77), we obtain the upper-bound on the decomposition (62);
(k + +) -
s 2 + 222 4mmi12uu Amax (HD(k)) -1ee112
+ (1+ (1 11 mmuL)
2m2 Amaax
Amax (H)(k))² + 4mmmmp Amax (HD(k))
ll - uD()))l (2 [2|10>]
[1))
+ +2(1 -2 ub)())l | naul |/ا |
2
372uL n2p²L + o (mmmmmanl))) }} 1lve1i -
(1+ mpL + nEp" **) L1) (1) + +0( (om'mm"n' + +0 (ummnmanl?
1ly - (k)
A- 11 (1 - B) ||y uk(k)
(78)
With the order choices of μ. and 772 as in (69). it is easy to see the leading terms of both A and B are same as n2 ) Then, by recursively applying the inequality (78), we can get the upper-bound on the training error.
ly un(k 1) A. || (1 B) f1y ( k:
A
| (1 - BB) + (1 - -B+++11 - 1p (0)l 1=
A
- B
|1vl + (1 - x+ -|y - (
< O(n) +(1 - k+1 |1y (0)l
(79)
In the last inequality, we used $ = o11. B N nouL and l1s133 = O()).
35

---

Published as a conference paper at ICLR 2022
Step 3. The order of the radius of perturbation region. It remains to prove the radius of n
perturbation region T has the order Op
LV
First, recall that the lz-regularized GD
vm
update rule is as:
W (--1) W D2 (1 7214
(k)
D.E 7n Vw, Ls (WD
[
W2 D VI visesT. and Ak 2
(80)
Similarly with the proof in the Theorem 3.5, we employ the induction process for the proof. The induction hypothesis is
may/m
W De
(0) W
De
S 0o
Vōnau
as E +1.
(81)
It is easy to see it holds for s = 0, and suppose it holds for s 0, .,....h,, k we consider k+ 1. Using the update rule (80), we have
w ((++1) w()) D. b.e
((() D.E
w D.e
Vw. Ls (Ls(W)))))
S 722u
+ m
72/4
(k)
D,E
w ||
D.
+ m
Σ y: (b,, Vw. [w.
mynmm
+
M MVVRmw
V8
m
(O(VT) + -11 +(1-muL)$00
(v²))
n
5
+
0
MVVmm
V8
mmy/m
<
Vōngh
In the first inequality, we use the induction hypothesis for s = k. and Lemma 4.4. In the second inequality, since the induction hypothesis holds for 0, 1..... k, we employ l1y un(k)ll2 I O(vū) + (1 - T2 bly un(0)]; with the Lemma 4.9. In the last inequality, we use 7a/4 < 1. By triangle inequality, the induction holds for k 1. Plugging the proper choices of mh 122 and
suggested in (69) to of n. punn/mww yields
| (k) D.E
W S Op
LV/ Vnn
n2 34
Vonap
H PROOF OF THEOREM 3.10- -E-KENL RIDGE REGRESSOR APPROXIMATION
We present following proof sketch on the approximation regularized DNN estimator to kernel ridge regressor.
1. The key idea for proving the second result in Theorem 3.8 is to write the distance between (k) (where D is to denote the prediction is obtained from regularized GD rule) and kernel regressor B H (Cμ I H -ty in terms of NTK matrix H which is as follows:
(k()) - B = (1- I mmm.HH)) (uD(0) - B) + (D).).
Above equality describes how the regularized estimator evolves to fit the kernel regressor as iteration algorithm goes by.
2. We can bound the f--oomm of residual term (k))) as O(1/n), and show that the & norm the first term on the RHS of equation (4.3) decays at the rate O (00((11)2LL))) Here the /n comes from the bound [BI|2 < O(yn), since we know ||u(0)]]2 has O ((vnw) with small < 1. This yields the claim.
36

---

Published as a conference paper at ICLR 2022
Recall the equality (65). Then, we have
up(k + 1) - (1 7ouL)ub(k)
m (u) -y) + 1, + +,. 5.D
(k)
= -mm H (un(k)-1) -y)
mmn (HD(k) -HE) (ub(k)) - y) + 2,0 + 3.D
5.D
mm H (k)(k) y) + (kk).
(82)
With ( Ly vmm
similarly with Lemma 4.10 and direct employment of the result from Lemma 4.11, we can control the distance from (k) to H under operator norm as follows:
H (k)) 1
(k) H(O))l2
[H
(mg)
log(nL/0)
0
7/6 10/3 n
+ O
n
md²
m
L 19/12 s 0
128-8
log lmg) mdd
0
Ln
184-8 128-8
log(nI/0)
171
log" (m) mo²
L 19/12
128-8
(83)
where in the third inequality, ( 13/3 n I is plugged-in. The last inequality holds with d 2 with large enough n and the condition on width 11 (m)) Then, the & norm of ED (A) can be bounded as:
[kE(())]12 I mmn [HE
HD(k)ll2 [(u 2ll2 +
|
/lo((m)
L 19/1 0
124-5
1/l2
+Op²
m 1/6
n
So(Vn/6)
L 19/12
128
184-7
v (mg(m)
O²
1
O2
(84)
m 1/685/6
n2
n
where in the second inequality, we used (83) with m = 0
1 n
3d
to control the first term and
employed Eq. (70) to control the second term. In the last equality, we used m 2 (( 20 log (m)
82
-1
Now, by setting B == repl. I + 3 for k > 1,
Hy y, we can easily convert the equality (82) as follows:
mm
un (k) -B- B (1-
mm (uD(k- 1) - B) + ED(K - 1).
(85)
The recursive applications of the equality (85) yields
K (k) = -(1- -b--) mm mm H (un(0)- B)
+ Σ (1 m2fuLl I H ED(k-j- - --1 1)
j=
= =(11 =(11-1ju1)) malll) I mm H. b
(nD(0) -B) + (k).
(86)
37

---

Published as a conference paper at ICLR 2022
Now, we bound the lg norm of ep (k) in (86):
k
||e(()]l2 -
Σ
12uL) . I mnHH ED(k j E
j=0
(1 (2jel))) I Hy 1EE - 1)112
j=0
k (1 "2uu11) 115 - 1)11 = o (
(87)
j=0
in the last inequality, we used M2 (+ and Eq. (84). Now, we control the & norm of the first term in (86) as:
(11- mppuL) I mmy H h
(n)(0) B)
I (1 72HL) A |ln - Bll
2
- 0 Vvi(1- maLLL-
(88)
where in the second inequality, we used ||un(0)]|2 3 (Vviw/ and the fact that
napL mm
-1
B|1 <
H.
H
||yl12 S O(vn).
By combining (87) and (88) and using fact (1 D² < exp((-1a we conclude that after
k 2 (((2pL)
((((:uu)"log(((82)))) lo2)n)/2)), the error ann (k) - B decays at the rate (2).
1 PROOF OF THEOREM 3.11
We begin the proof by decomposing the error (ww)(() - fx(x) for any fixed x E Unif(S(-11 into
two terms follows:
W (f)) (z) (x)) + (g)( - (*))
(89)
AD.1
Ap,
Here, we devise solution of kernel ridge regression (x) in the decomposition (89):
gh (x) == Ker(æ, (C I+ H H y.
for some constant C O. Specifically, in the proof to follow, we choose v and 7/2 such that C TzL for the theoretical convenience. Our goal is to show that all the terms ||AD,ı and Tim
2122 have the order either equal to or smaller than Onn==- m, μ4, 771 and 7/2- Since the high-level proof idea is similar with that of Theorem 3.8, omit the step-by-step proof sketch of Theorem 3.11. The most notable difference between the proof strategies of the two theorems is that the regularized DNN approximate the kernel ridge regressor of noisy data, whereas in Theorem 3.8, unregularized DNN approximate the interpolant based on noiseless data.
2d=1) with the proper choices on
Step I. Control on Ap. First, note that there is recent finding that the reproducing ker- nel Hilbert spaces induced from NTKs with any number of layers (i.c., L > 1) have the same set of functions, if kernels are defined Sd-1, See Chen Xu [2020]. Along with this result, under the choice of model parameters as suggested in (69), we can apply exactly the same proof used in Theorem.3.2 in Hu et [2021] for proving following:
|| A
|/ 1 Or ( )
=
(90)
38

---

Published as a conference paper at ICLR 2022
Step 2. Control Ap,1- For n data points (xi,...,x.) xn) and for the h updated parameter (A)
denote:
Vw, [W (X)] = vee Vws [I (w vee Vw. Www./wsy [W (xx)))
Note that when f= = 1, Vw, W (X)] mddxn and when & 2..... L, Vw, [W (X)
Rm3xx xn
With this notation, we can write the vectorized version of the update rule (80)
k R-1
vec (w.))) D.t. vee ( D.
71
Σ
- -)
==
VI vIsesL L and Ak 2 1. Using the equality, we can get the decomposition:
vec vec(WD.)) = vec (W (.
mn Vw, (f X)
Σ
(1
uD (ub(k-j-1) - yy
==
E
E2
k-1
(uD(k - 1) -y
71
Σ 1=0
(1
72113
Vw, Fw.lfwo((s-nn(3)
Vw, (w/
: Ea
(9))
Let 2D,((x) vee w. [ wiy (z)]). and note that f fwoe (z) (2D, vec (o(...) Then, by the definition of AD, and the decomposition (91), we have
AD. = 1 Σ (zD, E, + E2 Ea) Ker(æ, X)
1.
MAL mmm
I H. y
-1
= Σ
(z), (.),E.) En) + Σ
(z), Es)
L t=1
1=1
12211 1/1m
-1 H
(1), E2) - Ker(r, X)
I
y
(92)
First, focus controlling the lg bound on the first two terms in (92). Observe that the first term can be bounded as:
L (x), E1)
S
(ED (x),
(93)
E=1
Then, the random variable D.e) (x) is simply (0, O(w)) for 1 < e L. A straightforward ap- plication of Chernoff bound for normal random variable and taking union bound over the layer 1 < l < L yield that: with probability least 1-
Recall that [[DD)())]22 I ((Vmw) by Lemma 4.4.
(2)) < 2
=0( log ( )
(x) vee w (
(94)
The Ea norm of the second term in (92) be similarly bounded as (93) in addition with the Cauchy- Schwarz inequality:
1 < E
(x), Ex)
(x))
(x),
( Eal
(95)
T.
1=11
E=
39

---

Published as a conference paper at ICLR 2022
The |Ess|2 is bounded as
k-1
(1 nanu" - -Wwl/[,ooxx] (uD(k= - j 1) 31
E3ll2- = 111
j=0
(k m-pp)) Vw, [ww[ - Vw, [w. | 11 - 1)l91
1
Vw, [ - Vw, [w |l - - 1) 2112
(1 T224²
Vw: Vw.(fWD(t----((x)) Vw. (w luD - j - 1) 2112
S m
Σ
(1 m2))
Ww. [wwlfwoodt---((x)) - Vw. www ||u -j j-- - 1) 11 1/12
==0
m 72
/ (0(m)) o ( L3/ wwm (mmmlog(m) -0(V)) S so
1//3///6 m2/381/3 nod-3 Vlog(m)
4d
(96)
In the first, second and third inequalities, we used a simple fact that for the matrix A E Rd xd2 with rank r, then || S || A/|| Recall that the rank of the matrix Vw, [/w (t-)(kk--1))44 (c)]
Vw. [fw (o)((r) (x)] is at most 2. In the second to the last inequality, we use the result of Lemma 4.6 and the [i) ylI2 S (Vv)) for any 2 1. In the last inequality, we plug the correct orders as set in (69) to r, m/. 1/2 and μ.. Back to the inequality (95), using the [I>D,( S (Vymw)
and (96), we can get
L
n (
(120/3/4/3 nd
Σ L
(
Esle S Or
log(m))
(97)
m/13
Before controlling the & norm of C in (92), recall that we set B =
vank I H 91m
Hy y and
the dynamics of (k) B can be expressed in terms of H as follows: For any k 2
up (k) - B = (11 maan) I mm mm (u) -B) + (k)),
(98)
with (b)) S (12). Using (98), we can further decompose the term Eg in (91) as:
h-1
Eg = - == Vw. (x)
Σ (1-
- (1-m
(ub(k-)--))) jj j-- 1))
-)) -
1=0
h-1
k-j-1
m Www (X)
Σ
(1 - (onl (1 (1-nauL) naul)) I - mm HP
B
0=0
R-j-1
- -TVWw//fwo00)/
Σ (1- mau)d (1-mau)
(1-m maucl) I Hm -j -1)
uD
5=
k-1
Σ
(1
n www.wfww.oolf
Σ
(1 nan B BB
1=0
E2 E2 Eg3 Eg.4-
(99)
40

---

Published as a conference paper at ICLR 2022
Then, re- write the error term C in (92) as:
L Σ (x), E2.1) + I Σ
L
1 C I
(E), E222 + I 1=1
Σ (2D,((x), E2,3)
1=1
MuL m1m
(2), E2,1 Ker(x, X)
I + H
(100)
Our goal is control the norm of each summand in the equality (100). For the first three terms in (100), a simple Cauchy- Souuhy-Schwarz inequality can be applied: for i = 2,
Σ
(x), E2,1)
(ED (1)), E21)
Σ ( -1,,,E,,
T.
L
We work on obtaining the bound of E/= |2,,1 12. Let Tk be defined as
k-j-1
nauu" (1- naub) I mm Hy
Ts
j=0
Then, have
L
L
E
l1
m/
Th. Vw, (w Vw. (x, TBB
t=1
=mmiB B
To H(O)B
B
T
H(0) H T&B + mn m
T TE
S <mn [H(0) HE
I| B T mn T H TBB.
(101)
To obtain the upper-bound (101), need control the terms T HTTTE and B TT Let us denote H Ei= Avaay be the eigen-decomposition of H Using 12 S 72/4, note that
k-5-1
T
Σ 1=0
(1
m211) -12ptt)) k-j-1 )2H1I)(-
I
mm H
1 72pL
k-1
1 (1 - m2144)
1-1
mi71 H
77/2
i=0
n
m271 X,)
(1 m2214
(1
m2/4))
1-m34
II.
(102)
mv
X,
mmido
1=0
1-13p
A similar logic can be applied to bound Th TR:
1 mm
21)²
T T 2 (1 12pp))
1-12 >
(1- (1-7/21) 24
(H))
(103)
m² 2
41

---

Published as a conference paper at ICLR 2022
Recall the definition of the notation B = H
Paph
I Hς
y. Then, we bound the term
9mm
B B TrB:
B Th HLB < (1 72/1
24
B
T
(T2) B
12
(1 1/211)
2h
Taul
)'y
y
I
I
H
H
I
H2
m2
111
m
(1 7/211
2h
o
(104)
m2
where the last equality, we used l1stil = Op(1) in (90). Now we turn our attention to bound the term B TB
(1 - 7/2H1)
MAL 11m
2
( (maaL I + H ) y
TBB <
y
+HE
H
m² >22
mim
0 7221) n
26
(105)
12 X
where used ||v1l (n) in the last inequality. Combining the bounds (104), (105) and the result from Lemma 4.11, 11, we can further bound (101) and have:
E2,1 112 < 0(w
(1 -
1211)) 2k
(1 - M2/44 2k
S (1 72/44 2k
n² 1/2
log(n2/8)
mX2
m
(106)
where in the second inequality, we used m 2 12 I 218 6² ) Similarly, we can bound
E
L
L Σ
E2,2112
2 = n
uD(() TT Vw, W.. [XW VV, [w.]]]///[[[// [w.,
t=1
t=1
T6 =mnjup (0) TH ((O))&uu(0)
-mmjup(0)
H(O) H TOuD(() + mn (0) T TE
S <mni |H(0)) H
112 uD(
The 72) mnjuu To HE (uu
(1 77214)
< mmn
wnL
5/2
log(nL/6)
[u)(0)]3
m2n 1,?? X2
+ mm/
(0) (H (D)
m2
(1 M2fl 2k n 2222I51
now (1 - 72/1)) 2k
log(nI./6)
mX2 82
m2 52
nww [1 - 72H4) 2k
Op
(107)
max0
Here, in the second inequality, used the inequalities (102) and (103) and Lemma 4.11. In the third inequality, we used the Lemma 4.8, ||u(0]]22 = O( /nw
8 with probability at least - 8. In the
last equality, we used m 2 Ω 1, 20 log" (og)
42

---

Published as a conference paper at ICLR 2022
Next, we bound E/=1 E2,3 l12 as:
L
R-1
T
k-1
2 2
mnn
Σ 1=0
(1 - m212) (ex-)-1)
(D)
H
Σ
(1 n22) (on-s-1)
1=0
maj n22²
Amaa
(HD(k))
||ok
mnj n222
OwmL)) o ( n22
)
1,3
w.n
2d
4d-3
m
(108)
Now, we focus obtaining the l norm bound D in (100). Recall the definition of the notation
-1
B
TapL I + H
y. simple calculation yields that
92HL
T2HL mil
B B-y-Hī
I H.. y-
I + H2
71m
Then, we can re-write the expression of the D as:
naaul)) mm
k-1
12nt mm
-1 I + H7:
D
71
(ED,((t), Vw, [fwo (x)))
Σ (1 m211
y
f=1
==
Mapil
Ker(z, X)
I + H y
(D)) Vw, [Ww (X)) - Ker(x, x)
I H
mim
(1 1221))
(ED Vw, [w,
I +H
y
11m
(aut 7mm
-1
(z), Vw. [fwo( Ker(x, x))
I HZ
171
1=11
- -(1-m24)
(z), (o][f
I
mauLL mmm
I + H7:
t=1
(nauL I m/mm
+ (1 (1 )2
H2 y, (109)
m
where in the second equality, E/=0 - nours = 1-(1-1u)* is used. The & norm of first term in the (109) can be bounded as:
nan
(
(naull H mim
(zD, Vw, Vw, [f)o(o(())) Ker(x, x)
y
m
2
M2p4e mim
(x), Vw. [w.(fw - Ker(z, x)
I
+
y
2
n1
2
Maaul m/m
-1
(2o(z), Vw. [wrlfwoo,o(())]] Ker(I, xi)
I + H
y
m
0 WnLL5/2 / (og(nL/8)
o mim vn M2L
m
0
wmmmm 1,5/2 y log(nL/8)
O
T.,.//2 2 ा y log log(nL/8)
(110)
T22LL
43

---

Published as a conference paper at ICLR 2022
where, in the second inequality, we used Lemma 4.11, and also used
Maakk mmm
I+ H
y $ $18 2
m2 m71m
I+ H
y
nim² n2u2
llyll
=0(
m
Vn). (111)
MatuL
The &g norm of the second term in (109) can be easily bounded as:
(11
m2211) (1-1)1)
(2)(2), Vwe (o)
IHE 8/
I HE
m
m/m
$ (1 - not1)
Σ
(zo(x)) Vw: (X)]) Ker(z,
(TauLL m11
I H
y
1=1
+
(1 n211)
"er((x,X) X)
I HΣ
1/1m
L
1
(naulli
$ (1 n2/1)*
k
Σ
(20(z)) Vw, (f (x)])
Ker(r: x. x)
I
H²
y
m
mim
t=1
2
rpuu I
+ (1 m211))
Ker(æ,, X)
H
y
1/mm
$ (1 nap)* 0
WWVTL3/2
Lou(nL/8)
mmmm Vn + 0 0(11 (1-
muL
$ (1 na/4)
o
+ O (11 m251) )
(112)
Lastly, the Eg norm of the third term in (109) is bounded as:
(1 - (1-121))) )
Σ
- =D,O(x), =o.d
I
I H2
m t=1
mm
I |
(naull mm
s (1 - (1 - m214)))
(zD - =2 V [[w>:o]
H y
s <(1- - (1 nau)*
(.))
I + H
y
m
mm
s s(1 (1 nau)")
L m
o 1/3 1,2 lmmlog(m) O ((Wmm))
mim
Vn
< (1 (1 m244 )) o w 10/3 3 - v llg(m)
(m)
< O 7//0 1/7/0110// 10/3 3/
1/681/33
m 1/681/3
(113)
where in the fourth inequality, Op ties (110), (112) and (113), we get the bound on |1D|| in (109):
Ly vm
2 is plugged in. Combining the incquali-
| < o 2 1 T
log(nL/8) m log(m)
(1 11-nyy -21))² 0 /W -
log (gg(nL/8) m
o ((1 (1-1122)) --1/11))
wT/ 2/013 +
in 1//82/33
2 00 2,0/3
+t log(m)
0 ((1 72111) 24
(114)
m//382/3
44

---

Published as a conference paper at ICLR 2022
Step 3. Combining all pieces. Recall [12 I OVvmw). With this fact, combining the bounds (94), (97), (106), (107), (108) and (114), we can bound the ||Ap,llg via the decomposi- tion (92) follows:
1 A 112 - L
Σ
(DD( vec (ee()))oe))))))
2
1
E
L
L +
1
E2.1122 + T t=1
Σ
|222 2
|
T.
t=1
t=1
2
Taulle mm
+
(t)) E2,1) - Ker(a, X)
+ H.
L t=1
)
L
2/3/3/4/3
S 0
w log
+ Or
11 10003 log(mL)
m//3
w(1 -7244
2k
nw2 (1 m2pp) 26
L2
Op
+ Oz
+ O= +O=
20
L
LAx
+0
w 20/3
log(mm) m 1/822/3
+ OF: 10=(111)))) m2244)
(1-
50p
n1
45


Reviews:
[{"review_id": "c4uGx5yd-GU", "reviewer": "Reviewer_eixk", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "This paper is well written and shows some novel results. Although I didn't go over all the proof, those theoretical seems correct to me. I also appreciate that the authors provide a detailed comparison with [Hu et. al, 2021] in order to highlight the contribution of this paper. The following are some detailed comments.\n\n1. The condition about $\\mu$ in Eq.~(12) seems a bit strange to me. It basically means that $\\mu$ should increase with $n$ at a certain speed, which is kind of a strong restriction on the regularized factor. It would be nice to see some explanation on why such requirement is needed and how the performance changes when such requirement is not satisfied.\n\n2. I notice that the noise considered in this paper follows i.i.d. Gaussian. I wonder whether the stated theoretical results (e.g., generalization error of unregularized case is bounded away from zero by a constant) are likely to hold for other types of noise.\n\n3. The presentation of Fig. 1(c) is not very clear. Fig. 1(c) is used to illustrate that the prediction risk goes to zero as the number of training samples $n$ increases. However, it is not clear with the x-axis being \"Epochs\". I suggest plotting a figure with the x-axis being the number of training samples $n$.", "summary_of_the_paper": "This paper considers fully connected DNNs with finite equal width $m$ in each layer. Gradient descent is used to minimize the unregularized or L2-norm regularized training error. For unregularized situations, this paper proves that the training error decreases to zero at a linear rate and the generalization error is bounded away from zero by some constant factor if the training process is too long or too short when there exists noise. For the L2-norm regularized situation, this paper provides an upper bound on the training error that consists of two terms, one converges linearly to 0, the other is a constant. Additionally, this paper also proves that the training dynamics of the regularized neural network can approximate the corresponding kernel ridge regression. For the generalization performance of the regularized situation, this paper proves that with enough large width, the prediction risk decreases with the number of training samples $n$ at least at the speed of $n^{-d/(2d-1)}$, which is a little bit faster than the existing results $n^{-1/2}$. Numerical results are provided to support those theoretical results.", "summary_of_the_review": "This paper is a good paper with sufficient contribution. Some minor places could be stated more clearly.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "WuVvOlXk-ej", "reviewer": "Reviewer_XydK", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "Strengths: \n- Theoretical understanding of neural networks, and in particular, the understanding of multi-layer NN, is an important direction of research for advancing deep learning; so while I'm not following the latest literature, I believe this paper has merit along this ongoing line of research; specifically, the line of research leveraging the NTK (Neural Tangent Kernel, i.e., linearized) representation of a multi-layer NN\n- The paper has mainly made technically incremental improvements along existing works, but they have made clear what is their unique contribution and has made good effort in citing relevant work and making comparisons.\n\nWeaknesses:\n- While I would like to trust the technical quality of the current submission, I feel the authors can spend more time on this: \n   - perhaps the authors can summarize the intuition behind each theorem/proof;\n   - perhaps the authors should re-check correctness of their statements/results: In all of Theorem 3.4, Theorem 3.6, Theorem 3.8, and Theorem 3.9, the network width m has a dependence on itself (log m); is this a typo?\n- The practical interpretability of their result is limited: The bound on the network width seems unrealistically high (e.g., n^24, L^20); how does it compare to existing work?\n- Experiments are not very convincing: in the middle plot of Figure 1, it seems that the best un-regularized generalization prediction risk is lower than (or at least on par with) the best regularized one, and that the best result of un-regularized generalization error is achieved with very few epochs. How does this experiment support the result of Theorem 3.6?", "summary_of_the_paper": "The paper made technical contribution along the recent line of theoretical work on DNN: It proves that when data is generated from a nonparametric regression model with i.i.d. Gaussian noise, training (over-parametrized, i.e., wide) ReLU DNN with a regularization term with GD approximately converges, and furthermore that the generalization error decays in order faster than O(1/n^{1/2}), where n is sample size.", "summary_of_the_review": "While the contribution of the paper seems a bit incremental and I am not a hundred percent confident about the technical quality of the paper, I think the paper works on an important topic and has merit to be accepted. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "OphMSkDxsAp", "reviewer": "Reviewer_FGhp", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "Overall I think this paper is well organized and well written. The proof of this paper seems solid. However, I still have the following concerns:\n\n1.  Theorem 3.6 suggests that GD fails if the DNN is trained for either too short or too long. Could you add a comment on whether early stopping is hard to implement in this scenario? \n\n2. Does the regularization sensitive to the hyperparameter $\\mu$? In section 3.3., the authors directly choose $mu = \\Theta(n^{\\frac{d-1}{2d-1}})$. What if we choose $\\mu$ to be larger or smaller than a $log(n)$ factor?\n\n3. Typo: Theorem 3.6 this should be $O((\\frac{\\lambda_{0}\\delta}{n})^{2/3})$", "summary_of_the_paper": "In this paper, the authors analyze the convergence rate of both the unregularized and the L2 regularized gradient descent for a regression problem. Under a positivity assumption of NTK,  this paper shows that without early stopping, the vanilla GD may fail. This can be solved by using L2 regularization and could achieve a better convergence rate.", "summary_of_the_review": "Overall I think this paper is well written, and the proof seems solid. Given Hu et al. [2021], the results of this paper are not that surprising. But the proof technique is different. I still have some concerns. So currently, I would like to suggest a rejection, but I am open to discussion and willing to change my score.\n\n", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "5q2pMnRFCoA", "reviewer": "Reviewer_ytWV", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "The paper addresses interesting and relevant topic. Namely, it is one of few papers which thinks of a neural network learning as a nonparametric problem. This is justifiable as learning is always overparameterized. The question is whether such learning procedure can recover complex regression functions in a presence of label noise, as typically considered in the nonparametric literature. To this end, the paper embraces an NTK point of view and considers regression functions which belong to a corresponding Hilbert space. The paper gives a positive answer to this question and moreover shows that this can be done with an optimal rate. The proof idea is also straightforward: It is well-known that with a right tuning, ridge regression enjoys an optimal rate and so all that is left to do is to establish that deep ReLU networks trained by GD (with regularization) \"track\" predictions of the ridge regressor: This is done in Theorem 3.8.\n\n\nThe paper can be considered as an extension of Hu et al. 2021, who considered a very similar setting albeit with a shallow network.\n\nTechnical details:\n* It is known that interpolants are not consistent in general, e.g. see [1]. It is not clear what theorem 3.6 adds to that.\n* The paper highlights that one of the main technical novelties is a control of the distance parameters travel from initialization, which is $\\\\|W^{(k)} - W^{(0)}\\\\| \\\\leq \\tilde{O}_P(1/\\\\sqrt{m})$ vs $\\\\|W^{(k)} - W^{(0)}\\\\| \\\\leq \\\\tilde{O}_P(1)$ (where $m$ is the width).\nI guess this should be $\\\\|W^{(k)} - W^{(0)}\\\\| \\\\leq \\tilde{O}_P(n/(\\\\sqrt{m} \\\\lambda_0))$ vs $\\\\|W^{(k)} - W^{(0)}\\\\| \\\\leq \\\\tilde{O}_P(n/ \\\\lambda_0)$ (sample size and the eigenvalue are relevant here)? It seems that $1/\\\\sqrt{m}$ comes from the factor $\\\\sqrt{m}$ which multiplies the neural network, this makes its way to Part 5 of the proof of Theorem 3.8 (explanation on page 3 seems to be a bit unclear about that).\nOne detail which is unclear, and would be nice if authors could clarify, how is the factor $\\\\sqrt{m}$ \"balanced-out\" in the part of the proof where you need to track the ridge regressor (second result of Theorem 3.8): It seems to be important because both predictors have to be of the same scale. Is it done by having an extremely small step size of order $1/m$? In most NTK-style proofs this factor is not present.\n* Remark 3.5. $\\lambda_0 = \\Omega(\\phi n^{-2})$ is either extremely loose, or there's a mismatch in normalization. Lower bounds on $\\lambda_0 = \\Omega(d)$ are known under certain assumptions on the input distribution. See, e.g. [4].\n* It is not very surprising that networks can indeed learn regression functions in RKHS of NTK, because such regression functions are essentially by design what networks learn in an extremely overparameterized regime. However, a somewhat more interesting detail is what kind of functions are representable there? In other words, is this RKHS small?\nThere are some works discussing this and it would be interesting if the paper could put them in perspective.\n\n\nSome recent relevant references about nonparametric regression with GD+neural networks not present in the work: [1,2,3,4].\n\n\n\n\n\n\n\n\n\n[1] M. Kohler and A. Krzyzak. Over-parametrized deep neural networks do not generalize well.arXivpreprint arXiv:1912.03925, 2019.\n\n[2] Z. Ji, J. D. Li, and M. Telgarsky. Early-stopped neural networks are consistent, NeurIPS 2021.\n\n[3] I. Kuzborskij and C. Szepesvari. Nonparametric Regression with Shallow Overparameterized Neural Networks Trained by GD with Early Stopping, COLT 2021.\n\n[4] P. L. Bartlett, A. Montanari, and A. Rakhlin. Deep learning: a statistical viewpoint. Acta Numerica, 2021.", "summary_of_the_paper": "The paper proves a bound on the excess risk in a nonparametric regression setting, where the estimator is a deep ReLU network trained by GD with L2 regularization, and the regression function belongs to the RKHS induced by the Neural Tangent Kernel (NTK) related to a deep network.\nIn particular, this work considers presence of label noise and argues that without an explicit regularization such learning procedure is not consistent in general as the network reaches interpolating regime. The paper proposes to use a relative L2 regularization (relative to the initialization) and shows that with an appropriate tuning of parameters the procedure is consistent and yields an optimal rate for regression on RKHS. The proof is heavily based on the NTK machinery, and in particular on the \"coupling\" between predictions of the network and a ridge regressor given the NTK kernel matrix.", "summary_of_the_review": "The paper proves a bound on the excess risk in a nonparametric regression setting, where the estimator is a deep ReLU network trained by GD with L2 regularization, and the regression function belongs to the RKHS induced by the Neural Tangent Kernel (NTK) related to a deep network. This is an incremental contribution w.r.t. Hu et al. 2021. Some technical parts necessary for the proof come from cited works. In this respect this work is also quite incremental. However, I believe that contribution points in a relevant direction of understanding neural nets from nonparametric point of view. I'd be happy to raise the score if authors clarify some details.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper contributes a theoretical understanding of training over-parametrized deep neural networks with rectified linear unit (ReLU) activations using gradient descent with respect to square loss in the neural tangent kernel (NTK) regime. Authors consider a non-parametric regression framework wherein the labels are generated using a ground truth function, which is assumed to be in the RKHS associated with the NTK, perturbed with noise. Authors show that gradient descent based training without early stopping fails whereas \ell-2 regularized gradient descent achieved minimax optimal convergence rate. The paper is clearly written and the results are solid. Overall, a good paper.
Decision: Accept (Poster)