From Linear to Nonlinear: Provable Weak-to-Strong Generalization through Feature Learning
Authors: Junsoo Oh
Jerry Song
Chulhee Yun
Venue: NeurIPS 2025 poster ()
Keywords: weak-to-strong generalization
theory
feature learning
Primary area: theory
TL;DR: We theoretically investigate weak-to-strong generalization from a linear CNN to a two-layer ReLU CNN

Abstract: Weak-to-strong generalization refers to the phenomenon where a stronger model trained under supervision from a weaker one can outperform its teacher. While prior studies aim to explain this effect, most theoretical insights are limited to abstract frameworks or linear/random feature models. In this paper, we provide a formal analysis of weak-to-strong generalization from a linear CNN (weak) to a two-layer ReLU CNN (strong). We consider structured data composed of label-dependent signals of varying difficulty and label-independent noise, and analyze gradient descent dynamics when the strong model is trained on data labeled by the pretrained weak model. Our analysis identifies two regimes—data-scarce and data-abundant—based on the signal-to-noise characteristics of the dataset, and reveals distinct mechanisms of weak-to-strong generalization. In the data-scarce regime, generalization occurs via benign overfitting or fails via harmful overfitting, depending on the amount of data, and we characterize the transition boundary. In the data-abundant regime, generalization emerges in the early phase through label correction, but we observe that overtraining can subsequently degrade performance.

From Linear to Nonlinear: Provable Weak-to-Strong Generalization through Feature Learning
Junsoo Oh
Jerry Song KAIST
Chulhee Yun
(uussoo.oh oh, sjerry0316, chulhee, yun) ac.
Abstract
Weak-to-strong generalization refers the phenomenon where stronger model trained under supervision from a weaker one can outperform its teacher. While prior studies aim to explain this effect, most theoretical insights are limited abstract frameworks or linear/random feature models. In this paper, we provide formal analysis of weak-to-strong generalization from linear CNN (weak) a two-layer ReLU CNN (strong). We consider structured data composed of label- dependent signals of varying difficulty and label- Sbblliindependent noise, and analyze gradient descent dynamics when the strong model is trained on data labeled by the pretrained weak model. Our analysis identifies two regimes data-scarce and data-abundant--bar and reveals distinet mechanisms of weak-to-strong generalization. In the data- scarce regime, generalization occurs via benign overfitting or fails via harmful overfitting, depending on the amount of data, and we characterize the transition boundary. In the data-abundant regime, generalization emerges in the early phase through label correction, but we observe that overtraining can subsequently degrade performance.
on the signal-to-noise characteristics of the dataset,
Introduction
As the capabilities of today's AI models grow, recent models such state-of-the-art large language models (LLMs) increasingly demonstrate superhuman performance in various domains. The com- plex and often unpredictable behaviors of superhuman models make it crucial align them with human intent, a challenge known as superalignment. In order to tackle this challenge, human-level supervision techniques, such reinforcement learning from human feedback (RLHF), commonly applied. This situation, where a less capable supervisor guides a more advanced model, reverses the traditional teaching paradigm and raises important question: What happens when model with stronger capabilities is trained under the supervision of a weaker one?
To address this question, Burns et al. (2024) performed extensive experiments training strong student models, like GPT-4 (OpenAI, 2023), with supervision from a weaker teacher model, such as fine-tuned GPT-2 (Radford et al., 2019). They observe that the strong model consistently surpasses their supervisor's performance, and refer to this phenomenon as weak-to-stron generalization. This surprising phenomenon has attracted considerable attention, and several recent studies have investigated from theoretical perspectives.
Lang et al. (2024) introduce theoretical framework that establishes teak-too-ttron generalization when the strong model unable to fit the weak model's mistakes. Building on this framework, Shin et al. (2025) propose mechanism for weak-to-strong generalization in data exhibiting both easy and hard patterns. Concurrently, another line of work has focused on quantifying the weak-to-strong gain. Charikar et al. (2024) investigate the relationship between weak-to-strong gains and the misfit between weak and strong models in regression with squared loss. Specifically, they show that the
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

gain in strong models. Mulgund and Pabbaraju (2025) and Yao et al. (2025) extend this analysis broader class of loss functions, including the reversed Kullback-Leibler divergence. However, both lines of work often rely on abstract theoretical frameworks and typically do not guarantee that weak-to- strong generalization can be achieved through practical training procedures such as gradient-based optimization.
generalization correlates with the degree of misfit between the weak and
Wu and Sahai (2025) explore weak-to-strong generalization in an overparameterized spiked covariance model and prove transitions between generalization and random guessing by considering both weak and strong models as minimum &g norm interpolating solutions on feature spaces of differing expressivity. Ildiz et al. (2024) investigate more general form of knowledge distillation (Hinton et al., 2015) in a nigh-dimensional regression setting and show that distillation from a weak model can outperform distillation from a strong model, while it fails to improve the overall scaling law. Dong et al. (2025) also study a linear regression setting from a variance reduction perspective via the intrinsic dimension of feature spaces. However, these works are limited to linear models and rely on specific assumptions on structural differences between the feature spaces of weak and strong models. A more recent work by Medvedev et al. (2025) alleviates some of these limitations by using random feature networks of differing widths for the strong and weak models. However, in their approach, the trainable component is still linear. These limitations motivate the following question:
When and how does weak-to-sstrng generalization emerge through nonlinear feature learning?
1.1 Summary of Contributions
In this paper, we investigate a classification problem on structured data composed of patches, which consist of signals and noise. We employ linear CNNs as the weak model and two-layer ReLU CNNs as the strong model. We focus on the following training scenario: training the weak model under true supervision and then training the strong model under supervision from the pretrained weak model. We investigate how models trained through this scenario perform, particularly focusing on when and how weak-to-strong generalization emerges. We summarize our contributions follows:
We compare the capability of weak models and strong models in our data distribution, showing that any weak model makes non-negligible errors (Proposition 2.1) while there exists a strong model that exhibits zero errors (Proposition 2.2).
We prove that training weak model using finite number of training samples and gradient descent can result in a test error that is close to the best possible error achievable by the weak model architecture (Theorem 3.3).
We also demonstrate that when strong model is trained on finite set of samples using supervision from a weak model that makes non-negligible errors, it either achieves near-optimal generalization via benign overfitting suffers from degraded performance due to harmful overfitting. We further characterize the conditions under which this transition occurs (Theorem 3.4).
We further explore yeak-to-strong training in the regime where more data is available than the previously considered scenario, and perhaps surprisingly, we find that it exhibits a notably different behavior. The strong model can achieve near-zero test error even while the training error on pseudo-labels remains non-negligible (Theorem 3.6). However, we also empirically observe that "overtraining" until convergence to zero training loss climinates this benefit, resulting in test error levels close to those of the weak model.
2 Problem Setting
In this section, we introduce the data distribution and weak/strong model architectures that we focus on, and formally describe the training scenario considered in our work.
In our analysis, we adopt a patch-wic wise structured data distribution and patch- patch-wise convolutional neural network architectures. This approach follows a recent line of work on feature learning theory starting from Allen-Zhu and Li (2020). This type of setting provides a simple but useful framework for studying training dynamics in deep learning. Similar problem settings have been widely used to understand several aspects of deep learning, such as benign overfitting (Cao et al., 2022; Kou et al., 2023; Meng et al., 2024), optimizer (Jelassi and Li, 2022; Zou et al., 2023b; Chen et al., 2023), data

---

augmentation (Shen et al., 2022; Chidambaram et al., 2023; Zou et al., 2023a; Oh and Yun, 2024; Li al., 2025), and architecture (Huang al., 2023; Jiang al., 2024). The broad utility of such settings confirms their value in understanding fundamental aspects of deep learning.
2.1 Data Distribution
We investigate a binary classification problem on structured data consisting of multiple patches. These patches contain label-dependent vectors (called signal) and label-independet vectors (called noise). Definition 1. We define data distribution D on Rdx3 x {+1} such that a sample (X, (X,)) 'D with X (ao(1) 2x(2) ()) and y E {+1} is constructed follows.
1. Choose the label y E } uniformly at random.
2. Let {u1 14111111,10 14-1, 21,1 be a set of mutually orthogonal signal vectors. We choose two signal vectors o0)),1(e E Rd for data point X associated with the label as follows:
(g)
with probability Pe
(v0))
Unif((Ug, vy), Uuy) (-My: My); U,,, - -2 Unil((Ayy My); (Hy. My); (Uy, Hy), (- uy (k))
with probability ph
with probability ps
For simplicity, we assume || = |||- and || = |111 ||. and refer to their norms as | and ||M]], respectively, omitting the subscripts.
3. A noise vector is drawn from Gaussian distribution /V (0, ofA), where the covariance matrix mrr
pe is given by = Ia |all
M-I
e- -_
||
||]
||0|
4. The components (1), (2) x. of the data point X are formed by assigning the generated vectors ((1), (2)) & in randomly shuffled order.
Our data distribution is based characteristics of image data, where inputs consist of multiple patches. Some patches contain information relevant to the label (such as a face or a tail for "dog"), while others contain irrelevant information, like grass in the background. Intuitively, model can fit data by learning signals and/or memorizing noise. However, relying primarily on noise memorization instead of learning signals leads to poor generalization since noise is label-irrelevant. Therefore, effectively learning signals is crucial for achieving better generalization.
Real-world data often contains multiple types of label-relevant information, and these corresponding signals can exhibit varying levels of learning difficulty. For example, both a face and a tail are useful for recognizing "dog". but learning the tail could be harder since it occupies only small region of the image or appears only in a small number of images. To reflect this difference, we consider two types of signals. We refer to 14-1 as easy signaly and v1, V-1 hard signals. These signal types are designed to have different levels of learning difficulty within the architectures we focus on, as detailed in the following subsection. We categorize data point having only easy signals as easy-only data, only hard signals as hard-only data, and both types of signals as both-signal data. We denote by S., Sp, and S, the supports of these data categories, respectively.
2.2 Neural Network Architecture
We now define the weak and strong model architectures in our analysis. First, weak models are linear convolutional neural networks where patch-wiss convolution is applied.
Definition 2 (Weak Model). We consider our weak model as linear CNN fw .) Rdxx3 + R
parameterized by w E Edd defined as follows. For each input X = (x(1), x(2), (()) E RRdx3 we define
f X) =
-w (w, 2011) (. .x)2 + ( w. (3)
Our choice of weak model has limited capability for learning our data distribution D. particular, any weak model shows random-gues level performance on hard-only data, as formalized below. Proposition 2.1. Let (X, ,y) ~ D be a test example. For any weak model fwx(wn, -), it satisfies
flyffx(w, X) < 0 [X, 8) Sn = =
3

---

Proof. Consider a hard-only data (X, y) Sn with the noise vector Ç. If the two underlying signals in a hard-only data point have opposite signs. the weak model's output fwk (w, X) simplifies to (w. E). This results in 1/2 conditional error rate due to symmetry of noise. For a hard-only data having two signal vectors of identical signs, we may assume two signal vectors of (X, y) E Sh are both My, without loss of generality. Define (X, Sn to data point where both signal vectors are By and the noise vector is c. Then, v.fwk(tu (w, X)) = yffwk( [w, X). From the symmetry of &. implies the model has 1/2 error rate conditioned on the case where two signal vectors identical. By combining two cases, we have the desired conclusion.
The strong model is 2-layer convolutional neural network with ReLU activation, also applying patch-wise convolution, where the second layer weights are fixed and only the first layer is trainable.
Definition 3 (Strong Model). We consider strong model as 2-layer CNN fat (W.)) Rdx3 R parameterized by W = (W1. W-1} where W, = (ws,r for s E {=1} represents the set of positive/negative filters, each containing filters Warr E Rd. For each input X (xx1), (2), (3)) E R define
fat (W X) = Fi FW, F-I--.,....
where for each 8 E {+1),
F. X)
1
Σ
o ((wss))())) + +(w(wr))))))) to (
m rE[m]
and (-) denotes the ReLU activation function.
In contrast to the limitations of the weak model, the following proposition demonstrates the strong model architecture's is capability for perfect generalization.
Proposition 2.2. Let (X, y) ~ D be test example. 1fm 2 2, then there exists a strong model with parameter n that achieves zero test error: TP [ySst
Susst(W". (W". X) 0] O.
Proof. We construct W by defining, for each E {+1), the filters w = +V. w = p4 V and setting wh,r = 0 for r >> 2. Direct calculation shows that y (W*, X) > for all (X,y) ,y) ~ D. leading to zero test error.
2.3 Training Scenario
Our goal is to train the weak and strong models, using finite training set sampled from the distribution
D. to correctly classify unseen test examples from DD We first outline the training procedure of the weak model and then describe the training of the strong model supervised by the weak model.
2.3.1
Weak Model Training
M:) Hiak Lld. D and training loss is In weak model training, we use now labeled data points {(X;,
defined as
1 Σ (Jifwk (w, X.)),
Lwn (w)
Towk
sE(mwl]
where {(2) = log(1+ +xp((=)) the logistic loss. We consider using gradient descent with learning
rate 7j to minimize training loss Lwk(w) and model parameters are initialized as (() = The parameters are updated at each iteration L as
(++1) (t) V Lowk
(20(1))
(t())
Towk Σ Vill (WiSwx (10(), x:) (a.
xx
(3)
x
VE [Wwk
(t)
vi (2011) xx(0) + x13)
(1)
Bokk vE(mwk]
where X; (x.") _ xx!
(2)
and we use yj = ff (yiSwx (x)())x))))

---

2.3.2 Weak-to-Strong Training
Let {(X,, ~ D denote dataset drawn from the data distribution D. Then the strong model trained on the dataset {(X,, i, 9:) Ji where the supervision d; provided by pretrained weak model swk(w", .), i.e., 91- = sign(Swk (wwk("" x))) instead of using true label ii- The training objective
is defined as
L = 1sst
Σ (i.fa(W.X.) (E(ma)
and we use gradient descent with learning rate to minimize La (W). where the model parameters are initialized as (0) ~ (N,, Ta for all 8 {+1} and r E [m)] The parameters are updated at
each iteration È as
w (1+1)
w (t) V/ wx,
Let (W(())
(t)
msst Σ ÚcP (Bifa(W(o,, Ed _(((u())) a!!0)
w s.r
iE|mme]
PE[J]
[ (t) + mnst :E(n
Úi (1)
Σ o'
20(1) s!!1)
(2)
PE(3]
where X; (0!") _2
(Wrl, x.)) a and we use of0
for each E [nat]
3 Provable Weak-to-Strong Generalization
In this section, we provide theoretical results on when and how weak-to-strong generalization occurs in our setting. For our analysis, we denote by T the maximum admissible training iterates and we assume 7 = 1 polyys(ss_1 d, Neat Tluk. m), where is a target training loss and poly(.) (.) is sufficiently large polynomial. Furthermore. we focus on an asymptotic regime where parameters e- d, flat, Awk, m are considered sufficiently large. Consequently, our theoretical guarantees will often be expressed using asymptotic notation such as (-), (()). o(-), w(-), as well ((-), which hide logarithmic factors. Our main results depend on the conditions detailed below.
Condition 3.1. There exists sufficiently large constant
such that the following hold:
(C1) d d C max { mii log (Cnik) Nyt log (Crue) }} (log T
(C2) Dokk Not 2 C max {po²: ppp² Ph log (g), m 2 C' Colog C'tat
(C3) - C-1 min 1 [ I o min {
Rapa mm ozd
ofd (2pe tpo.mm Ml
(log (Crnza) )) -
(C4) I C- o- 2d
ofd (2not9))1laa))
(C5) (2pe + pell 2 Cptlluil?
nokk Dest w
(C6) 2 Cmax op ||)/|| ||||| -2 (logT*)+}
(CI) and (C2) allow us to apply concentration incqualities and ensure that our training data samples and initial model parameters satisfy certain desirable properties with high probability. (C3) and (C4) ensure that initialization negligible compared to the update and that learning dynamics are stable. They facilitate our analysis of the learning dynamics. (C5) guarantees that easy signals are easier to learn than hard signals for both weak and strong models, as the difficulty of learning signals is determined by their frequency and strength. This also ensures that both models guaranteed to learn these easy signals. Furthermore, a large enough portion of both-signal data stated in (C6) is essential weak-to-strong generalization, in line with the insights discussed in Shin et al. (2025).
As we mentioned before, in our problem setting, there are two mechanisms for minimizing training loss: learning signals and memorizing noise. Since signals repeatedly appear in data while noise is
5

---

independent across data points, the amount of data affects which mechanism predominantly influences the learning dynamics. In our analysis, we consider two regimes based on this observation: the data-scarce regime and the data-abundant regime.
In the data-scarce regime, demonstrate two key findings. First, prove that weak model training can achieve performance close to the optimal limit of the weak model class even in this regime. Second, we demonstrate that even within the data-scarce regime, weak-to-strong training can achieve low test error through benign overfitting, provided that the given dataset size is not too small. We also characterize tight conditions under which the weak-to-strong training exhibits benign or harmful overfitting. In the data-abundant regime, we analyze weak-to- tt-sonn training and, perhaps surprisingly. observe that weak-to-stee to-tonng generalization behaves differently compared to the data-scares regime: Early stopping plays crucial role.
3.1 Data-Scarce Regime
In this regime, the amount of available data is small. Consequently, noise memorization is more prevalent than signal learning, leading to model outputs on training data points mainly determined by activations from noise vectors. We formalize this regime follows.
Condition 3.2 (Data-Scarce Regime). All conditions in Condition 3.1 hold, using the same con- stant C 0 as introduced therein, and the following additional condition holds: Powky fstt I C- oo + pb) ||]= log log )
The following theorem provides convergence and test error guarantees for weak model training.
Theorem 3.3 (Weak Model Training). Let w(() be the iterates of weak model training. For any 8 > and å E (0, 1) satisfying Condition 3.2, with probability at least 1 1-6 ô, there exists Twk ler-le--nidddae
such that for all t E [Twk, Th the following statements hold:
The training loss converges below e: Lwn (wl)) <.
2. Let (X,y) ~ 'D be an unseen test example, independent of the training set ((X;, Vi) Then, have
P [[uSw (,01,,) <0 E S. U.S.S. S <exp ( "owk (2po + pb)) ||llll
(
) o(1).
Clo2d
=
Here, Ci > 0 is constant.
The proof is provided in Appendix B. Combined with Proposition 2.1, Theorem 3.3 guarantees the convergence of training loss and shows that the trained weak model achieves low test error on easy-only data and both-signal data, while performing random guessing on unseen hard-only data. This corresponds to the near optimal error attainable by the weak model, but not perfect because the overall test error will be of order 2 + o(1).
The following theorem provides convergence and test error guarantees for weak-to to-strong training.
Theorem 3.4 (Weak-un to-ong Training, Data-Scarce Scarce Regime). Let W be the iterates of weak- to so-strong training. with the weak model fwk(w (wo, satisfying the conclusion of Theorem 3.3. For any & 0 and E (0, 1) satisfying Condition 3.2, with probubility at least 8, there exists T Tw2s = -g-n-atd- T072) such that for any E [Twzs; T*) the following statements hold:
1.
The training loss converges below e: Tua (W(") <.
2. Let (X,y) 'D be unseen test example, independent of the training set ((x,, (1),
(Benign Overfitting) When nxPP ||||** /(a 2 C2.² we have
P P[ySst(((t)
(())
x <0] S (po+pb) exp
nex nap + pp1)11)))l))
(-
+pn exp
Cagfd
Caold
(Harmful Overfitting) When napi
|11$ /(o9d) S Ca,
yfat
( (4)
< 0 0.12pm-
We emphasize that this condition does contradict Condition 3.2 due to (C6).

---

Here, C2 C3. C2 > O are constants.
The proof is provided in Appendix C. Theorem 3.4 guarantees training loss convergence and further characterizes the overall test error in the weak-to-strong scenario. Specifically, it shows that the error is much smaller than the lower bound for the weak model's error (Proposition 2.1) when the number of data ft exceeds certain threshold. Conversely, when nat falls below a similar threshold, the error remains lower-bounded by constant multiple of ph. as in the case of the supervising weak model's error. The fact that these two thresholds differ only by constant factors provides tight characterization of these distinct regimes.
3.2 Data-Abundant Regime
In this regime, a sufficient amount of data is available, allowing signal learning to dominate the effects of noise memorization. We formalize this regime as follows.
Condition 3.5 (Data-Abundant Regime). All conditions in Condition 3.1 hold, using the same constant C > as introduced therein, and the following additional condition holds: fitt Z Cohd log T (pv ||]
Due to the limited availability of costly true-labeled data, the defining conditions for this data- abundant regime primarily focus fsst- Thus, the characteristics of the supervising weak model, as established in Theorem 3.3, remain applicable in this regime. The following theorem demonstrates the emergence of weak-to-strong generalization the early phase, where training loss remains large.
Theorem 3.6 -Weak-to-Strong Training, Data-Abundant Regime). Let ((t) be the iterates of the weak-to-strone strong training, with the weak model fwx(w0" satisfying the conclusion of Theorem 3.3. For any 5 (0, 1) satisfying Condition 3.5, with probability at least ō, there exists early stopping time T (1 mmpp. + Pb) |||||
such that the following statements hold:
1. The early stopped strong model fst (W(T:)),)) perfectly fits all training data points having correct labels (i.e. Ús- = Ús) but fails on all training data points with flipped labels (i.e. 9s + 9:). In other words. the model predicts the true label Us for any training data point X,-
2. Les (X,u) ~ D be an unseen test example, independent of the training set ((X, 12) We have
P Sfat (W(Te)) x) <0] s (Pe) exp (-
(- C3o
nat (2pe + +p)) ||ll|(
) +Ph exp
Here, C5 > 0 is a constant.
The proof is provided in Appendix D. Theorem 3.6 shows that weak-to-strong generalization can arise via early stopping in this regime. It provides guarantees for an early-stopped model and thus does not provide guarantees on the model's performance at convergence. One might therefore be curious how training until convergence influences performance. We conducted experiments in our setting and observed that after this early phase, performance often degrades and then plateaus, exhibiting accuracy similar to or even lower than that of the supervising weak model. While we leave rigorous proof for this late-phase behavior open, we provide an intuitive explanation in Section 4.
The role of early stopping for weak-to-strong generalization is also discussed in the literature. Burns et al. (2024) observe that in ChatGPT Reward Modeling tasks and subset of NLP tasks, early stopping can improve weak-to-strong generalization, while overtraining can lead degradation. Medvedev et al. (2025) also discuss early stopping in their theoretical setting, where it becomes essential due to their consideration of training on the population risk over the distribution of pseudo- labeled data. In contrast, in our finite-sapple setting, early stopping is not strictly required to achieve weak-to-strong generalization. In fact, strong model that perfectly fits the pseudo-labeled training data may lead to either low or high test error, as observed in the data-scarce regime. Thus, the fact that training dynamics can converge to a solution with poor generalization, even under abundant data and the existence of good solutions, is somewhat surprising.
7

---

4 Key Theoretical Insights
In this section, we provide key insights behind our theoretical analysis. We formally prove this intuition using several theoretical tools, such as the signal-noise decomposition (Cao et al., 2022).
For weak model training, its update rule (1) implies that the model weight vector w is updated in directions determined by the signal and noise vectors within the training samples. The evolution of along each such vector's direction is influenced by that vector's strength and its frequency of appearance in the dataset. Due to the limited capability of the weak model, it cannot learn hard signals with opposite signs (e.g., , -V)). Furthermore, the cancellation of updates along hard signal directions and our condition (C5) ensure that the learning of easy signals predominates over that of hard signals. This dominance means that while easy signals are effectively learned, the learning of hard signals is largely suppressed. Consequently, in both-signal data, the contribution from the poorly learned hard signal component is not large enough to disrupt the classification guided by the well-learned easy signals. Therefore, the weak model can correctly predict not only easy-only data but also both-signal data.
We now explain how the supervision from the pretrained weak model affects the learning dynamics of weak-to-strong training. Let us first introduce some notation. For each E [m we denote by a("), of"), and &, the signal vectors and noise vector of the i-th input X,, respectively. For each E [max] such and the supervision corresponds to the clean label (i.e., 0s (j:) or the flipped label
E {uI 1- - 11 and E [2]. we define c!O) and F(! as the sets of indices
that a!!)
(i.e., i, = j.). respectively. Lastly, recall that g(()) ( (W (0, X.)) denotes the negative
of the loss derivative for i-th sample.
Update rule for weak-to-strong training (2) implies that for any s E {=1} and r E [m]]
(wit+1) (1+1) 6x (4)) s. Hs)
(w
? m
Σ [E[2]
Σ EE
o. || 1 (w > =0]
REC
Since the supervising weak model achieves low test error on easy-only and both-signal data, the pseudo-labels for training samples involving μ, have a low flipping probability, and this implies (t) [illl n O. This ensures that, in both data-scarce and data-abundant regimes, (whr, ps)
increases if it is positive.
Similarly, update for learning hard signals can be written follows:
(1+1) v.)) (w0!f Uz or
17
9
Σ
T
||w/1
(w (o >
mist
(E(2)
(EC()
(EF1))
( 9
Σ
(1) 9
||
I
(w Ms <
[E
iEC
VE -M
However, weak-to-strong generalization exhibits different behaviors across the two regimes, in- fluenced by the presence of a negligigee fraction of data containing hard signals with flipped pseudo-labels. In the data-scarce regime, noise memorization is dominant component of the learning process. This can lead to the learning effort being more balanced across different data points. A
sufficient fraction of both data guarantees (cl) (c()) Cp. > |F (F -2,, and this indicates
v.) < (w..r M2) if (w..r. v.) < 0. Therefore, the strong model can learn hard signals with opposite signs Vs and -vs, simultaneously.
that (w (1+1) v,)) > (t) M.) if (w.r,, v.). > 0 and (w..r ((+1)
by utilizing different sets of filters {r E [m] (w..) v.) > 0} and {r E [m]: (w..) v.) < 0}.
In contrast to the data-scarce regime, in the early phase of the data-abundant regime, the strong model can learn both easy and hard signals quickly (even faster than noise is memorized) due to the significant abundance of signal vectors from the clean-labeled training data. This leads to almost perfect generalization on unseen data. Let us describe our intuition for why overtraining can lead to performance degradation. Rapid learning of signals also creates growing discrepancy in the negative loss derivatives ( between clean-label data and flipped-label data. The non-neg negliggli portion of flipped- label hard-only data combined with the imbalance in loss derivatives can lead to the
8

---

contributions from these flipped-label data points (e.g. ΣiEr!! (1)) predominating over those from clean-labeled data points (e.g.. Eiec!! ) Consequently, the strong model may start "forgetting" learned signals it continues to minimize the training loss defined by these pseudo-labels.
Practical Insights. Our analysis reveals the following mechanism for weak-to-strone generalization: the weak model first successfully labels data containing easy-to-learn information. This data includes a subset that contains both easy information and harder-to-learn information (which the weak model fails to capture). The strong model then utilizes this correctly labeled subset to successfully learn the harder-to-learn information. We believe that this insight can be applied to practical scenarios, potentially leading to the development of data selection techniques that preferentially select such beneficial data for better weak toak--t-strong generalization.
5
Experiments
We conduct experiments to support our findings, using NVIDIA RTX A6000 GPUs.
5.1
Experiments on Our Theoretical Setting
We perform experiments our setting described in Section We set the dimension 2000 and the signal vectors 1 1 1:: V1, V-1 are constructed from randomly generated orthonormal vectors, which are subsequently scaled so that their respective norms are |||||| = 0.4 and || 0.35. The noise strength is op 0.1 and the data type probabilities are p. 0.4 and ph Pb 0.3.
We first train the weak model using Rwk 5000 truellabeled data points. The training is conducted for 1000 epochs using stochastic gradient descent with batch size 256 and learning rate 0.1, which results in a test accuracy 0.851. For veak-to-strong training, we use the strong model with m = 50 filters and an initialization scale To 0.01. We train the strong model using stochastic gradient descent with batch size 256 and learning rate 7) = 0.1 on the dataset labeled by the pretrained weak model. We use three different values for the number of data points, nst = 75, 2000, 20000.
Figure 1 provides the training and test accuracy for weak-to-strong training with three different training dataset sizes. We train the strong model for 2000 training epochs when Tha 75 or Nss 2000, and for 10000 epochs when nat = 20000, as this requires more iterations for convergence compared to the other cases. We observe three different types of results revealed in our analysis.
The cases Nst 75 and Rgt 2000 support analysis in the data-scarce regime. In both cases, the training accuracy initially increases faster than the test accuracy. However, their final test accuracies differ. In the case of nst 75, the strong model achieves perfect training accuracy, while its test accuracy remains close to that of the supervising weak model. This aligns with our findings on the failure of yeak-to-stront generalization due harmful overfitting. In contrast, for n&t 2000, the increased amount of data allows the test accuracy to sufficiently increase, eventually exceeding the weak model's test accuracy. This aligns with our findings on the emergence of weak-to-strong generalization via benign overfitting.
The case of ns. 20000 corresponds to the data-abundant regime in analysis. Unlike the prior two cases, test accuracy grows faster than training accuracy and achieves near near-perfect accuracy, while training accuracy remains comparable to that of the weak model; this aligns with Theorem 3.6. We also observe that continued training deteriorates test accuracy, while training accuracy increases.
Text
Wast Mo30
5.053
M0:00
1est 2.852
Wozt Mozel kss 0.51
055
250
180
124e
1959
1999
2002
15
350
1009
1429 1999 2812
5009
2000
18500
Spach
Boach
byoch
(a) Teut 75
(b) 2000
(c) Yout 20000
Figure 1: Weak-to-strong training with varying training dataset sizes (nst). These align with our theoretical findings: (a) harmful overfitting for Nst 75; (b) benign overfitting for nst 2000; and (c) for na = 20000, an early emergence of generalization and degradation with overtraining

---

5.2 Experiments on MNIST
We also provide empirical results using real-world dataset MNIST. Since is hard to clearly delineate signal and noise in real data, we modify the MNIST dataset emphasize their roles.
First, we multiply each pixel in the original images of digits 5, 6. 7, 8. and 9 by 0.02, while keeping the images of other digits unchanged. This corresponds to the presence of hard signals, with digits 4-9 serving as the hard signals. To emphasize the role of noise, we replace the border region of each 28x28 image-a a a 5-pixel-wide frame along the images where the central 18x18 region contains the digit, surrounded by Gaussian noise. Finally, we randomly concatenate two such modified images that share the same parity (i.e., both even both odd), producing 28x56 images. We assign binary labels based on their parity.
wwit standard Gaussian noise. This results in
Figure 2 provides examples of the modified data. The resulting data includes variety of signal types: some pairs contain two bright digits, others contain one bright and one dark digit, and some consist of two dark digits. These types serve as easy-only data, both-signal data, hard-only data in our setting,
For the weak model, we use MLP consisting of single hidden layer with 128 units followed by ReLU activation. For the strong model, we use a CNN with three convolutional layers of increasing channels (64, 128, 256), each followed by batch normalization, ReLU, and max pooling. The extracted features are then flattened and passed through a fully connected layer with 512 units. We first train the weak model using 500 samples. Then, train the strong model using labels predicted by the trained weak model, with varying numbers of training samples That 500, 1000, 1500, 2000, 2500, We train each model for 300 epochs using the full-batch Adam optimizer with default parameters.
In Table 1, we observe a trend in which the weak-to-strong gain increases with n&t and then decreases. These observations are consistent with our theoretical findings, which describe a transition from harmful overfitting to benign overfitting, and eventually to the data-abundant regime.
Table 1: Test accuracy (%) for the weak model and the resulting weak-to-strong model. Results are calculated as the mean and standard deviation over five independent runs.
Label:
Label: 0
S
21
L
ast
Weak Model
Weak-to-Strong
500
86.06 (0.45)
84.62 (3.95)
1000
85.93 (0.13)
88.34 (1.28)
1500
86.42 (1.50)
88,46 (2.85)
2000
86.69 (0.52)
87.44 (2.73)
Figure 2: Examples of the modified MNIST.
2500
85.86 (1.39)
86.55 (1.22)
6 Conclusion
We theoretically investigated weak-to-strong generalization by analyzing the training dynamics of two-layer ReL.U CNN under supervision from a pre-trained linear CÑN on patch-wise data containing both signals and noise. Interestingly, our results reveal that weak-to-strong training exhibits distinct behaviors across different data regimes. In the data-scarce regime, we prove that weak-to-strong training converges and that generalization can emerge via benign overfitting when data availability is not extremely limited. Furthermore, we characterize the conditions leading to a transition from this benign overfitting harmful overfitting. In the data-abundant regime, we show that weak-to. -t- strong generalization arises in an early phase of training, and we observe that overtraining leads to performance degradation. We hope our theoretical approaches provide valuable insights.
Limitation and Future Work. Our work has some limitations regarding the simplified data distribution and model architectures used for theoretical analysis. Extending our analysis to more complex data or models could be a future direction. Also, would be interesting to analyze methods for improving weak-to-strong generalization (e.g., auxiliary confidence loss (Burns et al., 2024)) in our theoretical framework. Lastly, developing techniques for better weak-to took--t-ssaee soaak-t--ttron generalization based on our theoretical insights is important future direction.
10

---

Acknowledgement
This work was supported by a National Research Foundation of Korea (NRF) grant funded by the Korean government (MSIT) (No. RS-2024-004212233 and the InnoCORE program of the Ministry of Science and ICT (No. N10250156).
References
Zeyuan Allen-Zhu and Yuanzhi Li. Towards understanding ensemble, knowledge distillation and self-distillation in deep learning, arXiv preprint arXiv:2012.09810 2020.
Sébastien Bubeck. Convex optimization: Algorithms and complexity. Foundations and Trends@ in Machine Learning, (53-4):331-3717 2015.
Collin Burns, Pavel Izmailov, Jan Hendrik Kirchner, Bowen Baker, Leo Gao, Leopold Aschenbren- ner, Yining Chen, Adrien Ecoffet, Manas Joglekar, Jan Leike, Ilya Sutskever, and Jeffrey Wu. Weak-to-strong generalization: Eliciting strong capabilities with weak supervision. Forty-first International Conference Machine Learning. 2024. URL https://openreviewt www.wwwwwee/fftttttoee id=ghNRg2mEgN.
Yuan Cao, Zixiang Chen, Misha Belkin, and Quanquan Gu. Benign overfitting in two-layer convo- lutional neural networks. Advances in neural information processing systems, 35:25237-25250, 2022.
Moses Charikar, Chirag Pabbaraju, and Kirankumar Shiragur. Quantifying the gain in weak-to-strong generalization. Advances in neural information processing systems, 37:126474-126499 2024.
Zixiang Chen, Junkai Zhang, Yiwen Kou, Xiangning Chen, Cho-Jui Hsieh, and Quanquan Gu. Why does sharpness- aware minimization generalize better than SGD? Advances in neural information processing systems, 36, 2023.
Muthu Chidambaram, Xiang Wang, Chenwei Wu, and Rong Ge. Provably learning diverse features in multi-view data with midpoint mixup. In International Conference Machine Learning, pages 5563-5599, PMLR, 2023.
Luc Devroye, Abbas Mehrabian, and Tommy Reddad. The total variation distance between high- dimensional gaussians with the same mean. arXiv preprint / 2018.
Yijun Dong, Yicheng Li, Yunai Li, Jason D Lee, and Qi Lei. Discrepancies virtue: Weak-to-strong generalization through lens of intrinsic dimension. arXiv preprint arXiv:2502.050075 2025.
Geoffrey Hinton, Oriol Vinyals, and Jeff Dean. Distilling the knowledge in neural network. arXiv preprint arXiv:1503.022 025331, 2015.
Wei Huang, Yuan Cao, Haonan Wang, Xin Cao, and Taiji Suzuki. Graph neural networks provably ben- efit from structural information: A feature learning perspective. arXiv preprint vrXiv:2306.13977 2023.
M Emrullah Iddiz, Halil Alperen Gozeten, Ege Onur Taga, Marco Mondelli, and Samet Oymak. High-dimensional analysis of knowledge distillation: Weak-to toak-to--ttong generalization and scaling laws. arXiv preprint 241. 18837, 2024.
Samy Jelassi and Yuanzhi Li. Towards understanding how momentum improves generalization in deep learning. In International Conference Machine Learning, pages 9965-10040. PMLR, 2022.
Jiarui Jiang, Wei Huang, Miao Zhang, Taiji Suzuki, and Ligiang Nie. Unveil benign overfitting for transformer in vision: Training dynamics, convergence, and generalization. Advances in Neural Information Processing Systems, 11111334441352222 2024.
Yiwen Kou, Zixiang Chen, Yuanzhou Chen, and Quanquan Gu. Benign overfitting in two-layer ReLU convolutional neural networks. In International Conference on Machine Learning, pages 17615-17659, PMLR, 2023.

---

Hunter Lang, David Sontag, and Aravindan Vijayaraghavan. Theoretical analysis of seak-to-stronn generalization. Advances in neural information processing systems, 37:46837-46880, 2024.
Jingyang Li, Jiachun Pan, Kim-Chuan Toh, and Pan Zhou. Towards understanding why data
augmentation improves generalization. arXiv preprint arXiv:2502.08940, 2025.
Marko Medvedev, Kaifeng Lyu, Dingli Yu, Sanjeev Arora, Zhiyuan Li, and Nathan Srebro. Weak-to- strong generalization even random feature networks, provably. arXiv preprint arXiv:2503.02877, 2025.
Xuran Meng, Difan Zou, and Yuan Cao. Benign overfitting two-layer ReLU convolutional neural networks for XOR data. In Forty-first International Conference on Machine Learning, 2024. URL htw.:pppnrrreeeeeeeee/orrrrr...o
Abhijeet Mulgund and Chirag Pabbaraju. Relating misfit to gain in weak-to-strong generalization beyond the squared loss. arXiv preprint arXiv:2501.11005 2025.
Junsoo Oh and Chulhee Yun. Provable benefit of cutout and cutmix for feature learning. In The eiihth- Annual Conference on Neural Information Processing Systems, 2024. URL https: htmpp::///peeee http//ppppreee..eee/eeeee
OpenAl. Gpt-4 technical report. arXiv preprint arXiv:2303.055. 08774, 2023.
Alec Radford, Jeffrey Wu, Rewon Child, David Luan, Dario Amodei, Πlya Sutskever, et al. Language models are unsupervised multitask learners. OpenAl blog, 1(8);9, 2019.
Ruoqi Shen, Sébastien Bubeck, and Suriya Gunasekar. Data augmentation as feature manipulation.
In International conference on machine learning, pages 19773-19808. PMIR, 2022.
Changho Shin, John Cooper, and Frederic Sala. Weak-to-strong generalization through the data- centric lens. In The Thirteenth International Conference Learning Representations, 2025, URL https: /tpprs////peeeieeee wttp:///oormmiiuuoggesette.
Roman Vershynin. High-dimensional probability: An introduction with applications in data science, volume 47, Cambridge university press, 2018.
David Xing Wu and Anant Sahai. Provable weak-to-strong generalization via benign overfitting.
In The Thirteenth International Conference on Learning Representations, 2025. URL https: // wttp:/iwww...eetoooo/a/aaaa/a/aa
Wei Yao, Wenkai Yang, Ziqiao Wang, Yankai Lin, and Yong Liu. Understanding the capabilities and limitations of weak-to-strong generalization. arXiv preprint arXiv:2502.014558 2025.
Difan Zou, Yuan Cao, Yuanzhi Li, and Quanquan Gu. The benefits of mixup for feature learning, In International Conference on Machine Learning, pages 43423-43477 PMLR, 2023a.
Difan Zou, Yuan Cao, Yuanzhi Li, and Quanquan Gu. Understanding the generalization of Adam in learning neural networks with proper regularization. In The Eleventh International Conference on Learning Representations, 2023b. URL https: pttttps://opereeeee /openreview wwt.:e///ffoooo aett/forummiddiiWplMee....
12

---

Contents
1
Introduction
1.1
Summary of Contributions
2
Problem Setting
2.1
Data Distribution
2.2
Neural Network Architecture
2.3
Training Scenario
3
Provable Weak-to-Strong Generalization
3.1
Data-Scarce Regime
3.2
Data-Abundant Regime
Key Theoretical Insights
5
Experiments
5.1 Experiments on Our Theoretical Setting
5.2 Experiments on MNIST
10
Conclusion
10
A Proof Preliminaries
14
A.1 Proof Preliminaries for Weak Model Training
14
A.2 Proof Preliminaries Weak-to-Strong Training
17
B Proof of Theorem 3.3
25
B.1 Preserved Properties during Training
25
B.2 Convergence Training Loss
30
B.3 Test Error
32
Proof of Theorem 3.4
34
C.I Preserved Properties during Training
34
C.2 Convergence of Training Loss
44
C.3 Test Error
45
D Proof of Theorem 3.6
53
D.I Analyzing Early Phase
53
D.2 Train Error
60
D.3 Test Error
60
13

---

A Proof Preliminaries
We use the following notation for the proof.
Notation. We define ,N = |e /aa, SNR, (o,l/(,,V)) Let S be the orthogonal complement of the span of the signal vectors {M1, M,,, M-1) We denote orthonormal basis for S by (bl...., bb-a).
For any vector v E R II represents the projection of onto S.
A.1 Proof Preliminaries for Weak Model Training
In this subsection, we sequentially introduce signal-noise decomposition (Cao et al., 2022; Kou et al., 2023) in our setting, high-probability properties of data sampling, and quantitative bounds frequently used throughout the proof for weak model training.
We use the following notation for the analysis of weak model training.
Notation. For each [nwwk] denote by v!") u, and the signal vectors and noise vector of the i-th input X,, respectively, For each v E {MI, 11-1, #v-1
i., we define s(²) and s!?) as the sets of indices [nwx] such that w!!h) and w (2) respectively.
A.1.1 Signal-Noise Decomposition
Lemma A.1. For any iteration t 2 O, we can write (t(()
(1) (1
( 1
11
p
VI
Σ
yiP
E: E
|
12
EE m
where (a _v( .Pi are recursively defined as
(1)
M(++1) M + n
Σ
Σ
Di
li
iES
SES!!
N(++1) No(1) + n
Σ
91
(0)
9i
(1)
Σ
9
(0)
Σ
gf
|u|
Dork
iES!!)
iES
ies(2)
iESt?
((+1) Pi P
(8)
gi |1::112
Towk
starting from M
NOO)
P: (0)
0. It follows that M and ( are increasing in iteration t.
Proof of Lemma A.I. It is trivial for the case t = 0. Suppose that it holds at iteration From the update rule, we have
(T+1) = (T)
x!!
(p)
Took
(e((
Pe
(T) (T) 11
M (T)
#11
+N((T)
(T)
yip!") &: || 12
|
|
|
i /E(nwkl
+ 1
Σ
(p)
Vigi
x
Tokk
(E (E(pma]
pE[3]
(p) are one of p1; 1-1, V1, 1-11 and E: By grouping the terms accordingly, we obtain Here x
(T+1) = (1+1 P1 (7+1)
P1
(1+1)
V1
(
Σ
& E
ViP
|
EE [ank
14

---

with
M(r+1)= =
+ n
Σ
+
Σ
Di
||eel?
Bokk
iES
iES
N(7+1) -N(r) + 7
Σ
Di
(T) +
Σ
91
Σ
9i
Σ
gi
Yoak
1ES%.
iES!
VES
tES
P3 (7+1)
(4)
7
11:.11.
Pi
93
Thuck
Hence, we have desired conclusion.
A.1.2 Properties of Data Sampling
We establish concentration results for the data sampling.
Lemma A.2. Let Ewk denote the event in which all the following hold for some large enough universal constant Cwk > 0:
1. For each E {=1} and L E [2], we have
s(t)
pb
| -
pb
Rook
Cwk
+
Rook
S
log
4
8
2
2. For any i [nowk]
|IE -12--ppd 4) Ownozet
1 1og
CwknWw
3. For any i,j E [mwk] with + j.
Cwkk
(E,, S CwroRdd y 8
flog
wk
Then, the event Ew occurs with probability at least
Proof of Lemma A.2. For each E {=1), E [2], and i [nwwk]
P ut
Pe
Pb
P
vs = P 1
- 11-
Ph
+
Ph
4
4
8
Hence, by Höeffding's inequality, we have
Pe
Pb
Powk
Cwk
28
m.
+
4
no
2
2
log
<
Cwk
and
Ph
Pb
Took
Cww ④
28
P
Dowk
2
log
2
Owk
Note that for each i [Rewk]. we can write E:
a = op
Σ
he(d-4)
where 2i, Ltd. (0, 1). The sub-gaussian norm of standard normal distribution (0,,1) is then (2 I's are mean sub-exponential random variables with sub-exponential norm
and
15

---

(Lemma 2.7.6 in Vershynin (2018)). In addition, Zr, 's with * are mean zero sub-euuueeeooeeee aub-exxonential random variables with sub-exponential norm less than or equal to (Lemma 2.7.7 in Vershynin (2018)). We Bernstein's inequality (Theorem 2.8.1 in Vershynin (2018)), with being the absolute constant stated therein. We then have the following:
P |1:11 oz - 4) 2 Cwiozat
log
CwkBww 6
Cwk 6
P
Σ (21,n)=-1) 2 Cwxd
log
hEld-11 11
90
CCweBook
< 2exp
log
64(d
4)
8
Cuktlwkk
28
s 2xxp
-log
8
In addition, for i, E [nrwk] with + j. we have
Cwk
Ef) Gurozat Viogs
P
8
=
P
Zi,hZi,i
2 Cwrdz Vlog
hEld-4]
900 64(d
Cuunhink 8
))
26
< 2 exp
wk
log
-4) 4)
Cwit wk
From union bound and a large choice of universal constant Cww > O, we conclude that the event E occurs with probability least
5.
A.1.3 Properties Used Throughout the Proof
We introduce some notation and properties that are frequently used throughout the proof.
Let us define
Cww
1
(Cwk
Bwk 4C Wowkk
V log 8
Twk
log
Kwk 2
2n
8
Under Condition 3.2 and the event Ewis the following hold:
By combining (C1) and (C5), applying (C2), and from Condition 3.2, Bwk and Ywk satisfy the following:
Rowk
min (pe. Phs pb}
Bwk
256 log T
Twk
(3)
From (C1), the following holds for any i,j [nwck] with + j:
3ddd 2
KE Eg>1
Bwrk Thokk
|KE, 112
Bwn
1|
(4)
1
1 2
Nwr
For any s, E {+1}, we have
(())
4.
Pe
2
+
Pb
nwk
(!)
Siv.
Ph
4
+
Pb
8
nwk
S
Twk
(5)
16

---

A.2 Proof Preliminaries for Weak-to-Strong Training
In this subsection, we sequentially introduce signal-noise decomposition (Cao et al., 2022; Kou et al., 2023) in our setting, high-probabillty properties of data sampling, quantitative bounds frequently used throughout the proof, and a technical lemma (Meng et al., 2024) for the analysis of weak-to-strong training.
We use the following notation for the analysis of teak-t training.
Notation. For each i E [Mat], we denote by 0. -6(²) and É. the signal vectors and noise vector of the i-th input X,, respectively. For each v E { p 1 = and E [2], we define cl and F( as the sets of indices i [m such that o.") v and the supervision corresponds to the clean label (i.e., 0i = Ui) or the flipped label (i.e., Ds = Ūt), respectively.
A.2.1 Signal-Noise Decomposition
Lemma A.3. For any iteration 2 O, we can write each weights wh? with s {=1),r e [m] as
wh w M M
lhs
+ M(it) p-s
No Us
NOO V-s + Σ bir
|za1 +
Paind || 12
||ee!1
|1/11
sE|mal
where !0
s,r: s,r1 arr soro Parn are recursively defined as
M(0) (()
(() (t)
M (((1) M
(A)
Σ
(0)
||a|/ . 1 (11!00 ( 11s) >0 =
Di
msst 1E[2)
iEel!
SEP
M((41)
M
7
Σ
(t)
Σ
(1)
|1a112 1 [( (100 a, 1e pe-s) > 0/
Ji
mfst 1E(2)
iEc!!)
SE
N(((11)
((())
7
Σ
(t)
||0112- {( (1!h v., > 0]]
9,
p.r
myst
LE[2]
iEC!!
iEF!! (1)
n
(t)
Σ
(0)
||0| 1 [[ (w v2) <o]
9i
9i
mill
[E[2)
(EC!!)
(EF(!)
N((+1)
(1)
7
Σ
(1)
Σ
(1)
||]1 1 {{ (w0 s.ro u_s) )
D
Di
5,7
myst
[E(2)
iEc!!)
77
(4)
Σ
(1)
||n|
( (w0 (1)
<0].
Di
mill
TE(2)
iEC!!)
(
((+1)
súm (2) 11E:11
[ (un!)) (t) E, > 0
Ps.r. Parri
mmst
starting from M(()) = MID = N((0 s.r
8. = NoO = Pert = -. For simplicity, for any iteration
(t)
I E [0, r E [m]] and E [naa], we define Pr. = Purs and p10 = (t) is increasing and gl is decreasing in iteration l.
P 11 follows that Pra
(t)
17

---

Proof of Lemma A.3. It trivial for the case t = 0. Suppose it holds at iteration т. From the update rule. we have
w (T+1)
w
(7)
Σ
de प. 1
(wo,77- xx.²)
> 0 2;
(p)
maat
pE[3] EE [nae]]
w!! + M
M
+ M(7
1
+ +V((7)
Us
+ No77 v-a
(r) &. Pari
|al| 2
||
grr
||0|1
||
+
[
iE mmee
31
(T) 1 (wo
0.r x ((1))
(T)
0
(n)
Di Di
pE[3] iE|mal
Here, 7, 2(P)'s s are one of μ1, 1 V1, 1-1, and É. By grouping the terms accordingly, we obtain
w = w.! +M
1] pes
+M
p_a -V(tt1)
v.
+((++1)
(r+1) &. Parr
5,r ||
||
||
|
||
SE sE[mal
with
M Mr (T+1)
M
(7)
n
gi
(r)
Σ
|al| 1 [[[ (w(77) Ms) ) >0 >0]
mmst
1E(2]
iEF
M(++1)
= -M(7
Σ
||u|| - 1 {( ( (k_s (w/ > 0]
msst
12(2]
SECL
(T+11)
(
Σ
(T)
|1011 -1 (10 vs) > o].
(r)
D
Di
msst
[E[2]
iECH
iEFL!
Σ
||u||2- 1 (n0 3, Us) =o].
mi&s
tE(2)
iEC!!)
Mx
1((++)
-
Σ
|1a1| . 1 ( (uu(t).o.)) > =0]
5,r
=
K,T
[E[2]
iEC
iEF12.
Σ
|111 1 { (10t7.1 v_o) < <0].
m&ss
(E(2)
iEe!)
(r+1)
(7)
SyJn 11 1
{
(w
E,
> 0]
Parn = Paand
mngt
Hence, we have desired conclusion.
A.2.2 Properties of Data Sampling and Model Initialization
We establish concentration results for data sampling and model initialization.
Throughout the proof, we frequently use the following quantities. For each s E (+1} and i E [mat]. we define:
Pat 8 MM = fre [m]: w us) > =0.
nu := (2no+pb) Po ny
(0)
AA=== = {re(m)) [m] ( (w!tr, vs) > 00. B,
B,: : frr {re [m] (wo.. vs) <0}
18

---

X2 = { [m]
Lemma A.4. Let Est denote the event in which all the following hold for some large enough universal constant Cat > 0:
1. For each
{=1}, 1 [2]. we have
(1- (1-Cx') ny -
c
|
s Cat
ng
and
(1- (1-0zz)) Rp - c(0)
-u
S (1 + C.t
nl
S Cst
ny
2. For each
{=1},r [m], and [nst]
m [Mall
2
.||4.11
m
2
|B
m1
2
S
V
m
2
log
Cst
8
and
Cst
|XX
1 V
log
2
2
3. For each s, E {+l} and r E [mm].
K (wo!))
(0)
[Tea||
)/-
(0) p.r
Vs
|
S oooo
2
Cse
4. For any [mat]
||5 - oz(dd 10-44 4) S &Croeety
CCttaat
5
5. For any i.j E [ma]] with + j.
Cann 2
K (E., ki) o V Vlog
6. For any E ( [m], and i [nac].
Kuot). <:> s Curopopdh y llog Cat
7. For any E {+1) and E [m].
10 (0)
s.r |2 < 20
Then, the event Es, occurs with probability at least 1 -
Proof of Lemma A.4. We begin by showing that each statement holds with high probability, and conclude the proof by applying union bound. We prove the statements one by one, marking each with once established.
We fix an arbitrary s E {+1}. E {+1} and E [na.]. We have
I i C!!) 14.
=P Wilwx (w,, X,) >0 (0(0)) , )(3-11) (Mss (a) p (150 (((--)) (p., (e)
19

---

P frk w", Xi
> 0
33 1)
(Hes 23)
P
, x((0-11) (1s, (Hs)
P
(ir Jwrk 100, x:) > 0
1
(3
(Ho: vs))
P
(1(0) 83 0/3-11) = (Hss -ua)
Ji Swk (wo", xx) > 0
0
= (Ms, us)
Pe
2
P Jikk w0" X > 0
(0/) 0
13-1 1) = (Jss vn)
pb
8
-P P Swkk (w"" X; > 0
(3 0) = (Hss - us)
ph
8
From the conclusion of Theorem 3.3, we have
P Ji (10", x; > 0 (1
(1()) 10 -000-0) = (1ss [sm
2 2 20st*
P Wiffw (w", Xi > 0
(6.0) 8. 1)) = (Hes Us)
21 - 2Cst
and
P Vefwk (w0 ,X,) > 0
(1)
ū , 015-10 = (ks, -vs) 2 1 20st
Therefore,
1 - 1
-n E ||//00 S np
2Csr
and
|
E c
11
E
= nu
S
20
By Höeffding's inequality, we have
p
c
-E
E
Nut log
Cst
25
Ca
and
PP
[()
-
E |
2
nsst log
Cat
<
25
2
8
Cat
Hence, combining with (C2),
(1- st
<
c!l Ms
<1 +
S
C,T+)
|2x0 S Caat Ryp.
with probability at least
Cat
Now we address the case vs. We have
P i E
c00
= IP
Tifwk
w.,
X,
>
0
0
(3-1) 1) = (Vo, us)
p (b) ((
00 (0,0)0000 (((--1) = (vo.HH))
Wi.wk
w. X,
(3 1)
= (v,, v2)
P *[(() ( 0 (0-1)) = =(v,. Us)
+
ww,, Xx, > 0
11)
= =VVe- vv))
P [[(7) (1(0) 0.00 )10-1)) = (Vo. -Vs)
= IP (p.Swir
w,, X; > 0
1)
=(V,, 1b.)
Pb
8
+ PP Vifwk
(w,, x,, 0
(1)
8 (31) = (V,, v))
Ph
8
+
PPPP ji.ww
(w', X, 0
(1)
0.8 )(a-1) = (Va, -2,)
Ph
8
From the conclusion of Theorem 3.3, we have
P ferk (w=,xx,) xx, > 0 (500) (,,0))((-1)) = (vs, [bm 21- 1
2Cat'
20

---

From (C6), we have
E
-
Ph
8
Ph
not
11
2Cst
1
nl
and
E
c00
us
2
1
20
1
Pollst
1
20
1
In addition, we have
(
Pb
Ph
||000
1
Ph
Ph
2ny
E
-
+
nhat
E
<
g
4
20
8
4
3Cst
By Höeffding's 's inequality, we have
|
nst log
Cst
26
P
E
8
Cst
and
IP
F(0
- E [
2
nsst
log
Cat 5
26
2
Cst
From (C2), we have
(1-Cz²) ny S c/00 < (1+ Cza' <(++Cz)) np,
|
S Czz 1 -22
with probability at least
46 where the last inequality follows from Condition 3.1. C..
Using a similar argument, we also have the desired conclusion for the case -V,.
Let us prove that the second statement holds with high probability. we fix arbitrary & E {+1) and i E [nat]. For each e [m]. PPrr E MM]] Fir E A.] = P(r B.] Pfr E X,] 2/4 By Höeffding's 's inequality, we have
Ma
m
2
m
log
Cat
S
28
2
2
8
Csa
m
m
Cst 8
28
IP
log
<
2
2
mC
P
|B,l
m
m
log
Cst 8
28
2
2
Cst
and
m
m
nat
28
P
X
2
V
2
log
8
<
For the third statement, we fix arbitrary 8, s' E 1=1} and
E [m]. We have
(i)
(o)
Vs'
itd
|
Hence, by Höeffding's inequality, we have
Cam
28
P
(0) s,r
> 001
2log
<
Cam
Similarly, we also have
IP
w
k.r.
(0)
||
Vs.
> ooy?
2oo
Csem 8
< 28
Cam
21

---

Before moving the remaining part, that for each i [msa], (+1), and [m]. write & and ug (0)
as
= Op Σ b,
Ig (0) op Σ bg
hEld-4) 4]
held-4 4
where h, Bank Ltd. N/0, 1). The sub-gaussian norm of standard normal distribution N/0, 1) is v and then (Z.,h) 1, (h) I's are mean zero sub-exponential random variables with sub-exponential norm (Lemma 2.7.6 Vershynin (2018)). In addition, Zs,r,hZi,h 's and 24,6 with o i are mean zero sub-exponential random variables with sub-exponential norm less than or equal to 3 (Lemma 2.7.7 in Vershynin (2018)).
We use Bernstein's 's inequality (Theorem 2.8.1 in Vershynin (2018)), with e being the absolute constant stated therein. We then have the following for any [nat]:
P |
oz - 4) 2 CaloZet
/
Cst δ
P
Σ
(zi.N)² - (1):h)=11 2 Cadt
log
Cut Mast
8
hEld-1]
9c02ed d
Cat
< 2exp
log
64(d 4)
8
[CatMlss
26
2xx
(llog
Tst
For i,j E [mar] with + j. we have
Ca
PP
(.., E)) 2 O
log
IP
Σ
Zi,h2ihh
2 Czedt
llog 8
he(d-4) 4]
9cC2,d d
Cat
< 2exp
log
64(d - 4)
28
Cang
For any s E (+1),r [m] and [naa], by applying Bernstein's inequality, have
(0) w s,r+ Ei) 2 Cao V flog
CCtt
Carmrnn
=
2 Candt flog
6
hE(d-4] 4]
9cC2d dd
CCemmna
< 2 exx
log
64(d 4)
28
16mni
22

---

By applying Bernstein's inequality, for any E {+1} and [m]. have
1 P
200
S P
11 w!
od - 4) 2 Casodet /lo8
Cstm
(Zamn)² -1) 2 Cand V
Cstm
P
log
8
WE [)
9cC d
Caam
< 2exp
64(d - 4) log
Cat ))
25
< 2exp
-log log
S
Cam
where the first inequality follows from (CI).
From union bound and large choice of universal constant Cst 0, conclude that the event Est occurs with probability at least
A.2.3 Properties Used Throughout the Proof
We introduce some notation and properties that are frequently used throughout the proof.
Let us define
att := 2C's max ||4| |||||l opdtt o }
2 2
8
CCstRat
Bx == 4Cae / log
8
and
Kst 810g(12), Aae := exp(21sst).
Under Condition 3.1 and the event Est. the following hold:
Ost and Sat are small enough satisfy
1 Pb |1
ond
Oest < min
100
aed
(2pe + Pb)mec |1 S.
Bat log TM
<
100"
(6)
For any s, s E {+1), r E [m]. and E [nsel=
K (w!)) Me'' (o!) s.r, Ms!
(w Ei) ast.
(7)
From (C3), for any i.j [ma]] with of j, we have
o2 d
3d
(E., Eg)
Ast Nist
Bet Nhat
|EE.12
oz 4)
Bno
2
2
||
||E:
nstt
(8)
For any E {+1), E [m), and i E [Pat),
we have
MM
1
A&
1
[B.1
<
(9)
2
2
2
10"
The learning rate rj small enough to satisfy
Bam
Bam
Bam
7 S min
(10)
207d
2Ast
||
2h ||/112
23

---

A.2.4 Technical Lemma
We also introduce a technical lemma that enables a tight characterization of the learning dynamics.
Lemma A.5 (Lemma D.1 in Meng et al. (2024)), Suppose that a sequence ot, f. 2 0 follows the iterative formula
a++1 de + + bear"
for some c E [0, 1] and 2 Then it holds that
Dt S 04 + beao
+
for all Here, Te the unique solution of
It + be cl an 0e
24

---

B Proof of Theorem 3.3
For the proof, we first introduce properties preserved during training (Appendix B.1), then prove the convergence of the training loss (Appendix B.2), and finally establish bound the test error (Appendix B.3).
B.1 Preserved Properties during Training
In this subsection, present several properties that remain preserved throughout training.
Lemma B.1. Under Condition 3.2 and the event E have the following for any iteration t e [0,T*
(WI) S d s 4log T for any E [Nww]]
(W2) m. tpul SNR Pi (0) 12
I M I (2p + Po)SNR Pi for any i E [nwk], s E {+1}.
(W3) pi
(8) Pj
S Eag for any i,j [nwk]]
(W4) 1is (wolt,Xx
yソ fwk (wit), xx)x S ta for any i.j [nwk]-
(W5) 1 - Kwk S 8.
S 1 + Kwnk for any i.j E [nwk].
(W6) !o!0 S (2ph + Pb) Pi for any {+1), i E [m].
Proof of Lemma B. is trivial for the case = O. Assume the conclusions hold iteration / = and we will prove for the case = T + 1. Note that (W2) and (W6) at iteration t = т, along with (C5) and (C6) imply that
|NS0| < (2pm + +PD) xf²)) S Twk (2pe + PO)SN m/
1
1 M
(11)
24
2
for any 8, E (+1} and i [m].
(W1): We fix an arbitrary i E [[ww]] and we want to show PÚ pf (++1) then we have
< 4 log
If xT < 2log T"
30dd
(r+1) Pi
Pi (T)
" (T)
Di |1 2 log T
4logT"
Tlok
where the first inequality follows from
9
(r) < 1 and (4), and the last inequality follows from (C4).
( < 2 log T < ((+1) since pú" is increasing in iteration t.
Otherwise, there exists < r such that
From (4) and (C4), we have
(r+1) = p. + ((++1) -p.0) + Σ (p. (14+1) -p!")
p
t=i+1
(
9: ||E.1
(
9 ||E,11
(t)
Pi
nw
Rowk tmē+1
< 2loog T +
"
3
d.d +
71
od Σ
Bowk 2
Towk 2
tiit
3no 2d
<3log T
p
Σ
exp (-BiSwk (zn(0,x,)) xx)).
2n
1=t+1
25

---

For any iteration t E [E+ 1,7], we have
W:Jwk (10()) x,) (t) -vu + ( (t) ,00, (22) + +/(+0 (t) , -1tii)
2 - 2 max |N101 |
(2)
Σ
(1) Ex)
Pi
||5,11
je(mmal1(()
2 max 11140/ |
Ps
Σ
(50))
1EE.. E,11
||&,11 11
jelnmal 110)
KE E,)
4n (2ph + Po)SN
D. + pi (t)
Σ
||E,
2 4n (2pb + PO)SNR loo + +2log T
4 4log T Bwk
(1 w + Po)SNR 28wlc) 2 2log T
2 log
where the first inequality follows from the fact that M M 2 0, the third from applying (W2) at iteration t, the fourth from (WI) at iteration t and (4), and the last from (3) and Condition 3.2.
Now, we have conclusion
S 3 log T + 3n02d
(r+1) Pi
Σ
(-ifww (1o()) xx)) x:))
exp
no t=i+1
S 3 log T + 3n1 Σ
exp
(-log
2n t=i+1
3no p T exp T*)
< 3 log T +
2n
< 4 log T"
where we applied (C4) for the last inequality.
(W2): We fix arbitrary s {+1] and i [mwck]- We have
M(r+1) - -M
Σ
9j
(T)
+
Σ
|1leal?
no
JES
JES
17
Pe
Pb
nwk (0.²) (1 + nwn)) ||eall
2
+ York
Towk
2
3
pb
nowk 29. (T) ||ee|l
2
Towk
2
2"
3
(2pe + Ph) 9;
(T)
||
where the first inequality follows from (W3) at iteration and (5), the second follows from (3).
From (4), have
n0 d (r)
(7+1)
7 -
Pi
2n Di
Dork
and thus,
M M! < 3r (2pe + pb) SNR2 (p(r -o-t1)-pp -p(tt).
Combining with (W2) at iteration 7, we have
M(++1)= M(T) + -M)+)
< 3n 32p + PA)SNR? 05" + 3/ (2pp + po) SNR (pitt3) -1))))p(7))) -p(T))
26

---

(2pe + Po)SNN Pi of
Similarly, we have
M - M
Σ
9
3
Σ
of
no
JES
jES
2
Pr
Ph
Ywnk
Dowk
(of
(T)
kiwk))
1|eall?
nw
11 2
1
Pe
ph
Towk 29 (T)
-1|zal12
Nwk
2
7 (2pe + pb) 9
||
where the first inequality follows from (W5) at iteration T and (5), and the second follows from (3). From (4), we have
3nd p (r)
pl (T+1)_ - -p/-) = 7
9, 11,11
9
nowk
2n
and thus, we have
M(T+1) M(T)= 1
12 wk (2pe pb) SNNR, (D: (1(7t1)-pp 15-1)
Combining with (W2) at iteration T, we have
M(++1) = M +
M(
2 12 Towk (2pe + pb) /3
+
1
niwk (2pe pb) SNR? / (p. p= (2
12
12 Towk (2po P&)SNR Pi
(r+1)
(W3): We fix arbitrary i E [nwwk] with i * j. Without loss of generality, we assume that p. 272/0 p/
From (4) and (C4), we have
30
Pi ((+1) - (T+1)
Pj = p. Pj
(r)
+ 71 -() 9i ||E.1| - 035 11=:11²) 2
17
2
Kwk 4
lokk
Tlwkk
Thus, we want to show that (1+1)
pfr+ (r Kyk.
If p -0-7) < Kuk from triangular inequality, (4), and (C4), we have 8
30 dl
P; (r+1) 155 (1-1)= = - 157) + 1
gi 1 96²²) 1|&)1²)
Kwk
11
Kikk
S
Dowk
nw
Otherwise, we have
Vifww (w)(T) x,, yj fwnk (wo(t),xg
(T) 2/ (1()) + =,(²) + E:
(1)
(T)
[0) + uf + Ex))
(1)
2 pp: 03 (11) -3M(7) + Σ
(r) (E,, Ev)
Σ
(T)
E,))
1|E:r1"
||E
j'E(Meul\()
(1(²) (1 -3M(()
Σ
(7) KE E.>i
Σ
1|
||E
112
VE
j'ElnwuJVU
Kwk
-3 3 3n (2po + ph SNNR
4logg T 2 4 log T Bunk
8
Bwk
> 0,
16
27

---

where the first inequality follows from (11), and the fourth inequality follows from (3) and Condi- tion 3.2. Then, we have
9 1ell
1+ exp [yffwx (w) xx)) |
|5
+ exp (UkSwk (WO(T) X:)) ||&
9j
wjf (20(1) xX,) fofw (20(t), xx,) (1
Suk Towk
I exp
link
Book
I cxp
16
Bwkk
< 1.
Therefore, we have
Pi Pj =p,-) -p;
(++1) (r+1)
(7)
(o!") 1IE.11 - 9j
(T) [1s/1()) S <p,T) -p3
Kwk
Pp
+
nwk
4
(W4): For any i [nwk], we have
wifwk (w0(+1),, .x)) Vjfwk (wo(T)), ,X})
(wl(+))) :1// (/:- + -0.²) + E1)) - (T(+)) ,39 (010) + of+²) + E3)
(1)
(p) ((+t)) - o + 3.
yidr (r+1) Ex)
B,Ur (T+1) (5,, Ep)
Σ
||
|1
(0.- (T+1) - p, p/++)l)) + 3M
(T+1) (E:.E.))
(++1)
KE Ey>>
|15
1|5,,11
PElMwk]M
I J'E(nwullfb)
liwk
+ 31 (2pe + P 4log T + . 4 T Buk
fiwk
2
where the first inequality follows from (11), the third inequality follows from (W1) and (W2) at iteration 1, which have shown earlier, and the last inequality is due to (3) and Condition 3.2.
(W5): Let us fix arbitrary i.j E [nw*]] and assume yifww (w(++1,, 2 fy (w(++),, X,). without loss of generality. Then, we have
(7+1)
1 exp (JhSwk (((++11)))))
9j
5
[++1]
1 exp (WkSwk (w(r+1), xx))
9i
S exp Wiikw (wo(r+1)), ,x:) Uz Si (wo(++),,xg xx,]
< + yiiww (20(++1), xx) fjfwk (w((+ X,) ]
< 11+ Kwwk
where we use the inequality e² < 1 + 2z for any 2 E (0, 1), which is applicable due to (W4) at iteration 7 + 1. In addition, we have
(++)
1+ exp fwk (wo(++)), x,))
1 >
(7+1)
1 exp (JiSwk (wor++),, X:))
9j
Jz (T++1) xx,) Vifw (w (w((++),xx)
2 exp
> +
fj X,) Vifwk (w( X:
Kwkk
28

---

where we use the inequality ot 2 1 1++ 2 for any 2 E R.
(W6): We fix arbitrary 8 {+1] and i [nwi)]. We have
N -1-+))_((7)
7
Σ ( +
Σ
Σ
E og ||011
9j
93
JESL
jES
JES
JES
7
[
(
|
) (1 + Kiwk)
(150)))
+ | 1) (1 - kiwk)
9 111
wk
1/
+
v.
"
Ph
pb
Twk)
(1 + kiwk) - 2
Ph
pb
Twk) ) (1 -kwx) 3 1|11
n9
(1)
2phh + Pr.
liwk + 4riwk
||u|12
2
((pp + pb)9, (T)
||/11
2
(2ph. + (bb) (o))mwklull?
(p(-41)-p(") p!²))
2/
where the inequalities follow from (W5) at iteration T, (3), and (4) respectively. Hence, we obtain
<(() N(++1)
+ (2pb. + Pb Pb)mwkllle 1|212
(e. (p/++1)- p. (
E.
NSO) + (2ph + DR)
(p. (T+1) - ps²t)
S (2ph + D Pi + (2ph + Pb) (D! -p:" p,T))
(2pa- + Ph SNR, Pi (T+1),
where the second and last inequalities follow from (5) and (W6) at iteration t, respectively. Similarly, we have
((++1)_ N(())
Σ gj
+ Σ
(T)
Σ
Σ
oftt) ||1112
gj
9j
JES
JES
jES
SES
77
[(s)]]
+ |/2) ) (1 - Kiwk)
(1s())
+ |
1) (1 + kmn))
g (1) 1112
-v.
7l
1
Ph
+
Pb
+ Ywk)
(1 - kiwk)
2
Ph
Pb
1ik) (1 kmn)
9 ||/12
4
8
8
(7)
[2ph
Ph
Kink + 4rwk
||
2
(2pp + Pbb)); (T)
|/2111
2
(2ph. + Pbb) Tw |212 2
(p: (1+1) -
-p(")) =)")),
1| 2
where the inequalities follow from (W5) at iteration r, (5), and (3), respectively. Hence, we obtain
N(1+1) ((F)) (2ph. + pb) m
(((+t1))
- pf:))
1|
N(G) (2ph + Ph Dh
(1/ - -1(-t)
2 (2ph + Pbb +PDD (17)) -2ph + Pb) mO (--t))-("))
29

---

-2pm + SNRRE, p (++1)
where the second and last inequalities follow from (4) and (W6) at iteration 7, respectively. Therefore, the conclusions hold at any iteration E [0, T"
B.2 Convergence of Training Loss
In this subsection, we prove that the training loss converges below within Ô (1)-t-- -owke mwwkdt All the arguments in this subsection are under Condition 3.2 and the event Ewk.
Let us define
e == log((4/))
Σ
yiC. ||E:||
/E(nwal
which plays crucial role in proving convergence.
Lemma B.2. Under Condition 3.2 and the event Ewk we have the following:
to Yi ww (w)(t), X:) 20) 2 log(4/e) for any & [T. T*).
||قه||| s 3og 3og(4/)) (4/E)m
Vi (1) s 20 Lonk (w(()) for any t E [0,T")
Proof of Lemma B.2. The first statement follows from
| = (2log(4/s))
Σ
y:Ei ||E:1| 2
E [m
(Ex+ Ei)
= (4/0g244/E)
Σ
|| 1-
Σ
||&:1] 11
||E,
AE kE[nwk]
( (
((E Ei>l
< <4log"(A/e)
Σ
E
|1&/1 ||E,11
AE kE(nwk]
2
Bwk
2
< <4log"(4/5
Tlwk o7d
+ n
Pork
07
2n (1 + Bwnk)
=4log2(A/e)
oRd
< 99log
Tokk ozd
where the second inequality follows from (4) and the last inequality follows from (3).
Next, let us prove the second statement. For any t E [0,T"). we have
yi Vunlww (w)!) X,
Vi
D (1)
(2)
E 2 2ogg(4///
Σ Un 11,,11
JE (m
(E:
log(44/)
yilli
||E,
(Es. E/)
2 log(4/)) -
Σ
2 2log
||E, _|
30

---

2 2(1 Bwk) 14g(4/E)
2 1og(4/E)
where the second inequality follows from (4) and the last inequality follows from (3).
Let us prove the last statement. For any t E [0, T",, we have
V liwk (20()))
Di Vi
vi
(2)
6:
Dok [Mwik]
(2)
(1)
+ v,- + E:11
Ji
Took VE [Rackl
gi
(1)
20
Took (Rokl
S 20
Ji
Toock :E re(m
S 20
(WiSwk (wo Xi))
Tlwk #E|nwal
20 d. Lwkk (2o(1))
where the first incquality follows from the triangle inequality, the second follows from (4) and the bound |al² || dd implied by Condition 3.2, the third follows from 1 and the last follows from - (2) S {(2) for all E R.
Eie inwal g
Lemma B.3. Under Condition 3.1 and the event Ewko for any iteration T [0, we have
1 T
2 2
Σ
Lwk (w((1)
T
1/T
2
t=
Proof of Lemma B.3. For any t E [0,T"*, we have
(t)
w (t+1) 2
w
w
(!)
w 2
(t) v V Lokk )²²
2n LV (t)
(t) 2 - 11² VLww (20(0))² 1|²
2m Σ Ji ((uVSww (wo(), xx) ,80) Sww (uo!t), x.)) -1² Vlowk (1) ||²
Towk sE(mwll
21
Σ di (log(4/s) - -yifkk (w)(), .x.)) - 1? VLwx (2011) 1|
z Towk i (mwk)
2m
e e(v. (00()) (1o1))
8)
172 VLwk )|
now sE(nwk)
4
nLwk
(2)
T
2
where the first inequality follows from Lemma B.2, the second follows from the convexity of and the bound ((lo((//)) 8/ 4, and the last follows from Lemma B.2 and (C4).
By applying telescoping sum and using the fact that w
O, we obtain the desired conclusion.
31

---

Using lemmas above, we can prove that the training loss converges to below E. By applying Lemma B.3 with iteration T [18m e log log(4/E)mwzd On " "wwdd 1op 0p²) and using Lemma B.2, we obtain
1
f
Lwk (uo(t))
| 1 nsT -
(4/E)(4/) op2
2 S.
1/T
Therefore, there exists Twk [0. 7 such that Lwk s In addition, for any W1, W2 E R we have
V [ook(wi)) Vnn (wwlwx(u22)
Σ
Bele We(C(VsSwkkunn X:)) (Vifunuuu, X.)) ( (n..) + o² 5.
Rok
iE|mwal
[lee (Biffnn(1) Xi)) - e' (UsSwk(uzg X:)) po (1) + o!?) +
Rowk :E(nwa)
Σ 1(fuk(11 fwx(wws, X:))
21
iE(Dwk)
v20
1 + +u²
(1)
(2)
+ -1w1 w
2nwk
iE(nwk)
Lond w2ll.
where the first and third inequalities follow from the
inequality, the second and last implied by Condition 3.2, and for the
inequalities follow from (4) and the bound ||/| ||
< and
second inequality, we also use the fact that 0 < l' < 4-
Since Lwkk (w) is d-sothh and the learning rate satisfies (10), we can apply the descent lemma (Lemma 3.4 in Bubeck (2015)). This proves the first part of our conclusion.
B.3 Test Error
In this subsection, we prove the second part of our conclusion. All the arguments in this subsection are under Condition 3.2 and the event Ewk.
Define (1),, (2), and & as the signal vectors and the noise vector in the test data (X, respectively.
For any iteration & E [Twk; T"] and for the case given (X,y) y) E Se U Sb. we can express the test accuracy as
yfwk (() xx) < (x, .y) E E US}]
IP (1 E) < (mrol))
<)<-(vo(() _0()) ) (yro((,,022) (X,x) S. Us.]
() <) M
IP
PP
z
where z ~ N (0.02 [s2w((0)) and the inequality follows from (11). By Höeffding's 's inequality,
have
(2 2
PP yfwk (wo()),xz < <o v) E S. u.. s exp
807 [s20(o)12
32

---

Let us characterize
| We have
(
Jip,
2 Ei
||Eil -2
Ronk
(x²)) ||5.11
Σ
Σ
(0 (0)
1.5. E,>
Pi Pj
||& 2 ||5
rE(nwel
rE(nmxl j [imnklitt
(.500
2
12) 2
(1) Pi
Σ
Σ
+
Bon 2
0gd
2
no
ogd
iE sE(nwk]
VE <[[wwll jE[nwk]
4
)
2
o0d
iE [mak]
12
(MI())
Rwkk 0z
Dowk (2pe + Pb) SNR,
Took (2po + po) ||/1| (AL())²
57
2
where the first and second inequality follows from AM-GM incquality and (4), the third inequality follows from (3), and the last inequality follows from (W2). Hence, we have
Towk (2p. + Pp))2 ||eal1" )
P Julw (w0"),)] <0 (X. E S. U.U. S Sexp
460803d
33

---

C Proof of Theorem 3,4
suffices to prove the following restatement of Theorem 3.4.
Theorem C.1
Training,
Regime). Let W be the iterates of weak-
to- to-strong training. with the weak model fwi( (w", .)) satisfying the conclusion of Theorem 3.3. For any ε > 0 and 8 E (0, 1) satisfying Condition 3.2, with probability at least 1 1 8, there exists Tw2x = mmmadd
such thatfor any E [Tw2s; TM) the following statements hold:
1. The training loss converges below E: La (W <E
2. Let (X, DD be an unseen test example, independent of the training set {(Xx
is Ds))
(Benign Overfitring) When nappi |1||* /(0/d) 2 C2, we have
P Ufa (wrl), xx <0 (X. <0 E S. uSA S eexp (- nat (2pe + Pbb Pl
C2ofd
and
P afa (W(O) x) < 0 (x, v) E ES]] s exp (- |s
(Harmful Overfitting) When n |||| /(a3d)) s Cs.
P yfat (w()) x) < 0 2 0.12ph.
Here, C2 C3, C4 are constants.
For the proof, we first introduce properties preserved during training (Appendix C.I), then prove the convergence of the training loss (Appendix C.2), and finally establish a bound on the test error (Appendix C.3).
C.1 Preserved Properties during Training
In this subsection, we present several properties that remain preserved throughout training.
Lemma C.2. Suppose for some iteration t [0, it satisfies M
S ait + Sar.
0 S Prik I 4ogTT, and -as - -5Ba log T S pl s for any s E {+1), E [m]. and i E [mat]-
Then, for any i E [ma] it holds that
F-g. (!) X3 I
Kist
o ((00)--)))) - -p:ol S
figt
16"
16
Proof of Lemma C.2. For any i E [nae], we have
F 8:
((())
X.
0:
1
Σ 0
(t)
Br.rr 10. //.))) + (w x((i)) + to ((w E. E:
rE|m]
1
Beims of o (
(w0 - Benrs of
(w -o E:>1
m
rE|m]
1
Σ
(0)
Dirro af
+ (
ww (U)
Desro 8 {1-)) >
+ 2 (ast + Bar) + ( ww "...rr:)))
< m
w
rE[m]
< (4ast + 2.3xa)
+
1 Σ
(t)
"
(t)
{
m
re[m]
34

---

where the last two inequalities follow from the given bounds on for any E [m]] we have
N(O M s.r
and (7). In addition.
(E:. E
w
(6) Brrr
E.)
=
-
w
(1)
B, E,
200 +
|6
jemmall(ss
|(Er, E,>
Wirr E:
p())
Σ
Nh.ra
||
jE(ma]((0)
20 93at log T
where the last inequality follows from the given bound on pr. Pr.i E [m]] we have
(00) (7), and (8). Similarly, for any
(E,, E,)
w (0) Uc.r. E.) = =(w0))
(U)
E,
100 +
Σ
Di.r
DESTI
|6S11
jE(msI](
I( E
w (0)
B. E.
(t)
Σ
||
jE
S Ost + 48at log T",
where the last inequality follows from the given bound on 7:3 p!0, (7), and (8). Hence, have
F-g. (w 9. X.) S 6ast + 23st + 98s log T S
Rig
16
where the last inequality follows from (6).
Next, we prove the second part. For any E [mst] and r [m.. we have
o (w ( E.)) - p.7 = o w
(t)
E.))
(p!h2
Berr
u g..r: 5.)
-Pri
(t)
Pr.i
KE E
Diam E.
(1)
1|E:
jE(maJ](
I agt + 4 log T
fige
16
where the third inequality follows from the given bound on (t) o (7), and (8).
Lemma C.3. Under Condition 3.2 and the event Est, we have the following for any iteration
t t (0,T*):
(SI) -0st 5,at log T S 200 < 0 and O S p/9 S 4 log T for any i [nea] and [m].
(S2) 1ft 2 1, then for any & E (+1}, we have Mi(() sir 2 M for all r E [m].
N'1))
o,r 2 N for
air
all r E A.. and (1) ar < N!t-") for all r E B.. In addition, [
x(0) Air
S ast + for all
E [m].
(S3) For any s {11} and i E [nar], we have
n SNR,
(( 8,r S GAR
Σ
Pro
12\
rE(m]
re [m[m]
rE(m)
n2p SNR?
A(t) oir S GD GALt
Σ p!!
PrA
12
re(m
rEA,
rE(m]
35

---

(8)
N/(1) or S SAget
Σ
(3)
Prs S
Prçe-
121st
re(m]
rEB,
re pm)
(S4)
(ir.at (W(1), x:) - Ere(m) Pris (2)
" forany any i [msa]
(S5)
1 [Ere(m) Pr. Ere(mm) Prol S rist for any i E [mse]-
m
8/0 (S6)
S dat for any i.j E [maa].
(S7) For any i E [Ma] and r E [mm] ( (w! birr Ł.)
> 0 is ( bi.r Ei) > 0. Furthermore, for any
i [nai] and r E X, P. = Elm) Pr
(S8) Let I be the unique solution of
no p 1 + (xp(Fist/A)
It + exp(x; + Kist/ 16t//16)
8mnnst
It holds that for any E [Mat].
Σ
Ft S m rE(m]
Pr.
Proof of Lemma C.3. is trivial for the case 0. Assume the conclusions hold at iteration t and we will prove for the case = + 1.
(S1): We fix arbitrary E [msa] and E [m:] Let us prove the first statement. If p(T) n,
2 -Ost. 4.st log T* then we have
3no p
(
1 >
Osst 4,3ar log T*
2 -0st
5, log T
mnnt
2mng
where the first inequality follows from (8) and the second inequality follows from (10). Otherwise, we have
E,)
(T) - B.rr Es) = (w=
:u.: - 5,) + + +
Σ
(r)
P-air
||
jE(malltst
(E,,E))
I Ois + (-ast - 4Bat log T*) +
Σ
(0())
je(maliff
Sat
< -43st log T + nst 4 log T
0.
It implies (1+1)
(T)
ast 5,ar log 7 and have desired conclusion.
r2
Next, we prove the second statement. If p(7 < 3 log T* then we have
3no
(T+1) Pr
Pr.
" mint
1 1 < log T
< <olog T*
2mn
where the second inequality follows from (8) and the third inequality follows from (10). Otherwise,
(f+1) Then, we have
there exists < 7 such that P7 < 3 3lg T < Pnr
(r+1) = pr3 + (7. Pr
(1+1)
(0)
Pr.i
36

---

9i 11:11:11 + n1
< <3log T +
100
Σ D
mnst
mnst
e=t+1
S 3 <logg T + log T
3n0
+
2mn
(Fg. (W , x,) - F-g. w X.)
1=1+1 1 + eep
$ log T + 3
(Fgg. (will)
Mi , xx) + F-8: (with x:))
exp
2mm
(=++1
7 < 2 log T
3nd
exp
-Pg
(w/l)) yr
x:)
+
Kist
2mmss
16
t=f+1
where the second inequality follows from (10) and (8) and the last inequality follows from Lemma C.2.
For any t = + 1,,.., T and r' E X₁ by applying (S7) with iteration t. we have
( E
(w (1) me E:) = w (0)
Wir' E.)
+ P
(1)
Pinir
||5/| 1
2 Prii ast - -4 log T
2 3log T ast - 4,3 logT".
T".
Therefore, we have
Σ exp (-Pa: (W/ xx,x
< Σ exp
1 Σ
w (t)
Ba E:)
m
(=/+1
(=
E'E
(3 (3log T
4.at log I'*) |26
exp
m
[+1
(3log ast 4, log TT*) [2,
$ T exp
m
$ T exp(-logg)) log T*) 1,
where the last inequality follows from (6) and (9). Finally, we conclude
3g00d exp(Ka/16) I 4log
(r+1) Pro
- log T +
2
2mn
where the last inequality follows from (10).
(S2): We fix an arbitrary E (=1) and E [nat]. For any r E [m]] we have
mfat
M (M(+1) - -M!!7)
nl 1 2
Σ
Σ 3j
(T) - Σ of
1 {( (wo!7 14s) > 0]
=
2 Σ (10%0 /Ast
|
Aat)
g:
1 {{ (T) (w > 0]
[E(2]
2 2 (1
C / /ost - -C Mes 36 1 ( us) > 0]
nuh (7)
( (w uss > 0]
(12)
Ast
2 0,
37

---

where the first inequality follows from (S6) with iteration 5 and the third inequality follows from large choice of C...
T. we have ( (wir.. vs)
For any r E Ag. from (S2) at iteration O,...,T,
>
0. Hence, we have
m n||p||
(N(rt))
N N
Σ ).t²)
s.r
5,r
1E/2
/EC
JEFL
(1%
| Ast (T)
/Ast
[E[2]
2
C mv/ Aut
Cat "ot'mudss) (1)
nzdi (T)
(13)
Ast
0,
where the first inequality follows from (S6) with iteration 7 and the third inequality follows from the large choice of C.c.
Similarly, for any E B,, from (S2) with iteration O,...., we have (ws , us < O. Hence, have
mist
(N(T) N((+11)
Σ
Σ
7 2/| s,r
12
jECt!)
jEF()
Σ
(c_))
/Ast
[x()
Aust D6
[E(2]
2 (1 - Cgsl)
n//s Cat ne
Mes Aet g.
np (T)
Ast
0,
where the first inequality follows from (S6) with iteration v and the third inequality follows from large choice of Cat > O.
Let us prove the last part. For any E [m], if M < -Ost then we have ( (Wair 1u-)) .) 0. Hence,
(r)
M
M aist + Bat by Lemma A.3. Otherwise, M(T) > aat implies
mist
M(++1) 3,r
-M(7)
n||la||
=-Σ
Σ 93
Σ
g.-²) 1 (w077. v-_) )) ol
1E[2]
jECK)
EET!!!
5 Σ (1e/)) /
| Astt
((T) 1 ( ((
(7) 1. |l_ >0
[E(2)
< 2 - (1-Cz)) Repe Ca. madee
gi 1 [ (wo!77 > 0]
00,
where the first inequality follows from (S6) with iteration 7 and the last inequality follows from the large choice of Cue. Thus, (7+1) < (T) aa + B In addition,
mns..
( (T)
n 1
38

---

Σ
Σ 5 Σ
10 ues > 0
1E
jECK
1ET
(1/02 1e-o Ast - | / (ott) 0/:²) -1 ( (k-5) > 0]
|E|2]
2 (1
Ost
Cee
my/ Ae 133 1 {( (uu p--
|e >0 0
2Agt
where the first inequality follows from (S6) with iteration T. Therefore, we have
2 2 2Agtllaal? 2 -ast - Pst:
M 1)
where the last inequality follows from (10).
From Lemma A.3, for any r [m].
2n ||1
N
N(+))
S Olst.
m
Therefore, it suffices to show that N(T-1) N when N.7 Ost and N(7+1) > N(7) when
N < -lst. If (T()) ast. then we have
w 2,7 v-
(T)
(0 s.r, u-s) + N(7) O.
Hence, we have
[((++1] p,p
N(T7
77 | 2
=- Σ
Σ 9j
Σ
16(2]
jECl!
JEILL
Σ
(!))
A
Aat
v__
1E(2]
2 (1
Ozi -nddet
00
where the first inequality follows from (86) with iteration t and the last inequality follows from the large choice of Caa. Using the similar argument, we can also show that ( (x( when (T) (tst and we have desired conclusion.
s.
(S3): We fix arbitrary s E {+1] and E [nac]-
From (12) and (S2) at iteration 0, ..... T, we have
M ((+
Σ
M (T)
n 11ull
mug! Aut
MMal
mnat
rE[m]
rE(m)
n SNRR
(T) 115/112
n99
12 Must
n SNR 4
Σ
(r+1)
Σ
pl7
Pr.
12hat
re[m]
re[m]
39

---

where the second inequality follows from (8) and (9). Combining with (S3) at iteration 7, we have
n SNR
(r+1)
Mar ((+)
Pra
12hst
re(m]
rE[m)
For any r E [m], we have
mmgt
M
M
(++1)
M (T)
7 p0
(T)
Σ s
1 { (wol7
( Mbs ) > 0]
(T)
fj
1E[2]
5E
c(l)
Ast
/ Mose
0577) .1 ((027 s M4 0]
( (T)
14,
1E[2]
Ast
c(I)
7
1 ( (w(7) mo} 0]
Me
[E(2]
$ 2Ast (1 + +=+z) muds (T) 11 (( 1 H4s > 0]
S 3da (7) 1
(1o5 Msm
0)
where the first inequality follows from (S6) with iteration T. Hence, we have
Aam 11all
Σ M (r+1))
Σ
M
"ugi |,M
6.
mmng
rE[m]
rE[m]
6
n SNN, o( 1E
n&at
$ SNRR y
Σ
(7+1)
Σ
Pro rE(m)
rE[m]
where the second and third inequalities follow from (8) and (9), and (S7) with iteration T. Combining with (S3) iteration T, we have
Σ rE[m]
M (++1) S SARttH
Σ
Pr.
rE/m]
From (13) and (S2) at iteration O,..., T, we have
Σ N
(1(11)_
NO12 a.r
nog," 1Aal
2
mnst
2Ast
TEA,
rEA,
SNRR
(7) 12:
2
n9:
12
SNR
Σ
12\at
Pr.
rE(m]
rE(m)
where the second inequality follows from (8) and (9). Combining with (S3) iteration 7, we have
SNR 12X
Σ
(++1)
(++1)
Pri
8.
rE(m)
TEA.
For any r E As, we have
mmat n||p||2
(((+)))
N((T)
- Σ o5
4,r
s.r
IE [
/EC!!
JEFL!
40

---

Ast
c
9i
1E(2)
v 22 (1 +1+ Cst n
S N (7)
where the first inequality follows from (S6) and the third inequality follows from the large choice of Cst- Hence, have
n 1
Σ
Nl++1) 8.r
Σ
NoT)
(7) |A,1
mt
rEAx
rEA.
11E:11
n9:
Taat
Σ
(++1)
Σ
Pra
Pro
rE(m]
re(m]
where the second and third inequalities follow from (8) and (9). Combining with (S3) iteration we have
Σ
x(++1)
S SGAan
Σ
P
rEA,
rE[m]
Using similar argument, can also show that
SNR
P
(T+1)
I Σ
S GAat
Σ
Prs (T+1))
12Ast
rE/m]
rEB,
re(m)
(S4): We fix arbitrary E [nar]. From (S3) at iteration T + which we have already shown, we have
M 1
(++1) M
M (r-1)
m
s,r
m
8,7
rEM,
rE[m]
SNR? 4
(++1)
Prç
rEim]
< 24A M SNR
log T
Kst
64
where the first equality follows from (S2) iteration 0. 0.....7, T, the second inequality follows from (S1) and the last inequality follows from Condition 3.2. Similarly, we have
(++1)
SNR
(r+1) 24 log T <
Kigt
Prá
m
m
64
rEA.
rE(m]
and
N (1+1)
(7+1)
< 24R log <
Prá
64
TEB.
rE[m]
Therefore, for any E [+1), due to (6) and the above three inequalities, we have
((w()-)) Ma))
(wwltt)) vz))
1
Σ a ((w(rtt) -v. -v.)) -
Kig
32
PE(m)
rE[m]
rE(m)
(14)
Together with applying Lemma C.2 and we have
Jafat (w(rt)),x, x.) - 1 Σ
(++1)
Pris
ml
41

---

Fg: (Wibr) 9i
x
m Σ
Prç
F-g; 1;
(Wir) x:)
-Bs
rE[m]
Σ o
(
( ..i - -ri p(-++1)
Dur
+ Σ E o ((wg..n
250)
-Prs
-
+
Kst
16
re[m]
(2 rE(m)
Kst
(S5): We fix j E [nai] and we assumee Ere(ml
(T) Pr.
p:3
> 0. without loss of generality.
From the triangular inequality, (8), and (10), we have
(++1)
(T+1
P - p/7
Pro
m
m
mm]
TE [m)
(r+1) (7)
Pr.s P3:
(r-1)
Pr.
Pr.6
m
rE]m]
rE[m]
(T) 11::11 + 9."
5 11, 1|
mnst
mnst
misstt
Kat
2
Hence, we have 1
m Ere(m)
(r+1) (1+1)]
Pro
2
Also, if mo Ene(m]
Prie p/3 < z then we have
1
Pr.a - Pr.jj -Prs
(1+1)
(1+1)]
S m
Σ
Pr
(1) Pr.j]
+
Aist
S
Kis-
m
2
rE/m)
rE(m)
Otherwise, we have (14), we have
S Σ r[m]]
p17 - -P-7]
S Kutt Together with applying Lemma C.2 and
Disst ((() x.) Ú353 (W(r), (y(,),;))
(W()) X, F F'
4. (w(1)
-0:0 x.) - -Pis (w(())
(T) xx,) + F-os (w(z),
F2.
2 Fr (W)
X,
P's (w((7) (F) x,)
Kist
16
Σ o
w wiir E.) E - a (( (10
(T)
1 ->>1-->
σ ((1)))))))))
Kist
m rE(m)
m
[E re[m]
16
Kist 4
Pr.d
Pr..
rE[m)
Nigt
4
Therefore, we have
al 1 ++exp 0jfft (W(+) X;)
of7 1 exep (iisat (W(+), X.
- (w(r), +1
exp
exp (-ūjJal (w()),,)) +
exp (irtst (y(,,,X.) 05.5t (())),,))
42

---

exp -8yfa [x())x;)) +
0gfet ( + exp (Nis//4
exp
exp(His//16 +1
exp Ratt/ (66 exp(Kat/4) /4)
I exp (-)a/88)
where the second inequality follows from
- fat (w xx),
s FF
(w(r)
-B, X,)
Kst
16
and the last inequality follows from applying Therefore, we have
=(=*+1)
x(22 1) 2 2 with = exp(Mist 16).
z+1
1++1)
(++1)]
Σ
Pri
Pr.
rE(m]
7
(T) mll mllii111
mmst
0. 7l7ml ml| 1.11 -1)
5
|25] 11 11
maa
0 [2 ||E,11
17
(T)
|X]] ||
(exp(-Kis)) /8) 4. (1 + Ba//1) 1)
7
|2, ||ε, 11 (12exp(-KKa) Kst/8) - 1)
mmat
0,
where the third inequality is due to (6) and 1 + 2 S e- for any Z E IR. Hence, we have
1
Σ rE[m]
(1+1))
(T+1)]
P S Hist
Prs
Pr.
Pro
rE(m]
(S6): We fix arbitrary i,j E [Mai] and we assume Gifst (W(+1)) without loss of generality. By combining (S4) and (S5) at iteration shown, we have
X3 2 fafat (w(++),,x,) X,).
which we already have
V: Sat (w(r+1), x.) - (w(+)), x;)
(T+1) 165t1]
Prs
Pro
m
rE(m]
jrfat (W(T+1)), ..))
Σ (++1)
+ Wjfat (wlr+t),
- Σ
- ( rE[m]
rE[m]
< 2
Then, we have
9j (T+1)
+ exp (Bifat (W(++)),
9,
[r+1)
1
exp exp (ūyfar (W(++)),x,)
< exp jisa (wirtt), xX) - 8s (wirt)),xx)
< exp((2tit)
= dst-
43

---

(S7): We fix arbitrary i [ma]. From (S7) at iteration т, we have (w Therefore, we have
for any r E X.
(7+1)
Pr.
" mmst
g 1111
and
w
1++1)
E.)
(w
Berr E,)
(r)
(Ei, Es)
(1+1)
- -prh) (5) +
(r+1) - Pi(irs)
Pr.i
||š||1
jElmasMMat
11E:1
Σ
KE Eg>
jE(mae]M(i)
oft)
(E: Eイ>
(7) 11:11 1
Σ
mn
JE|m.
Di
|1
1T |1 Ast)
mt
where we use (S6) at iteration т, (8) for the second inequality, and (6) for the last inequality. Hence,
we have w ( E
O. Now we prove the second part. For any E Xr and r' E [m]] we have
(++1)
9. (T) 1E
σf 11 (r+1) Prr
Pri
Pr
Pro
migt
mm
where the second inequality is due to (S7) with iteration T. (S8): From (S7) at iteration we have
Σ
(T-1)
Σ
[g ||
Pri
Pr.
rE(m]
rE(m)
|2g
Σ
115.11
m rE(m)
mnst
1 + exp @iifet (W(t),
m
From (S4) at iteration t, 78) and (9), we have
1
(++
nood
1
Pra
8mngt
+ exp( exp
Ere(m) Pr:
rE(m]
re[m]
By applying Lemma A.5, the fact that + T+ is an increasing function for any c E 10,11,6 > and the comparison theorem, we have our conclusion.
C.2 Convergence of Training Loss
In this subsection, we prove that the training loss converges below E within - nde 10,)) All the arguments in this subsection are under Condition 3.1 and the event Est-
For any / E [0,T*), from the definition of Tt. we have
no
Ft < log
8mnss exp Kst/ / ++11
Combining the inequality above with the definition of Ii, we have
no
nond
exp(x1) 2 8mns exp(Rat/4)
t t+1 1 - exp(-xippp Kist 44) log
8mnn (xp((sst44) +1
44

---

nogdd
no
log
SmnMg exp((ist/44) t +1
St exp Fist/ /4)
no
+
16mm exp(
2
no
(15)
16m exp Kist /
where we use the inequality log 2/2 for any >> 1.
For any E [0, T*) and E [mst]. by applying (S4) and (S8), we have
G.f (W(t), X: 2
Hist
Σ
(c)
Prá
4
m
rE(ml
Kist
4
no
Rigt
2
log
4
16mm exp (ist (ist/41
no
log
16mn
Sxap(iit//2) (2)
nopa
2 log
16
where the third inequality follows from (15) and the fourth inequality follows from (6). Therefore, we have
(w()) S log 11 16
x S 16 t-1
Let
nopd
nowd
where the incquality follows from log(1 I 2 for 2 O. Ift 2 16 : mdadd opp then
we have Lut (W()) < s. Hence, by defining Ta - mm, d op= 21 we have the first conclusion.
C.3
Test Error
In this subsection, we prove the second part of our conclusion. All the arguments in this subsection under Condition 3.1 and the event Est-
Define (1), (2), and & as the signal vectors and the noise vector in the test data (X,9), xyy), respectively, We fix an arbitrary iteration i E T"). From the choice of iteration / and (15), for any E [mat]. we have
log (5 (c S log
napd 16 t
< log
16mm (xp((stt/))
na
1 <
Σ rE(m]
Pr.
(
(16)
C.3.1 Test Error Upper Bound
Ere(m) a ((w ((==)m=)) for any z E S. It plays
We define a function S + IR as l((z)))))))))())) =
crucial role when prove the upper bounds on error. We have
[[h(E)] m Ez......m
Σ o(z,)
1 E
|z
Op
Σ
Is
(c)
2m
22mm
p.r
re|m]
re/m]
rE/m]
1sw - 11)
where 2, ~ No. 0, 02
for each r E [m]]. Also, for any 21, 22 E S, we have
(M21)
-1(22)) <
Σ
(1000 ((
21)) - ((w")) 22 22))
mm)
45

---

2 (0)
-y.r yyr 21 - (wo y,r 222
<
rE/m]
1
[Is (t)
y,r, 21 (1))-(((ss) (Iss yirt 222)
m
rE/m]
Nsw (t)
|| - -221
-8.
rE/m]
Hence, is Em
-g.r I
(t)
Lipschitz.
The following lemma characterizes Ere(m [sw
(0) y.r
's which is related to key properties of h.
Lemma C.4. For any E {=1]. it holds that
2
1 (t) 3.r
$ 200 'd
p
ri
[m(m]
iE(mee]
rE|m
Proof of Lemma C.4. From triangular inequality and the event Est, for each r [m]] we have
1s
Σ (E(ma)
( =.1E:11
22ood +
Σ
sE(mLl
In addition, we have
2
Σ iE/mal]
Panii Ei1EE11 -2
Σ
Porrs) )
1| +
Σ
Psrral (5. (E. E| -11,,1
(0) (1)
sE|mai]
[JE(mal] (x
< 20 d Σ
+ n
pp
d-
Σ
Pairel Parril
VE :E|mxr]
s.je|mne] bØ$
2
I 200 2d
Σ
Pains)
2
+ Bat op 2d
Pa.ris
+
Perri
2
iE iE(mar]
[Je(mal (+)
2
< 40 201
(Pars)
&E *Eimat]
where the first incquality follows from (8) and the second inequality follows from AM-GM inequality, and the last inequality follows from (6). From the Cauchy-Schward Schwarz incquality, we have
1
Σ
Σ RE(mal
< 20
Σ
Σ iEEmal
( (Parrs)
[m]
rE(m]
< 2m og 1
Σ Σ
rE[m] sE[naa]
In addition, from (S1) with iteration t. we have
Σ Σ Σ
(penns
2
(1()) L
vE|mA:rEE(m)
iE Mat] rE(m)
iE i re [m] i==-s
8:=5
46

---

Σ
Pr.
(ast + 5 log T mmst.
re [ml
For any E [mst] such that 0t = S, we have
Σ
S
max rElm
p
S
16m
Σ p
re[m]
(e|m]
where the last inequality follows from (S7) and (9). Therefore, we have
2
Σ ΣΣ
Pantt
- 16m
Σ
Σ
Pr.
+ (ast + +535t log )
xE/nas] rE[m]
iE(nal
refm²
2
25m
Σ
Σ
Prá
!1)
VE(narl
re|m]
where the last inequality follows from (16) and (6). We conclude
Σ rE[m]
Hsw!i
2moodd + 100
(c) Prus
[m(mee]
[e(mm]
2
< 200 2200-1d -
(t) Pr.e rE[m]
*E(Nae]
where the second inequality follows from (16), (6), and (C3).
By Theorem 5.2.2 in Vershynin (2018), for any 2 > 0, it holds that
P(h(E) - B(h(E)) 2 2] < exp
where e is a universal constant and ||-IIr.ip denotes the best Lipschitz constant. Combining with
Lemma C.4, we have
cm2d
P(N(E) - ((M(E) 2 2] S exp
(1)) 222
(17)
400 Eie(ma))
(Ere(m)
Now, we characterize the test error. First, we consider the case (X,z) S. U Up. We have
yfst (!), x)
= Fy (t) x - F-y (W -yy x
1 Σ
1
1
Σ
Σ σ ((wott.))
+
m
[E(2] rE[m]
m
rE(m]
1 ΣΣ
1
Σ
rE(m]
47

---

Σ
( w
(0)
(
+ Σ a ((rf00 (ir Hwy)
ΣΣ a ((wD) 1(0)))
rE(m]
rE[ml
LE(2 re|m]
Σ o ((w ( y.r x)) + m
(t)
M 2(2ast + -ae)
m
rE(m]
rE(m]
= -h(E) +
M M.r
2(2ckst + Bst),
rElm
where the second inequality follows from (7) and (S2). From (S3), (S8), and (16), we have
m
1
M
v.
(1)
12>st
1
n4
SNR
It
rE[m]
2 1
12 ng SNRR log (e
4(2ast Bat):
where the last inequality follows from (6). Therefore, we have
yfftt (w()) xx) 2 -h(E) + 2m rEim]
Σ
M
y.r
and thus
P Usat (w(t), x) <
<0 (X,u)
E S. USb] SP h(E)
1
M (1)
2m
re[m]
From Lemma C.4, we have
Σ
MO D.r
E(h(E)]
2m
rE[m]
M
(t)
Op
(t) Usw
-g.r y0r
2m
22m
rE[m]
rE/m]
2
SRR 4
20
Σ
Σ
Pro
Prr
24 am
v 2mmd
sE(mal
rE(m]
sE[na]]
rE[m]
2
S
Pri
mnn
[E(mal]
rE(m)
where the last inequality follows from the condition narP |||||* 2 C204d and (C5).
From (17), we have
P
((E))
Σ
M
11)
P
h(E) - ([A(E))
>
M [[((E)]
27T
8.T
2m
TE|m]
rE[m]
$
71 SNR
< PP
h(E) - E[A(E))
Σ
Σ Pr
48 mn
iE(n..]
rc(mm]
cn ||+l|*
<exp
400
482 2 Rad
48

---

ngt (2pe + pb)) |1ea|1"
S exp
Czopp
with some constant C3 > 0.
Using a similar argument, we can prove the upper bound on test error for the case (X,9) E Sh. In this case, we have
yfst
( X
Fg
(
X
F-y (W())
-y3 x)
1
o (wwft b(l))
1
Σ σ ((w())
[2(2] mE
rE(m]
Σ
( 10 -yrre )
1
Σ σ (( 20 -))m)()))
m
m
1E[2] rE/m]
rE [m]]
Σ
(1)
rE(m]
1 Σ Σ
(( (2000) w10))
ΣΣ σ -y.n x(())
(00)))))0)))
m
m
1E/2)e//m
12(2) rE[m]
2
Σ
(t)
+
2
min
N-(1)
Σ
Nilt) v.r
2(2 + Bax))
U.r.
rE[m]
rEA,
rEB,
= -1((E) +
min
VOO pirr
Σ
(V(1) Mir
2(2
+ Bat))
rEAD
BEB,
where the first inequality follows from (7) and (S2).
From (S3), (S8), and (16), we have
Σ
(1 (1)
1
SNR, Zt
m TEA,
v.rt
m
v.r
12Aa
rEB,
1
no 16mm exp 44)
SNR,
log
12\
2 12hst
1
SNR, log (=
2 4 4(2ast + Bat)
(18)
where the last inequality follows from (6). Therefore, we have
1 Ufst (w()) x) -h(E) min
Mir:
m rEAD
rEB,
and thus
P Ufa (w(1), x) < (x, v) Sn SP h(E)
min
Σ
v(()
Σ
(i(1) yor
Uirt
rEA,
rEB
From Lemma C.4 and Condition 3.1, we have
min
(1)))
Σ
(1)
[[((EE]
v.r.
redy
rEB
(1())
(i()
Op
Σ
(t) (t)
m
min
Birr
B.r
2 rE[m]
-g.r
rEA, rEB,
49

---

1
SNR
Pri
3
Σ
Σ
Pr.
mns
V2rmn
d
Ve [mall re(m]
rE/m]
1
nl SNR
Σ
Σ
Prit
(t)
24
iE[na]] rE[m]
where the last inequality follows from the condition given in the statement. From (17), have
h(E) min
1 m
Σ
N Mirs
(9)
B.r
rEAd
rEBy
TP
h(E) B[((E))
1
min
N
Σ rEB,
No(1)
B(N(E))
m
rEA,
< P
(((E) B[((E)) >
1
SNR
Σ
Pri
(t)
24
se[ma] rE[m]
on ||/||
S exp
9. 24 24 ost
Matpl ||e||1 Osofed
S exp
with some constant C3 > O.
C.3.2 Test Error Lower Bound
= t Ere(m) o ((wf)1))
We consider the case (X,y) E Sh- Define : S + R as g(z)
1 Ergim] (w0),,²) for any S. Then, we have
yʃst (())) x)
(i(t) xx) FFyy (wr()) -yo x
Fy
1
Σ
((whth bill))
m Σ
1
((w(t)
m
() re|m]
rE[m]
1
Σ
Σ
(w
( Mori )00))
(1)
Σ o ( (w - 5))
m
m
1E(2) rE(m]
rE(m]
1 Σ
(1o
5))
1
Σ
(w0 (1)
1 ΣΣ ((15)).000)
<
rE(m)
re(m)
rE(m)
N
(e 8.r
< Sy((E) + max
20
V.P
rEA,
rEB,
T=(() 3rr
$ <gg(E) +
max
MiPr
m
rEAp
rEB
(1) B,rr
(1(1)
<g)(E) +
max m
(E(+1)
rEA.
rEB.
where the second inequality follows from (18). Therefore, we have
PP Ufat (w(0),x x) (X, v) Sn]
1
P
lo(E)
3 max
Σ
Σ N(O)
2
m sE{t1}
reA
rEB,
50

---

We define the set
Ω S: [g(x)l 2
3
max
No
m (E(+1}
rEA.
rEB,
We immediately obtain P [y/S<r (W())) x) (X, .) E Sn
2 P E 2 and thus we will character-
ize Piς E 52). Denote Ç = CopESNR
Σ
E. where Cs > 0 is some small constant. Then, we
m 1==1
have
||<|| S CEPESNR, iE (mal
15
Σ
Σ
(G
sE(mae] jE (M (R)
3(1 + oad
S COP6SNR
Po |
ozd
S 0.020pp P
(19)
where the first incquality follows from (8) and the last follows from the statement condition n | s Csape and the small choice of Co- Also, for any [ml], we have
1,r+ E + 5)) - a (wof..)) + t (( (10f2 -E+ - ()) o ((of))-E))
21 (w11 (1 5) > o] w w) 5) + 1 {( 10 -)) > 0] ( (10 c)
(wi,rr)) <)
(1)
(t) (É,
C
Σ
P
Σ
Σ
Pi.n
+
Σ
( E:)
||
iE(mal 8==1
se ==1
[
M=
2 C
Σ
(8) Prr
4.3r log T Clst
EE mm
B1=1
where the first inequality follows from the convexity of ReLU, and the second incquality follows from (S1), (7), and (8). In addition, for any E [mm] we have
1.r. 5 ++G) ++)) - a ((w=)...)) + (uu___.-++))) a (ww09 -s))
< 2
w 1,r1 5)
(É.. Eg
2
Σ Σ
P-nn
|1E
10 10) (.. s:>1
iE(ma] v==1
ve(ma] jE (x)
8.=1
8==1
2Cop (ne (Ost + 5.3st log T 4,3t log T + ast)
=NGo na (20st + 98.t log T*),
where the first inequality holds since ReLU is 1-Lipschitz and the second inequality follows from (SI), (7), and (8). Therefore, we have
g + <) - g(5) + + + <) - g(-E)
51

---

CoPASNRI
Σ
Pri
(1)
Deat (7rttt
12B3st log T
mal
8==1
COP
Prá
2m
kE [E[ns]]
fimm
c(I)
((1)
+ (())
CoR
(1) b,r
N
max
2m
.E
(
rEB,
NO 8,M
max sE(11)
8.
PEA.A
rEB,
where the second inequality follows from (16) and (6), the third inequality follows from (S3) and the last inequality follows from the choice of Co > 0 and
+ c 2 CT') nn + 2(1 CT+)mn = (1-
(pe + +pb)
c
c
Ratt
By the pigeonhole principle, it implies that at least one &, -, + 5. - + Ç belongs to Ω. Hence,
F|S E Ω + PI- E 2 + Plc + C St + P| E + Ç E Ω2 2 1.
Also, from symmetry, we have Pic E St] = Pi & = 22 and - following lemma allows us to relate the probability PI 22] to the probabilities IP - Ç E S2
M PP ( S2 The
Lemma C.5 (Direct from Proposition 2.1 Devroye et al. (2018)). For any v E S the total variation distance TV.,.) between (0,, A) and ((v, A, ) is smaller than [l].
20,"
By Lemma C.5 and (19), have
||||
IP|E E Ω] - P E Q C] TV (NNIO.CAA)..VEES..
S
< 0.01. 20
Therefore, we have
1 1 Plg E Q]
+ Pl- E ?] + Ple + Ç E 22] + - CE < 4TP & E Ω + 0.02
and thus PP E 22 2 0.24. We conclude that
(X. yfat (w(O) x)((x,)) E S. 2 0.12.
52

---

D Proof of Theorem 3.6
suffices to prove the following restatements of Theorem 3.6.
Theorem D.1 (Weak-to-Strong Training, Data-Abundant Regime). Let W be the iterates of the weak-to tookk-to-stee tooak-to-strong strong training, with the weak model fwi(w", satisfying the conclusion of Theorem 3.3. For any (0, 1) satisfying Condition 3.5, with probability at least 1- 6, there exists early stopping time Tes = (n mm(2. + Pb) |||||- such that the following statements hold:
The early stopped strong model fst (W(Tw), perfectly fits training data having correct label (i.e. Di = ût) but fails to training data with flipped label (i.e. dJ + Úi). In other words, the model predicts the true label ys for any training data point X,
Let (x,y) DD be an unseen test example, independent of the training set ((X; 9:) We have
P yfat (W x) <0 (X.)) U.S. S eexp
(-Maa(po Czo
Nest _Tst(2p. (2po + pb)) 1
and
(- M.saPP 12|l |211
P Ufsa (WiTO), x) <0 (x, E Eo,] S exp
-Gooad Goofed
Here, Cs > O is constant.
For the proof, we first analyze the early training dynamics and characterize the early stopping iteration (Appendix D.I). We then show that the early-stopped model perfectly fits the training data with true labels (Appendix D.2), and finally, we establish a bound on the test error (Appendix D.3).
D.1 Analyzing Early Phase
First, we establish upper bounds on the noise coefficients.
Lemma D.2. Under Condition 3.5 and the event Est, for any t E [0, E {#1), E [m] and
i E [n it holds that
3mo (w.... 21
3n0
Pa.ns
I
t,
S Ccst +
mm t.
Proof of Lemma D.2. We fix arbitrary {=1}, r E [m] and E [mat]. For any iteration t S T*, we have
3n0 d p 2mn
3n0 2mms
3110 p 1
7
Pa.r.
S.
mm,t
Ps.T.E
S ....
Ps.ra
1
2mn
where the first inequality is due to the triangular inequality and the others are due to (8). Therefore, we have
(E:, E,)
K un! s.
E. E. 5
(o (0)
(e) Parri
Σ
(e)
Parro
||5, ||2
jEinee]Me
3n0 cl
5 Osst.
1(1 + Bax))
2m1
3n0ed
S Oct
p- t
mill
where the second inequality follows from (7) and (8).
The following lemma can be inductively applied when characterize the early phase of learning dynamics.
Lemma D.3. Suppose the iteration T E [0,
miZ
satisfy the following:
1p dog T
53

---

1. 1 [rEmmm Mir m E Ergim M -1r < 2.
m
For each 8 E [+1], it holds that M M (wb...1 pt: > Oifr E M,, and M 6i = 0 ifr & &M..
(t)
(5) 3. For each {+1}, it holds that N 8.r ( W > 0fr E Ao and No. 855 (wor < <fif
r E B..
4. 1
Eme(m)
M -ir S Ere(m)
Mh S (mm) M
60
For each 8, E {+1}.
Pb |
Σ
M
(r)
Σ
(r)
Byy
Σ rEB.
N
(r)
or S
Σ
M
(r) 8'y
120 + pb) 1
rE(m)
rEA.
rE(m)
6. For any s {=1} and r E [m], it holds that M
N oir
S ast Bat.
Then under Condition 3.5 and the event Est, the following hold:
1. For any E {=1], it holds that M(++1) 2
MT s,r if E [m], N!T
2 No ifr E As, and
arr
s.r if E Ba. ((+1) <
2. For each E {+1}. it holds that M M (T+1) Whir .us) > Off E M. and M (r++1) 0 if
(
(7+1)
r $ M,
3. For each s E [+1}, it holds that N(Tt1) ( (z+1)) ,u)) > 0 of E A, and
M(++1) (wir
(7+1) .u) <Oifre B..
For each E {+1}.
M (7) s.r + (2pp. + Pb) ||
M Ml
(r+1)
Σ
80m
rE[m]
rE[m]
5. For each s E {+1}.
(1+))
Ph |01
mPh
| 1
m
8,r
m
160m
m
S,T
m
8.
160m
YEA.
tEA.
rEB
rEB.
(++1) M 11r
M (++)
(++1)
60
Ereim)
S Erejm
S
60 Ere(m)
M
-1r
7. For each s E {+1).
pb |12/2 2 120 + Pb) ||ll rE[m)
M(r+!)
<
Σ
(((+1)
Σ
(l(+1)
< M (T+1)
rEA,
rEB
rE(m]
8. For any s E {+1} and r E [m],
s.r
|N(+1)
< ast + BSt.
Proof of Lemma D.3. For any E [mat]. we have
j.fa. (W(r), X, Fy.
( 14
X,)
F-ge (W
(W(1), X,)
< Ps. (W(T), ; x.)
54

---

ΣΣ o
((
(
Σ o ((wf).)))))
+
re]m
rE]m]
For each i E [Maa] and 1 E [2], we have
w (r)
Si.r. 8. )
m
rE[m]
1
Σ
Be.rs
(0)
)
+
max
T s.r: 8.r
rE|m]
Σ
(0)
( + N. 2.r |
nn o
01.ro
max (E(1))
m
re|m]
(0)
)
o (MS?T) a (N!?T) a (-M!.?)
w 0
+ =E(=1}
max
m
rE/m]
1
(w!)) (0)
M (T) 1 Σ
N
N (T)
+ max
s.r
m
(=(+1)
m rE[m]
s.r! m TEA,
m
s.r
rE[m]
BEB
5 Ogt
+
2
Combining with Lemma D.2, for any i [mat], we have
ja (w(+), (T) x; < 2
1
3
Ost + 2
+ Ost
+
S 2,
log T
where the last inequality follows from (6) and thus we have
1 1
2 1 cxp((2)
2 9"
(20)
(irSa (W6), x.))
1
exp eexp
for any i E [nat]-
From Lemma A.3 and the event Est, for any & E {+1} and r E [m]] we obtain
M M(++1)
M
Σ g
Σ
||aal2 11 {( (1o ( o]
ait
mnst
(E[2]
c(t)
- |
Ileal1e- - 1 [( (w0,7..11) pba > 0]
[E(2]
27
1 -
Cz-1
n2 Cat m/4 |1am12 (20077 (1a) 0]
mfssst
nH |||u||2
1 {( (w(??
0]
5m
(2po + +ph)
|||||/ 1
(w(T) s.7 1e.)
> 0]
20m
20. 0.
Hence, i E Ma. we have
( (7+1) Hss) = (w(0) Hs. Us) ) + +M (T+1)
2 w (0 us) + +M (T) (T)
= (wo?)) ( us > 0
a.r
and i & Ms, we have M(r-!) sr = M1 9,r In addition, we have
=
M(++1)
Σ
M(t +
(2pre + pb)
||11|2 Σ (100 (2)) > o)
sr
20m
rE|m]
rE(m)
rE(m]
55

---

M +
n(2pe + Db)
|1e112
MMall
m rE(m)
20m
m
1
Σ
MD +
nm2pe + +pb
||a11?
80m
rE[m]
where the last inequality follows from (9). Similarly, for any E {+1 and r E A, we obtain
(r+1) 8,7 8,
(T)
Σ
Σ
Tltt) 11u1
9i
milst
(E(2)
iEcl!
$EF12
7
c!
|
11u11
mnst
[E(2]
2m
1
C--l
-np - Cra nx))
|1011
mist
9
17
The ||
5mnst
mPPo
||
40m
2 O.
Hence, if E As, we have
( (w((+t)) ,e.) - (s)
N2(+t1)
w (0)
us Us) + er
NoT)
( (wo (w0 ps) > 0.
In addition, we have
((1t))
1 Σ
((())
17bb
||// A4g
+
m
8.
40
rEA.
TEA.
1
17Pb
|||
160m
TEA.
We can obtain similar conclusions for Bg. Thus, we obtain the first five statements. For any 8 E {+1], we have
M
M
7.
(1222) + (2,o1) ||
rE[m]
rE(m]
2 (1 CTal) n7p |1ea13
M (7)
m
rE(m)
1
M(T)
(npo + pb)
||a1|2
4m
rE(m]
In addition, we have
1
Σ
((++1)
1
NO
T
((c22) + |c,0| 1) ||
m
orr
m rEA.
sir
mist
rEd.
2 (1 + CTa2) myn ||//1
Σ m TEA.
(T)
s,r
msst.
(+)
3mpb 8m
|012
m TEA.
s.r
56

---

Similarly, we have
1
Σ
((T
m Σ
1
N
(7)
7
(cc + cLe 1)
or
8,y
771
rEB,
TEB,
(1 + Czal) ) my ||/112
N (
m rEB,
8,
mmat
1
3pb7
||||2-
m
8m
rEB,
Using these, we have
Σ
M
Σ
M +
Σ
M
Σ
M
rE(m)
re[m)
rE|m]
rE(m)
Σ
M (7)
n(2p + pb)
|| ?
+
80
rEim]
M
1rr
(T)
+
60
1
M
(++1) 1r
Σ
M M
-1,
rE[m)
[rEmm]
re(mL
1
M -r
+
1
M
(T+)) 1,,
Σ
M 11,
60 rE[m]
60
[E(m]
re|m]
M
(++1)
60
-,,
rE[m]
By using symmetric arguments, we can obtain Ere(m) M(++1) < 60 Ere(m))
M (++1)
-1,
Similarly, for any 8, s, E {+1}, we have
N Σ x((+t))
Σ
No(T)
N N2(+2)
[((r s.r
sr +
STT
rEA.
rEA.
LrEAD
reA.
Nr(T)
3rppb
|
8,r +
8
rEA,
(T())
(2pp + pb)
s,r +
||
80
rEA,
M(())
st +
M
o
(++1)
M ofar
rE[m)
rE(m)
rE [m]
Σ
M M(T+1)
rE[m)
In addition, we have
Σ
8.
rEA.
= Σ NO
Σ
Σ
N(O) s,T
s.r
or
rEA,
LEAA Pb3]
rEA,
Σ N(T)
160
rEA,
57

---

Σ rEA.
Nolr
ph. |
3n(2po + pp)) |eal
s,r +
120(2pe + Pb) ||/1
4m
Pb ||
M (T)
s/rr
Pb ||2|
Σ
M
M
Σ
M M ol
120 + pb) || rE(m]
120 + +Pb pe
re/mm]
rE(m)
Ph ||211 120 + Pb) ||
M M
rE(m]
Now, we prove the last statement. For any E [m]] if M -ast, then we have (T) Hence,
(Wirr s pe_) < 0.
M(++1)
+ Ast by Lemma A.3. Otherwise, M > -Oss implies that mnsst
M
M(++1)
M
7 1
bir
=-
Σ
of
Σ
g)
1 (10,7 =0]
1E(2)
jEC
JEF
Σ
c()) -
(10057 (e_) > 0
[E(2)
00
where the first inequality follows from (20) and the last inequality follows from the event Est. Thus, M(++1) < M$ < Ost Bst. In addition, we have
mnst
M(+++) a
M
| ?
Σ
Σ
1
(w(
>0
1E(2
jECK
JE
Σ
c(l)
1l
(ww
(T)
14-88
[E[2]
-1
Therefore, have
2n 2n11
2011|pe11
M M
(+)
2 ast
2 -0st Bot
m
m
where the last inequality follows from (10). From Lemma A.3, for any r E [m].
2n| 1/12
N(++1)
((7) 3,
<
<
Osst.
m
Therefore, it suffices to show that ( 1) s,r
(T) s.r
when N(T) Ost and ( b,
((7) when
N(r) Clst. If ((r) ast. then have
(n (T) e,r,
=
( (0! N v_ + N(7)) > 0.
Hence, we have
mill
(x++1)
N((7)
y
58

---

Σ
Σ
12
jECK
JEFL
c(1
9
12|2]
(1
Cat
-2
ny
Cst
-y
00,
where the first inequality follows from (20) and the last inequality follows from the event Est. Using similar argument, we can also show that a.r (++1)) > N(7) when N -Ost and we have desired
conclusion.
Next, we characterize the early-phase learning dynamics of easy signals.
Lemma D.4.
Under Condition 3.5 and the event Est, there exists the smallest iteration Tes E
0,
200m
such that
M
(Tal
(Tee) 1,
max
1r
2
TE[m)
rE|m]
Proof of Lemma D.4. Suppose there is such iteration. We fix arbitrary s {+1}. Note that
foom I
from Condition 3.5, 7(2petru)la 1
mintt noādlogT* Thus, we can apply Lemma D.3 and for any
t 0. o2pp. ml
100m
we have
M
M M
(2pp + Pb)
||
m
m
80m
rE
re(m]
M 0))
n2ppe + Pb)
m
80m
rE[m]
(2po + ph))
||a1|/2 L.
80
By choosing
40m
0, 7(ppe+tu)
100m
we obtain contradiction. Therefore, there
7()p.+Pu)lle
||
exists an iteration E 0, 2oa
100m
such that
max
M Lr:
(1) M
-1r
2
1
m
rE(m]
rE(m)
We then define Tos the smallest such iteration.
We will show that iteration Tas obtained from Lemma D.4 our desired stopping time, By sequentially M(
applying Lemma D.3, for any {+1}, we have M (T..) 0 for all [m], (T.)) Of E As,
and N (Tes) 0 if B., Furthermore, we have
6.7
(T)) 1
(Ta) (T)) 8x
pb. |
2
(21)
m
120'
m
8r
240 2pp + pb)) ||
rElm) (m]
rEA,
rEB.
59

---

and for any E [m]) we have
M (T,) 5,r
((T 5.r
I Ost +
Bat.
(22)
Combining the upper bound on Tes and Lemma D.2 leads to the following bound: for any 8 {+1},r E [m], and i [mst].
(wo (2ae)) Ei S
3nood
100m
400ofd
Pank :
Ostt +
S
(23)
mistt
(2pp + Pb) ||
(2pe + pb ||
where the last inequality follows from (6).
D.2 Train Error
In this subsection, we prove the first conclusion conditioned on the event Est. For any i E [Mat], we have
Iitst
(W))))) x.)
1
W
(Tes)
Σ
Σ
w
(Tes) Disrr
m 1E(2] rE[m]
1E/2) rE/ml
+ m
1
Σ
1 Hiir
(Tes)
..:))
1 Σ @ (ww
(Ta)
Ei))
m
rE(m]
rE(m)
Σ
w
(Tee) -o(T)) 2- (ast + ast + Bot)
400g
(2pe + pb) po) ||aal
LE [2] rE[m]
2
Tex) M
(o(Taa (Ta) Best
No(Taal (Tes) Berr
400
2
m
min
Bur
2((2xst + )at))
(2po pb) ||
rE[m]
rE(m]
rEB
||2112
400g
Ph
2((cst + Bat)
p
120 + Pb) ||
(2pe + pb ||
>
where the first inequality follows from (22) and (23), the third inequality follows from (21), and the last inequality follows from (6) and Condition 3.5.
D.3
Test Error
In this subsection, we characterize the test error of the strong model. All arguments in this subsection are under the event Est. Define (11), (22), and & as the signal vectors and the noise vector in the test data (X, y), respectively.
We define a function S - R as h(z))())))))))) = Eremm o ( ((w (,r,,,,,))))))))))))
x)) for any z E S. It plays a
crucial role when we prove the upper bounds on error. We have
[[h(E)] = - -Ez,.... Zm
(Zz,)
=
2m
1
Ez
Zm
Σ |z,| rE|m]
22m
op
Σ
Uss
(Ta)) v.r
['[mm]
rE(m)
where 2, ~ ~ 00.03 T (Taa))
for each r E [m]] Also, for any 21, Zz E S, we have
(h(21) h((2211 5 m Σ o ((w (Ter)
vir: (a)/22)) 211) σ ((w (ine) v,r+ z2
rE(m)
Σ
(w
(mo) 21
(w (Tm) Z32
rE(m]
60

---

Σ
[gge (Tes)
- g,r, 21 - [I -I (Te)
y1r 22) 22)
re|m]
(Fas) Ig
|| E2| y.
m
rE]m]
Hence, h is 1 [re(m)
(Tar) g
Lipschitz.
M.r
The following lemma characterizes
Iig
(ex) yor
's which related to key properties of h.
Lemma D.5. For any E {+1}, it holds that
900mng
Σ re[m
M (Te)) s.r
(2pe + Pb )n ||ll
Proof of Lemma D.5. From Lemma A.3 and triangular inequality, we have
[ (Tan)
us 0)
Σ
S 2o0dd +
Σ :E/rea]]
(Ten) E:
+
sE|mul]
We have
Σ
(To))
E:IEE:1
Parn
Σ
(Taz)
2
||E:11
Σ
Pard Penn (E., 1- -115)
(Ta) (Ta)
Parris
EE [aa]
(Tem)
11E:11-2
Σ
(Te) P Sini Panrs
E 1 12
Parrii
VE [ad]
i.jfmmll $59
(Tee) PsTr.h
2
|1E:11-2
Σ
(Perci) + (p!t)s) ) (5. E |1 -11,
(Te) 2
VE [ma]]
(nac) 173
Ba)
||E:11 -2
sE(mme]
800g of
(2po pb)m ||/))
where the third inequality follows from (8) and the fourth inequality follows from (23) and (8). Therefore, we have
Σ | rE(m]
(T>) s
800ma,da
900ma
(2pe + pb)n ||a112 (2pe + pb)) m ||]]
where the last inequality follows from (C3).
By Theorem 5.2.2 in Vershynin (2018), for any 2 > 0, it holds that
cz2
P(((E) - B(M(E)) 2 2] S exp
03 1
61

---

where è is a universal constant and Ilpp denotes the best Lipschitz constant. Combining with
Lemma C.4, we have
c(2pe + Pb) 1bell 22
P(N(E) - B(N(E) 2 2] & exp
(24)
900
Now, we characterize the test error. First, we consider the case (X, y) E S. U Sb. We have
W (Texe), x)
= Fy W WW(Tio) xx - -Fyy (WiTTa) ,x)
1
(woffr)) ,00)))
1
Σ
(( ((1offa)) (offfa)) . .E)
m 12(2) rE(m)
m
rc(m]
σ (wDT y,r: b.rrb(1)))
1
Σ o
(w (Tx) E))
m
m
1E r(
rE(m]
( (Te)) D.r
1
Σ
1 -yrr E))
Σ
M
(Ta)
40st
m
rE[m]
m
rE[m]
m
re|m]
v.t
un (Tnd)
5))
+
40
m
120
rE(m]
2 -() + 200'
where the first inequality follows from (7) and (22). From (24) and Lemma D.5, we have
fat
(To))
X
<
0 (X. v) E S. U..]
1
h(E)) E[h(E)] 1
$
h(E)
P
E(((E))]
200
200
1
900grp
$
((E)) E[h(E))
200
(2pe + Pb pb) 111211
1
<
h(()) - [E((E)) >
250
Mai (2pe + pb))2 ||
exp
Cbozd
with some constant C3 > 0.
Using a similar argument, we can prove the upper bound on the test error for the case (X, 9) Sn. In this case, we have
yffe (w(Tos), xx)
Fg (ToT x)
-F-y -F-((1o (W .x)
1 Σ 0 (( (InSTa) (0())
m Σ
1
(T)) (To)) .5)
(E(2) rE[m)
rE/m]
(TT)
(Ta) 20)))
un
(Tew)
yir: 5))
-Mirs
m
m
[E[2) rE[m]
re[ml
(Ta) Wor .5)
1
Σ
w (To)) {))
2
rE[m]
rE(m]
+ min
((llnn) vor
Σ
Nillin) v.r
2( + Bax)
m
rEA,
rEB
62

---

1 Σ
(( ((w (no
(Tm) ))
min
Σ
N NoTe
Σ
N (TTTs)) vir
2( + Bat)
yir
m
re [m]
rEA,
rEB,
Pb ||
2 ((()) +
2(Eist + (st))
[20 + pb) ||
Pb ||21
2 (E( +
200 + pb) ||
where the first inequality follows from (7) and (22), the third inequality follows from (21), and the last inequality follows from (6) and Condition 3.5.
From (24) and Lemma D.5, we have
P yff
(Ta)) x) < 0 (x, y) Sb.
Ps ||
S P
h(E) 200(2pp + pb) |/ll
Pb ||2/| |
M() E(((E))
[(((E))
200 + pt) |1 3
pb ||
900g d'
((E) E(h(E)]
200(2pp + Pb)) ||,4|1
(2pe pb) ||
pb ||/|1
S P
h(E) - [(((E))
250 + Pb) || 2
Patpl |211 Coofe Co
< exp
with some constant Cg > 0.
63

---

NeurIPS Paper Checklist
1. Claims
Question:
Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
The abstract and introduction clearly state the main contributions of the paper, including limitations of prior works, brief description of the problem setting, and summary of our theoretical findings.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results be expected to generalize other settings.
is fine include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification:
We discussed the limitations our theoretical results in Section and Sec-
tion 6.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification. asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect the scope of the claims made, e.g., if the approach was only tested on a few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and prool's
Question: For each theoretical result, does the paper provide the full of assumptions and complete (and correct) proof?
64

---

Answer: [Yes]
Justification: We provide the list of regularity conditions in Section 2 and conditions for the regimes investigated in Section 3. In addition, we provide complete proof of our theoretical findings in the appendix.
Guidelines:
The answer NA means that the paper does include theoretical results. All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions the paper (regardless whether the code and data are provided or not)?
Answer: [Yes]
Justification:
We provide details for our main experimental results in Section 5.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, other means that appropriate to the research performed.
also be provided via detailed
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reprodueibility may be tricky in some cases, in which authors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path reproducing or verifying the results.
5. Open access to data and code
65

---

Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: We do not provide code in supplemental material. However, our results in synthetic data and MNIST data can be easily reproduced since we opened all details.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips. cc/
conooicylylll for more details.
While encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https: / /nips. http/uulicceeeeee wwwpc//gg/////eeeeeeeeeceeseeeee het////beebbieeee cerbbbmmsssoooooliiiioooo
for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing much information possible in supplemental material (appended to the paper) is recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Question:
Answer: [Yes]
Justification:
We provide all details for our main experimental results in Section 5.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can provided either with the code, appendix, or as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [No]
Justification: Our work is mainly theoretical, and the numerical experiments are designed to illustrate our theoretical analyses and aid reader comprehension. Therefore, we do not report measures of statistical significance for these illustrative results. Given the theoretical nature of our primary contributions, this omission does not detract from the paper's core findings.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by emror bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
66

---

The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not show in tables figures symmetric error bars that would yield results that are out range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
Justification:
We provide computer resource information in Section
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics https: : hwwrrps.....///
Answer: [Yes]
Justification: This paper does not violate the NeurIPS Code of Ethics in terms of data privacy, potential for misuse, other ethical issues.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (c.g.. there special consid- eration due to laws or regulations in their jurisdiction..
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: This work is primarily theoretical.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
67

---

If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), faimess considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: This paper focuses on theoretical analysis.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but encourage authors to take this into account and make best. faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [NA]
Justification: Our experiments synthetic data in our problem setting and MNIST, and therefore do not rely on existing assets.
Guidelines:
The answer NA means that the paper does existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset used and, possible, include a URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
68

---

If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com/dataseta has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided. If this information is available online, the authors encouraged to reach out the asset's s creators.
13. New assets
Question: Are assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: Our work does not release assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification: This research does not involve any human subjects or crowdsourcing.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Bthics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: This research does not involve any human subjects, Thus, IRB approval applicable.
Guidelines:
The answer NA means that the paper does involve crowdsourcing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
69

---

We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, formatting purposes and does not impact the core methodology. scientific rigorousness, or originality of the research, declaration is not required.
Question:
Answer: [NA]
Justification:
We used LLMs only for writing and editing.
Guidelines:
The answer NA means that the method development in this research does not involve LLMs as any important, original, or non-standard components.
Please refer to our LLM policy (https: //neur//s.....eee / for what should or should be described.
70


Reviews:
[{"review_id": "burPZc69or", "reviewer": "Reviewer_twxS", "summary": "This paper attempts to find a simple setting in which weak to strong generalization provably occurs.  Their weak learner is a linear network with 3 copied weights (what they call a linear CNN).  Their strong learner is a 1-hidden layer ReLU CNN in which the second layer weights are set to one and only the first layer weights learn.  The ReLU CNN has three types of hidden units in correspondence with three patches in the data. Their model of data is a very contrived data distribution consisting of 3 different patches (matched to both the architecture of the linear and one-hidden layer CNN) with a set of easy, and hard signals in each patch, or noise.  They ask if the weak learner learns on actual data first, then the strong learner learns on data generated by the weak learner, when will the strong learner outperform the weak learner? \n\nThe types of results they can prove relevant to this are:\n\n1) In a data scarce regime (not much data but above a threshold), the weak learner performs as well as expected, and the strong learner can perform better than the weak learner due to benign overfitting, in which it does not overfit to the mistakes of the weak learner. \n\n2) In a data abundant regime, the strong learner provably exhibits weak to strong generalization, if the strong learner's learning is stopped before an early stopping time.  If the strong learner learns for too long it could potentially overfit to the mistakes of the weak learner (though no theoretical guarantees are derived at the convergence point of strong learning.  But early stopping of the strong learner provably prevents this.\n\n3) They have simulations in which they train the strong learner for longer than the early stopping time and find performance degrades then plateaus. No theory is provided for this.", "questions": "What are the prospects of generalizing your theory methods to more general structures in data and lack of match to architectures?", "limitations": "Yes. But further discussion on the limitations of their data assumptions would be helpful.", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 2, "significance": 2, "originality": 2, "strengths_and_weaknesses": "Strengths:\n\n1) The paper provides a simple example in which weak to strong generalization is provable.\n2) Some simulations bear out the predictions of the theory, and also reveal other phenomena at late times in learning that are beyond the reach of this theory.\n\nWeakness\n\n1) A major weakness is the highly contrived nature of the data and its match to the architecture.  The data comes in 3 patches, and the architecture comes with hidden units (or linear units) with receptive fields matched exactly to one of the three patches.  What goes into each patch has a strange combinatorial nature out of a finite set of objects (fixed orthogonal vectors).  Only first layer weights learn; second layer weights are fixed.  This strong match between data and architecture is unrealistic.  It seems that the analysis is tied to this match.  It is less clear what one can conclude about how the structure of realistic data impacts weak to strong generalization, and what is going on when there is not such contrived match, or such a toy dataset.  It is unclear how their derivations could be generalized. \n2) Less of a concern but an area for improvement in exposition: the authors need 6 conditions C1-C6 in section 3.  Some of them are well explained intuitively whereas others are not.  More discussion of these conditions and their roles would help.", "was_revised": true, "final_justification": "While the setting in which the theorems are proved are quite simple, the phenomenon of weak to strong generalization is interesting enough that having a simple setting in which it provably occurs may be valuable, and the intuitions provided in the rebuttal as to what we can learn in general from this simple setting are helpful.", "rebuttal": "We would like to express our gratitude for your valuable comments. In the following, we address the points raised by the reviewer.\n\n## **W1, Q. Extensions and Practical Insights Based on Our Theory**\nWe agree with the reviewer that our theoretical framework may look overly simplified compared to realistic settings. As described in lines 82–90, our work builds on the recent line of research in feature learning theory, where the adopted settings allow for mathematically tractable analysis of learning dynamics. While our setting may appear simplified, similar assumptions have been widely used to gain theoretical understandings on various phenomena—such as how model ensembling improves generalization [1], how benign overfitting arises [2,3], how different optimizers affect generalization [4–6], how architectural choices influence generalization [7,8], and how data augmentation contributes to generalization [9–11].\n\nHere, we provide a more high-level explanation of the intuition behind the analysis presented in Section 4. A weak model may sometimes exhibit low performance because it fails to learn certain hard-to-learn information (referred to as hard signals in our setting). Now, consider training a strong model—strong enough to capture the hard-to-learn information that the weak model fails to learn—under the supervision of the weak model. The strong model can only learn useful information from correctly pseudo-labeled data.\n\nOur key intuition behind how the strong model can outperform the weak model is as follows: there exists a subset of data that contains hard-to-learn information but is still labeled correctly due to the presence of easy-to-learn information (easy signals in our setting). This subset of data (termed both-signal data) provides gradient updates that enable the strong model to learn the hard-to-learn information. \n\nOur theoretical framework may seem simple at first glance, but analyzing its training dynamics is technically involved and the fomal proof spans 50 pages in the supplementary material. Also, the intuition from this setting can help us understand more general scenarios. One such example is early stopping, an often adopted practical choice for weak-to-strong generalization. The discussion in lines 313–322 explains the role of this strategy.\n\nRegarding our three-patch data setting, while it could in principle be extended to incorporate more patches, we deliberately choose the minimal number (three) that is sufficient to capture all essential types of signal and noise vectors defined in our framework, in order to maintain mathematical simplicity. In addition, we would like to note that our analysis can be potentially extended to more general architectures—for example, by adopting a simple CNN as the weak model and a simple ViT as the strong model, whose learning dynamics and benign overfitting have been studied in [3] and [8]. However, we believe that our simplified setting is more effective for delivering clear insights. For more details, you can check our response to Reviewer bMLu‘s Q1.  \n\nWe additionally conducted experiments on a simplified real-world dataset to support our findings. Specifically, we slightly modified the MNIST dataset to highlight the roles of key components such as signal and noise. The results demonstrate that our theoretical insights also hold beyond our settings. Detailed experimental settings and results are provided in our responses to Reviewer ABZC’s W1 and Q2.\n## **W2. Further Explanation on Condition 3.1**\nWe would like to provide further explanation of Condition 3.1. These types of conditions are widely adopted in feature learning theory literature that we have discussed above. In (C1) and (C2), we assume a sufficiently large dimension and large sample sizes. These assumptions allow us to apply concentration inequalities to quantities such as norms and correlations involving Gaussian noise, as well as the number of each type of data.\n\nIn (C3) and (C4), we assume a sufficiently small initialization scale and learning rate. These assumptions ensure that the effect of initialization can be neglected compared to the gradient descent updates, and that each update step remains small, which enables stable training dynamics.\n\nLastly, we provide explanations for (C5) and (C6) in lines 189–192 of the draft, and we would like to further clarify that the motivation behind (C5) is that the difficulty of learning a signal is determined by its frequency and strength.\n\nWe will discuss these points more clearly in the next revision.\n\n---\n\nThanks for your time and consideration. We are happy to discuss further if anything remains unclear.\n\nBest regards,\n\nAuthors\n\n---\n\n**References**\n\n[1] Allen-Zhu & Li. Toward Understanding Ensemble, Knowledge Distillation and Self-Distillation in Deep Learning. ICLR 2023\n\n[2] Cao et al. Benign Overfitting in Two-layer Convolutional Neural Networks. NeurIPS 2022\n\n[3] Kou et al. Benign Overfitting in Two-layer ReLU Convolutional Neural Networks. ICML 2023\n\n[4] Zou et al. Understanding the Generalization of Adam in Learning Neural Networks with Proper Regularization. ICLR 2023\n\n[5] Jelassi et al. Towards Understanding How Momentum Improves Generalization in Deep Learning. ICML 2022\n\n[6] Chen et al. Why Does Sharpness-Aware Minimization Generalize Better than SGD. NeurIPS 2023\n\n[7] Huang et al. Quantifying the Optimization and Generalization Advantages of Graph Neural Networks Over Multilayer Perceptrons. AISTATS 2025\n\n[8] Jiang et al. Unveil Benign Overfitting for Transformer in Vision: Training Dynamics, Convergence, and Generalization. NeurIPS 2024\n\n[9] Shen et al. Data Augmentation as Feature Manipulation. ICML 2022\n\n[10] Zou et al. The Benefit of Mixup for Feature Learning. ICML 2023\n\n[11] Oh & Yun. Provable Benefit of Cutout and CutMix for Feature Learning. NeurIPS 2024"}, {"review_id": "FKJpCnY4GQ", "reviewer": "Reviewer_ABZC", "summary": "This paper studies weak-to-strong generalization, a phenomenon where a strong model trained with the supervision from a weaker model outperforms the weaker one. This work focuses on the theoretical analysis to interpret the model behavior in weak-to-strong generalization with a linear CNN as a weak model and a two-layer ReLU CNN as a strong model. Depending on the amount of data, this work provides rigorous explanations for the performance in weak-to-strong generalization. Specifically, when the data is scarce, the generalization can occur via benign overfitting, or fail due to harmful overfitting; when the data is abundant, the generalization occurs at the early stage of model training and diminishes as the training progresses.", "questions": "1. Some empirical insights might be helpful, such as identifying key aspects of real data that trigger benign or harmful overfitting in the data-scarce regime. For example, does a smaller dimension for data $d$, a larger proportion of mixed data $p_b$, or a larger number of samples for strong models $n_{st}$, tend to trigger benign overfitting more easily?\n\n2. Is it possible to include experiments with simple real data? What would be the challenges or limitations in validating the theoretical results in real data?\n\n3. As the weak-to-strong generalization refers to the stronger model outperforming the weaker model, is it needed to compare the performance of weaker and stronger models in the theoretical analysis in Theorem 3.4? It doesn't seem to be an obvious comparison in terms of the test errors.\n\n4. How are the conditions 3.1 obtained, and how do they ensure the training properties as discussed in lines 187-192?", "limitations": "The authors didn't mention the limitations or potential negative societal impact of their work in the main paper. Discussing the possible scope of applying the modeling or constraint to real data might be helpful.", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n\n1. This paper is well-written and clearly organized. The writing is concise and effective in conveying the claims. Overall, it's of high quality in terms of clarity.\n\n2. This work provides a theoretical and detailed analysis of the weak-to-strong generalization, specifically from the aspects of gradient descent with linear/nonlinear models, which has the potential to inspire such modeling or further research in the community.\n\nWeaknesses:\n\n1. This paper mainly focuses on the theoretical analysis, and the experiments are limited to synthetic data modeled similarly in the setup. It would be better to include more empirical insights or experiments with simple real data.\n\n2. It would be better for this paper if more discussions on the empirical insights could be added, such as identifying key aspects of data that we can adjust or change in real data to make weak-to-strong generalization occur.", "was_revised": true, "final_justification": "My major concern is that this work mainly presents theoretical insights without much empirical validation. The rebuttal of the authors showed the results on synthetic datasets and explained the challenges of empirical experiments, which addressed my concerns, and I would like to keep my positive rating.", "rebuttal": "Thank you for your valuable comments. In the following, we address the points raised by the reviewer.\n## **W1, W2. High-level Intuition from Our Analysis**\nWe would like to restate the intuition behind our analysis presented in Section 4 at a higher level and emphasize that these insights can be extended to more general scenarios.\n\nA weak model may sometimes perform poorly because it fails to capture certain difficult-to-learn features, which we refer to as hard signals in our setting. Now, imagine training a strong model—capable of learning these hard signals that the weak model misses—using supervision from the weak model. The strong model can only acquire meaningful information from data points that are correctly pseudo-labeled by the weak model.\n\nOur main intuition for why the strong model can outperform the weak model is that there exists a subset of data containing these hard signals but that is still labeled correctly thanks to the presence of easier-to-learn features (or easy signals) that the weak model has successfully learned. This subset, which we call both-signal data, provides the necessary gradient information to help the strong model learn the hard signals. While our framework is simple, we believe the insights gained here can be applied to understand broader scenarios.\n\nBased on the intuition that using more both-signal data is crucial for weak-to-strong generalization, we believe that data selection techniques, such as uncertainty-based methods, can be designed to preferentially select such both-signal data. This is because both-signal data may exhibit higher uncertainty due to the weak model’s inability to fully capture the hard signals. We leave empirical investigations of this approach for future work.\n\n## **Q1. Key Factors Triggering the Transition from Harmful to Benign Overfitting**\nYou're almost right. In fact, noise level matters more than $d$ in general settings. More precisely, the transition from harmful to benign overfitting in weak-to-strong training is mainly governed by the number of both-signal samples, which depends on both the proportion of mixed data $p_b$ and the number of strong model training samples $n_{st}$. Additionally, the noise level in the dataset—controlled by $\\sigma_p$ and dimension $d$ in our setting—also plays a key role. This is because only the both-signal data contributes to learning the hard signals, and a higher noise level requires more such data to avoid harmful overfitting.\n\n## **W1, Q2. Experiments of Real-World Data**\nWe additionally conducted experiments on simple real-world data to support our findings. Since it is hard to clearly delineate signal vs noise in real data, we modified the MNIST dataset to emphasize their roles.\n\nFirst, we multiply each pixel in the original images of digits 4, 5, 6, 7, 8, and 9 by 0.02, while keeping the images of other digits unchanged. This corresponds to the presence of hard signals, with digits 4–9 serving as the hard signals. To emphasize the role of noise, we replace the border region of each 28×28 image—a 5-pixel-wide frame along the edges—with standard Gaussian noise. This results in images where the central 18×18 region contains the digit, surrounded by Gaussian noise. Finally, we randomly concatenate two such modified images that share the same parity (i.e., both even or both odd), producing 28×56 images. We assign binary labels based on their parity.\n\nThe resulting data includes a variety of signal types: some pairs contain two bright digits, others contain one bright and one dark digit, and some consist of two dark digits. These types serve as easy-only data, both-signal data, hard-only data in our setting.\n\nUsing this modified real-world dataset, we investigate the weak-to-strong training scenario beyond our theoretical settings. For the weak model, we use an MLP consisting of a single hidden layer with 128 units followed by a ReLU activation. For the strong model, we use a CNN with three convolutional layers of increasing channels (64, 128, 256), each followed by batch normalization, ReLU activation, and max pooling. The extracted features are then flattened and passed through a fully connected layer with 512 units.\n\nWe first trained the weak model using 500 samples. Then, we trained the strong model using labels predicted by the trained weak model, with varying numbers of training samples $n_{st} = 500, 1000, 1500, 2000, 2500$. We used the Adam optimizer with default parameters and trained each model for 300 epochs. Each experiment was repeated five times for every $n_{st}$, and we report the mean and standard deviation of the test accuracy for both the weak model and the resulting weak-to-strong model.\n\n| $n_{st}$ | weak test acc  | weak-to-strong test acc | \n|:---:|:---:|:---:| \n| 500 |  0.8606 ± 0.0045 | 0.8462  ± 0.0395 |\n| 1000 |  0.8593 ± 0.0013 | 0.8834 ± 0.0128 | \n| 1500 |   0.8642 ± 0.0150  | 0.8846 ± 0.0285  | \n| 2000 |  0.8669 ± 0.0052 | 0.8744 ± 0.0273 | \n| 2500 |  0.8586 ± 0.0139  | 0.8655 ± 0.0122 | \n\nWe observe a trend in which the weak-to-strong gain increases with $n_{st}$ and then decreases. These observations are consistent with our theoretical findings, which describe a transition from harmful overfitting to benign overfitting, and eventually to the data-abundant regime.\n\n## **Q3. Comparison of Test Error Between Weak Model Training and Weak-to-Strong Training**\nHere, we provide a comparison between the test errors presented in Theorem 3.4 and that of the weak model. In the benign overfitting case, our theoretical bound includes exponentially decreasing terms in the proportions of all three types of data—$p_e, p_b,$ and $p_h$. This implies that the model achieves low test error across all data types. Since we have shown in Proposition 2.1 that the weak model fails on hard-only data, this result demonstrates that the weak-to-strong model improves upon the weak model by a test error gap of $p_h/2 + o(1)$ via benign overfitting.\n\nIn the harmful overfitting case, the test error is lower bounded by $0.12p_h$, which implies that the gap between the test errors of the weak and weak-to-strong models is upper bounded by a constant multiple (less than $1/2$) of $p_h$.\n\nWe will clarify this comparison more explicitly in the next revision to avoid any potential confusion.\n\n## **Q4. Regarding the Role of Condition 3.1**\nWe provide additional clarification regarding Condition 3.1, which reflects standard assumptions commonly adopted in the feature learning theory literature (e.g., [1], [2]).\nConditions (C1) and (C2) allow us to apply concentration inequalities to key quantities such as norms and correlations involving Gaussian noise, as well as to accurately track the relative proportions of different types of data. These assumptions are essential for analyzing training dynamics—for example, by enabling control over inner products between filters and Gaussian noise vectors.\nConditions (C3) and (C4) assume a sufficiently small initialization scale and learning rate. This ensures that the influence of initialization is dominated by gradient descent updates, and that each step remains moderate, leading to stable training behavior.\nWe would like to reiterate that Condition (C5) is motivated by the intuition that the learnability of a signal depends on both its frequency and strength. The lower bound on p_b imposed by Condition (C6) is also essential for weak-to-strong generalization, as both-signal data play a central role in our analysis.\n\n## **Limitations**\nThank you for your suggestions. We plan to discuss our limitations more explicitly in the next revision.\n\n---\n\nThank you very much for your time and consideration. Please let us know if anything remains unclear.\n\nBest regards,\n\nAuthors\n\n---\n\n**References**\n\n[1] Cao et al. Benign Overfitting in Two-layer Convolutional Neural Networks. NeurIPS 2022\n\n[2] Kou et al. Benign Overfitting in Two-layer ReLu Convolutional Neural Networks. ICML 2023"}, {"review_id": "hpFV9XEjWO", "reviewer": "Reviewer_bMLu", "summary": "This paper provides a theoretical and empirical analysis of weak-to-strong generalization, where a stronger model trained under supervision from a weaker model can outperform the teacher. This work fills a gap by analyzing a special setting: weak-to-strong training from a linear CNN to a two-layer ReLU CNN on patch data.", "questions": "1. Why does the data distribution assign only the positive direction $\\mu_y$ for easy signals, while it allows both $\\pm\\nu_y$ directions for hard signals? In Definition 1, the easy signals are always set to $\\mu_y$, whereas the hard signals are drawn uniformly from all sign combinations $\\pm\\nu_y$. This introduces a structural asymmetry. I understand that this may be designed to ensure the weak model can reliably learn easy signals while remaining ineffective on hard signals, but I would appreciate clarification on whether this choice is essential to the theoretical guarantees, or whether the same qualitative conclusions would hold under a more symmetric signal setup (e.g., also randomizing the sign of $\\mu_y$).\n2. How sensitive is the theory to the assumption that the weak model labels are not adversarial, especially in the data-abundant regime? Can small adversarial label flips cause failure of weak-to-strong generalization?", "limitations": "While the paper presents a rigorous analysis, its setting is highly stylized and somewhat artificial. The data distribution is carefully engineered to contain label-aligned \"easy\" and \"hard\" signals with hand-picked orthogonality, which may not reflect the structure or complexity of real-world data. As a result, it is unclear how broadly the insights or guarantees would transfer to practical scenarios, such as vision or NLP tasks. Moreover, much of the technical analysis builds directly on tools and mechanisms developed in prior work on benign overfitting and feature learning (e.g., Cao et al. 2022; Kou et al. 2023), such as signal-noise decompositions and patch-wise convolutional structure. While the application to weak-to-strong generalization is interesting, the paper feels more like a thoughtful reuse of existing techniques in a contrived setting tailored to fit them, rather than a technically novel contribution in its own right. A more ambitious advance would involve analyzing weak-to-strong generalization in less restrictive or more realistic settings.", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n1. The paper provides a detailed and mathematically sound characterization of weak-to-strong generalization in both data-scarce and data-abundant regimes, including tight bounds and transition conditions between benign and harmful overfitting.\n\nWeaknesses:\n1. The data distribution is highly engineered, with orthogonal easy/hard signal vectors and shuffled patch structures. While analytically convenient, it lacks realism and limits the applicability of the results to real-world tasks.\n2. Much of the analytical machinery (e.g., signal-noise decomposition, patch-wise CNN analysis, benign overfitting dynamics) closely follows prior work. The contribution lies more in adapting known tools to a new but contrived setup, rather than developing fundamentally new techniques.\n3. All experiments are conducted on synthetic data tailored to the theoretical setup. Even simple real-data tests (e.g., CIFAR with weak supervision) would help assess whether the observed phenomena persist beyond the toy model.", "was_revised": true, "final_justification": "This paper offers a clean and technically solid analysis of weak-to-strong generalization in a synthetic setting. While its scope is narrow and some assumptions are idealized, the corrected proof and added insights meaningfully contribute to the theoretical understanding of the phenomenon. I recommend a weak accept based on its rigor, the technical fix to prior work, and the relevance of the topic to current interest in model distillation and student-teacher dynamics.", "rebuttal": "We would like to express our appreciation for your valuable comments. In the following, we address the points raised by the reviewer.\n\n## **W1, L1. Our Simple Problem Settings**\nWe acknowledge that our problem setting is simplified to enable rigorous theoretical analysis. In particular, assumptions such as the orthogonality of signal vectors allow us to make the learning dynamics mathematically tractable. However, similar simplifications are commonly employed in the recent feature learning theory literature. These line of works utilize similar settings to gain theoretical understandings on various phenomena—such as how model ensembling improves generalization [1], how benign overfitting arises [2,3], how different optimizers affect generalization [4–6], how architectural choices influence generalization [7,8], and how data augmentation contributes to generalization [9–11]. \n\nWhile our assumptions may not hold in practical settings, we believe that they still offer valuable insights into the mechanisms behind weak-to-strong generalization. We would like to offer a more intuitive, high-level explanation for our insights presented in Section 4. A weak model may fail to generalize well because it cannot learn certain types of information that are difficult to capture, what we refer to as hard signals. Now consider training a stronger model—one that is strong enough to learn these hard signals—under the supervision of the weak model. In this setting, the strong model learns from pseudo-labeled data, and its success depends on how often the weak model assigns correct labels.\n\nThe key idea is this: there exists a subset of training data that contains both easy and hard signals. Thanks to the easy signals, the weak model is likely to label these examples correctly, even though it cannot learn the hard signals on its own. These correctly labeled examples—what we call both-signal data—provide useful gradient updates that guide the strong model to learn the hard signals. Although the framework we propose is simple, we believe it captures essential intuition that can be extended to more general settings. Also, in our response to W3 (see below), we have empirically shown that our insights can be applied to real-world data.\n\n## **W3. Experiments on Real World Data**\nWe additionally conducted experiments on a simplified real-world dataset to support our findings. Specifically, we slightly modified the MNIST dataset to highlight the roles of key components such as signal and noise. The results demonstrate that our theoretical insights also hold beyond our settings. Detailed experimental settings and results are provided in our responses to Reviewer ABZC’s W1 and Q2.\n\n## **W2, L2. Novel Contributions**\nEven though we use techniques from [3], we would like to highlight some key differences between [3] and our work.\n\n* While [3] considers a single type of signal for each class, our setting involves two different types of signals per class. Moreover, the label flipping probability in [3] is independent of the input, whereas in our setting, it depends on the input because it is introduced by a pretrained weak model. These differences require more careful analysis in our proofs.\n\n* While working on this paper, we also identified technical issues in [3]. Specifically, [3] often uses the sum of activations as the model output, whereas the correct formulation should use the average of activations. To correct this, in our Lemma C.3 (S7), we show that the filter whose initialization has a positive inner product with the noise tends to have a noise coefficient close to the maximum among all filters. This is an analysis not previously presented in [3].\n\n* Condition 4.1 in [3] considers a regime where noise learning dominates signal learning, which corresponds to the data-scarce regime in our work. However, we additionally consider the data-abundant regime and reveal that a different behavior emerges in this setting.\n\nMoreover, we would like to emphasize that our work not only advances techniques from the feature learning literature, but also addresses several limitations of prior theoretical studies on weak-to-strong generalization by incorporating the following elements: consideration of gradient-based training dynamics, a more natural definition of weak and strong models, analysis based on finite samples rather than population loss, and identification of distinct data regimes. We provide further discussion on these points in our response to Reviewer yKoW’s Q3.\n\n## **Q1. Choice of Asymmetric Signals**\nYour understanding is correct. Our asymmetric choice of signal directions is intended to highlight the fundamental gap between the weak and strong models. We can also consider a symmetric case where both easy and hard signals involve no sign flips. However, in such a setting, we believe that a linear CNN and a ReLU CNN would require asymptotically the same sample complexity for generalization. As a result, it would be difficult to argue that the two models have different capabilities. In such cases, we believe that changing the architectures of the weak and strong models can lead to similar conclusions. For example, one could adopt a simple CNN as the weak model and a simple ViT as the strong model, whose learning dynamics and benign overfitting behaviors have been studied in [2] and [8]. As noted in [8], a simple ViT has a superior ability to learn signals compared to a simple CNN. Therefore, if we consider a regime where easy signals are learnable by both architectures while hard signals lie in the gap between the two, our theoretical insights discussed above may still apply.\n\nHowever, we believe that our current simplified setting is more effective in delivering clear and interpretable insights.\n\n## **Q2. Assumption on Supervising Weak Model**\nWe believe there may be a misunderstanding regarding our assumption about supervising the weak model. We do not assume that the weak model's labels are non-adversarial; we only assume that the supervising weak model satisfies certain error bounds. We would like to note that our results also extend to supervisors that assign labels adversarially, as long as they remain within the assumed error budget, since the only requirement is that the weak model satisfies the specified error bounds.\n\n---\n\nThanks for your time and consideration. Let us know if you have remaining questions; we are happy to discuss more.\n\nBest regards,\n\nAuthors\n\n---\n\n**References**\n\n[1] Allen-Zhu & Li. Toward Understanding Ensemble, Knowledge Distillation and Self-Distillation in Deep Learning. ICLR 2023\n\n[2] Cao et al. Benign Overfitting in Two-layer Convolutional Neural Networks. NeurIPS 2022\n\n[3] Kou et al. Benign Overfitting in Two-layer ReLU Convolutional Neural Networks. ICML 2023\n\n[4] Zou et al. Understanding the Generalization of Adam in Learning Neural Networks with Proper Regularization. ICLR 2023\n\n[5] Jelassi et al. Towards Understanding How Momentum Improves Generalization in Deep Learning. ICML 2022\n\n[6] Chen et al. Why Does Sharpness-Aware Minimization Generalize Better than SGD. NeurIPS 2023\n\n[7] Huang et al. Quantifying the Optimization and Generalization Advantages of Graph Neural Networks Over Multilayer Perceptrons. AISTATS 2025\n\n[8] Jiang et al. Unveil Benign Overfitting for Transformer in Vision: Training Dynamics, Convergence, and Generalization. NeurIPS 2024\n\n[9] Shen et al. Data Augmentation as Feature Manipulation. ICML 2022\n\n[10] Zou et al. The Benefit of Mixup for Feature Learning. ICML 2023\n\n[11] Oh & Yun. Provable Benefit of Cutout and CutMix for Feature Learning. NeurIPS 2024"}, {"review_id": "2mxSGPuaP2", "reviewer": "Reviewer_YK97", "summary": "This paper provides a theoretical analysis for weak-to-strong generalization in binary classification based on special structured data consisting of signal and noise patches (a variation of the multi-view dataset introduced in Allen-Zhu and Li (2020)). The authors take a linear CNN as the weak model and a two-layer ReLU CNN as the strong model. The main theoretical findings are the following:\n* A separation result on the generalization of the weak and strong models on the special binary classification task, showing that there exists some parametrization of the strong model that achieves zero test error, whereas the weak model cannot achieve zero test error.\n* A generalization bound for the supervised training of the weak model with gradient descent, providing a sample complexity of $n_{wk} \\gtrsim \\frac{\\sigma_p^2 d}{(2 p_e + p_b)^2 \\|\\mu\\|^4}$ for the weak model to achieve a close-to-optimal test error on the binary classification task, where $\\sigma_p^2$ is the variance of the noise patches, $p_e$ and $p_b$ are the probabilities of the easy-only and mixture of easy and hard patches, $d$ is the feature dimension, and $\\mu$ is the easy feature norm.\n* A phase transition analysis for weak-to-strong generalization with respect to the weak-to-strong training sample size $n_{st}$ in the \"data-scarce regime\", showing that when the strong model is trained with weak supervision, it can either generalize in the case of benign overfitting or fail to generalize in the case of harmful overfitting.\n* An analysis of the \"data-abundant regime\", showing that weak-to-strong generalization can arise via early stopping but vanishes when the strong model is overtrained with weak supervision.", "questions": "* It is unclear from the setup in Section 2.1 how the \"easy\" and \"hard\" signals are defined and distinguished for various statements. \n    - From the proof of Proposition 2.2, the mixture of signs where the hard signals are sampled uniformly seems to be the only key difference between the easy and hard signals that leads to the separation of the algorithm-agnostic capacity gap between the weak and strong models (which I think should be highlighted explicitly). \n    - However, additional assumptions on the sampling probabilities $p_e, p_h, p_b$ and signal strength $\\|\\mu\\|,\\|\\nu\\|$ are needed (e.g., Condition (C5)) for weak-to-strong generalization when analyzing the training dynamics of GD. The current organization of these assumptions is somehow confusing. It may be helpful to partition the assumptions in Condition 3.1 into several parts. For example, C5 and C6 may be separated as a stand-alone additional assumption on the easy v.s. hard signals for the training dynamics analysis.\n* The phase transition in the \"data-scarce\" regime with respect to $n_{st}$ is not very clear from the statement of Theorem 3.4. In particular, Theorem 3.4 shows that $n_{st} \\ge C_2 \\frac{\\sigma_p^4 d}{p_b^2 \\|\\nu\\|^4}$ leads to benign overfitting, while $n_{st} \\le C_4 \\frac{\\sigma_p^4 d}{p_b^2 \\|\\nu\\|^4}$ leads to harmful overfitting. Here, the upper and lower bounds are asymptotically the same, and there are no discussions on conditions like $C_2 \\approx C_4$, showing that this indeed leads to a phase transition. The simulation in Section 5 shows one synthetic example with three seemingly arbitrary $n_{st}$, without investigating the scaling of weak-to-strong generalization with respect to $n_{st}$ that could demonstrate the phase transition.", "limitations": "Major limitations are discussed in the weaknesses section. Here are some minor points:\n* The explanations for some assumptions (specifically, C1-C4) in Condition 3.1 is vague. \n* Section 4 may be partitioned into subsections of \"data-scarce\" and \"data-abundant\" regimes to be more organized.\n* The meaning of \"filters\" in line 312 is not clear. The explanation in lines 310-312 is not very clear either.", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "### Strengths\n* While mainly leveraging existing problem setup and technical tools, this paper provides a fresh non-linear feature learning analysis of weak-to-strong generalization, which offers new angles to understand weak-to-strong generalization.\n* The setting and main takeaways from the theoretical analysis are clearly organized and presented. \n* The key theoretical insights outlined in Section 4 is helpful for understanding the intuitions behind the theoretical results and the implications of the results for weak-to-strong generalization.\n\n### Weaknesses\n* Some detailed settings and statements seem vague and could be better clarified. See the \"Questions\" section below for more details.\n* The empirical evidence of this paper seems limited, even given its theoretical nature. Section 5 only provides a single set of experiments on the synthetic binary classification task and does not investigate the scaling of weak-to-strong generalization with respect to $n_{st}$ that seems essential for demonstrating the phase transition in the \"data-scarce\" regime (see the second point in the \"Questions\" section below). That is to say, I don't think strong experiments on real data and models are necessary for this work, given its theoretical nature. But given the (possibly inevitable) limitations of some theoretical statements in the paper (e.g., Theorem 3.4, see the second point in the \"Questions\" section below), it would be helpful to at least provide thorough simulations on the synthetic binary classification task.\n* A potential limitation inherited in the problem setup of this work is that the capacity gap between the weak and strong model completely comes from the architecture of the weak and strong models with respect to the special structured data. This is fairly different from weak-to-strong generalization, or the superalignment problem that it aims to address, in practice. The capacity gaps between large foundation models are often due to many other factors beyond the architecture (e.g., pretraining data and methods) and shared across various tasks, more like differences in the qualities of their representations. While I think the learning dynamics analysis of weak-to-strong generalization from linear to non-linear models on special structured data is theoretically interesting and valuable, I subjectively believe that it has a considerable gap from the practical weak-to-strong generalization problem. I think such a gap should be carefully discussed, maybe as a part of the conclusion/limitations at the end.", "was_revised": true, "final_justification": "I would like to thank the authors for their efforts to address my questions and concerns. I will maintain my positive evaluation.", "rebuttal": "We express our gratitude for your valuable comments. In the following, we address the points raised by the reviewer.\n\n## **W2, Q2. Experiments on Synthetic Data**\n\nAdmittedly, a precise calculation of the constants $C_2$ and $C_4$ is complex; our analysis focuses on an asymptotic regime where parameters such as the number of data points and dimension are sufficiently large. In this regime, the upper and lower bounds for the transition match asymptotically up to constants, creating a sharp threshold. In the small sample settings of our experiments, this transition appears more gradual, rather than a sharp phase transition. However, by varying $n_{st}$ and the dimension d, we can still observe and verify the transition dynamics in our theoretical analysis.\n\nWe ran new experiments with the same setup as described in the paper, while varying $n_{st}$ and dimension $d$. The same pretrained weak model was used to generate pseudolabels across all runs within the same seed. We ran experiments for 5 different random seeds. Below is the average test accuracy with standard deviation across different seeds. \n\nAs shown in the table, the test accuracy of the weak-to-strong training generally improves as $n_{st}$ increases for both $d = 2000$ and $d = 4000$. This demonstrates the transition in the data-scarce regime. The results also suggest that the transition point scales with the dimension $d$, as a larger $n_{st}$ is required to achieve similar performance when $d$ is doubled, which aligns with our theoretical findings.\n\n| | $d=2000$ (weak test acc: 0.8508) | | $d=4000$ (weak test acc: 0.8494) |\n|:---:|:---:|:---:|:---:|\n| **$n_{st}$** | **weak-to-strong test acc** | **$n_{st}$** | **weak-to-strong test acc** |\n| 75 | 0.8829 ± 0.0448 | 150 | 0.8566 ± 0.0274 |\n| 150 | 0.8830 ± 0.0236 | 300 | 0.8888 ± 0.0267 |\n| 225 | 0.9022 ± 0.0204 | 450 | 0.8963 ± 0.0172 |\n| 300 | 0.9013 ± 0.0310 | 600 | 0.9019 ± 0.0249 |\n| 375 | 0.8831 ± 0.0428 | 750 | 0.8947 ± 0.0099 |\n| 450 | 0.8970 ± 0.0260 | 900 | 0.9054 ± 0.0178 |\n| 525 | 0.9135 ± 0.0124 | 1050 | 0.8845 ± 0.0145 |\n| 600 | 0.9022 ± 0.0281 | 1200 | 0.8846 ± 0.0317 |\n| 675 | 0.9126 ± 0.0200 | 1350 | 0.9128 ± 0.0124 |\n| 750 | 0.9268 ± 0.0173 | 1500 | 0.9036 ± 0.0106 |\n| 825 | 0.9122 ± 0.0119 | 1650 | 0.9112 ± 0.0277 |\n| 900 | 0.9228 ± 0.0044 | 1800 | 0.9001 ± 0.0253 |\n| 975 | 0.9053 ± 0.0115 | 1950 | 0.9079 ± 0.0132 |\n| 1050 | 0.9225 ± 0.0208 | 2100 | 0.9168 ± 0.0166 |\n| 1125 | 0.9254 ± 0.0191 | 2250 | 0.9205 ± 0.0254 |\n| 1200 | 0.9340 ± 0.0141 | 2400 | 0.9094 ± 0.0105 |\n| 1275 | 0.9176 ± 0.0293 | 2550 | 0.9275 ± 0.0194 |\n| 1350 | 0.9082 ± 0.0169 | 2700 | 0.9093 ± 0.0210 |\n| 1425 | 0.9223 ± 0.0148 | 2850 | 0.9066 ± 0.0228 |\n| 1500 | 0.9121 ± 0.0188 | 3000 | 0.9132 ± 0.0255 |\n| 1575 | 0.9205 ± 0.0150 | 3150 | 0.9096 ± 0.0277 |\n| 1650 | 0.9310 ± 0.0176 | 3300 | 0.9263 ± 0.0123 |\n| 1725 | 0.9262 ± 0.0138 | 3450 | 0.9197 ± 0.0157 |\n| 1800 | 0.9380 ± 0.0250 | 3600 | 0.9280 ± 0.0161 |\n| 1875 | 0.9148 ± 0.0250 | 3750 | 0.9343 ± 0.0144 |\n| 1950 | 0.9226 ± 0.0156 | 3900 | 0.9253 ± 0.0096 |\n| 2025 | 0.9230 ± 0.0221 | 4050 | 0.9169 ± 0.0081 |\n| 2100 | 0.9245 ± 0.0298 | 4200 | 0.9224 ± 0.0088 |\n| 2175 | 0.9248 ± 0.0143 | 4350 | 0.9133 ± 0.0136 |\n| 2250 | 0.9304 ± 0.0118 | 4500 | 0.9123 ± 0.0130 |\n\n## **W3. Architectural Differences Between Weak and Strong Models**\nIt is true that architectural differences are not the only factors contributing to the differing capabilities of weak and strong models. However, we believe that one key difference lies in expressive power, as exemplified by the weak-to-strong training experiment from GPT-2 to GPT-4 presented in [1].  While we focus on architectural differences in this work, we believe that the core intuition behind our analysis can be extended to more general scenarios, and we will add this discussion to the Conclusion section as you suggested.\n\n## **Q1. Conditions on Easy and Hard Signal**\nWe agree with the reviewer that the conditions on easy and hard signals appear in multiple places in the draft and may cause confusion. In Section 2.1, line 116, we mentioned that easy and hard signals differ in their learning difficulty. \n\nAs you mentioned, the XOR structure of the hard signals creates a capacity gap between our weak and strong models. We agree that this point should be mentioned earlier, and we will explicitly add it around line 116.\n\nIn addition, as you mentioned, Conditions (C5) and (C6) are related to the distinction between easy and hard signals and to the weak-to-strong learning scenario, which may differ in nature from Conditions (C1)–(C4). We grouped them together for compactness, but we will consider restructuring this part to improve clarity.\n\n## **Limitations. Suggestions for Clarification**\nThank you for your suggestions for improving our paper. We will address the points in the limitations part one by one, following the order in which you raised them.\n\n* We would like to provide further explanation of Condition 3.1. In (C1) and (C2), we assume a sufficiently large dimension and large sample sizes. These assumptions allow us to apply concentration inequalities to quantities such as norms and correlations involving Gaussian noise, as well as the number of each type of data. In (C3) and (C4), we assume a sufficiently small initialization scale and learning rate. These assumptions ensure that the effect of initialization can be neglected compared to the gradient descent updates, and that each update step remains small, which enables stable training dynamics. Lastly, we would like to additionally clarify that the motivation behind (C5) is that the difficulty of learning a signal is determined by its frequency and strength.\n* In our draft, we didn’t separate the discussion of the two regimes into distinct subsections, given that they share overlapping insights. Instead, we plan to add clearer transitional markers for the reader’s convenience in the next revision.\n* In line 312, “filters” refers to $w_{s,r}$ as defined in Definition 3. We would like to provide a more detailed explanation of the discussion in lines 310–312.\nFor a filter $w_{s,r}$ that is initially positively aligned with $\\nu_s$, the first term in the block equation between lines 304 and 305 is positive, while the second term is zero. As a result, the inner product between this filter and $\\nu_s$ increases over time.\nIn contrast, for a filter that is initially negatively aligned with $\\nu_s$, the first term becomes zero, and the second term is negative. This leads to a decrease in the inner product.\nThis contrasting behavior between positively and negatively aligned filters allows the strong model to learn both $\\pm \\nu_s$. \n\nWe will include these in the next revision.\n\n---\n\nThanks for your time and efforts. Please let us know if you have further questions.\n\nBest regards,\n\nAuthors\n\n---\n\n**References**\n\n[1] Burns et al. Weak-to-Strong Generalization: Eliciting Strong Capabilities with Weak Supervision. ICML 2024"}, {"review_id": "l6i8ljvnve", "reviewer": "Reviewer_yKoW", "summary": "The paper introduces a theoretical framework for studying weak-to-strong generalization via feature learning. It shows how a two-layer ReLU CNN learns from a linear CNN model, and characterize two regimes depending on the number of samples for training the stronger model. Empirical simulation match the derived theories.", "questions": "1. What is the role of weak model? It seems the weak model will learn to correctly classify both the easy-only and both-signal samples (with $o(1)$ error) while random guess the hard-only samples. Then the training of stronger model would be on a dataset with label noise almost only on hard-only samples. Is my understanding correct? If so, could the author comment on what is the difference to paper [2], which also considers label noise in their data model.\n\n2. How practical the data distribution is and how likely the theoretical results hold in practice? Could the authors provide some experiments done in real-world scenarios?\n\n3. Could the authors provide more discussions in relation to the existing theoretical analysis of weak-to-strong generalization? Currently the paper only mentions the difference in terms modelling assumption, without an in-depth discussion how the derived results in the paper show similar/different insights compared to existing works.\n\n4. It seems the settings and analysis techniques are based on [1,2]. It would be good if the authors could comment on the differences in terms of analysis and training dynamics, which could further help understand the insights as well as the technical contributions of the paper (if any).\n\n[1] Benign Overfitting in Two-layer Convolutional Neural Networks.\n\n[2] Benign Overfitting in Two-layer ReLU Convolutional Neural Networks.", "limitations": "The discussions of limitation is insufficient. Authors are encouraged to add a separate paragraph outlining the limitations.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 2, "originality": 3, "strengths_and_weaknesses": "In terms of strengths, the paper studies weak-to-strong generalization with nonlinear models, in contrast to existing analysis with linear model or random feature model. Also, the theoretical analysis appears to be complete in terms of characterizing a transition from generalization to overfitting. For the weakness, refer to the question section.", "was_revised": true, "final_justification": "I remain positive for the paper as most of my concerns are addressed during rebuttal.", "rebuttal": "We express our gratitude for your valuable comments. In the following, we address the points raised by the reviewer.\n\n## **Q1, Q4. Comparison to [1],[2]**\nYour understanding on the role of weak model is correct. We would like to provide differences between our work and previous works [1, 2]. \n\n* We focus on a training scenario that is different from the one considered in [1, 2]: training a single type of network. Specifically, we study a two-stage training process: first training a weak model, then training a strong model supervised by the pretrained weak model. This difference in training scenarios leads to some technical differences.\n\n* While [1,2] considers a single type of signal for each class, our setting involves two different types of signals per class. Moreover, the label flipping probability in [2] is independent of the input, whereas in our setting, it depends on the input because it is introduced by a pretrained weak model. These differences require more careful analysis in our proofs.\n\n* While working on this paper, we also identified technical issues in [2]. Specifically, [2] often uses the sum of activations as the model output, whereas the correct formulation should use the average of activations. To correct this, in our Lemma C.3 (S7), we show that the filter whose initialization has a positive inner product with the noise tends to have a noise coefficient close to the maximum among all filters. This is an analysis not previously presented in [2].\n\n* Condition 4.1 in [2] considers a regime where noise learning dominates signal learning, which corresponds to the data-scarce regime in our work. However, we additionally consider the data-abundant regime and reveal that a different behavior emerges in this setting.\n\n## **Q2. Practical Insights and Experiments on Real-World Data.**\nOur data distribution is inspired by real-world characteristics, consisting of label-relevant information (corresponding to the signal in our work) and label-irrelevant information (noise in our work). Moreover, the label-relevant information varies in learning difficulty due to differences in its strength or complexity. The distribution is designed to reflect these properties while maintaining mathematical tractability. We also emphasize that analysis in such simplified settings can still provide valuable insights into the underlying mechanisms.\n\nOur key intuition behind weak-to-strong generalization is as follows: there exists a subset of data containing hard-to-learn information that is nevertheless labeled correctly due to the presence of easy-to-learn information (referred to as easy signals in our setting). This subset of data, termed both-signal data in our work, provides gradient updates that enable the strong model to learn the hard-to-learn information.\n\nWe additionally conducted experiments on a simplified real-world dataset to support our findings. Specifically, we slightly modified the MNIST dataset to highlight the roles of key components such as signal and noise. The results demonstrate that our theoretical insights also hold beyond our settings. Detailed experimental settings and results are provided in our responses to Reviewer ABZC’s W1 and Q2.\n\n## **Q3. Comparison to Previous Works on Theory of Weak-to-Strong Generalization**\nWe would like to include more discussion on some prior works related to the theory of weak-to-strong generalization, in addition to what is already presented in our draft.\n\nThe most closely related prior work is [3], which shares a similar intuition with ours—namely, that data containing both easy-to-learn and hard-to-learn information is essential for weak-to-strong generalization. However, their theoretical analysis relies heavily on the abstract framework introduced in [4], and it remains unclear whether gradient-based training can indeed lead to weak-to-strong generalization in their setting.\n\nSimilar to our results, [5] demonstrates that weak-to-strong generalization can emerge through benign overfitting. They consider linear models and analyze the minimum $\\ell_2$-norm interpolating solution, which is attainable via gradient descent. We view this as a step forward from analyses based purely on abstract frameworks. However, this work still relies on the assumption that the weak and strong models have access to different sets of features different access to feature space, an assumption we consider to be somewhat unnatural. Moreover, this work does not consider scenarios with a large amount of data, which we explicitly analyze as the data-abundant regime in our work.\n\n[6] considers a more natural setting, where training is performed using gradient-based methods and the weak/strong models are chosen as random feature models with different numbers of hidden nodes. However, they analyze training on the population loss, where early stopping becomes crucial, as overtraining can lead the strong model to produce outputs similar to those of the weak model on the population. In contrast, our analysis is based on finite-sample training and explicitly reveals the role of early stopping in the finite but data-abundant regime.\n\nWe believe that our contribution is essential in this line of work, as it makes the theoretical analysis more aligned with realistic training settings.\n\n## **Limitations**\nThank you for your suggestions. We plan to discuss our limitations more explicitly in the next revision.\n\n---\n\nThank you very much for your time. If there is anything that requires further clarification, please do let us know.\n\nBest regards,\n\nAuthors\n\n---\n\n**References**\n\n[1] Cao et al. Benign Overfitting in Two-layer Convolutional Neural Networks. NeurIPS 2022\n\n[2] Kou et al. Benign Overfitting in Two-layer ReLU Convolutional Neural Networks. ICML 2023\n\n[3] Shin et al. Weak-to-Strong Generalization through the Data-Centric Lens. ICLR 2025\n\n[4] Lang et al. Theoretical Analysis of Weak-to-Strong Generalization. NeurIPS 2024\n\n[5] Wu & Sahai. Provable Weak-to-Strong Generalization via Benign Overfitting. ICLR 2025\n\n[6] Medevedev et al. Weak-to-Strong Generalization Even in Random Feature Networks, Provably. ICML 2025"}]

Author rebuttal:

Meta-review: This paper develops a theoretical framework for weak-to-strong generalization using a stylized setting where a linear CNN serves as the weak model and a two-layer ReLU CNN serves as the strong model. The authors prove that in data-scarce regimes, weak-to-strong generalization can occur via benign overfitting, while in abundant data regimes it arises under early stopping but may vanish with overtraining. Simulations support these results and highlight additional behaviors beyond theory. 

The main strengths are the technical rigor, the clear theoretical characterization of different learning regimes, and the identification of precise conditions under which weak-to-strong generalization succeeds or fails. The rebuttal added valuable intuition, clarified assumptions, and provided new experiments on a modified MNIST dataset, demonstrating that the theoretical insights extend beyond purely synthetic cases. Importantly, the authors also corrected and extended aspects of prior feature-learning analyses, which reviewers recognized as a meaningful contribution. The weaknesses are primarily the highly engineered data distribution and limited real-world applicability, as well as an exposition that could better emphasize the roles of key assumptions. 

During the rebuttal, the reviewers agreed that the paper makes a technically solid and timely contribution. The authors’ clarifications, additional intuition, and new experiments satisfactorily addressed the main concerns, and some reviewers raised their scores accordingly. While the narrow and stylized scope limits its suitability for a spotlight, the work provides rigorous and valuable insights into weak-to-strong generalization, a phenomenon of broad current interest. I therefore recommend acceptance.
Decision: Accept (poster)