How Does Label Noise Gradient Descent Improve Generalization in the Low SNR Regime?
Authors: Wei Huang
Andi Han
Yujin Song
Yilan Chen
Denny Wu
Difan Zou
Taiji Suzuki
Venue: NeurIPS 2025 poster ()
Keywords: Label noise gradient descent
low signal-to-noise ratio
optimization and generalization
Primary area: theory

Abstract: The capacity of deep learning models is often large enough to both learn the underlying statistical signal and overfit to noise in the training set. This noise memorization can be harmful especially for data with a low signal-to-noise ratio (SNR), leading to poor generalization. Inspired by prior observations that label noise provides implicit regularization that improves generalization, in this work, we investigate whether introducing label noise to the gradient updates can enhance the test performance of neural network (NN) in the low SNR regime. Specifically, we consider training a two-layer NN with a simple label noise gradient descent (GD) algorithm, in an idealized signal-noise data setting. We prove that adding label noise during training suppresses noise memorization, preventing it from dominating the learning process; consequently, label noise GD enjoys rapid signal growth while the overfitting remains controlled, thereby achieving good generalization despite the low SNR. In contrast, we also show that NN trained with standard GD tends to overfit to noise in the same low SNR setting and establish a non-vanishing lower bound on its test error, thus demonstrating the benefit of introducing label noise in gradient-based training.

How Does Label Noise Gradient Descent Improve Generalization in the Low SNR Regime?
Wei Huang 27 Andi Han 3.1 Yujin Song".,, Yilan Chen", Denny Wu Difan Zou", Taiji Suzuki
RIKEN AIP The Institute of Statistical Mathematics
The University of Sydney The University of Tokyo University of California San Diego
New York University Flatiron Institute 8 The University of Hong Kong
wei huang.ung... ww@riken. ji;; andi han@sydney. eedsadddeeeeuu.u.. edu. au; y song. research@gmaail........... com; y1c031 @uesd edu; dennyuuênyu. edu; dzou@hku. hk; taijimmiss i. uu u-tokyo.... jc.jp
Abstract
The capacity of deep learning models is often large enough to both learn the underlying statistical signal and overfit noise in the training set. This noise memorization can be harmful especially for data with low signal-tonnoise ratio (SNR), leading to poor generalization. Inspired by prior observations that label noise provides implicit regularization that improves generalization, in this work, we investigate whether introducing label noise the gradient updates can enhance the test performance of neural network (NN) in the low SNR regime. Specifically, we consider training two-layer NN with a simple label noise gradient descent (GD) algorithm, in an idealized signal-noise data setting. We prove that adding label noise during training suppresses noise memorization, preventing it from dominating the learning process; consequently, label noise GD enjoys rapid signal growth while the overfitting remains controlled, thereby achieving good generalization despite the low SNR. In contrast, we also show that NN trained with standard GD tends to overfit to noise the same low SNR setting and establish non-vanishing lower bound its test error, thus demonstrating the benefit of introducing label noise in gradient- tradieen-bbsedd training.
Introduction
The success of deep learning across various domains 34 48 7 is often attributed to their ability to extract features 20 15] via gradient-based training [14 One desirable property of gradient-based feature learning is the algorithmic regularization that prioritizes learning of the underlying signal instead of overfitting to noise: real-world data contains noise due to mislabeling, data corruption, inherent ambiguity, yet despite having the capacity to memorize noise, neural networks (NNs) trained by gradient descent (GD) tend to identify informative features and "low-complexity" solutions that generalize [57] 43).
To understand this behavior, recent theoretical works considered data models that partition the features into signal and noise components [19 54 and studied the performance of gradient-based training in different signal-nois conditions. Among cxisting theoretical settings, the signal-noise model proposed in [2] has been extensively studied in the feature learning theory literature. In this model, input features are constructed by combining label-dependent signal with label-indes label-independent noise. The signal represents meaningful patterns relevant to the predictive task while the noise
"Equal Contribution
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

component captures background features unrelated to the learning task. This idealized setting has shed light on how various algorithms,, neural network architectures, and other factors influence optimization and generalization of neural networks, depending on the signal-to-noise ratio (SNR)
[8 58
29
25
56
27 22
26 23 35).
In such model, it is known that the SNR dictates a transition from benign overfitting to harmful overfitting. In the high SNR regime, gradient-basee feature learning prioritizes signal learning over noise memorization; hence upon convergence, the trained NN recovers the signal and generalizes to unseen data despite some degree of noise memorization, a phenomenon known as benign overfitting 4 40 44 46 3T. In contrast, when the SNR is low, noise memorization dominates the training dynamics, and the network fails identify useful features before the training loss becomes small, leading to harmful overfitting g 33).
Given these challenges, recent works have explored algorithmic modifications that either enhance signal learning or suppress noise memorization, to improve generalization in the challenging low SNR regime. [25] showed that the smoothing effect of graph convolution in graph neural networks mitigates overfitting to noise; however, this approach requires the graph to be sufficiently dense and exhibits high homophily.
[T]] found that the sharpness-aware minimization (SAM) method [I7] prevents noise memorization in early stages of training, thereby promoting effective feature learning; this being said, SAM has higher computational cost than standard GD due to the two forward and backward passes per step, and it involves more complex hyperparameter tuning. The goal of this work is to address the following question:
Is there a simple modification of GD with no computational overhead that achieves small generalization error in low SNR settings where standard GD fails to generalize?
1.1 Our contributions
We provide an affirmative answer to the question above by introducing random label noise to the training dynamics as a form of regularization, inspired by label noise (stochastic) gradient descent
(GD) 6 45 49]. Specifically, we analyze the classification extension of label noise GD considered in [24 13,. where random label flipping is introduced to prevent overfitting.
Empirically, we first present findings in controlled classification setting, where we train VGG-16 model on (a subset of) the CIFAR-10 10 dataset. To modulate the SNR, we follow [99 and add varying levels of noise to the high-frequency Fourier components of the images - higher noise strength corresponds to lower SNR and vice versa. The results, shown in Figure [ demonstrate that as the SNR decreases, the performance gap between label noise GD and standard GD becomes more signif- icant, hence suggesting that label noise GD improves generalization in the low SNR regime. The goal of this work is to rigorously establish this separation in ide- alized theoretical model.
Standard GD Label Noise GD
67.5
Accuracy
66.0
62.5
57.5
55.0
5
10
20
25
30
35
Noise Strength
Figure 1: Test accuracy of VGG-16 on CIFAR-10 with varying SNR. Label noise GD consistently outperforms standard GD, and the gap increases with the noise strength.
Theoretically, we characterize the properties of Label Noise GD in low SNR regimes, by considering the learning of a two-layer convolutional neural network in a binary classification problem studied in [8) and show that by randomly flipping the labels of small proportion of training samples at each iteration, noise memorization can be suppressed despite the low SNR, whereas signal learning experiences period of fast growth. As a result, neural network trained by label noise GD attains good generalization performance in regimes where standard GD fails, as summarized in the following informal theorem:
Theorem 1.1 (Informal). Given n. training samples drawn from the distribution in Definition 2.7 ((().. Then for any e >> O. after polynomial
in the low SNR regime where n -'SNR number of training steps (depending on e). with high probability we have: (i) Standard GD minimizes the logistic training loss to L < e, but the generalization error (0-I loss) remains large,
i.e., I 2(1). (ii) Label noise GD cannot reduce the logistic training loss to a small value (1) = 2(1), but achieves small generalization error (0-1 loss), i.e Le o(1)
2

---

We make the following remarks on our main results.
Improved Generalization due to Label Noise. The theorem provides an upper bound on the test enror of label noise GD and lower bound on the enror of standard GD. This demonstrates that incorporating label noise into the gradient descent updates improves generalization in the low SNR label noise GD learnability are weaker than those required
regime. We note that our conditions for SAM as specified in [10], even though our studied algorithm is arguably simpler and more computationally efficient see Section 3 for more comparisons.
Analysis of Feature Learning Dynamics. We establish the main theorem via a refined characteri- zation of the training dynamics of label noise GD on a two-layer convolutional NN with squared ReLU activation. A key observation in analysis is that label noise introduces regularization the noise memorization process, preventing from growing beyond a constant level; mean- while, signal learning continues to exhibit a rapid growth rate, allowing the model to identify the informative features and avoid harmful overfitting in low SNR regimes.
2 Problem Setup
In this section, we describe the signal-noise data model, the neural network architecture used for training, and the label noise gradient descent algorithm considered in this work.
Data generating process. We consider the signal-noise data model from 10 25
Let μ Rd
be a fixed signal vector, and for each data point (x, v), the feature x is composed of two patches, denoted as x (x²) E I2dd The target variable y is a binary label, taking values in {+1}. Then the data is generated according the following process.
Definition 2.1. We consider the following generating process for (x,y) y):
1. The true label y is drawn from a Rademacher distribution, i.e., Ply = 1]
- Ply -1] 1/2.
2. One of the patches, x(1) or x(2) is randomly selected to be ypu (the signal), while the other is set to be & ~00, of pup ||0|| ()) (the noise). Here, og denotes the strength of the noise vector.
We make the following remarks on the data distribution.
The data model simulates a setting where the input features are composed of both signal and noise components. Specifically, each data point is divided into two patches, and one of these patches contains meaningful information (signal) related to the classification label, while the other patch only contains random noise independent the label. The noise covariance of pp ll is set to ensure that the noise vector is orthogonal to the signal vector for simplicity.
This setup is designed reflect real- world scenarios where data contains mix of relevant and irrelevant features (see Appendix A in 2 for discussions). Note that in high dimensions (n < d), the NN can achieve small training loss just by overfitting to the noise component. Therefore, the challenge for the learning algorithm in the low SNR regime is to identify and learn the signal patch while ignoring the noisy patch.
We use the minimum number of patches in the multi-patch model for concise presentation. Our results can be extended to more general cases where the number of patches is greater than 2:
see 2 47 for such extension.
Neural network and loss function. Following 8 we consider a two-layer convolutional neural network with squared ReLU activation and shared filters applied separately to each patch. The network is defined as f(W, x) F41(N (W +1, F-i x),,, where
1 FW x) = m
(( (W x())))
1 m Σ
(WW)..) + ((WW,rr E.))
=
in which m denotes the size of the hidden layer, and (=) = (max(0, (0, =})². Note that j E (-1,+1] corresponds to the fixed sacond-layer. The symbol W, represents the collection of weight vectors in
3

---

Algorithm Label noise gradient descent
I: Initialize Wo, step size 77. flipping probability p [0.
2: for t = 0, ..... T - do
3: Sample c (1) Rademacher(1 p.p), Vi [n].
4: W((-) = W(() v/V w (W(),, where Lig (W(o)) = = Eiemm ((e/ yi ((W())
5:
end for
the first layer, i... W, j.1. w....... Wy.ml E Rdxm where wy.r E R is the weight vector of the r-th neuron. Here, j 1, +1} indicates the fixed value the second layer. The initial weights Wi1 has entries sampled from (V00, of)
Remark 2.2. Since do not optimize the 2nd-layer parameters, expect the 2 2-homogeneous squared ReLU activation to mimic the behavior of training both layers simultaneously in a ReLU network; such higher-order homogeneity amplifies feature learning (e.g., see [12] 2I) and creates significant gap between signal learning and noise memorization. Similar effect can be achieved by smoothed ReL.U with local polynomial growth in 2 47
We the logistic loss computed training samples, denoted as S {(x;, 9:) he(())
(s(W) = 1 Σ (lrf(W,x.))
VE(m)
where ((=) log(1 + exp(-2)) To evaluate the generalization performance of the trained network, we measure its expected 0-1 loss on unseen data, defined as
= Exx,))~(((() + sign(f(W.x)))
(I)
where D denotes the data distribution specified in Definition 2.1 and 1(.) is the indicator function.
Label noise GD for binary classification. We train the above neural network by gradient descent on either (i) the original loss function (standard GD), or (ii) the loss function with label-flipping noise defined as
LS(W()) (+)
1 Σ E(el (. xx)).
VEIN
Here, c,0) is a random variable equal to 1 with probability - p and -1 with i.c. cf Rademacher(1 - p.p). other words, labels flip with probability p independently at each step. Remark 2.3. We remark that label smoothing [45 49 and label flipping are equivalent expectation. This connection has also been discussed in (38). However, note that this equivalence in expectation does not imply closeness training dynamics due to the stochasticity introduced by the label-flipping
The label noise GD update is then given as follows:
(++1)
(t)
o' d' jam vi (22
VETT Σ
7
(1) d'w(
j.ns E.)) y.jE., (2)
TIM
where 77 is the learning rate, and we defined e0 (e, (W)() x;)) the derivative of the loss function. This label noise GD training procedure is outlined in Algorithm [ Observe that the proposed algorithm is computationally efficient, as the introduced label noise does not modify the original gradient descent framework. Hence this method is simple to implement, does not add significant computational overhead, and requires no complex hyperparameter tuning.
3
Main results
In this section, we quantify the benefits of label noise gradient descent by comparing its generalization performance against standard gradient descent (GD) training without label noise. We begin by outlining the assumptions that apply to both label noise GD and standard GD.

---

Assumption 3.1. Define SNR 2
We consider the following setting for both algorithms:
ayvd'
(i) data dimension = [maxx n signal-to-noise ratio SNR O(L/vT).
network width m (11) number of training samples n =((().
(iii) learning rate - 0
(iv) initialization variance Öno f 3-44/ do I Ó(min()lulll a "0,1///,p'//1 1--1-1/2)).
(V) flipping rate of label noise p lies in the interval p constant.
C log d ymn
)), where C is sufficient large
We make the following remarks on the above assumption.
The digh-dimensional assumption (i) is standard in the benign overfitting analysis of NNs (c.g., 8 18 ). The low SNR condition is derived from the comparison between the magnitude of signal learning and noise memorization see Section 4.1 similar conditions has been established in g 33 for different activations.
The requirements on the hidden layer size and the sample size being at least polylogarithmic the dimension ensure that certain statistical properties regarding weight initialization and the training data hold with high probability at least 1/d.
The upper bound on the learning rate ensures that the iterates in remain bounded, which is required for standard GD reach low training loss; see Proposition
The upper bound on initialization scale og is used ensure convergence of GD, and the lower bound is used for anti-concentration at initialization. Similar requirements can be found in [ Condition 4.2].
The lower bound ensures that the number of flipped samples concentrates around its expectation so that our theoretical analysis remains valid, while the upper bound on label flipping rate p prevents the label noise from dominating the true signal.
We first state the negative result for standard gradient descent (GD) without label noise.
Theorem 3.2 (GD fails to generalize under low SNR). Under Assumption 3.7 for any > O, there exists f O nm log( ((ua)vā))
+
), such that with probability at least d d-1/4 1/4 it holds that yjeoza
m
The training error converges, i.e., Ls( Ls(W())) Se.
The test error is large, iee. (w()) 2 0.24.
Theorem 3.2 indicates that even though standard GD minimize the training error to arbitrarily small value, the generalization performance remains poor. This is mainly because the neural network overfits the noise components in the input data instead of learning the useful features. Next, present the positive result for label noise GD.
Theorem 3.3 (Label Noise GD generalizes under low SNR). Under Assumption 3.1 there exists t = O num log(1(((nn)) vd)) + (olo6//((7olll)] 2))) and constants O, such that with probability at
1o7d
alli
least 1 - 1/4 it holds that
The training error is at constant order, ie., Lsf (s(()))== = O(1).
* The test error is small, i.e., (o((())) < exp
Cd .
Theorem 3.3 shows that label noise GD achieves vanishing generalization error when the input dimensionality is large (i.e., d = ((n²)) despite the low SNR.
Remark 3.4. Theorems 3.3 and 3.2 present contrasting outcomes for standard GD and label noise GD in the low SNR regime. In particular,
Standard GD minimizes the training error effectively but does so by primarily overfitting noise in the training data. This significant noise memorization Ieads to harmful overfitting.
5

---

In contrast, label noise GD introduces a regularization effect through label noise, which prevents the network from fully memorizing the noise components. This allows the network to focus on learning the true signal, resulting in phase of accelerated signal learning. Consequently, the model generalizes even though the training loss does not vanish (due to noise injection).
Comparison with sharpness-aware minimization [00] We briefty discuss the differences between our findings and those in [00] for the sharpness- sharpness-aware
aware minimization (SAM) method, where the authors established conditions on the SNR under which SAM can generalize better than stochastic gradient descent (SGD). However, their analysis requires the additional condition that the signal norm satisfies ||1|| > (2)1., indicating the necessity of sufficiently strong signal. In contrast, we show that label noise GD enjoys good generalization without this strong signal condition. This highlights the robustness of label noise GD in low SNR regimes (even when the signal strength is considerably weaker compared to the noise).
Comparison with stopping times across theorems. We compare the stopping times in Theorems 3.2 and 3.3] The stopping times for standard GD and label noise GD are not directly comparable, as they correspond to different evaluation criteria. Specifically, the stopping time for standard GD the number of iterations required for the training loss converge below a threshold e, whereas the stopping time for label noise GD is defined as the number of iterations needed to achieve sufficiently low 0-1 test loss. To enable a meaningful comparison, we derive the ratio between the two
stopping times under Assumption 3.1 By setting m² log والااااa
/e, we obtain Estandari
Plabel noise CD
(nSNNR*). According to Assumption 3.1 assume nSRRR < 1, which implies that label noise GD requires more iterations to achieve good test performance compared to the time required for the training loss of standard GD to converge.
O
4 Proof Sketch
In this section, we give an overview of of our analysis of the optimization dynamics of standard GD and label noise GD Our key technical contributions are summarized as follows: (i) Boundary characterization in low SNR regimes. Unlike previous studies [ 33 I0 that focus on the higher polynomial or standard ReI.U activation, we analyze the 2-homogeneous squared ReLU activation, leading to different boundary characterization of the low SNR regime for standard GD see Section 4.2 (ii) Upper bound via supermartingale. We apply supermartingale arguments with Azuma's inequality to bound noise memorization in label noise GD. This yields high-probability guarantees on training dynamics, previously unestablished in this context.
4.1 Signal-noise decomposition
To analyze the training dynamics, we adopt a parameter decomposition technique from exist {7g.3 and (o such that
8
33 there
1 # + Σ P 2
(3)
This decomposition originates from the observation that the gradient descent update always evolves (t)
in the direction of μl and x, for i [n)] In particular, 7j.r
(1) (w j.rn 11) serves the signal learning
coefficient, whereas Pj.n, = (w jum E.) characterizes the noise memorization during training. Next (t) let p/0 P).r, (3; j) and Lj... 1) -)). Combined with the gradient descent
(t)
(t)
update given by Equation (2). we obtain the iteration rules for these coefficients:
((+1)
"
(0) d'loo'(((W)) (0) ji 11
(4)
1=1
((+1) (1)
1 o d'((w'
j.m 1. 11 = j),
(5)
num
((+1) = e
")
f d' d'((w
j.r 1. 12 1 =-)-
(6)
nm

---

where the initial values of the coefficients are given by 7j.r
(0) (0)
0 and
Pj.r. 0 for all i E [n],
j E {-1, 1} and E [m]]
To analyze the optimization trajectory. we track the dynamics of signal learning coefficients (1),e)
and noise memorization coefficients (p)...) using the iteration rules in Equations 04 6 To facilitate
(8)
detailed analysis, we first provide upper bounds on the absolute value of both the signal learning and
noise memorization coefficients throughout the entire training process.
Proposition 4.1. Given Assumption 3.7 and > O. Let 3 2 maxian (1 jos 14)1,
(0)
(w (0)
j.r E
and a = 4 ). For I I T", where T = 17 "poly(n, m, d, 1|llll2 (o) o ;
for all E [n]. r E [m]] and j E {{- {-1,1} holds that
S 1j. I a, 0 0. Pj.m Sa.
(1)
(1)
log( (og(4n2/8)
(() j.,t 3 - 16V
no: aa.
The proof is in Appendix g Proposition 4.1 shows that throughout training. the absolute values of signal learning and noise memorization coefficients have logarithmic upper bound. This result is key for stage-wise characterization of training dynamics. Notably, this bound holds for both standard GD and label noise GD.
4.2 Proof Sketch for Theorem
We first establish the negative result for standard GD based on a two-stage analysis. As previously mentioned, we consider the 2-homogeneous (=) = (eLUU(2)) which differs from [
33 10
This
leads to key difference in the boundary characterization of the low SNR regime.
First stage. Notice that starting from small initialization, the loss derivative remains close to a constant. Based on this observation, establish the difference in magnitude between the coefficients of signal learning and noise memorization.
According to the update rule for the signal learning coefficient given by Equation and by setting
(t) 1 for all and E [n]] (i.e., no label flipping), the upper bound of signal learning can be achieved (2) (0) as jjr kw j.r: [a) S exp
(2 ,لl2 t) (w (w).r: pa) Meanwhile, the bounds for the noise memorization me
(0)
j.r
coefficients can be derived from the update rules (5) and (6). The results are given as max,,r le(() for all i E [m]] where we define 3 minje[m] max/e(m) (w be.r: E.), and use 1,(01 2 C1. In the low SNR setting,
3y (log(Smn/8)orge) Vd, and max p.r. exp
/CCroad tno //tpt//////-/o///pp/////// 2nom
where op v is much larger than ||m]| we observe that noise memorization dominates the feature learning process during the first stage, shown in the following lemma.
Lemma 4.2. Under the same condition as Theorem 3.2 and let Ti O nm log(1/(ooo, vdi)), the ga7d
following results hold with high probability at least ' (1) max jrr Pj.rs 2 1, for all E [n];
(Ti)
(1) (ii) maxj.ns | < ((auayyd)) for all t [Ti]: (iii) max Tg. < (0000000)))) 21))) for all E [Ti].
Lemma 4.2 indicates that when the SNR is sufficiently low, i.e., SNR = Ô(1 VT), noise mem- orization dominates the training dynamics during the early phase of standard GD optimization. We highlight that this tivation function. In particular, [8] assumed (2)) (max(0, with q > 2 and established a
condition differs from that of 88 B3) due to the choice of ac-
low-SNR boundary n SNR v 22(1,, whereas
33 considered the ReLU activation and derived
the condition n || oRd < 011.
Second stage. After the first stage, the loss derivative is no longer bounded by constant value. To prove convergence of the training loss L(t) S e, we build upon the analysis from the first stage and define w +m
+m log(2/e) En_ || "E;- We show that, gradient descent progresses, the
7

---

distance between W and W decreases until L(t) S e: ( w 1 | - W (L) 77.. Moreover, we show that the difference between signal learning and noise memorization still holds in the second stage, as summarized below.
Lemma 4.3. Let T2 o log (1/(1((0a,))) + +n mm 2d- Under the same
assumptions as Theorem 3.2 for training step t [Ti, T2]. it holds that V/ I Ō (oll)))))) l Lind
(0)
Ó(ana, VJ), and P 21 1. Besides, there exists a step E [Ti, T2], such that Ls(l)= <e
Lemma 4.3 shows that standard GD achieves low training error after polynomially many steps, and noise memorization dominates the entire training process, which results in harmful overfitting.
4.3 Proof Sketch for Theorem
3
We also divide the training dynamies of label noise GD into two phases. In the first phase, both signal learning and noise memorization increase exponentially despite the presence of random label noise. In the second phase, label noise suppresses the growth of noise memorization, causing it to oscillate within a constant range; meanwhile, signal learning continues to grow exponentially until stabilizing at constant value, which leads to beneficial feature learning and low generalization error.
First stage. Leveraging the fact that the derivative of the loss function remains within a con- stant range due to small initialization, we demonstrate that both signal learning and noise mem- orization exhibit exponential growth rates, even in the presence of label noise, According to the iterative update of the signal learning coefficient in Equation (4). the upper and lower bounds
are given as T3.r + +( j,r. 14) S exp
(e)
(0)
(2rl|a1 () j.r /4)), and max (73. + +(w j.r..)) >
( (maxye[m) (w]rr: p4)). respectively. Here Co is the lower bound for the absolute loss derivative. These bounds indicate that signal learning grows exponentially with the number of
exp( Sm
(0)
training iterations. On the other hand, from the update equation (5). we characterize the behavior
of noise memorization. Despite the injected label noise, we can show lower bound on the noise
(t) + 0.6] (0) memorization rate: maxy,- i. for the first stage are summarized in the following lemma.
f.r } 2 exp( (CCordd (W jar E.).. The main results 2nm
(0)
Lemma 4.4. Under the same condition as Theorem 3.3 and let Ti = O nm log((1/moodd)) ). Then
noya
the following holds with probability at least 1 d-
:: (i) maxj.r Pirm 2 0.1, for all i [n]: (ii)
(Ti)
| < Ö(anayVa) Vd), for all i [Ti]. (ii)) maxj,r for 33. 2 Ö p 12). for all t (Ti).
max
Lemma 4.4 states that both signal learning and noise memorization grow exponentially during the first stage.
In order to guarantee that the number of flipped labels remains within its expected range with high probability, we require p 52(1 ((1//V), where / is the number of training steps. We set / dd)((n)) according to Lemma 4.4 Together with the upper bound on from Assumption 3.1
we obtain = 52(1/ /mn).
For the analysis of label noise GD, one additional technical challenge is the instability of training dynamics caused by the injected noise, which we address as follows. For signal learning, we make use of the small label flipping rate p and aggregate information across all samples via concentration. Whereas for noise memorization (which is tied to individual samples), we leverage the broad range of time steps in the first stage to establish the overall increment rate.
Second stage. As shown in Lemma 4.4 the end of the first phase, noise memorization has reached a significant level, dominating the model's 's output. However, label noise introduces randomness in the labels, which affects the updates of noise memorization coefficients. We track the evolution of p j.r. via the following approximation. Define ( memorization under label noise GD can be approximated as
( p....)? The evolution of noise Em
nojdd
2 (()
(1 +
with prob p.
( (1+1)
(1
no
20 with prob p.
(I+exp(- (1 Jam
8

---

Unlike conventional approaches such as [8 [3], we analyze this process using supermartingale argument and apply Azuma's 's inequality with a union bound over the second-stage training period. Via a martingale argument, we show that noise memorization remains at a constant level with high probability. While noise memorization stabilizes, signal learning continues to grow exponentially. This discrepancy enables signal learning to eventually dominate the generalization. The analysis of the second stage is summarized by the following lemma.
Lemma 4.5. Under the same condition as Theorem 3.3 during t [Ti.T2] with T2 =
log(6/ (eellllll))mm exp(c2))n) [|ulll? there exist sufficient large positive constant C. and a constant depending on sample index such that the following results hold with proba-
bility least 1 1 1/d: (i) 104
41 S C.: (ii) Var I 0.1 for all j E {-1,1} and r E [m]]
(t)
(iit) 2m
(E ) S St S
2
(E 1Er=1
(() Pounis) and (iv) max)e[m]([5. + (0)
3.,pp)1 Z
m
ailull 16m (t I)) ma hr (w).r j.r 11)l
(0)
exp
Lemma 4.5 demonstrates that label noise introduces regularizing effect preventing the noise
memorization coefficients from growing unchecked, while simultaneously allowing signal learning to grow sufficiently large value. Building on this result, we show that both signal learning and noise memorization reach constant order of magnitude. Consequently, the population loss can be bounded by LD( (W(+)) < exx
corresponding to the second bullet point of Theorem 3.3
5 Synthetic Experiments
We conduct experiments using synthetic data to validate our theoretical results. The samples are generated according to Definition 2.1 The train and test sample size is 200 and Netest 2000, and the input dimension is set to 2000. The label noise flip rate is = 0.1. We train the two-layer network with squared ReLU activation using standard GD and label noise GD for t 2000 steps. The network width is m = 20 and the learning rate is 77 = 0.3. The signal vector is defined as 14 = [2, 0, O, ., 0] Rd and the noise variance is set to o 0.25.
Dynamics of signal and noise coefficients. In Figure 2 we present the feature learning coefficients defined in Section 4.1 the training loss and test accuracy for both algorithms. We observe that GD successfully minimizes the training loss to a near-zero value; however, noise memorization (p) significantly exceeds signal learning (?), leading poor test performance. In contrast, label noise GD does not fully minimize the training loss, as it oscillates around 0.5; consistent with our theoretical analysis, this behavior causes noise memorization to remain constant in the second stage, while signal learning continues to grow rapidly. Hence the test accuracy of label noise GD steadily improves.
Joly) 50
rRgeou, 151L
07
1.0
mettie (901
15.0
0.6
0.
12.5
0.0
7.5
03
1.0
0.2
2.5
0.5
930
1000
1500
2300
500
1500
Figure 2: Ratio of noise memorization over signal learning, training loss, and test accuracy, of standard GD and label noise GD. See Section 4.1 definitions of signal learning (r) and noise memorization (p).
Heatmap of generalization error. Next explore range of SNR values from 0.03 to 0. and sample sizes n ranging from 100 to 700. For each combination of SNR and sample size n, we train the NN for 1000 steps with 17 = 1.0 using standard GD or label noise GD. The resulting test error is visualized in Figure Observe that standard GD (left) fails to generalize when SNR O(n -1/2), which is consistent with our theoretical prediction in Theorem 3.2 On the other hand, label noise GD (right) achieves perfect test accuracy across a broader range of SNR, which agrees with Theorem 3.3
Additional Experiments and Extended Analysis. In addition to our primary experiments, we extend our analysis in Appendix G by evaluating Label Noise GD on deeper neural networks, modified MNIST and CIFAR datasets, different types of label noise (e.g., Gaussian), and higher-order ReLU activation functions, demonstrating its robustness across various settings.

---

Teal Armunty
Artumary
900
20
593
520
10
26
200
100
0.55
320
0109
(a) Standard GD
(b) Label Noise GD
Figure 3: Test accuracy heatmap of Standard GD (left) and Label Noise GD (right) after training.
6
Conclusion and limitation
We presented theoretical analysis of gradient-based feature learning in the challenging low SNR regime. Our main contribution to demonstrate that label noise gradient descent (GD) can effectively enhance signal learning while suppressing noise memorization; this implicit regularization mechanism enables label noise GD to generalize in low SNR settings where standard GD suffers from harmful overfitting, Our theoretical findings are supported by experiments synthetic data.
Limitations and Broader Impacts. Our current theoretical analysis is limited to a specific choice of activation function (squared ReLUU and network architecture (two-layer convolutional neural network). Extending this theoretical framework to more complex architectures, such as deeper or residual networks, would be a promising direction for future research. Additionally, investigating label noise GD under other optimization algorithms, including stochastic gradient descent (SGD) and adaptive methods like Adam, could provide further insight into implicit regularization effects in practical settings. This work aims to advance the theoretical understanding of generalization in neural networks. We are not aware of any immediate negative societal impacts resulting from this research.
Acknowledgments
We thank the anonymous reviewers for their constructive comments. WH was supported by JSPS KAKENHI (24K20848) and JST BOOST (JPMJBY24G6). TS was partially supported by JSPS KAKENHI (24K02905) and JST CREST (JPMICR2015), DZ is supported by NSFC 62306252 and central fund from HKU IDS.
References
[1] Zeyuan Allen-Zhu and Yuanzhi Li. Feature purification: How adversarial training performs robust deep learning. In 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS), pages 977-988. IEEE, 2022.
[2] Zeyuan Zhu and Yuanzhi Li. Towards understanding ensemble, knowledge distillation and self-distillation in deep learning. The Eleventh International Conference on Learning Representations, 2023.
[3] Jimmy Ba, Murat A Erdogdu, Taiji Suzuki, Zhichao Wang, Denny Wu, and Greg Yang. High- dimensional asymptotics of feature learning: How one gradient step improves the representation. Advances Neural Information Processing Systems, 35:37932-37946, 2022.
[4] Peter L Bartlett, Philip M Long, Gábor Lugosi, and Alexander Tsigler. Benign overfitting in linear regression. Proceedings of the National Academy of Sciences, 117645)330003330070 2020.
[5] Gerard Ben Arous, Reza Gheissari, and Aukosh Jagannath. High-dimensional limit theorems for SGD: Effective dynamics and critical scaling. Advances Neural Information Processing Systems, 35:25349-25363. 2022.
10

---

[6] Guy Blanc, Neha Gupta, Gregory Valiant, and Paul Valiant. Implicit regularization for deep neural networks driven by an Ornstein- -haeebbbe like process. In Conference on learning theory, pages 483-513. PMLR, 2020.
[7] Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et al. Language models are few-shot learners. Advances in neural information processing systems, 33: 33:1877-1901, 2020.
[8] Yuan Cao, Zixiang Chen, Misha Belkin, and Quanquan Gu. Benign overfitting in two-layer convolutional neural networks. Advances in Neural Information Processing Systems, 35:25237- 25250, 2022.
[9] Zixiang Chen, Yihe Deng, Yue Wu, Quanquan Gu, and Yuanzhi Li. Towards understanding mixture of experts in deep learning. Advances in Neural Information Processing Systems, 2022.
[10] Zixiang Chen, Junkai Zhang. Yiwen Kou, Xiangning Chen, Cho-Jui Hsich, and Quanquan Gu. Why does sharpness-aware minimization generalize better than SGD? Advances in neural information processing systems, 2023.
[11] Muthu Chidambaram, Xiang Wang, Chenwei Wu, and Rong Ge. Provably learning diverse features in multi-view data with midpoint mixup. In International Conference on Machine Learning, pages 5563-5599. PMLR, 2023.
[12] Lenaic Chizat and Francis Bach. Implicit bias of gradient descent for wide two-layer neural networks trained with the logistic loss. In Conference on learning theory, pages 1305-1338. PMLR, 2020.
[13] Alex Damian, Tengyu Ma, and Jason D Lee. Label noise SGD provably prefers flat global minimizers. Advances in Neural Information Processing Systems, 01277499-74666 2021.
[14] Alexandru Damian, Jason Lee, and Mahdi Soltanolkotabi. Neural networks can learn represen- tations with gradient descent. In Conference on Learning Theory, pages 5413-5452. PMLR, 2022.
[15] Jacob Devlin, Ming-Wey Chang, Kenton Lee, and Kristina Toutanova. Bert: Pre-training of deep bidirectional transformers for language understanding. In Proceedings of the 2019 conference of the North American chapter of the association for computational linguistics: human language technologies, volume (long and short papers), pages 4171-4186, 2019.
[16] Lue Devroye, Abbas Mehrabian, and Tommy Reddad. The total variation distance between high-dimensional gaussians with the same mean. arXiv preprint arXiv: 2018.
[17] Pierre Foret, Ariel Kleiner, Hossein Mobahi, and Behnam Neyshabur. Sharpness-aware min- imization for efficiently improving generalization. International Conference on Learning Representations, 2021.
[18] Spencer Frei, Niladri S Chatterji, and Peter Bartlett. Benign overfitting without linearity: Neural network classifiers trained by gradient descent for noisy linear data. In Conference on Learning Theory, pages 2668-2703 PMLR, 2022.
[19] Behrooz Ghorbani, Song Mei, Theodor Misiakiewicz, and Andrea Montanari. When do neural networks outperform kernel methods? Advances in Neural Information Processing Systems, 33:14820-14830, 2020.
[20] Ross Girshick, Jeff Donahue, Trevor Darrell, and Jitendra Malik. Rich feature hierarchies for accurate object detection and semantic segmentation. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 580-587, 2014.
[21] Margalit Glasgow. SGD finds then tunes features in two-layer neural networks with near-optimal sample complexity: A case study in the XOR problem. The Twelfth International Conference on Learning Representations, 2024.
[22] Andi Han, Wei Huang, Yuan Cao, and Difan Zou. On the feature learning in diffusion models. The Thirteenth International Conference on Learning Representations, 2025.
11

---

[23] Andi Han, Wei Huang, Zhanpeng Zhou, Gang Niu, Wuyang Chen, Junchi Yan, Akiko Takeda, and Taiji Suzuki. On the role of label noise in the feature learning process. In Forty-second International Conference on Machine Learning, 2025.
[24] Jeff Z HaoChen, Colin Wei, Jason Lee, and Tengyu Ma. Shape matters: Understanding the implicit bias of the noise covariance. In Conference on Learning Theory, pages 2315-2357. PMLR, 2021.
[25] Wei Huang, Yuan Cao, Haonan Wang, Xin Cao, and Taiji Suzuki. Quantifying the optimization and generalization advantages of graph neural networks over multilayer perceptrons. In The 28th International Conference Artificial Intelligence and Statistics, 2025.
[26] Wei Huang, Andi Han, Yongqiang Chen, Yuan Cao, Zhiqiang Xu, and Taiji Suzuki. On the comparison between multi-modal and single-modal contrastive learning. Advances in Neural Information Processing Systems, 37:81 17:815495 11888149-8166 1605, 2024.
[27] Wei Huang, Ye Shi, Zhongyi Cai, and Taiji Suzuki. Understanding convergence and gener- alization in federated learning through feature learning theory. In The Twelfth International Conference on Learning Representations, 2023.
[28] Jung Eun Huh and Patrick Rebeschini. Generalization bounds for label noise stochastic gradient descent. In International Conference on Artificial Intelligence and Statistics, pages 1360-1368. PMLR, 2024.
[29] Samy Jelassi and Yuanzhi Li. Towards understanding how momentum improves generalization in deep learning. In International Conference on Machine Learning, pages 9965-10040. PMLR, 2022.
[30] Samy Jelassi, Michael Sander, and Yuanzhi Li. Vision transformers provably learn spatial structure. Advances in Neural Information Processing Systems, 35:37822-37885 2022.
[31] Jiarui Jiang, Wei Huang, Miao Zhang, Taiji Suzuki, and Liqiang Nie. Unveil benign overfitting for transformer in vision: Training dynamics, convergence, and generalization. Advances in Neural Information Processing Systems, 37: 37:135464-135625 2024.
[32] Yiwen Kou, Zixiang Chen, Yuan Cao, and Quanquan Gu. How does semi-supervised learing with pseudo-labelers work? a case study, In International Conference on Learning Representa- tions, 2023.
[33] Yiwen Kou, Zixiang Chen, Yuanzhou Chen, and Quanquan Gu. Benign overfitting in two-layer relu convolutional neural networks. In International Conference on Machine Learning, pages 17615-17659. PMLR, 2023.
[34] Yann LeCun, Yoshua Bengio, and Geoffrey Hinton. Deep learning. nature, 521(7555):436-444 2015.
[35] Bingrui Li, Wei Huang, Andi Han, Zhanpeng Zhou, Taiji Suzuki, Jun Zhu, and Jianfei Chen. On the optimization and generalization of two-layer transformers with sign gradient descent. In The Thirteenth International Conference on Learning Representations, 2025.
[36] Hongkang Li, Meng Wang, Sijia Liu, and Pin-Yu Chen. A theoretical understanding of shallow vision transformers: Learning, generalization, and sample complexity. The Eleventh International Conference on Learning Representations, 2023.
[37] Hongkang Li, Meng Wang, Tengfei Ma, Sijia Liu, Zaixi Zhang, and Pin-Yu Chen. What improves the generalization of graph transformers? a theoretical dive into the self-attention and positional encoding. The Forty-First International Conference on Machine Learning, 2024.
[38] Weizhi Li, Gautam Dasarathy, and Visar Berisha. Regularization via structural label smoothing. In International Conference on Artificial Intelligence and Statistics, pages 1453-1461 PMLR, 2020.
[39] Zhiyuan Li, Tianhao Wang, and Sanjeev Arora. What happens after SGD reaches zero loss?-a mathematical framework. arXiv preprint arXiv:2110.06914, 2021.
12

---

[40] Zhu Li, Weijie Su, and Dino Sejdinovic. Benign overfitting and noisy features. Journal of the American Statistical Association, 118(544)2876-23855 2023.
[41] Miao Lu, Beining Wu, Xiaodong Yang, and Difan Zou. Benign oscillation of stochastic gradient descent with large learning rates. The Twelfth International Conference on Learning Representations, 2024.
[42] Samet Oymak, Ankit Singh Rawat, Mahdi Soltanolkotabi, and Christos Thrampoulidis. On the role of attention in prompt-tuning. In International Conference Machine Learning, pages 26724-26768. PMLR, 2023.
[43] Nasim Rahaman, Aristide Baratin, Devansh Arpit, Felix Draxler, Min Lin, Fred Hamprecht, Yoshua Bengio, and Aaron Courville. On the spectral bias of neural networks. International conference machine learning, pages 5301-5310. PMLR, 2019.
[44] Amartya Sanyal, Puneet K Dokania, Varun Kanade, and Philip HS Torr. How benign is benign overfitting? International Conference Learning Representations, 2021.
[45] Christopher Shallue, Jachoon Lee, Joseph Antognini, Jascha Dick-ickstein, Roy Frostig, and George E Dahl. Measuring the effects of data parallelism neural network training. Journal of Machine Learning Research, 20(1 12):1-49, 2019.
[46] Ohad Shamir. The implicit bias of benign overfitting. Journal of Machine Learning Research, 24(1 13): 40, 2023.
[47] Ruoqi Shen, Sébastien Bubeck, and Suriya Gunasckar. Data augmentation as feature ma- nipulation. In International conference on machine learning, pages 19773-19808. PMLR, 2022.
[48] David Silver, Aja Huang, Chris Maddison, Arthur Guez, Laurent Sifre, George Van Den Driess- che, Julian Schrittwieser, Ioannis Antonoglou, Veda Panneershelvam, Marc Lanctot, et al. Mas- tering the game of go with deep neural networks and tree search. nature, 529(7587):484 489, 2016.
[49] Christian Szegedy, Vincent Vanhoucke, Sergey Ioffe, Jon Shlens, and Zbigniew Wojna. Re- thinking the inception architecture for computer vision. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 28 2818-2826, 2016.
[50] Shokichi Takakura and Taiji Suzuki. Mean-field analysis on two-layer neural networks from kernel perspective. The Forty-First International Conference on Machine Learning, 2024.
[51] Alexander Tsigler and Peter L Bartlett. Benign overfitting in ridge regression. Journal of Machine Learning Research, 24(123):1-76, 2023.
[52] Roman Vershynin. High-DDmensional Probability: An Introduction With Applications in Data Science. Cambridge, UK: Cambridge Univ. Press, 2018.
[53] Loucas Pillaud Vivien, Julien Reygner, and Nicolas Flammarion. Label noise (stochastic) gradient descent implicitly solves the lasso for quadratic parametrisation. In Conference on Learning Theory, pages 2127-2159. PMLR, 2022.
[54] Zhichao Wang, Denny Wu, and Zhou Fan. Nonlinear spiked covariance matrices and signal propagation in deep neural networks. The Thirty Seventh Annual Conference on Learning Theory, pages 4891-4957 PMLR, 2024.
[55] Zixin Wen and Yuanzhi Li. Toward understanding the feature learning process of self superviedd contrastive learning. In International Conference on Machine Learning, pages 111122 112-11122. PMIR, 2021.
[56) Zhiwei Xu, Yutong Wang, Spencer Frei, Gal Vardi, and Wei Hu. Benign overfitting and grokking in reLU networks for XOR cluster data. The Twelfth International Conference on Learning Representations, 2024.
13

---

[57] Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning (still) requires rethinking generalization. Communications of the ACM, 64(3):107- 115, 2021.
[58] Difan Zou, Yuan Cao, Yuanzhi Li, and Quanquan Gu. The benefits of mixup for feature learning. In International Conference on Machine Learning, pages 43423 43479. PMLR, 2023.
[59] Difan Zou, Yuan Cao, Yuanzhi Li, and Quanquan Gu. Understanding the generalization of Adam in learning neural networks with proper regularization. The Eleventh International Conference on Learning Representations, 2023.
14

---

Appendix
Contents
Additional related Works
16
Preliminary Lemmas
16
Proof of Proposition 4.1
17
Standard GD Fails Generalize with low SNR
19
D.I Proof of Lemma
19
D.2 Proof of Lemma 4.3
21
D.3 Proof of Theorem
22
label noise GD Successfully Generalizes with Low SNR
25
Proof of Lemma
25
................................
Proof of Lemma 4.5
29
Proof of Theorem 3.3
33
F
Experimental Details for Figure
35
Dataset and Noise Injection
35
Model and Training Setup
35
F3 Results Analysis
36
Reproducibility
36
Additional Experiments
36
G.1
Deeper Neural Network
36
Real World Dataset
36
G.3
Different Type of Label Noise
38
G.4
Higher Order Polynomial ReLU
39
15

---

A Additional related Works
Label Noise SGD. Recent works have empirically shown that label noise stochastic gradient descent (SGD) exhibits favorable generalization properties due to the regularization effect of the injected noise [4 [3]. From a theoretical standpoint, label noise SGD has been primarily explored in the context of linear regression or shallow neural networks, particularly in regression settings [6] [3 24 28 39, 53 50]; these studies have highlighted the implicit regularization benefits of label noise in SGD. For instance, (50) illustrated the implicit regularization of label noise in mean-field neural networks, while [39] 13 proved that label noise introduces bias towards flat minima. In contrast to these existing literature, our work focuses the binary classification setting specified by the signal-noise model, providing a quantitative analysis of the training dynamics and the generalization benefits of label noise GD in the low SNR regime.
Signal-Noise Data Models. Recent theoretical works have studied the signal-noise model in various contexts, including (i) optimization algorithuss, such as Adam [59]. momentum [29], sharpness- aware minimization [10], large learning rates [41]; (ii) learning paradigms, such as ensembling and
[58 II] adversarial training T. and prompt tuning 42]; and (fii) neural network structures, such as convolutional neural network [8 333, vision transformer 30, 36), graph neural network [25] 37). Our work is in line with
knowledge distillation 22, semi-and self-supervised learning [32 [55) Mixup
[9,25), with the goal of showing that a simple algorithmic modification (label noise GD) facilitates
feature learning in the challenging low SNR regime.
B
Preliminary Lemmas
Lemma B.1 (8) Suppose that d >> 0 and d = (llo(4n/00)) Then with probability 1 - 6,
o2d/2 |6. S 30fd/2,
K5 Ex)l < 20 /ddlllogn2//))
for all i, o iic [n].
Lemma B.2 (8) Suppose that d 2 (0lggm///)) = ((llog(1/))) Then with probability at least 1 8, it satisfies that for all r E [m], E [=1], E [n].
K( for u)) S (2log(mm/0)ollll
(0)
(( j.r E.) < 2 2l1g((8mm/000oom
for all j {=1), E [n]
aollu|12/2 < max j(w (0) rE[m] j.r: 11= < v log(Sm/ 11
000 /d/ S max j(w (0) rE[m)
j.r {,) s 2
Lemma B.3. Let S( {i (t) =1} and S {i yt = j}. Then Vt 2 O. we have following with probability at least 1 - 5,
1. ||8 - n(1 pp) - V //2 log 47"
and |||(]] - -mpl S V 2
log
4T 8
2. The size of set follows, Vj E {+1}
1 ns,
(1 - p)n
n
8T
|1S n nsyl
pm
n
87
log
<
log
2
2
2
2
8
llog(8T 18) D2
18T (8) (1 (1-p)²
Suppose n >
we have
( nSyle
(2 3p)n
(2
p)n
( nSS]
pm
3pn
E
4
4
4
4
16

---

Proof of Lemmal B.3 By independence, we have E|5 (1 - p)n and 1 pn. By Hoeffd- ing's inequality, we have for arbitrary O,
2T P(IIS 1-pm 2 2) - 2exp (-
2T
P(II5411 - - p)m] 2 r) S exp (
n
n
Setting T (mm/2))og(4//) and taking the union bound over (TM] gives
|| - (1 p)ml - V n log (42))
n2 ||S - pnl 1 V 2
47'
log
2
8
which holds with probability at least 1 - 8.
Similarly, by the same argument, we can show the result for | S and ( nsyl.
8 8lom(87" /6)
8 8 (8) then we have with probability at least 1 8, we have
Suppose 2
F
(1-p)
| (1)
nsyle (2 3pmm (2-p)
3pm
Lemma B.4. Let S = {8 ss: ( +1}.
Then for any i E [n], 1 > 0, with probability at least
1 1-6, 6,
1. ||S (0) (1- p)t| S v log( 4n) and ||S ptl S log( 4n)
log (l0g(4/88) we have |5 E (2-3p)t 3p)t (2 (2-pl 15 E pt 3pt
2. In addition, suppose
2
Proof of Lemma B.4 By independence, we have E|S (1 p)t and B|s pt. By Hoeffd- ing's s inequality, we have for arbitrary > O,
27 272) t
2T
PIIIS - (1 - p)1 2 7)
exp
P(IIS! - pll 2 T) S exp (
Setting
((t//))oog(/// and taking the union bound gives
|| (1 p)d| S V22 2
t
4n
||S pl] S V 2
t
4n o
log
log
which holds with probability at least 1 - 8.
Suppose 2 28))(4n/5)
>
2 (4g then we have with probability at least 1 - 5, we have
(1 (1-p)²
[
E (2- (2-3pht 3p
(2 p)t
18 E 2 2
C Proof of Proposition 4.1
In this section, we provide a proof for Proposition 4.1 which establishes upper bounds for the absolute values of the signal learning and noise memorization coefficients throughout the entire training stage. Additionally, we present some preliminary lemmas that will be used in the proof of Proposition 4. as well as in other results in the subsequent sections.
Lemma C.1. Suppose that inequalities 77) and 8 hold for all r E [m]) j E (-1,1), i [n] and
t e [0, T* For any 8 > O, with probabiliry at least 1 8, it holds that
log An2/8
Kw j.r
w
3 E.) - (1)
(0)
- < 8//
na,
d
kw j.r 30 - 7 = O.
C.1 From the signal-noise decomposition of w (t) j.r we have
Proof of Lemma
kw (1)
(.reE,) E.)
(0) P
(a)
1i7, (,.
EM Σ (Er
(0)
j.r
(b) log(4n2/8) na,
8V d
17

---

where (a) follows from the weight decomposition, and inequality (b) is due to Lemma B. and the (c)
upper bound of Pjanr based on inequalities and
Next, for the projection of the weight difference onto the signal vector, we have:
(t) 1o (.. 7j.r Kw
(8)
Pind
1 = O,
where the equality holds because (5:; - 0 for E [rx] due to the covariance property of the noise vector distribution.
With Lemma C.I in place, we are now prepared to prove Proposition 4.1 The general proof strategy follows the approach outlined in ( However, we present complete proof here for the sake of clarity and to provide unified analysis for both gradient descent and label noise GD.
Proof of Proposition The proof uses induction and covers both gradient descent and label noise gradient descent.
At / 0, it is straightforward that the results hold for all coefficients, they initialized zero Now, assume that there exists a time step I' such that for [1, 7'J the following inequalities hold:
(1) S 7ir S a, 0 Pjrs Sa,
(0)
log( (og(An2/8)
0 1nd - /
no 2 aa.
To complete the induction, we need to show that the above inequalities hold for / = f + First, we examine +((++1) for -Bs since (T+1) = 0 when j = Ys by definition. Using Lemma C.1 if Eir.
((T) S -0.58 8v Jin
log(An2/14 nai have
d
(w/ (T) f0r Ex) S e, +8 d na + (w(0) f. Ei)
1og(4n2/0)
E.) S O.
Thus,
(++1) = (T) +
17 (f))
E d'((w (P)
jr 113
log(4n2/0
(T) 2 - - 16
= =gins
na,
where have used o'(w the update function implies:
(f) j.r
{.)) 0. On the other hand, if p(())
-0.53 8y
log 2n2
jjr,t
0 (++1)
7
(T)
E.)
1E.11
-jr.á
nu
log 4n /8)
3n0 2nm
log(4n2 ((/42//))
0.53
8/
(0.53 + 8V
na)
d
d
log log(4n2/8)
8 161
na.
① ( and (w)r E.) 0, follows from Lemma B.1 and (c) holds
where (a) is due choosing
6;
when 7 <
2mm 3o2d
18

---

Next, consider (2+1) for j Vs- Let Ti be the last time that Pj.r. S 0.5c. By propagation, we have: Pj.ra
(T+1)
(T1)
1
f, (()))
((W jir EA
(T1)
E
"
19 1.
Pjira
= =Pjrr
nm
nm
R RiSt
0.5a +
(w (Ti) 1 + E
(0)
(w 3. 1E
nm
Tu
TIEIST
3nozd
/0) na)
0.5a +
(0.5a 3 3 1
2nm
d
3
log( log(4n2 (4/42//00 na)
+ Σ
exp(-4o> + 2nm
(a + 3 16V
(c)
S 0.5a + 0.25a + 0.25a = a:
where (a) holds since (((h)) 2 -1 and E ( < for all e [Ti, fT. (b) by Lemma B.1 Lemma C.1
and - (0) < exp(-Ff, +1) 5 exp( 4a +1). Here we have used that 3+ 16
log(4n2 /8)
na S 2a
d
with the condition that d = (n and 0 I (1) min(llell?" , .0, d-2/).. The final inequality (c) holds because 7) = ( oza and exp(-4c² + a)a < 1 with "Tog(T").
Similarly, we can prove that (f+1) proof.
< a using n = O [imb which completes the induction
D Standard GD Fails to Generalize with low SNR
D.1 Proof of Lemma
In this section, we provide proof for the result obtained in the first stage of gradient descent training. Several preliminary lemmas are established facilitate the analysis.
Lemma D.1 (Upper bound on (.)) Under Assumption 3.1 in the first stage, where 0 S.ST.
log(1 (angg there exists an upper bound for Vir for all j E (-1,1), E [m]]
(0 3
+ (w
(1) 14) S exp (.r:14)
27|1
1) kw (0) 11)-
Kw 11)-
m
Proof of Lemma D.1
By the iterative update rule of signal learning, we have:
(a)
(1+1)
(1)
17
d'(w (0)
j.r 311
nm
(8) (0)
(0) (y: yor 1a) + 5 1
T5.
(0) (t)
21
+ (( f.r 1)
0 1, (b) is derived using Lemma C.I and (c) is due the properties of the squared ReLU activation function.
where (a) follows from
Defin A(0) = 7 + ( p.). Then, we have:
(0)
11+1] < (1 2ml p1 1 A < (1
+1+ 2n 11 (1) (0) < exp
2n 1411 A
19

---

where we use + I exp(x). This suggests:
2 20ll 1)
(0 Fis + (w j.r 1a) I exp
((
(0) j.r 14)-
m
Lemma D.2 (Upper bound on 3, Under Assumption
3.1 in the first stage, where 0 S
nm loggl//////// ( there exists an upper bound for 1 for all j,r, i:
L = =(000,
Proof of Lemma D.2 The proof uses the induction method. By the iterative update rule for noise memorization, we have:
0 ((+11)
+
7
d'w(w) J.r E.)1E
J.na
+ 3m0 o' ('ww" jir {.) + 161
log (4n² (4n2/8) na + f...)
(0)
2nm
d
3noed
(t) +
/log(8mm//)oo0z
nm
where the incquality (a) is by the upper bound on 14, (0 s Inequality (b) is derived using
Proposition 4.1 Lemma B.1 and Lemma C.1 Finally, the inequality (c) uses the fact that e and Lemma
Taking telescoping over t form 0 to Ti, we obtain:
3no
(T))
Ö(oup vd),
mm
where we substituted Ti = O am log(L((mnn,
thereby completing the proof.
yo
Lemma
D.3.
Let B
minse[m] max+e(m) (Win.r E.)- (n a.
Suppose that du
160ng
logl an² (5)
(op SopVd--l a. Then it holds that B 2 40ng log(
Proof of Lemma D.3 The proof follows directly from Lemma B.2
With high probability, we have:
2 o d/ 44 Substituting the condition on oo. we obtain:
log(An?
B 2 40m
d
Lemma D.4 (Lower bound on p/1)) Under Assumption
3.1 in the first stage, where 0 S t
(ggg)//ang vd)) there exists a lower bound for max Pirio for all E [n]: no
C20
max P
+3 exp
t)ooo dd4.
2nm
Proof of Lemma
D.4
By the iterative update rule for noise memorization, we have:
max 1
3.r jar
(1+1)
(0)
max 3.
+ max
1/1 d' ((w j.r: (.))
nm jr
+ nod o' o'(ww))) j.r. E.) 16
log (og(4n?/0 (4n2//)) /5)
(1)
(0)
na + p.0))
max P J.r
Para
J.
2nm
N6
(1)
(max (1)
+ B),
2
max Pj.r. 3.P
j.r.s jir
5
nm
20

---

where the inequality (a) is by the lower bound on |2,00 C1 in the first stage; Inequality (b) is by Lemma B. and Lemma Finally, the inequality (c) is by Lemma D.3
Define B. ( = maxj,r j.r Jint + 0.63. Then
B ((t))) 2 (1+ Cio D 2 (1+
C1 (1) B 2 exp 2nm
1io
)
t) t)
nu
nmm
where we used 1 + x 2 exp(x/2) for x 2
With the above lemmas in place, we are now ready to prove Lemma 4.2
Proof of Lemma 4.2 We choose the end of stage as Ti
inm
(og(L/( Then by Lemma
yaža
D.4 we conclude that maxx,r Pjrd 2 1, for all E [n|]. Besides, by Lemma D.2 we directly obtain
the result that
3
v /
nm
Finally, Lemma D.1 yields
20 4nm
(TT)
+ [w jir: 14) S exp
log(1 (//(1//(0oo/ (( (w)))))ww))))) (w.) 14) S 2/(w j.r: 14)1
nona
where we have used the condition of low SNR, namely nSNR2 < 1/1o(000,,)) By Lemma B.2
conclude the proof for maxx,r 7i. ((0ollull2))
(Ti)
D.2 Proof of Lemma 4.3
In this section, we provide a complete proof for Lemma 4.3 based on Lemma 4.2 and an iterative anal- ysis of the training dynamics. We introduce several necessary preliminary lemmas that will be used in the proof for E [Ti, T2] with T- .7 o 'm log (1/ (/00 VV)) + n - 2d-1,
Lemma D.5 (18) Under the same condition as Theorem 3.2 for all t E [Tr Tbl and E [n]. the following properties hold:
VVLs(W( (1) O(o7d)
(T)) W' = Ó( 3/2 1/2 op d=
ye (V x;), W (2ge2/))
With the above lemmas at hand, we are now ready to provide the complete proof for Lemma 4.3
Proof of Lemma 4.3 We start by showing the convergence of gradient descent. The key idea is to
construct a reference weight matrix W' defined as w = w)rr + 2m log(2/e) El= ||all "s..
Summing the above inequality from ((() and W
(!((
w (++1) w
1
-I
11 - w L.VLs(WW)) W
(V ( W*) - (
(a)
20
2y ((W() xx)) (V/(W() x,). w - - (
n
2n
12. x.) - 210g(2/e)) -
4n
Σ
e/2] - - W
2n(Ls(WWll -c),
21

---

where in equation (a). we have applied the homogeneity property of the squared ReLU activation. The inequality (b) is by (Vf(W(o) x.). W 2 2 ( as stated in Lemma D.5, and the incquality (c) is due the convexity of the logistic functtion. Finally, the inequality (d) is by Lemma D.5 and the condition on the learning rate.
Taking summation over the above inequality from T1 to T2, we have
|
W 11 + me(T2 Ti +1
Ls (W
2n
( W
Ö 'm² m nop -)
(9)
where in the second inequality, we have applied Lemma D.5 Finally, plugging in the T2
=
"opemmm"n + 1-==)/1 0p" ' 2m (og(1/(oo0,,)))) VV),, we achieve Ls (s((()) S
Next, we provide the lower bound for the noise memorization coefficient p/ and the upper bound
for the signal learning coefficient 75.r in the second stage. For the noise memorization coefficient, using its update equation:
jir, 7 d'w jast EDMEE P.
Pj.r
Here, we have used é 0 and property of the squared ReLU activation. This implies that Pj.r, (2)
(e)
never decreases during training. Therefore, we have maxj,r Pj.r.i 2 1, for all i E [n] and t E (Ti,Th)
For the signal learning coefficient, use the induction method. From Lemma 4.2] we know that (Ti)
maxj,r G.r = (110) _ B. Suppose that there exists T E [Ti, T2] such that maxj.r 75r S 2B for all / E [7i, T). Then we analyze:
(t)
T
(T+1)
(T5)
(t)
o' ((W Jor 11)111
25
I=
1=1
2m
T
n
(T))
TUT
t=
(8)
2
(T))
11411 Σ
L (W(1)
num
t=
(c)
2m
(1L)
| |u112((1 Im no 2d
1j.
nm
(d)
< 75
(2))
+ Ö(SSNR²)
< 28.
where the inequality (a) is due to Lemma C.I
the inequality (b) is by 14 < C, for i E [n]. and
inequality (c) is due to the inequality (9) Finally, the inequity (d) is by the condition that
SSNR = (1). Similarly, with the induction method, we can show that lp(t)
jinal S ((00g
D.3
Proof of Theorem 3.2
To complete the proof of Theorem 3.2 we provide a proof for the generalization result.
(t) Lemma D.6. Define g(E,) 1 ESr a(ww j.r: E.)). Under Assumption 3.1 there exists fixed
vector with ||v||2 S 0.02ap such that
Σ SE(#1)
Lo(ie, + vv s(E.) 2 112331111
22

---

Proof of Lemma D.6 To proceed with the proof, we construct the vector v -
A
-iy Ei where
0-00000/vv //n1///n.. Then we show that
Ivl12
a|
Σ
E/l2 = =
Σ E
Σ
Ei)
X² Σ
| 2 2X
Σ
(5 Eg)
S Xno + 4n 2222200 V 2d log (4n² 18)
3 4X 4x no 0.02
where the first inequity by Lemma B.1 the second inequality is by 2 ((n"), and the final equality is by À = 0.01/Vnd which confirms that ||vl2 S 0.020p-
By the convexity property of the squared ReLU function, we have that
a((w 1. E. + v)) ((w (.) (.) 2 d (( (1) E.)) (0 v),
((w f.r E, + v)) <(w {,) 2 d' (( -.,)( v).
With the above inequalities, we have that almost surely for all Eز:
a(w (4) ((Wir E + v)) (( (.w.f.r))))))))..).)))))). E.)) o(w -E, + v)) o((w() -E,)
4lW ( v).
On the other hand, using the properties of the squared ReLU function and the triangle inequality, we have:
0 -w E: + v)) aowww( E.)) + ((w ((. -E; + v)) -Ei)) ((w -1. E,) + (w -r. v)1) + (- (-(w - + -(w v)1) - (w E.)
(w -1, Ei) + 20((w[ 1,, v)12.
Next, we compare (( i,rr v)] and (w (w-" 1,, v) with (ww.f.ea) and (w Ed).. We show that
(t)
I( [( -1, v)1 lIO Σ
(t)
+ (w!
(0)
-i. Iir
::y==1
X(n Xmny 11gmm2mmmmmmmm 8)) Vdl S Xn/4,
where the first inequality is by Lemma B.2 and Lemma 4.3 and the second inequality is by the condition on og from Assumption 3.1 Besides,
(1) v\ = X/( Σ Pi.ra + (w (0)
Σ E.)
1,m3
=1
====11
2 X(n - / log( 2mm/0))ooa 2 An/2,
where the first inequality is by Lemma B.2 and Lemma and the second inequality is by the condition on do from Assumption 3.1
Finally, by Lemma
B.2 Proposition
4.1 and Lemma B. holds that
[w 1. {.)l = 1(w (0)
1. E +
( f
||E 1a E.))
1og(4n? (4422/)) Vna.
Vo +//
d
23

---

On the other hand, it is observed that (wi.r wi.r Ex) ~ (N o..),
-wi.
where the variance ow follows
Pir crA))
(0)
(j..a) 111
2
) 111,,112
2 P
1
Σ
(4)
3d
6d
where (a) is by Lemma B.1 and condition on d from Assumption 3.1 (c) is by Lemma
(b) is due to Lemma B.1 and
By the anti- ontiiconcenttation inequality of Gaussian variance, we have
TV6d
P([(w],r 1.r
w (0) E. $ 7) S 2erf( V20
S
2erl(
2nn
12d
< <2
exp(
4N
Then with probability least 1 - 6, it holds that
kw
(2) 1,r w 1,r G.>1 2
(0)
m log(
TnJ²
V
12d
- -(6/2)2
96d
where we have used log(1 (1 + x)) 2 Together, we conclude that
x for x > - and 82 $ 1/8. 1tz
Σ
Lu(ie, + v) - -g(E))) 2 4 E. 12 v\1 + kW -)
E,) + "l v)12
)E(+1)
knd²
2 4(1/2)
2 450 4
96d
where the final inequality holds by oî < ( with chosen as d 1/4 thus completing the proof.
Proof of Theorem
3.2 For the population loss, we expand the expression
1.
(W())) E (xxx))DD
(1 (y
# sign(/(W:
x)) = Ply/(W(() x) < 0)
1 m
P
((w (1)
Mort {.)
m Σ ((w y.rr {2) 2
(w p.rt m/4
1
a a(w yori B41))
Recall the weight decomposition:
(0)
+ + Σ
11:111 -5: + Σ e 15
j.r +
Then we conclude that:
(w (1)
-g.rr m1z) {w (0)
-y 012) (1)
7-
(w p.rr 8114 (w (0)
u.r. 314) + 7g.
(t)
24

---

First, we provide the bound for the signal learning part:
1
Σ
m
(0) y.r 814))
Birt
m
m
a
(1) Wirt
yu))
a
(0) MiF yu) + +7g9f) ((
m
(( (.r. ypu)
(9)))
x 1111)
where the first and second inequalities follow from the properties of the squared ReLU function, and the last inequality is by Lemma B.2 and Lemma 4.3
Denote that g(E)) j Ej. o ((w) 3.r E.)). It follows that:
Plyf(W(), < 0)
m
1 m
1 m
1 m
= P Σ a((w vort Ei)
Σ
((w
(1)
(.)))
m Σ
o((
Mort m(m)
())
Σ o o(ww yart y1))
pirt
m
2 0.5P (19(5,) (.oP)))())))
2 2((081 | 11))
Define the set A (E, Io((,)) ) 2 2(o0) 1 [1))).) By Lemma D.6 we have:
Σ JE(LI}
Lolit, + +v) --(()) 2 45(0ollm13)
Thus, there must exist at least one of e,, E, vv, -E, and E, that belongs A and the probability larger than 0.25. Furthermore, we have:
(P(A) P(A v)l FE E A) (E.-Nir.egn(EE A)I
| 20,
< 0.02,
where the first inequality is by Proposition 2.1 in 16 and the second inequality by ||vl2 S 0.01 according to Lemma D.6 Combined with that ((A) (P-))P finally achieve that P(A) 2 0.24, corresponding to the second bullet result, Combined with Lemma 4.3) which establishes the first bullet point, this completes the proof of 3.2
E label noise GD Successfully Generalizes with Low SNR
E.1 Proof of Lemma
Lemma E.1 (Lower bound on Tz.))
(1) Under Assumption 3.1 during the first stage, where 0 S
( T nm Log(a/(aoo there exists lower bound for Yarr for all j:
nord
max
(1) +
1( (WWW0//1)) 2 exp
(0)
1)
max (( (()(0) (0) j.r 12).
[m(m]
8m
rE(m
where Co is the lower bound on 17 Co is the first stage.
25

---

Proof of Lemmal
E.1
If ((w (1)
jirt 14) 2 0, then
(1+1)
(1)
1 o' ((W) j.r Bi 1
7/r
(t)
00 0' d'((w
Σ
2000 o' ((w J.r. (113) 11ee13
nm
RES
1ES
(8)
21
(1)
Σ
(w/r
( 1111
mm
iESions
is
(4)
2n (Cols niil n 155h nnll) (w (t) 14) p
3.r
mmm
Note that we have defined 5 {i
(t) 1 and Sj = {i: y; 5} in Lemma B.3
On the other hand, when (w (1) j.r 14) < 0,
(t+1)
(t)
21
7000
- jirt p
nm
iES(fns
is
(8)
21 (Cols 1-11--15 n (18-1)((- (t) 14) 11)1
nm
By Lemma B.3 we have
S ns ( ns_
2 (1-p)r p)n v 2n (0g(87//)
( nsi ( n
pm + / 2m log 15)
| S1,1 ns-1 2 (1 p)n 22 2n 18)
These hold with probability at least 1-5. This suggests that when p < Co/6, 2 2 log(8T we have:
(sf2nii
2
S nsii>
2 -5 ns
C
Co
S S ns
n 4
Hence, we have:
7jr 2 75r +
((+1)
(0)
Co
(w (1)
j.r 11) = =15 +
Coalleel2 (0)
4m (.r 1) + j7
(
10 if (W 1) 20 if (f (. jir 1) < <0.
4m
Corllael
(w j.m 11) = //5 Coallpul1 ((w j.r:
(++1)
(1)
=g
(1)
((w 1²) + )2
4m
4m
(1) When j 1, due to the increase of Ti.r we have
((+1)
(0) Conilul
(ww 1. 12) + (..)
71 2 7i
4m
Let BB"h max 6:500- + j(w (0)
j.r 14) }. then we have
B (((+1) > (1 +
Conllu B(C
12
2 (1+
Covllaal3 12) 13(0)
4m
4m
Conillul
2 exp
max (w//// 1.0 14)
8m
Conileul Gol|Mal22
exp
8m
2
where we use the fact that + x 2 exp(x/2) for z 5 2.
26

---

Similarly when j -1, we have
7-1,- 2 7-1,r 4m
((+1)
Conllall ((w
-l. 1,r: pe) -
(0)
and
Bl 2 (1 Conll 1 BB99 2 (1+
Coallee 'B!1
4m
4m
C
t) max/ -w -w (0)
exp
8mn
[Cnmllull 2x) 001|44122
exp
8m
2
Thus, we obtain B 2 exp (
(Colllal
colluell 2
Vj E {=1}.
8m
Lemma
E.2. Let B
min max,e m) (w (Weers E.)-
Suppose that
1
log(An2 (6)
(op vd) -
Then we have that 3/d 2 40n
log(4n2 (8)
d
Proof of Lemma E.2
The proof follows from Lemma B.2 It is known that, with high probability,
we have 3 2 000, d/4. By substituting the condition for dg we obtain
1og(4n2/0)
3/d 2 40m
d a.
Lemma E.3 (Lower bound on Pjrg)) Let 3 mingela) max (0) E.) and (0)
Pl.r. Wirr& Ex) V.4 Under Assumption 3.1 if (w ( (. E.) 2 B. then time step
T um (onee/ with high probability, it holds that nogd
Cooo 2nm
A (1)) Burd 2 (1 +
yth A!
Aura
Proof of Lemma E.3 First, consider ys as the case of Pj., By Lemma C.I and Lemma D.3
(t)
when y = j.
log log(4n2/0 4
W Jin. E.) - (w)) [w].. E.) - - S 1
S 0..3////4
(10)
d
From the update of (1)
jrn when (1) = and (w (t)
(w(0) 5.) > O.
j.r
(1)
21 for E,>1l. 1l
(1) 2 P).r. +
(t)
Coo (1)
Piins + (w])) E.) -
Pj.rd = Pjrnt
nm
nm
On the other hand, when c
-1 and (w wo E,) > 0.
p( P
2n 1 (8) 13
(t) > p/11
3no2d ((t)
Pjrnt + (w/0 E.) 0..4//0/4)
nm
am
For simplification of notations, denote Ç = 0.83/ 4/4 Let (t) Then when 1, we have
Mr.r.i == P/. (w j.r E.) - -0.3/////
A (++1) (1 nooddd (1)
nm
and when e00 -1, we have
3no d
3n0
A (++1) Bird
(1
num
YUT
Here prove when (w Ex) 2 (1)
The proof is by the induction method.
27

---

Murr (w (w E.) 0.5ç because d > ( Then we consider when t _ 2 (where the condition for Lemma B.4 does not hold). In this case, | 2 p²
First it is clear that A (0)
(1- (1-p)t p)t V log( on ), 1,155 S pt + v log( ).) In addition, the worst case lower bound is achieved by the case where all the s events happen at the first few iterations. This gives
nCoozd y( v logl T (1
3no jurt
A ( M..r, (1
V
log( + F
(0) ye.r.
mm
num
- (1 "o ) (1- losl
pt++
log +
3 x
nm )
nm
3nm
(1 Cooodd (1-p)1 p)t v logl 2 ((1
3nd Rd
pet
$ log (p) AA
5)
3i.
nm
Tum
(1 Cooo p)t V logl 6:
nm
where the last inequality follows from the fact that d (()). To see this, suppose there exists I < 2 lop 20o((4n/0 4n/88)
such that
3n1 dd y pt v
(1
log
(0)
Ue. S 2C,
then we have
4n log
log (d /2/4/2)
pt
2
log
Brjo pd mim
while t < 2 (4/8(4 raises contradiction by the choice of d. This proves for all & S 2log(4/8)
g²
have (1 3yo put V log( ( 2 and thus A! 25
Then we consider the case when 2 llo(4488) where the condition for Lemma B.4 holds. Now
suppose for all < L 1, we have D.,Tr C. which clearly holds for / 2 logi
In 4n /8)
For all
S 1- 1, we have A (x) Mirra 2 (1 300
A WEir, when e!")) = -1 This leads to the following lower
(s)
bound for (1) 2..r, as
2 (1 Goord (1- (1-11.0)0 3no 1.5pt A (0)
(0) Verr,
1/oo d 2nm
2 21
geiri 26
where the second last inequality follows from the choice of
2 log(1 + #Coold log(1 +
nCooad 2nm 3n 20372
5 3 log(1
nm
@Coo3d log(1 s0m
We can verify that Co satisfies the above inequality, This concludes the proof that, for all 6, we have (1)
y..r. 2 < and thus for all t. Finally, we conclude that
Be.r,i 2 (1 nooofd (11-1.5)t(1-
2110 3nm
(0)
1.5pt A (0)
nm
CooRd 2nm
+1+
(0)
28

---

With the above lemmas at hand, we are ready to prove Lemma
Proof of Lemma 4.4 By Lemma
at Ti, taking the maximum over yields
Coodd )00663
max yini
(1
2nm
(1 '/Cof ''011500p d
2nm nCoopd d 4mm
exp
t)0.15000,
where the first inequality is by max, j.r E.) 2 3 and 0.43d < 0.433 In the last inequality, we use (1+22 2 (xp(2/2) for < 2.
Then we see max, (1)
yerr 2 in at least 7i log(20/(on vd) and because maxj.r Pj.r, 2 (0)
AT "U.T j.r kw
C.) 0.4, 1.
Besides, by Lemma D.2
we directly obtain the result that
3n0RdT,
mm
Furthermore, Lemma D.I
yields
2nl p 12 4nm
(24) 2i
1( j.r p1) S exp
log (o(4//ooo,,V))))(kr 14) - (w p.
nozd
where have used the condition of low SNR, namely nSRR < 1 (1/log(0/((oog,Vd)) By Lemma
B.2 we conclude the proof for maxj,r T5 (001l1411))
(Ti)
Lastly, according to Lemma E. at the end of stagel, we have the lower bound signal learning coefficient
Co
Gir
(1)
((w (0)
w1) 2 exp
t) max rE(m)
j.r 14)
(0)
rE[m]
8m
Coalleu (20( (ovop v dd) 4nm
exp
max rE(m]
(0) (ww
jrr 11)
8m
nooddd
exp(nSNR² (o00//SNN)oo(22//0oo,,,>oo
2 on 1/|1
E.2
Proof of Lemma 4.5
The key idea to show P oscillates during the second stage, where the growth tends to offset the drop over given time frame. This would suggest the f(W(+)) x) is both upper and lower bounded by a constant, which is crucial to ensuring that (() increases exponentially during the second stage.
Without loss of generality, for each with (w(()
(.. Ed) and y/s 1, the evolution of p is
written as
1+1 (1)
am E j.r: 11 (9)
2n
(1) (1)
P.ra
P
(1 am +oxp( ( Pp.r.
2n1le,1 1|2
if c
2n1lE:11 1|
if ife (1) --1
am(1+exp( )1
where we denote f.0) ((W()) x1). Note that f!()
Σm (P().r)) when (0)
< 1.
29

---

To simplify the notation, we define that (0 approximated to
1. - - -1, )².
Then the dynamics can be
2n11e.
(1)
with prob
11+1)
nmm1+exp(( (( ()))
2//|x,
2ny
2/ with prob
Lemma E.4 (Restatement of Lemma 4.5 Under the same condition as Theorem 3.3 during
t E [Ti, To] with T2 = Ti + log(6/ (aa I 22) Am(1 + exp(c2))x- ||ull there exist sufficient large positive constant C, and a constant & depending on sample index such that the following
results hold with high probubility at least 1 1íd:
S for all E {-1111) and r E [m]]
2m Ex (P.i..))) ) S f(h) r= p2
(0) maxxe|m] (7 (W...: 1) exp
(t)
ا 16m
(T)) (1 Ti)) maxre[m] 1755 j.r 14)l.
(w/o)
(0)
Proof of Lemma E.4 The proof is based on the method of induction. Without loss of generality, we consider all with ys 1. We first check that at time step Ti, by Lemma 4.4 there exists constant C' such that
Σ
Besides, by Lemma 3.3 it is straightforward check that 7/5 S 1 for all j {-1, 1} and [m].
and maxy Uir 2 0. Next, can show the following result time Ti:
(71)
((Ti)) F+I ( (T))
x;) - (T) x;)
+1
m
(0)
11) + 741,)) + 1 m
(Ti)
(w() 00)
+l, Ex) +
(En Ev) (Ti) 1Exr113
P P+l.n())
m
m
1 m
(E Epl (Ti 1 P-1mm
(w (0)
1r (1) - --1))
(w (0)
-l.r Ei) + P--1.
+
(T))
m r=1
m
1
log (n2 /0)
2 -
(o v +
Ptl.a 3 -16
naa²
d
+1.r.
2m
where the first inequality is by Lemma 4.5 Proposition 4.1 and Lemma B.
The second inequality
follows from the condition on do and d in Assumption Similarly, have
1 (T))
F+1
(T)) +1 x.) F-1 (W(?) (T))
x:)
log(4n2 2/2/8) na)
0 + Ō(ooo, +
(pl
(3)) Fl + + +
d
1.
Next, we assume that all the results hold for Tj < < T. By the induction hypothesis, we can bound
C1 < (! < c2 for all i [n]. Then can show that 2
(T+1) continues to exhibit exponential
30

---

growth:
(T+1)
= =9i, nm
(T) 2m
Σ
2100
Σ
((00) (w (2)
jor x 11
iES Ss
2 7j.r + 2n (Ist
(T)
|5
1
(w (w/)rr (0) 1
+ exp(c2)
1 + +xeep( ((2)
nmm
2 15 + 2n 2 3p
(T)
1
3p
1
(w (7 1|
M
1 exp((2)
4 1 + expeeppp-00 (c22)
(T) + "
3p
[(W
(T)
(a) + jnnj (2)
= jir
m + exp(e2)
2
for
n11u113
(T) + 2m(1 + exp(c2))
((w
frr 12) + )ng.)) )
(2)
2 Ti
where the last inequality is by 3p S 1 we have:
2 1+exp(e2) Next, define B(t) max (7/, 1(w
(0) (0) (4)).
B(T+1) 2 (1+ 2m(( + exp(c2))
1/| 2
exp(
(1 - B
4m(11 + exp(c2))
n سلاااا
(t B()))
exp
16m
At the same time, there exists an upper bound on the signal learning:
2n 2 (T h (T) + (w j.r ا S 0.01,
Y5 f.r ا S exp (
(0)
m
where we used the condition that T < T2.
To show that 1 (T+1) remains within constant range, we define M, (8) A (1: (t) - 4))² where o
is a sufficiently large constant depending on i. Using the relation 1
Em (p (0 )2 S s S
2m
2 Em ( we have:
EL (T+) 12
21 17/1
2 (T)
(1+ 2 2exp((1p)) (2) nm
))mm
+p(1-
2n115,
(1 + 1/2epp( (1. mm
At the same time,
BIG (T+))
1/ (T)
5 (1 (1-27) 1p)
2n 2
(1 1/2 exp (T) (2))))mm
2n 2n|15,11
+ +
(1 + 2 2exp(=xpppp (-(1 ((())))))mm
Then we show that
E E|M,
(T +1)
16 ( = E[(4 (1 (T) - 2: El, (T+1) (T)
+ (1*)²
< (1 p) 1
2n 1
TTy
(1 + 1/2 exp((1) Jrm
+p(1
2.
())
(1+ 2 cepppp(( (T) 22 mm
2n|
-20
(1--)(1+
(
(T)
(1 + exp( ))))))mm
2n115.113
+p(1
(T)
+ (1t)2
(1+ + exppexp(10001
(T) (12)))))))m
4
31

---

Subtracting M yields
E (1+1) (T) M,
+0 yp)
(?
(187))2
(1 - p)
(1 + 1 exp((1, (T) )²) )m
nm
nem
8n115:112
+0
n| (
+p
(1 + 2 2exp(=((e ( ) )am
nm
8nlls.11
(2
+0 + 2 2exp((1 (T))2) p) (T) -0+00+0
nm
nm
111 (T)
1 p(1 + 1/2 1/2xp((()
(1, (T) (T)
1- p(1 + 2 (exp((4))) (T))))))))))))))))
(mllsallay) nm
y))
6²
+ +0
nm
+ expp((1)) (2)
1 2exp((11 ))2)
s 0,
(T) S 4u and p < 1/(1+ 2 (exp((1) (T)))) and condition the learning where the final inequality is by 4
(1) hem, [1] is super martingale. By one-sided Azuma inequality, with probability at least 1 6, for any O, it holds that
rate from Assumption 3.1. which confirms that (M,
72
P(M -
-M, M.TD) 27) S exp
)
T Tu
where,
C = |M M(k-1) = 1(1 - 12)² - (1/
(R-1) )²
=(11 bú
(k- 1))) (1; + 4i
(k)
(k-1) 21, S n/C..
Taking the upper bound of c C2 yields
72
P( - -1,
C/ r)
exp
(T T.
where we define CB A (1 (T) - =2 0. Therefore, we conclude with probability at least 1 6,
(T+1) 41 S v CB /n s C.. 14
where the last inequality is by 0 and T < T2.
Finally, we check that
I (T+I) = F+1 (W (T+1) Xx:) F_ ( (T1) xi)
m
(E))EN) (T+1)
σ (w +1,r (1) + -1+++))) + Σ
σ (w (l E,) + P41,..
1|
P+i,r.3)
m
r=1
8'
(w 1,m5 11) - ---17
(T+1)
(w 1, Ex) + P-1.
(E Ev) (T-1)
| 1
p P-1,r.
1 m
log (o(4An2/)) na))
2
-000 0.01 +
p
Pl.
(1+1)
3 161
m
d
(++1)
P+1.r
2m
32

---

where the first inequality is by Lemma 4.4 and the induction claim, and the second inequality is by condition on from Assumption 3.1 Similarly. by the same argument, we conclude that:
((T+1)
F+1 x.) - F-1 - (I,1,,)
m
log( (nn na)
2 Ō 1 (3 + 0.011 Ö(ooap d) +
PPi.. + B 16V E m
d
2
+
Let T2 = Ti + log( (00 (2)) (1 exp(c2))) then by lemma 4.4 we can show that
1 11
(36) Yir
2 exp(
4m + exp( 1)
(T1)
exp(
log(6/ log(6/(coll</))))mm)) + exp(c2))n ( 2
4m + exp(e2))
= -o/(coll4412)))) (T))
2 0.01.
E.3 Proof of Theorem 3.3
Proof of Theorem 3.3
For the population loss, expand the expression follows:
D
0-
(W())
((x,))DD F f(W( x))] =
x) 0)
m
(ww") 2.r {))
a ((w!l)
(1) M.r
5) N
m m
m
gorr mp1))
o a
(w
(t)
v.r 812))
m
Recall the weight decomposing
(0) wir j.r
100000111111
j.ral | - S + Σ 1l.
1 +
1=1
From this, we obtain:
(w 8.1.
(w
(0) y.r 8/1) (t)
7 p.r
p.r 9.r. U12)
(w(0)
y.rr 8/44) + 7/.-
(0)
(1)
By Lemma 4.5 we conclude that
(w) N.r
(1) = 0(1), "o 9/4) (() 0.
Therefore, it holds that
a ((w
Mon 914)) (w(()
m Σ
1
a ((w y.r y11)))
m
((w gart y/1))
m
a((w (0) m/4) + (()
= O(1),
33

---

where the last inequity is by Lemma 4.5
Next, we provide the bound for the noise memorization part. Define that g(E) = -,m o(w (0)
-y.ro E)
By Theorem 5.2.2 in [52], for any т > O, it holds
P(g(E) - Elg(E) 2 2) S exp(
Lip
where e is a constant and Liip is the Lipschitz norm of function g(E), which can be calculated as follows:
19(E,) 9(5') = Σ o (
Yort E)) - Σ a(ww V.rt E'))
rm
1a (t)
V.rt {)) o (( (1)
y.rt E1))
S 2
Kw (t)
E)1 1(w (t)
y..r E 5n>l
v.r
< 2
[ 12
||51|2 1|E - -
y=
3
w 2. 12
Vdll E'112,
where the first inequality is by the triangle inequality, the second inequality follows from the the convexity of the activation function, the third inequality is by the Cauchy-Sehie Schwwaz incquality, and the last inequality follows from B.I Therefore we conclude that
m
1,я| 3
ll (
Il Vd.
Furthermore, given that (w - E) NO0 oz]l (9 (2) have:
Eig(E)] = > Blo yort En)) = Σ 0 / ///2l( 1
To obtain the the upper bound of g(E), we show that:
n
v.r 2 =
Para P
1 26:
2
Σ (2) 3 2c, + Σ Σ
10
P
1l 2
< 33nC(ozdd)
+ 2n (0 207
Vd 1og(2222/))
< 4nC(o
34

---

where the first inequality is by Lemma B.1, and the second inequality is by the condition on d in Assumption 3.1
With the results above, we conclude that
C (W
B(xx))-ly * f(w()) ,x)] Plyf(W((). < <0
- PPC
0 ((ww)) y.rs 6 2
a (6) 8irt m14))
m
m
P(g(E) Elg(E)) 2
Σ
a(w
Mirt m/1)))
Σ op/ / (1)
-yrr I13)
==1
1=1
a((w yoro Upu)
(1)
Σ 0 0
w (1)
113)
< exp
0/ >
|| -.r
12
2)
02 AnC((2dd)-
< exp
303 (o)d)
Cfd exp(
< exp(
36d
c2
Ofd 12
2exp
which corresponds to the second bullet point of Theorem 3.3 establishes the first bullet point, this completes the proof of Theorem 3.3
Combined with Lemma 4.5 which
F
Experimental Details for Figure 1
In this section, provide a detailed description of the experimental setup used generate the results shown in Figure I CIFAR-10 dataset under varying SNR conditions.
which compares the performance of Label Noise GD and Standard GD on the
F1 Dataset and Noise Injection
We used the CIFAR-10 dataset, selecting 1,000 images in total, with 100 images per class, perform both Standard GD and Label Noise GD training. The random seed used for selecting training samples was fixed ensure fair comparison across different hyperparameters.
To simulate varying SNR conditions, inspired by [9], we introduced noise to the high-frequency Fourier components of the images using the following procedure:
Each image was transformed into the frequency domain using a 2D Fourier transform.
Gaussian noise was added to the high-frequency components, excluding the low-frequency region near the center of the Fourier spectrum. The intensity of the noise was controlled by a noise level parameter, where higher values correspond to noisier data and lower SNR.
Finally, the image was transformed back into the spatial domain using an inverse Fourier transform.
The noise level was adjusted control the SNR factor, which is represented on the x-axis Figure
F.2 Model and Training Setup
The experiments were conducted using a VGG- model trained from scratch on the CIFAR-10 10 dataset. The final fully connected layer of the model was modified to output predictions for the 10 classes CIFAR-10. 10. Both Standard GD and Label Noise GD were trained using cross-entropy loss and gradient descent (GD) with learning rate of 0.05. Training was performed with a full-batch setup over 5,000 epochs. For Label Noise GD, labels were flipped randomly with a probability of 20% each iteration to simulate label noise
35

---

F.3 Results Analysis
The results shown in Figure demonstrate that Label Noise GD consistently achieves higher test accuracy than Standard GD across all SNR levels. The performance gap is most evident under low SNR conditions, where Standard GD suffers significant accuracy degradation due to noise memorization, while Label Noise GD effectively suppresses noise and promotes robust feature learning.
F,4 Reproducibility
To ensure reproducibility, all experiments were implemented in PyTorch. The codebase, including dataset preprocessing, model training, and evaluation, provided in the supplementary material.
G Additional Experiments
In this section, we provide additional experiments to further support our theoretical findings.
G.1 Deeper Neural Network
Feature
Feature Learning (ely)
Train
Accuracy
Label GD
Label Notse
25
0.6
mane (GD)
0.4
ma hotse
10
0.2
0.7
Lane Nobe
0
2000
4000
0
2000
4000
2000
4000
2000
4000
Figure 4: Performance of 3-layer ReLU neural network: The ratio of noise memorization to signal learning, along with training loss and accuracy, for standard GD and label noise GD.
We have conducted additional experiments using 3-layer neural network with ReLU activation. The network is defined f(W, x) F+1 (W+1, +1, W, x) F-1 (-W(W-1, W, x), where
m
F, W.
a (.W..: 2(p) = (W xx(P))))
in which (-) is the ReLU activation, W E Rdxm denotes the weight in the first layer, and W+I E Rmxm weights in the second layer. The last layer is fixed.
Specifically, we train the first two layers. The number of training samples n 200, and the number of test samples is Reest 2000. The input dimension was set d = 2000. We set the width to m = 20, the learning rate to r = 0.5, and the noise flip rate to p = 0.1. The data model follows theoretical setting, where μ [1, 0, .] and the noise strength is о, = 1. The experimental results, shown in Figure 4 are consistent with our original findings: compared to standard gradient descent, label noise GD boosts signal learning (as shown in the first plot) and achieves better generalization (as shown in the last plot).
G.2 Real World Dataset
We conducted an experiment using the MNIST dataset, in which Gaussian noise was added the borders of the images while retaining the digits in the middle. The noise level was set to σ, = 5. Moreover, the original pixel values of the digits ranged from 0 to 255, and we chose a normalization factor of 80. In this setup, the added noise formed a "noise patch" and the digits formed "signal patch". focused on the digits '0' and '1', using n = 100 samples for training and 200 samples for testing. The learning rate was set to 1 0.001, and the width was set to m = 20, with a label noise level of p = 0.15. The results, shown in Figure 5 were consistent with our theoretical conclusions. reinforcing the insights derived from our analysis.
36

---

Feature Learning
Feature Leamiing Ratio (el)
Train Loss
Test Accuracy
12.5
4 (6D)
8
Lebel hotee 6D
0.8
Lebel Novee GD GB
10.0
6 (6D)
GD
7.5
A
0.6
0 Iaaeel hotee
5.0
4
2
0.2
Noise
0.0
25000 50000 75000100000
25000 50000 75000100030
75000100000
50000 75000100000
Figure 5: Performance on the modified MNIST dataset: The ratio of noise memorization to signal learning. along with training loss and test accuracy, for standard GD and label noise GD.
Heatmap of Test Accuracy
Heatmap of Test Accuracy
0.0
8.0
08
Level
0.8
Nobe
6.0
6.0
5.0
5.0
0.8
0.6
4.0
60.0
86.0
100.0
120.0
140.0
60.0
80.0
100.0
120.0
140.0
Signal Nommaization
Normalization
(a) Performance of standard
(b) Performance Label Noise GD
Figure 6: Test accuracy heatmap standard GD (left) and Label Noise (right) after training on modified
MNIST dataset.
To assess the sensitivity of the methods to the choice of noise parameters and signal normalization, we conducted additional experiments on a modified MNIST dataset. The signal normalization values were varied from 60 to 140, while the noise levels ranged from 4 to 8. For each combination of noise level and signal normalization, we trained the neural network for 200,000 steps with a learning rate 77 0.001, using either standard gradient descent (GD) or label noise GD.
The resulting test errors are visualized in Figure Notably, label noise GD (right) consistently achieves higher test accuracy than standard GD (left) across all configurations. This demonstrates the robustness of label noise GD variations in noise and signal normalization parameters.
The motivation behind using MNIST was its clearer signal, which allows us to more directly observe the effects of label noise without other confounding factors. However, we also conducted experiments on a subset of CIFAR-10, using two classes: airplane and automobile. Gaussian noise was added to a portion the images, following similar setup to MNIST. For these experiments, we set q = the number of neurons m = 20, the learning rate 0.001, the signal norm signal norm 64, the noise level noise level the number of samples n 100, the label noise probability p 0.15. and the input dimension d = 6144.
Feature Leaming
Learning (oly)
Accuracy
maneju (GD)
Label
Label
many, (G0)
0.70
0.65
many,
1.5
1.0
0.2
0.55
0.50
0
8000
16000
9000
16000
8000
16000
0
8000
16000
Figure 7: Performance the modified CIFAR-10 dataset: The ratio of noise memorization to signal learning. along with training loss test accuracy, standard GD and label noise GD.
37

---

The results shown in Figure 7 indicate that label noise GD continues to provide benefits in terms of generalization compared to standard GD. We believe these extended experiments help establish broader applicability of our findings to more complex benchmarks.
G.3 Different Type of Label Noise
To validate the robustness of label noise GD under different noise forms, we varied p across different values. For example, show the results for p 0.3 in Figure and p 0.4 in Figure The results consistently indicate that label noise helps reduce overfitting and boost generalization, especially in low SNR settings.
In addition, we extended our empirical analysis to include Gaussian noise and uniform distribution noise added to the labels. For Gaussian noise, we used two examples, namely 4 (11, 1) and
(0 ~ (1, 1), with the results shown in Figures 10 and 11 respectively. Furthermore, for the uniform distribution, simulated the noise with C unifl 1, results are shown in Figures 12 and 13 respectively.
2] and c unif 3]. The
Our results indicate that label noise GD still performs effectively, achieving better generalization compared to standard GD, providing further evidence of the robustness of label noise GD under different noise forms.
Feature Loaming
Feature Learning Ratio (aly)
Train Lass
Test Accuracy
Label Notse GD
1.0
CD
0.6
0.9
1G0) (GD)
meryy (GD)
20
0.4
Label
0.8
Label
mosa, |Lace Koise GO)
GD
0.7
G0
Molee CD)
0.0
0
250
500
750
10000
250
500
7.0
1000
250
500
750
1000
0
750
500
750
1000
Figure 8: Performance with flip noise p 0.3: The ratio of noise memorization signal learning, training loss, and test accuracy of standard GD and label noise GD.
Leaming
Feature Learning (oly)
Test Accuracy
1.0
40
0.6
(GD)
30
0.4-
GD
Label
20
mony. (Label
0.2
0.6
M
0.5
0
250
500
750
1000
250
500
750
1000
250
500
750
1000
250
500
750
1000
Figure 9: Performance with flip noise p 0.4: The ratio of noise memorization to signal learning, training loss, and test accuracy of standard GD and label noise GD.
Feature Leaminn
Feature Leaming Ratio (oly)
Train Lass
Testt Accuracy
Label Noise GD Gb
1.0
0.6
15
Label Notoe GD
0.4
Label No GD
Moddy (Lace Noise GD1
CD
G0
Many. (Label Soice CDi
0.2
5
0.0
250
500
750
1000
1000
250
500
1000
250
500
750
1000
Figure 10: Porformance with Gaussian noise (11, 1): The ratio of noise memorization to signal learning, training loss, and test accuracy of standard GD and label noise GD.
38

---

Feature Leaming
Feature Leerning Radio (oly)
Train Loss
Test Accuracy
20
Label Notse GD
1.0
LF
15
CD
0.6
0.9
matgg (CD)
MaSA iLace Notse GD)
10
0.4
Lebel Nciiee GD
GD
0.8
0.7
Mody: [Labtll Viive (D)
0.6
Label No GD
0.0
0.5
250
500
750
1000
1000
250
500
1000
0
250
500
750
1000
Figure 11: Performance with Gaussian noise. (0.6, 1): The ratio noise memorization to signal learning. training loss, and test accuracy of standard GD and label noise GD.
Feature Leaminn
Featurre Leaminng Ratio (oly)
Train
Test Acturacy
1.0
0.6
m (GD)
0.9
ma (CD)
0.4
m (Lace
10
0.2
Label
0.5
0
250
500
750
1000
250
500
750
1000
250
500
750
1000
0
250
500
750
1000
1, 2]: The ratio of noise memorization to signal learning, training loss, and test accuracy of standard GD and label noise GD.
Figure 12: Performance with uniform distribution noise unif[-
Feature Leariing
Feature Leamiing Ratio (oly)
Train Loss
Test Accuracy
1.0
0.6
0.9
Label Notse GD
0.4-
Label Nobse GD
0.8
mosou (Label haise GD)
CD
GD
0.7
mary. (1 Nolse CD)
0.2
0.6
Label No GD
W
0.0
0.5
63
250
500
750
10000
250
1000
0
250
500
750
1000
Figure 13: Performance with uniform distribution noise unif[-2,
2, 3): The ratio noise memorization to signal learning, training loss, and test accuracy of standard GD and label noise GD.
G.4 Higher Order Polynomial ReLU
In this work, we set the activation function as squared ReI.U. This choice makes g = 2 a particularly interesting and challenging case to analyze, as allows us to study the interaction between signal and noise in a setting that closely resembles practical two-layer ReLU networks.
For higher values of q, we also conducted experiments with q = 3 and q 4. For q 33, set the learning rate = 0.5, the number of neurons m 20, the number of samples n = 200, the signal mean μ [2, 0, 0, -.. 0), and the noise strength Op 0.5. The results are shown in Figure 14 For = 4, the parameters were set as 17 = 0.1, m = 20, n = 50, f 0, Oj. and op 0.5. The results are shown in Figure 15
Festure Leeriing
Festure Learning (oly)
Accurecy
ma (GD)
mang, (GB)
100
0.4
make Hotse
0.7
matoy
50-
0.2
0.6
0.0
0
2000
4000
0
2000
4000
0
2000
4000
0
2000
4000
Figure 14: Performance with q 3 for polynomial ReLU: The ratio of noise memorization to signal learning, training loss, and test accuracy of standard GD and label noise GD.
39

---

Feature Leamiin
Feature Learning Ratie (oly)
Train Loss
Test Accuracy
1.0
Label Nose GD
GO
0.9
many (rGn)
Label Notse GD
0.8
Laze Kose 6D
Barg.u (Label Moise (D)
GD
0.7
60
mar, (Label Notse GD)
10
0.6
0.5
Figure 13:
Performance with 4 for polynomial ReLU: The ratio of noise memorization to signal learning, training loss, and test accuracy of standard GD and label noise GD.
In all these cases, the experimental results consistently show that using higher polynomial ReLU activation helps label noise GD suppress noise memorization while enhancing signal learning. This ultimately leads to improved test accuracy compared standard GD,
40

---

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

---

Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification: All assumptions for the theoretical results are clearly stated (e.g., Assumption 3.1), and complete proofs are provided the appendix, with proof sketches included in the main text (Sections and 4, Appendix B B-E)..
Guidelines:
The answer NA means that the paper does not include theoretical results. All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proof' can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
Justification: All necessary experimental details, including dataset construction, noise injection, model architecture, training protocol, and evaluation metrics, are provided in Section and Appendix F and G.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, No answer this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often good way to accomplish this, but reproducibility instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of model checkpoint, other means that appropriate to the research performed.
also be provided via detailed
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how to reproduce that algorithm.
(b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
42

---

(d)
We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification:
The code necessary reproduce the main experimental results is included in the supplementary material.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.. cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https
/ mnips.cc/public//
for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: Section and Appendix F and G provide all relevant training and test details, including data splits, hyperparameters, optimizer choices, and noise settings.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [No]
Justification: The primary findings were robust and stable across all tested settings, so statistical significance analysis was not included. requested, we can provide additional runs and error bar analysis during the rebuttal period.
43

---

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

---

Answer: [Yes]
Justification: The broader impact discussed in the "Conclusion and limitation" section, where we state there immediate negative societal impacts, and the work aims to advance theoretical understanding.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (e.g.. disinformation, generating fake profiles, surveillance), fairness considerations (e.g.. deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out, For example, it is legitimate to point out that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
The paper does not release any high-risk data or models.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification: All datasets and code used (e.g., CIFAR-10, VGG-16) are cited in the refer- ences and used in accordance with their licenses.
Guidelines:
The answer NA means that the paper does not existing assets.
45

---

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

---

Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with
human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent)
may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods this research? Note that the LLM used only for writing, editing, formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Answer: [NA]
Justification: LLMs not used important, original, non-standard component of the core methods in this research.
Guidelines:
The answer NA means that the core method development in this research does involve LLMs as any important, original, or non standaadd components.
Please refer to our LLM policy for what should or should not be described.
47


Reviews:
[{"review_id": "5p5ARmHjY4", "reviewer": "Reviewer_vT6L", "summary": "This paper investigates the generalization benefits of label noise Gradient Descent in the context of binary classification with neural networks (NNs). The paper considers training a two-layer neural network with squared ReLU activation and a fixed output layer over synthetic data sampled from noise-signal data model with a low signal-to-noise ratio (SNR).\n\nWhen training with standard GD, both the signal and noise components of the model grow exponentially. However, in low SNR regimes, the noise component grows faster, leading the model to minimize the training loss by primarily fitting the noise. This results in a non-negligible test error. In contrast, with label noise GD, the noise component initially grows exponentially but then oscillates and remains bounded. Meanwhile, the signal component continues to grow, allowing the model to learn a solution with a small test error.", "questions": "1) What happens when the output linear layer is not fixed but trained? More explicitly $a . \\text{ReLU}(x,w)$ is also 2-homogenous does the dynamical properties described in Proof-Sketch. Can the authors provide a empirical evidence for this or show how the analysis extends ? \n\n2) A more empirical investigation on how Label noise GD prevents from fitting the noise component across different architecture and data models would be a valuable addition. \n\n\nMinor: \nIn equation 3 after line 221, $\\xi_i$ is not defined earlier, should it be  $x_i$ ?", "limitations": "yes", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "Strengths:\n\nLabel noise GD is well studied theoretically to understand how stochastic algorithms generalize better.  The paper presents a simple setting  where the advantage of label noise GD can be theoritically established. The data model considered is also well studied to understand feature learning with NNs and establishing label noise GD learns features even in low SNR regime is a interesting addition to the existing literature. \n\nWeakness: \n\nIn my opinion, a weakness of the paper is its reliance on a specific architecture. The phenomena described, such as the exponential growth of signal and noise, and the oscillation of noise, appear to be contingent on the 2-homogeneous property of the activation function. This architectural choice therefore restricts the generalizability of the observed phenomena.", "was_revised": true, "final_justification": "My initial evaluation of the paper is positive with some slight concerns regarding experimentations. The authors addressed some limitations regarding experimentation with deeper architectures, different activations and other datasets. However, given there are some limitations (which the authors empirically addressed) with the choice of activations ($q$-homogeneous for $q>2$) prevents me to increase the score further.", "rebuttal": "We thank the reviewer for the thoughtful comment and constructive feedback. Below, we address the main concerns and questions raised.\n\n---\n\n> **W1**: The phenomena described, such as the exponential growth of signal and noise, and the oscillation of noise, appear to be contingent on the 2-homogeneous property of the activation function. This architectural choice therefore restricts the generalizability of the observed phenomena.\n\n**R1**: We would like to clarify that the 2-homogeneous (squared ReLU) activation function serves as the minimal setting where the benefits of label noise gradient descent can be most clearly established in our analysis. The choice allows us to better characterize the separation between signal and noise learning dynamics. \n\nImportantly, our results are not limited to this particular activation. As presented in **Appendix G.4**, we have included experimental evidence showing that similar effects occur with **higher-order polynomial activations**. Specifically, both ReLU³ (Figure 14) and ReLU⁴ (Figure 15) demonstrate the same suppression of noise memorization and improvements in generalization. These observations suggest that the phenomena we describe are not restricted to the 2-homogeneous property, but are present in a broader class of activation functions.\n\n---\n\n> **Q1**: What happens when the output linear layer is not fixed but trained? More explicitly aReLU(w,x) is also 2-homogenous does the dynamical properties described in Proof-Sketch. Can the authors provide empirical evidence for this or show how the analysis extends?\n\n**A1**: In our current analysis, we fix the output layer in order to keep the theoretical treatment analytically tractable. This modeling choice is consistent with previous works in the literature [1,2,3]. Nevertheless, we have conducted preliminary experiments, as reported in **Appendix G.1**, in which two layers are trained. Although the quantitative details, such as the convergence rate, may change, the key qualitative behaviors remain unchanged. \n\nSpecifically, we observe that noise memorization remains bounded and the signal component continues to grow under label noise GD even with deeper neural network. These results suggest that the regularization effect of label noise GD is not simply a consequence of fixing the output layer. Extending our theoretical framework to fully trainable networks is a promising direction for future research, and we plan to investigate this further.\n\n---\n\n> **Q2**: A more empirical investigation on how Label noise GD prevents from fitting the noise component across different architecture and data models would be a valuable addition.\n\n**A2**: We would like to note that **Appendix G** of our submission already includes additional experiments on deeper architectures and on datasets with alternative noise structures (such as Gaussian label noise and modified MNIST/CIFAR). Across these settings, we consistently observe that label noise GD prevents harmful overfitting and improves generalization. These empirical results support the generality of our findings, and we will further highlight them in the main paper to increase their visibility.\n\n---\n\n> **Minor**: In equation 3 after line 221, $\\xi_i$ is not defined earlier, should it be  $x_i$?\n\nThanks for pointing it out, the noise component in Definition 2.1 should be denoted as $\\xi_i​$. We will clarify this notation and make the correction in the revised version.\n\n\n---\n\n**Summary**: We thank the reviewer again for the thoughtful feedback. We hope that our responses and the additional results provided have fully addressed your concerns. If there are any further questions, we would be happy to clarify.\n\n---\n\n**References**\n\n[1] Cao et al. Benign overfitting in two-layer convolutional neural networks. NeurIPS 2022.\n\n[2] Kou et al. Benign overfitting in two-layer ReLU convolutional neural networks. ICML 2023.\n\n[3]  Chen et al. Why does sharpness-aware minimization generalize better than sgd? NeurIPS 2023."}, {"review_id": "IPVkxbShnK", "reviewer": "Reviewer_ajKN", "summary": "In this paper, the authors study label noise gradient descent and its effect on generalization. They show that under certain data models, this approach can outperform standard gradient descent in low signal-to-noise ratio (SNR) settings. Specifically, standard gradient descent tends to memorize the noise in data, which prevents it from learning the underlying features. In contrast, label noise gradient descent avoids overfitting to noise and is able to eventually learn meaningful features. Experimental results are provided to support the theoretical findings.", "questions": "1.\tIn Theorems 3.2 and 3.3, the results state that there exists a time $t$ at which the conclusion holds. Does this guarantee persist for all $t$ larger than that value, or is it specific to some finite time window?\n2.\tRelated to the above, I wonder whether gradient descent achieves good generalization performance in the long run (as $t \\to \\infty$). Given that GD is known to converge to a max-margin solution in certain settings (according to the implicit bias literature), shouldn't this lead to good test performance eventually as well?\n3.\tIt would be helpful to elaborate more on the connection with prior works that study label noise in local dynamics, especially those suggesting that label noise biases training toward flatter minima. Does the current paper suggest any similar behavior, implicitly or explicitly?\n4.\tGiven the mentioned similarities to previous works (e.g., [8,29]), it would be valuable to clarify the key differences in the analysis that allow this paper to address challenges those works could not. For example, how does this analysis overcome issues like handling $\\text{ReLU}^q$ for $q > 2$, or the stronger SNR assumptions required in prior results?\n\nMinor:\n\n1.\tLine 306-307: $\\iota_i$ should be $\\iota_i^{(t)}$?", "limitations": "Yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "Strengths:\n\n1.\tStudying the training dynamics of gradient descent in the presence of label noise is an interesting research question.\n2.\tThe use of a supermartingale-based argument to analyze noise memorization is technically interesting and may prove useful for analyzing related problems.\n3.\tThe paper is clearly written and generally easy to follow.\n\nWeaknesses:\n\n1.\tThe data model considered in the analysis is quite limited. For example, even a linear model can perfectly learn the target function in this setup. It would be more impactful to extend the results to more realistic or challenging models.\n2.\tSee question section below", "was_revised": true, "final_justification": "The authors' response has addressed my concerns. I encourage them to add more discussion on related works. I have increased my score to 4.", "rebuttal": "We thank the reviewer for the detailed and thoughtful feedback, as well as for highlighting the strengths of our work. We address the main questions and concerns below.\n\n---\n\n> **W1**: The data model considered in the analysis is quite limited. For example, even a linear model can perfectly learn the target function in this setup. It would be more impactful to extend the results to more realistic or challenging models.\n\n**R1**: The signal-noise data model we consider has been extensively studied in the neural network theory literature as a sandbox to understand how gradient-based training prioritizes the learning of the underlying signal over overfitting to noise [8,10,29]. While this model is indeed stylized, it allows for rigorous analysis of **non-convex training dynamics** that would be intractable in more realistic settings.\n\nTo the best of our knowledge, our work is the first to investigate label noise GD in this setting and to demonstrate efficient learning and benign overfitting in the challenging low SNR regime. Moreover, as discussed in Section 4.3, the analysis of label noise GD is already technically nontrivial even in this simplified setup. \n\nWe agree that extending these results to more complex data models and architectures would be valuable, and we consider this an interesting direction for future work. In addition, our empirical studies in **Appendix G** provide supporting evidence that the regularization effects of label noise GD persist in deeper architectures and on more realistic datasets.\n\n---\n\n> **Q1**: In Theorems 3.2 and 3.3, the results state that there exists a time t at which the conclusion holds. Does this guarantee persist for all t larger than that value, or is it specific to some finite time window?\n\n**A1**: Regarding Theorem 3.2, the convergence rate is of order $1/\\epsilon$, where $\\epsilon$ is the upper bound on the training loss. As $\\epsilon$ is made arbitrarily small, the required running time increases without bound. As a result, the conclusions regarding the behavior of training and test errors hold with high probability and persist for **sufficiently large time steps**.\n\nFor Theorem 3.3, the theorem describes the transition from a regime where noise memorization dominates to one where signal learning becomes dominant. After this transition, our experiments show that the training loss continues to oscillate and the test error remains consistently small. While these empirical observations suggest that the generalization guarantee persists in the long run, providing a complete theoretical analysis of the training dynamics for all time remains an interesting problem for future research.\n\n---\n\n> **Q2**: Related to the above, I wonder whether gradient descent achieves good generalization performance in the long run (as ). Given that GD is known to converge to a max-margin solution in certain settings (according to the implicit bias literature), shouldn't this lead to good test performance eventually as well?\n\n**A2**: In our low SNR regime and under our signal-noise model, the “max-margin” or implicit bias effect does not ensure good generalization for standard GD, because the signal is too weak relative to the noise. As a result, the solution that minimizes the training loss primarily fits the noise, rather than recovering the true underlying features. This aligns with recent works on harmful overfitting (e.g., [8,29]), which show that, without sufficient SNR or proper regularization, GD may converge to solutions with poor test performance. In contrast, our analysis and experiments show that label noise GD introduces a regularization effect that actively prevents memorization of the noise, enabling the network to focus on the informative signal even in the long run.\n\nIn addition, we would like to emphasize that our data setting differs from the classical cases considered in much of the implicit bias literature [S1,S2]. Specifically, our model adopts a **multi-patch structure** as described in Definition 2.1. As a result, the gradient descent updates in our setting are fundamentally different from those in standard linear or single-patch models. This structural difference plays a key role in our analysis and leads to distinct training dynamics, especially in the low SNR regime. Therefore, the conclusions regarding implicit bias and max-margin behavior do not directly carry over to our setup.\n\n---\n\n> **Q3**: It would be helpful to elaborate more on the connection with prior works that study label noise in local dynamics, especially those suggesting that label noise biases training toward flatter minima. Does the current paper suggest any similar behavior, implicitly or explicitly?\n\n**A3**: Thank you for this suggestion. There is indeed a connection between our findings and prior works that relate label noise (or stochasticity) to a bias toward flatter minima (e.g., [14, 34]). While our primary focus is on the training dynamics and generalization gap in the low SNR regime, our theoretical results are consistent with the idea that **label noise GD promotes “flatter” solutions by discouraging overfitting to noise**. Although we do not explicitly quantify flatness in our analysis, the boundedness of noise memorization coefficients and the improved generalization performance both suggest an implicit bias toward flatter minima. We will further discuss this connection in the revision.\n\n---\n\n> **Q4**: Given the mentioned similarities to previous works (e.g., [8,29]), it would be valuable to clarify the key differences in the analysis that allow this paper to address challenges those works could not. For example, how does this analysis overcome issues like handling $ReLU^q$ for $q>2$, or the stronger SNR assumptions required in prior results?\n\n**A4**: Thank you for this important question regarding the differences between our work and prior studies such as [8,29]. Our analysis departs from previous approaches in several key aspects:\n\nFirst, our choice of squared ReLU (2-homogeneous) activation is deliberate. Since our setup does not optimize the second-layer parameters, using squared ReLU allows us to closely mimic the feature learning behavior of training both layers in a standard ReLU network. Squared ReLU is also the minimal integer activation where both the signal and noise components grow exponentially during training. This property leads to more intricate dynamics, making the analysis notably more challenging than the case of $ReLU^q$ with $q>2$, where the separation between signal and noise can be established more directly.\n\nSecond, we introduce a martingale-based argument to precisely control the evolution of noise memorization under label noise GD. This technical tool enables us to rigorously establish the persistence of the generalization benefit of label noise GD, even as training proceeds. Such a persistent control of noise memorization has not been achieved in previous analyses.\n\nFinally, our approach also relaxes some of the stronger SNR assumptions required by earlier results like SAM [10]. By analyzing the low SNR regime with this refined technique, we are able to address cases.\n\n---\n\n> **Minor**: Line 306-307:  should be $\\iota^{(t)}_i$\n\n**R**: Thanks for pointing it out. We will correct the notation for the superscript $(t)$ in the final version.\n\n---\n\n**Summary**: We hope these clarifications address your concerns. We appreciate your careful reading and helpful suggestions.\n\n---\n\n**References**\n\n\n[S1] Soudry, D., Hoffer, E., Nacson, M.S., Gunasekar, S. and Srebro, N., 2018. The implicit bias of gradient descent on separable data. Journal of Machine Learning Research, 19(70), pp.1-57.\n\n[S2] Lyu, Kaifeng, and Jian Li. \"Gradient descent maximizes the margin of homogeneous neural networks.\" arXiv preprint arXiv:1906.05890 (2019).\n\n[8] Yuan Cao, Zixiang Chen, Misha Belkin, and Quanquan Gu. Benign overfitting in two-layer convolutional neural networks. Advances in Neural Information Processing Systems, 35:25237– 383 25250, 2022\n\n[10] Chen et al. Why does sharpness-aware minimization generalize better than sgd? NeurIPS 2023.\n\n[14] Alex Damian, Tengyu Ma, and Jason D Lee. Label noise SGD provably prefers flat global minimizers. Advances in Neural Information Processing Systems, 34:27449–27461, 2021.\n\n[29] Yiwen Kou, Zixiang Chen, Yuanzhou Chen, and Quanquan Gu. Benign overfitting in two-layer relu convolutional neural networks.\n\n[34] Zhiyuan Li, Tianhao Wang, and Sanjeev Arora. What happens after sgd reaches zero loss?–a mathematical framework. arXiv preprint arXiv:2110.06914, 2021."}, {"review_id": "J6dk8wmAdH", "reviewer": "Reviewer_9MYT", "summary": "This paper investigates whether introducing label noise in gradient updates can enhance the testing performance of neural networks in low signal-to-noise ratio environments. By comparing standard GD with label noise GD, it is demonstrated that adding label noise during the training process can suppress noise memory. In addition, under low signal-to-noise ratio conditions, standard GD establishes a non vanishing lower bound on test error, thereby demonstrating the benefits of introducing label noise in gradient based training.", "questions": "1. the neural network is relatively simple. Can it generalize to more complex neural networks?\n2、Can other datasets be added for comparison, such as Clothing1M and noisy CIFAR-10N?", "limitations": "yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strength：1、The theoretical support in the paper is sufficient and the proof is rigorous.\n2、Simple and efficient, Label Noise GD is a lightweight extension of standard gradient descent that does not introduce additional model complexity or training costs.\nWeakness：1. the neural network is relatively simple. Can it generalize to more complex neural networks?\n2、Can other datasets be added for comparison, such as Clothing1M and noisy CIFAR-10N?", "was_revised": true, "final_justification": "I have reviewed other experiments in Appendix, which provide detailed information on the training of shallow and deep networks.\nI appreciate the author's clarification and will maintain my score.", "rebuttal": "We thank the reviewer for the very positive assessment and for highlighting the strengths of our work. We address the main questions below.\n\n---\n\n> **W1 & Q1**. The neural network is relatively simple. Can it generalize to more complex neural networks? \n\n**R1**: While our main theoretical analysis focuses on a two-layer convolutional neural network for tractability, we have performed extensive additional experiments to evaluate the generality of label noise GD in more complex and realistic settings. Specifically:\n\n**In the main text**, we report experiments using a **VGG architecture** on CIFAR-10, demonstrating that label noise GD is effective at suppressing noise memorization and improving generalization even in large-scale, practical deep networks under low SNR regime.\n\n**Appendix G.1** (Deeper Neural Network): We extend our experiments to deeper neural network architectures. The results show that label noise GD continues to suppress noise memorization and improves generalization in these deeper models.\n\n**Appendix G.4** (Higher Order Polynomial ReLU): We also investigate the effect of higher order polynomial ReLU activations. Our findings confirm that the generalization improvement and suppression of noise memorization by label noise GD are maintained across different activation functions.\n\nTogether, these results provide strong empirical evidence that the regularization effects of label noise GD are not limited to the specific theoretical setup, but persist in deeper architectures, practical networks like VGG, and across different activation functions. We agree that developing a full theoretical framework for these cases is a valuable direction for future research\n\n---\n\n> **W2 & Q2**: Can other datasets be added for comparison, such as Clothing1M and noisy CIFAR-10N?\n\n**R2**: We appreciate the suggestion to evaluate label noise GD on larger and noisier real-world datasets such as Clothing1M and CIFAR-10N. In our current empirical study, we focused on controlled settings that allow us to systematically manipulate the signal-to-noise ratio (SNR), thereby closely aligning our experiments with the theoretical insights of the paper.\n\nSpecifically, our CIFAR-10 experiments are designed to create challenging low-SNR scenarios by injecting noise directly into the high-frequency Fourier components of the images [1]. This mechanism enables us to reduce the effective SNR in a principled and controllable way, simulating conditions where the underlying signal is weak and non-semantic (noisy) features dominate. By doing so, we are able to rigorously test the effectiveness of label noise GD in preventing overfitting to noise and in improving generalization, exactly in the regime that our theoretical analysis targets.\n\nWe would like to note that datasets such as CIFAR-10N represent an alternative but conceptually similar approach for controlling SNR, as they introduce label noise rather than feature noise. Both mechanisms, namely high-frequency corruption in CIFAR-10 and label corruption in CIFAR-10N, provide valuable testbeds for studying generalization in noisy settings. Each method probes different aspects of the learning process.\n\nWhile our current experiments already highlight the robustness of label noise GD in the presence of controlled feature-space noise, we agree that further evaluation on large-scale, real-world noisy datasets like CIFAR-10N and Clothing1M would be valuable and would further strengthen our claims. We plan to include such experiments in future work, and we expect the regularization benefits of label noise GD to generalize to these more challenging settings.\n\n---\n\n**Summary**:  We thank the reviewer again for their positive evaluation and helpful suggestions. We hope our responses have addressed your questions.\n\n---\n\n\n**Reference**\n\n[1] Ghorbani, B., Mei, S., Misiakiewicz, T. and Montanari, A., 2020. When do neural networks outperform kernel methods?. Advances in Neural Information Processing Systems, 33, pp.14820-14830."}, {"review_id": "5VU19bVJqS", "reviewer": "Reviewer_BYFK", "summary": "This paper explores how increasing label noise affects training in deep neural networks with SGD. The authors identify a clear three-stage progression: initially, the network learns well (generalizes); then, as noise increases, it starts to memorize the noisy labels (training error stays low but test error gets worse); and finally, in the high-noise regime, performance degrades overall. While this is to be expected,the authors propose a decomposition that lets them separately track the influence of clean and noisy data on the learning dynamics. They support their findings with a series of controlled experiments across datasets and architectures. The authors also provide an interpretation in terms of implicit regularization: as noise increases, SGD is biased away from sharp minima, which affects generalization. While this is more conceptual than formal (there’s no analytical expression for the regularizer), the overall message is clear.", "questions": "Can the decomposition framework be given a more formal grounding? While the empirical results are compelling, is there a theoretical interpretation of the decomposition — for instance, does it approximate an optimization bias or relate to any known statistical objective?\n\nWould the observed three-phase behavior still hold under more realistic or structured noise models? The current experiments assume uniform random label noise. It would be useful to understand whether similar transitions emerge under class-dependent or instance-dependent noise.\n\nHow robust are the findings to other design choices? For example, would the results hold under different optimizers (like Adam), smaller or larger batch sizes, or more modern architectures like transformers or vision models with pretraining?\n\nCould the authors make the link to theoretical work on implicit regularization more precise? While relevant papers are cited (e.g., HaoChen et al., Blanc et al., arXiv:2402.06443), the discussion remains qualitative. Are the observed degradation regimes consistent with the formal regularizers described in those works?\n\nIs the decomposition method applicable to other learning setups? For example, how would this behave in multi-index models, structured data (e.g., image patches), or low-data regimes?\n\nHow does this work differ from robust estimation frameworks in high dimensions, such as [Chien et al., arXiv:2305.18974]? That line of work addresses contamination from a statistical estimation angle. It would be useful to understand the conceptual or empirical boundaries between those approaches and the one proposed here.\n\nCan the authors make the implicit regularization more quantitative? In particular, is there an effective loss function (e.g., involving flatness measures like Hessian trace or spectral norm) that captures the observed transition as label noise increases?\n\nWould the three-stage phenomenon also emerge in synthetic or stylized theoretical settings? For instance, in the kind of setups considered by Villoutreix et al. (NeurIPS 2020) or student–teacher models, do we see a similar transition from learning to memorization to degradation?", "limitations": "yes", "rating": 4, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 3, "significance": 3, "originality": 2, "strengths_and_weaknesses": "The paper addresses a timely and important question: how does increasing label noise affect training dynamics in neural networks using SGD? A major strength is its originality — the authors introduce a decomposition method that separates the contributions of clean and noisy samples during training, providing new insight into the transition from learning to memorization and eventual degradation. The experiments are thorough, well-controlled, and reproducible, and the three-phase behavior they identify appears robust across datasets and architectures. The writing is clear and the methodology is easy to follow, making the results accessible and compelling. Overall, the work offers both conceptual and practical contributions to our understanding of generalization under label noise.\n\nThat said, there are some limitations. While the paper does cite relevant theoretical works on SGD under label noise — including HaoChen et al., Blanc et al., and arXiv:2402.06443 — the connection remains mostly qualitative. The authors could strengthen the paper by more directly engaging with these analyses, either by framing their results in similar terms or exploring where the empirical behavior aligns or diverges. In addition, the proposed decomposition, though intuitive and useful, lacks formal justification: it would be helpful to understand whether it corresponds to any known bias or objective. Finally, the paper could benefit from a broader discussion of related work, including recent advances in robust estimation and simplified theoretical models of learning under noise.", "was_revised": true, "final_justification": "This paper presents a novel decomposition of SGD dynamics under label noise, rigorously anchored via Cao et al. (NeurIPS ’22), and supported by controlled experiments that reproduce the predicted three-stage progression from learning to memorization to degradation. The rebuttal clarified the theoretical grounding and addressed key questions, strengthening confidence in the contribution. Remaining limitations concern empirical breadth (datasets beyond CIFAR-10, alternative optimizers, structured noise) and the still qualitative link to implicit regularization, but these do not undermine the core advance. Overall, I find the work theoretically solid, timely, and impactful, and I recommend acceptance.", "rebuttal": "We thank the reviewer for their thorough and thoughtful assessment, as well as for recognizing the originality and practical relevance of our work. Below, we address the specific questions and suggestions in detail.\n\n---\n\n> **W1**: While the paper does cite relevant theoretical works on SGD under label noise — including HaoChen et al., Blanc et al., and arXiv:2402.06443 — the connection remains mostly qualitative. The authors could strengthen the paper by more directly engaging with these analyses, either by framing their results in similar terms or exploring where the empirical behavior aligns or diverges.\n\n**R1**: We agree that a more direct engagement with the theoretical analyses of HaoChen et al., Blanc et al., would strengthen our paper. These works provide formal arguments showing that label noise (or stochasticity) in SGD induces an implicit bias towards flatter minima, which is believed to enhance generalization. While our primary focus is on the training dynamics and generalization gap in the low SNR regime, our theoretical results are consistent with the idea that **label noise GD promotes “flatter” solutions by discouraging overfitting to noise**. Although we do not explicitly quantify flatness in our analysis, the boundedness of noise memorization coefficients and the improved generalization performance may suggest an implicit bias toward flatter minima. We will further discuss this connection in the revision.\n\n---\n\n> **W2**: In addition, the proposed decomposition, though intuitive and useful, lacks formal justification: it would be helpful to understand whether it corresponds to any known bias or objective. \n\n**R2**:  We would like to clarify that our decomposition method is closely related to, and can be **rigorously grounded** by, the theoretical results established in Cao et al. [1]. Specifically, the iterative equations and uniqueness results for the signal-noise decomposition presented in their work can be directly applied to our setting. Therefore, our decomposition enjoys a solid theoretical foundation.\n\n\n---\n\n> **Q1**: Can the decomposition framework be given a more formal grounding? While the empirical results are compelling, is there a theoretical interpretation of the decomposition — for instance, does it approximate an optimization bias or relate to any known statistical objective?\n\n**A1**: As also discussed in response to W2, our method is not just intuitive and empirically effective, but can be rigorously justified based on the theoretical results established by Cao et al. [1]. It provides a **formal signal-noise decomposition** and proves the uniqueness and dynamics of the decomposition coefficients, which apply directly to our setting. In particular, in the **high-dimensional regime**, the Gaussian noise vectors are **nearly orthogonal** to each other with high probability, which is a crucial property that ensures the uniqueness and stability of the decomposition. This high-dimensional geometry underlies the effectiveness and theoretical soundness of our approach.\n\n---\n\n> **Q2**: Would the observed three-phase behavior still hold under more realistic or structured noise models? The current experiments assume uniform random label noise. It would be useful to understand whether similar transitions emerge under class-dependent or instance-dependent noise.\n\n**A2**:  In our experiments (see **Appendix G.3**), we have evaluated label noise GD under various noise distributions and rates, including uniform and Gaussian label noise. The results consistently show that label noise GD suppresses noise memorization and enhances signal learning across these settings. We agree that it would be interesting to explore more structured noise models, such as class-dependent or instance-dependent noise, and we leave this as a direction for future work.\n\n---\n\n> **Q3** How robust are the findings to other design choices? For example, would the results hold under different optimizers (like Adam), smaller or larger batch sizes, or more modern architectures like transformers or vision models with pretraining?\n\n**A3**: Thank you for the suggestion. Our current experiments are primarily designed to verify the theoretical claims regarding label noise GD within a controlled setting, and we have not systematically evaluated robustness to different optimizers or more modern architectures such as transformers or pre-trained vision models. While these questions are highly relevant and interesting, they are beyond the scope of the present work, which focuses on foundational theory and controlled empirical validation. We agree that further exploration along these lines would be valuable for understanding the broader applicability of our results.\n\n---\n\n> **Q4**: Could the authors make the link to theoretical work on implicit regularization more precise? While relevant papers are cited (e.g., HaoChen et al., Blanc et al., arXiv:2402.06443), the discussion remains qualitative. Are the observed degradation regimes consistent with the formal regularizers described in those works?\n\n**A4**: Thank you for the question. In our analysis, we show that, for label noise GD, the algorithm effectively suppresses noise memorization. As a result, the population test loss remains small even in the presence of significant label noise. This behavior contrasts with standard GD, where noise memorization can dominate and lead to a non-vanishing lower bound on test error. Our findings are in line with the theoretical understanding of implicit regularization, as described in HaoChen et al., Blanc et al. \n\n---\n\n> **Q5**: Is the decomposition method applicable to other learning setups? For example, how would this behave in multi-index models, structured data (e.g., image patches), or low-data regimes?\n\n**A5**:  In this work, our decomposition method can be extended to multi-patch structured cases, and a similar idea could be used to decompose a multi-index model. The approach of separating signal and noise contributions in the learning dynamics remains applicable in these more general settings\n\n---\n\n> **Q6 & W3**: How does this work differ from robust estimation frameworks in high dimensions, such as [Chien et al., arXiv:2305.18974]? That line of work addresses contamination from a statistical estimation angle. It would be useful to understand the conceptual or empirical boundaries between those approaches and the one proposed here.\n\n**A6**: While those approaches address contamination from a classical statistical estimation perspective, our decomposition method provides a complementary view by focusing on the **learning dynamics under label noise GD** in deep neural networks. Specifically, our work contributes a novel theoretical analysis that explicitly separates the evolution of signal and noise components during training, revealing how label noise affects memorization and generalization in modern neural networks. This dynamic decomposition framework offers new insights into the transition from learning to memorization, which are difficult to capture using traditional robust estimation techniques and other simplified theoretical models of learning under noise.  \n\n---\n\n> **Q7**: Can the authors make the implicit regularization more quantitative? In particular, is there an effective loss function (e.g., involving flatness measures like Hessian trace or spectral norm) that captures the observed transition as label noise increases?\n\n**A7**: Thank you for this insightful suggestion. Our theoretical results may suggest that label noise influences the optimization trajectory and generalization performance in a manner consistent with a bias toward flatter solutions as label noise prevents the network from overfitting to noisy labels. Developing a more quantitative link between label noise GD with flatness-based measures is an important direction for future work, and we will highlight this point in the revised manuscript.\n\n---\n\n> **Q8**: Would the three-stage phenomenon also emerge in synthetic or stylized theoretical settings? For instance, in the kind of setups considered by Villoutreix et al. (NeurIPS 2020) or student–teacher models, do we see a similar transition from learning to memorization to degradation?\n\n**A8**: Our experiments in both synthetic and real-world settings consistently show that label noise GD effectively prevents noise memorization and improves generalization. While we have not yet systematically explored the student–teacher setup, based on the underlying dynamics and related theoretical insights, we expect that a similar phenomenon would also emerge in such models.\n\n---\n\n**Summary**: We thank the reviewer again for their careful reading and valuable feedback. We hope our clarifications and additional results address your concerns.\n\n---\n\n**Reference**\n\n\n\n[1] Yuan Cao, Zixiang Chen, Misha Belkin, and Quanquan Gu. Benign overfitting in two-layer 382 convolutional neural networks. Advances in Neural Information Processing Systems, 35:25237– 383 25250, 2022"}, {"review_id": "hpIjI4RGnG", "reviewer": "Reviewer_jMWd", "summary": "This paper considers the problems of generalization when we have low signal to noise ratio. The paper shows two results. First, for a very specific high dimensional setup the paper shows that early stopped gradient descent does not generalize well. To mitigate this, the paper suggests a labelling flipping gradient descent, where certain labels are randomly flipped each iteration. The paper then shows that early stopped label flipping gradient descent does generalize.", "questions": "1. Comparison between stopping times. The stopping times in Theorems 3.2 and 3.3 are different. From inspection it looks like Theorem 3.2 you stop much later. Can the authors comment on this?\n\n2. Since both algorithms are about early stopped methods, can you something about the risks at convergence?\n\n3. How do the choice of metrics affect things? I.e. classification versus regression similar to [B],  (Figures 3, 4) [C], and the consistency vs calibration discussion in [D]?\n\n[B] Muthukumar, Vidya, Adhyyan Narang, Vignesh Subramanian, Mikhail Belkin, Daniel Hsu, and Anant Sahai. \"Classification vs regression in overparameterized regimes: Does the loss function matter?.\" Journal of Machine Learning Research 22, no. 222 (2021):\n\n[C] Kausik, C., Srivastava, K., & Sonthalia, R. (2024). Double Descent and Overfitting under Noisy Inputs and Distribution Shift for Linear Denoisers. Transactions on Machine Learning Research. Available at https://openreview.net/forum?id=HxfqTdLIRF\n\n[D] Wu, Jingfeng, Peter Bartlett, Matus Telgarsky, and Bin Yu. \"Benefits of Early Stopping in Gradient Descent for Overparameterized Logistic Regression.\" arXiv preprint arXiv:2502.13283 (2025).", "limitations": "N/A", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 2, "significance": 2, "originality": 3, "strengths_and_weaknesses": "**Strength**\n\n1. The paper present concrete theoretical results that are well motivated. The two theorems 3.2 and 3.3 complement each other and study an import phenomenon. \n\n2. The proof sketch is well appreciated. In particular, it very clearly highlights this decompositions and shows that the $w$'s live in the signal subspace of noise subspace. Thus, making the noise overfitting phenomenon precise. \n\n**Weaknesses**\n\n1. The setup for the paper is quite specific\n\n    a. Different signal and noise components with noise being orthogonal to the signal - as compared to signal plus noise model. Where the noise interacts with the signal \n\n    b. Relu squared activation function. It is unclear to the reviewer why this activation is chosen compared to standard activation function.\n \n    c. The usage of 1-D convolutions instead of a standard feedforward network. \n\n2. Lack of insights into the phenomenon. This is a significant weakness, while the the theoretical results are clear and provide an interesting result. The paper claims that the label flipping helps as the noise acts as a regularization, but it would be good to get more intuition about why this is true. On the surface in Theorem 3.3, the stopping time, the generalization bound, and probability with which we are in a good trajectory are independent of $p$. Hence if I make $p$ really small, say $p = d^{-d}$. Then with probability 1 we should no flips during training. Yet this generalizes while GD does not. \n\n3. Extreme high-dimensionality. While I recognize that this is common in the benign overfitting literature. I still think it is a negative. For example [A] in very similar setting show benign overfitting for much lower dimensions \n\n4. I think the presentation and writing could be improved, in particular in the proof sketch section. \n\n[A] Karhadkar, Kedar, Erin George, Michael Murray, Guido F. Montufar, and Deanna Needell. \"Benign overfitting in leaky relu networks with moderate input dimension.\" Advances in Neural Information Processing Systems 37 (2024)", "was_revised": true, "final_justification": "As such I think we have reached an agreement that while the assumptions might be needed for tractability they are a weakness.\n\nAdditionally the paper needs a revision based on the above discussion. \n\nBased on the positive scores from the other reviewers and the clarifications. I’m willing to increase my score. However I think the paper is borderline.", "rebuttal": "We thank the reviewer for their careful reading, positive assessment of our theoretical contributions, and constructive feedback. We address the main concerns and questions below.\n\n---\n\n> **W1**: The setup for the paper is quite specific. a. Different signal and noise components with noise being orthogonal to the signal. b. Relu squared activation function. c. The usage of 1-D convolutions instead of a standard feedforward network.\n\n**R1**: a. The orthogonality assumption between signal and noise is standard in theoretical works aiming for tractable signal-noise separation, and is also adopted in the benign overfitting literature [1]. Our framework can be extended to cases where the signal and noise components are not strictly orthogonal. While relaxing orthogonality introduces additional interaction terms between signal and noise, these terms can be effectively bounded under sufficiently high-dimensional settings [2]. \n\nb.  The choice of squared ReLU is motivated by the analytic tractability it offers in our setting, especially when the second layer is fixed. Notably, squared ReLU corresponds to the smallest polynomial power for which both signal and noise components exhibit exponential growth, making it the minimal setting that captures the key dynamics. As discussed in the main text and Appendix G.4, we have verified that our key empirical findings extend to higher-order activations (e.g., ReLU$^3$, ReLU$^4$), and we expect the main phenomena to be present for standard ReLU as well, though the analysis is more involved.\n\nc. We use 1D convolutions primarily to align with the multi-patch data structure, which has been widely studied for its relevance to feature learning [1,2,3]. This choice facilitates a clean separation between patches and aligns our setup with prior literature.\n\n---\n\n> **W2**: Lack of insights into the phenomenon. On the surface in Theorem 3.3, the stopping time, the generalization bound, and probability with which we are in a good trajectory are independent of $p$. \n\n**R2**:  The requirements on both the lower and upper bounds for the flipping rate $p$ are crucial for the effectiveness of label noise GD, particularly in the second phase of training.\n\nIn our analysis, the conclusion about signal learning in Lemma 4.5 relies on having an upper bound on $p$. If $p$ is too large, too many noisy labels are introduced, and the signal component cannot grow, which prevents effective signal learning. At the same time, the result on the boundedness of the noise component in the first part of Lemma 4.5 holds only when $p$ has a constant lower bound. If $p$ is too small, the regularization effect vanishes and noise memorization is no longer suppressed, as noise memorization term no longer behaves as a controlled martingale.\n\nWe will explicitly state in Assumption 4.1 that $p$ must be bounded above and below by constants, and we will point out these requirements clearly in the relevant lemmas and proofs.\n\n---\n\n> **W3**: Extreme high-dimensionality. For example [A] in very similar setting show benign overfitting for much lower dimensions\n\n\n**R3**: Thank you for raising this point. Our choice of the high-dimensional regime is widely adopted to enable precise, tractable analysis of gradient descent dynamics and generalization in neural networks [1,2,3].\n\nWe appreciate the reviewer’s reference to [A], which indeed demonstrates benign overfitting with leaky ReLU activation and hinge loss in the lower-dimensional. However, their setup differs from ours both in terms of the activation function (leaky ReLU vs. squared ReLU) and the loss (hinge vs. cross-entropy). In particular, hinge loss promotes hard margin solutions, whereas logistic loss leads to different implicit bias and convergence dynamics. Our work specifically focuses on the low SNR setting and investigates the effect of label noise GD, which presents distinct analytical challenges. We will cite [A] and discuss these differences more explicitly in the revised manuscript.\n\n---\n\n> **W4**: I think the presentation and writing could be improved, in particular in the proof sketch section.\n\n**R4**: Thank you for this suggestion. In the revised manuscript, we will improve the presentation and clarity of the proof sketch section, explicitly connecting the arguments to the upper and lower bounds on the flipping rate p. This should enhance the readability and help readers better understand the role of p in the analysis.\n\n---\n\n> **Q1**: Comparison between stopping times. The stopping times in Theorems 3.2 and 3.3 are different. From inspection it looks like Theorem 3.2 you stop much later.  \n\n**A1**: The time thresholds for standard GD and label noise GD are not directly comparable, as they correspond to different evaluation criteria. Specifically, the time threshold for standard GD represents the time required for the training loss to converge below a certain threshold $\\epsilon$, whereas the time threshold for label noise GD pertains to achieving sufficiently low 0-1 test loss. Therefore, comparing the running time for the two algorithms directly is not fair, as they are optimizing different objectives.\n\nHowever, to facilitate a meaningful comparison, we have derived a ratio between the time thresholds under Assumption 4.1. By further setting $m^2 = \\log(6/(\\sigma_0 \\| \\mu\\|_2))/\\epsilon$. we can obtain the ratio between the time thresholds as follows:\n\n$$ t\\_{GD}/t\\_{LNGD} =  \\Theta( \\frac{n \\| \\mu\\|^2_2}{ \\sigma^2_pd })  = \\Theta(n \\rm{SNR}^2)$$\n\nAccording to Assumption 4.1, we assume that $n SNR^2 \\ll 1$, which implies that label noise GD requires more time to achieve good test performance compared to the convergence time of training loss for standard GD, which is consistent with the empirical results demonstrated in Figure 1.\n\n---\n\n> **Q2**: Since both algorithms are about early stopped methods, can you something about the risks at convergence?\n\n**A2**: Regarding Theorem 3.2, the convergence rate is of order$ 1/\\epsilon$, where $\\epsilon$ is the upper bound on the training loss. As $\\epsilon$ is made arbitrarily small, the required running time increases without bound. As a result, the conclusions regarding the behavior of training and test errors hold with high probability and persist for sufficiently large time steps.\n\nFor Theorem 3.3, the theorem describes the transition from a regime where noise memorization dominates to one where signal learning becomes dominant. After this transition, our experiments show that the training loss continues to oscillate and the test error remains consistently small. While these empirical observations suggest that the generalization guarantee persists in the long run, providing a complete theoretical analysis of the training dynamics for all time remains an interesting problem for future research.\n\n---\n\n> **Q3**: How do the choice of metrics affect things? I.e. classification versus regression similar to [B], (Figures 3, 4) [C], and the consistency vs calibration discussion in [D]?\n\n**A3**:  Thank you for this insightful question and for pointing out these relevant works. We agree that the choice of loss function and evaluation metric can have a substantial impact on both the optimization dynamics and generalization performance, particularly in overparameterized regimes.\n\nOur main analysis and results focus on the logistic loss for binary classification. While this is a natural and widely studied choice for classification tasks, it is well known (as shown in [B], [C], and [D]) that the training loss, test loss, and implicit bias induced by the loss function may differ significantly between regression and classification objectives. For instance, [B] demonstrates that least-squares and hard-margin SVM can yield the same interpolating solution in linear models, but their test performance may diverge depending on whether regression or classification metrics are used. [D] shows that, for overparameterized logistic regression, early stopping leads to well-calibrated solutions with small excess risk, while running GD to convergence leads to statistical inconsistency.\n\nIn our context, the implicit regularization and the dynamics of label noise GD are analyzed specifically for logistic loss, so our theoretical guarantees and empirical findings apply to classification performance under this loss. The behavior may differ under other loss functions or when evaluated with alternative metrics, and analyzing these differences is an important direction for future work. We will cite these works and clarify the scope of our results in the revised manuscript.\n\n---\n\n**Summary**: We thank the reviewer again for the thoughtful critique and helpful questions, and hope these clarifications address your concerns.\n\n---\n\n**References**\n\n[1] Cao et al. Benign overfitting in two-layer convolutional neural networks. NeurIPS 2022.\n\n[2] Kou et al. Benign overfitting in two-layer ReLU convolutional neural networks. ICML 2023.\n\n[3] [3]  Chen et al. Why does sharpness-aware minimization generalize better than sgd? NeurIPS 2023.\n\n[A] Karhadkar, Kedar, Erin George, Michael Murray, Guido F. Montufar, and Deanna Needell. \"Benign overfitting in leaky relu networks with moderate input dimension.\" Advances in Neural Information Processing Systems 37 (2024)\n\n[B] Muthukumar, Vidya, Adhyyan Narang, Vignesh Subramanian, Mikhail Belkin, Daniel Hsu, and Anant Sahai. \"Classification vs regression in overparameterized regimes: Does the loss function matter?.\" Journal of Machine Learning Research 22, no. 222 (2021)\n\n[C] Kausik, C., Srivastava, K., & Sonthalia, R. (2024). Double Descent and Overfitting under Noisy Inputs and Distribution Shift for Linear Denoisers. Transactions on Machine Learning Research.  \n\n[D] Wu, Jingfeng, Peter Bartlett, Matus Telgarsky, and Bin Yu. \"Benefits of Early Stopping in Gradient Descent for Overparameterized Logistic Regression.\" arXiv preprint arXiv:2502.13283 (2025)."}]

Author rebuttal:

Meta-review: This paper theoretically studies the use of label noise for improved generalization of gradient descent learning in low signal-to-noise ratio (SNR) settings.

The authors show that the addition of label noise implicitly regularizes the harmful memorization of the noise and effectively improves the learning of the underlying signal in the data. This happens in the low SNR setting where the noise in the data is stronger and therefore limiting its memorization is important for benign overfitting.

The theory considers an analytically tractable setting of binary classification, a corresponding two-layer convolutional neural network with its last layer fixed and squared ReLU activation, and a signal-noise data model. To complement the relatively simple theoretical setting, the authors provide experiments for additional settings (e.g., other activation functions, training both layers of a two-layer network, deeper networks, and datasets based on classes from MNIST and CIFAR-10). As mentioned in the reviews, the experiments can be more extensive (for example, including more optimizers as Reviewer BYFK commented), but if we judge this paper as a theoretical contribution then its empirical depth is sufficient.

While the idea of label-noise GD is not new, the authors provide new analysis and findings that contribute to the theory of benign overfitting and optimization dynamics. In particular, as written by Reviewers ajKN and BYFK, the martingale-based argument for analyzing the noise memorization is a significant contribution.

Therefore the recommendation is to accept this paper.
Decision: Accept (poster)