Research map / Learning theory and algorithms / Kernels and regression theory
Regularized least squares learning with heavy-tailed noise is minimax optimal
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.
Shows kernel ridge regression with heavy-tailed noise (finite q-th moment, q≥3) attains the same minimax-optimal excess-risk rates as under sub-exponential (Bernstein) noise, via a Hilbert-space Fuk–Nagaev inequality.
Problem
Existing optimal-rate analyses of kernel ridge regression (integral operator framework) assume sub-exponential/Bernstein noise; the question is whether optimal rates survive when noise only has finitely many moments.
Approach
Replace the Bernstein inequality in the integral operator analysis with a Hilbert-space Fuk–Nagaev inequality giving subgaussian plus polynomial tail terms; use the effective dimension also as a proxy for the higher moments, yielding the same regularization schedule and rates as the light-tailed case.
Key results
- Under finite q-th moment noise, KRR attains the known capacity-independent rate (log(6c1/δ)/n)^{min(ν,1)/(2min(ν,1)+1)} with the same regularization schedule as under sub-exponential noise.
- Capacity-dependent bound yields rate (log(8c1/δ)/n)^{min(ν,1)/(2min(ν,1)+p)} with regularization alpha ~ (log/n)^{1/(2min(ν,1)+p)}, matching known minimax-optimal rates, independent of q.
- Numerical experiment (n=20, t-noise with 3 dof vs Gaussian) shows heavy-tailed model needs stronger regularization at high confidence levels (~0.95+).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Allow finite q-th noise moments instead of requiring the Bernstein condition | Kernel ridge regression, capacity-independent setting · Well-specified RKHS regression | excess risk convergence rate: \left( \frac{\log(6c_1/\delta)}{n} \right)^{\frac{\min\{ \nu, 1 \}}{2\min\{\nu ,1\} +1}} | No clear effect |
| Allow finite q-th noise moments instead of requiring the Bernstein condition | Kernel ridge regression, capacity-dependent setting · Well-specified RKHS regression with polynomial eigenvalue decay | excess risk convergence rate: \left( \frac{\log(8 c_1 / \delta)}{n} \right)^{\frac{\min\{\nu ,1\}}{2\min\{\nu ,1\} +p}} | No clear effect |
| Use a small regularization parameter under heavy-tailed rather than light-tailed noise | Kernel ridge regression · Numerical experiment, n=20, high confidence beyond 1 - δ ≈ 0.95 | excess risk quantile | Hurt |
| Use stronger regularization for heavy-tailed rather than light-tailed noise | Kernel ridge regression · Numerical experiment, n=20, high confidence | excess risk quantile | Helped |
| Use heavy-tailed rather than light-tailed noise | Kernel ridge regression · Numerical experiment, n=20, moderate confidence levels | excess risk quantile | No clear effect |
| Move into the polynomial confidence regime rather than the subgaussian confidence regime | Kernel ridge regression under finite higher-moment noise · Small-sample or high-confidence regime | excess risk confidence dependence | Hurt |
Surprising findings
- The schedule for optimal rates does not depend on the noise moment order q, despite heavy tails.
- The paper reports that a published Fuk–Nagaev proof for Hilbert spaces had an inconsistent exponential moment bound, which the authors fix.
Limitations
- Analysis restricted to integer q≥3 for the Fuk–Nagaev bound; q in (2,3) not covered
- Only the well-specified setting (nu ≥ 1/2) with bounded kernel is treated
- Confidence-dependent regularization needed at high confidence levels; empirical parameter choice left open
Experimental setup
Datasets: synthetic 1D Gaussian-kernel regression with Gaussian and Student-t noise (n=20)
Metrics: L2(pi) excess risk quantiles
Baselines: Bernstein-condition (sub-exponential noise) kernel ridge regression rates
Builds on: Bernstein-inequality integral operator analysis of kernel ridge regression Fuk–Nagaev inequality effective dimension
Closest papers by meaning
- Optimal Rates for Vector-Valued Spectral Regularization Learning Algorithms (NeurIPS 2024 · similarity 0.89)
- Second-order Optimization under Heavy-Tailed Noise: Hessian Clipping and Sample Complexity Limits (NeurIPS 2025 · similarity 0.87)
- Flat Minima in Linear Estimation and an Extended Gauss Markov Theorem (ICLR 2024 · similarity 0.87)
- Overfitting Behaviour of Gaussian Kernel Ridgeless Regression: Varying Bandwidth or Dimensionality (NeurIPS 2024 · similarity 0.87)
- Characterizing Overfitting in Kernel Ridgeless Regression Through the Eigenspectrum (ICML 2024 · similarity 0.87)
- High-Probability Minimax Adaptive Estimation in Besov Spaces via Online-to-Batch (NeurIPS 2026 · 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.