mlsanityData to 14 Oct 2026

Generalization for multiclass classification with overparameterized linear models

arXiv 2206.01399 ↗First posted 3 Jun 2022cs.LG stat.MLcited by 8

Not on the map. Why?

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.

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

44 of 91 references.

References · 44

  1. 2016Understanding deep learning requires rethinking generalizationcited by 1,674
  2. 2018Reconciling modern machine learning practice and the bias-variance trade-offcited by 927
  3. 2017The Implicit Bias of Gradient Descent on Separable Datacited by 655
  4. 2019Benign Overfitting in Linear Regressioncited by 549
  5. 2019Surprises in High-Dimensional Ridgeless Least Squares Interpolationcited by 513
  6. 2020Underspecification Presents Challenges for Credibility in Modern Machine Learningcited by 496
  7. 2019The generalization error of random features regression: Precise asymptotics and double descent curvecited by 413
  8. 2014In Search of the Real Inductive Bias: On the Role of Implicit Regularization in Deep Learningcited by 342
  9. 2018Characterizing Implicit Bias in Terms of Optimization Geometrycited by 266
  10. 2021Deep learning: a statistical viewpointcited by 240
  11. 2019Two models of double descent for weak featurescited by 195
  12. 2018To understand deep learning we need to understand kernel learningcited by 187
32 more
  1. 2020Benign overfitting in ridge regressioncited by 153
  2. 2016A vector-contraction inequality for Rademacher complexitiescited by 142
  3. 2020Evaluation of Neural Architectures Trained with Square Loss vs Cross-Entropy in Classification Taskscited by 138
  4. 2021Fit without fear: remarkable mathematical phenomena of deep learning through the prism of interpolationcited by 132
  5. 2019Harmless interpolation of noisy data in regressioncited by 121
  6. 2018Convergence of Gradient Descent on Separable Datacited by 110
  7. 2020On the Optimal Weighted ℓ2 Regularization in Overparameterized Linear Regressioncited by 98
  8. 2020Classification vs regression in overparameterized regimes: Does the loss function matter?cited by 97
  9. 2019A Model of Double Descent for High-dimensional Binary Linear Classificationcited by 81
  10. 2020Finite-sample Analysis of Interpolating Linear Classifiers in the Overparameterized Regimecited by 81
  11. 2021Label-Imbalanced and Group-Sensitive Classification under Overparameterizationcited by 74
  12. 2018The jamming transition as a paradigm to understand the loss landscape of deep neural networkscited by 62
  13. 2020Asymptotics of Ridge (less) Regression under General Source Conditioncited by 62
  14. 2021A Farewell to the Bias-Variance Tradeoff? An Overview of the Theory of Overparameterized Machine Learningcited by 57
  15. 2018Optimal ridge penalty for real-world high-dimensional data can be zero or negative due to the implicit ridge regularizationcited by 53
  16. 2016Squared Earth Mover's Distance-based Loss for Training Deep Neural Networkscited by 45
  17. 2021Benign Overfitting in Multiclass Classification: All Roads Lead to Interpolationcited by 42
  18. 2022The Implicit Bias of Benign Overfittingcited by 38
  19. 2019More Data Can Hurt for Linear Regression: Sample-wise Double Descentcited by 37
  20. 2019The Impact of Regularization on High-dimensional Logistic Regressioncited by 35
  21. 2019Sampled Softmax with Random Fourier Featurescited by 33
  22. 2020On the proliferation of support vectors in high dimensionscited by 32
  23. 2020Theoretical Insights Into Multiclass Classification: A High-dimensional Asymptotic Viewcited by 32
  24. 2020Analytic Study of Double Descent in Binary Classification: The Impact of Losscited by 28
  25. 2019Understanding overfitting peaks in generalization error: Analytical risk curves for l2 and l1 penalized interpolationcited by 23
  26. 2016Structured Prediction Theory Based on Factor Graph Complexitycited by 18
  27. 2015Multi-class SVMs: From Tighter Data-Dependent Generalization Bounds to Novel Algorithmscited by 14
  28. 2016Multiclass Classification Calibration Functionscited by 13
  29. 2019Visualising Basins of Attraction for the Cross-Entropy and the Squared Error Neural Network Loss Functionscited by 13
  30. 2020Sharp Asymptotics and Optimal Performance for Inference in Binary Modelscited by 13
  31. 2020Fundamental Limits of Ridge-Regularized Empirical Risk Minimization in High Dimensionscited by 13
  32. 2019A New Look at an Old Problem: A Universal Learning Approach to Linear Regressioncited by 11

Built on by

Cited by year

Citing papers per year: 2023: 4; 2024: 3; 2025: 1.

8 papers.

  1. 2024Provable Weak-to-Strong Generalization via Benign Overfittingcited by 16
  2. 2023Domain-Guided Conditional Diffusion Model for Unsupervised Domain Adaptationcited by 9
  3. 2024Can DPO Learn Diverse Human Values? A Theoretical Scaling Lawcited by 7
  4. 2023General Loss Functions Lead to (Approximate) Interpolation in High Dimensionscited by 4
  5. 2023Precise Asymptotic Generalization for Multiclass Classification with Overparameterized Linear Modelscited by 3
  6. 2025How Well Can Preference Optimization Generalize Under Noisy Feedback?cited by 3
  7. 2024One-Bit Quantization and Sparsification for Multiclass Linear Classification with Strong Regularizationcited by 1
  8. 2023Diffusion-based Target Sampler for Unsupervised Domain Adaptationcited by 0