On the Role of Label Noise in the Feature Learning Process
Authors: Andi Han
Wei Huang
Zhanpeng Zhou
Gang Niu
Wuyang Chen
Junchi Yan
Akiko Takeda
Taiji Suzuki
Venue: ICML 2025 poster (2025)
Keywords: Label noise
Feature Learning
Training Dynamics
Primary area: theory->deep_learning
TL;DR: We theoretically characterize the role of label noise in training neural networks from a feature learning perspective, identifying two-stages in the training dynamics.

Abstract: Deep learning with noisy labels presents significant challenges. In this work, we theoretically characterize the role of label noise from a feature learning perspective. Specifically, we consider a signal-noise data distribution, where each sample comprises a label-dependent signal and label-independent noise, and rigorously analyze the training dynamics of a two-layer convolutional neural network under this data setup, along with the presence of label noise. Our analysis identifies two key stages. In Stage I, the model perfectly fits all the clean samples (i.e., samples without label noise) while ignoring the noisy ones (i.e., samples with noisy labels). During this stage, the model learns the signal from the clean samples, which generalizes well on unseen data. In Stage II, as the training loss converges, the gradient in the direction of noise surpasses that of the signal, leading to overfitting on noisy samples. Eventually, the model memorizes the noise present in the noisy samples and degrades its generalization ability. Furthermore, our analysis provides a theoretical basis for two widely used techniques for tackling label noise: early stopping and sample selection. Experiments on both synthetic and real-world setups validate our theory.

On the Role of Label Noise in the Feature Learning Process
Andi Han 12 Wei Huang",
Zhanpeng Zhou 33
Gang Niu
Wuyang Chen
Junchi Yan
Akiko Takeda Taiji Suzuki
Abstract
1989), yet this ability becomes problematic in the presence of noisy labels. ever-parameterized neural networks, which have sufficient capacity to memorize training data, tend to overfit noisy lahels, leading to poor generalization on unseen data (Zhang et al., 2021). Although many studies (Patrini et al., 2017; Ma al., 2018; Yu al., 2019; Tanaka et al., 2018; Han et al., 2018; Liu et al., 2023b; Chen al., 2023a; Xia et al., 2024) have developed methods mitigate the effects of label noise in practice, our theoretical understand- ing of how label noise affects the learning process remains incomplete. A crucial step toward bridging this gap is to develop comprehensive theory describing neural network training dynamics in the presence of label noise.
Deep learning with noisy labels presents signif- icant challenges. In this work, we theoretically characterize the role of label noise from a fea- ture learning perspective. Specifically, we con- sider a signal-noise data distribution, where each sample comprises lahel-dependent signal and label-independent noise, and rigorously analyze the training dynamics of two-layer convolutional neural network under this data setup, along with the presence label noise. Our analysis identifies two key stages. In Stage I, the model perfectly fits all the clean samples (i.e., samples without label noise) while ignoring the noisy ones (i.e., samples with noisy labels). During this stage, the model learns the signal from the clean samples, which generalizes well on unseen data. In Stage II, as the training loss converges, the gradient in the direction of noise surpasses that of the signal, leading to overfitting on noisy samples. Eventu- ally, the model memorizes the noise present in the noisy samples and degrades its generalization ability. Furthermore, our analysis provides the- oretical basis for two widely used techniques for tackling label noise: early stopping and sample selection. Experiments on both synthetic and real- world setups validate our theory.
Existing works have attempted to analyze the effects of la- bel noise theoretically, but many such studies focus on the lazy training regime (Jacot et al., 2018; Chizat et al., 2019a). For instance, Li et al. (2020) constrained the distance be- tween model weights and their initialization, while Liu et al. (2023a) adopted an infinitely-wiin -ide neural network, where the dynamics can be described by a static kernel function. However, the lazy regime, which typically occurs in wide neural networks with relatively large initialization, is consid- ered undesirable in practice (Chizat et al., 2019a; Ghorbani et al., 2020). Understanding how label noise influences training dynamics beyond the lazy regime remains an active research frontier.
Recently, a new line of research (Allen-Zhu & Li, 2020; Frei al., 2022: Cao al., 2022; Kou al., 2023; Xu et al., 2024) has developed the feature learning theory to better capture the complex, nonlinear training behaviors of neural networks. The core idea of the feature learning theory, which dates back to Rumelhart et al. (1986), is to assume simplified data distribution and analyze how neural networks learn useful features from it-an an approach that stands in contrast to the linear dynamics observed in lazy training. However, few works have examined how label noise shapes these nonlinear feature-learning dynamics. To address this, we pose the following question:
1. Introduction
One of the key challenges in deep learning lies in its suscep- tibility to label noise (Angluin & Laird, 1988). The success of deep learning stems from its exceptional ability to approx- imate arbitrary functions (Hornik al., 1989; Funahashi,
"Equal contribution 'RIKEN AIP Universsity of Sydney 'School of Computer Science & AI, Shanghai Jiao Tong University "Simon Fraser University *University of Tokyo. Correspondence to: Andi Han <andi. hwwhhaydnyyeedu...o.mmo Zhanpeng Zhou
Wei Huang wwei.huang.v@@rieen. <zap1012@sjtu.edu..n..
How does label noise affect the feature learning process of neural networks?
Proceedings of the 42nd International Conference Machine Learning, Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).
Our main contributions. In this work, we analyze the

---

On the Role of Label Noise in the Feature Learning Process
Stage I. fit all clean samples and ignore noisy ones; learn signal.
Theorem 4.1
w/ label noise
Stage II. over-fit noisy samples; learn noise; degrade generalization.
Theorem 4.2
w/o label noise
the loss converges; all clean samples; generalize well.
Theorem 4.4
Table 1: Overview of the two-phase picture and corresponding theoretical results.
feature learning process of neural networks in the presence of label noise, unveiling two-stage behavior. Our analysis is based on signal-noise data distribution. Specifically, we consider the classification task where each data point consists of a label-dependent signal and a label-independee noise patch. This simplified data setup has been widely adopted recent theoretical advances on feature learn- ing (Allen-Zhu & Li, 2020; Frei et al.. 2022; Cao et al., 2022; Kou al., 2023). We introduce label noise by flip- ping the label into other classes with certain probability. We then rigorously analyze the training dynamics of two- layer convolutional neural network under the above setup and characterize the following hvo-stage picture:
In summary, our theoretical analysis provides a rich and trackable view of training dynamics under label noise while providing practically relevant insights, a contribution that addresses a notable gap in deep learning theory.
2. Related Work
Feature Learning Theory. Feature learning (Geiger et al., 2020; Woodworth et al., 2020), or the rich regime, is of- ten used to broadly describe learning behaviors that de- viate from the lazy regime. Despite significant interest in exploring the mechanism behind feature learning, our understanding remains limited (Tu et al., 2024). Recent works (Allen-Zhi & Li, 2020; Frei et al., 2022; Allen-Zhu & Li, 2022; Cao et al., 2022: Kou et al., 2023; Zou et al., 2023; Chen et al., 2023b; Huang et al., 2023b; Xu et al., 2024; Bu et al., 2024) have developed systematic theoretical framework to study feature learning, namely feature learn- ing theory. By simplifying the data setup, feature learning theory provides a tractable view of the complex non-linear dynamics of neural networks and has offered significant insights into the success of deep learning. For instance, feature learning theory explains the implicit bias in various architectures, such convolutional neural networks (Cao et al., 2022; Kou et al., 2023), vision transformers (Jelassi et al., 2022; Li et al., 2023; Jiang et al., 2024), graph neural networks (Huang et al., 2023a), and diffusion models (Han et al., 2024; 2025). Many attempts have also been made to understand different training schemes, including gradient descent with momentum (Jelassi & Li. 2022), Adam (Zou et al., 2021), sharpness-aware minimization (Chen al., 2024), mixup (Zou et al., 2023; Chidambaram et al., 2023) and contrastive learning (Huang et al., 2024).
Stage The model perfectly fits all the clean samples while ignoring the noisy ones'. The model mainly learns the signal from clean samples, which generalizes well on unseen data.
Stage II. The training loss converges and the model over- fits to the noisy samples. The model memorizes the noise features from noisy samples, degrading its generalization.
For comparison, we also show that when training without la- bel noise, the model tends to fit all training samples through- out the training, and the test error remains well-bounded See Table for summary. Our two-stage picture success- fully explains existing empirical phenomena label noise: neural networks tend to first learn simple patterns from clean samples and then proceed to memorize the noisy ones (Arpit et al., 2017; 7 Han et al., 2018).
Our theoretical analysis also provides valuable insights into the effectiveness of two common techniques used address the label noise problem, early stopping (Liu et al., 2020; Bai et al., 2021) and sample selection (Han et al., 2018; 2020). i) For early stopping, we show that stopping the training process at the end of the first stage ensures a low test error, even in the presence of label noise. ii) For sample selection, we verify that the small-loss criterion 2 (Han et al., 2018) can provably identify the clean samples from noisy ones. These insights ground the path towards more effective techniques tackling the label noise problem.
Label Noise Theories. Many existing works have tried to theoretically analyze the training of neural networks under label noise. Li et al. (2020); Liu et al. (2023a) studied label noise in the lazy-training regime (Jacot et al., 2018; Chizat et al., 2019b), constraining the distance between model weights and their initialization, and thus cannot capture the process of learning features from data (Rumelhart et al., 1986; Damian et al., 2022). On the other hand, Frei et al. (2021) focused on the early dynamics of neural networks trained with SGD, which can be largely explained by the behavior of a linear classifier (Kalimeris et al., 2019; Hu et al., 2020), thereby overlooking the adverse effects of label noise on generalization in later training stages.
'To clarify, "clean samples" refers samples without noisy labels, while "noisy samples" refers to those with noisy labels. The same terminology applies for the rest of this paper. "The samples with small loss are more likely he the ones which are correctly labeled, i.e., the clean samples.
2

---

On the Role of Label Noise in the Feature Learning Process
In comparison, our work characterizes the whole training process of neural networks under label noise from feature- learning perspective, unveiling novel two-stage behavior in the training dynamics. Some recent works (Kou et al., 2023; Meng et al., 2023; Xu et al., 2024) in feature learning theory also considered label noise in their analysis. However, they fail to characterize the two-stage distinet behaviors due to differences in their setups.
(wi(W+1:33 and F-1(W -1, x) are given by
1 m F( m
(o((War))))) o ((W 8))
for j = Here, ((.) is the ReI.U activation function, defined as (x) max This corresponds to two- layer CNN with second layer weights fixed be =1/m.
We initialize the entries of W independently from zero-
3. Problem Setup
mean Gaussian distribution with variance o. i.e., w (O0, TaTa) for all j = +1, E [m]] We also fix the second layer weights uniformly to +1, which is a common setting used in previous studies (Arora et al., 2019; Chatterji et al., 2021).
Basic Notation. We use bold letters for vectors and matrices, and scalars otherwise. The Euclidean norm of a vector and spectral norm of matrix are denoted by || lle. and the Frobenius norm of matrix by I| ||r. We use y to represent the true label and y to represent the observed label. For logical variable a, let (a) 1 if a is true, otherwise
Gradient Descent with Logistic Loss. We consider the logistic loss E(S, 5) = loo (1 + exp(- -)). Then the training loss, or the empirical risk, can be written as:
(a) 0. Denote La as the d x d identity matrix and [n] m1].
Binary Classification. We consider chary-classificatiin data distribution D,, following prior works (Cao et al., 2022; Kou et al., 2023), where each data point consists of label-dependent signal and a label-independent noise. More precisely, let μ E Rd be fixed vector representing the signal and let & E Rd be random vector sampled from N(0, ((O,) representing the noise. Then each data point x E R2d is defined as x = 1x())x(())
Ls( = 1 ((((W.)).)))
To minimize this empirical risk, we use gradient descent (GD) with a constant learning rate > 0.
w ((+1)) jr j.r 17
((()) (t)
Vw5,. Lss (W())
x(2),, where one of x1), (1),x( x(2) is chosen to be y/u and the other E. Here y E 1- is the corresponding label, generated from the Rademacher distribution, i.e., Ppy- = 1) = P(y = -1) 2- We sample the training set {x,: } from D.r and assume the training set is balanced without loss of generality.
n frr nm
(t) w
o' (l (1) j.m ualiiuu (1)
nmm
Label Flipping. We introduce label noise for each training sample, where the observed label ÿ may differ from the ground-truth label y 4. Specifically, we flip the observed label into the incorrect class with a certain probability, i.e.,
where the loss derivative e:10 =
Itexp(e.((Wi), x.))
Evaluation. We characterize the generalization by evaluat- ing the 0-1 error on the test distribution Drest:
T+ = Plū = - 11y = T) = Piū = 1 = -1). We require T- T- E (0, 1/2) such that neural networks can still learn the signal from data under label noise. In addition,
1. (W) = (x.x)))DDin (v S(W, x) < 0)
we denote the clean sample set as S, == {i E [m] Tr = y and the noisy sample set as Sy ii [m] ÿt y.).
D Deest mainly follows the settings of De.: however, to sim- ulate spurious features in real-world scenarios, for any (x, v) E Deest. we define x = [y/u, & + C). where & ~ (nif((E)) and < ~ o0 In practice, spurious features exist, which occur in both the training and test set but lack causal relationships with the ground-truth la- bel y (Sagawa al., 2020; Zhou et al., 2021; Singla & Feizi, 2021; Izmailov et al., 2022). We consider the label- independent noise & in the training set as spurious features and randomly incorporate them into the test distribution.
Two-Layer ReLU CNN. We consider two-layer convo- lutional neural network (CNN) with ReLU activation, as in (Cao et al., 2022; Kou et al., 2023). Formally, given the input data x, the output of the neural network is de- where 'The analysis can be extended to multi-class classification, where each class is represented by distinct, orthogonal signal vec- tor, i.e., Mli U2, Mi. along with one labels. "In experiments. the ground-truth labels are inaccessible, and we only evaluate models based on the observed labels.
fined as f(W, =
x)
Signal-Noise Decomposition. In our analysis, we utilize a proof technique termed signal-noise decomposition, which has been widely adopted by (Li et al., 2019; Allen-Zhu &
3

---

On the Role of Label Noise in the Feature Learning Process
Li, 2020; 2022; Cao al., 2022). The signal-noise decom- position breaks down the weight (!) into signal and noise components. Formally, we express:
Remarks on Condition 4.1. We first require the signal-to- noise ratio n -NRR and label flipping probability T+, to be of constant order. Such condition is critical for the sub- sequent characterization of the two-stage behaviors. Other conditions, including sufficiently large d, m, n. ||al|/2 and sufficiently small co 77, are commonly adopted in existing analysis (Cao et al., 2022; Kou et al., 2023; Meng et al., 2023), to ensure sufficient over-oorameet peee-paraettrrizttion and that the training loss converges under gradient descent.
jir
w jr w (0) jir + + M F
Pana E E. (2)
where Tj.r /0000 and (0) Pj.r.i represent the signal and noise coef- ficients, respectively. The normalization factors ||ll (t) and ||E:ll2 ensure that 7 = (w.rr ue), and Pjira Re "2r"
4.1. Feature Learning Process with Label Noise
(w jirt Et) Naturally, T/1e characterizes the process of signal learning, while ( captures the memorization of noise.
In this subsection, we analyze the feature learning process of neural networks under label noise. We identify two stages where the learning dynamics exhibit distinct behaviors.
To facilitate finer-gras Aner-grained analysis of the evolution of (1)
the noise coefficients, we introduce the notations Pjar. == Pj.r. 1 (P 2 2 0). pfth. == P (Cao al., 2022). Consequently, the weight decomposition can be further expressed as:
Stage I. Model Fits Clean Data. Theorem 4.1 characterizes the learning outcome at the end of Stage I.
(4) (1) S 0), following
Theorem 4.1. Under Condition 4. 1, there exists Ti =
θ (1T 1n-on -2 2d such that Pacnr (L) all i [n]]
(T1) ((T))
E [m]] with (w (0) B..r. Ex) 2 0 and (Th) @(1) for all
(t)
w)
j.r
(0)
+ 1n 4
+l, E [m]] and
Para 1
Σ Son 12
(3)
(Ti) > Pins for all j +l, E [m], E [n].
1. 7ir
2. All clean samples i E S, satisfy üt (W(()) xx,) 2 0.
This decomposition translates the dynamics of weights into dynamics of signal and noise coefficients (See Lemma C.I).
3. All noisy samples E Sy satisfy ū:f (T.)), ,x,) S O.
4. Main Results
Theorem 4.1 states that at the end of Stage I, the signal co- efficients 7/.r are larger than the noise coefficients (T,) suggesting signal learning dominates the feature learning process. During this stage, the model correctly classifies all clean samples, i.c., Vi E S,, ūc ff (W(T)) x.) 2 O, and classifies all noisy samples to the ground- -ruth classes, i.e., Vi E Sy, (W x;) = - / / (W()), x.) 2 0.
Before presenting our main results, we first state main condition.
P
Notations. We denote SNR- == |1111/// to be the signal-to-noise ratio and T 101 -d-1) to be the maximum iterations for any given > 0.
Condition 4.1. Suppose there exists a sufficiently large constant C' such that the following holds.
Insights from Theorem 4.1. In Stage the model perfectly fits all the clean samples while disregarding the noisy ones. The model initially learns the signal from the data, leading to an optimal generalization ability.
1. The signal-to-noise ratio and label flipping probability satisfy n SNR² = @(1), T+, 7- = +1))
Stage II. Loss Converges and Model Fits Noisy Data. Theorem 4.2 formalizes the learning behavior in Stage II as the training loss converges.
2. The dimension of a single data patch d satisfies d > C' max (n² log(nm/8) "illellll Vlog(n/0)}.
3. The size of training sample and model width m satisfy > Clog(n/6), 2 C' Cl))
Theorem 4.2. Under Condition 4.1, for arbitrary c <> O. there exists t" E (T, such that training loss converges, i.e., Ls (s()(())) S c and
4. The magnitude of signal patch ||al|2 satisfies || Co log(n/8).
1. All clean samples, iee, i E Se holds that ÿr (.((W())) xx)) 20.
5. The standard deviation do of the Gaussian dis- tribution for weights initialization satisfies do S
2. There exists constant 0 < T' < I-tr_ such that there are I'n noisy samples, i.e, i E Si
||ا4|| C-l min (vno -/ log(m/6)-117)
that satisfy 1 m Em Pani > 1 E -iir and
(t)
6. The positive constant learning rate 17 satisfies 7 <
C-1 min (o=2 20-3 n (om3//nnmm/oog(m/55).. - In..
5.((W() x.) 2 O.

---

On the Role of Label Noise in the Feature Learning Process
3. Test error D (W(")) 2 0.5 (T.
complexity of the training dynamics and unknown data dis- tribution. However, our theory suggests the existence of point Ti, beyond which further training may degrade gener- alization performance. This implies that validation accuracy can serve as a practical surrogate for identifying, which aligns with the common practice of early stopping at the point of maximum validation accuracy. Indeed, our theory explains the effectiveness of the common practice.
Theorem 4.2 states that in Stage II, as the training loss converges, the model continues to make correct predic- tions clean samples, consistent with Stage I; however, for certain noisy samples, the averaged noise coefficient across all neurons surpasses the averaged signal coefficient, i.e., J/ >m P > m -- 7 B..r" Consequently, for m these noisy samples, the model's predictions align with the noisy observed labels ÿ. In addition, if evaluating the model on the test distribution introduced in Section 3, it results in a constant, non-vanishing test error, which is lower-bounded by the label flipping probability in the training set.
4.3. Feature learning Process without Label Noise
For comparison, we also analyze the feature learning process of neural networks without label noise. The analysis follows similar two-stage framework as the analysis conducted with label noise.
Insights from Theorem 4.2. With the presence of label noise and sufficient training iterations, the model inevitably learns the noise features from the data, which leads to de- graded generalization.
Model Fits All Data and Generalizes Well. Theorem 4.4 characterizes the learning outcome without label noise.
Theorem 4.4. Under Condition I with T+, = 0, there exists Ti = O(n -L "nmo 2 "d-1) such that for all Ti S 5 T v.(((()) xx,) 2 0 for all E [mn]. In addition. there exists a time t" E [TT, T*] such that training loss
4.2. Theoretical Supports for Techniques: Early Stopping and Sample Selection.
Our two-stage picture provides theoretical support for two widely used techniques to address label noise: early stop- ping (Liu et al., 2020; Bai et al., 2021) and sample selec- tion (Han et al., 2018; 2020). Intuitively, early stopping aims to stop training before the loss converges, preventing overfitting noisy samples. On the other hand, sample selection leverages the small-loss criterion (Han al., 2018) to distinguish clean samples from noisy ones, assuming that samples with smaller losses are more likely to be clean. Proposition 4.3 formally supports the effectiveness of these two strategies.
converges, i.e., Ls( (s(W(t)) ) S and
1. yff ).((((t)) xx) 2 0 for all i E [m].
2. Test error is bounded as (W((()()) S exp { " ( for some constant CD 0.
Theorem 4.4 states that without label noise, all samples can be classified correctly at the end of training, suggesting that the model fits all the samples throughout the training process. Theorem 4.4 also shows that when evaluating, the test enror can be upper bounded by exp( o
Proposition& 4.3 (Early stopping and sample selection). Un- der the sume conditions as in Theorem 4. 1, we have that
Early stopping: suppose the training is terminated early at Ti, then the test loss is bounded by T (W)))) v exp(-dn-1 for some constant C" > O.
Cooga ). Thus, n- FNRS > 2Cp = ((1), it follows that L6 (W(')) S n|| exp( 20ooga) ) which is small given the requirement on d (see Condition 4.1).
Sample selection: At iteration Tú, clean and noisy sam- ples can be well-separated based on the training loss,
i.e., for all i E St, e(Th) I log(2) and for all i E Sj, ((Th)) > lo)(2).
5. Proof Sketch
In this section, we provide an overview of our proof tech- niques for our theoretical results in Section 4.
Proposition 4.3 implies that if training is stopped during Stage I S Ti, before the loss converges, the test error can be upper bounded arbitrarily small under the condition that d d= [((n2) Proposition 4.3 also states that noisy samples tend to have higher loss values compared to clean samples, and there exists a hard threshold log(2), which allows for perfect separation of clean samples from noisy ones.
Technical Novelty. Compared with existing works in fea- ture learning theory, we mainly introduce two novel condi- tions: i) n SNR² and ii) T-, T- are of the constant order. These two conditions establish a significantly different train- ing regime and are crucial for identifying the two-stage picture in learning dynamics. We delve into the technical details of these distinctions in the subsections below and in Appendix A.
Remarks on Proposition 4.3. We note that directly com- puting Ti in real-world scenarios not feasible due to the
5

---

On the Role of Label Noise in the Feature Learning Process
5.1. Feature Learning Process with Label Noise
a constant, i.e., | 2 C2 for all E [n]. This ensures the balance of loss derivatives across all samples as (e,00 S 1. Such a condition allows both Pj T3." T3. to increase to a constant order, enabling the establishment of the bound in Proposition 5.2. Furthermore, by applying Lemma 5.1, we can assert that U: ( x;) 2 0 for all i E St. On the other hand, as long nt- -NSS 2 c', for some constant c' > 0, we can demonstrate that signal learning slightly surpasses noise memorization, concluding that j.f (W x.) S 0 for noisy samples E Sy.
The analysis of feature learning with label noise critically relies on Lemma 5.1, which shows the difference in terms of model predictions between clean and noisy samples. Lemma 5.1. Under Condition 4.1, there exists a sufficiently large constant Cj such that all t E [0, J, the following are satisfied:
(00
(t)
+ P (..n)) - 1/C, S (.f(W()) x.) &
r=
1 m (t)
1==1 (8.r Parra)) + 1/0, for all clean samples,
In Stage II, after the coefficients reach a constant order, the loss derivatives can no longer be lower-bounded by a constant. To establish that Proposition 5.2 still holds in this stage, we first rewrite the signal learning dynamics in Lemma C.I as follows:
i.e., i E St
m -m= (p(t)
7- -) 1/O, S iif(W()) x1) S Bon
(t)
m -r=
1
(p Mini - + 1/C1, for all noisy samples,
i.e., i E Sy.
(t+1) (t)
7
[ [[ (1) J.rt Bifl) 2 0)
Lemma 5.1 suggests for clean samples i E Se. the model prediction ūi (W(())) x,) is determined by J. >> (T P/ Pi..a)) while for noisy samples E Sy. ((())) x.) is
nm
iES,
Σ SE
(n (1) Ball) 2 0) m0l.
determined by Em= (Pir.
(t)
(1) -.
Recall 16,00 (Wei))):((Wi)) Based on Lemma 5.1,
Besides Lemma 5. we also need to bound the scale of coefficients throughout the training process.
|,,00 1 E Sy) can be larger than 1,(0) |[i E S,), which (1)
Proposition 5.2. Under Condition for any 0 S STST", we can bound
causes 7ir to decrease. However, we show by contradiction
that 75r S 0 cannot occur. When 7/ decreases, the gap between 1 E S.) and |e(00) [ E Sy) diminishes, allowing ?jr to eventually increase in subsequent iterations. Therefore, the upper bound for both 7/00 P).,, can be de-
0 S Pr Tor < (log(T")),
(t)
(6)
0 2 S.r 2- (max (oul p1l2, v Vd, nd 1/2)).
(t)
(()
rived by showing that |,(00) converges rate of O(1/t) ((() when either 755- or Py.r, grows to a logarithmic order.
Proposition 5.2 states that lp(0) is lower bounded by j.r. small term based on Condition 4.1. In addition, both (/0) 3jr are positive and cannot grow faster than loga- rithmic order of T
Additionally, we demonstrate that training loss converges at some iteration 8x. Upon convergence, because of the monotonicity of P and positivity of "5,r- we can show ú (W"" xx.) 2 0 for all i E St. On the other hand, we establish by contradiction that there must exist con- stant fraction of noisy samples satisfying oif( .x)) Z
(t)
Comparison with Previous Studies. Some previous works also need to bound the scale of coefficients during training; however, their analysis is not applicable to our case due to our condition that n SNR2 = ((1). As a representative example, the analysis in Kou et al. (2023) requires the auto- matic balance of updates, i.e., the loss derivatives /(()) are balanced across all samples. However, in our case, due to the SNR condition, signal coefficients are on the same scale as noise coefficients. Consequently, the loss derivatives e((t) are no longer solely determined by 1 > p.... Thus, m the automatic balance of updates cannot be derived.
O. Because otherwise, we would have 1 Em je.rd m
Y -- S C, for some constant C, > 0 over a constant frac- tion of samples. This suggests the training loss Ls (s(()) can be lower bounded by strictly positive constant ci 0, which leads to a contradiction.
Finally, to establish the test error, we show that, based on the test distribution Drest introduced in Section 3, there exists some sufficiently large constant C' that
Two-Stage Analysis. To prove Proposition 5.2 as well as the main theorems in Table under our Condition 4.1, we separately consider two stages.
Plyf (W(") xx) 0)
In Stage I, before the maximum of the coefficients reaches a constant order, all loss derivatives can be lower bounded by
P
Σ
c (( (t') y.r E, + ())
6

---

On the Role of Label Noise in the Feature Learning Process
m
TR m
w/ label noise
w/o label noise
yor E m Σ
(0) y.r
+ +1/0²)
make of 7
Coeffidents
4.0
Next, we show that for any y = =1, there exists some
3.0
sufficiently large constant C2 that for any E Sj n Sy:
2.0
(r") (w")) yor C) 2 p -y. 11/C2, (w E C) S 1/C2.
1.0
0.0
Then, based the scale that 1
Ce. we can show P(yf Plyf(W (W m Σr Pa.nt (-bur)
(6))
100
x) < 0) 2 0.5T+ if =
and Pfyf (W()), x) < 0) 2 0.5T_ y = -1
Anamay
0.75
0.6
0.50
ACC AcCnvasn
5.2. Feature Learning Process without Label Noise
ACCo, ar
0.25
ACCo, a
The analysis of feature learning without label noise follows similar two-stage framework as the analysis with label noise. Our analysis without label noise relies on Lemma 5.3, where we show that under Condition 1. the loss derivatives are balanced across all samples, and both the noise coefficients and signal coefficients are of the same order.
0.0
0.00
150
ltteaatonn
Iteration
Figure 1: Experimental validation under the synthetic setup, with label noise (left) and without label noise (right). (Top) The change in maxj,r "ir (signal learning) and maxj.r Pj.r.s (noise memorization) on noisy (i.e., when Yi # (n) and clean samples (i.e., when y/s = ÿ.) w.n.t the training iteration t. (Bottom) The change in overall train- ing accuracy AcCDius as well as the accuracy on clean ACCD and noisy samples ACCD w.I.t the train- ing iteration t for models under different settings. Note that there are no noisy samples when training without label noise; thus we only plot noise memorization on clean sam- ples and the overall training accuracy. The gray dashed line separates the two stages for training with label noise. More experimental results are in Appendix F.
Lemma 5.3. Under Condition 4.1, for any 0 SISST, there exists constants K. Ce >> O such that
1. 1 1
(8) (5) + (5) Pan.rik 78k Ks for all
m
i, k E [n].
2. (000 10( S for all k [n].
Lemma 5.3 allows us to establish Proposition 5.2 for all training iterations. Initially, we can demonstrate that both signal and noise coefficients reach a constant order during Stage as in Section 5.1. In Stage II. we can show that the scales of the signal and noise coefficients remain on the same order, i.., / Σi= P/t = O(SNR?). Finally, by carefully analyzing the test error, we can upper bound the test error in terms of n SNR? (see details in Appendix D.2).
Model and training settings. A two-layer CNN (as defined in Section 3) is trained using gradient descent, with total of T = 200 iterations and a learning rate of 1) = 0.1.
The Two-Stage Picture Emerges in the Feature Learning Process with Label Noise. Specifically, we demonstrate the signal learning process in the two-layer CNN by showing how maxj,r 7j.r changes during training. We also present the noise memorization process by illustrating the evolution of maxj,r Pj.rú In Figure I (left), a clear two-stage pattern is observed in the learning process:
6. Experiments
In this section. we provide empirical evidence under both synthetic and real-world setups to support our theory.
6.1. Synthetic Experiments
First, we conduct experiments under the synthetic setup.
Stage I. The values of maxj. Tirr are significantly larger than those of max3.r Pj.r,i, indicating that the signal learn ing initially dominates;
Synthetic Setup with Label Noise, We follow precisely the problem setup introduced in Section 3:
SNR. The fixed signal vector is set to be μ [yzr, 0,... 0 E dRd, where 20 and d = 2000, and the random noise vector & is sampled from from,V(O, (0, This setting corresponds to n SNR" 20.
Stage IL. The values of max,,r Pj.ra on noisy sam- ples (i.e., when y/ + (i)) increasingly surpass those of maxj.r Ti. implying that the noise memorization pro- cess, particularly for noisy samples, gradually takes over.
Label noise. The n = 100 training samples is generated with balanced class labels and each sample's 's label is flipped with a probability of 0.1.
Additionally, we provide the training accuracy curves. In Figure 1 (bottom, left), the accuracy on noisy samples ini-
7

---

On the Role of Label Noise in the Feature Learning Process
Accuracy curves
Feature Leaming Process w/ Label Noise
1,0
0.8
0.6
Acc w/o label noise
0.4
Acciva label
Accn auo w/ label
Acco
120 160
1.0
0.8
0.6
0.4
0.2
ACC label
Acco.. w/ label noise
0.0
0
40
80
120
160
Egoch
Epoch 41
Epoch
Epoch 121
Epocht
Figure 2: Experimental validation in real-world scenarios. Two VGG nets trained on the first two categories of CIFAR-10 under nearly identical settings. One is trained with label noise and the other without. (Left) The accuracy curves for the two models. Here, AcCD... and Acep... represent the accuracy on the entire training and test sets, respectively, while AcCD.in..eo and ACcD,in way specifically denote the accuracy on clean and noisy samples from the training set. (Right) Visualization of model predictions (via SHAP (Lundberg & Lee, 2017)) for noisy samples across multiple epochs. Red regions indicate positive contributions model predictions, while blue regions denote negative contributions, with darker regions signifying greater contributions. More experimental results in Appendix F.
tially drops to 0 during the early stage and then gradually increases, as predicted by our theory in Section 4.1
stochastic gradient descent (SGD) samples from the first two categories of CIFAR-10, where each sample's 's label is flipped with probability of 0.2. Similar to the synthetic experiment, for comparison, we also train another VGG net under the same settings but without label flipping.
Synthetic Setup without Label Noise. For comparison, we also train a baseline model under nearly identical settings but without label flipping.
The Two Stage Picture:
Accuracy. Accuracy curves demonstrate the two-stage picture with label noise in real- world scenarios. In Figure 2 (left), when training with label noise, the accuracy noisy samples follows a similar two- stage pattern to the synthetic experiments- - an initial drop followed by a gradual increase to - while the test set accuracy remains consistently lower than when training without label noise. In comparison, when training without label noise, the accuracies on both training and test sets consistently increase during the training.
Signal Learning Dominates in the Feature Learning Pro- cess without Label Noise. Similarly, focus the evo- lution of signal and noise coefficients. In Figure (top, right), the values of max,,r "ir are larger than those of maxi.r Pj.r,i throughout the training, suggesting that the signal learning dominates the feature learning process. Fur- thermore, in Figure 1 (bottom, right), the training accuracy remains consistently high along the training. These results closely align with our theory in Section 4.3.
6.2. World Experiments
Visualization of the Feature Learning Process. As deep models are black-boxes, we visualize their fcature learning process using post-hoc inter- pretability methods. Specifically, we choose SHAP (Lund- berg & Lee, 2017). which interprets model predictions by attributing the contribution of each input variable (e.g., pix- els for image inputs). In Figure (right), it is evident that two-stage behavior emerges. In the first stage (reflected by Epoch and 41), clear patterns are observed in the interpre- tations, such as the wings of "airplane" class and contours of "automobile" class, implying the model relies on the general-
The Two Stage Picture:
Taking a step further, we also validate our theoretical anal- ysis in the real-world scenario. The code for replicat- ing the results is available on httpps://g http//ggttttu..tt// thub. com/ @zp1012/laber -ooteell-oissee www.aabellnonsseeeeeeeeeeee se
Real-World Setup with and without Label Noise. We perform experiments on the commonly used image classi- fication dataset CIFAR-10 10 (Krizhevsky et al., 2009), using the standard network architecture VGG net (Simonyan & Zisserman, 2015). Specifically, train the VGG net with
8

---

On the Role of Label Noise in the Feature Learning Process
izable features for predictions. However, in the second stage (reflected by Epoch 81 and 121), the interpretations appear messy, and the model overfits to the spurious features, such as the noise in backgrounds.
References
Allen-Zhu, Z. and Li, Y. Towards understanding ensem- ble, knowledge distillation and self siff-distillation in deep learning. arXiv preprint arXiv:2012.09816, 2020.
7. Conclusion and Limitations
Allen-Zhu. Z. and Li, Y. Feature purification: How adversar- ial training performs robust deep learning. In 202/ IEFE 62nd Annual Symposium on Foundations of Computer Science (FOCS), pp. 977-988. IEEE, 2022.
In conclusion, our work offers an exact learning dynamies analysis of training neural networks with label noise, We identify two distinct stages in the feature learning process, offering a solid explanation for the effectiveness of tech- niques such as early stopping and sample selection. Our theoretical results, along with sufficient practical insights, are significant contributions that have been largely absent from the deep learning theory literature. addition, experi- ments under both synthetic and real-world setups back up our theory.
Anglunn, D. and Laird, P. Learning from noisy examples. Machine Learning. 2(4):343-370, 1988.
Arora, S., Du, S., Hu, W., Li, Z., and Wang, R. Fine- line-grained analysis of optimization and generalization for overpa- rameterized two-layer neural networks. In International Conference on Machine Learning, pp. 322-332. PMLR, 2019.
Limitations. Our current analysis is limited to random la- bel noise and does not account for data-dependent label noise, where mislabeling probability varies based on sample characteristics. Extending our framework to structured or adversarial noise remains an important direction for future research. Additionally, our theoretical results are derived for two-layer CNN, which, while analytically tractable, may not fully capture the complexities of deeper architectures. Investigating whether our two-stage learning dynamics per- sist in deeper networks with advanced components (e.g.. residual connections, normalization) is crucial for improv- ing robustness.
Arpit, D.,, Jastrzebski, S., Ballas, N., Krueger, D., Bengio, E., Kanwal, M. S., Maharaj, T., Fischer, A., Courville, A., Bengio, Y., et al. A closer look at memorization in deep networks. In International conference on machine learning, pp. 233-242. PMLR, 2017.
Bai, Y., Yang, E., Han, B., Yang, Y., Li, Mao, Y., Niu, G., and Liu, T. Understanding and improving early stopping for learning with noisy labels. Ranzato, M., Beygelz- imer. A., Dauphin, Y., Liang, P., and Vaughan, J. W. (eds.), Advances in Neural Information Processing Sys- lems, volume 34, pp. Inc., 2021.
Curran Associates,
Acknowledgments
Beauchamp, M. On numerical computation for the distribu- tion of the convolution of n independent rectified gaussian variables. Journal de la société française de statistique, 159(1):88-111, 2018.
WH was supported by JSPS KAKENHI Grant Number 24K20848, TS was partially supported by JSPS KAKENHI (24K02905) and JST CREST (JPMJCR2115). This research supported by the National Research Foundation, Singa- pore and the Ministry of Digital Development and Informa- tion under the AI Visiting Professorship Programme (award number AIVP- 2024-04). Any opinions, findings and con- clusions or recommendations expressed in this material are those of the author(s) and do not reflect the views of Na- tional Research Foundation, Singapore and the Ministry of Digital Development and Information.
Bu, D., Huang, W., Han, A., Nitanda, A., Suzuki, T., Zhang, Q., and Wong, H.-S. Provably transformers harness multi- concept word semantics for efficient in-context learning. Advances in Neural Information Processing Systems, 37: 2024.
Cao, Y., Chen, Z., Belkin, M., and Gu, Q. Benign overfit- ting in two-layer convolutional neural networks. arXiv preprint arXiv:2202.06526, 2022.
Impact Statement
Chatterji, N. S., Long, P. M., and Bartlett, P. L. When does gradient descent with logistic loss find interpolating two- layer networks? Journal of Machine Learning Research, 22(159):1-48, 2021.
This paper presents work whose goal is to advance the field of Machine Learning. There are many potential societal consequences of our work, none which we feel must be specifically highlighted here.
Chen, J., Zhang, R., Yu, T., Sharma, R., Xu, Z., Sun, T., and Chen, C. Label-retrieval veetrieval-augmented diffusion mod- els for learning from noisy labels. In Oh, A., Naumann, T., Globerson, A., Saenko, K., Hardt, M., and Levine, S.
9

---

On the Role of Label Noise in the Feature Learning Process
(eds.), Advances in Neural Information Processing Sys- Tems, volume 36, pp. 66499-66517. Curran Associates, Inc., 2023a.
Ghorbani, B., Mei, S., Misiakiewicz, T., and Montanari, A. When do neural networks outperform kernel methods? Advances in Neural Information Processing Systems, 33: 2020.
Chen, Y., Huang, W. Zhou, K., Bian, Y., Han, B., and Cheng, J. Understanding and improving feature learning for out-of-distribution generalization. Advances in Neu- ral Information Processing Systems, 36:68221-68275, 2023b.
Han, A., Huang, W., Cao, Y., and Zou, D. On the feature learning in diffusion models. arXiv preprint arXiv:2412.01021 2024.
Han, B., Yao, Q. Yu, X., Niu, G., M., Hu, W., Tsang, I., and Sugiyama, M. Co-teaching: Robust training of deep neural networks with extremely noisy labels. In Bengio, S., Wallach, H., Larochelle, H., Grauman, K., Cesa-Bianche N., and Garnett, R. (eds.), Advances in Neural Information Processing Systems, volume 31. Cur- ran Associates, Inc., 2018
Chen, Z., Zhang, J., Kou, Y., Chen, X., Hsieh, C.-J., and Gu, Q. Why does sharpness-aware minimization gener- alize better than sgd? Advances in neural information processing systems, 36, 2024.
Chidambaram, M., Wang, X., Wu, C., and Ge, R. Provably learning diverse features in multi-view data with mid- point mixup. In International Conference on Machine Learning, pp. 5563-5599 PMLR, 2023.
Han, B., Niu, G., Yu, X., Yao, Q., Xu, M.. Tsang, I., and Sugiyama, M. Sigua: Forgetting may make learning with noisy labels more robust. In International Conference on Machine Learning, pp. 4006-4016. PMLR, 2020.
Chizat, L., Oyallon, E., and Bach, F. On lazy training in dif- ferentiable programming. In Wallach, H., Larochelle, H., Beygelzimer, A., d'Alché- Buc, F., Fox, E., and Garnett, R. (eds.), Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019a.
Han, Y., Han, A., Huang, W., Lu, C., and Zou, D. Can diffusion models learn hidden inter-feature rules behind images? arXiv preprint arXiv:2502.0472 2025.
Chizat, L., Oyallon, E., and Bach, F. On lazy training in differentiable programming. Advances neural informa- tion processing systems, 32, 2019b.
Hornik, K., Stinchcombe, M., and White, H. Multilayer feedforward networks are universal approximators. Neu- ral networks, 2(5):359-366, 1989.
Damian, A., Lee, J., and Soltanolkotabi, M. Neural net- works can learn representations with gradient descent. In Conference Learning Theory, pp. 2022.
Hu, W., Xiao, L., Adlam, B., and Pennington, The sur- prising simplicity of the early-time learning dynamics of neural networks. In Larochelle, H., Ranzato, M., Hadsell, R., Balcan, M., and Lin, H. (eds.), Advances in Neural Information Processing Systems, volume 33, pp. 17116- 17128. Curran Associates, Inc., 2020.
PMLR,
Frei, S., Cao, Y., and Gu, Q. Provable generalization of sgd-trained neural networks of any width in the presence of adversarial label noise. In International Conference on Machine Learning, pp. 3427-322443 3438. PMLR, 2021.
Huang, W., Cao, Y., Wang. H., Cao, X., and Suzuki, T. Graph neural networks provably benefit from structural in- formation: feature learning perspective. arXiv preprint 20w:23306.13226 2023a.
Frei, S., Chatterji, N. S., and Bartlett, P. Benign overfitting without linearity: Neural network classifiers trained by gradient descent for noisy linear data. In Loh, P.-.. and Raginsky, M. (eds.), Proceedings of Thirty Fifth Confer- ence Learning Theory, volume 178 of Proceedings of Machine Learning Research, pp. 2668 2703. PMLR, 02-05 Jul 2022.
Huang, W., Shi, Y., Cai, Z., and Suzuki, Understand- ing convergence and generalization in federated learning through feature learning theory. In The Twelfth Interna- tional Conference Learning Representations, 2023b.
Huang. W., Han, A., Chen, Y., Cao, Y., Xu, 7.., and Suzuki, T. On the comparison between multi-modal and single- modal contrastive learning. Advances in Neural Informa- tion Processing Systems, 559--86605, 2024.
Funahashi, K.-I. On the approximate realization of continu- ous mappings by neural networks. Neural networks, 2(3); 183-192, 1989.
Geiger, M., Spigler, S., Jacot, A., and Wyart, M. Disentan- gling feature and lazy training in deep neural networks. Journal of Statistical Mechanics: Theory and Experiment, 2020(1 1): 13301, 2020.
Izmailov, P., Kirichenko, P., Gruver, N., and Wilson, A. G. On feature learning in the presence of spurious correla- tions. Advances Neural Information Processing Sys- tems, 35:38516-333 2022.
10

---

On the Role of Label Noise in the Feature Learning Process
Jacot, A., Gabriel, F., and Hongler, C. Neural tangent ker- nel: Convergence and generalization in neural networks. Advances in neural information processing systems, 31, 2018.
Liu, S., Niles-Weed J., Razavian, N., and Fernandez- Granda, C. Early-learning regularization prevents memo- rization of noisy labels. In Larochelle, H., Ranzato, M., Hadsell, R., Balcan, M., and Lin, H. (eds.), Advances in Neural Information Processing Systems, volume 33, pp. Curran Associates, Inc., 2020.
Jelassi, S. and Li, Towards understanding how momen- tum improves generalization in deep learning. In Interna- tional Conference Machine Learning, pp. 9965-10040, PMLR, 2022.
Liu, Z., peitian, Chen, D., Pei, W., and Ma. Q. Scale- teaching: Robust multi-scale training for time series clas- sification with noisy labels. In Oh, A., Naumann, T., Globerson, A., Saenko, K., Hardt, M., and Levine, S. (eds.), Advances in Neural Information Processing Sys- Curran Associates,
Jelassi, S., Sander, M., and Li, Y. Vision transformers provably learn spatial structure, Advances in Neural In- formation Processing Systems, 35:37822-37838 2022.
tems, volume 36, pp. 33726-33757. Inc., 2023b.
Jiang, J., Huang, W., Zhang, M., Suzuki, T., and Nie, L. Un- veil benign overfitting for transformer in vision: Training dynamics, convergence, and generalization. Advances in Neural Information Processing Systems, 37:135464- 135625, 2024.
Lundherg, S. M. and Lee, S.-I. unified approach to inter- preting model predictions. In Guyon, I., Luxburg, U, V., Bengio, S., Wallach, H., Fergus, R., Vishwanathan, S., and Garnett, R. (eds.), Advances in Neural Information Processing Systems, volume 30. Curran Associates, Inc., 2017.
Kalimeris, D., Kaplun, G., Nakkiran, P., Edelman, B., Yang, T., Barak, B., and Zhang, H. Sgd on neural networks learns functions of increasing complexity. In Wallach, H., Larochelle, H., Beygelzimer, A., d' d'Alché-Buc, F., Fox, E.,, and Garneut, R. (eds.), Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019.
Ma, X., Wang. Y., Houle, M. E., Zhou, S., Erfani, S., Xia, S., Wijewickrema, S., and Bailey, J. Dimensionality-driee learning with noisy labels. In Dy, J. and Krause, A. (eds.), Proceedings of the 35th International Conference Ma- chine Learning, volume 80 of Proceedings of Machine Learning Research, pp. 3355-3364. PMLR, 10-15 Jul 2018.
Kou, Y., Chen, Z., Chen, Y., and Gu, Q Benign overfit- ting in two-layer ReLU convolutional neural networks. In International Conference on Machine Learning, pp. 17615-17659, PMLR, 2023.
Meng. X., Zou, D., and Cao, Y. Benign overfitting in two- layer relu convolutional neural networks for xor data. arXiv preprini arXiv:2310.01975, 2023.
Krizhevsky, A., Hinton, G., et al. Learning multiple layers of features from tiny images. 2009.
Patrini, G., Rozza, A., Krishna Menon, A., Nock, R., and
Qu, L. Making deep neural networks robust to label noise: A loss correction approach. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 1944-19522 2017.
Li, H., Wang, M., Liu, S., and Chen, P.-Y. A theoretical understanding of shallow vision transformers: Learning, generalization, and sample complexity. arXiv preprint arXiv:2302.066115, 2023.
Rumelhart, D. E., Hinton, G. E., and Williams, R. J. Learn ing internal representations by error propagation, parallel distributed processing, explorations in the microstructure of cognition, ed. de rumelhart and j. mcclelland. vol. 1. 1986. Biometrika, 71(599-607):6, 1986.
Li, M., Soltanolkotabi, M., and Oymak, S. Gradient de- scent with early stopping is provably robust to label noise for overparameterized neural networks. In International conference on artificial intelligence and statistics, pp. 4313 4324. PMLR, 2020.
Sagawa, S., Raghunathan, A., Koh, P. W., and Liang, P. An investigation of why overparameteerization exacerbates spurious correlations. In International Conference on Machine Learning, pp. 6346-8356 PMLR, 2020.
Li, Y., Wei, C., and Ma, T. Towards explaining the regu- larization effect of initial large learning rate in training neural networks. In Advances Neural Information Processing Systems, pp- 1 11674-11685 2019.
Simonyan, K. and Zisserman, A. Very deep convolutional networks for large-scale image recognition. In Bengio, Y. and LeCun, Y. (eds.), 3rd International Conference on Learning Representations, ICLR 2015, San Diego CA, USA, May 7-9, 2015, Conference Track Proceedings, 2015.
Liu, C., Abedsoltan, A., and Belkin, M. On emergence of clean- priority learning in early stopped neural networks. arXiv preprint 206.2236..02333, 2023a.

---

Yu, X., Han, B., Yao, J., Niu, G., Tsang, I,, and Sugiyama, M. How does disagreement help generalization against label corruption? In Chaudhuri, K. and Salakhutdinov, R. (eds.), Proceedings the 36th International Conference on Machine Learning, volume 97 of Proceedings of Ma- PMLR, 09-15 On the Role of Label Noise in the Feature Learning Process
Singla, S. and Feizi, S. Salient imagenet: How discover spurious features in deep learning? arXiv:2110004301, 2021.
Zou, D., Cao, Y., Li, Y., and Gu, Q The benefits of mixup for feature learning. In International Conference Ma- chine Learning, pp. 43423-43479, PMLR, 2023.
Tanaka, D., Ikami, D., Yamasaki, T., and Aizawa, K. Joint optimization framework for learning with noisy labels. In CVPR, 2018.
Tu, Z., Aranguri, S., and Jacot, Mixed dynamics in linear networks: Unifying the lazy and active regimes. In The eighty- Anmual Conference Neural Information Processing Systems, 2024.
Vershynin, R. High-ddiensiooal probability: An introduc- fion with applications in data science, volume 47. Cam- bridge university press, 2018.
Woodworth, B., Gunasekar, S., Lee, D., Moroshko, E., Savarese, P., Golan, I., Soudry, D., and Srebro, N. Kernel and rich regimes in overparamettizee models. In Aber- nethy, J. and Agarwal, S. (eds.). Proceedings of Thirty Third Conference on Learning Theory, volume 125 of Proceedings of Machine Learning Research, pp. 3635- 3673. PMLR, 09-12 Jul 2020.
Xia, X., Lu, P., Gong, C., Han, B., Yu, J., Yu, J., and Liu, T. Regularly truncated m-estimators for learning with noisy labels. IEEE Transactions on Pattern Analysis and Machine Intelligence, 46(5):3522-3534) 2024. doi: 10.1
Xu, Z., Wang, Y. Frei, S., Vardi, G., and Hu, W. Benign overfitting and grokking reLU networks for XOR clus- data. In The Twelfth International Conference on Learning Representations, 2024.
chine Learning Research, pp.
Jun 2019.
Zhang, C., Bengio, S., Hardt, M., Recht, B., and Vinyals, O. Understanding deep learning (still) requires rethinking generalization. Communications of the ACM, 64(3):107- 115, 2021.
Zhou, C., Ma, X., Michel, P., and Neubig, G. Examining and combating spurious features under distribution shift. In International Conference on Machine Learning, pp- 12857-12867, PMLR, 2021.
Zou, D., Cao, Y., Li, Y., and Gu, Q Understanding the generalization of adam in learning neural networks with proper regularization. arXiv preprint arXiv:2108.1137. 2021.
12

---

On the Role of Label Noise in the Feature Learning Process
A. Comparison of Technical Quantities to (Kou et al., 2023)
Among the various differences in conditions compared to (Kou et al., 2023), the most critical distinction lies in the scale of the SNR. Because we aim to characterize the two-stage behaviors induced by label noise, we require the SNR to satisfy SNR² (1). This enables the signal learning dominate the noise learning in the first stage while noise learning dominates signal learning in the second stage. Such distinct two-stage dynamics cannot be captured by (Kou al., 2023) due to n SNR = o(1).
More specifically, in the following, we explicitly compares the key differences in the analysis techniques compared to (Kou et al., 2023):
Non-Time- Time-invarian coefficients: One of the key techniques (Key Technique 1 in (Kou et al., 2023)) is the derivation
(6) of time-invariant order of the coefficient ratio: (4) E Piana @SSNR²). which is critical for their generalization analysis. However, in our case, due to the setting of constant order n SNR?, the noisy samples exhibit different behaviors as the clean samples (which is the main goal we wish to show), such time-invariance may not hold for all iterations.
Non-balancing of the updates: Another key technique employed in (Kou et al., 2023) is the automatic balancing of coefficient updates, which requires show //th/ /e(()) < C for all i [n]. That is, the loss derivatives across all samples are approximately balanced, which is critical for their convergence analysis. Because in our case n. SNR?, the loss derivatives of noisy samples may be significantly larger than that of clean samples, we cannot guarantee the balance of updates across all samples.
Without the above two results in our case, the convergence and generalization analysis becomes challenging, To address the challenges, we require developing novel techniques via refined analysis on clean and noisy samples, which cannot be addressed in the prior works.
To better comprehend the differences to the analysis of (Kou et al., 2023), present the following tables that compare the different quantities at each training stage. These differences require non-trivial analysis.
First Stage
Second Stage
(Kou et al., 2023)
Monotonic increase
Monotonicity of signal
Our work
Monotonic increase
No monotonicity
(Kou et al., 2023)
Noise dominates
Signal-noise magnitude
Our work
Signal dominates
Noise dominates
(Kou et al., 2023)
L P 2nr (1)
Determining factors of SJ(( (WW xx)
+ P ()) + =()),
i S,
Our work
Tur
Sutt - ) + o(1),
(t)
i Sy
m0
(Kou et al., 2023)
(cf(W()) x:) 2 20.i [M]
Prediction
(us(W xx) 2 0, S
Our work
i if(()) x.) Vi [n]
(uS(WC) xx)
S0
[o().
if 11
C- C-lood
(Kou et al., 2023)
12(1),
if p
S Chofd
Test error L. (W()))
Our work
o(1)
2(1)
Table 2: Comparisons of key quantities in the analysis at each stage.
B. Preliminary Lemmas
This section introduces a few lemmas that are critical to bound the parameters at initialization.
Lemma B.1 (CCao et al., 2022; Kou et al., 2023)). Suppose d = 2(log(6n//)) (6)). Then with probability at least - 5,
d/2 < |1 s d
13

---

On the Role of Label Noise in the Feature Learning Process
Ke,, Ez) s 20 loggd ((...)) & || 2lgg(6n/5)
Lemma B.2 (CCao et al., 2022; Kou al., 2023)). Suppose that s2(log(nm/0)) m ()(log(16)). Then with probability least 1 6.
ogd/2 < |w j.r 1 - 3
(( Jir ا S V2log T 2
k( j.r
10
Et) - 2/log(12mm) 6). oboe Vd.
Lemma B.3 ((Kou al., 2023)). Let (/ fr E [m] (w i Ei) 0} and S {i [m] ; yr (w j.r: (.) 0}.
Then for any 8 > 0, and m 2 50 log( (og(4//)), n 2 32 log 0), have with probability at least 6,
18:00 0.4m, 15/0 2 n/8,
Vi [n]]
Vj =1, [ml]
C. Analysis with label noise
Without loss of generality, for the subsequent analysis, we assume |S| n (1-7+ |S| i SinSyl=
Tam
2 11-1 n
(1-T- |
2
C.1. Coefficients Decomposition Iteration
(0) Lemma C.1. The coefficients Yir Pirii (1)) in decomposition (3) satisfy 22 P.0. p00) ij..
(t) (1)
0 and admit the following
iterative update rule:
n "
(1+1) (t)
(00 0 ((w(())
(1) M. 11
G5r 7
nm
11
((()) o' d''(w y.r ( 1 j),
Pjjrtt
nm
((+1)
210) + nm
11 ((0) d'w j.r. 1E (0: -)).
Proof of Lemma C.I. By iterating the gradient descent update, we can show
(0)
20 (w (w
j.r
s=0
1=1
==0
Because E., la are linearly independent almost surely for E [n]. Then from the definition:
w 1.00 + + 1012 4 +
(4)
Σ
j.r
there exists unique decomposition as
(8)
((((W))) 3 3:44)) pal3
3.
nm
1-1
(0)
d d((w
Pj.r
mm
14

---

On the Role of Label Noise in the Feature Learning Process
By definition of Pl S.
and the fact that & S O,
19)
(+) o' E = 5)
Pj
Tum
00
o' (e) jor 1:
Then the iterative updates of the coefficients follow directly.
C.2. Scale of Coefficients
Here we start to provide a global bound for the decomposition coefficients. We show for a sufficiently large number of iterations T = D oo 2). the scale the coefficients can be upper bounded up to some logarithmic factors.
We consider the following definition:
SNR ||||||
B = 2 max (w (0) f,J.r J.r (w (0)
J.r &.),,,
a = C2 log(T")
OF Vevd
for some constant C. > to be determined later. dg max V log(12m/6)) 112 2 (0og(1mm/88)0mm vd).
Then by Lemma B.2, we can bound as 3 S
We next provide the main proposition that bounds the scale of coefficients.
Proposition C.2 (Restatement of Proposition 5.2). Under Condition 1.1, for any 0 < S T
0 S p/ S a,
(4)
log( (2(66n/))
0 > (t) 2 -3 -3-10p
d nox 2 -0,
(5)
0 5 7j s &Caa
(1)
(6)
for some constant C > O.
We aim to prove Proposition C.2 using induction. This requires several intermediate lemmas through the induction process.
Lemma C.3. Under Condition 4.1, suppose (4), (5), (6) hold at iteration t. Then for all r E [m]. j E {+1}, i e [n].
8log(6n/)) no,
Kw (1) jrr
- 14) -j 1. S SNRV
d
log(Gn2/0) (w jrr ( - -pgg. < 5V
(0)
d na, 0
1og(6n2/00 (0)
kw (1) (0)
E.) (00) 5y
d na, 0 = -j
Proof of Lemma C.3. From signal-noise decomposition (3),
(w (8)
jir 14) j. -- Pani || (E: 2. 14)
(0)
Σ
(0) Jana
||E:ll22 (EE, m2)
j.r.al + (ef0):1) 11:11122 IKEs, 14)1
log (6n/ / /))
SNR
(1750ral + +1(())
d
llog(Gn/B)
< SNR
na
d
15

---

On the Role of Label Noise in the Feature Learning Process
where the second inequality is due to Lemma B.1 and the last inequality is by (4), (5). The second inequality follows similarly.
Then, for 81 = j. we have p(0) jir,i
= 0, vt 2 and hence
k(
jir w w.r: Ei) - -Pf.h.al
(1)
= 2.3. ||pe|12" (H.EE)) + Σ Pare |15x (
(1)
Ee) + Eegn 11Ev1112 (E,,
84
- 11al12? 10,, E:\l -11,511 +
(12 + (e |1::1122 KKvv,
2 2log(6n/6)
log(6n2 (8)
- S
d
Cyna + AV
d
na
1og(6n2/0) d
s (2C,SNR + 1)
na
(ogg6n///)
s <bV
d
where we use Lemma B.1 and (6) in the second inequality. In the third inequality, we use log(6n/0)) < 1log(6n2/0)) In the fourth inequality, we note that the condition on SNR ensures that SNR = @(1/V)).
For yJ # j. the proof follow exactly the same strategy as for y = j and hence is omitted.
Lemma C.4. Under Condition 4.1 and suppose (4), (5), (6) hold at time t, then there exists a sufficiently large constant 1 > O such that
1 m
(ogr
(1) ( 1/C, < (/((()) xx) x;)
Σ
(4)
+ 1/C1 when E Se
m
m
Pund ( 1/C1 S i.((w()) xx) 5
1
(p Birr.s ---prr) + +1/0
when i E S
Proof of Lemma C.4. We first see
sec
J. (W x.) x,)
Σ
Ts J. (wwwS/huuii + o( ((w
m
J.r
(o((w mu va11)) + ((w ss.r Ei))
(1)
1 Σ (a((w 9.11)) + +
B.. 01.ro E:)).
Recall from the gradient descent update and Lemma C.3,
(( (1) p1) (w (0) g.r: 11) - -1.7501 =SNR
$log(6n// (6n/ (
na
Then it can be verified that when y = Yis
8 log (6n/8) na
(w(() g..rt Voft) S <((w(0) (0) gorrt
p1) + 7g.rr + SNR
(0)
d
(w( We.r ya S (( p p1)l
-0 -
log (6n6)) na
+ SNR
d
8 Slog 6n/6)
< (w S..
(0)
m1) + SNR
na d
16

---

On the Role of Label Noise in the Feature Learning Process
log( (8)
(w ( Ei) S (w We.r Ei)l +
((0))
Miii + 5V
na
d
(w Da yi 2 --uur
bur - |w -B,rr 14| - -SNR
log (6n/0)
d na
Using these inequalities, we can upper bound when Vi = yi, i.e., i S..
(:S(W() xi)
(a((w (4)
Dirrs Bill)) + ao((( R.r (i))
(1)
m
T7
(7gh.r + po..r)) + + + Ō(aa /V)) 772
1
(o + + + 1/02
m
where we use Lemma C.3 and the Condition 4.1 where we choose a sufficiently large C1. Similarly, we can lower bound
f
x2)
2 m Σ (1ge) + +(blrr)) - 1/C1
On the other hand, when üs + yi, it can be shown that
8 (0g(66/))
Blog(6n/ (6n/6) na
(w (t)
Wirr Vilte) S (w (0)
u2)1 - 7 + SNR
-00 (0)
na S
(( Be.rt
B.rr u1) + SSNR
Beirt
d
(w Ne Bife) S 1(w 1: 11)1 + 7 + SNR
8 log (6n/
d n0
(w Di.ri vi14) 2 --ber
Bi.r - l( (0)
Birri 14)1 - S
8 log (6n/6) 11CK
d
loog (e((6n2//) /5)
(w (t) E,) S (1)
Bi.rss + 1(w! (0)
Be.r <i) + =5/
1a
d
where we notice 1ir 2 0.
Then we can upper bound when ã * yi as
0ef (W(( x,) x
(o((w!))
Burr bipt)) + ((w
(1)
bi.r:
(1)
Ei))
o (w (t)
Burt Vitt))
8 8log(6n/0)
Dog(6n? (62/1) Cpn
< 3 + SNR
Con
(1)
Marra + +5V
d
d
1 m
8 8log(6n/88
1( (0)
Birr ViHte) SNN
Opn
Brr
m
m
m
--. + 1/C1
(1)
m
where the second inequality uses Lemma C.3 and last inequality is by the Condition 4.1.
Similarly, we can lower bound J. (W(()) x;) as
j.(W xx:)
x:)
1 Σ
a((w
s..r. El)
Σ
(a((w (2) (g.r Wi11)) + (( -g. (.)))
m
17

---

On the Role of Label Noise in the Feature Learning Process
T7
(P
(t) Piin
- 1/O1
m
where we use Lemma C.3.
Lemma C.5. Under Condition 4.1 and suppose (4), (5), (6) hold at time t. If max Sip O(1), we have J.f(W(o xx) = (()) and ( = (1) for all E [n]]
Proof of Lemma C.5. The proof trivially from Lemma C.4 and the definition of loss. Specifically, we denote the upper bound as C". For E St, by Lemma C.4,
1
1
exp 1/ Σ (7 +bo.r.)) 1/C1) + exp(ixf(W()) x,))
(1)
1 1+ exp(2C" +000"+1//0" 1/C1)
i E Sy. by Lemma C.4,
1
+ (xpp (WO) x.))
1 + exp
(1 >m
( (-7 7 7-p.r jrr +Ponr.d 1/C1)
(1)
(1)
m
1
1 1+ exp(C" + 1/C1) 1+ exexp(2C" 1/Cr)
where the second inequality is by y-g.r 2 Thus for all i E [n]. we can show that |,,00) 2 e1+ + +C
Recall s(x) = {r E [m] : (w
Si Ei) 0} and 5/:P- = (i E [m] : y = J. (w/ Ex) > 0}.
The next lemma shows that in the first stage where the loss derivatives can be lower bounded, the inner product between weights and noise is increasing.
Lemma C.6. Under Condition 4.1 and suppose for any t TT, (4), (5), (6) hold for all S tt. Then show
5 C c 500 C 5
for any 8 S. t.
Proof of Lemma C.6. The proof is by induction where we separately consider two stages. First t 0, it is trivial to verify that both claims hold. In the first stage where maxj.r. (t) (t)
j. = O()), we can lower bound the loss derivatives by a constant according to Lemma C.5, i.e., 1 2 C. for all i E [n]. Let Ti be the termination time of the first stage. Suppose there exists time < Ti such that the claims hold for all s S f 1, we now prove also holds at f.
By the gradient descent update, for any s have S f 1) and thus
1 (w ns Ex) (w
(f-1)
(i-1) o' ((w (x)) (Ei,Er)
E.) mm
ju.r
(ī-1) 1)
o' a'((W (epp)) Ei)
(T-1)
==1
=(w]
(F-1) 1)
E.)
(1 1
1) of d'(( Jear
(F-1)
Ex))
(E Ev)
Tu
A1
A2
( (1-1) 1)
o' <(w (I-1)
T077L
Ag
18

---

On the Role of Label Noise in the Feature Learning Process
We respectively bound each term follows.
2 num
(T- 1)
do
A
min iE(m
2nm
where the last inequality is by Lemma B.1.
For A2, we can upper bound its magnitude
|A2| -
Ke Ev)
21 oe V /llogGnn2///
m
where the first inequality is by | S for all t and the second inequality is by Lemma B.I. For Ag. similarly, we can bound
10,, Gi " 11lu41200 v 2 loo((6n/0))
Aal S 2 m
m
where the second inequality is m3x ?n 1og(6n2/0)) 20," =211 22 log(( (oog(6n/8)) (n/ we can show A 2 max [A2//2, /2, |Aal/2] and thus
again by Lemma B.I.
By requiring d
2
(w 1 Murt Ei) = (w 0ur
(f-1)
Et) 2 (w (f-1) E A A22
{w (f-1) y.r
As
.E:) >
s.r
for all s((-1) Thus, s and o f s(i
c ss
For the other claim, we follow similar strategy as above. For i E 5/ we have by induction condition that i Sft and thus for j = yj
(w j.r E.) = -(W] (7-1)
((-l) d' ((w) (t))) (Ei,Er)
Ei) mm
j.r
(i-1) ((w) j.r
((w$(") (i-1)
(1 .yr (ye 1, E.)
nm
Following the same analysis, we can show (w (w/ j.r {.) 2 (w) (i-1)
j.r .Ei) > 0 and thus i E 500 and s S s(i-1) c S
Now at the end of the first stage where Pj.. 211 for all j = - E 5: Then we continue the proof by induction.
(T))
Suppose there exists a time 2 Ti such that for all Ti < 3 Es<i s- 1, P..r. 2 Cp for some constant C,2 > 0. Then by the
update of Pjr,, we can show for j = Jar E S
Pj..i = (i-1)
i
7 5000 d'((([]]]] j.r E PArs 2 Cp
(T-1)
nm
where we notice that (1) > 0. Then we can show from Lemma C.3
log(6n2/1 (8)
( j.r E.) 2 p/ (w) (0) E.) 5v d nax 2 1/C'/C'
where we use the condition on d to be sufficiently large and choose C' > 1/Cp-
Thus we have for r E (() and thus
5:0) C s(t--)) C s(i) For the other claim, we can use the same argument.
Next, we proceed to prove Proposition C.2.
19

---

Ing(6n2 (8) On the Role of Label Noise in the Feature Learning Process
Proof of Proposition C.2. We prove the claims by induction. is clear that at / 0, all the claims are satisfied trivially
'/r j.r,6 Lir,, = 0 for all j. r, é. Suppose there exists T < T such that the results in Proposition C.2 hold for all time S T -1 1. Then we have Lemma C.3, C.4, Lemma C.6 hold for all T
given [0)
Now we show that the results in Proposition C.2 also hold for t = T.
(I) We first show p(t) j.r.
2- -3 V
log 1 (622 /8)
na. When /ff-1) S -0.53 - 5V
log(6n2 /8)
d na, by Lemma C.3, we have
j,r,
Eii + 5/ 1og(6n2/0)
(w(f-)) 10
1), Ei) S 1/rr')) + 1(
(0)
d na < 0
j.r
and this suggests
( ((f-1)= + nm
p(f
11 i ((T-1)-'((W!! (T-1) (
- _),r,
(1-
log (6n2
2 - - 100
d na
On the other hand, when o (1-1) 2 -0.3 - 5v 100(0n2/8) /8)
na.
d
0 g e(fi-1)
"1
N(T-1)
1) of ((w (T-1)
11 3n0
nm
2 0.53 5/
Cpm-
d
2nm
log (e(66n2 (6n2//) 10) 0.53 10
Can
log Bog(Gn2/0) Cpn
2 3 - 100
d
where we use Lemma B.I in the first inequality. The second inequality is by the condition on 7) such that 5 (noodd(2nm)) This completes the induction for the result on L).rs
Opn 2
d
(2) 2 0. Towards this end, we separate the analysis in two stages. In the first stage, the loss derivatives (2) We next prove 7j.r
can be lower bounded by constant, i.e., 1,(00 > Ce for all E [m]] Recall the update rule for 7).r is
11-
(T-1) (T-1) 1) o' (ww (w )v: 11111/3
nm
(1-1 When (w (f-F-) 11) 2 we can show
11)
17
(T-))) 1112
1.
mm
iES:NS1
iES,NS:
2 7/r
11-1
n
1-
T+
Ce
T=)
||m1|
11m
2
2
(1-1)
2 7/r
20 0
where in the first inequality, we uses C2 S 11,00) Similarly, when (w (T-) 1)
<
The second inequality is by the choice 7 S
Ci C241
11) < 0, we have
( 11-
17
((T-1)) |114
Tor 7ir
nm
iES,nS_1
iESyns_1
20

---

On the Role of Label Noise in the Feature Learning Process
(T-1)
1
1
Ce
|
1m
2
(T-1)
2 7jr
2 0
where we choose T- S
Ce CC+T
In the second stage, prove the claim by contradiction. First, without loss of generality that (w j.rt pe) 0, and we write the update as
(1+1)
(6)
17
Σ
35r = Vjr
Tmm
iES:nS,
VESyNS,
-grr + 1
Σ
1 exp (W:((W(), x:)) ) 1
1 exp (W:((W()), x:))
iESinS;
iESynS,
(0) Suppose at an iteration 1, A4 < O, which leads to a decrease in the "j.r Then by Lemma C.4
A4 2 Σ
iES,ns, 1 + exp ( Em= Bur + + + 1/C1)
iESynS, 1 + exp
(1 m B.r, - Do. - 1/C1)
Then we can see the gap between loss derivatives of S, and Sy becomes progressively smaller such that for a given 74 (or
T- when (w( jar (1) S 0) which sufficiently small, A4 > and ((() starts increase.
(3) Next we show upper bound for P Bunr Recall the update rule for (1) Pj.r, is
(t)
(11))
(0) 1 p:(0)
d'((w jar 1
B..r. Beorii
nm
Now suppose tr, be the last time T such that Poinn S 0.5a. Then
(
(1r.))
17 0:00 ( owww Berr (.))
Σ
Burr (E))
Po
Picins
nm
Tm
MASKET
3
(1m.s)
n
Σ
6 (w Buar 1E)12
S
2nm
nm
< 0.5a + 0.25a
7
Σ
((w))
where we apply Lemma B.1 for the first inequality and choose 1) C-'no 2d for the last inequality. Then bound the last term for t E (tr.;; T)
1 + (xp(f.f(W()) xx)) S exp( (xp(-))f(W()).
Next we consider two cases depending on whether i E S, or E Sy.
When E Sg, we can bound by Lemma C.4
0. xx)
1
Σ No.r
P Pyur.))
- 1/C, > m
- Pour. 1/C, > 0.5a 0.1.
p=1
21

---

On the Role of Label Noise in the Feature Learning Process
where the second inequality is by T 2 and the last inequality is by choosing C1 2 10. Then this suggests
(9)
(1) S exp( expp(-://(We) (.S(W()) ,x,) xx)) - Eexp(-0.5a) 2
where the last inequality is by choosing C: 2 2.
When E Sy, we can bound by Lemma C.4
(.f(w())
1
(t) --bir)) - 1/C1 2
1
Binr 1/C, 2 0.5a 0.1.
(0)
m
m
Here we only consider the case when - B.rr,
1 -
(2)
-a.r when deriving the upper bound for
L D P
Bu.tE because otherwise, the loss cannot converge to arbitrarily small as we show later. To see this, (
we suppose 1 Dr
S Em= T-her at termination time. Then for such sample, (.S(W()), xx)) S
1 Er=
(T")
0:. +1/C/ I 0.1 the loss can be lower bounded as ((T") = (e xx)))
log(1 + expl -011) 2 0.6.
Hence we let d=
E (1)
m Σx=
(1) 7-1.r) 1. Then
m
1
T.((W))
x:)
1/6)) 1/01 2 (1- 1/c))..5a (1-1/)0.5 0.1.
Then we have
-4 S exp(- xx))
x:)) S 2exp (1 1/c)0 (301))))0 2
where the last inequality is by choosing C2 sufficiently large. In both cases, (7) can be further bounded as
dd 2
Pi,r, S 0.75a +
T <a
2nm
where the first incquality is by upper bound on the loss derivatives and the last inequality by the condition on Condition 4.1
where 1) S C- C--no-nn "nog" d= S nmog 2d'1/3. 1/3.
(4) Finally for the upper bound on 7g.r
(t)
verify that by the update of ?/.r
((-1)
(1)
17
(() (4) y.
2 0) Σ
200)
(1) 1(w So M.MA 2 20))ll 1
Yj.r
jirr
nm
iES,
iES,
<
1j.r +
(t)
1
VES.
jrr + 1
(1)
$
nmn
iES, 1 exp Em (p + (..) - -/Ca)
Suppose b,, be the last time
< T such that
Tir < 0.5C,, a. Then
(t)
11(2 - T- --------- -1]
S (t..)) 1r
2m
1 cxp(0..C 0.1)
(tz,r) S 1/
+ 11(2 - T- - T T-)111113 T 2xxp(-033C,.,
2m
11(2 T T 1|
(1prr)
< 7i
m
S Caaa
Pjr. 0 and we let C. > 10, 1. The last inequality follows from Condition 4.1 where 77 S '='no=="'"
where notice (1)
-0- < 0.5(2 - T4 - - where the last inequality is by condition on || and d. Thus the
proof is now complete.
22

---

On the Role of Label Noise in the Feature Learning Process
C.3. First Stage
Next we consider first stage of the training dynamics. In this stage, before the coefficients
(e) ((t) 7i.ro P.rr reach a constant order,
we can both lower and upper bound the loss derivatives by an absolute constant, i.e., C. S |c, S Ce. Here we suggests
C 0.49 and C₁ = 0.51 is sufficient to show the desired result.
Before proceed prove Theorem 4.1, provide tighter bound on ||E, and | compared to Lemma B.1 and Lemma B.3 respectively.
Lemma C.7. With probability at least 1 8, we can bound
dd 1 Ō(1/V)))) S 13,13 o2d(1+
Proof. By Bernstein inequality, with probability at least - n, we have ||1: - -z7d = =0 =0(0) VVllog (6n/ Then taking the union bound gives the desired result.
Lemma C.8. With probability at least we can bound
m 1 (01/vm) (m) - |
(0)
m (1 (000m\m
2
2
Proof. Because P((w
(0) Wear
{.)
0) = 0.5, by Hoeffding inequality, with probability at least 8/n, can bound
|s
(og(2n/0
Then taking union bound gives the desired result.
Theorem C.9 (Restatement of Theorem 4.1). Under Condition 4.1, there exists Ti =0 "iin""mog""" 2d- such that
(Ti) (1) for all i E [n]]. r E [m] such that (w (w) Burr
Br.r x,) 2 0.
(Ti) =1(1) for all +1, r [m].
2. 15
3.
(Ti) f all j = +1, e [m], E [n]]
4. All clean samples E St satisfy that ūsf (WT(), ;x;) 2 0.
All noisy samples E Sy satisfy that ÿi. j.f( (T.)), xx))
Proof of Theorem C.9. We first show the lower and upper bound for noise dynamics. For any i E [n] and 5. by Lemma C.6, we know that r E s(0 for all t < Ti. Hence, by the update noise coefficients.
n/Crodd 0.99
(t) Pir
17 (tt 1) 1 Tum
P G.... + 0.99
nmn
YuT
where the first inequality is by Lemma C.7 where we choose ((lo((n/5) sufficiently large and the loss derivative lower bound in this stage. The second inequality is by iterating the first inequality to = 0 and by noticing P = 0. For the upper bound, for E [n].
(0)
nond
gond
(0) Porna Pornd + nm
(
(t-1) Po..d
1.01
< 1.01
nm
nm
where we Lemma C.7 and 1 11
Next, we lower and upper bound the signal dynamics. Recall the update rule for
3g as
(t-1)
(1) o' d'((w!t-) (t-1)
35. 13.r
23

---

On the Role of Label Noise in the Feature Learning Process
(t-1)
17
(1 M(0 d' fr yipl)) - Σ ( o' (o jrr (114e)) 1lal
((-1)
(t-1)
jj.r
Tum
iES.
iESs
When (w
(w
14) 2 O,
jor
(1) (1-1)
17
(1-1))
1ul2
35r 15.
18m
iES,NS,
iESynS,
(t-1)
11
(1 T4 )nCr
T4
|1
mm
2
2
(t-1)
0.49
m
where the first inequality uses the lower bound and upper bound on loss derivatives, i.e., C. S 16 S 1. The second inequality follows by letting T+ I 0.02Cr.
1+C,"
Similarly, when (w " 11) < 0,
(t) 11-1)
Σ (
3ir 75t
iES;NS_1
iES
2
(b-1)
17
-
T- JnCC T_
|1,111
1N
2
2
n n
(t-1)
0.49
m
where we let T- -
0.02Cz
Combining both cases, we can iterate the inequality, which gives
1+C,
mllulBCe, 1- = 0.49 nl1aaBBee
35r 2 7or +
4m
We first show the claim that (W (T:), x,) 2 for i E S.. By the update of signal and noise coefficients, we have for all
any E S,, and r s/O), by, we have E S and thus for all t < Ti,
For the upper bound, we obtain from the signal dynamics that
11-1)
Σ (1)
d' jrr (L-1) -114)) -
(t-1) 1 (0) d' (( (8(1))))))))))))))))))))))))() 1
25. 7jr
iES.
iES,
1 11l T+
$ 1/50-- (t-1)
m
2
17 1
(t-1)
7j.r
2m
7 ا
2m
where we use the upper bound on loss derivative in the first inequality.
Now verify the conditions such that the claims are satisfied. First, we set termination time for the first stage Ti, where
Ti C2n n 2d
for some constant C₂ > 0 to be chosen later. This suggests at the end of first stage, we have
(Ti) P P 2 0.99- C2, for all i E [n] and r E 5
24

---

On the Role of Label Noise in the Feature Learning Process
(Ti)
S 1.01 C2 for all i e [n]-
Vi 2 0.49C2n SNR? for all j = =1, e [m].
(Ti)
(T) dr
0.55Cn SNR² for all = =1, e [m].
Then for all i E St, we have by Lemma C.4,
m
S/WW x.)
(Tger + Brrr)) - 1/C1 2 0.49C2n SNR* + 0.99C - 1/C1 >
where the last inequality is by choosing C1 sufficiently large, e.g., C1 2 (0.99C2) This verifies the first claim of Theorem 4.1.
Second, for all Sy, we have by Lemma C.4,
(.((W())
Bir + ( 1//0 < -0.490 SNR² 1010,077 1/0
where the last inequality is by the choice that C1 2 1000 and
SNR 2.07C, 0.002C
(8)
Under such condition, also verify the third claim of Theorem C.9.
It remains to analyze the condition under which the loss derivative is lower bounded by Cz. In particular, we require
min ( 2 C₁ where
min ie
1,,00
min RES,
+ exp(maxies W: (W(()),,, x;))
1
1 + exp ( Em
(grrr + P (Ti)
(Ti)
p +
1 exp (1.01C²C7 0.502n SNR² 1/C1)
where we denote i = arg ma (.f(((Ti)) x,) and apply Lemma C.4.
Thus ensure miS, (4 2 Ce. we require 1.0102C7 + 0.5Cpn SNR² 1/C1 S log(C, -1), which translates to
SNR2 log 1)C2 2.02C, 0.002C7
(9)
where we choose C 1000.
The final step is to show there exists combination of C2 n SNR2 and Ce such that conditions (8) and (9) are satisfied. For this, we can fix C = 0.4 for example and thus
5.175 + 0.0020 S n SNR? < 0. - 5.05
Then let C2 1/31, we have 5.237 < n SNR² < 5.49. Thus the proof is complete.
C.4. Second Stage
The second stage aims to show convergence of the training dynamics. By the end of the first stage, without loss of generality, we set C2 = 2.1 and we can see
25

---

On the Role of Label Noise in the Feature Learning Process
For all i [n]. r E o we have (T1)
Pi,rr 2 2; (t) For all j = =1, E [m], we have 2j.
S2(n SNR?), where SNR? ((1)
max | - 1/C for some sufficiently large constant C' C>> 0.
In the second stage, we show that in order to achieve convergence in loss to arbitrary tolerance, noise coefficients for noisy samples would first surpass signal coefficients by a large margin. To this end, we first show convergence in the loss function.
First, we let
(0) + 5 llg((2/)) Ei=1
1 ( j). TE:ll
E,
Lemma C.10. Under Condition 4.1, we can show [
W S 0/ d
Proof of Lemma C.10. From the decomposition at Ti, we can show
[W(T)) W Wr S |W(T)
W || + W w
0 (vm))
max 3ir
J.r
(Ti)
2 + O(ym)
max 3.
Pin
&
(Ti) J,r.a
& 113
E:
+0 1/2 log (1/c)0 -d-122 1
O(m SNR 1 + (m 1/2 122 00 0. 1/2)
0(m og d 1/2)
where the last inequality is by SNR (1).
Lemma C.11. Under Condition 4.1, we can show that all Ti St T
(V)(W))) W*) (2/c)
Proof of Lemma C.II. By the gradient decomposition, we can write
De
(VF x;), W
1
BiM) wi.)) + m
Σ
o' ((w (9
jin (u)
= m
ja
3s
1
Σ
o' d'ww (0 (1))
((w (1)
j.r: < (0/00////0////0001111
3.r Vigli
j.r (1 -1 Σ
111
(o (1)
j.rt Us14)) (1o0))0001111))))) (00)))4]12)
3,
1 m
Σ
(1)
θ (oook
2 2 12g/)/ (2/c)
= (2/(
where in the first inequality, we use the expression w and Lemma B.1. The second inequality is by
1 Σ
1 S log(/2 2 (2og(2/e)
lo)g
2
where we use Lemma C.6 and Lemma C.8 that (((0) constant, This completes the proof.
> 0.4m. Further the other terms can be bounded by arbitrarily small
26

---

On the Role of Label Noise in the Feature Learning Process
Theorem C.12 (Restatement of Theorem 4.2). Under Condition 4. I, for arbitrary e O, there exists 1" E T"). where
T O - "mmo 2 )) such that
1. Training loss converges. i.e. (s(W(c)) SE
2. All clean samples, i.e., i E St. it holds that df jif(W()) )x)) 20
There exists a constant < <+'s S 2
I+ such that there are I'n noisy samples, ie., i E Sj satisfy ú: ((W(), (,))) 2 0.
4. The test error 1 2 0.5 min
Proof of Theorem C.12. (1) First, we prove that the loss converges to arbitrarily small tolerance. Specifically, we use Lemma D.4 of (Kou et al., 2023) to bound for all S T", we have
L W 1 0(max[1l1l.
(10)
Then bound the difference in the distance optimal solution
||w(0)
w ((+1) w
W -W) 'IIVV (W
2m
(10)
(.f(W()) x.) - (Vf(W()) x,), w - V>' (W(())
2n
10 (. x.) - log(2/e)) L
n
x:),0: (I(W(),xx))))) 2 (wLs( - TJE - [10(max(|||||p
20
l (s(Wi),
c/2] ('I
n
2 nns ([()) n7c
where the first inequality is due to Lemma C. and the second inequality by convexity of cross entropy function. The third inequality is by (10) and the last inequality is by choosing 1) S C' mmax df -1 be sufficiently small.
Finally, we telescope the inequality from Ti tot T", which yields
1
2
W W 12 TT Ti 1)
Ls (w()))
+ 2c
T T
where the last inequality is due to the choice of 7 = Ti + 1, W((i) - w
Ti + -t
This suggests there exists an iteration E [Ti.T*) where Ls( (W(()) < 2e for any e < 0. By setting e +- 2e, we verify the first claim.
(2) For the second claim, it is easy to see by Lemma C.4, fol E St
ū.f(W
Pari + ((7) - 1/C1 20
where the second inequality is by 7p.r and
2(11 for i [n], r E s. Pg.. P.....
(11)
(3) For the third claim, prove by contradiction that there exists sufficiently large gap C. > 0 such that for noisy samples (t")
i Sy, there exists a constant fraction that satisfies 1 Em (D - 2 C.
m
27

---

On the Role of Label Noise in the Feature Learning Process
We prove this claim by contradiction. Suppose the claim does not hold. Then there must exist constant fraction of samples 7 ((2) I Ce- Formally, We denote the set of such samples as
such that 1 2mm1 (P
I' = E Sy:
(P
Co
DErr 7-
with [T'| = I'n -'n for some constant 7' 0 that satisfies the dataset. Then we have
T'
I+ +++ i.e. upper bounded by the number of noisy samples in 2
12 (J(W xx).
L.s( lss((())=
log(1 + (esp(-0ss(W')) x,)))
n
(E2'
1 m
log
1 exp
Σ
(7
(t") Wes
- p/ -1/C))1/)))
m
VET'
r log(1 (1 + exp(-C. - 0.001)) 7 (2)
where we use Lemma C.4 in the second inequality. The third inequality is by the definition of I' and C 2 1000. Thus this raises a contradiction given that L5(W (W(+)) S 2e for any e 0. This suggests there exists constant fraction of noisy
(2()) samples satisfy 1 E Poant ( 2 C.. This further indicates by Lemma C.4, for these samples
ü f((((()) x2) 2 C. 1/C, > O.
(4) For the test error, we first derive the probability Plyf(W(*),, x) < 0) as
P(yS(W(T)) x) 0)
P
E + ())
Σo o
E+ <)) 2 0
- Σ
(
(t)
Uirt B11)))
yor
1=1
m
1 m
m
2 PP
y.r. c + {))
E + ())
(0) yr
+ +1/())
m
- y.r E <))
(t))
a(w (c) v.r E: ())
ya + 1/(²)
(11)
n
m
for some sufficiently large constant C" > 0 and the second equality is by uniform distribution of &.
Next, we consider the following two cases separately, i.c., (a) When = and (b) when y = -1. When y = 1, (11) can be further bounded as
P(yf(W((), xx) 0)
2 P.
Σ ca(w""
1, - Envssnss + +())
(t))
(t*)
(t) 1 Σ f Euesyns, +()) 2 Σ
11 +1/C²)
(0)
where we use the sample size of [Sy nS] = Zin 2
Now we analyze the the magnitude of each term. Based on the decomposition, we obtain for any i E Sy. j +1 and any r E [m]
for
E + ()- =
(0) Wir 7i.
||al p +
Ping EE 11 E + Σ
Ee
1v
v=1
1=1
P/ + 2g. + +wW!00 (0)
E: + <)
(1/r
(t')
||ا|| u. E + <)
(()) (Ev, Ei ()
(Ev, Ei + ()
(r)
Pina [ 112
+
Sires || l2
28

---

On the Role of Label Noise in the Feature Learning Process
Then bound particularly for i Sy n St, i.e., Di -1
- (w (w) E +) 2 p_1,, - ((000g 0(1lu115 oz) - ((nd-1/3)
p (t)) 1,n 1/C3
(t") Ō(1 for the first inequality. The second inequality is where we use Lemma B.I, B.2 and the upper bound on Pj.r.i Vrr by Condition 4.1 on ||/l|2 and d for some sufficiently large constant C3-
In addition, we can similarly show
(wir E: - 5) S S + +1 oe) + Önd 1 < 11/Cs
Then can show for any i E Sy ns i.c. = =-1
m
1 m
m
Σ
<a((w!")
(f')
1,r E: + ())
Σ
a (w
(t') 1r
E. + ()) 2
(1')
-,r, 2/C3
m
m
m
(1")
C. 2/Css
11
+1/C"
where we choose Cz, C" such that C. 2//3s > 1/C". This suggests when y = 1, we have P(yf(W(r)), x) 0) 2 0.57+
Similarly, use the same argument to show when y = -1
P(yf(W(T"). x) < <0) 2 0.5T_.
This completes the proof that P(yf x) 0) 2 0.5 (T,,
D. Analysis without Label Noise
For the case of no label noise, i.e., T4, T_ = O. We still require the same assumption as in Condition 4.1. We reiterate the assumption for completeness here.
Condition D.I. We T - 2 2d-1) to be the maximum number of iterations considered. Suppose that there exists sufficiently large constant C such that the following hold:
The signal-to-noise ratio bounded by constants n SNN22 ((1)
2. The dimension d is sufficiently large, d 2 C'mxx {n² log(nm/ 6) log(T")) mllpell20 Vlog(n/8)}.
3. The standard deviation of the Gaussian initialization du is chosen such that du C-1 min (vnoz=d-1 ||]| log(m/8)-1/2/)
4. The size of training sample n and width adhere m Clog(n/0), 2 C Clog(m/0).
5. The signal strength satisfies || 3 2 Co? log(n/6).
6. The learning rate satisfies 7 S C-1 min (o 3/2 2 mo (og(n//)) og 22 -2 1d)
With the label noise, the coefficient update equations are given by
(0) (0) Far pr 1000 0,
29

---

On the Role of Label Noise in the Feature Learning Process
(t)
"
o'((
jirt Ma
nm
p
(1)
" 4
d'( j.r l B = j),
Pjinn
nm
( 2 +
" (())
d'
( IE --)).
nm
where we highlight that for all i [n]. i1 y/-
Proposition D.1. Under Assumption 4.1 and the same definition as for the label noise case, for 0 S TT, we have
0 $ P.rr S
(12)
log(Gn2 (5)
0 2 C 2 --3 -10V
nax 2 -a,
(13)
d
0 S 7jr S CCaa
(0)
(14)
In order to prove such results, we use the same induction strategy as for the label noise case. We first notice that if (12), (13), (14) hold at iteration t, then bounds Lemma C.3 and Lemma C.4 hold at iteration t. We include the results here for the purpose of completeness.
Lemma D.2. Under Condition D.I, suppose (12), (13), (14) hold at iteration t,
8log(6n/8))
kw w w.r (4) - -j.7.. 1.
101 S
no,
logí (6n2 65) na, y/1 j
Kw (1)
E.) -Pyr.al S /
d
log(6n2 /0) na, y/4 jj
kw f.r
E.)
e 5V
all E [m],j +1,1 E [n]. Further, there exists a sufficiently large constant Cj such that
(1 + + 1/C1 < v.f(WW) xx) (.)
(100) -1t Pmina) 1/C2
for all i E [n].
Proof of Lemma D.2. The proof follows directly from Lemma C.3 and Lemma C.4.
Next prove a stronger lemma that only holds under the condition n SNR===(1)) and without the presence of label noise.
First we require a lemma that allows us to bound the loss derivative ratios.
Lemma D.3 ((Kou et al., 2023)). Let g(=) -1/(1 + exp(z)), then for all - 2 21 2 -1, 2 0, we have
exp(c)
g(21)
S exp(cc
g(22)
Lemma D.4. Under Condition D.I, for any given t < TT, suppose (12), (13), (14) hold for all iterations S t. Then we can prove for some constant K 2 0
(I) 1 Em (P + Tour Punrrk - -ee)) S for all i E [m].
m
(2) (( 1p(0) < Ör for all i, [m].
(3) 5.0) _ 5( S _ -. for all i [n] and = r [m].
30

---

On the Role of Label Noise in the Feature Learning Process
Proof of Lemma D.4. We prove the results by induction. It is clear at s 0, claims (1) and (3) are satisfied trivially. Then for claim (2), we use Lemma D.3 bound
(D) (()) S exp(y=/( xx) - Vi](((o) x:))
S exp
Σ
m
Panki + +-/0or))
(0)
1
(p
Phins + +700)) + 2/01)
m
m
exp (2/()))))
which shows constant upper bound.
Next suppose / = i, (1)-(3) hold for all 8 S i - 1, then show they also hold Ō. For (1), according the update rule of the coefficients,
1
m
1
m
P
772
m
17
Σ
Σ
11
Ex
(15)
nmm
res(t-1)
res
(8)
(
(f-1))
18ur
1z.rr)
yyeer
n 1l
1)
((w
(f-1)
1) 1
((w((-)))
())
(16)
nmn
Be.r
P=1
We first analyze A5 depending on the following four cases.
(i-1) When (w our 11) 2 0, (w ya.r
(F-1)
14) 2 O, we have As = Evess, (1-1)-Ereh (0-1)==
When (w0-1)) (i-1)
(i-1) 1)
3 S we have As = Evess, (1(111- EvES,
-U-essEVes,, ((-1)) = O.
.. S 0, (w ya.r
(i-1)
( 1)
3 S 0, we have As A== =vrs, - Eves_ ((--1)
When (W |4) 2 0, (w ya.r
When (w (W pn) S 0, (w
(i-1)
(11)
p 2 0, we have As Eres,, (1-11- Eves, ((-1))
-
ya.r
Now we would like to bound the combination of (15) and (16).
When
(F-1) Yuur Pur.k
-
-(5-2) < 0.5x, then (15) can be bounded as
m
Peard + (0) p (1)
m
11-1)
+ (0-1))
-7(8-1) p ((-11))
Σ
Σ
M (1-1))
1
nm?
res!t-1)
rEs
n||
m
2
(tt /
1) 1
((w
p(t 1) 1
(w (i-1)
yaar ye )1/1
nm2
yi.r
(( 10
11 1) 11::12
7
< 0.5k
31

---

On the Role of Label Noise in the Feature Learning Process
nooa
0.5k + 1.01
n
m
K
where the second inequality is by 400 O for all i,t. The third inequality is by |s| ((1--11 1 S m. 11(1-1) S 1 and Lemma C.7. The last inequality us by Condition D.I for sufficiently small stepsize 1).
When L m Emm (Dlter)) + Your - Meank Your (0122) 2 0.5x, then by Lemma D.2,
(E-1)
vf((W(- xx) (W xx))
1
+ + (/0-))
-pu-- 2/C1
m
2 0.5x 2/01
2 0.4m
where we choose C 2 20/n. Then by Lemma D.3
((-1)
1i-1) I exp(y) (t-11)), xb) - yi (w xx)) S exp((-0.4m
k
Then we can show
11
1 11 < 1.01 exp(-0.4k)
(17)
/
1)
1
where we use Lemma C.7 and C.8 by choosing sufficiently large d and m.
Then we obtain
Ponns + (0) Pye,t,
(
m
(pllirn + ((-11)
((-11))
7
(1s 1
||5/113
-1s xx
1( |1Ex 12)
m
18ur
nm?
"
((i--))
|
nm
S
118,1
1
1i-1) (f-1)
7/.rr ((-!)))
1x01exp(-004k - 111 (((1))))) .1
+ Tour
171
nm²
17 (Õe 1) min 10 (i-1) |11111
+ 2m
iE(n)
1 m
(Priis) + 7/:r""
(i-1) (2-1) - (1-1)) + (0.49exp(-0.44) - (f
7.
m
nm
+ +0.5m(0; - 1) (0/ ((10~1|11
m
Porrss + - (8-1) (1-1) -11-111
f1-1)
m
where the second inequality is by applying (17) and also Evesy, - (f-1) < 2/2 (max,e[m) 1e
minje | ( < (C,- - 1) minier)) ( by induction. The third incquality is by K 2 1 and Lemma C.7, Lemma
C.8. The fourth inequality follows from the conditions on SNR? 2(0.48 210.48-0.990w -0.4)) O()). This verifies the claim (1) for T.
(C,-1)C,
32

---

On the Role of Label Noise in the Feature Learning Process
Now by Lemma D.3 and Lemma D.2, we can show
exp(ykf( .x,)
-b. .x,)
1
m
Panori + -
(1)
- -P (geer) + 2/C
I exp
m
I exp(1 + 2/(1))
Hence for given we can take C₂ = exp(1< + 2/C1). This verifies that claim (2) is satisfied. To verify the claim (3), we can show
(w Birr Ei) = (w (E-1)
E.) ..)
(i-1) o' d'((w (111) (E)) (E,,Ez)
y=1
(i-1) 1] ((W 61.r
(f-1)
ye pu) ) (ue Ei)
(w Bi.r
(F-1)
((--1)
1
Σ
(1-
4
d'((W))
((w Biir
(t-1)
,Er)) (E:: Ev)
Ag
A7
o'( ((w (-1)
m)) (UVHA.
We respectively bound the three terms as
e ((t-1)))
As 2 0.99
nm
where we use C.7. For A7, we can bound
| < 2n 1002 10 V dloo(66n///)
where we use Lemma B.1 and claim (2). Similarly,
|Asl S nCCle ( |1ll|200 2log(6n/0)
where we use Lemma B.1 and claim (2). By the Condition D.I where d C Cmax((33 log((n?) (6nn(6/n),, Cenlllel120 /2llll/l /)} for sufficiently large C. This ensures As 2 |Ar| + |Asl. which leads to (w())
I Ei) 2 (w(l-)) Bur ..)) > and thus s:D) c s(i-1) C ss Similarly, we can use the same argument to
prove j.r C ((t=))) C s!! jrr'
Proof of Proposition D.I. We prove the results by induction. At t = 0, it is clear that the claims hold trivially. Suppose there exists T < T such that the the claims hold for all < - 1. We aim to show they also hold at f = T. By Lemma
D.4, we know for all < f 1, we have ((()) /e < Č₁ for all k [n] and s: c _ S S
First, we follow the same proof strategy to show 0 >
> 33 10 (oog(622/8)/4
jmt
Next we show the upper bound for Pirn Let by be the last time / < T such that p/r,3 S 0.5a. Then
PoT. = Pulrdd
7 p(tma)) 1
((wll (trs)) Besr" .E)) 2 0)
Σ
17 0000 ((w (1) wu.r
(0))))))))))))) E1) 2 0)1...11
nm
nm
tE(t....))
33

---

On the Role of Label Noise in the Feature Learning Process
0.5a + 1.01
nold
1.01
nood
Σ
1
nu
mm
1 expp(
Ex=1 70%.)) 1/C1)
tE(t,,i))
aond
< 0.75a
2.02
7mm
a
where the first inequality is by Lemma C.7, Lemma D.2 and eltrra) < The second and third inequality is by choosing for sufficiently large C.
1) S C' C--CC""mmmm "mm 2d 2
(T) From the update rule, it is clear that Then we proceed to show upper bound for 25
( (F-1) 1i. 2ir 2 0. To prove the
upper bound on ?3pr we aim to show there exists 1 E [n] such that for all t s T that
S Cnn-SNRR
P yc T.."
where we take C. 1.1 We prove the claim by induction. We first lower bound Poini In particular, we can lower bound for any E [n], r o that
T
-1 Th Poi-.r
1) [E:
P
(1-1) Por... + 0.49
11
((T-1) -1)
mmm
111
(T)
where we use Lemma C.7 and Lemma D.2. Then for
7jr we have
(T-1)
(1)
o ((w ((w (T-1)
55r 31 S 73.
(T-1)
+
n
71772
where we use the second claim of Lemma D.4.
Then at iteration / 1, we can show
n 111ceBBBe 0.490²d
< 1.10m SNRR = C,n- -NRR..
P Nc -r
Now suppose for all t < - 1, we have
Pj.r/
I C.n SNR?, then we
Then we can bound
(
11
< max
Yi
n nllm|BBCe
$ &Cnn-SNR's SNR".
(T)
(T-1) Pg..
0.490²d
P Pr...
( This shows 75 < C.n (NR22(1-1) (1)
P...r. I C.a..
D.I. First Stage
In the first stage, we can lower bound the loss derivatives by a constant C2 (by Lemma C.5) and we show both Par
(t) E S (0) and 7g can grow to constant order.
Theorem D.5. Under Condition D.I, there exists Ti 110101(11eee Inmoo -2 2d such that
(Ti) Pa O(1) for all E [n] and r E 5
34

---

On the Role of Label Noise in the Feature Learning Process
(T)) -0n-SNNR") (11) for all +1, r [m]] y.(((TT)) x,) 2 0. for all i [n]]
Proof. By the update rule of the coefficients, for E 5
Cro
Ceoade
" ((( | 2 P
Poe.r.
+ 0.99
0.99
t,
nm where we use the lower bound on loss derivatives and Lemma C.7.
nm
num
Then with
Ti = 2.11 nnmm og 0=²dd
we can show Pyr.t 2 2. Further we can obtain the upper bound as for all E [n].r E [m].]] = +1
no
nofd
(1) Pj.r, -ij..
11:
|1:
1.01
1.01
1971
nm
nm
where we use the upper bound on loss derivatives and Lemma C.7. Under the definition of Tı, for all i, r. we upper bound P 3C,
Next for lower and upper bound for Tj.r we first recall the update for any j +1, [m].
11
(1)
7
0' ((ww ((w)""" 1.HH)))111133.
71
When (w (t-1) 114 2 0,
(t-1) CellllllB
Cellllll
(1-1) 1)
1
73.r
nm
2m
2m
KE
where the lower bound on (((-1)
Similarly, when (w((-1) .14) I O, can obtain the same lower bound as
35.r
20me
Then at Ti, we can bound for all j +1, [m]] as
(1) n n111
23.5 2
n SNR2 2(11)
ofd
The upper bound follows from
7/1
n/ 1 1
(1) (1-1)
7/.r S 7f.
2m
2m
where we apply the upper bound on 17 < 1. This verifies that at t = Ti,
(t-1)
(t)
$ 1.10, 'n. SNR² = O(1),
3,r
which shows at Ti, both p 1j.r For all samples, by Lemma D.2,
(Ti)
O()).
Vef (T))
xi)
1
1/C1 2 0, Pain t2g.r
(Ti) (Ti)
m
where we let C₁ to be sufficiently large.
35

---

On the Role of Label Noise in the Feature Learning Process
D.2. Second Stage
In the second stage, we show the loss converges and under constant signal-to-noise ratio, we can show the test error can be arbitrarily small at convergence, while for all Ti sts T y.f(W(t), .x) 0, for all i [n]]
Theorem D.6. Under Condition D.I, there exists a time 1.* E [Ti, T where T = Ot -t "mnoog 2 such that
Training loss converges, ie,, Ls (s( S.
For all samples, ie.., i E [n], it satisfies y: (.)( xx) 2 O.
Test error is small, i.e., (1b((w(()) 2 exp ( 0
Proof of Theorem D.6. The proof of convergence is exactly the same as for the case with label noise, and thus we omit it here. The second claim is also easy to verify given that both Jer p are monotonically increasing. By Lemma D.2, we can obtain the desired result.
Now we prove the third claim regarding the test error. To this end, we first show for all Ti StS (t) 3/r -= Pinn
(t)
(Ti) (SSNR²) for all j =l,r E [m]. We prove such claim by induction. is clear at Ti, we have Σ j.rd (n) (Ti
and (75) (n SNR?) for all j =1, [m]. Thus, we can verify the 7 ΣE= Pj.n O(SNR²) ). Now suppose
7/r
for a given T E [T) such that //r// Ei=1 Pj @(SN?² holds for all Tj S t S T 1. Then according tor the update.
12
T-11)
Σ
E
jina
Jini
7m
::0=
ky
iES(T-1 1) 2.7
(-1)
2
jin
+ 0.12
min
m
1E(n)
1=1
where the second inequality is by 5000 C -1- 1) and Lemma B.3, Lemma C.7. Similarly, we can upper bound
Σ
Pant
Pira + 1.01
(T-1)
no
max
(T (T-))
X [n
2m
where we Lemma C.7.
On the other hand, we can lower and upper bound
( (T-1
17
min ( 1)
2m iES.
(
S 9i.
(-11
"
max
(
1)
||
2m iE ml]
This suggests
1T-1) 2
min mg] 1 1)
|1110111
(T-1)
SNR²
jjrr T2 Σ Pj.r
min
min
Σ
n
(T-1)²
2.02 maxie[n] 1 (T(T-1)
(T-1)
2.02
1= Pj.r.
2SNR2)
where we use maxie[n] 1 (1) < Ö2 minie(m) (TD) by second claim of Lemma D.4. Similarly,
i
(T-1)
ČASNR2 2
j.r
O(SNR?.
Σ" Σm
max
Σ P
(--))
0.24
36

---

On the Role of Label Noise in the Feature Learning Process
This verifies for all T1 S
(SSNR))
(18)
jint
Finally, we prove the test error can be upper bounded. We first write for test sample (x, y) ~ Drest.
yf yf(W
x)
((w yor ypu) (( W. E ())
m
(o(w (t") y. ym)
=o (t') p.r E + c)))
For (wyr ypt), we can bound
(Es. Vpe (1)
(E 8pe)
gir B1) = -0tt? + (w gor, mp) +
((
Purri
E
y.r
2 1.r
v log 12m 2011mmm000l/
1اl| (ll 2allll//22ll((//8)00 d
OS(SRR
(
(19 y.
where Lemma B.1 and Lemma B.2 and (18) in the second inequality. The last inequality follows from Condition D.1. With an similar argument, we can show
(e) y.r un) S -4.99 (t") (w
Further, we let g({) = Em a((w (t)) p.rt < + {)) and by Vershynin (2018, Theorem 5.2.2), we have for any 2 0,
((g(C) Eg(() a) S exp(-ca'a 2 (
where expectation is taken with respect to Ç ~ NO, I and c > 0 a constant. To compute the Lipschitz constant, we compute
m
19(C) 9(00(((()
Σ
(t')
Dart < (+ - Σ (t')
-grr 5' E))
0 (1')
(+ - c((w -yir (( 5' + {
(t")
r=1
m
m
Σ
(w - S
<\)l Σ
| (t) V 112ll - 5'112
where the first inequality is by triangle inequality and the second is by the property of ReLU function. This suggests lل Σm |/ prr 12-
In addition, because conditioned on (w((") -yirs S N (N (C)) mo E), [|w][) ).
Eg(()=
Eo Eo((w (t')
y.rr 5 E))
m
(w (t)
my:r: E)
[[w(t?) (t")
||
-y. 1120
(t")
-g.r E)2
Σ
(w (t')
y.ri :. <) (1 $6
exp(
|| (tt)) 1120
2m
2| blww" ((*) 11:02
|/ ||w((") 1120g 11
p (t")
P-y.n +
2n
r=1
37

---

On the Role of Label Noise in the Feature Learning Process
where the expectation is taken with respect to Ç and the last equality is due to (Beauchamp, 2018) on expectation of truncated Gaussian. The first inequality is by taking 5 = E:- where i = arg maX,e P-y.r, and use Condition D.1 to remove the leading constant.
Further, we require to bound || -yrllla by first bounding
2
Σ Ie
&.
=
11::112
-2 +2
Σ
Paniljjr j.ni
(e) (e))
Ec)
2
1=1
Isisi'n
log (6n /8)
1.01o s
-2 d
Pj.ra 4.08
(2))²
Σ
(e)
o2/51/2
Ssici'n
=1.01og" 2d
(t))²
4.08
V /log(6n2/0 18)
)
o2.312
0 2d
(1))
+ -0(05
-2d
3/23
Pirr
I 0 in
where the first inequality by Lemma C.7 and Lemma B.1 and the last inequality is by the coefficient orders at 8", Thus, we can bound
1/2) ////f 112 S | 1 + 7/5 |ml| + O(O 1d -11/2
Σ
P
Pirs
= O(oovd) OSNN og d 1/2 n 1/2)
(1) Pjana
< 500 d- 1/2 1/2)
where the first equality uses Lemma B.2 and (18). The second equality follows from Σ.= P/ M(n). The last inequality is by Condition D.1 where SNR / d 1/11/22211//
vn SNR O(1) and
ao vovil(o 1-122 E ( ((ooredn 11/2) O(1) by condition on oo in Condition D.I.
This gives
m o((w) (e') yp))
9 (d-1/2n Er, -- (
O SNR?)
Eg(C)
u.r. + ExL p (1)
--y-r-,-
Suppose n SNR? 2 C+ for C+ > 0 sufficiently large. Then we have Ere a(wW?? (2) ,2p)) - Rg(() > 0.
We bound the test eтror as
Plys(W(()) x) <)
PPP
a a(lw"!
(t")
yorr E ()) 2 Σ o((
1=1
IP
5 w v.r.
E + ()) N
o a(wl(() (44)
1=1
IP
9:(C) - Eg:(C)> > Σ a((w ((wl(() y.r spو) - Egi(s)
38

---

On the Role of Label Noise in the Feature Learning Process
Th o
(( g.r vp))
Ex=1 P y.ri
(()
0e/(2
Er= || [[ ( =gmllla
exp
T2
|w |W 112)
1=1
-r== a(W vir yp)) > P-m
c
exp
2T
0.5c
05 -
|
(19)
ll2
y.r
Σx= 0 (79.1 1 D/=1 p ((12)
exp
2T
0.5c
(d 1/2n 1/2)
Σ Zi=1 (1r)
Piree
7
Σ O(n 1 'SNR
-2,((")
A(d 1/2 2r + (
(t")
exp
c
10.1"
0.25c
2T
O(d 1/2n 1/2) -/=1 Σm=
(3)
1/2) - Σ==1 i=
P j,
Jm
=
exp
CDofd
where we denote gi(5) = Em= o(w (1)) yar + E.)).
The third and fourth inequalities are by (s - t)² 2 s²/2 12.
E. Early Stopping and Sample Selection
Proof of Proposition 4.3. The proof follows the same idea as for Theorem D.6, with the difference that both Ere(m) (1))
(T)) = (m) and Eremm "ir (m) and Ere(m] Pi.r.
(T1) (Ti) > Eremm) Poina for all j = +1 and i E [m] (from the results of
Theorem C.9). Then we can bound the test error directly as
E of ((W (
y2)) Em p (T)))
Plys(W(()) (T)) x) <) S
exp
2T
0.5c
OE Σx= w v.r ll2
(T))
exp
2x
0.5c
O ((d-1/2n!/2)
C
d
exp
2T
71
d
S exp(
nCe
where the second inequality follows from Ere(m)
(T))
(Ti Ere(m) Pa..r (m) and || wy.
ll2 s O(o5" d 1/2
where Σ._ (T) < (n). The last inequality is by choosing sufficiently large constant C. >>
The claim sample selection follows easily from Theorem 4.1.
F. Additional Experiments
39

---

On the Role of Label Noise in the Feature Learning Process
28
5.
0.0
36
6.-
10
1900
0
(a) 1l 20, 7 0.1.
(b) / 20, T 0.15.
(C) f 20, T 0.2.
24
0.4
54
22
0.2
50
125
130
(d) 20, 0.25.
(c) 15, 0.2.
(f) 25,
0.2.
Figure 3: Experiments on synthetic data with varying problem settings, including varying signal strength and label noise
ratio r. We shade the area before noise learning overtakes signal learning of noisy samples in blue. This corresponds to the Stage I our analysis, where early stopping beneficial. We shade the area where signal learning exceeds noise learning for noisy samples in orange, which corresponds to Stage II in our analysis.
40

---

On the Role of Label Noise in the Feature Learning Process
1.0
1.0
0.8
0.8
0.6
0.6
Accover wi label noise
Accu label naise
0.4
0.4
ACComose w/ label noise
ran wi label noise
0.2
AcC w/ label noise
0.2
AcCommoww wi label noise
AcCr wio label noise
AcCro wio label noise
0.0
0.0
1.0
1.0
0.8
0.8
0.6
0.6
0.4
0.4
0.2
Accouur W/ label noise
0.2
AcCouur W/ label naise
Accouu w/o lebel nobe
Accosur w/o label noise
0.0
0.0
40
120
160
40
120
160
0.1.
(b) 0.15.
1.0
1.0
0.8
0.8
0.6
0.6
ACC label
ACCrowe label
0.4
ACGrrmaeee label noise
0.4
AcSivueee label naise
0.2
ACS
0.2
AcC label noise
ACCo label noise
0.0
0.0
1.0
1.0
0.8
0.8
0.6
0.6
0.4
0.4
0.2
Accoue w/ label noise
0.2
AcCous w// label naise
w/o label noise
AcCour w/o label noise
0.0
0.0
40
120
40
(c)
(d) r 0.25.
Figure 4: Experiments CIFAR-10 dataset with varying label noise ratio Across different label noise ratios, observe similar pattern that there exist initial decrease in the training accuracy noisy samples before increase perfect classification. This validates our theoretical findings in real-world settings under various label noise ratios.


Reviews:
[{"review_id": "IsNSsTMjbj", "reviewer": "Reviewer_Q9d8", "summary": "This paper analyzes the training dynamics of a (custom) two-layer ConvNet under binary class-conditional label noise. The main result is a a two-stage characterization of \"first fitting all clean samples, then overfitting to noisy samples\".", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your great efforts on the review of this paper and for recognizing the value of our contributions. We will try our best to address your questions.\n\n**Q1: Suggestion for acknowledgement in setup part. “The setup is built upon Kou et al. (2023), it would be good to indicate that in the main text.”**\n\n**A1**: Thank you for the suggestion. We will include additional commentary in the Preliminary section to explicitly acknowledge that we built our theoretical setup upon [1] and [2].\n\n**Q2: Question on the possibility of extending to a standard CNN. “I understand that this is the setup considered in Kou et al. (2023), but I am still curious about whether it's possible to consider a more general form that resembles a \"standard\" CNN.”**\n\n**A2**: Good question. We would like to clarify and address the points as follows:\n* **Justification of the Two-Layer CNN Model**. First, we clarify that the two-layer ReLU CNN architecture, while simplified, is a well-established model in deep learning theory for analyzing training dynamics [1, 2, 3, 4]. This choice strikes a balance between capturing essential learning phenomena and maintaining mathematical tractability.\n* **Clarification on Global Average Pooling**. We respectfully point out that our theoretical analysis does not consider global average pooling. In fact, we can rewrite the two-layer ReLU CNN model as \n$$ \nf(\\mathbf W, \\mathbf x) = \\frac{1}{2m} \\sum_{r = 1}^{2m} a_r \\left(\\sigma(\\langle \\mathbf w_{r}, y\\mu\\rangle) +\\sigma(\\langle \\mathbf w_{r}, \\xi\\rangle) \\right).\n$$\nwhere $a_r$ represents the second-layer weights, which are fixed as $a_r = -1$ for $r \\leq m$ and $a_r = +1$ for $r > m$. This is different to global average pooling where $a_r = 1$ for all $r$. We will clarify this point in the revised paper.\n* **Extension to \"Standard\" CNN**. We have also carefully considered the extension to a more “standard” CNN. Based on the review’s context, we interpret the term “standard” into two aspects: \n     1. *Flexible stride in the convolutional layer*. We acknowledge that variable strides are commonly used in practice. Extending the data distribution to a multi-patch case allows us to use a larger stride (increase the size of the receptive field), which is more aligned with standard CNN architectures.\n     2. *Multi-layer architectures*. We recognize the importance of deeper networks. However, the analysis of training dynamics beyond two-layer CNN remains an open challenge and often requires unrealistic assumptions, e.g., infinite width [5, 6] layer-wise training [7]. \n\nOverall, while we acknowledge the value of extending our analysis to a more complex setup, this lies beyond the scope of our paper and is deferred to future work.\n\n**Q3: Concerns about the synthetic experiments. “line 376, synthetic experiments: why choose a high-dimensional case $d \\gg n$? Will the same result hold for $d < n$?”**\n\n**A3**: Good question. First, we clarify that we choose $d \\gg n$ according to our theoretical setting (Condition 4.1), where we analyze the over-parameterization regime. \n\nNevertheless, we followed your suggestion to conduct a new experiment with $n > d$. Specifically, we choose $n = 200$, $d = 180$. Results are presented at [Figure (please click this link)](https://anonymous.4open.science/r/ICML2025-label-noise-26D3). Consistently with our main paper, we observe a two-stage behaviour, where the model initially fits the clean samples and then overfits to the noisy ones.\n\n**Q4: Suggestions for emphasizing Appendix A. “the authors may need to emphasize Appendix A because it's crucial when evaluating novelty of this work.”**\n\n**A4**: Thank you for the suggestion. We will follow your suggestion to include a “technical novelty” paragraph to highlight Appendix A in our revised paper.\n\n### Reference\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] Zou et al. The benefits of mixup for feature learning. ICML 2023.\n\n[4] Chen et al. Understanding and improving feature learning for out-of-distribution generalization. NeurIPS 2023.\n\n[5] Du et al. Gradient descent finds global minima of deep neural networks. ICML 2019.\n\n[6] Allen-Zhu et al. A convergence theory for deep learning via over-parameterization. ICML 2019.\n\n[7] Chen et al. Which layer is learning faster? a systematic exploration of layer-wise convergence rate for deep neural networks. ICLR 2023.", "claims_and_evidence": "Yes, the claims were proved.", "methods_and_evaluation_criteria": "Overall makes sense to me.", "theoretical_claims": "I've skimmed through the proofs, but have not checked the details.\n\nInsights and proof sketches were provided in the main text, which is good for readers.", "experimental_designs_or_analyses": "Yes.", "relation_to_broader_scientific_literature": "This paper analyzes the training dynamics of NN under label noise beyond the \"lazy training\" regime, which is a good contribution to the literature.", "essential_references_not_discussed": "Essential references are included.\n\nThe setup is built upon Kou et al. (2023), it would be good to indicate that in the main text.", "other_strengths_and_weaknesses": "My understanding is that the paper uses the setup and tools from Kou et al. (2023) to analyze the training dynamics under label noise.\n\nThe paper is well written and the results are clear to me. Though novelty is a bit limited, I'm glad to see a new analysis of label noise learning.", "other_comments_or_suggestions": "The data distribution and Two-Layer ReLU CNN setup seems to follow the one in Kou et al. (2023) and Cao et al. (2022), please indicate that.", "questions_for_authors": "1) line 142: The \"Two-Layer ReLU CNN\":\n$$\nF_j(W_j, x) = \\frac{1}{m} \\sum_{r=1}^{m} \\left( \\sigma \\langle w_{j,r}, y\\mu \\rangle + \\sigma \\langle w_{j,r}, \\xi \\rangle \\right)\n$$\nseems to corresponds to CNN with stride $d$ and then global average pooling.\nI understand that this is the setup considered in Kou et al. (2023), but I am still curious about whether it's possible to consider a more general form that resembles a \"standard\" CNN.\n\n2) line 376, synthetic experiments: why choose a high-dimensional case $d >> n$? Will the same result hold for $d < n$?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Up4EWbl6kS", "reviewer": "Reviewer_P2ej", "summary": "The paper is concerned with a theoretical analysis of gradient descent when the training samples contain label noise as well as features uncorrelated to the correct class. The chosen methodology is feature learning theory, where highly simplified learning problems are introduced in which the features carrying signal are clearly separated from features representing noise, and a simple network architecture is trained. In this setup, the convergence of the loss can be formally analyzed in great detail as a function of the type of the example. The paper presents theorems that suggest that in the setup they study signal features are picked up by the network much faster than noise features, which creates an initial stage with generalizable learning and a second stage with overfitting.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your great efforts on the review of this paper and for appreciating our novelty and contributions! We will try our best to address your questions.\n\n**Q1: Concerns about the presentation. “The formalism is well designed and it is possible to follow, although not too easily, eg the two-layer CNN is described extremely briefly.”**\n\n**A1**: Thank you for your feedback. We will provide a more detailed and clearer explanation of the two-layer CNN in our revision. \n\n**Q2: Concerns about the real-world experiments. “the CIFAR10 experiments are not well described (training setup, etc) and the results there have very little overlap with the presented theory in general (data model, network architecture, ...) so they provide only very indirect support for the usefulness of the theory, they basically reiterate well known empirical behavior.”**\n\n**A2**: Thanks. We would like to clarify that the primary purpose of the CIFAR-10 experiment is to support and illustrate the theoretical findings, rather than to introduce new empirical discoveries. As the reviewer noted, there are differences between the theoretical setup and the CIFAR-10 training setup. However, the observed results align with our theoretical insights and help demonstrate the broader applicability of our theory beyond the simplified setting. \n\nAdditionally, in response to the reviewer’s suggestion, we will include more details on the CIFAR-10 experimental setup in the appendix to improve clarity and transparency.\n\n**Q3: Concerns about the simplified theoretical setup. “the theoretical results of the paper are in a very simplistic setup in which signal and noise are very clearly separated not only in the input, but also within the network architecture. The learning algorithm is GD with a constant learning rate. This makes the analysis possible but the usual question remains: does this approach have any explanatory power?”**\n\n**A3**: We sincerely appreciate the reviewer's thoughtful critique regarding our theoretical setup. We address these concerns from three perspectives:\n\n* **Well-Established in the Community**. Our simplified framework follows standard practice in the deep learning theory community. Similar settings (e.g., GD with constant LR, architecturally separated signal/noise) have been adopted in many influential works [1, 2, 3, 4] to gain fundamental insights into neural network behavior. These simplifications are essential for isolating and rigorously analyzing core learning dynamics.\n\n* **Empirically Validated**. Our theoretical results are not merely abstract; they align closely with our real-world experiments (see Section 5). This consistency underscores the validity of our framework and demonstrates its explanatory power in practical scenarios.\n\n* **Challenges of Extension**. While we agree that extending the analysis to more complex settings (e.g., deeper model, realistic dataset) would be valuable, it remains highly challenging due to the nonlinear, nonconvex nature of neural network training. Many existing approaches rely on unrealistic assumptions—such as infinite-width networks [5, 6] or layer-wise training [7]—which can obscure the phenomena our work aims to clarify.\n\nFrom a broader view, simplified models are foundational across many scientific disciplines, from idealized models in physics to mean-field theories in neuroscience. Thus, we believe our theory provides valuable insights and substantial explanatory power, offering a solid foundation for further research in more realistic settings.\n\n**Q4: “Typo: line 146, I guess F_{-1}(W_{-1}…”**\n\n**A4**: Thanks. We will correct this typo.\n\n**Q5: Questions for applying $T_1$ as the early stopping point in practice. “I was wondering ... T_1 is not necessarily an early stopping point (in the usual sense of having a local maximum accuracy (or min loss) on a validation set), ..., because finding T_1 is not possible directly in practice. Do you have any thoughts on that?”**\n\n**A5**: Insightful question. We agree that directly computing $T_1$ in real-world scenarios is not feasible due to the complexity of the training dynamics and unknown data distribution. However, our theory suggests the existence of a point $T_1$, beyond which further training may degrade generalization performance. This implies that validation accuracy can serve as a practical surrogate for identifying $T_1$, which aligns with the common practice of early stopping at the point of maximum validation accuracy, as mentioned by the reviewer. Indeed, our theory explains the effectiveness of the common practice, which further strengthens the applicability of our theory. We will clarify this point in the revised paper.\n\n### Reference\nDue to space limit, we defer the reference list to the Reference part in *Rebuttal to Reviewer Q9d8*.", "claims_and_evidence": "The theoretical claims in the specific simplified setup are supported by thorough proofs. I have not checked these proofs in detail but the formulation is of high quality. In the experimental section the CIFAR10 experiments are not well described (training setup, etc) and the results there have very little overlap with the presented theory in general (data model, network architecture, training setup, specific assumptions, etc) so they provide only very indirect support for the usefulness of the theory, they basically reiterate well known empirical behavior.", "methods_and_evaluation_criteria": "The theoretical methods are appropriate.", "theoretical_claims": "I did not check the proofs. The formalism is well designed and it is possible to follow, although not too easily, eg the two-layer CNN is described extremely briefly, the supplementary could have expanded this a bit. The rest of the presentation is similarly dense, it requires a lot of effort to follow.", "experimental_designs_or_analyses": "As mentioned above the CIFAR10 experiments are not described in enough detail and present observations that have been rather well known from research into memorization, as also mentioned in the paper itself (eg that early stopping works for label noise). So overall, the theory does not have a really strong experimental support, but in general it is in line with empirical observations (clean samples converge first).", "relation_to_broader_scientific_literature": "The paper can be positioned as a purely theoretical work in the area of feature learning theory, a specific methodology to study the convergence during training. Its contributions lie in studying label noise in this framework and also applying a number of technical innovations in the analysis.", "essential_references_not_discussed": "No suggestions here that are essential.", "other_strengths_and_weaknesses": "As for strengths, the paper targets an interesting problem and offers a theoretical approach in a novel framework (feature learning theory) that captures some of the empirically well-known observations such as that clean samples converge first, and early stopping is a good way of filtering noisy labels.\n\nAs for weaknesses, the theoretical results of the paper are in a very simplistic setup in which signal and noise are very clearly separated not only in the input, but also within the network architecture. The learning algorithm is GD with a constant learning rate. This makes the analysis possible but the usual question remains: does this approach have any explanatory power?", "other_comments_or_suggestions": "Typo: line 146, I guess F_{-1}(W_{-1}…", "questions_for_authors": "About the early stopping result (prop. 4.3). I was wondering whether it is really early stopping in the sense that although stopping at T_1 is good, T_1 is not necessarily an early stopping point (in the usual sense of having a local maximum accuracy (or  min loss) on a validation set), and that is actually a rather crucial question, because finding T_1 is not possible directly in practice. Do you have any thoughts on that?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "cMpZVxtrwC", "reviewer": "Reviewer_VPGT", "summary": "This paper provides a theoretical analysis of how label noise impacts the feature learning process in deep neural networks. The authors prove a two-stage learning dynamic for networks trained with label noise:\n\n1. Stage I – The model first learns from clean samples while ignoring noisy ones, leading to good generalization.\n2. Stage II – As training continues, the network starts overfitting to noisy labels, resulting in performance degradation.\n\nTo support their theoretical framework, the authors analyze the training dynamics of a two-layer convolutional neural network (CNN) on uniform label noise. Their findings highlight the risks of prolonged training with noisy labels and provide a theoretical justification for two commonly used strategies to mitigate label noise: early stopping and sample selection. The paper further validates its claims through synthetic experiments and real-world experiments on CIFAR-10.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your great efforts on the review of this paper and for recognizing the value of our contributions. We will try our best to address your questions.\n\n**Q1: Suggestions for more explanations of why the model tends to prioritize learning from clean-labeled samples. “However, its impact could be further strengthened if the authors offered a more in-depth explanation, based on their theory, of why the model tends to prioritize learning from clean-labeled samples before incorporating noisy labels.”**\n\n**A1**: Thank you for the suggestion. We will include a more in-depth explanation in the proof sketch. Intuitively, the signal $\\mu$ is shared across all samples, and thus it is easier to be captured by the model. In contrast, noise is more complicated and varies across samples, so learning the noisy samples requires the neural network to spend more time exploring a refined structure to memorize the noise for each sample.\n\n**Q2: Questions for applying $T_1$ as the early stopping point in practice. “According to Theorem 4.1, $T_1$ marks the transition between the first and second stages. Could $T_1$ be leveraged in practical applications to determine the optimal point for early stopping, even for the synthetic experiment?”**\n\n**A2**: Thank you for the question. As also discussed in *Reviewer P2ej A4*, we acknowledge that directly computing $T_1$ in real-world scenarios is not feasible due to the complexity of the training dynamics and unknown data distribution. However, our theory suggests that validation accuracy can serve as a practical surrogate for identifying $T_1$. Based on Theorem 4.1 and Theorem 4.2, $T_1$ marks the transition beyond which generalization performance begins to degrade. Therefore, early stopping at the point of maximum validation accuracy aligns with our theoretical insights and the common practice of early stopping.", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "Yes", "theoretical_claims": "I haven't carefully checked the proof, but the proof sketch looks reasonable.", "experimental_designs_or_analyses": "The authors clearly show two-stage phases during training with label noise via synthetic experiments and real-world experiments on CIFAR-10.", "relation_to_broader_scientific_literature": "The paper provides theoretical support for learning with label noise, especially methods focusing on early stopping.", "essential_references_not_discussed": "Related works have been well discussed.", "other_strengths_and_weaknesses": "The early stopping technique is widely used in learning with label noise, yet its theoretical justification remains incomplete. This paper provides valuable theoretical support for the phenomenon. However, its impact could be further strengthened if the authors offered a more in-depth explanation, based on their theory, of why the model tends to prioritize learning from clean-labeled samples before incorporating noisy labels.", "other_comments_or_suggestions": "See above.", "questions_for_authors": "According to Theorem 4.1, $T_1$ marks the transition between the first and second stages. Could $T_1$ be leveraged in practical applications to determine the optimal point for early stopping, even for the synthetic experiment?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper presents a rigorous theoretical analysis of how label noise impacts feature learning in neural networks. Using a signal-noise decomposition of the data distribution and a two-layer CNN model, the authors identify a two-phase training dynamic: in the first phase, the network fits clean samples and learns useful features; in the second, it begins to overfit to noisy labels, leading to degraded generalisation. The theoretical findings also provide justification for common heuristics like early stopping and sample selection, and are supported by experiments on both synthetic and real datasets.

Reviewers appreciated the clarity of the setup, the relevance of the analysis, and the combination of theory with supporting experiments. However, some concerns remained—particularly around the restrictive assumptions (e.g., model architecture and data distribution), and how these might limit generalisability to more complex or realistic settings. While these limitations are acknowledged, the core insights are sound and the contribution to understanding label noise in deep learning is meaningful.

Overall, the paper makes a valuable and timely contribution to the theory of training dynamics under label noise, and I recommend acceptance.
Decision: Accept (poster)