Reducing Crowdsourcing to Graphon Estimation, Statistically.

Inferring the correct answers to binary tasks based on multiple noisy answersin an unsupervised manner has emerged as the canonical question for micro-taskcrowdsourcing or more generally aggregating opinions. In graphon estimation,one is interested in estimating edge intensities or probabilities between nodesusing a single snapshot of a graph realization. In the recent literature, therehas been exciting development within both of these topics. In the context ofcrowdsourcing, the key intellectual challenge is to understand whether a giventask can be more accurately denoised by aggregating answers collected fromother different tasks. In the context of graphon estimation, preciseinformation limits and estimation algorithms remain of interest. In this paper,we utilize a statistical reduction from crowdsourcing to graphon estimation toadvance the state-of-art for both of these challenges. We use concepts fromgraphon estimation to design an algorithm that achieves better performance thanthe {\em majority voting} scheme for a setup that goes beyond the {\em rankone} models considered in the literature. We use known explicit lower boundsfor crowdsourcing to provide refined lower bounds for graphon estimation.