mlsanityData to 7 Oct 2026

Universality of max-margin classifiers

arXiv 2310.00176 ↗First posted 29 Sep 2023math.ST stat.ML stat.THcited by 4

Not on the map. Why?

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.

Key facts. Cited by 4 papers in the map (data through 7 Oct 2026). Builds on 27 of its 49 references that are in the map. First posted on arXiv 29 Sep 2023.

Builds on

27 of 49 references.

References · 27

  1. 2018Gradient Descent Provably Optimizes Over-parameterized Neural Networkscited by 655
  2. 2017The Implicit Bias of Gradient Descent on Separable Datacited by 649
  3. 2019Benign Overfitting in Linear Regressioncited by 544
  4. 2019Surprises in High-Dimensional Ridgeless Least Squares Interpolationcited by 508
  5. 2019The generalization error of random features regression: Precise asymptotics and double descent curvecited by 410
  6. 2021Deep learning: a statistical viewpointcited by 239
  7. 2019Two models of double descent for weak featurescited by 194
  8. 2020Benign overfitting in ridge regressioncited by 152
  9. 2021Learning curves of generic features maps for realistic datasets with a teacher-student modelcited by 126
  10. 2018Overfitting or perfect fitting? Risk bounds for classification and regression rules that interpolatecited by 99
  11. 2018Overparameterized Nonlinear Learning: Gradient Descent Takes the Shortest Path?cited by 87
  12. 2020The Interpolation Phase Transition in Neural Networks: Memorization and Generalization under Lazy Trainingcited by 84
15 more
  1. 2020Finite-sample Analysis of Interpolating Linear Classifiers in the Overparameterized Regimecited by 81
  2. 2018A modern maximum-likelihood theory for high-dimensional logistic regressioncited by 79
  3. 2022Benign Overfitting without Linearity: Neural Network Classifiers Trained by Gradient Descent for Noisy Linear Datacited by 74
  4. 2022Universality of empirical risk minimizationcited by 73
  5. 2021Uniform Convergence of Interpolators: Gaussian Width, Norm Bounds, and Benign Overfittingcited by 54
  6. 2020Precise Statistical Analysis of Classification Accuracies for Adversarial Trainingcited by 49
  7. 2018The phase transition for the existence of the maximum likelihood estimate in high-dimensional logistic regressioncited by 45
  8. 2020A Precise High-Dimensional Asymptotic Theory for Boosting and Minimum-ℓ1-Norm Interpolated Classifierscited by 44
  9. 2022The curse of overparametrization in adversarial training: Precise analysis of robust generalization for random features regressioncited by 40
  10. 2019The Impact of Regularization on High-dimensional Logistic Regressioncited by 35
  11. 2023Deterministic equivalent and error universality of deep random features learningcited by 35
  12. 2023Benign Overfitting in Linear Classifiers and Leaky ReLU Networks from KKT Conditions for Margin Maximizationcited by 29
  13. 2019The generalization error of max-margin linear classifiers: Benign overfitting and high dimensional asymptotics in the overparametrized regimecited by 27
  14. 2015Universality laws for randomized dimension reduction, with applicationscited by 21
  15. 2022A Non-Asymptotic Moreau Envelope Theory for High-Dimensional Generalized Linear Modelscited by 11

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2024: 2; 2025: 1; 2026: 1.

4 papers.

  1. 2025The Nuclear Route: Sharp Asymptotics of ERM in Overparameterized Quadratic Networkscited by 11
  2. 2024Neural population geometry and optimal coding of tasks with shared latent structurecited by 9
  3. 2024Benign overfitting in leaky ReLU networks with moderate input dimensioncited by 5
  4. 2026The sharp SAT/UNSAT phase transition in random ellipsoid fittingcited by 0