Noisy Label Learning with Instance-Dependent Outliers: Identifiability via Crowd Wisdom
Authors: Tri Nguyen
Shahana Ibrahim
Xiao Fu
Venue: NeurIPS 2024 spotlight (2024)
Keywords: Noisy label
instance-dependent label noise
sample selection
end-to-end learning
identifiability
crowdsourcing
Primary area: learning_theory
TL;DR: proposed an end-to-end noisy label learning system that provably identifies the target system (as if no label noise exists) in the presence of instance-dependent outliers.

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.

Noisy Label Learning with Instance-Dependent Outliers: Identifiability via Crowd Wisdom
Tri Nguyen" School of EECS
Shahana Ibrahim" Department of ECE
Oregon State University Corvallis, Oregon, USA
University of Central Florida Orlando, Florida, USA shahana ibrrhiimucc edu
nguuetr9@oregonsatte.co
Xíao Fu School of EECS
Oregon State University Corvallis, Oregon, USA xiao fu@orogonsttate.......o......... edu
Abstract
The generation of label noise is often modeled as a process involving probability transition matrix (also interpreted 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 model identification problem. Prior works along this line demonstrated appealing empirical performance, yet identifiability of the model was mostly established by assuming an instance-invarian confusion matrix. Having an (occasionally) instance-dependent confusion matrix across data samples apparently more realistic, but inevitably introduces outliers to the model. Our interest lies 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 identify the ground-truth classifier. Then, we prove that by employing a crowdsourcing strategy involving multiple annotators, a carefully designed loss function 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 mode-based annotations distinguish nominal data and instance-dependen outliers using a low- dimensional subspace. Experiments show that our learning scheme substantially improves outlier detection and the classifier's testing accuracy.
which show that crowdsourced
Introduction
Many strategies have been proposed avoid negative impacts label noise when training neural classifiers see, c.g., noisy label filtering ( robust loss design (9 [3] and noise generation modeling (or loss correction) [4.22] 22). the last genre, 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
Deep neural networks can easily overfit to noisy labels due to its excessive expressiveness
matrix. The transition matrix is interpreted as the "confusion matrix" [9 14 18 that can effectively
"Equal contribution.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

model the annotators' expertise level and the difficulty of annotating each class/sample, and thus is considered intuitive. Under this model, learning the "label noise-free" target neural classifier boils down to identifying the confusion matrix.
The confusion matrix-based models have proven quite useful in practice practice-algoriteee algorithms developed in this line of work often exhibits appealing empirical performance; see, c.g., 14 [9-21[23/31] In addition, these models admit interesting statistical and algebraic structures, leading to plausible results on identifiability of the confusion matrix and/or the "ground-truth classifier" -ii... the classifier that can be learned if no noisy annotations were present. However, most of the aforementioned early works considered an instance-invariant confusion matrix-i.a confusion matrix is not affected by sample features, but only classes -or analytical and computational simplicity. Considering instance- dependent confusion models is more realistic, as the sample characteristics. e.g., lightening and resolution of image, affect the annotation accuracy (32). The existence of such (at least occasionally occurred) instance-depender noisy labels inevitably introduces outliers to the instance- -nvaariann confusion models, leading to performance degradation. In general, learning under instance-dependent confusion matrices is heavily ill-posed. Hence, various problem-specifee structures were exploited to add regularization terms and constraints; see, e.g. (2 28 (3833/44) Nonetheless, unlike the instance- invariant confusion matrix case, identifiability guarantees of the target classifier have been largely under-studied. The lack of theoretical understanding also affects algorithm design design-mant many approaches in this domain had to resort to somewhat od-hoc treatments with multi-stage training procedures, often involving nontrivial pre- and post-processing; see (27 35 37 39 40).
Contributions. To advance understanding, we consider model where instance- instance-dependent confusion matrices occur occasionally across the samples, and the rest of data share a common nominal confusion matrix. This way, the instance-dependent noisy labels can be regarded as outliers. The model is motivated by the fact that only a proportion of all instances may have a labeling difficulty Our contributions are as follows:
that significantly deviates from the general population 33 44 45)
(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 employ crowd of annotators- -which is the common practice in data labeling (14 20 31). We show that, by incorporating a carefully designed column sparsity constraint to a coupled cross-entropy (CCE) loss from crowdsourcing (20) (3] 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-basee implementation. To be specific, our proposed learning loss allows approximate the column-sparsity constraint using a smoothed nonconvex Ép (where 0 < < 1) function based regularization (see (46)). This way, the overall loss differentiable and can be readily tackled by off-the-shelf optimizers. This is in contrast to many existing methods that involve multiple stages 40)
(c.g.. 28 23
33 33 (0)
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
2 Problem Statement
The Confusion Model and Learning Goal. Consider N data items J from K classes. Here, \ ) be the set of ground-truth labels, where Yn E [K]. Assume that yn 's are unobserved. Instead, we observe the "noisy" version {Tn N The label In e [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-guaramee
an E RD represents the feature vector of the nth data item. Let (y,
classifier using the data items (a,) IN and noisy labels J We consider the following expression of Pr(Øn = k((r,):
K
Pr(T.. = =k(x,)
Σ W=1
Pr(T. = kly, = (,,,,) (.
Note that Pr(yn- = k(ar)) is the ground-truth label distribution given the sample Fy This is also the distribution that the target classifier wishes to learn from. We represent the ground-trun classifier

---

using a function f IRD + R such that [ff )l& Pr(yn = k)x)), We call ff the ground-truth classifier as it the function that we aim learn and can be learned under ideal conditions (e.g.. when N = xo and the learner is a universal approximator), given that no noise is present. We define T RDD - R x such that (xn))) - Pr(O = klyn. k, Tn). Va..- That is, (xx,,, is the
label transition matrix or confusion matrix of sample .n. Let [g Pr(O k/ Accordingly,
iid. Da, is modeled as follows:
the noisy label generation process for n
g = (z,)
(2a)
In ~ categorical(gi).
(2b)
where categorical(g) denotes the K K-dimensional categorical distribution. Per the physical meaning of T (Zx,) and (xxx,, we have 1 (xx,) = 1T, " (xnn) 2 0 and 1 f* 1, f 2 0,
for all n. Under this model, the main goal is to learn f from { and (Fn J
Identifiability under Instance-Invarian T (z:). From (2a) it becomes apparent that learning f is not a straightforward task. Even if gf is observed (which is not), is hard to identify f* or T (2), from the product of (z (x,,). To tackle the identifiability challenge, a popular approach is to simplify 2 by assuming that all instances have the same confusion matrix, i.c., (*x,)= A with certain A RK*K for all [16 18
Under this assumption, The loss correction idea modifies the training loss of the classifier by taking the confusion matrix into consideration, e.g..
19
21
47 48
many used the "loss correction" " based formulation, e.g., 19 16
19 21 48]
N
K
minimize AEA.FEF
UnJa (f([A((z)))
(3)
N
n=lk=1
where the objective is a modified cross-entropy (CE) loss. The "noise correction" term A and f are used to learn A and f², respectively, On E {0, 1 denotes the one-hot encoding of the noisy label yn. and A and F denote appropriate constraint sets-ie., A = {A E R A'A=1" A 2 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 0o, the CE term enforces the learned
A and f satisfy g¹. (z, for all n [19]. Note that G [gi............. gyvl can be expressed as G A
= A where F ( ( f*(xx)], Consequently, Eq. 3 can be understood as learning A and F such that G R AF. As both A and F are nonnegative matrices (due to their physical meaning), the identifiability of F²b can be connected to uniqueness of the nonnegative matrix factorization (NMF) model G A see 19 21 45
These are interesting developments, yet the key assumption (z,) A for all n appears to be overly stringent. As mentioned, it makes sense to believe that at least proportion of samples have
-nstance-dependent T (xx,.'' 36 44 45 49) Not considering such samples may cause performance degradation.
Destanc--Depended Confusion-Inndue Outliers. When the instance-dependent confusion happens sparingly instead of overwhelmingly, we can re-express T*x,,) using the following decomposition:
T (m.) = A + (x:x),
where A E RR represents an cestance-independent eclass-dependent confusion waic is the nominal confusion matrix that reflects the general annotation difficulty of the dataset. The term E (Ixn represents the seetance-depedeett "perturbation". For many n's, E Ea(x,, = O. When E (rr, # 0, have (At + E² (a.,)) A ( + ei,- where eq. Ex,
Using 4). the model in 2ab can be expressed as follows:
(z e
Vn E I
gh
(5)
A ('))
Vn E T
where I and I represent the instance index set where E (xx) f 0 and its complement, respectively. In other words, I is the outlier index set.
remark that from this point on we will ignore the structure et (*,,) of the outliers. Disregarding the structure comes with some losses. For example, this way, method is not able
3

---

to learn (x,,, that could be of interest. Nonetheless, considering (=),,) renders extra modeling and computational burdens. Our treatment simplifies the subsequent analytical 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.
and computational
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;, and modify (3) as follows:
minimize (CEE
Unls log (Af( enlk:
N E1(lenlla > 03 SC
subject to
n=1
where = fe E IR | 0} is the constraint set for e,, 's (due to the probability simplex constraints the model parameters in (5) and C' is a scalar that is estimation of [Z]. The idea is to use the prior knowledge that e,, does not occur overwhelmingly as constraint. The hope that the solution of (6) can detect I, thereby enabling accurate estimation of A and fa. However, the following fact reveals a conflicting insight:
F are universal function approximators, that rank(A =K, and that N + co. Suppose that I + V. 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', ff e,,) is A = (. = f + et, and ea, = for all n.
Fact 2.1. Assume that all
This fact is easy to show (see Appendix FJ. yet 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 employed), does not suffice to recover the ground-trun truth f when there exists instance- dependent outliers (or any other types of outliers) under the model in (5) -under the condition that I is universal function approximator. The practical implication undesirable: as deep neural networks are powerful function approximators and are usually very expressive, Fact means that the learned neural networks easily overfit to outliers, even the sparsity prior on outliers is explicitly used in the loss function.
3 Proposed Approach
Intuition: Exploiting Crowd-induced Subspace. To get around the issues illustrated in Fact 2.1 our idea is to "create" a low- diw-eeeeniional subspace where the nominal data reside while the outhiers are likely far away from. To this end, we propose a crowdsoureing approach. Consider the scenario where M annotators label the dataset (æ,, 1 J The noisy label provided by an annotator for the
data item vn is denoted as yh [K] and follows the generation model as follows:
(m) ~ categorical(g gl ((m) A + ch(m)) Vm, n,
(6)
where A3, is the annotator m's 's confusion matrix and e, h(m) is the outlier term induced by annotator m's instance-depen -eeendee confusion.
Putting together, have the following expression:
gi ((1)
b(1)
A (x)) + +el
((1)
A + +eN : A f + ((1))
:(1)
NN
G
H(M)
H(M)
L f (x)) + +e H(M))
IN
wt pt - E
where F is defined as before, and
W = [(A)
(A IT.
ei, = (e(( (ct(A))TT
(8)
Denote ((m) as the index set where (m)) o 0. Then I= I(1) U... U((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 high- dimensional space, i.e., IR RMK However, the nominal data part W resides in K --diimnnsional subspace range( W where K < M K, multiple annotators are employed. More importantly, ej for E Z is M K -i-diinnsional vector and is unlikely to be inside range( W With this geometry. is much more likely that one can separate the outliers from the nominal data.
Next, we will use the above intuition to build 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 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):
minimize (AmEA) JEE
Lce
Σ
1 1x log [mm((a)) + c!Tm))
(9a)
(m,n)ES
k=1
N
M
subject to
Σ
|e
(m)) ||2 > 0
>0|50 sc,
(9b)
where S _ [M] x [N] denotes the set of observed noisy lahels indexed by (m, n) with S = |S| (note that all data items may not be labeled by annotator), (m) is the one-hot encoding of the annotator- provided label olm)) and C' is an estimate of [Z]. Here, the constraint sets F, A. and & are as defined
before. If e! is not considered, the objective function (9a) is sometimes referred to 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 99 and the theoretical characterizations of the constrained formulation is unknown.
We will use the following notations in our analysis. We use I S [N] to denote index set of the outliers, i.c., I = {n ea * 0}. We also consider that the function class in our learning problem, i..., F. has a complexity measure A In particular, we adopt the so-called peectal-complexxtn upper bound of the function class F [11 see Lemma C.4 in the Appendix.
We first establish that the criterion recovers the ground-truth ((m²) g
's with reasonable accuracy.
Specifically, we hope characterize the average estimation accuracy of gn a(mm)ss where g(())
Am (xx,, + en and A, 's, e.m")ss and f are estimated via solving (
Lemma 3.1. Assume that the observed index pairs (m, n) E S are sampled uniformly at random with replacement. Also assume f E F, [ C S N/2, and that each [Am (Ix) + (mm)) [k, AAm A, Ven (m)) greater than 1 8, the following holds:
E E,Vf E F are lower bounded by (1/B) for a certain 3 > 0. Then, with probability
N
M
3(m)
S (S)),, (g) = 0 (D8 log 5/V3 + log (B) vlo((1/8)/
NM
K2 log (K) KIX /.85/8 + CMK log v NM and X [ ungl are the annotated samples, in which (M,, E S for S.
where Ri
The proof is in Appendix C which uses similar idea as tion of the outliers. Lemma I reveals that the criterion G [cf. Eq, (7) from the noisy and incomplete observations of its entries, when S/C is sufficiently large. To proceed, we will need suite of assumptions and definitions:
31 Proposition 1] but takes into considera- 99 essentially recovers the complete matrix
Assumption 3.2. The outliers satisfy ct $ range W Vi E I, where rank(W3)) = K.
Assumption 3.2 presents the key condition to disassociate instance-dependee and instance- independent contusions. As discussed after Eq. (8). having larger M would decrease the possibility that any ed, belongs range (Wa). We also characterize the "quantity" that et, is perturbed from range( W²) in the following definition:
5

---

range( (W")
M =
M > 1
. clean samples outlier samples
x(e)) > x(e))
>
Figure 1: An illustration of outliers and nominal data items w.r.t. rangel W (left) when M = 1, e² E range(W*? (right) while M > I, it is highly likely that e * range 3) addition, the measure k(e) is larger for outliers that are farther from range W*).
Definition 3.3. The outlier impact score r((e)) of data defined as
k(ct)= A
min W.W.b.h.E& CCT 2
(IW*F*(: W + W f + whhl?)
(10)
where W [W = [A] A
Am E A}.
A larger score x(ee)) implies it is easier for our criterion to distinguish the outliers from the nominal data. Fig. [ iillustrates the geometry that we rely on to detect outliers. One can notice that when M = 1, we always have x(e)) = 0, as the outlier satisfies e E range A)
In addition, we consider the following assumptions assist identifying A and f²: Assumption 3.4 (Class Specialists and Anehor Points). Assume that the following conditions hold:
There exists near-class specialist for each class k i.e., Vk. E [K], 3mm
[M] such that || my (k) 2 S Ê1, where Gg is unit vector.
b. There exists near-anchor point sample for each class k in the dataset, i.e., Vk: E [K], 3ng E
Ie such that f e < E2, where e₁ is unit vector.
Assumption 3.4 is sometimes used in the crowdsourcing literature (e.g.. 52 to characterize the expertise of annotators. Assumption 3.4|b.e 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:
Theorem 3.5 (Identifiability and Generalization). Let (1Am). J. (el!") }, f) be any optimal solution of (9) with ī {NE [N] én ((el")) (eh ( TJ + 0.. Suppose that the conditions in Lemma 3.7 Tholds, that we set C [T] and that Assumption 3.4 holds with &,, S //K. Denote
a as the upper bound muax (At,) S a, Vm. In addition, assume that VL C I", [C| = N - 2 JI*, (:.
rank(F (;, C)) = K. Then, for some a > O, and S > So where Sn as the smallest integer such that
k(e?) 2 (So),, Vi E I, the following result holds with probability greater than 1 - 2/S K K/To:
E min [lf(z)
IIT (m)) )1) S K(n++
E2).
D>
min A A I Ko²(n (n + E1 + +2), Vm.
where 122 (SMTT) /VS (v log S + | ).2)) II a permutation matrix, X is defined as before, and T = N [Z] In addition, we have exact outlier detection, i.e., II
The proof is in Appendix D We should mention that we set C' [[] for notation simplicity. With notation wise slightly more complicated definition of L, the same proof holds under C 2 [Z]. which
leads to T = N C and I C Σ. 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. requires the presence of glass-speciallss 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 also viable in the presence of outliers:

---

Theorem 3.6 (Enhanced Identifiability). Let (1 ((Am). (el")),, f) be any optimal solution of (
with W & ..... AMl admitting the minimum volume of conv (w (W) (i.e., the simplex spanned by its columns) over all possible optimal solutions. Assume that we set C [I] and that (² I)) satisfies the SSC. Under Assumptions (.2) and the same conditions used in Lemma the following result holds with probability greater than 1 6, when S grows to infinity:
E 12--a
[11((0)) - II l = 1 -5/5
5/8
+ llg(1/6)//Z9)
In addition, we have A.A. A II O, Vm and I = I.
The proof relegated Appendix which also holds for C [Z] 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:
minimize Am E.A.ch EE.
Lce + M1 Loutlier + W μ2
[ m=1 lee 12+ where Ç > 0 and 0 < p S 1 to approximate the column-suee -parsitty constraint. The lp nonconvex mixed quasi-none has proven to be a very effective approximator for column sparsity [54]. In addition, as the function is differentiable, it offers
Note that we use Loutlier Em=
n=
an optimization -iriiiiaattio-feenlllyy surrogate.
For the minimum-volumg loss, we use Luol = - log det (FFF), where F = =f (xx)). f( Note that the term encourages maximizing the volume of conv (F), which in turn minimizes the volume of conv { under the model G = W.. Therefore, the volume of conv (W) can be minimized via using either log det W W) or - log det(FFF) as the regularizer. The reason why choose the latter is because minimizing log det (W W) is ill-defined term encourages rank-deficient W instead of small-volume full-rank W. The remedy in the literature is to use log det W + 7J) with 7 > 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 Am 's can be handled by adding omax the columns. The function class F can be a designated deep neural network model (c.g., ResNet), where the outputs are also constrained by
softmax. The constraint on (m² can be handled by parameterizing each e (mm - -(Te, (m)) en )1/K
where (((m) is trainable weight vector. More details of the implementation are provided in Ap- pendix G.1 We name approach Crowdsourcing- -bssed Qutlier-robust criterion and INstance-
dependence-aware deep neural Network learning, abbreviated as COINNet.
Related Works
Our development is related to works in transition matrix-based [1431991
56 35 37 39) noisy label learning. confusion identification in and sample selection based (3
33
crowdsourcing 18 57). end-to-end end crowdsourcing 30 (with some paying particular
attention incomplete annotations (58 (,), and identifiability of NMF [53] 60)
see detailed
discussions of the related work in Appendix
A particular connection highlight is the usage of multiple annotators a key enabler of 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-independees label noise using the consensus of at least three similar data items with the same true label. Similarly, the work by (4) leveraged Kruskal's 's santiiiabblity-baseee arguments to recommend using at least three noisy labels to establish the identifiability of the -estance-dependem 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 wixdom-labed from multiple annotators based on an intuitive geometric characteristic of the model, which leads to clearly realizable implementations.
7

---

Experiments
Baselines. The proposed method 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 instance- dependent noisy learning approach, namely, MEIDTM [36]. PTD [27]. and BLTM [33] (33)-which all use a single annotator. In addition, we present the result of VolMinNet (19) that uses the instance- independent confusion model and the volume minimization regularization. We also use two noise- robust loss function-bas based approaches, namely GCE (10) and Reweight (2T). For baselines that were developed for single annotator cases, 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 (ef. the II term in Theorems 3.5 and 3.6p. Hence, report the highest classification accuracy attained among all possible permutation matrices for every method. In practice, II can be removed by additional annotator inspection on several anchor samples, but we skipped these steps to keep the evaluation simple.
5.1 Experiments with Machine Annotations
Dataset. We consider the CIFAR-I0 and the STL-10 datasets
63 see Appendix G for details.
Experiment Setup. To generate multiple noisy labels, we use M =3 3 machine annotators for each dataset. In order to simulate 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 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 μı = μ2 = 0.01. Adam (65) is used as the optimizer with weight decay of 10 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 I 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 per- formance gap between COINNet and the second-best method is more significant in the high noise regime. For example, the CIFAR-IO 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 er- rors easily under such circumstances. In addition, our approach outperforms the Instance-independee confusion- based baselines, such VolMinNet, Reweight and GeoCrowdNet (W), by nontrivial margins, showing that modeling instance-dependent outliers is indeed beneficial.
5.2 Experiments Using Real Annotations
In this section, we use three datasets to evaluate the algorithms.
The data has N = 60, 000 samples from K = 10 classes and the samples were labeled by M anonymous real annotators. The error rates of the 3 annotators are 17.23%, 18.12%, and 17. 17.64% respectively.
CIFAR-1ON.
The first dataset that we use is the CIFAR-ION dataset 66
LabelMe. We also test the algorithms over the LabelMe dataset 67 68 The dataset has N = 2, 688 samples from K = classes, and M = 59 anonymous real annotators were involved in labeling the data. The average error rate is 25.95%.
8

---

Table Average classification accuracy using machine annotators in CIFAR-IO and STL- datasets
under different labeling scenarios. Bold black represents the best and blue represents the second best.
Method
CIFAR-10
STL-10
High Noise
Medium Noise
Low
Nouse
High Noise
Medium Noise
Low
Noise
PTD BLTM
61,98 1: 0.35
65.71
0.69
79.21
1 0.41
22.94
1 2.15
30.92 5.45
23.98 1 11.52
52.62 1 1.12
61.19 = 0.45
71.36 0.48
31.28
1: 2.78
30.57
1: 4.34
32.73 +: 3,45
VolMinNet:
49.83 + 2.66
50.93
3.34
70.44
7.32
42.38
+ 3.64
60.79
4.67
64.67
2,93
Reveight
59.73 +: 1.25
67.57
0.62
77.40
48.57
8.52
54.23
4: 3.86
54.67
6.93
GCE
52.14 0.67
63.90
0.12
0.32
58.35
1 0.74
60.65
1.69
61.70
+ 2.54
MEIDTM
51.38 + 0.62
56.20 0.65
0.50
55.50
1 0.52
6.220
59.84 +: 3.57
CrosdLayer
62.76 1: 3.12
67.24 2.26
3:302
47.83
1 5.51
61.46 4.58
66.64 2.48
TraceReg
64,90 +: 0.26
71.21 0.32
0.42
50.14
5.47
64.50
65.67 3.86
MaxMIC
51.92 1.10
68.45 0.21
0353
67.92
0.49
71.75
74.32 0.76
GeoCroudNlet (F)
67.22 + 0.27
71.11
0.50
8
64.70 + 0.82
66.15
68.40 + 0.31
GeoCroudNltt (M)
64.08 + 0.83
70.01 0.08
81.53 + 0.27
+ 4.62 49.30
61.54 +1.444.990
68.37 + 0.41
CDINNet: (Gurs)
71,22 + 0.72
73.31 0.09
84.14 0.38
70.12
T 0.48
7A.11 + 0.37
76.39 0.58
Table 2: Average classification accuracy on CIF, LabelMe, and ImageNet- 15N datasets, labeled by human annotators. Bold black represents the best and blue represents the second best. ImageNet-155
Method/Dataset
CIFAR-ION
LabelMe
PTD
89.32 E 0.24
84.18 1.36
65.53 = 0.18
BLTM
75.68 + 0.47
82.10 0.56
66.57 + 0.76
VolMinNett
86.58 + 0.21
79.97
63.11 = 1.08
Reweight
89.56 + 0.30
84.51 0.50
65.85 + 2.93
GCE
78.01 7.23
83.41
64.71 1.38
MEIDTM
68.69 + 0.31
83.53 + 0.21
72.66 + 0.58
CrowdLayer
87.38 + 0.43
82.80 0.90
61.36
TraceReg
86.57 0.24
82.83 + 0.23
68.43 + 0.12
MaxMIG
90.11 + 0.09
83.73 1 0.84
GeoCrowdNet (F)
87.19 + 0.37
87.21 + 0.39
80.45 + 1.77
GeoCrowdNee (W)
86.43 + 0.44
82.83 + 0.75
68.79 0.27
COINNet (Ours)
92.09 + 0.47
87.60 + 0.54
93.71 = 3.26
ImageNNet-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 httpss
Settings. For CIFAR-1ON, we employ the ResNet-34 architecture to serve as f. For the LabelMe and ImageNet-15N datasets, we employ similar settings as (20). Specifically, the training sets small, the pretrained VGG-16 [69] and CLIP (70) models are used to first extract image embeddings for the experiments LabelMe and ImageNet- 15N, respectively. The embeddings
then fed to f. which is 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 #2 = 0.1 for LabelMe, and μ2 = 0.01 for CIFAR-ION and ImageNet- 15N.
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.
Results.
Fig. 2 demonstrates the outlier identification results using the CIFAR-1ON dataset. Here, we define M
the outlier indicator as Sn > m==1 ||a|" I|,, Vn, where a(m) are the learned instance-dependent
perturbations in the model (5). The histogram plot of these scores in Fig. 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 8, values show more instance-dependent confusion characteristies (such background noise and blurring) compared to

---

100
003
0.00% Au
0.003
by 0.000
0.376
0.470
0.477
A.
0.376
Ag 0.377
Count
1.
0.00
0.05
0.10
0.15
Figure 2: Histogram of the learned outlier indicator values Sn images in the CIFAR-ION dataset (left), and examples with low (middle) and high (right) sn," more examples in Appendix H
>
m en
over all training
label: penguin
container.ship
liger.cal
freight.car
Au
label: penguin
1.50
orange
So 1,51 label:
Figure 3: Some examples from ImageNet- 15N with low (top) and high (bottom) Sn 's
those the middle. Overall, these results indicate the effectiveness our outlier-based model in real-world settings.
Fig. shows some examples selected from high-s, and low-s, regimes from the results output by COINNet in the ImageNet- 15N experiment. Similar as before, the images in the first row that have lower 8n scores are visually much easier to recognize. The images in the second row that have about 5 times higher 8,, scores are apparently more visually confusing.
More experiments can be found in Appendix H
6 Conclusion
In this work, we considered the noisy label learning problem under confusion matrix-based model. We developed theory and algorithms in the presence of desenneedeeennent outliers. Our study revealed that relying solely 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 sparsity-constraine 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-friende Empirical results underscore the plausibility of our model and the effectiveness of our proposed method, showing noticeable performance improvements
existing basclines.
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 leeance-depeneent manner. More sophisticated models are needed to deal with this more general case. addition, our treatment 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 not fully exploited. the outier-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.
10

---

Acknowledgment
The work was supported in part by the National Science Foundation (NSH) under Project IIS 200786.
References
[1] Devansh Arpit, Stanistaw Jastrzundefinedbsi, Nicolas Ballas, David Krueger, Emmanuel Bengio, Maxinder S. Kanwal, Tegan Maharaj, Asja Fischer, Aaron Courville, Yoshua Bengio, and Simon Lacoste-Julien. A closer look at memorization in deep networks. In Proceedings of International Conference on Machine Learning, page 233-242, 2017.
[2] Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning requires rethinking generalization. In Proceedings of International Conference on Learning Representations, 2016.
[3] Lu liang, Zhengyuan Zhou, Thomas Leung, Li-Jia Li, and Li Fei-Fei. MentorNet: Learning data-driven curriculum for very deep neural networks on corrupted labels. In Proceedings of International Conference on Machine Learning, volume 80, pages 2304-2313, 2018.
[4] Mengye Ren, Wenyuan Zeng. Bin Yang, and Raquel Urtasun. Learning to reweight examples for robust deep learning. In Proceedings of International Conference on Machine Learning, volume 80, pages 4334-4343 2018.
[5] Xingrui Yu, Bo Han, Jiangchao Yao, Gang Niu, Ivor Tsang, and Masashi Sugiyama. How does disagreement help generalization against label corruption? In Proceedings of International Conference Machine Learning, pages 7164-7173, 2019.
[6] Eran Malach and Shai Shalev-Shwartz. Decoupling "when to update" from "how to update". In Advances Neural Information Processing Systems, volume 30, 2017.
[7] Bo Han, Quanming Yao, Xingrui Yu, Gang Niu, Miao Xu, Weihua Hu, Ivor W. Tsang, and Masashi Sugiyama. Co-teaching: Robust training of deep neural networks with extremely noisy labels. In Advances in Neural Information Processing Systems, page 8536-8546, 2018
[8] Quanming Yao, Hansi Yang, Bo Han, Gang Niu, and James Tin-Yau Kwok. Searching to exploit memorization effect in learning with noisy labels. In Proceedings of International Conference 2020.
on Machine Learning, volume 119, pages
[9] Nagarajan Natarajan, Inderjit S Dhillon, Pradeep K Ravikumar, and Ambuj Tewari. Learning with noisy labels. In Advances in Neural Information Processing Systems, volume 26, 2013.
[10] Zhilu Zhang and Mert Sabuncu. Generalized cross entropy loss for training deep neural networks with noisy labels. In Advances in Neural Information Processing Systems, volume 31, 2018.
[11] Yisen Wang, Xingjun Ma, Zaiyi Chen, Yuan Luo, Jinfeng Yi, and James Bailey. Symmetric cross entropy for robust learning with noisy labels. In IEEE/CVT International Conference on Computer Vision (ICCV), pages 322-330, 2019.
[12] Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Curriculum loss: Robust learning and generalization against label corruption. In Proceedings of International Conference on Learning Representations, 2019.
[13] Yilun Xu, Peng Cao, Yuqing Kong, and Yizhou Wang. LDMI: A novel information-theoree loss function for training deep nets robust to label noise. In Advances in Neural Information Processing Systems, volume 32, 2019.
[14] Alexander Philip Dawid and Allan M Skene. Maximum likelihood estimation of observer error-rates using the EM algorithm. Applied statistics, pages 20-28, 1979.
[15] Scott Reed, Honglak Lee, Dragomir Anguelov, Christian Szegedy, Dumitru Erhan, and Andrew Rabinovich. Training deep neural networks on noisy labels with bootstrapping. 2015.
[16] Giorgio Patrini, Alessandro Rozza, Aditya Krishna Menon, Richard Nock, and Lizhen Qu Making deep neural networks robust to label noise: loss correction approach. In Proceedings of the IEEE conference computer vision and pattern recognition. pages 1944-1952, 2017.
[17] Jacob Whitehill, Ting fan Wu, Jacob Bergsma, Javier R. Movellan, and Paul L. Ruvolo. Whose vote should count more: Optimal integration of labels from labelers of unknown expertise. In Advances in Neural Information Processing Systems, volume 22, pages 2035-2043, 2009.
11

---

[18] Yuchen Zhang, Xi Chen, Dengyong Zhou, and Michael I. Jordan. Spectral methods meet EM: provably optimal algorithm for crowdsoureing. Journal of Machine Learning Research, 17(102): -44, 2016.
[19] Xuefeng Li, Tongliang Liu, Bo Han, Gang Niu, and Masashi Sugiyama. Provably end-to-end laiel-noise learning without anchor points. In Proceedings of International Conference on Machine Learning, pages 6403-6413, 2021.
[20] Filipe Rodrigues and Francisco Pereira. Deep learning from crowds. Proceedings of the AAAI Conference on Artificial Intelligence, 32(1), 2018.
[21] Tongliang Liu and Dacheng Tao. Classification with noisy labels by importance reweighting. IEEE Transactions on Pattern Analysis and Machine Intelligence, 38:447-461, 2016
[22] Tri Nguyen, Shahana Ibrahim, and Xiao Fu. Deep clustering with incomplete noisy pairwise annotations: A geometric regularization approach. In International Conference on Machine Learning, pages 26080-26007. PMLR, 2023.
[23] Yang Liu and Hongyi Guo. Peer loss functions: Learning from noisy labels without knowing noise rates. In Proceedings of the 37th International Conference Machine Learning, volume 119, pages 6236, 2020.
[24] Yivan Zhang, Gang Niu, and Masashi Sugiyama. Learning noise transition matrix from only noisy labels via total variation regularization. In Proceedings of the 38th International Conference on Machine Learning, volume 139, pages 12501-12512, 2021.
[25] Kiran K Thekumparampil, Ashish Khetan, Zinan Lin, and Sewoong Oh. Robustness of conditional gans to noisy labels. In Advances in Neural Information Processing Systems, volume 31, 2018.
[26] Xiaobo Xia, Tongliang Liu, Nannan Wang, Bo Han, Chen Gong, Gang Niu, and Masashi Sugiyama. Are anchor points really indispensable in label-noise learning? In H. Wallach, H. Larochelle. A. Beygelzimer, F. d' d'Alché-But E. Fox, and R. Gamett, editors, Advances in Neural Information Processing Systems, volume 32, 2019.
[27] Xiaobo Xia, Tongliang Liu, Bo Han, Nannan Wang. Mingming Gong, Haifeng Liu, Gang Niu, Dacheng Tao, and Masashi Sugiyama. Part-dependent label noise: Towards instance- dependent label noise. In Advances in Neural Information Processing Systems, volume 33,
pages 7597-7610, 2020.
[28] Jiacheng Cheng, Tongliang Liu, Kotagiri Ramamohanarao, and Dacheng Tao. Learning with bounded instance and deeendden label noise. In Proceedings of International Conference on Machine Learning, volume 1 119, pages
2020.
[29] David Karger, Sewoong Oh, and Devavrat Shah. Iterative learning for reliable crowdsourcing systems. In Advances in Neural Information Processing Systems, volume 24, pages 1953-1961, 201
[30] Ryutaro Tanno, Ardavan Saeedi, Swami Sankaranarayanan, Daniel C. Alexander, and Nathan Silberman. Learning from noisy labels by regularized estimation of annotator confusion. 2019 IEEE/VV Conference on Computer Vision and Puttern Recognition (CVPR), pages 11236- 11 11245, 2019.
[31] Shahana Ibrahim. Tri Nguyen, and Xiao Fu. Deep learning from crowdsourced labels: Coupled cross-entropy minimization, identifiability, and regularization. In Proceedings of International Conference Learning Representations, 2023.
[32] Kristen Grauman and Bastian Leibe. Visual Object Recognition. Synthesis Lectures Artificial Intelligence and Machine Learning. Morgan & Claypool Publishers, 2011.
[33] Shuo Yang, Erkun Yang, Bo Han, Yang Liu, Min Xu, Gang Niu, and Tongliang Liu. Estimating instance-dependent Bayes-label transition matrix using deep neural network. In Proceedings of International Conference on Machine Learning, 2021.
[34] Yu Yao, Tongliang Liu, Mingming Gong, Bo Han, Gang Niu, and Kun Zhang. Instance- dependent label-noise learning under a structural causal model, 2021.
[35] Zhaowei Zhu, Tongliang I Liu, and Yang Liu, second-order approach to learning with instance- dependent label noise, 2021.
12

---

[36] D. Cheng, T. Liu, Y. Ning, N. Wang, B. Han, G. Niu, X. Gao, and M. Sugiyama. Instance- dependent label-noise learning with manifold-reullaiieed transition matrix estimation. In IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), pages 16609- 16618. jun 2022.
[37] Shikun Li, Xiaobo Xia, Jiankang Deng. Shiming Ge, and Tongliang Liu. Transferring annotator- and instance-dependent transition matrix for learning from crowds. arXiv preprint arXiv:2306.08 16, 2023.
[38] Qizhou Wang, Bo Han, Tongliang Liu, Gang Niu, Jian Yang, and Chen Gong. Tackling instance- dependent label noise via a universal probabilistic model. Proceedings of the AAAI Conference on Artificial Intelligence, 35(1 101101111111,,,, May 2021.
[39] Hao Cheng, Zhaowei Zhu, Xingyu Li, Yifei Gong, Xing Sun, and Yang Liu. Learning with instance-dependent label noise: A sample sieve approach. In Proceedings of International Conference on Learning Representations, 2021.
[40] Zhimeng Jiang, Kaixiong Zhou, Zirui Liu, Li Li, Rui Chen, Soo-Hyun Choi, and Xia Hu. An information fusion approach to learning with instance-dependent label noise. In Proceedings of International Conference on Learning Representations, 2022.
[41] Yikai Zhang, Songzhu Zheng. Pengxiang Wu, Mayank Goswami, and Chao Chen. Learning with feature-dependent label noise: progressive approach. Proceedings of International Conference Learning Representations, 2021.
[42] Le Zhang. Ryutaro Tanno, Mou-Cheng Xu, Chen Jin, Joseph Jacob, Olga Cicarrelli, Frederik Barkhof, and Daniel Alexander. Disentangling human error from ground truth in segmentation of medical images. In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages 15750-15762. Curran Associates, Inc., 2020.
[43] Hui Guo, Boyu Wang, and Grace Yi. Label correction of crowdsourced noisy annotations with an mestance-dependen noise transition model. In Advances in Neural Information Processing Systems, 2023.
[44] Qizhou Wang, Jiangchao Yao, Chen Gong, Tongliang Liu, Mingming Gong, Hongxia Yang, and Bo Han. Learning with group noise. Proceedings of the AAAI Conference on Artificial Intelligence, 35:10192-10200, 05 2021.
[45] Zhaowei Zhu, Yiwen Song, and Yang Liu. Clusterability as an alternative to anchor points when learning with noisy labels. In Proceedings of the 38th International Conference on Machine Learning, volume 139, pages 22912-12923 2021.
[46] Xiao Fu, Wing-Kin Ma, José Bioucas- Dias, and Tsung-Han Chan. Semiblind hyperspectral unmixing in the presence of spectral library mismatches. arXiv preprint arXiv:1507.01661. 2015.
[47] Qiang Liu, Jian Peng, and Alexander T Ihler. Variational inference for crowdsoureing. In Advances in neural information processing systems, volume 25, pages 692-700, 2012.
[48] Xiyu Yu, Tongliang Liu, Mingming Gong, and Dacheng Tao. Learning with biased comple- mentary labels. In Proceedings of the European conference on computer vision (ECCV), pages 68-83, 2018.
[49] Yang Liu, Hao Cheng, and Kun Zhang. Identifiability of label noise transition matrix. In Proceedings of the 40th International Conference on Machine Learning, volume 202, pages 21 21475-21496, 2023.
[50] Zhendong Chu. Jing Ma, and Hongning Wang. Learning from crowds by modeling common confusions. In Proceedings of the AAAI Conference on Artificial Intelligence, 2021.
[51] Peter L Bartlett, Dylan J Foster, and Matus J Telgarsky. Spectrally-normaaizee for neural networks. In Advances in Neural Information Processing Systems, volume 30, 2017.
normalized margin bounds
[52] Shahana Ibrahim, Xiao Fu, Nikos Kargas, and Kejun Huang. Crowdsourcing via pairwise co-occurrences: Identifiability and algorithms. In Advances in Neural Information Processing Systems, volume 32, pages 7847-7857. 2019.
[53] K. Huang, N. Sidiropoulos, and A. Swami. Non-negative matrix factorization revisited: Unique- ness and algorithm for symmetric decomposition. IEEE Trans. Signal Process., (2(1):211-2 2014.
13

---

[54] Xiao Fu, Kejun Huang, Bo Yang, Wing-Kin Kin Ma, and Nicholas D Sidiropoulos. Robust volume minimization-basee matrix factorization for remote sensing and document clustering. IEEE Trans. Signal Process., 64(23))6254 6268, 2016.
[55] Rion Snow, Brendan O' O'Connor, Daniel Jurafsky, and Andrew Y Ng. Cheap and it good?: evaluating non-expert annotations for natural language tasks. In Proceedings of the Conference on Empirical Methods in Natural Language Processing, pages 254 354-263, 2008
is
[56] Peter Welinder, Steve Branson, Pietro Perona, and Serge J Belongie. The multidimensional wisdom of crowds. In Advances in Neural Information Processing Systems, pages 2424-2432. 2010.
[57] Panagiotis A Traganitis, Alba Pages-Zamora, and Georgios B Giannakis. Blind multiclass ensemble classification. IEEE Trans. Signal Process. 66(18):4737-4752, 2018.
[58) Hansong Zhang, Shikun Li, Dan Zeng, Chenggang Yan, and Shiming Ge. Coupled confu- sion correction: Learning from crowds with sparse annotations. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 38, pages 16732-16740, 2024.
[59] Shikun Li, Tongliang Liu, Jiyong Tan, Dan Zeng, and Shiming Ge. Trustable co-label learning from multiple noisy annotators. IEEE Transactions on Multimedia, 25:1045-100 1057, 2021.
[60] Nicolas Gillis. Nonnegative Matrix Factorization. Society for Industrial and Applied Mathe- matics, 2020.
[61] Peng Cao, Yilun Xu, Yuqing Kong, and Yizhou Wang. Max-Mig: An information theoretic approach for joint learning from crowds. In Proceedings of International Conference on Learning Representations, 2019.
[62] Alex Krizhevsky. Learning multiple layers of features from tiny images. 2009.
[63] Adam Coates, Andrew Ng, and Honglak Lee. An analysis of single-layer networks in unsuper- vised feature learning. In Proceedings of International Conference on Artificial Intelligence and Stutistics, volume 15, pages 215-223, 2011.
[64] Kaiming He, X. Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. IEEE Conference on Computer Vision and Pattern Recognition, pages 770-778. 2016.
[65] Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In Proceedings of International Conference on Learning Representations, ICLR, 2015.
[66] 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.
[67] Filipe Rodrigues, Mariana Lourenco, Bernardete Ribeiro, and Francisco C. Pereira. Learning supervised topic models for classification and regression from crowds. IEEE Transactions on Pattern Analysis and Machine Intelligence, (9(12):449-224 2017.
[68] Bryan C. Russell, Antonio Torralba, Kevin P. Murphy, and William T. Freeman. Labelme: A database and web-based tool for image annotation. International Journal of Computer Vision, 77:157-173, 2007.
[69] Karen Simonyan and Andrew Zisserman. Very deep convolutional networks for large-scale image recognition. arXiv preprint arXiv:
2014.
[70] Alec Radford, Jong Wook Kim, Chris Hallacy, Aditya Ramesh, Gabriel Goh, Sandhini Agarwal, Girish Sastry, Amanda Askell, Pamela Mishkin, Jack Clark, et al. Learning transferable visual models from natural language supervision. In International conference on machine learning. pages -7633 PMLR, 2021.
[71] Hwanjun Song, Minseok Kim, Dongmin Park, Yooju Shin, and Jae-Gil Lee. Learning from noisy labels with deep neural networks: A survey. IEEE Transactions on Neural Networks and Learning Systems, pages 1-19, 2022.
[72] Dana Angluin and Philip Laird. Learning from noisy examples. Mach. Learn., 2(4):343-370, apr 1988.
[73] Javed A. Aslam and Scott F. Decatur. On the sample complexity of noise-tolerant learning. Inf. Process. Lett., 57(():17941)))))) 195, feb 1996.
14

---

[74] Michael Kearns. Efficient noise-tolerant learning from statistical queries. 45(6)9983-1066 nov 1998.
J. ACM,
[75] Clayton Scott, Gilles Blanchard, and Gregory Handy. Classification with asymmetric label noise: Consistency and maximal denoising. In Shai Shalev-Shwartz and Ingo Steinwart, editors, Proceedings of the 26th Annual Conference Learning Theory, volume 30, pages 489-511, 2013.
[76] Antonin Berthon, Bo Han, Gang Niu, Tongliang Liu, and Masashi Sugiyama. Confidence scores make instacce-dependen label-noise learning possible. In Proceedings International Conference on Machine Learning, volume 139, pages 825-836, 2021.
[77] Mark A. Davenport, Yaniv Plan, Ewout van den Berg, and Mary Wootters. 1-bit matrix completion. Information and Inference: A Journal of the IMA, 3(3): -299,22,---- 2014.
[78] M S Pinsker. The information stability of gaussian random variables and processes (in Russian). Dokl. Akad. Nauk SSSR, 133:28-30, 1960.
[79] A.A. Fedotov, P. Harremoes, and F. Topsoe. Refinements of pinsker's inequality. IEEE Transactions on Information Theory, 4961:149,,, 2003.
[80] Shai Shalev-Shwartz and Shai Ben-David. Understanding Machine Learning: From Theory to Algorithms. Cambridge University Press, 2014.
[81] Andreas Maurer. A vector-contraction inequality for rademacher complexities. ArXiv,
abs/ Abs/1605.00251, 2016.
[82] Roman Vershynin. Introduction to the non-asymptotic analysis of random matrices, page 210-268. Cambridge University Press, 2012.
[83] G. Raskutti, Martin Wainwright, and Yu. Minimax rates of estimation for high-dimensional linear regression over l by-balls. IEEE Transactions Information Theory, 57:6976 6994, 2011.
[84] X. Fu, W.-K. Ma, K. Huang, and N. D. Sidiropoulos. Blind separation of quasi-stationary sources: Exploiting convex geometry in covariance domain. IEEE Trans. Signal Process., (3(9):230-2322) May 2015.
[85] Xiao Fu, Kejun Huang, and Nicholas D Sidiropoulos. On identifiability of nonnegative matrix factorization. IEEE Signal Process. Lett., 25(3):328-333 332, 2018.
[86] Leslic N Smith and Nicholay Topin. Super-convergence: Very fast training of neural networks using large learning rates. In Artificial intelligence and machine learning for multi-domain operations applications, volume 1006, pages 369-386, 2019.
15

---

Supplementary Material of " Noisy Label Learning with Instance-Dependent Outliers: Identifiability via Crowd Wisdom"
A
Notation
The notations used in the paper summarized in Table
Table 3: Definitions of the notations.
Notation
Definition
x
scalar in R
x
vector in R", i.e.,
[1 Fn
x (Ak)
ith entry of the vector I
[ bsf
subvector æ such that [ j:j [2i Js+1.
where >> i
X
matrix in RT
X 1.j or
X (i,
i, )hh entry of X
X
(1.
ith column of X
X
0
X (i, 2 0, A (i,))
X
vector representing column- wise stacking of X
Euclidean norm of æ
nnz ar)
number of non-zero entries of to norm of æ:; also equal to nnz(x))
maxx
maximum singular value of X
min
minimum singular value of X
X
2
spectral norm or 2-norm of X. [X] 2 max X
X
Frobenius norm of X
X
2.1
2 norm of X, i.c., X 2.1
X
A K
the probability simplex x E R
x
1,
0}
cone X)
conic hull of X:
y
y
=
X0,
40 2 0
convex X)
convex hull of X:
y X0,
v0
2 0, 1,
=
pseudo-inverse
transpose
the cardinality of the set C
(l.... T) for an integer T
K
identity matrix of size K K
all-one vector with proper size
0
all-zero vector or matrix with proper size unit vector with the ith element being nonnegative orthant of R"
e;
R7
1 [[A]
Indicator function: 1 [[A] = if the event happens, otherwise [[A] 0
CE(x, y)
cross entropy function: Σx= 11 = k] log()(k))
B
Related Work
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 sce survey of these methods in (71). Among the numerous approaches proposed, those based on label transition matrix- several variants of the model have been introduced; see, e.g., 11419 21 23 27 29
models (cf. the model in (2) have been proven effective and
33 47
55 56]
A broad classification of them is of instance- indeeeeeddde models and instance dependennddedde models.
Instance-indeppeneet Model-based Methods. One of the earliest Destance-independee label noise models (i.e., assuming T (x..) = A?, Vn in 2 is the random classification model (RCN) (72-74), where true labels are flipped with fixed noise rate independently at random. To extend this modeling to more general scenarios, elass-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
16

---

design of several statistically consistent classifiers, as the label transition matrix acts as correction
term for the loss associated with the noisy labels 241 75]. To provably learn the CCN model,
several notions are exploited, e.g., assuming the presence of anchor data items [2T]. exploiting the clusterability of data items [45. and minimizing the geometric volume of the transition matrix (19).
Instance denendet Model-based Approaches. Instance-dependent label noise models are naturally more plausible. In these models, each data item has label transition matrix dependent on the data's s attributes (cf. Eq. Recently, a number of methods studied such models by using
various simplified
the transition matrix (2,,,, e.g.. imposing
structural assumptions on label transition matrices (27 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] (36 42]. To be specific, the work [27] assumed that the label transition matrix is convex combination of several instance- instance-indepennee independent transition matrices
and the combination coefficients depend on the instances. The work (28) assumed 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 (35 first performs instance selection, then estimates the (Bayes-label) transition matrices, and finally estimates the classifier, in three-stage
training scheme. Similar multi-stage approaches are employed in 27 28 28.3)
Our approach is also related to sample-selection-bee
approaches in noisy label learning, e.g., clean sample selection-based methods [38] 35 37,39) 39]. However, most of them treat sample selection as pre-processing step based 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 more principled approach by integrating sample selection with the learning of the classifier and transition matrices in an end-to-end fashion.
C Proof of Lemma 3.1
Lemma is re-stated below:
Lemma C.1. Assume that the observed index pairs (m, n) E S are sampled uniformly at random with (m))
replacement. Also assume f E F, | S C S N/2, and that each [Am (xx) + en jk, vAm
A, Velm) E Ef F are lower bounded by (1/B) for certain > O. Then, with probability greater than 1 8, the following holds:
N
M
l1g
((m)
Inh (mm) (c)(s,, (g(S)
( 5/13++ log (B) v Vlo((1 /lo((1/0//55) 181/v5)
NM
1=1 m=1
where Wy = K2 log (K) + X + CMK / NM and X = [a Bnsl are the annotated samples, which (m, na) S for r S.
The proof is essentially viewing the g estimation problem quantized matrix completion problem with missing blocks. The key ideas and steps all follow the proof of the end-to-end
crowdsourcing work 31 Proposition 1] with the additional consideration of h(m) This addition is conceptually not hard to come up with, but the notations can be involved. Thus, we still derive the proof in detail.
17

---

Proof: Consider the cross entropy based learning criterion given by
minimize Am AmEA,EEFEE
CE(Amf(a)) + 2
(11a)
S
EE
(m,m))S
N
M
subject to
Σ
1
e
m
12
0
SC
(11b)
where S |S], and CE(x, y) = - 1 k] (k))
Let us denote the objective function (1a) follows:
Ls(G:)) _
Σ
CE(g.. (m)) "
(12)
(m.n)ES
where gn (m)
is given by gm
(m)
Am f f(x)) + (mm)
G is given by
gi
9N
A1f(x1) +el"
Aif(xN) +eN
G
=
(M)
(M) NN
A f (m) + (M)
Am (( + eNN
(M)
and D denotes the set observed noisy labels, i.e., fun { (m.njss- Let (Ám) }. (el and f denote
optimal solutions of the learning criterion 11
Let also define the following:
G arg min Ls Ls()))
(13)
GEg
where
G EGER MKXN ggh (m)) f + e!mh E (m) E E S C, Am E AJ,
FC (f: RD - RR is the neural network function class associated with the classifier function,
3 = (EER" 1Tc= =0,, | Σ
(e(m)|l2 ||2 0 }
m=1
A= (AERKXK 1 A 4 = 1T, A 0}.
Let G¹ represents the ground-truth such that
E(1)
a(1)
Aif +e ((1)
A +eN ((1)
NN
G
(14)
(M)
(M)
A (z)) ((M)
ft + + ((M)
g
We aim to bound G
G lp.. Towards this goal, we adopt the proof strategy based on the viewpoint
of matrix completion as employed in 77
Let us consider that we have S number of observations W1, wi...., We such that W, (m, Ra. yú, where each (m,, n.)) is sampled uniformly at random (with replacement) from [M] [N], i.c., i.e. the sampling probability for each (m, n) is given by Tm,, NM In addition, the noisy observations are generated as
(m.))
categorical a(m.)).
Let D., denote the joint probability distribution from where the observations wa are sampled. Then we define the following:
(G 2 E.--D_ [CE(g(m) (m), -(.""
18

---

We consider the following set of relations:
Lo( LD )) - Lo( - Ls(())) Lo(G.)))Lss(C,) + LLs(G):)) - LD(G" -
+ +Ls(G:D) - Ls((G:
< LD((),) - Ls(G:)) () + LLs(GA:)) - LD(G
2up LD ) Ls(G:)))
(15)
GEg
where the first inequality is obtained since G is the optimal solution as given by 13 and hence satisfies Ls(G;)) S (s( D). The last inequality is from the given assumption that G E 9 (This satisfied since it is given that f E F and | S C).
Next, we consider the following set of relations:
(G. LD( )) = Ew-D... (CE(g!..) (((m)) - CE(g (mm) m
(o!m)) k] loglo!m!)
(o!T logig
1=1
M
N Tm, Epm
K
(m)) = k] loglgn (m)
k] log (0glg
M
K
(m) log logloh (m))
JR +
>
( log log(g
NM
==
In=1
k=1
[g [(m))
1
Σ
Σ
Σ
h(m)))
& log
1
NM
ggle (m)
h
M
N
Σ
DKL (g (m) g((m)
NM
m=1n= n=1
N
M
2
Σ
(m)
g(m) 11?
2NM
n=1 m=1
N
g(m))
(16)
2NM
where we applied Pinsker's inequality 77 uses the fact that ||=|| ||>||| for any vector RKK having [[x]a] < v. [K]. Here
79 for the first inequality and the last inequality
DKL 92) denotes the Kullback-Leibh divergence between any 91, 92 E Ak. i.e. DKL(g1.g:) =
ΣX [9 log k
[91]
Combining
15 with 16
we get
N
M
19
(m))
(m)
<
4 sup
LD -Ls
(17)
NM
Geg
72
Next, we proceed to characterize the R.H.S. of 17 To achieve this, we invoke the following theorem derived from Theorem 26.5 in [80]:
Theorem C.2.
88 Theorem 26.5] Assume that V(m, n, Jn slm))) and VG G. we have Then for any G E G. the following holds with probability greater
(CE(g)) (m] [(m) < Zmax.
y/
than 8:
2 log(4/6)
Go - < 20R(E Go 42max V
(18)
S
where E o G o S denotes the set
tog S & { (CEE(g
(111) Almr))
CE(gi (ms)
)(m=a))
GEG
and R(X) denotes the empirical Rademacher complexity of the set X.
19

---

To apply Theorem C.2 be characterized below:
we need to characterize the terms 2max and RiE [ S). The term 2max can
2max
CE(g.
v)
max [g yE[K]
Σ k=1
ily
[s] log|g I
logig]ı log(8). (19)
[g)>>>
y
Note that in the above relation To characterize the Rademacher complexity R(e S), consider its definition follows [80]
19 we utilize the given assumption that each [g]x 2 1/3,Vg E g.
g
A(e o 9 o S)
_
E
sup GEG
o. CE(gn
(mx), p(mma)
(20)
where expectation is w.r.t. the independent Rademacher random variables o, E (-1,1). Since gi (m) are vectors, we utilize the following result to upper bound R(E G o)):
Lemma C.3.
87
Assume that the function CE(,,U), vy has the Lipschitz constant L. Then
5
5
K
E
sup GEG
Σ
(m))) Flmma) a. CE(g "
S
22L
sup GEG 8=1
Σ
Σ
oak
(m.))
where sak is an independent (doubly indexed) Rademacher random variable and the expectations are taken w.r.t the Rademacher random variables.
To apply Lemma C.3 let us define vector z
A
ghs
(mi)
11 [ni
(m))
J2. 12.-... ... Ins
(mm)
K 1,
giss
(ms)
RSK and the set Z o S - {2
(lgh)
(m1)
1. 19 12
(m))
ghg
(ms)
K-1 11 gin
(ms)
G E g). Using
these definitions, let us apply Lemma in (20) and get the following relation:
228
K
R(COGoS)
E
sup
oak (mm)))
S
GEG
s=1
kml
V28
SK
Σ
sup =E
S
SK
223K
LE
sup #EZoS
Σ
oz
= V23KR S),
(21)
SK
1=1
where B is upper bound of the Lipschitz constant of the cross entropy loss function CE(g.y) K Ek Ily = k] log[g)& when g E A with [x)]& (1/3). Vk.
Next, we will characterize R(2 o S) using the covering number of the set 2 o S. To define the covering number, let us first consider the concept of e-net covering of set. The e-net covering of set X' (denoted Xx) is defined the finite subset of X (i.e..X. S X') such that for any E X, there exists an æ E X, satisfying ||æ: x: < (2). The smallest cardinality of the e-nets of X' is known as the covering number of X, which is denoted as N(c,2))
Let us consider pair of vectors zs, Es o below:
zs
[g (mm))
[[, [g
(m1)) J2.
(ms)
K 1- [ (ms)] Jx
RRSK (m2)) Am, ((Dn)) + (m.))
Es = g m1)
11
mm))
g
mms)
K-1,
gh [
(ms)
E RSK
g!
(m.) J + t (m.).
where Am, belongs the e-net covering of A, f belongs to the e-net covering of F, and (m.) the appropriate sub-vector belonging to the e-net covering of Eg.
20

---

Let us also consider the following definitions:
us ([Am, ( )]1, [Am, f 12,
[ms I ( ]] K- [Am ( (k)) RSR
U = ([Am, (2n)) (Am, (vn)) 12,
Ams J (nns) K-1, Amg ( ( E RR*
Es [e 111 [e 12....,
[e
(ms)]
|K
--11 [e [mmes1]]] RRSK
ng
Es = [e(n))] 11 [el 12,..., [mmms)
---
E RSSK
ENM = [e] 11, [ei (1) 1,,..., IeN (M) | (eN (14) [x) E ERNNK
[e] 11, le..,,,, 1-1, [/ E RRNKK
N
ENM
Then, we have the following relation due to triangle inequality
- zs|l2 < |us usll2 + lles - es|12-
(22)
Next, consider the second term on the R.H.S. of 22
8
|les -ssl2 = Σ
||e (m.)
(mm
Sllexm - eNMM
(23)
We also have the following relations for the first term on the R.H.S. of (22
us
us|2
|Am. f(x..) Am. F(x.
s=1
Σ
Amm, (I).. Am, f( ) + Am, f(xn.)
Am, f(r,,
<
(I|mm Am, ||II5 +
f(xnn)
5
< 2
Amm, - Amm Amml-mm1111,. + Σ
Am, [ - f(on,)ll
a=1
s=1
< 2
Amm Am. 11 + +2K > (f(mn)) - F (xxn,))l
(24)
#=1
In the above set of relations, the first inequality is by triangle inequality. The second inequality uses that fact that (a + b)2 < 2a 262. The third inequality uses the fact that the Frobenius norm of An (xx,,) 's are bounded by K and the E norm of f (xx,) bounded by 1. Hence, combining (22)- 24), we get that in order to obtain an s-net covering for the set Z o S (i.e., || æ <. e), we only need to show that there exists 4yK -net covering for F S, an _ -net covering for ENM. 275
Vm, and a s -net covering for each A's. Here we have
1/S
FoS ([f(z))
f(+s) E ERKx FF E ES),
ENM ((e
(1)
e TTT E RKNN e((T) E, Ello S C,}.
[B = DN />
|e(m)) ||2 > o). Note that the full rank matrix Am E RRK can be
represented as a K²2 dimeenssio vector whose Euclidean norm is bounded by K. Hence, the
cardinality of the 4/3 neet covering for Am E K is at most [KKSKK K²
[80]. We consider the covering number corresponding to the function class F Towards this, we invoke the following lemma:
21

---

Lemma C.4. [51 Theorem 3.3] Let fixed nonlinearities (o1...., OL) and reference matrices (M,.... M.) be given. where os is Pr-Lipschitz and (;(0) 0. Let spectral norm bounds (81,..., 81.), h. and matrix (2, )-norm bounds bi.... br. be given. Let , be the S num- her of data items. Let h belongs to the following function class:
H _ (h:RD - RK h(z) -_L(CoL--(CL-1 (C 1), E ER),
where C₁ Rd, Rd.- with do D and dp = K. Let H. o S denote the family of matrices obtained by evaluating the data items with all choices of network H.
H. ([((z)), h(xs)) C= (I), 8i, C1 M2ll2,1 S b, h E H),
Then for any > 0,
|X |
log N(c H 0) 8)
2²
where X [ xsl, Rx = log(211²) (1I
is called as the spectral-complexng upper bound of neural network functiin class H and max, de.
s50²) 1
(Er
Using Lemma C,4 we get the cardinality of the 8VSK
-net covering for F FoN as below:
16K X P
N
E
Fos)
exp
8VSK
where Xs [1...... æs} E Rdx8 and the parameter Rx the spectral-complext upper bound of F.
2/5 Next, proceed get the cardinality of the c net covering for ENM Here, ENM is set
of sparse vectors with the number of non-zero elements upper-bounded by CM K, i.e., for any eN' E M, ||ex: I C.K. To get the covering number of set of sparse vectors, we invoke the following result:
Lemma C.5. 833 Let X f2 E 1| S q. 112110 C}. Suppose that C S N Then, there
exists an c-net covering denoted as X such that
ceN q c $
N(e,
0
where is the Euler's number.
Applying Lemma C.5
we get the cardinality of - nett covering of of ENM as follows:
2/9
CMK
eNMK 4CMVS CMK
N
ENM)
2VS
CMK
4eNMVS
(25)
Note that in 25). we used the result that |levm S V2CM < 2CM, VeNM E ENM
Using the covering number results, the cardinality the s-net covering of set Z o is bounded by the following:
CMK
R²
16K | X IR,RF))
4eNMVS
8KVSK
N(s, 2 S) exp
X
c2
[6K X5 RF
ANNSVS
8K KK
-exp
CMK log
+ log
(26)
22
Now that we have characterized N(e, 2 o S), we invoke the Dudley entropy chaining technique lemma to obtain the Rademacher complexity Ri R o S) 88):
22

---

Lemma C.6. Consider set A C R" let mina maxaed a all. Then for any integer T > 0,
22
6
T
R(A) v
log N(c2-t,A).
m
m
Since,
| S vs, E
applying Lemma C.6 on 2 o gives
PR(Z0S)
VS2-T
T S
2
V log Ní 2222,2220
VSK
SK
t=1
2
6
16K X 12
NcN 2
8K 8KvK 2-
2-
CMK
K2 log
VK
KVS
$4-
2-T
6
Σ
16
12
4
CMM
4eNM
Kollo
(KVK 2-
VK
KVS
2
T-
6
Σ
16K
+ CMK log (4eNM) - K2 (8K (SKKK)
VK
KVS
S
2
6T
16K X
RT
CMK (4eNM) + 12 K2 (8KVK)
VK
KVS
S
Choosing = log S/(2 log 2), we get the bound
R(Z 0) <
VSK
6 log S
16K
X
1
+ C.CK log (4cN + K2 log (SKVK)
(27)
2K 2 log
S
Combining the upper bound of Ri( S) given by 27 with the upper bound of R(e g 8) as given by (2T) and with the results 18) and (19, we get that with probability greater than -
2 )
2lg((4/))
< LLsG))
(28)
S
where Rs(Z o S) is upper bounded by (27
The above relation, combined with (16). implies that with probability greater than 1 - 28:
N
M
S 4223KR(ZZ + 8log(3) (og(4/
f(m)
g.
(29)
NM
S
n=
m=1
where R(2 o S) is upper-bounded in 27
D Proof of Theorem 3.5
To obtain the results in Theorem 3.5 we first show that the criterion correctly distinguishes the deeendeed and essance-independeer samples, i.e., I = I where we define ी & {i E [ é + 0).
Recall A.,. 's, e (m)) and f are defined as Theorem 3.5 and let ē, = =(e(1))
(2())
TT. We
first show that 7. C Ie. From Lemma 3.1 the following holds:
W
E
WF Ell S (S)
(30)
23

---

Then the inequality also holds for any submatrix of the left hand side matrix. In particular, for i E I and S > So.
Eg (So) (g(S)
|| F (1. {i] ( B nT
(onnnnnnn).... nI9)
(i nī) E(: (i nl
=I F T [9]
e .0.......) WIf.. ( 1 n ( (2, 0
0,
|| Ft (:, I" [9]
W(f. F(: I n ) || 0, 0
2 x(ee) - [, 0, 0 0|r (by Definition 3.3
2 (S)) [|
0]
(by the assumption in Theorem 3.5
Therefore, e, + and that concludes 7o C
the other hand, since e!m)ss minimizes m || la }). it holds that I CT. This implies that I I must hold.
Σn 2 M
With I = Ie, we have the following relation from 30
log log(4/6)
MN W
W
I & ( + (og((5)
(31)
S
To proceed, we invoke result from the work 31
considering Assumption
3.4
satisfied, and the set
2
2K
I is uniformly chosen from [N], with probability at least
5 No
cs(5 )TKR) +64T 644T-5/822
2 log(45)
E
min f(xx) - (x)) < 1I
RS 0.25 0 +161
T(1 VK)2
N
where
2 2log(4S)
RRs log S
v /log (1/8)
6 = ()) SV
00
+ +log (3)
VS
VS
22 (lgg(45)
-² = MT
4V23K99 5) 810g((3)
+ 4/5
S
K 4 + + E2 VKf
X = PR.... ........ Engl. where (m, n2.) E S,
K| 8
23 = K2 log (K) +
CMK log VNM,
S
T = N [Z].
E Proof of Theorem 3.6
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 oc. We repeat the derivation here for completeness.
We first show that the criterion correctly distinguishes the instance-dependent and instance- independent labels.
Let (A,, 's, e(m))ss and f) be an optimal solutions as state in Theorem From Lemma 3.1 the following holds as the number of observations grows S infinitely large:
= Am (w.) + + g,. (m) A (xxw) + ((m) Vn, m.
(32)
Consider the following relation:
B(1)
a(1)
(x)) t 2(1)
A + +eN
{(1)
gN
G
: f + + b(M)
(33)
(MM
(M)
ft +e +(()) ((M)
N
24

---

Here, each column of the matrix G is given by
A
h(1)
ex
|G =
(xx) +
h(M)
En
WiERMEXK
CAERMA
G = f + en Vn.
(34)
Similarly, we can also define
A
e(l)
En
W
:
ên
A
MJ
Cn
(M)
From 32
we get that
[ ffxn) + en, Vn.
(35)
We will use contradiction-based argument towards this. Let us start by considering the case where there exists i" I as well as i" E z holds. Then, combining (34 and (35) we get
W ff(x.) = W (x),), Vi e e n
(36)
We can rewrite the relation 336 as
W FF nz) = W F F n
Since any submatrix formed by N 2| columns of F = [f(x),,,-))) ..... [(x)] has rank and that rank(W3) K. we get that there exists nonsingular matrix E R R such that
W WºQ.
(37)
Next, we consider the case where there exists i* I and i" It. Then, again from get that
34
35
we
W Wfx; wif e
(38)
However, by applying the relation
37 in
38)
we get
@'Qf(x;-)) = W (xx,)) + e/.
W'Qf(mr)) W f e/.
W'q = ei.,
where q = Qf(x..) - (x a nonzero vector since is assumed that e₁. * 0. The above relation implies that e/. E range(WWs must hold which is contradiction the assumption that ei. range( Wa) when it E I. Hence, the relation (38) is feasible only if eç- 0. It means that there exists i* E 7r, we should have i* I", leading to the conclusion that 7 I
On the other hand, i
I holds, then
N
M
N
Σ
(m)) ||2
>
0
Lez(m (m))
2 > 0
Since <(m) ' are the optimal solution of Problem the following should hold
p
with minimal
DM 12( ||2 > 03.
M
N
((m))
2|2
0
ee(m) 1|2 > 0
25

---

which is contradiction. This implies that I Ī must hold.
Since Z = holds, we have the following relation from (32
G (t, G(:,I",
(39)
where we utilized the following notations:
G WF(;IT),
G (: 19
WF (:,
9: [0 (1IT
(M)) J T
W [A]
Th
M
W [A]
AM
Next, we connect the det W W) term to our optimal solutions. This part is similar to the classical proofs in 85) with proper modifications. Consider the following result extracted from the proof of Theorem 1]:
Lemma E.1. Suppose a matrix Y E RR satisfies Y 2 0, Ty = rank K, and SSC. Then, for any Y QY satisfying Y 0. 2 1T, the following holds:
(et((Q) 1
The equality holds only if Q a permutation matrix.
Since W is the optimal solution of the criterion given by Theorem 3.6 the following holds:
det (W W) I det(W* (W:T W
(40)
We also have W and (",, I are of rank K. Hence, from (39 we get that W and F(., I>)
satisfies W = wiQ-1 F(: I = (:" ("), for a certain invertible matrix Q. Let us assume that is not permutation matrix, Then, we have
det(W TT W det(() W (T)))
det(Q) 2 det W W)
det W W),
where the last inequality is from Lemma E.1 using the SSC condition (F, Note that the result is contradiction from (40) Hence, Q must be permutation matrix. This implies that the
optimal solution W and f:., I satisfies the following:
W = WIII,
(41a)
F(. I II F*)
(41b)
F Proof of Fact 2.1
For rank(At) K, when N oc, the objective in (6) seeks the optimal solutions A f* and e such that
A (x)) + eat A f (x.)) + e n E [N].
(42)
This can be seen from Lemma 3.1 with M = 1. One solution that satisfies the equality 42) and the sparsity constraint in ( A 1, f (a: A (ar.) eq, and e = O, which can always hold
when ff is universal function approximator.
26

---

Table Noise levels and methods used train machine annotators.
Case
Noise Level
Training
CIFAR-I0
High Noise
0.26, 0.69, 0.57
Logistic Regression, k-NN, ResNet34
Medium Noise
0.26, 0,46, 0.57
k-NN, ResNet34, ResNet34 k-NN, ResNet34, ResNet34
Low Noise
0.26, 0.29, 0.57
STL-10
High Noise
0.15, 0.25, 0.69
k-NN, ResNer9, ResNer9 ResNet9, ResNer9, ResNer9 ResNet9, ResNet9, ResNet9
Medium Noise
0.15, 0.36, 0.21
Low Noise
0.15, 0.02, 0.21
Table 5: Average classification accuracy on CIFAR-10 using synthetic annotators over random
trials.
Method
Noise rate
0.2
Noise rate
0.4
= 0.1
0.3
= 0.5
11 0.1
7 0.3
17 0.5
CroudLayer
91.01 0.28
88.49
84.59
0.47
89.00 + 0.31
86.47 + 0.33
82.39 + 0.09
TraceReg
91.76 0.38
89.55 0.20
83,60
3.14
89.95
0.19
87.28 0.08
76.73 + 1.24
MaxMIG
88.85 0.29
84.99 0.41
81.96 0.16
86.27 + 0.59
82.69 0.57
78.60 + 0.33
(FoCroRdNet
9I.36 0.26
89.13
85.28
0.34
89.21 = 0.43
86.73 0.36
83.03 + 0.49
(eoCroxdNet
91.21 0.28
88.69
0.29
84.68
0.44
89.16
0.14
86.17 = 0.39
81.49 + 0.31
MEIDTM
91.27 0.09
84,50 4.24
52.77 4.05
87.74
0.09
61.33 +: 3.92
49.88 +: 1.11
PTD
79.59 0.46
69.02 +: 1.61
52.56
1.05
70.33 1 0.63
50.94 =: 5.48
37.83 + 5.87
BLTM
73.82 1.77
66.27
1.60
53.72
1.84
66.34
1.84
55.83 = 0.67
46.20 + 0.97
VolMinNet
89,95 0.23
87.34
1 0.26
82,60
1 0.50
87.32
0.38
83.62 0.14
76.50 1 1.13
Reweight
87.39 0.82
82.35
0.79
81.82
0.10
88.34
1 0.44
86.16 1 0.55
81.67 0.61
GCE
88.75 0.31
86.98
0.21
83.72
+/ 0.20
86.70
0.15
84.58 + 0.26
80.29 + 0.56
COINNet (Durs)
92.23 0.36
90.06 1 0.06
86.47 = 0.04
91.97
1 0.02
87.90 1 0.03
83.45 +: 0.04
G
More Details on Experiment Settings and Datasets
G.1
Implementation
We train with batch size of 512, number of epochs 200, Adam optimizer with learning rate 0.01 and learning rate scheduler OneCycleLn [86). We initialize An using an identity matrix going through softmax and em for all m [M]. We also apply standard data augmentation including random cropping, random flipping, when training on CIFAR-10, CIFAR- 1ON, 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 10 takes about 60 minutes using Nvidia A40, and 30 minutes using Nvidia DGX H100 GPU.
G.2 Machine Annotations
For machine annotator experiments, consider the CIFAR-10 662 and the STI.-10 datasets (63 The CIFAR-I0 10 dataset consists of 60, 000 labeled color images of animals, vehicles and so on, each having size of 32 x 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 CIFAR-10. Of these, 5,000 images are designated for training and 8,000 for testing.
Table shows the details regarding the individual label noise rates and training methods in our experiments with machine annotators.
G.3 Real Annotations
For real annotation experiments, we use popular public datasets: CIFAR-ION (66) and LabelMe 67 68) and construct the ImageNet-15N 15N dataset with higher number of annotators. All three datasets are labeled by anonymous annotators from the AMT platform. The CIFAR-ION "noisy"
version of the popular CIFAR-10 dataset, containing 50,000 images for training, and separate
27

---

0.900
0.921
0.927
0.944
0.898
0.918
0.932
0.870
0.801
0.752
0.676
0.636
0.549
Score
score
0.4
0.4
0.359
0.335
0.202
0.2
0.2
Outlier Detection Rate Accuracy
Outlier Detection Rate
Accuracy
0.0
0.0
1
1
4
M
M
Figure 4: Performance of COINNet on CIFAR-10 with synthetic labels against different number of annotators; left: = 0.2, 17 = 0.1, right: T = 0.4, 17 0.1.
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-1ON 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. 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 applied, resulting in 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 images 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_cus
sete_cctt_oe cat, airship, aircraft carrier, trailer _tuck, orange, penguin, lemon, soccer_bar ball, airliner, freight_cars 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 42.68%. The validation and testing sets have 1,462 and 13,157 images, respectively. We release the noisy annotations at https //github. http://cco/ttttt/////Neeee
H More Experiments
H.1 Experiments with Synthetic Annotators
Noisy Label Generation. Here, consider labels corrupted by synthetically generated annotator confusions. To generate the confusion matrices, we utilize the following strategy. We control the instance-independene label noise rate using a parameter construct the ground-truth confusion matrix A?, where the diagonal entries of A are set as [A*] = 1 - t, vk, and the off-diagonal entries are set as [A*]*.j = -ー., + j. First, we randomly select
(0, 1). By employing this parameter,
fraction of the data samples and generate their labels using the instance- independent confusion matrix A For the remaining percent of the samples, we adopt an instance- dependent noise generation process, by following strategy outlined (27). Specifically, for such "outliers". the label confusions vary depending the features of such instances.
28

---

Table 6: Average classification accuracy on CIFAR-IO 10 and STL-10 datasets using machine annotators; results are averaged over 3 random trials.
Method
CIFAR-I0
STL-10
High Noise
Medium Noise
Low Noisc
High Noise
Medium Noise
Low
Noise
COTNNeT, 141 0.01.P3 M3
71.22
0.72
73.31
0.37
76.39 0.58
Rlle, 0101, 0.00
71.4 0.33
73 + 0.31
83.61 + 0.68
58.90 3.4
64.47 - 3.75
72.79
+2.8
COINNet, ju 0.000 P2 0.01
71.17 = 0.46
73.18 = 0.91
83.51 = 0.47
06.77 = 4.81
72.40 0.57
76.24 = 0.52
Table 7: Average classification accuracy on CIFAR-I0 10 using synthetic annotators; results are averaged over 3 random trials.
Method
rate
rale
11 0.1
7) = 0.3
1) = 0.5
12= D.1
1
0.3
9. 0.5
COINNet, = 0.01, 0.01
92.23 + 0.36
90.06 0.06
86.47 + 0.04
91,97
0.02
87.90
+ 0.03
83.45 + 0.04
COINNet, j4 = 0.01 Mr
0.00
92.23
0,93
89.64
0.16
86.40
0.18
91.16
0.07
87.98
0.13
83.15 1 0.16
C0 COINNet, p4 M.
0.01
91.87
+ 0.0
89.65 0.13
85.44
0.31
90.21
0.22
87.01
0.48
66.50 + 1.44
Table Average classification accuracy over random trials on real datasets.
Method
CIFAR-ION
COINNet, μl1 = 0.01, #2 = 0.01
92.09 + 0.47
COINNet, /41 = 0.01, 1/2 0.00
92.26 + 0.24
COINNet, 11 = 0.00, P2 = 0.01
91.51 + 0.60
Method
LabelMe
COINNet, 141 = 0010. μ42 = 0.10
87.60 + 0.54
COINNet, μ1 = 0. 0.10, μ22 = 0.00
83.64 1 1.29
COINNet, 111 0.00, μ22 0.10
84.85 1 0.22
We generate synthetic noisy labels for CIFAR-10 dataset with M = 3. CIFAR- 10 contains 50,000 images of size 32 x 32 as training set, and 10,000 images as test set. We keep the test set untouched while randomly splitting the train set into 2 parts (47,500; 2,500) to serve as training and validation set. We use the same neural network architecture and the optimization settings as used in machine annotator case. The results are presented in Table One can observe that our approach consistently perform well in all scenarios.
To demonstrate the effectiveness of the advocated crowdsourcing approach in outlier detection, we vary the number of annotators M and present the average outlier detection rate and the testing accuracy, where
In (i
|e.112 E top [[] values among all |@,.12. [N]]
Outlier Detection Rate
We observe that increasing the number of annotators M shows improvement over both outlier detection and the final accuracy score as shown in Fig,
H.2 Ablation Study
Effect of regularization terms. Tables 7 and B show the effectiveness having both the proposed regularization terms sparsity and volume).
Effect missing annotations. Table and Table show results under different levels of missing an- notations under various parameters settings. Table and Table 12 present results where only single label is available for each image. In all four cases, the proposed method demonstrates superior ro- bustness against the negative effect of missing annotations relative to MaxMIG and GeoCrowdNet (F), two competitive baselines.
Effect of initialization. In Table 13 we test the performance of our approach using different initialization strategies. In particular, we conduct the machine annotator experiment on CIFAR-IB 10 using the following initialization strategies: the confusion matrices are (i) initialized using identity matrices, and (ii) initialized by the GeoCrowdNet (F) method. We also include the performance of GeoCrowdNet (F) for reference. We observe slight improvement (around 0. 100.4%) in accuracy when using initialization from GeoCrowdNet (F) with the cost of training GeoCrowdNet (F) for 10 epochs.
29

---

Table Average classification accuracy v.s. missing rate on CIFAR-10 using synthetic annotators;
M = 3 = 0.2. 0.3: results are averaged over 3 random trials.
missing rate
0.1
0.2
0.3
0.4
0.5
MaxMIG
85.01 = 0.26
84,32 0.20
83,90 0.59
83.17 = 0.70
81.80 + 0.25
GeoCrowdNet (F)
83.19 0.63
83.03 = 0.41
81.83 0.17
81,46 = 0.47
81.28 + 0.56
COINNet (Ours)
89.41 + 0.13
89.22 0.21
88.98 0.55
88.53 0.40
87.54 0.16
Table 10: Average classification accuracy missing rate CIFAR-10 using synthetic annotators; M = 3 = 0.2, = 0.5; results are averaged over 3 random trials.
missing rate
0.1
0.2
0.3
0.4
0.5
MaxMIG
80.97 + 0.77
79.04 + 0.90
79,46 + 0.62
77.78 + 0.72
76.15 + 1.81
GeoCrowdNet (F)
80.32 0.55
79.42
0.27
78.81 0.27
76.93 0.39
76.01
0.42
COINNet (Ours)
86.23 + 0.14
84.98 + 0.64
84.24 + 0.71
83.79 + 0.40
81.49 + 0.59
0.005
0.005
0.005
0.005
0.005
0.005
0.005
0.004
0.005
0.004
0.005
0.005
0,004
0.005
0.004
0.004
0.004
0,005
0.004
0.005
0.004
0.004
0.005
0.004
0.005
0.005
0.005
0.004
0.005
0.005
0.005
0.005
0.004
0.005
0.005
0.005
0.004
0.005
0.005
0.005
0.005
0.004
0,005
0.005
0.005
0.005
0.005
0.004
0.005
0.005
Figure 5: Some examples from the CIFAR-1ON dataset learned with low outlier scores 8, 's.
H.3 Outlier Detection in CIFAR-1ON Dataset
Following the result Fig. 2 we show more examples of nominal data items and outlier data items as separated by our approach in Fig. and Fig. [ respectively. Clearly, more instance- instance-varying confusing characteristics are present in the latter case.
30

---

Table 11: Average classification accuracy in the scenario where each image of CIFAR-I0 is labeled by only one randomly chosen annotator from .M synthetic annotators; results are averaged over 3 random trials.
T 0.2, 77 = 0.3
T == 0.2, = 0.5
MaxMIG
81.36 + 0.81
70.78 + 4.66
GeoCrowdNet (F)
80.44 + 0.18
75.31 + 0.33
COINNet (Ours)
87.18 + 0.29
80.96 + 0.38
Table 12: Average classification accuracy in the scenario where each image of CIFAR-1O is labeled
by only one randomly chosen annotator from M = 3 machine annotators; results averaged over random trials see the annotation generation settings as Sec. 5..
High Noise
Medium Noise
Low Noise
MaxMIG
58.58 + 0.64
67.64 = 0.25
77.01 + 0.25
GeoCrowdNet (F)
55.25 1.09
66.91 0.53
75.48 0.28
COINNet (Ours)
59.76 =E 0.62
70.94 0.32
80.12 + 0.44
Table 13: Average classification accuracy with different initializations for the confusion matrices. We
use machine annotations with the same setting as described in Sec. 5.1 in the manuscript. Results are averaged over 3 random trials.
Initialization Strategy for A. 's
High Noise
Medium Noise
Low Noise
Identity matrix GeoCrowdllet (F) after training 10 epochs
70.37 0.61
73.33 0.46
83.25
0.39
71.75 + 0.73
73.48 + 0.27
84.26
0.13
Current setting (close to an identity matrix)
71.22 0.72
73.31 + 0.09
84.14 = 0.38
0.176
0.176
0.175
0.175
0.171
0.167
0.172
0.174
0.175
0. 0.176
0.167
0.172
0.174
0.175
0.176
0.166
0.177
0.176
0.175
0. 0.172
0.166
0.177
0.176
0.175
0.172
0.171
0.176
0.180
0.178
0.167
0.171
0.176
0.180
0.178
0.167
0.172
0.174
0.175
0.172
0.167
0.172
0.174
0.175
0.172
0.167
0.173
0.177
0.174
0.176
0.176
Figure Some examples from the CIFAR-ION dataset learned with high outlier scores 8, 's
31

---

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: Our claims have been discussed and supported our analysis in Section
and 3 particularly by Fact 2. Theorem 3.5 and Theorem 3.6 with empirical evidence in
Section 5
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made 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
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.
is fine to include aspirational goals as motivation as long as is clear that these goals not attained by the paper.
2. Limitations
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
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 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 (c.g.. independence assumptions, noiseless settings, model sell-specfiiatiinn 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 the scope of the claims made, e.g. if the approach was only tested on 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-tex, system might not be used reliably to provide closed captions for online lectures because it fails 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 faimesss.
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 '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?
32

---

Answer: [Yes]
Justification: We have presented all assumptions we have used in Section 3
All proof are
presented in the Appendix, particularly in Appendix D Appendix E Appendix F
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 or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a 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
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 whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: We have described in details experiment settings as well as the implementation
techniques in Section 3 Section 3 and Appendix G We also include our code in this
submission as supplementary material.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, No answer 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 dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access 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 a hosted model (e.g.. in the of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS 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) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily
model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are 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.
33

---

5. Open access to data and code
Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, described in supplemental material?
Question:
Answer: [Yes]
Justification: We have included code, including instruction how to run in this submission. is almost the same code that all identity related information. All data we used are publicly accessible.
to produce all experiment results, except removing
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips... cc/
for more details.
While we encourage the release of code and data, we understand that this might be possible, so "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 rum to reproduce the results. See the NeurlPS code and data submission guidelines (https
//nips.co tttpcc//pbbb. muublc//guidee wttggdedeeeeeeeudbmmmmmee www.//ooieeeisiiieeoaa wommiisssoooiicy for more details.
The authors should provide instructions on 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 possible in supplemental material (appended to the paper) recommended, but including URLs to data and code 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:
We describe these in Appendix G
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: All experiments are repeated at least times. All numbers are accompanied with standard deviation, as described in Section
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by emor bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
34

---

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.
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 out range (e.g. negative еπτог rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: We have included these information in Appendix
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported the paper (e.g., preliminary or failed experiments that didn't make it into the paper).
9. Code Of Ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics httpp:://eeuri: wwwpuripssccpppuue hwtp///bbbcccccccccciii........e
Answer: [Yes]
Justification: We have made to our best effort to remove all identity-related information in both the main paper supplementary material.
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 or 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: [Yes]
Justification: Our work tackles the noisy labels problem which is ubiquitous, especially in the big data era, and hence bring positive impact society.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
35

---

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), faimess 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 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 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 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 system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
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 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 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
Guidelines:
The answer NA means that the paper does
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 used and, 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.
36

---

If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com/dataseta
latasets.papersstt
has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
this information is not available online, the authors are encouraged to reach out to the asset's s creators.
13. New Assets
Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Question:
Answer: [NA]
Justification: There is no new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details the dataset/codeemmodll as part 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 used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsoureing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
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 research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According 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.
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/teview based 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 crowdsoureing nor research with human subjects.
37

---

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.
38


Reviews:
[{"review_id": "SkxgCsEskz", "reviewer": "Reviewer_okUb", "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.", "questions": "1. The meaning of some terms, like \"outliers\", \"the model of interest\", \"neural systems\", is not clear when just reading the abstract.\n2. It seems that there is a symbol that is not displayed in the restrictive condition of Eq.(6).\n3. What does $e^\\star_n$ mean in Line 129?\n4. What does \"over-canceling” mean in Line 211?\n5. I suggest placing the learning-from-crowds methods after the learning-from-single-annotator methods in Table 1 and 2.", "limitations": "See above.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. This work provided some interesting identifiability results for learning from crowds, which may inspired further work.\n2. The writing is excellent, making it easy to understand.\n3. The proposed method is end-to-end and one-stage, which is nice for application.\n4. The case study in Figure 2 clearly showed the rationality of the results.", "weaknesses": "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？\n\n2.  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].\n\n3. 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.\n\n[1] Label correction of crowdsourced noisy annotations with an instance-dependent noise transition model. NeurIPS 2023\n\n[2] Coupled confusion correction: learning from crowds with sparse annotations. AAAI 2024\n\n[3] Trustable co-label learning from multiple noisy annotators. TMM 2023", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "__[Regarding Impact of the Number of Annotators]__ In Figure 3 of the supplementary section H.1, we presented experiments showing the impact of the number of annotators for outlier identification. The results indicate that increasing the number of annotators improves the detection of instance-dependent samples as well as the classification performance. We will add more obvious pointers to this result in the supplementary material.\n\n__[Regarding \"Sparse Annotations\"]__ Thanks for this suggestion. We hope to remark that our identifiability analysis does cover the “sparse annotation” case—see Eq. 10, Lemma 3.1 and Theorem 3.5 where the bounds depend on $S$, i.e., number of observed labels. Here, $S$ can be much smaller than $NM$, where $N$ is the number of data items and $M$ is the number of annotators. We also thank the reviewer for providing the papers addressing sparse annotations. We will discuss them in “Related Works”. The interest on the sparse annotations also attests to the importance of our theoretical result in Theorem 3.5.\nIn our real-data experiments, the LabelMe dataset has many missing labels (please see Table 2 of the manuscript). To be specific, only 2547 annotations are obtained from 59 workers for 1000 images, which implies that 95% of the annotations are missing ($S/(NM) \\approx 0.05$). Our approach scores the best classification performance in this case as shown in Table 2 of the manuscript. \nTo further analyze the effect of missing annotations, we followed the reviewer’s suggestion to conduct the following synthetic data experiments for various levels of sparsity in the CIFAR-10 dataset—see _Table 1, 2 in the attached pdf_. The results show that the proposed method is more robust to the negative effect brought upon by the missing annotations, relative to the best-performing baselines, namely, $\\texttt{MaxMIG}$ and $\\texttt{GeoCrowdNet}$. \n\n__[Regarding Abstract]__ Thank you for your suggestions. We agree that the terminologies can be simplified/unified to improve clarity. Mentioning the sparsity prior also makes sense to us. We will revise our abstract accordingly. \n\n__Questions:__\n\n__[Q1]__ Agreed. We will revise accordingly.\n\n__[Q2]__ The symbol $\\mathbb{I}[E]$ in the constraint denotes the indicator function, whose value is 1 if the event $E$ happens and 0 otherwise. We defined this notation in Table 3 in Appendix A. To avoid confusion, we will make this clearer in the main text.\n\n__[Q3]__ $(\\textbf{A}_n^\\star, \\textbf{e}_n^\\star, \\textbf{f}^\\star)$ denotes an optimal solution of Problem (6). We will make it clearer. \n\n__[Q4]__  Ideally, we hope to just cancel/exclude the exact set of outliers from the process of learning $\\textbf{f}$. This would require us to set $C=\\| \\mathcal{I}\\|$ in Problem (6). Nonetheless, the exact number $\\|\\mathcal{I}\\|$ is hard to estimate. Our analysis in Theorem 3.6 shows that for even when $C$ is over-estimated ( i.e., $C > \\|\\mathcal{I}\\|$), our method still can cancel out all the outliers. As a price to pay for overestimating $C$,  there will be $C- \\|\\mathcal{I}\\|$ nominal data samples also identified as outliers and excluded for learning $\\textbf{f}$. This is what we meant by “over-canceling”.\nThanks for pointing out this ambiguity. We will rephrase this sentence to make this discussion clearer.\n\n__[Q5]__ Thank you for your suggestion. We will do the rearrangement in the revised version.", "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": "X9S3EMbq4o", "reviewer": "Reviewer_TTRF", "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.", "questions": "I do enjoy reading the paper. It is coherent and easy to follow. I do not have any questions.", "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.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The paper thoroughly presents the motivation and the formulation of their modelling approach. The paper also connects to previous studies when formulating the noisy label learning with instance-dependent noise as outliers. In general, the paper is well-written and easy to follow.\n- The main contribution of the paper is to extend further the modelling considering only class-dependent transition matrix by adding *perturbation* induced by instance-dependent label noise samples. The paper also analyses the theoretical guarantee when estimating the classifier of interest in terms of PAC-style formulae.", "weaknesses": "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.\n\nAnother 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.\n\n### Minors\n- Line 76: typo \"traget\" -> target\n- The abbreviation \"NMF\" at line 100 is not defined.\n- Line 111: $E(x_{n})$ is a matrix. Thus, please make it clear when specifying $E(x_{n}) > 0$.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the insightful comments.\n\n\n__[Regarding the Lack of Public Multi-rater Dataset]__ We agree. It would benefit the community if more public multi-rater datasets are available. We are working on creating such data using Amazon Mechanical Turk (AMT), but the size of data is still limited by resource/cost and it might be beyond the timespan of this submission.\nA relevant remark is that, to conduct experiments under realistic multi-annotator settings, we considered machine annotators in our experiments (see our settings in Sec. 5.1, and Appendix G.2). Note that a machine annotator is a classifier (e.g., SVM,  kernel SVM and KNN based classifiers) that are trained using limited data. Hence, they all make mistakes in “labeling” data. The setting is of interest: (i) integrating the annotations from such erroneous classifiers is called ensemble learning, which is a special case of noisy label learning and crowdsourcing---and is a real application in practice. (ii) The classifiers make mistakes according to the hardness of each item, and thus the setup well represents instance-dependent errors. \nWe will release the code for making such machine annotator-based datasets, so that the community could easily create multi-rater scenarios with specified error rates and missing label proportions, etc, to facilitate reproducible research in an economical way.\n\n__[Minor Points]__ Thanks for the attentive reading. We will fix the typos. In particular, $\\textbf{E}^{\\natural}(\\textbf{x}_n)>0$ should be $\\textbf{E}^{\\natural}(\\textbf{x}_n) \\neq \\textbf{0}$, that is, the matrix is not an all-zero matrix.", "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": "8VNhWIvVQS", "reviewer": "Reviewer_FFyM", "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.", "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?\n2. Would existing estimators for noisy labels, such as [R1], provide a good initialization for the variable $\\mathbf A_m$ in the proposed loss function?\n\n[R1] Unmasking and improving data credibility: A study with datasets for training harmless language models. ICLR 2024.", "limitations": "NA", "rating": 5, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The work aims at an important and the proposed solution is solid.\n2. The presentation is clear and the proposed method is supported by thorough theoretical results.\n3. Experiments on real-world label noise such as CIFAR-N validate the effectiveness of the proposed method.", "weaknesses": "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$. \n2. The organization part of the proposed method could be polished.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "__[Regarding $S \\to \\infty$ in Theorem 3.6]__ We agree that an analysis with finite $S$ is more desirable (as we did in Theorem 3.5). Nonetheless, we argue that even with infinite $S$, the result in Theorem 3.6 is meaningful and nontrivial. Let us explain.\nFirst, the aggregated noise will not disappear when $S \\to \\infty$. Note that $S$ represents the number of annotations (not the number of annotators). When ($M,N$) are fixed, $S$ can still go to $\\infty$ as sampling for annotation is assumed to be with replacement. Recall that for $\\textbf{y}_n^{(m)} \\sim \\textbf{p}_n^{(m)} = \\textbf{A}_m \\textbf{f}(\\textbf{x}_n) + \\textbf{E}_n^{(m)}$. \nEven when there is no outliers, if $\\textbf{A}_m$ is heavily non-diagonal, $\\textbf{p}_n^{(m)}$ is going to be very different from $\\textbf{f}(\\textbf{x}_n)$, and thus $\\textbf{y}_n^{(m)}$ is always going to be wrong no matter how large is $S$. \n\nOne possibility of using increased annotators to attain zero aggregated noise is when $\\sum_{m=1}^M \\textbf{A}_m = \\textbf{I}$, but this requires that all the annotator errors are zero mean across $m$---which might be too special to assume. Majority voting also does not help if most $\\textbf{A}_m$ are not close to diagonal.\n\nSecond, the identifiability analysis is not trivial and the result has good practical implications. Note that $S \\to \\infty$ makes the equality $\\textbf{p}_n^{(m)} = \\textbf{A}_m \\textbf{f}(\\textbf{x}_n) + \\textbf{O}_n^{(m)}$ hold for every $m$ and $n$. But this equality per se still does not guarantee the identifiability of any of $\\textbf{A}_m$, $ \\textbf{f}(\\textbf{x}_n)$, or the outlier $\\textbf{O}_n$. The point made by Theorem 3.6 is that our formulation with a volume maximization constraint can identify all the three terms. This theorem gives useful insight: when we have sufficiently large $S$, using the outlier sparsity and volume regularization (as shown in line 227-228, page 6) is expected to give good performance. We believe this insight itself can benefit practical implementations.\n\n__[Organization of the Proposed Method Section]__ We will do a thorough proofreading and polish the section.\n\n__[Regarding Multiple Annotators and the One-Label-Per-Item Case]__ This is an interesting question. The method does require the existence of multiple annotators, but it does not require each item to be labeled by all annotators (see the settings of Lemma 3.1 and Theorem 3.5). Therefore, even if each item is annotated by only one annotator, the method still works under reasonable conditions.  To show this, we present some empirical results in _Table 3 and 4 of the attached pdf_. The results suggest that the proposed method still outperforms the competing baselines in this setting.\n\n__[Initialization for A_m]__ Good initialization techniques are always appreciated. We will add discussion in the revised version on initializing $\\textbf{A}_m$ using existing methods such as those in [R1]. In _Table 5 of the attached pdf_, we also compared the performance of our approach using different initialization strategies. In particular, we compare the machine annotator experiment on CIFAR-10 using different initialization strategies: (i) $\\textbf{A}_m$ initialized using identity matrices and (ii) $\\textbf{A}_m$ initialized by the$ \\texttt{GeoCrowdNet(F)} $method. We also include the performance of $\\texttt{GeoCrowdNet(F)}$ for reference. We observe a slight improvement (around 0.1-0.4%) in accuracy when using initialization from $\\texttt{GeoCrowdNet(F)}$ with the cost of training $\\texttt{GeoCrowdNet(F)}$ for 10 epochs.", "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": "f77IwpsZCL", "reviewer": "Reviewer_BkAV", "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.", "questions": "Can the authors discuss any limitations their method might have in scenarios of highly imbalanced noise?", "limitations": "NA", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "● The problem setting, considering the instance-dependent noisy samples as outliers, is realistic and really interesting.\n● The paper posits that existing methods relying on sparsity priors are insufficient for outlier detection and proposes a novel crowdsourcing strategy as a solution with theoretical grounding and generalization guarantees.", "weaknesses": "Lack of large-scale datasets in experiments", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "__[Regarding Large-Scale Datasets]__ We agree with the reviewer on this point. In the current manuscript, we have tested our methods against baselines on a dataset of size 50,000 samples in both machine annotations and real datasets. We did not use larger data size due to resource limitations and also because our focus has been on the design principle side.\nNonetheless, to examine the proposal’s scalability, we have conducted an experiment on the full SVHN dataset which contains more than 600,000 images. In this experiment, $K=10$. We used $M=3$ machine annotators as we defined in the manuscript. The error rates of the annotators are 0.30, 0.36, and 0.32. We also included performance of $\\texttt{GeoCrowdNet(F)}$ and $\\texttt{MaxMIG}$ for comparison. The result is presented in _Table 6 in the attached pdf_. Although we have not been able to sufficiently tune our method’s parameters due to time limitation, the preliminary result already looks promising.\n\n__[Regarding Imbalanced Noise]__ Thank you for this question. Please note that Table 1 in the manuscript addresses the imbalanced noise setting, where annotators have different annotation noise rates. Table 4 of the Appendix G presents the individual noise rates for each scenario. As shown in the table, in the high level noise case, the noise rates for the three annotators are 26%, 69%, 57% for CIFAR-10, and 15%, 25%, 69% for STL-10, respectively. The results in Table 1 show that our method is robust to such highly imbalanced noise settings, outperforming the second-best baseline by approximately 3% on average.", "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 would like to thank all reviewers for their attentive reading and valuable comments/suggestions. We have replied to each reviewer in their corresponding sections. Here we present a summary of major comments and our responses accordingly.
 
__[Reviewer okUb]__
Reviewer okUb suggested investigating the impact of annotation sparsity and the number of annotators. We clarified that the effects of both annotation sparsity and number of annotators are covered by our analysis and some existing experiments. To further observe these aspects, we have additionally run more experiments under various sparsity levels and presented the results in _Table 1 and 2 in the attached pdf_. We also clarified a number of notation and terminology questions.

__[Reviewer TTRF]__
Reviewer TTRF made a comment regarding the lack of public multi-rater datasets in this field.  We followed up with some thoughts and offered our perspectives. We highlighted the benefits of including machine annotators in our experiments and its usefulness in facilitating reproducible, realistic experiments in an economical way.


__[Reviewer FFyM]__
Firstly, the reviewer FFyM raised concerns about the significance of the infinite sample analysis in Theorem 3.6. In our response, we clarified the merit of Theorem 3.6 under the infinite case, when the number of annotations goes to infinity. We pointed out that the aggregated noise would not be canceled out by simply letting $S \to \infty$ and explained the practical implications and significance of the identifiability analysis of Theorem 3.6. 

Secondly, reviewer FFyM asked about the importance of multiple annotators and suggested considering a one-label-per-sample case. We clarified that our method is able to work with such single-label data and provided additional results in _Table 3 and 4 in the attached pdf_. 

Lastly, we followed reviewer FFyM’s suggestion on trying different initializations, and provided additional empirical study (in _Table 5 of the attached pdf_).

__[Reviewer BkAV]__
Reviewer BkAV made a comment about experiments using large-scale datasets. We replied and offered our perspectives on these points. To address this comment, we conducted an experiment on the full SVHN dataset which contains more than 600k images. The result is presented in _Table 6 in the attached pdf_.

In addition, reviewer BkAV asked about the performance of the proposed method under imbalanced annotation noise. We pointed out that we had already considered such a setting in our experiments and provided a pointer to the pertinent results in the appendix.

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