Research map / Learning theory and algorithms / Kernels and regression theory

Minimum Norm Interpolation Meets The Local Theory of Banach Spaces

ICML 2024 · Learning theory and algorithms › Kernels and regression theory · approach: High-dimensional asymptotic generalization

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.

Builds a Banach-space geometry framework (uniform convexity, cotype, K-convexity) for analyzing minimum-norm interpolators, bounding their bias/variance and proving a tight lower bound for l_p linear regression with sub-Gaussian covariates.

Problem

Understanding generalization of minimum-norm interpolators beyond Hilbert spaces and beyond Gaussian covariates, where existing tight analyses rely on closed-form Hilbert-space solutions or Gaussianity.

Approach

Connects interpolator generalization to local Banach space geometry: 2-uniform convexity bounds the bias and structural variance by Gaussian complexity; cotype 2 yields a reverse Efron-Stein lower bound on expected conditional variance, shown sharp for l_p regression with sub-Gaussian covariates.

Key results

• Under 2-uniform convexity, the bias plus variance of the conditional expectation of the minimum-norm interpolator is bounded by R_MM* G_n(F)/t, matching the classical ERM unlocalized bound.
• Under cotype 2, a reverse Efron-Stein lower bound EVar >= n * Psi_n(e1, ...) holds for the expected conditional variance.
• For l_p linear regression with p in [1+C loglog log d / loglog d, 2] and d >~ n log n, E Var <= log(d)^2 n/d, which matches the lower bound n/d and extends Donhauser et al. to sub-Gaussian covariates.

Surprising findings

• Under 2-uniform convexity, the unlocalized bound on bias plus variance of conditional expectation matches the classical ERM MSE rate, despite interpolation.

Limitations

• Upper bound on noise-effect variance (T2) not established; only lower bound given, tightness conjectured for UC(2) plus regularity.
• Relaxing UC(2) to CO(2) for the structural bound is conjectured but not proven.
• Noise must be Gaussian or Rademacher; results rely on this for the K-convexity and rotational invariance arguments.

Experimental setup

Metrics: mean squared error bound expected conditional variance

Baselines: Donhauser et al. 2022 minimum l_p-norm interpolator bounds Wang et al. 2022 minimum l1-norm interpolator

Builds on: Efron-Stein inequality Empirical risk minimization localized bounds Gaussian min-max theorem local uniform convergence (Koehler et al., 2021)

Closest papers by meaning

• Beyond Worst-Case Dimensionality Reduction for Sparse Vectors (ICLR 2025 · similarity 0.86)
• Global Minimizers of $\ell^p$-Regularized Objectives Yield the Sparsest ReLU Neural Networks (NeurIPS 2025 · similarity 0.86)
• Minimum-Norm Interpolation Under Covariate Shift (ICML 2024 · similarity 0.85)
• Beyond Benign Overfitting in Nadaraya-Watson Interpolators (NeurIPS 2025 · similarity 0.85)
• Generalization Bounds for Rank-sparse Neural Networks (NeurIPS 2025 · similarity 0.85)
• Spectral Perturbation Bounds for Low-Rank Approximation with Applications to Privacy (NeurIPS 2025 · similarity 0.85)