Research map / Learning theory and algorithms / Kernels and regression theory
Beyond Benign Overfitting in Nadaraya-Watson Interpolators
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 interpolating Nadaraya-Watson (Shepard/IDW) classifier with inverse-distance weights of exponent beta, proving tempered overfitting for beta>d, benign at beta=d, and catastrophic for beta<d.
Problem
Generalization behavior of interpolating Nadaraya-Watson estimators beyond consistency: which overfitting profile (benign, tempered, catastrophic) arises as a function of the bandwidth-like exponent beta under noisy labels.
Approach
Shows that a single bandwidth-like exponent beta yields all three overfitting regimes for the interpolating NW/Hilbert-kernel predictor: for beta>d it behaves like a finite-k nearest neighbor rule (tempered), for beta<d far-away points dominate and cause constant error (catastrophic), with the proof based on locality rather than spectral analysis.
Key results
- For beta>d the asymptotic clean error is bounded between Omega(poly(p)) and O~(p), i.e. tempered overfitting.
- For beta<d there exists a distribution where clean error is at least a constant c(beta,d) independent of noise level p (catastrophic).
- Experiments on MNIST 0/1 show optimal exponent roughly beta≈8, matching an estimated intrinsic dimension, far below the extrinsic dimension 784.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Set β=d rather than β≠d | NW interpolator · Asymptotic noisy classification | clean classification error: 0 | Helped |
| Set β>d rather than β=d | NW interpolator · Asymptotic noisy classification | clean classification error: C_1(β/d)·p^{c(β/d)} ≤ 𝓛(ĥ_β) ≤ C_2(β/d)·log^{1/(1-d/β)}(1/p)·p | Hurt |
| Set β<d rather than β=d | NW interpolator · Asymptotic noisy classification | clean classification error: 𝓛(ĥ_β) ≥ C_2 · c(β,d) | Hurt |
| Overestimate rather than underestimate the intrinsic dimension when setting β | NW interpolator · Data with intrinsic dimension d_int | overfitting severity | Helped |
| Set β below the intrinsic dimension rather than above it | NW interpolator · One-dimensional synthetic data | clean test error: 0.1 | Hurt |
| Set β above the intrinsic dimension rather than below it | NW interpolator · One-dimensional synthetic data | clean test error | Helped |
| Tune β to the intrinsic dimension rather than the embedding dimension | NW interpolator · Spherical data on S²⊂R³ | clean test error: β=2 | Helped |
| Tune β near the intrinsic dimension rather than the extrinsic dimension | NW interpolator · MNIST 0/1 | clean test error: β≈8; 784 | Helped |
Surprising findings
- Over-estimating the intrinsic dimension (beta above it) is much less harmful than under-estimating it, so the predictor is more tolerant to large beta.
Limitations
- Theoretical results are proven for distributions with a density on R^d; the intrinsic-dimension extension is conjectured, not proven.
- Asymptotic results only; finite-sample behavior is illustrated only empirically.
Experimental setup
Datasets: MNIST (0 and 1 digits)
Benchmarks: MNIST 0/1 subset synthetic 1D data synthetic spherical data S^2
Metrics: clean classification error
Baselines: 1-nearest neighbor k-nearest neighbor
Builds on: Hilbert kernel estimate (Devroye et al.) benign overfitting tempered overfitting (Mallinar et al.)
Closest papers by meaning
- Noisy Interpolation Learning with Shallow Univariate ReLU Networks (ICLR 2024 · similarity 0.89)
- Transfer Learning for Benign Overfitting in High-Dimensional Linear Regression (NeurIPS 2025 · similarity 0.89)
- Minimum-Norm Interpolation Under Covariate Shift (ICML 2024 · similarity 0.88)
- Overfitting Behaviour of Gaussian Kernel Ridgeless Regression: Varying Bandwidth or Dimensionality (NeurIPS 2024 · similarity 0.86)
- Benign Overfitting in Adversarial Training of Neural Networks (ICML 2024 · similarity 0.86)
- Benign Overfitting in Single-Head Attention (NeurIPS 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.