Year: 2022

Abstract:
In learning with noisy labels, the sample selection approach is very popular, which regards small-loss data as correctly labeled during training. However, losses are generated on-the-fly based on the model being trained with noisy labels, and thus large-loss data are likely but not certain to be incorrect. There are actually two possibilities of a large-loss data point: (a) it is mislabeled, and then its loss decreases slower than other data, since deep neural networks “learn patterns first”; (b) it belongs to an underrepresented group of data and has not been selected yet. In this paper, we incorporate the uncertainty of losses by adopting interval estimation instead of point estimation of losses, where lower bounds of the confidence intervals of losses derived from distribution-free concentration inequalities, but not losses themselves, are used for sample selection. In this way, we also give large-loss but less selected data a try; then, we can better distinguish between the cases (a) and (b) by seeing if the losses effectively decrease with the uncertainty after the try. As a result, we can better explore underrepresented data that are correctly labeled but seem to be mislabeled at first glance. Experiments demonstrate that the proposed method is superior to baselines and robust to a broad range of label noise types.

heading: 1 INTRODUCTION
text: Learning with noisy labels is one of the most challenging problems in weakly-supervised learning, since noisy labels are ubiquitous in the real world (Mirzasoleiman et al., 2020; Yu et al., 2019; Nishi et al., 2021; Arazo et al., 2019; Yang et al., 2021a; Bai & Liu, 2021). For instance, both crowdsourcing and web crawling yield large numbers of noisy labels everyday (Han et al., 2018). Noisy labels can severely impair the performance of deep neural networks with strong memorization capacities (Zhang et al., 2017; Zhang & Sabuncu, 2018; Pleiss et al., 2020; Lukasik et al., 2020; Chen et al., 2022).
To reduce the influence of noisy labels, a lot of approaches have been recently proposed (Natarajan et al., 2013; Liu & Tao, 2016; Ma et al., 2018; Yang et al., 2021b; Zheng et al., 2020; Xia et al., 2019; 2020; Tanaka et al., 2018; Malach & Shalev-Shwartz, 2017; Li et al., 2020b; Menon et al., 2018; Thekumparampil et al., 2018; Xu et al., 2019; Kim et al., 2019; Jiang et al., 2020; Harutyunyan et al., 2020). They can be generally divided into two main categories. The first one is to estimate the noise transition matrix (Patrini et al., 2017; Shu et al., 2020; Hendrycks et al., 2018; Yang et al., 2021c; Wu et al., 2022), which denotes the probabilities that clean labels flip into noisy labels. However, the noise transition matrix is hard to be estimated accurately, especially when the number of classes is large (Yu et al., 2019). The second approach is sample selection, which is our focus in this paper. This approach is based on selecting possibly clean examples from a mini-batch for training (Han et al., 2018; Wang et al., 2018; Yao et al., 2020a; Wang et al., 2019; Yu et al., 2019; Lee et al., 2019; Wang et al., 2019; Yao et al., 2022). Intuitively, if we can exploit less noisy data for network parameter updates, the network will be more robust.
A major question in sample selection is what criteria can be used to select possibly clean examples. At the present stage, the selection based on the small-loss criteria is the most common method, and has been verified to be effective in many circumstances (Han et al., 2018; Jiang et al., 2018; Yu et al.,
†Corresponding author
2019; Wei et al., 2020; Yao et al., 2020a). Specifically, since deep networks learn patterns first (Arpit et al., 2017), they would first memorize training data of clean labels and then those of noisy labels with the assumption that clean labels are of the majority in a noisy class. Small-loss examples can thus be regarded as clean examples with high probability. Therefore, in each iteration, prior methods (Han et al., 2018; Wei et al., 2020) select the small-loss examples based on the predictions of the current network for robust training.
However, such a selection procedure is debatable, since it arguably does not consider uncertainty in selection. The uncertainty comes from two aspects. First, this procedure has uncertainty about small-loss examples. Specifically, the procedure uses limited time intervals and only exploits the losses provided by the current predictions. For this reason, the estimation for the noisy class posterior is unstable (Yao et al., 2020b), which causes the network predictions to be equally unstable. It thus takes huge risks to only use losses provided by the current predictions (Figure 1, left). Once wrong selection is made, the inferiority of accumulated errors will arise (Yu et al., 2019). Second, this procedure has uncertainty about large-loss examples. To be specific, deep networks learn easy examples at the beginning of training, but ignore some clean examples with large losses. Nevertheless, such examples are always critical for generalization. For instance, when learning with imbalanced data, distinguishing the examples with non-dominant labels are more pivotal during training (Menon et al., 2020). Deep networks often give large losses to such examples (Figure 1, right). Therefore, when learning under the realistic scenes, e.g., learning with noisy imbalanced data, prior sample selection methods cannot address such an issue well.
To relieve the above issues, we study the uncertainty of losses in the sample selection procedure to combat noisy labels. To reduce the uncertainty of small-loss examples, we extend time intervals and utilize the mean of training losses at different training iterations. In consideration of the bad influence of mislabeled data on training losses, we build two robust mean estimators from the perspectives of soft truncation and hard truncation w.r.t. the truncation level, respectively. Soft truncation makes the mean estimation more robust by holistically changing the behavior of losses. Hard truncation makes the mean estimation more robust by locally removing outliers from losses. To reduce the uncertainty of large-loss examples, we encourage networks to pick the sample that has not been selected in a conservative way. Furthermore, to address the two issues simultaneously, we derive concentration inequalities (Boucheron et al., 2013) for robust mean estimation and further employ statistical confidence bounds (Auer, 2002) to consider the number of times an example was selected during training.
The study of uncertainty of losses in learning with noisy labels can be justified as follows. In statistical learning, it is known that uncertainty is related to the quality of data (Vapnik, 2013). Philosophically, we need variety decrease for selected data and variety search for unselected data, which share a common objective, i.e., reduce the uncertainty of data to improve generalization (Moore, 1990). This is our original intention, since noisy labels could bring more uncertainty because of the low quality of noisy data. Nevertheless, due to the harm of noisy labels for generalization, we need to strike a good balance between variety decrease and search. Technically, our method is specially designed for
handling noisy labels, which robustly uses network predictions and conservatively seeks less selected examples meanwhile to reduce the uncertainty of losses and then generalize well.
Before delving into details, we clearly emphasize our contributions in two folds. First, we reveal prior sample selection criteria in learning with noisy labels have some potential weaknesses and discuss them in detail. The new selection criteria are then proposed with detailed theoretical analyses. Second, we experimentally validate the proposed method on both synthetic noisy balanced/imbalanced datasets and real-world noisy datasets, on which it achieves superior robustness compared with the stateof-the-art methods in learning with noisy labels. The rest of the paper is organized as follows. In Section 2, we propose our robust learning paradigm step by step. Experimental results are discussed in Section 3. The conclusion is given in Section 4.

heading: 2 METHOD
text: In this section, we first introduce the problem setting and some background (Section 2.1). Then we discuss how to exploit training losses at different iterations (Section 2.2). Finally, we introduce the proposed method, which exploits training losses at different iterations more robustly and encourages networks to pick the sample that is less selected but could be correctly labeled (Section 2.3).

heading: 2.1 PRELIMINARIES
text: Let X and Y be the input and output spaces. Consider a k-class classification problem, i.e., Y = [k], where [k] = {1, . . . , k}. In learning with noisy labels, the training data are all sampled from a corrupted distribution on X × Y . We are given a sample with noisy labels, i.e., S̃ = {(x, ỹ)}, where ỹ is the noisy label. The aim is to learn a robust classifier that could assign clean labels to test data by only exploiting a training sample with noisy labels.
Let f : X → Rk be the classifier with learnable parameters w. At the i-th iteration during training, the parameters of the classifier f can be denoted as wi. Let ` : Rk × Y → R be a surrogate loss function for k-class classification. We exploit the softmax cross entropy loss in this paper. Given an arbitrary training example (x, ỹ), at the i-th iteration, we can obtain a loss `i, i.e., `i = `(f(wi;x), ỹ). Hence, until the t-th iteration, we can obtain a training loss set Lt about the example (x, ỹ), i.e., Lt = {`1, . . . , `t}. In this paper, we assume that the training losses in Lt conform to a Markov process, which is to represent a changing system under the assumption that future states only depend on the current state (the Markov property). More specifically, at the i-th iteration, if we exploit an optimization algorithm for parameter updates (e.g., the stochastic gradient descent algorithm (Bottou, 2012)) and omit other dependencies (e.g., S̃), we will have P (wi|wi−1, . . . ,w0) = P (wi|wi−1), which means that the future state of the classifier f only depends on the current state. Furthermore, given a training example and the parameters of the classifier f , we can determine the loss of the training example as discussed. Therefore, the training losses in Lt will also conform to a Markov process.

heading: 2.2 EXTENDED TIME INTERVALS
text: As limited time interval cannot address the instability issue of the estimation for the noisy class posterior well (Pleiss et al., 2020), we extend time intervals and exploit the training losses at different training iterations for sample selection. One straightforward idea is to use the mean of training losses at different training iterations. Hence, the selection criterion could be
µ̃ = 1
t t∑ i=1 `i. (1)
It is intuitive and reasonable to use such a selection criterion for sample selection, since the operation of averaging can mitigate the risks caused by the unstable estimation for the noisy class posterior, following better generalization. Nevertheless, such a method could arguably achieve suboptimal classification performance for learning with noisy labels. The main reason is that, due to the great harm of mislabeled data, part of training losses are with too large uncertainty and could be seen as outliers. Therefore, it could be biased to use the mean of training losses consisting of such outliers (Diakonikolas et al., 2020), which further influences sample selection. More evaluations for our claims are provided in Section 3.

heading: 2.3 ROBUST MEAN ESTIMATION AND CONSERVATIVE SEARCH
text: We extend time intervals and meanwhile exploit the training losses at different training iterations more robustly. Specifically, we build two robust mean estimators from the perspectives of soft truncation and hard truncation (Catoni, 2012). Note that for specific tasks, it is feasible to decide the types of robust mean estimation with statistical tests based on some assumptions (Chakrabarty & Samorodnitsky, 2012). We leave the analysis as future work. Two distribution-free robust mean estimators are introduced as follows.
Soft truncation. We extend a classical M-estimator from (Catoni, 2012) and exploit the widest possible choice of the influence function. More specifically, give a random variable X , let us consider a non-decreasing influence function ψ : R→ R such that
ψ(X) = log(1 +X +X2/2), X ≥ 0. (2) The choice of ψ is inspired by the Taylor expansion of the exponential function, which can make the estimation results more robust by reducing the side effect of extremum holistically. The illustration for this influence function is provided in Appendix A.1. For our task, given the observations on training losses, i.e., Lt = {`1, . . . , `t}, we estimate the mean robustly as follows:
µ̃s = 1
t t∑ i=1 ψ(`i). (3)
We term the above robust mean estimator (3) the soft estimator.
Hard truncation. We propose a new robust mean estimator based on hard truncation. Specifically, given the observations on training losses Lt, we first exploit the K-nearest neighbor (KNN) algorithm (Liao & Vemuri, 2002) to remove some underlying outliers in Lt. The number of outliers is denoted by to(to < t), which can be adaptively determined as discussed in (Zhao et al., 2019). Note that we can also employ other algorithms, e.g., principal component analysis (Shyu et al., 2003) and the local outlier factor (Breunig et al., 2000), to identify underlying outliers in Lt. The main reason we employ KNN is because of its relatively low computation costs (Zhao et al., 2019).
The truncated loss observations on training losses are denoted by Lt−to . We then utilize Lt−to for the mean estimation. As the potential outliers are removed with high probability, the robustness of the estimation results will be enhanced. We denote such an estimated mean as µ̃h. We have
µ̃h = 1
t− to ∑ `i∈Lt−to `i. (4)
The corresponding estimator (4) is termed the hard estimator.
We derive concentration inequalities for the soft and hard estimators respectively. The search strategy for less selected examples and overall selection criterion are then provided. Note that we do not need to explicitly quantify the mean of training losses. We only need to sort the training examples based on the proposed selection criterion and then use the selected examples for robust training.
Theorem 1 Let Zn = {z1, · · · , zn} be an observation set with mean µz and variance σ2. By exploiting the non-decreasing influence function ψ(z) = log(1 + z + z2/2). For any > 0, we have∣∣∣∣∣ 1n n∑ i=1 ψ(zi)− µz ∣∣∣∣∣ ≤ σ2(n+ σ2 log( −1) n2 ) n− σ2 , (5) with probability at least 1− 2 .
Proof can be found in Appendix A.1.
Theorem 2 Let Zn = {z1, . . . , zn} be a (not necessarily time homogeneous) Markov chain with mean µz , taking values in a Polish state space Λ1 × . . .× Λn, and with a minimal mixing time τmin. The truncated set with hard truncation is denoted by Zno , with no < n. If |zi| is upper bounded by Z. For any 1 > 0 and 2 > 0, we have∣∣∣∣∣∣ 1n− no ∑ zi∈Zn\Zno −µz ∣∣∣∣∣∣ ≤ 1n− no ( 2Z √ 2τmin log 2 1 + 2Zno n √ 2τmin log 2n 2 ) , (6) with probability at least 1− 1 − 2.
Proof can be found in Appendix A.2. For our task, let the training loss be upper-bounded by L. The value of L can be determined easily by training networks on noisy datasets and observing the loss distribution (Arazo et al., 2019).
Conservative search and selection criteria. In this paper, we will use the concentration inequalities (5) and (6) to present conservative search and the overall sample selection criterion. Specifically, we exploit their lower bounds and consider the selected number of examples during training. The selection of the examples that are less selected is encouraged.
Denote the number of times one example was selected by nt(nt ≤ t). Let = 12t . For the circumstance with soft truncation, the selection criterion is
`?s = µ̃s − σ2(t+ σ 2 log(2t) t2 )
nt − σ2 . (7)
Let 1 = 2 = 12t , for the situation with hard truncation, by rewriting (6), the selection criterion is
`?h = µ̃h − 2 √ 2τminL(t+ √ 2to)
(t− to) √ t
√ log(4t)
nt . (8)
Note that we directly replace t with nt. If an example is rarely selected during training, nt will be far less than n, which causes the lower bounds to change drastically. Hence, we do not use the mean of all training losses, but use the mean of training losses in fixed-length time intervals. More details about this can be checked in Section 3.
For the selection criteria (7) and (8), we can see that they consist of two terms and have one term with a minus sign. The first term in Eq. (7) (or Eq. (8)) is to reduce the uncertainty of small-loss examples, where we use robust mean estimation on training losses. The second term, i.e., the statistical confidence bound, is to encourage the network to choose the less selected examples (with a small nt). The two terms are constraining and balanced with σ2 or τmin. To avoid introducing strong assumptions on the underlying distribution of losses (Chakrabarty & Samorodnitsky, 2012), we tune σ and τmin with a noisy validation set. For the mislabeled data, although the model has high uncertainties on them (i.e., a small nt) and tends to pick them, the overfitting to the mislabeled data is harmful. Also, the mislabeled data and clean data are rather hard to distinguish in some cases as discussed. Thus, we should search underlying clean data in a conservative way. In this paper, we initialize σ and τmin with small values. This way can reduce the adverse effects of mislabeled data and meanwhile select the clean examples with large losses, which helps generalize. More evaluations will be presented in Section 3.
Algorithm 1 CNLCU Algorithm. 1: Input θ1 and θ2, learning rate η, fixed τ , epoch Tk and Tmax, iteration tmax; for T = 1, 2, . . . , Tmax do
2: Shuffle training dataset S̃; for t = 1, . . . , tmax do
3: Fetch mini-batch S̄ from S̃; 4: Obtain S̄1 = arg minS′:|S′|≥R(T )|S̄| `?(θ1, S′); // calculated with Eq. (7) or Eq. (8) 5: Obtain S̄2 = arg minS′:|S′|≥R(T )|S̄| `?(θ2, S′); // calculated with Eq. (7) or Eq. (8) 6: Update θ1 = θ1 − η∇`(θ1, S̄2); 7: Update θ2 = θ2 − η∇`(θ2, S̄1);
end 8: Update R(T ) = 1−min { T Tk τ, τ } ;
end 9: Output θ1 and θ2. The overall procedure of the proposed method, which combats noisy labels by concerning uncertainty (CNLCU), is provided in Algorithm 1. CNLCU works in a mini-batch manner since all deep learning training methods are based on stochastic gradient descent. Following (Han et al., 2018), we exploit two networks with parameters θ1 and θ2 respectively to teach each other. Specifically, when a mini-batch S̄ is formed (Step 3), we let two networks select a small proportion of examples in this mini-batch with Eq. (7) or (8) (Step 4 and Step 5). The number of instances is controlled by the function R(T ), and two networks only select R(T ) percentage of examples out of the mini-batch. The value of R(T ) should be larger at the beginning of training, and be smaller when the number of epochs goes large, which can make better use of memorization effects of deep networks (Han et al., 2018) for sample selection. Then, the selected instances are fed into its peer network for parameter updates (Step 6 and Step 7).

heading: 3 EXPERIMENTS
text: In this section, we evaluate the robustness of our proposed method to noisy labels with comprehensive experiments on the synthetic balanced noisy datasets (Section 3.1), synthetic imbalanced noisy datasets (Section 3.2), and real-world noisy dataset (Section 3.3).

heading: 3.1 EXPERIMENTS ON SYNTHETIC BALANCED NOISY DATASETS
text: Datasets. We verify the effectiveness of our method on the manually corrupted version of the following datasets: MNIST (LeCun et al.), F-MNIST (Xiao et al., 2017), CIFAR-10 (Krizhevsky, 2009), and CIFAR-100 (Krizhevsky, 2009), because these datasets are popularly used for the evaluation of learning with noisy labels in the literature (Han et al., 2018; Yu et al., 2019; Wu et al., 2021; Lee et al., 2019). The four datasets are class-balanced. The important statistics of the used synthetic datasets are summarized in Appendix B.1.
Generating noisy labels. We consider broad types of label noise: (1). Symmetric noise (abbreviated as Sym.) (Wu et al., 2020; Ma et al., 2018). (2) Asymmetric noise (abbreviated as Asym.) (Ma et al., 2020; Xia et al., 2021; Wei et al., 2020). (3) Pairflip noise (abbreviated as Pair.) (Han et al., 2018; Yu et al., 2019; Zheng et al., 2020). (4). Tridiagonal noise (abbreviated as Trid.) (Zhang et al., 2021). (5). Instance noise (abbreviated as Ins.) (Cheng et al., 2020; Xia et al., 2020). The noise rate is set to 20% and 40% to ensure clean labels are diagonally dominant (Ma et al., 2020). More details about above noise are provided in Appendix B.1. We leave out 10% of noisy training examples as a validation set.
Baselines. We compare the proposed method (Algorithm 1) with following methods which focus on sample selection, and implement all methods with default parameters by PyTorch, and conduct all the experiments on NVIDIA Titan Xp GPUs. (1). S2E (Yao et al., 2020a), which properly controls the sample selection process so that deep networks can better benefit from the memorization effects. (2). MentorNet (Jiang et al., 2018), which learns a curriculum to filter out noisy data. We use self-paced MentorNet in this paper. (3). Co-teaching (Han et al., 2018), which trains two networks simultaneously and cross-updates parameters of peer networks. (4). SIGUA (Han et al., 2020), which exploits stochastic integrated gradient underweighted ascent to handle noisy labels. We use self-teaching SIGUA in this paper. (5). JoCor (Wei et al., 2020), which reduces the diversity of networks to improve robustness. To avoid too dense tables, we provide results of other sample selection methods and other types of baselines such as adding regularization. All results are presented in Appendix B.2. Here, we term our methods with soft truncation and hard truncation as CNLCU-S and CNLCU-H respectively.
Network structure and optimizer. For MNIST, F-MNIST, and CIFAR-10, we use a 9-layer CNN structure from (Han et al., 2018). Due to the limited space, the experimental details on CIFAR-100 are provided in Appendix B.3. All network structures we used here are standard test beds for weaklysupervised learning. For all experiments, the Adam optimizer (Kingma & Ba, 2014) (momentum=0.9) is used with an initial learning rate of 0.001, and the batch size is set to 128 and we run 200 epochs. We linearly decay learning rate to zero from 80 to 200 epochs as did in (Han et al., 2018). We take two networks with the same architecture but different initializations as two classifiers as did in (Han et al., 2018; Yu et al., 2019; Wei et al., 2020), since even with the same network and optimization method, different initializations can lead to different local optimal (Han et al., 2018). The details of network structures can be checked in Appendix C.
For the hyper-parameters σ2 and τmin, we determine them in the range {10−1, 10−2, 10−3, 10−4} with a noisy validation set. Note that the use of hyperparameters aims to reduce the dependency on strong assumptions and thus make our methods perform well in practice. We provide more details about this in Appendix D. Here, we assume the noise level τ is known and set R(T ) = 1−min{ TTk τ, τ} with Tk=10. If τ is not known in advanced, it can be inferred using validation sets (Liu & Tao, 2016; Yu et al., 2018). As for performance measurement, we use test accuracy, i.e., test accuracy = (# of correct prediction) / (# of testing). All experiments are repeated five times. We report the mean and standard deviation of experimental results.
Experimental results. The experimental results about test accuracy are provided in Tables 1, 2, and 3. Specifically, for MNIST, as can be seen, our proposed methods, i.e., CNLCU-S and CNLCU-H, produce the best results in the vast majority of cases. In some cases such as asymmetric noise, the baseline S2E outperforms ours, which benefits the accurate estimation for the number of selected
small-loss examples. For F-MNIST, the training data becomes complicated. S2E cannot achieve the accurate estimation in such situation and thus has no great performance like it got on MNIST. Our methods achieve varying degrees of lead over baselines. For CIFAR-10, our methods once again outperforms all the baseline methods. Although some baseline, e.g., Co-teaching, can work well in some cases, experimental results show that it cannot handle various noise types. In contrast, the proposed methods achieve superior robustness against broad noise types. The results mean that our methods can be better applied to actual scenarios, where the noise is diversiform. Ablation study. We first conduct the ablation study to analyze the sensitivity of the length of time intervals. In order to avoid too dense figures, we exploit MNIST and F-MNIST with the mentioned noise settings as representative examples. For CNLCU-S, the length of time intervals is chosen in the range from 3 to 8. For CNLCU-H, the length of time intervals is chosen in the range from 10 to 15. Note that the reason for their different lengths is that their different mechanisms. Specifically, CNLCU-S holistically changes the behavior of losses, but does not remove any loss from the loss set. We thus do not need too long length of time intervals. As a comparison, CNLCU-H needs to remove some outliers from the loss set as discussed. The length should be longer to guarantee the number of examples available for robust mean estimation. The experimental results are provided in Appendix B.4, which show the proposed CNLCU-S and CNLCU-H are robust to the choices of the length of time intervals. Such robustness to hyperparameters means our methods can be applied in practice and does not need too much effect to tune the hyperparameters.
Furthermore, since our methods concern uncertainty from two aspects, i.e., the uncertainty from both small-loss and large-loss examples, we conduct experiments to analyze each part of our methods. Also, as mentioned, we compare robust mean estimation with non-robust mean estimation when learning with noisy labels. More details are provided in Appendix B.4.

heading: 3.2 EXPERIMENTS ON SYNTHETIC IMBALANCED NOISY DATASETS
text: Experimental setup. We exploit MNIST and F-MNIST. For these two datasets, we reduce the number of training examples along with the labels from “0” to “4” to 1% of previous numbers. We term such synthetic imbalanced noisy datasets as IM-MNIST and IM-F-MNIST respectively. This setting aims to simulate the extremely imbalanced circumstance, which is common in practice. Moreover, we exploit asymmetric noise, since these types of noise can produce more imbalanced case (Patrini et al., 2017; Ma et al., 2020). Other settings such as the network structure and optimizer are the same as those in experiments on synthetic balanced noisy datasets.
As for performance measurements, we use test accuracy. In addition, we exploit the selected ratio of training examples with the imbalanced classes, i.e., selected ratio=(# of selected imbalanced labels / # of all selected labels). Intuitively, a higher selected ratio means the proposed method can make better use of training examples with the imbalanced classes, following better generalization (Kang et al., 2020).
Experimental results. The test accuracy achieved on IM-MNIST and IM-F-MNIST is presented in Figure 2. Recall the experimental results in Tables 1 and 2, we can see that the imbalanced issue is catastrophic to the sample selection approach when learning with noisy labels. For IM-MNIST, as can be seen, all the baselines have serious overfitting in the early stages of training. The curves of test accuracy drop dramatically. As a comparison, the proposed CNLCU-S and CNLCU-H can give a try to large-loss but less selected data which are possible to be clean but equipped with imbalanced labels. Therefore, our methods always outperform baselines clearly. In the case of Asym. 10%, our methods achieve nearly 30% lead over baselines. For IM-F-MNIST, we can also see that our methods perform well and always achieve about 5% lead over all the baselines. Note that due to the huge challenge of this task, some baseline, e.g., S2E, has a large error bar. In addition, the baseline SIGUA performs badly. It is because SIGUA exploits stochastic integrated gradient underweighted ascent on large-loss examples, which makes the examples with imbalanced classes more difficult to be selected than them in other sample selection methods. Due to the limited space, the selected ratio achieved on IM-MNIST and IM-F-MNIST is presented in Appendix B.5, which explain well why our methods perform better than multiple baselines.

heading: 3.3 EXPERIMENTS ON REAL-WORLD NOISY DATASETS
text: Experimental setup. To verify the efficacy of our methods in the real-world scenario, we conduct experiments on the noisy dataset Clothing1M (Xiao et al., 2015). Specifically, for experiments on Clothing1M, we use the 1M images with noisy labels for training and 10k clean data for test respectively. Note that we do not use the 50k clean training data in all the experiments. For preprocessing, we resize the image to 256×256, crop the middle 224×224 as input, and perform normalization. The experiments on Clothing1M are performed once due to the huge computational cost. We leave 10% noisy training data as a validation set for model selection. Note that we do not exploit the resampling trick during training (Li et al., 2020a). Here, Best denotes the test accuracy of the epoch where the validation accuracy was optimal. Last denotes test accuracy of the last epoch. For
10 12 14 16 18 20 22 24 Time Interval
48
49
50
51
52
Te st
A cc
ur ac
y
S2E MentorNet Co-teaching SIGUA JoCor CNLCU-S CNLCU-H
– Asym. 10% – – Asym. 20% – – Asym. 30% – – Asym. 40% –
– IM
-M N
IS T
–
0 50 100 150 200 Epoch
20
40
60
80
100
Te st
A cc
ur ac
y
0 50 100 150 200 Epoch
20
40
60
80
100
Te st
A cc
ur ac
y
0 50 100 150 200 Epoch
20
40
60
80
100
Te st
A cc
ur ac
y
0 50 100 150 200 Epoch
20
40
60
80
Te st
A cc
ur ac
y
– IM
-F -M
N IS
T –
0 50 100 150 200 Epoch
10
20
30
40
50
60
70
Te st
A cc
ur ac
y
0 50 100 150 200 Epoch
10
20
30
40
50
60
70
Te st
A cc
ur ac y 0 50 100 150 200
Epoch
10
20
30
40
50
60
Te st
A cc
ur ac
y
0 50 100 150 200 Epoch
10
20
30
40
50
60
Te st
A cc
ur ac
y
Combining with semi-supervised learning. For combating noisy labels in real-world noisy datasets, the stateof-the-art methods, e.g., DivideMix (Li et al., 2020a), always employ the semi-supervised learning technology. As our methods mainly focus on sample selection, to make the comparison fair, we combine our methods with
semi-supervised learning. The sample selection procedure in DivideMix is replaced by our methods. Other settings are kept the same. Following prior works (Ma et al., 2020), the experiments are conducted on three real-world noisy datasets, i.e., Food-101 (Bossard et al., 2014), WebVision (Mini) (Li et al., 2017), and Clothing1M (Xiao et al., 2015). The results are provided in Table 5. As can be seen, the proposed methods are superior and can be used to improve the cutting edge performance.

heading: 4 CONCLUSION
text: In this paper, we focus on promoting the prior sample selection in learning with noisy labels, which starts from concerning the uncertainty of losses during training. We robustly use the training losses at different iterations to reduce the uncertainty of small-loss examples, and adopt confidence interval estimation to reduce the uncertainty of large-loss examples. Experiments are conducted on benchmark datasets, demonstrating the effectiveness of our method. We believe that this paper opens up new possibilities in the topics of using sample selection to handle noisy labels, especially in improving the robustness of models on imbalanced noisy datasets.

heading: 5 ETHICS STATEMENT
text: This paper doesn’t raise any ethics concerns. This study doesn’t involve any human subjects, practices to data set releases, potentially harmful insights, methodologies and applications, potential conflicts of interest and sponsorship, discrimination/bias/fairness concerns, privacy and security issues, legal compliance, and research integrity issues.

heading: ACKNOWLEDGMENT
text: XBX is supported by Australian Research Council Projects DE-190101473. TLL is partially supported by Australian Research Council Projects DE-190101473, IC-190100031, and DP-220102121. BH was supported by the RGC Early Career Scheme No. 22200720 and NSFC Young Scientists Fund No. 62006202. MMG is supported by Australian Research Council Projects DE-210101624. JY is sponsored by CAAI-Huawei MindSpore Open Fund (CAAIXSJLJJ-2021-016B). GN and MS are supported by JST AIP Acceleration Research Grant Number JPMJCR20U3, Japan. MS is also supported by the Institute for AI and Beyond, UTokyo.

heading: A PROOF OF THEORETICAL RESULTS
text: A.1 PROOF OF THEOREM 1 For the circumstance with soft truncation, µ̃z = 1n ∑n i=1 ψ(zi). As suggested in (Catoni, 2012), we can exploit µ̃−z and µ̃ + z such that µ̃−z ≤ µ̃z ≤ µ̃+z , (9) to derive a bound for µ̃z . For some positive real parameter α, we define
r(µ̃z) = n∑ i=1 ψ [α(zi − µ̃z)] = 0. (10)
Let us introduce the quantity
r(θ) = 1
αn n∑ i=1 ψ [α(zi − θ)] . (11)
With the exponential moment inequality (Giné et al., 2000) and the Cr inequality (Mohri et al., 2018), we have
exp{αnr(θ)} ≤ { 1 + α(µz − θ) + α2[σ2 + (µz − θ)2] }n
≤ exp{nα(µz − θ) + nα2[σ2 + (µz − θ)2]}. (12)
In the same way,
exp{−αnr(θ)} ≤ exp{−nα(µz − θ) + nα2[σ2 + (µz − θ)2]}. (13)
If we define for any µs ∈ R the bounds
B−(θ) = µz − θ − α[σ2 + (µz − θ)2]− log( −1)
αn (14)
and
B+(θ) = µz − θ + α[σ2 + (µz − θ)2] + log( −1)
αn . (15)
From (Chen et al., 2020) (Lemma 2.2), we obtain that
P (r(θ) > B−(θ)) ≥ 1− and P (r(θ) < B+(θ)) ≥ 1− . (16)
Let µ̃−z be the largest solution of the quadratic equation B−(θ) and µ̃ + z be the smallest solution of the quadratic equation B+(θ). Also, to guarantee the solution of the quadratic equation, we assume
4α2σ2 + 4 log( −1)
n ≤ 1. (17)
From (Chen et al., 2020) (Theorem 2.6), we then have
µ̃−z ≥ µz − ασ2 + log( −1) αn
α− 1 , (18)
and
µ̃+z ≤ µz + ασ2 + log( −1) αn
α− 1 . (19)
With probability at least 1-2 , we have µ̃−z ≤ µ̃z ≤ µ̃+z . We can choose α = nσ2 . Then we have
|µ̃z − µz| ≤ σ2(n+ σ 2 log( −1) n2 )
n− σ2 , (20)
which holds with probability at least 1-2 .
We exploit the lower bound and let = 12t . Then we have
`?s = µ̃s − σ2(t+ σ 2 log(2t) t2 )
nt − σ2 , (21)
where nt denotes the number of times that the example was selected in the time intervals.
Here, we provide the graph of the used influence function for the soft estimator, which explains the mechanism of the function y = log(1 + x + x2/2) more clearly. The illustration is presented in Figure 3. As can be seen, when x is large and may be an outlier, the influence function can reduce its negative impact for mean estimation. Therefore, we exploit such an influence function for robust mean estimation, which brings better classification performance.
A.2 PROOF OF THEOREM 2
Lemma 1 ((Paulin et al., 2015)) Let Zn = {z1, . . . , zn} be a (not necessarily time homogeneous) Markov chain with mean µz , taking values in a Polish state space Λ1 × . . .× Λn, with a mixing time τ(υ) (for 0 ≤ υ ≤ 1). Let
τmin = inf 0≤υ<1
τ(υ) · (
2− υ 1− υ
)2 . (22)
For some η ∈ R+, suppose that f : Λ→ R satisfies the following inequality: f(a)− f(b) ≤ n∑ i=1 η1[ai 6= bi], (23) for every a, b ∈ Λ. Then for any ≥ 0, we have
P (|f(Zn)−Ef(Zn)| ≥ ) ≤ 2 exp ( −2 2
η2τmin
) . (24)
The detailed definition of the mixing time for the Markov chain can be found in (Paulin et al., 2015; Roberts et al., 2004). Let f be the mean function. Following the prior work on mean estimation (Liu et al., 2019; Diakonikolas et al., 2020; Diakonikolas & Kane, 2019; Niss & Tewari, 2020), without loss of generality, we assume µz = 0 for the underlying true distribution, and |zi| is upper bounded by Z. Then we can set η to 4Z/n for Eq. (23). Combining the above analyses, we can revise Eq. (24) as follows:
P (∣∣∣∣∣ 1n n∑ i=1 zi ∣∣∣∣∣ ≥ 2Zn √ 2τmin log 2 1 ) ≤ 1, (25)
and
P ( max i∈[n] |zi| ≥ 2Z n √ 2τmin log 2n
2
) ≤ 2, (26)
for 1 > 0 and 2 > 0. If we remove the potential outliers Zno from Zn. Therefore, we have∣∣∣∣∣∣ 1n− no ∑
zi∈Zn\Zno
−µz ∣∣∣∣∣∣ = 1n− no ∣∣∣∣∣∣ ∑ zi∈Zn − ∑ zi∈Zno ∣∣∣∣∣∣ ≤ 1 n− no ∣∣∣∣∣ ∑ zi∈Zn ∣∣∣∣∣+ ∣∣∣∣∣∣ ∑ zi∈Zno ∣∣∣∣∣∣ 
≤ 1 n− no (∣∣∣∣∣ ∑ zi∈Zn ∣∣∣∣∣+ no maxi∈[n] |zi| )
≤ 1 n− no
( 2Z √ 2τmin log 2
1 + 2Zno n
√ 2τmin log 2n
2
) ,
(27)
which holds with probability at least 1− 1 − 2. For our task, we exploit the concentration inequality. Let 1 = 2 = 12t , and the losses be bounded by L. Next we can obtain
|µ̃h − µ| ≤ 2L
t− to
(√ 2τmin log(4t) +
to t
√ 4τmin log(4t) ) = 2 √ 2τminL(t+ √ 2to)
(t− to)t √ log(4t)
(28)
with the probability at least 1− 1t . In practice, it is easy to identify the value of L. For example, we can training deep networks on noisy datasets to observe the loss distributions. Then, we exploit the lower bound such that
`?h = µ̃h − 2 √ 2τminL(t+ √ 2to)
(t− to) √ t
√ log(4t)
nt (29)
for sample selection.

heading: B COMPLEMENTARY EXPERIMENTAL ANALYSES
text: B.1 THE DETAILS OF DATASETS AND GENERATING NOISY LABELS
For the details of datasets, the important statistics of the used datasets are summarized in Table 6.
For the details of generating noisy labels, we exploit both class-dependent and instance-dependent label noise which include five types of synthetic label noise to verify the effectiveness of the proposed method. Here, we describe the details of the noise setting as follows:
(1). Class-dependent label noise:
• Symmetric noise: this kind of label noise is generated by flipping labels in each class uniformly to incorrect labels of other classes.
• Asymmetic noise : this kind of label noise is generated by flipping labels within a set of similar classes. In this paper, for MNIST, flipping 2→7, 3→8, 5↔6. For F-MNIST, flipping TSHIRT→SHIRT, PULLOVER→COAT, SANDALS→SNEAKER. For CIFAR-10, flipping TRUCK→AUTOMOBILE, BIRD→AIRPLANE, DEER→HORSE, CAT↔DOG. For CIFAR-100, the 100 classes are grouped into 20 super-classes, and each has 5 sub-classes. Each class is then flipped into the next within the same super-class.
• Pairflip noise: the noise flips each class to its adjacent class. • Tridiagonal noise: the noise corresponds to a spectral of classes where adjacent classes are easier to be mutually mislabeled, unlike the unidirectional pair flipping. It can be implemented by two consecutive pair flipping transformations in the opposite direction.
(2). Instance-dependent label noise:
• Instance noise: the noise is quite realistic, where the probability that an instance is mislabeled depends on its features. We generate this type of label noise to validate the effectiveness of the proposed method as did in (Xia et al., 2020; Yao et al., 2021).
We use synthetic noisy MNIST as an example and plot the noise transition matrices in Figure 4. The noise rate is set to 20%.
B.2 COMPARISON WITH OTHER BASELINES
We focus on the sample selection approach in learning with noisy labels. In the main paper (Section 3.1), we fairly compare our methods with the baselines which also focus on sample selection. We add two other sample-selection baselines here. As suggested by the related survey (Song et al., 2020), the sample selection methods can be divided into three categories: (a) “Multi-network Learning”, (b) “Multi-round Learning”, and (c) “Hybrid Approach”. As our method belongs to (a), we exploit INCV (Chen et al., 2019) which belongs to (b), and NPCL (Lyu & Tsang, 2020) which belongs to (c), to make the comparison more comprehensive.
Here, we also evaluate other types of baselines. We exploit APL (Ma et al., 2020) and CDR (Xia et al., 2021), which add implicit regularization from different perspectives. The experiments are conducted on MNIST and F-MNIST. Other experimental settings are the same as those in the main paper. The experimental results are provided in Tables 7 and 8, which show that the proposed methods are superior to these baselines with respect to classification performance.
B.3 EXPERIMENTS ON SYNTHETIC CIFAR-100
For CIFAR-100, we use a 7-layer CNN structure from (Yu et al., 2019; Yao et al., 2020a). Other experimental settings are the same as those in the experiments on MNIST, F-MNIST, and CIFAR-10. The results are provided in Table 9. We can see the proposed method outperforms all the baselines.
B.4 EXPERIMENTS FOR ABLATION STUDY
We conduct the ablation study to analyze the sensitivity of the length of time intervals. The results are shown in Figure 5 and 6. As we can seen, the proposed method, i.e., CNLCU-S and CNLCU-H are robust to the choices of hyperparameters.
Note that in this paper, we concern uncertainty from two aspects, i.e., the uncertainty about small-loss examples and the uncertainty about large-loss examples. Here, we conduct ablation study to show the
effect of removing different components to provide insights into what makes the proposed methods successful. The experiments are conducted on MNIST and F-MNIST. Other experimental settings are the same as those in the main paper (Section 3.1). Note that we employ two networks to teach each other following (Han et al., 2018). Therefore, when we do not consider uncertainty in sample selection, the proposed methods will reduce to the baseline Co-teaching (Han et al., 2018).
To study the effect of concerning uncertainty about small-loss examples, we remove the concerns about large-loss examples, i.e., the network is not encouraged to choose the less selected examples for updates. We express such a setting as “without concerning about large-loss examples” (abbreviated as w/o cl). To study the effect of concerning uncertainty about large-loss examples, we remove the concerns about small-loss examples, i.e., we only exploit the predictions of the current network. We express such a setting as “without concerning about small-loss examples” (abbreviated as w/o cs). Besides, we express the setting which directly uses non-robust mean as Co-teaching-M.
The experimental results of ablation study are provided in Tables 10 and 11. As can be seen, both aspects of uncertainty concerns can improve the robustness of models. Therefore, combining two uncertainty concerns, we can better combat noisy labels. In addition, robust mean estimation is superior to the non-robust mean in learning with noisy labels.
B.5 RESULTS ON SYNTHETIC IMBALANCED NOISY DATASETS
In the main paper, we have provided the test accuracy on synthetic imbalanced noisy datasets in Figure 2. Due to the limited space, we provide the selected ratio achieved on IM-MNIST and IM-FMNIST in Table 12. The results explain well why our methods perform better on synthetic imbalanced noisy datasets, i.e., our methods can make better use of training examples with the imbalanced classes. Note that since we give a try to large-loss but less selected data in a conservative way, the selected
ratio is still far away from the class prior probability on the test set, i.e., 10%. However, a little improvement of the selection ratio can bring a considerable improvement of test accuracy. These results tell us that, in the sample selection approach when learning with noisy labels, improving the selected ratio of training examples with the imbalanced classes is challenging but promising for generalization. This practical problem deserves to be studied in depth.
B.6 EXPERIMENTS WITH HIGH NOISE LEVELS
In the main paper, we set the noise rates to be smaller than 50%, which ensures that clean labels in noisy classes are diagonally dominant in all label noise settings. To demonstrate the effectiveness of our method with high noise levels, we conduct experiments on MNIST and F-MNIST with 50%, 60%, and 70% symmetric noise. The experimental results are presented in Table 13. As can be seen, the proposed methods can achieve the best performance in almost all cases.

heading: C COMPLEMENTARY EXPLANATION FOR NETWORK STRUCTURES
text: Table 14 describes the 9-layer CNN (Han et al., 2018) used on MNIST, F-MNIST, and CIFAR-10. Table 15 describes the 7-layer CNN (Yu et al., 2019) used on CIFAR-100. Here, LReLU stands for Leaky ReLU (Xu et al., 2015). The slopes of all LReLU functions in the networks are set to 0.01. Note that that the 7/9-layer CNN is a standard and common practice in weakly supervised learning. We decided to use these CNNs, since then the experimental results are directly comparable with previous approaches in the same area, i.e., learning with noisy labels.
CNN on MNIST CNN on F-MNIST CNN on CIFAR-10 28×28 Gray Image 28×28 Gray Image 32×32 RGB Image
3×3 conv, 128 LReLU 3×3 conv, 128 LReLU 3×3 conv, 128 LReLU
2×2 max-pool dropout, p = 0.25
3×3 conv, 256 LReLU 3×3 conv, 256 LReLU 3×3 conv, 256 LReLU
2×2 max-pool dropout, p = 0.25
3×3 conv, 512 LReLU 3×3 conv, 256 LReLU 3×3 conv, 128 LReLU
avg-pool dense 128→10 dense 128→10 dense 128→10
Table 14: The CNN on MNIST, F-MNIST, and CIFAR10.
CNN on CIFAR-100 32×32 RGB Image 3×3 conv, 64 ReLU 3×3 conv, 64 ReLU
2×2 max-pool 3×3 conv, 128 ReLU 3×3 conv, 128 ReLU
2×2 max-pool 3×3 conv, 196 ReLU 3×3 conv, 196 ReLU
2×2 max-pool dense 256→100
Table 15: The CNN on CIFAR-100.

heading: D NEEDED ASSUMPTIONS WITHOUT NOISY VALIDATION SETS
text: In the main paper, a noisy validation set is exploited to determine σ2 and τmin. We discuss, if we do not use the noisy validation set, what assumptions we will need.
• In statistical learning, it is an important problem for estimating the variance of a data distribution. However, it is hard to obtain an accurate estimation from a finite sample. To reduce the estimation errors, some kinds of assumptions are often needed, e.g., random sampling assumptions, replacement assumptions, and strict distribution assumptions. We suggest the readers to refer (Wolter, 2007) for more details.
• For the accurate estimation of τmin, we have to assume that the Markov chain can exhibit a cutoff, which means that the total variation distance decreases very rapidly in a small interval (Paulin et al., 2015). Readers can check the Figure 1 of (Lubetzky & Sly, 2013) for better understanding.

heading: E FURTHER DISCUSSION ON LEARNING BY UNCERTAINTY
text: We discuss a related work named ActiveBias (Chang et al., 2017) on learning with uncertainty, although it studies the predicted probability, rather than the loss. In general, the differences between our work and ActiveBias lie in the different problems, different focuses, and different technical implementation. In more detail, we summarize the main differences between the two works in the following:
• ActiveBias mainly focuses on mining hard examples to help generalization. Although it mentions the label-noise problem, it does not consider comprehensive noise settings. Also,
the baselines are SGD, ADAM, and other optimization methods, but not the methods are specially designed for learning with noisy labels. In contrast, our work mainly focuses on learning with noisy labels and has more comprehensive experiments, which explore the performance of different label-noise methods under noisy supervision.
• ActiveBias focuses on using the hard examples, but not too difficult examples, which is stated in the original paper. In the imbalanced setting of this paper, clean imbalanced data are too difficult to distinguish with the predictions of models (Figure 1, right) and therefore are too difficult examples. Our methods aim to make use of such examples. Experiments show that such examples are of great importance for generalization.
• The introduction of uncertainty in ActiveBias relies on the estimation of the prediction variance but does not consider the bad influence of mislabeled data/outliers on this estimation. Our methods use the loss distribution and the side effect of mislabeled data is considered by robust mean estimators.

heading: F RELATED WORK ON SAMPLE SELECTION
text: In this paper, we focus on the procedure of using the small-loss criterion for sample selection, which is very commonly used in learning with noisy labels and shared by the state-of-the-art methods. We review prior effects in this line. Existing methods (Jiang et al., 2018; Han et al., 2018; Yu et al., 2019; Wei et al., 2020; Lyu & Tsang, 2020) focus on the class-balanced problem. Based on the memorization effect of deep networks, they select examples with small losses for network updates and drop examples with large losses. The main reason is that clean examples are more likely to have small losses, but mislabeled examples are more likely to have large losses in class-balanced cases. Distinctly, these methods ignore the clean examples with large losses, following suboptimal generalization. When the training dataset is noisy and extremely imbalanced, prior methods are weak. It is because since they cannot select clean hard examples within non-dominant classes effectively based on losses, which is shown in the main paper. Unfortunately, such examples are critical for generalization. We are the first one to focus on this important problem and tackle it by considering the uncertainty of losses.

Review summaries:
This paper discusses the potential weaknesses in previous sample selection criteria in learning with noisy labels. And then propose a new selection criterion by incorporating the uncertainty of losses, together with theoretical justification. Experiments on both synthetic noisy balanced/imbalanced datasets and real-world noisy datasets validate the effectiveness of the proposed approach.

This paper proposes a novel algorithm to improve the sample selection in the case of noisy labels training by incorporating the uncertainty of losses. To select samples, the authors propose to use the lower bounds of the confidence intervals derived from concentration inequalities instead of using point estimation of losses. The authors introduce the Soft truncation estimator and the Hard truncation estimator and propose lower bounds for both estimators. The authors introduce an algorithm, the CNLCU Algorithm based on using either the lower bounds calculated for the Soft truncation estimator or the Hard truncation estimator.   The authors validate empirically their results on four benchmark datasets (MNIST, F-MNIST, CIFAR-10, CIFAR-100) and use a diverse set of possible noise functions. The method proposed almost always outperforms all other comparable approaches. 

The paper proposes a novel sample selection method for learning with noisy labels (LNL). Based on the typical "small-loss" assumption, the motivation is to consider uncertainty about large-loss samples in order to distinguish the two confounding cases: truly mislabeled samples, or clean yet underrepresented samples that are less frequently selected or learned by the model so far. The proposed method explores robust mean estimation to summarize the per-sample loss trajectory, through soft truncation and hard truncation. Concentration inequalities are used to obtain the final selection criteria to perform conservative search. Results are overall promising, in particular showing very good results dealing with label noise + extreme class imbalance (Figure 2).

This paper introduces the uncertainty of losses into the sample selection approach for learning with noisy labels. The authors discuss how to effectively exploit underlying clean examples that are less selected during training. Experimental results verify the effectiveness of the proposed method. 

The authors discuss potential weakness of previous sample selection criteria and propose new selection criteria based on the uncertainty of losses (not losses themselves).  Some theoretical analysis on the criteria is provided.  Then, they experimentally validate the proposed algorithms (CNLCU-S and CNLCU-H), showing that the proposed algorithms outperform some baselines in learning with noisy labels.

This paper proposes a CNLCU strategy that incorporates the uncertainty of losses by adopting interval estimation.  In learning with noisy labels, the sample selection approach regards small-loss data as correctly labeled during training.  This paper gives large-loss data a try to explore underrepresented data that are correctly labeled but seem to be mislabeled at first glance. Experiments demonstrate that the proposed method is superior to baselines and robust to a broad range of label noise types. This paper opens up new possibilities in the topics of using sample selection to handle noisy labels.