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:
- Kernel Sensitivity: How quickly the kernel's eigenvalues decay.
- 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:
- Multiple Kernel Learning (MKL): Taiji Suzuki and Masashi Sugiyama showed in Fast Learning Rate of Multiple Kernel Learning: Trade-Off between Sparsity and Smoothness that while sparse $\ell_1$ regularization is intuitive, dense $\ell_p$ regularization is often superior because it better manages the spectral complexity when kernels have varying smoothness.
- Numerical Integration: In Kernel quadrature with DPPs, Ayoub Belhadji and co-authors demonstrate that kernel-based integration (quadrature) can achieve super-polynomial convergence rates by exploiting the spectral decay of smooth kernels, far outperforming Monte Carlo methods.
- Scaling Gaussian Processes: Alex H. Barnett and colleagues in Uniform approximation of common Gaussian process kernels using equispaced Fourier grids use spectral analysis to show that Squared Exponential kernels converge superexponentially, while Matérn kernels converge only algebraically, providing a rigorous "recipe" for scaling GPs to billions of points.
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.