Precise Asymptotic Generalization for Multiclass Classification with Overparameterized Linear Models
Not on the map. Why?
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.
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
36 of 65 references.
References · 36
- 2020Scaling Laws for Neural Language Modelscited by 6,586
- 2016Understanding deep learning requires rethinking generalizationcited by 1,674
- 2020Prevalence of Neural Collapse during the terminal phase of deep learning trainingcited by 719
- 2017The Implicit Bias of Gradient Descent on Separable Datacited by 655
- 2019Benign Overfitting in Linear Regressioncited by 549
- 2019Surprises in High-Dimensional Ridgeless Least Squares Interpolationcited by 513
- 2019The generalization error of random features regression: Precise asymptotics and double descent curvecited by 413
- 2017Community Detection and Stochastic Block Modelscited by 319
- 2018Characterizing Implicit Bias in Terms of Optimization Geometrycited by 266
- 2021Deep learning: a statistical viewpointcited by 240
- 2019Two models of double descent for weak featurescited by 195
- 2021Fit without fear: remarkable mathematical phenomena of deep learning through the prism of interpolationcited by 132
24 more
- 2019Harmless interpolation of noisy data in regressioncited by 121
- 2020The Gaussian equivalence of generative models for learning with shallow neural networkscited by 113
- 2020Classification vs regression in overparameterized regimes: Does the loss function matter?cited by 97
- 2022More Than a Toy: Random Matrix Models Predict How Real-World Neural Representations Generalizecited by 91
- 2020Finite-sample Analysis of Interpolating Linear Classifiers in the Overparameterized Regimecited by 81
- 2014A statistical model for tensor PCAcited by 72
- 2021A Farewell to the Bias-Variance Tradeoff? An Overview of the Theory of Overparameterized Machine Learningcited by 57
- 2021Learning Gaussian Mixtures with Generalised Linear Models: Precise Asymptotics in High-dimensionscited by 54
- 2020Reducibility and Statistical-Computational Gaps from Secret Leakagecited by 51
- 2022Spectrum of inner-product kernel matrices in the polynomial regime and multiple descent phenomenon in kernel ridge regressioncited by 45
- 2021Benign Overfitting in Multiclass Classification: All Roads Lead to Interpolationcited by 42
- 2020On the proliferation of support vectors in high dimensionscited by 32
- 2023Benign Overfitting in Linear Classifiers and Leaky ReLU Networks from KKT Conditions for Margin Maximizationcited by 29
- 2022An Equivalence Principle for the Spectrum of Random Inner-Product Kernel Matrices with Polynomial Scalingscited by 27
- 2023Are Gaussian data all you need? Extents and limits of universality in high-dimensional generalized linear estimationcited by 26
- 2022A Blessing of Dimensionality in Membership Inference through Regularizationcited by 18
- 2022Learning curves for the multi-class teacher-student perceptroncited by 17
- 2021Harmless interpolation in regression and classification with structured featurescited by 14
- 2022Generalization for multiclass classification with overparameterized linear modelscited by 8
- 2022Deep Linear Networks can Benignly Overfit when Shallow Ones Docited by 8
- 2023General Loss Functions Lead to (Approximate) Interpolation in High Dimensionscited by 4
- 2023New Equivalences Between Interpolation and SVMs: Kernels and Structured Featurescited by 3
- 2020Estimating High-dimensional Covariance and Precision Matrices under General Missing Dependencecited by 2
- 2022Sparse Hanson-Wright Inequality for a Bilinear Form of Sub-Gaussian Variablescited by 2
Built on by
Citing papers per year: 2024: 2; 2025: 1.
3 papers.