Finite-sample Analysis of Interpolating Linear Classifiers in the Overparameterized Regime

Abstract

We prove bounds on the population risk of the maximum margin algorithm for two-class linear classification. For linearly separable training data, the maximum margin algorithm has been shown in previous work to be equivalent to a limit of training with logistic loss using gradient descent, as the training error is driven to zero. We analyze this algorithm applied to random data including misclassification noise. Our assumptions on the clean data include the case in which the class-conditional distributions are standard normal distributions. The misclassification noise may be chosen by an adversary, subject to a limit on the fraction of corrupted labels. Our bounds show that, with sufficient over-parameterization, the maximum margin algorithm trained on noisy data can achieve nearly optimal population risk.

arXiv commentCorrected typographical errors from the previous version of this paper

References in corpus (20)

• Reconciling modern machine learning practice and the bias-variance trade-off
• Benign Overfitting in Linear Regression
• High-dimensional classification using features annealed independence rules
• Risk bounds for statistical learning
• A modern maximum-likelihood theory for high-dimensional logistic regression
• The generalization error of random features regression: Precise asymptotics and double descent curve
• Statistical performance of support vector machines
• Characterizing Implicit Bias in Terms of Optimization Geometry
• Overfitting or perfect fitting? Risk bounds for classification and regression rules that interpolate
• In Search of the Real Inductive Bias: On the Role of Implicit Regularization in Deep Learning
• Uniform convergence may be unable to explain generalization in deep learning
• The generalization error of max-margin linear classifiers: Benign overfitting and high dimensional asymptotics in the overparametrized regime
• Implicit Regularization in Deep Learning
• Classification vs regression in overparameterized regimes: Does the loss function matter?
• Distribution-Independent PAC Learning of Halfspaces with Massart Noise
• Stochastic Gradient Descent on Separable Data: Exact Convergence with a Fixed Learning Rate
• Interpolating Classifiers Make Few Mistakes
• On the Implicit Bias of Initialization Shape: Beyond Infinitesimal Mirror Descent
• Efficient Learning of Linear Separators under Bounded Noise
• On the Error Resistance of Hinge Loss Minimization

Cited by in corpus (2)

• A Precise High-Dimensional Asymptotic Theory for Boosting and Minimum-${\ell }_1$-Norm Interpolated Classifiers
• High-dimensional Asymptotics of Langevin Dynamics in Spiked Matrix Models