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

• URL: http://arxiv.org/abs/2603.28956v1
• Date: Mon, 30 Mar 2026 19:59:59 GMT
• Title: Minimum Norm Interpolation via The Local Theory of Banach Spaces: The Role of $2$-Uniform Convexity
• Abstract summary: We study the minimum-norm interpolator (MNI) under a uniform convexity assumption.<n>We prove sharp generalization bounds for the $ell_p$-MNI when $p in bigl (1 + C/log d, 2bigr)$.
• Score: 4.234046389084922
• License: http://creativecommons.org/licenses/by/4.0/
• 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, and it 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 unit ball of the norm is in isotropic (or John's) position, and the covariates are isotropic, symmetric, i.i.d. sub-Gaussian, such as vectors with i.i.d. Bernoulli entries. Finally, under the same assumption on the covariates, we prove sharp generalization bounds for the $\ell_p$-MNI when $p \in \bigl(1 + C/\log d, 2\bigr]$. To the best of our knowledge, this is the 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 works on $K$-convexity, and more modern work on the geometry of 2-uniform and isotropic convex bodies.

Related papers

• Self-Normalized Martingales and Uniform Regret Bounds for Linear Regression [65.82017723631897]
  We show that scale-invariant upper bounds on self-normalized martingales are possible.<n>We derive a self-normalized concentration inequality free of the usual regularization penalties.
  arXiv  Detail & Related papers  (2026-05-02T22:39:00Z)
• Hardness of High-Dimensional Linear Classification [58.29089693778071]
  We establish new exponential in dimension lower bounds for the Maximum Halfspace Discrepancy problem.<n>Both are fundamental problems in computational geometry and machine learning in their exact and approximate forms.
  arXiv  Detail & Related papers  (2026-03-19T15:53:41Z)
• Regularized Online RLHF with Generalized Bilinear Preferences [68.44113000390544]
  We consider the problem of contextual online RLHF with general preferences.<n>We adopt the Generalized Bilinear Preference Model to capture preferences via low-rank, skew-symmetric matrices.<n>We prove that the dual gap of the greedy policy is bounded by the square of the estimation error.
  arXiv  Detail & Related papers  (2026-02-26T15:27:53Z)
• Shrinkage to Infinity: Reducing Test Error by Inflating the Minimum Norm Interpolator in Linear Models [0.0]
  Hastie et al. (2022) found that ridge regularization is essential in high dimensional linear regression $y=betaTx + epsilon$<n>We make precise this observation for linear regression with highly anisotropic covariances and $d/n$.<n>We find that simply scaling up (or inflating) the minimum $ell$ interpolator by a constant greater than one can improve the generalization error.
  arXiv  Detail & Related papers  (2025-10-22T03:30:27Z)
• Efficient reductions from a Gaussian source with applications to statistical-computational tradeoffs [8.162867143465382]
  We leverage our technique to establish reduction-based computational lower bounds for several canonical high-dimensional statistical models under widely-believed conjectures in average-case complexity.<n>We show that computational lower bounds proved for spiked tensor PCA with Gaussian noise are universal, in that they extend to other non-Gaussian noise distributions within our class.
  arXiv  Detail & Related papers  (2025-10-08T17:16:36Z)
• Learning with Norm Constrained, Over-parameterized, Two-layer Neural Networks [54.177130905659155]
  Recent studies show that a reproducing kernel Hilbert space (RKHS) is not a suitable space to model functions by neural networks. In this paper, we study a suitable function space for over- parameterized two-layer neural networks with bounded norms.
  arXiv  Detail & Related papers  (2024-04-29T15:04:07Z)
• Near-Interpolators: Rapid Norm Growth and the Trade-Off between Interpolation and Generalization [28.02367842438021]
  We study the generalization capability of nearly-interpolating linear regressors. For $tau$ fixed, $boldsymbolbeta$ has squared $ell$-norm $bbE[|boldsymbolbeta|_22]. We empirically that a similar phenomenon holds for nearly-interpolating shallow neural networks.
  arXiv  Detail & Related papers  (2024-03-12T02:47:00Z)
• A Unified Framework for Uniform Signal Recovery in Nonlinear Generative Compressed Sensing [68.80803866919123]
  Under nonlinear measurements, most prior results are non-uniform, i.e., they hold with high probability for a fixed $mathbfx*$ rather than for all $mathbfx*$ simultaneously. Our framework accommodates GCS with 1-bit/uniformly quantized observations and single index models as canonical examples. We also develop a concentration inequality that produces tighter bounds for product processes whose index sets have low metric entropy.
  arXiv  Detail & Related papers  (2023-09-25T17:54:19Z)
• Minimax Optimal Quantization of Linear Models: Information-Theoretic Limits and Efficient Algorithms [59.724977092582535]
  We consider the problem of quantizing a linear model learned from measurements. We derive an information-theoretic lower bound for the minimax risk under this setting. We show that our method and upper-bounds can be extended for two-layer ReLU neural networks.
  arXiv  Detail & Related papers  (2022-02-23T02:39:04Z)
• Minimum $\ell_{1}$-norm interpolators: Precise asymptotics and multiple descent [19.781475554462553]
  This paper pursues theoretical understanding for an important type of interpolators: the minimum $ell_1$-norm interpolator. We observe, and provide rigorous theoretical justification for, a curious multi-descent phenomenon. Our finding is built upon an exact characterization of the risk behavior, which is governed by a system of two non-linear equations with two unknowns.
  arXiv  Detail & Related papers  (2021-10-18T17:51:14Z)
• Minimum complexity interpolation in random features models [16.823029377470366]
  kernel methods are heavily affected by the curse of dimensionality. We show that learning with $mathcalF_p$ norms is tractable in an infinite-dimensional convex problem. We introduce a proof technique based on uniform concentration in the dual.
  arXiv  Detail & Related papers  (2021-03-30T00:00:02Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.