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

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

## Key facts

- Cited by 51 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 11 Jun 2020.

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

- [Learning curves of generic features maps for realistic datasets with a teacher-student model](https://mlsanity.com/paper/2102.08127/) (2021)
- [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)
- [A Farewell to the Bias-Variance Tradeoff? An Overview of the Theory of Overparameterized Machine Learning](https://mlsanity.com/paper/2109.02355/) (2021)
- [Benign Overfitting in Multiclass Classification: All Roads Lead to Interpolation](https://mlsanity.com/paper/2106.10865/) (2021)
- [Bayes-optimal Learning of Deep Random Networks of Extensive-width](https://mlsanity.com/paper/2302.00375/) (2023)
- [Asymptotics of feature learning in two-layer networks after one gradient-step](https://mlsanity.com/paper/2402.04980/) (2024)
- [Graph-based Approximate Message Passing Iterations](https://mlsanity.com/paper/2109.11905/) (2021)
- [A phase transition between positional and semantic learning in a solvable model of dot-product attention](https://mlsanity.com/paper/2402.03902/) (2024)
- [Gaussian Universality of Perceptrons with Random Labels](https://mlsanity.com/paper/2205.13303/) (2022)
- [Phase Transitions in Transfer Learning for High-Dimensional Perceptrons](https://mlsanity.com/paper/2101.01918/) (2021)
- [High-dimensional Asymptotics of Denoising Autoencoders](https://mlsanity.com/paper/2305.11041/) (2023)
- [Fundamental computational limits of weak learnability in high-dimensional multi-index models](https://mlsanity.com/paper/2405.15480/) (2024)
- [Theoretical characterization of uncertainty in high-dimensional linear classification](https://mlsanity.com/paper/2202.03295/) (2022)
- [Error Scaling Laws for Kernel Classification under Source and Capacity Conditions](https://mlsanity.com/paper/2201.12655/) (2022)
- [Learning curves for the multi-class teacher-student perceptron](https://mlsanity.com/paper/2203.12094/) (2022)
- [On double-descent in uncertainty quantification in overparametrized models](https://mlsanity.com/paper/2210.12760/) (2022)
- [Fundamental limits of overparametrized shallow neural networks for supervised learning](https://mlsanity.com/paper/2307.05635/) (2023)
- [High-dimensional learning of narrow neural networks](https://mlsanity.com/paper/2409.13904/) (2024)
- [The Nuclear Route: Sharp Asymptotics of ERM in Overparameterized Quadratic Networks](https://mlsanity.com/paper/2505.17958/) (2025)
- [Sharp global convergence guarantees for iterative nonconvex optimization: A Gaussian process perspective](https://mlsanity.com/paper/2109.09859/) (2021)
- [The Underlying Scaling Laws and Universal Statistical Structure of Complex Datasets](https://mlsanity.com/paper/2306.14975/) (2023)
- [Regularized Linear Regression for Binary Classification](https://mlsanity.com/paper/2311.02270/) (2023)
- [A High Dimensional Statistical Model for Adversarial Training: Geometry and Trade-Offs](https://mlsanity.com/paper/2402.05674/) (2024)
- [A Comprehensive Analysis on the Learning Curve in Kernel Ridge Regression](https://mlsanity.com/paper/2410.17796/) (2024)
- [Statistical Advantage of Softmax Attention: Insights from Single-Location Regression](https://mlsanity.com/paper/2509.21936/) (2025)
- [Performance of Bayesian linear regression in a model with mismatch](https://mlsanity.com/paper/2107.06936/) (2021)
- [Lower Generalization Bounds for GD and SGD in Smooth Stochastic Convex Optimization](https://mlsanity.com/paper/2303.10758/) (2023)
- [Random Matrix Analysis to Balance between Supervised and Unsupervised Learning under the Low Density Separation Assumption](https://mlsanity.com/paper/2310.13434/) (2023)
- [High-dimensional Asymptotics of VAEs: Threshold of Posterior Collapse and Dataset-Size Dependence of Rate-Distortion Curve](https://mlsanity.com/paper/2309.07663/) (2023)

## Abstract (arXiv)

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 α=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 ℓ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 ℓ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 α → ∞ 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.