Simple and Effective Regularization Methods for Training on Noisily Labeled Data with Generalization Guarantee
Authors: Wei Hu
Zhiyuan Li
Dingli Yu
Venue:  (2020)
Keywords: deep learning theory
regularization
noisy labels

Abstract: 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.

Published as a conference paper at ICLR 2020
SIMPLE AND EFFECTIVE REGULARIZATION METHODS FOR TRAINING ON NOISILY LABELED DATA WITH GENERALIZATION GUARANTEE
Wei Hu
Zhiyuan Li Dingli
Princeton University
(huwei, zhiyuanli, dingliyl (cs. www.specnnteeneiie.
ABSTRACT
Over-parameteriver deep neural networks trained by simple first-order methods are known be able to fit any labeling of data. Such over-fitting ability hinders gener- alization 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 regulariza- tion methods: (i) regularization by the distance between the network parameters to initialization, and (ii) adding trainable auxiliary variable to the network output for each training example. Theoretically, either of these two methods leads to 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 com- parable to the bound one can get when there is no label noise. Experimental results verify the effectiveness of these methods on noisily labeled datasets.
prove that gradient descent training with
INTRODUCTION
Modern deep neural networks trained in highly over-parameterrzze 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 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 early stopping, which has been observed to 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-I0 even when 60% of the training labels 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 step towards theoretical understanding of the generalization phenomenon for over- parameterized 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 0 the network parameters and by (0) its random initialization. This method adds regularizer À 0 0(0) 2 to the training objective.
2. Adding an auxiliary variable for each training example. Let x; be the i-th training example and f(e.-) represent the neural net. This method adds trainable variable b, and tries to fit the i-th label using f0, æ,) + Xb; At test time, only the neural net f(0, is used and the auxiliary variables discarded.

---

Published as a conference paper at ICLR 2020
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), 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 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 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 al., 2019a). In this line of work, parameters in 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 l 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 literature. This viewpoint makes explicit the connection between our methods and early stopping.
alternative to early stopping in kemell
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 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.
2 RELATED WORK
Neural langent 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; 201 8b; Li and Liang, 2018; Allen-Zhu et al., 201 Sa;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- wer-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 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), 8), using a pre-trained network (Jiang et al., 2017), and training two networks simultane- ously (Malach and
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 normal training procedure) and come with formal generalization guarantee.
2

---

Published as a conference paper at ICLR 2020
3 PRELIMINARIES
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 I| to denote the Frobenius norm of matrix. (.. represents the standard inner product. Let I be the identity matrix of appropriate dimension. Let [n] = 21, m).
Let [[[ be the indicator of event A.
3.1 SETTING: LEARNING FROM NOISILY LABELED DATA
Now we formally describe the setting considered this paper. We first describe the binary classifica- tion setting as 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 I x {+ where 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 (æ, y) DD and flip the sign of label y with probability p (0 E < } let y [+1] be the resulting noisy label.
Let ((.,, ū.));_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 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 Fd - R whose sign is used to predict the class, and thus the classification error of f on 'D is defined as Pr(a.w)DD(sg (sgnn + v].
Multi-class classification. When there are K classes (K > 2), let the underlying data distribution 'D be over I x [K]. We describe the noise generation process entry Pe is the probability that the label e is transformed into d' (Ve, d' E [K]. Therefore the data generation process is: draw (x,c) D, and replace the label with from the distribution Pr[c= c'lc = Pe,c (Vé's E [K].
matrix P E IR whose
Let " be i..dd samples from the above process. Again we would like to learn neural net with low classification error on the clean distribution D. For K-way classification, it is common to neural net with K outputs, and the index of the maximum output is used to predict the class. Thus for f ddd RK its (top-1) classification error on D is Pr(m.e)-DlC & argmax o (x)], where (k) : Idd - R is the function computed by the h-th output of f.
As standard practice, a class label E [K] is also treated as its one-hot encoding e(e) (0,0,-.- ...... 0, 1......, 0) e TRK (the e-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 Pe.c > Pe,e for all + c', i.e., the probability that class label transformed into another particular label must be smaller than the label e being correct otherwise it is impossible to identify class correctly from noisily labeled data.
3.2 RECAP OF NEURAL TANGENT KERNEL
Now briefly and informally recap the theory of neural tangent kernel (NTK) (Jacot al., 2018; Lee et al., 2019; Arora et al., 2019a), which establishes the equivalence between training a wide neural net and kernel method.
We first consider a neural net with a scalar output, defined as f(O,an .x) E R, where E R is all the parameters in the net and æ: E IRd is the input. Suppose that the net is trained by minimizing the la loss over training dataset {( 3=) random initial parameters be (()), and the parameters be updated according to gradient descent on L(0). It is shown that the network is sufficiently wide'. the parameters @ will stay close to the initialization (0) during training so that the following first-order approximation is accurate:
Rdd I: L(O)= 1 >" (f(0, æx.) y;)² Let the
f(0, x) ~ f(((0), x) + (Ve ( x), A()))
(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 d( () = fef(O(0), x) for any x E Rdd. The right hand side in (1) is linear in 0. As a consequence, training on the la loss with gradient descent leads to the kernel regression solution
""Widhh" refers number of nodes in fully connected layer number of channels in convolutional layer.
3

---

Published as a conference paper at ICLR 2020
with respect to the kemee induced by (random) features Φ(x), which is defined as k(x, x') (Ø(x), ((x')> for x, E Rd. This kernel was named the neural tangent kernel (NTK) by Jacot et al. (2018). Although this kernel is random, is shown that when the network is sufficiently wide, this random kernel converges to a deterministic limit in probability (Arora et al., 9a). If we additionally let the neural net and its initialization be defined so that the initial output is small, i.e., f(0(0), x) x 0,2 then the network at the end of training approximately computes the following function:
x k(xx, X) (k(X, X)) y,
(2)
= where X = (Z),.... xn,) is the training inputs, y = (y1..... Yn) is the training targets, k(xz X) (k(2, 21),........ k(,,,,))) E IR",, and (xX, X) E R=** with (i. th entry being k(z,, 23))
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 neural net with K outputs, f(0, x), by minimizing the &g loss over a training dataset {( y:) c R x gk; ((O) = Σ If(O., ..) - y:1² 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 yr. Namely, the h-th output of the network computes the function
(z) = k( x) (k(X, x (h)
where (() R" whose i-th coordinate is the hith coordinate of ye-
4 REGULARIZATION METHODS
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 kernel ridge regression using the NTK.
We first consider the case of scalar target and single-output network. The generalization to multiple outputs is straightforward and is treated the end of this section. Given noisily labeled training dataset { (2; ū.) ]== C Rd x IR, let f(O,-) -) be a neural net to be trained. A direct, unregularized train- ing method would involve minimizing an objective function like ((O) Σm= (S(O, æx;) ".))" To prevent over- aver-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 pa- rameters e()) be randomly generated, and minimize the following regularized objective:
L
Σ (S x;) x.)²
X²
2 0 0(0))
Method 2: adding an AUXiliary variable for each training example (AUX). We add an auxiliary trainable parameter 6; R for each i e [n]. and minimize the following objective:
L L (0,b) 2
(J xx)) + Ab. =x)²
(4)
where = (b1,...,,,,) b,.) E R" 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: f(0, x) R f(((0), x) + Φ(x)T( (e- (0)). Recall that we have ((x) = (0))), æ) which induces the NTK k(æ, x²) = (Φ(x), ((x')). Also recall that we can assume near-zero initial output: [(0((), x) z 0 (see
Footnote 2). Therefore we have the approximation:
f(0,z) x) ~ ((x)
0(0)).
(5)
We 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... f(0,2) x)) L g x) >L2 9(2,,, æ): then initialize 0 and 6g to be the same (and still random); this ensures f() x) = 0 (vm) at initialization, while keeping the same value of (db())) Φ(x')> for both f and g. See more details in Appendix
Forr the theoretical results in this paper use lz loss. In Section 6 we will present experimental results of both &g loss and cross-entropy loss for classification.
4

---

Published as a conference paper at ICLR 2020
Under the approximation (5), it suffices to consider gradient descent on the objectives (3) and (4) using the linearized model instead:
T.RDI (0) 2
1
Σ ((x.) (0 ((0)) - 5.
+
10 -
LAUX(0, (0, b)
1 - (<())) (0- ((0)) + Xb- 51
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 learning rate 1j > Consider gradient descent on I.RDI with initializaatin (()):
0(t + 1) (t) - (o t= 0, 2,
(6)
and gradient descent on Ī.AUX (0, b) with initialization (0)) and b(0) 0:
0(0) (0). @ + 1) 0(1) vV (t()), b(t), = 0,1,
(7)
60) = 0, b(t + 1) = b(t) - 111,)_ ((11), b()), t 0, 0,1,
Then we must have ((t) (t) for all t. Furthermore, if the learning rate satisfies v & xxXXX)
then (0())} converges linearly limit solution 0* such that:
((x) T (0* (()) = k(xx, X) (k(X, + 22) V, Va,
where y -iI1-.., Vn) e R
Proof sketch. The proof is given in Appendix B. A key step is to observe 0(t) = 0(0)+ (b)(t)- <(æ:), from which we can show that (0(1) and (0(()) 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: I (*) k(x,, X)T (I:X,, X) + X²I) ÿ.
(8)
If no regularization were used, the labels ÿ would be fitted perfectly and the learned function would be k(x, X (k(x.)) ÿ (c.f. (2)). Therefore the effect of regularization is to add X to the kernel matrix, and (8) known as the solution to kernel ridge regression in kernel literature. In
Section 5, we give generalization bound of this solution on the clean data distribution, which is comparable the bound one can obtain even when clean labels are used in training.
Extension to multiple outputs. Suppose that the training dataset is ((x;, 9:)]
Rd R and the neural net f(0, x) has K outputs. On top of the vanilla loss = - [f((0. x.) - 9 the two regularization methods RDI and AUX give the following objectives similar to (3) and (4):
1 Σ |f(0, m.) 5.1
X²
T.R0I (0)
0 0(0)1
2
2
AUX (0, B) =
1 _ If x.) + Ab: 31 B
b.) Kxn
In the NTK regime, both methods lead to the kernel ridge regression solution at each output. Namely, letting Y (Ur,...: Un) e TR Kxn be the training target matrix and T(h) e R" be the h-th row of Y. at the end of training the h-th output of the network learns the following function:
(0h) (x) k( X) (k(X, X) + X²1) (h)) h [K].
(9)
5 GENERALIZATION GUARANTEE ON CLEAN DATA DISTRIBUTION
We show that gradient descent training noisily labeled data with regularization methods RDI or AUX leads to a generalization guarantee on the clean data distribution. As Section 4, we consider the NTK regime and let k(-,.) 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 in Appendix C.
5

---

Published as a conference paper at ICLR 2020
Theorem 5.1 (Additive label noise). Let D be distribution over B x 1-1.1]. Consider the following data generation process: (i) draw (x. y) ~ D, (it) conditioned on (x, y), let be drawn from a noise distribution En.y over R that may depend on and y. and (ii) let y + Suppose that E has mean O and is subgaussian with parameter a > 0, for any (x. y)-
Let {(x,, Vi. (:) be ii.dd samples from the above process. Denote X- = (z),.... Fn), y
(Ui,...;; :Bn) and y = (U1....;hh Noo) Consider the kernel ridge regression solution in (8): (x))
k(æ,, X) (x( A²1) y. Suppose that the kernel matrix satisfies trlk(X (X, X)] O()).
Then for any loss function É I. x IR - [0, 1] that is 1- 1-Lipschitz in the first argument such that
fly, v) 0. with probability at least 1 we have
B(GD)) ((()(())))
x 0(1)
3 (M(X, x))
+ +0 =0(2) +D
(10)
n
where A = =0 1
1og(1/8)
(o/(1/6))
log Ex
Remark 5.1. As the number of samples - 0O, we have A - O. In order for the second term O in (10) to go to O, we need to choose X to grow with n, e.g., X = 1e for some small constant
<> O. Then, the only remaining term in (10) worry about is 3/ "y' (x((xxXX)) 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 (V y (X(XXX
In comparison, we can see that even when there is label noise,
only lose a factor of O()) in the population loss on the clean distribution, which can be chosen as any slow- noowgrowing function of n. If (k(X, X, ;X))) grows much slower than n, by choosing an appropriate X, 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 gradi- ent descent can learn a class of smooth functions on the unit sphere. Their proof is by showing y (k( X, X O(1) if yk = g(x;) (Vi E [n]) for certain function 9, where k(,,,) ) is the NTK corresponding to two-layer ReI.U nets. Combined with their result, Theorem 5. 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 K-output neural net. Again, we use &g 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. Rd [=1} {+1} be i.i.d. samples from that process. Recall that Prí + Let [[z,, V/. G. 30)
milus = p < p < 4). Denote X (æI...., Rn)), y ..., Mn) and ÿ (VI..... Mn
Consider the kernel ridge regression solution in (8): f fxx) k(xxX) (k(X,X) + X2)
y.
Suppose that the kernel matrix satisfies tr[k(X, x)] Onn). Then with probability at least 1 the classification error of f on the clean distribution D satisfies
8.
Pr [sgn[] (5 (x=)) * v) < (w.))/-
A + 0(1)
y (k(X,
y
p plog
+
log n
5x
16
24
12
Theorem 5.3 (Multi-class classification). Consider the K-class classification setting stated in (,,,))))
Section 3.1. Let (( 1 c Rd x [K] x [K] be i.i.d. samples from that process. Recall that Pr[c;- = cc = cl pe,o (Vc, e [K],, where the transition probabilities form a matrix PE R K Let gap = din),.e(().oto (Pe,e c).
Let X= = (II..... In). and let ys =((a)) E RRK U. = e E RKK be one-hot label encodings. Denote Y -U1, (UI,...,y,. M,) E Kxn Y (ii..... .Un) RRKx,, and let ((t)) a R. be the h-th row
of Y. Define matrix Q
Kxnn and let ((h)) E BR" be the h-th row of Q.
Consider the kernel ridge regression solution in (9): f(h) Suppose that the kernel matrix satisfies tr[k(X (X, x)] = O()). Then with probability at least 1 8. the classification error of f (f( 1 on the clean data distribution D is bounded
-kxxx,,' X)T (k(X, X) + +xx11* (()).
6

---

Published as a conference paper at ICLR 2020
SCD+AUX
early stop GD+AUX GD+RDI
S00H+AUX
3.25
SCD
0.20
2.15
0.10
100
250
303
4.30
500
600
Spoch
(a) Test error vs. noise level for Setting 1. For each noise level, we do grid search for À and report the best accuracy.
(b) Training (dashed) & test (solid) errors vs. epoch for Setting 2. Noise rate = 20%. 4. Training enror of AUX is measured with auxiliary variables.
Figure 1: Performance on binary classification using lg loss. Setting I: MNIST; Setting 2: CIFAR.
c neg]
((h) (x))
(m,o)-
A+ (1)
( (1))
(h)
log n
log 3
KKK.
+
gap
n
n
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.
6 EXPERIMENTS
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 two-layer wide fully-connected net. Setting 2: Binary classification on CIFAR ("airplanes" vs. "automobiles") using 11-layer convolu- tional neural net (CNN).
Setting 3: CIFAR-I0 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, corrupted label is chosen uniformly from the other 9 classes.)
6.1 PERFORMANCE OF REGULARIZATION METHODS
For Setting (binary MNIST), we plot the test errors of different methods under different noise rates in Figure la We observe that both methods GD +UX and GD+RDI consistently achieve much lower test eтror than vanilla GD which over-fits the noisy dataset, and they achieve similar test eгror 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 (binary CIFAR), Figure 1b shows the learning curves (training and errors) of SGD, SGD+AUX and SGD+RDI for noise rate 20% and À = 4. Additional figures for other choices of Figure 5. We again observe that both SGD+AUP and SGD+RDI outperform vanilla SGD and are comparable to SGD with early stopping. We also observe discrepancy between SGD+AUX and SGD+RDI, possibly due to the noise SGD or the finite width.
Finally, for Setting 3 (CIFAR-10), Table shows the test accuracies of training with and without AUX. We train with both mean square error (MSE/f, loss) and categorical cross entropy (CCE) loss. For normal training without AUX, 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
7

---

Published as a conference paper at ICLR 2020
Nošse
0.4
0.6
Normal CCE (early stop)
94.05 10.07
89.73=0.44
86.45
79.13
Normal MSE (early stop)
03.8
89.9620.13
85.92+00332
78.08
CCE+AUX (last)
94.22:1..10
92.07
4-.31
0.260-0.229
CCE+AUX (hest)
94.30:40.09
92. 1.060.000
88.6140.14
82.91 +0222
MIE 0CC
MSE+AUX (last)
94,25 94,25 10.10
92.31 10118
88,92 10.30
83.90 0..30
MSE+AUX
94.3210.06
02.4
88.95
(Zhang and Sahuncu, 2018)
89,8
87.6240.26
82,70=0.25
330 329
Table I:
CIFAR-10 test accuracies of different methods under different noise rates.
Figure 2: Test accuracy during CIFAR-10 training (noise 0.4).
Distanne to Inirsalizztiin
Frobenius Norm
577.8
SGD
SCD-RD
6.
SGD+RD
577.6
SGD
SGD
0
200
400
600
200
400
600
Epoch
Figure 3: Setting 2, |W(0) Ir and [ (())()) 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 used as the loss function.
6.2 DISTANCE OF WEIGHTS TO INTIALIZATIIN,, VERIFICATION OF THE NTK REGIME
We also track how much the weights move during training as way see whether the neural is in the NTK regime. For Settings 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 shows in Setting 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 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.
samples
noise level
width
regularization strength
learning rate
Distance
Table 2: Relationship between distance to initialization convergence and other hyper- parameters. "/", positive correlation; "X": ": negative correlation; "-"; no correlation as long width is sufficiently large and learning rate sufficiently small.
CONCLUSION
Towards understanding generalization of deep neural networks in presence of noisy labels, this paper presents simple regularization methods and shows that they theoretically and empirically effective. The theoretical analysis relies on the correspondence between neural networks and NTKSs. We believe that 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 left for future work.
ACKNOWLEDGMENNS
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.
8

---

Published as a conference paper at ICLR 2020
REFERENCES
Zeyuan Allen-Zhu, Yuanzhi Li, and Yingyu Liang. Learning and generalization in overparameterized neural networks, going beyond two layers. arXiv preprint urXiv:1811.04915 2018a.
Zeyuan Allen-Zhu, Yuanzhi Li, and Zhao Song. convergence theory for deep learning via over- parameterization. arXiv preprint
2018b.
Sanjeev Arora, Simon S Du, Wei Hu, Zhiyuan Li, Ruslan Salakhutdinov, and Ruosong Wang. On exact computation with an infinitely wide neural net. arXiv preprint arXiv: 11955, 2019a.
Sanjeev Arora, Simon Du, Wei Hu, Zhiyuan Li, and Ruosong Wang. Fine-grained analysis of optimization and generalization for overparameterized two-layer neural networks. arXiv preprint arXiv:190..0888, 2019b.
Peter L Bartlett and Shahar Mendelson. Rademacher and gaussian complexities Risk bounds and structural results. Journal of Machine Learning Research, 3(Nov):463-482 2002.
Frank Bauer, Sergei Pereverzev, and Lorenzo Rosasco. On regularization algorithms in learning theory. Journal of complexity, 23(1):52-72 2007.
Yuan Cao and Quanquan Gu. A generalization theory of gradient descent for learning over- parameterized deep relu networks. arXiv preprint /rXiv:/902.0138x 2019.
Lenaic Chizat and Francis Bach. A note lazy training in supervised differentiable programming. arXiv preprint arXiv:1812.07955 2018.
Simon S Du, Wei Hu, and Jason D Lee. Algorithmic regularization in learning deep homogeneous models: Layers are automatically balanced. Advances in Neural Information Processing Systems 31, pages 382-393, 2018a.
Simon S Du, Jason D Lee. Haochuan Li, Liwei Wang, and Xiyu Zhai. Gradient descent finds global minima of deep neural networks. arXiv preprint arXiv: 18/1:///..0 1.03844, 2018b.
Simon Du, Kangcheng Hou, Barnabás Póczos, Ruslan Salakhutdinov, Ruosong Wang, and Keyulu Xu. Graph neural tangent kernel: Fusing graph neural networks with graph kernels. arXiv preprint 1rXiv: 13192, 2019a.
Simon S. Du, Xiyu Zhai, Barnabas Poczos, and Aarti Singh. Gradient descent provably optimizes peeattrraeteri neural networks, In International Conference Learning Representations, 2019b.
Lo Gerfo, Lorenzo Rosasco, Francesca Odone, E. De Vito, and Alessandro Verri. Spectral algorithms for supervised learning. Neural Computation, 20(7):1873- 1897, 2008.
Aritra Ghosh, Himanshu Kumar, and PS Sastry. Robust loss functions under label noise for deep neural networks. In Thirty-First AAAI Conference on Artificial Intelligence, 2017.
Melody Y Guan, Varun Gulshan, Andrew M Dai, and Geoffrey E Hinton. Who said what: Modeling individual labelers improves classification. In Thirty-Second AAAI Conference on Artificial Intelligence, 2018.
Bo Han, Quanming Yao, Xingrui Yu, Gang Niu, Miao Xu, Weihua Hu, Ivor Tsang, and Masashi Sugiyama. Co-teaching: Robust training of deep neural networks with extremely noisy labels. In NeurlPS, pages 8527-8537, 2018.
Daniel Hsu, Sham Kakade, Tong Zhang, et al. A tail inequality for quadratic forms of subgaussian random vectors. Electronic Communications Probability, 17, 2012.
Arthur Jacot, Franck Gabriel, and Clément Hongler. Neural tangent kernel: Convergence and generalization in neural networks. arXiv preprint arXiv:1806 18t..07726.0 2018.
Lu Jiang, Zhengyuan Zhou, Thomas Leung, Li-Jia Li, and Li Fei-Fei. Mentornet: Learning data-driven curriculum for very deep neural networks on corrupted labels. arXiv preprint /7t2://71..00000 2017.

---

Published as a conference paper at ICLR 2020
Ranjay A Krishna, Kenji Hata, Stephanie Chen, Joshua Kravitz, David A Shamma, Li Fei-Fei, and Michael S Bernstein. Embracing error to enable rapid crowdsoureing. In Proceedings of the 2016 CHI conference human factors in computing systems, pages 3167-3179. ACM, 2016.
Jachoon Lee, Lechao Xiao, Samuel S Schoenholz, Yasaman Bahri, Jascha Sohl-Dickstein, and Jeffrey Pennington. Wide neural networks any depth evolve as linear models under gradient descent. arXiv preprint arXiv: 190..0/22000000000 2019.
Mingchen Li, Mahdi Soltanolkotabi, and Samet Oymak. Gradient descent with early stopping is prov- ably robust to label noise for overparameterized neural networks. arXiv preprint arXiv: 1680, 2019.
Yuanzhi Li and Yingyu Liang. Learning overparameterized neural networks via stochastic gradient descent on structured data. arXiv preprint arXiv: / /804.0/204, 2018.
Tongliang Liu and Dacheng Tao. Classification with noisy labels by importance reweighting. IEEE
Transactions on paltern analysis and machine intelligence, 361) 2015.
Eran Malach and Shai Shalev-Shwards Decoupling" when to update" from" how to update". In Advances in Neural Information Processing Systems, pages 960-970, 2017.
Mehryar Mohri, Afshin Rostamizadch, and Ameet Talwalkar. Foundations of machine learning. MIT Press, 2012.
Vaishnavh Nagarajan and Zico Kolter. Generalization in deep networks: The role of distance from initialization. arXiv preprint arXiv:900.00162,, 2019.
Behnam Neyshabur, Zhiyuan Li, Srinadh Bhojanapalli, Yann LeCun, and Nathan Srebro. The role of pner-parametrization in generalization of neural networks. In International Conference Learning Representations, 2019.
Garvesh Raskutti, Martin Wainwright, and Bin Yu. Early stopping and non paraameaetticc regression: optimal data-dependent stopping rule. The Journal of Machine Learning Research, 15(1): 335-366, 2014.
Mengye Ren, Wenyuan Zeng. Bin Yang, and Raquel Urtasun. Learning to reweight examples for robust deep learning. arXiv preprint vrXiiv/8033.00 2018
David Rolnick, Andreas Veit, Serge Belongie, and Nir Shavit. Deep learning is robust to massive label noise. arXiv preprint arXiv: 10694, 2017.
Sainbayar Sukhbaatar, Joan Bruna, Manohar Paluri, Lubomir Bourdev, and Rob Fergus. Training convolutional networks with noisy labels. arXiv preprint arXiv: 2014.
Yuting Wei, Fanny Yang. and Martin J Wainwright. Early stopping for kernel boosting algorithms: A general analysis with localized complexities. In Advances in Neural Information Processing Systems, pages 6065-6075, 2017.
Greg Yang. Scaling limits of wide neural networks with weight sharing: Gaussian process behavior, gradient independence, and neural tangent kernel derivation. arXiv preprint AKK::1902.04766 2019.
Xingrui Yu, Bo Han, Jiangchao Yao, Gang Niu, Ivor Tsang, and Masashi Sugiyama. How does disagreement help generalization against label corruption? In International Conference on Machine Learning, pages 7 7164-7173, 2019.
Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning requires rethinking generalization. In Proceedings of the International Conference on Learning Representations (ICLR), 2017, 2017.
Zhilu Zhang and Mert Sabuneu. Generalized cross entropy loss for training deep neural networks with noisy labels. In NeurlPS, pages 8778-8788, 2018.
Difan Zou, Yuan Cao, Dongruo Zhou, and Quanquan Gu. Stochastic gradient descent optimizes over-parameterized deep ReI.U networks. arXiv preprint arXiv:181 1.8888, 2018.
10

---

Published as a conference paper at ICLR 2020
A DIFFERENCE TRICK
We give quick analysis of the "difference trick" deseribed in Footnote 2, i.e., let f(0. x2
x22 g( 02, æ) where 0 (01, 02), and initialize 0 and 02 to be the same (and still random). The following lemma implies that the NTKs for and the same.
2 9 x))
Lemma A.1. 1 (2) then
(i) S(0(0), Φ) 0, Va;;
(ii) (Vof(0(()) 2) 1 vo.((((0))))) Va, x'.
Proof. (i) holds by definition. For (ii), we can calculate that
vof(010,,2)
= vo.. + (vo,((000)) (V._))))))))))
2 (Va.((((00,2),v,0(((00.... 1
()).(()(0)),), |,gp::/0_0..0000000_000000000000 vo.00(0)))
= VVo.:00(0)=0,,,00000000111
The above lemma allows ensure output initialization while preserving NTK. As comparison, Chizat and Bach (2018) proposed the following "doubling trick": neurons in the last layer 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 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 O.
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 zero-mean Gaussian process, whose covariance matrix is equal to the NTK contributed by the gradients of parameters in its last layer. Therefore, learning 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.
GD+early stop
GD
Test error (%)
3.
0.0
0.1
0.2
0.3
0.4
0.5
Figure 4: Plot of test error for fully connected two-layer network on MNIST (binary classification between "5" and "8") with difference trick and different mixing coefficients where f() 02 x)) =
V (1) / V g( .)). Note that this parametrization preserves the NTK. The network has 10,000 hidden neurons and we train both layers with gradient descent with fixed learning rate for 5,000 steps. The training loss is less than 0.0001 at the time of stopping. We observe that when increases, the test error drops because the scale of the initial output of the network goes down.
11

---

Published as a conference paper at ICLR 2020
B MISSING PROOF IN SECTION 4
Proof of Theorem 4.1. The gradient of (0, can be written
VoLAUX (0, b) = _ 1= a,(() Vo, b) Aass i 1,,.....
where a, o(x,) ( 0(0)) + db, - 3u (i E [n]]. Therefore we have VoL (0, b) = E LA, (0, b) Φ(x)). Then, according to the gradient descent update rule (7), we know that 1() and b(l) always be related by ((1) ( En (1) ((x:). It follows that
O(t 1) 0()) " Σ (d(m:) (0(t) 0()) + (b,(1) 5.) ((x.))
=(() 7 Σ (ó(x:) (0(t) - 0(0)) ū.) ((x.) - y Σ b.(t)(((;)) O(() Σ (ω(m)) (0(t) ((0)) j.) ((x,) ()2(((())))))))))))))))))))))1 -(()))
On the other hand, from (6) we have
( + = ((1) Σ
- - ū:) d(m)) 7)²(((()) 0(0))
Comparing the above equations, find that (0(()) and (0(1) have the same update rule. Since 0(0) (0), this proves 0(1) = O()) for all I.
Now we prove the second part of the theorem. Notice that L (R) is a strongly convex quadratic
function with Hessian V ()) Σ (f=;))(((()))))))) ();;)) + x zz + I where Z (Φ(x1),.... ... (.x))) From the classical convex optimization theory, long 1 & ž
2 -+XI [xXX gradient descent converges linearly to the unique optimum 0 of
T.RD(()), (0), which can be easily obtained:
0 - - Z(k(X, X) + 1
Then have
<(x) (0* 0(0)) - x(x) 2 X) + X2T) 1 k(x, X) (K(X,)) + x21) -1 g.
finishing the proof.
C MISSING PROOFS IN SECTION 5
C.I PROOF OF THEOREM 5.1
Define E; 3: y/ (i [n]), and e = (E1)...,En) = 1 y.
We first prove two lemmas.
Lemma C.1. With probability at least have
A
(f*(x))
vi)² -1)) 2 V (
2X Virk((X, X)] + a 2og((1 1/8).
Proof. In this proof we are conditioned on X and y, and only consider the randomness in ÿ given X and y. First of all, we can write
(a1))..., k(X, X) -1 g.
12

---

Published as a conference paper at ICLR 2020
so we can write the training loss true labels y as
(f*()))) - -1)0== = [x(X (XXX, y
|A(X, ( (y+ E) -
3/
|A(X,X) (X(x,)x))xx
- 6-> [ + x -1
y/
< X) X) (X(X,))
e + x2 (k(X, X) + 22) y
(11)
Next, since E, conditioned on X and y, has independent and subgaussian entries (with parameter o). by (Hsu et al., 2012), for any symmetric matrix A, with probability at least
|Ee| 0 ur [r[A2]]+ 2 ir| A (1/6) log(8) + 2 42l log(1/0)
(12)
Let A- k(X, X) (k(X, X) + + -1 and let \1 , An 0 be the eigenvalues of k(X, X).
We have
n
X
X
[X]
tr[Aa] Σ
(); + 22)2
4); X
412
x
(13)
[r[A*] = Σ
(): 22)1
4 X2
A1
9X2
|A < 1.
Therefore,
(r[k(X, X)]
[rrk((X, X)] log(1/0) loggo()))
|Xx,, x
+ +2V
+olog(1/0)
412
912
trlk(X, X)]
2 1og((1/))
4X2
Finally, since (k(X,, X) + X21)
(k: X, X)) -1 (note (A, + 22)3 > 4h, X2), we have
< A
Xa (x(X + 1 = 2² L (X, x) + X31)
2 2 (xxXX X)) ... (14)
The proof is finished by combining (11), (13) and (14).
Let H be the reproducing kernel Hilbert space (RKHS) corresponding to the kernel k(.)). Recall that the RKHS norm of a function f(x)= = a k(x,, X) is
1sl VaTk(X, X)a.
Lemma C.2. With probubility at least 8, we have
|s VV V (k(x, x) - y A (Vr+ log(11)))
Proof. In this proof we are still conditioned on X and y, and only consider the randomness in ÿ given X and y. Note that (x) α T(z x) with (k(X X) + X²1) -1
y. Since
(A(X,)) + x21) (k(X,))) and (A(X X x31) I L1 we can bound
| H = V ET (k( X) + X²1) k X X) (k(X, X) x1 ū
$ + T (k( X, X) + x21 ee)
13

---

Published as a conference paper at ICLR 2020
V y (k(X, (-1) y + Ve' (M X) + x²1)
y VETE
< (k(X,
Since e has independent and subgaussian (with parameter a) coordinates, using (12) with A = I, with probability at least
δ have
VETE < (vi+ (2log(1/6))
Now we prove Theorem 5.1.
Proof of Theorem 5.1. First, by Lemma C.1, with probability 1 18/3,
X Σ (s*(a)) - vi)²
2 (x)x, 2A tr X)] + ov log(33 (3/))
which implies that the training error on the true labels under loss function l bounded as
Σ ((f* =
(e( ff (x:)) v.) E(vr. v.))
f (x,)) Vil
n
a
| (2x.) -vil2
m
$ y (k{ (,,(xX))
A 2
x))-1y
a
tr X, X)]
+ log (l/(3/5)
+ 2A
Next, for function class FB (f(x) = a k(æ, X): showed that its empirical Rademacher complexity can be bounded as
Ifl B), Bartlett and Mendelson (2002)
B Bv
(
E
sup
11 1=13=
feFn
By Lemma C.2, with probability least 1 8/3 we have
| H V y (k(X, + X²1
(V++ 2 2log(3300) B¹.
We also recall the standard generalization bound from Rademacher complexity (see e.g. (Mohri et al., 2012)): with probability least 1 - 8, we have
1 3 Σ (f(2))) vi) & 2Rs(())+ +3/ n
log log(2/0) 2n
sup feF
(15)
Then is tempting to apply the above bound on the function class FB. which contains f*. However, are not yet able to do so, because B' depends the data X and y. To deal with this, we use standard e-net argument on the interval that B' must lie in: (note that | = O(vn))
B'e 1 (vn+ 22log(3/8) A (Vn+ 2log(33/8) O 1
The above interval has length O (H), its e-net / has size O (.) Using union bound, apply the generalization bound (15) simultaneously on FB for all B E N: with probability at least 8/3 have
((ey)~D((((())) v) -111 Σ {(((z)) vi) < (F)) +0 (V
log FiX
sup fBEF
VBEN.
14

---

Published as a conference paper at ICLR 2020
By definition there exists B E A such that B' & B & B' + Then also have f E FB. Using the above bound on this particular B, and putting all parts together, we know that with probability at least 1 5,
E ( D(()
log n cd
(1:)) + 2Rs(RR +0
y (k(X X X) y
trik( X, x))
2 log (3/0)
2
"
2X
"
1
2(B' + e) krlk(A x]]
log aox
+0
n2
y' (T((( X, x))
(r[k(XXX)
2 2ogg (3/6)
oo
2
n1
2A
2 [H,
(VUT (K( X, x)) y d
(vn + v 1og(3188
+ + +
V
log cox
n2
A
y ( x
50
tr[k(X,
2 1lo((3/0)
+ toV
2
n
2A
n
n
2 trlk(X,X) X)]
log n rai
(3/((3 +e) 2
+ 0
x
Then, using tr (r[,(X, X)] (n) and choosing c = 1, we obtain
E B( ~ D p[((f* (f)((z))))) v)1
A
y (k(X, x
2 2lg((3
+ +0 ( + v
2
71
+0
T (k(X, y
+0
o
V 1l0((3/0)
(+)) nn
1
+
log 11
Avn n
11.
A + O
y (R: X, X))
y
log(1/8)
log(110)
log
+0 A
+ tov
2
n
n
n
n2
C.2 PROOF OF THEOREM 5.2
Proof of Theorem 5.2. We will apply Theorem 5.1 this proof. Note that we cannot directly apply it on {(x,, Wes 31 because the mean of ū: y/ is non-zero (conditioned on (æ, v:)). Nevertheless, this issue can be resolved by considering {(x,, (1 2p)y;, ÿ.)] instead.* Then we can easily check that conditioned on ys. V. (1 2p)y has mean 0 and is subgaussian with parameter O( With this change, we are ready to apply Theorem 5.1.
Define the following ramp loss for E R E (= 2p)}:
(1 2p),
uÿ < 0, 0 < ujj < (1 21=2p)² uy > (1 - 2
gramp (u. 7) =
(1 2p)
1 wy,
1-2p
0.
is easy to see that gramp (u, y) is 1-Lipschitz in u for y (+(1+ 2p) and satisfies gramp (j, 77) =
for ÿ (+(1= - 2p)). Then by Theorem 5.1, with probability at least 1 8,
B( gramp (f (x), (1 2p)
"For binary classification, only the sign of the label matters, can imagine that the true labels are from (+(1 2p)} instead of (+1}, without changing the classification problem.
15

---

Published as a conference paper at ICLR 2020
(1 O
yp)y ;
2p)y
vP
p plog(1/0)
log 83
2
Th
A
7
n
2p) + 0(1))
y (kl X, X)
y
vD
p plog
log
2
72
n
72
Note that gramp also bounds the 0-1 loss (classification error) as @ramp(u, (u (1- 2p)y) e (1 (1- 11-)p)[(ssgu(u) & sgn(y)] = (1- 2p)l(sgu((u) # y].
Vue Re (+1).
Then the conclusion follows.
C.3 PROOF OF THEOREM 5.3
Proof of Theorem 5.3. By definition, we have E[u = B[e(@i)/c] = Pe, (the 4--th column of P). This means E [] Q. Therefore we can view Q as encoding of clean labels, and then the observed noisy labels Y is Q plus 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 ((h), which says that with probability at least 8',
((,,)) (x) Ph.o < + O()) O(L) 2
(qth) (k(X, -2 (h)
log n
log 8x
n
Letting 8' = and taking union bound over h [K]. we know that the above bound holds for every h simultaneously with probability at least 1 - 6.
Now we proceed to bound the classification error. Note that & argmax ( E (x) - Ph.el e gap. Therefore the classification error can bounded as
(x)
(x) implies
Pr
c nrg
Pr (a,c)~>
(())()) Ph.c gap
(#,c)>D
(1) (x:) Ph.c
E (a) -D (((0)(2)) -hh.
(o,0)~D
gap
gap
+ 0()) K
(h(h)) (k(X, X)) (h)
log
log 8
+ K.
d +
+
gap
h=1
completing the proof.
D EXPERIMENT DETAILS AND ADDITIONAL FIGURES
In Setting I, train two-layer neural network with 10,000 hidden neurons on MNIST ("55 "8"). In Setting 2, we train CNN, which has 192 channels for each of its 11 layers, 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 fixed learning rate for GD 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 x 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
'This is because the NTK scaling at initialization balances the norm of the gradient each layer, and the first and the last layer weights have smaller norm than intermediate layers. Since different weights are expected 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 the NTK regime.
16

---

Published as a conference paper at ICLR 2020
observe little werr-ftttng to noise in the first stage of training (before learning rate decay), restrict the regularization power 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 X's.
SGD+AUX
SGD+AUX
0.30
SGD+RDE
0.30
SGD+RDI
SGD+AUX
SGD+AUX
0.25
SGD+RDI
0.25
SGD+RDI
0.20
SGD
0.20
SGD
0.10
0.10
0.05
0.05
0.00
0.00
100
200
300
400
300
600
100
200
400
Epach
Epach
(a) \ 0.25
(b) 0.5
0.35
0.35
SGD+AUX
SGD+AUX
0.30
0.30
SGD+AUX
SGD+AUX
SGD+RDI
SGD+ RDI
SGD
SGD
0.20
SGD
0.20
SGD
0.15
0.15
0.10
0.10
0.05
0.05
100
200
300
400
500
600
0
100
200
300
400
500
600
Epach
Epech
(c) A =1
(d) =
SGD+AUX
SGD+AUX
0.30
SGD+ RDI
0.30
SGD+RDI
SGD+AUX
SGD+AUX
0.25
SGD+RDI
0.25
SGD
SGD
0.20
SGD
0.20
SGD
0.15
0.15
0.05
0.05
0.00
0.00
300 8poch
400
300
600
100
200
400
500
Spach
(e) A
(f) A
Figure 5: Training (dashed) & test (solid) errors vs. epoch for Setting 2. Noise rate 20%,
E {0.25, 0.5, 1, 2, 4, 83. Training error of AUX is measured with auxiliary variables.
17

---

Published as a conference paper at ICLR 2020
Distance Initialization
Frobenius Norm
575.4
10.0
575.2
SGD+AUX S SGD
7.5
SGD+AUX
SCD+RDI RDI
575.0
SGD
574.8
2.5
0.0
200
400
600
200
100
600
Epoch
Epoch
Figure 6: Setting |W F and [W (O)()) during training. Noise 20%, 4.
S77.7
Distance Initialization
Prabenies Norm
SCD-ALX
577.5
SCD
577.4
SCD-AUX
SGD
300 Epoch
400
300 Epoch
400
500
Figure 7: Setting 2, (())) and (W(4) (0)) during training. Noise rate 0, A 2.
@
Disaace to Initial lizatin
575.0
Proberius Norm
SCD+ALX
SGD
374.8
SGD+AUX SGD
574.7
300 Epoch
400
200
300 Egoch
400
500
Figure 8: Setting 2, ( and (T) (0)] during training. Noise rate 0, A
18


Reviews:
[{"review_id": "S1xDkcCjtB", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "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.\n\nOverall, the paper is very well-organized and well-written. The contribution of the paper is significant, and numerical results also vindicate the theory developed in the manuscript. I recommend accepting the paper.\n\nTwo minor questions that are not going to affect my rating:\n1. The theory developed in the paper depends highly on NTK. What if the network is not sufficiently wide (which is usually the case in practice), and the loss function is not L2?\n2. In the second method using the auxiliary variable, it seems that every training sample x_i needs a variable b_i. Is this going to cause any problem in practice if data augmentation is used?\n", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper."}, "extra_text": {}}, {"review_id": "S1gq-N_pYH", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "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).\n\nContributions:\n- Propose two simple regularization techniques for learning from a noisily labeled dataset.\n- Give generalization guarantees for these methods\n\nClarity:\nThe paper is well organized and easy to read.\n\nQuality:\nThe work is of good quality and is technically sound.\n\nSignificance:\nSince proposed methods are in some sense related to the early-stopping for the (stochastic) gradient descent, the developed theory is useful in understanding the generalization ability of over-parameterized neural networks falling into NTK-regime. Although an additive noise setting for the regression problem is rather common in statistical learning theory, an artificially flipped label setting for the classification problem may be new except for a few recent studies [Li+(2019)]. A result (Theorem 5.1) for the regression problem with the squared loss is not so surprising because the generalization error of gradient descent in a high-dimensional space (e.g., over-parameterized NNs) or an RKHS (i.e., infinite-dimensional model) has been well studied and the generalization error is composed of the (constant) variance and the distance between the model output and the true label. Thus, existing results of generalization error analyses for the regression are directly applied to bound the prediction error for clean labels. However, I basically like this paper and I think this paper makes a certain contribution to understanding the effect of over-parameterization.\n\nA few questions:\n- Usually, the regularization parameter goes to zero as the number of examples increases. Conversely, the regularization parameter in the proposed methods also increases. Could you explain why this difference happens?\n- In classification tasks, the original problem setting is recovered by setting $p=lamba=0$. However, the generalization bound by Theorem 5.3 is still affected by $\\lambda$. Is this theorem tight?\n\n-----\nUpdate: \nI thank the authors for the response. I have read the revised version of the paper and have confirmed an improvement of Theorem 5.2. I will keep my score. This paper is of good quality.", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "HJengQ5IYH", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "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.\n\nNumerical experiments are performed to verify that the proposed methods indeed helps over the baseline at fighting noisy labels. One weak point of the paper is that there is no comparison to any other methods designed to learn under noisy labels. Even though the paper states that the primary advantage of the proposed methods is simplicity, it would still be good to have some empirical comparison for reference.\n\nI like that the paper has a section to explicit check whether the neural networks used in the experiments are in neural tangent kernel regime. However, I'm not very sure how to interpret the scale of the Frobenius norm in the change of the weights. Maybe one alternative approach is to compare the difference between the two neural tagent kernel --- one defined by theta(0), and one defined by theta(t) after training. Alternatively, maybe the experiments can be carried out with recent techniques to perform learning directly on infinite width networks (e.g. https://arxiv.org/abs/1904.11955 ).", "extra_scores": {"experience_assessment": "I have published in this field for several years.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper studies the effect of various regularization techniques for dealing with noisy labels. In particular the authors study various regularization techniques such as distance from initialization to mitigate this effect. The authors also provide theory in the NTK regime. All reviewers have positive assessment about the paper and think is clearly written with nice contributions but do raise some questions about novelty given that it mostly follows the normal NTK regime. I agree that the paper is nicely written and well-motivated. I do not think the theory developed here fully captures all the nuances of practical observations in this problem. In particular, with label noise this theory suggests that test performance is not dramatically affected by label noise when using regularization or early stopping where as in practice what has been observed (and even proven in some cases) is that the performance is completely unaffected with small label noise. I think this paper is a good addition to ICLR and therefore recommend acceptance but recommend the authors to more clearly articulate the above nuances and limitations of their theory in the final manuscript.  
Decision: Accept (Poster)