A novel large deviation principle is established for unit norm linear classifiers, demonstrating that all but an exponentially small fraction of such classifiers share nearly identical generalization performance. This highlights an efficiency gap where empirical risk minimization.
This research establishes a large deviation principle concerning the generalization error of unit norm linear classifiers ($S$) that perfectly interpolate a labeled dataset. Under specific data-generating distributions (Gaussian mixture model and logistic model with Gaussian features) and the proportional regime ($n/d \to \alpha$), the study shows a strong concentration phenomenon. Specifically, almost all interpolating classifiers share the same generalization performance, determined by the maximizer of a deterministic rate function. The authors compare this theoretical result to empirical methods like gradient descent and natural linear programs, concluding that in the overparametrized regime, these efficient procedures significantly outperform the majority of interpolating models, pointing toward the benign overfitting observed in modern deep learning.