Paper Overview
- Field: Machine Learning
- Authors: August Y. Chen, Ahmed El Alaoui
- Posted: 2026-06-04
- arXiv: 2606.06469
- A large deviation principle for the generalization error of uniformly sampled interpolating linear classifiers.
- A deterministic rate function quantifying the exponential-scale abundance of interpolators at each performance level.
- A concentration result: nearly all interpolators share the same generalization error.
- Numerical evidence that efficient algorithms (gradient descent, linear programming) outperform typical interpolators for small α.
Summary
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 α, the authors 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, the authors establish a concentration phenomenon: except for an exponentially small proportion, all interpolating classifiers have approximately the same generalization performance, given by the unique maximizing value of the rate function.
They numerically compare this maximizing value with the performance of gradient descent empirical risk minimization and a natural linear program—both of which find a point in S—and infer that in the overparameterized regime of small α, these efficient procedures outperform the vast majority of interpolators, indicating the existence of nontrivial benign overfitting in this setting.