Timezone: »

Sewoong Oh: "The Minimax Rate for Adaptive Crowdsourcing"
Sewoong Oh

Fri Dec 09 02:00 AM -- 02:45 AM (PST) @

Adaptive schemes, where tasks are assigned based on the data collected thus far, are widely used in practical crowdsourcing systems to efficiently allocate the budget. However, existing theoretical analyses of crowdsourcing systems suggest that the gain of adaptive task assignments is minimal. To bridge this gap, we propose a new model for representing practical crowdsourcing systems, which strictly generalizes the popular Dawid-Skene model, and characterize the fundamental trade-off between budget and accuracy. We introduce a novel adaptive scheme that matches this fundamental limit. We introduce new techniques to analyze the spectral analyses of non-back-tracking operators, using density evolution techniques from coding theory.

Author Information

Sewoong Oh (University of Washington)

More from the Same Authors