acceptodds
Under review as a conference paper at ICLR 2027

Quadratic Weak-to-Strong Generalization in Random Feature Networks via Random Matrix Theory

Abstract

Weak-to-strong generalization is the phenomenon where a strong student model trained with labels produced by a weak teacher model is able to generalize better than the teacher. In this paper, we study this phenomenon in two-layer random feature networks where the model strength is determined by its width. Using tools from random matrix theory, we derive deterministic equivalents for the population errors of an optimally trained teacher and a student trained with gradient flow. For ReLU activation and a pure spherical harmonic target, we obtain sharp asymptotics under a Gaussian universality assumption, showing a quadratic improvement: the student error scales as the square of the teacher error. These results attain the general lower bound of Medvedev et al. (2025). We also analyze how the student behaves under more general stopping times and targets supported on multiple harmonic degrees, characterizing the regimes in which weak-to-strong generalization occurs and identifying the transition between quadratic, non-quadratic, and no improvement.

Primary area:
learning theory
Keywords:
random features, random matrix theory, generalization, weak-to-strong

Reviews

Among:
Shape:
1234this paper, Top 4%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.25 over 4 reviews, above 96% of the others.
Reviewer_smqCOpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
1
Presentation
2
Soundness
1
Read review
Paper summary

This paper studies weak-to-strong generalization in random-feature networks, where a finite-width teacher is trained on ground-truth labels and an infinitely wide student is trained on the teacher's predictions. The authors derive deterministic expressions for the teacher and student population errors and use a bias–variance decomposition to explain the role of early stopping. The main result shows quadratic improvement for pure spherical-harmonic targets. The paper also studies different stopping times, mixed targets, and extensions to other activation functions.

Critical strengths
  1. Clear theoretical setting.
  2. Interesting quadratic improvement result.
  3. Useful mixed-target examples.
Critical weaknesses
  1. Section 6 claims that, for α>k0\alpha>k_0 and k0≤γ<αk_0\leq\gamma<\alpha, $ \overline L_{\mathrm{ST}}(T_\gamma) \lesssim d^{k_0-\alpha}\overline L_{\mathrm{TE}}. $ I do not think this rate holds throughout the stated stopping-time window.

For example, consider α=5,k0=2,γ=4\alpha=5, k_0=2, \gamma=4, with a target having nonzero degree-one and degree-two components of comparable energy. The teacher error is of order d−3d^{-3}. At T4T_4, the degree-four contribution to the variance trace gives H(T4)≳d−2H(T_4)\gtrsim d^{-2}, so the student variance alone is at least of order d−5d^{-5}. However, Eq. (6.1) would imply a student error of order at most d−6d^{-6}.

This also seems consistent with the nonquadratic regime described in Theorem 4. In Appendix D.2, the variance is shown to be small compared with the teacher error, but that does not necessarily make it smaller than the bias or establish the particular rate in Eq. (6.1).

The weaker conclusion that polynomial improvement is possible may still hold. My concern is with the claimed quantitative rate and its interpretation in Figure 3.

  1. Claim 2 states that, for even k, σk+22σk2≲d−2\frac{\sigma_{k+2}^2}{\sigma_k^2}\lesssim d^{-2}.

However, the ReLU harmonic coefficients give (k−1d+k+1)2\left(\frac{k-1}{d+k+1}\right)^2.

For fixed k, this has the claimed order. But if k=d with even d, the ratio approaches 1/4, rather than zero.

My concern is that the proof of Theorem 2 also considers harmonic degrees growing with d, so the fixed-degree estimate cannot be applied uniformly over those ranges. This does not necessarily invalidate Theorem 2, but the high-degree tail estimates need a different justification.

Questions for authors
  1. Could you clarify how the variance term is controlled for k0≤γ<αk_0\leq\gamma<\alpha? In particular, how does the claimed bound apply when (α,k0,γ)=(5,2,4)(\alpha,k_0,\gamma)=(5,2,4)? Would a stopping-time-dependent rate be more appropriate?

  2. Is the eigenvalue-ratio bound intended only for fixed harmonic degrees? If so, how are the contributions from degrees growing with d controlled in the proof of Theorem 2?

  3. What additional assumptions or concentration estimates would be required to obtain relative deterministic-equivalent accuracy at the quadratic student-error scale? Could the authors further clarify which conclusions are established for the original random-feature model?

3 comments

Thank you for the careful feedback.

  1. Section 6 claims that, for α>k0\alpha >k_0 and k0≤γ<αk_0\le \gamma <\alpha, LˉST(Tγ)≲dk0−αLˉTE.\bar L_{\mathrm{ST}}(T_{\gamma })\lesssim d^{k_0-\alpha }\bar L_{\mathrm{TE}}. I do not think this rate holds throughout the stated stopping-time window. […] The weaker conclusion that polynomial improvement is possible may still hold. My concern is with the claimed quantitative rate and its interpretation in Figure 3.

You are right. The variance term dominates when γ>(α+k0)/2\gamma>(\alpha+k_0)/2, and we wrongly dropped it. The corrected rate (see the revisions we made in the paper updated draft) depends on the stopping time, as you suggest: LST(Tγ)≲(dk0−α+d2γ−2αlog⁡2d) LTE.L_{\rm ST}(T_\gamma)\lesssim\big(d^{k_0-\alpha}+d^{2\gamma-2\alpha}\log^2 d\big)\ L_{\rm TE}. As you anticipated, polynomial improvement holds throughout the window. The corrected text of Section 6 is in our response to UhSz, and Fig. 3 and App. D.2.1 are corrected accordingly.

  1. Claim 2 states that, for even k, σk+22σk2≲d−2\frac{\sigma_{k+2}^2}{\sigma_k^2}\lesssim d^{-2}. However, the ReLU harmonic coefficients give (k−1d+k+1)2{(\frac{k-1}{d+k+1})}^2. […] the high-degree tail estimates need a different justification.

Thank you. The ratio ((k−1)/(d+k+1))2\big((k-1)/(d+k+1)\big)^2 is exact; our proof dropped a factor (k−1)2(k-1)^2. We restated Claim 2 with the exact ratio. It is ≲d−2\lesssim d^{-2} for fixed kk, and <1<1 for all kk, so the sequence is decreasing.

The proof of Theorem 2 used the claim for growing degrees only in the tail terms (iii) and (iv). We now split these at k=log⁡dk=\log d instead of k=dk=d:

  • Degrees k0<k≤log⁡dk_0<k\le\log d. The exact ratio is at most (log⁡d/d)2(\log d/d)^2 per step, so σk2/σk02≲(log⁡d/d)k−k0\sigma_k^2/\sigma_{k_0}^2\lesssim(\log d/d)^{k-k_0}. The original computation then goes through with extra powers of log⁡d\log d, which do not matter.
  • Degrees k>log⁡dk>\log d. By monotonicity, σk2≤σk∗2\sigma_k^2\le\sigma_{k_\ast}^2, where k∗k_\ast is the largest degree ≤log⁡d\le\log d. By Parseval, ∑kNkσk2=tr⁡Ψ=1/(2d)\sum_kN_k\sigma_k^2=\operatorname{tr}\Psi=1/(2d). The term is therefore at most d2α+2(σk∗2T)2tr⁡Ψ=d−Ω(log⁡d)d^{2\alpha+2}(\sigma_{k_\ast}^2T)^2\operatorname{tr}\Psi=d^{-\Omega(\log d)}.

The same repair applies to the corresponding terms in Theorem 4. The conclusions of Theorems 2 and 4 are unchanged.

  1. Could you clarify how the variance term is controlled for k0≤γ<αk_0\le \gamma <\alpha? In particular, how does the claimed bound apply when (α,k0,γ)=(5,2,4)(\alpha ,k_0,\gamma )=(5,2,4)? Would a stopping-time-dependent rate be more appropriate?

Yes, the stopping-time-dependent rate above is the correct one. The variance is V‾(Tγ)≍d2γ−2αLTE\overline V(T_\gamma)\asymp d^{2\gamma-2\alpha}L_{\rm TE}, up to a factor log⁡2d\log^2 d when a degree lies in (γ,α](\gamma,\alpha]. It comes from the degrees k∈(γ,α]k\in(\gamma,\alpha] that the student has partly learned by time TγT_\gamma, together with the degree γ\gamma itself.

At (5,2,4)(5,2,4) with your two-mode target:

  • the teacher error is ≍d−3\asymp d^{-3};
  • the bias is ≲d−3⋅d−3=d−6\lesssim d^{-3}\cdot d^{-3}=d^{-6};
  • the variance is ≍d−2⋅d−3=d−5\asymp d^{-2}\cdot d^{-3}=d^{-5}.

So LST(T4)≍d−5L_{\rm ST}(T_4)\asymp d^{-5}. This matches your lower bound and Theorem 4, and is still polynomial improvement over d−3d^{-3}.

  1. Is the eigenvalue-ratio bound intended only for fixed harmonic degrees? If so, how are the contributions from degrees growing with d controlled in the proof of Theorem 2?

Yes, the d−2d^{-2} bound is for fixed degrees. Growing degrees are controlled as described under Weakness 2: the exact ratio up to log⁡d\log d, then monotonicity and Parseval beyond.

  1. What additional assumptions or concentration estimates would be required to obtain relative deterministic-equivalent accuracy at the quadratic student-error scale? Could the authors further clarify which conclusions are established for the original random-feature model?

What is established for the original model. For the random model itself, the only established statement is Medvedev et al.'s lower bound (their Thm 4.3), which applies to our setting. All our other results are theorems about the DE. They transfer to the random model under Assumption 1, which is exactly the relative accuracy you describe, for both losses at the stopping times.

What a proof would take. We do not prove Assumption 1. With population training and an infinitely wide student, the only randomness is the teacher's weights u1,…,umu_1,\dots,u_m, i.i.d. uniform on Sd−1\mathbb S^{d-1}, and both losses are functionals of the mm i.i.d. random features σ(⟨ui,⋅⟩)\sigma(\langle u_i,\cdot\rangle). We expect a proof to follow the route used for multiplicative deterministic equivalents in random-feature ridge regression (Defilippis, Loureiro & Misiakiewicz 2024; Misiakiewicz & Saeed 2024):

  1. Leave-one-out. Removing one neuron at a time turns the resolvent functionals that define the losses into an approximate fixed-point (Dyson) equation, whose error terms are fluctuations of quadratic forms in a single feature. Equivalently, in a cumulant expansion (App. B, Eq. (B.4)), the second cumulants give the Dyson equation and the higher cumulants are the error terms.
  2. Concentration. For spherical features the quadratic forms are controlled degree by degree: hypercontractivity of spherical harmonics handles the fixed low degrees, and the high-degree part concentrates near a multiple of the identity (Mei, Misiakiewicz & Montanari 2022). The log-Sobolev inequality on the sphere gives concentration of the losses around their means.
  3. Stability. Stability of the fixed-point equation for ν\nu turns the approximate equation into bounds on both losses. To reach relative error at the scale of the student error, this has to be done multiplicatively, as in the works above, rather than with additive bounds.

For the teacher, the infinite-data limit of Defilippis et al.'s bound is our teacher deterministic equivalent, so what remains there is checking their hypotheses in our polynomial scaling. The student is the new part: it is a time-dependent two-resolvent functional, and the error must be relative at the scale LTE2L_{\rm TE}^2.

Where the difficulty lies. The demanding requirement is relative accuracy at the scale of the student error, LTE2L_{\rm TE}^2. This is hardest in the variance-limited phases, where the random-matrix variance term itself must be captured to leading order. Each step is standard; the work is in carrying the error terms through the two-stage, double-resolvent structure. This is a substantial undertaking that we leave open. The paper's population simulations agree with the DE.

Thanks for your response, it addressed my concerns. I will raise my score to 3.

Reviewer_UhSzOpenReview ↗
Rating
3(+1)
Confidence
4
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper investigates weak-to-strong generalization in random feature networks, using a finite-width teacher network and an infinite-width student network, trained by gradient flow with early stopping. Using random matrix theory, it characterizes their population errors, establishing optimal quadratic improvement for pure spherical harmonic targets. It also proves that for mixed targets, incompatible time can prevent quadratic improvement.

Critical strengths

Using a deterministic-equivalent framework, the paper sharpens the results of Medvedev et al. (2025) by establishing optimal quadratic improvement for pure harmonic targets and relaxing the teacher-capacity condition from α>2k0\alpha > 2k_0 to α>k0\alpha > k_0. Its bias–variance analysis also clarifies how the improvement depends on early stopping.

Critical weaknesses

Comparison with Medvedev et al. (2025)

Since the main contribution is improving on the results of Medvedev et al. (2025), I suggest adding a side-by-side table to the main text comparing assumptions, teacher-capacity requirements, and improvement rates. Although Appendix A.1 addresses these differences, placing them in the main text would aid readers' understanding.

Inconsistency between Figure 2/Theorem 4 and Figure 3/Eq. (6.1)

I believe Eq. (6.1) is incorrect. Consider a unit pure harmonic target with k0=2k_0=2, α=5\alpha=5, and γ=4\gamma=4. Here L‾TE≍d−3\overline L_{\mathrm{TE}} \asymp d^{-3}, but the two claims give different conclusions:

\text{Figure 2/Theorem 4:}\quad &\overline L_{\mathrm{ST}}(T_4)=\widetilde\Theta(d^{-5}),\\\\ \text{Figure 3/Eq. (6.1):}\quad &\overline L_{\mathrm{ST}}(T_4)\lesssim d^{-6}. \end{aligned}$$ The potential error lies in the dominant-term comparison in Appendix D.2.1, Regime 4. The proof obtains $$\text{4)(1)}\lesssim d^{k_0-\alpha}\overline L_{\mathrm{TE}}, \qquad \text{4)(2)}\asymp d^{2\gamma-2\alpha}\overline L_{\mathrm{TE}},$$ and then concludes that 4)(1) dominates. However, when $\gamma > (\alpha+k_0)/2$, the variance term 4)(2) instead exceeds the stated upper-bound scale for 4)(1). Could the authors clarify this discrepancy and provide the corrected rate and proof? I would be willing to raise my score if this issue is satisfactorily resolved.
Questions for authors

Medvedev et al. (2025) also study linear random feature models. Could the proof techniques in this paper also apply to them?

2 comments

Thank you for the feedback.

Since the main contribution is improving on the results of Medvedev et al. (2025), I suggest adding a side-by-side table to the main text comparing assumptions, teacher-capacity requirements, and improvement rates. Although Appendix A.1 addresses these differences, placing them in the main text would aid readers' understanding.

We will add the table: regime, lower bound, attainment, ReLU rate, teacher capacity (MT≳d2kM_T\gtrsim d^{2k} vs. α>k0\alpha>k_0), stopping times and assumptions. We'll try to work it into the main text if space allows, otherwise at the top of App. A.1. See also the general response, part 2.

I believe Eq. (6.1) is incorrect. Consider a unit pure harmonic target with k0=2k_0=2, α=5\alpha =5, and γ=4\gamma =4. Here LˉTE≍d−3\bar L_{\mathrm{TE}}\asymp d^{-3}, but the two claims give different conclusions: […] The potential error lies in the dominant-term comparison in Appendix D.2.1, Regime 4. […] Could the authors clarify this discrepancy and provide the corrected rate and proof? I would be willing to raise my score if this issue is satisfactorily resolved.

Thank you for catching this; your diagnosis is exactly right. In Regime 4 we dropped the variance term 4)(2) when comparing the two terms. The corrected Section 6 statement reads (see also the revised manuscript which has these changes marked in color):

If the teacher has enough capacity to learn every mode of the target, α>k0\alpha>k_0, and the student is stopped after the target degree but before the teacher's capacity edge, k0≤γ<αk_0\le\gamma<\alpha, then LST(Tγ)≲(dk0−α+d2γ−2αlog⁡2d) LTE=o(LTE).L_{\rm ST}(T_\gamma)\lesssim\big(d^{k_0-\alpha}+d^{2\gamma-2\alpha}\log^2 d\big)\ L_{\rm TE}=o(L_{\rm TE}). This is weak-to-strong generalization for every mixed target, whatever its coefficients. The two terms are the squared bias and the variance. The bias is at most dk0−αLTEd^{k_0-\alpha}L_{\rm TE}. The variance, the part of the teacher's error that the student has already imitated by time TγT_\gamma, is of order d2γ−2αLTEd^{2\gamma-2\alpha}L_{\rm TE} up to the logarithmic factor. The first term dominates for γ≤(α+k0)/2\gamma\le(\alpha+k_0)/2 and the second for γ>(α+k0)/2\gamma>(\alpha+k_0)/2. The bound is sharp: a pure harmonic of degree k0k_0 attains it, since by Theorem 4 its student error at these stops is LTE2L_{\rm TE}^2 in the quadratic phase and Θ~(LTEρ)=Θ~(d2γ−2αLTE)\tilde\Theta(L_{\rm TE}^{\rho})=\tilde\Theta(d^{2\gamma-2\alpha}L_{\rm TE}) in the nonquadratic phase. Any stop in the window [k0,α)[k_0,\alpha) gives polynomial improvement, and the stops with γ≤(α+k0)/2\gamma\le(\alpha+k_0)/2 give the largest factor, dk0−αd^{k_0-\alpha}.

What this changes:

  • Your example. At (5,2,4)(5,2,4) the bound gives d−5d^{-5}, matching Fig. 2 and Theorem 4.
  • The rest of the paper. We made the same correction in the legend of Fig. 3 and in App. D.2.1 (Regime 4 and its summary table).
  • The conclusions of Section 6 are unchanged:
    • every stop in [k0,α)[k_0,\alpha) gives polynomial weak-to-strong generalization for every target when α>k0\alpha>k_0;
    • stopping at γ≥α\gamma\ge\alpha gives none;
    • the two mixed-target obstructions stand as stated.

Medvedev et al. (2025) also study linear random feature models. Could the proof techniques in this paper also apply to them?

Yes. An earlier version of this work carried out the DE analysis in their linear setting (spiked covariance, linear target) and found quadratic improvement for the DE. That is weaker than their Thm 3.2, which holds for the random model unconditionally. Gaussian features remove the need for a universality assumption, but transferring the DE result to the random model would still require the double-resolvent DE with relative error at the scale LTE2L_{\rm TE}^2, which we have not proved.

Thank the authors for their response and revision. It successfully addressed my concerns, especially as the technical flaws were corrected, so I will raise my score and lean toward acceptance of this paper.

Reviewer_cfzZOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

The paper studies the phenomenon known as "weak-to-strong" generalization. Namely, there is a ground-truth function f∗f_* that relates input xx to label y=f∗(x)y=f_*(x). A teacher model is trained to reproduce the ground-truth function; on the other hand, a student model has no access at training time to the ground-truth, but only to the labels generated by the teacher. Weak-to-strong generalization refers to the phenomenon where the student's performance on the test set surpasses the teacher's. The authors characterize this using a Random-Features model for both teacher and student, while considering a standard decomposition of the ground truth in an orthonormal basis. They prove, using a deterministic equivalent approach, a quadratic improvement if the student is trained with early-stopped gradient descent. The authors also present supporting numerical simulations.

Critical strengths

The critical strength of this paper is the clarity of exposition. The reader understands that there is a clear scientific problem to study (weak-to-strong generalization) and the authors do a great job in: describing the related works; building a theoretical framework that addresses the main points of this phenomenon; presenting the theoretical results associated to this modelization with rigorous results and numerical experiments. On top of the main text being correctly written, also the appendix does a good job in presenting the proofs and derivations for non-expert readers. The phase diagram is neat and the figures properly illustrated.

Critical weaknesses

I do not identify a critical weakness for this paper. However, I want to mention that, as a reader, I would have appreciated some general discussion on why most of the assumptions are necessary. If they are needed only for some technical details in the proof scheme, I would have liked explanations of whether the authors believe the phenomena to be more general and valid in diverse settings. I will make this point precise in the following section.

Another (less critical) weakness is the lack of proper coverage to the Gaussian Universality results present in the literature for Random Features model in the main text. The ReLU gradient descent attaining the lower bound, namely the central result of the paper, depends clearly on them, but they are not cited thoroughly. Similarly, the approach of decomposing ground truth functions on an orthonormal basis and characterizing the hardness of a given function according to its decomposition is central in the line of work referring to the "Information exponents" (e.g. see [1,2] among many others) that are never considered in the submission.

  • [1] Gerard Ben Arous, Reza Gheissari, and Aukosh Jagannath. Online stochastic gradient descent on non-convex losses from high-dimensional inference. Journal of Machine Learning Research, 22(106):1–51, 2021.
  • [2] Emmanuel Abbe, Enric Boix-Adsera, and Theodor Misiakiewicz. The merged-staircase property: a necessary and nearly sufficient condition for sgd learning of sparse functions on two-layer neural networks. In Conference on Learning Theory, pages 4782–4887. PMLR, 2022.
Questions for authors

I will expand here on the thoughts of the weakness section. In the age of AI-assisted research, I would have liked more ambitious attempts to overcome the technical details in the proofs, explaining to the reader why this was left for future work and not addressed in the submission. I would have appreciated some comments in the main text on the following: a) why quadratic improvement and not other factors? I could follow the math, but the fact that the ReLU gradient flow attains the lower bound is telling something fundamental about the quadratic exponent; b) could the author comment on the finite-sample (nn) regime? We know the universality results extend to a general setting where the relevant parameter becomes P=min(m,n)P = min(m,n), which governs the universality properties of kernel methods/Random features; c) similar point on finite nn for Gradient Flow on population loss: this is a very idealized setting, and the authors could comment on the difficulties of going to minimizing empirical risk

Minor points:

  • Page 3: MST→∞M_{ST} \to \infty, be precise with respect to what, many things are diverging;
  • Page 4: notation of eq. 3.1 is confusing with mm
  • I would suggest including the nice phase diagram in one of the first pages of the manuscript to give a visual understanidng of the results early on to the readers
3 comments

I do not identify a critical weakness for this paper. However, I want to mention that, as a reader, I would have appreciated some general discussion on why most of the assumptions are necessary. If they are needed only for some technical details in the proof scheme, I would have liked explanations of whether the authors believe the phenomena to be more general and valid in diverse settings.

Thank you. We answer this together with your questions (a)–(c) in the next comment.

Another (less critical) weakness is the lack of proper coverage to the Gaussian Universality results present in the literature for Random Features model in the main text. The ReLU gradient descent attaining the lower bound, namely the central result of the paper, depends clearly on them, but they are not cited thoroughly.

We will expand the literature coverage in the main text, if accepted (we'll have to balance this against extended discussion about Medvedev et al, which was also requested). These works are discussed in App. B. We will cite them in the main text next to Assumption 1 (Hu & Lu; Montanari & Saeed; Goldt et al.; Mei, Misiakiewicz & Montanari; and the deterministic-equivalent works already cited in the introduction).

Similarly, the approach of decomposing ground truth functions on an orthonormal basis and characterizing the hardness of a given function according to its decomposition is central in the line of work referring to the "Information exponents" (e.g. see [1,2] among many others) that are never considered in the submission.

We will cite these works. The closest relative of our setting is the kernel and random-feature learning theory, in which a degree-kk spherical harmonic needs about dkd^k features and, here, a gradient-flow time of about dk+1d^{k+1}. The information-exponent and staircase literature studies the related question for feature-learning dynamics. We will add a sentence making this connection.

Minor points:

  • Page 3: MST→∞M_{ST}\to \infty, be precise with respect to what, many things are diverging;
  • Page 4: notation of eq. 3.1 is confusing with mm
  • I would suggest including the nice phase diagram in one of the first pages of the manuscript to give a visual understanidng of the results early on to the readers
  • MST→∞M_{\rm ST}\to\infty is taken first, at fixed teacher width and dd: the student is infinitely wide and is trained by the limiting spectral flow. We will say so. Quantifying finite student widths is an interesting further capacity question.
  • In Eq. (3.1), mm denotes a generic width, and later the teacher width is MTE=mM_{\rm TE}=m. We will use a separate symbol for the generic width.
  • We'll consider moving the diagram.

I will expand here on the thoughts of the weakness section. In the age of AI-assisted research, I would have liked more ambitious attempts to overcome the technical details in the proofs, explaining to the reader why this was left for future work and not addressed in the submission. I would have appreciated some comments in the main text on the following: a) why quadratic improvement and not other factors? […] b) could the author comment on the finite-sample (nn) regime? […] c) similar point on finite nn for Gradient Flow on population loss: this is a very idealized setting, and the authors could comment on the difficulties of going to minimizing empirical risk

Thank you for these questions.

Regarding the comment about AI-assisted research: based on recent experience auto-proving/formalizing related results, we would expect AI systems are capable of completely discharging the GUA/deterministic equivalent asumption and giving a lean-formalized end-to-end theorem with minimial input from the authors. We may look at adding this as a type of supplementary material. However, supposing this is true, it seems to us most of the machine-learning theory value is contained in understanding the phase diagram of the deterministic equivalent, whose proof complexity cost is orders of magnitude lower.

Regarding the other points, here is a short discussion along these lines; a condensed version can go into the revision, with the details in the appendix.

Why the exponent is 2. For a unit pure-harmonic target, the deterministic equivalent gives the teacher error exactly as LTE=sL_{\rm TE}=s, where s=ν/(σk02+ν)s=\nu/(\sigma_{k_0}^2+\nu) is the factor by which the teacher shrinks the target. This error has two parts: a systematic shrinkage of the target, of size s2s^2 (the squared bias), and a remainder s−s2s-s^2 spread over the many directions the teacher can represent. A student stopped at the target's time scale imitates the systematic part but not the spread part, so LST≈s2=LTE2L_{\rm ST}\approx s^2=L_{\rm TE}^2. The exponent 2 is the ratio of the orders of these two parts, and Theorem 1 shows that the squared bias cannot be removed. Nothing in this argument is specific to ReLU, which is why Theorem 3 gives the same rate for every non-polynomial activation.

The role of the assumptions.

  • Uniform data and weights on the sphere make the spectrum explicit.
  • The infinitely wide student and population training isolate the teacher's finite width as the only obstruction to optimal student learning
  • Assumption 1 is needed to transfer statements about the deterministic equivalent to the random model.

Proving Assumption 1 requires deterministic equivalents with relative error at the scale LTE2L_{\rm TE}^2 of the student error. There is a previously successful route: leave-one-out over the teacher's neurons, concentration of quadratic forms in the features (via hypercontractivity of spherical harmonics and the log-Sobolev inequality on the sphere), and multiplicative stability of the fixed-point equation. There is precedent for error bounds of this type (Defilippis, Loureiro & Misiakiewicz '24; Misiakiewicz & Saeed '24; Cheng & Montanari '22), and for the teacher, the infinite-data limit of Defilippis et al. is our teacher deterministic equivalent. The new difficulty is the student: carrying sharp error terms through the two-stage, double-resolvent structure is a long technical project, which we leave to future work.

Finite samples and empirical risk. With nn samples, the teacher's capacity is governed by min⁡(m,n)\min(m,n) (Mei, Misiakiewicz & Montanari, 2022), away from the interpolation threshold m≈nm\approx n. A finite sample acts on the teacher as an additional effective ridge. Since the mechanism above uses only that the teacher's error splits into a shrinkage plus a spread part, we expect the same picture with mm replaced by min⁡(m,n)\min(m,n). Verifying this, and the analogous statement for a student trained on finitely many teacher-labelled samples, requires deterministic equivalents with additional resolvents for the empirical covariances. With finite nn, the student's error becomes a functional of three random matrices: the teacher's features, the student's features and the data.

Thank you for addressing my concerns. I believe this is an interesting submission, and I maintain my score (just one level below the maximum grade).

Reviewer_nFL7OpenReview ↗
Rating
4(+1)
Confidence
4
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

The paper considers Weak-to-Strong setting in 2-layer Random Feature networks as in Medvedev et al, where the teacher is optimally and the student is early stopped. The main contributions are (i) analyzing this setting from the deterministic equivalents perspective in ReLU networks, which allows you to analyze exact closed forms of test losses for student and teacher and hence W2S under a standard Gaussian Universality assumption, and showing that under these conditions the lower bound established in Medvedev et al can be achieved in the ReLU case as well (and not just linear case which was known so far). They validate that predictions of deterministic equivalent actually hold in practice with experiments. The claimed contribution for the lower bound is a bit unclear to me because Medvedev et al prove a quite general lower bound.

Critical strengths

The main strength of this paper, how I see it, is actually carrying the calculations of what happens when you approach the W2S Random Feature settings from the point of view of deterministic equivalents. This calculations allows for the analysis of W2S to carry through with more general stopping times, and also allows for a more fine grained analysis of W2S improvement for ReLU case, which is hard to do directly due nontrivial spectrum of the appropraite kernel eigenbasis. This shows that the quadratic lower bound can also be achieved with ReLU networks, which was one of the questions left open in Medvedev et al 2025. Further, it is slightly surprising since the indications there were that the exponent might be a bit lower, which shows that this result is also suprising (however the paper misses this point). Finally, the general analysis of stopping times points to clear separation of different regimes of early/late/optimal stopping, which is a nice result and more quantiatively explains the main mechanism of W2S in this setting.

Critical weaknesses

The paper slightly misplace their contribution compared to that of Medvedev et al 2025. This does not take away that there is a contribution, but leaves the reader slightly confused as to what is actually (i) known but proved here under GUA (ii) expected but confirmed/proved (iii) unexpected about the results of this paper. First of all, the paper phrases one of their contributions as achieving the quadratic lower bound on the improvement of student to teacher. However, Medvedev et al 2025 already shows that the lower bound can be achieved for the linear network settings, so the real novelty is showing that it can be achieved the ReLU setting as well. Medvedev et al also proved LS<=O(LT1.5)L_S <= O(L_T^{1.5}) for a certain setting with ReLU network, and they show empirically in fixed dd setting that we can achieve LS=Theta(LTT1.8)L_S = Theta(L_TT^{1.8}). So, I feel like the results should be discussed in the context of these already existing ReLU bounds - how is the current setting different, and why do we get sharper degree bounds on LTL_T.

Second, the lower bound in Medvedev et al 2025 applies more broadly than indicated in line 237-239, namely the Medvedev et al's lower bound applies for any shrinkage optimal teacher and student. So, this warrants a discussion of whether the setting considered here does not fit those conditions and if it does whether the bound present here is better than the already existing one.

Finally, the paper presents the current bounds as strictly more general than what is present in Medvedev et al, however, if I understand coirrectly, the bounds in this trade off having exact end-to-end mathematical proofs for a reslt that is conditional on the deterministic equivalents actually modelling the real settings.

Overall, I think the result could definitely greatly benefit from more close discussion of Medvedev et al, since the results seem to be (i) surprising given empirical results on ReLU networks present there and (ii) complementary, showing lower bound can be achieved for ReLU networks as well.

Questions for authors
  1. For Theorem 1, and in lines 237-239, you claim that Theorem 1 is "deterministic-equivalent counterpart of the lower bound of Medvedev et al. (2025), who prove the analogous result for the random student error." However, the lower bounds in Medvedev et al 2025 are much more general than "random student error." In particular, their Theorem 4.3 and Theorem 4.5 show the lower bounds apply for any "shrinkage optimal" teacher and student and only as a corollary do they get the random student lower bounds. So, is it the case that your setting does not fall under the shrinkage optimal regime? Medvedev et al 2025 goes on saying "First of all, they hold with any student and teacher feature space—these need not be random."
  2. If we were to want to carry out the full proof of deterministic equivalents without GUA, are there any "easy" regimes and any "hard regimes", i.e. when does deterministic equivalent actually help (e.g. in terms of stopping times)? If I understand correctly, Medvedev et al analyze only regime of stopping times while you identify 4 types of stopping times (which one does their correspond to)?
3 comments

The paper slightly misplace their contribution compared to that of Medvedev et al 2025. This does not take away that there is a contribution, but leaves the reader slightly confused as to what is actually (i) known but proved here under GUA (ii) expected but confirmed/proved (iii) unexpected about the results of this paper.

Thank you. We will add the comparison in part 2 of the general response to the paper. In your terms:

  • (i) Known, re-derived for the DE: the quadratic lower bound (Theorem 1).
  • (ii) Expected, now established for the DE: quadratic improvement for ReLU (Theorem 2). Medvedev et al. expect their LT1.49L_T^{1.49} bound to be loose. The numerics suggest it tends to quadratic (and that LT≈1.8L_T^{\approx 1.8} was not where the generalization error was settling.)
  • (iii) Not in Medvedev et al.:
    • the threshold α>k0\alpha>k_0, compared with their MT≳d2kM_T\gtrsim d^{2k};
    • the extension to all non-polynomial activations;
    • the stopping-time phases, including the nonquadratic phase;
    • the mixed-target guarantee and its two obstructions.

First of all, the paper phrases one of their contributions as achieving the quadratic lower bound on the improvement of student to teacher. However, Medvedev et al 2025 already shows that the lower bound can be achieved for the linear network settings, so the real novelty is showing that it can be achieved the ReLU setting as well.

This is a fair point. Medvedev et al. (Thm 3.2) attain the quadratic rate for linear random-feature networks. We will say so, and state our contribution as attaining it for ReLU and other non-polynomial activations.

Medvedev et al also proved LS<=O(LT1.5)L_S<=O(L_T^{1.5}) for a certain setting with ReLU network, and they show empirically in fixed dd setting that we can achieve LS=Theta(LTT1.8)L_S=Theta(L_TT^{1.8}). So, I feel like the results should be discussed in the context of these already existing ReLU bounds - how is the current setting different, and why do we get sharper degree bounds on LTL_T.

Medvedev et al. prove polynomial improvement for ReLU unconditionally, and O~(LT1.49)\tilde O(L_T^{1.49}) under Gaussian universality. That is an upper bound, and they note it is likely loose. The empirical exponent of about 1.8 is a fit over a finite range (LTL_T up to 0.80.8, MT≤256M_T\le256), not the asymptotic rate. In their own fixed-dd regime the DE gives LS/LT2→1L_S/L_T^2\to1 as MT→∞M_T\to\infty, so the exponent tends to 2; their App. I also says LS=Θ~(LT2)L_S=\tilde\Theta(L_T^2) is plausible there. Our sharper exponent comes from computing the student error exactly at the DE level, rather than bounding the teacher–student feature misalignment. We will include this in the comparison (general response, part 2).

Finally, the paper presents the current bounds as strictly more general than what is present in Medvedev et al, however, if I understand coirrectly, the bounds in this trade off having exact end-to-end mathematical proofs for a reslt that is conditional on the deterministic equivalents actually modelling the real settings.

You understand correctly. We don't prove an end-to-end theorem, as do Medvedev et al. And for the tradeoff that, we can make sharper statements about the rates and more general statements about the domain of applicability.

We'd like to gently push back on the statement that we 'present the current bounds as strictly more general.' We write repeatedly in the paper that the results rest on deterministic equivalent/GUA (the abstract, the contributions, the conclusions/limitations, and around the discussion of Assumption 1).

But we really do want this to be clear, and we welcome specific feedback regarding this point.

Second, the lower bound in Medvedev et al 2025 applies more broadly than indicated in line 237-239, namely the Medvedev et al's lower bound applies for any shrinkage optimal teacher and student. So, this warrants a discussion of whether the setting considered here does not fit those conditions and if it does whether the bound present here is better than the already existing one.

  1. For Theorem 1, and in lines 237-239, you claim that Theorem 1 is "deterministic-equivalent counterpart of the lower bound of Medvedev et al. (2025) […]". However, the lower bounds in Medvedev et al 2025 are much more general than "random student error." […] So, is it the case that your setting does not fall under the shrinkage optimal regime?

We answer this weakness and Question 1 together. Our setting is shrinkage-optimal, so their Theorem 4.3 applies directly to our random model, and our Theorem 1 is not a stronger bound: it has the same leading constant and holds only for the DE. We do not intend it to replace their theorem.

We include it because the paper is about understanding the DE. Once the two-term formula is written down, the lower bound takes one line: drop the variance, then apply Cauchy–Schwarz to the squared bias. That identifies the floor LTE2L_{\rm TE}^2 as the teacher's squared bias, which organizes the rest of the analysis.

We will correct how we discuss their Theorem 4.3.

  1. If we were to want to carry out the full proof of deterministic equivalents without GUA, are there any "easy" regimes and any "hard regimes", i.e. when does deterministic equivalent actually help (e.g. in terms of stopping times)? If I understand correctly, Medvedev et al analyze only regime of stopping times while you identify 4 types of stopping times (which one does their correspond to)?

We have not investigated this in detail. Our expectation is that the variance-limited regimes are the hard ones: the nonquadratic phase and late stopping. There a proof must pin down the random-matrix variance term to relative accuracy, which is a second-moment universality statement. The bias-limited quadratic phase should be easier. A full proof in this setting looks feasible but long; we sketch the steps in our response to smqC (Q3).

Their stopping time, T=σk−2log⁡(1/δT)T=\sigma_k^{-2}\log(1/\delta_T), is the target's own time scale. That is γ=k0\gamma=k_0 in our Theorem 4, the left end of the quadratic window.

Overall, I think the result could definitely greatly benefit from more close discussion of Medvedev et al, since the results seem to be (i) surprising given empirical results on ReLU networks present there and (ii) complementary, showing lower bound can be achieved for ReLU networks as well.

We'll look to improve our discussion of Medvedev's result (see the attached overview). Regarding 'surprise' -- we don't want to speak for Medvedev et al here -- we would say that most important outcomes of having done this analysis are:

  1. the degree of the harmonic target affects the range of stopping times that work (expected, although the quantiative dependence is not obvious),
  2. but nonetheless, there is a robust regime of polynomial WTS generalization if the teacher is actually strong enough to learn the target (α>k0\alpha > k_0), which works for generic targets (not obviously expected -- naively I would expect incompatible stopping conditions to make it impossible, but that's not how the math works out)

Thank you for answering my questions. I will raise my score to 4. However, I hope the suggested modifications do make it back into the paper.

Finally, I still consider the result for ReLU "surprising" given the empirical results in Medvedev et al. It might be interesting to understand what about increasing dd enables exact quadratic improvement (because my intuition was that in fixed dd the spectrum of ReLU just doesn't allow for quadratic improvement).

Comments on the paper

2 comments

We thank the reviewers for their careful reading. Two reviewers (UhSz, smqC) found an error in Eq. (6.1), and smqC found a gap in Claim 2. Both are fixed in the revision, and neither changes the main results (Theorems 1–4). Several reviewers asked for a sharper comparison with Medvedev et al. (2025). We give it in part 2 of this response and will add it to the paper, in the main text if space allows, together with a comparison table.

We have uploaded a revised PDF, which contains fixes to the mistakes marked in color. (Lines removed in strikeout red, lines added in blue). [Aside: We have not added other requested changes at this time, but we would do this as part of using the extra allowed page which would be granted if this paper were accepted. We have discussed possible changes in our responses.]

1. Eq. (6.1) (UhSz, smqC). The reviewers are right. In Regime 4 of App. D.2.1 we showed that the squared bias is ≲dk0−αLTE\lesssim d^{k_0-\alpha}L_{\rm TE} and the variance is ≍d2γ−2αLTE\asymp d^{2\gamma-2\alpha}L_{\rm TE}. We then wrongly concluded that the bias dominates; in fact the variance dominates when γ>(α+k0)/2\gamma>(\alpha+k_0)/2. The corrected bound, for α>k0\alpha>k_0 and k0≤γ<αk_0\le\gamma<\alpha, is LST(Tγ)≲(dk0−α+d2γ−2αlog⁡2d) LTE=o(LTE).L_{\rm ST}(T_\gamma)\lesssim\big(d^{k_0-\alpha}+d^{2\gamma-2\alpha}\log^2 d\big)\,L_{\rm TE}=o(L_{\rm TE}). This still gives weak-to-strong generalization for every mixed target in that window, and it is sharp: a pure harmonic attains it. At (α,k0,γ)=(5,2,4)(\alpha,k_0,\gamma)=(5,2,4) it gives d−5d^{-5}, in agreement with Fig. 2 and Theorem 4. We have corrected Eq. (6.1), the text around it, the legend of Fig. 3 and App. D.2.1.

2. Claim 2 (smqC). The exact ratio is σk+22/σk2=((k−1)/(d+k+1))2\sigma_{k+2}^2/\sigma_k^2=\big((k-1)/(d+k+1)\big)^2 for even k≥2k\ge2. So the bound d−2d^{-2} holds for fixed kk only; the proof had dropped a factor (k−1)2(k-1)^2. The sequence is still decreasing in kk. We restated the claim with the exact ratio and repaired the places where it was applied to degrees that grow with dd. The conclusions are unchanged; the repair is described in our response to smqC.

AuthorsOpenReview ↗

Extended comparison width Medvedev

(This comment should follow the comment below! Ooops!)

3. Comparison with Medvedev et al. (2025).

Medvedev et al. introduced the random-feature weak-to-strong setup that we study, and their results are theorems about the random model itself. Three of them are directly relevant here.

  • A quadratic lower bound, LS≥LT2(1−LT+O(LT2))L_S\ge L_T^2(1-L_T+O(L_T^2)), for any shrinkage-optimal teacher and student in any feature spaces, with no distributional assumption (their Thm 4.3). It applies to our model.
  • That this rate is attained by linear random-feature networks with a spiked covariance (Thm 3.2).
  • That ReLU random features give polynomial improvement: LS≲(log⁡2MT/MT) LTL_S\lesssim(\log^2M_T/\sqrt{M_T})\,L_T once MT≳d2kM_T\gtrsim d^{2k}, which is O~(LT1.49)\tilde O(L_T^{1.49}) under Gaussian universality (Thm 3.1).

They say they expect the ReLU bound to be loose, and their experiments give fitted exponents above it.

Our analysis is carried out on the deterministic equivalent (DE) of the same model, and gives three results that are not in their work.

  • ReLU attains the quadratic rate. For a pure harmonic target of degree k0k_0, LST≍LTE2L_{\rm ST}\asymp L_{\rm TE}^2 for every α>k0\alpha>k_0, that is, as soon as the teacher error vanishes. Their bound needs MT≳d2kM_T\gtrsim d^{2k}. The same holds for every non-polynomial activation (Theorem 3).
    • The exponent is 2 in their fixed-dd regime too: there the DE gives LS/LT2→1L_S/L_T^2\to1 as MT→∞M_T\to\infty.
    • Their fitted exponents (1.55, 1.85 and 1.90 at d=16,32,64d=16,32,64) are fitted with MT≤256M_T\le256.
  • Robust, but only within a window of stopping times. Theorem 4 gives quadratic improvement for every stopping degree k0≤γ≤(α+k0)/2k_0\le\gamma\le(\alpha+k_0)/2. Training longer, the student starts to copy the teacher's error: the exponent decreases continuously from 2 to 1, and improvement is lost at γ≥α\gamma\ge\alpha. Their stopping time corresponds to γ=k0\gamma=k_0.
  • Mixed targets: dispersion of time scales. Different degrees are learned on different time scales. If the teacher can learn every mode (α>k0\alpha>k_0), every stop in [k0,α)[k_0,\alpha) gives polynomial improvement. However, the best stop can still be strictly nonquadratic (LST≍LTE5/3L_{\rm ST}\asymp L_{\rm TE}^{5/3} in a two-mode example). If a small mode lies above the teacher's capacity, only a constant-factor improvement is possible even though LTE→0L_{\rm TE}\to0.

Rigor and our Theorem 1. Medvedev et al. prove their results for the random model. Ours are proved for the DE, and transfer to the random model under Assumption 1, which asks that the DE be accurate to relative precision for both losses at the stopping times. We do not prove Assumption 1. We expect it to hold, and the paper's population simulations agree with the DE; we sketch a route to a proof in our response to smqC.

Our Theorem 1 is not stronger than their Theorem 4.3: it has the same leading constant and applies only to the DE. We include it because, once the DE's two-term formula is written down, it takes one line: drop the variance and apply Cauchy–Schwarz to the squared bias. It also shows that the floor LTE2L_{\rm TE}^2 is exactly the teacher's squared bias, which is the quantity the stopping-time analysis has to reach. So we feel it's conceptually important to keep it, even though it is essentially a weaker version of Medvedev's Theorem 4.3.

We can adjust the language of how we discuss it at this point in the text. A fuller discussion could go in hand with a deeper comparison to Medvedev's results.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.