Research map / Learning theory and algorithms / Kernels and regression theory
Bayes-optimal learning of an extensive-width neural network from quadratically many samples
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Derives a closed-form Bayes-optimal MMSE for learning a one-hidden-layer extensive-width quadratic-activation network from quadratically many samples, and proposes GAMP-RIE, a polynomial-time algorithm that attains it.
Problem
Learning a teacher one-hidden-layer neural network with extensive width (m = kappa d) and quadratic activation from n = alpha d^2 samples; the Bayes-optimal test error in this regime was an open problem.
Approach
Reduce the learning task to a matrix generalized linear model on the Wishart matrix S* = (1/m) sum w_k w_k^T with Gaussian-equivalent sensing matrices, then combine GAMP with a rotationally-invariant (RIE) matrix denoiser whose free entropy is computed via HCIZ integrals, yielding a closed-form Bayes-optimal MMSE.
Key results
- Closed-form Bayes-optimal MMSE; in the noiseless case perfect recovery occurs at alpha_PR = kappa - kappa^2/2 for kappa <= 1 and 1/2 for kappa >= 1.
- GAMP-RIE state evolution fixed points match the Bayes-optimal prediction; finite-size experiments at d=100 and 200 agree well with theory for kappa=0.5.
- In the noiseless case, randomly initialized gradient descent yields test error about twice the Bayes-optimal MMSE, while averaging over initializations approaches the MMSE.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use GAMP-RIE for estimation | Wishart matrix GLM for the extensive-width quadratic network · Extensive-width quadratic network, α = n/d² and κ = m/d | MMSE | Helped |
| Average gradient-descent predictions over random initializations | Gradient descent on the noiseless quadratic network · Noiseless extensive-width quadratic network | MSE: twice larger than the asymptotic MMSE -> consistent with the MMSE | Helped |
| Average gradient-descent predictions over initializations | Gradient descent on the noisy quadratic network · Noisy extensive-width quadratic network | MSE | Mixed |
Surprising findings
- Randomly initialized gradient descent in the noiseless case gives roughly twice the Bayes-optimal error, resembling a Gibbs-estimator relation, and averaging over initializations recovers near-optimal error.
- No computational-to-statistical gap was identified for this model, unlike canonical phase retrieval (m=1).
Limitations
- Restricted to Gaussian inputs, i.i.d. Gaussian teacher weights, quadratic activation, and a single hidden layer.
- Main free-entropy derivation relies on the replica method; the rigorous route relies on two conjectures (universality and matrix GLM free entropy).
- Noisy-case gradient descent shows a gap from the MMSE even when averaged over initialization.
Experimental setup
Datasets: synthetic Gaussian teacher-student data
Benchmarks: synthetic teacher-student data
Metrics: mean squared error minimum mean squared error (MMSE)
Baselines: linear regression gradient descent (random initialization) averaged gradient descent
Builds on: GAMP rotationally invariant estimators for extensive-rank matrix denoising Cui et al. 2023 linear regression Bayes-optimality result ellipsoid fitting results
Closest papers by meaning
- Learning quadratic neural networks in high dimensions: SGD dynamics and scaling laws (NeurIPS 2025 · similarity 0.88)
- The Nuclear Route: Sharp Asymptotics of ERM in Overparameterized Quadratic Networks (NeurIPS 2025 · similarity 0.87)
- A Study of Bayesian Neural Network Surrogates for Bayesian Optimization (ICLR 2024 · similarity 0.86)
- Sharper Guarantees for Learning Neural Network Classifiers with Gradient Methods (ICLR 2025 · similarity 0.86)
- Can Neural Networks Achieve Optimal Computational-statistical Tradeoff? An Analysis on Single-Index Model (ICLR 2025 · similarity 0.85)
- Training Bayesian Neural Networks with Sparse Subspace Variational Inference (ICLR 2024 · similarity 0.85)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.