Label Noise: Ignorance Is Bliss
Authors: Yilun Zhu
Jianxin Zhang
Aditya Gangrade
Clayton Scott
Venue: NeurIPS 2024 poster (2024)
Keywords: label noise; multi-class classification; learning theory; domain adaptation; minimax rate; self-supervised learning
Primary area: learning_theory

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.

Label Noise: Ignorance Is Bliss
Yilun Zhu
Jianxin Zhang EECS University of Michigan j jianxinzuum ch edu
EECS University of Michigan all Llanhuuuummi ch. edu
Aditya Gangrade
Clayton Scott
ECE Boston University gangrade@bu.co edu
EECS, Statistics University of Michigan clayscot@umich. edu
Abstract
We establish 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 relative signal strength (RSS), a pointwise measure that quantifies the transferability from noisy clean posterior. Using RSS, we establish nearly matching upper and lower bounds on the excess risk. Our theoretical findings support the simple 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 linear classifier on top of supe-vuue feature extractor, we achieve state-of-the-art performance on the CIFAR-N data challenge.
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 E (1,-.., K) is the true label associated X, and Y (1,.... K) a noisy version of Y. The learner has access to i.i.d. realizations of (X, Y), and the objective is to learn classifier that optimizes the risk associated with YX,
In recent years, there has been a surge interest in the challenging setting of instance (i.e., feature) dependent label noise, 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 theoretical framework for learning under multi-class, restance-dependen label noise. Our framework hinges on the concept of relative signal strength, which is point-wise measure of "noisiness" in label noise problem. Using relative signal strength to charachterize the difficulty of 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 zero as the sample size grows, implying that consistent learning is possible.
Surprisingly, Noise Ignorant Empirical Risk Minimization (NI-ERM) principle, which conducts empirical risk minimization if no label noise exists, is (nearly) minimax optimal. To translate this insight into practice, we use NI-ERM to fit lincar classifier on top of self-supervised feature extractor, achieving state-of-the-ar performance the CIFAR-N data challenge.
38th Conference on Neural Information Processing Systems (NeurIPS 2024).

---

2 Literature review
Theory and algorithms for classification with label noise are often based on different probabilistic models. Such models may be categorized according on how Y depends on Y and X. The simplest model is symmetric noise, where the distribution of Y is independent of Y and X [Angluin and Laird 1988]. In this case, the probability that Y = k is the same for all l: + Y, regardless of Y and X. In this setting, it is easy to show that minimizing the noisy excess risk (associated to the 0/1 loss) implies minimizing the clean excess risk, a property known immmnitt. When immunity holds, there is no need to modify the learning algorithm on account of noisy labels. In other words, the learner may be ignorant of the label noise and still learn consistently.
A more general model is classification with label dependent noise, in which the distribution of Y depends on Y. but not X. Many practical algorithmss have been developed over the years, based on principles including data re-weighting [Liu and Tao 2015). robust training (Han et al.) 2018 Liu et al. 2020, Hu et al. 22200] Foret et al. 202 1
Liu et al. 2022 and data cleaning [Brodley and Friedl 1999 Northcutt et al., [022]] Consistent learning a algorithms still exist, such as those
based loss correction Natarajan et al. 2013 Patrini et al. 2017 Van Rooyen and Williamson|
2018 Liu and Guo 2020 Zhang et al.) [002]. These approaches assume knowledge of the noise
transition probabilities, which can be estimated under some identifiability assumptions (Scott et al., 2013 Zhang et al. 2021b).
In the most general setting, that of instance dependent label noise, the distribution of y depends on both and X. While algorithms are emerging [Cheng et al., 202T Zhu et al. 202T Wang et al.) 2022. Yang et al. 2023), , theory has primarily focused on the binary setting. SScott [2019] establishes immunity for a Neyman-Pearson
performance criterion under a posterior drift model, discussed in more detail below. Cannings et al. (2020) establish an upper bound for excess risk under the strong
assumption that the optimal classifiers for the clean and noisy distributions are the same.
Closest to our work, Im and Grigas (0023 derive excess risk upper and lower bounds, and reach similar conclusion, that noise-ignorant ERM attains the lower bound up to constant factor. Our results, based on the new concept of relative signal strength, provide a more refined analysis.
Additional connections between our contributions and prior work are made throughout the paper.
3 Problem statement
Notation. X' denotes the feature space and y = (1,2, K} denotes the label space, with K E N. The K K-simplex AK := {p E R2K Vi, P; 2 0, Σp: P: 1]. A K K matrix is row stochastic all of its rows are in A Denote the i-th element of a vector v as [b]s, and the (i,j)-th element of a matrix M as [M] j..j.
In conventional multiclass classification, we observe training data Yi), .i)..... (X.,, Yn) drawn i...d. from a joint distribution Pxy. The marginal distribution of X is denoted by Px, and the class posterior probabilities Py x== the j-th component of the vector is [n(z)], = P (Y =j -il X I)). A classifier f: X' - y maps an instance x to class (xx) y. Denote the risk of classifier f with respect distribution Pxy as R(f) -xxx [1 (r(x)ry) J. The Bayes optimal classifier for Pxx is f (z) E arg max (x)). The Bayes risk, which is the minimum achievable risk, is denoted as R R( = inf, R()).
captured by K --simplex-valued vector 7) X - A where
We consider the setting where, instead of the true class label Y, a noisy label Y is observed. The training data (X1, YI)...,((X,,,,,,,, Yx) can be viewed as an i.i.d. sample drawn from a "noisy" distribution Pxp. We define Prix= ?7. R and f analogously to the "clean" distribution PXY.
The goal of learning from label noise is to find classifier that is able to minimize the "clean test error," that is, the risk R defined w.r.t. PxY. even though the learner has access to only corrupted training data (X,, Yi) itd
Pxv
Noise transition perspective. Traditionally, label noise is modeled through the joint distribution of (X, Y, Y). This joint distribution is governed by Px. the clean class posterior Prpx. and
2

---

matrix-valued function
: + (M E R Kxk M is row stochastic),
known as the noise transition matrix. The (i,j)-th entry of the matrix is defined as:
E(()), = = j
-i,x -
This implies that the noisy and clean class posteriors are related by 77(x) (())))))) where denotes the matrix transpose.
Domain adaptation perspective. Alternatively, label noise learning can be framed as a domain adaptation problem. In this view, "xy represents the source domain, and Pxy 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 X-marginal, the class posteriors (i.e., the distribution of labels given X) may differ [Scott] 2019 Cai and Weil 2021 Maity et al. 2023 Liu et al. 2024). Thus, a label noise problem can also be described by a triple (Px 17. 77)
The two perspectives are equivalent, as discussed in Appendix AA.1 In this work, we emphasize the domain adaptation perspective for Sections and and the noise transition perspective for Section 6
4 Relatíve 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 Weil [021] has examined 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 (Relative Signal Strength) For any class probability vectors n,, î, define the relative signal strength (RSS) at E X as
max; [-))) [+)r]
M(z.n. min JEy max, (x))] [m(x)]}
where 0/0 +oc. Furthermore, for E [0, oo), denote the set of points whose RSS exceeds k as An(n, = (ar E X M(x: 7) > k).
M(x; 17. 17) 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 by taking j = arg max îj (assuming for simplicity that the arg max is singleton set). Now suppose the clean and noisy Bayes classifiers do make the same prediction at x, say i*, and consider fixed j. If
[) - [7(x]]
[x))] (x)]
is 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 is not the correct noisy label. Taking the minimum over j gives the relative signal strength at ar. As we formalize in the next section, large RSS x ensures that 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 n)x)) = [0 1 oJ and (xx) = [0.3 0.6 0.1]T,
max, [x)] - [7x)), = [ - [+))]
0.6 0.3
M(x: n. 77 = min
jEy max, (x))) - [n()], [m(2]2 (n(x)) = 1-0 0.3.
Here, first of all, arg max arg max πj 2, Lee. the clean and noisy Bayes classifier give the same prediction. What's 's more, M(x; n7 9) because the clean Bayes classifier is absolutely certain about its prediction, while the noisy Bayes classifier is much less certain.
3

---

Example 2 When n>x) = [0 1 o] and 7(x) = 00 0 1]"
max; [+))]; [[0]]
M 770] 0.
M(zn, min jey
max, [=)]]; |n(=]l m=))]2 [x))ss
The zero signal strength results from ni and n leading to different predictions about arg
Example 3 (Comparison to KL divergence) When n(x) = [0.05 0.7 0.25] and (x) =
[0.25 0.7 0.05].. (x) = [0.1 0.6 0.3]".
1
while M (x: M (2; (.:)))))))
DKL (7) DKL T(2)
Here, 17 is "closer" to in terms of KL divergence, but (7 provides more information in terms of predicting the arg max of n. 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.
desirable learning scenario would be if (n 17) = X for some large K, 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 1.2.1
Proposition 1 An 17) x X arg max ()x) arg max n(z))
If we assume that both arg max sets are singletons, this result indicates that Ao, the region with positive RSS, is the region where the true and noisy Bayes classifiers agree. Accordingly, X' \ Ao. the zero signal region, is the region where the clean and noisy Bayes decision rules differ. The "region of strong signal." Are is subset of .gg Since the clean and noisy Bayes classifiers will typically disagree for at least some v, An 3 X' in general. We note that the strong assumption that Ao X has been made in prior studies [Cannings et al. 2020 Cai and Wei 2021 Our notion of RSS relaxes this assumption and provides unified view.
4.1 RSS in binary classification
We can express relative signal strength more explicitly in the binary setup. Let nπ()) = [n())] P PY==1 =V=11 X x:) and 7(x) = [+) P(Y
X = x). In standard binary classification, 1
the margin Tsybakov 2004 Massart and Nédélec 2006]. defined as (л())) - 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 n 2 O,
7(x) n(x))
7(z) 1 11())
M(a; = max
0 and
Aa(n. = E:
X:
2
In other words, RSS can be viewed as "relative" margin.
Example 4 Illustration of relative signal strength in binary classification setup (Figure) 7
4.2 Posterior Drift Model Class.
Now putting definitions together, consider the posterior drift model II defined over the triple (Px, n, M) Let E [0, E [0, +o.), and define
[T(, = (Px. Px (A.. (n. 2 21 1-c.
This is set of triples (label noise problems) such that Are, the region with RSS at least k, covers at least 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.

---

PlY -V-1X-2
Mix:m A A
pi -1x11-- 2)
threshold 0.5 A,
Relative Signal Strangtt
Frobability
Figure Illustration of relative signal strength for binary classification. Left: clean and noisy posteriors [n(=)]] P (Y 1|X = x) and [7(=]] P 1|X z)). Right: relative signal strength corresponding these posteriors. The gray region, E (0, 5), is where the true and noisy Bayes classifiers differ, and also the zero signal region X' Ay. The red region is Ao.4. where the RSS is > 0.4. Note that t 0, Ma; v, 7) co, which occurs since [n(x)]] t 1/2, while [?] is far from 1/2. For = 0+, the predicted labels under and disagree, and the RSS crashes to O.
Upper and lower bounds
In this section, we establish both upper and lower bounds for excess risk under multi-class instance- dependent label noise.
5.1 Minimax lower bound
Our first theorem reveals a fundamental limit: no classífier trained using noisy data can surpass the constraints imposed by relative signal strength minimax sense. state the theorem, we employ
the following notation and terminology. Denote the noisy training data by 2 {Xx, Y))) iidd
P A learning rule is an algorithm that takes 2" and outputs a classifier. The risk R(f) of learning rule random variable, where the randomness is due the draw Z".
Theorem (Minimax Lower Bound) Letc [0, 1], > 0. Then
R (f) -R())
K -
1 1.
inf sup f (Px..)))
Ez-
K
+
V
where the inf 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 (A') (A'),A.))) learning is difficult if not impossible, and the learner incurs an irreducible error of (1 - 1/ c. On the high RSS region (A.,), the standard nonparametric rate (Devroye et al. 1996) is scaled by 1/k. These aspects determine fundamental limits that no classifier trained only on noisy data can overcome without additional assumptions.
5.2 Upper bound
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, potentially surprising result given that NI-ERM is arguably the simplest approach one might consider. We begin by presenting general result on the excess risk of any classifier, which is proved in Appendix A.2.4
5

---

Lemma (Oracle Inequality) For any label noise problem (Px, 17 and any classifier f.
Px (xx An (17 (n. 1 (i
R() - R(F) S inf 630
For (Px. 77. 77) k),, the first term is bounded by e. When f is selected by ERM over the noisy training data, conventional learning theory implies bound on the second term. This leads to the following upper bound for NI-ERM, whose proof is in Appendix A.225
Theorem (Excess Risk Upper Bound of NI-ERM) Let E [0.1], KE > O. Consider any (Px, n, 7 E K)),, assume function class F has Natarajan dimension V, and the noisy Bayes classifier fr belongs F. Let f F be the ERM trained on z {(X,, Y.) i.e. f f= arg min D (1(x.))8)) Then JEF
Ezn ( (
V k
1
Ô denotes big-O notation ignoring logarithmic factors. The Natarajan dimension is multiclass analogue of the VC dimension. The upper bound in Theorem 2 aligns with the minimax lower bound (Theorem D in both terms. For the irreducible error c, there is 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 AA is not provided to NI-ERM. If AA,. were known to the learner (an unrealistic assumption), then mixed strategy that preforms NI-ERM A, and randomly guesses on X \ A. would have an upper bound with first term of (1 1/Ke,, 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 standard outcome in learning theory.
This result 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.
5.3 A smooth margin-condition on the relative signal strength
The previous sections have analyzed learning with label noise over the class II(c, ((Px. n, n) Px 2 1 - e). Now, the set X \ A. equals (X' \\ Ao) U (Ao \ 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 region where these match, but the RSS is small. Naturally, while Px (2' \ An) must be incurred as an irreducible error, one may question why the class II also limits the mass of Ao Ar. After all, with enough data, the optimal prediction in this region can be learned.
This issue would be resolved if there existed a Ko > 0 such that (x()A)) = (x.())) i.e., if Px (Ao A = 0. In fact, our lower bound from Theorem uses precisely such a construction. An interesting point of comparison to this condition lies in Massart' hard-margin condition from standard supervised learning theory, which, for binary problems, demands that Px (1 ([[r(=)]]
[n(x)22] < h) = 0 for some h 0, under which one obtains minimax excess risk bounds of O(V/na) [Massart and Nédélec 2006). With this lens, we can view the condition (x \ \Am,)) = 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) [004].
Definition 2 A triple (Px, n, 7 satisfies an (e, -mm-sh relative signal margin condition with e [0, 1]. a > 0, C. > if
VK > O,
S k) Cak +e.
Further, we define II' ax, C.) as the set of triples (Px, n. 9) that satisfy an (e, a, -mooth relative signal margin condition.
We show in Appendix A.2.7 that the techniques of Section 5.2 yield the following result for 11'.

---

Theorem 3 Let e E [0.1]. > O,Ca > 0. Consider any 7P.. E aT, Ca), assume function class FF has Natarajan dimension V, and the noisy Bayes classifier f belongs to F. Let f E F be the ERM trained T X)) Then
SEt inf Can" +6 Conn+ xz0
(2(21)) (0/
E R (f) (D((R()) -
e 0 -a/1(22-2)
Compared to Theorem 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, s. The advantage of the smooth relative margin is that the irreducible term in the above theorem is exactly Px An), 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 a, and to the optimal x. for each value of a, as a consequence the oracle inequality of Lemma
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 funetion 7 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 immunity
The 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 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 Ax S Ao as stated in Proposition [ This not only explains past empirical successes, but also gives 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 Ao = X. These conditions are linear algebraic conditions on E that ensure arg max (2x) arg max 77 (z). 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 (Px, n7 7 is immune to label noise if Va E X, arg max (1x)) = arg max (z))
Notice that due to Proposition]] D if problem is immune, then Ag = X. We now provide necessary and sufficient conditions noise transition matrix E that ensure noise immunity. We begin by considering distribution Px with zero Bayes risk, that is, where n is one-hot almost surely. A matrix defined as diagonally dominant if, for each row, the diagonal element the unique maximum.
Theorem 4 (Immunity for Zero-error Distribution) If Pxy has Bayes risk of zero, then immunity holds if and only if for all x, the noise transition matrix E(x) diagonally dominant.
Remark For a zero-error distribution Pxy. even corrupted with instance-depender label noise, achieving the Bayes risk is still feasible with a noise rate P(Y + YY up to K-1 This highlights that K 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 Pxy. 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 Pxy, immunity holds
1 +
c(x)
i= i
Be(z) > O.S. Vr E X, E E(x))as
K
e(x)
j.
K
K

---

Binary
10-class
0.8
0.8
The rationale behind the necessity of E(x) taking this specific form that it redistributes the probability mass of 7 in "uniform" manner. This constraint arises because E(z) cannot favor any for some Testing Accuracy
Testing Accuracy
0.6
0.6
0.4
0.2
0.2
Linear Theory
2-layer CNN
Theary
0.1
0.6
0.2
0.6
0.8
Noise Rate
Noise Rate
(a) Logistic regression trained on 2D gaussian mix- ture data with different levels of symmetric noise
(b) 2-layer CNN trained on MNIST with different levels of symmetric noise
Figure 2: Data simulation that verifies noise immunity. For binary, the turning point is at noise rate
P(Y * Y) = 0.5. For 10-class, the turning point is at PY * Y) 0.9.
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 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, Furthermore, this transition is abrupt: when P(Y * Y) K-1
K
K
Ao = X, but when (Y # Y) 2 K-1 Ao = 0. Consequently, we expect to see a sudden drop in performance when noise rate passes the threshold.
K
classes besides the true class. For instance, consider (xx) = [ + K - K K.
small 8 > 0, a non-uniform" ((x) would alter the arg max.
The above theorems demonstrate that signal strength at æ 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 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 wear-Bayes risk performance until a certain noise threshold is reached, beyond which the testing performance sharply deteriorates.
Practical implication
The modern practice of machine learning often involves training deep neural network. In complex tasks involving noisy labels, the naïve NI-ERM is often outperformed by state-of-the-art methods by significant extent [Li et al.) 2020 Xiao 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'.
1. Perform feature extraction using any method (e.g., transfer learning or self-supervised learning) that does not require labels.
2. Learn a simple classifier (e.g., a linear classifier) on top of these extracted features, using the noisily labelled data, in noisc-ignorant way.

---

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 simple model (step 2) noisy data, which we observed in F 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 al. [022], 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 experiments oon 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-superrvsed ResNet-50 using contrastive loss
(Chen et al. 2020]. We also compared to a simple linear model trained on the raw pixel intensities, and ResNet-Si 50 trained end-to-end, We observed that ResNet--0 exhibits degrading performance with increasing noise, consistent with previous findings (Zhang et al. 202 la Mallinar et al. 2022). The linear model demonstrates robustness noise, but suffers from significant approximation error.
Synthetic Label Error
Human I Label Frror
0.8
0.8
Accuracy
Test Accuracy
0.6
0.6
0.4
0.1
Lineer + DINOW2 SS1.
Linesr + DINOw2 SSI.
0.2
-
Lineur ResNet--0 55 SSL
Linear ResNet 50 TL
0.2
Linear+ ResNett50 551,
Linear ResNet 50 TL
Linear Model
Linear Model
ReaNet:50 50
ReaNet 50
0
0.2
0.4
0.6
0.8
0
0.2
0.4
0.6
0.8
Noise Rate
Noise Rate
(a) CIFAR- 10 with synthetic label noise
(b) CIFAR-10 with realistic label noise
Figure 3: A linear model trained on features obtained from either transfer learning (pretrained ResNet-50 on ImageNet [He et al. 20166) ). self-supervised learning (ResNet-50 trained on CIFAR-10 10 images with contrastive loss [Chen et al. 20200), or a pretrained self-supervised foundation model DINOv2 [Qquab 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 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 WWii 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- ION and -OFAR-IOON benchmarks, across the noise levels, as shown in Table
We emphasize that the only hyperparameters of our model are the hyperparameters of the linear classi- fier, which are tuned automatically using standard cross- gross-validation on the noisy labels. This contrasts to the implementation of many methods on the CIFAR-N leaderboard
com/)
'Code is available at: http::////shuub..ommmlllaaaas
_ignoranceeeeeee

---

where the hyperparameters are hard-coded. Furthermore, our approach does not rely on data aug- mentation. Additional experiments, detailed in Appendix A..4. include comparisons with the 'linear probing, then fine-tuning' approach [Kumar 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 I: Performance comparison with CIFAR-N leaderboard (nttp://noissylabele com/) in terms of testing accuracy. "Aggre", "Randl", ..... "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 al., 2023], ILL [Chen al.) 2023 PLS [Albert 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 of-thh-art results, highlighted in bold. We employed Python's 's sklearn logistic regression and cross cross-validation functions without data augmentation; the results are deterministic and directly reproducible.
Leaderboard
CIFAR-ION
CIFAR-100
Methods
Aggre
Rand
Rand2
Rand3
Worst
Noisy
ProMix
97.65 = 0.19
97.39 + 0.16
97.55 + 0.12
97.52 + 0.09
96.34 + 0.23
73.79 + 0.28
ILL
96.40 = 0.03
96.06 + 0.07
95.98 + 0.12
96.10 + 0.05
93.55 + 0.14
68.07 + 0.33
PLS
96.09 = 0.09
95.86 + 0.26
95.96 + 0.16
96.10 + 0.07
93.78
+: 0.30
73.25 + 0.12
DivideMix
95.01 + 0.71
95.16 + 0.19
95.23 + 0.07
95.21 + 0.14
92.56 + 0
71.13 + 0.48
FE + NI-ERM
98.69 - 0.00
98.80 0.00
98.65
0.00
98.67 + 0.00
95.71 + 0.00
83.17 + 0.00
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 v and
Cos ti- x
PaiMinn ki)
055
Emparical COF
jj. Despite the high overall noise rate CIFAR-ION "Worst" labels, with PPYY
0.-
Y) = 40.21%, we conjecture that the re- gion where there is signal, X' Ao.
covers only small portion of the proba- bility mass < 4%). Furthermore, the cumulative distribution of the estimated RSS can be upper-bounded by a polyno- mial R + c, supporting the validity of the smooth relative signal margin condition introduced in Section 5.33
022
0.
65
Figure Empirical CDF of estimated RSS for CIFAR-
ION, evaluated on test data.
Conclusions
This work presents 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 feature extractor with NI-ERM, demonstrating significant performance enhancements. A limitation of this work is that our methodology warrants more extensive experimental evaluation.
IIf the link is inaccesssille see the May 23, 2024 archive captured by Wayback Machine: httpp:///ve
archive. http:///ww.........aaa//////////
10

---

Acknowledgements
This work was supported in part by the National Science Foundation under award 2008074 and the Department of Defense, Defense Threat Reduction Agency under award HDTRAI 10TTRA1-20-2-000 The authors thank Zixuan Huang. Yihao Xue for helpful discussions and Raj Rao Nadakuditi for feedback during a course project in which some early experiments in this paper were conducted. We also thank the anonymous reviewers for their suggestions, especially the reviewer who provided Example
References
Paul Albert, Eric Arazo, Tarun Krishna, Noel E O'Connor, and Kevin McGuinness. your noise correction noisy? pls: Robustness to label noise with two stage detection. In Proceedings of the IEEE/CVF Winter Conference on Applications of Computer Vision, pages 118-127, 2023.
Dana Angluin and Philip Laird. Learning from noisy examples. Machine learning, 2:343-370, 1988.
Yamini Bansal, Gal Kaplun, and Boaz Barak. For self- learning, rationality implies generalization, provably. In International Conference on Learning Representations, 2021.
Carla E Brodley and Mark A Friedl. Identifying mislabeled training data. Journal of artificial intelligence research, I 11:1311677, 1999.
Tony Cai and Hongji Wei. Transfer learning for nonparametric classification: Minimax rate and adaptive classifier. The Annals of Statistics, 49(1):100-128, 2021.
Timothy Cannings, Yingying Fan, and Richard J Samworth. Classification with imperfect training labels. Biometrika, (0722)311-330) 2020.
Hao Chen, Ankit Shah, Jindong Wang, Ran Tao, Yidong Wang, Xing Xie, Masashi Sugiyama, Rita Singh, and Bhiksha Raj. Imprecise label learning: A unified framework for learning with various imprecise label configurations. arXiv preprint arXiv:2305.12715. 2023.
Ting Chen, Simon Kornblith, Mohammad Norouzi, and Geoffrey Hinton. A simple framework for contrastive learning of visual representations, In International conference on machine learning, pages 1597-1607. PMLR, 2020.
Hao Cheng, Zhaowei Zhu, Xingyu Li, Yifei Gong, Xing Sun, and Yang Liu. Learning with instance- dependent label noise: A sample sieve approach. In International Conference Learning
Representations, 2021.
Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei. Imagenet: A large-scale scale- hierarchical image database. In 2009 IEEE conference on computer vision and pattern recognition, pages 248-255 IEEE, 2009.
Luc Devroye, László Györfi, and Gabor Lugosi. Probabilistic Theory of Pattern Recognition, volume 31. Springer, 1996.
Pierre Foret, Ariel Kleiner, Hossein Mobahi, and Behnam Neyshabur. Sharpness-aware minimization for efficiently improving generalization. In International Conference on Learning Representations, 2021. URL
Aritra Ghosh and Himanshu Kumar. Robust loss functions under label noise for deep neural networks. In Proceedings of the AAAI conference on artificial intelligence, 2017.
Aritra Ghosh and Andrew Lan. Contrastive learning improves model robustness under label noise. In Proceedings of the IEEE/CVF Conference Computer Vision and Pattern Recognition, pages 2703-2708, 2021.
Aritra Ghosh, Naresh Manwani, and PS Sastry. Making risk minimization tolerant to label noise. Neurocomputing, 160:93-107, 2015.

---

Bo Han, Quanming Yao, Xingrui Yu, Gang Niu, Miao Xu, Weihua Hu, Ivor Tsang, and Masashi Sugiyama. Co-teaching: Robust training of deep neural networks with extremely noisy labels. Advances in neural information processing systems, 31, 2018.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition. pages 770-778, 2016.
Wei Hu, Zhiyuan Li, and Dingli Yu. Simple and effective regularization methods for training on noisily labeled data with generalization guarantee. In International Conference Learning Representations, 2020.
Hyungki Im and Paul Grigas. Binary classification with instance and label dependent label noise. arXiv preprint arXiv:2306.03402, 2023.
Ananya Kumar, Aditi Raghunathan, Robbie Jones, Tengyu Ma, and Percy Liang, Fine-tuning can distort pretrained features and underperform out-of-distribution. International Conference on Learning Representations, 2022.
Junnan Li, Richard Socher, and Steven CH Hoi. Dividemix: Learning with noisy labels semi- supervised learning. In International Conference on Learning Representations, 2020.
Jiashuo Liu, Tianyu Wang, Peng Cui, and Hongseok Namkoong. On the need for language describing distribution shifts: Illustrations on tabular datasets. Advances in Neural Information Processing Systems, 36, 2024.
Sheng Liu, Jonathan Niles-Weed, Narges Razavian, and Carlos Fernandez-Granda, Early-learning regularization prevents memorization of noisy labels. Advances in neural information processing systems, 33:20331-2033 2020.
Sheng Liu, Zhihui Zhu, Qing Qu, and Chong You. Robust training under label noise by over- parameterization. In International Conference on Machine Learning, pages 14153-14172. PMLR, 2022.
Tongliang Liu and Dacheng Tao. Classification with noisy labels by importance reweighting. IEEE Transactions pattern analysis and machine intelligence, 38(3):447 461, 2015.
Yang Liu and Hongyi Guo. Peer loss functions: Learning from noisy labels without knowing noise rates. In International conference on machine learning, pages 6226-6236. PMLR, 2020.
Jianhao Ma and Salar Fattahi. Blessing of depth in linear regression: Deeper models have flatter landscape around the true solution. Advances Neural Information Processing Systems, 35: 34334-34346, 2022.
Subha Maity, Diptavo Dutta, Jonathan Terhorst, Yuekai Sun, and Moulinath Banerjee. A linear adjustment based approach to posterior drift in transfer learning. Biometrika, 2023, URL https //doi.org/10. 1093 wttt:////tt//aaeeeeee/eeeeeeeeee asad029
Neil Mallinar, James Simon, Amirhesam Abedsoltan, Parthe Pandit, Misha Belkin, and Preetum Nakkiran. Benign, tempered, or catastrophic: Toward refined taxonomy of overfitting. Advances in Neural Information Processing Systems, 35:1 111111291155 2022.
Pascal Massart and Élodie Nédélec, Risk bounds for statistical learning. The Annals of Statistics, 34 (5):2326-23) 2366, 2006.
Aditya Menon, Brendan Van Rooyen, Cheng Soon Ong, and Bob Williamson. Learning from corrupted binary labels via closs-probabilityy estimation. In International conference on machine learning, pages 125-134. PMLR, 2015.
Aditya Krishna Menon, Brendan Van Rooyen, and Nagarajan Natarajan. Learning from binary labels with instance-dependent noise. Machine Learning, 107:1561-1595, 2018.
Balas K Natarajan. On learning sets and functions. Machine Learning, 4:67-97, 1989.
12

---

Nagarajan Natarajan, Inderjit S Dhillon, Pradeep K Ravikumar, and Ambuj Tewari. Learning with noisy labels. Advances neural information processing systems, 26, 2013.
Curtis Northeutt, Lu Jiang, and Isaac Chuang. Confident learning: Estimating uncertainty in dataset labels. Journal of Artificial Intelligence Research, 70:1373-1411, 2021.
Maxime Oquab, Timothée Darcet, Théo Moutakanni, Huy V Vo, Mare Szafraniec, Vasil Khalidov, Pierre Fernandez, Daniel HAZIZA, Francisco Massa, Alaacldin El-Nouby, et al. Dinov2: Learning robust visual features without supervision. Transactions Machine Learning Research, 2023.
Diane Oyen, Michal Kucer, Nicolas Hengartner, and Har Simrat Singh. Robustness to label noise depends on the shape of the noise distribution. Advances in Neural Information Processing Systems, 2022.
Giorgio Patrini, Alessandro Rozza, Aditya Krishna Menon, Richard Nock, and Lizhen Qu Making deep neural networks robust to label noise: A loss correction approach. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 1944-1952, 2017.
Clayton Scott. A generalized Seyman-PPeason criterion for optimal domain adaptation. In Algorithmic Learning Theory, pages 738-761. PMLR, 2019.
Clayton Scott, Gilles Blanchard, and Gregory Handy. Classification with asymmetric label noise: Consistency and maximal denoising. In Conference on learning theory, pages 489-511. PMLR, 2013.
Alexander B Tsybakov. Optimal aggregation of classifiers in statistical learning. The Annals of Statistics, 32(1): 166,, 2004.
Brendan Van Rooyen and Robert Williamson. A theory of learning with corrupted labels. Journal of Machine Learning Research, 18(228):1-50, 2018.
V. N. Vapnik and A. Ya. Chervonenkis. On the uniform convergence of relative frequencies of events to their probabilities. Theury of Probubility Its Applicutions, 16(2):264-280, 1971. doi: 10.1137/1 16025. URL http:pp:://....rg//1.11.1111 1117/11111117/110025
Jialu Wang, Eric Xin Wang, and Yang Liu. Estimating instance-dependen label-noise transition matrix using a deep neural network. International Conference on Machine Learning. 2022.
Jiaheng Wei, Zhaowei Zhu, Hao Cheng, Tongliang Liu, Gang Niu, and Yang Liu. Learning with noisy labels revisited: A study using real-world human annotations. In International Conference on Learning Representations, 2022.
Xiaobo Xia, Tongliang Liu, Bo Han, Nannan Wang. Mingming Gong, Haifeng Liu, Gang Niu, Dacheng Tao, and Masashi Sugiyama. Part-dependent label noise: Towards dependet label noise. Advances in Neural Information Processing Systems, 33:7597-7610, 2020.
Ruixuan Xiao, Yiwen Dong, Haobo Wang, Lei Feng, Runze Wu, Gang Chen, and Junbo Zhao Promix: Combating label noise via maximizing clean sample utility. In Edith Elkind, editor. Proceedings of the Thirty-Second International Joint Conference on Artificial Intelligence, IJCAI- 23, pages 1442-4450. International Joint Conferences on Artificial Intelligence Organization, 2023. doi: 10. 2224963/jcaii
URL https://doi. htll//ii.oogggg// 10. 114963/ijcai. /t0.://3//caa..223/4444444
Main Track.
Yihao Xue, Kyle Whitecross, and Baharan Mirzasolciman. Investigating why contrastive learning benefits robustness against label noise. In International Conference on Machine Learning, pages 24851-24871. PMLR, 2022.
Shuo Yang, Songhua Wu, Erkun Yang, Bo Han, Yang Liu, Min Xu, Gang Niu, and Tongliang Liu. A parametrical model for instance-dependent label noise. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2023.
Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning (still) requires rethinking generalization. Communications of the ACM, 64(3):107-115, 2021a.
13

---

Jianxin Zhang, Yutong Wang, and Clayton Scott. Learning from label proportions by learning with label noise. Advances in Neural Information Processing Systems, 35:26933-2666 269422, 2022.
Mingyuan Zhang, Jane Lee, and Shivani Agarwal. Learning from noisy labels with no change to the training process. In International Conference Machine Learning, pages 12468-12478, PMLR, 2021b.
Evgenii Zheltomozhskii, Chaim Baskin, Avi Mendelson, Alex M Bronstein, and Or Litany. Contrast to divide: Self-super pre- tre-training for learning with noisy labels. In Proceedings of the IEEE/CVF Winter Conference on Applications of Computer Vision, pages 1657-1667, 2022.
Zhaowei Zhu, Tongliang Liu, and Yang Liu. A second-order approach learning with instance- dependent label noise. In Proceedings of the IEEE/CVF conference computer vision and pattern recognition, pages 101 10113-10123, 2021.
14

---

A Appendix supplemental material
A.1 Equivalence of noise fransition and domain adaptation perspectives
The noise transition perspective models the joint distribution of (X,Y, Y), which can be characterized as:
Px, = Px Prix Prrxx
E
Thus, by specifying Px. 17, and E, we obtain a triple (Px, 7. 17) with r7x)) = E(x) (2)). In contrast, the domain adaptation perspective views label noise problems directly as triple (Px, 17, 77, 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 (Px,7) 17. 7), we can always define a noise transition matrix as:
(xx) 17
where = ........ We can verify that E is row-stochastic, and
î = E(x) (11 T )n - 77 17) = rj
Therefore, these two perspectives are equivalent.
A.2 Proofs
A.2.1
Proof of Proposition
Proposition
Ao(n, 7) {x X' arg max ?7x)) S arg max m)x)).
Proof. Notice that
M( 77 =
arg max (7xx) g arg max (zx).
This is because M(1; n, 7 0 when the numerator is and the denominator is non-zero, which happens when arg max 7xx) L arg max (xx)
An equivalent statement of this is
M(nn..) 00
arg max 7)x) arg max (x).
A.2.2 Proof of Proposition 2
Proposition In the binary setting. for K 2 0.
T(x) 0
and As 7) { E
X: 75x)
M(I; n, 7)) max
T(x) I
7(x)
Proof. In a brute-force way, we can examine the nine cases where 17(x), 77(2)) is greater, equal, or smaller than 1/2.
15

---

If f7x) > (()) > 2. then
max;(ū(x)) (1)
M(
min JEY max; (T)]]
(T))
7)x)) (1 77(x))
712) (1 (7)))
7)x))
(())
71z))
max
(7
If ff)()) 3. n()) 1. the same argument holds.
If (f)) ()) 1 or π()) < nxx))
1. take arg max (2x), we have
max; (+)=); [
M( .) = min
yey
max; [x)]] (x)]
=0
7(xx)
= max
0
(1(2)
If ()x) = 1.1 n(x) < or f(x)) = n1x) < 2, take j # arg max (2),, we have
max; [Txx)) - [7({)]}
M(x: .7 = min jey
max; [n(x)]; [m)(
0
7(x)
max
(1(x) 1 0
If nz(x) 1.4 then
max, max.(7(x)) m
(-)) }}
M(x; n.
min jEy
max, [n(x)], (n)
max (2))] [m
Vj
+00
[)x))
max
0
(1(x))
Note that it makes sense for RSS to be +00 when 17(x) = 2. because in this case, clean excess risk R(f) R(f*) 0 at point æ for any classifier.
Therefore, we can conclude that
7(x) 2
M(z:n.i) = max
(1((x)
by definition, have, for 2 0
An fx X MMx n, s}}
π(z) 1
= x E X
n(z) > K
16

---

A.2.3 Proof of lower bound:
Theorem 1
Now we provide more formal statement of the minimax lower bound and its proof. We begin with the scenario where the noisy distribution xx has zero Bayes risk as an introductory example. The proof for the general case follows similar strategy but involves more complex bounding techniques. We recommend that interested readers first review the proof of the zero-error version to build solid understanding before tackling the general case.
Now consider a more restricted subset of 11(E, K):
[I(e, K. V,0) :- (Px. (
Px (An (n, (n. 2 11-E,Ps supported on V + points, R² = =0}.
Theorem (Minimax Lower Bound: when Rt = 0) Lete E [0, k > 0, V > 1. For any learning
rule f based upon z" (xX,, and n max(V 1,2),
E R [R({)(
Ez R (f) R(F*
sup (Px.n (Px.e.)))TT(e..)))
2
sup
(Px (.......
K
(V
1)( -
K
6
8en
Proof.
We will construct triple (Px, m, 77) that is parameterized by j, b 161 b2 ... -v- and
First, define Px. Pick any V + distinct points zu. ,
x To
Px(x) (1 c) n
........ -V-
c) V=1)
I TV.
this is where need the condition that > V 1.
Then, define the clean and noisy class posteriors:
f To. then (xx) = C,, 7)x) c1 j (1.2....1) K}
(2)
b-1
2
(-1)
2
If 24, 1stsV then 77x)
0
7(xx) = eb, be E [1,2],6 0,
0
(3)
2(x+o]
x = zv, then (7x)) =
((x)) C1:
(4)
where e; denotes the one-hot vector whose i-th element is one.
The triple (Px, 17, 7 is thus parameterized by j, b [6, by 6v-1] and 6. This construction ensures (Px, m7 77 E II(E; K, V,O). In particular,
Ax 2 (I1, "2..,, Jy
Px(Aw) 2 -6, Px AA))) Se,
X' \ A. S {zo}.
and Rº = because 7xx) is hot for all æ.
17

---

For any classifier f. by definition, its risk equals
R() = Ex,y [[x)x]]
Ex ( ((x)x)]
Ex - s(x)=]
Ex [1 [x())
/ (1- (n())))(()) dx)
Therefore, the Bayes risk and excess risk equal
R( inf Ex, [[x]a]]
= =/x (1- (1-max((z) dP
/ -n(x)())-((=))150))) dPx (z).
R(f) - R(f*)
Under our construction of Px. R(f) can be decomposed into two parts
R())
(1 - (=) dPx(x)
(1 (1- (m(()()))) dPx(x))
120b
Ra(h)
:FR(()
and so can the excess risk
R(f) R(f)) = [Ro - Ro(f*) [Ry (f) (f) - Rv(f*)
= (maxn())- [n(x))s())) dPx(x)
120}
+
max
(n (m()))(()) dPx (x).
(
Recall that in construction, (Px, 17, 97) is parameterized by j, b, and 6. Therefore
sup (Px (.x.
Ez-
R f R({*)]
2 sup Ez.
R f R(F*)
j.b.8
Ezn
Ru f Ro(f*)
sup
5.b,8
Rv (f) Rv(f*) }
Ez
sup Ezn
Ro
( Ro(s*)
Ry (f) (r((()
sup
Ez-
6,8
where the last equality holds because region {ro} only depends on j. while region {Ii...., only depends on b, 8.
In the remaining part of the proof, we will examine
Ra (f) Ro(
sup
Ez-
(5)
i
and
sup Ezn b,d
Ry (f - Rv(f*)
(6)
18

---

separately.
Let's start with the first term {zo}. Since is one-hot on jooh its Bayes risk over that is zero
5p. which reflects the excess risk over the "low signal strength" region
sup Z Ro (f) Ro(S")
sup 1z Ro (f)
= sup Ezn
(mo)
To deal with sup,, we use technique called "the probabilistic method" replace j with a random variable
Devroye et al.
1996]:
sup Ezz Von [10)ss [
2 EB,
Ez-1
E,,, zn [ fool
1 (1ssadP((()))
( (100)
Egn
Bujzz
1 d
Again, notice that // is an independent draw. Even if the point xo is observed in 2", the associated noisy label = 1 does not give any information about the clean label Y = J. Thus
E 2
E B
Ez
E,
1 )
(0o)
(20)
J Es
Ez
[ dPx(x))
(zo)
/ (zo)
(1
1
dPx(cs)
Ezn
K
(1
K
Now we have the minimax lower bound for the first part (5)
[e (f) R(zox(()))
1 K
sup Ezz
>
1
For the second part 66. which over (.1,..., J. due to the relative signal strength condition, and from explicit construction in Equ. 3 and (4), the excess risks w.r.t. true and noisy distribution are related by
RV -v = (mimaay)
maxx(()) - (m(x))(()) dPx(x)
(aimaay)) K+8 (max (xx) - ((o))) dPx(x) by construction of n. 7
[Rv(f)- - -kv
where Rf( = (qn.....v) (1 (()))))))))))))))) dPx(x). Also note that f*(x) = f=(xx for x e (zy which a result of our construction of 17. 77.
Then
Ry (f) - Ry = sup Ezn b,d
(arl))rr((ft))
sup Ez"
K + 8
19

---

This allows us to reduce the label noise problem to standard learning problem: we have an iid sample T from px and consider the risk evaluated on the same distribution Px Pxy- The remainder of the proof is similar to the proof of Devroye et al. [196 Theorem 14.1].
Notice that by our construction, Y is a deterministic function of X. To be specific, Y = (X), where
1 T = Jo
(x)
bt Ft. 1 V-1
1 F. IV
is the noisy Bayes classifier.
We use the shorthand fo := f to denote that the noisy Bayes classifier depends on b.
Since the noisy Bayes risk is zero,
sup E2n
1
(Rr(f) Rv((t))
sup b,6
1 x 8
Bzn
[Rv(f]
b,8
Again, use the probabilistic method, replace b with Uniform
1123
1
[v((N] 2 sup
[Rv(A]]
sup
Ez-
EB,2
b,6
5
K +
Veen 1 1 dPx(x)
sup
Ezn
BBIz"
K K
Since we have B ~ Uniform 2], 2 and also Z" B ~ ppn then by Bayes rule (or eye-balling, since 7j is one-hot), we get the posterior distribution of B 7", be specific: Vz {x1," ,IV;, }.
n). Ir= X (1, .1,,
then (fB(x) = Y,(z") = 1, IP
# ( =
If = RV. then P(]((r) = 1|2") = P(s((x) = 2|2")
I & (X.....
Nv, then P(fn(r) = 1[2") = 1.2 (f)((x)) = 2") = 1
2'
where we overload the notation to denote conditional probability of B
Then the optimal decision rule for predicting B based sample Z" is:
Y 1
Xt,i i E 11,2....,7.
g(0; Zm)=
Zy
random guess from (1,2) r # Xi....,
x + Xn, x # IV.
20

---

Therefore, the error comes from the probability of X E {æ1...., vv not being one of the observed X;: for any f.
V
E
[Rv[f)]
1m
BB| 2
1 / 1n Px
2 (XX E {ai,...,vV), (") # fB(X))
eeroo of 2 error of g
1 P X # X X # IV, X E (v1))..,
P(X # X1 X + Xn, X + σV, X =x²)
P(1 * Tt....,, Xn +
TV # 2t, X =x²)
''replace all X with Te
P( + r ,,
* , = zt)
= 2
(x # Ir. I,.,..,,,,, Xn = = x1)
Σ
P( =xx))) P(X xz)
t=1
(1- 1 1-6 -
(V
11
n
(V 1)(1 ct)
2n
n
(V 1)(1 c)
1-c
- c
n-1-E
1
2n
n
n
(V 1)(1 - c)
6
-1+
(1- 1-E n-1-c
t 1
2n
(V 1)(1 c)
1
2
1 [0,1]
2n
n
(V 1)(1 c) -1
(V
1)(1
c)
take n > 2.
2n
4
8en
Now we get the minimax risk for the second part 6
RA. (f) -RAA(())
(V - 1)(1 c)
sup
Ez-
2 sup 8
6,
K +
Sen
1)(1
let 4
8en
Combine the two parts together, we get the final result, for n > max(V V 1,2)
R (f( --(-)]
K K
(V - 1) c)
sup V...
Ezn
2
8en
21

---

As for the general version of the lower bound, now consider the set of triples:
I1( V,L) = (Px,7. {
:Px (An (n,1)) 2 11-6.
RA, (fr)
Px supported on V points,
S St.j..
Px An (n. 7))
where Rc(f) = (1- dxx(
Theorem (Minimax Lower Bound (General Version)) Lete E 10,11.1 > 0,V 1, E (0, 1/2).
For any learning rule f based upon Z {f {X,, I for n 2 2L
V-1 max { (16, [1-2 }
sup (Px (.)...)
Ezz
R ())-)((()
2
Ezn
[ [R(F) R(S*)
K-1 1
1-
(V
-1)L
1)L 6
c+
K
K
2n
K
1
6 6+ Ω
K
n
Proof.
Now we construct triple (Px, m7. 7) that is parameterized by j, b. = [b by ... -v- 5, and
First, define Px. Pick any V + distinct points wn; ,1,
(x(x)
(1 .
Il.... 2V-1
(1 c). (1 (1- (V 1)p) x = .V.
This imposes the constraint (V - 1)p s 1, which will be satisfied in the end. Notice the differ- ence compared to the previous zero-error proof: we place probability mass p. rather than 1/n, on
Ti. JI....,Zy-I -V-
As for the clean and noisy class probabilities, choose
If x To, then (xx) = Cjj 7ix) = c1;
j (1, k}
7 + xto
(-1) b-1)
+ c
(- 12
i
1
1
2 x+8
If = 2r, 15 2 V
- V-
then (x))- =
0
7(xx)
0
(0. 1
by E {1,2}, > O, CE
(0:5)
(8)
2
+ 2))
2[x+o]
x = zV, then 17(x) =
O
77x))= = C1+
(9)
where e; denotes the one-hot vector whose i-th element is one.
The construction for class posterior is also similar the previous proof, except that for
Jt,4 l E (1,..., V - -1), 7 is no longer a one-hot vector, rather has class probability separated by 2c: ()))], - [7] 2c.
22

---

Therefore, the triple (Px, 17) can be parameterized by j. == [bg b2 -v 6. and p.
Again, this construction ensures (Px; 7) (T(,, ki), to be specific:
Ax 2 (2..,
Px(A,) 2 -1 Px(2 An) S..
X' Aw S {zo),
For any classifier f, its risk can be decomposed into two parts
R()) (1-(m(=))so)) dxx(x)+
(1 (1-1n(=)1s(s) dPx(2)
(20}
Ro(())
=Rv((
as can its excess risk
(Ro (f) Ro(f)) + (Rv (Rv(F) (F())))
R
In our construction, (Px, 17, 77) parameterized by j. b= [bi b2 ... by- 8, e cand p. therefore
R (f) -R(F)) 2 sup Ezn Ro (f) - -Ro(f*)
sup (...
Ezn
(10)
x + (Rv(f)) - -Rr (11)
1
sup Ez
b,8,0p
Note that we have used the fact that
Rv Rv(f-) k6 k
where Rv(s): [ (1 (())) dPx(x)).
The first part (10) is exactly the same as in the zero-error proof, and we have
Ezn Ro (f) Ro((t) 2 -1- K
sup
From this point forward, the procedure similar to the proof of Devroye et al. 1996 Theorem 14.5]. For the second part (II), the noisy Bayes classifier still
j I Fu. b Ft, 1St5V x TV.
(x)
We also use the shorthand So = f to denote that the noisy Bayes classifier depends on Now the noisy Bayes risk is no longer zero. In fact
Rv( 1
(e (1 (())) dPx()) (V (1)( -c)p (--21-0 -
What's more.
RA (F*)
Ry(s²)
(1-).
2 -c).
S
(V 1)p
(12)
Px Av (17.77 77
Px (x11...,
where the inequality holds from RA, (fr) = (f*) (because v is one-hot at point mp) and
Px Ax (n. (1.7) 2 Px (k
23

---

Notice that in order to ensure that our construction (Px. 1)
II(e, NG V, L, by definition
RA. (f*)
S L,
Px An (1.
Due to the upper bound of (12). it suffices to require that
(V - 1)p -0) L,
(13)
and this ensures that (Px, 77 7) E [I((E K, V, L) upon recalling that (Px, 97 9) E [[(e, K), and that Px is supported on + points.
should be noted that since (V - 1))p < is required, and since e 0, we have L. < 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( 1/2) instead. In any case, we are left with two nontrivial constraint on
our parameters (p, c): (33 and (V 1)p s along with the boundary consraints p E [0, 1] and
E [0, 1/2].
For fixed b, plugging in the definition of the excess risk over region (.1,,-., becomes
2c1
V-1
2c (1- f(m))toa))))))
where the inequality follows from the fact that we ignore the risk on point rv.
Using the probabilistic method, replace b with B ~ Uniform [1, 11,3V=1
Ezn (Rv
1 k d
Rv(()))] -
1 (Rv(() Rv((*))
sup b.d.e,p
> sup 8.c.p
EB,
K K 5
1
EBI2" [(Vv(() Ry (Rv
sup s.c.p
Ezn
+
Now, we need to calculate Z!Z", which can calculated using Bayes rule because we have B 21 and also z" B
psn XY
To be specific, for any x fro, Z1.... xv vv- 2v.., sample Z
assume point 2; is observed times in training
I X1 .1.....22 2 # Xn. x # IV IP (B, Iy....... Y.)) x 2, Xx,
((]B(z)= 1|
X.,, 1 1stsv-
where B, denotes the t-th element of vector B (that associates with .it).
Next we compute IP (B, = 1 V1....., Yv = yk) for y1, y1..... M/k E {1, 21. Denote the numbers
of ones and twos by h {j < k Vo 13 and K2 H6 < k y 2) Using Bayes rule, we get
P (B. = 10y InY Yoa)
P P(B.
Yr.)
PY Vr.)
P PY ......,,,,, = P) ((p =)
1r
Ei_ PY,....,.,. = :B)
(1/2-
24

---

After some calculation, following the proof of Devroye et al.
1996 Theorem 14.5], we get
1
(F) - RA. Rf)(
sup 2
b,6.c.p
K K 8
1
An(1-r)pp2 1-26
4cyn/1-ele 1-26
sup
+ c(V 1)) c)pe
6,c.p
1
Smpe?
seu/pp
sup
c(V 1)pe
1-26
1-26
T' 2
take 8 0
cp
1-6
L
Sauc2 1-26
4cy/p
sup
C
1-20
13
(14)
1/2
cpp
where the supremum is over (p. c) E [0, 1] x [o, 1/2] such that
(V- - 1)p I 1, and (V - 1)p(1/2 - c) = =L.
Now, suppose n is so large that
(V-1)
VV (V-1) 1) - LS 2 8nL
n 2
8L(1/2 - L)3
and further that
VV 1)
1
= nz 8(V - 1)
8nL S 8
We choose
<=v -
(V -1 (V-1) and
L
8nL
(V - 1)(1/2
By our choice of and the first condition on n above, we can conclude that I. S (1/2 c). and therefore,
L
(V 1)p
1/2- 1
meaning that both the constraints required on (p, c) are met by the above choice.
As consequence of this choice of c, observe that n2
nL
(V-1) 1)
1
1
nipe
c² (V 1)(1/2 c)
(V 1)(12 c)
SnT.
3
Since e S 1/8 further implies that
1
I
4 this implies that
I-2c
8npe2
4
npc
8 4
4
I
+
<
+
4.
1 2c
2c
3
3
Thus, instantiating the bound
14
conclude that
sup Ez-
1
(f) - (
1
1-c
V -
L
-7
b.8,e.p
8nL
1/2
1
1)L - -7.2
K
8n
1)L 6 7
K
2n
Putting the two parts together
R (f)
-R(M)]
K
1
1)L
sup (Px (.m)mn) f...)eeeeee....
Ezn
2
E
+
e
K
K
2n
for n > V-1
max 16,
2L
(1-2L)²
25

---

A.2.4 Proof of upper bound: Lemmal
Lemma (Oracle Inequality under Feature-dependent Label Noise) For any (Px, 97 7) and any classifier f, we have
R(J) - R(F) S inf { Ax 1 R ( (
630
Proof. For any x 2 0, the input space X' can be divided into two regions: X' \ Are and A..
For any f. its risk is
R() Ex, [_xxe)]]
Ex Eyix ((x#))
Exj s(x)=]
Ex [1 - [m(X)))(()))
/ (1- [n(x)]s(a)) dx)(x).
Therefore, its excess risk is
R(F) R(F)) = / mmxx)()) (m(=)) ) dPx (x)
( - (n(x)))()))))))) dPx(x)
XMA
maxn(()) ((0)) dPx (x)
Now examine the two terms separately,
@
/ xrde
IdPx(x) Px Ax (n.7).
and
- dPx(x))
: by definition of relative signal strength
An
1
<
mmxx (2x) - (+())) dxx(x)
x K
R(J) R((}))
by definition of R.
Since this works for any O, we then have
Px x Ar (n:7) + (
R() R() inf e50
A.2.5 Proof of upper bound: Theorem
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 NNtaraaan, 1989] which serves as multiclass counterpart to the VC dimension /Vapnik and Chervonenkis 1971].
26

---

Definition 4 (Multiclass Shattering) Let H. be class of functions from X' to ) = (1,2..... K}. For any set containing n distinct elements C₁ = , In C X, denote
Hc,, ((((z)))...,((((,)))) h H),
and therefore [He,l is the number of distinct vectors of length n. that can be realized by functions in H.
The nh shatter coefficient is defined as
S(H, max
IHc..-
Ca
We say that set On is shattered by H if there exists J,g Cn + Y such that for every E C.. f() # g(z), and
Hc 2 (f(11),((11) x (f(r2). x x...x (f(rn),
I = [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.c.. Hc {1, 21,2]Ic1, Note that multiclass shattering does not mean being able 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 allowed to pick from two of the labels.
Definition (Natarajan Dimension) The Natarajan dimension of H. denoted Ndim(H), is the maximal size of a shultered set C' E X.
Theorem (Excess Risk Upper Bound of NI-ERM) Let E [0. 1]. E (0, (20). Consider any (Px, n, 7) E R),, assume function class FF has Natarajan dimension V, and the noisy Bayes classifier f belongs to F. Let E F be the ERM trained on n {(x,, Y:) l=1' then
Ezn R ( - R(S) < -161
V Vlog n + 2V log k +
2n
1
V
=c
up log factor.
K
Proof. Following directly from Lemma with (Px, 77. 17) E II(e, K). we already have
R(f) - R(f*) < Px X An (7. n) + x
[i())) R (f))
Set ((()) - πe (i+))
Now replace f with NI-ERM To bound the expected excess risk we employ multiclass VC-style inequality.
Lemma
log (H,,
Ez-
f
R (f*)
s 161
2n
The binary version of this lemma is Corollary 12.1 in Devroye et al. (999).. We prove the multiclass version below in Section A.2.6]
Next, 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 Natarajan 1989 ) Let and y be two finite sets and let H be a set of functions from C to y. Then
H < IC| Nddim( (H).
| 2Ndim H))
27

---

Letting V denote (H). we have that S(H, S nnkkk,, K and therefore Lemma can be upper bounded by
E ~m
(
R
R
(f*)
S 16V
log (8e(n) K2v)
2n
log 8e log (n + log (K2V)
V
2n
V llog n + 2V log K + 4
2 16
2n
Putting things together,
- sct _. .16V
R (f) R(F)
V log + 2V log +
B
2n
A.2.6 Proof of Lemma
Theorem Consider any set of multiclass classifiers F. Let (X1, .X,,),,,,,,,,,,, Yn) be iid draws from Pxy. For any n, and any O,
Pr sup [R(J) R() >E e } < S8S(F, male--ee -ne -ne fer
where 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 notation from Devroye al. 1996], and the right-hand side is our notation.
V Pxy
Z = (X,Y)
2, = (i)
= (A, If F}, where A, {(x lf()) y)
With these identifications, we have
v(A,) = R(f)
vn (A,) 1
n Σ 112EEA1 - - - Rn(
By Theorem 12.5 conclude
Pr sup Rn(f) - R(fI sej s 8s(A, (2) EEF
where s(A,n) (note the lowercase "s") is defined to be
max NA(2i,..., En) Ai....Pp
where the max is over points 2 form
Zn. and NA Zn) is the number of distinct subsets of the
A₁ (21,...,2.)
as / ranges over F.
To conclude the proof, it suffices show that (A, S S(F, n), where the latter expression the multiclass shatter coefficient defined above. We show this as follows.
28

---

Consider fixed pairs 2, (z,, 31), = 1,..., n. Supposed that there are N distinct subsets of the form Ay (=1,...: 2n
and ..,...; SN be the classifiers in that realize these distinct subsets. Consider the map that sends f; to the vector of its values at Ti,...;
fi + (f.
E Y.".
We will show that this map is injective, from which the claim follows. To see injectivity, consider classifiers Si and fj. where + j. Since Ji and fj yield different subsets, means there is some pair (zy,, yk) such that one of fi and fy classifies the pair correctly, while the other does not. This implies that [((xa) + fz(),, and therefore
+ (f)(a)).....$
This concludes proof.
Now, Lemma 2 follows from the above theorem (stated in terms the noisy dataldistributionnissk) in precisely the way that Corollary 12.1 in Devroye al. (T996) follows from Theorem 12.6 in the same book.
A.2.7 Proof of upper bound: Theorem
Theorem (Exeess Risk Upper Bound of NI-ERM under smooth relative margin condition) Let E [0, a) > 0, Ca > O. Consider any (Px. 7) II' Ca), assume function class F has Natarajan dimension V, and the noisy Bayes classifier f* belongs F. Let f E F be the ERM trained on 7 {x;; {:)) i=1 Then
f R(())
S c inf
Caka
(
V
#30
17
= (n aa/(2+22))
Proof. Again, using Lemma large enough constant.
1 and Theorem we can conclude the following, where C some
Ez [R() R(f*)]
inf x20
A Px X Anc (1, +
(i( R (Fr))
CV log(n)))
inf
Px
x Ax (n.
x>0
n
Now, by definition of (e, a, Ca), holds that
Vk > 0, (x(M(z; n. S k) S Cak +e.
Thus, further conclude that
1 /CV log(nk)
Ez- [R()) R(")) inf
C.ka c C+Cana
<20
k
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
Ki. ((aCa)-) lognk)))) 1/(a+1)
This yields the bound
Ez- (R() - R((5) ((VVlog(nK)/u) a/(a+1)
(
= (nn-O(nnnaaaa -a/(a42)).
29

---

A.2.8 Proof of immunity results: Theorem and
Here, we state the immunity theorems in equivalent but different way, so that the proofs are easier to follow.
Theorem (Immunity for one-hot vector) vectors.
Denote B (ei...., ext be the set of one-hot
V (2)) E B,
arg max mTx) arg max (2x) (z))
Diagonal elements of E(x) maximizes its row.
Proof. Let 17x)) = By for some y, then
P YY=1y== - =
y =,
7(x) = (>))
= =[E(x))n
P p K Y y, x,x=a)
To have
arg max 77x) arg EE arg max 77xx) y
for 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,
A (z)), arg max (x)) arg max E(x) (x)))
Be(x) s.l. Vx, e(x)
0, K
and
- (K- - 1)e(x)
c(x) 1 - (K - 1)e(x)
e(x)
e(x)
e(z)
E(x)
e(xx
c(x)
1 (K - 1)e(x))
Proof.
= Plug E(r) into the expression
7)x) E (xx)
(K- 1)e(x))
c(x)
e(x)
e(x)
1 (K - 1))(x)
e(x)
((x)
e(x)
e(x)
(K 1)e(x))
0
0
0
(1 - K e(x))
+
e(x)
1]
(())
(1 - K e(xx) (x) + constant vector
When e(x) E [0, }), we have
Vn(x), arg max ((x)= arg max (T)).
30

---

i Denote T(x) := E(x)", then
(1((2) (1((2)
(x(
(21(1)
(22(1)
1xx(1)
T(x)
(ki(#))
(x2(x)
lk (x)
has each column sum to 1. Let consider several choices of (xx), which pose conditions matrix T(x).
1)
k Il" then
f1((1) + t2((2) + ... + (x) (2)(x) (2) + 12x
7(x) - T))))())=
K
(ki(z) + ( + +txx
To have
arg max 7)x) = arg max (x) = {1, (1.2....,A))
all elements of 77x)) must be equal, ie.. each row of T()) should sum the same value. The sum of all elements in ((x) is K, since all column sum to 1. Therefore, each row of (zx) also sum to 1.
2) If ( R R- x o]
then
(1(2) + (2)(2) + 11( (2) (2) + (2) + ... ............ 12 (x)
()x) T(x)7(1)= = K 1
1)] (K-1)2 + ti-- -ICK- (1((-1)(2)
(xi(x) (x2(x) ... 1K(K-1j
(xx(x)
(②x(x)
each row of T(x) sum
K
()-)))(
1 (x)
To have
arg 7i(x)) arg max 17xx) (1,2,...,, K. K-.,.,,1) 1},
the first elements of (7x)) must be equal (and larger than tk (I:)), then we have
(xx(x) t2x (z)
t(k ((k())x(2)).
In other words, all elements of the K column of T(x) are the same (except for the (K, K)-th element). Similarly, consider ()x) to be vector that contains O in the i-th position and к- in
other positions, then the general condition for T(x) is that: all elements of the i-th column equal,
except the i-th diagonal. Written explicitly.
(1)())
(12()) (1a(x)
(x((a)
(x)
(x)
f1s(2)
(x(()
T(x) = (2))
(2((1) (3s(x)
(x(c)
(x)
(2)(x)
(1s(2)
(kk()))
31

---

Since each row and column of T() sum to 1, we have
0 (++12((1) + (1((2) tix (K (a)
of first of first column
(21(1) + +0+ +xxx)x (K ())
+ +(()))((())))) +0+ 1..
=(K - (1)(1(())
(2) (12 /13(1)
(K (K-1)l1 ())
Subtracting the first equation from the second, we have 112 equations, we have 121 (z: 42(x)) (1(2)) 1ix (2)) What's more, all diagonal elements of T()) will be equal. Thus,
(z).. Repeating for all pairs of
(K 1))(x)) e(x)
c(x) 1 (K - 1)e(x)
e(x)
e(x)
T(x)
where e(x) E [0.
: (K 1)e(x)
e(x)
e(x)
3) The final step is to determine what value e(x) can take. Take n(x) Ey for some y, then from Theorem 4 we know that the diagonal elements of (xx) maximize their column, therefore
1 e(x) [0, K
(K 1)e(z) > e(x)
Finally, take any (Tr), the arg max preserved by multiplying this specific choice of T(x). This concludes the = part..
A.3
Experimental details
A.3.1
2D Gaussian with synthetic label noise
For 2D Gaussian mixture data, we draw from two Gaussian centered [1 1] and IjT with covariance matrix being identity, 200 data points from each, with label Y = 1,2 respectively. To generate noisy labels, flip every label uniformly with some probability. We Sklearn's 's logistic regression (with no & 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 different draw of both instances and noisy labels.
Table Testing accuracy of logistic regression on gaussian mixture data with uniform label noise. "Noise rate" refers to P P( + Y), the percentage of wrong labels in the training data. As theory in Section predicts, when P(Ý # Y) reach 50%, there sharp decrease performance.
0.
Toar
91.00
9.95
10.00
Tradls 45
91.55
91.58
91.80
01.63
91.68
91
91.25
90.86
$9.95
38.38
60.53
9.95
8.35
10.00
10.45
9.88
9.00
0.53
9.20
9.0
845
Man
92.11
92.07
02.08
01.95
91.90
91.37
91
90.33
39:15
83.35
65.13
20.40
11.88
10.10
9.23
3.43
3.34
5.45
R21
K16
7.99
Sul
0.70
0.66
0.51
0.50
0.38
0.35
0.41
1.74
3.79
13.44
12.35
10.94
5.39
2.56
1.29
0.35
0.68
1.07
1.00
0.9
0.70
A.3.2 MNIST with synthetic label noise
We flip the clean training label of MNIST (http://yann. lecun. com/exdb/mnist// uniformly (to any of the wrong classes). We use 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 the same hyperparamters for all tests. The experiments were conducted on single NVIDIA GTX 1660S GPU. The goal of the simulation is to experimentally verify noise immunity results in Section 6 Here randomness corresponds different realization of noisy labels and stochastic gradient descent.
32

---

Table Testing accuracy of a shallow CNN (2 conv layers with 2 fully connected layers) on MNIST with uniform label noise. "Noise rate" refers to PY * Y), the percentage of wrong labels in the training data. As theory in Section 6 predicts, when P (Y + Y) reach 90%, there is sharp decrease in performance.
NNaso pac
0:05
0.1
0.15
0.2
0.25
0:35
0.4
0.45
0.5
0.55
05
0.63
837
0.775
0.5
0.55
110
2005
Trall
99.97
05.59
09.81
08.5
06.0 16
98.45
58.07
97.08
97.57
07.88
97.54
07.19
95.10
95.70
95.02
89.00
83.72
11.58
0.17
0.3
Thal
us
98
98.1
91.30
96-31
95.76
91:55
885,09
5:39
98.37
01:31
Menn
05.11
95.11
98.99
96.11
18.35
96.10
15
98.00
V1.30
07.45
9539
M830
91.10
91.31
0124
S12
0.07
0.17
0.09
0.15
0.12
0.25
0.08
0.20
0.21
0.35
0.16
0.30
0.21
0.41
0.34
0.51
1.65
2.59
1.98
0.04
0.63
A.3.3 CIFAR with synthetic label noise
We flip the clean training label of CIFAR-IO (https://www toronto. edu/"kriz/ciii html) uniformly (to any of the wrong classes). To have 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 logistic regression function to fit the (feature, noisy label) pair in a full batch manner. We pre- specify range of values for &2 regularization (40.0001, 0.001, 0.01, 0.1, 10, 100) and number of iterations for Ibfgs optimizer (f10, 20, 50, 100 then do tross-validation on noisy data to pick the best param-parameters. We use the same range of hyper-pass peramppareeters in all tests. The experiments were conducted on single NVIDIA Tesla V100 GPU. The result is deterministic.
-eaikiittell.n....mmmm lewreeerrnn.. org/ stable/)
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 pre-trained ResNet-50 on ImageNet [Deng et al. 2009) (available in Pytorch model library) in 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: //gp:::///ita hhggtttt.b..... com ContrastToDivides C2D?
taa=reedde- ov-file) and "DINOv2 SSL." refers to using the self-supervised foundation model DINOv2 [Oquab al. [2023] (available at //attps://giii
comm/facebookresearcch (atperssarrr/ddior dinov2)) as the feature extractor. "Noise rate" refers to (Y # Y). the percentage of wrong labels in the training data. As theory in 6ectionn6]predicee when IP (P + Y) reach 90%, there is sharp decrease in performance. We employed Python's 's sklearn logistic regression and cross-validation functions without data augmentation. The results deterministic.
Noise rate
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.85
0.9
0.95
Litear
41.37
41.09
40.97
40.37
40.45
39.44
37.28
35.20
26.74
10.28
Linear ResNet 50 TL.
90.17
89.58
89.01
88.27
87.55
87.28
86.40
85.01
82.03
74.02
10.82
1.47
0.26
Lineur + 50 SSL
92.48
92.26
91.74
91.46
91.13
90.33
91.07
90.99
89.11
83.89
10.08
1.31
0.34
Linear DINOv2 SSL
99.25
99.27
99.23
99.14
99.10
99.11
99.02
98.84
95,50
76.91
10.13
0.92
0.03
A.3.4 CIFAR with human label error
We load the noisy human labels provided by http://noieylabells.com same procedure as above.
then follow exact the
33

---

Table Performance on CIFAR-N dataset (ittp:///hoisylabelss... com/) ) in terms testing aceu- racy. "Aggre". "RandI", ..... "Noisy" denote various types of human label noise. We apply linear model on top different feature extractors: "ResNet-50 TL" refers to using a pre-trained ResNet-50 on ImageNet (Deng al., 2009) in transfer learning fashion, "ResNet-50 SSL." refers using 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.
Methods
CIFAR-ION
CIFAR-100N
Aggre
Randl
Rand2
Rand3
Worst
Noisy
Linear
40.73
40.41
40.31
40.63
38.43
16.61
Linear ResNet-50 TL
89.18
88.63
88.61
88.66
85.32
62.89
Linear ResNet-50 SSL
91.78
91.66
91.39
91.28
87.84
57.95
Linear + DINOv2 SSL
98.69
98.80
98.65
98.67
95.71
83.17
A.4
Additional experiments
A.4.1 Linear probing, then fine tuning (LP-FT))
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 CIFAR-N dataset (attp://noissllabelss com/ in terms of testing curacy. "Clean" refers to no label noise, "Aggre", "Randl" "Noisy" denote various types of human label noise. We compare the testing accuracy of LP-FT versus L.P only, over different feature extractors: "ResNet-50 TL" refers to using pre-trained ResNet-50 ImageNet [Deng et al. 2009) transfer learning fashion, "ResNet-50 SSL" refers to using pre-trained ResNet-50 on unlabeled CIFAR data with contrastive loss [Chen al. 2020) and "DINOv2 (small) SSL" refers using light version of the self-supervised foundation model DINOv2 (Quub et al.
2023 as the feature
extractor.
Feature
Method
CIFAR-ION
CIFAR 1IFAR-1OON
Clean
Aggre
Rand1
Rand2
Rand3
Worst
Clean
Noisy
LP (ours)
90.17
89.18
88.63
88.61
88,66
85.32
71.79
62.89
ResNet-50 TL.
LP-FT
95.94
92.03
88.55
87.78
87.82
71.88
82.3
63.85
LP (ours)
92.54
91.78
91.66
91.46
91.17
87.85
69,88
57.98
ResNet-50 SSL
LP-FT 94.11
89.11
84.49
83.75
84.15
65.00
74.41
54.49
(ours) 96.09
94.39
94.42
94.35
91.14
83.82
72.46
DINOv2 (small) SSL
LP-FT 98.23
93.29
88.03
87.27
86.94
67.42
89.97
64.81
A.4.2 Robust learning strategy over DINOv2 feature
This section examines how different robust learning strategy works over DINOv2 feature, compared with only training with cross entropy.
34

---

Table 7: Comparison of different noise robust methods on DINOv2 features. Training a linear classifier with cross entropy (CE) loss is the baseline. We compare it with robust losses: mean
absolute error (MAE) loss Ghhoh and Kumar 2017 Ma and Fattahi 2022], sigmoid loss Ghhosh
et al. 2013], and regularized approaches: "Early-Learnnn Regularization (ELR) [Liu et al. 2020
Sharpness Aware Minimization' (SAM) [Foret et al. 2021].
Feature
Method
CIFAR-1ON
CIFAR-100N
Clean
Aggre
Rand1
Rand2
Rand3
Worst
Clean
Noisy
CE
99.25
98.69
98.8
98.65
98.67
95.71
92.85
83.17
MAE
99.27
99.04
99.01
99.09
99.11
95.55
90.68
82.55
DINOv2 SSL
Sigmoid
99.26
98.86
98.91
98.87
98.96
96.66
92.82
82.03
ELR 99.09
98.49
98.62
98.53
98.56
95.60
89.99
82.75
SAM
99.09
97.66
98.47
98.53
98.47
95,47
89.97
82.85
A.4.3
Synthetic instance-dependent label noise
Table We synthetically corrupt labels of CIFAR- 10 according Xia al. [2020). and compare
our NI-ERM with the PPart-dependent matrix estimation" (PTD) method proposed in that same paper.
Method \ Noise rate
10 %
20 %
30 %
40 %
50 %
PTD
79.01
76.05
72.28
58.62
53.98
NI-ERM (ours)
99.11
98.94
98.20
93.35
74.67
35

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: The claims are either supported by theory statements or by reproducible experiment results.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made 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 long is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification: Limitations about our practical method described.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors encouraged to create separate "Limitations" section in their paper.
The paper should point any strong assumptions and how robust the results are violations of these assumptions (c.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 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, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-text system might not be used reliably 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 faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
36

---

Answer: [Yes]
Justification: Assumptions are stated in the theorem statement. Full proofs are included in the appendix.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated referenced in the statement of any theorems.
The proofs can either appear the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
Justification: Important information about the experiments are main text. Details on the experimental setup is described in the appendix.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
the contribution is a dataset and/or model, the authors should describe the steps taken make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, may be necessary either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how replicate the results, access to a hosted model (e.g.. g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurlPS does not require releasing code, the conference does require submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is new model (e.g., a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers to have some path to reproducing verifying the results.
37

---

5. Open access to data and code
Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [Yes]
Justification: Code is provided, common benchmark datase were used, instructions are given, the result is casily reproducible.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.co
publicc/uiiee//ddeeluu....s ooo.ooooeooouiiiisooooooooooiioi for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https
7 //nips. //nips.c/pput wttpc//pwpcpcgddeeeeeeeeeeeeeeee http://gguuides/ddduubbbbiiiaaia
for more details.
The authors should provide instructions data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, 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 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, as supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
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, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
38

---

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 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).
should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are range (e.g. negative enror rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
Justification: See appendix.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary failed experiments that didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics
Answer: [Yes]
Justification: The authors have read the NeurlPS Code of Ethics and confirm that this research follows the code of ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurlPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws regulations in their jurisdiction).
10. 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 theory-oriented paper towards better understanding of label noise
problem.
Guidelines:
39

---

The answer NA means that there is no societal impact of the work performed.
If the authors answer NA 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 unintended (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 tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that 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 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 being used as intended but gives incorrect results, and harms following from (intentional 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 MI..
11. Safeguards
Does the paper deseribe safeguards that have been put in place for responsible release of data or models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
The paper poses no such risks
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have 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 challenging, and many papers do not require this, but we encourage authors to take this into account and make 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 URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
40

---

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, ptttassts.paperssttt paperswi thcode. cww.coo////o/// datasets
has curated licenses for some datasets. Their licensing guide can help determine the license 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.
this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New Assets
Are assets introduced in the paper well documented and is the documentation provided alongside the assets?
Question:
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/cooeemmodel 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 anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. 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 the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then much detail as possible should be included in the main paper.
According to the NeurlPS 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.
15. 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 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 crowdsoureing nor research with human subjects.
41

---

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 the institution conducting the review.
42


Reviews:
[{"review_id": "s06UzHhvo4", "reviewer": "Reviewer_rXjd", "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.", "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. \n\n- 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\")\n\n- 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": "Yes", "rating": 4, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The paper's analysis is correct, and the results relative to the CIFAR-N leaderboard are impressive. (I wish I was able to see the leaderboard, however; several browsers failed to load more than a blank screen.) The message of the paper -- in the presence of unknown noise, learning final-layer classifiers is more robust than learning a classifier from scratch -- is an old one, known empirically to be worth using. The paper's message is clear, and it is overall clearly written.", "weaknesses": "The problem addressed in this paper is very common, and people use many heuristic practical strategies it. The paper states that there are theoretical contributions leading to practical consequences. These practical consequences (recommending ignoring the noise) are not new, and the theory lends no understanding on when this might succeed and fail. \n\nThe 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.\n\nThe 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. \n\nPresentation-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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for taking the time to review our paper. We appreciate your feedback and constructive criticism. In response to your comments, we would like to address your concerns regarding weakness of the theory and the experiments. We believe we can clarify many points.\n## \"Brittleness\" of theory\n> The theory is quite brittle in a couple of ways ... 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\n\n**No, we did not use uniform label noise in the proof.** See the construction of $\\eta(x), \\widetilde{\\eta}(x)$ in line 437 Eqn. (2) - (4). To be specific, the label noise in that construction puts all probability mass into one specific class, while uniform label noise would spread probability mass into all classes instead. \n\nThe reviewer may be alluding to the fact that we \"let $J \\sim Uniform (1,2, ..., K)$\" in line 454, or \"let $B \\sim Uniform (1,2 )^{V-1}$\" in line 468. This is a technique called the \"probabilistic method\" that is commonly used in the minimax lower bound proofs (see, e.g., [7] Section 14).\n\nWe re-iterate that our lower bound proof did not use uniform label noise. The bound applies exactly to **instance-dependent label noise**.\n\n> 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.\n\n\nIf $A_0$ is empty, then our theory still returns a meaningful result. In this case, the noisy and clean Bayes classifiers disagree almost everywhere, and therefore $\\epsilon = 1$, leading to a (big) lower bound of $(1-1/K)$ on the clean excess risk. So we are not sure why you say our theory is brittle here, and we welcome clarification.\n\n\"the gap to the top class probability\" is fundamental in learning theory, see for example the standard assumptions of Massart and Tsybakov [1-3].\n\n## Practical performance\n\n> The results relative to the CIFAR-N leaderboard are impressive. I wish I was able to see the leaderboard, however; several browsers failed to load more than a blank screen.\n\nWe have contacted the research team who maintains the CIFAR-N leaderboard. They have fixed it, welcome to try it again <http://noisylabels.com/>.\nOtherwise, wayback machine records its status on May 23rd, see <https://web.archive.org/web/20240523101740/http://noisylabels.com/>.\n\n> These practical consequences (recommending ignoring the noise) are not new, and the theory lends no understanding on when this might succeed and fail.\n\nWe acknowledge that the practical idea of ignoring label noise is not new [4], but the full power of this approach has not been previously recognized. For example, prior work that has suggested ignoring the label noise usually augments this approach with additional heuristics such as fine-tuning with early stopping [5]. We will add a paragraph about previous works that practically suggest ignoring the noise.\n\nFurthermore, our theory precisely describes when the method succeeds: It is nearly minimax optimal under the setting of Thm 2, and consistent under the settings discussed in Section 5.\n\n> How about estimating label shift ...  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.\n\n**Label shift is a different problem (compared with label noise).** In label shift, the X-marginal distribution changes (from source to target) whereas with label noise, it does not. Furthermore, label shift methods assume access to an unlabeled test dataset, which is also not present in the label noise setting. Finally, label shift methods estimate the class prior for the test data (which is a $K$ dimensional vector), not class-conditional noise parameters in a class-conditional noise model (which is a $K \\times K$ matrix). \n\nOr, are you asking if \"label shift-ignorant ERM\" works in a label shift problem? It sounds like an interesting research question and worth exploring. Again we welcome clarification.\n\n> Are the authors aware of the two-step strategy of linear probing then fine-tuning the whole network... How does this do? \n\nYes, we are. We have ran additional experiments: **LP-FT is generally beneficial when there is no label noise, but becomes harmful when noise rate increases**, see Table 1 in the pdf attached to the global rebuttal.\n\n> Why not simulate with instance-dependent label noise of some kind (e.g. simulate cluster-dependent label noise) instead of uniform label noise?\n\nWe have ran additional experiments: we simulated instance-dependent label noise using a commonly adopted approach in [8]. Our NI-ERM performs better than the approach proposed in [8]. See Table 3 in the pdf attached to the global rebuttal for detail.\n\nReference:\n\n[1] Alexander B Tsybakov. Optimal aggregation of classifiers in statistical learning. The Annals of Statistics, 2004.\n\n[2] Pascal Massart and Élodie Nédélec. Risk bounds for statistical learning. The Annals of Statistics, 2006.\n\n[3] Vu Dinh, et al. Learning from non-iid data: Fast rates for the one-vs-all multiclass plug-in classifiers, TAMC 2015.\n\n[4] Aritra Ghosh and Andrew Lan. Contrastive learning improves model robustness under label noise. CVPR Workshop, 2021.\n\n[5] Yihao Xue, et al. Investigating why contrastive learning benefits robustness against label noise. ICML, 2022.\n\n[6] Ruixuan Xiao, et al. Promix: Combating label noise via maximizing clean sample utility. IJCAI, 2023. \n\n[7] Luc Devroye, László Györfi, and Gabor Lugosi. A Probabilistic Theory of Pattern Recognition, 1996.\n\n[8] Xiaobo Xia, et al. Part-dependent label noise: Towards instance-dependent\nlabel noise. Advances in Neural Information Processing Systems, 2020.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "BObEtrvWTi", "reviewer": "Reviewer_JX6n", "summary": "In this work, the authors use a new theoretical framework for analyzing learning under label noise in multi-class classification. \nThe proposed framework is based on relative signal strength (RSS), which measures noisiness data points in the training sets.\nBased 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.", "questions": "Not really, I will be happy to read the authors comments on my points from the weakness section.", "limitations": "Limitations were discussed. I see no negative social impact of this work.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The paper is sound and, despite being very theoretical, is easy to read, as authors step by step explain the thinking process.\n- Newly obtained bounds are indeed simple in form.\n- The effectiveness of the new two-step NI-ERM is confirmed by a few empirical empirical experiments.", "weaknesses": "- It seems to me, that the analysis conducted under the Relative Signal Strength framework does not provide a lot of new surprising insights, the conclusions more or less confirm findings from previous works. \n- 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.\n- The considered analysis and proposed approach is limited to classifier accuracy, while in many applications other task losses/utilities are often considered.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for taking the time to review our paper.\nWe are especially glad that you find our paper easy to read. Below we would like to address some concerns.\n\n> 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.\n\nWould you be willing to provide specific references to prior work to help us frame our response? Thanks. \n\nWe agree that the empirical idea of ignoring the noise is not original (e.g., [1]). \nTheoretically, however, to our knowledge no prior published articles have proved the optimality of the noise-ignorance approach. We are also unaware of any lower bound analysis on label noise that treat a setting as general as ours.\n\n\n\n> 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.\n\nFortunately, foundation models are being developed for a rapidly expanding list of application domains, including audio, video, graphs, text and tabular data ([3], Section 4). Generalizable strategies for self-supervised learning are also advancing at a rapid pace, e.g., self-distillation, masked text/image modeling ([3], Section 2).\n\n> The considered analysis and proposed approach is limited to classifier accuracy, while in many applications other task losses/utilities are often considered.\n\nOur results can be extended to the balanced error, and we expect that they also extend naturally to cost-sensitive 0/1 loss. Extensions of our work to other performance measures would be an important research question. \n\nReference:\n\n[1] Aritra Ghosh and Andrew Lan. Contrastive learning improves model robustness under label noise. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, 2021.\n\n[2] Ruixuan Xiao, et al. Promix: Combating label noise via maximizing clean sample utility. In Proceedings of the Thirty-Second International Joint Conference on Artificial Intelligence, 2023. \n\n[3] Jonas Geiping, Quentin Garrido, Pierre Fernandez, Amir Bar, Hamed Pirsiavash, Yann LeCun, and Micah Goldblum. A cookbook of self-supervised learning. arXiv preprint arXiv:2304.12210,2023.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "bTHeWnR0Rz", "reviewer": "Reviewer_V7Mw", "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.", "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": "-", "rating": 5, "confidence": 2, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "The author presents a novel perspective for solving the LNL problem. The interpretations of RSS proposed by the author are sufficiently insightful for peers in the LNL field. Moreover, the author's method is well-suited for use with pretrained feature extractors and aligns with current trends in the AI field.", "weaknesses": "There are two major concerns. The first is the low reproducibility. Despite the robust interpretation of the proposed method, the lack of a specific algorithm makes it challenging to conceptualize a clear learning approach. Specifically, it would be beneficial to provide examples of e(x) in Theorem 5, as well as pseudocode for feature extraction and the derivation of the transition matrix. Secondly, it is challenging to interpret the advantages of the proposed method from the experiments. (1) The author conducted experiments solely on light synthetic data, making it difficult to ascertain the effectiveness of the theoretically-based method in practical noise scenarios. (2) The author employs a highly trained pretrained model, which introduces an unfair factor in comparisons with other methods. Notably, there is experimental evidence suggesting that self-supervised pre-training can enhance the performance of existing methods (https://arxiv.org/pdf/2103.13646v2). I recommend including the author's method applied to various pretrained models in Table 1, or adding the use of pretrained models for existing methods to provide a fair comparison.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for taking the time to review our paper. \n\n> I have given high marks to the author's novel perspective and the reasonable interpretations and proof methods presented... 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.\n\nWe are glad that you find our paper helpful. **A small point: the current rating seems to corresponding to \"borderline accept\" rather than \"weak accept\".** Thanks.\n\n>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, \n\nActually, $e(x)$ is not part of our algorithm. It is a quantity that describes a theoretical condition under which NI-ERM is consistent. It is not needed by the algorithm.\n\n> it would be beneficial to provide ... pseudocode for feature extraction and the derivation of the transition matrix. \n\nActually, we do not propose a method for feature extraction. We simply use existing methods (e.g., pre-trained ResNet available in pytorch model zoo).\n\nWe also do not estimate a noise transition matrix. This is a mathematical object that we use to state theorems about the performance of NI-ERM, but it is not a quantity that is needed as input to an algorithm.\n\nWe have a description of our practical method, which is described in steps 1 and 2 in Section 6 (line 260-263). It is actually a meta-algorithm, allowing the user flexibility in choosing the feature extractor and empirical risk minimizer.\n\n> 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. \n\nIn paper, we have results for real data (MNIST, CIFAR), including the noisy CIFAR dataset which has real-world (human generated) noisy labels.\n\nIn response to your (and other reviewers') requests, we have also performed some additional experiments. See the results in the pdf file attached to global response (and our responses to other reviewers), those demonstrates our NI-ERM is hard to beat.\n\n> (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.\n\nThanks for bringing this up, we will include the paper in the reference.\n\nIn respond to your request, we have ran additional experiments, all based on the same pretrained model, see Table 2 in the pdf attached to the global response.\n\n\nNotice:\n\nthe \"noise rate of $90\\\\%$\" in Table 1 of the referred paper (https://arxiv.org/pdf/2103.13646v2) corresponds to \"actual noise rate $P(Y \\neq \\widetilde{Y}) = 0.90 \\times (1-1/10) = 81 \\\\%$\".", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "pc32dWTKaq", "reviewer": "Reviewer_1ugH", "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.\nThis 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).", "questions": "- Does the analysis depend on any particular loss used during training?", "limitations": "yes", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "I enjoy reading this paper. The work presents a surprisingly simple idea to deal with noisy labels, especially instance-dependent noise, and show that it is the optimal learning strategy under some conditions.\n- The authors introduce the Relative Signal Strength (RSS) to quantify how much noisy label distribution can reveal about the clean label distribution.\n- Based on this measure, the authors suggest a class of noisy label learning problems that can be guaranteed to be solvable (Theorem 2) by just ignoring the existence of noisy labels. This is somewhat still intuitive because RSS is positive and the excessive risk is measured based on 0-1 loss.\n- They also present a min-max analysis to show that for the same class of problems, the above learning strategy achieves an optimal rate. This is really a surprising and intriguing result.\n- Lastly, they show how applicable this class of problems can be in practice (Theorem 4, 5): the label noise probability vector should have the same argmax as the clean probability vector.", "weaknesses": "- The key condition for ignoring the existence of noisy labels to work is to have $\\mathcal{A}_0 = \\mathcal{X}$ (or $\\mathcal{A}_0$ covers most of $\\mathcal{X}$), which in turns requires $\\text{argmax } \\widetilde{\\eta}(x)  = \\text{argmax } \\eta(x)$. This condition would be violated if certain classes are tricky and easy to mistaken one as another, for example, labeling leopard, lion,  cheetah, tiger. Therefore, the condition that \\kappa > 0 might be restrictive in this regard.\nOn 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.\n- The experiment section is limited:\n   + How is performance of the proposal compared to baselines under various noise level?\n   + More baselines should be included, such as BLTM[1], MEIDTM[2], MaxMIG[3].\n\n[1] Yang, Shuo, et al. \"Estimating instance-dependent bayes-label transition matrix using a deep neural network.\" International Conference on Machine Learning. PMLR, 2022.\n\n[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.\n\n[3] Cao, Peng, et al. \"Max-mig: an information theoretic approach for joint learning from crowds.\" arXiv preprint arXiv:1905.13436 (2019).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for taking the time to review our paper. We are especially glad that you enjoyed reading our paper.\n\n> The key condition for ignoring the existence of noisy labels to work is to have A0=X (or A0 covers most of X), which in turns requires $\\arg \\max \\widetilde{\\eta}(x)= \\arg \\max \\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.\n\nThat is an interesting scenario. It seems to us that \"disambiguate a label permutation\" requires additional information (e.g., human feedback), which is not a part of our problem statement.\n\nIf we allow further \"post-processing\", that would be an interesting research problem worth exploring.\n\n\n> Does the analysis depend on any particular loss used during training? \n\nThe theoretical analysis is on zero-one loss. To incorporate surrogate losses, one can use the classification-calibration [1] argument.\n\nAs for practical performance, we have tried more than 10 different multi-class losses, they end up performing similarly. We could incorporate that in our next version. \n\nAs for now, Table 2 in the attached pdf file to the global rebuttal shows the comparison of cross entropy to several \"noise robust losses\" [2-3], their results are comparable.\n\n\n> The experiment section is limited... More baselines should be included, such as BLTM, MEIDTM, MaxMIG.\n\nThanks for mentioning these papers, we will include them in our next version. \n\nAt this point, due to time constraint, the additional experiments we have ran are shown in the attached pdf to the global rebuttal. Feel free to take a look, thanks.\n\n\nReference:\n\n[1] Peter Bartlett, Michael Jordan, and Jon McAuliffe. \"Convexity, classification, and risk bounds.\" Journal of the American Statistical Association, 2006.\n\n[2] Aritra Ghosh and Himanshu Kumar. Robust loss functions under label noise for deep neural networks. In Proceedings of the AAAI conference on artificial intelligence, 2017.\n\n[3] Aritra Ghosh, et al. Making risk minimization tolerant to label noise. Neurocomputing, 2015", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Vupgt4PRJT", "reviewer": "Reviewer_G7Jo", "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.", "questions": "1. Definition of RSS: \nI 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?\n\n2. Gap between Theory and Practice: \nWhile 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": "Limited Application to Classification Problems: \nWhile 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.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "1. Theoretical Depth: \nThis paper introduces the novel concept of Relative Signal Strength (RSS) to quantify the impact of noise in label learning. Using RSS, the authors mathematically derive precise upper and lower bounds for excess risk.\n\n2. Combination of Theory and Practicality: \nThe research seamlessly bridges theory and practice by developing a two-step 'feature extraction + NI-ERM' approach based on their theoretical analysis. This method achieves high performance using simple linear classifiers instead of complex deep learning models, validating the theoretical predictions about the optimality of NI-ERM in practical applications. This successful translation of theoretical insights into effective practical methods is a significant strength of the paper.\n\n3. Surprising Results:\nOne of the most striking aspects of this work is the mathematical proof that simple Noise Ignorant Empirical Risk Minimization (NI-ERM) is minimax optimal. The authors theoretically guarantee accurate learning even under high noise levels, such as up to 90% in 10-class problems. These surprising findings challenge conventional wisdom about the necessity of complex noise handling techniques and achieve state-of-the-art performance with a remarkably simple approach.\n\n4. Experimental Validation:\nThis paper provides experimental validation of its theoretical claims by achieving top performance on real-world noisy datasets like CIFAR-10N and CIFAR-100N. They demonstrate that performance changes with increasing noise levels align closely with their theoretical predictions, providing empirical support for their theoretical framework.\n\n5. Practicality:\nThe proposed method achieves high performance without relying on data augmentation or complex hyperparameter tuning", "weaknesses": "1. Insufficient Introduction:\nThe 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.\n\n2. Validity of Relative Signal Strength (RSS) Definition:\nThe 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.\n\n3. Experimental Validity Concerns:\nThe 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:\na) Compare NI-ERM using feature extractors from models trained with other SOTA noisy label methods.\nb) Apply SOTA methods to the same high-quality feature extractors used for NI-ERM, training only the final linear layer for a fairer comparison.\nThese additional experiments would provide a more robust validation of the NI-ERM approach in practical scenarios.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for taking the time to review our paper. The \"strength\" section of your review indeed summarizes our contributions. We also especially thank you for bringing up the point about the relation of RSS and KL divergence. In the next version, we will include the example you provided and explain the relations between the two concepts.\n\n## Regarding \"Weaknesses\":\n\n> 1. Insufficient Introduction: ... A more detailed exposition of the overall approach and key findings would better prepare readers and emphasize the paper's significance.\n\nThank you for this suggestion. We will certainly include a paragraph outlining the content and contributions in the next version.\n\n> 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.\n\nThank you again for this comment. Fortunately, there are a few lines from the appendix (line 526-528) that we will move to the main text that show precisely where the definition of RSS comes in to play. \n\nIn short, the clean excess risk is \n$$\nR(f) - R^* = \\int (\\max_i [\\eta(x)]_i - [\\eta(x)]_f ) d P_X(x),\n$$\nwhere we see the denominator of RSS.\nWhile the noisy excess risk is\n$$\n\\widetilde{R}(f) - \\widetilde{R}^* = \\int (\\max_i [\\widetilde{\\eta}(x)]_i - [\\widetilde{\\eta}(x)]_f ) d P_X(x),\n$$\nwhere we see the numerator of RSS.\n\nRSS is the right definition because it is what **pops up naturally** when bounding the clean excess risk with the noisy one.\n\nAs for more intuition, see also our response to your first question, below.\n\n> Experimental Validity Concerns... 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. \n\nThese are reasonable requests. For:\n\na) Although we have not had time to run these experiments, we already have some insight into what would happen: the performance relates to the \"feature quality\", assessed in terms of classification accuracy with no noise, see line 279-282.\n\nb) We have ran additional experiments by fixing the \"high-quality feature\" and training the final linear layer with different robust losses [2-3] and robust training procedures [4], see Table 2 in the pdf attached to the global rebuttal. Our NI-ERM approach is highly competitive.\n\n\n## Regarding \"Questions\":\n\n> 1.\tDefinition of RSS: I am curious about how RSS measures certainty about the label... 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?\n\nThanks for bring up this excellent point.\nThe short answer is:\n**KL divergence considers the similarity between two (whole) distributions, while the task of classification only focuses on predicting the $\\arg \\max$.**\n\nIn the example you mentioned, $p_1$ is the clean class distribution, and $p_2, p_3$ can be viewed as two noisy copies of it. $p_3$ is closer to $p_1$ in terms of KL divergence, but $p_2$ provides more information in terms of predicting the $\\arg \\max$ of $p_1$. There is no conflict, intuitively: the difference of $p_1$ and $p_2$ lies in that the probability of being class 1 and 3 got swapped, but the \"margin\", aka gap between the largest probability and second largest, is still $0.7 - 0.25 = 0.45$. While in $p_3$, the \"margin\" is $0.6 - 0.3 = 0.3$, which is smaller than $p_2$. \n\nTo conclude, although $p_1$ and $p_3$ are \"closer\" in terms of distribution, $p_2$ provides more information regarding predicting the $\\arg \\max$ of $p_1$ than $p_3$ does.\n\nWe would like to include your example in our paper and write a paragraph about the relation between KL divergence and RSS.\n\n> 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?\n\nThis is because the Natarajan dimension of a large neural net is too big, and therefore the upper bound in Thm 2 is vacuous (bigger than 1). With a lot more data, the bound would be meaningful and NI-ERM would probably work well for end-to-end training (although the amount of data and computational resources required would probably be prohibitive). For a linear classifier, the Natarajan dimension is upper bounded by the dimension of the self-supervised features ([1], Thm 29.7), thus providing much better control on the excess risk.\n\nReference:\n\n[1] Shai Shalev-Shwartz and Shai Ben-David. Understanding machine learning: From theory to algorithms, 2014.\n\n[2] Aritra Ghosh and Himanshu Kumar. Robust loss functions under label noise for deep neural networks. AAAI, 2017.\n\n[3] Aritra Ghosh, et al. Making risk minimization tolerant to label noise. Neurocomputing, 2015\n\n[4] Pierre Foret, et al. Sharpness-aware minimization for efficiently improving generalization. ICLR, 2021.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
We thank all reviewers for your time and effort. Our paper will be substantially better as a result of your comments and questions. Here we provide responses to questions that seem most likely to be of interest to all reviewers.

## Theory

> KL divergence vs. Relative Signal Strength (RSS)

We thank Reviewer G7Jo for bringing up the question on the relation of KL divergence and our new concept RSS. We will include a new paragraph and a new example in our next version to illustrate this. This shall make the concept of RSS more intuitive.

The short answer is: KL divergence considers the similarity between two (whole) distributions, while the task of classification only focuses on predicting the $\arg \max$, making RSS the correct measure. See our response to G7Jo for more detail.

> uses "uniform label noise" in minimax lower bound proof?

No, we did not use uniform label noise in the proof. Our lower bound holds for general instance-dependent label noise. For details, see our response to Reviewer rXjd.

## Experiments

> include comparison to more methods, apply SOTA methods to the same high quality features, linear probing - then fine tuning (LP-FT), ...

These are reasonable requests. We have run additional experiments comparing our NI-ERM approach to previously proposed "noise robust" methods, see **attached pdf** file for details. 

In Table 1, we report results for LP-FT (linear probing then fine tuning), and find that it underperforms our approach when noise is present. 

In Table 2, we compare against two recently published robust training methods by giving those methods access to the same high-quality DINOv2 features that we used. Again we find that NI-ERM is superior. We also reran our own method using some robust losses (mean absolute error, sigmoid) and find that these are comparable to cross-entropy (which we used for the submission).

In Table 3, we ran experiments using a synthetically generated, non-uniform instance-dependent label noise. Again, NI-ERM is superior.

We will add of these results to the next version of the paper.

We thank all reviewers again.

Meta-review: 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.
Decision: Accept (poster)