Benign overfitting occurs for many norms beyond Euclidean in regression

Benign Overfitting for General Norms and Distributions

Machine Learning

Summary

Predictors that perfectly fit noisy data can often still perform well on new data, a phenomenon called benign overfitting. Most studies focus on solutions that minimize the usual Euclidean norm, but the authors study general norms that reflect other optimization methods like Adam. They show that for many norms and data distributions, benign overfitting still happens, but for the 1-norm it can fail outside Gaussian settings. Their analysis uses geometric and probabilistic tools to understand why this happens in high-dimensional cases.

What this means in practice

  • For machine learning engineers: Design regression models that minimize norms aligned with modern optimizers beyond Euclidean norm for better generalization understanding.
  • For data scientists in finance: Avoid relying on 1-norm based models assuming benign overfitting unless data distributions are close to Gaussian.

A theory result. No direct application yet.

Authors

Daniel Barzilai, Ohad Shamir

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.