# A Model of Double Descent for High-dimensional Binary Linear Classification

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

## Key facts

- Cited by 81 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 13 Nov 2019.

## Built on by (most cited first, 30 of 81)

- [Universality of empirical risk minimization](https://mlsanity.com/paper/2202.08832/) (2022)
- [Label-Imbalanced and Group-Sensitive Classification under Overparameterization](https://mlsanity.com/paper/2103.01550/) (2021)
- [Classifying high-dimensional Gaussian mixtures: Where kernel methods fail and neural networks succeed](https://mlsanity.com/paper/2102.11742/) (2021)
- [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)
- [Uniform Convergence of Interpolators: Gaussian Width, Norm Bounds, and Benign Overfitting](https://mlsanity.com/paper/2106.09276/) (2021)
- [Benign Overfitting in Multiclass Classification: All Roads Lead to Interpolation](https://mlsanity.com/paper/2106.10865/) (2021)
- [Implicit Bias of Spectral Descent and Muon on Multiclass Separable Data](https://mlsanity.com/paper/2502.04664/) (2025)
- [Towards an Understanding of Benign Overfitting in Neural Networks](https://mlsanity.com/paper/2106.03212/) (2021)
- [Are Gaussian data all you need? Extents and limits of universality in high-dimensional generalized linear estimation](https://mlsanity.com/paper/2302.08923/) (2023)
- [The good, the bad and the ugly sides of data augmentation: An implicit spectral regularization perspective](https://mlsanity.com/paper/2210.05021/) (2022)
- [Interpolating Classifiers Make Few Mistakes](https://mlsanity.com/paper/2101.11815/) (2021)
- [Fast Rates for Noisy Interpolation Require Rethinking the Effects of Inductive Bias](https://mlsanity.com/paper/2203.03597/) (2022)
- [The Interplay Between Implicit Bias and Benign Overfitting in Two-Layer Linear Networks](https://mlsanity.com/paper/2108.11489/) (2021)
- [Model, sample, and epoch-wise descents: exact solution of gradient flow in the random feature model](https://mlsanity.com/paper/2110.11805/) (2021)
- [Optimistic Rates: A Unifying Theory for Interpolation Learning and Regularization in Linear Regression](https://mlsanity.com/paper/2112.04470/) (2021)
- [On double-descent in uncertainty quantification in overparametrized models](https://mlsanity.com/paper/2210.12760/) (2022)
- [Interpolation can hurt robust generalization even when there is no noise](https://mlsanity.com/paper/2108.02883/) (2021)
- [Understanding the Learning Dynamics of Alignment with Human Feedback](https://mlsanity.com/paper/2403.18742/) (2024)
- [Implicit Optimization Bias of Next-Token Prediction in Linear Models](https://mlsanity.com/paper/2402.18551/) (2024)
- [On the interplay between data structure and loss function in classification problems](https://mlsanity.com/paper/2103.05524/) (2021)
- [Monotonicity and Double Descent in Uncertainty Estimation with Gaussian Processes](https://mlsanity.com/paper/2210.07612/) (2022)
- [A Non-Asymptotic Moreau Envelope Theory for High-Dimensional Generalized Linear Models](https://mlsanity.com/paper/2210.12082/) (2022)
- [Classification of Heavy-tailed Features in High Dimensions: a Superstatistical Approach](https://mlsanity.com/paper/2304.02912/) (2023)
- [Differentially Private Regression with Unbounded Covariates](https://mlsanity.com/paper/2202.11199/) (2022)
- [Multiple Descent in the Multiple Random Feature Model](https://mlsanity.com/paper/2208.09897/) (2022)
- [Preventing Model Collapse Under Overparametrization: Optimal Mixing Ratios for Interpolation Learning and Ridge Regression](https://mlsanity.com/paper/2509.22341/) (2025)
- [Generalization for multiclass classification with overparameterized linear models](https://mlsanity.com/paper/2206.01399/) (2022)
- [Deep Linear Networks can Benignly Overfit when Shallow Ones Do](https://mlsanity.com/paper/2209.09315/) (2022)
- [Regularized Linear Regression for Binary Classification](https://mlsanity.com/paper/2311.02270/) (2023)

## Abstract (arXiv)

We consider a model for logistic regression where only a subset of features of size p is used for training a linear classifier over n training samples. The classifier is obtained by running gradient descent (GD) on logistic loss. For this model, we investigate the dependence of the classification error on the overparameterization ratio kappa=p/n. First, building on known deterministic results on the implicit bias of GD, we uncover a phase-transition phenomenon for the case of Gaussian features: the classification error of GD is the same as that of the maximum-likelihood (ML) solution when kappa<kappa_star, and that of the max-margin (SVM) solution when kappa>kappa_star. Next, using the convex Gaussian min-max theorem (CGMT), we sharply characterize the performance of both the ML and the SVM solutions. Combining these results, we obtain curves that explicitly characterize the classification error for varying values of kappa. The numerical results validate the theoretical predictions and unveil double-descent phenomena that complement similar recent findings in linear regression settings as well as empirical observations in more complex learning scenarios.