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

Source 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.