Research map / Learning theory and algorithms / Kernels and regression theory
An Agnostic View on the Cost of Overfitting in (Kernel) Ridge Regression
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.
Analyzes the cost of overfitting (ratio of ridgeless to optimally tuned KRR test error) under a Gaussian universality ansatz, giving agnostic non-asymptotic bounds in terms of effective ranks and a taxonomy of benign, tempered, and catastrophic overfitting.
Problem
When does interpolating (ridgeless) kernel ridge regression overfit noisy data benignly, temperedly, or catastrophically, measured relative to the optimally regularized model rather than the Bayes error, and without assuming consistency or the target lies in the RKHS?
Approach
Defines the cost of overfitting as the ratio of ridgeless to optimally tuned test risk and bounds it agnostically, independent of the target, using the omniscient risk estimate and effective ranks r_k and R_k; this yields necessary and sufficient conditions for benign, tempered and catastrophic regimes via k/r_k.
Key results
- Proves the cost of overfitting E_0 upper bounds the ridgeless-to-optimal risk ratio for any target, and E_0 -> 1 iff k_n/n -> 0 and n/R_{k_n} -> 0 (Corollary on benign overfitting).
- Taxonomy theorem: benign if k/r_k -> 0, tempered if k/r_k converges to a value in (0, inf), catastrophic if k/r_k -> inf, resolving an open question from prior work.
- For isotropic features in the proportional regime d = gamma n, the bound gives E_0 <= gamma/(gamma-1), which is tight when the target is zero.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use the interpolating ridgeless model instead of optimally tuned ridge regression | Kernel ridge regression under the Gaussian design ansatz · Any target distribution and sample size | cost of overfitting | Mixed |
| Use covariance spectra with k = o(n) and R_k = ω(n) | Ridgeless kernel ridge regression · Noisy KRR | cost of overfitting | Helped |
| Use isotropic features in the proportional regime d = γn, γ > 1 | Ridgeless linear regression · Proportional regime | test risk: σ^2 γ/(γ - 1) | Hurt |
| Use a power-law spectrum λ_i = i^(-α), α > 1 | Ridgeless kernel ridge regression · Power-law spectrum | overfitting coefficient: E_0 ≲ α | Mixed |
| Use an exponentially decaying spectrum λ_i = e^(-i) | Ridgeless kernel ridge regression · Exponential-decay spectrum | overfitting coefficient | Hurt |
| Use inner-product kernels in the polynomial regime with l bounded away from integers | Ridgeless kernel ridge regression · Polynomial regime n ≍ d^l | cost of overfitting | Helped |
Surprising findings
- Overfitting can be catastrophic for exponentially decaying spectra such as lambda_i = e^{-i}, where r_k/k goes to 0.
- The cost of overfitting bound E_0 depends only on the marginal P(x) and does not depend on the target, so it is the tightest agnostic bound over P(y|x).
Limitations
- Relies on the non-rigorous Gaussian design / Gaussian universality ansatz and the omniscient risk estimate treated as equality.
- The bound may be loose when the optimally tuned ridge is not consistent.
Experimental setup
Metrics: cost of overfitting ratio
Baselines: minimal norm interpolant consistency results
Builds on: omniscient risk estimate for kernel ridge regression benign overfitting in linear regression effective rank
Closest papers by meaning
- Overfitting Behaviour of Gaussian Kernel Ridgeless Regression: Varying Bandwidth or Dimensionality (NeurIPS 2024 · similarity 0.92)
- Characterizing Overfitting in Kernel Ridgeless Regression Through the Eigenspectrum (ICML 2024 · similarity 0.91)
- Benign Overfitting in Out-of-Distribution Generalization of Linear Models (ICLR 2025 · 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)
- Risk and cross validation in ridge regression with correlated samples (ICML 2025 · similarity 0.86)
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.