The generalization error of max-margin linear classifiers: Benign overfitting and high dimensional asymptotics in the overparametrized regime

2019/11/05 by Andrea Montanari, Feng Ruan, Montanari, Andrea +5 · 6 citations
Computer Science · #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (stat.ML) #Machine Learning and ELM #Neural Networks and Applications #Statistics Theory (math.ST) #Stochastic Gradient Optimization Techniques

paper · pdf · doi:10.48550/arxiv.1911.01544

openalex publication_date 2019/11/05 · openalex created_date 2019/11/22 · openalex updated_date 2026/07/28

Abstract

Modern machine learning classifiers often exhibit vanishing classification error on the training set. They achieve this by learning nonlinear representations of the inputs that maps the data into linearly separable classes. Motivated by these phenomena, we revisit high-dimensional maximum margin classification for linearly separable data. We consider a stylized setting in which data (y_i,\boldsymbol x_i), i≤ n are i.i.d. with \boldsymbol x_i\simN(\boldsymbol 0,\boldsymbol Σ) a p-dimensional Gaussian feature vector, and y_i ∈\+1,-1\ a label whose distribution depends on a linear combination of the covariates ⟨ \boldsymbol θ_*,\boldsymbol x_i ⟩. While the Gaussian model might appear extremely simplistic, universality arguments can be used to show that the results derived in this setting also apply to the output of certain nonlinear featurization maps. We consider the proportional asymptotics n,p→∞ with p/n→ ψ, and derive exact expressions for the limiting generalization error. We use this theory to derive two results of independent interest: (i) Sufficient conditions on (\boldsymbol Σ,\boldsymbol θ_*) for `benign overfitting' that parallel previously derived conditions in the case of linear regression; (ii) An asymptotically exact expression for the generalization error when max-margin classification is used in conjunction with feature vectors produced by random one-layer neural networks.

Citations

• To understand deep learning we need to understand kernel learning
• Implicit Regularization in Deep Matrix Factorization
• Understanding deep learning requires rethinking generalization
• The generalization error of random features regression: Precise asymptotics and double descent curve

Cited by

• One-Bit Quantization for Random Features Models
• Optimal Regularization for Performative Learning
• High-dimensional Analysis of Synthetic Data Selection
• Preventing Model Collapse Under Overparametrization: Optimal Mixing Ratios for Interpolation Learning and Ridge Regression
• Theoretical Insights Into Multiclass Classification: A High-dimensional Asymptotic View
• Eigenvalue distribution of the Neural Tangent Kernel in the quadratic scaling

Related

• Universality of max-margin classifiers
• Risk Bounds for Over-parameterized Maximum Margin Classification on\n Sub-Gaussian Mixtures
• Max-Margin Works while Large Margin Fails: Generalization without Uniform Convergence
• Universality of Benign Overfitting in Binary Linear Classification
• Benign Overfitting under Learning Rate Conditions for α Sub-exponential Input