Timezone: »

A Minimax Optimal Algorithm for Crowdsourcing
Thomas Bonald · Richard Combes

Mon Dec 04 06:30 PM -- 10:30 PM (PST) @ Pacific Ballroom #23 #None

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.

Author Information

Thomas Bonald (Telecom ParisTech)
Richard Combes (Centrale-Supelec)

I am currently an assistant professor in Centrale-Supelec in the Telecommunication department. I received the Engineering Degree from Telecom Paristech (2008), the Master Degree in Mathematics from university of Paris VII (2009) and the Ph.D. degree in Mathematics from university of Paris VI (2013). I was a visiting scientist at INRIA (2012) and a post-doc in KTH (2013). I received the best paper award at CNSM 2011. My current research interests are machine learning, networks and probability.

More from the Same Authors