Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: Comments:
Label noise is very frequently in many real world applications. However, the noise can be with different distributions. If we build the learning model under a certain distribution, it is difficult to capture the discriminative information. In this paper, without assuming that the noise is a certain distribution, the proposed method can handle the general noise, and it mainly target a new family of feature-dependent label noise, which is much more general than commonly used i.i.d. label noise and encompasses a broad spectrum of noise patterns. The experimental results show that the proposed method is promising. Meanwhile, the theoretical analysis of the proposed method is well inferred.

Strong points:
[1] The theoretical foundation of the proposed method is strong. 
[2] The experimental results of the proposed method are promising.
Weak points:
[1] Some details about the experiments are not clear, such as the experimental settings of the compared methods.
[2] It is better to show the connection between the polynomial margin diminishing noise and the other noises.

Accept reason:
[1] The paper has shown a promising performance than several state-of-the-art methods. The noise assumption is more general than the traditional types. Hence, the paper may provide a novel way to deal with noise labels.

Feedbacks:
[1] I found that the step size \beta has an influence on the threshold \theta, and how to set it. It is necessary to show the details about \beta, which has directly influence on the results.
[2] The noise in the experiments is more than 30%. Whether the proposed method is suitable to the high-level noise. It is better to show the results without any noise.
[3] Since the polynomial margin diminishing noise is general, whether the polynomial margin diminishing noise can represent any noise functions in theoretical.
[4] The details of all the compared method may need to be provided.
review_title: This paper proposes a progressive label correction algorithm by correcting labels and refine the model iteratively.

final_score: rating: 8: Top 50% of accepted papers, clear accept
review_content: **Summary of paper**

The authors introduce a data-relabeling method that they claim is the first that both allows for data-dependent noise and is theoretically guaranteed to converge to an optimal model.

The authors introduce a novel family of label noise, called Polynomial Margin Diminishing (PMD), which defines a polynomially-decreasing upper bound on the label noise as the true label probability is above some threshold and as it approaches 1. Below the threshold (when the true label probability is closer to 0.5), the noise is unbounded.

The authors introduce an algorithm, "Progressive Label Correction", which iteratively flips the training labels of examples for which the model's confidence is above a threshold. The threshold decreases over time, so that only the most confident examples are flipped at first, and then the less-confident examples are flipped later.

The authors prove (Theorem 1) that under the assumption of PMD label noise distribution, as well as Assumption 1 concerning the flexibility of the hypothesis class and the continuity of the true label's conditional distribution, then their Progressive Label Correction algorithm asymptotically approaches a set of corrected labels that match the true (de-noised) labels with high probability.

The authors experimentally show that their algorithm consistently outperforms 5 alternatives on CIFAR-10 and CIFAR-100 datasets with various types of synthetic noise, both feature-dependent and hybrid feature-depedent/indepdendent. Finally, they show their algorithm outperforms 10 alternatives on a real-world dataset (Clothing1M) with unknown noise.

**Conclusions**

Quality: Overall I like this paper. It's a pretty simple algorithm to implement, and it seems to be quite effective in practice and have nice theoretical properties.

Clarity: The paper is structured very well. It is easy to follow the narrative and high-level ideas. There are a few minor typos (see below for some examples). The theory is relatively easy to follow.

Originality: I'm not familiar with the related work, but this appears to be original/novel from my limited perspective.

Significance: This algorithm can potentially be used to improve test accuracy on any supervised learning task, so the intended audience is quite large. The improvement on both synthetic and real data seems quite large. It's hard to tell whether the results were cherry-picked at all, but they are impressive.

**Minor comments**

Figre 1 caption has a typo: "Red dots are the data that remain incorrect. that remain un-corrected and are closer to the
decision boundary."

In Section 2.1, "illustrate the upperbound (red curve)", but the figure actually shows an orange curve (not red) for the upper bound.

Figure 2 caption, "closed to 0 or 1" should be "close to 0 or 1". Also, "a equal probability" should be "an equal probability".
review_title: Simple and effective label de-noising algorithm

final_score: rating: 7: Good paper, accept
review_content: The work appears to original, and it deals with an important topic (ie, how to deal with noisy labels). The paper is well written and reasonably easy to follow. Figure 1 is extremely helpful in providing an intuitive explanation that helps understanding the rest of the paper.   

Even though the empirical validation is reasonably thorough for a paper that also includes a theoretical analysis of the novel approach, it is here that the authors could improve the paper the most. The main weakness of this section is that even though the results on the synthetic datasets are strong, the ones on the Clothing1M domain are significantly less so, with two competing approaches (PENCIL  & MLTN) within 0.53% - 0.55% from the PCL result. Ideally, the paper should include another 2-3 real-world domains in this evaluation. At the very least, they could add to the evaluation the CUB-200 dataset from [Yi & Wu, 2019], on which PENCIL was evaluated for robustness on less noisy data.  Adding two more synthetic domains such as MNIST and ModelNet40, as done in [Zheng et al, 2020], is another possibility - but far less appealing.   
review_title: The authors introduce an iterative approach to learning from data with noisy labels under realistic circumstances (rather than iid assumptions).

final_score: rating: 8: Top 50% of accepted papers, clear accept
review_content: The paper presents a learning method for the scenario of feature dependent label noise. A framework where label noise diminishes away from the decision boundary is established and a relabeling strategy based on this by relabeling highly confident points is proposed.  The method is a straight-forward adaptive method which the authors both theoretically and empirically explore in detail.

# Pros

- The approach is simple and easy to implement on top of existing methods
- The authors support their simple method with some very nice theoretical results
- Good empirical evaluation showing competitive performance to other methods
- The paper is clearly written and easy to read
- Citations place the work well among existing literature

# Cons

- The authors mention Menon et al. in their "related works" section, but dismiss it immediately as "...it does not recalibrate individual data based on their contexts, and thus are not as effective as other deep-learning -based methods in practice." A citation here is needed showing this point, or further experiments.
- The related works section is very short and is essentially a list of other approaches. A more thorough discussion would help readers.
- A selection of baseline methods are chosen for comparison to the proposed approach in the empirical evaluation, but the particular choices aren't discussed in any detail. Some of the methods were mentioned in the related works section, but some are not (why not?), and neither section explains some of the choices.
review_title: A good practical method and theoretical contribution for learning from feature dependent label noise

Meta-review: This paper studies the problem of learning from data that have been corrupted by label noise. The authors define a natural data-dependent noise condition, that allows the noise rate to be large close to the decision boundary, and provide a simple iterative method that eventually converges to the Bayes optimal classifier. The method is evaluated on both synthetic a real datasets. There was a consensus among the reviewers that this is an interesting contribution and I propose acceptance.
Decision: Accept (Spotlight)