Label Noise: Ignorance Is Bliss

Authors: yilun  zhu
jianxin  zhang
aditya  gangrade
clayton  scott
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-15 01:25:54

Abstract: 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.

Main paper: 
 introduction: 
 The problem of classification with label noise can be stated in terms of random variables X, Y , and Y , where X is the feature vector, Y ∈ {1, . . . , K} is the true label associated to X, and Y ∈ {1, . . . , K} is a noisy version of Y . The learner has access to i.i.d. realizations of (X, Y ), and the objective is to learn a classifier that optimizes the risk associated with (X, Y ).In recent years, there has been a surge of interest in the challenging setting of instance (i.e., feature) dependent label noise, in which Y can depend on both Y and X. While several algorithms have been developed, there remains relatively little theory regarding algorithm performance and the fundamental limits of this learning paradigm. This work develops a theoretical framework for learning under multi-class, instance-dependent label noise. Our framework hinges on the concept of relative signal strength, which is a point-wise measure of "noisiness" in a label noise problem. Using relative signal strength to charachterize the difficulty of a label noise problem, we establish nearly matching upper and lower bounds for excess risk. We further identify distributional assumptions that ensure that the lower and upper bounds tend to zero as the sample size n grows, implying that consistent learning is possible. Surprisingly, Noise Ignorant Empirical Risk Minimization (NI-ERM) principle, which conducts empirical risk minimization as if no label noise exists, is (nearly) minimax optimal. To translate this insight into practice, we use NI-ERM to fit a linear classifier on top of a self-supervised feature extractor, achieving state-of-the-art performance on the CIFAR-N data challenge. matrix-valued function E : X → {M ∈ R K×K : M is row stochastic}, known as the noise transition matrix. The (i, j)-th entry of the matrix is defined as:[E(x)] i,j = P Y = j | Y = i, X = x .This implies that the noisy and clean class posteriors are related by η(x) = E(x) ⊤ η(x), where ⊤ denotes the matrix transpose. Domain adaptation perspective. Alternatively, label noise learning can be framed as a domain adaptation problem. In this view, P X Y represents the source domain, and P XY represents the target domain. The relationship between the two domains is characterized by "posterior drift," meaning that while the source and target share the same X-marginal, the class posteriors (i.e., the distribution of labels given X) may differ [Scott, 2019 , Cai and Wei, 2021 , Maity et al., 2023] . Thus, a label noise problem can also be described by a triple (P X , η, η).The two perspectives are equivalent, as discussed in Appendix A.1. In this work, we emphasize the domain adaptation perspective for Sections 4 and 5, and the noise transition perspective for Section 6. 
limitations: 
 Question: Does the paper discuss the limitations of the work performed by the authors?Answer: [Yes] Justification: Limitations about our practical method is described.Guidelines:• The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper. • The authors are encouraged to create a separate "Limitations" section in their paper.• The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be. • The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with a few runs. In general, empirical results often depend on implicit assumptions, which should be articulated. • The authors should reflect on the factors that influence the performance of the approach.For example, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon. • The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size. • If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness. • While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations. 
theory assumptions and proofs: 
 Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof? 
relative signal strength: 
 To study label noise, we introduce the concept of relative signal strength (RSS). This is a pointwise measure of how much "signal" (certainty about the label) is contained in the noisy distribution relative to the clean distribution. Previous work [Cannings et al., 2020, Cai and Wei, 2021] has examined a related concept within the context of binary classification, under the restriction that clean and noisy Bayes classifiers are identical. Our definition incorporates multi-class classification and relaxes the requirement that the clean and noisy Bayes classifiers agree.Definition 1 (Relative Signal Strength) For any class probability vectors η, η, define the relative signal strength (RSS) at x ∈ X as M(x; η, η) = minEQUATIONwhere 0/0 := +∞. Furthermore, for κ ∈ [0, ∞), denote the set of points whose RSS exceeds κ as A κ (η, η) = {x ∈ X : M(x; η, η) > κ} .M(x; η, η) is a point-wise measure of how much "signal" the noisy posterior contains about the clean posterior. To gain some intuition, first notice that if the noisy Bayes classifier predicts a different class than the clean Bayes classifier, the RSS is 0 by taking j = arg max η (assuming for simplicity that the arg max is a singleton set). Now suppose the clean and noisy Bayes classifiers do make the same prediction at x, say i * , and consider a fixed j.If [ η(x)] i * -[ η(x)] j [η(x)] i * -[η(x)] jis small, it means that the clean Bayes classifier is relatively certain that j is not the correct clean label, while the noisy Bayes classifier is less certain that j is not the correct noisy label. Taking the minimum over j gives the relative signal strength at x. As we formalize in the next section, a large RSS at x ensures that a small (pointwise) noisy excess risk at x implies a small (pointwise) clean excess risk. To gain more intuition, consider the following examples.Example 1 When η(x) = [0 1 0] ⊤ and η(x) = [0.3 0.6 0.1] ⊤ , M(x; η, η) = minj∈Y max i [ η(x)] i -[ η(x)] j max i [η(x)] i -[η(x)] j = [ η(x)] 2 -[ η(x)] 1 [η(x)] 2 -[η(x)] 1 = 0.6 -0.3 1 -0 = 0.3.Here, first of all, arg max η = arg max η = 2, i.e., the clean and noisy Bayes classifier give the same prediction. What's more, M(x; η, η) < 1 because the clean Bayes classifier is absolutely certain about its prediction, while the noisy Bayes classifier is much less certain.Example 2 When η(x) = [0 1 0] ⊤ and η(x) = [0 0 1] ⊤ , M(x; η, η) = minj∈Y max i [ η(x)] i -[ η(x)] j max i [η(x)] i -[η(x)] j = [ η(x)] 3 -[ η(x)] 3 [η(x)] 2 -[η(x)] 3 = 1 -1 1 -0 = 0.The zero signal strength results from η and η leading to different predictions about arg max.Example 3 (Comparison to KL divergence) When η(x) = [0.05 0.7 0.25] ⊤ , and η (1) (x) = [0.25 0.7 0.05] ⊤ , η (2) (x) = [0.1 0.6 0.3] ⊤ , 1 D KL η η (1) < 1 D KL η η (2) while M x; η, η (1) > M x; η, η (2) .Here, η (2) is "closer" to η in terms of KL divergence, but η (1) provides more information in terms of predicting the arg max of η. There is no conflict: KL divergence considers the similarity between two (whole) distributions, while the task of classification only focuses on predicting the arg max.This also illustrates why our notion of RSS is better suited for the label noise problem than other general-purpose distance measures between distributions.A desirable learning scenario would be if A κ (η, η) = X for some large κ, indicating that the signal strength is big across the entire space. Unfortunately, this ideal situation is generally not achievable.To gain some insight, consider the following result, proved in Appendix A.2.1.Proposition 1 A 0 (η, η) = x ∈ X : arg max η(x) ⊆ arg max η(x) .If we assume that both arg max sets are singletons, this result indicates that A 0 , the region with positive RSS, is the region where the true and noisy Bayes classifiers agree. Accordingly, X \ A 0 , the zero signal region, is the region where the clean and noisy Bayes decision rules differ. The "region of strong signal," A κ , is a subset of A 0 . Since the clean and noisy Bayes classifiers will typically disagree for at least some x, A 0 ̸ = X in general. We note that the strong assumption that A 0 = X has been made in prior studies [Cannings et al., 2020, Cai and Wei, 2021] . Our notion of RSS relaxes this assumption and provides a unified view.We can express relative signal strength more explicitly in the binary setup. Let η(x) := [η(x)] 1 =P (Y = 1 | X = x) and η(x) := [ η(x)] 1 = P Y = 1 | X = x .In standard binary classification, the margin [Tsybakov, 2004, Massart and Nédélec, 2006] , defined as η(x) -1 2 , serves as a pointwise measure of signal strength. Our notion of relative signal strength (RSS) can be interpreted as an extension of this concept in the context of label noise learning.Proposition 2 In the binary setting, for κ ≥ 0,M(x; η, η) = max η(x) -1 2 η(x) -1 2 , 0 , and A κ (η, η) = x ∈ X : η(x) -1 2 η(x) -1 2 > κ .In other words, RSS can be viewed as a "relative" margin.Example 4 Illustration of relative signal strength in a binary classification setup (Figure 1 ).Now putting definitions together, we consider the posterior drift model Π defined over the triple ) , and define(P X , η, η). Let ϵ ∈ [0, 1], κ ∈ [0, +∞Π(ϵ, κ) := (P X , η, η) : P X A κ (η, η) ≥ 1 -ϵ .This is a set of triples (label noise problems) such that A κ , the region with RSS at least κ, covers at least 1ϵ of the probability mass. In the next section, we will demonstrate that the performance within A κ can be guaranteed, whereas learning outside the region A κ is provably challenging. The gray region, x ∈ (0, 5), is where the true and noisy Bayes classifiers differ, and is also the zero signal region X \ A 0 . The red region is A 0.4 , where the RSS is > 0.4. Note that as x ↑ 0, M(x; η, η) ↑ ∞, which occurs since [η(x)] 1 ↑ 1/2, while [ η] 1 is far from 1/2. For x = 0 + , the predicted labels under η and η disagree, and the RSS crashes to 0. 
upper and lower bounds: 
 In this section, we establish both upper and lower bounds for excess risk under multi-class instancedependent label noise.Our first theorem reveals a fundamental limit: no classifier trained using noisy data can surpass the constraints imposed by relative signal strength in a minimax sense. To state the theorem, we employ the following notation and terminology. Denote the noisy training data byZ n = (X i , Y i ) n i=1 i.i.d.∼ P X Y . A learning rule f is an algorithm that takes Z n and outputs a classifier. The risk R( f ) of a learning rule is a random variable, where the randomness is due to the draw Z n .Theorem 1 (Minimax Lower Bound) Let ϵ ∈ [0, 1], κ > 0. Then inf f sup (P X ,η, η)∈Π(ϵ,κ) E Z n R f -R(f * ) ≥ K -1 K ϵ + Ω 1 κ 1 n ,where the inf is over all learning rules.The proof in Appendix A.2.3 offers insights into how label noise impacts the learning process: On the low RSS region (X \A κ ), learning is difficult if not impossible, and the learner incurs an irreducible error of (1 -1/K)ϵ. On the high RSS region (A κ ), the standard nonparametric rate [Devroye et al., 1996] is scaled by 1/κ. These aspects determine fundamental limits that no classifier trained only on noisy data can overcome without additional assumptions.This subsection establishes an upper bound for Noise Ignorant Empirical Risk Minimizer (NI-ERM), the empirical risk minimizer trained on noisy data. This result implies that NI-ERM is (nearly) minimax optimal, a potentially surprising result given that NI-ERM is arguably the simplest approach one might consider. We begin by presenting a general result on the excess risk of any classifier, which is proved in Appendix A.2.4.Lemma 1 (Oracle Inequality) For any label noise problem (P X , η, η) and any classifier f ,R(f ) -R(f * ) ≤ inf κ>0 P X X \ A κ (η, η) + 1 κ R(f ) -R f * .For (P X , η, η) ∈ Π(ϵ, κ), the first term is bounded by ϵ. When f is selected by ERM over the noisy training data, conventional learning theory implies a bound on the second term. This leads to the following upper bound for NI-ERM, whose proof is in Appendix A.2.5.Theorem 2 (Excess Risk Upper Bound of NI-ERM) Let ϵ ∈ [0, 1], κ > 0. Consider any (P X , η, η) ∈ Π(ϵ, κ), assume function class F has Natarajan dimension V , and the noisy Bayes classifier f * belongs to F. Let f ∈ F be the ERM trained onZ n = (X i , Y i ) n i=1 , i.e., f = arg min f ∈F 1 n n i=1 1 {f(Xi)̸ = Yi} . Then E Z n R f -R(f * ) ≤ ϵ + Õ 1 κ V n .Õ denotes big-O notation ignoring logarithmic factors. The Natarajan dimension is a multiclass analogue of the VC dimension. The upper bound in Theorem 2 aligns with the minimax lower bound (Theorem 1) in both terms. For the irreducible error ϵ, there is a small gap of 1/K. This gap arises because, in the lower bound construction, the low signal region X \ A κ is known to the learner, whereas knowledge of X \ A κ is not provided to NI-ERM. If A κ were known to the learner (an unrealistic assumption), then a mixed strategy that preforms NI-ERM on A κ and randomly guesses on X \ A κ would have an upper bound with first term of (1 -1/K)ϵ, exactly matching the lower bound. Regarding the second term, there is a universal constant and a logarithmic factor between the lower and upper bounds, which is a standard outcome in learning theory.This result is surprising as it indicates that the simplest possible approach, which ignores the presence of noise, is nearly optimal. No learning rule could perform significantly better in this minimax sense.The previous sections have analyzed learning with label noise over the class Π(ϵ, κ) = {(P X , η, η) :P X (A κ ) ≥ 1 -ϵ}. Now, the set X \ A κ equals (X \ A 0 ) ∪ (A 0 \ A κ ).The first part of this decomposition is the region where the Bayes classifiers under the noisy and clean distributions differ, while the second is a region where these match, but the RSS is small. Naturally, while P X (X \ A 0 ) must be incurred as an irreducible error, one may question why the class Π also limits the mass of A 0 \ A κ . After all, with enough data, the optimal prediction in this region can be learned.This issue would be resolved if there existed a κ 0 > 0 such that P X (A 0 ) = P X (A κ0 ), i.e., if P X (A 0 \ A κ0 ) = 0. In fact, our lower bound from Theorem 1 uses precisely such a construction. An interesting point of comparison to this condition lies in Massart's hard-margin condition from standard supervised learning theory, which, for binary problems, demands thatP X (|[η(x)] 1 -[η(x)] 2 | < h) = 0for some h > 0, under which one obtains minimax excess risk bounds of O( V /nh) [Massart and Nédélec, 2006] . With this lens, we can view the condition P X (A 0 \ A κ0 ) = 0 as a type of hard-margin condition on the relative signal strength M. This naturally motivates a smoothened version of this condition, inspired by Tsybakov's soft-margin condition [Tsybakov, 2004] .Definition 2 A triple (P X , η, η) satisfies an (ϵ, α, C α )-smooth relative signal margin condition with ϵ ∈ [0, 1], α > 0, C α > 0 if ∀κ > 0, P X (M(x; η, η) ≤ κ) ≤ C α κ α + ϵ.Further, we define Π ′ (ϵ, α, C α ) as the set of triples (P X , η, η) that satisfy an (ϵ, α, C α )-smooth relative signal margin condition.We show in Appendix A.2.7 that the techniques of Section 5.2 yield the following result for Π ′ .Theorem 3 Let ϵ ∈ [0, 1], α > 0, C α > 0. Consider any (P X , η, η) ∈ Π ′ (ϵ, α, C α ), assume function class F has Natarajan dimension V , and the noisy Bayes classifier f * belongs to F. Let f ∈ F be the ERM trained on 2+2α) .Z n = (X i , Y i ) n i=1 . Then E Z n R f -R (f * ) ≤ ϵ + inf κ>0 C α κ α + Õ 1 κ V n = ϵ + Õ n -α/(Compared to Theorem 2, we see that the rate of the second term is slightly slower, which is consistent with standard learning theory where Massart's hard margin assumption leads to faster rates than Tsybakov's. The advantage of the smooth relative margin is that the irreducible term in the above theorem is exactly P X (X \ A 0 ), which has a clearer meaning as it measures the mismatch between clean and noisy Bayes classifiers. Further, notice that the NI-ERM algorithm does not need information about α, and thus the result is adaptive to both α, and to the optimal κ for each value of α, as a consequence of the oracle inequality of Lemma 1.More broadly, Theorem 3 illustrates the flexibility of our conceptualization of label noise problems through RSS. The RSS M characterizes the irreducible error in label noise learning, similar to how the regression function η characterizes excess risk in standard learning. Thus, standard theoretical frameworks can be adapted to the noisy label problem via the relative signal.6 Conditions that ensure noise immunityThe minimax lower bound in the previous section revealed a negative outcome, indicating that no method can do well in the low signal region. Nevertheless, numerous empirical successes have been observed even under significant label noise. This is not mere coincidence. In this section, we will illustrate that the high signal region A κ can indeed cover the entire input space X even under massive label noise, albeit with the constraint A κ ⊆ A 0 as stated in Proposition 1. This not only explains past empirical successes, but also gives a rigorous condition on the consistency of NI-ERM.This section will delve into the study of noise transition matrix E and establish precise conditions that lead to A 0 = X . These conditions are linear algebraic conditions on E that ensure arg max η(x) = arg max η(x). As a result, we can infer that in a 10-class classification problem, even with up to 90% of training labels being incorrect, the NI-ERM can still asymptotically achieve Bayes accuracy. In the upcoming definition, we introduce the concept of noise immunity, wherein the optimal classifiers remain unaffected by label noise [Menon et al., 2015 , Scott, 2019] .Definition 3 (Immunity) We say that a K-class classification problem (P X , η, η) is immune to label noise if ∀x ∈ X , arg max η(x) = arg max η(x).Notice that due to Proposition 1, if a problem is immune, then A 0 = X . We now provide necessary and sufficient conditions on noise transition matrix E that ensure noise immunity. We begin by considering distribution P XY with zero Bayes risk, that is, where η is one-hot almost surely. A matrix is defined as diagonally dominant if, for each row, the diagonal element is the unique maximum.Theorem 4 (Immunity for Zero-error Distribution) If P XY has Bayes risk of zero, then immunity holds if and only if for all x, the noise transition matrix E(x) is diagonally dominant.Remark For a zero-error distribution P XY , even corrupted with instance-dependent label noise, achieving the Bayes risk is still feasible with a noise rate P Y ̸ = Y up to K-1 K . This highlights that the task of classification itself is robust to label noise, specially when the clean η is well-separated.The above result relies on strong assumptions about the distribution P XY . Now, we present a result that applies to any distribution, which, as a trade-off, turns out to impose more requirements on E.Theorem 5 (Universal Immunity) For any choice of P XY , immunity holds Previous works [Ghosh and Kumar, 2017 , Menon et al., 2018 , Oyen et al., 2022] have established that symmetric label noise is sufficient for immunity. Our contribution advances this understanding by demonstrating that such noise conditions are not only sufficient but also necessary. Specifically, under symmetric label noise, learning towards the Bayes classifier is feasible as long as the proportion of wrong labels does not exceed K-1 K . Furthermore, this transition is abrupt: when⇐⇒ ∃ e(x) > 0 s.t. ∀x ∈ X , [E(x)] i,j = 1 K + e(x) i = j 1 K -e(x) K-1 i ̸ = j.P Y ̸ = Y < K-1 K , A 0 = X , but when P Y ̸ = Y ≥ K-1 K , A 0 = ∅.Consequently, we expect to see a sudden drop in performance when noise rate passes the threshold.The rationale behind the necessity of E(x) taking this specific form is that it redistributes the probability mass of η in a "uniform" manner. This constraint arises because E(x) cannot favor any classes besides the true class. For instance, consider η(x)= 1 K + δ 1 K -δ 1 K • • • 1 K ⊤for some small δ > 0, a "non-uniform" E(x) would alter the arg max.The above theorems demonstrate that signal strength at x can still be high even under massive label noise P Y ̸ = Y , and, in essence, it is the discrete nature of the classification problem that allows robustness to label noise. When immunity holds, the irreducible error in Theorem 2 vanishes, therefore NI-ERM becomes a consistent learning rule. We validate this through data simulations presented in Figure 2 , where we systematically flip labels uniformly and observe the corresponding changes in the testing accuracy of NI-ERM. The simulation results align closely with the theoretical expectations: NI-ERM achieves near-Bayes risk performance until a certain noise threshold is reached, beyond which the testing performance sharply deteriorates.Question: Does the paper provide open access to the data and code, with sufficient instructions to faithfully reproduce the main experimental results, as described in supplemental material?Answer: [Yes] Justification: Code is provided, common benchmark datase were used, instructions are given, the result is easily reproducible.Guidelines:• The answer NA means that paper does not include experiments requiring code. • Providing as much information as possible in supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted. 
experimental setting/details: 
 Question: Does the paper specify all the training and test details (e.g., data splits, hyperparameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?Answer: [Yes] Justification: See appendix and attached code.Guidelines:• The answer NA means that the paper does not include experiments.• The experimental setting should be presented in the core of the paper to a level of detail that is necessary to appreciate the results and make sense of them. • The full details can be provided either with the code, in appendix, or as supplemental material. 
practical implication: 
 The modern practice of machine learning often involves training a deep neural network. In complex tasks involving noisy labels, the naïve NI-ERM is often outperformed by state-of-the-art methods by a significant extent [Li et al., 2020 , Xiao et al., 2023] . This is consistent with the finding that directly training a large neural network on noisy data frequently leads to overfitting [Zhang et al., 2021a ].Yet this is not grounds for abandoning NI-ERM altogether as a practical strategy. Instead of using NI-ERM for end-to-end training of a deep neural network, we instead propose the following simple, two-step procedure, termed 'feature extraction + NI-ERM'.This approach has three advantages over full network training. First, it avoids the potentially negative impact of the noisy labels on the extracted features. Second, it enjoys the inherent robustness of fitting a simple model (step 2) on noisy data, which we observed in Figure 2 . Third, it avoids the need to tune hyperparameters of the feature extractor using noisy labels. We note that a "self-supervised + simple approach" to learning was previously studied by Bansal et al. [2021] , although their focus was on generalisation properties without label noise. We also acknowledge that the practical idea of ignoring label noise is not new [Ghosh and Lan, 2021] , but the full power of this approach has not been previously recognized. For example, prior works often combine this approach with additional steps or employ early stopping to mitigate the effects of noise [Zheltonozhskii et al., 2022 , Xue et al., 2022] .Remarkably, this two-step approach attains extremely strong performance. We conducted experiments1 on the CIFAR image data under two scenarios: synthetic label flipping (symmetric noise) and realistic human label errors [Wei et al., 2022] , as shown in Figure 3 . We examine three different feature extractors: the DINOv2 foundation model [Oquab et al., 2023] , ResNet-50 features extracted from training on ImageNet [He et al., 2016] , and self-supervised ResNet-50 using contrastive loss [Chen et al., 2020] . We also compared to a simple linear model trained on the raw pixel intensities, and a ResNet-50 trained end-to-end. We observed that ResNet-50 exhibits degrading performance with increasing noise, consistent with previous findings [Zhang et al., 2021a , Mallinar et al., 2022] .The linear model demonstrates robustness to noise, but suffers from significant approximation error. [He et al., 2016] ), self-supervised learning (ResNet-50 trained on CIFAR-10 images with contrastive loss [Chen et al., 2020] ), or a pretrained self-supervised foundation model DINOv2 [Oquab et al., 2023] significantly boosts the performance of the original linear model. In contrast, full training of a ResNet-50 leads to overfitting.Conversely, the FE+NI-ERM approach enjoys the best of both worlds. Regardless of how the feature extraction is carried out, the resulting models exhibit robustness to label noise, while the overall accuracy depends entirely on the quality of the extracted features. This is illustrated in Figure 3 , where the flatness of the accuracy curves as noise increases indicates the robustness, and the intercept at zero label noise is a measure of the feature quality. Importantly, this property holds true even under realistic label noise of CIFAR-N [Wei et al., 2022] . In fact, we find that using the DINOv2 [Oquab et al., 2023] extracted features in our FE+NI-ERM approach yields state of the art results on the CIFAR-10N and CIFAR-100N benchmarks, across the noise levels, as shown in Table 1 .We emphasize that the only hyperparameters of our model are the hyperparameters of the linear classifier, which are tuned automatically using standard cross-validation on the noisy labels. This contrasts to the implementation of many methods on the CIFAR-N leaderboard (http://noisylabels.com/)2 , where the hyperparameters are hard-coded. Furthermore, our approach does not rely on data augmentation. Additional experiments, detailed in Appendix A.4 , include comparisons with the 'linear probing, then fine-tuning' approach [Kumar et al., 2022] , the application of different robust learning strategies on DINOv2 features, and results on synthetic instance-dependent label noise.Overall, the strong performance, the simplicity of the approach and the lack of any untunable hyperparameters highlights the effectiveness of FE+NI-ERM, and indicates the value of further investigation into its properties.Table 1 : Performance comparison with CIFAR-N leaderboard (http://noisylabels.com/) in terms of testing accuracy. "Aggre", "Rand1", . . . , "Noisy" denote various types of human label noise.We compare with four methods that covers the top three performance for all noise categories: ProMix [Xiao et al., 2023] , ILL [Chen et al., 2023] , PLS [Albert et al., 2023] and DivideMix [Li et al., 2020] .Our approach, a Noise Ignorant linear model trained on features extracted by the self-supervised foundation model DINOv2 [Oquab et al., 2023] achieves new state-of-the-art results, highlighted in bold. We employed Python's sklearn logistic regression and cross-validation functions without data augmentation; the results are deterministic and directly reproducible. Empirical CDF RSS for realistic human label error. To calculate the RSS under realistic human label error, we train two linear classifiers on DINOv2 features under clean and noisy labels and use the models' predictions as estimates for the class probabilities η and η. Despite the high overall noise rate in CIFAR-10N "Worst" labels, with P(Y ̸ = Y ) = 40.21%, we conjecture that the region where there is no signal, X \ A 0 , covers only a small portion of the probability mass (ϵ ≤ 4%). Furthermore, the cumulative distribution of the estimated RSS can be upper-bounded by a polynomial C α κ α + ϵ, supporting the validity of the smooth relative signal margin condition introduced in Section 5.3.Cακ α + = 1.49 • κ 1.35 + PX(M(x; η, η) ≤ κ)) = 0.04Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?Answer: [Yes]Justification: We have done repeated experiments for data simulation, e.g., different iid draw.For the result on CIFAR-N data challenge, our result is deterministic and thus no error bar.Guidelines:• The answer NA means that the paper does not include experiments.• The authors should answer "Yes" if the results are accompanied by error bars, confidence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.• The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions). • The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.) • The assumptions made should be given (e.g., Normally distributed errors).• It should be clear whether the error bar is the standard deviation or the standard error of the mean. Guidelines:• The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.• If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction). 
conclusions: 
 This work presents a rigorous theory for learning under multi-class, instance-dependent label noise. We establish nearly matching upper and lower bounds for excess risk and identify precise conditions for classifier consistency. Our theory reveals the (nearly) minimax optimality of Noise Ignorant Empirical Risk Minimizer (NI-ERM). To make this theory practical, we provide a simple modification leveraging a feature extractor with NI-ERM, demonstrating significant performance enhancements. A limitation of this work is that our methodology warrants more extensive experimental evaluation. A Appendix / supplemental material A.1 Equivalence of noise transition and domain adaptation perspectivesThe noise transition perspective models the joint distribution of (X, Y, Y ), which can be characterized as:P X,Y, Y = P X P Y |X η P Y |Y,X EThus, by specifying P X , η, and E, we obtain a triple (P X , η, η) with η(x) = E(x) ⊤ η(x).In contrast, the domain adaptation perspective views label noise problems directly as a triple (P X , η, η), bypassing the explicit modeling of the noise transition matrix E.If no assumptions are made about the form of E, the domain adaptation view remains fully expressive. Given a triple (P X , η, η), we can always define a noise transition matrix as:E(x) = 1 η ⊤ ,where 1 = [1 . . . 1] ⊤ . We can verify that E is row-stochastic, andη = E(x) ⊤ η = ( η1 ⊤ )η = η(1 ⊤ η) = η.Therefore, these two perspectives are equivalent.A.2 Proofs A.2.1 Proof of Proposition 1 Proposition A 0 (η, η) = x ∈ X : arg max η(x) ⊆ arg max η(x) .Proof. Notice thatM(x; η, η) = 0 ⇐⇒ arg max η(x) ̸ ⊆ arg max η(x).This is because M(x; η, η) = 0 when the numerator is zero and the denominator is non-zero, which happens when arg max η(x) ̸ ⊆ arg max η(x).An equivalent statement of this isM(x; η, η) > 0 ⇐⇒ arg max η(x) ⊆ arg max η(x). 
broader impacts: 
 Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?Answer: [NA] Justification: This is a theory-oriented paper towards better understanding of label noise problem.Guidelines:• The answer NA means that there is no societal impact of the work performed.• If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact. • Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations. • The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster. • The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology. • If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?Answer: [NA] Justification: The paper poses no such risks Guidelines:• The answer NA means that the paper poses no such risks.• Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters. • Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images. • We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make a best faith effort.12. Licenses for existing assets Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?Answer: [Yes] Justification: Citations and urls are included.Guidelines:• The answer NA means that the paper does not use existing assets.• The authors should cite the original paper that produced the code package or dataset.• The authors should state which version of the asset is used and, if possible, include a URL. • The name of the license (e.g., CC-BY 4.0) should be included for each asset.• For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided. • If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset. • For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided. • If this information is not available online, the authors are encouraged to reach out to the asset's creators. 
new assets: 
 Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?Answer: [NA] Justification: The paper does not release new assets.Guidelines:• The answer NA means that the paper does not release new assets.• Researchers should communicate the details of the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc. • The paper should discuss whether and how consent was obtained from people whose asset is used. • At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file. 
crowdsourcing and research with human subjects: 
 Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?Answer: [NA] Justification: The paper does not involve crowdsourcing nor research with human subjects.Guidelines:• The answer NA means that the paper does not involve crowdsourcing nor research with human subjects. • Including this information in the supplemental material is fine, but if the main contribution of the paper involves human subjects, then as much detail as possible should be included in the main paper. • According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector. 
institutional review board (irb) approvals or equivalent for research with human subjects: 
 Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?Answer: [NA] Justification: The paper does not involve with this matter.Guidelines:• The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.• Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper. • We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution. • For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review. 
 
 Appendix: Proposition In the binary setting, for κ ≥ 0,M(x; η, η) = max η(x) -1 2 η(x) -1 2 , 0 , and A κ (η, η) = x ∈ X : η(x) -1 2 η(x) -1 2 > κ .Proof. In a brute-force way, we can examine the nine cases where η(x), η(x) is greater, equal, or smaller than 1/2.If η(x) > , η(x) > 1 2 , then M(x; η, η) = min j∈Y max i [ η(x)] i -[ η(x)] j max i [η(x)] i -[η(x)] j = η(x) -(1 -η(x)) η(x) -(1 -η(x)) = η(x) -1 2 η(x) -1 2 = max η(x) -1 2 η(x) -1 2 , 0 . If η(x) < , η(x) < 1 2 , the same argument holds. If η(x) > , η(x) < 1 2 or η(x) < 1 2 , η(x) > 1 2 , take j = arg max η(x), we have M(x; η, η) = min j∈Y max i [ η(x)] i -[ η(x)] j max i [η(x)] i -[η(x)] j = 0 = max η(x) -1 2 η(x) -1 2 , 0 . If η(x) = , η(x) < 1 2 or η(x) = 1 2 , η(x) < 1 2 , take j ̸ = arg max η(x), we have M(x; η, η) = min j∈Y max i [ η(x)] i -[ η(x)] j max i [η(x)] i -[η(x)] j = 0 = max η(x) -1 2 η(x) -1 2 , 0 . If η(x) = , then M(x; η, η) = min j∈Y max i [ η(x)] i -[ η(x)] j max i [η(x)] i -[η(x)] j = max i [ η(x)] i -[ η(x)] j 0 ∀j = +∞ = max η(x) -1 2 η(x) -1 2 , 0 .Note that it makes sense for RSS to be +∞ when η(x) = 1 2 , because in this case, clean excess risk R(f ) -R(f * ) is 0 at point x for any classifier.Therefore, we can conclude thatM(x; η, η) = max η(x) -1 2 η(x) -1 2 , 0 ,by definition, we have, for κ ≥ 0A κ (η, η) = {x ∈ X : M(x; η, η) > κ} = x ∈ X : η(x) -1 2 η(x) -1 2 > κ .Now we provide a more formal statement of the minimax lower bound and its proof. We begin with the scenario where the noisy distribution P X Y has zero Bayes risk as an introductory example. The proof for the general case follows a similar strategy but involves more complex bounding techniques. We recommend that interested readers first review the proof of the zero-error version to build a solid understanding before tackling the general case.Now consider a more restricted subset of Π(ϵ, κ):Π(ϵ, κ, V, 0) := (P X , η, η) : P X A κ (η, η) ≥ 1 -ϵ, P X supported on V + 1 points, R * = 0 .Theorem (Minimax Lower Bound: whenEQUATIONProof.We will construct a triple (P X , η, η) that is parameterized byj, b := [b 1 b 2 • • • b V -1 ] ⊤ , and δ.First, we define P X . Pick any V + 1 distinct points x 0 , x 1 , . . . , x V ,P X (x) =      ϵ x = x 0 (1 -ϵ) • 1 n x = x 1 , . . . , x V -1 (1 -ϵ) • 1 -V -1 n x = x V ., this is where we need the condition that n > V -1.Then, define the clean and noisy class posteriors:EQUATIONEQUATIONwhere e i denotes the one-hot vector whose i-th element is one.The triple  and δ .(P X , η, η) is thus parameterized by j, b := [b 1 b 2 • • • b V -1 ] ⊤ ,This construction ensures (P X , η, η) ∈ Π(ϵ, κ, V, 0). In particular,A κ ⊇ {x 1 , x 2 , . . . , x V }, P X (A κ ) ≥ 1 -ϵ, X \ A κ ⊆ {x 0 }, P X (X \ A κ ) ≤ ϵ,and R * = 0 because η(x) is one-hot for all x.For any classifier f , by definition, its risk equalsR (f ) = E X,Y 1 f (X)̸ =Y = E X E Y |X [1 f (X)̸ =Y ] = E X E Y |X [1 -1 f (X)=Y ] = E X 1 -[η(X)] f (X) = X 1 -[η(x)] f (x) dP X (x).Therefore, the Bayes risk and excess risk equalR(f * ) = inf f E X,Y 1 f (X)̸ =Y = X (1 -max η(x)) dP X (x), R(f ) -R(f * ) = X max η(x) -[η(x)] f (x) dP X (x).Under our construction of P X , R(f ) can be decomposed into two partsR (f ) = {x0} 1 -[η(x)] f (x) dP X (x) :=R0(f ) + {x1,...,x V } 1 -[η(x)] f (x) dP X (x) :=R V (f ), and so can the excess riskR(f ) -R(f * ) = R 0 (f ) -R 0 (f * ) + R V (f ) -R V (f * ) = {x0} max η(x) -[η(x)] f (x) dP X (x) + {x1,...,x V } max η(x) -[η(x)] f (x) dP X (x).Recall that in our construction, (P X , η, η) is parameterized by j, b, and δ. Thereforesup (P X ,η, η)∈Π(ϵ,κ,V,0) E Z n R f -R(f * ) ≥ sup j,b,δ E Z n R f -R(f * ) = sup j,b,δ E Z n R 0 f -R 0 (f * ) + E Z n R V f -R V (f * ) = sup j E Z n R 0 f -R 0 (f * ) + sup b,δ E Z n R V f -R V (f * )where the last equality holds because region {x 0 } only depends on j, while region {x 1 , . . . , x V } only depends on b, δ.In the remaining part of the proof, we will examinesup j E Z n R 0 f -R 0 (f * ) (5)andsup b,δ E Z n R V f -R V (f * ) (6)separately.Let's start with the first term (5), which reflects the excess risk over the "low signal strength" region {x 0 }. Since η is one-hot on {x 0 }, its Bayes risk over that is zerosup j E Z n R 0 f -R 0 (f * ) = sup j E Z n R 0 f = sup j E Z n {x0} 1 f (x)̸ =j dP X (x) .To deal with sup j , we use a technique called "the probabilistic method" [Devroye et al., 1996] : replace j with a random variable J ∼ Uniform{1, 2, . . . , K}:sup j E Z n {x0} 1 f (x)̸ =j dP X (x) ≥ E J E Z n |J {x0} 1 f (x)̸ =J dP X (x) = E J, Z n {x0} 1 f (x)̸ =J dP X (x) = E Z n E J|Z n {x0} 1 f (x)̸ =J dP X (x) .Again, notice that J is an independent draw. Even if the point x 0 is observed in Z n , the associated noisy label Y = 1 does not give any information about the clean label Y = J. ThusE Z n E J|Z n {x0} 1 f (x)̸ =J dP X (x) = E Z n E J {x0} 1 f (x)̸ =J dP X (x) = E Z n {x0} E J 1 f (x)̸ =J dP X (x) = E Z n {x0} 1 - 1 K dP X (x) = 1 - 1 K ϵ.Now we have the minimax lower bound for the first part (5):sup j E Z n R {x0} f -R {x0} (f * ) ≥ 1 - 1 K ϵ.For the second part (6), which is over {x 1 , . . . , x V }, due to the relative signal strength condition, and from our explicit construction in Eqn. ( 3) and ( 4), the excess risks w.r.t. true and noisy distribution are related byR V (f ) -R V (f * ) = {x1,...,x V } max η(x) -[η(x)] f (x) dP X (x) = {x1,...,x V } 1 κ + δ max η(x) -[ η(x)] f (x) dP X (x) by construction of η, η = 1 κ + δ R V (f ) -R V ( f * ) , where R V (f ) := {x1,...,x V } 1 -[ η(x)] f (x) dP X (x). Also note that f * (x) = f * (x) for x ∈ {x 1 , . . . , x V },which is a result of our construction of η, η.Thensup b,δ E Z n R V f -R V (f * ) = sup b,δ E Z n 1 κ + δ R V (f ) -R V ( f * ) .This allows us to reduce the label noise problem to a standard learning problem: we have an iid sample Z n from P X Y and consider the risk evaluated on the same distribution P X Y . The remainder of the proof is similar to the proof of Devroye et al. [1996, Theorem 14.1] .Notice that by our construction, Y is a deterministic function of X. To be specific, Y = f * (X), wheref * (x) =      1 x = x 0 , b t x = x t , 1 ≤ t ≤ V -1 1 x = x Vis the noisy Bayes classifier.We use the shorthand f b := f * to denote that the noisy Bayes classifier depends on b.Since the noisy Bayes risk is zero,sup b,δ E Z n 1 κ + δ R V ( f ) -R V ( f * ) = sup b,δ 1 κ + δ E Z n R V ( f ) .Again, use the probabilistic method, replace b withB ∼ Uniform{1, 2} V -1 , sup b,δ 1 κ + δ E Z n R V ( f ) ≥ sup δ 1 κ + δ E B,Z n R V ( f ) = sup δ 1 κ + δ E Z n E B|Z n {x1,...,x V } 1 f (x)̸ =f B (x) dP X (x)Since we have B ∼ Uniform{1, 2} V -1 and also Z n |B ∼ P ⊗n X Y , then by Bayes rule (or eye-balling, since η is one-hot), we get the posterior distribution of B|Z n , to be specific:∀x ∈ {x 1 , • • • , x V }, If x = X i , i ∈ {1, 2, . . . , n} , then P f B (x) = Y i |Z n = 1, P f B (x) ̸ = Y i |Z n = 0 If x = x V , then P (f B (x) = 1|Z n ) = 1, P (f B (x) = 2|Z n ) = 0 If x / ∈ {X 1 , . . . , X n , x V }, then P (f B (x) = 1|Z n ) = 1 2 , P (f B (x) = 2|Z n ) = 1 2 ,where we overload the notation P to denote conditional probability of B|Z n .Then the optimal decision rule for predicting B based on sample Z n is:g(x; Z n ) =      Y i x = X i , i ∈ {1, 2, . . . , n} 1 x = x V random guess from {1, 2} x ̸ = X 1 , . . . , x ̸ = X n , x ̸ = x V .Therefore, the error comes from the probability of X ∈ {x 1 , . . . , x V } not being one of the observed X i : for any f ,E B,Z n R V ( f ) = E Z n E B|Z n {x1,...,x V } 1 f (x)̸ =f B (x) dP X (x) ≥ P (X ∈ {x 1 , . . . , x V }, g(X; Z n ) ̸ = f B (X)) ∵ error of f ≥ error of g = 1 - 1 2 P (X ̸ = X 1 , . . . , X ̸ = X n , X ̸ = x V , X ∈ {x 1 , . . . , x V }) = 1 2 V t=1 P (X ̸ = X 1 , . . . , X ̸ = X n , X ̸ = x V , X = x t ) = 1 2 V t=1 P (X 1 ̸ = x t , . . . , X n ̸ = x t , x V ̸ = x t , X = x t ) ∵ replace all X with x t = 1 2 V -1 t=1 P (X 1 ̸ = x t , . . . , X n ̸ = x t , X = x t ) = 1 2 V -1 t=1 P (X 1 ̸ = x t , . . . , X n ̸ = x t |X = x t ) P (X = x t ) = 1 2 V -1 t=1 (1 -P (X = x t )) n P (X = x t ) = 1 2 (V -1) 1 - 1 -ϵ n n 1 -ϵ n = (V -1)(1 -ϵ) 2n 1 - 1 -ϵ n n = (V -1)(1 -ϵ) 2n 1 - 1 -ϵ n 1+ϵ 1 - 1 -ϵ n n-1-ϵ ≥ (V -1)(1 -ϵ) 2n 1 - 1 -ϵ n 1+ϵ e -1+ϵ ∵ 1 - 1 -ϵ n n-1-ϵ ↓ e -1+ϵ ≥ (V -1)(1 -ϵ) 2n 1 - 1 n 2 e -1 ∵ ϵ ∈ [0, 1] ≥ (V -1)(1 -ϵ) 2n e -1 4 = (V -1)(1 -ϵ) 8en take n > 2.Now we get the minimax risk for the second part ( 6)sup b,δ E Z n R Aκ f -R Aκ (f * ) ≥ sup δ 1 κ + δ (V -1)(1 -ϵ) 8en ≥ 1 κ (V -1)(1 -ϵ) 8en let δ ↓ 0Combine the two parts together, we get the final result, for n > max(V -1, 2)sup (P X ,η, η)∈Π(ϵ,κ,V,0) E Z n R f -R(f * ) ≥ K -1 K ϵ + 1 κ (V -1)(1 -ϵ) 8en .As for the general version of the lower bound, now consider the set of triples:Π(ϵ, κ, V, L) := (P X , η, η) :P X A κ (η, η) ≥ 1 -ϵ, P X supported on V + 1 points, R Aκ f * P X A κ (η, η) ≤ L , where R C (f ) = C 1 -[ η(x)] f (x) dP X (x). Theorem (Minimax Lower Bound (General Version)) Let ϵ ∈ [0, 1], κ > 0, V > 1, L ∈ (0, 1/2).For any learning rule f based uponZ n = (X i , Y i ) n i=1 , for n ≥ V -1 2L max 16, 1 (1-2L) 2 sup (P X ,η, η)∈Π(ϵ,κ) E Z n R f -R(f * ) ≥ sup (P X ,η, η)∈Π(ϵ,κ,V,L) E Z n R f -R(f * ) ≥ K -1 K ϵ + 1 -ϵ κ (V -1)L 2n e -7 = K -1 K ϵ + Ω 1 κ 1 n .Proof.Now we construct a triple (P X , η, η) that is parameterized byj, b := [b 1 b 2 • • • b V -1 ] ⊤ , δ, c and p.First, we define P X . Pick any V + 1 distinct points x 0 , x 1 , . . . , x V ,P X (x) =      ϵ x = x 0 (1 -ϵ) • p x = x 1 , . . . , x V -1 (1 -ϵ) • (1 -(V -1)p) x = x V .This imposes the constraint (V -1)p ≤ 1, which will be satisfied in the end. Notice the difference compared to the previous zero-error proof: we place probability mass p, rather than 1/n, on x 1 , . . . , x V -1 .As for the clean and noisy class probabilities, chooseEQUATIONwhere e i denotes the one-hot vector whose i-th element is one.The construction for class posterior is also similar to the previous proof, except that for x = x t , t ∈ {1, . . . , V -1}, η is no longer a one-hot vector, rather has class probability separated by 2c:[ η(x)] 1 -[ η(x)] 2 = 2c.Therefore, the triple (P X , η, η) can be parameterized by j, b := [b 1 b 2 • • • b V -1 ] ⊤ , δ, c and p.Again, this construction ensures (P X , η, η) ∈ Π(ϵ, κ), to be specific:A κ ⊇ {x 1 , x 2 , . . . , x V }, P X (A κ ) ≥ 1 -ϵ, X \ A κ ⊆ {x 0 }, P X (X \ A κ ) ≤ ϵ.For any classifier f , its risk can be decomposed into two partsR (f ) = {x0} 1 -[η(x)] f (x) dP X (x) :=R0(f ) + {x1,...,x V } 1 -[η(x)] f (x) dP X (x) :=R V (f ), as can its excess riskR (f ) -R(f * ) = R 0 (f ) -R 0 (f * ) + R V f -R V (f * ) .In our construction, (P X , η, η) is parameterized byEQUATION)Note that we have used the fact thatR V (f ) -R V (f * ) = 1 κ + δ R V (f ) -R V ( f * ) , where R V (f ) := {x1,...,x V } 1 -[ η(x)] f (x) dP X (x).The first part (10) is exactly the same as in the zero-error proof, and we havesup j E Z n R 0 f -R 0 (f * ) ≥ 1 - 1 K ϵ.From this point forward, the procedure is similar to the proof of Devroye et al. [1996, Theorem 14.5 ].For the second part (11), the noisy Bayes classifier is stillf * (x) =      j x = x 0 , b t x = x t , 1 ≤ t ≤ V 1 x = x V .We also use the shorthand f b := f * to denote that the noisy Bayes classifier depends on b.Now the noisy Bayes risk is no longer zero. In factEQUATIONwhere the inequality holds from R Aκ ( f * ) = R V ( f * ) (because η is one-hot at point x 0 ) andP X A κ (η, η) ≥ P X {x 1 , . . . , x V } .Notice that in order to ensure that our construction (P X , η, η) ∈ Π(ϵ, κ, V, L), by definitionR Aκ f * P X A κ (η, η) ≤ L,Due to the upper bound of ( 12), it suffices to require thatEQUATIONand this ensures that (P X , η, η) ∈ Π(ϵ, κ, V, L) upon recalling that (P X , η, η) ∈ Π(ϵ, κ), and that P X is supported on V + 1 points.It should be noted that since (V -1)p ≤ 1 is required, and since c > 0, we have L < 1 • 1/2. This is the origin of our condition L < 1/2 in the statement of the theorem. Naturally, the statement can be adjusted to min(L, 1/2) instead. In any case, we are left with two nontrivial constraint on our parameters (p, c): ( 13) and (V -1)p ≤ 1, along with the boundary consraints p ∈ [0, 1] and c ∈ [0, 1/2].For fixed b, plugging in the definition of η, the excess risk over region {x 1 , . . . , x V } becomesR V ( f ) -R V ( f * ) = {x1,...,x V } 2c1 f (x)̸ =f b (x) dP X (x) ≥ 2c V -1 t=1 (1 -ϵ)p1 f (xt)̸ =f b (xt) ,where the inequality follows from the fact that we ignore the risk on point x V .Using the probabilistic method, replace b with B ∼ Uniform{1, 2} V -1 , sup b,δ,c,pE Z n 1 κ + δ R V ( f ) -R V ( f * ) ≥ sup δ,c,p E B,Z n 1 κ + δ R V ( f ) -R V ( f * ) = sup δ,c,p 1 κ + δ E Z n E B|Z n R V ( f ) -R V ( f * )Now, we need to calculate B|Z n , which can be calculated using Bayes rule because we have B ∼ Uniform{1, 2} V -1 and also Z n |B ∼ P ⊗n X Y . To be specific, for any x ∈ {x 0 , x 1 , . . . , x V -1 }, assume point x t is observed k times in training sample Z n ,P (f B (x) = 1|Z n ) = 1 2 x ̸ = X 1 , . . . , x ̸ = X n , x ̸ = x V P (B t = 1|Y t1 , . . . , Y t k ) x = x t = X t1 = • • • = X t k , 1 ≤ t ≤ V -1,where B t denotes the t-th element of vector B (that associates with x t ).Next we compute P (B t = 1|Y t1 = y 1 , . . . , Y t k = y k ) for y 1 , . . . , y k ∈ {1, 2}. Denote the numbers of ones and twos by k 1 = |{j ≤ k : y j = 1}| and k 2 = |{j ≤ k : y j = 2}|. Using Bayes rule, we getP (B t = 1|Y t1 , . . . , Y t k ) = P (B t = 1 ∩ Y t1 , . . . , Y t k ) P (Y t1 , . . . , Y t k ) = P (Y t1 , . . . , Y t k |B t = 1) P (B t = 1) 2 i=1 P (Y t1 , . . . , Y t k |B t = i) P (B t = i) = (1/2 + c) k1 (1/2 -c) k2 (1/2) (1/2 + c) k1 (1/2 -c) k2 (1/2) + (1/2 + c) k2 (1/2 -c) k1 (1/2) .After some calculation, following the proof of Devroye et al. [1996, Theorem 14 .5], we get sup b,δ,c,pE Z n 1 κ + δ R Aκ (f ) -R Aκ ( f * ) ≥ sup δ,c,p 1 κ + δ c(V -1)(1 -ϵ)pe -8n(1-ϵ)pc 2 1-2c - 4c √ n(1-ϵ)p 1-2c ≥ 1 -ϵ κ sup c,p c(V -1)pe -8npc 2 1-2c - 4c √ np 1-2c ∵ ϵ ≥ 0, take δ ↓ 0 = 1 -ϵ κ sup c,p c L 1/2 -c e -8npc 2 1-2c - 4c √ np 1-2c , ∵ (13) (14)where the supremum is over(p, c) ∈ [0, 1] × [0, 1/2] such that (V -1)p ≤ 1, and (V -1)p(1/2 -c) = L. Now, suppose n is so large that n ≥ (V -1) 8L(1/2 -L) 2 ⇐⇒ L ≤ 1 2 - (V -1) 8nL ,and further that(V -1) 8nL ≤ 1 8 ⇐⇒ n ≥ 8(V -1) L .We choosec = (V -1) 8nL , and p = L (V -1)(1/2 -c).By our choice of c and the first condition on n above, we can conclude that L ≤ (1/2c), and therefore,(V -1)p = L 1/2 -c ≤ 1,meaning that both the constraints required on (p, c) are met by the above choice.As a consequence of this choice of c, p, we observe thatnpc 2 = nL (V -1)(1/2 -c) • c 2 = nL (V -1)(1/2 -c) • (V -1) 8nL = 1 4 -8c ≤ 1 3 . Since c ≤ 1/8 further implies that 1 1-2c ≤ 4 3 , this implies that 8npc 2 1 -2c + 4 npc 2 1 -2c ≤ 8 3 • 4 3 + 4 • 4 3 • 1 3 ≤ 7.Thus, instantiating the bound ( 14), we conclude that sup b,δ,c,pE Z n 1 κ + δ R Aκ (f ) -R Aκ ( f * ) ≥ 1 -ϵ κ • V -1 8nL • L 1/2 -c • e -7 ≥ 1 -ϵ κ (V -1)L 8n e -7 • 2 = 1 -ϵ κ (V -1)L 2n e -7 .Putting the two parts togethersup (P X ,η, η)∈Π(ϵ,κ) E Z n R f -R(f * ) ≥ K -1 K ϵ + 1 -ϵ κ (V -1)L 2n e -7 , for n ≥ V -1 2L max 16, 1 (1-2L) 2 .A.2.4 Proof of upper bound: Lemma 1 Lemma (Oracle Inequality under Feature-dependent Label Noise) For any (P X , η, η) and any classifier f , we haveR(f ) -R(f * ) ≤ inf κ>0 P X X \ A κ (η, η) + 1 κ R(f ) -R f * .Proof. For any κ ≥ 0, the input space X can be divided into two regions: X \ A κ and A κ .For any f , its risk isR (f ) = E X,Y 1 f (X)̸ =Y = E X E Y |X [1 f (X)̸ =Y ] = E X E Y |X [1 -1 f (X)=Y ] = E X 1 -[η(X)] f (X) = X 1 -[η(x)] f (x) dP X (x).Therefore, its excess risk isR(f ) -R(f * ) = X max η(x) -[η(x)] f (x) dP X (x) = X \Aκ max η(x) -[η(x)] f (x) dP X (x) a ⃝ + Aκ max η(x) -[η(x)] f (x) dP X (x) b ⃝ Now examine the two terms separately, a ⃝ ≤ X \Aκ 1 dP X (x) = P X X \ A κ (η, η) , and b ⃝ < Aκ 1 κ max η(x) -[ η(x)] f (x) dP X (x) ∵ by definition of relative signal strength ≤ X 1 κ max η(x) -[ η(x)] f (x) dP X (x) = 1 κ R(f ) -R( f * ) ∵ by definition of R.Since this works for any κ > 0, we then haveR(f ) -R(f * ) ≤ inf κ>0 P X X \ A κ (η, η) + 1 κ R(f ) -R f * .To set the stage for the rate of convergence proof, we first introduce the concept of shattering in the multiclass setting and the Natarajan dimension [Natarajan, 1989] , which serves as a multiclass counterpart to the VC dimension [Vapnik and Chervonenkis, 1971] .Definition 4 (Multiclass Shattering) Let H be a class of functions from X to Y = {1, 2, . . . , K}.For any set containing n distinct elements C n = {x 1 , . . . , x n } ⊂ X , denoteH Cn = {(h(x 1 ), . . . , h(x n )) : h ∈ H} ,and therefore |H Cn | is the number of distinct vectors of length n that can be realized by functions in H.The n th shatter coefficient is defined asS(H, n) := max Cn |H Cn | .We say that a set C n is shattered by H if there exists f, g :C n → Y such that for every x ∈ C n , f (x) ̸ = g(x), andH C ⊇ {f (x 1 ), g(x 1 )} × {f (x 2 ), g(x 2 )} × • • • × {f (x n ), g(x n )} If Y = {1, 2}, this definition reduces to the binary notion of shattering which says all labeling of points can be realized by some function in the hypothesis class H, i.e., H C = {1, 2} |C| . Note that multiclass shattering does not mean being able to realize all K possible labels for each point x ∈ C. Instead, multiclass shattering is more like "embed the binary cube into multiclass", where every x ∈ C is allowed to pick from two of the K labels.Definition 5 (Natarajan Dimension) The Natarajan dimension of H, denoted Ndim(H), is the maximal size of a shattered set C ∈ X .Theorem (Excess Risk Upper Bound of NI-ERM) Let ϵ ∈ [0, 1], κ ∈ (0, +∞). Consider any (P X , η, η) ∈ Π(ϵ, κ), assume function class F has Natarajan dimension V , and the noisy Bayes classifier f * belongs to F. Let f ∈ F be the ERM trained onZ n = (X i , Y i ) n i=1, thenE Z n R f -R(f * ) ≤ ϵ + 1 κ • 16 V log n + 2V log k + 4 2n = ϵ + O 1 κ V n up to log factor.Proof. Following directly from Lemma 1, with (P X , η, η) ∈ Π(ϵ, κ), we already haveR(f ) -R(f * ) ≤ P X X \ A κ (η, η) + 1 κ R(f ) -R f * ≤ ϵ + 1 κ R(f ) -R f * .Now replace f with NI-ERM f . To bound the expected excess risk we employ a multiclass VC-style inequality.Lemma 2EQUATIONThe binary version of this lemma is Corollary 12.1 in Devroye et al. [1996] . We prove the multiclass version below in Section A.2.6.Next, we bound the multiclass shattering coefficient with Natarajan dimension, using the following lemma, which can be viewed as a multiclass version of Sauer's lemma.Lemma 3 (Natarajan [1989] ) Let C and Y be two finite sets and let H be a set of functions from C to Y. Then H) .EQUATIONLetting V denote Ndim(H), we have that S(H, n) ≤ n V K 2V , and therefore Lemma 2 can be upper bounded byE Z n R f -R f * ≤ 16 log (8e(n) V K 2V ) 2n = 16 log 8e + log (n V ) + log (K 2V ) 2n ≤ 16 V log n + 2V log K + 4 2nPutting things together,E Z n R f -R(f * ) ≤ ϵ + 1 κ • 16 V log n + 2V log K + 4 2n .A.2.6 Proof of Lemma 2 Theorem 6 Consider any set of multiclass classifiers F. Let (X 1 , Y 1 ), . . . , (X n , Y n ) be iid draws from P XY . For any n, and any ϵ > 0, Pr supf ∈F |R n (f ) -R(f )| > ϵ ≤ 8S(F, n)e -nϵ 2 /32where the probability is with respect to the draw of the data.Proof. Apply Theorem 12.5 from Devroye et al. [1996] , with the following identifications. In what follows, the left-hand side of each equation is a notation from Devroye et al. [1996] , and the right-hand side is our notation.ν = P XY Z = (X, Y ) Z i = (X i , Y i ) A = {A f | f ∈ F}, where A f := {(x, y) | f (x) = y}With these identifications, we haveν(A f ) = 1 -R(f ) ν n (A f ) = 1 n i 1 {Zi∈A f } = 1 n i 1 {f (Xi)=Yi} = 1 -R n (f )By Theorem 12.5 we concludePr sup f ∈F |R n (f ) -R(f )| > ϵ ≤ 8s(A, n)e -nϵ 2 /32 ,where s(A, n) (note the lowercase "s") is defined to be max z1,...,znN A (z 1 , . . . , z n )where the max is over points z 1 , . . . , z n , and N A (z 1 , . . . , z n ) is the number of distinct subsets of the form A f ∩ {z 1 , . . . , z n } as f ranges over F.To conclude the proof, it suffices to show that s(A, n) ≤ S(F, n), where the latter expression is the multiclass shatter coefficient defined above. We show this as follows.Consider fixed pairs z i = (x i , y i ), i = 1, . . . , n. Supposed that there are N distinct subsets of the form A f ∩ {z 1 , . . . , z n }, and let f 1 , . . . , f N be the classifiers in F that realize these distinct subsets. Consider the map that sends f i to the vector of its values at x 1 , . . . , x n :f i → (f i (x 1 ), . . . , f i (x n )) ∈ Y n .We will show that this map is injective, from which the claim follows. To see injectivity, consider classifiers f i and f j , where i ̸ = j. Since f i and f j yield different subsets, it means there is some pair (x k , y k ) such that one of f i and f j classifies the pair correctly, while the other does not. This implies that f i (x k ) ̸ = f j (x k ), and therefore(f i (x 1 ), . . . , f i (x n )) ̸ = (f j (x 1 ), . . . , f j (x n )).This concludes the proof. Now, Lemma 2 follows from the above theorem (stated in terms of the noisy data/distribution/risk) in precisely the same way that Corollary 12.1 in Devroye et al. [1996] Z n = (X i , Y i ) n i=1 . Then E Z n R f -R (f * ) ≤ ϵ + inf κ>0 C α κ α + Õ 1 κ V n = ϵ + Õ n -α/(2+2α) .Proof. Again, using Lemma 1, and Theorem 2, we can conclude the following, where C is some large enough constant.E Z n [R( f ) -R(f * )] ≤ inf κ>0 P X X \ A κ (η, η) + 1 κ R(f ) -R f * ≤ inf κ>0 P X X \ A κ (η, η) + 1 κ CV log(nK) n . Now, by definition of Π ′ (ϵ, α, C α ), it holds that ∀κ > 0, P X (M(x; η, η) ≤ κ) ≤ C α κ α + ϵ.Thus, we can further conclude thatE Z n [R( f ) -R(f * )] ≤ inf κ>0 ϵ + C α κ α + 1 κ CV log(nK) n .The final statement now comes from optimizing the above bound, which is attained by taking the derivative w.r.t. κ and set to zero, we haveκ * = (αC α ) -1 CV log(nK)/n 1/(α+1).This yields the boundE Z n [R( f ) -R(f * )] ≤ ϵ + O V log(nK)/n α/(α+1) = ϵ + Õ(n -α/(2α+2) ).A.2.8 Proof of immunity results: Theorem 4 and 5Here, we state the immunity theorems in an equivalent but different way, so that the proofs are easier to follow.Theorem (Immunity for one-hot vector) Denote B = {e 1 , . . . , e K } to be the set of one-hot vectors.∀ η(x) ∈ B, arg max η(x) = arg max E(x) ⊤ η(x)⇐⇒ Diagonal elements of E(x) maximizes its row.Proof. Let η(x) = e y for some y, thenη(x) = E ⊤ η(x) =         P Y = 1 | Y = y, X = x P Y = 2 | Y = y, X = x . . . P Y = K | Y = y, X = x         = [E(x)] ⊤ y,:To havearg max η(x) = arg max [E(x)] ⊤ y,: = arg max η(x) = yfor any choice of y, it is equivalent to say that the diagonal elements of E(x) maximizes its row.Theorem (Universal Immunity) Consider K-class classification, ∀ η(x), arg max η(x) = arg max E(x) ⊤ η(x)⇐⇒ ∃ e(x) s.t. ∀x, e(x) ∈ 0, 1 K andE(x) =     1 -(K -1)e(x) e(x) • • • e(x) e(x) 1 -(K -1)e(x) • • • e(x) . . . . . . . . . . . . e(x) e(x) • • • 1 -(K -1)e(x)     .Proof.⇐=: Plug E(x) into the expressionη(x) = E ⊤ η(x) =     1 -(K -1)e(x) e(x) • • • e(x) e(x) 1 -(K -1)e(x) • • • e(x) . . . . . . . . . . . . e(x) e(x) • • • 1 -(K -1)e(x)     η(x) =     (1 -K • e(x)) •     1 0 • • • 0 0 1 • • • 0 . . . . . . . . . . . . 0 0 • • • 1     + e(x) •     1 1 . . . 1     • 1 • • • 1     η(x) = (1 -K • e(x)) η(x) + constant vectorWhen e(x) ∈ [0, 1 K ), we have ∀η(x), arg max η(x) = arg max η(x).=⇒: Denote T (x) := E(x) ⊤ , thenT (x) =     t 11 (x) t 12 (x) • • • t 1K (x) t 21 (x) t 22 (x) • • • t 2K (x) . . . . . . . . . . . . t K1 (x) t K2 (x) • • • t KK (x)    has each column sum to 1. Let us consider several choices of η(x), which pose conditions on matrix T (x).1) If η(x) = 1 K 1 K • • • 1 K ⊤ , then η(x) = T (x)η(x) = 1 K     t 11 (x) + t 12 (x) + • • • + t 1K (x) t 21 (x) + t 22 (x) + • • • + t 2K (x) . . . t K1 (x) + t K2 (x) + • • • + t KK (x)     .To havearg max η(x) = arg max η(x) = {1, 2, . . . , k} ,all elements of η(x) must be equal, i.e., each row of T (x) should sum to the same value. The sum of all elements in T (x) is K, since all column sum to 1. Therefore, each row of T (x) also sum to 1.2) If η(x) = 1 K-1 1 K-1 • • • 1 K-1 0 ⊤ , then η(x) = T (x)η(x) = 1 K -1       t 11 (x) + t 12 (x) + • • • + t 1(K-1) (x) t 21 (x) + t 22 (x) + • • • + t 2(K-1) (x). . .t (K-1)1 (x) + t (K-1)2 (x) + • • • + t (K-1)(K-1) (x) t K1 (x) + t K2 (x) + • • • + t K(K-1) (x)       = 1 K -1       1 -t 1K (x) 1 -t 2K (x). . .1 -t (K-1)k (x) 1 -t KK (x)       . ∵ each row of T (x) sum to 1To havearg max η(x) = arg max η(x) = {1, 2, . . . , K -1} ,the first K -1 elements of η(x) must be equal (and larger than t KK (x)), then we havet 1K (x) = t 2K (x) = • • • = t (K-1)K (x).In other words, all elements of the K-th column of T (x) are the same (except for the (K, K)-th element). Similarly, consider η(x) to be a vector that contains 0 in the i-th position and 1 K-1 in other positions, then the general condition for T (x) is that: all elements of the i-th column are equal, except the i-th diagonal. Written explicitly,T (x) =       t 11 (x) t 12 (x) t 13 (x) • • • t 1K (x) t 21 (x) t 22 (x) t 13 (x) • • • t 1K (x) t 21 (x) t 12 (x) t 33 (x) • • • t 1K (x) . . . . . . . . . . . . . . . t 21 (x) t 12 (x) t 13 (x) • • • t KK (x)       .Since each row and column of T (x) sum to 1, we have               0 + t 12 (x) + t 13 (x) + • • • + t 1K (x) = (K -1)t 21 (x) ←-sum of first row = sum of first column t 21 (x) + 0 + t 13 (x) + • • • + t 1K (x) = (K -1)t 12 (x) t 21 (x) + t 12 (x) + 0 + • • • + t 1K (x) = (K -1)t 13 (x) . . . t 21 (x) + t 12 (x) + t 13 (x) + • • • + 0 = (K -1)t 1K (x)Subtracting the first equation from the second, we have t 12 (x) = t 21 (x). Repeating for all pairs of equations, we havet 21 (x) = t 12 (x) = t 13 (x) = • • • = t 1K (x).What's more, all diagonal elements of T (x) will be equal. Thus,T (x) =     1 -(K -1)e(x) e(x) • • • e(x) e(x) 1 -(K -1)e(x) • • • e(x) . . . . . . . . . . . . e(x) e(x) • • • 1 -(K -1)e(x)     , where e(x) ∈ [0, 1].3) The final step is to determine what value e(x) can take. Take η(x) = e y for some y, then from Theorem 4, we know that the diagonal elements of T (x) maximize their column, therefore1 -(K -1)e(x) > e(x) =⇒ e(x) ∈ [0, 1 K .Finally, take any η(x), the arg max is preserved by multiplying this specific choice of T (x). This concludes the ⇐= part.For 2D Gaussian mixture data, we draw from two Gaussian centered at [1 1] ⊤ and [-1 -1] ⊤ , with covariance matrix being identity, 200 data points from each, with label Y = 1, 2 respectively. To generate noisy labels, we flip every label uniformly with some probability. We use Sklearn's logistic regression (with no ℓ 2 regularization). The experiment was conducted on AMD Ryzen 5 3600 CPU. The goal of the simulation is to experimentally verify noise immunity results in Section 6. Notice that different trial corresponds to different draw of both instances and noisy labels. We flip the clean training label of MNIST (http://yann.lecun.com/exdb/mnist/) uniformly (to any of the wrong classes). We use a shallow neural network with two convolution layers and two fully connected layers. We train with stochastic gradient descent with learning rate 0.01 for 10 epochs, batch size equals 64. We use the same hyperparamters for all tests. The experiments were conducted on a single NVIDIA GTX 1660S GPU. The goal of the simulation is to experimentally verify noise immunity results in Section 6. Here randomness corresponds to different realization of noisy labels and stochastic gradient descent. We flip the clean training label of CIFAR-10 (https://www.cs.toronto.edu/~kriz/cifar. html) uniformly (to any of the wrong classes). To have a fair comparison between different methods, we fix the realization of noisy labels. Follow the 2-step procedure described in Section 7, we use different pre-trained neural networks as feature extractor: forward-passing the training image through the network and record the feature. Then use sklearn's (https://scikit-learn.org/stable/) logistic regression function to fit the (feature, noisy label) pair in a full batch manner. We prespecify a range of values for ℓ 2 regularization ({0.0001, 0.001, 0.01, 0.1, 1, 10, 100} ) and number of iterations for lbfgs optimizer ({10, 20, 50, 100}), then do cross-validation on noisy data to pick the best hyper-parameters. We use the same range of hyper-parameters in all tests. The experiments were conducted on a single NVIDIA Tesla V100 GPU. The result is deterministic.Table 4 : Peformance on CIFAR-10 with synthetic label noise. We apply linear model on top of different feature extractors: "ResNet-50 TL" refers to using a pre-trained ResNet-50 on ImageNet [Deng et al., 2009] (available in Pytorch model library) in a transfer learning fashion, "ResNet-50 SSL" refers to using a pre-trained ResNet-50 on unlabeled CIFAR data with self-supervised loss [Chen et al., 2020] (publicly downloadable weights https://github.com/ContrastToDivide/C2D? tab=readme-ov-file) and "DINOv2 SSL" refers to using the self-supervised foundation model DINOv2 [Oquab et al., 2023] We load the noisy human labels provided by http://noisylabels.com/, then follow exact the same procedure as above.Table 5 : Performance on CIFAR-N dataset (http://noisylabels.com/) in terms of testing accuracy. "Aggre", "Rand1", . . . , "Noisy" denote various types of human label noise. We apply linear model on top of different feature extractors: "ResNet-50 TL" refers to using a pre-trained ResNet-50 on ImageNet [Deng et al., 2009] in a transfer learning fashion, "ResNet-50 SSL" refers to using a pre-trained ResNet-50 on unlabeled CIFAR data with self-supervised loss [Chen et al., 2020] and "DINOv2 SSL" refers to using the self-supervised foundation model DINOv2 [Oquab et al., 2023] as the feature extractor. We employed Python's sklearn logistic regression and cross-validation functions without data augmentation; the results are deterministic and directly reproducible. We study whether 'linear probing, then fine tuning' (LP-FT) [Kumar et al., 2022] works better than linear probing (LP) only, in label noise learning scenario.Table 6 : Performance on CIFAR-N dataset (http://noisylabels.com/) in terms of testing accuracy. "Clean" refers to no label noise, "Aggre", "Rand1", . . . , "Noisy" denote various types of human label noise. We compare the testing accuracy of LP-FT versus LP only, over different feature extractors: "ResNet-50 TL" refers to using a pre-trained ResNet-50 on ImageNet [Deng et al., 2009] in a transfer learning fashion, "ResNet-50 SSL" refers to using a pre-trained ResNet-50 on unlabeled CIFAR data with contrastive loss [Chen et al., 2020] and "DINOv2 (small) SSL" refers to using a light version of the self-supervised foundation model DINOv2 [Oquab et al., 2023] [Ghosh and Kumar, 2017, Ma and Fattahi, 2022] , sigmoid loss [Ghosh et al., 2015] , and regularized approaches: 'Early-Learning Regularization' (ELR) [Liu et al., 2020] , 'Sharpness Aware Minimization' (SAM) [Foret et al., 2021] . Guidelines:• The answer NA means that the abstract and introduction do not include the claims made in the paper. • The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers. • The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings. • It is fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper.38th Conference on Neural Information Processing Systems (NeurIPS 2024).Perform feature extraction using any method (e.g., transfer learning or self-supervised learning) that does not require labels.Learn a simple classifier (e.g., a linear classifier) on top of these extracted features, using the noisily labelled data, in a noise-ignorant way.Code is available at: https://github.com/allan-z/label_noise_ignorance.If the link is inaccessible, see the May 23, 2024 archive captured by Wayback Machine: https://web. archive.org/web/20240523101740/http://noisylabels.com/. 


Decision: The paper presents a novel theoretical framework for learning with multi-class, instance-dependent label noise. While the reviewers were somewhat divided, the overall decision is to accept the paper.

Reviews: review: paper_summary: paper_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.
strength_weakness: strength_weakness: 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: 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.
limitations: limitations: Yes
paper_summary: paper_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.
strength_weakness: strength_weakness: - 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: questions: Not really, I will be happy to read the authors comments on my points from the weakness section.
limitations: limitations: Limitations were discussed. I see no negative social impact of this work.
paper_summary: paper_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.
strength_weakness: strength_weakness: 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: 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.
limitations: limitations: -
paper_summary: paper_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).
strength_weakness: strength_weakness: - 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: questions: - Does the analysis depend on any particular loss used during training?
limitations: limitations: yes
paper_summary: paper_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.
strength_weakness: strength_weakness: 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: 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?
limitations: 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.

Comments: title: Good rebuttal, concerns remain
Main Concerns Addressed by Authors' Response
comment: We thank all reviewers for the feedback. 
The discussion is very helpful.
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.
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.
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 authors,

Thank you for addressing my comments. All my questions are answered and I have no further comments. I will keep my initial rating.
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.
I have lowered my confidence level due to the realization of my misunderstanding.
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.
Thank you for your response.
Your review is very beneficial and definitely helps the paper to be better framed.
We really appreciate that.
Thanks.
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.
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.