Research map / Learning theory and algorithms / Kernels and regression theory
A Comprehensive Analysis on the Learning Curve 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.
Gives a unified non-asymptotic and asymptotic analysis of kernel ridge regression learning curves under minimal feature assumptions, validating the Gaussian Equivalence Property under strong ridge and sharpening bias/variance bounds.
Problem
Characterizing the learning curve (test error vs sample size) of kernel ridge regression under minimal assumptions on features, eigen-decay, ridge, and source condition, and when the Gaussian Equivalence Property (GEP) holds.
Approach
Derives Master inequalities bounding bias and variance via whitened-feature concentration coefficients, covering both independent sub-Gaussian features and generic dependent (kernel) features; shows GEP holds under strong ridge but fails under weak ridge, and obtains a novel bias bound for weak ridge with polynomial decay.
Key results
- Under strong ridge, bias and variance bounds coincide for independent and generic features, validating GEP asymptotically.
- Novel weak-ridge bias bound: O(n^{-(1+a)s~}) for s>1 under polynomial eigen-decay, improving prior rates.
- Variance under polynomial decay with weak ridge is Theta(sigma^2) for Laplacian-type kernels but diverges (catastrophic overfitting) for the 1-hidden-layer NTK, so GEP fails under weak ridge.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use independent rather than generic features under strong ridge | KRR · Over-parameterized regime with strong ridge | bias and variance learning-curve bounds | No clear effect |
| Use generic rather than independent features under weak ridge | KRR · Over-parameterized regime with weak ridge | variance: \bigtheta{}{\sigma^2} ; \bigot{}{\sigma^2 n^{2a}} | Hurt |
| Use generic rather than independent features under weak ridge | KRR · Over-parameterized regime with weak ridge | bias | Mixed |
| Replace kernel features with independent Gaussian or Rademacher features | KRR with sine features · Kernel regression on [0,1], sample sizes 100 to 1000 | bias and variance decay | No clear effect |
| Apply a strong ridge | KRR with generic or independent features · Over-parameterized regime | test-error learning curve | No clear effect |
| Use a weak ridge with generic features rather than independent features | KRR · Over-parameterized regime with polynomial eigen-decay | variance: \V=\bigtheta{}{\sigma^2} ; \V=\bigo{}{\sigma^2n^{2a}} | Mixed |
| Use the improved weak-ridge bias bound | Kernel ridgeless regression · Polynomial eigen-decay with generic features | bias: n^{-(r-a)_+} ; n^{-(2r+a)} ; n^{-2(1+a)} | Helped |
| Use a weak ridge rather than a strong ridge | KRR with generic features · Over-parameterized regime with exponential eigen-decay | variance | Hurt |
Surprising findings
- GEP does not hold under weak ridge: variance can diverge for NTK kernels while staying constant for Laplacian kernels.
- Variance decays at most O(1/n) regardless of eigen-decay in the over-parameterized regime under strong ridge, so exponential-decay settings are dominated by variance in noisy cases.
Limitations
- Upper bounds in some phase-diagram regions are not known to be sharp.
- Lower bounds for generic features exist only in some settings.
- Experiments are limited to a simple kernel with p=2000 finite-rank features due to page constraints.
Experimental setup
Metrics: bias variance test error decay rate
Baselines: Gaussian Design replica-method results Embedding Condition bounds MaxDoF bounds
Builds on: Gaussian Design analyses (replica method) Embedding Condition analyses Master inequalities (prior work) MaxDoF assumption
Closest papers by meaning
- Kernel Regression in Structured Non-IID Settings: Theory and Implications for Denoising Score Learning (NeurIPS 2025 · similarity 0.92)
- Characterizing Overfitting in Kernel Ridgeless Regression Through the Eigenspectrum (ICML 2024 · similarity 0.90)
- Overfitting Behaviour of Gaussian Kernel Ridgeless Regression: Varying Bandwidth or Dimensionality (NeurIPS 2024 · similarity 0.90)
- Towards Theoretical Understanding of Learning Large-scale Dependent Data via Random Features (ICML 2024 · similarity 0.88)
- Kernel conditional tests from learning-theoretic bounds (NeurIPS 2025 · similarity 0.88)
- High-Dimensional Kernel Methods under Covariate Shift: Data-Dependent Implicit Regularization (ICML 2024 · 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.