Skip to content
Preprint

Benign Overfitting Property of the Minimum $\ell_q$ -norm Interpolant Estimator in Regression Problem via Feature Space Decomposition

Oct 2026 · 0 citations
Mathematics

Abstract

This paper establishes high-probability, non-asymptotic upper bounds for the population excess risk of minimum $\ell_q$-norm interpolating estimators in linear regression, valid for all $1<q<\infty$ under three scenarios: convex concentration, mild moment assumptions and log-concavity. Consequently, we derive sufficient conditions for these estimators to exhibit benign overfitting. Our analysis hinges on a Feature Space Decomposition (FSD) framework, which naturally highlights the self-regularizing properties of minimum norm interpolants as well as the role of alignment between the signal and the features for benign overfitting. From a technical perspective, our approach circumvents the traditionally used Convex Gaussian Min-max Theorem (CGMT) by instead leveraging the Dvoretzky-Milman theorem. We emphasize that the FSD method has the potential to refine standard uniform convergence approaches. Furthermore, the isomorphic Dvoretzky-Milman theorem established herein -- proven under the three scenarios mentioned above -- for the $\ell_q$-norm is of independent mathematical interest.

View source

Similar papers

Grokking through the Lens of Minimum-Norm Interpolation

A statistical theory is developed that characterizes how regularization geometry and signal sparsity govern generalization near interpolation in the prototypical setting of high-dimensional regression and identifies regimes in which sparsity-promoting regularization makes exact interpolation much more accurate than app...

G. Kur, I. Rugina, C. Dominé et al. · 0 citations
Preprint Sep 2026

Oracle high-dimensional $M$-estimation using smooth reparameterization for sparsity

This paper establishes a unified non-linear regularization framework for high-dimensional $M$-estimation, encompassing both linear regression and Cox's proportional hazards models. Rather than relying on traditional additive non-convex penalties, the proposed paradigm embeds sparsity directly into the parameter mapping...

Y. Nishiyama · 0 citations
#artificial intelligence Preprint Nov 2026

A simple adaptive accelerated optimistic dual averaging method for unconstrained convex optimization in $p$-norm geometry

Efficient preconditioning plays an important role in large-scale first-order optimization. In this paper, we propose an adaptive accelerated optimistic dual averaging ($\text{A}^2$ODA) method for unconstrained convex optimization that adopts low-cost preconditioning based on $p$-norm geometry for $p\in[2,\infty]$. The...

Bo-Wen Li, Dan-Qing Zhou, Chuan He · 0 citations

Benign Overfitting for General Norms and Distributions

This paper develops a method to analyze benign overfitting in linear regression for general norms and general (sub-Gaussian) distributions and proves that minimum-p-norm interpolation with p>1 can benignly overfit even for non-Gaussian distributions, under suitable conditions.

Daniel Barzilai, Ohad Shamir · 0 citations
Preprint Nov 2026

Convex Regression at Scale: Geometry-Preserving Constraint Sparsification

Convex regression provides a flexible nonparametric estimation framework while incorporating appropriate shape information. However, its standard least-squares formulation has $O(n^2)$ supporting-hyperplane constraints creating a computational bottleneck as the sample size $n$ increases. We study a $K$-nearest-neighbor...

Anish Senapati, J. Blanchet · 0 citations
Preprint Nov 2026

On the Instance-Specific Sharp Rates for Constrained Least Squares Estimators in the Sequence Model

We develop a general methodology based on the Feature Space Decomposition framework for establishing explicit, instance-specific sharp rates for the expected estimation error of convex-constrained least squares estimators in the sequence model, without requiring estimates of localized Gaussian mean widths. We apply thi...

Zong Shang · 0 citations

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.