# A Worker-Task Specialization Model for Crowdsourcing: Efficient Inference and Fundamental Limits

arXiv: https://arxiv.org/abs/2111.12550 · HTML: https://mlsanity.com/paper/2111.12550/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 28 of its 78 references that are in the map.
- First posted on arXiv 19 Nov 2021.

## Builds on (most cited first, 28 of 28)

- [Exact Recovery in the Stochastic Block Model](https://mlsanity.com/paper/1405.3267/) (2014)
- [Spectral Methods meet EM: A Provably Optimal Algorithm for Crowdsourcing](https://mlsanity.com/paper/1406.3824/) (2014)
- [A Faster Interior Point Method for Semidefinite Programming](https://mlsanity.com/paper/2009.10217/) (2020)
- [Learning From Noisy Singly-labeled Data](https://mlsanity.com/paper/1712.04577/) (2017)
- [Clustering with Noisy Queries](https://mlsanity.com/paper/1706.07510/) (2017)
- [Solving SDP Faster: A Robust IPM Framework and Efficient Implementation](https://mlsanity.com/paper/2101.08208/) (2021)
- [Statistical-Computational Tradeoffs in Planted Problems and Submatrix Localization with a Growing Number of Clusters and Submatrices](https://mlsanity.com/paper/1402.1267/) (2014)
- [Crowdsourcing via Pairwise Co-occurrences: Identifiability and Algorithms](https://mlsanity.com/paper/1909.12325/) (2019)
- [On semidefinite relaxations for the block model](https://mlsanity.com/paper/1406.5647/) (2014)
- [Error Rate Bounds and Iterative Weighted Majority Voting for Crowdsourcing](https://mlsanity.com/paper/1411.4086/) (2014)
- [Adversarial Crowdsourcing Through Robust Rank-One Matrix Completion](https://mlsanity.com/paper/2010.12181/) (2020)
- [Robust and computationally feasible community detection in the presence of arbitrary outlier nodes](https://mlsanity.com/paper/1404.6000/) (2014)
- [Community Detection in Hypergraphs, Spiked Tensor Models, and Sum-of-Squares](https://mlsanity.com/paper/1705.02973/) (2017)
- [Convexified Modularity Maximization for Degree-corrected Stochastic Block Models](https://mlsanity.com/paper/1512.08425/) (2015)
- [A Permutation-based Model for Crowd Labeling: Optimal Estimation and Robustness](https://mlsanity.com/paper/1606.09632/) (2016)
- [Community Recovery in Hypergraphs](https://mlsanity.com/paper/1709.03670/) (2017)
- [Consistency of weighted majority votes](https://mlsanity.com/paper/1312.0451/) (2013)
- [Gradient Descent for Sparse Rank-One Matrix Completion for Crowd-Sourced Aggregation of Sparsely Interacting Workers](https://mlsanity.com/paper/1904.11608/) (2019)
- [Exact Exponent in Optimal Rates for Crowdsourcing](https://mlsanity.com/paper/1605.07696/) (2016)
- [Achieving Budget-optimality with Adaptive Schemes in Crowdsourcing](https://mlsanity.com/paper/1602.03481/) (2016)
- [Minimax Optimal Convergence Rates for Estimating Ground Truth from Crowdsourced Labels](https://mlsanity.com/paper/1310.5764/) (2013)
- [Reducing Crowdsourcing to Graphon Estimation, Statistically](https://mlsanity.com/paper/1703.08085/) (2017)
- [Robust Hypergraph Clustering via Convex Relaxation of Truncated MLE](https://mlsanity.com/paper/2003.10038/) (2020)
- [Regularized Minimax Conditional Entropy for Crowdsourcing](https://mlsanity.com/paper/1503.07240/) (2015)
- [Exponential error rates of SDP for block models: Beyond Grothendieck's inequality](https://mlsanity.com/paper/1705.08391/) (2017)
- [Fundamental Limits on Data Acquisition: Trade-offs between Sample Complexity and Query Difficulty](https://mlsanity.com/paper/1712.00157/) (2017)
- [Binary Classification with XOR Queries: Fundamental Limits and An Efficient Algorithm](https://mlsanity.com/paper/2001.11775/) (2020)
- [Crowdsourced Labeling for Worker-Task Specialization Model](https://mlsanity.com/paper/2004.00101/) (2020)

## Built on by (most cited first, 2 of 2)

- [SignSGD with Federated Voting](https://mlsanity.com/paper/2403.16372/) (2024)
- [SignSGD with Federated Defense: Harnessing Adversarial Attacks through Gradient Sign Decoding](https://mlsanity.com/paper/2402.01340/) (2024)

## Abstract (arXiv)

Crowdsourcing system has emerged as an effective platform for labeling data with relatively low cost by using non-expert workers. Inferring correct labels from multiple noisy answers on data, however, has been a challenging problem, since the quality of the answers varies widely across tasks and workers. Many existing works have assumed that there is a fixed ordering of workers in terms of their skill levels, and focused on estimating worker skills to aggregate the answers from workers with different weights. In practice, however, the worker skill changes widely across tasks, especially when the tasks are heterogeneous. In this paper, we consider a new model, called d-type specialization model, in which each task and worker has its own (unknown) type and the reliability of each worker can vary in the type of a given task and that of a worker. We allow that the number d of types can scale in the number of tasks. In this model, we characterize the optimal sample complexity to correctly infer the labels within any given accuracy, and propose label inference algorithms achieving the order-wise optimal limit even when the types of tasks or those of workers are unknown. We conduct experiments both on synthetic and real datasets, and show that our algorithm outperforms the existing algorithms developed based on more strict model assumptions.