Generalization error in high-dimensional perceptrons: Approaching Bayes error with convex optimization

Abstract

We consider a commonly studied supervised classification of a synthetic dataset whose labels are generated by feeding a one-layer neural network with random iid inputs. We study the generalization performances of standard classifiers in the high-dimensional regime where $\alpha =n/d$ is kept finite in the limit of a high dimension $d$ and number of samples $n$. Our contribution is three-fold: First, we prove a formula for the generalization error achieved by ${\ell }_2$ regularized classifiers that minimize a convex loss. This formula was first obtained by the heuristic replica method of statistical physics. Secondly, focussing on commonly used loss functions and optimizing the ${\ell }_2$ regularization strength, we observe that while ridge regression performance is poor, logistic and hinge regression are surprisingly able to approach the Bayes-optimal generalization error extremely closely. As $\alpha \to \infty$ they lead to Bayes-optimal rates, a fact that does not follow from predictions of margin-based generalization error bounds. Third, we design an optimal loss and regularizer that provably leads to Bayes-optimal generalization error.

arXiv comment11 pages + 45 pages Supplementary Material / 5 figures, v2 revised and accepted at NeurIPS

Cited by in corpus (12)

• Learning curves of generic features maps for realistic datasets with a teacher-student model
• Triple descent and the two kinds of overfitting: Where & why do they appear?
• Gaussian Universality of Perceptrons with Random Labels
• Learning curves for the multi-class teacher-student perceptron
• Phase Transitions in Transfer Learning for High-Dimensional Perceptrons
• Benign Overfitting in Multiclass Classification: All Roads Lead to Interpolation
• A Farewell to the Bias-Variance Tradeoff? An Overview of the Theory of Overparameterized Machine Learning
• Strong replica symmetry for high-dimensional disordered log-concave Gibbs measures
• Theoretical characterization of uncertainty in high-dimensional linear classification
• Error Scaling Laws for Kernel Classification under Source and Capacity Conditions
• High-dimensional Asymptotics of VAEs: Threshold of Posterior Collapse and Dataset-Size Dependence of Rate-Distortion Curve
• Sharp global convergence guarantees for iterative nonconvex optimization: A Gaussian process perspective