[Paper] How abundant are good interpolators?
Source: arXiv - 2606.06469v1
Overview
Let $S$ be the set of unit norm linear classifiers $θ\in \mathbb{R}^d$ which correctly classify every point of a labeled dataset $(X_i,y_i)_{i=1}^n$, $X_i \in \mathbb{R}^d$, $y_i \in {-1,+1}$, with a possibly negative margin $κ$ fixed in advance. Under two natural data-generating distributions of the $(X,y)$ pairs — a Gaussian mixture model and a logistic model with Gaussian features — and in the proportional regime $n/d \to α$ with small enough $α$, we establish a large deviation principle on the event that a point $θ$ chosen uniformly at random from $S$ achieves a given generalization error, with high probability over the choice of the data. The associated large deviation rate function is deterministic and describes the proportion, at the exponential scale in $d$, of interpolating classifiers having a given desired performance. As a consequence, we establish the following concentration phenomenon: all but an exponentially small fraction of interpolating classifiers have approximately the same generalization performance given by the unique maximizer of this rate function. We numerically compare this maximizer to the performance of empirical risk minimization by gradient descent and to the performance of a natural linear program, both finding a point in $S$, and deduce that in the overparametrized regime of small $α$, these efficient procedures outperform the vast majority of interpolators, pointing to their nontrivial benign overfitting in this setting.
Key Contributions
This paper presents research in the following areas:
- math.ST
- cs.LG
- math.PR
Methodology
Please refer to the full paper for detailed methodology.
Practical Implications
This research contributes to the advancement of math.ST.
Authors
- August Y. Chen
- Ahmed El Alaoui
Paper Information
- arXiv ID: 2606.06469v1
- Categories: math.ST, cs.LG, math.PR
- Published: June 4, 2026
- PDF: Download PDF