mlsanityData to 7 Oct 2026

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

arXiv 2006.06560 ↗First posted 11 Jun 2020stat.ML cond-mat.dis-nn cs.LGcited by 51

Not on the map. Why?

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.

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

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 8; 2022: 7; 2023: 11; 2024: 14; 2025: 8; 2026: 3.

51 papers.

Sort:

  1. 2021Learning curves of generic features maps for realistic datasets with a teacher-student modelcited by 126
  2. 2021Label-Imbalanced and Group-Sensitive Classification under Overparameterizationcited by 74
  3. 2022Universality of empirical risk minimizationcited by 73
  4. 2021A Farewell to the Bias-Variance Tradeoff? An Overview of the Theory of Overparameterized Machine Learningcited by 54
  5. 2021Benign Overfitting in Multiclass Classification: All Roads Lead to Interpolationcited by 41
  6. 2023Bayes-optimal Learning of Deep Random Networks of Extensive-widthcited by 41
  7. 2021Graph-based Approximate Message Passing Iterationscited by 35
  8. 2024Asymptotics of feature learning in two-layer networks after one gradient-stepcited by 35
  9. 2024A phase transition between positional and semantic learning in a solvable model of dot-product attentioncited by 30
  10. 2022Gaussian Universality of Perceptrons with Random Labelscited by 26
  11. 2021Phase Transitions in Transfer Learning for High-Dimensional Perceptronscited by 21
  12. 2023High-dimensional Asymptotics of Denoising Autoencoderscited by 19
38 more
  1. 2022Theoretical characterization of uncertainty in high-dimensional linear classificationcited by 18
  2. 2022Error Scaling Laws for Kernel Classification under Source and Capacity Conditionscited by 17
  3. 2022Learning curves for the multi-class teacher-student perceptroncited by 17
  4. 2024Fundamental computational limits of weak learnability in high-dimensional multi-index modelscited by 17
  5. 2022On double-descent in uncertainty quantification in overparametrized modelscited by 15
  6. 2023Fundamental limits of overparametrized shallow neural networks for supervised learningcited by 12
  7. 2024High-dimensional learning of narrow neural networkscited by 12
  8. 2025The Nuclear Route: Sharp Asymptotics of ERM in Overparameterized Quadratic Networkscited by 11
  9. 2021Sharp global convergence guarantees for iterative nonconvex optimization: A Gaussian process perspectivecited by 10
  10. 2023The Underlying Scaling Laws and Universal Statistical Structure of Complex Datasetscited by 9
  11. 2023Regularized Linear Regression for Binary Classificationcited by 7
  12. 2021Performance of Bayesian linear regression in a model with mismatchcited by 6
  13. 2023Lower Generalization Bounds for GD and SGD in Smooth Stochastic Convex Optimizationcited by 6
  14. 2023Random Matrix Analysis to Balance between Supervised and Unsupervised Learning under the Low Density Separation Assumptioncited by 6
  15. 2024A Comprehensive Analysis on the Learning Curve in Kernel Ridge Regressioncited by 6
  16. 2025Statistical Advantage of Softmax Attention: Insights from Single-Location Regressioncited by 6
  17. 2023High-dimensional Asymptotics of VAEs: Threshold of Posterior Collapse and Dataset-Size Dependence of Rate-Distortion Curvecited by 5
  18. 2024A High Dimensional Statistical Model for Adversarial Training: Geometry and Trade-Offscited by 5
  19. 2022On how to avoid exacerbating spurious correlations when models are overparameterizedcited by 4
  20. 2023Asymptotic Bayes risk of semi-supervised multitask learning on Gaussian mixturecited by 4
  21. 2024High-dimensional logistic regression with missing data: Imputation, regularization, and universalitycited by 4
  22. 2024Asymptotic generalization error of a single-layer graph convolutional networkcited by 3
  23. 2024Asymptotic Dynamics of Alternating Minimization for Bilinear Regressioncited by 3
  24. 2026A Boundary-Layer Mechanism for One-Third Scaling in Online Softmax Classificationcited by 3
  25. 2024On the Geometry of Regularization in Adversarial Training: High-Dimensional Asymptotics and Generalization Boundscited by 2
  26. 2025Statistical physics analysis of graph neural networks: Approaching optimality in the contextual stochastic block modelcited by 2
  27. 2025Implicit bias produces neural scaling laws in learning curves, from perceptrons to deep networkscited by 2
  28. 2025Generalization performance of narrow one-hidden layer networks in the teacher-student settingcited by 2
  29. 2025Pseudo-likelihood produces associative memories able to generalize, even for asymmetric couplingscited by 2
  30. 2023Asymptotic Characterisation of Robust Empirical Risk Minimisation Performance in the Presence of Outlierscited by 1
  31. 2024Stability of a Generalized Debiased Lasso with Applications to Resampling-Based Variable Selectioncited by 1
  32. 2024Dimension-free uniform concentration bound for logistic regressioncited by 1
  33. 2024Statistical Mechanics of Min-Max Problemscited by 1
  34. 2025On the Existence of Consistent Adversarial Attacks in High-Dimensional Linear Classificationcited by 1
  35. 2025Breaking the curse of dimensionality for linear rules: optimal predictors over the ellipsoidcited by 1
  36. 2023The Generalization Error of Stochastic Mirror Descent on Over-Parametrized Linear Modelscited by 0
  37. 2024Analysis of High-dimensional Gaussian Labeled-unlabeled Mixture Model via Message-passing Algorithmcited by 0
  38. 2026Generalization Bounds of Stochastic Gradient Descent in Homogeneous Neural Networkscited by 0

50 most cited of 51 All 51 (JSON)