Noisy Label Learning with Instance-Dependent Outliers: Identifiability via Crowd Wisdom

Authors: tri  nguyen
shahana  ibrahim
xiao  fu
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-15 15:09:33

Abstract: The generation of label noise is often modeled as a process involving a probability transition matrix (also interpreted as the _annotator confusion matrix_) imposed onto the label distribution. Under this model, learning the ``ground-truth classifier''---i.e., the classifier that can be learned if no noise was present---and the confusion matrix boils down to a model identification problem. Prior works along this line demonstrated appealing empirical performance, yet identifiability of the model was mostly established by assuming an instance-invariant confusion matrix. Having an (occasionally) instance-dependent confusion matrix across data samples is apparently more realistic, but inevitably introduces outliers to the model. Our interest lies in confusion matrix-based noisy label learning with such outliers taken into consideration. We begin with pointing out that under the model of interest, using labels produced by only one annotator is fundamentally insufficient to detect the outliers or identify the ground-truth classifier. Then, we prove that by employing a crowdsourcing strategy involving multiple annotators, a carefully designed loss function can establish the desired model identifiability under reasonable conditions. Our development builds upon a link between the noisy label model and a column-corrupted matrix factorization mode---based on which we show that crowdsourced annotations distinguish nominal data and instance-dependent outliers using a low-dimensional subspace. Experiments show that our learning scheme substantially improves outlier detection and the classifier's testing accuracy.

Main paper: 
 introduction: 
 Deep neural networks can easily overfit to noisy labels due to its excessive expressiveness [1, 2] . Many strategies have been proposed to avoid negative impacts of label noise when training neural classifiers; see, e.g., noisy label filtering [3] [4] [5] [6] [7] [8] , robust loss design [9] [10] [11] [12] [13] , and noise generation modeling (or loss correction) [14] [15] [16] [17] [18] [19] [20] [21] [22] . In the last genre, a noisy class label is modeled as a realization of a categorical distribution, which is the ground-truth label distribution being distorted by a probability transition matrix. The transition matrix is interpreted as the "confusion matrix" [9, 14, 18] that can effectively (i) Identifiability via Crowdsourcing. We first show that using the sparsity prior on outliers is insufficient to identify the model of interest, if only one annotator is present. To circumvent this challenge, we propose to employ a crowd of annotators-which is the common practice in data labeling [14, 18, 20, 31] . We show that, by incorporating a carefully designed column sparsity constraint to a coupled cross-entropy (CCE) loss from crowdsourcing [20, 31] to integrate the annotators' outputs, the outliers can be provably identified. Consequently, the ground-truth classifier can be learned with generalization guarantees.(ii) End-to-end One-Stage Implementation. Our approach features a one-stage continuous optimization-based implementation. To be specific, our proposed learning loss allows to approximate the column-sparsity constraint using a smoothed nonconvex ℓ p (where 0 < p ≤ 1) function based regularization (see [46] ). This way, the overall loss is differentiable and can be readily tackled by off-the-shelf optimizers. This is in contrast to many existing methods that involve multiple stages (e.g., [27, 28, 33-35, 37, 39, 40] )-and is arguably easier to implement.We evaluate the proposed method over a number real datasets that are annotated by machine and human annotators under various conditions and observed nontrivial improvements of testing accuracy.Notation. The notations are summarized in the supplementary material in Sec. A. 
problem statement: 
 The Confusion Model and Learning Goal. Consider N data items {x n } N n=1 from K classes. Here, x n ∈ R D represents the feature vector of the nth data item. Let {y n } N n=1 be the set of ground-truth labels, where y n ∈ [K]. Assume that y n 's are unobserved. Instead, we observe the "noisy" version { y n } N n=1 . The label y n ∈ [K] is noisy due to various reasons, e.g., the lack of expertise of the annotator. In this setting, our goal is to learn a performance-guaranteed classifier using the data items {x n } N n=1 , and noisy labels { y n } N n=1 . We consider the following expression of Pr( y n = k|x n ):EQUATIONNote that Pr(y n = k|x n ) is the ground-truth label distribution given the sample x n . This is also the distribution that the target classifier wishes to learn from. We represent the ground-truth classifier using a function f ♮ : R D → R K such that [f ♮ (x n )] k ≜ Pr(y n = k|x n ). We call f ♮ the ground-truth classifier as it is the function that we aim to learn-and it can be learned under ideal conditions (e.g., when N = ∞ and the learner is a universal approximator), given that no noise is present. We define T ♮ : R D → R K×K such that [T ♮ (x n )] k,k ′ ≜ Pr( y n = k|y n = k ′ , x n ), ∀x n . That is, T ♮ (x n ) is the label transition matrix or confusion matrix of sample x n . Let [g ♮ n ] k ≜ Pr( y n = k|x n ). Accordingly, the noisy label generation process for x n i.i.d.x is modeled as follows:EQUATIONEQUATIONwhere categorical(g) denotes the K-dimensional categorical distribution. Per the physical meaning of T ♮ (x n ) and f ♮ (x n ), we have1 ⊤ T ♮ (x n ) = 1 ⊤ , T ♮ (x n ) ≥ 0 and 1 ⊤ f ♮ (x n ) = 1, f ♮ (x n ) ≥ 0,for all n. Under this model, the main goal is to learn f ♮ from {x n } N n=1 and { y n } N n=1 . Identifiability under Instance-Invariant T ♮ (x). From (2a), it becomes apparent that learning f ♮ is not a straightforward task. Even if g ♮ n is observed (which is not), it is hard to identify f ♮ (x n ) or T ♮ (x n ) from the product g ♮ n = T ♮ (x n )f ♮ (x n ). To tackle the identifiability challenge, a popular approach is to simplify (2) by assuming that all instances have the same confusion matrix, i.e., T ♮ (x n ) = A ♮ with a certain A ♮ ∈ R K×K for all n [16, 18, 19, 21, 47, 48] . Under this assumption, many used the "loss correction" based formulation, e.g., [9, 16, 19, 21, 48] . The loss correction idea modifies the training loss of the classifier by taking the confusion matrix into consideration, e.g., minimizeEQUATIONwhere the objective is a modified cross-entropy (CE) loss. The "noise correction" term A and f are used to learn A ♮ and f ♮ , respectively, y n ∈ {0, 1} K denotes the one-hot encoding of the noisy label y n , and A and F denote appropriate constraint sets-i.e.,A = {A ∈ R K×K | 1 ⊤ A = 1 ⊤ , A ≥ 0}and F is a certain deep neural network function class whose outputs reside in the probability simplex. Note that the objective is often used together with regularization and additional constraints of A for various purposes; see, e.g., [19, 21, 30] . When N → ∞, the CE term enforces the learned A and f to satisfy g ♮ n = Af (x n ) for all n [19] . Note that G = [g ♮ 1 , . . . , g ♮ N ] can be expressed as G = A ♮ f ♮ (x 1 ), . . . , f ♮ (x N ) = A ♮ F ♮ , where F ♮ = [f ♮ (x 1 ), . . . , f ♮ (x N )]. Consequently, Eq. ( 3) can be understood as learning A and F such that G ≈ AF . As both A ♮ and F ♮ are nonnegative matrices (due to their physical meaning), the identifiability of F ♮ can be connected to uniqueness of the nonnegative matrix factorization (NMF) model G = A ♮ F ♮ ; see [19, 21, 45] . These are interesting developments, yet the key assumption T ♮ (x n ) = A ♮ for all n appears to be overly stringent. As mentioned, it makes sense to believe that at least a proportion of samples have instance-dependent T ♮ (x n )'s [36, 44, 45, 49] . Not considering such samples may cause performance degradation.Instance-Dependent Confusion-Induced Outliers. When the instance-dependent confusion happens sparingly instead of overwhelmingly, we can re-express T ♮ (x n ) using the following decomposition:EQUATIONwhere A ♮ ∈ R K×K represents an instance-independent (class-dependent) confusion matrix-which is the nominal confusion matrix that reflects the general annotation difficulty of the dataset. The term E ♮ (x n ) represents the instance-dependent "perturbation". For many n's, E ♮ (x n ) = 0. When E ♮ (x n ) ̸ = 0, we have(A ♮ + E ♮ (x n ))f ♮ (x n ) = A ♮ f ♮ (x n ) + e ♮ n, where e ♮ n = E ♮ (x n )f ♮ (x n ). Using (4), the model in (2a) can be expressed as follows:EQUATIONwhere I and I c represent the instance index set where E ♮ (x n ) ̸ = 0 and its complement, respectively. In other words, I is the outlier index set.A remark is that from this point on we will ignore the structure e ♮ n = E ♮ (x n )f ♮ (x n ) of the outliers. Disregarding the structure comes with some losses. For example, this way, our method is not able to learn E ♮ (x n ) that could be of interest. Nonetheless, considering E ♮ (x n ) renders extra modeling and computational burdens. Our treatment simplifies the subsequent analytical and computational developments, particularly, algorithm design. In addition, other types of outliers and anomalies can also be handled by the proposed approach due to the unstructured treatment.Challenge of Outlier Detection. Under the model in (5) , the natural idea is to first identify I and remove the impacts of outliers. Our first attempt is to explicitly model e ♮ n and modify (3) as follows:minimize A∈A,{en∈E},f ∈F - 1 N N n=1 K k=1 [ y n ] k log [Af (x n ) + e n ] k , subject to N n=1 1 {∥e n ∥ 2 > 0} ≤ C, where E = {e ∈ R K | 1 ⊤ e = 0}is the constraint set for e n 's (due to the probability simplex constraints on the model parameters in ( 5)) and C is a scalar that is an estimation of |I|. The idea is to use the prior knowledge that e n does not occur overwhelmingly as constraint. The hope is that the solution of ( 6) can detect I, thereby enabling accurate estimation of A ♮ and f ♮ . However, the following fact reveals a conflicting insight: Fact 2.1. Assume that all f ∈ F are universal function approximators, that rank(A ♮ ) = K, and that N → ∞. Suppose that I ̸ = ∅. Optimal solutions of Problem (6) can attain the minimal value of the objective function and satisfy the sparsity constraint without detecting any outliers. One such trivial solution(A ⋆ , f ⋆ , e ⋆ n ) is A ⋆ = I, f ⋆ (x) = A ♮ f ♮ (x n ) + e ♮ n, and e ⋆ n = 0 for all n.This fact is easy to show (see Appendix F), yet it highlights a somewhat unexpected issue in confusion matrix-based noisy label learning: If only one nominal confusion matrix A ♮ is present (i.e., only one annotator is employed), it does not suffice to recover the ground-truth f ♮ when there exists instancedependent outliers (or any other types of outliers) under the model in ( 5)-under the condition that f is a universal function approximator. The practical implication is undesirable: as deep neural networks are powerful function approximators and are usually very expressive, Fact 2.1 means that the learned neural networks easily overfit to outliers, even if the sparsity prior on outliers is explicitly used in the loss function.S -net covering for E N M . Here, E N M is a set of sparse vectors with the number of non-zero elements upper-bounded by CM K, i.e., for any e N M ∈ E N M , ∥e N M ∥ 0 ≤ CM K. To get the covering number of a set of sparse vectors, we invoke the following result: Lemma C.5. [83] Let X = {z ∈ R N |∥z∥ 2 ≤ q, ∥z∥ 0 ≤ C}. Suppose that C ≤ N 2 . Then, there exists an ϵ-net covering denoted as X ϵ such thatN(ϵ, X ) ≤ eN C q ϵ C ,where e is the Euler's number.Applying Lemma C.5, we get the cardinality of ε 2 √ S -net covering of of E N M as follows:EQUATION)Note that in (25) , we used the result that ∥eN M ∥ 2 ≤ √ 2CM ≤ 2CM, ∀e N M ∈ E N M .Using the covering number results, the cardinality of the ε-net covering of set Z • S is bounded by the following:EQUATIONNow that we have characterized N(ε, Z • S), we invoke the Dudley entropy chaining technique lemma to obtain the Rademacher complexity R(Z • S) [80] :Lemma C.6. Consider set A ⊆ R m , let c = min a a∈A ∥a -a∥. Then for any integer T > 0,R(A) ≤ c2 -T √ m + 6c m T t=1 2 -t log N(c2 -t , A). Since, ∥z∥ ≤ √ S, ∀z ∈ Z • S, applying Lemma C.6 on set Z • S gives R(Z • S) ≤ √ S2 -T √ SK + 6 √ S SK T t=1 2 -t log N( √ S2 -t , Z • S) ≤ 2 -T √ K + 6 K √ S T t=1 2 -t 16K∥X S ∥ 2 F R F S4 -t + CM K log 4eN M 2 -t + K 2 log 8K √ K 2 -t ≤ 2 -T √ K + 6 K √ S T t=1 16K∥X S ∥ 2 F R F S + 4 -t CM K log 4eN M 2 -t + K 2 log 8K √ K 2 -t ≤ 2 -T √ K + 6 K √ S T t=1 16K∥X S ∥ 2 F R F S + CM K log (4eN M ) + K 2 log 8K √ K = 2 -T √ K + 6T K √ S 16K∥X S ∥ 2 F R F S + CM K log (4eN M ) + K 2 log 8K √ K .Choosing T = log S/(2 log 2), we get the boundEQUATION)Combining the upper bound of R(Z • S) given by (27) with the upper bound of R(ℓ • G • S) as given by ( 21) and with the results in ( 18) and ( 19), we get that with probability greater than 1 -δ,EQUATIONwhere R S (Z • S) is upper bounded by (27) .The above relation, combined with ( 16), implies that with probability greater than 1 -2δ:EQUATIONwhere R(Z • S) is upper-bounded in (27) .Question: Does the paper discuss the limitations of the work performed by the authors?Answer: [Yes]Justification: We have discussed the limitations at the end of Section 6.Guidelines:• The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper. • The authors are encouraged to create a separate "Limitations" section in their paper.• The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be. • The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with a few runs. In general, empirical results often depend on implicit assumptions, which should be articulated. • The authors should reflect on the factors that influence the performance of the approach.For example, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon. • The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size. • If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness. • While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations. 
proposed approach: 
 Intuition: Exploiting Crowd-induced Subspace. To get around the issues illustrated in Fact 2.1, our idea is to "create" a low-dimensional subspace where the nominal data reside while the outliers are likely far away from. To this end, we propose a crowdsourcing approach. Consider the scenario where M annotators label the dataset {x n } N n=1 . The noisy label provided by an annotator m for the data item x n is denoted as y (m) n ∈ [K] and follows the generation model as follows:EQUATIONwhere A ♮ m is the annotator m's confusion matrix and eis the outlier term induced by annotator m's instance-dependent confusion.Putting together, we have the following expression:EQUATIONwhere F ♮ is defined as before, andEQUATIONDenote I (m) as the index set where e ♮(m) n ̸ = 0. Then I = I (1) ∪ . . . ∪ I (M ) stands for the nonzero column support of E ♮ . From (7) , one can see that now the "data columns", i.e., the columns of the matrix G ♮ , live in a highdimensional space, i.e., R M K . However, the nominal data part W ♮ F ♮ resides in a K-dimensional subspace range(W ♮ ) where K ≪ M K, if multiple annotators are employed. More importantly, e ♮ j for j ∈ I is an M K-dimensional vector and is unlikely to be inside range(W ♮ ). With this geometry, it is much more likely that one can separate the outliers from the nominal data.Next, we will use the above intuition to build a learning loss. We will take into consideration of practical aspects, e.g., missing annotations and finite dataset size N .Proposed Identification Criterion & Analysis. In this section, we connect our proposed idea to a practically convenient, end-to-end identification criterion and provide identifiability guarantees for the desired model parameters. We consider the following empirical risk minimization under the crowdsourcing model in (6) : is not considered, the objective function (9a) is sometimes referred to as coupled cross-entropy minimization (CCEM) in the end-to-end crowdsourcing literature [20, 30, 31, 50] . CCEM has not been used together with the outlier detection constraint (9b)-and the theoretical characterizations of the constrained formulation is unknown.EQUATION)EQUATIONWe will use the following notations in our analysis. We use I ⊆ [N ] to denote index set of the outliers, i.e., I = n | e ♮ n ̸ = 0 . We also consider that the function class in our learning problem, i.e., F, has a complexity measure R F . In particular, we adopt the so-called spectral-complexity upper bound of the function class F [51] ; see Lemma C.4 in the Appendix.We first establish that the criterion (9) recovers the ground-truth g ♮(m) n 's with a reasonable accuracy. Specifically, we hope to characterize the average estimation accuracy of g (m)n 's where g(m) n = A m f (x n ) + e (m) n and A m 's, e (m)n 's and f are estimated via solving (9): Lemma 3.1. Assume that the observed index pairs (m, n) ∈ S are sampled uniformly at random with replacement. Also assumef ♮ ∈ F, |I| ≤ C ≤ N/2, and that each [A m f (x n ) + e (m) n ] k , ∀A m ∈ A, ∀e (m) n∈ E, ∀f ∈ F are lower bounded by (1/β) for a certain β > 0. Then, with probability greater than 1 -δ, the following holds:1 N M N n=1 M m=1 ∥g ♮(m) n -g (m) n ∥ 2 2 ≤ ϵ g (S), ϵ g (S) = O βR S log S / √ S + log (β) √ log(1/δ) / √ S ,whereR 2 S = K 2 log (K) + K∥X∥ 2 F R F /S + CM K log √ N M and X = [x n1 , . . . , x n S ] are the annotated samples, in which (m s , n s ) ∈ S for s = 1, . . . , S.The proof is in Appendix C, which uses a similar idea as [31, Proposition 1] but takes into consideration of the outliers. Lemma 3.1 reveals that the criterion (9) essentially recovers the complete matrix G ♮ [cf. Eq, (7) ] from the noisy and incomplete observations of its entries, when S /C is sufficiently large. To proceed, we will need a suite of assumptions and definitions: Assumption 3.2. The outliers satisfy e ♮ i / ∈ range(W ♮ ), ∀i ∈ I, where rank(W ♮ ) = K.Assumption 3.2 presents the key condition to disassociate instance-dependent and instanceindependent confusions. As discussed after Eq. ( 8), having a larger M would decrease the possibility that any e ♮ n belongs to range(W ♮ ). We also characterize the "quantity" that e ♮ n is perturbed from range(W ♮ ) in the following definition: outlier samples clean samples Figure 1 : An illustration of outliers and nominal data items w.r.t. range(W ♮ ): (left) when M = 1, e ♮ ∈ range(W ♮ ), (right) while M > 1, it is highly likely that e ♮ ̸ = range(W ♮ ). In addition, the measure κ(e) is larger for outliers that are farther from range(W ♮ ).Definition 3.3. The outlier impact score κ(e ♮ i ) of data i ∈ I is defined as κ(e ♮ i ) ≜ minEQUATIONwhereW = W = [A ⊤ 1 , . . . , A ⊤ M ] ⊤ | A m ∈ A .A larger score κ(e ♮ i ) implies it is easier for our criterion to distinguish the outliers from the nominal data. Fig. 1 illustrates the geometry that we rely on to detect outliers. One can notice that when M = 1, we always have κ(e ♮ i ) = 0, as the outlier satisfies e ♮ i ∈ range(W ♮ ). In addition, we consider the following assumptions to assist identifying A ♮ and f ♮ : Assumption 3.4 (Class Specialists and Anchor Points). Assume that the following conditions hold: a. There exists a near-class specialist for each class k, i.e., ∀k ∈[K], ∃m k ∈ [M ] such that ∥A ♮ m k (k, :) -e ⊤ k ∥ ≤ ξ 1, where e k is a unit vector. b. There exists a near-anchor point sample for each class k in the dataset, i.e., ∀k ∈[K], ∃n k ∈ I c such that ∥f ♮ (x n k ) -e ⊤ k ∥ ≤ ξ 2, where e k is a unit vector.Assumption 3.4.a. is sometimes used in the crowdsourcing literature (e.g., [52] ) to characterize the expertise of annotators. Assumption 3.4.b. is often seen in loss correction based noisy label learning; see, e.g., [16, 21, 27] . Under Assumptions 3.2 and 3.4, we have the following result: n }, f ) be any optimal solution of (9) with I = n ∈ [N ] | e n = [( e (1) n ) ⊤ , . . . , ( e (M ) n ) ⊤ ] ⊤ ̸ = 0 .Suppose that the conditions in Lemma 3.1 holds, that we set C = |I|, and that Assumption 3.4 holds with ξ 1 , ξ 2 ≤ 1/K. Denote σ as the upper bound σ max (A ♮ m ) ≤ σ, ∀m. In addition, assume that ∀L ⊂ I c , |L| = N -2 |I c |, rank(F ♮ (:, L)) = K. Then, for some α > 0, and S > S 0 where S 0 as the smallest integer such that κ(e ♮ i ) ≥ ϵ g (S 0 ), ∀i ∈ I, the following result holds with probability greater than 1 -2/S -K/T α :E x∼Dx min Π ∥ f (x) -Π ⊤ f ♮ (x)∥ 2 2 ≤ K(η + ξ 1 + ξ 2 ), min Π ∥ A m -A ♮ m Π∥ 2 F = Kσ 2 (η + ξ 1 + ξ 2 ), ∀m,whereη 2 = O βM T α / √ S √ M log S + (∥X∥R F ) 0.25 , Π a permutation matrix, X is defined as before, and T = N -|I| . In addition, we have exact outlier detection, i.e., I = I.The proof is in Appendix D. We should mention that we set C = |I| for notation simplicity. With a notation-wise slightly more complicated definition of L, the same proof holds under C ≥ |I|, which leads to T = N -C and I ⊆ I. That is, over-estimated C still enables identifying I with the price of discarding some nominal samples. While the criterion (9) offers the desired identifiability, it requires the presence of class-specialist annotators and the anchor data points (c.f. Assumption 3.4), which are considered relatively restrictive [19, 31] . In [19] , the CE loss was combined with a simplex volume minimization-based regularization to establish identifiability of f ♮ under more relaxed conditions, namely, the sufficiently scattered condition (SSC) from the NMF literature [53] . We show that this is also viable in the presence of outliers:Theorem 3.6 (Enhanced Identifiability). Let ({ A m }, { e (m)n }, f ) be any optimal solution of (9) with W ≜ [ A ⊤ 1 , . . . , A ⊤ M ] ⊤ admitting the minimum volume of conv{ W } (i.e., the simplex spanned by its columns) over all possible optimal solutions. Assume that we set C = |I| and that F ♮ (:, I c ) satisfies the SSC. Under Assumptions 3.2 and the same conditions used in Lemma 3.1, the following result holds with probability greater than 1 -δ, when S grows to infinity:E x∼Dx ∥ f (x) -Π ⊤ f ♮ (x)∥ 2 2 = O(|I c | -5/8 (2∥X(:, I c )∥ F R F ) 1 4 + log(1/δ)/|I c |).In addition, we have ∥ A m -A ♮ m Π∥ F = 0, ∀m and I = I.The proof is relegated to Appendix E, which also holds for C ≥ |I| with slight modifications as discussed before. Theorem 3.6 shows that the target classifier can be accurately estimated in the presence of instance-dependent outliers, without needing anchor samples or class specialists.Implementation. Our learning losses allows relatively easy implementation and optimization. We consider the following regularized criterion: minimizeAm∈A,e(m) n ∈E,f ∈F L ce + µ 1 L outlier + µ 2 L vol .Note that we useL outlier = N n=1 ( M m=1 ∥e (m) n ∥ 2 2 +ζ) p 2where ζ > 0 and 0 < p ≤ 1 to approximate the column-sparsity constraint. The ℓ 2 /ℓ p nonconvex mixed quasi-norm has proven to be a very effective approximator for column sparsity [54] . In addition, as the function is differentiable, it offers an optimization-friendly surrogate.For the minimum-volume loss, we useL vol = -log det(F F ⊤ ), where F = [f (x 1 ), . . . , f (x N )].Note that the term encourages maximizing the volume of conv{F }, which in turn minimizes the volume of conv{W } under the model G = W F . Therefore, the volume of conv{W } can be minimized via using either log det(W ⊤ W ) or -log det(F F ⊤ ) as the regularizer. The reason why we choose the latter is because minimizing log det(W ⊤ W ) is ill-defined-the term encourages a rank-deficient W instead of a small-volume full-rank W . The remedy in the literature is to use log det(W ⊤ W + γI) with γ > 0 [54] or adding structural constraints (e.g., diagonal dominance) to W [19] , but these require more parameter tuning and more prior knowledge.The constraints on A m 's can be handled by adding softmax to the columns. The function class F can be a designated deep neural network model (e.g., ResNet), where the outputs are also constrained by softmax. The constraint on e Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?• The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions). • The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.) • The assumptions made should be given (e.g., Normally distributed errors). • It should be clear whether the error bar is the standard deviation or the standard error of the mean. Justification: Our work tackles the noisy labels problem which is ubiquitous, especially in the big data era, and hence bring positive impact to society. Guidelines:• The answer NA means that there is no societal impact of the work performed.• If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact. • Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations. • The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster. • The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology. • If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
related works: 
 Our development is related to works in transition matrix-based [14-19, 21, 23, 27-29, 33, 47, 55, 56] and sample selection-based [28, 33, 35, 37, 39] noisy label learning, confusion identification in crowdsourcing [14, 18, 57] , end-to-end crowdsourcing [20, 30, 31, 49] (with some paying particular attention to incomplete annotations [58, 59] ), and identifiability of NMF [53, 60] -see detailed discussions of the related work in Appendix B.A particular connection to highlight is the usage of multiple annotators as a key enabler of our identifiability guarantees. This result (implicitly) aligns with some recently proposed approaches that advocate for the use of multiple labels in learning under label noise [45, 49] . Specifically, the work by [45] established the identifiability of instance-independent label noise using the consensus of at least three similar data items with the same true label. Similarly, the work by [49] leveraged Kruskal's identifiability-based arguments to recommend using at least three noisy labels to establish the identifiability of the instance-dependent noise transition matrix. These works, particularly [49] , were more concerned with the theoretical limitations other than realizable methods. They did not connect the existence of repeated noisy labels to crowdsourcing, but used clusterability properties of datasets to support their arguments. In this work, we advocate diversity in crowd wisdom-labels from multiple annotators-based on an intuitive geometric characteristic of the model, which leads to clearly realizable implementations. 
experiments: 
 Baselines. The proposed method is compared with a number of existing baselines in noisy label learning. We choose several end-to-end crowdsourcing methods, namely, GeoCrowdNet(F)&(W) [31] , TraceReg [30] , CrowdLayer [20] , and Max-MIG [61] . We also employ four different instancedependent noisy learning approach, namely, MEIDTM [36] , PTD [27] , and BLTM [33] -which all use a single annotator. In addition, we present the result of VolMinNet [19] that uses the instanceindependent confusion model and the volume minimization regularization. We also use two noiserobust loss function-based approaches, namely GCE [10] and Reweight [21] . For baselines that were developed for single annotator cases, we train them using the labels after majority voting. Note that all the confusion matrix-based noise correction methods (including ours) inherently have a permutation ambiguity (cf. the Π term in Theorems 3.5 and 3.6). Hence, we report the highest classification accuracy attained among all possible permutation matrices for every method. In practice, Π can be removed by additional annotator inspection on several anchor samples, but we skipped these steps to keep the evaluation simple.Dataset. We consider the CIFAR-10 [62] and the STL-10 datasets [63] -see Appendix G for details.Experiment Setup. To generate multiple noisy labels, we use M = 3 machine annotators for each dataset. In order to simulate a wide range of annotation behaviors, we employ different classification and clustering methods such as k-nearest neighbors (kNN), logistic regression, and convolutional neural networks. Each machine annotator is trained by randomly choosing a subset of the training data. We control the labeling accuracies of these machine annotators by varying the size of the dataset and the number of epochs during their training phase. This results in annotators with different labeling qualities, with their average individual noise rates around 20% (good), 40% (medium), and 70% (low). This way, we set up the following three cases: (i) High Noise: Three machine annotators are with low, medium, and good quality, respectively. (i) Medium Noise: Two machine annotators are with medium quality and one machine annotator with good quality. (i) Low Noise: One machine annotators is with medium quality and two machine annotators with good quality. More details are in Appendix G.2.Neural Network and Optimizer Settings. We use ResNet-34 and ResNet-9 architectures [64] as the backbone to run all methods on CIFAR-10 and STL-10 datasets, respectively. For our proposed approach COINNet, we fix ζ = 10 -10 , p = 0.4, and µ 1 = µ 2 = 0.01. Adam [65] is used as the optimizer with weight decay of 10 -4 , learning rate of 0.01, and batch size of 512.More details and ablation studies with the hyperparameters are provided in Appendix G.Results. Table 1 presents the average testing accuracy of the methods. One can see that our approach COINNet consistently outperforms all baselines in different scenarios under test. Notably, the performance gap between COINNet and the second-best method is more significant in the high noise regime. For example, in the CIFAR-10 high noise scenario, COINNet shows around 4% improvement over the second-best performing baseline GeoCrowdNet(F). Another key observation is that the instance-dependent modeling based baselines such as MEIDTM, PTD, and BLTM, exhibit much degraded performance in high-noise scenarios, possibly due to their multi-stage procedures that accumulate errors easily under such circumstances. In addition, our approach outperforms the instance-independent confusion-based baselines, such as VolMinNet, Reweight and GeoCrowdNet(W), by nontrivial margins, showing that modeling instance-dependent outliers is indeed beneficial.In this section, we use three datasets to evaluate the algorithms.The first dataset that we use is the CIFAR-10N dataset [66] . The data has N = 60, 000 samples from K = 10 classes and the samples were labeled by M = 3 anonymous real annotators. The error rates of the 3 annotators are 17.23%, 18.12%, and 17.64%, respectively.LabelMe. We also test the algorithms over the LabelMe dataset [67, 68] . The dataset has N = 2, 688 samples from K = 8 classes, and M = 59 anonymous real annotators were involved in labeling the data. The average error rate is 25.95%. ImageNet-15N. In addition to existing datasets, we also acquire noisy annotations by asking AMT workers to annotate some images from ImageNet. We select K = 15 classes and submit randomly chosen images to AMT for labeling. Eventually we collect annotations for N = 2, 514 images from M = 100 anonymous real annotators, which serve as our training set. The average error rate of the annotators is 42.68%. The validation and testing sets have 1,462 and 13,157 images, respectively. We release the code and our acquired noisy annotations at https://github.com/ductri/COINNet.Settings. For CIFAR-10N, we employ the ResNet-34 architecture to serve as f . For the LabelMe and ImageNet-15N datasets, we employ similar settings as in [20] . Specifically, as the training sets are small, the pretrained VGG-16 [69] and CLIP [70] models are used to first extract image embeddings for the experiments on LabelMe and ImageNet-15N, respectively. The embeddings are then fed to f , which is a fully connected neural network with one hidden layer and 128 hidden ReLU units.The same encoders and architecture choices are employed for the all methods under test. For our approach COINNet, we set µ 1 = µ 2 = 0.1 for LabelMe, and µ 1 = µ 2 = 0.01 for CIFAR-10N and ImageNet-15N.Results. Table 2 presents the average testing accuracy of different methods on the three datasets. The proposed approach, COINNet, shows promising results in all cases, clearly outperforming the baselines by a noticeable edge. This is consistent with the machine annotator experiments. are the learned instance-dependent perturbations in the model (5) . The histogram plot of these scores in Fig. 2 clearly shows that our method does output two types of samples, i.e., nominal samples and outliers, based on these perturbations. In the figure, the images on the middle and the right are examples from the low and high outlier indicator value regimes, respectively. The images with high s n values show more instance-dependent confusion characteristics (such as background noise and blurring) compared to More experiments can be found in Appendix H. 
conclusion: 
 In this work, we considered the noisy label learning problem under a confusion matrix-based model. We developed theory and algorithms in the presence of instance-dependent outliers. Our study revealed that relying solely on single-annotator labels is insufficient for effective outlier detection under the model of interest. We further demonstrated that a crowdsourcing approach, leveraging multiple annotators and a sparsity-constrained loss function, can successfully detect outliers and identify the desired, label noise-free learning system under reasonable conditions. Our analyses and design feature a one-stage differentiable training loss that is optimization-friendly. Empirical results underscore the plausibility of our model and the effectiveness of our proposed method, showing noticeable performance improvements over existing baselines.Limitations. Our work explores a noise transition matrix-based model and treats instance-dependent noisy labels as outliers. The key assumption is that the outliers do not occur overwhelmingly. The assumption is useful, but also could be debatable. In principle, all labels could be generated in an instance-dependent manner. More sophisticated models are needed to deal with this more general case. In addition, our treatment is outlier structure-agnostic. The upshot is that this treatment can also help exclude the negative impacts of other types of outliers. However, the downside is that the structural prior knowledge of the outliers is not fully exploited. If the outlier-generating function could be learned, it can help detect "difficult samples" before sending for annotation, which would potentially save resources and reduce annotation errors. We leave this direction for future work. 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?Answer: [NA] Justification: We do not see any potential harm in publishing data and trained models of the proposed method.Guidelines:• The answer NA means that the paper poses no such risks.• Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters. • Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images. • We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make a best faith effort.12. Licenses for existing assets Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?Answer: [Yes]Justification: We have cited all datasets used in Section 5.Guidelines:• The answer NA means that the paper does not use existing assets.• The authors should cite the original paper that produced the code package or dataset.• The authors should state which version of the asset is used and, if possible, include a URL. • The name of the license (e.g., CC-BY 4.0) should be included for each asset.• For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.• If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset. • For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided. • If this information is not available online, the authors are encouraged to reach out to the asset's creators. 
new assets: 
 Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets? 
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)? 
institutional review board (irb) approvals or equivalent for research with human subjects: 
 Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?Answer: [NA]Justification: As mentioned above, our work 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.• Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper. • We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution. • For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review. 
 
 Appendix: Identifiability via Crowd Wisdom"The notations used in the paper are summarized in Table 3 .Table 3 : Definitions of the notations.Notation Definition x scalar in R x vector in R n , i.e., x = [x 1 , . . . , x n ] ⊤ [x] i or x(k) ith entry of the vector x [x] i:j subvector x such that [x] i:j = [x i , x i+1 , . . . , x j ] ⊤ , where j > i X matrix in R m×n [X] i,j or X(i, j) (i, j)th entry of X X(:, i) ith column of X X ≥ 0 X(i, j) ≥ 0, ∀ (i, j) X[:]vector representing column-wise stacking of X ∥x∥ 2Euclidean norm of x nnz(x) number of non-zero entries of x ∥x∥ 0 ℓ 0 norm of x; also equal to nnz(x)σ max (X) maximum singular value of X σ min (X) minimum singular value of X ∥X∥ 2 spectral norm or 2-norm of X, ∥X∥ 2 = σ max (X) ∥X∥ F Frobenius norm of X ∥X∥ 2,1 ℓ 2,1 norm of X, i.e., ∥X∥ 2,1 = n i=1 ∥X(:, i)∥ 2 ∆ K the probability simplex {x ∈ R K : i [x] i = 1, x ≥ 0} cone(X) conic hull of X: {y | y = Xθ, ∀θ ≥ 0} convex(X) convex hull of X: {y | y = Xθ, ∀θ ≥ 0, 1 ⊤ θ = 1} † pseudo-inverse ⊤ transpose |C| the cardinality of the set C [T ]{1, . . . , T } for an integer T I K identity matrix of size K × K 1 all-one vector with proper size 0 all-zero vector or matrix with proper size e i unit vector with the ith element being 1R n + nonnegative orthant of R n 1[A]Indicator function:1[A] = 1 if the event A happens, otherwise 1[A] = 0 CE(x, y)cross entropy function:- K k=1 1[y = k] log(x(k))In this section, we briefly review some of the existing works that is relevant to our proposed method. Noisy label learning has been a prominent research focus within the machine learning community for many years-see a survey of these methods in [71] . Among the numerous approaches proposed, those based on label transition matrix-based models (cf. the model in ( 2)) have been proven effective and several variants of the model have been introduced; see, e.g., [14-19, 21, 23, 27-29, 33, 47, 52, 55, 56] .A broad classification of them is of instance-independent models and instance-dependent models.Instance-independent Model-based Methods. One of the earliest instance-independent label noise models (i.e., assumingT ♮ (x n ) = A ♮ , ∀n in (2)) is the random classification model (RCN) [72] [73] [74] ,where true labels are flipped with a fixed noise rate independently at random. To extend this modeling to more general scenarios, class-conditioned model (CCN) was proposed [9] , where the noise rates are assumed to be dependent on the true-class the data item belongs. CCN model has led to the design of several statistically consistent classifiers, as the label transition matrix acts as a correction term for the loss associated with the noisy labels [21, 24, 26, 75] . To provably learn the CCN model, several notions are exploited, e.g., assuming the presence of anchor data items [21] , exploiting the clusterability of data items [45] , and minimizing the geometric volume of the transition matrix [19] .Instance-dependent Model-based Approaches.Instance-dependent label noise models are naturally more plausible. In these models, each data item has a label transition matrix dependent on the data's attributes (cf. Eq. ( 2)). Recently, a number of methods studied such models by using various simplified representations/parameterizations of the transition matrix T ♮ (x n ), e.g., imposing structural assumptions on label transition matrices [27, 41, 43] , bounding noise rates [28] , modeling the Bayes label transition matrix or posterior transition matrix instead of the true label transition matrix [33, 37, 40] , leveraging additional forms of supervision such as confidence scores [76] , and crafting specific regularization terms [36, 39, 42] . To be specific, the work in [27] assumed that the label transition matrix is a convex combination of several instance-independent transition matrices and the combination coefficients depend on the instances. The work in [28] assumed a known bounded noise rate and proposed an instance selection-based strategy. The method proposed in [39] also advocated an instance selection scheme, accompanied with a regularization term to combat instance-dependent label noise. In the work [36] , the simplification relies on the assumption that many data items that lie close to each other in the feature space have similar label transition matrices. These interesting developments showed empirical progresses, but the theoretical understanding has been limited. Particularly, the aforementioned identifiability issue was not resolved. In addition, most approaches resort to multi-stage training strategies which may be practically inefficient due to potential error propagation. For example, the approach in [33] first performs instance selection, then estimates the (Bayes-label) transition matrices, and finally estimates the classifier, in a three-stage training scheme. Similar multi-stage approaches are employed in [27, 28, 36] .Our approach is also related to sample-selection-based approaches in noisy label learning, e.g., clean sample selection-based methods [28, 33, 35, 37, 39] . However, most of them treat sample selection as a pre-processing step based on strict prior assumptions (e.g., known noise rates) and then estimate the transition matrix using these selected samples. In contrast, our proposed method and identifiability analysis offer a more principled approach by integrating sample selection with the learning of the classifier and transition matrices in an end-to-end fashion.Lemma 3.1 is re-stated below:Lemma C.1. Assume that the observed index pairs (m, n) ∈ S are sampled uniformly at random with replacement. Also assume f ♮ ∈ F, |I| ≤ C ≤ N/2, and that each[A m f (x n ) + e (m) n ] k , ∀A m ∈ A, ∀e (m) n∈ E, ∀f ∈ F are lower bounded by (1/β) for a certain β > 0. Then, with probability greater than 1 -δ, the following holds:1 N M N n=1 M m=1 ∥g ♮(m) n -g (m) n ∥ 2 2 ≤ ϵ g (S), ϵ g (S) = O βR S log S / √ S + log (β) √ log(1/δ) / √ S ,where . This addition is conceptually not hard to come up with, but the notations can be involved. Thus, we still derive the proof in detail.R 2 S = K 2 log (K) + K∥X∥ 2 F R F /S + CM K log √ N MProof: Consider the cross entropy-based learning criterion given by minimize Am∈A,f ∈F ,eEQUATIONEQUATION)where S = |S|, and CE(x, y) = -K k=1 1[y = k] log(x(k)).Let us denote the objective function in (11a) as follows:EQUATIONwhere g(m) nis given by g(m) n = A m f (x n ) + e (m)n , G is given byG =    g (1) 1 . . . g (1) N . . . . . . . . . g (M ) 1 . . . g (M ) N    =    A 1 f (x 1 ) + e (1) 1 . . . A 1 f (x N ) + e (1) N . . . . . . . . . A M f (x 1 ) + e (M ) 1 . . . A M f (x N ) + e (M ) N    ,and Y denotes the set of observed noisy labels, i.e., { y(m) n } (m,n)∈S . Let { A m }, { e (m)n } and f denote optimal solutions of the learning criterion (11) . Let us also define the following:EQUATIONwhereG ≜ {G ∈ R M K×N | g (m) n = A m f (x n ) + e (m) n , f ∈ F, e (m) n ∈ E, ∥E∥ 0 ≤ C, A m ∈ A},F ⊂ {f : R D → R K } is the neural network function class associated with the classifier function,E = {e ∈ R K | 1 ⊤ e = 0}, ∥E∥ 0 = N n=1 1 M m=1 ∥e (m) n ∥ 2 > 0 , A = {A ∈ R K×K | 1 ⊤ A = 1 ⊤ , A ≥ 0}.Let G ♮ represents the ground-truth such thatEQUATION)We aim to bound ∥G ♮ -G∥ F . Towards this goal, we adopt the proof strategy based on the viewpoint of matrix completion as employed in [31, 77] .Let us consider that we have S number of observations ω 1 , . . . , ω S such that ω s = (m s , n s , yns ), where each (m s , n s ) is sampled uniformly at random (with replacement) from [M ] × [N ], i.e., the sampling probability for each (m, n) is given by π m,n = 1 N M . In addition, the noisy observations are generated asy (ms) ns ∼ categorical(g ♮(ms) ns ).Let D ω denote the joint probability distribution from where the observations ω s are sampled. Then we define the following:L D (G, Y) ≜ E ω∼Dω [CE(g (m) n , y (m) n )].We consider the following set of relations:EQUATIONwhere the first inequality is obtained since G is the optimal solution as given by ( 13) and hence satisfies L S ( G; Y) ≤ L S (G ♮ ; Y). The last inequality is from the given assumption that G ♮ ∈ G (This is satisfied since it is given that f ♮ ∈ F and ∥E ♮ ∥ 0 ≤ C).Next, we consider the following set of relations:EQUATION)where we applied Pinsker's inequality [78, 79] for the first inequality and the last inequality uses the fact that ∥x∥ 1 ≥ ∥x∥ 2 for any vectorx ∈ R K having |[x] k | ≤ 1, ∀k ∈ [K].Here D KL (g 1 , g 2 ) denotes the Kullback-Leibler divergence between any g 1 , g 2 ∈ ∆ K , i.e., D KL (g 1 , g 15) with ( 16), we get2 ) = K k=1 [g 1 ] k log [g1] k [g2] k ] . Combining (EQUATIONNext, we proceed to characterize the R.H.S. of (17) . To achieve this, we invoke the following theorem derived from Theorem 26. EQUATIONwhere ℓ • G • S denotes the setℓ • G • S ≜ CE(g (m1)n1 , y (m1) n1 ), . . . , CE(g (m S ) n S , y (m S ) n S ) | G ∈ G and R(X ) denotes the empirical Rademacher complexity of the set X .To apply Theorem C.2, we need to characterize the terms z max and R(ℓ • G • S). The term z max can be characterized as below:z max = max [g] k > 1 β y∈[K] CE(g, y) ≤ max [g] k > 1 β y∈[K] - K k=1 1[y = k] log[g] k ≤ max [g] k > 1 β -log[g] k = log(β). (19)Note that in the above relation (19) , we utilize the given assumption that each [g] k ≥ 1/β, ∀g ∈ G.To characterize the Rademacher complexity R(ℓ • G • S), we consider its definition as follows [80] :EQUATION)where expectation is w.r. To apply Lemma C.3, let us define a vector z ≜ [g(m1) n1 ] 1 , [g (m1) n1 ] 2 , . . . , [g (m S ) n S ] K-1 , [g (m S ) n S ] K ∈ R SK and the set Z • S ≜ {z = [g (m1) n1 ] 1 , [g (m1) n1 ] 2 , . . . , [g (m S ) n S ] K-1 , [g (m S )n S ] K | G ∈ G}. Using these definitions, let us apply Lemma C.3 in (20) and get the following relation:EQUATIONwhere β is an upper bound of the Lipschitz constant of the cross entropy loss function CE(g, y) = -K k=1 1[y = k] log[g] k when g ∈ ∆ K with [x] k > (1/β).∀k. Next, we will characterize R(Z • S) using the covering number of the set Z • S. To define the covering number, let us first consider the concept of ϵ-net covering of a set. The ϵ-net covering of a set X (denoted as X ϵ ) is defined as the finite subset of X (i.e.,X ϵ ⊆ X ) such that for any x ∈ X , there exists an x ∈ X ϵ satisfying ∥x -x∥ 2 ≤ ϵ [82] . The smallest cardinality of the ϵ-nets of X is known as the covering number of X , which is denoted as N(ϵ, X ) .Let us consider a pair of vectors z S , z S ∈ Z • S as below:z S = [g (m1) n1 ] 1 , [g (m1) n1 ] 2 , . . . , [g (m S ) n S ] K-1 , [g (m S ) n S ] K ∈ R SK , g (ms) ns = A ms f (x ns ) + e (ms) ns , z S = [g (m1) n1 ] 1 , [g (m1) n1 ] 2 , . . . , [g (m S ) n S ] K-1 , [g (m S ) n S ] K ∈ R SK , g (ms) ns = A ms f (x ns ) + e (ms) ns ,where A ms belongs to the ϵ-net covering of A, f belongs to the ϵ-net covering of F , and e (ms) ns is the appropriate sub-vector belonging to the ϵ-net covering of E 0 .Let us also consider the following definitions:EQUATION1 ] 2 , . . . , [eEQUATION1 ] 2 , . . . , [e(M ) N ] K-1 , [e (M ) N ] K ∈ R N M K ,Then, we have the following relation due to triangle inequalityEQUATION)Next, consider the second term on the R.H.S. of ( 22):EQUATION)We also have the following relations for the first term on the R.H.S. of ( 22) :EQUATION)In the above set of relations, the first inequality is by triangle inequality. The second inequality uses that fact that (a + b) 2 ≤ 2a 2 + 2b 2 . The third inequality uses the fact that the Frobenius norm of A m (x n )'s are bounded by √ K and the ℓ 2 norm of f (x n ) is bounded by 1. Hence, combining ( 22)-( 24), we get that in order to obtain an ε-net covering for the set Z • S (i.e., ∥z -z∥ 2 ≤ ε), we only need to show that there exists a ε F • S = {[f (x 1 ), . . . , f (x S )] ∈ R K×S | f ∈ F, (m, n) ∈ S}, E N M = {[e (1)⊤ 1 , . . . , e (M )⊤ N ] ⊤ ∈ R KN M | e (m) n ∈ E, ∥E∥ 0 ≤ C, }, ∥E∥ 0 = N n=1 1 M m=1 ∥e (m)n ∥ 2 > 0 . Note that the full rank matrix A m ∈ R K×K can be represented as a K 2 -dimensional vector whose Euclidean norm is bounded by√ K. Hence, the cardinality of the ε 4 √ S -net covering for A m ∈ R K×K is at most 8K √ SK ε K 2 [80]. We consider the covering number corresponding to the function class F • S. Towards this, we invoke the following lemma:Lemma C.4. [51, Theorem 3.3] Let fixed nonlinearities (σ 1 , . . . , σ L ) and reference matrices (M 1 , . . . , M L ) be given, where σ i is ρ i -Lipschitz and σ i (0) = 0. Let spectral norm bounds (s 1 , . . . , s L ), and matrix (2,1)-norm bounds b 1 , . . . , b L be given. Let x 1 , . . . , x S be the S number of data items. Let h belongs to the following function class:H ≜ {h : R D → R K | h(x) = σ L (C 1 σ L-1 (C L-1 . . . σ 1 (C 1 (x) . . . )), ∀x ∈ R D },where C i ∈ R di×di-1 with d 0 = D and d L = K. Let H • S denote the family of matrices obtained by evaluating the data items with all choices of network H:H • S ≜ {[h(x 1 ), . . . , h(x S )] | C = (C 1 , . . . , C L ), ∥C i ∥ 2 ≤ s i , ∥C i -M i ∥ 2,1 ≤ b i , h ∈ H}, Then for any ϵ > 0, log N(ϵ, H • S) ≤ ∥X∥ 2 F R H ϵ 2 , where X = [x 1 , . . . , x S ], R H = log(2H 2 ) L j=1 s 2 j ρ 2 j i L (b i /s i ) 2/33 is called as the spectral-complexity upper bound of neural network function class H and H = max ℓ d ℓ .Using Lemma C.4, we get the cardinality of the ε 8 √ SK -net covering for F • N as below:N ε 8 √ SK , F • S ≤ exp 16K∥X S ∥ 2 F R F ε 2 ,where X S = [x 1 , . . . , x S ] ∈ R d×S and the parameter R F the spectral-complexity upper bound of F.Next, we proceed to get the cardinality of the εTo obtain the results in Theorem 3.5, we first show that the criterion correctly distinguishes the instance-dependent and instance-independent samples, i.e., I = I where we defineEQUATIONn 's and f are defined as in Theorem 3.5, and let e n = [( en ) ⊤ , . . . , ( e (M ) n ) ⊤ ] ⊤ . We first show that I c ⊆ I c . From Lemma 3.1, the following holds:EQUATIONThen the inequality also holds for any submatrix of the left hand side matrix. In particular, for i ∈ I and S > S 0 , ϵ g (S 0 ) > ϵ g (S) With I c = I c , we have the following relation from ( 30):≥ ∥W ♮ F ♮ (:, {i} ∩ I c ∩ I c ) + E ♮ (:, {i} ∩ I c ∩ I c ) -W F (:, {i} ∩ I c ∩ I c ) -E(:, {i} ∩ I c ∩ I c )∥ F = ∥W ♮ [f ♮ i , F ♮ (:, I c ∩ I c )] + [e ♮ i , 0, . . . , 0] -W [ f i , F (:, I c ∩ I c )] -[ e i , 0, . . . , 0]∥ F ≥ ∥W ♮ [f ♮ i , F ♮ (:, I c ∩ I c )] + [e ♮ i , 0, . . . , 0] -W [ f i , F (:, I c ∩ I c )]∥ F -∥[ e i , 0, . . . , 0]∥ F ≥ κ(e ♮ i ) -∥[ e i ,EQUATIONTo proceed, we invoke a result from the work [31] considering Assumption 3.4 satisfied, and the setI c is uniformly chosen from [N ], with probability at least 1 - 2 S - 2K N α , E x∼D min Π ∥ f (x) -Πf (♮ (x)∥ 2 2 ≤ c 3 (ζ + √ T Kκ) 2 T (1 - √ Kκ) 2 +64T -5/8 (2∥X∥ F R F ) 0.25 +16 2 log(4S) Nwhereζ 2 = 4 √ 2βKR(Z • S) + 8 log(β) 2 log(4S) S = O βR S log S √ S + log (β) log (1/δ) √ S , φ 2 = M T α 4 √ 2βKR(Z • S) + 8 log(β) 2 log(4S) S + 4/S κ = φ + ξ 1 + ξ 2 + √ Kξ 1 ξ 2 , X = [x n1 , . . . , x n S ], where (m s , n s ) ∈ S, R 2 S = K 2 log (K) + K∥X∥ 2 F R F S + CM K log √ N M , T = N -|I| .The proof of Theorem 3.6 follows similar steps in finite case presented in Theorem 3.5, except that we have the exact recovery of G when S → ∞. We repeat the derivation here for completeness.We first show that the criterion correctly distinguishes the instance-dependent and instanceindependent labels.EQUATIONn 's and f ) be an optimal solutions as state in Theorem E. From Lemma (3.1), the following holds as the number of observations grows S infinitely large:EQUATIONConsider the following relation:EQUATIONHere, each column of the matrix G ♮ is given byEQUATIONSimilarly, we can also defineEQUATION. . .e (M ) n    .From (32), we get thatEQUATIONWe will use contradiction-based argument towards this. Let us start by considering the case where there exists i ⋆ ∈ I c as well as i ⋆ ∈ I c holds. Then, combining (34) and ( 35) we getEQUATIONWe can rewrite the relation (36) asW F (:, I c ∩ I c ) = W ♮ F ♮ (:, I c ∩ I c ).Since any submatrix formed byN -2|I c | columns of F ♮ = [f (x 1 ), . . . , f (x N )] has rank K and that rank(W ♮ ) = K, we get that there exists a nonsingular matrix Q ∈ R K×K such thatEQUATIONNext, we consider the case where there exists i ⋆ ∈ I and i ⋆ ∈ I c . Then, again from (34) , (35) we get thatEQUATIONHowever, by applying the relation (37) in (38) , we getW ♮ Q f (x i ⋆ ) = W ♮ f ♮ (x i ⋆ ) + e ♮ i ⋆ =⇒ W ♮ Q f (x i ⋆ ) -W ♮ f ♮ (x i ⋆ ) = e ♮ i ⋆ =⇒ W ♮ q = e ♮ i ⋆ , where q = Q f (x i ⋆ ) -f ♮ (x i ⋆ ) is a nonzero vector since it is assumed that e ♮ i ⋆ ̸ = 0.The above relation implies that e ♮ i ⋆ ∈ range(W ♮ ) must hold which is a contradiction to the assumption that e ♮ i ⋆ / ∈ range(W ♮ ) when i ⋆ ∈ I. Hence, the relation ( 38) is feasible only if e ♮ i ⋆ = 0. It means that if there exists i ⋆ ∈ I c , we should have i ⋆ ∈ I c , leading to the conclusion that I c ⊆ I c . On the other hand, if I c ⊂ I c holds, thenN n=1 1 M m=1 ∥ e (m) n ∥ 2 > 0 > N n=1 1 M m=1 ∥e ♮(m) n ∥ 2 > 0 . Since e (m)n 's are the optimal solution of Problem ( 9) with minimalN n=1 1 M m=1 ∥ e (m) n ∥ 2 > 0 , the following should hold N n=1 1 M m=1 ∥ e (m) n ∥ 2 > 0 ≤ N n=1 1 M m=1 ∥e ♮(m) n ∥ 2 > 0 ,which is a contradiction. This implies that I = I must hold.Since I = I holds, we have the following relation from (32) :EQUATIONwhere we utilized the following notations:G(:, I c ) = W F (:, I c ), G ♮ (:, I c ) = W ♮ F ♮ (:, I c ), g i = [g (1)⊤ i , . . . , g (M )⊤ i ] ⊤ , i ∈ I c , W ♮ = [A ⊤♮ 1 , . . . , A ⊤♮ M ] ⊤ W = [ A ⊤ 1 , . . . , A ⊤ M ] ⊤ .Next, we connect the det(W ⊤ W ) term to our optimal solutions. This part is similar to the classical proofs in [84, 85] , with proper modifications. Consider the following result extracted from the proof of [84, Theorem 1]:Lemma E.1. Suppose a matrix Y ∈ R K×J satisfies Y ≥ 0, 1 ⊤ Y = 1 ⊤ , rank(Y ) = K, and SSC.Then, for any Y = QY satisfying Y ≥ 0, 1 ⊤ Y = 1 ⊤ , the following holds:| det(Q)| ≤ 1,The equality holds only if Q is a permutation matrix.Since W is the optimal solution of the criterion given by Theorem 3.6, the following holds:EQUATIONWe also have W ♮ and F ♮ (:, I c ) are of rank K. Hence, from (39), we get that W and F (:, I c ) satisfies W = W ♮ Q -1 , F (:, I c ) = QF ♮ (:, I c), for a certain invertible matrix Q. Let us assume that Q is not a permutation matrix, Then, we havedet(W ♮⊤ W ♮ ) = det(Q ⊤ W ⊤ W Q) = | det(Q)| 2 det( W ⊤ W ) < det( W ⊤ W ),where the last inequality is from Lemma E.1 using the SSC condition on F ♮ (:, I c ). Note that the result is a contradiction from (40) . Hence, Q must be a permutation matrix. This implies that the optimal solution W and F (:, I c ) satisfies the following:EQUATIONEQUATIONF Proof of Fact 2.1For rank(A ♮ ) = K, when N → ∞, the objective in (6) seeks the optimal solutions A ⋆ , f ⋆ and e ⋆ n such thatEQUATIONThis can be seen from Lemma 3.1 with M = 1. One solution that satisfies the equality (42) and the sparsity constraint in ( 6) isA ⋆ = I, f ⋆ (x) = A ♮ f ♮ (x n ) + e ♮ n, and e ⋆ n = 0, which can always hold when f is a universal function approximator. We train with batch size of 512, number of epochs 200, Adam optimizer with learning rate of 0.01 and learning rate scheduler OneCycleLR [86] . We initialize A m using an identity matrix going through softmax and e m = 0 for all m ∈ [M ]. We also apply standard data augmentation including random cropping, random flipping, when training on CIFAR-10, CIFAR-10N, and STL-10. The experiment results are averaged over 3-5 random trials. All runs have been conducted using either Nvidia A40 or Nvidia DGX H100 GPU. Each run of COINNet on CIFAR-10 takes about 60 minutes using Nvidia A40, and 30 minutes using Nvidia DGX H100 GPU.For machine annotator experiments, we consider the CIFAR-10 [62] and the STL-10 datasets [63] . The CIFAR-10 dataset consists of 60, 000 labeled color images of animals, vehicles and so on, each having a size of 32 × 32 and belonging K = 10 different classes. The images are split into training and testing sets with size 50,000 and 10,000, respectively. The STL-10 dataset consists of 13,000 labeled images from 10 different classes, similar to CIFAR-10. Of these, 5,000 images are designated for training and 8,000 for testing.Table 4 shows the details regarding the individual label noise rates and training methods in our experiments with machine annotators.For real annotation experiments, we use 2 popular public datasets: CIFAR-10N [66] and LabelMe [67, 68] , and construct the ImageNet-15N dataset with a higher number of annotators. All three datasets are labeled by anonymous annotators from the AMT platform. The CIFAR-10N is a "noisy" version of the popular CIFAR-10 dataset, containing 50,000 images for training, and a separate 10,000 images for testing. We randomly split the training set into 47,500 and 2,500 to use as train and validation set for all methods. Every image in CIFAR-10N has 3 labels.The LabelMe dataset comprises 2,688 images from eight distinct classes: highway, inside city, tall building, street, forest, coast, mountain, and open country. Out of the available images, 1,000 have been annotated by 59 AMT workers. In total, approximately 2,547 image annotations were collected, with labeling accuracy ranging from 0% to 100% and an average accuracy of 69.20%. To enhance the training dataset, standard augmentation techniques such as rescaling, cropping, and horizontal flips were applied, resulting in a training set of 10,000 images annotated by the same 59 workers-see more details in [67] . The validation set comprises 500 images, while the remaining 1,188 are reserved for testing.We select 15 classes from the ImageNet dataset with the intention of including easy-to-confuse classes. These classes are: dog, leopard, sports_car, tiger_cat, airship, aircraft_carrier, trailer_truck, orange, penguin, lemon, soccer_ball, airliner, freight_car, container_ship, passenger_car. We collect annotations for N = 2, 514 images from M = 100 anonymous real annotators. These serve as our training set. The average error rate of the annotators is 42.68%. The validation and testing sets have 1,462 and 13,157 images, respectively. We release the noisy annotations at https: //github.com/ductri/COINNet.Noisy Label Generation. Here, we consider labels corrupted by synthetically generated annotator confusions. To generate the confusion matrices, we utilize the following strategy. We control the instance-independent label noise rate using a parameter τ ∈ (0, 1). By employing this parameter, we construct the ground-truth confusion matrix A ♮ , where the diagonal entries of A ♮ are set as [A ♮ ] k,k = 1 -τ, ∀k, and the off-diagonal entries are set as [A ♮ ] k,j = τ K-1 , ∀k ̸ = j. First, we randomly select 1 -η fraction of the data samples and generate their labels using the instanceindependent confusion matrix A ♮ . For the remaining η percent of the samples, we adopt an instancedependent noise generation process, by following the strategy outlined in [27] . Specifically, for such "outliers", the label confusions vary depending on the features of such instances. Following the result in Fig. 2 , we show more examples of nominal data items and outlier data items as separated by our approach in Fig. 5 and Fig. 6 , respectively. Clearly, more instance-varying confusing characteristics are present in the latter case. Guidelines:• The answer NA means that the abstract and introduction do not include the claims made in the paper. • The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers. • The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings. • It is fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper.Justification: There is no new assets.Guidelines:• The answer NA means that the paper does not release new assets.• Researchers should communicate the details of the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc. • The paper should discuss whether and how consent was obtained from people whose asset is used. • At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.Justification: There is no human subjects or crowdsourcing experiments conducted in the work. All datasets are from published sources.Guidelines:• The answer NA means that the paper does not involve crowdsourcing nor research with human subjects. • Including this information in the supplemental material is fine, but if the main contribution of the paper involves human subjects, then as much detail as possible should be included in the main paper. • According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector. 


Decision: There is a clear consensus in the PC that this is a strong paper that should be accepted. Congratulations to the authors! I am requesting the author to carefully incorporate the suggestion provided by the review in the camera-ready version.

Reviews: review: paper_summary: paper_summary: This paper studied the identifiability problem of instance-dependent label noise with multiple annotators. To achieve the identifiability, this work first claimed a fact that only a proportion of all instances may have a labeling difficulty that significantly deviates from the general population. Then, it connected the problem to the uniqueness of non-negative matrix factorization with mild assumptions. Inspired by the identifiability result, this work proposed a end-to-end one-stage method to learn from crowds via identifying instance-dependent label noise. Experiments on multiple datasets with machine annotations and human annotators showed the effectiveness of the proposed method.
strength_weakness: strength_weakness: 1. As this work claimed, the number of annotators is important to identify the instance-dependent label noise, is there some experimental results verifying this analysis？

2.  For human annotations,  the annotations are usually sparse. Does the annotation sparsity level influence the identifiability and the performance of the proposed method? I suggest the authors do some experiments as existing works to clarify it [1-3].

3. The meaning of some terms, like "outliers", "the model of interest", "neural systems", is not clear when just reading the abstract. Besides, since the sparsity prior of the outliers is a basis assumption for this work, it should be referred to in the abstract.

[1] Label correction of crowdsourced noisy annotations with an instance-dependent noise transition model. NeurIPS 2023

[2] Coupled confusion correction: learning from crowds with sparse annotations. AAAI 2024

[3] Trustable co-label learning from multiple noisy annotators. TMM 2023
questions: questions: 1. The meaning of some terms, like "outliers", "the model of interest", "neural systems", is not clear when just reading the abstract.
2. It seems that there is a symbol that is not displayed in the restrictive condition of Eq.(6).
3. What does $e^\star_n$ mean in Line 129?
4. What does "over-canceling” mean in Line 211?
5. I suggest placing the learning-from-crowds methods after the learning-from-single-annotator methods in Table 1 and 2.
limitations: limitations: See above.
paper_summary: paper_summary: The paper extends further estimation of transition matrix in label noise learning. In previous studies, label noise is often assumed to be class-dependent. Hence, one can use the noisy label data and apply loss correction to learn a good classifier. The paper extends from such a modelling approach by considering most of samples having class-dependent label noise and some samples having class- and instance-dependent noise. Those with instance-dependent label noise are then considered as outlier in the newly proposed modelling approach. Despite such a modelling, it still results in a non-identifiable solution. To overcome that, the paper incorporates multiple labels from multiple annotators, so that one can solve for the nominal transition matrix and the classifier of interest. The paper also provides theoretical results to guarantee that the estimation holds under certain confidence level. Empirical results show that models trained on the new loss function performs competitively with prior methods.
strength_weakness: strength_weakness: The major weakness of the paper may lie at the assumption that majority of samples would share the same nominal transition matrix, while a few would have their own transition matices. However, this does not affect too much to the contribution of the paper.

Another weakness is the usage of multiple annotators, while the conventional noisy label learning does not consider any additional labels. Of course, some studies (e.g., [43]) show that using a single noisy label would result in non-identifiability, unless additional constraints are exploited. Nevertheless, multiple annotator setting would be closer to current practice. The downside is that there are not many multi-rater learning datasets for benchmarking.

### Minors
- Line 76: typo "traget" -> target
- The abbreviation "NMF" at line 100 is not defined.
- Line 111: $E(x_{n})$ is a matrix. Thus, please make it clear when specifying $E(x_{n}) > 0$.
questions: questions: I do enjoy reading the paper. It is coherent and easy to follow. I do not have any questions.
limitations: limitations: As mentioned in the weakness section above and in the conclusion of the paper, the paper only considers a few samples with instance-dependent label noise, while the remaining samples are class-dependent label noise, to reduce the complexity of the modelling and analysis. Such an assumption may not always hold in all settings.
paper_summary: paper_summary: The paper investigates the challenge of instance-dependent noisy labels, which are modeled using an instance-dependent confusion matrix reflecting annotator errors. Traditional approaches assume a consistent confusion matrix across instances, which simplifies the problem but is unrealistic. This study models the instance-dependent confusion matrices as outliers. The authors propose using a crowdsourcing strategy with multiple annotators and a specialized loss function to effectively detect outliers and identify the target classifier. The method is supported by extensive theoretical results. Experimental results also confirm the efficacy of the proposed method.
strength_weakness: strength_weakness: 1. Theorem 3.6 requires $S\rightarrow \infty$. However, we know if we have sufficient annotators, the aggregated noise rate could be 0, making the result trivial. It is interesting to show the result with finite $S$. 
2. The organization part of the proposed method could be polished.
questions: questions: 1. Does this method heavily rely on multiple annotators? If there is only one label for each example, is there any approximation method to generate extra labels to simulate multiple annotators?
2. Would existing estimators for noisy labels, such as [R1], provide a good initialization for the variable $\mathbf A_m$ in the proposed loss function?

[R1] Unmasking and improving data credibility: A study with datasets for training harmless language models. ICLR 2024.
limitations: limitations: NA
paper_summary: paper_summary: The paper addresses the problem of learning with noisy labels by considering a model where instance-dependent confusion matrices occur occasionally across the samples, and the rest of data share a common nominal confusion matrix. The paper claims two main contributions: (1) showing that a single confusion matrix is insufficient to identify outliers and proposing a crowdsourcing strategy with a column sparsity constraint to overcome this, and (2) presenting an end-to-end, one-stage learning loss that is differentiable and easily optimized. These contributions are validated through experiments that demonstrate improved testing accuracy.
strength_weakness: strength_weakness: Lack of large-scale datasets in experiments
questions: questions: Can the authors discuss any limitations their method might have in scenarios of highly imbalanced noise?
limitations: limitations: NA

Comments: title: Comments by Reviewer TTRF
comment: Thank you, the authors, for discussing the concerns I raised in my initial review. Regarding the public datasets, there are a number of available datasets that could be used in noisy label learning and multi-rater learning:
- 10 datasets mentioned in the NeurIPS 2022 paper: *Is one annotation enough? - A data-centric image classification benchmark for noisy and ambiguous label estimation*
- *dopanim: A Dataset of Doppelganger Animals with Noisy Annotations from Multiple Humans* available on zenodo with DOI 10.5281/zenodo.11479590

In addition, I have just found another (preprint) paper investigating the identifiability of the noisy label learning: *Towards the Identifiability in Noisy Label Learning: A Multinomial Mixture Approach*. In that paper, they showed that at least $2C - 1$ noisy labels per sample needed to make the label noise problem identifiable, where $C$ is the number of classes. This is, to me, more practical than [43] because the result of 3 noisy labels per sample in [43] is too optimistic, although in their paper, they also mentioned that it must be larger than 3 (but not explicitly say how many specifically). Hence, I think that it worths to add that into the discussion, especially the authors already showed that the more annotations, the better the estimation.

In summary, I believe that this is a good paper in the field of noisy label learning.