A Minimax Optimal Algorithm for Crowdsourcing
We consider the problem of accurately estimating the reliability of workers based on noisy labels they provide, which is a fundamental question in crowdsourcing. We propose a novel lower bound on the minimax estimation error which applies to any estimation procedure. We further propose Triangular Estimation (TE), an algorithm for estimating the reliability of workers. TE has low complexity, may be implemented in a streaming setting when labels are provided by workers in real time, and does not rely on an iterative procedure. We prove that TE is minimax optimal and matches our lower bound. We conclude by assessing the performance of TE and other state-of-the-art algorithms on both synthetic and real-world data.
Summary of paper:
The authors derive a lower bound on estimating crowdsource worker reliability in labeling data.  They then propose an algorithm to estimate this reliability and analyze the algorithm’s performance.
Summary of review:
This submission presents a solid piece of research that is well-grounded in both theory and application.
Detailed review:
—
Quality:
This paper is thorough.  The lower bound and relevant proofs are outlined cleanly.  The algorithm is presented in conjunction with time and memory complexity analysis, and the authors compare to related work nicely.  Both simulated and real data sets are used; the simulated data have multiple settings and six sources of real-world data are used.  The experiments do not demonstrate that the proposed algorithms outperforms all competing methods, but these results are refreshingly realistic and provide a compelling argument for the use of the proposed algorithm.
—
Clarity:
The paper is well-written; the problem and contributions are outlined clearly.  The paper would benefit from more description regarding the intuitions of TE and perhaps a high-level summary paragraph in the numerical experiments section.
—
Originality: 
The proposed algorithm is novel and the derived lower bound is tied nicely to the problem, bringing a rare balance of theory and application.  
—
Significance:
While the problem addressed is very specific, it is important.  The proposed algorithm does well—even if it doesn’t beat all others in every instance, it’s more consistent in its performance.  This paper will be a solid contribution to the crowdsourcing literature, and could easily impact the use of crowdsourced labels as well.