The Nuclear Route: Sharp Asymptotics of ERM in Overparameterized Quadratic Networks
Authors: Vittorio Erba
Emanuele Troiani
Lenka Zdeborova
Florent Krzakala
Venue: NeurIPS 2025 poster ()
Keywords: neural networks
quadratic activation
global minima
nuclear norm
regularisation
Primary area: theory
TL;DR: We study the high-dimensional asymptotics of empirical risk minimization (ERM) in over-parametrized two-layer neural networks with quadratic activations trained on synthetic data.

Abstract: We study the high-dimensional asymptotics of empirical risk minimization (ERM) in over-parametrized two-layer neural networks with quadratic activations trained on synthetic data. We derive sharp asymptotics for both training and test errors by mapping the $\ell_2$-regularized learning problem to a convex matrix sensing task with nuclear norm penalization.  This reveals that capacity control in such networks emerges from a low-rank structure in the learned feature maps. Our results characterize the global minima of the loss and yield precise generalization thresholds, showing how the width of the target function governs learnability. This analysis bridges and extends ideas from spin-glass methods, matrix factorization, and convex optimization and emphasizes the deep link between low-rank matrix sensing and learning in quadratic neural networks.

The Nuclear Route: Sharp Asymptotics of ERM in Overparameterized Quadratic Networks
Vittorio Erba
Emanuele Troiani
Statistical Physics of Computation Laboratory EPFL, Switzerland
Statistical Physics of Computation Laboratory EPFL, Switzerland
Lenka Zdeborová
Florent Krzakala
Statistical Physics of Computation Laboratory EPFL, Switzerland
Information, Learning & Physics Laboratory EPFL, Switzerland
Abstract
We study the high-dimensional asymptotics of empirical risk minimization (ERM) in over-parametrized two-layer neural networks with quadratic activations trained synthetic data. We derive sharp asymptoties for both training and test errors by mapping the ég-regularized learning problem to a convex matrix sensing task with nuclear norm penalization. This reveals that capacity control in such networks emerges from low-rank structure in the learned feature maps. Our results char- acterize the global minima of the loss and yield precise generalization thresholds, showing how the width of the target function governs learnability. This analysis bridges and extends ideas from spin-glass methods, matrix factorization, and con- vex optimization and emphasizes the deep link between low-rank matrix sensing and learning in quadratic neural networks.
Modern machine learning relics heavily on training highly over- poraparamtterized neural networks, which often generalize well despite having far more parameters than data points [Zhang et al., 2021] While it is known that large non-linear networks can approximate many functions [Cybenko, 1989], it remains unclear what these models actually learn in practice, and why training succeeds often. In particular, we lack a precise understanding of how the structure of the data and the target function affects learnability, and how many samples are needed. Developing such an understanding remains central theoretical challenge.
A promising route toward addressing these questions is to study models that go beyond the lin- car case already well understood, eg. [Lee et al., 2018, Ji and Telgarsky, 2019, Pesme et al., 2021]-while remaining simple enough for rigorous analysis. Two-layer networks with quadratic activations are then the next natural candidate that captures some nonlinear behavior while still allowing for mathematical treatment [Gamarnik al., 2019, Arjevani et al., 2025, Maillard et al., 2024]. On top of that working with synthetic data helps isolate the core mechanisms of learning and generalization [Mei et al., 2018, Aubin al., 2020, Mei and Montanari, 2022, Xiao et al., 2022, Damian et al., 2024], free from the confounding factors of real-world datasets.
In this paper, we thus study learning by empirical risk minimization with quadratic networks from data that also generated by a quadratic network. Consider a dataset = (xx", y "² where the data x" E Rd are standard Gaussian x" ~ (O Il) (though our results allow for some universality) for μ 1,..., n, and the labels y" E IR are generated by an unknown targer function fx(x). We aim at learning this unknown function using a quadratic neural network f(x; W) with number of
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

hidden unit m 2 d:
ÿ = f(x; W) =
W X Vd
(1)
k=
where o (u( u² //w.l///dis is the (centered) quadratic activation, and where we collect the first-layer weights Wi E I for & = 1, ...... : in the matrix W Rmxd We leam W by empirical risk minimization of the square loss with & regularization (or equivalently, weight decay):
W arg min L(W), where L(W)
+ +
(2)
Given the structure of the model, the considered quadratic neural network can represent any centered positive semi-definite quadratic form of the input data-but no more. In particular, functions involving higher-order nonlinearities cannot be captured and are effectively treated as noise by the learner. To focus on the regime where generalization is possible, we therefore choose a target function f that lies within the expressivity class of the model (1) (we will also refer to the model as the student while thinking about the target as the teacher):
y" = fx"" VA"", with (x;: =
W X vd
ok
where e"h ~ (0, 1) is an additional Gaussian label noise. As will shall see, our result will depend on W* only through the spectral density of S* = (W*)T / E Rddd, which needs to have a well-defined limit as d + oo.
We will work in the high-dimensiona. limit d -> oo with extensive-width target and quadratically many samples, i.e. the joint limit d, n, mm. m - +oo with
a a= n/d = 0(1, K = m 0(1, - x=m/d=
Our contributions. We provide exact characterization of training and generalization in over- parameterized two-layer neural networks with quadratic activations, in the high-dimensional limit with Gaussian data. Our main result (Theorem 1) gives closed-form expressions for the training loss, generalization error, and spectral properties of the global minima the regularized empirical risk (2), in the regime m/d 1, R² O()), and 0.
Our solution this problem connects three previously distinct lines of research that turn out to be related: the geometry and training dynamics of quadratic networks in teacher-student setups [Sarao Mannelli et al., 2020, Gamarnik et al., 2019, Martin et al., 2024a, Arjevani et al., 2025], recent advances in high-dimensional Bayesian analysis of networks with extensive width [Maillard and Bandcira, 2023, Maillard et al., 2024], and the role of implicit regularization matrix factoriza- tion [Gunasekar et al., 2017] and its connection to matrix compressed sensing and nuclear norm regularization [Recht et al., 2010, Fazel et al., 2008].
Concretely, we map the non-linear estimation problem for W in (2) to the linear one of estimating the matrix S = W W/ W/d e Rdxd, where, remarkably, the lg regularization on W translates into nuclear norm regularization on S. This reveals that the learning dynamics implicitly favor solutions f corresponding to narrow neural networks. We then study this equivalent matrix model by rigorous tools based on approximate message passing [Berthier et al., 2020, Gerbelot and Berthier, 2023] and their relation to convex optimization [Loureiro et al., 2021b]. Our main result is Theorem 1, an analytical prediction for the test error achieved by the ERM, where importantly the error does not depend on the value x as long as K > 1, thus describing potentially massively over- wee--paametrried models. Theorem allows us to answer range of questions function of K* (see Section 3).
1. Location of the interpolation threshold: How many samples n are needed to have only unique global minimum of (2) in the limit X = 0+, both in the noiseless and noisy case?
2. Generalization performance: How many samples needed to achieve perfect generaliza- tion with zero label noise?
3. Low-rank limit: What is the generalization performance in the limit x* << corresponding to low-rank target functions?

---

In this paper, we provide new sharp results focusing on the extensive width case, encompassing the full range of target widths and focusing in particular on the setting 0 < n² 1, previously unexplored.
Finally, we remark that while (2) is a priori non-convex, it has no non-global local minima [Arjevani et al., 2025], implying that if' a gradient- based algorithm converges to a minimum at all, it must converge to global one. Hence, our main result Theorem I provides a closed-form characterization of the behavior at convergence to minima of gradient-based algorithms for any strictly positive regularization X.
Further related work. Deriving exact formulas for two-layer networks in the
setting in high dimensions is classical problem that has been extensively studied over the past decades (e.g., [Gardner and Derrida, 1989, Bayati et al., 2010, Thrampoulidis et al., 2018, Barbier al., 2019, Montanari et al., 2023])- The case of a single hidden unit, or single-index model, has been widely explored and, for quadratic activations, reduces to phase retrieval [Mondelli and Montanari, 2018, Lu and Li, 2020, Maillard et al., 2020J. The case of a finite number of hidden units falls into the broader class of multi-index models, which has seen a surge of recent interest [Seung et al., 1992, Aubin et al., 2018, Damian et al., 2022, Bietti et al., 2025, Troiani et al., 2025, Bruna and Hsu, 2025, Montanari and Urbani, 2025]. When the number of directions becomes extensive (i.e., of order (d)) and for general activations, the problem has been studied for linearly-many samples = (dd) [Li and Sompolinsky. 2021, Cui et al., 2025, Pacelli et al., 2023, Bordelon and Pehlevan, 2023, Camilli et al., 2025]. It becomes significantly more challenging in the setting we consider here of quadratically-mant empirically [Cui et al., 2025] and heuristically [Barbier et al., 2025] in a few specific settings, but an asymptotically exact sharp characterization is still lacking.
samples = (d²). This more difficult regime has been explored
Significant progress, however, has recently been made for the quadratic networks in the Bayes- optimal, citrmatiion-thoreee optimal performance in the setting considered here, a result later rigorously proven in [Xu al., 2025]. These works build upon recent advances originating in the context of ellipsoid fitting [Maillard and Kunisky, 2024, Maillard and Bandeira. 2023], and leverage Gaussian universality principle that also underpins our approach [Goldt et al., 2022, Hu and Lu, 2022, Montanari and Saced, 2022, Dubova et al., 2023]. This allows to study the problem as a matrix denoising task [Bun et al., 2014, Troiani et al., 2022, Pourkamali and Macris, 2023a,b, Semerjian, 2024]. For empirical minimization instead, landscape properties have been studied in [Du and Lee, 2018, Venturi et al., 2019, Soltanolkotabi et al., 2019, Gamarnik et al., 2019, Sarao Mannelli et al., 2020, Arjevani et al., 2025], and gradient descent on the population loss has been discussed in [Martin et al., 2024b).
setting. In particular, [Maillard et al., 2024] computed the Bayes-
The concept of double descent (see e.g. [Belkin et al., 2019, Nakkiran et al., 2021)) has reshaped our understanding of the bias-variance trade-off, revealing that increasing model complexity can, counterintuitively. improve generalization. While many of these analyses have focused on linear or kernel regimes [Gerace al., 2020, Geiger et al., 2020. Belkin et al.. 2020, Mei and Montanari, 2022], our work instead provides sharp asymptotics for non-linear two-layer nets.
Our analysis for two-layer networks hinges on a mapping to matrix compressed sensing, low rank-matrix recovery. problem with nuclear norm regularization [Fazel et al., 2008]. The number of samples required for perfect recovery has been discussed in [Donoho et al., 2013, Oymak and Hassibi, 2016, Amelunxen et al., 2014]. Additionally, we leverage tools from Approximate Message Passing (AMP) theory. AMP has become tool of choice for the rigorous analysis of statistical inference problems and algorithms in high-dimension. It often allows to provides sharp asymptotic characterizations of both Bayesian and empirical risk minimization procedures in many models [Bayati and Montanari, 2011. Donoho and Montanari, 2016, Rangan et al.. 2016, Loureiro et al., 2021b, Viluechio et al., 2025]. In this work, we use AMP with separalee denoisers [Berthier et al., 2020, Gerbelot and Berthier, 2023] to prove rigorously our main formula, that can also be derived by the heuristic replica method, a non-rigorous technique from statistical physics [Mézard et al., 1987, Mezard and Montanari, 2009].
Setting and notations
We consider a dataset of n samples D = [xx*, (", } with x" E RRd and y E R. constructed as in (I). We remark that the assumption of Gaussian data could be relaxed in the same spirit as in [Xu
3

---

et al., 2025, Assumption 2.21, and denote by E the average of the training set. We will assume that the empirical spectral density of the matrix 5 = /W*> distribution Jr" with finite first and second moment as + oo with K m /d = O(1), and call Q' its second moment. As our running example, we will focus on the Marchenko-Pastin (MP) targer case, where the weights w' are such that the limiting distribution satisfies μ (z) V K PMP. (A..../VP/))))) where μM.P. the Marchenko- Pastur distribution [Marchenko and Pastur, 1967] with parameter (the asymptotic spectral distribution of A" A'AA///nn where A E R has i..d. zero-mean unit- variacee components), and Q = + k". For example, this is the case for w with i.i.d. components extracted from distribution with zero mean and unit variance, but we stress that our results hold also for deterministic targets, as well as targets with different spectral distributions.
E R converges to a limiting
We learn the dataset by empirical risk minimization on the loss (2), and unless stated otherwise, in this paper will always consider learning with m d. typically for m m'. We will measure the performance of the empirical risk estimator using the test error on the labels
1 Fxx - Crest (W) = 2
(5)
where the average is over a new test sample x with the same distribution as the training samples (notice that for the sake of the test error we do not add any label noise on the test label). The Bayes- optimal (BO) test error, i.e. the minimum test error achievable by any estimator (on average over the joint realization of the dataset and the target weights) is natural baseline. In the high-dimensional limit (4), the BO test error has been characterized [Maillard al., 2024]. We will always consider the nigh-dimensional limit (4).
2
Main theorem
Our main technical result is the characterization of the properties of the global minima of the empirical loss (2) in the high dimensional limit in terms of training and test error.
Theorem (Asymptotics of ERM (2), informal) Consider the setting of Section 1 with k 2 1. Define X VEA and μo μe² E ps.c..6. where E is the free convolution and pa.c.,ō V402 2²/ 22/(22)2²) the semicircle distribution of radius 28 for O. Call (ō,z) IR4, the unique solution of
40d = J Xe)
1 +00
where [a,
dx pa(x) bz) (6)
Q + A + 2nd 82 =1 =11-((0))J(6 Xe)
Then, for all values of a, k², A 0, A and k 2 1 any global minimum W of (2) satisfies
82 A
lim Eerest (W) = 2a0² d-000
lim d (EC(W) +o
-- (5, Xe).
= 42a
2
Moreover, if n² has compact support, then the empirical singular value density of W /md satisfies
lim E d0000
Σ 5(z-o;)
= I(x 0) [2xpu(22 + Xε)
(8)
where {a are the singular values of W/ /dd I is the indicator function and F3 is the c.d.f. of 33.
Sketch of the proof. The proof, detailed in Appendix A, proceeds as follows. We reduction of regularized version of the minimization (2) to the one of a positive semi-definite matrix estimation:
12
$ = arg min ((S), with E(S) = [x (S - + Vmd (AIr(S) +||S) (9)
Sz0
where we defined S* = W WWWWW" and X(x) = (xx /d, and where we have added Frobenius norm penalty of amplitude т. Notice that (9) is strongly convex for X, > 0, so that

---

109
1.2
Test error
10-1
A = 0.4
0.2
0.8
0.1
0.05
0.6
0.025
Theory
0.4
CVX (d 50)
10
CVX (d 100)
0.2
Bayes optimal
LBFGS (d 300)
0.00
0.05
0.10
0.15
0.20
0.25
0.30
0.0
0.2
0.4
0.6
0.8
Sample complexity a = n/dd
Sample complexity a n/d
Figure 1: Left: Test error of simulations of vanilla GD (crosses, error bars are the standard deviation over 16 realizations of the target/training set at d 300) compared with the results of Theorem
1 (lines) function of the number of samples n ad?, noiseless case A 0, n= = 0.2. We observe a perfect match, particularly striking in the regime of small test error. The purple line is the Bayes-optimal performance [Maillard et al., 2024]. Right: Test error of simulations of GD run with LBFGS on (2) (yellow dots, = 300) and of convex solver run on the equivalent convex matrix problem (9) (blue dots d = 50, purple d = 100 dots), for A = 0.5, n² = 0.2, and À = 0.02 and as a function of the number of samples n = adZ Error bars are the standard deviation over 16 realizations of the target/training set, compared with the result of Theorem 1 (gray line).
S unique. Under the mapping S(W) WWT //md, we have S S(W) for any (Frobenius regularized) solution of (2), due to the uniqueness of S. The second part is to use the Gaussian universality principle, that allows to replace each matrix (xx" - -L///Vd by a random Wigner matrix, following closely the steps of [Maillard et al., 2024, Xu et al., 2025]. This in turns reduces the problem to a rank-penalized matrix recovery problem with GOE(d) sensing matrices:
12
+ $ = arg min Es(S), with E(S) = Σ [T (S -')] + Vmd ( +|))) (10) S
The problem can then be studied in various way. For instance with the heuristic, but powerful, replica method technique from statistical physies (see for instance [Maillard and Kunisky, 2024]). To provide a rigorous approach, we use instead suitable Approximate Message Passing (AMP) algorithm with non-separable prior [Berthier et al., 2020, Gerbelot and Berthier, 2023], designed in such way its (unique) non-trivial fixed point is also the fixed point of projected gradient descent on (9) [Bayati al., 2010, Montanari et al., 2012, Loureiro al., 2021b], which by the convexity of (9) coincide with the unique S. We then write the state evolution of this AMP algorithm which gives us all the relevant characteristics of the minimizer. Simple manipulations of the state evolution equations, in the limit r + 0, lead the characterization (6).
Theorem provides an asymptotic result for train and test error, as well as a characterization of the singular values of the optimal neural network weights. It is of independent interest for the matrix compressed sensing problem (10) and extends directly to any strictly convex matrix problem.
A remarkable observation is that the & regularization over the weights W naturally translates to nuclear norm regularization in the equivalent matrix problem (the convexification of the minimum rank regularization), naturally favoring model weights configurations with effective lower width (i.e., implementable with fewer hidden units): a weight decay in W thus implies low nuclear norm of the matrix S.
Theorem also implies that the properties of the global minima do not depend on the network width m, as long as 2 d. This means that neural network with width y >> 1 will achieve the same test error as a much narrower network with x 1, when trained on the same data, provided that the regularization strength is appropriately matched. Theorem I thus described both mildly and massively over-paramen over-parametrized models since for very large x the number of learnable parameters will be not only much larger than the target function, but also can be much larger than the number of samples.
5

---

a = 0.3
= 0.55
Singolar value demiity
0.8
0.4
0.0
0.0
0.5
2.0
Singular values of W/ Vmnd
Singular values W Vind
Singular valurs of W/ 1mmd
Spectra of the singular values of W/ Vmd for n" = 0.2, A = 0.5, À = 0.02 and several values of a. The red line is the singular value density of the target 2xpp" 2x²p(x²²), the blue line is the density predicted by (8). The histogram in gray is computed on the singular values of 16 runs of LBFGS on experiments with d 400.
Figure 2:
We remark that our results can be extended to the setting where the second layer weights of the student are binary =1 with at least positive and d negative weights, see Appendix G.
Illustration of Theorem and the behavior of gradient descent. In Figure we compare the asymptotic results of Theorem I with numerical experiments at finite size run directly on the equivalent convex loss (9) (using the solver CVXPY [Diamond and Boyd, 2016, Agrawal et al., 2018]. We notice that despite the theoretical results being valid in the high-dimensional limit, they are in excellent agreement with simulation at sizes as moderate as d = 50. Details on the numerical experiments are given in Appendix
The mapping onto a matrix problem implies immediately that Theorem describes also the perfor- mance of gradient descent convergence. Indeed, [Arjevani et al., 2025, Theorem 12] implies that m 2 d. then the original minimization problem (2) has no local minima (in the language of [Arjevani al., 2025], it has no spurious valleys, which implies in our case absence of local minima). We verify this claim experimentally at finite size by running gradient descent (GD)
w/s w/s 1-1 V Wk, L(w)
(11)
initialized as w/s ~ ~N,0 (2) independently, with Φen = w", where T = 10 is fixed stopping time (we check that by time T GD has convincingly reached convergence) and a tuned learning rate (in Figure 1 right we used LBFGS for better convergence). We present our experiments in Figure Again, we observe a very nice agreement, surprisingly precise the region of small test error (notice the lcg-scale on the vertical axis in the left panel). We further test results by comparing the empirical spectra with our thcoretical prediction of equation (8) in Figure 2, observing a nice match.
Relation with kernel ridge regression. While the equivalent model (9) linear in the quadratic feature space x + T,Hi, out result departs significantly from the analysis of kernel ridge regression, random features regression and other linear methods studied in the literature (see e.g. [Gerace et al., 2020, Bordelon et al., 2020, Loureiro et al., 2021a la Mei and Montanari, 2022]). The crucial difference is in the regularization, which in (9) is non-separable regularization including the positive semi-definite construint, that takes into account the full spectral distribution of the target μ², while in the literature only the case &g regularization in feature space was usually studied explicitly (a separable regularization that takes into account only the second moment of the target Q", disregarding for example the low-width of the target function). Among the consequences of this, we find an interpolation threshold that, unexpectedly, depends the structure of the target function (Result 1).
Narrow students K" S K < We remark that Theorem applies as also to models with m for certain values of the parameters, i.c. for all choices of a, x X, A such that m/a = K > 1 F2(2). This is a consequence of the fact that the global minima of (2) for k 2 have rank F3(E) (see (8)), and thus are also global minima of the (2) for < 1 under the above condition. Lower than this value of K, the rank constraint imposed by the structure of the student network affects the global minima of the unconstrained (9), leading to non-convexity and to the failure of Theorem 1.

---

Test error (A 0)
Test error (A 0.5)
Train loss (A 0.5)
1.2
Optimal
0.1
0.6G
0
0.8
Bayre optimal
0.005
0:001
0.10
0.0005
0.4
2
Uptimal
0.0
0.00
0.00
0.06
0.10
0.2
0.3
0.4
0.4
Sumple complexity a n/df
Sample complexitt or = n//d
Sample complexily or o. n//d
Figure 3: (Left) The test error of any global minimum of (2) (Theorem 1) in the noiseless case A = 0, n* = 0.2 for finite regularization À = 0.4 (blue line), in the limit À - 0+ (yellow line) and for optimal regularization (dashed line). We compare with the Bayes-optimal performance [Maillard al., 2024] (purple line), and highlight the strong recovery threshold (vertical gray line, Corollary 1). (Center, Right) The test and train loss (2) in the noisy case A = 0.5, x² = 0.2 for several values of the regularization À (solid lines), À - 0+ (yellow line) and for optimal regularization (dashed line). We highlight the region of sample ratio a where non-regularized training loss goes to zero (before the vertical grey line, from Result 1), which coincides with the development of a cusp in the test error as À decreases.
Main results and consequences of Theorem 1
In this section focus specifically on the Marchenko-Pastte target case (see Section 1, details on the computation of μ in Result are given in Appendix E). We believe that our results generalize (qualitatively for the learning curves, and as is for the thresholds and the low-rank target limit) to any target such that μ has a finite spectral gap, i.e. such that Amin = min(æ E supp(H") ) >> 0} satisfies Amin O, with mass in zero equal to max(0, matrix [min( I)d and second moment Q* = 1 + n².
E²*) (i.e. rank of the associated target
Learning curves. In Figure we show the test and train error of any global minimum of the loss function (2) given by Theorem 1, both the noiseless (A 0) and noisy (A 0.5) scenarios. Details on the numerical experiments are given in Appendix E.
In the noiseless case (Figure 3 left), plot the test error functions of the sample ratio for finite regularization value (A = 0.4, blue line), in the limit of vanishing regularization (A + 0+,, yellow line), and for the optimal choice of regularization (dashed line). These are contrasted with the Bayes-op caytes-ptimmal performance as derived [Maillard et al., 2024] (purple line), clearly illustrating the effect of regularization the perfect recovery threshold, marked by the vertical gray line as per Corollary 1.
In the noisy case (Figure 3 center and right), we show both the test and train losses as functions of the sample ratio a for multiple values of (solid lines), including the minimum regularization interpolator limit (A - 0+, yellow line) and the optimally regularized scenario (dashed line). Notably, we highlight the specific region of a where the non-regularized training loss reaches zero (vertical gray line, as per Result 1), which coincides with the emergence of a cusp the double descent peak [Belkin et al., 2019, Nakkiran et al., 2021] - the test error as À decreases.
Interpolation threshold. We define the interpolation threshold Qinter (k* A) as the value of the sample ratio at which the set of PSD matrices S for which the loss (9) is zero for X = 0 (we call those the interpolators of the training dataset) shrinks single point. For thus has a single global minimum with positive training loss if A > O, or with both zero training and test loss if A O. For < Qiuter (r.". A) instead, the regulaaulr À == loss admits many global minima (all PSD interpolators), while the limit À + 0+ has still a single global minimum with zero training loss, and minimum value of the regularization norm. While we stated Theorem I for A > 0 it also holds, at least at an heuristic level, for Ointtr (x"ter(s", AA and X = O by directly plugging À
Qinter (x= A), (9)
(6). The theorem does not hold for X = and a < Ointer (k² A) while it can be adapted to the limit À + 0+ by careful rescaling, which we comment upon in Appendix B. A
7

---

direct consequence of Theorem 1 is theoretical characterization of the position of the interpolation threshold Ointer (1* A).
Result 1 (Interpolation threshold) Consider the setting of Section 1 for a Marchenko-Pastae larget. Then, the interpolation threshold Ointor (k* A) satisfies
8 Ointerr (K)))) 1 J(10) (8,0) + oa(1) where Q' Q+ = -
(0.00)----35500) (12)
where O1 denotes derivative w.r.t. the first argument, and was defined in (6). Additionally, we have
1 2x= x²² if 00- < K* <1 if R 2
1
lim Cinter (n² A) 4 A+
lim Oiner (k" A) (13)
Result is derived by considering the solution of the minimization problem (6) and setting = directly at large where there is unique minimum of (9) and then looking for the smallest value of consistent with a unique minimum assumption. Equivalently, this is when the asymptotics training loss reach zero (see Appendix C). We plot (13) in Figure 4. As discussed above, the interpolation threshold does not depend on the width of the student.
It is interesting to contrast our results with the ellipsoid-fittie
problem, where one seeks PSD matrix S such that a dataset of points {x"}==) lies on the surface of the associated ellipsoid. This problem, recently studied in a high-dimensional limit similar to (4) [Maillard and Kunisky, 2024, Maillard and Bandeira, 2023], predicts that fitting is possible as long as a < 1/4. We recover this
same threshold, Oinntrr = 1/4, in two extreme cases: when noise dominates (A - +o0) or when the target is vanishingly small (A = 0, K* + )+). In all other scemarios, however, the interpolation threshold is strictly larger, reflecting the structural advantage of the data over random labeling. Unlike linear ridge regression or kernel methods, the interpolation threshold here nontrivial and intricately linked to data structure. Notably, it is not simply determined by the ratio of samples to parameters. Despite the effective number of parameters scaling as O(d /2). interpolation can occur well before this count if the target function is sufficiently narrow (0- < K 1). This effect arises from the PSD constraint in the equivalent matrix problem (9), marking a fundamental departure from classic kernel theory.
We note that special cases this threshold has been considered in the literature, for n² 2 1 and A in [Gamarnik et al., 2019], and our result agrees with these works. An analogue of this threshold (still for = 0) has been considered in [Sarao Mannelli et al., 2020] for the case of low-width target m = 1, where the interpolation for the model with 2 happens at n = 2d. The authors conjecture without solid thcoretical justification that for generic m" the interpolation happens at d(m" + 1)- m² (m* 1)/2, which, however, is not compatible with our results. We conclude that their conjecture is incorrect in the regime m = Od(d). as it predicts interpolation for values lower than the rigorous 1/4 random labels threshold [Maillard and Bandeira, 2023, Maillard and Kunisky, 2024] as well.
Strong recovery threshold. A different phenomenon can be studied in the noiseless case A 0 and - 0+, i.e. what we call the strong recovery: the value of the sample ratio Ostronn (xx* = nstrong/ d such that, for strictly positive at A= = O. Notice the difference with the previous paragraph, where the interpolation peak was concerning the training error vanishing in the A > 0 case, while we here consider the perfect test error at A = O. This limit was studied in the context of matrix model (9) in the minimal- norm interpolation setting [Donoho et al., 2013, Amelunxen et al., 2014, Oymak and Hassibi, 2016]. Here we re-derive their result independently as a consequence of Theorem 1.
asstrong the test error of the global minima of (2) is zero, and for < Ostrong is
Corollary 1 (Strong recovery threshold) Consider the setting of Section I for Marchenko-Pate Pastur targets with A 0, X + O+ and K 2 1. Define for x E 1-2, 2] the incomplete moments of the semicircle distribution
(x) [" dx cs.c. (x)
[" dx v 4 x2 x²a
(14)
2
and call ē the solution of the equation
M cMV(D)())
x² 0,
(15)
8

---

Interpolation (N"" A)
Thresholds at A
Test error for n² ->
0.50
10
==0,A=0*
A 0.006,
10"
0.010 A
0
10
0.1
DO
0.5
EKM Str.
Interp.
10
0.00
10
10
10a
0.0
0..5
1.5
2.6
3.6
Target widsh
Target width
Rescaled sample complexity m/(dm=)
Figure 4: (Left) Interpolation threshold Oinser (x* A) as a function of x* for several values of label noise A (Result 1). Notice the convergence to the 1/4 random-label-iitine
threshold for very narrow targets k* 1 and large label noise À >>>>/ 1. (Center) Comparison between interpolation threshold (Result 1, A 0) and strong recovery threshold (Corollary 1) of the global minima of (2), with the BO strong recovery threshold [Maillard et al., 2024]. Minimal regularization interpolators of (2) reach perfect recovery well before the interpolator set shrinks to singleton on the target weights (the effect more pronounced for very small ranks emor of any global minimum of (2) in the limit x* 0 (Result 2) for several values of regularization = A/VK* and label noise A, compared with the Bayes-optimal [Maillard et al., 2024].
target function x < (Right) The test
for 0 < K² < 1. Then,
2 x²²² (1I=x)?(M22.00)
0 n² <1 x2 + oa(1).
Olstrong
(16)
Informally, the strong recovery threshold presented in Result I is derived by expanding (6) for + 0+ within an appropriate scaling ansatz, as the test error is proportional
82 (Theorem 1, noiseless case Osstrongg such that the expansion is consistent. We provide all the details in Appendix C. We plot (16) in Figure 4, comparing with the strong recovery threshold BO estimator [Maillard et al., 2024] and with the interpolation threshold Result for A =. 0.
A = 0), and finding the value
Small target rank limit. Finally, we consider the small target width limit x* - 0+ for bounded away from zero. This is an example of large over-parametrizationn as the ratio between student and target widths m/m" diverges. In the limit x* 0, i.e. m < d, we define the rescaled sample ratio = a/n² = n/ (m" d). The natural baseline to compare this limit against is given by the analogue limit for the test emor of the BO estimator given in [Maillard al., 2024].
Result 2 (Test error in the k* limit) Consider the setting of Section Consider the limit
Rº 0+ for any fixed & > 0, a/K= and X XVR'. Then, if A 0 and X + 0+ the test error satisfies
if
1/2.
lim
lim + d0000
Etest (S)
= aa(4 - Voa V6a 2)2 2)2
if 1/2 < 3
(17)
if a 3
In Appendix D we provide analogous expressions, albeit less explicit, for generic regularization
X > and noise A > O. We just state that for all X 0 and A > O, and for < @wwakk (X, A) the test error equals one, where
11 1/2
Ā 2(1 2 4/2)+
Oreakk (A, max
(18)
2
4
and that for all X > 0 and A > 0 and for ā - 400 he have
3A
lim lim E Eerest
(1 + 0v (1))
(19)
xc" +0+
20

---

Result provides a closed-form expression for the test error in the - O limit. It is derived by direct expansion of (6) at small Ks, and involves BBP-like phase transition [Baik et al., 2005] in the spectrum of W. We notice that Result 2 holds for any extensive student width & > 0 due to the fact that the rank of the global minima of (2) is vanishing as ((*)).
Figure right shows the test error in the k* 0 limit for selection of parameters. We see that the solution at X, A * 0 as a non-trivial behavior, tracking closely but not exactly the À - 0+, A * 0 curve until an angular point is reached. We observe that for < @ (7, Á). the empirical risk minimizer achieves BO performance, even though that is given by the trivial prior-average estimator. Moreover, for A 0 and Ā - 0+, the empirical risk minimizer achieves strong recovery for in accordance with Corollary 1. Finally, we remark that for fixed X > 0 and A > 0, the test error goes to zero as 1/a, which is the Bayes-optimal rate.
Discussion and limitations
In this paper, we presented a closed-form asymptotic characterization of learning one hidden-layer quadratic neural network target with an over-parametrized architecture, in the challenging high- dimensional regime extensive widths m (d) target functions and quadratically-mang samples (d?). We presented the asymptotic learning curves and values of relevant thresholds, well as numerical experiments (including gradient descent algorithms) illustrating that our theory applied also accurately to very moderate sizes.
The main limitations of our setting are the restriction to random input data (which can be relaxed to a certain extent, see [Xu et al., 2025] for theoretical direction hinging on Gaussian universality, or Loureiro [2021b] for an empirical direction modeling real data by matching to Gaussian mixtures with appropriate first and second moments), the choice of quadratic activation, the single hidden-layer architecture and the requirement that the width of the target function satisfies m > (imposing no non-convex rank constraint in (9)). All such elements present highly non-trivial technical challenges, and we hope our work will spark progress in these directions.
Acknowledgments and Disclosure of Funding
We thank Yatin Dandi, Cedric Gerbelot, Antoine Maillard, Simon Martin, Yizhou Xu and Nathan Srebro for insightful discussions. This work was supported by the Swiss National Science Foundation under grants SNSF SMArtNet (grant number 21 212049), SNSF OperaGOST (grant number 200390), and SNSF DSGIANGO (grant number 225837).
References
Akshay Agrawal, Robin Verschueren, Steven Diamond, and Stephen Boyd. A rewriting system for convex optimization problems. Journal of Control and Decision, 5(1):42-60, 2018.
D. Amelunxen, M. Lotz, M. B. McCoy, and J. A. Tropp. Living on the edge: phase transitions in convex programs with random data. Information and Inference, 3(3):224 294, September 2014. ISSN 2049-8764, 2049-8772.
Yossi Arjevani, Joan Bruna, Joe Kileel, Elzbieta Polak, and Matthew Trager. Geometry and optimiza- tion of shallow polynomial networks. arXiv preprini arXiv:2501.06077 2025.
Benjamin Aubin, Antoine Maillard, Florent Krzakala, Nicolas Macris, Lenka Zdeborová, et al. The committee machine: Computational to statistical gaps in learning a two-layers neural network. Advances in Neural Information Processing Systems, 31, 2018.
Benjamin Aubin, Florent Krzakala, Yue Lu, and Lenka Zdeborová. Generalization error in high- dimensional perceptrons: Approaching bayes error with convex optimization. Advances Neural Information Processing Systems, 122111199122111 2020.
Jinho Baik, Gérard Ben Arous, and Sandrine Péché. Phase transition of the largest eigenvalue for nonnull complex sample covariance matrices. Annals of Probability, pages 1643-1697, 2005.
10

---

Jean Barbier, Florent Krzakala, Nicolas Macris, Léo Miolane, and Lenka Zdeborová. Optimal errors and phase transitions in high-dimensional generalized linear models. Proceedings of the National Academy of Sciences, I (16(12)554515444 2019.
Jean Barbier, Francesco Camilli, Minh-Toan Nguyen, Mauro Pastore, and Rudy Skerk. Optimal generalisation and learning transition in extensive-width shallow neural networks near interpolation, January 2025.
Mohsen Bayati and Andrea Montanari. The lasso risk for gaussian matrices. IEEE Transactions on Information Theory, 58(4): 2011.
Mohsen Bayati, José Pereira, and Andrea Montanari. The lasso risk: asymptotic results and real world examples. Advances Neural Information Processing Systems, 23, 2010.
Mikhail Belkin, Daniel Hsu, Siyuan Ma, and Soumik Mandal. Reconciling modern machine-learnine practice and the classical birs-variance trade-off. Proceedings of the National Academy of Sciences, 116632):15849-15855 2019.
Mikhail Belkin, Daniel Hsu, and Ji Xu. Two models of double descent for weak features. SIAM Journal on Mathematics of Data Science, 2(4):1167-11800 2020.
Raphaël Berthier, Andrea Montanari, and Phan-Minh Nguyen. State evolution for approximate message passing with non-separable functions. Information and Inference: A Journal of the IMA, 9(1:333-79, March 2020. ISSN 2049-8764, 2049-8772.
Alberto Bietti, Joan Bruna, and Loucas Pillaud- Vivien. On learning gaussian multi-index models with gradient flow part i: General properties and two-timescale learning. Communications on Pure and Applied Mathematics, 78(12):2354-243 2025. doi: https://doi.oow wtt.i/oiiooo/1..... 1002000a.70000 70006.
Erwin Bolthausen. An iterative construction of solutions of the tap equations for the sherrington- kirkpatrick model. Communications in Mathematical Physics, 325(1):333-36) 2014.
Blake Bordelon and Cengiz Pehlevan. Self-consistent dynamical field theory of kernel evolution in wide neural networks. Journal of Statistical Mechanics: Theory and Experiment, 2023(11): 114009, 2023.
Blake Bordelon, Abdulkadir Canatar, and Cengiz. Pehlevan. Spectrum dependent learning curves in kernel regression and wide neural networks. In International Conference on Machine Learning. pages 1024 1034. PMLR, 2020.
Joan Bruna and Daniel Hsu. Survey on algorithms for multi-index models. arXiv preprint arXiv:2504.05426, 2025.
J. Bun, J. Bouchaud, S. N. Majumdar, and M. Potters. Instanton approach large harish-chandra- itzykson-zuber integrals. Phys. Rev. Lett, 1 113:070201, Aug 2014.
Francesco Camilli, Daria Tieplova, Eleonora Bergamin, and Jean Barbier. Information -thhorettcc reduction of deep neural networks to linear models in the overparametrized proportional regime. arXiv preprint htt.:::25500053577 2025.
Lucas Clarté, Bruno Loureiro, Florent Krzakala, and Lenka Zdeborová. On double-descent in uncertainty quantification in overparametrized models. In International Conference on Artificial Intelligence and Statistics, pages 7089-7125. PMLR, 2023.
Hugo Cui, Florent Krzakala, and Lenka Zdeborová. Bayes-optimal learning of deep random networks of *x Journal of Statistical Mechanics: Theory and Experiment, 2025(1):014001. January 2025. ISSN 1742-5468. Publisher: IOP Publishing.
George Cybenko. Approximation by superpositions sigmoidal function. Mathematics of control, signals and systems, 244):303-314, 1989.
Alex Damian, Loucas -ivien,, Jason Lee, and Joan Bruna. Computational-staiinn gaps in gaussian single-index models. The Thirty Seventh Annual Conference on Learning Theory, pages 1262-1262. PMLR, 2024.

---

Alexandru Damian, Jason Lee, and Mahdi Soltanolkotabi. Neural networks can learn representations with gradient descent. In Conference on Learning Theory, pages 5413-5452. PMLR, 2022.
Yatin Dandi, Ludovic Stephan, Florent Krzakala, Bruno Loureiro, and Lenka Zdeborová. Univer- sality laws for gaussian mixtures in generalized linear models. Advances in Neural Information Processing Systems, 36:54754 -4466, 2023.
Jairo RL de Almeida and David J Thouless. Stability of the Seerrington-kikkaaee solution of a spin glass model. Journal of Physics A: Mathematical and General, 1 11(5):983, 1978.
C De Dominicis and Imre Kondor. Eigenvalues of the stability matrix for parisi solution of the long-range spin-glass. Physical Review B, (6666, 1983.
Steven Diamond and Stephen Boyd. CVXPY: A Python-embeddee modeling language for convex optimization. Journal of Machine Learning Research, 17(83):1-5, 2016.
David Donoho and Andrea Montanari. High dimensional robust m-cstimation: Asymptotic variance via approximate message passing. Probability Theory and Related Fields, 166:935-969, 2016.
David L. Donoho, Matan Gavish, and Andrea Montanari. The phase transition of matrix recovery from gaussian measurements matches the minimax mse of matrix denoising. Pruceedings of the National Academy of Sciences, 110021)8800-8441 84100 May 2013. ISSN 1091-6490.
Simon Du and Jason Lee. On the power of over parametrizaaioon in neural networks with quadratic activation. In Jennifer Dy and Andreas Krause, editors, Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pages 1329-1338. PMLR, 10-15 Jul 2018.
Sofia Dubova, Yue M Lu, Benjamin McKenna, and Horn--Tzer Yau. Universality for the global spectrum of random inner-product kernel matrices in the polynomial regime. arXiv preprint arXiv:2310. 18280, 2023.
Maryam Fazel, Emmanuel Candes, Ben Recht, and Pablo Parrilo. Compressed sensing and robust recovery of low rank matrices. In 2008 42nd Asilomar Conference on Signals, Systems and Computers, pages 1043-1047. IEEE, 2008
Oliver Feng, Ramji Venkataramanan, Cynthia Rush, and Richard J. Samworth. Unifying Tutorial on Approximate Message Passing. Foundations and Trends@ in Machine Learning, 15(4):335-534 2022. ISSN 1935-8237, 1935-8245.
David Gamarnik, Eren C Kızıldag, and Ilias Zadik. Stationary points of shallow neural networks with quadratic activation function. arXiv preprint arXiv: 1:XX:v:9/2.015999 2019.
Elizabeth Gardner and Bernard Derrida. Three unfinished works on the optimal storage capacity of networks. Journal of Physics A: Mathematical and General, 22(12):1983, 1989.
Mario Geiger, Arthur Jacot, Stefano Spigler, Franck Gabriel, Levent Sagun, Stéphane d' Asscoll Giulio Biroli, Clément Hongler, and Matthieu Wyart. Scaling description of generalization with number of parameters in deep learning. Journal of Statistical Mechanics: Theory and Experiment, 2020(2):033011, 2020.
Federica Gerace, Bruno Loureiro, Florent Krzakala, Mare Mézard, and Lenka Zdeborová. General- isation error in learning with random features and the hidden manifold model. In International Conference on Machine Learning, pages 3452-3462. PMLR, 2020.
Cédric Gerbelot and Raphaël Berthier. Graph-based approximate message passing iterations. Infor- mation and Inference: A Journal of the IMA, 12(4):2562-2628 2023.
Sebastian Goldt, Bruno Loureiro. Galen Reeves, Florent Krzakala, Marc Mézard, and Lenka Zde- borová. The gaussian equivalence of generative models for learning with shallow neural networks. In Mathematical and Scientific Machine Learning, pages 426-471. PMLR, 2022.
Suriya Gunasekar, Blake E Woodworth, Srinadh Bhojanapalli, Behnam Neyshabur, and Nati Srebro. Implicit regularization in matrix factorization. Advances in neural information processing systems, 30, 2017.
12

---

Hong Hu and Yue M Lu. Universality laws for high-dimensional learning with random features.
IEEE Transactions on Information Theory, 69(3):1932-194, 2022.
Adel Javanmard and Andrea Montanari. State evolution for general approximate message passing algorithms, with applications to spatial coupling. Information and Inference: A Journal of the IMA, 12):11 2013.
Ziwei Ji and Matus Telgarsky. Gradient descent aligns the layers of deep linear networks. In 7th International Conference Learning Representations, ICLR 2019, 2019.
Florent Krzakala and Lenka Zdeborová. Statistical physics methods in optimization and machine learning. Lecture Notes, 2024.
Jaehoon Lee, Yasaman Bahri, Roman Novak, Samuel S Schoenholz, Jeffrry Pennington, and Jascha Sohl-Dickstein. Deep neural networks as gaussian processes. International Conference on Learning Representations, 2018.
Qianyi Li and Haim Sompolinsky. Statistical mechanics of deep linear neural networks: The backpropagating kernel renormalization. Phys. Rev. X, 11:031059, Sep 2021.
Bruno Loureiro, Cedric Gerbelot, Hugo Cui, Sebastian Goldt, Florent Krzakala, Marc Mezard, and Lenka Zdeborová. Learning curves of generic features maps for realistic datasets with teacher-student model. Advances in Neural Information Processing Systems, 34:18137-18151, 2021a.
Bruno Loureiro, Gabriele Sicuro, Cédric Gerbelot, Alessandro Pacco, Florent Krzakala, and Lenka Zdeborová. Learning gaussian mixtures with generalized linear models: Precise asymptotics in high-dimensions. Advances Neural Information Processing Systems, 34: 14140071-, 2b.
Yue M Lu and Gen Li. Phase transitions of spectral initialization for high-dimensional non-convex estimation. Information and Inference: A Journal of the IMA, 9(3): 541, 2020.
Antoine Maillard and Afonso S Banddera, Exact threshold for approximate ellipsoid fitting of random points. arXiv preprint arXiv:2310.05787, 2023.
Antoine Maillard and Dmitriy Kunisky. Fitting ellipsoid to random points: predictions using the replica method. IEEE Transactions on Information Theory, 70(10):7233-729, 2024.
Antoine Maillard, Bruno Loureiro, Florent Krzakala, and Lenka Zdeborová. Phase retrieval high dimensions: Statistical and computational phase transitions. Advances in Neural Information Processing Systems, 33:11071-11082 2020.
Antoine Maillard, Emanuele Troiani, Simon Martin, Lenka Zdeborová, and Florent Krzakala. Bayes- optimal learning of an extensive-width neural network from quadratically many samples. Advances in Neural Information Processing Systems, 37:82085-82132 December 2024.
VA Marchenko and Leonid A Pastur. Distribution of eigenvalues for some sets of random matrices. Mat. Sb.(NS), 72(144):4 1967.
Simon Martin, Francis Bach, and Giulio Biroli. On the impact of overparameterization on the training of shallow neural network in high dimensions. In International Conference Artificial Intelligence and Statistics, pages 3655-3663. PMLR, 2024a.
Simon Martin, Francis Bach, and Giulio Biroli. On the Impact of Overparameterrization on the Train- ing of Shallow Neural Network in High Dimensions. In Proceedings of The 27th International Conference on Artificial Intelligence and Statistics, pages 3655-3663. PMLR, April 2024b.
Song Mei and Andrea Montanari. The generalization error of random features regression: Precise asymptotics and the double descent curve. Communications on Pure and Applied Mathematics, 75 (4):667-766, 2022.
Song Mei, Andrea Montanari, and Phan-Minh Nguyen. A mean field view of the landscape of two- layer neural networks. Proceedings of the National Academy of Sciences, 176655)777666577777 2018.
13

---

Mare Mezard and Andrea Montanari. Information, physics, and computation. Oxford University Press, 2009.
Mare Mézard, Giorgio Parisi, and Miguel Angel Virasoro. Spin glass theory and beyond: An Introduction to the Replica Method and Its Applications, volume 9. World Scientific Publishing Company, 1987.
Leon Mirsky, A trace inequality of john von neumann. Monatshefte, für mathematik, 79(4):003-306, 1975.
Marco Mondelli and Andrea Montanari, Fundamental limits of weak recovery with applications to phase retrieval. In Conference On Learning Theory, pages 1445-1450. PMLR, 2018.
Andrea Montanari and Basil N Saeed. Universality of empirical risk minimization. In Conference on Learning Theory, pages 4310-4312. PMLR, 2022.
Andrea Montanari and Pierfrancesco Urbani. Dynamical decoupling of generalization and overfitting in large two-layer networks. arXiv preprint arXiv:2502.21126: 2025.
Andrea Montanari, YC Eldar, and Kutyniok. Graphical models concepts in compressed sensing. Compressed Sensing, pages 394 434, 2012.
Andrea Montanari, Feng Ruan, Basil Saeed, and Youngtak Sohn. Universality of max-margin classifiers. arXiv preprint arXiv:2310.00176 2023.
Preetum Nakkiran, Gal Kaplun, Yamini Bansal, Tristan Yang, Boaz Barak, and Ilya Sutskever. Deep double descent: Where bigger models and more data hurt. Journal of Statistical Mechanics: Theory and Experiment, 2021 122):120033 2021.
Samet Oymak and Babak Hassibi. Sharp MSE Bounds for Proximal Denoising. Foundations of Computational Mathematics, 16(4):955-1029, August 2016. ISSN 1615-3375, 1615-3383.
R. Pacelli, S. Ariosto, M. Pastore. F. Ginelli, M. Gherardi, and P. Rotondo. A statistical mechanics framework for Bayesian deep neural networks beyond the fhinite-width limit. Nature Machine Intelligence, 5(12):1497-1500 December 2023. ISSN 2522-5839. Publisher: Nature Publishing Group.
Scott Pesme, Loucas Pillaud-Vivien, and Nicolas Flammarion. Implicit bias of sgd for diagonal linear networks: provable benefit of stochasticity. Advances in Neural Information Processing Systems, 34:29218-22 -92330, 2021.
Marc Potters and Jean-Philippe Bouchaud. A first course in random matrix theory: for physicists, engineers and data scientists. Cambridge University Press, 2020.
Farzad Pourkamali and Nicolas Macris. Bayesian extensive-rank matrix factorization with rotational invariant priors. Advances in Neural Information Processing Systems, 36:24025-24073, 2023a
Farzad Pourkamali and Nicolas Macris. Rectangular rotational invariant estimator for general additive noise matrices. In 2023 IEEE International Symposium on Information Theory (ISIT), pages 2081-2086. IEEE, 2023b.
Sundeep Rangan, Philip Schniter, Erwin Riegler, Alyson Fletcher, and Volkan Cevher. Fixed points of generalized approximate message passing with arbitrary matrices. IEEE Transactions on Information Theory, 62(12))7464-744 2016.
Benjamin Recht, Maryam Fazel, and Pablo Parrilo. Guaranteed minimum-rank solutions of linear matrix equations via nuclear norm minimization. SIAM review, 52(3):471-50,, 2010.
Stefano Sarao Mannelli, Eric Vanden- Eijnden,, and Lenka Zdeborová. Optimization and General- ization of Shallow Neural Networks with Quadratic Activation Functions. In Advances in Neural Information Processing Systems, volume 33, pages 13445-13455. Curran Associates, Inc., 2020.
Guilhem Semerjian. Matrix denoising: Bayes-optimal estimators via low-degree polynomials. Journal of Statistical Physics, 191 2024.
14

---

H Sebastian Seung, Manfred Opper, and Haim Sompolinsky. Query by committee, In Proceedings of the fifth annual workshop on Computational learning theory, pages 287-294, 1992.
Mahdi Soltanolkotabi, Adel Javanmard, and Jason D. Lee. Theoretical Insights Into the Optimization Landscape of Paee-Parrmeteriieedd Shallow Neural Networks, IEEE Transactions Information Theory, 65(2):742-766 February 2019. ISSN 1557-9654.
Christos Thrampoulidis, Ehsan Abbasi, and Babak Hassibi. Precise error analysis of regularized m-estimators in high dimensions. IEEE Transactions Information Theory, 64(8):5592 5628, 2018.
Emanuele Troiani, Vittorio Erba, Florent Krzakala, Antoine Maillard, and Lenka Zdeborová. Optimal denoising rotationally invariant rectangular matrices. In Mathematical and Scientific Machine Learning, pages 97- PMLR, 2022.
Emanuele Troiani, Hugo Cui, Yatin Dandi, Florent Krzakala, and Lenka Zdeborová. Fundamental limits of learning sequence multi-index models and deep attention networks: High-dimensional asymptotics and sharp thresholds. To appear in ICML 2025, 2025.
Luca Venturi, Afonso S. Bandcira, and Joan Bruna. Spurious valleys in one-hidden-layer neural network optimization landscapes. Journal of Machine Learning Research, 20(133)) 2019.
Matteo Vilucchio, Yatin Dandi, Cedric Gerbelot, and Florent Krzakala. Asymptotics of non-convex generalized linear models in high-dimensions: A proof of the replica formula. arXiv preprini arXiv:2502.20003. 2025.
Lechao Xiao, Hong Hu, Theodor Misiakiewicz, Yue Lu, and Jeffrey Pennington. Precise learning curves and higher-order scalings for dot- not-product kernel regression, Advances in Neural Information Processing Systems, 35:4558 1144558--570,, 2022.
Yizhou Xu, Antoine Maillard, Lenka Zdeborová, and Florent Krzakala. Fundamental limits of matrix sensing: Exact asymptotics, universality, and applications. In Nika Haghtalab and Ankur Moitra, editors, Proceedings of Thirty Eighth Conference Learning Theory, volume 291 of Proceedings of Machine Learning Research, pages 5757-5823. PMLR, 30 Jun an-04 Jul 2025.
Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning (still) requires rethinking generalization. Communications of the ACM, 64(3):107-115, 2021.
15

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
We present faithfully our claims in the abstract and introduction.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results be expected to generalize other settings.
is fine include aspirational goals as motivation as long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification:
We discuss the main limitations our setting in the final Section.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification. asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low images are taken in low lighting. Or speech-to-text system might be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach address problems of privacy and faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question:
For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
16

---

Justification: In the paper we present Theorem 1, for which we provide a sketch of the proof in the main text, as well as all details in the Appendix. All other theoretical results follow from analytic manipulations of Theorem 1.
Guidelines:
The answer NA means that the paper does not include theoretical results. All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should properly referenced.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: We provide all details of the numerical procedures used to produce the figures in the Appendix, and we provide the code in the SM.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer this question will not perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
the contribution is a dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm.
(b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way access this model for reproducing the results way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reprodueibility may be tricky in some cases, in which authors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path reproducing verifying the results.
5. Open access to data and code
17

---

Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [Yes]
Justification:
We provide the code in the SM.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips cc/
serrides/CodeSubmisssee
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (c.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https: /nips.coom wttpccccpppc/eeeeeeee..ec...ceee http//udddes/soeeeeeeeeeee /Coo/eeooiissssseeeeeee www.isssioppccyccccc for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary understand the results?
Answer: [Yes]
Justification: We provide all details of the numerical procedures used to produce the figures in the Appendix.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification:
We describe error bars whenever they are present.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi-
dence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for
example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
18

---

The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
should be clear whether the error bar is the standard deviation or the standard error of the mean.
It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables figures symmetric error bars that would yield results that are out of range (c.g. negative emror rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [NA]
Justification: All our numerical procedure can be run on common laptops.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't 't make it into the paper).
9. Code ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https: / /ttp///eerrp/.eeeee//eee/eeeesee cc wwwablic/Ethicscuiiccc
Answer: [Yes]
Justification: Our work is theoretical in nature, and we respected the code of ethics.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: The work is theoretical and synthetic setting.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
19

---

The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: The work is theoretical and in synthetic setting far from direct applications.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g.. code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification: We cite the original papers associated with special (still publicly released) code libraries used.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
20

---

If this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
No assets produced.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/mmoel as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
We use synthetic data that we generate ourself.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question:
Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
We use synthetic data that we generate ourself.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
16. Declaration of LLM usage
21

---

Question: Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods this research? Note that if the LLM used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Answer: [NA]
Justification: No LLM was used for the mentioned core aspects of the research.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs any important, original, non-standard components.
Please refer to our LLM policy (https / /ttp:///eeec.eeeeeeee////////// for what should or should not be described.
22

---

A Proof of Theorem 1
In this section we discuss theorem 1 for the minima of VV" f("" + XIIWII + +I|lW
W arg min C(W), where c(W)
(20)
which, due to the added regularization, is strongly convex for T, À > 0 and hence it admits a unique global minimum. Note that while we concentrate on this case, the computation goes through for any (strongly) convex denoiser.
The proof of Theorem is application of standard approaches in high-dimensional statistics, and goes as follows:
1. In Section A.1, we show how to map the original learning problem into an equivalent matrix estimation problem. This, in turn, can be reformulated as a vector Generalized Linear Model (GLM) with non-separable regularization.
2. In Section A.2, we use Gaussian universality and show that this model is asymptotically equivalent to a Gaussian sensing problem, leveraging recent results on universality in high-dimensional estimation.
3. The resulting Gaussian model can then be analyzed using the Generalized Approximate Message Passing (GAMP) algorithm. We briefly recall the relevant properties of GAMP in Section A.3.
To apply GAMP rigorously, we exploit the fact that its fixed points coincide with the solutions of the associated convex optimization problem (Section A.3. These fixed points are characterized by a set of deterministic equations known as state evolution (Section A.3.2). With appropriate initialization (see Corollary 2), GAMP converges to the correct fixed point (Theorem 5), which corresponds to the global minimizer of our original problem. Hence, the fixed points of the associated state evolution equations describe the properties of the global minima of (1). Notice that this discussion is generic (i.e. allows for generic convex losses and regularizations) long as the global minimum of the associated matrix problem is unique.
4. Finally, in Appendix A.4, we describe the state evolution equations that precisely character- izes the asymptotic behavior of the minimizer of the empirical risk (2), which is precisely equivalent the results given in Theorem in the limit 7 - 0+.
A.1 Mapping to a matrix model
The mapping of the data part of the loss is straightforward. For the l regularization on the network weights we have
d. Σ 1=
d.m
W2
d
W
V md
v Vmd
S(W) = Vmd (21)
md
1,K=1
The same goes for the part proportional to r in (20), that become the Frobenius norm of S. This leads to the equivalent problem:
x, T # - La
)
1 +Vmd (X + +))
S arg min L(S), with E(S) =
Tr
(S- (S-S")
S
Vd
(22)
A.2 Data universality
The universality of the minimal error (or "ground state energy" in the physics jargoo) jargon) follows directly from rich line of work on universality of empirical risk minimization [Goldt et al., 2022, Hu and Lu, 2022, Montanari and Saeed, 2022, Maillard and Bandeira, 2023, Martin al., 2024b, Xu et al., 2025]. These results establish that, under broad conditions, the asymptotic behavior of the test and
23

---

training errors becomes equivalent to those with a Gaussian sensing matrix. Given the maturity of this theory, we will refer directly to these foundational works and provide a concise sketch of the main arguments for completeness.
The universality follows directly from Proposition 2.1 in [Maillard and Bandeira, 2023], who derived it in the related context of ellipsoid fitting. This was adapted to the "planted" case in [Xu et al.. 2025, Section 3.1, Lemma 3.3]. The proof strategy is consider an interpolating model where each data matrix given by (t) (x -T2// sin(()GG in l [0, 2 from the original model 0 the one with a GOE(d) random matrix G at π 2/2, and to show that the "time" does not change the expected loss. We refer to these works (and to [Montanari and Saced, 2022]) for the detailed proofs, and directly state the universality result:
Theorem (Gaussian Universality of the loss, from [Maillard et al., 2024, Xu et al., 2025]) Let vp R T. be a bounded differentiable functions with bounded derivative, then for any finite = n , the minimum of the training loss GS( ()(($p) == arg ming ((S)((#))) p (m))))))))))))))))mm))) (9) universal with respect to the training data Dy in the sense that for any such tb, then
]
XXx
Ta Vd
lim d-000
E (xx 1b
GSa
E (G,,) ( & [GSal(Gp)ppm)) = (23)
if the matrices ((x,x] - Ia))//V respects the so-called one-dimensional CLT property [Xu et al., 2025, Assumption 2.2] and if target weights S and the regularization term of the loss r(S) satisfy [Xu al., 2025, Assumption 2.1].
The required one-dimensional CLT [Goldt et al., 2022, Montanari and Saeed, 2022, Dandi et al., 2023] property is a point-wise normality of the projection of the operator, proven the case of Gaussian x" in [Maillard and Bandeira, 2023, Lemma 4.8].
The universality argument can be readily adapted other quantity as well, in order to show that only the loss, but also other observables such as the overlaps are universal. We will not repeat the full proof, and directly use Theorem in [Dandi et al., 2023] that can be applied mutatis mutandis':
Theorem (Universality of the overlaps [Dandi et al., 2023], informal) For any bounded- Lunchitz.unntion function V dRd x dRd
R. we have:
( (s,
E T
Eg
n,d++000 n//==a>0
where $ = arg ming L(S), and S determines the target function.
This directly can be applied to the overlap Tr S and Tr[ST S*), which are thus universal, as well as to the test error. Notice indeed that
1 Crest (1)) = 2 En (fm- (x; w²) - f fm; (x; 0))² _ [|S((w) - S(w*)) I|
(24)
leading to an expression for the test error as a fuucction of the overlaps. Finally, note that one can apply the same argument to show the universality of any finite & E Z, moment d Tr[S*] (hinging erucially on the PSD constraint to claim that all such perturbations are convex). With mild regularity assumptions (for e.g. compact support, which is satisfied by the Marchenko-Pasee target case studied in detail in the main text), this implies the universality of the spectral distribution of Š as well.
'The argument is classic approach of large deviation, or Legendre transform. This is done by applying the universality to a perturbed version of the loss, where -to use the parlance of physics-a source term, or a regularization, such as Às TT|S" S*). is added. Due to the convexity of the loss in Às the derivative with respect to As must converges to the same exact quantity in both the original and the equivalent model, since they converge point-ve wise to the same limit.
24

---

A.3 Generalized Approximate Message Passing algorithm and state evolution equations
We review here how use GAMP to solve asymptoties convex optimization problems. Later, in section 1.4.1 we show indeed that the present PSD matrix optimization problem can be written as vector one, with non-separable denoiser.
We will work in a vector setting, where one has sensing matrices A E TR ~ (N(0, (i.e. N samples in D dimension) with rows a².
Notice that in this scaling ||u| should be always of order O(D).
The generic form of the "rectangular" GAMP algorithm reads [Javanmard and Montanari, 2013]:
t++1 A gc((") die((u').
(25)
e² = Aer( - 11 (1
with initialization === and the convention that g-1(-) Here V E u RD, g: RN N + R and e IRD + R.
The terms b de usually called Onsager's reaction terms [Mézard et al., 1987], and are tuned in such a way as to erase time-to-time to-t correlations between the iterates (u', w²) and the sensing matrix A, so that from statistical point of view of (u', v²) is as if the matrix A was resampled independently at each time-step (conditioned on the previous iterates {(u", )"))== One has
1 1 c,(u'),
d
D V se(v") and by ==
(26)
where f-f= 0.f: denotes the divergence of a function f Rd + Rd. We will see later that in nigh-dimension D >> 1, O(D), the Onsager's term concentrate and do not depend on the iterates u and v² anymore.
A.3.1 GAMP for convex optimization
Using AMP for studying the minimum of loss is now classical approach that has been used in many context, c.g. [Bayati et al., 2010, Montanari et al., 2012, Rangan et al., 2016, Loureiro et al., 202 Vilucchio et al., 2025]. This is also discussed in detail the pedagogical review [Feng et al., 2022, Section 4.4] and the lecture notes [Kzzaaala and Zdeborová, 2024, Section 12.7.4).
The argument goes as follows: consider the convex optimization problem
arg min
Σ flu a, u a) + R(u),
(27)
MEC
with E, R convex in their first argument, and C C RDD a convex set. Define the functions
2b (2 r)3 and g(r,s,b) g(r, 8)
g(r, s, b) arg min
s22 +
b
2E3
(28)
d
c(r, d) arg min #EC
R(z) + ? ||2 d r111
Consider the GAMP algorithm
AT g(' y, b²) + dielu', , d²), 3' Ae(u', d() big(v' y, b² 1)
(29)
where is applied component-wise to and y. Then, [Feng et al., 2022, Proposition 4.4] guarantees that fixed points of (29) are solutions of (27) (by minor adaptation, as they consider separable regularization, but all their arguments generalize directly).
As long f, R are convex in their first argument, state evolution follows automatically for this choices of g and e.
Additionally, we remark that if the loss is strictly convex, then the optimization problem (27) has only single global minimum, so that AMP will have a single fixed point coinciding with this global minimum.
25

---

A.3.2 State evolution
Thanks to the conditional Gaussianity discussed in Appendix A.3, one can track the statistics of the iterated u, GAMP through set of so-called state evolution equations. The main difference with respect previous approaches in our case is that the denoising function is not separable. However, [Berthier et al., 2020, Gerbelot and Berthier, 2023] guarantees that the state evolution that allows to track the performance of AMP remains corrects (under regularity assumptions that are automatically satisfied by and yf being proximal operators).
The state evolution associated to the GAMP
2 A 9i b, + dics(u', ; dd),
(30)
v' (e, d²) big.-11" y, 10,6-11
(where again here we consider g applied component-wis wise to and y) is derived by considering that yd = p(u² a") where Φ possibly random non-linearity, and taking into account the evolution of the iterates and separately in the parallel and orthogonal directions to u² (and similarly with and A u²). Using [Berthier al., 2020, Gerbelot and Berthier, 2023] we have:
Theorem (Theorem in [Berthier et al., 2020], informal) Define
m
10. g(w, )(2)),b))
D (gww, )2²), 61)
d'+1
N E (w of )(²)),))
m,
u" :u;elv dz +mm (o,,t,d'))
(31)
d JE (e( (e(v9lz 9- + =m d,),dd;;) (( gi m d')
b² -EEV V + m,nndd")
where the average Ey over the randomness in Φ well over (w, z*) E TR2 distributed
u
11/D
m²
W
(32)
m
and El is over z i.i.d. Gaussian ((O,ID)-
Then the AMP vectors - and of converges weakly to their Gaussian version: U = mi,u" + V (with z random Gaussian as above) and V Vtt my w in the sense that, for any deterministic sequence on (RD Ny x RN + of uniformly ggeudo-Lipschit. functions of order k.
m A" u² (with N IN)),
(u v .'..v....,,v'
v utt t Eu. (on vO.
U2 V2 ..... Vt-L,U"]] (33)
An immediate corollary we shall the following:
Corollary (Fixed point initialization) Consider a fixed point of the state evolution equations (31) (we denote the fixed point quantities by fp). one initializes an AMP sequence in the fixed point, i.e. by using n mf fP'" + / qu (with random Gaussian as above), then probability for any time t> 0 and as d + oc, the sequence of iterates U and V remains in their fixed point.
We then use the following theorem, that ensure with the initialization of 2, then the GAMP equation converges to their fixed point:
Theorem (Convergence of GAMP, Lemma from [Loureiro et al., 2021b]) Consider the GAMP iteration with e, in (28), where all free parameters initialized al any fixed point the state evolution equations. If the associated loss (27) is strongly convex, then GAMP converges to the fixed point of the loss under study:
lim lim (+0 d
val
lim 1
lim
of =
(34)
Vd
Thus, state evolution allows to compute all scalar observables (such as overlaps, errors, etc) on the iterates, which at convergence and under the setting of Appendix 1.3.1, are equivalent the global minimum of (27).
26

---

A.4 State evolution for Theorem
Now that we have reviewed how to use GAMP to study the fixed point of an optimization problem, it remains to show that the present matrix problem can be mapped to such equivalent vectorized problem. Consider (9), and write in the following form:
$ = arg min Z(S), with L(S) = Σ (I + R(S),
(35)
SEC
where S E Sym, is symmetric d x d matrix, C S RD is convex and f, R are convex in their first argument.
A.4.1 Mapping matrix-GIM, vector-GLM
We consider the mapping from vec Sym, - [Rd(d+1//2 (which conveniently maps the Frobenius scalar product in Sym, given by (A; Tr(AB) to the standard Euclidean scalar product in pd(d+ 1) given by
vec (A) (ab) = =(blat) AA) = V2 Sab
(36)
under the choice of orthonormal basis
(aa) = 6ia
blab))
Ōz 5b + des0g0
(37)
v2
Here (ab) stands for the ordered pair of S a b d. and we denote Aij the i, entry of matrix A, while A(ab) the component of matrix A onto the basis element b(aB), Let us denote d(d + 1)/2 D (we will often use D z dd² /
will be interested in the leading order in d).
Under this mapping, have that /d/2vec (S) satisfies
d
| 12 2 Tr O(D).
(38)
for any S with asymptotically well-defined spectral density. In particular in state evolution u." vec (S*) is such that u / Q Moreover, we can define the correctly normalized sensing vectors
d(2 dab)
Alab) = V d+1 vee (Xx)) (ab) = v
X ~NO,1/DD)
(39)
2D
for all 1 1 a a a 5 bs d, where we used that X ~ GOE(d), giving
d +1
Tr(X"s]= Σ
vec (at)) vec (S)
Σ
A (ab) ((ab)
V22 Σ
((ab) W(ab)
d (ab)
(ab)
(ab)
(40)
where a n2/d2.
Thus, we can pick
((a e(V2a, 2b), R(w)= R(mat (w)/ vd/2) and 6(=)= = AA22 (41)
where mat () denotes the inverse vec (), is a standard Gaussian (we are restricting here to the Gaussian noise function Φ), and similarly we define Č by a rescaling of C. Finally, we define the equivalent vector problem in dimension D d(d + 1)/2 with N samples
N
W = arg min (w), with Evee (w) = Eā(a" w, 6(a" w²)) + R(w). (42)
WEd
In particular, the GAMP iteration described in Appendix A.3 for this loss solves (9) modulo the bijection vec (), with generic convex loss, regularization and constraint set C.
27

---

A.4.2 GAMP denoiser for the square loss
We directly specialize to the case of the square loss, but all this can be generalized to generic losses,
see [Loureiro al., 2021a]. For E(a, b) = (a- b)2 we have
gr. 8, b) = arg min sER
{22,) + 20
(2 r)² r 4bs
and g s, = $
(43)
+ 4b
bb+1 1+1/4
The associated state evolution equations read (recall that x(=*) 2" + VA/25, including the average over the noise Ç in the activation Φ in E.) N Bw b() 20 3-14
d'+1
3
m =
D E 10 ((=),b)) b]] = 22 g'-11
(44)
qh = BB ((= 0- = -2x 22---2++t4/2
(b++1/4)2
where we used that N/D = 2n/d2= 20.
A.4.3 GAMP denoiser for spectral regularization, including PSD constraints and nuclear/Frobenius regularization
Spectral denoising function e. with the dimension d)
We have (calling r mat (V2/dr) and d to avoid confusion
R(z) + 1 |r|1
e(r, k) = arg min xEĆ
k
arg min =eč
((v22 /dmatt (z))
マタ || z - k r11
(45)
= V d
k
2 vec
arg min Zec
R(2) + 4 ||
k 1
Now, assume that both C and R are spectral, meaning that they do not depend on the eigenvectors of Z. Then, if we consider the spectral decompositions r = ODO e(r, k) ULU" and we parametrize Z = VTVT, then for each T
U arg max Tr(VLV"TDO"), VEO(d)
(46)
which, by Von Neumann's 's trace inequality [Mirsky, 1975] is given by the rotation V such that U O aligns the eigenvalues of and D in decreasing order, which if we take the convention that spectral decomposition are given with eigenvalues sorted decreasingly, gives U O. Thus, the problem reduces to a spectral minimization
d
= arg min
d R
+ ET. i=1 2 i=1
Σ T.D:
(47)
TEC
where here we are abusing the notation by writing T; to mean Ta as is really a diagonal x matrix, and similarly for D. Notice that this expression is still general.
Spectral denoising function e for the case of the main text.
We now specialize to the case the
main text. C is the of PSD matrices and R(T)= d² (x T, + T/2 T, T?) then
ReLU (D; - -2x)
L 2T K
(48)
In the end, this means that if
vec (Va/20DOT)
(49)
with cigenvalues Dj sorted decreasingly, then
V 2 vec (o
{ d
1 ReLU (D-22) 0z)
e(r, k))
(50)
2T +
where here ReLU is applied component-wisc to the diagonal matrix D 2dLg-
28

---

State evolution equations. evolution equations
Now we need to derive explicit expressions for the associated state
m = D
Xo xo:e (oleloozz m² "nnl"udd')) ,d')
d = 1E el elv + u d') :el V + m uz ,d))
(51)
= T Ei 0,e( V + m u,
d,"); ,d'));
We revert the case of general C and R for this, assuming that R. is strictly convex over C for simplicity. It is useful to consider the following function
1
By min R(w): + k wll (w((w my mu(::
(k: Lu: mw)
D
wed
2
1
- 1 log [
dwe Baee-lee (((((w)++ ([Wl) /T m (w)"))) (52)
lim
D 8
B
Jwe
1 lim Ey log (ki qus mas 2, Xo):
D 8-+00
where the limiting procedure and all following interratooudeerivatiiilmiii exchanges are well defined by the strict convexity of R. and Z/ was defined in the last line. Then we have immediately
-m., L (ki, Gus m.)
1
E (u' velvvgee + m,,",, .d)i]]
D
(53)
20 V (ki Ou m.)
D
1
Et
(ee + mau" d') ;e ;e(vglz + m u,, dd)
Moreover (dropping the omnipresent 3 limit and average E, as well the inputs of Z for readability)
-20 (k: qus m.))
3 (R(())+ #1/ /ou(w :x) -m.. (w ;u"))
1
E
dw Σ W/zs
Vou
Zg
-a(R(())+ 311 w/l (w
E
dw Σ w.
Zg
((((()))+ 1|lw (/ (54)
Mootttman S Swed
E
dww;
D
Z
Er
Σ er, k)i vouettua
Σ 0,e(V -- x mi,"
where in the third line we used Stein's 's lemma, so that
m
-m.. Ti (el gio m²))
d 20, (dd Ly m
(55)
= 20, T (dd Lio m))
We just need to compute v for the sake of the state evolutions.
State evolution equations for the case of the main text. R(T) =
the set of PSD matrices and
T,), then
(k: Jn, m..) = 2
E4+
Σ E4+
+ ma
Σ 1a
k
LLDD L.D.
(56)
where D, the i-th eigenvalue of the matrix S" / m../m Z, and L, is determined by
L 2T k
Ma
ReLU (D, 25. 15/mm.)
(57)
29

---

giving
V (ki qu mm) = 2
Σ
Li + 7/2 Σ 12
k: Σ
1
ma
ELiDi L;Di
4
2
m
E
ReLU(D; - -28/mu)²
2(k k 2T)
(58)
m J2h/ma
de Woa/mmm (x) 22/man)
2(k: + 2T)
m
J( ( 22/ma),
2(k 2r)
where in the last step used that leading order the spectrum of S* "/u/mm/umma assumption in 1) to μ¹ /T//m. defined in Theorem I.
W concentrates (by
A.4.4 Final form of the state evolution and observables
Collecting the state evolution equations derived in Appendices A.4.2 and A.4.3, calling m, m, Yu q. E, ma m. qu ② and d = Σ. we get the system of equations
H1+1
2a
+54+174
m
2a
41/4
g+t1
=2a O" 2m 22
42741/4)
m'
=mp' 2(5 J( /i 28/m2)))m))
(1
(59)
q'
(1²')²² J( /m 22/m²)
($2
(mi') 0g: ( 'mm 2²/m²)
E
11+27
where J is defined in Theorem This reduces to the equations presented Theorem its fixed point and under the change of variable Vq/m,, 2/m.
The test error then is given by
Etest
Qo 2m + q 2ad² A/2.
(60)
The expression train loss instead van be derived by using the fact that the residuals in the data part of the loss can be computed from state evolution as q/16, and by evaluating the regularization at the spectral density μ4 (which is just the Tr of shift and rescaling of this spectral distribution) giving the expression in Theorem in the limit 7 + 0+
Notice that these state evolution can be also heuristically applied in the case problem has unique global minimum. This can be checked by having Σ < +oo, as Σ is a proxy for the inverse of the curvature of the loss at the global minimum [Clarté et al., 2023], which becomes flat when Σ +oo. Notice also that Σ can be used to guarantee, at the heurisite level, that the minimum of the global loss unique even without the need of the regularization 0.
as long as the
A.5 Replicon condition for Generalized Approximate Message Passing fixed points
For completeness, discuss in this section the pointwise convergence of the GAMP algorithm when initialized at a fixed point of the state evolution equations. While the convex nature of the problem ensure this convergence [Loureiro et al., 2021b], discussed here the explicit criterion that can also be directly checked within the state evolution formalism. As noted by Bolthausen [2014], it hinges on stability condition- innittionnkkonnnn known in statistical physics the replicon de Thoulesss (AT) condition [de Almeida and Thouless, 1978, De Dominicis and Kondor, 1983] which can be directly and easily checked from the state evolution equations.
We thus provide the replicon condition on point-wise convergence of GAMP for generic non-separable denoisers (see for instance Vilucchio et al. [2025] for the separable case).
30

---

Consider again the recursion (25)
u = A Ac drer(ue)
(61)
v' Ae, b
with the br, d, given in (26). We want assess linear stability. To this end, we suppose that the iteration is initialized at fixed point (u, (and that at this point we also assume that the nonlinearities g, e and the Onsager's is terms are constant in time), consider a Gaussian perturbation ~ (0, ella) of u, and compute whether the iteration converges back to the fixed point after such perturbation. Notice that we can avoid perturbing the Onsager's terms, as in the high nigh-dimensional limit they are independent on the iterates. We have (at first order in E)
nne Ac(u u + E) bg(e) = v A(Ve(u))E, new
A" g(v A(Ve(u))e + +eeu
=u +u =
D D- ((t))(Ve(u))e,
D
N
1 N
new u
up +
Σ
Σ
Σ
0n9h Σ Dee4
(62)
N
D
N
us Σ
(ActAns - D Suo (ankkk)))pppe @pgrdrezci,
where in the second to last step we used the explicit form of the Onsager's term d, and in the last step suppressed the dependencies of the functions 9, u, for clarity and passed in components notation.
The L2 norm of the perturbation u new equals (on average over the initial perturbation e)
Ee(uk
ux)2 ===EE EE Σ
Σ
(AuRAut
- N 1pu Opp
p===
Σ
Σ
(AuiA - N 1 90 Oreper
"5'= w/v=11
(63)
D
N
= 2
Σ
Σ
8v 0,
i =1
p.aip w!==
Σ (a,e,)²
Σ (0,g.)² nV=1
x D
D 1-==1
where we used that Ege,cy Sw, and the law of large number to substitute
(Avx Aus D- Ows D 35m 8 5pp'
N 6-16
(64)
where in the last step we only kept the term that will contribute leading order (equality at elading order is denoted by x. This is the generalization to non-separable functions of [Vilucchio et al., 2025, Definition 1].
Thus, the linear stability criterion for GAMP is
D
N Σ p,011
N
x Σ 00ee) $J=1
(0.gv)
<1
(65)
D
D
N
In particular, in the case of independent observations we will have 0,g9 0n and in the case of separable denoiser one would have 0ee; = 0, deg. Notice also that this criterion is independent of the value of the iterates u, the fixed points, as concentrates onto its cate-evolutioo-prrdiiee value.
31

---

In the case of &g loss +PSD + nuclear norm regularization, fixed point of the state evolution describes stable fixed point of GAMP if
f |de (3((2)
/ dy vz(v) ReLU(( - Ry -c)
<
2a.
(66)
y/
We have checked numerically that this condition was satisfied in our fixed point (in accord with Theorem 5).
B Minimal norm interpolation limit X + 0
Consider (6). We would like to give a prescription to manipulate this equations order to describe minimal regularization interpolators. We first remark that the limit À - 0+ of (6) as written describes the case non-regularized minimization, and thus Theorem will be valid in this case only for 0iintrrp. when only one interpolator of the training dataset exists.
Consider now the rescaling of (9) given by Å-I For any fixed positive A, this rescaling does not alter the solution of the minimization problem. In the limit À - 0+ instead, the loss first imposes that the global minimum is an interpolator of the training dataset, and then minimizes the regularization within the interpolator set. Thus, rescaling the loss by A-1 and then sending À + 0+ will describe minimal regularization interpolators, as long as Cinterp the noisy case (after that threshold no interpolator exists, and the minimization problem is ill-defined) of for all a in the noiseless case (as in this case there exists always one interpolator).
We practically achieve the loss rescaling in (6) by renaming de - e, and obtaining the new system of equations
4ad 2 = (6,((6))
(67)
Q' + + 2a62 10 = -1- (11-c())(66c))
equivalent to (6) for all Ā > 0, and then taking Ā 0+
Thus, summarize the learning curves at À 0+ found as follows.
In the noiseless case A = O, we solve (67) with Ā = 0 for all values of a.
In the noisy case A > 0, we solve (67) with À = 0 for all values of a < Qinter, and we solve (6) for = 0 for all values of a > Qinter-
Derivation of Result 1 and Corollary 1
C.1 Prerequisites
For both Result and Corollary we will need the following results on the spectral density μ² WJus....5. where B1 is the free convolution and Ps..... 44- /2=(5)))))) the semicircle distribution of radius 25 for 8 > O. Here 4² (x) /K*PMMP (VK*x), where JMPP. is the Prrchenko-Pasttu distribution [Marchenko and Pastur, 1967] with parameter x" (the asymptotic spectral distribution of A A/m where A R has i.i.d. zero-mean unit-variance components), and Q* =1*k*
We start by recalling that
[ +000
J (ô,s)
da (z(2) 5)) =²==Q²++++ 02 -2sM + = - dr p5(x) (I - s)², (68)
where
dr f=
dx=))=)()))) M M-= ar=fddan d -
Q' Q'=
(69)
and where we used that
dr i p((x)))=== / da depp f Mo., M
(70)
/ do px()))))²²
d do = Q" Q"+ 8
dd
32

---

by additivity of the mean and variance.
Now use [Maillard et al., 2024, Appendix D.3] to state that for any fixed x; for d - 0+, we have at leading order
5v1 Re* (3(2zv1 -()) = (1 x² (..)).
(71)
This will allow to compute the last integral in (68) when å < for some values of Indeed, when < 1 and 0 < K² < 1 the spectral density 143 is composed by small semicirele around the origin with mass 1 - k*, and an approximately μ -shaped bulk gapped away from the origin. So long as s lies in the gap between the two bulks, only this semicircle will contribute to (68). For R² > 1 instead, the bulk the origin is not present leading to zero contribution from all the integrals. The case K is more delicate, as there the spectral distribution of the target may be non non-gapped (for example, in the narrow target case). We recover this case by limiting procedure from the two sides.
C.2 Derivation of Result
To find the interpolation threshold, we consider (6) for À To do this, we need to make sure that we are in the Cinter region, where only one interpolator (noiseless case) or no interpolator (noisy case) exists, giving single minimum of the training loss. This can be checked by having
= ae < +00
(72)
where Σ was defined in (59). The interpolation threshold will be exactly at the point where ox e diverges.
Noisy case.
Consider the (6) with Ā = 0. We have
4ad = (,,(0,
(73)
1 + -/2 + 2a02 6² ((;,0)
We now consider the limit - +00, obtaining
{ 4ad = ((6
- + + 2a6 = ((6 0)
Oiner = 18 (8,00) Q' = (6, ((,
(74)
Q'
ie. equation for 5, which can be plugged in to directly find This gives the first part of Result 1. Notice that the value of found will be finite, giving also an analytic prediction of the height of the cusp of the test error at interpolation.
For A - +00, we see that a consistent solution is given by 6 - too (starting from (73) at finite 6, and then taking the limit). In that case, 11, is, at leading order, semicircle with radius 26, so that
J 0) 82 and ( R
(75)
implying that for large the interpolation threshold converges to 1/4.
Noiseless case. Here we can advance more. In the noiseless case A + O, we also know that after interpolation we have zero test error, hence å Thus, we can expand [(, 0) for small 5. Using (68) and (71) we have
O&J (6,0) = Os(Q" + + 0s I dr p (z) x²
= 28 0g 82(1 (1- k²)
d (
(76)
1 dy Pa.. (
= 25 0g 81 n²)²
z 8 2 (1- (1-x*)? nT
implying that the equation for is satisfied for 8 = O, and that
1 + 2x x* 22
Oiittr
(77)
33

---

Let us notice that the å = 0 solution here is valid for all a > Qinter we could have worked with (6) with À = 0 and finite e, and computed explicitly as function of a. Doing this shows that < +o0 for all a Qinter and that + +-00 exactly at the threshold. This concludes the derivation of Result
C.3 Derivation of Corollary
Consider first the case 0 xº < 1. We start from the stationary conditions for (6)
{ 4ad = JgJ 3 6, Ae
(78)
Q" + 200 + 3/2 da = -1--880 (0,)
To compute the strong recovery, i.c. the value of a at which the test error is zero, we look for the value of that is consistent with a solution of (6) in the limit - 0+. We assume the scaling
c= 881 c
(79)
and verify it cenfscoonsstentlly. We have that (71) implies at leading order
de
Ös
dr (z) (x Ac)²
= =s00 1 - -n²)) At/ōO/T
λ
dy 051 p x(y))
5v
k
= 038 (1 - (1-x²) {- P2c/BVT-R
de
2
dy (a) 1 8V1 - K²
(80)
28(1 - x²)² (ML22(2c) 2AaM + X2e² 2 (Ac) + +55(1 - xx)² (AeMSL) (Ac) M(0
= (k)² (Me) - (cM
where we defined the incomplete k-th moment of the semi-cirele distribution as
M 1 dy Ma.c (,. (²)
(81)
Similarly
(1- s0.) / de uz(x) (x - s)2 s
de dx pT(()) (x= Xee²
+ 2c / de
dr (z(())))) (x - -c)
(82)
// da (z(x)) (x= -xc2)
de
8 x²)² [M 32e
This leads to the equations (at leading order in 8 + 0+)
tov LovI-K=A [1 x²) [ (c) c. =M.ld(c)
A
(83)
2 --)=-))= - [1 x² (.l - m!!
482 + 2evI-x-8
where we renamed ct + (which will allow to be in the interpolation limit for Ā = 0 as detailed in Appendix B). Define
and A
(84)
48 48
482
34

---

that is the small regularization limit and noisless limit at the critical scaling. Then the equations read
A - - = 2 - x²)² (cM))((e) (c) - 2M..2 + I-A²
(85)
_ - x=²
- (M2((c)-cM
Osstrong
giving one equation for and one for dsstrong given c. By computing the next-to-leading order, one could access the speed at which - Olstrong in 6, invert it and find the critical scalings of X and A
as a function of Astrong a. In the case Ā = A = 0 we have the simpler equation
-1 (1-k*) xx) (0 (c) M.H
(86)
Ostrong = 1 [1 - x²²² x1= (M (c) (c)
which modulo conversions gives the same lsstrong as [Donoho et al., 2013, 12]. For x² 1, the same equations hold with all M contributions giving (again for À A 0)
zero (see discussion above),
asstrong =
(87)
This shows Corollary 1.
D Derivation of Result 2
We start again from (6)
{ 4ad = = (0,
(88)
Q- + 2ad2 +
8² == =
[66, Xe) cx,(0.1) eλ).
We redefine de + and consider the limit n² - 0 under the scaling ansatz a = ōxx", 5 = dx* 1..--11 1/2
cw 1/2 and x = 1/2 Notice that Q + x²* vo 1 in the limit. The equations read
f 4ād - \o 0₂J (8,e) e)
(89)
1 + 2nd +
X (1 cd.)J(dn" 1/2 cxx--112 -1/2
Then
+00
(dr--1122 -xc" 112)
(drs
dx Fa 1/ (x) (x= - CK 1122g12222
(90)
x
[
+.00
dy 112 1/2 Hare (ync" 11/3 (y c)2.
We now use the fact that at leading order for small K
v(y) Rs x--11/² 1aa-- (yn" -1/2)
(91)
is given by a semi-circle distribution of radius 2d centered at zero with mass 1 - n², plus Dirac's delta spike at y = 1 dl with mass n² if d2 < 1, see [Maillard et al., 2024, Appendix E.
We then have the following cases in which the spike does not contribute.
No spike d² > and e <>> 2d, or spike 0 < of < and c > 1 1 df > 2d. Then the integral
J does not contribute to the equations. Thus
4ād d
(92)
1 2nd +
===0
d2
i+A/2
2
2a
under the condition
p p>1 á 1+A/2
1+
X²
c> 2d
< 32(+-/22
2
x2
à < min
2
32(1 + 2/2)
(93)
or
1 <1 - aة 1+4/2
1/1/2
Ā 2(1 + +/22)
c>1+8 & - < 2-1(1
2
2
< à
4
(94)
35

---

No spike d? > and bulk integral contribution - (2d) In this case tends to 2d with the appropriate rate order have order ((1) contribution from the bulk integral in the equations. We have, calling 2d = dt i.e. d(2 t) for some / >> 0
2d 1 dy Jun.. (g) (y d(2 1))² = x x-
x²"
dy Ma.c. (1) (y - 2 + 1)²
(2-1)d
2-t
16t
+ +0 [n* -000m* (x1-))0/2)
= km
105m
(95)
giving
16d40/22
jbulk
RJ 0
105TH*
16d15/2
Ju.bbllk
T
(96)
15TH"
8dt5/2 T
J.
2 from which we see that the bulk integral contributes to non-diverging order if (3/2 O(n)), giving the equations
15TK"
{ 4ād =T
=
T = 20
20 1 A/2) - -
(97)
1 + 2nd
+ - - dT
d2
1+A/2
24
under the conditions
dc >>> = ā < 1+4/2
X²
1+ A/2
24 x²
<ā <
(98)
T> á (/2+
32(1 A/2)
2a
Thus, we start finding that
1 + A/2
211 4/4))
2(1
MSE = 1 for ā < max
(99)
2
4
We now consider the case in which the spike contributes.
If there is the spike df < and it is the only contribution 2d < c < equations read
+ d, then the
4ad 4 4d(1 + d2 c) 0
(100)
1 2nd
L = (1+
2c 20 (
This system can be solved explicitly under the conditions above, giving quite an unmanage- able expression. It reduces 5 0 for A = A O.
If there is the spike d² < and it contributes along with the bulk (see discussion above and (96) e + (2d)-, then the equations read
{
[ 2 2nd / + A = d)a + 4d(1 - d)² d7
f 4d(1 +
(101)
These give again unmanageable expressions, but for A 0 it gives
MSE á (4 v Ga - 2)
(102)
One can check by explicit solution that the last two cases lead to test error strictly smaller than one. The last two cases can be casily solve numerically, allowing to plot the curves in Figure 4.
Finally, the large a behavior can be found by considering the last case
4ād } 4d(1 d)² +T
(103)
2nd2 - = dd+ 4d(1 d)2 df
36

---

under the scaling ansatz
1
di + )
Ti
d
do
T va
To va +
(104)
va
and solving the equations perturbatively gives
VA and d1 3VD do 2
(105)
giving the large a scaling presented in Result 2. This completes the derivation Result 2.
E Details of the numerical implementation of Theorem
We provide the code for the numerical implementation of the equations in Theorem and the experiments at https: thub. com/sPOC coom///PC-ggroop//vvrrrraaaaaa groon//Overparraetrieedll
The numerical implementation of (6) reduces, at its core, to two sub-tasks: the numerical evaluation of p. the integration involved in computing (a, b) and its partial derivatives, and the numerical solution of the equations themselves.
Computing -. Recall that the spectral density μ4, is the free convolution of rescaled Marchenko- Pastur μ² distribution, and that of semicircle distribution with radius 2a. In particular, μ (x) VK* (V.".. where JMLP. is the Marchenko- Pastur distribution with parameter H² (the asymp- totic spectral distribution A A m where A E mmd has i.i.d. zero-mean unit-variance compo- nents). This free convolution can be computed using standard random matrix theory [Potters and Bouchaud, 2020] tools. We report here the procedure as described in Maillard et al. [2024], and summarize here only the steps without providing derivation.
To compute the spectral density under consideration, first we fix the noise level and the location at which we want to compute 1 (Ir). Then, we solve the following cubic equation (looking for the solution with largest imaginary part, if all solutions are real then the spectral density that location zero)
(1)g
g2
-
2
g²
2
VR
1 =-
(106)
VK-
VK-
VK*
where i7 with small positive constant.
The solution g - g=)) of the equation is the so-called Stieltjes transform of μ²¹ (xx) i.e.
g(2) / dx j(z)
(107)
I --2
which can be inverted by the Stieltjes-Pene Perron inversion formula, i.e.
(x) lim 1 Im Juy (x iT).
(108)
- π
In practice, the limit done by using T 10-12 directly in (106).
Additionally, by imposing that the discriminant of (106) is zero we obtain an equation for x (setting 0) that allows precisely evaluate the boundaries of each of the bulks of μ (the distribution has two bulks in the low-noise setting, and one single bulk otherwise, with the splitting threshold depending non-trivially on x² and a).
Computing (a, b). We use the estimate of the bulk boundaries to set-up an efficient integration scheme to finally compute (a, b). We first compute the bulk boundaries, then intersect the support of the bulks with the integration region (b, +oo), and finally for each bulk integrate (x) b)² using quad from the Scipy library in Python. This explicit use of the bulk boundaries allows precise evaluation of J(a b) even the low-noise regime, where one of the bulks has very small support with quite large values for the spectral density.
Finally, we compute the partial derivatives of J(a, b) by centered finite differences, with step size equal to 10-$
37

---

Numerical solution of the equations. To solve numerically (6), we find it convenient to revert to the state evolution equations presented Appendix A.4, equation (59). We follow the prescribed iteration, possibly damping the updates with a factor small as 10-2, and declaring convergence when the Fuclidean distance between two subsequent updates falls below a prescribed tolerance of at least 10-1 It is also convenient to adopt planting scheme, where the equations for given value of X, A, x² are solved for one initial value of (we found that value around the mid-point between a 0 and a = Ostronn works best), and then the rest learning curve as a function of is computed by successively using the solution at value as the initialization for that of + da, where da a small step-size.
F Details of the experiments
For Figure right and d 100 used the CVXPY package in Python. Ahe other experiments realized PyTorch. We instantiate the student weights randomly as centered Gaussian variables with standard deviation 10 and the target ones with variance appropriately changing the functional form of the target. Figure right we optimize using LBFGS for the sake of efficiency. For Figure left optimize using the GD iteration
W 1+1
w1
2XT
md
7
Wi
1
m
m
okk
W
vdd
X2
(109)
1=1
with 13 20.
G Arbitrary sign in the second layer weights
key limitation of the network in (1) is that it can only learn targets with positive definite S This is because the second layer weights are all positive. Within formalism consider more generic function with fixed ag E (-1,1) with at least positive and negative entries.
W)
Σ aooK
Wk Vd
'rr
X(()
o.w.w?
(110)
dm
with loss
a. w.w.""" ))
(w) =
Σ Tr X(x) 5
+
|w;
(111)
dm
1=11
where
m
5'
a
ww((w;)'
(112)
dmm
d=
Our goal will be to show that minimizing over Cw(W) is equivalent to minimize Cs(S) from (9) over all symmetric matrices S
2 (S (*)
x xxxxI II
$ = arg min ES(S), with Ls(S) =
Tr
+ Vmddl|S|I.. (113)
ScSym(d)
dd
The argument goes as follows. For any fixed value o, define the sets of indices P, N as
P (kla: 0),
N = =Kkaa < <0}
(114)
and additionally, define
(Sp)
Σ WesWeng
(Sx) Vmd
(115)
md
kEP
KEN
38

---

The matrix S is then given by the sum S = Sp+Sy, and we remark that both matrices are symmetric, non-rank constrained and respectively positive and negative semi-definite. The minimization of Lw (W) over W can be rewritten as (Sp, Sx) arg min (Sp(Sp,
Sp20 So
(116)
with (PN SN) = Σ
Tr 1T + SN - SS)] vmdd(]|Spll.. + I[S]))
1am1
What we have to show is that (113) and (116) have the same optimal value, and that the minimizer $ of (113) yields a minimizer (Sp, Sx) of (116) by taking the positive and negative spectral parts of S. First, we write
n
Xpx
Tla
12 + +vndAR(S)
min LpN(Sp, (Sp, = min
Tr
(S (S-
8*)
(117)
Sp20
SESym(d)
Vd
Sw
where
R(S) = inf Spł0. Sy =0 Sp+
(1Sp|l~ + (|Sx
(118)
By the triangle inequality
||S|| ||S + Swll. S || + ||Sv
(119)
hence R(S) 2 ||||, This bound in fact achievable: let be symmetric, with spectral decomposi- tion
s U diag(or......o oa)
(120)
Define its positive and negative spectral parts
S+ = U diag(o )TT
S_ U diag(o,) UUT,
(121)
where
tt = max(o;; 0),
of = min(o,; 0) S.
(122)
Then S+ 0, 3 0, and S = St + S_. Moreover,
|| Σ at. ||-|| Σ (-07),
(123)
:0:30
00
so
|S+ + ||S_ = Σ | ||||.
Thus, for this admissible decomposition R(S) S ||S|| which combined with the other inequality gives us R(S)= = ||S| This proves the claim.
Asymptotics without PSD constraint. positivity constraint:
We are solving the same problem as (22), just without the
2
x Ha
$ arg min Z(S), with Z(S) SE)ym(d)
=
Tr
(S - S*))
+Vmd
Vd
(124)
For this case, the spectral denoising function (48) becomes
L; + k Softhhessholding (D 24
(125)
where
Threhhooold (z, 0) = sign(x) max [x] - 0,03.
(126)
Similarly, equation (57) needs to be substituted by my
L 2r + k
SoftThresholding (D., (0.225/m.)
(127)
The final state evolution will be unchanged by redefining J in (6)
/ /=|s dx p. (x) ([ar) b)
[(a
(128)
We illustrate how this changes the theoretical predictions in Figure 5.
39

---

10a
A-cf
0.00
4.0.0
0.05
Tist arror
10
20
0.2
0.3
0.7
0.8
Sample complexity a n/dd
Figure 5: Test error as a function of the sample complexity a for different values of the regularization when optimizing without PSD constraint described in G. Here K = 0.2 and A 0.5. Notice that this case the interpolation peak at a = 0.5, and there the test error diverges.
40


Reviews:
[{"review_id": "8GmvryDCOV", "reviewer": "Reviewer_8thr", "summary": "The paper delivers a technically rigorous analysis of two‐layer quadratic networks trained by $\\ell_2$‐regularized empirical risk minimization on high‐dimensional Gaussian data, by showing that the nonconvex learning problem can be exactly reformulated as a convex, nuclear‐norm–penalized matrix sensing task. Through precise AMP state‐evolution arguments, the author obtain closed‐form expressions for training and generalization errors in the limit $\\alpha = n/d^2 = O(1)$, $m^\\star/d = O(1)$ and $m/d = O(1)$, where $n$ is the number of measurements, $d$ is the embedding dimension, $m$ is the number of neurons (i.e., rank of the weight matrix) in the learner's (i.e., student) model and $m^\\star$ is the same for the teacher model.\n\nThe main results are as follows,\n\n1. The calculation of an interpolation threshold $\\alpha^\\star_1$ in the case of an i.i.d. prior on $w^\\star$ (referred to as the MP case), which corresponds to a characterization of the ratio $\\alpha$ for which interpolators collapse to a single solution as the nuclear norm regularization strength goes to $0$. This is a statement about the optimization landscape of the regularized $\\ell_2$-regularized empirical risk.\n\n2. The calculation and a strong recovery threshold, $\\alpha^\\star_2$ in the MP case, beyond which perfect generalization occurs in the noiseless setting. This is shown to be $1/2$ when $m^\\star/d \\ge 1$ (overparameterized setting).\n\nTheir results demonstrate that $\\ell_2$ weight decay implicitly enforces low‐rank structure and also results in test error that is independent of $m$ in the overparameterized setting.", "questions": "N/A", "limitations": "The paper is restricted to the case of quadratic activations and a single layer. While I do not view these as weaknesses of the paper, I think it would be nice if the authors addressed what happens if the activation function is no longer quadratic, for instance.", "rating": 3, "confidence": 1, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 1, "significance": 2, "originality": 3, "strengths_and_weaknesses": "I am not an expert in this area, and am reviewing this paper as a member of the broader audience. Perhaps someone more well versed with the statistical physics analyses of this problem and mean-field approximations for matrix completion in the overparameterized regime may have a different take about this, but overall I thought that the paper was incredibly hard to read. The main result is quite dense, and missing many simple interpretations. It is written for an expert who already understands the setting (which is admittedly very specific). There are several notations (for instance, free convolution) which were not defined anywhere in the paper, which I believe is necessary for the results to be understood in a self contained manner. Overall, I would recommend that the paper be simplified and presented in a top-down approach, and even potentially lengthened for the goal of making it easier to motivate the main result. I believe my review does not adequately address the technical contribution of the paper, which I was unable to grasp fully. However, improving the writing in the paper seems to be a prerequisite to be able to carry this out.\n\nMinor:\n\n1. $\\kappa^\\star$ is denoted $\\kappa_\\star$ in some locations.", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their thoughtful comments and for engaging with the paper \"as a member of the broader audience\".\n\nWe acknowledge that the paper is technical and that some of the mathematical tools—such as free convolution and matrix compressed sensing—may be unfamiliar to non-specialists. However, the analysis of Hermite expansions, polynomial networks, and student-teacher models with quadratic activations is a well-established and active line of work in theoretical machine learning. Our references include numerous recent contributions in this area.\n\nThat said, we appreciate the reviewer’s suggestion and agree that the exposition can be improved in places. In particular, we will clarify the definitions of specialized terms and notations such as free convolution and better motivate our main result in Section 2. We will also fix notational inconsistencies (e.g., the conflict between $\\phi$ and $\\varphi$, the $\\kappa^*$).\n\nAs for the question of generalizing beyond quadratic activations: we agree that this is a natural direction, but it's important to highlight that the quadratic case is a necessary prerequisite. The quadratic activation allows for an exact mapping to a convex matrix sensing problem, which underpins our closed-form results. Moving to more general activations—e.g., higher-order monomials—would correspond to a tensor compressed sensing, which is a significantly harder problem for which sharp asymptotic results remain largely open. This is the subject of ongoing work. Nonetheless, the study of quadratic networks is not only tractable but also a classical and insightful approach to understanding nonlinear learning in overparameterized models.\n\nRegarding the broader significance, we would like to emphasize that our analysis sheds light on how feature learning, low-rank bias, and generalization thresholds emerge in overparameterized networks beyond the NTK/lazy regime. While the setting is stylized (quadratic activations, Gaussian inputs), it allows us to rigorously distinguish between regimes where learning occurs and where it does not—something that remains difficult in more general settings. We will add more discussion about these aspects."}, {"review_id": "RCqk7pUM3E", "reviewer": "Reviewer_aFup", "summary": "This study presents an analysis of empirical risk minimization over the quadratic loss for a two-layer neural network with extensive width and quadratic activations. The authors rigorously derive predictions for the generalization error in high dimensions. The results are then analyzed and used to derive thresholds for interpolation and strong recovery. Finally, all results are placed in the context of related literature on different models and compared with previous Bayes-optimal baselines for the same model.", "questions": "### Questions\n- What are the key technical differences in the proofs that distinguish the ERM setting considered here from the Bayes-optimal analyses by Maillard et al. [2024] and Xu et al. [2025]?\n- Can you comment on the gap between Bayes-optimal performance and the best ERM error in Figure 1 and Figure 2 (left plots)? Does this suggest the presence of a statistical-to-computational gap?\n- In line 268, you mention \"reflecting the structural advantage of the data over random labeling,\" but it is unclear to me how the previous reasoning on $\\Delta$ and $\\kappa^*$ implies this. Could you elaborate further?\n\n### Minor Corrections\n- Line 196: \"then,\" not \"than.\"\n- In equation (13), the cases for $\\kappa^* $  repeat the same condition. I assume the bottom line should state $\\kappa^* \\ge 1$.", "limitations": "Yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 3, "significance": 3, "originality": 2, "strengths_and_weaknesses": "### Strengths\n- The wide network setting is considered to be challenging.\n- The setting of Theorem 1 is very general: very few assumptions on the spectral density of $S^*$ are required, providing versatility for different applications.\n- This work shows that $\\ell^2$ regularization over $W$ translates into nuclear norm regularization over $S$. This correspondence of regularizations is completely new to me.\n- The rigorous delineation of thresholds for interpolation and strong recovery is an important contribution to understanding networks with extensive structure. The fact that these thresholds differ from the kernel ones when $\\kappa^*$ is small is noteworthy.\n- The results in the paper disprove a conjecture on interpolation thresholds from [Sarao Mannelli et al., 2020].\n\n### Weaknesses\n- The assumption of i.i.d. Gaussian noise is very restrictive, although it is shared with most of the related literature.\n- The quadratic activation assumption is restrictive. However, given the other challenges this model presents, together with the fact that several related works share this assumption, I believe this limitation is not too impactful.\n- Several works on this model have already appeared, especially the Bayes-optimal analyses by Maillard et al. [2024] and Xu et al. [2025]. While it is clear that ERM is a different problem from Bayes-optimal analysis, the two settings are related and share some core analytical ideas. In my view, this slightly impacts the originality and significance score.", "was_revised": true, "final_justification": "The authors answered clearly to all my quesitons. Stil, I believe that the fact that the setup is very similar to reference Maillard et al. 2024 should be counted, slightly limiting the originality from the modeling poin of view.  Otherwise my rating would be 5, since in all the other aspects I believe this work is very interesting and analyzes thoroughly a particular phenomenology.", "rebuttal": "We thank the reviewer for their constructive comments.\n\n**Q1**: While the target function considered is the same as in the Bayes-Optimal setting, the nature of the problem is fundamentally different. Maillard et al. and Xu et al. analyze the Bayes-optimal performance, i.e., the minimum test error achievable by any estimator. Their results do not pertain to neural networks per se, but rather to the theoretical limits of inference. In contrast, our work asks: What does a neural network trained via empirical risk minimization (ERM) actually learn?\n\nFrom a technical standpoint, although both approaches leverage the Gaussian universality principle, the rest of the analysis is entirely different. Bayes-optimal proofs benefit from powerful interpolation techniques and concentration inequalities that are available in the information-theoretic setting. These tools are not applicable in our case.\n\nTo handle the ERM setting, we map the original non-linear optimization to a convex matrix compressed sensing problem and analyze it via Approximate Message Passing (AMP) with non-separable denoisers. This AMP is specifically designed so that its fixed point coincides with the solution of the ERM, thus providing a rigorous and constructive characterization of both generalization error and spectral properties of the learned weights. This approach also allows us to analyze the role of overparameterization, which is inaccessible through purely Bayes-optimal tools.\n\n**Q2**:  This gap does not indicate a statistical-to-computational gap in the usual sense. Rather, it reflects the difference between the information-theoretically optimal estimator (which assumes full knowledge of the model, including the rank or spectrum of the target function) and the ERM solution, which is constrained by the use of a generic $\\ell_2$ (or equivalently, nuclear norm) regularization.\n\nIn essence, the Bayes-optimal algorithm exploits prior knowledge about the structure of the teacher—most notably, its rank—and can adapt perfectly. The ERM solution instead imposes a generic form of spectral regularization without access to such information. Despite this, we show that ERM achieves nearly optimal performance, often surprisingly close to the Bayes-optimal curve. But some gap is inevitable due to the mismatch in available information and inductive bias.\n\n**Q3**:  This refers to the fact that the interpolation threshold depends non-trivially on the structure of the target function. When $\\kappa^* > 0$ and $\\Delta < \\infty$, the dataset is not unstructured: it contains meaningful correlations inherited from the structure of the teacher. This makes it easier to fit the data than in the worst-case setting of random labels. As a result, interpolation becomes possible at a lower sample complexity than $d^2/2$, when the number of samples equals the numbers of free parameters of the network, which would be the threshold in the random-label scenario."}, {"review_id": "VH7NbuPUbs", "reviewer": "Reviewer_vWPi", "summary": "The paper analyzes the training and test error of regularized ERM solutions of the empirical square loss for two-layer networks with quadratic activations. They assume that the teacher network is also a quadratic two-layer network, and allow for label noise. They focus on the high-dimensional limit with quadratically many samples and certain bounds on the widths. They provide closed-form expressions for the training and test losses. They use their result to analyze some more specific settings and properties of the solution.", "questions": "See the question in the strengths and weaknesses section.", "limitations": "Yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 3, "strengths_and_weaknesses": "The paper analyzes a basic setting and proves strong and highly non-trivial results for the high-dimensional limit. I believe the results are significant and contribute to our understanding of the problem.\n\nCould the authors also compare their results with the following paper? “On the Power of Over-parametrization in Neural Networks with Quadratic Activation”, Du and Li (2018)\n\nOverall, other than the above question and the obvious limitations mentioned in the last paragraph of the paper, I don’t have further comments. Indeed, the paper considers a rather specific setting with many assumptions, but I still believe that a detailed analysis of this setting is of interest.", "was_revised": true, "final_justification": "I maintain my original evaluation.", "rebuttal": "We thank the reviewer for the positive assessment and for pointing out the relevant work by Du and Li (2018). While our focus is quite different—centered on a precise asymptotic characterization of the global minima of ERM in the high-dimensional regime—we agree that their analysis of the optimization landscape of overparameterized quadratic networks is a valuable and complementary perspective.\n\nTheir work studies convergence guarantees of gradient descent in the infinite sample regime and under assumptions that ensure benign landscapes. In contrast, our work focuses on finite-sample generalization, spectral properties, and test error asymptotics in the high-dimensional setting with quadratically many samples, and does not address convergence per se. As such, the goals and techniques are distinct, but we agree this is relevant related work and will include a proper citation and brief discussion in the revised manuscript."}, {"review_id": "YyoPr3aYfn", "reviewer": "Reviewer_5q53", "summary": "The authors analyze a two-layer, overparameterized neural network with quadratic activation, trained by empirical risk minimization (ERM) on data generated by the same model. They show that, in the high-dimensional limit (input dimension $d$, number of samples $n$, network width $m$ all  $\\rightarrow \\infty$ at fixed ratios), the nonconvex ERM problem can be exactly reformulated as a convex nuclear-norm‐penalized positive semidefinite matrix sensing problem. Leveraging Gaussian universality, AMP/state‐evolution, and convex‐optimization tools, they derive closed-form asymptotic expressions for the training error, test error, and singular‐value distribution of the learned weight matrix. Their formulas reveal sharp thresholds for perfect recovery, interpolation, and the double‐descent phenomenon as functions of sample complexity $d^2$, width ratio $\\kappa$, regularization strength $\\lambda$, and noise level $\\Delta$.", "questions": "1. I want to make sure if the training and testing errors in (7) can be always non-negative?\n\n2. Standard GAMP / AMP state‐evolution theory covers separable scalar denoisers. Here your denoiser acts on symmetric matrix blocks. What modifications to the state‐evolution proof are needed to handle this non‐separable, PSD‐projected “denoiser”? Are there additional convergence or stability conditions?\n\n3. In the unregularized case ($\\lambda=0$) you identify an interpolation threshold αinterαinter​. Is it possible that local but non-global minima exist just below $\\alpha_{inter}$? \n\n4. For the low rank setting $\\kappa^\\star <<1$, can you compare learning performance with work [1]? \n[1] Li et al. (COLT 2018) in “Algorithmic Regularization in Over-parameterized Matrix Sensing and Neural Networks with Quadratic Activations.”", "limitations": "1. Authors study the well-specified student-teacher model and quadratic activation,  the more realistic setting is considering mis-specified case where student and teacher have different models and general activation functions beyond quadratic and smooth activations such as widely used ReLU-type activation functions.\n\n2. All sharp predictions are exact as $d,n,m \\rightarrow \\infty$. No finite-$d$ error bounds or convergence rates are provided. For moderate dimensions, it’s unclear how large the bias or variance of the asymptotic formulas is.  \n \n3. Limited insight on feature learning. By focusing on a fixed quadratic feature map, the paper sidesteps any notion of learning useful representations from raw data. All the heavy lifting happens in the convex PSD stage, with no mechanism for adapting or discovering features—a key strength of deep networks in practice.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 3, "strengths_and_weaknesses": "**Strengths**\n1. Exact asymptotics: Delivers fully explicit high-dimensional limits for both training and generalization error—stronger than typical “order-level” bounds.\n\n2. Convex reformulation: The reduction from a nonconvex quadratic network to a convex nuclear-norm problem is conceptually elegant and may inspire similar mappings for other architectures.\n\n3. Universality: By invoking one-dimensional CLT and an interpolation argument, they show their results hold for a broad class of input distributions, not just Gaussian.\n\n4. Numerical Validation: Experiments in moderate dimensions (e.g. $d=50,100,300$) match the theory closely, demonstrating practical relevance of the asymptotics.\n\n**Weaknesses**\n1. Model specificity: Focuses exclusively on centered quadratic activations; it is unclear how to adapt to ReLU, tanh, or deeper nets.\n\n2. Synthetic data: All experiments use rotationally invariant Gaussian-like data; performance on real-world datasets remains untested.\n\n3. Regularization dependence: The sharp formulas require nonzero nuclear regularization $\\lambda>0$; the purely unregularized case is only partially characterized by an interpolation threshold. Actually, many existing works focus on learning theory of regularization-free models that demonstrate the optimization methods can automatically found the parameters with good generalization performance from multiple solutions.\n\n4. Not well-defined notations. For example, authors used semicircle distribution and free convolution terms in Theorem 1 without introduced beforehand. The $\\delta$ in defined  radius of semicircle distribution conflicts with the $\\delta$ function in Eq. (8).", "was_revised": true, "final_justification": "I keep my recommendation at 4 (Borderline accept). The paper provides sharp, explicit asymptotics for ERM in quadratic two-layer networks via a clean convex reformulation and AMP/SE analysis. After the rebuttal and discussion, several of my concerns were addressed; a few remain open but do not outweigh the technical contribution.", "rebuttal": "We thank the reviewer for their constructive comments. \n\n**W1** We agree and acknowledge this in the conclusion. Generic activation is an open challenge. See also the answer to referee 8thr. \n\n**W2**  The contribution of our paper is a theoretical insight into the mechanisms of feature learning under overparametrization. Single-hidden-layer quadratic networks have limited expressive power and thus their performance on real datasets will not be very good. It would, however, be interesting to construct models for the data structure that would reproduce the learning curves on real datasets. We will add a comment on this point. \n\n**W3** \nTo study which solution is found in the unregularized case in the interpolation regime, a sharp analysis of the gradient descent algorithm would be needed. This is a challenging open problem even in simpler settings and is beyond the scope of the present paper. The regularisation ensures that the ERM is well defined and leads to interesting and new insights. One can take the limit of small regularisation in our equations (appendix B), but in general it will not give the same result as the completely regularisation-free case. \n\nFor large enough sample complexity, when the network cannot interpolate anymore, the small regularisation limit accurately describes the minima of the unregularised loss.\n\n**W4** We will fix the notation issues, and we thank them for spotting them.\n\n\n**Q1** Yes, the quantities in equation (7) represent squared errors (training and test), and are therefore non-negative by construction. \n\n**Q2** Indeed one must uses non-separable denoisers in AMP. Surprisingly, this does not introduce much difference, which is one of the stenghts of the AMP formalism. This can be done following the framework of Berthier et al. [2020], which rigorously extends AMP to non-separable denoisers, including those acting on matrix-valued inputs. The key requirement is that the denoising function is Lipschitz, which holds in our case: the denoiser is a soft-thresholding operator on the singular values (Appendix A.4.3). Furthermore, Appendix A.5 outlines a sufficient condition for point-wise convergence of AMP in this setting, which is always satisfied for our problem.\n\n**Q3** In the overparametrized case, Venturi et al showed the absence of spurious minima.\n\n**Q4** Comparison with Li et al. (COLT 2018): Thank you for highlighting this relevant work—we will cite and briefly discuss it in a revised version. In the low-rank regime, our results yield a sharper threshold: as shown in Figure 3 (right) and Equation (17), recovery is possible with $n \\sim d m$ samples. This improves upon the scaling $n \\sim d m^2$ established in Li et al. for similar models, highlighting a more favorable sample complexity for the overparameterized setting with nuclear norm bias.\n\n**L1** In our work, we consider the mis-specified case where the student and teacher have different models (the student is wider than the dimension, while the teacher's width is varied). The activation being quadratic is indeed an important limitation, but going beyond it is a widely open problem, see also answer to referee  8thr. \n\n**L2** Finite-size accuracy of asymptotic predictions: As shown in Figure 1, the asymptotic predictions already match simulations remarkably well even at very moderate dimensions (e.g., $d = 50$). While we do not provide formal finite-size error bounds, the empirical agreement suggests that bias and variance are small, and likely decay rapidly with dimension. Deriving such bounds rigorously (e.g., along the lines of Rush and Venkataramanan, 2018) is an interesting direction for future work. We do, however, provide rates in the low rank regime in eq.(19) (i.e. the generalization decays as $n^{-1}$.\n\n**L3**: We respectfully but strongly disagree with the reviewer’s assessment. A key contribution of our work is to show that feature learning does occur, and we characterize it precisely. Specifically, we demonstrate that ERM training in this regime induces a nuclear norm bias on the learned feature matrix, as opposed to the Frobenius norm regularization that arises in lazy or NTK-like settings.\n\nThis distinction is crucial: just as in matrix compressed sensing, Frobenius regularization ignores low-rank structure and fails to exploit sparsity, while nuclear norm regularization leads to Bayes-optimal recovery. In our setting, this is reflected in Result 2 and Equation (19), where the nuclear-norm–biased ERM achieves optimal test error rates, while NTK-type lazy training would yield near-random performance.\n\nWe will add a comment in the revised version to highlight this important distinction and clarify how our work explicitly connects feature learning with training beyond the lazy regime."}]

Author rebuttal:

Meta-review: This manuscript provides thorough analysis of a simple two layer neural network with quadratic activations trained on synthetic data. In particular, sharp results are provided for both training and test error in specific limits (related to overparametrization). Simple numerical experiments highlight that the theory is illustrative.

The main strength of this manuscript is its sharp characterization of the target model: the theory it provides leads to many interesting follow up observations about the model behavior.

Conversely, the primary weakness of the manuscript is its highly restrictive model and data generation process. In addition, aspects of the presentation could be improved.

Ultimately, the strength of the theoretical results and insights that follow outweigh the restrictiveness of the model. Results of this type are, for the moment, likely limited to more restricted settings. The hope is that the provide stepping stones to further analysis of more realistic models.
Decision: Accept (poster)