# Spectral Methods meet EM: A Provably Optimal Algorithm for Crowdsourcing

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

## Key facts

- Cited by 63 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 15 Jun 2014.

## Built on by (most cited first, 30 of 63)

- [Detecting Corrupted Labels Without Training a Model to Predict](https://mlsanity.com/paper/2110.06283/) (2021)
- [If in a Crowdsourced Data Annotation Pipeline, a GPT-4](https://mlsanity.com/paper/2402.16795/) (2024)
- [Identifiability of Label Noise Transition Matrix](https://mlsanity.com/paper/2202.02016/) (2022)
- [End-to-End Weak Supervision](https://mlsanity.com/paper/2107.02233/) (2021)
- [Beyond Images: Label Noise Transition Matrix Estimation for Tasks with Lower-Quality Features](https://mlsanity.com/paper/2202.01273/) (2022)
- [Convergence of gradient descent for deep neural networks](https://mlsanity.com/paper/2203.16462/) (2022)
- [Bayesian Calibration of Win Rate Estimation with LLM Evaluators](https://mlsanity.com/paper/2411.04424/) (2024)
- [An Instance-Dependent Simulation Framework for Learning with Label Noise](https://mlsanity.com/paper/2107.11413/) (2021)
- [Breaking the gridlock in Mixture-of-Experts: Consistent and Efficient Algorithms](https://mlsanity.com/paper/1802.07417/) (2018)
- [Deep Learning From Crowdsourced Labels: Coupled Cross-entropy Minimization, Identifiability, and Regularization](https://mlsanity.com/paper/2306.03288/) (2023)
- [Theoretical Constraints on the Expressive Power of mathsfRoPE-based Tensor Attention Transformers](https://mlsanity.com/paper/2412.18040/) (2024)
- [Knowledge Learning with Crowdsourcing: A Brief Review and Systematic Perspective](https://mlsanity.com/paper/2206.09315/) (2022)
- [CrowdSpeech and VoxDIY: Benchmark Datasets for Crowdsourced Audio Transcription](https://mlsanity.com/paper/2107.01091/) (2021)
- [Crowdsourcing via Annotator Co-occurrence Imputation and Provable Symmetric Nonnegative Matrix Factorization](https://mlsanity.com/paper/2106.07193/) (2021)
- [Deep Clustering with Incomplete Noisy Pairwise Annotations: A Geometric Regularization Approach](https://mlsanity.com/paper/2305.19391/) (2023)
- [CrowdLLM: Building LLM-Based Digital Populations Augmented with Generative Models](https://mlsanity.com/paper/2512.07890/) (2025)
- [Surprisingly Popular Voting Recovers Rankings, Surprisingly!](https://mlsanity.com/paper/2105.09386/) (2021)
- [Rethinking Noisy Label Models: Labeler-Dependent Noise with Adversarial Awareness](https://mlsanity.com/paper/2105.14083/) (2021)
- [A Taxonomy of Rater Disagreements: Surveying Challenges & Opportunities from the Perspective of Annotating Online Toxicity](https://mlsanity.com/paper/2311.04345/) (2023)
- [Ensemble learning using individual neonatal data for seizure detection](https://mlsanity.com/paper/2204.07043/) (2022)
- [Transfer Learning for Kernel-based Regression](https://mlsanity.com/paper/2310.13966/) (2023)
- [Learning From Crowdsourced Noisy Labels: A Signal Processing Perspective](https://mlsanity.com/paper/2407.06902/) (2024)
- [OpinionRank: Extracting Ground Truth Labels from Unreliable Expert Opinions with Graph-Based Spectral Ranking](https://mlsanity.com/paper/2102.05884/) (2021)
- [A Worker-Task Specialization Model for Crowdsourcing: Efficient Inference and Fundamental Limits](https://mlsanity.com/paper/2111.12550/) (2021)
- [A Light-weight, Effective and Efficient Model for Label Aggregation in Crowdsourcing](https://mlsanity.com/paper/2212.00007/) (2022)
- [Streaming algorithms for evaluating noisy judges on unlabeled data -- binary classification](https://mlsanity.com/paper/2306.01726/) (2023)
- [Scalable Interactive Machine Learning for Future Command and Control](https://mlsanity.com/paper/2402.06501/) (2024)
- [Sharp bounds on aggregate expert error](https://mlsanity.com/paper/2407.16642/) (2024)
- [Time and Memory Trade-off of KV-Cache Compression in Tensor Transformer Decoding](https://mlsanity.com/paper/2503.11108/) (2025)
- [Detecting adversaries in Crowdsourcing](https://mlsanity.com/paper/2110.04117/) (2021)

## Abstract (arXiv)

Crowdsourcing is a popular paradigm for effectively collecting labels at low cost. The Dawid-Skene estimator has been widely used for inferring the true labels from the noisy labels provided by non-expert crowdsourcing workers. However, since the estimator maximizes a non-convex log-likelihood function, it is hard to theoretically justify its performance. In this paper, we propose a two-stage efficient algorithm for multi-class crowd labeling problems. The first stage uses the spectral method to obtain an initial estimate of parameters. Then the second stage refines the estimation by optimizing the objective function of the Dawid-Skene estimator via the EM algorithm. We show that our algorithm achieves the optimal convergence rate up to a logarithmic factor. We conduct extensive experiments on synthetic and real datasets. Experimental results demonstrate that the proposed algorithm is comparable to the most accurate empirical approach, while outperforming several other recently proposed methods.