Provable Weak-to-Strong Generalization via Benign Overfitting

1 Introduction

• The setup inverts classic teacher-student learning by having a weak teacher generate imperfect pseudolabels for a stronger student.Weak-to-strong generalization was introduced by Burns et al. (2023), who reported strong performance on standard benchmarks but failures on harder tasks.Source: §1 · p. 1
• The central question is whether a simple theoretical setting can exhibit different phases of weak-to-strong generalization.Source: §1 · p. 1
• The analysis connects weak-to-strong generalization to pseudolabeling, synthetic data, supervised finetuning, scaling laws, and knowledge distillation.The paper studies interpolating linear models as an idealized analogue of finetuning or linear probing under Gaussian features.Source: §1 · pp. 1–2
• Related theory suggests that generalization may arise when the learning cascade purifies representations in true directions and contracts false directions.Mobahi et al. (2020) emphasize the regularizing role of Gram-matrix eigenvalues in self-distillation.Source: §1 · p. 2

1.1 Contributions

• The paper proves two asymptotic phases: increasing weakly labeled examples can move the strong learner from random guessing to perfect generalization.The result holds in an overparameterized spiked covariance model with minimum ℓ2-norm interpolation.Source: §1.1 · p. 3
• The paper’s concrete model assumes the weak teacher is an interpolating linear model representable by the strong student.The authors note that the results can generalize to weak teachers producing logits through a linear head.Source: §1.1 · p. 3

2.1 Weak-to-strong setup

• The setup targets binary classification with n clean weak-model examples and m ≫ n strong-model examples, reflecting scarce labeled data and abundant unlabeled data.Source: §2.1 · p. 3
• The weak-to-strong setting uses weak and strong feature sets related through a subset ensemble, so strong features can represent the weak model while favoring the true direction more.The label-defining direction lies in the span of both feature sets.Source: §2.1 · p. 3, §2.2 · pp. 5–6, Figure 1 · p. 6
• Using real-valued weak logits instead of hard pseudolabels changes only constants that are not crucial to the stated results.Source: §2.1 · p. 4
• Weak-to-strong generalization requires the strong model to generalize, represent the weak model, and coexist with a weak model whose error asymptotically equals random guessing.The strong model may therefore imitate the weak labels while still extracting signal from many pseudolabeled examples.Source: §2.1 · p. 4

2.2 Data model

• The data model uses zero-mean Gaussian covariates with unknown learner-specific covariances and labels generated by signs or multiclass maxima of hidden directions.The label directions satisfy sparsity and alignment assumptions relative to covariance eigenvectors.Source: §2.2 · pp. 4–5
• The bi-level ensemble scales the feature dimension as d = np and the low-rank subspace dimension as s = nr, with d ≫ n and s ≪ n.For multiclass classification, the number of classes can also scale with n.Source: §2.2 · p. 5

2.3 Learning algorithm

• Minimum ℓ2-norm interpolation fits the training labels and yields coefficients X⊤(XX⊤)^−1y, with predictions formed by the sign or largest class score.The procedure corresponds to the asymptotic behavior of zero-initialized gradient descent.Source: §2.3 · p. 6
• The procedure trains a weak MNI model on n clean examples, then trains a strong MNI model on m unlabeled examples with the weak model’s hard pseudolabels.The weak and strong learners observe corresponding weak and strong features for the additional examples.Source: §2.1 · p. 3, §2.3 · p. 6

3 Main results

• The main binary result assumes 1-sparse true labels, a bi-level subset ensemble, and an upper bound on the number of weakly labeled examples.The theorem focuses on q + r > u and qweak + rweak > 1, with additional parameter restrictions stated in the theorem.Source: §3 · p. 7
• Weak-to-strong generalization occurs when the strong model receives sufficiently many weak binary labels, under the theorem’s parameter conditions.The condition is non-vacuous, and Figure 2 provides numerical simulations supporting the predicted success and failure regimes.Source: §3 · p. 7
• Theorem 3.3 identifies regimes where weak-to-strong generalization satisfies all three core desiderata under the stated bi-level ensemble assumptions.These include weak labels that asymptotically resemble random guessing, strong imitation of weak labels, and strong-model generalization.Source: §3 · p. 7
• Weak-to-strong success requires a positive combined threshold, τw2s = p + 1 − (q + r + qweak + rweak) > 0, together with the theorem’s sample-size conditions.The weak-label requirement is stricter than the corresponding clean-label condition by the excess weak-feature contribution qweak + rweak − 1.Source: §3 · p. 8
• PCA cannot recover the spiked subspace in the theorem’s regime, and there are regimes where weak-to-strong training succeeds although the strong model cannot bootstrap itself from clean labels.The bonus desiderata also include cases where the strong model fails with the same number of clean examples.Source: §3 · p. 8
• The multilabel extension treats training as several approximately independent binary problems and achieves weak-to-strong generalization in the same regimes as the binary theorem.The informal Theorem 3.5 applies under analogous assumptions to weakly hard multilabeled examples.Source: §3 · p. 8
• For multiclass problems, weak multilabel supervision can avoid label-vector sparsity that harms clean one-hot supervision, motivating soft labels or logits when available.The paper argues that some regimes favor weak multilabels despite their noisier underlying signal.Source: §3 · p. 8

3.1 Technical overview

• The proof tracks signal survival and noise contamination through minimum-norm interpolation, using concentration tools and extensions beyond 1-sparse labels.A new lower-tail inequality for maxima of correlated Gaussians tightens binary and multiclass error analyses and may be independently useful.Source: §3 · pp. 7–8, §3.1 · p. 10

4 Discussion

• The theory assumes Gaussian features and tractable bi-level or subset ensembles; extending it to more complicated feature ensembles would likely be involved.Source: §4 · p. 10
• Sharp asymptotic transitions need not appear in practice because finite-n convergence and the 1-sparse true-label assumption affect observed test-error transitions.When true directions are not covariance eigenvectors, the transition is expected between different constant test-error levels rather than from 1/2 to 0.Source: §4 · p. 10
• A tri-level ensemble may produce a third weak-imitation regime in which the strong model eventually imitates the weak classifier, while weak-to-strong generalization can still occur.The weak-to-strong regime is expected to widen as the intermediate favoring level decreases.Source: §4 · pp. 10–11
• Multiclass extension is expected in principle, but controlling expected weak-to-strong training behavior is substantially more difficult than in the multilabel setting.The multilabel formulation is more tractable because it avoids this technical challenge.Source: §4 · p. 11
• Under lazy fine-tuning, an NTK generalized linear model can represent the dynamics, allowing the results to apply to sufficiently overparameterized intermediate activations and linear probes.The discussion also points toward studying beyond-classification problems using implicit-bias results for next-token prediction.Source: §4 · p. 11

A Preliminaries

• The preliminaries define notation, asymptotic probability conventions, and bi-level prefactors used to state the subsequent survival and contamination results.Source: A Preliminaries · p. 16

B Tools for analyzing survival and contamination

• The analysis uses a distinguished eigenbasis in which strong features are independent, the planted direction is 1-sparse, and relevant comparison vectors have only a few coordinates.Source: B Tools for analyzing survival and… · p. 16
• A soft-sparsity Hanson-Wright inequality controls bilinear forms when paired variables may be correlated, provided the matrix is independent of those variables.Gaussian decorrelation supplies that independence in the paper's applications, with additional handling for sparse multiclass vectors.Source: B Tools for analyzing survival and… · p. 17
• Decorrelating the Gram matrix from selected Gaussian features makes the residual matrix independent of the corresponding observations, enabling concentration arguments for bilinear forms.The construction also supports Woodbury-based comparisons between decorrelated and original inverses.Source: B Tools for analyzing survival and… · p. 17
• Effective-rank eigenvalue bounds and interlacing control the spectrum after projection onto a sublinear feature set.Source: B Tools for analyzing survival and… · p. 18
• In the bi-level model with q + r > 1, decorrelation by any sublinear set of features yields a flat Gram matrix spectrum with very high probability.The corresponding eigenvalues satisfy µ_i(A−R) = d(1 ± o(1)) with high probability.Source: B Tools for analyzing survival and… · p. 18
• For sign labels generated by a direction w, Proposition B.8 gives concentration bounds for the relevant bilinear forms, including high-probability simplifications under bi-level scaling.Source: B Tools for analyzing survival and… · p. 19

B.1 Controlling the error from Woodbury

• The analysis proceeds by selecting R = {e1, e2, es+1} so that the relevant signal and weak-feature directions are decorrelated before applying concentration bounds.Source: §B.1 · p. 20
• Under q + r > 1, Lemma B.9 bounds uniformly over coordinates the error from replacing A−1 with the inverse of the decorrelated Gram matrix.The proof combines Woodbury with Hanson-Wright bounds in the distinguished eigenbasis.Source: §B.1 · p. 20
• The general error expression contains contributions from the relevant coordinates and lower-order terms controlled by the bi-level scaling.Source: §B.1 · pp. 20–21
• When the comparison direction equals the 1-sparse planted direction, choosing R = {e1} yields a substantially cleaner Woodbury error bound.Source: §B.1 · p. 21

B.2 Survival analysis

• The section first establishes a general survival bound and then specializes it under assumptions that simplify the Woodbury error.Source: §B.2 · pp. 21–22
• Proposition B.11 gives the general high-probability survival of the planted direction when labels are generated by a direction with three relevant coordinates.The resulting expression depends on the leading alignment component and the bi-level scaling.Source: §B.2 · p. 21
• The survival calculation uses labels y_i = sgn(⟨g_i, w⟩) and evaluates the signal component after expressing the classifier in the distinguished basis.Source: §B.2 · p. 21
• For labels generated directly by the 1-sparse planted direction, Corollary B.12 reduces survival to a clean expression because the remaining error terms are lower order when q + r > 1.Source: §B.2 · p. 22
• Additional assumptions on w and q + r yield a similarly clean survival bound, with the leading dependence involving arcsin(w1).Source: §B.2 · pp. 21–22

• When q + r > 1, Proposition B.14 bounds the relevant strong-learner quantity under a 1-sparse label direction and specified distinguished-basis coordinates.The lower bound remains valid even without Corollary B.13’s additional assumptions.Source: §B.3 · p. 23
• The proof controls the first term using Lemma B.9 and the remaining contribution using bounds derived from the bi-level model and Gaussian concentration.The argument specializes to R = {e1, e2, es+1} and combines coordinate bounds with Hanson–Wright estimates.Source: §B.3 · p. 23
• The resulting contamination estimates complete matching upper- and lower-bound arguments for the relevant survival and contamination terms.The lower-bound proof invokes Wu and Sahai (2024, Proposition A.2) and applies to multiclass problems with t ⩾ 0.Source: §B.3 · p. 23

• Theorem 3.2 gives weak-to-strong generalization when m = n^u weakly pseudolabeled examples satisfy q + r > u and qweak + rweak > 1, under the stated data assumptions.The analysis assumes 1-sparse strong labels, bi-level subset features, and a bound on the number of weakly labeled examples.Source: C Analyzing the subset ensemble · p. 24
• The strong learner’s test error is o(1) if u > qweak + rweak − min {1 − r, τstrong}, and 1/2 − o(1) if the inequality is reversed.Here τstrong = p + 1 − 2(q + r).Source: C Analyzing the subset ensemble · p. 24
• The weak classifier can retain signal despite an error rate approaching random guessing, because its distinguished-basis coordinates preserve mass in the true label direction.The weak-model prefactor and coordinate bounds are used to transfer this signal into the strong learner’s analysis.Source: C Analyzing the subset ensemble · p. 24
• The positive regime follows by lower bounding signal survival and showing the survival-to-contamination ratio grows polynomially under the collected conditions.The sufficient condition is u > qweak + rweak − min {1 − r, p + 1 − 2(q + r)}.Source: C Analyzing the subset ensemble · pp. 25–26
• In the failure regime, contamination dominates survival, yielding a ratio o(1) under the complementary parameter conditions.The proof uses the corresponding upper and lower bounds and distinguishes the case u < qweak + rweak − 1.Source: C Analyzing the subset ensemble · p. 26

D Multilabel classification

• The analysis permits label-defining directions that are nonorthogonal, but their relationship changes the tight misclassification rate.The directions may even coincide, provided the required basis representation exists.Source: D Multilabel classification · p. 26
• Multilabel training decomposes into k nearly independent binary classifiers, with a union bound over classes preserving the polynomial-regime thresholds.For constant or polynomially growing k, the additional dependence is at most polylogarithmic and does not shift the regimes.Source: D Multilabel classification · p. 27
• The basic converse gives error at least 1/2 − o(1), while a refined argument is expected to yield 1 − O(2^-k) in the failure regime.The refined estimate uses shared Gaussian behavior across classes and a union bound when k grows slowly with n.Source: D Multilabel classification · pp. 27–28
• For multilabel classification, the strong learner’s test error is o(1) above the same threshold and Ω(1) below it: u compared with qweak + rweak − min {1 − r, τstrong}.Theorem D.3 assumes 1-sparse multilabel directions, bi-level subset features, q + r > u, and qweak + rweak > 1.Source: D Multilabel classification · pp. 27–28

D.1 Multilabel supervision for multiclass classification

• Multilabel supervision can support multiclass classification because pairwise class-score comparisons reduce the multiclass question to multilabel or binary survival-versus-contamination behavior.In the successful multilabel regime, the relative survival-to-contamination ratio grows polynomially, implying multiclass success.Source: §D.1 · p. 28

• Theorem E.1 tightens the previous multiclass misclassification bound under the bi-level ensemble, 1-sparse labels, and the stated class-number scaling.The result is obtained by applying the new correlated-Gaussian lower-tail theorem to the multiclass error event.Source: E Improving the bounds for… · pp. 28–29
• The new result complements Lopes and Yao (2022, Theorem 2.1) by controlling deviations farther below the expectation.The paper uses it to improve existing binary and multiclass error rates in the bi-level ensemble.Source: E Improving the bounds for… · p. 29
• Theorem 3.6 gives a lower-tail inequality for the maximum of jointly Gaussian variables with pairwise correlations bounded by ρ0, including a sharper equicorrelated case.The threshold scales with (1 − ρ0) log N and the constants depend only on ρ0.Source: E Improving the bounds for… · p. 29
• The proof reduces general correlations to the equicorrelated case using Slepian’s lemma, decomposes the variables into independent Gaussians, and estimates the resulting integral with Mills’ inequality.The integral is split into regions selected to obtain polynomial or superpolynomial decay.Source: E Improving the bounds for… · pp. 29–30
• The resulting bounds are nontrivial beyond a log-logarithmic deviation scale and become superpolynomially small for larger deviations.The stated threshold behavior depends on the constant multiplying log log N / log N.Source: E Improving the bounds for… · p. 30

F Experiments

• Theory correctly predicts whether weak-to-strong generalization occurs in both averaging and MNI experiments.The experiments include slices predicted to succeed and fail.Source: F Experiments · p. 33
• The clean-label strong model fstrong has higher test accuracy than both the weak model fweak and weak-to-strong model fw2s in every plot.Test accuracy is evaluated on 100 fresh datapoints, with repeated trials for the weak and weak-to-strong models.Source: F Experiments · pp. 32–33
• Averaging significantly outperforms MNI in non-asymptotic settings, supporting the practical benefits of early stopping for gradient descent.The comparison concerns finite-sample behavior rather than the asymptotic MNI regime.Source: F Experiments · p. 33
• Averaging-classifier experiments compare weak, weak-to-strong, and ground-truth models as m increases, with success predicted in the top row and failure in the bottom row.Class averaging approximates the first few gradient-descent iterations.Source: F Experiments · p. 32, Figure 3 · p. 33
• MNI experiments show weak-to-strong accuracy increasing with m in predicted-success regimes, while predicted-failure regimes remain consistent with theory.The plots corroborate the theoretical predictions.Source: F Experiments · p. 33, Figure 4 · p. 34

G Heuristic calculations

• The heuristic proof sketch relies on approximating A^-1 by d^-1I_d in the isotropic regime, with rigorous justification deferred to Appendix B.This approximation is explicitly identified as non-rigorous within the sketch.Source: G Heuristic calculations · pp. 35, 37
• The heuristic requires sufficient alignment between planted and weak features, with the leading survival term proportional to their heavy-coordinate correlation α.The first term dominates only when α is at least of the relevant s-dependent order.Source: G Heuristic calculations · p. 36
• Splitting coordinates by heavy and light spiked features improves deviation bounds, particularly when the relevant support size satisfies |T_v| = o(s).This sharper deviation can beat the contamination bounds in the considered regime.Source: G Heuristic calculations · p. 36
• Under bi-level scaling with q + r > 1, the weak-feature covariance scale satisfies μ_n ≪ 1, shaping the contamination analysis.The strong learner receives m = n^u weakly labeled examples.Source: G Heuristic calculations · p. 37
• Weak-to-strong generalization is predicted when the survival-to-contamination ratio grows with n; failure occurs when this ratio is o_n(1).The analysis treats survival of the planted signal and contamination from other features as the governing terms.Source: G Heuristic calculations · p. 37
• For ground-truth supervision, v* = e_1 gives T_v = T_w = {1}, α = 1, and ρ = 1, satisfying the generalization conditions under bi-level scaling.The calculation verifies the corresponding conditions for clean ground-truth supervision.Source: G Heuristic calculations · p. 37

G.1 The necessity of 1-sparse assumption

• Asymptotically perfect generalization requires the survival-to-contamination ratio to be ω_n(1), imposing strong structural conditions on the planted feature.The result concerns learning v from labels generated by v under the stated heuristic assumptions.Source: §G.1 · p. 37
• Each heavy coordinate must have either v_i = o(1) or v_i = 1 − o(1).Intermediate-sized heavy coordinates violate the necessary condition.Source: §G.1 · p. 38
• Therefore, 1-sparse labels are necessary for asymptotically perfect generalization in this setting.The conclusion follows from the survival and contamination bounds over the relevant spiked coordinates.Source: §G.1 · p. 38