Minimax Optimal Convergence Rates for Estimating Ground Truth from Crowdsourced Labels

Abstract

Crowdsourcing has become a primary means for label collection in many real-world machine learning applications. A classical method for inferring the true labels from the noisy labels provided by crowdsourcing workers is Dawid-Skene estimator. In this paper, we prove convergence rates of a projected EM algorithm for the Dawid-Skene estimator. The revealed exponent in the rate of convergence is shown to be optimal via a lower bound argument. Our work resolves the long standing issue of whether Dawid-Skene estimator has sound theoretical guarantees besides its good performance observed in practice. In addition, a comparative study with majority voting illustrates both advantages and pitfalls of the Dawid-Skene estimator.

References in corpus (2)

• On the absolute constants in the Berry-Esseen type inequalities for identically distributed summands
• Estimating Undirected Graphs Under Weak Assumptions

Cited by in corpus (21)

• Spectral Methods meet EM: A Provably Optimal Algorithm for Crowdsourcing
• Error Rate Bounds and Iterative Weighted Majority Voting for Crowdsourcing
• Regularized Minimax Conditional Entropy for Crowdsourcing
• Statistical Decision Making for Optimal Budget Allocation in Crowd Labeling
• A Permutation-based Model for Crowd Labeling: Optimal Estimation and Robustness
• Exact Exponent in Optimal Rates for Crowdsourcing
• Achieving Budget-optimality with Adaptive Schemes in Crowdsourcing
• Fast Dawid-Skene: A Fast Vote Aggregation Scheme for Sentiment Classification
• SLiMFast: Guaranteed Results for Data Fusion and Source Reliability
• Reducing Crowdsourcing to Graphon Estimation, Statistically
• Breaking the $1/\sqrt{n}$ Barrier: Faster Rates for Permutation-based Models in Polynomial Time
• A Technical Survey on Statistical Modelling and Design Methods for Crowdsourcing Quality Control
• Bayesian Decision Process for Cost-Efficient Dynamic Ranking via Crowdsourcing
• A Worker-Task Specialization Model for Crowdsourcing: Efficient Inference and Fundamental Limits
• Learning from Multiple Noisy Partial Labelers
• Optimal Inference in Crowdsourced Classification via Belief Propagation
• Crowdsourced Labeling for Worker-Task Specialization Model
• Towards Optimal Estimation of Bivariate Isotonic Matrices with Unknown Permutations
• On the Impossibility of Convex Inference in Human Computation
• Dynamic Task Allocation for Crowdsourcing Settings
• Binary Classification with XOR Queries: Fundamental Limits and An Efficient Algorithm