Provable weak-to-strong generalization via benign overfitting
Authors: David Xing Wu
Anant Sahai
Venue: ICLR 2025 Poster (2025)
Keywords: benign overfitting
spiked covariance models
overparameterized models
interpolation
pseudolabeling
weak-to-strong generalization
alignment
Primary area: learning theory
TL;DR: We use recent advances in benign overfitting for classification to prove weak-to-strong generalization in a toy setting.

Abstract: The classic teacher-student model in machine learning posits that a strong teacher supervises a weak student to improve the student's capabilities.
    We instead consider the inverted situation, where a weak teacher supervises a strong student with imperfect pseudolabels. 
    This paradigm was recently brought forth by \citet{burns2023weak} and termed \emph{weak-to-strong generalization}. 
    We theoretically investigate weak-to-strong generalization for binary and multilabel classification in a stylized overparameterized spiked covariance model with Gaussian covariates where the weak teacher's pseudolabels are asymptotically like random guessing.
    Under these assumptions, we provably identify two asymptotic phases of the strong student's generalization after weak supervision: (1) successful generalization and (2) random guessing. 
    Our techniques should eventually extend to weak-to-strong multiclass classification. 
    Towards doing so, we prove a tight lower tail inequality for the maximum of correlated Gaussians, which may be of independent interest.
    Understanding the multilabel setting reinforces the value of using logits for weak supervision when they are available.

Published as a conference paper at ICLR 2025
PROVABLE WEAK-TO-STRON GENERALIZATION VIA BENIGN OVERFITTING
David X. Wu
Anant Sahai Department of EECS
Department of EECS UC Berkeley Berkeley, CA 94720 david_wu@berkelley edu
UC Berkeley
Berkeley, CA 94720
saha feecs wer.eley..eeeo....o.......eeee edu
ABSTRACT
The classic teacher-student model machine learning posits that a strong teacher supervises weak student to improve the student's 's capabilities. We instead consider the inverted situation, where weak teacher supervises a strong student with imperfect pseudolabels. This paradigm was recently brought forth by Burns et al. (2023) and termed weak-to-strong generalization. We theoretically investigate weak-to-strong generalization for binary and multilabel classification in stylized overparameterized spiked covariance model with Gaussian covariates where the weak teacher's 's pseudolabels are asymptotically like random guessing. Under these assumptions, we provably identify two asymptotic phases of the strong student's generalization after weak supervision: (1) successful generalization and (2) random guessing. Our techniques should eventually extend to weak-to weak-to-strong multiclass classification. Towards doing so, we prove tight lower tail inequality for the maximum of correlated Gaussians, which may be of independent interest. Understanding the multilabel setting reinforces the value of using logits for weak supervision when they available.
INTRODUCTION
Motivated by the problem of aligning increasingly capable models, Burns al. (2023) introduced the framework of weak-to-strong generalization! , which draws an analogy between humans supervising superhuman AIs and weaker teacher models supervising stronger student models. This inverts the classic teacher-student model framework, which typically assumes that the teacher is stronger than the student. Burns et al. (2023) found that using GPT-2 to finetune GPT-4 can recover most of the performance of standard supervised finetuning with benchmarks, but struggles on more difficult tasks such as chess puzzles or reward modeling. One failure mode observed by Burns et al. (2023) is that the strong student sometimes learns to mimic the weak teacher, i.e. the strong model overfits to the limitations of the weaker one. Since Burns et al. (2023), this phenomenon has been studied in variety of other empirical settings (see e.g. Ji et al. (2024); Guo et al. (2024); Liu & Alahi (2024); Yang et al. (2024); Tao & Li (2024)).
data across standard NLP
These empirical observations naturally lead the question that we aim answer in this paper: Can we identify a simple, concrete theoretical setting where we can provably exhibit different phases of weak-to-strong generalization? Below, we survey closely related areas of research.
Pseudolabeling and synthetic data. In semi-supervised learning, pseudolabeling refers to the method of using one model's outputs generate pseudolabels for unlabeled data (Lee al., 2013; Arazo et al., 2020; Rizve et al., 2021; Zhang et al., 2021: Soscantee-onillle et al., 2021: He et al., 2024). These pseudolabels are then used to supervise the target model. We consider using the weak model to generate pseudolabels for the strong model in our concrete setting.
This situation is related, but slightly different, from the earlier identified problem of casy-to-hace hard generaliza- tion (see e.g. Schwarzschild et al. (2021); ); Hase et al. (2024)) wherein a model is trained on "easy" cases but has generalize to "hard" cases. The most important distinction is that in weak-to-stree to-stoong generalization, the weak teacher actually gets things wrong.

---

Published as a conference paper at ICLR 2025
Synthetic data generation is another widely popular paradigm for sealing up models in the absence of human-annottn -amaan-nnnottte data; see, e.g. (Nikolenko, 2021; Liu et al., 2024; Chen et al., 2021; Figueira & Vaz, 2022) and references therein. In this approach, one uses generative models to generate synthetic data, which can then be labeled and used to supervise other models. The use of synthetic data to train models resembles the weak-to-strong setup that we study, although we assume the unlabeled datapoints are generated from the ground-truth distribution. Nevertheless, we believe that extending our techniques may yield interesting insights on the success and failure modes of synthetic data.
Supervised finetuning and scaling laws. In contemporary deep learning, the dominant paradigm is to pretrain large (e.g. billions of parameters) models on copious (e.g. trillions of tokens) unlabeled data in a self-supervised fashion and then finetune the model on relatively tiny (e.g. less than 100K) finetuning datasets. The prevailing wisdom suggests that (1) pretraining helps the model learn useful features that can be repurposed for specific tasks and (2) the optimal size of models should scale with the amount of data (see, e.g. (Kaplan et al., 2020; Wei et al., 2021: Wang et al., 2022b; Liu et al., 2022; Hoffmann et al., 2022)). Much effort has gone into improving the effectiveness and efficiency of finetuning (Houlsby et al., 2019; Hu et al., 2021: Lester et al., 2021; Dettmers et al., 2024).
According to NTK theory, if the model weights do not move far from initialization during finetuning. we can approximate finetuning as training a generalized linear model using (tangent) features. These features arise from the gradients of the network's 's outputs with respect to the parameters at finetuning initialization. This motivates our studying the behavior of interpolating linear models in the context linear- of supervised finetuning. Our concrete theoretical setting sits within the Gaussian- model style of Wei et al. (2022); Belkin et al. (2020); Mei & Montanari (2022); Bartlett et al. (2020); Muthukumar al. (2020; 2021); Chatterji & Long (2021): Wang & Thrampoulidis (2021); Subramanian et al. (2022); Wang et al. (2022a); Wang et al. (2021); Cornacchia et al. (2023).
Knowledge distillation. The topic of weak-to-strong generalization is related the extensive literature on knowledge distillation, which originated in the desire to compress large powerful models (teachers) into smaller ones (students) (Hinton al., 2015; Buciluă et al., 2006). See Gou al. (2021) for general survey. Theoretical perspectives for the essentially underparameterized case were developed in Phuong & Lampert (2019); Ji & Zhu (2020), and the theoretically engaged literature in this area has continued to expand; see Yuan et al. (2024); Ojha et al. (2023); Safaryan et al. (2023); Alballa & Canini (2024); Hong et al. (2024); Sarnthein et al. (2023); Zhao & Zhu (2023); Das & Sanghavi (2023); Xu et al. (2024); Nagarajan et al. (2023); Borup & Andersen (2023); Harutyunyan (2023); Stanton et al. (2021): Mobahi et al. (2020) for a few representative more recent examples.
The question of how knowledge distillation can improve the student's 's generalization to surpass the teacher (especially when they have the same architecture) has led to the identification of several different underlying mechanisms (Yuan et al., 2024; Safaryan et al., 2023; Sarnthein et al., 2023; Das & Sanghavi, 2023; Nagarajan et al., 2023; Mobahi et al., 2020). Of these, the closest in spirit to our approach is the regularization viewpoint of Mobahi et al. (2020), which studies kernel-regressson model. They call out the crucial role of the spectrum of the Gram matrix more specifically, self-distillation accentuates the importance of the larger eigenvalues, which has regularizing effect by making the corresponding basis functions more prominent in the learned pattern.
Concurrent theoretical work. Zhang et al. (2024) engages with generative models and observes that temperature can play an important role in allowing trained model to surpass its training sources. Somerstep al. (2024) takes a transfer-leaminn perspective and asserts that naive fine-tuning on weak pseudolabels tends not to work; our results show conditions where this does in fact succeed. Charikar et al. (2024) takes a representation-cene centric perspective in regression setting and zooms in on the question of how much better the representation is for the stronger model. Lang et al. (2024) studies the classification setting and takes a neighborhood perspective that posits that the stronger model's neighborhood structure allows it to average over the weak labels to get generalization. At high level, our work along with Mobahi et al. (2020); Charikar et al. (2024); Lang et al. (2024) all generalization works when the cascading learning process
circle around the idea that weak-to-stree purifies representations in the true direction and contracts in false directions.
2

---

Published as a conference paper at ICLR 2025
1.1 CONTRIBUTIONS
In this paper, we explore weak-to-strong generalization in stylized theoretical model that captures the dynamics of finetuning with weak supervision studied in Burns et al. (2023). Under a simple overparameterized spiked covariance model for the pretraining features, we prove that finetuning an overparameterized linear classifier using minimum &2 norm interpolation on top of these features provably exhibits two distinct phases of weak-to-strong generalization. In particular, under certain scalings, as we increase the number of weakly labeled finetuning examples, the strong learner's asympiotic accuracy transitions from (1) random guessing to (2) perfect generalization; see Section 3 for a precise statement.
To be specific, study the generalization of interpolating linear models with and without weak supervision. Although our results can be generalized to any weak teacher which produces logits using linear head, assume for the sake of concreteness that the weak teacher is also interpolating linear model which can be fully expressed by the strong student. We discuss how our theoretical results connect to realistic supervised finetuning scenarios in Section 4.
Our results strongly hinge on the tight analysis for benign overfitting in multiclass classification in Wu & Sahai (2024), although the study of benign overfitting for regression and binary classification was already carried out by Bartlett et al. (2020); Muthukumar et al. (2021).
2 PRELIMINARIES AND SETUP
Below, we set up the weak to-strong learning task in Section 2.1, along with the data assumptions in Section 2.2, and finally specify the concrete end-to-end learning algorithm we study in Section 2.3.
2.1 YEAK-TO-STRONT SETUP
To study weak-to-strong generalization, we will consider simple setup which encapsulates the dy- namies of standard supervised finetuning well as training linear probes intermediate activations. We will now give a high level description of the teak-to-strong setting, and in subsequent sections formally define the specific assumptions we make to theoretically study weak supervision.
Suppose we have n labeled datapoints and m = n² unlabeled datapoints, where u > This matches the modern ML paradigm where labeled data scarce and unlabeled data is abundant.
We assume that we have access to two sets of features extracted from the datapoints: the weak and strong features. Using these features, we will create weak-to-strone setup with a weak model and strong model, where the weak model is used to generate hard pseudolabels to train the strong model (see Procedure for formal definition). The learning task at hand is binary classification, where each model uses its respective features obtained from the datapoints - see Section 4 for how our techniques apply to the multiclass setting.
Clearly, to get nontrivial learning guarantees, there needs to be some relationship between the weak and strong features. To specify this, we will assume that the weak and strong features come from an appropriate weak-to- sostooo-ttoong ensemble of features, which we formally define in Section 2.2. One way to interpret the teak-to-strongg ensemble is that the true hidden direction is highlighted more in the strong features than the weak features; see Figure 1.
In supervised finetuning and linear probing, the strong and weak features come from pretraining via the neural tangent features and intermediate activations, respectively. For example, in the GPT2 to GPT4 weak-to-steee to-t-tog-ttong setup Burns et al. (2023), the weak features come from GPT2 pretraining, whereas the strong features come from GPT4 pretraining.
Broadly speaking, we study the case where the true labels are generated by a distinguished (but unknown) low-rank subspace hidden in very high dimensional space.
To be concrete, we will study two different classifiers in this setup:
(1) f fweak: train/finetune
datapoints using weak features in Thank and ground-truth labels. (2) fwes: train/finetune on m > n datapoints using strong features in IRd and hard pseudolabels generated from fueak-
3

---

Published as a conference paper at ICLR 2025
We study scheme where fweak and fw2s are linear models trained by performing minimum E2 interpolation (MNI) on their respective training sets; see Section 2.3 for a formal definition MNI. Remark 2.1. Instead of training with hard (categorical) pseudolabels, one could use the real-valued scores from Sweak. This would only affect constants which are not crucial to any of our results.
We will measure generalization via the test accuracy of these classifiers. In particular, let {(+) be the 0-1 loss function, and let E({(-)] be the expected test error over a fresh test sample. We introduce the following desiderata to define weak to-strong generalization for binary classification.
Desiderata 1. The main desiderata the following:
(i) The strong model asymptotically generalizes when trained on the m weakly labeled data- points: [[L[[w2=)] = (1).
(ii) The strong model can fully represent the weak model.
(iii) The weak model asymptotically does not generalize: B[((fweak)] on.
In Section 3, we show that the above desiderata are achievable in simple toy model; see Theorem 3.3 for formal statement. This paints rather striking picture: there are situations where the weak labels asymptotically look like random guessing (Desideratum I.iii), the strong model perfectly imitate the weak labels (Desideratum Lii), yet the strong model still asymptotically generalizes by extracting enough signal out of the plentiful weak labels (Desideratum 1.i).²
We also include some bonus desiderata, which paint a comparison to natural alternative training methods. We can also provably achieve these bonus desiderata in certain regimes; see Remark 3.4. Desiderata 2. The extra desiderata are the following:
(i) PCA cannot recover the low-rank structure from m observations of the strong features.
(ii) Let fatrnng be the strong model when trained on n datapoints using strong features Te and ground-trat -rrth labels. Then fssrong asymptotically fails: [(s(oo)) -0 (1).
2.2 DATA MODEL
Throughout, we will consider data with zero mean Gaussian covariates, which can be viewed as an idealized version the pretraining features or representations. These covariates are generated from ambient standard Gaussian vector (g1, ... 9DD) R... We make Gaussianity assumptions for the sake theoretical tractability; in Section 4 we discuss potential extensions to other settings.
Covariates. A learner observes iid features æ; (0, 2), where emphasize that the feature covariances Σ E Rdxd are unknown and different for each learner. The different E's capture how weak strong the features are for each model; make this precise below. Note that æ; is linear transformation of the underlying randomness 9s ~ N(0, In). We will often refer to the eigendecompositiin Σ UAUT, where U E IRdd is orthogonal and A Raxd is diagonal.
Labels. For binary classification, we consider hard labels generated by the signs of Gaussians, so that y = sgn( (g, v.)), where v, is unknown unit-norm direction. To analyze the generalization of various learners, we will allow ourselves to study labels generated by various directions v, not just the true v., all of which assume are unknown. 4 For multiclass classification, we assume the labels are generated via arg max (g. v. (i) where (!)
(R) are all unknown.
......" ,
Following Muthukumar et al. (2021); Subramanian et al. (2022); Wu & Sahai (2024), we will make the following assumption on the true label directions to simplify the analysis. However, to study weak-to-strong generalization, 1 1-sparse. One of our main contributions is showing how to analyze this case.
will eventually have to analyze weak label direction which is not
The natural extension to multiclass settings with & different classes would require E[E(fwexx) IIn particular, Desideratum 1.ii allows the failure mode of the strong model imitating the weak model and also rules out more trivial sources of weak labels, such as independent label noise. the strong model cannot represent the noise in the weak labels, then wcak-to-strong generalization is intuitively much simpler. "To study weak supervision, take tWwak, the direction that the weak model learss.
e
4

---

Published as a conference paper at ICLR 2025
Assumption 1 (1-sparse assumption). We say that the labels satisfy the 1-sparse assumption relative to covariance Σ if the following holds. The label defining direction v, (directions v. =h for multiclass) is aligned with top eigenvector (top-k eigenvectors for multiclass) of Σ such that, in an eigenbasis where v, = e1 and u. ei respectively, we have
= sgn(x1)
(Binary) (Multiclass)
y arg max
jE(k]
For example, if the 1-sparse assumption holds for the strong covariance, then strong eigenbasis where the strong features are independent, the labels are generated by axis-aligned directions.
Bi-level ensemble and weak-to-strong ensemble. To simplify the analysis, we follow Muthukumar et al. (2021); Subramanian et al. (2022); Wu & Sahai (2024) and assume the eigenvalues A of the covariance are parameterized by the bi-level ensemble defined shortly. The bi-level ensemble is simple overparameterized version of the well-known spiked covariance model for PCA.
Definition (Bi-level ensemble), Let x (O, E), where the covariance Σ = UAUT. The bi-level ensemble parameterizes A = A(p, q, where > 1, 0 & r < 1, and 0 < q (p (p-ry r). The number of features (d), number of spiked directions (8), and degree of favoring (a) all scale with the number of training points (n) as follows:
d= [n [nn"
Then A = diag(As)ii(d where
ad a-ajd
Aj
(2)
otherwise
If the above holds, we refer to œ. A. or E as being drawn from the bi-level ensemble. We use the shorthands Ar a ad and Au - (1-a)d d-s to denote thvoreee and unfavored eigenvalues, respectively.
In particular, the parameterization controls the total number of features, d = n2 >> n., well as the dimension of the low-rank subspace = n² < n. For multiclass classification, we allow the number of classes to also scale with the number of datapoints n.
Definition 2 (Scaling for multiclass). For multiclass classification with l classes, we have k: = < [n*], where 0 & r and Cę is a positive integer.
We now pin down a concrete weak-to-strong ensemble, which boils down to specifying the joint distribution of the weak and strong features. We impose subset relationship between the weak and strong features in the strong basis; see Figure for a diagram.
A Assumption 2 (Weak-to-strong subset ensemble). Let A(p, r) E Rdxd denote the strong eigenvalues and Aweak M(Pwakk Qweak, Tweak) E Rdden denote the weak eigenvalues, both drawn from the bi-level ensemble. Let >F.weak amoadaa and Ae. A (1-awat) denote the weak favored and unfavored eigenvalues, respectively. Let U be any distinguiseed eigenbasis of E. where Ei (Assumption 1). The weak and strong features in the basis U related as follows.
duank Bwakk
(1) Ustrong ~ NO), where A = \FI[ + A[TTa)
[s], with 1 E S and |S| = Sweaks such (2) There exists subsets of coordinates S [s), S [d] \ that
Tweak = (V A IIs
Au Au
HI Istrong N Ae + AU
Here, 11g denotes the projection onto the axis-aligned subspace indexed by S.
We will often abuse notation and restrict &weak E Rd to the coordinates in SUT, viewing @weak Bddees Hence. the weak favored features are subset of the strong favored features, the weak features features are a subset of the strong unfavored features, with different bi-level scalings, and furthermore the 1-sparse assumption holds for both Σ and Eweak.
Clearly, under Assumption 2, desideratum i. is satisfied, and the subset ensemble is essentially the simplest relationship between the features one could impose to achieve the desideratum. In Section 4, discuss how expect the results to change if we relax these data modeling assumptions.
5

---

Published as a conference paper at ICLR 2025
Subset ensemble
Inservalleo A,
Strong fovord
Woek lavdrod
Strong unfovorec
Weak unfovored
'2'
d 1P
Feature index
Figure I: Visualization of subset ensemble (Assumption 2) relating weak and strong features. Notice the decreased favoring for the weak features, and how the weak features are subset of the strong features in their respective category. Hence, a linear model on the strong features can simulate one on the weak features (Desideratum 1 I.i.). Moreover, the label defining directions, represented by the green shaded box, are in the span of both the weak and strong features.
2.3 LEARNING ALGORITHM
Our models are all trained using minimum fn-norm interpolation (MNI), which corresponds to the asymptotic behavior of gradient descent with zero initialization (Ji & Telgarsky, 2021). Define the data matrix X Raxd by X [an]
2n.. Let y R" be the (centered) one-hot vector for class E [k]. In MNI, we learn linear score function f(i) via the optimization problem
f(0 = arg min l|ll
s.t. X = 3) (
(MNT)
The coefficients of (() can be easily computed to be f(0) X (XX
X A y
where the matrix A XXT R is the unnormalized Gram matrix and invertible almost surely.
At time, given a fresh sample Ftest (0, Σ), in the binary case we predict ssggn(( Frest)). and for multiclass we predict the class with the highest score: ÿ arg max4e[k] (f Ttest) To be very explicit, let us formally define the end-to-end traning procedure for weak-to-strong. binary classification (cf. the description before Remark 2.1), with an obvious extension to multiclass settings.
Procedure 1 (Weak-to-stron training). The weak learner observes initial dataset datapoints (wiwweak 9:) [e)]] where T; weak are the weak features for the ith datapoint and = sgn( (g,, v.)) is the corresponding clean hard label. We train fwesk E Baaa using MNI on these n clean datapoints.
Then, both learners observe m extra unlabeled datapoints, where the weak model sees weak features jeak and the strong model sees the corresponding strong features (I jE(])) Generate hard pseudolabels via Ug.weak sgn(( (gu((feeak: (Bj.weak)), ), and use MNI to train fwzs IRd (xx j.trong: je(())
MAIN RESULTS
In this section, state main results for binary classification (Theorem 3.3) and multilabel classification (Theorem 3.5). We focus on the regime + >> and Sweak + Tweak > 1, since Muthukumar al. (2021, Theorem 13) implies that these the only nontrivial regimes for binary classification under the bi-level ensemble.
In this regime, we also tighten the previous error rates for binary and multiclass classification in the bi-level ensemble from (Wu & Sahai, 2024, Theorem 3.2); the proof can be found in Appendix E. To that end, we establish Gaussians, which may be of independent interest; we defer its statement to the end of this section.
concentration inequality for the lower tail of the maximum of correlated
Theorem 3.1 (Regimes with clean labels). Suppose the strong features have bi-level covariance == E(p, r) (Definition 1), where q ++ 1, the true multiclass labels are 1-sparse (Assumption 1), and the number classes & = [n'] (Definition 2). Then the test error for fstrong MNI-trained with

---

Published as a conference paper at ICLR 2025
clean multiclass labels satisfies
(1), (
if f < min {1 Tstrong j if t > min {1 r, Tstrong,
E[L(f strong )
where Tstrong - + 1- 2(q r). Furthermore, for binary classification (i.e. k 2), the explicit
error rates are given by
Elé( strong) = 1
arctan (n(no (ooon))).
(4)
By generalizing other results from Wu & Sahai (2024) handle imperfect labels, formally establish weak-to-strong generalization for binary classification in the subset ensemble. We give brief technical overview of the proof Section 3.1 and prove formally in Appendix C.
Theorem 3.2 (Weak-to-stroon generalization for subset ensemble), Consider the setup in Procedure I where the weak model fweak is MNI-trained on n correctly labeled examples and the strong model fwzs is MNI-trained
= n² weakly pseudolabeled examples, where + u and 4weak + Tweak 1.
In addition, we make the following data assumptions:
(1) The true binary labels are 1-sparse (Assumptiion for the strong covariance.
The weak and strong features follow the subset ensemble (Assumption 2) with bi-level eigenvalues Mp, r) and Mpueaks Qweak, Tweak), respectively, scaled relative to n.
(3) There are not too many weakly labeled examples: u 2+1+ttr (guast Twnkk)
Recall Tstrong - p + 1 22 + r). Then, the resulting test error for fw2s satisfies
E[l(fwes)] (1), O1),, if Qweak + Tweak min {1 F, Tstrong
if lweak + Tweak min {1 T, Tstrong)
(5)
In other words, under the stated parameter regimes, weak-to-strong generalization occurs when the strong model is trained on sufficiently many weak binary labels.' Figure demonstrates that the conditions for weak-to-strong generalization are not vacuous. We make the third enumerated assumption for technical reasons, but we believe this condition is essentially tight.
By combining Theorems 3.1 and 3.2, we obtain the exact conditions where the main desiderata from Section are satisfied in the bi-level ensemble. The regimes where our theorem applies are depicted in Figures 2a and 2b, and we validated our theory with numerical simulations of MNI with = 50 in Figures and 2d; see Appendix for more details on the experiments.
Theorem 3.3 (Main result). Under the same setup as Theorem 3.2, all the core weak-to-strong desiderata Desiderata l. to liii are satisfied under the following conditions:
fweak + Tweak
min {1 r, Tstrong
(Weak-to-strong generalization) (Weak model does not generalize)
0 Tweak-
where Tweak & Pweak + 1 2(qweak + Tweak) and Tstrong 2 + 1-11-22 2(q + r). In particular, the conditions the number of weak examples n2 are non-vacuous long
Tw2s p+l (g + Oweak + Tweak)) >> 0.
Note that under Assumption 2, Desideratum 1.ii is immediately satisfied since the weak features are spanned by the strong features. Also, as a sanity check, we confirm that whenever weak- to-s-ong generalization occurs with weak labels, the strong model would generalize with clean labels. By Theorem 3. if the strong model was instead trained on m = n clean examples, it would generalize whenever 2(q + r) p. By expanding the definition of Tstrong and using 9weak Tweak 1,
u. > Ownak + F Tweak Tstrong 2(g + r) p (gumak Twnnk 1) > 2(g + p.
which recovers the condition with m clean labels stated above.
'We expect weak imitation to occur as soon >> d if the models trained using gradient descent, i.c.
the classic underparameterized regime with weakly labeled datapoints than features.
7

---

Published as a conference paper at ICLR 2025
Remark 3,4 (Bonus desiderata). I >> u, as in the setup of Theorem 3.3, fails recover the spiked subspace (Shen et al., 2013; Fan & Wang. 2015), so the bonus Desideratum 2.1 automatically holds. Additionally, by using the condition for where the strong model fails with n clean examples from Theorem 3.1 (Tstrong < 0), one can construct parameter regimes where the bonus Desideratum 2. also holds. The theorem also implies the strong model cannot bootstrap its own performance. Indeed, some basic algebra shows Tu2s
Tstrong
Tweak if (p, q. = (Pweak: Qweaki Tweak).
We can extend the above result to the multilabel setting, which is a variant of multiclass classification where a datapoint can have multiple positive labels. The basic idea is that multilabel training can be approximated several independent binary classification problems, and then we can apply the binary analysis. Since this requires additional setup, we defer the formal details to Appendix D.
Theorem 3.5 (Informal, see Theorem D.3). Under the analogous assumptions as Theorem 3.3 for multilabel classification, there is weak-to st-sonnngg generalization for fw2s trained on m weakly hard multilabeled examples from weak in the exact same regimes.
The above result also suggests an interesting result for true multiclass problems with one-hot labels. In particular, one can use the multilabel scheme to generate weak multilabels for a multiclass weak-to- strong classifier fw2s- One can argue that whenever multilabel weak-to-strong generalization occurs, so too does multiclass weak-to- strrongg generalization (see Appendix D.1 for more justification). By comparing to the regimes for clean multiclass labels due Theorem 3.1, there exists regimes where the strong model would fail if trained using the same number of clean multiclass labels (i.e. only one positive label per example). At a high level, this can happen because there are too many classes, which sparsifies the label vectors. In contrast, the weak multilabels do not suffer from the sparsity issue, even though the underlying signal is noisier. This appears to be related to the strategy of using soft labels or logits in the pseudolabeling and knowledge distillation literature.
Redimo Baggon
Bery Ddagprn
2.0
2.0
pares
parer
3A
3.4
32-
12-
1/
13
10
(a) (g.r) = (1.4, 0.9, 0.4).
(0.9, 0.8). (Plwakk: 9wnskk Twnek)
(b) (g. r)
(0.9, 0.5),
(plweak Sanaie; Twnek)
(1.1, 0.1,0.9.022 0.2)
NN
MN
www.
tww
E-12
(c) (p. = (2,0.6, 0.6), (Pweak, Tweaks Tweak) (1.4,0.90055)
(d) (p, g. r) (165,0.6, (Pwesks Tweaks Tweak) (1.4,0.9, 0.5).
Figure 2: (Top): Regime plots for weak-to to-ronn generalization based on Theorem 3.3. The blue region is the successful w2s regime, and the red region where w2s training fails. The white region corresponds to regimes where either the hypotheses of the theorem fail to hold, or invalid settings of parameters for the bi-level ensemble. (Bottom): Comparison of simulations of MNI test accuracies for two different regimes where random guessing and how the weak-to-strong accuracy increases as m increases. As corroborated by the plots, Theorem 3.3 predicts w2s success in Figure 2c and failure in Figure 2d.
50. Observe how the weak accuracy is close to
8

---

Published as a conference paper at ICLR 2025
Finally, we state the aforementioned concentration inequality for the maximum of correlated Gaus- sians, which may be of independent interest. Our result complements the sharp bound of Lopes & Yao (2022) for more moderate deviations; the proof can be found in Appendix E.
Theorem 3.6 (Lower tail for correlated Gaussians). Let Pu E (0, 1) be parameter bounded away from and 1, and let (gi) be jointly Gaussian with zero mean and unit variance. Suppose Elg:9,] & Pu for all distinct i,j E [N]. For any 0 < iN du 2 Pu) log N where öu E [0, 1) is bounded away from 1, there is a constant C > 0 depending only on Po such that
IN & C..N. (c- (1 P0 (log
1-90(2-60)-66
Pr
max 9: [EIN
200
In particular, one can take C
V - If we further have E[ggyj po. for all distinct i, and
tN O
log log N: Ving N then Pr maxxE[N] 9: < [N] 2 (N- 7d (log N) 3H -1
3.1 TECHNICAL OVERVIEW
In this section, we illustrate the main ideas of the proof of Theorem 3.2. Recall that the true label is sgn(x.). where Is (grest, V.). Thus, studying weak-to-strone generalization amounts to analyzing
(6) where the fresh test point Øtest ~ (0, 2). Observe that conditioned on the training data X, the true Gaussian v, and (fw2s, Trest) are jointly Gaussian random variables, so there exist À IR and ~ 10, independent of x, such that
Pr(sgu( (fw2s (test)) sgn(x.)],
(fw2s Frest) Ar +
The exact value of À depends on exactly how much of æ, 's signal survives through the weak-to-strong training process. Intuitively, the larger À is, the higher the accuracy. Indeed, it is well-known from the classical study noise stability that the probability in Equation (6) is precisely 1 + x arctan(A).
To compute X,
Gram- Schmidt decompose fwzz to obtain the signal and noise with respect to x.. We term these quantities the survival and contamination of x., respectively. Without loss of generality, we can rotate to the basis U where the strong features drawn iid from (0, A),
where A diag(A1. (lag((A........ Aa). After applying the basis change, easily computes (fw2s Freat) N (0, ||Affas l22). The survival and contamination are then defined follows.
Definition (Survival and contamination). Let v E D be a unit vector and let { E RRd be a linear classifier for features drawn from N (0, Eieid )vv.o,) ), where UI,...,0d E IR are orthonormal. The survival and contamination of in is defined as
SU(e)
Σ SEld
Vx.f(e (v,, v)
CN(.) & v /IAfI SU(D)?
If f is trained by MNI on y sgn(44 (g. w)), we write SU, (mlw)) for the survival of given n labels generated w, and similarly for (v),.. In or w clear from context, we omit them.
To interpret these notions, consider the simple where 61 and v. Cs. which is the 1-sparse setting studied by previous papers. There, the survival is simply just [f and the contamination is / Ei>1 X; fi]: this was used to analyze binary classification in (Muthukumar et al., 2021).
In the weak-to-strong setting, we have (fw2s: (Ftest SU, (v, (eeek) + CN (v,, (M )g, where Tweak fweak/ [| is the unit-norm direction learned by the weak model, and g is standard Gaussian independent of z., Plugging in x. (g, v.) into (7) yields
Pr(sgn( SU,, (v. (week) x. + CN (v. (weak))) sgn (zn()
(8)
from which we can read off À = SUm(w. [eass)) Thus, the explicit formula for the probability yields (W..(e///uass.
that fwzs approaches perfect accuracy if and only if SUm (v, (aant) approaches random guessing if and only if SU.(v.. (Westt)
w(1). whereas its accuracy
CN... (v. ( (wwask)
(1).
CN., (aaak)

---

Published as a conference paper at ICLR 2025
We now turn to the strategy for controlling the survival and contamination. Using the explicit MNI for- mula for fweak and fwes. this amalysis reduces to controlling certain random bilinear forms. Applying standard eigenvalue concentration results and version of the Hanson- Wrrigttt concentration inequality for bilinear forms developed by Wu & Sahai (2024), we can precisely control the coordinates of fweak, and hence weakk- Once we have control over wwaak: we can then study fw2s-
One technical difficulty is that the weak labels are no longer 1-sparse, even if the true labels are. This marks a departure from previous analyses of benign overfitting in classification, which all assumed 1-sparse labels (Muthukumar et al., 2021; Wang et al., 2021; Wu & Sahai, 2024). To overcome this obstacle, we develop tools to analyze MNI beyond the 1-sparse regime, namely by using the Woodbury inversion formula and carefully bounding error terms using Hanson- Wright. Under the subset ensemble, the explicit parameterizations for the survival and contamination then yield the stated conditions for weak-to-strong generalization.
4 DISCUSSION
We now discuss further extensions which suggest interesting new weak-to-strong phenomena.
Modeling assumptions. In this paper, we assumed the features were Gaussian for the sake of theoretical tractability. One could relax this vector-subgaassian, as this notion is preserved under rotation. On the other hand, the bi-level and subset ensembles were chosen as a minimal set of tractable theoretical conditions study weak-to-strong generalization. In principle, our techniques could be extended to more complicated feature ensembles, but it would likely be quite involved.
As corroborated by our experiments in Figs. 2c and 2d, in practice one does not observe sharp transitions in test error from 1 to 0 using weak supervision - such a sharp transition corresponds to a Performance Gap Recovered (PGR) equal to in Burns et al. (2023) This phenomenon can nevertheless be justified by our theory. First, the transition we prove is asymptotic; the rate of convergence matters to predict the PGR for finite n. Another factor is the 1-sparse assumption for the true labels. We argue in Appendix G that this is essentially necessary to get this sharp transition in asymptotic test error. In practice, the true directions are rarely aligned with the eigenvectors of the covariance, the transition would instead between different constant levels of test error.
Weak imitation. Our main result Theorem 3.2 uses the subset ensemble Assumption 2 to establish two distinct phases of weak-to-stron, generalization. By adding a third intermediate eigenvalue level - thus relaxing the bi-level ensemble to a tri-level ensemble - and changing the relationship between the strong and weak basis, we expect a third distinct regime of weak imitation to occur in an overparameterized setting. At a high level, this can happen if the weak classifier puts most of its mass in its own unfavored direction v. but in the strong feature space v has intermediate level of favoring. Given enough weakly labeled datapoints, the strong model will eventually learn to imitate the weak model. Nevertheless, it is still possible for weak-to-strong generalization occur, with the regime for weak-to-strong generalization widening as the intermediate favoring level decreases.
Multiclass classification. By leveraging Theorem 3.1 and the techniques developed for binary and multilabel classification in the appendix. we expect our result to extend to the multiclass setting. The main technical challenge is controlling the expected weak -o-stoo- training behavior, which is significantly more complicated. However, multilahel weak supervision overcomes this challenge and more tractable to analyze, as discussed after Theorem 3.5.
Relevance to realistic settings. One connection to more realistic settings comes through the NTK perspective, as touched upon the introduction. To reiterate, if finetuning remains in the lazy training phase, then the supervised finetuning dynamics are captured by an appropriate generalized linear model defined by the NTK approximation. The strong and weak features are therefore learned from the pretraining phase. Another relevant setting is training linear probes on intermediate activations to interpret large models (Alain & Bengio, 2016; Marks & Tegmark, 2023; Nanda et al., 2023; Zou et al., 2023). Hence, under appropriate overparameterrizaioo of the intermediate activations, results also apply there. To go beyond classification problems, one could hope to use some recent implicit bias results for next token prediction (Thrampoulidis, 2024) study language models.
10

---

Published as a conference paper at ICLR 2025
ACKNOWLEDGMENTS
We would like to acknowledge support from an OpenAl Superalignment grant and NSF AST-2132700.
REFERENCES
Guillaume Alain and Yoshua Bengio. Understanding intermediate layers using linear classifier probes. arXiv preprint arXiv: 1610.01644, 2016.
Norah Alballa and Marco Canini. Practical insights into knowledge distillation for pre-trained models, 2024.
Eric Arazo, Diego Ortego, Paul Albert, Noel O'Connor, and Kevin McGuinness. Pseudo-labeling and confirmation bias in deep semi-supervised learning. In 2020 International joint conference on neural networks (IJCNN), pp. 1-8. IEEE, 2020.
Peter L Bartlett, Philip M Long, Gábor Lugosi, and Alexander Tsigler. Benign overfitting in linear regression. Proceedings of the National Academy of Sciences, 11 117744):30033-30077 2020.
Mikhail Belkin, Daniel Hsu, and Ji Xu. Two models of double descent for weak features. SIAM
Journal on Mathematics of Data Science, 167):1167-1180, 2020.
Kenneth Borup and Lars Nørvang Andersen. self-distillation for gaussian process regression and classification, 2023.
Cristian Buciluă, Rich Caruana, and Alexandru Niculescu-Mizze Model compression. In Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 535-541, 2006.
Collin Burns, Pavel Izmailov, Jan Hendrik Kirchner, Bowen Baker, Leo Gao, Leopold Aschenbrenner, Yining Chen, Adrien Ecoffet, Manas Joglekar. Jan Leike, et al. Weak-to-strong generalization: Eliciting strong capabilities with weak supervision. arXiv preprint arXiv:2312.09390 2023.
Paola Cascante-Bonitn Bonilla, Fuwen Tan, Yanjun Qi, and Vicente Ordonez. Curriculum labeling: Revis- iting pseudo-lahelin for semi-supervised learning. In Proceedings of the AAAI conference on artificial intelligence, volume 35, pp. 6912-6920, 2021.
Moses Charikar, Chirag Pabbaraju, and Kirankumar Shiragur. Quantifying the gain in weak-to-strong generalization. arXiv preprint arXiv:2405.1511 2024.
Niladri S Chatterji and Philip M Long. Finite-sample analysis of interpolating linear classifiers in the overparameterizee regime. Journal of Machine Learning Research, 22(129):1-30, 2021.
Richard Chen, Ming Lu, Tiffany Chen, Drew FK Williamson, and Faisal Mahmood. Synthetic data in machine learning for medicine and healthcare. Nature Biomedical Engineering, 5(6):
493-497, 2021.
Elisabetta Cornacchia, Francesca Mignacco, Rodrigo Veiga, Cédric Gerbelot, Bruno Loureiro, and Lenka Zdeborová. Learning curves for the multi-class teacher-student perceptron. Machine Learning: Science and Technology, 4(1) 4(1):015019, 2023.
Rudrajit Das and Sujay Sanghavi. Understanding aif-disillation in the presence label noise. In Andreas Krause, Emma Brunskill, Kyunghyun Cho. Barbara Engelhardt, Sivan Sabato, and Jonathan Scarlett (eds.), Proceedings of the 40th International Conference on Machine Learning, volume 202 of Proceedings of Machine Learning Research, pp. 7102-7140. PMLR, 23-29 Jul 2023. URL https: / ptw./eeooeeee/// ings mlr www.rrprsss//ee.m v 22..0//ddaa233 html.
Tim Dettmers, Artidoro Pagnoni, Ari Holtzman, and Luke Zettlemoyer. Qlora: Efficient finetuning of quantized llms. Advances Neural Information Processing Systems, 36. 2024.
Jianqing Fan and Weichen Wang. Asymptotics of empirical eigen sigentstructure for ultra-high dimensional spiked covariance model. arXiv preprint arXiv: 04733, 2015.

---

Published as a conference paper at ICLR 2025
Alvaro Figueira and Bruno Vaz. Survey synthetic data generation, evaluation methods and gans. Mathematics, 10(15):2733, 2022.
Jianping Gou, Baosheng Yu, Stephen J Maybank, and Dacheng Tao. Knowledge distillation: A survey. International Journal of Computer Vision, 129(6):189-11899 2021.
Jianyuan Guo, Hanting Chen, Chengcheng Wang, Kai Han, Chang Xu, and Yunhe Wang. Vision superalignment: Weak-to-strong generalization for vision foundation models. arXiv preprint arXiv:2402.03749, 2024.
Hrayr Harutyunyan. On information captured by neural networks: connections with memorization and generalization, 2023.
Peter Hase, Mohit Bansal, Peter Clark, and Sarah Wiegreffe.. The unreasonable effectiveness of easy training data for hard tasks. arXiv preprint arXiv:2401.0655/ 2024.
Chunming He, Kai Li, Yachao Zhang, Guoxia Xu, Longxiang Tang, Yulun Zhang, Zhenhua Guo, and Xiu Li. Weakly-supervised concealed object segmentation with sam-based pseudo labeling and multi-scale feature grouping. Advances in Neural Information Processing Systems, 36, 2024.
Geoffrey Hinton, Oriol Vinyals, and Jeff Dean. Distilling the knowledge in neural network. arXiv preprint arXiv:1503.0253/ 2015.
Jordan Hoffmann, Scbastian Borgeaud, Arthur Mensch, Elena Buchatskaya, Trevor Cai, Eliza Rutherford, Diego de Las Casas, Lisa Anne Hendricks, Johannes Welbl, Aidan Clark, et al. Training compute-optimal large language models. arXiv preprint arXiv:2203. 2022.
Chi Hong, Robert Birke, Pin- Yu Chen, and Lydia Y. Chen. On dark knowledge for distilling generators. In De-Nian Yang, Xing Xie, Vincent S. Tseng, Jian Pei, Jen-Wei Huang, and Jerry Chun-Wei Lin Advances in Knowledge Discovery and Data Mining, pp. 235-247, Singapore, 2024. Springer Nature Singapore. ISBN 777-9911997-2255
Neil Houlsby, Andrei Giurgiu, Stanislaw Jastrzebski, Bruna Morrone, Quentin De Laroussilhe, Andrea Gesmundo, Mona Attariyan, and Sylvain Gelly. Parameter-efficient transfer learning for nlp. In International conference on machine learning, pp. 2790-2799, PMLR, 2019.
Edward J Hu, Yelong Shen, Phillip Wallis, Zeyuan Allen-Zhu, Yuanzhi Li, Shean Wang. Lu Wang. and Weizhu Chen. Lora: Low-rank adaptation of large language models. arXiv preprint arXiv:2106.09668 2021.
Guangda Ji and Zhanxing Zhu. Knowledge distillation in wide neural networks: Risk bound, data efficiency and imperfect teacher. Advances in Neural Information Processing Systems, 33: 20823-20833, 2020.
Jiaming Ji, Boyuan Chen, Hantao Lou, Donghai Hong, Borong Zhang, Xuehai Pan, Juntao Dai, and Yaodong Yang. Aligner: Achieving efficient alignment through yeak-to-strong correction. arXiv preprint 16Xiv:2402.02446, 2024.
Ziwei Ji and Matus Telgarsky. Characterizing the implicit bias via primal-dual analysis. In Algorithmic Learning Theory, pp. 772-804. PMLR, 2021.
Jared Kaplan, Sam McCandlish, Tom Henighan, Tom B Brown, Benjamin Chess, Rewon Child, Scott Gray, Alec Radford, Jeffrey Wu, and Dario Amodei. Scaling laws for neural language models. arXiv preprint arXiv:2001.08323 2020.
Hunter Lang, David Sontag, and Aravindan Vijayaraghavan. Theoretical analysis of weak-to-strong generalization. arXiv preprint arXiv:2405. /6043, 2024.
Dong-Hyun Lee al. Pseudo-label: The simple and efficient seii-supervised learning method for deep neural networks. In Workshop on challenges in representation learning, ICML, volume 3, pp. 896. Atlanta, 2013.
Brian Lester, Rami Al-Rfou, and Noah Constant. The power of scale for parfmeter-efffiient prompt tuning. arXiv preprint arXiv: 104 004.08691, 2021.
12

---

Published as a conference paper at ICLR 2025
Haokun Liu, Derek Tam, Mohammed Mugeeth, Jay Mohta, Tenghao Huang, Mohit Bansal, and Colin A Raffel. Few-shot aarameter-efficien fine-tuning is better and cheaper than in-context learning. Advances in Neural Information Processing Systems, 35:1950- 1960-1996,000 2022.
Ruibo Liu, Jerry Wei, Fangyu Liu, Chenglei Si, Yanzhe Zhang, Jinmeng Rao, Steven Zheng, Daiyi Peng. Diyi Yang, Denny Zhou, et al. Best practices and lessons learned on synthetic data for language models. arXiv preprint arXiv:2404.07503, 2024.
Yuejiang Liu and Alexandre Alahi. Co-supervised learning: Improving weak-to- generalization with hierarchical mixture of experts. arXiv preprint arXiv:2402.15500, 2024.
Miles Lopes and Junwen Yao. sharp lower-tail bound for gaussian maxima with application to bootstrap methods in high dimensions. Electronic Journal of Statistics, 16(1):58-8) -3, 2022.
Samuel Marks and Max Tegmark. The geometry of truth: Emergent linear structure in large language model representations of true/false datasets. arXiv preprint arXiv:2310.068244 2023.
Song Mei and Andrea Montanari. The generalization error of random features regression: Precise asymptotics and the double descent curve. Communications on Pure and Applied Mathematics, 75 (4):667-766, 2022.
Hossein Mobahi, Mehrdad Farajtabar, and Peter Bartlett. Self-distillation amplifies regularization in hilbert space. Advances in Neural Information Processing Systems, 33:3351-3361, 2020.
Vidya Muthukumar, Kailas Vodrahalli, Vignesh Subramanian, and Anant Sahai. Harmless interpo- lation of noisy data in regression. IEEE Journal on Selected Areas in Information Theory, 1(1): 67-83, 2020.
Vidya Muthukumar, Adhyyan Narang, Vignesh Subramanian, Mikhail Belkin, Daniel Hsu, and Anant Sahai. Classification vs regression in overparameteriieed regimes: Does the loss function matter? Journal of Machine Learning Research, 22(222): 2021.
Vaishnavh Nagarajan, Aditya K Menon, Srinadh Bhojanapalli, Hossein Mobahi, and Sanjiv Ku- mar. On student-teacher deviations in distillation: does it pay disobey? In A. Oh, T. Naumann, A. Globerson, K. Saenko, M. Hardt, and S. Levine (eds.), Advances in Neu- ral Information Processing Systems, volume 36, pp. 5961-6000. Curran Associates, Inc.. wwwrips.cc/paapeeepeeeee cc/paper files/ hiiles/paper/222//
2023. URL attps::/proceedde file/1 (ttp:/2222222222ebeeeee wtw.lleeee4eeee22222222222222 f41 aaaaaaae02ee2a11111aaaaa---ooaea Canc---aaaae--Cfaeeeeeeeee pdf.
Neel Nanda, Andrew Lee, and Martin Wattenberg. Emergent linear representations in world models of self-supervised sequence models. arXiv preprint arXiv:2309.00941 2023.
Sergey Nikolenko. Synthetic data for deep learning, volume 174. Springer, 2021.
Utkarsh Ojha, Yuheng Li, Anirudh Sundara Rajan, Yingyu Liang, and Yong Jae Lee. What knowledge gets distilled in knowledge distillation?
In A. Oh, T. Naumann, A. Globerson, K. Saenko, M. Hardt, and S. Levine (eds.), Advances in Neural In- formation Processing Systems, volume 36, pp- 11037-11048. Curran Associates, Inc., 2023. URL https: http:/ppoceeennnneeeee neurips cc cc/paper files files/papess https//ppeee/2/////// FiLe/2443fe2214cccc wttp::4444ef5ffaeeeee httea//ffeeeeeecoceeaeaeeeeaaaaa -aap:eeeee---------------- Conferenceeeeeeeeeee pdf.
Mary Phuong and Christoph Lampert. Towards understanding knowledge distillation. In International conference on machine learning, pp. 5142-5151. PMLR, 2019.
Damián Pinasco, Ezequiel Smucler, and Ignacio Zalduendo. Orthant probabilities and the attainment of maxima on a vertex of simplex. Linear Algebra and its Applications, 610:785-803, 2021.
Mamshad Nayeem Rizve, Kevin Duarte, Yogesh S Rawat, and Mubarak Shah. In defense of pseudo- labeling: An uncertainty-awar pseudo-label selection framework for cemi-supervised learning. 2021.
arXiv preprint
13

---

Published as a conference paper at ICLR 2025
Mher Safaryan, Alexandra Peste, and Dan Alistarh. Knowledge distillation performs partial variance reduction. In A. Oh, T. Naumann, A. Globerson, K. Saenko, M. Hardt, and S. Levine (eds.), Advances in Neural Information Processing Systems, volume 36, pp. 75229-75258. Curran Asso- ciates, Inc., 2023. URL. ht.tps: 2023/ 1e/ee 7 Ffdde70662.ff111ecccccaaaaa33333
cc saapperr_fllse files/paper/
Felix Sarnthein, Gregor Bachmann, Sotiris Anagnostidis, and Thomas Hofmann. Random teachers are good teachers. In Andreas Krause, Emma Brunskill, Kyunghyun Cho, Barbara Engelhardt, Sivan Sabato, and Jonathan Scarlett (eds.), Proceedings of the 40th International Conference on Machine Learning, volume 202 of Proceedings of Machine Learning Research, pp. 3002233041, 23- 29 Jul 2023. URL https: / ptwppedinceensseeee mlr. press / w2w2/222222//// / /tss//aannttnnnneeee html.
Avi Schwarzschild, Eitan Borgnia, Arjun Gupta, Furong Huang. Uzi Vishkin, Micah Goldblum, and Tom Goldstein. Can you learn an algorithm? generalizing from easy to hard problems with recurrent networks. Advances in Neural Information Processing Systems, 34:6695-6706, 2021.
Dan Shen, Haipeng Shen, Hongtu Zhu, and JS Marron. Surprising asymptotic conical structure in critical sample eigen-directions. arXiv preprint arXiv:1303..617,, 2013,
Seamus Somerstep, Felipe Maia Polo, Moulinath Banerjee, Ya'acov Ritov, Mikhail Yurochkin, and Yuekai Sun. A statistical framework for weak-to-strong generalization. arXiv preprint arXiv:2405. 2024.
Samuel Stanton, Pavel Izmailov, Polina Kirichenko, Alexander A Alemi, and Andrew G Wilson. Does knowledge distillation really work? Advances in Neural Information Processing Systems, 34: 6906-6919, 2021.
Vignesh Subramanian, Rahul Arya, and Anant Sahai. Generalization for multiclass classification with overparameterized linear models. In Alice H. Oh, Alekh Agarwal, Danielle Belgrave, and Kyunghyun Cho (eds.), Advances in Neural Information Processing Systems, 2022. URL https: /pwp://eeeeeeeeeeeeeeeeeeeeeeee. net /eee/fooumte forum? siiddiikitt d==ikwMMVVVW...
Leitian Tao and Yixuan Li. Your weak Ilm is secretly strong teacher for alignment. arXiv preprint arXiv:2409.088/3, 2024.
Christos Thrampoulidis. Implicit bias of next-token prediction. arXiv preprint 11X1v:2402.18551 2024.
Roman Vershynin. Introduction to the non-asymptotic analysis of random matrices. arXiv preprint arXiv:1011.3027, 2010.
Guillaume Wang, Konstantin Donhauser, and Fanny Yang. Tight bounds for minimum form interpolation of noisy data. In International Conference on Artificial Intelligence and Statistics, pp. 10572-10602. PMLR, 2022a.
Ke Wang and Christos Thrampoulidis. Benign overfitting in binary classification of Gaussian mixtures. In ICASSP 2021-2021 IEEE International Conference Acoustics, Speech and Signal Processing (ICASSP), pp. 4030-4034. IEBE, 2021.
Ke Wang, Vidya Muthukumar, and Christos Thrampoulidis. Benign Overfitting in Multiclass Classification: All Roads Lead to Interpolation. arXiv e-prints, art. arXiv:2106.10865, June 2021.
Yizhong Wang, Yeganch Kordi, Swaroop Mishra, Alisa Liu, Noah A Smith, Daniel Khashabi, and Hannanch Hajishirzi. Self-instruct: Aligning language models with self-generated instructions. arXiv preprint 2xXx:2212.10066 2022b.
Alexander Wei, Wei Hu, and Jacob Steinhardt. More than toy: Random matrix models predict how real-world neural representations generalize. In Kamalika Chaudhuri, Stefanie Jegelka, Le Song, Csaba Szepesvari, Gang Niu, and Sivan Sabato (eds.), Proceedings of the 39th International Conference Machine Learning, volume 162 of Proceedings of Machine Learning Research, pp. 23549-23588. PMLR, 17-23 Jul 2022. URL https: : / pwwppedinse.g...ce//e/p//c mlr. www.ppressilee. 22a. html.
14

---

Published as a conference paper at ICLR 2025
Jason Wei, Maarten Bosma, Vincent Y Zhao, Kelvin Guu, Adams Wei Yu, Brian Lester, Nan Du, Andrew M Dai, and Quoe V Le. Finetuned language models are zero-shot learners. arXiv preprint arXiv:2109.01652, 2021.
David Wu and Anant Sahai. Precise asymptotic generalization for multiclass classification with overparameterized linear models. Advances in Neurul Information Processing Systems, 36, 2024.
Liuchi Xu, Jin Ren, Zhenhua Huang, Weishi Zheng, and Yunwen Chen. Improving knowledge distillation via head and tail categories. IEEE Transactions on Circuits and Systems for Video Technology, 34(5):3455-344)
2024. doi: 10. 101100/TCST222233335588.
Wenkai Yang. Shiqi Shen, Guangyao Shen, Zhi Gong, and Yankai Lin. Super (ficial)-alignment: Strong models may deceive weak models in weak-to-strong generalization. arXiv preprint arXiv:2406. 1 11431, 2024.
Hua Yuan, Yu Shi, Ning Xu, Xu Yang, Xin Geng, and Yong Rui. Learning from biased soft labels. Advances in Neural Information Processing Systems, 36, 2024.
Bowen Zhang, Yidong Wang. Wenxin Hou, Hao Wu, Jindong Wang. Manabu Okumura, and Takahiro Shinozaki. Flexmatch: Boosting semi-supervised learning with curriculum pseudo labeling. Advances in Neural Information Processing Systems, 34: 1811888811449 2021.
Edwin Zhang, Vincent Zhu, Naomi Saphra, Anat Kleiman, Benjamin L Edelman, Milind Tambe, Sham M Kakade, and Eran Malach. Transcendence: Generative models can outperform the experts that train them. arXiv preprint arXiv:2406.11744 2024.
Qingyue Zhao and Banghua Zhu, Towards the fundamental limits of knowledge transfer over finite domains, 2023.
Andy Zou, Long Phan, Sarah Chen, James Campbell, Phillip Guo, Richard Ren, Alexander Pan, Xuwang Yin, Mantas Mazeika, Ann-Kathrin Dombrowski, et al. Representation engineering: A top-down approach ai transparency. arXiv preprint arxiv:2310.01405, 2023.
A PRELIMINARIES
In this section, we lay out some preliminaries for the rigorous justification of our main results, and give a technical overview in Section 3.1 which motivates the study of the survival and contamination the signal, defined formally in Definition 3. In Appendix B, will introduce tools from high dimensional probability which can rigorously control the survival and contamination. In Appendix C, we will then use these tools to prove the main results of the paper for binary classification. Then, in Appendix D, we will discuss how the same exact proofs extend to the multilabel setting, and in Appendix we will prove tight lower tail inequality for correlated Gaussians which yields Theorem 1. In Appendix F we include some simulations validating in our theory, and finally in Appendix G we give a heuristic calculation which arrives at the same predictions for the weak-to-strong regimes which should lead to rigorous proofs even without the 1 --sparse assumption.
Notation. For positive integers n, we use the shorthand [n] [1, (I,...,Pu nJ. For a vector E R", [|ll|/ always denotes the Euclidean norm. We index entries by using square brackets or subscripts, whichever is clearer, so v[j] and By both denote the jth entry of v. For any matrix M Rm
Tr M M) denotes the Frobenius norm. If M E mR= is symmetric, we write μi (M) > u denote the ordered eigenvalues of M.
denote its ijth entry by maj- || ll2 denotes the spectral norm, and ||
pn un (M) to
We make extensive use of usymptotic notation. We say f(n) g(n) if f() O(g(n)), f(n) S (n) Ogg(n)
if (n) (g(n)), and f(n) Ö(g(n)) if I (n) log()))g(())) for some constant > 0. When we write (n) >> g(n). we mean that s(n) > nz for some constant > 0. An event E is said to hold with high probability if it holds with probability 1 1/n2 for some constant > 0, and very high probability it holds with probability 1 exp(-n" for some constant c > 0. For us, high probability statements will be taken with respect to n, the number of datapoints we scale the weak
g(n)
15

---

Published as a conference paper at ICLR 2025
and strong features with respect to, but under terminology it makes difference whether n or m because they are polynomially related.
In the weak-to-strong ensemble analysis, many of the expressions will depend q + r, but the number of datapoints involved will change. In an effort to reduce confusion, we introduce the following notation.
Definition 4 (Bi-level prefactor), If the covariance E = C(, q,r)) is drawn from the bi-level ensemble scaled with respect to n, then we define
a
In particular, + then Hn, < During weak supervision, the strong learner has bi-level features with covariance E(p, q.r) scaled with respect to and receives m = n weakly labeled examples. Hence, we define
am
pm
(10)
Remark A.1. Note that once a, s are fixed. pa is linear n.
B TOOLS FOR ANALYZING SURVIVAL AND CONTAMINATION
In this section, we introduce the basic machinery which can justify the heuristic calculations carried out in Appendix A. We will heavily rely on the analysis of Wu & Sahai (2024), so in an attempt to not replicate effort we will comment on how the proofs change in the weak-to-strong setting.
Basis change. Since we have bi-level data and the true direction v, is 1-sparse (Assumption 1). there are convenient basis changes which will greatly simplify the calculations. In particular, let be the spiked subspace of Σ, and t be any unit vector. Then any vectors in S are eigenvectors of Σ, so we can pick an eigenbasis U, so that Tistrong has independent coordinates, v, 1-sparse, and ur 3-sparse. We state this more formally in the following definition.
Definition 5 (Strong eigenbasis). Given E, V., and un as above, let U. be the distinguished eigenbasis of E such that after rotating to U.. we have Detrong N), v, ej, and 1iei + W262 Ws416s41.
Hanson Wright inequality. Now, we recall a few versions of the Hanson- -Wright inequality which handles bilinear forms between subgaussian vectors.
For the multiclass case, we also need handle potentially sparse vectors; this version was proved in Wu & Sahai (2024).
Theorem B.1 (Hanson-Wait Wright for bilinear forms with soft sparsity). Let x = (XI....,X., Xn) E R" and y E (Y,,..., Ya) In be random vectors such that (X;, Y.) are independent pairs of (possibly correlated) centered random variables such that [[Xill & and Y, has soft sparsity at level o, ie.
[V & 1 almost surely, and B[Y?)) & a. Assume that conditioned on Y, ||X & K. Then there exists an absolute constant >> such that for all M E Ruxaa and e 2 we have
KIM (1)
}):
Pr x T My - E[æ My > c) < 2ex
-omin
(11)
KKa M|
Because we are working with MNI. in a typical application we hope to set M = A A-1 However, in order apply Hanson- Wright, one needs to ensure that the matrix M is independent of and y.
Decorrelated Gram matrix. As we are working with Gaussian covariates, one way to achieve this decorrelate A with æ and y.
Definition 6 (Decorrelated Gram matrix), Let I,, (0,, A) be iid samples from a Gaussian distribution in RRd, Let R = {n(1), ,..... _b()) be an arbitrary set of orthonormal vectors in T&d and for each [0, let h() (li,,..,,ly, R. be the corresponding Gaussian observations, where h4 (11/2 gi, o())..
16

---

Published as a conference paper at ICLR 2025
Define the projection matrix onto R by Ig EvER vot. The R-projection of the data matrix XR [Rx is defined by
XR A XIlR,
and the R-decorrelated data matrix X n Ruxd is defined by
X-R X(I II = X XR.
The decorrelated Grum matrix is defined by
A-R X X- X(1 1RR When R = {1), will simply abbreviate {u} with Remark B.2. If R does not consist of orthonormal vectors, one can apply Gram-Schmidt first so that the above definition still makes sense.
It is not hard to show that as defined above, A_R is mutually independent of { yeler
Fact B.3. In the same setling Definition 6, A-R is mutually independent of (h()) Ja((
Proof. The fact that X- R is independent of the h, 's due to the fact that if g, are jointly Gaussian with zero mean and unit variance, then E[gh] is independent of h. This immediately generalizes to each row of X, since the entries are all independent for any row. Finally, as the rows are independent, the statement is proved.
To relate bilinear form against A to the original bilinear form against A- we will also need the Woodbury inversion formula for inverting the Gram matrix after decorrelating with various features.
Define the hat matrix for by
HR é X
(12)
These hat matrices appear in the Woodbury inversion formula. For the sake of notational compactness, define
MR X + Hn)
(13)
Fact B.4 (Woodbury inversion formula). We have
A-1 (XxX) A R1 A A x RRl + HR) -R)
(14)
A A MRA
(15)
Concentration of spectrum. Finally, in view of Hanson- Hanson-Wright Wright, we will need to control and Tr(A To this end, we control the spectrum of A- For any PSD matrix with eigenvalues A =
|
sorted in descending order and & [d], define the effective rank rk (E) Eieh We will use the following bounds adapted from Bartlett et al. (2020), which show that the effective rank of the covariance matrix controls the spectrum of the Gram matrix (and hence the sample covariance).
At
Lemma B.5 (Eigenvalue bounds from Bartlett et al. (2020)). Suppose that a ~ N E), where = TA Write A (i)) and let = XX B denote the Gram matrix for n iid observations of æ. If 1/22. z. where z has independent, unit variance, o(1)-subgaussian coordinates, the following holds.
[fr = w(n), then with very high probability
Tr(A) o(1) < pm (A) & (A) (MA))(++((1))
As a corollary, we show that in the regime q - r > 1 in the bi-level ensemble, decorrelating the Gram matrix with any sublinear number of jointly Gaussian random variables will yield flat matrix.
17

---

Published as a conference paper at ICLR 2025
Corollary B.6. Suppose that NO.. Σ), where E E R satisfies p1(Σ) ) and for any & = o(). we have pe (e( = d(1-o(1) (in particular, this holds if Σ follows the bi- level ensemble and q + > 1). Let R be an arbitrary set of orthonormal vectors in I2 such that [R = old), and let A Rn be the corresponding decorrelated Gram matrix for n iid observations of x in Definition 6. Then with very high probability.
d(1 on (1)) & pn (A- EM(AAR) & d(1+
Proof. First, note that the rows of X are iid samples from [(0, E-R), R), where Σ- (I IR) Rl).
Let L = [R] by assumption & old). Since 1 - 1T is projection matrix, we conclude by Cauchy
Interlacing that 14 RE_R) < 141 (x) and for {E 1,...,d), d] Mx(E) & (4(_RR) It follows that
r1 (E_R) = Tr(E-R)
Me (E)r((()
(1({__) R)
(I)
> d(1 d(1-o(1)) o(1))
(Assumption on Σ)
d/n
> wn)..
Thus Lemma B.5 implies that μ4 (4(An)) = d(1 = o(1) with high probability.
This leads to the following bounds on the spectra of A and the hat matrix H this generalizes Wu & Sahai (2024, Corollary B.5, Proposition B.6).
Lemma B.7. In the bi-level model, for any set of orthonormal vectors R with R = o(d), if > 1. then with very high probability we have
Tr Tr(A=1) = n² P1 o
|| | < (1+ (1))
X X lill <(n"))
A (HR) 1= o1)) i [d]
Proof. The first two statements are an immediate consequence of Corollary B.6. For the third, let S.T Rdd be the spiked and unspiked subspaces of Σ. Since Xa (Xs + I and using (A B)M(A+ B) = 2AMA+ + 2BMB, we have
XR 2X + II
Wu & Sahai (2024, Lemma I.1) implics that X $ 1 < 1- np" ====0= o(n") since q + > 1. On the other hand, since the law of X,r is rotationally invariant, one can view X. as Wishart matrix YYT where Y [R] Hence the concentration of singular values for matrix with independent subgaussian rows (see, e.g. Vershynin (2010, Theorem 5.39)) implies that with probability
X < <VVR + vn+ - + o(n²).
Combining this with the bound on X 5 2. we conclude that Xxx R 11 = o(nP).
For the last statement, since H 1 X R A X R. by applying the earlier bounds that μ4 (A-1)
(1 (1)) and X X onn)), we conclude that pi (HR) o(1).
Hanson- calculations. Combining the above results, we can establish a concentration inequality for the bilinear form 2, A-
18

---

Published as a conference paper at ICLR 2025
Proposition B.8. Let y sgn((g. w)) for some unit vector E R and R. be any set of orthonormal vectors such that span (R) 2 {ee, w and [R] = o(d). Then conditioned on A with probability 1 1-1
A - E|z, - & a |- log
where e1 is positive constant. Furthermore, under the bi-level scaling, if + r > 1, then with very high probability over A-), we have
2
3/2
E n
(1# arcsin(w;) d'
vn d
|ARRl = (1 on om (1))
Proof. Since A nt is independent of (Zi: y),
apply Theorem B.1 to obtain the first statement.
For the other two expressions, we can apply Lemma B.7 since we assumed + r > 1. We now compute the expectation using the noise stability formula:
E(z, A ky A Tr (1
3/2
arcsin(w:) Tr(A (rssin()))T((A))
(Noise stability)
3/2
(1 + on (1)) arcsin(ws)
(Lemma B.7)
where the last line holds with very high probability over A-1 Finally, for the last statement we have
A
1
Σ
Mil
(i(A 11)
kE(n]
Σ de o(1))
(Lemma B.7)
iE(n]
(1 + o()) V
d
B. CONTROLLING THE ERROR FROM WOODBURY
In the previous subsection, introduced some tools for obtaining concentration of the coefficients of the MNI classifier fstrong- The remaining survival and contamination reduce to understanding the typical behavior of bilinear forms 2 A A-1y. y. To do so, we work in the distinguished basis U. introduced in Definition 5. We thus pick R {ei, 62, 1,+1) and apply Hanson-Wrighh the bilinear form 2, A- The next lemma bounds the enror from replacing A-1 with A
Lemma B.9. Suppose are in the bi-level model, y sgn((g, w)), and q + 1. Suppose in the basis U., w = wi e1 + W2e2 + Ws+1 2.+1. Let R = {E1, e2; Be+1). With probability O(1nn). we have uniformly over i [d] that
2,- A y 2, A A
A X x A
Furthermore, the bi-level scaling we have with probability ((1/n) that
ÖWWmm'' '2²)
i i [2] i=st1
| A
xx
+n--p) ÖWWnn +
otherwise
and
[X] A Ahell : VVin((101 |uz Dn 1n + Ō((-2)) + |ws+1/rt- 1pp Ō(n
19

---

Published as a conference paper at ICLR 2025
Proof. By relating these two bilinear forms using Woodbury, have
2 -
| A MR A R
(Fact B.4)
< l
ス A X
A R 11
(Cauchy-Schwarz)
R
< (1 (1) A
X A R
(Lemma B.7)
remains to control above norms, which we achieve through another application of Hanson- Wright. Indeed, we can compute
|| A- x
E 25(2, A=)))
JE(1,2,+11
Now, by Saason--righht have with probability - 0 that
Ō(n²~2p) i=st1
(z A R=
((n)-2p) otherwise
Similarly we have with probability 1 1 )+) that
Ö(np-o-r--p) n 2 i E [2]
XP E (2 AmTAA>>;)) JE(2]
Ö((p-a-r n 22))
otherwise
Since n²-9-- >> 1 as p> >>>>
+ r and nº p- nl-p = pnn follows that with prohability 0
have simultaneously for i [d] that
Ö DlVTmm' 'T)
E [2]
| A x
Ō Ö(Vunn - & P Ö
i=
otherwise
A similar calculation, applying Proposition B.8, yields that
2 (2) 3/2 arcsin (w,) + Ō(vn)²
ie (1,2,++1)
(2. A=))))))²
(
otherwise
Hence,
VA ([wi(n + Ō(vT))
ATA A R2
11
Σ
11/1,2,+11}
'2" + -Ō(n-B)) + wworinn Ō(n2-p) I (1
This concludes the proof.
We can simplify the above emror bound greatly if w satisfies the 1-sparse assumption.
Corollary B.10 (Woodbury error under 1-sparse assumption), Suppose, in addition the assumptions of Lemma B.9, we have
where satisfies the 1-sparse assumption. In other words, in the U. basis we have U. = E1. Then we pick {Ei), and with probability O(2) we have
0(mm -n- i=1
T
< Ö n² nd- otherwise
B.2 SURVIVAL ANALYSIS
Let us first establish a general survival bound using Lemma B.9. Afterward, we present special cases under additional assumptions.
20

---

Published as a conference paper at ICLR 2025
Proposition B.11. = be drawn from the bi-level ensemble scaled with respect with q + + > 1. Suppose in the distinguished basis Us. we have w w1e1 1 + W2E2 + We w and set R {er, E2, e2,, ext1). Then, given labels generated by w, we have
3/2
T y
711+ o(1)) arcsin W1
+
+1
X
d
Proof. Recall our expressions for the survival:
(u/w)) Σ 112, A 1-11y (U,
(MNI)
iE(d]
where each label is generated by y; sgn( (g., w)).
Setting v v., the basis U, from Definition 5, the above expression simplifies to
SU, (v. (v) = 2 A A
Applying Woodbury (Fact B.4) with R w). have
= 2 A R - z A
Now apply Proposition B.8 conclude that
z A ny
" (1 + o(1) arcsin(w1)
< Ō
Vn
d
d
with probability - n= Now, triangle inequality and Lemma B.9 shows that
2 3/2
vn d
-
(1 + o(1)) aresin wh
S
Ō
+
||
A
x x
x A
Thus the statement follows.
By way of Corollary B.10, we get clean expression for the survival if w U. Corollary B.12. If + 1, v, satisfies the I-sparse assumption, and = sgn( (g. v.)). then with probability 1 - O(1/n)
z A A- y x
d
2 A y/
Vii d
Vi
1
SU, (v= (b.) x pn
Proof. If wo V.. then by Corollary B.10 the error bound simplifies to
1mmm 3) i=1 10pm 3) otherwise
A
x AAA
R3
Since q + 1, these error terms lower order, and the results follow.
We get similarly clean bound under a few additional assumptions and + Corollary B.13. If. in addition to the assumptions of Proposition B.I,, we have
(1) w/l w(y w(v logn for {1,2, +
wzl o((wil)
Vpnn -s E |w
21

---

Published as a conference paper at ICLR 2025
then with y4 sgn((gt, w)). we have
2 y d
aresin w1.
Furthermore, the survival of v. given labels generated by is with high probability
SU.(v.lw)) W1
(16)
Proof. Under the additional assumptions, then from Lemma B.9
X A x V wi +
(022)n== '7" +n" '
(wal w( log n n/ni))
vn wi 1 --->p
(wuz) o(ww)))) I))
Since i here, we can apply Lemma B.9 see that Woodbury error term is upper bounded by
A XR| Ö(Vpnn 222 Thus, the
ÖlVinn + (VHnlw I 7 + n PP
< 0( w0l (n- v/hn =))
x 0 wi wninnt-9 + o(n' ((nl-P/wor))
< o(n - (wil)
where the second line follows because we assumed Mn '78 < |wi/. and the last line follows because we assumed g > 1 so pn 1. Therefore, Proposition B.8 implies that
3/2 - + o()) aresin wi
2 A 2
P(
$ O( P) + d(n' "P arcsin((w1))
< Mo arcsin w1),
(w)) 3 wl
log n
which recovers the stated result.
B.3 CONTAMINATION ANALYSIS
We now move onto the contamination. Proposition B.14. Suppose satisfies the I-sparse assumption, and in the distinguished basis U. have v, = e₁ and ur Wiet + W262 + 1g-16s41- Under the same assumptions as Corollary 13, there datapoints, and +
then
(o. S o(/22//1 + n log(n)² + - -log(n)
(N,ww,/))² 2 pnnn-1+ + -
Furthermore, the lower bound holds even without the additional assumptions from Corollary B.13.
Proof. Since v. is 1-sparse, we have
CN(v./w)2
Σ ie (2,
Σ
(AizTA-'1 -
(17)
(1112,.+11
Since by definition w, for i & {1, 8 + 13. the second term Equation (17) can upper bounded up constant factors using Wu & Sahai (2024, Proposition A.2) by
M n log(n)² 2 + log(n) p log(n)² + ' loggn)).
Now, set R (e1, 62, ex+1). }. For the first term, we know from Lemma B.9 that
2 A A
2, A A
|| A A
x A |
22

---

Published as a conference paper at ICLR 2025
where
i=2
|| A
R
( + i=st1
and from our bounds in Proposition B.11, we have
| A hy 1| Z
Vunlwiln 2 + n
Hence we have
| A R
X
|
X A R <
On the other hand, we have
- 14
A RM
Un [n| In - p w1 + v Mnn
2 + + 2 2p
2 on + on (w))) + n=22pp
where the last line follows from the assumptions and p > 1. Putting these together with Hanson- Wright, we have
1 A A / < Ö(n + o(n
+ o(n #.+1 A y +((+t))+ - w/ =n2 2-22p
This yields an upper bound of
o ww (3) Ö(n
o(n 2- wT (3) 1p 01 (0113/1 13) + n
as > 1 and |wi| < 1. This completes the proof of the upper bound.
For the lower bound, careful inspection of the proof of Wu & Sahai (2024, Proposition A.2) reveals that, for + > 1, the lower bound holds for any multiclass problem with t > 0. This recovers the desired bound by simply lower bounding the second term in the expansion Equation (17), completing the proof.
C ANALYZING THE SUBSET ENSEMBLE
In this section, we prove Theorem 3.2, which establishes weak-to-strong generalization in the simple weak-to-strong subset ensemble. We restate it below for convenience.
Theorem 3.2 Weea--t-sttoong generalization for subset ensemble). Consider the setup in Procedure where the weak model fweak is MeNl--rained on correctly labeled examples and the strong model fw2s MNI-trained on m = n² weakly pseudolabeled examples, where + u and qweak + Tweak >> In addition, we make the following data ussumptions:
(1) The true binary labels are 1-sparse (Assumption for the strong covariance.
(2) The weak and strong features follow the subset ensemble (Assumption 2) with bi-level eigenvalues Mp, q, r) and Mppwaak Qweak, Tweak), respectively, scaled relative to n.
33) There are not too many weakly labeled examples: u p+l+gtr- (gaask + Twank)
Recall Tstrong - Ap - 1-211-2444 +r. Then, the resulting test error for fw2s satisfies
El((fw2s)] = [ (1)(1), 1 on(,,,
if Tweak + Tweak min {1 r, Tstrang }
(5)
Ownak + Tweak min {1 - r; Tstrong
Proof. The key idea of the proof is that, despite the error rate of the weak classifier being o(1). the weak classifier still has a noticeable amount mass on the true label defining direction. So long the error rate is not 0 ())))) ) which random guessing achieve, the strong learner can
23

---

Published as a conference paper at ICLR 2025
still pick up the signal contained in the weak labels. To make this precise, will control the coordinates fweak the distinguished basis (Definition 5).
Quantitatively, for the weak learner fweak. since have clean labels and gweak + Tweak > apply Corollary 12. Let we. Shaak? denote the bi-level prefactor for the weak model. Then we have with high probability
Smecat
the corollary shows that in the basis where
fweak [1]
FFweeakz A A
aweak tweak Tt
Sweak
dweak
1-Poost
Wn.weakf
whereas for all other coordinates we have with high probability
AFweeak
v
Mog v
i (2...., Sweak] }
If [t]]
dunsk
v
Vlggn n
i E {sweak + 1,... dweak }
V Pn.wweklt
Vlog
i E { Sweak)
72
Preak
Vlogn
E {Sweak + 1..... dweak]
Hence, obtain wwakk in U.. we first normalize fweak and then do the basis change. Some calculation yields
Sweak P.wekk + (dweak
Sweak Wu.we
ffweakl 2 weakn Prncak + n2
-Paca log n
dweak
wenk + log --m--Puuss
2 Porch log n
(Swnnkk + Tweakk 1)
where the second line follows because Sweak PPeeak (dwweak can compute a simple lower bound:
Sweak) Ae,
dweak- Similarly,
Il 11
Σ
(2) (2
y)
A-
Σ 2:2; A A
i>+11
n Paaak
(Lemma B.7)
We therefore obtain the sandwiching bounds
[|sweakk S 1- Parah Vlog
(18)
By rotating to the distinguished basis, since Qweak + Tweak 1, this yields
Sweak [lfweak
Week
Wie1 + Wye + Ws+16,+1
where
/og v Mn,weak Z W1 S V Pn,weak
(19)
log
1
Suask
[W S n
Sweak
log n
(20)
Wo+1l
(21)
Let us now check the conditions to apply Corollary B.13, keeping in mind we need to scale with respect m instead of n. In particular, require
Wt w(y
log for all i {1,2, s 1).
wwzl & wi
24

---

Published as a conference paper at ICLR 2025
Since going check the second condition, and clearly the first condition is satisfied for i = s + 1, suffices to check the first condition for i = 1. By plugging in the scaling for wi in
Equation (19), we have wo = w(y
log m
if
Qweak
Tweak
Qweak + Tweak < u + 1.
(22)
Let us now verify the second condition. It turns out that the second condition always holds under the bi-level parameterization. Indeed, from Equations (19) and (20), we always have
W2
Vlogn
& WI:
Vlogn
as wwaa < 1. Finally, for the third condition, we have
v Mmm
2u 2 (p+
r) < 1 - (Qweak + Tweak)
q+r> 2u (p - 1) + Qweak + Tweak (23)
With these preparations in hand, we now prove the positive side of the result.
Sufficient condition for weak-to-strong generalization.
First we lower bound SUm. (v, /Uwnaa))
Under Equations (22) and (23), we conclude that
SU m. strong (v, (weaa)) 2 Mm W1
Vlogn Mm
On the other hand, by Proposition 1.14 we have
CN (v, w) < of wi (1ll)/))))))))"))) + - n log n2 + n2 "P log n1.
We will now analyze the survival-oo-cottaminatoo ratio for the strong learner. The first term is clearly at least w1). For the second term, we get
log n
which is w(1) if
Oweak + Tweak < u +
(24)
Finally, for the third term, we get
48-9- 8- Monak Goeat 22
log 72
which is (11) if
Oweak + Tweak u +u+pp 1 2(g + r).
(25)
Collecting the conditions Equations (22), (24) and (25) yields
Gweak + Fweak min {1, 1 r, 1 2(q + r))
Oweak + Tweak min {1 r, + 1 2(g + rr)
which establishes the positive side of the result.
Sufficient condition for failure of weak-to-strong generalization. To get the negative result, we need to upper bound SUm stsooog U. (WWeak) and lower bound CN (v. (weak). Our earlier calculations and Proposition 1.14 yield
SU SU m, (v, (Uweea)) ) S Pm max { wn, n Vlogn
(26)
(Nm,,stonp (v. (ewkk) Z Pmn - + =
(27)
The above bound only differ by log factors from the upper bounds. Hence, in this case, the sufficient condition merely flips the direction of the inequality, which recovers the stated result, Otherwise, if
Oweak + T weak 1, then certainly u Qveak + Tweak 1+r r. and x /loog dominates. The
latter is in turn dominated by n - so the ctnpiiialtto-ootamnnnttti ratio is o(1). This completes the proof.
u
25

---

Published as a conference paper at ICLR 2025
D MULTILABEL CLASSIFICATION
In this section, we analyze multilabel classification with classes, which a variant of multiclass classification where single datapoint be positive examples of multiple classes. Given datapoints, encode this label enformation using label vectors y y where for i [Kt], we encode the ith label vector y (=1}", j", with representing positive examples. We make the following 1-sparse assumption for multilabel data.
Assumption 3 (1 (1-sparse assumption for multilabel). The label defining directions u. u. aligned with a top eigenbasis of the strong covariance E. In a strong eigenbasis where v. Ci have
y( - sgn(zz))
eje [k]
Remark D.I. In fact, the analysis below will turn oul to work even if the label defining directions are not orthogonal; they could all be the same! The analysis only relies on there existing some basis
U; such that ! = e1. However, the tight misclassification rate would be different depending on the relationship between the label defining directions.
The weak-to-strong setup is defined follows.
(1) Sweak E R.dos xk; train on n datapoints using weak features and ground-truth labels. (2) fwss E Rdxk; train on m >>> n datapoints using strong features and hard pseudolabels generated from fweak.
As before, we will study weak- took-tt-strong generalization using overparameterized linear classifiers. Hence, fweak will now consist of & differrntt linear classifiers f @R for i E [A]] all trained by MNI on n clean multilabel datapoints. To train (( we generate hard pseudolabel vectors ( sgn( (een((rei)) Frnak)), and then perform MNI on these hard pseudolabel vectors. We deem that multilabel classifier f generalizes if. for fresh test sample Irest and for every class i E [k]. f correctly labels whether Øtest is positive example of class i. More formally, define for collection of classifiers f f= ( (kk),, the loss function {(f) = Pr[3i E [k] ::gn]ggn" (g (xtest)) + Vrest). where the probability is taken over fresh test sample (Frestt Brest))
Remark D.2. The weak model can also be trained clean multiclass data rather than clean multilabel data. This will only affect the regimes for the weak model to satisfy Desideratum 1.iii, based on Theorem 3.1.
The subset ensemble definition is essentially the same as before (Assumption 2), with the main difference being that require all of the label defining directions to be favored and axis-alignable in both the weak and strong favored feature subspace.
Assumption 4 (Subset ensemble for multilabel classification). Lei A = A(p, q, E Rdddd denote the strong eigenvalues and Aweak A(pweak, Qweak, Tweak) E Rulees Xclaasi denote the weak eigenvalues, both drawn from the bi-level ensemble. Suppose the 1-sparse assumption (Assumption 1) holds for the strong covariance, with any disting eigenbasis U where (6) e, for E [K6]. The following conditions relate the weak and strong features after rotating to U.
Estrong A), where A (FI( \uT[())))
(2) There exists subsets of coordinates S [s], S [d] N Ms), with [k] C S and |S] Sweak such that
Tweak = (V Ag 1ls De
Actweak ) Dstrong N Aeweakks + AU.weakkT) Xg
The crucial observation is that multilabel training boils down to i (nearly) independent binary classification problems. The main difference establish successful generalization that we now need to union bound over all & multilabel classifiers. The high probability bounds from the binary analysis come from two sources: (1) applying spectral bounds (Lemma B.5), which holds with very high probability (xpp(nn/2)), and (2) Hanson-W Wright calculations (Proposition B.8), where bounds
26

---

Published as a conference paper at ICLR 2025
that hold with probability 5 have deviation poly log(1/8). Hence, for k constant, 5 is only affected by a constant, and this will only change the bounds in our amalysis by a constant, which does not shift the regimes. Furthermore, even if we allow & scale with n as in Definition 2, since & is polynomial in n. the dependence for the high probability bounds on is at most polylogarithmic in k, so again nothing changes with the analysis, which looks at polynomial regime shifts.
For the converse direction, one can use crude bound of just analyzing the probability of one classifier failing, which gives a error rate bounded from below by 2 On (1). However, we expect that more refined analysis would give the expected error rate of 1 - O(2=*); we sketch an argument for how to get this improved error rate after the theorem statement. With these minor modifications, the formal details go through unchanged, and we arrive at our main theorem for weak-to-strong multilabel classification using hard ascudd-multilabee
generalization for multilabel subset ensemble). Consider the setup where the weak model f trained on n correctly labeled examples and the strong model Juzs is trained on n" weakly labeled examples using MNI, where u < P. 9 4 u, and qweak + Tweak 1. Assume the following:
Theorem D.3
(1) The true multilabels satisfy the 1-sparse assumption (Assumption 3) for the strong covari- ance.
(2) The weak and strong features follow the subset ensemble (Assumption 2) with bi-level eigenvalues Mp, q, r) and M[Pweak Qweak, Tweak), respectively, scaled relative to
(3) There are not too many weakly labeled examples: p+1+gtr (gaest Tweek
Let Tstrong - ppt - -2(g + rr) Then, the resulting test ervor for fuzz satisfies
[on(1), if Qweak + Tweak
min {1 T, Tstrong
E[((fwas)]
(28)
[(11,
if Tweak + Fweak min {1 r, Tstrong
We now sketch out approach which should give the correct error rate for constant is (or even k growing slowly with n). Note that the complement of the failure event is
Vi E [M] sgn( ( :rrest) Veest
From the Gram-Schmice decomposition Equation (8) and the noise stability formula, we can decom- pose this event
Vi E [A] sgn
SU( w) CN( (w)
1 + (0)) sgn(x.")
where 2: grest: v. and (()) are iid standard Gaussians. the converse regime, the survival
to contamination ratio is polynomially decaying, so for typical (()) with probability exp(-n") we have sgn( SU( [w) x. (6)
+ ()) = sgn(g()), Furthermore, by unpacking on the analysis of f
CN(C un)
(specifically, see Equation (20)) for i A j. (نو and gقكو only differ by a Gaussian with polynomially decaying variance, so to a failure event with probability exp(-n"), we can replace these with the
same Gaussian which is independent of both 2 and ( We can do this for all pairs (i. and union bound over & (this is where we use the slow growing condition on k). Hence, up to these error
terms, which are negligible, the complementary event occurs with probability 2 so the test error will indeed be 1 - 0(2 k).
D.1 MULTILABEL SUPERVISION FOR MULTICLASS CLASSIFICATION
In this section, we expand upon the arguments to use weak multilabel supervision to train a weak- to-strong multiclass classifier fw2s- The difficulty of the multiclass analysis is studying the MNI behavior for weak supervision. However, since the multilabel MNI behavior is well under control by the arguments above, it is tractable to study this setup instead.
The key insight is that, for multiclass classification to succeed, it suffices to look at pairwise com- parisons between the score functions for the l different classes (see Wu & Sahai (2024) for more
27

---

Published as a conference paper at ICLR 2025
justification). In particular, one studies the relative survival given different class label vectors:
SU SU( - ( (weak):
with the signal component for class being the above quantity with v = v. One can then define the relative contamination in analogous way. However, the path towards studying the survival comes from understanding the coefficients of fweak and fwzs. which is feasible.
Thus, to determine whether fw2s generalizes for multiclass classification, it reduces back down to the multilabel/binary behavior. As argued in Wu & Sahai (2024), because of the margin between the features and the survivals, it suffices get polynomially increasing SU/CN ratio. Hence, in the successful regime for weak-to-strong multilabel generalization, this relative SU/CN ratio is polynomially increasing, which implies that multiclass classification succeeds.
E IMPROVING THE BOUNDS FOR MISCLASSIFICATTION RATE
In this section we tighten the bounds on misclassification rate for the multiclass setting.
Theorem E.1 (Tightening of (Wu & Sahai, 2024, Proposition A.7)). Assume we in the bi-level ensemble model (Definition 1), the true data generating process is 1-sparse (Assumption 1). and the number of classes follows the scaling defined in Definition 2. Then, in the negative regime where the model does not achieve vanishing error, we have
Elé(fstrong] = =1 1 (
(29)
where the expectation taken over the randomness of the training data and the test point.
At high level, the misclassification event Eerr is governed by the following inequality holding:
SU max Jzyl CN,, jE(k] [E[
& max Jr:
where (x))) are iid standard normals, and (g:)Ee) are jointly gaussian with some correlation structure.
Now, (Wu & Sahai, 2024, Proposition A.3) implies that SU < n for some constant u >> 0 with CN.
probability - O(1 /n). Also, we can upper bound max |at & O(ylog)) with probability at least 1 (1/k). Moreover, in the regime where classification fails, we know that from (Wu & Sahai, 2024, Proposition F.I), we have that E[g:9,] < 1/2 + n for some constant > 0 with probability at least 1 1- O(1nn). Since i o(n), when we union bound over the above events, they get absorbed by the (-) and 12-)) terms.
To tighten the misclassification rate, we will improve upon (Lopes & Yao, 2022. Theorem 2.1). In particular, we shows the following lower tail inequality for the maximum of correlated gaussians. We will prove the following theorem, which captures the lower tail behavior of the maximum of correalted Gaussians very far from its expectation. This result complements the lower tail bound of Lopes Yao (2022), which holds for more moderate deviations.
Theorem 3.6 (Lower tail for correlated Gaussians). Let Po E (0, 1) be parameter bounded away from 0 and 1, and let (gi) (g)) be jointly Gaussian with zero mean and wnit variance. Suppose Elg.9,] & Po for all distinct i E [N]. For any 0 & tx do / /2(1 Po) log N where Sn E [0, 1) is bounded away from 1, there is a constant C > 0 depending only on Po such that
Pr
max 91 & tNN [EIN]
CC. (1--6)
Pa (log N)
1-20(2-60)-6
2P0
In particular, one can take C
مo_ If we further have E[ggg, Po. for all distinct i, and V
T-Po
ty O( log log N vlng N then Pr [maxie[N] 9: tN] θ (N' 3 (log N) 2no
Before we prove the theorem, let us how it tightens the misclasstifeation rate.
28

---

Published as a conference paper at ICLR 2025
Proof of Theorem E.I. We will apply Theorem 3.6 with N k - 1, Pu ++ tnn and d0 log
Noting that 6b / 2(1 Po) log k 2 n n" if l = C&n" for any t E [0, 1), we see that
Pr [mamax 9i < n "]
Pr[mmx4 9s < 60 / po) log k]
(ōu V 2(1 pu) log k 3 n n)
(E[R]
iElki
0 k (1 1--00 60) (1+n $1 (log 1:)" s -
(Theorem 3.6)
0 h - (1- (log k) (1 + on (1))
(km = + On (1))
0 (1-66)²
(log k) 5012 -0022
oK (1))
(6p 1/ log k)
Inverting this bound, we that
n "] "1= (
Pr|max 9: iE[k]
For the upper bound on the above probability, we can use Slepian's lemma and then compare to Gaussians 9: which have correlation 2 -n Writing it all out, we have
Prfmax Ii & n "] ic[k]
Pr Øi & nn
(Slepian's lemma)
iE|k]
Pr[max gr < 0] EE(M
> Ω
(Pinasco et al., 2021, Theorem 2.1))
bl+n-a
Ω
(ka="= =1 + on (1))
from which we get nearly matching upper bound on the probability of 22 ())-
We return to the proof of Theorem 3.6.
Proof of Theorem 3.6. The lower bound directly follows from the proof of Lopes & Yao (2022), so we focus on proving the upper bound. We remark that the constant hidden by θ can be pinpointed to (1+ (1))
but we will not discuss this further. T-po
Pa
To reduce confusion, we will attempt to follow the notation and treatment from Lopes & Yao (2022). To prove the upper bound, all i + j. Then, we can explicitly decompose
Slepian's 's lemma reduce to the where Elg.g] Po for
P + V pohi.
where xr h; are iid standard Gaussians. Via this decomposition, we can write an integral representation for the desired probability:
Primax 9i < [N]] [ (i(sdss N
(30)
(bs) A ((s) (AN-
v Pos
ds,
(31)
Po
where o(.) and o(-) are the standard Gaussian density and CDF, respectively. We will estimate this integral by splitting it into a couple pieces. To this end, we will bound the Gaussian CDF using Mills'
inequality. For any & >>> 0, we have
1 12 ((1) < +()) (-1)) < 70(1)
29

---

Published as a conference paper at ICLR 2025
We will need the following multiplicatiie estimate 4b (.), which holds for any d [0, 1]:
s log N(1
5)) (1 $ 20(-V2log N(1 8)))
1 V2TNil 632 (v [22 N(1-))+
(Mill's inequality)
< exp
N1-016022
(32)
(Po
The above bound (32) yields nontrivial bounds only when d > decays superpolynomially if
e clog log log
for a constant >>>
1 i and
These bounds motivate splitting (31) into few different pieces, based on which term dominates the behavior of the integral v. To this end, let cN, dN be parameters we specify shortly, Then we split the integral into three pieces:
dy
(s))
(ss
(b)s ds
-N
dx
As in Lopes & Yao (2022), we define Okp
A ( - 1)(1 50)² and So
T- Then the ultimate
80-11 bound we want prove is - ds & 0 No N~ N)
We explain the choice of CN, oN > 0 as follows. For succinctness, we introduce the following two functions on R:
2(1 Po) log N u=
/200 log N
sN(u)= &
Po
(s(s) A IN /pus
VI Po
and reparameterize the interval [-CN, dvv as another interval on below.
1. We want cy to satisfy o(-cx) = 0 N- (log N) 0--1 be bounded by
Given this, the first term can
CN
cxN ((s) ds = ((-ox) & x0 Nao (log N)
80
(5) ds <
By inverting Mills' inequality, we see that it suffices to pick
2(1 Po) log N
(1 (1-50- 10-00-
log log
CN
(33)
Po
4 log N
log log N
SN
1 80
4log
Indeed, we have for sufficiently large N that
log log 2
4(-cx) < p(CN)
exp
- Oup log N(1 4(1 4(1-50) lng N
ON
2n
2( (1 -1) N(1 ON (1))
Po
N a0
(log.N
00 (30 = 1-
1= 2.
2. We pick dN such that n. (fN(-dN)) < Noo we evidently have
1 (log N)
Given this, by monotonicity
L dn
Nac (log N) 11
1
((s) < x x2 (fx(-dw)) <
30

---

Published as a conference paper at ICLR 2025
Owing (32), to achieve the desired superpolynomial decay it suffices to pick dN 2 0 such that fxr o-t PPodx VT-Po < V2llog ((1 + E) log log N ). where & 0 a constant. log N
Recalling that tN 60 2 po) log N, we see that fN(-dN) 2llog Noo
pP dv. Hence the desired inequality holds by picking VI-po
2(1 Po) N dN V
log log N log N
(1-80 (2 +
(34)
Po
log log N log N
1 - 50 ( +)
Given the above choices of cN, dy in Eqs, (33) and (34), we see that the interval Z that belongs to 60 -
& [1 - 6g - ? + =) log log
log log Hence, it is natural to reparameterize the log N
log N
integral in terms of ry [o. =] via the following change of variables
(n + 4) log log N
un(1) 1 -o do
log N
and an easy computation yields
V200 log log dn 1- dg log N
ds = s'N (onn()))))(il (m)
It is not hard to see that uN ( 1/2 + = l-NN, for the compositions of our changes of variable:
Let us introduce the following abbreviations
(n() A (N((n(n))
Tw(n)= & (N)(((n)) = 22 N (1- (n 1) log log N log N
In this notation, have
dN (s) V200 log log N
/
1/246 (x(((1)) dn
I- d0 log N
ex
Now the argument in (Lopes & Yao, 2022. Eq. 4.22) shows that this integral is
O(N-=0(log N) 2n 2 which completes the proof of the first part of the theorem. 6 However, let us give alternative proof which is bit simpler. We will estimate the integral by performing Riemann sum with subintervals of width > O, which we pick to satisfy Bor < and such that evenly divides 1 Then, we have
1/2+E
1/2+8
(k+1))
(x)(
<
((3x(n)) dn
kr
k=
By monotonicity, for any ls we have
fri (k+1)r
(6x((1)) dn <T T. (0 1)7) (f (FN(k)))
KT
CC.. N) 80 80 +2(k+1)7)
N) 2Kr). (arr)
where C is universal constant. Here, the last line used d53N (n)) O(N-aa (log N) 2.00 and V (fN (n)) = NV
2)2 200 +n))
If 23 (k + 1)r < }, then 2k 1)7 > 1. then Bor < J. we have 2k
Ing lng (log ()) < (log NN as desired. On the other hand, log N
T3 0. Since exp(- N)2kT) dominates
any polylog terms, so is not hard to see that the total contribution here < N N (log N) "o-1
Hence, we conclude that -ー (s)s) ds V I
Po
No N) 8u-1 as desired.
N
TTo be explicit, their calculation requires verify that /2 N N(60 ux(n)) w(1), which is certainly truc.
31

---

Published as a conference paper at ICLR 2025
F EXPERIMENTS
In this section, we describe the simulations we conducted to validate the theory. We generated Gaussian data following the subset ensembles specified in the figures, and constructed two linear models from them: the MNI classifier and the simple averaging classifier. In the averaging classifier, we average over the positive examples of label, which approximates the behavior of the first few iterations of gradient descent. In contrast, the MNI classifier governs the asymptotic behavior of gradient descent.
The weak-to-strong behavior for these two learning algorithms was compared to two other baselines: the weak accuracy for feek and the accuracy for the strong model trained on m clean labels: fstrong. The test accuracies were evaluated on fets 100 fresh datapoints. We ran 8 independent trials to train weak with n 50 so that we could explore how the weak-to-strong behavior scales with p and For each fweak, conducted 16 independent trials to train fw2s.
We swept out u using five equally spaced points in [1, 1.3]. In Figures and 4, we show the results of the averaging and MNI experiments, respectively, for four different slices. In the top row, we show two slices where the theory predicts weak-to-strong generalization to occur for MNI, and the bottom row we show two slices where the theory predicts failure of wcak-to-strong generalization. The error bars show the estimated 95% CI over all sources of uncertainty in the inner and outer loop (fw2s and fweak). In both the averaging and MNI plots, the theory successfully predicts whether weak-to-strong generalization occurs. Furthermore, in every plot the ground truth trained strong model fstrong trained Another interesting experimental observation is that the averaging classifier does significantly better than MNI in non-asy con-asymptotic settings. This corroborates the view of practitioners of the benefits of carly-stopping for gradient descent.
clean labels has better accuracy than fwnak and fwzs, as expected.
G HEURISTIC CALCULATIONS
Recall from the definition of MNI that
ftrrng =
where y E 1 is a label vector generated by either the true feature v. or a weak feature Tweak and A = X E Rnx= is the Gram matrix. The key to our analysis is studying the survival and contamination of various features when the labels are possibly generated by another feature. Recall that we performed basis change X XU, so that the strong features are drawn iid from (0.
Writing the transformed data matrix now as
X = 2\
Vi222
Vdaza]
where each z; N0,, I,), we obtain for any unit norm e R that
SU(w)= Σ
2 A (vi, v)
(MNI)
iE (d]
CN(2) = (Miz, (- (1i, 3)
(Orthonornality of v;)
iE[d
Since A is close to dI, the isotropic case, and we are working in the regime where PCA fails to extract the bi-level structure (q + >>>>> 1), one could hope for the best and pretend that A L.a. This step is not rigorous, but we will justify these approximations in Appendix B.
Based on the decompositions in Definition 3, we study the case where y sgn( (g. w)) for some w E R but we want to recover the planted direction v E RR.. For a subspace V C R D and a vector 2, let uy denote the projection of u onto V. For axis-aligned subspaces V [d], this just corresponds to restricting to the coordinates in V. To simplify the heuristic calculation, we will make the following assumptions.
Assumption 5. Let S = [s] denote the spiked subspace after the basis change, and let a, > 0 be parameters possibly depending on n. For any vector u E RRd, let Tu, A {i JiES: S: lui| = w( (ax)
32

---

Published as a conference paper at ICLR 2025
Averaging
Averaging
weak
ground truth
ground truth
0.9
0.9
10st 605
0.8
0.6
0.8
6x16'
10"
8=10'
m
(a) (p.g.r) 0., 0.6), (Pweak; Tweaks Tweak) (1.4, 0.5).
(b) (p.g,r) (2.099.0.). (Pweak, Qweak, Tweak)
(1.4,0.90.4)
Averaging
Averaging
1.0
w2s
1.0
w22 ground
gr ground
0.9
0.9
0001 ao5
0.9
acc
0.7
0.7
0.5
6x166'
10¹
6x 10'
10"
(c) (p.q,r) (1.5,0.6, 0.8), (Presk, Pwesk: Twesk) 0.9.0.
(d) (p. r)) = (2, 0.4), (Presic Pweak; Tweak) (1.4, 0.9,
Figure 3: Comparison of test accuracies for four different models using averaging training. The r-axis plots m, the number of additional labeled datapoints. The models are trained using class averaging, which approximates the behavior of the initial few gradient descent iterations. Note how the weak model has low accuracy, whereas the weak-to-strone accuracies that increase as m increases. The top row Figures 3a and 3b are in a regime where we predict MNI weak-to-strong generalization succeed, whereas the bottom row Figures 3c and 3d depict regimes where we expect MNI weak-to-strong generalization to fail.
model and ground truth have higher
denote the spiked coordinates where is large, and Ru = S \ Tu denote the spiked coordinates where u is small.
We assume the following holds for T = Tw and R = Rw:
We have (vr, wr) = a 12l1/ In other words, v and have correlation a restricted to the heavy coordinates for w.
We have Eier of
0²11 W Note that by LP norm inequalities we always have
(3) We have R| = D(s), i.e. constant fraction of w spiked coordinates are small.
Remark G.I. When v = w. Item (2) can be thought of as a relaxed notion of u being 1-sparse; for given p one should roughly think of v being p -sparse.
33

---

Published as a conference paper at ICLR 2025
MNI
1.0
weak
ground Iruth
ground Iruth
0.9
0.9
10st 606
0.8
0.6
0.6
0.5
6=16'
10'
8=10'
m
(a) (p.g.r) (2, 0.6), (Pweak: Tweak, Tweak) 0.9,0.9...5
(b) (p.g,r) (2,0.9.05)) (Pweak, Bweak, Tweak) (1.4,0.9,055)
MNI
MNI
1.0
w2s
1.0
w2s ground
gr 3round
0.9
0.9
8001 aoc
0.8
acc
0.7
0.7
0.5
0.5
6x16''
10¹
6x 10'
10"
(c) (p. (p. = (1.5, 0.6, 0.8), (Preak, Pwesk: Tweek)) 0.9.
(d) (p. ()) = (2, 0.4), (Presks Pweak, Tweak) (1.4,0.9.0.4
Figure 4: Comparison of MNI test accuracies for four different models. Observe how the woak-to- strong accuracy increases m increases. Again, the top row Figures 4a and 4b are in regime where we predict MNI weak-to-strong generalization to succeed, whereas the bottom row Figures 4c and 4d depict regimes where we expect MNI weak-to-strong generalization to fail. The plots corroborate these theoretical predictions.
Survival bound. Recall that y = sgn( (g. w)). By applying the noise stability formula again and the fact that zig ~ N NO, 1), we deduce that
D y] n.E [zgyv]
= Prisgun = y, E[|,|] - (1 - Pr[sgn(2y) = E|a,1
V 2 (2Pr(sgn(2s) y/} 1)
3/2 arcsin wt;
where in the second to last line we have used the fact that the expected magnitude of standard Gaussian is v2/.T, and in the last line we have used the noise stability formula. By standard concentration inequalities, the deviations will be of order O(vR), As the behavior of 2 aresin(z) x
2x for small x, we deduce that the expectation will dominate whenever |w:] J
We will now plug in the bi-level scaling, Recall that X = A ad for E [s] and X du (1-a)d d-s
for i >>
34

---

Published as a conference paper at ICLR 2025
Thus, ignoring constants, with high probability should have
SU(o/w) Us aresin wy + AFVR Σ
AFn d
Σ iE
+
AU
v
Σ
Vi.
d iERw
$38
Observe that
2 aresin 2 & |z],
π
for all x E [-1,1].
Consequently, for i E Tw. each summand contributes vs aresin(w;) = ((vwus). Thus, by Item (1)
and the definition of Xp, the first term is ((a en - ll WT... 12)-
For the second term, we will upper bound its magnitude by
XP
VRR l vn
on
| ll2
(Rw S S)
an
([ell 1)
Vn
Finally, for the third term, since Ei>. us| < ||l|| & Vd, after plugging in the definition of Ay, obtain the asymptotics
SU(
s x an (a. 12 l12ll Wr
n
(35)
d
Note that for the first term to dominate, we must have a (2()). Also, if we want improve our estimate on the second term, we can further split it by Tu. we can gain and get deviations of order
Σ iER
U
Vi
URn Mor
112
+
(Definition of R.p)
Vn
To
R..
UR nTo l1 +
Vn
yielding an ultimate relative deviation of Ii + 5. This is significantly better if, say (To)
Vn
o(s). as it allows us to beat the contamination bounds which have relative deviations V
Contamination bound. For succinctness, introduce the shorthand h? = (1 - -vf) (2) y)² Then the squared contamination is
22(v = Σ
2 v
A 212
A
sE(d!
1
Σ
X
(A-1 R (T))
iE|d
x
Σ
Σ
n
d
TTT.
i....
X2,n² ?
23,n d²
(1- aresin w
(d s).
d²
d2
TET
RER
where in the last line we have used the observation that the expectation of hy dominates if and only if i Te.
The reason this is not an equality is that there might be some heavy wis which disagree in sign with o/s, but
for the settings we consider this estimate will be true.
35

---

Published as a conference paper at ICLR 2025
The first term can be bounded (up to constants)
an
Σ
(1
uu
a.7
WT....
1221 p²).
(Item (2))
sET
For the second term, we can bound up to constants as
2
R
|| R.
Σ
(1-
1,)
8
n
8
71
ant
2 |Rw
(|u122 = 1)
Finally, the third term can be bounded by 3. Putting these together, we conclude that
CN(wlw)
VI p² WT ll
Rawl n
V
(36)
n
Let Un, on In our regime, Pn < because g r >> Combining Equations (35) and (36) yields
SU(w)w) CN (N(vvw)
Un [1| UT |12|| lla +
n 1li
+
+
d
(37)
Pn [ p²
+
+ VV
Hence, for the survival to contamination ratio to grow with n, we need
PT ll2
>>
p2
(Weak supervision)
R
UT
11
WT
112
> V
(Favored contamination)
n
ll2
n
Let us put these scalings together to predict the scaling regimes for weak-to-strong generalization. For strong generalization, have U. and y sgn((g, v.)). From the discussion in Section 3.1, we know that the strong learner generalizes if
SU(v.lv.) (1), CN(v.
and fails generalize if the ratio on (1). Under Assumption have e1, T. Tup {1}. a = 1, and = 1, and the expression simplifies to
SU(u.lu.) (N(v.lo.)
Pn
which under the bi-level parameter scaling verifies the conditions for ground truth supervision.
This completes the proof sketch; it remains to justify the above estimates rigorously. In the subsequent subsections, we will assume that the above scalings of the survival and contamination are correct and them to deduce that the 1-sparse assumption necessary get sharp transition in the test error. These calculations can be upgraded to rigorous proofs using the tools are developed in Appendix B.
G.1 THE NECESSITY OF 1- S-SAARSE ASSUMPTION
Let's suppose we get clean labels from sgn( (g. v)) and want to learn the unit vector v. We will abbreviate T = T. Tu. In this case, we have a = and p²
| in Assumption 5.
[or
36

---

Published as a conference paper at ICLR 2025
Lemma G.2. Suppose given labels according and want to learn Then, the survival to contamination ratio is wn(1) only if
|/ 11 ||0||1
- o(1).
In particular, the above condition holds only if the following two conditions hold:
(1) -1 -1-12-1--10011 o(1).
(2) For each E T, either o(1 = 1 o(1).
The upshot is that having 1-sparse labels is necessary for obtaining asymptotically perfect general- ization.
Proof. Hence, focusing only the survival terms coming from T, which are the only relevant coordinates for learning, and lower bounding the contamination with just the T terms, we have
(U( CN(olv)
|UT 11
UT ll
|U 12 1
Py
By
Mr
where the last inequality used the fact that v is unit norm. This proves the first necessary condition.
We show that || or 1|2 = 1 - (11, then the second set of necessary conditions hold.
Indeed, for the first claim, suppose || < 1 for some constant s >> 0. The I.P norm inequalities contradiction. For the
imply that || || & (1 - e)ll the ratio most second claim, suppose instead there is coordinate with of
for some constant E (0, 1).
Then, we have ||eraoll 11 < || < E, but then | < (1 s)² + < 1- -((s), contradiction.
37


Reviews:
[{"review_id": "yMmRjPYOxZ", "reviewer": "Reviewer_Ns5A", "summary": "The paper investigates weak-to-strong generalization in the setting of an overparameterized spiked covariance model with Gaussian covariates. The paper identifies an asymptotic phase transition between successful and unsuccessful generalization.", "questions": "1. The main setup is quite confusing to me. The paper first states that \"$f_{weak} \\in \\mathbb{R}^d$\" is the object we learn. Normally, the model is a function, not a vector, so this was not immediately clear. It is defined later in line 347 how we learn $ f $, which is quite far from where it was introduced (line 184). It would be better to define that we train $f$ by MNI earlier.\n\n2. In line 201, it says, \"As a consequence of our main results in Section 3, we will show that the above desiderata are achievable in a simple toy model; see Theorem 3.3 for a formal statement.\" However, Theorem 3.3 only considers desiderata 1.2 and 2.1, not the entirety of the desiderata.\n\n3. What is \"$t$\" in Equation (3) of Theorem 3.1?\n\n4. The notation $ u, p, q, r $ used is not very intuitive, and it makes the result difficult to interpret. Is there a simpler way to rephrase the result?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "The math appears correct to me; the problem is significant, and desiderata 1 and desiderata 2 make sense.", "weaknesses": "The paper is rather technical, and the clarity could be improved significantly to make it more readable. (see questions)", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "AvF27rZgv3", "reviewer": "Reviewer_vRgg", "summary": "The papers identifies a specific setting under which weak to strong generalization occurs. Consider a strong model that learns a classifier on strong features of the data by supervised learning on $m$ weak labels given by a weak model that was trained on weak features on $n$ clean labels. Then weak to strong generalization implies that \n\nCondition 1):  The strong model has perfect classification accuracy whereas the weak model has close to random accuracy. \n\nCondition 2): The generalization is due to weak labels, i.e. if the strong model was only trained on $n$ clean labels, there is no generalization.\n \nThe setting is as follows: A learner observes features distributed according to a Gaussian distribution, $x \\sim N(0, \\Lambda)$ where $\\Lambda$ is diagonal covariance matrix following a bilevel ensemble parameterization \n\\begin{equation}\\lambda_j = \\lambda_F =  \\frac{ad}{s} \\text{ for } 1 \\leq j \\leq s \\text{ otherwise } \\lambda_j = \\lambda_U = \\frac{(1-a)d}{d-s}\\end{equation}\nwhere $d = n^p, s= n^r, a = n^{-q}$ and $p > 1; q, r >0; q+ r < p$. For multiclass setting, classes are further scaled as $k = c_k n^t$ for some $t<r$.  The strong model observes features given by some $p, q, r$ and weak model observes features  characterized through $p_{weak}, q_{weak}, r_{weak}$. In particular the strong features $x_{strong}$ and weak features $x_{weak}$ are given as \n$$ x_{strong} = N(0, \\lambda_F I_{[s]} + \\Lambda_U I_{[d]/[s]}) $$\n$$ x_{weak} = N(0, \\lambda_{F, weak} \\Pi_S + \\Lambda_{U, weak} \\Pi_T)$$\nfor some subsets $S \\subseteq [s], T \\subseteq [d]/[s]$ and $\\Pi_S$ denotes projection onto axis aligned subspace indexed by $S$. $\\lambda_{F, weak}  = \\frac{a_{weak}d_{weak}}{s_{weak}}$ and $\\Lambda_{U, weak} =  \\frac{(1-a_{weak})d_{weak}}{d_{weak}-s_{weak}}$.\n\n The true labels are given by $y = \\text{sign}(x_1)$ for binary classification and $y = \\arg\\max_k (x_1, \\dots x_K)$ for $K$ way classification. \n\n\n \nIn this parameterized setting, the authors show that there is a particular regime of number of weak labels $m$ provided by the weak model (for certain regimes of $p, q, r, p_{weak}, q_{weak}, r_{weak}$) where weak to strong generalization occurs (condition 1) holds). The conditions (for binary classification) are given by (assuming $m = n^u$)\n\n1. $u + \\min(1 -r,  p + 1 - 2(q + r)) > q_{weak}+r_{weak} > (p_{weak} + 1)/ 2$\n2. $p + 1   >  (q + r + q_{weak} + r_{weak})$\n3. $u < (p + 1 + q + r  - (q_{weak} + r_{weak})/ 2)$ \n\nFurther the classification error of strong learner trained on $n$ cleaned labels is shown to be depend as \n$$1/2 - 1/\\pi \\arctan (\\Theta(n^{p+1 - 2(q+r)}))$$\n\nThus they claim one can identify regimes under which condition 2) also holds (possibly when $p+1 - 2(q+r) << 1$) although no details are provided).\n\nFurther they provide an informal claim and details in appendix that there exists some regime for multi class setting.", "questions": "Suggestions:\n\n1. Reduce the introduction - it currently spans 2 pages. \n2. Figure 1 is useless.\n3. The section on data model was not particularly needed. Page 5 and 6 can be compressed into 1 or 2 paragraphs.\n4. Include some experiments in main body.\n\nIn general the paper is quite verbose, it can be compressed substantially and content moved back into main body.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "Exact characterization of the regime where weak to strong generalization occurs in terms of parameters of the covariance matrix of strong and weak features.", "weaknesses": "Most of the important details are pushed into appendix. The main body only contains one useful theorem which identifies a certain condition where condition 1) of weak to strong generalization holds. Setting for condition 2) and multi class settings are merely mentioned as claims. The main body also does not provide proof sketch or provide insights into the proof of the theorem.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "kCDVYKXpjH", "reviewer": "Reviewer_P4ZD", "summary": "In this work, the authors provide theretical justification for the empirically observed phenomenon of weak to strong generalization. In this setting, a weak learner is used to created labelled examples (from unlabelled training data) that is used to further train a stronger model. The intuition is that the weak learner has learnt some useful information about the ground truth and hence the pseudolabels it generates will actually enable generalization. The authors prove that this weak to strong generalization has two phases: (1) when the number of pseudolabelled examples is less than some threshold, the strong learner behaves like a random guesser, (2) beyond the threshold the strong learner achieves perfect generalization. A technically interesting tool that they use is a new lower tail for the max of correlated gaussians which could be of independent interest.", "questions": "21) What the the word \"represent\" mean in Desiredata 1.(ii).\n2) What is the significance of the bi-level-ensemble? \n3) What is $t$ in Theorem 3.1?\n4) Is there a reason for choosing a halfspace for the ground truth? Does this analysis extend to other concepts. Is there a similar notion for regression (rather than classification)?", "limitations": "", "rating": 8, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "1) This work addresses the important problem of obtaining theoretical justification for a frequently encountered empirical phenomenon\n2) The lower tail for max of correlated gaussians is an interesting result.", "weaknesses": "See questions.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "XIi4Yj7QSx", "reviewer": "Reviewer_ww6B", "summary": "This paper studies a toy-model for weak-to-strong generalization. They show that under the assumptions of their toy-model, two asymptotic phases occur for the student: (1) it is able to successfully generalize or (2) the student resorts to effectively random guessing. The authors also try to extend their results to weak-to-strong multiclass classification and derive new lower tail inequalities for the max of correlated gaussians.", "questions": "See weaknesses above. It would be nice if the authors can address these.", "limitations": "", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "- The paper studies a phenomenon that has been empirically observed and thus relevant to practice\n- The results and proof techniques seem non-trivial and interesting", "weaknesses": "I find the organization and presentation a bit confusing and hard to parse. In particular, Theorem 3.3 is hard to interpret without referencing the Desiradatum outlined in Section 2. Ideally, Theorem 3.3 should be standalone and at the very least, the variables in Theorem 3.3 like $\\tau_{weak}, p_{weak}, ...$ should be defined. In addition, and in my opinion, the notation and current presentation of the result doesn't really make it seem like this is a \"simple, toy model\", given how many free variables there are to keep track of.  One possible fix is to give more intuition and less notation about the toy-model in the main text, and push the details into the Appendix. For example, I think it would be really helpful to have an informal, non-rigorous theorem summarizing the main result in the Main Contributions section.\n\nIn addition, I am not sure what to take away from this paper. It is nice that you found a toy example, where you can provide rigorous evidence of the empirical phenomena of weak-to-strong generalization. However, I am not convinced this toy model is realistic/relevant to practice, even after reading the Modeling assumptions in the Discussion. In short, it would be nice if the authors can answer:\n-  **why** one should care about finding a \"simple, concrete theoretical setting where we can provably exhibit different phases of weak-to-strong generalization?\" \n- what can I take away from this result?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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:

Decision: Accept (Poster)