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 is robust to outliers, it is also 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 stagewise 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 noisy MNIST, CIFAR10 and CIFAR100 dataset validate the robustness of the proposed loss.
Summary: 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.
========================================================
Clarity:
The paper is well-written and easy to follow. 
========================================================
Significance:
The proposed paradigm is interesting and I am convinced that it can be useful under label noise. The experiments look promising. Future work about the analysis of NPCL/CL is also interesting to consider (e.g., which surrogate loss to use, rigorous theoretical guarantee, etc.). I think the proposed method is impactful. 
========================================================
Comments:
The proposed method is interesting and can give a tighter bound for any surrogate loss by using this method (CL). Moreover, the author suggested a simple extension of CL for label corruption (NPCL) and the performance is impressive. I would like to vote accept for this paper but the following point highly concerns me and I am not sure about the correctness (see the concern below). It is about the motivation not the proposed method.
Concerns about motivation:
I disagree with the original motivation of this paper. The authors used the result of Hu et al. 2018 to motivate the use of CL. To my knowledge, the main point raised by Hu et al. is as follows:
In classification, minimizing the adversarial risk yields the same solution as using the standard empirical risk. This suggests that minimizing the adversarial risk may not enhance the robustness of a classifier. Yet, it may still be useful when we consider regression (other settings but not classification). As a result, in classification, we should try other methods to make a robust classifier. Then, Hu et al. considered to utilize some kind of structural assumption to make a robust classifier. From their title: "Does Distributionally Robust Supervised Learning Give Robust Classifiers?", I think they suggested "No" as an answer and the discussion about 0-1 loss in the curriculum loss paper will be contradicted to them from the motivation perspective. 
Furthermore, regarding the adversarial risk, it is not focusing on the label noise but rather the noise of the feature-label pair, i.e, perturb (x,y) adversarially within an f-divergence ball. However, in my opinion, if we randomly flip the label of the data regardless of x (as the authors and existing work did in experiments when considering label corruption: symmetric, partial, etc.), we cannot be confident to state that the f-divergence between test distribution and corrupted training distribution is small under label noise. 
Another point to motivate the use of 0-1 loss that the author mentioned is when we have outliers (Masnadi-Shirazi & Vasconcelos, 2009). This makes sense and this is a famous argument to discourage the use of too steep loss functions, e.g., exponential loss. I think this motivation is fine but it is not directly related to label corruption because we do not add out-of-distribution data but rather the label noise. Furthermore, the authors did not inject any outliers in the experiments in my understanding. I think this is totally no problem because we are focusing on label noise here, but this makes the motivation about outliers less important when we are talking about label noise.
I think the most important direction both in theory and experiments about the robustness to label noise of the 0-1 loss is that 0-1 loss satisfies a "symmetric property", i.e., \ell(z)+\ell(-z) = Constant for a margin-based loss function in binary classification. Under symmetric label noise, "the minimizer of the expected symmetric noise risk (a risk that the label is corrupted by coin flipping noise) is identical to the minimizer of the clean risk (normal risk)". Although it is not empirically but the expected version, it gives a good insight about the advantage of directly minimizing 0-1 loss under label noise. This is first pointed out by 
[1] Manwani et al.: Noise tolerance under risk minimization, IEEE Transactions on Cybernetics 43 (2013) 
[2] Ghosh et al.: Making risk minimization tolerant to label noise Neurocomputing 160 (2015): 93-107. 
([1] focused on the 0-1 loss while [2] extended it to symmetric losses.)
Then, it was extended to the multiclass loss by the following paper:
[3] Ghosh et al.: Robust loss functions under label noise for deep neural networks. AAAI2017. 
The advantage of symmetric losses is also discussed in this paper that the authors already cited in the symmetric noise experiment section. 
[4] van Rooyen et al.: Learning with symmetric label noise: The importance of being unhinged, NeurIPS2015
The advantage of the symmetric condition and 0-1 loss is also discussed in a more general noise scenario and more evaluation metrics:
[5] van Rooyen et. al: An average classification algorithm. arXiv:1506.01520, 2015
[6] Charoenphakdee et al.: On symmetric losses for learning from corrupted labels, ICML2019
And the following paper that was also cited in the submitted work and compared:
[7] Zhang and Sabuncu: Generalized cross-entropy loss for training deep neural networks with noisy labels, NeurIPS2018
is also inspired by the robustness of the symmetric losses (including 0-1 loss). They argued that although the symmetric loss (MAE) for multiclass proposed by Ghosh AAAI2017 is robust, it is hard to train for challenging datasets, and they try to relevate this condition while making it easier to train.  This paper outperformed [7] and I think it is clearer and better to build a story along this line.
In short, here is the key message why I think the current motivation does not feel right. When we have noisy labeled data, instead of motivating the use of 0-1 loss by suggesting that 
"If we have clean labeled data, minimizing the "adversarial" ERM risk using "clean" labeled data yields the same minimizer as minimizing the "standard" ERM risk using "clean" labeled data",
I believe the story to motivate the robustness of 0-1 loss under label noise should be 
"If we have noisy labeled data, minimizing the "standard" or "modified" risk using "noisy" labeled data yields the same minimizer as minimizing the "standard" ERM risk using "clean" label data"
The latter statement corresponds to the literature I suggested. 
Apart from the motivation raised by the authors, as we can see from this curriculum loss paper, NPCL nicely outperformed generalized cross entropy loss in [7], which is impressive.
========================================================
Decision.
I strongly feel that motivating the noise robustness of 0-1 loss by discussing about the adversarial risk (Hu et al.) is misleading. Nevertheless, I feel the proposed method itself makes a lot of sense and I am impressed by the results. If the author can convince me that using the current motivation of the paper is suitable, I am happy to improve the score. Another way is to agree to modify the motivation part. Given the experiments were done, it is not to difficult to change the motivation of the paper. At this point, I have decided to give a weak reject. 
========================================================
Questions:
1. Is it straightforward to combine NPCL with Co-teaching/Mentornet/Co-teaching+?
2. Does the traditional theory about classification-calibration (Zhang, 2004, Bartlett+, 2006) can guarantee the Bayes-optimal solution if we use NPCL?
========================================================
Minor comments:
1. Page 9: Both our NPCL and Generalized Cross Entropy(GCE) << space missing between Entropy and (
Update: I have read the rebuttal. Although I am still not fully convinced with the motivation of the paper and still doubting whether NPCL works well because of the given motivation, I still believe that the proposed NPCL should give a new perspective to deal with noisy labels. I like the idea of the paper. Thus, I change the score to Weak Accept.