Timezone: »
Motivated by the growing literature on ``benign overfitting" in overparameterized models, we study benign overfitting in multiclass linear classification. Specifically, we consider the following popular training algorithms on separable data generated from Gaussian mixtures: (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. Our first key finding is that under a simple sufficient condition, all three algorithms lead to classifiers that interpolate the training data and have equal accuracy. Second, we derive novel error 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.
Author Information
Ke Wang (University of California, Santa Barbara)
Vidya Muthukumar (Georgia Institute of Technology)
Christos Thrampoulidis (University of British Columbia)
More from the Same Authors
-
2021 : Classification and Adversarial Examples in an Overparameterized Linear Model: A Signal-Processing Perspective »
Adhyyan Narang · Vidya Muthukumar · Anant Sahai -
2021 : Binary Classification of Gaussian Mixtures: Abundance of Support Vectors, Benign Overfitting and Regularization »
Ke Wang · Christos Thrampoulidis -
2021 : Label-Imbalanced and Group-Sensitive Classification under Overparameterization »
Ganesh Ramachandra Kini · Orestis Paraskevas · Samet Oymak · Christos Thrampoulidis -
2021 : Estimating Optimal Policy Value in Linear Contextual Bandits beyond Gaussianity »
Jonathan Lee · Weihao Kong · Aldo Pacchiano · Vidya Muthukumar · Emma Brunskill -
2023 : Generalization and Stability of Interpolating Neural Networks with Minimal Width »
Hossein Taheri · Christos Thrampoulidis -
2023 : Supervised-Contrastive Loss Learns Orthogonal Frames and Batching Matters »
Ganesh Ramachandra Kini · Vala Vakilian · Tina Behnia · Jaidev Gill · Christos Thrampoulidis -
2023 : Fast Test Error Rates for Gradient-based Algorithms on Separable Data »
Puneesh Deora · Bhavya Vasudeva · Vatsal Sharan · Christos Thrampoulidis -
2023 : On the Training and Generalization Dynamics of Multi-head Attention »
Puneesh Deora · Rouzbeh Ghaderi · Hossein Taheri · Christos Thrampoulidis -
2023 : Saving a Split for Last-layer Retraining can Improve Group Robustness without Group Annotations »
Tyler LaBonte · Vidya Muthukumar · Abhishek Kumar -
2023 Poster: On the Role of Attention in Prompt-tuning »
Samet Oymak · Ankit Singh Rawat · Mahdi Soltanolkotabi · Christos Thrampoulidis -
2022 Poster: Universal and data-adaptive algorithms for model selection in linear contextual bandits »
Vidya Muthukumar · Akshay Krishnamurthy -
2022 Spotlight: Universal and data-adaptive algorithms for model selection in linear contextual bandits »
Vidya Muthukumar · Akshay Krishnamurthy -
2022 Poster: FedNest: Federated Bilevel, Minimax, and Compositional Optimization »
Davoud Ataee Tarzanagh · Mingchen Li · Christos Thrampoulidis · Samet Oymak -
2022 Oral: FedNest: Federated Bilevel, Minimax, and Compositional Optimization »
Davoud Ataee Tarzanagh · Mingchen Li · Christos Thrampoulidis · Samet Oymak -
2021 Poster: Safe Reinforcement Learning with Linear Function Approximation »
Sanae Amani · Christos Thrampoulidis · Lin Yang -
2021 Spotlight: Safe Reinforcement Learning with Linear Function Approximation »
Sanae Amani · Christos Thrampoulidis · Lin Yang