We establish a new theoretical framework for learning under multi-class, instance-dependent label noise. This framework casts learning with label noise as a form of domain adaptation, in particular, domain adaptation under posterior drift. We introduce the concept of \emph{relative signal strength} (RSS), a pointwise measure that quantifies the transferability from noisy to clean posterior. Using RSS, we establish nearly matching upper and lower bounds on the excess risk. Our theoretical findings support the simple \emph{Noise Ignorant Empirical Risk Minimization (NI-ERM)} principle, which minimizes empirical risk while ignoring label noise. Finally, we translate this theoretical insight into practice: by using NI-ERM to fit a linear classifier on top of a self-supervised feature extractor, we achieve state-of-the-art performance on the CIFAR-N data challenge.
Paper
Similar papers
Peer review
Summary
This paper presents a theoretical framework for learning under multi-class, instance-dependent label noise. It introduces the novel concept of Relative Signal Strength (RSS) to measure the impact of noise and uses it to derive upper and lower bounds on excess risk. Notably, it proves the minimax optimality of Noise Ignorant Empirical Risk Minimization (NI-ERM) and provides conditions for immunity to label noise. Bridging theory and practice, the paper proposes a two-step 'feature extraction + NI-ERM' approach, achieving state-of-the-art performance on the CIFAR-N dataset.
Strengths
1. Theoretical Depth: This paper introduces the novel concept of Relative Signal Strength (RSS) to quantify the impact of noise in label learning. Using RSS, the authors mathematically derive precise upper and lower bounds for excess risk. 2. Combination of Theory and Practicality: The research seamlessly bridges theory and practice by developing a two-step 'feature extraction + NI-ERM' approach based on their theoretical analysis. This method achieves high performance using simple linear classifiers instead of complex deep learning models, validating the theoretical predictions about the optimality of NI-ERM in practical applications. This successful translation of theoretical insights into effective practical methods is a significant strength of the paper. 3. Surprising Results: One of the most striking aspects of this work is the mathematical proof that simple Noise Ignorant Empirical Risk Minimization (NI-ERM) is minimax optimal. The authors theoretically guarantee accurate learning even under high noise levels, such as up to 90% in 10-class problems. These surprising findings challenge conventional wisdom about the necessity of complex noise handling techniques and achieve state-of-the-art performance with a remarkably simple approach. 4. Experimental Validation: This paper provides experimental validation of its theoretical claims by achieving top performance on real-world noisy datasets like CIFAR-10N and CIFAR-100N. They demonstrate that performance changes with increasing noise levels align closely with their theoretical predictions, providing empirical support for their theoretical framework. 5. Practicality: The proposed method achieves high performance without relying on data augmentation or complex hyperparameter tuning
Weaknesses
1. Insufficient Introduction: The introduction lacks a comprehensive overview of the paper's content and contributions. A more detailed exposition of the overall approach and key findings would better prepare readers and emphasize the paper's significance. This could include a clearer roadmap of the theoretical and practical aspects of the work. 2. Validity of Relative Signal Strength (RSS) Definition: The definition of RSS is not intuitive and lacks a sufficient explanation of how it represents the signal content of the noisy distribution relative to the clean distribution. While examples are provided, they primarily demonstrate RSS calculation rather than explaining the fundamental reasoning behind its definition. Since all theoretical results in the paper are based on the RSS definition, it is crucial to establish whether RSS accurately represents the degree to which the noisy distribution contains signal compared to the clean distribution. A more thorough justification and explanation would strengthen the paper's theoretical foundation. I will raise a question about the definition of RSS in the question section to seek further clarification on this point. 3. Experimental Validity Concerns: The two-step method employs pre-trained feature extractors. While this demonstrates the effectiveness of NI-ERM, it may not provide a fair comparison with other methods. To more convincingly demonstrate the superiority of NI-ERM, the paper could: a) Compare NI-ERM using feature extractors from models trained with other SOTA noisy label methods. b) Apply SOTA methods to the same high-quality feature extractors used for NI-ERM, training only the final linear layer for a fairer comparison. These additional experiments would provide a more robust validation of the NI-ERM approach in practical scenarios.
Questions
1. Definition of RSS: I am curious about how RSS measures certainty about the label. The definition of RSS does not seem intuitive. Generally, in deep learning, KL divergence is used to measure the difference between two probability distributions. The definition of RSS shows a different tendency compared to KL divergence. For example, let's consider three probability vectors: p1 = [0.05, 0.7, 0.25], p2 = [0.25, 0.7, 0.05], and p3 = [0.1, 0.6, 0.3]. The RSS between p1 and p2 is 1.44, and the RSS between p1 and p3 is 0.67. If we assume p1 is the clean distribution, it can be interpreted that p2 contains more label information. However, the KL divergence between p1 and p2 is 1.96, and between p1 and p3 is 1.05, indicating that p1 and p3 are closer in terms of distribution. Is there a justification for claiming that p2 contains more label information despite having a higher KL divergence? 2. Gap between Theory and Practice: While the paper bridges the gap between theory and experiments by using pretrained feature extractors, as mentioned in line 254, generally training the feature extractor with NI-ERM does not perform well. This differs from the theory presented in the paper. What do you think is the reason for this discrepancy?
Rating
7
Confidence
3
Soundness
3
Presentation
4
Contribution
3
Limitations
Limited Application to Classification Problems: While noisy label problems exist in various tasks, the theoretical analysis and experimental validation in this paper focus solely on classification problems, particularly image classification tasks.
Main Concerns Addressed by Authors' Response
Thank you for the author's response and new experiments. The author's explanation has alleviated many of my concerns. I now understand why the authors set the RSS in that way and how you tried to capture the signal of the clean posterior differently from KL divergence. While I'm still not fully convinced that RSS is the best definition for representing how much signal from the clean distribution is included, I believe it is sufficient for the proposed theories to have meaningful implications. I will raise my score to accept.
Thank you for your response. Your review is very beneficial and definitely helps the paper to be better framed. We really appreciate that. Thanks.
Summary
The work provides a new insight on how to deal with instance-dependent label noise under the context of multi-class classification problem. Under certain conditions, they prove that training a classifier as if there is no noisy labels is the best course of action. This idea is presented in details supported by several theorems with finite sample analysis as well as by several experiments on synthetic and a real dataset (CIFAR-10N).
Strengths
I enjoy reading this paper. The work presents a surprisingly simple idea to deal with noisy labels, especially instance-dependent noise, and show that it is the optimal learning strategy under some conditions. - The authors introduce the Relative Signal Strength (RSS) to quantify how much noisy label distribution can reveal about the clean label distribution. - Based on this measure, the authors suggest a class of noisy label learning problems that can be guaranteed to be solvable (Theorem 2) by just ignoring the existence of noisy labels. This is somewhat still intuitive because RSS is positive and the excessive risk is measured based on 0-1 loss. - They also present a min-max analysis to show that for the same class of problems, the above learning strategy achieves an optimal rate. This is really a surprising and intriguing result. - Lastly, they show how applicable this class of problems can be in practice (Theorem 4, 5): the label noise probability vector should have the same argmax as the clean probability vector.
Weaknesses
- The key condition for ignoring the existence of noisy labels to work is to have $\mathcal{A}_0 = \mathcal{X}$ (or $\mathcal{A}_0$ covers most of $\mathcal{X}$), which in turns requires $\text{argmax } \widetilde{\eta}(x) = \text{argmax } \eta(x)$. This condition would be violated if certain classes are tricky and easy to mistaken one as another, for example, labeling leopard, lion, cheetah, tiger. Therefore, the condition that \kappa > 0 might be restrictive in this regard. On the other hand, it would be intuitively feasible to still learn a classifier under this type of noise as long as one mistakes a class with another class in a consistent way. In that case, having permutation ambiguity is inevitable, but it is not a very detrimental as the cost of post-processing to disambiguating permutation is relatively cheap. - The experiment section is limited: + How is performance of the proposal compared to baselines under various noise level? + More baselines should be included, such as BLTM[1], MEIDTM[2], MaxMIG[3]. [1] Yang, Shuo, et al. "Estimating instance-dependent bayes-label transition matrix using a deep neural network." International Conference on Machine Learning. PMLR, 2022. [2] Cheng, De, et al. "Instance-dependent label-noise learning with manifold-regularized transition matrix estimation." Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition. 2022. [3] Cao, Peng, et al. "Max-mig: an information theoretic approach for joint learning from crowds." arXiv preprint arXiv:1905.13436 (2019).
Questions
- Does the analysis depend on any particular loss used during training?
Rating
8
Confidence
3
Soundness
3
Presentation
3
Contribution
3
Limitations
yes
Summary
The author proposes a Label Noise Learning (LNL) method that assumes a noise transition matrix. The author introduces the concept of Relative Signal Strength (RSS), which is calculated as the ratio of the signal difference between the true prediction and the prediction under label noise. The author demonstrates that the set satisfying the condition of RSS being greater than zero is noise immune. Additionally, the author provides a method to define a noise transition matrix that upholds this condition.
Strengths
The author presents a novel perspective for solving the LNL problem. The interpretations of RSS proposed by the author are sufficiently insightful for peers in the LNL field. Moreover, the author's method is well-suited for use with pretrained feature extractors and aligns with current trends in the AI field.
Weaknesses
There are two major concerns. The first is the low reproducibility. Despite the robust interpretation of the proposed method, the lack of a specific algorithm makes it challenging to conceptualize a clear learning approach. Specifically, it would be beneficial to provide examples of e(x) in Theorem 5, as well as pseudocode for feature extraction and the derivation of the transition matrix. Secondly, it is challenging to interpret the advantages of the proposed method from the experiments. (1) The author conducted experiments solely on light synthetic data, making it difficult to ascertain the effectiveness of the theoretically-based method in practical noise scenarios. (2) The author employs a highly trained pretrained model, which introduces an unfair factor in comparisons with other methods. Notably, there is experimental evidence suggesting that self-supervised pre-training can enhance the performance of existing methods (https://arxiv.org/pdf/2103.13646v2). I recommend including the author's method applied to various pretrained models in Table 1, or adding the use of pretrained models for existing methods to provide a fair comparison.
Questions
I have given high marks to the author's novel perspective and the reasonable interpretations and proof methods presented. Despite the proposed method's low reproducibility and unproven practical performance, it has the potential to positively influence other research in the LNL field. Therefore, I have assigned a rating of "weak accept". If the author provides more detailed treatment of the proposed method and richer empirical interpretations, I believe the paper would be strong enough for acceptance.
Rating
5
Confidence
2
Soundness
3
Presentation
4
Contribution
3
Limitations
-
Thank you for your reply. As author continues to assert, one of the undeniable contributions of the author is demonstrating that LP is a simple yet competitive method using the RSS metric. However, the limited applicability of the proposed method may provide little assistance to colleagues researching LNL. Therefore, my concern has been partially addressed, and I will maintain my original evaluation: borderline accept.
Summary
In this work, the authors use a new theoretical framework for analyzing learning under label noise in multi-class classification. The proposed framework is based on relative signal strength (RSS), which measures noisiness data points in the training sets. Based on RSS, the authors propose new upper and lower bounds on excess risk and identify when the classifier learned from label noise is consistent. Based on the theoretical results, a new simple learning framework, called Noise Ignorant Empirical Risk Minimisation (NI-ERM), is proposed, which basically performs standard ERM learning on nosy data. To practically apply NI-ERM, the authors proposed a simple framework of learning linear classifiers on top of a feature extractor trained in an unsupervised/semi-supervised way. The effectiveness of this approach is validated in a few experiments where the method was tested on popular benchmarks under different noise distributions.
Strengths
- The paper is sound and, despite being very theoretical, is easy to read, as authors step by step explain the thinking process. - Newly obtained bounds are indeed simple in form. - The effectiveness of the new two-step NI-ERM is confirmed by a few empirical empirical experiments.
Weaknesses
- It seems to me, that the analysis conducted under the Relative Signal Strength framework does not provide a lot of new surprising insights, the conclusions more or less confirm findings from previous works. - Training feature extractors in an unsupervised/semi-supervised way might be more difficult in the case of some more specialized applications than, for example, general image classification used in the experiments. - The considered analysis and proposed approach is limited to classifier accuracy, while in many applications other task losses/utilities are often considered.
Questions
Not really, I will be happy to read the authors comments on my points from the weakness section.
Rating
6
Confidence
3
Soundness
3
Presentation
3
Contribution
3
Limitations
Limitations were discussed. I see no negative social impact of this work.
Summary
This paper investigates multiclass classification under label noise, specifically instance-dependent label noise in which the noise can depend on the features as well (a.k.a. local noise). A minimax result is derived that lower-bounds the misclassification probability of a classifier. The paper finds a good empirical practice to be the procedure of training a linear classifier on some separately-learned features.
Strengths
The paper's analysis is correct, and the results relative to the CIFAR-N leaderboard are impressive. (I wish I was able to see the leaderboard, however; several browsers failed to load more than a blank screen.) The message of the paper -- in the presence of unknown noise, learning final-layer classifiers is more robust than learning a classifier from scratch -- is an old one, known empirically to be worth using. The paper's message is clear, and it is overall clearly written.
Weaknesses
The problem addressed in this paper is very common, and people use many heuristic practical strategies it. The paper states that there are theoretical contributions leading to practical consequences. These practical consequences (recommending ignoring the noise) are not new, and the theory lends no understanding on when this might succeed and fail. The practical consequences are to encourage linear probing (learning a linear classifier on top of a frozen feature layer) on features learned separately from possibly different data. This is possibly the most commonly used idea in practice, including in many situations where it's assumed that there is no noise by default, even when there is. This is not benchmarked thoroughly on different noise distributions. Many other papers in similar areas use Dirichlet distributions to precisely simulate different non-uniform noise, which would be a more thorough synthetic benchmark (e.g. Garg et al. "A Unified View of Label Shift Estimation"). On the real-data side, I would like to see different fine-tuning strategies also compared. The theory is quite brittle in a couple of ways. It only takes into account the gap to the top class probability, making some of the definitions like A_0 brittle as well; for many classes of noise distributions A_0 could be quite small to empty. The minimax lower bound construction again uses uniform label noise, meaning that it does not adapt to the actual structure of the instance-dependent label noise; the results showing NI-ERM matching this bound are therefore fairly weak. Presentation-wise, the paper introduces many new terms without apparent reason; these are used correctly, but their combined effect is not to simplify and may be misleading as to the results. An example is "immunity" - it is easy to construct class-conditional noise distributions which would break the minimax results, and they tend to be non-uniform in interesting ways.
Questions
- Why not simulate with instance-dependent label noise of some kind (e.g. simulate cluster-dependent label noise) instead of uniform label noise? Uniform label noise is easy to combat - simply being oblivious works. - The main message of the paper is that linear probing deals with label noise better than full training / fine-tuning of the network. Are the authors aware of the two-step strategy of linear probing then fine-tuning the whole network, as popularized recently as a general strategy for encouraging robustness to distribution shift? How does this do? (ref. Kumar et al. '22, "Fine-Tuning can Distort Pretrained Features and Underperform Out-of-Distribution") - How about estimating label shift and benchmarking similar methods, which all implicitly rely on the adjustments to the calibration of a classifier? The Garg et al. reference given above, and methods therein, are SOTA here, and I would think that if there is significant class-conditional noise in \tilde{Y}, then estimating this would be key and perform better than NI-ERM.
Rating
4
Confidence
4
Soundness
3
Presentation
3
Contribution
2
Limitations
Yes
Good rebuttal, concerns remain
Thanks to the authors for their detailed and precise comments. As I write below, I agree with the authors on many points (and have changed my review accordingly), but would leave much of my initial assessment intact. In my initial review, I mis-spoke on a couple of points, which I will clarify. The lower bound construction does indeed use instance-dependent label noise on a discrete space, not uniform label noise. Label shift is indeed a different problem, and I do not mean to suggest this is the same setting; but the simulations/benchmarking of the papers in that area comes far closer to practical relevance here. Thanks to the authors for their experiments in the rebuttal, including on LP-FT. The NI-ERM method itself is oblivious of the existence of any noise, and there is no new algorithm or loss function. Yet it is standard practice because it seems to sometimes work. So the paper's contribution is looking to justify where the standard procedure does and doesn't work - in which label noise situations would it be fine to use, and where should one look to do something else - where is ignorance bliss? This is why the brittleness of the theory matters in this context. I am very familiar with the standard label noise literature (Tsybakov, Massart, et al.) and the authors are correct about the theory here also being in that spirit. However, that theory is most robust/successful (and originally developed) for binary classification, in which the problem reduces to one where the authors' RSS is a good pointwise signal-to-noise measure. As K > 2, the min over the K classes in the RSS starts to eliminate more and more information, and lower the RSS even when learning would appear to be intuitively possible. For e.g. Imagenet (K=1000) or many similar-scale problems, the classes themselves show significant structure, with some being easily confusable for each other, and others less so; the sets A_{\kappa} could be small or even null, in my practical opinion. Clearly this will not nontrivially happen for K = 2, and tends to happen less for low K. Ideally a reasonable \kappa (to get a reasonable \epsilon) should scale nicely with K, which would make the upper bounds quite relevant. I don't have good intuition about whether this applies for noise distributions in the wild. (It would be great to see if this is correct by computing A_{\kappa} for a real dataset, which can be done approximately with sampling. If A_{kappa} is nontrivial for reasonable \kappa; the inverse dependence of the bounds on \kappa means that we do need some statistically nontrivial gap). This of course affects the model class over which the minimax result is proved. The result is strong (like any minimax result is) *over its posterior drift model class* - but \Pi may be nearly empty. The lower bound construction is certainly correct, but its tightness, and the logic of the proof, again rely on the model class \Pi. All this means I am not really able to answer the question, as a practical matter, of when ignorance is bliss. The practical relevance of the theory here appears limited for higher K (though it could be very relevant for low K). There are of course many theories of learning under label noise that extend beyond the binary setting, but those often lead to a new algorithm, loss function, etc. Since this is not true here, the "practically interpretable" aspects of the theory are important in assessing the contribution.
We thank reviewer for the detailed response. ## Contribution of the paper > ... so the paper's contribution is looking to justify where the [Noise ignorant] procedure does and does not work. Actually, we feel that this is not our main focus (although the exploration of section 5 is concerned with this, e.g., Thm 4). The main theoretical focus of the paper is **what is the fundamental limit (e.g., minimax risk) in learning with label noise**. In other words, if we **do not assume any further structure on the data**, what can we hope to get, and what works for this. It is in this regard that Section 4 (and the preceding definitions of Section 3) are strong: they identify that the minimax risk is captured directly by the RSS, and that the RSS is the 'right' object to think about when considering label noise. Note that the RSS is a novel way of characterising the noisy labels problem. The framework not only admits tight bounds, suggesting that at least in a minimax sense RSS is the natural object to study, it also is flexible enough to capture structure (of label noise), one example is demonstrated through Thm 3. ## What if number of classes $K$ is big? > As $K > 2$, the min over the K classes in the RSS starts to eliminate more and more information, and lower the RSS even when learning would appear to be intuitively possible. For e.g. Imagenet ($K=1000$) or many similar-scale problems, the classes themselves show significant structure, with some being easily confusable for each other, and others less so... Ideally a reasonable $\kappa$ (to get a reasonable $\epsilon$) should scale nicely with K When $K$ becomes large, even the standard learning scenario becomes provably hard (e.g., literature on extreme classification). We imagine the same also holds for label noise setup. As for a solution for this, just as you have suggested, is to explore 'structure', formally speaking, assume **sparsity**: both $\eta, \widetilde{\eta}$ are $C$-sparse, which corresponds to the scenario you described as "...some (classes) being easily confusable for each other, and others less so". Now, let us examine the concept of RSS again: $$ M(x; \eta, \widetilde{\eta}) = \min_{j \in \\{1, 2, \dots, K\\} } \frac{ \max_i [\widetilde{\eta}(x)]_i - [\widetilde{\eta}(x)]_j }{ \max_i [\eta(x)]_i - [\eta(x)]_j }, $$ For the "unrelated classes" $j$, where both $[\widetilde{\eta}(x)]_j$ and $[\eta(x)]_j$ are zero, $$ \frac{ \max_i [\widetilde{\eta}(x)]_i - [\widetilde{\eta}(x)]_j }{ \max_i [\eta(x)]_i - [\eta(x)]_j } = \frac{ \max_i [\widetilde{\eta}(x)]_i }{ \max_i [\eta(x)]_i }, $$ thus it will not deflate the RSS. Therefore, the minimum of $j$ over $\\{1, 2, \dots K\\}$ reduces to the set containing non-zero indices of $\eta$ and $\widetilde{\eta}$, which contains at most $2C$ elements (from the $C$-sparse assumption above). To conclude, with an additional sparisty assumption which takes the noise structure into account, our notion of RSS "scales well with $K$". ## $A_0$ being null? > For e.g. Imagenet (K=1000) ... with some (classes) being easily confusable for each other, and others less so; the sets $A_{\kappa}$ could be small or even null, in my practical opinion. In order to claim "$A_{\kappa}$ could be small or even null", several things need to be taken into account: - value of $\kappa$ - overall hardness of the classification task: $\eta(x)$ - quality of labeller: $\widetilde{\eta}(x)$ For an un-trained labeler (e.g., common people like you and us), images of some classes are "easily confusable", thus the resulting $A_0$ can be quite small. For the "ImageNet labeler(s)" who have gone through detailed instruction and careful quality control, the (final) label quality is much better, thus $A_0$ shall be quite big. For a fixed unlabeled image dataset, and a fixed value of $\kappa$, how big $A_{\kappa}$ depends on (human) label quality, which shall be analyzed case-by-case. Towards this end, we thank you for bringing up the task of "calculating the RSS level of real-world noisy dataset". We could start from the CIFAR-N dataset. This is a big project, beyond the scope of the current paper, but would benefit from the framework constructed in this paper. --- To conclude, the main point of the paper is not to "justify when NI-ERM does and does not work", but to develop a theoretical understanding of the general label noise problem (through the new concept of RSS). We thank you for bringing up the question on how the theoretical concept can be used to explain "label noise in the wild", we believe it is important and worth studying. Thank you again.
Dear area chair, Up to now we have not received any comments from reviewers. Could you please ask the reviewers to engage with us? Thanks.
We thank all reviewers for the feedback. The discussion is very helpful.
Thank you for the detailed review. I realized that I had misunderstood the paper, and through the rebuttal and the opinions of other reviewers, I now understand that the author was justifying the use of the linear probing approach. Thanks to this, my concerns about low reproducibility have been alleviated, but I still have other remaining concerns. As highlighted in the global rebuttal, the power of a well-trained feature extractor cannot be overlooked. I have an additional question at this point. Did the other methods also involve training only the classifier? I am curious whether the author’s theoretical interpretation is empirically valid: if the performance of other methods remains high with the well-trained feature extractor being frozen, the practical significance of the author’s findings would be greatly diminished.
I have lowered my confidence level due to the realization of my misunderstanding.
Thank you for your reply. > I now understand that the author was justifying the use of the linear probing approach. Practically, yes. Motivated by the theory, we are demonstrating (Noise-Ignorant) linear probing itself as a promising approach for label noise. > Did the other methods also involve training only the classifier? I am curious whether the author’s theoretical interpretation is empirically valid: if the performance of other methods remains high with the well-trained feature extractor being frozen, the practical significance of the author’s findings would be greatly diminished. As for Table 2 in the attached pdf file to the global rebuttal, yes, the feature extractor is frozen. The simple method performs as good as (and sometimes better than) other more complicated "robust" methods, which shall be good news for practitioners. Thanks.
Decision
Accept (poster)