Spectral Clustering and Labeling for Crowdsourcing with Inherently Distinct Task Types
Authors: Saptarshi Mandal
Seo Taek Kong
Dimitrios Katselis
R. Srikant
Venue: Accepted by TMLR ()

Abstract: The Dawid-Skene model is the most widely assumed model in the analysis of crowdsourcing algorithms that estimate ground-truth labels from noisy worker responses. In this work, we are motivated by crowdsourcing applications where workers have distinct skill sets and their accuracy additionally depends on a task's type. Focusing on the case where there are two types of tasks, we propose a spectral method to partition tasks into two groups such that a worker has the same reliability for all tasks within a group. Our analysis reveals a separability condition such that task types can be perfectly recovered if the number of workers $n$ scales logarithmically with the number of tasks $d$. Numerical experiments show how clustering tasks by type before estimating ground-truth labels enhances the performance of crowdsourcing algorithms in practical applications.

Published in Transactions on Machine Learning Research (09/2025)
Spectral Clustering and Labeling for Crowdsourcing with Inherently Distinct Task Types
Saptarshi Mandal*
smandal4 @illkoois edu skong 10@ilknois. edu katselis @ @illinois. edu rsrikant @ill Wilniiiis... edu
Seo Taek Kong"
Dimitrios Katselis
R. Srikant
Department of Electricnl and Computer Engincering
University of Ilinnos Priana-Champpen
Reviewed on OpenReview: https: // openrviie.. net/ per/forum? id- (VV2juttedVVVo JVQjtzcUAc
Abstract
The Dawid-Skene model is the most widely assumndd model in the analysis crowdsourcing algorithms that estimate ground-truth labels from noisy worker responses. In this work, we motivated by crowdsourcing applications where workers have distinct skill sets and their accuracy additionally depends task's type. Focusing the case where there are two types of lasks, propose a spectral melhod to partition lasks inlo two groups such that worker has the same reliability for all tasks within group. Our analysis reveals separability condition such that task types can be perfectly recovered if the number of workers n scales logarithmically with the number of tasks Numerical experiments show how clustering tasks by type before estimating ground-truth labels enhances the performance of crowdsourcing algorithms in practical applications.
1 Introduction
Labeled datasets are required in many machine learning applications to either train classifiers using supervised learning or to evaluate their performance. Crowdsourcing a popular way to label large datasets by collecting labels from a large number of workers a low cost. The collected labels are often noisy due to many reasons including the difficulty of some labeling tasks and differing worker skill sets (Bonald & Combes, 2017 Gao et al. 2016)). The crowdsourced labels are then used to infer ground-truth labels by aggregating the responses of the workers. To analyze the quality of the inferred labels, statistical model for the workers' responses is often assumed.
A widely-studied model for crowdsourcing was first proposed by Dawid & Skene (979)). Their one-coin model assumes that workers have distinct skill sets, and each worker submits responses to a task independently of all other tasks and workers. Formally, each worker is assumed to submit a response X,j to a task j that correctly reflects the label yj with an unknown but fixed probability pa. Although the true labels are never observed, it is possible to estimate the unknown accuracy parameters p= (p by assuming that workers respond according to this statistical model. Once the accuracy parameters are estimated, labels estimate (Nitzan & Paroush 1983) Despite the simplicity of
can be estimated using the Nitzan-Parona this Dawid-Skene model, the optimal error rates of label estimation algorithms have only been understood relatively recently (Berend & Kontorovich 2014
Gao et al. 2016).
In this paper, we are interested in modcling worker responses when crowdsourced tasks demand different levels of expertise. The considered model motivated by expert behavior in radiology when labeling the presence of thoracic nodules can be more difficult because of their shape and size, when they are imaged with different resolutions, resulting in labels that are more reliable for tasks with one type than the other Shhirisshi et al. 2000 He et al. 2016 The contributions of the paper are the following:
* "Equal Contribution

---

Published in Transactions on Machine Learning Research (09/2025)
1. We consider a model for crowdsourcing that describes settings when workers label tasks that require different levels of expertise. Hence, different tasks can be associated with different types with this assignment of types being unknown. For this model, we propose spectral clustering algorithm to cluster the tasks into different types.
2. We analyze the performance of the proposed clustering algorithm and establish sufficient conditions for perfect clustering, focusing on the case of two lask types. A key contribution of this paper is proving that the clustering algorithm correctly classifies all tasks with high probability when the number of workers scales logarithmically with the number of tasks which is a natural condition in crowdsourcing applications. To the best of our knowledge, this result is novel for spectral clustering in the context. of crowdsourcing models.
Traditional spectral clustering analyses rely on matrix perturbation results, such as the Davis-Kahan theorem Yuu et al. 2014), which provides bounds on the 2o-norm of cigenvector perturbations when noise is added to the signal matrix. However, such bounds are insufficient (see Remark 2 for proving perfect clustering, which requires control over the horm of the perturbation, a significantly stronger and more challenging requirement. The Davis-Kahan theorem does not yield meaningful guarantees in this setting.
Moreover, exact-recovery arguments from stochastic block models Abbe
which rely on matrices with independent Bernoulli edges-do do not extend to the dependent, aggregated response matrix that arises in crowdsourcing (see Subsection 2.4 for a detailed discussion), necessitating the 160 de-perturbation analysis we consider here.
2018)
Our main contribution lies in leveraging the specific low-rank pegnualplus--erturbbllee structure of the expected similariyy matrix. We show that the perturbation remains sufficiently small and adapt techniques from Fan et al. (2018) to establish perfect clustering. While the proof is intricate, we provide a concise outline in the main body of the paper.
3. Clustering, and in particular, identifying the hard tasks may be the end goal in many cases. After the clustering step, one may choose to add more workers to the hard lasks and try to identify experts who are better at the hard tasks. But here, in addition, we also study whether the clusters can be helpful to perform better labeling. For this purpose, we conduct experiments using publicly available datasets. We compared two classes of algorithms: one where we first performed task clustering by type and then applied an algorithm designed for the traditional DS model to label tasks separately for each type and the other where the labeling algorithm is directly applied to the dataset without any clustering. Our experimental results show that clustering followed by labeling outperforms direct labeling in the datasets we considered. We also compared our algorithm with other algorithms which also divide tasks into types. Again, we found that our algorithm outperforms other task type-dependent algorithms.
4. In Scction 3.3 we theorctically examine the impact of the clustering step on downstream label estimation in the two-lype crowdsourcing model. Specifically, we derive a lower bound on the expected labeling error when applying DS-based weighted majority voting without clustering (i.e., typo-agnostic). We then compare this lower bound the performance of weighted majority voting with clustering, assuming task types are known. Our analysis shows that the latter asymptotically outperforms the lower bound for type-agnostic algorithms.
2
Background and Related Work
In this section, we first discuss the model under consideration followed by discussion on related prior works.
2.1 Problem Setting
For any positive integer m, denote by [m] the set fl...., m). We use the notation || to denote Iz-norm and || |loo to denote norm in this paper. Let n 2 be the number of workers labeling tasks. Each task [d] is associated with deterministic but unknown ground-truth labels yı, ;2,...; Va +13 following
2

---

Published in Transactions on Machine Learning Research (09/2025)
Gao et al. (2016). Each worker E [n] independently submits a response X, f-11++1] to each task j with Xij being independent across task index j. The goal is to estimate the true label yj +1, for every task j E [d.
Our model is motivated by crowdsourcing scenarios with more than one type of task. For simplicity of exposition this paper, we are considering there are exactly two types of tasks. More specifically, each task associated with a type ky {e,h) indicating "easy" and "hard" types, respectively, The task types are also deterministic but unknown, and task's type ky determines the accuracy parameter Pky = P(X;, vj) as the probability of worker i correctly labeling task j for all workers i e [n]. Using the accuracy vectors, we can define the reliability vectors Th E [- as т = 2pk - 1, where we denote the 2th element of pa- by Pki for all & E {e, h). Finally, we let the number of tasks of type k be da; clearly, de + d4 - d. We assume that dy is unknown and re # Th.
This hard-easy model is motivated by applications where certain tasks can inherently be more difficult than others. In keeping with the motivation of studying problems with hard and easy tasks, we assume the following:
Assumption 1
1. The reliability vectors satisfy
(a) l|rell2 1|ral22
(b) For some universal constant E (0,1/2),
1 + p 2
21 11-p,Vie [k] he,
(1)
There exists a E (0,1) such that d, = ad and dn (1 -1- We assume a 2 0.5, that is, 2 dr.
There erists positive constant F such that L. Tki > F for all types i E fe, Practically speaking, this assumption requires the average reliability of the workers to be positive for each type. Without this assumption, the label veclor y is only identifiable up to sign.
The assumption de 2 dn is practically motivated, as in most crowdsourcing settings, easier tasks tend to be more common than harder ones. Nevertheless, this assumption can be relaxed up to any a E (0,1) without affecting the validity of our results.
Our hard-easy model can be considered an extension of the one-coin Dawid-Skene (DS) model to two types of tasks. Henceforth, when we refer to the DS model, we mean the one-coin DS model unless explicitly stated otherwise.
It is worth noting that our model assumes all workers respond to all tasks, as it is motivated by applications where an institution contracts professionals to label a dataset. In this paper, we are not interested in applications that use platforms such as Amazon Mechanical Turk, in which workers independently select a sparse subset of tasks to label.
2.2 Related Work: Sawid-Skene Model
Crowdsourcing models differ in the assumed structure for the accuracy matrix P, where
Pi = P = mz)
In the one-coin DS model, P is a matrix with identical columns. There a vast literature on inferring labels from data under this model. These include the original EM algorithm proposed in Dawid & Skene (1979).
spectral-EM algorithm in Zhang et al. (2066), message passing algorithm in Karger al. (2013) 201 4b) label estimation from the principal eigenvector of the worker-similarity matrix studied in Dalvi al. (2013
to name few. For experiments, once the tasks are separated by types, we use the following common approach on the DS model to estimate the reliability vector тд from the responses X, denoted as fx, and use the Pirzuh-Paroush decision rule (Nizzan & Paroush 1983) to infer the labels for each type k:
1 + fkk Xij
ONP = sgn
Σ
log
Vj E [d,k, =
(2)
1 Pko
3

---

Published in Transactions on Machine Learning Research (09/2025)
where we assign the label as +1 if the argument inside the right-hand side is equal to zero In the reliability estimation step after the clustering step, we use the Triangular Esttimation (TE, algorithm proposed in Bonald & Combes (0117), which we use in our theoretical results. The reason we focus on this algorithm is that it has been compared to other algorithms and shown to perform better in real datasots. Additionally, by comparing the probability of labeling error expression derived from Bonald & Combes (2017) with the lower bounds in Gao et al. (2016), it can be seen that the algorithm is provably asymptotically optimal. We give a brief description of the TE algorithm in Appendix B
mixture model and, in the context of crowdsourcing, focus on the standard Dawid-Skene (DS) model where all tasks are assumed to be probabilistically identical. While their framework allows multiple labels per task, it does not incorporate heterogeneity across task types. Their Lloyd-type algorithm is closely related to EM with spectral initialization.
Lu & Zhou 2016) study
2.3 Related Work: More General Models
The DS model has been extended in numerous prior works to account for scenarios where the same worker may exhibit different reliabilities across various tasks. We review these extended models this subsection.
A rank-1 model studied by Khetan & Oh (2016) assumnss that P is an outer product of the accuracy of the workers and vector parametrizing the easiness of all tasks. A more general model was studied in (hhah et al. (2021), where P is assumed to satisfy strong stochastic transitivity (Shah et al., 2016). In the context of crowdsourcing, this assumption implies that workers can be ranked from most to least accurate and that this ranking does not change across tasks. The P that they consider can be associated with a rank as large as min(n, d). Lastly, the model in [hah & Leel (2018): Kim et al. (2024) assumes an accuracy matrix P that exhibits a low-rank structure with a fixed number of distinct entrics. They call k-type specialization model which is close to stochastic block model with & communities. The algorithms designed for this model in Shah & Lee 2018 Kim et al. (0024) have two-step approach. The first step involves clustering workers according to their types. The second step is estimating labels for each task j using weighted majority vote where significant weight is given to workers that match the type of task and negligible weight is given to all
other workers.
We now compare our model to the above models. As pointed out in Kim et al. (2024), both Khetan & Oh (2016) and (haah et al. (2021) consider the following: if worker A is better than worker B for any task, then this same ordering holds for all other tasks. Such monotonicity is not assumed in our model. The k-type specialization model in (Shah & Loe (018);; Kim et al. (2024) is somewhat similar in spirit to our model in the sense it atlempts to cluster tasks according to types. However, they also cluster workers according to types and their algorithm uses simple majority vote or a majority vote with two weights. Such a voting scheme is not optimal when diffcrent workers have different reliabilities (Nitzan & Paroush 1983).
While Ariu et al. (2024) also considers models with multiple task lypes, their selting and contributions are fundamentally different. They assume all workers are statistically identical, resulting in a rank-1 expected response matrix and making simple majority voting optimal. In contrast, our model captures heterogencity in worker reliabilities across task types, leading to rank-2 structure and necessitating the use of weighted majority voting. Moreover, their clustering method requires the number of workers to exceed the number of tasks for reliable recovery, whereas our analysis shows that only log(d) workers suffice making our approach significantly more practical in expert-labeling scenarios.
Several well-known probabilistic models also capture heterogeneity in crowdsourcing but pursue a different goal from ours. GLAD Whitehill al. (2009) represents each worker by a continuous "ability" and each item by a contimuus "difficulty" and learns these parameters via. DnpectaationMMxxiizzatiii without finite-sample error guarantees. Zhou et al. (2012) assigns separate latent distribution to every worker item pair and poses label aggregation as convex minimax-entropy problcm, again with no recovery bounds. The CBCC/EBCC family (Kim & Ghahramani] 2012 Li et al.) 2019) introduces latent worker communities with shared confusion matrices, improving aggregation through richer Bayesian priors while still treating tasks as i.i.d. and leaving task types unidentified. The tutorial Drutsa et al. (2019) and the recent paper Ibrahim et al. (2025) review these models from a systems perspective but do not provide new theoretical limits. In contrast, we focus discrete latent task types. We prove that. these types can be perfectly clustered with only O(lo((d)
4

---

Published in Transactions on Machine Learning Research (09/2025)
workers under constant reliability gap. Identifying such hard/easy groups is often end goal in practice (e.g,, triage or active relabeling) and is orthogonal to the per-item difficulty or worker-community structure emphasised by GLAD, Zhou et al. (2012), and BCC variants.
It is also important to note a recent work Han et al. (2025) which considers a different regime from ours: it exploits item features and per-worker continuous embeddings; The method does not posit latent task types; ground truths are not treated as hidden variables in the worker model, and no finite-sample guarantees are reported.
2.4 Related Work: Spectral Clustering
Spectral clustering has been widely studied in various contexts. Von Luxburg (2007) provides comprehensive review of this area. The basic idea behind spectral clustering is to analyze the spectrum of the expected observation matrix and then show that the spectrum of the observed data is close to that of the expected matrix (Von Luxburg, 2007 Ng et al. 2001). The specifics of these steps can differ significantly across applications. To the best of our knowledge, there is limited prior work on spectral clustering specifically for crowdsourcing data. Some works, including Dalvi et al. (2013); Shah et al. (2021) ): Khetan & Oh (2016)
explore the use of spectral methods in crowdsourcing, mainly focusing on analyzing worker simela-i matrices and improving label aggregation. However, most focus on label aggregation rather than explicilly clustering result that perfect clustering of tasks by type is possible with
tasks based their types. In particulor, (log(d)) workers when task-type reliabilities are well-separated in norm appears to be novel.
The condition that a logarithmic number of workers suffices for perfect clustering bears resemblance to sample complexity thresholds in other latent structure models, such as the degree condition for exact recovery in stochastic block models (SBMs) (Abbe
2018) and the signal-to-noise ratio threshold sub-Gaussian mixture models ŞLu& & Zhou, 2016). However, the analogy appears be superficial. In particular, unlike SBMs where Laplacian matrix entries (Abbe 2018 are independent Bernoulli random variables, the entries of our task-task similarity matrix are highly dependent, each aggregates the responses of shared workers taking integer values in [0, n]. These dependencies violate key assumptions in SBM-style analyses, which is why classical guarantees e.g., those based on Fiedler vectors do not directly apply in our setting.
To frame our setting in mixture-model terms we can treat the four task groups (easy, label +1), (easy, label -1), (hard, label +1), and (hard, label -1)- as four mixture components over binary vectors of worker responses. While this allows us to apply tools from mixture model analysis, even then, the guarantees differ: Lu & Zhou (2066) show perfect clustering with probability 1 1 eva when n ((lo(dd). whereas we achieve stronger guaranlee of 1 e- under the same conditions.
A more direct comparison is with SBM esact-recovery thresholds. For the general two block SBM with possibly differont within-class probabilities Pı1 = a log d/d, P22 = clog d/d and cross probability P12 = blo d/d, Abbe Abbe & Sandon (2015) show that exact recovery is informatioon-leeorttiallll possible iff
2018
L<va - vb)² + - (01=)((V x)(vē - vb)²] 2,
mîn zE(0,1)
(see Theorem in Abbe 2018)) ). By contrast, our exact recovery result. requires only n = Olog d) workers are
available, and the reliability gap satisfies ||rell2 ||r|| 1/ > 3n for some absolute constant 3 > 0, markedly weaker condition than the thresholds needed for SBM.
These differences highlight why SBM-style guarantees cannot be directly transferred to multi-type crowd- sourcing and motivated the new perturbation analysis considered in this work.
3 Main Results
Notation
For clarity, Table I summarizes the key symbols used throughout the paper. We follow standard conventions and do not use boldface for vectors; symbols like re, The and 0 denote vectors, while their indexed versions (e.g., rei) refer to scalars.
5

---

Published in Transactions on Machine Learning Research (09/2025)
For vector R we write ||||| for the Euclidean norm and || max, [zy] for the max norm. For a square matrix idxdd we define the infinity norm as || = max; 2 Megl i.e,, the maximum absolute row sum.
Symbol
Mcaning / Definition
[m]]
Index set {I....,m}
n, d
Number of workers and number of lasks, respectively
X1y E [-1,+11
Response given by worker i on task j
My ([1,+
Unknown ground-truth label of task j
ky {e.h)
Type of task j: either easy (e) hard (h)
pui
Probability that worker i correctly labels task of type k Reliability of worker on lype-k tasks
Thi 2pk
Te: Th
Reliability vectors for casy and hard tasks, respectively
de: da
Number of easy and hard tasks, respectively (de + dh d)
Proportion of easy tasks: de = ad, d, = (1 - -a)d
The amount by which Pki is bounded away from 0 and 1
F
Lower bound on average reliability: - The
T
X
Task-similarity matrix
0
Principal eigenvector of T used for clustering Threshold for clustering lasks based
Σ, 1ōyl
Rg
Low rank signal matrix defined Lemma Normalized eigengap of Ry as defined in Lemma Estimated reliability of worker i for type-k tasks Fraction of tasks mis-clustered by the algorithm
v(n-1Rn)
fki
17
8 Drre a, pn (rk)
Ratio between the distinct entries of the principal eigenvector of E[T] Problem-deeendent term in the perfect clustering bound in Theorem [ Error exponent for DS-based label estimation on type-k tasks
Table 1: Summary of notation used throughout the paper. Subscripts E {e, h3 indicate task type when relevant.
3.1 Algorithm
We proposed clustering algorithm for clustering tasks by type from the observation matrix X. For the goal of estimating the ground truth label yj for each task j [d], we propose a two-step approach:
1. Clustering Tasks by Type: Separate the tasks into two clusters using Algorithm
DS Algorithm for Label Estimation: Use the following DS model-basod algorithm on each of those clusters to estimate the labels within each cluster:
(a) Use the TE algorithm (see Appendix for details of TE algorithm) to estimate the reliability vector for cach cluster.
(b) Estimate the labels using the plug-in NP rule given in Equation 2
The clustering method described in Algorithm ! computes the principal eigenvector of the similarity matrix T n - xxXX X denoted as 6. Each task j is then assigned one of the two clusters by thresholding the magnitude of the 7th entry 0y with a threshold X = E, 16,l. We adopt the convention that eigenvectors are unit norm.

---

Published in Transactions on Machine Learning Research (09/2025)
Algorithm 1 Clustering tasks into hard and easy types
Input:
Worker responses E (-1,+1)xx4
Compute the principal eigenvector of the task-similarity matrix T n - Set threshold
Σy ldyl-
Classify task lypes by thresholding:
if 0 2
R2
h if 18yl < j.
Return: Task type estimates ki,.... hs.
3.2 Clustering
In this sub-section, we analyze the performance of the clustering Algorithm ! algorithm only needs to classify tasks into two groups, as long as all the easy tasks fall into one group and all the hard tasks fall into the other group, Later, we will apply the DS-based algorithm separately to each cluster and hence, it does not matter which group we call hard and which group we call easy. Therefore, the clustering error associated with Algorithm D can be defined as
We note that our clustering
=
min (e
d
E 1 [1)((
(3)
We show that the probability of perfectly recovering clusters, i.e. 1) 0, approaches with rate exponentially fast in n. This is preciscly stated and shown in Theorem
To understand why task types can be perfectly recovered from clustering, we characterize the spectral properties of the task-similarity matrix T. For simplicity of analysis, we re-arrange the tasks such that easy tasks are in the first de columns of and hard tasks are the remaining columns. Knowing the arrangement of columns implies knowledge task lypes, but we only use this to simplify exposition and note that this is not used by our algorithm and does not affect our analysis.
Denote Ia and laxb to be the d identity matrix and the all-ones matrix of size b, respectively. We first show that the expected lask similarity matrix B[T) == E x T X] can be decomposed into sum of low-rank and sparse components,
Lemma 1 Define the matrix
1-1 Ry
|1 [1rall2taxxd xd. Th Telddxxd
re rn unllaxdd
) diag(y)
diag(y)
I| L2 xds
and a diagonal matriz
S 1a diag (IlIra 12 Lixe 1Ia
The matria n n Ry is rank-l with e < 2, and its normalized eigen-gap v(n v(n-11nn Ryy (' >2(n-1 R,y)) between its two largest eigenvalues X1, d2 can be eapressed as:
unn-'R V /dellre 12 1 + (d.dn nd
(4)
Further, we have the decomposition
E[T] -IP,, + S.
(5)
The proof is provided in Appendix P
7

---

Published in Transactions on Machine Learning Research (09/2025)
Our key motivation for Algorithm 1 is based the observation in Lemma 2 where the principal eigenvector Ry, of the low-rank signal matrix n n- Ry has a special structure. Specifically, there exists a bijection between the magnitudes of entries in the principal eigenvector and task types. The proof follows from the cigendecomposition matrix n n=! Ry and is presented in Appendix
Lemma 2 Suppose re Th + O. Then, the principal eigenvector of the matrin n n Rg has the following form:
+dd 1dxx1
cnn = diag(y)
(6)
v sd Idaxl
where
w + V u2 dn
(7)
de
and
de dellrel 1/3 dn 1ra1/
2d. r? rn
In the alternative case that re r.rn rh = 0, we have that
Vah x1 0d,x1
v(n RRy) = diag(v)
(8)
Denote the distinct magnitudes in ((n-)Ry))) corresponding to easy and hard tasks as (n and Pn (n- Ry) respectively. It turns out that p.(n- -1 Ryy # Pe(n R.y) as long as ||rella * ||rlll2- Consequently under this condition, if we have access the signal matrix n Rgg we can differentiate tasks of one type from another by inspecting the entries of the vector v(n- Ryy) Specifically, the task type be recovered by thresholding the magnitudes of the entries with the average
de d ue(nn RRy d pm Rg). (Ry)
dp
p(n Roy
However, we can only access the principal eigenvector è of T -= theorem shows that the noisy entries in 0 are sufficiently concentrated to those in such that the threshold rule applied to è perfectly recovers the task types.
x instead of vnn Ry). The following
Theorem Under Assumption if the number of tasks d satisfies
C1
d D(res The a, d)
(10)
then Algorilim relurns lask lype estimates such that
P( 2 2x exp exp(-CanD(ee The ox, d)),
Th,
(11)
where the problem-dependent quantity ah, d is defined as follows:
ar characterizing the error exponent and the requirement
(1-0)'p w(n (R,11ls-111 2 when, r rh # 0,
vs*+1 Dr,e,Th (1-a)² u (nn-nnnnnnn RR,)
(12)
when, r. rh 0
and C₁ and C2 are universal constants, independent of the problem parameters.
Remark Inspecting the problem-dependers exponent D(re, Thy a, d) in Theorem reveals that, when the reliability vectors are not orthogonal, the expoment increases (as [s] is an increasing function of [w| and |s] under Assumplion with
de ||r 112 de T
|
2d, In
This implies that the probability of perfect clustering improves (i.e., has better exponent) when there is large gap in the norms of the reliability vectors and/or or the angle between them is large.
8

---

Published in Transactions on Machine Learning Research (09/2025)
3.2.1 log(d) Workers Suffice for Perfect Clustering
From the above Theorem ! we show that for achieving a clustering with 7j = 0 using Algorithm we only need the number of workers a to be of order ((log()) under our model assumptions. From Theorem 1 the requirement on for the event of perfect clustering with probability 2 1 6 becomes:
log
2d
Y 2
C2 Th, a,
The next lemma provides an intuitive condition on the reliability vectors re and ra showing that (log(d)) workers suffice for perfect clustering.
Corollary 1 If there exist some universol consland with
1,
|
1r l12 8
(13)
then, under Assumption Algorithm achieves clustering error with probability at least 1 5 when
Cgcz log (2))
n ス (1 - a) 32
(14)
where Cg is on absolute constant given as Cg
160 C2
Recall from our model assumptions, indeed have ||rel ||r On)). Hence, the above condition in Equation 13 is quite practical. It requires that the normalized norm gap between the reliability vectors is bounded away from zero.
The idca behind proving Corollary is to show that the problem-dependent parameter D(re: Th, a, d) is of order O11). This shown detail in Section F.5
3.2.2 Proof Sketch of Theorem
Building upon the above discussion, we give outline of the key ideas involved in proving Theorem below. The detailed proof of Theorem is given in Appendix
1. Recall the structure of ((n--R,) the principal eigenvector of the signal matrix n- n-1R, Ry from Lemma We prove that the magnitudes of v(n o(n'RR,) corresponding to different types are separated when Ielll # ||ra|22- This suggests that under this condition if we had access to u(n-1R,, then we can cluster tasks by using a threshold to differentiate the magnitudes of the clements of vnn- Ryy) But we do not. have access this eigenvector, therefore the rest. of the proof shows that the eigenvector we have access is a small perturbation of v(n "Ry).
2
We note that == R S + N, where N is a random matrix noise term given by N = T E[T]. We use matrix Hoeffding incquality to show that this noise term is small in the infinity-norm sense. This is shown in Lemmal
Lemma For any t 0 and any positive values of n and d, the task-similarity matrix T concentrates around its expectation given by the noise matrix concentration follows:
n
P 2) < 2d exp
(15)
2d
The proof is given in the appendix
F.1
Since S is a diagonal matrix, it can be easily shown that its spectral norm is sufficiently small when the number of tasks is large, which is the case in erowdsoureing models. This observation, along with

---

Published in Transactions on Machine Learning Research (09/2025)
Lemma implies that the spectral norm of S + N is sufficiently small with high probability. Then, using the result of Fan et al. (2018), we show that the principal eigenvector of the matrix T which is denoted as è has structure similar to that of u(n ((n")))) i.e, é is a perturbed version of v(n o(n")Ry) in the le-- -nom sense, where the perturbation small under our model. This is shown in Lemma
Lemma P(n satisfies Cs(1-a)"p uu(n (o(n--Rydd > 0, then, for every 0 < C3(1
a))v(n RR)d 1, the event
C.a
min 6
100 v(n Rg) loo 2
(1 po (c+1)
(16)
occurs with probability at most 2d exp (nn where C3 and C₁ are universal positive constants.
The proof of Lemma D quite involved and is provided in Appendix F.2 Below, outline the key intuition behind the approach. Let Ç denote the angle between reliability vectors re and The Our analysis distinguishes between two regimes:
Sufficiently large Ç: In this case, we approximate the expected task-similarity matrix using a rank-2 signal matrix.
Small Ç: Here, we employ a rank-1 approximation of the sask-iimilarity matrix.
A crucial aspect of our analysis is identifying the transition between these regimes, which requires a careful, structure-aware examination of the task-similarity matrix.
4. The lsc-norm concentration in Lemma 4 yiclds a sufficient condition for perfect clustering. In particu- lar, we show that ||ê - RR, |oo is with high probability, al most 1 min(m.(nn ma (n (R,),,,),, where (n = (ee 1 Ryy - p(n RR,) and m, (1n)))))))))))))))))) = |u(n "R,) - pn Ry)l- A little thought shows that this would imply that all tasks are clustered perfectly.
Remark 2 In the above proof sketch, we leveraged the -orm perturbation of the eigenvectors of the lask-similarily malrin, as established in Lemma A to derive the perfect clustering resull in Theorem 7 where log(d) order of workers suffice. Nezt, we discuss why direct application of the Davis-Kahon theorem (Yu) et al. 2014), one of the most commonly used perturbation results in clustering literature, yields vacuous bounds in this context.
The Kahis-Kahan theorem characterizes eigenvector perturbations as a function of matria perturbations in the 12-norm of the eigenvectors. However, it ineffective for obtaining meaningful norm bounds on eigenvector perturbations. standard approach convert an 12-norm bound into an -nom bound relies the inequality ||<=||> || for a vector in Rdd This introduces an undesirable. vd factor, leading to requirement that the number of workers must scale polynomially with the namber of tasks which is on impractical condition for crowdsourcing applications.
This limitation highlights the necessity of more refined analysis, as developed in our approach, to ensure that perfect clustering is achievuble under realislic condilions. Notably, the Davis-Kot Kahan theorem does not exploit any special structure of the matrir that is being perturbed while the result in Fan et al. (2018) allows us to erploit a low-rank structure that we have identified in the crowdsourcing task- aask-immllarity matriz.
3.3 How Useful is Clustering for Labeling?
A natural question to ask in this two-type model is how important is the clustering step for the subsequent label estimation. Can one use a weighted majority voting estimate for the labels using a single weight vector across all tasks? The following proposition gives a lower bound on the expected labeling error for such type-agnostic weighted majority voting (TA-WMV) algorithms in this context.
Proposition 1 Let the WMV estimate using a single weight vector across all task j is defined as:
WW (w) = sgn Σ wiXii
Vj Vi id
10

---

Published in Transactions on Machine Learning Research (09/2025)
for some weight vector w. We consider weight vectors belonging to the set wi S |wa| Wa for all workers with and wa two posilice constants such that 0 < wn S < oc. Under this construction, for any E {-1,+1} the average labeling enror rate for the type-agnostic WMV algorithm can be lower bounded as
lim inf log min E n10000
1
Σ 1
(1r) + vs))
2
lim sup max min (n, rk),
à
n
for any ground-truth vector y E {-1, (-1, where the error exponent pn, rk) is given by
1 1-
Tki
+ two 1 Tki
(x(w,T))=- = inf 120
log
e tw;
(17)
2
2
The above result is a generalization of Theorem 5.1 in Gao et al. (2016) our proposition uses weighted majority voting for arbitrary weights for a type k, whereas their result is for majority voting. The proof of Proposition 1 is given in Appendix G It's worth noting that the paper Gao & ZZoou (2013) has shown lower bounds on labeling performance for two-type model for these two algorithms: projected expected maximization and majority voting (Theorems 4.2 and 4.3 in Gao & Zhou (2013)). Compared to them, we have lower bound on the performance of labeling for the weighted majority voting, To understand the limitation of TA-WMV algorithms, it is instructive to compare the error rates in Proposition D with the achievable rates by an algorithm that accounts for type difference among different tasks under the setting when task types are known but the reliability vectors (Fe, Th) are unknown.
Proposition 2 Assume V₂ min,mara.bbe v [kaakal for each k E feehh which is satisfied if there are al least two workers with non-zero reliabillly values for each lype. If the number of workers sulisfies n 2 /3p/r, and the number of tasks per type satisfies
n²
du 2 Cs min(p 12) (rk) + log(6n"))
(18)
for some universal constant Cs then, the TE algorithm to estimate the reliability vectors followed by NP- WMV for label estimation separately for each type (when type information is known) achieves labeling ervor rate satisfying
Σ de exp (-nD),(kk),,
53
kE(e,h)
where 0j and yj are the estimated and true labels of lask j, respectively, and
log (V(++ra)(1- - -1r)) (rk))) = Σ 1=1
(19)
The error exponent Equation 19 for type-dependent weighted majority voting can be related to the error exponent for the type-agnostic weighted majoring voting in Equation 17 through the identity
$ (Tk) = max (w,
Recall from Proposition [ the lower bound on the error exponent for type-agnostic Weighted Majority Vote is max, ming (ww,,, r4) and from the definition of (rk)),, , it is clear that max,, min; (pw,, rx) < (rx)..) Vk e {e, h). It is easy to see that, in most cases, the inequality is strict for both E he Therefore, TA-WMV is strictly worse than WMV applied to each task type separately. The proof Proposition 2 is provided in the Appendix H
This error exponent serves asymptotic lower bound for the laheling error one-coin DS model corresponding reliability type rı (aao al. 2016).
11

---

Published in Transactions on Machine Learning Research (09/2025)
3.3.1 Labeling Error Guarantee for Our Two-Step Approach
By combining the perfect clustering result from Theorem | with the labeling error guarantee for the known- type case from Proposition [ we immediately obtain the labeling error guarantee for our two-step approach.
This approach consists of: (1) clustering tasks by type using Algorithm [ and (2) applying the DS-based
algorithm TE with NP-WMV for label estimation within each cluster. For completeness, the labeling guarantee of this two-step approach is provided in Theorem in the Appendix D with its proof in Appendix
4 Experiments
In this paper, we present experiments with real-world datasels, pseudo-real datasets, and synthetic datasets to supplement the theory presented in the previous sections. By pscudo-real datascts, we mean the following: some real-world sets do not contain all the information we need to run our experiments and therefore, we generate some of the data we need using the available data in the datasets. In such cases, we will explain how we filled the required data.
1. First, we compare our two-step algorithm (clustering tasks and then applying a DS algorithm to each type of task) with a single-step DS algorithm (i.e., applying a DS algorithm to all the tasks). Our experiments clearly show the benefit of clustering. Although our theoretical analysis primarily employs TE followed by WMV with NP-weights the Dawid-Skene (DS) algorithm, we also compare DS algorithms with and without clustering across various other DS algorithms to demonstrate the benefits of clustering: unweighted majority vote (MV), ratio of eigenvectors (ER, Dalvi et al. 2013),
TE (Bonald & Combes (2017)), and Plug-in gradient descent (PGD, Ma et al. 2022). A large number of algorithms have been proposed for crowdsourcing including Spectral-EM (Zhang et al. (2016)), ) and message-passingg (Karger et al. (2014a)) to name just a few. Exhaustively comparing with all the algorithms is difficult, so we have chosen compare our algorithm to ER, TE, and PGD for the following reason: many algorithms have been compared in Dalvi al. (2013), Bonald & Combes
(2017) and Ma et al. (0022. where it was shown that ER, TE, and PGD consistently out-perform other algorithms.
Next, we compare our algorithm with other algorithms that also consider tasks of different types. We demonstrate that our algorithm performs better the datasets considered.
The datasets we used for our experiments are the following:
Two of the real-world datasets we used which are called the "Bluebird" (Welinder et al. 2010 and "HC-TREC" (Buckley et al. 2010) are complete datasets, i.e., the response matrix has no missing entry.
2. Three other real-world datasets, "Dog" (Deng et al. 2009 "Temp" (Sno et al. 2008 and "RTE" (Snow et al. 2008) are sparse datasets that do not provide responses corresponding to all worker-task pairs as in our motivating example in the introduction. To handle this, for the "Dog" dataset that contains 4 classes, we converted it to binary groups (0,2) vs. (1,3) following Bonald & Combes (2017). Then we calculate the fraction of correct labels (given by workers) for each task based on the ground truth and the available responses and classify half of them (the half with the most accurate worker responses) as easy tasks and the rest as hard tasks. Then, we estimate the empirical reliabilities of the workers for each type of task and use this to generate synthetic entries for the missing worker-task pairs in the response matrix. Similar treatments for the no-response entries are done for, "RTE" and "Temp", each of which contains binary truth values. The number of workers and tasks for all five datasets ("Bluebird", "HC-TREC", "Dog", "Temp", and "RTE") are provided in Table 2
Obtaining real-world crowdsourcing datasets for healtheare examples that we mention the Intro- duction is difficult due to privacy reasons. With the limited information available from a radiology dataset, created synthetic dataset and we report the results from the dataset in Appendix C.1
12

---

Published in Transactions on Machine Learning Research (09/2025)
Table 2: Dataset Descriptions
Dataset
# Workers
# Tasks
Bluebird
39
108
Dog
78
807
RTE
164
800
HC-TREC
10
1000
Тemp 76
462
Table 3: Label estimation errors for different crowdsourced datasets. "TA" and "C" indicate that labels were estimated without (lype-agnostic) or with clustering.
Dataset
MV
ER
TE
PGD
Bluebird-TA
24.07
27.78
17.59
25.93
Bluebird-C
24.07
11.11
12.96
12.96
Gain
0.00
16.67
4.63
12.97
Dog- TA
26.15
19.85
13.64
19.01
Dog-C
26.15
0.78
12.23
20.56
Gain
0.00
19.07
1.41
-1.64
TREC-TA
33.70
68.80
67.30
30.80
HC-TREC-C
33.70
40.90
30.60
30.80
Gain
0.00
27.90
36.6
0.00
Comparing with Traditional DS Algorithms: We observe that clustering improves performance in the dataset considered. In the case of RTE and Temp datasets, with without clustering, the accuracy of label estimation is 100%, which is why we did not include them in Table 3 Hence, our results show that clustering does not hurt the accuracy even in cases where it may not be required.
Comparison with Task-Specific Reliability Models: As discussed in the related work section, several previous papers address models with multiple types of tasks and use different lask-specific reliability models infer task labels. Notable works include Khetan & Oh (2016), Shah al.) (2021), Shah & Lee (2018).
Kim al. (2024) to name few. The model in Khetan Oh (2016) assumes that [[[] is rank-1 matrix. Clearly, this is not true if there is more than one type of task. The algorithm in Shah et al. (022) involves
large number of parameters, leading to very poor performance the datasets we used, therefore we are not
comparing it with our model. Thus, we restrict the comparison of our algorithm to those in Shah & Lee
(2018) and Kim et al. 2024).
Table 4: Comparison of our approach with Task-specific Reliability Models. "TE-C' is our two-step approach clustering followed by TE-WMV.
Dataset
TE-C
SDP
SS
Bluebird
12.96
24.81
22.62
Dog
12.23
34.56
51.70
TREC
30.6
38.22
49.39
Temp
1.93
50.35
In Table 4 columns "TE-C", "SDP" and "SS" correspond lo our two-step approach, SDP-based algorithm in Kim et al. (2024) and SS algorithm from Shah & Lee (2018), respectively. We used the MATLAB code provided by the authors in Kim et al. (2024) for running different 'SDP' and 'SS' algorithms and listed the error minimized over the input parameter the number of specializations from (2,3.4] We see that our algorithm outperforms SDP and SS in the datasets considered above.
13

---

Published in Transactions on Machine Learning Research (09/2025)
Runtime Comparison: We report the runtime performance of our proposed two-step algorithm to illustrate its practicality. In particular, we compare the type-agnostic DS-based TE. algorithm (denoted TE-TA) with our type-dependent pipeline (denoted TE-C), which consists of spectral clustering followed by TE and NP-WMV applied separately to each task cluster.
The clustering step is dominated by the computation of the principal eigenvector of the task-similarity matrix of size d'x d, which can be performed in (dP) time using power iteration. The TE algorithm (see Appendix B is dominated by the computation of the worker-similarity matrix and can be implemented in O(n d) time.
Table 5 presents the average runtime (in seconds) of the algorithms on the three real-world datasets used in our experiments. All runtimes were measured on a standard CPU using Google Colab. We observe that the overhead due to clustering is negligible in practice. We observe that the clustering runtime increases from Bluebird to HC-TREC, consistent with its polynomial dependence on the number of tasks d. In contrast, the TE labeling stop, which scales as O(n2d), d), fastest on HC-TREC due to its small number of workers (n 10), and slowest on Dog, which has the largest 78.
Dataset (workers, tasks)
Clustering Step
TE-TA (DS-based)
TE-C (Our approach)
Bluebird (39, 108)
0.0998
0.0318
0.1280
Dog (78, 807)
0.2217
0,2064
0.5935
HC-TREC (10, 1000)
0.2927
0.0212
0.3207
Table 5: Runtime comparison (in seconds) of TE algorithms with and without clustering.
For comparison with other type-dependent algorithms, we used the MATLAB implementation of the SDP- based method proposed by Kim et al. (2024). Due to the complexity parameter tuning and the reliance on a semi-dcfinite program solver, the runtime for this method is substantially higher, ranging from several minutes to over 30 minutes on standard laptop with 16GB RAM.
A broader question: A broader question in crowdsourcing, beyond the scope of this paper, is assessing the validity of the DS model and its extensions in a data-driven manner for given dataset. In Appendix C.2 we present a dataset where plain majority voling outperforms weighted majority voling. This suggests that. the DS model or its variants may not be suitable in such cases, either because the underlying mathematical assumptions do not hold or there is insufficient data to accurately estimate worker reliabilities.
5 Discussion: Extensions and Practical Implications
The analysis in this paper focuses on a two-type crowdsoureing model where each worker labels every task. The main contribution is identifying separability condition for perfect clustering, which implies that (log(d)) workers suffice for perfect clustering (1). In this section, discuss possible extensions of our algorithm to more general settings and the practical implications of our work.
Sparse response matrices. Unlike some datasets considered in the paper (e.g., "Blue-bird", "HC-TREC"), many practical datascts yicld sparse response matrices. Real-world datascts with sparse responscs examined here include "Dog", "Temp", and "RTE". To fit. these into our model, we preprocess the sparse response matrices by imputing missing entries using only the observed labels (without access to ground truth), consistent with common approaches in the literature. We then evaluate the performance of our clustering- pipeline against existing algorithms designed for multi-type crowdsourcing. Extending the theoretical analysis to sparse response matrices is an important direction for future work.
Extension to more than two types of tasks and when clustering is beneficial. Our algorithi can, in principle, be extended to more than two types (e.g., via k-means clustering on the top eigenvectors). However, accurate estimation in such settings requires that type-specific reliability vectors be sufficiently separated and that each type has enough labeled examples. The algorithmic pipeline presented in this work is most useful when worker skills vary by task type. Heuristically, a clear eigengap after the first two components
14

---

Published in Transactions on Machine Learning Research (09/2025)
can be used diagnostic indicator of multi-type structure. If no eigengap is present, type-agnostic aggregator (e.g., DS) is reasonable fallback. Extending the theoretical guarantees to more than two types remains an important direction for future work.
6 Conclusion
We considered a crowdsourcing model which is more appropriate than the Dawid-Skene model when there are tasks that require different levels of skill sets. Then described spectral clustering algorithm that clusters tasks by difficulty and analyzed its performance to characterize the condition for perfect clustering. Experiments with real-life datasets demonstrate the benefits of in label estimation when combined with TE and NP-WMV for each task type separately.
An intriguing direction for future research extending our clustering approach to models with more than two task types. While our algorithm naturally generalizes multiple types types-by applying k-means clustering entries corresponding dominant eigenvectors accurate label estimation in such settings requires sufficiently distinct reliability vectors across task types. Morcover, estimating multiple reliability vectors introduces additinn ional data requirements. Though our focus in this work has been the (wo-lype set tett,ng, the extension to more than two types presents rich theoretical challenges, making it promising avenue for further exploration.
Broader Impact Statement
In accordance with the TMLR guidelines on potential societal impacts and ethical conduct, the authors are not aware of any direct or indirect negative implications of this work. The proposed method may help reduce labeling costs in crowdsourcing by enabling more accurate label aggregation in heterogeneous task settings. Our findings suggest that two tase modeling approach captures meaningful structure in real datasets, and may serve a foundation for more general task-type inference in future work.
References
Emmanuel Abbe, Community detection and stochastic block models: recent developments. Journal of Machine Learning Research, 18(177):1-86, 2018
Emmanuel Abbe and Colin Sandon. Community detection in general stochastic block models: Fundamental limits and efficient algorithms for recovery. In 2015 IEEE 56th Annual Symposium Foundations of Computer Science, pp. 670 688. IEEE, 2015.
Kaito Ariu, Jungscul Ok, Alexandre Proutiere, and Seyoung Yun. Optimal clustering from noisy binary feedback. Machine Learning, 113(5):2733-277) 2764,, 2024.
Daniel Berend and Aryeh Kontorovich. Consistency of weighted majority votes. Advances in Neural Information Processing Systems, 27, 2014.
Thomas Bonald and Richard Combes. A minimax optimal algorithm for crowdsourcing. In Advances in Neural Information Processing Systems, volume 30, 2017.
Chris Buckley, Matthew Lease, Mark D Smucker, Hyun Joon Jung, Catherine Grady, Chris Buckley, Matthew Lease, Mark D Smucker, Catherine Grady, Matthew Lease, et al. Overview of the trec 2010 relevance feedback track (notebook). In The nineteenth tert retrieval conference (TREC) notebook, pp. 3-92, 2010.
Nilesh Dalvi, Anirban Dasgupta, Ravi Kumar, and Vibhor Rastogi. Aggregating crowdsourced binary ratings. In Proceedings of the 22nd International Conference on World Wide Web, WWW '13, pp- 285 294, New York, NY, USA, 2013. Association for Computing Machinery. ISBN 9781450320351. doi: 10.1145/2488388.2455 24884444
A. P. Dawid and A. M. Skene. Maximum likelihood estimation of observer error-rates using the em algorithm. Applied Statistics, 28(1):20-24 28, 1979.
15

---

Published in Transactions on Machine Learning Research (09/2025)
Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei. Imagenet: A large-scale hierarchical image database. In 2009 IEEE Conference on Compuler Vision and Pattern Recognition, pp. 248-255, 2009. doi: 10.1109/CVPR.2009.555 200.500888.
Alexey Drutsa, Viktoriya Farafonova, Valentina Fedorova, Olga Megorskaya, Evfrosiniya Zerminova, and Olga Zhilinskaya. Practice of elficient data collection via crowdsourcing at large-scale. ar preprinl 01Xiv1112..4414 2019.
Jianqing Fan, Weichen Wang, and Yiqiao Zhong. An foc cigenvector perturbation bound and its application to robust covariance estimation. Journal of Machine Learning Research, 18(207): 42, 2018
Chao Gao and Dengyong Zhou, Minimax optimal convergence rates for estimating ground truth from crowdsourced labels. arXiv preprint 1rXim:3310.5000 2013.
Chao Gao, Yu Lu, and Dengyong Zhou. Exact exponent in optimal rates for crowdsourcing. In Maria Florina Balcan and Kilian Q. Weinberger (eds.), Proceedings of The 33rd International Conference on Machine Learning, volume 48 of Proceedings of Machine Learning Research, pp. 603 611, New York, New York, USA, 20 22 Jun 2016. PMLR.
Tao Han, Huaixuan Shi, Xinyi Ding, Xi-Ao Ma, Huamao Gu, and Yili Fang. Mixture of experts based multi-task supervise learning from crowds. In Proceedings of the AAAT Conference on Artificial Intelligence, volume 39, pp. 14256 14264, 2025.
Lan He, Yanqi Huang, Zelan Ma, Cuishan Liang, Changhong Liang, and Zaiyi Liu. Effects of contrast- enhancement, reconstruction slice thickness and convolution kernel on the diagnostic performance of radiomics signature in solitary pulmonary nodule. Sci Rep, 6:34921, October 2016.
Shahana Ibrahim, Panagiotis A. Traganitis, Xiao Fu, and Georgios B. Giannakis. Learning from crowdsourced noisy labels: A signal processing perspective, 2025. URL httpp://arxxiv.orr//aa///2009 26992
David R. Karger, Sewoong Oh, and Devavrat Shah. Efficient crowdsourcing for multi-class labeling. SIG- METRICS Perform. Evol. Rev., (1 92, jun 2013. ISSN 0163-5999. doi: 10.1455/294432.246778.. URL
246677
David R. Karger, Sewoong Oh, and Devavrat Shah. Budget-optimal task allocation for reliable crowdsourcing systems. Oper. Res., 62(():1-24, feb 2014a. ISSN 0030-364X. doi: 10.
David R. Karger, Sewoong Oh, and Devavrat Shah. Budget-Optimal Task Allocation for Reliable Crowd- sourcing Systems. Operations Research, 62(1):1 24, February 2014b. doi: 10.1287/opre.2113 2011..1.3...... 1235. URL https://ideas. www.ideassrrppe...o wttt:////.......r/./ee.ooooo/o//
imm http:///oorrrr//////00111111--1 html
Ashish Khetan and Sewoong Oh. Achieving budget-optimality with adaptive schemes in crowdsourcing, In D. Lee, M. Sugiyama, U. Luxburg, 1. Guyon, and R. Garnett (eds.), Advances in Neural Information Processing Systems, volume 29. Curran Associates, Inc., 2016.
Doyeon Kim, Jeonghwan Lee, and Hye Won Chung. A worker-lask specialization model for crowdsourcing: Efficient inference and fundamental limits. IEEE Trans. Inf. Theor. (0(33)2076 2117, March 2024. ISSN 0018-9448. doi: 10.1109/THI TIT 2023.3315720. URL htttps://doo. fttps://ddo.oorg1000 1ww1//199TTTTT 2023 3315720
Hyun-Chul Kim and Zoubin Ghahramani. Bayesian classifier combination. Artificial Intelligence and Statistics, pp. 619-627. PMLR, 2012.
Yuan Li, Benjamin Rubinstein, and Trevor Cohn. Exploiting worker correlation for label aggregation crowdsourcing. In International conference on machine learning, pp. 3886 3895. PMLR, 2019.
Yu Lu and Harrison H Zhou. Statistical and computational guarantees of lloyd's algorithm and its variants.
ar Xiv preprint ar X 161..1100000 2.0099, 2016.
16

---

Published in Transactions on Machine Learning Research (09/2025)
Yao Ma, Alex Olshevsky, Venkatesh Saligrama, and Csaba Szepesvari. Gradient descent for sparse rank-one matrix completion for crowd-sourced aggregation of sparsely interacting workers. J. Mach. Learn. Res., 21 (1), jun 2022. ISSN 1532-4435.
Andrew Ng. Michael Jordan, and Yair Weiss. On spectral clustering; Analysis and an algorithm. Advances in neural information processing systems, 14, 2001.
Shmuul Nitzan and Jacob Paroush. Small panels of experts in dichotomous choice situations Decision (0.1111/1.540055115199333
Sciences, 14(3):314 325, 1983. doi:
Devavrat Shah and Christina Lec. Roducing crowdsourcing to graphon cstimation, statistically. In Amos Storkey and Fernando Perez-Cruz (eds.), Proceedings of the Twenly-Fine First International Conference on Artificial Intelligence and Statistics, volume 84 of Proceedings of Machine Learning Research, pp. 1741 1750. PMLR, 09 11 Apr 2018.
Nihar B. Shah, Sivaraman Balakrishnan, Adityanand Guntuboyina, and Martin J. Wainwright. Stochastically transitive models for pairwise comparisons: Statistical and computational issues. In Proceedings of the 33rd International Conference International Conference Machine Learning Volume 48, 1CML'IC '66
pp. 11-20. JMLR.org, 2016.
Nihar B. Shah, Sivaraman Balakrishnan, and Martin J. Wainwright. A permutation-based model for crowd labeling: Optimal estimation and robustness, IEEE Transactions on Information Theory, 67(6):4162 4184, 2021. doi: 10.1109/TII T0000///TT.220.034442. 3020.3045613.
Junji Shiraishi, Shigehiko Katsuragawa, Junpei Ikezoe, Tsunco Matsumoto, Takeshi Kobayashi, Ken-ichi Komatsu, Mitate Matsui, Hiroshi Fujita, Yoshie Kodera, and Kunio Doi. Development of a digital image database for chest radiographs with and without lung nodule. American Journal of Roentgenology, 174 (1):71 74, 2000. doi: 10.2214/aa 1/2214//j:.17..111775
PMID: 10628457.
Rion Snow, Brendan O'Connor, Daniel Jurafsky, and Andrew Ng. Cheap and fast- but is it good? evaluating non-expert annotations for natural language tasks. In Proceedings of the 2008 Conference Empirical Methods in Natural Language Processing, pp. 254 263, Honolulu, Hawaii, October 2008. Association for Computational Linguistics.
R. Srikant and Tei Ying. Communiention Networks:: An Oplimization, Control, and Stochastic Networks Perspective. Cambridge University Press, 2013. doi: 10.0117/CB09978119556633
Clrike Von Luxburg. A tutorial on spectral clustering. Statistics and computing, 17(4):395 416, 2007.
Peter Welinder, Steve Branson, Serge Belongie, and Pietro Perona. The Multidimensional Wisdom of Crowds. Tn NIPS, 2010.
Jacob Whitehill, Ting- fan Wu, Jacob Bergsma, Javier Movellan, and Paul Ruvolo. Whose vote should count more: Optimal integration of labels from labelors unknown exportise. In Y. Bengio, D. Schuurmans, J. Lafferty, C. Williams, and A. Culotta (eds.), Advances in Neural Information Processing Systems, volume 22. Curran Associates, Inc., 2009.
Y. Yu, T. Wang, and R. J. Samworth. A useful variant of the Davis thcorem for statisticians. Biomelrika, 102(2):315 323, 04 2014. ISSN 0006-3444. doi: 10. (o.100//booet/asv000
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):1-44, 2016.
Dengyong Zhou, John C. Platt, Sumit Basu, and Yi Mao. Learning from the wisdom of crowds by minimax entropy. In Proceedings of the 26th International Conference on Neural Information Processing Systems- Volume 2, NIPS'12, pp.
Red Hook, NY, USA, 2012. Curran Associates Tnc.
17

---

Published in Transactions on Machine Learning Research (09/2025)
A Contents: Appendix Sections
The appendix sections are organized as follows:
1. In Appendix B detail description of DS algorithm is provided. The algorithm we discussed is TE followed by NP-WMV following the discussion in the related work: Dawid-Skend model from the main paper.
2. In Appendix C.3
plotted the eigenspectram of the datasets used in the experiments. The description of the datasets is given in Table in the main paper. The idea here is to give an intuition on the benefit of clustering.
3. In Appendix C.1 provide some additional experiments. Here we synthetically generate different datascts from the meta-data available from radiology database.
4. In Appendix D we provide performance guarantee (Theorem 2 the label estimation of our two-step approach described in the main paper: clustering by Algorithm ! plus label estimation using TE followed by NP-WMV.
Appendix establishes the spectral properties of the signal matrix RR, which serves as key motivation for our analysis in the main paper. It also proves Lemma [ and Lemma
Appendix proves the main result in the paper: Thcorem
7. The proof of the Proposition is given in Appendix H !
8. We provide the proof of the Theorem in Appendix
In Appendix
we prove Proposition of the main paper.
B Detail Description of DS Algorithms: TE and NP-WMV
In this section, we provide brief description of the DS-based algorithm used in our experiments for label estimation for each task type after separating the tasks into different clusters according to their types. It consists of two steps: first, estimate the reliability vector and then algorithm for estimating task tasks. We will review the WMV algorithm first. Consider the Dawid-Skens model so that the distribution of the binary worker response matrix X E {-1,++1mxd is determined by a single reliability vector r E +1]", i.c. all tasks are of the same type. Given known reliabilitics r and locusing on single lask with worker responses r = (I1)..., the maximum likelihood decision rule for a given task j is then given by the map
weighted majority vote (WMV)
ga(x) sgn Σ Wkss
(20)
1=1
with (possibly infinite) weights
1 1 r
W4 = log
(21)
1- T;
Based on this observation, a common approach is to estimate the reliability vector r from the responses X, denoted as f, and use the Nitzan- Nitzan-Paroush docision rule [Nitzan & Paroush, 1983 to infer the labols as
T2
1 f 1- p:
0/
sgn
log
Vj e [d]. Xis
Equation corresponds to a weighted majority vote of the form Equation 20 with weights w; = log 1+
I-
Next, we review the TE algorithm for estimating reliabilities proposed in Bonald Combes 2017). which we will use in our theoretical results. The reason focus this algorithm is that it has been compared to
18

---

Published in Transactions on Machine Learning Research (09/2025)
other algorithms and shown to perform better in real datascts. Additionally, by comparing the probability of labeling error expression derived from Bonald & Combes) (2017) with the lower bounds in Gao et al. (2016), it can be seen that the algorithm is provably asymptotically optimal. We give brief description of the TE algorithm for completeness. The TE algorithm designed for estimating a reliability vector for the DS model first computes the worker-covariance matrix
Wab Σ d Xaj. Va, in].
For every worker E [mi], the most informative pair of co- co-workers arg be/xa, (Wasl denoted by (at, b:) is computed, and the magnitude of the ith worker's reliability is estimated as
M
WaysWiys W Warbe
if W azh, > 0
|A.1
(22)
121-1,1-2pl
clse
The sign of f; is estimated by letting
arg
F7 +
Σ
Wja
(E(n)
jE(n]iiii
and by setting the sign of f according to
sgn (?t- + +Eje()jjp> W3F)
i= else
sgn(ft)
sgn WH-)
This concludes our discussion of the TE algorithm.
C Additional Experiments
C.1 Synthetically Generated Radiology Data
Obtaining real-world datasets for healtheare examples mentioned in the Introduction is difficult. Due to privacy reasons, such datasets do not contain much of the information require, including ground truths and responses. Nevertheless, we considered one radiology datasot: the Japanese Socicty of Radiological Technology (JSRT) Database and its report (Shiraishi et al. (2000) to conduct a synthetic experiment. These datasets only contain information about the reliability of the doctors who looked at the data. In other words, this dataset only provides range of realistic reliabilities, but we had generate synthetic ground truths and response matrices.
C.1.1 Setup
In this subsection, we describe how we generate our synthetic datasets from the JSRT report in Shiraishi et al. (2000). The JSRT report contains the performance of 20 radiologists for identifying solitary pulmonary
Table 6: JSRT dataset. Size is in millimeters, and subtlety of 0 indicates that a nodular pattern is absent.
Subtlety
0
2
4
5
Count
93
25
29
50
38
12
Size
0.0
23.0
17.9
17.2
16.4
14.6
Mean sensitivity (accuracy) of experts
80.9
99.6
92.6
75.7
54.7
29.6
nodules in chest radiographs. Its dataset statistics summarized in Table 0
Expert performances
19

---

Published in Transactions on Machine Learning Research (09/2025)
reported for various levels of subtlety defined by the size of nodular patterns. It is clear that detecting nodular patterns becomes significantly more difficult as the size is decreased, demonstrating a multi-type phenomenon with varying levels of task difficulty. Our setup for the JSRT experiments is given as follows. There is a total of 6 types according to the mean sensitivity reported across all radiologists for different subtlety levels. These values are used as the accuracy for each type as described next.
1. For the JSTR-6 data, we use the reported means and standard deviations of sensitivities of a type k' E [6]: ow) as: for each type, we sample the probability parameter for each worker i, Plrr as a sample from the uniform distribution with support F' + ow. Then we set Tke P.4+1
2. To get an casy-hard model from this, we generate the dataset JSRT-2. Here, we combine the higher and lower 3 accuracy parameters: for the easy type, the sensitivity is estimated as having a mean of
3 = Far and standard deviation as the root mean square of the standard deviation of the first three subtlety levels. The parameters for the hard types are generated similarly from the next 3 subtlety levels.
1
Each truth value yo is drawn randomly from its class distribution defined by the sample mean of positive (presence of nodules) cases. We then sample the crowd's response following the number of tasks per type in
Table
C.1.2 Results
Table 7: Label estimation errors (%) for the JSRT experiments. "TA" and "C" after dataset names indicate whether label estimation was performed without (type-agnostic) or with clustering, respectively.
Dataset
MV
ER
TE
PGD)
JSRT-2-TA
5.65
5.65
4.74
5.06
JSRT-2-C
5.65
4.39
3.16
3.81
Gain
0.00
1.26
1.58
1.25
JSRT-6-TA
10.30
10.30
9.96
9.72
JSRT-6-C
10.30
10.02
9.84
9.76
Gain
0.00
0.28
0.12
-0.04
The performance of crowdsourcing algorithms with and without our clustering algorithm on the JSRT-6 and JSRT-2 datasets is shown in Table 7 As shown, separation consistently increases accuracy over Dawid-Skene algorithms. Because experts labeled the JSRT dataset, we observe high accuracy using the simple majority vote. However, failing to identify nodules can be consequential and even small gain in accuracy is critical.
C.2 An Example of Majority Voting Performing Better than Weighted Majority Voting
Working with the "Duck" dataset WWelinder et al 2010), we observed an interesting phenomenon: majority voting outperforms weighted majority voting when using existing algorithms for this dataset. The label estimation errors of the various algorithms considered in this paper for this dataset are presented in Table
The plain majority voting is denoted as "MV-TA" and the weighted majority voting algorithms without clustering are "ER-TA", "TE-TA" and "PGD-TA". The "Duck" dataset consists of 53 workers labeling 240 tasks. To align this datasct with the framework used in this paper, we handle missing entries similarly other datasets such as *Dog", "Temp", and "RTE". Specifically, we compute the fraction of correct labels provided by workers for each task based ground truth and available responses. We then classify the half of tasks with the most accurate worker responses as casy tasks and the rest as hard tasks. Using this classification, we estimate the empirical reliabilities of workers for each task type and generate synthetic entries for the missing worker-task pairs in the response matrix.
As discussed in the Experiment Section g this finding suggests that the DS model and its variants may not be applicable in certain cases, either because the underlying mathematical assumptions do not hold or due insufficient data to accurately estimate worker reliabilities. From Table g we observe that the -DP-based
20

---

Published in Transactions on Machine Learning Research (09/2025)
Bluebird Eigenspectrum
(b) TREC Eigenspectrum
(c) Dog Eigenspectrum
(d) Duck Eigenspectrum
(e) RTE Eigenspectrum
(f) Temp Eigenspectrum
Figure 1: Eigenspectrun of T for different datasets: (a) Bluebird, (b) TREC, (c) Dog, (d) Duck, (e) RTE, and (f) Temp. For each plot, the y-axis represents the eigenvalues, and the x-axis represents the corresponding index of each eigenvalue.
algorithm outperforms all other methods, with TE with clustering and plain majority voting coming second and third, respectively. Notably, the SDP algorithm clusters workers and tasks separately and then applies plain majority voting for label estimation. On the other hand, the main approach in the paper: TE with clustering uses weighted majority voting based the reliability estimation by the TE algorithm.
These results highlight an open question in crowdsourcing: how can we determine when majority voting oulperforms weighted majority voting? A data-driven approach to this decision could improve label aggregation in cases where standard models like DS may not apply.
Table 8: Label estimation errors for the "Duck" dataset using different algorithms. "-TA" and '-C" indicate that labels were estimated without (type-agnostic) with clustering. Algorithms compared are: unweighted majority vote (MV), ratio of eigenvectors (ER., Dalvi et al. 2013). TE (Bonald & Combes (211)) ), and Plug-in in
gradient descent (PGD, Ma et al. 2022), SDP-based algorithm in KKm et al. (SDP) and SS algorithm from (Shah & Lee (SS), respectively
MV-TA
MV-C
ER-TA
ER-C
TE-TA
TE-C
PGD-TA
PGD-C
SDP
SS
32.58
32.58
59.37
24.33
41.04
41.67
38.96
32.58
19.88
56.58
C.3 Eigenspectrum of Fask-Similarity Matrix the Datasets Used for Experiments
In the Table 3 of the main draft, have seen that clustering improves performance if used before DS-based algorithm. To get an intuition of why this is the case, we plotted the eigenspectrun of the matrix T in Figure D As we can see, all the datasets exhibit at least two eigenvalues which are larger than the rest of them which are close to zero, thus indicating that there is more than one type of task. Therefore, clustering helps to separate tasks by their reliabilities.
C.4 Synthetic Validation of the Clustering Performance
We simulate controllable synthetic setting to verify the clustering bound in Theorem
21

---

Published in Transactions on Machine Learning Research (09/2025)
Clustering error vs. reliability gap
0.40
n=30
0.35
n=40
n=50
n=
0.30
Clustering error
0.25
0.20
0.15
0.10
0.05
0.05
0.10
0.15
0.20
0.25
0.30
0.35
Reliability gap A
Figure 2: Clustering error on synthetic data versus reliability gap A.
Setup. We create d 1000 (asks (600 easy, 400 hard) and vary the number of workers E {20, 30, 40, 60). For each worker i we draw base accuracy Unif(0.6, 0.9) and set
Teji = 2g. - Th = 2 max {q: A, 0,0.11) 1,
where the reliability gap (0.05, 0.100.10... 0.200,00.00, 0.225, 0.30, 0.35) simultaneously controls the f-rmorm gap and the angle between re and rh- Responses generated via Xi, = Vj with probability (rk,a 1)/2, else -Pj, with yj lid Rademacher. We apply the clustering step of Algorithm and report the fraction of mis-clustered tasks, averaged over five independent trials.
Results. Figure 2 shows the average clustering error versus A. Error decreases (i) as the reliability gap widens and (ii) as the worker count rises.
Label Estimation for Hard-Easy Tasks
this section, we provide a performance guarantee of the overall clustering plus label estimation terms of the expected labeling error. If we denote as the label estimation our approach, then the expected labeling error is defined E Σ, 1(0, + v,) Before giving upper bound the expected labeling error by our overall algorithm, few quantitics and notations are to be introduced as follows.
After having divided the tasks into two clusters, in practice, one can simply apply a DS algorithm, such as TE, each task lype separately. However, analyzing such an algorithm difficult because the clustering step and label estimation steps are correlated due the fact that we use the same dataset for both. Therefore, is common in the literature (sce Shah al. (2021), for example), split the workers into two disjoint groups and use the responses of one group for clustering and the other group for label estimation. We present. these details next.
For the following analysis, let Na be the set of workers used for clustering, and define N₂t = [m] - Na to be the set of workers that is used for reliability estimation as well as label estimation. Let the responses of the workers in the set No be denoted by
X = (Xij (i.5) E Na. [d],
22

---

Published in Transactions on Machine Learning Research (09/2025)
and the worker responses of the set Mr be
X = (Xiz (i.j) E Nar x [d].
We cluster the tasks in X using Algorithm assignment for all task j E [d]:
(with the substitution X Xx) resulting in the following type
Tk {1 jele:: :, = =k] k (e.
We then use the TE algorithm to estimate reliabilities PR (Pks : E NG)) from the responses
(Xiy : (i.5) E NN Tk) for each k. Lastly, the labels y/ are estimated using the NP decision rule
+ Ekye Pkys X1s
TE 93
sgn
log
(23)
Now we are ready to present the theorem characterizing the accuracy of our combined clustering and label estimation algorithm. Let net and nyt be the number of workers in the sets Na and Nrs, respectively. Let Ti(Wa) and rx (Nat) be the reliability vector associated with each lask type for the set of workers N and Nr1, respectively.
Theorem Suppose (nrs, de, dn, (N))) satisfy the conditions stated in Proposition and (net, de,dh, (Ne)) satisfy the conditions from Theorem 1 Then, for the hard-easy crowdsourcing model under Assumplion 7. the labels ù eslåmaled using Equalion salisfy
Σ
1 (0) # +1))
d
de
3
Σ
exp (ann) + 2d exp (-C2na (Fa2
d
kE(c,h)
where DK.NA == (r,,(N((NH)) and D(re(Na), (N, d) is defined similarly to D(re, Thy O. d) in Equa- tion 12 with the obvious changes to account for the fact that we are only using the reduced dataset X for clustering. Here, C2 the same posilive universal constant as in the Theorem 7 the main puper.
The proof of Theorem is an immediate application of Theorem and is provided in Appendix
E Spectral Properties of the Expected Task-Similarity Matrix
In this section, we establish the spectral properties of the signal matrix n "R and give the proofs to the Lemma 1 and Lemma 2
Given the ordered response matrix X we consider in Section 3.2 where the easy and hard tasks are listed consecutively in the columns, the true response matrix with arbitrary task ordering is obtained by a column permutation of X. It is casy to see that the ordered task-similarity matrix T = n - is then related to the true task-similarity matrix with type-permutations by a similarity transform. All eigenvalues and eigen-spectrum are therefore related by the same permutations, and as long as the algorithm does not utilize an unknown prior on the ordering of these types, its analysis still pertains to the un-ordered case.
Recall the decomposition of the expected task- matrix E[T] into
||rallllaxd TT la xdy diag(y) -n diag (Ilrell@41xd 11al221xx, 12) + Ia T relan xd.
E = n diag(y)
Aral12d,xxd
R
-n-R S,
(24)
23

---

Published in Transactions on Machine Learning Research (09/2025)
where S is diagonal matrix. First, prove the above decomposition by analyzing the entries of the expected lask-similarity matrix B[T]. From the definition, T = - O. That is for all ji [d], E [d], we have, Tiita n =n= "i= Oih Oije Now, from the probabilistic crowdsourcing model considered in Section 2.1 if j E [de], then, E[O = Feilly. Similarly, j $ [de], then, E[O;yl Thsli- Now if j2 = J1, then, duda. = h[[hh] 1. But for Ji # j2, we have,
n (re, re) = 1rre11
if ji e [de), E [de], # j2
E B
n (Teith)
if j1 E [de]. & [de], else if, ji & [del.j2 [de]
n (r-, rn) = -n
i & [de), & [do]. + j2
where, the above relations for J1 + j2 is due to the fact that for a worker i, the labels provided to different. tasks are independent of each other. The above observations yield us with the decomposition of the matrix [[[]]
E.1 Proof of Lemma and Lemma 2
Spectral Properties of n Rgg
We restate Lemma 1 and Lemma here.
Restatement of Lemma 1
Define the matrix
Ro = n diag(y)
I1. Th To Id
re rh Xd diag(y) I| 12 lan xdv
and a diagonal matrix
S La diag [[lreel211 1rrlxxxl/rrall111 IIra|121xxdn
The matrix n- R, is rank-l with S 2, and its normalized eigen-gap u(n u(n-RRy) Ryy = (1 (2(n=) (2n))BBy) between its two largest eigenvalues λ1 22 can be expressed as:
v Idellre 1r + 4d.dn(r!rn) nd
Further, we have the low-rank decomposition
E
E[T] = -2 + S.
Restatement of Lemma 2
Suppose r. rh # 0. Then, the principal eigenvector of the matrix n Rgg has the following form:
sd dh 1xx1
v(n ((n))R,)) diag(y)
voddethh lds x1
where
dp w + V w22
do
and
de fellee1 113 - dn 1
2d. r'd rh
In the alternative case that r_ rb = O, we have that
+ Jon Idxxi
((n-11R diag(r)
Toe
0d,x1
24

---

Published in Transactions on Machine Learning Research (09/2025)
Proof:
[Ire [Irelldaaee xde rh Fotdixxx xde
re rn Ia xxxxx diag(u). Clearly, the n BRy 11ral Ia xd,
Recall, n- Ry is defined as, n- - diag(()) is a rank-l matrix with S 2. Specifically,
1, when ra and Th are collincar
8 =
2 else
Next, we calculate the eigenspoetram of n Ry.. First consider the case when r. r.rr ra # 0. Case 1: When re Th #0:
Consider generic vector of the form [iag(y)(s (xxxd, 1ixd,] 1 for some as the ratio of the magnitude
between the entries of the vector corresponding to different types of tasks. A normalization of q serves as candidate eigenvector for the matrix n Ry. where
d x1
g diag(y)
Vd. +ds
lalla
1d,
+d
The cigen-pair equation for the candidate eigenvector above is calculated to be:
[ (3de Irell + derrrn) Ldax1
1
(3der ra + dn dnllrall) q. L
R.g diag(y)
(25)
a
(3der + dh [2)] 1ds x1
n
Now 8 is the ratio between the quantity 1 (sdellra 11 + dar? rb) and 1. (sderr rn + da dallral13 can write:
- (dder + da 11a11)))) = Irell dur.
(26)
The solutions to this quadratic equation given by
de dellrelB 1 du 1r + / [dellrel1 dn 1allrrl13 12:" (r.
(27)
2d.r?
Let us call the solution 4.1r. -ddlll dd.1rr.13 di +2d.ds (4 The eigenvalues n (3der dallral 11) of n RR, corresponding to solutions and respectively are
and the other solution as 82-
2d.r!
(n (Ry)) = dellrell3 daliral1 +
dd Ire |r [B]
2n
and
A del dellrel13 dallral1 V /deelree Ill l12
de ra 112) + 4d di dr
(28)
2n
where >1 (n Ry) 2 d2(n - Ryy) By Assumption 1 we have ||rella > O. Hence, for de 2 and dn 2 1, we can
write, >1 ( > 0 and >2 (n'RR,,) 2 0. When Te and ra are co-linear, Ag(n -1 RRy) = 0.
Case 2: when r. Th = 0
When the reliability vectors are orthogonal, we can write
Ry =n - Ire lidgggia I diag(yr:a) @
l1d) xd, diag(Ud.+11d))
(29)
where Vird, and tid are the ground truth vectors corresponding type easy tasks and type hard tasks respectively and @ is the notation for direct. sum. From the expression Equation 29 it clear that rank(n -lR,) R2y) = 2 when ||rall2 * with the following eigenvalues:
An - Rgy)
max d = n ddlllrell 2 A2(n (inm-RRp Rgy) = n min da d = n ..-'da (l 12. kE(e,h)
kEfe.h)
25

---

Published in Transactions on Machine Learning Research (09/2025)
with (2 An = for all j j= ......d.
Also, the eigenvectors of n nn-11 Ry corresponding to the eigenvalues n n= delllbell and n -n-1d Ir are respectively
[
vdc Idxx 0dax1 x1
x1 vdn ddxxt x1
diag(y)
and diag(y)
F Proof of Theorem
1 Perfect Clustering
This section gives the complete proof of Theorem the main paper. We restate the theorem here: Restatement of Theorem
Under Assumption if the number of lasks d satisfies
G
d 2 D(res
then Algorithm 1
returns lask type estimates such that
P(r = 0) 1 2dl exp (e d)),
where the problem-dependent quantity D Thi a, characterizing the error exponent and the requirement d is defined as follows:
(1-a) v(n R. 11111111111 v=*+1
when, re rh # 0, when, r.rn
a,,
(1-a)' " v(n Roy
and C1 and C2 are universal constants, independent of the problem parameters.
As discussed in the proof sketch of the theorem, the first step is to show that the principal cigenvector o(n-RR, Ryy of the signal matrix n n--R, Ry reveals the type information for each task. This is discussed in detail in Lemma. T and Lemma 2 and proved in Appendix E Building upon the Lemma 2 the rest of the proof of Theorem is given in this section as enlisted below.
1. First, we prove Lemma in Subsection
2. Then we show that the principal eigenvector 0 of the task-similarity matrix T is small perturbation of m(n-1Ry) in the los norm sense. This is stated in Lemma and proved in the following Subsection F.2
3. Next, we relate the event of perfect clustering, that is {n 0) with a sufficient condition on the concentration with respect to v(n- (see Proposition in Subsection F.3
4. Finally, we prove that the condition described in the Proposition 3 is satisfied with high probability. See Subsection F.4 for this final step.
F.1 Proof of Lemma 3: Concentration of the Noise Matrix N
Restatement of Lemma 3
For any and any positive values of n and d, the task-similarity matrix T concentrates around its expectation follows:
ne²
PP (1 2 c) 2d
2df exp
2dF
Proof:
26

---

Published in Transactions on Machine Learning Research (09/2025)
The proof of the Lemma 3
stating the concentration of N is given
P ( 2 e) =P P
max iEld
[2 - B 2e
Σ [i - B[ 2
==1
(a)
1=1
[iy - B[ui|1 )
max /E|d
TTy - E 2
P
1=1
(6)
i=1 j=1
1
n2
Σ
(K 1[X,X113))
2
71
2
2d exp
-d2
2d
In (a) and (b) we use the union bound, and (c) we employ Hoeffiding's incquality for the independent bounded random variables X1s, Xig E [=1}.
F.2 norm Concentration of the Principal Eigenvector We prove the Lemma here.
Restatement of Lemma 4 If vnn- satisfies
Ca(1-a)'e ev(n -R - 0, then, for every 0 < E <
C1(1 - av)=aa>v(m -1 -' R)d - 1, the event
min
1100 v(n unn--Ryyll Ry
8E 0E(-1,+1)
C4a
(1 - a1-a) p Rdy (e+1)
à² occurs with probability at most 2 exp (-n where Cs and C4 universal positive constants.
Proof:
We use result from the paper Fan et al. (018)) that turns out be more useful than the standard Devis-Kahal perturbation result (Yu et al. 2014) for loe norm perturbation bounds on the eigenvectors of a perturbed matrix in certain scenarios. In our case, recall that the task-similarity matrix T has the following
decomposition:
n S
It turns out that the low-rank structure of n n RR and the fact that S is diagonal matrix with matrix inf-norm d,n den-=1[[re ||r_|l makes the above decomposition of T a suitable setting for getting a useful loo norm perturbation bound on the principal eigenvector of T treating n Ry as the signal matrix. From the Lemma we have S = diag (IIr= 1xx,, || 1xx,, 17) + Ia- Here we are interested in the distance between 0 which is the principal eigenvector of and v(n -1 (R,) induced by the infinity norm.
Let 12 be the rank-1 approximation of the signal matrix -' Rg. First, we state the result from Fan 2018) on too norm perturbation that use in paper. Before stating the result from Fan et al. et al.
20188 we need to define a quantity called the coherence of the signal matrix n - and the coherence of its best rank-1 approximation - R,,1- Writing the modal matrix of n n- R, which is of size d E as V so that its columns correspond to the unit-norm eigenvectors of n -2
"Ry, the coherence M of matrix n n-1R, Ry is defined as
M max V22
(30)
JEld
jg
9=1
Similarly the coherence M of the matrix n Ry,1 1 is defined as
M = dax ( ?.
(31)
sE(d]
27

---

Published in Transactions on Machine Learning Research (09/2025)
We utilize the following result by Fan et al. 2018 cf. Theorem 3
Lemma 5 Let C1 and C2 be two universal constants. Consider a d-dimensional rank-2 symmetric matrir A and its eigen-decomposiiionn
2 A = Σ (A))))) 9=1
Let m E (1, We call Am as the best vunk-rn approcimation of A. Clearly for our construclion, A2 A. Define I' as 7mm ||A Amll Clearly, O. Denote M (1 and A2(A) as the coherence of the matric Am; the largest and second largest eigenvalue of A. Let perturbation of A be and the perturbation À is also symmetric with the same dimension as A. Then, for each m E {1,2}, if (m) satisfies:
1mm (m)(A)] - 7' 2
All
(32)
and if
(A){({))))) > 1 |
(33)
a5m
with notation \a(A)= 0, then,
min [(1 - Our (A)lloo S SC (M Alloo + m MM(m)) ]1 All2 0E(-1,+1)
(1mml ~mm)-mm)V -m)vv
mingsm (Ag(A) (g+1(()))))))))))))))))))(()))
where, vi (A) denotes the principal eigenvector of the matria Å.
F.2.1 Characterizing the Suitable Based on the Angle between Ta and
Before applying the above Lemma 5 first characterize which from the set {1, 2} is more suitable in this setting to apply the lemma based on the angle between the vectors тe and Th. Let us call the angle between Te and ra as Ç. The idea is that if |in is sulficiently small, we use m = 1, and if it is sufficiently large, we use m 2.
To understand this, we study the error of the best rank-1 approximation of n defined as: ?1 == ||m ||m-'R n Ry and its implication in Equation 32 for the case of m 1 with the signal matrix A and the perturbed matrix À being replaced by n- n-1 R, and T. Let denote 22(n Ry) as the eigenvector corresponding to the eigenvalue (n Rg))
(Ry) of -- Ry. Then, have
R2))u((n A2(n -1 [1)2 (R)))))22 (eionn-RRn)) RTyTT 11 = 122(n (22(n-1Ry)) max D2y (n Rgy jeld
Σ 122 -1 Ryy)
where 02 the jth element of the vector u2(n RRy) Let us first consider the case when ((nn)1RR,)) A 0. We know from Appendix E that the magnitude of the elements vector 02 RRy) from the set
[sg]
with
Mal Vde
corresponding to easy tasks and Vo.s3to
corresponding to hard
Vdo Vdcoā+dn tasks where
de Ir.l
11 ddlllralB du dr (d.
82
2d.rTrh
2The theorem
Fan
2018 for matrix rank where take any finite value, simplified it our purpose
when
28

---

Published in Transactions on Machine Learning Research (09/2025)
Under our Assumption in the main draft, we have dellrel13 dn I1 18 2 0. Hence, we have 0 1 [s2| S 1. Thus, we can write,
dz|32|
dA
21 = (22(n=A
+
v dd dp
V Vo.3 + db
Vd. + dn
dels2] + dp.
= -12 -By)
de (82)² + dn
du $2 +1
112(m=1 Ryy)
dh
de On
(s2 )² +
on eel++ # |s//++1
Now a bit of calculus shows that the quantity
as function of [22 with S |s2l S achieves a its
maxima at value
which can be further upper-bounded by 1.25 de de
dg dv 2 1. Thus, we
2 1+ de 4n
write:
de '1 S 1.25
A2(n (R))l
dn
Next, we would characterize the quantity (n [R,))
7i which should be sufficiently large we put m
in the application of Lemma in light of Equation 32 Recall from Appendix E we can write:
A (Ry) = de del 12 da 1 + V de |r
12
dn ||r |13] + 4d.dh (r' rn)²
20.
2n
de 1lr 12 du 1r V dde
||a
12
d, 11 123 + 4d, (r2 r2)
be(n-1ab)
2n
de Ir 12 1r V [del|re + da
11 11) 4d (Ire (rTrw))
2 0.
2n
Then, we can write:
(Ire - (r?rr)²) = 4d IIre cos (?) 4d.da 1 (sin c)?
Clearly, the quantity (1in [Ry) - can be lower-bounded as:
[A1 RRy) - 712 2 An 'Ry) 1.25 de Xu(n (R,)
dn
= 1.25 de
v Idellrel1 da - 4d. 1ld (3 ç)2 +1) dn
de 1.25
-1)
(de (dellrell3 + di |I 113)
2n
dn
2n
Now since,
[del1re13 + di d 4d 12 = (dellrell dn ||r 121
0. we have,
[dellrell + 1r 2 4d.dalre 1 Hence, [del|ral13 + dnl1r=111] 4d d, 1 (a 2
[del|rell3 + da ||r (1 (sin () [dellrellž du ||
cos cos C² giving us the following:
de + 1 cos çl 1.25
de 1.25
dn ) (dellrel13 + dh (ral111))))
[n [Ry)) m 2
dn
2n (dellre 113 + dh l1rl113)
(1 + cos ()) - 11.5 de
(1 - cos cos
dp
2n
Clearly, if cos çl 2 4d
3d, we have, (1 + |os - 1.25 + (1 - cos (l)
2 1
ad
2 $.- A sufficient
5d.
condition of cos 1- 5d.
4da is (sin()² < 25d.
4da, So have arrived at the following fact: 4d,
fact: When the angle between and ra satisfy (sin 2)2 <
25d, we can write:
A1(n-'RR - m 2 (del 12 + drllral1))
10n
29

---

Published in Transactions on Machine Learning Research (09/2025)
In the alternative case of ((sin <)² / in Lemma the second largest cigenvalue of R, as the approximation error for a rank-2 approximation in this case is O. Next, lower-bound the second largest eigenvalue of n nRy as follows:
4dg.), the quantity of interest in light of the condition given in Equation 32
de dellrelli du Ira Idellr rell + dn |r 4d. dn Ir. |rx (sin Ç)²
A2(n Rτy
4d,d I Pm (sin C)²
de [ + da 1 + / dd 1rel 1r 4d 1rellllla (sin c)²
(d)
2n
4d,ch
[re 1r (sin ę)2
(indel/rell 112 d Ir 112)
dr 1r [sin ç)2
(e)
where in
(d),
we
multiply the numerator and the denominator
by
dellrelle + dh |1 12 + v [dellrel13 + dh dr/l1111111 4d 11r (3 ç)2
assuming
sin Cl + 0.
(e), we use that de 2 dn and ||relle 2 |1r/122-
Hence, for the case of (sin c)² 25d,
4dz we have,
2el ||
A2(n (a(n-RRn) Ryy
25d
Hence, the idea is to use m the Lemin when (sin <)² S
otherwise use m = 25d
4d,
F.2.2 Characterizing the Upper and Lower Bound on the Coherence Terms M and M
Before applying the Lemma our case, we want give an upper bound on the coherence parameter M and M defined in Equation 30 and Equation 31 that will be used in the proof of this section. Recall the definition of M and M1 as:
d max L
M
Vi
jE(d
g
and
M = d ( RR, 1,)
sE(d]
From the Lemma 2 of the main draft, the elements of ((n-1Ry)) corresponding to easy and hard tasks are Vd. and +d." respectively. Similarly, for non-collinear тe and Th, the two non-zero eigenvectors
for the signal matrix the corresponding entrics of the sccond cigenvector of n n- Ry would be
#2
and
Here s and $2 takes the following values:
del1relle du Ira
[dellral de |ral (rF
2d Th
From the expressions obtained above, write the coherence terms defined in Equation and and Equation 31
as
d
d
2²
1 da + dn des² dn + de dn
22
max
max
iEid
2
da - dn
1=1
x²
1
M dmax
d_s² + dp d_s² dh
30

---

Published in Transactions on Machine Learning Research (09/2025)
Hence, lower bound the coherence terms as:
s²
1
$3
= )
M 2
de des²
+ dn des² + dn
+ de
+ db
2
+ dp
de dn
d + dr
M 2 de d + dp
+ dn
d,s² + dz. =1
Moreover, we can upper bound the coherence terms as:
1 ds +
ds + d des2 dh
2² +1
$2 +1
)
= 1
M
2
des² dp
ass
+
a)
as + (1 a)
1 l
(f)
M < do + d
82 +1
1
d² + di (g)
ass +
a)
1-a
where in (/) and (g), use Assumption in the main draft, specifically the assumption de ad and dn = a)d and a 2 0.5.
F.2.3 When (sin <)² > 4da de
In this case, we apply Lemma with m = 2. We substitute the matrix with n a- RR and the perturbation
Á with + N. The conditions to satisfy according to Equations 32 and 33 are:
X2(n-1R,)) 2 N
and
min(A1(n Ryy) >2 - R,y) 22 RRy) > ||S + Nil2.
Recall from the discussion above, M 2 1 and M - Also for symmetric matrix B, |B]0 2 || Hence, letting Ö₂ = max/1, C,23} the sufficient condition to satisfy Equations 32 and 33 can stated as
C
min(A1 (Ra)) - A2(n (iaa-RR,, A2(nn -1 RB)} 2 (1 a1
| + N|
or equivalently
S + No < a1=
min min (n Ae(n 1
C2
Define the event E as:
E 1 < (1 a1
( (n,) Ryy) A2 Ryy), >e(n >eenn- -1
C3
Clearly, on the event EN, the conditions given by Equations and 33 are satisfied by the use of the triangle inequality with the fact that ||S')oo n -1 1|r < for the diagonal matrix S.
Now conditioning on the event Ex can use Lemma 88:
21 2 N
2 v M S NN12
min [I(n (o(n-1Ry)) 00 Eē 0
(A2(n-1 R2,) min (n 12(n-11 1
C,1|S + ||10c
(1 a)² min (n RRy) A2 - X2) - 1Ry Vd
(6)
C. 11 +1]
(34)
(1 a)²² min f (n (n- Rly) A2 Rly >2 -
31

---

Published in Transactions on Machine Learning Research (09/2025)
In (h), we let C2 C2(2 + 28) and the fact that s M S a-a in (i). we use ||5|| I 1.
We interested in the event EN n (1 S { for some such that,
-zoa" min (11 (n R,y)
A2(n= Ja(n A2(n ( - 1. On the event Ex n al I ct. the following is satisfied using Equation
34
c+1
min ||o(n - Ryy) ~0 C. 0E(-1,+1)
(35)
R,y) - d2(n (e(n--R,n A2), A2(n-1 Ry)]vd (1 - a}² min (1 (n-1nRRRR))
It remains to show that the event EN 21 I e} for some e in the range < <
(1-a)
min An (nn)))
Cs
Je(n-)Ry) ( 1 occurs with high probability:
-ne?
P (EN 11 5
+0)= =
PI $ 2
2d exp
2d
(3)
where in (j) we use the fact that the event in the main draft.
[|| Se} a subset of the event EN and (k), we use Lemma
F.2.4 When (sin c)² <
4d d.
In this case, we apply Lemma 5 with m = 1. The steps are similar to the other case with a few differences.
The conditions to satisfy according to Equations 32 and 33
are:
An 11 Rgg) m 2 ČI(M') + N
and
(n Ryy - X2(nn1R, Ryy) > ||S + 2112.
Recall from the bounds on the coherence terms, M > and M S -
Hence, letting C3 = max (1,
the sufficient condition satisfy Equations 32 and 33 can be stated as
C3 (1 a)
in >2(n R,) Ry) 71 2
|S Nl
or cquivalently
(1 a1)
|S 1100 1
min (1 (n 'Ry) >2(n (R(n- An 7.
C3
Define the event Ey
BR |
a1-a)² C3
min (n- -2( Ryy. Ai (n - -1
Clearly, on the event Ex the conditions given by Equations 32 and 33 are satisfied by the use of the triangle inequality with the fact that ||S'] = - n =1 < 1 for the diagonal matrix S.
Now conditioning on the event E we can use the Lemma as:
( + N11
VM + N/12
0c (-(-1,+1) |lonn-1 Ry) 00 SC,
min
+ (11(n-1 ndvd (A1(n-1R,) - >e(n Rl - Vd
CIS1S + No
(1 a)² min ()i (011nn11p))) >2(n > \1 (m11) niva
C. || +1]
(36)
(1 a) min min((i (n 22 - -1 (m1,) Vilva
(m)
32

---

Published in Transactions on Machine Learning Research (09/2025)
In (1) use the fact that M 1 I-a+ in (m), use |||| I 1.
We interested in the event Fi n [o S {e for some such that, <<s
- min (A1 (ny
(n Ry), A1 (n (Ry) - - 1. On the event E n ~l I <c), the following is satisfied using Equation
36
e+1 - 0601lo S C2 (1-a) a) min Ryy)
min
(37)
0E(-1,+1)
22(n An (Ry) - 71 1lV
It remains to show that the event E n [I I }} for some e in the range < <E (l-a²²
min (n-
Cs
x2(n-1Ry)) A1 (n -713 occurs with high probability:
-nE²
(ENN n (IN 5 = P( $092) 2d exp
2dl2
(o)
where in (n) we use the fact that the event <|| & c) is a subset of the event E and in (o), we use the lemma 3 the main draft.
F.2.5 Combining the Two Regimes: Completing the Proof of Lemma 4
Recall the following fact proved before in this section:
fact: When the angle between Te and ra satisfy (sin <)² <
4da, 25d.
we can write:
Pn (n)nn m 2 (de IIve 12 dn (())))
R2y)
10n
and for the case of (sin (sinc)²
>
4d, 25d.
we have,
2df ||r 12
A2(n R.y)
25d m
We use the above fact to combine the two regimes to complete the proof of Lemma 4 of the main draft. When
(sin 2)2 >
4dg we can write:
25d.
Min(AAnn-1R, Ryy) - >2(n (oy) A2n (2(nn11nR)) R,y) 2 (n - A2(n (Ry)) 2df | 12 Rgy)
25d n
ddmin(d (A( (a(n))B,))) 2(1 - 11) }.
25am
Now recall from Lemma of the main draft,
RR)) - / ld 1rall dellral13 (r?
[d Ilrllell 112 + 11
S d.
n
Also, from the Assumption of of the main draft, we have, ||rx 2 2 2pm. From the above two observations, we can write, when (sin ()2 >
4da
25d
>2(n RRy)] 2 Ōs(1 a) (An Ryy) >2
(n RR, >e(n (en
where, we let Õ5 = 23.
4
Now for the alternative case of (sin 5)2
4dg
write,
25d.
min(Ai (n -R,) >a(1 X2( BBy), A1 (n -Rn) - } 2 min(Ai(n (n--)) - >2(n >o(n= de dellrel1 + dn ||r
10m
33

---

Published in Transactions on Machine Learning Research (09/2025)
Now as shown above, we have, RR) X2 2 de d.Ilral1++d, ralll giving us: for the case of (sin Q)2 < 4dg
254.
1
min - >2(n "Ry), (n - - 2 10
(A1 (A1 (n Ryy >2(n X2(n=-Ryy)) RRy))
Hence, we can combine the two cases in the following statement.
Let C = min
min (Cs, to If v(n Ry, satislies:
(6(1-a)
v(n
Czax
then, for every such that 0 <
Coll-a) Oga
vnn (onnn L, we have the following:
Č4a
c+1
/-ne?
min 0E(-1,+1)
[l((n ) 001l00 2
S 2d exp
cxp
2d2 )
Co(1-a)<pv(6 (alu0-1gddd ( RRydvdd
where we used the following notation from the main draft: v(n R2y = d (~1(1inn -Rnn) -Ry) ->2(n - R2,))
Letting
C3
Cu and C4
we arrive at the statement in Lemma Caa
Ca,
Co
F.3 Sufficient Condition for Perfect Clustering
Here, we relate the event of perfect clustering with the concentration of the principal cigenvector with respect to RRy).
Proposition 3 Under the stated assumptions, Algorithm 1 achieves perfect clustering, that is = 0 when the following event occurs
[|nnn (on)) - 00.loc min {me(n- mn(n [Rn)
1
E
min 00(-1.+1)
The proof of the above proposition is given in Appendix 663
F.4 Proof of the Theorem T Perfect Clustering
Now we complete the proof of the clustering Theorem
From Proposition 3 we know that,
1
Pm==0) PP min || (R)) 00 < min {m.(n" (Ry) 6E(-11+1)
Ry), my R2)
Now we show that the right hand side of the above equation is close to 1 for large values of n using lemma 4 We also derive the corresponding necessary conditions on the problem parameters n and d.
One requirement of Lemma is that Ca(1-a)') v(n Ryyd (o-n---Bydd 1 > 0. This leads to the following requirement
d:
a
d d> Cs(1 a) a) R,y)
(38)
Under Equation 38 we have from Lemma for every < <E< Call-a)' v(n RRy) -1,
a(c+1)
2
min 1000 v(n"" -1 -R,))loo 2 C4 (1 -1-oa a) Ry)ddd
< 28 exp
(ct 2d
EE +)
Next, we choose suitable e with <E< Call-a)te -2 such that
a
alE 11
C. [1 -1-a) pi-nn)-p(n--Rppp
min {mo(n -lan--RRn mmn Ryy) }
34

---

Published in Transactions on Machine Learning Research (09/2025)
The following choice of satisfies the above requirement
1
(1 a v(n -1 (dy)din(( RBy Ryyd ma(n" mn(n-'Ryydd 'Ry)d 1)
max 14
a
when we impose:
4 max { (Cs, Ca,
(39)
(1 - (1 p min
(,, Rt R2)d1/211)
Notice that the requirement on d in Equation 39 is stronger than the requirement in Equation 38 Putting it together, we get, when d satisfies Equation 39 the perfect clustering is guaranteed as
1
(n==0) = 0) 2 TP
min (E(-11-1)
||u(n - Ry) 00|100 < min (me(n-'Rig mn mn Ryl)
(1-a)* 1 Rgy) min {me (n - Ry (n (n 4 max (C3, 1Ja
2 11-24 2d exp
When r.r rh- = 0, from the analysis of Appendix E.1
we have,
dn
(Me (ue(n (ne Ryy (8p)-Ha (n( = dj
Me(n-RRB = Me(n" (Ry) =m(n" -1 RRy)
d
d de
mn(n-1Bi = (((mn-RBy) un un (By) = d (Me(n -Rn) (n = de
de
Now, da (1 add and de ad with 0 < min me press the absolute margins Me(n-RR, and my (n Rgy) as a function of the ratio s = pe(n Roy between the easy and hard maguitudes Me We u1 (n- -Ry) so that
< 1. Hence for this case, we have my (nnnnnnn- /2,)d 2 11-a. a. On the other hand when, re rh * 0, it is convenient to ex-
Ry)
dn (Me(n 1lan-1Rp Ryy - pa(n-11
dp
|8| -
m = (een111 (((=21R)) Ryy)
(40)
d
d
v Vdss + dp
de (Ra))) -Ma(n RRy)) (a,nn)",,)))
de
|||| -
mn(n R,y) =n(n
Ryy plnn"Byy)
mn(n (R,))
d (Mo(n Ryy
(41)
d Vinis + dr
Hence, we can lower bound the term min (n R2y 1222 ( R/ydd 11 as follows:
min(ma(n -R, mn(n RR, (2) = min dp ||s| 11 1/2 de
|||| 1//2
Vd.s² + dr
Vd dn
al|ss -ل Vasz + +( Vas + (I a) 1
|s 1
-min
min fa 1 a
82 +1
(p)
where in (p), we use the fact that min fa, a} min (m.(n-1 Ry)d mn Ryy 12/2 1 ,1,, we write the sufficient. number of tasks required for perfect
||--||| < 1. From the above bounds on M and
clustering
C1
((rresh,,add)
and the probability guarantee of perfect clustering as
F(n 0) 2d exp (- C2nDD(rre Th, F,, a, a,d),
where the problem-dependent quantity D(re, Thy a, d) characterizing the error exponent and the requirement on d is given by
(1-a)'p vin - ( a /32+1 1 (1-a)'e v R,y)
when, r.T 0,
Drre:Th, a,
2
when, r. rh 0,
with the positive universal constants C₁ 4max(Cs, C2, 1} and C2 [mmaX Ca.J+
35

---

Published in Transactions on Machine Learning Research (09/2025)
F.5 Proof of Corollary 1
Restatement of Corollary
If there exist some universal constant with 0 11
r
2
| 11
2 3
then, under Assumption 1 Algorithm achieves clustering error with probability at least 1 - 6 when
n1 2 Cça² log (24)
(1 a) a2 p2
where Cg Cs
Proof:
We are assuming that there exist positive 3 such that B S 1, the following is true
||rell - ||rx|1 2 Sn.
We would like to lower-bound the following term:
(1-0)'p v(n 1 11,) [1)1l=--11) 2
when, r r. 0, when, r rh = 0.
D(re: Th: D(re:Th; at d)= =
v 2 [1a))2 v(nn - R,y)
a
Let us first lower-bound v(n RRy) We have the following:
v(n-1Ry) Ry) An R.y) Ry
(dellre I 112 nd
dr (1 2 + (r.
nd
dellrel? dn.1rr111
nd
dellre
del 1| + dollral13 da 1r
nd
de (l - (
nd
(p)
2 ag
where in (p), used the assumptions de dn and ||ralla 2 ||ra Next, let lower-bound the term Recall from the Lemma 2 of the main draft, we have:
(1s|-19²
6241
uu2 +
dn de
8 8 -
with
w dellz Tellrel1 12- - dh 1r
2d.r. Tb
36

---

Published in Transactions on Machine Learning Research (09/2025)
Using simple calculus, we can show that, (sl--1)* s*41
min 23 20
(Iwl
da-da 2dhe
2
The rest is to lower-bound
(ww) 2mddx)
We can write:
de dh
dell dellrel1 d, 1r (de dn)lren rm
Wwl
2d
2ele rul
del dellrell?
dh |rlel dl (Ireell 11ml11)) (de dr, dr)lra r rhl
2d re rn
dp (1l (1 112
|| (12) 2d re rh
(g)
dg.3
3(1 (x)
2d
2a
where in (4) we use ||rell2 2 Irall2 and (c), we used that Ir_rh rh S n. Thus, we can lower-bound (el-11)
5 as:
(|s)
1)
1
8 a)²
min
22 +1
25'
24. 5a
Giving us:
(1- p2
D(r Thi a,
-5
From Theorem 1
the requirement on n for an event of perfect clustering with probability 2 5 bocomes:
2d log
Y1 2
C2 Drres a,,
Hence, we can write that, Algorithm achieves clustering error r = 0 with probability at least when
n 2 Caa log (2)
(1 a) p2
where Cg
160 C2
F.6
Remaining Part of Proofs for Theorem
Here we characterize the relation between the Too norm concentration of the eigenvectors with the event of perfect clustering which leads to a proof of the Proposition 3
F.6.1
Relating the Event of Misclustering to Eigenvector Concentration
Before stating the sulficient condition for the perfect clustering, state a more general result that provides the sufficient conditions for a clustering error S -t for some t E [0, 1] in the following proposition.
Proposition Let be the sign that resolves the eigenvector ambiguity
0 = arg min (00(n-RRR,)) 06
De 0-(-1,+1)
Fir any non-negative Algoritio 7 returns cluster membership with 1, < 1 1-t the following event on the random vector 8 and the rondom voriable fa:
1(E,,) 2t
(42)
d
where,
Faj R,y) -00y1 Iu(n -1 Ryy / < (min(me(nn -Ry)) mm(n--m(nppppp RRy))
37

---

Published in Transactions on Machine Learning Research (09/2025)
Proof 1 Assume the event defined in Equation 42 is true for fixed t such that 0 $ 1. Under this event we show that there cxists permulalion from (e, to {e, hi such that ll First, consider the case of pe(nn Ry) 2 (a(n-BRg) Our condidate permutation for this case is a = {e + e; + h]. We claim that when event Ea, is true, the tosk j is clustered into group 1 if k, = and into group otherwise. Under this claim, is easy to see that on the event Equation 42 at least l. fruction of tasks are correctly clustered, that is, 13 S 1-t. t. We are left to prove the claim now. Consider the case K; = e for a task j. By definition of the absolute margins me(n" (ae(n--P,) RRy) and mn mn(n (n Byy) we have that min(me(n RRy) mm)mmmnn" Ryy) S ( (R)) μ. Suppose Ev, is true Then,
10,l 1 A -nu,(n (((nn'1p0 Ry)] u(n (R)) + u(n - Rτy) - ā + 108,1 - |0,(n RRy)
2 min(me (R)), mn(n" -1 Ry)} - 10,(n (n - -001 + lu(n" Rgy) - [i]
min(mel mn Ryy} } - min(me(n RRy; mn(n" [Rg)) 0,
where (r) is due to event Eo.g- This implies |βy] > a. This proves that task j is correctly clustered as k5 and I((s)) = By the similar arguments for kj h, we obtain that T(k,) h in the same event. The flow is almost identical for the case of We(n-RR,) 2
Lastly, consider the case of Ue (n Ryy) Ry) < (n Ma(n-RR, but, it is given below for completeness. Our condidate permatation for this cose is π = {e + We claim that when event Fa.j is true, the lask j is clustered inlo group 1 if kig = h and into
h; h + e)- group 2 otherwise. Under this claim, it is easy to see that under event Equation 42/ at least t fraction of tasks are correctly clustered, that is, 17 S 1-t. We are left to prove the claim now. Consider the case ky = e for a task j. By definition of the absolute margins me(n-1Ry and mn(n (R)) we have that min min(me(nnTha (oo)) mn(n" (n-11n) (R)) plnn R,y) [n5(n=1
Suppose Ev. is true. Then,
P |0 n(n - R₂y) 10,(n Ry)] + ft p(n 1 10--111 R,y) + 108,1 - (0,(n RRy)
2 min { (m ( Ryy, mn -1 R2y} - 10, 1 Rgy) - 08y1 + ((((m--BB)) - fil
min mmin(m,. (m (R)) mn Ry)} } min (ny mn(n- (111) O,
where (s) is due to the event Es.j. This implies 10yl < p.. This proves that task is correctly clustered 7 (kz) e. Repeuling the same argument for kg = h, we oblain that x (kk)) = h in the same event.
F.6.2
Concentration of the Threshold f
Recall, the Algorithm uses the following threshold to cluster the entries of [0]
A
0
Fact: For any vectors v, é of dimension the mean absolute error |a - A between the average of magnitudes / = d Ef and that of 0 satisfies
A 5 1/2
min ||0 08ll2 s min |/e 0blloc.
(43)
0E(
oe
1,+
Proof 2
1 d
d
A P- 1
(100g) - (10l)
7
Σ - (1551-l051)-
j=1
j=1
Taking the absolute value and using the triangle inequality, followed by the root mean square arithmetic mean inequality,
l als S E10 00 -uy1
5 -lle S min eE(-1,+1)
||0 00|| bo
38

---

Published in Transactions on Machine Learning Research (09/2025)
Using the above fact, can relate the concentration of á with respect to m((-1R) Z== (1)(n= Ry) as
1 E0; 00 Ry)1 1 = v(n-t R2)R i - pnnnnnnnnn (Rl)=1RRy)=- -
min 055 -
(o(n-RRy) 00/loo- (44)
F.6.3 Proof of Proposition 3 Relating the Event of Perfect Clustering with Eigenvector Concentration
The Proposition an immediate implication of Proposition and Equation
On the event E using Equation 44 the following satisfied [p - 14| < 1 min {m (n -o--RR RR) mm (Ry) Hence, the event E is satisfied for all E [n]. Hence is achieved from Proposition
G Proof of Proposition 1 Error Rate Lower Bound of Type-Agnostic Weighted Majority Vote
We restate the proposition for easy reference:
Restatement of Proposition
Let the WMV estimate using a single weight vector w across all task j is defined as:
WM (w) = sgn Σ WxXKs 0
Vjj [d].
We consider weight vectors belonging to the set wy S |wyl S Wa for all workers i with wy and w. two positive constants such that 0 wy S wa co. Under this construction, for any y E {-1, +1]3, the average labeling error rate for the type-agnostic WMV algorithm can be lower bounded as
lim inf log min E n-000
Σ MV (w) + vi)
n
lim sup max min pn rk),
n- w
for any ground-truth vector +1] where the error exponent Pn rk) is given by
1
log tw: 1 1 Thi
2 + -wc 1 Thi
(w(,TTk) = inf 120
Proof:
This proof technique uses large deviation analysis a sum of independent random variables (Srikant & Ying 2013). Let us first fix a lask index j and let the lype of that task be k, = k for some E (e, For each worker and task j, let Gı be a random variable that takes the value +1 if worker correctly labels task j and is -1 otherwise. other words, G = X; which +1 with probability (1+x). Let the probability measure corresponding to type be denoted by P& and we can write the probability of mislabeling task j as:
P& (1)(w) 1i) 2 Pk yj Σ
w. X,y <0
Pk
Σ G. < <0)
where the inequality follows from the observation that when E Wi 0, assign the label as +1. MV
where we drop the superscript 'WMV" in this section from 2/ WWMVV (w). We notice that Ei. w,Gi only
take finitely many values and Σn w;Gig & E. lwyl- Consider the set $ {8:8= E, gi {-w,, w:))
39

---

Published in Transactions on Machine Learning Research (09/2025)
For any positive value of Sk with 0 < Ss - Σ, wtl
Pp
Σ
my
Gij
<0 0
Pk
Wy Gij 0 0
2
Σ
Pk Σ
GgGGis =
(45)
Σ SE8:0<<<S.
Σ
II
Po (- = gi)
(46)
E, 9. 14.00)
holds by the independence the responses across workers, Now, we use change of measure of the concernod random variable. Define random variable corresponding each as Gij given by the following mass distribution for some t, (k) 2 0
(1 + Tke) (k)jw:
2aa(M) (Gis =) = (1 + rhit tr (k))s;; + (1
(1 - Tkx) T (k)ar,
(k)
(1 + rki
to (k)ar (1 Tke Tet (A)aw
Then we can express Equation 46
n
Σ
Σ
II
P (-w; = 9:)
Σ, 9. ( Fm1
I. ((1 (ki)e (n)ass + (1 rkx)e (A)ue))
2 (k)(
0<~ w;Gis < Sk
(k)S
where to obtain the last step above, we have multiplied and divided each term in the product by (t)g (Itrude fate/ +(1 aalt and used the bound E I Sy. Recall the expression
Pn (w) = inf
Σ log 120
2 ((1
rkile
(47)
Define t,, (A:) = (k) to be minimizing argument of E, log ( ((1 + r (a(k)m + (1 - (k))e in
the domain (n.kk) 2 O. Now, putting the minimizing argument iy (k) in the place of (n(k) we oblain a lower bound for type &s as
P& (0s + vj)
(.)
( < Ss mp.((w)))-
Noting that the distribution of the random variable G.j is invariant to task index j, drop the index in the subsequent bounds the error rate for positive values Sg, wk {e, ht (note that the following holds for all y):
E
7 Σ
(oWWV (w) + vn)
Σ
de ( d
(O<-
Σ w < Sh --pp)(()
(48)
kEle,))
To analyze this further, use the following Lemma on the distribution of - -; w;Gi an extension to the asymptotic analysis of majority voting in Gao et al. (2016).
Recall our definition p I min; 14TH < 1 p, Vk he, The following lemma is similar to Lemma 6.3 in Gao et al. 2016). The proof is given next to it for completeness.
Lemma 6 Let p S min; 1
vk E (c, h), for some p E 1/21.
40

---

Published in Transactions on Machine Learning Research (09/2025)
1. Let f. (k) be the minimizer of E, log (3 ((1 + rxa)e twr + +1 rks)ettri) Then,
0 S (k) < Teelli log k E (e, h.. Vn 2 1.
2. For any y E {+1} and any (k) 2
E
(-w,C, B (1)) (w,
d م, W (0,
under the mensure Q (1)(()
Varroguu (- Di=1 w(Gi)
n-+00
Moreover, at tk) = (k),,,
-Es w,G:
ب N (0,1),
under the measure (5(1k)
Var gaas (aa0(-Ete -it= w;G:)
n-
Proof 3 1. Let
n (x)))(()))
(1 + tt + (1 rke)e
Then (x) = 1 and ( 2 Twll loge, P, we have that (k() II (peta(t))lou)) 2 1. Therefore, a Twlli - log p).
t (k) E
2. For the second part, we use Lindeberg's 's condition for the Central Limit Theorem for the expression E -w The Lindebery's ss condition in this contert corresponds to
( [(-mCc E - 1 {{ -,,,G -B Bo ev Var Var (E - -. w.G.)
lim 8+000
Var Var (Ei=1 -w
=0, Ve > 0.
A direct colculation gives
(1 Pkt Pe (a D5:c (k)ws
E 2)
u.
(1 pke) (N) (b))r. + PA:EE - (k))s
(0)
de,, (K) [(1 - Phos) )l + PASe Ia (k))w
(1 Phi) (ke)e + Phote (n(k)
dt,, (k:) log (11 (11 Pke P + pasee Rn
where in (a), we used the following relation Pki = Itree Vk E E h, [n]. 2
The last two equalities imply: at t, (k) (k), E E
[Ei -w = 0. Moreover, ( (.,,
w²- Therefore,
[11
Phoe (k)))n PEuee (.
Var ( (n (-w;Gi) = =w
Pio Pka))e (t (k)/r, + Paoee (nn
4pxc(1 pLo))
Pki eet (k)ms (k))m + Pkace (R/0000
4w p²
2w p² (1- ef (k)]
2wF p2 (1- et (k))s.
(1 p)2 (k)w: e t,, (k)oz)
and hence, Var ora E2 w. 2 (ot
20
00 08 7 - 00.
41

---

Published in Transactions on Machine Learning Research (09/2025)
Additionally, -w,G, -B B [-, - 2/ 2/ws| S 200 almost surely (and therefore, Var ga (-w,G,) - ). Thus, for every e we have that
of w, E Bopaasl-wiCh) 2 Var Varogau
)
i
Σ E-m(i
0, almost surely
for n > 2w 21 (1 Lindeberg's 's condition now follows.
Remark 3 We can see that Var Q q (-ww > 0 as t (k)
<
<- n
11ill log p.
Now, let us go back to proving the lower bound. We have the following:
E
Σ (0) MV (w) + wi)
Σ of
de
(0<-Z)
E EwgGr < Sk
d
d
kEfe.h]
Setting S/=
V Var (fi Ei -w;Gi)), we write the following
Q (k(
0< Ew, w.G. < Ss
Q (k)
0 0< Σ w,G's < V
Var q::(())) Σ O
-, w.G.
0<<
<1)
V Vaa 22000
(E Gw;
(b)
In (b), we use Remark 3
from the proof of Lemma
/Var of2c0) (E, -w; at tn(k)) = tt (k). Also,
Σ (I-wxdh)
exp exp (-nip(w,rr)) rk) (k))a)) exp -n,n(w,ra)) rx) - -t) ( Var
Evaluating Vara -w,,, s E, wi and using the following bounds on the entries of w wi S |ws| I Why Vi E [n), and using the upper-bound t (k) from the Temma D
Σ E-wwc
|/0 |2| log(p)]
exp
-npn(w, r2) ( Var 2:00
2 exp
rep (w, rk))
|
Wrll log(p))
exp
ryp (w, ris)
Putting it all together, We can write from Equation 48
E
1
Σ
(1) Wa (w) # +wi)
(w))
di (k) (0c Var (2 EE; -w;Gis)
-E, WrG.
<1 exp (-vm w.l log(p)
Σ KE (n.h)
nw rk)
Wi
2 min exp ( (-vm Wal log(p)) min pn (w. rk))
dx k d
min (kk(k)
0<
Var (, (E (2, -w; <1
Σ, w,G
42

---

Published in Transactions on Machine Learning Research (09/2025)
By first taking minimum weight vector and then taking the lim inf as - oo and using the Lemma
lim inf log n
Σ d (1)
(w) # ws)
2
lim sup max min yP (w, TR).
n
71
j
n-000
w
H Proof of Proposition 2
Restatement of Proposition 2 Assume V2 = mingmaaza Tkk > 0 for each kt E {e, hi which is satisfied there are at least two workers with non-zero reliability values for each type. the number of workers n satisfies n 2 /3p/F, and the number of tasks per type satisfies
n²²
du Co V min(o2 (n + log(6n")).
for some universal constant Cg then, the TE algorithm to estimate the reliability vectors followed by NP-WMV for label estimation separately for each type (when type information is known) achieves a labeling error rate satisfying
Σ de exp (rkD)
E 10,
+w))
53
kEfe.h}
where ØJ and yy are the estimated and true labels of task j, respectively, and
1 Σ
(T(rr)
log (V)++
7
Proof:
The statement is obtained by appropriately modifying Theorem 4.1 in Gao al. (0166) and Theorem 2 in Bonald & Combes (2017). For the known type case, scparate the tasks according to their type, and each type is dealt with separately as two Dawid-Skene problem instances. Because task types are known for this setting, the TE algorithm is applied separately to each type independently of the other to estimate each type's reliability vectors. Labels are estimated using the corresponding NP-WMV.
From Theorem Bonald & Combes 2017
we have that if the number of workers satisfies
3p F
n
(49)
and the number of tasks d, per type ls E he is
n²
de 2 max 120 x 24a
Vi 2 (nd (rx) + log((n2))) x 82 ni
VRF (n (nd + log((n)))
(50)
then
P (lIre rklooo 2 () < exp((nv0.(r))
(51)
The sufficient condition of can also be written as
n²
dx 2 Cs V² min(p?, F2) (n log(6n2))
B the estimated reliabilities projected onto the sct S 1tfss < 1 This step was not included in the original TE algorithu proposed by Bonald & Combes 2017). Nevertheless, the concentration of the reliability estimate derived from Theorem 2 of [Boaldd & Combes 2017 in the nax-norm sense also holds under this projection, it acts contraction operator.
"According to the TE algorithm described in Section
model and the model considered in Bonald & Combes 2017 is that cousider the true labels deterministic quantity and [ouald & Combes 2017 cousiders them to be random variables. The TE amgorithm the worker-similarity matrix and we can easily
*One difference between
that the worker-similarity matrix independent of the labels and thus the performance bound the TE algorithm Thenrem in Bonald Combes (207)) is valid for deterministic labels
43

---

Published in Transactions on Machine Learning Research (09/2025)
with C3 15 x 29.
Using the inequality log - log yl - min(2.9)
|z-Ø|
Vz, > 0 implied by log x S x 1 for positive 2, we have that
when dy satisfies Equation 50
1 fxs
1 - fki 1
Σ max log
log
1 1 Thi
1 Tki
2
with probability 2 exp(-n - (rx))- Now define the event
1 far Ex Σ max (loB
{max
1 - fki
log
I+ Tus
1 Tki
Under this event, the weights used by the NP estimate are approximately equal to the maximum likelihood
weights. Applying Equation 51
((E) S (- (rx))
Without loss of generality, consider yy so that 03 # y, implics Ú3 1. Let the type for task j be hy-
P(Ùs # セソ) = P((9; + かル } Eki) ) + +(EE))
+ fxje Xi3
=
log - Pkyz
<0 n Eky
+ +P(E
1 1 fkye 1-
I(X,==1)
1 + Fkyz
1(Xxx=11
21 216n 0 Fig) + +PF
(52)
1 PR.i
1 - pkya
Define the two random variables
A Tkys
1(X,==)
1 (1+ Tkys Tky
1(X,=-1)
Tky
1-
(1 fk, riage))
11x
(1 PA - Tkyi)
1(X,=
A2
(1 + Arge))
(1 + (1+ -1k
1-fuge 1(X.=11
1+fr,t T-Payt
1(x,==11 1)
Then, the expression II: of A and Ag. On the event Ekyy
in the above probability is given by the product
ItFaye
1 pkya
)) s exp(1). 1 - -1kj
1 1-Pkyt Pkyz
A2 < exp
2 Σ max
log
1 log
1 + rkya
Therefore,
2(AA12221]
< ((A1 2 exp (-1)) n Fiky))
IP ((At 2 exp (- n Eig
}
(a)
(( |
(-2) 1 }
$
2 exp
1
B[A
< exp
2
(6)
44

---

Published in Transactions on Machine Learning Research (09/2025)
where in (a) used the observation that A1 and in (b) used Markov's inequality the random
variable A 0. Evaluating the expectation,
E[A]
Tky I + Tkya
Tkgt
+
Tkys +
$ 1 Tki
2
Tkys
2
exp
Σ log (1 -1-rin (1-12))
n
2
Returning to Equation 52 we have that for a task j with type h;
Ps (0, + vU) I exp ( P(()) exp
1 +1 exp exp (-p(-=un((r))
Averaging for all tasks j E [d], we get the error rate for known types as
d Σ
de Σ kEfe.h)
E
Σ
(0) + ui)
+1)
d exp (-nff,((rt)
==1
Label Estimation Performance: Proof of Theorem 2
The expected rate of labeling error using the law of lotal expectation can be decomposed as
Σ (0s + v))
1 Σ Σ 1 (0s # us) Eep PP(Epp)) +E
E
(0s
Uj)
P(F))))
d
11
where Eepe defined as the event of perfect clustering. that 1 = 0. We upper bound the second term II 11 F(Ep.). Now, when the condition described in the Equation 10 of Theorem 1 in the main paper is satisfied by (nes d, (N(a)) for each i E {e, h} it is characterized by Theorem as
P(F < 2d exp (-C2na ((eaa
To upper bound the term we invoke the Proposition 2 Recall the partition of the set of workers mutually exclusive sets Na and Mrr for clustering and the labeling steps, respectively. Hence, given the event Epc: the labeling step has perfect knowledge of each task's 's type, and NP W MV for the known type model would yield the following error rate when (nrt, de, da, (NN)) satisfy the conditions stated in Proposition
dx
I 3 Σ
exp (- n (bN
d
kEtE,
45


Reviews:
[{"review_id": "FYPJOP546z", "reviewer": "Reviewer_tuu7", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths**\n- The use of $\\ell\\_\\infty$-concentration to obtain tight guarantees for spectral clustering is clever. Also, interesting how spectral clustering alone can achieve perfect clustering without additional refinement steps as in SBMs or GMMs.\n- Algorithm-specific lower bound for weighted majority voting schemes clearly shows the superiority of cluster-then-DS approach.\n- Experiments with various baselines\n\n**Weaknesses**\n- Writing can be improved.\n- Slightly lacking discussions related to prior work; see Requested Changes below.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The authors consider a clustered variant of the Dawid-Skene (DS) model, by assuming that there are two types of tasks and each worker's mistake probability is determined by the task's type. The paper proposes a two-stage approach, where in the first stage, the tasks are clustered from the (empirical) task-similarity matrix via computing the leading eigenvector and thresholding based on its entries. In the second tage, existing DS Algorithm is used per cluster, which consists of Triangular Estimation (TE) and Nitzan-Paroush (NP). The authors show that even with weighted majority voting scheme, the error exponent without clustering is strictly worse than the proposed clustering-based approach. The proposed approach is empirically compared against various baselines, showing its efficacy.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "**Minor**\n- \"proposition\" \"algorithm\" \"theorem\" should be capitalized whenever applicable\n- Showing the runtime would be helpful to see the overhead of two-stage approach, as well as runtime comparison of different algorithms.\n- Also, maybe I missed it, but seeing the actual clustering accuracy would be nice.\n\n**Critical**\n- Some relevant discussions and references are missing. For instance, in clustering of GMMs, Lu & Zhou (2016) [2], they showed that for a general Dawid-Skene model including different task types with different reliability vectors, if I'm not mistaken. Also, [1] seems to also perform weighted majority voting of some sort. I can vaguely see that there are indeed some differences, but given the amount of literature in crowdsourcing theories, I feel that there is a strong need to clearly articulate the difference from the current submission and prior works, both model-wise and guarantee-wise, maybe even as a separate section/appendix.\n- The result that a logarithmic number of tasks suffices for perfect clustering highly resembles the results for clustering in mixture models, such as GMMs [2,3]. Some discussions should be provided regarding this as well.\n- In Proposition 1, the error exponents depend on $e^{w\\_i}$'s. Then if $w_i = w$ for some $w > 0$, then we should recover the unweighted version. But then, $\\hat{y}^{WMV}$ should be the same regardless of what $w > 0$ is, yet the guarantee seems to depend heavily on $w$, i.e., it is not \"scale-invariant\" in some sense. If my description is not mistaken, the authors should elaborate on this \"gap.\"\n\n\n**Questions**\n- The idea of using the entries of leading eigenvector for thresholding seems similar to Fiedler vector entries that can be used to partition a graph via algebraic connectivity. Is this somewhat related to the approach taken by the authors?\n- Is the Lloyd-type baseline of [1] also applicable here?\n\n\n[1] https://ieeexplore.ieee.org/document/10252002\n[2] https://arxiv.org/abs/1612.02099 (Sec 4.2)", "broader_impact_concerns": "None", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "AyjMcjUD64", "reviewer": "Reviewer_Yfhp", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "# Strengths\n\n - **Theoretical analysis**: The paper provides a formal guarantee that perfect task-type clustering is achievable with high probability under a logarithmic worker-to-task ratio, using spectral methods, while a set of impractical assumptions are required.\n\n - **Empirical validation**: The method is evaluated on small-scale synthetic and real-world datasets, showing improved labeling accuracy compared to type-agnostic baselines.\n\n# Weaknesses\n\n - **Unclear novelty**: The modeling assumptions (type-dependent worker accuracy), spectral clustering approach, and analysis closely follow existing literature, with unclear distinctions from prior work, e.g., [Kaito et al 24] Kaito et al. \"Optimal Clustering from Noisy Binary Feedback\", Machine Learning, 2024. Also, the spectral analysis follows known techniques, and the paper does not clearly identify new technical challenges or insights.\n\n - **Unrealistic assumptions**: The setting assumes only two task types and that all workers label all tasks, which is not practical in real-world crowdsourcing platforms. Indeed, the crowdsourcing systems are employed for constructing large-scale datasets. These assumptions need to be thoroughly justified. At least, regarding the complete assignments of all tasks to all workers, the authors could provide an empirical evaluation given spare assignments investigating the importance of the assumption. In addition, the method does not handle more general task heterogeneity (e.g., more than two types or continuous difficulty), unlike recent works such as [Kaito et al. 24].\n\n - **Poor writing and organization**: The paper is hard to follow in several places, and the related work section is incomplete and outdated.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper introduces a new crowdsourcing model where each task belongs to one of two latent types (easy or hard), and each worker has type-dependent reliability. It proposes a spectral clustering method that recovers task types using the principal eigenvector of a task similarity matrix, followed by type-aware label aggregation using the Dawid-Skene model. Theoretical analysis shows that perfect clustering is achievable with high probability when the number of workers scales logarithmically with the number of tasks, and that clustering improves label estimation. Experiments on synthetic and real datasets demonstrate that the proposed method outperforms type-agnostic baselines and other task-type–aware approaches.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "**1. Clarify Novelty and Contributions**\n\n The authors could clarify how their model and algorithm differ from prior work, particularly those that already address type-dependent worker reliability and spectral clustering (e.g., Kaito et al., 2024, and collaborative clustering literature). It would be helpful to highlight any specific theoretical challenges or insights that distinguish this work from standard spectral clustering analysis.\n\n**2. Justify and Generalize Modeling Assumptions**\n\nThe paper could provide stronger justification for its simplifying assumptions, particularly the restriction to two task types and complete worker-task assignment. It would also improve the paper to include discussion on how these assumptions align with real-world crowdsourcing settings, and how the method might generalize to more realistic cases (e.g., multiple or continuous task types, sparse worker-task assignment). A toy experiment or illustrative extension to more than two task types could help support this discussion.\n\n**3. Evaluate Robustness to Sparse Assignments**\n\nThe authors could include experiments where workers label only a subset of tasks to examine how performance changes when the complete assignment assumption is relaxed. This would help assess the method’s robustness and practical relevance in realistic settings.\n\n\n**4. Improve Writing and Organization**\n\nThe authors could revise the paper for clarity, especially in the theoretical sections, to make the analysis and key ideas easier to follow. Reorganizing some sections would also help improve logical flow and readability.\n\n\n**5. Expand and Update Related Work**\n\nThe related work section could be expanded to include recent and relevant literature on task heterogeneity, adaptive querying, and clustering in crowdsourcing. This would help position the contribution more clearly within the broader research landscape.", "broader_impact_concerns": "I have no specific broader impact concerns.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "KvOLqmryMM", "reviewer": "Reviewer_eMiz", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths\n\nThe authors provide theoretical guarantees for the proposed two-step model.\n\nEvaluation on multiple real and synthetic datasets demonstrates the benefit of clustering, and comparisons to alternative specialization models bolster the empirical case.\n\nWeaknesses\n\nThe model assumes every worker labels every task, which may not hold in most real-world crowdsourcing settings.\n\nThe authors assume that the tasks can be separated into  “easy” and “hard” clusters. However, the authors did not provide evidence whether this assumption holds in the real-world dataset. I suspect whether there exists a clear gap between \"easy\" and \"hard\" clusters or there might exist more than two clusters in the real-world datasets.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper addresses the problem of crowdsourcing when tasks inherently fall into “easy” and “hard” types. Building on the classical Dawid–Skene one-coin model, the authors propose a two-type DS model in which each worker has separate reliability parameters for each task type. The authors first introduce a simple spectral method to cluster tasks by types , with a theoretical guarantee that O(log d) workers suffice for perfect clustering. Then, the authors provide an $ℓ_∞$-norm perturbation bound enabling a perfect-recovery result. The proposed method is validated on five public datasets, showing that clustering followed by DS-style algorithms reduces error compared to DS alone and outperforms other task-specialization methods.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Can the authors provide evidence whether real-world datasets can be separate into \"easy\" and \"hard\" clusters? It would be beneficial if the authors can illustrate a clear gap between \"easy\" and \"hard\" clusters in real-world datasets.\n\nSection 3 contains a lot of technical details. It would be beneficial if the authors can provide more commentary after each lemma or theory, explaining what is proven in plain English. This section also involves many mathematical symbols, and it would be beneficial if the authors can summarize the symbols in a table.", "broader_impact_concerns": "The authors did not provide a discussion related to broader impact. The authors might want to discuss the potential benefits of the method such as reduce labeling costs or whether the method is likely to mitigate or introduce new bias in crowdsourcing analysis.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Decision: Accept (poster)