A model of double descent for high-dimensional binary linear classification. (3rd April 2021)

• Record Type: Journal Article
• Authors: Deng, Zeyu; Kammoun, Abla; Thrampoulidis, Christos
• Is Part Of: Information and inference. Volume 11:Number 2(2022)
• Page Start: 435
• Page End: 495
• Publication Date: 2021-04-03
• Subjects: sharp asymptotics -- empirical risk minimization -- hard-margin SVM -- overparameterization -- Gaussian process inequalities; Mathematical models -- Periodicals; 519.605
• DOI: 10.1093/imaiai/iaab002
• Languages: English
• ISSNs: 2049-8764

Abstract

Abstract: 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 on logistic loss. For this model, we investigate the dependence of the classification error on the ratio $\kappa =p/n$ . First, building on known deterministic results on the implicit bias of gradient descent, we uncover a phase-transition phenomenon for the case of Gaussian features: the classification error of the gradient descent solution is the same as that of the maximum-likelihood solution when $\kappa <\kappa _\star $, and that of the support vector machine when $\kappa>\kappa _\star $, where $\kappa _\star $ is a phase-transition threshold. Next, using the convex Gaussian min–max theorem, we sharply characterize the performance of both the maximum-likelihood and the support vector machine 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.