summaries: This paper addresses a limitation of BatchNorm: vulnerability to adversarial perturbations. The authors propose a possible explanation of this issue and correspondingly an alternative called RobustNorm to tackle this problem. Specifically, the authors observe that the statistics of BatchNorm for training and inference are different, resulting in different data distributions for training and inference. To solve this problem, the authors propose to use min-max rescaling instead of normalization. In addition, the running average is calculated with mean and the running mean of the denominator during inference. Experimental results show significant improvement of robustness and also comparable accuracy for clean data.

summaries: Review: This paper investigates the reason behind the vulnerability of BatchNorm and proposes a Robust Normalization. They experimentally show that it is the moving averages of mini-batch means and variances (tracking) used in Normalization that cause the adversarial vulnerability. Based on this observation, they propose a new normalization method not only achieves significantly better results under a variety of attack methods but ensures a comparable test accuracy to that of BatchNorm on unperturbed datasets. The paper is clearly written, easy to read.

summaries: This paper proposes an interesting perspective that BatchNorm may introduce the adversarial vulnerability, and probes why BatchNorm performs like that (the tracking part in BatchNorm). In experiment, the robustness of the networks increases by 20% when removing the tracking part, but the test accuracy on the clean images drops a lot. Afterwards, the authors propose RobustNorm, which performs better than BatchNorm for both natural and adversarial scenarios.

abstractText: Batch Normalization (BatchNorm) has shown to be effective for improving and accelerating the training of deep neural networks. However, recently it has been shown that it is also vulnerable to adversarial perturbations. In this work, we aim to investigate the cause of adversarial vulnerability of the BatchNorm. We hypothesize that the use of different normalization statistics during training and inference (mini-batch statistics for training and moving average of these values at inference) is the main cause of this adversarial vulnerability in the BatchNorm layer. We empirically proved this by experiments on various neural network architectures and datasets. Furthermore, we introduce Robust Normalization (RobustNorm) and experimentally show that it is not only resilient to adversarial perturbation but also inherit the benefits of BatchNorm.

authors:
Devansh Arpit
Yingbo Zhou
Bhargava U Kota
Venu Govindaraju

title: Normalization propagation: A parametric technique for removing internal covariate shift in deep networks

venue: arXiv preprint arXiv:1603.01431,

authors:
Nils Bjorck
Carla P Gomes
Bart Selman
Kilian Q Weinberger

title: Understanding batch normalization

venue: In Advances in Neural Information Processing Systems,

authors:
Nicholas Carlini
David Wagner

title: Towards evaluating the robustness of neural networks

venue: IEEE Symposium on Security and Privacy (SP),

authors:
Gavin Weiguang Ding
Kry Yik Chau Lui
Xiaomeng Jin
Luyu Wang
Ruitong Huang

title: On the sensitivity of adversarial robustness to input data

authors:
Laurent Dinh
Razvan Pascanu
Samy Bengio
Yoshua Bengio

title: Sharp minima can generalize for deep nets

venue: In Proceedings of the 34th International Conference on Machine Learning-Volume

authors:
Christian Etmann
Sebastian Lunz
Peter Maass
Carola-Bibiane Schönlieb

title: On the connection between adversarial robustness and saliency map interpretability

authors:
Angus Galloway
Anna Golubeva
Thomas Tanay
Medhat Moussa
Graham W Taylor

title: Batch normalization is a cause of adversarial vulnerability

authors:
Ian J Goodfellow
Jonathon Shlens
Christian Szegedy

title: Explaining and harnessing adversarial examples

venue: arXiv preprint arXiv:1412.6572,

title: Deep residual learning for image recognition

title: Batch renormalization: Towards reducing minibatch dependence in batch-normalized models

venue: In Advances in neural information processing systems,

authors:
Sergey Ioffe
Christian Szegedy

title: Batch normalization: Accelerating deep network training by reducing internal covariate shift

venue: arXiv preprint arXiv:1502.03167,

authors:
J”orn-Henrik Jacobsen
Jens Behrmann
Richard Zemel
Matthias Bethge

title: Excessive invariance causes adversarial vulnerability

venue: arXiv preprint arXiv:1811.00401,

authors:
Jörn-Henrik Jacobsen
Jens Behrmannn
Nicholas Carlini
Florian Tramer
Nicolas Papernot

title: Exploiting excessive invariance caused by norm-bounded adversarial robustness

authors:
Nitish Shirish Keskar
Dheevatsa Mudigere
Jorge Nocedal
Mikhail Smelyanskiy
Ping Tak Peter Tang

title: On large-batch training for deep learning: Generalization gap and sharp minima

venue: arXiv preprint arXiv:1609.04836,

title: Learning multiple layers of features from tiny images

venue: Technical report, Citeseer,

authors:
Alexey Kurakin
Ian Goodfellow
Samy Bengio

title: Adversarial machine learning at scale

venue: arXiv preprint arXiv:1611.01236,

authors:
Hao Li
Zheng Xu
Gavin Taylor
Christoph Studer
Tom Goldstein

title: Visualizing the loss landscape of neural nets

authors:
Xiang Li
Shuo Chen
Xiaolin Hu
Jian Yang

title: Understanding the disharmony between dropout and batch normalization by variance shift

venue: arXiv preprint arXiv:1801.05134,

authors:
Ping Luo
Xinjiang Wang
Wenqi Shao
Zhanglin Peng

title: Towards understanding regularization in batch normalization

authors:
Aleksander Madry
Aleksandar Makelov
Ludwig Schmidt
Dimitris Tsipras
Adrian Vladu

title: Towards deep learning models resistant to adversarial attacks

venue: arXiv preprint arXiv:1706.06083,

authors:
Anh Nguyen
Jason Yosinski
Jeff Clune

title: Deep neural networks are easily fooled: High confidence predictions for unrecognizable images

authors:
Nicolas Papernot
Patrick McDaniel
Xi Wu
Somesh Jha
Ananthram Swami

title: Distillation as a defense to adversarial perturbations against deep neural networks

venue: In 2016 IEEE Symposium on Security and Privacy (SP),

title: Sur les équations algébriques ayant toutes leurs racines réelles

venue: Mathematica, 9:129–145,

authors:
Tim Salimans
Durk P Kingma

title: Weight normalization: A simple reparameterization to accelerate training of deep neural networks

authors:
Shibani Santurkar
Dimitris Tsipras
Andrew Ilyas
Aleksander Madry

title: How does batch normalization help optimization

authors:
Carl-Johann Simon-Gabriel
Yann Ollivier
Léon Bottou
Bernhard Schölkopf
David Lopez-Paz

title: Adversarial vulnerability of neural networks increases with input dimension

venue: arXiv preprint arXiv:1802.01421,

authors:
Karen Simonyan
Andrew Zisserman

title: Very deep convolutional networks for large-scale image recognition

venue: arXiv preprint arXiv:1409.1556,

authors:
Florian Tramèr
Alexey Kurakin
Nicolas Papernot
Ian Goodfellow
Dan Boneh
Patrick McDaniel

title: Ensemble adversarial training: Attacks and defenses

venue: arXiv preprint arXiv:1705.07204,

authors:
Cihang Xie
Yuxin Wu
Laurens van der Maaten
Alan L Yuille
Kaiming He

title: Feature denoising for

venue: Vision (ECCV),

heading: 1 INTRODUCTION

text:
In spite of their impressive performance on challenging tasks in computer vision such as image classification and semantic segmentation, deep neural networks (DNNs) are shown to be highly vulnerable to adversarial examples, i.e. carefully crafted samples which look similar to natural images but designed to mislead a trained neural network model (Goodfellow et al., 2014; Nguyen et al., 2015; Carlini & Wagner, 2017). Designing defense mechanisms against these adversarial perturbations has been subjected to much research recently (Xie et al., 2019; Madry et al., 2017; Tramèr et al., 2017; Papernot et al., 2016).
Meanwhile, Batch Normalization (BatchNorm or BN) (Ioffe & Szegedy, 2015) has successfully proliferated throughout all areas of deep learning as it enables stable training, higher learning rates, faster convergence, and higher generalization accuracy. Initially, the effectiveness of the BatchNorm has been attributed to its ability to eliminate the internal covariate shift (ICS), the tendency of the distribution of activations to drift during training. However, later on, alternative reasons including avoiding exploding activations, smooth loss landscape, reducing the sensitivity to initialization, etc. have also been proposed as the basis of BatchNorm’s success (Santurkar et al., 2018; Bjorck et al., 2018; Luo et al., 2018).
While there exist a plethora of reasons for the adversarial vulnerability of deep neural networks (Jacobsen et al., 2018; Simon-Gabriel et al., 2018), a recent study by Galloway et al. (2019) showed that BatchNorm is one of the reasons for this vulnerability. Specifically, they empirically showed that removing the BatchNorm layer enhances robustness against adversarial perturbations. However, removal of BatchNorm also means a sacrifice of benefits such as the use of higher learning rates, faster convergence, and significant improvement in the clean test set accuracy among many others.
In this paper, we propose a new perspective regarding the adversarial vulnerability of the BatchNorm layer. Specifically, we probe why BatchNorm layer causes the adversarial vulnerability. We hypothesize that the use of different normalization statistics during training and inference phase (mini-batch statistics for training and moving average of these statistics also called tracking, at inference time) is the cause of this adversarial
vulnerability of the BatchNorm layer. Our experiments show that by removing this part of the BatchNorm, the robustness of the network increases by 20%. Similarly, robustness can further be enhanced by up to 30% after adversarial training. However, by removing the tracking part, the test accuracy on the clean images drops significantly ( though better than without normalization). To circumvent this issue, we propose Robust Normalization (RobustNorm or RN). Our experiments demonstrate that RobustNorm not only significantly improve the test performance of adversarially-trained DNNs but is also able to achieve the comparable test accuracy to that of BatchNorm on unperturbed datasets. We perform numerical experiments over standard datasets and DNN architectures. In almost all of our experiments, we obtain a better adversarial robustness performance on perturbed examples for training with natural as well as adversarial training.

heading: 2 BACKGROUND

text:
We consider a standard classification task for data, having underlying distribution denoted as D, over the pair of examples x ∈ Rn and corresponding true labels y ∈ {1, 2, ..., k} where k represents different labels. We denote deep neural network (DNN) as a function Fθ(x), where θ denotes trainable parameters. θ is learned by minimizing a loss function L(x, y) with training data x, y. The output of the DNN is a feature representation f ∈ Rd, that we give input to a classifier C : Rn → {1, 2, ..., k}. The objective of the adversary is to add the additive perturbation δ ∈ Rn under the constrain that the generated adversarial sample xadv = x+ δ that looks visually similar to the true image x, and for which the corresponding labels are not same i.e. C(x) 6= C(xadv). In this work, we have added the perturbation via following well-known adversarial attack approaches.
Fast Gradient Sign Method: Given an input image x along with its corresponding true label y, FGSM Goodfellow et al. (2014) aims to generate the adversarial image xadv as,
xadv = x+ · sign(∇xL(x, y), (1) where is the perturbation budget that is chosen to be sufficiently small. We use two of its variants: Gradient (Grad) where graidents are used and Gradient sign (GradSign) which is similar to 1.
Basic Iterative Method (BIM): BIM (Kurakin et al., 2016) is a straight forward extension of FGSM, that applies it multiple times with a smaller step size. Specifically,
x0adv = x, x N adv = Clipx, {x N−1 adv + α · sign(∇xL(x N−1 adv , y))} (2)
where x0adv is the clean image and N denotes iteration number.
Carlini-Wagner attack (CW): CW is an effective optimization-based attack model introduced by Carlini & Wagner (2017). It works by definining an auxilary variable ϑ and minimizes the following objective functions
min ϑ ‖1 2 (tanh(ϑ) + 1)− x‖+ c.f(1 2 (tanh(ϑ) + 1)), (3)
where 12 (tanh(ϑ) + 1)− x is the perturbation δ, c is a scalar constant, and f(.) is defined as:
f(xadv) = max(Z(xadv)y −max{Z(xadv)k : k 6= y},−%)). (4)
Here, % is to control the adversarial sample’s confidence and Zxadv are the logits values for class k. Projected Gradient Descent (PGD): PGD perturbs the true image x for total number of N steps with smaller step sizes. After each step of perturbation, PGD projects the adversarial example back onto the -ball of normal image x , if it goes beyond the -ball. Specifically,
xNadv = Π(x N−1 adv + α.sign(∇xL(x N−1 adv , y))), (5)
where Π is the projection operator, α is step size, and xN denotes adversarial example at the N -th step. We have used `∞ norm as a distance measure. Gaussian Noise For comparison purposes, we also have used Gaussian noise with 0 mean and 0.25 variance.
2.0.1 ADVERSARIAL TRAINING:
It has been shown that empirical risk minimization using only clean images for training can decrease the robustness performance of DNNs. A standard approach to achieve the adversarial robustness in DNNs is adversarial training which involves fitting a classifier C on adversarially-perturbed samples along with clean images. We have used PGD based adversarial training which has shown to be effective against many firstorder adversaries (Madry et al., 2017) unlike other methods which overfit for on a single attack.

heading: 2.1 EXPERIMENTAL SETUP

text: We have used two network architectures, Resnet He et al. (2016) with 20,38 and 50 layers and VGG Simonyan & Zisserman (2014) with 11 and 16 layers. We have used CIFAR10 and 100 datasets (Krizhevsky et al., 2009) for all the evaluations. We have used term natural training for training with clean images while adversarial training is done with PGD based method formulated by Madry et al. (2017). We have always used a learning rate of 0.1 except for no normalization scenarios where convergence is not possible with higher learning rates. In such cases, we have used a learning rate of 0.001. We decrease the learning rate 10 times after 120 epochs and trained all the networks for 164 epochs. For robustness evaluations, we have used =0.03/1 for most of the experiments and used 20 epochs for all the iterative attacks. We also have tested the model on different noise levels ranging from 0.003/1 to 0.9/1.

heading: 3 HOW DOES BATCHNORM CAUSES ADVERSARIAL VULNERABILITY

heading: 3.1 HOW BATCHNORM WORKS

text:
In this section, we briefly explain the working principle of BatchNorm layer. Broadly speaking, the BatchNorm layer has been introduced to circumvent the issue of internal covariate shift (ICS). Consider a minibatch B of size M , containing samples xm for m = 1, 2, ...,M . BatchNorm normalizes the mini-batch during training, by calculating the mean µβ and variance σ2β as follows:
µB = 1
M M∑ i=1 xi ; σB = √√√√ 1 M M∑ i=1 (xi − µB)2 + . (6)
Activation normalization is then performed as,
x̂i = xi − µB σB . (7)
To further compensate for the possible loss of representational ability of network, BatchNorm also learns per-channel linear transformation as: yi = γx̂i + B, (8) for trainable parameters γ and β that represent scale and shift, respectively. These parameters are learnt using the same procedure, such as stochastic gradient descent, as other weights in the network. During training, the model usually maintains the moving averages of mini-batch means and variances(a.k.a. tracking), and during inference, uses these tracked statistics in place of the mini-batch statistics. Formally, tracking (moving average) of mean and variance, for scalar τ are given as,
µ̂ = (1− τ)µ̂+ τµβ , σ̂2 = (1− τ)σ̂2 + τσ2B (9) For inference, we can write,
ytest = xtest − µ̂
σ̂ .γ + β. (10)

heading: 3.2 BATCHNORM AND ADVERSARIAL VULNERABILITY

text: Recently, Galloway et al. (2019) empirically showed that the accelerated training properties and occasionally higher clean test accuracy of employing BatchNorm in network come at the cost of low robustness to adversarial perturbations. While removing the BatchNorm layer may be helpful for robustness, it also means the loss of desirable properties of BatchNorm like very high learning rate, faster convergence, boost in test accuracy, etc. Therefore, it is pertinent to devise a normalization method that is not only robust to the adversarial perturbations but also inherits the desirable properties of the BatchNorm layer.

heading: 3.3 DEVIL IS IN THE TRACKING

text:
In this section, we aim to investigate the reasons behind the adversarial vulnerability of the BatchNorm layer on the following two grounds;
• We note that during training, mini-batch statistics are used to normalize activations as shown in Equations 6 and 7. Moving average of these statistics are also calculated during the training that is called tracking (shown in Equation 9). The tracked mean and variance are used in the inference step (Equation 10). In this way, different values for mean and variance are used during training and inference. We show this in Figure 1 where it is clear that batch statistics at the start of the training are very different from tracked values that are used at the inference.
• Our second observation is based on the recent work of (Ding et al., 2019; Jacobsen et al., 2019). These works shed light on the link of the distributional shift in input data and robustness. Specifically, Ding et al. (2019) showed that adversarial robustness is highly sensitive to change in the input data distribution and prove that even a semantically-lossless shift on the data distribution could result in drastically different robustness for adversarially trained models.
Based on the above two observations, we hypothesize that: Different values of first-order statistics (mean and variance) are used in the normalization layer for training and inference. This means different internal
representations being used at training and inference time which causes drift in input distributions of these layers. Therefore, the tracking part is the main culprit behind the adversarial vulnerability of the BatchNorm layer.
To prove our hypothesis, we have done extensive experiments. For each experiment, we train a neural network model with three different normalization layers: BatchNorm, BatchNorm without tracking, and no normalization. To prove the generality of our argument, we have used various architectures, depths, and datasets as written in section 2.1. We train these networks on clean images as well as with based adversarial training procedure. For adversarial training, we use PGD attack for perturbation. We choose PGD due to its ability to generalize well for other adversarial attacks.
Table 1 shows our results on Resnet20. For detailed experimental results on various architectures, depths and dataset with different attacks see Table 4, 5 in appendix. The results clearly show that while the elimination of BatchNorm and training at a very small learning rate can help increase robustness, it also reduces clean data accuracy (with BatchNorm). More importantly, this proves our hypothesis that by removing tracking, we can increase the robustness of a neural network significantly. By using BatchNorm without tracking, we also keep many benefits of BatchNorm. Unfortunately, by eliminating the tracking part of BatchNorm, clean accuracy of a network also reduces as compared to clean accuracy with BatchNorm. We tackle this issue in the next section.

heading: 4 ROBUST NORMALIZATION

text:
Although alleviation of ICS was claimed reason for the success of BatchNorm, recently, Bjorck et al. (2018) have shown that BatchNorm works because it avoids activation explosion by repeatedly correcting all activations. For this reason, it is possible to train networks with large learning rates, as activations cannot grow uncontrollably and convergence becomes easier. On a different side, recent work on robustness has shown a connection between the removal of outliers in activations and robustness (Xie et al., 2019; Etmann et al., 2019). Based on these observations, we use min-max rescaling that is often employed in preprocessing. This is also useful in the elimination of outliers since it rescales the data to a specific scale, Minmax normalization is defined as;
yi = xi −min(xi)
max(xi)−min(xi) . (11)
However, we experimentally found this layer to be less effective in terms of convergence. Considering the importance of mean (Salimans & Kingma, 2016), we modify this to;
yi = xi − µ
max(xi)−min(xi) . (12)
We empirically observe the effectiveness of Equation 12 over Equation 11 but the overall performance was still inadequate. During debugging, we found that Equation 12 suppress activations much stronger than BatchNorm. This can also be seen from Popoviciu’s inequality (Popoviciu, 1935),
4σ2 ≤ (max(xi)−min(xi))2. (13)
Following Popoviciu’s inequality, we introduce the hyperparameter 0 < p < 1, that reduces the denominator in Equation 12,
yi = xi − µ
(max(xi)−min(xi))p (14)
We experimentally found that p = 0.2 value generalizes well for many networks as well as datasets. We call this normalization Robust Normalization (RobustNorm or RN) due to its robustness properties. We do not use tracking for the RobustNorm. But for comparison purposes, we keep running average of both mean and denominator and use this running average during inference and call this normalization RobustNorm with tracking.
Table 3 shows the accuracy of RobustNorm on Resnet20 for clean as well as adversarial training with both CIFAR10 and CIFAR100 datasets with 95% confidence interval calculated over 5 random restarts. These results show a better clean accuracy of RobustNorm in both natural and adversarial training scenarios. Apart from this, RobustNorm with tracking also shows better performance compared to BatchNorm with tracking. For adversarial robustness, we have shown Figure 2 with different attacks on CIFAR100 dataset. From the Table 3 and Figure 2, it is clear that RobustNorm keeps its clean accuracy while being more robust. For more results on Resnet38, Resnet50, VGG11, and VGG16 with CIFRAR10 and CIFAR100 datasets and both natural and adversarial training and many attack methods, please have a look at Table 4 and 5.
Figure3 shows the evolution of validation loss and accuracy for PGD based adversarial training with a confidence interval of 95% on Resnet20 architecture and CIFAR100 dataset. From Figure 8 in the appendix, it can also be seen that the evolution of training loss and accuracy is normal. But validation loss and accuracy for normalizations with tracking is much different for different random restarts. This can probably be explained based on flat and sharp minima attained by different normalizations as can be seen in loss landscape in Figure 9 in the appendix. For further discussion on the loss landscape, please see section B in appendix.

heading: 4.1 RESISTANCE FOR DIFFERENT VALUES OF ADVERSARIAL PERTURBNESS

text: To further understand the performance of RobustNorm under adversarial conditions, we run an experiment where values are increased for the test set. We train networks with BatchNorm, BatchNorm w/o Tracking and RobustNorm with Natural as well as PGD-`∞ based adversarial training and tested them on different values of . The results are shown in Figure 4. As increases, the robustness of neural network decreases but the robustness of neural network with RobustNorm is much higher than BatchNorm while also higher than BatchNorm w/o tracking. To see the effect of an increase in adversarial noise on CIFAR100 dataset, see Figure 6 in the appendix.

heading: 5 IS TRACKING A NECESSARY EVIL?

text:
In the previous sections, we have empirically shown the wickedness of tracking in BatchNorm. But there is more to the story. One benefit of tracking that makes it a necessary evil in BatchNorm is its ability to have
consistent results on small inference time batch sizes. For all the results mentioned in this paper, we have used 100 as inference time batch size. By removing tracking, we lose this ability as shown in Figure 5. Does this make tracking a necessary evil? Based on the observations in section 3, one straight forward solution to this problem could be the use of tracked values during training as well since it will change the issue of different distributions. This, however, causes the model to blow up as argued by Ioffe & Szegedy (2015); Ioffe (2017). To resolve this issue, one possible solution is Batch Renormalization like formulation (Ioffe, 2017) but it requires careful tuning of many hyperparameters which makes its use very difficult. Similarly, other possible solutions such as Arpit et al. (2016); Salimans & Kingma (2016); Wu & He (2018) have their own challenges as well. From these observations, we argue that this problem requires more investigation.
It is also important to note that RobustNorm’s results are restored by increasing batch size by a small number. Similarly, tracking is also less harmful for RobustNorm and RobustNorm with tracking is still more robust while having all the benefits of BatchNorm.

heading: 6 CONCLUSION

text: Addition of maliciously crafted noise in normal inputs, also called adversarial examples has proven to be deceptive for neural networks. While there are many reasons for this phenomena, recent work has shown BatchNorm to be a cause of this vulnerability as well. In this paper, we have investigated the reasons behind this issue and found that tracking part of BatchNorm causes this adversarial vulnerability. Then, we showed that by eliminating it, we can increase the robustness of a neural network. Afterward, based on the intuitions from the work done for the understanding of BatchNorm, we proposed RobustNorm which has much higher robustness than BatchNorm for both natural as well as adversarial training scenarios. In the end, we have shown how tracking can be a necessary evil and argued that it requires further careful investigation.

heading: A ROBUSTNORM

text:
A.1 ROBUSTNORM FOR OTHER ARCHITECTURES
In this section, we provide more detailed results for our experiments for both CIFAR10 and CIFAR100 datasets. Table 4 and 5 shows detailed results.
A.2 RESISTANCE TO INCREASE IN ADVERSARIAL NOISE
In this section, we put results of increasing adversarial noise on CIFAR100 dataset.
A.3 ANOTHER ASPECT OF ROBUSTNORM
As we have discussed, ICS hypothesis has been negated by a few recent studies. One of these studies (Santurkar et al., 2018) suggested that based on the results, “ it might be valuable to perform a principled exploration of the design space of normalization schemes as it can lead to better performance.” In this way, we can see RobustNorm with tracking as a new normalization scheme which is based on alternative explanations yet having performance equal to BatchNorm which, in a way, weakens ICS hypothesis. See Figure 7 for a comparison of accuracies over different models for CIFAR10 and CIFAR100 datasets.

heading: B LOSS LANDSCAPE

text:
In this section, we discuss possible reasons for the high variation of validation loss for a network with normalization with tracking. As shown in Figure 8, training loss of all the norms converges with similar
fashion for all the random restarts but validation loss has a lot of variation over these restarts. In other words, the value of training loss is similar among many restarts while the same loss values change drastically for validation. To further understand it, we draw loss landscape of these networks using formulation given by Li et al. (2018b) in Figure 9. From these plots, we observe an interesting behaviour: networks having normalization without tracking(i.e. better robustness) tend to have sharp minima as can be seen in figures 9c, 9d, 9e, 9f while their counterparts have more flat loss landscape i.e. figures 9a, 9b, 9g, 9h. There is a long history of debate on generalization ability of sharp vs flat minima Hochreiter & Schmidhuber (1997); Keskar et al. (2016); Dinh et al. (2017). We think more work in this direction can lead to a better understanding of how BatchNorm causes this vulnerability.

heading: C MORE EXPERIMENTS ON ROBUSTNORM

text:
In this section, we discuss some less interesting experiments done to understand the role of power in RobustNorm.
C.1 EFFECT OF POWER ON ROBUSTNORM
In this section, we show the effect of changing hyperparameter p for clean as well as robust accuracy. From figure 4 and 11, it can be seen that both robustness to many attacks as well as accuracy changing with the power. So it can be concluded that by tuning hyperparameters, we can get better results.


summaries: This paper proposes two regularization methods for learning on noisily labeled data: the first penalizes the distance w.r.t. Euclidean norm from an initial point and the second uses an additional auxiliary variable for each example to learn a noise. In the theoretical part, the paper shows that an original clean dataset can be learned from a noisily labeled dataset based on NTK-theory. Finally, the effectiveness of proposed regularization methods is well verified empirically for 2-layer NN, CNN, and ResNet on image classification tasks (MNIST, CIFAR-10).

summaries: This paper studies the topic of learning with noisy labels, in particular, classification problem where the labels are randomly flipped with some probability. The main technical contributions of this paper are two folds: 1) proof of generalization bounds for kernel ridge regression solutions that depends on the clean labels only. 2) two regularization techniques that are shown to be equivalent to the kernel ridge regression when the neural networks approach the neural tangent kernel regime.

summaries: In this paper, based on the effectiveness of early stopping in the training of noisily labeled samples, the authors proposed two intuitive (and novel) regularization methods: (1) regularizing using distance to initialization (2) adding an auxiliary variable b_i for every input x_i during training. In terms of theory, the authors showed that in the NTK regime, both regularization methods trained with gradient descent are equivalent to kernel ridge regression.  Moreover, the authors also provided a generalization bound of the solution on the clean data distribution when trained with noisy label, which was not addressed in previous research.

abstractText: Over-parameterized deep neural networks trained by simple first-order methods are known to be able to fit any labeling of data. Such over-fitting ability hinders generalization when mislabeled training examples are present. On the other hand, simple regularization methods like early-stopping can often achieve highly nontrivial performance on clean test data in these scenarios, a phenomenon not theoretically understood. This paper proposes and analyzes two simple and intuitive regularization methods: (i) regularization by the distance between the network parameters to initialization, and (ii) adding a trainable auxiliary variable to the network output for each training example. Theoretically, we prove that gradient descent training with either of these two methods leads to a generalization guarantee on the clean data distribution despite being trained using noisy labels. Our generalization analysis relies on the connection between wide neural network and neural tangent kernel (NTK). The generalization bound is independent of the network size, and is comparable to the bound one can get when there is no label noise. Experimental results verify the effectiveness of these methods on noisily labeled datasets.

authors:
Zeyuan Allen-Zhu
Yuanzhi Li
Yingyu Liang

title: Learning and generalization in overparameterized neural networks, going beyond two layers

venue: arXiv preprint arXiv:1811.04918,

authors:
Zeyuan Allen-Zhu
Yuanzhi Li
Zhao Song

title: A convergence theory for deep learning via overparameterization

venue: arXiv preprint arXiv:1811.03962,

authors:
Sanjeev Arora
Simon S Du
Wei Hu
Zhiyuan Li
Ruslan Salakhutdinov
Ruosong Wang

title: On exact computation with an infinitely wide neural net

venue: arXiv preprint arXiv:1904.11955,

authors:
Sanjeev Arora
Simon S Du
Wei Hu
Zhiyuan Li
Ruosong Wang

title: Fine-grained analysis of optimization and generalization for overparameterized two-layer neural networks

venue: arXiv preprint arXiv:1901.08584,

authors:
Peter L Bartlett
Shahar Mendelson

title: Rademacher and gaussian complexities: Risk bounds and structural results

venue: Journal of Machine Learning Research,

authors:
Frank Bauer
Sergei Pereverzev
Lorenzo Rosasco

title: On regularization algorithms in learning theory

venue: Journal of complexity,

authors:
Yuan Cao
Quanquan Gu

title: A generalization theory of gradient descent for learning overparameterized deep relu networks

venue: arXiv preprint arXiv:1902.01384,

authors:
Lenaic Chizat
Francis Bach

title: A note on lazy training in supervised differentiable programming

venue: arXiv preprint arXiv:1812.07956,

authors:
Simon S Du
Wei Hu
Jason D Lee

title: Algorithmic regularization in learning deep homogeneous models: Layers are automatically balanced

venue: In Advances in Neural Information Processing Systems

authors:
Simon S Du
Jason D Lee
Haochuan Li
Liwei Wang
Xiyu Zhai

title: Gradient descent finds global minima of deep neural networks

venue: arXiv preprint arXiv:1811.03804,

authors:
Simon S Du
Kangcheng Hou
Barnabás Póczos
Ruslan Salakhutdinov
Ruosong Wang
Keyulu Xu

title: Graph neural tangent kernel: Fusing graph neural networks with graph kernels

venue: arXiv preprint arXiv:1905.13192,

authors:
Simon S. Du
Xiyu Zhai
Barnabas Poczos
Aarti Singh

title: Gradient descent provably optimizes over-parameterized neural networks

venue: In International Conference on Learning Representations,

authors:
L Lo Gerfo
Lorenzo Rosasco
Francesca Odone
E De Vito
Alessandro Verri

title: Spectral algorithms for supervised learning

venue: Neural Computation,

authors:
Aritra Ghosh
Himanshu Kumar
PS Sastry

title: Robust loss functions under label noise for deep neural networks

venue: In Thirty-First AAAI Conference on Artificial Intelligence,

authors:
Melody Y Guan
Varun Gulshan
Andrew M Dai
Geoffrey E Hinton

title: Who said what: Modeling individual labelers improves classification

venue: In Thirty-Second AAAI Conference on Artificial Intelligence,

authors:
Bo Han
Quanming Yao
Xingrui Yu
Gang Niu
Miao Xu
Weihua Hu
Ivor Tsang
Masashi Sugiyama

title: Co-teaching: Robust training of deep neural networks with extremely noisy labels

venue: In NeurIPS,

authors:
Daniel Hsu
Sham Kakade
Tong Zhang

title: A tail inequality for quadratic forms of subgaussian random vectors

venue: Electronic Communications in Probability,

authors:
Arthur Jacot
Franck Gabriel
Clément Hongler

title: Neural tangent kernel: Convergence and generalization in neural networks

venue: arXiv preprint arXiv:1806.07572,

authors:
Lu Jiang
Zhengyuan Zhou
Thomas Leung
Li-Jia Li
Li Fei-Fei

title: Mentornet: Learning data-driven curriculum for very deep neural networks on corrupted labels

venue: arXiv preprint arXiv:1712.05055,

authors:
Ranjay A Krishna
Kenji Hata
Stephanie Chen
Joshua Kravitz
David A Shamma
Li Fei-Fei
Michael S Bernstein

title: Embracing error to enable rapid crowdsourcing

venue: In Proceedings of the 2016 CHI conference on human factors in computing systems,

authors:
Jaehoon Lee
Lechao Xiao
Samuel S Schoenholz
Yasaman Bahri
Jascha Sohl-Dickstein
Jeffrey Pennington

title: Wide neural networks of any depth evolve as linear models under gradient descent

authors:
Mingchen Li
Mahdi Soltanolkotabi
Samet Oymak

title: Gradient descent with early stopping is provably robust to label noise for overparameterized neural networks

authors:
Yuanzhi Li
Yingyu Liang

title: Learning overparameterized neural networks via stochastic gradient descent on structured data

venue: arXiv preprint arXiv:1808.01204,

authors:
Tongliang Liu
Dacheng Tao

title: Classification with noisy labels by importance reweighting

venue: IEEE Transactions on pattern analysis and machine intelligence,

authors:
Eran Malach
Shai Shalev-Shwartz

title: Decoupling" when to update" from" how to update

venue: In Advances in Neural Information Processing Systems,

authors:
Mehryar Mohri
Afshin Rostamizadeh
Ameet Talwalkar

title: Foundations of machine learning

authors:
Vaishnavh Nagarajan
J Zico Kolter

title: Generalization in deep networks: The role of distance from initialization

venue: arXiv preprint arXiv:1901.01672,

authors:
Behnam Neyshabur
Zhiyuan Li
Srinadh Bhojanapalli
Yann LeCun
Nathan Srebro

title: The role of over-parametrization in generalization of neural networks

authors:
Garvesh Raskutti
Martin J Wainwright
Bin Yu

title: Early stopping and non-parametric regression: an optimal data-dependent stopping rule

venue: The Journal of Machine Learning Research,

authors:
Mengye Ren
Wenyuan Zeng
Bin Yang
Raquel Urtasun

title: Learning to reweight examples for robust deep learning

venue: arXiv preprint arXiv:1803.09050,

authors:
David Rolnick
Andreas Veit
Serge Belongie
Nir Shavit

title: Deep learning is robust to massive label noise

venue: arXiv preprint arXiv:1705.10694,

authors:
Sainbayar Sukhbaatar
Joan Bruna
Manohar Paluri
Lubomir Bourdev
Rob Fergus

title: Training convolutional networks with noisy labels

venue: arXiv preprint arXiv:1406.2080,

authors:
Yuting Wei
Fanny Yang
Martin J Wainwright

title: Early stopping for kernel boosting algorithms: A general analysis with localized complexities

title: Scaling limits of wide neural networks with weight sharing: Gaussian process behavior, gradient independence, and neural tangent kernel derivation

authors:
Xingrui Yu
Bo Han
Jiangchao Yao
Gang Niu
Ivor Tsang
Masashi Sugiyama

title: How does disagreement help generalization against label corruption

venue: In International Conference on Machine Learning,

authors:
Chiyuan Zhang
Samy Bengio
Moritz Hardt
Benjamin Recht
Oriol Vinyals

title: Understanding deep learning requires rethinking generalization

venue: In Proceedings of the International Conference on Learning Representations (ICLR),

authors:
Zhilu Zhang
Mert Sabuncu

title: Generalized cross entropy loss for training deep neural networks with noisy labels

authors:
Difan Zou
Yuan Cao
Dongruo Zhou
Quanquan Gu

title: Stochastic gradient descent optimizes over-parameterized deep ReLU networks

venue: arXiv preprint arXiv:1811.08888,

heading: 1 INTRODUCTION

text:
Modern deep neural networks are trained in a highly over-parameterized regime, with many more trainable parameters than training examples. It is well-known that these networks trained with simple first-order methods can fit any labels, even completely random ones (Zhang et al., 2017). Although training on properly labeled data usually leads to good generalization performance, the ability to over-fit the entire training dataset is undesirable for generalization when noisy labels are present. Therefore preventing over-fitting is crucial for robust performance since mislabeled data are ubiquitous in very large datasets (Krishna et al., 2016).
In order to prevent over-fitting to mislabeled data, some form of regularization is necessary. A simple such example is early stopping, which has been observed to be surprisingly effective for this purpose (Rolnick et al., 2017; Guan et al., 2018; Li et al., 2019). For instance, training ResNet-34 with early stopping can achieve 84% test accuracy on CIFAR-10 even when 60% of the training labels are corrupted (Table 1). This is nontrivial since the test error is much smaller than the error rate in training data. How to explain such generalization phenomenon is an intriguing theoretical question.
As a step towards a theoretical understanding of the generalization phenomenon for overparameterized neural networks when noisy labels are present, this paper proposes and analyzes two simple regularization methods as alternatives of early stopping:
1. Regularization by distance to initialization. Denote by θ the network parameters and by θp0q its random initialization. This method adds a regularizer λ }θ ´ θp0q}2 to the training objective.
2. Adding an auxiliary variable for each training example. Let xi be the i-th training example and fpθ, ¨q represent the neural net. This method adds a trainable variable bi and tries to fit the i-th label using fpθ,xiq ` λbi. At test time, only the neural net fpθ, ¨q is used and the auxiliary variables are discarded.
These two choices of regularization are well motivated with clear intuitions. First, distance to initialization has been observed to be very related to generalization in deep learning (Neyshabur et al., 2019; Nagarajan and Kolter, 2019), so regularizing by distance to initialization can potentially help generalization. Second, the effectiveness of early stopping indicates that clean labels are somewhat easier to fit than wrong labels; therefore, adding an auxiliary variable could help “absorb” the noise in the labels, thus making the neural net itself not over-fitting.
We provide theoretical analysis of the above two regularization methods for a class of sufficiently wide neural networks by proving a generalization bound for the trained network on clean data distribution when the training dataset contains noisy labels. Our generalization bound depends on the (unobserved) clean labels, and is comparable to the bound one can get when there is no label noise, therefore indicating that the proposed regularization methods are robust to noisy labels.
Our theoretical analysis is based on the recently established connection between wide neural net and neural tangent kernel (Jacot et al., 2018; Lee et al., 2019; Arora et al., 2019a). In this line of work, parameters in a wide neural net are shown to stay close to their initialization during gradient descent training, and as a consequence, the neural net can be effectively approximated by its first-order Taylor expansion with respect to its parameters at initialization. This leads to tractable linear dynamics under `2 loss, and the final solution can be characterized by kernel regression using a particular kernel named neural tangent kernel (NTK). In fact, we show that for wide neural nets, both of our regularization methods, when trained with gradient descent to convergence, correspond to kernel ridge regression using the NTK, which is often regarded as an alternative to early stopping in kernel literature. This viewpoint makes explicit the connection between our methods and early stopping.
The effectiveness of these two regularization methods is verified empirically – on MNIST and CIFAR-10, they are able to achieve highly nontrivial test accuracy, on a par with or even better than early stopping. Furthermore, with our regularization, the validation accuracy is almost monotone increasing throughout the entire training process, indicating their resistance to over-fitting.

heading: 2 RELATED WORK

text:
Neural tangent kernel was first explicitly studied and named by Jacot et al. (2018), with several further refinements and extensions by Lee et al. (2019); Yang (2019); Arora et al. (2019a). Using the similar idea that weights stay close to initialization and that the neural network is approximated by a linear model, a series of theoretical papers studied the optimization and generalization issues of very wide deep neural nets trained by (stochastic) gradient descent (Du et al., 2019b; 2018b; Li and Liang, 2018; Allen-Zhu et al., 2018a;b; Zou et al., 2018; Arora et al., 2019b; Cao and Gu, 2019). Empirically, variants of NTK on convolutional neural nets and graph neural nets exhibit strong practical performance (Arora et al., 2019a; Du et al., 2019a), thus suggesting that ultra-wide (or infinitely wide) neural nets are at least not irrelevant.
Our methods are closely related to kernel ridge regression, which is one of the most common kernel methods and has been widely studied. It was shown to perform comparably to early-stopped gradient descent (Bauer et al., 2007; Gerfo et al., 2008; Raskutti et al., 2014; Wei et al., 2017). Accordingly, we indeed observe in our experiments that our regularization methods perform similarly to gradient descent with early stopping in neural net training.
In another theoretical study relevant to ours, Li et al. (2019) proved that gradient descent with early stopping is robust to label noise for an over-parameterized two-layer neural net. Under a clustering assumption on data, they showed that gradient descent fits the correct labels before starting to over-fit wrong labels. Their result is different from ours from several aspects: they only considered two-layer nets while we allow arbitrarily deep nets; they required a clustering assumption on data while our generalization bound is general and data-dependent; furthermore, they did not address the question of generalization, but only provided guarantees on the training data.
A large body of work proposed various methods for training with mislabeled examples, such as estimating noise distribution (Liu and Tao, 2015) or confusion matrix (Sukhbaatar et al., 2014), using surrogate loss functions (Ghosh et al., 2017; Zhang and Sabuncu, 2018), meta-learning (Ren et al., 2018), using a pre-trained network (Jiang et al., 2017), and training two networks simultaneously (Malach and Shalev-Shwartz, 2017; Han et al., 2018; Yu et al., 2019). While our methods are not necessarily superior to these methods in terms of performance, our methods are arguably simpler (with minimal change to normal training procedure) and come with formal generalization guarantee.

heading: 3 PRELIMINARIES

text: Notation. We use bold-faced letters for vectors and matrices. We use }¨} to denote the Euclidean norm of a vector or the spectral norm of a matrix, and }¨}F to denote the Frobenius norm of a matrix. x¨, ¨y represents the standard inner product. Let I be the identity matrix of appropriate dimension. Let rns “ t1, 2, . . . , nu. Let IrAs be the indicator of event A.

heading: 3.1 SETTING: LEARNING FROM NOISILY LABELED DATA

text:
Now we formally describe the setting considered in this paper. We first describe the binary classification setting as a warm-up, and then describe the more general setting of multi-class classification.
Binary classification. Suppose that there is an underlying data distribution D over Rd ˆ t˘1u, where 1 and ´1 are labels corresponding to two classes. However, we only have access to samples from a noisily labeled version of D. Formally, the data generation process is: draw px, yq „ D, and flip the sign of label y with probability p (0 ď p ă 12 ); let ỹ P t˘1u be the resulting noisy label.
Let tpxi, ỹiquni“1 be i.i.d. samples generated from the above process. Although we only have access to these noisily labeled data, the goal is still to learn a function (in the form of a neural net) that can predict the true label well on the clean distribution D. For binary classification, it suffices to learn a single-output function f : Rd Ñ R whose sign is used to predict the class, and thus the classification error of f on D is defined as Prpx,yq„Drsgnpfpxqq “ ys.
Multi-class classification. When there are K classes (K ą 2), let the underlying data distribution D be over Rd ˆ rKs. We describe the noise generation process as a matrix P P RKˆK , whose entry pc1,c is the probability that the label c is transformed into c1 (@c, c1 P rKs). Therefore the data generation process is: draw px, cq „ D, and replace the label c with c̃ from the distribution Prrc̃ “ c1|cs “ pc1,c (@c1 P rKs). Let tpxi, c̃iquni“1 be i.i.d. samples from the above process. Again we would like to learn a neural net with low classification error on the clean distribution D. For K-way classification, it is common to use a neural net with K outputs, and the index of the maximum output is used to predict the class. Thus for f : Rd Ñ RK , its (top-1) classification error on D is Prpx,cq„Drc R argmaxhPrKsf phqpxqs, where f phq : Rd Ñ R is the function computed by the h-th output of f .
As standard practice, a class label c P rKs is also treated as its one-hot encoding epcq “ p0, 0, ¨ ¨ ¨ , 0, 1, 0, ¨ ¨ ¨ , 0q P RK (the c-th coordinate being 1), which can be paired with the K outputs of the network and fed into a loss function during training.
Note that it is necessary to assume pc,c ą pc1,c for all c “ c1, i.e., the probability that a class label c is transformed into another particular label must be smaller than the label c being correct – otherwise it is impossible to identify class c correctly from noisily labeled data.

heading: 3.2 RECAP OF NEURAL TANGENT KERNEL

text:
Now we briefly and informally recap the theory of neural tangent kernel (NTK) (Jacot et al., 2018; Lee et al., 2019; Arora et al., 2019a), which establishes the equivalence between training a wide neural net and a kernel method.
We first consider a neural net with a scalar output, defined as fpθ,xq P R, where θ P RN is all the parameters in the net and x P Rd is the input. Suppose that the net is trained by minimizing the `2 loss over a training dataset tpxi, yiquni“1 Ă Rd ˆ R: Lpθq “ 12 řn i“1 pfpθ,xiq ´ yiq 2 . Let the random initial parameters be θp0q, and the parameters be updated according to gradient descent on Lpθq. It is shown that if the network is sufficiently wide1, the parameters θ will stay close to the initialization θp0q during training so that the following first-order approximation is accurate:
fpθ,xq « fpθp0q,xq ` x∇θfpθp0q,xq,θ ´ θp0qy. (1)
This approximation is exact in the infinite width limit, but can also be shown when the width is finite but sufficiently large. When approximation (1) holds, we say that we are in the NTK regime.
Define φpxq “ ∇θfpθp0q,xq for any x P Rd. The right hand side in (1) is linear in θ. As a consequence, training on the `2 loss with gradient descent leads to the kernel regression solution
1“Width” refers to number of nodes in a fully connected layer or number of channels in a convolutional layer.
with respect to the kernel induced by (random) features φpxq, which is defined as kpx,x1q “ xφpxq,φpx1qy for x,x1 P Rd. This kernel was named the neural tangent kernel (NTK) by Jacot et al. (2018). Although this kernel is random, it is shown that when the network is sufficiently wide, this random kernel converges to a deterministic limit in probability (Arora et al., 2019a). If we additionally let the neural net and its initialization be defined so that the initial output is small, i.e., fpθp0q,xq « 0,2 then the network at the end of training approximately computes the following function:
x ÞÑ kpx,XqJ pkpX,Xqq´1 y, (2) whereX “ px1, . . . ,xnq is the training inputs, y “ py1, . . . , ynqJ is the training targets, kpx,Xq “ pkpx,x1q, . . . , kpx,xnqqJ P Rn, and kpX,Xq P Rnˆn with pi, jq-th entry being kpxi,xjq.
Multiple outputs. The NTK theory above can also be generalized straightforwardly to the case of multiple outputs (Jacot et al., 2018; Lee et al., 2019). Suppose we train a neural net with K outputs, fpθ,xq, by minimizing the `2 loss over a training dataset tpxi,yiquni“1 Ă Rd ˆ RK : Lpθq “ 12 řn i“1 }fpθ,xiq ´ yi} 2 . When the hidden layers are sufficiently wide such that we are in the NTK regime, at the end of gradient descent, each output of f also attains the kernel regression solution with respect to the same NTK as before, using the corresponding dimension in the training targets yi. Namely, the h-th output of the network computes the function
f phqpxq “ kpx,XqJ pkpX,Xqq´1 yphq,
where yphq P Rn whose i-th coordinate is the h-th coordinate of yi.

heading: 4 REGULARIZATION METHODS

text:
In this section we describe two simple regularization methods for training with noisy labels, and show that if the network is sufficiently wide, both methods lead to kernel ridge regression using the NTK.3
We first consider the case of scalar target and single-output network. The generalization to multiple outputs is straightforward and is treated at the end of this section. Given a noisily labeled training dataset tpxi, ỹiquni“1 Ă RdˆR, let fpθ, ¨q be a neural net to be trained. A direct, unregularized training method would involve minimizing an objective function like Lpθq “ 12 řn i“1 pfpθ,xiq ´ ỹiq
2. To prevent over-fitting, we suggest the following simple regularization methods that slightly modify this objective:
• Method 1: Regularization using Distance to Initialization (RDI). We let the initial parameters θp0q be randomly generated, and minimize the following regularized objective:
LRDIλ pθq “ 1
2
n ÿ i“1 pfpθ,xiq ´ ỹiq2 ` λ2 2 }θ ´ θp0q}2 . (3)
• Method 2: adding an AUXiliary variable for each training example (AUX). We add an auxiliary trainable parameter bi P R for each i P rns, and minimize the following objective:
LAUXλ pθ, bq “ 1
2
n ÿ i“1 pfpθ,xiq ` λbi ´ ỹiq2 , (4)
where b “ pb1, . . . , bnqJ P Rn is initialized to be 0.
Equivalence to kernel ridge regression in wide neural nets. Now we assume that we are in the NTK regime described in Section 3.2, where the neural net architecture is sufficiently wide so that the first-order approximation (1) is accurate during gradient descent: fpθ,xq « fpθp0q,xq ` φpxqJpθ ´ θp0qq. Recall that we have φpxq “ ∇θfpθp0q,xq which induces the NTK kpx,x1q “ xφpxq,φpx1qy. Also recall that we can assume near-zero initial output: fpθp0q,xq « 0 (see Footnote 2). Therefore we have the approximation:
fpθ,xq « φpxqJpθ ´ θp0qq. (5) 2We can ensure small or even zero output at initialization by either multiplying a small factor (Arora et al., 2019a;b), or using the following “difference trick”: define the network to be the difference between two networks with the same architecture, i.e., fpθ,xq “ ? 2 2 gpθ1,xq ´ ? 2 2 gpθ2,xq; then initialize θ1 and θ2 to be the same (and still random); this ensures fpθp0q,xq “ 0 p@xq at initialization, while keeping the same value of xφpxq,φpx1qy for both f and g. See more details in Appendix A.
3For the theoretical results in this paper we use `2 loss. In Section 6 we will present experimental results of both `2 loss and cross-entropy loss for classification.
Under the approximation (5), it suffices to consider gradient descent on the objectives (3) and (4) using the linearized model instead:
L̃RDIλ pθq “ 1
2
n ÿ
i“1
´ φpxiqJpθ ´ θp0qq ´ ỹi ¯2 ` λ 2
2 }θ ´ θp0q}2 ,
L̃AUXλ pθ, bq “ 1
2
n ÿ
i“1
´ φpxiqJpθ ´ θp0qq ` λbi ´ ỹi ¯2 .
The following theorem shows that in either case, gradient descent leads to the same dynamics and converges to the kernel ridge regression solution using the NTK. Theorem 4.1. Fix a learning rate η ą 0. Consider gradient descent on L̃RDIλ with initialization θp0q:
θpt` 1q “ θptq ´ η∇θL̃RDIλ pθptqq, t “ 0, 1, 2, . . . (6) and gradient descent on L̃AUXλ pθ, bq with initialization θp0q and bp0q “ 0:
θ̄p0q “ θp0q, θ̄pt` 1q “ θ̄ptq ´ η∇θL̃AUXλ pθ̄ptq, bptqq, t “ 0, 1, 2, . . . bp0q “ 0, bpt` 1q “ bptq ´ η∇bL̃AUXλ pθ̄ptq, bptqq, t “ 0, 1, 2, . . .
(7)
Then we must have θptq “ θ̄ptq for all t. Furthermore, if the learning rate satisfies η ď 1}kpX,Xq}`λ2 , then tθptqu converges linearly to a limit solution θ˚ such that:
φpxqJpθ˚ ´ θp0qq “ kpx,XqJ ` kpX,Xq ` λ2I ˘´1
ỹ, @x, where ỹ “ pỹ1, . . . , ỹnqJ P Rn.
Proof sketch. The proof is given in Appendix B. A key step is to observe θ̄ptq “ θp0q` řn i“1 1 λbiptq¨ φpxiq, from which we can show that tθptqu and tθ̄ptqu follow the same update rule.
Theorem 4.1 indicates that gradient descent on the regularized objectives (3) and (4) both learn approximately the following function at the end of training when the neural net is sufficiently wide:
f˚pxq “ kpx,XqJ ` kpX,Xq ` λ2I ˘´1
ỹ. (8) If no regularization were used, the labels ỹ would be fitted perfectly and the learned function would be kpx,XqJ pkpX,Xqq´1 ỹ (c.f. (2)). Therefore the effect of regularization is to add λ2I to the kernel matrix, and (8) is known as the solution to kernel ridge regression in kernel literature. In Section 5, we give a generalization bound of this solution on the clean data distribution, which is comparable to the bound one can obtain even when clean labels are used in training.
Extension to multiple outputs. Suppose that the training dataset is tpxi, ỹiquni“1 Ă RdˆRK , and the neural net fpθ,xq has K outputs. On top of the vanilla loss Lpθq “ 12 řn i“1 }fpθ,xiq ´ ỹi}
2, the two regularization methods RDI and AUX give the following objectives similar to (3) and (4):
LRDIλ pθq “ 1
2
n ÿ i“1 }fpθ,xiq ´ ỹi}2 ` λ2 2 }θ ´ θp0q}2 ,
LAUXλ pθ,Bq “ 1
2
n ÿ i“1 }fpθ,xiq ` λbi ´ ỹi}2 , B “ pb1, . . . , bnq P RKˆn.
In the NTK regime, both methods lead to the kernel ridge regression solution at each output. Namely, letting Ỹ “ pỹ1, . . . , ỹnq P RKˆn be the training target matrix and ỹphq P Rn be the h-th row of Ỹ , at the end of training the h-th output of the network learns the following function:
f phqpxq “ kpx,XqJ ` kpX,Xq ` λ2I ˘´1 ỹphq, h P rKs. (9)

heading: 5 GENERALIZATION GUARANTEE ON CLEAN DATA DISTRIBUTION

text:
We show that gradient descent training on noisily labeled data with our regularization methods RDI or AUX leads to a generalization guarantee on the clean data distribution. As in Section 4, we consider the NTK regime and let kp¨, ¨q be the NTK corresponding to the neural net. It suffices to analyze the kernel ridge regression predictor, i.e., (8) for single output and (9) for multiple outputs.
We start with a regression setting where labels are real numbers and the noisy label is the true label plus an additive noise (Theorem 5.1). Built on this result, we then provide generalization bounds for the classification settings described in Section 3.1. Omitted proofs in this section are in Appendix C.
Theorem 5.1 (Additive label noise). Let D be a distribution over Rd ˆ r´1, 1s. Consider the following data generation process: (i) draw px, yq „ D, (ii) conditioned on px, yq, let ε be drawn from a noise distribution Ex,y over R that may depend on x and y, and (iii) let ỹ “ y ` ε. Suppose that Ex,y has mean 0 and is subgaussian with parameter σ ą 0, for any px, yq.
Let tpxi, yi, ỹiquni“1 be i.i.d. samples from the above process. Denote X “ px1, . . . ,xnq, y “ py1, . . . , ynqJ and ỹ “ pỹ1, . . . , ỹnqJ. Consider the kernel ridge regression solution in (8): f˚pxq “ kpx,XqJ ` kpX,Xq ` λ2I ˘´1
ỹ. Suppose that the kernel matrix satisfies trrkpX,Xqs “ Opnq. Then for any loss function ` : R ˆ R Ñ r0, 1s that is 1-Lipschitz in the first argument such that `py, yq “ 0, with probability at least 1´ δ we have
Epx,yq„D “ `pf˚pxq, yq ‰ ď λ`Op1q 2
c
yJpkpX,Xqq´1y n `O ´σ λ ¯ `∆, (10)
where ∆ “ O ˆ σ b
logp1{δq n ` σ λ
b
logp1{δq n `
b
log nδλ n
˙
.
Remark 5.1. As the number of samples n Ñ 8, we have ∆ Ñ 0. In order for the second term Opσλ q in (10) to go to 0, we need to choose λ to grow with n, e.g., λ “ n c for some small constant c ą 0. Then, the only remaining term in (10) to worry about is λ2 b yJpkpX,Xqq´1y n . Notice that it depends on the (unobserved) clean labels y, instead of the noisy labels ỹ. By a very similar proof, one can show that training on the clean labels y (without regularization) leads to a population loss bound O ´ b
yJpkpX,Xqq´1y n
¯
. In comparison, we can see that even when there is label noise, we
only lose a factor of Opλq in the population loss on the clean distribution, which can be chosen as any slow-growing function of n. If yJpkpX,Xqq´1y grows much slower than n, by choosing an appropriate λ, our result indicates that the underlying distribution is learnable in presence of additive label noise. See Remark 5.2 for an example. Remark 5.2. Arora et al. (2019b) proved that two-layer ReLU neural nets trained with gradient descent can learn a class of smooth functions on the unit sphere. Their proof is by showing yJpkpX,Xqq´1y “ Op1q if yi “ gpxiq p@i P rnsq for certain function g, where kp¨, ¨q is the NTK corresponding to two-layer ReLU nets. Combined with their result, Theorem 5.1 implies that the same class of functions can be learned by the same network even if the labels are noisy.
Next we use Theorem 5.1 to provide generalization bounds for the classification settings described in Section 3.1. For binary classification, we treat the labels as ˘1 and consider a single-output neural net; for K-class classification, we treat the labels as their one-hot encodings (which are K standard unit vectors in RK) and consider a K-output neural net. Again, we use `2 loss and wide neural nets so that it suffices to consider the kernel ridge regression solution ((8) or (9)). Theorem 5.2 (Binary classification). Consider the binary classification setting stated in Section 3.1. Let tpxi, yi, ỹiquni“1 Ă Rd ˆ t˘1u ˆ t˘1u be i.i.d. samples from that process. Recall that Prrỹi “ yi|yis “ p (0 ď p ă 12 ). Denote X “ px1, . . . ,xnq, y “ py1, . . . , ynq
J and ỹ “ pỹ1, . . . , ỹnqJ. Consider the kernel ridge regression solution in (8): f˚pxq “ kpx,XqJ ` kpX,Xq ` λ2I ˘´1
ỹ. Suppose that the kernel matrix satisfies trrkpX,Xqs “ Opnq. Then with probability at least 1´ δ, the classification error of f˚ on the clean distribution D satisfies
Pr px,yq„D rsgnpf˚pxqq ‰ ys ď λ`Op1q 2
c
yJpkpX,Xqq´1y n ` 1 1´ 2pO
¨
˝
? p
λ `
d
p log 1 δ n ` c log n δλ n
˛
‚.
Theorem 5.3 (Multi-class classification). Consider the K-class classification setting stated in Section 3.1. Let tpxi, ci, c̃iquni“1 Ă Rd ˆ rKs ˆ rKs be i.i.d. samples from that process. Recall that Prrc̃i “ c1|ci “ cs “ pc1,c (@c, c1 P rKs), where the transition probabilities form a matrix P P RKˆK . Let gap “ minc,c1PrKs,c “c1ppc,c ´ pc1,cq.
Let X “ px1, . . . ,xnq, and let yi “ epciq P RK , ỹi “ epc̃iq P RK be one-hot label encodings. Denote Y “ py1, . . . ,ynq P RKˆn, Ỹ “ pỹ1, . . . , ỹnq P RKˆn, and let ỹphq P Rn be the h-th row of Ỹ . Define a matrixQ “ P ¨ Y P RKˆn, and let qphq P Rn be the h-th row ofQ.
Consider the kernel ridge regression solution in (9): f phqpxq “ kpx,XqJ ` kpX,Xq ` λ2I ˘´1
ỹphq. Suppose that the kernel matrix satisfies trrkpX,Xqs “ Opnq. Then with probability at least 1´ δ, the classification error of f “ pf phqqKk“1 on the clean data distribution D is bounded as
0.0 0.1 0.2 0.3 0.4 Noise level
0.0
0.1
0.2
0.3
0.4
Te st
e rr
or
GD early stop GD+AUX GD+RDI
(a) Test error vs. noise level for Setting 1. For each noise level, we do a grid search for λ and report the best accuracy.
0 100 200 300 400 500 600 Epoch
0.00
0.05
0.10
0.15
0.20
0.25
0.30
0.35
er ro
r
SGD+AUX SGD+RDI SGD+AUX SGD+RDI SGD SGD
(b) Training (dashed) & test (solid) errors vs. epoch for Setting 2. Noise rate “ 20%, λ “ 4. Training error of AUX is measured with auxiliary variables.
Note that the bounds in Theorems 5.2 and 5.3 only depend on the clean labels instead of the noisy labels, similar to Theorem 5.1.

heading: 6 EXPERIMENTS

text:
In this section, we empirically verify the effectiveness of our regularization methods RDI and AUX, and compare them against gradient descent or stochastic gradient descent (GD/SGD) with or without early stopping. We experiment with three settings of increasing complexities:
Setting 1: Binary classification on MNIST (“5” vs. “8”) using a two-layer wide fully-connected net.
Setting 2: Binary classification on CIFAR (“airplanes” vs. “automobiles”) using a 11-layer convolutional neural net (CNN).
Setting 3: CIFAR-10 classification (10 classes) using standard ResNet-34.
For detailed description see Appendix D. We obtain noisy labels by randomly corrupting correct labels, where noise rate/level is the fraction of corrupted labels (for CIFAR-10, a corrupted label is chosen uniformly from the other 9 classes.)

heading: 6.1 PERFORMANCE OF REGULARIZATION METHODS

text:
For Setting 1 (binary MNIST), we plot the test errors of different methods under different noise rates in Figure 1a. We observe that both methods GD+AUX and GD+RDI consistently achieve much lower test error than vanilla GD which over-fits the noisy dataset, and they achieve similar test error to GD with early stopping. We see that GD+AUX and GD+RDI have essentially the same performance, which verifies our theory of their equivalence in wide networks (Theorem 4.1).
For Setting 2 (binary CIFAR), Figure 1b shows the learning curves (training and test errors) of SGD, SGD+AUX and SGD+RDI for noise rate 20% and λ “ 4. Additional figures for other choices of λ are in Figure 5. We again observe that both SGD+AUX and SGD+RDI outperform vanilla SGD and are comparable to SGD with early stopping. We also observe a discrepancy between SGD+AUX and SGD+RDI, possibly due to the noise in SGD or the finite width.
Finally, for Setting 3 (CIFAR-10), Table 1 shows the test accuracies of training with and without AUX. We train with both mean square error (MSE/`2 loss) and categorical cross entropy (CCE) loss. For normal training without AUX, we report the test accuracy at the epoch where validation accuracy is maximum (early stopping). For training with AUX, we report the test accuracy at the last epoch as well as the best epoch. Figure 2 shows the training curves for noise rate 0.4. We observe that training with AUX achieves very good test accuracy – even better than the best accuracy of normal training with early stopping, and better than the recent method of Zhang and Sabuncu (2018) using the same
0 20 40 60 80 100 120 140 160
50
60
70
80
90
MSE CCE MSE + AUX CCE + AUX
Figure 2: Test accuracy during CIFAR-10 training (noise 0.4).
0 200 400 600 Epoch
577.4
577.6
577.8
578.0
Fr ob
en iu
s N
or m
SGD+AUX SGD+RDI SGD
0 200 400 600 Epoch
0
2
4
6
8
10
D is
ta nc
e to
In iti
al iz
at io
n
SGD+AUX SGD+RDI SGD
Figure 3: Setting 2, }W p4q}F and }W p4q ´W p4qp0q}F during training. Noise “ 20%, λ “ 4.
architecture (ResNet-34). Furthermore, AUX does not over-fit (the last epoch performs similarly to the best epoch). In addition, we find that in this setting classification performance is insensitive of whether MSE or CCE is used as the loss function.

heading: 6.2 DISTANCE OF WEIGHTS TO INITIALIZATION, VERIFICATION OF THE NTK REGIME

text:
We also track how much the weights move during training as a way to see whether the neural net is in the NTK regime. For Settings 1 and 2, we find that the neural nets are likely in or close to the NTK regime because the weight movements are small during training. Figure 3 shows in Setting 2 how much the 4-th layer weights move during training. Additional figures are provided as Figures 6 to 8.
Table 2 summarizes the relationship between the distance to initialization and other hyper-parameters that we observe from various experiments. Note that the weights tend to move more with larger noise level, and AUX and RDI can reduce the moving distance as expected (as shown in Figure 3).
The ResNet-34 in Setting 3 is likely not operating in the NTK regime, so its effectiveness cannot yet be explained by our theory. This is an intriguing direction of future work.

heading: 7 CONCLUSION

text: Towards understanding generalization of deep neural networks in presence of noisy labels, this paper presents two simple regularization methods and shows that they are theoretically and empirically effective. The theoretical analysis relies on the correspondence between neural networks and NTKs. We believe that a better understanding of such correspondence could help the design of other principled methods in practice. We also observe that our methods can be effective outside the NTK regime. Explaining this theoretically is left for future work.

heading: ACKNOWLEDGMENTS

text: This work is supported by NSF, ONR, Simons Foundation, Schmidt Foundation, Mozilla Research, Amazon Research, DARPA and SRC. The authors thank Sanjeev Arora for helpful discussions and suggestions. The authors thank Amazon Web Services for cloud computing time.

heading: A DIFFERENCE TRICK

text:
We give a quick analysis of the “difference trick” described in Footnote 2, i.e., let fpθ,xq “? 2 2 gpθ1,xq ´ ? 2 2 gpθ2,xq where θ “ pθ1,θ2q, and initialize θ1 and θ2 to be the same (and still random). The following lemma implies that the NTKs for f and g are the same.
Lemma A.1. If θ1p0q “ θ2p0q, then
(i) fpθp0q,xq “ 0, @x;
(ii) x∇θfpθp0q,xq,∇θfpθp0q,x1qy “ x∇θ1gpθ1p0q,xq,∇θ1gpθ1p0q,x1qy, @x,x1.
Proof. (i) holds by definition. For (ii), we can calculate that @
∇θfpθp0q,xq,∇θfpθp0q,x1q D
“ @ ∇θ1fpθp0q,xq,∇θ1fpθp0q,x1q D ` @ ∇θ2fpθp0q,xq,∇θ2fpθp0q,x1q D
“ 1 2 x∇θ1gpθ1p0q,xq,∇θ1gpθ1p0q,xqy ` 1 2 @ ∇θ2gpθ2p0q,xq,∇θ2gpθ2p0q,x1q D “ @
∇θ1gpθ1p0q,xq,∇θ1gpθ1p0q,x1q D .
The above lemma allows us to ensure zero output at initialization while preserving NTK. As a comparison, Chizat and Bach (2018) proposed the following "doubling trick": neurons in the last layer are duplicated, with the new neurons having the same input weights and opposite output weights. This satisfies zero output at initialization, but destroys the NTK. To see why, note that with the “doubling trick", the network will output 0 at initialization no matter what the input to its second to last layer is. Thus the gradients with respect to all parameters that are not in the last two layers are 0.
In our experiments, we observe that the performance of the neural net improves with the “difference trick.” See Figure 4. This intuitively makes sense, since the initial network output is independent of the label (only depends on the input) and thus can be viewed as noise. When the width of the neural net is infinity, the initial network output is actually a zero-mean Gaussian process, whose covariance matrix is equal to the NTK contributed by the gradients of parameters in its last layer. Therefore, learning an infinitely wide neural network with nonzero initial output is equivalent to doing kernel regression with an additive correlated Gaussian noise on training and testing labels.

heading: B MISSING PROOF IN SECTION 4

text:
Proof of Theorem 4.1. The gradient of L̃AUXλ pθ, bq can be written as
∇θL̃AUXλ pθ, bq “ ÿn
i“1 aiφpxiq, ∇biL̃AUXλ pθ, bq “ λai, i “ 1, . . . , n,
where ai “ φpxiqJpθ ´ θp0qq ` λbi ´ ỹi pi P rnsq. Therefore we have ∇θL̃AUXλ pθ, bq “ řn i“1 1 λ∇biL̃ AUX λ pθ, bq ¨φpxq. Then, according to the gradient descent update rule (7), we know that θ̄ptq and bptq can always be related by θ̄ptq “ θp0q ` řn i“1 1 λbiptq ¨ φpxiq. It follows that
θ̄pt` 1q “ θ̄ptq ´ η ÿn
i“1
` φpxiqJpθ̄ptq ´ θp0qq ` λbiptq ´ ỹi ˘ φpxiq
“ θ̄ptq ´ η ÿn
i“1
` φpxiqJpθ̄ptq ´ θp0qq ´ ỹi ˘ φpxiq ´ ηλ ÿn
i“1 biptqφpxiq
“ θ̄ptq ´ η ÿn
i“1
` φpxiqJpθ̄ptq ´ θp0qq ´ ỹi ˘ φpxiq ´ ηλ2pθ̄ptq ´ θp0qq.
On the other hand, from (6) we have
θpt` 1q “ θptq ´ η ÿn
i“1
` φpxiqJpθptq ´ θp0qq ´ ỹi ˘ φpxiq ´ ηλ2pθptq ´ θp0qq.
Comparing the above two equations, we find that tθptqu and tθ̄ptqu have the same update rule. Since θp0q “ θ̄p0q, this proves θptq “ θ̄ptq for all t.
Now we prove the second part of the theorem. Notice that L̃RDIλ pθq is a strongly convex quadratic function with Hessian ∇2θL̃RDIλ pθq “ řn i“1 φpxiqφpxiqJ ` λ2I “ ZZJ ` λ2I , where Z “ pφpx1q, . . . ,φpxnqq. From the classical convex optimization theory, as long as η ď 1}ZZJ`λ2I} “ 1 }ZJZ`λ2I} “ 1 }kpX,Xq}`λ2 , gradient descent converges linearly to the unique optimum θ ˚ of L̃RDIλ pθq, which can be easily obtained:
θ˚ “ θp0q `ZpkpX,Xq ` λ2Iq´1ỹ.
Then we have
φpxqJpθ˚ ´ θp0qq “ φpxqJZpkpX,Xq ` λ2Iq´1ỹ “ kpx,XqJ ` kpX,Xq ` λ2I ˘´1 ỹ,
finishing the proof.

heading: C MISSING PROOFS IN SECTION 5

text:
C.1 PROOF OF THEOREM 5.1
Define εi “ ỹi ´ yi (i P rns), and ε “ pε1, . . . , εnqJ “ ỹ ´ y. We first prove two lemmas.
Lemma C.1. With probability at least 1´ δ, we have g
f
f
e
n ÿ i“1 pf˚pxiq ´ yiq2 ď λ 2 b yJpkpX,Xqq´1y ` σ 2λ a trrkpX,Xqs ` σ a 2 logp1{δq.
Proof. In this proof we are conditioned onX and y, and only consider the randomness in ỹ given X and y.
First of all, we can write
pf˚px1q, . . . , f˚pxnqqJ “ kpX,Xq ` kpX,Xq ` λ2I ˘´1 ỹ,
so we can write the training loss on true labels y as g
f
f
e
n ÿ i“1 pf˚pxiq ´ yiq2 “ › › › kpX,Xq ` kpX,Xq ` λ2I ˘´1 ỹ ´ y › › ›
“ › › › kpX,Xq ` kpX,Xq ` λ2I ˘´1 py ` εq ´ y › › ›
“ › › › kpX,Xq ` kpX,Xq ` λ2I ˘´1 ε´ λ2 ` kpX,Xq ` λ2I ˘´1 y › › ›
ď › › › kpX,Xq ` kpX,Xq ` λ2I ˘´1 ε › › › ` λ2 › › › ` kpX,Xq ` λ2I ˘´1 y › › › .
(11)
Next, since ε, conditioned onX and y, has independent and subgaussian entries (with parameter σ), by (Hsu et al., 2012), for any symmetric matrixA, with probability at least 1´ δ,
}Aε} ď σ b trrA2s ` 2 a trrA4s logp1{δq ` 2}A2} logp1{δq. (12)
Let A “ kpX,Xq ` kpX,Xq ` λ2I ˘´1
and let λ1, . . . , λn ą 0 be the eigenvalues of kpX,Xq. We have
trrA2s “ n ÿ
i“1
λ2i pλi ` λ2q2 ď n ÿ
i“1
λ2i 4λi ¨ λ2 “ trrkpX,Xqs 4λ2 ,
trrA4s “ n ÿ
i“1
λ4i pλi ` λ2q4 ď n ÿ
i“1
λ4i
44λ2 ` λi 3
˘3 ď trrkpX,Xqs
9λ2 ,
}A2} ď 1.
(13)
Therefore,
›
› › kpX,Xq
` kpX,Xq ` λ2I ˘´1 ε › › › ď σ
d
trrkpX,Xqs 4λ2 ` 2 c trrkpX,Xqs logp1{δq 9λ2 ` 2 logp1{δq
ď σ ˜ c
trrkpX,Xqs 4λ2 ` a
2 logp1{δq ¸ .
Finally, since ` kpX,Xq ` λ2I ˘´2 ĺ 14λ2 pkpX,Xqq ´1 (note pλi ` λ2q2 ě 4λi ¨ λ2), we have
λ2 › ›
›
` kpX,Xq ` λ2I ˘´1 y › › › “ λ2
b
yJ pkpX,Xq ` λ2Iq´2 y ď λ 2
b
yJpkpX,Xqq´1y. (14)
The proof is finished by combining (11), (13) and (14).
Let H be the reproducing kernel Hilbert space (RKHS) corresponding to the kernel kp¨, ¨q. Recall that the RKHS norm of a function fpxq “ αJkpx,Xq is
}f}H “ b αJkpX,Xqα.
Lemma C.2. With probability at least 1´ δ, we have
}f˚}H ď b yJ pkpX,Xq ` λ2Iq´1 y ` σ λ ´? n` a 2 logp1{δq ¯
Proof. In this proof we are still conditioned on X and y, and only consider the randomness in ỹ given X and y. Note that f˚pxq “ αJkpx,Xq with α “ ` kpX,Xq ` λ2I ˘´1
ỹ. Since `
kpX,Xq ` λ2I ˘´1 ĺ pkpX,Xqq´1 and ` kpX,Xq ` λ2I ˘´1 ĺ 1λ2 I , we can bound
}f˚}H “ b ỹJ pkpX,Xq ` λ2Iq´1 kpX,Xq pkpX,Xq ` λ2Iq´1 ỹ
ď b py ` εqJ pkpX,Xq ` λ2Iq´1 py ` εq
ď b yJ pkpX,Xq ` λ2Iq´1 y ` b εJ pkpX,Xq ` λ2Iq´1 ε
ď b yJ pkpX,Xq ` λ2Iq´1 y ` ? εJε
λ .
Since ε has independent and subgaussian (with parameter σ) coordinates, using (12) with A “ I , with probability at least 1´ δ we have
? εJε ď σ ´? n` a 2 logp1{δq ¯ .
Now we prove Theorem 5.1.
Proof of Theorem 5.1. First, by Lemma C.1, with probability 1´ δ{3, g
f
f
e
n ÿ i“1 pf˚pxiq ´ yiq2 ď λ 2 b yJpkpX,Xqq´1y ` σ 2λ a trrkpX,Xqs ` σ a 2 logp3{δq,
which implies that the training error on the true labels under loss function ` is bounded as
1
n
n ÿ i“1 `pf˚pxiq, yiq “ 1 n n ÿ i“1 p`pf˚pxiq, yiq ´ `pyi, yiqq
ď 1 n
n ÿ i“1 |f˚pxiq ´ yi|
ď 1? n
g f
f
e
n ÿ i“1 |f˚pxiq ´ yi|2
ď λ 2
c
yJpkpX,Xqq´1y n ` σ 2λ
c
trrkpX,Xqs n ` σ c 2 logp3{δq n .
Next, for function class FB “ tfpxq “ αJkpx,Xq : }f}H ď Bu, Bartlett and Mendelson (2002) showed that its empirical Rademacher complexity can be bounded as
R̂SpFBq fi 1
n E
γ„t˘1un
«
sup fPFB
n ÿ i“1 fpxiqγi
ff
ď B a trrkpX,Xqs n .
By Lemma C.2, with probability at least 1´ δ{3 we have
}f˚}H ď b yJ pkpX,Xq ` λ2Iq´1 y ` σ λ ´? n` a 2 logp3{δq ¯ fi B1.
We also recall the standard generalization bound from Rademacher complexity (see e.g. (Mohri et al., 2012)): with probability at least 1´ δ, we have
sup fPF
#
Epx,yq„Dr`pfpxq, yqs ´ 1
n
n ÿ i“1 `pfpxiq, yiq
+
ď 2R̂SpFq ` 3 c logp2{δq 2n . (15)
Then it is tempting to apply the above bound on the function class FB1 which contains f˚. However, we are not yet able to do so, because B1 depends on the dataX and y. To deal with this, we use a standard -net argument on the interval that B1 must lie in: (note that }y} “ Op ? nq)
B1 P ”σ
λ
´? n` a 2 logp3{δq ¯ , σ
λ
´? n` a 2 logp3{δq ¯ `O ´n
λ
¯ı
.
The above interval has length O ` n λ ˘ , so its -net N has size O ` n λ ˘
. Using a union bound, we apply the generalization bound (15) simultaneously on FB for all B P N : with probability at least 1´ δ{3 we have
sup fBPF
#
Epx,yq„Dr`pfpxq, yqs ´ 1
n
n ÿ i“1 `pfpxiq, yiq
+ ď 2R̂SpFBq `O ˜ c log n δλ n ¸ , @B P N .
By definition there exists B P N such that B1 ď B ď B1 ` . Then we also have f˚ P FB . Using the above bound on this particular B, and putting all parts together, we know that with probability at least 1´ δ, Epx,yq„Dr`pf˚pxq, yqs
ď 1 n
n ÿ i“1 `pf˚pxiq, yiq ` 2R̂SpFBq `O
˜
c
log n δλ n
¸
ď λ 2
c
yJpkpX,Xqq´1y n ` σ 2λ
c
trrkpX,Xqs n ` σ c 2 logp3{δq n
` 2pB1 ` q
a
trrkpX,Xqs n
`O ˜ c log n δλ n ¸
ď λ 2
c
yJpkpX,Xqq´1y n ` σ 2λ
c
trrkpX,Xqs n ` σ c 2 logp3{δq n
` 2 a trrkpX,Xqs n ˆ b yJ pkpX,Xqq´1 y ` σ λ ´? n` a 2 logp3{δq ¯ ` ˙ `O ˜ c log n δλ n ¸
“ λ 2
c
yJpkpX,Xqq´1y n ` 5σ 2λ
c
trrkpX,Xqs n ` σ c 2 logp3{δq n
` 2 a trrkpX,Xqs n ˆ b yJ pkpX,Xqq´1 y ` σ λ a 2 logp3{δq ` ˙ `O ˜ c log n δλ n ¸ .
Then, using trrkpX,Xqs “ Opnq and choosing “ 1, we obtain Epx,yq„Dr`pf˚pxq, yqs
ď λ 2
c
yJpkpX,Xqq´1y n `O ´σ λ ¯ ` σ c 2 logp3{δq n
`O
¨
˝
d
yJ pkpX,Xqq´1 y n
˛
‚`O ˆ σ
λ ? n
a 2 logp3{δq ˙ `O ˆ 1? n ˙ `O ˜ c log nδλ n ¸
ď λ`Op1q 2
c
yJpkpX,Xqq´1y n `O ˜ σ λ ` σ c logp1{δq n ` σ λ c logp1{δq n ` c log nδλ n ¸ .
C.2 PROOF OF THEOREM 5.2
Proof of Theorem 5.2. We will apply Theorem 5.1 in this proof. Note that we cannot directly apply it on tpxi, yi, ỹiqu because the mean of ỹi ´ yi is non-zero (conditioned on pxi, yiq). Nevertheless, this issue can be resolved by considering tpxi, p1´ 2pqyi, ỹiqu instead.4 Then we can easily check that conditioned on yi, ỹi ´ p1´ 2pqyi has mean 0 and is subgaussian with parameter σ “ Op ? pq. With this change, we are ready to apply Theorem 5.1.
Define the following ramp loss for u P R, ȳ P t˘p1´ 2pqu:
`ramppu, ȳq “
$
&
%
p1´ 2pq, uȳ ď 0, p1´ 2pq ´ 11´2puȳ, 0 ă uȳ ă p1´ 2pq 2, 0, uȳ ě p1´ 2pq2.
It is easy to see that `ramppu, ȳq is 1-Lipschitz in u for ȳ P t˘p1´2pqu, and satisfies `ramppȳ, ȳq “ 0 for ȳ P t˘p1´ 2pqu. Then by Theorem 5.1, with probability at least 1´ δ,
Epx,yq„D r`ramppf˚pxq, p1´ 2pqyqs 4For binary classification, only the sign of the label matters, so we can imagine that the true labels are from
t˘p1´ 2pqu instead of t˘1u, without changing the classification problem.
ď λ`Op1q 2
c
p1´ 2pqyJpkpX,Xqq´1 ¨ p1´ 2pqy n
`O ˜? p λ ` c p logp1{δq n ` c log nδλ n ¸
“ p1´ 2pqpλ`Op1qq 2
c
yJpkpX,Xqq´1y n
`O ˜? p λ ` c p logp1{δq n ` c log nδλ n ¸ .
Note that `ramp also bounds the 0-1 loss (classification error) as
`ramppu, p1´2pqyq ě p1´2pqIrsgnpuq ‰ sgnpyqs “ p1´2pqIrsgnpuq ‰ ys, @u P R, y P t˘1u.
Then the conclusion follows.
C.3 PROOF OF THEOREM 5.3
Proof of Theorem 5.3. By definition, we have Erỹi|cis “ Erepc̃iq|cis “ pci (the ci-th column of P ). This means ErỸ |Qs “ Q. Therefore we can viewQ as an encoding of clean labels, and then the observed noisy labels Ỹ isQ plus a zero-mean noise. (The noise is always bounded by 1 so is subgaussian with parameter 1.) This enables us to apply Theorem 5.1 to each f phq, which says that with probability at least 1´ δ1,
Epx,cq„D ˇ ˇ ˇ f phqpxq ´ ph,c ˇ ˇ ˇ ď λ`Op1q
2
c
pqphqqJpkpX,Xqq´1qphq n `O
¨
˝
1 λ `
d
log 1δ1 n ` c log nδ1λ n
˛
‚.
Letting δ1 “ δK and taking a union bound over h P rKs, we know that the above bound holds for every h simultaneously with probability at least 1´ δ.
Now we proceed to bound the classification error. Note that c R argmaxhPrKsf phqpxq implies řK h“1 ˇ ˇf phqpxq ´ ph,c ˇ ˇ ě gap. Therefore the classification error can be bounded as
Pr px,cq„D
” c R argmaxhPrKsf phqpxq ı
ď Pr px,cq„D
«
K ÿ
h“1
ˇ
ˇ ˇ f phqpxq ´ ph,c
ˇ
ˇ ˇ ě gap
ff
ď 1 gap Epx,cq„D
«
K ÿ
h“1
ˇ
ˇ ˇ f phqpxq ´ ph,c
ˇ
ˇ
ˇ
ff
“ 1 gap
K ÿ h“1 Epx,cq„D ” ˇ ˇ ˇ f phqpxq ´ ph,c ˇ ˇ ˇ ı
ď 1 gap
¨
˝ λ`Op1q 2
K ÿ
h“1
c
pqphqqJpkpX,Xqq´1qphq n `K ¨O
¨
˝
1 λ `
d
log 1δ1 n ` c log nδ1λ n
˛
‚
˛
‚,
completing the proof.

heading: D EXPERIMENT DETAILS AND ADDITIONAL FIGURES

text:
In Setting 1, we train a two-layer neural network with 10,000 hidden neurons on MNIST (“5” vs “8”). In Setting 2, we train a CNN, which has 192 channels for each of its 11 layers, on CIFAR (“airplanes” vs “automobiles”). We do not have biases in these two networks. In Setting 3, we use the standard ResNet-34.
In Settings 1 and 2, we use a fixed learning rate for GD or SGD, and we do not use tricks like batch normalization, data augmentation, dropout, etc., except the difference trick in Appendix A. We also freeze the first and the last layer of the CNN and the second layer of the fully-connected net.5
In Setting 3, we use SGD with 0.9 momentum, weight decay of 5ˆ 10´4, and batch size 128. The learning rate is 0.1 initially and is divided by 10 after 82 and 123 epochs (164 in total). Since we
5This is because the NTK scaling at initialization balances the norm of the gradient in each layer, and the first and the last layer weights have smaller norm than intermediate layers. Since different weights are expected to move the same amount during training (Du et al., 2018a), the first and last layers move relatively further from their initializations. By freezing them during training, we make the network closer to the NTK regime.
observe little over-fitting to noise in the first stage of training (before learning rate decay), we restrict the regularization power of AUX by applying weight decay on auxiliary variables, and dividing their weight decay factor by 10 after each learning rate decay.
See Figures 5 to 8 for additional results for Setting 2 with different λ’s.