Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 4: Ok but not good enough - rejection
review_content: The paper considers the problem of estimating instance-independent label noise. More formally, it is assumed that the true labels for any data point are modified based on a noise transition matrix, and the goal is to estimate this noise transition matrix. The paper proposed an information-theoretic approach for this task, the key idea behind which is to estimate if a particular dataset has maximum entropy with respect to the labels. This estimation problem is solved using a recent discovery that the training dynamics of a neural network can be used to infer the presence of label noise.

Strengths:

1. The problem of learning with instance-independent noise has received some attention from the community and could be of interest. 
2. The proposed information-theoretic framework is conceptually interesting, and also comes with some theoretical guarantees.

Weaknesses:

1. The paper does not show that the approach leads to better downstream neural networks in the presence of instance-independent noise. The current experiments only show that the approach can find better transition matrices Q in terms of KL divergence. Since this is simple, synthetic noise model this is not very convincing. The paper needs a much more thorough experimental evaluation to demonstrate that the approach can improve the state-of-the-art on downstream learning tasks. The experiments are also only done on CIFAR-10, whereas most of the related work considers at least a few other datasets.
2. I also think that the setting needs to be motivated better. As can be seen in Table 1 and 2, MPEIA and GLC which need only 0.5% clean samples can actually do better than the proposed approach, which is this such a hard requirement? I also don’t find the ours-2 and ours-3 results convincing and a bit misleading, since we should then also consider combinations of other models.

Overall, I am not in favor of acceptance because of the experimental evaluation not being convincing. However, the proposed algorithm is interesting and has potential, if the authors can build more on it in the future then it should make for a good paper.

Other points: 
1. The discussion of “anchor points” and “mixture models” is quite unclear in the introduction.
2. I found the discussion and notation in Section 2.3 to be a bit convoluted. I think there should be a much clearer description of the approach.

--------Updates after author response--------

I thank the authors for the detailed response and appreciate the additional experiment. However, I still believe that evaluation on downstream tasks is essential to demonstrate the superiority of the approach, and I unfortunately do not agree with the authors that it implicit that the approach will yield better downstream networks. Therefore, I cannot raise my score, but would encourage additional experimentation. 
review_title: Lacking in experimental evaluation

final_score: rating: 5: Marginally below acceptance threshold
review_content: ***	

Summary:

The paper aims to develop an information-theoretic framework for learning the underlying model from data with instance-independent label noises. It first formalizes the problem and relevant definitions with information measures, such as conditional entropy and conditional KL divergence, then argues that if the underlying model is well-separated, the proposed algorithm will be consistent in learning the noise-labeling matrix. At the heart of the algorithm is a discriminator being able to measure the labelings' noise level. A class of discriminators based on 'local intrinsic dimension (LID)' is then provided and evaluated empirically. The resulting algorithm performs well on the tested instances compared to existing ones. 


***	

Reasons for score: 

 
Overall, I would like to give a weak reject. I like the idea of understanding and analyzing data models with label-independent noises through the lens of information theory. It is even better as such an idea leads to an improvement in practical applications. However, the paper is unsatisfiable in terms of writing and theoretical contribution. The authors may refer to the 'cons' below.


***	

Pros: 

 
1. The problem of learning models of instance-independent label noise is, by itself, an important and practical problem.

2. The proposed framework and algorithm (Algorithm 1) are both general/flexible and work without additional structure assumptions on the noise transition matrix. Besides, the information-theoretic formulation is also natural for the following reason. A trained discriminator is used to infer how different the noise matrix is from a completely random matrix, namely, a matrix with all rows being uniform. By inserting user-designed noise and training multiple discriminators, one effectively probes the underlying matrix and, in the limit, obtains sufficient information for its recovery.

3. This paper provides a useful estimator that performs well in practical experiments. In particular, it is shown that the proposed algorithm can be combined with prior ones to improve their efficiency/accuracy. 

 
***	

Cons: 
 
1. I am concerned about the significance of the theoretical results. The major contribution is Theorem 2.5 on page 6, which states that the proposed algorithm is consistent in estimating the noise matrix. 

- It might be better to make the main theorem self-contained. Currently, the major assumptions appear at the beginning of Algorithm 1. 

- The paper suggests that its results hold under "mild" conditions on the discriminator. I believe this requires further clarification, especially on why these conditions are mild, given the existing literature. For example, the algorithm relies on the existence of a separable random function $g$ on $\mathfrak U[\mathcal D]$. I wonder if this condition can be checked in practice only by utilizing the data OR whether there is a practical scenario where this condition is automatically satisfied. Besides, how strong is this condition? Is such a condition satisfied by the random function $g_{\text{LID}}$ used in the experiments? 

- The theoretical results show that the estimator is consistent if (nearly) all parameters tend to infinity, which doesn't seem practical. I don't see how this theoretical insight can guide the design of real estimators. 

 
2. I am also concerned about the writing of the paper due to the following reasons. 

- The notation is somewhat heavy, and I feel that more than half of the paper is introducing new definitions. Besides, there are few issues with those definitions/notation: 1) Notation introduced but merely used, e.g., the KL divergence between two derived DILNs on page 4; 2) Quantities undefined or defined after being used, e.g., in Definition 2.4 of a trained $n$-fold estimator,  what is $\Phi^+$?  For another example, what is $E_{i,j}'$, referred to as "error" in the definition of $Q_{i,j}'$ on page 4? 3) For information-theoretical quantities, it might be better also (or just) presenting their standard forms, e.g., the key definitions $H(\mathcal D)$ and $\text{KL}(\mathcal D'\vert\\!\vert \mathcal D'')$ in Section 2.1 are basically $H(Y\vert Z)$ and $\text{KL}(Y'\vert Z\vert\\!\vert Y''\vert Z)$. Also, what is the novelty here then? 

- I would suggest adding more explanations about the theorem and algorithm. The paper currently spends lots of effort defining new quantities but much less in providing insights and intuitions about the algorithm and its guarantee. For example, after the heavy notation on page 5, the main algorithm is directly presented at the top of page 6, followed by its guarantee, Theorem 2.5. As the algorithm is nontrivial, it would be helpful to explain the logic and rationality. In particular, a critical definition, valid $\alpha$-sequence, is postponed to the appendix, and I don't see why. Similar comments apply to the main theorem, as I mentioned in the last major point.  

I hope that the authors can address (at least some of) the concerns/questions/suggestions stated above. Thanks.

 
***	
review_title: The theoretical contribution is not so clear/significant, but the experimental results seem reasonable.

final_score: rating: 5: Marginally below acceptance threshold
review_content: This paper studies the problem of learning the noise model in a classification problem. The basic setup is that
X -> Z -> Y
is a Markov chain, where X are the features/input to the classifier, Z is the true label, and Y is the observed noisy label. The term "instance-independent label noise" refers to the fact that the law of Y | Z doesn't depend on X. The goal is to learn the noise model, i.e. the transition kernel Z -> Y. 

I feel the writing clarity could be improved in places. The definition of DILN in the main text is confusing (does it include the noise model or not?) although the presentation in Appendix A is somewhat clearer. A lot of notation is introduced and it makes it difficult to read the main text -- for example the algorithm description depends on a "valid alpha-sequence" as input and this is not defined until the appendix. An informal definition in main text would be helpful.

As far as I understood the theorem statement, it says that if the algorithm is given as input a 'separable map' g then it is possible to learn the noise model, and the main difficulty to apply it is to construct an efficient separable map (which in practice, they attempt with decision trees + LID scores). It would be nice if the authors discuss the conditions under which such a separable map is guaranteed to exist. (And ideally, under which we could hope to find such a map.)

Overall, I think there may be some interesting ideas in this paper, but I did not find the results to be very strong support for the claims made (see other notes below regarding the experiments). I also think the paper could benefit from clearer writing. So right now, I would tend towards rejection.

Other notes:
* The beginning of the paper suggests that the key contribution is to learn the noise model without needing to "accurately" learn a classifier X -> Z. However, if I understand right the final algorithm based off of "Local Intrinsic Dimensionality" (LID) scores requires training a 12-layer CNN to predict the label from X so it seems to be somewhat weak support for this claim? 

* I found the definition of f_{matrix} confusing. If U[D] indicates we throw away the information about the noise model, then what does the map f_{matrix} : D' |-> Q_{D'} mean, is Q_{D'} is still determined from D'? Is this a 'random map'?
review_title: Writing could be improved

Meta-review: This paper studies the following model: The input to our classifier is the instance X which determines the label Z and we observe a noisy version of this label Y. The key assumption is that the label noise is independent of the instance, and the goal is to learn the channel from Z to Y. The main motivation is that generally algorithms that can handle instance-independent noise need to know the noise model. Thus the main contribution of this paper is to decouple the problem of learning the noise channel and the problem of learning a high-accuracy classifier. In particular they inject their own label noise and design a discriminator to test if the noise on the labels has maximum entropy. They show that their method is statistically consistent. Finally they complement this with synthetic experiments on CIFAR to show that their algorithm works. 

While the reviewers all found the ideas promising, they brought up a few deficiencies in this work which they hope could be improved in later versions. First, the writing is at times unclear and imprecise. For example, there are many places that could benefit from further discussion, particularly in terms of justifying why the assumptions are "mild" or not. Second, the experiments would be more compelling if there were an application where learning the noise model actually led to improved performance on some downstream application. Third, the approach crucially relies on having a separable map, which seems like a rather strong assumption. 
Decision: Reject