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.

Corrected 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 (14)

• Prevalence of Neural Collapse during the terminal phase of deep learning training
• 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?
• Multi-class SVMs: From Tighter Data-Dependent Generalization Bounds to Novel Algorithms
• Generalization error in high-dimensional perceptrons: Approaching Bayes error with convex optimization
• 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
• Regularization in High-Dimensional Regression and Classification via Random Matrix Theory
• Risk Bounds for Over-parameterized Maximum Margin Classification on Sub-Gaussian Mixtures
• Explicit regularization and implicit bias in deep network classifiers trained with the square loss

Cited by in corpus (3)

• 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
• Explaining generalization in deep learning: progress and fundamental limits