Fast Learning Rates via Kernel Eigenvalue Decay

This direction is no longer present in the current build. Its last version stays readable and citable here.

Version 1 of 125 papers33 conceptsfrozen 2026-10-04

In classical statistical learning theory, the generalization error of a model typically decreases at a rate of $O(1/\sqrt{n})$, where $n$ is the number of training samples. This "slow rate" suggests that to halve your error, you need four times as much data. However, practitioners often observe much faster convergence in kernel-based methods like Support Vector Machines (SVMs) and Gaussian Processes.

A growing body of research demonstrates that the actual speed of learning is not a fixed constant, but is instead dictated by the spectral decay of the kernel—specifically, how quickly the eigenvalues of the kernel's integral operator diminish.

The Spectrum as a Measure of Complexity

To understand why some kernels learn faster than others, we must look at the Reproducing Kernel Hilbert Space (RKHS) not as a monolithic block, but as a structured hierarchy of functions. Every kernel has an associated integral operator, and the eigenvalues of this operator represent how much "capacity" the kernel allocates to different functional components.

Ingo Steinwart, Don Hush, and Clint Scovel established in Optimal Rates for Regularized Least Squares Regression that these eigenvalues provide a far more granular measure of space complexity than traditional geometric measures like covering numbers. If the eigenvalues $\lambda_i$ decay rapidly (e.g., exponentially), the kernel is effectively "smooth" and concentrates its power on a few simple functions. If they decay slowly (e.g., polynomially), the kernel is "rough" and spreads its capacity across many complex, high-frequency functions.

Localization and the Local Rademacher Complexity

The shift from slow $O(1/\sqrt{n})$ rates to fast $O(1/n)$ rates is achieved through localization. Standard Rademacher complexity considers the worst-case behavior over the entire function space. However, as we gain more data, the learning algorithm only considers functions that achieve low empirical error.

Gilles Blanchard in The Local Rademacher Complexity of Lp-Norm Multiple Kernel Learning uses this intuition to derive tighter bounds. By linking the "local" complexity of the function class to the decay rate of the kernel’s eigenvalues, researchers can prove that the error decreases significantly faster than the square-root limit. This explains why "dense" models—where many kernels are combined—often outperform sparse models: they can adapt their spectral decay to match the complexity of the data.

The Alignment of Kernel and Target

The speed of learning is not just a property of the kernel, but a relationship between the kernel and the "ground truth" (the target function). This is often framed as a Teacher-Student problem.

As explored by Mario Geiger, Matthieu Wyart, and Stefano Spigler in Asymptotic learning curves of kernel methods, the learning rate is a tradeoff between:

  1. Kernel Sensitivity: How quickly the kernel's eigenvalues decay.
  2. Target Regularity: How well the target function aligns with the kernel's top eigenvectors.

If the target function is "smooth" relative to the kernel, the model can capture the underlying pattern using only the dominant eigenvalues, leading to rapid convergence. Jianfa Lai and colleagues recently extended this to classification in The optimality of kernel classifiers in Sobolev space, showing that kernel classifiers (and overparameterized neural networks) achieve minimax optimal rates by exploiting this spectral alignment.

Practical Implications: From MKL to Quadrature

This spectral perspective resolves several practical paradoxes in machine learning:

By moving from global complexity measures to spectral ones, this research direction provides a unified framework to predict and optimize the learning speed of modern non-parametric models.

Papers in this version

History & citationVersion 1 · 2026-10-04

No longer present in the current build · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_fast_learning_rates_via_kernel_eigenvalu_ba44d0e3,
  title = {Fast Learning Rates via Kernel Eigenvalue Decay},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/fast-learning-rates-via-kernel-eigenvalue-decay/rdr_ba44d0e33f9649d2a6c6f5e93dc3542f},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-21},
}

This exact version (version 1, frozen text):

@misc{lacuna_fast_learning_rates_via_kernel_eigenvalu_ba44d0e3_v1,
  title = {Fast Learning Rates via Kernel Eigenvalue Decay},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/fast-learning-rates-via-kernel-eigenvalue-decay/rdr_ba44d0e33f9649d2a6c6f5e93dc3542f/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-21},
}