Implicit Bias of MSE Gradient Optimization in Underparameterized Neural Networks
Authors: Benjamin Bowman
Guido Montufar
Venue: ICLR 2022 Poster (2022)
Keywords: underparameterized regime
spectral bias
neural tangent kernel
implicit bias
implicit regularization
gradient flow

Abstract: We study the dynamics of a neural network in function space when optimizing the mean squared error via gradient flow.  We show that in the underparameterized regime the network learns eigenfunctions of an integral operator $T_K$ determined by the Neural Tangent Kernel at rates corresponding to their eigenvalues.  For example, for uniformly distributed data on the sphere $S^{d - 1}$ and rotation invariant weight distributions, the eigenfunctions of $T_K$ are the spherical harmonics.  Our results can be understood as describing a spectral bias in the underparameterized regime. The proofs use the concept of ``Damped Deviations'' where deviations of the NTK matter less for eigendirections with large eigenvalues.  Aside from the underparameterized regime, the damped deviations point-of-view allows us to extend certain results in the literature in the overparameterized setting. 

Published as a conference paper at ICLR 2022
IMPLICIT BIAS OF MSE GRADIENT OPTIMIZATION IN UNDERPARAMETERIZER NEURAL NETWORKS
Benjamin Bowman
Guido Montúfar
UCLA Departments of Mathematics benbowman31 4 4@math, ucl a edu
UCLA Departments of Mathematics and Statistics and MPI MIS montu fa @math, vcl a edu
ABSTRACT
We study the dynamics of neural network in function space when optimizing the mean squared error via gradient flow. We show that the underparameterrzeed regime the network learns eigenfunctions of integral operator TK> determined by the Neural Tangent Kernel (NTK) at rates corresponding to their eigenvalues. For example, for uniformly distributed data on the sphere S and rotation invari- ant weight distributions, the eigenfunctions Our results can be understood describing spectral bias in the underparameter- ized regime. The proofs use the concept of "Damped Deviations", where devia- tions of the NTK matter less for eigendirections with large eigenvalues due the occurence of damping factor. Aside from the underparameterized regime, the damped deviations point-of-view can be used track the dynamics of the empir- ical risk in the overparameterized setting, allowing us to extend certain results in the literature. We conclude that damped deviations offers a simple and unifying perspective of the dynamics when optimizing the squared error.
Tk are the spherical harmonics.
INTRODUCTION
A surprising but well established empirical fact is that neural networks optimized by gradient descent can find solutions to the empirical risk minimization (ERM) problem that generalize. This is surpris- ing from an optimization noint-of-view because the ERM problem induced by neural networks is nonconvex (Sontag & Sussmann) 1989 1991) and can even be NP-Complete in certain cases (Blum) & Rivest 1993). Perhaps even more surprising is that the discovered solution can generalize even when the network is able to fit arbitrary labels (Zhang et al.) 2017), rendering traditional complexity measures such Rademacher complexity inadequate. How does deep learning succeed in the face of pathological behavior by the standards of classical optimization and statistical learning theory?
Towards addressing generalization, modern line of thought that has emerged is that gradient de- scent performs impliciteggulariin regularization, limiting the solutions one encounters in practice to a favorable subset of the model's full capacity (see, e.g.. Neyshabaaa et al.) 2015 2017 Gunasekar et al. 2017 Wu et al.] 2017). An empirical observation is that neural networks optimized by gradient descent tend to fit the low frequencies of the target function first, and only pick up the higher frequencies later in training (Rahaman et al. [2019] Ronen et al., 2019 Basri et al. 2020 Xu et al. (2019). A closely related theme gradient descent's bias towards smoothness for regression problems (Williams al. 2019 Jin & Montúfar 2021). For classification problems, in suitable settings gradient descent prov- ably selects max- maa-in solutions (Soudry et al. 2018, Ji Telgarsky 2019). Gradient descent is not impartial, thus understanding its bias is an important program in modern deep learning.
Generalization concerns aside, the fact that gradient descent can succeed in a nonconvex optimiza- tion landscape warrants attention on its own. A brilliant insight made by Jacot et al.) (2018) is that in function space the neural network follows a kernel gradient descent with respect to the "Neural Tangent Kernel" (NTK). This kernel captures how the parameterization biases the trajectory in func- tion space, an abstraction that allows one to largely ignore parameter space and its complications. This is a profitable point-of-view but there is a caveat. The NTK still depends the evolution of the network parameters throughout time, and thus is in general time- denendennddent and complicated to analyze. However, under appropriate scaling of the parameters in the infinite-widd limit remains

---

Published as a conference paper at ICLR 2022
2018 Once the NTK matrix has small enough deviations to remain strictly positive definite throughout training, the optimization dynamics start to become comparable to that of linear model (Lee et al. 2019). For wide networks (quadratic or higher polynomial dependence on the number of training data samples n and other parameters) this property holds and this has been used by variety of works to prove global convergence guarantees for the optimization (Du eet al. 2019b Oymak & Soltanolkotabi 2020; Du et al. [2019a] [Allen-Zhu et al. 20119 by Zou et al.,
constant (Jacot et al.
2020
Zou & Gu 2019 SSng & Yang. 2020; Dukler et al. 2020 and characterize the solution
throughout time (Arora et al. 2019; Basri et al.) 2020). The NIK has been so heavily exploited in this setting that has become synonymous with polynomially wide networks where the NTK is strictly positive definite throughout training. This begs the question, to what extent is the NTK
informative outside this regime?
While the NTK has hitherto been associated with the heavily overparameterizze regime, we demon- strate that reñned analysis is possible in the underparameterized setting. Our theorems primarily concern one-hidden layer network, however unlike many NTK results appearing in the literature our network has biases and both layers are trained. In fact, the machinery we build is strong enough to extend some existing results in the overparameterized regime appearing in the literature to the case of training both layers.
1.1 RELATED WORK
There has been deluge of works on the Neural Tangent Kernel since it was introduced by Pacot let al.] (2018). and thus we do our best to provide a partial list. Global convergence guarantees for the optimization, and lesser extent generalization, for networks polynomially wide in the number of training samples n and other parameters has been addressed in several works (Du et al.,
(019b//yymak & Soltanolkotabi] 2020 Du et al. 2019a Allen-Zhu et al. 2019a by Zoo et al., 20200] Zou & Gu 2019; Song & Yang 2020 Arora et al. 2019). To our knowledge, for the regression
problem with arbitrary labels, quadratic overparameterization m Z n² is state-of-the art (Oymak
& Soltanolkotabi] 2020; Song & Yang 2020. Nguyen & Mondelli 2020). E et al. (2020) gave
fairly comprehensive study of optimization and generalization of shallow networks trained under the standard parameterization. Under the standard parameterization, changes in the outer layer weights are more significant, whereas under the NTK parameterization both layers have roughly equal effect. Since we study the NTK parameterization in this work, we view the analysis as complementary.
Our work is perhaps most closely connected with Arora et al. (2019). In Theorem 4.1 in that work they showed that for shallow network in the polynomially overparameterized regime m λ n², the training error along eigendirections of the NTK matrix decay linearly at rates that correspond to their eigenvalues. Our main Theorem 3.5 can be viewed as an analogous statement for the actual risk (not the empirical risk) in the underparameterized regime: eigenfunctions of the NTK integral operator Tx are approximately learned linearly at rates that correspond their eigenvalues. In contrast with Arora et al. (2019). we have that the requirements on width m and number of samples required to learn eigenfunctions with large eigenvalues are smaller compared to those with small eigenvalues. Surprisingly the machinery we build is also strong enough to prove in our setting the direct analog of Theorem 4. Note AAroa et al. (2019) train the hidden layer of a ReLU network via gradient descent, whereas we are training both layers with biases for network with smooth activations via gradient flow. Due to the different settings, the results are not directly comparable. This important detail notwithstanding. our overparameterization requirement ignoring logarithmic factors is smaller
n by a factor of पह where n is the number of input samples, d is the input dimension, and is the failure probability. [Basri et al. (2020) extended Theorem 4.1 in Arora et al. (2019) to deep ReLU networks without bias where the first and last layer are fixed, with a higher overparameterizattoo requirement than the original (Arora et al. 2219)) Since the first and last layers are fixed this cannot be specialized to get a guarantee for training both layers of a shallow network even with ReLU activations.
Although it was not our focus, the tools to prove Theorem 3.5 are enough to prove analogs of Theorem 4 and Corollary 2 in the work of & Yang 2019). Theorem 4 and Corollary 2 of Sf & Yang 2019) are empirical risk guarantees that show that for target functions that participate mostly
Not all these works explicitly use that the NTK is positive definite. However, they all operate in the regime where the weights do not vary much and thus typically associated with the NTK regime.
2

---

Published as a conference paper at ICLR 2022
in the top eigendirections of the NTK integral operator TK= moderate overparameterizztion is possible. Again in this work they train the hidden layer of a ReLU network via gradient descent, whereas we training both layers with biases for network with smooth activations via gradient flow. Again due to the different settings, we emphasize the results are not directly comparable. In results the bounds and requirements are comparable to & Yang (209)), with neither appearing better. Nevertheless we think it is important to demonstrate that these results hold for training both layers with biases, and we hope our "Damped Deviations" approach will simplify the interpretation of the aforementioned works.
Cao et al. (2020] Theorem 4.2) provide an analogous statement to our Theorem 3.5 you replace our quantities with their empirical counterparts. While our statement concerns the projections of the test residual onto the eigenfunctions of an operator associated with the Neural Tangent Kernel, their statement concerns the inner products of the empirical residual with those eigenfunctions. Their work was crucial step towards explaining the spectral bias from gradient descent, however view the difference between tracking the empirical quantities versus the actual quantities to be highly nontrivial. Another difference they consider a ReLU network whereas we consider smooth activations; also they consider gradient descent versus consider gradient flow. Due the different settings we would like to emphasize that the scalings of the different parameters are not directly comparable, nevertheless the networks they consider are significantly wider. They require least m Ommxx(o ())), where d is cutoff eigenvalue and is the error tolerance. By contrast in our work, to have the projection onto the top eigenvectors be bounded by epsilon in L. norm requires m a(0 e 2). Another detail is their network has no bias whereas ours does.
1.2 OUR CONTRIBUTIONS
The key idea for work is the concept of "Damped Deviatons", the fact that for the squared error deviations of the NTK are softened by a damping factor, with large eigendirections being damped the most. This enables the following results.
In Theorem 3.5 we characterize the bias of the neural network to learn the eigenfunctions of the integral operator Tx> associated with the Neural Tangent Kernel (NTK) at rates proportional to the corresponding cigenvalues.
we show that in the overparameterized setting the training error along different directions can be sharply characterized, showing that Theorem 4.1 in Arora et al. (2019) holds for smooth activations when training both layers with a smaller overparameterization requirement.
In Theorem 3.7
In Theorem 3.8 and Corollary 3.9 we show that moderate overparameterization sufficient for solving the ERM problem when the target function has a compact representation in terms of eigenfunctions of Tx= This extends the results in Su & Yang 2019)) to the setting of training both layers with smooth activations.
2 GRADIENT DYNAMICS AND DAMPED DEVIATIONS
2.1 NOTATIONS
We will use || and (o, )2 to denote the I,2 norm and inner product respectively (for vectors or for functions depending on context). For a symmetric matrix A >x(AA) denotes its ith largest eigenvalue, i.e. X1 (A) > A2(A) > ... 2 (A). For a matrix A, ||All := sup 11 $1 || the operator norm induced by the Euclidean norm. We will let pm denote the standard inner product on 1²" normalized by 1. namely (z, y)a= = (xr, 8)2 - 233h.. We will let || / (z, Z be the associated norm. This normalized inner product has the convenient property that if v E R" such that
O(1) for each then || O(1), where by contrast ||u||2 = Ov)n.. This is convenient as we will often consider what happens when n - co. || will denote the supremum norm with associated space 0 We will use the standard big O and Ω notation with Ô and Ω hiding logarithmic terms.
3

---

Published as a conference paper at ICLR 2022
2.2 GRADIENT DYNAMICS AND THE NTK INTEGRAL OPERATOR
We will let f(;;; 0) denote our neural network taking input x E IR and parameterized by E IRP. The specific architecture of the network does matter for the purposes of this section. Our training data consists of n input-label pairs {(11 V1),-.., (Iny Ni.h where Xy E Rd and y! E R. We focus on the setting where the labels are generated from a fixed target function f i.. 34 = (z;). We will concatenate the labels into a label vector E IR" i.c. = (zz). We will let f(0) E R" be the vector whose ith entry is equal to [ 0) - f (z.). Hence f(0) the residual vector that measures the difference between our neural networks predictions and the labels. We will be concerned with optimizing the squared loss
1 |A(0)112 = [|((0))
+ ((0)
2n
Optimization will be done by gradient flow
0,0, = -
which the continuous time analog of gradient descent. We will denote the residual at time 4, P(O,), ft for the sake of brevity and similarly we will let [x() [(x; 0z). We will let (x) fe(z) (x) denote the residual off of the training set for an arbitrary input x.
We quickly recall some facts about the Neural Tangent Kernel and its connection the gradient dynamics. For a comprehensive tutorial we suggest Jacot et al. (018)) The analytical NTK is the kernel given by
KT (x,xx)) =E {
Of(=;)) 0f(z':0) 00
00
where the expectation is taken with respect to the parameter initialization for 0. We associate K with the integral operator T -2((X) LX( defined by
Tk~ f(x) = f (=),,))((s)dd
where X is our input space with probability measure p. Our training data x, X are distributed according to this measure p. By Mercer's theorem we can decompose
K (2,)0) = Σ (1))
where (di Him is an orthonormal basis of L2, for is nonincreasing sequence of positive values, and each di is an eigenfunction of Tx> with eigenvalue a; > O. When X = 5dd11 is the unit sphere, p is the uniform distribution, and the weights of the network from rotation invariant distribution (c.g. standard Gaussian), { are the spherical harmonics (which in d = 2 is the Fourier basis) due to 00 being rotation-invarian (see Buullin al. 2018 Theorem 2.2). We will let == max K (zx, æ) which will be relevant quantity in our later theorems. In our setting will always be finite as K will be continuous and X will be bounded. The training data inputs (fI....,,,,) induce discretization of the integral operator Tk=, namely
Σ (K,)))))( / Km (s)))
Tnf(x) n
where Pm
1 Σn NTKR n D 8z is the empirical measure. We recall the definition of the time-dependent
K,(r, = 0f(x; 0.) 0f(z':0.)
00
30
We can look at the version of Tn, corresponding to Kr, namely
1 Σ K((t,
T+f(s) = n
Ke(r, s)(ss)))
2The NTK is overloaded term. To help ameliorate the confusion, we will use NTK to describe K and NTK (italic font) descrihe the time-dependent version K,.
4

---

Published as a conference paper at ICLR 2022
We recall that the residual r2))) == f(z;0) (x) follows the update rule
Ocr((2) - Σ (z, (.)))(z)) = -T,
==1
We will let (H,)., == (2, xzg) and H = k (x), denote the Gram matrices induced
by these kernels and we will let G. == 1 H, and G == H be their normalized version Throughout we will let uj...., A....., An. The U1.....
denote the eigenvectors of G with corresponding eigenvalues ., Un are chosen be orthonormal with respect the inner product
3*
When restricted to the training set we have the update rule
O.tt
H.f -G n1
2.3 DAMPED DEVIATIONS
The concept of damped deviations comes from the very simple lemma that follows (the proof is provided in Appendix D). The lemma compares the dynamics of the residual f(t) on the training set the dynamics of arbitrary kernel regression exp(-Gl)f(0):
Lemma 2.1. Let G E gux" be an arbitrary positive semidefinite matrix and let G2 be the time dependent NTK matrix at time Then
L expl-G((t Ses(--Git-3]GGGGGJ-ee
f. = exp(-Gttfo
- Gd.
Let's specialize the lemma to the case where G = G In this case the first term exp(-G'op t) which is exactly the dynamics of the residual in the exact NTK regime when G, G for all t. The second term is a correction term that weights the NTK deviations (G - G.) by the damping factor cxp(-G (t-s)) s)). We see that damping is largest along the large eigendirections of 6 The equation becomes most interpretable when projected along a specific eigenvector. Fix an eigenvector u, of GeD corresponding to eigenvalue A; Then the equation along this component becomes
u:)R= + ((xep(->> (t))()))) - G ue) ds.
(fr, u1)2. =
The first term above converges to zero at rate Ar. The second term is correction term that weights the deviatiations of the NTK matrix G, from G by the damping factor exp(-Ax(f - s)). The second term can be upper bounded by
1/" (expl
(eapl->,t 1x(t- G)) Gz) u.)nn ds & I'
exp((>>(t - 8)) || J0
Gzllop 1f -Ggo-Galoop
ds
exp(-Ar()
sup | - Gollop || xE(0.s)
A
where we have used the property || || from gradient flow. When f = (()) we have that | = O(),, thus whenever || - G. lop is small relative to X; this term is negligible. It has been identified that the NTK matrices tend to have a small number of outlier large cigenvalues and exhibit a low rank structure (Oymak et al., 2020 Arora et al., 2019). In light this, the de- pendence of the above bound on the magnitude of X; is particularly interesting. We reach following important conclusion.
Observation 2.2. The dynamics in function space will be similar to the NTK regime dynamics along eigendirections whose eigenvalues are large relative to the deviations of the time-dependent NTK matrix from the analytical NTK matrix.
The equation Lemma 2.1
concerns the residual restricted the training set, but we will be inter- ested in the residual for arbitrary inputs. Recall that (x( = far 02) fzr( denotes the residual at time for an arbitrary input. Then more generally we have the following damped deviations lemma for the whole residual (proved in Appendix C.3)
'Gr and T are the natural matrices to work with when working with the mean squared error as opposed to the unnormalized squared error. Also G 's spectra concentrates around the spectrum of the associated integral operator Tgo and is thus more convenient choice in our setting.
5

---

Published as a conference paper at ICLR 2022
Lemma 2.3. Let (x,x') be arbitrary continuous, symmetric, positive-deffnit kernel. Let [Tkh] = [x K( 8) s)((s)dp(s) be the integral operator associated with K and let [T = 1 - (, denote the operator associated with the time time-dependent NTK Kg. Then
S' exp(-TT<e (T) - -Ty)ra
Ft = eexp(pTTTtpp)
where the equality is in the L sense.
For main results will specialize the above lemma to the case where K = K However there are other natural kernels to compare against, say Ko or the kernel corresponding to some subset of parameters. We will elaborate further this point after introduce the main theorem. When specializing Lemma 2.3 to the case K = K we have that T and 7h are the operator analogs of G and Gs respectively. From this statement the same concepts holds before, the dynamics of rr will be similar to that of exp(- -xx= I) along eigendirections whose eigenvalues are large relative the deviations (Tx=> TH). In the underparameterrized regime we can bound the second term and make it negligible (Theorem 3.5) and thus demonstrate that the cigenfunctions Ø; of T T with eigenvalues o, will be learned rate o,, When the input data are distributed uniformly on the sphere s and the network weights are from a votation-invarian distribution, the eigenfunctions of Tk= are the spherical harmonies (which the Fourier basis when = 2). In this case the network is biased towards learning the spherical harmonics that correspond to large eigenvalues of Tg= It is in this vein that we will demonstrate a spectral bias.
3
MAIN RESULTS
Our theorems will concern the shallow neural network
1 m m
f(x;
ago (wue, x)2 + be) + bo = mm
a ooo W + +) bu.
where W E mxdd a, E R and bo E R and we = We,: denotes the 7th row of W and o T - TR is applied entry-wise. A = (aT, cec(W)T, bT, bu) E R2 where p md + 2m + is the total number of parameters. Here are utilizing the NTK parameterization (Jacot al.] 2018). For thorough analysis using the standard parameterization we suggest E et al. (2020). We will consider two parameter initialization schemes. The first initializes (0) W. (0) B, ar(0) A, by ~ B' i.i.d., where W, B, A. B3' represent zero-ment mean unit variance subgaussian distributions. In the second initialization scheme we initialize the parameters according to the first scheme and then a(0)
W(0) W b(0) [b(0)
perform the following swaps (0))
a(0) - -a(0) bo + 0 and replace the vm factor in the parameterization with /2m This is called the "doubling trick" (Chizat
b(0)
et al. 2019: Zhang et al. 2020) and ensures that the network is identically zero f(x; 0b) = 0 at
initialization. We will explicitly state where we the second scheme and otherwise will be using the first scheme.
The following assumptions will persist throughout the rest of the paper: Assumption 3.1. a is C2 function satisfying ||a'll ||o" < co. Assumption 3.2. The inputs satisfy ||æ||2 I M.
The following assumptions will used in most, but not all theorems. We will explicitly state when they apply.
Assumption 3.3. The input domain X is compact with strictly positive Borel measure
Assumption 3.4. Tg is strictly positive, i.e., T f)2 >
0 f + 0.
Most activation functions other than ReLU satisfy Assumption 3.1 such as Softplus (xx) In(1 + e²), Sigmoid (z) = T and Tanh (x)) e"-e
te Assumption 3.2 is a mild assumption which is satisfied for instance for RGB images and has been commonly used (Du et al.) 2209b
Oymak & Soltanolkotabi 2020). Assumption 3.3 is that Mercer's decomposition holds, which

---

Published as a conference paper at ICLR 2022
is often assumed implicitly. Assumption family of parameter initializations (e.g. Gaussian) anytime a not a polynomial function, as we will show in Appendix [ Assumption 3.4 is not strictly necessary but it simplifies the presentation by ensuring Tx> has no zero eigenvalues.
[ is again mild assumption that is satisfied for broad
We will track most constants that depend parameters of theorems such M, the activation function 0, and the target function f" However, constants appearing in concentration inequalities such Hoeffding's or Bernstein's inequality or constants arising from 6/2 or 6/3 arguments will not be tracked. We will reserve C > 0 for untracked constants whose precise meaning can vary from statement statement. In the proofs in the appendix it will be explicit which constants are involved.
3.1 UNDERPARAMETERIEE REGIME
Our main result compares the dynamics of the residual rx(2) of exp(-TR==[)) ()ro in the underparameterizze setting. Note that Texp(-Tx=ll)) ()ro. di)o (xp(-o,()(ro- di)2, thus exp(-Tx> ()ro learns the eigenfunctions Φ of Tx= rate o, Therefore exp(-Tk=t)rp exhibits bias learn the cigenfunctions of Tk- corresponding to large eigen- values more quickly. To our knowledge no one has been able to rigorously relate the dynamics in function space of the residual r, to exp(-Tx<=ttrag although that seems to be what is suggested by Ronen et al. (2019); Basri et al. (2020). The existing works we are aware of (Arora et al.] 2019] Basri al. 2020 Cao et al.) (020) characterize the bias of the empirical residual primarily in the heavily overparameterized regime (Cao et al. (2020) stands out as requiring wide but not necessar- ily overparameterized networks). By contrast, we characterize the bias of the whole residual in the underparameterizee regime.
[(x;0,) (xx to that
Theorem 3.5. Assume that Assumptions 3.3 and 3.4 hold. Let Ps. be the orthogonal projection in L onto span(Ti..... [b) and let D = max MM I1o'll 110'1lx,, 1). J. If we are doing the
S = 1I + S'. Also let T > Assume m 2 D22 lI T2, and m 2 (log(c/0) +00))+(())) max {T2 11. Then with probability at least 1 - 8 we have that for all t $ T and k E N
doubling trick set S' = 0 and otherwise set S' = O / ( log(c/
1- -xxp(-ool)
Vd Vm
S(1 T) vV
||P((Tr -oo
S[L+
ok
and
Vd mm
+ S(1 + T) vp
||r- - exp(-Txx()roll < 10 $[1
Theorem 3.5
will be proved in Appendix C The proof uses the uniform deviation bounds for the NTK to bound T,, TT and tools from empirical process theory to show convergence Tn to Tx uniformly over a class of functions corresponding to networks with bounded parameter norms.
To interpret the results, observe that to track the dynamics for eigenfunctions corresponding to eigenvalue d and above, the expression under the Ô needs to be small relative to 1. Thus the bias towards learning the eigenfunctions corresponding large eigenvalues appears more pronounced. When t = log( [roll2 /c// okk we have that PA cxp((Txx=t)roll) < c. Thus by applying this stopping time get that to learn the eigenfunctions corresponding to eigenvalue dg and above
dxk
up to accuracy we need 2 Z and Vm pozit In typical NTK works the width needs to be polynomially large relative to the number of samples n, where by contrast here the width depends on the inverse of the eigenvalues for the relevant components of the target function. From an approximation pfint-of-view this makes sense; the more complicated the target function the more expressive the model must be. We believe future works can adopt more precise requirements on the width yn that do not require growth relative to the number of samples n. To further illustrate the scaling of the parameters required by Theorem 3.5 can apply Theorem (35 for appropriate stopping time to get bound the test error.
L've V
< which translates to m 2 o -c- and n 2
Corollary 3.6. Assume Assumptions 3.3 and 3.4 hold. Suppose that f* = O(1) and assume we are performing the doubling trick where fo so that ro -f" Let k E N and let Pt. be

---

Published as a conference paper at ICLR 2022
the orthogonal projection onto maanf Set 1og
Then we have that
m ((a)))) and 52
suffices ensure with probability least 1
o
IIell 2e + 2 -
If one specialized to the case where f finite sum of eigenfunctions of Tς (when the data is uniformly distributed on the sphere 5 and the network weights are from rotation invariant distribution this corresponds to a finite sum of spherical harmonics, which d = 2 is equivalently a bandlimited function) one can choose such that [[(I f* = O. It is interesting to note that in this special case gradient flow with early stopping achieves essentially the same rates with respect to m and n (up to constants and logarithms) as the estimated network in the classical approximation theory paper by BBrrron 1994). It is also interesting note that the approximation results by Barron (1994) depend on the decay in frequency domain of the target function f" via their constant Cy", and similarly for us the constant 1/0 grows with the bandwidth of the target function in the case of uniform distribution on the sphere S* which we mentioned parenthetically above.
While in Theorem 3.5 we compared the dynamics of r; against that of exp( (xp(-ZZu -TK t)ro, the damped deviations equation given by Lemma 2.3 enables you to compare against exp(-Txxt)e for an arbi- trary kernel K. There are other natural choices for K besides K = K the most obvious being K Ko. In Appendix C.8 we prove a version of Theorem 3.5 where K Ko and 0, is an arbitrary deterministic parameter initialization. This could be interesting in scenarios where the parameters initialized from pretrained network one has a priori knowledge that informs the selection of 8. One could let K be the kernel corresponding to some subset of parameters, such as the random feature kernel (Rahimi & Rechi 2008b) corresponding to the outer layer. This would compare the dynamics of training all layers to that of training subset of the parameters. If one wanted to account for adaptations of the kernel K2 one could try to set K = Kt for some to > O. However since O, depends the training data it is not obvious how one could produce a bound for T Kio- Nevertheless we leave the suggestion open as a possibility for future work.
3.2 OVERPARAMETERIEE REGIME
Once one has deviation bounds for the NTK so that the quantity | Gellop controlled, the damped deviations equation (Lemma 2.T) allows one to control the dynamics of the empirical risk. In this section we will demonstrate three such results that follow from this approach. The following our analog of Theorem 4.1 from Arora et al. (2019) in our setting, proved Appendix F The result demonstrates that when the network is heavily overparameterized, the dynamics of the residual i follow the NTK regime dynamics exp(-G**tff
Theorem 3.7. Assume
( (1=))))))))))) and m 2 O(log(c0) + Ô(d) and f O(1), Assume we are performing the doubling trick so that Po = y. Let V2,..., Un denote the eigenvectors of G normalized have unit L2 norm |elll2 2 1. Then with probability at least 1-8
f. = ===xp(-G9))(--)) 8(1),
where sup:20 [15(1)]22 S e. particular
|fell2
exp(-22x0)) u1)2/
In the work of Arora et al. 2019) the requirement is m = O( = (0.,,H"")+00 and ((+)) where we ~ NO, 7) (not to be confused with our definition of = max, K00 (xr, x)). ). By contrast our weights have unit variance, which for Gaussian initialization corresponds require x to be small to ensure the neural network is small in magnitude at initializeation. To achieve the same effect we can perform antisymmetric initializeation to ensure the network equivalently at initializeation. Our overparameterizatin requirement ignoring logarithmic factors is smaller by x? factor of dør- Again due to the different settings we do not claim superiority this work.
we (0, They
8

---

Published as a conference paper at ICLR 2022
The following is our analog of Theorem 4 by Su & Yang (2019) proved in Appendix Fi This shows that when the target function has a compact representation in terms of eigenfunctions of Tk a more moderate overparametrization is sufficient to approximately solve the ERM problem.
Theorem 3.8. Assume Assumptions
3.3 and 3.4 hold.
Furthermore assume
á a RdT I1 (1+TIff))))) where > is time parameter and m 2 -(log(c/0) +
((d) and n 2 128x log(2/6) Also assume f E (X) C (2) and let pIx= be the or- thogonal projection onto the eigenspaces of TK> corresponding to the eigenvalue
(ox-0=11)²"
(TTx>> and higher. Assume that [[ pTx" )f S c' for some e' 2 O. Pick k so that = and ak+1 < a, i.e. is the index of the last repeated eigenvalue corresponding to a in the ordered sequence }o Also assume we are performing the doubling trick that f(0) = -.. Then we have with probability at least 35 over the sampling of Iı. .......,,,, In and Bg that for t S
4k 1l v (0g/0(2
||flllzm exx((= -xt) llvll== +
+26' +c.
(Øx ok+1lvn
Su & Yang (2019) have || S |l S x 3 and they treat constant. Taking these into account we do not see the overparameterization requirements or bounds of either work being 4<il , v 1100/11l22222 10log(2/5) and 1//
we immediately get the analog of Corollary 2 in the work of Su & Yang (2019). This explains how in the special case that the target function is finite sum of eigenfunctions of Tx,,, the width m and the number of samples n can grow at the same rate, up to logarithms, and still solve the ERM problem. This is an ERM guarantee for m = ((()) and thus attains moderate overparameterization.
superior to the other. From Theorem 3.8 setting
(a
Corollary 3.9. Assume Assumptions
3.3 and 3.4 hold. Furhtermore assume m 128k log(2/5) Let (dk-0R411
Q nioc ox+i== II2 (1+A, 10-+,,111 "IS ".))
m O(log(c/8) Ō(d) n
x² x211
f", PTKN, and l the same as the hypothesis of Theorem 3.8 Furthermore assume that
(1 pTw>) )f* =. Also assume we are performing the doubling trick so that f(0) -y.
Set T log( vn [F(())))))))) AR. Then we have with probability at least 35 over the sampling of 41, I' and Og that for s
8K 11 V 10 log
| S exp(-Xxe) [bll
(Ør 0k+1)/n
Note Su & Yang 2019) are training only the hidden layer of ReLU network by gradient descent, by contrast we are training both layers with biases of a network with smooth activations by gradient flow. For Corollary 2 by Su & Yang (019)) they have the overparameterization requirement m ž n log + log n log (178)
Thus both bounds scale like X Our bound has the extra factor
(A -n-7p]
) in front which could make it appear smaller at first glance but their Theorem 4 is strong enough include this factor in the corollary they just chose not to. Thus we view both overparameterization requirements comparable with neither superior to the other.
(ox xx+1)
4 CONCLUSION AND FUTURE DIRECTIONS
The damped deviations equation allows one to compare the dynamics when optimizing the squared error to that of an arbitrary kernel regression. We showed how this simple equation can be used to track the dynamics of the test residual in the underparameterized regime and extend existing sults the overparameterized setting. In the underparameterizeed setting the neural network learns eigenfunctions of the integral operator Tk determined by the Neural Tangent Kernel at rates cor- responding to their eigenvalues. In the overparameterizee setting the damped deviations equation combined with NTK deviation bounds allows one to track the dynamics of the empirical risk. In this fashion we extended existing work to the setting of a network with smooth activations where all parameters trained in practice. We hope damped deviations offers simple interpretation of the MSE dynamics and encourages others to compare against other kernels in future work.

---

Published as a conference paper at ICLR 2022
ACKNOWLEDGMENTS
Benjamin Bowman was at the Max Planck Institute for Mathematics in the Sciences while working on parts of this project. This project has received funding from the European Research Council (ERC) under the European Union's 's Horizon 2020 research and innovation programme (grant agree- ment no 757983).
REFERENCES
Zeyuan Allen-Zhu, Yuanzhi Li. and Zhao Song. A convergence theory for deep learning via over- parameterization. In Kamalika Chaudhuri and Ruslan Salakhutdinov (eds.), Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pp. 252. PMLR, 09-15 Jun 2019a. URL https: /eLLtttss//poccedligggs /ttp://pooccee.....// mlr. wlr.press/v97/Se a zhul 9a html
Zeyuan Allen-Zhu, Yuanzhi Li, and Zhao Song. On the convergence rate of training recurrent neural networks. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Buc, E. Fox, and R. Garnett (eds.), Advances in Neural Information Processing Systems, volume 32. Curran Asso- ciates, Inc., 2019b. URL /tttcpe://procceedingg.. newriisss...nnnn.io.oo..m...i..m wwtppppee/2119//...... httppp//cooooooeo..........eeeee
pdf
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 Kamalika Chaudhuri and Ruslan Salakhutdinov (eds.), Proceedings of the 36th International Conference Machine Learning, volume 97 of Proceedings of Machine Learning Research, pp. 322-332.
PMLR, 09-15 Jun 2019. URL https: httEp:://proceedingg mar...mrr..... www.s.ppess/vve ortp
html
Andrew R Barron. Approximation and estimation bounds for artificial neural networks. Machine learning, 14(1):115-133, 1994.
Ronen Basri, Meirav Galun, Amnon Geifiman, David Jacobs, Yoni Kasten, and Shira Kritchman. Frequency bias in neural networks for input of non-uniform density. In Hal Daumé III and Aarti Singh (eds.), Proceedings of the 37th International Conference on Machine Learning. volume 119 of Proceedings of Machine Learning Research, pp. 685-694. PMLR, 13-18 Jul 2020. URL
mlr (ttess//v19//aari2000 html
Alain Berlinet and Christine Thomas-Agnan. Reproducing Kernel Hilbert Spaces in Probability and Statistics. Springer, Boston, MA, 2004.
Avrim L. Blum and Ronald L. Rivest. Training a 3-node neural network is NP-complete, pp. 9-28. Springer Berlin Heidelberg, Berlin, Heidelberg, 1993. URL betts:://ci..roee
3 5440-56483- 7_
Brian Bullins, Cyril Zhang, and Yi Zhang. Not-so-random features. In International Confer- ence on Learning Representations, 2018. URL /tR.:tttss///ppeeeeeeew net/ www.:orrt/fooommmm// forum?id
Hk
Yuan Cao, Zhiying Fang, Yue Wu, Ding spectral bias of deep learning, 2020.
Ding-Xuan Xuan Zhou, and Quanquan Gu. Towards understanding the
Lénaïc Chizat, Edouard Oyallon, and Francis Bach. On lazy training in differentiable program- ming. In H. Wallach, Н. Larochelle, A. Beygelzimer, F. d'Alché-Buc, E. Fox, and R. Gar- nett (eds.), Advances in Neural Information Processing Systems, volume 32. Curran Asso- ciates, Inc., 2019. URL htttps://proceeeaaeeee neurips............ http://ws.....ppppp//////////eee Se611c557884 wtw.:432...333222233222223333533
pdf
Simon Du, Jason Lee, Haochuan Li, Liwei Wang, and Xiyu Zhai. Gradient descent finds global minima of deep neural networks. In Kamalika Chaudhuri and Ruslan Salakhutdinov (eds.), Proceedings of the 36th International Conference Machine Learning. volume 97 of Pro- ceedings of Machine Learning Research, pp. 1675-1688 PMLR, 09-15 Jun 2019a. URL
r.w.sss.p//ee............o peress/v977 du 9c. html
10

---

Published as a conference paper at ICLR 2022
Simon S. Du, Xiyu Zhai, Barnabas Poczos, and Aarti Singh. Gradient descent provably optimizes over-parameterized neural networks. In International Conference on Learning Representations, 2019b. URL httpss://pperrewieeeeeeee//////t
net/ wot.ee/oorrriii-1eee311000
Yonatan Dukler, Quanquan Gu, and Guido Montúfar. Optimization theory for ReLU neural networks trained with normalization layers. In Hal Daumé III and Aarti Singh (eds.), Proceedings of the 37th International Conference Machine Learning, volume 119 of Proceedings of Machine PMLR, 13-18 Jul 2020. URL
Learning Research, pp.
wtw.ppes/vlllv.... 9/ www.da hhtml
Weinan E, Chao Ma, and Lei Wu. A comparative analysis of optimization and generalization prop- erties of two-layer neural network and random feature models under gradient descent dynamics. Sci. China Math. 63, 1235-1258, 2020.
Suriya Gunasekar, Blake E Woodworth, Srinadh Bhojanapalli, Behnam Neyshabur, and Nati Srebro. Implicit regularization in matrix factorization. In Guyon, U. V. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett (eds.), Advances in Neural Information Processing Systems, volume 30. Curran Asso- ciates, Inc., 2017. URL /BL//t/ts////prreeediggg hew..eiis.dinnn.......s......... wwtpurrppp...pppppeepeepeep wttpp//pppp//2////ieeeee
pdff
Jiaoyang Huang and Horng-Tzer Yau. Dynamics of deep neural networks and neural tangent hicrar- chy. In Hal Daumé III and Aarti Singh (eds.). Proceedings of the 37th International Conference on Machine Learning. volume 119 of Proceedings of Machine Learning Research, pp. 4542-4555 PMLR, 18-18 Jul 2020. [ttpss:::////ecteeeet .ww.innssmm.rr....mmm.mmmm...mmm www.pppeessili...... wtt....prees///11//aaaaa2222
html
Arthur Jacot, Franck Gabriel, and Clement Hongler. Neural tangent kernel: Convergence and generalization in neural networks. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. DessaBBaanchi, and R. Garnett (eds.), Advances in Neural Information Processing Systems, volume 31. Curran Associates, Inc., 2018 URL http:: httt:::://pprcceednnng. www.eeiddinnnnn.nn.............. www.ine.rrsc.o..o Paapeaadddeeeeeaaaea.epa.eee
Ziwei Ji and Matus Telgarsky. The implicit bias of gradient descent on nonseparable data, In Alina Beygelzimer and Daniel Hsu (eds.). Proceedings of the Thirty-Second Conference on Learning Theory, volume 99 of Proceedings of Machine Learning Research, pp. 1772-1798. PMLR, 25-28
Jun 2019. URL htt.lhttp: httttp:://proccedingss.ou wtwp://wwww...........eeeeeeeee wwwpppressssss
9a .html
Hui Jin and Guido Montúfar. Implicit bias of gradient descent for mean squared error regression with wide neural networks, 2021. MxXiv:0006.07356.
Jaehoon Lee, Lechao Xiao, Samuel Schoenholz, Yasaman Bahri, Roman Novak, Jascha Sohl- Dickstein, and Jeffrey Pennington. Wide neural networks of any depth evolve linear models under gradient descent. In H. Wallach, H. Larochelle, A. Beygelzimer, d' d'Achéé-Bue E. Fox, and R. Garnett (eds.), Advances in Neural Information Processing Systems, volume 32. Curran As- sociates, Inc 2019. URL ht htttts::/pprocccedngs....t mew.eeddddiinn.e.nneeeeeeee....e pttpp/ccappppe//1///111aa [dd Mdla96511 4 38 c387 (1777718855222444--
.ddf]
Moshe Leshno, Vladimir Ya. Lin, Allan Pinkus, and Shimon Schocken. Multilayer feedforward net- works with a nonpolynomial activation function can approximate any function. Neural Nenworks, 6(6):811-677 1993. URL https: h/www//wwwww. sc encedi incedddiiiiiiiii rect com/ htmm//scienne//arti..n p11/500936080058000
Chaoyue Liu, Libin Zhu, and Misha Belkin. On the linearity of large non-linear models: when and why the tangent kernel is constant. In H. Larochelle, M. Ranzato, R. Hadsell, M. F. Bal- can, and H. Lin (eds.), Advances in Neural Information Processing Systems, volume 33, pp. 15954 15964. Curran Associates, Inc., 2020. URL httpps://prrcceediineeee neurips...e..........m cc/ 3c///aperr/222//1l///ooaae htt.ee/eeeeooooccccccceceeeee3e.
Behnam Neyshabur, Ryota Tomioka, and Nathan Srebro. In search of the real inductive bias: On the role of implicit regularization in deep learning. In Yoshua Bengio and Yann LeCun (eds.). International Conference on Learning Representations. ICLR 2015, San Diego CA, USA. May 7- 9, 2015, Workshop Track Proceedings, 2015. URL httt.tttt:////ttiiii wwwp:/wwwwwwwwrrr//////orooors// 2.6614666.4

---

Published as a conference paper at ICLR 2022
Behnam Neyshabur, Ryota Tomioka, Ruslan Salakhutdinov, and Nathan Srebro. Geometry of opti- mization and implicit regularization in deep learning, 2017. arXiv:1705.0307..
Quynh N Nguyen and Marco Mondelli. Global convergence of deep networks with one wide layer followed by pyramidal topology. In H. Larochelle, M. Ranzato, R. Hadsell, M. Bal- can, and H. Lin (eds.), Advances in Neural Information Processing Systems, volume 33, pp- 11961-11972. Curran Associates, Inc., 2020. URL htttp::/ neurips. ct/pappe//02///Eeeeepp
Samet Oymak and Mahdi Soltanolkotabi. Toward moderate overparameterization, Global con- vergence guarantees for training shallow neural networks. IEFE Journal on Selected Areas in Information Theory, 1(1):84-105, 2020.
Samet Oymak, Zalan Fabian, Mingehen Li, and Mahdi Soltanolkotabi. Generalization guarantees for neural networks via harnessing the low-rank structure of the jacobian, 2020. URL https:
//openrevi ew. net/ www.moiidddrooo......... 5CJSFPS
Nasim Rahaman, Aristide Baratin, Devansh Arpit, Felix Draxler, Min Lin, Fred Hamprecht, Yoshua Bengio, and Aaron Courville. On the spectral bias of neural networks. In Kamalika Chaudhuri and Ruslan Salakhutdinov (eds.), Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pp. 5301-5310. PMLR, 09-15 Jun 2019. URL htttps://proceedinggg pttp://s//..mm.ress/s/ssssseee wahmmma 9a html
mlr. press
Ali Rahimi and Benjamin Recht. Uniform approximation of functions with random bases. In 2008 46th Annual Allerton Conference on Communication, Control, and Computing, pp. 555-561, 2008a.
Ali Rahimi and Benjamin Recht. Random features for large-scale kernel machines. In J. Platt, D. Koller, Y. Singer, and S. Roweis (eds.), Advances in Neural Information Processing Systems, volume 20. Curran Associates, Inc., 2008b. Pttprrrfeessttiiaaaosaaaae.peeep
www.ieeu.i.... ec/
Basri Ronen, David Jacobs, Yoni Kasten, and Shira Kritchman. The convergence rate of neural networks for learned functions of different frequencies. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Buc, E. Fox, and R. Garnett (eds.), Ad- vances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019. URL hnttps::/pproceedinggss... newriiiiiiiinnnnn.....e.....iiip cc//paper/2019//11e. 02eebba8774455522777888333333
Lorenzo Rosasco, Mikhail Belkin, and Ernesto De Vito. On learning with integral operators. Jounnal of Machine Learning Research, 11(30):905 934, 2010. URL http::t///// http//innnr.rrooppprrr../ vl w/1/rosaser Da html]
Zhao Song and Xin Yang. Quadratic suffices for over-parametriiztion via matrix Chernoff bound, 2020. arXiv: 1xXiv:1906.03: 19559033...
Eduardo Sontag and Héctor J. Sussmann. Backpropagation can give rise to spurious local minima even for networks without hidden layers. Complex Systems, 3:91-106, 1989.
Eduardo D. Sontag and Héctor Sussmann. Back propagation separates where perceptrons do. Neural Networks, 4(2):243-249, 1991. URL sciience/rrticee/pii.//a
www.:wwwwiwenieeecc...c....oooee com/
httpp/iiio///.00 90008888
Daniel Soudry, Elad Hoffer, Mor Shpigel Nacson, Suriya Gunasekar, and Nathan Srebro. The im- plicit bias of gradient descent on separable data. Journal of Machine Learning Research, 19(70): 1-57, 2018. URL http///tts///iiitt.oooror/ssessp wttp:///////11111111111
Lili Su and Pengkun Yang. On learning over parameertetr neural networks: A functional approx- imation perspective. In H. Wallach, H. Larochelle, A. Beygelzimer, d'Alché-Buu E. Fox, and R. Gameett (eds.), Advances in Neural Information Processing Systems, volume 32. Curran As- sociates, Inc., 2019. URL ht http://ppppooeeeaaao...eeeeenooo http::/aww.....e.........eooeeee ottp:///pp///ooooooooooooooaaeer
12

---

Published as a conference paper at ICLR 2022
Roman Vershynin. Introduction the non-asymptotic analysis of random matrices. In Compressed Sensing, chapter 5. Cambridge University Press, 2012.
Roman Vershynin. Vighh-Dimnssooal Probubility: An Introduction with Applications in Data Sci- ence. Cambridge Series in Statistical and Probabilistic Mathematics. Cambriddge University Press, 2018.
Francis Williams, Matthew Trager, Daniele Panozzo, Claudio Silva, Denis Zorin, and Joan Bruna. Gradient dynamics of shallow univariate relu networks. In H. Wal- lach, H. Larochelle, A. Beygelzimer, F. d'Alché-Buc, E. Fox, and R. Garnett (eds.), Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019. URL Inttps::/proceeddigg http://pocced.n.....eee..i..spss www.ips.rppp...m cctpapper//019//ilee 1f6419b1
Paper. pdf
Lei Wu, Zhanxing Zhu, and Weinan E. Towards understanding generalization of deep learning: Perspective of loss landscapes. CoRR, abs/1706.10039, 2017. URL hatp:://axxi.......////
abs/1706. 1 0239
Zhi-Qin John Xu, Yaoyu Zhang, and Yanyang Xiao. Training behavior of deep neural network in frequency domain. In Tom Gedeon, Kok Wai Wong, and Minho Lee (eds.), Neural Information Processing, pp. 264-274, Cham, 2019. Springer International Publishing.
Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning requires rethinking generalization. In 5th International Conference on Learning Representations, ICLR 2017, Toulon, France, April 24-26, 2017, Conference Track Proceedings. OpenReview.net, 2017. URL /ttps::/openzevieet www.:///ttmmddddyeeeeeemee
net
Yaoyu Zhang. Zhi-Qin John Xu, Tao Luo, and Zheng Ma. A type of generalization error in- duced by initialization in deep neural networks. In Jianfeng Lu and Rachel Ward (eds.), Pro- ceedings of The First Mathematical and Scientific Machine Learning Conference, volume 107 of Proceedings of Machine Learning Research, pp. 144-164. PMLR, 20-24 Jul 2020. URL hnttps://procest .ew.inggsmm........ www..ppressse.m.. /vaess/vvloe v107 wwwp0//g2//....aiiii html
Difan Zou and Quanquan Gu. An improved analysis of training over-parameterizeer deep neu- ral networks. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Bus Buch E. Fox, and R. Garnett (eds.), Advances in Neural Information Processing Systems, volume 32, Curran As- sociates, Inc., 2019. URL /Rtphttts::///ooeeeeeee wwwp:eeedddinn....eeeeeeeeeeeeee neuries cct/ppaper/2019//1111 pff
Difan Zou, Yuan Cao, Dongruo Zhou, and Quanquan Gu. Gradient descent optimizes over- parameterized deep relu networks. Machine learning, 109:467-492. 2020.
APPENDIX
A ADDITIONAL NOTATIONS
For a set we let [A] denote its cardinality. ||~|| denotes the Frobenius norm for matrices, and for two matrices A, B e R= we will let (A, B) Tr(A" B) =
We let [k] == (1. k}.
E Σn Ai, Br, denote the Frobenius entry-wise inner product. We will let Bn {x
| S R} be the Euclidean ball of radius R 0.
B NTK DEVIATION AND PARAMETER NORM BOUNDS
Let > 1. At the end of this section we will prove high probability bound of the form
sup (x B BM
Kf(2xx') - K (x, x
1 3
13

---

Published as a conference paper at ICLR 2022
Ideally would like to use the results in Huang& & Yau (2020)
where they prove for a deep feed-
forward network without biases:
12 m
sup [z) - K K 13)] Ô gg
+
However there are three problems that prevent this. The first is that the have a constant under the Ô above that depends on the training data. Specifically their Assumption 2.2 requires that the smallest singular value of the data matrix (Za....., are arbitrary distinct indices. As you send the number of samples to infinity you will have C, + 0, thus is not clear how the bound will scale the large sample regime. The second is that their bound only holds on the training data, whereas we need bound that is uniform over all inputs. The final one is their network does not have biases. the following section we will overcome these issues. The main difference between our argument and theirs is how prove convergence initialization. In their argument for convergence at initialization they make repeated use of a Gaussian conditioning lemma they pass through the layers, and this relies their Assumption 2.2. By contrast will use Lipschitzness of the NTK and convergence over an net to prove convergence at initialization. As we see our deviation bounds for the time derivative 0,K, are proved in a very similar fashion and the rest of the argument is very much inspired by their approach.
is greater than C. > 0 where S a1..... Q, -
At the time of submission of this manuscript, that provides an alternative uniform NTK deviation bound by providing uniform bound on the operator norm of the Hessian. Their work is very nice, and opens the door to extending the results of this paper to the other architectures they consider. Nevertheless, we proceed with our original analysis below.
made aware of the work by Liu et al. (2020)
This section is conceptually simple but technical. We will take care to outline the high level structure of each section to prevent the technicalities from obfuscating the overall simplicity of the approach. Our argument runs through the following steps:
Control parameter norms throughout training.
Bound the Lipschitz constant of the NTK with respect spatial inputs.
Use concentration of subexponential random variables (Bernstein's 's inequality) to show that (x') - [x(2')| O(1/ /m) (roughly) for all z' in net of the spatial domain. Combine with the Lipschitz property of the NTK to show convergence over all inputs, namely Sup.EB., (x) - Ko(z)l = 0(1/ m)) (roughly).
Produce the bound sup BM [x) ((1/ (roughly).
Conclude that sup x Byi [K((z) - Ko(z)] = Ö(t/ Vm) (roughly).
B.1 IMPORTANT EQUATIONS
The following list contains the equations that are relevant for this section. We found easier to read the following proofs by keeping these equations on separate piece of paper or in separate tab. We write a X x = ard". Also throughout this section the training data will be considered fixed and thus the randomness of the inputs is not relevant to this section. The randomness will come entirely from the parameter initialization 0p
f(;;0) - oWox+oxx +b) bo
Vm
x01 1
Vm [WWx W +
o' = diaglo (Wa b))
d(xx) = diag(o (a" "(Wx + b))
0xf(;;0) /m
WWr + b) = (1)
fw 0) = 1
(2)
vm
14

---

Published as a conference paper at ICLR 2022
1
0.f(x;0)
(
Vm
Oba f fz; 0) =
(1)
0,a
n
1 O.W
Σ
i
(1; 8
12
m
i=1
0,6
1 (x)) )a
1=1
0,b0
Σ ft
0z = d:
( +b) = [
Vm
vm
1
A
(x)o
(x, +1]
v
mm
(z) 0,00 (o' + b) (3) W0, 0₂6)
of (I:))cag x1)2 +
B.2 A PRIORI PARAMETER NORM BOUNDS
In this section we will provide bounds for the following quantities:
[())llop 1
f. [lb(t)ll -/mm [la(t)]l2 1}
E(t) = max
((t) max max [|we())ll [I((t)l [|6(t)]l 1}.
[E(m)
Here wy We,: E Rd is the vector of input weights to the fth unit. These quantities appear repeatedly throughout the rest of the proofs of this section and thus need controlled. The
parameter norm bounds will also be useful for the purpose of the covering number argument in
Section C.6 This section is broken down follows:
Prove Lemma B.1
Bound E(!)
Bound E(t)
The time derivatives throughout will repeatedly be the form 1 Σn f,(t),, Lemma B.1 provides simple bound that will use over and over again.
Lemma B.1. Let
||]|| be any norm over a vector space V. Then for any UI...., on E we have
(())
max
[[(())
S max
||w/|l [[)(0)]
n
xE(n]
4E(n)
Proof. Note that
11
1
(1))
$
[a((0)
S max
||
(A(())
71
dEin]
72
max kE(n)
[|(())]2
max ||
[[(()]]
S max
|
[I=(0) l
Vn
<Ejm] [| || < [0)] from gradient flow.
where the last inequality follows from
15

---

Published as a conference paper at ICLR 2022
We now proceed to bound {(t).
Lemma B.2. Let E(t) = max (W( oop Jim ll((t)l2 Jim [la(t)]l. 1) and
D= 3 max (0)), m M | 1loo'loo booo .3.
Then for any initial conditions (0)), b(0), a(O) we have for all t
D Vm
!
D Vm
E(1) S exp
[((()]]R)) ds E(O) S exp
[1((0)] 1) E(O).
Proof. Recall that
0,a
1
A
(1)
i=1
1
O,W
f Vm
of (I:) 80
n
(=1
0,6
o (xx)a.
n
m
We will show that each of the above derivatives is [F(()) gM E(t) then apply Grönwall's inequality- By Lemma B.] it suffices to show that the terms multiplied by f; in the above sums are S E(t). First note that
z
o + b))
Vm
-
$ (o{(0)
vm
| WWa + bll2
< |o((0)]
+
l
|I
oop
||0:||2
[161||]
S <|a(0) + Vm
I1o'
M + [1b|12] [I
$ DE.
Second we have that
- of (z;)a
1 vm
||2/||2 s M |
||a|| S DE.
m
Finally have that
1 vm
1 vm
S 1100
10
||a||2 I DE.
Thus by Lemma B.I and the above bounds we have
[1), l()ra(t)ll (l [1,,((t)l2 S D D () E(t).
b(t) with corresponding Let v() be a placeholder for one of the functions al)) vm W(1, b()
norm |||] Then we have that
[e(()]] s |[(()]] [le(t) x(0)]l ||v(0]] + 1 (2o())ds))
< ||+(0)]| / ['1200())] < E(O) L' [f()) DE(s)
Vm
This inequality holds for any of the three choices of thus we get that
L' ||(()]la= DE(s)ds.
<t) < E(0)
Therefore by Grönwall's inequality we get that
( / [+(()]l de
D
D
[F(())l 1) E(O).
E(1) < exp
E(O) S exp
Vm
16

---

Published as a conference paper at ICLR 2022
We will now bound {tt) using essentially the same argument as in the previous lemma.
Lemma B.3. Let E(t) = max max(maase [max
(1b())l 1) and
D max (0),, ||o'll 11o' 1}.
Then for any initial conditions (O). ((0), a(O) we have for all L
D ( J. [[(())]R) ds E(O) S exp
D (cm [[F())]22 t) E(O).
E(t) S exp
Proof. The proof is basically the same as Lemma B.2
We have that
O.we = ri Vm
of ((we, + be)xz.
Now note
1
D Dg. vm"
o' ((we, xz)2 + be)xz
||a|l 10''lloo M
Vm
vm
2
Thus by Lemma
B.
we have that
10.2e(t)l22
[f(())lg) E(t).
mm
On the other hand
A (1)
0,a
11
with
1
(W + +b)
[|o(0)] + Ilo'll
[W + bllocl
m
mm
D
[o(0) + 1loo
(M max ||wlll2 + 1161(0o
< Vm
E.
m
Thus again by Lemma
B.I
we have
D 10,a(1)l s
[[(())l E(1).
Vm
Finally we have
0,b
Σ
A of (x:)a
1=1
with
| o (m:)a
D
||o mo |aal
vm E.
m
mm
Again applying Lemma B.] one last time we get
D (1F())le ε(().
|0b(()) S Vm
Therefore the same argument in Lemma B.2 using Grönwall's inequality get that
ε(1) & exp (mm / [[(()))l ds ε(() < exp
D
D
(>m [[((0)]le> &. ε(().
17

---

Published as a conference paper at ICLR 2022
B.3 NTK Is LIPSCHITZ WITH RESPECT To SPATIAL INPUTS
The NTK being Lipschitz with respect to spatial inputs is essential to our proof. The Lipschitz property means that show convergence uniformly for all inputs suffices show convergence on an e net of the spatial domain. Since the parameters are changing throughout time, the Lipschitz constant of the NTK will change throughout time. We will see that the Lipschitz constant depends on the quantities E(t) and É(t) from the previous Section B.2
The NTK Ke is a sum of terms of the form g(x)² g(x") where g is one of the derivatives fzf 8t), (z; Ow f(z; 0b,.0b. 0z). Since fa; 02) = 1 this term can be ignored for the rest of the section. The upcomming Lemma [.4]sshows that if is Lipschitz and bounded then (xr, x') > g(x) g(x") is Lipschitz. This lemma guides the structure of this section:
. Prove Lemma B.4
Show that 0./ (a;; 0), 0n5((;;;) (z;0),, Ow (a; 0) are bounded and Lipschitz
Conclude the NTK is Lipschitz
Lemma B.4. Let g: RR R' be L-Lipschitz with respect to the 2-norm, i.e.
[1a(x) - g(=) S || #|12
and satisfy 119())ll2 S M for all x in some set X. Then Kg X x X + I
k,(=,x))= = g(x)" g(z')
is ML-Lipschitz with respect to the norm
[|<,,>')|| == ||0||| + 1l2
Proof. We have
(2 - K2 = (g(x)) g(()) g(x') - g(=)² g(=')
= (=(x)) - g('))) + ((((x) - =0(=))² 9('')l
< 1l(())l12 11a(x') - g(2')112 [0(x)) -g(=))l2 Ila(2')ll2
- ML || - =1112 + ML || - =112 s ML x²) - (2,
By the previous Lemma B.4 to show that the NTK is Lipschitz it suffices to show that fz; 0), (x; 0). Ow [a: 8), fx; 0) are bounded and Lipschitz. The following lemma bounds the norms of the derivatives fa: 0), fx; 0), (x;
Lemma B.5. Let D (a)( M |oo'l ||o' 1) and
1
& = maxf
W olp
|bbl[ , vm
|aall, 13.
Then
100:::00111100000000000000000011 DE.
110
Proof. We have
(0af(x;0)1l= = =1| (Wx + b) -l
1
1 $10(0)] + vm ||o'll || Wa + bl2
1
<l0(0)] +
||0'll
[ ||=||| + +|b112]
m
1 |
<la(0)]+
[| M + [16//] s DE.
1
=
o -I
1
| S M
1 fx;;
of (x)a z
(zr)a
Vm I1o'll |1all2 DE.
Vm
vm
18

---

Published as a conference paper at ICLR 2022
[0,,(220))12
| (x)a
1 /- lo'lloo |aall2 S DE. vm
The following lemma demonstrates that 0af 0). ow fx;; and O,, 0) are Lipschitz func- tions of the input x. Lemma B.6. Ler
1
1
& max
W
|b612
|aal2
1}.
Vm
op
mm
vm
{ max
max [E(m]
| ll
||a1 |||||| 13.
D' max 1lo0 .M Ilo
L= ==
Then faf(æ; 0). 0zf(2;; 0). Ow f(z; 0) are all L-Lipschitz with respect to the Euclidean norm || In symbols:
[ 0) (r;(1;0)11 - L || - yll
[@w f(x; Owf F) S L || 10--y1 yl12 [0,,((z;)) (vr(;; I L ||x - vll2-
Proof. We have
[ 0) - -of 0)11 = (o(Wx - b) - -b)-oWWy + b))
mm
1
| [[ -1ll12 -
||o' ||x ||||, op ||. Ull2 s 1| -vl12.
vm
f(; 0) ow f(y:0)1l=>>>
1
( 2
vm -
1
m
(x)a
(---]]
w]
(x) (1)))) 81
1 2ll
[[] (w)laall llv|l2
Vm
1
1
|
||al|
|
vll2
+
I1o'
lo'Wxx + b) o' <w + bll ||al|2 M
Vm
Vm
1 |
1
||al|2
||
ull2
+
||o" 2c [[ a0 ||a||2 M
vm
|o'll
||a||2 || - vll2 +
lo"|la
max ZE(m]
|wlllz | - vlla ||lll M
Vm
$ T. || - y1l2.
1 _ (x)a J
10.f(x;00) - Ob:(v;))
vm
mm
110 (Wo x + b) o'WWy + b) ||al|
| |ax [ 2>|b,a ||a||2
|oo max |wwllz l || - vll2 ||all2 5 L || vll..
rE[m]
19

---

Published as a conference paper at ICLR 2022
Finally can prove that the Neural Tangent Kernel is Lipschitz.
Theorem B.7. Consider the Neural Tangent Kernel
K (2.z) v) = (2: 0), oof(u 8)r2 + (fof(x; 0), Ouf (): + (dw f(x; Ow:: 0)) + and let
1
1
& = max
W WWllop
|b1|2
||a||2 1}.
Vm
Vm
Vm
É max max
[weel22
||ll
||b||
1):
tE(m)
D = 3 max M | I1
11o' Fz 1},
D' max || M ||o"|l
l|o ml /-
Then the Neural Tangent Kernel is Lipschitz with respect to the norm
(x,, ||>||| llvll2
with Lipschitz constant L 6DD' In symbols:
(xx, y) K(',, ,')' = L ((x, (x', s/1ll
Proof. By Lemma B.5
we have that the gradients are bounded [10.f(x;
(x; 0) [1:,f S DE.
Also by Lemma B.6 the gradients are Lipschitz with Lipschitz constant 2EED'. Thus these two facts combined with Lemma B.4 tell us that each of the three terms fx; 0). 0af 0)), (0r (a; 0), 0o (y; 0)), and (ōw f (z; 0), Ow f (2r: 0)) are individually Lipschítz with constant (DE) (2EED"). Thus the Lipschitz constant of the NTK itself is bounded by the sum of the 3 Lipschitz constants, for total of 6...
Using that the NTK time zero Ko(z, y) is Lipschitz we can prove that the analytical NTK K = [[,o(z, y)] is Lipschitz. We will use this primarily as qualitative statement, meaning that the estimate that we derive for the Lipschitz constant will not be used it not very explicit. Rather, in theorems where use the fact that K is Lipschitz we will simply take the Lipschitz constant of K as an external parameter.
Theorem B.8. Assume that W.,J Wr,(0), ~ W, b²(0) ~ B, (e( ~ A are all i.i.d. zero-mean, unit variance subgaussian random variables. Let
1
|1(00)l2 1
E(0) max
[I(O])
/m ||a(0]]22 1}.
m
m
E(O) max
max
||6(0)) 1). (0)l1. [a(0))l
FE[m)
D = 3 max [o)) M ||o'll Il 11ol'll 1}.
D' max |oo Il MM ||o II ||10" 1lac
Then the analytical Neural Tangent Kernel K norm
(z, v) = Eo,o( w)) is Lipschitz with respect to the
(x, v)1l ||0||| llal|2
with Lipschitz constant < 6DD < co. If one instead does the doubling trick then the same conclusion holds.
Proof. First assume we are not doing the doubling trick. We note that
K (x,v) v) '' (a', v')l = [ v)) [[Ko(' ,'']l
s E (z( y) - Ko(a', 3/) S 6DD' (z, (z', 33)l
where the last line follows from the Lipschitzness of Kü provided by Theorem B.7 Using that [[]]l)) I [|W(0)) er and the fact that the Euclidean norm of a vector with i.i.d. subgaussian
entries is subgaussian (Vershynin 2018 Theorem 3.1.1), we have that ((0) and {()) maximums of subgaussian random variables. Since a maximum subgaussian random variables is subgaus- sian, we have that E(O) and (()) are subgaussian. From the inequality ab < [a22 + 1,2) we get E| < [B| + | oo since moments of subgaussian random variables all finite. Since the doubling trick does not change the distribution of Ko, the same conclusion holds under that initialization scheme.
20

---

Published as a conference paper at ICLR 2022
B.4 NTK CONVERGENCE AT INITIALIZATION
In this section we prove that sup=e Ba Ba [Ko(z) (=) 0(1/m)) Our argument traces the following steps:
Show that Ko is sum of averages of m independent subexponential random variables
Use subexponential concentration show that supa'ea [Ko(z)) K (====)===01 for all z' in an net A of Вы x Bм
Use that Ko Lipschitz and convergence over the epsilon net A to show that
[Ko(z) - K (2) = ((1/mm) (roughly)
B x Bar
We recall the following definitions 2.5.6 and 2.7.5 from Vershynin 2018
Definition B.9. (Vershynin 2018 Let Y be a random variable. Then we define the subgaussian norm Y to be
Y
| = inf > :: Eexp(Y2 2}
II #2 co, then say Y subgaussian.
Definition B.10. [Vershynin2011 Let be a random variable. Then we define the subexponential norm of Y to be
|| in [ 0: (exp((Y 2
| < oo, then we say Y is subexponential.
We also recall the following useful lemma Vershynin 2018 Lemma 2.7.7).
Lemma B.11. (Vershynin 2018) Let X and Y be subgaussian random variables. Then XY is subexponential. Moreover
XXY| < X
|Y
We recall one last definition Vershynin 2018 Definition 3.4.1)
Definition B.12. /Vershynin 2018) A random vector Y E R is called subgaussian ihe one dimen- sional marginals 2)) are subgaussian random variables for all R The subgaussian norm of is defined
|
0/2 = sup rESt
The typical example of a subgaussian random vector is a random vector with independent subgaus- sian coordinates. The following lemma demonstrates that the NTK at initializeation is sum of terms that are averages of independent subexponential random variables, which will enable us to use concentration arguments later.
Theorem B.13. Let we. be- ag all be independent subgaussian random variables with subgaussian norms satisfying < K. Furthermore assume || I K. Also let
D (aax((l(()) M |oo'l ||a''llcc 1}.
Then for fixed each of the following
fly (0.f(r: 0), O. ()) (Onf(x;; 0), (y: f f), O an averuge of m independent subexponential random variables with subexponential norms bounded by D2K3 2
Proof. We first observe that
1 (z; 0)); (a(Wx b). ( + b));
m
1
o(wer xx2 (e)o v) + bz).
21

---

Published as a conference paper at ICLR 2022
(bbf(;; (,,00),o000 00: 0)) = =1
(xx)a, -\ o (v)a)}
Vm
0z0 (() + (w,r, v12 be),
1
( I, 1 / of & v)2
(Owf(x;0), Ow f(:
Vm
( = (x. V12
di ((we, + be)o
(o)))o(((2u)) ((wee 8)2 + be).
Note that
(o((we, + bx)l S 1o(0) + 11o'l [1 x)1 + [bal].
Thus
(lo((w,, x)2 + b,)ll S |o(0)) |1||||||
+ IIo''l [1l x) 11 + |1be
S (o0) |oo'l [M [| /116 [11pa]
x 3 max (00)) M :1o s DK.
Also
(ooo((w x)2 + bn) - leel |1l1o111 1o S Dlael,
therefore
+ ( - D [[eell s DK.
Finally
KI, 2)21"/2a0 (wwe, 2)2 + be)
S M 11o'1l leell S DKK
follows by Lemma B.11 that each of (0.f(x;; f), (zy: f(x; (), Ow f(r 0)), and (0of(z; 0), fyr 0)) is an average of m independent subexponential random variables with subex-
ponential norm || 1l S K2.
We now recall the following Theorem from Vershynin (2012 Theorem 5.39) which will be useful.
Lemma 1.14 Vershynin 2012). Let A be an N x matrix whose rows A; independent subgaus- sian isorropic random vectors in R Then for every L 2 O, with probability at least 1 2 2exp( - ct2) one has the following bounds on the singular values
VN -VCn- t Smin (A) S Smaw (A) S VN + +C/++t.
Here C = CK > O depends only on the subgaussian norms K = max; || of the rows.
Also the following special case of Vershynin 2012 Lemma 5.5) will be useful for us.
Lemma B.15 /Vershynin 2012) Let Y be subgaussian. Then
P ([Y] > 1) < C exp((cct2 /|
will be useful to remind the reader that C, c > 0 denote absolute constants whose meaning will this abuse of notation becomes especially prevalent during the
vary from concentration of measure arguments of the rest the section. The following lemma provides a concentration inequality for the maximum of subgaussian random variables which will be useful for bounding & and & later which is necessary for bounding the Lipschitz constant of Ko- Lemma B.16. Let YY,..,,,, be subgaussian random variables with ||Vill there exists absolute constants c', C such that
S K Koro i [n]. Then
IP
max Y > t + K logn S (Cexp(-oP/K3) :E|n]
22

---

Published as a conference paper at ICLR 2022
Proof. Since each Y, is subgaussian have for any 2 0 (Lemma B.15
P (
- C Cexp (-ot² (12])))))
By the union bound,
max iE|nl
|i
+ K
log n
P
Y1 > 1+ K KV c- KVc
log
i=1
I exCexp -c ( K log
/K² = C exp((_c2 K
Thus by setting d' c- we get the desired result.
We now introduce high probability bound for ç. Lemma B.17. Assume that Wa3 W, be ~ B. ~ A are all i.id zero-mean, subgaussian random variables with unit variance. Furthermore assume /welllz ||aell l|bell S K for each
E [m] where K 2 1. Let
max
|bl m
[all2)
vm oop mm
Then with probability at least 1 - 6
& 511+ dd K2 log(c/8)
mm
Proof. Note that by setting least 1 -
V c log(2/0) in Lemma B.14 have that with probability at
[ op 1 Vm + c
Cvd
log(2/5)
Vm
Also by Theorem 3.1.1 in /Vershynin 2018
|||a||2
SCK²
m
|||b1| v
CCK²
Thus by Lemma B.15 and union bound we have with probability at least 1-2 26
C K² Vlog(c/6)
|all
|b]| <
1+
Vm
vm
Thus by replacing every 8 in the above arguments with 8/3 and using the union bound have with probability at least 1
d K2 log(c/8)
& $ 1+
Vm
Similarly we now introduce a high probability bound for E. Lemma B.18. Assume that W., ~ W, be ~ B, ae ~ A are all i.dd zero-mean, subgaussian random variables with unit variance. Furthermore assume [welly, ||aelly, ||bell K for each É [m] where K 1. Let
= = max [/wlll.> |alloc bb1locc Ae(m)
Then with probability at least 1 - we have
E (Tog(c/0) + Vlog m
23

---

Published as a conference paper at ICLR 2022
Proof. By Theorem 3.1.1 in (Vershynin 2018 have
|elll2 vdl S SCK²
Well then by Lemma B.16 there is constant e' 0 so that
P
max [E[m]
11eell2
vā>++ V logm
S
max [E(m]
||
l2
V
>
>1+CK
& Ceep((-cl /
Thus by setting t CK² Vlog(c/) we have with probability at least 1 8
||well2 vd CK VaacCKK-lllooea Vlo(c//5) + CK² log m
max
BE[m]
where we have absorbed the constant ve into C. Similarly by Lemma B.16 and a union bound we get with probability least - 28 that
|allx |||| I CK CK /lo(lc/) + CK V logm
Thus by replacing each with 6/3 in the above arguments and using the union bound we get with probability least 1
V [Viollc00) + Vlgmm
We now finally ready prove the main theorem of this section.
Theorem B.19, Assume that Wij W, be ~ B, A are all i.id zero-mean, subgaussian random variables with unit variance. Furthermore assume [wwllpp ||aellos libell S K for each E [m] where K 2 1. Let
D = 3 max M Iolll 1}
D' = max{1lo'llee M | Ila"
Define
(,M,,ddKK&,,))
V K2 loglc//) CDD' 1+ 1+C
(Vā+Ck² /Vlogee/6 + Vlogmi m
Vm
Let L(K denote the Lipschitz constant of K If
m 2 C(log(c/6) + log(CM max(p, L(K
then with probability at least 1 8
1 I / 2d Lodlo(CCM)) max(p, L(Ke)) Vm
sup
(x)
B BBM
one instead does the doubling trick then the same conclusion holds.
Proof. First assume
not doing the doubling trick. Recall that by Theorem B.7 that Ko is
Lipschitz with constant at most
CD)))(
where & and & are defined as in the theorem. Well then by Lemmas B.17 B.18 and union bound we have with probability at least 1 28
(()))((0) < { + Vd + K² add+Kvlogg (lg(c/0))
VV++Ck [Vlglc//0) + Vlog m }
Vm
24

---

Published as a conference paper at ICLR 2022
Let [[K),,L(K>> denote the Lipschitz constant of Kg and * respectively. Then assuming the above inequality holds we have that
L(Ko) S p(M, K,K,
(I)
For conciseness from now we will suppress the arguments of p. Now set
= 2 pa L(K*))/mm
Let (B,()))) be the cardinality of maximal 7-net of the ball BM far 1|0112 S M) with respect
to the L2 norm |=l|2. By standard volume argument we have that
CM Y
(BM) S
By taking the product of two 7/2 nets of By follows that we can choose a y net of Ba x BM say A, with respect the norm
[1z,, [2,,
||||| + llvll2
such that
CM
2d
A S (NG/2(BMr)
M,
By Theorem B.13 for (x,9) E BM x Bas fixed each of the following
(f.f(r; 0). (y: 2)), (a.f(x: 0). fur 2)), (Ow (x;6), ow fv;
average of subexponential random variables with subexponential norm at most K² Therefore separately from the randomness discussed before by Bernstein's inequality Vershynin 2018 Theorem 2.8.1) and union bound we have
mi? P([Ko(1, v) K (x, v)), > t) 3 2exp (-emin
D*K D2K3 })
mt
Thus for l S D2K we have
mtt
P([Ko( v) K w)1 S 6exp
(-TTRA
Then by union bound and the previous inequality we have that for t < D2
mt²
K (2') S 6,M exp max Ko(2²)
ZEEA
Thus by setting 1 = KD /ogiic/5)+oon (note that the condition on m in the hypothesis V
ensures that < D2 we get that with probability
max ZEA
[K((z)) K (x')l St.
Now fix E By By and choose z' such that ||2 z'll S 7. Then
[K((2) - K (=)] S Ko(z) - Ko(E')l + Ko(z') - K
(x (2') + (x)) kx (z)
< 2 ma L(K 1 +
(2)
Note that this argument runs through for any BM BM therefore
sup Bar XBM
Ko(()) - (x) max (T [(K*)))
25

---

Published as a conference paper at ICLR 2022
Well by replacing 8 with 8/3 in the previous arguments taking union bound assume that equations T and 2 hold simultaneously. In which case
Ko(2) - (2) & max(L(Ko). L(K )y + 2 m +
B x Bar
+ K2 l/g( log M,
+ C2 log(c/0) 2d log CM/7)
Vm
mm
Vm
1 CD*K Vog(e//0) + 2d log(CM max [(KK)))m)
vm
where we have used the definition of M, in the second-to-lan equality and the definition of in the last equality. Since the doubling trick does not change the distribution of Ko. the same conclusion holds under that initialization scheme.
We immediately get the following corollary. Corollary B.20. Assume that Wa W, B. at A are all i.i.d zero-mean, subgaussian random variables with unit variance. Furthermore assume |/weellp ||aellez Ilbell d/2 I K for each
i e [m]] where K 2 1. Then
m 2 Cllog(c//) O(d)]
suffices to ensure that with probability at least 8
Vd
sup Ko(2)- - Kx) = Ō
BE B x BM
mm
instead does the doubling trick then the same conclusion holds.
B.5 CONTROL OF NETWORK AT INITIALIZATION
Many of our previous results depend on the quantity [[(())] which depends on the network at initialization. Before proceed we must control the infinity of the network at initialization and work out a few consequences of this. The following lemma controls [l ( Bo)lloo-
Lemma B.21. Assume that Waj W, be B, a by B' are all i.idd zero-mean, subgaus- sian random variables with unit variance. Furthermore assume [| l| ll ||aellys ||bell <
K for each & E [m] where K 2 L. Let
D 3 maxx{(o(0)) M 11a'll 11o''l
1 1+0 Vd+ K2 Vlo(lc/5) 2
L(m, a, d, K, = Vmlll'l 10llo'll 00
vm
Assume that
m 2 C(log(c/0) dlog(CMM)).
Then with probability at least 1 - 5
sup ((xx00)) < CDK2 V loglc// -((( B
Proof. First note that
a
T b)
|alla
(Wy y + b)
Ilo + bb oWW 1oW++0 b)1l2
Vm
vm
|alla
||
||o' lox [| 2)122 <
|10'11
||
|| - 2ll2 S vm |o'll E(0) || - yll2.
Vm
mm
where {(0) is defined as in Lemma B.17
Thus f( 0o) is Lipschitz with constant L /m ||oooll E Well then by Lemma we have with probability least
2
Vd K² log(c/0) m
E(O)² <
(3)
26

---

Published as a conference paper at ICLR 2022
When the above holds we have that f( 0b) is Lipschitz with constant
L = / 1 1 vd+ K² (og((////)
vm
On the other hand note that
(0(( + be)l s |0(0) + 11o' 10 2122 -bel]-
Thus
(lo be)l - (a()) | || ||o'll [lI (ure, 222111.0 [1
- (0) || ||o'll al [M [|welly [116e11
I 3 max (0)),, M I1o'll 1lo'11loo & DK.
Therefore by Lemma B.1 have
||aja ((wy, x)2 + b,) 1 DDR.
Thus for each æ fixed we have by Bernstein's ' inequality Vershynin 20188 Theorem 2.8.1)
tymm
P
aeo (uwe, 2)2 + be) > tym)
s 22exp -emin
[DK2p DK2
Thus for & vmDK2 this simplifies to
P
aro (wwe, x)2 + be)
> ttm
S 2xxp
(DDDKK
Let A be ry net the ball Ba = fx | by standard volume argument have that
S M) with respect to the Euclidean 10/22 norm. Then
CM
d
A S
=: ::M
Thus by union bound we have for S VmDK2
t2 > ttm < 22M exp (-c
P
Σ
aco (woe x)2 + be)
D2K+)
ZEA
Thus by setting CDK² Vlo(cMM./0) assuming least 1 1-6 8
S VmDK2 we have with probability at
ai
max AEA
owwe, x)2 be) St. Vm
(4)
On the other hand by Lemma B.15 the constants c, C" to ensure that with probability at least 8
prior definition of is large enough (up redefinition of
|bo| t.
When (4) and (5) hold simultancously we have that maxwea (f 0o) < 2t. By a union bound
we have with probability at least 36 that 33. 4 (5) hold simultaneously. Well then for any x E Ba we may choose x' E A so that || - x ll
S 7 Then
[s 0o)) s (f(a3300)) (s; 0n) (((::0)) 21 Iry.
Therefore
sup (x; 0o)l s 2t + In
and this argument runs through for any > 0. We will set y = 1/L. Note that for this choice of ? the hypothesis ensures that t < VMDK3, Thus the preceding argument goes through in this case. Thus by replacing 8 with 8/3 in the previous argument we get the desired conclusion up to redefinition of e, C.
27

---

Published as a conference paper at ICLR 2022
We quickly introduce the following lemma. Lemma B.22.
|(O))l S [If( + llvll==
Proof. Let ÿ E I" be the vector whose ith entry is equal to f(z;; Well then note that ||0l| 1 [I (o)loo)) Therefore
[] = = -l S 11 + llll I IIff fo) llyll
Finally we prove one last lemma that will be useful later.
Lemma B.23. Assume that Wus W, be B, A are all i.id zero-mean, subgaussian random variables with unit variance. Furthermore assume ||||| || ,1|ae ||ae|l ||bell S K
for each E [m] where 2 Let 1, = 3 ( M |1o'l 1o'll .1,
1 1+ 1 Vd ++c K² Vlollo//)
Lm,, d, K) = vm 10llo xc
Vm
P = CDK2 - Ö(vd).
tog
Suppose
4D2 M l2 T
and m 2 max {
44D2p212 P
m
log []]
[log(T)]2
DK2
Then with probability at least 1 -
max E(t) S I'E(
max E(t) < Lε(()), SST
ST
where E(t) and E(t) are defined as in Lemmas B.2 and B.3 If one instead does the doubling trick
the second hypothesis on can be removed and the conclusion holds with probability 1.
Proof. First we doing the doubling trick. Well from the condition m (Dfz)
have by Lemma B.21 that with probability at least -
sup 1s(2; s CDK2 Vdlog(CMT.) + log(c/0) =: p.
B
Also by Lemma B.22 and the above bound we have
[A(())la= S ||ul|æ +
Well in this case
D ())(0))) t
Plll + plt <
2D 2D 2Dmax(lll ptt I log(l))
Vm
mm
Vm
where we have used the hypothesis on m in the last inequality. Therefore by Lemmas B.2 have in this case that
B.3
we
max E(t) & IE(O) *T
max E(t) S rε(())
Now assume performing the doubling trick so that f( 0o) = 0. Then p in the previous ar- gument can simply be replaced with zero and the same argument runs through, except using Lemma is not needed). Without
B.21 is longer necessary (and thus the second hypothesis ing Lemma B.21 the whole argument is deterministic so that the conclusion holds with probability 1.
28

---

Published as a conference paper at ICLR 2022
B.6 NTK TIME DEVIATIONS BOUNDS
In this section we bound the deviations of the NTK throughout time. This section runs through the following steps
Bound BB |0, (x,
Bound B [x( y) Ko(z,
In the following lemma we sup,,yEBu B. (x,
will provide
upper bound on the NTK derivative
Lemma B.24. Let
<(1) max
[W(Illop
|M01] Vm
|a())]2 1},
Vm
Vm
E(t) = max max
w
( 1}
[E/ml
= 3 m (0)), M || 1l 1|o' lx 1}
D'= |ax (olax(llo')))
(Ioo'l 11
+ 1] + loel max M).
Then for any initial conditions (()), ((0), a()) we have for all L
CDD' E(t))E(t) (f(t)l
sup BarEBrBBBa
10,K(
vm
Proof. We need to bound the following time derivatives
1
0,0,1(I; 0) = 0,x(1) = n
(z:)
(0, 21)2 + 1]
Vm
1=1
0,0w f(x; 0) = θ. vm
(
-/11//1/ (0 (x))a ((() or
0,0,f(x;0) O. _ (x)a
- (z)oa + (x))
mm
Note that
(x))
(1, xi)e ((,
11
s 1
1
1
||a||
[M1 + 1].
Vm
Vm
mm
vmn
Thus by Lemma B.I
[1;8a[(x;;0) 0) S Vm 110'113 vm
||a|| [M² + 1] [F(())
| [ - 1]] E(L) |+(()
mm
On the other hand
(z)o( =- Σ n ("(a))((())diii(())(((eee 1].
vm
i=1
29

---

Published as a conference paper at ICLR 2022
Well
+ 111 S mm
||0"| I|o' Illll llal|2 [M² +
$ $ | [M2 1)((1)((1).
Thus by Lemma B.1
we have that
[10.,o{ s |1o"|l 11x | [M² +1E(()E(() [((())l)))
Finally we have
d((2),a
Σ (
n
Well
- ||o'l
||''l vm [lo b)ll2
2
1 10 [0] + Vm
||o'll,
mo
(II op M + [1bll2]]
$ | |0(0)) + | + (oe & | (E(.).
Thus we finally by Lemma B. again we get that
(x))aal| ||a'll DE(t) [[((t))l=.
It follows that
10,0,5(2;0)1
1 mm
s |loo"llo lo'll 1M2 + 1]1+|1o'lll DJ (())()) (f(()))
and similarly
f(x;0)
M ||oo" loo 1oo'l 2M + +1] |1''ll D) (())(()) [I((t))l=.
<
Thus in total we can say
D' (())(() [I(())
|0,0, 0)1,, [x, 0)1, [0;0 <
Vm
It thus follows by the chain rule and Lemma B.5 that
CDD' Vm
sup e Bar
10,K <
(()) [f(())g))
bound the deviations of the NTK. Theorem B.25. Assume that W.g W, be B, A are all iidd zero-mean, subgaussian random variables with unit variance. Furthermore assume |!welyy,, ||aelle, |lbbllls,, S K for each L E [m]] where K 2 1. Let and T > 0 be positive constants,
Using the previous lemma
3 max (aaaxx((((0)) [0))),, M I|o'll 11oo'lle. .1, D' = ( | + 1] 1] I|o' [bd]] max(1,
and assume
4D² My _. T
4D'O(log(c/0) + 0(log(c/)) ((0g(c/0)+0((()) [lo{(T)]
m 2
[lo((T) and m 2 max
30

---

Published as a conference paper at ICLR 2022
Then with probability at least 1 -
sup
[K( - Ko(x,)))
E BM Bar
t DDCDD' CDD Vm [[(())lz)
K2 (1 [1+cvà+
1ost-KVyoggle Mog(c/0) {vā+ (Vogle/5) + Vlog m
mm
If one instead does the doubling trick then the second condition on m can removed from the hypothesis and the same conclusion holds.
Proof. First assume we are not doing the doubling trick. By Lemmas B.17 B.18 have with probability least 1
and a union bound
{ | vd + K² (lo(c//))
((0)
Vva+ CK2 CK2 [Vlog(/0)) + v Vlogm) m
}.
(6)
Vm
Note that p defined in Lemma strong enough to apply Lemma at least 1 -
B.23
satisfies p² Ollog(c/8) (d)). Thus the hypothesis on m
B.23 therefore by applying this lemma we have with probability
max E(1) < TE(O) 1ST
max IST
É(1) S TÉ(O).
Thus by replacing with 5/2 and taking union bound we have that with probability at least 1 - 6 and (7) hold simultaneously. Then using Lemma B.24 and the fact that [1)(l)) S 1IF(0))lze we have Tor / S T
CDD' (()) (F())le.. Vm
10,K( v) < 1
sup B BMM
Therefore by the fundamental theorem of calculus for t TT
Ke(x,y) Ko(0,y) S 3 CDD' {(0))ε(0) [|P(0)]
sup
vm
Ba Bad
< (D3
CDD' Vm
[F(()]]
1 +1+oVa+ks gM
vd log(c/8)
[Vd+Ck² [Violc/00) + vlgg
Vm
Now consider if one instead does the doubling trick where does the following swaps W(0) ( [
b(0)
a(0) (0) and 2m where W (0). b(0). and a(O) are initial-
6(0)
b(0) a(0)
ized as before. Then {()) and (()) do not change. We can then run through the same exact proof as before except when we apply Lemma the3 second hypothesis on m is no longer needed. D
Theorem B.26. Assume that Waj ~ W, by ~ B, at ~ A are all i.id zero-mean, subgaussian random variables with unit variance. Let r >>> and T > be positive constants and let D 3 max{(a M [|a'lloo -|oo'lloo 1}- Assume
4D2 MIv F. T [T] and 2 max
4D*O(log(c/5) -(())) Ollo((//0) +
[T)]
Then with probability at least 1 we have for T
Vd m
[ 11+1" 2 [100))..)))
(K((x,)) K (x))))))
sup (x Bas
If one instead does the doubling trick then one can remove the assumption m AD² +(oag and have the same conclusion hold.
[og(F)]
The condition 2 (llog(c/)) + Ö(d) is sufficient to satisfy the hypothesis of Theorem B.19 The condition on m also immediately satisfies the hypothesis of Theorem B.25 The desired result then follows from union bound.
Proof.
31

---

have that with probability at Published as a conference paper at ICLR 2022
Theorem B.27. Under the same assumptions Theorem B.26 least for all $
Vd
|100 Hillop S nd
1 + 3 |((0))
mm
vd
sup
- TT
Gellop 50
1 + t
[F(0)]lz=)
mm
Proof. Recall that for matrix E Ruxn ||A| S men maxi, |Aaile Thus by Theorem B.26 with probability at least 8
|| Hellop S n max
H
(He)isl S
sup (a.9)EPMxX Bar
[K((r,9) K (x.
1.
Vd
= nō
8 |+(0))le=))
vm
The second bound follows from G. H,, and 6 10
B.7 NTK DEVIATIONS FOR RELU APPROXIMATIONS
The NTK deviation bounds given in the previous subsections assumed ||a"|| co. For ReLU this assumption is not satisfied. It is natural to ask to what extent we might expect the results hold when the activation function (z) (cLU(() get to ReLU without modifying the proofs is use the Softmax approximation to ReLU, namely (xx) =
max(0, x). The closest we can
In(1 + exp(axr)), and consider what happens as a + co. For this choice of a we have where that |oo" loo Oa)). In Subsection B.6 where you will pay the biggest penalty is in Theorem B.25
via the constant D' = ((1="113)) = O(a)). Since the final bound depends on ratio D'
v you
will have that will grow like (aa²). This is moderate penalty, although might expect the results to hold for wide ReLU networks if finite a provides a reasonable approximation. In particular Softmax In(1 + exp(x)) leads fixed constant for D'.
C UNDERPARAMETERRZEED REGIME
In this section we build the tools to study the implicit bias in the underparameterizee case. Our ultimate goal is prove Theorem 3.5
Outline of this section
Review operator theory
Prove damped deviations equation
Bound ||(Tk>> Th)rell
Bound [Tr, Th ll2 using NTK deviation results (comparatively easy)
Bound [Tx=> Tllr
*
Derive covering number for class functions
Use covering number to bound sup,ec [|[Tx> TT,gll
*
Show that v, class C
Prove Theorem
3.5
C.I RKHS AND MERCER'S THEOREM
We recall some facts about Reproducing Kernel Hilbert Spaces (RKHS) and Mercer's Theorem. For additional background we suggest Berlinet Thomas- Agnan (2004). Let C Rd a compact space equipped with strictly positive (regular Borel) probability measure p. Let K XxX - be
32

---

Published as a conference paper at ICLR 2022
continuous, symmetric, positive definite function. We define the integral operator Tk (2(X) (X)
TkJ(x) == J ((a,))
In this setting Tx is a compact, positive, self-adjoint operator. By the spectral theorem there is countable nonincreasing sequence of nonnegative values {0,) and an orthonormal set {Ø; ) in L such that T = o,0, We will assume that TK is strictly positive, i.c. (f.Tkf)z f > for f * O, so that we have further that { is an orthonormal basis of L and o; > 0 for all
Moreover since K is continuous we may select the Ø; so that they are continuous functions, i.e. 6 C(X) for each i. Then by Mercer's theorem can decompose
K(x, v) = E (x))
where the convergence is uniform. Furthermore the RKHS H associated with K is given by the set of functions
01 Fi
< <00
H = FEL
1=1
where the inner product H. is given by
(f. (1.0))2(9.00 0112
(f.iH
Note that in this setting (Vor0, ) is orthonormal basis of H. Define K2 = K(o,z). Recall the RKHS has the defining properties
K. VxeX
h(x) = KahN v(z,h)
E H.
We will let & = suPaex K(x, x) < oc. From this we will have the useful inequality: for h E H
[k(x)] = (h, K2 ml S |1 [K,ll = |A v (Kg, K2) = |1 v K(x x)
< 1hl/
Furthermore the elements of H are bounded continuous functions and H. is seperable.
C.2 HILBERT-SCHMINE AND TRACE CLASS OPERATORS
We will recall some definitions from (Rosasco et al. 2010). A bounded operator on separable Hilbert space with associated norm ||]] is called
if
20
Σ
||Ae|ll 00
for some (any) orthonormal basis (ei). For such an operator we define its Hilbert-Schhiitt norm ||Al| be the square root of the above sum. The Hilbert-Schmidt norm is the analog of the Frobenius norm for matrices. is useful to note that every Hilbert-Schmidt operator is compact. The space of Hilbert-Schmidt operators is Hilbert space with respect to the inner product
(A, B)
> (Acy, Bez). Beg)
stronger notion is that trace class operator. We say bounded operator on a separable Hilbert space is trace class if
V A* 44) < 0c
33

---

Published as a conference paper at ICLR 2022
for some (any) orthonormal bases fer For such operator may define
Tr(A) : (Ae, (Ae,
By Lidskii's theorem the above sum is also equal to the sum of the eigenvalues of A repeated by multiplicity. The space of trace class operators is Banach space with the norm || Tr(vA*A). The following inequalities will be useful
||||| < | us S T|A and B is bounded have
Furthermore is Note that in setting we have
BA Hs ||AB| S |||A| || ||
2
K(x,
K(z,,)dp(z))
Σ
(1) -o;
[d((())(pp(a)
x
o
1=1
where the interchange of integration and summation justified by the monotone convergence theo- rem. Thus Tx is trace class operator and we have the inequality
1=1
which will prove useful later.
C.3 DAMPED DEVIATIONS
Let gx(x) 2 for each (0 such that (di,gr); is measureable for each i and
So l|g. l/ < oo. Then define the integral
S. gdds
coordinatewise, meaning that So g.ds is the 2 function h such that
(h, 0xi) 1/ (9..d1))dss dxx)dd.
Using this definition, we can now prove the "Damped Deviations" lemma.
Lemma 2.3. Let K K(x,x') x²) be an arbitrary continuous, symmetric, positive-deftitte kernel. Let [Txh]e = Ix K(a, ()h(s)pp(s) be the integral operator associated with K and let [T) E (,(,, (xx;) denote the operator associated with the time teeeddeendentt NTK Kg- Then
J.
Tt = cxp( + ( "exp(-Tx(e <T) r
where the equality is in the 2 sense.
Proof. We have that
0.r.(x) = Σ K, ()),))) = rT)).)())
where the equality is pointwise over O,r,(a (x) is continuous function of since K, continuous and is thus in L Therefore we can consider
(0.rs; (- (-Trrs, 9x)2.
34

---

Published as a conference paper at ICLR 2022
By the continuity of > 0, we have the parameters locally bounded in time and thus by Lemma B.5 we have that | is also locally bounded therefore for any d > 0, su: sup/s-solst | <
00.
Note then that
(0rr(1))
K2 (x) $ |[Kol 11
||Kall ||ollR
follows that |.rrsl is bounded locally uniformly in s. Therefore the following differentiation under the integral sign is justified
d (1)2 (0,rs: 01)2.
ds
Thus combined with our previous equality get
d
de fras 0.)2 (-THrr, 01)2 ( (-TKTs, + ((TK - r. 0i)2 (r., Tk ((I' r: - = (r 01)2 ((TK T rr. 01l2.
where we have used that Tk is self-adjoint. Therefore
ds (r.. 0i)2 oi (r.. 01)2 = ((TK Tx)r::
Multiplying by the integrating factor exp(o,s) we get
de (exp(a,s))r.. 01)2 exp(o,s) 01)2
Therefore applying the fundamental theorem calculus after rearrangement we get
(re, 0b)2 = exp(-o,t) 0:)2 / exp(-o,(t <)) TT) 2,)
which is just the coordinatewise version of the desired result.
Fi = =xxp(-Txx(rr + f
8)) - rrydds.
C.4 COVERING NUMBER OF CLASS
We will now estimate the covering number of the class of shallow networks with bounds on their pa- rameter norms. This lemma is slightly more general than what we will use but we will particularize latter as it's general formulation presents no additional difficulty.
Lemma C.1. Let
a Vm
C=
o (Wr + bo : I|a a'll2 Pl: IW
W P2:
||b b'1l2 S P3:
b1y s P4
||al|2 S M/. Vm
|
S ph Vm
||ا|| S p5)
m
and
>' = |o() + 11 PP2M + p' Then the (proper) covering number of C in the uniform norm satisfies
NCC, e, <
where p = mn + 2m + is the total number of parameters and C' equals
C = C max , P2M ||o') lloe ph. Ilol pak.
where C is absolute constant.
35

---

Published as a conference paper at ICLR 2022
Proof. We will bound the pertubation of the function when changing the weights, specifically will bound
T
a o ( +
sup #E BM
T (W x + b)
m
Let (1)) _ (W b) and x(1)
o (WV x + b).
Then note that we have
mm
$(1)
-
1
| lo'lls
(W W)x + 8
Vm
-
110'l1
W
w
|,||| + ||0 b1
op
110'1l00
W W/
M |10. 81 7
Vm
F
Well then
1a x1) a²'=00)
S <1a"
- 1 + 1(a - =))
=|all2 + ||a x|ل2 (2
Finally
x(1)
(w +
1 |o((0)] +
1
||o' 11
Wa
mm
2
vm
|a(0)]
1
|10'
W
|| 1l2
[
Vm
[o(0)
1
|0'11
W
M +
[6|]
mm
|00(0)] ||o'1l m0 JoS + +p/] 7
Therefore
10 x s ||all2 7 1|a -áll2
Thus if we have
||a - all2 S 47
=: E1s
|| w/e s 8M ||o li
=: =:
b b112 S
b-6
8 8110'|l 100 li
6
=: E3.
then
<laa112
|all2
4p vm 4"
Therefore
aa - (1) S c/2
and this bound holds for any x E Bys add biases bn and in such that |bn -bol S e/2 we simply get by the triangle inequality
la Tx ( + bo - (āTx() + bo)l
Thus to get cover we can simply cover the sets
{a : aa - 112 p1} {W |W - - S p2]
{b: 6-116 - pa} {bo |bo 0 b1l p4}
in the Euclidean norm and multiply the covering numbers. Recall that the e covering number for Euclidean ball of radius R in IR,,, say NC. using the Euclidean norm satisfies
CR
CR
N.
<
for two absolute constants c, C' > Therefore we get that
Cp1
Cp2
md
Cpa
2Cpp
NCC,,,
C2
36

---

Published as a conference paper at ICLR 2022
The desired result follows from
P1
P2
P3
2p4
max 1oo'l Pooll
max
22
We can now prove the following corollary which is the version of the previous lemma that we will actually for our neural network.
Corollary C.2. Let
C C= a
1 vm
1
o(Wx +)
+ bb:
|all2
|| [Wllop: vm
l1b|12 S A, |b0l s B
Vm
Vm
and
= (0() + 11''ll oc. [AM + A]
and assume m 2 Then the (proper) covering number of the uniform norm satisfies
(W(mmd) (
P
NCCC, e,C,,,111.. 11llan)
where
() max (ymAn', VmdA² ||o'1l M, /mm 110'1l ; B}
vmd0 mmxx { A2 {A², Vmd 1)
Proof. The idea is to apply Lemma C.1 with d' W 0, 0. and by 0. Note that ||W|| I WdllWllop VmnA. The result then follows by applying lemma with P = /mA. P2 VmdA, P3 /mA and A4 B and pi 0/ P3 A.
C.5 UNIFORM CONVERGENCE OVER THE CLASS
We now show that (T, Tx وااو is uniformly small for all in a suitable class of functions C'. Ultimately we will show that rt C and thus this result is towards proving that (T, Tk (rer)rrrll is small.
Lemma C.3. Let xxxxx)) by continuous, symmetric, positive-defiite kernel and let maxxEx K(I, (xI,x) <
Let Twh(o) -Ix K( s))(s)))) and Tnh(o)
(x))((())) be the associated operators. Let a denote the largest eigenvalue of Tk. Let C and Vi (m, d) be defined as in Corollary C.2 We let C' = [g ---
E C} nig ||gllse S S} be the set where C translated by the target function f* then intersected with the L ball of radius S > 0. Then with probability at least 1 over the sampling of 21. En
25 25 JolKo 2log c/6) 2p log [K] (mm, d)vn)
2
sup II Tx)gl12 < gEC'
+
log(l//)))))))) 2 1 / Ö(p)
Vn
Proof. Let g C' We introduce the random variables Y, == Kz,g(x,) (K taking values in the Hilbert space H for E [m] where H is the RKHS associated with K. Note that for any
[kng(t)lz [g(x))] (K,,K,) S S S
K (x,x)) < 1/2
Thus by Hoeffding's inequality for random variables taking values in separable Hilbert space (see Rosasco et al. (2010) Section 2.4)) we have
Thus ||Y||| 1/2
< 2 exp (-nt² /2222222
IP
Y
1=
37

---

Published as a conference paper at ICLR 2022
Note that by basic properties of the covering number have tha ||| &/C, lll)))) thus by Corollary C.2 the covering number of C' satisfies (up to a redefinition of C)
V (W(m.d))
CC Illbo) &
Y, Y= -Tn Let A be net of C' in the uniform norm. Note that 1 1. union bound we have
-KTTg Thus by taking
IIT,, Tk)9llx 21) (W(m.d) P
2exp (-n6//222S>
IP max DEA
Note that for any probability measure and h E L
/ K(x, s)h(()dd((s)
< [K(x, s(llss))ll) & || |1llo
follows that for any h E L
[[(Tk T.)hlla - 2 |1Al|
Note for any g E C' pick in A such that ||g r11 I Then
ll Tx)9l12 - |[T,, - Tk 1x)1l12 + (T, -Tk) 11
S voi [(2, - Tk)6lx + [T2, - (x - -9)ll
- Voit + | l1g - Āll
$ Vail + + | 6,
where have used the fact that Thus by setting
|| Voi || and || ||+ in the second inequality.
1 2/2 / log(c//) + 2p log (m, d)/e)
Vn
have with probability least 1 1
sup
(T, - Tx)gl12 5
gEC'
2/2 1/2 log ()/0) + 2p log V ((mmd)//
V0l
+ 11
Vn
This argument runs through for any 0. result.
Thus by setting K Vn we get the desired
C.6 NEURAL NETWORK IS IN THE CLASS
In this section we demonstrate that the neural network in such a class as C as defined in Lemma C. Once we have this we can use Lemma C.3 to show that [[ Tn)rs ll2 is uniformly small. The first step is bound the parameter norms, hence the following lemma.
Lemma C.4. Assume that Wa, W, be ~ B, at A are all i.idd zero-mean, subgaussian random variables with wnit variance. Furthermore assume [| ||well ||aellys [|bellyz S K for each E [m]] where K > 1. Let 1, T > D = max{ la (0).. M ||o'll Ilo I 13, and
1
1 Vm
E(I) max{
|
|b6|
||a||2 11.
Vm
mm
Furthermore assume
4D² ll 1 T [T]] and 2 max
(logge)( O(d)TT Ollg(c/0)) ((()) [log(T))
m
Then with probability at least 1 - 8
max E(t) ST 1+ /d K2 K22 /lo(cg//// <E
Vm
If one instead does the doubling trick then the second condition on m can be removed from the hypothesis and the conclusion holds.
38

---

Published as a conference paper at ICLR 2022
Proof. First assume not doing the doubling trick. Note that the hypothesis is strong enough to satisfy the hypothesis of Lemma B.23 therefore we have with probability at least 6
max E(C) S TE(0).
STT
Well then separately by Lemma B.17 with probability least - 8
Vd c K2 Vlo((e/))
<()) I 1 + 1
vm
Thus by replacing å with 6/2 in the previous statements and taking union bound we have with probability least 1
_ c vi + K22+ BlaKKVloogee Vlolc//))
[
max E(L) ST (E
Vm
which the desired result. Now suppose instead one does the doubling trick. We recall that the doubling trick does not change E(O). Thus we can run through the exact same argument as before except when we apply Lemma B.23 we can remove the second condition on m from the hypothesis.
The following lemma bounds the bias term. Lemma C.5. For any initial conditions we have
[bo s [bo(0)] + / [|/
Proof. Note that
(0,bo(t)l 1
F(t);
[F((]RR>
[1F(0)]RR
i=1
Thus by the fundamental theorem of calculus
[t) [bo(0)] (|
The following lemma demonstrates that the residual = f f is bounded.
Lemma C.6. Assume that We, W. be ~ B, at A are all i.i.d zero-mean, subgaussian random
variables with unit variance. Furthermore assume || ||wel|| |aell ||belly,, S K for each E [m]] where K
2 1. Let P 1, T > D = max a (0), M ||o'll lo''llo 11, and assume
4D2 B1y 2 T
AD²O(log(e/() Ō O(log(c/0) + +Ō(d)) [lo{(T))]
m
and 2 max
[T]](T)]²
Then with probability at least 1 - 6 ST
Vd K2 Vlog(c c/8)
Ilfe f" - llfo 1o1 + +111F(0)]lg= CD2T2
1 +
mm
one instead does the doubling trick then the second condition on can be removed from the hypothesis and the same conclusion holds.
Proof. Recall that
1 Σ
(f((x))) = -
1 Σ K((x,x;))(0)
((Le(x)-1100
Thus
1 Σ -f < n
Ka(x, (F)((())))) < |K [IF(() - K [10)
39

---

Published as a conference paper at ICLR 2022
Well by Lemma B.5 we have that Kello I (t) where
1
E(t) = max
W W
|bbl
||all2 17.
Vm
vm
Well by Lemma C.4 we have that with probability at least -
max {(t) I 1 vd K²
Vlog(c//)
rEjU.Ty
mm
Thus by the fundamental theorem of calculus for < T
Vd (d+K2, K2 Mog(c//)
()(x)) - r" (x)) - + CD
CD2T2
1 + C
vm
Thus by taking the supremum over æ we get
vd K2 K
- 1' < 115o 1l + +111(0)) CD2T2 +
vm
which is the desired conclusion.
We can now finally prove that [[(T - -Tnrell is uniformly small.
Lemma C.7. Let K(,, x') by continuous. symmettrcc, positive-definite kernel and let K max, K K(x,2) x) co. Let Txh(o) = ()),,)))(())dppp) and Ta)(() be the associated operators. Assume that W.,
W, be B. -i= ((,, n. (x,s) A are all iid zero-mean, subgaussian random variables with unit variance. Furthermore assume || ||wy p2 ||aeellleleeeee yo ||bell 11 0/2 K' for each E [m] where K' 2 1. Let r I, T > 0, D max (0)), M 1o''loo o and assume
4D2 By F T
4D*O(log(c/O) -((()) O(log(c/0) [log(T)}
010g(//)))))))))) +Ō(())
m 2
[T] and 2 max
If we are doing the doubling trick set S' = 0 and otherwise set
S' =C=CC(K') (L) log(c//) Ö(va).
Then with probability at least 1 5
sup [Tn Tk)rell2 = [IIMM + 0 T
+1)
Vn
and
||rollso S 111f" +S.
are performing the doubling trick the second condition be removed and the same conclusion holds.
Proof. By Lemma C.4 we have with probability at least 1 -
Vd (K'2 log(c/0) =: A.
max E(L) *
ST
+
(8)
mm
Also by Lemma
C.5
[bo( (0) Il)
If we are doing the doubling trick then (0) 0. Otherwise by Lemma B.15 we have with proba-
bility at least 5
bo [0) < CK' Vlgle//)).
40

---

Published as a conference paper at ICLR 2022
Furthermore by Lemma B.22 we have
|](())l S
lllllp- + -1)ll(;00)llo>>
Let L be defined as in Lemma B.21 i.e.
L(m, 0, d, K', /m ||~0 1 va (K')2 /logle/0))
{
Ö(vm).
m
If we are not performing the doubling trick set CCD(k') + log(c/6).
Otherwise if are performing the doubling trick set S' 0. In either case by Lemma B.21 we have with probability at least 5
1o)( S S"
(9)
In particular by Lemma B.22 we have
||(00]] S lllll= +l] S |1lllz= S"
Thus we can say
(b(()) - +
SCK' /lol///))//0)) T(lyllg +S) =:
and this holds whether or not we are performing the doubling trick. Thus up until time T the neural network is in class C as defined in Corollary C.2 with parameters A and B defined above. Moreover by Lemma separte from the randomness before we have that with probability at least 1 6
|1rl |rollac [)= CD2T2
1 1
Vd (K')² Mlog(c//)
vm
Well note that when holds we have
11f + [0))|l S ||oollo S 1l + (l.((
Thus
V4 Vd vo (K')² V |1rll S 1115 + S') 1 1 1
(orr)2/lol(/////
mm
Thus by taking union bound and redefining we have by an application of Lemma C.3 with S as defined in the hypothesis of the current theorem that with probability at least 6
2 1 + S 1
sup (Tn Tk)rell2 ETT
vn
=ō = (111 + +1)
Vn where we have used that S = Ö(1If*) + S*
+TT)).
C.7 PROOF OF THEOREM
However first must introduce a couple lemmas. The following lemma uses the damped deviations equation to bound the difference between r, and exp(-Txitrr-
We are almost ready to prove Theorem 3.5
Lemma C.8. Let K(x, x') by a continuous. symmetric, positive-definit kernel with associated operator Txh(o)= =
K( s)h(s)dp(s). Let TT) Σn K₂ 2z)(((z))) denote the oper- ator associated with the demendepnndent NTK. Then
Pa -xp(-exxxTTxx)llll S exp(-ont) sup [ r
and
(x--exp(-Tkt)olll $ sup [T r
41

---

Published as a conference paper at ICLR 2022
Proof. From Lemma 2.3 we have
r r== =x= + / exp(-Txx(1- ()) - rss),ds.
Thus for any & E N
Pa(r: - exp(exp(--xip P =Ps ( ([l-Tx((-s)](C( -- r,,
= L. Pa Prexp(- - -)] rds
Therefore
= 111' Prexp(-Tx<(l- - ()) - r.a
[Pa((r -
Caop--Txiie -Tx(t - (T) - rg)rslllds ds
< |P exxpppTx((tt f))l| (Tx- T 112 ds
< //" exp(- 5)) [[Tx r1 ds
1 - -expl okt)
sup 15
[Tx - rell
ok
Similarly
|r.- (x-cxpp-Txttrol) = 11/1 exp(-Tx(( - -))((xx) - rod
< / lexp(- -Tx(( - ()) ra)allldd ds
|eexp(- -Tx(t 8))ll [[ r ds
$ / 1[TTK rhl ds st sup |[Tx rall
In light of the previous lemma we would like to have bound for [[ Tirrall.. This is accom- plished by the following lemma.
Lemma C.9. Let K(x, x²) by continuous, symmetric, positive-defiiite kernel. Let Tkh(o) Jx ((o,KKss,iiie sd{p)) and Twh(o) = = ((,,,,),,))))). I;))((,)) be the associated operators. Let
(h)()) A E K2( xz;)) (xx;)) denote the operator associated with the time-dependent NTK.
Then
sup
[T - rll < sup [Txx - Tnrroll2 + sup || K - Kolloo [[((0)]
TT
ST
SST
Proof. We have that
|[Tx- - Tharlll - [[TK - Tw)rrlla + [[,,, - T
Now observe that
= 1 -) - x:))(
1(T, - (x))
1
K [(x, (x)))r))))))
n
K - K, [s( < <|K-- K.llac (1)
42

---

Published as a conference paper at ICLR 2022
Therefore
[1 - Th 1 1TT - Th)rollo $ || - |[((0)]R=.
Thus
sup SST
[[[x (r))rlll S
sup [(Tx Tn)roll2 SST
sup || Kalla [))()))
SgT
We are almost ready to finally prove Theorem 3.5 We must prove one final lemma that combines Lemma C.7 with the NTK deviation bounds in Theorem B.26 to show that [[ -r)rrll is
uniformly small.
Lemma C.10. Assume that Was ~ W, by ~ B, ae ~ Are random variables with unit variance. Furthermore assume || |/ p -|leell
are all i.dd zero-mean, subgaussian pp ||bell ds S K
for each E [m]] where K 2 Let 1, 0, D 3 max (0)),, M ||o'l 11 11 and
assume
4.22 11 1 T [log(T)} and 2 max
4D²O(log(c//) O
0000000000000,ee ((log(c/)) +(()))
[log(T)}
If we are doing the doubling trick set S = 0 and otherwise set
S' CDK² /llo + log(c/0) log(c))) Ö(Va), 11 Then with probability at least 6
Vd Vm [1 +
S(1 TT TiaP
sup
- est
Vn
(f can be removed
If we are performing the doubling trick the condition and the same conclusion holds.
[[][[]]]
Proof. Note by Lemma C.9 we have
sup
[TK>>
Tgrsll S sup eST
[T<K> - Tr)rsll2 sup S k Kalloo [|((0)]|
<<T
sST
Well then by Theorem B.26 we have with probability at least 8 that
sup K,
K 1lo =
vd
[
[1 a [100))l-)))
Separately by Lemma
C.7
we have with probability at least
0(11 (11//
S')(1 TT ( Vorkp
((11 + VOINT
sup STT [[ - Tr)rsl22 = δ
=0
Vn
Vn
and
| 30 S. The result follows then from taking union bound and replacing ō with 5/2.
|((())l
We now proceed to prove the main theorem of this paper.
Theorem 3.5. Assume that Assumptions 3.3 and 3.4 hold. Let Ps be the orthogonal projection in I onto span $1....... Φx and let D = max { (0) M ||a'll 11a''ll,,, 1). If we are doing the
doubling trick set S' = O and otherwise set S' = Vold) log(c//)) S = =11f S'.
Also let T > O. Assume 2 D2 Iivll T2, and m 2 O0log((/0)+ max (T Then with probability at least 8 we have that for all t < and E
1 exp(-oot) δ [Prrrr s I
Vd Vm
5(1 T) vp
S + +S]
σh
and
Vd
+ S(1 + T)) vP
|/ ex--ex((Txx= <1
S|1+15]
Fm
43

---

Published as a conference paper at ICLR 2022
Proof. By Lemma C.8
we have for any le
1 - exp(-oxk)
[ (xffreexppTxxxxxppp
sup $51
(TKx rllll
Ok
and furthermore
||r exp(-Tx roll I suu
(Tkw
Tx Tralll2
*St
Well the conditions in the hypothesis suffice apply Lemma C.10 with r e² ensure that with probability at least
vd [1 + [S] S(1 + T)
sup [TTK - SEt
Vn
Since и and 01 only depend on K which is fixed we will treat them as constants for simplicity of presentation of the main result (note that they were tracked in all previous results for anyone inter- ested in the specific constants). The desired result follows from plugging in the above expression into the previous bounds after setting σs and constants.
Theorem 3.5 is strong enough to get bound on the test error, which is demonstrated by the following corollary.
Corollary 3.6. Assume Assumptions 3.3 and 3.4 hold. Suppose that f = O(1) and assume we are performing the doubling trick where fo so that To -f" Let E N and let Ps. be
the orthogonal projection onto spantor..... ... )z). Set log( P 1
Then we have that
m = 52( (2)) and = 52 o suffices to ensure with probability at least 1 8
11rll < 20 + PA)
2
Proof. Set log(v/) (1l//e
Note that
ok
|rrel22 - |llexp(-Txxse t)roll + -
2
2
< 2 max hxtp//eepppxx_papp 1 = 11
s 2 (kx -
Note that
20 112
lexp(-I<<<e =
Σ
exp(-2o;t))(f+ 21)22
b I exp( -xxx()2xxt) Σ
61)21
Σ
i=1
i=++1
+ II(I Pa)
We want to apply Theorem 3.5 with T = t. We need
m 2 D2
||>| 2.m. 8² and m 2 O(log(c/)) + ((d) max 1].
Note that since f = (1) we have that ||=(0)]l ||v||p- = =0(1). Then
D2 livl 1 Ô ((2) δ (0)
thus condition is strong enough to satisfy the first condition. Also ((log(c/0) + O(d) max 2 1) (dd?) which is satisfied by our condition on m. Thus by application
of Theorem 3.5 with T = / we have with probability at least
||x - ex-pepp(TTx=-)rre <10 (1rIh [1 + +111
Vd Fm + 11 (1 1) VP
44

---

Published as a conference paper at ICLR 2022
Recall that f (1). Thus the first term above is
t Vd d
vd o v
=
Vm
Thus setting m = ( - suffices to ensure the first term bounded by (2v2) Similarly the second term is
δ e VD
(
vp
vn
of
Thus setting n = á (gt suffices to ensure that the second term bounded by (222/2 Thus in this case we have
1/2
||: -xp((Txx=x)oo)) 2)rol22 S
V2
Thus we have
1
2 mrel $ 2
||exp(-TT l|re 11re-exph (ire-exp(-Tpp -xxp((TT==)) 22 -1)
C.8 DETERMINISTIC INITIALIZATION
In this section will prove a version of Theorem 3.5 where instead of Op being chosen randomly we take Og to some deterministic value. Og could represent the parameters given by the output of some pretraining procedure that is independent of the training data, selected with priori knowledge.
Lemma C.11. Let Oo be a fixed parameter initialization. Let P 3 ma)((o(0)), M ||a'll ||o'll 11.
T, O
E(t) = max
[
Vm [b(()]l2 Vm la(t) l2 17.
Vm
É(1) max
max xE|m
|| (1)l2. |a(()) [1(()) 1).
Furthermore assume
D2 |1)))) 7 m 2
[To]
Then
E(t) < TE(()
max E(t) < Iε((). (E(O.T]
rE
Proof.
By the hypothesis m we have that for s T
D DI((()) Vm
< log T.
Therefore by Lemmas B.2 and B.3 the desired result holds.
Lemma C.12. Let Oo be fixed parameter initialization. Let P
1, T
0, D
3 max{[o(0)), M I|o'll I|o'Ilooo 1}.
E(I) max
(W()l Vm |101222 Vm
|a(1)) 1}.
and assume
D2 [(0)) 2 T2
m 2
R- [[]]
Then for < T
II 1' 5 $110 I (l)()) CDLT
45

---

Published as a conference paper at ICLR 2022
Proof. Recall that
0e(f(z) - (x))
Σ Ki (((x,))(((x=) Ke(z,z;)f(t
Thus
((((())))(())) -
Ki(a, x.) < |K (1((t) S |eell [I
Well by Lemma B.5 we have that Kello - (t) Also by Lemma C.11 we have that
max E(t) - [g(0). tE|o,r]
Thus by the fundamental theorem of calculus for S T
- - (x)) < [f(x)) (x)) + ()0 CD
Thus by taking the supremum over x we get
Ilfe - f' & llfo 1o + + (D)
which is the desired conclusion.
Lemma C.13. Let Oy be a fixed parameter initialization. Let Ky denote the lime-dependent NTK at initialization to. Let TK, h( = .x Ko (o s))((s)dpp and Tnh(o) = Ei= Ko( Fy h((,) be the associated operators. Lef x = max, Ko(x, x) and let 01 denote the largest eigenvalue of Ko Let l 1, T D max (0))) M ||o')l Il Ilo'lloo 1}.
1 Vm
{(O) max
|W()] op
Vm [1(0)]2
|a(0)]l2 1),
Vm
and assume
D2
+ || [oc] 12
m
[log(T)]²
Then with probability at least 1 over the sampling of 21...... Fn we have that
Tw,)rell = = (11.f*l>>> + 11 + TT (T, KT
sup
Vn
Proof. First note that
||((0)]R> S 1 - |1 + Il
(10)
Thus our hypothesis on m is strong enough to apply Lemma C.II so that we have
max {(t) - rg(0) =: A. rE|0,7
(11)
Also by Lemma C.5
[bt(t) $ [0) + ||
therefore
max (bo( < (bo (0) T (1) g= == B. FST
Thus up until time T the neural network is in class C as defined in Corollary C.2 with parameters A and B defined above. Furthermore by Lemma C.12 we have
|/ l'1 < I llc [I=(0) 1R 2D²
Well then by (10 and the above have
||rello (l (Ilollle)) (1 TCDT =:
46

---

Published as a conference paper at ICLR 2022
Thus by an application of Lemma C.3 sampling Z1,.... In that
with K Ko we have with probability at least over the
2
+ SVOIR
sup (T - TKo ET
Vn
= [115 + Ilolll (()))+++))))))))))))))))))))))))
vn
where we have used that S =
O(1lff' + 1Ifolll TTT
Lemma
C.14. Lel
0o
be
fixed
parameter initialization.
Let T
1, T
>
0,
D
=
3 m 1o'1loo, 11o' 11.
D
|max[loolll
o0 [M
m, D
<(t) max
|W Vi |6(t)]l2
la(t)]2, 11.
vm
Vm
{(t) max max [E(m)
|| [ ||(())) [l .1}.
Furthermore assume
D2 |1((0) 12 T m 2
[[og([))]²
Then for t S T
CDD' (e{(0) (F
Ko Kelloo
Vm
Proof. Note by Lemma B.24 we have that
CDD' E(t) []((t)] (r,K
sup ByyEBr Bar
Vm
Now applying Lemma C.11 and the fact that [|((t)] S [[(())l2z from the above we get that for
t < T
CDD' T' ||(()))
sup 18, (x, v)
vm
a.VE BMr BM Thus by the fundamental theorem of calculus we have that for / < T
|oo Kelloo St CDD' (E(()))(()) [[(())]
mm
Theorem C.15. Let On a fixed parameter initialization. Assume that Assumption 3.3 holds. Let {or), denote the eigenfinctions of TKo corresponding to the nonzero eigenvalues, which enumerate 0ı 2 02 2 .... Let Pk be the orthogonal projection in L onto span (1..... . Ox and let D = 3 max ( M ||o'|] ||
||o'| 1}. Also let T > 0 and set
{(O) = max
[ op -m [b(0)]l2 vm |a((0)]22 1],
Vm
{()) = max
( max w/ (0)ll, |a((0)) |Ib(0) 1). [E|m]
S = 1( + 1l.oollec ())
Assume
> D2 [1 + 11.o 1-
Then with probability at least 1 over the sampling of II,..., In we have that for all S and
k E N
[Perr -xp(p-xpppp]))p) 1 - exp(-oR()
S S
[(0) |F(0))
Ok
n
and
(00--1(0)) | + SVoInD
- ex--exp(TTxx
$10
/m
Vn
47

---

Published as a conference paper at ICLR 2022
Proof. By Lemma C.8 we have for any le N
Pk(r: - -xx((-Txx))) 1 --expp-or
sup $51
((TKo - r
ok
and furthermore
- - cx,((Txxxxxo)) tyroll - suu (T r
Let (,, = = -i= Ko zz)h(a; be the discretization Tk. Thus by Lemma C.9
we have
sup e5t
(T r.lrllle sup (T T.)rsll2 + sup ||o K (IF(0)) a5t
a5t
Note from the inequality
[F R. S |1olloo S 1
the hypothesis on m is strong enough to apply Lemma C.14 with I' = e. Well then by an application of Lemma C.14 with r e we have that
K, Koll - -0 ( {(0))E(0) [If(O))le))
sup S
Separately by Lemma C.13
we have with probability at least 1 -
(11" + 1Solloo) + TE(0))) -
sup (T 1n)r
Vn
Combining these results get that
|l(TKo rll) S ((0000)))0)) (((O)
SVonKP
sup
25t
The desired result follows from plugging in the above expression into the previous bounds.
D DAMPED DEVIATIONS ON TRAINING SET
The damped deviations lemma for the training is incredibly simple prove and yet incredibly powerful as we will see later. Here is the proof.
Lemma 2.1. Let G E Raxn be an arbitrary positive semidefinite matrix and let G2 be the time dependent NTK matrix at time Then
c: = exp(-Gt) + S (xp(-G((-s))(G- Gz)r
Proof. Note that have the equation
0,f, = GGf, = -Gf, + (G G.)
Thus by multiplying by the integrating factor ext( and using the fact that exp(Gt) and com- mute have that
a exp(G)))==xp(()))))))) exp G.)
=
Therefore by the fundamental theorem of calculus
exp(Gl) - 1o 1' (xxxpGG)((G-G::: - G.),ads
which after rearrangement gives
f = exp(-Gt)fo /' G()]GG)())(( - G.)r,ds
48

---

Published as a conference paper at ICLR 2022
Throughout will let Mi..... Uy denote the eigenvectors of G with corresponding eigenvalues A1...., An. normalized to have unit norm demonstrates that if one is only interested in approximating the top eigenvectors, then the deviations of the NT only need to be small relative to the cutoff eigenvalue X that you care about.
g.. i.c. |4 14 = 1. The following corollary
Corollary D.1. Let Ps be the orthogonal projection onto span spanfu),... (............... u Then for any & E [n]
[P expl exp((="*))) S sup | - Gollop llvollz 1 - exp(->xe
$51
sup e5t
| Gall 1|
In particular
1 - --exp(--ha (nnt) GzllR |
| -xp(-G22)fooll- I supp |
I
sup [ - -sllop |IollR 4.
An
ast
est
Proof. Note by Lemma 2.1 we have that
-))((G - -G i exp(-G = S/' expl_ (t-)s
Therefore for any & [n]
Pa(f: exp(-G**)fo) = Pv // exp(- 8)) Go
f Pa exexp( (t-pl-Gx(t-s)lllle) -G
Thus
PP - G = 1//0 Pa (xcxp(- (t) G.)r,ds
R"
1 (t GG. ds
GG,
8)) lap || -
G. |
ds
/' exp(- de(t 8)) 1 - -Galoa ||rlllæ~ ds
|1 - -Gallop |!ul|lz S'' exp(->x s))ds
< sup $5t
1 exp(-Aat)
I sup sst
| Go IloollR..
Ax
sup | - G.ll Il
*
where we have used the incquality 1+ x exp(x) in the last inequality. By specializing to the case = n since span ui,..., un, = Rd we have
sup ~ Go llop ||FollR 1- 1-exp(-Ar (xxp(AAnt)) l|fe exp(-Gx*)follee
$5t
An
sup
| Gollon || 2st
This completes the proof.
Theorem 3.5 uses the concept of damped deviations to compare r with exp(-T We can also prove the analogous statement on the training set that compares ft to exp(-G t The following is the analog of Theorem 3.5 on the training set.
49

---

Published as a conference paper at ICLR 2022
Theorem D.2. Let D 3 maxx
M| 11 .1. Also let I 1, >> 0. Further-
more assume
4D2
T RM log
1
(1//())()//)) + ((d)) [log(T)}
m N
and m 2 max
(1lo((c/))+000
Let Ps be the orthogonal projection onto span(u1.... ..... 3 have for any ls E [m] and t S
Then with probability least 1 - we
1 expeepppx
vd Vm [1
Pe - expl-eexpppCc -pp(-G-00 exp(-Gxt)f))
||ollRR. δ
8 [[((0)le-)]
d/:
Vi v [1 [1+t
1 follool δ
in particular
Vd
||fe 10--xpp exp((G
||FolRR Ō
[+ [F(O)]a]))
An
Vm
S 11follle ò
Vd
[1++)1((0))).]] 1=(0))lo.))
If one instead does the doubling trick the condition (POolog(c/()+01()))) [[og(T)]
can be removed from the
hypothesis and the same conclusion holds.
Proof. By Corollary D.I we have
exp(-Net)
[P&(fft - Cexfff-epp(-Grr exp( S sup || - G2llæ- ||oolle
A
s5t
Suup G - Gz ||Follgn
#5t
Well by Theorem B.27 have with probability least 1
sup |G - Gellop
<ō
[ 8 [I((0)]
The desired result follows from plugging this in to the previous bounds.
E PROOF OF THEOREM 3.7
We can now quickly prove our analog of Theorem 4.1 from Arora et al. (2019).
Theorem 3.7. Assume m 2
and m 2 Ollo((c/)) + Ö(d) and f" O(1). Assume are performing the doubling trick that fo y. Let U1,..., Un denote the eigenvectors of G normalized to have wnit L2 norm ||u:||2 = 1. Then with probability at least 1-
i (oxp(-G>)((-s))) 5(1),
where suP:20 [|((t]l2 5 e. In particular
|elll
exp(- v1)2/2 te.
Proof. Set T = log([)((0)) /n/ Note that since f = 0(1) and we are performing the
doubling trick we have that ||Aolle- = ||v|lg- = O(1). Recall that X := " (H therefore
2)) is strong enough to ensure that = 5e -2,, -44 -
4D2 1 T
0(2,3) m 2 O(log(c/6) + +(d)) Ō(d)
m
log 22)
50

---

((d) and n 128k² log(2/8) Also assume f (X) C L2(X) and let pl'x> be the or- thogonal projection onto the eigenspaces of TK> corresponding to the eigemvalue E (Tx=) and higher. Assume that (1-- 111-pkx>" "f é' some é' 2 O. Pick k so that = and ak+1 < a, i.e. le the index of the last repeated eigenvalue corresponding to in the ordered Then we Published as a conference paper at ICLR 2022
Then by application of Theorem all t v
D.2 with I we have with probability at least 1 5 that for
1 exp(- - -nt)
Vd
| exp(-G=o)follz
|Bol|RR Ô
[1 II ||((0)]l.)]
An
vm
|
vdl
1 + TI [|(())
An
m
Since f = (1) we have that ||Au|lR= = |1lllz- (1) therefore the above bound is
vd T
Ô Vd
Vm An
X
Thus m 2 e/ Vn. Thus in this case
Idnne ²x,²²) suffices make the above term bounded by
sup tTT
|| () S Se/vn.
Let ö(1) = fr exp(- t)ro. We have just shown that supigT [10(()llz) S s/Vnn We will now bound 6(t) for 2 T. Note that for 2 T
I expp(-Ant) ||oll <exp(-An |Rollz= S s/vVn
Also for t 2 T
| $ |/ < |exp(-G*T)folle + [6( I 22/Vn
where we have used that [|eelR is nonincreasing for gradient flow. Therefore for 2
lR= < |fellR= + G s 33/Vn
Thus have shown
sup [1(())] S 3E/Vn.
x20
The desired result follows from replacing with e/3 in the previous argument and using the fact that and în = -y.
lll
F PROOF OF THEOREM 3.8
Using some lemmas that we leave to the following section, we can prove Theorem 3.8 quite quickly using the damped deviations equation and the NTK deviation bounds.
F.I MAIN THEOREM
Theorem 3.8. Assume Assumptions 3.3 and 3.4 hold.
Furthermore assume m a time parameter and m 2 O(lo((c/) +
( 2I [1 If where
(o2-oe4:)=
sequence {arh- Also assume we are performing the doubling trick so that r(0) have with probubility at least 35 over the sampling of xı, In and Og that for ST
4k 1111 / 10010000ooo (010g(2/0) + +2''
| S Texp(-Ax) Ilvll +
(ok ok+1lyn
Proof. Recall that we have [|((0)]le = |1-vllen S | Note that m 2( 26-2 1| (1 + T [I and m > O(log(e/0) - Ô(d) are strong enough to ensure
51

---

Published as a conference paper at ICLR 2022
the hypothesis of Theorem D.2 is satisfied with I = 2. From on I = 2 (1)) and will be treated as a constant. Then by Theorem D.2 with probability at least 1 we have for I
| - exp( expp(G'' G G g) S T Pooll ò ( Va
Vm [1 TT [1((0)]l=]]
Thus using the fact from the doubling trick that [|F(0))l== lllll 1 1l setting m Q (cc ddT Il (1 T If 1lx) )xx))) suffices ensure that ||A
I for
t i T. Let Ps be the orthogonal projection onto span(ui...... ux Well then for t ST
| < llexp(-GGrm 1yroll + 2 P| () + |I Pk) () te S Espp-Axdh [|oolle- p- + |1(1 Px)follz= +
By Theorem F.6 we have with probability at least 25 over the sampling of #1,..., In that
| Px)ullg- S 2 4x 1 / (olg/2))
(0x 0++1)/n
Since we are using the doubling trick we have fo y. Thus we have
II( - Pe) S 2e' 4x ll / 10log(2/0)
(ox 0k+1l/n
Thus by taking a union bound we have with probability at least 1 - 35 for all t < T
4x 1I / 10 (2/()
| II=- S exp(-AAd) [lollR=
+ +2e' +
(ok 0h 1)
The desired result follows from fo- y.
F.2 CONTROL OF INITIAL RESIDUAL
We will use some of the notation and operator theory from Section C.1 and Section C.2 in this section, thus recommended to have read those sections first. Let U1. Un denote the eigen- vectors of G normalized to have unit norm in || i.c. ||u l|uellze = 1. Let Ps be the orthogonal projection onto span (u....., } The goal of this section is upper bound the extent to which the labels participate in the bottom eigendirections of G i.e. to show that [[ Pk)yl R is small. Let pTxx be some projection onto the top eigenspaces of Tg The idea is to show small then by picking Ps so that rank(Pk) also small with high probability. The results in this section essentially all ap-
that if || pfx="))""" "/
rank pTxx> then
- - P pear in the proofs in (Su& & Yang 2019). We repeat the arguments here for completeness and due to differences in notation and constants.
We use some of the same machinery in (Rosasco al. 2010 We define operators Lu H. + H and Tn : H. + H. by
Txt = / (S. U. K.)pks)
Twf = 1 Σ (a.KK.
Note that TN is equal to Tk= on H and Tn is simply the operator you get if you replace p in the defintion of Th with the empirical measure 1 E 82.- We define the "restriction" operator R, : H 1 by
R., = f(z)), f(..))
Note here the domain Rd is H but other parts of this paper we will allow Rn to take more general functions as input. Define R R + H by
Ry (Vi,...,, vv)) =
Σ v Kz
im
52

---

Published as a conference paper at ICLR 2022
It can be seen that
v, f) (v, Rnf)
and thus Rt is the adjoint of Rn Using these operators we may write Ta = R, and G R will follow that 7n and Go have the same eigenvalues (up to some zero eigenvalues) and their eigenvectors are related. We recall the following result from (Rosasco et al. 2010 (Proposition 9)
Theorem F.1. Rosascoo et al. 2010 The following hold
The operator T, finite rank, self-adjoint and positive, and the matrix G is symmetric and semi-positive definite. In particular the spectrum o (TT, of n. has finitely many non- zero elements and they are contained in [0, ri].
The spectrum of T, and G are the same up to zero, specifically (GG)) \ {0} a (T,,) \. {0). Moreover if X is nonzero eigenvalue and and are the corresponding eigenvector and eigenfunction for Go and T, respectively (normalized to norm in ge and || respectively), then
U1
Rn U2
1
1
0/
1 u1
Koy (ui)s
X
1/2
j=1
where (ui) is the jth component of the vector u.
The following decompositions hold
G w =
Σ
A us),n
j=1
Taf = Σ (5. j=1
where k = rank(G**) rank(Tn)) and both sums run over the positive eigenvalues. {u: le an orthonormal basis for ) and {vi)+z an orthonormal basis for ker(TT))
We will make use the following lemma from Rosasco et al. (201) Proposition 6):
Lemma F.2. (Rosasco al. 2010) Let on 02 ... ON ON+1 be the top N distinct eigenvalues of TH. Let pru be the orthogonal projection onto the eigenfunctions of Tx correspond- ing to eigenvalues ON and above. Let PI,, be the projection onto the top eigenvectors of T so that k = (i))))nge(Tn)) dim((rngee(T:) Assume further that
TTH Tull S
ON CN+1
Then
pT
pTu
HS <
2
IH Tn HH
ON+1
The following lemma will be useful. Lemma E.3. Let f L and let pTT and pTa be defined as in Lemma F.2 Then
Σ (R, pT fo), us) | dat1
pTv
pfa
HS
σk
Proof. We repeat the same proof as in (uu & Yang 2019) for completeness and to remove confusion that may arise from differences notation. The proof was originally given (Rosasco et al. 2010)
albeit with minor error involving missing multiplicative factors. Note that
pTa
Σ (r* 05)20s
53

---

Published as a conference paper at ICLR 2022
Therefore
(R p fr ui)yn = Σ (f' ( u.)a.
Applying Cauchy-Schward we get
k Kr 0322
KR pTww 8 uu)Rul
Σ
RRn و3. un) 12
h Σ j=1
- | 12
KRn u.)..1P.
Well then note that
k >
(Rndy u4) u1) 2=
Kobs RG u Σ
Ael(or, u:)
j=1
Therefore
k
Σ
(R f*) us),,)) 11f
Σ Σ
X %e aine
1
i=k+1
S 11 Ak+1
Σ
(12)
1=k+1j=
On the other hand
pTx - pTa
2
(PTx- -PTh )o
HS
j=1
-P
pTa vojos
j=1 11i
Note that for 1 iSiS k and + 1 sis we have
((PTx - pTT) ui) (pTH -o - (PTn Voro,, vinu
pT.
-Vo,oj, (v nin = (VJ,0g,
So
h
1(pTH - pJx) pTo) uiiul Σ Σ
j=1
σk Σ
3=1 i=
To summarize we have shown
1 1
pT
PTT
( u.
HS
0k
j=1
Combining this with
112 we get the final result
|f Au+1
PTx f*), 12
pTv -PT, 1
HH
1+1
54

---

Published as a conference paper at ICLR 2022
We use Lemma F33 produce the following bound.
Lemma F.4. Let f" L2 and let pTN and PTT be defined as in Lemma F22
Then
2 n
(1 pTxx (f* + 1ff 12 ARt1
(Rns" Ui)RR 12
pT -p HS
Proof. We have that
(Rnf* u1)Rr (R - plxxx f u,)2n + ptke fr, us)
Thus from the inequality (a + b)2 - 2(a² + b²) we get
n
n
KR,f u.)an S
(R p2xwpxxwFFFppp 3f" un) +2 Σ
RR pI f" (
i=k+1
i=k+1
k=++1
To control first term we have
(Tx== )f" ui) uu) S || p2x0 |
Σ
pf
n
Then by applying Lemma the second term we get the desired result.
We recall the following lemma from Rosasco al. (2010) Theorem 7)
Lemma F.5. (Rosasco et al. 2010) With probability at least 1 over the sampling of 21. Zn
2 (2/(2
[T> Tallss S
VTi
Now finally we can provide bound on the labels participation in the bottom eigendirections. Theorem F6. Assume I" E I,2(X) and let pTw= be the orthogonal projection onto the eigenspaces Tf corresponding the eigenvalue E (T<x)) and higher. Assume that
||[I-PTx> pf* 15"
for some 2 O. Pick & so that σы = a and ak+1 < a, i.e. k the index of the last repeated eigen- value corresponding to in the ordered sequence {oi)i. Let Ph denote the orthogonal projection onto span(ui..... ). Finally assume
128x log(2/8)
n Σ (ax- ok+1)2
Then we have with probability least 28 over the sampling of æ1...., Fy that
4x 1 / 10 10lgg(2/0)
[I - P = (I(T - Pa)ullg. & 2e'
(Øx oxt1)nn
Proof. From Lemma we have
Σ (Rn un)
2
(T PT0- (fx)) +
11 Ax+1
pTx
pTa
|12 HS
Ok
$=
By assumption we have that the first term is bounded by 2(e')². Now we must control the term
1
p -P
| HS
Ok
By Lemma H.5 we have with probability at least 5
2 2 log (2/5)
1T TT HS
Vn
55

---

Published as a conference paper at ICLR 2022
Then
128x log(2/0)
(Øk- 0k+1)²
suffices that the right hand side above is less than or equal to have that
1111
Thus by Lemma F.2 we
4
2
2
2ky 2 (2g(
PT - 11
IT - -T HS S
ok xx+1
0x. at+1
vn
Thus from the above inequality we get that
2 f AR+1 pTu pI= HS S
64x² ||. Ak+1 12/(2/
oz Tk+ )²
By Proposition 10 in Rosasco et al. (2010) we have separately with probability at least
2x, 2 log(2/6)
Ak+1 S 0k+1 +
vn
Note that
n 2 128x log(2/0)
(0r - 0k+11²
implies that
1
xh+1
<
Vn
8K / 12gg(2/))
therefore
AR+1 S 0b41
+
2x 220g(2/0)
1 (on - 0x+1) So
-x41) S J
5
Vn
Thus
| A6+1 1 S
64k² || Ak+1 log(2/8)
80k² 15 1og(2/5)
2
ok(0k 0k+1)
(ox 12
Thus combined with our previous results we finally get that
80k² 102 (ox ck+1) 2n
- Pn) = Σ KRRf u.)an s 2(c))
i=t+1
Thus from the inequality va+bs V2(Va+ vb) which holds for all a, 2 0 we have
I| Pa) S 22 + 4k |1 / 10logg2/5)
(ox - xk+1)
Since y = Rr,f" this provides the desired conclusion.
G T Is STRICTLY POSITIVE
Note that KT (x,)x=)))= (lo( (1)x")"w"2))))))))""))" ("))))))))) ((w, (1n,))))
where the expectation is taken with respect to the parameter initialization. It suffices show that the kernel corresponding to the first term above
Ka x') = B[a((u, x)2 + ('o +b]]
induces a strictly positive operator Tk_ f(x) = Ix Ka(a, {s)(s))((s) From the discussion in Section C. it suffices to show that the RKHS corresponding to K2 is dense in L In Proposition 4.1 in Rahimi & Recht (2008a) they showed that the RKHS associated with K2 has dense subset
F F:= x / a(w, ((w 2)2 + b)dp(w,b) b) / la(w, dp b) < o0
where μ is the measure for the parameter initialization. i.c. (w, b) ~ μ. Since C(X) is dense in T.2 (X) it suffices to show that F is dense in C(X) which is provided by the following theorem:
56

---

Published as a conference paper at ICLR 2022
Theorem G.1. Let be L-Lipschitz and not polynomial. Assume that μ is strictly positive measure supported on all of RR Also assume that
[1 [bbl))d oo.
Then F is dense in (XX) under the uniform norm.
Proof. We first show that F C C(X). Suppose we have f E FF and write f(x)
Jaats a(w, b)o((ww 2)2 (dd b). Well then
((())f(=))1 = I alw, ()[o((w, b) o(w,, 2²/2 + ( b)]du(w,
$ S J211 la(w, ()]lo( 2)2 + b) o o((w, x²)2 + b)]du((w,b)
S la(w, b) [W, 22) 2d)ld
[ 3a+1
la(w, b)1,,)]L[0 ||0 12 1 x' du(w, b)
Rd-1
V g0+1
1/2
|| du(w, b) Uge.
1/2
S - - 2'112
la(w, b)) dutu, b)
Thus / is Lipschitz and thus continuous. Now suppose that F is not dense in C(X). Then by the Riesz representation theorem there exists nonzero signed measure v(x) with finite total variation such that Jx f( (z))dv(z) = for all f F. Well then writing f(x) SRan alw, ((w, + b)du(w, o, b) as before we have
Ju alwe ()0 x)) + b)du(w,, b)du(x) =
(13)
Note that
Jeen la(w, ((W.b)ll(((wwat) z)2 b) b)
{ la(w;b)llo00)) + L ()) + bl]du(w.b)
aaw, b)][l(()) + ((000)))+++[[[])))) M + [[bll))dH[(, b) <0
R
where we have used Kauchy-Schwarz and the hypothesis the integrability of || l2 |B81 in the last step. Thus the integrand in (13) is fu x integrable thus by Fubini's theorem we may interchange the order of integration. To get that
S alw,b) b) / o(ww, x/2 + b)du(r)) b)
and the above holds for any (R Thus fx oiw x/2 ())du(x) = 0 for p-almost every w, b. However by essentially the same proof when we showed F C C(X) we may show that Ix a(w, x²)2 + ()))(x)) = a continuous function of (w, b). Thus since μ is a strictly positive measure on dR++1 this implies that [x a(ww, .r)2 + b)du(x) = 0 for every (w, b) E Rd-1 However by Theorem 1 in Leshno et al. (1993) we have that spanfo((w, æ)2 + bb: (w, b) IR++1] is dense C(X). However by our previous conclusion and linearity we have that f (x))dd(x))
.)..
for any
g in span(o ((w, +b) (w, 6) [d++1], which implics then that v/ must equal Thus F is dense
in C(X).
Since Gaussians are supported on all of IR ddd+1 we have the following corollary:
Corollary G.2. If (w, b) ~ (0, I8+1) then 1 is strictly positive.
57


Reviews:
[{"review_id": "mRHML_hweS", "reviewer": "Reviewer_Q2fJ", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper is well-written and somehow clear and easy to follow. As far as I checked, it is technically sound (I did not go through all the appendices). The authors added plenty of discussions and comparison with previous work. I particularly appreciated the residual evolution equation with the damped deviations, which is quite simple, giving good intuition on the dynamics, and is new as far as I can tell. However I have a few concerns:\n\nI am not convinced about the novelty of the contributions in this paper. The uniform Lipschitzness of the Kernel function + a bound on the change of the weights were obtained in several papers (e.g., 'On the linearity of large non-linear models: when and why the tangent kernel is constant', Liu et al.), which are the main ingredients of the uniform NTK concentration. Considering the change of the residuals (admittedly, only on the empirical data) along the eigenvectors of the NTK was already considered in 'Towards Understanding the Spectral Bias of Deep Learning’, Cao et al. While there is value in working out the technical details, I think the results in this paper are quite expected and not much surprising. At the start of the dynamics, the weights are close enough to initialization for the evolution to follow the NTK and be biased toward the top eigenvectors.  \n\nThere has been a lot of works that are studying the NTK regime. Here, the authors consider the change of the function along the data-independent eigendirections of the NTK (the fact that we are using early stopping is another clue that we are not escaping the NTK regime). Several works have showed convincingly that the interesting question is to study how GD escape the RKHS and learn functions that are not aligned with NTK, which I am not convinced can be done with these techniques. Furthermore, the spectral bias is well understood  for linear models and kernel methods, which is approximately the behavior of models at the beginning of GD so that we don’t need much overparametrization in order to still be able to get NTK-like behavior.\n\nIf the point is to study the underparametrized regime, other work like 'Generalization error of random features and kernel methods: hypercontractivity and kernel matrix concentration’ (Mei et al.) showed that training only the second layer (random features model), $\\min(n,m) \\geq d^{\\delta} / \\sigma_k$ is enough to learn perfectly the top $k$ eigenvectors, which is much tighter than the results in Corollary 3.6. I am not sure that developing more techniques to study the NTK regime is interesting or helpful, especially if they are not tight with respect to the dependency on the different parameters.", "summary_of_the_paper": "In this paper, the authors study gradient flow on the empirical squared loss. More specifically, they consider the evolution in function space of the residuals and show that it can be written as the sum of 1) the residual obtained by training with the NTK operator (infinite width and samples, no training of the kernel), and 2) damped deviations between time dependent kernel matrix and the NTK operator. Based on this decomposition and a uniform deviation bound on the NTK, they show that 1) in the underparametrized regime, GD at the beginning of the dynamics learn eigenfunctions of NTK at rates proportional to the corresponding eigenvalues; 2) in the overparametrized regime, they derive new bounds for the `kernel regime’ to appear; 3) in the overparametrized regime, if we further assume that the target function is aligned with the top eigenvectors of the NTK, then a milder overparametrization is required.", "summary_of_the_review": "I am not convinced that the current paper is bringing anything new to what is already known about the `spectral bias’ in the NTK regime, even though I believe the technical contribution to be non-trivial. For that reason, my recommendation is marginally below the acceptance threshold. If the authors can convince me that this damped equation can be used in more interesting ways (take target function in a different RKHS or use $K^\\infty$ that is not the NTK etc.) or that I misunderstood or missed some important conceptual/technical contributions, I will raise my recommendation!", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "eAz0papT3XS", "reviewer": "Reviewer_VUVP", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "This is an interesting theoretical work. The main technique of analysis, if I understood correctly, is to use the infinite width NTK dynamics, which is linear, as an auxiliary term to add and subtract from the actual dynamics, and leverage Duhamel’s principle to study the finite width situations. This is not a completely new trick, as it is often used in the mathematical literature for differential equations; nevertheless, I still think it is remarkable to actually execute the idea (well) for the important problem of neural networks, even if it’s just deterministic gradient flow and 2-layer. I therefore gave a positive rating. Still, there are a few things that I’d like to understand better, hence the followings.\n\nOne of my questions is, quantitatively, what regime is exactly the underparameterized regime considered in Theorem 3.5? I’m confused because I didn’t find any assumption on n (number of data). Is it implicitly assumed that Theorem 3.5 applies when $n>m$? Why is the lower bound of $m$ in Theorem 3.5 independent of $n$?\n\nAnother question about Theorem 3.5 is, are $\\Gamma$ and $T$ really just any numbers that satisfy $\\Gamma>1$ and $T>0$? If yes, why not optimize over them to get the best bound?\n\nOne more question is, did I understand right about Theorem 3.5 that $exp(-T_K t)r_0$ is decreasing but the bound on its difference from $r_t$ is growing quadratically in t? Wouldn’t this produce a low “signal-to-error” ratio?\n\nI’m also wondering about the gap between the underparameterized regime in Section 3.2 and the overparameterized regime in Section 3.3. If 3.2 really requires $n>m$ (see above), the gap is rather large. What can happen there? Some explanations in the main paper would be very helpful.\n\nI also found the comparison with [Arora et al. 2019] and [Su & Yang 2019] helpful. I understand that this work trains both layers and there are many other important differences (well stated in the paper and thus omitted here), but these are mostly in terms of the results. Could the authors also comment about the differences (and similarities) in terms of the analysis techniques?\n\nA couple of minor observations:\n\n* Section 1.1 Related work, reference Weinan E (2020) should be [E et al. 2020]\n\n* Lemma 2.1 “… semidefinite matrix $G_s$ the time dependent …” probably means “… semidefinite matrix and $G_s$ be the time dependent …”\n\n* No empirical results are provided. This is probably okay, but of course if the tightness of the theoretical results could be supported by empirical evidence, it would be fantastic.\n", "summary_of_the_paper": "This paper considers the gradient flow training of 2-layer neural network (both layers are trained) and provides a theoretical tool termed “damped deviations” for improved NTK analysis. One outcome is a characterization of how a neural network deviates, when in an underparameterized regime, from learning the eigenfunctions of the integral operator associated with infinite width NTK at rates proportional to the corresponding eigenvalues.", "summary_of_the_review": "I found this work very interesting. The proposed theoretical tool of “damped deviations” is useful, and the outcome (the “characterization”, see Summary of The Paper) is a nontrivial step for the important task of going beyond infinite overparameterization.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "NC567WheMuX", "reviewer": "Reviewer_hz1D", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "First, I would like to say that I am nor an expert neither a contributor of the abundant NTK literature. Hence, even if I know well the phenomenon as well as kernel methods, I might under-appreciate the novelty of the bounds presented in the paper under review.\n\nThat being said, I have to say that the *story of the paper* is clearly written with a nice introduction that makes the reader eager to discover what is really in it. The question: « to what extent is the NTK informative outside the NTK regime ?» could be of primal importance and introduces nicely the paper. *However*, when it comes to the paper itself, I have to say that I was a bit disappointed. \n\nFirst, the two last paragraphs of the related work are a bit fuzzy comparing bounds with previous papers that are not so much in the exact setting, and furthermore not explaining why it is interesting to have improved these bounds, or considered another setting. That made me think: *what is the actual message of the paper ?* This impression is reinforced by the fact that the title indicates that the focus will be on the implicit bias of neural networks whereas it is really on the NTK regime and hence on the implicit bias of kernel methods.\n\nGoing further, my main problem on this paper comes with the second disappointment: in my opinion, the paper does not really study neural nets outside the NTK regime as either it compares to the NTK itself for the test error (Theorem 3.5) or either show convergence to 0 of the train error (Theorems 3.7 and 3.8). In other words, the authors suggest that their damped deviation analysis could be the first stone towards getting a bit out of the NTK regime, but under the current form, I am not very convinced by the argument.  On the one side, I understand that obviously this is not the aim of Theorems 3.7 and 3.8 that could be nice technical contributions of their own (once again I lack some knowledge in this specific domain and do not know how impactful these results are). On the other side, in my opinion, Theorem 3.5 and Corollary 3.6 really describe regimes (underparametrized with large $m$ and $n$) under which the trajectory of the gradient flow remains in the vicinity of the trajectory of the true NTK gradient flow. Then the fact that the estimator given by the flow learns first eigenfunctions of the integral operator related to large eigenvalues in usual in kernel methods. In my opinion getting outside of the NTK regime requires other analysis than the one given in Theorem 3.4: that is I cannot consider new an analysis that presents systematically deviations from the Neural Tangent Kernel.\n\n**In conclusion**, I am not saying that the results are not interesting, but in my opinion they are quite *expected* and are not conceptual novelties but rather technical ones. To what extend these are new, I do not know. \n\n\n\n\nMinor Typos:\n\n- page 2, 3rd paragraph : « generalizeation » \n- page 2, 4th paragraph : « is is smaller by… » \n- page4, authors may precise that $L^2$ is in fact $L^2_\\rho$, precise also that $\\kappa$ is finite under mild assumptions on the model but not always the case\n- page4, lemma 2.1, put a « and » before $G_s$ ", "summary_of_the_paper": "In the paper under review, the authors study the behaviour of gradient flow in the kernel regime of one hidden layer neural networks. More precisely, they show deviations bounds on the test error  w.r.t. the true NTK gradient flow in the underparametrized regime and train error bounds in the overparametrized regime.", "summary_of_the_review": "As a non-specialist of the NTK regime, I may underestimate the technical contribution of the present paper, but I was not surprised by the results and see the submission as a detailed and nice technical improvement of known results in the NTK regime. Hence, I am between neutral and unsatisfied by the paper.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "9Dbt6YYS7bX", "reviewer": "Reviewer_bKHH", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths\n----\n- The work provides an original treatment of neural networks in under-parametrized regime. A number of new results are established.\n- The paper is well-written and easy to follow.\n- The paper appears to be technically correct. The theoretical setting of the paper is clearly stated.\n- The tecniques developed in this paper are powerful enough to recover and extend previous works even in the over-parametrized regime.\n\nLimitations\n---\n- My main critic is that the ssumptions of the paper exclude nonsmooth activation functions,  for example (perhaps) the most important activation function known to both practitioners and theoreticians alike: the ReLU. Which part aspect of the proofs needs smoothness of the activation function ?\n- The analysis in this paper is for continuous time gradient-descent (i.e gradient-flow). Which aspects of the results would continue to hold after time discretization ?\n- There have been other contributions on the function-space view of neural gradient descent on neural networks (for example Ongie et al. \"A FUNCTION SPACE VIEW OF BOUNDED NORM INFINITE WIDTH RELU NETS: THE MULTIVARIATE CASE\", ICLR 2020). Is there any comparison to be made here ?\n\nQuestions\n---\n- All the results in this paper appear to be about training error. Can anything be said about generalization error, i.e $\\mathbb E_{x \\sim \\rho}[r_t(x)^2]$ ?\n", "summary_of_the_paper": "This work studies the implicit bias of optimizing underparametrized neural networks with MSE loss function and establishes upper-bounds on the training error. One of the takeaways of the paper is that under-parametrized neural networks first learn the most important eigenfunctions associated with the NTK integral operator. This is what the work posits as the implicit bias of gradient-descent in this setting. A key tool developed in the paper is the concept of damped deviations, where in the evolution of MSe w.r.t to one kernel is related to that of another kernel and the damped \"distance\" between these kernels. As a byproduct, the paper uses this tool to extend certain results in the literature in the over-parametrized setting.", "summary_of_the_review": "A new function-space view of gradient-flow on neural networks. Establishes that in function space, dynamics of training (when projected along the most important eigendirections of the associated kernel integral operator, is very similary to NTK dynamics, even in under-parametrized regime.\n\n\nAfter authors' response\n---\n\nMy concerns have been fully addressed by the reviewers. I'm raising my score from 6 to 8, and therefore strongly recommending the paper for acceptance.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}]

Author rebuttal:

Meta-review: There was a healthy discussion with all the reviewers with a consensus that the results are somewhat expected and unlikely to shed light beyond the ntk  regime, yet within the confine of ntk there is a solid and nicely written technical contribution.
Decision: Accept (Poster)