Leveraging inductive bias of neural networks for learning without explicit human annotations
Authors: Fatih Furkan Yilmaz
Reinhard Heckel
Venue:  (2020)
Keywords: dataset construction
deep learning
candidate examples

Abstract: Classification problems today are typically solved by first collecting examples along with candidate labels, second obtaining clean labels from workers, 
and third training a large, overparameterized deep neural network on the clean examples. The second, labeling step is often the most expensive one as it requires manually going through all examples.
In this paper we skip the labeling step entirely and propose to directly train the deep neural network on the noisy raw labels and early stop the training to avoid overfitting.
With this procedure we exploit an intriguing property of large overparameterized neural networks: While they are capable of perfectly fitting the noisy data, gradient descent fits clean labels much faster than the noisy ones, thus early stopping resembles training on the clean labels.
Our results show that early stopping the training of standard deep networks such as ResNet-18 on part of the Tiny Images dataset, which does not involve any human labeled data, and of which only about half of the labels are correct, gives a significantly higher test performance than when trained on the clean CIFAR-10 training dataset, which is a labeled version of the Tiny Images dataset, for the same classification problem.
In addition, our results show that the noise generated through the label collection process is not nearly as adversarial for learning as the noise generated by randomly flipping labels, which is the noise most prevalent in works demonstrating noise robustness of neural networks.

Under review as a conference paper at ICLR 2020
LEVERAGING INDUCTIVE BIAS OF NEURAL NETWORKS FOR LEARNING WITHOUT EXPLICIT HUMAN ANNOTA- TIONS
Anonymous authors Paper under double-blind review
ABSTRACT
Image classification problems today are often solved by first collecting examples along with candidate labels, second obtaining clean labels from workers, and third training a large, overparameterized deep neural network on the clean examples. The second, manual labeling step is often the most expensive manually going through all examples. In this paper we propose to i) skip the man- ual labeling step entirely, ii) directly train the deep neural network the noisy candidate labels, and iii) early stop the training to avoid overfitting. With this pro- cedure we exploit an intriguing property of overparameterized neural networks: While they are capable of perfectly fitting the noisy data, gradient descent fits clean labels faster than noisy ones. Thus, training and early stopping on noisy labels resembles training on clean labels only. Our results show that early stop- ping the training of standard deep networks (such as ResNet-18) on subset of the Tiny Images dataset (which is obtained without any explicit human labels and only about half of the labels are correct), gives significantly higher test performance than when trained on the clean CIFAR-10 training dataset (which is obtained by labeling a subset of the Tiny Images dataset). In addition, our results show that the noise generated through the label collection process is not nearly adversarial for learning as the noise generated by randomly flipping labels, which is the noise most prevalent in works demonstrating noise robustness of neural networks.
as it requires
INTRODUCTION
Much of the recent success in building machine learning systems for image classification can be attributed to training deep neural networks large, humanly annotated datasets, such Ima- geNet (Deng et al. 2009) or CIFAR-10 (Torralba et al.) al.] (2088). However, assembling such datasets is time-consuming and expensive: Both ImageNet and CIFAR-10 were constructed by first searching the web for candidate images and second labeling the candidate images by workers to obtain clean labels instead of the noisy candidate ones. The first step already yields labeled examples, but the accuracy of those automatically collected, candidate labels is low: For example, only about half of the labels of the Tiny Images dataset constructed in the first step of obtaining the CIFAR- dataset are correct (Torralba et al. 2008). In the second step, clean labels are obtained by asking workers through a crowdsoureing platform for annotations and aggregating them.
In this paper we propose to train directly on the noisy candidate examples, effectively skipping the expensive human labeling step. To make this work, we exploit an intriguing property of large, overparameterized neural networks: If trained with stochastic gradient descent or variants thereof, neural networks fit clean labels significantly faster than noisy ones. This fact is well known, see for example the experiments by Zhang et al. (2017) Fig. la) which demonstrated that overparameterizee deep networks can fit even randomly shuffled CIFAR- 10 labels perfectly. What is now well known is that this effect is sufficiently strong enable training candidate labels only. Our idea is that, neural networks fit clean labels faster than noise, then training them on a set containing clean and wrong labels and early stopping the training resembles training on the clean labels only.

---

Under review as a conference paper at ICLR 2020
1.1 OUR CONTRIBUTIONS
We show that early stopping the training on candidate examples can achieve classification perfor- mance higher than when training on clean labels, provided the total number of clean labels in the candidate training set is sufficiently large (throughout this paper, we refer to the dataset that con- sists of the examples with the associated, noisy candidate labels-as obtained in the first step of the dataset construction process as the candidate dataset/candidate training set). This result questions the expensive practice of building clean humanly labeled training sets, and suggests that it can be better to collect larger, noisier datasets instead.
Specifically, we consider the CIFAR-10 classification problem, where the goal is to classify 32x32 color images in 10 classes. The clean training set consists of 5000 images per class and was obtained by labeling the images from the Tiny Images dataset with expert labelers. Instead of training on the original, clean training set, we train on new noisy training set consisting of candidate examples only. We constructed this candidate training set by picking the images from the Tiny Images dataset with the labels of the CIFAR-10 10 classes. Only about half of the examples in this candidate dataset are correctly labeled. We quantify performance on the new CIFAR-10. 10.1 test set from Recht et al.) (011)) We ensured by automatically and manually cleaning the training set that it contains no images that are similar to any of the images the CIFAR-10.1 test set.
We trained the best performing networks for CIFAR- 10, (ResNet (He et al. 2016 Shake- Shake (Gastaldi, 2017). VGG (Simonyan & Zisserman 2015), DenseNet (Huang et al., 2017) and others (Han et al. 2017 Liu et 2018)) and found that with early stopping the training we achieve significantly higher lest accuracy than when training on the original, clean examples. That is possi- ble, because even though the candidate dataset is very noisy, it contains more clean examples than the original CIFAR-10 10 training set, as additional experiments show.
More specifically, the best performing model trained on the original CIFAR-I0 10 training set has 7% classification error on the CIFAR-10.1 test set (Recht et al. 2019). The best performing model trained on candidate training set, in contrast, achieves the better error rate of only 5.85%, with early stopping training of the PyramidNet-110 11 model. This is a lower (better) test accuracy (as measured on the CIFAR-IO.1 dataset) than that achieved by any model trained on the clean CIFAR- 10 training set. What is more, all models we tested have a significant gap of training on the original clean and our noisy data. For example, the performance of ResNett-8 jumps from 85.2% 92.15% when training and early stopping on the noisy dataset instead of the clean one.
Early stopping critical achieve the best performance. By keeping track of the performance of a clean subset of the noisy training set, we show that the clean labels are fitted significantly faster than the noisy labels, and good point to stop is when most of the clean labels are fitted well by the network, because at this point most of the wrong labels have not been fitted yet.
We also study the difference between the "real" noise in the data obtained through the actual data collection progress (from sources such as search engines, like Tiny Images) and artificially generated noise through randomly flipping the labels of a clean dataset, which is often used in the literature as proxy for the former. We show that the "real" noise is more structured and therefore it is easier to fit and less harmful to the classification performance in contrast to artificially generated noise, which is harder to fit and potentially much more adversarial performance.
Finally, we show that our results continue to hold for other datasets. Specifically, we consider clas- sifying invertebrate animals from training on i) candidate dataset we collected from Flicker only through keyword search es and without subsequent labeling and from ii) a subset of the ImageNet. While for this experiment training on the candidate dataset does not improve over training on the clean set, early stopped gradient descent achieves performance close to that obtained when training on the clean set.
1.2 RELATED WORK
While our work focuses on exploiting the fact that large neural networks fit clean labels faster than noise, large number of related works have shown that neural networks are robust to label noise, both in theory and practice (Rolnick et al. (0177), and have proposed methods to make deep networks even more robust label noise (Sukhbaatar & Fergus 2014 Jindal al., 2016). Several other papers have
2

---

Under review as a conference paper at ICLR 2020
suggested loss function adjustments and re- re-weighting techniques for noise robust training (Zhang & Sabuncu 2018 Ren et al. 2018 Tanaka et al. 2018
Guan al. (2018) has demonstrated that the classification performance of deep networks remains almost constant when training on partly randomly perturbed MNIST (handwritten digits) training examples. A number of recent works have offered explanations for why deep neural networks fit structure in data before fitting noise or other complex patterns: Arpit et al. (2017) has shown that loss sensitivity of clean examples is different to noisy examples. Ma et al. (2018) demonstrated that DNNs model low-dimensional subspaces that match the underlying data distribution during the early stages of training but needs increase the dimensionality of the subspaces to fit the noise later in training. and finally et et al. (2019); AAroa et al. (2019) have attributed this in the over-parameterized case with the low-rank structure of the Jacobian at initialization. There are few works that have ex- ploited the fact that clean examples are fitted faster than noise, with three noteable exceptions being the paper by [Shen& & Sanghavi (2019) which achieved nobse-robus by proposing a iterative re- training scheme, (Sun et al. (2018) which proposed systematic early stopping, and Song et al. (2018) which trains networks with large learning rates and uses the resulting loss to separate clean from misslabeled examples. Li et al. 2019) provided the perhaps first theoretical justification for early stopping to achieve robustness, by showing that gradient descent with early stopping is provably robust label noise for overparameterized networks.
Next we note that, we have used the Tiny Images dataset as a source for obtaining (noisy) candidate examples; other works have used it source for augmenting the clean CIFAR-10 and CIFAR-100 datasets (Carmon et al. 2019 Laine & Aila 2016) for a semi-supervised learning setting.
Finally we note that most of the works on learning from noisy labels have used artificially generated noise on clean, baseline datasets for motivation, experimentation and as performance metrics. As discussed later in this paper, we find that the performance degradation resulting from overfitting the noisy data is significantly worse on such artificially generated noise, whereas overfitting to the true label noise is not nearly as detrimental. The reason is that the true label noise found in the Tiny Images dataset is highly structured and not adversarial.
DATASET COLLECTION AND PROBLEM SETUP
We construct a candidate training dataset for the CIFAR-10 classification problem, without any explicit human labeling effort. Our noisy training set is a subset of the 80 million Tiny Images dataset (Torralba et al., 2008). The Tiny Images dataset consists of 32x32 images obtained by searching for nearly 80, 000 query keywords or labels in the image search engines Google, Flickr, and others. This yields examples of the form (keyword, image), but the associated labels (keywords) very noisy, specifically only about 44% are correct (Torralba et al. 2008 Sec. III-B), and often an example image is completely unrelated to the label (keyword).
The goal of the CIFAR-10 10 classification problem is to classify 32x32 color images into the ten classes {airplane, automobile, bird, cat, deer, dog, frog, horse, ship, truck). J. The original, clean, training for the CIFAR-10 dataset was obtained by first extracting candidates from the noisy examples of the Tiny Images dataset for each of the ten classes based on the finely grained tiny- images keywords (for example, keywords for the class dog are: puppy, pekingese, chihuahua, etc., see (Recht et al., [2019] Table 6) for a complete list), and then labeling all of the so-obtained images by human experts (Krizhessky 2009). This gives a clean training set consisting of 5000 examples per class.
We construct a new and larger (by factor of about 10) noisy training set by simply taking the subset of the Tiny Images for the respective class according to the same finely grained Tiny Images keywords, without any further human labeling. This resembles a data collection process without any explicit human labeling or cleaning of the data.
In our experiments throughout this paper, test performance is measured on the CIFAR-10.1 test set from Recht et al. (2019). To ensure that our noisy training set does not overlap with the CIFAR- 10.1 test set in any way, we carefully removed all test images as well as images that are similar to test images from the noisy training set. Both is necessary because the extracted subset of the Tiny Images dataset contains many images that are similar to test images up to slight differences in color scale, contrast, original resolution, croppings, and watermarks. See Appendix AJon A details and
3

---

Under review as a conference paper at ICLR 2020
airplane
bird
cat
dog
ship
Figure 1: Randomly selected images from our noisy training set for some CIFAR- 10 classes. Each row corresponds to a class and contains 10 randomly selected images. Note that about half of the images (marked with a red rectangle) are completely unrelated the class and even to other classes.
examples of this non-trivial data cleaning process. We work with the CIFAR-10. 10.1 test set instead of the original CIFAR-10 10 test set because it contains fewer images (2000 instead of 10000), and thus made our manual data cleaning process faster. Both datasets share the same distributional propertics, and Recht al. 2019 Figure 1) found the test performance on both sets to be linearly related.
After removing the similar images, our noisy training set consists of the number of examples indi- cated in the table below. About half of the labels in the noisy training for an illustration. Also note that they are often completely unrelated and out of distribution-
wrong, Figure
example screenshot, picture of person, and wheel all assigned the label "dog".
plane 39k
auto
bird
cat
deer
dog
frog
horse
ship
trick
total
our candidate training set CIFAR training set
53k
35.5k
47.5k
38k
48k
33.5k
41.5k
46.5k
44k
426.5k
TRAINING ON A LARGE NOISY DATASET CAN BE BETTER THAN TRAINING ON CLEAN ONE
In this section, we show that the performance of deep network trained on clean examples can be matched or even bested if the same network is trained with early stopping on noisy candidate examples despite the many wrong labels as long there are sufficiently many clean labels in the noisy dataset. Our results show that this is due to neural networks fitting clean labels significantly faster than noise; specifically we observe that subset of training that has clean labels is fitted during the early stages of training and much faster than the overall training set. Thus, when stopped early, the network is a state similar to that obtained when only trained on the clean labels in the first place. This effect enables achieving classification performance by training on very noisy, potentially automatically collected candidate datasets that on par with the performance obtained by training on very clean, expert annotated datasets.
Figure depicts the training and test accuracy of training with stochactic gradient descent on our candidate dataset as well as on the clean CIFAR- 10 training dataset for ResNet-18 with default parameters, taken from the Pytorch GitHub repository (PyTorch)) The results show that when trained on the noisy dataset, the network achieves significantly better test performance than when trained on the clean dataset. Moreover, the best performance achieved when the network is early stopped at about 30 epochs. At this optimal early stopping point, essentially all the clean examples but only very few the noisy examples are fitted. This follows by noting that at about 30 epochs, the network achieves almost 100% training accuracy a clean subset of the noisy dataset, but only about 65% overall test accuracy at a false-label-rate of about 50%. As test set we used CIFAR- 10. and the clean subset of the training examples is the original CIFAR- 10 test set, which is by construction
4

---

Under review as a conference paper at ICLR 2020
candidate training set/ResNet
clean training set/ResNet
100
% accuracy
80
60
40
candidate training set/DenseNet
clean training set/DenseNet
100
accuracy
80
mn0
training
60
test
40
clean subset
100
200
300
50
100
epoch
epoch
Figure 2: Accuracy on the training set, test set throughout training of the ResNet- 18 and DenseNet- 110 (k=12) models on our training set (left) and original CIFAR-10 training set (right). For the experiment on our training set, also show the accuracy on subset of the training that is known to have clean labels and corresponds to CIFAR-10 test set.
subset of the candidate training set. In practice, the optimal stopping time be obtained in data driven way by monitoring the test performance on a small, clean subset of the data, and stopping close to 100% training accuracy is achieved on the clean subset of the data.
ResNet is sufficiently overparameterized to perfectly fit the training data, even the mislabeled ex- amples. However, clean data before the network reaches its capacity to fit the noisy labels and the training accuracy plateaus at about 80%, Figure
network with fewer parameters, such the DenseNet-110 (k=12) fits the
We observe this effect across a large number of standard and state-of-the-art models (see Ap- pendix B). In Table[]] we provide the main results for the models we have tested on both the original clean CIFAR-10 training set and our candidate training set. The reported accuracies correspond to the best ones achieved during training for each setup. We note that there a significant improvement in test performance across all models. We also observe that the number of parameters does not seem be directly related to the performance increase of the models.
Clean training accuracy
Noisy training accuracy
#Parameters
Gap
Shake-Shake- 2x64d
1.19-107
87.6
93.6
6
PyramidNet- 100 (a = 270)
2.85-107
87.5
94.15
6.65
DenseNet-BC-100 (k=12)
7.69-10s
85.25
91.35
6.1
ResNet-18 18
1.12-107
85.2
92.15
6.95
VGG-16 16
1.47-107
84.65
89.9
5.25
PNASNet
4.52-10
81.25
89.55
8.3
Table 1: Model accuracy (in percent) on the CIFAR- 10.1 test set when trained on the original CIFAR- 10 training set and our noisy training set. Number of parameters is the total trainable number of parameters of the model and gap is the difference between the corresponding accuracies of the two training sets.
5

---

Under review as a conference paper at ICLR 2020
100
50z= r=1
size=5000 m2
% Accuracy
80
six=50000
siz=5000, 1=
5iz=500,, 1=1
size=500, m=
60
500=5000 r3
500 5
500-500 10
40
0
0.2
0.4
0.6
0.8
fraction of clean images substituted with candidate ones
Figure 3: Average test performance of ResNet-18 18 for training on datasets with varying number of examples and noise level: The fraction 0 corresponds to a dataset entirely consisting of clean labels of the CIFAR-10 10 traing set; fraction 0.5, half of the clean images are substituted each with many images from the noisy dataset. The results show that that if the number of clean examples grows sufficiently fast with the noisy level, the test accuracy improves.
HOw CLEAN DO THE LABELS HAVE TO BE?
In the previous section we found that learning on the noisy data gives significantly better perfor- mance than training on the clean data. Next we demonstrate that this finding relies on the total number of clean labels that availablc-ii that number grows sufficiently fast with the noise level, then performance becomes increasingly better when training on the noisy training set.
We perform the following experiment to measure performance increasingly larger and noisier datasets. We start with the original CIFAR- 10 training set and gradually replace a fraction of it with 1,2, 3, 5, 10 times more images from the Tiny Images dataset. For example, if the fraction is 0.5 and r = 2, that means that the new, noisy dataset consists of 25.000 images of the original clean CIFAR-IO training set and of 50.000 noisy images from noisy training set. Increasing the fraction for some fixed value of r > 1 thus increase both the dataset size as well as the noise level. We did this experiment both in the regime of very few examples (500 per class) and many examples (5000 per class). Figure 3 depicts the results.
For 1, the total dataset size remains constant but becomes increasingly noisier. Thus the ef- fective number of clean examples in the noisy dataset becomes smaller as the fraction increases. Non- non-surprisingly, we observe that the test accuracy drops the noise increases. The curve for r 5 is more interesting: If we substitute one clean label with 5 noisy ones, then the test perfor- mance increases even though the noise level increases, because the total number of clean examples also grows sufficiently fast.
TRUE VERSUS SYNTHETIC LABEL NOISE
As mentioned in the introduction, a large number of papers has shown that neural networks fit randomly corrupted labels slower than clean noise (Zhang et al. 2017 Rolnick et al. 2017 Guan et al. 2018 Ma et al., 2018 Li et al. 2019) The experiments in those works are exclusively for noisy labels generated by randomly flipping the clean labels, which can be considered as in-distribution noise. As we see from Figure the 'true' label noise generated through the image collection process is very different that it contains lots of out-of-distribution images well as structured noise. For example, the keyword 'Mouser' used to query images for the cat class by CIFAR-10 yields mostly toy guns and listing images of an electronics distribution company and only few cat related images. Similarly. the keyword 'Tomcat' surprisingly yields only few cat related images as well. Most of the images are related to Java server implementations, the F-14 jet nicknamed Tomcat, and species of insects.
and/or that neural network are robust label
Such structured, "real" noise is easier to fit and less harmful to classification performance. To demonstrate this, take the original CIFAR-10 training set and perturb 45% % of the labels by uni-

---

Under review as a conference paper at ICLR 2020
candidate dataset
CIFAR- 10 shuffled labels
100 -1
% accuracy
80
60
40
training
test
0
20
40
60
80
100
120
20
40
60
80
100
120
epoch
epoch
Figure 4: Accuracy on the training set and test set throughout training of the ResNet- 18 model on 50, 000 image subset of our training set (left) and original CIFAR-10 50, 000 image training set with the labels permuted such that each class retains 55% clean labels (right).
formly flipping them. We then train on the so-obtained artificially perturbed dataset and a subset of our noisy dataset consisting of the same number of examples (5000 per class). This process ensures that the label error probability is approximately the same, but the distribution of the errors is very different. The results in Figure show that the data from our noisy dataset fitted significantly faster because the noise is more structured. Moreover, the results show that early stopping is impor- tant for both setups, but training until overfitting is not nearly as detrimental to the test performance for training the candidate dataset than the noisy one.
EXTENSIONS TO SUB-SET OF IMAGENET
The finding that it is possible to build a well-performing classifier by training and early stopping on noisy candidate dataset is not unique the CIFAR-I0 classification problem. In order to demonstrate this, we train a classifier for a subset of the popular ImageNet(Deng et al. (2009) dataset.
We randomly choose 15 classes out of the 61 classes belonging the family class invertebrates (any animal lacking backbone). In order to construct a noisy candidate set, we use the synsets of these classes as search keywords to obtain candidate images from Flickr. In order avoid any overlaps between the original ImageNet dataset and the candidate dataset, we restrict the search date to a 5-year period, from 2014-07-12 to 2019-07-12. We also search 4-month intervals at a time and restrict the maximum number of images from each interval in order to prevent any bias that might be a result of mass uploads from institutional and professional accounts. We do not filter or further label any of the images obtained from the Flickr searches, only resize them to 256x256, which is the size of the images in the ImageNet. The resulting candidate dataset consists of around 173k images across 15 classes. Note that this is extremly noisy dataset, the average accuracy of image search results from the internet is considered to be around 10% Torralba et al. (2008).
In Figure 5 we show the training and test accuracy of training with stochastic gradient descent candidate dataset obtained from Flickr as well as the subset of ImageNet training set corresponding the chosen 15 classes for the ResNet-18 model with default parameters. The results show that when trained on the candidate dataset, the model achieves a comparable test performance to when trained on the clean dataset. Moreover, there is a clear early stopping point (about 30 epochs) during the training on the candidate dataset where the best test performance is achieved. Our manual inspections of the candidate dataset reveal that the dataset is very noisy with falsely labeled images accounting to much more than half of all the images for each class. Moreover, large part of the falsely labeled images comes from uploads from few, but highly active accounts. This also hinders the independence of the noise distribution across different classes as there are few prominent sources of the noise, which in turn makes the noise more adversarial. This partly explains the high variance and lower test performance during the early steps of training on the candidate dataset. We note that in practice using more specific search keywords instead the ImageNet synsets can yield much better results.
7

---

Under review as a conference paper at ICLR 2020
candidate dataset
ImageNet dataset
80
% accuracy
60
40
training test
20
40
60
80
100
120
20
40
80
100
120
epoch
epoch
Figure 5: Accuracy on the training set, test throughout training of the ResNet-18 model our candidate training set (left) that was obtained from Flickr searches and original ImageNet training (right) for the classification problem consisting of 15 children classes of the parent class corre- sponding to invertebrate animals.
7 REGULARIZATION WITH EARLY STOPPING: APPEALING TO LINEAR MODELS
For understanding why highly overparameterized neural networks fit structure faster than noise, it helpful to appeal to linear models. Specifically, a number of recent works show that highly over- parameterized models behave like an associated linear model around the initialization, which in turn offers an explanation why neural networks fit structure faster than no structure (Li et al. 2019; Du al. 2019 2018 Arora al.) 2019). While the regime where those results hold extremely overparameterizee and thus might not be the regime in which those models actually operate (Chizat al. 2018). it can provide some intuition on the dynamies of fitting clean this section, we first briefly comment on those recent theoretical results and explain how they pro- vide intuition on why deep networks fit structured data faster than noise, and second, inspired by those explanations for linear models, we demonstrate that early stopping the training of non-deep overparameterized linear models enables learning from noisy examples as well.
noisy data. In
7.1 EXISTING THEORY FOR OVERPARAMETERIIAA MODELS
Consider a binary classification problem, and let fw: Rd + R be neural network with weights label. The output label associated with
W E R.N mapping d-dimensional features space example x is interpreted as belonging to class if fw (xx) is positive and as belonging to class -1 if fw(x) negative. Let {1) xi)...., (Hn, xx)} be a set of n many training examples. The network trained by minimizing the empirical loss
C(W) 1 (x)13
with gradient descent, where y = I. ynl are the labels of the examples and fw (X) = [fw (x.)...., fw. (x.)] are the predictions of the model. Let J (W) == be the Jacobian of the mapping from weights to outputs f: R. + R. and let E x be specific matrix that obeys ! E [J( (W,)) TT (W.)). where expectation is with respect the random initialization W.. For two-layer networks, a number of very recent works (Li et al. 2019 Du et al.) 2019 2018 2018) Arora al. 2019) have shown that gradient descent in close proximity around the initialization well approximated by gradient descent applied to the associated linear loss
Liinear W)=
] [...
J(W Wo) y/
From this, it follows that (see (Li al. 2019 Arora al. 2019)) that the prediction enoor after t iteration gradient descent with stepsize (provided that yt is not too large) is given by
yy fw. fw. (X)l
Σ ( 2 "((())(()))))))),)>) v.))?.
(I)
8

---

Under review as a conference paper at ICLR 2020
singular values
candidate dataset
clean dataset
-104
mi
training
2
de accuracy
test
0.8
0.6
0.4
0 mal
11100
1nd
0.2
10
10a
102
10a
10a
10a
10a
10
10
10
10a
10a
10c
10
index
iteration
iteration
Figure 6: Training a large random feature model on a subset of our candidate training set (middle) and the CIFAR-10 training set (right) with gradient descent. Singular values of the feature matrix (left) shows the low-rank structure for our candidate training set.
where V; are the cigenvectors and of are the eigenvalues of the matrix JJ", and 1 S 1/o max- Equation [T] shows that the directions associated with large cigenvectors are fitted significantly faster by gradient descent than directions associated with small eigenvalues. Thus labels vectors y that are well aligned with eigenvectors corresponding to large eigenvalues are fitted significantly faster than those corresponding to small eigenvalues. The eigenvalues and eigenvectors are determined by the structure of the network. turns out that for neural network the structure is such that the projection of correctly labeled data (i.e.. (v., y). for y set of correct labels) is much more aligned with directions associated with large eigenvalues of JJ than the projection of falsely labeled data (i.c., (Vs. y), for y set of falsely labeled examples). This suggests that for highly linear overparameterized models we expect to see similar dynamics in that for certain model structure fitted faster than noise-a a property that demonstrate in the next section.
7.2 NON-DEEP MODELS
Finally, we demonstrate that even with non-deep overparameterized models, clean labels are learned faster than noisy ones, and thus early stopping enables learning from (noisy) candidate examples. We consider a random feature model fitted with gradient descent and early stopped. The reason for considering a random feature model that such models can reach performances that are reasonably close to that of a neural network if the number of random features, and thus the size of the model, is sufficiently large.
We consider vundom-featur model as proposed in Coates et al. (2011). We first extract for each example random features through a one-layer convolutional network G with 4000 random filters, each of size 6 x 6. For each image x, this gives feature vector G(x) of size 72000. Consider a training set with N examples, and let E R xm be the feature matrix associated with the training set, and let Y E N x be the matrix containing the labels. Specifically, Y has one in the k-th position of the i-th row if the i-th training example belongs to the k-th class, E K}. In the training phase, we fit a linear model by minimizing the least-squares loss
((Z) = Y XZ
with gradient descent. Here, the matrix Z mm K specifies the model, along with the random featurizer (i.e., the random convolutional model). Given new example the model then assigns the label arg max; G.x)
We trained the model above on two datasets: clean dataset consisting of 500 examples for each class of the CIFAR-10 10 training set, and a candidate dataset consisting of 1500 examples for each class from our candidate dataset. We measure classification performance as done throughout on the CIFAR-10.1 test set. The results, shown in Figure 66 show that on the clean dataset, this model achieves essentially 100% training accuracy. On the noisy dataset, similarly for the deep net- works, early stopping improves performance in that the best performance is achieved at about 70,000 iterations of gradient descent, long before the best fit of the model is achieved.

---

Under review as a conference paper at ICLR 2020
REFERENCES
Sanjeev Arora, Simon S. Du, Wei Hu, Zhiyuan Li, and Ruosong Wang. Fine-grained analysis of op- timization and generalization for overparameterizzed two-layer neural networks. In International Conference Machine Learning (ICML), 2019.
Devansh Arpit, Stanislaw Jastrzkebski, Nicolas Ballas, David Krueger, Emmanuel Bengio, Maxin- der S. Kanwal, Tegan Maharaj, Asja Fischer, Aaron Courville, Yoshua Bengio, and Simon Lacoste-Julies closer look at memorization in deep networks. In International Conference on Machine Learning (ICML), 2017.
Yair Carmon, Aditi Raghunathan, Ludwig Schmidt, Percy Liang, and John C Duchi. Unlabeled data improves adversarial robustness. arXiv:190S.13736 2019.
Lenaic Chizat, Edouard Oyallon, and Francis Bach. On lazy training in differentiable programming. arXiv:1812.0790 2018.
Adam Coates, Andrew Ng. and Honglak Lee. An analysis of single-layer networks in unsupervised feature learning. In Conference on Artificial Intelligence and Statistics (AISTATS), 2011.
Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei. Imagenet: A large-scale hierarchical image database. In Conference on Computer Vision and Puttern Recognition (CVPR), 2009.
Simon Du, Jason Lee, Haochuan Li, Liwei Wang, and Xiyu Zhai. Gradient descent finds global minima of deep neural networks. In International Conference on Machine Learning (ICML), 2019.
Simon S. Du, Xiyu Zhai, Barnabas Poczos, and Aarti Singh. Gradient descent provably optimizes over-parameterized neural networks. In International Conference on Learning Representations (ICLR), 2018.
Xavier Gastaldi. Shake-shake regularization. arXiv:1705.07485. 2017.
Melody Y Guan, Varun Gulshan, Andrew M Dai, and Geoffrey Hinton. Who said what: Modeling individual labelers improves classification. In Conference on Artificial Intelligence (AAAI), 2018.
Dongyoon Han, Jiwhan Kim, and Junmo Kim. Deep pyramidal residual networks. In Conference on Computer Vision and Pattern Recognition (CVPR), 2017.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recog- nition. Conference on Computer Vision and Pattern Recognition (CVPR), 2016.
Gao Huang, Zhuang Liu, Laurens Van Der Maaten, and Kilian Q Weinberger. Densely connected convolutional networks. Conference on Computer Vision and Pattern Recognition (CVPR), 2017.
Ishan Jindal, Matthew Nokleby, and Xuewen Chen. Learning deep networks from noisy labels with dropout regularization. In International Conference Data Mining (ICDM), 2016.
Alex Krizhevsky. Learning multiple layers of features from tiny images, 2009, https:// /twp:://ww. cs. aatpottt.ecc//tttiii/aaaaannnnee
pdf
Samuli Laine and Timo Aila. Temporal ensembling for semi-supervised learning. 1610.02242, 2016.
arXiv:
Mingchen Li, Mahdi Soltanolkotabi, and Samet Oymak. Gradient descent with early stopping is provably robust to label noise for overparameterized neural networks. arXiv: 1903. 1680, 2019.
Chenxi Liu, Barret Zoph, Maxim Neumann, Jonathon Shlens, Wei Hua, Li-Jia Li. Li Fei-Fei, Alan Yuille, Jonathan Huang, and Kevin Murphy. Progressive neural architecture search. In European Conference Computer Vision (ECCV), 2018.
10

---

Under review as a conference paper at ICLR 2020
Xingjun Ma, Yisen Wang, Michael E. Houle, Shuo Zhou, Sarah Erfani, Shutao Xia, Sudanthi Wi- jewickrema, and James Bailey. Dimensionality-dmin drivvn learning with noisy labels. In International Conference Machine Learning (ICML), 2018.
PyTorch. Pytorch examples.
master/ hirr//maaagneett
Benjamin Recht, Rebecca Roelofs, Ludwig Schmidt, and Vaishaal Shankar. Do imagenet classifiers generalize to imagenet? In International Conference on Machine Learning (ICML), 2019.
Mengye Ren, Wenyuan Zeng, Bin Yang, and Raquel Urtasun. Learning to reweight examples for robust deep learning. In International Conference Machine Learning (ICML), 2018.
David Rolnick, Andreas Veit, Serge Belongie, and Nir Shavit. Deep learning is robust to massive label noise. arXiv:1705. 10694, 2017.
Yanyao Shen and Sujay Sanghavi. Learning with bad training data via iterative trimmed loss mini- mization. In International Conference on Machine Learning (ICML), 2019.
Karen Simonyan and Andrew Zisserman. Very deep convolutional networks for large-scale image recognition. In International Conference Learning Representations (ICLR), 2015.
Jiaming Song, Tengyu Ma, Michael Auli, and Yann Dauphin. Better generalization with on-
the-fly dataset denoising. Sep 2018. URL
HyGDdsCcFQ
Sainbayar Sukhbaatar and Rob Fergus. Learning from noisy labels with deep neural networks. arXiv:1406.2080, 2014.
Yi Sun, Yiping Xu, et al. Limited gradient descent: Learning with noisy labels. arXiv:1811.0811 2018.
Daiki Tanaka, Daiki Ikami, Toshihiko Yamasaki, and Kiyoharu Aizawa. Joint optimization frame- work for learning with noisy labels. In Conference on Computer Vision and Paltern Recognition (CVPR), 2018
A. Torralba, R. Fergus, and W. T. Freeman. 80 million tiny images: A large data set for nonpara- metric object and scene recognition. IEEE Transactions on Pattern Analysis and Machine Intelligence (TPAMI), 2008.
Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning requires rethinking generalization. In International Conference on Learning Rep- resentations (ICLR), 2017.
Zhilu Zhang and Mert Sabuncu. Generalized cross entropy loss for training deep neural networks with noisy labels. In Advances in Neural Information Processing Systems (NIPS), 2018.

---

Under review as a conference paper at ICLR 2020
A DETAILS ON THE DATA-CLEANING PROCESS
In order to make sure that the CIFAR-10.1 test set has no overlap with our noisy dataset, we con- structed noisy dataset by first extracting all images with the respective keywords from the Tiny Images dataset, and then removing all images that are similar to the images in the CIFAR-1O. 1 test follows: We first identified 100 closest images for each individual image in the CIFAR-10. test set in fg-distance, and then removed equivalent and similar images after manual visual inspec- tion of these candidates.
We consider two images similar, if they share the whole or considerable portion of the same underlying main object, secondary object, or specific background (see Figure for examples). Performing this step manually is necessary because even images that are relatively far in ly-distance are often extremely similar, while images relatively close can be significantly different (see Figure for examples). We also note that it is too pessimistic to cutoff the images by using threshold together with a closeness measure because of this wide variety differences across images that actually contain the same object. Figure demonstrates instance of this problem for an image in the 'bird' class. There are many other such instances with highly different distance values, which necessitates manual inspection for this part.
In the following figures 9 11 we showcase some instances that further demonstrate the need for expert labeling for this similar image identification task. We note that in addition to the provided similar images, all the test images that are shown here also have identical copies in our training set that can be found without any need for manual labor. This is expected because the CIFAR-10.J test set is compiled mostly from Tiny Images and holds true for most of the images in this set.
Orig.
a) 4.35
b) Orig.
b) d = 6.14
c) Orig.
c) d 3.14
d) Orig.
d) d 4.22
Figure 7: Examples of images that are considered similar for the following reasons: a) Same pri- mary object with different contrasts; b) Different primary objects in the same background c) Same secondary object with different primary objects d) Same object in different poses.
Original
d 7.51
d 7.69
d 7.70 d = 7.71
d 7.76
Figure 8: Top-5 closest images to an test image in fæ-distance (d). The image at distance d = 7.76 almost equal to the original one, while closer one, at 7.69 is a different image.
12

---

Under review as a conference paper at ICLR 2020
a) Original
b) d 3.34
c) ~ 3.46
d)
3.56
e) 3.88
d 4.41
g) d = 4.45
Figure 9: Images that contain the same object in different colors, and are all removed from the training set.
Original
d 6.72
c) 6.91
d) d 6.94
e) 6.96
Figure 10: Images that contain the same object in different colors as well different object. This demonstrates that images in different colors can have a larger & diiiitaacc than completely different images, thus cannot simply remove images based on thresholding.
Original
c) d R 3.10
d)
e) dz = 3.78
f) d Rz 3.79
Figure 11: Images that contain different main objects in addition to the same or very similar sec- ondary objects in the background.
13

---

Under review as a conference paper at ICLR 2020
B LEARNING CURVES FOR DEEP LEARNING MODELS
In this section, we display additional learning curves for the models omitted in Section 3 of our main document.
candidate training set/VGG
clean training set/VGG
100
% accuracy
80
60
40
candidate training set/PNASNet
clean training set/PNASNet
100
% accuracy
80
60
40
candidate training set/Shake-Shake
clean training set/Shake-Shan Shake
100
% accuracy
80
60
training
test clean subset
40
100
200
300
50
100
epoch
epoch
Figure 12: Accuracy on the training set, test set throughout training of the VGG-16, PNASNet, and Shake-Shake-26 2x64d (S-S-I) models on our training set (left) and original CIFAR-10 training set (right). For the experiment on our training set, we also show the accuracy on a subset of the training set that are known to have clean labels and corresponds to CIFAR-10 test set.
C ERROR ANALYSIS
In this section we take closer look at the accuracy obtained by training on the candidate dataset. Figure shows the accuracy per class for training R8sNet-18 on the original CIFAR- 10 training set and training the candidate images with early stopping. The plots show that the model trained on candidate examples has better performance each class than the model trained on the original training set.
14

---

Under review as a conference paper at ICLR 2020
% Accuracy
0.8
airptar
mutomsbole
hard
doer
dog
fmng
hora
sbip
tnick
Figure 13:
Accuracy per class for training ResNet18 on the original CIFAR-10 training set (red bars) and training the candidate images with early stopping (blue bars). The plots show that the model trained on the candidate examples has better performance in each class than the model trained on the original training set. The error bars correspond to one standard deviation obtained by averaging over many different initialization.
15


Reviews:
[{"review_id": "HyxyyOuBqr", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "The paper reads well, the topic is interesting, and the connection between early stopping and fitting true label distributions before noisy ones, if generally true, is of potential impact. I do not feel the paper is ready for publication, though: \n\nMissing context/references:\n\t⁃\tNoisily collected labels are standard elsewhere, e.g., in sentiment analysis (self-ratings), in discourse parsing (explicit discourse markers), in weakly supervised POS tagging (crowdsourced dictionaries), in NER (Wikidata links), and in machine translation from mined parallel corpora or comparable corpora. \n\t⁃\tLearning a ground truth from a population of turkers (MACE and subsequent work). It is well-known that the noise in such silver standard or non-adjudicated annotations is also “more structured” and to a large extent predictable (Plank et al., EACL 2014 and subsequent work on learning/predicting inter-annotator disagreements). \n\t⁃\tConnection between L2 and early stopping. Can you replicate your results with simple L2 regularisation?\n\t⁃\tCost-sensitive learning of systematic disagreements (use class coherence scores for cost-sensitive learning). \n\t⁃\tThe observation that “clean examples are fitted faster than noise” is obviously related to baby steps training regimes (training on easy examples first), including active learning. \n\nExperimental details and flaws: \n\t⁃\tUsing a black box search engine to collect labels is problematic for a few reasons: (a) Search engines change, so results are hard to reproduce. (b) Search engines are biased toward certain types of categories. Such biases will be reinforced by any model trained on this data. \n\t⁃\tI’m always a little worried about papers that only report results for a single dataset. \n\t⁃\tI would have liked to see some more error analysis. Are the improvements on classes with more or less support in the original dataset, for example?\n\t⁃\tIt seems to be that it would have been relatively straight-forward to construct synthetic datasets that would more directly evaluate the hypothesis that the true labels are learned first. I realize you’re interested in “real” noise rather than “random” noise - but synthetic noise doesn’t have to be random. \n\t⁃\tThat “the noise generated through the label collection process is not nearly as adversarial for learning as the noise generated by randomly flipping labels” is no surprise, and I would not present this as a finding. It would be interesting to describe the bias, e.g., by presenting confusion matrices (see Plank et al., EACL 2014). \n", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "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_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "N/A"}, "extra_text": {}}, {"review_id": "H1x3TdB6Fr", "reviewer": "AnonReviewer3", "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": "Summary\n\nThe paper exploits the training dynamics of deep nets: gradient descent fits clean labels much faster than the noisy ones, therefore early stopping resembles training on the clean labels. The paper shows that early stopping the training on datasets with noisy labels can achieve classification performance higher than when training on clean labels (on condition that the total number of clean labels in the noisy training set is sufficiently large).\n\nThe paper also makes the point that noise introduced during data collection are different from artificially generated noise through randomly flipping the labels of a clean dataset. The latter is often done in the literature. The “real” noise is more structured and therefore it is easier to fit and less harmful to the classification performance.\n\nStrengths\n\nThe paper is well written. The results are very interesting even though they are very intuitive and simple.\n\nWeaknesses\n\nThe idea seems to be known. For example,\nBetter Generalization with On-the-fly Dataset Denoising\nhttps://openreview.net/forum?id=HyGDdsCcFQ\n\nThe paper talks about early stopping. As shown by the above paper, it is also a function of the learning rate. Please comment on what happens in the case of small learning rate and early stopping.\n\nIt would have been great to prove the theorem for deep learning. The result is limited to linear models with large number of random features.\n\nThe paper does not make it clear under what conditions early stopping prevents the model from memorizing bad labels.\n\nThe paper focuses on classification. Will the claims hold for other task types such as object detection, segmentation, etc?\n", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The authors present an approach to learning from noisy labels. The reviews were mixed and several issues remain unresolved. I do not accept the following as a valid response: "We fully agree that noisily collected labels are common for many problems other than image classification. However, the focus of our paper is image classification, and we thus concentrate on classification problems related to the widely popular CIFAR-10 and ImageNet classification problems." ICLR is a conference on theoretical and applied ML, and the fact that a technique has not been used for image classification before, does not mean you bring something to the table by doing so. The NLP literature is abundant with interesting work on label noise and should obviously be considered related work. That said, there's also missing references directly related to the connection between early stopping/regularization and label bias correction, including: 

[0] https://arxiv.org/pdf/1904.11238.pdf
[1] https://arxiv.org/pdf/1705.03419.pdf
[2] http://proceedings.mlr.press/v80/ma18d/ma18d.pdf

See also this paper submitted to this conference: https://openreview.net/forum?id=SJldu6EtDS
Decision: Reject