Perfect recovery threshold for unregularized quadratic-network training
Fix $0 < \kappa^* < \kappa < 1$ and $\alpha > 0$, and let $d \to \infty$ along integers $m^*, m, n$ with $m^*/d \to \kappa^*$, $m/d \to \kappa$ and $n/d^2 \to \alpha$. Draw independent teacher vectors $w_1^*, \dots, w_{m^*}^* \sim N(0, I_d)$ and set $Z^* = \frac{1}{m^*} \sum_{i=1}^{m^*} w_i^* w_i^{*\top}$. Independently, draw $n$ independent symmetric sensing matrices $X_k$ with independent entries $(X_k)_{ij} \sim N\bigl(0, (1 + \delta_{ij})/d\bigr)$ for $i \le j$, and observe the noiseless labels $z_k = \operatorname{Tr}(X_k Z^*)$. For $W \in \mathbb{R}^{d \times m}$ let $$\mathcal{L}_d(W) = \frac{1}{4n} \sum_{k=1}^{n} \bigl[\operatorname{Tr}(X_k W W^\top) - z_k\bigr]^2,$$ and run the unregularized gradient flow $\dot W = -d\, \nabla \mathcal{L}_d(W)$ from $W(0)$ with independent $N(0, 1/m)$ entries, drawn independently of the rest. Let $$R(\alpha; \kappa, \kappa^*) = \lim_{t \to \infty} \lim_{d \to \infty} \frac{1}{d}\, \mathbb{E}\, \|W(t) W(t)^\top - Z^*\|_F^2,$$ the expectation being over the teacher, the measurements and the initialization. Let $\sigma$ be the semicircle law, with density $\sqrt{4 - x^2}/(2\pi)$ on $[-2, 2]$, let $\omega \in (-2, 2)$ satisfy $\sigma([\omega, 2]) = (\kappa - \kappa^*)/(1 - \kappa^*)$, and set $$a_{\mathrm{inter}} = \kappa^* - \frac{(\kappa^*)^2}{2} + \frac{(1 - \kappa^*)^2}{2} \int_{\max(0, \omega)}^{2} x^2 \, d\sigma(x), \qquad a_{\mathrm{PR}} = \min\Bigl\{\kappa - \frac{\kappa^2}{2},\ a_{\mathrm{inter}}\Bigr\}.$$ The sensing matrices stand in for $(x_k x_k^\top - I_d)/\sqrt{d}$ with standard Gaussian inputs $x_k$, which makes this a two-layer network with quadratic activation trained on a teacher network. Martin, Biroli and Bach derived, by non-rigorous dynamical mean-field methods and a simplifying assumption on the long-time dynamics, the vanishing-regularization limit of $\ell_2$-regularized gradient flow, whose perfect-recovery threshold is a different value; $a_{\mathrm{inter}}$ is their interpolation threshold there, and $\kappa - \kappa^2/2$ is the normalized dimension of the set of positive semidefinite matrices of rank $\lfloor \kappa d \rfloor$. From numerical simulations they conjectured that $a_{\mathrm{PR}}$ is the perfect-recovery threshold of the unregularized flow.
Problem. Is $R(\alpha; \kappa, \kappa^*) = 0$ for every $\alpha > a_{\mathrm{PR}}$ and $R(\alpha; \kappa, \kappa^*) > 0$ for every $0 < \alpha < a_{\mathrm{PR}}$? Proving that the limits defining $R$ exist is part of the problem; nothing is asked at $\alpha = a_{\mathrm{PR}}$.
Source: Martin, Biroli and Bach (2026), Conjecture 15 (Conjecture 11 in arXiv:2601.10483v2). Stated by AIM — Open Applied Problems for a Gaussian teacher and initialization with 0 < κ* < κ < 1, with the threshold made precise.
Imported from github.com/MColbrook/AIM.
Classification
- Primary
- PR — Probability
- Secondary
- OC, ST
- Keywords
- AIM Open Applied Problems, gradient flows, matrix sensing, quadratic neural networks
References
@article{martin2026,
author = {Martin, Simon and Biroli, Giulio and Bach, Francis},
title = {High-dimensional analysis of gradient flow for extensive-width quadratic neural networks},
journal = {J. Mach. Learn. Res.},
volume = {27},
number = {136},
year = {2026},
pages = {1--182},
url = {https://www.jmlr.org/papers/v27/26-0672.html},
eprint = {2601.10483},
archivePrefix = {arXiv},
}
@misc{aim-quadratic-network-recovery-threshold,
author = {Brunton, Steve and Colbrook, Matthew J. and de Hoop, Maarten V. and Stepaniants, George and Townsend, Alex and Ward, Rachel},
title = {{Perfect recovery threshold for unregularized quadratic-network training}},
howpublished = {AIM --- Open Applied Problems, GitHub repository},
year = {2026},
url = {https://github.com/MColbrook/AIM/blob/a153f469ee0ea64e876b2ad97c79d252c19a3e22/problems/550-quadratic-network-recovery-threshold.md},
note = {Entry 550 at commit a153f46, 2026-10-13},
}
Citing this problem
This identifier is permanent. It will not change if the problem is solved, reclassified or withdrawn.
OP-00300, "Perfect recovery threshold for unregularized quadratic-network training", clopen.solutions.