Benign Overfitting in Multiclass Classification: All Roads Lead to Interpolation

Abstract

The literature on "benign overfitting" in overparameterized models has been mostly restricted to regression or binary classification; however, modern machine learning operates in the multiclass setting. Motivated by this discrepancy, we study benign overfitting in multiclass linear classification. Specifically, we consider the following training algorithms on separable data: (i) empirical risk minimization (ERM) with cross-entropy loss, which converges to the multiclass support vector machine (SVM) solution; (ii) ERM with least-squares loss, which converges to the min-norm interpolating (MNI) solution; and, (iii) the one-vs-all SVM classifier. First, we provide a simple sufficient deterministic condition under which all three algorithms lead to classifiers that interpolate the training data and have equal accuracy. When the data is generated from Gaussian mixtures or a multinomial logistic model, this condition holds under high enough effective overparameterization. We also show that this sufficient condition is satisfied under "neural collapse", a phenomenon that is observed in training deep neural networks. Second, we derive novel bounds on the accuracy of the MNI classifier, thereby showing that all three training algorithms lead to benign overfitting under sufficient overparameterization. Ultimately, our analysis shows that good generalization is possible for SVM solutions beyond the realm in which typical margin-based bounds apply.

arXiv commentCorrected subtle issue in the proofs of Lemmas 4 an 5. Relaxed Assumptions 1 and 2 and added error bound for ETF geometry

References in corpus (23)

• Reconciling modern machine learning practice and the bias-variance trade-off
• Benign Overfitting in Linear Regression
• Prevalence of Neural Collapse during the terminal phase of deep learning training
• A modern maximum-likelihood theory for high-dimensional logistic regression
• Computing Nonvacuous Generalization Bounds for Deep (Stochastic) Neural Networks with Many More Parameters than Training Data
• Scaling description of generalization with number of parameters in deep learning
• Statistical Mechanics of Support Vector Networks
• Squared Earth Mover's Distance-based Loss for Training Deep Neural Networks
• The generalization error of max-margin linear classifiers: Benign overfitting and high dimensional asymptotics in the overparametrized regime
• Benign overfitting in ridge regression
• Evaluation of Neural Architectures Trained with Square Loss vs Cross-Entropy in Classification Tasks
• Classification vs regression in overparameterized regimes: Does the loss function matter?
• Generalization error in high-dimensional perceptrons: Approaching Bayes error with convex optimization
• Structured Prediction Theory Based on Factor Graph Complexity
• Multi-class SVMs: From Tighter Data-Dependent Generalization Bounds to Novel Algorithms
• A Precise Performance Analysis of Learning with Random Features
• Interpolating Classifiers Make Few Mistakes
• Failures of model-dependent generalization bounds for least-norm interpolation
• Theoretical Insights Into Multiclass Classification: A High-dimensional Asymptotic View
• Multiclass Classification Calibration Functions
• Risk Bounds for Over-parameterized Maximum Margin Classification on Sub-Gaussian Mixtures
• Regularization in High-Dimensional Regression and Classification via Random Matrix Theory
• Explicit regularization and implicit bias in deep network classifiers trained with the square loss

Cited by in corpus (4)

• Learning curves for the multi-class teacher-student perceptron
• A Farewell to the Bias-Variance Tradeoff? An Overview of the Theory of Overparameterized Machine Learning
• Semi-supervised Vector-valued Learning: Improved Bounds and Algorithms
• Explaining generalization in deep learning: progress and fundamental limits