Research map / Learning theory and algorithms / Kernels and regression theory
Characterizing Overfitting in Kernel Ridgeless Regression Through the Eigenspectrum
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 non-asymptotic condition-number bounds for kernel matrices and uses them to prove tempered overfitting (polynomial spectral decay) and catastrophic overfitting (exponential decay) for kernel ridgeless regression under sub-Gaussian design, showing feature independence matters.
Problem
Understanding overfitting of kernel ridgeless (minimum-norm interpolant) regression in the over-parameterized regime with fixed input dimension, where prior analyses relied on Gaussian design or asymptotic/high-dimensional assumptions.
Approach
Bounds the condition number of kernel matrices under a sub-Gaussian design (replacing Gaussian features), showing polynomial eigen-decay gives the intuitive lambda_1/lambda_N scaling while exponential decay gives an extra factor N; this yields tempered overfitting for polynomial and catastrophic overfitting for exponential decay, and shows dependent features can break the tempered-overfitting resu
Key results
- For polynomially decaying spectra the condition number scales as lambda_1/lambda_N, while for exponentially decaying spectra it scales as N*lambda_1/lambda_N under Gaussian features with M=eta N.
- Under sub-Gaussian design with independent entries, test error is bounded by constants C for polynomial decay (tempered overfitting), and is at least cN for exponential decay (catastrophic overfitting).
- With dependent features (cosine/sine, NTK), the smallest singular value vanishes and both tempered and catastrophic overfitting can occur for polynomial decay.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use a polynomially decaying kernel spectrum rather than an exponentially decaying spectrum | Ridgeless KRR under the sub-Gaussian design assumption · Ridgeless KRR | test error: C≤𝓡≤C⁻¹; 𝓡≥CN | Helped |
| Use independent sub-Gaussian features rather than possibly dependent sub-Gaussian features | Ridgeless KRR with polynomial eigen-decay · Ridgeless KRR, polynomial eigen-decay | test error | Helped |
Surprising findings
- The NTK, which has polynomial eigen-decay, can exhibit catastrophic overfitting when features are dependent, contradicting prior tempered-overfitting conclusions.
- Smallest singular value of the kernel matrix vanishes for dependent cosine/sine features even with polynomial decay.
Limitations
- Analysis restricted to finite-rank features and independent sub-Gaussian design; the realistic infinite-rank dependent kernel case is not covered.
- Benign overfitting regime (linear-poly-logarithmic decay) is out of scope.
- Experiments are simple synthetic simulations rather than real datasets.
Experimental setup
Metrics: condition number s_max/s_min test error (MSE) smallest singular value
Baselines: Gaussian design KRR analysis Barzilai-Shamir-type condition number bound Mallinar et al. tempered/catastrophic overfitting results
Builds on: benign overfitting in kernel ridge regression Gaussian design analysis of KRR (Mei and Montanari type) Barzilai-style condition number bounds for kernel matrices tempered vs catastrophic overfitting taxonomy
Closest papers by meaning
- Overfitting Behaviour of Gaussian Kernel Ridgeless Regression: Varying Bandwidth or Dimensionality (NeurIPS 2024 · similarity 0.94)
- An Agnostic View on the Cost of Overfitting in (Kernel) Ridge Regression (ICLR 2024 · similarity 0.91)
- A Comprehensive Analysis on the Learning Curve in Kernel Ridge Regression (NeurIPS 2024 · similarity 0.90)
- Generalization in Kernel Regression Under Realistic Assumptions (ICML 2024 · similarity 0.89)
- Kernel Regression in Structured Non-IID Settings: Theory and Implications for Denoising Score Learning (NeurIPS 2025 · similarity 0.88)
- Kernel conditional tests from learning-theoretic bounds (NeurIPS 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.