# Precise Asymptotic Generalization for Multiclass Classification with Overparameterized Linear Models

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 36 of its 65 references that are in the map.
- First posted on arXiv 23 Jun 2023.

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

- [Scaling Laws for Neural Language Models](https://mlsanity.com/paper/2001.08361/) (2020)
- [Understanding deep learning requires rethinking generalization](https://mlsanity.com/paper/1611.03530/) (2016)
- [Prevalence of Neural Collapse during the terminal phase of deep learning training](https://mlsanity.com/paper/2008.08186/) (2020)
- [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)
- [The generalization error of random features regression: Precise asymptotics and double descent curve](https://mlsanity.com/paper/1908.05355/) (2019)
- [Community Detection and Stochastic Block Models](https://mlsanity.com/paper/1703.10146/) (2017)
- [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)
- [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)
- [The Gaussian equivalence of generative models for learning with shallow neural networks](https://mlsanity.com/paper/2006.14709/) (2020)
- [Classification vs regression in overparameterized regimes: Does the loss function matter?](https://mlsanity.com/paper/2005.08054/) (2020)
- [More Than a Toy: Random Matrix Models Predict How Real-World Neural Representations Generalize](https://mlsanity.com/paper/2203.06176/) (2022)
- [Finite-sample Analysis of Interpolating Linear Classifiers in the Overparameterized Regime](https://mlsanity.com/paper/2004.12019/) (2020)
- [A statistical model for tensor PCA](https://mlsanity.com/paper/1411.1076/) (2014)
- [A Farewell to the Bias-Variance Tradeoff? An Overview of the Theory of Overparameterized Machine Learning](https://mlsanity.com/paper/2109.02355/) (2021)
- [Learning Gaussian Mixtures with Generalised Linear Models: Precise Asymptotics in High-dimensions](https://mlsanity.com/paper/2106.03791/) (2021)
- [Reducibility and Statistical-Computational Gaps from Secret Leakage](https://mlsanity.com/paper/2005.08099/) (2020)
- [Spectrum of inner-product kernel matrices in the polynomial regime and multiple descent phenomenon in kernel ridge regression](https://mlsanity.com/paper/2204.10425/) (2022)
- [Benign Overfitting in Multiclass Classification: All Roads Lead to Interpolation](https://mlsanity.com/paper/2106.10865/) (2021)
- [On the proliferation of support vectors in high dimensions](https://mlsanity.com/paper/2009.10670/) (2020)
- [Benign Overfitting in Linear Classifiers and Leaky ReLU Networks from KKT Conditions for Margin Maximization](https://mlsanity.com/paper/2303.01462/) (2023)
- [An Equivalence Principle for the Spectrum of Random Inner-Product Kernel Matrices with Polynomial Scalings](https://mlsanity.com/paper/2205.06308/) (2022)
- [Are Gaussian data all you need? Extents and limits of universality in high-dimensional generalized linear estimation](https://mlsanity.com/paper/2302.08923/) (2023)
- [A Blessing of Dimensionality in Membership Inference through Regularization](https://mlsanity.com/paper/2205.14055/) (2022)
- [Learning curves for the multi-class teacher-student perceptron](https://mlsanity.com/paper/2203.12094/) (2022)
- [Harmless interpolation in regression and classification with structured features](https://mlsanity.com/paper/2111.05198/) (2021)

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

- [Provable Weak-to-Strong Generalization via Benign Overfitting](https://mlsanity.com/paper/2410.04638/) (2024)
- [Implicit Optimization Bias of Next-Token Prediction in Linear Models](https://mlsanity.com/paper/2402.18551/) (2024)
- [On the Effect of Regularization on Nonparametric Mean-Variance Regression](https://mlsanity.com/paper/2511.22004/) (2025)

## Abstract (arXiv)

We study the asymptotic generalization of an overparameterized linear model for multiclass classification under the Gaussian covariates bi-level model introduced in Subramanian et al.~'22, where the number of data points, features, and classes all grow together. We fully resolve the conjecture posed in Subramanian et al.~'22, matching the predicted regimes for generalization. Furthermore, our new lower bounds are akin to an information-theoretic strong converse: they establish that the misclassification rate goes to 0 or 1 asymptotically. One surprising consequence of our tight results is that the min-norm interpolating classifier can be asymptotically suboptimal relative to noninterpolating classifiers in the regime where the min-norm interpolating regressor is known to be optimal. The key to our tight analysis is a new variant of the Hanson-Wright inequality which is broadly useful for multiclass problems with sparse labels. As an application, we show that the same type of analysis can be used to analyze the related multilabel classification problem under the same bi-level ensemble.