The Nuclear Route: Sharp Asymptotics of ERM in Overparameterized Quadratic Networks

We thank the reviewer for their constructive comments.

W1 We agree and acknowledge this in the conclusion. Generic activation is an open challenge. See also the answer to referee 8thr.

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.

W3 To 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.

For large enough sample complexity, when the network cannot interpolate anymore, the small regularisation limit accurately describes the minima of the unregularised loss.

W4 We will fix the notation issues, and we thank them for spotting them.

Q1 Yes, the quantities in equation (7) represent squared errors (training and test), and are therefore non-negative by construction.

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.

Q3 In the overparametrized case, Venturi et al showed the absence of spurious minima.

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.

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.

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}$.

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.

This 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.

We 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.

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.

Their 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.

We thank the reviewer for their thoughtful comments and for engaging with the paper "as a member of the broader audience".

We 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.

That 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^*$).

As 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.

Regarding 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.

We thank the reviewer for their constructive comments.

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?

From 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.

To 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.

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.

In 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.

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.