# Generalization for multiclass classification with overparameterized linear models

arXiv: https://arxiv.org/abs/2206.01399 · HTML: https://mlsanity.com/paper/2206.01399/

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- Builds on 44 of its 91 references that are in the map.
- First posted on arXiv 3 Jun 2022.

## Builds on (most cited first, 30 of 44)

- [Understanding deep learning requires rethinking generalization](https://mlsanity.com/paper/1611.03530/) (2016)
- [Reconciling modern machine learning practice and the bias-variance trade-off](https://mlsanity.com/paper/1812.11118/) (2018)
- [The Implicit Bias of Gradient Descent on Separable Data](https://mlsanity.com/paper/1710.10345/) (2017)
- [Benign Overfitting in Linear Regression](https://mlsanity.com/paper/1906.11300/) (2019)
- [Surprises in High-Dimensional Ridgeless Least Squares Interpolation](https://mlsanity.com/paper/1903.08560/) (2019)
- [Underspecification Presents Challenges for Credibility in Modern Machine Learning](https://mlsanity.com/paper/2011.03395/) (2020)
- [The generalization error of random features regression: Precise asymptotics and double descent curve](https://mlsanity.com/paper/1908.05355/) (2019)
- [In Search of the Real Inductive Bias: On the Role of Implicit Regularization in Deep Learning](https://mlsanity.com/paper/1412.6614/) (2014)
- [Characterizing Implicit Bias in Terms of Optimization Geometry](https://mlsanity.com/paper/1802.08246/) (2018)
- [Deep learning: a statistical viewpoint](https://mlsanity.com/paper/2103.09177/) (2021)
- [Two models of double descent for weak features](https://mlsanity.com/paper/1903.07571/) (2019)
- [To understand deep learning we need to understand kernel learning](https://mlsanity.com/paper/1802.01396/) (2018)
- [Benign overfitting in ridge regression](https://mlsanity.com/paper/2009.14286/) (2020)
- [A vector-contraction inequality for Rademacher complexities](https://mlsanity.com/paper/1605.00251/) (2016)
- [Evaluation of Neural Architectures Trained with Square Loss vs Cross-Entropy in Classification Tasks](https://mlsanity.com/paper/2006.07322/) (2020)
- [Fit without fear: remarkable mathematical phenomena of deep learning through the prism of interpolation](https://mlsanity.com/paper/2105.14368/) (2021)
- [Harmless interpolation of noisy data in regression](https://mlsanity.com/paper/1903.09139/) (2019)
- [Convergence of Gradient Descent on Separable Data](https://mlsanity.com/paper/1803.01905/) (2018)
- [On the Optimal Weighted ℓ2 Regularization in Overparameterized Linear Regression](https://mlsanity.com/paper/2006.05800/) (2020)
- [Classification vs regression in overparameterized regimes: Does the loss function matter?](https://mlsanity.com/paper/2005.08054/) (2020)
- [A Model of Double Descent for High-dimensional Binary Linear Classification](https://mlsanity.com/paper/1911.05822/) (2019)
- [Finite-sample Analysis of Interpolating Linear Classifiers in the Overparameterized Regime](https://mlsanity.com/paper/2004.12019/) (2020)
- [Label-Imbalanced and Group-Sensitive Classification under Overparameterization](https://mlsanity.com/paper/2103.01550/) (2021)
- [The jamming transition as a paradigm to understand the loss landscape of deep neural networks](https://mlsanity.com/paper/1809.09349/) (2018)
- [Asymptotics of Ridge (less) Regression under General Source Condition](https://mlsanity.com/paper/2006.06386/) (2020)
- [A Farewell to the Bias-Variance Tradeoff? An Overview of the Theory of Overparameterized Machine Learning](https://mlsanity.com/paper/2109.02355/) (2021)
- [Optimal ridge penalty for real-world high-dimensional data can be zero or negative due to the implicit ridge regularization](https://mlsanity.com/paper/1805.10939/) (2018)
- [Squared Earth Mover's Distance-based Loss for Training Deep Neural Networks](https://mlsanity.com/paper/1611.05916/) (2016)
- [Benign Overfitting in Multiclass Classification: All Roads Lead to Interpolation](https://mlsanity.com/paper/2106.10865/) (2021)
- [The Implicit Bias of Benign Overfitting](https://mlsanity.com/paper/2201.11489/) (2022)

## Built on by (most cited first, 8 of 8)

- [Provable Weak-to-Strong Generalization via Benign Overfitting](https://mlsanity.com/paper/2410.04638/) (2024)
- [Domain-Guided Conditional Diffusion Model for Unsupervised Domain Adaptation](https://mlsanity.com/paper/2309.14360/) (2023)
- [Can DPO Learn Diverse Human Values? A Theoretical Scaling Law](https://mlsanity.com/paper/2408.03459/) (2024)
- [General Loss Functions Lead to (Approximate) Interpolation in High Dimensions](https://mlsanity.com/paper/2303.07475/) (2023)
- [Precise Asymptotic Generalization for Multiclass Classification with Overparameterized Linear Models](https://mlsanity.com/paper/2306.13255/) (2023)
- [How Well Can Preference Optimization Generalize Under Noisy Feedback?](https://mlsanity.com/paper/2510.01458/) (2025)
- [One-Bit Quantization and Sparsification for Multiclass Linear Classification with Strong Regularization](https://mlsanity.com/paper/2402.10474/) (2024)
- [Diffusion-based Target Sampler for Unsupervised Domain Adaptation](https://mlsanity.com/paper/2303.12724/) (2023)

## Abstract (arXiv)

Via an overparameterized linear model with Gaussian features, we provide conditions for good generalization for multiclass classification of minimum-norm interpolating solutions in an asymptotic setting where both the number of underlying features and the number of classes scale with the number of training points. The survival/contamination analysis framework for understanding the behavior of overparameterized learning problems is adapted to this setting, revealing that multiclass classification qualitatively behaves like binary classification in that, as long as there are not too many classes (made precise in the paper), it is possible to generalize well even in some settings where the corresponding regression tasks would not generalize. Besides various technical challenges, it turns out that the key difference from the binary classification setting is that there are relatively fewer positive training examples of each class in the multiclass setting as the number of classes increases, making the multiclass problem "harder" than the binary one.