Research map / Learning theory and algorithms / Kernels and regression theory
Generalization error of spectral algorithms
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Derives asymptotic generalization error of spectral algorithms (KRR, gradient flow, optimal profile) trained on kernels, for Wishart and circle data models, and identifies spectral localization, saturation, and universality/overlearning effects under power-law spectra.
Problem
Asymptotic generalization error of kernel learning beyond kernel ridge regression, i.e., for gradient-based and general spectral learning algorithms, under power-law kernel eigenvalues and target coefficients.
Approach
Represent any spectral algorithm by a profile h(λ) applied to the empirical kernel matrix; the generalization error is then an exact quadratic functional of h, whose learning measures are computed explicitly for Wishart and circle models, enabling derivation of the optimal profile and a naive noisy-observation model (NMNO) that matches both models.
Key results
- Under power-law spectra, KRR saturates at kappa/nu > 2 for noisy observations, while gradient flow with optimal stopping avoids saturation and attains rate O(N^{-kappa/(kappa+1)}).
- For noiseless observations, the loss localizes at s=nu with rate O(N^{-kappa}) for kappa<2nu and saturates to O(N^{-2nu}) for kappa>2nu, persisting even for the optimal algorithm.
- An overlearning transition at kappa=nu-1 is identified where the optimal noiseless algorithm switches from underfitting (h<1) to overfitting (h>1).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Replace KRR with gradient flow | Kernel learning under power-law spectra · Noisy observations | generalization error exponent: \tfrac{2\nu}{2\nu+1} -> \tfrac{\kappa}{\kappa+1} when \tfrac{\kappa}{\nu} > 2 | Helped |
| Use the optimal spectral algorithm instead of KRR | Kernel learning under power-law spectra · Noisy observations with \tfrac{\kappa}{\nu} > 2 | generalization error exponent: \tfrac{2\nu}{2\nu+1} -> \tfrac{\kappa}{\kappa+1} | Helped |
| Use any spectral algorithm, including the optimal algorithm | Noiseless Circle model · Noiseless observations with \kappa>2\nu | generalization error exponent: \kappa -> 2\nu | Hurt |
| Use negative-regularization KRR | Noiseless Circle model · Noiseless observations with \kappa>2\nu | generalization error: L[h^*]=L[h_{\eta^*}](1+o(1)) | No clear effect |
| Overlearn the training data rather than underfit it | Optimal spectral algorithm · Noiseless observations with \kappa>\nu-1 | generalization error | Helped |
Surprising findings
- In the saturated noiseless regime, the optimal loss is achieved asymptotically by KRR with negative regularization.
- Optimal algorithms overlearn the training data (h>1) for easier targets with kappa > nu-1.
Limitations
- Wishart model results rely on approximations (leading-order Wick pairings, neglecting O(1/N) terms) and the universality conjecture is verified only for two data models.
- Analysis restricted to exact power-law spectra and targets.
Experimental setup
Metrics: generalization error asymptotic exponent spectral localization scale
Baselines: kernel ridge regression gradient flow spectral cut-off
Builds on: kernel ridge regression asymptotics spectral algorithms neural tangent kernel
Closest papers by meaning
- Generalization in Kernel Regression Under Realistic Assumptions (ICML 2024 · similarity 0.90)
- Optimal Rates for Vector-Valued Spectral Regularization Learning Algorithms (NeurIPS 2024 · similarity 0.88)
- On the Saturation Effects of Spectral Algorithms in Large Dimensions (NeurIPS 2024 · similarity 0.88)
- Kernel Regression in Structured Non-IID Settings: Theory and Implications for Denoising Score Learning (NeurIPS 2025 · similarity 0.87)
- A Comprehensive Analysis on the Learning Curve in Kernel Ridge Regression (NeurIPS 2024 · similarity 0.87)
- Sharp Generalization for Nonparametric Regression by Over-Parameterized Neural Networks: A Distribution-Free Analysis in Spherical Covariate (ICML 2025 · similarity 0.87)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.