The Eigenlearning Framework: A Conservation Law Perspective on Kernel Ridge Regression and Wide Neural Networks
Authors: James B Simon
Madeline Dickens
Dhruva Karkada
Michael R DeWeese
Venue: Submitted to ICLR 2023 (2023)
Keywords: kernel regression
kernel ridge regression
wide neural networks
neural tangent kernel
ntk
generalization
conservation laws
learnability

Abstract: We derive simple closed-form estimates for the test risk and other generalization metrics of kernel ridge regression (KRR). Relative to prior work, our derivations are greatly simplified and our final expressions are far more interpretable. These improvements are enabled by our identification of a sharp conservation law which limits the ability of KRR to learn any orthonormal basis of functions. Test risk and other objects of interest are expressed in a transparent, interpretable way in terms of our conserved quantity evaluated in the kernel eigenbasis.
We use our improved framework to:
   i) provide a theoretical explanation for the ``deep bootstrap" of Nakkiran et al (2020),
   ii) prove a new result regarding the hardness of the classic parity problem,
   iii) fashion a theoretical tool for the study of adversarial robustness, and
   iv) draw a tight analogy between KRR and a well-studied system in statistical physics.

Under review as a conference paper at ICLR 2023
THE EIGENLEARNING FRAMEWORK: A CONSERVATION LAW PERSPECTIVE ON KERNEL REGRESSION AND WIDE NEURAL NETWORKS
Anonymous authors Paper under double-blind review
ABSTRACT
We derive a simple unified framework giving closed-form estimates for the test risk and other generalization metries of kerne ridge regression (KRR). Relative to prior work, our derivations are greatly simplified and our final expressions are more readily interpreted. In particular, we show that KRR can be interpreted as an explicit competition among kernel eigenmodes for a fixed supply of quantity we term "learnability." These improvements are enabled by sharp conservation law which limits the ability of KRR to learn any orthonormal basis of functions. Test risk and other objects of interest are expressed transparently in terms of our con- served quantity evaluated in the kernel eigenbasis. We use our improved frame- work to: i) provide a theoretical explanation for the "deep bootstrap" of Nakkiran et al.] (2020), ii) generalize a previous result regarding the hardness of the classic parity problem, iii) fashion a theoretical tool for the study of adversarial robust- ness, and iv) draw tight analogy between KRR and a well-studied system in statistical physics.
INTRODUCTION
Kernel ridge regression (KRR) is a popular, tractable learning algorithm that has seen a surge of attention due to equivalences to infinite-width neural networks (NNs) (Lee et al. 2018 Jacot et al.) 2018). In this paper, we derive a simple theory of the generalization of KRR that yields estimators for many quantities of interest, including test risk and the covariance of the predicted function. Our framework is consistent with other recent works, such as those Canatar et al.] (002)) and (aacot al. 2020), but is simpler and easier derive. Our framework paints new picture of KRR an explicit competition between eigenmodes for fixed budget of quantity we term "Icarnability." and downstream generalization metrics can be expressed entirely in terms of the learnability received by each mode (Equations) 744.
This picture stems from conservation law latent in KRR which limits any kernel's ability to learn any complete basis of target functions. The conserved quantity, learnability, is the inner product of the target and predicted functions and, as we show, can be interpreted as measure of how well the target function can be learned by a particular kernel given n training examples. We prove that the total learnability, summed over a complete basis of target functions (such as the kernel eigenbasis), no greater than the number of training samples, with equality at zero ridge parameter.
The conservation of this quantity suggests that it will prove useful for understanding the general- ization of KRR. This intuition is borne out by our subsequent analysis: we derive a set of simple, closed-form estimates for test risk and other objects of interest and find that all of them can be trans- parently expressed in terms of eigenmode lcarnabilities. Our expressions are more compact and readily interpretable than those of prior work and constitute a major simplification.
Our derivation of these estimators is significantly simpler and more accessible than those of prior work, which relied on the heavy mathematical machinery of replica calculations and random matrix theory to obtain comparable results. By contrast, our approach requires only basic linear algebra, leveraging our conservation law at a critical juncture to bypass the need for advanced techniques.
We our improved framework to shed light on several topics of interest:

---

Under review as a conference paper at ICLR 2023
i) We provide compelling theoretical explanation for the "deep bootstrap" phenomenon of Nakkiran et al.] (2020) and identify two regimes of NN fitting occurring at early and late training times.
ii) We generalize a previous result regarding the hardness of the parity problem for rotation- invariant kernels. Our technique simple and illustrates the power of our framework.
iii We craft an estimator for predicted function smoothness, new tool for the theoretical study of adversarial robustness.
iv) We draw tight analogy between our framework and the free Fermi gas, a well-studied statistical physics system, and thereby transfer insights into the free Fermi gas over to KRR.
We structure these applications series of vignettes.
The paper is organized as follows. We give preliminaries in Section 2
We define our conserved
quantity and state its basic properties in Section 3 We characterize the generalization of KRR in
terms of this quantity in Section 4 We check these results experimentally in Section [ Section 6
consists of series of short vignettes discussing topics (i)-(iv). We conclude in Section
1.1 RELATED WORK
The present line of work has its origins with early studies of the generalization of Gaussian pro- cess regression (pper 1997, Sollich 1999), with [Sollich (200T) deriving an estimator giving the expected test risk of KRR in terms of the eigenvalues of the kernel operator and the eigendecompo- sition of the target function. We refer to this result as the "omniscient risk estimator as it assumes full knowledge of the data distribution and target function. Bordelon al. (2020) and Canatar et al.) 202T) brought these ideas into a modern context, deriving the omniscient risk estimator with a replica calculation and connecting it to the "neural tangent kernel" (NTK) theory of wide neural networks (Jacot et al.] 2018). with (Lourciro et al.] (221)) extending the result to arbitrary convex losses. Sollich & Halees (2002); Caponnetto & De Vito (2007); (Spigler et al.) (2020); Cui et al. (202T: Mallinar et al. (2022) study the asymptotic consistency and convergence rates of KRR in similar vein. [Jacot al. (2020); Wei et al. (2022) used random matrix theory derive risk estimator requiring only training data. In parallel with work on KRR, Dobriban & Wager (2018 8);
Wu & Xu 20200; Richards al. (202T); Hastie et al. 2022 and Bartlett et al. (021) developed equivalent results in the context of linear regression using tools from random matrix theory. In the
present paper, we provide new interpretation for this rich body of work in terms of explicit com-
petition between eigenmodes, provide simplified derivations of the main results of this line of work, and break new ground with applications to new problems of interest. We compare selected works with ours and provide a dictionary between respective notations in Appendix A
All prior works in this line - and indeed most works in machine learning theory more broadly bounds to make any claims about generalization. The rely on approximations, asymptotics, conservation law is unique in that it gives a sharp equality even at finite dataset size. This makes it particularly robust starting point for the development of our framework (which does later make approximations).
In addition those listed above, many works have investigated the spectral bias of neural networks in terms of both stopping time (Rahaman et al. 2019 Xu et 2l. a. Xu] 2018 Cao et al. 2019
Su & Yang 2019) and the number of samples (Valle-Perez et al.) 2018 Yang & Salman 2019
Arora et al. 2019). Our investigation into the deep bootstrap ties together these threads of work:
find that the interplay of these two sources of spectral bias is responsible for the deep bootstrap
phenomenology.
2 PRELIMINARIES AND NOTATION
We study a standard supervised learning setting in which n training samples D = { are drawn i...d from a distribution over Rd. We wish to learn a (scalar) target function f given noisy evaluations y = (1.)i with yi = f(x;) + mhe with na ~ NN( As it simplifies later
We borrow this terminology from Wei al. 2022
2

---

Under review as a conference paper at ICLR 2023
A
B
6
10
D
E
D
8
learaaillity budget
6
2m
(D)
C
learnahility budget
(D, (D)) network
fr.
regression
((D) (0k) = (0k; fk))
0
4HL
1HL
4HL
ReLU ReLU tanh
tanh
ReLU
ReLU
tanh
tanh
Figure 1: Toy problem illustrating conservation law. (A) The task domain: the unit cir- cle discretized into A = 10 points, n of which comprise the dataset D (filled circles). (B) The 10 eigenfunctions of rotation-invariant kernel this domain, grouped into degenerate pairs and shifted vertically for clarity. (C) We use each eigenfunction Φx in turn as the target function. For each ΦR. we compute training targets gix(D) (D), obtain a predicted function fx in standard supervised learning setup, and subsequently compute D-Jearnability. This comprises 10 orthogonal learning problems. (D,E) Stacked bar charts with 10 components showing D-learnability for each eigen- function. The left bar each pair contains results from NTK regression, while the right bar contains results from wide neural networks. Models vary in activation function and number of hidden layers (HL). Dashed lines indicate n. Learnabilities always sum to n, exactly for kernel regression and approximately for wide networks.
analysis, assume this (V,, c2) label noise is also applied test target Our results are easily generalized to vector-valued functions as in Canatar et al. (2021). For scalar functions g, h, we define (g, h) EE=plg(z))h()) and | (9.g).
We shall study the KRR predicted function f given by
f(x) k (KDD SI,))
where, for a nositive-semidefniite kernel K, we have constructed the row vector [k.p]; K (x., x.;) and the empirical kernel matrix [Kookj K K(,,, x.,) (which trust be nonsingular), 5 is ridge parameter, and I, is the identity matrix. We wish to minimize test mean squared error (MSE) (F) If - -fl12 + e² and its expectation over training sets E(f) = Ep [E() (where the expectation over DD also averages over noise values). We emphasize that, here and in our discussion of learnability, is understood to be the KRR predictor given by Equation | from training targets generated with target function f. In the classical bias- variance decomposition of test risk, we have
bias B(f) |/ [=] 2 and variance V(J) E(ʃ) B(J) We also define train MSE as Ef(f) Σ (f f(x:))²
2.1 THE KERNEL EIGENSYSTEM
By Mercer's theorem Mercer 1909), the kernel admits the decomposition K(x, x') Σ, λ, (z) with eigenvalues A, 0 and basis of eigenfunctions o, satisfying (o., Øz)
Dgj. We assume eigenvalues are indexed in descending order.
As the eigenfunctions form a complete basis, we are free decompose / and f as
f(z) Σ vx))(()) and f(x)) = Σ t1d((2),
where v = (v:); and v = (6:); are vectors of eigencoefficients.
"To study noiseless targets instead, simply subtract ? from expressions for test MSE
3

---

Under review as a conference paper at ICLR 2023
3 LEARNABILITY AND ITS CONSERVATION LAW
Here we define learnability, our conserved quantity. Learnabiiity is measure of f defined similarly to test MSE, but it is linear instead of quadratic. For any function f such that |J| - 1, let
(P) ff. and C(f) = ED [
(3)
where, with MSE, f is given by Equation We refer C(P) (f) the D-learnability of function f with respect to the kernel and n and refer to L() as the learnability. Up to normalization, this quantity is akin to the cosine similarity between ff and f. We shall show that, for KRR, learnability gives a useful indication how well a function (particularly a kernel eigenfunction) is learned. Results in this section are rigorous and exact; see Appendix G for proofs.
We begin by stating several basic properties of learnability to build intuition for the quantity.
Proposition 3.1. The following properties of (P),, L. { and any f such that Ifll = 1 hold:
(a) [(d.), (PP) E [0, 1].
(b) When n 0, ((P) (J) [(J) =0
(c) Let D+ be D Uu where x E Xx of 'D is a new data point. Then ((P+) 2 (o.).
(d) ax, ((P) ( 2 0. a C P) (0,) = 0, and 06 (0i) S0.
04.
(e) 8()) 2 B 2 -(
Properties (a-c) together give an intuitive picture of the learning process: the learnability of each eigenfunction monotonically increases from zero the training set grows, attaining its maximum of one in the ridgeless, maximal-data limit. Properties (d) shows that the kerne eigenmodes are in competition increasing one eigenvalue while fixing all others can only improve the learnability of the corresponding eigenfunction, but can only harm the learnabilities of all others and that regularization only harms eigenfunction learnability. Property (e) gives a lower bound on MSE in terms of learnability and will be useful when we discuss the parity problem.
We now state the conservation law obeyed by learnability. This rule follows from the view of KRR as projection of f onto the n-dimensional subspace of the RKHS defined by the samples and is closely related to the "dimension bound" for linear learning rules given by Hsu (002I).
Theorem 3.2 (Conservation of learnability). For any complete basis of orthogonal functions F, when ridge parameter 0,
Σ ((()) Σ E(() n,
(4)
JeF
SEF
and when > O,
Σ (PP) <n <n fEF
and Σ < n
(5)
fEF
This result states that, summed over any complete basis of target functions, total learnability is most the number of training examples, with equality at zero ridge This theorem is stronger ver- sion of the classic "no-frec-lunch" theorem for learning algorithms. which states that, averaged over all target functions, all models perform at chance level (Wolperi 1996). While deep and compelling, this classic result rarely informative in practice because the set of all possible target functions prohibitively large to make a nonvacuous statement. By contrast, Theorem 3.2 requires only an av- erage over a basis target functions and, as we shall see, it is directly informative in understanding the generalization of KRR.
We call Theorem 3.2 conservation law because zero ridge, either the data distribution or the kernel changes, total learnahility remains constant. This analogous to, for example, physical conservation of charge.
4

---

Under review as a conference paper at ICLR 2023
4 THEORY
Eigenmode learnabilities are interpretable quantitics, obeying a conservation law and several intu- itive properties. These features suggest they may prove wise choice of variables in theory of KRR generalization. Here we show that this is indeed the case: we derive a suite of estimators for various metrics of KRR generalization, all of which can be expressed entirely in terms of modewise learnabilities and thereby inheriting their interpretability. Because they characterize KRR learning via eigenmode learnabilities, we call these equations the eigenlearning equations.
Our derivation leverages our conservation law avoid the need for either replica calculation random matrix theoretic tools and is consequently more accessible and extensible than derivations of prior works. Results in this section are nonrigorous. Like comparable works, our derivations use an experimentally-vaiide "universality" assumption that the kernel features may be replaced by independent Gaussian features with the same statistics without changing downstream generalization metrics.
We sketch our method here and relegate the derivation to Appendix H
We begin by observing that v depends linearly on V, and we can thus construct a "learning transfer matrix" TDD) such that v (P)) v. T(P) is equivalent to the "KRR reconstruction operator" of Jacot et al. (2020) and, viewing KRR as linear regression in eigenfeature space, is essentially the universality assumption to show that it is diagonal with diagonal elements of the form >/((A; + k), where is mode- independent constant. We show the mode-independence of к with an eigenmodc--emovall argument reminiscent of the cavity method of statistical physics (Del Ferraro et al. 2014). We use Theorem 3.2 to determine k. Differentiating this result with respect to kernel eigenvalues, we obtain the covariance (P) and thus of v, which permits evaluation various test metrics
"hat" matrix of linear regression. We then study E [T)] leveraging
4.1
THE FIGENLEARNING EQUATIONS
Let the effective regularization x be the unique positive solution to
A
n Σ
(6)
+ K
We calculate various test and train metrics to be
X; Li
(eigenmode learnability)
((Ø.)
(7)
X; +
0k
71
(overfitting coefficient)
En = n 08
(8)
n - E, C7'
(test MSE)
E(f) = & Σ (1 2.22v + +2)
(9)
E())
(bias of test MSE)
B(f) = Σ 2. +
(10)
En
E0 -
(variance of test MSE)
V( 8() B(J
E()),
(11)
E
82 ( n² E(),
(train MSE)
(12)
(mean predictor)
B[V,] LiVi. E(F) 853
(13)
(covariance of predictor)
Covlv; vy]
(14)
n
The lcarnability of an arbitrary normalized function can be computed as L(f) = Σ, Liv. The
mean of the target function evaluated at input can be obtained as [[f(x)) = Σ, (.v)), with the covariance obtained similarly.
Forr train risk, we simply quote the result of Canatar 2021
5

---

Under review as a conference paper at ICLR 2023
4.2 INTERPRETATION OF THE EIGENLEARNING EQUATIONS
Remarkably, all test metrics, and indeed all second-order statistics of f. can be expressed solely in terms of modewise learnaillities, with additional reference eigenvalues required. This strongly suggests that we have identified the "correct" choice of variables for the problem. We now interpret these equations through the lens of learnability.
Equation 6 gives constant A which decreases monotonically as n increases, Equation 7 states that the learnability of eigenmode i is 0 when x >>>> X; and approaches when K A2 in line with the observation of Jacot et al. (0200) that a mode is well-learned when K < Aç. Inserting Equation into 6 and setting
0, we recover our conservation law.
Equation 9 is the omniscient risk estimator for test MSE. Modes with learnability equal to one are fully learned and do not contribute to the risk. Noise acts the same as target weight placed in modes with learnability zero. Equation [8] defines Eg. the MSE when trained on pure-noise targets (v; 0 and e² = 1). It is strictly greater than one and can be interpreted as the factor by which pure noise is overfi The denominator explodes when the units of learnability are fully allocated to the first modes, not distributed among a greater number (Lign = 1, Li>n = 0). In this sense, overfitting of noise is "overconfidence" on the part of the kernel that the target function lies in the top-n subspace, and "hedging" via a wider distribution of learnability (or sacrificing a portion of the learnability budget the ridge parameter) lowers & and fixes this problem. This overconfidence occurs when the kernel eigenvalues drop sharply around index n and is the cause of double-descent peaks (Belkin al., 2019). ) which other works have also found can be avoided with an appropriate ridge parameter Canatar et al. (2021): Nakkiran et al. (2021).
Equations 10 and show that, remarkably, the bias and variance can be expressed solely in terms of E() and Eg. Since learnabilities strictly increase as n grows, the bias strictly decreases while the variance can be nonmonotone, as also noted by Canatar et al. (202I). Equation [2] states that train error is related to test error by the farget-independent proportionality constant 8=/m² Finally, Equations 13 and 14 give the mean and covariance of the predicted eigencoefficients. Different eigencoefficients are uncorrelated, and the variance of v, is proportional to L? but surprisingly independent of V,.
EXPERIMENTS
Here we describe experiments confirming our main results. The targets are eigenfunctions on three synthetic domains - the unit circle discretized into M points, the (Boolean) hypercube {=1]d and the d-sphere - as well as two-class subsets of MNIST and CIFAR-10. Unless otherwise stated, experiments
wee-hhiddn-yyeee ReLU architecture, and finite networks have width 500. The kernel eigenvalues on each synthetic domain group into degenerate sets which we index by k E Z+. Eigenvalues and eigencoefficients for image datasets approximated numer- ically from a large sample of training data. Full experimental details can be found in Appendix
fully-connected
Figure T Iillustrates Theorem 3.2 in a toy setting. Modewise D-learnabilities indeed sum to n. Figure 2 compares theoretical predictions for learnability and MSE with experiments on real and synthetic data, finding good agreement in all cases. Oppendix[rrepeaa one of these experiments with network widths varying from oo to 20, finding good agreement with theory even narrow width.
VIGNETTES
6.1 EXPLAINING THE DEEP BOOTSTRAP
The deep bootstrap (DB) is phenomenon observed by Nakkiran et al. (2020) in which the perfor- mance of a neural network stopped after a given number of training steps relatively insensitive to the size of the training set, unless the training set is small that has been interpolated. The DB has been studied theoretically on kernel gradient flow (KGF), which describes the training of wide neural networks, by Ghosh et al. 2022 in the toy case in which the data lies on high-dimensional
See Mallinar al. 2022 for discussion of this interpretation.

---

Under review as a conference paper at ICLR 2023
A
Unit Circle
B
8d Hypercube
C
7-sphere
D Image Datasets
1.0
c(
MARST
0.5
0.0
E
2
UNORT
0
2
74
Figure 2: Predicted learnabilities and MSEs closely match experiment. (A-D) Learnability of various cigenfunctions on synthetic domains and binary functions over image datasets. Theoretical predictions from Equation 7 (curves) are plotted against experimental values from trained finite networks (circles) and NTK regression (triangles) with varying dataset size n. Error bars show one standard deviation of variation. (E-H) Same as (A-D) for test MSE, with theoretical predictions from Equation 9
sphere. Here we give convincing general explanation of this phenomenon using our framework and identify two regimes of NN fitting in the process.
Ali et al. (2019) proved that KRR with finite ridge generalizes remarkably similarly to KGF with finite stopping time theoretical result confirmed empirically by Lee et al. (2020) for NTKs on image datasets). When considering standard supervised learning setting, the effective training time corresponding to a ridge d Teff 8 8-1n (see Appendix [ for a discussion of this scaling). As proxy for KGF, we shall study KRR as Terr increases from 0 to co.
In Equation the ridge parameter affects MSE solely through the value of k. Define Kg = k|8=0- the minimum effective regularization at given dataset size. In Appendix D we show that, for powerlaw eigenspectra (as are commonly found in practice), there are two regimes of fitting:
1. Regularization-Ilmitee regime: Tell < Kg and к - The generalization gap is small: ((f)/Eu(f) = 1. Regularization dominates generalization, and adding training samples does not affect generalization
2. Data-limited regime: Tex >> Kg and = Ky- The generalization gap large:
{(f)/Eu(f) > 1. Data is interpolated. and decreasing regularization (i.e. increasing training time) does not affect generalization.
We suggest that Nakkiran et al. 2020) observe overlapping error curves for different early times because, at these times, the model is in the regularization-limiee regime.
We now present experiment confirming interpretation. In Figure 3 we reproduce an experi- ment of Nakkira et al. (2020) illustrating the DB using ResNets trained on CIFAR-10, juxtaposing with our proposed model for this phenomenon MNIST. The match is excellent: in particular, both plots share the DB phenomenon that error curves for all n overlap early times, with test and train eттог peeling off the master curve roughly the same time. We find that Tef Kig is indeed when the transition between regimes occurs for KRR, matching our theoretical prediction. This experiment strongly suggests that both neural network and KRR fitting can be thought of as transition between regularization-limies and data-limited regimes. See Appendix D for experimental details.
KRR with varying Teff trained on binarized
6.2 THE HARDNESS OF THE PARITY PROBLEM FOR ROTATION-INVARIAN KERNELS
The parity problem stands as a classic example of a function which is easy to write down but hard for common algorithms to learn. The parity problem was shown to be exponentially hard for Gaus-
We here that adding training samples while holding Tor constant does affect generalization.
7

---

Under review as a conference paper at ICLR 2023
10
16
Classification Eiror
500
125
71 2000
600
71 8000
KRR
10
NN
test
32000
Cheory
KRR test
== 8000
10ah
10P
10
10P
10a
10
Tran steps
Figure 3: We reproduce and explain the deep bootstrap phenomenon in KRR. (A) An ex- periment illustrating the deep bootstrap effect using ResNet-18 on CIFAR-10. (B) An analogous experiment using KRR on binarized MNIST. Eigenlearning predictions closely match experimental curves, and Teff Kg (vertical dashed lines) faithfully predicts the transition from regularization- limited to lamae fitting for each n.
sian kernel methods by Bengio et (2006). Here we generalize this result to KRR with arbitrary rotation-invariant kernels. Our analysis is made trivial by the use of our framework and is a good illustration of the power of working terms of learnaillities.
The problem domain is the hypercube X' = 1-1,+11%, over which we define the subset-parity -arity functions (I)) (-1) [|;=1), where 5 S {1, d} = [d]. The objective is to learn Φ1d1-
For any rotation-invarian kernel (such as the NTK of a fully-connected neural network), {os}s the eigenfunctions over this domain, with degenerate eigenvalues {>x depending only on = [S. Yang & Salman (2019) proved that, for any fully-connected kernel, the even and odd eigenvalues each obey particular ordering in k. Letting d be odd for simplicity, this result and Equation 7 imply that Ci 2 L3 2 2 La. Counting level degeneracies, this is a hierarchy of 2d-1 leamabilitiess of which La the smallest. The conservation law of 3.2 then implies that La S 2d-1 which, using Proposition 3. [e] implies that
2
E((14) 2
(15)
2d-
Obtaining MSE below desired threshold thus requires at least 70 = (1 2/22) samples, a sample complexity exponential in d. The parity problem is thus hard for all rotation-invarian kernels7
6.3 MEAN-SQUARED GRADIENT AND ADVERSARIAL ROBUSTNESS
While the omniscient risk estimate is the most important of the eigenlearning equations, we have also obtained estimators for arbitrary covariances of f. Here we point out first use for these covari- ances: studying the smoothness of f and thus its adversarial robustness. We fashion an estimator for function smoothness, confirm its accuracy with KRR experiments, and identify a discrepancy between intuition and experiment ripe for further exploration.
Consider the mean squared gradient (MSG) of defined by G() = E, [va](()]]] IV This quantity is a measure function smoothness. Eigendecomposittin yields that
E V
vzf(x)
Σ ElVivglgi with 9y = (x))()) Vady(=))
(16)
The expectation E[v,v,l = E[ E I + Cov(v, v,] is given by the eigenlearning equations, and the structure constants Pij. which encode information about the domain, be computed analyti- cally for simple domains. On the d-sphere, for which the Φ; Φ are spherical harmonics, these (ke) k:kk d d2r
We note number of recent approaches Daniely & Malach 2020 Kamath et al. 2020 Hsu 2021 which
give complexity lower bounds for lcarning parities using simple degeneracy argument. However, these ap- proaches do not leverage the spectral bias of the kemee and become vacuous when à d.
8

---

Under review as a conference paper at ICLR 2023
Figure4 the MSG of the function learned by KRR with polynomial kernel trained on k = 1 modes spheres of increasing dimen- sion d, normalized by the MSG of the ground- truth target function. See Appendix [ for ex- perimental details and additional experiments this vein. True MSG matches predicted MSG well in all settings, particularly at large and d.
1.00
4=4
d 16
0.75
64
d= 256
0.50
1020
0.25
0.00
The study of adversarial robustness currently suffers from a lack of theoretically tractable toy models, and we suggest our expression for MSG can help fill this gap. To illustrate this, we describe an insight that can be drawn from Figure 4 Vulnerability to gradient-based ad- versarial attacks can be viewed essentially as phenomenon of surprisingly large gradients with respect to the input. If such vulnerability inevitable consequence of high dimension,
24
26
2
2
212
12.
Figure 4: Predicted function smoothness matches experiment. Predicted MSG of (curves) and empirical MSG for kernel regression (triangles) for k = modes on hyperspheres with varying dimension.
common heuristic belief (e.g. Gilmer al. (2018). one might expect that G(f) generally much larger than G(f) at high dimension. Surprisingly, we see no such effect, a discrepancy which can be investigated further using our framework.
6.4 A QUANTUM MECHANICAL ANALOGY AND UNIVERSAL LEARNABILITY CURVES
Here we describe a remarkably tight analogy between our picture of KRR generalization and the statistics of the free Fermi gas, canonical model statistical physics. This allows certain insights into the free Fermi gas to be ported over to KRR. This correspondence is also of fundamental inter- est: KRR and free Fermi gas are both paradigmatic systems in their respective fields, and is remarkable that their statistics are in fact the same.
We defer the details of this correspondence to Appendix F and focus here on the takeaways. The free Fermi gas is defined by scalar μ and set of states with energies { each of which may be occupied or not. We find that In x is analogous to p. the state energies are analogous to kernel eigenvalues, and the states" occupation probabilies are precisely analogous the eigenmodes' learnabiiities.
In all prior work and in work thus far, the constant has thus far been defined only as the solution to an implicit equation. Having an explicit equation would be advantageous. Leveraging methods for the study of the free Fermi gas, find the following explicit formula for
M7 (A1, )2....
where
my (21,
=
Σ
(17)
Mn (A1,, '2....)'
15 SJ.
The second takeaway is the identification of a universal behavior in the learning dynamics of KRR. In systems obeying Fermi-Dise statistics. plot of p. vs. E; takes a characteristic sigmoidal shape. As shown in Figure I0] we robustly see this sigmoidal shape in plots of L; vs. An. As the number of samples and even the task are varied, this sigmoidal shape remains universal, merely translating horizontally (in particular, moving left samples are added). This sigmoidal shape is thus signature of KRR and could in principle be used to, for example, determine an unknown kernel method resembles KRR.
7 CONCLUSIONS
We have developed an interpretable unified framework for understanding the generalization of KRR centered on wrexiousy-uneeplootee conserved quantity. We then used this improved framework to break new theoretical ground in a variety subjects including the parity problem, the deep bootstrap. and adversarial robustness and developed tight analogy between KRR and canonical physical system allowing the transfer of insights. We have covered much territory, and each of these subjects is ripe for further exploration in future work.

---

Under review as a conference paper at ICLR 2023
REFERENCES
Alnur Ali, J Zico Kolter, and Ryan J Tibshirani. A continuous-tin -ime view of early stopping for least squares regression. In The 22nd international conference on artificial intelligence and statistics, pp. 1370-1378. PMLR, 2019.
Sanjeev Arora, Simon Du, Wei Hu, Zhiyuan Li, and Ruosong Wang. Fine-graines analysis of op- timization and generalization for overparameterized two-layer neural networks. In International Conference Machine Learning, pp. 32.322-333 332.. PMLR, 2019.
Jimmy Ba. Murat Erdogdu, Taiji Suzuki, Zhichao Wang, Denny Wu, and Greg Yang. High- dimensional asymptotics of feature learning: How one gradient step improves the representation. arXiv preprint wwX.v:2205.01444: 2022.
Yasaman Bahri, Ethan Dyer, Jared Kaplan, Jachoon Lee, and Utkarsh Sharma. Explaining neural scaling laws. arXiv preprint arXiv:2102.06701, 2021.
Peter L Bartlet, Andrea Montanari, and Alexander Rakhlin. Deep learning: statistical viewpoint. Acla numerica, 30:87-201, 2021.
Mikhail Belkin, Daniel Hsu, Siyuan Ma, and Soumik Mandal. Reconciling modern machine- learning practice and the classical varinnar trade-off. Proceedings of the National Academy of Sciences, 166632):15449-158
2019.
Yoshua Bengio, Olivier Delalleau, and Nicolas Le Roux. The curse of highly variable functions for local kernel machines. Advances in neural information processing systems, 18:107 2006.
Blake Bordelon and Cengiz Pehlevan. Learning curves for sgd on structured features. arXiv preprint 1oXiv:2/06.02213. 2021.
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. 1024-1034. PMLR, 2020.
James Bradbury. Roy Frostig, Peter Hawkins. Matthew James Johnson, Chris Leary, Dougal Maclaurin, George Necula, Adam Paszke, Jake VanderPlas, Skye Wanderman-Miin MMilee, and Qiao Zhang. JAX: composable transformations of Python+NumPy programs, 2018. URL http:
//github. ctm com./oogle/oo/a/.////ooo
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-Dinuun Xuan Zhou, and Quanquan Gu. Towards understanding the spectral bias of deep learning. arXiv preprint arXiv: /9/2.01 198, 2019.
Andrea Caponnetto and Ernesto De Vito. Optimal rates for the regularized squsres algorithm. Foundations of Computational Mathematics. 7(3):331-369) 2007.
Xiuyuan Cheng and Amit Singer. The spectrum of random inner-product kernel matrices. Random Matrices: Theory and Applications, 2(04))130001,, 2013.
Omry Cohen, Or Malka, and Zohar Ringel. Learning curves for overparametrized deep neural networks: field theory perspective. Physical Review Research, 3(2):023034, 2021.
Hugo Cui, Bruno Loureiro, Florent Krzakala, and Lenka Zdeborová. Generalization error rates in kernel regression: The crossover from the noiseless to noisy regime. Advances in Neural Information Processing Systems, 34:10131-10143, 2021.
Amit Daniely and Eran Malach. Learning parities with neural networks. Advances in Neural Infor- mation Processing Systems, 33:20356-20365, 2020.
Gino Del Ferraro, Chuang Wang. Dani Martí, and Mare Mézard. Cavity method: Message passing from physics perspective. arXiv preprint arXiv:/409.3300 2014.
10

---

Under review as a conference paper at ICLR 2023
Edgar Dobriban and Stefan Wager. High-dimensional asympttoo of predictions: Ridge regression and classification. The Annals of Statistics, 46(1):247-279) 2018.
Noureddine El Karoui. The spectrum of kernel random matrices. The Annals of Statistics, 38(1): 1-50, 2010.
Zhou Fan and Andrea Montanari. The spectral norm of random inner-product kernel matrices. Probability Theory and Related Fields, 173(1):27-85, 2019.
Christopher Frye and Costas J Efthimiou. Spherical harmonies in p dimensions. arXiv preprint 1205.3550 2012.
Nikhil Ghosh, Song Mei, and Bin Yu. The three stages of learning dynamics in high- seah--dimensional kernel methods. In International Conference on Learning Representations, ICLR, 2022.
Justin Gilmer, Luke Metz, Fartash Faghri, Samuel S Schoenbolz, Maithra Raghu, Martin Watten- berg, and Ian Goodfellow. Adversarial spheres. arXiv preprint arXiv: urXiv:1801.02774 2018.
Nigel Goldenfeld. Roughness-induced critical phenomena in turbulent flow. Physical review letters, 9644):0 2006.
Trevor Hastie, Andrea Montanari, Saharon Rosset, and Ryan J Tibshirani. Surprises in high- dimensional ridgeless least squares interpolation. The Annals of Statistics, 50(2):949-98) 2022.
Daniel Hsu. Dimension lower bounds for linear approaches to function approximation. Daniel Hsu's homepage, 2021.
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), 2018.
Arthur Jacot, Berfin Şimşek, Francesco Spadaro, Clément Hongler, and Franck Gabriel. Kernel alignment risk estimator: risk prediction from training data. arXiv preprint arXiv:2006.09796, 2020.
Pritish Kamath, Omar Montasser, and Nathan Srebro. Approximate is good enough: Probabilistic variants of dimensional and margin complexity. In Conference on Learning Theory, pp. 2236- 2262. PMLR, 2020.
Jared Kaplan, Sam McCandlish, Tom Henighan, Tom B Brown, Benjamin Chess, Rewon Child, Scott Gray, Alec Radford, Jeffrey Wu, and Dario Amodei. Scaling laws for neural language models. arXiv preprint arXiv:2001.0836/ 2020.
Mehran Kardar. Statistical physics of fields. Cambridge University Press, 2007.
Jaehoon Lee, Yasaman Bahri, Roman Novak, Samuel S. Schoenholz, Jeffrey Pennington, and Jascha Sohl-Dickstein. Deep neural networks as gaussian processes. In International Conference on Learning Representations (ICLR), 2018.
Jaehoon Lee, Lechao Xiao, Samuel S. Schoenholz, Yasaman Bahri, Roman Novak, Jascha Sohl- Dickstein, and Jeffrey Pennington. Wide neural networks of any depth evolve linear models under gradient descent. In Advances Neural Information Processing Systems (NeurIPS), 2019.
Jaehoon Lee, Samuel S. Schoenholz, Jeffrey Pennington, Ben Adlam, Lechao Xiao, Roman Novak, and Jascha Sohl-Dickstein. Finite versus infinite neural networks: 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.02 222000002218.... 2020. URI. https: /ttppp://arxiee wttp//iivvv.. o abs / 2003. 02218
Fanghui Liu, Zhenyu Liao, and Johan Suykens. Kernel regression in high dimensions: Refined anal- ysis beyond double descent. International Conference on Artificial Intelligence and Statistics, pp. 649-657. PMLR, 2021.
11

---

Under review as a conference paper at ICLR 2023
Bruno Loureiro, Cedric Gerbelot, Hugo Cui, Sebastian Goldt, Florent Krzakala, Mare Mezard, and Lenka Zdeborová, Learning curves of generic features maps for realistic datasets with a teacher- student model. Advances in Neural Information Processing Systems, 34:18137-181511 2021.
Yue M Lu and Horng-Tzer Yau. An equivalence principle for the spectrum of random inner-product kernel matrices. arXiv preprint arXiv:2205.06308, 2022.
Neil Mallinar, James B Simon, Amirhesam Abedsoltan, Parthe Pandit, Mikhail Belkin, and Pree- tum Nakkiran. Benign, tempered, or catastrophic: A taxonomy of overfitting, arXiv preprint arXiv:2207.06569, 2022.
J Mereer. Functions of positive and negative type and their connection with the theory of integral equations. Philosophical Transactions of the Royal Society of London, 209:4-415, 1909.
Preetum Nakkiran, Behnam Neyshabur, and Hanie Sedghi. The deep bootstrap framework: Good online learners are good offline generalizers. arXiv preprint arXiv:2010.08127, 2020.
Preetum Nakkiran, Prayaag Venkat, Sham M. Kakade, and Tengyu Ma. Optimal regularization can mitigate double descent. In International Conference on Learning Representations, ICLR, 2021.
Roman Novak, Lechao Xiao, Jiri Hron, Jachoon Lee, Alexander A. Alemi, Jascha Sohl-Dickstein, and Samuel S. Schoenholz. Neural tangents: Fast and easy infinite neural networks in python. CoRR, abs/1912 912.02833,, 2019. URL
02803
Manfred Opper. Regression with gaussian processes: Average case performance. Theoretical as- pects of neural computation: A multidisciplinary perspective, pp. 17-23, 1997.
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Kopf, Edward Yang. Zachary Vito, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala. Pytorch: An imperative style, high-performance deep learning library. In Advances in Neural Information Processing Systems 32, pp. 8024 8035.
Curran Associates, Inc., 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- ence on Machine Learning, pp. 5301-5310. PMLR, 2019.
Dominic Richards, Jaouad Mourtada, and Lorenzo Rosasco. Asymptotics of ridge (less) regres- sion under general source condition. In International Conference Artificial Intelligence and Statistics, pp. 3889-3897. PMLR, 2021.
Jascha Sohl-Dickstein, Roman Novak, Samuel S Schoenholz, and Jaehoon 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-350, 1999.
Peter Sollich. Gaussian process regression with mismatched models. In Advances in Neural Infor- mation Processing Systems, pp. 519-526. MIT Press, 2001.
Peter Sollich and Anason Halees. Learning curves for gaussian process regression: Approximations and bounds. Neural computation, 14(6):1393-1428 2002.
Stefano Spigler, Mario Geiger, and Matthiuu Wyart. Asymptotic learning curves of kernel methods: empirical data versus teacher-student paradigm. Journal of Statistical Mechanics: Theory and Experiment, 2020(12): 2020.
Lili Su and Pengkun Yang. On learning over-parameterizee neural networks: A functional approxi- mation perspective. arXiv preprint 1905. 2019.
Umberto M Tomasini, Antonio Sclocchi, and Matthieu Wyart. Failure and success of the spectral bias prediction for laplace kernel ridge regression: the case of low-dimensional data. In Interna- fional Conference on Machine Learning, pp. 21548-21522 PMLR, 2022.
12

---

Under review as a conference paper at ICLR 2023
Guillermo Valle-Perez, Chico Camargo, and Ard A Louis. Deep learning generalizes because the parameter-fume funnctionn map is biased towards simple functions. arXiv preprint 180.:088000 2018.
Alexander Wei, Wei Hu, and Jacob Steinhardt. More than a toy: Random matrix models predict how real-world neural representations generalize. In International Conference on Machine Learning, Proceedings of Machine Learning Research, 2022.
David H Wolpert. The lack of priori distinctions between learning algorithms. Neural computation, 8(7)1144113300, 1996.
Denny Wu and Ji Xu. On the optimal weighted & regularization in overparameterized linear regres- sion. Advances in Neural Information Processing Systems, 33:10112-10123, 2020.
Zhi-Qun -in John Xu, Yaoyu Zhang, Tao Luo. Yanyang Xiao, and Zheng Ma. Frequency principle: Fourier analysis sheds light on deep neural networks. arXiv preprint ar0iv: 065233, 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 arXiv: arXhv:1808.04295 2018.
Greg Yang and Hadi Salman. A fine-grained spectral perspective neural networks. arXiv preprint /0t7:/9900.0999 2019.
13

---

Under review as a conference paper at ICLR 2023
A NOTATION DICTIONARY AND COMPARISON WITH RELATED WORKS
Tables 2 and provide a dictionary between the notations of our paper and the nearest related works. Rows should be read in comparison with the top row and interpreted "when the present paper writes X, the other paper would write for the same quantity." Comparing expressions for test MSE in Table and predicted function covariance in Table makes framework permits simpler and much more interpretable expression of these results than previously given.
makes it very clear that our learnability
Table 1: Notation dictionary between the present paper and related works (part 1).
Paper
# samples
ridge
noise
eigenvalues
eigenfns
eigencoeff's
(ours)
5
e²
A
Bordelon et al. (020))
P
X
NA
X
1/2 Xp
vpp
1172 Wi
Canatar et al. 2021
P
X
o²
Ppp
1)p
1/2
wp
7p 1/2 wp
Jacot al. (2020)
N
N
e²
dg
f(k)
(f(R), f*)
Cui et al. 202
n
nd
a²
T]
Φx
1/
1/2 0%.
Table Notation dictionary between the present paper and related works (part 2).
Paper
eff. reg. overfitting coeff.
test MSE
(ours)
K
Eg
E(f) = Eo (E,
22, + c?)
Bordelon al.
*+ 2020
(1
Eg Ep a
p.
-2
1 (2+1)²
(1+2)²
do
Ate
Canatar et al.
2021
8
Eg = 1- Ep
"p
(k2202 + o² Pmp))
I-g
(x+P
Ñe Oxll (11o=
Āo)s (TTo-A))) +
Jacot et al.
2020
0
020
2 u2 ksl (e/ntin to²
Cui et al. (202 9
2
kg
1-
(
kml (s/ntn))
Cui et al. 2021 simplitications of the expressions of Loureiro al. 202 10.1). whose notation does map cleanly onto tables.
'The overfitting coefficient and test MSE estimator of Cui et al.
2021 appear more complex than the
alternatives in part because other works define intermediate quantities like Ea, 7, etc., which include sums over eigenmodes.
14

---

Under review as a conference paper at ICLR 2023
Table 3: Notation dictionary between the present paper and related works (part 3).
Paper
predicted fn covariance
Cov (Vi, 53] CEE()
(ours)
dij
n
Bordelon et al. (2020)
NA
Canatar et al.
(021)
MTVD "/a w3} = T-y
(02 + R2 Ep (Pnu +mo??
p
(Pou PN SaB
Pm
Jacot et al.
2020
10
V&U A.N.) DAd(A)
(1((c-Ao)) +o2 + (5tt), 8 (o(A)+da))
(2
o7 [o(A)+d,)
Cui et al.
2021)
NA
Sollich ) derived the omniscient risk estimate in the context of GP regression and was, to our knowledge, the first to obtain the result. As its notation does not map cleanly onto the variables we use, we do not include this work in the above tables. Other analogous works include Wu &
Xu (2020), Richards et al. (02T). Hastie et al. (022) (see Definition 1) and Bartlett al. (2021) (see Theorem 4.13), which derive comparable equations for the test MSE of linear ridge regression (LRR), which, taking the dual view of KRR as LRR in the kernel embedding space, is essentially
the same problem. All comparable works involve solving a self-consistent equation for an effective regularization parameter, which we call x in our work.
It worth pointing out that this literature is largely divided into two parallel camps: the works in the tables above, together Loureioo et al. (2021) Cohen et al. (202T) (who study GP regression using field theoretic tools), study the generalization of KRR, largely using approaches from statisti- cal physics, while Dobriban & Wager (018); Wu & Xu (2020); Richards et al. (202T): HHasti et al. 2022 Bartlett al. (2021) study LRR using random matrix theory. Despite studying virtually the same problem, these camps have largely developed unaware of each other, and we hope the present paper helps unify them. The KRR works all rely on approximations, particularly the spectral "uni- versality" approximation that the eigenfunctions are random and structureless and the design matrix can thus be replaced by a random Gaussian matrix. The works of Bordelon al.] (2020); Canatar iet al. (202T). as well as ours, make additional approximations valid for reasonable eigenspectra and large n, while et al. (2020) does not make approximations and provides bounds instead (though these bounds diverge at zero ridge, highlighting the difficulty of studying interpolating methods). On the other side, the LRR works do not make a unversality approximation, but instead assume their setting that the feature vectors are high-dimensional and have Saussianniiann moments (or some sim- ilar condition). which ultimately amounts to the same condition, now enforced in the setting instead of assumed as approximation. These works are typically mathematically rigorous. Relative the LRR works, one contribution of the KRR works is the empirical observation that this universality approximation is generally accurate in practice even for NTKs at initialization (for NTKs after training, the story appears mixed; see Wei et al. (0022) for evidence for universality and Ba et al.) (2022) for evidence against it).
While our work is generally consistent with other works in the KRR set, we note one discrepancy regarding the covariance of the predicted function. Our expression, Equation [4 agrees with that
of Canatar et al. 2021 12 However, the expression of Jacot et al. (2020), given in Theorem 2, contains an extra Onn ") term (blue in Table 33 dependent upon the target eigencoefficient of the mode in question. This term is small enough that it can be removed without affecting the bounds the authors prove. contributes negligibly when summing over all eigenmodes to compute e.g. test
"Tiis a nontrivial observation, as is not hard to construct contrived cases in which this approximation does not hold, as discussed by /Sollich & Halees (200)). The conditions under which this universality assump- tion holds are an active area of research. A variety of rigorous works have proven this spectral universality assumption in specific -ige-dimensional settings (El Karoui 2010 Cheng & Singer, 2013 Fan & Montanari
2019 Liu 2021 Lu & Yau 2022), and Tomasini al.
2022 has shown it does quite hold in certain
noisy low-dimensional settings.
"EEuattoo 71 in the supplement of their published paper, giving the covariance of the predicted function, contains an spurious extra term, but this has been fixed in the arXiv version.
15

---

Under review as a conference paper at ICLR 2023
squared gradient, but contributes leading order when interrogating the variance of particular mode. A samity-chede calculation that the sum of variance over all modes ought to equal V(f) provides evidence that equations, which lack this term, correct.
Lastly, wc note that Cohen et al. (202I) study Gaussian process regression in the spirit of Sollich 1999) using field theoretic tools. Though they do not explicitly diseuss the omniscient risk estimate, Canatar et al. (2021) note that their "equivalence kernel + corrections" learning curve can be viewed perturbative expansion of the omniscient risk estimate.
B EXPERIMENTAL METHODS
B. SYNTHETIC DOMAINS
Our experiments use both real image datasets and synthetic target functions on the following three domains:
1. Discretized Unit Circle. We discretize the unit circle into M points, X (2x0s(2r]/M)) sin(2nj/MM) MM) Unless otherwise stated, M 256. The eigen- functions on this domain are (o( = 1. (0) = 2 cos(kf), and d% sinkk),, for 1.
2. Hypercube. We use the vertices of the d-dimensional hypercube X {-1, giving M = As stated in Section 6.2 the eigenfunctions on this domain are the subset-parity functions with eigenvalues determined by the number of sensitive bits k.
3. Hypersphere. To demonstrate that our results extend to continuous domains, we perform experiments on the d-sphere St {o Rd+ Ix2 1}. The eigenfunctions on this domain are the hyperspherical harmonics (see, e.g., Frye & Efthimiou (2012); [Bordelon et al. (2000) which group into degenerate sets indexed by E N. The corresponding eigenvalues decrease exponentially with k, and when summing over all eigenmodes when computing predictions, we simply truncate sum at kimax = 70.
Eigenvalues and multiplicities for these synthetic domains are shown in Figure
Unit Circle
8d Hypercube
7-sphere
10
A
B
10-1
10a1
10a
10:5.
10
10
10-1
10-3
D
10a E
10a
F
multplicity
2-
10
10a
10a
10"
1
10a
k
Figure 4HL ReLU NTK eigenvalues and multiplicities on three synthetic domains. (A) Eigenvalues for lo for the discretized unit circle (M = 236). Eigenvalues decrease
as increases except for a few near exceptions high k. (B) Eigenvalues for the 8d hypercube. Eigenvalues decrease monotonically with k. (C) Eigenvalues for the 7-sphere up to = 70. Eigenvalues decrease monotonically with (D) Figenvalue multiplicity for the discretized unit circle. All eigenvalues are doubly degenerate (due and sin modes) except for & = 0 and & = 128. (E) Eigenvalue multiplicity for the 8d hypercube. (F) Eigenvalue multiplicity for the 7-sphere.
16

---

Under review as a conference paper at ICLR 2023
B.2 IMAGE DATASET EIGENINFORMATION
Experiments with binary image classification tasks used scalar targets of #1. To obtain the eigen- information necessary for theoretical predictions, select a large training set with M 0(10*) samples, computing the eigensystem of the data-data kernel matrix to obtain M eigenvalues {A:)a and target vector eigencoefficients v. We then compute theoretical learnability and MSE as normal.
The resulting test MSE predictions obtained this way correspond to an average over the M points in the sample, n of which are in fact part of the training set (compare with the discrete and continuous settings of Appendix H.1 and thus they are too low when n/M is not negligible. We wish to predict purely the off-training-SSe error Eors- We do so by noting that ME nÊ + (M n)Eors and solving for Ecrs (doing the same thing for for learnability). Another solution to this problem is to change the experimental design so train and test data are sampled from the same large pool (as done by Bordelon et al. (2020) and Canatar et al. (2021)), but this trick allows in which train and test data are disjoint. Experimental test metrics for image datasets are computed with random subset of M' O(1)) images from the test set.
standard setup
Eigenvalues and multiplicities for four two-class image datasets are shown in Figure
A
B
10P
MNIST 0/1
MNIST 3/
CIFARIO bird/truck
CIFARIO decr/horse
10
10a
10
10
10a
10" 10 10
10'
Figure 6: Eigenvalues and eigencoefficients for four binary image classification tasks. (A) Kernel eigenvalues as computed from 10 training points as described in Appendix B
Spectra for CIFARIO tasks roughly follow power laws with exponent 11, while spectra for MNIST tasks follow power laws with slightly steeper descent. (B) Eigencoefficients computed from 10a training points. Tasks with higher observed learnability (Figure)
place more weight in higher (i.e., lower-index) eigenmodes and less in lower ones.
B.3 RUNTIMES
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 minutes and depends 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 we do here).
B.4 HYPERPARAMETERS
We conduct all our experiments using JAX (Bradbury et al. 2018), performing exact NTK regression with the neural_tan _tangents library (Novak et al. 2019 built atop it. Unless otherwise stated, all experiments used Sour-hidden-layer ReLU networks initialized with NTK parameterization (Sohl- Dickstein et al.) 2020) with a... = 1.4, σ = .1. The tanh networks used in generating Figure 1.5. Experiments on the unit circle always used a learning rate of .5. while
instead used ow experiments on the hypereube, hypersphere, and image datasets used learning rate of .5 .1 depending on the experiment. While higher learning rates led to faster convergence, they tended to match theory more poorly, in line with the large learning rate regimes described by Lewkowye7
17

---

Under review as a conference paper at ICLR 2023
al. (020). Means and ane-standard--ae seandardddeviatoon error bars always the statistics from several random dataset draws and initializations (for finite nets):
The toy experiment of Sigure[uset only a single trial per eigenmode by design.
Other experiments synthetic domains used 30 trials.
The experiments on image datasets in Figure 2 used 15 trials.
B.5 INITIALIZING THE NETWORK FUNCTION AT ZERO
Naively, when training an infinitely-wide network, the NTK only describes the mean learned func- tion, and the true learned function will include NNGP-kemmel-depedeen fluctuation term reflect- ing the random initialization (Lee et al. 2019). However, by storing a copy of the parameters at t = O and redefining fe(x)) == f((x) fo(x) throughout optimization and at test time, this term becomes zero. We use this trick in our experiments with finite networks.
18

---

Under review as a conference paper at ICLR 2023
C VARYING WIDTH EXPERIMENT
While kernel regression describes only infinitely-wide neural networks, it is natural to wonder whether equations are nonetheless informative outside this regime. Figure compares pre- dicted learnability and MSE with experiment for hypercube eigenmodes with networks with varying widths. Our predictions remain informative down width 50, and lower-frequency modes bet- ter learned at all widths, suggesting that kernel eigenanalysis has a role to play even in the study of feature learning.
width
B
width 500
width 200
1.0
0.8
(D)
0.6
0.4
0.0
1.2
width 100
B
width 50
width 20
1.0k
4 (D)
0.6
0.2
0.0
width
width 500
width 200
1.5
8 (D) (ox)
1.0
0.0
width 100
K
width 50
width
1.5
3 (D) (db)
0.5
0.
72
7b
72
Figure 7: Comparison between predicted learnability and MSE for networks of various widths. (A-F) Predicted (curves) and true (triangles and circles) learnability for four eigen- modes the 8d hypercube. Dataset size varies within each subplot, and the width of the 4HL ReLU network varies between subplots. (G-L) Same as (A-F) but with MSE instead of learnability.
19

---

Under review as a conference paper at ICLR 2023
D EXPLAINING THE DEEP BOOTSTRAP IN KRR
In this appendix, we use the eigenlearning equations to arrive at an explanation of the deep bootstrap phenomenon of Nakkiran et al. (2020). As explained the main text, we study KRR as a proxy for KGF, We begin by finding the relationship between the ridge parameter and the effective training
time (we assume for simplicity that the learning rate of KGF is one). Ali et al. (2019) obtained their result regarding the similarity of KRR and K under the identifcation [time] [ridge] They assume a different ridge scaling than ours, and, in our notation, we identify Tett = nn Their KGF scaling correct for modeling standard supervised learning setup, as can be verified by taking the KGF limit of ordinary minibatch SGD.
To study the effect of this "early stopping" constant k. Recalling Equation 6 defining K.
generalization, must find how finite Ter affects the
n Σ
A A +
(6p
we can easily see that R. S. (n (n En and K 2 T.m) Squeezing k with these bounds, we -1 E; As then x Rs Tall For any Ter, there thus exists some n above which further lower and permit the learning of additional eigenmodes. Let us
find that, when n > Tell
additional data does call this the regularization-iine -lmited regime, and its counterpart (in which Tet is sufficiently large and regularization is effectively zero) the data-limited regime.
We can find the crossover regularization provided knowledge of the eigenspectrum. Let us as- sume that (a T csc(a cs)(a=>>)) a n as n + oc. Extending their analysis finite ridge, we find that, at large n, n = ( 1//a + (dk) or equivalently
i-a for some a 1. Mallinar et al. (2022) show that No = k|a=
1 TenK
(18)
Inspection of Equation reveals that when Tei < Ko then x zs T and when Tear >> Kō then Kg- We thus expect crossover from the regularization -imited to the data-limited regime when
Tell AJ Kin-
In Figure 8 we plot the theoretical omniscient risk estimate using powerlaw eigenvalues (A; i-a) and powerlaw eigencoefficients v? ~ i=9) with a 2 for various n. The close resemblance of these curves to the experimental KRR curves of Figure 3 confirm that our powerlaw toy model is good. If desired, Figures 3 (,B) and Figure 8 can be viewed as the distillation of the DB phenomenon in three stages of increasing artificiality.
It is worth noting that increasing n serves to both decrease x and decrease Eg. For powerlaw spec- tra, as n increases with fixed Tet.. En tends to its lower bound of 1. It approaches 1 when the regularization-line limited regime begins.
Similar ideas regarding the scaling of KRR are discussed by Cui et (021)) The notion of regimes limited by either dataset size or training time is explored using the language of scaling laws by Kaplan et al. (2020) and Bahri et al. (202T). We expect that this analysis could be extended to proper KGF using the analysis of Bordelon & Pehlevan (2021).
(20)))
D.1 DEEP BOOTSTRAP EXPERIMENTS
In replicating the deep bootstrap phenomenon for neural networks, use the same experimental setup as Nakkiran et al. (2020), a ResNet-18 88 architecture trained on CIFAR-10 with data augmenta- tion (random horizontal flips and random crops). We optimize cross-entropy loss using SGD, with batchsize 128, momentum 0.9, and initial learning rate 0.1 with cosine decay. The test/train curves are the mean of 4 training runs; the curves have been coussian-smoothee noise artifacts.
remove high-frequency
Moor precisely, they study linear ridge regression and linear gradient flow, but their result also applies to the kemeliied versions of these algorithms.
20

---

Under review as a conference paper at ICLR 2023
We perform kernel ridge regression (KRR) using the NTK of a fully-comnected network with four hidden layers of width 500. We binarize MNIST into two classes: {0, 1, 4] and {5, 6, 7, 8, 9}. Although the test curves shift slightly depending the binarization scheme, the theory curves all fall within one standard deviation of the empirical curves for all binarizations we tried. The KRR test/train curves the mean of 10 training runs.
10
1: 16
125
S
train
72 1000
10
n 8000
72-000
1
10
104
107
10
Teff
Figure 8: Deep hootstrap theoretical test/train curves for a synthetic kernel spectrum. Here we illustrate the deep bootstrap phenomenon using a hypo- thetical kernel giving powerlaw eigenvalues and eigencoefficients with expo- nent a = 2. In this setting, we note that finite-data test/train curves simul- taneously split from the - oo "online learning curve" (black dot-dashed line). We see that from regularization-limite to data-limited fitting for each n. (We choose a = 2 for clean illustration of the phenomenon; empirically, CIFAR-10 10 and MNIST give spectra with exponents closer to 1.)
rip (vertical dashed lines) predicts the transition
E ADDITIONAL MEAN-SQUARED GRADIENT EXPERIMENTS
In the MSG experiment of we run KRR with polynomial kernel on data sampled from hyper- spheres of varying dimension. The polynomial kernel is K K(x, x!) = 1 + x' + (x x')2 (xT x')3.
We perform this experiment using Py Torch (Paszke et al. 2019 and compute V numerically.
In the MSG experiment of we train finite-width FCNs on eigenmodes on the (discretized) unit circle.
21

---

Under review as a conference paper at ICLR 2023
1.00
0.75
0.50
h =
k: =
0.25
4 h =
0.00
2
2
2
2
2
Figure 9: Predicted function smoothness matches experiment on the unit circle. Theoretical MSG predictions (curves) and empirical values for finite networks (circles) and kernel regression (triangles) for various eigenmodes on the discretized unit circle with M 256, normalized by the ground-truth mean squared gradient of G()) E [I]'
ka. Because this a
discrete domain, smoothness is computed using discretization as G(f) E [f(;;) - f(0)+1)]] where 2 and xj+1 are neighboring points on the unit circle.
F QUANTUM MECHANICAL ANALOGY ANALOGG
F.1 EXPLICIT EQUATION FOR
Here we develop a tight analogy between our picture of KRR and the free Fermi gas. The free Fermi gas consists collection of single-particle orbitals with energies {si}; connected bath of particles at chemical potential In our analogy, we will identify orbital i with kernel eigenmode Each orbital will contain zero or one fermions (n; of orbital given by the Fermi-Dirac distribution to be (n,) (1 + - If we identify
()))). with the occupation probability
&, = In A and μ = In x, we find that (n;) = L;: the orbital occupation probability is precisely the eigenmode learnability.
We can always choose so that eigenmode learnabilities sum to n. This is equivalent to the state- ment that on average. An eigenmode with eigenvalue X; 2 к receives at least half a unit of learnability, and orbital with energy E; S j is occupied with probability at least one half.
always choose the chemical potential y ensure the system contains n fermions
Here we elaborate further the physical analogy laid out in Section 6.4 our system of noninteract- ing fermions, have thus far identified
In A + E, (energy of orbital i)
(19)
In + (chemical potential)
(20)
L. + (m:) (expected occupancy of orbital i).
(21)
What is the value of x? Observe that
(m.)
(22)
+ eFI-H
gives the expected occupation number in the grand canonical ensemble where the total number of fermions is allowed to fluctuate. By the equivalence of thermodynamic ensembles, expect to get the same answer for (n.) in the canonical ensemble where the total number fermions does not fluctuate and is exactly n. This suggests that should attempt to compute (n.) in the canonical ensemble. By comparing the answer to the grand canonical expression, we can solve for μ and hence for
22

---

Under review as a conference paper at ICLR 2023
We assume total number of orbitals M > (which may be infinite). Note that the equivalence of ensembles holds only in the thermodynamic limit n > 1, so we must take this limit at the end.
In the canonical ensemble, each microstate is labeled by of a list of indices 1 S < jn S M corresponding to the occupied orbitals. Direct computation of the canonical partition function shows that
Zc = =m ...,,,
(23)
where m, is the so-called "elementary symmetric polynomial of order n":
my m2 (21......, TM)
Σ
Iy Jn.
(24)
We also define the same with index disallowed:
m (x1, RM)
Σ
J.
(25)
IShRwRR jatiV
We find that
0ln Zc
m mn-1(
6M
(m4)
(26)
dei
Mn (e
EM
Comparing Equations 22 and 26 solving for μu and using Equation 20
we find that
K m,, (A)
X
(27)
(A)
for any i, where À = (Ax) We are free to choose i >> so that X; is negligible, yielding
mn (A)
K
(28)
m (A)
We have arrived at an explicit expression for K. This expression "solves" Equation 6 the implicit equation defining K, in the thermodynamic limit. Numerics easily confirm close match with the implicit solution. While many works have defined similar constants implicitly, this is the first place to our knowledge that the explicit solution appears.
The meaning of x is elucidated by analogy to f in the canonical ensemble. In the canonical ensem- ble, all orbitals are "fighting" for the supply of n particles, and μ represents their "average pull" on each unit. Similarly, in KRR, we can view eigenmodes as competing for the kernel's supply of units of learnability, with λ encoding their average pull on this supply. This analogy deepens our picture of KRR the competition among eigenmodes for fixed supply of learnability.
F.2 ADDITIONAL ANALOGOUS QUANTITIES
Σ, ni concentrates about its mean n and has fluctuations given by Var [V] Σ, (n) (n,)) (since each site constitutes Bernoulli
In the grand canonical ensemble, the total occupation
variable). Comparing with equation g we find that
n2/E <> Var[N].
(29)
Smaller particle number fluctuations in the analogous physical system thus correspond larger Eo and greater overfitting of noise. This provides physical interpretation of the "overfitting as overconfidence" notion of Section 4.2
The grand canonical partition function of our free Fermi gas is
Zoc
(1 + eiit)).
(30)
The analogous quantity in KRR is
ZKRR II (1+ X
(31)
holds that
i In Zoc
(11),
(32)
Op
and indeed we find that
In ZKRR
= n.
(33)
i In
23

---

Under review as a conference paper at ICLR 2023
F.3
UNIVERSAL LEARNABILITY CURVES
Unit Circle
8d Hypercube
7-sphere
1.0
L(oe)
(n 8
All
0.5
0.0
1.0
[(
(n 64)
Av/x
0.5
10" 10
10
10
0.0
10
101
10
10
Ax/ K
Ae
Figure 10: Modewise learnabilities fall universal sigmoidal curves. (A-F) Predicted learn- ability curve (sigmoidal curves) and empirical learnabilities for trained networks (circles) and NTK regression (triangles) for eigenmodes & {0, .... 7} on three domains for 8, 64. Vertical dashed lines indicate K. (G) All data from (A-F) with eigenvalues rescaled by K.
Figure 10 shows that curves of learnability vs. eigenvalue collapse onto a single sigmoidal curve upon rescaling. We note that similar collapse of data from different experiments upon rescaling occurs in many important statistical physies systems including superconductors (Kardar 2007) and turbulent flows (Goldenfeld, 2006).
broadly worth noting that informative constants determined by self-consistency conditions are hallmark of statistical mechanics. It is thus sensible that such constant would be emerge from the replica calculation of Canatar et al. (202I).
G PROOFS: L.ARNABIIITY AND ITS CONSERVATION LAW
In this appendix, we provide proofs of the formal claims of Section We make use of our learning transfer matrix formalism (diseussed in Appendix H.2)) for these proofs it improves clarity and compactness, but all our proofs can also be straightforwardly carried through without it. The learning transfer matrix is defined as
T = A& Φ AΦ + -1,,)) Φb
with @, (x,)) and T Ep [P) It holds that v (P) v. It is easy (by making one-hot vector) that ( T (D) and L(d;) T..
Property (a) L(dx), L (()) 1].
Letting e; be the one-hot unit vector with a one index i, we observe that
((P) = = (P)e
(34)
= e; AΦ ④ T A +LI))
TTe,
(35)
X 1/2 3 + AΦ sIn) Φ Too2 1/2
(36)
z [zz' + M)
E [0, 1].
(37)
where in the third line we have used the fact that e; is unit vector and is diagonal, the fourth line we have defined X & e; and - x A ôI, zz T, and in the fifth line we have used the fact that M positive semidefinite. Given this, L(dx) E [0, 1] by averaging.
Property ((P) = C(f) = 0.
Proof. When n = 0, the predicted function f is uniformly zero, and so we have (P)(f)=((1)
24

---

Under review as a conference paper at ICLR 2023
Remark.
As corollary, it is easy to show that, when M is finite,
M, and
0, then
(PP (J) [() 1.
Property (c) Let D+ be D D x, where E X,x x & D is a new data point. Then C (o.) Z
((P) (o:).
We first use the Moore-Penrose pseudoinverse, which we denote by (-) to cast T(P) into the dual form
T (D)
-1 AΦ ④ AΦ)
$ = A//22 (A A (A1/200) A + +dIM)
A A-1/2,
(38)
This follows from the property of pseudoinverses that A(A for any matrix A. We now augment our system with one extra data point, getting
(AAT)AAA +
((P-) = A/2 (122( + +ES )A/
(A'
T + )A + +8IM)
A-1/2 (39)
A 1/12
where & an M-element column vector. Equations 38 and 39 yield that
(o)) = e, ( e, = <1 T A²/2)) A 41/2200 A + +5IM) +
(40)
((P+) e, ( e ( 11122( ($
+ )A (A (A +EE + ōl
e;
(41)
The rightmost expressions of Equations 40 and 41 both contain factor of the form B(B + 51) where a symmetric positive semidefinite matrix. An operator of this form is a projector onto the row space of B when ō = 0 and variant of this projector with "shrinkage" when these equations, we find that the projectors are the same except that, in Equation 41 there is one additional dimension in the row-space and thus new basis vector in the projector (provided is orthonormal to the other columns of 4; otherwise there are zero additional dimensions).
0. Comparing
In the g (p)) in the ridgeless case. In the case 8 0, singular value decomposition of the projec- tor confirms that the addition still cannot decrease e, ((+))e; This shows the desired property. follows as a corollary that increasing n + + 1 cannot decrease L(.).
this new basis vector cannot decrease e._ TP++)e, and thus ((P+)(()) 2
Property
(d)
P) (bx)) 2 O, ax. L (D) (6)) I 0, and a5 ( S 0.
ax
Proof. Differentiating T(P with respect to a particular Xi we find that
C ( ax;
(bt)
TPP = (ō.g - - K (o)) K- "
(42)
0x
where o, is the ith row of E and K A + SI,. Specializing the case i = j. we note that Φ, K- > 0 because K positive definite, and λ. < 1 because A. is one of the positive semidefinite summands in K Σx d ōI,. The first clause of the property follows.
To prove the second clause, instead specialize to the i + j. which yields that
0 ((()) oy, jj = - (0) K k''
PP) (0,)
(43)
ax
which is manifestly nonpositive because X > 0. The second clause follows.
Differentiating Equation
51 w.r.t. 5 yields that
@ (D) = - A T, We then observe that
06
i
0 T e; = =X,0, ΦK 2Φ e,
(IP) (6.) =
(44)
08
38
25

---

Under review as a conference paper at ICLR 2023
which must be nonpositive because X, 0 and &K T is manifestly positive definite. The desired property follows.
Property| (e) E(f 2 B(f) 2 (1 C(f))²
Noting that |v| |f] = expected MSE is given by
8(J) E [v v) = |v| 2v B
2v
E + [B[
Var [1v]]
(45)
bias 15())
variance V(f)
It is apparent that {(f 2 B Projecting any vector onto an arbitrary unit vector can only decrease its magnitude, and
B(f) 2 1- 2v E v + E vv T E[v] = (1 v [ =1 -(f))
(46)
G.1 PROOF OF THEOREM 3.2 [CNNSERVATION OF LEARNABILITY)
First, we note that, for any orthogonal basis F on X,
v TT
ΣCP
Σ
(47)
FEF
VEV
where V is orthogonal of vectors spanning R This is equivalent Tr [T(P]. This trace is given by
Tr [(P) Tr $ A A SI,)) Tr [K(K "I,
(48)
When 5 = 0, this trace simplifies to Tr[I,]] = n. When 0, it is strictly less than n. This proves the theorem.
Remark. Theorem 3.2 is a consequence of the fact that (P)) simply projector onto an n- dimensional space spanned by the embeddings of the samples.
H DERIVATIONS: THE EIGENLEARNING EQUATIONS
In this appendix, we derive the eigenlearning equations for the test risk and covariance of the pre- dicted function. Throughout this derivation, we shall prioritize clarity and interpretability over math- ematical rigor, giving derivation which can be understood without advanced mathematical tools and thereby filling a gap in the literature. For formal derivation using random matrix theory, see Jacot et al. (0220). and for derivation using replica calculation of similar level of rigor use here, see Canatar et al. 2021).
In the interest of clarity, begin with brief summary of the appendix. We begin by discussing the problem setting (Section H.... ). We then define the learning transfer matrix formalism (H.2) and
set the ridge parameter and noise zero HH.).. After stating our main approximation (H.4) we find the expectation of the learning transfer matrix (H.3) (.6)). using our conservation law to fix
H.7 H.8). Taking well-placed derivatives, we bootstrap the expectation of the learning transfer
matrix to its second order statistics (H.9) and add back the ridge and noise (H.10). We conclude
with various useful bounds on K HH.11).
H.1 THE DATA DISTRIBUTION
We shall, in this derivation, consider a slightly more general setting than discussed in the main text. In the main text, we supposed the data were drawn i.i.d. from continuous distribution over Idd Here, in addition to this case, shall also consider setting in which the data are sampled without replacement from discrete set X' C R2 with |X = M. We will refer to this as the "discrete setting" and the setting with continuous distribution the "continuous setting." As discussed in Appendix the discrete setting matches several our experiments (namely those on the discretized unit circle and the vertices of the hypercube).
26

---

Under review as a conference paper at ICLR 2023
This discrete setting clearly converges to the continuous setting M - oo: when M > n², the probability of sampling the same point twice is negligible (and so we can drop the "without replace- ment" and sample with replacement as in the continuous setting) and, by distributing A' throughout Rd with point density proportional to p. we approach sampling from a continuous distribution. Al- ternatively, could imagine X' consists of M i.i.d. samples from p, that, when we later sample points from X, they are themselves i.idd samples from as M - co. It is worth noting that the data distribution in e.g. computer vision task is in fact discrete because pixel values are discretized, and thus it is reasonable to work with a discrete measure.
Kernel eigenmodes in the discrete setting are defined as M M K(x,,') (a')) (x)) Note that, in this case, the number of eigenmodes is M, the same number as the cardinality of X. In the continuous setting, the number of eigenmodes infinite (though there may be only finitely many with nonzero eigenvalues), but, like Bordelon et al.) (2020), we will find it useful to assume that we need only consider a finite (but very large) number M. This serves merely permit us to work with finite matrices (to which the standard tools of linear algebra apply) and to thereby save us the trouble of dealing with infinite and semi-infinite matrices, which require greater care. So long as M is sufficiently large, we do not lose anything in discarding the exceedingly small eigenvalue tail AssM- M, as is typical in the study of kernel methods and as our final results will confirm.
Our subsequent derivation will generally apply to both the discrete and continuous settings.
H.2 THE LEARNING TRANSFER MATRIX
We begin by translating the KRR predictor into the kernel eigenbasis. Because K(x, 2') = Σ i= (10;()) we can decompose the empirical kernel matrix as KDD = 4 T A where diag(A1, ..., Aad) and + is the M x n "design matrix" given by i; = (x,))
The predicted function coefficients v are given by
V: (di, f) (KDD + 51,)) -
(49)
where we have used the orthonormality of the eigenfunctions and defined [øil; dx(z,) to be the i-th row of T Stacking these coefficients into a matrix equation, we find
V A +
A SI,)
+ VV==T(P v
(50)
where the learning transfer matrix
(P)) AΦ ④ A $
(51)
is M x M matrix, independent of ʃ, that fully describes the model's learning behavior on training set [ The learning transfer matrix is the same as the "reconstruction operator" of Jacot al. (2020) viewed as finite matrix instead of linear operator. Full understanding of the statistics of T P) will give us the statisties of and thus of f, and so our main objective will be to find the mean and the covariance of (P))
H.3 SETTING THE RIDGE AND NOISE TO ZERO
Our setting includes both nonzero ridge parameter and nonzero noise. However, it is by this point modern folklore that many small eigenvalues together act as an effective ridge parameter equal to their sum and that power in zero-eigenvalue modes is effectively noise (see e.g. Canatar et al. (202T) for a discussion of these). Inverting these equivalences, we should expect to be able to convert into a small increase to many eigenvalues and convert e² to power in a zero-eigenvalue mode, and thereby permit ourselves consider neither ridge nor noise in our derivation and add them back at the end. Here explain our method for doing
The ridge parameter can be viewed as a uniform increase in all eigenvalues. We first observe that M M &- I, in the discrete case. Letting T(P) 6) denote the learning transfer matrix with cigenvalue matrix A and ridge parameter 8, it follows from Equation (1aiionnn]aamm and this fact that
8
8 M IM :0). 0).
(P)();;) = A A
IM
(DD)
A+
(52)
M
"We take this terminology from control theory in which, for system under study, "transfer function" maps inputs outputs, or driving response.
27

---

Under review as a conference paper at ICLR 2023
In the continuous case, M - - In as M oo (since the columns of + uncorrelated), and since M is very large in the continuous setting, we are again free to use Equation 52
As for the noise, simply set e² = 0 for now and, once have our final equations, add power e² to hypothetical zero-eigenvalue mode.
H.4 ASSUMPTION: THE UNIVERSALITY OF 4
We wish to take averages over in finding the statistics of T(P), The distribution of 4 is fact highly structured (reflecting the eigenstructure of the kernel), and we know only that E ( Eyy-. We neglect this structure, making the "universality" assumption that we may take o to be sampled from a simple Gaussian measure without substantially changing the statistics of T(P), We henceforth assume iúj iid ().
This universality assumption is also made in comparable works (implicitly by Bordelon et al. (2020);
Canatar al.] (202T) and explicitly by Jacot et al. (2020). See Appendix [A further references to relevant literature. The validity of this approximation is ultimately justified by the close match of our theory with experiment.
H.5
VANISHING OFF-DIAGONALS OF E T()
We next observe that
Ex
AΦ
S U
AU -1 T Ex AU
(Φ
A
+ U
(53)
where U is any orthogonal M x M matrix. Defining U(m) the matrix such that U(m) (m)
8as
26am), noting that U (m)) A. and plugging Umm) as in Equation 53
we find that
E
T
(D)
(U(())
T(P) U(m) (-1) Bim E
T
(P) ab
(54)
By choosing m a, conclude that [P)
ab
0 if a + b.
((P)
(D)
H.6
FIXING THE FORM OF
H.6.1 ISOLATING THE DESIRED ELEMENT
We now isolate particular diagonal element of the mean learning transfer matrix. To do write E (P() in terms of x (the ith eigenvalue), (9) (A with its ith row and column removed),
$
(the äth row of 4), and T ( (Ø with its ith row removed).
Using the Cherman-Morrisee matrix inversion formula, we find that
ΛΦ -1
Arc $
( (1)
(1)
Φ.Φ.T
(1))A1))
(())
(55)
-1
(8)
A
1 +
A1)
Φ
28

---

Under review as a conference paper at ICLR 2023
Inserting this into the expectation of T(P,, we find that
T
1 T
AΦ)
$i
2
X2
(1)
Φ
(1)
$
Φi
+ dook
(1))
$
Φ
(56)
A +
Φ
$ (1)
(1)
(1)
Φ
X
A5 + x 1 (.))
where xe $ (1)
= x(())
Φ
Φ (1)
(1) ( (
-1
Φi
a nonnegative scalar.
(.)
H.7 CONCENTRATION AND MODE-INDEPENDENCE OF KG
Important quantities statistical mechanics systems are typically self-averaging (i.e. concentrating about their expectation) in the thermodynamic limit. Self-averaging quantities are the focus of random matrix theory, and generalization metrics machine learning also tend be self-averaging under most cireumstances (e.g. resampling the data and rerunning training procedure will typically yield similar generalization error). Here we argue that k self-averaging the thermodynamic limit and can be replaced by its expectation.
This could be shown rigorously by means of random matrix theory. Here we opt to simply observe
that, if K; were not self-averaging, then for modes i such that A K; T((P) and thus CPP) (ó.) would not be self-averaging either. However, because C(P) (Φ;) is a generalization metric like MSE, we should in general expect that it is self-averaging at large n. Our experimental results (Figure 2
confirm that fluctuations in (di) are indeed small in practice, especially large n. We thus
replace kg ($) with its expectation Ka Ex
We next argue that K2 is approximately independent i, so we can replace it with a mode- independent constant This, too, could be argued rigorously by means of random matrix the- ory. We opt instead for an eigennode-removal argument inspired by the cavity method of statistical physics (Del Ferraro al., 22044). Observe that, in the thermodynamic limit, the addition or removal of a single eigenmode should have negligible effect on any observable and thus on Kg. We shall here show that, by inserting one eigenmode and removing another, can transform K; into K, for any and j. implying that K4 R Ki.-
Assume that the addition or removal of single eigenmode negligibly affects K,, Concretely, assume that K; re R.T, where K is K; computed with the addition of one extra eigenmode of arbitrary eigenvalue. We choose the additional eigenmode to have eigenvalue X and we insert index i, effectively reinserting the missing mode into (()) and (())
To clarify the random variables in play, we shall adopt more explicit notation, writing out (()) in terms of its row vectors as P(1) = [ØI.... Φ 05+1. ΦM Using this notation, we find upon adding the eigenmode that
29

---

Under review as a conference paper at ICLR 2023
-1
K; = cy
pi 4
(1)
Φ
(57)
(ox Mn
OT (10), ..., Φ P141, Das (m)01 0: )
pi
(58)
K.
S., @1+ ØMl
Φ
(59)
where A is the original eigenvalue matrix and o. is the design matrix row corresponding to the new mode.
We can also perform the same manipulation with Kj Gj * i), this time adding an additional eigen- value A at index j. yielding that
N2 = B
④ ()
(0)
$
(60)
[J) (106,,... $1 pM - $5/
= ( Jim
(61)
(1b), (10 ,5 AMl (,
2 KJ = E
( MM
|/ ΦM
Φ)
(62)
We now compare Equations 59 and 62 Each is an expectation over M + vectors from the isotropic measure. T he statistics of these M + 1 vectors are symmetric under exchange, so we are free to relabel them. Equation 59 identical to Equation 62 upon relabeling Φ; Φj. Φ: + Φi and Φj + Φ,. so they are equivalent, and x x This in turn implies that K; se Kg. In light of this, replace all Kę with mode-independent (but as-yet-unknown) constant and conclude that
E T P
88s
A A +
(63)
In summary, we have argued that K; is not significantly changed by the addition or removal of single eigenmodes, and two such changes permit us to transform K; into Ky, so they are therefore approximately equal.
Our argument here is similar the cavity method of statistical physics (Del Ferraro et al. 2014 4) which essentially compares the behavior of weakll-interacting system with and without single element. The cavity method is often used as a simpler and more intuitive alternative to the replica method, role it reprises here (contrast our approach with the replica approach of Canatar et al. 2021
H.8 DETERMINING
We can determine the value of x by observing that, using the ridgeless case of Theorem 3.2
ΣE(TP] Σ
A A + =
(64)
This is much more straightforward method of fixing this constant than used in comparable works. The ability to use the ridgeless version of Theorem 3.2 is the main motivation for setting d = at the start of the derivation.
30

---

Under review as a conference paper at ICLR 2023
H.9 DIFFERENTIATING W.R.T. A TO OBTAIN THE COVARIANCE OF T(P)
Here we obtain expressions for the covariance of (P) and thereby the covariance of V. Remarkably, we shall need no further approximations beyond those already made in approximating E [T()], which lends credence to our thesis that understanding modewise learnabilities is sufficient for un- derstanding more interesting statistics of f.
We begin with calculation that will later be of use: differentiating both sides of the constraint on K with respect to a particular eigenvalue, find that
a
M
M
Ōk
K
0,
(65)
a\:
K
13)
04,
(A:+ K3)
==1
j=1
yielding that
Ōk
n²2
M
k2 ()g + k)²
where
q
(66)
a(>; + x)²
j=1
We now factor TDP) into two matrices as
(P) AZ,
where
AΦ)
TT.
(67)
Unlike T(P), the matrix Z has the advantage of being symmetric and containing only one factor of A. We will find the second-order statistics of Z. which will trivially give these statistics for (D) From Equation 63 we find that the expectation of
E Z
(A + KIM)
(68)
We also define a modified Z-matrix Z = + ( T AU TT, where U is an orthogo- nal M x . matrix. Because the measure over which & is averaged is rotation-invariant, we can equivalently average over d U with the same measure, giving
E [i]
Es
T
AΦ
$ TT
Es
U
UTZU = UA -
(69)
It is similarly the case that
Ex
(Z ( joy (Z
E& (UTZU),, (U ZU) kt
(70)
Our aim will be to calculate expectations of the form Es [Z, Zur] With a clever choice of U, a symmetry argument quickly shows that most choices of the four indices make this expression zero.
We define U((r) = 8av(1 25am) and observe that, because is diagonal, (U(m)) (((m) A
and thus (U(m) Z. Equation 70 then yields that
Eq. Zij Zue] (-1)dim +.5m +8 Exg [Zg Zue),
(71)
from which it follows that E. Zze] = 0 if any index is repeated an odd number of times. In light of the fact that Z.,- Zyc, there are only three distinct nontrivial cases to consider:
1. Ex [Z Zu].
2. E. [Z, Z,y] with * j. and
3. EA 7 with + j.
31

---

Under review as a conference paper at ICLR 2023
We note that are not using the Einstein convention of summation repeated indices.
Cases and 2. We now consider differentiating Z with respect to a particular element of the matrix A. This yields
FZ 02 ( ( AΦ) 0A jk
D50K (ΦTAΦ) A -1
Φr -Zez
(72)
where as before Φ; is the i-th row of Φ. This gives us the useful expression that
E Ziy Zac]
BlZ.e]
(73)
0Ajk.
We now set l k j and evaluate this expression using Equation 68 concluding that
a 1 (xx+x) (2 (2+ k32
1
6os (Big
On.
0x, aa,, E - =
(74)
ax,
and thus
8x (Ae + k=2 0b,
x²
Cov (Zij, Z,y] Cov [Zy Zyd
(75)
g(>: + () + x2)²
We did require that * j. and so Equation holds for Case as well as Case 2.
Case 3. We now aim to calculate E Z, F,y for i * j. We might hope to use Equation 73 in calculating [ZZZZ but this approach is stymied by the fact that we would need to take derivative with respect to Aij. but we only have an approximation for Z for diagonal A. We can circumvent this by means of (U), From the definition of Z(U), we find that
a
Z
(t)
OU ij
dU
ji
UUIN
=-
AΦ
[
0 + =.N00 - o c AA 8
= - X1) (Z) + Z, Z (76)
Differentiating with respect to both Uy and Uy with opposite signs ensures that the derivative is taken within the manifold of orthogonal matrices. Now, using Equation 69 we find that
0
δ a
E [
U UT
(A -IM)
U
U
aU
U=IN
U=I
(77)
1
A +
K
A +
Taking the expectation of Equation 76 plugging in Equation performing some algebra, we conclide that
74 for E.. [2y]] comparing to
77 and
R² q(>: - k))(A, + x)²²
E Z.
(78)
(A: + x)( + +x)
and thus that Zu. Zij anticorrelated with covariance
32

---

Under review as a conference paper at ICLR 2023
Cov [Z, 25y =
(79)
ạ(A: + k)) + x22
Cases 1-3 can be summarized as
x² b1 + 8110,1 - δt5ōkE)
Cov (Zi Zue] = g(> + (A; + (Ax k))(2e + +R)
(80)
Using the fact that T
A,Zig defining C; = de(Ae + x)) and noting that =
E. -, we find that
-be) - Lx) - Le) m==1
Cov
TDD) 1j
(D))
(D)
(8s2dge + dssdzk deg
(81)
11
Noting that E(f) = E || - v/2 recalling that v = T(D),, and using Equation 81 to evaluate a sum over eigenmodes, we find that expected MSE is given by
E(f)
2
(82)
Σ C
Taking a sum over indices of v, we find that the covariance of the predicted function can be written simply in terms of MSE
(E
Cov [P,, V,]
dgg.
(83)
H. ADDING BACK THE RIDGE AND NOISE
We have thus far assumed 8 = O. We can now add the ridge parameter back using Equation
52
To add ridge parameter 8, we need merely replace >; - Ai
8 and then change T (D)
(x + - This yields that
83.4 A
(84)
X +
6 M7
+
K 5d + 5.e0gr - -8.5
Cov (T) (D) T(()]
(85)
(A= +
á M
+ (2 + 34 (>) + 1o + x)( + $ + x))
A +
5
\ラ , و
where x 2 0 satisfies
M
and
q
Σ
M
(86)
A + M
+
(As + M x)2
Taking either 5 0 or M -> oo, we find that
A A +
5
(87)
and the mean and covariance of (P) are again given by Equations 63 and
To summarize this simplification: in the continuous setting (M + oo), recover the results of prior work. In the discrete setting with zero ridge, we find that these expressions apply unmodi- fied. In the discrete setting with positive ridge, find that these expressions contain corrections A with perturbative parameter x the main text, we report the expressions with A experiments obey this condition.
M = 0, and our
33

---

Under review as a conference paper at ICLR 2023
Modifying to place power e² into eigenmode with zero eigenvalue, Equation 82 for MSE becomes
E(f) = & -0-2))
(88)
H.11 PROPERTIES OF
In experimental settings, k in general easy to find numerically, but for theoretical study, we antic- ipate it being useful to have some analytical bounds on in order to, for example, prove that certain eigenmodes are or are not asymptotically learned for particular spectra. To that end, the following lemma gives some properties of
A.tk E with positive eigenvalues {Ne ordered from greatest least, the following properties hold:
Lemma H.1. For K. 2 O solving Σ
A
(a) k when 0, and 0 when M and 8 O.
(b) x strictly decreasing with n.
(c) x v - (6+ Eise+1 2:) for all & E (O,..., n 13.
(d) K 2 de ( - 1) for all l {n,...MM,
Proof of property (a): Because Ei= A,tr + is strictly decreasing with x for k 2 O, there can only be one solution for given n. The first statement follows by inspection, and the second follows by inspection and our assumption that all eigenvalues
strictly positive.
Proof of property (b): Differentiating the constraint on i with respect to yields
M
A +
8
dn dn which implies that dn
dx
M
= 1,
O.
A
K)²
R2
(A:
x)²
k²
(89)
Proof of property (c): We observe that E M property follows.
S l Diet+ d 5 The desired
Proof of property (d): We set ê = 0 and consider replacing A, with x if < l and Oif > Noting AA.
that this does not increase any term in the sum, we find that n = Σ Ar
Xr+x X
The desired property in the ridgeless case follows. A positive ridge parameter only increases K. so the property holds in general. We note that a positive ridge parameter can be incorporated into the bound, giving
K 2
(e - m)Ae + 8+ ((e n)Ae 5)² 4ndde
(90)
2n
We also note that, as observed by Jacot et al. 2020 and Spigler et al. (2020), the asymptotic scaling of k can be fixed if the kernel eigenvaluee ues follow power law spectrum. Specifically, if X; i-a for some a >> 1, then Jacot et al. 22000 show that
K O(ōn + "))
(91)
Jacot al. (200 scale the ridge parameter proportional to in their definition of kernel ridge regression; reproduction of their result accounts for this and applics convention.
34


Reviews:
[{"review_id": "lWf28q7Hi0B", "reviewer": "Reviewer_zi9Y", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "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": "", "summary_of_the_paper": "This paper proposes a quantity called the \"learnability\" of a kernel, and shows that this satisfies a \"conservation law\". This is applied in four scenarios:\n\ni) to explain \"deep bootstrap\" of Nakkiran et al\nii) to prove a result on the hardness of the parity problem by kernels\niii) to study adversarial robustness\niv) to investigate the relation between kernel ridge regression and quantum mechanics.", "summary_of_the_review": "Unfortunately, because of the weaknesses I have written above, I do not recommend accepting the paper at this time.", "strength_and_weaknesses": "## Strengths\nThis paper provides a convenient heuristic to predict the test MSE of a kernel ridge regression (and its bias and variance), as well as the train MSE. The authors use it to power several applications. The most interesting application is perhaps an explanation of the deep bootstrap effect . The authors' analysis extends results by Ghosh et al. 2022 that apply to spherically-distributed data, to any kernel with power law eigenvalue \ndecay.\n\n## Weaknesses\nThere are some weaknesses that the authors should address.\n### Level of formality\nIt is unclear what is proved and what is not. For example, in equations (6) through (14) it is not clear what is proved in the main text. The arguments in appendices H.6 and H.7 are informal, which is fine, but I feel that it should come with a disclaimer in the main text.\n\n### Novelty of the framework\nBe more specific in comparison to Canatar et al. '21 and Jacot et al. '20? It seems similar to the former.\n\n### Novelty of the conservation law\nThe main conservation law, Theorem 3.2, essentially follows from the representer theorem for kernels:\ngiven training data points $(x_i,y_i)\\_{i \\in [n]}$, kernel ridge regression will learn a function of the form $\\hat{f}(x) = \\sum_{i=1}^n \\alpha_i K(x,x_i)$, for some scalars $\\alpha_i$. Therefore, the best one can do to minimize MSE is to learn the projection of the target function $f$ onto this $n$-dimensional space $V$ spanned by the functions $K(x,x_i)$ for $i \\in [n]$.\n\nSo (when $\\delta = 0$) the \"learnability\" of $f$ is $\\mathcal{L}(f) = \\langle f, \\Pi_V f\\rangle = ||\\Pi_V f||^2$. The conservation law states that for any \northonormal functions $f_1,\\ldots,f_m$ we have $\\sum_{i=1}^m ||\\Pi_V f_i||^2 \\leq n$. However, this can be seen by writing $||\\Pi_V f_i||^2 = \\sum_{j=1}^n \\langle v_j, f_i \\rangle^2$, where $v_1,\\ldots,v_n$ is an orthonormal basis of $V$, and switching order of summations. (Note this is essentially the same proof as remarked in Section G.1.)\n\nThe above proof is the basis for the kernel lower bounds technique surveyed in the note by Daniel Hsu https://www.cs.columbia.edu/~djhsu/papers/dimension-argument.pdf, which extends beyond $f_1,\\ldots,f_m$ being orthonormal. It has been the basis for many recent lower bounds for kernels, and is not new.\n\n### Application 2: Hardness of parity problem by rotationally-invariant kernels\nThis result is known (see the Daniel Hsu note). Note that it is true for permutation-invariant kernels (which are a superset of rotationally-invariant kernels). \n\n### Application 3: Adversarial robustness\nPlease specify what the function $f$ is. Is it just $\\mathrm{sgn}(x_1)$, or a smoothed version?\n\nPredicted function smoothness does not seem to match experiment as you take $d$ larger in Figure 4. Why only test for $d \\leq 8$, if the claim is about high-dimensional functions?\n\n### Application 4: Investigation of relation between kernel ridge regression and quantum mechanics\n\nThis section (and Appendix F) has plenty of physics terminology and was difficult for me to understand. The connection to Fermionic particles seems to go through, but I don't understand what the takeaway is? The sigmoidal relationship between $\\mathcal{L}_i$ and $\\ln(\\lambda_i)$ seems  apparent without having to appeal to physics. Simply because by definition $\\mathcal{L}_i = \\frac{\\lambda_i}{\\lambda_i + \\kappa}$.\n\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "ZEvWGiAQbm", "reviewer": "Reviewer_R9g9", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper presents simplified  closed-form estimates for the test risk and other generalization\nmetrics of kernel ridge regression. Compared to prior work, the authors claim their derivations\nare greatly simplified and lead to higher interpretability. Test risk and other objects of interest \nare expressed in a transparent, interpretable way in terms of the conserved quantity evaluated \nin the kernel eigenbasis. Among others, the main contributions include a theoretical explanation\nfor the “deep bootstrap” of Nakkiran et al. (2020), as well as a generalization of a result regarding \nthe hardness of the classic parity problem.", "summary_of_the_review": "To the best of my knowledge the theory appears correct and the analysis reasonably novel. I choose \"marginally above threshold\" but I am happy to change my score if the authors provide more clarity.", "strength_and_weaknesses": "-) The paper is well-written and clear (apart from parts of the text which are made more complex than necessary using viewpoints borrowed from physics). \n-) The experimental results are interesting and carry the main message with sufficient clarity. \n-) Figure 1. Please explain what 1HL and 4HL mean.\n-) The paper considers some concepts from a physics perspective which might be hard to follow for people without this background.\n-) I do not fully understand why Theorem 3.2 is a \"Conservation Law\". My best understanding is the authors use this phrase because \nthe learnability remains fixed (in expectation) as the dataset evolves? This term is confusing, and rather un-necessary. For example, I can reach the global minimum of a strictly convex problem (assuming there is one) for any starting point. Is this a conservation law?\n-) it would be nice to add more details regarding the training phase with eigenfuctions.", "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": "A16ETga1IcQ", "reviewer": "Reviewer_F6bZ", "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": "", "summary_of_the_paper": "The paper presents a framework to describe the capacity of KRR to generalize different types of functions. An ability to generalize a function f is measured by the so called learnability (a measure that has a version that depends on training set inputs as well as a version that is expectation of the latter value). A key result is Theorem 3.2 that formulates a conservation of learnability. Authors claim that this result is similar in spirit with well-known “no-free-lunch” theorems of Wolpert.", "summary_of_the_review": "Though some claims are not substantiated, a novelty of the framework is a strong side of the contribution.", "strength_and_weaknesses": "Among experimental results presented, the first one, described in Fig 1, seems to me the most valuable. The fact that even for moderate size widths, neural networks almost follow the same conservation of learnability, seems surprising (or this is true only for small n?). Why does this happen? IMHO, this should be discussed deeper, some additional comments are needed. Does this mean that for any architecture, from NTK one can correctly predict which functions are better learnable? This would be a very strong statement.\n\nSection 6.1 is not self-contained. To understand it one needs to read citations given there. E.g. from the given explanation what is deep bootstrap phenomenon is not clear. The effective training time is not defined and etc.\n\nIn Section 6.2 it is claimed that the result generalizes  Bengio et al. (2006) to more general kernels. It would be interesting if authors discuss also, how different are required training set sizes according to Bengio et al. (2006) and in authors' analysis. How these two approaches are different.\n\nQuantum mechanical analogy is not convincing.", "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": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "7kVF0ieUBR", "reviewer": "Reviewer_zjAQ", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "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": "", "summary_of_the_paper": "This submission computes the generalization error of kernel ridge regression (KRR) which depends on the eigenspectrum of the kernel and the decomposition of the target function onto the kernel eigenbases. The derivation is based on a Gaussian equivalence assumption, and the authors presented various interpretation of the formulae via the notion of learnability, which is the inner product between the KRR estimator and some given test functions. The theoretical predictions are empirically validated on synthetic and real-world datasets. ", "summary_of_the_review": "In my opinion this submission is below the acceptance bar due to the incremental theoretical contribution. I will consider updating my evaluation if the authors can adequately discuss the prior results and clarify the novelty in their theoretical analysis. ", "strength_and_weaknesses": "## Strength\n\nThe derived generalization error formulae lead to a few interesting findings. \n\n- A heuristic explanation of the deep bootstrap framework using the approximate equivalence between early stopping in gradient descent and ridge regularization. \n- A learning lower bound for kernel methods on the parity problem. \n- An analytic expression of the expected gradient norm of the estimator, which can be seen as a measure of robustness. To my knowledge this computation has not appeared in prior works. \n\n## Weaknesses \n\nMy main concern is that the theoretical contribution in this submission is limited. \n\n1. The generalization error formulae is derived from assuming the kernel features are Gaussian. This reduces the problem to linear regression on Gaussian features, for which the same set of equations has been rigorously proved and extensively studied in many prior works using random matrix theory, see [Hastie et al. 2019] [Wu and Xu 2020] [Richards et al. 2020]. These existing results are not thoroughly discussed in this submission, and I do not see the value of rederiving the same result using a non-rigorous approach (in fact, one could argue that the Stieltjes transform-based derivation is cleaner). \n\n2. The \"no-free-lunch\" implied by the conservation of learnability is not surprising. Given a kernel with certain spectral bias, we should not expect it to perform well on all target functions. Moreover, analogues of \"the recent folklore intuition that, given n samples, KRR and wide NNs can reliably learn at most O(n) orthogonal functions\" have been rigorously shown in [Ghorbani et al. 2019] [Mei et al. 2021]. \n\n3. The applications of the error formulae in Section 6 are also not entirely new. \nThe explanation of \"deep bootstrap\" due to spectral filtering has already appeared in [Ghosh et al. 2021]. And the parity lower bound is a known result from various works such as [Daniely and Malach 2020] [Kamath et al. 2020]. \n\n4. The empirical validation of the generalization error formulae on neural network features has been done in [Loureiro et al. 2021]. Also, unlike the cross-validation estimators, the omniscient risk estimate studied in this submission requires access to \"population\" statistics, which can be computationally demanding in real-world applications. \n\nGhorbani et al. 2019.  Linearized two-layers neural networks in high dimension.  \nHastie et al. 2019. Surprises in high dimensional ridgeless least squares interpolation.  \nDaniely and Malach 2020. Learning parities with neural networks.  \nWu and Xu 2020. On the optimal weighted $\\ell_2$ regularization in overparameterized linear regression.  \nRichards et al. 2020. Asymptotics of ridge (less) regression under general source condition.  \nKamath et al. 2020. Approximate is good enough: probabilistic variants of dimensional and margin complexity.  \nMei et al. 2021. Generalization error of random feature and kernel methods: hypercontractivity and kernel matrix concentration.  \nLoureiro et al. 2021. Learning curves of generic features maps for realistic datasets with a teacher-student model.  \nGhosh et al. 2021. The three stages of learning dynamics in high-dimensional kernel methods. ", "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": "Not applicable"}, "extra_text": {}}]

Author rebuttal:

Decision: Reject