Year: 2021

Abstract:
We study the generalization properties of the overparameterized deep neural network (DNN) with Rectified Linear Unit (ReLU) activations. Under the nonparametric 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 L2 prediction error is bounded away from 0. As a complement of the above result, we show that the `2-regularized gradient descent enables the overparametrized DNN achieve the minimax optimal convergence rate of the L2 prediction error, without early stopping. Notably, the rate we obtained is faster than O(n−1/2) known in the literature.

1 INTRODUCTION
Over the past few years, Neural Tangent Kernel (NTK) [Arora et al., 2019b; Jacot et 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 in showing the linear convergence of the training error on 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 on both models [Arora et al., 2019a; Cao & Gu, 2019]. These findings clearly lead to the equivalence between learning dynamics of neural networks and the kernel methods in an reproducing kernel Hilbert spaces (RKHS) associated with NTK. 1 Specifically, Arora et al. [2019a] provided the O(n−1/2) generalization bound of shallow neural network, where n 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, Nitanda & Suzuki [2020] showed that the shallow neural network with smoothly approximated ReLU (swish, see Ramachandran et al. [2017]) activation trained via `2-regularized averaged stochastic gradient descent (SGD) can recover the target function from RKHSs induced from NTK with swish activation. Similarly, Hu et al. [2021] showed that a shallow neural network with ReLU activation trained via `2-regularized GD can generalize well, when the target function (i.e., f?ρ ) is fromHNTK1 . 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 `2-regularized GD or averaged SGD algorithms for recovering functions from respective function spaces. Nevertheless,
1Henceforth, we denoteHNTK1 andHNTKL as RKHSs induced from NTK of shallow L = 1 and deep neural networks L ≥ 2 with ReLU activations, respecitvely.
these results are restricted to shallow neural networks, and cannot explain the generalization abilities of deep neural network (DNN). Similarly with Arora et al. [2019a], Cao & Gu [2019] obtained the O(n−1/2) generalization bound, showing that the SGD generalize well for f?ρ ∈ HNTKL , when f?ρ has a bounded RKHS norm. However, the rate they obtained is slower than the minimax rate we 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 as follows:
When the noisy dataset is generated from a function fromHNTKL , does the overparametrized DNN obtained via (`2-regularized) GD provably generalize well the unseen data?
We consider a neural network that has L ≥ 2 hidden layers with width m n. (i.e., overparametrized deep neural network.) We focus on the least-squares loss and assume that the activation function is ReLU. A positivity assumption of NTK from ReLU DNN is imposed, meaning that λ0 > 0, where λ0 denotes the minimum eigenvalue of the NTK. We give a more formal mathematical 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 L2-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 on training dynamics 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 as well.
• In an unregulaized case, under the assumption λ0 > 0, we show randomly initialized GD converges to 0 training loss at a linear rate. As will be detailed in subsection 3.3, this is the different result from the seminal work of Allen-Zhu et al. [2018], where they also prove a linear convergence 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 f?ρ ∈ HNTKL under noisy observations, if the DNN is trained for either too short or too long: that is, the prediction error is bounded away from 0 by some constant as n goes to infinity.
• In regularized case, we 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 `2-regularization can be helpful in achieving the minimax optimal rate of the prediction risk for recovering f?ρ ∈ HNTKL under the noisy data. Specifically, it is shown that after some iterations of `2-regularized GD, the minimax optimal rate (which is O ( n− d 2d−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 `2-regularized DNN can achieve a minimax optimal rate of prediction error for recovering f?ρ ∈ HNTKL . 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 et 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: a set of nodes whose activation 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 a 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 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 ‖W‖2F to the objective function. The `2-regularization solely on the W has an effect of pushing the weight towards the origin. This makes ‖W(k) −W(0)‖2 ≤ O ( 1 )
2, allowing most activation patterns of the nodes in the hidden layer can change during the training, even in overparametrized setting. Here, W(k) denotes the updated weight parameter at kth itertaion of algorithm, and ‖ · ‖2 denotes the spectral norm of the matrix. Nonetheless, this doesn’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 `2-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 `2-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 can ignore the non-convex interactions of parameters across the hidden layers. Specifically, under suitable model parameter setting, we prove that ‖W(k)` −W (0) ` ‖2 ≤ ÕP ( 1√ m ) 3 over all ` ∈ {1, . . . , L}. Here, ÕP(·) hides the dependencies on the model parameters; L, ω, and n. This result allows us to adopt the so-called “Forward Stability” argument developed by Allen-Zhu et al. [2018], and eventually leads to the control of network gradient under `2 sense.
1.3 ADDITIONAL RELATED WORKS
There has been another line of works 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 L2-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 a linear combination of Ω(n10d 2
) smaller neural network, and the activation function they consider is sigmoid function, which is smooth and differentiable. Along this line of research, Kuzborskij & Szepesvári [2021] (regression) and Ji et al. [2021] (classification) showed that when training overparametrized shallow neural network, early stopping of vanilla GD enables us to obtain consistent estimators.
Notation. We use the following notation for asymptotics: For sufficiently large n, we write f(n) = O(g(n)), if there exists a constant K > 0 such that f(n) ≤ Kg(n), and f(n) = Ω(g(n)) if f(n) ≥ K ′g(n) for some constant K ′ > 0. The notation f(n) = Θ(g(n)) means that f(n) = O(g(n)) and
2This was empirically shown to be 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.
3Readers can find the proof of this result in Appendix G.
f(n) = Ω(g(n)). Let 〈A,B〉Tr := Tr(A>B) for the two matrices A,B ∈ Rd1×d2 . We adopt the shorthand notation denoting [n] := {1, 2, . . . , n} for n ∈ N.
2 PROBLEM FORMULATION
2.1 NON-PARAMETRIC REGRESSION
Let X ⊂ Rd and Y ⊂ R be the measureable feature space and output space. We denote ρ as a joint probability measure on the product space X × Y , and let ρX be the marginal distribution of the feature space X . We assume that the noisy data-set D := {(xi,yi)}ni=1 are generated from the non-parametric regression model yi = f?ρ (xi) + εi, where εi
i.i.d.∼ N (0, 12) for i = 1, . . . , n. Let f̂W (k)(·) be the value of neural network evaluated with the parameters W at the k-th iterations of GD update rule. At k = 0, we randomly initialize the weight parameters in the model following He initialization [He et al., 2015] with a slight modification. Then, the L2 prediction risk is defined as the difference between two expected risks (i.e., excess risk) R(f̂W (k)) := Eρ∼(x,y)[ ( y − f̂W (k)(x) )2 ]
and R(f?ρ ) := Eρ∼(x,y)[ ( y − f?ρ (x) )2 ], where f?ρ (x) := E[y|x]. Then, we can easily show the prediction risk has a following form:
R ( f̂k, f ? ρ ) := R ( f̂W (k) ) −R ( f? ) = Eρx,ε [( f̂W (k)(x)− f?ρ (x) )2] . (1)
Note that the expectation is taken over the marginal probability measure of feature space, ρx, and the noise of the data, ε. However, the (1) is still a random quantity due to the randomness of the initialized parameters ( W
(0) ` ) `=1,...,L .
2.2 DEEP NEURAL NETWORK WITH RELU ACTIVATION
Following the setting introduced in Allen-Zhu et al. [2018], we consider a fully-connected deep neural networks with L hidden layers and m network width. For L ≥ 2, the output of the network fW(·) ∈ R with input data x ∈ X can be formally written as follows:
fW(x) = √ m · vTσ ( WLσ ( WL−1 · · ·σ ( W1x ) · · · )) , (2)
where Sd−1 is a unit sphere in d-dimensional euclidean space, σ(·) is an entry-wise activation function, W1 ∈ Rm×d, W2, . . . ,WL ∈ Rm×m denote the weight matrices for hidden layers and v ∈ Rm×1 denote the weight vector for the output layer. Following the existing literature, we will consider ReLU activation function σ(x) = 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 ( Wi,j ) `=1,...,L
∼ N (0, 2m ), and entries of the output layer are drawn from vj ∼ N (0, ωm ). 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 ωm , where ω ≤ 1 is a model parameter to be chosen later for technical convenience.
Unregularized GD update rule. We solve a following `2-loss function with the given dataset D:
LS ( W ) = 1
2 n∑ i=1 ( yi − fW(xi) )2 . (3)
Let W(0)1 , . . . ,W (0) L be the initialized weight matrices introduced above, and we consider a following gradient descent update rule:
W (k) ` = W (k−1) ` − η∇W` ( LS(W(k−1)` ) ) , ` ∈ [L], k ≥ 1, (4)
where ∇W` ( LS(·) ) is a partial gradient of the loss function LS(·) with respect to the `-th layer parameters W`, and η > 0 is the learning rate of the gradient descent.
`2-regularized GD update rule. The estimator is obtained by minimizing a `2-regularized function;
ΦD(W) := LS ( WD ) + µ
2 L∑ `=1 ∥∥∥WD,` −W(0)D,`∥∥∥2 F . (5)
Naturally, we update the model parameters { WD,` } `=1,...,L via modified GD update rule:
W (k) D,` = ( 1− η2µ ) W (k−1) D,` − η1∇W` [ LS ( W (k−1) D )] + η2µW (0) D,`, ∀` ∈ [L], ∀k ≥ 1. (6)
The notations η1, η2 are step sizes, and µ > 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(0)D,` are initialized parameters same with the unregularized case. For simplicity, we fix the output layer, and train L hidden layers for both unregularized and regularized cases.
3 MAIN THEORY
First, we describe the neural tangent kernel (NTK) matrix of (2), which is first proposed by Jacot et al. [2018] and further studied by Arora et al. [2019b]; Du et al. [2019]; Lee et al. [2018]; Yang [2019]. NTK matrix of DNN is a L-times recursively defined n × n kernel matrix, whose entries are the infinite-width limit of the gram matrix. Let ∇W` [ fW(0)(·) ] be the gradient of the ReLU DNN (2) with respect to the weight matrix in `th hidden layer at random initialization. Note that when ` = 1,∇W` [ fW(0)(·) ] ∈ Rm×d and when ` ∈ {2, . . . , L},∇W` [ fW(0)(·) ] ∈ Rm×m. Then, as m→∞,
H(0) :=
( 1
m L∑ `=1 〈 ∇W` [ fW(0)(xi) ] ,∇W` [ fW(0)(xj) ]〉 Tr ) n×n → H∞L , (7)
where H∞L := { Ker(xi,xj) }n i,j=1
. Here, Ker(·, ·) denotes a NTK function of (2) to be defined as follows: Definition 3.1. (NTK function of (2)). For any x,x′ ∈ X and ` ∈ [L], define
Φ(0)(x,x′) = 〈x,x′〉 ,
Θ(`)(x,x′) = ( Φ(`−1)(x,x) Φ(`−1)(x,x′) Φ(`−1)(x′,x) Φ(`−1)(x′,x′) ) ∈ R2×2,
Φ(`)(x,x′) = 2 · E (u,v)∼N (0,Θ(`))
[ σ(u) · σ(v) ] , and
Φ̇(`)(x,x′) = 2 · E (u,v)∼N (0,Θ(`))
[ σ̇(u) · σ̇(v) ] ,
where σ̇(u) = 1 ( u ≥ 0 ) . Then, we can derive the final expression of NTK function of (2) as follows:
Ker(x,x′) = ω 2 · L∑ `=1 ( Φ(`−1)(x,x′) · L∏ `′=` Φ̇(` ′)(x,x′) ) . (8)
The expression in (8) is adapted from Cao & Gu [2019]. As remarked in Cao & Gu [2019], a coefficient 2 in Φ(`) and Φ̇(`) remove the exponential dependence on the network depth L 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 vj ∼ N (0, 1m ), whereas we consider vj ∼ N (0, ωm ). (ii) Φ
(L) is not added in the final expression of (8)), whereas it is added in the definition provided in Cao & Gu [2019]. This is because we 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]; 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 tt 1 ) with |t| ≤ 1:
E (u,v)∼N (0,Θ(`))
[ σ(u) · σ(v) ] = 1
2π
( t · (π − arccos(t)) + √ 1− t2 ) ,
E (u,v)∼N (0,Θ(`))
[ σ̇(u) · σ̇(v) ] = 1
2π
( π − arccos(t) ) .
(9)
Clearly, (8) is symmetric and continuous on the product space 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) as: Definition 3.2. (NTK induced RKHS). For some integer p ∈ N, set of points {x̃j}pj=1 ⊂ X , and weight vector α := {α1, . . . , αp} ∈ Rp, define a complete vector space of functions, f : X → R,
HNTKL := cl ({ f(·) = p∑ j=1 αjKer(·, x̃j) }) , (10)
where cl(·) denotes closure.
In the remaining of our work, we assume the regression function f?ρ (x) := E[y|x] belongs toHNTKL .
3.1 ASSUMPTIONS.
In this subsection, we state the assumptions imposed on the data distribution with some remarks.
(A1) ρX is an uniform distribution on Sd−1 := {x ∈ Rd | ‖x‖2 = 1}, and noisy observations are assumed to be bounded. (i.e., ρx ∼ Unif ( Sd−1 ) , yi = O(1), ∀i ∈ [n].)
(A2) Draw n i.i.d. samples {xi, f?ρ (xi)}ni=1 from the joint measure ρ. Then, with probability at least 1− δ, we have λmin ( H∞L ) = λ0 > 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,HNTKL . See the Appendix 3.2 and references therein.
• Assumption (A2) is commonly employed in NTK related literature for proving global convergence of training error and generalization error of both deep and shallow neural network, Du et al. [2018; 2019]; Arora et al. [2019a]. Note that the (A2) holds as long as no two xi and xj are parallel to each other, which is true for most of the real-world distributions. See the proof of this claim in Du et al. [2019].
3.2 MINIMAX RATE FOR RECOVERING f?ρ ∈ HNTKL
The obtainable minimax rate of L2-prediction error is directly related with the complexity of function space of interest. In our setting, the complexity of RKHS HNTKL 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:
Ker(x,x′) = ∞∑ k=0 µk N(d,k)∑ j=1 Yk,j(x)Yk,j(x ′),
where Yk,j , j = 1, . . . , N(d, k) are spherical harmonic polynomials of degree k and {µk}∞k=0 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 µk is in the order of Θ ( k−d ) 4. Given this result and the fact N(d, k) = 2k+d−3k ( k+d−3 d−2 ) grows as kd−2 for
large k, it can be easily shown λj = Θ ( j− d d−1 ) , when Ker(x,x′) = ∑∞ j=1 λjφj(x)φj(x
′), for eigen-values λ1 ≥ λ2 ≥ · · · ≥ 0 and orthonormal basis {φj}∞j=1. Furthermore, it is a well known fact that if the eigenvalues decay at the rate λj = Θ(j−2ν), then the corresponding minimax rate for estimating function in RKHS is O ( n− 2ν 2ν+1 ) , [Raskutti et al., 2014; Yuan & Zhou, 2016; Hu et al.,
2021]. By setting 2ν = dd−1 , we can see the minimax rate for recovering f ? ρ ∈ HNTKL isO
( n− d 2d−1 ) .
Remark 3.4. We defer all the technical proofs of the Theorems in subsections 3.3 and 3.4 in the Appendix for conciseness of the paper. At the beginning of each proof, a high-level proof idea is also provided. 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 minimizing unregularized `2-loss (3) and on the corresponding estimator’s L2-prediction riskR ( f̂k, f ? ρ ) . Theorem 3.5. (Optimization) For some δ ∈ [0, 1], if we set the width of the network as m log3(m)
≥ Ω ( ω7n8L18
λ80δ 2
) , and we set the step-size of gradient descent as η = O ( λ0
n2L2m
) . Then, with probability
at least 1−δ over the randomness of initialized parametersW(0) := { W
(0) ` }L+1 `=1
with W(0)L+1 = v, we have for k = 0, 1, 2, . . . ,
LS ( W(k) ) ≤ (
1− ηmλ0 2
)k LS ( W(0) ) . (11)
In other words, the training loss drops to 0 at a 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 is 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 0. Furthermore, the result of Allen-Zhu et al. [2018] relies on φ-separateness assumption stating that the every pair of feature vectors { xi,xj }n i 6=j is apart from each other by some constant φ > 0 in a Euclidean norm. In our work, the positivity assumption on the minimum eigenvalue of the NTK is imposed (i.e., λ0 > 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 Ω ( n8L12
φ8
) , where they impose φ-separateness assumption.
Remark 3.7. There has been an attempt to make a connection between the positivity and φseparateness assumptions. Recently, Zou & Gu [2019] proved the relation λ0 = Ω ( φn−2 ) 5 in a shallow-neural net setting. See Proposition 3.6. of their work. However, it is still an open question on whether this relation holds in DNN setting as well. The results in Theorem 3.5 suggest a positive conjecture on this question. Indeed, plugging the relation λ0 = Ω ( φn−2 ) in (11) and in
the η = O (
λ0 n2L2m
) yield the discount factor ( 1− Ω ( ηmφ n2 ))k and step-size η = O ( φ n4L2m ) , which
are exactly the same orders as presented in Allen-Zhu 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.
4In shallow neural network with ReLU activation without bias terms, it is shown that µk satisfy µ0, µ1 > 0, µk = 0 if k = 2j + 1 with j ≥ 1, and otherwise µk = Θ ( k−d ) . See Bietti & Mairal [2019]. However, in
ReLU DNN, it is shown that these parity constraints can be removed even without bias terms and µk achieves Θ ( k−d ) decay rate for large enough k. Readers can refer Bietti & Bach [2021] for this result.
5We conjecture that this is not the tightest lower bound on λ0. Recently, Bartlett et al. [2021] proves that λ0 & d/n in shallow neural net setting. See Lemma 5.3 in their paper.
Theorem 3.8. (Generalization) Let f?ρ ∈ HNTKL . Fix a failure probability δ ∈ [0, 1]. Set the width of the network as m
log3(m) ≥ Ω
( ω7n8L18
λ80δ 2
) , the step-size of gradient descent as η = O ( λ0
n2L2m
) , and the
variance parameter ω ≤ O (( λ0δ n )2/3) . Then, if the GD iteration k ≥ Ω ( log(n) ηmλ0 ) or k ≤ O ( 1 ηmωL ) , with probability at least 1− δ over the randomness of initialized parametersW(0), we have
R ( f̂k, f ? ρ ) = Ω(1).
This theorem states that if the network is trained for too long or too short, the L2-prediction error of f̂W(k) is bounded away from 0 by some constant factor. Specifically, the former scenario indicates that the overfitting can be harmful for recovering f?ρ ∈ HNTKL 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 R ( f̂k, f ? ρ ) over the range of iterations (ηmωL)−1 . k . (ηmλ0) −1 log(n). In the numerical experiment to be followed in Section A, we observe that for some algorithm iterations k∗, the risk indeed decreases to the same minimum as low as the `2- regularized algorithm can achieve, and increases again. This observation implies that the unregularized algorithm can achieve the minimax rate of prediction risk. However, analytically deriving a data-dependent stopping time k∗ in our scenario requires further studies, since we need a sharp characterization of eigen-distribution of NTK matrix of ReLU DNN, denoted as H∞L in this paper. Readers can refer the Theorem 4.2. of Hu et al. [2021] in shallow-neural network and equation (6) in Raskutti et al. [2014] in kernel regression context on how to compute k? with the given eigenvalues of the associated kernel matrices.
Remark 3.10. From practitioner’s point of view, we can simply stop GD before it hits the nearlyzero empirical risk, but monitor the performance on a held-out validation sample, and stop training early when a minimum on the validation sample has been reached.
3.4 ANALYSIS OF `2-REGULARIZED DNN
In this subsection, we study the training dynamics of `2-regularized DNN and the effects of the regularization for obtaining the minimax optimal convergence rate of L2-prediction risk. In the results to be followed, we set the orders of model parameters µ, η1, η2 in (6), and a variance parameter of output layer, ω as follows:
µ = Θ ( n d−1 2d−1 ) , η1 = Θ ( 1
m n− 3d−2 2d−1
) , η2 = Θ ( 1
L n− 3d−2 2d−1
) , ω = O ( 1
L3/2 n− 5d−2 2d−1
) .
(12)
Theorem 3.11. (Optimization) Suppose we minimize `2-regularized objective function (5) via modified GD (6). Set the network width m
log3(m) ≥ Ω
( L20n24
δ2
) and model parameters as in (12). Then,
with probability at least 1− δ, the mean-squared error follows
LS ( W(k)D ) /n ≤ ( 1− η2µL )k · LS ( W(0)D ) /n+OP(1), (13)
for k ≥ 0. Additionally, after k ≥ Ω ( (η2µL) −1 log(n3/2) )
iterations of (6), for some constant C > 0, we have ∥∥∥∥∥uD(k)−H∞L ( Cµ · I + H∞L )−1 y ∥∥∥∥∥ 2 ≤ OP ( 1 n ) , (14)
where we denote uD(k) := [f̂W(k)D (x1), . . . , f̂W(k)D
(xn)] >.
Several comments are in sequel. Theorem 3.11 is, to our knowledge, the first result that rigorously shows the training dynamics of `2-regularized ReLU DNN in overparametrized setting. Observe that the first term on the right-hand side of the inequality (13) converges linearly to 0, and the second term is some positive constant that is bounded away from 0. This implies that the MSE of regularized DNN is upper-bounded by some positive constant. Note that we only provide the upper
bound, but the results of our numerical experiments indicate that the MSE is lower-bounded by OP(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 as g?µ) of the following kernel ridge regression problem:
min f∈HNTK
{ 1
2 n∑ i=1 ( yi − f(xi) )2 + Cµ 2 ‖f‖2HNTKL } , (15)
where ‖ · ‖HNTKL denotes a NTK-induced RKHS norm. (Note that the optimization problem in (15) is not normalized by sample size n.) The inequality (14) states that after approximately (η2µL) −1 iterations of (6), the error rate becomes OP ( 1 n ) . The approximation error is computed at the training data points under `2 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, we show that the approximation holds “after” k ≥ Ω ( (η2µL)
−1 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 `=1 ‖W` −W (0) ` ‖2F , whereas Hu et al. [2021] regularized the term ‖W1‖2F .
As another important comparison, Hu et al. [2019] showed the equivalence of a solution of kernel ridge regression associated with NTK and first order Taylor expansion of the regularized neural network dynamics; note, however, that the uD(k) in (14) is a full neural network dynamics. LetR(f̂
W (k) D , f?ρ ) be the L2-prediction risk of the regularized estimator f̂W(k)D via modified GD (6).
Next theorem states the result of generalization ability of f̂ W
(k) D
. Theorem 3.12. (Generalization) Let f?ρ ∈ HNTKL . Suppose the network width mlog3(m) ≥ Ω ( L20n24 δ2 ) and model parameters are set as suggested in (12). Then, with probability tending to 1, we have
R ( f̂ W
(k) D
, f?ρ ) = OP ( n− d 2d−1 ) .
The resulting convergence rate is O ( n− d 2d−1 ) with respect to the training sample size n. Note that
the rate is always faster than O ( n−1/2 ) and turns out to be the minimax optimal [Caponnetto & De Vito, 2007; Blanchard & Mücke, 2018] for recovering f?ρ ∈ HNTKL in the following sense:
lim r→0 lim inf n→∞ inf f̂ sup ρ
P [ R ( f̂ , f?ρ ) > rn− d 2d−1 ] = 1, (16)
where ρ is a data distribution class satisfying the Assumptions (A1), (A2) and f?ρ ∈ HNTKL , 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?ρ ∈ HNTK1 . (i.e., Hu et al. [2021]) This result can be derived from the recent discovery of the equivalence between two function spaces ,HNTK1 = HNTKL . See Geifman et al. [2020] and Chen & Xu [2020].
Remark 3.13. A particular choice of µ = Θ ( n d−1 2d−1 ) in (12) is for obtaining an optimal minimax rate for prediction error in Theorem 3.12. Specifically, the order of µ determines the L2 distance between the f?ρ and the kernel regressor g ? µ. That is, ‖f?ρ − g?µ‖22 = OP( µ n ). With the resultH NTK 1 = HNTKL , the same proof of Lemma D.2. in Hu et al. [2021] can be applied for proving this result.
4 CONCLUSION
We analyze the convergence rate of L2-prediction error of both the unregularized and the regularized gradient descent for overparameterized DNN with ReLU activation for a regression problem. Under a positivity assumption of NTK, we show that without the adoption of early stopping, the L2-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 `2-regularized GD achieves the optimal minimax rate (Theorem 3.12). The minimax rate O ( n− d 2d−1 ) is a faster than the O(n−1/2) by specifying the complexities of target function and hypothesis space.
ACKNOWLEDGMENTS
Use unnumbered third level headings for the acknowledgments. All acknowledgments, including those to funding agencies, go at the end of the paper.
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 overparameterized neural networks, going beyond two layers. Advances in Neural Information Processing Systems, 32:6158–6169, 2019.
Sanjeev Arora, Simon Du, Wei Hu, Zhiyuan Li, and Ruosong Wang. Fine-grained analysis of optimization 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–8150, 2019b.
Peter L. Bartlett, Andrea Montanari, and Alexander Rakhlin. Deep learning: a statistical viewpoint. Acta Numerica, 30:87–201, 2021. doi: 10.1017/S0962492921000027.
Ronen Basri, Meirav Galun, Amnon Geifman, David Jacobs, Yoni Kasten, and Shira Kritchman. Frequency bias in neural networks for input of non-uniform density. In International Conference on Machine Learning, pp. 685–694. PMLR, 2020.
Benedikt Bauer and Michael Kohler. On deep learning as a remedy for the curse of dimensionality in nonparametric regression. Annals of Statistics, 47(4):2261–2285, 2019.
Alberto Bietti and Francis Bach. Deep equals shallow for ReLU networks in kernel regimes. In ICLR 2021-International Conference on Learning Representations, pp. 1–22, 2021.
Alberto Bietti and Julien Mairal. On the inductive bias of neural tangent kernels. In NeurIPS 2019-Thirty-third Conference on Neural Information Processing Systems, volume 32, pp. 12873– 12884, 2019.
Gilles Blanchard and Nicole Mü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, 32:10836–10846, 2019.
Andrea Caponnetto and Ernesto De Vito. Optimal rates for the regularized least-squares algorithm. Foundations of Computational Mathematics, 7(3):331–368, 2007.
Lin Chen and Sheng Xu. Deep neural tangent kernel and Laplace kernel have the same RKHS. In International Conference on Learning Representations, 2020.
Lénaı̈c Chizat and Francis Bach. On the global convergence of gradient descent for overparameterized models using optimal transport. In Proceedings of the 32nd International Conference on Neural Information Processing Systems, pp. 3040–3050, 2018.
Youngmin Cho and Lawrence Saul. Kernel methods for deep learning. Advances in Neural Information 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. In International Conference on Machine Learning, pp. 1675– 1685. PMLR, 2019.
Simon S Du, Xiyu Zhai, Barnabas Poczos, and Aarti Singh. Gradient descent provably optimizes over-parameterized neural networks. In International Conference on Learning Representations, 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:2007.01580, 2020.
Behrooz Ghorbani, Song Mei, Theodor Misiakiewicz, and Andrea Montanari. When do neural networks outperform kernel methods? arXiv preprint arXiv:2006.13409, 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 nonparametric perspective on 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 on Learning Representations, 2019.
Arthur Jacot, Clément Hongler, and Franck Gabriel. Neural tangent kernel: Convergence and generalization in neural networks. In NeurIPS, 2018.
Ziwei Ji, Justin D Li, and Matus Telgarsky. Early-stopped neural networks are consistent. arXiv preprint arXiv:2106.05932, 2021.
Yongdai Kim, Ilsang Ohn, and Dongha Kim. Fast convergence rates of deep neural networks for classification. Neural Networks, 138:179–197, 2021.
Michael Kohler and Adam Krzyzak. Over-parametrized deep neural networks do not generalize well. arXiv preprint arXiv:1912.03925, 2019.
Ilja Kuzborskij and Csaba Szepesvári. Nonparametric regression with shallow overparameterized neural networks trained by gd with early stopping. In Conference on Learning Theory, pp. 2853– 2890. PMLR, 2021.
Jaehoon 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:1902.01687, 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:1710.05941, 2017.
Garvesh Raskutti, Martin J Wainwright, and Bin Yu. Early stopping and non-parametric regression: an optimal data-dependent stopping rule. The Journal of Machine Learning Research, 15(1): 335–366, 2014.
Johannes Schmidt-Hieber. Nonparametric regression using deep neural networks with ReLU activation function. Annals of Statistics, 48(4):1875–1897, 2020.
Richard S Varga. Geršgorin-type theorems for partitioned matrices. In Geršgorin and His Circles, pp. 155–187. Springer, 2004.
Roman Vershynin. High-dimensional probability: An introduction with applications in data science, volume 47. Cambridge university press, 2018.
Colin Wei, Jason Lee, Qiang Liu, and Tengyu Ma. Regularization matters: Generalization and optimization of neural nets vs their induced kernel. 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-Xuan Zhou. Minimax optimal rates of estimation in high dimensional additive models. Annals of Statistics, 44(6):2564–2593, 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 arXiv:1811.08888, 2018.
Difan Zou, Yuan Cao, Dongruo Zhou, and Quanquan Gu. Gradient descent optimizes overparameterized deep ReLU networks. Machine Learning, 109(3):467–492, 2020.
A NUMERICAL ILLUSTRATIONS
In this section, we use synthetic data to corroborate our theoretical findings. We use the He initialization [He et al., 2015] and employ (`2-regularized) GD as introduced in subsection 2.2. For the experiments, we run 1000 epochs of GD and use a fixed step size, setting η1 = η2 = 0.001. We uniformly generate n feature data xitrain from Sd−1 with d = 2 and generate yi from f?ρ (xtraini ) with εi ∼ N (0, 1). To create a function f?ρ ∈ HNTKL , we use the definition in (10) with α ∈ Unif(Sp−1) and with p fixed points {x̃j}pj=1 ⊂ Unif(Sd−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 we have a network with depth L = 8 and width m = 2000. The variance parameter of the output layer (ω) is set as 1 for unregularized and 0.001 for regularized cases.
In Fig 1.(a), we record the training errors of regularized networks over the GD epochs k ≤ 1000, where we have n ∈ {100, 300, 500, 1000, 5000} training samples. This aims to verify the inequality (13) that the MSE of regularized network is bounded away from 0 by some constant. In Fig 1.(b), the prediction risks of both unregularized and regularized networks are displayed. We approximate the risk with 1500 ∑500 j=1 ( f̂k(x test j ) − f?ρ (xtestj ) )2 with a new test data set {xtestj , f?ρ (xtestj )}500j=1 over k ≤ 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 ( 1
ηmωL
) , the prediction error is bounded away from 0. In the experiment for unregularized
case, we set η = 0.01, m = 2000, L = 8, and ω = 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 0 at the rate O ( n− d 2d−1 ) . In Fig 1.(c), we verify that the more training sample sizes we have, the closer the risks of the regularized networks get to 0. The risk is evaluated at the sample sizes n = {100, 300, 500, 1000, 5000}.
We have to acknowledge that there is a discrepancy between our experiment setting and theory. Specifically, due to the limited computing power, we could not run the experiment under the regime of width m
log3(m) ≥ Ω
( ω7n8L18
λ80δ 2
) . But the prediction risk behaves similarly as expected by
our theorem, which can be a partial evidence that the statement in Theorem 3.6 still holds in the narrower width of the network.
B PRELIMINARY NOTATIONS
Before presenting the formal proofs of Lemmas and main results, we introduce several notations used frequently throughout the proofs. First, we denote x`,i the output of the `th hidden layer with the input data xi after applying entry-wise ReLU activation function.
x`,i = σ ( W`σ ( W`−1 · · ·σ ( W1xi ) · · · )) .
Denote fW(k)(x) a value of neural network (2) evaluated at the collection of network parameters W(k) := { W
(k) ` } `=1,...,L and W(k)` denotes the `th hidden layer parameter updated by kth GD
iterations.
Partial gradient of fW(k)(x). We employ the following matrix product notation which was used in several other papers [Zou et al., 2018; Cao & Gu, 2019]:
`2∏ r=`1 Ar := { A`2A`2−1 · · ·A`1 if `1 ≤ `2, I otherwise. (17)
Then, the partial gradient of fW(k)(x) with respect to W (k) ` for 1 ≤ ` ≤ L has a following form: for i ∈ {1, . . . , n},
∇W` [ fW(k)(xi) ] = √ m · [ x (k) `−1,iv T ( L∏ r=`+1 Σ (k) r,i W (k) r ) Σ (k) `,i ]> , ` ∈ [L],
where Σ(k)`,i := Diag ( 1 ( 〈w(k)`,1 ,x (k) `−1,i〉 ≥ 0 ) , . . . ,1 ( 〈w(k)`,m,x (k) `−1,i〉 ≥ 0 )) ∈ Rm×m and w(k)`,j 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:
Hi,j(k) = 1
m L∑ `=1 〈 ∇W` [ fW(k)(xi) ] ,∇W` [ fW(k)(xj) ]〉 Tr .
Note that H(0) → H∞L as m → ∞ which is proved in Jacot et al. [2018]; Yang [2019]; Lee et al. [2018]; Arora et al. [2019b].
Perturbation region of weight matrices. Consider a collection of weight matrices W̃ = { W̃` } `=1,...,L such that
W̃ ∈ B ( W(0), τ ) := { W̃` : ‖W̃` −W(0)` ‖2 ≤ τ, ∀` ∈ [L] } . (18)
For all i ∈ {1, . . . , n} and ` = 1, . . . , L, we denote x`,i and x̃`,i as the outputs of the `-th layer of the neural network with weight matrices W(0) and W̃, and Σ`,i and Σ̃`,i are diagonal matrices with( Σ`,i ) jj = 1 ( 〈w(0)`,j ,x`−1,i〉 ≥ 0 ) and ( Σ̃`,i ) jj = 1 ( 〈w̃`,j , x̃`−1,i〉 ≥ 0 ) , respectively.
C WHY IS IT HARD TO PROVE ‖W(k)D,` −W (0) D,`‖2 ≤ O
( 1 ) ?
In this subsection, we provide a heuristic argument on why it is hard to prove ‖W(k)D,` −W (0) D,`‖2 ≤ O ( 1 ) , where W(k)D,` is the model parameter of `th layer in kth iteration of algorithm. Here, we regularize solely on the model parameter, instead on the relative to the initialization. In this case, we can write the update rule as follows :
W (k) D,` = ( 1− η2µ ) W (k−1) D,` − η1∇W` [ LS ( W (k−1) D )] , ∀1 ≤ ` ≤ L and ∀k ≥ 1. (19)
By recursively applying above equation (4.3), we can write W(k)D,` with respect to W (0) D,` as follows:
W (k) D,` = (1− η2µ) kW (0) D,` − η1 k−1∑ `=0 (1− η2µ)`∇W` [ LS ( W (k−`−1) D )] .
Then, we can control the bound as follows:
‖W(k)D,` −W (0) D,`‖2 ≤
( 1− ( 1− η2µ )k)∥∥∥W(0)D,`∥∥∥ 2 + η1 η2µ max `=0,...,k−1 ∥∥∥∇W`[LS(W(k−`−1)D )]∥∥∥ 2 .
We know under the initialization setting in our paper, ‖W(k)D,`‖2 ≤ O(1) with high-probability (see Vershynin [2018]), and as long as we can prove the `2-norm of gradient is bounded, then we can conclude ‖W(k)D,`−W (0) D,`‖2 ≤ O ( 1 ) . However, we are not aware of works in which they control
the size of ‖∇W` [ LS ( W (k−`−1) D )] ‖2 where the non-convex interactions between model parameters across the hidden layers are allowed. To the best of our knowledge, we 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 to arbitrary L-hidden layer setting.
D USEFUL LEMMAS
A simple fact. Suppose vj i.i.d∼ N (0, ωm ) for j ∈ [m]. Then, with probability at least 1 − exp [−Ω(m)], ‖v‖22 ≤ O(ω).
Proof. Since ∥∥v2j∥∥Ψ1 ≤ O( ωm) for j ∈ [m], where ‖ · ‖Ψ1 denotes a sub-exponential norm, Bernstein’s inequality for i.i.d. centered sub-exponential random variables can be employed : For any t ≥ 0,
P ( ∣∣∣∣∣∣ m∑ j=1 ( v2j − ω m )∣∣∣∣∣∣ ≥ t ) ≤ 2 exp ( − cmin ( t2∑m j=1 ∥∥v2j∥∥2Ψ1 , t maxj ∥∥v2j∥∥Ψ1 )) , (20)
where c > 0 is an absolute constant. Note that we used the fact centering does not hurt the subexponentiality of random variable. Choosing t = O ( ω ) concludes the proof.
Lemma 4.1 (Lemma 7.1. Allen-Zhu et al. [2018]). With probability at least 1 − O(nL) · exp[−Ω(m/L)], 3/4 ≤ ‖x(0)`,i ‖2 ≤ 5/4 for all i ∈ {1, . . . , n} and ` ∈ {1, . . . , L}.
Lemma 4.2 (Lemma B.1. Cao & Gu [2019]). If τ ≤ O ( L−9/2[log(m)]−3 ) , then with probability
at least 1 − O(nL) · exp[−Ω(mτ2/3L)], 1/2 ≤ ‖x̃`,i‖2 ≤ 3/2 for all W̃ ∈ B ( W(0), τ ) , i ∈ {1, . . . , n} and ` ∈ {1, . . . , L}. Lemma 4.3 ( Allen-Zhu et al. [2018]). Uniformly over i ∈ {1, . . . , n} and 1 ≤ `1 ≤ `2 ≤ L, the following results hold:
1. (Lemma.7.3, Allen-Zhu et al. [2018]) Suppose m ≥ Ω(nL log(nL)), then with probability at least, 1−O ( nL2 ) · exp[−Ω(mτ2/3L)],∥∥∥∥∥ `2∏ r=`1 Σ (0) r,iW (0) r ∥∥∥∥∥ 2 ≤ O (√ L ) .
2. (Lemma.7.4, Allen-Zhu et al. [2018]) Suppose m ≥ Ω(nL log(nL)), then with probability at least, 1−O ( nL ) · exp[−Ω(m/L)],∥∥∥∥∥v> ( L∏ r=`1 Σ (0) r,iW (0) r )∥∥∥∥∥ 2 ≤ O (√ w ) .
3. (Lemma.8.2, Allen-Zhu et al. [2018]) Suppose τ ≤ O ( L−9/2[log(m)]−3 ) . For all W̃ ∈
B ( W(0), τ ) , with probability at least, 1−O ( nL2 ) · exp[−Ω(mτ2/3L)],∥∥∥x̃`1,i − x(0)`1,i∥∥∥2 ≤ O(τL5/2√log(m)).
4. (Corollary.8.4, Allen-Zhu et al. [2018]) Suppose τ ≤ O ( L−9/2[log(m)]−3 ) , then with
probability at least, 1−O ( nL2 ) · exp[−Ω(mτ2/3L)],∥∥∥Σ̃`1,i −Σ(0)`1,i∥∥∥0 ≤ O(mτ2/3L).
5. (Lemma.8.7, Allen-Zhu et al. [2018]) For all ` ∈ [L], let Σ′′`,i ∈ [−3, 3]m×m be the diagonal matrices with at most s = O(mτ2/3L) non-zero entries. For all W̃ ∈ B ( W(0), τ ) ,
where τ = O (
1 L1.5
) , with probability at least 1−O ( nL ) · exp[−Ω(s log(m))],∥∥∥∥∥vT ( L∏ r=`1+1 (Σ′′r,i + Σ (0) r,i ) W̃r,i )( Σ′′`1,i + Σ (0) r,i ) − vT ( L∏ r=`1+1 Σ (0) r,iW (0) r,i ) Σ (0) `1,i ∥∥∥∥∥ 2
≤ O ( τ1/3L2 √ ω log(m) ) .
Lemma 4.4 (Lemma B.3. Cao & Gu [2019]). There exists an absolute constant κ such that, with probability at least 1 − O ( nL2 ) · exp[−Ω(mτ2/3L)], i ∈ 1, . . . , n and ` ∈ 1, . . . , L and for all
W̃ ∈ B ( W(0), τ ) , with τ ≤ κL−6[log(m)]−3, it holds uniformly that∥∥∇W`[fW̃(xi)]∥∥2 ≤ O(√ωm). Lemma 4.5. Suppose W̃ ∈ B ( W(0), τ ) and τ ≤ O ( L−9/2[log(m)]−3 ) . For all u ∈ Rm with a cardinality ‖u‖0 ≤ s, for any 1 ≤ ` ≤ L and i ∈ {1, . . . , n}, with probability at least 1−O(nL) · exp ( − Ω(s log(m)) ) −O(nL) · exp ( − Ω(mτ2/3L)
) ,∣∣∣∣∣v> ( L∏ r=` Σ̃r,iW̃r,i ) u ∣∣∣∣∣ ≤ √ ωs log(m) m · O ( ‖u‖2 ) .
Proof. Recall Lemma 4.2. For any fixed vector u ∈ Rm, with probability at least 1 − O(nL) · exp[−Ω(mτ2/3L)] for τ ≤ O ( L−9/2[log(m)]−3 ) , for any 1 ≤ ` ≤ L and i ∈ {1, . . . , n}, we have the event T , ∥∥∥∥∥ ( L∏ r=` Σ̃r,iW̃r,i ) u ∥∥∥∥∥ 2 ≤ 3 ‖u‖2 . (21) Conditioned on this event happens, it is easy to see the random variable v> (∏L r=a Σ̃r,iW̃r,i ) u ∼
SG (
9ω m ‖u‖ 2 2
) . Based on this observation, we have the probability,
P ( ∣∣∣∣∣v> ( L∏ r=` Σ̃r,iW̃r,i ) u ∣∣∣∣∣ ≥ √ ωs log(m) m · O ( ‖u‖2 ))
≤ P ( ∣∣∣∣∣v> ( L∏ r=` Σ̃r,iW̃r,i ) u ∣∣∣∣∣ ≥ √ ωs log(m) m · O ( ‖u‖2 ) ∣∣∣ T )+ P(T c) ≤ O(nL) · exp ( − Ω(s log(m)) ) +O(nL) · exp ( − Ω(mτ2/3L) ) ,
where in the last inequality, union bounds over the indices ` and i, and over the vector u ∈ Rm with ‖u‖0 ≤ s are taken.
Lemma 4.6. Suppose τ ≤ 1 CL9/2[log(m)]3 for some constant C > 0. Then, for all i ∈ [n] and ` ∈ [L], with probability at least 1−O ( nL ) · exp[−Ω(mτ2/3L)], we have
∥∥∇W`[fW(k)(xi)]−∇W`[fW(0)(xi)]∥∥2 ≤ O(τ1/3L2√ωm log(m)).
Proof. By using the results from Lemma 4.3, we can control the term : ‖∇W` [ fW(k)(xi) ] −∇W` [ fW(0)(xi) ] ‖2
= √ m · ∥∥∥∥∥x(k)`−1vT ( L∏ r=`+1 Σ(k)r W (k) r ) Σ (k) ` − x (0) `−1v T ( L∏ r=`+1 Σ(0)r W (0) r ) Σ (0) ` ∥∥∥∥∥ 2
≤ √ m · ‖x(k)`−1 − x
(0) `−1 ‖2︸ ︷︷ ︸ ≤O(τL5/2 √ log(m)) ·
∥∥∥∥∥vT ( L∏ r=`+1 Σ(k)r W (k) r ) Σ (k) ` ∥∥∥∥∥ 2︸ ︷︷ ︸
≤O( √ ω)
+ √ m · ∥∥∥x(0)`−1∥∥∥ 2︸ ︷︷ ︸
≤O(1)
· ∥∥∥∥∥vT ( L∏ r=`+1 Σ(k)r W (k) r ) Σ (k) ` − v T ( L∏ r=`+1 Σ(0)r W (0) r ) Σ (0) ` ∥∥∥∥∥ 2︸ ︷︷ ︸
≤O(τ1/3L2 √ ω log(m))
≤ O ( τ1/3L2 √ ωm log(m) ) ,
where, in the last inequality, we used the condition on τ ≤ 1 CL9/2[log(m)]3 < 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 vj ∼ N (0, ωm ) for j ∈ [m].
For the notational convenience, in following Lemmas we denote fW(k)(xi) as ui(k) and let u(k) := [u1(k), . . . ,un(k)]
> for k ≥ 0. Lemma 4.8. For some δ ∈ [0, 1], if m ≥ Ω ( L log(nL/δ) ) , then with probability at least 1 − δ,
‖u(k)‖2 ≤ O (√nω
δ
) for any k ≥ 0.
Proof. Recall the Lemma 4.2 stating that ∥∥∥x(k)L,i∥∥∥
2 = O(1) for any input data xi for i ∈ [n]. Also
recall that vj ∼ N (0, ωm ) for j ∈ [m], xL,i ∈ R m and ui(k) = √ mv>xL,i ∼ N ( 0,O(ω) ) . Then, we have a following via simple Markov inequality: for any t ≥ 0,
P ( ‖u(k)‖2 ≥ t ) ≤ E [ ‖u(k)‖2 ] t ≤ √ E [ ‖u(k)‖22 ] t ≤ O (√ nω ) t .
Lemma 4.9. For some δ ∈ [0, 1], if m ≥ Ω ( L log(nL/δ) ) , then with probability at least 1− δ, we have
‖u(0)− y‖2 ≤ O (√ n
δ
) .
Proof. By Markov’s inequality, for any t ≥ 0,
P ( ‖u(0)− y‖2 ≥ t ) ≤
Eε,W(0),v [ ‖u(0)− y‖22 ] t2 . (22)
Note that the expectation in the nominator of (22) is taken over the random noise ε and initialized parameter W(0), v. We can expand the nominator as follows:
Eε,W(0),v [ ‖u(0)− y‖22 ] = EW(0),v‖u(0)‖22 + Eε‖y‖22 − 2Eε,W(0),v [ y>u(0) ] . (23)
For the convenience of notation, let y∗ := [f?ρ (x1), . . . , f ? ρ (xn)] > and ε := [ε1, . . . , εn]>. Recall that we have y = y∗ + ε, and ‖y∗‖22 = O(n). Also note that by Lemma 4.1, with probability at least 1−O(nL) · exp[−Ω(m/L)], for any i = 1, . . . , n, ‖x(0)L,i‖22 = O(1). Then, we have a random
variable ui(0) = √ mv>xL,i ∼ N (0,O(ω)). Now, we are ready to derive the orders of three terms on the RHS of (23). EW(0),v‖u(0)‖22 = O(n),
Eε‖y‖22 = Eε [ ‖y∗‖22 + ‖ε‖22 − 2y>ε ] = O(n),
Eε,W(0),v [ y>u(0) ] = Eε,W(0),v [( y∗ + ε )> u(0) ] = 0.
Combining the above three equalities, we conclude the proof. Lemma 4.10. Suppose τ = O ( n√ω√
mδλ0
) . For some δ ∈ [0, 1] such that δ ≥ O(nL) ·
exp[−Ω(mτ2/3L)], then with probability at least 1− δ, we have
‖H(k)−H(0)‖2 ≤ O
( ω7/6n4/3L3 6 √ log3(m)
mδλ20
) .
Proof. By the definition of gram matrix Hi,j(k) for any k ≥ 0, we have |Hi,j(k)−Hi,j(0)|
= ∣∣∣∣∣ 1m L∑ `=1 〈 ∇W` [ fW(k)(xi) ] ,∇W` [ fW(k)(xj) ]〉 Tr − 〈 ∇W` [ fW(0)(xi) ] ,∇W` [ fW(0)(xj) ]〉 Tr ∣∣∣∣∣ ≤ 1 m L∑ `=1 {∣∣∣∣〈∇W`[fW(k)(xi)],∇W`[fW(k)(xj)]−∇W`[fW(0)(xj)]〉 Tr
∣∣∣∣ +
∣∣∣∣〈∇W`[fW(0)(xj)],∇W`[fW(k)(xi)]−∇W`[fW(0)(xi)]〉 Tr ∣∣∣∣ }
≤ 1 m L∑ `=1 {∥∥∇W`[fW(k)(xi)]∥∥2︸ ︷︷ ︸ ≤O (√ ωm ) · ∥∥∇W`[fW(k)(xj)]−∇W`[fW(0)(xj)]∥∥2︸ ︷︷ ︸ ≤O ( τ1/3L2 √ ωm log(m)
) + ∥∥∇W`[fW(0)(xj)]∥∥2︸ ︷︷ ︸
≤O (√ ωm ) · ∥∥∇W`[fW(k)(xi)]−∇W`[fW(0)(xi)]∥∥2︸ ︷︷ ︸ ≤O ( τ1/3L2 √ ωm log(m) ) }
≤ O ( ω7/6n1/3L3 6 √ log3(m)
mδλ20
) .
In the second inequality, Lemmas 4.4 and 4.6 are used, and in the last inequality, τ = O ( n√ω√
mδλ0 ) is plugged in. With this, using the fact that Frobenius norm of a matrix is bigger than the operator norm, we bound the term ‖H(k)−H(0)‖2 as follows:
‖H(k)−H(0)‖2 ≤ ‖H(k)−H(0)‖F ≤ O
( ω7/6n4/3L3 6 √ log3(m)
mδλ20
) .
Lemma 4.11. For some δ ∈ [0, 1], with probability at least 1− δ, ‖H∞L −H(0)‖2 ≤ O ( ωnL5/2 4 √ log(nL/δ) m )
Proof. For some δ ′ ∈ [0, 1], set ε = L3/2
4 √
log(L/δ ′ )
m from Theorem 3.1. of Arora et al. [2019b]. For any fixed i, j ∈ [n], we have
P [∣∣H∞i,j −Hi,j(0)∣∣ ≤ O(ωL5/2 4√ log(L/δ′ )m )] ≥ 1− δ′ .
After applying the union bound over all i, j ∈ [n], setting δ = δ ′
n2 , and using the fact that Frobenius norm of a 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-definite 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 A and B,
1. Suppose A is non-singular, then A B ⇐⇒ λmax(BA−1) ≤ 1 and A B ⇐⇒ λmax(BA −1) < 1, where λmax(·) 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 ui(k) = fW(k)(xi) and let u(k) =[ u1(k), u2(k), . . . , un(k) ]> . In order to achieve linear convergence rate of the training error, ‖u(k)− y‖22, we decompose the term as follows:
‖u(k + 1)− y‖22 = ∥∥u(k)− y + (u(k + 1)− u(k))∥∥2
2 = ‖u(k)− y‖22 − 2 ( u(k)− y )>( u(k + 1)− u(k) ) + ‖u(k + 1)− u(k)‖22 .
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 I(k)1 and I (k) 2 , respectively. We note that the first term I (k) 1 is related with a gram matrix H(k) and a second term I(k)2 can be controlled small enough in `2 sense with proper choices of the step size and the width of network.
2. A term ‖u(k + 1)− u(k)‖22 needs to be controlled small enough to ensure 2 ( u(k) −
y )>( u(k + 1)− u(k) ) > ‖u(k + 1)− u(k)‖22 so that the loss decreases.
3. It is shown that the distance between the gram matrix H(k) and the NTK matrix H∞L is close enough in terms of operator norm.
4. Lastly, we inductively show that the weights generated from gradient descent stay within a perturbation region B ( W(0), τ ) , irrespective with the number of iterations of algorithm,
We start the proof by analyzing the term u(k + 1)− u(k).
Step 1. Control on u(k + 1) − u(k). Recall ( Σ
(k) `,i ) jj = 1 ( 〈w(k)`,j ,x (k) `−1,i〉 ≥ 0 ) and we
introduce a diagonal matrix Σ̃(k)`,i , whose jth entry is defined as follows:( Σ̃
(k) `,i ) jj = ( Σ (k+1) `,i −Σ (k) `,i ) jj ·
〈w(k+1)`,j ,x (k+1) `−1,i 〉
〈w(k+1)`,j ,x (k+1) `−1,i 〉 − 〈w (k) `,j ,x (k) `−1,i〉
.
With this notation, the difference x(k+1)L,i − x (k) L,i can be rewritten via the recursive applications of Σ̃ (k) `,i :
x (k+1) L,i − x (k) L,i =
( Σ
(k) L,i + Σ̃ (k) L,i
)( W
(k+1) L x (k+1) L−1,i −W (k) L x (k) L−1,i ) = ( Σ
(k) L,i + Σ̃ (k) L,i
) W
(k+1) L
( x
(k+1) L−1,i − x (k) L−1,i
) + ( Σ
(k) L,i + Σ̃ (k) L,i
)( W
(k+1) L −W (k) L
) x
(k) L−1,i
= L∑ `=1 ( L∏ r=`+1 ( Σ (k) r,i + Σ̃ (k) r,i ) W(k+1)r )( Σ (k) `,i + Σ̃ (k) `,i )( W (k+1) ` −W (k) ` ) x (k) `−1,i
(24)
Then, we introduce following notations :
D (k) `,i = ( L∏ r=`+1 Σ (k) r,i W (k) r ) Σ (k) `,i , D̃ (k) `,i = ( L∏ r=`+1 ( Σ (k) r,i + Σ̃ (k) r,i ) W(k+1)r )( Σ (k) `,i + Σ̃ (k) `,i ) .
Now, we can write ui(k + 1)− ui(k) by noting that ui(k) = √ m · vTx(k)L,i:
ui(k + 1)− ui(k) = √ m · vT ( x (k+1) L,i − x (k) L,i ) = √ m · vT
L∑ `=1 D̃ (k) `,i ( W (k+1) ` −W (k) ` ) x (k) `−1,i (25)
= −η √ m · vT L∑ `=1 D (k) `,i ∇W` [ LS ( W(k) )] x
(k) `−1,i︸ ︷︷ ︸
I (k) 1,i
−η √ m · vT L∑ `=1 ( D̃ (k) `,i −D (k) `,i ) ∇W` [ LS ( W(k) )] x
(k) `−1,i︸ ︷︷ ︸
I (k) 2,i
Here, I(k)1,i can be rewritten as follows:
I (k) 1,i = −η
√ m · vT L∑ `=1 D (k) `,i n∑ j=1 ( uj(k)− yj ) ∇W` [ fW(k)(xj) ] x (k) `−1,i
= −η · n∑ j=1 ( uj(k)− yj ) · (√ m L∑ `=1 vTD (k) `,i ∇W` [ fW(k)(xj) ] x (k) `−1,i ) = −mη · n∑ j=1 ( uj(k)− yj ) · 1 m L∑ `=1 〈 ∇W` [ fW(k)(xi) ] ,∇W` [ fW(k)(xj) ]〉 Tr
= −mη · n∑ j=1 ( uj(k)− yj ) ·Hi,j(k).
For I(k)2,i , we need a more careful control. First, we pay our attention on bounding the term ‖v>(D̃(k)`,i −D (k) `,i )‖2 as follows: By triangle inequality, we have∥∥∥∥v>(D̃(k)`,i −D(k)`,i )∥∥∥∥
2
≤ ∥∥∥∥v>(D(k)`,i −D(0)`,i)∥∥∥∥
2
+ ∥∥∥∥v>(D̃(k)`,i −D(0)`,i)∥∥∥∥ 2 . (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, we know ‖Σ(k)r,i −Σ (0) r,i ‖0 ≤ O ( mτ2/3L ) and | ( Σ (k) r,i −Σ (0) r,i ) j,j | ≤ 1 for j ∈ [m]. Then, we can plug Σ′′r,i = Σ (k) r,i −Σ (0) r,i in the inequality of the fifth item of Lemma 4.3. So, the first term of the
R.H.S in (26) can be bounded by O ( τ1/3L2 √ ω log(m) ) .
The second term of the R.H.S in (26) can be similarly controlled as the first term. Observe that | ( Σ
(k) r,i +Σ̃ (k) r,i ) jj | ≤ 1, then we have | ( Σ (k) r,i +Σ̃ (k) r,i −Σ (0) r,i ) j,j | ≤ 2 for all j ∈ [m]. Note that by the
definition of Σ̃(k)r,i , we have ‖Σ̃ (k) r,i ‖0 = ‖Σ (k+1) r,i −Σ (k) r,i ‖0 ≤ ‖Σ (k+1) r,i −Σ (0) r,i ‖0+‖Σ (k) r,i −Σ (0) r,i ‖0 ≤ O ( mτ2/3L ) . Thus, by the triangle inequality, we have ‖Σ(k)r,i + Σ̃ (k) r,i − Σ (0) r,i ‖0 ≤ O ( mτ2/3L ) . These observations enable us to plug Σ′′r,i = Σ (k) r,i + Σ̃ (k) r,i −Σ (0) r,i in the inequality of the fifth item
of Lemma 4.3, and give the bound on the second term as O ( τ1/3L2 √ ω log(m) ) .
We have ‖v> ( D̃
(k) `,i − D (k) `,i ) ‖2 ≤ O ( τ1/3L2 √ ω log(m) ) . Now, we control the `2-norm of
the I(k)2 as follows:∥∥∥I(k)2 ∥∥∥ 2 ≤ n∑ i=1 ∣∣∣I(k)2,i ∣∣∣ ≤ η √ m ·
n∑ i=1 [ L∑ `=1 ∥∥∥∥v>(D̃(k)`,i −D(k)`,i )∥∥∥∥ 2︸ ︷︷ ︸
≤O(L2τ1/3 √ ω log(m))
· ∥∥∥∇W`[LS(W(k))]∥∥∥
2 · ∥∥∥x(k)`−1,i∥∥∥ 2︸ ︷︷ ︸
≤O(1) : Lemma 4.2
]
≤ O ( ηnL2τ1/3 √ ωm log(m) ) L∑ `=1 ∥∥∥∇W`[LS(W(k))]∥∥∥ 2
≤ O ( ηnL5/2τ1/3 √ ωm log(m) )√√√√ L∑ `=1
∥∥∇W`[LS(W(k))]∥∥2F ≤ O ( ηnL5/2τ1/3 √ ωm log(m)
)√√√√ n∑ j=1 ( uj(k)− yj )2 L∑ `=1
∥∥∇W`[fW(k)(xj)]∥∥2F ≤ O ( ηnL3τ1/3ωm √ log(m) ) ‖u(k)− y‖2 . (27)
Step 2. Control on ‖u(k + 1)−u(k)‖22. Recall that by (25), x (k+1) L,i −x (k) L,i can be written as follows:
x (k+1) L,i − x (k) L,i = L∑ `=1 D̃ (k) `,i ( W (k+1) ` −W (k) ` ) x (k) `−1,i
= −η · L∑ `=1 D̃ (k) `,i ∇W` [ LS ( W(k) )] x (k) `−1,i.
It is worth noting that,
∥∥∥∇W`[LS(W(k))]∥∥∥2 2 = ∥∥∥∥∥∥ n∑ j=1 ( uj(k)− yj ) ∇W` [ fW(k)(xj) ]∥∥∥∥∥∥ 2
2 ≤ n∑ j=1 ( uj(k)− yj )2 n∑ j=1 ∥∥∇W`[fW(k)(xj)]∥∥22 ≤ O(nmω) ‖u(k)− y‖22 . (28)
Also, observe that | ( Σ
(k) r,i + Σ̃ (k) r,i ) jj | ≤ 1 for all j ∈ [m], so by Lemma A.3 of Zou et al. [2020], we
know ‖D̃(k)`,i ‖2 ≤ O (√ L ) . Combining all the facts, we can conclude:
‖u(k + 1)− u(k)‖22 = m · n∑ i=1 ( vTx (k+1) L,i − v Tx (k) L,i )2 ≤ m · ‖v‖22
n∑ i=1 ∥∥∥x(k+1)L,i − x(k)L,i∥∥∥2 2
≤ η2m · ‖v‖22 n∑ i=1 [ L∑ `=1 ∥∥∥D̃(k)`,i ∥∥∥2 2 · ∥∥∥∇W`[LS(W(k))]∥∥∥2 2 · ∥∥∥x(k)`−1,i∥∥∥2 2 ] ≤ O ( η2n2L2m2ω2 ) ‖u(k)− y‖22
≤ O ( η2n2L2m2 ) ‖u(k)− y‖22 , (29)
where in the third inequality, we additionally used the fact ‖v‖22 = O(ω) with probability at least 1− exp(−Ω(m)), and the inequality (28). In the last inequality, we used the assumption ω ≤ 1.
Step 3. λmin ( H(k) ) ≥ λ02 with sufficiently large m. Denote ρ(A) as a sprectral radius of a matrix A. Then, we have
‖H(k)−H∞L ‖2 ≥ ρ ( H(k)−H∞L ) ≥ −λmin ( H(k)−H∞L
) ≥ λmin ( H∞L ) − λmin ( H(k)
) ≥ λ0 − λmin ( H(k) ) , (30)
where, in the second inequality, we used a triangle inequality, λmin ( H(k) −H∞L ) + λmin ( H∞L ) ≤
λmin ( H(k) ) . By Lemmas 4.10 and 4.11, setting m ≥ Ω ( ω7n8L18 log
3(m) λ80δ
) and Õ ( λ 4/3 0 δ 1/3
n4/3L4
) ≤
ω ≤ 1, we have
‖H(k)−H∞L ‖2 ≤ ‖H(k)−H(0)‖2 + ‖H(0)−H ∞ L ‖2
≤ O ( ω7/6n4/3L3 6 √ log3(m)
mδλ20
) +O ( ωn2L5/2 4 √ log(nL/δ)
m
)
≤ O ( ω7/6n4/3L3 6 √ log3(m)
mδλ20
)
≤ λ0 2 . (31)
Thus, combining (30) and (31) yields that λmin ( H(k) ) ≥ λ02 .
Step 4. Concluding the proof. Recall that I(k)1 = −mη · H(k)(u(k) − y). Then observe that
(u(k)− y)>I(k)1 = −ηm · (u(k)− y)>H(k)(u(k)− y) ≤ −ηm · λmin ( H(k) ) ‖u(k)− y‖22
≤ −ηm · λ0 2 ‖u(k)− y‖22 . (32)
We set the step size η, radius of perturbation region τ and network width m as follows,
η = Ω
( λ0
n2L2m
) ,
τ = O ( n √ ω√
mδλ0
) ,
m ≥ Ω ( ω7n8L18 log3(m)
λ80δ
) .
With the above settings, we can control the ‖u(k + 1) − y‖22 by combining (27), (29) and (32) as follows,
‖u(k + 1)− y‖22 = ∥∥u(k)− y + (u(k + 1)− u(k))∥∥2
2 = ‖u(k)− y‖22 − 2ηm · ( u(k)− y )> H(k) ( u(k)− y ) − ( u(k)− y )> I (k) 2 + ‖u(k + 1)− u(k)‖ 2 2
≤ ( 1− ηmλ0 +O ( ηnL3τ1/3mω √ log(m) ) +O ( η2n2L2m2 )) ‖u(k)− y‖22
≤ (
1− ηmλ0 2
) ‖u(k)− y‖22 .
So far, we have shown from Step 1 to Step 4 that given the radius of perturbation region τ has the order O ( n√ω√ mδλ0 ) , then we can show the training error drops linearly to 0 with the discount factor (1 − ηmλ02 ) along with the proper choices of η and m. It remains us to prove the iterates W (k) `
for all ` ∈ [L] generated by GD algorithm indeed stay in the perturbation region B ( W(0), τ ) over
k ≥ 0 with τ = O ( n√ω√
mδλ0
) .
Step 5. The order of the radius of perturbation region. We employ the induction process for the proof. The induction hypothesis is : ∀s ∈ [k + 1],
∥∥∥W(s)` −W(0)` ∥∥∥ 2 ≤ η · O (√ nmω ) s−1∑ t=0 ( 1− ηmλ0 2 ) t 2 O (√ n δ ) ≤ O ( n √ ω√ mδλ0 ) . (33)
First, it is easy to see it holds for s = 0. Now, suppose it holds for s = 0, . . . , k, we consider s = k + 1.∥∥∥W(k+1)` −W(k)` ∥∥∥ 2 = ∥∥∥∇W`[LS(W(k))]∥∥∥ 2
= η · ∥∥∥∥∥∥ n∑ j=1 ( uj(k)− yj ) ∇W` [ fW(k)(xj) ]∥∥∥∥∥∥ 2
≤ η · √√√√ n∑ j=1 ∥∥∇W`[fW(k)(xj)]∥∥22 √√√√ n∑ j=1 ( uj(k)− yj
)2 ≤ η · O (√ nmω )√ 2LS ( W(k)
) ≤ η · O (√ nmω )( 1− ηmλ0
2
) k 2 O (√ n
δ
) , (34)
where in the second inequality, we used Lemmas 4.4. Note that since it is assumed that
W (k) ` ∈ B
( W(0), τ ) , the Lemma is applicable with m ≥ Ω ( ω7n8L18 log
3(m) λ80δ
) . Simi-
larly, since it is assumed that the induction hypothesis holds for s = 0, . . . , k, we can see ‖u(k) − y‖22 ≤ ( 1 − ηmλ02 )k‖u(0) − y‖22. This inequality is plugged in the last inequality with Lemma 4.9.
By combining the inequalities (33) for s ∈ [k] and (34), and triangle inequality, we conclude the proof:
∥∥∥W(k+1)` −W(0)` ∥∥∥ 2 ≤ η · O (√ nmω ) k∑ t=0 ( 1− ηmλ0 2 ) t 2 O (√ n δ ) ≤ O ( n √ ω√ mδλ0 ) .
Proposition 5.1. For some δ ∈ [0, 1], if we set the width of the network as m ≥ Ω ( ω7n8L18 log
3(m) λ80δ 2
) , and we set the step-size of gradient descent as η = O ( λ0
n2L2m
) . Then,
with probability at least 1 − δ over the randomness of initialized parameters W(0), we have for k = 0, 1, 2, . . . ,
u(k)− y = ( I− ηmH∞L )k( u(0)− y ) + ξ(k),
where
‖ξ(k)‖2 = k (
1− ηmλ0 2
)k−1 O ( ηm · ω7/6n4/3L3 6 √ log3(m)
mλ20δ
) ‖y − u(0)‖2 .
Proof. Define ui(k) := fW(k)(xi), then we have u(k + 1)− u(k) = −ηm ·H(k) ( u(k)− y ) + I
(k) 1 = −ηm ·H∞L ( u(k)− y ) − ηm · ( H(k)−H∞L )( u(k)− y ) + I (k) 1
= −ηm ·H∞L ( u(k)− y ) + e(k).
By recursively applying the above equality, we can easily derive a following for any k ≥ 0,
u(k)− y = ( I− ηmH∞L )k( u(0)− y ) + k−1∑ t=0 ( I− ηmH∞L )t e(k − 1− t)︸ ︷︷ ︸
=ξ(k)
. (35)
Now, we want to show ξ(k) can be controlled in arbitrarily small number. First, e(k) needs to be bounded in an `2 norm:
‖e(k)‖2 ≤ ηm ‖H ∞ L −H(k)‖2 ‖u(k)− y‖2 + ∥∥∥I(k)2 ∥∥∥ 2
≤ ηm · O ( ω7/6n4/3L3 6 √ log3(m)
mλ20δ
) ‖u(k)− y‖2 ,
where, in the second inequality, τ = O ( n √ ω√
mδλ0
) is plugged in (27). Equipped with the bound on
‖e(k)‖2, we can easily bound the ‖ξ(k)‖2 as follows:∥∥∥∥∥ k−1∑ t=0 ( I− ηmH∞L )t e(k − 1− t) ∥∥∥∥∥ 2
≤ k−1∑ t=0 ‖I− ηmH∞L ‖ t 2 ‖e(k − 1− t)‖2 ≤ k−1∑ t=0 ( 1− ηmλ0 )t O ( ηm · ω7/6n4/3L3 6 √ log3(m) mλ20δ ) ‖u(k − 1− t)− y‖2 ≤ k−1∑ t=0 ( 1− ηmλ0 )t O ( ηm · ω7/6n4/3L3 6 √ log3(m) mλ20δ )( 1− ηmλ0 2 )k−1−t ‖u(0)− y‖2
= k ( 1− ηmλ0
2
)k−1 O ( ηm · ω7/6n4/3L3 6 √ log3(m)
mλ20δ 2
) ‖u(0)− y‖2 . (36)
Note that in the third inequality, we used the result from Theorem 1.
F PROOF OF THEOREM 3.8
We begin the proof by decomposing the error f̂W(k)(x)− f∗(x) for any fixed x ∈ Unif(Sd−1) into two terms as follows:
f̂W(k)(x)− f∗(x) = ( f̂W(k)(x)− g∗(x) )︸ ︷︷ ︸ ∆1 + ( g∗(x)− f∗(x) )︸ ︷︷ ︸ ∆2 . (37)
Here, we denote the solution of kernel regression with kernel H∞L as g ∗(x), which is a minimum RKHS norm interpolant of the noise-free data set {xi, f?ρ (xi)}ni=1. To avoid the confusion of the notation, we write Ker(x,X) = ( H∞L (x,x1), . . . ,H ∞ L (x,xn) )n i=1 ∈ Rn and let y∗ = [f?ρ (x1), . . . , f ? ρ (xn)] >. Then, we have a following closed form solution g∗(x) as,
g∗(x) := Ker(x,X) ( H∞L )−1 y∗.
With the decomposition (37), the proof sketch of Theorem 3.8 is as follows.
1. Note that for any ` ∈ [L], we have f̂W(k)(x) = 〈vec ( ∇W` [ fW(k)(x) ]) , vec ( W (k) ` ) 〉. We
can write the term vec ( W
(k) `
) with respect to vec ( W
(0) ` ) , H∞L 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), we can further decompose ∆1 into three terms. That is, ∆1 = ∆11 + ∆12 + ∆13. Then, using the boundedness of `2-norm of network gradient and the fact that the size of ‖ξ(k)‖2 can be controlled with wide enough network, we can control the size of ‖∆12‖2 and ‖∆13‖2 aribtarily small.
2. In the term ∆2, the g? is an interpolant based on noiseless data. For large enough data points, g? converges fastly to f? at the rate OP( 1√n ).
3. Lastly, the ∆11 is the only term that is involved with random error ε, and we show that ‖∆11‖2 is bounded away from 0 for small and large GD iteration index k.
Step 1. Control on ∆1. For n data points ( x1, . . . ,xn ) and for the kth updated parameter W(k), denote:
∇W` [ fW(k)(X) ] = [ vec ( ∇W` [ fW(k)(x1) ]) , · · · , vec ( ∇W` [ fW(k)(xn) ])] .
Note that when ` = 1, ∇W` [ fW(k)(X) ] ∈ Rmd×n and when ` = 2, . . . , L, ∇W` [ fW(k)(X) ] ∈ Rm2×n. With this notation, we can rewrite the Gradient Descent update rule as
vec ( W
(k+1) `
) = vec ( W
(k) ` ) − η∇W` [ fW(k)(X) ]( u(k)− y ) , k ≥ 0.
Applying Proposition 3.8, we can get : vec ( W
(k) `
) − vec ( W
(0) ` ) =
k−1∑ j=0 ( vec ( W (j+1) ` ) − vec ( W (j) ` ))
= −η · k−1∑ j=0 ∇W` [ fW(j)(X) ]( u(j)− y ) = η ·
k−1∑ j=0 ∇W` [ fW(j)(X) ]( I− ηmH∞L )j( y − u(0) ) − η · k−1∑ j=0 ∇W` [ fW(k)(X) ] ξ(j)
= η · k−1∑ j=0 ∇W` [ fW(0)(X) ]( I− ηmH∞L )j( y − u(0) ) − η · k−1∑ j=0 ∇W` [ fW(k)(X) ] ξ(j)
+ η · k−1∑ j=0 ([ ∇W` [ fW(j)(X) ] −∇W` [ fW(0)(X) ]]( I− ηmH∞L )j( y − u(0) ))
= η · k−1∑ j=0 ∇W` [ fW(0)(X) ]( I− ηmH∞L )j( y − u(0) ) + ξ ′ (k). (38)
First, we control `2-norm of the first term of ξ ′ (k) as follows: Note that ‖∇W` [ fW(j)(X) ] ‖F ≤
O (√ nmω ) by Lemma 4.4 for 0 ≤ j ≤ k − 1. Then, we have∥∥∥∥∥∥η · k−1∑ j=0 ∇W` [ fW(j)(X) ] ξ(j) ∥∥∥∥∥∥ 2
≤ k−1∑ j=0 O ( η √ nmω ) O ( j ( 1− ηmλ0 2 )j−1) O ( ηm · ω7/6n4/3L3 6 √ log3(m) mλ20δ ) ‖y − u(0)‖2
≤ O ( n11/6L3ω5/3
m2/3λ 7/3 0 δ 1/6
√ log(m) ) ‖y − u(0)‖2 . (39)
In the second inequality, ∑∞ j=1 j ( 1− ηmλ02 )j = O ( 1
η2m2λ20
) is used. Then, we control `2-norm of
the second term of ξ ′ (k) as follows:
∥∥∥∥∥∥η · k−1∑ j=0 [ ∇W` [ fW(j)(X) ] −∇W` [ fW(0)(X) ]]( I− ηmH∞L )j( y − u(0) )∥∥∥∥∥∥ 2 ≤ k−1∑ j=0 η ‖I− ηmH∞L ‖ j 2 ‖y − u(0)‖2 √√√√ n∑ i=1
∥∥∇W`[fW(j)(xi)]−∇W`[fW(0)(xi)]∥∥22 ≤ k−1∑ j=0 η ( 1− ηmλ0 )jO(n1/3m1/3L2ω2/3 λ 1/3 0 δ 1/6 √ log(m) ) O (√ n ) ‖y − u(0)‖2
≤ O ( n5/6L2ω2/3
m2/3λ 4/3 0 δ 1/6
√ log(m) ) ‖y − u(0)‖2 , (40)
where in the second inequality, we used Lemmas 4.6 with τ = O ( n√ω√
mδλ0
) .
Now, we are ready to control ∆1 term. By using the equality (38), we can decompose the term ∆1 as follows: Let us denote Gk = ∑k−1 j=0 ηm ( I − ηmH∞L )j . Note that for any ` ∈ [L], f̂W(k)(x) =
〈vec ( ∇W` [ fW(k)(x) ]) , vec ( W (k) ` ) 〉 and recall that y = y∗ + ε. Then, for any fixed `′ ∈ [L], we have:
∆1 = [〈 vec ( ∇W
` ′
[ fW(k)(x) ]) , vec ( W (k)
`′
)〉 −Ker(x,X) ( H∞L )−1 y∗ ]
+ Ker(x,X)Gky −Ker(x,X)Gky
= [ Ker(x,X) [ Gk − ( H∞L )−1] y∗ + Ker(x,X)Gkε ] ︸ ︷︷ ︸
=∆11
+
[ 1
m L∑ `=1 vec ( ∇W` [ fW(k)(x) ])>∇W`[fW(0)(X)]−Ker(x,X)]Gky − 1 m ∑ `:` 6=`′ vec ( ∇W` [ fW(k)(x)
])>∇W`[fW(0)(X)]Gky︸ ︷︷ ︸ =∆12
+ [〈 vec ( ∇W
` ′
[ fW(k)(x) ]) , vec ( W (0)
`′
)〉 + vec ( ∇W
` ′
[ fW(k)(x) ])> ξ ′ (k)
− 1 m
vec ( ∇W
` ′
[ fW(k)(x) ])>∇W ` ′ [ fW(0)(X) ] Gku(0) ] .︸ ︷︷ ︸
=∆13
(41)
Our goal in this step is to control ‖∆12‖2 and ‖∆13‖2. Then, in the third step, we will show ‖∆11‖2 is the term, which governs the behavior of the prediction risk with respect to algorithm iteration k.
First, we bound the `2 norm of the first term in ∆12 as: ∥∥∥∥∥ [ 1 m L∑ `=1 vec ( ∇W` [ fW(k)(x) ])>∇W`[fW(0)(X)]−Ker(x,X)]Gky ∥∥∥∥∥
2
≤ 1 mL L∑ `=1 ∥∥vec(∇W`[fW(k)(x)])− vec(∇W`[fW(0)(x)])∥∥2︸ ︷︷ ︸ ≤O ( τ1/3L2 √ ωm log(m) ) : Lemma 4.6 ∥∥∇W`[fW(0)(X)]∥∥F︸ ︷︷ ︸ ≤O (√ ωnm ) : Lemma 4.4 ‖Gky‖2
+ 1
L √√√√ n∑ i=1 ( 1 m L∑ `=1 〈 ∇W` [ fW(0)(x) ] ,∇W` [ fW(0)(xi) ]〉 Tr −Ker(x,xi) )2 ‖Gky‖2
≤ { O ( n5/6L2ω7/6
m1/6δ1/6λ 1/3 0
√ log(m) ) +O ( ωn1/2L3/2 4 √
log(nL/δ) m )} ‖Gk‖2 ‖y‖2
≤ O ( n5/6L2ω7/6
m1/6δ1/6λ 4/3 0
√ log(m) · ‖y‖2 ) +O ( ωn1/2L3/2
λ0
4 √
log(nL/δ) m · ‖y‖2
) , (42)
where, in the second inequality, we plugged τ = O ( n√ω√
mδλ0
) in the result of Lemma 4.6 and used
Lemma 4.11. In the last inequality, we used ‖Gk‖2 ≤ O ( 1 λ0 ) . Similarly, we can control the `2 norm of the second term in ∆12 as follows:∥∥∥∥∥∥ 1m ∑ `:` 6=`′ vec ( ∇W` [ fW(k)(x) ])>∇W`[fW(0)(X)]Gky ∥∥∥∥∥∥
2
≤ 1 m ∑ `:` 6=`′ ‖vec ( ∇W` [ fW(k)(x) ]) ‖2︸ ︷︷ ︸
≤O (√ ωm ) · ‖∇W`
[ fW(0)(X) ] ‖F︸ ︷︷ ︸
≤O (√ ωmn ) · ‖Gk‖2︸ ︷︷ ︸ ≤O (
1 λ0 ) ‖y‖2 ≤ O ( ωL √ n
λ0
) · ‖y‖2. (43)
We turn our attention to controlling ‖∆13‖2. The first term in ∆13; Recall that∥∥∥vec(∇W ` ′ [ fW(k)(x) ])∥∥∥ 2 ≤ O (√ mω ) by Lemma 4.4. Then, the random variable
vec ( ∇W` [ fW(k)(x) ])>vec(W(0)` ) is simply a N (0,O(ω)) for 1 ≤ ` ≤ L. A straightforward application of Chernoff bound for normal random variable and taking union bound over the layer 1 ≤ ` ≤ L yield that: with probability at least 1− δ,
∣∣∣vec(∇W ` ′ [ fW(k)(x) ])>vec(W(0) `′ )∣∣∣ ≤ O(√ω log(L δ )) . (44)
The `2 norm of the third term in ∆13 can be bounded as follows:∥∥∥∥ 1mvec(∇W`′ [fW(k)(x)])>∇W`′ [fW(0)(X)]Gku(0) ∥∥∥∥
2
≤ 1 m ∥∥∥vec(∇W ` ′ [ fW(k)(x) ])∥∥∥ 2︸ ︷︷ ︸
≤O (√ mω )
∥∥∥∇W ` ′ [ fW(0)(X) ]∥∥∥ F︸ ︷︷ ︸
≤O (√ ωmn ) ‖Gku(0)‖2︸ ︷︷ ︸≤O(√nωλ0δ )
≤ O ( nω3/2
λ0δ
) . (45)
In the last inequality, we used the Lemma 4.8 and ‖Gk‖2 ≤ O ( 1 λ0 ) . By combin-
ing (39), (40), (44), (45) with ∥∥∥∇W
` ′
[ fW(0)(x) ]∥∥∥ F ≤ O (√ mω ) , we have a following :
‖∆13‖2 ≤ ∥∥∥〈vec(∇W
` ′
[ fW(k)(x) ]) , vec ( W (0)
`′ )〉∥∥∥ 2 + ∥∥∥(vec(∇W ` ′ [ fW(0)(x) ]))> ξ′(k) ∥∥∥ 2
+ ∥∥∥∥ 1m(vec(∇W`′ [fW(0)(x)])>∇W`′ [fW(0)(X)]Gku(0) ∥∥∥∥
2
≤ O (√ ω log ( L
δ
)) +O ( n11/6L3ω13/6 ‖y − u(0)‖2
m1/6λ 4/3 0 δ 1/6
√ log(m)
)
+O
( n5/6L2ω7/6 ‖y − u(0)‖2
m1/6λ 7/3 0 δ 1/6
√ log(m) ) +O ( nω3/2
λ0δ
)
= O
( n11/6L3ω13/6 ‖y − u(0)‖2
m1/6λ 4/3 0 δ 1/6
√ log(m) ) +O ( n5/6L2ω7/6 ‖y − u(0)‖2
m1/6λ 7/3 0 δ 1/6
√ log(m)
)
+O
( nω3/2
λ0δ
) . (46)
Step 2. Control on ∆2. First, note that there is a recent finding that the reproducing kernel Hilbert spaces of NTKs with any number of layers (i.e., L ≥ 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 :
‖∆2‖2 = OP (
1√ n
) . (47)
Step 3. The behavior of L2 risk is characterized by the term ∆11. Recall the decompositions (37) and (41), then we have:
f̂W(k)(x)− f∗(x) = ∆11 + ( ∆12 + ∆13 + ∆2 ) := ∆11 + Θ. (48)
Our goal in this step is mainly two-folded: (i) Control Eε ‖Θ‖22 arbitrarily small with proper choices of step-size of GD η and width of the network m. (ii) Show that how Eε ‖∆11‖22 affect the behavior of prediction risk over the GD iterations k. First, note that we have
Eε ‖y‖22 = Eε ‖y ∗ + ε‖22 ≤ 2
( y∗ )>
y∗ + 2Eε ‖ε‖22 = O(n). (49) Second, recall Lemma 4.9 and note that over the random initialization, with probability at least 1−δ,
Eε ‖y − u(0)‖22 ≤ O ( n
δ
) . (50)
Now, by combining the bounds (42), (46) and (47), we have Eε ‖Θ‖22 ≤ 3Eε ( ‖∆12‖22 + ‖∆13‖ 2 2 + ‖∆2‖ 2 2 ) ≤ Eε [ O ( n5/3L4ω7/3
m1/3λ 8/3 0 δ
1/3 log(m) · ‖y‖22
) +O ( ω2nL3
λ20
√ log(nL/δ)
m · ‖y‖22
)
+O
( n11/3L6ω13/3 ‖y − u(0)‖22
m1/3λ 8/3 0 δ
1/3 log(m)
) +O ( n5/3L4ω7/3 ‖y − u(0)‖22
m1/3λ 14/3 0 δ
1/3 log(m)
)]
+O
( n2ω3
λ20δ 2
) +O ( 1
n
)
≤ O ( ω2n2L3
λ20
√ log(nL/δ)
m
) +O ( n14/3L6ω13/3
m1/3λ 8/3 0 δ
4/3 log(m)
) +O ( n8/3L4ω7/3
m1/3λ 14/3 0 δ
4/3 log(m)
)
+O
( n2ω3
λ20δ 2
) +O ( 1
n
) , (51)
where in the third inequality, we used (49) and (50).
Case 1. When k is large, the L2 risk is bounded away from zero by some constant.
Now we control Eε ‖∆11‖22. Recall the definitions ‖f‖ 2 2 := ∫ x∈Sd−1 |f(x)| 2dx and
Gk = ∑k−1 j=0 ηm ( I− ηmH∞L )j . Let us denote S = y∗y∗>. Then, we have
Eε ‖∆11‖22 = ∫ x∈Sd−1 Ker(x,X) [( Gk − ( H∞L )−1) y∗y∗> ( Gk − ( H∞L )−1) +G2k ] Ker(X, x)dx
= ∫ x∈Sd−1 Ker(x,X) ( H∞L )−1 Mk ( H∞L )−1Ker(X, x)dx where
Mk = ( I− ηmH∞L )k S ( I− ηmH∞L )k + ( I− ( I− ηmH∞L )k)2 = [( I− ηmH∞L )k − (S + I)−1](S + I)[(I− ηmH∞L )k − (S + I)−1]+ I − (S + I)−1.
For the algorithm iterations k ≥ ( log(n) ηmλ0 ) C0 with some constant C0 > 1, we have(
I − ηmH∞L )k (1− ηmλ0)k · I exp(−ηmλ0k) · I exp(−C0 log(n)) = 1
nC0 · I.
Since 1 + ‖y‖22 ≤ C1n for some constant C1, we have
λmax
( 1
nC0 · ( S + I )) = 1 + ‖y‖22 nC0 ≤ C1 nC0−1 < 1. (52)
Using the first item of Lemma (4.12) with the inequality (52), we have( I − ηmH∞L )k 1 nC0 · I ≺ ( S + I )−1 . (53) The above inequality (53) lead to a following result :( S + I
)−1 − (I − ηmH∞L )k (S + I)−1 − 1nC0 · I. (54) It is obvious that both ( S + I
)−1 − (I − ηmH∞L )k and (S + I)−1 − 1nC0 · I are positive definite matrices due to (54), and it is also easy to see that they are exchangeable. By using the second item of Lemma (4.12), we have
Mk = [( I− ηmH∞L )k − (S + I)−1](S + I)[(I− ηmH∞L )k − (S + I)−1]+ I − (S + I)−1
[( S + I )−1 − 1 nC0 · I ]( S + I )[( S + I )−1 − 1 nC0 · I ] + I − ( S + I )−1 = 1
n2C0 S +
( 1− 1
nC0
)2 · I.
Then, we have
Eε ‖∆11‖22 1
n2C0 A+
( 1− 1
nC0
)2 B c0B,
where c0 ∈ (0, 1) is a constant and A = ∫ x∈Sd−1 [ Ker(x,X) ( H∞L )−1 y∗ ]2 dx, and B = ∫ x∈Sd−1 [ Ker(x,X) ( H∞L )−1]2 dx.
(55)
By triangle inequality with the decomposition (48) and the bound on Eε ‖Θ‖22 in (51), we have: Eε ∥∥∥f̂W(k) − f∗∥∥∥2
2 = Eε ‖∆11 + Θ‖22
≥ 1 2 Eε ‖∆11‖2 − Eε ‖Θ‖ 2 2
≥ c0 2 B −O
( 1
n
) −O ( n2ω3
λ20δ 2
) − Õ ( 1
m1/3 poly
( ω, n, L, 1
λ0 ,
1
δ
)) . (56)
For the third term in (56), we can choose ω ≤ C2 ( λ0δ n )2/3 for some constant C2 > 0 such that
the term can be bounded by c08 ∥∥∥Ker(·,X)(H∞L )−1∥∥∥2
2 . Similarly, the width m can be chosen large enough such that the fourth term in (56) is upper-bounded by c08 ‖Ker(·,X) ( H∞L )−1‖22. Using the above choices of k, ω, and m, we can further bound (56):
Eε ∥∥fW(k) − f∗∥∥22 ≥ c04 ∥∥∥Ker(·,X)(H∞L )−1∥∥∥22 −O ( 1 n ) . (57)
Note that Eε‖f̂∞ − g∗‖22 = ‖Ker(·,X) ( H∞L )−1‖22 where g∗ := 0 and f̂∞ denotes the noise interpolator. Then, by Theorem 4.2. of Hu et al. [2021], we know that Eε‖f̂∞−g∗‖22 ≥ c1 for some constant c1 > 0. Then, we can take n large enough such that the term O ( 1 n ) is upper-bounded by c0c1 8 , and finish the proof.
Case 2. When k is small, the L2 risk is bounded away from zero by some constant.
Recall the definition of ∆11 in the decomposition (41), ∆11 := Ker(x,X)Gk [ y∗ + ε ] −Ker(x,X)H∞L y∗ := ∆∗11 −Ker(x,X)H∞L y∗. (58) We denote the eigen-decomposition of the matrix H∞L := ∑n i=1 λivivi
>, then we can easily see a following:
Gk = ηm k−1∑ j=0 ( n∑ i=1 (1− ηmλi)jvivi> ) ηm k−1∑ j=0 n∑ i=1 vivi > ηmk · I.
By using the above inequality, we have
Eε ‖∆∗11‖ 2 2 = ∫ x∈Sd−1 Ker(x,X)Gk ( S + I ) GkKer(X, x)dx
≤ η2m2k2 (∫
x∈Sd−1
[ Ker(x,X)y∗ ]2 dx+ ‖Ker(·,X)‖22 ) = O ( η2m2k2ω2n2L2 ) .
Recall the decompositions (37) and (41), then we have: Eε ∥∥∥f̂W(k) − f∗∥∥∥2
2 = Eε ‖∆∗11 + Θ−Ker(·,X)H∞L y∗‖ 2 2
≥ 1 2 ‖Ker(·,X)H∞L y∗‖ 2 2 − Eε ‖∆ ∗ 11 + Θ‖ 2 2 ≥ 1 2 ‖Ker(·,X)H∞L y∗‖ 2 2 − 2Eε ‖∆ ∗ 11‖ 2 2 − 2Eε ‖Θ‖ 2 2
≥ 1 2 ‖Ker(·,X)H∞L y∗‖ 2 2 −O
( η2m2k2ω2n2L2 ) −O ( 1
n ) −O ( n2ω3
λ20δ 2
) − Õ ( 1
m1/3 poly
( ω, n, L, 1
λ0 ,
1
δ
)) . (59)
For some constant C ′ 1 > 0, let k ≤ C ′ 1
( 1
ηmnωL
) such that the second term in the bound (59) can be
bounded by 18‖Ker(·,X) ( H∞L )−1 y∗‖22. For the fourth term in (59), we can choose ω ≤ C ′ 2 ( λ0δ n )2/3 for some constant C ′
2 > 0 such that the term can be bounded by 1 8 ∥∥∥Ker(·,X)(H∞L )−1y∗∥∥∥2 2 . Sim-
ilarly, the width m can be chosen large enough such that the fifth term in (59) is upper-bounded by 1 8‖Ker(·,X) ( H∞L )−1 y∗‖22. Using the above choices of k, ω, and m, we can further bound (59):
Eε ∥∥fW(k) − f∗∥∥22 ≥ 14 ∥∥∥Ker(·,X)(H∞L )−1y∗∥∥∥22 −O ( 1 n ) ≥ C ′ 3 ∥∥f?ρ∥∥22 −O( 1n ) . (60)
In the second inequality, we used (47) with triangle inequality. In the third inequality, we can take n large enough such that the term O (
1 n
) is upper-bounded by C ′ 3
2 ∥∥f?ρ∥∥22. Lastly, by using the assumption that f?ρ is a square-integrable function, we finish the proof.
G PROOF OF THEOREM 3.11-TRAINING ERROR
For the convenience of notation, we denote uD,i(k) = fW(k)D (xi) and let uD(k) =[ u1,D(k), . . . , un,D(k) ]>
. In order to analyze the training error of `2-regularized estimator, ‖uD(k)− y‖22, we decompose the term as follows:
‖uD(k + 1)− y‖22 = ‖uD(k + 1)− (1− η2µL)uD(k)‖ 2 2 + ‖(1− η2µL)uD(k)− y‖ 2 2 − 2 ( y − (1− η2µL)uD(k) )>( uD(k + 1)− (1− η2µL)uD(k) ) (61)
Equipped with this decomposition, the proof consists of the following steps:
1. We decompose the decayed prediction difference uD(k+ 1)− (1− η2µL)uD(k) into two terms. We note that the first term is related with a gram matrix HD(k) and denote a second term as I(k)D .
2. The term I(k)D can be further decomposed into three terms, where we denote them as I (k) 2,D,
I (k) 3,D and I (k) 5,D. The crux for controlling the `2-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 (k)D,` − W (0) D,`‖2 is sufficiently small
enough for large enough m. 3. Given the decomposition (61), we further decompose it into four terms as follows:
(61) = ‖(1− η2µL)uD(k)− y‖22︸ ︷︷ ︸ :=T1 + ‖uD(k + 1)− (1− η2µL)uD(k)‖22︸ ︷︷ ︸ :=T2
+ 2mη1 ( y − (1− η2µL)uD(k) )> HD(k) ( uD(k)− y )︸ ︷︷ ︸ :=T3
−2 ( y − (1− η2µL)uD(k) )> I (k) D︸ ︷︷ ︸
:=T4
. (62)
In this step, we obtain the upper-bound of ‖Ti‖2 for i = 1, 2, 3, 4 obtained in Step 4. 4. We combine the upper-bounds of ‖Ti‖2 for i = 1, 2, 3, 4 in step 3 and obtain the bound on ‖uD(k + 1)− y‖22 with respect to ‖uD(k)− y‖22 and ‖y‖2.
5. Lastly, we inductively show that the weights generated from regularized gradient descent stay within a perturbation region B ( W(0), τ ) , irrespective with the number of iterations of
algorithm.
We start the proof by analyzing the term u(k + 1)− (1− η2µL)u(k).
Step 1. Dynamics of uD(k + 1)−(1−η2µL)·uD(k). Recall ( Σ (k) D,`,i ) jj = 1 ( 〈w(k)D,`,j ,x (k) D,`−1,i〉 ≥
0 )
and we introduce a diagonal matrix Σ̃(k)D,`,i, whose jth entry is defined as follows:
( Σ̃
(k) D,`,i ) jj = ( Σ (k+1) D,`,i −Σ (k) D,`,i ) jj ·
〈w(k+1)D,`,j ,x (k+1) D,`−1,i〉
〈w(k+1)D,`,j ,x (k+1) D,`−1,i〉 − 〈w (k) D,`,j ,x (k) D,`−1,i〉
.
With this notation, the difference x(k+1)D,L,i − x (k) D,L,i can be rewritten via the recursive applications of Σ̃ (k) D,`,i: Then, we introduce following notations :
D (k) D,`,i = ( L∏ r=`+1 Σ (k) D,r,iW (k) D,r ) Σ (k) D,`,i, D̃ (k) D,`,i = ( L∏ r=`+1 ( Σ (k) D,r,i + Σ̃ (k) D,r,i ) W (k+1) D,r )( Σ (k) D,`,i + Σ̃ (k) D,`,i ) .
Now, we can write uD,i(k + 1)− uD,i(k) by noting that uD,i(k) = √ m · vTx(k)D,L,i:
uD,i(k + 1)− uD,i(k)
= √ m · vT ( x
(k+1) D,L,i − x (k) D,L,i ) = √ m · vT
L∑ `=1 D̃ (k) D,`,i ( W (k+1) D,` −W (k) D,` ) x (k) D,`−1,i
= √ m · vT L∑ `=1 D̃ (k) D,`,i ( − η1∇W` [ LS ( W (k) D )] − η2µW(k)D,` + η2µW (0) D,` ) x (k) D,`−1,i
= −η1 √ m · vT L∑ `=1 D (k) D,`,i∇W` [ LS ( W (k) D )] x
(k) D,`−1,i︸ ︷︷ ︸
I (k) 1,D,i
−η1 √ m · vT L∑ `=1 ( D̃ (k) D,`,i −D (k) D,`,i ) ∇W` [ LS ( W (k) D )] x
(k) D,`−1,i︸ ︷︷ ︸
I (k) 2,D,i
−η2µ √ m · vT L∑ `=1 ( D̃ (k) D,`,i −D (k) D,`,i )( W (k) D,` −W (0) D,` ) x
(k) D,`−1,i︸ ︷︷ ︸
I (k) 3,D,i
−η2µ √ m · vT L∑ `=1 D (k) D,`,iW (k) D,`x
(k) D,`−1,i︸ ︷︷ ︸
I (k) 4,D,i
+η2µ √ m · vT L∑ `=1 D (k) D,`,iW (0) D,`x
(k) D,`−1,i︸ ︷︷ ︸
I (k) 5,D,i
(63)
where in the second equality, we used the recursive relation (24), and in the third equality, modified GD update rule (6) is applied.
Furthermore, I(k)1,D,i can be rewritten as follows:
I (k) 1,D,i = −η1
√ m · vT L∑ `=1 D (k) D,`,i n∑ j=1 ( uD,j(k)− yj ) ∇W` [ f W (k) D (xj) ] x (k) D,`−1,i
= −η1 · n∑ j=1 ( uD,j(k)− yj ) · (√ m L∑ `=1 vTD (k) D,`,i∇W` [ f W (k) D (xj) ] x (k) D,`−1,i ) = −mη1 · n∑ j=1 ( uD,j(k)− yj ) · 1 m L∑ `=1 〈 ∇W` [ f W (k) D (xi) ] ,∇W` [ f W (k) D (xj) ]〉 Tr
= −mη1 · n∑ j=1 ( uD,j(k)− yj ) ·HD,i,j(k). (64)
With I(k)4,i = (−η2µL) · uD,i(k) and (64), we can rewrite (63) as follows:
uD,i(k + 1)− (1− η2µL)uD,i(k) = −mη1 · n∑ j=1 ( uD,j(k)− yj ) ·HD,i,j(k) + I(k)2,D,i + I (k) 3,D,i + I (k) 5,D,i.
(65)
Step 2. Control of the size ∥∥∥I(k)D ∥∥∥
2 .
Let I(k)D = [I (k) 2,D,1 + I (k) 3,D,1 + I (k) 5,D,1, . . . , I (k) 2,D,n + I (k) 3,D,n + I (k) 5,D,1] >. Now, we control the bound on the ∥∥∥I(k)D ∥∥∥2
2 . Recall that in Eq. (27), we have ∥∥∥I(k)2,D∥∥∥ 2 ≤ O ( η1nL 3τ1/3ωm √ log(m) ) ‖uD(k)− y‖2 . (66)
Similarly, ∥∥∥I(k)3,D∥∥∥
2 can be bounded:
∥∥∥I(k)3,D∥∥∥ 2 ≤ n∑ i=1 ∣∣∣I(k)3,D,i∣∣∣ ≤ η2µ√m · n∑ i=1 [ L∑ `=1 ∥∥∥∥v>(D̃(k)D,`,i −D(k)D,`,i)∥∥∥∥ 2︸ ︷︷ ︸
≤O ( L2τ1/3 √ ω log(m)
) · ∥∥∥W(k)D,` −W(0)D,`∥∥∥ 2︸ ︷︷ ︸ ≤τ · ∥∥∥x(k)D,`−1,i∥∥∥ 2︸ ︷︷ ︸ ≤O(1)
]
≤ O ( η2µnL 3τ4/3 √ ωm log(m) ) . (67)
Lastly ∥∥∥I(k)5,D∥∥∥
2 can be bounded:
∥∥∥I(k)5,D∥∥∥ 2 ≤ n∑ i=1 ∣∣∣I(k)5,D,i∣∣∣ ≤
n∑ i=1 ∣∣∣∣∣η2µ√m · vT L∑ `=1 D (k) D,`,iW (k) D,`x (k) D,`−1,i ∣∣∣∣∣+ n∑ i=1 ∣∣∣∣∣η2µ√m · vT L∑ `=1 D (k) D,`,i ( W (k) D,` −W (0) D,` ) x (k) D,`−1,i ∣∣∣∣∣ ≤ η2µL ·
n∑ i=1 |ui,D(k)|+ η2µ √ m · n∑ i=1 [ L∑ `=1 ‖v‖2︸ ︷︷ ︸ ≤O( √ ω) · ∥∥∥D(k)D,`,i∥∥∥ 2︸ ︷︷ ︸ ≤O( √ L) · ∥∥∥W(k)D,` −W(0)D,`∥∥∥ 2︸ ︷︷ ︸ ≤τ · ∥∥∥x(k)D,`−1,i∥∥∥ 2︸ ︷︷ ︸ ≤O(1) ]
≤ O ( η2µnL √ ω log(L/δ) ) +O ( η2µnL 3/2τ √ mω ) , (68)
where in the last inequality, we employed the same logic used in (44) with the Lemma 4.2 to obtain the upper-bound on the |ui,D(k)|. We set the orders of the parameters µ, η1, η2, τ , and ω as follows:
µ = Θ ( n d−1 2d−1 ) , η1 = Θ ( 1
m n− 3d−2 2d−1
) , η2 = Θ ( 1
L n− 3d−2 2d−1
) ,
τ = O ( L √ ω√
mδ n
d 2d−1 ) , ω = O ( 1
L3/2 n− 5d−2 2d−1
) . (69)
Plugging the choices of parameters (69) with sufficiently large m in (66), (67) and (68) yields
∥∥∥I(k)D ∥∥∥ 2 ≤ O ( L37/12n− 9d−8 12d−6 √ log(m) m1/6δ1/3 ) · ‖uD(k)− y‖2 +OP ( 1 n2 ) . (70)
Step 3. Upper-bound of ‖Ti‖2 on i = 1, 2, 3, 4.
First, we work on getting the upper-bound on λmax ( HD(k) ) . By the Gershgorin’s circle theorem [Varga, 2004], we know the maximum eigenvalue of symmetric positive semi-definite matrix is upper-bounded by the maximum absolute column sum of the matrix. Using this fact, we can
bound the λmax ( HD(k) ) as :
λmax ( HD(k) ) ≤ max i=1,...,n n∑ j=1 |HD,i,j(k)|
≤ max i=1,...,n n∑ j=1 ∣∣∣∣∣ 1m L∑ `=1 〈 ∇W` [ f W (k) D (xi) ] ,∇W` [ f W (k) D (xj) ]〉 Tr ∣∣∣∣∣ ≤ max i=1,...,n n∑ j=1 1 m L∑ `=1 ∥∥∥∇W`[fW(k)D (xi)]∥∥∥F︸ ︷︷ ︸ ≤O( √ mω) ∥∥∥∇W`[fW(k)D (xj)]∥∥∥F︸ ︷︷ ︸ ≤O( √ mω)
≤ O ( nLω ) . (71)
Recall the decomposition (62). Our goal is to obtain the upper-bound on Ti for i = 1, 2, 3, 4. Control on T1. By using the inequality 2η2µL(1−η2µL)y> ( y−uD(k) ) ≤ η2µL ‖y‖22+η2µL(1− η2µL) 2 ‖y − uD(k)‖22, we have
‖y − (1− η2µL)uD(k)‖22 = ∥∥(1− η2µL)(y − uD(k))+ η2µLy∥∥22
= (1− η2µL)2 ‖y − uD(k)‖22 + η 2 2µ 2L2 ‖y‖22 + 2η2µL(1− η2µL)y> ( y − uD(k) ) ≤ (η2µL+ η22µ2L2) ‖y‖ 2 2 + ( 1 + η2µL )( 1− η2µL
)2 ‖y − uD(k)‖22 . (72)
Control on T2. Recall the equality (65). Then, through applications of the Young’s inequality ‖a+ b‖22 ≤ 2 ‖a‖ 2 2 + 2 ‖b‖ 2 2 for a, b ∈ Rn, we have
‖uD(k + 1)− (1− η2µL)uD(k)‖22 = ∥∥∥−mη1 ·HD(k)(uD(k)− y)+ I(k)D ∥∥∥2
2 ≤ 2m2η21λmax ( HD(k) )2 ‖y − uD(k)‖22 + 2 ∥∥∥I(k)D ∥∥∥2 2 . (73)
Similarly with T1 and T2, we can control T3 and T4 as follows:
Control on T3. Recall HD(k) is a Gram matrix by definition. Then, by using the fact λmin ( HD(k) ) ≥ 0 and Cauchy-Schwarz inequality, we have
2mη1 ( y − (1− η2µL)uD(k) )> HD(k) ( uD(k)− y ) = −2mη1(1− η2µL) ( y − uD(k) )> HD(k) ( y − uD(k) ) + ( 2mη1η2µL ) · y>HD(k) ( uD(k)− y
) ≤ ( 2mη1η2µL ) · λmax ( HD(k) ) ‖y − uD(k)‖22 + ( 2mη1η2µL ) · ( λmax ( HD(k) ) ‖y‖2 ‖y − uD(k)‖2
) − 2mη1λmin ( HD(k) ) ‖y − uD(k)‖22
= ( 4mη1η2µL ) · λmax ( HD(k) ) ‖y − uD(k)‖22 + ( 4mη1η2µL ) · λmax ( HD(k) ) ‖y‖22 . (74)
Control on T4. By a simple Cauchy-Schwarz and Young’s inequality, we have − 2 ( y − (1− η2µL)uD(k) )> I (k) D
= −2(1− η2µL) ( y − uD(k) )> I (k) D + 2η2µL · y >ID(k)
≤ 2 ( 1− η2µL ) ‖y − uD(k)‖2 ∥∥∥I(k)D ∥∥∥ 2 + η2µL ‖y‖22 + η2µL ∥∥∥I(k)D ∥∥∥2 2 (75)
Step 4. Upper-bound of the decomposition on training error (62).
Before getting the upper bound of the decomposition (62), we first work on obtaining the bound of (76). Set κ = O ( 1 n2 ) and notice η2µL = O ( 1 n ) by (69), then we have
2 ∥∥∥I(k)D ∥∥∥2 2 + 2 ( 1− η2µL ) ‖y − uD(k)‖2 ∥∥∥I(k)D ∥∥∥ 2 + η2µL ∥∥∥I(k)D ∥∥∥2 2 (76)
= ( 2 + η2µL )∥∥∥I(k)D ∥∥∥2 2 + 2κ ( 1− η2µL ) ‖y − uD(k)‖2 · 1 κ ∥∥∥I(k)D ∥∥∥ 2
≤ ( 2 + η2µL+ 1
κ2 )∥∥∥I(k)D ∥∥∥2 2 + κ2 ( 1− η2µL )2 ‖y − uD(k)‖22 = 1 κ2 · ∥∥∥I(k)D ∥∥∥2 2 + κ2 ( 1− η2µL
)2 ‖y − uD(k)‖22 ≤ { 1 κ2 · O ( L37/6n− 9d−8 6d−3 log(m) m1/3δ2/3 ) + κ2 ( 1− η2µL )2} · ‖y − uD(k)‖22 + 1κ2 · OP ( 1 n4
) ≤ ( η2µL )4( 1− η2µL
)2 · ‖y − uD(k)‖22 + η2µL · ‖y‖22, (77) where in the second inequality, the Eq. (70) is used with (a + b)2 ≤ 2a2 + 2b2 for a, b ∈ R, and in the last inequality, we used ‖y‖22 = O(n) and the sufficiently large m to control the order of the coefficient terms of ‖y − uD(k)‖22. Specifically, we choose m ≥ Ω ( L19n20 log 3(m) δ2 ) .
Now, by combining the inequalities (72), (73), (74), (75), (71) and (77), we obtain the upper-bound on the decomposition (62);
‖uD(k + 1)− y‖22 ≤ (
2η2µL+ η 2 2µ 2L2 + 4mη1η2µL · λmax ( HD(k) )) · ‖y‖22
+ (( 1 + η2µL )( 1− η2µL )2 + 2m2η21λmax ( HD(k) )2 + 4mη1η2µL · λmax ( HD(k) )) · ‖y − uD(k)‖22 + ( 2 ∥∥∥I(k)D ∥∥∥2 2 + 2 ( 1− η2µL ) ‖y − uD(k)‖2 ∥∥∥I(k)D ∥∥∥ 2 + η2µL ∥∥∥I(k)D ∥∥∥2 2
) ≤ { 3η2µL+ η 2 2µ 2L2 +O ( ωmnη1η2µL 2 )} · ‖y‖22
+ {( 1 + η2µL+ η 4 2µ 4L4 )( 1− η2µL )2 +O ( ω2m2n2η21L 2 ) +O ( ωmnη1η2µL 2 )} · ‖y − uD(k)‖22 := A · ‖y‖22 + (1− B) · ‖y − uD(k)‖ 2 2 . (78)
With the order choices of µ, η1 and η2 as in (69), it is easy to see the leading terms of both A and B are same as η2µL = o( 1n ). Then, by recursively applying the inequality (78), we can get the upper-bound on the training error.
‖y − uD(k + 1)‖22 ≤ A · ‖y‖ 2 2 + (1− B) · ‖y − uD(k)‖ 2 2 ≤ A‖y‖22 · ( k∑ j=0 (1− B)j ) + (1− B)k+1 · ‖y − uD(0)‖22
≤ A B · ‖y‖22 + (1− B) k+1 · ‖y − uD(0)‖22
≤ O ( n )
+ (1− η2µL)k+1 · ‖y − uD(0)‖22 . (79)
In the last inequality, we used AB = o(1), B ≥ η2µL and ‖y‖ 2 2 = O(n).
Step 5. The order of the radius of perturbation region. It remains us to prove the radius of perturbation region τ has the order OP ( L √ ω√ m n d 2d−1 ) . First, recall that the `2-regularized GD
update rule is as:
W (k) D,` = ( 1− η2µ ) W (k−1) D,` − η1∇W` [ LS ( W (k−1) D )] + η2µW (0) D,`, ∀1 ≤ ` ≤ L and ∀k ≥ 1.
(80)
Similarly with the proof in the Theorem 3.5, we employ the induction process for the proof. The induction hypothesis is∥∥∥W(s)D,` −W(0)D,`∥∥∥
2 ≤ O
( η1n √ mω√
δη2µ
) , ∀s ∈ [k + 1]. (81)
It is easy to see it holds for s = 0, and suppose it holds for s = 0, 1, . . . , k, we consider k+1. Using the update rule (80), we have∥∥∥W(k+1)D,` −W(k)D,`∥∥∥
2 ≤ η2µ ∥∥∥W(k)D,` −W(0)D,`∥∥∥ 2 + η1 ∥∥∥∇W`[LS(W(k)D )]∥∥∥ 2
= η2µ ∥∥∥W(k)D,` −W(0)D,`∥∥∥
2 + η1 ∥∥∥∥∥ n∑ i=1 ( yi − uD,i(k) ) ∇W` [ fWD(k)(xi) ]∥∥∥∥∥ 2
≤ O ( η1n √ mω√ δ ) +O ( η1 √ nmω ) · ‖y − uD(k)‖2
≤ O ( η1n √ mω√ δ ) +O ( η1 √ nmω ) · { O (√ n ) + (1− η2µL) k 2O (√ n δ )} ≤ O ( η1n √ mω√
δη2µ
) .
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 s = 0, 1, . . . , k, we employ ‖y − uD(k)‖2 ≤ O (√ n )
+ (1− η2µL) k 2 ‖y − uD(0)‖2 with the Lemma 4.9. In the last inequality, we use η2µ < 1.
By triangle inequality, the induction holds for s = k + 1. Plugging the proper choices of η1, η2 and µ as suggested in (69) to O ( η1n √ mω√
δη2µ
) yields ‖W(k)D,` −W (0) D,`‖2 ≤ OP ( L √ ω√ m n d 2d−1 ) .
H PROOF OF THEOREM 3.11-KERNEL RIDGE REGRESSOR APPROXIMATION
We present a following proof sketch on the approximation of 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 ui,D(k) (where D is to denote the prediction is obtained from regularized GD rule) and kernel regressor B := H∞L ( Cµ · I + H∞L )−1 y in terms of NTK matrix H∞L , which is as
follows: uD(k)−B = (( 1− η2µL ) · I −mη1H∞L )k( uD(0)−B ) + eD(k).
Above equality describes how the regularized estimator evolves to fit the kernel regressor as iteration of algorithm goes by.
2. We can bound the `2-norm of residual term eD(k) as O(1/n), and show that the `2 norm of the first term on the RHS of equation (4.3) decays at the rateO (√ n ( 1− η2µL )k) . Here
the √ n comes from the bound ‖B‖2 ≤ O( √ n), since we know ‖u(0)‖2 hasO( √ nω) with small ω ≤ 1. This yields the claim.
Recall the equality (65). Then, we have
uD(k + 1)− (1− η2µL)uD(k) = −mη1 ·HD(k) ( uD(k)− y ) + I (k) 2,D + I (k) 3,D + I (k) 5,D
= −mη1 ·H∞L ( uD(k)− y ) −mη1 · ( HD(k)−H∞L )( uD(k)− y ) + I (k) 2,D + I (k) 3,D + I (k) 5,D
= −mη1 ·H∞L ( uD(k)− y ) + ξD(k). (82)
With τ = O ( L √ ω√
mδ n
d 2d−1 ) , similarly with Lemma 4.10 and a direct employment of the result from
Lemma 4.11, we can control the distance from HD(k) to H∞L under operator norm as follows:
‖HD(k)−H∞L ‖2 ≤ ‖HD(k)−H(0)‖2 + ‖H(0)−H ∞ L ‖2
≤ O ( ω7/6L10/3n 7d−3 6d−3 6 √ log3(m)
mδ2
) +O ( ωL5/2n 4 √ log(nL/δ)
m
)
≤ O ( L19/12n− 21d−8 12d−6 6 √ log3(m)
mδ2
) +O ( Ln− 18d−6 12d−6 4 √ log(nL/δ)
m
)
≤ O ( L19/12n− 21d−8 12d−6 6 √ log3(m)
mδ2
) , (83)
where in the third inequality, ω = O (
1 L3/2
n− 5d−2 2d−1 ) is plugged-in. The last inequality holds with
d ≥ 2 with large enough n and the condition on width m ≥ Ω ( L19n20 log
3(m) δ2 ) . Then, the `2 norm
of ξD(k) can be bounded as:
‖ξD(k)‖2 ≤ mη1 · ‖H ∞ L −HD(k)‖2 ‖uD(k)− y‖2 + ∥∥∥I(k)D ∥∥∥ 2
≤ O ( L19/12n− 12d−5 6d−3 √ log(m)
m1/6δ1/3 ) · ‖uD(k)− y‖2︸ ︷︷ ︸ ≤O( √ n/δ) +OP ( 1 n2 )
≤ O ( L19/12n− 18d−7 12d−6 √ log(m)
m1/6δ5/6
) +OP ( 1
n2
) = OP ( 1
n2
) , (84)
where in the second inequality, we used (83) with η1 = O ( 1 mn − 3d−22d−1 ) to control the first term and
employed Eq. (70) to control the second term. In the last equality, we usedm ≥ Ω ( L19n20 log
3(m) δ2
) .
Now, by setting B := ( η2µL η1m I + H∞L )−1 H∞L y, we can easily convert the equality (82) as follows:
for k ≥ 1, uD(k)−B = (( 1− η2µL ) · I −mη1H∞L )( uD(k − 1)−B ) + ξD(k − 1). (85)
The recursive applications of the equality (85) yields uD(k)−B = (( 1− η2µL ) · I −mη1H∞L )k( uD(0)−B ) +
k∑ j=0 (( 1− η2µL ) · I −mη1H∞L )j ξD(k − j − 1)
= (( 1− η2µL ) · I −mη1H∞L )k( uD(0)−B ) + eD(k). (86)
Now, we bound the `2 norm of eD(k) in (86):
‖eD(k)‖2 = ∥∥∥∥∥∥ k∑ j=0 (( 1− η2µL ) · I −mη1H∞L )j ξD(k − j − 1) ∥∥∥∥∥∥ 2
≤ k∑ j=0 ∥∥(1− η2µL) · I −mη1H∞L ∥∥j2 ‖ξD(k − j − 1)‖2 ≤
k∑ j=0 ( 1− η2µL )j ‖ξD(k − j − 1)‖2 = O( 1n ) , (87)
in the last inequality, we used η2µL = O ( 1 n ) and Eq. (84). Now, we control the `2-norm of the first term in (86) as:∥∥∥∥∥ (( 1− η2µL ) · I −mη1H∞L )k( uD(0)−B )∥∥∥∥∥ 2 ≤ ( 1− η2µL
)k ‖uD(0)−B‖2 ≤ O (√ n ( 1− η2µL )k) , (88)
where in the second inequality, we used ‖uD(0)‖2 ≤ O( √ nω/δ) and the fact that
‖B‖2 ≤ ∥∥∥∥∥ ( η2µL η1m I + H∞L )−1 H∞L ∥∥∥∥∥ 2 · ‖y‖2 ≤ O( √ n).
By combining (87) and (88) and using a fact (1− η2µL)k ≤ exp(−η2µLk), we conclude that after k ≥ Ω ( (η2µL) −1 log(n3/2) ) , the error ‖uD(k)−B‖2 decays at the rate O ( 1 n ) .
I PROOF OF THEOREM 3.12
We begin the proof by decomposing the error f̂ W
(k) D (x)− f∗(x) for any fixed x ∈ Unif(Sd−1) into two terms as follows:
f̂ W
(k) D
(x)− f∗(x) = ( f̂ W
(k) D (x)− g∗µ(x) )︸ ︷︷ ︸
∆D,1
+ ( g∗µ(x)− f∗(x) )︸ ︷︷ ︸ ∆D,2 . (89)
Here, we devise a solution of kernel ridge regression g∗µ(x) in the decomposition (89):
g∗µ(x) := Ker(x,X) ( Cµ · I + H∞L )−1 y,
for some constant C > 0. Specifically, in the proof to follow, we choose η1 and η2 such that C = η2Lη1m for the theoretical convenience. Our goal is to show that all the terms ‖∆D,1‖ 2 2, and
‖∆D,2‖22 have the order either equal to or smaller than O ( n− d 2d−1 ) with the proper choices on m, µ, η1 and η2. Since the high-level proof idea is similar with that of Theorem 3.8, we omit the step-by-step proof sketch of Theorem 3.12. 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.
Step 1. Control on ∆D,2. First, note that there is a recent finding that the reproducing kernel Hilbert spaces induced from NTKs with any number of layers (i.e., L ≥ 1) have the same set of functions, if kernels are defined on 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 al. [2021] for proving a following :
‖∆D,2‖22 := ∥∥g∗µ − f∗∥∥22 = OP(n− d2d−1), ∥∥g∗µ∥∥2H = OP(1). (90)
Step 2. Control on ∆D,1. For n data points ( x1, . . . ,xn ) and for the kth updated parameter W(k)D ,
denote: ∇W` [ f W
(k) D
(X) ] = [ vec ( ∇W` [ f W
(k) D
(x1) ]) , · · · , vec ( ∇W` [ f W
(k) D
(xn) ])] .
Note that when ` = 1, ∇W` [ f W
(k) D
(X) ] ∈ Rmd×n and when ` = 2, . . . , L, ∇W` [ f W
(k) D
(X) ] ∈
Rm2×n.
With this notation, we can write the vectorized version of the update rule (80) as:
vec ( W
(k) D,`
) = vec ( W
(0) D,` ) − η1 k−1∑ j=0 ( 1− η2µ)j∇W` [ fWD(k−j−1)(X) ]( uD(k − j − 1)− y ) ,
∀1 ≤ ` ≤ L and ∀k ≥ 1. Using the equality, we can get the decomposition :
vec ( W
(k) D,`
) = vec ( W
(0) D,` )︸ ︷︷ ︸ :=E1 −η1∇W` [ fWD(0)(X) ] k−1∑ j=0 ( 1− η2µ)j ( uD(k − j − 1)− y ) ︸ ︷︷ ︸
:=E2 −η1 k−1∑ j=0 ( 1− η2µ)j [ ∇W` [ fWD(k−j−1)(X) ] −∇W` [ fWD(0)(X) ]]( uD(k − j − 1)− y ) .︸ ︷︷ ︸
:=E3
(91) Let zD,k(x) := vec ( ∇W` [ f W
(k) D
(x) ])
, and note that f W
(k) D
(x) = 〈zD,k(x), vec ( W (k) D,` ) 〉. Then, by
the definition of ∆D,1 and the decomposition (91), we have
∆D,1 = 1
L L∑ `=1 〈zD,k(x),E1 + E2 + E3〉 −Ker(x,X) ( η2µL η1m I + H∞L )−1 y
= 1
L L∑ `=1 〈zD,k(x),E1〉+ 1 L L∑ `=1 〈zD,k(x),E3〉
+ 1
L L∑ `=1 〈zD,k(x),E2〉 −Ker(x,X) ( η2µL η1m I + H∞L )−1 y︸ ︷︷ ︸
:=C
(92)
First, we focus on controlling the `2 bound on the first two terms in (92). Observe that the first term can be bounded as: ∣∣∣∣∣ 1L L∑ `=1 〈zD,k(x),E1〉 ∣∣∣∣∣ 2 ≤ 1 L L∑ `=1 |〈zD,k(x),E1〉|2 . (93)
Recall that ‖zD,k(x)‖2 ≤ O (√ mω )
by Lemma 4.4. Then, the random variable zD,k(x) >vec ( W (0) D,` ) | zD,k(x) is simply a N ( 0,O(ω) ) for 1 ≤ ` ≤ L. A straightforward application of Chernoff bound for normal random variable and taking union bound over the layer 1 ≤ ` ≤ L yield that: with probability at least 1− δ,
1
L L∑ `=1 ∣∣∣zD,k(x)>vec(W(0)D,`)∣∣∣2 ≤ O ( ω log ( L δ )) . (94)
The `2 norm of the second term in (92) can be similarly bounded as (93) in addition with the CauchySchwarz inequality:∣∣∣∣∣ 1L L∑ `=1 〈zD,k(x),E3〉 ∣∣∣∣∣ 2 ≤ 1 L L∑ `=1 |〈zD,k(x),E3〉|2 ≤ 1 L L∑ `=1 ‖zD,k(x)‖22 ‖E3‖ 2 2 . (95)
The ‖E3‖2 is bounded as :
‖E3‖2 = ∥∥∥∥∥∥η1 k−1∑ j=0 ( 1− η2µ)j [ ∇W` [ fWD(k−j−1)(X) ] −∇W` [ fWD(0)(X) ]]( uD(k − j − 1)− y )∥∥∥∥∥∥ 2
≤ η1 k−1∑ j=0 ( 1− η2µ)j · ∥∥∇W`[fWD(k−j−1)(X)]−∇W`[fWD(0)(X)]∥∥2 ‖uD(k − j − 1)− y‖2 ≤ η1
k−1∑ j=0 ( 1− η2µ)j · ∥∥∇W`[fWD(k−j−1)(X)]−∇W`[fWD(0)(X)]∥∥F ‖uD(k − j − 1)− y‖2 = η1
k−1∑ j=0 ( 1− η2µ)j · √√√√ n∑ i=1
∥∥∇W`[fWD(k−j−1)(xi)]−∇W`[fWD(0)(xi)]∥∥2F ‖uD(k − j − 1)− y‖2 ≤ η1
k−1∑ j=0 ( 1− η2µ)j · √√√√2 n∑ i=1
∥∥∇W`[fWD(k−j−1)(xi)]−∇W`[fWD(0)(xi)]∥∥22 ‖uD(k − j − 1)− y‖2 ≤ η1 η2µ · O ( τ1/3L2 √ ωmn log(m) ) · O (√ n ) ≤ O ( L10/3ω1/6 m2/3δ1/3 n 4d 6d−3 √ log(m) ) . (96)
In the first, second and third inequalities, we used a simple fact that for the matrix A ∈ Rd1×d2 with rank r, then ‖A‖2 ≤ ‖A‖F ≤ √ r‖A‖2. Recall that the rank of the matrix∇W` [ fWD(k−j−1)(x) ] −
∇W` [ fWD(0)(x) ] is at most 2. In the second to the last inequality, we use the result of Lemma 4.6
and the ‖uD(i) − y‖2 ≤ O( √ n) for any i ≥ 1. In the last inequality, we plug the correct orders as set in (69) to τ , η1, η2 and µ. Back to the inequality (95), using the ‖zD,k(x)‖2 ≤ O (√ mω ) and (96), we can get
1
L L∑ `=1 ‖zD,k(x)‖22 ‖E3‖ 2 2 ≤ OP ( L20/3ω4/3 m1/3 n 8d 6d−3 log(m) ) . (97)
Before controlling the `2 norm of C in (92), recall that we set B := ( η2µL η1m I + H∞L )−1 H∞L y and the dynamics of uD(k)−B can be expressed in terms of H∞L as follows: For any k ≥ 1,
uD(k)−B = (( 1− η2µL ) · I −mη1H∞L )k( uD(0)−B ) + eD(k), (98)
with ‖eD(k)‖2 ≤ O ( 1 n ) . Using (98), we can further decompose the term E2 in (91) as:
E2 := −η1∇W` [ fWD(0)(X) ] k−1∑ j=0 ( 1− η2µ)j ( uD(k − j − 1)− y )
= η1∇W` [ fWD(0)(X) ] k−1∑ j=0 ( 1− η2µ)j (( 1− η2µL ) · I −mη1H∞L )k−j−1 B
− η1∇W` [ fWD(0)(X) ] k−1∑ j=0 ( 1− η2µ)j (( 1− η2µL ) · I −mη1H∞L )k−j−1 uD(0) − η1∇W` [ fWD(0)(X)
] k−1∑ j=0 ( 1− η2µ)jeD(k − j − 1)
− η1∇W` [ fWD(0)(X) ] k−1∑ j=0 ( 1− η2µ)j ( B− y ) = E2,1 + E2,2 + E2,3 + E2,4. (99)
Then, we can re-write the error term C in (92) as:
C = 1 L L∑ `=1 〈zD,k(x),E2,1〉+ 1 L L∑ `=1 〈zD,k(x),E2,2〉+ 1 L L∑ `=1 〈zD,k(x),E2,3〉
+
{ 1
L L∑ `=1 〈zD,k(x),E2,4〉 −Ker(x,X) ( η2µL η1m I + H∞L )−1 y } ︸ ︷︷ ︸
:=D
. (100)
Our goal is to control the `2 norm of each summand in the equality (100). For the first three terms in (100), a simple Cauchy-Schwarz inequality can be applied: for i = 1, 2, 3:∣∣∣∣∣ 1L L∑ `=1 〈zD,k(x),E2,i〉 ∣∣∣∣∣ 2 ≤ 1 L L∑ `=1 |〈zD,k(x),E2,i〉|2 ≤ 1 L L∑ `=1 ‖zD,k(x)‖22 · ‖E2,i‖ 2 2 . We work on obtaining the bound of ∑L `=1 ‖E2,1‖ 2 2. Let Tk be defined as
Tk := k−1∑ j=0 ( 1− η2µ)j (( 1− η2µL ) · I −mη1H∞L )k−j−1 .
Then, we have
L∑ `=1 ‖E2,1‖22 = η 2 1 L∑ `=1 ( B>T >k ∇W` [ fWD(0)(X) ]>∇W`[fWD(0)(X)]TkB) = mη21B >T >k H(0)TkB
= mη21B >T >k ( H(0)−H∞L ) TkB +mη21B>T >k H∞L TkB
≤ mη21 ‖H(0)−H∞L ‖2 ·B >T 2k B +mη21B>T >k H∞L TkB. (101)
To obtain the upper-bound on (101), we need to control the terms T >k H∞L Tk and B>T 2k B. Let us denote H∞L = ∑n i=1 λiviv > i be the eigen-decomposition of H ∞ L . Using 1− η2µL ≤ 1− η2µ, note that
Tk = k−1∑ j=0 ( 1− η2µ )j( 1− η2µL )k−j−1(I − mη1 1− η2µL H∞L )k−j−1
( 1− η2µ )k−1 k−1∑ i=0 ( I − mη1 1− η2µ H∞L )i
= ( 1− η2µ )k−1 n∑ j=0 ( 1− ( 1− mη11−η2µλj )k mη1 1−η2µλj ) vjv > j ( 1− η2µ )k mη1λ0 · I. (102)
A similar logic can be applied to bound T >k H∞L Tk:
T >k H∞L Tk ( 1− η2µ )k−1 n∑ j=0 ( 1− ( 1− mη11−η2µλj )k mη1 1−η2µλj )2 λjvjv > j
( 1− η2µ )2k m2η21 · ( H∞L )−1 . (103)
Recall the definition of the notation B := H∞L ( η2µL η1m I + H∞L )−1 y. Then, we can bound the term
B>T >k H∞L TkB:
B>T >k H∞L TkB ≤ ( 1− η2µ )2k m2η21 ·B> ( H∞L )−1 B
=
( 1− η2µ )2k m2η21 · y> ( η2µL η1m I + H∞L )−1 H∞L ( η2µL η1m I + H∞L )−1 y
= O (( 1− η2µ )2k
m2η21
) , (104)
where in the last equality, we used ∥∥g∗µ∥∥2H = OP(1) in (90). Now we turn our attention to bound the term B>T 2k B,
B>T 2k B ≤ ( 1− η2µ )2k m2η21λ 2 0 y> ( η2µL η1m I + H∞L )−1( H∞L )2( η2µL η1m I + H∞L )−1 y
= O (( 1− η2µ )2k n
m2η21λ 2 0
) , (105)
where we used ‖y‖22 = O(n) in the last inequality. Combining the bounds (104), (105) and the result from Lemma 4.11, we can further bound (101) and have:
L∑ `=1 ‖E2,1‖22 ≤ O ( ω ( 1− η2µ )2k mλ20 n2L5/2 4 √ log(nL/δ) m + ( 1− η2µ )2k m ) ≤ O (( 1− η2µ )2k m ) ,
(106) where in the second inequality, we used m ≥ Ω ( L19n20 log
3(m) δ2 ) . Similarly, we can bound∑L
`=1 ‖E2,2‖ 2 2:
L∑ `=1 ‖E2,2‖22 = η 2 1 L∑ `=1 ( uD(0) >T >k ∇W` [ fWD(0)(X) ]>∇W`[fWD(0)(X)]TkuD(0)) = mη21uD(0) >T >k H(0)TkuD(0)
= mη21uD(0) >T >k ( H(0)−H∞L ) TkuD(0) +mη21uD(0)>T >k H∞L TkuD(0)
≤ mη21 ‖H(0)−H∞L ‖2 · uD(0) >T 2k uD(0) +mη21uD(0)>T >k H∞L TkuD(0)
≤ mη21
( 1− η2µ )2k m2η21λ 2 0 O ( ωnL5/2 4 √ log(nL/δ) m ) ‖uD(0)‖22
+mη21
( 1− η2µ )2k m2η21 uD(0) >(H∞L )−1uD(0)
≤ O (( 1− η2µ )2k n2ω2L5/2
mλ20δ 2
4 √
log(nL/δ) m +
nω ( 1− η2µ )2k mλ0δ2 ) = OP ( nω ( 1− η2µ )2k mλ0 ) . (107)
Here, in the second inequality, we used the inequalities (102) and (103) and Lemma 4.11. In the third inequality, we used the Lemma 4.8, ‖u(0)‖2 = O (√nω δ ) with probability at least 1− δ. In the
last equality, we used m ≥ Ω ( L19n20 log
3(m) δ2
) .
Next, we bound ∑L `=1 ‖E2,3‖ 2 2 as: L∑ `=1 ‖E2,3‖22 = mη 2 1 · ( k−1∑ j=0 ( 1− η2µ )j( ek−j−1 ))> HD(0) ( k−1∑ j=0 ( 1− η2µ )j( ek−j−1 ))
≤ mη 2 1
η22µ 2 · λmax
( HD(k) ) · ‖ek−j−1‖22 ≤
mη21 η22µ
2 · O ( ωnL ) · O ( 1
n2
) = O ( L3
m ω · n− 4d−3 2d−1
) .
(108)
Now, we focus on obtaining the `2 norm bound on D in (100). Recall the definition of the notation
B := H∞L ( η2µL η1m I + H∞L )−1 y. A simple calculation yields that
B− y = H∞L ( η2µL
η1m I + H∞L
)−1 y − y = −η2µL
mη1
( η2µL
η1m I + H∞L
)−1 y.
Then, we can re-write the expression of the D as : D := ( η2µL
mη1
) · η1 1
L L∑ `=1 〈 zD,k(x),∇W` [ fWD(0)(X) ]〉 k−1∑ j=0 ( 1− η2µ)j ( η2µL η1m I + H∞L )−1 y
−Ker(x,X) ( η2µL
η1m I + H∞L
)−1 y
=
( 1
m L∑ `=1 〈 zD,k(x),∇W` [ fWD(0)(X) ]〉 −Ker(x,X) )( η2µL η1m I + H∞L )−1 y
− ( 1− η2µ )k 1 m L∑ `=1 〈 zD,k(x),∇W` [ fWD(0)(X) ]〉(η2µL η1m I + H∞L )−1 y
=
( 1
m L∑ `=1 〈 z0,k(x),∇W` [ fWD(0)(X) ]〉 −Ker(x,X) )( η2µL η1m I + H∞L )−1 y
− ( 1− η2µ )k 1 m L∑ `=1 〈 z0,k(x),∇W` [ fWD(0)(X) ]〉(η2µL η1m I + H∞L )−1 y + ( 1− ( 1− η2µ )k)( 1 m L∑ `=1 〈 zD,k(x)− zD,0(x),∇W` [ fWD(0)(X) ]〉)(η2µL η1m I + H∞L )−1 y,
(109) where in the second equality, ∑k−1 j=0 (1− η2µ)j = 1−(1−η2µ)k η2µ
is used. The `2 norm of first term in the (109) can be bounded as:∥∥∥∥∥ ( 1 m L∑ `=1 〈 zD,k(x),∇W` [ fWD(0)(X) ]〉 −Ker(x,X) )( η2µL η1m I + H∞L )−1 y ∥∥∥∥∥ 2
≤ ∥∥∥∥∥ ( 1 m L∑ `=1 〈 zD,k(x),∇W` [ fWD(0)(X) ]〉 −Ker(x,X) )∥∥∥∥∥ 2 · ∥∥∥∥∥ ( η2µL η1m I + H∞L )−1 y ∥∥∥∥∥ 2
= √√√√ n∑ i=1 ( 1 m L∑ `=1 〈 z0(x),∇W` [ fWD(0)(xi) ]〉 −Ker(x,xi) )2 · ∥∥∥∥∥ ( η2µL η1m I + H∞L )−1 y ∥∥∥∥∥ 2
≤ O ( ω √ nL5/2 4 √
log(nL/δ) m
) · O ( η1m
η2µL
√ n ) = O ( ωη1mn
η2µL L5/2
4 √
log(nL/δ) m
) = O ( ωL5/2n d 2d−1 4 √
log(nL/δ) m
) , (110)
where, in the second inequality, we used Lemma 4.11, and also we used∥∥∥∥∥ ( η2µL η1m I + H∞L )−1 y ∥∥∥∥∥ 2 ≤ √ y> ( η2µL η1m I + H∞L )−2 y ≤ √ η21m 2 η22µ 2L2 · ‖y‖22 = O ( η1m η2µL √ n ) .
(111)
The `2 norm of the second term in (109) can be easily bounded as:∥∥∥∥∥(1− η2µ)k 1m L∑ `=1 〈 z0(x),∇W` [ fWD(0)(X) ]〉(η2µL η1m I + H∞L )−1 y ∥∥∥∥∥ 2
≤ ∥∥∥∥∥(1− η2µ)k ( 1 m L∑ `=1 〈 z0(x),∇W` [ fWD(0)(X) ]〉 −Ker(x,X) )( η2µL η1m I + H∞L )−1 y ∥∥∥∥∥ 2
+ ∥∥∥∥∥(1− η2µ)kKer(x,X) ( η2µL η1m I + H∞L )−1 y ∥∥∥∥∥ 2
≤ ( 1− η2µ )k ∥∥∥∥∥ 1m L∑ `=1 〈 z0(x),∇W` [ fWD(0)(X) ]〉 −Ker(x,X) ∥∥∥∥∥ 2 · ∥∥∥∥∥ ( η2µL η1m I + H∞L )−1 y ∥∥∥∥∥ 2
+ ( 1− η2µ )k ∥∥∥∥∥Ker(x,X) ( η2µL η1m I + H∞L )−1 y ∥∥∥∥∥ 2
≤ ( 1− η2µ )k · O(ω√nL3/2 4√ log(nL/δ)m ) · O( η1mη2µL√n ) +O (( 1− η2µ )k)
≤ ( 1− η2µ )k · O(ωL3/2n d2d−1 4√ log(nL/δ)m )+O((1− η2µ)k). (112) Lastly, the `2 norm of the third term in (109) is bounded as:∥∥∥∥∥(1− (1− η2µ)k) ( 1 m L∑ `=1 〈 zD,k(x)− zD,0(x),∇W` [ fWD(0)(X) ]〉)(η2µL η1m I + H∞L )−1 y ∥∥∥∥∥ 2
≤ ( 1− ( 1− η2µ )k) · ∥∥∥∥∥ 1m L∑ `=1 〈 zD,k(x)− zD,0(x),∇W` [ fWD(0)(X) ]〉∥∥∥∥∥ 2 · ∥∥∥∥∥ ( η2µL η1m I + H∞L )−1 y ∥∥∥∥∥ 2
≤ ( 1− ( 1− η2µ )k) · ( 1 m L∑ `=1 ‖zD,k(x)− zD,0(x)‖F ∥∥∇W`[fWD(0)(X)]∥∥F ) · ∥∥∥∥∥ ( η2µL η1m I + H∞L )−1 y ∥∥∥∥∥ 2
≤ ( 1− ( 1− η2µ )k) · ( L m O ( τ1/3L2 √ ωm log(m) ) · O (√ ωmn )) · O ( η1m
η2µL
√ n ) ≤ ( 1− ( 1− η2µ )k) · O(ω7/6L10/3n 4d6d−3 √log(m) m1/6δ1/3 ) ≤ O ( ω7/6L10/3n 4d 6d−3 √ log(m) m1/6δ1/3 ) ,
(113) where in the fourth inequality, τ = OP ( L √ ω√ m n d 2d−1 ) is plugged in. Combining the inequali-
ties (110), (112) and (113), we get the bound on ‖D‖2 in (109):
‖D‖22 ≤ O ( ω2L5n 2d 2d−1 √ log(nL/δ)
m
) + ( 1− η2µ )2kO(ω2L3n 2d2d−1√ log(nL/δ)m )+O((1− η2µ)2k) +O ( ω7/3L20/3n 8d 6d−3 log(m)
m1/3δ2/3 ) ≤ O ( ω7/3L20/3n 8d 6d−3 log(m)
m1/3δ2/3
) +O (( 1− η2µ )2k) . (114)
Step 3. Combining all pieces. Recall ‖zD,k(x)‖2 ≤ O (√ mω ) . With this fact, combining the bounds (94), (97), (106), (107), (108) and (114), we can bound the ‖∆D,1‖22 via the decomposition (92) as follows:
‖∆D,1‖22 ≤ 1
L L∑ `=1 ∣∣∣zD,k(x)>vec(W(0)D,`)∣∣∣2 + 1L L∑ `=1 ‖zD,k(x)‖22 ‖E3‖ 2 2
+ 1
L L∑ `=1 ‖zD,k(x)‖22 ‖E2,1‖ 2 2 + 1 L L∑ `=1 ‖zD,k(x)‖22 ‖E2,2‖ 2 2 + 1 L L∑ `=1 ‖zD,k(x)‖22 ‖E2.3‖ 2 2
+ ∥∥∥∥∥ 1L L∑ `=1 〈zD,k(x),E2,4〉 −Ker(x,X) ( η2µL η1m I + H∞L )−1 y ∥∥∥∥∥ 2
2
≤ O ( ω log ( L
δ
)) +OP ( L20/3ω4/3
m1/3 n
8d 6d−3 log(m)
)
+OP
( ω ( 1− η2µ )2k L ) +OP ( nω2 ( 1− η2µ )2k Lλ0 ) +OP ( L2 m ω · n− 4d−3 2d−1 )
+O ( ω7/3L20/3n 8d 6d−3 log(m)
m1/3δ2/3
) +OP (( 1− η2µ )2k)
≤ OP ( n− d 2d−1 ) .

Review summaries:
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.

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. In 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.

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.