Minimum Norm Interpolation via the Local Theory of Banach Spaces: The Role of $2$-Uniform Convexity

Abstract

The minimum-norm interpolator (MNI) framework has recently attracted considerable attention as a tool for understanding generalization in overparameterized models, such as neural networks. In this work, we study the MNI under a $2$-uniform convexity assumption, which is weaker than requiring the norm to be induced by an inner product; in this setting, the MNI typically does not admit a closed-form solution. At a high level, we show that this condition yields an upper bound on the MNI bias in both linear and nonlinear models. We further show that this bound is sharp for overparameterized linear regression when the norm's unit ball is in isotropic or John's position and the covariates are i.i.d.\ sub-Gaussian, for example, when each covariate vector has i.i.d. Rademacher entries. Finally, under the same assumption on the covariates, we prove sharp generalization bounds for the ${\ell }_p$-MNI when $p\in (1+C/\log d,2]$. To the best of our knowledge, this is the \emph{first} work to establish sharp bounds for non-Gaussian covariates in linear models when the norm is not induced by an inner product. This work is deeply inspired by classical work on $K$-convexity and recent work on the geometry of $2$-uniformly convex and isotropic convex bodies.

Submitted (minor corrections and improved readability from the previous version). A preliminary work titled "Minimum Norm Interpolation Meets the Local Theory of Banach Spaces'' appeared at the 2024 International Conference on Machine Learning (consider this information for citations)