Predicting kernel regression learning curves from only raw data statistics

This paper introduces the Hermite eigenstructure ansatz (HEA), a theoretical framework that accurately predicts kernel regression learning curves on real datasets using only the empirical data covariance and target function decomposition, by approximating kernel eigenstructures as Hermite polynomials and demonstrating that MLPs in the feature-learning regime follow similar learning patterns.

The Gist

Imagine you are trying to teach a robot to recognize pictures of cats, dogs, and cars. You have a massive library of photos (the dataset), but you don't know exactly how the robot will learn or how many photos it needs before it stops making mistakes. Usually, to predict this, you'd have to run the robot through thousands of training sessions, which takes forever and costs a fortune.

This paper proposes a shortcut. It says: "You don't need to run the robot a thousand times. You just need to look at the shape of your photo library and a simple math map of what you're trying to teach it."

Here is the breakdown of their discovery, using everyday analogies.

1. The Problem: The "Black Box" of Learning

Machine learning models are like black boxes. You put data in, and a prediction comes out. But inside, the math is incredibly complex.

• The Old Way: To predict how well a model will do, scientists usually had to assume the data was perfectly simple (like random noise) or run massive computer simulations to guess the outcome. Real-world data (like photos of dogs) is messy and complex, so these guesses often failed.
• The Goal: The authors wanted a "crystal ball" that could look at a messy dataset and say, "If you use this specific learning algorithm, here is exactly how your error rate will drop as you add more data."

2. The Solution: The "Hermite Eigenstructure Ansatz" (HEA)

The authors came up with a theory called the Hermite Eigenstructure Ansatz (HEA). Let's break down the fancy name:

• The "Eigenstructure": Imagine your dataset is a giant, multi-dimensional cloud of points. This cloud has a shape. It might be stretched out like a long sausage, or squashed like a pancake. The "eigenstructure" is just a fancy way of describing the shape and orientation of this cloud.
• The "Hermite" Part: In math, there are special shapes called Hermite polynomials. Think of these as the "alphabet" of shapes for data that looks somewhat like a bell curve (a Gaussian distribution).
• The "Ansatz": This is a fancy word for an educated guess.

The Big Insight:
The authors discovered that even though real-world data (like images of cars) is incredibly complex, it behaves as if it were made of these simple "Hermite shapes."

The Analogy: Imagine you are trying to describe a chaotic jazz band playing in a crowded room. You could try to record every single sound wave (impossible). But, the authors realized that if you just look at the volume of the instruments (the data covariance) and the type of music (the target function), you can predict the band's performance almost perfectly by assuming they are playing a simple, structured scale (Hermite polynomials).

3. How It Works: The "Recipe"

The paper claims you only need two ingredients to predict the learning curve (how fast the model learns):

1. The Data's "Skeleton" (Covariance Matrix): This is a simple measurement of how the data points relate to each other. It tells you if the data is stretched out in certain directions.
2. The "Difficulty Map" (Polynomial Decomposition): This measures how complex the task is. Is it easy to tell a cat from a dog (simple shape)? Or is it hard to tell a specific breed of dog from a wolf (complex shape)?

The Magic Trick:
Once you have these two ingredients, the authors' formula acts like a translator. It converts the "skeleton" of the data and the "difficulty" of the task into a prediction of the model's performance.

The Metaphor: Imagine you are baking a cake. Usually, you have to bake it, taste it, and adjust the recipe. This paper says: "If you know the quality of your flour (data shape) and the complexity of the recipe (target function), you can predict exactly how the cake will taste without ever turning on the oven."

4. Why It's Surprising

The authors proved this works perfectly if the data is a perfect mathematical bell curve (Gaussian). But the real surprise is that it works for real images too (CIFAR, ImageNet, SVHN).

Even though a picture of a dog is not a perfect bell curve, it is "Gaussian enough." The messy details of the real world average out in a way that makes the simple math work.

The Analogy: It's like predicting the weather. Technically, the atmosphere is chaotic and impossible to model perfectly. But if you look at the average pressure and temperature trends, you can predict a storm with surprising accuracy. The "messy" details don't ruin the prediction; they just add a little noise.

5. The "Feature Learning" Surprise

The paper also tested this on Neural Networks (the AI models that actually power things like self-driving cars).

• They found that when these networks learn, they don't just memorize random patterns. They learn in a very specific order: Simple shapes first, then complex shapes.
• The order in which they learn these shapes matches the order predicted by the authors' simple math formula.

The Metaphor: Think of a student learning to draw. They start with circles and lines (simple), then move to faces, then to detailed portraits. The authors found that Neural Networks follow this exact same "curriculum," and their formula predicts exactly when the student will master each step.

Summary: What Does This Mean for You?

This paper is a "proof of concept" that we can finally understand machine learning without needing to run endless simulations.

• Before: "Let's train the model 1,000 times with different settings and see what happens."
• After: "Let's measure the data's shape and the task's difficulty, plug it into this formula, and we know exactly how the model will perform."

It's a move from guessing and checking to predicting and understanding. It suggests that even in the chaotic world of AI, there is a simple, underlying mathematical order that we can finally see.

Technical Summary

1. Problem Statement

The central challenge in machine learning theory is developing analytical frameworks that can predict model performance (specifically learning curves: test risk vs. sample size) on real-world datasets. Existing theories often rely on simplistic data assumptions (e.g., isotropic Gaussian or spherical data) that fail to capture the complex, anisotropic structure of real data like images (CIFAR, ImageNet).

While recent work has established that Kernel Ridge Regression (KRR) performance is determined by the kernel eigensystem (eigenvalues and eigenfunctions) with respect to the data distribution, calculating this eigensystem for real, high-dimensional, anisotropic datasets is computationally intractable. It typically requires constructing and diagonalizing massive kernel matrices, which defeats the purpose of having a predictive theory.

The Goal: To derive a closed-form, analytical approximation of the kernel eigensystem using only minimal statistics of the data (specifically the empirical covariance matrix) and the functional form of the target, enabling accurate prediction of learning curves without numerical diagonalization.

2. Methodology: The Hermite Eigenstructure Ansatz (HEA)

The authors propose the Hermite Eigenstructure Ansatz (HEA), a theoretical framework that approximates the eigensystem of rotation-invariant kernels on anisotropic data.

Core Concept

The HEA posits that for rotation-invariant kernels (e.g., Gaussian, Laplace, NTK) acting on high-dimensional data, the true eigenfunctions are approximately multivariate Hermite polynomials constructed from the data's principal components, and the eigenvalues follow a specific algebraic structure based on the data's covariance and the kernel's Taylor coefficients.

Key Components

1. Data Representation:

   • Let $\Sigma = \mathbb{E}[xx^\top]$ be the empirical data covariance matrix.
   • Decompose $\Sigma = U \Gamma U^\top$, where $U$ contains principal directions and $\Gamma = \text{diag}(\gamma_1, \dots, \gamma_d)$ contains eigenvalues (variances).
   • Define rescaled coordinates $z = \Gamma^{-1/2} U^\top x$.

2. The Ansatz (Definition 4):
   The true eigensystem $(\lambda_i, \phi_i)$ is approximated by the Hermite eigensystem $HE(\Sigma, (c_\ell))$:

   • Eigenfunctions ($\phi_\alpha$): Multivariate Hermite polynomials constructed from the rescaled coordinates:
     $$\phi_\alpha(x) = h^{(\Sigma)}_\alpha(x) = \prod_{i=1}^d h_{\alpha_i}(z_i)$$
     where $h_k$ are normalized probabilist's Hermite polynomials and $\alpha$ is a multi-index.
   • Eigenvalues ($\lambda_\alpha$): Monomials of the data variances scaled by the kernel's "on-sphere" level coefficients ($c_\ell$):
     $$\lambda_\alpha = c_{|\alpha|} \cdot \prod_{i=1}^d \gamma_i^{\alpha_i}$$
     Here, $|\alpha| = \sum \alpha_i$, and $c_\ell$ are derived from the Taylor expansion of the kernel restricted to a sphere of radius $r = \sqrt{\text{Tr}(\Sigma)}$.

3. Target Decomposition:
   To predict learning curves, the target function $f^*$ must be decomposed into this Hermite basis. Since real data is not perfectly Gaussian, the authors use a Gram-Schmidt orthogonalization process on the sampled Hermite polynomials to estimate the projection coefficients ($v_i$) of the target function, correcting for non-orthogonality caused by data non-Gaussianity.

4. Prediction Pipeline:

   • Input: Data covariance $\Sigma$ and kernel type.
   • Step 1: Compute HEA eigenvalues and eigenfunctions.
   • Step 2: Estimate target coefficients in the HEA basis.
   • Step 3: Plug these into existing KRR eigenframework equations (e.g., Bordelon et al., 2020; Simon et al., 2021) to calculate test risk and learning curves.

3. Theoretical Foundations

The paper provides rigorous proofs for the validity of the HEA under specific limiting conditions:

• Theorem 1 (Wide Kernel Limit): For Gaussian data and a Gaussian kernel, as the kernel width $\sigma \to \infty$, the true eigensystem converges to the HEA.
• Theorem 2 (Fast-Decay Limit): For Gaussian data and a dot-product kernel with rapidly decaying level coefficients ($c_{\ell+1} \ll c_\ell$), the eigensystem converges to the HEA.
• Intuition: In high dimensions, rotation-invariant kernels behave like dot-product kernels on a sphere. When the kernel width is large (or coefficients decay fast), the kernel operator acts as a perturbation on the identity, and the eigenfunctions align with the orthogonal polynomials of the underlying measure (Hermite polynomials for Gaussian-like data).

4. Key Results and Empirical Validation

The authors validate the HEA on real datasets (CIFAR-5m, SVHN, ImageNet-32) and synthetic tasks.

• Accuracy of Eigensystem Prediction:

  • The HEA accurately predicts both the spectrum (eigenvalues) and the eigenbasis (eigenfunctions) of various kernels (Gaussian, Laplace, ReLU NTK) on real image data.
  • Visualizations show high overlap between empirical eigenspaces and HEA-predicted eigenspaces, even for complex datasets.

• Learning Curve Prediction:

  • Using only the sample covariance and a polynomial decomposition of the target, the framework predicts test MSE vs. sample size curves with high accuracy.
  • It successfully predicts sample complexity (the number of samples needed to reach a specific error threshold), including constant prefactors, for tasks like "dog vs. all others" on CIFAR-5m and "car vs. ship" on ImageNet.
  • The method works without ever constructing or diagonalizing a kernel matrix.

• Conditions for Success:
  The paper identifies three conditions where HEA holds well:

  1. Fast decay of kernel coefficients: The kernel must not be too "narrow" (high-frequency).
  2. High effective dimension: Data must concentrate on a sphere (high $d_{eff}$), which is true for complex image datasets but fails for low-dimensional tabular data.
  3. "Gaussian enough" distribution: The data marginals should be approximately Gaussian. Complex datasets (CIFAR) work better than simple ones (MNIST, tabular) because they satisfy this condition better due to the "blessings of dimensionality."

• Extension to MLPs:
  The authors empirically find that Multi-Layer Perceptrons (MLPs) in the feature-learning regime learn Hermite polynomials in the exact order predicted by the HEA for KRR. The optimization time required to learn a specific polynomial mode scales inversely with the square root of the corresponding HEA eigenvalue ($\eta \cdot n_{iter} \propto \lambda_\alpha^{-1/2}$).

5. Significance and Contributions

1. End-to-End Theory: This work provides a "proof of concept" that a complete theoretical pipeline—from raw dataset statistics (covariance) to model performance (learning curves)—is possible for non-trivial algorithms on real data.
2. Computational Efficiency: It eliminates the need for $O(N^3)$ kernel matrix diagonalization, allowing for the prediction of learning curves using only $O(d^2)$ covariance statistics.
3. Unification of Theory: It unifies previous results on isotropic data, dot-product kernels, and Gaussian measures into a single framework (HEA) that applies to anisotropic, high-dimensional real data.
4. Insight into Feature Learning: The finding that MLPs learn in the order of Hermite polynomials suggests a deep connection between the inductive bias of kernel methods and the learning dynamics of feature-learning neural networks.
5. Practical Utility: The framework allows researchers to predict optimal hyperparameters and sample complexity for new tasks on existing datasets without expensive training runs.

Conclusion

The paper demonstrates that despite the complexity of real-world data, the learning dynamics of kernel regression (and by extension, wide neural networks) can be captured by a simple analytical model based on Hermite polynomials and data covariance. The "Hermite Eigenstructure Ansatz" bridges the gap between abstract theoretical models and practical deep learning, offering a powerful tool for predicting and understanding learning curves in realistic settings.