# Universality of max-margin classifiers arXiv: https://arxiv.org/abs/2310.00176 · HTML: https://mlsanity.com/paper/2310.00176/ ## Key facts - Cited by 6 papers in the map (data through 14 Oct 2026). - Builds on 27 of its 49 references that are in the map. - First posted on arXiv 29 Sep 2023. ## Builds on (most cited first, 27 of 27) - [Gradient Descent Provably Optimizes Over-parameterized Neural Networks](https://mlsanity.com/paper/1810.02054/) (2018) - [The Implicit Bias of Gradient Descent on Separable Data](https://mlsanity.com/paper/1710.10345/) (2017) - [Benign Overfitting in Linear Regression](https://mlsanity.com/paper/1906.11300/) (2019) - [Surprises in High-Dimensional Ridgeless Least Squares Interpolation](https://mlsanity.com/paper/1903.08560/) (2019) - [The generalization error of random features regression: Precise asymptotics and double descent curve](https://mlsanity.com/paper/1908.05355/) (2019) - [Deep learning: a statistical viewpoint](https://mlsanity.com/paper/2103.09177/) (2021) - [Two models of double descent for weak features](https://mlsanity.com/paper/1903.07571/) (2019) - [Benign overfitting in ridge regression](https://mlsanity.com/paper/2009.14286/) (2020) - [Learning curves of generic features maps for realistic datasets with a teacher-student model](https://mlsanity.com/paper/2102.08127/) (2021) - [Overfitting or perfect fitting? Risk bounds for classification and regression rules that interpolate](https://mlsanity.com/paper/1806.05161/) (2018) - [Overparameterized Nonlinear Learning: Gradient Descent Takes the Shortest Path?](https://mlsanity.com/paper/1812.10004/) (2018) - [The Interpolation Phase Transition in Neural Networks: Memorization and Generalization under Lazy Training](https://mlsanity.com/paper/2007.12826/) (2020) - [A modern maximum-likelihood theory for high-dimensional logistic regression](https://mlsanity.com/paper/1803.06964/) (2018) - [Finite-sample Analysis of Interpolating Linear Classifiers in the Overparameterized Regime](https://mlsanity.com/paper/2004.12019/) (2020) - [Universality of empirical risk minimization](https://mlsanity.com/paper/2202.08832/) (2022) - [Benign Overfitting without Linearity: Neural Network Classifiers Trained by Gradient Descent for Noisy Linear Data](https://mlsanity.com/paper/2202.05928/) (2022) - [Uniform Convergence of Interpolators: Gaussian Width, Norm Bounds, and Benign Overfitting](https://mlsanity.com/paper/2106.09276/) (2021) - [Precise Statistical Analysis of Classification Accuracies for Adversarial Training](https://mlsanity.com/paper/2010.11213/) (2020) - [The phase transition for the existence of the maximum likelihood estimate in high-dimensional logistic regression](https://mlsanity.com/paper/1804.09753/) (2018) - [A Precise High-Dimensional Asymptotic Theory for Boosting and Minimum-ℓ1-Norm Interpolated Classifiers](https://mlsanity.com/paper/2002.01586/) (2020) - [The curse of overparametrization in adversarial training: Precise analysis of robust generalization for random features regression](https://mlsanity.com/paper/2201.05149/) (2022) - [The Impact of Regularization on High-dimensional Logistic Regression](https://mlsanity.com/paper/1906.03761/) (2019) - [Deterministic equivalent and error universality of deep random features learning](https://mlsanity.com/paper/2302.00401/) (2023) - [Benign Overfitting in Linear Classifiers and Leaky ReLU Networks from KKT Conditions for Margin Maximization](https://mlsanity.com/paper/2303.01462/) (2023) - [The generalization error of max-margin linear classifiers: Benign overfitting and high dimensional asymptotics in the overparametrized regime](https://mlsanity.com/paper/1911.01544/) (2019) - [Universality laws for randomized dimension reduction, with applications](https://mlsanity.com/paper/1511.09433/) (2015) - [A Non-Asymptotic Moreau Envelope Theory for High-Dimensional Generalized Linear Models](https://mlsanity.com/paper/2210.12082/) (2022) ## Built on by (most cited first, 6 of 6) - [The Nuclear Route: Sharp Asymptotics of ERM in Overparameterized Quadratic Networks](https://mlsanity.com/paper/2505.17958/) (2025) - [Neural population geometry and optimal coding of tasks with shared latent structure](https://mlsanity.com/paper/2402.16770/) (2024) - [Benign overfitting in leaky ReLU networks with moderate input dimension](https://mlsanity.com/paper/2403.06903/) (2024) - [High-Dimensional Statistics: Reflections on Progress and Open Problems](https://mlsanity.com/paper/2605.05076/) (2026) - [The sharp SAT/UNSAT phase transition in random ellipsoid fitting](https://mlsanity.com/paper/2608.10184/) (2026) - [Universality and sharp thresholds for ellipsoid fitting](https://mlsanity.com/paper/2608.27372/) (2026) ## Abstract (arXiv) Maximum margin binary classification is one of the most fundamental algorithms in machine learning, yet the role of featurization maps and the high-dimensional asymptotics of the misclassification error for non-Gaussian features are still poorly understood. We consider settings in which we observe binary labels yi and either d-dimensional covariates boldsymbol zi that are mapped to a p-dimension space via a randomized featurization map boldsymbol φ:ℝd →ℝp, or p-dimensional features of non-Gaussian independent entries. In this context, we study two fundamental questions: (i) At what overparametrization ratio p/n do the data become linearly separable? (ii) What is the generalization error of the max-margin classifier? Working in the high-dimensional regime in which the number of features p, the number of samples n and the input dimension d (in the nonlinear featurization setting) diverge, with ratios of order one, we prove a universality result establishing that the asymptotic behavior is completely determined by the expected covariance of feature vectors and by the covariance between features and labels. In particular, the overparametrization threshold and generalization error can be computed within a simpler Gaussian model. The main technical challenge lies in the fact that max-margin is not the maximizer (or minimizer) of an empirical average, but the maximizer of a minimum over the samples. We address this by representing the classifier as an average over support vectors. Crucially, we find that in high dimensions, the support vector count is proportional to the number of samples, which ultimately yields universality.