Learning with Feature-Dependent Label Noise: A Progressive Approach
Authors: Yikai Zhang
Songzhu Zheng
Pengxiang Wu
Mayank Goswami
Chao Chen
Venue: ICLR 2021 Spotlight (2021)
Keywords: Noisy Label
Deep Learning
Classification

Abstract: Label noise is frequently observed in real-world large-scale datasets. The noise is introduced due to a variety of reasons; it is heterogeneous and feature-dependent. Most existing approaches to handling noisy labels fall into two categories: they either assume an ideal feature-independent noise, or remain heuristic without theoretical guarantees. In this paper, we propose to target a new family of feature-dependent label noise, which is much more general than commonly used i.i.d. label noise and encompasses a broad spectrum of noise patterns. Focusing on this general noise family, we propose a progressive label correction algorithm that iteratively corrects labels and refines the model. We provide theoretical guarantees showing that for a wide variety of (unknown) noise patterns, a classifier trained with this strategy converges to be consistent with the Bayes classifier. In experiments, our method outperforms SOTA baselines and is robust to various noise types and levels.

Published as a conference paper at ICLR 2021
LEARNING WITH FEATURE-DEPENDENT LABEL NOISE: A PROGRESSIVE APPROACH
Yikai Zhang',, Songzhu Zheng"*, Pengxiang Wu²*, Mayank Goswami", Chao Chen Rutgers University, {yz422, pw241 10cs. www.gert.teree.... Stony Brook University, {zheng. songzhu, chao chen. www.aa.....eee...tt..eeeee..ee.e @estonnyrooko.e.. edu 3 CCity University of New York, mayank. isi wewigmmmal..omm
ABSTRACT
Label noise is frequently observed in real-world large-scale datasets. The noise is introduced due variety of reasons; it is heterogeneous and feature-dependent. Most existing approaches to handling noisy labels fall into two categories: they either assume an ideal feature-independent noise, remain heuristic without theoretical guarantees. In this paper, we propose to target a new family of feature- dependent label noise, which is much more general than commonly used i.i.d. label noise and encompasses broad spectrum of noise patterns. Focusing on this general noise family, we propose a progressive label correction algorithm that iteratively corrects labels and refines the model. We provide theoretical guarantees showing that for a wide variety of (unknown) noise patterns, a classifier trained with this strategy converges to be consistent with the Bayes classifier. In experiments, our method outperforms SOTA baselines and is robust to various noise types and levels.
INTRODUCTION
Addressing noise in training set labels is an important problem in supervised learning. Incorrect annotation of data is inevitable in large-scale data collection, due to intrinsic ambiguity of data/class and mistakes of human/automatic annotators (Yan et al. 2014: Andreas et al., (2077). Developing methods that are resilient to label noise is therefore crucial in real-life applications.
Classical approaches take a rather simplistic i.i.d. assumption on the label noise, i.e., the label corrpption is independent and identically distributed and thus is on this assumption either explicitly estimate the noise pattern (Reed et al.) 2014] Patrini et al.
Methods based
2017
Dan et al. 2019 Xu al.
2019) or introduce extra regularizer/loss terms (Natarajan et al. 2013
Van Rooyen et al. | 2015 Xiao et al., 2015) Zhang & Sabuncu 2018 Ma et al.
2018| Arazo et al.
2019 Shen & Sanghavi, 2019). Some results prove that the commonly used losses are naturally
robust against such i.i.d. label noise (Manwani & Sastry 2013 Ghosh et al. 2015 Gao et al. 2016
Ghosh et al. 2017 Chhroenphakdee et al. 2019 Hu et al. 2020).
Although these methods come with theoretical guarantees, they usually do not perform as well as expected in practice due to the unrealistic i.i.d. assumption on noise. This is likely because label noise is heterogeneous and feature-dependent A cat with an intrinsically ambiguous appearance more likely to mislabeled as dog. An image with poor lighting or severe occlusion can be mislabeled, important visual clues imperceptible. Methods that combat label noise of much more general form are very much needed to address real-world challenges.
To adapt to the heterogeneous label noise, state-of-the the-arts (SOTAs) often resort data recabbbaaai strategy. They progressively identify trustworthy data or correct data labels, and then train using these data (Tnaka et al.) 2018 Wang al. 2018 Lu et al.) 2018 Li et al., 2019). The models gradually improve as more clean data are collected or more labels are corrected, eventually converging to models of high accuracy. These fata-recalibrating methods best leverage the learning power of deep neural nets and achieve superior performance in practice. However, their underlying mechanism remains a mystery. No methods in this category can provide theoretical insights as why the model
"Equal contributions.

---

Published as a conference paper at ICLR 2021
can converge to ideal one. Thus, these methods require careful hyperparameter tuning and are hard to generalize.
In this paper, we propose novel and principled method that specifically targets the heterogeneous, feature-dependent label noise. Unlike previous methods, we target a much more general family of noise, called Polynomial Margin Diminishing (PMD) label noise. In this noise family, allow arbitrary noise level except for data far away from the true decision boundary. This is consistent with the real-world scenario; data near the decision boundary are harder to distinguish and more likely to be mislabeled. Meanwhile, a datum far away from the decision boundary is a typical example of its true class and should have a reasonably bounded noise level.
pooreticalll-guaranteeee data-recalibrating algorithm that gradually corrects labels based on the noisy classifier's confidence. We start from data points with high confidence, and correct the labels of these data using the predictions of the noisy classifier. Next, the model is improved using cleaned labels. We continue alternating the label correction and model improvement until it converges. See Figure [ for an illustration. Our main theorem shows that with a theory-informed criterion for label correction at each iteration, the improvement of the label purity is guaranteed. Thus the model is guaranteed to improve with sufficient rate through iterations and eventually becomes consistent with the Bayes optimal classifier.
Assuming this new PMD noise family, we propose
Beside the theoretical strength, we also demonstrate the power of our method in practice. Our method outperforms others on CIFAR- 1IFAR-10/100 with various synthetic noise patterns. We also evaluate our method against SOTAs three real-world datasets with unknown noise patterns.
To the best of our knowledge, our method is the first rata-recalibiating method that is theoretically guaranteed converge to an ideal model. The PMD noise family encompasses broad spectrum of heterogeneous and feature-dependent noise, and better approximates the real-world scenario. It also provides a novel theoretical setting for the study of label noise.
Related works. We review works that do not assume an i.i.d. label noise. Menon et al. (2018) generalized the work of (Ghosh al., 2015) and provided an elegant theoretical framework, showing that loss functions fulfilling certain conditions naturally resist instance-dependen noise. The method can achieve even better theoretical properties (i.e., Bayes-consistenge
with stronger assumption on the clean posterior probability 1j. In practice. this method has not been extended to deep neural networks. Cheng et al. (2020) proposed an active learning method for instance- deeenddnt label noise.
Cass
Class 0
Clean Data
Class
class
Ronsy Label
x3
(a) Clean Data
(b) Corrupted Data
(c) Corrected Data
(d) Corrected Labels
Cieas cwts
Canal cara comperts selin
Cesn cwra
contesnce ragion
confests ragin
(e) Epoch 10
(f) Epoch 20
(g) Epoch 30
(h) Final Epoch
Figure 1: Illustration of the algorithm using synthetic data, (a) Gaussian blob with clean label (n* (x)). (b) Data with corrupted labels. (c) Final corrected data. Black dots are the data that have their clean labels. Red dots are the noisy data. Points that remain un-corrected are closer to the decision boundary. Our algorithm corrects most of the noise only using noisy classifier's confidence. (d) Data after label correction. (e)-(h) We show the intermediate results at different iterations. Gray region is the area where the classifier has high confidence. Labels within this region are corrected.
2

---

Published as a conference paper at ICLR 2021
The algorithm iteratively queries clean labels from oracle carefully selected data. However, this approach is not applicable to settings where kosher annotations are unavailable. Another contemporary work (Chen al., (02T) showed that the noise in real-world dataset is unlikely to be i.id., and proposed to fix the noisy labels by averaging the network predictions on each instance over the whole training process. While being effective, their method lacks theoretical guarantees. [Chn iet al. (2019) showed by regulating the topology of a classifier's decision boundary, one can improve the model's robustness against label noise.
Data-recalibrating methods use noisy networks' predictions to iteratively select/correct data and improve the models. Tanaka et al. (2018) introduced a joint training framework which simultaneously enforces the network to be consistent with its own predictions and corrects the noisy labels during training. Wang et al. (2018) identified noisy labels as outliers based on their label consistencies with surrounding data. Lu et al. (2018) used curriculum learning strategy where the teacher net trained on a small kosher dataset to determine if a datum is clean; then the learnt curriculum that gives the weight to each datum is fed into the student net for the training and inference. (Yu et al. 2019; Bo et al. 2018) trained two synchronized networks; the confidence and consistency of the two networks are utilized to identify clean data. [Wu et al. (2020) selected the clean data by investigating the topological structures of the training data in the learned feature space. For completeness. we also refer other methods of similar design (Li et al. 2017 Vahdat 2017 Andreas al. 2017 Ma et al.,
2018 Thullasdasann et al. 2019 Arazo et al. 2019: Shu et al. 2019 Yi & Wu 2019).
As for theoretical guarantees, Ren al. 2018) proposed an algorithm that iteratively re-weights each data point by solving an optimization problem. They proved the convergence of the training, but provided no guarantees that the model converges an ideal one. Amid et al. (2019b) generalized the work of (Amid et al., (211a) and proposed a tempered matching loss. They showed that when the final softmax layer replaced by the bi-tempered loss, the resulting classifier will be Bayes consistent. [Zheng et al. (2020) proved a one-shot guarantee for their data- recalieccli method; but the convergence of the model is not guaranteed. Our method the first data-recalinn recabbbraliirttingg method which is guaranteed to converge to a well-behaved classifier.
2
METHOD
We start by introducing the family of Poly-Margin Diminishing (PMD) label noise. In Section 2.2 we present our main algorithm. Finally, we prove the correctness of our algorithm in Section 3
Notations and preliminaries. Although the noise setting and algorithm naturally generalize to multi- class, for simplicity we focus binary classification. Let the feature space be X. We assume the data (x. y) is sampled from an underlying distribution D on X' x {0. 1}. Define the posterior probability y 0, æ and T1,0(2)
Pp = 0 y 1, x] be the noise functions, where y denotes the corrupted label. For example, if a datum x has true label y 0, it has 7o, (a:) chance be corrupted 1. Similarly, it has 71,0(ar) chance to be corrupted from to 0. Let f)(x) = Ply 1 æ]] be the noisy posterior probability of ğ = 1 given feature æ. Let 7) (x) [(((=))2)) } } be the (clean) Bayes optimal classifier, where 1A cquals if A is true, and 0 otherwise. Finally, let f(x) : X' + [o, 1] be the classifier scoring function (the softmax output of a neural network in this paper).
n(x)) = PPyy 1 æ². Let To,1 = Ply
2.1 POLY-MARGIN DIMINISHING NOISE
We first introduce the family of noise functions T this paper will address. We introduce the concept of polynomial margin diminishing noise (PMD noise), which only upper bounds the noise in certain level set of 17(x), thus allowing T to be arbitrarily high outside the restricted domain. This formulation not only covers the feature-independen scenario but also generalizes scenarios proposed by (Du & Cail 2015) Menon et al.) 2018; Cheng et al. 2020).
Definition 1 (PMD noise). A pair of noise functions To,1 and T1,0(z) are molynomial-margin diminishing (PMD), if there exist constants to (0, })), and c1, 02 0 such that:
1
(x) S ci[1- -n(=)]++0) vn(x) > 2
+ to, and
(I)
(x) S ((((x))+0) 402; vn(xx) S 2 to-
3

---

Published as a conference paper at ICLR 2021
We abuse notation by referring as the "margin" of T. Note that the PMD condition only requires the upper bound on T to be polynomial and monotonically decreasing in the region where the Bayes classifier is fairly confident. For the region {æ : Im(x) - b to), we allow both To,1(z) and 71,0 to be arbitrary. Figure[2cc illustrates the upper bound (orange curve) and a sample noise function (blue eurve). We also show the corrupted data according this noise function (black points the clean data whereas red points are the data with corrupted labels).
The PMD noise family is much more general than existing noise assumptions. For example, the boundary consistent noise (BCN) (Du & Cai 2013 Menon et al. 2018) assumes a noise function that monotonically decreases as the data are moving away from the decision boundary. See Figure 2)c) for an illustration. This noise is much more restrictive compared to our PMD noise which (I) only requires a monotonic upper bound, and (2) allows arbitrary noise strength in a wide buffer near the decision boundary. Figure(2 shows traditional reature-independen
noise pattern (Reed et al., 2014 Patrini et al. 2017), which assumes To.1 (x)) (resp. T1,0 (z)) to be a constant independent of az.
Noksy Data
Data
Noisy
X1
X1
X;
x;
To.1 + TT. T1.0(k))
+ + K2, (00)
To. 1o0 + Tq 9/8)
7000
0.5
X1
X1
(a) Clean labels
(b) Uniform noise
(c) BCN noise
(d) PMD noise
Figure 2: Illustration of different noise functions. (a) The original data: Gaussian blob with clean
labels (by clean label, refer to the prediction of the Bayes optimal classifier 17" (z)) not y)- Confident region of (and thus [) in this case is the place where 17()) is close to 0 or 1. Blue and green dots correspond to different classes. (b) Uniform label noise: each point has equal probability to be flipped. Red dots are data with corrupted labels; black dots correspond to data that are not corrupted. (c) BCN noise: the level of noise decreasing as 17" (a:) becomes confident. (d) PMD noise: noise level (blue) is only upper bounded by diminishing polynomial function when n(x)) higher or lower than certain threshold. The upper bound is shown in solid orange curve. The dashed orange curve means the noise level near the decision boundary is unbounded.
2.2 THE PROGRESSIVE CORRECTION ALGORITHM
Our algorithm iteratively trains neural network and corrects labels. We start with warm-up period, in which we train the neural network (NN) with the original noisy data. This allows us to attain a reasonable network before it starts fitting noise (Zhang al., 2017). After the warm-up period, the classifier can be used for label correction. We only correct a label on which the classifier f has a very high confidence. The intuition is that under the noise assumption, there exists "pure region" in which the prediction of the noisy classifier / is highly confident and is consistent with the clean Bayes optimal classifier r7". Thus the label correction gives clean labels within this pure region. In particular, we select high threshold 6. If f predicts a different label than ÿ and its confidence is above the threshold, (xx) 1/2) > we flip the label ÿ to the prediction of f. We repeatedly correct labels and improve the network until no label is corrected. Next, we slightly decrease the threshold 0, use the decreased threshold for label correction, and improve the model accordingly. We continue the process until convergence. For convenience in theoretical analysis, in the algorithm, we define a continuous increasing threshold T and let 0 = 1/2 - T. Our algorithm is summarized in Algorithm[1 II We term algorithm as PLC (Progressive Label Correction). In Section 3] will show that this iterative algorithm will converge to be consistent with clean Bayes optimal classifier vy" (a:) for most of the input instances.
4

---

Published as a conference paper at ICLR 2021
Algorithm 1 Progressive Label Correction
Input: Dataset = Di). (In, F2) initial NN f(),, step size 8, initial and end thresholds (To, Tend), warm-up m, total round N Output: (fina(())
1: T < To
2: 0 <- 1-2
1/2-11 1-12/2 To
3: for + 1,... ,N do
4: Train ((x) on S
5:
for all (z,, M2 1)
S and [f(x;) - 2 do
6:
K + [((022)))
7:
end for
8:
if 2 then
9:
0 1/2 - if E [1, T min(T(1 3), Tend)
10:
,n], 07 = --1 then
11:
12:
end if end if
14:
$ + [(x107)) Di)..... (2,,, }n)
end for
Generalizing to the multi-class scenario. In multi-class scenario, denote by fi(x) the classifier's prediction probability of label i. Let h be the classifier's 's class prediction, i.e., hg arg max; fx)). We change the [xx 1 term the gap between the highest confidence Sr., (ar) and the confidence on y. f& (x). If the absolute difference between these two confidences is larger than certain threshold 0, then we correct ÿ to hgg In practice, we find using the difference of logarithms will be more robust.
ANALYSIS
Our analysis focuses on the asymptotic case and answers the following question: Given infinitely many data with corrupted labels, is it possible to learn reasonably good classifier? We show that if the noise satisfies the arguably-general PMD condition, the answer is yes. Assuming mild conditions the hypothesis class of the machine learning model and the distribution D, prove that Algorithm|| AlgorithmmJootanns Jobtains nearly clean classifier. This reduces the challenge of noisy label learning from realizable problem into sample complexity problem. In this work we only focus on the asymptotic case, and leave the sample complexity for future work.
3.1 ASSUMPTIONS
Our first assumption restricts the model to be able to at least approximate the true Bayes classifier ())) This condition assumes that given hypothesis class H. with sufficient complexity, the approximation gap between a classifier f(x) in this class and ()x)) ) is determined by the inconsistency between the noisy labels and the Bayes optimal classifier.
Definition 2 (Level set (a, consistency) Suppose data are sampled as (x, ū) ~ D(x, ñ(x)) and f(x)) = arg min D (a)) (hs)( 5). Given & <, ), we call is (ax, e) connsisttn if: hE7
1 [(()) | 1 2 m(() 1/1
| +
[f(=) - n(x) < ( ((L
For two input instances z and æ such that r7x)) 17xx) (and hence the clean Bayes op- timal classifier 17 (x) has higher confidence at z than it does at I), the indicator function (=)) (z [m(z) - 1 2 In(=)= - H) equals to I if the label of the more confident point z is inconsistent with 17" (z). This condition says that the approximation error of the classifier at æ should be controlled by the risk of 17" (-) at points where 1) (-) is more confident than it is at æ.
We next define a regularity condition of data distribution which describes the continuity of the level set density function.
5

---

Published as a conference paper at ICLR 2021
Definition 3 (Level set bounded distribution). Define the margin t(x) = In(x) and G(t) be the edf of t. G(t) P Pa-D((1(a say the distribution D is (co, c" ) if for all 0 < t S 1/2, 0 < cx S g(t) S c'. If is "c.,"")-boundees we define the worst-case density- incillncce ratio of D by lp: C.
1 S t). Let g(t) (t) be the density function of t. We
The above condition enforces the continuity of level set density function. This is crucial in the analysis since such a continuity allows one to borrow information from its neighborhood region so that a clean neighbor can help correct the corrupted label. To simplify the notation, we will omit D in the subscript when we mention É. From now on, we will assume:
Assumption 1. There exist constants a, C, Cc, c² such that the hypothesis class H. is (a, c) conssisten and the unknown distribution (cx, ca) --boudded.
3.2 MAIN RESULT AND PROOF SKETCH
In this section we first state our main result, and then present the supporting claims. Complete proofs can be found in the appendix. Our main result below states that our starting function is trained correctly, i.e., f() arg min E(a, (i))
57), then Algorithm I terminates with
hER
most of the final labels matching the Bayes optimal classifier labels. In practice, minimizing true risk is not achievable. Instead, the empirical risk is used to estimate true risk, approaching true risk asymptotically. For scoring function f. will denote by Uf(=) [(f(a)) 2 1/2) the label
predicted by ʃ-
Theorem 1. Under Assumption for any noise which is PMD with margin tu- define eo
mar(to. 1+2a ). Then for the output of Algorithm with f as above and with the following initial-
izations: (1) To 1
2 Co. (2) m
21b ). (3) N 2 m m+++ 1 log( Tb ). (4) Tend S 3c and (5) Ea loo(
1e2
3
at B 25
at. have:
P P Pa-Dlyff
1J" (x) 2 3c
In the remainder of this section we shall assume that the noise 7 is PMD with margin to. To prove our result we first define "pure" level set. Definition 4 (Pure (e, n.)) set). A set [(ee = {a (m)(a)) 1 2 e) is pure for ff 17" (x) all x E L(e, m)-
We now state a lemma that forms the foundation of our progressive correction algorithm. We show that given a tiny region where the model is reliable, we can move one step forward by trusting the model. Although the improvement slight in a single round, it empowers a conservatively recursive step in the Algorithm D
Lemma (One round purity improvement). Suppose Assumption I is satisfied, and assume an f such
that there exists a pure (c, f, -level set with 3c S < 1 Let finew (x) = Uf()) if (z() - 1/2] 2
and 7(z) if (x(x) - 1//2 < e, and assume fnew = arg min E (m..i) (())) Loss(h (1(x))))))))))))))()) (z), ÿ). Let
heH
Gnew = minfele > 0, Me,, 1)) is pure for Jnow]. Then Gnew 2 (1 0 - e)-
The above lemma states that the cleansed region will be enlarged by at least a constant factor. In the following lemma, we justify the functionality of the first m warm-up rounds. Since the initial neural network can behave badly, the region where can trust the classifier can be very limited. Before starting the flipping procedure in a relatively larger level set, one first needs to expand the initial tiny region? eg to constant To-
Lemma (Warm-up rounds). Suppose for a given function fo there exists a level set L(eo. 17) which is pure for for Given To < 1/2, after running Algorithm for m 2 Ea log( 1-200 rounds, there exists a level set L To. 1)) that is pure for fo-
Next we present our final lemma that combines the previous two lemmata.
Lemma 3. Suppose Assumption I is satisfied, and for a given function fo there exists a level set L(eo, 1) which is pure for fo- If one runs Algorithm! starting with fo and the initializations: (1)
To 1/2 Cp. (2) m 2 la log( 2T (3) N 2 m + 1/2 log( 165),, (4) Tend S 3/2 3e and (5) 1)" (m)) 2 3c
5 5 33 at, then we have IP Pa-D(y

---

Published as a conference paper at ICLR 2021
This lemma states that given an initial model that has reasonably pure super level set, can manage to progressively correct a large fraction of corrupted labels by running Algorithm [ for a sufficient long time with carefully chosen parameters. The limit of Algorithm will depend on the approximation ability of the neural network, which is characterized by parameter in Definition 2 To prove Theorem | Jusing Lemma []] it suffices get a model which has reliable region. This provably achievable by training with a family of good scoring functions on PMD noisy data.
4 EXPERIMENTS
We evaluate our method on both synthetic and real-world datasets. We first conduct synthetic experi- ments two public datasets CIFAR-10 and CIFAR- --0FR-100 (Krizhevsky et al. 2009). To synthesize the label noise, we first approximate the true posterior probability v using the confidence prediction of a clean neural network (trained with the original clean labels). We call these original labels raw labels. Then we sample yæ ~ nn(x) for each instance æ. Instead of using raw labels, we use these sampled labels ya as the clean labels, whose posterior probabilities are exactly n7(z); and therefore the neural network is the Bayes optimal classifier 7/" X + (1..... ................................ , C)2 where C is the number of classes. Note that in multi-class setting, 77(2z) has vector output and (ax) is the i-th element of this vector.
Noise generation. We consider a generic family of noise. We consider not only feature-dependent noise, but also hybrid noise that consists of both feature-dependent noise and i.i.d. noise.
noise, we use three types of noise functions within the PMD noise family. To make the noise challenging enough, for input æ we always corrupt label from the most confident category the to the second confident category $g. according to (ar). Because 8 is the class that confuses 17" (x) the most, this noise will hurt the network's performance the most. Note that yo is sampled from n(x), which has quite extreme confidence. Thus we generally assume yo is ugx For each datum æ, we only flip it to Sa or keep it as ugz The three noise functions are as follows:
For Seature-dependee
1
Type-I: Tu
1m (x) 7ee (x)]]² + 2'
Type-Il: Tun. = - [Then (x) - 7s== (x))3
2
Type-III: Tu
[ (x) - Ts (x) + [nm. (2) - 7s (x)) + IThe (x) - To_ (3)]
Notice that the noise level is determined by the r7(x)) naturally and we cannot control it directly. To change the noise level, we multiply : by certain constant factor such that the final proportion of noise matches our requirement. For PMD noise only, we test noise levels 35% and 70%, meaning that 35% and 70% of the data are corrupted due to the noise, respectively.
For i.i.d. noise we follow the convention and adopt the commonly used uniform noise and asymmetric noise (Patrini et al. 2017). We artificially corrupt the labels by constructing the noise transition matrix T, where Tyj = jly = i) = Tiy defines the probability that a true label y = is flipped to Then for each sample with label i, we replace its label with the one sampled from the probability distribution given by the i-th row of matrix T. We consider two kinds of i.i.d. noise in this work.
(1) Uniform noise: the true label is corrupted uniformly to other classes, i.e., Tí = T/(CC- - 1) for i * j, and Th 1 - where 7 is the constant noise level; (2) Asymmetric noise: the true label i is flipped to j or stays unchanged with probabilities Tıj T and T. 1 T, respectively.
Baselines. We compare our method with several recently proposed approaches. (1) GCE Zhang & Sabuncu 2018); (2) Co-teaching+ (Yu et al., 2019;; (3) SL (Wang al., 2019): (4) LRT Zheng et al. 2020 All these methods are generic and handle the label noise without assuming the noise structures. Finally, we also provide the results by standard method, which simply trains the deep network on noisy datasets in standard manner.
During training, we use a batch size of 128 and train the network for 180 epochs to ensure the convergence of all methods. We train the network with SGD optimizer, with initial learning rate 0.01. We randomly repeat the experiments times, and report the mean and standard deviation values. Our code is available at httttts:://gttitii
com www.o//ppiioooo wwwpp//wwwwwwwp////cccctptptpp/p
Results. Table I lists the performance of different methods under three types of feature- dependen noise at noise levels 35% and 70%. We observe that our method achieves the best performance across different noise settings. Moreover, notice that some of the baseline methods" performances are inferior to the standard approach. Possible reasons are that these methods behave too conservatively
7

---

Published as a conference paper at ICLR 2021
in dealing with noise. Thus they only make use of small subset of the original training set, which is not representative enough to grant the model good discriminative ability.
In Table 2 we show the results on datasets corrupted with combination of feature- deeture-dependent noise and i..d. noise, which ends up to real noise levels ranging from 50% to 70% (in terms of the proportion of corrupted labels). Li.d. noise is overlayed on the Peature-dependert noise. Our method outperforms baselines under these more complicated noise patterns. In contrast, when the noise level is high like the cases where we further apply additional 30% and 60% uniform noise, performances of a few baselines deteriorate and become worse than the standard approach.
We carry the ablation studies on hyper-parameters On (determining the initial confidence threshold for label correction, see Algorithm 1) and 8 (the step size). In Tables 3 and 4 we show that our method is robust against the choice of 0g and | up to a wide range. Notice that to compare against the threshold fo. here we are calculating the absolute difference of log fa(()) and log Jt. (a:). As
mentioned in Section 2.2 this operation gives a good performance in practice.
Table I: Test accuracy (%) on CIFAR-10 and CIFAR- 100 under different feature-dependent noise types and levels. The average accuracy and standard deviation over trials are reported.
Dataset
Noise
Standard
Co-teaching+
GCB
S1.
PL.C (ours)
Type-1 (5%%
18.11
79.97
0013
80.65 + 0.39
79.76
0.72
80.98
= 0.80
82,80 + 0.27
Type-I 70%
41.98 + 1.96
10.69 = 1.99
36. + 1.62
36.29
: 0.66
11.52 = 4.53
12.74 + 2.14
CIFAR-10
Type-1I
76.65 0.57
77.34
0.44
77.60 0.88
77.92
80.74
81.54 0.47
Type-Il ( 70%
}
45.57 + 1.12
45.44
00661
40.30
1.46
41.11
1.92
4/.67 = 3.89
46.04 + 2.20
Type: 33%%
76.89 + 0.79
78:38
0.BY
79.18
+ 0.61
78.81
0:29
$1.08 + 0.35
81.50 0.50
Type-IIl < 70%
43.32 +
41.90
0.86
37.10
0.59
38.49
1.46
44.47 = 1.23
45.05 + 1.13
Type-I (35%
57.68 + 0.29
56.70=00
0.71
58.37
= 0.18
55.20
0.33
56.71 = 0.34
60.01 0.43
Type-I ( 70%
39.32 + 0.43
39.53
0,28
40.01 + 0.71
40.02
= 0.85
45.29 = 0.43
45.92 = 0.61
Type-II (35%)
57.83
+ 0.25
56.57
0.52
58.11 1.05
56.10
0.73
5r.25 = 0.68
63.68 = 0.29
CIFAR-100
Type-I1 70%
39.30 0.33
36.81
0.39
37. 37.75
0.46
38.45
0.45
13.71
45.03 0.50
Type- III 35%
56.07
+ 0.79
55.77
0.98
57.51
+ 1.16
00.74
56.57
= 0.30
63.68
+ 0.29
Type-III ( 70%)
10.01 + 0.18
35.37 2.65
40.53 = 0.60
0.891
11.1 = 0.19
44.45 - 0.62
Table 2: Test accuracy (%) on CIFAR-10 and CIFAR-100 under different hybrid noise types and levels. The average accuracy and standard deviation over trials are reported.
Daraset
Noise
Standard
Co-teaching+
GCE
SL.
LRT
PLC (ours)
Type-1+ 30% Uniform
75.26 = 0.32
78.72
78.08
0.66
77.79-3
0.16
75.97 0:27
Type + 60% Uniform
64.25 0.78
55.49 1: 2.11
67.43
1.43
67.63
1.36
59.22
0.74
72.21
1: 2.92
Type-1+ + 30% Asymmetric
75.21 = 0.64
75.43
2.943:29.6 2.96
76.91
= 0.56
77.14
0.70
76.96
= 0.45
78.31
0.41
Type-I+ + 30% Uniform
7432 = 0.63
0.51
70:09
0.21
75.08
= 0.47
75.91
0.58
80.08
0.37
CIFAR-10
Type-11 + 60% Uniform
61022 = 0.66
59.89
0:::::0:0 0.63
66.39
0.29
66.76 1: 1.60
58.99
= 1.43
71.21
1.46
Type-1I 30% Asymmetric
74.28 0.39
13.37
75.30
0.81
75.13
0.42
71.03
77.63
Type-III 30% Uniform
74.00 - 0.38
TT.31 + 0.11
77.00
0.12
76.22
+ 0.12
75.06
0.57
80.06
0..47
Type-1ll 60% Uniform
63.96 = 0.69
56.78 2 1.56
67.53
0.51
67.79
+ 0.54
59.36
0.93
73. 48
1.54
Type-II1 30% Asymmetrie
75.31 0.34
74.62
1.71
70.70
0.91
76.09
0.10
79.
0.74
77. 54
0.70
Type + Unitorm
$2.33
52.00
0.53
51.34
0.64
45.66
60.09
Type-1 + 60% Uniform
35.97 1.12
27.17 - 1.66
38.62
1.65
37.57
: 0.43
23.37
= 0.72
51.68
= 0.10
Type-1 30% Asymmnetric
45.85 0.93
51.21
0.31
$2.60
1.14
50.18
0.97
52.04
0.15
56 40
0.34
Type-11 11 + 30% Unitorm
19.32 0.36
51.08
0.73
53.61
0.46
30.58
1 0.25
14.38
1.11
60.01
0.63
CIFAR-100
Type-11 60% Uniform
35.16 0.05
25.91
= 0.64
39.58
3.13
37.
93
= 0.22
23.05
0.99
19.35
1.53
Type 11 30% Asymmetric
0.95
$1.98
0.37
49.46
0.23
52.11
1ype-111 111 + 30% Unitorm
4891 0.61
19.91
0.11 0.14
52.07
= 0.33
50.18
2 0.54
12.79
L.78
60.14 0.97
Type-111
60% Uniform
34.67
0.16
22.89
0.75
36,82
0.49
1.42
22.81
0.72
73
Type 111 + 30% Asymmetric
45.70 = 0.12
19.38 1: 0.86
50.87
1.12
48.15
1 0.50
50.31
0.39
51.56 = 1.11
Table 3: The effect of 6g on the performance. We use CIFAR-I0 with 35% feature- ceature-dependent noise, and set B
Table 4: The effect of / on the performance. We use CIFAR-10 with 35% feature-dependent
0.1.
noise, and set exp (0p) = 0.3.
exp (fa)
0.2
0.3
0.4
0.5
B
0.05
0.1
0.2
0.3
Type-I Noise
83.33
83.04
82.66
82,94
Type-I Noise
83.58
83.04
83.28
83.31
Type-II Noise
81.84
81.18
81.09
81.24
Type-II II Noise
80.94
81.18
80.98
80.86
Type-I11 III Noise
81.79
81.75
81.98
82.06
Type-Ill Noise
81.91
81.75
82.13
82,39
Results on real-world noisy datasets. To test the effectiveness of the proposed method under real- Xxp world label noise, we conduct experiments on the Clothing I dataset (Xiao et al. 2015). This dataset contains million clothing images obtained from online shopping websites with 14 categories. The labels in this dataset are quite noisy with an unknown underlying structure. This dataset provides 50k,
8

---

Published as a conference paper at ICLR 2021
14k and 10k manually verified clean data for training, validation and testing, respectively. Following (Tanaka et al. 2018 Yi & Wu 2019). in our experiment we discard the 50k clean training data and evaluate the classifcation accuracy on the 10k clean data. Also, following (Yi & Wu 2019). use randomly sampled pseudo-balanee
subset as the training set, which includes about 260k images. We set the batch size 32, learning rate 0.001, and adopt SGD optimizer and use ResNet-50 with weights
pre-trained on ImageNet, as in (Tanaka et al. 2018 Yi & Wu 2019).
We compare our method with the following baselines. (1) Standard; (2) Forward Correction (Patrini
et al. 2017); (3) D2L (Ma et al. 20188;; (4) JO (Tanaka et al. 2018); (5) PENCIL (Y & Wu 2019); (6)
DY Arazo al. 2019); (7) GCE (Zhang & Sabuncu, 2018); (8) SL (Wang et al. 2019): (9) MLNT
Li et al. 2019); (10) LRT (Zheng et al., 2020). In Table we observe that our method achieves the best performance, suggesting the applicability of our label correction strategy in real-world scenarios.
Apart from Clothing we also test our method on another smaller dataset, Food- 101N (Lee et al. 2018). Food-101N is a dataset for food classification, and consists of 310k training images collected from the web. The estimated label purity is 80%. Following (Lee et al., 2018), the classification accuracy is evaluated on the Food-101 (Bossard et al. 2014) testing set, which contains 25k images with curated annotations. We use ResNet-50 pre-trained on ImageNet. We train the network for 30 epochs with SGD optimizer. The batch size is 32 and the initial learning rate is 0.005, which is divided by 10 every 10 epochs. We also adopt simple data augmentation procedures, including random horizontal flip, and resizing the image with a short edge of 256 and then randomly cropping 224x224 patch from the resized image. We repeat the experiments with 3 random trials and report the mean value and standard deviation. The results are shown in Table 6 Our method much improves upon the previous approaches.
Finally, we test our method on a recently proposed real-world dataset, ANIMAL- (Song et al. 2019). This dataset contains buman-labeled online images for 10 animals with confusing appearance. The estimated label noise rate is 8%. There are 50,000 training and 5,000 testing images. Following (Song et al. ) we use VGG-19 with batch normalization. The SGD optimizer employed. Also following (Song et al. 2019). we train the network for 100 epochs and use an initial learning rate of 0.1, which is divided by at 50% and 75% of the total number of epochs. We repeat the experiments with 3 random trials and report the mean value and standard deviation. As is shown in Table 7 our method outperforms the existing baselines.
Table 5: Test accuracy (%) on Clothing IM.
Method
Standard
Forward
D2L
JO PENCIL
DY
GCE
SL
MINT
LRT
PLC (ours)
Accuracy
68.94
69.84
69.47
72.23
73.49
71.00
69.75
71.02
73.47
71.74
74.02
Table 6: Test accuracy (%) on Food-101N.
Table 7: Test accuracy (%) on ANIMAL-ION
Method
Accuracy
Method
Aceuracy
Standard
81.67
Standard
79.4 + 0.14
CleanNet (Lee et al. 2018
83.95
SELFIE (Song et al. 2019
81.8 + 0.09
PLC (ours)
85.28 + 0.04
PLC (ours)
83.4 + 0.43
CONCLUSION
We propose a novel family of feature-dependent label noise that is much more general than the traditional i.i.d. noise pattern. Building upon this noise assumption, we propose the first data- recalibrating method that theoretically guaranteed to converge synthetic datasets, we show that our method outperforms various baselines under different feature- dependent noise patterns subject to our assumption. Also, we test our method on different real- world noisy datasets and observe superior performances over existing approaches. The proposed noise family offers a new theoretical setting for the study of label noise.
well-behaved classifier. On the
Acknowledgement. The authors acknowledge support from US National Science Foundation (NSF) awards 1751-1755791, CCF-19 191071,,,73, CCF-1855760. This effort was partially supported by the Intelligence Advanced Research Projects Agency (IARPA) under the contract W W91INF20C0038. The content of this paper does not necessarily reflect the position or the policy of the Government, and official endorsement should be inferred.
9

---

Published as a conference paper at ICLR 2021
REFERENCES
Ehsan Amid, Manfred K Warmuth, and Sriram Srinivasan. Two-temperature logistic regression based on the tsallis divergence. In AISTATS, pp. 2388-2396, 2019a.
Ehsan Amid, Manfred K. K Warmuth, Rohan Anil, and Tomer Koren. Robust bi-tempered logistic loss based on bregman divergences. In NeurlPS, pp. 15013-15022, 2019b.
Veit Andreas, Alldrin Neil, Chechik Gal, Krasin Ivan, Gupta Abhinav, and Belongie Serge. Learning from noisy large-scale datasets with minimal supervision. In CVPR, pp. 6575-6583, 2017.
Eric Arazo, Diego Ortego, Paul Albert, Noel E O'Connor, and Kevin McGuinness. Unsupervised label noise modeling and loss correction. In ICML, 2019.
Han Bo, Yao Quanming, Yu Xingrui, Niu Gang, Xu Miao, Hu Weihua, W. Tsang Ivor, and Sugiyama Masashi. Co-teaching: Robust training of deep neural networks with extremely noisy labels. In NeurlPS, pp. 8536 8546, 2018.
Lukas Bossard, Matthieu Guillaumin, and Luc Van Gool. Food- Food-101-aa 101-minin discriminative compo- nents with random forests. In ECCV, pp. 446 0664461,2 2014.
Nontawat Charoenphakdee, Jongyeong Lee, and Masashi Sugiyama. On symmetric losses for learning from corrupted labels. In ICML, pp. 961-970, 2019.
Chao Chen, Xiuyan Ni, Qinxun Bai, and Yusu Wang. A topological regularizer for classifiers via persistent homology. In AISTATS, pp. 2573-2582, 2019.
Pengfei Chen, Junjie Ye, Guangyong Chen, Jingwei Zhao, and Pheng-Ann Heng. Beyond class- conditional assumption: A primary attempt combat instance-dependent label noise. AAAI, 2021.
Jiacheng Cheng, Tongliang Liu, Kotagiri Ramamohanarao, and Dacheng Tao. Learning with bounded instance- and label-dependent label noise. In ICMI, pp. 1789-1799, 2020.
Hendrycks Dan, Lee Kimin, and Mazeika Mantas. Using pre-training can improve model robustness and uncertainty. ICMI., pp. 2712-2721, 2019.
Jun Du and Zhihua Cai. Modelling class noise with symmetric and asymmetric distributions. In AAAI, pp. 2589-2595, 2015.
Wei Gao, Bin-Bin Yang, and Zhi-Hua Zhou, On the resistance of nearest neighbor to random noisy labels. arXiv preprint 1007vv667..075500 2016.
Aritra Ghosh, Naresh Manwani, and P.S. Sastry. Making risk minimization tolerant to label noise. Neurocomput, 160:93-107, 2015.
Aritra Ghosh, Himanshu Kumar, and PS Sastry. Robust loss functions under label noise for deep neural networks. In AAAI, 2017.
Wei Hu, Zhiyuan Li, and Dingli Yu. Simple and effective regularization methods for training on noisily labeled data with generalization guarantee. In ICLR, 2020.
Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. 2009. URL
https://www. cs wtw.:cc...oooooo toronto. edw httpss///ww.....ooooocccccee//td
features 2009- TR
pdf
Kuang-Huci Lee, Xiaodong He, Lei Zhang, and Linjun Yang. Cleannet: Transfer learning for scalable image classifier training with label noise. In CVPR, pp. 5447-5456, 2018
Junnan Li, Yongkang Wong, Qi Zhao, and Mohan S Kankanhalli. Learning to learn from noisy labeled data. CVPR, pp. 5051-5059, 2019.
Yuncheng Li. Jianchao Yang, Yale Song, Liangliang Cao, Jiebo Luo, and Li-Jia Li. Learning from noisy labels with distillation. In /CCV, pp. 1928-1929999 1936, 2017.
10

---

Published as a conference paper at ICLR 2021
Jiang Lu, Zhou Zhengyuan, Leung Thomas, Li Li-Jia, and Fei-Fei Li. Mentoret: Learning data- driven curriculum for very deep neural networks on corrupted labels. In ICML, pp. 2309-2318, 2018.
Xingjun Ma, Yisen Wang, Michael E. Houle, Shuo Zhou, Sarah M. Erfani, Shu-Tao Xia, Sudanthi N. R. Wijewickrema, and James Bailey. Dimensionality-diii driven learning with noisy labels. In ICML, pp. 3361-3370, 2018.
Naresh Manwani and PS Sastry. Noise tolerance under risk minimization. IEEE transactions on cybernetics, 43(3):
2013.
Aditya Krishna Menon, Brendan Van Rooyen, and Nagarajan Natarajan. Learning from binary labels with instance-dependent noise. Machine Learning, 107(8):1561-1599 2018.
Nagarajan Natarajan, Inderjit S Dhillon, Pradeep K Ravikumar, and Ambuj Tewari. Learning with noisy labels. In NeurlPS, pp. 1204, 2013.
Giorgio Patrini, Alessandro Rozza, Aditya Krishna Menon, Richard Nock, and Lizhen Qu. Making deep neural networks robust to label noise: loss correction approach. In CVPR, pp. 2233-2241, 2017.
Scott Reed, Honglak Lee, Dragomir Anguelov, Christian Szegedy, Dumitru Erhan, and Andrew Rabinovich. Training deep neural networks on noisy labels with bootstrapping. In ICLR Workshop, 2014.
Mengye Ren, Wenyuan Zeng. Bin Yang. and Raquel Urtasun. Learning to reweight examples for robust deep learning. In ICML, pp. 4331-4340, 2018.
Yanyao Shen and Sujay Sanghavi. Learning with bad training data via iterative trimmed loss minimization. In ICML, pp. 17739-574,,22 2019.
Jun Shu, Qi Xie, Lixuan Yi, Qian Zhao, Sanping Zhou, Zongben Xu, and Deyu Meng. Meta- weight-net: Learning an explicit mapping for sample weighting. NeurIPS, pp. 1917-1928. 2019.
Hwanjun Song, Minseok Kim, and Jae-Gil Lee. Selfie: Refurbishing unclean samples for robust deep learning. ICML, pp. 5907-5915, 2019.
Daiki Tanaka, Daiki Ikami, Toshihiko Yamasaki, and Kiyoharu Aizawa. Joint optimization framework for learning with noisy labels. In CVPR, pp. 5552-5552666 5560, 2018.
Sunil Thulasidasan, Tanmoy Bhattacharya, Jeff Bilmes, Gopinath Chennupati, and Jamal Mohd- Yusof. Combating label noise in deep learning using abstention. In ICML, pp. 6234-6243, 2019.
Arash Vahdat. Toward robustness against label noise in training deep discriminative neural networks. In NeurlPS, pp. 5596-5605, 2017.
Brendan Van Rooyen, Aditya Menon, and Robert C Williamson. Learning with symmetric label noise: The importance of being unhinged. In NeurlPS, pp. 10-18, 2015.
Yisen Wang, Weiyang Liu, Xingjun Ma, James Bailey, Hongyuan Zha, Le Song, and Shu-Tao Xia. Iterative learning with open-set noisy labels. In CVPR, pp. 8688-8696, 2018.
Yisen Wang, Xingjun Ma, Zaiyi Chen, Yuan Luo, Jinfeng Yi, and James Bailey. Symmetric cross entropy for robust learning with noisy labels. In CVPR, pp. 322-330, 2019.
Pengxiang Wu, Songzhu Zheng, Mayank Goswami, Dimitris Metaxas, and Chao Chen. A topological filter for learning with label noise. In NeurlPS, 2020.
Tong Xiao, Tian Xia, Yi Yang, Chang Huang, and Xiaogang Wang. Learning from massive noisy labeled data for image classification. In CVPR, pp. 2691-26999 2015.
Yilun Xu, Peng Cao, Yuqing Kong, and Yizhou Wang. L dmi: A novel information theoretic loss function for training deep nets robust label noise. In NeurlPS, pp. 2222-633,, 2019.
11

---

Published as a conference paper at ICLR 2021
Yan Yan, Rómer Rosales, Glenn Fung, Ramanathan Subramanian, and Jennifer Dy. Learning from multiple annotators with varying expertise. Machine learning, 95(3):291-32) 2014.
Kun Yi and Jianxin Wu. Probabilistic end-to-end noise correction for learning with noisy labels, In CVPR. pp. 7017-7025, 2019.
Xingrui Yu, Bo Han, Jiangchao Yao, Gang Niu, Ivor Tsang, and Masashi Sugiyama. How does disagreement help generalization against label corruption? In ICML, pp. 7164-7173, 2019.
Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning requires rethinking generalization. In ICLR, 2017.
Zhilu Zhang and Mert Sabuncu. Generalized cross entropy loss for training deep neural networks with noisy labels. In NeurIPS, pp.
2018
Songzhu Zheng, Pengxiang Wu, Aman Goswami, Mayank Goswami, Dimitris Metaxas, and Chao Chen. Error-bounded correction of noisy labels. In ICML, pp. 11447-11455 2020.
A APPENDIX
Lemma (One round purity improvement). Suppose Assumption I is satisfied, and assume an f such that there exists pure (e, f, -level set with 3e S < 1.
2. Let ()) w)(w) if (xx) - 1/2| 2
and T)(x) if (x( - 1/2] < e, and assume fnew = arg min ((...))DD(m..... Loss((zz) ÿ). Let heH
Cnew = minfele > 0, L(e, 1)) is pure for Snew]. Then Gnew 2 (1 ( e).
Proof: We analyze the case where ny(z) > 1. The analysis on the other side can be derived similarly. Due to the fact that there exists a level set [[e, n) pure to f, we have S (m))x))
1 Va:
I (Ga m(x)) _ 2 n7()) ]
E (.E.))
Now consider a where 7 S !n(x)) 2 Since the distribution D is cc.. ('., -bounded, we have:
B ((s..)- (x)) [1 (U A (2)) (z)||(())) [|[()) 1 In(x)
1 2
=P= 02 # (=)))((((>))
1 2 In(x:)
2
Ps [ūx # (z)
In(x)
- 2 (()) I1
P P= ( +
g - n(2) < 2
P2 # (z), - < - +
P2 [2(1((z) b 2 (m( - 1ll
Pz - 2 Iv(x) - -
P. Pv # (*), +es [+)]
Px Pu # {2)
Px P>117(z) a1 (n(
II
P- P>llm(>) 31 -50
C²7
c -
( (
If 5) set (aosssiiis condition implies fnew (x) 17(x)) < 3e for x s.t. e e- S In(x)) 1 If e 3c, (x) will give the same label as 17" (z:) and thus (e 7, -)eeell set becomes pure for f- Meanwhile, the choice of y ensures that 1 Cnew 2 (1 ta
the impurity in super level set / + 7 is at most 2, The level
e).
Li
Lemma 2 (Warm-up rounds). Suppose for function Jo there exists a level set L(eo, 11) which is pure for for Given To < 1/2, after running Algorithm for m 2 la exists a level set TO} To, 1)) that is pure for Jo-
log( 2oo rounds, there
? I-2c0)
12

---

Published as a conference paper at ICLR 2021
Proof: The proof follows from the fact that each round of label flipping improves the purity by factor of (1 5. To obtain an at least To pure region, it suffices to repeat the flipping step for
m 2 ta log( To 1-200 rounds.
Lemma 3. Suppose Assumption I is satisfied, and for given function fo there exists level set
Lee, 1) which is pure for fo. If one runs Algorithm starting with fo and the initializations: (1)
To eo, (2) m 2 ta log( 2Tb
1-2e0 (og((12200>) (3) N 2 m + 3 log( 1)" (a))
1-65) ). (4) Tend S 3e and (5)
21o
A
ae' then we have IP P''-DWWI
3.
Proof: The proof can be done by combining Lemma and Lemma In the first iterations, by Lemma 2 we can guarantee level set ( To. 7) pure to f. In the rest of the iterations we ensure the level set [n(x) - žl 2 1/2 - '"' is pure. We increase 7' by a reasonable factor of B to avoid incurring too many corrupted labels while ensuring enough progress in label purification, i.e., a S B S 24 such that in the level set (m(x) - 1 1 - T we have [f 77(z) - 3s. This condition ensures the correctness of flipping when T S 2 3s. The purity cannot be improved once T 2 3 Tend since there is no guarantee that f fxx ) has consistent label with n)x) when (1)()) 2l < 3z and In(x) f(x)] I 3c. By (c., -b-buudddd assumption on D, its mass of impure 3e level set region is
most c.
Theorem 1. Under assumption 1, for any noise which is PMD with margin to, define en mao 1+2a/ ). Then for the output of Algorithm with f as above and with the following initial-
izations: (1) To 1 Eg. (2) m llog(
2To
(3) N Z m B
1 log( To (4) T Tend S 3e and (5)
20g
3 v 2c
at we have:
oZ
TP PonD (yf 1/" (a:) 2 c.
Proof: The proof is based Lemma plus verification of the existence of fo for which there exists a pure (eo: f, 1)) set. Let:
Txx) = ={
To( Toi (x)
'T()) > 1/2 17x)) < 1/2
| ca] S -o T(2). By level set (a, E) ccnnsistency, suffices satisfy a{} c. + 7) + Go ensure that f(x) has the same prediction with ry(x)) when [ı)(x) - 1 2 eg. By polynomial level set diminishing noise, we have T(x) < 2 cu if eu > to. and thus by choosing eu max((oo 142a one can ensure that initial fo
In the level set (л)(=) 2 co. P- P=(0z + 1/ (z)l |n(=)
has a pure (Co, fo: 17) level set. The rest of the proof follows from Lemma 3
13


Reviews:
[{"review_id": "uPoXsoSsvts", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "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 presents a learning method for the scenario of feature dependent label noise. A framework where label noise diminishes away from the decision boundary is established and a relabeling strategy based on this by relabeling highly confident points is proposed.  The method is a straight-forward adaptive method which the authors both theoretically and empirically explore in detail.\n\n# Pros\n\n- The approach is simple and easy to implement on top of existing methods\n- The authors support their simple method with some very nice theoretical results\n- Good empirical evaluation showing competitive performance to other methods\n- The paper is clearly written and easy to read\n- Citations place the work well among existing literature\n\n# Cons\n\n- The authors mention Menon et al. in their \"related works\" section, but dismiss it immediately as \"...it does not recalibrate individual data based on their contexts, and thus are not as effective as other deep-learning -based methods in practice.\" A citation here is needed showing this point, or further experiments.\n- The related works section is very short and is essentially a list of other approaches. A more thorough discussion would help readers.\n- A selection of baseline methods are chosen for comparison to the proposed approach in the empirical evaluation, but the particular choices aren't discussed in any detail. Some of the methods were mentioned in the related works section, but some are not (why not?), and neither section explains some of the choices.", "extra_scores": {}, "extra_text": {}}, {"review_id": "lovzCBL7xba", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "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 of paper**\n\nThe authors introduce a data-relabeling method that they claim is the first that both allows for data-dependent noise and is theoretically guaranteed to converge to an optimal model.\n\nThe authors introduce a novel family of label noise, called Polynomial Margin Diminishing (PMD), which defines a polynomially-decreasing upper bound on the label noise as the true label probability is above some threshold and as it approaches 1. Below the threshold (when the true label probability is closer to 0.5), the noise is unbounded.\n\nThe authors introduce an algorithm, \"Progressive Label Correction\", which iteratively flips the training labels of examples for which the model's confidence is above a threshold. The threshold decreases over time, so that only the most confident examples are flipped at first, and then the less-confident examples are flipped later.\n\nThe authors prove (Theorem 1) that under the assumption of PMD label noise distribution, as well as Assumption 1 concerning the flexibility of the hypothesis class and the continuity of the true label's conditional distribution, then their Progressive Label Correction algorithm asymptotically approaches a set of corrected labels that match the true (de-noised) labels with high probability.\n\nThe authors experimentally show that their algorithm consistently outperforms 5 alternatives on CIFAR-10 and CIFAR-100 datasets with various types of synthetic noise, both feature-dependent and hybrid feature-depedent/indepdendent. Finally, they show their algorithm outperforms 10 alternatives on a real-world dataset (Clothing1M) with unknown noise.\n\n**Conclusions**\n\nQuality: Overall I like this paper. It's a pretty simple algorithm to implement, and it seems to be quite effective in practice and have nice theoretical properties.\n\nClarity: The paper is structured very well. It is easy to follow the narrative and high-level ideas. There are a few minor typos (see below for some examples). The theory is relatively easy to follow.\n\nOriginality: I'm not familiar with the related work, but this appears to be original/novel from my limited perspective.\n\nSignificance: This algorithm can potentially be used to improve test accuracy on any supervised learning task, so the intended audience is quite large. The improvement on both synthetic and real data seems quite large. It's hard to tell whether the results were cherry-picked at all, but they are impressive.\n\n**Minor comments**\n\nFigre 1 caption has a typo: \"Red dots are the data that remain incorrect. that remain un-corrected and are closer to the\ndecision boundary.\"\n\nIn Section 2.1, \"illustrate the upperbound (red curve)\", but the figure actually shows an orange curve (not red) for the upper bound.\n\nFigure 2 caption, \"closed to 0 or 1\" should be \"close to 0 or 1\". Also, \"a equal probability\" should be \"an equal probability\".", "extra_scores": {}, "extra_text": {}}, {"review_id": "H0NCv1gozQ", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "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 work appears to original, and it deals with an important topic (ie, how to deal with noisy labels). The paper is well written and reasonably easy to follow. Figure 1 is extremely helpful in providing an intuitive explanation that helps understanding the rest of the paper.   \n\nEven though the empirical validation is reasonably thorough for a paper that also includes a theoretical analysis of the novel approach, it is here that the authors could improve the paper the most. The main weakness of this section is that even though the results on the synthetic datasets are strong, the ones on the Clothing1M domain are significantly less so, with two competing approaches (PENCIL  & MLTN) within 0.53% - 0.55% from the PCL result. Ideally, the paper should include another 2-3 real-world domains in this evaluation. At the very least, they could add to the evaluation the CUB-200 dataset from [Yi & Wu, 2019], on which PENCIL was evaluated for robustness on less noisy data.  Adding two more synthetic domains such as MNIST and ModelNet40, as done in [Zheng et al, 2020], is another possibility - but far less appealing.   ", "extra_scores": {}, "extra_text": {}}, {"review_id": "BvmU2V48tyB", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "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": "Comments:\nLabel noise is very frequently in many real world applications. However, the noise can be with different distributions. If we build the learning model under a certain distribution, it is difficult to capture the discriminative information. In this paper, without assuming that the noise is a certain distribution, the proposed method can handle the general noise, and it mainly target a new family of feature-dependent label noise, which is much more general than commonly used i.i.d. label noise and encompasses a broad spectrum of noise patterns. The experimental results show that the proposed method is promising. Meanwhile, the theoretical analysis of the proposed method is well inferred.\n\nStrong points:\n[1] The theoretical foundation of the proposed method is strong. \n[2] The experimental results of the proposed method are promising.\nWeak points:\n[1] Some details about the experiments are not clear, such as the experimental settings of the compared methods.\n[2] It is better to show the connection between the polynomial margin diminishing noise and the other noises.\n\nAccept reason:\n[1] The paper has shown a promising performance than several state-of-the-art methods. The noise assumption is more general than the traditional types. Hence, the paper may provide a novel way to deal with noise labels.\n\nFeedbacks:\n[1] I found that the step size \\beta has an influence on the threshold \\theta, and how to set it. It is necessary to show the details about \\beta, which has directly influence on the results.\n[2] The noise in the experiments is more than 30%. Whether the proposed method is suitable to the high-level noise. It is better to show the results without any noise.\n[3] Since the polynomial margin diminishing noise is general, whether the polynomial margin diminishing noise can represent any noise functions in theoretical.\n[4] The details of all the compared method may need to be provided.", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper studies the problem of learning from data that have been corrupted by label noise. The authors define a natural data-dependent noise condition, that allows the noise rate to be large close to the decision boundary, and provide a simple iterative method that eventually converges to the Bayes optimal classifier. The method is evaluated on both synthetic a real datasets. There was a consensus among the reviewers that this is an interesting contribution and I propose acceptance.
Decision: Accept (Spotlight)