Label Noise Gradient Descent Improves Generalization in the Low SNR Regime

We thank the reviewer for the helpful feedback. We address the technical concerns below.

---

one is free to choose whatever model architecture they want

We do not claim that standard GD always fails to learn this problem regardless of the architecture and hyperparameter – such an unconditional lower bound is extremely difficult to establish. We are not interested in the statistical complexity of solving this problem under some notion of “optimal architecture” — in fact, it is clear that the target function in our signal-noise data model (Definition 2.1) can be expressed by a linear classifier, so if the motivation is to simply learn this binary classification task, many well-known and influential papers on feature learning theory Allen-Zhu & Li (2020),Jelassi et al. 2022,Wen 2021,Shen et al. (2022),Kou et al. 2023 are meaningless and ought to be rejected, because there is no point of using a (wide) neural network when the task can be solved by a linear model.

In other words, the signal-noise model has been extensively studied not because it represents an intrinsically challenging function class that requires extensive network width to learn; instead, the setting provides a tractable model for the nonlinear optimization dynamics, so that one can reason about how simple modifications of the learning algorithm affect the order of signal learning vs. overfitting. More specifically, it is well known that deep neural networks are capable of overfitting to noise in the training set, yet gradient-based optimization tends to avoid such memorization solutions. The theory community introduced the signal-noise data model to capture this phenomenon, where the key features are that (i) the data contains a noise component that potentially leads to overfitting, and (ii) the neural network is expressive enough to memorize noise. Consequently, prior works Allen-Zhu & Li (2020),Jelassi et al. 2022,Cao et al. 2022,Wen 2021,Shen et al. (2022),Chen et al. 2023 and our analysis requires a minimum width of the neural network so that noise memorization is feasible. Setting the width to be very small (e.g., m=3) limits the network capacity and therefore rules out the possibility of overfitting — this explicit capacity control is tangential to our investigation where harmful overfitting should be avoided by algorithmic regularization.

While we do not argue that all our theoretical assumptions are justified simply because prior works also consider similar restrictions, we would like to point out that these well-cited papers in feature learning theory were not dismissed by the theory community because "the model architecture looked quite strange" or the studied learning problem is not statistically hard; rather, they serve as an important first step toward understanding more complicated feature learning dynamics in more realistic data settings.

We hope the reviewer can re-evaluate our contributions in light of this perspective, and reconsider the statement that “for the sake of that student and the learning theory community, I must insist on rejecting this submission,” which we believe is inappropriate.

• the paper is quite misleading due to its catchy claim "label noise GD improves generalization"

Our primary goal is to provide a theoretical understanding of the differences in generalization between label noise GD and standard GD in the well-studied signal-noise data model. To ensure the soundness of our theoretical claims, we have explicitly detailed our data model, neural network structure, and provided proof sketches. We do not claim that label noise GD is universally superior to standard GD in all settings (in fact, benign overfitting of standard GD has been established in many prior works in the high-SNR regime). Our analysis is specific to the signal-noise setting, and we argue that the benefit of label noise injection is prominent in the low SNR setting (see response below on the experimental setup), which is known to be a challenging regime to establish benign overfitting.

We believe that the mechanism presented in Theorem 3.2 (regularization effect through label noise) is nontrivial and fairly robust in the studied signal-noise data model – see our response to the experimental settings.

---

I did some experiments and came to the conclusion that the claim of this paper "label noise GD can be better than standard GD" only works for very limited situations.

As discussed in our previous response, decreasing the network width reduces the model capacity and hence its ability to memorize noise. Hence it is not surprising that overfitting is less of an issue regardless of the optimization algorithm. Our analysis considers the setting where the network has enough capacity to memorize the training labels, yet optimization provides additional regularization that prevents overfitting. Nevertheless, we respectfully disagree that “the claim can be easily invalidated by just changing one parameter”. We make the following clarifications.

• First, based on the plots you provided, we noticed that the training loss of label noise GD appears to be diverging, which indicates that the learning rate is too large. To investigate this further, we adjusted the learning rate by using a smaller value in your provided code. The updated results, which can be found https://postimg.cc/py7B7BXB, show that label noise GD performs at least as well as standard GD in achieving high test accuracy, even though our theoretical analysis excludes such narrow-width settings.

• Second, we conducted additional experiments for the narrow-width model ($m = 3$) under smaller signal-to-noise ratio (SNR) $\sigma_p = 10$. Specifically, we used the following parameter settings: $\eta = 0.002$, $m = 3$, $\mu[0]$ = 2, and $\sigma_p = 10$. The results, which can be found: standard GD (https://postimg.cc/vgZzRqV0); label noise GD (https://postimg.cc/D8HYrTXn), show that label noise GD outperforms standard GD under these conditions. These simulations were based on the code you provided, with the only modifications being the value of $\sigma_p$ and setting the learning rate to 0.002. These findings suggest that even for narrow models, label noise GD can still be advantageous when the SNR is low.

• Third, to further confirm that label noise GD can consistently outperform standard GD in the low SNR regime, we conducted an additional experiment involving a hyper-parameter search on the learning rate. This time we used a larger width $m = 10$, which is more aligned with our theoretical requirement on the network width compared to $m = 3$. The specific settings were: $m = 10$, $\sigma_p = 2$, and $\mu[0] = 2$, while keeping other hyper-parameters unchanged. We conducted a search over different learning rates from the set [0.01, 0.05, 0.1, 0.5, 1.0]. The results show that standard GD failed to achieve high test accuracy across all learning rates (https://postimg.cc/d74292xr), while label noise GD achieved almost 100% test accuracy when using $\eta = 0.1$ (https://postimg.cc/zHRT59XF). These results corroborate the claim that label noise GD has significant advantage in the low SNR regime, particularly when using an appropriate network width that meets the theoretical conditions.

• Lastly, following your suggestion, we conducted an experiment on a real-world dataset using MNIST. We introduced noise to the dataset to align with our theoretical setting and compared the performance of standard GD and label noise GD under this setting. The results are consistent with our theoretical findings—label noise GD demonstrated improved generalization compared to standard GD, especially in noisy environments. These additional findings are now included in Appendix E.2 of the revised manuscript.

We thank the reviewer for the response. We address the additional concerns below.

---

Regarding the three theoretical papers you cited here, they were studying the implicit noise induced by SGD. However, none of the three cited papers suggested that flipping the labels during training is a good idea. I am very familiar with this line of research on SGD. One of the main arguments is that SGD can be better than GD due to the stochasticity, which I think is a beautiful result, but this is drastically different from flipping the labels.

As mentioned in Line 210 of the main text, our label-flipping procedure was introduced in Damian et al. 2021, which the reviewer should be very familiar with. This extension is needed since the additive label noise used in the regression analysis is not suited for binary classification – see their Section 5.1. Note that all experiments on CIFAR-10 + ResNet in Damian et al. 2021 were conducted using this label-flipping algorithm.
Besides, Haochen et al. 2021 trained a VGG19 model on CIFAR100 with flipping noise, and found adopting flipping label noise achieves better test error (around 15% improvement over baseline). Similar label flipping regularization appeared in Xie et al. 2016., and it has been argued that this approach can be cast as label smoothing methods Li et al. 2020.

We have added these references in the revised manuscript to clarify the role of label flipping and how it relates to existing works on regularization.

---

Thus, Jelassi & Li (2022) asked if momentum can always improve generalization. They constructed an example where momentum actually hurts generalization, and thus their conclusion was "momentum does not always lead to a higher generalization in deep learning". This conclusion is sound, because like I said in my review, one can prove that something does not work by showing a counter-example.

We respectfully disagree. The main contribution of Jelassi & Li (2022) is the analysis of GD vs. GD+M in the signal-noise data model where the conclusion is that GD+M indeed improves generalization – this is in the exact same vein as our comparison of SGD vs. label noise GD.
The claim that "momentum does not always lead to a higher generalization in deep learning" is merely confirmed in a toy experiment to motivate their introduction of the signal-noise data model, in which GD+M provably avoids overfitting.
We are not aware of any existing works on the signal-noise data model where the contribution is only a counterexample that a specific algorithm does not work. If anything in Jelassi & Li (2022) counts as a “counterexample”, it would be the negative result that GD fails to generalize (Theorem 4.1), which is established under similar hyperparameters (width, learning rate, etc.) as our analysis.

---

The only purpose of my experiment is to show that your result is not robust w.r.t. the parameters. Choosing a smaller m is the very first thing I thought of.

Please refer to our Part I response. Choosing a network width to be small introduces additional capacity control which reduces overfitting without algorithmic regularization. As mentioned earlier, setting $m=3$ will also break the conclusion in prior works on the comparison of algorithms in the signal-noise model (e.g., Jelassi and Li 2022, Chen et al. 2023). In this regard, we do not think that the claims in any of these works are more “sound and robust” than ours.

---

Suggestion on changing the Title

We have revised our title to:"How Does Label Noise Gradient Descent Improve Generalization in the Low SNR Regime?" This title suggests an investigative nature of our study (rather than presenting a universally applicable claim), analogous to the title of Jelassi and Li 2022. We hope this addresses the reviewer's concern on the presented scope of our results.

We thank the reviewer for the response.

Jelassi & Li emphasized that their theory only works for small-margin data, and they empirically validated it with small-margin data in CIFAR-10. They were not claiming that their theory would work in a very general setting like "low SNR regime".

The term “small margin” is defined in the theoretical binary classification setting in the signal-noise data model, parallel to our definition of “low SNR”. Similar to Jelassi & Li 2022, we have also emphasized that our theory applies to the particular single-noise model in the abstract and introduction.
If the reviewer thinks that our title is too general and constitutes overclaiming, we do not see why the claims in Jelassi & Li 2022 are sound instead of misleading, as their title does not include the qualifier “small margin data”.

Regarding the modified CIFAR-10 experiment in Jelassi & Li 2022, the margin (or SNR) of real-world data is not known a priori, and there is no explanation of why shuffling the RGB channels corresponds to modulating the margin.
Nevertheless, we have conducted experiments on the CIFAR-10 dataset where a VGG-16 model is optimized by full-batch GD vs. label-noise GD (analogous to Figure 1 in Jelassi & Li 2022). We trained the model on 10,000 samples, and to isolate the effect of label noise, we disabled data augmentation and batch normalization. The learning rate was set to 0.02, and the label flipping rate was 0.2.
The results are available here, where we observe ~2% improvement in the test accuracy due to label noise, even though it is not clear if this dataset has low SNR. We also note that our baseline for full-batch GD achieves higher accuracy than that reported in Jelassi & Li 2022. This indicate that, in real-world scenarios, label-noise GD can outperform standard GD, which is consistent with the findings in Haochen et al. 2021.

We will provide additional updates on synthetic experiments where the SNR can be explicitly controlled.

---

None of the papers you provided in your new response empirically showed that flipping labels could be preferable in real applications.

We do not argue that label noise is an indispensable component for state-of-the-art algorithms in practical datasets such as ImageNet – such SOTA performance is not achieved by standard SGD training (without preconditioning, data augmentation, etc.).
This being said, it has been empirically observed in Haochen et al. 2021 that label flipping noise closes the gap between small- and large-batch training, and the benefit (due to implicit regularization) of such label noise has been studied in Damian et al. 2022. We believe that this provides sufficient justification to study label noise GD in the signal-noise data model and to characterize how this algorithmic regularization contributes to benign overfitting.

---

Finally, while we appreciate the reviewer’s constructive feedback, we find it frustrating that a substantial part of our response has been consistently overlooked. We summarize these points as follows.

1. The reviewer stated in the original review that the primary concern was that “the experimental results I present here establish the fact that the claim of this paper, that is "label noise GD is better than GD", is not very robust and not very sound”. We have clarified in our previous response that
   • The experiment where GD achieves comparable generalization performance does not contradict our theoretical findings. Moreover, we have shown that by further decreasing the SNR in this narrow-width setting, the benefit of label noise is once again observed.
   • The experiment where “label noise GD is much worse than standard GD” is due to large learning rate that leads to non-convergence.
2. The reviewer wrote in the followup comment that “I suggest you do more sensitivity analysis and ablation studies”. Note that in our first round of response, we have already provided such a learning rate sweep for GD in our signal-noise data model. We have also included additional experiments on modified MNIST and CIFAR where the SNR can be modulated (see Appendix E).
3. Regarding the reviewer’s concern on our theoretical setup, we have explained the role of different components of our model (width, noise patch, activation, etc.) and referred to earlier works where similar conditions were introduced.
4. We have clarified claims that the reviewer made on the literature that we find misleading in our second round of response, including
   • The review claimed “none of the cited papers suggested that flipping the labels during training is a good idea”, when we explicitly mentioned in the main text that our label flipping procedure originated from one of the cited papers.
   • The reviewer claimed that the conclusion of Jelassi and Li (2022) was "momentum does not always lead to a higher generalization in deep learning", while this is not the central contribution of the work.

We thank the reviewer for the thoughtful comment and constructive feedback. We address the technical concerns below.

---

W1: The paper only contains synthetic experiments, which serve to verify the theory directly. It seems to me that one could practically mimic Definition 2.1 by concatenating random noise to images from standard datasets (randomly to either the front or back).

R1: We appreciate your suggestion regarding practical verification. In response, we have conducted an additional experiment using the MNIST dataset, where we concatenated random noise to each image (either at the front or back), in a manner similar to Definition 2.1. This setup aims to mimic the low SNR setting by introducing irrelevant noisy features while retaining the core signal in the original images.

The noise level was set to $\sigma_p = 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 a "signal patch." We focused on the digits '0' and '1', using $n = 100$ samples for training and 200 samples for testing. The learning rate was set to $\eta = 0.001$, and the width was set to $m=20$, with a label noise level of $p = 0.15$. The results, shown in Figure 4, were consistent with our theoretical conclusions, reinforcing the insights derived from our analysis. We show the corresponding result in Appendix E.2.

---

W2: Theorem 3.1 has an analogous result in [1] (Theorem 4.4) and it would be helpful to compare the two more directly. It would also be useful to provide more motivation for using squared ReLU as opposed to other modifications -- for what pieces of the analysis is this necessary? Lastly, it would be nice to sketch some intuition for proving the supermartingale property in Lemma D.4; I looked at the proof but it's hard to get a sense from the calculations themselves.

R2: The main difference between our Theorem 3.1 and Theorem 4.4 from [1] lies in the condition under which harmful overfitting occurs for standard GD. In [1] (Theorem 4.4), the condition that leads to harmful overfitting is $n^{-1} SNR^{-q} = \tilde{\Omega}(1)$, where $q \ge 3$. In contrast, our work shows that even under a different condition, we require $n^{-1} SNR^{-2} = \tilde{\Omega}(1)$ harmful overfitting can still occur.

The choice of squared ReLU activation is motivated by the fact that we do not optimize the second-layer parameters. We aim for the 2-homogeneous squared ReLU activation to mimic the behavior of training both layers simultaneously in a standard ReLU network. This higher-order homogeneity amplifies feature learning (e.g., see Chizat & Bach, 2020; Glasgow, 2023) and helps create a more significant gap between signal learning and noise memorization, which is crucial for our analysis. A similar effect can be achieved by a smoothed ReLU activation with local polynomial growth as in Allen-Zhu & Li (2020); Shen et al. (2022)

The supermartingale property in Lemma D.4 is established to demonstrate how the introduced label noise keeps the noise memorization coefficient oscillating within a range of constant values. More specifically, we define:$\iota^{(t)}\_i = \frac{1}{m} \sum\_{r=1}^m \overline{\rho}^{(t)}\_{y\_i, r,i}$, where $\iota^{(t)}\_i$​ represents the noise memorization coefficient at iteration t. Under label noise GD, its evolution can be approximated as:

$$\iota^{(t+1)}\_{i} \approx (1 + \frac{\eta \sigma^2\_p d}{(1+\exp((\iota^{(t)}\_{i} )^2))nm}) \iota^{(t)}\_{i}, \text{ with prob } 1-p.$$ $$\iota^{(t+1)}\_{i} \approx (1 - \frac{\eta \sigma^2\_p d}{(1+\exp(-(\iota^{(t)}\_{i} )^2))nm}) \iota\_{i}, \text{ with prob } p.$$

From this equation, we observe that the probability of an increase ($1−p$) is greater than the probability of a decrease ($p$). On the other hand, the magnitude of an increase is smaller than that of a decrease. This implies that while there is a higher chance of an increase, each increase is relatively small; conversely, decreases are less frequent but larger in magnitude. This balancing effect results in the oscillating behavior of the noise memorization coefficients.

We use a one-sided Azuma inequality based on the supermartingale property because the noise memorization coefficient originates from a small order value, and the inequality provides a quantitative tool to characterize the oscillatory nature of noise memorization. This helps demonstrate that the noise remains controlled.

Thank you for your follow-up questions and for your interest in our work. We are glad that you found the modified MNIST experiments encouraging. Below, we address your concerns in detail.

---

how sensitive are the plots to the choice of noise parameters and normalization

R: To assess the sensitivity of our methods to the choice of noise parameters and signal normalization, we conducted additional experiments on a modified MNIST dataset. Specifically, we varied the signal normalization values from 60 to 140 and the noise levels 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 of $\eta = 0.001$, using either standard gradient descent (GD) or label noise GD.

The results consistently show that label noise GD achieves higher test accuracy compared to standard GD across all tested configurations. This demonstrates the robustness of label noise GD to variations in both noise and signal normalization parameters, highlighting its effectiveness in handling different training conditions. We have updated Appendix E.2 to include these results.

---

Given the simplicity of the modification do the same results appear in harder benchmarks like CIFAR-10/CIFAR-100

R: We have also extended our experiments to a subset of CIFAR-10, specifically using two classes: airplane and automobile. Gaussian noise was added to a portion of the images, following a similar setup as the MNIST experiments.

The results indicate label noise GD consistently outperformed standard GD, demonstrating its robustness even in more challenging CIFAR-10 dataset. We believe that these extended experiments help establish the broader applicability of our findings to more complex benchmarks.

We have updated Appendix E.2 to include these results.

---

Do your results hold for q≥2 or is the choice of squared ReLU specifically necessary

R: Our theoretical results regarding label noise GD hold for $q=2$, which is the minimal value for which both the signal and noise exhibit exponential growth. This makes a particularly interesting and challenging case to analyze, as it allows us to study the interaction between signal and noise in a setting that closely resembles practical two-layer ReLU networks.

We conducted additional experiments with $q=3$ and $q=4$. In both cases, the experimental results consistently show that using a higher polynomial ReLU activation helps label noise GD suppress noise memorization while enhancing signal learning, ultimately leading to improved test accuracy compared to standard GD. These findings suggest that the benefits of label noise GD generalize well to higher-order polynomial ReLU activations. We believe our current theoretical analysis can be extended to higher higher-order polynomial ReLU activations.

We have updated Appendix E.4 to include the experimental results for $q=3$ and $q=4$.

We thank the reviewer for the thoughtful comment and constructive feedback. We address the technical concerns below.

---

W1 Clarify if the different time thresholds for GD and LNGD are directly comparable, and if not, explain why; Provide a more detailed comparison of how GD and LNGD perform when run for the same number of iterations; Analyze or discuss how the performance of both algorithms changes as the number of iterations varies.

R1: 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 LNGD 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.

However, to facilitate a meaningful comparison, we have derived a ratio between the time thresholds under Assumption 4.1. By setting $m^2 = \log(6/(\sigma_0 \\| \boldsymbol{\mu} \\|_2))/\epsilon$. we can obtain the ratio between the time thresholds as follows:

$\frac{n \\| \boldsymbol{\mu} \\|^2_2}{ \sigma^2_p d} = n \mathrm{SNR}^2$

According to Assumption 4.1, we assume that $n \mathrm{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.

Regarding performance as the number of iterations varies:

• For standard GD, the 0-1 test loss does not vary significantly with the number of iterations; the main focus is on training loss convergence, which requires sufficient iterations.
• For LNGD, it is the opposite: the training loss does not vary significantly with the number of iterations, while the 0-1 test loss benefits from increased training iterations as the label noise regularizes and prevents overfitting.

---

W2 How does LNGD perform under different forms of noise? I am concerned that LNGD might only be effective in specific noise regimes. The authors should provide empirical or theoretical evidence to address this concern.

R2. To validate the robustness of label noise GD under different noise forms, we varied $p$ across different values. For example, we show the results for $p = 0.3$ in Figure 5 and $p = 0.4$ in Figure 6. 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 $\epsilon^{(t)}_i \sim \mathcal{N}(1,1)$ and $\epsilon^{(t)}_i \sim \mathcal{N}(0.6,1)$, with the results shown in Figures 7 and 8, respectively. Furthermore, for the uniform distribution, we simulated the noise with $\epsilon^{(t)}_i \sim \mathrm{unif}[-1, 2]$ and $\epsilon^{(t)}_i \sim \mathrm{unif}[-2, 3]$. The results are shown in Figures 9 and 10, respectively.

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. We update the corresponding results in Appendix E.3.

---

W3 For larger values of m, it appears that reaching the generalizable region as per Theorem 3.2 becomes slower. Could the authors offer insights into this phenomenon?

R3 The parameter $m$ represents the number of neurons in the hidden layer. In our analysis, we utilize $F_{j}= \frac{1}{m} \sum\_{r = 1}^m \sum\_{p = 1}^2 \sigma ( \langle w\_{j,r}, x^{(p)} \rangle )$ for output function, and similarly, $\gamma^{(t+1)}\_{j,r} = \gamma\_{j,r}^{(t)} - \frac{\eta}{nm} \sum_{i=1}^n \ell_i \sigma'(\langle w_{j,r}^{(t)}, y_i \mu \rangle) \| \mu\|^{2}_2 \epsilon_i^{(t)}$ for signal learning. Here $1/m$ is the scaling factor.

As the network is trained, different neurons converge at different rates. The training process often exhibits an "exponential separation" effect, where the neuron with the fastest convergence rate can significantly outpace the others. Importantly, while the convergence rate of the fastest neuron remains relatively stable, the overall outcome is effectively averaged across all m neurons, resulting in an average impact of approximately $\max_r\gamma^{(t)}_{r}/m$.

As $m$ increases, the contribution of each individual neuron becomes smaller, which means that the network as a whole requires more time to achieve similar overall performance.

We thank the reviewer for the thoughtful comment and constructive feedback. We address the technical concerns below.

---

W1: Practical Applications: While the theoretical analysis and synthetic experiments are thorough, adding experiments on more complicated simulations or real-world datasets would significantly strengthen the practical relevance of the findings.

R1 Thank you for your suggestion regarding the practical applications of our work. To address this, we have conducted two additional experiments to extend our findings to more complex simulations and real-world datasets. First, we conducted additional experiments using a 3-layer neural network with ReLU activation. Specifically, we fixed the last layer and trained the first two layers. The experimental results are consistent with our original findings: compared to standard GD, label noise GD boosts signal learning (as shown in the first plot) and achieves better generalization (as shown in the last plot). We have updated our manuscript to include this new result, with more details provided in Appendix E.1. We hope that this extension will address your concerns about the practical implications of our work.

Second, We conducted an experiment using the MNIST dataset, in which Gaussian noise was added to the borders of the images while retaining the digits in the middle. The noise level was set to $\sigma_p = 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 a "signal patch." We focused on the digits '0' and '1', using $n = 100$ samples for training and 200 samples for testing. The learning rate was set to $\eta = 0.001$, and the width was set to $m=20$, with a label noise level of $p = 0.15$. The results, shown in Figure 4, were consistent with our theoretical conclusions, reinforcing the insights derived from our analysis. We show the corresponding result in Appendix E.2.

These additional experiments help demonstrate the practical applicability of our approach and provide further validation of our theoretical findings.

---

Q1: Data Generating Process Complexity: The current data generating process appears to be relatively simple, which may limit the generalizability of the results. I suggest exploring more complex data generation functions, such as staircase functions and parity functions, to test the robustness of the proposed method in capturing more intricate relationships.

A1: Although we focus on simplified data setting, they successfully capture the primary factors necessary to quantitatively distinguish the training dynamics and generaliztion of both standard GD and label noise GD. Furthermore, we believe the data model setup is suitable for theoretical studies, given the non-linear, two layer structure and the non-convex nature of neural network optimization.

We agree that exploring more complex data models, such as staircase functions and parity functions, may provide additional insights into the robustness of the proposed method in capturing more intricate relationships. This is indeed an interesting direction, and we plan to explore these more complex data models in future work.

We thank the reviewer for the thoughtful comment and constructive feedback. We address the technical concerns below.

---

W1 & Q1: Concern with the big-O notation. Appreciate a simplified version of Assumption 3.1 and Theorems 3.1 and 3.2 (even if it is less general).

R1: Thank you for the suggestion; we have revised the manuscript to enhance the clarity of our presentation. We believe that the big-O notations are appropriate for our purposes as they enhance clarity while maintaining mathematical rigor, as these notations are commonly used to concisely describe asymptotic relationships without explicitly stating all constants, which keeps the presentation clean and focused on key insights. This approach follows from recent works on gradient-based feature learning, such as Cao et al. 2022, Jelassi et al. 2022, Chen et al. 2023, Frei et al. 2023, Allen-Zhu et al. 2023. We make the following clarifications.

---

• Simplified Version of Assumption 3.1:

To improve clarity, we provide a simplified version of Assumption 3.1 below:

Given a failure probability $\delta \in (0,0.5)$,with a large enough universal constant $C$ we make the following assumptions on the parameters:

• data dimension $d \ge C \log(n/\delta) \max \\{ n^2, n \\| \boldsymbol{\mu} \\|^2_2/\sigma^2_p \\}$

• network width $m \ge C\log(d/\delta)$

• number of training samples $n \ge C\log(d/\delta)$.

• learning rate $\eta \le 1/(C\log(d/\delta)) \sigma^{-2}_p d^{-1}$.

• initialization variance $C\log(d/\delta) n \sigma^{-1}_p d^{-3/4} \le \sigma_0 \le 1/(C\log(d/\delta)) \min \\{ \\| \boldsymbol{\mu} \\|^{-1}_2 d^{-5/8}, \sigma^{-1}_p d^{-1/2} \\}$.

• flipping rate of label noise $0 < p < 1/C$

---

• Assumption 3.1 says n is Omega(1) but d is Omega(n^2). I am not sure how that is possible

We would like to clarify that this requirement does not imply a contradiction. Specifically, the relation can be understood as: $d \ge n^2 \log(n) \ge C \mathrm{poly}(\log(d))$ Note that similar constraints also appeared in Cao et al. 2022,Chen et al. 2023,Kou et al. 2023.

---

• Theorem 3.2 has some constants C1 and C2 inside the Theta notation

Thank you for pointing this out. In the revision we have removed these constants from the Θ notation

---

• Appreciate a simplified version of Assumption 3.1 and Theorems 3.1 and 3.2

To verify the consistency of the conditions in Assumption 3.1, we provide a concrete choice of hyperparameters: $\sigma_0 = d^{-11/16}, \eta< d^{-1}, \\| \boldsymbol{\mu} \\|_2 = d^{-1/3}$, $\sigma_p = C$, $n = d^{1/3}$, here $C$ is a constant. In this case, the constant does not need to be specified as d is sufficiently large.

---

• like 2 and pi and not problem dependent constants like d,n, m etc

We would like to clarify that certain parameters, such as $m$ and $n$, cannot be treated as constants. In our analysis, $m$ and $n$ need to be at least polylogarithmic in the dimension $d$, as indicated by the use of the \tilde{} notation to hide polylogarithmic terms.

---

W2: The two main results are Theorems 3.1 and 3.2. But Theorem 3.1 proves the same result as Cao et al. for q=2 while they prove for q>2. This is not a significant extra contribution.

R2: First we note that the case where $q=2$ is not a straightforward extension of previous results for higher-order homogeneity. As remarked in Section 2, the choice of squared ReLU activation is motivated by the fact that we do not optimize the second-layer parameters. We aim for the 2-homogeneous squared ReLU activation to mimic the behavior of training both layers simultaneously in a standard ReLU network. Besides, $q=2$ is the smallest integer for which both the signal and noise exhibit exponential growth. This characteristic makes the analysis more challenging compared to $q>2$, where the gap between signal learning and noise memorization can be more easily characterized.

In addition, the purpose of presenting Theorem 3.1 is also to enable a direct comparison label noise GD and standard GD. Therefore, the significance lies not in Theorem 3.1 itself as a standalone contribution, but rather in the comparison it allows. This comparison clearly demonstrates that incorporating label noise into gradient descent updates improves generalization in the low SNR regime, which is the core contribution of our work.

W3: artificiality and extreme simplicity of the entire setup.

R3: We agree that the problem setting (signal-noise data model, network architecture, etc.) has been studied in many prior works — as explained in the Introduction, this signal-noise model has been extensively studied in the neural network theory literature, as a sandbox to understand how gradient-based training prioritizes learning of the underlying signal instead of overfitting to noise. However, to the best of our knowledge, we are the first to study label noise GD in this setup and demonstrate efficient learning and benign overfitting in the challenging low SNR regime; moreover, the analysis of label noise GD is already rather nontrivial as discussed in Section 4.3. Extending this result to more complicated data generating process and architecture is an interesting future direction.

In light of your feedback, we have also conducted additional experiments using a more complicated architecture of 3-layer neural network with ReLU activation. Specifically, we fixed the last layer and trained the first two layers. The experimental results are consistent with our original findings: compared to standard GD, label noise GD boosts signal learning (as shown in the first plot) and achieves better generalization (as shown in the last plot). We have updated our manuscript to include this new result, with more details provided in Appendix E.1.

---

Q2: The label noise fraction seems to be a crucial parameter and is not given sufficient detail in the assumptions (it is bounded by some undefined C) and in the proofs and also in the synthetic experiments. Some details on this are needed.

A2: In our theoretical analysis, the label noise fraction ($1/C$) is used as an abstraction to maintain the correctness of asymptotic analysis. This approach is consistent with other recent works in the field, such as Condition 4.1 in Kou et al. 2023, Assumption (A3) in Xu et al. 2023, Condition 3.1 in Chen et al. 2023. Specifically, there are two main sources that impose constraints on the label noise fraction:

(1) Signal Learning Coefficient: To guarantee the lower bound of the signal learning coefficient, we need to impose an upper bound on the flipping rate ($p$). This is necessary for maintaining effective learning of the signal and corresponds to Lemma D.1 and the third bullet point in Lemma 4.3.

(2) Noise Memorization Coefficient: Similarly, to guarantee the lower bound of the noise memorization coefficient during the initial phase of training, we also need to limit the flipping rate ($p$). This constraint corresponds to Lemma D.3 and the first bullet point in Lemma 4.3.

For the experimental section, we indeed used a fixed value of $p = 0.1$ for the label noise fraction. We have updated our manuscript to include this information explicitly, ensuring that the experimental details are clearly presented for reproducibility.

We thank the reviewer for the further questions. Below, we address your concerns:

---

Does the result of Cao et al. apply only to integer values of q? If it applies to real values of q>2couldn't Theorem 2.1 potentially be derived via an approximation argument, like using ReLU^{2.0001} and arguing this is close to ReLU squared?

While it is theoretically possible to use an approximation argument with $\text{ReLU}^{2.0001}$ to analyze the setup, the resulting separation condition would differ significantly from that of $\text{ReLU}^2$. Specifically, with $\text{ReLU}^{2.0001}$, the separation condition would scale as $n \cdot \text{SNR}^{2.0001}$. The ratio $\frac{n\text{SNR}^{2.0001}}{n \text{SNR}^2} \rightarrow 0$ as $n \rightarrow \infty$, given $n \text{SNR}^2 \le 1/\log(d)$.

More generally, if we consider $q = 2 + \epsilon$, letting $\epsilon \rightarrow 0$ introduces significant challenges. Specifically, in the condition of 4.2 from Cao et al. (2022), they require $\sigma_0 \le \tilde{O}(m^{-2/(q-2)}) n^{-[1/(q-2)] \lor 1}$, where $\sigma_0$ represents the initialization variance. As $\epsilon \rightarrow 0$, the term $m^{2/(q-2)}$ diverges, causing the constraint on $\sigma_0$​ to become impractical.

---

I am not sure that the new experiments in Section E1 can be called a deeper neural net, as there is only one layer which has an activation. It is more like an amalgamation of the deep linear network with the signal noise model. I understand the authors intention to show that the message could be applied to other architectures, but I am not sure this section achieves anything.

There is a typo in the previous description: the first layer in the experiment is defined as $z^{(p)} = \sigma(W^\top x^{(p)})$, where $\sigma(\cdot)$ represents the ReLU activation function. In the experiment, this transformation is indeed applied alongwith ReLU activation. We have updated the manuscript to clarify this.

---

Can the authors add a paragraph/theorem/experiments on explicit label smoothing, as opposed to the simulated label smoothing that is implemented in the algorithm here? Would that also fail similar to standard SGD? Experiments with this baseline would also be appreciated.

In this work, we focus on the label flipping flipping which has been studied both empirically and theoretically in prior works. For instance, Damian et al. 2021 where they use CIFAR-10 + ResNet with flipping label noise algorithm. Besides, Haochen et al. 2021 trained a VGG19 model on CIFAR100 with flipping noise, and found adopting flipping label noise achieves better test error compared to the baseline full-batch GD algorithm.

We have also conducted experiments on the CIFAR-10 dataset where a VGG-16 model is optimized by full-batch GD vs. label-noise GD (analogous to Figure 1 in Jelassi & Li 2022). We trained the model on 10,000 samples using both algorithms, and to isolate the effect of label noise, we disabled data augmentation and batch normalization. The learning rate was set to 0.02, and the label flipping rate was 0.2. The results are available here, where we observe a ~2% improvement in the test accuracy due to label noise, even though it is not clear if this dataset exhibits low SNR.

Lastly, we remark that label smoothing and label flipping is equivalent in expectation. In particular, label smoothing transform the original label $y_k$ to $y’_k = y_k(1-\alpha) + \alpha/2 y_k + \alpha/2 (-y_k) = (1-\alpha) y_k,$ where $\alpha$ is the smoothing parameter. On the hand, taking expectation of label flipping, the expected label is $y’_k = (1-p)y_k - p y_k = (1-2p) y_k.$
Thus, when $\alpha=2p$, label smoothing is mathematically equivalent to label flipping in expectation; this connection has been discussed in Li et al. 2020. However, we note that this equivalence in expectation does not imply closeness in the training dynamics due to the stochasticity introduced in the label flipping procedure.

We will include the above clarifications in the revised manuscript.