NEURAL TANGENT KERNEL EIGENVALUES ACCURATELY PREDICT GENERALIZATION
Year: 2021

Abstract:
In many cases, infinitely-wide deep neural networks are equivalent to kernel regression 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 a new theory predicting the generalization of kernel regression. Our theory accurately predicts not only test mean-squared-error but all firstand second-order statistics of the 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 kernel regression: improving 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 networks in the infinite-width limit, we experimentally find that its predictions are accurate for wide finite networks.

heading: 1 INTRODUCTION
text: Understanding and predicting a machine learning model’s generalization to unseen data is a central goal of machine learning theory. For a given class of model, one would ideally want a simple picture of a model’s inductive bias, identifying the set of functions on which a given model will generalize well and those on 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 a basic conservation law describing the inductive bias of kernel regression (Theorem 1). This law states that any kernel has a fixed budget of a 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. As a consequence of this conservation law, we prove that for every kernel, there exists a target function on which kernel regression generalizes worse than chance (Corollary 1), and we provide a recipe to construct such functions.
• We derive a new theory of generalization for kernel regression, culminating in analytical expressions for all first- and second-order statistics of the learned function (Equations 11 and 13). This theory extends the spectral picture of kernel regression revealed by Bordelon et al. (2020) and Canatar et al. (2021). We conclude from our theory that, in realistic settings, most kernel eigenfunctions have the counterintuitive property that MSE increases as examples are added to a small training set (Section 2.7).
• We empirically verify all our results on synthetic datasets using both exact kernel regression and deep networks of width 500 trained with gradient descent. We find that our conservation law and analytical expressions for generalization performance hold to an excellent approximation even for wide finite networks, and we observe worse-than-chance generalization and increasing MSE as predicted. We find that our theory’s core predictions remain
fairly accurate even down to width 20 for depth-four networks, suggesting it is a promising starting point for understanding generalization in practical architectures.

heading: 1.1 RELATED WORK
text: 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, Sollich (1999) and Vivarelli & Opper (1999) 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., 2018a; 2019b;a; Liang & Rakhlin, 2020; Bietti & Mairal, 2019). Further noting that both kernel regression and deep learning can generalize well despite perfectly interpolating their training data, Belkin et al. (2018b) argued that “to understand deep learning we 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 is a significant advance over VC-dimension-based bounds inapplicable to overparameterized models, it only applies to a 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 infinite-width architecture (and in fact to any incarnation of kernel regression).
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 set, the network generalizes well on a larger and larger subspace of input functions. The natural 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-order 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 at the same results.
Our work is related to the well-known observation that neural networks have a “spectral bias” towards representing slowly-varying functions (Valle-Perez et al., 2018; Yang & Salman, 2019); in particular, the kernel spectrum picture clarifies that this bias is a 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;a; Xu, 2018; Cao et al., 2019; Su & Yang, 2019).

heading: 2 THEORY

heading: 2.1 A REVIEW OF KERNEL REGRESSION
text: Consider the task of learning an m-element function f : X → Rm given a set of n unique training points D = {xi}ni=1 ⊆ X and their corresponding function values f(D) ∈ Rn×m. To simplify our analysis, we will let the domain X be discrete with size M ≡ |X | 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 →∞, our results easily extend to problems with continuous domain: for example, if M →∞ and we allow the points in X to approach a density equal to some desired measure over Rd, we recover the standard setting where the data are sampled nonuniformly from Rd.
We will use f̂ to denote the function learned by a neural network trained on this dataset. Remarkably, for an infinite-width neural network optimized via gradient descent to zero training MSE loss, this learned function is given by
f̂(x) = K(x,D)K(D,D)−1f(D), (1)
where K : X × X → R is the network’s “neural tangent kernel” (NTK) (Jacot et al., 2018; Lee et al., 2019), K(D,D) is the “kernel matrix” defined by K(D,D)ij = K(xi, xj), and K(x,D) is a row vector with components K(x,D)i = K(x, xi).1 We give a brief introduction to the NTK in Appendix C. Due to its similarity to the normal equation of linear regression, Equation 1 is often called “kernel regression.”2
Equation 1 holds exactly in the infinite-width limit of fully-connected networks (Lee et al., 2019), convolutional networks (Arora et al., 2019b), transformers (Hron et al., 2020), and more (Yang, 2019). Moreover, several empirical studies have shown it to be a good approximation for networks of even modest width (Lee et al., 2019; 2020). Our approach will be to study the generalization behavior of Equation 1, 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 to simply performing kernel regression with each of the m indices as a scalar target function and then vectorizing the results. For simplicity, then, we hereafter assume m = 1. The extension to m > 1 is 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〉 ≡ 1M ∑ x∈X g(x)h(x).
The first measure of quality is mean-squared error (MSE). For a particular dataset D, MSE is given by E(D)(f) ≡ 〈f − f̂ , f − f̂〉. Of more interest will be the expected MSE over all datasets of size n, given by E(f) ≡ ED [ E(D)(f) ] . We note that the inner product is taken over all X , including D,
even though f̂(x) = f(x) for x ∈ 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 f̂ of one such orthogonal function to f . Letting g : X → R be a function such that 〈f, g〉 = 0, we consider the mean and variance of the quantity 〈f̂ , 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 “learnability.” It is given by
L(D)(f) ≡ 〈f, f̂〉 〈f, f〉
, L(f) ≡ ED [ L(D)(f) ] , (2)
where L(D)(f) is the dataset-dependent learnability of the function f (“D-learnability”) and L(f) is its expectation over random data (“learnability”). 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 1: unlike MSE, both are bounded in [0, 1] (Lemma 1d), always change monotonically as new data points are added (Lemma 1e), are invariant to rescalings of f , and obey a simple conservation law (Theorem 1). Furthermore, expanding the inner product in the definition of E and noting that E(f) ≥ 〈f, f〉(1 − L(f))2, 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 MSE.
1Naively, Equation 1 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 t = 0 and redefining f̂t(x) := f̂t(x)− f̂0(x) 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.
2Interestingly, exact Bayesian inference for infinite-width neural networks yields predictions of the same form as Equation 1, with K being the “neural network Gaussian process” (NNGP) kernel instead of the NTK (Lee et al., 2018). We will proceed treating K as a network’s NTK, but our theory and exact results (including our “no-free-lunch” theorem) apply equally well to any incarnation of kernel regression, including RBF kernel regression and linear regression.

heading: 2.3 THE KERNEL EIGENSYSTEM
text: By definition, any kernel function is symmetric and positive-semidefinite (Shawe-Taylor et al., 2004). This implies that we can find a set of orthonormal eigenfunctions {φi}Mi=1 and nonnegative eigenvalues {λi}Mi=1 that satisfy
1
M ∑ x′∈X K(x, x′)φi(x ′) = λiφi(x), 〈φi, φj〉 = δij . (3)
For simplicity (and to ensure that K(D,D) is invertible), we will assume that K is in fact positive definite and λi > 0, an assumption that will hold in most cases of interest.3,4
We will now translate Equation 1 to this eigenbasis. First we decompose f and f̂ into weighted sums of the eigenfunctions as
f(x) = M∑ i=1 viφi(x), f̂(x) = M∑ i=1 v̂iφi(x), (4)
where v and v̂ are vectors of coefficients. Using this notation, MSE is E(D) = (v − v̂)2 and D-learnability is L(D) = vT v̂/|v|2.
Noting that K(x1, x2) = ∑M i=1 λiφi(x1)φi(x2), we can decompose the kernel matrix as K(D,D) = ΦT (D)ΛΦ(D), where Φ(D)ij = φi(xj) is the M × n “design matrix” and Λ = diag(λ1, ..., λM ) is a diagonal matrix of eigenvalues. The learned coefficients v̂ are then given by v̂i = 〈φi, f̂〉 = λiφi(D)K(D,D)−1ΦT (D)v. Stacking these coefficients into a matrix equation, we find that
v̂ = ΛΦ(D) ( ΦT (D)ΛΦ(D) )−1 ΦT (D)v = T(D)v, (5)
where T(D) ≡ ΛΦ(D) ( ΦT (D)ΛΦ(D) )−1 ΦT (D) is an M ×M matrix, independent of f , that fully describes the model’s learning behavior on a training set D. We call this fundamental quantity the “learning transfer matrix.” If we can determine the statistical properties of this matrix, we will understand the learning behavior of our model.
We also define the mean learning transfer matrix T ≡ ED [ T(D) ] . D-learnability and learnability are then respectively given by L(D)(f) = vTT(D)v/|v|2 and L(f) = vTTv/|v|2.

heading: 2.4 EXACT RESULTS
text: The following lemma gives basic properties of the quantities defined above.
Lemma 1. The following properties of T(D), T, L(D), and L hold:
(a) L(D)(φi) = T(D)ii , and L(φi) = Tii.
(b) When n = 0, T = T(D) = 0 and L(f) = L(D)(f) = 0.
(c) When n = M , T = T(D) = IM and L(f) = L(D)(f) = 1.
(d) All eigenvalues of T(D) are in {0, 1}, all eigenvalues of T are in [0, 1], and so L(f),L(D)(f) ∈ [0, 1].
(e) Let D+ be D ∪ x, where x ∈ X,x /∈ D is a new data point. Then L(D+)(f) ≥ L(D)(f).
(f) For any i ∈ {1, ...,M}, ddλi T (D) ii ≥ 0, hence ddλiL (D)(φi) ≥ 0.
(g) For any i, j ∈ {1, ...,M}, i 6= j, ddλi T (D) jj ≤ 0, hence ddλiL (D)(φj) ≤ 0.
3By Mercer’s Theorem, one can also find the eigensystem of any kernel on a continuous input space X . 4We do not use the Reproducing kernel Hilbert space (RKHS) formalism in this work, but we note that, by
the Moore–Aronszajn theorem, the kernel K defines a unique RKHS.
Property (a) in Lemma 1 formalizes the relationship between the transfer matrix and learnability. Properties (b-e) together give an intuitive picture of the learning process: the learning transfer matrix monotonically interpolates between zero and IM as the training set grows — adding data never harms the learnability of any function. Properties (f-g) show that the kernel eigenmodes are in competition: increasing one eigenvalue can only improve the learnability of the corresponding eigenfunction, but can only decrease the learnabilities of all others. We prove Lemma 1 in Appendix D.
We now present our first major result.
Theorem 1 (“No-free-lunch” theorem for kernel regression). For any complete basis of orthogonal functions F , ∑
f∈F L(f) = ∑ f∈F L(D)(f) = n. (6)
The proof, which hinges on the intermediate result that Tr [ T(D) ] = n, is given in Appendix E. We note that this result is stronger than the ordinary “no-free-lunch” theorem for learning algorithms, which requires averaging over all target functions instead of merely an orthogonal basis (Wolpert, 1996). To understand the significance of this result, consider that one might naively hope to design a neural kernel that achieves generally high performance for all target functions f . Theorem 1 states that this is impossible: averaged over a complete basis of functions, all kernels achieve the same learnability. This exact result implies that, because there exist no universally high-performing kernels, we must instead aim to choose a kernel whose high-eigenvalue modes align well with the function to be learned. To our knowledge, this is the first exact result quantifying such a 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 poorly-aligned with the kernel’s inductive bias on which the model generalizes as bad or worse than it would by simply predicting zero on all unseen test points.
Corollary 1 (Negative generalization). There is always at least one eigenfunction φi for which L(φi) ≤ Lnaive(φi) and E(φi) ≥ Enaive(φi), where Lnaive and Enaive are the learnability and mean MSE given by a naive, non-generalizing model with predictions given by
f̂naive(x) = { f(x) x ∈ D 0 x /∈ D . (7)
This theorem follows from Theorem 1. We give a full proof in Appendix E. This negative generalization property will hold for any function with learnability less than or equal to n/M , including any weighted sum of eigenfunctions with this property.

heading: 2.5 DERIVING A CLOSED-FORM EXPRESSION FOR T
text: We will now derive an approximation for T and the second moments of T(D), ultimately yielding simple yet accurate expressions for L, E , and 〈f̂ , g〉. We sketch our method and state our results here and provide a full derivation in Appendix F.
We begin by noting that the expectation in T ≡ ED [ T(D) ] is essentially an expectation over a combinatorially large set of possible design matrices Φ(D), each of which has orthogonal columns. We replace this with an average over all M × n matrices Φ satisfying ΦTΦ = M1n, which we write
T = ED [ ΛΦ(D) ( ΦT (D)ΛΦ(D) )−1 ΦT (D) ] ≈ EΦ [ ΛΦ ( ΦTΛΦ )−1 ΦT ] . (8)
We can then readily prove by symmetry that the off-diagonal 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
Φ+ = [ Φ φT ] , Λ+ = [ Λ 0 0 λ ] , T+ = EΦ,φ [ Λ+Φ+ ( Φ+TΛ+Φ+ )−1 Φ+T ] . (9)
Using the Sherman-Morrison formula, we find that the new mode’s learnability is given by
T+(M+1)(M+1) = EΦ,φ  λ λ+ [ φT (ΦTΛΦ) −1 φ ]−1  = EΦ,φ[ λ λ+ C(Φ,φ) ] , (10)
where C(Φ,φ) ≡ [ φT ( ΦTΛΦ )−1 φ ]−1 is a nonnegative dataset-dependent constant. For large n
and realistic eigenspectra, C(Φ,φ) is distributed tightly around its mean, and so we can replace it with a constant, which we call C. We emphasize that C is the same for every eigenmode. Using Theorem 1 to obtain a constraint on C, we reach our ultimate approximation that
Tij = δij λi
λi + C , where C ≥ 0 satisfies M∑ i=1 λi λi + C = n. (11)
Using Lemma 1, we obtain the major result that
L(f) = 1 |v|2 M∑ i=1 λi λi + C v2i , (12)
with C given by Equation 11.
A function is thus more learnable the more weight it places in high eigenvalue modes. We show in Section 3 that Equation 12 is 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 {λi}Mi=1 ordered from greatest to least, the following properties hold:
(a) C =∞ when n = 0, and C = 0 when n = M . (b) C is strictly decreasing with n.
(c) C ≤ 1n−` ∑M i=`+1 λi for all ` ∈ {0, ..., n− 1}.
(d) C ≥ λ` ( ` n − 1 ) for all ` ∈ {n, ...,M}.
Properties (a-b), paired with Equation 11, paint a surprisingly simple picture of the learning process: as the training set grows,C gradually decreases, and eigenmodes are learned high-to-low asC passes each eigenvalue. Properties (c-d) provide bounds on C, which, in addition to then yielding bounds on learnability, can be used to furnish an initial guess when numerically solving for C.

heading: 2.6 SECOND-ORDER STATISTICS OF T
text: We now have an expression for the mean of T(D), but many quantities of interest, including MSE, depend on second-order fluctuations about that mean. In Appendix G, we show how, by taking a derivative with respect to Λ, we can obtain expressions for the second-order statistics of T(D) and, as a result, for MSE. Our main second-order result is that
Cov [ T
(D) ij ,T (D) k`
] =
Cλiλk (δikδj` + δi`δjk − δijδk`) q(λi + C)(λj + C)(λk + C)(λ` + C) , where q ≡ M∑ m=1 λm (λm + C)2 . (13)
Using Equation 13, we can study the admixtures of particular spurious modes in the learned function f̂ . For example, if f = φi and i 6= j, then we find that
E [ 〈f̂ , φj〉 ] = 0, E [ 〈f̂ , φj〉2 ] = Var [ T (D) ji ] =
Cλ2j q(λi + C)2(λj + C)2 . (14)
We note that E [ 〈f̂ , φj〉2 ] increases with λj , reinforcing our broad conclusion that the model is
biased towards high-eigenvalue modes. Finally, by noting that E(f) = ED [ |(T(D) − IM )v|2 ] , we can recover the expression of Bordelon et al. (2020) for MSE:
E(f) = vTEv, where Eij ≡ δij nC
q
1
(λi + C)2 . (15)
Our experiments corroborate existing evidence that this is an excellent approximation for MSE.

heading: 2.7 NONMONOTONIC MSE CURVES
text: Expanding E for small n, we find that
Eii ∣∣∣ n=0 = 1, dEii dn ∣∣∣∣∣ n=0 = ∑ j λ 2 j(∑
j λj
)2 − 2λi∑ j λj . (16)
The second equation implies that dEiidn ∣∣ n=0 > 0 for all modes i such that λi < ( ∑ j λ 2 j )/(2 ∑ j λj), 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 a bounded kernel on a continuous input space (for which M → ∞), an infinite number of arbitrarily low modes is inevitable due to the constraint that ∑ i λi is bounded
5. We therefore expect that there quite often exist functions for which a given neural network yields an MSE nonmonotonic with n. Figure A1 shows that experiments confirm this surprising first-principles prediction. We emphasize that this is a different, more generic phenomenon than that noted by Canatar et al. (2021), which required that f was either noisy or placed weight in unlearnable zero-eigenvalue modes.

heading: 3 EXPERIMENTS
text: 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) fourhidden-layer (4L) ReLU architecture with width 500. Because this model is FC, it has a rotationinvariant NTK (Lee et al., 2019). These experiments used three distinct input spaces X . For each, the eigenmodes of X can be grouped into degenerate subsets indexed by k ∈ N, with higher k corresponding to faster variation in space. In all cases, we find that as k increases, eigenvalues 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, see Appendix H.
Discretized Unit Circle. The simplest input space we consider is the discretization of the unit circle into M points, X = {(cos(2πj/M), sin(2πj/M)}Mj=1. The eigenfunctions on this domain are φ0(θ) = 1, φk(θ) = √ 2 cos(kθ), and φ′k(θ) = √ 2 sin(kθ), for k ≥ 1.
Hypercube. The next input space we consider is the set of verticies of the d-dimensional hypercube, X = {−1, 1}d, giving M = 2d. The eigenfunctions on this domain are the subset-parity functions φs(x) = (−1)s
T x, where s ∈ {0, 1}d is a vector indicating the elements of x to which the output is sensitive (Yang & Salman, 2019). Here we define k = ∑ i si.
Hypersphere. To illustrate that our results extend easily to continuous input spaces, we consider the d-sphere Sd = {x ∈ Rd+1|x2 = d+ 1}. The eigenfunctions on this domain are the hyperspherical harmonics (see, e.g., Frye & Efthimiou (2012); Bordelon et al. (2020)) which group into degenerate sets indexed by k ∈ N. The corresponding eigenvalues decrease exponentially with k, and so when summing over all eigenmodes to compute C and q, we simply truncate the sum at kmax = 70.
∑
∑
Predicting learnability L(D). We use both wide finite nets and exact NTK regression to learn several eigenmodes on all three domains and compare true learnabilities with our theoretical predictions. Our theory predicts true generalization behavior quite well (Figure 1). We further show that the k = 8 mode on the 8d hypercube has worse-than-chance generalization, an inevitable result of its low eigenvalue and Corollary 1. We note that finite networks and NTK regression give very similar results, supporting the validity of approximating networks with the NTK.
Universal form for learnability. We next fix n and plot learnability vs. eigenvalue for eight modes over each domain. In each case we find L(φ) ≈ λ/(λ + C), and by rescaling the eigenvalues (a symmetry which leaves Equation 1 invariant), we see that for any neural network learning problem with any training set size n, 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 as kernel regression (Figure 3). We use both models to learn a function on the discretized unit circle with M = 10 and sum the resulting D-learnabilities of each eigenmode. Unlike in our other experiments, we only sample D once for each n; even without the benefit of averaging over datasets, we find that total D-learnability is always conserved. Nonmonotonic MSE curves. We next confirm our first-principles prediction of nonmonotonic MSE curves at small n. We plot curves for four eigenmodes on each domain, three of which Equation 16 predicts will have positive dE/dn|n=0. MSE is indeed increasing as predicted (Figure A1). Agreement with narrow networks. Finally, we repeat the experiment of Figure 1B 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.

heading: 4 CONCLUSION
text: 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 predictive 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 a general framework for understanding their learning behavior, opening the door to the principled study of many other deep learning mysteries.

heading: A NONMONOTONIC MSE CURVES AT SMALL TRAINING SET SIZE
text: 0 2 4 6 n
0.0
0.5
1.0
1.5
2.0
( ) (
k)
A
Unit Circle
k = 6 k = 4 k = 2 k = 0
0 2 4 6 n
0.00
0.25
0.50
0.75
1.00
1.25 B 6d Hypercube
k = 6 k = 4 k = 2 k = 0
0 2 4 6 n
0.0
0.5
1.0
1.5 C
2-sphere
k = 6 k = 4 k = 2 k = 0
Figure A1: Our theory correctly predicts that, for low-eigenvalue eigenfunctions, MSE counterintuively increases as points are added to a small training set. (A-C) Generalization MSE of exact NTK regression (triangles) and finite networks (circles) when learning four different eigenmodes on each of three different domains given n training points. Theoretical curves closely match experimental data. Eigenmodes with higher k have lower eigenvalues and thus higher mean MSEs, and for k ∈ {2, 4, 6}, MSE even increases as n increases from zero. Dashed lines show dE/dn|n=0 as predicted by Equation 16.
B EXPERIMENTAL RESULTS FOR NARROW NETWORKS
0.0
0.2
0.4
0.6
0.8
1.0
1.2
( ) (
k)
A width k = 0 k = 1 k = 3 k = 8
B width 500 C width 200
20 22 24 26 28 n
0.0
0.2
0.4
0.6
0.8
1.0
1.2
( ) (
k)
D width 100
20 22 24 26 28 n

heading: E width 50
text: 20 22 24 26 28 n
F width 20
Figure B2: Theoretical learnability predictions remain accurate even for quite narrow networks of moderate depth. Plots show learnability vs. training set size for four eigenmodes of the 8d hypercube, learned with a 4L ReLU net with various widths. Except for changing width, these experiments are identical to those of Figure 1b. Theoretical predictions (solid curves) are the same in all plots. Dashed lines show learnability from a naive, nongeneralizing model; points below the line imply worse-than-chance generalization (see Corollary 1). (A) Infinite-width results using exact NTK regression. (B-F) Results for successively narrower finite networks. As width decreases, mean learnability increases slightly, and 1σ error grows. Despite this, mean learnabilities remain remarkably close to our theoretical predictions even at width 20.
0.0
0.5
1.0
1.5
2.0
( ) (
k)
A width k = 0 k = 1 k = 3 k = 8
B width 500 C width 200
20 22 24 26 28 n
0.0
0.5
1.0
1.5
2.0
( ) (
k)
D width 100
20 22 24 26 28 n
E width 50
20 22 24 26 28 n
F width 20
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 is plotted instead of learnability, these experiments are identical to those of Figure 1b. Theoretical predictions (solid curves) are the same in all plots. Dashed lines show MSE from a 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.

heading: C REVIEW OF THE NTK
text: In the main text, we assume prior familiarity with the NTK, using Equation 1 as the starting point of our derivations. Here we provide a definition and very brief introduction to the NTK for unfamiliar readers. For derivations and full discussions, see Jacot et al. (2018) and Lee et al. (2019).
Consider a feedforward neural network representing a function f̂θ : X → R, where θ is a parameter vector. Further consider one training example xwith target value y and one test point x′ and suppose we perform one step of gradient descent with a small learning rate η with respect to the MSE loss `θ ≡ (f̂θ(x)− y)2. This gives the parameter update
θ → θ + δθ, with δθ = −η∇θ`θ = −2η(f̂ − y)∇θf̂θ(x). (17)
We now wish to know how this parameter update changes f̂θ(x′). To do so, we linearize about θ, finding that
f̂θ+δθ(x ′) = f̂θ(x ′) +∇θf̂θ(x′) · δθ +O(δθ2)
= f̂θ(x ′)− 2η(f̂ − y) [ ∇θf̂θ(x) · ∇θf̂θ(x′) ] +O(δθ2)
= f̂θ(x ′)− 2η(f̂ − y)K(x, x′) +O(δθ2),
(18)
where we have defined K(x, x′) ≡ ∇θf̂θ(x) · ∇θf̂θ(x′). This quantity is the NTK. Remarkably, as network width6 goes to infinity, the O(δθ2) corrections become negligible, and K(x, x′) is the same after any random initialization7 and at 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 an arbitrary dataset, the network’s learned function is given by Equation 1. See, for example, Equations 14-16 of Lee et al. (2019)8.

heading: D PROOF OF LEMMA 1
text: Property (a): L(D)(φi) = T(D)ii , and L(φi) = Tii.
Proof. Using the fact that 〈φi, φi〉 = 1, we see that L(D)(φi) = 〈φ̂i, φi〉 = eTi T(D)ei = T (D) ii , where ei is a one-hot M -vector with the one at index i. The second clause of the property follows by averaging.
Property (b): When n = 0, T = T(D) = 0 and L(f) = L(D)(f) = 0.
Proof. When n = 0, Φ(D) has no columns, and thus T(D) = 0. The other clauses follow from Property (a) and averaging.
Property (c): When n = M , T = T(D) = IM and L(f) = L(D)(f) = 1.
Proof. When n = M , Φ(D) is a full-rank M ×M matrix. Inspection of the formula for T(D) then shows that T(D) = IM . The other clauses follow from Property (a) and averaging.
Property (d): All eigenvalues of T(D) are in {0, 1}, all eigenvalues of T are in [0, 1], and so L(f),L(D)(f) ∈ [0, 1].
Proof. From the definition of T(D), it is easy to see that T(D) = ( T(D) )2 . T(D) 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 L(f),L(D)(f) follow from the fact that, for any compatible vector z and matrix A, it holds that z
TAz zT z is bounded by the maximum and minimum eigenvalues of A.
Property (e): LetD+ beD∪x, where x ∈ X,x /∈ D is a new data point. ThenL(D+)(f) ≥ L(D)(f).
Proof. To begin, we use the Moore-Penrose pseudoinverse, which we denote by (·)+, to cast T(D) into a more transparent form:
T(D) ≡ ΛΦ ( ΦTΛΦ )−1 ΦT = Λ1/2 ( Λ1/2ΦΦTΛ1/2 )( Λ1/2ΦΦTΛ1/2 )+ Λ−1/2, (19)
where we have suppressed the D in Φ(D). This follows from the property of pseudoinverses that A(ATA)+AT = (AAT )(AAT )+ for any matrix A. We now augment our system with one extra data point, getting
T(D+) = Λ1/2 ( Λ1/2(ΦΦT + ξξT )Λ1/2 )( Λ1/2(ΦΦT + ξξT )Λ1/2 )+ Λ−1/2, (20)
where ξ is an M -element column vector orthogonal to the others of Φ. We now convert the pseudoinverse into an inverse with a limit, getting
T(D+) = lim δ→0+
Λ1/2 ( Λ1/2(ΦΦT + ξξT )Λ1/2 )( Λ1/2(ΦΦT + ξξT )Λ1/2 + δIM )−1 Λ−1/2.
(21) 6The “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 a convolutional network. 7(assuming the parameters are drawn from the same distribution) 8We note that there exists a different infinite-width kernel, called the “NNGP kernel,” describing a network’s random initialization, and this reference uses K for the NNGP kernel and Θ for the NTK.
We now use the Sherman-Morrison matrix inversion formula to find that
T(D+) = T(D) + lim δ→0+ δ
( Λ1/2ΦΦTΛ1/2 + δIM )−1 ξξT ( Λ1/2ΦΦTΛ1/2 + δIM )−1 1 + ξT ( Λ1/2ΦΦTΛ1/2 + δIM )−1 ξ . (22)
Because both ξξT and the inverted matrix in Equation 22 are positive semidefinite, we conclude that, for any M -vector z, it will hold that zTT(D+)z ≥ zTT(D)z. The desired property follows.
Property (f): For any i ∈ {1, ...,M}, ddλi T (D) ii ≥ 0, hence ddλiL (D)(φi) ≥ 0.
Proof. Differentiating T(D)jj with respect to a particular λi, we find that
d
dλi T
(D) jj = (δij − λjφ T j K −1φi)φ T i K −1φj , (23)
where φTi is the i-th row of Φ and K = Φ TΛΦ. Specializing to the case i = j, we note that φTi K −1φi ≥ 0 because K is positive semidefinite, and λjφiK−1φTi ≤ 1 because λjφiφTi is one
of the positive semidefinite summands in K = ∑ k λkφkφ T k . The desired property follows.
Property (g): For any i, j ∈ {1, ...,M}, i 6= j, ddλi T (D) jj ≤ 0, hence ddλiL (D)(φj) ≤ 0.
Proof. Differentiating as in the proof of Property (f) and using the fact that i 6= j, we see that
d
dλi T
(D) jj = −λj ( φTj K −1φi )2 , (24)
which is manifestly nonpositive because λj > 0. The desired property follows.

heading: E PROOFS OF THEOREM 1 AND COROLLARY 1
text: Here we prove Theorem 1, our “no-free-lunch” result, and Corollary 1, which states the existence of eigenfunctions that generalize worse than chance. We begin with the former.
Proof of Theorem 1. First, we note that, for any orthogonal basis F on X ,
∑ f∈F L(D)(f) = ∑ v∈V vTT(D)v vTv , (25)
where V is an orthogonal set of vectors spanning RM . This is equivalent to Tr [ T(D) ] . This trace is given by
Tr [ T(D) ] = Tr [ ΦTΛΦ(ΦTΛΦ)−1 ] = Tr[In] = n, (26)
which proves the desired theorem.
Proof of Corollary 1. First, we note that the naive, nongeneralizing model described in the theorem will always have a learnability ofLnaive(f) = ED [ n〈f,f〉 M〈f,f〉 ] = nM . As per Theorem 1, this is exactly the mean learnability of all eigenfunctions, so either all have precisely this learnability or else one has lower learnability. This proves the clause of the theorem specific to learnability.
To prove the clause specific to MSE, we now note that, as defined by Equation 1, kernel regression will always perfectly memorize the training data, so for both the naive model and kernel regression, MSE is given by
E(f) = 1 M ∑ x∈X\D (f(x)− f̂(x))2 = 1 M ∑ x∈X\D f2(x)+ 1 M ∑ x∈X\D f̂(x)2− 2 M ∑ x∈X\D f(x)f̂(x). (27)
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(L(f) − nM ), which must be nonnegative for at least one eigenfunction. Kernel regression therefore gives worse MSE than the naive model unless, as for the naive model, f̂(x) = 0 for x /∈ D.

heading: F APPROXIMATING T
text: Here we provide details of the derivations of our approximation for T and of Lemma 2. Whenever possible, we leave it implicit that all expressions for T 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 ≈ EΦ [ ΛΦ ( ΦTΛΦ )−1 ΦT ] , (28)
where the expectation is taken over allM×nmatrices Φ satisfying ΦTΦ = M1n with the uniform measure. It turns out that we can equivalently average over all all M × n matrices Φ with a meanzero i.i.d. Gaussian measure over each element, without changing T. To see this, note that this equation is symmetric under right-multiplication of Φ by arbitrary n× n invertible matrices R:
ΛΦ ( ΦTΛΦ )−1 ΦT = ΛΦR ( RTΦTΛΦR )−1 RTΦT . (29)
Letting R always be the (Φ-dependent) matrix that orthogonalizes the columns of Φ (i.e. ΦTRTRΦ = MIn), one can see that, no matter the distribution of Φ in Equation 28, it holds that EΦ [ ΛΦ ( ΦTΛΦ )−1 ΦT ] = EΦ [ ΛΦo ( ΦTo ΛΦo )−1 ΦTo ] , where Φo is the orthogonalized
version of Φ. The expectation can thus equivalently be taken over any distribution that induces the same distribution over the orthogonalized Φo; 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 N (0, 1). This assumption will largely remain in the background, but will be useful later.
We now evaluate T, starting with the off-diagonal elements. We observe that
EΦ [ ΛΦ ( ΦTUTΛUΦ )−1 ΦT ] = EΦ [ ΛUTΦ ( ΦTΛΦ )−1 ΦTU ] , (30)
where U is any orthogonal M ×M matrix. Defining U(m) as the matrix such that U(m)ab ≡ δab(1− 2δam), noting that U(m)ΛU(m) = Λ, and plugging U(m) in as U in Equation 30, we find that
Tab =
(( U(m) )T TU(m) ) ab = (−1)δam+δbmTab. (31)
By choosing m = a, we conclude that Tab = 0 if a 6= b. To evaluate the diagonal elements of T, we consider augmenting our eigensystem with a new “test eigenmode” with eigenvalue λ, as described in the text and formalized in Equation 9. To proceed, we make the core assumption that Tii ≈ T+ii when n,M 1 9. This assumption, combined with the symmetry T+ii = T + jj whenever λi = λj , implies that Tii = T + (M+1)(M+1)|λ=λi . Therefore, to evaluate T, it suffices to evaluate T+(M+1)(M+1) as a function of λ.
9Empirically, we see that this approximation holds already for realistic values of n and M used in neural net experiments.
We now manipulate the expression for T+ to isolate T+(M+1)(M+1). Using the Sherman-Morrison matrix inversion formula, we obtain
( Φ+ T Λ+Φ+ )−1 = ( ΦTΛΦ + λφφT )−1 = ( ΦTΛΦ
)−1 − λ (ΦTΛΦ)−1 φφT (ΦTΛΦ)−1 1 + λφT (ΦTΛΦ) −1 φ ,
(32)
and inserting this into the full expression for T+ gives
T+(M+1)(M+1) = EΦ,φ [ λφT ( Φ+ T ΛΦ+ + λφφT )−1 φ ]
= EΦ,φ λφT (ΦTΛΦ)−1 φ− λ2 [ φT ( ΦTΛΦ )−1 φ ]2
1 + λφT (ΦTΛΦ) −1 φ  = EΦ,φ
 λ λ+ [ φT (ΦTΛΦ) −1 φ ]−1  = EΦ,φ [ λ
λ+ C(Φ,φ)
] ,
(33)
where C(Φ,φ) ≡ [ φT ( ΦTΛΦ )−1 φ ]−1 is a nonnegative scalar.
We now argue that, for realistic values of M , n, and {λi}i, we can simply replace C(Φ,φ) by its mean. We first note that, because λ/(λ+ C) is convex, we can use Jensen’s inequality to find that
EΦ,φ [
λ
λ+ C(Φ,φ) ] ≥ λ λ+ C̄ , (34)
where we have defined C̄ ≡ EΦ,φ [ C(Φ,φ) ] . Some algebra also yields the fact that
λ λ+ C(Φ,φ) ≤ λ λ+ C̄ − λ(C (Φ,φ) − C̄) (λ+ C̄)2 + (C(Φ,φ) − C̄)2 (λ+ C̄)2 , (35)
for C(Φ,φ) ≥ 0, which, after taking an expectation, gives us the upper bound that
EΦ,φ [
λ
λ+ C(Φ,φ) ] ≤ λ λ+ C̄ + VarΦ,φ [ C(Φ,φ) ] (λ+ C̄)2
≤ λ λ+ C̄ + VarΦ,φ
[ C(Φ,φ) ] C̄2 .
(36)
Armed with the bounds of Equation 34 and Equation 36, we can replace C(Φ,φ) by C̄ in the last line of Equation 33 if we can show that VarΦ,φ [ C(Φ,φ) ] C̄2. This will be nontrivial to show in general, but we can easily see that it holds in a caricature of a realistic problem. In practice, we often find that the NTK spectrum is dominated by a few large eigenvalues with a long tail of small eigenvalues (Figure I5). To model this sort of spectrum, let p ∈ N with p n M , and suppose
λi = { λ0 if 1 ≤ i ≤ p λ′
M−p if p+ 1 ≤ i ≤M , (37)
with λ0 λ′/(M − p). The kernel matrix is given by
ΦTΛΦ = p∑ i=1 λ0φiφ T i + M∑ i=p+1 λ′ M − p φiφ T i ≈ p∑ i=1 λ0φiφ T i + λ ′In, (38)
where φi is the i-th row of Φ and we have made an approximation using the central limit theorem assuming that Φ is random with entries sampled i.i.d. fromN (0, 1). This kernel matrix has p large, O(λ0) eigenvalues and n − p remaining eigenvalues of order λ′. Its inverse therefore has p small eigenvalues and n−p similar large ones of order 1/λ′. Letting {ξi}ni=1 be these inverted eigenvalues, we have that
C(Φ,φ) = 1
φT (ΦTΛΦ) −1 φ = 1∑n i=1 ξix 2 i , (39)
where {xi}ni=1 are the components of φ on each of the kernel eigendirections. For typical {xi}ni=1 sampled i.i.d. fromN (0, 1), the denominator approaches (n−p)λ′ by the central limit theorem, and thus we reach our desired conclusion that C(Φ,φ) ≈ 1/((n − p)λ′) is approximately deterministic. More precisely, we find
EΦ,φ [ C(Φ,φ) ] ≈ 1
(n− p)λ′ , VarΦ,φ
[ C(Φ,φ) ] ≈ 3
(n− p)3(λ′)2 , (40)
from which we see that VarΦ,φ [ C(Φ,φ) ] C̄2 ≈ 3 n− p , (41)
which approaches zero when n p, as desired. This argument used a somewhat unrealistic kernel eigenspectrum, but numerical experiments show that C(Φ,φ) is approximately deterministic even for real eigenspectra (Figure F4). We leave the analysis of C(Φ,φ) for realistic kernels for future work.
100 101 102 n
10 2
10 1
100
101
102
Va r[C
]/ [C
]2
Figure F4: For NTK eigenvalues on the 7-sphere, Var [ C(Φ,φ) ] 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 to k = 6.
Replacing C(Φ,φ) by a constant C yields our final approximation for T, given in Equation 11. We note that, though this constant C is roughly the mean of C(Φ,φ), we circumvent deriving an explicit expression for this mean by instead using Theorem 1 to fix C.
F.1 PROOF OF LEMMA 2 Here we provide a 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 {λi}Mi=1 ordered from greatest to least.
Property (a): C =∞ when n = 0, and C = 0 when n = M . Proof. Because ∑M i=1 λi λi+C
is strictly decreasing with C for C ≥ 0, there can only be one solution for a given n. The first statement follows by inspection, and the second follows by inspection given our assumption that all eigenvalues are strictly positive.
Property (b): C is strictly decreasing with n.
Proof. Differentiating the constraint on C with respect to n yields
M∑ i=1 −λi (λi + C)2 dC dn = 1, (42)
giving
dC dn = − [ M∑ i=1 λi (λi + C)2 ]−1 < 0. (43)
Property (c): C ≤ 1n−` ∑M i=`+1 λi for all ` ∈ {0, ..., n− 1}.
Proof. n = ∑M i=1 λi λi+C ≤ `+ ∑M i=`+1 λi C . The desired property follows.
Property (d): C ≥ λ` ( ` n − 1 ) for all ` ∈ {n, ...,M}.
Proof. We consider replacing λi with λ` if i ≤ ` and 0 if i > `. Noting that this does not increase any term in the sum, we find that n = ∑M i=1 λi λi+C ≥ ∑` i=1 λ` λ`+C
= `λ`λ`+C . The desired property follows.
G SECOND-ORDER STATISTICS OF T(D)
G.1 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 11 with respect to a particular eigenvalue, we find that
d
dλi M∑ j=1 λj λj + C = M∑ j=1 −λj (λj + C)2 dC dλi +
C
(λi + C)2 = 0, (44)
yielding that
dC dλi =
C
q(λi + C)2 , where q ≡ M∑ j=1 λj (λj + C)2 . (45)
We now factor T(D) into two matrices as
T(D) = ΛZ, where Z ≡ Φ ( ΦTΛΦ )−1 ΦT . (46)
Unlike T(D), the matrix Z has the advantage of being symmetric and containing only one factor of Λ. Our approach will be to study the second-order statistics of Z, which will trivially give these statistics for T(D). From Equation 11, we can approximate the mean of Z as
EΦ[Z] = (Λ + CIM )−1. (47)
We also define a modified matrix Z(U) ≡ Φ ( ΦTUTΛUΦ )−1 ΦT , where U is an orthogonal M × M matrix. Because the measure over which Φ is averaged is rotation-invariant, we can equivalently average over Φ̃ ≡ UΦ with the same measure, giving
EΦ [ Z(U) ] = EΦ̃ [ UT Φ̃ ( Φ̃TΛΦ̃ )−1 Φ̃TU ] = EΦ [ UTZU ] = UT (Λ + CIM ) −1U. (48)
It is similarly the case that
EΦ [ (Z(U))ij(Z (U))k` ] = EΦ [( UTZU ) ij ( UTZU ) k` ] . (49)
Our aim will be to calculate expectations of the form EΦ[ZijZk`]. With a clever choice of U, we can now see that most choices of the four indices will make this expression zero. We define U
(m) ab ≡ δab(1 − 2δam) and observe that, because Λ is diagonal, (U(m))TΛU(m) = Λ and thus
Z(U (m)) = Z. Equation 49 then yields that
EΦ[ZijZk`] = (−1)δim+δjm+δkm+δ`mEΦ[ZijZk`] , (50)
from which it follows that EΦ[ZijZk`] = 0 if any index is repeated an odd number of times. In light of the fact that Zij = Zji, there are only three distinct nontrivial cases to consider:
1. EΦ[ZiiZii], 2. EΦ[ZijZij ] with i 6= j, and 3. EΦ[ZiiZjj ] with i 6= j.
We stress that we are not using the Einstein convention of summation over repeated indices.
G.2 CASE STUDIES Cases 1 and 2. We now consider differentiating Z with respect to a particular element of the matrix Λ. This yields
dZi` dΛjk
= −φTi ( ΦTΛΦ )−1 φjφ T k ( ΦTΛΦ )−1 φ` = −ZijZk`, (51)
where φi is the i-th row of Φ. This gives us the useful expression that
EΦ[ZijZk`] = − d
dΛjk EΦ[Z] . (52)
We now set ` = i and evaluate this expression using Equation 47, concluding that
EΦ[ZijZij ] = EΦ[ZijZji] = − d
dλj
( 1
λi + C
) =
1
(λi + C)2
( δij +
C
q(λj + C)2
) , (53)
CovΦ[Zij ,Zij ] = CovΦ[Zij ,Zji] = C
q(λi + C)2(λj + C)2 . (54)
We did not require that i 6= j, and so Equation 53 holds for Case 1 as well as Case 2. Case 3. We now aim to calculate EΦ[ZiiZjj ] with i 6= j. We might hope to use Equation 52 in calculating EΦ[ZiiZjj ], but this approach is stymied by the fact that we would need to take a derivative with respect to Λij we only have an approximation for Z for diagonal Λ. We can circumvent this by means of Z(U). From the definition of Z(U), we find that
( d
dUij − d dUji
) Z(U) ∣∣∣∣∣ U=IM
= −φTi ( ΦTΛΦ )−1 [ φjλiφ T i − φiλjφTj + φiλiφTj − φjλjφTi ] ( ΦTΛΦ )−1 φj
= (λj − λi) ( Z2ij + ZiiZjj ) . (55)
Differentiating with respect to both Uij and Uji with opposite signs ensures that the derivative is taken within the manifold of orthogonal matrices. Now, using Equation 48, we find that
( d
dUij − d dUji
) EΦ [ Z(U) ] ∣∣∣∣∣ U=IM = ( d dUij − d dUji ) UT (Λ + CIM ) −1U ∣∣∣ U=IM
= 1 λi + C − 1 λj + C .
(56)
Taking the expectation of Equations 55, plugging in Equation 53 for the squared off-diagonal element, comparing to 56, and performing a bit of algebra, we conclude that
EΦ[ZiiZjj ] = 1 (λi + C)(λj + C) − C q(λi + C)2(λj + C)2
(57)
and that Zii,Zjj are anticorrelated with covariance
CovΦ[Zii,Zjj ] = − C
q(λi + C)2(λj + C)2 . (58)
With the use of Kronecker deltas, we can combine Equations 54 and 58 into one expression covering all cases. As can be verified by case-by-case evaluation, one such expression is
CovΦ[Zij ,Zk`] = C (δikδj` + δi`δjk − δijδk`)
q(λi + C)(λj + C)(λk + C)(λ` + C) . (59)
Using the fact that T(D)ij = λiZij , we obtain the elementwise covariances of T (D) given in Equation 13.
G.3 DERIVING AN EXPRESSION FOR MSE Mean MSE is given by E(f) = E [ (v̂ − v)2 ] = vTE [ (T(D) − IM )T (T(D) − IM ) ] v = vTEv, where v and v̂ are the eigenfunction coefficients of the true and learned functions and we have defined E ≡ E [ (T(D) − IM )T (T(D) − IM ) ] . We can derive Equation 15 as follows:
Eij = E [ M∑ k=1 ( T (D) ki − δik )( T (D) kj − δjk )]
= M∑ k=1 E [ T (D) ki T (D) kj ] − E [ T (D) ji ] − E [ T (D) ij ] + δij
= δij [ M∑ k=1 λ2k (λk + C)2 ( δik +
C
q(λi + C)2
) − 2 λi
λi + C + 1
]
= δij
[( 1− λi
λi + C
)2 +
C
q(λi + C)2 M∑ k=1 ( λk λk + C − Cλk (λk + C)2 )]
= δij
[( C
λi + C
)2 +
nC q(λi + C)2 − qC
2
q(λi + C)2
]
= δijnC
q(λi + C)2 .
(60)
Though it is not apparent at a glance, this expression for MSE is in fact equivalent to the main result of Bordelon et al. (2020) with a ridge parameter of zero. To obtain their expression from ours, substitute n → p, C → t/p, q → p2/t − p3γ/t3, and vi → λ1/2i wi. 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 an 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 IN TERMS OF LEARNABILITY
As a final theoretical note, we observe that our expressions for transfer matrix covariances and MSE can all be written strictly in terms of the modewise learnabilities Li ≡ λiλi+C . 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
n = M∑ m=1 Lm and Cq = M∑ m=1 Lm(1− Lm). (61)
With these expressions in hand, we can quickly see that
Cov [ T
(D) ij ,T (D) k` ] = Li(1− Lj)Lk(1− L`)∑M
m=1 Lm(1− Lm) (δikδj` + δi`δjk − δijδk`) (62)
and
Eii = ∑M m=1 Lm∑M
m′=1 Lm′(1− Lm′) (1− Li)2. (63)
These expressions allow one to more clearly see the effects of the model’s inductive bias. For example, in light of the fact that Li ∈ [0, 1], Equation 62 shows that Var [ T (D) ij ] is larger the
higher the learnability of the “learned mode” i 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 high-learnability modes, we thus expect that the learned function f̂ will tend to be spectrally biased, placing outsize weight in more learnable modes.
One recurring quantity in these expressions is Li(1−Li), which is zero for Li = 0, 1 and maximal at Li = .5. Intuitively speaking, it describes the rate at which a mode is “currently being learned” with increasing n, as can be seen from the fact that
dLi dn = Li(1− Li)∑M
m=1 Lm(1− Lm) . (64)
This equation states that a new unit of learnability (i.e. a new data point) is divvied up among all the eigenmodes in proportion to Li(1− Li).

heading: H EXPERIMENTAL DETAILS
text: We conduct all our experiments using JAX, performing exact NTK regression with the Neural Tangents library (Novak et al., 2019) built atop it. For the dataset sizes we consider in 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, as described by Rahaman et al. (2019), lower eigenmodes take longer to train (especially when aiming for near-zero training MSE as we do here).
Unless otherwise stated, all experiments used four-hidden-layer ReLU networks initialized with NTK parameterization (Sohl-Dickstein et al., 2020) with σw = 1.4, σb = .1. The tanh networks used in generating Figure 3 instead used σw = 1.5. Experiments on the unit circle always used a learning rate of .5, while experiments on the hypercube and hypersphere used a learning rate of .5 or .1 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 Lewkowycz et al. (2020). Means and 1σ error bars always reflect statistics from 30 random dataset draws and initializations (for finite nets), except for the nonmonotonic MSE curves of Figure A1, which used 100 trials. We emphasize that the “no free lunch” experiment of Figure 3 used only a single trial.
I NTK EIGENVALUES ON EXPERIMENTAL DOMAINS

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

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.