Spectral Bias Outside the Training Set for Deep Networks in the Kernel Regime
Authors: Benjamin Bowman
Guido Montufar
Venue: NeurIPS 2022 Accept (2022)
Keywords: Spectral Bias
Neural Tangent Kernel
Implicit Bias

Abstract: We provide quantitative bounds measuring the $L^2$ difference in function space between the trajectory of a finite-width network trained on finitely many samples from the idealized kernel dynamics of infinite width and infinite data.  An implication of the bounds is that the network is biased to learn the top eigenfunctions of the Neural Tangent Kernel not just on the training set but over the entire input space.  This bias depends on the model architecture and input distribution alone and thus does not depend on the target function which does not need to be in the RKHS of the kernel.  The result is valid for deep architectures with fully connected, convolutional, and residual layers.  Furthermore the width does not need to grow polynomially with the number of samples in order to obtain high probability bounds up to a stopping time.  The proof exploits the low-effective-rank property of the Fisher Information Matrix at initialization, which implies a low effective dimension of the model (far smaller than the number of parameters).  We conclude that local capacity control from the low effective rank of the Fisher Information Matrix is still underexplored theoretically.

Spectral Bias Outside the Training Set for Deep Networks in the Kernel Regime
Benjamin Bowman UCLA Department of Mathematics benbowman3140mathh ucla. edu
Guido Montúfar
UCLA Departments of Mathematics and Statistics and MPI MIS contufar@math scluuclleee.. edu
Abstract
We provide quantitative bounds measuring the 1.2 difference in function space be- tween the trajectory of finite-width network trained on finitely many samples from the idcalized kernel dynamics of infinite width and infinite data. An implication of the bounds is that the network is biased to learn the top eigenfunctions of the Neural Tangent Kernel not just on the training set but over the entire input space. This bias depends on the model architecture and input distribution alone and thus does not depend the target function which does not need to be in the RKHS of the kernel. The result is valid for deep architectures with fully connected, convolutional, and residual layers. Furthermore the width does not need grow polynomially with the number of samples in order to obtain high probability bounds up to a stopping time. The proof exploits the low-effective-ranl property of the Fisher Information Matrix at initialization, which implies a low effective dimension the model (far smaller than the number of parameters). We conclude that local capacity control from the low effective rank of the Fisher Information Matrix is still underexplored theoretically.
Introduction
Training heavily overparameterized networks via gradient based optimization has become standard operating procedure deep learning. Overparameterized networks are able to interpolate arbitrary labels both in principle and in practice (Zhang et al. 2017). rendering classical PAC learning theory insufficient to explain the generalization of networks within this modality. The high capacity of modern networks ensures that there are both good and bad empirical risk minimizers. Miraculously the network preferentially chooses the good solutions and sidesteps those that are unfavorable, posing challenge and opportunity today's 's researchers.
The success of overparameterized networks has prompted the theoretical community to search for more subtle forms of capacity control (Neyshabur et al. 2015 2017 Gunasekar et al. 2017). The contemporary point-of-view is that the data distribution, model parameterization, and optimization algorithm are all relevant in limiting complexity. This has led variety of efforts characterize the properties that networks and related models are biased towards when optimized via gradient descent. Examples include max-mnrgin bias for classification problems (Soudry et al., 2018 Ji & Telgarsky 2019 Nacson et al. 2019 Gunasekar et al. 2018), minimum nuclear norm bias for matrix Gunasekar et al. 2018), and minimum RKHS
factorization (Gunasekar al. 2017
2018
norm bias in the kernel regime (7hang et al. 2020
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

Empirically it is known that neural networks tend to learn low Fourier frequencies first and add higher frequencies only later in training (Rahaman et al. 2019 Xu al. 2019; Yang et al. 2022). the phenomenon that has been titled "Spectral Bias" or the "Frequency Principle". Theoretical justifications of this have been proposed by studying networks in the kernel regime. For shallow univariate ReLU networks [asri et al. (019 2020) demonstrate that the dominant eigenfunctions of the Neural Tangent Kernel (NTK) (Jacot et al. 2018) correspond to the low Fourier frequencies for the uniform distribution and more generally to smoother components for nonuniform distributions.
This echos the results by Williams et al. (2019) andJin & Montúfar (20TT) that show that univariate ReLU networks in the kernel regime are biased towards smooth interpolants. Abstracting away from Fourier frequencies, "Spectral Bias" can be interpreted more broadly to mean bias towards learning the top cigenfunctions of the Neural Tangent Kernel. By looking empirical approximations to the eigenfunctions, spectral bias was demonstrated to hold on the training set by Arroa et al. (2019a), Basri al. 2220)) and Cao al. (222T) A recent work by Bowman & Montúfar (2022) was able to demonstrate that spectral bias holds off the training set for shallow feedforward networks when the network is underparameterized. In the present work exploit the low-effective-rank property of the Fisher Information Matrix and are able to demonstrate that spectral bias holds outside the training set without the underparameterization requirement. In fact the number of samples can be on the same order as the width of the network. Furthermore, by leveraging a recent work by Liu et al. (2020)) bounding the Hessian of wide networks, our result permits deep networks with fully connected, convolutional, and residual layers. Consequently we are able to conclude that spectral bias holds for more realistic sample complexities and diverse architectures.
1.1 Our Contributions
We provide quantitative bounds measuring the L difference in function space between the trajectory of finite-width network trained on finitely many samples from the idealized kernel dynamics of infinite width and infinite data (see Theorem 3.5 and Corollary 3.7
As implication of these bounds, eigenfunctions of the NTK integral operator (not just their empirical approximations) are learned at rates corresponding to their eigenvalues (see Corollary 3.7
and Observation 3.8
We demonstrate that the network will inherit the bias of the kernel at the beginning of training even when the width only grows linearly with the number of samples (see Observation 3.9.
1.2 Related Work
NTK Convergence Results The NTK was introduced by Jacot et al. (018)) while almost concur- rently Du et al. (2199)) used it implicitly to prove a global convergence guarantee for gradient descent applied to shallow ReLU network. These two highly charismatic works led to a flurry of subsequent works, of which we can only hope to provide a partial list. Global convergence for arbitrary labels was addressed in a series of works (Du et al.. 2019b a Oymak & Soltanolkotabi 2020; Allle-Zhu let al., 2019; Nguyen& & Mondelli] 2020 Nguyen 2021, Zou al.] 2020) Zou & Gu 2019). For
arbitrary labels to our knowledge all works require the network width to either grow polynomially with the number of samples n or the inverse desired accuracy e-1, If one assumes the target function aligns with the NTK model, for shallow networks this can be reduced to polylogarithmic width for
the logistic loss g & Telgarsky 2020) or linear width for the squared loss (E al. 2020 Su Yang
2019 Bowman & Montufar 2022).
Spectrum of the NTK/Hessian and Generalization The fact that the NTK tends have a small number of large outlier eigenvalues has been observed in many works (e.g. Arora et al. 2019a Oymak al. 2020 Li et al. 2020). Papyan (020) demonstrated that for classification problems the logit gradients cluster within classes, which produces outliers in the spectra of the NTK and the Hessian of the loss. There have been series of works analyzing the NTK/Hessian spectrum theoretically
using random matrix theory and other tools (e.g. Karakida et al. 2021 Pennington & Worah 2018 Pennington & Bahri Bahrii201]] Fan & Wang 2020 Yang Salman Salman|2019. Recently the spectrum of the
NTK integral operator for ReLU networks has been shown to asymptotically follow a power law (Velikanov & Yarotsky 202T Arora et al. 2019a) provided gemeralization bound that effective when the labels align with the top eigenvectors of the NTK. Oymak et al. (2020) were able to use the low effective rank of the NTK to obtain generalization bounds, and Li et al. (2020) used the same
property to demonstrate robustness to label noise. The low effective rank of the Hessian has also been
2

---

incorporated into PAC-Bayee bounds, most recently by Yang et al. (20TT). Interestingly, the notion of the effective dimension they define is essentially the same quantity we use to bound the model complexity of the network's s linearization.
NTK Eigenvector and Eigenfunction Convergence Rates Luo et al. (2020) explicitly tracked the dynamics of the infinite width shallow model in the Fourier domain. |Aroa et al. (2019)) demonstrated that when training the hidden layer of shallow ReLU network, the residual error on the training set projected along eigenvectors of the NTK Gram matrix decays linearly at rates corresponding the eigenvalues. CCo al. (202T) proved similar statement for training both layers, and Basri et al. 2020) proved the analogous statement for a deep fully connected Rel.U LU network where the first and last layer are fixed. Our result can viewed as the corresponding statement for the test residual instead of the empirical residual: projections of the test residual along eigenfunctions of the NTK integral operator are learned at rates corresponding to their eigenvalues. This was shown in recent work (Bowman & Montúfar, 2022) for shallow fully connected networks that are underparameterized. By contrast our result does not require the network to be underparameterized. and holds for deep networks with fully connected, convolutional, and residual layers. We view our fundamental contribution as demonstrating that spectral bias holds with more realistic sample complexities and in considerable generality with respect to model architecture
2 Preliminaries
2.1
Notation
Vectors E R* will be column vectors by default. We will let (e, and ||0||a denote the Euclidean inner product and norm. We define
1 2 and || [ellg- := v( R to be the normalized Euclidean inner product and norm. The notation ((, == {w =|] 01l2 S r will denote the closed Euclidean ball centered at e of radius r. ||All == supp[ol-_- ||Al||2 will denote the operator norm for matrices. For a symmetric matrix A E I (x denotes its i-th largest eigenvalue, i.e. (A) 2 (A( 2 2 (A). For set A we will let |A] denote its cardinality. For natural number k 2 1, we will let [k] == X with measure v. We will denote the inner product associated with L²(X,"), v) (,.)).. We will use the standard big O and l notation with Ô and Q hiding logarithmic terms.
R
We will let LP(X, v) denote the 12 space over domain
2.2 NTK Dynamics
Let f(x; 8) be our scalar scalar-valued neural network model taking inputs x E X C Rd parameterized by 0 E IR". For we will not specify specific architecture. Our training data will be input-label yn)} C Rd x R where we assume that the labels y; are generated from a pairs {(11, y1 ...,. (I
fixed scalar-valued target function f", namely (=xx yt- We will let y E R denote the label vector y = (y1,.... yyx) Let f(0) E TR. denote the vector that measures the residual error on the
training set, whose i-th entry is f()): f(z;;) y/- We will optimize the squared loss
1
(0)
2n 11((0)12 ||((
via gradient flow
0,8, 0
which is the continuous time analog of gradient descent. For conciseness we will denote r(0:) by A and let (x) fxx 02) ff denote the residual for arbitrary input x not necessarily in the
training set. We may also write r(x; 0) = fz; 0) - (z) for the residual for an arbitrary 6.
We recall some key definitions and facts about the NTK. For comprehensive introduction we refer the reader to Jacot et al. (218)). We recall the definition the analytical NTK
K (x, = Eeg-u [[Vo (x; 0o), oaf 0o))]
where the expectation is taken over the parameter initialization Op μ. The kernel K00 induces an integral operator Tx= T.2(X,p) - 1,2 (.²,))))
TK= = / K
(1)
3

---

where X is our input space and is the input distribution. We assume our training inputs Fi..... Zn are i.idd samples from p. More generally, for a continuous kernel K (x,x²) we define
Tx: (2(X, > (2)
Tkg(z) := =/xx K(x, ()gs)))(
(2)
Returning back to k by Mercer's theorem we have the decomposition
K Kx, (2, (0, = Σ (1)((r))
where { is orthonormal basis for (X, and { } is nonincreasing sequence of positive values. will see that the bias at the beginning of training within our framework can be described entirely through the operator Tk> and its eigenfunctions. We note that Tx> depends only on the model architecture, parameter initialization distribution μ4, and input distribution p. The training data sample 21...... Zn introduces discretization of the operator Tk>
Tng(2) = - Σ n
K (x, (x) = / (x, ()g(s))(())))
(3)
where " 1 Ei= 82, is the empirical measure. We now introduce the time-dependent NTK (x,x,²') (Vof(x; 0s), Vof(x';0.)
with the associated dime-dependent operator T
1 n2 Σ K.(x, = / (,(zx))g(s)dd
(xx
(4)
The update rule for the residual re under gradient flow is given by
(-r(()==- = Σ (r) = -
Speaking loosely, as the network width tends to infinity the time-dependent NTK K, (I,xx') becomes constant that xx), = (x, x') uniformly in L. If K. K then have the operator equality Te = Tn. Similarly. heuristically as n - oo we have Tn + Tg=. Thus in the idealized infinite width, infinite data limit the update rule becomes
dr = -Tx-rr.
which has the solution r, exp(-Tx<x 1)ro which is defined via its projections
(1) exp(-o;t)(ro) (r)
Thus in this idcalized setting the network learns eigenfunctions eigenvalues og. The dependence of the convergence rate on the magnitude of a; is particularly relevant as the NTK tends to have very skewed spectrum. We estimate the spectrum of K by randomly initializing a network and computing the Gram matrix (Go)i.j := (Z, zy). In Figure we plot the spectrum of the NTK Gram Matrix (Go) == Ko(xi, 2rj) at initialization. We observe a small number of outlier eigenvalues of large magnitude followed by long tail of small eigenvalues. This phenomenon has appeared in many works (e.g. Arora al. 20T9a; Oymak al. 2020 Li et al. 2020). For ReLU networks the spectrum is known to asymptotically follow a power law 0; Ai (Velikanov & Yarotsky/ 2021). The goal of this work to quantify the extent to which a finite-width network trained on finitely many samples behaves like the idcalized kernel dynamics Ft exp(-Tk=ttrr corresponding infinite width and infinite data.
rates determined by their
2.3 Applicable Architectures
We now specify an architecture for our model [(x;; 0). We consider deep networks of the form
a (0) = 9 (0(1) a ((-1),,
I [T),
f(z;0) = T (L)

---

Spectrum of LeNet-5 NTK on MNIST
Spectrum of shallow NTK on CIFARIO
Normalized magnitude
Normalized magnitull
16-7
100
3000
Index eigenvalue
Index of eigenvalue
Figure I: We plot the NTK spectrum on MNIST and CIFARIO for two networks using 10 random parameter initializations and data batches. In both plots the x-axis represents the eigenvalue index (linear scale) and the y-axis the normalized eigenvalue / '1 magnitude (log scale). To avoid numerical issues, we compute the NTK on batch of size 2000 and plot the first 1000 eigenvalues. The left plot computed the NTK corresponding to the logit of class 0 for LeNet-5 on MNIST. The right plot is for shallow fully-connected sofiplus network with 4000 hidden units on CIFARIO.
where each (1()))))))) .) R + RT is vector-valued function parameterized by 1 E Rp and E _ We define ((L+1) and set 0 := ((O(1)TT ..... (0(++1)77) to be the collection of all parameters. We assume each layer mapping t/t has one the following forms:
Fully Connected ( aa=11))
wwau-11)
m
Convolutional (0 (((00)aa0111))) (1)-)))-
W(l)) * *all-1))
1
Residual ar(00))a""1))
W (( + (111)
Here g(4) = vee(we())))))) and w is a twice continuously differentiable function such that w and w' are Lipschitz. All parameters of the network will be trained as in practice. For feedforward and residual of convolutional layers W R Xxxmxxm- layers (!)) E R.mxx xm-- is matrix. For the definition of the convolution * is offered in the an order-3 tensor with filter size K. The precise appendix. We will let m min my denote the minimum width of the network. We will assume that maxi ma = O1). The input dimension d == mo, the depth L, and the filter sizes K of convolutional layers will be treated constant. The depth L being constant is essential for NTK convergence; see Hanin & Nica (2020) for an explanation of failure modes whenever depth is nonconstant.
We will now discuss initialization scheme. We will perform the antisymmetre initialization trick introduced by Zhang et al. (2200) so that the model is identically zero at initialization f(o; 0b) 0. Let (x;; 0) be any neural network of the form described above. Then let = [0 where 0, 0" E R.. We then define
1 V2 ((; J2 ((
1
fAST(I;0) =
which takes the difference of two rescaled copies of our original model f(z; 0) with parameters and 0' that are optimized freely. The antisymmetric initialization trick initializes Og N NN, I) then sets 0n = [ ]- We then optimize the model fAST starting from the initialization 0g This trick simultaneously ensures that the model is identically zero at initialization without changing the NTK initialization /Zhng et al. 2020). For ease of notation we will simply assume from now on that f(z 0) fAst (x; 8) and not write the subscript ASI.
5

---

3
Main Results
Before stating our main result, we enumerate our key assumptions for the sake of clarity, assumed to hold throughout. Detailed proofs are deferred to the appendix.
Assumption 3.1. The activation w is twice continuously differentiable and w and ut are Lipschitz.
Assumption 3.2. The input domain X is compact with strictly positive Borel measure p.
Assumption 3.3. The target function f satisfies IIf [|=,,x)))))) O(1).
Assumption 3.4. We use the antisymmetric initilization trick so that f( (o) = 0.
Most activation functions except for ReLU satisfy Assumption 3.1 such as Softplus w(x) = In(1
e"), Sigmoid w(x) I+e-2. and Tanh w(x) g- -e 2" Assumption 3.2 a sufficient condition for Mercer's Theorem to hold. While Mercer's theorem often assumed to hold implicitly, we prefer to make this assumption explicit. Assumption 3.3 simply means the target function is bounded. We believe the antisymmetric initialization specified in Assumption 3.4 is not strietly necessary but
greatly simplifies the proof's and associated bounds. To sidestep 3,4 one would utilize high probability bounds on the magnitude [x; 0o) at initialization.
the following results f(x; 0) will be any of 2.3 We are now ready to introduce the main result.
the architectures discussed in Section
Theorem 3.5. Let T > 1,E O. Let K(x, x') be fixed continuous, symmettrcc, positive definite kernel. For k E N let Ps pX, + (2, p) denote the orthogonal projection onto the span of the top k eigenfunntions of the operator Tk defined in Equation 2 Let 0 > 0 denote the k-th eigenvalue of T-- Then m = /(2 and n = CTT2 suffices to ensure with probubility at least 1 - ((mn) exme))xp((-e exp(=S2(log" (m)) over the parameter initilization Og and the training samples 3T, .......,2....................... Zn that for all S T and k E
1 exp(=ontt)
-xp( - -xpp-o-oo)))
I
[4 IK Kolli2(x2, +
Ok
and
1 -x-oxp(-Txeroolixxx. S [11 II (x) +
3.1 Interpretation and Consequences
Theorem 3.5 compares the dynamics of the residual r2(x)) f(z; fz) (z) of our finite- width model trained on finitely many samples the idealized dynamics of a kernel method exp(-Tx-tro with infinite data. We recall that if o; is an eigenfunction of TK with eigenvalue o; then (exp(-Txxt)mp Φx)p = exp(-a,t) Φz)p- Thus the term exp(-Tx((ro learns the projection along eigenfunction Φ; linearly at rate Whenever the NTK at initialization Ko concentrates around K, the residual r, will inherit this bias of the kernel dynamics exp(-Txt)ro- Furthermore, the bound for the projected difference [| - -eap--Txt)mp I2 ( is smaller whenever σμ is large. Therefore the bias appears more pronounced along eigendirections with large eigenvalues.
(x.,)
Consequences for the special case K K In the infinite width limit, have that K₂ ap- proaches 8 for general architectures Yang 2020 For fixed x, x', by concentration results the typical rate of convergence is Kn(x, x²) K (r. x') = Õ(1/ /m) with high probability (Du et al. 2019h a Huang & Yau 2020)_ Bounds that hold uniformly over 2;, x' of the same rate provided
by Bowman & Montúfar (2022) and Buchanan et al. (2021). A more pessimistic estimate of 1/m
Ωle -2) is strong enough to ensure that [x x²) (x, < cl/2, Given these results, it is reasonable make the following assumption for the architectures we consider (see Appendix
is provided by Arora et al. (2019)). Even if the rate is 1/m we have that
B
Assumption 3.6. (2(==) suffices to ensure that Ko K000 [ S holds with high
probability 1 5mm) over the initialization Og where 5(m) o(1)
Under this assumption, by setting K = K in Theorem 3.5 we get the following corollary. Corollary 3.7. Let 6(m) be defined as Assumption <> O. For lo E N let Pk (X2 p) L (X, p) denote the orthogonal projection onto the span of
3.6 which we assume to hold. Let 2 and

---

the top k eigenfunctions of the operator Tk> defined in Equation ① Let σk > 0 denote the k-th eigenvalue T<. Then m = and n = S1(T2 /e²) suffices to ensure with probability at least 1 - mmm) exp(-S2(log - 5(m) that for all - T and k E N
1 exp(
[Pr(r - (xtr---exx--xx=xo)lllll -
Ok
and
|r - -x-p(pTTxtt)ollll
S S
Informally Corollary 3.7 states that up to the stopping time T, we have that Tr & exp(-Tk< f)yoo As projected along the i-th eigenfunction of K decays lin- early, (exp(-T<< rr, 2x)p - (osp(-o,)(roo.... 6z) Given that 0 tends to have a highly skewed spectrum (see, e.g. Figure I. the effect the magnitude of a has on the convergence rate is particularly relevant. Furthermore the bound on the projected difference [r exp(-Tke ())p- ( is
discussed before, the term exp(-Tx=<))
smaller whenever σ% is large due the dependence of the bound on the inverse eigenvalue o Thus we have that the bias along the top eigenfunctions is particularly pronounced. Hence we make the following important observation.
Observation 3.8. At the beginning of training the network learns projections along eigenfunctions of the Nearal Tangent Kernel integral operator TK> at rates corresponding to their eigenvalues. This is particularly true for the eigenfunctions with large eigenvalues.
Scaling with respect width and number of training data samples Now let us interpret how the width and number of training samples in the theorem scale. We note that long S. m for some a > O the failure probability ((m)) exp( (m))) goes to zero m + co. Thus once m and n are sufficiently large relative to the stopping time T and precision e, they can both tend to infinity at just about any rate to achieve high probability bound. We also observe that m and both have the same scaling with respect to c, namely m, 5)(c-). Thus for fixed stopping time we can send m and n to infinity at the same rate m ~ n to send the error c c O. This significant as typical NTK analysis requires = ((poly(T)). We reach following important conclusion.
Observation 3.9. The network will inherit the bias of the kernel at the beginning of training even when the width m only grows linearly with the number of samples
Scaling with respect to stopping time time T. The relevant question is how quickly the terms Pa exp(-7T0 -T t)ro and exp( Sop(-Tx<> trro converge to zero. We observe that
We will now address the scaling with respect to the stopping
|| exp( -K T)=llrrll I exp(-oxt ( [[oll I exp(-oxkh |1f || (x(p)))
where we have used the antisymmetric initialization ro = f(; f"r basic inequality ||0 (.(,,)) I ||=1==(x,,)) Based on this we have that t 2 log(I) (11[1=l'l12xxxp) /c)/ox suffices ensure ||&
f 0 f and the
S Using this fact we get the following corollary.
Corollary 3.10. Let 5(m) be defined as in Assumption 3.6 which assumed to hold. Let = ((1/Ow) and e > O. For k E N let PN L²(XX p) - [2(X,, p) denote the orthogonal projection onto the span of the top k eigenfanctions of the operator Tw= defined in Equation O Let o
denote the k-th eigenvalue of Tx Then 21( -3 3/22) and 00000//// suffices to ensure that with probability at least (mm) 2(log" (m)) 5(m)
||PeTTlli2(x000 SE
and in particular
/ S Ō + +1[[ -
The interpretation of the Corollary 3.10 is that the stopping time T {((10x)) is long enough to ensure that the network has learned the top & eigenfunctions to accuracy provided that m = 0( 2 and n = 20 We note that the second conclusion of Corollary 3.10 is a bound the test error || | From the antisymmetric initialization ro =- so that
7

---

For general target f*, this quantity can decay arbitrary slowly with respect to k. Our goal with Theorem 3.5 was not to get a learning guarantee, but to describe how the bias of the kernel Ko is inherited by the finite-width network at the beginning of training even for general target functions, Nevertheless we will briefly sketch how it is possible to get a learning guarantee from Corollary 3.7 when f is in the RKHS of K In this case one can O
III Pr)rolli - -IUI-P))
the RKHS norm. Then treating I|x constant one can choose the stopping time e~' to bring the test error to provided that m, n = D(poly(e ))). More generally Velikanov & Yarotsky 2021 derive sufficient conditions Ct to hold. Using a similar argument in this case one can choose the stopping time T ~ e -1/E and get a learning guarantee for m, n = St(poly(e 1)).
show that [|exp(-Tk>> ()rol
- where || 11
for the power law llexp(-T<<> t)rroll
3.2 Technical Comparison to Prior Work
Lee et al.
2019) ; Arora et al. 2019b) compared the network (z; 0) to its linearization (I; 0)
(Vof(z; bo). 80) + f(;; 6b) in the regime where m (pplly(n)) nn). When m (pollyl (n)) one can show the loss converges to zero and the parameter changes 1|0 Boll, are bounded. By contrast
we avoid the condition m = (p))ly(n)) by employing a stopping time. Arora et al. (00 1a Cao
et al.
(2021): Basri et al. (2020) proved statements similar to Theorem 3.5 and Corollary 3.7 that
roughly correspond to replacing TR= with its Gram matrix induced by the training data (G
K x.,) and replacing p with the empirical measure ý = - 8z.- Arora al. (019a Basri
et al. (2000) operate in the regime where m = R(poly (n)) and as benefi do not need to employ
a stopping time. Cao et al. (02T)) instead of requiring m = (ppoly(n)) requires that the width
m satisfies least m (0mma {or -14 cc=)) where de is the cutoff eigenvalue. The most similar work is Bowmaan & Montutar (2022), which demonstrated a version of Corollary 3.7 a shallow feedforward network that is underparameterized. If is the total number of parameters, they require m 6i (T2) and n (T9). This requires the network to be greatly underparamettrizee >> p. Our result was able to remove the dependence of n on p and demonstrate the result for general deep architectures at the expense of slightly worse scaling with respect to T and c.
Proof Sketch
For simplicity we will go through the case where K = =0 At a high level the proof revolves around bounding the difference between the operators Tg and T defined in Equations 4 and
Bounding Operator Deviations
Bowman & Montúfar 2022) demonstrated
rt -Txt-T + L' Tk=(t <TK - rds.s
This exhibits the residual rt as a sum of exp(='T==>> t and a correction term. The proof of Theorem 3.5 revolves around bounding the correction term which involves bounding
[[TK>> T))rxllaa(xx,)) I [[[TK> T,)r, [=(x)))) [[ TT)rxlll=(x.,0)>
At high level [[ T2)r T=)rxlll will be small whenever the kernel deviations Ko K2 are small. On the other hand by metric entropy based arguments we have that [[[T== (r))xll will be small whenever n is large enough relative to the complexity of the residual functions T.-
Comparison with Linearization Let H(;; f) == fx;(x; 8) denote the Hessian of our network with respect to the parameters for fixed input æ. It turns out that if [2, l) was uniformly small over x and 0 then the kernel deviations Ku- K₂ would be bounded and the complexity of our model f(; 0) would be controlled by the complexity of the linearized model fiän (z; 8) := do not in fact have way to bound the (x; 0g),6 0 0o). The caveat to this approach demonstrated that for fixed x and R > 0 we Hessian H(x, 0) uniformly. However Liu et al. (0205)
have with high probability over the initialization 0o
R po P/
[((l,0)llo = Ô B (e,
sup
(5)
8

---

Using a priori parameter norm deviation bounds we have that 9P0-81l12 - O(vi) and thus we can set R = O(VT). The difficulty then arises to get bounds that only depend the Hessian (2; 8) evaluated only on finitely many inputs z. We overcome this difficulty by showing for fixed 8o has high probability bounds over the sampling of the training data 1 ........ Fy, that only require the Hessian evaluated on a finite point set. This requires some elaborate calculations involving Rademacher complexity. We then the Fubini-Tonelli theorem and the Hessian bound (
to get
bound over the simultaneous sampling of Og and T1,...,,
Covering Number of the Linearized Model The complexity of the residual functions T. up the stopping time T can be controlled by bounding the complexity of the function class C C {fiin (z; A E Bi R.}. In Appendix A we show that the (2 p) metric entropy of the linearized model [fin 0) : 0 E B(Oo, R is determined by the spectrum of the Fisher Information Matrix
F = Jx Vos(a; Vof dp)())
(6)
Let x1/2 2 X2 2 ... 2 0 denote the eigenvalues of F1/2, We define the effective rank of F1/2 at scale as
8(F = Hi: X >]]
This measures the number of dimensions within the unit ball whose image under F1/2 can be larger than in Euclidean norm. In Appendix A we demonstrate that the covering number of C in I,2 (X.P)) denoted (C,, Lx(X)))) c), has the bound
log. NCC || || (A((,0) .) (0.77
It turns out that for [[(T=> - -Trrssll (((,0)) to be on the order of E we merely need n to be large relative to ((F1/2 0.75e/ Rt). By contrast Bowman & Montúfar 2022) required that the network was underparameterizzd so that was large relative to the total number of parameters p. Since < p. this is what lets us relax the sample complexity dramatically. fact for fixed and we have that p = Ó(1 with high probability as the width grows to infinity whereas p + 0o. Interestingly, the quantity p for the loss Hessian at convergence was used recently derive analytical PAC-Bayes bounds (Yang et al. 2021). Note for the squared loss the (empirical) FIM can be taken as an approximation to the Hessian, and at minimizer this approximation becomes exact. Thus these two notions are closely related.
Conclusion and Future Directions
We provided quantitative bounds measuring the I difference in function space between finite-width network trained on finitely many samples and the corresponding kernel method with infinite width and infinite data. As consequence, the network will inherit the bias of the kernel at the beginning of training even when the width scales linearly with the number samples. This bias not only over the training data but over the entire input space. The key property that allows this is the low-effcctivv-rant property of the Fisher Information Matrix (FIM) at initialization which controls the capacity of the model at the beginning of training. An interesting avenue for future work is to investigate if flat minima manifesting a FIM of low effective rank at the end of training can be related to the behavior of the network oft-of-sample data after training.
Limitations
Our framework can only characterize the network's bias up to a stopping time. There is compelling evidence that the kernel adapts to the target function later in training (Baratin et al.) 2021 Atanasov et al. 2022), and this falls outside our framework. Accounting for adaptations in the kernel is important problem that is still being addressed by the theoretical community.
Broader impacts We do not foresee any negative societal impacts of characterizing the spectral bias of neural networks. To the contrary we believe that cataloging the properties that networks are biased towards variety of regimes will be essential to developing fair and interpretable artificial intelligence over the long-term.
Note that we define F' as an expectation over the true input distribution To approximate the Hessian of the empirical loss must replace p with the empirical measure

---

Acknowledgments and Disclosure of Funding
This project has received funding from UCLA FCDA, the National Science Foundation Division of Mathematical Sciences (NSF DMS-2145630), and from the European Research Council (ERC) under the European Union's s Horizon 2020 research and innovation programme (grant agreement n" 757983). The authors would like to thank Yonatan Dukler for sharing code to compute the NTK Gram matrix in PyTorch.
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 the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pp. 242-252 PMLR, 09-15 Jun 2019. URL https://prroeeedings mlr. mlr.press/ 207/allen-2huie html
Sanjeev Arora, Simon Du, Wei Hu, Zhiyuan Li, and Ruosong Wang. Fine-grained analysis of optimization and generalization for overparameterized two-layer neural networks. Kamalika Chaudhuri and Ruslan Salakhutdinov (eds.), Proceedings the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pp. 322-332. PMLR, 09-15 Jun 2019a. URL https:://///oo
mlr ppress/v97/ /wt./////rra1......m html
Sanjeev Arora, Simon S Du, Wei Hu. Zhiyuan Li, Russ R Salakhutdinov, and Ruosong Wang. On exact computation with an infinitely wide neural net. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Buc, Fox, and R. Garnett (eds.), Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019b. URL https: httpp::::pppppeeddiiiie htw.:/abbbbbbbbffbaaba333e 2019/ftle/dbc4444fffctt 4a0oo440000000222222oo0o11111a14
nwur cc/paper/ påf
Alexander Atanasov, Blake Bordelon, and Cengiz Pehlevan. Neural networks as kerell learners: The silent alignment effect. In International Conference on Learning Representations, 2022, URL
Aristide Baratin, Thomas George, César Laurent, R Devon Hjelm, Guillaume Lajoie, Pascal Vincent, and Simon Lacoste-Julien. Implicit regularization via neural feature alignment. In Arindam Banerjee and Kenji Fukumizu (eds.). Proceedings of The 24th International Conference on Artificial Intelligence and Statistics, volume 130 of Proceedings of Machine Learning Research, pp. 2269 2277. PMLR, 13-15 Apr 2021. html
URL httph:tt///pptt htttss://proceeddnggg mlr htt.a//imn.....ppeeeerr//////aaa pttppre//11//baraainn22.
Peter L. Bartlett and Shahar Mendelson. Rademacher and Gaussian complexities: Risk bounds and structural results. J. Much. Learn. Res., 3(nul1):463-488, mar 2003. ISSN 1532-4435.
Ronen Basri, David Jacobs, Yoni Kasten, and Shira Kritchman. The convergence rate of neural net- works for learned functions of different frequencies. H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Bus E. Fox, and R. Garnett (eds.), Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc.. 2019. URL https::/proceeddii hewproeeeedinngnn.uiir.......... nwwrips.riiccom cccpppprrrcpppp pdf
Ronen Basri, Meirav Galun, Amnon Geifman, David Jacobs, Yoni Kasten, and Shira Kritchman. Frequency bias in neural networks for input of non-uniform density. In 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 httpss//prooceedingg.. mlr wttp:es//11///ariiii//..// html
Benjamin Bowman and Guido Montúfar, Implicit bias of MSE gradient optimization underparam- eterized neural networks. In International Conference on Learning Representations, 2022. URL
htttps://oeenrevier
Sam Buchanan, Dar Gilboa, and John Wright. Deep networks and the multiple manifold problem. In International Conference on Learning Representations, 2021. URL. htttps://openreview.rr
forum?ide ienmnidd=--ee d00-6pm000--06m Q_
10

---

Yuan Cao, Zhiying Fang, Yue Wu, Ding- Xuan Zhou, and Quanquan Gu. Towards understanding the spectral bias of deep learning. In Hua Zhou (ed.). Proceedings of the Thirtieth Interna- tional Joint Conference on Artificial Intelligence, ISCA1-21, pp. 2205-2211, International Joint
Conferences on Artificial Intelligence Organization, 2021. doi: 10.24966/ijeai.221/553 URL. Main Track.
htttps://di.... org/ 10. 24963/ 11963/ijcar ijcai. 2021/304
Simon Du, Jason Lee, Haochuan Li, Liwei Wang, and Xiyu Zhai. Gradient descent finds global minima of deep neural networks. Kamalika Chaudhuri and Ruslan Salakhutdinov (eds.), Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pp. 1675-1685, PMLR, 09-15 Jun 2019a. URL https://
proceedings mlr wwwpppssss.....mm http///vv/dd/..... dw19c.111ccc html
Simon S. Du, Xiyu Zhai, Barnabas Poczos, and Aarti Singh. Gradient descent provably optimizes pecepaarmmeter neural networks. In Internatioona Conference on Learning Representations, 2019b. URL
Iyya Dumer. Covering an ellipsoid with equal balls. J. Comb. Theory Ser. A, 1130)):66666611 nov 2006. ISSN 0097-3165. doi: 10. 10.101661.etta,200..0..33 URL ctt. 2006 03.03.3... 021
Weinan E, Chao Ma, and Lei Wu. A comparative analysis of optimization and generalization properties of two-layer neural network and random feature models under gradient descent dynamics. Science China Mathematics, 63: 13:1223-1258, 2020.
Zhou Fan and Zhichao Wang. Spectra of the conjugate kernel and neural tangent kernel for linear- width neural networks. In Proceedings of the 34th International Conference on Neural Informa- tion Processing Systems, NIPS' 20, Red Hook, NY, USA, 2020. Curran Associates Inc. ISBN 9781713829546.
Y. Gordon, Hermann König, and Carsten Schütt. Geometric and probabilistic estimates for entropy and approximation numbers of operators. Journal of Approximation Theory, 49:219-2331 1987.
Suriya Gunasekar, Blake E. Woodworth, Srinadh Bhojanapalli, Behnam Neyshabur, and Nati Srebro. Implicit regularization in matrix factorization. In I. Guyon, U. V. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett (eds.), Advances Neural Information Processing Systems, volume 30. Curran Associates, Inc., 2017. URL http:tps://pproeeeeee http:///oooceeeng.eeeeeeee paper/2011/filee55e 111112200466a6666661111cccc11111
cc/
.ddf
Suriya Gunasekar, Jason Lee, Daniel Soudry, and Nati Srebro. Implicit bias of gradient descent on linear convolutional networks. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa- Bianchi, and R. Garnett (cds.), Advances in Neural Information Processing Systems, volume 31. Curran Associates, Inc., 2018. URL /ttp/attss://rrrceeiiiii http://ppoeeeen...//// nwwrins..i.... http://nnn.opp.....coo/a////2220 pctpapper/01///iieeee..
Boris Hanin and Mihai Nica. Finite depth and width corrections to the neural tangent kernel. In International Conference on Learning Representations, 2020. URL https::/oppenreviet net/
Torum?id=SJJnndTKka
Charles R. Harris, K. Jarrod Millman, Stéfan J. van der Walt, Ralf Gommers, Pauli Virtanen, David Cournapeau, Eric Wieser, Julian Taylor, Sebastian Berg, Nathaniel J. Smith, Robert Kern, Matti Picus, Stephan Hoyer, Marten H. van Kerkwijk, Matthew Brett, Allan Haldane. Jaime Fernández del Río, Mark Wiebe, Pearu Peterson, Pierre Sgrard-Marchant Kevin Sheppard, Tyler Reddy, Warren Weckesser, Hameer Abbasi, Christoph Gohlke, and Travis E. Oliphant. Array programming with NumPy, Nature, (85((885)
September 2020. doi: URL httph: /tttps://dol.c org 100 10. 000888//1186--00000 2649-2
Jaayaang Huang and Homg-TTer Yau. Dynamics of deep neural networks and neural tangent hierarchy. 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. 1542-4557 PMLR, 13-18 Jul 2020. URL
mlr. wll...pres/vvii ppres/vv19/huue htt///1111/ha/11..11/1/ html
D. Hunter. Matplotlib: A 2d graphics environment. Computing in Science Engineering, 9()): 90-95, 2007. doi: 10. N0.1109/MCSE..007.55.

---

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. Cesa- Bianchi, and R. Garnett (eds.), Advances in Neural Information Processing Systems, volume 31. Curran Associates, Inc., 2018 URL htt.stttss:// p/poceeding...sgss..o. negsssneurppp www.rips...pppper/ee/e..ee. pc/ppaper/01///ille.
Paper pdd
Ziwei Ji and Matus Telgarsky. The implicit bias of gradient descent on nonseparable data. In Alina Beygelzimer and Daniel Hsu (eds.), Proceedings of the Phirty-Second Conference on Learning Theory, volume 99 of Proceedings of Machine Learning Research, pp. 1772-1798. PMLR, 25-28 Jun 2019. URL httpbtts//pprrceediig///
mlr httpa//nnn.....eeee///////////1/
html
Ziwei Ji and Matus Telgarsky. Polylogarithmic width suffices for gradient descent to achieve arbitrarily small test error with shallow ReLU networks. In International Conference on Learning Representations, 2020. URL httpl/ttss///peerrreeeeeeeeeeese
Hui Jin and Guido Montúfar. Implicit bias of gradient descent for mean squared error regression with wide neural networks, 2021. 20Xiv:0006007356.
Ryo Karakida, Shotaro Akaho, and Shun-ichi Amari. Pathological Spectra of the Fisher Information Metric and Its Variants in Deep Neural Networks. Neural Computation, 33(8):2274-2300 July 2021. ISSN 0899-7667. doi: 10. 1626/ecoo_os a 2_111111111111111111111111111111 htttsttts::// /ttp://////o..o//////////// 1162/neco__ a 01411
_eprint: https://direct.n mit.
2atpeeeee____1111eeee_e_11 014111.ddf.
Thomas Kluyver, Benjamin Ragan-Kelley, Fernando Pérez, Brian Granger, Matthias Bussonnier, Jonathan Frederic. Kyle Kelley, Jessica Hamrick, Jason Grout, Sylvain Corlay, Paul Ivanov, Damián Avila, Safia Abdalla, and Carol Willing. Jupyter notebooks a publishing format for reproducible computational workflows. In F. Loizides and B. Schmidt (eds.), Positioning and Power in Academic Publishing: Players, Agents and Agendas, pp. 87 90. IOS Press, 2016.
Alex Krizhevsky. Learning multiple layers of features from tiny images. Technical report, 2009.
Y. LeCun, I.. Bottou, Y. Bengio, and P. Haffner. Gradient-based learning applied to document recognition. Proceedings of the IEEE, 86(1 1):2278 2324,, 1998. doi: 10. 10.1109/5.726791.
Jachoon Lee, Lechao Xiao, Samuel Schoenholz, Yasaman Bahri, Roman Novak, Jascha Sohl- Dickstein, and Jeffrey Pennington. Wide neural networks of any depth evolve as linear models under gradient descent. 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. Cur- ran Associates, Inc., 2019. URL https: httttt::////oooooo h/tppss//rroeeedingss neur www.eeess.c.ppppee//a....e wttpcc/pppp///19//11aaaa. pdf
Mingchen Li, Mahdi Soltanolkotabi, and Samet Oymak. Gradient descent with early stopping is provably robust to label noise for overparameterized neural networks. In Silvia Chiappa and Roberto Calandra (eds.), Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics, volume 108 of Proceedings of Machine Learning Research, pp. 4313- 4324. PMLR, 26-28 Aug 2020. URL https: https:::pppcceeediiiiieo
mlr peress/v108/122/ html
Yuanzhi Li, Tengyu Ma, and Hongyang Zhang. Algorithmic regularization in paaamerraeteei matrix sensing and neural networks with quadratic activations. In Sébastien Bubeck, Vianney Perchet, and Philippe Rigollet (eds.), Proceedings of the 31st Conference On Learning Theory, volume 75 of Proceedings of Machine Learning Research, pp. 2-47. PMLR, 06-09 Jul 2018. URL
.aagggss............... mlr. wwwpppewss////ppp /7t//i11/a....... html
Chaoyue Liu, Libin Zhu, and Mikhail Belkin, On the linearity of large non-linear models: when and why the tangent kernel is constant. CoRR, abs/2010.01092,, 2020a. URL httph:tt////aaat org/
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. Balcan, and H. Lin (eds.), Advances in Neural Information Processing Systems, volume 33, pp. 15954 15964. Curran Associates, Inc., 2020b. URL htt.:/ttps//prrctiiignneeeriegge
12

---

Tao Luo, Zheng Ma, Zhi-Qin John Xu, and Yaoyu Zhang. On the exact computation of linear frequency principle dynamics and its generalization, 2020. URL https://axxiv.or//aas/. 2010.08153
Mor Shpigel Nacson, J. Lee, Suriya Gunasekar, Nathan Srebro, and Daniel Soudry. Convergence of gradient descent on separable data. In AISTATS, 2019.
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.), 3rd International Conference on Learning Representations, ICLR 2015, San Diego, CA, USA, May 7-9, 2015, Workshop Track Proceedings, 2015. URL http::/tttt.iit.tt//// http://wwwxvvvoraaaaa/// wwt.///g////a/aeeeooe.o 1ttp//412..6..11
Behnam Neyshabur, Ryota Tomioka, Ruslan Salakhutdinov, and Nathan Srebro. Geometry of optimization and implicit regularization in deep learning, 2017. arXiv: AXKY:17705.3071.
Quynh Nguyen. On the proof of global convergence of gradient descent for deep relu networks with linear widths. In Marina Meila and Tong Zhang (eds.), Proceedings of the 38th Inter- national Conference Machine Learning, volume 139 of Proceedings of Machine Learning Research, pp. 8056-8062. PMLR, 18-24 Jul 2021. URL http:: htttps://proceedinggs mlr. press/ v139/nguyen21a. html
Quynh 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. F. Balcan, and H. Lin (eds.), Advances in Neural Information Processing Systems, volume 33, pp- 11961-11972. Curran Associates, Inc., 2020.
.dff pttprr/ppssccppppr////////eeeee.
Samet Oymak and Mahdi Soltanolkotabi. Toward moderate overparameterization Global con- vergence guarantees for training shallow neural networks. IEEE Journal on Selected Areas in Information Theory, 1(1):84 105, 2020.
Samet Oymak, Zalan Fabian, Mingchen Li, and Mahdi Soltanolkotabi. Generalization guarantees for neural networks via harnessing the low-rank structure of the Jacobian, 2020. URL https
Vardan Papyan. Traces of class/cross-class structure pervade deep learning spectra. Journal of Ma- chine Learning Research, 21(252):1-64, 2020. URL http::///hh..rorrpppppprr//////0
html
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Köpf, Edward Yang. Zach De Vito, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala. PyTorch: An Imperative Style, PerforPerfo Deep Learning Library. Curran Associates Inc., Red Hook, NY, USA, 2019.
Jeffrey Pennington and Yasaman Bahri. Geometry of neural network loss surfaces via random matrix theory. In Doina Precup and Yee Whye Teh (eds.), Proceedings of the 34th International Conference Machine Learning, volume 70 of Proceedings of Machine Learning Research, pp. 2798-2806 PMLR, 06-11 Aug 2017.
URL
html
Jeffrey Pennington and Pratik Worah. The spectrum of the fisher information matrix of single- hidden-layer neural network. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa- Bianchi, and R. Garnett (eds.), Advances in Neural Information Processing Systems, volume 31. Curran Associates, Inc., 2018. bttps https/////poooooeeeeeeoeeee neurips wwwweri.....pppeeeeeeeeeeeeeeeee pppppppe//011//111.... Paper. pdf
(B8b88e2638e488ceeccffff
Fernando Pérez and Brian E. Granger. IPython: a system for interactive scientific computing. Computing in Science and Engineering, 933)21122, May 2007. ISSN 1521-9615. doi: 10.1
MC55.2007.53, URL https::/spptthnn. org
Gilles Pisier. The Volume of Convex Bodies and Banach Spuce Geometry. Cambridge Tracts in Mathematics. Cambridge University Press, 1989. doi: 10.1017/CB099785511644444
13

---

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://proceedinggs mlr press/v97. wtt//999///aaaaaaa rahaman 19a. 19a. html
Lorenzo Rosasco, Mikhail Belkin, and Ernesto De Vito. On learning with integral operators. Journal of Machiie Learning Research, 11(30):005-9344 2010. URL http://jmlzz http://rrrrorr//./mme/meeol wwtggpppps/vvil//ppo Tosasco10a html
Daniel Soudry, Elad Hoffer, Mor Shpigel Nacson, Suriya Gunasekar, and Nathan Srebro. The implicit bias of gradient descent separable data. Journal of Machine Learning Research, 19(70):1-57, 2018. URL.ttpp://mmll httpp//rrpppppp/////eeeeee.
html
Lili Su and Pengkun Yang. On learning over-paramettrriedd neural networks: A functional approx- imation perspective. 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. Cur- neur
ran Associates, Inc., 2019. URL
Matus Telgarsky. Deep learning theory lecture notes. 2021. Version: 2021-10-27 v0.0-e7150F22 (alpha).
Maksim Velikanov and Dmitry Yarotsky. Explicit loss asymptotics in the gradient descent training of neural networks. In Marc Aurelio Ranzato, Alina Beygelzimer, Yann N. Dauphin, Percy Liang, and Jennifer Wortman Vaughan (eds.), Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, NeurIPS 2021, December 6-14, 2021, virtual, pp. 2570 2582, 2021. URL http 2021 he2l/hash/110e httaaaa1faaa969222ffff114 cweeefcccfff (tt.:///f001114777777---601-0110 .hml
Roman Vershynin. Introduction to the non-asymptotic analysis of random matrices. In Compressed Sensing, chapter 5. Cambridge University Press, 2012.
Pauli Virtanen, Ralf Gommers, Travis E. Oliphant, Matt Haberland, Tyler Reddy, David Cournapeau, Evgeni Burovski, Pearu Peterson, Warren Weekesser, Jonathan Bright, Stéfan J. van der Walt, Matthew Brett, Joshua Wilson, K. Jarrod Millman, Nikolay Mayorov, Andrew R. J. Nelson, Eric Jones, Robert Kern, Eric Larson, C J Carey, ilhan Polat, Yu Feng, Eric W. Moore, Jake VanderPlas, Denis Laxalde, Josef Perktold, Robert Cimrman, Ian Henriksen, E. A. Quintero, Charles R. Harris, Anne M. Archibald, Antônio H. Ribeiro, Fabian Pedregosa, Paul van Mulbregt, and SciPy 1.0 Contributors. SciPy 1.0: Fundamental Algorithms for Scientific Computing in Python. Nature Methods, -722, 2020. doi: 10. 19938/445522-01--6666-
Martin J. Wainwright. High-Dimenssonal Statistics: A Non-Asymptotic Viewpoint. Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, 2019. doi:
Francis Williams, Matthew Trager, Daniele Panozzo, Claudio Silva, Denis Zorin, and Joan Bruna. Gradient dynamics of shallow univariate relu networks. In H. Wallach, H. Larochelle. A. Beygelz- imer, d'Alché-Bur E. Fox, and Garnett (eds.), Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019. URL htt.https:: http://eeocceennss.//oe www..neurippe mourips.cco
ppf
Zhi-Qin John
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.
Ge Yang, Anurag Ajay, and Pulkit Agrawal. Overcoming the spectral bias of neural value ap- proximation. In International Conference on Learning Representations, 2022. URL hhtpss //openreview. wtwp:rreewiinnnt/ffffeeeee findiiidiiiieeeee XLFMM
Greg Yang. Tensor programs II: Neural tangent kernel for any architecture, 2020. URL. https // /arxivv org/ abs/200s. 14548
14

---

Greg Yang and Hadi Salman. A fine-graing spectral perspective on neural networks, 2019. URL https://arxiv.ort org abs/1907 10599
Rubing Yang, Jialin Mao, and Pratik Chaudhari. Does the data induce capacity control in deep
learning? ArXiv, abs/21 11.22110.11111 14163, 2021.
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 https://openrewieew net/forum? d=
Yaoyu Zhang, Zhi-Qin John Xu, Tao Luo, and Zheng Ma. A type of generalization error induced by initialization in deep neural networks. In Jianfeng Lu and Rachel Ward (eds.), Proceedings 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 URLLhttss:/prrocedding mlr. http//vv00///aag22 html
Difan Zou and Quanquan Gu. An improved analysis of training over-parametterized deep neu- ral networks, H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Buc, Fox, and R. Garnett (eds.), Advances in Neural Information Processing Systems, volume 32. Cur- ran Associates, Inc., 2019. URL httpp::/pproceednngs www..peuriipcooooo cearripp..c/pppeee////////i
fa01d/000a166200001a111111212223 Paper pdf
Difan Zou, Yuan Cao, Dongruo Zhou, and Quanquan Gu. Gradient descent optimizes parameterized deep ReLU networks. Machine learning, 109:467-492, 2020.
15

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] See Section
(c) Did you discuss any potential negative societal impacts of your work? [Yes] See
Section 5
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes] See Section and Section t
(b) Did you include complete proofs of all theoretical results? [Yes] The proofs are included in the supplementary material.
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material as URL)? [Yes] See Appendix
(b) Did you specify all the training details (c.g.. data splits, hyperparameters, how they were chosen)? [Yes]
(c) Did you report error bars (e.g.. with respect the random seed after running experi- ments multiple times)? [Yes] In Figure 1 we plot the curve for each the 10 runs of the experiment.
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [Yes] See Appendix F
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) your work uses existing assets, did you cite the creators? [Yes] See Appendix
(b) Did you mention the license of the assets? [Yes] See Appendix
(c) Did you include any new assets either the supplemental material or as URL? [Yes]
See Appendix F
(d) Did you discuss whether and how consent was obtained from people whose data you't 're using/curating? [Yes] See Appendix F
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [Yes] See Appendix F
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
16


Reviews:
[{"review_id": "qv0_KBrukOr", "reviewer": "Reviewer_9oZz", "summary": "This article theoretically offers quantitative bounds between the trajectory of a finite-width network from the idealized kernel dynamics of infinite one, which implies that networks tend to learn the top eigenfunctions of the NTK at rates corresponding to their eigenvalues. Furthermore, the authors observe that if the width of network grows linearly with the number of samples, it will remain the bias of the kernel at beginning. ", "questions": "1.\tIt seems that this article does not consider the bias term in the neural network. If the bias term is considered, do the corresponding results still hold?\n2.\tMany Relu-like activation functions do not satisfy Assumption 3.1. Can authors discuss more about such activation functions?\n3.\tIf I understand correctly, as t goes to infinity, the RHS of the first inequality converges to a non-zero constant. Does mean this estimation is too loose. And, how can this inequality relates the behavior of the convergence outside the training set?\n4.\tIn “NTK Eigenvector and Eigenfunction Convergence Rates”, a related reference is missed: https://arxiv.org/abs/2010.08153\n", "limitations": "1.\tThe main limitation of this paper is that although the theory is rich, there are too few experiments to tell the reader at a glance what it does. The interpretation of theoretical result is not clear enough, especially, for “outside the training set”.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n1.\tThe paper is rich in theory and offers quantitative bounds between the trajectory of a finite-width network from the idealized kernel dynamics of infinite one, which measure the L2 difference in function space and imply that networks tend to learn the top eigenfunctions over the entire input space. I'm sure the audience of NeurIPS will be interested in it.\n2.\tThe theoretical proof is detailed, the order is reasonable and the structure is clear.\n\nWeaknesses:\n1.\tAlthough the theory of this article is rich, there are very few experiments that could be found in it, which could verify the rationality of the hypothesis and whether the theoretical derivation is true or not. One suggestion is that: It will make the conclusions more convincing if corresponding graphs of experimental results could be attached after important conclusions. Especially, authors can use a 1d experiments to show the estimation in theorem 1 is meaningful.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "k2Ge5weQOYL", "reviewer": "Reviewer_XnSP", "summary": "The paper bounds the distance between the dynamics of wide DNNs and the dynamics of kernel gradient descent on the population with the limiting NTK. This paper improves over previous bounds, by considering the projected error along the top k eigenfunctions of the integral operator $T_{K^\\infty}$ for any $k$.\n\nThey show that the approximation is better along the top eigenvalues. This allows them to show that with early stopping, one can guarantee learning along the top eigenvalues of DNNs. In comparison to previous bounds, the results in this paper only require a width that grows linearly with the number of datapoints, at least with a specific early stopping.", "questions": "I do not have any questions or suggestions regarding the aforementioned weakness (except to try and do the proofs for gradient descent but I realize that it would require a lot of work).", "limitations": "As already mentioned I think the paper would be greatly improved with a discussion of gradient descent.", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The paper is well written and gives a good overview of the previous bounds and how their bound improves on previous ones. The paper nicely connects two lines of research: the NTK regime approximations for finite widths and the spectral bias of DNNs.\n\nThe results are new to my knowledge and describe an interesting phenomenon. I did not check the proofs in detail but I did not see any technical issues.\n\nThe only weakness that concerns me is the fact that the results only apply to gradient flow. The discussion of early stopping is much more interesting in the context of gradient descent since it then relates to computational complexity. There exist many proofs of convergence to NTK-dynamics for gradient descent, so I think the proofs should extend to this setting easily. I do not understand why the authors did not try to extend their proof to gradient descent.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "bKg-FsE7Bc9", "reviewer": "Reviewer_psNV", "summary": "This paper provides a new theoretical analysis of the bounds of function space difference between a finite-width network in a finite sample size regime and the corresponding kernel dynamics in finite width and finite data regime.\nThe results are presented based on fully connected, convolutional and residual neural network architectures.\nBy investigating the spectrum of the NTK and its connections to the Fisher Information Matrix, this work provided some insights into the spectral bias of neural network learning dynamics.", "questions": "- Besides the presented theoretical results, have the authors tried on any synthetic or MNIST-scale datasets to see if the results are consistent with the empirical experimental results?", "limitations": "N/A.", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "\n#### Strengths\n- This work continues to explore the spectral bias of the neural networks from the perspective of the neural tangent kernel theory. This work made some novel theoretical analyses on measuring the distance in function space and the scaling properties of the learning with respect to the stopping time.\n- This paper is generally clearly written. Alongside the main theoretical results, it provides some description and interpretation of the main theorems.\n\n#### Weaknesses\n- My main concerns are about the lack of more discussions about the connections with existing literature ([1,2,3,4,5]) on analyzing the spectral structure of neural networks and corresponding kernel formulations, for example, existing works [1] provided theoretical results on the spectral alignment of neural network and kernel methods in learning dynamics, [2] addressed the low-rank spectral structure of both neural tangent kernel and the Fisher information matrix. Not limited to the missing references below, a more detailed discussion on the theoretical and empirical connections to the relevant literature is needed.\n\n[1] Atanasov, Alexander, Blake Bordelon, and Cengiz Pehlevan. \"Neural networks as kernel learners: The silent alignment effect.\" arXiv preprint arXiv:2111.00034 (2021).\n\n[2] Zhang, R., Zhai, S., Littwin, E., & Susskind, J. (2022). Learning Representation from Neural Fisher Kernel with Low-rank Approximation. arXiv preprint arXiv:2202.01944.\n\n[3] Karakida, Ryo, Shotaro Akaho, and Shun-ichi Amari. \"Pathological spectra of the fisher information metric and its variants in deep neural networks.\" arXiv preprint arXiv:1910.05992 (2019).\n\n[4] Pennington, Jeffrey, and Pratik Worah. \"The spectrum of the fisher information matrix of a single-hidden-layer neural network.\" Advances in neural information processing systems 31 (2018).\n\n[5] Hazan, Tamir, and Tommi Jaakkola. \"Steps toward deep kernel methods from infinite neural networks.\" arXiv preprint arXiv:1508.05133 (2015).", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "G1xckh-VaPR", "reviewer": "Reviewer_32uw", "summary": "This paper presents a theoretical analysis \n- bounding the difference between a kernel dynamics of finite width network trained for time T with a finite set of samples and the ideal infinite width NTK kernel.\n- that concludes a finite width network is biased toward learning the top eigenfunction of the infinite width-based kernel ", "questions": "- The theorem associates the minimum width of the network and the number of samples to the number of iterations trained. I'm confused by this connection - scaling the size of the network is possible but the size of the data is, in practice, fixed. Does this mean that for fixed-size data, the results are applicable only up to a certain training step? \n", "limitations": "- The paper targets a simple question of spectral bias of networks using NTK kernels and provides a characterization that is applicable to deep networks.\n- The dependency on stopping time limits the consequences of the analysis to when the network is initialized (with few training steps)  ", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "- The paper positions itself well amongst related works and is presented such that even an outsider to the topic is able to understand the problem, analysis, and results.\n- The paper is constrained to bounding the difference in the kernels and it is not clear how the network architecture and activation function fits into the analysis. A discussion on how the model design affects the results could make clear the limitation as well as applicability to future model designs.\n- The analysis considered requires twice differentiable activation function which does not include ReLU. I think this is an admissible assumption for theoretical analysis though it makes analysis disconnected from practice.\nMinor comment\n- the notation for non-linearity and eigenvalue seems to be overloaded and might create confusion.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept