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

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,{\mathbf{x}}_i)$, $i\le n$ are i.i.d. with ${\mathbf{x}}_i\sim \mathsf{N}(0,\mathbf{\Sigma })$ a $p$-dimensional Gaussian feature vector, and $y_i\in \{+1,-1\}$ a label whose distribution depends on a linear combination of the covariates $⟨{\mathbf{\theta }}_{\ast },{\mathbf{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\to \infty$ with $p/n\to \psi$, and derive exact expressions for the limiting generalization error. We use this theory to derive two results of independent interest: $(i)$ Sufficient conditions on $(\mathbf{\Sigma },{\mathbf{\theta }}_{\ast })$ 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.

arXiv comment97 pages; 12 pdf figures (A major revision; changed the title and included a new result on benign overfitting)

References in corpus (18)

• Reconciling modern machine learning practice and the bias-variance trade-off
• Neural Tangent Kernel: Convergence and Generalization in Neural Networks
• Understanding deep learning requires rethinking generalization
• Benign Overfitting in Linear Regression
• Gradient Descent Provably Optimizes Over-parameterized Neural Networks
• The generalization error of random features regression: Precise asymptotics and double descent curve
• A modern maximum-likelihood theory for high-dimensional logistic regression
• Universality in polytope phase transitions and message passing algorithms
• Characterizing Implicit Bias in Terms of Optimization Geometry
• Scaling description of generalization with number of parameters in deep learning
• Overfitting or perfect fitting? Risk bounds for classification and regression rules that interpolate
• To understand deep learning we need to understand kernel learning
• Implicit Regularization in Deep Matrix Factorization
• The Impact of Regularization on High-dimensional Logistic Regression
• Optimal ridge penalty for real-world high-dimensional data can be zero or negative due to the implicit ridge regularization
• Algorithmic Regularization in Over-parameterized Matrix Sensing and Neural Networks with Quadratic Activations
• Fundamental Limits of Ridge-Regularized Empirical Risk Minimization in High Dimensions
• Rank-one matrix estimation: analysis of algorithmic and information theoretic limits by the spatial coupling method

Cited by in corpus (51)

• The generalization error of random features regression: Precise asymptotics and double descent curve
• Generalisation error in learning with random features and the hidden manifold model
• Learning curves of generic features maps for realistic datasets with a teacher-student model
• The Gaussian equivalence of generative models for learning with shallow neural networks
• Classification vs regression in overparameterized regimes: Does the loss function matter?
• The Lasso with general Gaussian designs with applications to hypothesis testing
• Universality Laws for High-Dimensional Learning with Random Features
• A Precise Performance Analysis of Learning with Random Features
• Finite-sample Analysis of Interpolating Linear Classifiers in the Overparameterized Regime
• Random Features for Kernel Approximation: A Survey on Algorithms, Theory, and Beyond
• A Model of Double Descent for High-dimensional Binary Linear Classification
• Gaussian Universality of Perceptrons with Random Labels
• Fundamental Limits of Ridge-Regularized Empirical Risk Minimization in High Dimensions
• On the Optimal Weighted ${\ell }_2$ Regularization in Overparameterized Linear Regression
• Interpolating Classifiers Make Few Mistakes
• On the Inherent Regularization Effects of Noise Injection During Training
• Mean-Field Neural ODEs via Relaxed Optimal Control
• Theoretical Insights Into Multiclass Classification: A High-dimensional Asymptotic View
• Benign Overfitting in Multiclass Classification: All Roads Lead to Interpolation
• Precise Tradeoffs in Adversarial Training for Linear Regression
• On the Generalization Effects of Linear Transformations in Data Augmentation
• When Does Preconditioning Help or Hurt Generalization?
• Label-Imbalanced and Group-Sensitive Classification under Overparameterization
• A Farewell to the Bias-Variance Tradeoff? An Overview of the Theory of Overparameterized Machine Learning
• On the interplay between data structure and loss function in classification problems
• On Uniform Convergence and Low-Norm Interpolation Learning
• Sharp Asymptotics and Optimal Performance for Inference in Binary Models
• When does gradient descent with logistic loss interpolate using deep networks with smoothed ReLU activations?
• Provable More Data Hurt in High Dimensional Least Squares Estimator
• Exploring Weight Importance and Hessian Bias in Model Pruning
• When does gradient descent with logistic loss find interpolating two-layer networks?
• Exact Gap between Generalization Error and Uniform Convergence in Random Feature Models
• Inference in Multi-Layer Networks with Matrix-Valued Unknowns
• CAD: Debiasing the Lasso with inaccurate covariate model
• Asymptotic Behavior of Adversarial Training in Binary Classification
• Bridging the Gap Between Adversarial Robustness and Optimization Bias
• Generalization Error of Generalized Linear Models in High Dimensions
• The Performance Analysis of Generalized Margin Maximizer (GMM) on Separable Data
• Asymptotic Risk of Overparameterized Likelihood Models: Double Descent Theory for Deep Neural Networks
• Explaining generalization in deep learning: progress and fundamental limits
• Generalization error of minimum weighted norm and kernel interpolation
• Prediction in latent factor regression: Adaptive PCR and beyond
• Implicit Bias of Linear RNNs
• Large dimensional analysis of general margin based classification methods
• Training Efficiency and Robustness in Deep Learning
• Sharp global convergence guarantees for iterative nonconvex optimization: A Gaussian process perspective
• Robustifying Binary Classification to Adversarial Perturbation
• Improved Complexities for Stochastic Conditional Gradient Methods under Interpolation-like Conditions
• How isotropic kernels perform on simple invariants
• The existence of maximum likelihood estimate in high-dimensional binary response generalized linear models
• The Interplay Between Implicit Bias and Benign Overfitting in Two-Layer Linear Networks