How Abundant Are Good Interpolators? A Large Deviation Analysis of Interpolating Classifiers

Forum topic · 小凯 · 2026-06-08

Summary

This paper by August Y. Chen and Ahmed El Alaoui (arXiv:2606.06469) studies the set S of unit-norm linear classifiers in R^d that correctly classify every point of a labeled dataset with a fixed, possibly negative margin. Under two natural data models — a Gaussian mixture model and a logistic model with Gaussian features — in the proportional regime n/d → α with small α, the authors establish a large deviation principle for the generalization error of a uniformly random classifier drawn from S. The deterministic rate function describes the exponential-in-d proportion of interpolating classifiers achieving a given performance. A concentration phenomenon follows: all but an exponentially small fraction of interpolators share nearly identical generalization performance given by the unique maximum of the rate function. The authors numerically compare this value to empirical risk minimization via gradient descent and a natural linear program, finding that in the overparameterized regime of small α, these efficient methods outperform the vast majority of interpolators, revealing benign, non-trivial overfitting in this setting.

Paper Overview

Field: Machine Learning
Authors: August Y. Chen, Ahmed El Alaoui
arXiv: 2606.06469

Key Points

Let S be the set of unit norm linear classifiers θ ∈ ℝ^d that correctly classify every point of a labeled dataset (X_i, y_i)_{i=1}^n, X_i ∈ ℝ^d, y_i ∈ {-1,+1}, with a possibly negative margin κ fixed in advance.
Under two natural data-generating distributions — a Gaussian mixture model and a logistic model with Gaussian features — and in the proportional regime n/d → α with sufficiently small α, the authors establish a large deviation principle for the event that a classifier θ chosen uniformly at random from S achieves a given generalization error, with high probability over the data.
The associated rate function is deterministic and quantifies the proportion, at the exponential scale in d, of interpolating classifiers attaining a given performance.
Concentration phenomenon: except for an exponentially small fraction, all interpolating classifiers have approximately the same generalization performance, given by the unique maximizer of the rate function.
The maximizer value is numerically compared with:
Empirical risk minimization via gradient descent,
A natural linear program —

both of which search for a point in S. In the small-α overparameterized regime, these efficient procedures outperform the vast majority of interpolators, indicating non-trivial benign overfitting in this setting.

Original Abstract (excerpt)

> Let S be the set of unit norm linear classifiers θ∈ ℝ^d which correctly classify every point of a labeled dataset (Xi,yi)_{i=1}^n, Xi ∈ ℝ^d, yi ∈ {-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 → α 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.

Source: arXiv:2606.06469