INSTANCE-DEPENDENT LABEL NOISE: A SAMPLE SIEVE APPROACH
Year: 2021

Abstract:
Human-annotated labels are often prone to noise, and the presence of such noise will degrade the performance of the resulting deep neural network (DNN) models. Much of the literature (with several recent exceptions) of learning with noisy labels focuses on the case when the label noise is independent of features. Practically, annotations errors tend to be instance-dependent and often depend on the difficulty levels of recognizing a certain task. Applying existing results from instance-independent settings would require a significant amount of estimation of noise rates. Therefore, providing theoretically rigorous solutions for learning with instance-dependent label noise remains a challenge. In this paper, we propose CORES (COnfidence REgularized Sample Sieve), which progressively sieves out corrupted examples. The implementation of CORES does not require specifying noise rates and yet we are able to provide theoretical guarantees of CORES in filtering out the corrupted examples. This high-quality sample sieve allows us to treat clean examples and the corrupted ones separately in training a DNN solution, and such a separation is shown to be advantageous in the instance-dependent noise setting. We demonstrate the performance of CORES on CIFAR10 and CIFAR100 datasets with synthetic instance-dependent label noise and Clothing1M with real-world human noise. As of independent interests, our sample sieve provides a generic machinery for anatomizing noisy datasets and provides a flexible interface for various robust training techniques to further improve the performance. Code is available at https://github.com/UCSC-REAL/cores.

heading: 1 INTRODUCTION
text: Deep neural networks (DNNs) have gained popularity in a wide range of applications. The remarkable success of DNNs often relies on the availability of large-scale datasets. However, data annotation inevitably introduces label noise, and it is extremely expensive and time-consuming to clean up the corrupted labels. The existence of label noise can weaken the true correlation between features and labels as well as introducing artificial correlation patterns. Thus, mitigating the effects of noisy labels becomes a critical issue that needs careful treatment.
It is challenging to avoid overfitting to noisy labels, especially when the noise depends on both true labels Y and features X . Unfortunately, this often tends to be the case where human annotations are prone to different levels of errors for tasks with varying difficulty levels. Recent work has also shown that the presence of instance-dependent noisy labels imposes additional challenges and cautions to training in this scenario (Liu, 2021). For such instance-dependent (or feature-dependent, instance-based) label noise settings, theory-supported works usually focus on loss-correction which requires estimating noise rates (Xia et al., 2020; Berthon et al., 2020). Recent work by Cheng et al. (2020) addresses the bounded instance-based noise by first learning the noisy distribution and then distilling examples according to some thresholds.1 However, with a limited size of datasets, learning an accurate noisy distribution for each example is a non-trivial task. Additionally, the size and the quality of distilled examples are sensitive to the thresholds for distillation. ∗Equal contributions in alphabetical ordering. Hao leads experiments and Zhaowei leads theories. †Corresponding authors: Y. Liu and Z. Zhu {yangliu,zwzhu}@ucsc.edu. 1The proposed solution is primarily studied for the binary case in Cheng et al. (2020).
Departing from the above line of works, we design a sample sieve with theoretical guarantees to provide a high-quality splitting of clean and corrupted examples without the need to estimate noise rates. Instead of learning the noisy distributions or noise rates, we focus on learning the underlying clean distribution and design a regularization term to help improve the confidence of the learned classifier, which is proven to help safely sieve out corrupted examples. With the division between “clean” and “corrupted” examples, our training enjoys performance improvements by treating the clean examples (using standard loss) and the corrupted ones (using an unsupervised consistency loss) separately.
We summarize our main contributions: 1) We propose to train a classifier using a novel confidence regularization (CR) term and theoretically guarantee that, under mild assumptions, minimizing the confidence regularized cross-entropy (CE) loss on the instance-based noisy distribution is equivalent to minimizing the pure CE loss on the corresponding “unobservable” clean distribution. This classifier is also shown to be helpful for evaluating each example to build our sample sieve.2) We provide a theoretically sound sample sieve that simply compares the example’s regularized loss with a closed-form threshold explicitly determined by predictions from the above trained model using our confidence regularized loss, without any extra estimates. 3) To the best of our knowledge, the proposed CORES2 (COnfidence REgularized Sample Sieve) is the first method that is thoroughly studied for a multi-class classification problem, has theoretical guarantees to avoid overfitting to instance-dependent label noise, and provides high-quality division without knowing or estimating noise rates. 4) By decoupling the regularized loss into separate additive terms, we also provide a novel and promising mechanism for understanding and controlling the effects of general instancedependent label noise. 5) CORES2 achieves competitive performance on multiple datasets, including CIFAR-10, CIFAR-100, and Clothing1M, under different label noise settings. Other related works In addition to recent works by Xia et al. (2020), Berthon et al. (2020), and Cheng et al. (2020), we briefly overview other most relevant references. Detailed related work is left to Appendix A. Making the loss function robust to label noise is important for building a robust machine learning model (Zhang et al., 2016). One popular direction is to perform loss correction, which first estimates transition matrix (Patrini et al., 2017; Vahdat, 2017; Xiao et al., 2015; Zhu et al., 2021b; Yao et al., 2020b), and then performs correction/reweighting via forward or backward propagation, or further revises the estimated transition matrix with controllable variations (Xia et al., 2019). The other line of work focuses on designing specific losses without estimating transition matrices (Natarajan et al., 2013; Xu et al., 2019; Liu & Guo, 2020; Wei & Liu, 2021). However, these works assume the label noise is instance-independent which limits their extension. Another approach is sample selection (Jiang et al., 2017; Han et al., 2018; Yu et al., 2019; Northcutt et al., 2019; Yao et al., 2020a; Wei et al., 2020; Zhang et al., 2020a), which selects the “small loss” examples as clean ones. However, we find this approach only works well on the instance-independent label noise. Approaches such as label correction (Veit et al., 2017; Li et al., 2017; Han et al., 2019) or semi-supervised learning (Li et al., 2020; Nguyen et al., 2019) also lack guarantees for the instancebased label noise.
2 CORES2: CONFIDENCE REGULARIZED SAMPLE SIEVE Consider a classification problem on a set of N training examples denoted by D := {(xn, yn)}n∈[N ], where [N ] := {1, 2, · · · , N} is the set of example indices. Examples (xn, yn) are drawn according to random variables (X,Y ) ∈ X × Y from a joint distribution D. Let DX and DY be the marginal distributions of X and Y . The classification task aims to identify a classifier f : X → Y that maps X to Y accurately. One common approach is minimizing the empirical risk using DNNs with respect to the cross-entropy loss defined as `(f(x), y) = − ln(fx[y]), y ∈ [K], where fx[y] denotes the y-th component of f(x) andK is the number of classes. In real-world applications, such as human-annotated images (Krizhevsky et al., 2012; Zhang et al., 2017) and medical diagnosis (Agarwal et al., 2016), the learner can only observe a set of noisy labels. For instance, human annotators may wrongly label some images containing cats as ones that contain dogs accidentally or irresponsibly. The label noise of each instance is characterized by a noise transition matrix T (X), where each element Tij(X) := P(Ỹ = j|Y = i,X). The corresponding noisy dataset2 and distribution are denoted by D̃ := {(xn, ỹn)}n∈[N ] and D̃. Let 1(·) be the indicator function taking
2In this paper, the noisy dataset refers to a dataset with noisy examples. A noisy example is either a clean example (whose label is true) or a corrupted example (whose label is wrong).
value 1 when the specified condition is satisfied and 0 otherwise. Similar to the goals in surrogate loss (Natarajan et al., 2013), LDMI (Xu et al., 2019) and peer loss (Liu & Guo, 2020), we aim to learn a classifier f from the noisy distribution D̃ which also minimizes P(f(X) 6= Y ), (X,Y ) ∼ D. Beyond their results, we attempt to propose a theoretically sound approach addressing a general instance-based noise regime without knowing or estimating noise rates.

heading: 2.1 CONFIDENCE REGULARIZATION
text: In this section, we present a new confidence regularizer (CR). Our design of the CR is mainly motivated by a recently proposed robust loss function called peer loss (Liu & Guo, 2020). For each example (xn, ỹn), peer loss has the following form:
`PL(f(xn), ỹn) := `(f(xn), ỹn)− `(f(xn1), ỹn2), where (xn1 , ỹn1) and (xn2 , ỹn2) are two randomly sampled and paired peer examples (with replacement) for n. Let Xn1 and Ỹn2 be the corresponding random variables. Note Xn1 , Ỹn2 are two independent and uniform random variables being each xn′ , n′ ∈ [N ] and ỹn′ , n′ ∈ [N ] with probability 1N respectively: P(Xn1 = xn′ |D̃) = P(Ỹn2 = yn′ |D̃) = 1 N ,∀n
′ ∈ [N ]. Let DỸ |D̃ be the distribution of Ỹn2 given dataset D̃. Peer loss then has the following equivalent form in expectation:
1
N ∑ n∈[N ] EXn1 ,Ỹn2 |D̃[`(f(xn), ỹn)−`(f(Xn1), Ỹn2)]
= 1
N ∑ n∈[N ] [ `(f(xn), ỹn)− ∑ n′∈[N ] P(Xn1 = xn′ |D̃)EDỸ |D̃ [`(f(xn′), Ỹ )] ]
= 1
N ∑ n∈[N ] [ `(f(xn), ỹn)− ED Ỹ |D̃ [`(f(xn), Ỹ )] ] .
This result characterizes a new loss denoted by `CA:
`CA(f(xn), ỹn) := `(f(xn), ỹn)− ED Ỹ |D̃ [`(f(xn), Ỹ )]. (1)
Though not studied rigorously by Liu & Guo (2020), we show, under conditions3, `CA defined in Eqn. (1) encourages confident predictions4 from f by analyzing the gradients: Theorem 1. For `CA(·), solutions satisfying fxn [i] > 0,∀i ∈ [K] are not locally optimal at (xn, ỹn).
See Appendix B.2 for the proof. Particularly, in binary cases, we have constraint f(xn)[0] + f(xn)[1] = 1. Following Theorem 1, we know minimizing `CA(f(xn), ỹn) w.r.t f under this constraint leads to either f(xn)[0] → 1 or f(xn)[1] → 1, indicating confident predictions. Therefore, the addition of term −ED
Ỹ |D̃ [`(f(xn), Ỹ )] helps improve the confidence of the learned classifier.
Inspired by the above observation, we define the following confidence regularizer:
Confidence Regularizer: `CR(f(xn)) := −β · ED Ỹ |D̃ [`(f(xn), Ỹ )],
where β is positive and `(·) refers to the CE loss. The prior probability P(Ỹ |D̃) is counted directly from the noisy dataset. In the remaining of this paper, `(·) indicates the CE loss by default. Why are confident predictions important? Intuitively, when model fits to the label noise, its predictions often become less confident, since the noise usually corrupts the signal encoded in the clean data. From this perspective, encouraging confident predictions plays against fitting to label noise. Compared to instance-independent noise, the difficulties in estimating the instance-dependent noise rates largely prevent us from applying existing techniques. In addition, as shown by Manwani & Sastry (2013), the 0-1 loss function is more robust to instance-based noise but hard to optimize with. To a certain degree, pushing confident predictions results in a differentiable loss function that approximates the 0-1 loss, and therefore restores the robustness property. Besides, as observed by Chatterjee (2020) and Zielinski et al. (2020), gradients from similar examples would reinforce each other. When the overall label information is dominantly informative that Tii(X) > Tij(X), DNNs
3Detailed conditions for Theorem 1 are specified at the end of our main contents. 4Our observation can also help partially explain the robustness property of peer loss (Liu & Guo, 2020).
will receive more correct information statistically. Encouraging confident predictions would discourage the memorization of the noisy examples (makes it hard for noisy labels to reduce the confidence of predictions), and therefore further facilitate DNNs to learn the (clean) dominant information.
`CR is NOT the entropy regularization Entropy regularization (ER) is a popular choice for improving confidence of the trained classifiers in the literature (Tanaka et al., 2018; Yi & Wu, 2019). Given a particular prediction probability p for a class, the ER term is based on the function −p ln p, while our `CR is built on ln p. Later we show `CR offers us favorable theoretical guarantees for training with instance-dependent label noise, while ER does not. In Appendix C.1, we present both theoretical and experimental evidences that `CR serves as a better regularizer compared to ER.

heading: 2.2 CONFIDENCE REGULARIZED SAMPLE SIEVE
text: Intuitively, label noise misleads the training thus sieving corrupted examples out of datasets is beneficial. Furthermore, label noise introduces high variance during training even with the existence of `CR (discussed in Section 3.3). Therefore, rather than accomplishing training solely with `CR, we will first leverage its regularization power to design an efficient sample sieve. Similar to a general sieving process in physical words that compares the size of particles with the aperture of a sieve, we evaluate the “size” (quality, or a regularized loss) of examples and compare them with some to-be-specified thresholds, therefore the name sample sieve. In our formulation, the regularized loss `(f(xn), ỹn) + `CR(f(xn)) is employed to evaluate examples and αn is used to specify thresholds. Specifically, we aim to solve the sample sieve problem in (2).
Sample Sieve-0
Sample Sieve-1
The crucial components in (2) are:
• vn ∈ {0, 1} indicates whether example n is clean (vn = 1) or not (vn = 0); • αn (mimicking the aperture of a sieve) controls which example should be sieved out; • f̄ is a copy of f and does not contribute to the back-propagation. F is the search space of f . Dynamic sample sieve The problem in (2) is a combinatorial optimization which is hard to solve directly. A standard solution to (2) is to apply alternate search iteratively as follows:
• Starting at t = 1, v(0)n = 1,∀n ∈ [N ]. • Confidence-regularized model update (at iteration-t):
f (t) = arg min f∈F ∑ n∈[N ] v(t−1)n [`(f(xn), ỹn) + `CR(f(xn))] ; (3)
• Sample sieve (at iteration-t):
v(t)n = 1(`(f (t)(xn), ỹn) + `CR(f (t)(xn)) < αn,t), (4) where αn,t = 1K ∑ ỹ∈[K] `(f̄ (t)(xn), ỹ) + `CR(f̄ (t)(xn)), f (t) and v(t) refer to the specific classifier and weight at iteration-t. Note the values of `CR(f̄ (t)(xn)) and `CR(f (t)(xn)) are the same. We keep both terms to be consistent with the objective in Eq. (2). In DNNs, we usually update model f with one or several epochs of data instead of completely solving (3).
Figure 1 illustrates the dynamic sample sieve, where the size of each example corresponds to the regularized loss and the aperture of a sieve is determined by αn,t. In each iteration-t, sample sieve-
t “blocks” some corrupted examples by comparing a regularized example loss with a closed-form threshold αn,t, which can be immediately obtained given current model f̄ (t) and example (xn, ỹn) (no extra estimation needed). In contrast, most sample selection works (Han et al., 2018; Yu et al., 2019; Wei et al., 2020) focus on controlling the number of the selected examples using an intuitive function where the overall noise rate may be required, or directly selecting examples by an empirically set threshold (Zhang & Sabuncu, 2018). Intuitively, the specially designed thresholds αn,t for each example should be more accurate than a single threshold for the whole dataset. Besides, the goal of existing works is often to select clean examples while our sample sieve focuses on removing the corrupted ones. On a high level, we follow a different philosophy from these sample selection works. We coin our solution as COnfidence REgularized Sample Sieve (CORES2).
More visualizations of the sample sieve In addition to Figure 1, we visualize the superiority of our sample sieve with numerical results as Figure 2. The sieved dataset is in the form of two clusters of examples. Particularly, from Figure 2(b) and Figure 2(f), we observe that CE suffers from providing a good division of clean and corrupted examples due to overfitting in the final stage of training. On the other hand, with `CR, there are two distinct clusters and can be separated by the threshold 0 as shown in Figure 2(d) and Figure 2(h). Comparing Figure 2(a)-2(d) with Figure 2(e)-2(h), we find the effect of instance-dependent noise on training is indeed different from the symmetric one, where the instance-dependent noise is more likely to cause overfitting.
3 THEORETICAL GUARANTEES OF CORES2
In this section, we theoretically show the advantages of CORES2. The analyses focus on showing CORES2 guarantees a quality division, i.e. vn = 1(yn = ỹn),∀n, with a properly set β. To show the effectiveness of this solution, we call a model prediction on xn is better than random guess if fxn [yn] > 1/K, and call it confident if fxn [y] ∈ {0, 1},∀y ∈ [K], where yn is the clean label and y is an arbitrary label. The quality of sieving out corrupted examples is guaranteed in Theorem 2.
Theorem 2. The sample sieve defined in (4) ensures that clean examples (xn, ỹn = yn) will not be identified as being corrupted if the model f (t)’s prediction on xn is better than random guess.
Theorem 2 informs us that our sample sieve can progressively and safely filter out corrupted examples, and therefore improves division quality, when the model prediction on each xn is better than random guess. The full proof is left to Appendix B.3. In the next section, we provide evidences that our trained model is guaranteed to achieve this requirement with sufficient examples.

heading: 3.1 DECOUPLING THE CONFIDENCE REGULARIZED LOSS
text: The discussion of performance guarantees of the sample sieve focuses on a general instance-based noise transition matrix T (X), which can induce any specific noise regime such as symmetric noise and asymmetric noise (Kim et al., 2019; Li et al., 2020). Note the feature-independency was one critical assumption in state-of-the-art theoretically guaranteed noise-resistant literatures (Natarajan et al., 2013; Liu & Guo, 2020; Xu et al., 2019) while we do not require. Let Tij := ED|Y=i[Tij(X)],∀i, j ∈ [K]. Theorem 3 explicitly shows the contributions of clean examples, corrupted examples, and `CR during training. See Appendix B.1 for the proof.
Theorem 3. (Main Theorem: Decoupling the Expected Regularized CE Loss) In expectation, the loss with `CR can be decoupled as three separate additive terms:
ED̃ [ `(f(X), Ỹ ) + `CR(f(X)) ] = Term-1︷ ︸︸ ︷ T · ED[`(f(X), Y )] + Term-2︷ ︸︸ ︷ ∆̄ · ED∆ [`(f(X), Y )]
+ ∑ j∈[K] ∑ i∈[K]
P(Y = i)ED|Y=i[(Uij(X)− βP(Ỹ = j))`(f(X), j)]︸ ︷︷ ︸ Term-3
, (5)
where T := minj∈[K] Tjj , ∆̄ := ∑ j∈[K] ∆jP(Y = j), ∆j := Tjj −T , Uij(X) = Tij(X),∀i 6=
j, Ujj(X) = Tjj(X)−Tjj , and ED∆ [`(f(X), Y )] := 1(∆̄ > 0) ∑ j∈[K] ∆jP(Y =j) ∆̄ ED|Y =j [`(f(X), j)].
Equation (5) provides a generic machinery for anatomizing noisy datasets, where we show the effects of instance-based label noise on the `CR regularized loss can be decoupled into three additive terms: Term-1 reflects the expectation of CE on clean distributionD, Term-2 shifts the clean distribution by changing the prior probability of Y , and Term-3 characterizes how the corrupted examples (represented by Uij(X)) might mislead/mis-weight the loss, as well as the regularization ability of `CR (represented by βP(Ỹ = j)). In addition to the design of sample sieve, this additive decoupling structure also provides a novel and promising perspective for understanding and controlling the effects of generic instance-dependent label noise.

heading: 3.2 GUARANTEES OF THE SAMPLE SIEVE
text: By decoupling the effects of instance-dependent noise into separate additive terms as shown in Theorem 3, we can further study under what conditions, minimizing the confidence regularized CE loss on the (instance-dependent) noisy distribution will be equivalent to minimizing the true loss incurred on the clean distribution, which is exactly encoded by Term-1. In other words, we would like to understand when Term-2 and Term-3 in (5) can be controlled not to disrupt the minimization of Term-1. Our next main result establishes this guarantee but will first need the following two assumptions. Assumption 1. (Y ∗ = Y ) Clean labels are Bayes optimal (Y ∗ := arg maxi∈[K] P(Y = i|X)). Assumption 2. (Informative datasets) The noise rate is bounded as Tii(X) − Tij(X) > 0,∀i ∈ [K], j ∈ [K], j 6= i,X ∼ DX .
Feasibility of assumptions: 1) Note for many popular image datasets, e.g. CIFAR, the label of each feature is well-defined and the corresponding distribution is well-separated by human annotation. In this case, each feature X only belongs to one particular class Y . Thus Assumption 1 is generally held in classification problems (Liu & Tao, 2015). Technically, this assumption could be relaxed. We use this assumption for clean presentations. 2) Assumption 2 shows the requirement of noise rates, i.e., for any featureX , a sufficient number of clean examples are necessary for dominant clean information. For example, we require Tii(X) − Tij(X) > 0 to ensure examples from class i are informative (Liu & Chen, 2017).
Before formally presenting the noise-resistant property of training with `CR, we discuss intuitions here. As discussed earlier in Section 2.1, our `CR regularizes the CE loss to generate/incentivize confident prediction, and thus is able to approximate the 0-1 loss to obtain its robustness property. More explicitly, from (5), `CR affects Term-3 with a scale parameter β. Recall that Uij(X) = Tij(X),∀i 6= j, which is exactly the noise transition matrix. Although we have no information about this transition matrix, the confusion brought by Uij(X) can be canceled or reversed by a sufficiently large β such that Uij(X) − βP(Ỹ = j) ≤ 0. Intuitively, with an appropriate β, all the effects of Uij(X), i 6= j can be reversed, and we will get a negative loss punishing the classifier for predicting class-j when the clean label is i. Formally, Theorem 4 shows the noise-resistant property of training with `CR and is proved in Appendix B.4. Theorem 4. (Robustness of the Confidence Regularized CE Loss) With Assumption 1 and 2, when
max i,j∈[K],X∼DX
Uij(X)
P(Ỹ = j) ≤ β ≤ min P(Ỹ =i)>P(Ỹ =j),X∼DX Tii(X)− Tij(X) P(Ỹ = i)− P(Ỹ = j) , (6)
minimizing ED̃[`(f(X), Ỹ ) + `CR(f(X))] is equivalent to minimizing ED[`(f(X), Y )].
Theorem 4 shows a sufficient condition of β for our confidence regularized CE loss to be robust to instance-dependent label noise. The bound on LHS ensures the confusion from label noise could be
canceled or reversed by the β weighted confidence regularizer, and the RHS bound guarantees the model with the minimized regularized loss predicts the most frequent label in each feature w.p. 1.
Theorem 4 also provides guidelines for tuning β. Although we have no knowledge about Tij(X), we can roughly estimate the range of possible β. One possibly good setting of β is linearly increasing with the number of classes, e.g. β = 2 for 10 classes and β = 20 for 100 classes.
With infinite model capacity, minimizing ED[`(f(X), Y )] returns the Bayes optimal classifier (since CE is a calibrated loss) which predicts on each xn better than random guess. Therefore, with a sufficient number of examples, minimizing ED̃[`(f(X), Ỹ ) + `CR(f(X))] will also return a model that predicts better than random guess, then satisfying the condition required in Theorem 2 to guarantee the quality of sieved examples. Further, since the Bayes optimal classifier always predicts clean labels confidently when Assumption 1 holds, Theorem 4 also guarantees confident predictions. With such predictions, the sample sieve in (4) will achieve 100% precision on both clean and corrupted examples. This guaranteed division is summarized in Corollary 1:
Corollary 1. When conditions in Theorem 4 hold, with infinite model capacity and sufficiently many examples, CORES2 achieves vn = 1(yn = ỹn),∀n ∈ [N ], i.e., all the sieved clean examples are effectively clean.

heading: 3.3 TRAINING WITH SIEVED SAMPLES
text: We discuss the necessity of a dynamic sample sieve in this subsection. Despite the strong guarantee in expectation as shown Theorem 4, performing direct Empirical Risk Minimization (ERM) of the regularized loss is likely to return a sub-optimal solution. Although Theorem 4 guarantees the equivalence of minimizing two first-order statistics, their second-order statistics are also important for estimating the expectation when examples are finite. Intuitively, Term-1 T · ED[`(f(X), Y )] primarily helps distinguish a good classifier from a bad one on the clean distribution. The existence of the leading constant T reduces the power of the above discrimination, as effectively the gap between the expected losses become smaller as noise increases (T will decrease). Therefore we would require more examples to recognize the better model. Equivalently, the variance of the selection becomes larger. In Appendix C.2, we also offer an explanation from the variance’s perspective. For some instances with extreme label noise, the β satisfying Eqn. (6) in Theorem 4 may not exist. In such case, these instances cannot be properly used and other auxiliary techniques are necessary (e.g., sample pruning).
Sieving out the corrupted examples from the clean ones allows us a couple of better solutions. First, we can focus on performing ERM using these sieved clean examples only. We derive the risk bound for training with these clean examples in Appendix C.3. Secondly, leveraging the sample sieve to distinguish clean examples from corrupted ones provides a flexible interface for various robust training techniques such that the performance can be further improved. For example, semisupervised learning techniques can be applied (see section 4 for more details).

heading: 4 EXPERIMENTS
text: Now we present experimental evidences of how CORES2 works. 5
Datasets: CORES2 is evaluated on three benchmark datasets: CIFAR-10, CIFAR-100 (Krizhevsky et al., 2009) and Clothing1M (Xiao et al., 2015). Following the convention from Xu et al. (2019), we use ResNet34 for CIFAR-10 and CIFAR-100 and ResNet50 for Clothing1M.
Noise type: We experiment with three types of label noise: symmetric, asymmetric and instancedependent label noise. Symmetric noise is generated by randomly flipping a true label to the other possible labels w.p. ε (Kim et al., 2019), where ε is called the noise rate. Asymmetric noise is generated by flipping the true label to the next class (i.e., label i→ i+1, mod K) w.p. ε. Instancedependent label noise is a more challenging setting and we generate instance-dependent label noise following the method from Xia et al. (2020) (See Appendix D.3 for details). In expectation, the noise rate ε for all noise regimes is the overall ratio of corrupted examples in the whole dataset.
Consistency training after the sample sieve: Let τ be the last iteration of CORES2. Define L(τ) := {n|n ∈ [N ], v(τ)n = 1}, H(τ) := {n|n ∈ [N ], v(τ)n = 0}, D̃L(τ) := {(xn, ỹn) : n ∈
5The logarithmic function in `CR is adapted to ln(fx[y] + 10−8) for numerical stability.
20 40 60 80 1000.0 0.2 0.4 0.6 0.8 1.0 Fsc or e
(a) 20% Symm. 20 40 60 80 1000.0
0.2 0.4 0.6 0.8 1.0
(b) 40% Symm. 20 40 60 80 1000.0
0.2 0.4 0.6 0.8 1.0
(c) 60% Symm.
20 40 60 80 100 epoch
0.0 0.2 0.4 0.6 0.8 1.0 Fsc or e
(d) 20% Inst.
CORES2 Co-teaching Co-teaching+
20 40 60 80 100 epoch
0.0 0.2 0.4 0.6 0.8 1.0
(e) 40% Inst. 20 40 60 80 100
epoch 0.0 0.2 0.4 0.6 0.8 1.0
(f) 60% Inst.
Figure 3: F-score comparisons on CIFAR10 under symmetric (Symm.) and instance-based (Inst.)
label noise. F-score := 2·Pre·RePre+Re , where Pre :=
∑
n∈[N] 1(vn=1,yn=ỹn)∑ n∈[N] 1(vn=1) , and Re :=
∑
n∈[N] 1(vn=1,yn=ỹn)∑ n∈[N] 1(yn=ỹn) .
L(τ)}, D̃H(τ) := {(xn, ỹn) : n ∈ H(τ)}. Thus D̃L(τ) is sieved as clean examples and D̃H(τ) is filtered out as corrupted ones. Examples (xn, ỹn) ∈ D̃L(τ) lead the training direction using the CE loss as ∑ n∈L(τ) `(f(xn), ỹn). Noting the labels in D̃H(τ) are supposed to be corrupted and can distract the training, we simply drop them. On the other hand, feature information of these examples encodes useful information that we can further leverage to improve the generalization ability of models. There are different ways to use this unsupervised information, in this paper, we chose to minimize the KL-divergence between predictions on the original feature and the augmented feature to make predictions consistent. This is a common option as chosen by Li et al. (2019), Xie et al. (2019), and Zhang et al. (2020b). The consistency loss function in epoch-t is ∑ n∈H(τ) `KL(f(xn), f̄
(t)(xn,t)), where f̄ (t) is a copy of the DNN at the beginning of epoch-t but without gradients. Summing the classification and consistency loss yields the total loss. See Appendix D.1 for an illustration.
Other alternatives: Checking the consistency of noisy predictions is only one possible way to leverage the additional information after sample sieves. Our basic idea of first sieving the dataset and then treating corrupted examples differently from clean ones admits other alternatives. There are many other possible designs after sample sieves, e.g., estimating transition matrix using sieved examples then applying loss-correction (Patrini et al., 2017; Vahdat, 2017; Xiao et al., 2015), making the consistency loss as another regularization term and retraining the model (Zhang et al., 2020b), correcting the sample selection bias in clean examples and retraining (Cheng et al., 2020; Fang et al., 2020), or relabeling those corrupted examples and retraining, etc. Additionally, clustering methods on the feature space (Han et al., 2019; Luo et al., 2020) or high-order information (Zhu et al., 2021a) can also be exploited along with the dynamic sample sieve. Besides, the current structure is ready to include other techniques such as mixup (Zhang et al., 2018).
Quality of our sample sieve: Figure 3 shows the F-scores of sieved clean examples with training epochs on the symmetric and the instance-based label noise. F-score quantifies the quality of the sample sieve by the harmonic mean of precision (ratio of actual cleans examples in sieved clean ones) and recall (ratio of sieved cleans examples in actual clean ones). We compare CORES2 with Co-teaching and Co-teaching+. Note the F-scores of CORES2 and Co-teaching are consistently high on the symmetric noise, while CORES2 achieves higher performance on the challenging instancebased label noise, especially with the 60% noise rate where the other two methods have low F-scores.
Experiments on CIFAR-10, CIFAR-100 and Clothing1M: In this section, we compare CORES2 with several state-of-the-art methods on CIFAR-10 and CIFAR-100 under instance-based, symmetric and asymmetric label noise settings, which is shown on Table 1 and Table 2. CORES2? denotes that we apply consistency training on the corrupted examples after the sample sieve. For a fair comparison, all the methods use ResNet-34 as the backbone. By comparing the performance of CE on the symmetric and the instance-based label noise, we note the instance-based label noise is a more challenging setting. Even though some methods (e.g., LDMI) behaves well on symmetric and asymmetric label noise, they may reach low test accuracies on the instance-based label noise, especially when the noise rate is high or the dataset is more complex. However, CORES2 consistently works well on the instance-based label noise and adding the consistency training gets better results. Table 3 verifies CORES2 on Clothing1M, a dataset with real human label noise. Compared to the other
approaches, CORES2 also works fairly well on the Clothing1M dataset. See more experiments in Appendix D. We also provide source codes with detailed instructions in supplementary materials.

heading: 5 CONCLUSIONS
text: This paper introduces CORES2, a sample sieve that is guaranteed to be robust to general instancedependent label noise and sieve out corrupted examples, but without using explicit knowledge of the noise rates of labels. The analysis of CORES2 assumed that the Bayes optimal labels are the same as clean labels. Future directions of this work include extensions to more general cases where the Bayes optimal labels may differ from clean labels. We are also interested in exploring different possible designs of robust training with sieved examples.
Acknowledgement This work is partially supported by the National Science Foundation (NSF) under grant IIS-2007951 and the Office of Naval Research under grant N00014-20-1-22.

heading: CONDITIONS REQUIRED FOR THEOREM 1
text: Theorem 1 holds based on the following three assumptions:
A1. The model capacity is infinite (i.e., it can realize arbitrary variation). A2. The model is updated using the gradient descent algorithm (i.e. updates follow the direction
of decreasing ED [`(f(X), Y )]− EDY [EDX [` (f(X), Y )]]).
A3. The derivative of network function ∂f(x;w)∂wi is smooth (i.e. the network function has no singular point), where wi’s are model parameters.

heading: APPENDIX
text: The appendices are organized as follows. Section A presents the full version of related works. Section B details the proofs for our theorems. Section C supplements other necessary evidences to justify CORES2. Section D shows more experimental details and results.

heading: A FULL VERSION OF RELATED WORKS
text: Learning with noisy labels has observed exponentially growing interests. Since the traditional crossentropy (CE) loss has been proved to easily overfit noisy labels (Zhang et al., 2016), researchers try to design different loss functions to handle this problem. There were two main perspectives on designing loss functions. Considering the fact that outputs of logarithm functions in the CE loss grow explosively when the prediction f(x) approaches zero, some researchers tried to design bounded loss functions (Amid et al., 2019; Wang et al., 2019; Gong et al., 2018; Ghosh et al., 2017). To avoid relying on fine-tuning of hyper-parameters in loss functions, a meta-learning method was proposed bt Shu et al. (2020) to combine the above four loss functions together. However, simply considering loss function values without discussing the noise type and the corresponding statistics could not be noise-tolerant as defined by Manwani & Sastry (2013). As a complementary, others started from noise types and tried to design noise-tolerant loss functions. Based on the assumption that label noise only depends on the true class (a.k.a. feature-independent or label-dependent), an unbiased loss function called surrogate loss (Natarajan et al., 2013), an information-based loss function called LDMI (Xu et al., 2019), and a new family of loss functions to punish agreements between classifiers and noisy datasets called peer loss (Liu & Guo, 2020) were proposed. They proved theoretically that training DNNs using their loss functions on feature-independent noisy datasets was equivalent to training CE on the corresponding unobservable clean datasets. However, surrogate loss focused on the binary classifications and required knowing noise rates. LDMI and peer loss does not require knowing noise rates while LDMI may not be easy for extension and multi-class classification of peer loss requires particular transition matrices.
The correction approach is also popular in handling label noise. Previous works (Patrini et al., 2017; Vahdat, 2017; Xiao et al., 2015) assumed the feature-independent noise transition matrix was given or could be estimated and attempted to use it to correct loss functions. For example, Patrini et al. (2017) first estimated the noise transition matrix and then relied on it to correct forward or backward propagation during training. However, without a set of clean examples, the noise transition matrix could be hard to estimate correctly. Instead of correcting loss functions, some methods directly corrected labels (Veit et al., 2017; Li et al., 2017; Han et al., 2019), whereas it might introduce extra noise and damage useful information. Recent works (Xia et al., 2020; Berthon et al., 2020) extended loss-correction from the limited feature-independent label noise to part-dependent or a more general instance-dependent noise regime while they relied heavily on the noise rate estimation.
Sample selection (Jiang et al., 2017; Han et al., 2018; Yu et al., 2019; Yao et al., 2020a; Wei et al., 2020) mainly focused on exploiting the memorization of DNNs and treating the “small loss” examples as clean ones, while they only focused on feature-independent label noise. Cheng et al. (2020) tried to distill some examples relying on the predictions using the surrogate loss function (Natarajan et al., 2013). Note estimating noise rates are necessary for both applying surrogate loss and determining the threshold for distillation. The sample selection methods could be implemented with some semi-supervised learning techniques to improve the performance, where the corrupted examples were treated as unlabeled data (Li et al., 2020; Nguyen et al., 2019). However, the training mechanisms of these methods were still based on the CE loss, which could not be guaranteed to avoid overfitting to label noise.

heading: B PROOF FOR THEOREMS
text: In this section, we firstly present the proof for Theorem 3 (our main theorem) in Section B.1, which provides a generic machinery for anatomizing noisy datasets. Then we will respectively prove Theorem 1 in Section B.2, Theorem 2 in Section B.3, and Theorem 4 in Section B.4 according to the order they appear.

heading: B.1 PROOF FOR THEOREM 3
text: Theorem 3. (Main Theorem: Decoupling the Expected Regularized CE Loss) In expectation, the loss with `CR can be decoupled as three separate additive terms:
ED̃ [ `(f(X), Ỹ ) + `CR(f(X)) ] = Term-1︷ ︸︸ ︷ T · ED[`(f(X), Y )] + Term-2︷ ︸︸ ︷ ∆̄ · ED∆ [`(f(X), Y )]
+ ∑ j∈[K] ∑ i∈[K]
P(Y = i)ED|Y=i[(Uij(X)− βP(Ỹ = j))`(f(X), j)]︸ ︷︷ ︸ Term-3
, (7)
where T := minj∈[K] Tjj , ∆̄ := ∑ j∈[K] ∆jP(Y = j), ∆j := Tjj −T , Uij(X) = Tij(X),∀i 6=
j, Ujj(X) = Tjj(X)−Tjj , and ED∆ [`(f(X), Y )] := 1(∆̄ > 0) ∑ j∈[K] ∆jP(Y =j) ∆̄ ED|Y =j [`(f(X), j)].
Proof. The expected form of traditional CE loss on noisy distribution D̃ can be written as
ED̃[`(f(X), Ỹ )] = ∑ j∈[K] ∑ i∈[K] P(Y = i)ED|Y=i[Tij(X)`(f(X), j)]
= ∑ j∈[K] ∑ i∈[K] P(Y = i)TijED|Y=i[`(f(X), j)] + ∑ j∈[K] ∑ i∈[K] P(Y = i)CovD|Y=i(Tij(X), `(f(X), j)).
The first term could be transformed as:
∑ j∈[K] ∑ i∈[K] P(Y = i)TijED|Y=i[`(f(X), j)]
= ∑ j∈[K] TjjP(Y = j)ED|Y=j [`(f(X), j)] + ∑ i∈[K],i6=j TijP(Y = i)ED|Y=i[`(f(X), j)]  =TED[`(f(X), Y )] + ∆̄ED∆ [`(f(X), Y )] +
∑ j∈[K] ∑ i∈[K],i6=j TijP(Y = i)ED|Y=i[`(f(X), j)],
where
T := min j∈[K] Tjj , ∆̄ := ∑ j∈[K] ∆jP(Y = j), ∆j := Tjj − T ,
and
ED∆ [`(f(X), Y )] :=
{∑ j∈[K] ∆jP(Y=j) ∆̄
ED|Y=j [`(f(X), j)], if ∆̄ > 0, 0 if ∆̄ = 0.
Then
ED̃[`(f(X), Ỹ )] =TED[`(f(X), Y )] + ∆̄ED∆ [`(f(X), Y )] + ∑ j∈[K] ∑ i∈[K],i 6=j TijP(Y = i)ED|Y =i[`(f(X), j)],
+ ∑ j∈[K] ∑ i∈[K] P(Y = i)CovD|Y =i(Tij(X), `(f(X), j))
=TED[`(f(X), Y )] + ∆̄ED∆ [`(f(X), Y )] + ∑ j∈[K] ∑ i∈[K],i 6=j TijP(Y = i)ED|Y =i[`(f(X), j)],
+ ∑ j∈[K] ∑ i∈[K],i 6=j P(Y = i)ED|Y =i[(Tij(X)− Tij)(`(f(X), j)− ED|Y =i[`(f(X), j)])]
+ ∑ j∈[K] P(Y = j)ED|Y =j [(Tjj(X)− Tjj)(`(f(X), j)− ED|Y =j [`(f(X), j)])]
=TED[`(f(X), Y )] + ∆̄ED∆ [`(f(X), Y )] + ∑ j∈[K] ∑ i∈[K],i 6=j P(Y = i)ED|Y =i[(Tij(X)− Tij)(`(f(X), j)− ED|Y =i[`(f(X), j)]) + Tij`(f(X), j)]
+ ∑ j∈[K] P(Y = j)ED|Y =j [(Tjj(X)− Tjj)(`(f(X), j)− ED|Y =j [`(f(X), j)])]
=TED[`(f(X), Y )] + ∆̄ED∆ [`(f(X), Y )] + ∑ j∈[K] ∑ i∈[K],i 6=j P(Y = i)ED|Y =i[Tij(X)`(f(X), j)]
+ ∑ j∈[K] P(Y = j)ED|Y =j [(Tjj(X)− Tjj)`(f(X), j)]
=TED[`(f(X), Y )] + ∆̄ED∆ [`(f(X), Y )] + ∑ j∈[K] ∑ i∈[K] P(Y = i)ED|Y =i[Uij(X)`(f(X), j)],
where Uij(X) = Tij(X),∀i 6= j, Ujj(X) = Tjj(X)− Tjj .
The expected form of `CR on noisy distribution D̃ can be written as ED̃ [`CR(f(xi))] = −βED̃ [ ED Ỹ |D̃ [`(f(xi), Ỹ )] ] = −β
∫ D̃ [ P(D̃)ED Ỹ |D̃ [`(f(xi), Ỹ )] ] = −β
∑ j∈[K] P(Ỹ = j)EDX [`(f(xi), j)]
= − ∑ j∈[K] ∑ i∈[K] P(Y = i)ED|Y=i[βP(Ỹ = j)`(f(xi), j)].
Thus the expected form of the new regularized loss is ED̃ [ `(f(X), Ỹ ) + `CR(f(xi)) ] = TED[`(f(X), Y )] + ∆̄ED∆ [`(f(X), Y )]
+ ∑ j∈[K] ∑ i∈[K] P(Y = i)ED|Y=i[(Uij(X)− βP(Ỹ = j))`(f(X), j)]. (8)

heading: B.2 PROOF FOR THEOREM 1
text: Theorem 1. For `CA(·), solutions satisfying fxn [i] > 0,∀i ∈ [K] are not locally optimal at (xn, ỹn).
Proof. Let `(·) be the CE loss. Note this proof does not rely on whether the data distribution is clean or not. We use D to denote any data distribution and D to denote the corresponding dataset. This
notation applies only to this proof. For any data distribution D, we have ED [ `(f(X), Y )− EDY |D [`(f(xn), Y )] ] =ED [`(f(X), Y )]− EDY [EDX [` (f(X), Y )]]
=− ∫ DX dx ∑ y∈[K] P(x, y) ln fx[y] + ∫ DX dx ∑ y∈[K] P(x)P(y) ln fx[y]
=− ∫ DX dx ∑ y∈[K] ln fx[y][P(x, y)− P(x)P(y)].
The dynamical analyses are based on the following three assumptions:
A1. The model capacity is infinite (i.e., it can realize arbitrary variation).
A2. The model is updated using the gradient descent algorithm (i.e. updates follow the direction of decreasing ED [`(f(X), Y )]− EDY [EDX [` (f(X), Y )]]).
A3. The derivative of network function ∂f(x;w)∂wi is smooth (i.e. the network function has no singular point), where wi’s are model parameters.
Denote the variations of fx[y] during one gradient descent update by ∆y(x). From Lemma 1, it can be explicitly written as
∆y(x) = fx[y] · η ∫ DX dx′ ∑ y′∈[K] [P(x′, y′)− P(x′)P(y′)] ∑ i∈[K] Gi(x, y)Gi(x ′, y′), (9)
where η is the learning rate,
Gi(x, y) = − ∂gy(x) ∂wi + ∑ y′∈[K] fx[y ′] ∂gy′(x) ∂wi ,
and gy(x) is the network output before the softmax activation. i.e.
fx[y] = exp(gy(x))∑
y′∈[K] exp(gy′(x)) .
With ∆y(x), the variation of the regularized loss is ∆ED [`(f(X), Y ) + `CR] = − ∫ DX dxP(x) ∑ y∈[K] ∆y(x) P(y|x)− P(y) fx[y] . (10)
If the training reaches a steady state (a.k.a. local optimum), we have ∆ED [`(f(X), Y ) + `CR] = 0. To check the property of this variation, consider the following example. For a particular x0, define
F (x0) := ∑ y∈[K] ∆y(x0) P(y|x0)− P(y) fx0 [y] .
Split the labels y into the following two sets (without loss of generality, we ignore the P(y|x0) − P(y) = 0 cases): Yx0;− = {y : P(y|x0)− P(y) < 0} and Yx0;+ = {y : P(y|x0)− P(y) > 0}. By assigning ∆y(x0) = ay < 0,∀y ∈ Yx0;− and ∆y(x0) = by > 0,∀y ∈ Yx0;+, one finds F (x0) > 0 since fx0 [y] > 0. Note we have an extra constraint ∑ y ∆y(x0) = 0 to ensure∑
y∈[K] fx0 [y] = 1 after update. It is easy to check our assigned ay and by could maintain this constraint by introducing a weight Nab to scale b′y as follows.∑
y∈Y− ay +Nab ∑ y∈Y+ b′y = 0, by = Nabb ′ y.
Let B (x0) be a -neighbourhood of x0. Since fx[y] is continuous, we can set ∆y(x) = 12 (1 + cos π‖x−x0‖ )∆y(x0),∀x ∈ B (x0) and 0 otherwise. The coefficient 1 2 (1 + cos π‖x−x0‖ ) is added so that the continuity of fx[y] preserves. This choice will lead to ∆ED [`(f(X), Y ) + `CR] < 0. Therefore, for any `CA(f(xn), yn) with solution fxn [i] > 0,∀i ∈ [K], we can always find a decreasing direction, indicating the solution is not (steady) locally optimal. Note D can be any distribution in this proof. Thus the result holds for the noisy distribution D̃.
Lemma 1. ∆y(x) = fx[y] · η ∫ DX dx′ ∑ y′∈[K] [P(x′, y′)− P(x′)P(y′)] ∑ i∈[K] Gi(x, y)Gi(x ′, y′).
Proof. We need to take into account the actual form of activation function, i.e., the softmax function, as well as the SGD algorithm to demonstrate the correctness of this lemma. The variation ∆y0(x0) is caused by the change in network parameters {wi}, i.e.,
∆y0(x0) = ∑ i∈[K] ∂fx0 [y0] ∂wi δwi, (11)
where δwi are determined by the SGD algorithm
δwi =− η ∂ED [`(f(X), Y ) + `CR]
∂wi =η ∑∫ x,y P(x, y)− P(x)P(y) fx[y] ∂fx[y] ∂wi .
Plugging back to (11) yields ∆y0(x0) = η ∑∫ x,y P(x, y)− P(x)P(y) fx[y] ∑ i∈[K] ∂fx0 [y0] ∂wi ∂fx[y] ∂wi .
To proceed, we need to expand ∂fx[y]∂wi . Taking into account the activation function, one has
fx[y] = exp(gy(x))∑
y′∈[K] exp(gy′(x)) ,
where gy(x) refers to the network output before passed to the activation function. Recall that, by our assumption, derivatives ∂f(x;w)∂wi are not singular. Now we have
∂fx[y] ∂wi = ∂e−gy(x) ∂wi 1∑ y′∈[K] e −gy′ (x) + e−gy(x) ∂ ∂wi
( 1∑
y′∈[K] e −gy′ (x)
)
= −e−gy(x)∑
y′∈[K] e −gy′ (x)
∂gy(x)
∂wi + e−gy(x)(∑ y′′∈[K] e −gy′′ (x) )2 ∑ y′∈[K] e−gy′ (x) ∂gy′(x) ∂wi
=fx[y] −∂gy(x) ∂wi + ∑ y′∈[K] fx[y ′] ∂gy′(x) ∂wi  . For simplicity, we can rewrite the above result as
∂fx[y]
∂wi = fx[y]Gi(x, y),
where
Gi(x, y) := − ∂gy(x) ∂wi + ∑ y′ fx[y ′] ∂gy′(x) ∂wi
is a smooth function.
Combining all the above gives ∆y0(x0) as follows. ∆y0(x0) = fx0 [y0] · η ∑∫ x,y [P(x, y)− P(x)P(y)] ∑ i Gi(x0, y0)Gi(x, y)

heading: B.3 PROOF FOR THEOREM 2
text: Theorem 2. The sample sieve defined in (4) ensures that clean examples (xn, ỹn = yn) will not be identified as being corrupted if the model f (t)’s prediction on xn is better than random guess.
Proof. Let yn be the true label corresponding to feature xn. For a clean sample, we have ỹn = yn. Consider an arbitrary DNN model f . With the CE loss, we have `(f(xn), yn) = − ln(fxn [yn]). According to Equation (4) in the paper, the necessary and sufficient condition of vn > 0 is
`(f(xn), ỹn) + `CR(f(xn)) < αn ⇔ − ln(fxn [yn]) < − 1
K ∑ y∈[K] ln(fxn [y])
⇔ − ln(fxn [yn]) < − 1 K − 1 ∑
y∈[K],y 6=yn
ln(fxn [y]).
By Jensen’s inequality we have
− ln (
1− fxn [yn] K − 1
) = − ln (∑ y∈[K],y 6=yn fxn [y]
K − 1
) ≤ − 1 K − 1 ∑
y∈[K],y 6=yn
ln(fxn [y]).
Therefore, when (sufficient condition) − ln(fxn [yn]) < − ln (
1− fxn [yn] K − 1
) ⇔ fxn [yn] > 1
K ,
we have vn > 0. Inequality fxn [yn] > 1 K indicates the model prediction is better than random guess.

heading: B.4 PROOF FOR THEOREM 4
text: Before proving Theorem 4, we need to show the effect of adding Term-2 to Term-1 in (5). Let X < 0.5 be the measure of separation among classes w.r.t feature X in distribution D, i.e., P(Y = Y ∗|X) = 1− X , (X,Y ) ∼ D, where Y ∗ := arg maxi∈[K] P(Y = i|X) is the Bayes optimal label. Let D′ be the shifted distribution by adding Term-2 to Term-1 and Y ′ be the shifted label. Then P(X|Y ) = P(X|Y ′),∀(X,Y ) ∼ D, (X,Y ′) ∼ D′ but P(Y ′) may be different from P(Y ). Lemma 2 shows the invariant property of this label shift.
Lemma 2. Label shift does not change the Bayes optimal label of feature X when X < min∀i,j∈[K]
( Tjj
Tii+Tjj
) .
Proof. Consider the shifted distribution D′. Let
TED[`(f(X), Y )] + ∆̄ED∆ [`(f(X), Y )] = CED′ [`(f(X), Y )],
where ED′ [`(f(X), Y )] := ∑ j∈[K] P(Y ′ = j)ED′|Y ′=j [`(f(X), j)],
and
P(Y ′ = j) := TjjP(Y = j)
C , where C := ∑ j∈[K] TjjP(Y = j) is a constant for normalization. For each possible Y = i, we have P(Y = i|X) ∈ [0, X ] ∪ {1− X}, X < 0.5. Thus
P(X|Y = i) = P(Y = i|X)P(X) P(Y = i) ∈ [0, XP(X) P(Y = i) ] ∪ {P(X)(1− X) P(Y = i) }.
Compare D′ and D, we know there is a label shift (Alexandari et al., 2020; Storkey, 2009), where P(X|Y = i) = P(X|Y ′ = i) but P(Y ) and P(Y ′) may be different. To ensure the label shift does not change the Bayes optimal label, we need
Y ∗ = arg max i∈[K] P(Y ′ = i|X) = arg max i∈[K] P(X|Y ′ = i)P(Y ′ = i) P(X) , (X,Y ′) ∼ D.
One sufficient condition is
XP(Y ′ = i) P(Y = i) < (1− X)P(Y ′ = j) P(Y = j) ⇒ X < min ∀i,j∈[K]
( Tjj
Tii + Tjj
)
With Lemma 2, Assumption 1, and Assumption 2, we present the proof for Theorem 4 as follows.
Theorem 4. (Robustness of the Confidence Regularized CE Loss) With Assumption 1 and 2, when
max i,j∈[K],X∼DX
Uij(X)
P(Ỹ = j) ≤ β ≤ min P(Ỹ=i)>P(Ỹ=j),X∼DX Tii(X)− Tij(X) P(Ỹ = i)− P(Ỹ = j) ,
minimizing ED̃[`(f(X), Ỹ ) + `CR(f(X))] is equivalent to minimizing ED[`(f(X), Y )].
Proof. It is easy to check X = 0,∀X ∼ DX when Assumption 1 holds. Thus adding Term-2 to Term-1 in (5) does not change the Bayes optimal label. With Assumption 1, the Bayes optimal classifier on the clean distribution should satisfy f∗(X)[Y ] = 1,∀(X,Y ) ∼ D. On one hand, when β ≥ maxi,j∈[K],X∼DX Uij(X)/P(Ỹ = j), we have
βij(X) := Uij(X)− βP(Ỹ = j) ≤ 0,∀i, j ∈ [K], X ∼ DX .
In this case, minimizing the regularization term results in confident predictions. On the other hand, to make it unbiased to clean results, β could not be arbitrarily large. We need to find the upper bound on β such that f∗ also minimizes the loss defined in the latter regularization term. Assume there is no loss on confident true predictions and there is one miss-prediction on example (xn, yn = j1), i.e., the prediction changes from the Bayes optimal prediction fxn [j1] = 1 to fxn [j2] = 1, j2 6= j1. Compared to the optimal one, the first two terms in the right side of (5) is increased by Tj1,j1`0, where `0 > 0 is the regret of one confident wrong prediction. Accordingly, the last term in the right side of (5) is increased by (βj1,j1(X)− βj1,j2(X))`0. It is supposed that
Tj1,j1`0 + (βj1,j1(xn)− βj1,j2(xn))`0 ≥ 0,∀j1, j2 ∈ [K],
which is equivalent to
β(P(Ỹ = j1)− P(Ỹ = j2)) ≤ Tj1,j1(xn)− Tj1,j2(xn),∀j1, j2 ∈ [K].
Thus
β ≤ min P(Ỹ=j1)>P(Ỹ=j2),X∼DX Tj1,j1(X)− Tj1,j2(X) P(Ỹ = j1)− P(Ỹ = j2) .
By mathematical inductions, it can be generalized to the case with multiple miss-predictions in the CE term.

heading: C OTHER JUSTIFICATIONS
text: In this section, we first compare `CR and entropy regularization in Section C.1 and highlight our superiority with both theoretical and experimental evidence, then show an example for explaining the variances incurred by label noise in Section C.2, and provide the risk bound in Section C.3 for training with the sieved examples that satisfy Corollary 1.
C.1 COMPARING `CR WITH ENTROPY REGULARIZATION
For simplicity, we consider two-class classification problem. Suppose for a given feature x, the probability of x belonging to class 1 is p. The entropy regularization (ER) can be written as:
RER(p) = −(p ln p+ (1− p) ln(1− p)), (12)
while our regularization term is written as:
RCR(p) = ln p+ ln(1− p). (13)
We have the following proposition:
Proposition 1. `CR regularizes models stronger than the entropy regularization in terms of gradients.
Proof. First notice that both RER and RCR are symmetric functions around p = 0.5. Thus we can only consider the situation where 0 < p < 0.5. The gradients w.r.t p are:
∂RER(p) ∂p = −(ln p− ln(1− p)) = ln(1 p − 1),
and ∂RCR(p)
∂p =
1 p − 1 1− p .
Now we compare the absolute value of two gradients. When 0 < p < 0.5, it is easy to check
∂RER(p)
∂p = ln(
1 p − 1) < 1 p − 2 < 1 p − 1 1− p = ∂RCR(p) ∂p ,
and both gradients are larger than 0. Therefore, `CR has larger gradients than the entropy regularization, i.e., `CR has stronger regularization ability than ER.
We can also draw a figure to show this phenomenon. Figure 4 shows the value of RCR and RER with respect to p. We can see the gradient of our regularization is larger than entropy regularization, resulting in a more confident prediction. We also perform an experiment to further show the evidence. Table 4 records comparison results which show our regularization achieves higher accuracy compared to the entropy term.
C.2 CALCULATING varD(`(f∗D(X), Y )) AND varD̃[`(f ∗ D(X), Ỹ ) + `CR(f ∗ D(X))]
Consider optimal classifier f∗D := arg minf ED[`(f(X), Y )]. Let `max be the upper bound of the `(·) loss, and `min be the lower bound of the `(·) loss. Denote ε by the over noise rate (ratio of corrupted examples in all examples).
For varD(`(f∗D(X), Y )), we know the loss `(f ∗ D(xn), yn) = `min for each example. Thus the variance is varD(`(f∗D(X), Y )) = 0.
For varD̃[`(f ∗ D(X), Ỹ ) + `CR(f ∗ D(X))], we know the loss `(f ∗ D(xn), ỹ = yn) = `min, and the loss `(f∗D(xn), ỹ 6= yn) = `max. Note
`CR = (K − 1)`max + `min
K for each example. The expectation is
ED̃[`(f ∗ D(X), Ỹ ) + `CR(f ∗ D(X))] = ε`max + (1− ε)`min + `CR.
Thus the variance is
varD̃[`(f ∗ D(X), Ỹ ) + `CR(f ∗ D(X))]
=ε(`max + `CR − (ε`max + (1− ε)`min + `CR))2 + (1− ε)(`min + `CR − (ε`max + (1− ε)`min + `CR))2
=ε(1− ε)(`max − `min)2.
We know in this example,
varD̃[`(f ∗ D(X), Ỹ ) + `CR(f ∗ D(X))] = ε(1− ε)(`max − `min)2 varD(`(f∗D(X), Y )) = 0.

heading: C.3 ANALYSIS FOR THE RISK BOUND
text: Let D̃L∗ and D̃L∗ be the set and the distribution of the sieved clean examples according to Corollary 1. We know they are supposed to contain only clean examples. Define RD(f) := ED[`(f(X), Y )], f∗D := arg minf RD(f), R̂D̃L∗ ,γ(f) := 1 |L∗| ∑ n∈L∗ [γ(xn)`(f(xn), ỹn)], f̂D̃L∗ ,γ := arg minf∈F R̂D̃L∗ ,γ(f), where γ(X) := PD(X)/PD̃L∗ (X) stands for the importance of each example to correct sample bias such that RD(f) = ED̃L∗ [γ(X)`(f(X), Ỹ )]. The weight γ(X) can be estimated by kernel mean matching (Huang et al., 2007) and its DNN adaption (Fang et al., 2020). Let D̃L∗,X be the marginal distribution of D̃L∗ on X . For example, with a particular kernel Φ(X), the optimization problem is:
min γ(X)
‖EDX [Φ(X)]− ED̃L∗,X [γ(X)Φ(X)]‖
s.t. γ(X) > 0 and ED̃L∗,X [γ(X)] = 1.
Note the selection of kernel Φ(·) is non-trivial, especially for complicated features. See (Fang et al., 2020) for a detailed DNN solutions.
Corollary 2 provides a risk bound for minimizing CE after sample sieve.
Corollary 2. If γ · ` is [0, b]-valued, then for any δ > 0, with probability at least 1− δ, we have
RD(f̂D̃L∗ ,γ)−RD(f ∗ D) ≤ 2R(γ ◦ ` ◦ F) + 2b
√ log(1/δ)
2|L∗| ,
where the Rademacher complexity R(γ ◦ ` ◦ F) := ED̃L∗ ,σ[supf∈F 2 |L∗| ∑ n∈L∗ σnγ(xn)`(f(xn), ỹn)] and {σn∈L∗} are independent Rademacher variables.
Proof. The sieved clean examples may be biased due to the covariate shift caused by instancebased label noise. One solution to such shift is re-weighting D̃L∗ to match D using importance re-weighting. Particularly, we need to estimate parameters γ(X) such that
RD(f) = RD̃L∗ ,γ(f) := ED̃L∗ [γ(X)`(f(X), Ỹ )].
With the optimal γ(X), the ERM should be changed as
f̂D̃L∗ ,γ := arg min f∈F R̂D̃L∗ ,γ(f),
where R̂D̃L∗ ,γ(f) := 1 |L∗| ∑ n∈L∗ [γ(xn)`(f(xn), ỹn)].
Via Hoeffding’s inequality, ∀f , w.p. at least 1− δ, we have
|R̂D̃L∗ ,γ(f)−RD̃L∗ ,γ(f)| ≤ R(` ◦ F) + 2b
√ ln(1/δ)
2|L∗| .
Following the basic Rademacher bound (Bartlett & Mendelson, 2002) on the maximal deviation between the expected empirical risks:
RD(f̂D̃L∗ ,γ)−RD(f ∗ D)
=RD̃L∗ ,γ(f̂D̃L∗ ,γ)−RD̃L∗ ,γ(f ∗ D̃L∗ ,γ )
= [ R̂D̃L∗ ,γ(f̂D̃L∗ ,γ)− R̂D̃L∗ ,γ(f ∗ D̃L∗ ,γ ) + ( RD̃L∗ ,γ(f̂D̃L∗ ,γ)− R̂D̃L∗ ,γ(f̂D̃L∗ ,γ) ) + ( R̂D̃L∗ ,γ(f ∗ D̃L∗ ,γ )−RD̃L∗ ,γ(f ∗ D̃L∗ ,γ ) )]
≤0 + 2 max f∈F |R̂D̃L∗ ,γ(f)−RD̃L∗ ,γ(f)|
≤2R(γ ◦ ` ◦ F) + 2b
√ ln(1/δ)
2|L∗| ,
where the Rademacher complexity R(γ ◦ ` ◦ F) := ED̃L∗ ,σ[supf∈F 2 |L∗| ∑ n∈L∗ σnγ(xn)`(f(xn), ỹn)] and {σn∈L∗} are independent Rademacher variables. Therefore, we get Corollary 2.
Corollary 2 informs us that, theoretically, the sample sieve is biased and γ(X) is necessary to correct the selection bias. However, the error induced by estimating γ(X) may degrade the performance. In addition, it is easy to check the optimal solution of performing direct ERM on the sieved clean examples is the same as f∗D in expectation when Assumption 1 holds.

heading: D MORE DETAILS AND RESULTS FOR EXPERIMENTS
text: We firstly show our training framework in Section D.1, then show implementation details and discussions in Section D.2. The algorithm for generating the instance-dependent label noise is provided in Section D.3. We show more experiments in Section D.4 and the ablation study in Section D.5.
D.1 ILLUSTRATION OF THE TRAINING FRAMEWORK
Our experiments follows the framework shown in Figure 5.
D.2 IMPLEMENTATION DETAILS AND MORE ANALYSIS
Implementation details on CIFAR-10 and CIFAR-100 with instance-based label noise: The basic hyper-parameters settings for CIFAR-10 and CIFAR-100 are listed as follows: mini-batch size (64), optimizer (SGD), initial learning rate (0.1), momentum (0.9), weight decay (0.0005), number of epochs (100) and learning rate decay (0.1 at 50 epochs). Standard data augmentation is applied to each dataset. CORES2 and baseline share the same hyper-parameters setting except for α and β in equation 2. When perform CORES2, We first train network on the dataset for 10 warm-up epochs with only CE (Cross Entropy) loss. Then β is linearly increased from 0 to 2 for next 30 epochs and kept as 2 for the rest of the epochs. The data selection is performed at the 30 epoch and αn,t is set to 1K ∑ ỹ∈[K] `(f̄ (t)(xn), ỹ) + `CR(f̄ (t)(xn)) in epoch-t as the paper suggests.
When performing CORES2?, we used the sieved result at epoch-40. It is worth noting that at that time, the sample sieve may not reach the highest test accuracy. However, the division property brought by the confidence regularizer works well at that time. We use the default setting from UDA (Xie et al., 2019) to apply efficient data augmentation.
Implementation details on Clothing-1M: We train the network for 120 epochs on 1 million noisy training images. Batch-size is set to 32. The initial learning rate is set as 0.01 and reduced by a factor of 10 at 30, 60, 90 epochs. For each epoch, we sample 1000 mini-batches from the training data while ensuring the (noisy) labels are balanced. Mixup strategy is employed to further avoid the overfitting problem (Zhang et al., 2018; Li et al., 2020). β is set to 0 at first 80 epochs, and linearly increased to 0.4 for next 20 epochs and kept as 0.4 for the rest of the epochs. It is worth noting that Clothing-1M actually does not satisfy our Assumption 2 since the class “Knitwear” (denoted by class-i) and the class “Sweater” (denoted by class-j) can not satisfy Tii(X)− Tij(X) > Tii − Tjj . Note consistency training is not implemented on Clothing-1M.
More analysis on β: The value of β mainly affects the sample sieve in CORES2. From Theorem 3 and Theorem 4 in the paper, when β is set to be small, we do not have the good division property. When β is set to be large, the training is biased to the CE term. Figure 6 visualize this phenomenon. It can be seen that in the left and right figure, many clean examples and corrupted examples overlap together located in the left and right clusters, respectively.
Algorithm 1 Instance-Dependent Label Noise Generation

heading: Input:
text: 1: Clean examples (xn, yn) N n=1; Noise rate: ε; Size of feature: 1× S; Number of classes: K.

heading: Iteration:
text: 2: Sample instance flip rates qn from the truncated normal distribution N (ε, 0.12, [0, 1]); 3: Sample W ∈ RS×K from the standard normal distribution N (0, 12); for n = 1 to N do 4: p = xn ·W // Generate instance dependent flip rates. The size of p is 1×K. 5: pyn = −∞ // Only consider entries different from the true label 6: p = qn · softmax(p) // Let qn be the probability of getting a wrong label 7: pyn = 1− qn // Keep clean w.p. 1− qn 8: Randomly choose a label from the label space as noisy label ỹn according to p; end for Output: 9: Noisy examples (xi, ỹn) N n=1.

heading: D.3 GENERATING THE INSTANCE-DEPENDENT LABEL NOISE
text: In this section, we introduce how to generate instance-based label noise which is illustrated in Algorithm 1. Note this algorithm follows the state-of-the-art method (Xia et al., 2020). Define the noise rate (the global flipping rate) as ε. First, in order to control ε but without constraining all of the instances to have a same flip rate, we sample their flip rates from a truncated normal distribution N(ε, 0.12, [0, 1]), where [0, 1] indicates the range of the truncated normal distribution. Second, we sample parameters W from the standard normal distribution for generating instance-dependent label noise. The size of W is S ×K, where S denotes the length of each feature. For each instance (xn, yn), we use Step 5 and Step 6 to ensure that the probability of getting a wrong label is qn. Step 7 ensures the sum of all the entries of p is 1.
Suppose there are two features: xi and xj where xi = xj . Then the possibility p of these two features, calculated by x ·W , from the Algorithm 1, would be exactly the same. Thus the label noise is strongly instance-dependent.

heading: D.4 MORE EXPERIMENTS ON CIFAR-10 AND TINY-IMAGENET
text: In this section, we compare CORES2 with more methods on CIFAR-10 and Tiny-Imagenet. Table 5 records the comparison results with recent benchmark methods. Table 6 compares CORES2 with other methods on Tiny-ImageNet. Both tables show that CORES2 achieves competitive results.

heading: D.5 ABLATION STUDY
text: CORES2 (without consistency training): By optimizing loss in (2), the model can be forced to concentrate only on clean examples. Thus even without consistency training, the network trained by CORES2 is also noise-robust. Table 7 compares CORES2 with other noise-robust methods which do not apply semi-supervised setting in the framework. We can see CORES2 still achieves the best performance among all the methods.
CORES2 without confidence regularization or dynamic data selection: The loss in equation 2 consists of data selection strategy and confident regularization term. To see how they influence the final accuracy, we perform the ablation study to show their effect on Table 8. The first row of Table 8 corresponds to the traditional CE loss. The second row corresponds to the sample sieve with CE
loss. The third row is the typical CORES2. The last row is CORES2?. We can see both the dynamic sample sieve in (4) and the confidence-regularized model update in (3) show positive effects on the final accuracy, which suggests the rationality of CORES2.

Review summaries:
The paper introduces a noise-robust loss function CORES2, motivated by peer loss. The novel loss adds a regularization term that promotes confident prediction and pushes the model prediction away from the prior of the label. Using this loss function, the authors propose a dynamic sample sieve to separate the clean data and corrupted data on-the-fly, by the magnitude of CORES2 loss. The author's approach is to rule out samples whose losses are larger than an adaptive threshold. Importantly, the process of sieving successfully sieves out corrupted samples, both in a theory of 'better than random guess classifier' and in practice. The authors, then show that the proposed CORES2 can be decoupled under the instance-dependent noise setting. Then CORES2 is proved to be noise-robust, which means CORES2 is equivalent to minimizing the original cross-entropy loss. They also show a principle approach for finding the hyperparameters $\beta$. Further, a consistency loss is adopted after sample sieve on the corrupted samples. The author conducts extensive experiments, including CIFAR10, CIFAR100, and Clothing1M under different settings of noise. CORES2 achieves the SOTA results in all the experiments.

The authors of the paper propose a new method, the CORES (COnfidence REgularized Sample Sieve), to tackle the important problem of learning under instance dependent label noise. The proposed method, in essence, involves the use of a confidence regularization term that encourages more confident predictions and a sieving process to remove the samples with large losses. Theoretical justification and empirical experiments were conducted to demonstrate the effectiveness of the proposed method.