Research map / Learning theory and algorithms / Matrix and tensor methods
The Nuclear Route: Sharp Asymptotics of ERM in Overparameterized Quadratic Networks
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 sharp asymptotics for ERM training and test error in over-parameterized two-layer quadratic networks on quadratic-teacher synthetic data, by mapping the problem to nuclear-norm-regularized matrix sensing solved via AMP.
Problem
Precise characterization of training and generalization error of ERM (l2-regularized) in over-parameterized two-layer quadratic-activation networks trained on data generated by a quadratic teacher, in the regime n = Θ(d²) and extensive width.
Approach
Maps the nonlinear weight-decay ERM problem to a convex PSD matrix estimation problem with nuclear-norm penalty, replaces the quadratic sensing matrices with GOE (Gaussian universality), and solves the resulting problem with a non-separable-denoiser AMP whose state evolution gives closed-form test/train error, interpolation threshold and strong recovery threshold.
Key results
- Asymptotic test error and training loss match finite-size gradient descent simulations at d=300 (noiseless, kappa*=0.2), with close agreement even at small test error.
- Interpolation threshold alpha_inter tends to 1/4 for Delta to infinity and to (1/4)(1+2kappa*-kappa*^2) for 0<kappa*<1 as Delta->0.
- Strong recovery threshold alpha_strong is given by a closed form in semicircle incomplete moments, with 1/2 for kappa* >= 1.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Increase the rescaled sample ratio from baralpha ≤ 1/2 to baralpha ≥ 3 | Quadratic-network ERM in the κ*→0, Δ=0, λ→0+ limit · Rescaled sample ratio baralpha | test error: 1 -> 0 | Helped |
| Increase student width κ while keeping κ ≥ 1 | Quadratic-network ERM · High-dimensional learning problem | test error | No clear effect |
| Use a low-rank target, κ*→0, with Δ=0 and λ→0+ | Quadratic-network ERM · Rescaled sample ratio baralpha ≥ 3 | test error: 1 -> 0 | Helped |
Surprising findings
- The interpolation threshold depends on the target spectrum (target width) rather than only on the parameter count, reaching strong recovery well before the interpolator set shrinks to a point for small kappa*.
- A previously published conjecture for the interpolation threshold for generic target width m* is incompatible with the derived results and is judged incorrect in the extensive-width regime.
Limitations
- Restricted to Gaussian (or universal) random inputs, quadratic activation and single hidden layer.
- Theory requires width m >= d; for narrower students the rank constraint makes the convex reduction fail.
- Rigorous statement for lambda = 0 with alpha below the interpolation threshold is not covered; only the lambda->0+ limit is handled via rescaling.
Experimental setup
Datasets: synthetic Gaussian inputs with quadratic-network teacher labels
Metrics: test error training loss singular value density interpolation threshold strong recovery threshold
Baselines: Bayes-optimal estimator gradient descent on the original network LBFGS on the original network
Builds on: approximate message passing replica method ellipsoid fitting Gaussian universality
Closest papers by meaning
- Learning quadratic neural networks in high dimensions: SGD dynamics and scaling laws (NeurIPS 2025 · similarity 0.89)
- Bayes-optimal learning of an extensive-width neural network from quadratically many samples (NeurIPS 2024 · similarity 0.87)
- On the Explicit Role of Initialization on the Convergence and Implicit Bias of Overparametrized Linear Networks (ICML 2021 · similarity 0.87)
- How Over-Parameterization Slows Down Gradient Descent in Matrix Sensing: The Curses of Symmetry and Initialization (ICLR 2024 · similarity 0.86)
- Globally Q-linear Gauss-Newton Method for Overparameterized Non-convex Matrix Sensing (NeurIPS 2024 · similarity 0.86)
- Neural network learns low-dimensional polynomials with SGD near the information-theoretic limit (NeurIPS 2024 · similarity 0.86)
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.