Benign Overfitting for General Norms and Distributions

Daniel Barzilai; Ohad Shamir

cs.LGSep 27, 2026

Benign Overfitting for General Norms and Distributions

Authors: Daniel Barzilai, Ohad Shamir

Organizations: Weizmann Institute of Science · University of Toronto & Vector Institute

Abstract

Understanding why predictors can generalize despite interpolating noisy training data is a central puzzle in machine learning. Most work on such "benign overfitting" studies minimum-2-norm linear regression, reflecting the inductive bias of gradient descent. However, modern optimizers such as Adam and Muon use non-Euclidean update geometries, favoring solutions associated with other norms. Analyzing regression for non-Euclidean norms is substantially more difficult, with known results essentially limited to Gaussians. In this paper, we develop a method to analyze benign overfitting in linear regression for general norms and general (sub-Gaussian) distributions. As a special case, we prove that minimum-p-norm interpolation with p>1 can benignly overfit even for non-Gaussian distributions, under suitable conditions. Perhaps surprisingly, for the 1-norm, benign overfitting does not hold in general for well-behaved (but non-Gaussian) distributions, showing that existing positive 1-norm results rely crucially on Gaussianity. Our proof analyzes the geometry of the dual optimization problem, using concentration and central limit tools to show it is approximately Euclidean in many high-dimensional cases.

Figures & tables

Figure 1: Minimum- $\ell_{p}$ interpolation for $p\in\{1,2,\infty\}$ , over i.i.d inputs $\mathbf{x}\in\mathbb{R}^{2000}$ with coordinates $x_{j}=\cos(jz)/j$ where $z\sim\mathrm{Unif}([0,\pi])$ . The number of inputs is $n=75$ and the labels are $y=\cos(3z)+\xi$ , with $\xi\sim\mathcal{N}(0,0.1)$ . The horizontal axis shows $z$ .

Figure 2: Dual geometry for Rademacher (top) and Gaussian (bottom) inputs with $n=12$ and $|N|=2^{n}$ . Each panel shows normalized level sets of $\boldsymbol{\lambda}\mapsto\|X_{N}^{\top}\boldsymbol{\lambda}\|_{q}$ on a random flat two-dimensional subspace $\boldsymbol{\lambda}=a\mathbf{u}+b\mathbf{v}$ , where $\mathbf{u},\mathbf{v}\in\{\pm 1/\sqrt{n}\}^{n}$ are orthonormal and $q$ is dual to the indicated minimum- $\ell_{p}$ norm. The black curve is the unit level set. The geometries differ substantially: For Gaussian inputs, the geometry is nearly Euclidean across all three norms. However, for Rademacher inputs, the geometry varies substantially between the norms.

Explore similar work

Grokking through the Lens of Minimum-Norm Interpolation
Sep 29, 2026Gil Kur, Ileana Rugina, Clémentine Carla Juliette Dominé +1Stochastic Interpolants Interpolation
ETH Zürich · Institute of Science and Technology Austria · Harvard University
Universality of Benign Overfitting in Binary Linear Classification
Jan 17, 2025Ichiro Hashimoto, Stanislav Volgushev, Piotr ZwiernikOverfitting Empirical Risk Minimization
Department of Statistical Sciences, University of Toronto
How abundant are good interpolators?
Jun 4, 2026August Y. Chen, Ahmed El AlaouiStochastic Interpolants Overparameterization
Cornell University, Department of Computer Science. Ithaca, NY, USA. · Cornell University, Department of Statistics and Data Science. Ithaca, NY, USA.

Sep 29, 2026, cs.LGJ/K move · Enter open · S save

Grokking through the Lens of Minimum-Norm Interpolation

Gil Kur, Ileana Rugina, Clémentine Carla Juliette Dominé, Marco Mondelli

ETH Zürich · Institute of Science and Technology Austria · Harvard University

Stochastic Interpolants Interpolation Grokking Exact Lens

Open paper AskPDF arXiv

Grokking shows that fitting the training data and learning the underlying signal can occur at very different stages. However, existing theories offer limited quantitative insight into how this delayed generalization depends on inductive bias and signal structure. Our work addresses the gap by developing a statistical theory that characterizes how regularization geometry and signal sparsity govern generalization near interpolation. In particular, we focus on the prototypical setting of high-dimensional regression and identify regimes in which sparsity-promoting regularization makes exact interpolation much more accurate than approximate fitting. In strongly overparameterized noiseless problems, we prove a zero--one generalization law and construct a family of convex norms whose interpolators transition from the trivial risk of the all-zero predictor to exact recovery, while keeping the training error equal to

0

. Furthermore, when feature dimension and sample size are proportional, we provide a precise characterization of training and generalization errors along

\ell_r

-regularization paths. This in turn allows us to quantify the generalization gain that remains near interpolation: we show that this gain increases as the norm becomes more sparsity-promoting and as the target becomes sparser, with a sharp drop in generalization reached for noiseless data and

\ell_1

regularization. Experiments on diagonal linear networks and transformers trained on modular arithmetic demonstrate the generality of our theoretical predictions. Finally, beyond grokking, our work reveals a statistical instability in minimum-norm interpolation: small perturbations in the regularization strength can lead to drastically different generalization, while preserving small training error.

Abstract

Explore similar work

Grokking through the Lens of Minimum-Norm Interpolation

Universality of Benign Overfitting in Binary Linear Classification

How abundant are good interpolators?