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

原文摘要

Modern machine learning classifiers often exhibit vanishing classification error on the training set. They achieve this by learning nonlinear representations of the inputs that map 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 (yi,xi), i≤n are i.i.d. with xi∼N(0,Σ) a p-dimensional Gaussian feature vector, and yi∈{+1,−1} a label whose distribution depends on a linear combination of the covariates ⟨θ∗,xi⟩. Recent universality results can be used to show that the results derived in the Gaussian setting also apply when xi=ϕ(zi) for standard Gaussian zi and ϕ a nonlinear featurization map. 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 (Σ,θ∗) for “benign overfitting” that are parallel to 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.

摘要来源：Crossref