Research map / Learning theory and algorithms / Kernels and regression theory
Generalization in Kernel Regression Under Realistic Assumptions
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 theory bounding the excess risk of kernel ridge regression under mild heavy-tailed feature assumptions, via relative eigenvalue perturbation bounds showing self-induced regularization, yielding benign overfitting in high dimensions and nearly tempered overfitting in fixed dimensions.
Problem
Existing theory of kernel regression (and min-norm interpolation, a proxy for overfitted neural networks) relies on unrealistic assumptions (Gaussian, sub-Gaussian, i.i.d. features) or covers only narrow settings (high- vs fixed-dimension, regularized vs unregularized, noisy vs noiseless).
Approach
Relative perturbation bounds on kernel matrix eigenvalues under only a mild heavy-tail condition show that the tail of the kernel spectrum acts as implicit ridge regularization (self-induced regularization), giving bias and variance bounds for any regularization, noise level, dimension and sample size.
Key results
- Lower bound on the smallest kernel-matrix eigenvalue of order 1/(n log^a n) for kernels with eigenvalues lambda_i ~ 1/(i log^{1+a} i), far exceeding lambda_n (self-induced regularization).
- Benign overfitting for dot-product kernels in high dimensions: variance goes to 0 and bias goes to O(||theta*_{>N_d}||_inf^2) when d^tau/n = Theta(1).
- For polynomially decaying spectra lambda_i ~ i^{-1-a}, min-norm interpolation has variance O~(n^{2a}) and bias O~(n^{-min(2(r-a),2-a)}), i.e. nearly tempered overfitting.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use the kernel's high-dimensional feature spectrum as implicit regularization | Kernel regression · Kernel matrix eigenvalues | smallest eigenvalue: \mu_n\left(\frac{1}{n}\mathbf{K}\right) \geq \Omega\left(\frac{1}{n\log^a(n)}\right) | Helped |
| Use a dot-product kernel with the stated spectral conditions and no explicit regularization | Min-norm kernel regression · High-dimensional inputs, d^τ/n = Θ(1) | variance: V ≤ σ_ε^2 · O_{n,d}(1/d^{τ−⌊τ⌋} + 1/d^{⌊τ⌋+1−τ}) | Helped |
| Use a min-norm interpolator with polynomial eigenvalue decay λ_i = Θ_{i,n}(i^{-1-a}) | Kernel regression · Fixed input dimensions | bias: B ≤ (1/δ) Õ_n(1/n^{min(2(r-a), 2-a)}) | Helped |
| Increase regularization by decreasing b in γ_n = Θ_n(n^{-1-b}) | Regularized kernel regression · Fixed-dimensional kernel regression | variance: V ≤ σ_ε² · O_n(1/n^{(a-b)/(1+a)}) | Helped |
| Increase regularization by decreasing b in γ_n = Θ_n(n^{-1-b}) | Regularized kernel regression · Fixed-dimensional kernel regression | bias: B ≤ (1/δ) · O_n(1/n^{(1+b)min((2r+a)/(1+a), 2)}) | Hurt |
| Assume Gaussian features so that ρ_{k,n} = Θ(1), instead of using the general feature assumptions | Min-norm kernel regression · Fixed-dimensional kernel regression | variance: σ_ε^2 Õ(1) | Helped |
Surprising findings
- The smallest eigenvalues of the kernel matrix are much larger than the corresponding population eigenvalues lambda_n, contrary to classical intuition.
- Assuming Gaussian features makes existing bounds over-optimistic relative to empirical behavior of common kernels such as a GPK on the unit disk.
Limitations
- Polylog factors in fixed-dimension bounds are likely unavoidable for common kernels without Gaussian features.
- Bounds are stated up to absolute constants and for specific regimes (dot-product kernels on the sphere for high-dimensional results, polynomial eigendecay for fixed-dimension results).
- Some results depend on the concentration coefficient rho_{k,n} and on assumptions alpha_k, beta_k being controlled.
Experimental setup
Metrics: variance (MSE) bias excess risk
Baselines: Gaussian-feature analyses of min-norm interpolation Mei and Montanari dot-product kernel analysis Barzilai and Levi style bounds
Builds on: benign overfitting (Bartlett et al.) neural tangent kernel effective rank
Closest papers by meaning
- Generalization error of spectral algorithms (ICLR 2024 · similarity 0.90)
- Improving Adaptivity via Over-Parameterization in Sequence Models (NeurIPS 2024 · similarity 0.90)
- Characterizing Overfitting in Kernel Ridgeless Regression Through the Eigenspectrum (ICML 2024 · similarity 0.89)
- Sharp Generalization for Nonparametric Regression by Over-Parameterized Neural Networks: A Distribution-Free Analysis in Spherical Covariate (ICML 2025 · similarity 0.89)
- Overfitting Behaviour of Gaussian Kernel Ridgeless Regression: Varying Bandwidth or Dimensionality (NeurIPS 2024 · similarity 0.88)
- Generalization Bound of Gradient Flow through Training Trajectory and Data-dependent Kernel (NeurIPS 2025 · similarity 0.88)
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.