Research map / Learning theory and algorithms / Kernels and regression theory
Overfitting Behaviour of Gaussian Kernel Ridgeless Regression: Varying Bandwidth or Dimensionality
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.
The paper theoretically analyzes minimum-norm interpolating Gaussian kernel ridge regression under varying bandwidth (fixed dimension) and increasing dimension, using the eigenframework and Gaussian design ansatz, showing inconsistency and benign/tempered/catastrophic regimes including the first sub-polynomial benign overfitting example.
Problem
Understanding the overfitting (interpolation) behavior of Gaussian kernel ridgeless regression when the bandwidth or input dimension varies with sample size, including whether it is benign, tempered, or catastrophic.
Approach
Uses the eigenframework predicted risk with spherical-harmonic eigenstructure of the Gaussian kernel to derive matching upper and lower bounds on the ridgeless test risk for arbitrary bandwidth and dimension scalings, yielding inconsistency results for fixed dimension and a generic characterization for increasing dimension, including sub-polynomial dimension.
Key results
- For fixed dimension with uniform sphere data, the ridgeless Gaussian KRR predicted risk is never consistent for any bandwidth scaling and is worse than the null predictor for sufficiently large noise.
- For d = exp(sqrt(log m)) with Gaussian kernel on the sphere, the minimum norm interpolant achieves Bayes error in the limit, giving the first sub-polynomial benign overfitting example.
- For dot-product kernels on the sphere with d = log m, the predicted risk exceeds (1+eta) sigma^2, so no benign overfitting.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use bandwidth τ_m = o(m^{-1/(d-1)}) | Gaussian kernel ridgeless regression · Uniform sphere, fixed dimension | predicted test risk relative to null predictor | Hurt |
| Use bandwidth τ_m = ω(m^{-1/(d-1)}) | Gaussian kernel ridgeless regression · Uniform sphere, fixed dimension | predicted test risk: lim_{m→∞} tilde R(f̂_0) = ∞ | Hurt |
| Use bandwidth τ_m = Θ(m^{-1/(d-1)}) | Gaussian kernel ridgeless regression · Uniform sphere, fixed dimension, sufficiently large noise | predicted test risk relative to null predictor: tilde R(f̂_0) > μ ||f*||^2+(1+η)σ^2 | Hurt |
| Scale dimension as d = log_2 m | Dot-product kernel ridgeless regression · Sphere; d = log_2 m | consistency: tilde R(f̂_0) > (1+η) σ^2 | Hurt |
| Use fixed bandwidth and scale dimension as d = exp(√(log m)) | Gaussian kernel ridgeless regression · Sphere; d = exp(√(log m)), S_d ≤ m^{1/4} | predicted test risk relative to Bayes risk: tilde R(f̂_0) ≤ (1 - 1/log m)^{-1} (1 - exp(-0.89 √(log m)))^{-1} σ^2 + 2B^2 1/m | Helped |
| Scale dimension polynomially with non-integer exponent α | Dot-product kernel ridgeless regression · Sphere; d^α/m = Θ(1), α non-integer | predicted test risk relative to Bayes risk: lim_{m → ∞} tilde R(f̂_0) = σ^2 | Helped |
| Scale dimension polynomially with integer exponent α | Dot-product kernel ridgeless regression · Sphere; d^α/m = Θ(1), α integer | predicted test risk relative to Bayes risk: tilde R(f̂_0) > 1/(1-c_1/9) σ^2 | Hurt |
Surprising findings
- With varying bandwidth in fixed dimension, ridgeless Gaussian KRR is never consistent and is usually worse than the null predictor.
Limitations
- Results rely on the non-rigorous Gaussian universality / eigenframework predicted risk rather than the true test risk.
- Analysis restricted to uniform data on the sphere, where eigenfunctions are spherical harmonics.
- Whether small-noise fixed-dimension tau = Theta(m^{-1/(d-1)}) can beat the null predictor is left open.
Experimental setup
Metrics: predicted test risk cost of overfitting effective rank
Builds on: eigenframework benign overfitting taxonomy (Mallinar et al.) Gaussian design ansatz
Closest papers by meaning
- Characterizing Overfitting in Kernel Ridgeless Regression Through the Eigenspectrum (ICML 2024 · similarity 0.94)
- An Agnostic View on the Cost of Overfitting in (Kernel) Ridge Regression (ICLR 2024 · similarity 0.92)
- A Comprehensive Analysis on the Learning Curve in Kernel Ridge Regression (NeurIPS 2024 · similarity 0.90)
- Kernel Regression in Structured Non-IID Settings: Theory and Implications for Denoising Score Learning (NeurIPS 2025 · similarity 0.88)
- Generalization in Kernel Regression Under Realistic Assumptions (ICML 2024 · similarity 0.88)
- Regularized least squares learning with heavy-tailed noise is minimax optimal (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.