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: Accepted by TMLR ()

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 more readily interpreted. In particular, we show that KRR can be interpreted as an explicit competition among kernel eigenmodes for a fixed supply of a quantity we term "learnability.'' These improvements are enabled by 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 transparently 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) generalize a previous 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.

Published in Transactions on Machine Learning Research (06/2023)
The Eigenlearning Framework: A Conservation Law Perspective on Kernel Regression and Wide Neural Networks
James B. Simon
jumees.imonnBBrrreeey.... edu
University of California, Berkeley and Generally Intelligent
Madeline Dickens
dickens@berkeley.ccom edu
University of California, Berkeley
Dhruva Karkada
dkarkada@Berkeleyyccom edu
University of California, Berkeley
Michael R. DeWeese
dewrese@berkeleeycco edu
University of California, Berkeley
Reviewed on OpenReview: https: // openreview. net/ htl/fforur forum? id= FDbQCCAVE)
Abstract
We derive simple closed-form estimates for the risk and other generalization metrics of kernel ridge regression (KRR). Relative to prior work, 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 a quantity we term "Icarnability." These improvements are enabled by sharp consorvation law which limits the ability KRR. to learn any orthonormal basis functions. Test risk and other objects of interest are expressed transparently terms of our conserved quantity evaluated in the kernel eigenbasis. We use our improved framework to:
i) provide theoretical explanation for the "deep bootstrap" of Nakkiran et al. 2020 ii) generalize previous result regarding the hardness of the classic parity problem,
iii) fashion thcoretical tool for the study of adversarial robustnoss, and
iv) draw a tight analogy between KRR and a canonical model in statistical physics.
1 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 eigenframework is consistent with other recent works, such as those of Canatar et al. (2021) and Jacot al, (2020), but is simpler work with and easier to derive. Our eigenframework paints a new picture of KRR as an explieit competition between eigenmodes for fixed budget of quantity term "learnability," " and downstream generalization metrics can be expressed entirely in terms of the lcarnability reccived by each mode (Equations 14
This picture stems from a conseroation law latent. in KRR which limits any kernel's ability to learn any complete basis of target functions. The conserved quantity, learnability, the inner product the target and predicted functions and, as we show, can be interpretod measure of how well the target function can
Code reproduce results availahle

---

Published in Transactions on Machine Learning Research (06/2023)
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), is no greater than the number of training samples, with equality at zero ridge parameter. This formal conservation law makes concrete the recent folklore intuition that, given n samples, KRR and wide NNs can reliably learn at most n orthogonal functions (Mei Montanari 2019 Bordelon et al. 2020).
The conservation of this quantity suggests that it will prove useful for understanding the generalization of KRR. This intuition is borne out by our subsequent analysis: derive set of simple, closed-form estimates for test risk and other objects of interest and find that all of them can be transparently expressed in terms of eigenmode learnabilities. 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 obtain comparable results. By contrast, our approach requires only basic linear algebra, leveraging our conservation law at critical juncture to bypass the need for advanced techniques.
We use our uscr-friendly framework to shed light on several topics of interest:
i) We provide a 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 is simple and illustrates the power of our framework.
iii We craft an estimator for predicted function smoothness, a new tool for the theoretical study of adversarial robustness.
iv) We draw a tight analogy wetween 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 as 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 Scction 4 We check these results experimentally in Scction 5
Section consists of a scries of short vignottes
discussing lopics (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 process regression Opper 1997 Sollich. 1999), with Sollich (2001) deriving an estimator giving the expected test risk of KRR in terms of the eigenvalues of the kernel operator and the eigendecompositionn of the target function. We refer to this result as the "omniscient risk estimator m as it assumes full knowledge of the data distribution and target function. [Bordelon et al. (2020) and Canatar et al. (2021) brought these ideas into a modern context, deriving the omniscient risk estimator with a replica calculation and connocting
the "ncural tangent kernel" (NTK) theory of wide neural networks {Jacot et. al. 2018), with {Loureiro et al.] 2021] exlending the result to arbitrary convex losses. [Sollich & Halees (2002) Caponnetto & De Vito (0077;; Spigler et al. (2020): Cui et al. (2021); Mallinar et al. (2022) study the asymptotic consistency and convergence rates of
KRR in a similar vein. Jacot. et al.] (2020); Wei et al. (2022) used random matrix theory lo derive a risk
estimator requiring only training data. In parallel with work on KRR, Dobriban & Wager (2018): : Wu & Xu
y Richards et al. )021): Hastie et al. (022) and Bartlett et al. (2021) developed equivalent results in
the context of linear regression using tools from random matrix theory. In the present paper, we provide a
new interpretation for this rich body of work in terms of explicit competition between eigenmodes, provide
simplified derivations of the main results of this line of work, and break new ground with applications to
We borrow this terminology from Wei
2022
2

---

Published in Transactions on Machine Learning Research (06/2023)
A
B
71
72 =
6
10
D
E
DD
8
leamabilityy buriget
6
2m
NTK
NN
C
leamaailiity budget
(D, (D, (D))
ΦK
neural network
fK
NTK regression
(D) (Øk) (Øk, fkk)
THL.
4HI.
IHI.
4HL.
IHL.
4HI.
IHI.
4HL
ReLU
ReLU
tanh
tanh
ReLU
ReLU
tanh
tanh
Figure 1: Toy problem illustrating our conservation law. (A) The task domain: the unit cirele discretized into M = 10 points, n which comprise the dataset D (filled circles). (B) The 10 cigenfumctions of a rotation-invarianl kernel on this domain, grouped into degenerate pairs and shifted vertically for clarity. (C) We use each eigenfunction de in turn the target function. For each Φk, we compute training targets on (D), obtain a predicted function fa a standard supervised learning setup, and subsequently compute D- learnability. This comprises 10 orthogonal learning problems. (D,E) Stacked bar charts with 10 components showing D-learnability for each eigenfunction. The left bar in 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 exactly for kernel regression and approximately for wide networks.
problems of interest. We compare selected works with ours and provide dictionary between respective notations in Appendix
All prior works in this line and indeed most works in machine learning theory more broadly - rely on approximations, asymptotics, or bounds to make any claims about genoralization. The conservation law is unique that gives a sharp equality even at finite dataset size. This makes a 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 al. 2019 Xu et al.) 2019b Xu 2018 Cao et al.) 2019 Su & Yang,
2019) and the number of samples (Valle- Perex et al. 2018 Yang & Salman
2019 Arora et al. 2019b. Our
investigation into the deep bootstrap ties together these threads of work: we find that the interplay of these two sources of spectral bias responsible for the deep bootstrap phenomenology.
Conservation laws are common across all fields of physics. Such laws provide both meaningful quantities with which to reason and theoretical tools aid in caleulation. In classical mechanics in particular, the identification of conserved quantity, such energy momentum, often greatly simplifies subsequent caleulation of quantity of interest. Our conservation law serves precisely these purposes in our study, permitting a simplified derivation of the omniscient risk predictor and giving an intuitive variable with which we can characterize the generalization of KRR. Learnability, our conserved quantity, is precisely the "teacher-student overlap" order parameter common in statistical physics treatments of KRR (e.g. Loureiro et al. (2021)), though its conservation has our knowledge not been noted before. Kunin al. (2020) also study conservation laws obeyed by neural networks, but their conservation laws describe weights during training and not related to ours.
3

---

Published in Transactions on Machine Learning Research (06/2023)
2 Preliminaries and notation
We study standard supervised learning setting in which n training samples D = {z: are drawn i.idd from a distribution over R We wish to learn a (scalar) target function If given noisy evaluations y = (y:)
with = f(x,)= + Th, with 7/1 ~ =), As it simplifies later analysis, we assume this AO, <²) label noise is also applied to test targets !
Our results are casily gencralized to voctor-valued functions as in Canatar et al. 20211. For scalar functions g, h, we define (g, h) = (===p((())(())) and I = (g, g).
We shall study the KRR predicted function f given by
f(x) (KD + 01.)
(1)
where, for a positive-semidefnite kernel K, have constructed the vector [k.D): K(x, v4) and the empirical kernel matrix [KDD); = (z) (which we trust to be nonsingular), 8 is ridge parameter, and I, the identity matrix. We wish to minimize test mean squared error (MSE) (P) |s f13 + e and its expectation over training sets &(f) Ep { noise values). We emphasize that, here and in our discussion of learnability, f 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(J) -If- //---EEEll E=[fi + and variance V(J) = E() - B()).
(E(D) (f)] (where the expectation over D also averages over
We also define train MSE as Eer(f) = (f(x)) - f(x:))2
2.1 The kernel eigensystem
By Mercer's theorem Mercer 1909). the kernel admits the decomposition K( x') E, (z0) with eigenvalues X; 2 0 and basis of eigenfunctions di satisfying (b) = dej. We assumee eigenvalues are indexed in descending order.
As the cigenfunctions form a complete basis, we are free to decompose f and as
f(z) Ev and f(z) 100=Empp (vo((z))
(2)
where v (vi)s and v (V:), are vectors of eigencoefficients.
3 Learnability and its conservation law
Here we define learnability, our conserved quantity. Learnability is measure of f defined similarly to test MSE, but it is linear instead of quadratic. For any function f such that Ifl = 1, let
((P) = (J,)) and L() = ED =0) ((P)
(3)
where, as with MSE, f is given by Equation 1 We refer to ((P)()) the D-learnability of function f with respect to the kernel and n and refer to L(f) as the learnability. Up to normalization, this quantity is akin to the cosine similarity between ʃ and f. We shall show that, for KRR, learnability gives useful indication of how well a function (particularly a kernel eigenfunction) is learned. Results in this section are rigorous and exact; see Appendix H 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, (0t), and any f such that Ifll = hold:
(a) L():), c(P) [0, 1].
(b) When = 0, (() ((f)=0)
2To study noiseless targets instead, simply subtract x2 from expressions for MSF
4

---

Published in Transactions on Machine Learning Research (06/2023)
(c) Let D+ be D where X, x D is new data point. Then (())) 2 (o))
(d) a ox, (PP) (b.) 0, σx, (1)) S 00, and as (o)) so. O.
(e) 8(f) B(f) 2 (1 - (1-
Properties (a-c) logether give an intuitive picture of the learning process: the learnability of each eigen- function monotonically increases from zero as the training set grows, attaining its maximum of one in the ridgeless, maximal-data limit. Property (d) shows that the kernel eigenmodes are in competition increas- ing one cigenvalue 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 learn- ability. Property (c) gives a lower bound on MSE in terms of Icarnability and will be useful when we discuss the parily problem.
We now state the conservation law obeyed by learnability. This rule follows from the view of KRR as a projection of f onto the n-dimensional subspace of the RKHS defined by the n samples and is closcly related to the "dimension bound" for linear learning rules given by Hsu 2021
Theorem 3.2 (Conservation of learnability). For any complete basis of orthogonal functions F, when ridge parameler 5 = 0,
ΣC
C(f)= =n.
(4)
FEF
JE5
and when 5 > 0,
Σ (f) <n fEr
and
n.
(5)
FEF
This result states that, summed over any complete basis of target functions, total learnability is at most the number of training examples, with equality at zero ridge To understand its significance, consider that one might naively hope to design a (neural tangent) kernel that achieves generally high performance for all target functions f. Thcorem 3.2 states that this is impossible bocause, averaged over complete basis of functions, all kernels achieve the same leornability, and we have seen that learnability far from one implies high generalization error. Because there exist universally high-performing kernels, must instead aim to choose kernel that assigns high learnability to task-relevant functions.
This theorem is a stronger version of the classic "no-free-lunch theorem for learning algorithms, which states that, averaged over all target functions, all models perform at chance level (Wolpert) 1996). While deep and compelling, this classic result rarely informative in practice because the set of all possible target functions is prohibitively large to make nonvacuous statement. By contrast, Theorem 3.2 requires only an average over a basis of target functions and, as we shall see, it is directly informative in understanding the gencralization of KRR.
While Theorem 3.2 holds in any basis, we will choose this basis to be the kernel eigenbasis in subsequent
derivations.
4 Theory
Eigenmode learnabilities are interpretable quantities, obeying a conservation law and several intuitive prop- erties. These features suggest they may prove wise choice of variables in theory of KRR generalization. Here show that this is indced the case: we derive suite of estimators for various metrics of KRR gen- eralization, all of which be ezpressed 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.
We call Theorem 3.2 conservation law because zero ridge, as either the data distribution the kernel changes, total learnability remains constant. This analogous to, for example, physical conservation charge.
5

---

Published in Transactions on Machine Learning Research (06/2023)
We sketch our method here and relegate the derivation to Appendix Our derivation leverages conser- vation law to avoid the need for either replica calculation or random matrix theoretic tools, laying bare in some sense the minimal operations needed to obtain these results. Results in this section are nonrigorous. "universality" assumption that the
Like comparable works, our derivations use an experimentally--aaiiaee kernel features may be replaced by independent Gaussian ueal with the same statistics without changing downstream generalization metrics. We discuss this assumption in Appendix T.4
Sketch of derivation. We begin by observing that V depends linearly on v, and can thus construct "learning transfer matrix" (P)) such that v (P)y, T(P) is equivalent to the "KRR reconstruction operator" of Jacot et al.] (2020) and, viewing KRR as linear regression in cigenfeature space, is essentially the "hat" matrix of linear regression. We then study E [T((P), leveraging our universality assumption to show that it is diagonal with diagonal elements the form >//(A; + k); where x is a mode-independeni constant. We show the mode-independence of и with an eigenmode-remova. argument reminiscent of the cavity method of statistical physics (Del Ferraro et al. 2014). We use Theorem 3.2 determine к. Difforentiating this result with respect to kernel eigenvalues, obtain the covariance of T(P) and thus of 9, which permits evaluation of various test metrics
4.1 The eigenlearning equations
Let the effective regularization k be the unique positive solution to
A
6
(6)
A
K
K
We calculate various test and train metrics to be
X C,
(eigenmode learnability)
((6,)
(7)
A; +
Ōk
n1
(overfitting coefficient.)
Eo 26
(8)
n - Σ, F2
(test MSE)
8(f) = & Σ (1 -2,) ?
+2)
(9)
B(f) = Σ (1 - 2, + E(f)
(bias of test MSE)
(10)
Eo
V(f) E(f) B(f) E -1
(variance of test MSE)
E E(f),
(11)
(f) 8²
(train MSE)
nºR² E(f),
(12)
(mean predictor)
B LiVi,
(13)
Covlt,, Vy] = E(f)L?
(covariance of predictor)
8.4
(14)
n
The learnability of arbitrary normalized function can be computed as L() E, Lvv.. The mean of the target function evaluated at input æ can be obtained B[f(x)) = E, Blv.] (x)x, with the covariance obtained similarly.
4.2 Interpretation of the eigenlearning equations
Remarkably, all test metrics, and indeed all sccond-ordor statistics of f, can be expressed solely in terms of modewise learnabilities, with no additional reference to eigenvalues required. This strongly suggests that we
4or train risk, we simply quote the result. of Canatar et 2021

---

Published in Transactions on Machine Learning Research (06/2023)
have identified the "correct" choice of variables for the problem. We now interpret these equations through
the lens of learnability.
Equation G gives a constant K which decreases monotonically as n increases. Equation 7 states that the learnability of eigenmode i is 0 when x > X and approaches 1 when & < X, in line with the observation of Jacot et al. (2020) that mode is well-learned when x & )1 Inserting Equation into 6 and setting 0, we recover our conservation law.
Equation g is the omniscient risk estimator for test MSE. Modes with learnability equal to are fully learned and do not contribute: to the risk. Noise acts the same as target weight placed in modes with learnability zero. Equation g defines Eo, the MSE when trained on pure-noise targets (v, = 0 and =)=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 n units of learnability are fully allocated to the first n modes, not distributed among a greater number (Lign = 1, Lisn = 0). In this sense, overfitting of noise "overconfidenes" 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 portion of the learnability budget to the ridge parameter) lowers Eg and fixes this problem. Thiss overconfidence occurs when the kernel eigenvalues drop sharply around index n and is the cause of double-descent peaks (Belkin et 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 I1 show that, remarkably, the bias and variance can be expressed solely in terms of E(f) 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. (202T)- Equation 12 states that train error is related to test error by the target-independent proportionality constant 0²/k². Finally, Equations 13 and 14 give the mean and covariance of the predicted eigencoefficients. Different eigencoelfiiients are uncorrelated, and the variance of v; is proportional to 23 but surprisingly independent v, v,
Each new unit of Icarnability (from cach new training example) is distributed among the set of cigenmodes as
dh. dn = n -n-r = Err,+5/K*
(15)
where r; L1 - L.) a quantity which represents the rafe at which mode i is being learned. As examples are added, each eigenmode's learnability grows in proportion to ri, with a fraction of the learnability budget proportional to 8/K sacrificed to the ridge parameter a hedge against overfitting. This learning rate is highest when L, R 1, and thus it is the partially-learned eigenmodes which most benefit from the addition of new training examples.
4.3
MSE at low 7
A priori, one might expect a learning rule to obey the lenet that "more data never hurts". However, via the study of double-descent, it has recently become well-understood that this is not true: while risk typically initially decreases w.r.t. n, it can later increase (at least at fixed regularization strength) as n approaches the model's (effective) number of parameters. Defying even the double-descent picture, however, an additional tangle is presented by various experimental plots reported by Bordelon et al. (2020) and Misiakiewicx & Mei (202T) (Figures 3 and 1, respectively), which show the test MSE of KRR. increasing w.r.t. immediately (i.c. with no initial drop) without a subsequent peak. In these sconarios, having fow samples is worse than having none. What causes this counterintuitive behavior?
Here we explain this phenomenon, identifying a spectral condition under which an eigenmode's learning curve is nonmonotonic, and conclude that this is in fact a different class of nonmonotonic curve than one gets from double descent. Expanding Equation
9 about n 0, we find that E(o)))== and
dε (0))) dn
1
Σラ
211
(16)
E
Σ,
n==
S8e Mallinar al. 2022) for a discussion this interpretation.
7

---

Published in Transactions on Machine Learning Research (06/2023)
Unit Circle
B 8d Hypereube
C
7-sphere
Image Datasets
1.0
CIFARI desits
2
NOIST
MNSTTA
0.5
0.0
E
2-0 4 F-l
2--1 A-8
G
1m0
2-2
Am
ONEST
CIRARIO festouk
2
km2
km
2m
km6
MNNST S3
CIARRO dbaibnn
K-5
k-10
21
20
2
2
2'
2
2
21
25
71
T1
71
Figure 2: Predicted learnabilities and MSEs closely match experiment. (A-D) Learnability of var- jous eigenfunctions 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 (Iriangles) with varying dataset size n. Error bars show one standard deviation of variation. (E-H) Same (A-D) for test MSE, with theoretical predictions from Equation
This implies that, at small n, MSE increases samples are added for all modes such that
Σ 2 ,
A
A
(17)
This worsening MSE is due to overfitting: confidently mistaking o; for more learnable modes.
This phenomenon is distinct from double descent. Double descent requires a finite number of nonzero eigenvalues (or a spectrum with sharp cutoff (Canatar al. 2021)). By contrast, the phenomenon we have identified occurs with any spectrum when attempting to learn mode with sufficiently small eigenvalue. We verify Equation 16 experimentally in Appendix E
5 Experiments
Here we describe experiments confirming our main results. The targets are cigenfunctions 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 use fully- connected four-nidden-layer ReLU architecture, and finite networks have width 500. The kernel eigenvalues each synthetic domain group into degenerate sets which we index by k E Z+. Eigenvalues and cigen- coefficients for image datasets are approxinated numerically from large sample of training data. Full experimental details can be found in Appendix B
Figure I illustrates 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 agrcement in all cases. Appendix C repcats one of these experiments with network widths varying from to 20, finding good agreement with theory even narrow width.
An important question is whether our KRR eigenframework remains predictive even in more realistic regimes with c.g. bigger datascts with structured kernels. We choose not to include in the present work battery of experiments exlending Figures 2 D and H which would establish this. The main reason is that it there is already appreciable evidence that this is true: for example, Wei et al. (2022) demonstrate that similar eigenequations (which one would expect to succced or fail precisely when our approach succcods or fails) find excellent agreement with KRR using empirical ResNet NTKs on CIFAR-100 A secondary reason is computational cost: computing convolutional NTKs, diagonalizing kernel matrices much bigger than those
8

---

Published in Transactions on Machine Learning Research (06/2023)
used in our experiment, is rather expensive. Nonetheless, we do think that testing the KRR cigenframework at scale would be a worthwhile inclusion in experimental followup work.
6
Vignettes
6.1
Explaining the deep bootstrap
The deep bootstrap (DB) is a phenomenon observed by Nakkiran et al. (2020) in which the performance of a neural network stopped after a given number of training steps is relatively insensitive to the size of the training set, unless the training set is so small that it 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 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. (0019) proved that KRR with finite ridge generalizes remarkably similarly to KGF with finite stopping lime (a theoretical result confirmed empirically by Lee el al. (2020) for NTKs on image datasets). When considering standard supervised learning setting, the effective training time corresponding to ridge 8 is Teff = 8 (scc Appendix D for discussion of this scaling). As a proxy for KGF, shall study KRR Toff increases from 0 to xc.
In Equation 9 the ridge parameter affects MSE solely through the value of k. Define Ko = k|á=0, the minimum effective rogularization at a given dataset size. In Appendix D] we show that, for powerlaw eigenspectra (as are commonly found practice), there are two regimes of fitting:
1. Rogularization-llmite regime: Tet < Ki and T The generalization gap is small: ((f)/Ex(f) x 1. Regularization dominates generalization, and adding training samples does not affect generalization
2. Data-limited regime: Teff >> Ki and s Ko. The generalization gap is large: (())&tr) > 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 n at early times because, at these times, the model is in the regularization-lliited regime.
We now present an experiment confirming our interpretation. In Figure 3 we reproduce an experiment of Nakkiran et al. (2020) illustrating the DB using ResNets trained on CIFAR-10, juxtaposing it with our proposed model for this phenomenon KRR with varying Teff trained on binarized MNIST. The match is excellent: in particular, both plots share the DB phenomenon that error curves for all n overlap at carly times, with lest and Irain error peeling off the master curve al roughly the same time. We find that Teh Ko 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-liiiee limited and data-limited regimes. See Appendix D for experimental details.
6.2
The hardness of the parity problem for rotation-invariant kernels
The parity problem stands as classic example of function which is casy to write down but hard for common algorithms to learn. The parity problem was shown to be exponentially hard for Gaussian kernel methods by Bengio et al. (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 in terms of learnabilities.
The problem domain the hypercube X == = (-1,+1 over which we define the subsct-parity functions (s(x) (-1) Eics [|==1] where S _ (l,.... d) [d]. The objective learn 014--
We mean here that adding training samples while holding F. constant does not affect generalization.

---

Published in Transactions on Machine Learning Research (06/2023)
10
109
B
8 16
Classification Liror
7 500
n= 125
10 2000
1000
12 8000
KRR train
NN train
12 = 32000
KRR test
8000
10a
NN test
theory
10
10
10a
10
10
10
100
10a
10
10
Train steps
Figure 3: We reproduce and explain the deep bootstrap phenomenon in KRR. (A) An experiment illustrating the deep bootstrap effect using a ResNet-18 on CIFAR-10. (B) An analogous experiment using KRR on binarized MNIST. Figenlearning predictions closely match experimental curves, and Teff = ngg (vertical dashed lines) faithfully predicts the transition from regularizatioon-liiies to data-limited fitting for each n.
For any rotation-invarian kernel (such as the NTK of a fully-connected neural network), {osts are the eigenfunctions over this domain, with degenerate eigenvalues {Ae depending only on k = 1S). Yang & Salman (2019) proved that, for any fully-connected kernel, the even and odd eigenvalues each obey a particular ordering in k. Letting d be odd for simplicity, this result and Equation 7 imply that L1 2 L3 2 ... 2 La- Counting level degeneracies, this is a hierarchy of 2d-1 learnabilities of which La is the smallest. The conservation law 3.2 then implics that La S 20-1; which, using Proposition 3. implics that
E(014) 2 (1 2d-1
n
(18)
Obtaining MSE below desired threshold thus requires at least Timin = -1- samples, sample complexity exponential in d. The parity problem is thus hard for all rotation-invarian kernel
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 a first use for these covariances: studying the smoothness of 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 f defined by g(f) = E. [[=](>)]] = /V This quantity is a measure of function smoothness Figendecomposition yields that
V (<) ||]
E
Σ E with 9o = L (z)))))()))))) (z)]
(19)
The expectation [00,0, = E [o.] [ Covio, 9,] is given by the eigenlearning equations, and the structure constants gig, which encode information about the domain, can be computed analytically for simple domains. On the d-sphere, for which the o; du are spherical harmonics, these ((k)))((e)))) = k(k + d 2)
Figure 4 shows the MSG of the function learned by KRR with a polynomial kernel trained on k = modes on spheres of increasing dimension d, normalized by the MSG of the ground-truth target function. See Appendix
FF for experimental details and additional experiments in this vein. True MSG matches predicted MSG well in all settings, particularly at large n and d.
Kamath ct al. 2020 Hsu 2021 which give complexity lower bounds for learning parities using simple degeneracy argument. However, these approaches do not leverage the spectral blas of the kernel and become vacuous when == d. SSee for further discussion of MSG as proxy for robustness.
We note number of recent approaches (Daiclyy Malach 2020
10

---

Published in Transactions on Machine Learning Research (06/2023)
The study of adversarial robustness currently suffers from 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 Vulnerability to gradient-based adversarial attacks can viewed essentially as a phenomenon of surprisingly large gradients with respect to the input. If such vulnerability is an inevitable consequence of high dimension, common heuristic belief (e.g. Gilmer et al. (2018)), )) one might expect that G(f) is generally much larger than G(f) at high dimen- sion. Surprisingly, we no such effect, discrepancy which can be investigated further using our framework.
1.00
d
d 16
0.75
d=
d 256
f
0.50
d 1004
0.25
2
22
210
2
Figure 4: Predicted function smoothness matches experiment. Predicted MSG of f (curves) and empirical MSG for kernel regres- sion (triangles) for spheres with varying dimension.
6.4 A quantum
1 modes hyper-
mechanical analogy and universal learnability curves
Here we describe remarkably tight analogy between our picture of KRR generalization and the statistics of the free Fermi gas, canonical model in statistical physics. This allows certain insights into the free Fermi gas to be ported over to KRR. This correspondence is also of fundamental interest: KRR and the free Fermi gas are both paradigmatic systems in their respective fields, and it is remarkable that their statistics are in fact the same.
We defer the details of this correspondence to Appendix G and focus here on the takcaways. The free Fermi gas is defined by scalar f and a set of states with energies {EiJi, each of which may be occupied or not. We find that II k is analogous to μt, the state energies are analogous to kernel eigenvalues, and the states' occupation probabilities are precisely analogous to the eigenmodes learnabilities.
In all prior work and in our work thus far, the constant к has thus far been defined only as the solution an implicit equation. Having an explicit equation would be advantagcous. Leveraging methods for the study of the free Fermi gas, we find the following emplicit formula for k in terms of the elementary symmetric polymomials m, when 8 == 0:
R mp((1 )2,..)) mn-1 101, (21,)....)
where
Σ
(20)
1S <i
The elementary symmetric polynomials obey the recurrence relation (amn-1(A1 )2,... + (m,,A,A2.... m,, (Ai, \1, x2,-.., where on the right hand side we have appended an additional X; to the arguments of m,- Using this and the fact that is typically changed only negligibly by the removal of single eigenvalue, we may observe that
C. Amn1-1(d1.N d2...) x AM1 .., Ar- Ast1......
(21)
(Nis A2,))...)
Mn (d1, d2....
where the numerator the right hand side we skip over X; the arguments of mn-1- Writing C, this form reveals that. the learnability of mode equals the "weighted fraction" of terms in my A2...) in which X, is selected.
The second takeaway is the identification of a universal behavior in the learning dynamics of KRR. In systems obeying Permi-Dirac statisties, a plot of p; vs. é lakes a characteristic sigmoidal shape. As shown in Figure we robustly see this sigmoidal shape in plots of L, vs. In A4. As the number of samples and even the task are variod, this sigmoidal shape remains universal, merely translating horizontally (in particular, moving left as samples are added). This sigmoidal shape is thus signature of KRR and could in principle be used to, for example, determine if an unknown kernel method resembles KRR.
11

---

Published in Transactions on Machine Learning Research (06/2023)
Unit Circle
8d Hypercube
7-sphere
1.0
B
((d))
All
0.5
NN
G
0.0
1.0
D
E
F
((())
(n -69
Az/K
0.5
Ne/K +1
10at
10º
10a
0.0
10
10
10a
10
10a
10a
XE/
X
X
Figure 5: Modewise learnabilities fall on universal sigmoidal curves. (A-F) Predicted learnability curve (sigmoidal curves) and empirical learnabilities for trained networks (circles) and NTK regression (tri- angles) for eigenmodes & E (0,....]] 7} on three domains for = 8, 64. Vertical dashed lines indicate K. (G) All data from (A-F) with cigenvalues rescaled by K.
7 Conclusions
We have developed an interpretable unified framework for understanding the generalization of KRR centered on a previotsly-mmexplottedd conserved quantity. We then used this improved framework to break new theoretical ground in a variety of 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.
An important line of ongoing work is to extend this cigenanalysis to more rcalistic domains and architectures. The eigenstructure of convolutional NTKs and kernels on structured domains are subjects of ongoing research
Xiao 2021
Misiakiewicz & Mei 2021 Cagnetta et al. 2022 Ghorbani et al., 2020 Tomasini et al. 2022
This flavor of neural network theory is potentially relevant for the study of AI reliability and safety (Amodei et al. 2016 Hendrycks et al.] 2021). In general, it desirable to have theory that predicts which patterns networks will preferentially identify and learn. With the tools here presented, one could conceivably construct problem in which one asks whether a kernel machine learns desired function or undesirable but "simpler" alternative, taking a step towards addressing the lack of tractable safety-relevant toy problems.
Acknowledgments
JS dedicates this work the memory of Madeline Dickens, friend and bright light. gone too soon. Maddie, owe you much, and I can only imagine the things you would have taught
The authors thank Berfin Şimşek, Blake Bordelon, and Zack Weinstein for useful discussions and Kamesh Krishnamurthy, Alex Wei, Chandan Singh, Sajant Anand, Jesse Livezey, Roy Rinberg, Jascha Sohl-Dickstein, and various reviewers for helpful comments on the manuscript. Particular thanks are owed Bruno Lourciro for valuable help in navigating the surrounding literature. This research was supported in part by the U.S. Army Research Laboratory and the U.S. Army Research Office under contract W911NF-20-1-011 gratefully acknowledges support from the National Science Foundation Graduate Fellow Research Program (NSF-GRFP) under grant DGE 1752814.
JS
References
Alnur Ali, J Zico Kolter, and Ryan J Tibshirani. continuous-time view of carly stopping for least squares regression. In The 22nd international conference on artificial intelligence and statistics, pp. 1370-1378. PMIRR 2019.
12

---

Published in Transactions on Machine Learning Research (06/2023)
Dario Amodei, Chris Olah, Jacob Steinhardt, Paul Christiano, John Schulman, and Dan Mané. Concrete problems in ai safety. Xiv preprint urXin:1606 166:066666666, 2016.
Sanjeey Arora, Simon Du, Wei Hu, Zhiyuan Li, and Ruosong Wang. Fine-grained analysis optimization and generalization for overparameterized two-layer neural networks. In International Conference on Machine Learning, pp. 322-332. PMLR, 2019.
Yasaman Bahri, Ethan Dyer, Jared Kaplan, Jaehoon Lee, and Utkarsh Sharma. Explaining neural scaling laws. arXie preprint arXiv:2102.0677 2021.
Peter Bartlett, Andrea Montanari, and Alexander Rakhlin. Deep learning: a statistical viewpoint. Acta numerica, 30:87-201, 2021.
Mikhail Belkin, Daniel Hsu, Siyuan Ma, and Soumik Mandal. Reconciling modern machine-learning practice and the classical birs-variance trade-off. Proceedings of the National Academy of Sciences, 116(32):15849- 15854, 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. ar preprint arXiv:2106.0277 02713, 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-Milne, and Qiao Zhang. JAX: compos- able transformations of Python+NumPP programs, 2018. URL http: http://ttttubcccoo com wowm/oooge/eaa
Francesco Cagnetta, Alessandro Favero, and Matthicu Wyart. How wide convolutional neural networks learn hierarchical tasks. arXiu preprinl arXiv:2208.0100 2022.
Abdulkadir Canatar, Blake Bordelon, and Cengiz Pehlevan. Spectral bias and task-model aligmment explain generalization in kernel regression and infinitely wide neural networks. Nature communications, 12(1): 1-12, 2021.
Yuan Cao, Zhiying Fang, Yue Wu, Ding- Xuan Zhou, and Quanquan Gu. Towards understanding the spectral bias of deep learning. arXi preprint arXiv:1912. 11111191..0 01198, 2019.
Andrea Caponnetto and Ernesto De Vito. Optimal rates for the regularized least-squares algorithm. Foun- dations of Computational Mathematics, 7(3):331-388 -368, 2007.
Xiuyuan Cheng and Amit Singer. The spectrum of random inner- inner-product kernel matrices. Random Matrices: Theory and Applications, 2(04):1350010, 2013.
Omry Cohen, Or Malka, and Zohar Ringel. Learning curves for overparametrized deep neural networks: A 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 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 Information Processing Systems, 14:23366-00363 2020.
Gino Del Ferraro, Chuang Wang, Dani Martí, and Marc Mézard. Cavity method: Message passing from a physics perspective. Xiu preprint arXio:1409.3046 2014.
13

---

Published in Transactions on Machine Learning Research (06/2023)
Edgar Dobriban and Stefan Wager. High-dimensional asymptotics of predictions: Ridge regression and classification. The Annals of Stalistics, 46(1):247-227 279, 2018.
Noureddine El Karoui. The spectrum of kernel random matrices. The Annols of Statistics, 38(1):1-50, 2010.
Zhou Fan and Andrea Montanari. The spectral norm of random inner-product kernel matrices, Probabiliyy Theory and Related Fields, 173(1):27-85, 2019.
Christopher Frye and Costas Efthimiou. Spherical harmonics in p dimensions. ar preprint
arXiv:1205.3548, 2012.
Behrooz Ghorbani, Song Mei, Theodor Misiakiewicz, and Andrea Montanari. When do neural networks outperform kernel methods? Advances in Neural Information Processing Systems, 33:14820 14830, 2020.
Nikhil Ghosh, Song Mei, and Bin Yu. The three stages of learning dynamics in high-dimensional kernel methods. In International Conference Learning Representations, ICLR, 2022.
Justin Gilmer, Luke Metz, Fartash Faghri, Samuel S Schoenholz, Maithra Raghu, Martin Wattenberg, and Ian Goodfellow. Adversarial spheres. arXiv preprint 1rXii:1801.022 2018.
Nigel Goldenfeld. Roughness-induced critical phenomena in turbulent flow. Physical review letters, 96(4): 044503, 2006.
Trevor Hastie, Andrea Montanari, Saharon Rosset, and Ryan J Tibshirani. Surprises high-dimensional ridgeless least squares interpolation. The Annals of Statistics, 50(2):949 986, 2022.
Dan Hendrycks, Nicholas Carlini, John Schulman, and Jacob Steinhardt. Unsolved problems in ml safety. arXiv preprint arXi::2109.1100 18916, 2021.
Daniel Hsu. Dimension lower bounds for linear approaches function approximation. Daniel Hsu's home- page, 2021.
Arthur Jacot, Clément Hongler, and Franck Gabriel. Neural tangent kernel: Convergence and generalization in neural nelworks. In Advances in Newral Informalion Processing Systems (NeurIPS). 2018.
Arthur Jacot, Berfin Simşek, Francesco Spadaro, Clément Hongler, and Franck Gabriel. Kernel alignment risk estimator: risk prediction from training data. arXiv preprint arXic:2006.0977 2020.
Pritish Kamath, Omar Montasser, and Nathan Srebro. Approximate is good enough: Probabilistic variants dimensional and margin complexity. In Conference on Learning Theory, pp. 2236-2262. PMLR, 2020.
Jared Kaplan, Sam McCandlish, Tom Henighan, Tom Brown, Benjamin Chess, Rewon Child, Scott Gray, Alec Radford, Jeffrey Wu, and Dario Amodei. Scaling laws for neural language models. arXiv preprint arXiv:2001.08.00 2020.
Mchran Kardar. Statistical physics of fields. Cambridge University Press, 2007.
Daniel Kunin, Javier Sagastuy-Brens Surya Ganguli, Daniel LK Yamins, and Hidenori Tanaka. Neu- ral mechanics: Symmetry and broken conservation laws in deep learning dynamics. ar preprint arXiv:2012.04 2020.
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 Repre- sentations (ICLR), 2018
Jachoon Lee, Lochao Xiao, Samuel Schocnholz, Yasaman Bahri, Roman Novak, Jascha Sohl-Dickstein, and Jeffrey Pennington. Wide neural networks of any depth evolve as linear models under gradient descent. In Advances in Neural Information Processing Systems (NeurIPS), 2019.
14

---

Published in Transactions on Machine Learning Research (06/2023)
Jachoon Lee, Samuel S. Schoenholz, Jeffrey Pennington, Ben Adlam, Lechao Xiao, Roman Novak, and Jascha Sohl-Diccstein. Finite versus infinite neural networks: an empirical study. In Advances in Neural Information Processing Systems (NewrIPS), 2020.
Aitor Lewkowycz, Yasaman Bahri, Ethan Dyer, Jascha Sohl- Sohk-Dickstein, and Guy Gur-Ari. The large learning rale phase deep learning: the catapult mechanism. CoRR, abs/ alss2200.022188, 2020. URL ptopps://aran /arxiv.
org/abs/2003. 02218
Fanghui Liu, Zhenyu Liao, and Johan Suykens. Kernel regression in high dimensions: Refined analysis beyond double descent. In International Conference on Artificial Intelligence and Statistics, pp. 649-657. PMLR, 2021.
Bruno Loureiro, Cedric Gerbelot, Hugo Cui, Sebastian Goldt, Florent Krzakala, Marc Mezard, and Lenka Zdeborová. Tearning curves of generic features maps for realistic datasets with a teacher-student model. Advances in Neural Information Processing Systems, 34:18137 18151, 2021.
Yue M Lu and Horng- Tzer Yau. An equivalence principle for the spectrum of random inner-produt kernel matrices. Xiv preprial or Xiv:2205506308, 2022.
Neil Mallinar, James B Simon, Amirhesam Abedsoltan, Parthe Pandit, Mikhail Belkin, and Preetum Nakki- ran. Benign, tempered, or catastrophic: A taxonomy of overfitting. arXiv preprint arXi::2207.06500 2022.
Song Mei and Andrea Montanari. The generalization error of random features regression: Precise asymptotics and the double descent curve. Communications on Pure and Applied Mathematics, 2019.
J Mercer. Functions of positive and negative type and their connection with the theory of integral equations. Philosophical Transactions of the Royal Society of London, 415, 1909.
Theodor Misiakiewicz and Song Mei. Learning with convolution and pooling operations in kernel methods. arXiv preprint xxX:::211..08388, 2021.
Preetum Nakkiran, Behnam Neyshabur, and Hanie Sedghi. The deep bootstrap framework: Good online learners are good offline generalizers. arXiv preprint orxiv:2010. 081227, 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, Jaehoon Lee, Alexander A. Alemi, Jascha Sohl-Dickstein, and Samuel S. Schoenholz. Neural tangents: Fast and casy infinite neural networks in python. CoRR, abs/1912.028833, 2019. URL http::///aaiii.oor/aa///////////
Manfred Opper. Regression with gaussian processes: Average case performance. Theoretical aspects 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 DeVito, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala. Pytorch: An imperative style, perforrrroeeeeee deep learning library. In Advonces in Newral 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 Conference on Machine Learning, pp. 5301-5310. PMLR, 2019.
Dominic Richards, Jaouad Mourtada, and Lorenzo Rosasco. Asymptotics of ridge (less) regression under general source condition. In International Conference on Artificial Intelligence and Statistics, pp. 3889- 3897. PMLR, 2021.
15

---

Published in Transactions on Machine Learning Research (06/2023)
Jascha Sohl-Dickstein, Roman Novak, Samuel S Schoenholz, and Jachoon Lee. On the infinite width limit of neural networks with a standard parameterization. arXiv preprint arXiv:2001.0783 2020.
Peter Sollich. Learning curves for gaussian processes. Advonces in Neural Information Processing Systems, pp. 344-350, 1999.
Peter Sollich. Gaussian process regression with mismatched models. In Advances in Newral Information Processing Systems, pp. 519 526. MIT Press, 2001.
Peter Sollich and Anason Halees. Learning curves for gaussian process regression: Approxinations and bounds. Neural computation, 14(6):1393 1428, 2002.
Stefano Spigler, Mario Geiger, and Matthieu Wyart. Asymptotic learning curves of kernel methods: empirical data versus teacher-studers paradigm. Journal of Statisticol Mechanics: Theory and Eaperiment, 2020 (12):124001, 2020.
Lili Su and Pengkun Yang. On learning over-parameterried neural networks: A functional approximation perspective. arXiv preprint orXi::1905.1082 10826, 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 International Conference on Machine Learning, pp. 21548 21383. PMLR, 2022.
Guillermo Valle-Perez, Chico Q Camargo, and Ard A Louis. Deep learning generalizes because the parameter- function map is biased lowards simple functions. arXiv preprinl Xrxi 08522,, 2018.
Alexander Wei, Wei Hu, and Jacob Stcinhardt. More than toy: Random matrix models predict how real- world neural representations generalize. In International Conference Machine Learning, Proceedings of Machine Learning Research, 2022.
David Wolpert. The lack of priori distinctions between learning algorithms. Neural computation, 8(7): 1341-1390, 1996.
Denny Wu and Ji Xu. On the optimal weighted & regularization in overparameterized linear regression. Advances in Newral Information Processing Systems, 33:10112 10123, 2020.
Lechao Xiao. Eigenspace restructuring: principle of space and frequency in neural networks. arXiv preprint arXiv:21122 12.1112.000 0eti:22112.511111 05611, 2021.
Zhi-Qin John Xu, Yaoyu Zhang, Tao Luo, Yanyang Xiao, and Zheng Ma. Frequency principle: Fourier analysis sheds light deep neural networks. arXiv preprint 1rXfc:1901.06523, 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. (64-274. Springer, 2019b.
Zhiqin John Xu. Understanding training and generalization in deep learning by fourier analysis. arXiv preprint xrx:::1805, 03..042200 04295, 2018.
Greg Yang and Hadi Salman. A fine-grained spectral perspective neural networks. XrXiv preprint arXiv:1907.10599 2019.
16

---

Published in Transactions on Machine Learning Research (06/2023)
A Notation dictionary and comparison with related works
Tables and - provide a dictionary between the notations of our paper and the nearest related works. Rows should be read comparison with the top row and interpreted as "when the present paper writes X, the other paper would write Y for the same quantity." Comparing expressions for test MSE in Table g and predicted function covariance in Table 3
very clear that our learnability framework permits simpler and much more interpretable expression of these results than previously given.
makes makes
Table 1: Notation dictionary between the present paper and related works (part 1).
Paper
# samples
ridge
noise
cigenvalues
eigenfns
eigencoeffs
(ours)
72
A
Ø
Vi
Bordelon et al.
(2020)
P
A
NA
Ap
Ap
1/2
Ap 1/2
wp
Canatar ct al.
2021
P
A
o²
Up
1/2
upp
Ap
1/ W
Jacot et al.
2020))
N
NA
c²
dg
f(())
(f(k), f()
Cui et al.
2021
a²
TJs
(x
11k
1/2
Table 2: Notation dictionary between the present paper and related works (part 2).
Paper
eff. reg.
overfitting coeff.
test MSE
(ours)
Eg
E(f) Eo (E, (1 C2 +
Bordelon et al.
(2020)
++>
py [(+A)²
22a F.g Ep
-2
(1
Ap
Ap
X+t
(X+1)=
Canatar et al.
2021
Eg 1-
1 Ep
Tp
(k² (k2,0 o² PMp))
1-7
Pmpp)
Jacot al.
(020
020 1
Re = 2x (I(Ie- - !|?
o 2 9p Tz/m up
+0
Cui et al. (2021 10
69
(s/n+my))
(z/n+t)))
Am1
Am1
CCui et al. 2021 simplifications of the expressions of Lourciro al. 2021 whose notation does map cleanly onto tables.
10 overfitting coefficient and test MSE estimator Cul al. 2021 appear more complex than the alternatives in part. because other works define intermediate quantities like Eo, 73 elc., which include sums over rigenmodes.
17

---

Published in Transactions on Machine Learning Research (06/2023)
Table 3: Notation dictionary between the present paper and related works (part 3).
Paper
predicted fn covariance
(ours)
CovlV; 8y CLE(1) dez
Bordelon al. (2020)
NA
Canatar et al.
(2021
MT W w3}
1 1-n
(02 + 122 Ep (Pr
(Pro (Pno dag
Pri
Jacot al.
2020
Vel N. SAgeN (1((c-
+e= (ere2+(((t)) (p00)) 1133 (OCA)tON) (o(A)+1A))
Cui et al.
2021
NA
Sollich 2201]] y 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 (202)), Richards et al. (2021), Hastic et al. (2022) (see Definition 1) and Bartlett et al.) (2021) (see Theorem 4.13), which derive comparable equations for the test. MSF of linear ridge regression (LRR),, which, taking the dual view of KRR LRR in the kernel embedding space, is esscntially the same problem. All comparable works involve solving self-consistent equation for an elfective regularization parameter, which we call in our work.
It is worth pointing out that this literature is largely divided into two parallel camps: the works in the tables above, together with Loureiro et al.
2021) and Cohen et al. 2021 (who study GP regression using field theoretic tools), study the generalization of KRR, largely using approaches from statistical physics, while Dobriban & Wager (2018): ; Wu & Xu (2020) Richards et al. (2021): Hastie et al. 2002) 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 "universality" approximation that the eigenfunctions are random and structureless and the design matrix can thus be replaced by a random Gaussian matrix. The works of Bordclon et al.] (2020): Canatar et al.] (2021), as well as ours, make additional approximations valid for reasonable eigenspectra and large n, while Jacot 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 unversality approximation, but instead assume in their setting that the feature vectors moments (or some similar condition), which ultimately amounts to the same condition, now enforced in the setting instead of assumed as an approximation. These works are typically mathematically rigorous. Relative to the LRR works, one contribution of the KRR works is the empirical observation that this universality approximation is generally accurate in practice and empirical evidence supports its validity for NTKs after training (Wei et al. 2022).
high-dimensional and have Gaussann
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 I4 agrees with that of Canatar et al. (2021 13 However, the expression of Jacot et al. (2020), given in Theorem 2, contains an extra O(n term (blue in Table 3 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. Tt contributes negligibly when summing over all eigenmodes to compute e.g. test error or mean squared gradient, but contributes to leading order when interrogating the variance of a particular mode. A sanity-check calculation that the sum
This is a nontrivial observation, as is not hard to construct contrived cases in which this approximation does not hold, as discussed by (Sollich& & Halees (2002). The conditions under which this universality assumption holds are active area of research. A variety of rigorous works ks have proven this spectral universality assumption in specific higl-dinensional settings
El Karoui 2010 Cheng & Singer 2013 Fan & Montanari 2019 Liu ct al. 2021 Lu & Yau 2022 and Tomasini al. 2022
has shown it docs not quite hold in certain noisy low-dimensional scttings.
Equation 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.
18

---

Published in Transactions on Machine Learning Research (06/2023)
of variance over all modes ought to equal V(f) provides evidence that equations, which lack this term, are correct.
Lastly, we note that Cohen et al. 2022 study Gaussian process regression in the spirit of Sollich (1999) using field theoretic tools. Though they do not explicitly discuss the omniscient risk estimate, Canatar et al.
(2021) note that their "equivalence kernel + corrections" learning curve can be viewed as perturbative expansion of the omniscient risk estimate.
B Experimental methods
B.1 Synthetic domains
Our experiments use both real image datascts and synthetic target functions on the following three domains:
1. Discretized Unit Circle. [(cos(2Tj/M sin(2rjMM) Unless otherwise stated, we use M = 256. The eigenfunc-
We discretize the unit circle into M points, X
tions on this domain are (0) 1, Φb (0) /2 cos(k and &/ (knnn(kf), for 1.
2. Hypercube. We use the vertices of the d-dimensional hypercube X = {-1,1]á giving M = 24. As stated in Section 6.2] the eigenfunctions on this domain are the nubset-parity functions with cigenvalues 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 gd = {x E 1d-11 = =1). The eigenfunctions on this domain are the hyperspherical harmonics (see, e.g., Frye Efthimiou (2012); Bordelon et al. (2020)) which group into degenerate sets indexed by 1s E N. The corresponding eigenvalues decrease exponentially with k, and so when summing over all eigenmodes when computing predictions, simply truncate the sum at kmax 70.
Figenvalues and multiplicities for these synthetic domains shown in Figure 6
19

---

Published in Transactions on Machine Learning Research (06/2023)
Unit Circle
8d Hypereube
7-sphere
100
A
B
10
C
10a
10a2
10.5
10a
10
10
10a
10a
E
10a
F
multiplicity
10
10a
10a
10a
10
10a
10
10
10
k
Figure 6: 4HL ReLU NTK eigenvalues and multiplicities on three synthetic domains. (A) Eigenvalues for for the discretized unit circle (M 256). Eigenvalues decrease increases except for few near exceptions at high k. (B) Eigenvalues for the 8d hypercube. Eigenvalues decrcase monotonically with k. (C) Eigenvalues for the 7-sphere up to k 70. Eigenvalues decrease monotonically with k. (D) Eigenvalue multiplicity for the discretized unit circle. All eigenvalues are doubly degenerate (due to cos and sin modes) except for k = 0 and & = 128. (E) Eigenvalue multiplicity for the Sd hypercube. (F) Eigenvalue multiplicity for the 7-sphere.
B.2 Image dataset eigeninformation
E'xperieetts with binary image classification tasks used scalar targets of +1. To obtain the eigeninformation necessary for theoretical predictions, select large training set with M O(10*) samples, computing the eigensystem of the data-data kernel matrix to obtain M eigenvalues ()i); and targel vector eigencoefficients v. This operation has roughly ((M3) time complexity, which is roughly the same as simply running KRR once. 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, of which are in fact part of the training set (compare with the discreto and continuous scttings of Appendix [.] and thus they too low when n/M is not negligible. We wish to predict purely the off-trainéng-ser set error Eors. We do so by noting that ME nEE + (M - nn)ooss and solving for cors (doing the same thing for for lcarnability). 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 eet al. (201))) )) but this trick allows us more standard setup in which train and test data are disjoint. Experimental test metrics for image datasets are computed with a random subset of M ~ O(1k) images from the test set.
Eigenvalues and multiplicities for four two-class image datasets shown in Figure
20

---

Published in Transactions on Machine Learning Research (06/2023)
A
B
MNIST 0/1
10P
MNIST 3/8
10a
CIFARIO bird/truck
10a1
CIFARIO decr/horse
10
1
2
10
10
10
10
10
10
10 10
10
10a
10a
Figure 7: Eigenvalues and eigencoefficients for four binary image classification tasks. (A) Kernel cigenvalues computed from 10t training points described in Appendix Spectra for CIFAR10 tasks roughly follow power laws with exponent -1, while spectra for MNTST tasks follow power laws with slightly steeper descent. (B) Eigencoefficients as computed from 10a training points. Tasks with higher observed learnability (Figure 2 place more weight in higher (i.e., inder) 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 sec- onds, while the training time of finite networks varies from seconds to minutes and depends on width, depth, training set size, and eigenmode. In particular, as described by Rahaman et al. (2019), lower eigenmodes take longer to train (especially when aiming for near-zero training MSE we do here).
B.4 Hyperparameters
We conduct all our experiments using JAX (Bradbury et al. 2018), performing exact NTK regression with the neural tangents library (Novak al. 2019) built atop it. Unless otherwise stated, all experiments used four-hiodden-layr ReLU nelworks initialized with NTK parameterization (Sohh-Dickslein el. al. 2020 with ow = 1.4, 9 = .1. The tanh networks used in generating Figure [ instead used a = 1.5. Experiments on the unit circle always used a learning rate of 55, while experiments on the hypercube, hypersphere, and image datasets used learning rate .3 or .1 depending on the experiment. While higher learning rates led faster convergence, they tended match theory more poorly, line with the large learning rate regimes described by Lewkowycz et al. (2020). Means and me--taanaard-deviatiee error bars always the statistics from several random dataset draws and initializations (for finite nets):
The toy experiment of Figure used only a single trial per eigenmode by design.
Other experiments on synthetic domains used 30 trials.
The experiments 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 function, and the true learned function will include NNGP-ternel--epenneen fluctuation term reflecting the random
initialization (Lee et al. 2019). However, by storing copy of the parameters at 0 and redefining f((x) fx) fo(x)) throughout optimization and at test time, this term becomes zero. We use this trick in experiments with finite networks.
21

---

Published in Transactions on Machine Learning Research (06/2023)
C
Varying width experiment
While kernel regression describes only infinitely-wide neural networks, is natural to wonder whether our equations are nonetheless informative outside this regime. Figure @ compares predicted learnability and MSE with experiment for hypercube eigenmodes with networks with varying widths. Our predictions remain informative down to width 50, and lower-frequency modes are better learned at all widths, suggesting that kernel cigenanalysis has a role to play even in the study of feature learning.
1.2
width oo
width 500
width 200
0.8
((D)
0.4
0.0
D
width
E
width 50
width
1.0
(D)
0.6
0.4
0.0
2.
width
H
width 500
width 200
1.0
(
width 100
width 50
width 20
1.5
1.0
(D)
06
21
71.
Figure 8: Comparison between predicted lcarnability and MSE for networks of various widths. (A-F) Predicted (curves) and true (triangles and circles) learnability for four eigenmodes on the 8d hypercube. Dataset size varies within each subplot, and the width of the 4HT. ReLU network varies between subplots. (G-L) Same (A-F) but with MSE instead of learnability.
22

---

Published in Transactions on Machine Learning Research (06/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 in 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 one). Ali et al. (2019) obtained their result regarding the similarity of KRR and - under the identifcation [time] - [ridge]-1. They assume a different ridge scaling than ours, and, in our notation, identify Teft 8 n. Their KGF scaling is 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' on generalization, we must find how finite Teff affects the constant k. Recalling Equation defining R;
n Σ
A A K
+
6
we can casily see that x S (n-1_, + +T and 2 TTa). Squeczing a with these bounds, we find that, when n > Tef E, Ae, then k RJ Teff For any Teff, there thus exists some n above which additional data does not further lower λ and permit the learning of additional eigenmodes. Let us call this the regularization- limited regime, and its counterpart (in which Teff is sufficiently large and regularization effectively zero) the data-limited regime.
We can find the crossover regularization provided knowledge of the eigenspectrum. Let assume that X; ~- for some >> 1. Mallinar et al. (2022) show that Ko = k| (a (a- csc(a 1)) a n- n co. Extending their analysis finite ridge, we find that, at large n, n = n(x/Ko) -1//
1/a + +6xx) 1, or equivalently
Aig
(22)
ToffK
Inspection of Equation 22 reveals that when Teff < Ko then K 8 Taff and when Telf >> Ki then Ko. We thus expect crossover from the iintiiiaatii--imiieddeee to the data-limited regime when Toff Kg-
In Figure g we plot the theoretical omniscient risk estimate using powerlaw eigenvalues (A; (-9) and powerlaw eigencoefficients v? ~ i=a) with = 2 for various n. The close resemblance of these curves to the experimental KRR curves of Figure 3 confirm that our powerlaw loy model is good. If desired, Figures B(A.)) and Figure 9 can be viewed as the distillation of the DB phenomenon in three stages of increasing artificiality.
It worth noting that increasing n serves to both decrease k and decrease Eg. For powerlaw spectra, as n increases with fixed Teff, Eo tends to its lower bound of 1. It approaches 1 when the regularization-liniee limited regime begins.
Similar ideas regarding the scaling of KRR are discussed by Cui et al. 2021). 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. (2021). We expect that this analysis could be extended to proper KGF using the analysis of Bordelon & Pehlevan (2021).
D.1 Deep bootstrap experiments
In replicating the deep bootstrap phenomenon for neural networks, we use the same experimental setup as Nakkiran et al. (2020), a ResNet-18 architecture trained on CIFAR-10 with data augmentation (random hor- izontal flips and random crops). We optimize cross-entropy loss using SGD, with batchsize 128, momentum 0.9, and initial learning rale 0.1 with cosine decay. The /est/train curves are the mean of 4 training runs; the curves have been -oussian-smoothed to remove figh-frequency noise artifacts.
We perform kernel ridge regression (KRR) using the NTK of a fully-connected network with four hidden layers of width 500. We binarize MNIST into two classes: {0, 1, 2,3, 4} and (5, 6, 7,8, 9]. Although the test
More precisely, they study Uiner ridge regression and lineor gradient flow, but their result also applies to the kernelized versions these algorithms.
23

---

Published in Transactions on Machine Learning Research (06/2023)
curves shift slightly depending the binarization scheme, the theory curves all fall within one standard deviation of the empirical curves for all binarizations tried. The KRR test, /train curves are the mean of 10 training runs.
10-1
72 = 16
125
S
train
1000
10-3
test
n 8000
120000
10
10
104
107
10
Teff
Figure 9: Deep bootstrap theoretical test/train curves for a synthetic kernel spectrum. Here we illustrate the deep bootstrap phenomenon using hypothetical kernel giving powerlaw eigenvalues and eigencoefficients with exponent a 2. In this setting, note that finite-data test/train curves simultaneously split from the - "online learning curve' (black dot-dashed line). We see that Teff Ku (vertical dashed lines) predicts the transition from regularization-limine
to data-limited fitting for each n. (We choose a = 2 for a clean illustration the phenomenon; empirically, C-FAR-10 and MNIST give spectra with exponents closer to 1.)
E Nonmonotonic MSE at low n
Unit Circle
6d Hypercube
2 2-sphere
A
2
bet
2-66
1.25
C
1.5
1.00
{((k)
0.75
1.0
0.50
0.5
0.5
0.00
2
1
6
n2
72.
Figure 10: For difficult eigenmodes, MSE increases with due to overfitting. Predicted MSE (curves) and empirical MSE for trained networks (circles) and NTK regression (triangles) for four eigenmodes on three domains at small n. Dotted lines indicated dE/dn)n=o as predicted by Equation 16
F Additional mean-squared gradient experiments
In the MSG experiment of 4 we run KRR with a polynomial kernel on data sampled from hyperspheres of varying dimension. The polynomial kernel is K(xxx') 1 x: Tx' + (x T=')2 (a T2)33 We perform this experiment using PyTorch Paszke et al. 2019) and compute v numerically.
In the MSG experiment of 11 train finite-width FCNs eigenmodes the (discretized) unit circle.
24

---

Published in Transactions on Machine Learning Research (06/2023)
1.00
0.75
0.50
h =
k: =
0.25
4 h =
0.00
2
2
2
2
2
Figure 11: Predicted function smoothness matches experiment on the unit circle. Thcoretical MSG predictions (curves) and empirical values for finite networks (circles) and kernel regression (triangles) for various eigenmodes the discretized unit circle with M 256, normalized by the ground-truth mean squared gradient of G(f) E [1] k Because this is discrete domain, smoothness is computed using a discretization G(f) B, [f(xz)) f(2)+2)) where Iy and 1,+1 are neighboring points on the unit circle.
G Quantum mechanical analogy
G.1 Explicit equation for
Here develop tight analogy between our picture of KRR and the free Fermi gas. The free Fermi gas consists of collection of single-particle orbitals with energies {si}; connected to bath of particles at chemical potential In our analogy, we will identify orbital i with kernel eigenmode i. Each orbital will contain zero or one fermions (n; E (0,1)), with the occupation probability of orbital given by the Fermi-Dirae distribution to be (n:) = (1 H If we identify e; = X and p= - lux, we find that (n,) L;: the orbital occupation probability is precisely the eigenmode learnability.
We always choose that eigenmode learnabilities sum to This equívalent to the statement that can always choose the chemical potential μ to ensure the system contains n fermions average. An eigenmode with eigenvalue X; 2 k receives at least half unit of learnability, and orbital with energy S; S is occupied with probability at least one half.
In our system noninteracting fermions, we have thus far identified
X + 6; (energy of orbital i) In + I (chemical potential)
(23)
(24)
C. + (n:) (expected occupancy of orbital i).
(25)
What is the value of x? Observe that
(n.) e=i-H
(26)
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, we expect to get the same answer for (na) in the canonical ensemble where the total number of fermions does not fluctuate and is exactly n. This suggests that. we should attempt to compute (n4) in the canonical ensemble. By comparing the answer to the grand canonical expression, we can solve for and hence for K.
We assume total number of orbitals M > (which may be infinite). Note that the equivalence of ensembles holds only in the thermodynamic limit > 1, must take this limit at the end.
25

---

Published in Transactions on Machine Learning Research (06/2023)
In the canonical ensemble, each microstate is labeled by of list of indices 1 1 j1 Jn M corresponding to the occupied orbitals. Direct computation of the canonical partition function shows that
= m===((==
(27)
where mn is the so-called "elementary symmetric polynomial of order n':
mn mn ( xMM =
Σ
(28)
We also define the same with index i disallowed:
mp (II, xM) =
Σ
(29)
15J S...jJ..M Juti &
We find that
0ln Zc
m n- (e 51 ...., FM)
(n:)
(30)
mn E1 y.... E
Comparing Equations 26 and 30 solving for nr, and using Equation
24 we find that
m. (), (A)
K
A
(31)
for any i, where X = =1 We are free to choose > n so that X is negligible, yielding
my (A)
K
(32)
M 1n (A)
We have arrived at an erplicit expression for K. This expression "solves" Equation B the implicit equation defining in the thermodynamie limit. Numerics easily confirm a 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 к elucidated by analogy μ in the canonical ensemble. In the canonical ensemble, all orbitals are "fighting" for the supply of particles, and μ represents their "average pull' on each unit. Similarly, in KRR, we can view eigenmodes competing for the kernel's ' supply of n units of learnability, with k encoding their average pull on this supply. This analogy deepens our picture of KRR as the competition among eigenmodes for a fixed supply of learnability.
G.2 Additional analogous quantities
In the grand canonical ensemble, the total occupation N = E, concentrates about its mean n and has fluctuations given by Var[N]= (1.)((1)))))))))) (ni)) (since each site constitutes a Bernoulli variable). Comparing with equation S we find that
n/En + Var[N].
(33)
Smaller particle number fluctuations in the analogous physical system thus correspond to larger Eo and greater overfitting of noise. This provides physical interpretation of the "overfitting as overconfidence" notion of Section
The grand canonical partition function of our free Fermi gas is
ZGc
II
(1 t
(34)
The analogous quantity in KRR is
d
ZKRR =
(35)
K
26

---

Published in Transactions on Machine Learning Research (06/2023)
It holds that
i ln Zoc = (n),
(36)
0p
and indeed we find that
i In ZKRR n.
(37)
Ōln K
G.3 Universal learnability curves
Figure 5 shows that curves of Icarnability vs. eigenvalue collapse onto 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).
It is broadly worth noting that informative constants determined by self-consistency conditions are a hallmark of statistical mechanics. It is thus sensible that such a constant would be emerge from the replica calculation of Canatar et al. (2021)
H Proofs: learnability and its conservation law
In this appendix, we provide proofs of the formal claims of Section g We make use of our learning transfer matrix formalism (discussed in Appendix [.2] for these proofs as it improves clarity and compactness, but all our proofs can also be straightforwardly carried through without it. The learning transfer matrix is defined as
((D) = A ④ AΦ + +
56
with i = (x²)) and T= Ep [(P). It holds that = ((P),. It easy to see (by making one-hot
vector) that ((P) (o.) T and [(o:) = T... Property (a) (():), (() (dx) [0,
Letting be the one-hot unit vector with a one at index i, we observe that
(P)) e, (P))e
(38)
c. AΦ Φ A SI,) TT.;
(39)
X \ e ④ AΦ + SI,) T Te
(40)
z (zz + M)
(41)
E [0, 1},
(42)
where the third line we have used the fact that e; is a unit vector and is diagonal, in the fourth line we have defined z = -1/² x e, and M = Φ A + őI, zz T. and in the fifth line we have used the fact that M is positive semidefinite. Given this, L().) E [0 by averaging.
Property (b): ((P)()) L(J)= =0 0.
Proof. When n = 0, the predicted function f is uniformly zero, and so we have ((P) = L(f) = Remark. As a corollary, it easy to show that, when M finite, n M, and d 0, then ((P) C(f) 1.
Property (c): Let D. be DUr, where X, & D is new data point. Then (P))) > (p))
We first use the Mooro-Penroes pseudoinverse, which we denote by (-)+, to cast ((D) into the dual form
(P) A& Φ AΦ) Φ T -/2 p1222 A1/2) (A (A 1/22 + +01M) A 1/2
(43)
27

---

Published in Transactions on Machine Learning Research (06/2023)
This follows from the property of pseudoinverses that A(A A (AAT)(AA) + SI) for any matrix A. We now augment our system with one extra data point, getting
T = 1/2 (1 +
(A4 + + =E 2/2 + SI
A A-1/2
(44)
where & is an M-element column vector. Equations 43 and
yield that
(6,) = e T = c. p 1//2) A A1/2 2 + +dIMr) Ci C (0,) e T e (1
(45)
+ + )AV))
(A 11 ( + 5l 112) e, (46)
The rightmost expressions of Equations 45 and 46 both contain a factor of the form B(B 5I) where A is a symmetric posilive semidefinite matrix. An operator of this form is a projector onto the row space of B when 8 = and a variant of this projector with "shrinkage" when d > O, Comparing these equations, we find that the projectors are the same except that, in Equation 46 there is one additional dimension in the row-space and thus one new basis vector in the projector (provided is orthonormal to the other columns of Φ; otherwise there are zero additional dimensions).
In the case 5 0, this new basis vector cannot decrease c. T and thus ((P+)())) 2 (()) in the ridgeless case. In the case 8 > 0, singular value decomposition of the projector confirms that the addition still cannot decrease e. (DD))e This shows the desired property. It follows as corollary that increasing n + n + cannot decrease L(f).
Property (
(b:) SO. (b.) 2 0, ox, (o)) S 0, and do ((P)
aA:
Proof. Differentiating T with respect to a particular A, we find that
0 (LP) (b:) a1,
8
T(PI ij (ō.g 230 K " K
(47)
07;
where Φ. is the ith row of 4 and K = T A + őI. Specializing to the case = j. we note that o K
0 2 because K is positive definite, and λ, ' S because A is one of the positive semidefinite summands in K Σ. A + SI,,. The first clause of the property follows.
To prove the second clause, instead specialize to the case + j, which yields that
a (D) (6)) = ax
θ T = ->, K [ K-)
(48)
a
which is manifestly nonpositive bocause Ay > The second clause follows.
Differentiating Equation 56 w.r.t. 8 yields that
à TD) - - We then observe that
36
i c (6.) (p,) =
T
e e; = -N, ΦK kK- Ci.
(49)
a6
a8
which must be nonpositive because A; > 0 and - is manifestly positive definite. The desired property follows.
Property (e): E(f)= 2 B(f) 2 (1 2
Noting that |v| = ||| = 1, expected MSE is given by
E() = [(v - +) = |v/ 2v
E[ + +
=1
2v
[ + |E[
+ Var [ar[l
(50)
blas B())
variance V())
It is apparent that E()) > B(). Projecting any vector onto an arbitrary unit vector can only decrease its magnitude, and so
B(J) 1 2v B + E
E((] (1 v E((]) = 100===11-00000 -1-) n
(51)
28

---

Published in Transactions on Machine Learning Research (06/2023)
H.1 Proof of Theorem 3.2 (Conservation of learnability)
First, note that, for any orthogonal basis F on X,
v T
Σ = -
(52)
v
JEF
VEV
where V is an orthogonal set of vectors spanning IR M, This is equivalent to Tr [T(]]. This trace is given by
Tr [ = Tr T AA AΦ + + = = Tr [K(K + SI,))
(53)
When 5 0, this trace simplifies to Tr[In] = n. When 8 > 0, it is strictly less than n. This proves the theorem.
Remark. Theorem 3.2 is consequence of the fact that (D) is simply projector onto n-dimensional space spanned by the embeddings of the samples.
Derivations: the eigenlearning equations
In this appendix, we derive the eigenlearning equations for the test risk and covariance of the predicted function. Throughout this derivation, we shall prioritize clarity and interpretability over mathematical rigor, giving a derivation which can be understood without advanced mathematical lools. For a formal derivation using random matrix theory, see Jacot et al. (2020), and for a derivation using a replica calculation of a similar level of rigor as we use here, see Canatar et al. (2021).
In the interest of clarity, we begin with a brief summary of the appendix. We begin by discussing the problem setting (Section [.1]. We then define the learning transfer matrix formalism [[22 and use it to set the ridge
parameter and noise to zcro (L3]. After stating our main approximation [[.4]. we find the expectation of
the learning transfer matrix L5
[.6 using our conservation law to fix K
L8.. Taking well-placed
derivatives, we bootstrap the expectation of the learning transfer matrix to its second order statistics (T.9)
and add back the ridge and noise (1.10p. We conclude with various useful bounds on K (1.11)
1.1 The data distribution
We shall, in this derivation, consider a slightly more general setting than discussed in the main text. the main text, we supposed the data were drawn i.i.d from a continuous distribution p over Rd. Here, in addition to this case, we shall also consider a setting which the data are sampled without replacement from discrete X' C gd with |x| M. We will refer to this as the "discrete setting' and the setting with continuous distribution the "contimous setting." As discussed in Appendix B the discrete setting matches several of our experiments (namely those on the discretized unit circle and on the vertices of the hypercube).
This discrete setting clearly converges to the continuous setting as M + oo: when M > n2, the probability of sampling the same point twice negligible (and so we can drop the "without replacement? and sample with replacement as in the continuous sctting) and, by distributing X' throughout Rd with point density proportional to p, we approach sampling from continuous distribution. Alternatively, we could imagine X' consists of M i.id. samples from p, so that, when we later sample n points from X, they are themselves i.i.d. samples from p as M + oc. 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 the discrete setting are defined as M- Exe K(x, x')(('''))===->->>)))))))")))>) (.).(a)). Note that, this case, the number of eigenmodes is M, the same number as the cardinality of X. In the continuous setting, the number of eigenmodes is infinite (though there may be only finitely many with nonzero eigenvalues).
29

---

Published in Transactions on Machine Learning Research (06/2023)
but, like Bordelon et al. (2020). will find it useful to assume that 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 A as typical the study of kernel methods and as our final results will confirm.
Our subsoquent derivation will generally apply to both the discrete and continuous settings.
1.2 The learning transfer matrix
We begin by translating the KRR predictor into the kernel eigenbasis. Because ((x,²') EM (z) we can decompose the empirical kernel matrix as KDD = $ T A where A =
diag(A), Aw) and is the x n "design matrix' given by tij = )x(x))
The predicted function coefficients are given by
v (d f) (KDD - Tv,
(54)
where we have used the orthonormality of the cigenfunctions and defined 10b1, (x(xy) to be the i-th row of 4. Stacking these coefficients into matrix equation, we find
AΦ - =II,) 4 = AΦ Φ
Φ v= T
(55)
where the learning transfer malrir
((P) = A& 1 AΦ +I,,,
(56)
is an M x M matrix, independent of f, that fully describes the model's learning behavior on a training set The learning transfer matrix the same as the "reconstruction operator' of Jacot et al. (2020) viewed as a finite matrix instead of a linear operator. Full understanding of the statistics of T(2) will give us the statistics of v and thus of f, and so our main objective will be find the mean and the covariance of (P)),
I 15
1.3 Setting the ridge and noise to zero
Our setting includes both a nonzero ridge parameter and nonzero noise. However, it 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 al. (2021) for discussion of these). Inverting these equivalences, eigenvalues and convert e² to power in vero-eigenvalue mode, and thereby permit ourselves to consider neither ridge nor noise in our derivation and add them back at the end. Here we explain our method for doing so.
should expect to be able to convert 8 into small increase to many
The ridge parameter can be viewed as a uniform increase in all eigenvalues. We first observe that M- 4 Ln in the discrete case. Letting (A;) 6) denote the learning transfer matrix with eigenvalue matrix A and ridge parameter 6, it follows from Equation 56 and this fact that
(PP) (A:6) = A (A
8 IM M
(A+
8 I 0)
T(D)
(57)
M
In the continuous case, --14 + I, as M oo (since the columns of t are uncorrelated), and since M is very large in the continuous setting, we are again free to use Equation 57
As for the noise, we simply set e² for now and, once we have our final equations, add power to a hypothetical zero-eigenvalue mode.
We take this terminalogy from control theory in which, a system under study, "transfer function" maps inputs to outputs, or driving response.
30

---

Published in Transactions on Machine Learning Research (06/2023)
1.4 Assumption: the universality of 4
We wish to lake averages over + in finding the statistics of T(P), The distribution of ④ is in fact highly structured (reflecting the eigenstructure of the kernel), and we know only that , = 63y- 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 lid 1).
This universality assumption is also made in comparable works studying KRR (implicitly by Bordelon et al. 20200; Canatar et al. (2021) and explicitly by Jacot ct al. (2020)), and analogous works on lincar regression (e.g. Hastie et al. 2022 Wu & Xu 2020 Bartlett et al. 2021) assume the features are either Gaussian or nearly so (e.g. uncorrelated and sub- Sub--aussian). See Appendix A for further references to relevant literature.
The validity of this approximation is ultimately justified by the close match of ours and others' theories with experiment.
Why should this rather strong assumption give good results for realistic cases? This is an active area of rescarch and satisfying answer has not yet emerged to our knowledge. However, this universality phenomenon has precedent in random matrix theory: many features of the spectra of random matrices depend only on the first and second moments of the matrix entries (within certain conditions), and so if one knows a matrix ensemble interest obeys this property, then one might as well just study the simplest distribution with the same moments, which often Gaussian ensemble. These results are akin to central limit theorems for random matrices.
It is worth noting that, while assumne Gaussian entries for simplicity, we do not actually require condition quite this strong. We will only really use the facts that the distribution is symmetric and that certain scalar quantities concentrate be sufficient on its own.
I.7 Wei et al. (022) discuss "local random matrix law' which we expect would
1.5 Vanishing Off Diagonasss of IE [T()]
We next observe that
ES A ( AU4) -1 xT] = -E AUT + (Φ AΦ)
o T
(58)
where U is any orthogonal M M matrix. Defining U(m) as the matrix such that U(m) dab(1 26
noting that ( A, and plugging U(m) in U in Equation 58 we find that
[P) = (u(())
T(P) U(m) = (-1 (om)
((P) mh
(59)
ab
By choosing a, conclude that E T (D)
= 0 af bb
1.6 Fixing the Form of E [T(]]
We now isolate a particular diagonal element of the mean learning transfer matrix. To do so, we write E in terms of X; (the ith eigenvalue), A() (A with its ith row and column removed), के (the ith row of b) and (B) ( with its ith row removed).
Using the Aheeman--Morrisse matrix inversion formula, we find that
④ T [ -1 =
A
+ A:000..)
(1)
A; $ (1)
PPΦ.T ( ( (())
(60)
A
(1))
-1
(0)
1 X
(1) A()
31

---

Published in Transactions on Machine Learning Research (06/2023)
Inserting this into the expectation of T(D, we find that
E
T
D
E
(1)
A10 T
④ A
Φ:
2
A
Φ.
A
(3)
Φ
Es
(1)
Φ:
1 x
A
Φ:
(61)
Ax Φ Φ
(1)
Φi
Ex (,
A x (1)
1
where x (..00)
=
Φb (1)
(1))(1)) (1)
is nonnegative scalar.
1.7 Concentration and mode-independence of (+)
Important quantities in statistical mechanics systems are typically self-averaging (i.c. concentrating about their expectation) in the thermodynamie limit. Self-averaging quantities are the focus of random matrix the- ory, and generalization metrics in machine learning also tend to be self-averaging under most circumstances (e.g. resampling the data and rerumning a training procedure will typically yield similar generalization error). Here we argue that K (+) is self-averaging in 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 Ki
(+) were not self-averaging, then for modes i such that x; Kg (4) (P) and thus (Ø:) would not be
self-averaging either. However, because ((.) 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 (()) are indeed small in practice, especially at large We thus replace i with its expectation
K; E4
We next argue that H2 is approximately independent of i, so we can replace it with a mode-independent constant K. This, too, could be argued rigorously by means of random matrix theory. We opt instead for an digenmode-removal argument inspired by the cavity method of statistical physics (Del Ferraro et al., 2014).. Observe Chat, in the thermodynamic limit, the addition negligible effect on any observable and thus Kg. We shall here show that, by inserting eigenmode and removing another, we can transform R; into Kj for any and j. implying that n; R Ki..
removal of single eigenmode should have a
Assume that the addition or removal of a single eigemmode negligibly alfects кę- Concretely, assurne that K R Rf, where kt K; computed with the addition of one extra eigenmode of arbitrary eigenvalue. We choose the additional eigenmode to have eigenvalue X; and we insert it at index i, effectively reinserting the missing mode into 4 (i) and A()-
To clarify the random variables in play, we shall adopt more explicit notation, writing out o in terms of its row vectors as L() [#r.... P $4.1..... ØM T. Using this notation, we find upon adding the new eigenmode that.
32

---

Published in Transactions on Machine Learning Research (06/2023)
$ $ (1))
Φi
(62)
-1 --1
(obe) J
Φ ((o),.,, Pi-1, Pi+1, pa/ (1)l1,, I1-1, P.t1, (Mrl')- (Ml" pi
(63)
[00 (1o).... Pi S. 014 A 11 E |M] |m] Φ; [ (64)
23 Ki
E (obe ) 1
where A is the original eigenvalue matrix and Φ is the design matrix row corresponding to the new mode.
We can also perform the same manipulation with Hy (j * i), this time adding an additional eigenvalue X, at index j, yielding that
Φ (G)
03
(65)
xM|])) Φ3 1-1
(ob c-1
(66)
K3 = E (o 1
(67)
Each is expectation over M +1 vectors from the isotropic measure T he statistics of these M vectors are symmetric under exchange, so we are free to relabel them. Equation
We now compare Equations
64 and
67
64 is identical to Equation 67 upon relabeling Ø; + Φj, Φ; + Φi, and Φj + Φ,, so they are equivalent, and A =x=] x5- This in turn implies that H2 R Ky- In light of this, we now replace all Ky with a mode-independent (but ys-yet-un)owwn) constant & and conclude that
T D
A Xa +
E
(68)
In summary, we have argued that K2 is not significantly changed by the addition or removal of single eigen- modes, and two such changes permit us to transform K; into Kj, so they are therefore approximately equal.
Our argument here similar to the cavity method of statistical physics (Del Ferraro al. 2014)), which essentially compares the behavior of weakly-interacting system with and without single element. The cavity method is often used as simpler and more intuitive alternative to the replica method, a role it reprises here (contrast our approach with the replica approach of Canatar et al. (2021)
1.8 Determining
We can determine the value of k by observing that, using the ridgeless case of Theorem 3.2
ΣE[TP] = Σ X
A; + =
(69)
This a much more straightforward method of fixing this constant than used comparable works. The ability use the ridgeless version of Theorem 3.2 the main motivation for setting 0 at the start of the derivation.
1.9 Differentiating w.r.t. A to Obtain the Covariance of (D)
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 I. [T(P)], which lends credence
33

---

Published in Transactions on Machine Learning Research (06/2023)
to thesis that understanding modewise learnabilities is sufficient for understanding more interesting statistics of f.
We begin with a calculation that will later be of use: differentiating both sides of the constraint on K with respect to a particular eigenvalue, we find that
M
M
A ()g + 16)2 04; (A:+ + 1:)2 = O,
K
(70)
a4:
K
j=1
yielding that
On
R² a(>; xs)2
where
(71)
aλ;
()i xT)²
We now factor T(D) into two matrices as
( AZ,
where
Z
+
A
Φ
(72)
Unlike T(P), the matrix Z has the advantage being symmotric and containing only one factor of A. Wo will find the second-order statistics of Z, which will trivially give these statistics for T(P), From Equation we find that the expectation of Z is
[ = (A + =
(73)
We also define a modified Z- Z-matrix ( matrix. Because the measure over which + is averaged is votation-invariant we can equivalently average over $ = U& with the same measure, giving
( T - TT where U is an orthogonal M M
EΦ ( =
E
U
U
(
AΦ)
E+ ZU = U (A+ U. $ U
(74)
It is similarly the case that
Ex
Z U1) Dey (Z
(2)
Ex ZUTZU), (U zU) ke
(75)
Our aim will be to calculate expectations of the form E+ [Z, Zue]. 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(m)
(1 25am) and observe that, because A is diagonal, (U(m))TAAE AU(m) = A and thus Z(U())) Z. Equation then yields that
75
E+ Z., Zue] = (-1)6in fin +6xm 40mm
Ex Zi Zue],
(76)
from which it follows that E. Z., Z 0 if any index is repeated odd number of times. In light of the fact that Zig = Zio, there are only three distinct nontrivial cases to consider:
Eg ZZ Zu],
2. E. Zz Zay] with # j, and
34

---

Published in Transactions on Machine Learning Research (06/2023)
3. E+ Zyy with i +
We note that we are not using the Einstein convention of summation over repeated indices.
Cases 1 and 2. We now consider differentiating Z with respect to particular element of the matrix A. This yields
aZ.
- ( AΦ) 0,0% (Φ)A d: Zie,
(77)
jA
where before Φ; is the i-th row of Φ This gives the useful expression that
Ziy Zael
EZZ
(78)
aAyk
We now set f= == j and evaluate this expression using Equation
73
concluding that
A; (x)x
1
1
On
E = = 02,
dij
(79)
(hr
k3)
and thus
1
n²²
Cov [Z. = Cov |ov|Z.j. Zyd
(80)
(Ae + x3)2 0bg
a(>i + x) + x)2²
We did not require that i * and so Equation 79 holds for Case as well as Case 2.
Case 3. We now aim calculate E[ZaZ,y] for / j. We might hope to use Equation 78 in caleulating Zyyl, but this approach is stymied by the fact that would need to take derivative with respect to Agr but ( using an approach which is equivalent to rediagonalizing A after symmetric perturbation. From the definition of ( we find that
only have approximation for Z for diagonal A. We can circumvent this by means of
z
U
aU ij
aU ji
U=Iv
=
Φ AΦ
T0,10T o.A t
(Ø - 0;;
= = A1) (Z), + Zz) (81)
Differentiating with respect to both U.y and Usa with opposite signs ensures that the derivative is taken within the manifold of orthogonal matrices. Now, using Equation 74 we find that
a
(
a
a
E
[UT (A + +KIN))-'U -UU---U U-IN
JU
aU ji
U=
(82)
1
A + k
Xq +
Taking the expectation of Equation algebra, we conclude that.
plugging in Equation
79 for E [2,)) comparing 82 and performing
35

---

Published in Transactions on Machine Learning Research (06/2023)
n.2
E Z, = (A: + R)( + +x)
(83)
q(A: - k))
( + x2)
and thus that Zu: Z5z are anticorrelated with covariance
x²
Cov [Z, 25y1
(84)
a(A: + k) + x)²
Cases 1-3 can be summarized as
x² (8.r0e + 81005 - 6esŌke) a(\; (A; + ()x x)e +K)
Cov Zuel
(85)
Using the fact that T(p X,Zıj, defining L, = >1(1; + - and noting that g= =Ei (.)) we find that
Cov ((()) T(P) let
C1(1- - C,) - Le) (ō:r + 81rd5M desōRe).
(86)
n2 Σ m
C
Noting that E(f) B[vv-[ eigenmodes, we find that expected MSE is given by
1alv-997 0/3], recalling that v =
TD)),, and using Equation 86 to evaluate sum over
E(f) = En C2
-1-
(87)
Taking sum over indices of v, we find that the covariance of the predicted function can be written simply in terms of MSE
Cov (0,, 0,] L3E(f) 8zz-
(88)
1.10 Adding back the ridge and noise
We have thus far assumed 8 We can now add the ridge paramcter back using Equation
57
To add a
ridge parameter 6, we need merely replace di + do X7 and then change T. - Ax + yields that
This
M 8
E
(D)
Az A A + M
(89)
+ K
16. E5e + 8.edgr - 8.y8ke)
(D)
(D) T(())
Cov
(90)
ke
(\: <) 3/4 + x)x + 1/4 +) 1/4 + +x)
A A = and
M
\ + oM
where x20 0 satisfies Σ
= Σ
(91)
A +
(Aj 3/ k))
j=l
Taking either 8 = or M + co, we find that
A
5
(92)
A +
36

---

Published in Transactions on Machine Learning Research (06/2023)
and the mean and covariance of T()) are again given by Equations 68 and 86
To summarize this simplification: in the continuous setting (M - xc), we recover the results of prior work. In the discrete setting with zero ridge, we find that these expressions apply unmodified. In the discrete setting with positive ridge, we find that these expressions contain corrections with perturbative parameter M- In the main text, we report the expressions with M 0, and our experiments obey this condition.
Modifying v place power e² into an eigenmode with zero eigenvalue, Equation 87 for MSE becomes
E() E
(93)
1.11 Properties of
In experimental settings, K is in general easy to find numerically, but for theoretical study, we anticipate it being useful to have some analytical bounds on K 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 K.
Lemma I.1. For K 2 solving E A. + = n, with positive eigenvalues { ordered from greatest to least, the following properlies hold:
Ae+x
(a) xo when n O, and x = O when - M and ā = 0.
(b) is strictly decreasing with
(6) - (5 E1+ Ei=e+1 >.) for all l (0...., n 13.
(d) K x de 1e 1) for all l M}.
Proof of property (a): Because E A + is strictly decrcasing with x for ạ 2 0, there only be one Asti solution for a given The first statement follows by inspection, and the second follows by inspection and our assumption that all eigenvalues are strictly positive.
Proof of property (b): Differentiating the constraint on k with respect to n yields
M
-ôl dx =
M
Σ
A
+
which implics that dR
Σ
+
< 0.
(94)
R² dn
dn
(As
x)2
x²
Proof of properly (c): We observe that n ΣM follows.
S st
Di=e+1
d
+
The desired property
Autx
x
n²
Proof of property (d): We set 5 = 0 and consider replacing A; with x if < l and 0 if l. Noting that
d Dr. A 2 Σln Art Xrte The desired this does not increase any term the sum, we find that n = EM Xrtr
property in the ridgeless case follows. A positive ridge paramcter only increascs K, so the property holds in general. We note that positive ridge parameter can be incorporated into the bound, giving
2 (e (e-n)de m)de + 8 V ((e m)de 8)² Andde
(95)
We also note that, observed by Jacot et al. (2020) and Spigler al. (2020), the asymptotic scaling of k. can be fixed if the kernel eigenvalues follow power law spectrum. Specifically, if X₂ ~i-a for some >> 1,
then Jacot et al. 2020 16 show that
== 0(ōn -1 1 n)).
(96)
16 Jacot et al. 2020 scale the ridge parameter proportional in their definition of kernel ridge regression; our reproduction of their result is translated inta our scaling convention.
37


Reviews:
[{"review_id": "mJKCumXBlT", "reviewer": "Reviewer_jTRA", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "# Strengths\n- The theory part of this paper is neat. The concept of learnability and the corresponding conservation law is insightful and novel.\n- The derived eigenlearning equations may have significant usage in related works.\n- The explanation of deep bootstrap and the new understanding of adversarial robustness are interesting.\n- The paper is very well written.\n\n# Weaknesses\n- Although I acknowledge that this is a theoretical paper aimed at introducing a new framework to explain and analyze existing mechanisms, the experimental results presented are relatively unconvincing. For instance, the binary image classification tasks were performed with a kernel defined using a fully-connected four-hidden-layer ReLU NN on a dataset consisting of O(10^4) samples. To me, more systematic verifications utilizing different kernels, larger datasets, more domains, and multi-dimensional KRR are necessary.\n\n- I still have concerns about the potential new insights that this work can offer to the mainstream deep learning community. For instance, can this method be utilized to analyze NN initialization for network pruning or any other related applications?\n\n- You will rely on an eigendecomposition step for the following analyses. What is the time cost/complexity of doing so? Will it introduce a large burden for large data scenarios?", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper develops a unified framework giving closed-form estimates for the test risk and certain generalization metrics of KRR. In particular, it shows that KRR can be interpreted as an explicit competition among kernel eigenmodes. The derived framework is finally used to offer theoretical explanations to and generalize previous works. It is interesting that the framework also helps to draw an analogy between KRR and a canonical model in statistical physics.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "- Please address the issues raised in the Weaknesses section in your revision. I am especially interested in seeing more thorough empirical verification and gaining a better understanding of the new insights this paper can provide for deep learning.", "broader_impact_concerns": "None", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "fblO03sWol", "reviewer": "Reviewer_hbK5", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strenghts:\n* The proposed framework based on learnabilities seems intuitive, has tight links to the statistical physics of the free Fermi gas, and leads to insights on various observed phenomena in deep learning.\n* Some observations seem new to me, such as eqs (15) and (16), though not particularly surprising given the risk formulas.\n* The theory is illustrated with several experiments in various synthetic and real settings, with both kernels and real networks.\n\nWeaknesses:\n* The obtained \"eigenlearning equations\" are essentially the same as those from other works, e.g. Canatar/Bordelon et al, Jacot et al, as well as various other works from the literature on double descent. This makes it difficult to see how the \"learnabilities\" and their \"conservations\" provide any new insights/interpretability on the results.\nIn particular, the quantities $\\frac{\\lambda_i}{\\lambda_i + \\kappa}$, referred here as \"eigenmode learnabilities,\" are quite standard in the study of ridge regression, even from before the \"double descent\", e.g. in the notions of degrees of freedom/effective dimension, leverage scores, and spectral filters (see, e.g., [this paper](https://arxiv.org/abs/1106.2363)).\n\n* The learnability on other functions $f$ that are not eigenfunctions could be new, but it does not seem to be of much relevance in the results when f is not a basis function.\n\n* Beyond interpretability, the authors claim the results are \"simpler\" to derive than in other works, by overcoming the need for RMT tools, or replica calculations. If this is the key difference with other works, then I encourage the authors to provide at least a proof sketch of the eigenlearning equations in the main paper, since currently the proof in the appendix does not seem particularly simple.\n\n* The vignettes are interesting in that they can all be explained from the proposed equations, but the individual findings do not seem to provide much new insight over previous works. E.g. the deep bootstrap see the cited Ghosh et al.; for lower bounds on high-degree parities, e.g. [here](https://arxiv.org/abs/2001.04413) (section I), **do** use the spectral properties of dot-product kernels in the parity basis (in contrast to what is mentioned in your footnote 7); for robustness, the \"mean squared gradient\" quantity was already considered in other works, e.g. [here](https://arxiv.org/abs/2106.02630) (eq. 5).", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper studies properties of kernel ridge regression, by providing tight expressions of various empirical and population quantities in terms of key quantities referred as \"learnabilities,\" which correspond to alignments between target functions and their ridge estimates.\nThe authors derive certain key properties of these quantities, such as conservation of averages over bases (Theorem 3.2) and monotonicity when increasing the dataset size (Prop 3.1). Estimates of learning quantities such as excess MSE risk are given in Sec 4.1 in terms of such quantities, as well as an effective regularization $\\kappa$, which can exceed the applied regularization $\\delta$.\n\nThe authors provides interpretations of these results, as well as various \"vignettes\" of how they help understand various phenomena, such as the \"deep bootstrap\", adversarial robustness, and hardness of learning high-degree parities.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "The main changes I'd like are the following:\n* further justification of what makes the analysis in the manuscript different than in other works, e.g. by providing a simple proof sketch, or clarifying the novelty of the proposed interpretation\n* better comparisons to related works.\n\n\nOther minor comments/typos:\n* eq. (2): the $v_i$ are not always bold? (e.g. the line just after)\n* eq. (20): could you provide more comments on what this explicit formula means, or how it is useful?", "broader_impact_concerns": "none", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "QLsD5JGo37", "reviewer": "Reviewer_xJDV", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "DISCLAIMER: I have not checked the proofs and derivations in the appendix in detail. I am also not deeply familiar with the related literature.\n\nStrengths:\n- The paper is well-written and makes a strong case.\n- The theory seems to fit the empirical observations really well.\n- The idea of learnability seems novel and useful.\n\nWeaknesses:\n- Some of the assumptions are a bit unintuitive and could be elaborated.\n- The practical usefulness of the framework is unclear.\n\nMajor comments:\n- How strong is the assumption that $\\left\\Vert f \\right\\Vert = 1$? I suppose you could always re-normalize the function by its actual norm, but I would guess that in most practical applications you don't know the norm of the true function, right?\n- The \"universality\" assumption for replacing kernel features with Gaussian ones seems quite strong to me. I appreciate that you say that other works have also used this, but for readers unfamiliar with the literature, it could be useful to elaborate a bit on why we can make that assumption.\n- Is your proposed framework mainly meant for explaining observed behavior on KRR models post-hoc or can it also be used in practice, e.g., to choose the optimal value for $\\delta$ that would minimize the test MSE or something like that? For a practitioner, what should be the main takeaway from the paper?\n\nMinor comments:\n- Your quotation marks seem to be inconsistent, try to use `` and '' in LaTeX\n- Sec. 6.4: probabilies -> probabilities", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The authors offer a theoretical study of kernel ridge regression in which they propose a novel quantity they call \"learnability\". They then proceed to show that this quantity obeys a conservation law and that many quantities of interest, e.g., train and test mean squared error and the bias-variance tradeoff, can be described in terms of learnability. They show that their theoretical predictions fit empirical observations well in several example problems and also explain some known phenomena from the literature in terms of their framework.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "I think this is overall a very interesting paper, I would just generally like to see more critical discussion of the assumptions and comments on the practical use cases for the framework.", "broader_impact_concerns": "No concerns", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The reviewers agreed that the paper provides interesting theoretical insights and should be accepted. Most of their concerns were addressed by the author response.
Decision: Accept (poster)