ERALIZATION AGAINST LABEL CORRUPTION
Year: 2020

Abstract:
Deep neural networks (DNNs) have great expressive power, which can even memorize samples with wrong labels. It is vitally important to reiterate robustness and generalization in DNNs against label corruption. To this end, this paper studies the 0-1 loss, which has a monotonic relationship with empirical adversary (reweighted) risk (Hu et al., 2018). Although the 0-1 loss has some robust properties, it is difficult to optimize. To efficiently optimize the 0-1 loss while keeping its robust properties, we propose a very simple and efficient loss, i.e. curriculum loss (CL). Our CL is a tighter upper bound of the 0-1 loss compared with conventional summation based surrogate losses. Moreover, CL can adaptively select samples for model training. As a result, our loss can be deemed as a novel perspective of curriculum sample selection strategy, which bridges a connection between curriculum learning and robust learning. Experimental results on benchmark datasets validate the robustness of the proposed loss.

text: Deep neural networks (DNNs) have great expressive power, which can even memorize samples with wrong labels. It is vitally important to reiterate robustness and generalization in DNNs against label corruption. To this end, this paper studies the 0-1 loss, which has a monotonic relationship with empirical adversary (reweighted) risk (Hu et al., 2018). Although the 0-1 loss has some robust properties, it is difficult to optimize. To efficiently optimize the 0-1 loss while keeping its robust properties, we propose a very simple and efficient loss, i.e. curriculum loss (CL). Our CL is a tighter upper bound of the 0-1 loss compared with conventional summation based surrogate losses. Moreover, CL can adaptively select samples for model training. As a result, our loss can be deemed as a novel perspective of curriculum sample selection strategy, which bridges a connection between curriculum learning and robust learning. Experimental results on benchmark datasets validate the robustness of the proposed loss.

heading: 1 INTRODUCTION
text: Noise corruption is a common phenomenon in our daily life. For instance, noisy corrupted (wrong) labels may be resulted from annotating for similar objects (Su et al., 2012; Yuan et al., 2019), crawling images and labels from websites (Hu et al., 2017; Tanaka et al., 2018) and creating training sets by program (Ratner et al., 2016; Khetan et al., 2018). Learning with noisy labels is thus an promising area.
Deep neural networks (DNNs) have great expressive power (model complexity) to learn challenging tasks. However, DNNs also undertake a higher risk of overfitting to the data. Although many regularization techniques, such as adding regularization terms, data augmentation, weight decay, dropout and batch normalization, have been proposed, generalization is still vitally important for deep learning to fully exploit the super-expressive power. Zhang et al. (2017) show that DNNs can even fully memorize samples with incorrectly corrupted labels. Such label corruption significantly degenerates the generalization performance of deep models. This calls a lot of attention on robustness in deep learning with noisy labels.
Robustness of 0-1 loss: The problem resulted from data corruption or label corruption is that test distribution is different from training distribution. Hu et al. (2018) analyzed the adversarial risk that the test distribution density is adversarially changed within a limited f -divergence (e.g. KLdivergence) from the training distribution density. They show that there is a monotonic relationship between the (empirical) risk and the (empirical) adversarial risk when the 0-1 loss function is used. This suggests that minimizing the empirical risk with the 0-1 loss function is equivalent to minimize the empirical adversarial risk (worst-case risk). When we train a model based on the corrupted training distribution, we want our model to perform well on the clean distribution. Since we do not know the clean distribution, we want our model to perform well for the worst case estimate of the clean distribution in some constrained set. It is thus natural to employ the worst-case classification risk of the estimated clean distribution as the objective. Note that the worst-case classification risk is an upper bound of the classification risk of the true clean distribution, minimizing the worst-case risk can usually decrease the true risk. When we employ the 0-1 loss, because of the equivalence between the classification risk and the worst-case classification risk, we can directly minimize the
classification risk under the corrupted training distribution instead of minimizing the worst-case classification risk.
From the learning perspective, the 0-1 loss is more robust to outliers compared with an unbounded (convex) loss (e.g. hinge loss) (Masnadi-Shirazi & Vasconcelos, 2009). This is due to unbounded convex losses putting much weight on the outliers (with a large loss value) when minimizing the losses (Masnadi-Shirazi & Vasconcelos, 2009). If the unbounded (convex) loss is employed in deep network models, this becomes more prominent. Since training loss of deep networks can often be minimized to zero, outlier with a large loss has a large impact on the model. On the other hand, the 0-1 loss treats each training sample equally. Thus, each sample does not have too much influence on the model. Therefore, the model is tolerant of a small number of outliers.
Although the 0-1 loss has many robust properties, its non-differentiability and zero gradients make it difficult to optimize. One possible way to alleviate this problem is to seek an upper bound of the 0-1 loss that is still efficient to optimize but tighter than conventional (convex) losses. Such a tighter upper bound of the 0-1 loss can reduce the influence of the noisy outliers compared with conventional (convex) losses. At the same time, it is easier to optimize compared with the 0-1 loss. When minimizing the upper bound surrogate, we expect that the 0-1 loss objective is also minimized.
Learnability under large noise rate: The 0-1 loss cannot deal with large noise rate. When the noise rate becomes large, the systematic error (due to label corruption) grows up and becomes not negligible. As a result, the model’s generalization performance will degenerate due to this systematic error. To reduce the systematic error produced by training with noisy labels, several methods have been proposed. They can be categorized into three kinds: transition matrix based method (Sukhbaatar et al., 2014; Patrini et al., 2017; Goldberger & Ben-Reuven, 2017), regularization based method (Miyato et al., 2016) and sample selection based method (Jiang et al., 2018; Han et al., 2018b). Among them, sample selection based method is one promising direction that selects samples to reduce noisy ratio for training. These methods are based on the idea of curriculum learning (Bengio et al., 2009) which is one successful method that trains the model gradually with samples ordered in a meaningful sequence. Although they achieve success to some extents, most of these methods are heuristic based.
To efficiently minimize the 0-1 loss while keeping the robust properties, we propose a novel loss that is a tighter upper bound of the 0-1 loss compared with conventional surrogate losses. Specifically, giving any base loss function l(u) ≥ 1 ( u < 0 ) , u ∈ R, our loss Q(u) satisfies∑n
i=1 1 ( ui < 0 ) ≤ Q(u) ≤ ∑n i=1 l(ui), where u = [u1, · · · , un] with ui being the classification margin of ith sample, and 1(·) is an indicator function. We name it as Curriculum Loss (CL) because our loss automatically and adaptively selects samples for training, which can be deemed as a curriculum learning paradigm.
Our contributions are listed as follows:
• We propose a novel loss (i.e. curriculum loss) for robust learning against label corruption. We prove that our CL is a tighter upper bound of 0-1 loss compared with conventional summation based surrogate loss. Moreover, CL can adaptively select samples for stagewise training, which bridges a connection between curriculum learning and robust learning.
• We prove that CL can be performed by a simple and fast selection algorithm with O(n log n) time complexity. Moreover, our CL supports mini-batch update, which is convenient to be used as a plug-in in many deep models.
• We further propose a Noise Pruned Curriculum Loss (NPCL) to address label corruption problem by extending CL to a more general form. Our NPCL automatically prune the estimated noisy samples during training. Moreover, NPCL is also very simple and efficient, which can be used as a plug-in in deep models as well.

heading: 2 CURRICULUM LOSS
text: In this section, we present the framework of our proposed Curriculum Loss (CL). We begin with discussion about robustness of the 0-1 loss in Section 2.1. We then show that our CL is a tighter upper bound of the 0-1 loss compared with conventional summation based surrogate losses in Section 2.2. A tighter bound of the 0-1 loss means that it is less sensitive to the noisy outliers, and it
better preserves the robustness of the 0-1 loss with a small rate of label corruption. For a large rate of label corruption, we extend our CL to a Noise Pruned Curriculum Loss (NPCL) to address this issue in Section 2.3. A simple multi-class extension and a novel soft multi-hinge loss are included in the Appendix. All the detailed proofs can be found in the Appendix as well.

heading: 2.1 ROBUSTNESS OF 0-1 LOSS AGAINST LABEL CORRUPTION
text: We rephrase Theorem 1 in (Hu et al., 2018) from a different perspective, which motivates us to employ the 0-1 loss for training against label corruption. Theorem 1. (Monotonic Relationship) (Hu et al. (Hu et al., 2018)) Let p(x, y) and q(x, y) be the training and test density,respectively. Define r(x, y) = q(x, y)/p(x, y) and ri = r(xi, yi). Let l(ŷ, y) = 1 ( sign(ŷ) 6= y ) and l(ŷ, y) = 1 ( argmaxk(ŷk) 6= y ) be 0-1 loss for binary classification and multi-class classification, respectively. Let f(·) be convex with f(1) = 0. Define risk R(θ), empirical risk R̂(θ), adversarial riskRadv(θ) and empirical adversarial risk R̂adv(θ) as
R(θ) = Ep(x,y) [l(gθ(x), y)] (1)
R̂(θ) = 1 n ∑n i=1 l(gθ(xi), yi) (2) Radv(θ) = sup r∈Uf Ep(x,y) [r(x, y)l(gθ(x), y)] (3)
R̂adv(θ) = sup r∈Ûf
1
n ∑n i=1 ril(gθ(xi), yi), (4)
where Uf = { r(x, y) ∣∣Ep(x,y) [f (r(x, y))] ≤ δ,Ep(x,y) [r(x, y)] = 1, r(x, y) ≥ 0,∀(x, y) ∈ X × Y } and Ûf = { r ∣∣ 1 n ∑n i=1 f(ri) ≤ δ, 1 n ∑n i=1 ri = 1, r ≥ 0 } . Then we have that
If Radv(θ1) < 1, then R(θ1) < R(θ2) ⇐⇒ Radv(θ1) < Radv(θ2). (5) If Radv(θ1) = 1, then R(θ1) ≤ R(θ2) ⇐⇒ Radv(θ2) = 1. (6)
The same monotonic relationship holds between their empirical approximation: R̂(θ) and R̂adv .
Theorem 1 (Hu et al., 2018) shows that the monotonic relationship between the (empirical) risk and the (empirical) adversarial risk (worst-case risk) when 0-1 loss function is used. It means that minimizing (empirical) risk is equivalent to minimize the (empirical) adversarial risk (worst-case risk) for 0-1 loss. When we train a model based on the corrupted training distribution p(x, y), we want our model to perform well on the clean distribution q(x, y). Since we do not know the clean distribution q, we want our model to perform well for the worst-case estimate of the clean distribution, with the assumption that the f -divergence between the corrupted distribution p and the clean distribution q is bounded by δ. Note that the underlying clean distribution is fixed but unknown, given the corrupted training distribution, the smallest δ that bounds the divergence between the corrupted distribution and clean distribution measures the intrinsic difficulty of the corruption, and it is also fixed and unknown. The corresponding worst-case distribution w.r.t the smallest δ is an estimate of the true clean distribution, and this worst-case risk upper bounds the risk of the true clean distribution. In addition, this bound is tighter than the other worst-case risks w.r.t larger δ. It is natural to use this upper bound as the objective for robust learning. When we use 0-1 loss (that is commonly employed for evaluation), because of the equivalence of the risk and the worst-case risk, we can directly minimize risk under training distribution p instead of directly minimizing the worst-case risk (i.e., the upper bound). Moreover, this enables us to minimize the upper bound without knowing the true δ beforehand. When the true δ is small, i.e., the corruption of the training data is not heavy, the upper bound is not too pessimistic. Usually, minimizing the upper bound can decrease the true risk under clean distribution. Particularly, when the clean distribution coincides with the worst-case estimate w.r.t the smallest δ, minimizing the risk under the corrupted training distribution leads to the same minimizer as minimizing the risk under the clean distribution.

heading: 2.2 TIGHTER UPPER BOUNDS OF THE 0-1 LOSS
text: Unlike commonly used loss functions in machine learning, the non-differentiability and zero gradients of the 0-1 loss make it difficult to optimize. We thus propose a tighter upper bound surrogate
loss. We use the classification margin to define the 0-1 loss. For binary classification, classification margin is u = ŷy, where ŷ and y ∈ {+1,−1} denotes the prediction and ground truth, respectively. (A simple multi-class extension is discussed in the Appendix.) Let ui ∈ R be the classification margin of the ith sample for i ∈ {1, ..., n}. Denote u = [u1, ..., un]. The 0-1 loss objective can be defined as follows:
J(u) = ∑n i=1 1 ( ui < 0 ) . (7)
Given a base upper bound function l(u) ≥ 1 ( u < 0 ) , u ∈ R, the conventional surrogate of the 0-1 loss can be defined as Ĵ(u) = ∑n i=1 l(ui). (8)
Our curriculum loss Q(u) can be defined as Eq.(9). Q(u) is a tighter upper bound of 0-1 loss J(u) compared with the conventional surrogate loss Ĵ(u), which is summarized in Theorem 2: Theorem 2. (Tighter Bound) Suppose that base loss function l(u) ≥ 1 ( u < 0 ) , u ∈ R is an
upper bound of the 0-1 loss function. Let ui ∈ R be the classification margin of the ith sample for i ∈ {1, ..., n}. Denote max(·, ·) as the maximum between two inputs. Let u = [u1, ..., un]. Define Q (u) as follows:
Q (u)= min v∈{0,1}n
max (∑n
i=1 vil(ui), n− ∑n i=1 vi + ∑n i=1 1 ( ui < 0 )) . (9)
Then J(u) ≤ Q (u) ≤ Ĵ (u) holds true.
Remark: For any fixed u, we can obtain an optimum solution v∗ of the partial optimization. The index indicator v∗ can naturally select samples as a curriculum paradigm for training models. The partial optimization w.r.t index indicator v can be solved by a very simple and efficient algorithm (Algorithm 1) in O(n log n). Thus, the loss is very efficient to compute. Moreover, since Q (u) is tighter than conventional surrogate loss Ĵ(u), it is less sensitive to outliers compared with Ĵ(u). Furthermore, it better preserves the robust property of the 0-1 loss against label corruption.
The difficulty of optimizing the 0-1 loss is that the 0-1 loss has zero gradients in almost everywhere (except at the breaking point). This issue prevents us from using first-order methods to optimize the 0-1 loss. Eq.(9) provides a surrogate of the 0-1 loss with non-zero subgradient for optimization, while preserving robust properties of the 0-1 loss. Note that our goal is to construct a tight upper bound of the 0-1 loss while maintaining informative (sub)gradients. Eq.(9) balances the 0-1 loss and conventional surrogate by selecting (the trust) samples (index) for training progressively.
Updating with all the samples at once is not efficient for deep models, while training with mini-batch is more efficient and well supported for many deep learning tools. We thus propose a batch based curriculum loss Q̂(u) given as Eq.(10). We show that Q̂(u) is also a tighter upper bound of 0-1 loss objective J(u) compared with conventional loss Ĵ(u). This property is summarized in Corollary 1. Corollary 1. (Mini-batch Update) Suppose that base loss function l(u) ≥ 1 ( u < 0 ) , u ∈ R is an upper bound of the 0-1 loss function. Let b, m be the number of batches and batch size, respectively. Let uij ∈ R be the classification margin of the ith sample in batch j for i ∈ {1, ...,m} and j ∈ {1, ..., b}. Denote u = [u11, ..., umb]. Let n = mb. Define Q̂ (u) as follows:
Q̂ (u)= ∑b
j=1 min v∈{0,1}m max (∑m i=1 vij l(uij),m− ∑m i=1 vij + ∑m i=1 1 ( uij < 0 )) . (10)
Then J(u) ≤ Q (u) ≤ Q̂ (u) ≤ Ĵ (u) holds true.
Remark: Corollary 1 shows that a batch-based curriculum loss is also a tighter upper bound of 0-1 loss J(u) compared with the conventional surrogate loss Ĵ(u). This enables us to train deep models with mini-batch update. Note that random shuffle in different epoch results in a different batch-based curriculum loss. Nevertheless, we at least know that all the induced losses are upper bounds of 0-1 loss objective and are tighter than Ĵ(u). Moreover, all these losses are induced by the same base loss function l(·). Note that, our goal is to minimize the 0-1 loss. Random shuffle leads to a multiple surrogate training scheme. In addition, training deep models without shuffle does not have this issue.
We now present another curriculum loss E (u) which is tighter than Q(u). E (u) is an (scaled) upper bound of 0-1 loss. This property is summarized as Theorem 3.
Algorithm 1 Partial Optimization Input: ui for i ∈ {1, ..., n}, the selection threshold C; Output: Index set v = (v1, v2, . . . , vn); Compute the losses li = l(ui) for i = 1, ..., n; Sort samples (index) w.r.t. the losses {li}ni=1 in a non-decreasing order; // Get l1 ≤ · · · ≤ ln Initialize L0 = 0; for i = 1 to n do Li = Li−1 + li; if Li ≤ (C + 1− i) then
Set vi = 1; else
Set vi = 0; end if
end for
Theorem 3. (Scaled Bound) Suppose that base loss function l(u) ≥ 1 ( u < 0 ) , u ∈ R is an upper
bound of the 0-1 loss function. Let ui ∈ R be the classification margin of the ith sample for i ∈ {1, ..., n}. Denote u = [u1, ..., un]. Define E (u) as follows:
E (u)= min v∈{0,1}n
max (∑n
i=1 vil(ui), n− ∑n i=1 vi ) . (11)
Then J(u) ≤ 2E (u) ≤ 2Ĵ (u) holds true.
Remark: E(u) has similar properties to Q(u) discussed above. Moreover, it is tighter than Q(u), i.e. E(u) ≤ Q(u). Thus, it is less sensitive to outliers compared with Q(u). However, Q(u) can construct more adaptive curriculum by taking 0-1 loss into consideration during the training process.
Directly optimizing E(u) is not as efficient as that optimizing Q(u). We now present a batch loss objective Ê(u) given as Eq.(12). Ê(u) is also a tighter upper bound of 0-1 loss objective J(u) compared with conventional surrogate loss Ĵ(u). Corollary 2. (Mini-batch Update for Scaled Bound) Suppose that base loss function l(u) ≥ 1 ( u < 0 ) , u ∈ R is an upper bound of the 0-1 loss function. Let b, m be the number of batches
and batch size, respectively. Let uij ∈ R be the classification margin of the ith sample in batch j for i ∈ {1, ...,m} and j ∈ {1, ..., b}. Denote u = [u11, ..., umb]. Let n = mb. Define Ê(u) as follows:
Ê (u)= ∑b
j=1 min v∈{0,1}m max (∑m i=1 vij l(uij),m− ∑m i=1 vij ) . (12)
Then J(u) ≤ 2E (u) ≤ 2Ê (u) ≤ 2Ĵ (u) holds true.
All the curriculum losses defined above rely on minimizing a partial optimization problem (Eq.(13)) to find the selection index set v∗. We now show that the optimization of v with given classification margin ui ∈ R, i ∈ {1, ..., n} can be done in O(n log n). Theorem 4. (Partial Optimization) Suppose that base loss function l(u) ≥ 1 ( u < 0 ) , u ∈ R is an upper bound of the 0-1 loss function. For fixed ui ∈ R, i ∈ {1, ..., n}, an minimum solution v∗ of the minimization problem in Eq. (13) can be achieved by Algorithm 1:
min v∈{0,1}n
max (∑n i=1 vil(ui), C − ∑n i=1 vi ) , (13)
where C is the threshold parameter such that 0 ≤ C ≤ 2n.
Remark: The time complexity of Algorithm 1 isO(n log n). Moreover, it does not involve complex operations, and is very simple and efficient to compute.
Algorithm 1 can adaptively select samples for training. It has some useful properties to help us better understand the objective after partial minimization, we present them in Proposition 1.
Proposition 1. (Optimum of Partial Optimization) Suppose that base loss function l(u) ≥ 1 ( u < 0 ) , u ∈ R is an upper bound of the 0-1 loss function. Let ui ∈ R for i ∈ {1, ..., n} be fixed values. Without loss of generality, assume l(u1) ≤ l(u2) · · · ≤ l(un). Let v∗ be an optimum solution of the partial optimization problem in Eq.(13). Let T ∗ = ∑n i=1 v ∗ i and LT∗ = ∑T∗ i=1 l(ui). Then we have
LT∗ ≤ C + 1− T ∗ (14) LT∗+1 > C − T ∗ (15) LT∗+1 > max(LT∗ , C − T ∗) (16)
min v∈{0,1}n
max (∑n
i=1 vil(ui), C − ∑n i=1 vi ) = max(LT∗ , C − T ∗). (17)
Remark: When C ≤ n + ∑n i=1 1 ( ui < 0 ) , Eq.(17) is tighter than the conventional loss Ĵ(u). When C ≥ n, Eq. (17) is a scaled upper bound of 0-1 loss J(u) . From Eq.(17) , we know the optimum of the partial optimization problem (13) (i.e. our objective) is max(LT∗ , C − T ∗). When LT∗ ≥ C − T ∗, we can directly optimize LT∗ with the selected samples for training. When LT∗ < C − T ∗, note that LT∗+1 > max(LT∗ , C − T ∗) from Eq.(16), we can optimize LT∗+1 for training. Note that when T ∗ < n, we have that LT∗+1 ≤ Ln = ∑n i=1 l(ui), which is still tighter than the
conventional loss Ĵ(u). When T ∗ = n, for the parameter C ≤ n+ ∑n i=1 1 ( ui < 0 ) , we have that LT∗ = Ĵ(u) ≥ J(u) ≥ C − n = C − T ∗. Thus we can optimize max(LT∗ , C − T ∗) = Ĵ(u). In practice, when training with random mini-batch, we find that optimizing LT∗ in both cases instead of LT∗+1 does not make much influence.

heading: 2.3 NOISE PRUNED CURRICULUM LOSS
text: The curriculum loss in Eq.(9) and Eq.(11) expect to minimize the upper bound of the 0-1 loss for all the training samples. When model capability (complexity) is high, (deep network) model will still attain small (zero) training loss and overfit to the noisy samples.
The ideal model is that it correctly classifies the clean training samples and misclassifies the noisy samples with wrong labels. Suppose that the rate of noisy samples (by label corruption) is ∈ [0, 1]. The ideal model is to correctly classify the (1 − )n clean training samples, and misclassify the n noisy training samples. This is because the label is corrupted. Correctly classify the training samples with corrupted (wrong) label means that the model has already overfitted to noisy samples. This will harm the generalization to the unseen data.
Considering all the above reasons, we thus propose the Noise Pruned Curriculum Loss (NPCL) as
L (u) = min v∈{0,1}n
max (∑n
i=1 vil(ui), C− ∑n i=1 vi ) , (18)
where C = (1− )n or C = (1− )2n+ (1− ) ∑n i=1 1 ( ui < 0 ) .
When we know there are n noisy samples in the training set, we can leverage this as our prior. (The impact of misspecification of the prior is included in the supplement.) When C = (1 − )n (assume C, n are integers for simplicity), from the selection procedure in Algorithm 1, we know n1 samples with largest losses l(u) will be pruned. This is because C −
∑n i=1 vi + 1 ≤ 0 when∑n
i=1 vi ≥ (1 − )n + 1. Without loss of generality, assume l(u1) ≤ l(u2) · · · ≤ l(un). After pruning, we have v(1− )n+1 = · · · = vn = 0, the pruned loss becomes
L̃ (u) = min v∈{0,1}(1− )n
max (∑(1− )n
i=1 vil(ui), (1− )n− ∑(1− )n i=1 vi ) . (19)
It is the basic CL for (1− )n samples and it is the upper bound of ∑(1− )n i=1 1 ( ui < 0 ) . If we prune more noisy samples than clean samples, it will reduce the noise ratio. Then the basic CL can handle. Fortunately, this assumption is supported by the "memorization" effect in deep networks (Arpit et al., 2017), i.e. deep networks tend to learn clean and easy pattern first. Thus, the loss of noisy or hard
1When ∑(1− )n+1 i=1 l(ui) 6= 0, n samples will be pruned. Otherwise, n− 1 samples will be pruned.
Algorithm 2 Training with Batch Noise Pruned Curriculum Loss Input: Number of epochs N , batch size m, noise ratio ; Output: The model parameter w; Initialize model parameter w. for k = 1 to N do
Shuffle training set D; while Not fetch all the data from D do
Fetch a mini-batch D̂ from D; Compute losses {li}mi=1 for data in D̂; Compute the selection threshold C according to Eq.(21). Compute selection index v∗ by Algorithm 1; Update w = w − α∇l ( D̂v∗ ) w.r.t the subset D̂v∗ of D̂ selected by v∗;
end while end for
data tend to remain high for a period (before being overfitted). Therefore, the pruned samples with largest loss are more likely to be the noisy samples. After the rough pruning, the problem becomes optimizing basic CL for the remaining samples as in Eq.(19). Note that our CL is a tight upper bound approximation to the 0-1 loss, it preserves the robust property to some extent. Thus, it can handle case with small noise rate. Specifically, our CL(Eq.19) further select samples from the remaining samples for training adaptively according to the state of training process. This generally will further reduce the noise ratio. Thus, we may expect our NPCL to be robust to noisy samples. Note that, all the above can be done by the simple and efficient Algorithm 1 without explicit pruning samples in a separated step. Namely, our loss can do all these automatically under a unified objective form in Eq.(18).
When C = (1− )n, the NPCL in Eq.(18) reduces to basic CL E(u) in Eq.(11) with = 0. When C = (1− )2n+(1− ) ∑n i=1 1 ( ui < 0 ) , for an ideal target model (that misclassifies noisy samples
only), we know that E[C] = (1 − )2n + (1 − )E[ ∑n i=1 1 ( ui < 0 ) ] = (1 − )2n + (1 − ) n = (1 − )n. It has similar properties as choosing C = (1 − )n. Moreover, it is more adaptive by considering 0-1 loss during training at different stages. In this case, the NPCL in Eq.(18) reduces to the CLQ(u) in Eq.(9) when = 0. Note that C is a prior, users can defined it based on their domain knowledge.
To leverage the benefit of deep learning, we present the batched NPCL as L̂ (u) = ∑b
j=1 min v∈{0,1}m max (∑m i=1 vij l(uij), Ĉj− ∑m i=1 vij ) , (20)
where Ĉj = (1− )m or as in Eq.(21): Ĉj = (1− )2m+ (1− ) ∑m i=1 1 ( uij < 0 ) . (21)
Similar to Corollary 1, we know that L (u) ≤ L̂ (u). Thus, optimizing the batched NPCL is indeed minimizing the upper bound of NPCL. This enables us to train the model with mini-batch update, which is very efficient for modern deep learning tools. The training procedure is summarized in Algorithm 2. It uses Algorithm 1 to select a subset of samples from every mini-batch. Then, it uses the selected samples to perform gradient update.

heading: 3 EMPIRICAL STUDY

heading: 3.1 EVALUATION OF ROBUSTNESS AGAINST LABEL CORRUPTION
text: We evaluate our NPCL by comparing Generalized Cross-Entropy (GCE) loss (Zhang & Sabuncu, 2018), Co-teaching (Han et al., 2018b), Co-teaching+ (Yu et al., 2019), MentorNet (Jiang et al., 2018) and standard network training on MNIST, CIFAR10 and CIFAR100 dataset as in (Han et al., 2018b; Patrini et al., 2017; Goldberger & Ben-Reuven, 2017). Two types of random label corruption, i.e. Symmetry flipping (Van Rooyen et al., 2015) and Pair flipping (Han et al., 2018a), are
considered in this work. Symmetry flipping is that the corrupted label is uniformly assign to one of K−1 incorrect classes. Pair flipping is that the corrupted label is assign to one specific class similar to the ground truth. The noise rate of label flipping is chosen from {20%, 50%, 35%} as a representative. As a robust loss function, we further compare NPCL with GCE loss in detail with noise rate in {0%, 10%, 20%, 30%, 40%, 50%}. We employ same network architecture and network hyperparameters as in Co-teaching (Han et al., 2018b) for all the methods in comparison. Specifically, the batch size and the number of epochs is set to m= 128 and N = 200, respectively. The Adam optimizer with the same parameter as (Han et al., 2018b) is employed. The architecture of neural network is presented in Appendix L. For NPCL, we employ hinge loss as the base upper bound function of 0-1 loss. In the first few epochs, we train model using full batch with soft hinge loss (in the supplement) as a burn-in period suggested in (Jiang et al., 2018). Specifically, we start NPCL at 5th epoch on MNIST and 10th epoch on CIFAR10 and CIFAR100, respectively. For Coteaching (Han et al., 2018b) and MentorNet in (Jiang et al., 2018), we employ the open sourced code of Co-teaching (Han et al., 2018b). For Co-teaching+ (Yu et al., 2019), we employ the code provided by the authors. We implement NPCL by Pytorch. For NPCL, Co-teaching and Co-teaching+, we employ the true noise rate as parameter. Experiments are performed five independent runs. The error bar for STD is shaded.
For performance measurements, we employ both test accuracy and label precision as in (Han et al., 2018b). Label precision is defined as : number of clean samples / number of selected samples, which measures the selection accuracy for sample selection based methods. A higher label precision in the mini-batch after sample selection can lead to a update with less noisy samples, which means that model suffers less influence of noisy samples and thus preforms more robustly to label corruption.
The pictures of test accuracy and label precision vs. number of epochs on MNIST are presented in Figure 1. The results on CIFAR10 and CIFAR100 are shown in Figure 5 and Figure 6 in Appendix, respectively. It shows that NCPL achieves superior performance compared with GCE loss in terms of test accuracy. Particularly, NPCL obtains significant better performance compared with GCE loss in hard cases: Symmetry-50% and Pair-flip-35%, which shows that NPCL is more robust to label corruption compared with GCE loss. Moreover, NPCL obtains better performance on MNIST, and competitive performance on CIFAR10 and CIFAR100 compared with Co-teaching. Furthermore, NPCL achieves better performance than Co-teaching+ on CIFAR10 and two cases on MNIST. In addition, we find that Co-teaching+ is not stable on CIFAR100 with 50% symmetric noise. Note that NPCL is a simple plug-in for a single network, while Co-teaching/Co-teaching+ employs two networks to train the model concurrently. Thus, both the space complexity and time complexity of Co-teaching/Co-teaching+ is doubled compared with our NPCL.
Both our NPCL and Generalized Cross Entropy (GCE) loss are robust loss functions as plug-in for single network. Thus, we provide a more detailed comparison between our NPCL and GCE loss with noise rate in {0%, 10%, 20%, 30%, 40%, 50%}. The experimental results on CIFAR10 are presented in Figure 3. The experimental results on CIFAR100 and MNIST are provided in Figure 8 and Figure 7 in Appendix.From Figure 3, Figure 8 and Figure 7, we can observe that NPCL obtains similar and higher test accuracy in all the cases. Moreover, from Figure 3 and Figure 7, we can see that NPCL achieves similar test accuracy compared with the GCE loss when the noise rate is small. The improvement increases with the increase of the noise rate. Particularly, NPCL obtains remarkable improvement compared with the GCE loss on CIFAR10 with noise rate 50%. It shows that NPCL is more robust compared with GCE loss against label corruption. GCE loss employs all samples for training, while NPCL prunes the noisy samples adaptively. As a result, GCE loss still employs samples with wrong labels for training, which misleads the model. Thus, NPCL obtains better performance when the noise rate becomes large.

heading: 3.2 MORE EXPERIMENTS WITH DIFFERENT NETWORK ARCHITECTURES
text: We follow the experiments setup in (Lee et al., 2019). We use the online code of (Lee et al., 2019) , and only change the loss for comparison. We cite the numbers of Softmax, RoG and D2L (Ma et al., 2018) in (Lee et al., 2019) for comparison.
The test accuracy results on uniform noise, semantic noise and open-set noise are shown in Table 1, Table 2 and Table 3, respectively. From Table 1, we can observe that both NPCL and CL outperforms Softmax (cross-entropy) and RoG (cross-entropy) on five cases for uniform noise. Note that RoG is an ensemble method, while CL/NPCL is a single loss for network training, one can combine them to boost the performance. From Table 2, we can see that CL obtains consistently better performance than cross-entropy and D2L (Ma et al., 2018) for the semantic noise. Table 3 shows that NPCL achieves competitive performance compared with RoG for open-set noise.
We further evaluate the performance of CL/NPCL on the Tiny-ImageNet dataset. We use the ResNet18 network as the test-bed. For GCE loss, we employ the default hyper-parameter q = 0.7 in all cases. All the methods are performed five runs with seeds {1, 2, 3, 4, 5}. The curve of mean test accuracy (shaded in std) are provided in Figure 2. We can see that NPCL and CL obtain higher test accuracy than generalized cross-entropy loss and stand cross-entropy loss on both cases. Note that CL does not have parameters, it is much convenient to use.

heading: 4 CONCLUSION AND FURTHER WORK
text: In this work, we proposed a curriculum loss (CL) for robust learning. Theoretically, we analyzed the properties of CL and proved that it is tighter upper bound of the 0-1 loss compared with conventional summation based surrogate losses. We extended our CL to a more general form (NPCL) to handle large rate of label corruption. Empirically, experimental results on benchmark datasets show the robustness of the proposed loss. As a further work, we may improve our CL to handle imbalanced distribution by considering diversity for each class. Moreover, it is interesting to investigate the influence of different base loss functions in CL and NPCL.

heading: ACKNOWLEDGEMENT
text: We sincerely thank the reviewers for their insightful comments and suggestions. This paper was supported by Australian Research Council grants DP180100106 and DP200101328.

heading: A EXPLANATION OF THEOREM 1 FOR ROBUST LEARNING
text: Theorem. (Monotonic Relationship) ((Hu et al., 2018) Let p(x, y) and q(x, y) be the training and test density,respectively. Define r(x, y) = q(x, y)/p(x, y) and ri = r(xi, yi). Let l(ŷ, y) = 1 ( sign(ŷ) 6= y ) and l(ŷ, y) = 1 ( argmaxk(ŷk) 6= y ) be 0-1 loss for binary classification and multi-class classification, respectively. Let f(·) be convex with f(1) = 0. Define risk R(θ), empirical risk R̂(θ), adversarial riskRadv(θ) and empirical adversarial risk R̂adv(θ) as
R(θ) = Ep(x,y) [l(gθ(x), y)] (22)
R̂(θ) = 1 n ∑n i=1 l(gθ(xi), yi) (23) Radv(θ) = sup r∈Uf Ep(x,y) [r(x, y)l(gθ(x), y)] (24)
R̂adv(θ) = sup r∈Ûf
1
n ∑n i=1 ril(gθ(xi), yi), (25)
where Uf = { r(x, y) ∣∣Ep(x,y) [f (r(x, y))] ≤ δ,Ep(x,y) [r(x, y)] = 1, r(x, y) ≥ 0,∀(x, y) ∈ X × Y } and Ûf = { r ∣∣ 1 n ∑n i=1 f(ri) ≤ δ, 1 n ∑n i=1 ri = 1, r ≥ 0 } . Then we have that
If Radv(θ1) < 1, then R(θ1) < R(θ2) ⇐⇒ Radv(θ1) < Radv(θ2). (26) If Radv(θ1) = 1, then R(θ1) ≤ R(θ2) ⇐⇒ Radv(θ2) = 1. (27)
The same monotonic relationship holds between their empirical approximation: R̂(θ) and R̂adv .
Hu et al. (2018) show that minimizing (empirical) risk is equivalent to minimize the (empirical) adversarial risk (worst-case risk) for 0-1 loss. Thus, we can directly optimize the risk instead of the worst-case risk. Specifically, suppose we have an observable training distribution p(x, y). The observable distribution p(x, y) may be corrupted from an underlying clean distribution q(x, y). We train a model based on the training distribution p(x, y), and we want our model to perform well on the clean distribution q(x, y). Since we do not know the clean distribution q(x, y), we want our model to perform well for the worst-case estimate of the clean distribution, with the assumption that the f -divergence between the corrupted distribution p and the clean distribution q is bounded by δ. Note that the underlying clean distribution is fixed but unknown, given the corrupted training distribution, the smallest δ that bounds the divergence between the corrupted distribution and clean distribution measures the intrinsic difficulty of the corruption, and it is also fixed and unknown. The corresponding worst-case distribution w.r.t the smallest δ is an estimate of the true clean distribution, and this worst-case risk upper bounds the risk of the true clean distribution. In addition, this bound is tighter than the other worst-case risks w.r.t larger δ. Formally, the upper bound w.r.t the smallest δ is given as
G(θ) := sup q∈Ũf Eq(x,y) [l(gθ(x), y)] (28)
where Ũf is an equivalent constrainted set w.r.t Uf for q(x, y). Then, we have
G(θ) := sup q∈Ũf Eq(x,y) [l(gθ(x), y)] = sup r∈Uf Ep(x,y) [r(x, y)l(gθ(x), y)] (29)
When l(·) is 0-1 loss, from Theorem 1, we know that minimizeG(θ) is equivalent to minimize G̃(θ). Thus, we can minimize G̃(θ) instead of G(θ).
G̃(θ) := Ep(x,y) [l(gθ(x), y)] (30)
Minimize the Eq.(30) enables us to minimize the Eq.(28) without knowing the true divergence parameter δ beforehand. Usually, minimizing the upper bound can decrease the true risk under clean distribution. Particularly, when the clean distribution coincides with the worst-case estimate w.r.t the smallest δ, minimizing the risk under the corrupted training distribution leads to the same minimizer as minimizing the risk under the clean distribution.
Relationship between label corruption and general corruption
Label corruption is a special case of general corruption. Label corruption restricts the corruption in the space Y instead of the space X × Y . That is to say, the training distribution p(x) is same as the clean distribution q(x) over X . Then, we have the robust risk for label corruption as
Gy(θ) := sup q∈Ũf∩H Eq(x,y) [l(gθ(x), y)] (31)
where H := {q(x, y) |q(x) = p(x),∀(x, y) ∈ X × Y }. The supremum in Gy(θ) is taken over Ũf ∩ H , while the supremum in G(θ) is taken over Ũf . Due to the additional constrain q(x) = p(x),∀(x, y) ∈ X × Y , we thus know that the robust risk Gy(θ) is bounded by G(θ), i.e., Gy(θ) ≤ G(θ). Moreover, it is more piratical and important to be robust for both label corruption and feature corruption.

heading: B PROOF OF THEOREM 2
text: Proof. Because 1 ( u < 0 ) ≤ l(u), we have ∑n i=1 l(ui) ≥ ∑n i=1 1 ( ui < 0 ) . Then
Q (u) = min v∈{0,1}n
max (∑n
i=1 vil(ui), n− ∑n i=1 vi + ∑n i=1 1 ( ui < 0 )) (32)
≤ max (∑n
i=1 l(ui), n− ∑n i=1 1 + ∑n i=1 1 ( ui < 0 )) (33)
= max (∑n
i=1 l(ui), ∑n i=1 1 ( ui < 0 )) (34)
= ∑n
i=1 l(ui) (35)
Since loss Ĵ(u) = ∑n i=1 l(ui), we obtain Q (u) ≤ Ĵ (u).
On the other hand, we have that
Q (u) = min v∈{0,1}n
max (∑n
i=1 vil(ui), n− ∑n i=1 vi + ∑n i=1 1 ( ui < 0 )) ≥ min v∈{0,1}n n− ∑n i=1 vi + ∑n i=1 1 ( ui < 0 ) (36)
= ∑n i=1 1 ( ui < 0 ) (37)
Since J(u) = ∑n i=1 1 ( ui < 0 ) , we obtain Q (u) ≥ J (u)

heading: C PROOF OF COROLLARY 1
text: Proof. Since n = mb, similar to the proof of Q (u) ≤ Ĵ (u), we have
Q̂ (u) = ∑b
j=1 min v∈{0,1}m max (∑m i=1 vij l(uij),m− ∑m i=1 vij + ∑m i=1 1 ( uij < 0 )) ≤ ∑b
j=1 max (∑m i=1 l(uij),m− ∑m i=1 1 + ∑m i=1 1 ( uij < 0 )) (38)
= ∑b
j=1 max (∑m i=1 l(uij), ∑m i=1 1 ( uij < 0 )) (39)
= ∑b
j=1 ∑m i=1 l(uij) = Ĵ (u) (40)
On the other hand, since the group (batch) separable sum structure, we have that Q̂ (u) = ∑b
j=1 min v∈{0,1}m max (∑m i=1 vij l(uij),m− ∑m i=1 vij + ∑m i=1 1 ( uij < 0 )) = min
v∈{0,1}n ∑b j=1 max (∑m i=1 vij l(uij),m− ∑m i=1 vij + ∑m i=1 1 ( uij < 0 )) (41)
≥ min v∈{0,1}n max ( b∑ j=1 m∑ i=1 vij l(uij), n− b∑ j=1 m∑ i=1 vij + b∑ j=1 m∑ i=1 1 ( uij < 0 )) (42)
= Q (u) ≥ J (u) (43)

heading: D PROOF OF PARTIAL OPTIMIZATION THEOREM (THEOREM 4)
text: Proof. For simplicity, let li = l(ui), i ∈ {1, ..., n}. Without loss of generality, assume l1 ≤ l2 · · · ≤ ln. Let v∗ be the solution obtained by Algorithm 1. Assume there exits a v such that
max ( n∑ i=1 vili, C − n∑ i=1 vi ) < max ( n∑ i=1 v∗i li, C − n∑ i=1 v∗i ) . (44)
Let T = n∑ i=1 vi and T ∗ = n∑ i=1 v∗i .
Case 1: If T = T ∗, then there exists an vk = 1 and v∗k = 0. From Algorithm 1, we know k > T ∗ (v∗k = 0⇒ k > T ∗) and lk ≥ lj , j ∈ {1, ..., T ∗}. Then we know n∑ i=1 v∗i li ≤ n∑ i=1 vili. Thus, we can achieve that
max ( n∑ i=1 v∗i li, C − n∑ i=1 v∗i ) = max( n∑ i=1 v∗i li, C − n∑ i=1 vi) (45)
≤ max ( n∑ i=1 vili, C − n∑ i=1 vi ) . (46)
This contradicts the assumption in Eq.(44) Case 2: If T > T ∗, then there exists an vk = 1 and v∗k = 0. Let LT∗ = T∗∑ i=1 li. Since lk ≥ 0, we have LT∗ + lk ≥ LT∗ . From Algorithm 1, we know that LT∗ + lk > C − T ∗. Thus we obtain that
max ( n∑ i=1 vili, C − n∑ i=1 vi ) ≥ LT∗ + lk (47)
≥ max ( LT∗ , C − T ∗ ) (48)
= max ( n∑ i=1 v∗i li, C − n∑ i=1 v∗i )
(49)
This contradicts the assumption in Eq.(44)
Case 3: If T < T ∗, we obtain C − T ≥ C − T ∗ + 1. Then we can achieve that max ( n∑ i=1 v∗i li, C − n∑ i=1 v∗i ) = max ( LT∗ , C − T ∗ ) (50)
≤ C + 1− T ∗ (51) ≤ C − T (52)
= C − ∑n
i=1 vi (53)
≤ max ( n∑ i=1 vili, C − n∑ i=1 vi ) . (54)
This contradicts the assumption in Eq.(44).
Finally, we conclude that v∗ obtained by Algorithm 1 is the minimum of the optimization problem given in (13).

heading: E PROOF OF PROPOSITION 1
text: Proof. Note that T ∗ = n∑ i=1 v∗i , from the condition of v ∗ i = 1 in Algorithm 1, we know that LT∗ ≤ C+1−T ∗. From the condition of v∗k = 0 in Algorithm 1, we know that LT∗+1 > C−T ∗. Because l(ui) ≥ 1 ( ui < 0 ) ≥ 0 for i ∈ {1, ..., n}, we have LT∗+1 = LT∗ + l(uT∗+1) ≥ LT∗ . Thus, we obtain LT∗+1 > max(LT∗ , C − T ∗). By substitute the optimum v∗ into the optimization function, we obtain that
min v∈{0,1}n
max (∑n
i=1 vil(ui), C − ∑n i=1 vi )
(55)
= max (∑n
i=1 v∗i l(ui), C − ∑n i=1 v∗i )
(56)
= max(LT∗ , C − T ∗) (57)

heading: F PROOF OF THEOREM 3
text: Proof. We first prove that objective (11) is tighter than the loss objective Ĵ(u) in Eq.(8). After this, we prove that objective (11) is an upper bound of the 0/1 loss defined in equation (7).
For simplicity, let li = l(ui), we obtain that
E (u) = min v∈{0,1}n max( n∑ i=1 vil(ui), n− n∑ i=1 vi) (58)
≤ max( n∑ i=1 l(ui), (n− n∑ i=1 1)) (59)
= n∑ i=1 l(ui). (60)
Note that Ĵ (u) = n∑ i=1 l(ui), thus, we have E (u) ≤ Ĵ (u). Without loss of generality, assume l1 ≤ l2 · · · ≤ ln. Let Li = i∑
j=1 lj , T = n∑ i=1 v∗i , where
v∗=[v∗1 , v ∗ 2 · · · v∗n]T is the optimum of v for fixed u. Let k = n∑ i=1 1(ui ≥ 0). Then we achieve that the 0/1 loss J(u) is as follows:
J(u) = n∑ i=1 1(ui < 0)=n− k. (61)
From Algorithm 1 with C = n, we achieve that LT ≤ n− T + 1 and LT+1 > n− T . Case 1: If k ≥ T , we can achieve that
2E (u)− J(u) = 2max(LT , n− T )− (n− k) (62) ≥ 2(n− T )− (n− k) (63) = n+ k − 2T ≥ 0.
Case 2: If k < T, n− T ≥ LT , we can obtain that 2E (u)− J(u) = 2(n− T )− (n− k) = n+ k − 2T. (64)
Since k < T , if follows that
LT = Lk+ T∑ j=k+1 lj ≥ Lk+ T∑ j=k+1 1 (65)
= Lk + T − k (66) ≥ T − k. (67)
Together with n− T ≥ LT , we can obtain that n− T ≥ LT ≥ T − k ⇒ n+ k − 2T ≥ 0. (68)
Thus, we can achieve that
2E (u)− J(u) = n+ k − 2T ≥ 0. (69)
Case 3: If k < T, n− T < LT , we can obtain that
2E (u)− J(u) = 2max(LT , n− T )− (n− k) (70) = 2LT − (n− k) (71) > (n− T ) + LT − n+k. (72)
From (67), we have LT ≥ T − k. Together with (72), it follows that 2E (u)− J(u) > (n− T ) + (T − k)− n+k ≥ 0. (73)
Finally, we can achieve that J(u) ≤ 2E (u) ≤ 2Ĵ (u) .

heading: G PROOF OF COROLLARY 2
text: Proof. Since n = mb, similar to the proof of Q̂ (u) ≤ Ĵ (u), we have Ê (u) = ∑b
j=1 min v∈{0,1}m max (∑m i=1 vij l(uij),m− ∑m i=1 vij )
≤ ∑b
j=1 max (∑m i=1 l(uij),m− ∑m i=1 1 )
(74)
= ∑b
j=1 max (∑m i=1 l(uij), 0 )
(75)
= ∑b
j=1 ∑m i=1 l(uij) = Ĵ (u) (76)
On the other hand, since the group (batch) separable sum structure, we have that Ê (u) = ∑b
j=1 min v∈{0,1}m max (∑m i=1 vij l(uij),m− ∑m i=1 vij )
= min v∈{0,1}n ∑b j=1 max (∑m i=1 vij l(uij),m− ∑m i=1 vij )
(77)
≥ min v∈{0,1}n max ( b∑ j=1 m∑ i=1 vij l(uij), n− b∑ j=1 m∑ i=1 vij )
(78)
= E (u) (79)
Together with Theorem 3, we obtain that J(u) ≤ 2E (u) ≤ 2Ê (u) ≤ 2Ĵ (u)

heading: H MULTI-CLASS EXTENSION
text: For multi-class classification, denote the groudtruth label as y ∈ {1, ...,K}. Denote the classification prediction (the last layer output of networks before loss function) as ti, i ∈ {1, ...,K}. Then, the classification margin for multi-class classification can be defined as follows
u = ty −max i 6=y ti. (80)
We can see that 1 ( u < 0 ) = 1 ( ty −max
i 6=y ti < 0
) is indeed the 0-1 loss for multi-class classification.
With the classification margin u, we can compute the base loss l(u) ≥ 1 ( u < 0 ) . In this work, we employ the hinge loss. As we need the upper bound of 0-1 loss, the multi-class hard hinge loss function Moore & DeNero (2011) can be defined as
H(t, y) = max(1− u, 0) = max(1− ty +max i 6=y ti, 0). (81)
The multi-class hard hinge loss in Eq.(81) is not easy to optimize for deep networks. We propose a novel soft multi-class hinge loss function as follows:
S(t, y) =
{ max(1− ty +max
i 6=y ti, 0) , ty −max i 6=y ti ≥ 0
max(1− ty + LogSumExp(t), 0) , ty −max i 6=y
ti < 0. (82)
The soft hinge loss employs the LogSumExp function to approximate the max function when the classification margin is less than zero, i.e., misclassification case. Intuitively, when the sample is misclassified, it is far away from being correctly separate by a positive margin (e.g. margin u ≥ 1). In this situation, a smooth loss function can help speed up gradient update. Because LogSumExp(t) > maxi∈{1,···K} ti we know that the soft hinge loss is an upper bound of the hard hinge loss, i.e., S(t, y) ≥ H(t, y) . Moreover, we can obtain a new weighted loss F (t, y;β) = βS(t, y) + (1− β)H(t, y), β ∈ [0, 1] that is also an upper bound of 0-1 loss.

heading: I EVALUATION OF EFFICIENCY OF THE PROPOSED SOFT-HINGE LOSS
text: We compare our soft multi-class hinge loss with hard multi-class hinge loss Moore & DeNero (2011) on CIFAR100 dataset training with Adam and SGD optimizer, respectively. We keep both the network architecture and hyperparameters same. We employ the default learning rate and momentums of Adam optimizer in PyTorch toolbox, i.e. lr = 10−3, β1 = 0.9, β2 = 0.999. For SGD optimizer, the learning rate (lr) and momentum (ρ) are set to lr = 10−2 and ρ = 0.9 respectively.
The pictures of training/test accuracy v.s number of epochs are presented in Figure 4. We can observe that both the training accuracy and the test accuracy of our soft hinge loss increase greatly fast as the number of epochs increase. In contrast, the training and test accuracy of hard hinge loss grow very slowly. The training accuracy of soft hinge loss can arrive 100% trained with both optimizers. Both
training and test accuracy of soft hinge loss are consistently better than hard hinge loss. In addition, training accuracy of hard hinge loss can also reach 100% when SGD optimizer is used. However, its test accuracy is lowever than that of soft hinge loss.
J IMPACT OF MISSPECIFIED ESTIMATION OF NOISE RATE
We empirically analyze the impact of misspecified prior for the noise rate . The average test accuracy over last ten epochs on MNIST for different priors are reported in Table 4. We can observe that NPCL is robust to misspecified prior for small noise cases (Symmetry-20%). Moreover, it becomes a bit more sensitive on large noise case (Symmetry-50%) and on the pair flipping case (Pair-35%).

heading: K RELATED LITERATURE
text: Curriculum Learning: Curriculum learning is a general learning methodology that achieves success in many area. The very beginning work of curriculum learning (Bengio et al., 2009) trains a model gradually with samples ordered in a meaningful sequence, which has improved performance on many problems. Since the curriculum in (Bengio et al., 2009) is predetermined by prior knowledge and remained fixed later, which ignores the feedback of learners, Kumar et al. (Kumar et al., 2010) further propose Self-paced learning that selects samples by alternative minimization of an augmented objective. Jiang et al. (Jiang et al., 2014) propose a self-paced learning method to select samples with diversity. After that, Jiang et al. (Jiang et al., 2015) propose a self-paced curriculum strategy that takes different priors into consideration. Although these methods achieve success, the relation between the augmented objective of self-paced learning and the original objective (e.g. cross entropy loss for classification) is not clear. In addition, as stated in (Jiang et al., 2018), the alternative update in self-paced learning is not efficient for training deep networks.
Learning with Noisy Labels: The most related works are the sample selection based methods for robust learning. This kind of works are inspired by curriculum learning (Bengio et al., 2009). Among them, Jiang et al. (Jiang et al., 2018) propose to learn the curriculum from data by a mentor net. They use the mentor net to select samples for training with noisy labels. Co-teaching (Han et al., 2018b) employs two networks to select samples to train each other and achieve good generalization performance against large rate of label corruption. Co-teaching+ (Yu et al., 2019) extends Coteaching by selecting samples with disagreement of prediction of two networks. Compared with Co-teaching/Co-teaching+, our CL is a simple plugin for a single network. Thus both space and time complexity of CL are half of Co-teaching’s. Recently, Zhang & Sabuncu (2018) propose a generalized Cross-entropy loss for robust learning.
Construction of tighter bounds of 0-1 loss: Along the line of construction of tighter bounds of the 0-1 loss, many methods have been proposed. To name a few, Masnadi-Shirazi et al. (MasnadiShirazi & Vasconcelos, 2009) propose Savage loss, which is a non-convex upper bound of the 0-1
loss function. Bartlett et al. (Bartlett et al., 2006) analyze the properties of the truncated loss for conventional convex loss. Wu et al. (Wu & Liu, 2007) study the truncated hinge loss for SVM. Although the results are fruitful, these works are mainly focus on loss function at individual data point, they do not have sample selection property. In contrast, our curriculum loss can automatically select samples for training. Moreover, it can be constructed in a tighter way than these individual losses by employing them as the base loss function.

heading: L ARCHITECTURE OF NEURAL NETWORKS
text: CNN on MNIST CNN on CIFAR-10 CNN on CIFAR-100 28×28 Gray Image 32×32 RGB Image 32×32 RGB Image
3×3 conv, 128 LReLU 3×3 conv, 128 LReLU 3×3 conv, 128 LReLU 2×2 max-pool, stride 2
dropout, p = 0.25 3×3 conv, 256 LReLU 3×3 conv, 256 LReLU 3×3 conv, 256 LReLU 2×2 max-pool, stride 2
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→100

Review summaries:
This paper proposes a new loss function: curriculum loss, which is a meta-loss function that we can still specify an existing surrogate loss to use this loss function. This meta-loss function guarantees to be tighter than using a traditional pointwise-sum loss function as used in the empirical risk minimization framework. Intuitively, the proposed CL loss embed the sample selection process in the objective function. The authors suggest that it is robust against label corruption because it is tighter and provided promising experimental results.