mlsanityData to 14 Oct 2026

Bayes-optimal learning of an extensive-width neural network from quadratically many samples

arXiv 2408.03733 ↗First posted 7 Aug 2024stat.ML cond-mat.dis-nn cs.ITcited by 23

Not on the map. Why?

Abstract (arXiv)

We consider the problem of learning a target function corresponding to a single hidden layer neural network, with a quadratic activation function after the first layer, and random weights. We consider the asymptotic limit where the input dimension and the network width are proportionally large. Recent work [Cui & al '23] established that linear regression provides Bayes-optimal test error to learn such a function when the number of available samples is only linear in the dimension. That work stressed the open challenge of theoretically analyzing the optimal test error in the more interesting regime where the number of samples is quadratic in the dimension. In this paper, we solve this challenge for quadratic activations and derive a closed-form expression for the Bayes-optimal test error. We also provide an algorithm, that we call GAMP-RIE, which combines approximate message passing with rotationally invariant matrix denoising, and that asymptotically achieves the optimal performance. Technically, our result is enabled by establishing a link with recent works on optimal denoising of extensive-rank matrices and on the ellipsoid fitting problem. We further show empirically that, in the absence of noise, randomly-initialized gradient descent seems to sample the space of weights, leading to zero training loss, and averaging over initialization leads to a test error equal to the Bayes-optimal one.

Key facts. Cited by 23 papers in the map (data through 14 Oct 2026). Builds on 42 of its 96 references that are in the map. First posted on arXiv 7 Aug 2024.

Builds on

42 of 96 references.

References · 42

  1. 2017Implicit Regularization in Matrix Factorizationcited by 322
  2. 2022Neural Networks can Learn Representations with Gradient Descentcited by 161
  3. 2020Towards Resolving the Implicit Bias of Gradient Descent for Matrix Factorization: Greedy Low-Rank Learningcited by 150
  4. 2023SGD learning on neural networks: leap complexity and saddle-to-saddle dynamicscited by 143
  5. 2015Statistical physics of inference: Thresholds and algorithmscited by 128
  6. 2017Theoretical insights into the optimization landscape of over-parameterized shallow neural networkscited by 128
  7. 2020Online stochastic gradient descent on non-convex losses from high-dimensional inferencecited by 119
  8. 2017Optimal Errors and Phase Transitions in High-Dimensional Generalized Linear Modelscited by 116
  9. 2018On the Power of Over-parametrization in Neural Networks with Quadratic Activationcited by 102
  10. 2019Notes on Computational Hardness of Hypothesis Testing: Predictions using the Low-Degree Likelihood Ratiocited by 85
  11. 2021Small random initialization is akin to spectral learning: Optimization and generalization guarantees for overparameterized low-rank matrix reconstructioncited by 78
  12. 2022Universality of empirical risk minimizationcited by 75
30 more
  1. 2018Phase Retrieval Under a Generative Priorcited by 73
  2. 2018Gradient Descent with Random Initialization: Fast Global Convergence for Nonconvex Phase Retrievalcited by 71
  3. 2023How Two-Layer Neural Networks Learn, One (Giant) Step at a Timecited by 68
  4. 2018The committee machine: Computational to statistical gaps in learning a two-layers neural networkcited by 58
  5. 2023On Learning Gaussian Multi-index Models with Gradient Flowcited by 57
  6. 2024The Benefits of Reusing Batches for Gradient Descent in Two-Layer Networks: Breaking the Curse of Information and Leap Exponentscited by 52
  7. 2015Solving Random Quadratic Systems of Equations Is Nearly as Easy as Solving Linear Systemscited by 50
  8. 2020Optimization and Generalization of Shallow Neural Networks with Quadratic Activation Functionscited by 50
  9. 2023Bayes-optimal Learning of Deep Random Networks of Extensive-widthcited by 41
  10. 2017Fundamental Limits of Weak Recovery with Applications to Phase Retrievalcited by 39
  11. 2020Phase retrieval in high dimensions: Statistical and computational phase transitionscited by 39
  12. 2021Graph-based Approximate Message Passing Iterationscited by 35
  13. 2017The landscape of the spiked tensor modelcited by 34
  14. 2016Statistical limits of spiked tensor modelscited by 28
  15. 2023Hitting the High-Dimensional Notes: An ODE for SGD learning dynamics on GLMs and multi-index modelscited by 26
  16. 2018Complex energy landscapes in spiked-tensor and simple glassy models: ruggedness, arrangements of local minima and phase transitionscited by 23
  17. 2021Stochasticity helps to navigate rough landscapes: comparing gradient-descent-based algorithms in the phase retrieval problemcited by 23
  18. 2023On the Impact of Overparameterization on the Training of a Shallow Neural Network in High Dimensionscited by 21
  19. 2019The spiked matrix model with generative priorscited by 20
  20. 2019Exact asymptotics for phase retrieval and compressed sensing with random generative priorscited by 20
  21. 2021On the Cryptographic Hardness of Learning Single Periodic Neuronscited by 20
  22. 2020Complex Dynamics in Simple Neural Networks: Understanding Gradient Flow in Phase Retrievalcited by 18
  23. 2019Mean-field inference methods for neural networkscited by 16
  24. 2019Stationary Points of Shallow Neural Networks with Quadratic Activation Functioncited by 12
  25. 2023Injectivity of ReLU networks: perspectives from statistical physicscited by 10
  26. 2021Solving phase retrieval with random initial guess is nearly as good as by spectral initializationcited by 9
  27. 2023Fitting an ellipsoid to random points: predictions using the replica methodcited by 7
  28. 2023Exact threshold for approximate ellipsoid fitting of random pointscited by 7
  29. 2022Matrix factorization with neural networkscited by 6
  30. 2023The Decimation Scheme for Symmetric Matrix Factorizationcited by 2

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2024: 3; 2025: 12; 2026: 8.

23 papers.

Sort:

By area:

  1. 2026There Will Be a Scientific Theory of Deep Learningcited by 29
  2. 2025Scaling Laws and Spectra of Shallow Neural Networks in the Feature Learning Regimecited by 20
  3. 2024High-dimensional learning of narrow neural networkscited by 12
  4. 2025The Nuclear Route: Sharp Asymptotics of ERM in Overparameterized Quadratic Networkscited by 11
  5. 2025From Kernels to Features: A Multi-Scale Adaptive Theory of Feature Learningcited by 10
  6. 2025Statistical mechanics of extensive-width Bayesian neural networks near interpolationcited by 9
  7. 2026Optimal scaling laws in learning hierarchical multi-index modelscited by 9
  8. 2025Information-theoretic reduction of deep neural networks to linear models in the overparametrized proportional regimecited by 6
  9. 2025Single-Head Attention in High Dimensions: A Theory of Generalization, Weights Spectra, and Scaling Lawscited by 6
  10. 2024On the phase diagram of extensive-rank symmetric matrix denoising beyond rotational invariancecited by 4
  11. 2024Bilinear Sequence Regression: A Model for Learning from Long Sequences of High-dimensional Tokenscited by 3
  12. 2025Bayes optimal learning of attention-indexed modelscited by 3
11 more
  1. 2025Generalization performance of narrow one-hidden layer networks in the teacher-student settingcited by 2
  2. 2025Overparametrization bends the landscape: BBP transitions at initialization in simple Neural Networkscited by 2
  3. 2025Optimal generalisation and learning transition in extensive-width shallow neural networks near interpolationcited by 1
  4. 2026Escape dynamics and implicit bias of one-pass SGD in overparameterized quadratic networkscited by 1
  5. 2026Factual recall in linear associative memories: sharp asymptotics and mechanistic insightscited by 1
  6. 2026Kernel Renormalization in Bayesian Deep Neural Networks: the Equivalent Wishart Ansatz in the Proportional Regimecited by 1
  7. 2025Information-Theoretic Criteria for Knowledge Distillation in Multimodal Learningcited by 0
  8. 2025Statistical physics of deep learning: Optimal learning of a multi-layer perceptron near interpolationcited by 0
  9. 2026Sharp feature-learning transitions and Bayes-optimal neural scaling laws in extensive-width networkscited by 0
  10. 2026Shortcomings and capacities of real-constrained neural networks in complex spacescited by 0
  11. 2026How Width and Data Shape Generalization Scaling Laws in Quadratic Neural Networkscited by 0