Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: The paper performs a comprehensive analysis on a sub-category of noisy-label classification techniques. Following that, the paper proposed a new improved method to handle sample selection-based noisy-label classification techniques.
main_review: Strength: (1) Provide comprehensive analysis on one category of noisy label classification method. (2) experiment dataset is diverse covering many commonly used datasets and setups.

Weakness: (1) the improvement in classification performance is marginal. (2) A critical state-of-the-art is not provided (see below). (2) Experiment results could be improved (need a t-test proving the experiment results are significant). (3) The paper only considers one category of noisy-label classification methods. There are many other categories that may provide better performance than the proposed methods (e.g., early learning, error bounded approach, etc.).

summary_of_the_review: I like this paper. It discusses the weakness of some noisy-label learning methods. The paper also conducts a solid experiment (except missing one critical comparison -- MentorMix). MentorMix is also a sample selection-based approach. It has demonstrated superior performance in dealing with the noisy labels. Because MentorMix uses mixup to enrich data, it should be robust against data imbalance. I would like to see a comparison of MentorMix and the proposed method.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: 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.

main_review: Strengths
- The proposed approach is justified theoretically
- Many datasets and comparison methods used and thus the proposed approach is also validated empirically

Weaknesses
- I could not find a major weakness in the paper. It would be interesting to see the work extended to other types of data (NLP, Speech...)

Typos
- 2.3, Soft truncation : « given a random variable X » probably

summary_of_the_review: The authors propose a novel algorithm, justified theoretically and validated empirically to improve the sample selection in the case of noisy labels training.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: 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).
main_review: The problem of label noise + (extreme) class imbalance is an interesting yet under studied direction with a potentially significant impact to many applications (e.g., worst-group generalization, fairness), which the paper does a good job brining attention to. The paper is well written and overall easy to follow, despite that some clarification may help readers better understand the proposed methods (see minor concern below).

Some of my major concerns are:

1. To implement the proposed method, it seems that naively one will need to keep track of the history of losses of every sample in the training set. For soft truncation (Eq. 7), one can simply keep a per-sample running mean and selection times in memory; for hard truncation (Eq. 8), it seems much more complicated. Can authors add some details of the space complexity overhead to use the proposed method? These can be argued as one major disadvantage when compared to other regularization-based LNL methods (Appendix B.2).
2. The hard truncation criterion is derived based on a Markovian assumption. Does it contradict with some popular tricks training DNN, such as temporal averaging, or momentum? For instance, it seems that all models in the paper are trained using ADAM where momentum is used hence the Markovian assumption is broken. Can the authors please comment?
3. The experiments mostly are designed with relatively low noise (20% and 40%). Sample selection can suffer typically from high-noise settings and the so-called self-confirmation trap. It would be good to compare the proposed method to other baselines in such settings, since so far all methods perform quite comparably across all datasets and noise types where the proposed method outperforms other slightly by 1-2% (Table 1, 2, 3, 9).

A minor concern/suggestion:

1. The paper only discussed related work very briefly in Sec 3.1 (Baselines). A dedicated related work section should help improve the paper: How do other sample selection consider different reasons for samples having large losses? Have they not considered at all? Any other paper that challenged the small-loss/large-loss assumption in any way?
2. How is Step 4/5 in Algorithm 1 optimized? At a first glance, this amounts to solving a combinatorial problem in each mini-batch? Perhaps the authors has a better way to do so?
3. How are hparams (sigma and tau_min) tuned given a *noisy* validation set?
summary_of_the_review: The proposed method is a novel method concerning an interesting yet under studied direction with a potentially significant impact to many applications (e.g., worst-group generalization, fairness), which the paper does a good job brining attention to. Results are overall promising, in particular showing very good results dealing with label noise + extreme class imbalance (Figure 2). Some concerns should be addressed during open discussion with authors.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: 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.
main_review: Pros:
1. This paper is well written and easy to follow. 
2. The goal of this paper is well-motivated, with a detailed discussion about the uncertainty of losses in sample selection.
3. The technical steps are clearly explained with theoretical justification.

Cons:

As shown in Table5, the difference between DivideMix-S/H and the original DivideMix is a little bit small. It will be more convincing if the authors could report the error bar of these experiments.

summary_of_the_review: From my perspective, this work studies an important problem in previous sample selection criteria in learning with noisy labels. And the proposed method is clearly explained and theoretical analyses have been provided. Sufficient experiment results validate the effectiveness of this approach, although the results in semi-supervised learning seem not very convincing. Overall, I tend to accept this paper.


################# After rebuttal ##################\
Thanks for the responses. I still tend to accept this paper and keep my score.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper proposes a probabilistic-based sample selection approach CNLCU to distinguish whether the training sample is mislabeled or ignored. The experimental results show that the proposed method outperforms most up-to-date sample selection methods.
main_review: Learning with noisy labels is an important issue and has attracted much attention. This paper proposes a novel sample selection method, namely CNLCU, to optimize model training. CNLCU is based on the probabilistic constraint relaxation and can select ‘good’ samples with time intervals.

Overall, the method proposed in the paper is technically sound. The authors provide complete derivations in the appendix, which shows the correctness of the features of the proposed method. The experimental design is reasonable, which follows the conventions in many noisy label learning studies. The comparison with well-selected baselines in different noise levels shows the advantages of the proposed method. The paper is well organized and clearly presented.

Weaknesses:
- It would better if the noise ratios cover a wider range rather than only 20% and 40% are selected. Usually, evaluations also should be made under heavily noisy situations where noise ratios are large than 50%. This will make the conclusion more convincing.
- The evaluation matric as well as the analysis should be diverse. CNLCU outperforms in terms of mean accuracy. E.g., if the dataset is imbalanced, the accuracy may be not enough to comprehensively describe the performance. I also notice that on some datasets, the performance of CNLCU appears larger variances, which should be further explained.
- This paper assumes that the training losses in L_t conform to a Markov process. This assumption may not be always true in reality. The position of W in parameter space depends on the starting points and search paths, but not merely the last positions. Some support evidences are better to be shown. Or, some statistical operations should be taken on the correlation of the W sequence during the training process.

summary_of_the_review: Although some minor issues are better to be further addressed, CNLCU is indeed novel and technically sound. The experimental results show the potential superior performance of CNLCU. Thereby, I rate this paper with marginally above the acceptance threshold.
review_title: null

Meta-review: The manuscript discusses weaknesses in previous sample selection criteria in learning with noisy labels, and proposes a new selection criterion by incorporating the uncertainty of losses, together with theoretical justification. To select samples, the manuscript uses the lower bounds of the confidence intervals derived from concentration inequalities instead of using point estimation of losses. By incorporating uncertainty about large-loss samples, the method is able to distinguish: truly mislabeled samples, or clean yet underrepresented samples that are less frequently selected or learned by the model so far. Experiments are performed on four benchmark datasets (MNIST, F-MNIST, CIFAR-10, CIFAR-100) and use a diverse set of possible noise functions. 

Reviewers agreed on several positive aspects of the manuscript, including:
1. This manuscript addresses weaknesses in previous sample selection methods and potentially impacts various applications (e.g., worst-group generalization and fairness);
2. The technical steps are clearly explained with theoretical justification;
3. Many datasets and comparison methods used and thus the proposed approach is also validated empirically.

Reviewers also highlighted several major concerns, including:
1. The space complexity of the proposed method; to implement the proposed method, it seems that naively one will need to keep track of the history of losses of every sample in the training set;
2. The validity of Markov process assumption on the training losses when momentum is used in optimization. Also, the position of the parameter in parameter space depends on the starting points and search paths, but not merely the last positions.
3. The experiments mostly are designed with relatively low noise (20% and 40%);
4. The evaluation matric as well as the analysis should be diverse. The performance of the proposed approach appears to have larger variances, which should be further explained.

Many of the major concerns have been addressed during the rebuttal including: experiments with 50%, 60%, and 70% symmetric noise, extension to NLP data by showing results on the NEWS dataset, and further discussion on the space complexity and Markov process assumption.
Decision: Accept (Poster)