Neural tangent kernel eigenvalues accurately predict generalization
Authors: James B Simon
Madeline Dickens
Michael R DeWeese
Venue: ICLR 2022 Submitted (2022)
Keywords: deep learning
generalization
neural tangent kernel
kernel regression
inductive bias

Abstract: Finding a quantitative theory of neural network generalization has long been a central goal of deep learning research. We extend recent results to demonstrate that, by examining the eigensystem of a neural network's "neural tangent kernel," one can predict its generalization performance when learning arbitrary functions. Our theory accurately predicts not only test mean-squared-error but all first- and second-order statistics of the network's learned function. Furthermore, using a measure quantifying the "learnability" of a given target function, we prove a new "no free lunch" theorem characterizing a fundamental tradeoff in the inductive bias of wide neural networks: improving a network’s generalization for a given target function must worsen its generalization for orthogonal functions. We further demonstrate the utility of our theory by analytically predicting two surprising phenomena --- worse-than-chance generalization on hard-to-learn functions and nonmonotonic error curves in the small data regime --- which we subsequently observe in experiments. Though our theory is derived for infinite-width architectures, we find it agrees with networks as narrow as width 20, suggesting it is predictive of generalization in practical neural networks.

Under review as a conference paper at ICLR 2022
NEURAL TANGENT KERNEL EIGENVALUES ACCURATELY PREDICT GENERALIZATION
Anonymous authors Paper under double-blind review
ABSTRACT
In many cases, infinitely-wide deep neural networks are equivalent to kernel re- gression using the network's 'neural tangent kernel." With the aim of shedding light on the learning behavior of wide neural networks, in this work we derive new theory predicting the generalization of kernel regression. Our theory curately predicts not only test mean-squaredd-error but all first- and second-order statistics of the learned function. Furthermore, using measure quantifying the "learnability" of given target function, we prove new "no-free- fre-frre-uunch theorem characterizing a fundamental tradeoff in the inductive bias of kernel regression: improving generalization for a given target function must worsen its generaliza- tion for orthogonal functions. We further demonstrate the utility of our theory by analytically predicting two surprising phenomena worse- worse-than-chane tha---hhnhcceeeee general- ization on hard-to-learn functions and nonmonotonic error curves in the small data regime- which we subsequently observe in experiments. Though our theory is derived for networks in the infinite- width limit, we experimentally find that its predictions are accurate for wide finite networks.
INTRODUCTION
Understanding and predicting a machine learning model's generalization to unseen data a central goal of machine learning theory. For given class of model, one would idcally want simple picture of a model's inductive bias, identifying the set of functions on which a given model will generalize well and those which it will generalize poorly and making quantitative predictions of key measures of the quality of generalization. In this paper, we derive such a theory for ridgeless kernel regression with any kernel and, using the neural tangent kernel (NTK) equivalence between kernel regression and infinitely wide deep neural networks, shed light on the inductive bias and generalization of wide deep neural networks.
Our main contributions are as follows:
We prove basic conservation law describing the inductive bias of kernel regression (Theo- rem[]] This law states that any kernel has fixed budget of quantity we call "learnability" that it must allocate to an orthogonal basis of functions, and this budget is equal to the size of the training set. nel, there exists target function which kernel regression generalizes worse than chance (Corollary []. and we provide a recipe to construct such functions.
consequence of this conservation law, we prove that for every ker-
We derive a new theory of generalization for kernel regression, culminating analytical expressions for all first- and second-order statistics of the learned function (Fquations T1 and This theory extends the spectral picture of kernel regression revealed by Bordelon et al. (0220) and Canatar et al. (202T) We conclude from our theory that, in realistic settings, most kernel eigenfunctions have the counterintuitive property that MSE increases examples added to small training set (Section 2.7)
We empirically verify all our results on synthetic datasets using both exact kernel regression and deep networks width 500 trained with gradient descent. We find that our conserva- tion law and analytical expressions for generalization performance hold to excellent approximation even for wide finite networks, and we observe worse-than-chance general- ization and increasing MSE predicted. We find that our theory's core predictions remain

---

Under review as a conference paper at ICLR 2022
fairly accurate even down to width 20 for depth-four networks, suggesting it is promising starting point for understanding generalization in practical architectures.
1.1 RELATED WORK
The study of the generalization of kernel regression via spectral analysis began in the literature on Gaussian process inference, for which kernel regression gives the mean of the posterior function. In a limited teacher-student setting in which teacher and student were described by the same Gaussian process, Soolich (rolich, ( (1999) and Vivarelli & Opper] (199)) studied expected MSE as a function of training set size, and [Sollich (2001) extended their results to the setting in which the Gaussian processes' eigenvalues can differ, but no similar results from this era described the fully general setting.
The discovery of the equivalence between wide neural networks and kernel regression via the NTK (Jacot et al. 2018: Lee et al. 2019) sparked a resurgence of interest in the generalization of kernel regression [Belkin et al. 2018: Sa 2019b at Liang & Rakhlin 2020, Bietti & Mairal 2019). Further noting that both kernel regression and deep learning can generalize well despite perfectly interpo- lating their training data, [elkin et al. (2018b) argued that "to understand deep learning need to understand kernel learning."" Arora et al. (2019a) derived a data-dependent generalization bound for a wide two-layer architecture involving its infinite-width NTK. Though this bound a signif- icant advance over VC-dimension-base applies specific architecture and can be many times greater than the true loss, while our results predict true loss within small error bars and apply to any mnfinite-width architecture (and in fact to any incarnation of kernel regressionn.
bounds inapplicable to overparameterized models, it only
In pioneering work, [Bordelon et al. (2020) and Canatar et al. (2021) extended classic results on the generalization of kernel regression to the fully general case and, using the NTK, confirmed that their approximate expressions for expected MSE agree even with wide finite deep neural networks. Their results reveal a simple picture of neural network generalization: as samples are added to the training larger and larger subspace of input functions. The natural
set, the network generalizes well basis for this subspace of learnable functions is the eigenbasis of the NTK, and its eigenfunctions are learned in descending order of their eigenvalues. The results of the present paper corroborate and extend this picture of the generalization of kernel regression. Our work chiefly differs from theirs in that (a) our conservation law is new, (b) we derive and test expressions for generic first- and second-orde statistics of the learned function, not just MSE, and (c) our derivation is quite different (and, we believe, easier to understand) even when it arrives the same results.
Our work is related to the well-known observation that neural networks have a "spectral bias" to- wards representing slowly-varying functions Valle-Perez et al.) 2018 Yang Salman (019); in particular, the kernel spectrum picture clarifies that this bias is consequence of the fact that high NTK eigenmodes are typically slowly-varying. We also note a body of work studying the related phenomenon that slowly-varying functions are learned first during training (Rahaman et al.) 2019
Xu et al. 2019b Xu 2018:
Cao et al. 2019 Su & Yang 2019).
THEORY
2.1 A REVIEW OF KERNEL REGRESSION
Consider the task of learning an m-element function f X Thth given set of n unique training points D = {x: }T=1 C X' and their corresponding function values f(D) E _= To simplify our analysis, we will let the domain X' be discrete with size M | and assume the n training points are uniformly sampled from X. This choice of discrete domain will permit us to use matrices and vectors instead of operators and functions in our derivations. By taking M + co, our results easily extend to problems with continuous domain: for example, if M + oo and we allow the points in X' to approach a density equal to some desired measure over Rdd we recover the standard setting where the data are sampled nonuniformly from Rd
We will use f to denote the function learned by neural network trained on this dataset. Remarkably, for an infinite-widhe neural network optimized via gradient descent to zero training MSE loss, this leamned function is given by
f(x) K(x, D))
2

---

Under review as a conference paper at ICLR 2022
2018 Lee where K X x X' + R is the network's "neural tangent kernel" (NTK) ( (Jacot et al.
et al. 2019), () is the "kernel matrix" defined by () = K ( (z) Ty), and K (x, D) is
a row vector with components (x, D), = K (x x;) | We give a brief introduction to the NTK in Appendix C
Due to its similarity to the normal equation of linear regression, Equation is often called "kernel regression." 0
Equation T holds exactly in the Sefinite-widte limit of conneccd networks (Lee et al. 2019 convolutional networks (Arora et al.] 2019b), transformers (Hron et al. 2020). and more Yangg
2019). Moreover, several empirical studies have shown it to be good approximation for networks of even modest width (Lee et al.] 2019, 2020). Our approach will be to study the generalization behavior of Equation |
conjecture that our results also apply to finite networks, and finally provide strong support for our conjecture with experiments.
Examining Equation 1 one finds that the m indices of f can each be treated separately: the learned f is equivalent simply performing kernel regression with each of the m indices as scalar target function and then vectorizing the results. For simplicity, then, we hereafter assume 1. The extension to m > straightforward.
2.2 FIGURES OF MERIT OF f
We will study three measures of the quality of the learned function f. All three will be defined in terms of the inner product over X: for two functions g, h X + R, their inner product is (g. h) = M Exex g(z)h(x).
The first measure of quality is mean-squared error (MSE). For a particular dataset D, MSE is given by E(P) (f) (f - f.f - f). Of more interest will be the expected MSE over all datasets of size n, given by E(f) Ep (f)]. We note that the inner product is taken over all X, including D, even though f(x) fz) for æ E D for kernel regression.
In maximizing the similarity of f to f. we typically wish to minimize its similarity to all functions orthogonal to f. The second measure examines the coefficient in of one such orthogonal function to f. Letting g X' IR. be function such that (f.g) = 0, we consider the mean and variance of the quantity (f.g) g). We will derive accurate predictions for this metric of generalization.
Lastly, we introduce a figure of merit quantifying the alignment of f and f. which we call "learn- ability." It is given by
(f.f) (S,)' C()= ED [
((P(())
where (() is the dataset-dependent learnability of the function f ("D-learnabilitty) and L(F) is its expectation over random data ("Icamaailltty)) Though at first glance these two seem like odd figures of merit, we will soon show that they have many desirable properties when f is given by Equation [ unlike MSE, both are bounded in [0, 1] (Lemma Db), always change monotonically as new data points are added (Lemma (e)) are invariant to rescalings of f, and obey a simple conser- vation law (Theorem D. Furthermore, expanding the inner product the definition of & and noting that E(f) 2 (f. f1 C(f)),, one can see that low MSE is impossible without high learnability. We will ultimately derive an accurate approximation for learnability that is substantially simpler than any known approximation for MSF.
Naively, Equation is only the expected learned function, and the true learned function will include a fluctuation term reflecting the random initialization. However, by storing a copy of the parameters at = 0 and redefining f((x) ;= fxx - fo( throughout optimization and at test time, this term becomes zero, and so we neglect it in our theory and use this trick in our experiments.
² 'Interestingly. exact Bayesian inference for anfinite-width neural networks yields predictions of the same form as Equation [] with K being the "neural network Gaussian process" (NNGP) kernel instead of the NTK (Lee et al. 2018). We will proceed treating K as network's NTK, but our theory and exact results (including our mon-free-lunch" theorem) apply equally well to any incarnation of kernel regression, including RBF kernel regression and linear regression.

---

Under review as a conference paper at ICLR 2022
2.3 THE KERNEL EIGENSYSTEM
By definition, any kemel function is symmetric and Dositive-semidefnni (Shawe-Taylor et al. 2004). This implies that we find set of orthonormal cigenfunctions {0: 37 M that satisfy
and nonnega-
tive eigenvalues {Me]i=1
K(a,,')os(r)) = (x))(()), (0i, kb) dez- N'EN'
Σ
M
For simplicity (and ensure that (D, D) invertible), we will assume that K is in fact positive definite and >; > 0, an assumption that will hold in most cases of interest P
We will now translate Equation to this eigenbasis. First we decompose f and into weighted sums of the eigenfunctions as
M
M
f(x) = Σ vo(()), f(x) = Σ 0.)((z),
(4)
1=1
where and V are vectors of coefficients. Using this notation, MSE is g(D) (v v)² and D-learnability is L(D) = v/vp//?
Noting that (2) K(D, D) T (D)A where (D));, dı(xy) is the M "design matrix" and A = diag( A1, Am) is a diagonal matrix of eigenvalues. The learned coefficients are then given by é (Øs f) (D)K((D) TT (D)v. Stacking these coefficients into a matrix equation, we find that
E (12))
decompose the kernel matrix as
A 3 (D)A T (DNN=
is M M matrix, independent of f. that fully describes the model's 's learning behavior on a training set D. We call this fundamental quantity the "learning transfer matrix." If we determine the statistical properties of this matrix, will understand the learning behavior of our model.
where T(P) (D) D (D))A((()) t
We also define the mean learning transfer matrix = T [P[]]_ D-learnability and learnability are then respectively given by ((P) = (DT(DD)//vv and L(f) = Tv//v/2
2.4 EXACT RESULTS
The following lemma gives basic properties of the quantities defined above. Lemma 1. The following properties of (P), T, L(P), and L hold:
(a) ((P) T(P) and L(())) Tú..
(b) When 0, T (D) 0 and L(f) ((P) 0.
(c) When n = M, T = ( IM and L(f) = (f) =.
(d) All eigenvalues of (D) in {0, 1}, all eigenvalues of T are in [0, 1]. and so (())) E [0,
(e) Let D4 be U x, where x E X,x & D is a new data point. Then L ((++) 2 (f)
(f) For any E (I,..,,M,
d (P))
2 0, hence d
((P) 20. 0.
ax,
(g) For any i,j E (1,..., M), i # A. T
(D) hence ax. (iP) 50.
By Mercer's Theorem, one can also find the eigensystem any kernel on continuous input space X. We do not use the Reproducing kernel Hilbert space (RKHS) formalism in this work, but note that, by the Moorc-Aronszajn theorem, the kemel K defines unique RKHS.
4

---

Under review as a conference paper at ICLR 2022
Property (a) in Lemma I formalizes the relationship between the transfer matrix and learnaiility. Properties (b-e) together give an intuitive picture of the learning process: the learning transfer ma- trix monotonically interpolates between zero and I the training set grows adding data never harms the learnability of any function. Properties (f-g) show that the kemel eigenmodes are in com- petition: increasing one eigenvalue only improve the learnabllity of the corresponding eigen- function, but can only decrease the learnabilities of all others. We prove Lemma | in Appendix D
We now present our first major result.
Theorem ("No-free-lunch" theorem for kernel regression). For any complete basis of orthogonal functions F.
ΣCの= FEF
Σ ((P =n. SEF
The proof, which hinges on the intermediate result that Tr [P)] n, is given in Appendix We note that this result is stronger than the ordinary "no-free-lunchi theorem for learning algorithms, which requires averaging over all target functions instead of merely orthogonal basis (Wolpert) 1996). To understand the significance this result, consider that one might naively hope to design neural kernel that achieves generally high performance for all target functions f. Theorem states that this is impossible: averaged over complete basis of functions, all kernels achieve the same learnability. This exact result implies that, because there exist no universally perr-perforiin kernels, we must instead aim to choose a kernel whose high-eigenvalue modey align well with the function to be learned. To our knowledge, this is the first exact result quantifying such tradeoff in kernel regression or deep learning.
Illustrating a consequence of this tradeoff, the following theorem states that, for any kernel, there will always be functions pporly-aligned with the kemel''s 's inductive bias on which the model generalizes as bad or worse than would by simply predicting zero on all unseen test points.
Corollary 1 (Negative generalization). There always at least one eigenfunction ò, for which [( < Lnaivel0; and E(o,) 2 Evaive (di), where Enaive and Eaiiee are the learnability and mean MSE given by a naive, non- non-generalizing model with predictions given by
fnoive (x)
[f(x) 10
x EED
x E
This theorem follows from Theorem I We give full proof in Appendix E This negative gener- alization property will hold for any function with learnability less than or equal to n/M, including any weighted sum of cigenfunctions with this property.
2.5 DERIVING A CLOSED-FORM EXPRESSION FOR
We will now derive an approximation for and the second moments of T(P), ultimately yielding simple yet accurate expressions for L, E, and (f.g)- We sketch our method and state our results here and provide full derivation in Appendix F
We begin by noting that the expectation in T ED (D) is essentially expectation over combinatorially large set of possible design matrices & (D), each of which has orthogonal columns. We replace this with an average over all M x n matrices satisfying T MI,, which we write
T= T (D) ( (D)AA(()) Φ T'((D) =e Eg AΦ
TT AΦ
(8)
We can then readily prove by symmetry that the off-diagona elements of T vanish, leaving the question of how each diagonal element depends on the set of eigenvalues. To probe this, we consider adding an (M + 1)-th "test eigenmode" to the problem, augmenting the principal quantities as
A+
=
A
0 X
T = Eg d A A (T+TA
-1 +
+T
99)
5

---

Under review as a conference paper at ICLR 2022
Using the Sherman-Ne Moriasoo formula, find that the new mode's learnability is given by
T (M+D)(++1) = Ex.
= Exr sb
(10)
AΦ Φ -I
A C(+
ΦJ T
is nonnegative dataset-dependent constant. For large n and realistic eigenspectra, ((..)) is distributed tightly around its mean, and so we can replace it with a constant, which we call C. We emphasize that is the same for every eigenmode. Using Theorem I to obtain a constraint on C, we reach our ultimate approximation that
where ((+,))= = TT AΦ
M
A A + C
A A +C
Tij = dig
where C 2 0 satisfies
(11)
Using Lemma we obtain the major result that
A C
C())
(12)
with C' given by Equation
11
A function is thus more learnable the more weight places in high eigenvalue modes. We show in Section 3 that Equation [2]s in excellent agreement with experiments using both kernel regression and trained finite networks.
The learnability of each eigenmode depends critically on the value of C. We now present several properties characterizing how C' depends on n.
Lemma 2. For C satisfying the constraint in Equation 11 with M ordered from greatest to least, the following properties hold:
(a) C when O, and C = when M.
(b) strictly decreasing with n.
(c) C D. for all E (0...,, 1}.
(d) C2 2e for all (n...,.})
Properties (a-b), paired with Equation TT paint surprisingly simple picture of the learning process: as the training set grows, C gradually decreases, and cigenmodes are learned high-to-low as C' passes each eigenvalue. Properties (c-d) provide bounds C, which, in addition to then yielding bounds on learnability, can be used to furnish an initial guess when numerically solving for C.
2.6 SECOND-ORDER STATISTICS OF T
We now have an expression for the mean of (D)) but many quantities of interest, including MSE, depend on second-order fluctuations about that mean. In Appendix G we show how, by taking derivative with respect A, we obtain expressions for the second-order statistics of (P) and, as result, for MSE. Our main second-order result is that
Cov T
(P) kt
=
CAide (ōa.5z + ōzddz ōzjōkt) ((A+ ()( + C)(ee + C)'
where =
Σ
M
(Am + C)2
Am
(13)
m=1
Using Equation| [3 we can study the admixtures of particular spurious modes in the learned function f. For example, if = Φi and * j. then we find that
CA
E B(( =0, {(( = Var (
(14)
9(>: + CC)(A, + CC2

---

Under review as a conference paper at ICLR 2022
We note that E (f increases with Xy. reinforcing our broad conclusion that the model is biased towards high-eigenvalle modes. Finally, by noting that {(f) = Ep [| (T - -Ia)v/? we can recover the expression of Bordelnn et al. (2020) for MSE:
{( v Ev, where Eny- = 61 nC
(15)
(A, C)
Our experiments corroborate existing evidence that this is an excellent approximation for MSE.
2.7 NONMONOTONIC MSE CURVES Expanding E for small n, we find that
dEu
Σ 24
Eg n=0
=1
dn
[ΣS (I,,,² Σラ
(16)
The second equation implies that AB4 which suggests that, for such low-eigenvalue modes, MSE increases as the training set size grows from zero. In practice, such low modes are commonplace; in fact, for bounded kernel on a con- tinuous input space (for which M - oc), an infinite number of arbitrarily low modes is inevitable due to the constraint that E; A is bounded We therefore expect that there quite often exist func- tions for which given neural network yields an MSE nonmonotonic with Figure AT shows that experiments confirm this surprising first- trst-principles prediction. We emphasize that this a different, more generic phenomenon than that noted by Canatar et al. (2021), which required that was either noisy or placed weight in unlearnable zero-eigenvalue modes.
In=0 0 for all modes i such that A < (E,, 12)
EXPERIMENTS
Here we describe experiments confirming our theoretical predictions for exact NTK regression and wide neural networks. Unless otherwise stated, all experiments used a fully-connected (FC) four- hidden-layer (41.) ReLU architecture with width 500. Because this model is FC, it has rotation- invariant NTK (Lee et al., 2019). These experiments used three distinet input spaces X. For each, the eigenmodes of X can be grouped into degenerate subsets indexed by h N. with higher k corresponding to faster variation in space. In all cases, we find that as increases, cigenvalues decrease, in concordance with the widespread belief that neural nets have a "spectral bias" towards slowly-varying functions (Rahaman et al. 2019| Canatar et al. 2021 Cao et al. 2019). We now describe these three input spaces. For full experimental details, Appendix H
Discretized Unit Circle. The simplest input space we consider is the discretization of the unit circle into M points, X' = {(cos(2T)/ (2 MM), sin [2z [ The eigenfunctions on this domain are (0) 1, (0) = /2 cko() and &% (0) = 22 (ko)), for k 2 1.
Hypercube. The next input space we consider is the set of verticies of the d-dimensional hypercube, X = (-1, giving M = 2d, The eigenfunctions on this domain are the subset-parity functions (x) = (-1)=² where E {0. 1) 1 is vector indicating the elements of x to which the output is
sensitive Yang & Salman 2019 Here we define k Σ $i.
Hypersphere. To illustrate that our results extend easily to continuous input spaces, we consider the + 1). The eigenfunctions on this domain are the hyperspherical harmonics (see, e.g., Frye & Efthimiou (2012); Bordelon et al.) (202h) which group into degenerate sets indexed by l: E N. The corresponding eigenvalues decrease exponentially with k and so when
d-sphere 8d = {i RZ++|
summing over all eigenmodes to compute C' and g. we simply truncate the sum at himex 70.
Figure 5 shows the 4L ReLU NTK eigenvalues on each domain, of which decrease almost monotonically with increasing k. In particular, the eigenvalues on the unit circle roughly follow power-law decay like the NTK spectra common image datasets (e.g. Lee et al. (2020)). We now describe our experiments.
Thiis constraint follows from the fact that Σ, X, 1 Evex K(2,z) cc.
7

---

Under review as a conference paper at ICLR 2022
Unit Circle
8d Hypercube
7-sphere
1.00
(1)) (0x)
0.75
0.50
0:25
0.00
21
2
Theoretical predictions closely match the true learnabilities of arbitrary eigen- functions on diverse input spaces. Each plot shows learnability ((ex) (Equation [1] of several eigenfunctions a function of training set size n. Theoretical curves show excellent agreement with results from exact NTK regression (triangles) and finite nets trained via gradient descent (circles). Error bars reflect la variation due to random choice of dataset and, for finite nets, random initial- ization. (A) Learnabilities of sinusoidal eigenfunctions on the unit circle discretized into M = 2 points. Eigenfunctions with higher & have lower eigenvalues and thus require more data to learn. At n = 28, the training set contains all input points and all functions are thus predicted perfectly. (B) Learnabilities of subset-parity functions on the vertices of the 8d hypercube. Eigenfunctions with higher A: again have lower eigenvalues and are learned later, with all functions predicted perfectly 28. The dashed line indicates C n/M, the learnability of any function with respect random model; L(os) falls below this curve, showing that the k = 8 eigenmode generalizes worse than chance. (C) Learnabilities of hyperspherical harmonics on the continuous 7-sphere S7. Eigen- functions with higher & again have lower eigenvalues and are learned later, but the continuous input space prevents Icarnability from exactly reaching 1.
Figure 1:
Unit Circle
8d Hypercube
7-sphere
1.0
A
( (n=64) (00))))) (o-8)
0.8
All
0.6
kemne
0.2
Afr
0.0
10-1
10-1
10
10
10
10
10
10-1
10
0.8
0.6
0.4
AC
0.2
10-4
10-1
10P
10
16a
10a
Ay/C
10
10
10a
10
10
10a
A
Ax
Figure 2:
Eigenmode learnability eigenvalue takes universal functional form. For any
dataset size and input domain, eigenmode learnability closely follows a universal curve >/(A + C) with one problem-dependent parameter C. Theoretical curves (solid lines) have the same sigmoidal shape in every panel. True eigenmode learnabilities L((x) for & E {O,.., for both exact NTK regression (triangles) and finite networks (circles) exhibit excellent agreement. Vertical dashed lines indicate C' for each learning problem. (A-C) Learnability vs. eigenvalue for eigenmodes of the unit circle, 8d hypercube, and 7-sphere with n 8. The k E (4..., 7} modes are cut off to the left of (C). (D-F) Learnability curves with = 64. Eigenmodes lie higher on each curve than the corresponding points in (A-C), reflecting greater learnability due to the larger n. (G) All points from
(A-F), rescaled by their respective values C, lie on the same universal curve A/C
X/C+1
Predicting learnability C(P), We use both wide finite nets and exact NTK regression to learn several eigenmodes all three domains and compare true learnabilities with our theoretical pre- dictions. Our theory predicts true generalization behavior quite well (Figure D We further show that the k 8 mode the Sd hypercube has worse-than-chanee generalization. of its low eigenvalue and Corollary [ We note that finite networks and NTK regression give very similar results, supporting the validity of approximating networks with the NTK.
inevitable result
8

---

Under review as a conference paper at ICLR 2022
n = 3
n =
A
B
L ( (ox)
8
kernel
net
1HL ReLU
4HL ReLu
tanh
4HL tanh
1HL ReLU
4HL ReLU 1HL tanh
4HL tanh
Figure 3: Eigenfunction learnability always sums to the size of the training set. Stacked bar charts show D-learnability for particular random D for each of the 10 eigenfunctions over simple 10-point domain. For all architectures, the total height of each bar is approximately n. (A) As per Theorem [ the summed D-learmabilities for exact NTK regression (left bars) are all exactly and those for trained finite nets (right bars) are remarkably close. Stacked bars show D-learnability for the 10 eigenfunctions, all from the same training set 'D of n 3 data points, stacked from top bottom in descending order of eigenvalue. A different network architecture was used in each of the four pairs of columns. As per Lemma Id. the height of each eigenmode contribution falls in [0, 1]. (B) Same as (A) with 6.
Universal form for learnability, We next fix and plot learnability vs. eigenvalue for eight modes over each domain. In each case we find L(Ø) x X/(A C.), and by rescaling the eigenvalues (a symmetry which leaves Equation I Tinariiant), we see that for any neural network learning problem with any training set size eigenmode learnability always lies on one universal curve (Figure 2
No free lunch for neural networks. We then experimentally confirm that our no-free-lunch result applies to finite networks as well kernel regression (Figure 3 We both models to learn function on the discretized unit circle with M = and sum the resulting D-learnabilities of each eigenmode. Unlike in our other experiments, only sample DD once for each benefit of averaging over datasets, we find that total D-learnability is always conserved.
without the
Nonmonotonie MSE curves. We next confirm curves at small n. We plot curves for four eigenmodes on each domain, three of which Equation [6 predicts will have positive dE/di //d////., MSE is indeed increasing predicted (Figure A1
princ-principes prediction of nonmonotonic MSE
Agreement with narrow networks. Finally, we repeat the experiment of Figure T for varying network width. We find that our theory gives accurate predictions of learnability and MSE even for networks of depth 4 and width as small as 20 (Figures B2 and B3). This surprising agreement suggests our theory is a promising starting point for understanding the generalization of practical neural networks.
CONCLUSION
We have presented a first-principles theory of generalization for kernel regression that predicts a variety of measures of generalization performance. We then empirically demonstrated its predic- tive accuracy for both exact NTK regression and wide finite networks in the NTK regime. This theory offers new insight into these models' inductive bias and provides general framework for understanding their learning behavior, opening the door to the principled study of many other deep learning mysteries.
REFERENCES
Sanjeev Arora, Simon Du, Wei Hu, Zhiyuan Li, and Ruosong Wang. Fine-grained analysis of op- timization and generalization for overparameterized two-layer neural networks. In International Conference Machine Learning, pp. 322 332. PMLR, 2019a.
Sanjeev Arora, Simon S. Du, Wei Hu, Zhiyuan Li, Ruslan Salakhutdinov, and Ruosong Wang. On exact computation with an infinitely wide neural net. In Advances Neural Information Processing Systems (NeurIPS), pp. 8139-8144 814888188.000 2019b.
Mikhail Belkin, Daniel Hsu, and Partha Mitra. Overfitting or perfect fitting? risk bounds for classi- fication and regression rules that interpolate. arXiv preprint arXiv:/806.000 061, 2018a.

---

Under review as a conference paper at ICLR 2022
Mikhail Belkin, Siyuan Ma, and Soumik Mandal. To understand deep learning need to under- stand kernel learning. In International Conference on Machine Learning, pp. 541-549. PMLR, 2018b.
Mikhail Belkin, Daniel Hsu, Siyuan Ma, and Soumik Mandal. Reconciling modern machine- learning practice and the classical bias-variance trade-off. Proceedings of the National Academy of Sciences, 116632):18449-1558 2019a.
Mikhail Belkin, Alexander Rakhlin, and Alexandre B Tsybakov. Does data interpolation contra- dict statistical optimality? In The 22nd International Conference on Artificial Intelligence and Statistics, pp. 1611-1619) PMLR, 2019b.
Alberto Bietti and Julien Mairal. On the inductive bias of neural tangent kernels. arXiv preprint arXiv: 12173, 2019.
Blake Bordelon, Abdulkadir Canatar, and Cengiz Pehlevan. Spectrum dependent learning curves in kernel regression and wide neural networks. In International Conference on Machine Learning, pp. 10344 PMLR, 2020.
Abdulkadir Canatar, Blake Bordelon, and Cengiz Pehlevan. Spectral bias and task-model alignment explain generalization in kernel regression and infinitely wide neural networks. Nature communi- cations, 12(1):1-12, 2021.
Yuan Cao, Zhiying Fang, Yue Wu, Ding- Xuan Zhou, and Quanquan Gu. Towards understanding the spectral bias of deep learning. arXiv preprint arXiv: arXiv:1912.01 1912001198, 2019.
Christopher Frye and Costas J Efthimiou. Spherical harmonies in p dimensions. arXiv preprint arXiv:1205.3548, 2012.
Jiri Hron, Yasaman Bahri, Jascha Sohl-Dickstein and Roman Novak. Infinite attention: NNGP and NTK for deep attention networks. In International Conference on Machine Learning (ICML), volume 119 of Proceedings of Machine Learning Research, pp. 4376-4386. PMLR, 2020.
Arthur Jacot, Clément Hongler, and Franck Gabriel. Neural tangent kernel: Convergence and gener- alization in neural networks. In Advances in Neural Information Processing Systems (NeurIPS), pp. 3580-8589, 2018
Jaehoon Lee, Yasaman Bahri, Roman Novak, Samuel S. Schoenholz, Pennington, and Jascha Sohl-Dickstein. Deep neural networks gaussian processes. In International Conference on Learning Representations (ICLR). OpenReview.net, 2018.
Jachoon Lee, Lechao Xiao, Samuel S. 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 Advances in Neural Information Processing Systems (NeurIPS), pp. 8570-8581, 2019.
Jaehoon Lee, Samuel S. Schoenholz, Jeffrey Pennington, Ben Adlam, Lechao Xiao, Roman Novak, and Jascha Sohl-Dickstein Finite versus infinite neural networks: an empirical study. In Advances in Neural Information Processing Systems (NeurIPS), 2020.
Aitor Lewkowycz, Yasaman Bahri, Ethan Dyer, Jascha Sohl-Dickstein, and Guy Gur-Ari. The large learning rate phase of deep learning: the catapult mechanism. CoRR, abs/2003.02218, 2020.
Tengyuan Liang and Alexander Rakhlin. Just interpolate: Kernel "ridgeless" regression can gener- alize. The Annals of Statistics, 48(3):1329-1347, 2020.
Roman Novak, Lechao Xiao, Jiri Hron, Jaehoon Lee, Alexander A. Alemi, Jascha Sohl-Dickstein, and Samuel S. Schoenholz. Neural tangents: Fast and easy infinite neural networks in python. CoRR, abs/1912.00880) 2019.
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 International Confer- on Machine Learning, pp. 5301-5310. PMLR, 2019.
10

---

Under review as a conference paper at ICLR 2022
John ShaweeTTylor, Nello Cristianini, et al. Kernel methods for pattern analysis. Cambridge uni- versity press, 2004.
Jascha Sohl-Dickstein, Roman Novak, Samuel S Schoenholz, and Jachoon Lee. On the infinite width limit of neural networks with a standard parameterization. arXiv preprint arXiv:2001.07301,
2020.
Peter Sollich. Learning curves for gaussian processes. Advances in neural information processing systems, pp. 344-34 4500 1999.
Peter Sollich. Gaussian process regression with mismatched models. arXiv preprint cond- mat/0106475, 2001.
Lili Su and Pengkun Yang. On learning over-parameeterized neural networks: A functional approxi- mation perspective. arXiv preprint arXiv:1905. 2019.
Guillermo Valle-Perez, Chico Q Camargo, and Ard A Louis. Deep learning generalizes because the parameter-function map is biased towards simple functions. arXiv preprint arXiv:/8055 08522, 180.08852, 2018.
F Vivarelli and M Opper. General bounds bayes errors for regression with gaussian processes. Advances in neural information processing systems, 11:002-308, 1999.
David H Wolpert. The lack of priori distinctions between learning algorithms. Neural computation, 877:1144 1996.
Zhi-Qin John Xu, Yaoyu Zhang, Tao Luo, Yanyang Xiao, and Zheng Ma. Frequency principle: Fourier analysis sheds light on deep neural networks. arXiv preprint arXiv: 1901.065200 2019a.
Zhi-Qin John Xu, Yaoyu Zhang, and Yanyang Xiao. Training behavior of deep neural network in frequency domain. In International Conference on Neural Information Processing, pp. 264-274. Springer, 2019b.
Zhiqin John Xu. Understanding training and generalization in deep learning by fourier analysis. arXiv preprint 1808. 1808.0429, 2018.
Greg Yang. Tensor programs I: wide feedforward or recurrent neural networks of any architecture are gaussian processes. CoRR, abs/1910. 12478, 2019.
Greg Yang and Hadi Salman. A fine-grained spectral perspective on neural networks. arXiv preprint 1907. 10599, 2019.

---

Under review as a conference paper at ICLR 2022
A
NONMONOTONIC MSE CURVES AT SMALL TRAINING SET SIZE
Unit Circle
6d Hypercube
2-sphere
1.5
1.5
0.75
1.0
0.50
0.5
0.0
0.0
2
Figure A1: Our theory correctly predicts that, for low-eigenvalue eigenfunctions, MSE coun- terintuively increases as points are added to small training set. (A-C) Generalization MSE of exact NTK regression (triangles) and finite networks (circles) when learning four different eigen- modes on each of three different domains given training points. Theoretical curves closely match experimental data. Figenmodes with higher have lower eigenvalues and thus higher mean MSEs, and for {2, 4, 6), MSE even increases increases from zero. Dashed lines show dE/dn| n= as predicted by Equation I6
B EXPERIMENTAL RESULTS FOR NARROW NETWORKS
1.2
width
width 500
width 200
1.0
(
4 (D) k
0.8
k=8
0.6
0.4
0.2
1.2
width 100
width 50
width 20
1.0
(
((D) (6V
0.8
0.2
2
2
2
26
2
20
2
2
25
2
2
2
n
n
Figure B2: Theoretical learnability predictions remain accurate for quite narrow net- works of moderate depth. Plots show learnability vs. training set size for four eigenmodes of the 8d hypercube, learned with 4L ReLU net with various widths. Except for changing width, these experiments are identical to those of TT. Theoretical predictions (solid curves) are the same all plots. Dashed lines show learnability from a naive, nongeneralizing model; points below the line imply worse-than-chance generalization (see Corollary [). (A) Infinite-width results using ex- act NTK regression. (B-F) Results for successively narrower finite networks. As width decreases, mean learnability increases slightly, and lo error grows. Despite this, mean learnabilities remain remarkably close to our theoretical predictions even at width 20.
12

---

Under review as a conference paper at ICLR 2022
2.0
A
width
B
width 500
c
width 200
K-0
K-3
1.5
(Φc)
8 (D)
1.0
0.5
0.0
2.0
D
width 100
width 50
width 20
1.5
(D) (Øk)
1.0
0.5
0.0
2
2
2
24
2 17
17
17
Figure B3: Theoretical MSE predictions remain accurate even for quite narrow networks. Plots show MSE vs. training set size for four eigenmodes of the 8d hypercube, learned with a 4L ReLU net with various widths. Except for changing width and the fact that MSE plotted instead of learnability, these experiments are identical to those Figure Dp. Theoretical predictions (solid curves) are the same in all plots. Dashed lines show MSE from naive, nongeneralizing model; points above the dashed lines imply worse-than-chance generalization (see Theorem (THEOREM]), (A) Infinite-width results using exact NTK regression. (B-F) Results for successively narrower finite networks. As width decreases, MSE tends to increase, but only slightly. Theoretical predictions remain remarkably accurate for most eigenmodes down to width 50, with qualitative agreement even at width 20.
C REVIEW OF THE NTK
In the main text, we assume prior familiarity with the NTK, using Equation as the starting point of our derivations. Here we provide definition and very brief introduction to the NTK for unfamiliar readers. For derivations and full discussions, see Jacot et al. (018) and Lee et al. (2019).
Consider feedforward neural network representing a function fe X' + R, where 0 is a parameter vector. Further consider one training example with target value y and one test point x' and suppose we perform one step of gradient descent with small learning rate r7 with respect to the MSE loss to (fo(z) 2 This gives the parameter update
0 + 80, with 50 = -IVVol -2n(f
Vefo(x))
(17)
We now wish to know how this parameter update changes fo(x'). To do so. we linearize about 0, finding that
lotso(x') Po(x') + Vala(r') 80 0(802)
80
- -o(x') 2n(s 1) Vofo(s))vooff(a)) 0(803)
(18)
= fo(x') - 2n( y) ((zxz)))0(00
13

---

Under review as a conference paper at ICLR 2022
where we have defined (x, 2²) Vofo(z) Vofo(z'). This quantity is the NTK. Remarkably, as network width goes to infinity, the (882) corrections become negligible, and (xx, x²) is the and and any time during training. This dramatically simplifies the analysis of network training, allowing one to prove that after infinite time training on MSE loss for arbitrary dataset, the network's learned function is given by Equation [ See, for example, Equations 14-16 Lee et al. (2019
same after any random initialization"
D PROOF OF LEMMA T
Property (a): (d)) T and [().) Tn:
Proof. Using the fact that (di, Φz) = 1, we see that (()) (Ø:; Φi) o TP) = D
where e; is one-hot M-vector with the one index The second clause of the property follows by averaging.
Property (b): When n = 0, = T(P) = 0 and L()) = L(D) = 0.
Proof. When n = 0, ((D) has no columns, and thus ((D) = 0. The other clauses follow from Property (a) and averaging.
Property (c): When M. = T() LMs and L(f) (f) =.
Proof. When M, (D) is full-rank M x M matrix. Inspection of the formula for T(P) then shows that (P) = IM. The other clauses follow from Property (a) and averaging.
Property (d): All cigenvalues of (D)) are in {0, 1}. all eigenvalues of T are in [0, 1]. and so L(), (()))
(f) E 10.
Proof. From the definition of (P)), it is easy to see that (P)) (T(P)) (P)) is thus idempotent, with all eigenvalues in {0, 1). The fact that all eigenvalues of T are in [0, 1] follows by averaging.
The stated properties of [(f), (() follow from the fact that, for any compatible vector and
matrix A, it holds that z²A2 is bounded by the maximum and minimum eigenvalues of A.
Property (e): Let D+ be DUz, where E X, x & D is a new data point. Then C(P) ((P))()) 2 (P)
Proof. To begin, we use the Moore-Penroee pscudoinverse, which we denote by (-)+, to cast (D)
into a more transparent form:
(P) = A& (o"
क- = 1/2 (1/2((1//// (A'2 (A'/200 AΦ)
A 11/2) A 1/2
(19)
where we have suppressed the D in (DD. This follows from the property of pseudoinverses that A(AT A)+ AT =(AAT) (AAT)+ for any matrix A. We augment system with extra data point, getting
((++) = 1/2 (A 1/2 A1E7) (1 -E5))A122 A A-1/2,
(20)
where & is M-element column vector orthogonal to the others of Φ. We convert the pseu- doinverse into an inverse with a limit, getting
( lim 1/2 (A (11/2 )VE)) ( (1 + + 88M)) A -1/2
5-
(21)
The "width" parameter varies by architecture; for example it is the minimal hidden layer width for fully connected networks and the minimal number of channels per hidden layer for convolutional network. (assuming the parameters are drawn from the same distribution)
We note that there exists different infinite-width kernel, called the "NNGP kemell"" deseribing network's s random initialization, and this reference uses K. for the NNGP kernel and θ for the NTK.
14

---

Under review as a conference paper at ICLR 2022
We now use the
matrix inversion formula to find that
T(D+) -T(P) lim (A (A'/2 A 41/24011 +dIM) 55" (A1/240p') A + 0IM) 1 (A1/20077 A + sT
(22)
6--0
Because both EE" and the inverted matrix in Equation 22 that, for any M-vector it will hold that z TT'tt++)
positive semidefinite, conclude
(D)) z. The desired property follows.
Property (f) For any i {L, M),
d ( O. hence d ((P) 2 0. ax,
ax;
Proof. Differentiating ( with respect particular A,, we find that
T (P) d>;
=ōor 100 K )1) K-
(23)
where of is the i-th row + and K = A.. Specializing to the case = j. we note that of 1 pb; 2 0 because K positive semidefinite, and X, K of K- S because d is one
of the positive semidefinite summands in Σn A The desired property follows.
Property (g): For any i E {I...., M) i j. 2x. T O. hence ax.
(Φ;) S O. (D)
Proof. Differentiating in the proof of Property (f) and using the fact that i + j. we see that
d T(P)
dy: jf - K k
(24)
which is manifestly nonpositive because Xj > O. The desired property follows.
E PROOFS OF THEOREM 1 AND COROLLARY 1
Here we prove Theorem I our "no-free-lunch" result, and Corollary D which states the existence of eigenfunctions that generalize worse than chance. We begin with the former.
Proof of Theorem 7 First, we note that, for any orthogonal basis on X,
Σ T VEV
Σc fEF
(25)
where V is orthogonal of vectors spanning IR M This is equivalent Tr [T(P]. This trace is given by
Tr [ Tr [ A Tr[I.] = n,
(26)
which proves the desired theorem.
Proof of Corollary 7 First, we note that the naive, nongeneralizing model described in the theorem nff.fi - As per Theorem this exactly MJJ.
will always have a learnability of Cnaine (f) Ep
the mean learnability of all eigenfunctions, either all have precisely this learnaillity else one has lower learnability. This proves the clause of the theorem specific to learnability.
To prove the clause specific MSE, now note that, defined by Equation I kernel regression will always perfectly memorize the training data, so for both the naive model and kernel regression, MSE is given by
15

---

Under review as a conference paper at ICLR 2022
8(f)
Σ (f(x)-f(0))
1 Σ ((x)
1 Σ f(x)²- M
2 E f(x)f(x). (27) M
ME
M
M DEAVD
BEAND
DEXID
The first term is the same for any model, the second term is nonnegative but zero for the naive model, and the third term is equivalent to -2(((f) M/ ). which must be nonnegative for least one eigenfunction. Kernll regression therefore gives worse MSE than the naive model unless, as for the naive model, f()) 0 for & D. C
F APPROXIMATING T
Here we provide details of the derivations of our approximation for T and of Lemma 2 Whenever possible, we leave implicit that all expressions for ' in this appendix will be approximations and use the symbol for equality for simplicity.
We begin by taking the approximation of Equation 8 that
T ~ Exp
AΦ
4
AΦ
TT
(28)
where the expectation is taken all M x matrices T satisfying T - M1, with the uniform measure. It turns out that we can equivalently average over all all M x n matrices with a mean- zero i.i.d. Gaussian measure each element, without changing T. To this, note that this equation is symmetric under right-multillication of 4 by arbitrary n X invertible matrices R:
AΦ Φ ( AΦb
-1 T. A&R TR (TTAA -1 T
(29)
Letting R always be the (#-dependent) matrix that orthogonalizes the columns of + (i.e. 4 R R = MI,), one can see that, no matter the distribution of 4 in Equation 28 it holds
T. where & is the orthogonalized version of 4. The expectation can thus equivalently be taken over any distribution that induces the same distribution over the orthogonalized 4,. in particular, the uniform measure on orthogonal & can be interchanged with the standard Gaussian measure. Moving forward, we will exploit this equivalence and assume that each element of $ is sampled i.i.d. from (/0, 1). This assumption will largely remain in the background, but will be useful later.
that Eg AΦ AA) ΦT] = E+ A& (
We now evaluate T, starting with the off off-diagonal elements. We observe that
E+ AΦ UT ΦT] Ex AU & ($"AE) &TU].
(30)
where U is any orthogonal M x M matrix. Defining U(m) the matrix such that U(m) (m) 8at
26 noting that ((m) Am(m) A, and plugging U as in Equation 30 we find that
T ((u(m) (U(m)
(-1)damm +55m Tab
(31)
By choosing m a. we conclude that Tas = ifa
To evaluate the diagonal elements of T, we consider augmenting eigensystem with new "test eigenmode" with eigenvalue X, as described in the text and formalized in Equation 9 To proceed, make the core assumption that Tx T when n, M 1 19 This assumption, combined with the symmetry T T whenever Xÿ, implies that T. T (M (M--1) ())+)(++1)l==- Therefore, to evaluate T, it suffices to evaluate T
(M+1))M++) function of X.
Empirically, see that this approximation holds already for realistic values of n and M used in neural experiments.
16

---

Under review as a conference paper at ICLR 2022
We now manipulate the expression for T to isolate T (M+1)(M44) Using the Sherman- Morrison matrix inversion formula, we obtain
( *+ = (x"A4 + ) -1
A(TAAR) 06" (Φ" (4)
(32)
( AΦ
1 + AΦ (Φ7 A4) Φ
and inserting this into the full expression for T gives
A0 ( + AΦt + =x00") -1
Tt (M++1)04+1) = EE,
X2 T5 Φ AΦ) -1 6 27
AΦ T (x" AΦ) -1
= Ex.
Φ
1 A
(
(33)
A
Es.
A +
Ex .b
x C(+.))
where (b) = Φ T A
Φ
is a nonnegative scalar.
We now argue that, for realistic values of M, n, and {Ai we can simply replace ((..b) by its mean. We first note that, because 2/(A + C)) is convex, we can use Jensen's inequality to find that
A
E +
(34)
A + ((+
x+C
where we have defined Č = Ex.s ((
Some algebra also yields the fact that
{(C(+,)) -O) + (C(* C)2
(35)
X C
X+C
C)+
(1 C)²
for ()) 2 0, which, after taking an expectation, gives us the upper bound that
Var (()
A
Ex d
A ())
X X+C
(A + C)2
(36)
Var ($
X X+C
C2
Armed with the bounds of Equation 34 and Equation
36 we can replace (+ by C in the last [C(
C This will be nontrivial to show that it holds in a caricature of realistic problem. In practice, often find that the NTK spectrum is dominated by a few large eigenvalues with long tail of small eigenvalues (Figure 15] To model this sort of spectrum, let p N with p & n M, and suppose
line of Equation 33 if we can show that Var Var..o[C( in general, but we can easily
Ao
if Sisp
A
(37)
fp+i<iI M
M-P
17

---

Under review as a conference paper at ICLR 2022
with do >> X/(M p). The kernel matrix is given by
4 AΦ
A +
Σ 1=++
M
X
~ Σ
00 + XIm,
(38)
M
1=1
where Φ; the i-th row of & and have made an approximation using the central limit theorem assuming that & is random with entries sampled i.i.d. from (O, 1). This kernel matrix has large, (Ao) eigenvalues and n p remaining eigenvalues order X. Its inverse therefore has small eigenvalues and n similar large ones of order 1/X'. Letting {&, ( be these inverted eigenvalues, we have that
C (2,4
(39)
A4)
Φ
Li=1 S
where (x; )= are the components of á on each of the kernel eigendirections. For typical {æ; )==1 sampled i.i.d. from (0, 1), the denominator approaches (n -p)X by the central limit theorem, and thus reach our desired conclusion that ((*.4) 1/((n p)X) is approximately deterministic. More precisely, we find
Ex Φ [((
~
1 (n (n-p)X²
Var c)+ (n (n- (N)))
3
(40)
from which we see that
Var ob ()
(41)
C
which approaches zero when >> p. as desired.
This argument used somewhat unrealistic kernel eigenspectrum, but numerical experiments show that ( is approximately deterministic even for real eigenspectra (Figure F4). We leave the analysis of ((#.6) for realistic kernels for future work.
10a
/ (TJ/EN E[C]
10a
10a
10-1
10-2
100
101
102
n
Figure F4: For NTK eigenvalues on the 7-sphere, Var (c{+4) < C for large n. The statistic
Var [C( /C + 0 is calculated for various n using 100 samples of & Φ with the 7-sphere eigenvalues up 6.
Replacing (b)))) by constant C yields our final approximation for T, given in Equation 11 We note that, though this constant C is roughly the mean of ($..)) we circumvent deriving an explicit expression for this mean by instead using Theorem to fix C.
F.1 PROOF OF LEMMA 2
Here provide proof of the Lemma 2 which states several properties of the constant C' defined by Equation]] 11 As stated in the Lemma, these properties assume {A: MM ordered from greatest to least.
18

---

Under review as a conference paper at ICLR 2022
Property (a): C = when 0, and C when M.
Proof. Because Li=1 A,+C* for given The first statement follows by inspection, and the second follows by inspection given our assumption that all eigenvalues are strictly positive.
A, is strictly decreasing with C for C 2 there can only be solution
Property (b): is strictly decreasing with
Proof. Differentiating the constraint on C' with respect to yields
A dC'
Σ
1,
(42)
(Ag + C)² dn
giving
dC
X
<..
(43)
dn
A C)2
Property (c): C S n-t Ei d for all & {o,..., n n 1
1
Proof. n =EE A < + Ee J. The desired property follows.
Property (d): C 2 de - 1) for all l MM.
Proof. We consider replacing X; with de i S and 0 if Noting that this does not increase d
any term in the sum, we find that = Em X+C 2 Ei xrtC A,+0 follows.
de fxg
The desired property
G SECOND-ORDER STATISTICS OF T(D)
G. PRELIMINARIES
Here we derive expressions for the second-order statistics of T(D) These derivations make no further approximations beyond those already made in approximating T.
We begin a calculation that will later be of use. Differentiating both sides of the constraint on C' in Equation II with respect particular eigenvalue, find that
M d
M
2 dc (1j C22 ddi
Σ j=1
Σ 3=1
+ "A+ = 0,
(44)
dA
+
yielding that
dC
C g(>x + CO2*
M
X (A3 + C)2²
where
= Σ
(45)
dA;
j=1
We now factor (P) into two matrices as
(P) AZ,
where
AΦ
-1 T
(46)
Unlike (D), the matrix Z has the advantage of being symmetric and containing only one factor of A. Our approach will be to study the second-order statistics of which will trivially give these approximate the mean of Z
statistics for (P), From Equation 11
E. [ (A -1
(47)
19

---

Under review as a conference paper at ICLR 2022
We also define modified matrix Z + 40"UFAA ) x2, where U is an orthogonal M
M matrix. Because the measure over which & is averaged is rotation-invariant we can equivalently average over + Up with the same measure, giving
Ex [10
Eg
Φ (
&-U
Ex UUZUU U + CTM)
(48)
It is similarly the case that
Ex (Z ( say (Z (k)e
E. (UTZU), ij (U ZU) ké
(49)
Our aim will be calculate expectations of the form Egg Zey Zee] With clever choice of U, we can now see that most choices of the four indices will make this expression zero. We define
U(m) dat(1 20am) and observe that, because A is diagonal, (U()))AAUm)) AU(m) A and thus Z ((((m)) Z. Equation 49 then yields that
E+ Zig Ziel = (-1) Simm +.5m +8 them Ex [Zi Zie),
(50)
from which it follows that Ex Ziy Zae] = if any index repeated an odd number of times. light of the fact that Zi Zys, there are only three distinct nontrivial cases to consider:
1. Ex Zu).
2. E4 [Z Zzy] with i * j. and
3. E& [yy with * j.
We stress that we are not using the Einstein convention summation over repeated indices.
G.2 CASE STUDIES
Cases and We now consider differentiating Z with respect a particular element of the matrix
A. This yields
dZv
-- : (Φ)
2,0% (Ø"AΦ) Φt -Zi; Zuer
(51)
dAjk
where di is the i-th row of 4. This gives us the useful expression that
d Ex. [Z].
Ex. Zee)
(52)
dAjk
We now set & = i and evaluate this expression using Equation 47
concluding that
Ex (2 Ex ZZ = d
di, ( (x+tc) = (A++ C)2
1
bij + o(>, hcp).
C
(53)
Cov (Zi Ziy] = Cov Ziij Zyd g(); + Cy
(54)
We did not require that * j. and so Equation 53 holds for Case as well as Case 2.
Case 3. We now aim to calculate Eq (Z Zin] with i * j. We might hope use Equation 52 calculating E+ Z, but this approach is stymied by the fact that we would need to take derivative with respect Ai only have approximation for Z for diagonal A. We can circumvent this by means of U)) From the definition of (U)) find that
20

---

Under review as a conference paper at ICLR 2022
d
(
dUji
U=1
=
T
AΦ)
21100 + toYi 05 (Φ" Aa) Φj [
= x4) (Z) + 1 (55)
Differentiating with respect to both U:j and U with opposite signs ensures that the derivative is taken within the manifold of orthogonal matrices. Now, using Equation 48 we find that
d
d dUzi))
d
Ex (V))
(A (IN)CIN)-'U
dUi
du,
U=
U U=
(56)
A+C
+C+
Taking the expectation of Equations 55 plugging in Equation 53 for the squared off-diagonal ele- ment, comparing to 56 and performing a bit of algebra, we conclude that
C Zz (A, ( a(> +C CC2
(57)
and that Zie, Zij are anticorrelated with covariance
C
Cov ZZ,, Zjyl
(58)
q(A; + C)2(A) +0²
With the use of Kronecker deltas, combine Equations 54 and 58 into one expression covering all cases. As can be verified by case-by-case evaluation, one such expression is
C (ō + 6:0 - -ky5ke) q(>: + ()) +C]c
Cov [Zij Zue]
(59)
Using the fact that T(P) A:Zij. obtain the elementwise covariances of (P) given in Equation
13
G.3 DERIVING AN EXPRESSION FOR MSE
Mean MSE is given by E(ʃ) = ( v) = v V' Im) V'E,, where and are the eigenfunction coefficients of the true and learned functions and we have defined E (T(()D) IM) (T) In)) We derive Equation 15 as follows:
21

---

Under review as a conference paper at ICLR 2022
M
Ei =
(D) kii
dis)
(I -85k)
M
T
(D)
(
E
E
- E T (D)
+di
ki
X
C
A
6,
6sk
g(1, + +)3)
* +1+
(A + +)2
(60)
64
A
C
Σ
M
A
CA.
+
g(A CJ²
+C)
k=1
C
2
nC
qC²
A C
a(A: + C)2
q(A,
aA + C)22
Though is not apparent a glance, this expression for MSE fact equivalent the main result of Borddloo et al. (2020) with ridge parameter of zero. To obtain their expression from ours, substitute π + p. C t/p. - p²/t- p²y/t², and v X Given that our derivations are quite different they provide one using the method of characteristics and one using the replica trick from statistical mechanics that both directly yield final approximate expressions, while ours first derives approximation with one unknown parameter C' and then later determines C with the no-free-lunch theorem - it is interesting that we nonetheless recover their results. We note that our results for other second-order statistics besides MSE did not appear in this or any other prior work.
G.4 SECOND-ORDER STATISTICS CAN BE WRITTEN STRICTLY TERMS LEARNABILITY
As final theoretical note, observe that expressions for transfer matrix covariances and MSE can all be written strictly in terms of the modewise learnabilities L; ميية The fact that this is possible supports our claim that modewise learnabilities are quantities of fundamental theoretical importance to kernel regression. We begin by noting that
M Cq = Σ
n1
and
Lm f.m).
(61)
With these expressions in hand, we can quickly see that
Cov T (D) (D) = - (
(8:r000 + 5:005r - d.y
(62)
ΣM Cm (1 - -mm)
and
E ΣM Lm
(1 L.)2.
(63)
Σm Lm (1- Lmm))
These expressions allow one to more clearly see the effects of the model's inductive bias. For example, in light of the fact that C, E [0, 1). Equation 62 shows that Var T(() is larger the higher the learnability of the "learned mode" and the lower the learnability of the "target mode" j. meaning that low-learnability modes tend to be mistaken for high-learnability modes. Since the model tends to err towards beghbactrnability modes, we thus expect that the learned function will tend to be spectrally biased, placing outsize weight in more learnable modes.
22

---

Under review as a conference paper at ICLR 2022
One recurring quantity in these expressions is Li - Li), which is zero for L, 0, 1 and maximal at L; = .5. Intuitively speaking. describes the rate at which a mode "currently being learned" with increasing can be seen from the fact that
dC;
L1(1 - fui Σm= Lm - fm)
(64)
dn
This equation states that a new unit of learnability (i.e. a new data point) is divvied up among all the eigenmodes in proportion (1 C.).
H EXPERIMENTAL DETAILS
We conduct all experiments using JAX, performing exact NTK regression with the Neural Tan- gents library (Novak et al.) 2019) built atop it. For the dataset sizes we consider this paper, exact NTK regression is typically quite fast, running in seconds, while the training time of finite networks varies from seconds to minutes and depends on width, depth, training set size, and eigenmode. In particular, described by Rahaman et al. (2019), lower eigenmodes take longer train (especially when aiming for zero training MSE as we do here).
Unless otherwise stated, experiments used four-hidden-layr ReLU networks initialized with NTK parameterization (Sohl-Dickstein et al. 2020) with o.,, = 1.4, Ø, = .1. The tanh networks used generating Figure instead used dw 1.5. Experiments on the unit circle always used learning rate of _5, while experiments on the hypercube and hypersphere used learning rate of .5 or .I depending on the experiment. While higher learning rates led to faster convergence, they often also gave qualitatively different generalization behavior, in line with the large learning rate regimes described by Lewkowyez et al. (2020). Means and lo error bars always reflect statistics from 30 random dataset draws and initializations (for finite nets), except for the nonmonotonie MSE curves of Figure All which used 100 trials. We emphasize that the "no free lunch" experiment Figure) used only single trial.
23

---

Under review as a conference paper at ICLR 2022
I
NTK EIGENVALUES ON EXPERIMENTAL DOMAINS
Unit Circle
8d Hypercube
7-sphere
10
10-1
10-1
10-2
10
10
1
0..0
10a
10a
multiplicity
10a
10a
102
100
0
10
10a
0
10
k 10a
10
Figure 15: Eigenvalues decrease with increasing for all three domains, the manifestation of an inductive bias towards smoother functions. All eigenvalues are calculated with the NTK of 4L ReLU network described in the text. (A) NTK eigenvalues for k for the discretized unit circle (M = 256). Eigenvalues decrease as increases except for a few near exceptions at high k. (B) NTK eigenvalues for the 8d hypercube. Eigenvalues decrease monotonically with k. (C) NTK eigenvalues for the 7-sphere up to k = 70. Eigenvalues decrease monotonically with k. (D) Eigenvalue multiplicity for the discretized unit circle. All eigenvalues doubly degenerate (due to cos and sin modes) except for = 0 and = 128. (E) Eigenvalue multiplicity for the 8d hypercube. (F) Eigenvalue multiplicity for the 7-sphere.
24


Reviews:
[{"review_id": "vxodXAItVf-", "reviewer": "Reviewer_7tiq", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "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 topic of the paper which is on the NTK approach of analyzing generalization error of neural networks is interesting. The paper continues the line of work of Bordelon et al 2020 which seems a promising direction. Moreover, the paper is well structured and has plenty of simulation results. However, on the theoretical aspect, I believe the paper can be improved.\n\nI especially found the problem setup section of the paper and its notation hard to read. I think the theoretical results of the paper is a bit incremental with respect to the Bordelon et al. 2020 and Canatar et al. 2021. In particular, Theorems 1 and 2 demonstrate simple facts and have very short proofs. Moreover, the setup of the paper is for finite set $\\mathcal{X}$ with $M=|\\mathcal{X}|<\\infty$ with data sampled from a uniform measure. Although in page 2 it is promised that for non-uniform measures and continuous sets $\\mathcal{X}$ results will later be explained, no such analytical explanation is provided except for a note in the simulations section in page 8. The justification for the reduction of output dimension to m=1 in page 3 is also not entirely clear. \n\nIn the conclusion section, it should be noted that the results of the paper concern the generalization property of neural networks in the “infinite width” regime, and that the paper merely conjectures that the same theory holds for finite width networks as well.", "summary_of_the_paper": "The paper examines the eigenvalues of a neural network’s “Neural Tangent Kernel” to analyze its generalization performance in the infinite-width regime. It conjectures that the same results will also apply in the finite width regime as well. By analyzing kernel regression and by defining a measure as the “learnability” of a given target function, the paper proves a “no-free-lunch” theorem which implies that improving a network’s or kernel's generalization for a given target function must worsen its generalization performance for its \"orthogonal functions\". The paper then analytically predicts two phenomena: worse than chance generalization for hard functions and non-monotonic error curves in a small data regime. It also provides some simulations to corroborate the analytic results.", "summary_of_the_review": "I am not very familiar with the recent prior work that this paper cites and builds upon its approach and I have not completely checked the mathematical correctness of the claims of the paper. But, overall, given the importance of the problem analyzed by the paper, i.e. generalization performance of neural networks using NTK approach, and due to mix of theoretical results of the paper with empirical results, I am inclined towards accepting the paper.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "rbaOXP6Jb6D", "reviewer": "Reviewer_gb7t", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 5, "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": "Strength\n\nThis paper studies generalization of deep neural networks, a central topic of theoretical research in deep learning. This paper is written well and easy to follow.\n\nWeakness\n\nMy major concern is that the key findings of this paper are either not novel which have been revealed in previous works, or lack comparison with existing works so it is unclear how significant the results are. \n\nIn particular, (1) the finding that target functions corresponding to fewer leading eigenfunctions of NTK are easier to learn have been revealed by the generalization bound in [a] (Theorem 5.1 of [a]). In addition, [b] shows that the empirical (training) loss drops fast when the target function lies on the subspace spanned by top-k eigenfunctions of the linear integral operator corresponding to the neural tangent kernel. \n\n(2) The “no-free-lunch” theorem presented as Theorem 1 is based on the new notation of “learnability” defined in equation (2), and it would be important to connect this new notation to existing works so that one could understand the significance of the results. For example, the pessimistic result of Theorem 1 could be connected to the result in Section 3.2 of [c], where it was proved that there exists a difficult test data set which fails the trained ReLU neural network (the difficult test data and the training data can be generated from the same target function).\n\nThere are some other issues, for example, only asymptotic analysis (the width of the neural network goes to infinity) is presented. Note that all the referenced works [a-c] are based on neural networks with finite width, which is the case closer to the practice.\n", "summary_of_the_paper": "This paper studies generalization capability of deep neural networks by the eigensystem of Neural Tangent Kernel (NTK). The findings of this paper include (1) target functions corresponding to fewer leading eigenfunctions of NTK are easier to learn (these target functions are learned faster); (2) a new “no-free-lunch” theorem characterizing a fundamental tradeoff in the inductive bias of wide neural networks: improving a network’s generalization for a given target function must worsen its generalization for orthogonal functions.", "summary_of_the_review": "While this paper studies an important topic of deep learning, generalization capability of deep neural networks, the key findings of this paper are either not novel or lack comparison with existing works. I suggest the authors perform a thorough literature review in the recent progress of theoretical research in deep learning, and then carefully place their work under the context of the literature.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "1: The contributions are neither significant nor novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "Y74X_Gm7KVB", "reviewer": "Reviewer_Mosm", "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": "- Section 2.1: In the opening part there is no assumption about independence of outputs (m of them). Judging by the claim on page 3 (the last paragraph), the paper does assume outputs are independent? Otherwise, I fail to see how the problem simplifies to m = 1. To see that these kernel-based problems are quite different, please check out \"On learning vector-valued functions\" by Micchelli and Pontil (2003).\n- Figure of merit: The inner product in Eq. (2) is cosine similarity and should be in [-1, 1]. Unless one takes the absolute value, I fail to see how this quantity is bounded in [0, 1]?\n- Section 2.3: This section appears to be a review of kernel methods rather than a novel theoretical contribution. In particular, it does not appear to depend on any assumptions or specifics of neural tangent kernels. If so, then this should be contrasted relative to prior work on kernels and eigendecomposition of kernel operators. For example, \"On the mathematical foundations of learning\" by Cucker & Smale (2002) or \"Reproducing kernel Hilbert spaces in Probability and Statistics\" by Berlinet & Thomas-Agnan.\n- Section 2.5: The discussion immediately after Lemma 2. This is about the dependence on the sample size and, thus, not sure why this is specific to neural tangent kernel? In kernel methods the hypothesis will concentrate around the target as the sample size increase. There are numerous bounds on this and prior work has also covered the spectral tail, interpolation, etc (see \"Just Interpolate: Kernel Ridgeless Regression Can Generalize\" by Liang & Rakhlin or \"Optimal Rates for the Regularized Least-Squares Algorithm\" by Caponnetto & de Vito). \n\nThe empirical analysis is interesting and should have been the main focus of the work. In this regard, the ablation study with input spaces that have the closed form expressions for eigenfunctions is quite informative. The observation that even for networks with only 20-unit widths the correlations persist is promising.", "summary_of_the_paper": "The paper aims at characterizing the generalization ability of a neural network via the spectral properties of the neural tangent kernel. ", "summary_of_the_review": "The paper should have focused on its strengths which is the empirical study that links the NTK spectrum to generalization in neural networks. The theoretical results apply to kernels in general and, thus, do not see much novelty in this regard. The related work does not adequately cover prior developments in kernel methods and fails to place the claimed theoretical contributions within this scope.\nI would recommend a major revision with a proper review of prior work on kernels. The focus of the paper should be empirical and presentation of its empirical findings should receive more attention/pages. I also fail to see sufficient theoretical contribution relative to prior work on kernel methods.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "31iK7bz2rNW", "reviewer": "Reviewer_q2g8", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "This paper provides a really nice theoretical analysis of generalization in the setting of kernel regression. The metric of \"learnability\" is intuitive *and* useful, and the new no-free-lunch theorem provides new insight into the relationship between the size of the training set and the success of regression. In particular, it explains how the inductive bias of the kernel relates to the properties of the function that is trying to be learned.\n\nI think a major weakness of the paper is the desire to extend the regime of these results to make claims about deep learning. In particular, deep neural neural networks are only kernel machines at infinite width, and we expect deviations from this limit for realistic finite width networks. It's well known that the kernel for finite width networks is not fixed and evolves during training, so it's rather hard to assess the relevance of the paper's results for the models that the authors really want their results to apply to (namely, neural network models). In addition, for these finite width networks, the eigenspectrum also would shift, and thus the notion of which modes are large may also become complicated.\n\nRelatedly, the specific experiments performed are on very artificial datasets. That certainly can be fine -- the results illustrate the validity of the kernel regression results(!) -- but it also gives me pause with the claims made about deep learning in general. One particular problem is that the spectrum of eigenvalues for realistic data often obeys a power law. (See e.g. some discussion in [Explaining Neural Scaling Laws](https://arxiv.org/abs/2102.06701), or just check it explicitly on MNIST or FMNIST with a few lines of code.) This seems to be an essential inductive bias of realistic datasets. Presumably, given the no-free-lunch theorem, to make claims about realistic deep learning scenarios we'd need to understand (a) what an eigendecomposition of typical functions we want to learn looks like and (b) how kernel regression solutions behave when the data has a power law spectrum. I suspect that there are important differences as compared to learning an eigenfunction on an artificial dataset. Along these lines, it seems that the most relevant question is why is the inductive bias of fully-connected networks, which could be assessed by looking at the particular combinations of parameters and activations that make up the NTK, often useful for learning and generalizing the datasets and functions that we typically care about for AI function approximation tasks.\n\nFinally, I am particularly bothered by the discussion finite width networks in the abstract, introduction, and final paragraph before the conclusion. Since finite-width neural networks are not kernel machines,  the first-principles theory of this paper can only approximately apply to them. I think the experiments at finite width in this paper -- primarily in Figure B2 of the supplement -- are not sufficient to support the various claims made about finite-width networks. First, as described above, it's not clear that the learning tasks are particularly realistic. Second, it's now pretty well known that the relevant quantity with which to compare the width of the network to assess the validity of the infinite-width limit is the depth of the network. Thus, simply stating that their experiments agree for \"networks as narrow as width 20\" is not particularly helpful or scientifically accurate. A width 20 network of 1 layer might be very much like kernel regression and be in a regime of applicability of their results, but a width 20 network of 20 layers will definitely not be. Of course, the relevant question is whether for typical width and depth combinations whether their results are still useful. But I think this is really hard to assess given the experiments are also on unrealistic data and learning tasks.\n\nOne minor comment: I wish the authors would compare their results more directly to the analysis of the Canatar et al. 2021 paper they cite. I understand that the no-free-lunch theorem, the learnability measure, and the analysis of the learning transfer matrix are new here, but both works purport to give a first-principles theory of generalization by studying the kernel eigenspectrum, and I would appreciate a deeper discussion of the connection.\n\nA tiny comment: It would be nice to have more discussion of what Theorem 2 means after giving it. (But I know that space constraints makes things difficult.)", "summary_of_the_paper": "This paper provides a novel theoretical account of generalization for kernel regression. To do so, the authors study a matrix built out of the kernel eigensystem evaluated on the training set that they call the \"learning transfer matrix,\" and which relates the decomposition of the true function in the eigenbasis to the decomposition of the learned function in the eigenbasis. In other words, this matrix characterizes the kernel regression solution in the eigenbasis. By making a number of approximations, they are able to find a closed-form expression for this matrix and study its first and second order statistics. A main conclusion from this analysis is that functions are more learnable by kernel regression if they have more weight in higher eigenvalue modes.\n\nMoreover, the authors also introduce a new metric, which they call \"learnability,\" that they use to prove a new no-free-lunch theorem whose content is that when averaging over a complete basis of functions the learnability is independent of the kernel. This means that the choice of kernel should be tailored to the details of the function being learned in order for kernel regression to succeed. A related result is that there are some functions for which the kernel regression solution generalizes worse than simply outputting \"0\" on data outside the training set, i.e. for which the solution fails to generalize at all.\n", "summary_of_the_review": "On the one hand, this is a really nice theoretical paper about generalization for kernel regression. I think the results are useful, intuitive, correct, and bring new insight that let us understand better how kernel regression works. On the other hand, I do not think the analysis supports that this is a first-principles theory of generalization in deep learning. The results may very well be relevant for explaining generalization in deep neural networks, but the theoretical analysis and experimental evidence for that are not particularly convincing as of yet.\n\nMy recommendation that this is marginally below the acceptance threshold is based on the framing of the paper and statements that about deep learning that are not as careful as the really nice analysis of kernel regression is. If some of these statements are revised (or perhaps supported with more evidence), and/or if there's more discussion of when they expect their results to apply to DNNs and when they expect it to break down, I will substantially increase my score and recommend an acceptance.\n\n### After Author Responses\n\nThe authors have addressed a number of my concerns, and I have updated my score accordingly.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "1: The contributions are neither significant nor novel."}, "extra_text": {}}]

Author rebuttal:

Meta-review: *Summary:* Study generalization in kernel regression discussing the NTK case and experiments on finite width nets. 

*Strengths:* 
- Mix of theoretical and empirical results in an important topic. 
- Advances a promising recent line of work. 

*Weaknesses:* 
- Concerns about novelty and lack of comparison with existing works. 
- Concerns about insufficient contextualization of new notion of learnability. 
- Concerns about scope of results in relation to claims. 

*Discussion:* 

Reviewer gb7t (3) found their concerns about lack of novelty and comparison with prior works not sufficiently addressed in the authors’ responses. 7tiq (6) found the line of investigation promising, but also issues with presentation and found the theoretical results incremental. Mosm (5) finds that the theoretical part pertaining kernels does not offer much novelty and that the paper should have focused on the empirical study that links the NTK spectrum to generalization. q2g8 (8) confidently considers this a good paper. In their view it provides a nice theoretical analysis of generalization in the setting of kernel regression and the metric of learnability intuitive. However, they also found that the detests of the experiments are very artificial and problematic the desire of the article to extend the regime of the results to make claims about deep learning. 

A the end of the discussion period, the official reviewer ratings are mixed 3,5,6,8, indicating various strengths and weaknesses (also in case of the most favorable reviews). From the reviews and discussion, I infer that the topic is worthwhile and relevant, but at the same time that the paper might not be sufficiently convincing in its current form. Therefore I lean to reject the paper. To arrive at a clear conclusion, I consulted two additional researchers. 

*Additional assessment 1:* 

The first additional assessment found the work 'underwhelming' but admitted there is a chance they might not have fully understood the work. 

*Additional assessment 2:*  

The second additional assessment provided following comments: The paper's first contribution (conservation law), I didn't see it elsewhere but I think it's quite expected. The testing performance of low-frequency target functions and high-frequency target functions are averaged. Thus the average performance is constant which is independent on the kernel. However, in practice, kernel learning performs well because real target functions have low frequency. And the very high-frequency functions are unrealistic. 

About the paper's second contribution, I think the paper needs to explain how the result is different from Bordelon et al. (2020). I noticed that the method they use is different but the result seems quite similar. The paper also consider noiseless case and gives an approximation for MSE. 

Also the paper should explain more about the approximation being used. For example, how much error the approximation introduce and how the approximation is different from Bordelon's approximation. I see that in the proof Φ is approximated by a matrix where each element is standard Gaussian. For me I can't understand why the approximation is reasonable. 

I read through the reviews and rebuttals. I didn't see the discussion of the issue of approximation. But I think it's a major issue and the approximation is a very strong assumption. The appendix states: "we have made an approximation using the central limit theorem assuming that Φ is random with entries sampled i.i.d. from N (0, 1)". Here Φ is the matrix of eigenfunctions. Hence it is not clear how to apply the central limit theorem. 

*Conclusion:* 

I conclude that although the paper presents some interesting ideas on a relevant subject, it still has much room for improvement. Hence I recommend to reject this article. I encourage the authors to revise taking the above comments into consideration.
Decision: Reject