Weak-to-Strong Generalization Even in Random Feature Networks, Provably
Authors: Marko Medvedev
Kaifeng Lyu
Dingli Yu
Sanjeev Arora
Zhiyuan Li
Nathan Srebro
Venue: ICML 2025 poster (2025)
Keywords: weak-to-strong
generalization
random features
student-teacher
2-layer NN
2-layer networks
Primary area: theory->learning_theory

Abstract: Weak-to-Strong Generalization (Burns et al.,2024) is the phenomenon whereby a strong student, say GPT-4, learns a task from a weak teacher, say GPT-2, and ends up significantly outperforming the teacher. We show that this phenomenon does not require a complex and pretrained learner like GPT-4, can arise even in simple non-pretrained models, simply due to the size advantage of the student. But, we also show that there are inherint limits to the extent of such weak to strong generalization. We consider students and teachers that are random feature models, described by two-layer networks with a random and fixed bottom layer and trained top layer. A ‘weak’ teacher, with a small number of units (i.e. random features), is trained on the population, and a ‘strong’ student, with a much larger number of units (i.e. random features), is trained only on labels generated by the weak teacher. We demonstrate, prove, and understand how the student can outperform the teacher, even though trained only on data labeled by the teacher. We also explain how such weak-to-strong generalization is enabled by early stopping. We then show the quantitative limits of weak-to-strong generalization in this model, and in fact in a much broader class of models, for arbitrary teacher and student feature spaces and a broad class of learning rules, including when the student features are pre-trained or otherwise more informative. In particular, we show that in such models the student’s
error can only approach zero if the teacher’s error approaches zero, and a strong student cannot “boost” a slightly-better-then-chance teacher to obtain a small error.

Weak-to-Strong Generalization Even in Random Feature Networks, Provably
Marko Medvedev
Kaifeng Lyu '2 Dingli Yu
Sanjeev Arora Zhiyuan Li Nathan Srebro
Abstract
1. Introduction
Weak-to-Strong -trton Generalization (Burns et al., 2024) is the phenomenon whereby a strong stu- dent, say GPT-4, learns task from weak teacher, say GPT-2, and ends up significantly outperforming the teacher. We show that this phenomenon does not require complex and pre- trained learner like GPT-4, can arise even in sim- ple hon-pretra models, simply due to the size advantage of the student. But, we also show that there are inherint limits to the extent of such weak to strong generalization. We consider students and teachers that are random feature models, de- scribed by two-layer networks with a random and fixed bottom layer and trained top layer. A 'weak' teacher, with a small number of units (i.e. ran- dom features), is trained on the population, and a 'strong" student, with much larger number of units (i.e. random features), is trained only labels generated by the weak teacher. We demonstrate, prove, and understand how the stu- dent can outperform the teacher, even though trained only on data labeled by the teacher. We also explain how such weak-to teak-to--ttoog generaliza- tion is enabled by early stopping. We then show the quantitative limits of weak-to-strong gener- alization in this model, and in fact in much broader class of models, for arbitrary teacher and student feature spaces and broad class of learn- ing rules, including when the student features are pre-trained or otherwise more informative. In par- ticular, we show that in such models the student's error can only approach zero if the teacher's 's er- ror approaches zero, and strong student cannot "boost" betphlly--bbtter--e--hhheee obtain small error.
(Samuel, 1959), in the first ever paper introducing the term "machine learning", emphasized how his learned system outperformed its human teacher. More broadly, the idea of good student outperforming their teacher is much older, as epitomized by the quote "Pvor is the pupil who does not surpass his master", widely attributed to Leonardo de Vinci." Recently, Burns et al. (2024) discussed the con- cept in the context of "superalignmenn"" (weak humans con- trolling strong machines), and suggested studying (strong) student machines outperforming their (weaker) machine teachers a surrogate model. Burns et al. demonstrated the phenomenon by fine-tuning a "weak" teacher model, namely pre-trained GPT-2, on task-specific data with true labels, and then using this "weak" teacher model to annotate data for the same task, and fine-tuning a "strong" student model, namely a pre-trained GPT-4, only using labels generated by the "weak" teacher (see Figure 1). In these experiments, the "strong" students indeed outperformed their "weak" teach- ers, and Burns et al. asked for understanding of this weak-to to-sonn generalization phenomenon.
There are several mechanisms by which a student can out- perform their teacher. A student can do a more thorough test-time search, e.g. looking ahead more moves or thinking of more ways solve a problem. Taking step further, on problems where such search can be helpful, student can also learn to internalize the search, learning better value function or next-action (or token) predictor through self-play or training-time search (as in Samuel's checker learner, and modern RL-based training methods for LLMs) A student might also be able to correct a teacher by having better induc- tive bias, perhaps obtained through pre-training on similar related tasks. For example, Chinese-speaking student can outperform their non-Chinese-speakin teacher when being taught to pronounce names of Chinese colleagues.
teacher to
'Department of Mathematics, Univer- sity of Chicago, Chicago, IL. US "Simons Institute, University of California, Berkeley, San Francisco, CA, US "Microsoft Re- search, Seattle, WA, US *Princeton University, Princeton, NJ, US 'TTIC, Chicago, IL, US. Correspondence to: Marko Medvedev <medvedev uchicago.cdu>..
"Equal contribution
But can a student outperform their teacher simply by being "bigger", having more units and a larger representation, with- out more specialized or specific inductive bias, nor more or better pre-training? Does this require sophisticated mod- els with emergent capabilities, such GPT-4 scale deep transformers, can it also arise in much simpler models?
Proceedings of the 42nd International Conference Machine Learning, Vancouver, Canada. PMLR 267, 2025. Copyright 20255 by the author(s).
"The quote does not appear in de Vinci's surviving writing and its source is unclear to us

---

Weak-to-Strong Generalization Even in Random Feature Networks, Provably
Strong student early stopping
have LsT = Ö (fire) (Theorem 3.2).
Optimally trained weak teacher
As in Burns et al. (2024), we use early stopping when train- ing the student-it is easy to see how in our setting early stopping is essential: Since the student is more expressive than the teacher, without early stopping they would just replicate the teacher's mistakes. In Section 5 we explain how such early stopping allows the weak-to-strong gener- alization described above, shedding light on its empirically observed role.
Data
Data
y f (x)
Steacher
yj J (xeacher(x)
Fanudent
Ground truth
Ground truth labals
Weak teachar prodictor
Weak teacher labels
Strong student prodictor
Figure/ 1. Illustration of our setup for weak-to-strong generaliza- tion. The teacher model of smaller size is trained on ground truth labels, while the student model of larger size is trained with early stopping on labels produced by the teacher model.
Complementing these results, we also study the limits of weak-to-strong generalization. In Section 4 we show that the quadratic gap described above is the largest possible, and in any random feature model we would always have Lst = (CCrg) In fact, this limit extends well beyond random feature models, to models with arbitrary teacher and student feature spaces (even if the student features highly specialized or pre-trained), with early stopped gradi- ent descent (starting from zero initialization) or with other convex regularizers. In particular, this limit implies that in such settings, we can have vanishing student error LsT + O only when the teacher error also vanishes Ltx - 0, and that if the teacher error is only slightly better than null, the student error will also be close to null- we cannot "boost" teacher with tiny edge to near- pear-perfect student.
If the model sizes are further scaled up, will weak-to-strong generalization be enhanced or diminished?
In the first part of this paper, we analyze and prove how weak-to-strong generalization (i.e. student outperform- ing their student) can happen even in models simple as "random feature models", i.c., two-layer networks with a random bottom layer and only the top layer trained. More specifically, we study the setup where the teacher and stu- dent models are two-layer networks with MTE and MST (hidden, random) units, respectively. The student model is significantly stronger than the teacher, in the sense that it has many more units than the teacher, MgT >> MrE. In both models, we sample the bottom layer weights from the same spherical distribution, and then train only the top layer weights. As in Burns et al. (2024) and Figure 1, the teacher model is trained with true labels, and the student model trained only with labels generated by the teacher. We further assume that the teacher model is trained so well that it attains the minimum possible population loss. Thus, the only remaining source of error is the approximation error due to the finite number of units.
Asymptotic Notation. We use Or. Ö.. and Q., where e is one or more variables, to indicate a multiplicative factor that depends on c. E.g., for any two quantities exp1, exp2- that could depend on various variables including d and k. writing exp, = (ex() means that there exists some function f(d, k)) and exponent 2 0 s.t. it always holds that exp1 S f(d, k) exp2 log" (expg).
2. Two Layer Networks, Random Features, and the Weak-to-Strong Setup
We consdier learning a predictor f X' + 3/ where X' = Rd and y = I, aiming for small population loss L(f) := E [x(())) - f (z)) where D is some input distribution and f : X + y our target function. Learning is done using two-layer networks with m units of the form
We consider two different random feature models, corre- sponding to two-layer networks with different activation functions and imput distributions: (a) ReLU activations with an isotropic input distribution; and (b) linear activations with simple anisotropic input distribution. Denoting the teacher and student predictive mean squared errors by LTF and EST respectively (normalized such that the null loss is 1), in both cases we show that the student can infinitely outperform its teacher, in the sense that the ratio LST LTF, can be arbitrarily small. Thus, the Performance Gap Recovered (PGR) introduced by Burns et al. (2024, see definition in Section 2 Equation (7)) can be arbitrarily close to 1. Fur- thermore, we show an even stronger gap, in the sense that the student learns polynomially better: for ReLU networks we show that we can have LST = Ô (CI-2) (Theorem 3.1, relying on the Gassian Universality Ansatz), and for linear networks with anisotropic inputs we show that we can
fu (x) = Σ wio((uu x)),
(I)
where 0 : R - is some fixed activation function (e.g. ReLU or linear), the bottom layer weights u, E Rd are randomly drawn
L.d. ~ U
u:
(2)
from some fixed distribution 24 over R (e.g. spherical Gaus- sian or similar) and then fixed during training. and only the top layer weights w. E are trained. Such models,
2

---

Weak-to-Strong Generalization Even in Random Feature Networks, Provably
which amount to learning a linear predictor over the random features defined by the outputs of the hidden units, have been extensively studied as finite approximations of kernel meth- ods (Arriaga & Vempala, 2006; Rahimi & Recht, 2007), as models and limits of deep learning in certain regimes (Mei et al., 2022) and recently also for deriving scaling laws and optimal tradeoffs (Lin et al., 2024; Paquette et al., 2024).
of gradient descent well, both for 2-layer networks (Ali et al., 2019) and for deep networsk (Elkabetz & Cohen, 2021). In our analysis, we consider student trained with the gradient flow dynamics (5) with stopping time T that needs to be specified and denote the resulting student predictor fsudens = (T, M.),
Infinitely Large Student. Furthermore, for simplicity we consider an infinitely large student MST - oo (see formal mathematical definitions in Section 6). All of our infinit-- width results can be extended to the finite-width case for sufficiently large width.
Weak-to- Sterono Setup. We train two networks, a 'weak' teacher network fiecheer with MIE units, and 'strong' stu- dent network Sstudent with MsT > MTE units. First, we train the teacher network feaeherr == fw.. ur on the true tar- get labels (2:, fxx)) using very large amount of data. We will model this by training the teacher on population. That is, to train the teacher we draw the bottom layer weights ( L random in (2), and for most results in this paper we assume that the top layer weights achieves the population loss minimization (Condition 2.1):
Generalization Gap. We evaluate the student on the ground truth labels (which they do not have access to!), that is
LST == EgE [Sstuteell (2)) (x)))
(6)
Condition 2.1. The teacher model attains the minimum loss among all possible models with the given bottom layers:
We ask how the student error LST compares with the teacher error LTF and, in particular, whether and how it can be smaller even though it only sees examples labeled by the teacher.
wt: = -rg min REED [Nuur (x) 1" (x)))² WER
(3)
To quantify the extent to which the student can best its teacher, Burns et al. (2024) suggested the Performance Gap Recovered (PGR), which is defined as":
We denote the teacher's population loss (which is the minimal possible loss using its MTE random units) by LTe == -EEDD (Stencher (2)) (a=)) We then train the student on inputs x ~ D but only using labels fx))her(z) generated by the teacher. To train the student, we draw the bottom layer at random according to (2), initialize the top layer weights to zero, (0) O, and train these weights using SGD on i. samples az (n)) ~ D labeled with by the teacher:
LTE LST LTE
LTE LsT LTE
PGR
ST
where Cgell 2 0 is the "ceiling performance"(Burn et al., 2024) of the student (the loss the student model could poten- tially have attained with direct access to the real labels). We do not carefully define or analyze this ceiling performance, since we provide lower bounds on the right-hand side in (7), and hence on the PGR regardless of the ceiling.
(n + (n)
(4)
Specific Activation and Data Models. We study two different variants of the random feature model (aka 2-1ayer network with random and fixed bottom layer) introduced above, which differ in the choice of activation function and input distribution:
'7' Owa, (fm,(n)),, (2(()) - freacher (z)))))
Gradient Flow Limit. We assume that the student has unrestricted access to the examples labeled by the teacher, and so can take arbitrarily small learning rate 7) and appropriately large number of steps N. Accordingly, we study the behavior with infinitesimally small learning rate 1) where the student's 's dynamics (4) converge to the gradient flow trajectory:
Model 2.2 (2-layer ReLU Network). The activation func- tions (=) = max(=, 0) is a standard ReLU function, the bottom layer weights u are uniform over the sphere, i.e. U = ln in (2), and the inputs a are also uni- formly distributed on the sphere, i.e. D Unif( In this model, we will consider target function (x) which 27 are sums of linear functions and even polynomials.
dl,,(())
9 dt MST Ows,s
ER ((ars(t).u, (z) ftescher (x))²
Model 2.3 (Linear Network), The activation functions (=) = is linear (i.e. this is linear neural net), and the bottom layer weights are standard Gaussian, i.c. U N (0, La) in (2). This time the inputs x are non-isotropic
(5)
where we replaced the step number n with training time t= myMsT. We add an additional factor of MsT here to ensure the gradient flow has proper limit when MyT - co, which will be useful in the analysis of the rest of the paper. Gradient flow has been show to approximate the trajectory
'This definition in terms of loss is equal to Burns al.'s definition in terms of accuracy.
3

---

Weak-to-Strong Generalization Even in Random Feature Networks, Provably
and are drawn from Gaussian D = (O, v) with diagonal covariance V diag(V' (41, v/2,..., . 1ha) with f/: decreasing- Here, we will consider linear targets supported on the first top few coordinates.
targets, and for large teachers, we can get a performance gap recovered (PGR) arbitrarily close 1. We see also that the PGR is not fine enough measure of weak-to-strong generalization, since the separation is obtained when the teacher error is small, and the PGR does not tell us how small the student error LST can be as a function of the teacher error LTE: having PGR + 1 only says that the student error LST goes to zero superlinearly faster than the teacher error LTE, but not how much faster. Indeed, we can see that even in the ReLU Model 2.2, the student error is polynomially smaller, by an exponent of at least 1.49. This last result relies on the widely verified Gaussian Universality Ansatz, and is also verified in our experiments: in Figure 2(a), we show that when the target f is linear, with proper early stopping time, the loss ratio CST/ Cre decreases when MTE grows. Furthermore, in Figure 2(b), we observe the student loss Lst is polynomially smaller than the teacher loss LrE with an estimated exponent even above our bound. Indeed, we expect our bound on the behavior of ReLU Random Feaure Networks is loose, and it might be possible to establish an even stronger separation.
Model 2.3 is fairly general and was studied by e.g. Lin et al. (2024) as a model for studying scaling laws. It can also be thought of as capturing a model where each unit outputs (u, (()),, where o(+) captures what happens in additional lower layers, which creates non-isotropic representation at the top layer.
3. Quantifying Weak-to-Strong Generalization
We are now ready to establish weak-to-strong generalization, starting with the ReI.U 2.2:
Theorem 3.1 -Satong generalization with 2-layer ReLU Network). Consider the ReLU Model 2.2 and the weak-to-strone stroon setup of Section for any dimension d and teacher size MTE. Consider a target I that is an even polynomial of degree at most k normalized s.t. B[f = 1, with any even degree k. If MTE. 2 (ddak) and the student is trained with some stopping time T = Od,x(log MTE), 3 then we have that with probability at least MIE'
Mrp
1st-
16
log" MIE + log" LTE STE)
LST S &Oa.k
256
VMTE
1.15
and so CST/ CTE + 0 and PGR + 1 as MTE increases. Furthermore, under the Gaussian Universality Ansatz for d >>>>>>>>> 200, LTF. = Da, Myte ) and so as MTF. - oc we have that
162
01 03
0.5
0.6
06
07
Ey
(a) LST/ Lre v.s.
(b) EST v.s. LrE
Figure 2. Weak-to-strong generalization happens in ReLU random feature networks (Model 2.2) with input dimension d = 32, stu- dent size MşT 16384, and teacher size MrE (16,... ... 256). We consider a linear target function (=) = (8, x) for unit norm some 3. Figure 2(a) plots the ratio between student loss LsT and teacher loss LTE. with varying teacher size MTE and gradient flow training time f. With appropriate stopping time, we see a significant wcak-to-strong generalization gain. This gain dimin- ishes with overtraining and rumning gradient flow to convergence, the student mimics the teacher, has the same error, and does not excite weak-to-strong generalization. In Figure 2(b), we fit the minimal student loss Lst (at the optimal optimal stopping time for each teacher size) as power law function of the student loss LTE. confirming Theorem 3.1. See Appendix J for simulation details.
Cst = Oak (C119).
For more detailed statement spelling out the dependnce on the degree k and stopping time T see Corollary E.3 and for the proof see Appendix F.
Theorem 3.1 already establishes that in Model 2.2, weak- to-strong generalization provably happens for large set of
*Or more generally, sum of a linear function and an even polynomial.
'The Gaussian Universality Ansatz states that when sampling the Gaussian universality holds for the eigenfunctions in the sense that the expected risk remains unchanged if we replace them
with Gaussian with appropriate parameters (Simon et al., 2023). In setting, this can be differently stated as the expected risk for Model 2.2 will remain unchanged if replace it with infinitely dimensional Model 2.3 with the appropriate covariance. Formally, the lower hound on LTE and an upper hound on T are conditional on the eigenframework. This assumption has been empirically verified in number of settings (Simon et al., 2023; Canatar et al., 2021; Wei et al., 2022: Misiakiewicz & Saeed, 2024).
In order to demonstrate a stronger separation theoretically, and also avoid the Gaussian Universality Ansatz, we turn to the Linear Network Model 2.3:
Theorem 3.2 (Weak-to-Strong Generalization with Linear Network). Consider the linear network Model 2.3, with Va = (1,....1., th "......,, .b.), where is repeated ls times and b. = (d-k) --)--/3-
'This choice of dimension is arbitrary. We can get close to Est = ( with larger d.
2/3 is repeated d - k times, and a linear
target f (æ)) (3, ar) supported by the first coordinates,
4

---

Weak-to-Strong Generalization Even in Random Feature Networks, Provably
i.e. 3r = 0 for > k that is normalized B[ 1. In the weak-to-strong setting of Section 2. for any l. and d > k + C.' C is absolute constant), and a teacher of size Mye= = (d (d-k) k)2/3,, if the student is trained until time T = (log MTE), we have that with probability at least for all MTE.
feature distribution and target, and how related they are, if the teacher has error LTE, a student, even with many more features, cannot obtain error better that LsT ((CTE).
In fact, we show that this limitation holds much more broadly, not only in random feature models, but for any teacher optimal on some set of features and for any student trained with early stopped gradient flow on any other set of features. The Random Feature models are a special case where the teacher and student models are small and large random subsets from the same feature distribution, but the limitation holds even if the student features are pre-trained or otherwise cleverly selected.
LST S ((K
In particular, for any fixed is as d, MIE + 0o, we have that PGR- +1. 1.
A more general statement for Model 2.3 that holds for any covariance matrix V and target is given in Theorem E.4. For the proof, see Appendix D. We indeed observe the behavior described by the Theorem in simulation experiments, as presented in Figure 3, where we can see the student loss LsT is indeed quadratically smaller than the teacher loss LTE, already for moderately sized networks.
Furthermore, the limitation applies to a broad class of train- ing methods, which go beyond just early stopped gradient flow, All we require that the learned predictor is shrinkage optimal in the following sense:
Definition 4.1 (Shrinking Optimality). Given two func- tions f, frain X + IR we say f is shrinnking-optimet with respect to furin if for any 0 a S 1, EE ((f(x)) funin (x) (z)) S EE, ((af(z)) fuzin {
218
0.000
0.002
2045
545
1404
That is, all we require is that the training method returns a predictor f which cannot improve its training objective, simply by scaling down, or shrinking toward the origin. Shrink optimality is satisfied by loss minimization on a linear subspace (i.e. our learning rule for the teacher). or more generally any convex class that includes the origin, It is also satisfied by early stopped gradient flow over any feature space or with any kernel, and with any stopping time (including T = oo, which corresponds to just loss minimization):
101
400G
0.000
0.000
0.02
0.04 0:65
6:7 0:00 D Eyp
(a) CST/ PT V.S. &
(b) LST v.S. LTe
Figure 3. Weak-to Stron generalization happens in random linear feature networks (Model 2.3). Here we used an input distribution as in Theorem 3.2, with k = 1 and a target function f = (c1, a²) where ei is the first standard basis vector. Figure 3(a) plots the ratio between the student loss Lst and squared teacher loss Ci with varying teacher size MIE, and where the dimensionality d = M/ as set as the scaling of Theorem 3.2, as a function of the gradient flow time f. With proper early stopping time LST/ / LiTE converges to approximately 1 as MTE grows, confirming that for large MTE we have LsT Lhe as in Theorem 3.2. This is also confirmed in Figure 3(b), where we fit the student loss Lst as a power law function of teacher loss Lrg, and recover excellent fit with an exponent very close to 2. We again see overtraining diminishes weak-to-strong generalization. See Appendix J for simulation details.
Lemma 4.2 (Shrinkage Optimality of Gradi- ent Flow Solutions). For any feature map o(x) and any target Smain consider gradient flow -w [[urr, p(x)) ( -frain(x))) (2:))] initialized
ib
at (0) 0. Then al any time 0 S T 60, the predictor fr(x) (w(T), ((x)) is shrink optimal w.E.t. f
Lemma 4.2 shows that in the Random Feature setup consid- ered in Section the teacher and the student both satisfy the shrinkage optimality Definition 4.1, with respect to target and the teacher predictor respectively.
With these definitions in place we are ready to state our main lower bonud on weak-to soak-to-strong generalization:
4. The Limit of Weak to Strong Generalization
In the previous Section we saw how a student can signifi- cantly ourperform its teacher, even in random feature mod- els. In particular, we showed that quadratic reductoin in error is possible. One might ask if in some cases an even greater improvement is possible. Perhaps a cubic or higher order polynomial improvement? In this Section, we show that the quartatic improvement of Theorem 3.2 is the largest possible in any random feature model. No matter the the
Theorem 4.3 (Genereal Limitation of Weak-to-Stron Generalization). For any target f" normalized S.I. ET [xx]] S 1, for any teacher Swacher that is shrinking optimal to f and any student Imndent that is crrinking-optimal shrinking optioall to freacher it holds that
Lst 2 (V1+ 11TTETE - v1 - LTE)
3 CtE
>
4
4
5

---

Weak-to-Strong Generalization Even in Random Feature Networks, Provably
Corollary 4.4 (Limit of Random Feature Weak to Strong Generalization).. For any Random Feature Network Weak- to-Strong training in Section 2, any normalized target [[ = 1, and any student stopping time T, we have that
trained model is already very good (at an extreme-if the pre-trained model already happens to be better on the task than the teacher), the student can be arbitrarily better than its teacher (similar to the speaakng student outperform- ing its non-Chinese-sppaking teacher in Chinese). In the setting of (Charikar et al., 2024), the difference is whether the teacher and student classes contain the origin (in which case shrink optimality holds and Theorem 4.3 applies), or do not contain the origin. One can think of this distinction in terms of whether the inductive bias specified by the fea- ture space, learning rule, initialization, and hyopthesis class is generic, i.c. extends from the origin, prefering certain directions but not a particular point in predictor space, or specialized, i.e. prefering not only particular directions of features, but a very specific bias.
(VI+3CTE VI -VI- LTE)
CST 2
Z Cipe
For the proof of Lemma 4.2, Theorem 4.3, and Corollary 4.4, see Appendix H.
Theorem 4.3 and Corollary 4.4 establish significant limits on the extent of weak-to-strong generalization. We see that although the PGR can be arbitrarily close to onc, and the student error can be quadratically smaller than the teacher error, it cannot be any smaller than that. We cannot have arbitrarily high teacher error and arbitrarily low student error. In particular, we cannot have a situation which the teacher error is very close to the null risk E] i.c. the teacher is barely learning, while the student error is low (if Cie is closer to one, then LST must also be close to one). That is, weak-to-strong learning cannol significantly "boost" a teacher that is only slightly better than chance. And, in order for the student error to go to zero, the teacher error must also go to zero.
Note that the quadratic lower bound in terms of teacher error for student error holds even in a bootstrapping setting with multiple students, see Appendix G for details.
5. How Does Weak-to-Strong Generalization Happen?
Linear Network. To understand how the strong student can correct their weak teacher and obtain a lower error, let us first consider linear networks as in Model 2.3. In this case, both weak and strong models, fteacher (1:) and fsnudem (2r), are linear functions of æ, and thus can be written as (w.(())) (B, ()) where 3 U w. First, let us understand the stu- dent's learning rule. Let fstudeut (x) = fw.u, (x) be the stu- dent predictor. Learning a predictor f with an early-stopped gradient descent shrinks f f- -- smn,, in the direction of the student's s random features a ((u,, x)) = (USTæ)); propor- tional to the variance of each of the features vú.. For a very wide student, i.e. with MST - oc, the student's features will effectively be the coordinate directions 24, the shrink- age of f f fw, u, will be proportional to the variance 1ù of z; in directions I,, This is because as MST - co, we have that UST + MSTI. This makes learning directions Ti with larger variance 4/s (i.e. for smaller i) significantly faster than the ones with smaller variance eh; (i.e. for larger i). If there is a sudden drop in variance uby at index K, i.e. #k >> K the time to learn any direction v, for i S K will be much smaller than the time to learn any of the di- rections I; for > K. So, in this case, we can choose a stopping time T to be such that all large variance directions xy are learned, that is (f ff u.); is very small or in other words (fwr,u) = fe, but all the small variance directions 2; of fw,,, are close to initialization, i.e. zero. In this way, the student predictor fsmudent (x) = fw... u. effectively learned the high variance (i.e. small index i) directions 2; of the teacher predictor fieaeher and zeroed out the small variance (i.e. large index i) directions of the teacher predictor fiescher- All of this can be explicitly seen in the closed form solution of
These limitations hold not only in random feature mod- els, but based on Theorem 4.3, also much more broadly. First of all, they hold with any student and teacher feature theee need not be random. We saw in Section 3 that a quadratic weak-to-strong improvement is possible even with random features, with the same student and teacher feature distributions. But what Theorem 4.3 tells us is that even if the student features are much more specialized than the teacher features, even if they are more aligned with the taregt, or even if they are pre-trained, we cannot get any larger improvement. Furthermore, this holds for a very gen- eral class of learning rules. Beyond early stopped gradient flow, using any type of convex regularizer (minimized at the origin) or constraining to any convex hypothesis class (which includes the origion) also ensures shrink- ootimallti Any such learning rule is still subject the limitation of Theorem 4.3.
The main caveat here is that the limitation applies only with gradient flow initialized at the origin, with convex hypothesis classes containing the origin or with convex reg- ularizers minimized at the origin. Concretly, consider a student that uses a pre-trained feature space. but trains the top layer weights from scratch (starting from the origin). This student is subject to the limitation of Theorem 4.3. In contrast, consider student that fine tunes pre-trained top layer, starting from the pre-trained initialization (or alterna- tively, explicitly regularizes to be close to the pre- trained model). Such a student is not shrink optimal and is not subject to the limitation of Theorem 4.3. Indeed, if the pre-
6

---

Weak-to-Strong Generalization Even in Random Feature Networks, Provably
gradient flow in function space, Equation (5). Let us now turn to the teacher. Although the signal f (i.e. the target of GF) is entirely in the first few high variance coordinates of 2, say {2y ligg K, if we have small number of teacher nodes MTE, they will not be directly represented in the hidden layer, i.c. in Ureæ. Instead, the teacher can only learn @TR. E span(Ute), and so learns STe to be the projection of f to span(Ure). This means that freacher (z) has some energy (non-zero coefficients) in all the coordinates. The student shrinkage will reduce the noise (i.e. teacher signal uncorrelated to the ground truth) in low variance coordi- nates by zeroing out the coefficients along those directions. Therefore, the weak-to-stron improvement comes exactly from improvement along the noise directions (i.e. directions uncorrelated with the ground truth). Note that if we train for too long, the effect will be the same on all directions, so there will be no weak-to-stee teat-no--trong generalization. So early stopping is crucial in this setup.
sis here. In this basis, the teacher predictor is given by fteacher (ar) = Ei, (x))
The student will learn the teacher's coefficients BI, for di faster for the spherical harmonics of lower order k. Since the covariance of the features is given by the square of the coefficients in the decomposition of the ReLU function in the basis &t.k: of they will naturally have jumps for certain indices k. Similarly, for any one of these jumps at, say, k K, i.e. ok > ØK+1, the gradient descent with wide student will learn the directions Ø1 (xx)) for l S K signif- icantly faster than (1))(z)) for k > K. So, again, we can choose an appropriate stopping time T such that the student predictor fw.u, learns the large variance directions, Φs,k for k S K, of the teacher predictor fiencher almost completely, but is very close to the initialization, i.e. zero, for small variance directions, Φi for k > K. This means that the student can denoise the direction of di for k > K. So, in particular, if all of the signal f is aligned with the directions of the first ko order of spherical harmonics, then everything the teacher learns in the directions Φi, for t > ky is the in- correctly learned noise. Zeroing out this incorrectly learned noise enables weak-to-strong generalization. To understand the inner workings of weak-to-strong generalization in this setup further, turn to the dynamics of GF (Equation (5)) in Section 6. This will be simplified if we consider the student's network as a kernel.
As student training progresses we fit more of the teacher's signal (i.e. the target of GF), but the shrinkage effect reduces. This can be seen in Figures and 3, where overtraining hurts weak-to-strong generalization. At the limit, as training time goes to infinity, the student would converge to exactly mimicking the teacher, and thus converge to the teacher error, without any weak-to-strowe to-strong benefit, as can be clearly seen in Figure 2.
The difficulty of applying this reasoning is that we need to establish that significant portion of the teacher error is actually present in the noise direction. In Theorem 3.1 and
6. General Multiplicative Weak-to-Strong Improvement
Theorem 3.2, we not only show that significant portion of the teacher's error Lte will be along the low energy directions but also that when the number of teacher's 's units MTE is large, most of the teacher's error lies along the low energy, i.e. noise directions. Our main result, Theorem 6.5, handles this difficulty. Proving that most of the teacher error CTE is in the low energy directions allows us to conclude that the PGR goes to as the number of teacher units MTE increases, instead of just being positive, and establish quantitative relationship between the student and teacher errors.
In Section 6, we show a general result that describes weak- to-strong improvement of a student described by a kernel trained with gradient flow and an optimally trained teacer with some fixed set of features, which Theorem 6.5.
The application of Theorem 6.5 to the particular cases of ReLU and linear random feature networks is delayed to Appendix E.
Gradient Flow Dynamics Recap. We can rewrite Equa- tion (5) in function space from parameter space in order to analyze the infinite-width limit MsT + oo in the same space. To do that, it will be convenient to consider the student to be described by its kemel
2-layer ReLU. For ReLU, we have a similar situation except that the relevant directions for wide student will the spherical harmonics. Learning a predictor fwru, us- ing as a target with early stopped gradient descent will shrink f - Swa, in the direction of the student's ran- dom features (( x)) = ReL.((u..,, z)), similarly to the case of linear networks. The relevant basis for a wide teacher, i.c. in the MYE + oo case, is not the coordinates of the input n; but rather spherical harmon- ies (3)) The difference comes from the fact that our probability distribution is now D = Unif() and the spherical harmonics 1 100 are the relevant ba-
K(xxx') x') == Eu--uit(ss-)) (u, x')]] (8)
The kernel K. can be decomposed as K(xxx')
Σizi (xex(x)exxx")) where {Ar) are the eigenval- ues of the associated kernel operator in descending order, and (<:(=)) |22, are orthonormal eigenfunctions in the in- ner product with respect to D, which we denote (s)),, i.e. Cp) = d.z. The inner product is defined as (f.g)D := EE<D [f))) We can derive (see Ap- pendix A) the following closed-form expression for the
7

---

Weak-to-Strong Generalization Even in Random Feature Networks, Provably
gradient flow dynamics of the student (Equation (5)) time t in the MST -> Do limit:
Teacher-Student Feature Alignment. The key quantity in our characterization of weak-to-strong generalization gap is teacher-student feature alignment, Kis. Let MrE = m and let {er be the eigenbasis of the student's 's kerne K. Let w E IR" be the teacher's 's weights, and let the teacher be parametrized as freucher = fu = >i=1 Wigr. where {9: | are teacher's units, i.e. features. Let the student's predictor at time T be fr. For S 2 K, let As, Bs E Rm*x be the Gram matrices of teacher's features projected onto the top-S eigenspace of K, i.e., As,.. :- Σx= (g,, ex) (fj.ex) Ex)
ft 2(1- (1-e Aut) (freacher: Dek
(9)
We note that given data distribution D (and thus the inner- product ()), the above solution of gradient flow at time t is only function of target fueuceer, time t, and the kernel K, which we denote by Jt = TT (Jrscher), where T.K. A iid-e e tK and id is the identity mapping. In other words, if different two-layer networks have different bottom layers but with the same induced kernel, they lead to same training behavior under gradient flow. For an outline of the derivation of gradient flow dynamics, see Appendix A.
Bss., == Ex2s+1 (9i: (x) ER)D. Then we define the teacher-student feature alignment Kis as
Kig 1+ (((((VAs)BB((V
(10)
Kg measures the alignment of the teacher's features with the top-S cigenspace of the student kernel and is a com- pletely deterministic quantity, As explained in Section 5, this misalignment is crucial for enabling weak-to-strong generalization in this setup.
Improvement Bound for Early Stopped Gradient Flow. First, in Lemma 6.2, we will derive bound on the error of student trained with an early stopped gradient flow in the weak-to-stron tt-oon setup. Consider a gener- alized 2-stage learning process of weak toot-nn setup from Section 2. where the student is trained with gradient flow for time t with kernel IC on population given by the teacher predictor fueatbrr. i.e. as given by Equation (9) and denoted with J, = (Jrachar)), but the teacher predictor can be an arbitrary square integrable function in the eigenspace of AC Furthermore, we require that the student's 's kernel IC correctly captures the prior of the target function f in the sense that f is supported on the top- eigenspace of IC with nonzero eigenvalues:
Student-Teacher
We will refer to fu the optimally trained teacher. We will require that no two units in the first layer of the teacher will be linearly dependent among the first K directions { 1=1- Condition 6.3. rank Ax) = K.
Lemma 6.4 (Error Ratio of Weak to-Strong Predictor in High Order Figendirections). In the random feature model in Equation (1), under Conditions 6.1 and 6.3, if ((fev) ER" ((fw() ), then Ex2s- (fu ex 2 Kgg f((fw).
Condition 6.1 (Ground Truth). f* is supported on the top- K eigenspace of K. corresponding to nonzero eigenvalues, i.e., if Ax = 0 for k S K then (f*,,x)) E = O and Vk K ( =
Lemma 6.4 shows that if the signal is spanned by first S eigendirections then at least Ky portion of error of the ran- dom feature predictor in Equation (1) will be in the eigendi-
rections of order 2 S S+1. 1.
Using Equation (9), Lemma 6.2, and Lemma 6.4 we can understand how weak-to-strong happens from Section 5 more clearly. In this notation, in Section 5, (fuswhers Ex)D is what we call 33 and (x are in Model 2.3 and spherical harmonics & in Model 2.2. Note that since A are decreasing, ---e-a e - is closer to for larger eigenvalues A; i.c. smaller indices i. In the special case that there is K for which AK+1 is significantly smaller than Ak, then for stopping time T E (xt2 AK+1 ), all e -X.T all going to be close to 0 for i < K, but e e for i 2 K + will be close to 1, effectively zeroing out freacher in directions K This means that in Lemma 6.2, the second term A 2- x I will be small. Taking S K + 1, the thirm term will be close KK+1 portion of the error by Lemma 6.4, which Lemma 6.2 shows that we zero out. This is the intuition behind Theorem 6.5.
Then, we can bound the students error at time T with respect to the ground truth f in terms of the spectrum of the kernel Ag.
Lemma 6.2. Under Condition 6.1 for any kernel K., any function Suncher in the eigenspace of K., all stopping times T > O, and any index S 2 K. we have that for the predictor St = T. (f (eeacher), then L(fr) S [(reuchier) + ART 2- R 11
T2 Ek2841 (Junacher, ex)o
Lemma 6.2 is an intermediate lemma that shows that the error of an early stopped GF solution with respect to the grond truth f* can be bounded in terms of the target fieehhr and the projection of the target freacher into the eigenspace of order 5 + 1, Σx2s+1 (freaceer ex)B- So, to get the final weak-to-strong upper bound (i.e. Theorem 6.5), we show in Lemma 6.4 that for the optimally trained teacher, the proportion of error in eigendirections of order 2 S ++1 is lower bounded by a quantity we call saacher-ttuden feature alignment.
Multiplicative Error Improvement in Weak-to-Strong Generalization. Our main result establishes multiplica- tive error improvement in the weak-to-stie to-stongg setup for a
8

---

Weak-to-Strong Generalization Even in Random Feature Networks, Provably
2-layer network teacher with any features, even even non-random, and student described by a kernel K.
loss and (Wu & Sahai, 2025) consider classification with a minimum norm interpolator. In the setup of Charikar et al. (2024), if the teacher and student classes contain the origin, our lower bound applies to their setting.
Theorem 6.5 (Weak-to-Strong Multiplicative Error Im- provement). For any groundtruth f", p.s.d. kernel K and positive integer K satissfing Condition 6.1 and any teacher model Suacher satisfying Condition 6.3 and Condition 2.1 ( (feacher attaining minimum loss), then for any time T > O, then the test loss of student saudeen 2 Txx (Fuacher) has the following upper bound:
Following up on Burns et al. (2024), many works explored ways to leverage weak models to im- prove the performance of strong models. Shin al. (2025); Li et al. (2024) propose data selection methods to improve W2S generalization. Somerstep et al. (2025) propose to use in-context learning to refine weak teacher labels. Yang et al. (2024); Bansal et al. (2025) show that small models can be effectively used to generate reasoning data with Chain-of- Thought (CoT) for supervising large models Bansal et al. (2025) point out that this can be more compute-optimal as compared to generating data from large models. Sun et al. (2024) showed that weak model can be trained reward model on easy tasks and then used to guide the training of strong model on harder tasks. Ji et al. (2024) proposed a plug-and-pin -laypppa module for alignment, where a small model learns to redistribute the output of a large model. Tao & Li (2025) systematically evaluated the performance of aligning large model with feedback from a small model instead of human feedback. Yang et al. (2025) highlighted that the strong model can deceive the weak model by being well aligned only in the areas familiar to the weak model.
Empirical Work.
{ (1 (3)1 (1- LTE
LST S inf 52K
+ 2 2- 1
Theorem 6.5 shows that if there is a large enough eigengap between A₂ so that Ki is close to 1, then we can select the early stopping time T" so that the student is only left with (1 (1-ks) fraction of teacher's loss. Note that Theorem 6.5 is completely deterministic and holds both or random and non- random teachers. For the proof of Lemma 6.2, Lemma 6.4, and Theorem 6.5, and the explanation for when equality holds, see Appendix C.
7. Related work
Theoretical Understanding of Weak-to-Strong General- ization. Lang et al. (2024) propose theoretical frame- work that establishes weak-to-strong generalization for clas- sification when the strong student is assumed to learn func- tions that are robust to mislabeled data among many cor- rectly labeled neighbors. Shin et al. (2025) use this frame- work to formulate a mechanism for weak-to-strong general- ization for data with easy and hard patterss. Charikar et al. (2024) study a general regression setup with squared loss, where a key example is training only the last linear layer of the teacher and student networks. They show that if the strong student's 's capacity is not large enough to express the weak teacher's 's function, then the student can outperform the teacher by an amount quantified by how much the stu- dent does not fit the teacher's labels. Mulgund & Pabbaraju (2025) further generalize this result to a broader class of loss functions, including the cross entropy loss. Wu & Sahai (2025) demonstrated that weak-to-strong generalization can happen in an overparametrized spiked covariance model for classification. (Ildiz et al., 2025) show that in a two-stage learning process in high-dimensional ridgeless regression, student trained teacher labels can be better than student trained on real labels (which is an effect of "distillation" rather than "weak-to-strong"
8. Conclusion
We prove that weak-to-strong generalization can happen even in a simple model of two-layer neural networks with random features. We show that in this case, the PGR (Per- formance Gap Recovered) can converge to 1 when teacher loss goes to O. Additionally, we show an even stronger sep- aration between the teacher and the student, namely that the student error is polynomially smaller than the teacher error. For the ReLU network, we show that the exponent in this polynomial dependence is at least 1.49 while for the linear networks, we show that it is 2. Further, we explain that in his setup, early stopping is crucial for weak-to-strong generalization to occur. We also explain that in this setup, the weak-to-strone improvement comes from the student zeroing out the teacher signal in the high-order eigendi- rections (which in our setup are noise directions under the condition that the ground truth is spanned by the first few eigendirections). Most interestingly, we show that there is inherent limitation to weak-to -o-soong generalization in random feature models trained with gradient descent or gra- dient flow, and even more generally. Namely, we show that if the target is normalized, the student error can be at most quadratically smaller than the teacher error. Our quadratic lower bound asserts that the student loss cannot be smaller than the square of teacher loss, regardless of the choice of student feature, the early stopping time.
Charikar et al. (2024) and Wu & Sahai (2025) consider linear models that are most closely related to our setup. Charikar et al. (2024) consider a general regression setup with square

---

Weak-to-Strong Generalization Even in Random Feature Networks, Provably
Impact Statement
Tomezak, J., and Zhang, C. (eds.), Advances in Neural Information Processing Systems, volume 37, pp. 126474- 126499, Curran Associates, Inc., 2024.
This paper presents work whose goal is to advance the field of Machine Learning. The phenomenon of weak to strong generalization was introduced as route to scalable over- sight, where the weak model is the human overseer who is trying to align the strong model, which is super-AGI. The current paper develops fundamental understanding of this phenomenon in the context of the random features model. Currently, there are no societal implications, but in the future, this work could lead to a better understanding of the uses of W2SG in super alignment. But that currently hypothetical.
Defllippis, L., Loureiro, B., and Misiakiewicz, Dimension-fre free deterministic equivalents and scaling laws for random feature regression. 38th Conference on Neural Information Processing Systems (NeurIPS 2024).. 2024.
Elkabetz, O. and Cohen, N. Continuous vs. discrete op- timization of deep neural networks. In Proceedings of the 35th International Conference tion Processing Systems, NIPS '21, Red Hook, NY, USA, 2021. Curran Associates Inc. ISBN 9781713845393.
Neural Informa-
Acknowledgements
Ildiz, M. E., Gozeten, H. A., Taga, E. O., Mondelli, M., and Oymak, S. high-dimensional analysis of knowledge distillation: Weak-to-strong generalization and scaling laws. The Thirteenth International Conference on Learn- ing Representations, 2025.
ZI. and SA are supported by OpenAl superalignment grant. SA is also supported by NSF, DARPA, and ONR. MM would like to thank Theodor Misiakiewicz for providing the reference (Defilippis al., 2024) and for useful discussion about it.
Ji, J., Chen, B., Lou, H., Hong, D., Zhang, B., Pan, X., Qiu, T. A., Dai, J., and Yang, Y. Aligner: Efficient alignment by learning to correct. In Globerson, A., Mackey, L.,, Bel- grave, D., Fan, A., Paquet, U., Tomczak, J., and Zhang, C. (eds.), Advances in Neural Information Processing Sys- tems, volume 37, pp. 90853-908899 Curran Associates, Inc., 2024.
References
Ali, A., Kolter, J. Z.,, and Tibshirani, R. J. A continuous-time view of early stopping for least squares. In Proceedings of the 22nd International Conference on Artificial Intel- ligence and Statistics (AISTATS) 2019, Naha, Okinawa, Japan, 2019.
Lang, H., Sontag, D., and Vijayaraghavan, A. Theoreti- cal analysis of weak-to-strong generalization. In The Thirty-eighth Annual Conference on Neural Information Processing Systems, 2024.
Arriaga, R. I. and Vempala, S. An algorithmic theory of learning: Robust concepts and random projection. Ma- chine Learning, 63-2:161-182, 2006.
Bansal, H., Hosseini, A., Agarwal, R., Tran, V. Q., and Kazemi, M. Smaller, weaker, yet better: Training Ilm reasoners via compute-optimal sampling. The Thirteenth International Conference on Learning Representations, 2025.
Li, M., Zhang, Y., He, S., Li, Z., Zhao, H., Wang, J., Cheng, N., and Zhou, T. Superfilterigg Weak-to-strong data filtering for fast instruction-tuningg In Ku, L.-W., Mar- tins, A., and Srikumar, V. (eds.), Proceedings of the 62nd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pp- 14255-14277 Bangkok, Thailand, August 2024. Association for Com- putational Linguistics. doi: 10.18653//1/2222.accl. 769.
Burns, C., Izmailov, P., Kirchner, J. H., Baker, B., Gao, L., Aschenbrenner, L., Chen, Y., Ecoffet. A., Joglekar, M., Leike, J., Sutskever, I., and Wu, J. Weak-to-strong gener- alization: Eliciting strong capabilities with weak supervi- sion. In Forty-first International Conference on Machine Learning, 2024. URL https:/ opwnreviee.....e /nett forum? L=gggggggghgggg.
Lin, L., Wu, J., Kakade, S. M., Bartlett, P. L.,, and Lee, J. D. Scaling laws in linear regression: Compute, param- eters, and data. 38th Conference on Neural Information Processing Systems (NeurIPS 2024), 2024.
Canatar, A., Bordelon, B., and Pehlevan, C. Spectral bias and masel alignment explain generalization in kernel regression and infinitely wide neural networks. Nature Communications, 12(1):1-12, 2021.
Mei, S., Misiakiewicz, T., and Montanari, A. Gen- eralization error of random feature and kernel methods: Hypercontractivity and kernel matrix concentration. Applied and Computational Har- monic Analysis, 59:3-84, 2022. ISSN 1063-5203. doi: URL https: //www/ sci encedi rect.
Charikar, M., Pabbaraju, C., and Shiragur, K. Quantifying the gain in weak-to-strong generalization. In Glober- son, A., Mackey, I.,, Belgrave, D., Fan, A., Paquet, U.,
10

---

Weak-to-Strong Generalization Even in Random Feature Networks, Provably
Zhang, C. (eds.), Advances in Neural Information Pro- cessing Systems, volume 37, pp. 51118-51168. Curran Associates, Inc., 2024.
Special Issue Harmonic Analysis and Machine Learning.
Misiakiewiez, T. and Saeed, B. non-asymptotic theory of kernel ridge regression: deterministic equivalents, test error, and GCV estimator. CoRR, abs/2403. 08998, 2024. doi: 10.48500AARXIV2243.008882 doi. /t../////.oo.....o//oo////.// 48550/550/00 /003550//rxi... 2403. 08938.
Tao, L. and Li, Y. Your weak LLM is secretly strong teacher for alignment. In The Thirteenth International Conference on Learning Representations, 2025.
URL https://
Vershynin, R. Introduction to the non-asymptotic analysis
of random matrices, pp. 210-268. Cambridge University Press, 2012.
Mulgund, A. and Pabbaraju, C. Relating misfit to gain in weak-to-strong generalization beyond the squared loss. arXiv preprint arXi::2501.19105 2025.
Wei, A., Hu, W., and Steinhardt, J. More than a toy: Random matrix models predict how real-wortd neural representa- tions generalize. In International Conference on Machine Learning. Proceedings of Machine Learning Research, 2022.
Paquette, E., Paquette, C., Xiao, L., and Pennington, J. 4+3 phases of compute-optimal neural scaling laws. 38th Conference on Neural Information Processing Systems (NeurIPS 2024). 2024.
Wu, D. X. and Sahai, A. Provable weak-to-strong general- ization via benign overfitting. The Thirteenth Interna- tional Conference on Learning Representations. 2025.
Petrini, L., Cagnetta, F., Vanden Eijnen,,,,,,en, E., and Wyart, M. Learning sparse features can lead overfitting in neural networks. 36th Conference on Neural Information Processing Systems (NeurIPS 2022), 2022.
Yang, W., Shen, S., Shen, G., Yao, W., Liu, Y., Zhi, G.,
Lin, Y., and Wen, J.-R. Super(ficil))atignnee models may deceive weak models in weak-to-strong generalization. In The Thirteenth International Confer- ence on Learning Representations, 2025. URL https: / /ppenrevveww..o net/
Strong
Pinelis, I. Optimum bounds for the distributions of martin- gales banach spaces. Ann. Probab. 22(4), pp. 1679- 1706, 1994.
Rahimi, A. and Recht, B. Random features for large-scale kernel machines. Advances in Neural Information Pro- cessing Systems 20 (NIPS 2007), 2007.
Yang, Y., Ma, Y., and Liu, P. Weak-to-strong reasoning. In Al-Onaizan, Y., Bansal, M., and Chen, Y.-N. (eds.), Find- ings of the Association for Computational Linguisties: EMNLP 2024, pp. 8350-8367, Miami, Florida, USA, November 2024. Association for Computational Linguis- tics. doi: 10. 10.18/653v 1/2024. findings-emnlp.....
Samuel, A. L. Some studies in machine learning using the game of checkers. IBM Journal of Research and Development, 3(3):210-229, 1959. doi: 10.1 13..3.3/r 0210.
Shin, C., Cooper, J., and Sala, F. Weak-to-strong general- ization through the data-centric lens. In The Thirteenth International Conference on Learning Representations, 2025.
Simon, J. B., Dickens, M., Karkada, D., and DeWeese, M. R. The eigenlearning framework: A conservation law perspective on kernel regression and wide neural networks. Transactions on Machine Learning Research, 2023.
Somerstep. S., Polo, F. M., Banerjee, M., Ritov, Y., Yurochkin, M., and Sun, Y. A transfer learning frame- work for weak to strong generalization. In The Thireentth International Conference on Learning Representations, 2025.
Sun, Z., Yu, L., Shen, Y., Liu, W., Yang, Y., Welleck, S., and Gan, C. Easy-to-hard hard generalization: Scalable alignment beyond human supervision. In Globerson, A., Mackey, L., Belgrave, D., Fan, A., Paquet, U., Tomezak, J., and

---

Weak-to-Strong Generalization Even in Random Feature Networks, Provably
Appendix
A. Gradient Flow Dynamics
We first introduce the function space view of gradient flow over the top layer of the student's network Equation (5). The main benefit of working function space from parameter space is allowing us analyze the unfintte-width limit in the same space. We first recall we parametrize the student
MST
Ssudent fu., un (x)
1 ((us, x)).
Let (2) (((u,,:: x)). Then, Equation (5) in function space is
d
1 MaT
dt (m),,)
B (1) (t), (2) feaaher (y). os,((1)) (x,((x)
MST
(11)
i=1
ByyDD
MET (x. y) (fw, (w) (aascher(()))
where Ksr (z. y)
E on (z)o,, is the empirical kernel.
Mgr
Taking MST + oo, the solution of Equation (11) converges the solution of the following equation:
d [((x) BYDD KK(x,, y) (fr(y) feeacher (y))
(12)
dt
where
K(æ, x²) = Bu [o( (o) x')]-
(13)
The kernel IC can be decomposed as K( = EkZI (x)e (2x), where a 2 A 2 A ... are the eigenvalues of the associated kernel operator in descending order, and e, (x), e2()) (.)...... are orthonormal eigenfunctions, that is, (e,, e = dij. This allows us to decompose the gradient flow dynamics (Equation (I1)) into simple ODEs for each eigendirection, which can be easily solved. With this decomposition, we can derive the following closed-form expression for the gradient flow dynamics of the student (Bquation (5)) time l:
Σ (1- -xx)) (feescher D
(14)
Theorem A.1 (Closed Form Solution Gradient Flow Dynamics). Let K. X X + R be p.s.d. kernel with eigendecomposition K((x,, a²) >i= (x))())) where (ei, ej) = 8zz. For any f X + IR, the equation of gradient flow for a predictor ft
d dt f((x) EynD [K(x, v) (f:(y) - (z))).
(15)
with initial condition given by fo 0 has a closed form solution ft
ft Σ e1-e-\o (f" ex)Dek.
Proof of Theorem A. To solve the gradient flow equation in (15), we project it onto the eigenbasis of the kernel operator K. Let 83 (Jt, e be the coefficients of ft-
Taking the inner product of both sides of (15) with ey:
d
3/ EEYDD ()) f()i
di
= = fi - 1")
- (f", e5))))
12

---

Weak-to-Strong Generalization Even in Random Feature Networks, Provably
Solving this ODE with initial condition % =0 0:
3i = (1 -1-
Therefore,
2
= Tx Σ [1 -1-c e ) eyypee,,
which concludes the proof.
B. Different Model Types
We will first introduce model that is slightly more general than Model 2.3. Model B.1 (Diagonal Covariate Features). Let fe; ] be fixed orthonormal basis of L2 (2). Take the random features to be given by
9
g. De
where (1g,ei Gi ~ A), where A = (A1, ......) in decreasing order.
Our results will hold for Model B.I and they are more general than Model 2.3.
Proposition B.2 (Linear network Diagonal Coavariate Features). To gel Model 2.3 from Model B.I, we take A Thus if we set 9; in Model B. I as (1)) (........ Va 0, O....). (x + TTu. J,,u,a x + u) = Ei= 1uu,, and ex(x) = 2./. A).
g(x) x U4 where U (0,, Ia), then flg, e Los Proposition B.3 (ReLU Network as Diagonal Covariate Features). If in Model B.1 we take D = Unif(Sd-1), (e:) be the spherical harmonics { ==1lk=11 and choose A = (01...., 02...., .2................ ok....,kk.... Tk....) where dg repeats NR times, we recover the same feature covariance as in Model 2.2. Under Gaussian Universality assumptions, for this instance of Model B.I, the teacher and the student risk behave the same as in Model 2.2.
Proof of Proposition B.3. In Model 2.2, the kernel induce by the random features is given by
K(x, x') := Buwuningá (o ((),,,))
random feature in the ReLU case Model 2.2 is given by
N
((w x)) E NNNorPas((W,ee) Σ (x(()(1))
T (
random feature in the Diagonal Feature Covariance case Model B. given by
DC N
g(x)
Gi (x).
((x,x') (u(o((u, (o(((, = E,,
Σ ah (d)( (b(())) on (x)) (((("))
Σ
o (vbe( (x)
A20
420
On the other hand, we have that for Model B.1 the kernel is
x'x,x')= E, [o(x)g(<')) = E,
ΣΣ
Σ
(z))
i.k
5.l
k=0
13

---

Weak-to-Strong Generalization Even in Random Feature Networks, Provably
B.1. Diagonalizability of the Feature Covariance in Model 2.3
In this section we establish the generality of Model 2.3. Namely, we show that one can assume that u is isotropic Gaussuian distribution and has diagonal covariance if and only if their covariance matrices codiagonalizable.
Proposition B.4 (Diagonalizability of the Linear Network Covariance), A linear network (2) with bottom layer weights distributed accoding to Gaussian distribution U (0, Vu) and the inputs x distributed according to [(, vx) is equivalent to Model 2.3 if and only if Va and Vu are codiagonalizable, with V = S / S V.. / the shared basis.
where V
Proof of Proposition B.4. Note that the distribution in the first case is given by x (u,z) | x .N NN, x Note further that for Model 2.3 with ! we have that غ ã ~ (ü. .)) Σ ~ N(0, V). Now if ē Ax for some A, then we have that y = cov ))) = cov(Ax) = A E A = A V,S, S,S,V A. where Vz is the basis of En, i.c. Eg = V S V₂ for St diagonal. Since is diagonal. So A V V2 A is diagonal if and only if A = DV, for Vz a basis of Eg and some diagonal matrix D. So the distributions of z and E are the same if and only if A DV, and x'axx x ~V, D² so Eu- V2D
C. Proof of Weak-to-Strong Multiplicative Error Improvement
Here we present the proof of Theorem 6.5. We will introduce the following notation. Let MTE = m and let { be the eigenbasis of the student's kernel K. Let the units, i.e. features, of the student be functions g drawn from some distribution G. For example, in Model 2.2, we gave that G is given by g(x) = o o(u,, x)) where u ~ unif(Sd-1). Let w E R be the teacher's weights, and let the teacher be parametrized as fiencher S = Ei= wigh, where (g: | are teacher's units, iee features. We will refer to fu the optimally trained teacher. Let the student's 's predictor at time T be fr. Let 7 be the Hilbert space of square-integrable functions with respect to D. Let o e Rm be the Gram matrix of random units, ie., 2y = (o,, G,)D Σx21 (a,, ( EA)
C.1. Preliminary Lemmas
Lemma C.1. For all k, k2 2 1,
A
ik==,
Egnella. (g) =
otherwise.
Lemma C.2. For e E 10,
(1- (1-c) A) - -62 s A² +
c 2 2-c
b²
Proof of Lemma C.2.
(Ib+ A) b)2 -(11 - -) - cb)² = (1 c)2
1 A + (2c-c))
2c - - (-eb)) 2
1
1 C
1
$ S (1-c)) c)2
2 + (2c dt)
(1 c)2
(2-c)
2
b2
2
where the inequality follows from Jensen's 's inequality.
The following is a standard result on the generalized Rayleigh quotient.
Lemma C.3. If X, Y E pmxxm are symmetric PSD matrices, then
YYu
((VX))(VVX)))
sup xEcolspan(X))
2 Xu
14

---

Weak-to-Strong Generalization Even in Random Feature Networks, Provably
Proof. Let colssan X) \ (0). Then u vX for some Z E
I {()). Thus,
u T Yu
z =T <v
2
S X1 (VV)*)
u Xu
z 2
The equality is achieved when z is the top eigenvector of (VX)+
C.2. Proof of Theorem 6.5
Lemma C.4. Under Condition f. all T 0,8 K and w R", we have
[(ST) S ((ww) + e ->x
e | (1- 1-1 Σ (kw
125+1
Proof of Lemma C.4. By (9).
((fr) = Σ (1 (fore - (f" ex)D 2
We provide upper bounds for lx in three cases. First, for all s k s K, by Lemma C.2 we have
e x
lx = ((1 (1-c--ATT (fe, ex)o - (f" (x>))) 1 (ffw ex)b (f" (f"
+
2 -- :x)2
(f'
s (ww (x)))))
2
+
e ex)
e exxx
2
where we used the fact that e ~ S e-Ae for 1 S k S K.
Then, for KL + 1 k ks S, we have
4 = (1-e---) (wwe)) (e)))) = (1 c (fw, exl2 & (Jw, - (f" (("))))))
Finally, for l 2 S + 1, we have e ~ 2 e - 2 1 - As+IT, T, and thus (1 (1-e~ S A3+1 T2, This implies the following bound for Ex:
l = (11- ~ (fw - - (f", ex))))
= = (1-e - e1-e->i7) ex)o S $ 1 Ex)..
Putting all these together proves the following:
-xxx K
((Sr) $ (fw,, ex) (8", (s')))))) 2
Σ (5, 13411 T Σ (Sur
T
k=
125+1
e ~xxT
K
((uu (8', (1*)ex))) )²
+
(5" ex) - (1 - X3 S T2)
Σ
(fuse ex12
2 - c -xxT
121
k=1
k2S+1
c AKT
= [(fw) +
2 - 1 - -(1 11-3_117 T2)
(Lwi Ex)2
828+1
which completes the proof.
It remains to bound Ex2s41 2. Let G : Rm + H. be the linear operator that maps u E RM to Σ ugg: E H. Let pf := E (f, ex be the projection operator onto the top-K eigenspace of IC, and Q be the projection onto the span of (gi...., }. Then G = $ G PG = A and Q = G G.
In the following, we give a characterization of K.
15

---

Weak-to-Strong Generalization Even in Random Feature Networks, Provably
Lemma C.5. AfA + O, then R QPQ # O and equals the smallest non-zero eigenvalue of R.
Proof. If A o 0, then there exist - m such that (Pgr, Pga) + O. This implies R + 0 because (gi, Rgz) (PQ9,, PQg;) * O.
Let Pmiu be the smallest non-zero eigenvalue of R. To see why & Pmins we first express Puiin as the minimum of Rayleigh quotient:
(a, Ra)
Pmin
inf eErange(R)
(a, a)
(16)
Then we have
Range(R) range(QPQQ) = (QPGo U D
R")
(GG VERR).
Since A G PG, we further have
range(R)) = (GAv uE RT) = {Gu u E colspan(A)}
Plugging this into (16), we have
(uu, RGuu
G.
u T Au
inf Pmin uEcolspan(A)
inf uEcolspan(A) (A) (u, G G*Gu)
inf @Ccolspan A) u 4u
(Gu, Gu))
u qu
sup (Ecolspan(A) Au
Since +- = A + B, we further have
T TAA B)u
Bu
Punnn
sup @uColsppan
=1
1+
sup MEcolspan( A) u Au
(A)
n. Auu
By Lemma C.3, the supermum here equals A1 ((V))+BL B(VA)+).
Therefore,
Pmin 1+ ((VA) B(VA)*) K.
which completes the proof.
Now we give a lower bound for Ex2s+1 (fw, ex) in terms of L(fw).
Lemma C.6. Under Conditions 6.1 and 6.3, if L(f min ERm L(Swwr) ), then
Σ (swren K L(fw):
(17)
$25+1
where the equality is atlained iff f Ph² for some h² H that is the span of the eigenvectors of R QPQ corresponding to the eigenvalue (if exists) and the smallest non-zero eigenvalue, which is
Proof of Lemma C.6. By Condition 6.3, f span Pym. range(PG) range(PQ)). which implies that there exists h E H such that f PQh. As w minimizes L(fw), for must be the least square solution and fuv = Q PQQ Rh. So have the following identities:
Σ (Lw: e [|(1 - - =
|[I- (h, QPQ(I -P)QUU))
125+1
c(fw)) = 11 fu = MIPQh-QPQNIT -IU=Q))Qu)]= (P(PP-)))Q)))).
16

---

Weak-to-Strong Generalization Even in Random Feature Networks, Provably
We express the linear operators and
and Q))) in terms of R follows.
- 0000
= R(R - R?),
Q - -PP = R-
Note that 0 3 R 3 T since (J,QPQN'D = (QS. and 0 v P(Qf)) & (Q1, = (..f) Let
Rf = Ei= (v,, f),, be an cigendecomposition of R, where 1 2
a2-- 2 > 0 and fu1,... U2 are the
corresponding eigenvectors.
By Condition 6.3, A & O. So by Lemma C.5, + 0, r 2 and Pr = R. Then we have
Pi (p; (h, 2;) (fw: 2x) = (h,, (R(R ))) = Σ A29+1
Σ
1=1
R. (pi -1:)(h, vi - (h, R2) =k.L. k.L(fw)
1=1
which proves (17).
To understand when the equality is attained, note that the equality holds iff the inequality in the second line is an equality. This means that for all S i S either Ps {1,k} or (h, u,)D 0. Equivalently, h can be expressed as h = u11h + 12h2 for some μl; #2 IR, where h1 is an eigenvector of R corresponding to eigenvalue 1 and h2 is an cigenvector of It corresponding to eigenvalue k.
In this case, f = PQh = μ1 PQh1 + 42h2. This can be further simplified to f = μ1l Ph1 + U2Ph2 = Ph since hi, h2 range R) S rQngo(Q).
Proof of Theorem 6.5. Putting Lemma C.4, Lemma C.6 and Lemma C.5 together, we have
e TxT
[(fr) S ((fw)
2 A AKT 1 (1- )x- L(fw)
e>xx
= (1 - (1 (1- -1-15+11 ((fw) + - Ax
- 115
which completes the proof.
C.3. General Lower Bound on
We will bound
KS =
1+ ((Vss( Bs +)
in the general case.
Let FA and Fg be defined follows:
FA span(ei..... es) + Rm
FA:h
(h,g))D
FB span(es, R
:
FB h+ (h.g))
17

---

Weak-to-Strong Generalization Even in Random Feature Networks, Provably
We will denote F and F their adjoint operators.
We rewrite the largest eigenvalue of (Ag))
8 F
A (v As) Bs(v
([ (s(VAs)))=
sup vEspan(ei.....e.)) v FAFAFF F
Let H. be Hilbert space defined as
H = (linear mappings from span(e1,..... ee) to span(ej, span(e),e_-1;." eJ-1,-..))
with the inner product defined as
U1 Elle))
We will show the following lower bound first. Proposition C.7. For span(ei,...... : ,e)) it holds that
x² FAFAFAFAU (A)
Proof. Let Ei=1 u:c; FAV. Then have that
FA UgCs: Σ
uueioo 2 ||1/2
(A))
For the upper bound, we will use the concentration of [| Full2. Proposition C.8. For Ej=n tse it holds that
F S
Σ F
Σ o
Proof. This follows immediately from Cauchy-Schwarz inequallity....
Proposition C.9. Let Y H be such that (e,, (())
(e).9)p(a,)))
|
Σ Σ
k=1==
so [Ps that is = 11
Pll P2
Furthermore, les Y; be the r.v. corresponding to the draw of the i-th feature gs- Then
F FA
Y,
We have the following concentration bound in Hilbert space.
Theorem C.10 (Pinelis, 1994)), Let Y, be independent H valued random variable with E(Y,) 0. where H is seperable
Hilbert space. Assume that for every 2 2, E N we have that E ([);))))) < B2 Then, for all E N and e 0 we have
ne
P
YN
>
< 2exp
B2 + Le B B 2Le
18

---

Weak-to-Strong Generalization Even in Random Feature Networks, Provably
Putting these together in the bound for λι ((v Bs(v ((s(A Ag) +), we get the following.
Proposition C.11. The largest eigenvalue of [A)) ( BB((As bounded by
شコ= FAe
> ((SAs)+Bs(AAA))
AA(A)²
Proof of Proposition C.11. This follows directly from Proposition C.8 and Proposition C.7.
We can now use this to bound the norm of FBFA Proposition C.12 (Hilbert Space Concentration). With probability at least 1 - 20
| FAlB S mB log 1 2
where B is as defined in Theorem C.10.
Proof of Proposition C.12. In Theorem C.10, taking m²e2 = mB² log" J. we get the desired result.
We can lower bound the cigenvalues of A using matrix concentration results.
Theorem C.13. Let a = (g.em)
as ~ G be a row of A. Depending on whether the rows of A are subgaussian or
k=1
bounded a.s. we have the following two bounds:
1. Under Model B.I, i.e. with Dg A) where A diag(>1;>2> then with probability 1 2 2exp(-cl3) holds that
{)(A) 2 As (vm- CVJ -tJ- -VJ--A -ta)²
if m 2 CVJ+ty tA where C C= and c = O (L)) where Ly is the subgaussian norm of the vector a. In this
case Lg S CgAr, where Cg is an absolute constant.
2. Under Model 2.2, i.e. if = a (w, x)) with w ~ unif( 54-11 1) and No + N1 +..... N No No+No N₁ + +N+ and s is or even, we have that with probability 2.J exp( (ctfA)
() 2 of (mm-lAV)
if vm 2 JAVJ, where is an absolute constant.
Under Model E.1, with probability 1 - 2J exp( -eta)) we have that
{) 2 of taVV
(vm-tavJ)+
This computation allows to lower bound Ks the cases of Model 2.2 in Appendix F and Model 2.3 in Model B.
Proof of Theorem C.13. We will use Theorems 5.39 and 5.41 in Vershynin (2012). These theorems say that the rows of matrix either bounded a.s. tub-gaussian, then the singular values of this matrix upper and lower bounded. Note first that in both cases, A is PSD matrix, so it's sufficient to consider the singular values of A. In both cases, note that in order to apply the theorems from Vershynin (2012) to a matrix X, we need to have ( = I, i.c. the rows of X have to be isotropic random variables. Note that in both cases
Σ(A) Eg (ig,e))
19

---

Weak-to-Strong Generalization Even in Random Feature Networks, Provably
If we let Σ E(A), we can apply these theorems to Σー G, where G such that A G² In that case, the theorems say that with corresponding probabilities that
G) 2 (Vm cvJ (A)² .ソ G) 2 (vm - A Aan-AtAyyy vJ²;
respectively, where Ly is the J-th singular value matrix. Note that we have that
sJ 2 smn (E
Therefore, we get that with corresponding probabilities
AA 2 (Z) (s)(E>)))²
Here, we need lower bounds on m so that we can square the inequality and go from singular values to eigenvalues. In the case of Model 2.3, we have that
E(A); =.
Therefore, we have that A)(Σ)= As. Note that we are only left with verifying the conditions of the theorem. First is that the rows of Σー A are isotropic which is true by design. Second, need that the rows of Σ A are subgaussian with subgaussian constant Lg. Note note that if X N(0. o) then || S Co for some absolute constant C. Note also that
||alls = sup ||=Ta|l>. allv, I VO 2 S VOGCLL
af & V /C x² = VC =
C. Note that therefore under Model 2.3, the conditions of the Theorem 5.39 in (Vershynin, 2012) are satisfied, so we get that with probability - 2 exp((ctta)
Xx(A) 2 As (Vm-cvJ- CVJ
as long as v 2 evJ + LA. Here C = ( and c c= c ( + ) the sense that both C and are upper and lower bounded by an absolute constant times the appropriate expression of Lg.
In the case of Model 2.2, note that since the target Condition 6.1 will not have anything in the directions with zero dkk we can just ignore and reindex the basis functions. So, for now we will just write as they are nonzero, but we will keep in mind that we skip the zero dg. Therefore, we have that
E(A),, diag diag(o),
where each a, repeats with the multiplicity N; for ; = 1 or i even (otherwise it's 0). Furthermore, note that | = J, so we can indeed apply Theorem 5.41 from (Vershynin, 2012). Therefore, we have that with probability at least - 2J ea/exp(-44) (c()))
(A 2 d2 ttV
where c is an absolute constant.
D. Weak-to-Strong Bound Applied to the Case of Linear Networks
Proof of Theorem 3.2. Follows from Theorem D.5.
Proof of Theorem E.4. This follows directly from Proposition B.2 and the general bound Theorem D.I.
Theorem D.1 (Weak-to-Strone
Generalization with Gaussian Feature Distribution). Under Condition 6. I, if Model B. holds for some K, and if the teacher attains minimum loss LTB Lmin. then for the student trained until time T we have with probability at least 4 that
[ Ad) (EESH Xs) (logm)² m
LtE + As+1 T CTE ) } 2 22- --e 1|
~AXT
LST S inf S2K
Proof of Theorem D.I. This follows from Theorem 6.5 using Theorem D.4 and noting that we can replace As+1 ks) & As+IT2 T2.
20

---

Weak-to-Strong Generalization Even in Random Feature Networks, Provably
D.I. Proofs Related to The Case of Linear Networks
We first aim to show that the k-th moments of ||Y || =|ll=alllll/ are bounded.
Proposition D.2. Ler = Ei= X3 where X, are i..d. standard Gaussian. Then for 2
E (x*) S k!
A=
Proof. Expanding the expression for X (Ei=1 xf
and using linearity of expectation, we have that
((x*)
Σ
((a))) E ((x))at).
|a|=
Note that B(X? = (2a; 1)!! $ 2 (a;)),, so have that
E
((*))=
Σ k!
m7
((a.)))
E ((x7)
S Σ
k! m
II ((a:))) 2%
a!
|a k
a||=k
Σ
(2(a:)2)
k!
Σ
(2)
|a m
k!
k!
(2(a.)3)
|a|
where the last inequality is true because a! S kt. Note that Ejo== a IT (2(a,)²) = -EEm 2a²) k
so the final bound
E
(xx) S h! Σ II
(2(a))))
= Ak Σ 2
| k
This implies that || is bounded for all l: 2 2 with an expression of the required form.
Proposition D.3. Let g G with (x) (0,, A) with A diag( ()1, .2. Then for Y it holds that for all l: 2
(1(2)
J 2 7=1
2 Σ A )
(|Y1| I
2 A
imJ++
Therefore, this case we can take B v 2 >x) (2En dx) and I= ViEin I.
(2Er Xi).
Note that Proposition C.12 applies in this case as well. Additionally, Theorem C.13 applies in this case. Theorem D.4. Let g ~ G with (g. ex) ~ A), with A = diag(Ar A2........ Then with probability at least 1 28
2 2exp(-cx x7 (x) we have that
8m (ES >:) (2i-s41 2;) (log 2
|F As(A)2
\1 ((V Bslv As)+)
X3 (Vm-Cv5 ---C---- -ta) -ta)
21

---

Weak-to-Strong Generalization Even in Random Feature Networks, Provably
where e and C are absolute constants. Setting LA X2 log J/4 we have
1, m
δ1 m we get that with probability least 1
4 m
8m
EE dx) (E (Eis X1) m)
A1 ((VA)) + Bs(v (osAAsss)))))))
N9 ( CVS Xp loggm)
If additionally m w(S) and m = w((A) log m) then with probaility 1 1
Ei )1) (Ei-st1 de) (log m)
A1 As) Bs Bs( Bs(vAs)t) 8
m
Proof of Theorem D.4. This theorems follows directly by taking the approproate lower bound from Theorem C.13 and combining that with the Hilbert concentration bound Proposition C.12.
D.2. Additional Proofs for Linear Networks
Proof of Theorem 1.4. This follows from Theorem D.6 by taking e = 0.01, 6n = 0.01, m 2 O(a)-()) and 8 = 0.01.
Note that since m = d-1 we can turn this inequality into an inequality with and d, i.e a 2 O (()))) ). The last claim also follows from Theorem D.6, since m - oo the lower bound converges to 0.99 a and the probability 1.
Theorem D.5 (Weak-to-Strong Generalization with Linear Network). Consider Model 2.3 when f is supported by the first k coordinates, i.e. f 3x, where 3 0 i >> k and take f to be norm 1. Take V m is repeated is times and 1 is repeated (m))) om2 times, with mm for any [0, 3 (so d = k + Ni(m)). Then, for all m > CVT if the student is trained until time T log m loog Zte
(I...., m. ..... 1), where I
1 with probability at least 0.99.
m
LTE 2
1 b--
log² m m
1
LST S
LTE + m
(log m + log
Cre +
Lre m
Lre
So, for all m we have with probability least 0.99,
LST S ((kLTE))
In particular PGR 1 as MTE- - DC.
Proof of Theorem D.5. For k = 1 this follows from Theorem D.6. Consider is copies of Theorem D.6 with N(m) each, V m,....., L k. For example, Vm.1 (1, 0,......., O, 1 ...., m
x m² 1 O,..., 0). were we have N (m) = k repeating
(m
1. Note that a set of weights w E R" that the teacher chooses to optimize over all problems is worse than choosing mn
a separate set of weights for each of the problems, so the loss will be greater than the sum of the losses each of the subproblems. So LiTE is the loss in the i-th instance, we have that LTE 2 Σ, LTg. Let BY be the norm of f in the directions of the basis functions corrrepooning to the j-th subset of V Mm i.c. B² = Ei B.. Note that by the
normalization of 8", Σj= B²- = 1. Furthermore, note that our setup is scale homogeneous, i.e. we scale || by é then the loss will scale by e² as well. Therefore, we can apply Theorem D.6 to each of the A subprolems to get with probability at least 1 - 2exp(-111 [am?) 2 2 mm)m)) (m
that
StP 2 B3 0.99
2m 1/2tem
2 0.98
k +1
Therefore, we have that CrE 2 Σ/ 0.983?
0.98
'here C is an absolute constant given by Theorem D.4
22

---

Weak-to-Strong Generalization Even in Random Feature Networks, Provably
Now consider Theorem D.1 in this case. Set S k. Then get for d7 1. TTE the upper bound since the sums of 1h; EE 4: = k and Ei=44 d cm com respectvvely with probability at least - 100 m - 2 exp(-c1mm
1
1
LST I 40ka log mLre + (log m + log
) LTE + LTE
LTe
where the constant 40 comes from the constant 8 from the upper bound and the constant from log 1/ by setting ò = 100m... Note now that since LTE is lower bounded by m- 2k
we can combine log 1 and log m terms into
Lte
log² m m LTE-
LSt S 50k
Here bounded (log m + log 2k)² < log This exactly gives with probability at least 1 2 eep((= ((0(--((mmm)))) 2 eexp(-11 m
10 . 2 -2exp(-cmm
LST S ((:
By setting ea $ and cm E. get that by union bound over all with probability at least 0.99 for all m
LST S ((kLTE))
In Theorem D.6 we will establish a case where we can provably lower bound the teacher loss.
Theorem D.6 (Lower bound for Teacher Loss). Condition 6.1 take f = 61 and in Model 2.3 take (g, es) ~ NO, Am). n., where m repeated ((m) times. If N (m) am2 then for all Ca, Cm E 10, where An diag(1, m m (am)(_)(am)
with probability 1 exxp(-1 (am) - eexp(- m we have LtE 2 0.99 + 2m +tem - (am)- -
Furthermore, as long as am (log 1)²² = (2m-2+e.) for some c. > 0. 1 - - 2 2exp(-cmmm we have that Lst & 8am(log())) Cre (1
Lemma D.7. Let Gij- = Ei es). let H (9i, eu) E gradd and let (gj,e1)
(0, (mm be
j=1
the rows of H, i.e. = Imm- Then with probability at least 2 expp(- 46a for all R vd Go 2 (1 - -8))r(A)e*
Proof of Lemma D.7. Note that G = H so have that T Go
| [H Note further that
H
Σm Em es eg)
N(O, ((
since the entries Em Vs (gg eÿ) are independent and each has variance $1
Note now that
2 ( eg)) ) ~ 2111013 (2) + +7))
m
|
e (0s,
where Z, ~ N(0, 1) are iid, i.c.
|
2 w | f x where xa. By concentation of x3 distribution, we have that
with probability at least - 2 exp( d5²
that
TG
T z (1
5) (1 8)tr(A)e²
23

---

Weak-to-Strong Generalization Even in Random Feature Networks, Provably Proof of Theorem D.6. Let f be the teacher predictor. Note that can rewrite this as
)
(E
m2
ED ( ffu) ED ei(z)² 1 1- 1 wy (gy,, (ussene))
+ ED
Σ
w
Σ
L9 1g es)e((())
2
1 2
Wy (ggi e1) +
Σ wy (g) (g.. e1)
+ ED
Σ2
Σ
wy
wy
(و) e()e((())
= 1 - 2 Σ
my my G1) +
Σ wy (g) 61)
+
Σ
Ep
Σ
wy (gg,
j=l
im2
2
m Σ
m
8
m
Wy (gj
Σ
wi (g5 61) 21)
>
W (ggs Ci)
j=1
:
(a) ea) and g= Let [G Eiszlgi =l (gg,
(g),es) e1)
5=1
Now, we can rewrite the above equation as follows.
2
C(fwx = 2 Σ
wy e1) Σ
wy (erree)))
+
Σ
Σ
wy (وg Ei)
j=1
2=2
= =1 2w=" g + (w g)² w" Gw.
By Lemma D.7, we have that with probability least 1 2exp(- d8a
4 that
Gw (1 (1- (1-8)tr(A)w=) w,
where d = (m). Therefore, we have that
[(fw) = 1 - -2 g + (wF + wx Gw 2 1 - -2 g + (wF + (1 -5)tr(A)um
The last expression minimized for w so it concetrates around m, i.e with probability least 2 expp 82
9. Note that we have (r(A) arn. Note further that ||g|] X2
9 (1))(())
we have
(1 + mm > || 2 (1
8mmm.
So overall, we have that with probability at least - 2eexp(
dd2
exp( 4
m252
2
1
[(fw) 2
+11 (1-o)tr(A)
||g/13
|1112 + (1 8)(
[1g + (1 (8)))(()))
m1 + 5m)
2
+ 8)a
(1 5mm)
m(1 + 5m) + (1 - 8)am
(1 + 8m + (11 8)
8)a
26,m.
+ 6m + (1 8)a + 5m + (1 - 8)a*
24

---

Weak-to-Strong Generalization Even in Random Feature Networks, Provably
Theorem D.4 in this case says that for J 1 have with probability - 8 2 2exp(-ccnm
1
(m)) (log( 1)² 8am((og( ( ()
())
m
Therefore T'eeormm 6.5 implies that with probability at least 1 - 8 2 eexp( -cmmm) with = log( bz)
CST & 8amm(log(] ())) ()9 + m²
1 (log(
1)> + b7 11.
dt
2 2-07 67
For 8x ne Cre, i.e. for stopping time T 2 2log log fTE
2log* m + log" fTE m² am emm((oo))) 2)
ESt S Sam(log( ;) 3))
1+
As long am (log 1)²² 22( for some 0 this can be simplified to
CST S Barm(log( () Lte (1 O( (m))
Note that we can simplify the lower bound for LTE, i.e we have that with probabilit at least -2expp ((=-)
d62 ) -2exp(
CTE 2 1 pm da
26m Sa.
1 2 8m 5a, this can be further simplified to As long as 100
a
Cre 2 0.99
1 1 26m Sa.
Therefore, taking 8 2 2exp(- exp(-}mm") that
d=- and 8m
we have that with probability at least 1 - 2exp(- {
m2
Cre 2 0.99 a
1+a 2m 1 - -(am²) (oom²)-1+e - ttaaa.
E. Weak-to-Strong Improvement in Random Feature Networks.
In this section, we provide detailed versions of Theorems 3.1 and 3.2, namely Corollary E.3 and Theorem E.4, respectively. Further, show that the result for ReLU networks can be generalized to any activation function.
2-layer Network with Arbitrary Activation Function Further, we show that the result for ReLU Model 2.2 generalizes to 2-layer network with features drawn uniformly and any activation function, which we define in Model E.
Model E.1 (2-layer Network). Consider a 2-layer network with an activation function that is bounded on [-1, 1]. Let the distribution D be u, Uni Let {or 1oc be the nonzero coefficients of the activation function a ((x t)) in the basis of spherical harmonics, i.e. ((x t)) = Ei, o; (x:)i.(()));;) (s, (t), where the sum goes over only the nonzero d,. Here Φi is the i-th spherical harmonic of order ls and is also the eigenbasis of the induced kernel (Equation (8))"*
Uni The first layer parameters u, initialized randomly isotropically, i.e.
Theorem E.2 (Weak-to-Strong Generalization with 2-layer NN). Under Model E.1, let Condition 6.1 be satisfied for groundturth f" population kernel K. (Equation (8)) and positive integer K. If MTF. K and the teacher allains the minimum loss (Condition 2.1), then for any dT E (0, 1) and the student trained to stopping time T = + log with MrE.) over the randomness of teacher features, it holds that
ox
probability least 2
K Kexp(-
MIE
14E5 0 af) log² MTF
os+1 (lo dr CTE / LIE +
8T
Est S inf 82K
+
|
MsM
ok
2-8y 8y
For the proof of this theorem see Appendix F.
"TThe existence of such decomposition follows from the Funk-Hecke formula
25

---

Weak-to-Strong Generalization Even in Random Feature Networks, Provably
2-layer ReLU Networks. As corollary, have the bound for ReLU networks. For ReLU activation in Model 2.2, the expansion of in the basis of spherical harmonics ΦR,i will be (01,.... 01; .2...., 02,...) where each ds repeats Nk- (2k-d -2(kkdd-3))) times, which is the order the k-th spherical harmonics in d dimensions. Furthermore, σg is kl(d-2)1 nonzero only for even k and & = 1. Therefore, Condition 6.1 in this case amounts to f being sum of linear functions and an even polynomial of order at most k, where K = No +... ...... Nu.
Corollary E.3 (Weak-to-Strong Generalization with 2-layer ReLU NN). Under Model 2.2, let Condition 6.1 be satisfied for f for some K and let k be the corresponding degree. If the teacher attains minimum loss LTE Lmin. then the student trained to early stopping time of
log by
will have with probability least MrTR
K exp( - Mrz K
EST S Od VTTTE
(log MTT)²) LTE + Oa
1 41) 0k (.Tr) (l08
1 δT
LTE +
ôT || 1
2 d7
Here e is an absolute constant.
For the proof of this theorem see Appendix F.1.
Linear Networks Finally, we can state the general bound for linear networks, Model 2.3.
Theorem E.4 (Weak-to-Shee So-tong Generalization in Linear Networks). For Model 2.3, if f spanned by the first K coordinates and the teacher attains minimum loss LTF Lmin. then for the student trained until time T we have with that
probability at least 7
E V:) (E) vi) (logm)² Cte + 1s41 T LTE I
e e
LST S inf 82k
2 e- ||
23
For the proof, see Appendix D.
F. Weak-to-Strong Bound Applied to the Case of 2-layer NN
This section deals with the cases of Model 2.2 and Model E.1.
Proof of Theorem 3.1. In Theorem F.2, if we select 87 VMTu
1 LTE, then with stopping time T = 2ेf (log MTF +log ZTz
have that with probability 1 MrE K
LST S Oa,
(log MTE))) CTE
VMTE
+ Oa.x o VMTB
(log MTE log LTR)² LTE + VMTE CrEIlS*133
This will hold if MTE/ log MTE > K N₂ +... No so it suffices to have MTE 2 (No + ..... + 22) For our setup, this is (No + +...4 22)² ((d2)).
From this have that
(log MIE)*) CTE
LSt Ouk
VMTE
1 Cte
+ Oa.
(log² MTE + log² CTE) CtE +
VMTE
VMTF
where we used the fact that the target is nomalized. Note now that from Lemma F.8, we have that d can be absorbed into the OUR So we have that
1
(log MIT)*) CTE
LST < Oa,
VMTE
Oa.k
log² CrELTE.
/MTE
26

---

Weak-to-Strong Generalization Even in Random Feature Networks, Provably
This can be written
log"
MTE + log" Lte
ESt S Od,
LTE
VMTE
Now, to get the right exponent, need sharp lower bound on LTE. We can get that under the Gaussian Universality Ansatz. Under Gaussian Universality Ansatz, the teacher's test risk Lre behaves like the deterministic equivalent Equation (20). Therefore, Theorem D.6 applies, which tells us that
LTE 2 O (MTE 2 [1
In other words, MTØ & Oa (F,((
Note that under Gaussian Universality, since LTF lower bounded polyonomially in MTE, we can absorb log' LTF into log" MTg. Therefore, we get
(VITE (log MIE)²) CTE.
CST S Od.k
<TTTE
So we have that
log" MTE
CST S Od,k
LTe S (LE
Ōd,
/ MMTE
Since can take to be close to that here is the number of nonzero d up index k, so by Corollary F.9, it of order O(d*). since an absolute constant, for MrE (dd2),, K exp(-c
d+2 for d > 200 we will have this be 1.02 so the final exponent is 1.49. Finally, note 2-2
and otherwise we can have the constant in Od,
MTE
Proof of Theorem E.2. This is given by Theorem F.1 for tA /V Mre. Note that since MTE 2 K, Condition 6.3 holds with probability one.
Theorem F.1 (Master Bound for Weak-to- Stronn Generalization with 2-layer NN). Under Model 2.2, if Condition 6.1 satisfied for I and K. If / 2 LA V and the teacher attains minimum loss LTF. Liins then the student trained to will have with probability at least 25 2K exp(-ct3)
early stopping time T log
k by
EST S inf S2K
D 9 1=
log Cre + ( m tAVK)²
J (log 8r ) of
5T CrE + 2 or
|| 1
Proof of Theorem F.l. Follows directly by instantiating Theorem 6.5 with the lower bound on Ks given by Theorem F.4 and the lower bound (A) given by Theorem C.13. Finally, we just choose T log bx
F1. Weak-to-Strong Bound Applied to the Case of 2-layer ReLU
Proof of Corollary E.3. This is given by Theorem F.2.
Theorem F2 (Weak-to-Streel Strong Generalization with 2-layer ReLU NN). Under Model 2.2, if Condition 6.1 is satisfied for f and K, let l be the unique number such that No + ..... Nk-1 + 1 K & Ny +... Ng. If MTE/ log MrE 2 K and the teacher attains minimum loss LrE = Lmin then the student trained to early stopping time T oz by with probability at least
log 1 will have
2 MTE
K exp(pcc MrE)
(log MIE)2) LIe
LSt S Od,
VMTE
1
1 (108 3r)
CrE + 8r
+ Oa,
|| 1 87
ox VMTF
Here e is an absolute constant.
27

---

Weak-to-Strong Generalization Even in Random Feature Networks, Provably
Proof of Theorem F.2. We will apply Theorem F.1. Note that the eigenvalues of the activation functions in this case oh and note that for odd k > 1, we have 0% O. Note that can just ignore the zero eigenvalues. So in this case, os will actually be equal to and 0541 to aa+2 if we select S No +.... No. Take from Proposition F.3, Then the proposition says that we have
m m k= Na) N.) (log 4)²
mym (log 4)²
Sta
vm -tavta tAVK)
(VV tAVK)
0 ok
1
2
1
1 log
) 8T
1 12 T
log
S
Od
bT
vm of
Therefore, from Theorem F.1, have that with probability least
26 2K exp(-
mym (log 4 (vm-LaVR) -LAK))))
LSt - Oa
LTE
log 81 )1)
)
2
(ogg 81 ) LrE +
1
dr
+ θ
11
vm of
2 2-
81
Take 5 = and take la m therefore with probability at least 1
2VK that vm LAVK vm/2. Then 2K exp( (xp(-cl33)
if
2 K. Note that
m
m
log m
we have
LST S 0a
1 VMTT
(log MTTE²) LTE
llgg 1 )
2
LrE + 87 2- 8T
+ 0
||
k VMTB
81
which completes the proof.
F.2 Proofs Related 2-layer NN Proposition F.3 (Optimal choice of 8). We can lake mm 47 + (1)(1) (s is closest even integer to m ma so that
K= Nb k NfN)) (log 4)2
mm/ (log 4)²
S Aa
0f (Vm- tAVK)
(vm- - tAvK)
م2 ot
1
2
1
1 log
T 2 1=
log
Ad
8T
vm o
8T
Note that this θ hides absolute constants and d dependence.
Proof. Note that for A > d we have that N₂ O(Ad-2). This follows directly from the closed form N₂. (2k+d 10k+d22)(b+d) 2))k+333) Furthermore, by Lemma F.8, we have that of ((kk-(++) for even > Furthermore, klld-2 2)
Ee of N₂- = (1). So, we have that
m O o (log 1)² 1 m1(1)² (log 1
!f (vm-
(mm-avk)
Therefore, taking m शाक + (1), where om (1) is taken so that s is the closest integer to m 2,5े25, Then since o? = (ss (d+2)), we have that of = (t) so ot O ((mm) Note that 0242 = O((m 400-2) + +2)-()+)) = 0(m -4). Therefore o:42 +(-)))
28

---

Weak-to-Strong Generalization Even in Random Feature Networks, Provably
Theorem F.4. Under Model 2.2, if Condition 6. I is satisfied for S and K, let be such that No +... No-1+15
No
+ Ns. Then with probability at least 20 2K -cp(-
FAlla AA
m( K- No) NENx) (log 2)
- A1 (sA
KS
o. (Vm-tav)
where c is an absolute constant and ā E (0,1). For $ 2 then withe probability at least 25 2K exp( (xp(-ct)))
mI (log 4)² of (vm
X1 (((AAs) + Bs Bs( (s(vAs)*)
(vm-tavK) (mmK 4'
Proof. The first bound follows from Theorem C.13 applied to (A( and Proposition C.12 applied with Corollary F.7. This gives that with probability at least 25 2K exp(- -c)
|FLFAI li
m oZ No.)) (log 2)²
X1 ((VAs)) Bs As)+)=
As)
(A)²
of (tm (emm-ttVi -tAVA)
The second bound follows by noting that > Nf, =0( (() = o(().
In this case, the basis of eigenfunctions can be taken to the spherical harmonics (1 where Φk., is the i-th spherical harmonic of order in d dimensions and N₂- (2R+d-211+td-3 is the dimensionality of spherical harmonics of order & in d dimensions.
kl(d22]
Proposition F.S (Figendecompositionn of the kemne induced by random features in the case of 2-layer NN). Under Model 2.2, the kernel induced by the random features is given by
K(æ, x²)
of (a))(())) (xx)))
Here, Φu :R. Ne is vector of spherical harmonics of order k in d dimension, No. (2k-d-2)(k-) 22k2)k4 3)! k-th term in the decomposition of the ReLU functions a to the basis of {Φx 100
and a is the
k!(d 2
We provide the estimates for the size of σ Appendix F.3.
Finally, we find B and L in the spherical case.
Proposition F.6. Under Model 2.2, Jf J = No + N1 + ... + N₂ then
Ni
A=1
|P2
Σ Nr.
k=s+1
So L=
Ei NfNa) oi
(Eestto
Proof. We have that
PsJg ( (z(x)
|Psug113
axdi (w) (z) Σ (
( (ox( ((()) d1()))
km Im1
29

---

Weak-to-Strong Generalization Even in Random Feature Networks, Provably
Now since (x(w)) )x))) ΣE= ok.5 (w) (x) (w) (x) remain. For these, we have that Ep we have that
Ne Pk. (w) (x) and since (dv,) are orthogonal w.r. D, only the terms of the form
(w)),, = Φk (w) 1. So
PPssg
xk 2
( (l)w)))xx()))))))))))))))))))))) (x(x))
Σ pRo k=1
Lo
k=1
The last step holds because dx (ww) (w)) = N&Pk((W, (()()w,)))))))))))))))))) N&P = No.
The same argument shows that P = 2k=st1 og.N..
Corollary F.7. Under Model 2.2, if No + .... No-1 + 11 No + +... + N₂ then
L= B =
ok N Nz)
k=1
k=
This simplifies to L= =B ((2)) +
Proof. Note that Jf No + N1 + N + p for some I S N₂ then we have that
|P Σ No +po
|P2441913 = (N₂ p)o + Σ No.
k=st1
E3. Computation of the Kernel Eigenvalues for the case 2-layer NN
Proof. of Proposition F5:: For ReLU activation, we can do the following decomposition:
a(w,, x)) Σ NgoxPa.(((u, = Σ ( (x))
Here 0% is given by
S σk S
sPr.d(s)(1 (5)(11-s)++ + ds.
Combining this with 1
2/d/2 T(T)
we have
r(
sPr,a(s)(1 -
-2) 52) ds.
The eigendecomposition of the kernel in this case is given by
()) K(x,, x²) Ew (o((w, x) ()) x')] Ew
Σ
Σ (l()(())
A20
R20
30

---

Weak-to-Strong Generalization Even in Random Feature Networks, Provably
Now, we find the size of ke-
Lemma F8 (Size of σ²). Depending on the size of d and k, the following holds for the size of coefficients of ReLU activation r(() in the basis of Legendre polynomials ok | 2 (3+ for even k, 2d and d 0 for odd k 1. Asymptotically, this means
1. .2xd Od 01
2. 1f k: =1),, then for even k, 0% = O(d )
3. kf >> d, for even k, o = ( _ -2). )).
Proof. The third case is shown in (Petrini et al., 2022). To prove the general claim, we use the formula derived in (Petrini et al., 2022)
ak r(#)
(((2))) 2 -
dk= dtk (1 p)
(πI(d=1) [ + 21)
Note that all terms will be multiplied by (1 - 22) which is 0 at & = 1, so we only need to consider t = 0. Note that if a term has a nonzero power of t, will be evaluated to O. When taking j-th (j - k 2) derivative of the expression above, all the terms will be in the form of (1 =2) ts times some constant that depends on d for some integers 1 and s. So if out of l - 2 derivatives we take a on the term with (1 (--() (²) and k 2 - on 1a (note that the ordering doesn't 't matter as we only add constants), in order to have term with no at the end, we need to have k: a = 8, but & = a so we have that
k=2, Therefore, the evaluated derivate equals exactly
a 2
dtk (1
d
2
d-3 k+ 2 = k +
k
2 - -1)+
d 3
= 1:
d-3
+4 - 3
+
2
2
2
2
2
r(
Note that
therefore can compute that
r(k+ -2)
(k-1+ _ )...
r(
d-3)
k:
+4
4
d-3
Ok 2* VTI d-1
(k- 1+ d
1 k
2
2
+
2
[(5)
0k V d=11
2
( +
ا=1 d-1
r(d)
Th
| 1-1
2 (k +
1)((k- 2) + 1)((k 4) d 1) 1.....222 (2+d 1)
2
So, when k- = +(1) we have that this is on = e - ) = O(d k+1 since the first term is
v O(d)).
r(g)
Corollary F9 (Size of of Ng). The following bound holds for No for even or k 11fk d then of O(k-*), If l < d then N ((d If is odd, then Nf 0.
Proof. We have for N N& that
r(()
(d- 1) (d) (2k + 2)
N
4
V
d-1
(k + d 10--13 (0-...dd1+2)4// 1)2
((
2
(2k + d 2) (d-1+1)d--1+)) (d 1+1
1
V d-1
1)ddd1+2)... (d 2) (d 1 k)²²
2
31

---

Weak-to-Strong Generalization Even in Random Feature Networks, Provably
When & < d, we can just count the terms with in the numerator and denominator and note that r(
(d).
(xr(
For > we just need to count the terms with & in the numerator and denominator, The results follow.
G. Bootstrapping
natural question to ask is whether extending the weak-to-strong setup described Scction 2 to use a chain of students can help break the limitations of Corollary 4.4. That is, training a teacher on the target, the first student on the teacher, the second student on the first student, and so on bootstraped game of "telephone", then finally asking if the final student can be much better than the teacher. The lower bound of Theorem 4.3 and Corollary 4.4 do not apply here as-is, because shrink-optimaliyy is not transitive. That is, if f2 is shrink-optimal w.r.t. fi, and fi is shrin-optimal w.r.t. freccher this does not imply f2 is shrink-optimal w.r.t. fleacher. Instead, we provide slightly weaker lower bound against more general proprety, which is transitive:
Theorem G.1 (Limitation Weak-to- Strong Generalization with a Bounded Student). If the target f is normalized, BE=D((( (x=))² 1, then for any teacher Suncher ceriinkinn-optimae w.r.t I and any student s 8.1. Ee [Sttutenc (2)) (2) S
Eg [Seucher [ we have that
1 LST (1- 11-v1- LrE fiE
It is easy to verify that the shrink optimality implies E, [f()))] < EE [ (x) and the transitivity of the inequality now implies:
Corollary G.2 (Limitation of Weak-to-Strong Generalization with Bootstrapping). If the target f is normalized, (=)))) = 1, then for any teacher Swetter shrinking-optimet w.rl. S and any chain of student S g(8++1)
f(i)) studenn we have that for all 2 0.2..... . 0o, where f(i) student freacher and studena shrinking ootiinagg--mmaallooee w.r..
LST, 2 (1- 1--EI-LTE
LTE
2 2 4
CTE
where LST, is the test loss of the n-th student. In particular, this includes the case where the student ( is trained by gradient flow w.r.t Siattn for arbitrary stopping time T, and using arbitrarily (random or determmistic) features.
For the proof of Theorem G.1 and Corollary G.2 see Appendix H.
H. Proofs of Limitation of Weak-to-Strong Generalization
Proof of Corollary 4.4. This follows from Theorem 4.3 by noting that from Lemma 4.2 the teacher satisfies Definition 4.1 with respect to the target and the student satisfies Definition 4.1 with respect to the teacher.
Proof of Lemma 4.2. We rewrite the claim of Lemma 4.2 as follows.
Lemma H.1 (Shrinkage Optimality of Gradient Flow Solutions). For any positive semi-definite kernel K,, time > O, and ground truth f*, the gradient flow solution fr T is shrinkage optimal with respect f the sense of Definition 4.1.
From Equation (9), the gradient flow solution is fr E1 ( eL)DER- For shrinkage optimality, need to show that minimizes Ex((afr(x) - (*(x)) for Sasl.
32

---

Weak-to-Strong Generalization Even in Random Feature Networks, Provably
Expanding this expression in the eigenbasis:
Ex - (xx)))
11 ( ((fee)
(18)
121
R21
(a(1- e ) -
1) ( cx))D
(19)
121
The proof is immediate by noting that 1- e A.T 0 and a(1 E- > s 1 for all k and 0 S a
Proof of Theorem 4.3. The proof a straightforward geometric argument in the function space. Note first that Definition 4.1 gives restiction of where the teacher predictor fuacher can be in the function space with respect the target f and the origin. Note that [eecher I1 < |ea/hencher 1 for all 0 S a S holds if and only if (Jreacher, freacher f S 0. Similarlry, Definition 4.1 holds if and only if (ffsnddets fieacher - fstutem? S 0. This implies that the teacher predictor fienchr is inside the set feacher E {f Il 2 I| I fllff11>) Similarly, have that faudem {f |l Imnate 1l I 2 fuachee || }. Both of these sets are spheres in the function space w.r.t. D-norm. Let 3 2 1 be such that feecher = 3 fracher and such that (Siencher, 1 fteaheer) Then we have that
LTE = 1 - 8² feescer (3 - f tencher - (2 - 1) 1)
f
Let /stutent the predictor inside the student set with the smallest risk, i.e. on the intersection of the line connecting I' and f and the boundary of the allowed student set. Note then that
-115
Trencher
feacher 2
D
1D
Note further that
feaacher
1 )
|1
1 - 18 SPecceer
+ (B
/ =1 1- 13- -
D
2
Therefore, have that
1 LrE 23
f
Jeacher
From this we get that
(v 1V1-
1.
1 1 LTE
1
LTE
C( [(Faudeat)
(3
23 -
2
23 1
8,3 4 (V48 - (48 - 1)LTE V LTF
Note that for 8 2 1 and LTF < 1 we have that
2
L( L(Famdoo))
(V8 (48 1)LTE V1 LTE
83 - 4
1 - - -3C
2
2 1 + LTE
The last inequality holds by noticiting that the function is increasing in B, so it is minimized for 3 1 for 0 < LTF < 1.
That is, since LsT 2 [(fandea)) by design, we have that
1 ( 1 LTE 1- 2LTE -3
3
LST 2
C
4
The last inequality? / LTE v1 11TE 3CTFE
2 Lie holds for 0 S LTF. 5 1.
33

---

Weak-to-Strong Generalization Even in Random Feature Networks, Provably
Proof of Theorem G.I. The proof is similar to the proof of Theorem 4.3. Similarly, we have that the teacher predictor is
bounded the set Sieacher (ʃ [ 1 Ilo S [l The student predictor is in this case bounded to the set fsudee
(S II S (eecherr p. Let 3 = (ʃ" fteacher, f*) Note that from the condition Siescher E I - - Il S 2 l|
we have that (fraachers f freacher) S 0 which implies that there 2 for which we have (3 fteacher: f frencher) Note that LTE = I| freacher 12.. Therefore, we have that since || =
LTE 1 88 Peaccher (3 1)2
leacher 2
(2/ fuucherr
This implies that
1- LTE 2 - 1
Reacher
Note that
LST 2 (I]/"|| - -IJeecchrr (1
/eacher 1)
by the same argument as in Theorem 4.3. Therefore, we have that
1 Cte
EST 2 11-1
2
Note that
V L-LTE is positive and increasing in B, so the above lower bound is minimized for 3 1. Therefore 23-1
V
ESt 2 (1- V1 V1-CTE) = LTE 2/1 LTE 2 fie
2
Proof of Corollary G.2. The proof is immediate from Theorem G. and the fact that the student p is shrinking-optime
w.r.t. ((3-1) implies that || S I Il.stteetll... which further implies that (| Suddd
ll S /raccee I|
Deterministic Equivalent of the Teacher Error
Let [(f", .m) be the deterministic equivalent of the test risk of our model with random features trained on population loss with target f". Let sx be the eigenvalues of the activation function, i.e. the decompositon of the activation function in the eigenbasis [e Let 8" be the coefficients of the target f in the eigenbasis, f" Eiz B ec. To write down a closed form of [(f*, m). we introduce the following notation S and
S diag ($1 S2....)
tr (S(($+
That is, v is the unique solution to this equation. According to Corollary 3.5 in Defilippis et al. (2024), the deterministic equivalent of test risk has the following closed form then
E(f" m) = 1 (S+
(20)
I.1. Lower Bound for Teacher Error
We show a lower bound on the deterministic equivalent of test risk of a Random Feature Model with m features that we consider in our setup. Under the Gaussian Universality Ansatz, the true test error of the teacher's predictor Ltg will behave like its deterministic equivalent.
Theorem I.1 (Lower bound for the Error of a 2-layer random feature ReLU), If f satisfies Condition 6.1 for Model 2.3 with K such that for some k. Ng +... Ng-1+t + < K < N₂ + ..... + Nr. then for fixed d there exists o > d-2
4+2 such that
for the deterministic equivalent of the test risk we have
[(S (,',m) m) 2 1
-f (11(=111)))
ma
We can take d-2 + oa(1).
34

---

Weak-to-Strong Generalization Even in Random Feature Networks, Provably
Proof of Theorrm I.I. Note that the eigenvalues of the activation function are of with multiplicity No. We want to lower bound Assume that for large m, I ma. Note that we have the following two things for > d,
0² - (1 ) and N. ((sa-3).
The first follows from Lemma F.8 and the second one follows immediately from the closed form of N₂. Note that in this case we have that S; of. Note that then for of V we have that
o² 0.+ン 1 Note that if m then we have that
for all 8 < m पîž that o > v. Note that there is at least N those, where smax the largest such 8. We have that mmax 2 m But we have that N samax
2-2
O
2+2
Note also that with this choice of mmax
20
1 N Namux
m = (((((++))))
(mm" 242)
8j +
2,1 +
2
where T... g.
So if a
d+2 2-2
+ (1) then we have a contradiction. Therefore // 2
1
for this
d+2
+ oa(l). Plugging this back in d-2
ma
we have
N
E(f", = v
3+2 ig
18.
0
2
+
2
o
773
For the last inequality, note first that 0; 51
Also note that
0
81
i=
St
m
+
V
i=1
80 V < 2 Note that since E. N. = o(1) = we have that E 11=1 = 1. Therefore, it holds that v < L. This finishes the proof.
1.2. ReLU Network Error Upper Bound
Theorem 1.2 (Upper Bound on Teacher Error with ReLU Network). If 1 is spanned by the spherical harmonics of order that is even and at mos or 1, for Model 2.2 in fixed dimension d, we have the following bound on the deterministic equivalent of the test risk
E(S" m) 5
(+ 11
m
Proof of Theorem 1.2. Note that
00
oc
m = tr((S + -)-
S
2i==
88
8i
+
V
V
so we have V < Σn 21 Since E 8; = o(1) = 1, we have that harmonics of order at most k
Then we have that since f spanned by
x Σ
m( =
2-2
v
Σ
Σ
3
3
o + 11.
V
07 +
1=1
1=1
1=1
1=1
Finally, note that of = Od (k+1)) so we have
240 ((d(+)))
Remark L.3. The same proof shows that in the Gaussian Features Model B.1 if the covairance structure is fixed we cannot have a ((1)-error asymptotic for any function that learnable by the model as MTE - oc in fixed dimension.
35

---

Weak-to-Strong Generalization Even in Random Feature Networks, Provably
-errrr asymptoties Theorem 3.2 shows quadratic gap between the student and teacher errors, but both vanish as the model size MrE increases. Perhaps
interesting and relevant scaling it proportional scaling where with larger model sizes can handle increasingly more complex problems while still ensuring bounded error. A more variant of the seperation result shows that for any asymptotic enror, we can have quadratic enror gap even model size and dimensinoality jointly increase:
Theorem I,4 (o(1)- asymptotics for Linear Networks), For any >> 0 there exists da E N such that for all d >> da Model 2.3 with f* Iı, La (1,
--1 and MTE
probability at least 0.99 have
LTE > 0.98 and LSt S 100
1 1 +
The proof can be found in Appendix D.2.
J. Experiment Details
In this section, provide experiment details for simulating weak-to-strong generalization for both 2-1ayer ReLU networks (Figure 2) and linear networks (Figure 3). All experiments are conducted on one H100 GPU, and are finished within 24 GPU hours.
To avoid the effect of randomness, experiments are repeated 5 times with different random seeds, 95% confidence intervals are shown Figure 2(a) and Figure 3(a).
For curve fitting in Figure 2(b) and Figure 3(b), we use numpy. pollyii with degree 1 after taking the log of teacher loss Lie and student loss Lsr.
For linear network, we simulate the limit case where student size MST oc. The simulation follows Equation (9) with A1 = L, A = (d - 1--1))-2 1)-2/3 for i >> 1. Note this method is not viable for 2-layer ReLU network because A is long-tailed for 2-layer ReLU network. Therefore, we set Mşr = 16384 Figure 2.
K. Additional Experimental Results
K.1. 2-Layer ReLU Network Experiments
Figure shows full experimental results for Model 2.2. It additionally includes d 16 and 64 compared Figure 2. We observe that when d = 64, the student loss LST is polynomially smaller than the teacher loss LTE. with higher estimated exponent compared to d = 32. When d = 16, the curve suggests a sudden change of optimal early stopping time, which we believe is caused by lack of student size MST-
However, due to GPU memory limit, we are not able to increase Mgr. Thus we conduct ablation study with smaller MsT to investigate the impact of Msr. In Figure we compare the loss ratio curve between MST = 8192 and MST 16384. We observe larger gap between the two when teacher loss LTe smaller, i.e., for small and large MTE. Therefore, is hard to believe that LsT @({?g) for this setting well. We leave it future work.
K.2. Linear ReLU Network Experiments
Figure shows full experimental results for Model 2.3. It shows the same conclusions Figure 3, but with A 10 and 100. providing additional verification of Theorem 3.2.
36

---

Weak-to-Strong Generalization Even in Random Feature Networks, Provably
10
MrE
M
M TE
16
32
32
LT
104
Csr/ Lm
LST LE
64
128
128
10a
10a
256
100
10-1
10-1
107
10a
10a
10
10a
101
10a
10a
10a
t.
1.
(a) CST LTE v.s. d = 16
(b) LST / LTT t at d
32
(c) CST Lre v.s. at d = 64
0.5
MYE
Mye
1.0
M n8
0.4
32
0.8
32
64
64
64
0.3
0.2
256
256
256
102
O.78C
LST
18
9T
0.2
0.0
0.2
0.6
CTE
LTE.
LTE
(d) LST v.s. LTE d
(e) LST v.s. LTE at
(I) LsT v.s. LrE d 64
Figure Weak-to-strone generalization happens in 2-layer ReLU networks with input dimension d = 16, 32, 64, student size MST
16384, and teacher size MIE {16,... 256}. We consider target function f be linear function, i.c., f (3, x) for some of unit norm. The top figures plots the ratio between student loss Lst and teacher loss Cre, with varying MTE and gradient flow training time t. In bottom figures, fit student loss Lst power law function of LrR. The empirical observations align with Theorem 3.1.
102
Mys
Mrx
Mxs
10
16
32
32
32
LTE
101
Can// Cig
LsT/ LTE
64
128
128
109
256
10
8192
8192
16384
16384
1634
10:1
162
10>
104
102
10P
104
10'
10R
10a
t
1.
(a) MsT 8192, d
16
(b) MsT 8192, = 32
(c) MgT = 8192, d = 64
Figure 5. Abalation of weak-to- generalization in 2-layer ReLU networks. We same setting Figure 4 and compare the results with smaller student size Msr.
37

---

Weak-to-Strong Generalization Even in Random Feature Networks, Provably
Mfz
MTE
MYR
10a
18
16
10
64
64
206
250
4059
1694
Csn/C
Csn 1gg
102
1020
10a
10a
109
10
10a
10
10a
102
10
(a) LST / CTB L
(b) LST/ C & & 10
(c) LST/Lis at 100
Figure 6. Weak-to-Strone ttrotoo generalization happens in antitropic random linear feature networks (Model 2.3). Here we used an input distribution in Theorem 3.2, with & 10, 100 and target function f (3,x) where / is unit norm vector with non-zero values for first coordinates. The figures the ratio between the student loss Lst and squared teacher loss Lig, with varying teacher size MTE, where the dimensionality early stopping time CST/Cte converges approximately MrE grows, confirming that for large MrE have Lst Lire in Theorem 3.2.
M2/2 + as set as in the scaling of Thcorem 3.2, as a function of the gradient flow time t. With proper
38


Reviews:
[{"review_id": "BVZiJZJ284", "reviewer": "Reviewer_2RDe", "summary": "The paper analyzes how weak-to-strong generalization can emerge in random feature models when the student model is trained using gradient descent with early stopping. It demonstrates that the student model can significantly outperform the teacher model, with the student’s error being much smaller, even to the extent of being a power of the teacher’s error.\n\nFor two-layer ReLU networks, the study shows that the gap between the student and teacher models can be arbitrarily large, meaning the student can have a much smaller error than the teacher. Specifically, the student’s performance can be arbitrarily better by a large factor, and the Performance Gap Recovered (PGR) ( which is defined by Burns et al. 2023) can approach 1. \n\nIn the case of two-layer linear networks learning linear target functions with a specific input distribution, the student’s error is shown to be asymptotically smaller than the teacher’s error, with the relationship \\( L_{ST} = \\mathcal{O}(L_{TE}^2) \\).\n\nThe paper explores the limit of weak-to-strong generalization and proves that for random feature models, the largest possible gap occurs in the linear network case, where the student’s error is at least quadratic in the teacher’s error. It also highlights that weak-to-strong generalization cannot arbitrarily improve a very weak teacher model, and for near-zero student error, the teacher's error must also be small.\n\nThe authors explain that early stopping during gradient descent helps the student model by eliminating spurious noise in higher-order eigen-components introduced by the weak teacher model, thereby enabling the student to better align with the leading components of the target.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their positive feedback. Below we address the main comments:\n\n-Regarding linear networks achieving optimal exponent:  With the linear network model, we choose the covariance directly and so can impose an extreme spectral structure, namely a huge eigengap. This makes our learning algorithm (GF with early stopping) the ideal truncating algorithm — zeroing out all projections onto the eigendirections with low eigenvalues but exactly keeping the projections into the eigendirections with large eigenvalues. This turns out to be sufficient for matching the lower bound.  But ReLU networks with spherical Gaussian random weights have a specific spectral structure, which does lead to significant weak-to-strong behavior (as we analyze), but is not as extreme.\n\n-Regarding $M_{TE}\\to \\infty$: We take $M_{ST}\\to\\infty$ first, so $M_{TE}/M_{ST}$ should be thought of as small, i.e $o(1)$. Our results do not use the simultaneous limit, i.e. taking $M_{ST}$ and $M_{TE}$ to infinity together.\n\n-Regarding analysis with finite data: It is certainly possible to obtain similar results also when the teacher is trained with a large but finite amount of data.  This is possible with a large enough amount of data such that standard generalization guarantees would ensure the teacher is close to its population optimum.   There isn’t a significant technical difficulty here, just bookkeeping and additional terms to track and a corresponding complication in the Theorem statements and proofs. We choose to not get into this complication as we felt it does not provide additional insight (the separation and gaps would be the same), would unnecessarily increase complexity of presentation, and that a weak-to-strong effect even if the teacher does has infinite data (and so is in a sense less weak) is in a sense even stronger.\n\n-Ildiz et al also study a two-step stage learning process, first training a linear teacher and then a linear student based on the teacher.  But the effect they show is that of “distillation”, i.e. how training the student based on teacher labels is better than training the student based on real labels. This is different from a weak-to-strong effect, where we compare the student trained on teacher labels to the teacher itself.  In their  Section 3.1 and Proposition 3, Ildiz et al do study a small teacher that, like our weak teacher, has fewer features than the student.  But what they show is very different: even in this subsection (which they title “weak to strong”) they show how student-trained-on-teacher-labels can be better than student-trained-on-real-labels (as opposed to weak-to-strong, which is student-trained-on-teacher-labels is better than teacher).  Even in their setting of Section 3.1, it is NOT the case that the student-trained-on-teacher-labels is better than the teacher, i.e. there is no “weak to strong” effect in the sense of Burns et al.  The type of distillation benefit they show (which we again emphasize is different from the weak-to-strong effect we study) is possible due to the following differences from our work:\n\n--Idliz et al train with either ERM or min-norm-interpolating predictor, not with early stopping.  We emphasize that early stopping is crucial for weak-to-strong generalization. What they can show is that the student-trained-on-teacher labels can be better than the student-trained-on-real-labels if the training data is finite, but this does not mean the student can be better than the teacher. In fact, if we increase the number of data to infinity, the student will eventually become the same as the teacher, while in our setting early stopping enables the student to perform better than the teacher.\n\n--The teacher uses a carefully selected subset of features, as opposed to random features.\n\nSimilarities include the use of linear models, the two-stage learning process (though without early stopping) and training the teacher model on infinite data.\n\n-Regarding the random features and gradient flow: Our main claim for random features factors into Theorems 6.5 and Theorems 6.9 and is a statement about the random feature features (in the teacher’s model) project onto the top-S eigenbasis. For this, we apply a general Hilbert Space concentration result to a carefully constructed Hilbert space to prove this statement. We are not aware of prior works having a similar approach. For the gradient flow reference, we agree that it is appropriate to include additional works. We will add references in the final version, including “A Continuous-Time View of Early Stopping for Least Squares” by Ali et al 2019 or “Continuous vs. Discrete Optimization of Deep Neural Networks” by Elkabetz et al 2021.", "claims_and_evidence": "The authors clearly proves all of their claims in the paper. In addition to that, the authors provide intuitions about how the weak-to-strong generalization and superalignment occurs in Section 5.", "methods_and_evaluation_criteria": "This paper is a theoretical paper where the authors prove their contributions in statements. The authors provide 2 different experimental settings where they used 2-layer ReLU networks and Linear Networks. The experimental settings make sense in general and verify the theoretical results.", "theoretical_claims": "I checked Appendix C, where the authors analyze Linear Networks; and I checked the arguments utilized in Appendix D, where the authors analyze the 2-layer ReLU networks.", "experimental_designs_or_analyses": "N/A", "relation_to_broader_scientific_literature": "The authors analyze two different models (2-layer ReLU networks and Linear Networks) in the context of weak-to-strong generalization, which is proposed in Burns et al. (2023). This paper provides a clear statement of when (based on the stopping criteria) and how (implicit regularization induced by early stopping) the weak-to-strong generalization appears in random features. Given the previous works, I think, this is paper is the best one which clearly explains the super-alignment behavior.", "essential_references_not_discussed": "The authors discussed the previous works of weak-to-strong generalization under the sections of empirical and theoretical works. However, I think, there are missing previous works related technical part of the paper. The related works related to random features are weak and there is no related works related to gradient flow dynamics as far as I see. I think the authors should discuss the technical parts of their work with respect to previous works.", "other_strengths_and_weaknesses": "### Strengths\n\n- The paper introduces a detailed framework for understanding how weak-to-strong generalization can emerge when the student model is trained using gradient descent with early stopping. This adds valuable theoretical insights into how a student model can outperform a teacher model, even with weaker training data or less optimal settings, which has significant implications for machine learning.\n\n- The paper provides strong, rigorously proven results, such as showing that the gap between the student and teacher models can be arbitrarily large.\n\n- The explanation of how early stopping helps the student model by eliminating spurious noise in higher-order eigen-components is a valuable contribution.\n\n- The authors also discuss the limit of weak-to-strong generalization and they found that the limit is achieved with Linear Networks.\n\n### Weaknesses\n\n- The training of the student and teacher models are with population data. For the student model, it is acceptable since the dataset is obtained using the teacher model. However, the authors only analyzes the training of the teacher model with population data. I am curious of the potential theoretical drawbacks of analyzing finite data in the training of the teacher model. It might be possible to analyze the linear networks with finite data for training the teacher model. \n\n- I noticed lots of typos in the paper. I think it would be better if the authors carefully check the typos. \n\n- There is no conclusion section in this paper. I think the authors should add a conclusion section where they can discuss the limitations and the future works of this paper. \n\n- There are some missing references regarding dynamic flow analysis.", "other_comments_or_suggestions": "I noticed some of the typos in the paper:\n\n- generalization in line 105 column 1.\n\n- trained in line 149 column 1.\n\n- dependence line 182 column 2.\n\n- random in line 234 column 1.\n\n- network in line 271 column 2.\n\n- coordinates in line 310 column 1.\n\n- quantities in line 332 column 2.", "questions_for_authors": "- Is there any intuition behind the fact that linear network achieves the limit of weak-to-strong generalization in Theorem 4.1?\n\n- For theorems 3.1 and 3.2, as $M_{TE}$ approaches $\\infty$, what is the regime of $M_{ST}$? Specifically, is $M_{TE}/ M_{ST}$ linear or supra-linear? \n\n- What are the potential technical difficulties when the authors analyze the models with finite data during the training of the teacher model?\n\n- In the case of linear networks, what are the differences and similarities between Ildiz et al. 2024 and this paper?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "N6EkRTCook", "reviewer": "Reviewer_fjzj", "summary": "The paper investigates weak to strong generalization via studying random feature networks. A set of experiments and a series of proofs are shown which give evidence that weak to strong generalization occurs in random feature networks with student models having significantly smaller error than the teacher model, giving a framework from which further studies can be conducted from.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their positive feedback.\n\nFull details on the data distributions used in the simulations are provided in the figure captions.  These are synthetic data distributions that match Theorems 3.1 and 3.2. More explicitly:\n\nIn Figure 2, we use a ReLU networks with the input dimension $d=32$.  The student has $M_{ST} = 16384$ hidden units, and different curves correspond to teacher with $M_{TE} \\in \\{16,...,256\\}$ hidden units. The inputs a uniformly distributed on a unit-radius sphere $S^{d-1}$ and the target is given by $f*=\\langle \\beta,x\\rangle$ for a unit norm beta. \n\nIn Figure 3, we consider linear networks where the number of hidden units for the student is always $M_{ST}=16384$, and teachers with varying number of hidden units $M_{TE}$ between $16$ and $4096$.  The input dimension is $d=M_{TE}^{3/2}$ (depending on the teacher width), as in Theorem 3.1.  The input follows a non-spherical Gaussian distribution $x\\sim N(0,\\Psi)$ where $\\Psi = (1,(d-1)^{-2/3},...,(d-1)^{-2/3})$, as in Theorem 3.1, and the target is $f^*=\\langle e_1,x\\rangle$.", "claims_and_evidence": "I find the experimental evidence to be of good quality, and it appears that multiple seeds are ran for each architecture and setting investigated.", "methods_and_evaluation_criteria": "Yes, but I would like to see some investigations on conventional datasets.", "theoretical_claims": "I took a brief look at the proofs, which are laid out clearly, but I am uncertain as to correctness.", "experimental_designs_or_analyses": "The experiment design is good. The experiments are done with 5 seeds. I am a bit a confused on what the inputs are, if it is images or text or random numbers, so it would be good if this was clarified whenever the experiments are detailed.", "relation_to_broader_scientific_literature": "A set of results on random feature networks for weak to strong generalization are presented.", "essential_references_not_discussed": "n/a", "other_strengths_and_weaknesses": "n/a", "other_comments_or_suggestions": "line 387 - > firsy\nline 272 -> Netowkr\nline 201 punctuation \nline 270 -> simmulation\nGrammar is odd in many parts \nThere is a lack of a conclusions section, making this paper appear incomplete.", "questions_for_authors": "What datasets are the experiments investigated on?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "m0JnU3dbLh", "reviewer": "Reviewer_TiKn", "summary": "The paper studies weak-to-strong generalization in random feature models trained via gradient flow with early stopping. Contrary to the prior belief that well-pretrained models (like GPT-4) are necessary for weak-to-strong, this paper shows that weak-to-strong can occur even in much simpler models without pretraining, like two-layer neural networks with random, fixed bottom layers and trained top layers. In the context of random feature models, the weak v.s. strong models are modeled as linear or two-layer ReLU networks with small v.s. large numbers of hidden units, respectively. For weak-to-strong, the last layer of the weak teacher is first trained over the population with ground truth labels. Then, an infinitely wide strong student is trained via gradient flow over the same population with pseudo-labels from the weak teacher. It is shown that the strong student can achieve polynomially smaller generalization error than the weak teacher. A lower bound of such improvement is derived. Insights are provided on the mechanisms behind weak-to-strong from the early stopping perspective.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their positive feedback. Below we address the main comments:\n\n-Regarding $M_{TE}\\to\\infty$:  First, it is important to emphasize that our results are not asymptotic and we show a gap for finite teacher width $M_{TE}$, not only as $M_{TE}\\to\\infty$.  Indeed, we also discuss $M_{TE}\\to\\infty$, and this is where the gap is largest.  Even as $M_{TE}\\to\\infty$, this is still very much a weak-to-strong setting: the teacher becomes larger, but the student is proportionally even larger.  We actually consider this the more interesting and relevant setting, as it captures using an already very large teacher (like GPT2 or 3, which as statistical models go, already has an extremely large number of parameters, well in the “high dimensional” regime) to train an even larger student (eg GPT4).  In short, we always consider students which are much larger than their teachers, i.e. $M_{ST} \\gg M_{TE}$, and even when we take both widths to be very large with $M_{ST}, M_{TE}\\to \\infty$ we still have $M_{ST} \\gg M_{TE}$.\n\n-Regarding the Gaussian Universality Ansatz: First, we want to emphasize that this is only used in the second part of Theorem 3.1, in order to easily get a lower bound on the teacher, and in a sense is not crucial for the main weak-to-strong effect, which is the improvement in the student as specified in the first part of Theorem 3.1. Regarding the difference between the ReLU setting with the Ansatz and the linear setting: the main difference is that the ReLU network imposes a particular structure on the spectrum of the kernel, which is different from that of the linear model.  The difference in exponent is due to the difference in this spectral structure. We can expand on this in the final version of the paper.\n\n-Regarding section 5: As the reviewer pointed out, the goal of section 5 is explain the how weak-to-stron generalization happens in this case. The main takeaway is understanding the implications of how the trajectory of the student predictor behaves in function space. This can be also seen from the closed-form equation of GF, i.e. Equation (13) on page 7. Namely, once we understand the directions along which GF (and approximately GD) shrinks $f_{TE}-f_{ST}$ and the fact that the shrinkage is faster for directions with larger covariance, we can explain the weak-to-strong phenomenon in this case. As it turns out, the relevant directions are eigendirections and they are the coordinate directions for linear networks and spherical harmonics for ReLU networks. How fast the shrinkage happens is determined by the eigenvalue corresponding to the given eigendirection. Therefore, if there is a big eigengap between $e_K$ and $e_{K+1}$, then we can learn the teacher predictor along $e_1,..,e_K$ much quicker than any of the $e_{\\ge K+1}$, effectively zeroing out the signal along any of the $e_{\\ge K+1}$. We will update section 5 to clarify this in our final version.", "claims_and_evidence": "Yes, while I couldn't verify all the proofs in the appendix, the main results in the paper seem reasonable. The claims are well-supported by theoretical analysis and some synthetic numerical experiments.", "methods_and_evaluation_criteria": "Yes, the theoretical tools used in the paper are reasonable. In particular, the connection between weak-to-strong and early stopping (or in general, taking training dynamics into consideration when analyzing weak-to-strong) is insightful.", "theoretical_claims": "While I couldn't verify all the proofs in the appendix, the main results in the paper seem reasonable.", "experimental_designs_or_analyses": "This is a theoretical paper with a few synthetic numerical experiments. The experiments are simple but sufficient to support the theoretical claims.", "relation_to_broader_scientific_literature": "In contrast to the common belief that weak-to-strong requires well-pretrained models, this paper provides rigorous analysis showing that weak-to-strong can occur even in much simpler models without pretraining.", "essential_references_not_discussed": "Upon my knowledge, the paper discusses the essential references in the field.", "other_strengths_and_weaknesses": "Strengths:\n- In contrast to the common belief that weak-to-strong requires well-pretrained models, this paper provides rigorous analysis showing that weak-to-strong can occur even in much simpler models without pretraining.\n- The connection between weak-to-strong and early stopping (or in general, taking training dynamics into consideration when analyzing weak-to-strong) is insightful.\n\nWeaknesses\n- The insights underneath some theoretical results are not thoroughly explained. For example, Theorem 3.1 (and 3.2) imply that $L_{ST} / L_{TE} \\to 0$ as $M_{TE} \\to \\infty$. Toward this limit, it seems that both the teacher and student will be infinitely wide random feature models. This limiting scenario seems to go beyond the weak-to-strong setting but brings the best PGR, which is in some sense counterintuitive regarding where the weak-to-strong effect comes from. It would be helpful to provide more insights on this.\n- The notion of \"Gaussian University Ansatz\" seems to be critical but is not well explained in the paper. For example, a formal definition of the ansatz in the main text (instead of footnotes) would be helpful. It's somehow confusing what's the key difference between the linear model 2.2 v.s. the two-layer ReLU model 2.1 under Gaussian University Ansatz in terms of analysis. Further clarification would be helpful, e.g., what leads to the different exponents 1.49 v.s. 2 (except the special spectrum of the covariance in Theorem 3.2)?\n- Section 5 provides valuable insights for the mechanism of weak-to-strong and the importance of early stopping. However, the writing is a bit confusing. It would be helpful to provide more structured explanations for better readability.", "other_comments_or_suggestions": "Here are some additional minor points:\n- Line 197, right: \"Indeed, we can see that even in the ReLU Model 2.1, the *teacher error* is polynomially smaller...\" -> \"student error\"?\n- Line 250, right: \"In Theorem 4.1 we show that this is not possible, at least not with a random feature *mdel* as in Section 2.\" -> \"model\".", "questions_for_authors": "Major questions are raised in the \"Other Strengths And Weaknesses\" section.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "p3pViUvlGy", "reviewer": "Reviewer_Z9fy", "summary": "This paper theoretically proves that, even in the random features model (a special case of two-layer neural networks and we only train the second layer), we can still obtain week-to-strong generalization if we choose a suitable earlying stopping time for the student model. The contributions include the following aspects:\n\n- in Theorem 3.1, for random features model, training with $\\Theta(\\log M_{TE})$ steps for the student model, the test loss on the student model can be sufficiently smaller than that of the teacher model. Under Gaussian universarity assumption, the relationship can be described with an index 1.49.\n\n- Without Gaussian universarity assumption, such charecterization can be given under a linear model with a proper spectrum decay in Theorem 3.2.\n\n- In Theorem 4.1, the limits of random features model with early stopping is given in terms of lower bound.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their positive feedback. Below we address the main comments:\n\n-The reviewer asks “Why at all introduce the teacher”?  Indeed, in the weak-to-strong setup as introduced by Burns, and as we study here, training directly on the target $f^*$ would give better performance than weak-to-strong training.  This is what Burns refers to as the “ceiling performance”, denoted by $L_{ST}^{ceil}$ in the definition of the PGR (our equation 9).  The weak-to-strong question, as introduced by Burns, asks how training with only the teacher labels, and not the true target, can get close to this ceiling performance. This captures a situation where **the target is not available when training the strong student, only the weak teacher**.  See Burns et al for further discussion.  What we are investigating are scenarios in which even if the student is trained only through the teacher, **the student is better than the teacher** (but not better than the ceiling performance!).  Unsurprisingly, this happens when the target is aligned in some way with the inductive bias of the student (and teacher), and the way we capture this in order to obtain crisp possibility results is through the eigenspace assumption (though our general results do not need this specific assumption and are more general).\n\n-Gradient flow: gradient flow can be thought of simply as gradient updates with very small step size (formally, when the step sizes goes to zero), see e.g. “A Continuous-Time View of Early Stopping for Least Squares” by Ali et al 2019 or “Continuous vs. Discrete Optimization of Deep Neural Networks” by Elkabetz et al 2021.  Using standard results on the convergence of gradient descent to gradient flow, it is possible to obtain the same results also for early stopped gradient descent, with an additional error term that depends on the stepsize, and can be made as small as we would like.  Studying how using large stepsizes effects weak-to-strong generalization, and how small the stepsize needs to be to realize weak-to-strong, is indeed an interesting and difficult problem (this follows the path of many results on the implicit bias of gradient descent, which are also much better understood in the gradient flow, ie small stepsize, limit).\n\n-Regarding the $\\kappa_S$: Effective rank is a property of the student’s kernel only, i.e. the eigenvalues of each of the eigendirections of the kernel function. $\\kappa_s$ measures, roughly, how much of the teacher error is contained in the $ \\{e_{\\ge S+1}\\}$ eigendirections. $\\kappa_s$ is a quantity that depends on the projection of the teacher features onto the eigendirections, and is not related to the student at all. So there is no a-priori connection - the eigenvalues of the student kernel do not factor in $\\kappa_s$. This can be seen from the fact that $\\kappa_S$ and the student eigenvalue factor separately into the final result.\n\n-Regarding the optimal stopping time: we indeed do not have a simple expression for the optimal stopping time. What we show is that with some stopping time we can get W2S generalization. We do however have some insight into the optimal stopping time through the experimental results. We agree that understanding the optimal stopping time is an interesting question.  Empirically, optimal stopping can often be achieved through validation.", "claims_and_evidence": "The key idea (Theorem 6.3) is that early stopping can reduce the variance if there exists a large eigenvalue gap while the bias can be unchanged, so we can obtain the weak-to-strong generalization. \n\n- The key issue here is that, the authors assume that the target function $f^*$ is supported on the top-K eigenspace of the student's kernel with nonzero eigenvalues. In this case, the bias can be unchanged and we only need to reduce the variance. However, I'm not sure this matches the key spirit of weak-to-strong generalization from the perspective of model capacity from a smaller to larger case (mainly on the bias part). More importantly, we assume the target function $f^*$ is supported by the student's kernel, why do we need to introduce the teacher model in a two-stage learning? In this case, we can directly learn it by the student model and then obtain $L_{ST}^C$.\n\n- Another issue is that, the authors use gradient flow to derive the results. I understand that this can simplify the analysis and we can directly obtain the dynamics of the output in a closed-form solution format. But using certain gradient steps for early stopping is more natural and makes sense, which is the key idea of this work.", "methods_and_evaluation_criteria": "This is a theoretical paper and no algorithm is provided.", "theoretical_claims": "I have checked the theoretical claims in Section 3 and Section 5, Section 6 in page 7.", "experimental_designs_or_analyses": "The experiments on toy model, e.g., Figure 1,2,3 look nice to grasp the main idea of this work.", "relation_to_broader_scientific_literature": "yes. this paper provides a theoretical analysis of weak-to-strong generalization.", "essential_references_not_discussed": "N/A", "other_strengths_and_weaknesses": "This paper provides one way to understand weak-to-strong generalization from the variance reduction part.", "other_comments_or_suggestions": "This paper is writing in a quite rush way with massive typos, e.g.,\n\nline 271: Random Feature Netowkr -> Random Feature Netowork\n\nNotation inconsistency: \nline 300, U_S is bold but sometimes not.", "questions_for_authors": "- What is the relationship between $\\kappa_S$ in Eq. (14) and effective rank? For example, if there is a large eigenvalue gap, $\\kappa_S$ is close to 1 and the effective rank (definition can be found in Peter's benign overfitting paper) is well-controlled.\n\n- In Theorem 6.3, it's still unclear to me what is the optimal early stopping time?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper studies the phenomenon of weak-to-strong generalization in a random feature model: a weak (=with less parameters) teacher gives labels to a strong (=with more parameters) student, and the student can outperform the teacher. Specifically, the paper provides upper bounds on the performance of the student: $\mathcal L_{\rm ST}= \mathcal L_{\rm TE}^{1.49}$ for ReLU under the Gaussian Universality Ansatz (which is pretty common in related work); $\mathcal L_{\rm ST}= \mathcal L_{\rm TE}^{2}$ in the linear case. Remarkably, the paper also gives a lower bound of quadratic order. Furthermore, the results are interpreted via the lens of early stopping.

All reviewers are positive about the paper, with varying levels of enthusiasm. The feedback of the authors has also been well received, addressing most concerns. There is consensus towards accepting the paper, and I concur. The results are rather strong, interesting and insightful; this is a solid contribution to ICML and I recommend accepting it.

It has been pointed out that the presentation could be improved and a number of typos should be corrected and I encourage the authors to do a careful round of polishing when preparing the camera-ready.
Decision: Accept (poster)