Predicting Kernel Regression Learning Curves from Only Raw Data Statistics
Authors: Dhruva Karkada
Joseph Turnbull
Yuxi Liu
James B Simon
Venue: ICLR 2026 Poster (2026)
Keywords: kernels
kernel regression
neural tangent kernel
eigenstructure
learning curves
natural data
MLPs
Primary area: learning theory
TL;DR: We give an analytical approximation to kernel ridge regression eigenstructure that works well even on real data, and are thus able to predict KRR learning curves from raw data statistics.

Abstract: We study kernel regression with common rotation-invariant kernels on real datasets including CIFAR-5m, SVHN, and ImageNet.
We give a theoretical framework that predicts learning curves (test risk vs. sample size) from only two measurements: the empirical data covariance matrix and an empirical polynomial decomposition of the target function $f_*$.
The key new idea is an analytical approximation of a kernel’s eigenvalues and eigenfunctions with respect to an anisotropic data distribution.
The eigenfunctions resemble Hermite polynomials of the data, so we call this approximation the \textit{Hermite eigenstructure ansatz} (HEA).
We prove the HEA for Gaussian data, but we find that real image data is often ``Gaussian enough’’ for the HEA to hold well in practice, enabling us to predict learning curves by applying prior results relating kernel eigenstructure to test risk.
Extending beyond kernel regression, we empirically find that MLPs in the feature-learning regime learn Hermite polynomials in the order predicted by the HEA.
Our HEA framework is a proof of concept that an end-to-end theory of learning which maps dataset structure all the way to model performance is possible for nontrivial learning algorithms on real datasets.

Published as a conference paper at ICLR 2026
PREDICTING KERNEL REGRESSION LEARNING CURVES FROM ONLY RAW DATA STATISTICS
Dhruva Karkada Joseph Turnbull Yuxi Liu", James B. Simon
{dkarkada, joeyturnbull, yuxi liu, jsi bbiekeerkkley..o edu
ABSTRACT
We study kernel regression with common rotation-invariant kernels on real datasets including CIFAR-5m, SVHN, and ImageNet. We give a theoretical framework that predicts learning curves (test risk vs. sample size) from only two measurements: the empirical data covariance matrix and an empirical polynomial decomposition of the target function f.. The key new idea is an analytical approximation of kernel's s eigenvalues and eigenfunctions with respect to anisotropic data distribution. The eigenfunctions resemble Hermite polynomials of the data, so we call this approximation the Hermite eigenstructure ansatz (HEA). We prove the HEA for Gaussian data, but we find that real image data is often "Gaussian enough" for the HEA to hold well in practice, enabling us to predict learning curves by applying prior results relating kernel eigenstructure to test risk. Extending beyond kernel regression, we empirically find that MLPs in the feature-learning regime learn Hermite polynomials in the order predicted by the HEA. Our HEA framework is a proof of concept that an end-to-end theory of learning which maps dataset structure all the way to model performance is possible for nontrivial learning algorithms on real datasets.
INTRODUCTION
The quest to understand machine learning is largely motivated by a desire to predict and explain learning behavior in realistic settings. This means that, sooner or later, scientists of machine learning must develop theory that works for real datasets, somehow incorporating task structure into predictions of model performance, optimal hyperparameters, and other objects of interest. This necessity has been the elephant in the room of much of deep learning theory for some time: despite much progress in the study of neural network training and generalization, it has proven difficult move beyond simplistic models of data and make analytical predictions applicable to real data distributions.
The central difficulty is of course the complexity of real data. There can be no full analytical description of any real data distribution, so it is difficult to see how we might develop mathematical theory that describes how such a dataset is learned. How might we hope to proceed?
One way forward may be to identify comparatively succinet "reduced description" of a data distribution that characterizes its structure, at least insofar as a particular class of learner is concerned. We would like this reduced description to be sufficient predict quantities of interest yet minimal enough to be a significant reduction in complexity. Ideally, we would like the theory that makes predictions from this reduced description be mathematiallly simple, and would like the description itself to give some insight into how the class of learner in question sees the data.
In this paper, we present such reduced description of high-dimensional datasets that is suitable for describing their learning by kernel ridge regression (KRR) with iintriinnnivraantt kernels. We find that just the data covariance matrix Σ = E /= together with Hermite decomposition of the target function,' is sufficient to characterize learning by notation-invarian kernels. We obtain this reduced description, which we term "Hermite eigenstructure," from study of Gaussian data, but we nonetheless find predictive for complex image datasets including CIFAR-5m -5m, SVHN, and
UCC Berkeley @ Imbue Joint primary authorship. Work completed during summer internship at Imbue. Code: https: / //gittii /gtt com/ Turn /eemmieeriii perritte titeeeee e genstructur ructure-ansat? See Section 3.2 and Appendix for review of Hermite polynomials.

---

Published as a conference paper at ICLR 2026
KRR algorithm
data space
(I)
feature space
estimator (data sprce),
Goussian kemel CIFAR-5m
MSE
1:00
implicit feature map
domesticated VS, wild
ridge reg.
0.30
dog vo all others
deet vs, hunse
Viu Mkg
0.25
cur vi. stup
plane vs. frog
10"
struccture
Kernel eigenstructure
Avg-casse prodictions
training samples
Theory
PCA variances r
Spectrum X; feature variances)
mean estimator
test emtrr
Taplace Imagenet32
PCA directions U
Eigenfunctions (b(x)) (o((s) A, (,))),
sample complexity
train error
Prodicted
8
qusibaik
etc.
culic
quartic
Hermite Eigenstructure Ansatz (this work)
Known eigenfrrmework
Empirical sample complexity flea
We provide an end-to-end theory of learning for kernel ridge regression (KRR) that maps minimal statistics of the data distribution to test-time performance. (Top left.) KRR implicitly consists of two steps: (1) the kernel maps the data to high-dimensional nonlinear features + (x)), then (2) it fits a linear estimator to these features. Let the covariance in data space be E [ UTU and let the covariance in feature space be E (<)())))((())))))))))))())))(( (x)] EAE (Lower left.) We introduce an ansatz (blue box) that predicts the feature covariance statistics (E, A) from only the data covariance (U, Т) and the functional form of (.))) This is sufficient to predict average-case test error using known results (green box). (Top right.) We are able to predict learning curves for KRR image tasks without requiring omniscient knowledge of the feature statistics (i.e., without ever constructing or diagonalizing a kernel matrix). (Bottom right.) We are able to accurately predict the KRR sample complexity, including constant prefactors, for learning polynomials of the ImageNet dataset. See Figure for additional plots and Appendix D for experimental details.
Figure I:
ImageNet. From just the covariance matrix, we can predict kernel eigenstructure and learning curves for synthetic functions. Using the true labels to estimate the target function's Hermite decomposition, we are additionally able to predict KRR learning curves on real tasks. Unlike previous approaches for predicting learning curves, this method does not require numerically constructing or diagonalizing a kernel matrix to find the kernel eigensystem.
Our approach relies on recent results the theory of KRR which assert that knowledge of the kernel's eigenstructure with respect a data measure is sufficient to predict learning behavior (Sollich (2001); Bordelon et al. (2020): Jacot et al. (2020): Simon et al. (2021)). These works provide a set of equations that map this eigenstructure predictions of test-time error. Our central observation is that, despite the complexity of high-dimensional datasets and the great variety of rotation-invariant kernels, this kernel eigenstructure is often very close a simple analytical form expressible in terms of Hermite polynomials in the original data space. We term this claim the "Hermite eigenstructure ansatz," " and we identify a (broad) of conditions under which empirically holds.
Concretely, our contributions are as follows:
We propose the Hermite eigenstructure ansatz (Section 4), a closed-form expression for the eigensystem of inttrioninvvriant kernels on real datasets. We find empirically that it holds to an excellent approximation for real image datasets (Figure 2).
We prove that the HEA holds in the case of Gaussian data for two limiting cases of the kernel function (Theorems I and 2).
We use the HEA to predict KRR learning curves CIFAR-5m, SVHN and ImageNet from only the sample covariance and Hermite decomposition of the target function (Figures I and 3).
We empirically find that MLPs in the feature-learning regime leamn Hermite polynomials of CIFAR-5m in the same order the HEA predicts for KRR (Figure 4).
2

---

Published as a conference paper at ICLR 2026
2 RESEARCH CONTEXT AND RELATED WORKS
Kernel models as proxies for neural networks. Our motivation for studying KRR comes from the "neural tangent kernel" (NTK) line of work, which finds suitably parametrized anfinite-width networks are equivalent KRR, and that for MLPs, the kernel function is rotation-invann et al., 2018; Jacot et al., 2018). Kernel methods have proven useful as models of network dynamics and optimization (Chizat et al., 2019; Du et al., 2019; Bordelon & Pehlevan, 2021).
(Neal, 1996; Lee
Learning curves for KRR. Motivated by the NTK, many recent works have converged on set of equations which predict KRR's ' test-time error from the kernel and task eigenstructure (Sollich, 2001; Bordelon et al., 2020; Jacot et al., 2020; Simon et al., 2021). This "KRR eigenframework" depends on the kernel's eigenvalues and eigenfunctions with respect to the data distribution. Our main result an approximate analytical expression for these eigenvalues and eigenfunctions, permitting the inductive bias of KRR to be studied directly in the data space. Appendix C reviews this eigenframework.
Exactly-solved cases of kernel eigenstructure. Exact kernel diagonalizaation with machine-learnnng relevant kernels are known in many highly torus T and iotation-invariant kernels on the sphere Sd (Mei & Montanari, 2019). Moving to anisotropic domains, Ghorbani et al. (2020) gave the eigenstructure of rotation-invariant kernels when the measure "product of spheres" of different radii. The case of a Gaussian kernel on a Gaussian measure was solved exactly by Zhu et al. (1997). Our Hermite eigenstructure ansatz is consistent with all these results and unifies them in a limiting case.
settings, including stationary kernels on the
Eigenstructure of dot-product kernels on anisotropic Gaussian data. Concurrent work by Wortsman & Loureiro (2025) takes up the same mathematical problem as us: finding the eigenstructure of dot- dot-product kernels on anisotropic Gaussian data. They prove upper and lower bounds on kernel eigenvalues that agree with the eigenvalues we propose our Equation (5). When studying the generalization of KRR, they switch from dot-product kernels to Hermite polynomial kernels. Our work provides a justification for this replacement: our HEA states that this swap changes the eigensystem only slightly.
Modeling data with a Gaussian measure. A developing body of literature argues that MLPs' learning of complex data distributions is similar to the behavior would see if the data were Gaussian with the same covariance (Goldt et al., 2020; Refinetti et al., 2023). We broadly adopt this lens in the study of KRR and find that, indeed, the data is well-modeled as Gaussian. We note that this is distinct from the "Gaussian universality" assumption typically made in the derivation of the KRR eigenframework. See Appendix for discussion of the difference.
Single- and multi-index models. Much recent literature has studied MLPs' learning of single- and multi-index functions which depend only on rank-one or rank-k projection of the input (Dudeja & Hsu, 2018; Bietti et al., 2022; Dandi et al.. 2023; Lee et al., 2024: Mansavi-Hossein et al., 2024). This work partially motivated our study, and the multidimensional Hermite basis we use this work is basis of multi-index functions. Prior work in this vein has found that higher-order Hermite polynomials require more samples or gradient steps to learn. Two ways in which we depart from this body of work are that (a) we seek to predict the value of the test error (including constant prefactors), not just asymptotics or scaling laws, and (b) we study anisotropic data, which allows application of our results to real datasets.
Analytical models of data. Several recent works have proposed thcoretical models for the hicrarchical structure in image and text data with the aim of understanding neural network performance on such datasets (Cagnetta et al., 2024; Sclocchi et al., 2025; Cagnetta & Wyart, 2024). Our work in this paper is undertaken in similar spirit.
3 PRELIMINARIES
We will work in a standard supervised setting: our dataset consists of n samples X' = {m>))_ drawn i...d. from a measure 4 over Rd,, and we wish to learn a target function f- from noisy training labels
y = {ux 1" where y; fx,)) (O, e²) with noise level 0. We will assume with minimal loss of generality that μ has mean zero: Em=a(æ] = O. Once a learning rule returns predicted
function f. we evaluate its test mean-squared error MSE = Enz (fx( f(x))]] + We write
(g. h)p == Eaz (x)) and 1 (g. g), for the 1,2 inner product and norm with respect to
3

---

Published as a conference paper at ICLR 2026
μ. We write (as)ez to denote an ordered sequence with index set I, and we write only (a,) when the index set clear from context.
3.1 KERNEL REGRESSION AND KERNEL EIGENSYSTEMS
KRR is learning rule specified by a positive-semidefing "kernel function" K IRd R - R and a ridge parameter ò 2 0. Given dataset (X' yy) KRR returns the predicted function
f(x:) x Xxx xx 8In) y,
(I)
where the vector [kax]; = K (æ, æ;) and matrix [Kxx]e = K (æ; x;) contain evaluations of the kernel function. In this paper, will restrict our attention to two special classes of kernel:
Definition (Rotation invvariant kernel), A kernel function is rotation-invarant if it takes the form (xx, x') ) = K [[| |x'1. TTxx)
iittriionnivvrantt because K (Ux, Ux') K(x, x²) for any orthonor- mal matrix U. Many widely- kemnlls are rotation rotation-invariant, including the Gaussian kernel
Such kernel K is called
K(x,, x²) = e z=z --- the Laplace kernel (æx x') e >| and the Neural Network Gaussian Process (NNGP) kernels and NTKs of infinite- MLPs. We will be particularly interested in a subset rotation-invare kernels which discard the explicit radial dependence:
Definition 2 (Dot-product kernel). A kernel function is dot-product kernel if it takes the form K K(x,, x²) = K K(x x²).
For dot-producc kernel to be positive-semidefnnie on all domains, must admit a Taylor series ((x:" x²) Er20 of (a: x² with nonnegative level coefficients ca 2 0 (Schoenberg, 1942). We will find it useful to describe dot-product kernels in terms of their level coefficients (c=)<20-
We would like to study arbitrary rotation-invariant kernels, but is easier to study dot-product kernels, which admit the above series expansion. Fortunately, a rotation invariant kernel is dot product kernel when the domain is restricted to a sphere, and if we know that our data has typical norm r, we kernel the dot-product kernel which matches rād-1;
rotation-invariant
may approximate the
Definition 3 (On-sphere level coefficients). The on-sphere level coefficients a rotation-invariant kernel K at a radius r are the nonnegative sequence coeffs K, r) == (ct)e20 such that
K K(x, xx)x'')
( x²)²
for all x, x' such that | | =
(2)
a!
E20
We give the on-sphere level coefficients for various kernels in Appendix B.
An eigenfunction of kernel K with respect to measure μ is function & such that Em'=pl K (xx x' (e))(())) = Xx((x) for some À 2 O. By Mercer's Theorem (Mohri et al., 2018, Theorem 6.2), any compact kernel admits complete basis of orthonormal eigenfunctions with (ó., Φ;)μ = ōij and may be spectrally decomposed as K(x, æ²) = Σ, (x) We will write eigensystem(1, u4, K) (Ax, ot) to denote the sequence of all eigenpairs, indexed in decreas- ing eigenvalue order (A; 2 >i+1) unless otherwise specified. It will prove useful to decompose the target function in the kernel eigenbasis as fx) Σ, (x),,,) where (v:) are eigencoefficients.
3.2 HERMITE POLYNOMIALS AS A NATURAL BASIS FOR GAUSSIAN DATA
Throughout, we write (he))20 for the normalized probabilist's Hermite polynomials. These are the orthogonal polynomials for the standard Gaussian measure, satisfying (x (x)] =
ppm. The first few such polynomials are ha (x) = h (x)= h2(2) +/22222( (x - -1). See Appendix A
for review of Hermite polynomials.
"Here is an intuitive description of kernel eigensystem which shown visually in Figure Any kernel function K may be viewed as an inner product in high-dimensional feature space: K K(x, x') = (vb(x), vb(x") Consider mapping the datasct into this high-dimensiona, space and then computing the principal components of Σg = E., (x))bb (æ)) EA= Each eigenvalue X; is kemel eigenvalue. The corresponding eigenfunction is projection onto the i-th principal direction: (xx))) 1/2b)( E.).
4

---

Published as a conference paper at ICLR 2026
We can these ID Hermite polynomials to construct orthonormal basis for multivariate Gaussian measure I ~ (O Σ) with positive-definite covariance Σ 0. First we diagonalize
the covariance Σ UTU with orthogonal matrix U [un uu and diagonal matrix diag (?,...,, --)) Then for any multi-index a E Nj. we define
ual
II No, (2.),
where
2 z-r-1/2
In Equation (3), the elements of a specify the order of the Hermite polynomial along each principal direction of data covariance. These multidimensional Hermite polynomials are orthonormal, satis- fying (m ha ( (x) (x)) òaxe. In the next section, assert that this naive guess of basis is in fact often close to the true basis of kernel eigenfunctions for synthetic and real datasets.
THE HERMITE EIGENSTRUCTURE ANSATZ: THEORY AND EXPERIMENT
Prior work has shown that predicting kernel regression learning curves boils down to understanding the kernel eigensystem. With this as motivation, we are ready to introduce our primary mathematical object: explicit functional form for the kernel eigensystem, suitable for rotation rotation-invariant kernels and high- nigh-dimenssioal datasets.
Plan of attack. First will write down this explicit functional form (Definition 4). Then will state our assertion that this functional form approximates the true kernel eigensystem (HEA). Next, will demonstrate that the HEA holds to excellent approximation for several rotation-invariant kernels on several real image datasets (Figure 2). We will then give an intuitive justification for the HEA and give two formal theorems which state that the HEA holds for Gaussian data kernel width grows (Theorems and 2). Next, we will characterize the factors that make the HEA work better or worse (Section 4.2). Finally, we will use the HEA to predict KRR learning curves in Section 5. We begin by explicitly defining our Hermite eigensystem:
Definition (Hermite cigensystem). Given a data covariance matrix Σ = UTU and a sequence of level coefficients (ce), define the (Σ, (cz)) Hermite eigensystem be the set of (scalar, function) pairs
HE (ct)) = {(aa Φa) for all a E Ng)
(4)
where for each multi-index a the proposed eigenvalue and eigenfunction are constructed as
>a = qal
Ih and da = (E)
(5)
1=1
where aa| = E a and ( is the multivariate Hermite polynomial given in Equation (3).
The (E, (ct)) eigensystem is set of Hermite polynomials da and associated positive scalars Aς. one for each multi-index a E No. The eigenvalues (Aa) are monomials the data covariance eigenvalues (7x), rescaled by the appropriate level coefficient Gja)- We now present the Hermite eigenstructure ansatz, which asserts that this set of (scalar, function) pairs is in fact a close match to the true kernel eigensystem.
Let K be a votation-invariin kernel and let μ be measure over Rd with zero mean. Then let:
be the data covariance matrix, xx Eg
r be the root-mean-squared data norm, and
(ce) Koeffs(K,r) be the level coefficients of K restricted the sphere rgd-1
The Hermite eigenstructure ansatz asserts that
eigensystem(j. K) R (E())())))
(HEA)
That is, the true kernel eigensystem approximately equal to the (E, ((e)))HHrmiitt eigensystem given in Definition 4.
5

---

Published as a conference paper at ICLR 2026
Gaussian kernel Gaussian data
Gaussian kernel
Laplace kemnel SVHN
ReLU NTK @ Imagenet32
@ CIFAR-10
137
107
thenry is empitics
Predkcad Pickkaal
eigarabe
1013
10"1
1071
kernel
guddiaic mode
mode
10th
Empiriai cigenvalae A(100)
Empiriall rigenvalue A A(reg)
Eupirial cigenvalec A (eespt
Enpirial eigeovalue A (194)
(grouped in specteal bios)
theney vs empirics
koree sigenbasis
Produces eigenigios
Preducedd eigcnsguoc
Predicud cigangiac
Proficoa eiganegiaa
Ergpincall diganepax:
Frpiiiiall cigesspaax:
Enginial digeraquas
Empiriad rigersqusz
Figure 2: The Hermite eigenstructure ansatz (HEA) accurately predicts the eigenvalues (top) and eigenfunctions (bottom) of various kernel/dataset combinations. For four kernel/dataset
settings (columns), we compute the empirical kernel eigensystem {(X(omp) .0 (:(cup))) and compare to the theoretical eigenpairs {(A, (th))) o; ((h))) obtained from Definition and indexed in order of
decreasing ((th)_ In the top plot in each column, the i-th point from the top right has coordinates
(A (emp) xxth)) and its color indicates the polynomial degree of di (th) In the bottom plot in each column, we bin both the predicted and empirical eigenfunctions into logarithmic spectral bins and visualize the pairwise subspace overlap (Equation (44)), with axes matching the top plot. Grey pixels indicate bins with no eigenvalues. In all plots, concentration along the diagonal indicates mheory-experrmenn
match. See Appendix D.2 for further explanation and experimental details.
The HEA is strong claim: it asserts that the kernel eigensystem, to good approximation, has simple analytical form which depends only on the second-order statistics of μ. and no higher moments and that the kernel eigenfunctions are multivariate Hermite polynomials independent of the kernel chosen (so long as it is rotation -nnvariaan).....
Rather than provable fact, the HEA should be treated as a falsifiable claim that may hold well or poorly in any given setting. In practice, with rotation invirraan kernels and nigh-dimensional image datasets, we will find that often holds quite well. Figure examines four such settings, finding that in each, both the kernel spectrum and eigenfunctions are well-predicted by the HEA.
Before moving on, we make note about the meaning of the symbol "z" in the HEA. Equality would mean that the i-th largest eigenvalues of the true eigensystem (u, K) and the synthetic Hermite eigensystem HE (,, (cx)) are equal, and the corresponding eigenfunctions are also equal (up to eigenspace degeneracy). Intuitively, approximate agreement means that the eigenvalues approximately match, and the i-th eigenfunction from one set has significant overlap only with eigenfunctions from the other set with eigenvalues close to A₃ This fuzzier notion of alignment is enough ensure that learning curves computed using the two eigensystems are a good match, which the practical outcome of interest. It is this notion of eigenspace alignment that test for empirically in Figure 2.
4.1 THE HEA FOR GAUSSIAN DATA: SOME INTUITION AND TWO THEOREMS
When might we expect the HEA to hold? To gain the central intuition, it is sufficient to consider simple case of univariate Gaussian data μ (0, and the Gaussian kernel K, (x,
e 2202 (a (x==")) This kernel admits the feature map K2 (x, = (4b, (I), tb (x')) where
45 (x) = 2ot
(6)
0
2202
Veloo

---

Published as a conference paper at ICLR 2026
We would like to find the directions of principal covariance of 1/ (z)). Let suppose that o² > y: the kernel width dominates the width of the data distribution. Examining Equation (6), we can make two observations. First, the exponential prefactor will be close to one, and may approximate t. componentwise as [sbo
z² This amounts to approximating our kernel as Ko (x, x') =
Vilo?
Ee (zan") that is, as dot-product kernel with coefficients et a- 24 Second, each component of 2 will dominate all subsequent components:
Ex I (x) o of
Ez [ (x))211
((1+1)
Since the first element of 2bo is by far the largest (and since we do not center th, before computing eigendirections), the first direction of principal variation will correspond to Φr(x) = 1, with variance An Rs 1.3 The next direction will correspond to Φ1 (I) ~ -1//2x with variance A o -2. The next eigenfunction must incorporate the x² direction, but we have problem: x² is not orthogonal to Φo(x)) = I. We must therefore orthogonalize it with respect to do against our measure μ in the usual Gram- -Shhmid fashion. This yields (2 s 1/2
(1 x² 1), which using standard formulas
for Gaussian integrals gives an eigenvalue
2 = /K(e,, xzz ( )dp(x)du(a")) R No 2,2
(8)
Continuing this process to higher orders, we find that the kernel eigensystem matches that predicted by the HEA: Φe is the E-th orthogonal polynomial with respect to our Gaussian measure that is, the Hermite polynomial he he(y-1/22)) and the ê-th eigenvalue is X R a a-2ig = cnn The corrections hidden by every "x" in this derivation are relative size O -2)) and thus vanish as a grows." 4
This same analysis holds for any dot-product kernel K(x, x²) = Ee ž (x:x') with level coefficients (ce) such that 2++12 < 1. It can, with some difficulty, be further extended to apply to multivariate Gaussian data oe
(0 E). But what if the kernel is not dot-product kernel, such as the Laplace kernel K(x,, x²) e iæ=a'll? Unlike the Gaussian kernel, the Laplace kernel is not well- approximated by a dot-product kernel even at large width because of its nonanalyticity at zero. However, like all rotation-invarian kernels, the Laplace kernel is dot-product kernel when restricted to a sphere (and will close to a dot-product kernel when restricted to a spherical shell whose thickness is not too big). In such a case, we will require the data to be high-dimensional: for data
IT 2
with a high effective dimension der == Th و
>> 1, samples will tend to concentrate in norm. We
may thus safely approximate any rotation Intatio--ivvariane invariant K as a dot-product kernel.
Having given intuitive derivation of the HEA for Gaussian data, we now move to formal statements. Our first theorem states that the HEA holds for the Gaussian kereel at large width.
Theorem (The HEA holds for wide Gaussian kernel on a Gaussian measure).
Let μ (N Σ) be multivariate Gaussian measure and let K, x²) 2 11= x''"" be the Gaussian kernel with width a. Let Tr[E] and let (ct) = (oeffs(Ko.))) r). which yields
C -26
20. 207 Then:
as a - oC, eigensystem((s, K,) - HEEE, (c+)).
Proof sketch (full proof in Appendix 1). Mehler's formula can be used to express the Gaussian kernel's eigensystem exactly (Mehler, 1866). Taking + in the resulting expressions yields agreement with the HEA.
Our second theorem applies dot-product kernels with fast-decaying level coefficients.
We index cigenmodes from 0 instead here match the polynomial order t. "Were we to repeat this calculation with different measure μ for x, we would obtain the orthogonal polyno-
mials with respect y eigenfunctions. For example, if μ U[-1, 11, get the Legendre polynomials.
Foor Gaussian data (0, E), the relative variance of the norm is Var [|^=|]] /F [Ia= 1 2 /dd.. which falls to zero der grows.
7

---

Published as a conference paper at ICLR 2026
Theorem (The HEA holds for fast-decaying dot-produs kernel on Gaussian measure). Let (0, Σ) be multivariate Gaussian measure with variance E > 0 and let
(x x') E 2=
Ci x
be a dot-prod dot-product kernel with coefficients Oj 2 O such that c++1 S c. Ct for some e >> O. Then:
- 0, eigensystem( K(e)) HE (c+)) linearty
Proof sketch: Our proof formalizes the intuitive We use perturbation theory to show that the kernel eigenstructure splits into saaeenniilll--sparrattt segments, with the b-th segment eigenstructure determined almost fully by the ê-th order term of (cc)) Due to the complexity of the proof, we break it up into stages: we rigorously state and prove the one-dimensional case in Appendix then state and prove the general case Appendix K.
derivation of the HEA given above.
What are the meanings of the "wide kernel" and "fast decay" limits in Theorems and 2? Instead of taking a wider (or faster-decaying) kernel on fixed data, one might equivalently fix the kernel and scale down the data + with + O, and these theorems will still hold. These are thus the limits in which the effective length scale of the kernel dominates that of the data.
An astute observer might note that in the limits taken in Theorems and 2, the kernel converges to a constant: K (xx, x²) x 1. Are these theorems then trivial? No: even though the zeroth- eigenvalue dominates all subsequent eigenvalues, the relative size of these smaller eigenvalues is nontrivial (and determines the inductive bias of KRR so long as one has n > 1 samples). These theorems state that, in these limits, the HEA gives the relative sizes of all eigenvalues, the constant mode and all subsequent smaller eigenvalues.
4.2 CONDITIONS SUCCESS: FAST DECAY OF ce, HIGH DATA DIMENSION, AND "GAUSSIAN ENOUGH" DATA DISTRIBUTION
The intuitive theory above suggests three conditions required for the HEA to hold reasonably well. Here we list these conditions and give empirical confirmation that breaking any one usually causes the HEA to fail.
Fast decay of level coefficients. As discussed in Section 4.1, need c > 71+++ for the Gram-Schmice process underlying the HEA to work. In Figure 13, we show that as we decrease the Gaussian kernel's width (and thus increase C6+1 on fixed dataset, the HEA eventually breaks.
2) High data dimension (for some kernels). As previously discussed, concentration of norm (via invariant kernel as a dot-produee
high den) is required if we are to approximate an arbitrary kernel. Figure 14, we show that for the Laplace kernel and ReLU NTK, agreement with the HEA worsens as den decreases. However, since the Gaussian kernel is smooth at æ x:', it does not require concentration of norm, and low deff is fine (Figure 15).
3) "Gaussian enough" data distribution. Common image datasets complex enough roughly satisfy simple tests of Gaussianity, such as coordinatewise Gaussian marginals. As we make the dataset simpler (CIFAR - SVHN + MNIST tabular), these marginals become less Gaussian, and HEA agreement degrades (Figures 16 and 17). is noteworthy that our theory empirically works better more complex datasety thanks the blessings of dimensionality.
THE HEA ALLOWS PREDICTION OF KRR LEARNING CURVES
Under the conditions outlined in the previous section, expect the HEA accurately predict kemel eigenstructure. We aim to plug these results directly into the aforementioned KRR eigenframework (of e.g. Simon et al. (2021)) predict the final test risk of KRR. However, key challenge remains: using the eigenframework requires knowing the coefficients of the target function in the kernel
TTii is essentially the physicist's duality hetween "scaling down your system" and "scaling up your measuring stick."
8

---

Published as a conference paper at ICLR 2026
Gaussian kernel @ CIFAR-5m
Predicted sample complexity
100
Laplace kemee @ ImageNet-32
213
1,5
210
2204
test MSE
2190
10
2100
1.0-
90
21
2g F1 Prg
0.5
216
10²
lincar
quadratic
26
cubic quartic
21
F1
0.0
10'
10a
10a
10
10
r. training samples
Empirical sample complexity
1.25
Gaussian kernel @ SVHN
1.25
Luplace kemel @ CIFAR-5m
1.25
Shallow ReLU NTK
@ ImageNet-32
1.00
1.00
1.00
test MSE
0.75
Souree cxp. 18
even vs. odd
1.1
0.50
prime vs. composite
0.50
vs. all others
0.50
3 1.15
genus 0 vs. genus 2
cur vs. truck
1.25
0.25
vs. others
0.25
dog vs. frog
0.25
1.4
4 2
vehicles animals
1.6
0.00
0.00
10'
truining samples
73 training samples
n training sumples
Figure 3: Using only the empirical data covariance and a polynomial decomposition of the target function, we predict learning curves across variety of kernels, datasets, and targets. (Top row.) We predict test error on synthetic target functions of real datasets. Each target is the multi-Hermite polynomial (Equation (3)) whose leading term is indicated in the plots. (Recall that 2; u, x/ / are the rescaled PCA coordinates.) For each of these targets, our ansatz predicts both learning curves (top left) and the sample complexity required to achieve MSE I 0.5 (top right). (Bottom left and center.) We train on binarized true target functions. See Appendix D.1 for details. (Bottom right.) We construct synthetic targets by drawing from Gaussian process. The source exponent controls the difficulty of the target. See Appendix D.1 for details. For all learning curve predictions, we estimate the coefficients of the target function in the predicted eigenbasis using the Gram-Schmidt process described in Appendix D.3. See Appendix D.4 for full experimental details.
eigenbasis, f. (a) = E, (z)). We must measure these coefficients ny from finitely many samples of the target function.
Were the data perfectly Gaussian, the multi-Hermite polynomials would be an orthonormal basis with respect to the measure, We could then estimate the coefficients by simply taking inner products between the target vector and generated Hermite polynomials and expect the estimation error to decay as (NN1/22 with the total number of samples N. However, small amounts of non-Gaussianity in the data introduce cascading non-orthogonality in the Hermite basis. As result, the naive method overestimates the power in the overlapping modes. To rectify this effect, we modify our measurement technique by re-orthogonalizing the sampled Hermite polynomials via the Schnidt process:"
iterate over increasing i: h (GGS) unitnorm
h4
n (GS) h J<3
h (GS)
where h; : (2') is the 7th multi-Hermite polynomial evaluated on the samples. The (hx())); ordered by increasing degree; there is dependence on the level coefficients og and thus our measurement is kernel-independent We proceed to estimate the coefficients as é; (h(S)) y). As we show in Figure 3, with this single estimate of the target's 's near-Hermite orthonormal decomposition, can reliably predict learning curves variety of tasks and kernels.
We summarize in Appendix F the various assumptions and simplifications we have made in the derivation of our theory and our successful prediction of learning curves.
For a full discussion of this method, see Appendix D.3.
9

---

One consequence of our theory is that there exists a canonical learning order in which KRR learns Hermite polynomials as sample size increases: each polynomial's learning priority is given by its associated HEA eigenvalue. Here, we check whether this order also predicts the training time learning order of feature-learning MLPs (Yang & Hu, 2021). We train MLPs online on multi-Hermite polynomial target functions of Gaussian data and CIFAR-5m and count the number of steps Tiuer required to reach online loss MSE & 0.1. We find that the effective optimization time 1) Ther 18 well predicted by the HEA eigenvalue (Figure 4). Published as a conference paper at ICLR 2026
MLPs LEARN HERMITE POLYNOMIALS IN THE ORDER PREDICTED BY THE HEA
MLP @ Gaussian Data
MLP @ CIFAR-5m
Elf. opt. time Higer
10a
10a
240
lincar
10a
21
quadratic
10
1/2
cubic
1/2
quartic
10
10a
10
10
10
10a
10
Inverse HEA eigenvalue Aa
Figure 4: The HEA accurately predicts polynomial learning order in MLPs in the feature- learning regime. We measure the amount of time it takes to train three-layer ReLU MLPs, each dot being a trained MLP on one multi-Hermitee polynomial target once a test error of MSE S 0.1 reached. We find that the optimization time is well well-predicted by the inverse square root of the HEA eigenvalue Ao 1/2
Details of our exact MLP setup experiments can be found in Appendix G, detailing validation of the feature-learning regime, insight into hyperparameter choices, and model performance when taken into the NTK/lazy and ultra-rich regimes.
7 DISCUSSION
We have presented theoretical framework which describes how KRR "sees" complex natural datasets: namely, as a hearly-Gaussian measure with Hermite eigenstructure as per Definition 4. This a proof of concept that end-to-end theories of learning mapping dataset structure all the way to model performance
are possible for a nontrivial learning algorithm on real datasets. Theories of this sort applicable to more general algorithms may be a good end goal for learning theory.
AUTHOR CONTRIBUTIONS
DK led the scientific development of the KRR empirics from early exploration through final experi- ments, wrote most of the codebase, and together with JT wrote the empirical sections of the main text. JT developed the MLP empiries and determined the conditions under which the HEA holds for KRR. YL provided formal statements of Theorems 1 and 2 and developed the proofs appearing in Appendices to K. JS guessed the HEA idea, developed preliminary empirics and the conjectures that became our theorems, wrote most of the main text, and led the team logistically.
ACKNOWLEDGMENTS
The authors thank Boris Hanin for giving us an introductory schooling in Hermite polynomials. We are grateful to Berkan Ottlkk for many clarifying discussions and detailed comments on the manuscript, Anthony Thomas for comments on the manuscript, and Evan Ellis for useful comments on the introduction. DK thanks the many friendly faces at Imbue for welcoming us, especially Evan Ellis for interesting conversations, Matthew Schallenkamp for useful tips, and Bowei Liu for being our GPU genie. JT thanks Kanjun Qiu and Josh Albrecht for supporting this research financially. YL acknowledges GPT-5 for multiple wrong attempts at proofs which gave salutary motivation to produce correct proofs, if only to prove someone on the internet wrong. JS thanks Parthe Pandit, Margalit Glasgow, and Jonathan Shi for useful early feedback and Josh Albrecht and Kanjun Qiu
10

---

Published as a conference paper at ICLR 2026
for encouragement, guidance and support during the development of this work and the process of learning to lead. JS additionally thanks the residents of Fort Jones, CA for providing peaceful and welcoming environment for a November 2024 stay in which the ideas developed in this paper took form.
This work principally funded by Imbue under the Feature Lab (FLAB) initiative. This work was supported in part by the U.S. Army Research Laboratory and the U.S. Army Research Office under Contract No. 1911NF-20-1-0151 awarded to Michael R. DeWeese. YL was supported by gift to the Center for Human-Conpatible Al at Berkeley from Coefficient Giving (formerly Open Philanthropy) during the development of this work.
STATEMENT ON THE USE OF LARGE LANGUAGE MODELS
We used large language models (LLMs) for analytical computations, writing code, detailed literature search on narrow topics, and the Taylor expansions of Laplace and ReLU kernels appearing in Appendix We found that LLMs performed certain tasks faster than us but with propensity for miscommunication or overconfidence, especially when fashioning proofs, so we sought or performed independent verification of everything useful we got from an LLM.

---

Published as a conference paper at ICLR 2026
REFERENCES
Alexander Atanasov, Alexandru Meterez, James B Simon, and Cengiz Pehlevan. The optimization landscape of sgd across the feature learning strength. arXiv preprint TrXiv:2410.046422 2024. Cited on page 36.
Francis Bach. High-dimensional analysis of double descent for linear regression with random projections. arXiv preprint arXiv:2303.013: 0113722, 2023. Cited on page 21.
Alberto Bietti, Joan Bruna, Clayton Sanford, and Min Jae Song. Learning single-index models with shallow neural networks. Advances in neural information processing systems, 35:9768-9999 978888997788888 2022. Cited on page 3.
Blake Bordelon and Cengiz. Pehlevan. Learning curves for sgd on structured features. arXiv preprint arXiv:2106.02713 2021. Cited on page 3.
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. Cited pages 3, and 21.
Francesco Cagnetta and Matthieu Wyart. Towards theory of how the structure of language is acquired by deep neural networks. Advances in Neural Information Processing Systems, 37: 83119-83166 83163, 2024. Cited on page 3.
Francesco Cagnetta, Leonardo Petrini, Umberto M Tomasini, Alessandro Favero, and Matthieu Wyart. How deep neural networks learn compositional data: The random hierarchy model. Physical Review X. 14(3):031011, 2024. Cited on page 3.
Abdulkadir Canatar, Blake Bordelon, and Cengiz Pehlevan. Spectral bias and task-model align- ment explain generalization in kernel regression and infinitely wide neural networks. Nature communications, 12(1):1-12, 2021. Cited on page 21.
Andrea Caponnetto and Ernesto De Vito. Optimal rates for the regularized least-squares algorithm. Foundations of Computational Mathematics, 7(3):331-368, 2007. Cited on page 21.
Yang Chen and Nigel Lawrence. Small eigenvalues of large hankel matrices. Journal of Physics A: Mathematical and General, 32(42))7305, 1999. Cited on page 51.
Chen Cheng and Andrea Montanari. Dimension free ridge regression. arXiv preprint arXiv:2210.08571, 2022. Cited page 21.
Lenaic Chizat, Edouard Oyallon, and Francis Bach. On lazy training in differentiable programming. Advances in Neural Information Processing Systems, 32, 2019. Cited on page 3.
Yatin Dandi, Florent Krzakala, Bruno Loureiro, Luca Pesce, and Ludovic Stephan. How two-layer neural networks learn, one (giant) step at a time. arXiv preprint 1rX1::2305..8270, 2023. Cited on page 3.
Chandler Davis and William Morton Kahan. The rotation of eigenvectors by perturbation. iii. SIAM Journal on Numerical Analysis, 7(1):1-46, 1970. Cited on pages 50 and 60.
J. Deng, W. Dong, R. Socher, L.-J. Li, K. Li, and L. Fei-Fei. ImageNet: A Large-Scale Hicrarchical Image Database. In CVPRO9, 2009. Cited page 22.
Edgar Dobriban and Stefan Wager. High-dimensional asymptotics of predictions: Ridge regression and classification. The Annals of Statistics, 46(1):247-279, 2018. Cited on page 21.
Simon Du, Jason Lee, Haochuan Li, Liwei Wang, and Xiyu Zhai. Gradient descent finds global minima of deep neural networks. In International Conference on Machine Learning, pp. 1675-1685.
PMLR, 2019. Cited on page 3.
Dheeru Dua and Casey Graff. UCI machine learning repository, 2017. URL Cited on pages 22 and 31.
Rishabh Dudeja and Daniel Hsu. Learning single-index models in gaussian space. In Conference On Learning Theory, pp. 1887-1930. PMLR, 2018. Cited on page 3.
12

---

Published as a conference paper at ICLR 2026
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. Cited
page 3.
Sebastian Goldt, Mare Mézard, Florent Krzakala, and Lenka Zdeborová. Modeling the influence of data structure on learning in neural networks: The hidden manifold model. Physical Review X, 10 (4):041044, 2020. Cited on page 3.
Trevor Hastie, Andrea Montanari, Saharon Rosset, and Ryan J Tibshirani. Surprises in high- dimensional ridgeless least squares interpolation. The Annals of Statistics, 50(2):49-986, 2022. Cited on page 21.
Arthur Jacot, Clément Hongler, and Franck Gabriel. Neural tangent kernel: Convergence and gener- alization in neural networks. In Advances in Neural Information Processing Systems (NeurIPS), 2018. Cited on page 3.
Arthur Jacot, Berfin Şimşek, Francesco Spadaro, Clément Hongler, and Franck Gabriel. Kernel alignment risk estimator: Risk prediction from training data. Advances in neural information processing systems, 15575588-15578, 2020. Cited on pages 2, 3, and 21.
Stefan Kaczmarz. Angenaherte auflosung von systemen linearer glei-chungen. Bull. Int. Acad. Pol. Sic. Let., Cl. Sci. Math. Nat., pp. 355-357, 1937. Cited on page 25.
Tosio Kato. Variation of discrete spectra. Communications in Mathematical Physics, 111(3):501-504, 1987. Cited on page 66.
Yann LeCun, Corinna Cortes, and Christopher J. C. Burges. The MNIST database of handwritten digits. 1998. Dataset. Cited on page 22.
Jachoon Lee, Yasaman Bahri, Roman Novak, Samuel Schoenholz, Jeffrey Pennington, and Jascha Sohl-Dickstein. Deep neural networks as gaussian processes. In International Conference on Learning Representations (ICLR), 2018. Cited on page
Jason D Lee, Kazusato Oko, Taiji Suzuki, and Denny Wu. Neural network learns low-dimensional polynomials with sgd near the information-theoreiie limit. Advances in Neural Information Processing Systems, 77:58716-58747 2024. Cited on page 3.
Bruno Loureiro, Cedric Gerbelot, Hugo Cui, Sebastian Goldt, Florent Krzakala, Marc Mezard, and Lenka Zdeborová. Learning curves of generic features maps for realistic datasets with teacher-student model. Advances in Neural Information Processing Systems, 34:18137-18151, 2021. Cited page 21.
F. Gustav Mehler. Ueber die entwicklung einer function beliebig vielen variablen nach laplaceschen functionen höherer ordnung. Journal für die reine und angewandte Mathemalik, 66: 161-176, 1866. Cited on pages and 44.
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. Cited on page 3.
Mehryar Mohri, Afshin Rostamizadeh, and Ameet Talwalkar. Foundations of Machine Learning. Adaptive Computation and Machine Learning. The MIT Press, Cambridge, Massachusetts, second edition edition, 2018. ISBN 278-0-262-03940-6 Cited on page
Alireza -oosavv,,, Denny Wu, and Murat A Erdogdu. Learning multi-index models with neural networks via mean-field langevin dynamics. arXiv preprint arXiv:2408.07254 2024. Cited on page 3.
Preetum Nakkiran, Behnam Neyshabur, and Hanic Sedghi. The deep bootstrap framework: Good online learners are good offline generalizers. arXiv preprint arXiv:2010.08127, 2020. Cited on page 22.
Radford M Neal. Priors for infinite networks. In Bayesian Learning for Neural Networks, pp. 29-53. Springer, 1996. Cited on page 3.
13

---

Published as a conference paper at ICLR 2026
Yuval Netzer, Tao Wang. Adam Coates, Alessandro Bissacco, Baolin Wu, and Andrew Y. Ng. Reading digits in natural images with unsupervised feature learning. In NIPS Workshop on Deep Learning and Unsupervised Feature Learning. pp. 2011. Workshop paper. Cited page 22.
Maria Refinetti, Alessandro Ingrosso, and Sebastian Goldt. Neural networks trained with sgd learn distributions of increasing complexity. In International Conference on Machine Learning, pp. 18843-28866 PMLR, 2023. Cited on page 3.
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. Cited page 21.
J. Schoenberg. Positive definite functions on spheres. Duke Mathematical Journal, 9(1):9 - 108, URL Cited on page 4.
1942. doi: 04-111//000127004-----0000000
Antonio Sclocchi, Alessandro Favero, and Matthieu Wyart. A phase transition in diffusion models reveals the hierarchical nature of data. Proceedings of the National Academy of Sciences, 122(1):
c2408799122 121, 2025. Cited on page 3.
James B Simon, Madeline Dickens, Dhruva Karkada, and Michael R DeWeese. The eigenlearning framework: A conservation law perspective on kernel ridge regression and wide neural networks. arXiv preprint /0.09221 2021. Cited on pages 3, 8, and 21.
Peter Sollich. Gaussian process regression with mismatched models. In Advances in Neural Information Processing Systems, pp. 519-526 MIT Press, 2001. Cited on pages 2, 3, and 21.
Terence Tao. Topics in Random Matrix Theory, volume 132 of Graduate Studies in Mathematics. American Mathematical Society, Providence, RI, 2012. ISBN 978-0-8218-7430-1 Cited on page 49.
Gerald Teschl. Mathematical Methods in Quantum Mechanics: With Applications to Schrödinger Operators. Number Vol. 99 in Graduate Studies in Mathematics. American mathematical society, Providence, R.I, 2009. ISBN 978-0-8218-4660-5. Cited on page 49.
Alexander Wei, Wei Hu, and Jacob Steinhardt. More than toy: Random matrix models predict how real-world neural representations generalize. In International Conference on Machine Learning, Proceedings of Machine Learning Research, 2022. Cited page 21.
Arie Wortsman and Bruno Loureiro. Kernel ridge regression under power-law data: spectrum and generalization. arXiv preprint arXiv:2510.04780 2025. Cited on pages 3 and 35.
Denny Wu and Xu. On the optimal weighted & regularization in overparameterized linear regression. Advances in Neural Information Processing Systems, 13:10112-10122 2020. Cited on page 21.
Greg Yang and Edward Hu. Tensor programs iv: Feature learning in infinite-width neural networks. In International Conference on Machine Learning, pp. 11727-11737. PMLR, 2021. Cited on page 10.
Greg Yang, James B Simon, and Jeremy Bernstein. A spectral condition for feature learning. arXiv preprint arXiv:2310. /78/3, 2023. Cited on page 36.
Huaiyu Zhu, Christopher K. I. Williams, Richard Rohwer, and Michal Morciniec. Gaussian regression and optimal finite dimensional linear models. Technical Report NCRG/97/011, Neural Computing Research Group, Aston University, Birmingham, UK, 1997. URL. Cited on pages 3 and 44.
14

---

Published as a conference paper at ICLR 2026
A REVIEW OF HERMITE POLYNOMIALS
Our ansatz for kernel cigenstructure is constructed from Hermite polynomials, and we use several key properties throughout the paper. In this appendix, we give brief review of Hermite polynomials.
Let us write He; for the probabilist's 's Hermite polynomials. 8 These are the unique set of polynomials satisfying the following properties:
Degree. Hеy a polynomial of degree f.
Monic. The leading coefficient is 1, Her(x) of +... (in particular Heo()) 1). (iii) Orthogonality w.r.t (0, 1). For & + m, it holds that 12- (H) [x)] 0.
The probabilist's Hermite polynomials have squared norm (=- [=)] é!. Since we will use the Hermite polynomials as a basis in which to express other functions, we will prefer them to have unit norm, so we use the normalized probabilist's Hermite polynomials ho (x) == Her(().
which satisfy E (a) (x)]] = ōge. The first several such polynomials are given by
No (z)= = 1, h1 (x:) 2,
ha2 h2(x)) = V2 (x² - 1),
ha(rr) /6
(x3 3x));
hz(x) = /24
(x 6x²² + 3),
1
h5(2)
(I5
10x + 15x))
VI20
The Hermite polynomials obey remarkable number of useful mathematical relations. In particular, single- and multidimensional integrals of Hermite polynomials against exponentials and other poly- nomials are often computable in closed form. The Wikipedia page (https: /en wi wikipedia, org/wik //wwkk k /Hermite, tomite_ppot polyy onomi al s) is a good first reference. Here we state one such integral which is useful for understanding the intuitive derivation of the HEA in Section 4.1:
m!
m > and m = (mod 2),
(o.. xJ]
Vel 2 0/2 ((m 2)/2)!
(10)
otherwise.
That is, the 8-th Hermite polynomial is orthogonal to all monomials x.th whose order is less than l (or whose order is simply of different parity from f). In particular, this implies that Egr (x²) [=0]==0] when m < E: the function hę lies in the nullspace of the rank-one kernel term ((x,x') = (m
For future reference, also note the multiplication and differentiation formulas:
min(m.x)
He, Hem =
Σ
m
n
j!He j!Hen+m-22
(11)
1=0
He,, nHen-1
(12)
'Some references use physicist's 's Hermite polynomials Hy. These are related the probabilist's Hermites by He, by Hz(z) He//Heee//22 When using Hermite polynomials, he sure you know which ones you't 're talking about!
15

---

Published as a conference paper at ICLR 2026
B ON-SPHERE LEVEL COEFFICIENTS FOR COMMON ROTATION-INVARINT KERNELS
In this appendix, tabulate the on-sphere level coefficients for various kernels. We also this appendix as the place where we recall the functional forms of the ReLU NNGP kernel and NTK.
We begin by recalling Definition 3.
Definition 3 (On-sphere level coefficients). The on-sphere level coefficients a rotation-invariant kernel K at radius O are the nonnegative sequence coeffs(K, K, r) (ct) such that
(xx, x!) =
Ci x
x²)
for all æ; x' such that |ar| = | =
(13)
e!
220
B. GAUSSIAN KERNEL
For the Gaussian kernel K (x, x²) = 202 1-====/ m01" the level coefficients (ct) = (oeffs(Kr)) may be found by noting that, when |a:|| = |ad|| = r, then
K = 22
=c
Σ
2t ll (x T x')e.
(14)
Pattern meterninttcing Definition 3, we may then observe that
Cu 57
2 C1 0
C2
C 57 -f 28
B.2 EXPONENTIAL KERNEL
Let the exponential kernel be K (xc, x²) e We do not use this kernel in experiments or theory reported in this paper, but we nonetheless include it here because it is arguably the nicest kernel for the study of the HEA, and we used it extensively in our initial experiments. The blessing of the exponential kernel is that it admits the Taylor expansion
K (xx, x') ed Tn
(T.'). 7 Σ-
(15)
That is, the exponential kernel is exactly dot-product kernel with coefficients oe = - When and thus C for all E, this is in some sense the "platonic ideal" dot-product kernel (though since we must then take 7 << for the HEA to hold as per the intuition developed in Section 4. I). When the domain is restricted to a sphere, the Gaussian kernel and exponential kernel are equal up to global factor of
B.3 LAPLACE KERNEL
Here obtain the on-sphere level coefficients for the Laplace kernel K(x, x') - 10 I1 Let
a xr'
=:= V2r
1-
(16)
Since || x'1l //r vI on the sphere,
K K(x, x') exp( - 8/1 s).
(17)
"Note for users of our codebase: as defined in our repo, Laplace kernel actually K (x, x') 1 |e==']] |e]l that is, there is extra factor of V2. We later moved away from this convention, but it remains Vea
code.
16

---

Published as a conference paper at ICLR 2026
Closed form for on-sphere level coefficients. with exponential generating function
Let yn (z) denote the reverse Bessel polynomials,
1 Vv--(())
exp
(1
vI 2xt)) 2xz)).
(18)
8!
2x
820
Applying Equation (18) with and t o/2 gives
cxp(B(1 v1 - s)) Σ ye- ve-1(22) (3s/2)
(19)
$20
Multiplying by e and substituting implies
(x x') //r the definition K(x,x') Eiso (x x')
1
8
22r
ci
(20)
22
2/
The first few coefficients.
With the convention y-1 1, y0(x)) = 1, y1 (1 1 v2(2)
3 + 3x + x², ()(2) = 15+ + 15r + 6x + x², we obtain (for 3 = /2r/o)
-
B
22
2'
8 3
8
C2
+
1
4
8
0 0
J33
3,32
+
66
8
16
16
- 9
[81
3,83
5,32
5
C4
88
16
16
128
Large-f asymptotics. The dominant singularity of F(s) = e 8yT=s is at = 1, with F(s) = 1 1 3 O(1 - s). yielding [s*)
3 2-322 where the coefficient extraction operator
2/
[s))((s) returns the ê-th coefficient in the power series of F(s). Since a r - (s))ss,,
3
1 (o)+
B V2r σ
C3 2/T 28 63/2
(21)
Subtlety: fast-growing oe means diverging HEA eigenvalues
Here we encounter a subtlety with the Laplace kernel coefficients: Equation (21) states that Cr + oo superexponentially as grows. Recall that the largest eigenvalue in each level predicted by the HEA is À c. This superexponential growth means that for any value of 71 >> O, no matter how small, these largest levelwise eigenvalues will eventually begin to increase as grows and continue to grow without bound. A hacky fixed-point calculation using Stirling's formula suggests that the minimum occurs at min R y22111 See Figure for numerical illustration of this.
What do we make of this? From a theoretical standpoint, this is the result of the fact that since the Laplace kernel on the sphere rdd-1 has a singularity at æ '' = n2, our on-sphere dot-product kernel approximation to the Laplace kernel will diverge when attempting to evaluate K K(æ, xx) at points with larger radius |æ| > r. Since our theory designed to work with Gaussian data, and roughly half of Gaussian distribution will spill outside its sphere of average radius into this divergent region, the HEA predicts growing eigenvalues and infinite trace.
While this might seem spell the doom of the HEA insofar the Laplace kernel is concerned, experiments (e.g. Figures 2 and 3) attest that this is not the case. We find that we can still get good experimental agreement by (a) ensuring the data has high effective dimension so that Yi is small
Simply decreasing all eigenvalues does not help as that also decreases the sphere radius proportionally. which Equation (21) shows then increases each ea manner that compensates.
17

---

Published as a conference paper at ICLR 2026
10a1
Y1
0.03
HEA eigval Cy 11
71 0.1
10a1
Y/1 0.3
10
10
10-9
10P
10
level f
Figure 5: We compute the Laplace kernel on-sphere coefficients o with o = and plot ee for various Dashed lines show p²rr1 the value of the predicted minimum.
and then (b) truncating the HEA at finite order E, usually e E [5, 10). It seems plausible to us that this series approximation the Laplace kernel is essentially asymptotic expansion rather than true Taylor series, meaning that gives a good approximation when truncated to finite number of terms so long a particular parameter (here r-1 is small, but then later diverges, rather than giving better and better, and ultimately perfect, approximation as the number terms grows.
Essentially this same story also holds for the ReLU NNGP kernel and ReLU NTK, will not discuss it again.
B.4 THE RELU NNGP KERNEI.
For la- ReLU network with first-layer weight variance o and bias variance of (and no output bias), the first-layer preactivation kernel is
K (i o
ao + oî.
(22)
On the sphere ||
|a''l| r,
= K2 x) = ,2, + oh.
x
Ki Ki(x, x')
22r s
o
2
(K( x 1 (x',x")
(23)
The ReLU NNGP kernel is
K2(xxx')
o² 2x
(V1- arccos) p)
o2
11 (p).
(24)
2T
We stylor-expand K₂ in powers of T ' and write
K2(2, x') Σ
C az))
(25)
120
A change of variables gives the coefficients
22 C7
o2
H (()(a)
with
q = 22 + of
(26)
2T
where H(p) V1 2 (πt arccos p)p and ( denotes the f-th derivative.
18

---

Published as a conference paper at ICLR 2026
The first few coefficients follow from (aa V 1 a² + (π
arccos a) a,
(a) arccos
(a)a)= VI- a²
H (a) (1 - 02)3/21
2a² +1
(a) = (1 222)//2
yielding
0
V -
a² + (π arccosa)
2T
0
0 1c
C1
4
arccos a),
2T
4
0
02
9
(27)
2T
9
v1
a²
3
0
0
a
C3
4
2T
4
(1 22)3/22
0
2a +1
C1
2T
q
(1 22)5/2
Asymptoties. As l grows, the coefficient ct grows
Cr
2m
/3/2
oo.
(28)
B.5 THE RELU NTK
As in the previous subsection, treat shallow ReLU network. The ReLU NNGP kernel remains
22
o2
K2(x, x¹)
(VI- 0² + (π arccos p) =: (H)))..
(29)
2T
2T
The corresponding two-layer ReLU NTK is
O2(x, x²) = 02 Kí K1( x.)
2m ( arccos p)
K₂ K2 x') training second layer
(30)
training first layer
a²
q (V1 - 1² + 2p( -aa--arccoss- arccos pi) = 2n
a
q {(p).
(31)
2π
We Taylor-expand O₂ in powers of x T x and write
02(2,
Σ
Ct x Taye.
(32)
A change of variables gives the coefficients
02 C₁
(l)
with
ob
q=
+o
ob
(33)
2x q
q
where ((p) /1 0² 2p(
arccos p) and ( denotes the L-th derivative.
19

---

Published as a conference paper at ICLR 2026
The first few coefficients follow from the identities
J(a) v1 a² + 2a (π arccos a);
J'(a) -2(TT arccos +
v1 a²
3 - 2n. (a)
(1 aa223//2
a (5 - 2a²)
(a)
(1 -1-c8 a²))/2²
5 5 14a² 4a
(a)
(1 02)7/2
yielding
2
- a² + 2a (T arccosa)
Co
9
2m
w
9
0
2( arccos +
a
2m
9
vI
2
3 2a²
02
2m
0
(1 - 02)3/2
0
0u
3
a (5 - 20²)
2m
9
q
(1 02)5/21
2
0
5 14a² 4a
44
2m
9
(1 22)7/2
Asymptoties. As l grows, the coefficient Gp grows
C θ
0u
2
e!
l 8
(34)
2T
q
63/2
20

---

Published as a conference paper at ICLR 2026
C REVIEW OF THE KRR EIGENFRAMEWORE FOR PREDICTING TEST PERFORMANCE FROM TASK EIGENSTRUCTURE
The central piece of existing theory which we use in this paper is set of equations which give the average-case test MSE of KRR in terms of the task eigenstructure. In this appendix, we will review this KRR eigenfrramwwrk.
This eigenframework has been derived many times by different means in both the statistical physics community and the classical statistics community (which usually phrases the result applying to linear ridge regression). References studying KRR include Sollich (2001); Bordelon et al. (2020); Jacot et al. (2020); Simon al. (2021); Loureiro al. (2021): Wei al. (2022); references studying linear ridge regression include Caponnetto & De Vito (2007); Dobriban & Wagerr (2018); Wu & Xu (2020); Hastie al. (2022); Richards et al. (2021); Cheng & Montanari (2022). The result is essentially the same in all cases. Here we will adopt the terminology and notation of Simon et al. (2021).
Recall that we are studying KRR with a kernel function K with data sampled æ; ~ μ. targets generated as y/ fx;) + 7. and noise 1) ~ NN 2) with variance 2² 2 The kernel admits an cigendecomposition K x²) = E, ( with orthonormal eigenfunctions (ø:). Let us decompose the target function in the eigenbasis as (x) = Σ, v;cr( Suppose we run KRR with samples and ridge parameter 5 2 O. and we compute the population (i.e. test) and train MSEs as
MSE = Ewwn (f=(x)) - f(x))² + +
(35)
MSE Σ (yi - f(x:))
(36)
C.I STATEMENT OF THE EIGENFRAMEWORK We are now ready state the eigenframework.
Let K 2 0 be the unique nonnegative solution
A; + R
Σ
n.
(37)
A₁ +
Then test risk is given approximately by
MSE ~ En := EoB,
(38)
where the overfitting coefficient & is given by and the bias is given by
En
(39)
n E,
A
A
B
0/ + 0².
2
(40)
d + R
Train risk is given by
8
MSE, 8 Egr
E
(41)
n²x²
What meant by the "<=" in Equations (38) and (41)? This result only becomes exact in certain stringent cases; it is formally derived under an assumption that the eigenfunctions are independent Gaussian (or sub-Gaussian) variables when æ sampled from μ. and is exact only in an asymptotic limit in which and the number of eigenmodes in given eigenvalue range (or the number of duplicate copies of any given eigenmode) both grow large 2023). These conditions emphatically do not apply to any realistic instance of KRR. Nonetheless, numerical experiments find that Equations (38) and (41) hold with small error even at modest n (Canatar et al., 2021; Simon et al., 2021; Wei et al., 2022): though derived in an idcalized setting and exact only in a limit, this eigenframework holds reliably in practical cases.
proportional rate (Hastie et al., 2022: Bach,
In this paper, we use this eigenframework as tool to map predictions of task eigenstructure to predictions of learning curves. Since we are here using it in settings very similar to those tested by previous works (Bordelon et al., 2020; Jacot et al., 2020; Simon et al., 2021; Wei et al., 2022), expect to work well. Its use introduces some small error (as is not perfect at finite n)), but this is usually not the dominant source of error.
21

---

Published as a conference paper at ICLR 2026
D EXPERIMENTS CHECKING THE HEA: DETAILS AND FURTHER DISCUSSION
This appendix contains descriptions of the experimental stack used to verify the HEA, as well as discussion of practical considerations for applying the HEA to real datasets. It is organized as follows:
In Appendix D.1 we catalog the kernels, datasets, and target functions we use throughout our experiments.
In Appendix D.2 we explain the experiments that directly check whether the kernel eigen- structure matches the HEA prediction (Figure 2).
In Appendix D.3 we describe our method for estimating the decomposition of the target function in the Hermite eigenbasis. Unlike previous work, our method does not require constructing or diagonalizing an empirical kernel matrix.
In Appendix D.4 we detail the experimental setups for each of the learning curve and sample complexity plots (Figures and 3).
Finally, in Appendix D.5 we show the results of various additional experiments.
D.1 KERNELS, DATASETS, AND TARGET FUNCTIONS
Kernels. We use the Gaussian kernel, Laplace kernel, ReLU NNGP kernel, and ReLU NTK in our experiments. A detailed review of these kernels can be found in Appendix B."
Datasets. We use the following datasets for the main experiments:
Mean-zero anisotropic Gaussian data. This synthetic dataset is fully specified by its (diagonal) covariance. Different experiments set the data dimension and covariance decay rate differently; see experiment-specife details in Appendices D.2, E and G.
(Nakkiran et al., 2020). This dataset consists of more than 5 million samples of synthetic images akin CIFAR-I0. These images were sampled using deep generative model trained on CIFAR- 10. Though the distributions of CIFAR-S R-5m and CIFAR-10 10 may not be identical, they are typically considered close enough for research purposes.
CIFAR-5m
SVHN (Netzer al., 20.1). This dataset contains over 600,000 images of numerals, taken from house numbers found on Google Street View.
ImageNet-32 (Deng et al., 2009). This dataset contains downsampled ImageNet images (32 x 32 pixels).
MNIST (LeCun et al., 1998) and Mushroom dataset (Dua & Graff, 2017). We use MNIST and the UCI Mushroom tabular dataset in Appendix E examples of insufficiently Gaussian datasets.
We sometimes employ regularized ZCA whitening to increase the effective dimension of the data. This is data preprocessing technique parameterized by a ZCA strength wa which maps
11/2
X = USV + US WH + Ia)
V
(42)
where X E RdxN is the data matrix, USVT is its SVD, and we use the normalization notation A = A/(II A All//d d). As the ZCA strength 2 - O, we get no spectral transformation apart from a scalar normalization
+ USVT, Conversely, when w² - 20, we get full whitening X - UVT T The crossover point of this behavior occurs at w² 1. Note that although whiteeel Gaussian data are slightly less anisotropic, they are still distributed as a multivariate Gaussian.
We sometimes employ sample normalization, x x /|| Note that although the normalized data lie on the hypersphere, their distribution is still anisotropic.
Both sample normalization and ZCA whitening preprocessing techniques that, aggregate, shift high-dimensional data samples closer to the hypersphere. Since the HEA relies on an expansion
"A note for users of our codebase: in this paper. we define the Laplace kernel be (x, x') e- ||a=')
but because initially used different convention, in code it is K(æ,, x²) ov2 [aa'l| When we report kernel width in this paper, this is the width in the parameterization use in the paper, not in code.
22

---

Published as a conference paper at ICLR 2026
of kernel functions in terms of on-sphere coefficients (see Appendix B), these methods move any experimental setup closer to the regime well-described by the HEA. See Appendix E for further discussion of this point.
Targets, We use a variety of synthetic and real target functions in our experiments. All targets scalar; the synthetic targets take continuous values, whereas the real targets are binarized (y: (+1,-1}). All targets are mean-zero; for real targets, this means that the binary (super)classes are always balanced (even if the binary superclasses contain differing number of base classes).
We use the following targets for the main experiments:
(Synthetic.) Multi-Hermine targets. A single (normalized) multi- Hermite polynomials of the PCA components (Equation (3)).
(Synthetic.) Powerlaw targets. We draw random sample of the Gaussian process
P [.(x) - Σ c,li(()) + (white noise),
(43)
where (x) is shorthand for the th mulli-Hermite polynomial ha, (z) and c; is mean-zero Gaussian random variable with variance (i+6)-5 The so-called source exponent 3 satisfies 3 1 and controls the Sobolev smoothness of the target: the larger 3 is, the smoother and easier-to-leam the target. We choose a numerical truncation threshold P = 30, 000 for convenience, choosing the target noise level to ensure that the target is unit norm E [ys] Our results are empirically insensitive to the randomness in the target.
(Real.) class vs. class. A binarization in which samples are only drawn from two classes.
(Real.) class vs. all others. binarization similar single output element of practical neural networks with one-hot label encodings. A key difference here is that samples are drawn from each binary superclass in equal proportion so that [yy:]
(Real.) Domesticated vs. wild animals. CIFAR-5m binarization: [cat, dog, horse]
vs. [bird, deer, frog].
(Real.) Vehicles vs. animals. CIFAR-5m binarization: [plane, car, ship, truck] vs. [bird, cat, deer, dog, frog, horse]. Samples are drawn from each superclass in equal proportion so that E[ys] O.
(Real.) Even vs. odd. SVHN binarization based on parity: [0, 2, 4, 6, 8] vs. I1, 3, 5, 7, 9].
(Real.) Prime vs. composite. SVHN binarization based on primality: [2, 3, 5, 7] vs.
(4, 8, 9]. We leave out [0] and [1], numerals whose primality is undefined.
(Real.) Genus 0 vs. genus 2 1. SVHN binarization based the numeral's topological
genus: [1, 3, 5, 7] vs. [0, 6, 8, 9]. We leave out [2] and [4], numerals
whose topological genus is font-dependent.
D.2 DIRECT EIGENSTRUCTURE CHECKS
What is the appropriate way to numerically compare two eigensystems?
The spectra are easy to compare one can simply check whether 1Λ- small for i. An easy A visual check is to simply scatter one spectrum against the other on log-log plot; if the points remain close to the y line, then the spectra agree.
Comparing the eigenbases, on the other hand, a subtler matter. One must careful when the eigensystems have small eigenvalue gaps. This issue is most easily understood by considering the limit: what happens when comparing two diagonalizations of a degenerate matrix? In this case, numerical cigendecomposition is undefined since the true eigenvectors are not unique; the computed eigenvectors thus arbitrary. Simply comparing à; with Φ; for all i is therefore insufficient.
Clearly, any good eigenbasis comparison must be spectrum-avee aware. In particular, differences between eigenvectors belonging (near-) seere-)degeneraee subspaces should not be strongly penalized.
23

---

Published as a conference paper at ICLR 2026
A coarse but simple way to make this comparison is with spectral binning. We divide R into logaritmmicallyspacee bins; then, for each eigenbasis, we treat the modes whose eigenvalues fall within the same bin as a single near-degenerate eigenspace. Applying this procedure to the HEA" 12 yields set of disjoint Hermite eigenspaces ( {$( ( Jabine, and likewise for the empirical basis. Let d, dim (th)) and likewise for d!mp)) Note that in general we do not expect af to equal dy) for i * jü indeed, some bins may contain no modes at all. However, we do expect d; = d!mpp) for all i (if the theory is accurate).
Having handled any issues of spectral near-degeneracy, we may directly compare the two eigenbases by computing the pairwise overlaps between the binned eigenspaces:
(amp)
# 0 and d d(emp) # 0,
Overlap(i, =
(emp)
p
(44)
undefined,
otherwise.
where again S 5 nbins enumerate the bins.
To visualize this in Figure bins do not contain any eigenmodes (and thus have undefined overlap). We note that discrepancies in the tails primarily caused by distortions in the empirical eigenbasis caused by finite-size effects, rather than genuine disagreement between the theory and the true eigensystem (see Figure 6).
plot the overlaps in heatmap, graying pixels whose spectral
The experiments that generated Figure used the following hyperparameters:
* Gaussian kernel, gaussian data. Kernel width 6. Data E R0200 drawn i.i.d. Gaussian
with diagonal covariance E x = (i + 6) 3.0 This results deff R 7. We choose a steep covariance decay exponent to ensure that cubic modes are clearly present in the plot.
Gaussian kernel, C-FAR-5m. Kernel width o 6. No ZCA nor sample normalization.
This results in detf Rz 9.
Laplace kernel, SVHN. Kernel width 8v2. Whiten data with ZCA strength w² 5 x 10-3 and then unit-normalize. This results in deff R 21. We generally observed that det 2 20 is reliable rule of thumb for obtaining good agreement with the HEA using the Laplace kernel.
ReLU NTK, ImageNet-32. Bias variance of = 1.68 and weight variance o = 0.56. Whiten data with ZCA strength w² 10-3 and then unit-normalize. This results in deff RS 40. Examining the on-sphere coefficients, we see that o > is the ReLU NTK equivalent for the wide kernel condition for Gaussian kernels.
D.3 How TO DECOMPOSE THE TARGET FUNCTION We are interested in recovering the coefficients of the target f. in the kernel eigenbasis:
Recover is from samples of fx) Σ (z))
(45)
where is the mode index. According to the HEA, this amounts expanding f+ in the multi-Hermite basis:
f. (x) Σ oxh((x).
(46)
where hx(x)) is shorthand for the 7th the Hermite coefficients since the HEA will not hold exactly in practical settings.
polynomial ha, (z). We use different notation for
Of course, obtaining any full expansion of f. from N samples is exactly as hard as the original learning problem. However, can hope obtain expansion that is good enough predict the behavior of KRR trained with up to samples.
Let define y E N the vector of target samples and h; N the 7th melti-Hermite polynomial evaluated on the samples. Let us stack the top P < N modes [h, h2 hp] and call
HeHee, we abuse terminology by referring the proposed Hermite basis eigenbasis; evaluated on finitely many samples of real data, these hasis vectors may not be truly orthonormal.
24

---

Published as a conference paper at ICLR 2026
the resulting matrix H E ERPx <RPxNN We would like to recover the top P coefficients e E RR from and H.
Naïve first try. As first pass, let's simply linear regression: è H y. where Hi is the pscudo-inverse. Empirically, the recovered coefficients are not very good. There are two main reasons.
The target contains Hermite modes which are not represented in our top P list. This is an essential model misspecification which appears to linear regression target noise. This is not problem itself: the learning curve eigenframework can handle this kind of noise, if it knows how much noise power there is. However, it is unclear how to measure the magnitude of this misspecification noise, since it gets mixed with the sampling "noise."
Linear regression has flat inductive bias: it tends to fit the samples using each of its regressors with equal enthusiasm. Here, the regressors are functions, arranged (roughly) in order of decreasing smoothness. On the other hand, natural targets are relatively smooth; their power tends to concentrate on the early modes. This leads to large estimation errors in the top coefficients.
These two challenges, left unresolved, result poorly predicted learning curves.
Second pass. Let us instead consider the following greedy iterative algorithm:
Algorithm Greedy Residual Fitting (GRF)
Require: Target vector y E RR, Hermite feature matrix H E ERPNN
1: y +
2: for
P do
3: hp t Hp::
4: 0p (hp: y y(p-1))
> find the coefficient of h2 in ((p-1)
1
5: y y(P) + y (p-1)
6p hp
subtract off the projection onto hp
6: end for
7: return (f1...., Up) and 22
1
This is essentially the Kaczmarz method for solving linear system (Kaczmarz, 1937). This target recovery algorithm has a few notable virtues. First, it is direcr; does not require matrix inverses, so it runs in quadratic rather than cubic time. Second, since it is iterative and stateful, it automatically prioritizes correctly estimating the top coefficients, which where the target power tends to lie. Third, it naturally estimates the noise power (it is simply the norm of the final residual (P)3). Fourth, estimates the correct amount of total power: by the Pythagorean theorem, Σ, 0 + E² |
|1tp VN, that is, the Hermite polynomials are indeed unit norm."
We empirically find that this algorithm works well for synthetic targets on synthetic Gaussian data. However, real data not perfectly Gaussian. Even small deviations from Gaussianity introduce systematic correlations between the Hermite polynomials { these overlaps cause the greedy algorithm to systematically overestimate the target power in the affected modes.
We empirically found that if the target is sufficiently "dense" in the Hermite modes (i.c., not dominated by very few coefficients), then these errors "average out" (loosely speaking) and the predicted learning curves remain accurate. Unfortunately, this is rarely the case in real targets. Real targets often contain much power a few early modes, many of which suffer from this overlap problem. As a result, the predicted learning curves are often far off the mark. See Figures and 11 for empirics.
In our experiments we choose 30, 000 and N 80, 000 since manipulating this tensor maximizes our GPU VRAM utilization.
"If they are not unit norm. then the purposes of the KRR eigenframework, one usually wants take
i ++ 1/1 h ép to estimate the total amount of power in Hermite direction p. After adopting this scaling,
GRF again conserves total power by the Pythagorean theorem: Σ, 67 + 2² = ||yll
25

---

Published as a conference paper at ICLR 2026
Third pass. To rectify these modes, simply squeeze out the non-orthogonality, starting from the top Hermite modes. A standard technique for iteratively eliminating overlaps is to use the Gram- Schmidt process. In practice, this simply amounts to performing QR decomposition, QR H, and estimating the coefficients from the orthogonal component as é = Qy-
The major strength of this coefficient recovery technique is that it accurately predicts learning curves. Another strength is that since the regressors are orthogonal, the noise power is easily obtained as 1 6 6. The main drawback is that we must once again resort cubic-time algorithm. A natural question is then: if we are going to run a cubic-time algorithm anyways, why not simply diagonalize the empirical keree matrix? There are several reasons:
Universal measurement of target. This procedure only needs to be run once for given target function. The resulting coefficients can then be reused predict learning behavior across variety of kernels and hyperparameters.
Finite-size effects. Diagonalizing the sample empirical kernel matrix typically intro- duces distortions in the tail modes. The HEA avoids this issue by constructing the basis directly.
Numerical conditioning. The (non-orthogonallize)) Hermite polynomial matrix H is very well-conditioned on natural datasets. Performing Gram-Schmidt orthogonalization tends to be numerically robust, even 32-bit floating-poin precision. On the other hand, the numerical conditioning of kernel diagonalization worsens as the number of samples (and retrievable modes) increases; in practice, we typically need 64-bit precision to obtain reliable eigenvectors. As consequence, the prefactors for GPU VRAM space complexity are friendlier for Gram-Schmidt.
Theoretical insight. Kernel diagonalization is an opaque numerical computation; it does not expose the functional form of the eigenfunctions. The perturbed closed-fome formddfommmm expression offered by HEA+ Gram-Schmidt reveals the analytical structure of learning in kernels.
Takeaway. The HEA conceptually holds; the kernel eigenfunctions are small perturbations of the multi-Hermite polynomials, even for complex real data. If the target function is sufficiently dense, the perturbations are not important to model, and the target coefficients can be estimated using direct greedy method. However, for some real targets with prominent coefficients, we must be careful to account for their perturbations.
D.4 LEARNING CURVES AND SAMPLE COMPLEXITIES
In this section, we discuss additional considerations for evaluating learning curves. We end by cataloging the experimental parameters used to generate learning curve plots.
Evaluating the theoretical predictions requires summing over all the eigenmodes. In practice, we estimate this sum by truncating at some large P >> N and discarding the tail. For kernels with fast spectral decay, the neglected tail contributes negligibly and the truncation introduces negligible error. However, for slow- decayin kernels (e.g., Laplace kernel or ReLU NTK) the tail sum is non-negligible and we must account for it. We do this by modifying the ridge as
P
8 x
Tr [K]
Σ
(47)
This heuristic arises from examining the eigenframework conservation law
X
n
(48)
X + R
X
P-1 x
Σ
(49)
A R
X;
+
i=0
P-1
A
(50)
1=0
where the final approximation follows from the fact that P > Combining terms yields the tail-corrected ridge.
12 5o K. > X for the tail modes.
26

---

Published as a conference paper at ICLR 2026
Finally, detail the parameters used in each of our main experiments. All kernel regression experiments use a ridge of 10 and run up to 50 trials, each with a new test set of size 5,000. All target function estimates use 80,000 samples.
Figure I, top right. Gaussian kernel, width 4. No ZCA normalization.
Figure I, bottom right. Laplace kernel, width o 4v2. ZCA strength w² 10-3 with data sample normalization. Sample complexities are obtained by computing learning curves (empirical curves averaged over 20 trials), performing logarithmic interpolation, and finding where the test risk falls below 0.5.
Figure 3, top left. Gaussian kernel, width = 8. No ZCA nor normalization. We use wide kernel for better agreement at targets of high degree; for comparison with narrower kernel, see Figure below.
Figure 3, top right. Same as Figure I, bottom right.
Figure 3, bottom left. Gaussian kernel, width o 10. No ZCA, but the samples are normalized. For comparison with narrow kernel and no sample normalization, see Figure below.
Figure 3, bottom center. Laplace kernel, width a 4v2. ZCA strength w² 5 x 10-3 with data sample normalization. For comparison with no sample normalization, see Figure 10.
Figure 3, bottom right. ReLU NTK, bias and weight variances of 1.96 and o 0.49. ZCA strength v² = 10-2 with data sample normalization. We found that the HEA for the ReLU NTK is particularly sensitive to insufficient effective dimension.
27

---

Published as a conference paper at ICLR 2026
D.5 ADDITIONAL EXPERIMENTS
Gaussian kemee
Gaussian kernel @ CIFAR-10
Laplace kemel
ReLU NTK @ Imagenet32
@ Gaussian data
@ SVHN
predined
10
empircall
10
107
10"4
eigetvalie
10"1_
101
00
10
10"4
Iasarreddat
(pelinatc coales
cabicc
10
10"1
11-
10'
10
107
107
10"
10"
10"
Misie incles
Made index
Medic index 2
Moda indes
Figure 6: We show an alternative visualization of the top row of Figure 2. comparing the predicted and empirical spectra of various kernel/dataset combinations. We see that the HEA accurately predicts the minute details of the kernel spectrum. Furthermore, tail deviations are indeed caused by finite-kerner effects in the empirical spectrum rather than failure of the HEA. We plot the empirical spectrum with curve and the predicted spectrum with dots, instead of vice versa, so the colors of the dots can denote the polynomial order of the predicted eigenmode.
Kernel width
Kernel width 2
Gaussian kernel @ C1FAR-5m
Gaussian kernel
1.5
1.5
@ CIFAR-5m
test MSE
2j0
test MSE
210
1.0
Z100
1.0
2150
-2
20
23.83
F1.33
0.5
216
0.5
222122
202122
0.0
0.0
10
102
10a
10
10'
10a
10a
10*
training samples
training samples
Figure We compare the original plot from Figure with kernel width (left) to the same experimental setup except for a kernel width 2 (right). The true eigenfunctions of the narrower kernel deviate from the HEA prediction, especially for the high-degree modes. For a similar comparison, see Figure 13.
1,25
Gaussian kernel SVHN
1,25
Gaussian kernel
1.25
Gaussian kernel SVHN namow
SVHN
1.00-
1,00-
pprm
1,00-
te0 MSB
0.75
0.75
test MSS
0.75
0.50
even odd
even vs, odd
0,550
even odd
gonus
gonus others
0.35
others
0.25
others
0.35
0.00
0.00
10'
10'
10
10
10"
10
10'
10'
10
simples
simples
Figure 8: We compare the original experimental setup from Figure 3 (sample normalization. kernel width 10) on the left, to two similar setups: no sample normalization (center) and narrower kernel width of 4 (right). Interestingly, the narrow kemell width does not change the agreement much; removing sample normalization worsens agreement slightly.
28

---

Published as a conference paper at ICLR 2026
HEA prediction
Empirical kemel diagonalization
1.6
1.6
Gaussian kernel CIFAR-5m
Gaussian kernel
@ CIFAR-5m
1.0
1.0
test MSE
0.8
0.8
0.6
0.6
0.4
domesticated vs, wild
car vs. ship
0.4
domesticnted vs. wild
car vs/shipp
dog vs. all others
plane vs. frog
dog all others
plane vs. Irog
0.2
0.2
deer horse
deer vs. horse
0.0
0.0
10
10a
10a
10
10*
training samples
training samples
Greedy residual fitting
Assuming isotropic data
1.6
1.6
Gaussian kernel
Gaussianceenel @ CI CITAR-mm
1.4
@ CIFAR-5m
1.4
1.2
1.2
1.0
1.0
Lest MSE
0.6
0.4
domesticated
shiig
0.4
domesticated
shig plane vs. frog
dog vs. all
plane frog
dog others
0.2
0.2
deer vs. horse
deer vs. horse
0.0
0.0
10'
102
10a
10*
10'
10
10a
10*
training samples
n training samples
Figure 9: Here we show four plots in which the experimental setup does not change; instead, we compare different techniques for estimating the required theoretical quantities. (Upper left.) HEA prediction, identical to Figure (size 25000 25000) and use the obtained eigenstructure to make predictions. The accuracy of the prediction degrades as the number training samples approaches the size the kernel matrix used to estimate the true cigenstructure. (Lower left.) We use the greedy algorithm described in Algorithm 1 to estimate the target coefficients. We see good initial agreement, but it degrades due to accumulating non-orthogonaliiy. (Lower right.) For comparison, one modeled the data distribution as an isotropic Gaussian. Clearly, major contribution of our work handle the anisotropy in natural data, since strongly affects the resulting learning curves.
(Upper right.) We numerically diagonalize the kernel matrix
include the predictions
would obtain if
29

---

Published as a conference paper at ICLR 2026
Laplace kernel @ CIFAR-5m
1.25
Laplace kemee @ CIFAR-5m
1.00
test MSE
no norm
test MSE
0.75
vs. all others
0.5
car vs. truck
0.50
all others
dog vs. frog
car vs. truck
vehicles animals
0.25
dog vs. frog
0.0
vehicles vs. animals
10
10a
10a
0.00
10
10'
training samples
n training samples
Figure 10: We compare the plot from Figure 3 on the left with an identical experimental setup, except without sample normalization. We see that normalization is necessary for obtaining agreement, since the HEA is derived using the kernel's on-sphere level coefficients.
1.2
Laplace Kernel Imagenet32
1.0
0.8
test test MSB
0.6
source exp. 8
0.4
3 3= 1.05
3 1.15
0.2
3 = 1.25
3 1.5
0.0
10
10a
10a
10
training samples
Figure 11: For "dense" synthetic targets (i.e., targets whose power is split among many eigenfunc- tions), the HEA predicts the performance of the Laplace kernel very well. Contrasting this with predictions for Laplace kernel on real targets (Figure 10), we conclude that dense targets are more forgiving of errors in target coefficient recovery. For this experiment, we use ZCA strength w 10 and sample normalization.
Laplace kernel
10
@ CIFAR-5m
Predicted complexity lexitty n
2190
103
100
2g 21 2/2
linear targets
20
10a
quadratic targets
cubic targets
quartic targets
10
10
10a
10a
10
Empirical sample complexity n
Figure 12: Additional sample complexity plot, this time for Laplace kernel on CIFAR-5m. We use sample normalization and ZCA strength of x 10-3
30

---

Published as a conference paper at ICLR 2026
E
WHAT BREAKS THE HEA? CASE STUDIES OF THREE CAUSES OF FAILURE
In the main text, we have primarily shown results in settings in which the HEA works quite well in predicting kernel eigenstructure, learning curves, and monomial learning rates, Here we get our hands dirty and show where it breaks.
First cause of failure: narrow kernel width. The discussion of Section 4.1 suggests that if we make kernel width too narrow or, in kernels without notion of width, change the kernel so that Se+1 much less than one we should start the HEA break. In particular, since for Gaussian kernel x o-22 2/ narrow width means non-small level coefficient ratios and vice versa. Figure 13 shows an empirical test: on the same synthetic data distribution, the kernel is made progressively narrower. As expected, the HEA breaks.
Second cause of failure: low data dimension leading non-concentration norm. The HEA treats all Seaation-invaran kernels as if they were dot-product kernels. In fact, it throws away all information about the kernel function that cannot obtained by its value on a sphere. For this to work in practice, we should expect our data to lie fairly close to sphere. For Gaussian data æ Σ, TY
Figure 14 shows that with a this is assured if the data has high effective dimension den == T-
Laplace kernel on a Gaussian dataset, the HEA breaks as deft decreases.
Interestingly, not all omation-invariaal kernels require high effective dimension. For example, our heuristic derivation of the HEA for Gaussian data in Section 4.1 took place in just one dimension! As turns out, this is because the Gaussian kernel is given by polynomial feature map (of infinite dimension), but the Laplace kernel has cusp at x and is not. (Equivalently, the Gaussian kernel
is analytic, but the Laplace kernel not.) For a stationary kernel K(x, x²) = k (22 |x - x²(3²) limit will give
which depends only the distance between points with scaling factor a, the the HEA on Gaussian data if the function k(-) is real-analytic at zero. The Gaussian kernel satisfies this real-analytic criterion, but the Laplace kernel does not, As evidence of this, Figure 15 repeats the above experiment with Gaussian kernel and finds that low dar is no problem.
We note that there is another problem conflated with this one: as discussed in Appendix B, the Laplace kernel's 's level coefficients actually diverge superexponentially, and the predicted HEA eigenvalues diverge faster the closer
21 E. is one. One could disentangle this by studying a rotation-invariant kernel that (a) does not factor into a product of one-dimensional kernels like the Gaussian and exponential kernels do but (b) is still analytic, its level coefficients will not diverge superexponentially. Such kernel is not among those studied here, so we leave this to future work.
Third cause of failure: the data not being "Gaussian enough."
The HEA is theoretically derived for Gaussian data, but nonetheless works for some real datasets. This suggests that the datasets for which it works are "Gaussian enough" in some sense. Here we support this intuition with experiments. First, in Figure 16, we plot the marginal distributions of the first few normalized principal coordinates for four datasets of decreasing complexity: CIFAR- 10, SVHN, MNIST, and the tabular UCI Mushrooms dataset (Dua & Graff, 2017). Plotted this way, these datasets appear increasingly -on-Gausiinn. Then, in Figure 17, we test the HEA on these four datasets, finding that the HEA indeed seems to work worse as the dataset becomes "less Gaussian." For good measure and out of interest, we plot the first few PCA coordinates for the three image datasets in Figure 18.
Of course, we put "Gaussian enough" " in quotes because this is a nonrigorous and ill-defined notion: we have not invoked any precise method of determining which of two datasets is "closer" to Gaussian! We do not attempt to give a precise definition here. This seems like a worthwhile direction for future exploration, especially from the statistics community.
31

---

Published as a conference paper at ICLR 2026
Gaussian kernel Goussian data (width or 6)
Gaussian kernel @ Gaussian data (width o 1.5)
Gaussian kernel @ Gaussiun data (width 0.8)
Gaussian kernel @ Gaussian data (width o 0.5)
thenry empiriie: spectrum
Prodctal cigenvlls
10
10
50
10
10"1_
lace
10
60
10
2. 16660
00
10
10
10
10
10
10
10
10
10P
10
10
10
Frepiniral rigensshr A,
Fmopirical rigeroahin A(ma)
Farginicl eigrnvater
Firpirico eigenvalor (me))
(grouped in spoctral biss)
thenry empiries:
kernel ciganbusis
eijonpacs
Peedited cigenepcc
Predicaa cigstogacc
Peedccd
Impiicaal
eigesspoce
Empincal eiginspoce
Empiriical digrrspoce
Figure 13: The HEA breaks when kernel width is too narrow. We repeat the experiment of
Figure with the Gaussian kernel function K(x, x') = - ||==2 and synthetic Gaussian data. The data is generated as (0, r), where I has eigenvalues % i for 1...30 .0.3, with 'n ss 0.83 after normalization. As the kernel width shrinks to a S 1, the HEA breaks: eigenvalue prediction fails with higher-order modes dominating predictions, and the clear eigenspace overlap present at large width evaporates.
Laplace kemel Gaussian data "ti oc (i + 3) 1.2
Laplace kemel Caussian data
Laplace kemnel @ Gaussian data
Laplace kernel @ Caussian
71. xc + 1.5
2/ Dc (6 2.0
"V x (6+
35-25
33.48
dg 10/91
Agr 1.63
theny empirios kemel
Prodiccd cigatollc
10
10
50
700
10-11
10-1
10-
10
zublic rasioo
wade
10
50"1
00-4
Empirial cigencalie A (laas)
Eupiriaal digeovalue Aesss)
Empiriaa (eept
Empiriaa eigenraluc A (teg)
(grouped in spectaal biss)
theury empiries:
sigenbasis
Prodesed djpnngise
Prodecod elycnspucc
Predkcsk cipesepcc
Peulical diganegtec
Empincall zigatsyex:
Empiniall cigenspuat:
Enginial rigeraquan
Empiriol rigenopusz
Figure 14: With the Laplace kernel, the HEA requires high effective data dimension... We repeat the experiment of Figure 13 with two modifications: first, the kernel function is Laplace
K(x = - -||===']] = with width a = 8,2, and second, the eigenvalues are 7/2 x (i + 3) with variable exponent As increases (moving left right), the effective dimension der decreases, and agreement with the HEA degrades. Empirically, we find that dett is usually high enough to good agreement.
(Σ. x)
Σ,
32

---

Published as a conference paper at ICLR 2026
Gaussian kernel Gaussian data TT (i++3 3)-1/2
Gaussian kernel @ Gaussian data
Gaussian kernel @ Gaussiun data
Gaussian kernel @ Gaussian data
T/ (2-1) -1.5
XC (8++ -2.0
TV. -3.0
da 35.35
50
4a m 21.44
13"
da 10:40
30
Ae 6.82
theury Vs empiries:
Prolical cigardie
10
50-
70-
kernd
cuddaii mede
10
12
20"h
Empirical digenvalte A(
Empircaall eigenvalte A(me))
Empteicall Areat
eigenvaloe A (mee)
(grouped in spectaal bins)
theery is empines:
kenel aigenhasis
Piedictol egensgaae
Prodiccol djenspace
Prolicced dipanppcc
Poolicaal digrtepaee
Frrginral digntepoor
Prppiniaal rigeaspext
Fnginaal rigenaquos
Forpirical rigeraqunz
Figure 15: ...but with the Gaussian kernel, it does not need high effective dimension. We repeat the experiment of Figure 14 exactly, but use Gaussian kernel with width = 3. Thanks to the smoothness of the Gaussian kernel, we little degradation of the theory-experiment match of the HEA.
cueedinate
Scanal PCA comniinat:
coadinate
Fouth camniisn
coent dandiy
CIFAR-10
Gansdas
0.0
0.4
SWHN
0.4
MNNST
0.0
Mushroons
-2
2 0
2 -4 -2
-2
D
2
22
Figure 16: Different datasets have different degrees of Gaussianity in their early principal components. For four natural datasets CIFAR-10, 10, SVHN, MNIST, and the UCI Mushrooms tabular dataset we compute the first four normalized principal coordinates (=,)² and plot their distributions histograms. We find that the first few principal coordinates for CIFAR- 10 are fairly close to Gaussian, this is less true for SVHN, yet less true for MNIST, and not at all true for the Mushrooms dataset.
33

---

Published as a conference paper at ICLR 2026
Gaussian kernel @ CIFAR-10
Gaussian kernel
Gaussian kernel @ MNIST
Gaussian kernel @ Mushrooms
@ SVHN
10
30'
12
thenry is empitics
Prodkcast eigarable
10
10
80
10
kernel
guddaiic mode
10"h
1072
Empirial cigesvalae A(100)
Empirial rigeovalue A(rap)
Eupirial cigenvalec A (Hept
Empirial cigeovalue A (164))
(grouped in specteal bios)
theney vs empirics
korel sigenbasis
Froduces dignnggoos
Prediced eigcnsquoc
Predicad cigatogiac
Predica digantgiaa
Erepincall diganspext
Eupitiza cigenspaxx:
Enginial digeraquax
Empirial Eigersqusz
Figure 17: The HEA works better with complex high-dimensional datasets and worse with simpler datasets. We repeat the experiment of Figure with Gaussian kernel of width = on 8000 samples from four datasets of increasing non-Gaussianity: CIFAR-IO, SVHN, MNIST, and the UCI Mushrooms tabular dataset. As the dataset becomes simpler, the HEA works worse and worse, though the predicted trend is still roughly present, if quantitatively wrong, even for the tabular dataset.
First PCA coordinate
Second PCA coordinate
Third PCA coordinate
Fourth PCA coordinate
CIFAR- 10
SVHN
S
9
MNIST
Figure 18: Visualization of the first four PCA directions for the CIFAR-10, SVHN, and MNIST datasets.
34

---

Published as a conference paper at ICLR 2026
F LIST OF ASSUMPTIONS MADE IN THE PREDICTION OF LEARNING CURVES
In Section 5, we demonstrate that using our HEA framework, we are able to predict KRR learning curves from the data covariance, a Taylor expansion of the kernel, and polynomial decomposition of the target function. We made many assumptions and simplifications on the path to deriving this theory. We summarize and discuss them here:
1. We model the data distribution as an anisotropic Gaussian in the input space order to get analytical eigenvalue and eigenfunctions.
2. We assume any given rotation-invario
kernel may be replaced with dot-product kernel. 3. Even with assumptions 1 and 2, the HEA holds exactly only in limiting cases (e.g. Theo- rems I and 2). We pretend it exact.
4. We assume our
procedure finds the correct Hermite coefficients of fx. 5. In order to invoke the KRR eigenframework, we assume Gaussian universality the kemnll
eigenfeatures.
6. Even with Gaussian universality, the KRR eigenframework has finite error at finite sample size nI. We assume that is large enough that this error is small.
Steps 1-3 above get us to the point where the HEA gives the kernel eigensystem. These are the assumptions discussed and validated in Section 4.2. Step 4 treats the decomposition of f.. Steps and are assumptions made in the use of the KRR eigenframework, Prior work has established that Gaussian universality reliably holds and the eigenframework gives accurate predictions even at modest n, and we encountered no additional subtleties in this work. We note that this prior Gaussian universality in kernel feature space, which allows the use of random matrix theory tools in the derivation the KRR eigenframework, distinct from our modeling of the data as Gaussian the input space. The latter is a stronger assumption, more naive and more surprising that it often seems to work well.
Each step here will introduce some error to the final prediction of learning curves. The total error will be small only when each individual source of error is small. In this paper, we opt for a scientific approach to this problem: we use theory guidance to suggest when each source of error will be small, and ultimately rely on empirics to validate our assumptions, checking steps individually and then putting them all together for the end-to-end prediction of learning curves. Much of the challenge in getting the empirical results for this paper lay in identifying, isolating, and fixing errors due to one of these steps. While comes with no formal guarantees, this scientific approach has the practical advantage of efficiently surveying a wide swath of settings and cases, notably including real datasets.
is also possible to take a mathematical approach to the problem of cascading errors: presumably, one might analytically control the error introduced in each of the above steps. leading to error bounds in the final learning curve. (See Wortsman Loureiro (2025) for an analysis of this type.) This approach will be difficult, with the greatest challenge lying in the application to real datasets: what can we say analytically about CIFAR-I0 that might enable formal proof of the empirical success of our theory? This is a worthy challenge, and this general type of question - finding useful formal conditions applicable to real datasets - is important for the advancement of the theory of machine learning. We leave this as open problem and invite interested parties to reach out us with ideas or results.
ClCearyyy it is a useful trick in the study of machine learning theory to replace distributions with moment- matched Gaussians.
35

---

Published as a conference paper at ICLR 2026
G MLP EXPERIMENTS: DETAILS AND FURTHER DISCUSSION
As the HEA requires level coefficients to predict Xa, level coefficients for MLP experiments are computed with the ReLU NTK with both bias and weight variances of which match the empirical variances of our MLP networks at initialization.
Unless otherwise stated, all experiments were performed using feature-learning (nP) MLP with the following data hyperparameters:
7: = (i + 6)
1.7
imput dimension d = 200
and MIP hyperparameters,
width w 8192
depth (number of hidden layers) L = 2
learning rate r = 2 10-2
batch size bsz 1024
< = 1,
where Çis is the richness parameter (defined by a rescaling of the network's output f + f/S and either learning rate M/nx - ?/u Ç2/L for <> 1 or M/max ++ 1/o ç² for Ç < 1, 17o representing richness- innneesdenndeennentt learning rate) allowing a network to scale between an ultra-rich and lazy/NTK regime (Atanasov et al., 2024). In order to avoid network outputs exploding for Ç < 1, we have all MLPs output the difference f(x: 0.) (a: 0o) for network parameters at gradient step / being O,.
All experiments were carried out in online setting, with Piter being the number of SGD steps it took to reach a train error Mr S 0.1. This choice is largely inconsequential to the results, and was only chosen such that (1) we ensure each target function is properly fit enough, and (2) training did not run for a prolonged time. Random samplings of n-bsz Gaussian datapoints produce variance in high-order Hermite polynomials, so exponential moving average (EMA) for MSE, is used with decay constant 0.9: EMAr, = 0.9MSEn, i + 0. 1.MA. t- This corresponds with a half-life for the train error of about steps. This ensures nigh-variance random samplings do not cause the effective optimization time Rier to be skewed in favor of higher order modes. We varied the EMA constant and found values less than 0.9 to underestimate high order modes' (as we had higher probability for random samples to have a naturally low Hermite norm) optimization time and values greater than 0.9 to overestimate lower order modes' optimization time (due to all modes' optimization time being offset by a constant). One could subtract the half-life from an empirically found Niter with any EMA constant to get a more EMA EeM--unbiseed estimate for when the test error goes below the set cutoff, although we do not perform such procedure. We additionally varied the loss cutoff (in the termination condition MSE S cutoff) and found that small changes did not significantly affect our results.
This network is empirically validated to be in the feature learning regime by looking at the Gram matrix W| Wi, with W, E IR widthh initialized with Gaussian entries. A lazy network has this Gram matrix constant throughout training, whereas feature learning allows for @(1) changes to the spectral norm of the W1, producing ((1) changes to WT W, (Yang et al., 2023). We train networks on simple PCA-mode target functions and find significantly more power in the Gram matrix entries corresponding to the data indices used in the target function, confirming that the MLP is operating in the feature-learning regime (Figure 19).
1
We check if our hyperparameter choices were simply lucky, or if our X= ~ Tliter scaling is real and reproducible. We take our base case, and vary all hyperparameters (depth, width, learning rate, batch size, data covariances) change we observe is an wewptvalll--nepeedddeee rise effective optimization time when going to a more shallow network. Results are summarized in Figure 20.
do not expect affect the scaling, finding that none do; the only
The only hyperparameter we know will change the exponent of X ~ 17 Aitrr is the richness parameter (: when Ç & 1, the kernel analysis in the main text tells expect exponent 1. What is
36

---

Published as a conference paper at ICLR 2026
ong
0-
2-
4-
6
8-
Mode dggtg
Mode a].=
2
8
Figure 19: Validation of MLPs being feature-learning We investigate the Gram matrix of the first weight matrix, WT W,. We train MLPs with ( 1 on d 10 Gaussian synthetic data for 1000 GD steps. Yellow denotes higher entries, while blue denotes near-zero entries. The Gram matrices are heavily weighted modes present in the target function, confirming the feature learning regime.
unknown is the scaling exponent as >>>>>>> our effective optimization time's defined as the base Ç-independent learning rate. Our findings are shown in Figure 21.
1, which we find to be lower than the baseline 1/2. Lastly,
Lastly, would like note that the base synthetic case and the CIFAR-5m case were averaged over 3 trials, and upon finding remarkably small standard deviation in effective optimization time, all further validation experiments were completed with only a single trial.
37

---

Published as a conference paper at ICLR 2026
10
Base case
Lower depth
Higher learning rate (1) 0.1)
MLLP @ Gaussian Data
(1 hidden layec)
Eff. opt. time 1l Nittrr
10a
constant
101
lincar
quadratic
cubic
quartie
10"
10
Narrow width
Lower batch size (batch size=64)
Different data exponent (a=11.14
(width= 1024)
10a
10'
10"
10
10
10
10
101
Inverse of HEA eigenvalue A -1
Figure 20: Our primary MLP results are largely invariant to hyperparameter choices. We train MLPs synthetic Gaussian data, with one hyperparameter being motified. The base case is shown in the (top left) for reference. Apart from the (top center), all modifications produce no notable changes observation of A 1/2 different than the rest by a change in ceenvallu--ndeppndeee prefactor, the scaling law still holding.
Raarr scaling. (Top center). The 2 hidden layer is only
10
Lazy
Rich
10
Ultra-rich
10
Eff. opt. time No Water
5
=10 -3
(=
Ç =10
10
10a
10a
constant lincar
10at
quadratic
cubic
quartic
10
1/2
10
0.47
10a
10'
10'
10
10
10
10a 10' 10
10*
Inverse of HEA eigenvalue Ag
Figure 21: Sweeping the richness parameter changes the slope. All. The effective optimization time uses the richness-ined independent learning rate no instead of 17. (Left) We validate taking < 1 to bring into the lazy/NTK regime, where know the eigenvalue to be inversely proportional the effective optimization time. To speed up training for the lazy runs, we set Yo 2 10 This likely is the cause of the constant mode being notably high. (Right) We investigate the so-called "ultra-rich" regime Ç > 1 and find there to be a A r7 Tijerr relationship. We suspect the 0.4 slope in the ultra-rich regime would change with variation of hyperparameters and thus fundamental, unlike the slopes of and 1/2 in the lazy and rich regimes.
H REVIEW OF HILBERT SPACE THEORY
In this section we review the basics of Hilbert space theory, which would be very useful in proving theorems in the next few appendices.
Naïvely, Hilbert space is just Th" or C", where n is allowed to go to infinity. In the standard notation, it is written as (H, (-1-)), where H is the set of vectors, and the angular brackets (+1-) is the inner product on pairs of vectors in the set.
H.1
DIRAC NOTATION
We use the standard Dirac notation.
Vectors written (r) H.
38

---

Published as a conference paper at ICLR 2026
The duals of vectors H. are written as (v), defined via the inner product: {ul (w))
(ulw).
Linear operators are written as capital letters: A.
Linear operators act on the right: (v]AAw) (v(((A)))
For example, the Euclidean space IR is a Hilbert space. Its inner product is the dot-product (ulw) w. Write column vectors kets and conjugates bras:
U1
(0)
(ol
1n) = luz
vul (v/w) = (vl (w) = TTuT w.
va
For matrix A Rddd it acts vectors by multiplicattin the right. Rank-one operators are of the form (e) (w/, with action (z) + [o)
H.2 OPERATORS
In a Euclidean space, such as R3, the geometry defined by its lengths and angles. linear operator on R preserves lengths and angles, and therefore preserves its geometry, iff it preserves the dot-product between vectors. Such seometry-preserving linear operators are called orthogonal operators.
Generalized to Hilbert spaces, geometry- linear operators are called unitary. An operator V H - K. is unitary iff
(Vul = (o/w), ||||)||| |I
For example, a unitary V R" R" is just orthogonal matrix. Unitary maps preserve all geometric relationships, such as angles between vectors, lengths of vectors, and orthonormal bases.
The rank of operator is the dimension of its range. By the analog of singular value decomposition in Hilbert space, if an operator has finite rank r, then it can be written in the form of Ex=1 (2%) (ux)-
In Euclidean space, operators have transposes. The transposition of operators satisfies (ATw) Tw)T w T (Av). Generalized to Hilbert space, operators have adjoints. The adjoint of an operator A is written as A", and satisfies
(wl Au) (A'wlu)
In a Euclidean space, symmetric operators are operators such that A = AT. In Hilbert space, self-adjoint operators are operators such that A
Just like how symmetric operators on Rd are of the form Ed=1 agvEey self-adjoint operators are of the form Σ3 a& (u)) (vu), although the summation may be infinite.
The operator norm a norm defined on operators. is defined by |Alop := SMPpsH.|===11 |Ax].
An operator positive definite, written as A > 0, iff is self-adjoint, and (u/Alp) > for all nonzero u)). Similarly, operator is positive semidefinite, written A >- 0, iff is self-adjoint, and (o (o|AAp) geg0 for all (p).
H.3 COMPACT OPERATORS
In infinite dimensions, some finite-dimensional intuitions break. A finite-rank operator, by virtue of being finite-rank, behaves essentially the same as a linear operator between two miite-dimensional spaces. However, they are somewhat too trivial. Compact operators are a compromise. They can have infinite rank, but still allow some finit-ddimensional intuitions to apply.
An operator operators.
- is compact iff the operator-norn limit of sequence of finite-rank
Symmetric matrices are diagonalizable. Similarly, if an operator is compact and self-adjoint, then is diagonalizable: There exists an orthonormal basis of eigenvectors {le,) hee and real eigenvalues {A heu with
K = Σ Nele
A A, - 0.
jEJ
39

---

Published as a conference paper at ICLR 2026
Nonzero eigenvalues have finite multiplicity, and the eigenvalues can only accumulate at zero. We will only study operators very specific form that arises naturally from kernel regression.
Let (n20 be orthonormal set in H. and let an 2 0 with En On co. Define
K
an en
Then:
K is self-adjoint, positive, has finite trace, and compact.
K has eigenpairs (An, (ux)) n 2 0}, counting multiplicities of repeated az.
| sup, On. Tr [K] En On
H.4 FUNCTION SPACES
Generally, the vector space of functions is certain geometric intuitions honed from low-dimensional Euclidean spaces are still useful even in an infiiiteddimensional function space.
Hilbert space theory shows that
As basic example, consider (dxx), the set of square-integrable functions on IR + R, with inner product
(flg) = f(z)g(x)dz
This generalizes to (d(d.z). the space of square-integrable functions on RDD - RP. It has inner product
(f1g) [ (()gg())d
Let be probability measure Rd. Then (2) is the space of functions f such that Jae (())) That is, the space of functions f. such that if X p, then f(X) has finite second-moment.
The inner product (flg) [X
In this formalism, the expectation operator is simply taking the inner product by the constant- vector:
E (r=,[[(()) = Ex~w f(X)) = (11))
We will mostly study (H) in the case where μ Gaussian distribution (00 E). Those cases are called Gaussian spaces.
We will concern ourselves mainly with integral kernel operators over L²( An integral kernel operator is a linear operator of the type K (²) + [2)).. It is defined using a kernel function K ddd x Rdd
R. such that
w<x)= 1 K( y)u(y))(dy)
Kle) (w):
Solving for the eigensystem of K is equivalent to diagonalizing the kernel operator, such that
K
Am (w
n=0
for some orthonormal basis (w,).
As an example, the dot-product kernel in R2 is
On (ry)"
K K(x,8) u) =
m!
n=0
40

---

Published as a conference paper at ICLR 2026
In operator form, it is equivalent to
Cn (2n 1)!!
K
(nn) (val
n=0 n!
where we define the vectors corresponding to the monomial functions:
n
(un), The factor of ((2n - 1)!! is necessary to make sure the vectors are unit-length: (vn/u,)) 1. The problem with the representation
(x)
V(2n 1)!!
62n 1)!! (Un)) (vml
K
n!
is that, while looks like diagonalization, is not, because the vectors unit-length, but not orthogonal to each other. Diagonalizing the kernel is impossible in general, but it is possible in certain limiting cases. Our main theoretical work in this paper is just working out these cases.
H.S ID GAUSSIAN SPACE
Let p(dx) (2TT) e /2 be the standard Gaussian distribution R². We have the ID Gaussian space (p).
x²
The differentiation operator D, maps f(z) to (x), and by antegration-by-per by-parts, has adjoint
D De + æ
Therefore, define the Ornstein-Ullenbed (OU) operator
L = D zD2 DD)
Then L is self-adjoint and positive semidefinite (1))
The eigenvector equation for is
L = An vn) = [x(x) - -v0x) (x) + (z) =0
This is just Hermite's differential equation, with solutions being the probabilist's Hermite polynomials He,, They are orthogonal in (p) with
En Hem (X)He,X)) nl6mnn.
but not normalized. They are normalized by
(en(x)
h (Ir)
(ha) E (²()).
Vn!
Thus we see that the normalized Hermite polynomials is the eigensystem for the OU operator in Gaussian space:
Llh,) nl/w),,
L
Σ (ha)
n=0
Since the OU operator the simplest way make self-adjoint operator out of the differentiation operator Dr., it a natural object to consider.
H.6 MULTIDIMENSIONAL GAUSSIAN SPACE
The gaussian space over R' can be generalized to multiple dimensions. Let μa = NN0, Ia) be the standard gaussian distribution on e The corresponding OU operator is
d
-=
-=
Σ
82 + xd..
41

---

Published as a conference paper at ICLR 2026
That is, write L sum of 1-dimensional OU operators, L Σi= L, Note that the operator operates on the dimensions 21,..., Fd without interfering with each other:
(z1) ... fa(za)) Because of this, the eigensystem of I. is obtained directly by taking the produet of the eigensystem of Li....,aa
(z)) fa(za) +... + fz(1)) ... fa- (
For a multiindex a (al)..., add) E N set
Hea (ara) Va.!
He (x)
I[ i=1
Hea, (zi), ha(x)
|00| == Σo. oz.
Then, L is diagonalized as
L Σ [allha) (haa
aEN4
For each n 0, 0,1,2,.... the eigenspace
En : == ||x|= =n}
has multiplicity
dim E, #(a E Nod |a| = n) n - )
d
This degeneracy is due to symmetry. For any orthogonal transformation M - Rd and any smooth f Rd + R. we have L(f o M) = (Lf) M. Consequently, (v,) is a solution to the eigenvector equation L(e,) Xn (n,), so would its spherical rotations, and any vector sum of them would have the same eigenvalue An-
This is similar to the case of solid harmonies in Rd. In that case, A is also spherically symmetric, and its eigenspaces accordingly are degenerate.
H.7 UNITARY TRANSFORMATIONS OF GAUSSIAN SPACES
Consider two Gaussian spaces L (N Ia)), (2 Σ)). One of them is standardized, the other is not. Since many properties of the Hermite polynomials are derived over the standard Gaussian space, we would like translate statements in L (0, Ia)) to statements (N E)).
By the geometric view point, as long as a statement is cast in the language of Hilbert space geometry. the statement will continue hold true after any unitary transformation.
Now, suppose we have a matrix M such that M M = Σ, then
E (x [X)] (
Thus, have unitary transformation V (O, E)) (.3 Ia)), defined by
(v))())= f(Mx), (V* ((M-
Note that the matrix M has an ambiguity: If MM E, then given any orthogonal matrix O, we also have (OM)(OM = Σ. Thus, we can obtain an entire family of unitary transformations, one per orthogonal matrix O. We will exploit this degree ambiguity later.
Vectors can be transformed. So can operators. An operator A is transformed to VAV* so that (VV)))))) = (((lo))
(3(N(0,E)) A, L2(N(0, E))
(2(N(O, VAV L2(N(0, (2)
If operator is represented as Σn an h.// (unl. then its transformed operator is represented as Σn an V(w,) (v. (v.[VV' V In particular, diagonalized operators stay diagonalized:
A
An Amlvn) (val
VAV* = >nn An... (v.lV
Kernels are transformed the same way as functions, since
Ex ( (X ()(Y)
=IE Bx (YMMM)))
42

---

Published as a conference paper at ICLR 2026
H.8 SOME USEFUL PROPERTIES HERMITE POLYNOMIALS
Let be the standard normal distribution on R² For each n E N, define the normalized monomial vector [en) by the function (2n D)l!"
and define the normalized probabilist's Hermite polynomial
vector [bm.
Aii (x).
They are both sequences of unit vectors in (1). However, the sequence ((o),, [(i)... is orthonor- mal, but the sequence (uo), /u),... not orthonormal, and fact, is increasingly ill-conditioned.
By looking up standard reference table, we have the following basic properties:
1. ho), 1/2), 1ha).... vo). (2). [Fa).....
are obtained by
Gram-Schmidt
orthonormalization of of
2. Ihi, Iha), Ihs),...
are obtained by 21), (s)), ( [us.....
Gram-Schmidt orthonormalization
3.
(-1) (2n 4m 1)!!
(nn) re!
(n--2m)
mm 2m)!
m=0
4. (na) -m== Mam Mmm) where M is an invertible lower-triangular matrix satisfying
n!
Mn,n 2m
((2n 1)!! ml / (n 2m)
2m vnl m / (2n 4m - 1)!!
M M
2mm 2m)!
for 0 < 2m S
5.
(n+m - 1i!!
m mod 2
(Un|Um)
(2n-1))! (2m-1)
else
In particular,
v (2n 1)(2n 3)(2n 5)(2n 7)
(Un (2n-4)
(2n - 1)(2n - 3)
(2n 1)(2n 3)
(Vn/Un-2)
2n
(vnlvn) 1,
2n +
(v, (vnlv))2)
(2n + 1)(2n + 3)
(2n + 1)(2n + 3)
(unlunta)
v (2n 1)(2n 3) + 5)(2n 7)
A useful operator is My, the mullippy-by-z operator, which, using the multiplication formula xHe, He nHen-1
gives
M₁ vn- n 1/m+t) (hml + vn + I(hm)) (hatal
a
It is equivalently expressed as M, = ata", where a = En Vn + 1[/h,) (bo is the lowering ladder operator. Furthermore, because He', = nHe,- , the lowering ladder operator is the differentiation operator D.. Therefore, a" D M2 M2-- Da.
43

---

This the Published as a conference paper at ICLR 2026
I PROOF OF THEOREM 1
In this appendix, we prove Theorem 1, which states that the eigensystem of a Gaussian kernel (2, x²) = e 2 ||= on a multidimensional anisotropic Gaussian measure μ = NN Σ) approaches the Hermite eigenstructure given in Definition as oc. To show this, will obtain exact expressions for the kernel eigensystem, then simply show that the eigenvalues and eigenvectors those predicted by the HEA up to terms that vanish as a grows.
We will proceed in three stages of successive generality:
1. We solve the problem for (2))), where μ (0, 1) the standard Gaussian. hardest stage.
2. We take an outer product of measures to solve the problem for (J)), where μ = -N Ia).
3. We solve the problem for L L²()), where μ = (O, E), by taking an opportune unitary transformation from (NN,O,, 7)) to (0().
1.1 PART I: THE ID UNIT GAUSSIAN
We solve the problem for (H),,, where μ (O, 1) is the standard Gaussian. Our approach here is more conceptual and geometric compared to the one used by (Zhu et al., 1997).
We first quote the Mehler formula (Mehler, 1866):
p² exp (2 + y²) 2pxy
Σ (z)n(
2(1 -p²)
n=0
for any o E +1). where hg is the normalized Hermite polynomial.
We multiply by (1 p), and substitute with p e- to make the form more beautiful:
Vtanh(t/22exp (a² ( + y²) 2ry
4 sinht
==0
is more beautiful, because En=o(1 - e e)e ")e- nt = 1, meaning that the right side could be read as a discrete exponential distribution the Hermitian modes.
Define an integral kernel operator K; (+²()) + (1) using the expression on the left:
(Kif)xz) = ( Vtanh (tanh(t/2)ess) exp
( +²2
2zy
f(y)uldy)
4 Asinht
The Mehler formula then states that K₂ is diagonalized as:
K Σ (1-e (n( (hal- 1=
Thus, we have successfully obtained a one- peepmaraeeter family of integral kernel operators, all diagonal- ized in the Hermite basis. Each operator has Gaussian kernel. However, of them matches the form that we want:
K(x, y) 262 (R-w)²
In order to reach such form, we need to construct [T, E RR. a one-parameter family of unitary transformations (2) Then we will solve for т, t, such that T,, K,V, V has the desired kernel form.
For any E IR, define the squeezing operator T, (²( + (²( by
(I+f)(x) e - 22
This is unitary by direct integration and change of variables. is a one-parameter family, and satisfies
= = T, o = Tr
In the language of quantum mechanics, this is Boltzmann distribution of the quantum harmonic oscillator, i.c. thermalized state.
44

---

Published as a conference paper at ICLR 2026
We can interpret this one-parameter family continuous "rotation" in (p).. Except that, because (p) has infinitely many dimensions, the rotation need not return to the starting point. Concretely, consider what happens when the Oth Hermite vector (ha) is rotated. The family of vectors T, (ho would not turn back towards (oo again. Instead, it continues to rotate further and further away, with
(ho (ol
0
c
as T + oo. Such behavior is possible, because there are infinitely many dimensions to rotate to.
The one-parameter family T, can be written I, e where A is the infinitesimal generator of the family:
A = 0+lr=uT, xD + 2 (1- He, D= + Hcz
2²)
2 Using the multiplication and differentiation formulas of the Hermite polynomials, we have
AHle, (He,t2 n(n 1)Hee,2),,
1
He, = 4 (Hen+1 - 2(n² + + H) + n(n 1)(n 2)(n - -)
Thus,
(hml O, (h.|44(hh,) n12 + +
Therefore, the angle between (h,,)) and Tr (h,)), the limit of small T, is
n22 + n +
arccos(halle A =
7 + 0(7
2
Equivalently, since
1 (n + 1)(n + 2))hm+2) + //nnn 1) (22-2)
A h,,
that the operator rotates Ih,,) in the direction of (/++2) and (hn-2) simultaneously. This explains our previous statement that A rotates (hx) further and further away, towards (/xc).
Now, for any two function f.g. have
(JT, [[C--nWKKKs)/T--OOOOCCCC...
/1
where the transformed kernel is
K,(,, v) = e² eee-" - - ( x,eee)
Consider the previously solved case of K Kr. Plugging in, we find that T, KT; an integral kernel operator with kernel function
2r -
+ e 2
2r
Ke,r (z. y) = e² /tanh(t/2)exxp exp
(x + x2) + 2 sinh t ay
4
4sinht
To match the target form K(x, v) = expl
(x y)2/(202)).
2r
e²r 1
4 + e e
2 sinht
4sinht t
202
Eliminate 27 and solve for t, we have 0² = + +__ - 1, that is.
2² 4sinh (t/2),
t 2 arrsnn (a/2)
Plug it back,
2sinht
tanh(t/2) / 11+ 4
2T
45

---

Published as a conference paper at ICLR 2026
So the prefactor simplifies to e" /tanh(t/2) 1, hence
(x - y)²
(1+
(+
(z, = exp
)
t = 2 Pasinn (a/2), ==
- In
20²
4
The diagonalization of K,T is
TKKIT = E11 ") "TT (1n))) (hnl
Thus, the eigensystem is eigensystem (1, K) = {(1 e e- Tr hn) n = 0,1,
At the limit, we have
2 l 2/0 1 T= 20 0 -
Now, the Hermite eigensystem corresponding to é - is HE HE (cn)) with On = o -2n, so we just need to check that eigensystem (u, (H, K) (1,(1, (cn)), which is true:
(1 --- =1 -1-(2n + 2) - + 1 4 +,
Cn
n2 +n+1 =
arccos (h,, (hm)
+ 0 1) + +0
2
Not only do we see the convergence, we also see that, for any fixed n. the rate of convergence is on the order of no-= 2 nc4+1/c2. We will show in the next few sections that this a generic phenomenon.
In general, if a kernel has coefficients cr decaying at a rate of e, then the n-th entry in the kernel's eigensystem converges the corresponding n-th entry in the Hermite eigensystem, rate of (c). The constant in O(e) increases with n, so that the convergence is not uniform. The higher-order entries converge slower.
1.2
PART BONUS
We can diagonalize K(x,8) = e///² in the same way:
1 In
(1 4
(1
1 K(r,y) = (1 21-2/02)-172 1/2 / (x. t arcosh (d2/2), 4 o+)
Thus, its eigensystem is eigensystem(14 K) - ((1-2/02) 2/02)-1122(1 - 6 7 Th(bi) : n 0, ..
At the o - oc limit,
t= 2ln o + 0 8), 7= -= + 0
yielding
(1 E --- = 1 + (n + 1) - + 08)
On
arccos (T.,ITT (ha) = - n2 + +n+11 o 0
This case is special, in that the convergence is on the order of n m(ce+1/ )22)2 by one order of magnitude than the generic case.
which is faster
To understand this, directly expand the operators. The operator for exp(- y)2/200 has expansion
Kexp(- (a-p(-(a-y))2000 I + o ((hi M3) + 0(aa-)) where we that the multiplication operator M, is self-adjoint, with expression
M Σ Vn (hm, vn + 1/hb)) (hn+1l
Because M3 is not diagonal in the Hermite basis, the operator Kexp(-(x-p)) (2- /202) is not diagonal at the o order, and perturbation occurs at that order.
In contrast, the operator for exp(ry/o²) has expansion
Kexp(ew/oF) - - (h1 - ((h2) ( 22///+211/( + 0
Therefore, it is not diagonal at the a order, and perturbation occurs that order.
46

---

Published as a conference paper at ICLR 2026
1.3 PART 2
We take its product, to solve the problem for (2),, where NN la).
le vl? 20
The kernel ((x, y)
decomposes into product of kernels:
(x y)
II
Therefore, its kernel operator decomposes into tensor product of kernel operators:
K K
1=1
Tr (han
aEN f=1
Σ
tyde 1 1ally (hal
aEN!
So, its eigensystem is At the a + oc limit, using the previous result, each eigenvalue converges as
[(1 (1----)dd-la)) lalt, Iha) a ENN
e ") (2|al + 2d)o +0
C|ai
and each eigenvector converges as
Ee (a ta, + 11 0- 0
arccos(hall) (ha) (halI
1.4 PART
We solve the problem for (p),,,, where μ No0,, E), by taking an opportune unitary transformation
V : (NN(O + (O, Ia)).
As previously stated, if T Σ. then (3(N(0,))) (3, (a)) defined by (V))))= f(Mx), (V' f)() f(M-1z)
is unitary.
lie-y1? and
Now, define the operator using the kernel function K( y) mation, its kernel becomes
With the unitary transfor-
u) Mr Mie mi
(VKV*) (x. 8) (MMx, My)
2
Therefore, the kerne decomposes if M M is diagonalized. This can be solved by taking the SVD of the covariance matrix as Σ UTU where T diag (?1,..., 7a), then we can
M = UT2/2
so that VKV* has kernel
( 2(1/v15)²
II 1=1
e
Thus, VKV* diagonalizes as
VKV* Σ ( -i--e--he- 2e aat 0d_ (80 Tr Iho
QEN
47

---

Published as a conference paper at ICLR 2026
where T. are defined by
t 2 arsinh (a/2/7), In (1=
1
47
Now, we convert this back to K to obtain
K I - e aatiaai of Tú Mo, 8/ Tr, (ho)))
QEN 1m1
At the limit of a + co, the eigenvalues converge to
II e Je-
0 2/a II %/
(1 (1-
(2/aa +
rate of 2 As before, the eigenvectors converge to V*(ha) at rate of / Ed Ei (aftattt 0-2 Since
ha*)))(<=)) = ha (T U x)) 11 (2) (x)
the theorem is proven fully.
Similarly to the case in Appendix 1.2, the kemel K(x,, y) 6 v/o² converges to the Hermite eigensystem at a rate ((a one order of magnitude faster.
48

---

Published as a conference paper at ICLR 2026
J PROOF OF THEOREM 2 IN ONE DIMENSION
In this appendix, we prove Theorem 2 in the special case of one dimension. The general case is proven in Appendix K. The proof of this case is casier than the general case since there is no multiplicity. The ideas in the proof would be reused in the general case.
Appendix J. a reference sheet quoting several theorems we need for the proofs. The reader can skip it and refer back when needed. Appendix J.2 states Theorem rigorously Theorem 5, then shows that a special case of more general theorem (Theorem 6). The next section proves the general case. Appendix J.3.1 shows that the cigenvalues of the kernel converge to the desired form with relative error decaying at a rate O(c) Appendix J.3.2 leverages this to show that the eigenvectors also converge to the desired form at rate of O()).
J.1 SETUP
We need quote some big-name theorems for later use.
We will need to cut up the spectrum of an operator into segments, each falling within an interval. The following theorem allows us to construct tight enough bounds on the intervals. It special case of the general Courant-Fischer-Wey, min-max principle, strong enough for our purpose. Our special case avoids the part about essential spectrum, which makes the general statement inconvenient to use.
min-max principle). Let A be compact, positive semidefinite operator over a Hilbert space H. Let its eigenvalues be enumerated as X1 Z X2 2 ... 2 0. They can be finite infinite. Then,
Theorem 3 Fouuratt-Fisher-Wae
d max min (s|A[z) MCH ZEM M= ||||==1
(51)
min max (x|A[x) MCH =EM- M=k-1 ||||=|
(52)
Proof. The second equation is (Teschl, 2009, Theorem 4.10). The first equation is proven by essentially the same technique the finite-dimensional case.
Let U1, u..... be its cigenvectors. If we set M to be the span of {uil..., then we have
A min {x, Az)
SEM ====1
So it remains prove the other half.
For any subspace with dim M = k, must have a nontrivial intersection with {ok, Uk41.... }. therefore, there exists some unit vector a E M,, such that it has decomposition i2z a.V. With that, we have
(a|Ax))
Σ |a//2t 12k
S Σ Jai1ae = A
12.
The min-max principle has corollary that we will use, more convenient than quoting the full min-max principle.
Corollary 1 (Cauchy interlacing law). For any n x Hermitian matrix An with top left n 1xn-1
minor An-1, then
Aet1 (An) S Xi (An-1) S Ax (An)
for all 1 < i < n. (Tao, 2012, Eq. 1.75)
After bounding the eigenvalues, we will use the second theorem to bound the eigenvectors. However, need something more, because need bound the eigenvector rotations of segments of the
49

---

Published as a conference paper at ICLR 2026
spectrum, and the segment may be badly separated within, even though it is well-separated from other segments.
Therefore, need to handle the rotations of reducing subspaces, not eigenspaces. A reducing subspace for an operator A is a closed subspace V. such that A(V) C V. For self-adjoint operators, the reducing subspaces are direct sums of eigenspaces. In partieular, the span of an eigenvector is reducing subspace.
Given segment of the spectrum, A (AA,, define VA as the reducing space of A. For example, A = (E), then VA is the closed span of all eigenvectors with eigenvalue E. We also define PA as the orthogonal projector VA-
The following theorem shows that, if the operator spectrum split into two parts mutually well- separated by S2(1), then their corresponding two reducing subspaces would each only rotate by O(e) under an operator perturbation by (
Theorem (Davis- sin theorem (Davis & Kahan, 1970)). Let A, be self-adjoint operators such that
(A) is partitioned into Ao, A1
σ B) is partitioned into Ii
The spaces VA Vr,
the dimension. Similarly for VA Vr
Au contained in an interval [z. yl.
Ii disjoint from the enlarged interval (x - d, 6).
Then there exists a self-adjoint "angle" operator O, such that the rotation operator
cos θ sin O
rotates VA, to Vr, for 0, 1. Furthermore, the angle operator satisfies
sin θ cos θ
|sin θ s | B||
(53)
for any unitarily invariant norm ||-|.
Intuitively, the operator θ is just diagonal matrix of angles, in suitable orthonormal basis. The cos θ sin θ
operator - -in cos + performs simultaneous rotation in many (potentially infinitely many) 2- dimensional planes, such that the two reducing subspaces of A are rotated to two reducing subspaces of B.
J.2 REDUCTION TO A GENERAL CASE
We clean up the form of Theorem 2 by performing few WLOGs and reductions into Theorem 5, so that deduce the theorem corollary of general Theorem 6. Alternatively, the theorem can be proven by proving the more general, multidimensional case. This is done in Appendix K. However, may be worthwhile study the following special before reading the more general case, since most of the proof ideas are present.
We begin with convenient definition.
Definition 5 (fast-decay). A real-valued sequence cp, Cl,... is fast-decaying iff there exists number e E [0, 1), such that c,+1 I EC,, for all n N.
As in the proof of Theorem in Appendix we perform unitary transform of L3 7)) to (A, 1))-
Next, we define a, (2n D!!! so that
K =
Σ an un (val
By Stirling's approximation,
(2n
1)!!
2n
2n
(1 + 0(1mn)
= Tn
n!
2n
50

---

Published as a conference paper at ICLR 2026
Therefore, if Cn is fast-decaying with parameter then on is fast-decaying with parameters 2e, Slow.n/ n.. So, we can study the kernel Σn On (n/en)(U)) with the fast-decaying condition directly imposed on an- This makes the notation cleaner.
Because (hn) to an (v.((
xe! 12n-1)1 (see Appendix H.8), convergence to is equivalent to convergence
With that, we can we restate the theorem we wish to prove, more rigorously:
Theorem 5 (The HEA holds for fast-decaying kernel on ID Gaussian measure). Lel μ (N), be the standard Gaussian measure, and let
K
an anl
1=0
be dot-proode dot-product kernel with fast-decaying coefficients with parameters then for any N. there exists an eigensystem of K, written as (Aa(K), (oo))))))))))))))))))))))))))))) ( (K))) (K)))...., such that
An(K) = 1 + O(c)
an (v hn,)
((ux((K)) (mm))) O(c)
as E > Furthermore, the scaling factor in O(e) depends only on the Gram matrix of the vectors (uo)..... ................................ (un).
The above statement may seem oddly convoluted with "for any E N, there exists...", ", but this is necessary, because the rate convergence is not uniform over the sequence. In general, higher-order eigenvectors converge slower than lower-order eigenvectors, which means the constant in the O(e) terms larger for larger n, and no uniform-convergencc rate exists.
The scaling factor in O(c) measures the speed of convergence for the n-th eigenpair. It is slower if the Gram matrix of the vectors (o.)...., (2n) is ill-conditioned, because in this case, the vectors are almost linearly dependent.
Indeed, the Hankel moment matrices most commonly used probability distributions, including the uniform distribution, the gaussian distribution, and the exponential distribution, are exponentially ill-conditioned (Chen & Lawrence, 1999). Therefore, we should expect the constant O(c) to grow exponentially with
Also, take note of the phrasing "there exists an eigensystem of K denoted as (Ae(K), (uu(K)))) because allow K to suffer multiplicity. In these cases, the corresponding eigenspace would have more than dimension, and therefore there is freedom in choosing any orthonormal basis of the eigenspace "the eigenvectors". The theorem states that, despite the multiplicity, there exists good choice of eigenvectors, such that they make small angle with the canonical eigenvectors (é.). This will become especially relevant in the proof of the multidimensional generalization in Appendix
Because the orthonormal basis (ha), [(z),... ... is obtained by Cram-Schmie orthonormalization on (vo), ) (i)...., we can generalize this time with all epsilons and deltas place for maximal rigor:
51

---

Published as a conference paper at ICLR 2026
Theorem 6. Let:
1. (uo),|ui>, lui)...... be a sequence linearly independent unit vectors in a Hilbert space, such that their closed span is the whole space;
2. (o))...).... be the sequence obtained by performing Gran-Schmidi process the sequence:
Then, there exists a sequence of constants Co. CI....,> and Eo, 61, > O. such that for all E N, c (n) and all oo; 01,... fast-decaying sequences with parameters there exists eigensystem of the kernel K = -n=o === anl (n) (Val. denoted as (Nu(K), 0y (K)))) such that
(k) E (nl(@n//n)) (2) (1 CCE)
and
Ke(een (K)), (o,)) S Cne
Furthermore, the scaling factor Cn and the bound Cn depend on only on the Gram matrix of the vectors (u0),...,,uy,
Intuitively restated, the theorem says that as e - 0, the eigensystem of the fast-decaying kernel En 0g ()))(( (vxl rotates towards the canonical eigensystem at rate of c.
The proof has two parts. The first part uses the min-max principle and lowest-order operator
perturbation (commonly used in quantum mechanics), to segment the spectrum of K into small intervals of the form
An(K) E an (o.l
In particular, since a, are fast-decaying, it shows that the eigenvalues are exponentially separated.
The second part applies Kahan twice, using this exponential separation of eigenvalues, to show that sin (K),, [K)) Oc)) and sin <(u,, (K)), (e.)) O(c), for cleverly-chosen operator K.
Before we launch into the proof, we should look at simple case that explains why this should be true.
Consider the case of two dimensions. We only have (uo), /t1)- In this case, the kernel K ag (o)lo)>< (vol + a1 (vyl. Diagonalizing the kernel is equivalent to finding the major and minor axes of the contour ellipse defined by {[z) (x K|x) = 1}. This ellipse is the unique ellipse tangent to the 4 lines defined by (v) x>)
Suppose we fix ag. and let 01 + 0. Then, the lines of op [0)|=))2 = remain constant, but the lines of aj (u [x)] semiaxis rotates to become perpendicular to the two parallel lines, i.e. parallel to Jvo). Therefore, the eigenpair converges to (oo) (6n)).
diverge to infinity. The ellipse degenerates to two parallel lines. Its minor
Suppose we fix a1 and let converge to the origin. The ellipse degenerates to two line segments. Its
Then, the lines of an (m1
remain constant, but the
lines of ap (22 major semiaxis rotates to become the same that line segment, i.c. parallel to aol (volz))2 1, i.c. perpendicular to (o).. Therefore, the eigenpair converges to (a1 ((] (01)).
Intuitively, we see that for given the effect of all an+1 4n+2.... terms in the kernel is small perturbation on the n-th eigenspace, and negligible because the parallel planes diverge to infinity. The effect of all 0g-11, 0n-2, ... dg is large but fixed perturbation. forcing the n-th eigenspace to be perpendicular to all of 1 ..... [un). but once that done, their effects are also negligible because the parallel planes converge the origin.
52

---

Published as a conference paper at ICLR 2026
(a) The of constant do, and a1 + 0. The cllipse degenerates to two parallel lines.
(b) The case of constant d1, and dg oo. The ellipse degenerates to two repeated line segments.
Figure 22: Diagonalizing the kernel in 2 dimensions the 0₁ /ag 0 limit.
J.3 PROOF OF THEOREM 6
J.3.1 PART
To show: (K) (fm O(e)).
Proof. If On = 0, then all An, Ant1.-... = O, and the kernel K becomes finite-ranked, with range Span ((00m-1))) ))). So the theorem becomes trivial. Otherwise, assume an 0, which means that all 0p,..., Un > O.
We apply the min-max principle to obtain upper bound of the form X, (K) S a, ((x (e)) and a lower bound of the form An (K) 2 a. (6, ((1+O(()))) thus completing the estimate.
For the upper bound, we use V Span( (0) then
An I
sup
(or K|z)
sESpan([vonn ||=|==1
1))
ak 1
sup
#ESpan( (rooaann//oniii Voon- ))>
k=0
||=||=1
sup rrSpann (aroo)) 1) k=n
axl (x|
[x] =1
20
sup #eSpan () [x =1
an anlKo/ 2
sup
Σ k=
axl (x)(2)1))12
SESpan on 1) ==
= =0, (2,)))))² + Amax
Σ 1mn+1
as (x)) (vul
5 <0n (un)) + Tr
ax (w) (val
k=n+1
=an (2,)) + Σ ak
k=
= <0, (2,,) + a, (())
= -a (0n (e,,) (1 O(e))
53

---

Published as a conference paper at ICLR 2026
where the step Amax Tr is because all oę O. Though unnecessary, we can concretely write down the upper bound as
An S (0nl0nlo Cc)
where
C = (ūnl unn)?
kmnt1 OnE
1(8m|uns) -
For the lower bound, use V Span then
An 2
inf
(xr) ()))
=ESpan((eonn))) ||[|=1
inf #Ivo.)( |e||=1
au (x/kv))))
K=
inf #ESpan([eun))
(x
|||||=1
The quantity is standard problem in quadratic programming, with exact solution Amin AG where A = diag( (An...., a,)) and G ((usluy)) is the Gram matrix.
To see this, write x = Ejeoin Uju then
| = cT
Σ an (o - A(G) k=0
= c
So the constrained minimum of GAGe equals the smallest eigenvalue /a/2AG2/2 by the Rayleigh-Ritz principle.
o" Ge
Let M = /1/2 We invert the matrix to use standard operator perturbation theory:
n-
M
Un un
up ug
an
ag
A=0
where Uı G-1/2ea is the k -th column of G-1/2 The perturbation EnE 1 uxuu is order O(e) as
compared to the unperturbed part 1
Un u
an
The unperturbed operator has maximal eigenvalue perturbed operator has maximal eigenvalue:
|u,]l" with eigenvector ún == un/ ||- The
|u,ll
+
Σ
àn ((e2)
an
ak
Inverting the eigenvalue,
Amin /2 = an
On an 1 2, pm
On
(1 + O(e))
|un 1|
[mn 1|
||,,,|1
Now, ||u,,.] = 2 G en, and G-1 is the Gram matrix of the dual basis of (vo..) in Span((vo..)).
In particular, because (ū,) is perpendicular to all of /u--1), the n-th dual vector is just (8.) (vwl0w))
Therefore ||u,ll
1
Re.le.)] and we obtain the desired lower bound
An 2 (6n + O(e))
54

---

Published as a conference paper at ICLR 2026
Some comments the constants in O(c).
In the above proof, we constructed an upper bound an (2)(1 + O()) and a lower bound (0, (1 O())).
The constant in the upper bound is
(6 vn
which depends on [6n/ (,)l1 sin? where 9 is the angle between (e,)) and Span((een-))). We see that the bound is pushed wider when either the coefficients become less strictly exponentially- decaying, or the vector (v,) leans into Span((vo.>-))), and thus becomes less orthonormal.
The constant in the lower bound is
Un 2 12 únl
||u,Il 1 Un! 1
=vnnl (un) 11 Uhy
Ke (0n) (G )²
Similarly to the previous case, G gets larger as the vectors |vo), ................................ .......)) get less orthonormal, which worsens eigenvalue convergence.
J.3.2 PART 2
Proof. If dn 0, then we can trivially select the ni-th eigenvector to be (a)). Otherwise, have d0:-.. Op > 0.
By the eigenvalue bound (that is, Part of the theorem), the spectral gap around (K) is min (K)( (y( (i.l(im (3 + O(e)) Negn
Define the truncated operator K = En anluk)(ukl By
2
ssin (vn(() Un (R))
KK 1K-Ki |K
an kū (n) (1 + O(c))
2
Tr K - K
an Kün (n) (1 O()))
2
0
Kn (u (1 + O(e))
a#
km
= O(e)
Thus, we need only bound sin (v,, (K), 6.)l-
Because K lives inside Span([vo..)) ), we thenceforth restrict the Hilbert space to just Span((vo:.)))
Define the wwice-truncated operator K Ik= as (u) (rx). The eigenvalue bound applies to its first n eigenvalues, and its (n + 1)-th eigenstate is the ground state, with eigenvalue 0 and eigenvector (ê.).
Thus, the spectral gap around its ground state eigenvalue is
min (K) (k)) = ( 11
Nemm
By Ravis-Kahan again,
sin ((v, (R), (K),0,)] [-]]= sin ((,, (K), [K))
2
K - K llop
16,
Up
1 + (()))
2
an-1l 66 Un 1) ()(+)((())) 6
O(c)
55

---

Published as a conference paper at ICLR 2026
There are two occurrences of O(e) in the proof. Both can be bounded explicitly, to show that they only depend the Gram matrix of , (U,),
in Part 1.
The first (e) has explicit upper bound constant
1 1
Σ
an an (n,)) O()))
(( c + O
k=n+1
where the remaining O(c) in 1+0(e) came from Part 1, which as we showed in Part 1, only depends on the Gram matrix of (oo):.... ..... (un).
The second O(e) has explicit upper bound constant
Hn (
where the remaining (E)) only depends on the Gram matrix of (oo).... (nn1))
56

---

Published as a conference paper at ICLR 2026
K PROOF OF THEOREM 2 IN THE GENERAL CASE
In this appendix, we prove Theorem 2 completely. The general idea is to modify the proof given in Appendix to account for multiplicity.
Appendix K.I presents the overall plan of the proof. Appendix K.2 sets up all the machinery needed to handle multiplicity in eigenvalues and eigenvectors, which is new occurrence in multiple dimensions. Appendix K.3 states the theorem in full rigor as Theorem 7. The next two subsections prove two lemmas that apply generic operators, not just an integral kernel operator: Appendix K.4 shows that the eigenvalues of a generic fast-decaying kernel splits into segments that are exponentially separated, and Appendix K.5 sharpens this separation into proving that the eigenvalues in the N segment are only slightly perturbed by all the other segments. Appendix K.6 specializes to the case of dot-product kernel, showing convergence of the eigenvalues, and then leverages that convergence into the convergence of eigenspaces.
K.1 PLAN OF THE PROOF
Let K(x, y) = En= (
y)" " be dot-product kernel with fast-decaying coefficients Cn.
As in Appendix 1.4, study a spherically symmetric dot-product kernel over a nonstandard Gaussian distribution N (00, Σ), we construct whitening unitary transform V L3 (O, Σ)) - L2 La). thus converting the problem to solving for the eigenstructure of spherically asymmetric kernel over the standard Gaussian distribution.
Let the SVD of E be UTUT, where r diag (7,.... Ja) with N...... 2 Define V by (v)) f (MMa). This then converts the operator K to VKV*. The operator V VKV* is a kernel operator with kernel function satisfying
VVKV)(ZZB)
(1a131 + ................................ (aaaya)"
n!
n=
We will prove that the eigensystem of V VKV* converges to
d {( Gjal II 7f" Iha)
for all a e No
==1
as + Then, by reversing the transform, we find that the eigensystem of K converges
{(a Clal II 7 1=1
for all a Nd
as desired.
We eliminate pesky special case: one more of ",.... Td may be equal to zero. In this case, V VKV* may not be positive definite, but merely positive semidefinite, which annoying. For example, what if 72 7/4 0? Then the operator V V'V splits to two halves. It is the zero operator on Span (e2, e4), and it is positive definite on Span (ε1, 63, , ed). Then we can separately prove the eigensystem convergence the two halves, and take their tensor product. The case of zero operator is obviously trivial, since its eigensystem is just
(0, (((a)))))) for all (ag, a4) E N
Thus, WIOGG we need only consider the case where 71....; 7d 0.
We note that, at least in one case, the theorem has been proven: If c, o- for some a, then it is just minor variant of Theorem which has been proven in Appendix I.2.
Thus, if we prove that the difference between the eigensystem of VKV* and the eigensystem of ce T 9/00 vanishes
0, for some well-chosen values of a, c, done.
This cannot be done directly, once again due to nonuniform convergence: The higher-order parts of the eigensystem is wilder, and harder to control. To bypass this difficulty, divide and conquer.
We prove that the cigensystem of KV* is "segmented" into exponentially separated intervals, such that each segment is e-insensitive to perturbations in all other segments. This allows show
57

---

Published as a conference paper at ICLR 2026
that, for any fixed No, the n-th segment of eigensystem (VVV*) corresponding the term on Ty)" converges to the n-th segment of eigensystem K the n-th segment of eigensystem( K (ry)) converges to
ceste Try)), where c = Cx Since
{
78 IMta) for for a E No. |a||
the theorem is proven.
K.2 MACHINERY FOR MULTIPLICITY
The main difficulty, compared to the one-dimensional case, is that we must directly handle the multiplicity of eigensystems. By this, we mean that in Rd, the Hermite basis is longer of form [ha))eeN but rather, (1/aa) lagrea. This creates degeneracy, that is, Σ 0z = Σ, o/ then Iha), ) belong the same eigenspace.
Concretely, define the OrsseeinUUllebeeck operator - x- V on (ua). In the d = case, its eigenvalues have no multiplicity, and its eigenvectors are precisely the normalized Hermite polynomials {Ihn) hed::.. In the d > 1 case, its eigenvalues suffer multiplicity, Its n-th eigenspace is (1/a)) ax| = neN" with ( dimensions.
This multiplicity is inescapable, because the Meastein-Uhlenbedd operator is spherically symmet- ric, and spherical symmetry inevitably leads to multiplicity. In our case, the dot-product kernel En al (x ry)" may have some entries of I equal, which leads to (partial) spherical symmetry, and thus multiplicity.
As more famous example, the spherical harmonics in I,2 (TEd)) are the eigenvectors of the Laplacian operator V2. Due to spherical symmetry of the operator, its eigenvalues have multiplicity, thus it splits (Rd) into eigenspaces. The nith eigenspace is spanned by (mn+dd2((n+d3))) degree-n homogeneous polynomials.
(d
Let's consider the prototypical case that we want to study: the convergence of dot-product kernels to the Hermite eigensystem. In Rd there are (=d-11) degree-n monomials, and ("+d-1) degree-n Hermite polynomials. To obtain the Hermite polynomials, we cannot simply apply the Gram- Schmidt process on the monomials individually. Instead, we need to apply the Gram-Schmidt process simultaneously on each segment of (n++d-)) monomials, to obtain the dimension spanned by the degree-n Hermite polynomials.
("massiioonnn111)) ("+--1) subspace
d-1
To count the multiplicity, we function m N NU (oo). It should be interpreted saying that the n-th eigenspace has dimension m(n). For example, the multiplicity counting function for the operator over (2(a))) is m(n) ("
Note that m does not need to be strictly positive. That is, we allow m(k) = 0 for some k. We even allow Σe m(k) be finite, in the case that the Hilbert space under consideration finite-dimensional. although we require Σ; m(kk > O, for otherwise it would be completely trivial.
For convenience, we will from now on assume that m(k) > for all k, since we do not need more generality. The reader who needs this generality can read the next few sections and mentally generalize the constructions.
The most important condition on the multiplicity counting function is:
Definition (polynomially bounded multiplicity). A multiplicity counting function is polynomially bounded iff there exists some A, d such that m(n) < An for all E N.
This is satisfied by the Hermite basis in any dimension, since its m()) O(n
Given a multiplicity counting function, we define a system of vectors that it counts: Definition 7 (vector systems with multiplicity). Given multiplicity counting function m, a vector
system with multiplicity m is an indexed set of vectors of form [VR.) k E N, E [1 m[k)])-
As in the last few sections, we will only consider vector systems that consists of linearly independent unit vectors, and such that the closure of their span is the entire Hilbert space.
58

---

Published as a conference paper at ICLR 2026
Similarly, define system of coefficient it counts:
Definition 8 (coefficient systems with multiplicity). Given multiplicity counting function m, coefficient system with multiplicity m an indexed set of real numbers form {ok,1 l N, E [})]]
We next generalize the Gram-Schmidt process handle multiplicity.
Definition (Gram-Schmidt process vector systems). Given multiplicity counting function m, and a linearly independent vector system {#k. k E N, [ mm(k]) we define the Gram-Sehh -rh process the vector system by the following algorithm:
1. Construct an arbitrary orthonormal basis of Span( ..., (vo,)(o))) Call them ....))..... (0))
2. Select the next smallest h: such that mmk) > 0, and project each of 1u..1)..., (()) to Span (1 1 orthonormal basis of their span. Call them (k.1)..... (kk))))))
m()))) to obtain (ok,1)--... 1 mas) then construct an arbitrary
3. Continue this way inductively.
Note that the CrammSchmiin process is not uniquely defined, due the steps where ar- bitrary orthonormal bases are chosen. However, it constructs sequence of subspaces {Span (16,,1).... (x))) M00::0. which are uniquely defined.
Also note that even the traditional Gram Schmidt defined, because each ig could have been -g instead. That is, there a (-1,+1) ambiguity per step. Now, note that {-1, +1} is just O(1), the orthogonal group on R and we see that it is general phenomenon: In general, the Cram-Schmidt process with multiplicity m creates an ((m(k)) amount of ambiguity at step k.
Gram-Schmidt process, without multiplicity, still is not uniquely
Each vector system defines a positive semi-definite kernel
mik) axa (wu,l
for any indexed set of non-negative scalars (ve, N,I E [1: m())]) provided that all ax,1 2 and Σx. dz.1 < co.
To handle the multiplicity of eigensystem K), we need to make four changes.
1. Generalize the definition of "fast-decaying coefficients" to fast-decaying segments of coeffi- cients.
2. Prove that segments of udjacent eigenvalues are exponentially separated.
3. Prove the convergence of reducing subspaces (i.e. direct sums of eigenspaces), rather than eigenvectors.
4. Prove the convergence of whole segments of eigensystem( (K), rather than individual entries like (A, (K))).
A fast-decaying sequence of coefficient segments with the specified multiplicity m is obtained by slightly loosening a fast-decaying sequence coefficients, so that instead individual coefficients, it is segments of coefficients that are now decaying exponentially. This will force segments of the eigenvalues be well-separated as well, and thus their corresponding reducing subspaces.
Definition 10 (fast-decay with multiplicity). A coefficient system Ck,1 is fast-decaying iff there exists sequence of numbers Stow. (0, 1], and number e [0, 1), and sequence of numbers č. such that
Cn,t E Otow,n En), in+1 S etn, Vn E
We say that such system is fast-decaying coefficient system with parameters (c, dlow, Cn):
59

---

Published as a conference paper at ICLR 2026
For example, fast-decaying sequence is fast-decaying system where the multiplicity counting function is m(k) (k) = 1, and all inow,n = 1. We will show that the coefficient system of a dot-product kernel Σ n! æ Tyy is fast-decaying in Appendix K.6.
Given polynomially bounded multiplicity vector system for m, and fast-decaying coefficient system, define
EEEE 0 (a.)) & K
positive semidefinite and has finite trace. Therefore, its spectrum is discrete, and except for zero, each of its eigenvalue is positive and has only finite multiplicity. Therefore, its eigensystem is well-defined.
Definition 11 (eigensegment). Given K, a positive semidefinite operator with finite trace, enumerate its eigenvalues as A,, 2 ... 2 A0.)(0) 2 \1,1 2 ... 2 0, counting eigenvalue multiplicity. Construct corresponding orthonormal eigenbasis (u,,))-
If all .n......,An,m... (n,)(n) are distinct, then the n-th eigensegment of eigensystem K) is the set {(An.t. Span (Ipm,)))) L [1 m(n]}} Otherwise, if A Xn,2, and all others are distinct, then the n-th eigensegment of eigensystem(K) is the set
{(An.1, Span (Ivx,1), (n,22)),, (An.2. Span (Iv,,1), (ww.))))) Span ((u,,))) : [3 m())]
In general, the eigensegment is obtained by merging degenerate eigenspaces.
Despite the valiant effort in removing ambiguity, the above definition still has some residual ambiguity: If unluckily, Ak.m(()) 7,1 then the reducing subspaces of the k-th and (k+ 1)-th eigensegments not uniquely defined, since rotate the eigenvector pair [vx+1,1), (*k,)(()) arbitrarily.
Fortunately, we will demonstrate that the residual ambiguity disappears in the + 0 limit for fast-decaying kernels.
Finally, we need to define what means for two eigensegments to be close together:
Definition 12 (eigensegment bulk closeness). Given two eigensegments of equal length, let An.1...., mn.((n) be the eigenvalues from the first segment, and X,, X,,m(n) from the second. We say that they are e-close in bulk if
N,,,,
Dm, - X,,1l < é miminnnan X,,1) VI E [1: [1:m(p)) m(n)]
In bulk? Indeed, due to the annoyances of degeneracy, we would first show that the eigenvalues converge (c)). After that is done, to match up as well, and thus does bulk closeness resolve into detailed closeness.
small enough that it will force the eigenspaces
Definition 13 (eigensegment detailed closeness). Given two eigensegments of equal length, say that the two eigensegments are e-close detail if they are é-close in bulk, and for each eigenspace V' in the second eigensegment, there exists one or more eigenspaces Vi,...; V, in the first, such that
cos θ
sin θ
there exists unitary angle operator O such that
sin θ cos θ rotates Vi V to V', and
sin θ Ollop <.
See Appendix J.1 and (Davis & Kahan, 1970) for details on the meaning of the angle operator.
cos θ sin θ
Intuitively, the operator sin θ cos is the generalization of multidimensional rotation to
Hilbert space. It performs simultaneous rotation many (potentially infinitely many) 2-dimensional planes. To say that sin O opp < means that in every single one of these planes, the angle of rotation is < arcsin(c).
The definition is by design asymmetric, because we will show that if one source eigensegment (think of the dot-product kernel's is eigensystem) is always O(e)-close to a target cigensegment (think of the the source eigensegment will be forced to be
Hermite eigensystem) in the bulk sense, then (cc)-close to the target eigensegment in the detailed sense. We would rather not hit a moving target with static gun, but hit static target with moving gun.
We point out that even "convergence in detail" does not imply convergence of every and each eigenvector, because degeneracy in the target eigensegment may stubbornly remain broken in the
60

---

Published as a conference paper at ICLR 2026
source segment. For example, it is possible that X, X, exactly in the target eigensegment, but An.1 # An.2 in the source eigensegment. In this case, the eigenvectors corresponding to An,1, An, may be rotated by 45 compared to the chosen eigenvectors for X,, N,,2.
Concretely for our case of the dot-product kernels, this means that the kernel may have no degenerate eigenvectors, but the Hermite eigensystem has degenerate eigenvectors. In such case, the best can possibly do is proving that each eigenspace of the Hermite eigensystem corresponds to direct sum of the kernel's eigensystem that is small angle's rotation away.
Concretely, suppose that we have = 72, then the Hermite eigensystem is degenerate, but we may find that the kernel's eigensystem stubbornly remains both nondegenerate and rotated by 45 askew of the Hermite basis. For example, it might stubbornly insist on containing two non-degenerate eigenvectors close to V (1h(o.1) + (A(1,0))) and / (1b(o.n) - (h(1,o))). This is fine, since their direct sum does converge to Span (1/(o.1)), (1(1,,))), and that is the best that can be proven. One cannot expect more be proven given such degeneracy in the target eigensystem.
In the case of Theorem 2, before proving it, we saw why it should be true using a 2-dimensional picture with ellipses (Figure 22). Here, we can also see why it should be true using 3-dimensional picture with ellipsoids.
Consider the case of three dimensions. We only have 1) (1.1), (112). In this case, the kernel
K 40,1 () + 41,1 (m,,) finding the principal axes of the contour ellipsoid defined by {|x)) [e|K(a) = 1}. This ellipsoid is the unique ellipse tangent to the 6 planes defined by (M,0) = 1, 1, 1...1.11.a (vi,1
| + 21,2 (11,2)- Diagonalizing the kernel is equivalent to
1, 2...2/11.2) (v1,2) 1.
Suppose we fix 01,1, 01,2, and let 40,1 - O. Then, the planes of a1,1 (e, 1, (1.2/11.22 (V1.2l = remain constant, but the planes of oo.1 (vo.1 1 diverge to infin- ity. The ellipsoid degenerates parallelogram prism defined by the planes. Two of its principal axes rotate to become perpendicular to the pairs parallel planes, and essentially ignore 00,1-
fix a1,1, 01,2. and let 60,1 1, 201,2/11.2 (V1,2l 2| = remain constant, but the planes of ao,1 1) (Vo.1l = converge to the origin. The ellipsoid degenerates two flat parallelograms. Two of its principal axes rotate to fall within the parallelogram, perpendicular to its 2 edges.
Suppose
Then, the planes of a a1,1 (u.1)vi.))
that for given n,, the effect of all 1,+1,1,-.. @a+1.m(nn 2,,,, terms in the kernel small perturbation on the n-th eigenspace, and negligible because the parallel planes diverge infinity. The effect of all an-1,m(n-1)) 1), 1.=-1mmm=-))-1- perturbation, forcing the n-th eigenspace to be perpendicular to all of |2,-1, m(n 1)),.... (oo.)) but once that done, their effects are also negligible because the parallel planes converge to the origin.
Intuitively,
a0,1 a large but fixed
61

---

Published as a conference paper at ICLR 2026
(a) The case of constant 01,1, 01,2, and 00,1 + O. The ellipsoid degenerates to a parallelogram prism.
(b) The case of constant 01,1; 01.2, and 00,1 + oc. The ellipsoid degenerates to two repeated parallelograms.
Figure 23: Diagonalizing the kernel in 3 dimensions limits.
Figure 24 shows the eigenstructure of K. On the coarse level, it divided into exponentially separated segments. The N-th segment contains m(N) eigenvalues clustered within interval with order of magnitude ((āv). As e + 0, the segments become ever cleanly separated, and also converging closer and closer to the .-th segment of target eigenstructure. The target eigensegment may contain multiple eigenvalues with varying multiplicity. a target eigenvalue À has multiplicity then there will be precisely 3 eigenvalues (counting multiplicity) falling within A(1 + ((c))
Notably, these eigenvalues may be degenerate, or not degenerate. In either case, the direct sum of their eigenspaces will have the same dimension the eigenspace corresponding to X, and it will make an angle of size (e)).
spectrum of K
0-th segment (8p)
1-st segment ((a))
N-th segment ~ (
0
A
(N)
(axe)
multiplicity =
5
target eigensegment
Figure 24: Structure of the kernel spectrum, zooming into one particular N-th segment. They converge to segment of the target spectrum according multiplicity of the target spectrum.
62

---

Published as a conference paper at ICLR 2026
K.3 STATEMENT OF THE THEOREM
The statement of the theorem is really unwieldy, so we write it out in separate section. dot-product kernel
K (xx y) = Cn n!
x
y)"
n=U
defined by its level-coefficients co, c 0. Given all E N.
it e-fast-decaying if cn+1 S eCn, for
The multiplicity counting function for is m(n) ("+t-1). It polynomially bounded.
We enumerate the eigensystem of K
(Ao.1, Vo.1),
(A1,1, V1,1), ..... (A1,d. Vi,a),
(A2,1, V2.1), (22)).,.,,,,2((4))))) V2 (2t)))
(An,1, Vn.1)...., ( (m12 V (21,
where the eigenvalues arranged in decreasing order:
Ao.1 2 \1,1 2
In case of multiplicity, the same eigenvalue is written repeatedly. For example, if X has multiplicity 2, then it is written out twice.
Each VR,1 is the eigenspace of λE.. In case of eigenvalue multiplicity, repeat the eigenspace. For example, A1, = A1.2 an eigenvalue of multiplicity then it corresponds to a 2-dimensional eigenspace V. In this case, define V1,1 V1 V.
We also need to perform similar "merging" on the Hermite eigensystem:
On II T Span (ma)) ( n E [a]
This merging is, unfortunately, not exactly the same, because we can't can'tjust say that if on I[ 7it Cve I7 then merge their cigenspaces, because we must not merge if n * n', even if the eigenvalues happen be the same this case. This is because, differ so greatly, that this accidental degeneracy is broken. We must only merge eigenspaces that are non-accidentally degenerate.
0, eventually e, and Cn' will
So why didn't 't we do this for K?? Because K is much harder to control for! We know everything there could be known about the Hermite eigenstructure, but a big unknown that we must laborously control. One thing that is big unknown about K is that we don't know which eigenvalues are accidentally the same, and which eigenvalues are -on-accidentalyy the same. So we treat them without special considerations. We know which are accidental and which are not for the Hermite eigenstructure, so we treat them differently.
So, perform non-accidental merge of the Hermite eigensystem. For each N, say that the nith segment of the Hermite eigensystem
{
On 7f Span (Ihm))
|a| =
and within each segment, merge the degenerate eigenspaces. For example, if it happens that I 7: - 7i for |ao| = =Ia'l = n, but no other a" with la"l = n, then replace both >aaa)),1
Span (162²) and Span (1x²7) by their direct sum Span (1i
(E), (x))
63

---

Published as a conference paper at ICLR 2026
With all this set up, can state Theorem 2, this time with full rigor.
Theorem (The HEA holds for fast-decaying dot-product kernel on Gaussian measure). Let
Σ be a covariance matrix;
2. = UUTU be its SVD, with r = diag (Y1..., ,a);
3. μ NOO,
For any N N. there exists constants CN. DN. ex. such that if E [O, and K is an E-fast- decaying dot dot-product kernel, the following happens.
For any element (x,V) V) within the merged N-th segment of the Hermite eigenstructure, there exists exactly dim V eigenvalues (counting multiplicity) of that are in the interval X(1 + CNE). Let their corresponding eigenspaces be Vi,..., Vdim V, then there exists unitary operator
COS θ sin θ sin +
cos θ that rotates V1 @ .... + Vdim v to V. such that || sin Oloop < Dxe.
K.4 PART 1: EXPONENTIAL SEPARATION OF EIGENSYSTEM SEGMENTS
For each segment N, we use the min-max principle to construct upper and lower bounds on its eigenvalues.
Lemma (exponential separation cigensystem segments). Given
a polynomially bounded multiplicity counting function m,
2. a fast-decaying coefficient system Cj2 with parameters (c, Srow, a.));
3. a linearly independent vector system (uk,))
4. operator
30 mil
K
ΣX
Σ
ax (o.) (vral
then for any n, there exists constants En Cr. Dn such that
) An,m(() [C @n
for all e en] The constants Cn, D,, depend only on Srow 0r ..... Srown and the Gram matrix of the vectors (o..........,.mm(())))
We bound the entire eigensegment (K) 2 ... 2 AN. (K) by the min-max principle. This analogous to what we did in Appendix J.3.1, but simplified, because do not need to produce sharp bounds. That comes later.
For the lower bound, V Span (Iva,))..... (
64

---

Published as a conference paper at ICLR 2026
(N.(N)(K)
min x zESpan (2o (()))) |=]|=1
(a|K(x)
m(k)
min zESpan 1 MN
a (at vn.))
||]|==
N (k)
min
and (1r 2w.1)
2 zESpan ( 10 mo))))) kmm ||]||=1
N (k)))
ON
min
Kaluu,
Smin zESpau( (eosaa((e..)...... (...))...,,,,,
1m
1=1
||=||=1
ay
Amiin
8min,N
= ={(x))
where G the Gram matrix of the vectors [oo.1)..... (N))) By assumption, these vectors are linearly independent, so the Gram matrix is positive definite.
For the upper bound, we use V Span (160.1)..... (.to:)))...,lxx-mmmv--. (
(x,((K)
sup
(x) K|x)
#ESpan (vo.))..... -
||||==
(2) K|))
sup
(( |+||=
(N)
m(k)
sup
on.(oolw..(vwx.lo Amax
Σ
and a (
rESpan( (0, [=|==1
1=1
k=N+1
20
m(k)
sup
ax:(ollxx//uwxnl)) + +
ag vv.1) (Faa))
Span [(x..)..... (Nm))))) ||
A=N+1
m(N)
m(N)
m(k
Amax
Σ
polynomial multiplicity
m(N)
M(N)
< Th
Σ
+ O(axe)
m(N) m(N)
Σ
Σ
ax..@xx.dvxx)/oxxxll...oo. O(āne)
m(N) m(N)
ĀN Σ
(bx.leoa O(anc)
O(āN)
65

---

Published as a conference paper at ICLR 2026
K.5 PART 2: CONVERGENCE IN BULK
Now that the spectrum is divided into exponentially separated segments, we can perform surgical extraction of each N-th segment of the spectrum, cut off both the "head" part N, and the "tail" part N.
Lemma (bulk insensitivity of eigensystem segments). Under the same assumptions as Ap- pendix K.4, for any n, there exists constants >> 0, such that the N-th eigensegment is O(c)-close in bulk to the spectrum of the matrix
m(N)
M!N)
1,==1
for all E E En] The constant En and the constant in O(e) depend only on Slow, Slown and the Gram matrix of the vectors Pnm.m))))
Intuitively, the lemma states that the eigensystem segments separate very cleanly. First, relative the N-th eigensegment, all the higher-order segments are (())-small, and thus ignorable. Second, relative the N-th segment, the only effect of the lower-order segments is to foree the N-th eigensegment into a safe subspace very close to the orthogonal subspace Span (l@x.1).... (ON,)(N))), within which the lower-order terms op,1 vanish.
(. UN -1.
all
Stated another way, the lemma states that the N-th segment of the spectrum of K is O(c)-close in bulk to K. To obtain K, we first remove its tail En=N+1 Σm(n) (n, (Vn,z), then project the space orthogonal [vo,))...., (UN-NNNN-N))) to remove its head, to obtain
m(N) m(N)
K Σ Σ
The key of the proof is to ensure that each cut perturbs eigenvalues by (āāNe), so that we would extract something that is -clo-s in bulk to the original eigensegment.
K.5.1 CUTTING OFF THE TAII. We need:
Theorem 8 (Wielandt-Hoffmann inequality (Kato. 1987)). Let A, be self-adjoint operators, such that C B A is trace-class operator, then we can enumerate the eigenvalues of A, B, C Oss Bi, Ti (including eigenvalue multiplicity) such that
Σ aa 3.15
Σ ml
(54)
The tail of the operator K is the part that comes after the aN coefficients. is bounded in trace norm:
m(k)
Tr
an av.
ak!
m(k) Am N+1
h -ー
< ON
Σ
K-N AKD
k=
O(āNc)
66

---

Published as a conference paper at ICLR 2026
where use the polynomial bound m(k) Σ A
Thus, by Wielandt- Viclandt-Hoffman, removing the tail perturbs the spectrum by only O(āze). Note particularly:
1. all segments from the 0-th to the N-th remain exponentially separated;
2. the perturbed N-th segment is -le)- in bulk to the original N-th segment.
K.5.2 CUTTING OFF THE HEAD
Cutting off the head is simply cutting off the inverted tail.
Having cut off the tail, we have finite-rank operator
m(k)
K
(vE.al
that splits into two reducing subspaces V, V- where V Span (10, 1)...., JN, (N,(()),, It is zero on V- and positive-definite V. Therefore, we drop down from the full Hilbert space just V, where we can reason with matrices.
We express K in matrix form in the orthonormal basis (úx,)) ordered so that (θN,)): (xx,i)..... -... 10N, come before 18..1)..... (N-1)-(N-1))
A B
B
[K]
C+D
where the four matrices are:
m(N)
NNN)
A
15=1
m(N)
B
Σ
fEl:m(N), (e.9))(0.N-111mm)
m(N)
C
(n (on)) (n.)).("
N (N)
D
Σ
an (n (Dn Paa (vm,l
==0
t=1
For symmetric matrix in block form,
=1 A--1
0 +
A B-
-A-'BS-1 S-1
B C+D 0
-S-
where S D+C BT B-B.. We need several crude bounds on A, B, C, D, to prove that the first term really the bulk term, and the second term really is an order O perturbation upon the bulk term, and thus we can safely cut off according to the Wielandt -oofmda inequality.
1. For each of A, B, C. their entries are all bounded in absolute values by O(āx). Thus, their spectral radii bounded by Oāāv).
2. By Cauchy interlacing law, Amin 2 Amin ([R) = (axx). Thus, the spectrum of A is (āāx), and the spectrum of A-1 is ()
3. Notice that the matrix D is constructed similarly to the matrix [K], except with one more truncation. Therefore, by the same argument, its least eigenvalue is on the order of ((āx-1) = ((ān/e).
67

---

Published as a conference paper at ICLR 2026
4. Therefore, B B have entries bounded in order O(1), and B AT'A-' B has entries bounded in order O(āx).
5.
Therefore, S has the same spectrum as D with order O(āx) perturbation. Since D has smallest eigenvalue l(@āy-1), so does S. Therefore, S-1 has largest eigenvalue = (=
Thus, the N-th segment of the eigenstructure K, inverted, is ((e) in bulk to the eigenstructure of A- Inverting again, find that it is Oce)-elose in bulk to the eigenstructure of A.
K.6 PART 3: THE SPECIAL CASE OF DOT-PRODUCT KERNELS
Recall, we need to show that, in the standard Gaussian space (0,, Ia)). an operator K defined by kernel Σn Co (ax "Ty)" converges to the Hermite eigensystem. Here, I diag (?1....: with O.
Before applying the two generic lemmas. We need first show that the kernel does have fast- decaying coefficient system. This is because, even though is fast-decaying coefficient sequence, does not automatically imply that K has fast-decaying coefficient system if express in the monomial vector system.
Once this is done, we apply Appendix K.4 to conclude that the kernel's spectrum divided into exponentially separated segments. Then, we "hopscotch" through several eigenstructures, until we show that the --th eigensegment of is Oc)-close bulk to the N-th cigensegment of stretched dot-product kemnel ce Tw), This argument is nearly the same as the proof of Appendix K.5, with small extension to account for the special structure of dot-product kernels. Finally, we hopscotch again, applying Davis-Kahan at every step, prove that the eigenspaces also converge as (()).
K. COMBINATORICS WITH THE MONOMIAL BASIS In analogy with the multidimensional Hermite vector system
ha))
Iha
II im1
ha. (z:)
we define the multidimensional normalized monomial vector system, by taking the tensor product of the single-dimensional normalized monomial vectors:
(aa)
(a.)
II i=1
(2a; 1)!!
i=1
Both of them are vector systems the polynomially bounded multiplicity counting function
T2 + d dd1) d -
m(n)
The n-th segment of the monomial vector system consists of {lua) |ax n), and similarly, for Hermite, {Iha) |o:| n).
The Hermite vector system is obtained by the Gram Gram-Schmidt process on the monomial vector system.
Now, consider the form of the dot- dot-product kernel function:
an ... aa! Th xf
n!!
K K(x v)
n
n!
|a|=n
In bra-ket notation, the operator is
d
(2a; 1)!!
K
Σ
Σ
CR II
|va)
as!
n=0
D: a|=n
1=1
Since Cn a fast-decaying sequence, it remains to show that the quantity
d
0: (2a, - 1)!!
max
a:
ag!
68

---

Published as a conference paper at ICLR 2026
grows most exponentially with Once we show that, know that the coefficient system is also fast-decaying. Equivalently, we need to show that
(a.11(7/22)) + In Σ
2a, O3
max Or 1=1
grows at most linearly with n. Note that, because such a bound on does not depend on the choice of the fast-decaying sequence cas it allows change on to any other on with the same decay rate e, and still get a fast-decaying coefficient system.
First term is trivial:
Σ (2(2222 E min In(ra/2), max In(7//2) = (n) (E(1:d]
(e[l:d]
To bound the second term, we do some combinatorics. Let Oę := (2)), then we have f(k+1) 4 k+T strictly monotonically increasing, Therefore, strictly log-convex, Therefore, + EE In f(ax) is strictly Schur-convex. Thus,
f(k)
In f(ax)
achieves its upper bound at (n,, o,..., 0), and lower bound when all ag are as close to equal as possible.
Upper bound:
(2n) = 2n 1n
In f(n) = In
In(mn) + 0 = (n)
2
Lower bound:
(2n/d)
1
d (n/d) dln
= 2n In
In(mn/d)++011/ 0(1/m) O(n)
+
n/d
2
In fact, we have shown that the coefficient block very tightly clustered:
d
Σ
In f(ax)
2n In(an) + |- In vd. + 0(1/m)
2
1=1
for all a satisfying |a|| =
69

---

Published as a conference paper at ICLR 2026
K.6.2 CONVERGENCE IN BULK
Like the general case, the proof has multiple parts. First, apply Appendix K.4 to conclude that K has exponentially separated eigensegments. Then, we hopscotch through multiple eigensystem segments show eigensegment convergence in bulk, as in Appendix K.5.
N- segment of K( y)
Σ
On m!
(mæiy) + .... + "a
|0(e)
N Σ
N-th segment of R( y)
Cn n!
(1 +.. va
n=
(0-th segment of [K]-
|0(()
(eigensystem of just the an part of [K]
provided that c'y = CN (eigensystem of just the part of [K'1-11-
|0())
(0-th segment of [K']-1--
N
da
-h segment of K²(x,))
Σ
11 + +.. + aaaa
n!
n n=
|1((c)
cn (111111 +... va
N-th segment of K' v) Σ set K'(x, y) car T Tvy, where e = ex/e" N
n!
oN N-th segment of K'(xx, v) N cla Trw)
l1o(c)
{(
cN
N-th segment of
E |xc]
II ri: Iha)
for all a E No
1=1
CN
haa
for all a e No. |a|
Figure 25: Hopscotching through eigensystems.
The new trick here is that we avoid solving for the N-th eigensegment of K, by going down then up again, arriving at previously solved kernel as if taking subway.
70

---

Published as a conference paper at ICLR 2026
K.6.3 CONVERGENCE IN DETAIL
We have successfully proven the source eigensegment converges in bulk the target eigensegment. It remains to prove convergence in detail. This requires breaking degeneracies in the source eigenseg- ment whenever the degeneracy broken in the target eigensegment (but not vice versa), followed by applying Davis-Kahan once per target eigenspace.
Fix some N. The N-th target eigensegment
CN I {<
{(cr
Iha) for all a E NO. |a|| N
Some of the eigenvalues in it may be equal, because {In 7i....s In 7 may be N-linearly dependent. 17 Therefore, merge the cigenvectors with equal eigenvalue into eigenspaces. The cigenspaces have distinct eigenvalues. Note in particular that this constitutes a static target: The coefficients co, Cl..... may change, but if cx I "i cN I o for one choice of the coefficients, then it is so for all choices.
Now, fix one such eigenspace V and its corresponding eigenvalue eNς. Let the N-th segment of K be
(cN SN (())(()))))))))))
(K)))}
where we do not yet demand that the eigenvalues are all distinct. some of the eigenvalues are unluckily degenerate, we just tolerate an arbitrary choice of the eigenvectors for now.
As previously argued, it is Ocl-se to the target eigensegment in bulk. Therefore, for small enough e, the source eigenvalues CNCN, (K)) ...)....a (M)) (K) will be corralled around their corresponding target eigenvalues, like iron filings around magnets. Because there are only m(N) source eigenvalues to go around, each target eigenvalue can only grab exactly as many source eigenvalues its multiplicity. In particular, this means that even if these of eigenvalues are highly degenerate, they still congregate into "herds" that keep a good distance away from each other by rx
In particular, this means ex will be able to grab exactly dim source eigenvalues, so that they are all stuck within an interval (C O())). Enumerate these as CN (K).... CN (aim (K). Let their eigenvecters be Jun.a, (K))..... | v (K)), and let the vector space spanned by them be VK. This is reducing subspace of K, and one that we wish to show as ( to V.
Follow through the hopscotching diagram again. At each step in the hopscotching. either there is an exact equality, in which case the reducing subspace unchanged, or there is a perturbation on the operator that is (c)) relative to the operator, in which case, by Davis- the reducing subspace perturbed by an angle of only (c))
We spell this out explicitly for the top half of the diagram. The bottom half is the same.
At the first step. K E en Ty)" " is perturbed by truncating the tail Em on (x Ty)". This has operator norm (CNE). Since the gap between CN (K)..., CN (K) and all other cigenvalues of K is on the order of āx (11). Thus, by Davis Kahan, truncating the tail only perturbs the reducing subspace VK by an angle O(c).
The second step is an exact identity. Under matrix inverse, the eigenspaces are preserved, even though the eigenvalues are inverted.
In the third step, the inverted head is truncated. The inverted head has operator norm on the order of O(e/āx) while the remaining operator has operator norm on the order O(1/ān). Now, since the gap between (CN(N.,, (K))-,,.... (CNCN,sama (K)) and other inverted eigenvalues of [K]-1 on the order ((), truncating the inverted head only perturbs the reducing subspace by another angle Occ).
17 Even if they are N-linearly independent, the gaps between successive eigenvalues will get smaller larger
N if d 2 3, By the standard counting argument in Diophantine approximation theory, the gap decays at least as fast N
71


Reviews:
[{"review_id": "xvsvWlR29h", "reviewer": "Reviewer_MH8X", "summary": "This paper proposes a principled framework for predicting learning curves of kernel ridge regression (KRR) using only empirical data statistics, specifically the data covariance matrix and the Hermite polynomial decomposition of the target function.  \nThe central theoretical idea is the Hermite Eigenstructure Ansatz (HEA), which posits that for rotation-invariant kernels on approximately Gaussian datasets, the kernel’s eigenfunctions coincide with multivariate Hermite polynomials of the data, and the corresponding eigenvalues factorize as simple monomials in the data covariance eigenvalues.\n\n\n\nThis work offers a conceptually novel and practically valuable contribution: predicting learning curves from minimal dataset statistics without explicit kernel computation.  \nIt bridges data geometry, kernel methods, and neural tangent kernel theory, showing a concrete mapping from data covariance to performance prediction.  \nThe observed similarity between MLP learning order and HEA predictions further strengthens its relevance.", "questions": "- Could the Gaussian assumption be relaxed to a mixture-of-Gaussians or empirical-moment approach to handle non-Gaussian data?  \n\n\n- Can the authors provide quantitative error bounds between predicted and empirical eigenvalues as a function of effective dimension or kernel width?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- Introduces the Hermite Eigenstructure Ansatz, a compact analytical surrogate for kernel eigenfunctions and eigenvalues grounded in probabilistic data geometry.  \n\n- Combines proofs, ablations, and large-scale experiments (CIFAR-5m, SVHN, ImageNet-32) with excellent agreement between theory and observation.  \n\n- The conceptual pipeline links data covariance to feature-space statistics and test error.  \n\n- Provides a data-to-performance theory that is both interpretable and predictive.  \n\n- Clearly delineates success and failure regimes (e.g., Figures 12–16).", "weaknesses": "- No analytical error bounds are provided for the eigenvalue approximation.  \n\n- The Gram–Schmidt coefficient estimation step can be computationally heavy for large datasets.\n\n- Minor comment: Dependence on Gaussianity: the HEA requires data to be \"Gaussian enough\"; it fails for structured or discrete datasets (MNIST, tabular). Extending it beyond this regime would strengthen the framework, but would be very difficult though (but does not undermine the results though).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "UqpnNNp85p", "reviewer": "Reviewer_msN8", "summary": "The paper introduces the hermite eigenstructure ansatz (HEA), which gives a closed form expression for the eigensystem of rotation invariant kernels. Using the eigenframework, this gives the learning curvevs for KRR on real image datasets, which are empirically shown to approximate the learning curves well using only the covariance matrix and the hermite decomposition of the target function. They also show that HEA holds for gaussian data and two limiting cases of the kernel function. Finally, the papers empirically shows that MLPs learn hermite polynomials on real datasets in the order predicted by HEA.", "questions": "1. Can the approximate relationship in the definition of HEA and elsewhere be formalized in terms of the error of the prediction of the learning curves? \n2. Is the HEA expected to hold whenever the Gaussian Universality Ansatz holds? How the two interact?\n3. What is the interpretation of the infinite width limit of Gaussian kernel?", "limitations": "", "rating": 8, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "The hermite eigenstructure ansatz solves one of the main difficulties of using the eigenframework predictions in predicting the learning curves of KRR on real datasets: estimating the eigenvalues and eigenfunctions of the kernel under the given data distribution. This a very important contribution and expands the applicability of this line of work.\n\n\nFurther, the paper provides extensive empirical evidence that the approximate closed form expression for eigenvalues and eigenfunctions can be used to very accurately predict the learning curves of KRR on a number of real image dataset and various synthetic setups, which is needed given the harndess of verfying the for real datasets HEA. \n\n\nFinally, the paper clearly demonstrates the usefulness of insights from HEA, which they use to predict how MLPs learn functions.\n\n\nOverall, I think that this is a very strong contribution that is presented clearly and concisely and should get accepted.", "weaknesses": "1. The paper is unnecessarily and sometimes confusingly written in an underdefined and informal way. For example, the use of undefined approximate sign $\\approx$, which is crucial to the Hermite eigenstructure ansatz lines 251-260, is at time confusing. Since we are interested in predicting the learning curves, it is quite easy to define this approximate equivalence between two eigenstructures as having learning curves differing by at most something small. It is also unclear whatt does the final prediction mismatch depend on after using a number of these approximations. I think the whole framework would greatly benefit if some care was taken to quantify or at least characterize the dependence of the prediction error of using the hermite eigenstructure ansatz.\n2. As explained in lines 968-969, and if I understand correctly, the hermite ansatz framework depends on eigenlearning framework to map predictions of eigenstructure to predictions of learning curves. Since the hermite ansatz is not formal (and not quantitative, see #1), the applicability of hermite eigenstructure ansatz also depends on the applicability of the eigenframework to the case considered (so it also depends on Gaussian Universality Ansatz). This way, the error of the final prediction aggregates the error of the hermite eigenstructure prediction and the eigenframework prediction. So it’s a bit unclear whether the conditions for success (Section 4.2) are sufficient for both of these errors to be small. I feel like this “hidden” dependence on the eigenframework should be more transparently discussed in the main body. This is especially given some recent work questioning whether the eigenframework actually applies in the case of NTK.\n3. The paper only shows that HEA holds for the Gaussian data with a Gaussian kernel or other fast-decaying dot product kernels in a certain limit of the parameters of those kernels. It’s unclear what is the interpretation of this limit (e.g. taking the width of the Gaussian kernel to infinity). This section would also be much more clear if the limit of is more quantitatively defined.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "FN35jullbq", "reviewer": "Reviewer_16Lq", "summary": "Authors study kernel ridge regression on anisotropic data for rotation-invariant kernels.\nThey introduce a Hermite eigenstructure ansatz (HEA), that allows to approximately compute the eigendecomposition of the kernel function.\nThe main finding is that the covariance of the data and the coefficients of the target function in the basis of this eigendecomposition are enough to predict the test error of the kernel ridge regression.\nThe result holds when the data is 'Gaussian enough', which is empirically verified for certain real datasets. \nIn particular, the width of the kernel needs to be sufficiently large, as well as the effective dimension of the data. \nThe cases when the predicted test errors are further from the real values, are thoroughly studied.\nTheoretical results prove that the predictions hold when data is Gaussian under two limiting regimes.\n\nOne of the technical issue that the authors had to deal with is how to obtain the coefficients of the expansion of the target function in the HEA of the kernel. They suggest to iteratively project the target function on the top eigenfunctions and use Gram-Schmidt orthogonalization to remove correlations between the Hermite polynomials that empirically works well even when the data is non-Gaussian, but the target is sufficiently smooth.", "questions": "See the section above. Furthermore:\n1. Throughout the text, both 'population data covariance, $\\Sigma$' (eg line 47, Figure 1) and 'empirical data covariance, $\\hat \\Sigma$' (eg line 13, Figure 3) are used. From the description in Section 4, it seems that $\\Sigma$ is the main quantity of study. Could the authors clarify to what extent they expect these results to hold when having access only to $\\hat \\Sigma$?  \n2. Line 1643 and Figure 18: what is $\\gamma$? Should it be $\\zeta$?\n3. Figure 5: in the legend, shouldn't the labels for predicted and empirical be swapped?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "The paper is very well-written and constitutes a timely contribution as the role of the data in learning is extremely important.\n\nHermite eigenstructure ansatz is a clean and theoretically motivated tool to understand KRR.\nThe authors present a thorough analysis of when the proposed HEA method holds, both on synthetic and real datasets. \nThey empirically study the effects of data dimension, target function, and various kernels.\nInterestingly, the authors also study the regime 'beyond kernel ridge regression' and find that their predictions hold in that scenario too, to some extent.\n\nFor the case of Gaussian data, two theorems regarding different scaling regimes (very wide kernel and very fast coefficient decay) are present. \nThis work is likely to motivate further research to understand rigorously where the limits of the use of the Gaussianity assumption are, possibly beyond kernel regimes.", "weaknesses": "I don't find serious weaknesses in the methodology, experiments or theoretical results of the paper, although I did not check the proofs in detail.\n\nExtended related work discussion would help the reader to position current work:\n1. In (Refinetti et al., 2023), the authors claim that the neural networks, trained on 'Gaussian versions' of CIFAR-10 (with the same mean and covariance), perform worse than on the real dataset. This can be interpreted that CIFAR-10 is not 'Gaussian enough'. Perhaps whether the data is 'Gaussian enough' depends on the class of learning algorithms, with KRR not being able 'to see further' than the covariance of the data. Is such interpretation correct?\n2. There is a line of work that studies 'staircase property' of learning (e.g., Abbe et al., 2021). Is there a relation between this property and the results in Figure 4? Why both Figure 3 and Figure 4 only use monomials as a target and what would happen when polynomials are used instead?\n\nAlso, the notation of $h_i$ (eg in line 1135) can be confused with $h_{\\mathbf{\\alpha}}$.\n\nRefinetti, Maria, Alessandro Ingrosso, and Sebastian Goldt. \"Neural networks trained with sgd learn distributions of increasing complexity.\" International Conference on Machine Learning. PMLR, 2023.\n\nAbbe, Emmanuel, et al. \"The staircase property: How hierarchical structure can guide deep learning.\" Advances in Neural Information Processing Systems 34 (2021): 26989-27002.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "EAqv7JEBFY", "reviewer": "Reviewer_Cuso", "summary": "This paper introduces the \"hermite eigensystem\" as an approximate formula for the eigenvalues and eigenfunctions of dot-product kernels, expressed in terms of the data covariance matrix. The authors present two limiting cases where their approximation holds exactly, then show that the learning curves obtained by applying the standard theory of kernel ridge regression under their approximation captureswell the empirical learning curves of kernel ridge regression on real data.", "questions": "Presumably, if the data are actually assumed to come from the Gaussian distribution with covariance matrix $\\Sigma$, then the eigenfunctions should be multivariate Hermite polynomials. Have the authors tried to relate the kernel eigenvalues to the Taylor coefficients of the Kernel expansion into powers of $\\mathbf{x}\\cdot\\mathbf{y}$ exactly? Is capturing the right eigenvalues even important for the prediction of learning curves, or is it really the order of the eigenfunctions that matters?", "limitations": "", "rating": null, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 1, "strengths": "- The paper is well written, and the results are clearly and logically organised.  \n- Developing an end-to-end theory of learning based directly on data statistics is a highly valuable goal.  \n- The experimental validation appears convincing and supports the proposed theoretical framework.", "weaknesses": "1. Theoretical learning curves for kernel regression have been established in prior work (e.g., *Optimal Rates for the Regularized Least-Squares Algorithm* by Caponnetto and De Vito). It is unclear what new insights an approximate, simplified formula based on Gaussian assumptions contributes to this existing body of knowledge.  \n2. Gaussian Equivalence Principles (e.g., *The Gaussian Equivalence of Generative Models for Learning with Shallow Neural Networks* by Goldt et al.) already characterise when Gaussian approximations like the one made by the authors are valid or not. The paper does not sufficiently discuss its relation to these frameworks.  \n3. The proposed approximation appears *uncontrolled*, as the limits of its validity are neither explored nor commented upon, leaving uncertainty about its general applicability.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "RsoPCiLJIj", "reviewer": "Reviewer_3sV7", "summary": "This paper presents a theoretical framework for predicting the learning behavior of kernel ridge regression (KRR) on high-dimensional possible complex datasets using rotation-invariant kernels.\nIt proposes the Hermite Eigenstructure Ansatz (HEA): the kernel's eigensystem (for rotation-invariant kernels) closely matches a \"Hermite eigensystem\" derived from multivariate Hermite polynomials in the data space, where the latter depends only on low-order statistics of the data distribution and has an explicit analytical form.\nFor two data models, wide Gaussian kernel on a Gaussian measure and fast-decaying dot-product kernel on a Gaussian measure, the ansatz is proven to hold asymptotically.\nNumerical simulations suggest that the ansatz also holds approximately for real datasets like MNIST and CIFAR-10.\nMoreover, MLPs in the feature learning regime are shown to learn Hermite polynomials in the order predicted by HEA (lower-degree first), suggesting broader applicability.", "questions": "1. What are the connections between the HEA and the Gaussian equivalence assumption (GEA) used in prior works on learning curves of kernel methods? \n2. What are the datasets that HEA fails to approximate well? Can you provide some more insights into the limitations of HEA?\n3. How will HEA be useful for practical applications, such as kernel selection or hyperparameter tuning?", "limitations": "", "rating": 8, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "* The paper is well-written and clearly structured, making it easy to follow the main ideas.\n* It is novel to propose the Hermite Eigenstructure Ansatz (HEA) to predict the learning curves of KRR using only low-order statistics of the data distribution. It would help to better understand the generalization behavior of kernel methods and intrinsic structure of data.\n* The theoretical analysis seem to be solid for the two specific data models.\n* Extensive numerical experiments are provided to validate the proposed theory, including synthetic data and real datasets (MNIST and CIFAR-10). The approximation seems to hold well, justifying the practical relevance of the theory.", "weaknesses": "* Most of the theory in this paper is heuristic, relying on the proposed Hermite Eigenstructure Ansatz (HEA) without rigorous proof except for two specific data models.\nIn addition, it would be helpful to bound the difference between the prediction errors (the original model and the Hermite one) in terms of the approximation error of HEA, giving non-asymptotic guarantees.\n\n* The theoretical results are limited to rotation-invariant kernels and Gaussian data distributions, which may not generalize to more complex real-world scenarios.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)