Avoiding Imposters and Delinquents: Adversarial Crowdsourcing and Peer Prediction

By Jacob Steinhardt, Gregory Valiant, Moses Charikar. 2016

46 citations recorded by the source corpus.

We consider a crowdsourcing model in which $n$ workers are asked to rate the quality of $n$ items previously generated by other workers. An unknown set of $\alpha n$ workers generate reliable ratings, while the remaining workers may behave arbitrarily and possibly adversarially. The manager of the experiment can also manually evaluate the quality of a small number of items, and wishes to curate together almost all of the high-quality items with at most an $\epsilon$ fraction of low-quality items. Perhaps surprisingly, we show that this is possible with an amount of work required of the manager, and each worker, that does not scale with $n$: the dataset can be curated with $\tilde{O}\Big(\frac{1}{\beta\alpha^3\epsilon^4}\Big)$ ratings per worker, and $\tilde{O}\Big(\frac{1}{\beta\epsilon^2}\Big)$ ratings by the manager, where $\beta$ is the fraction of high-quality items. Our results extend to the more general setting of peer prediction, including peer grading in online classrooms.

Subfields: Artificial Intelligence, Computer Science Applications

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computer Science Applications

Citations in the corpus

Certified Defenses for Data Poisoning Attacks (2017, background): “…(Diakonikolas et al., 2016; Lai et al., 2016; Charikar et al., 2017), classiﬁcation (Klivans et al., 2009; Awasthi et al., 2014), regression (Nasrabadi et al., 2011; Nguyen and Tran, 2013; Chen et al., 2013; Bhatia et al., 2015) and crowdsourced data aggregation (Steinhardt et al., 2016).”
Learning Discrete Distributions from Untrusted Batches (2017, background): “orks include [LRV16, DKK+16, DKK+17] who consider the problem of robustly estimating the mean and covariance of high-dimensional Gaussians (and other distributions such as product distributions), and [SVC16] who consider a sparse ratings aggregation setting. Other learning problems, such as robustly”
Learning from untrusted data (2016, neutral): “This result is strong in the following sense: if one instead uses all n samples xi , the classical result of Rudelson (1999) only bounds λmax by ≈ σ 2 log(n), and even then only in expectation.”
Does robustness imply tractability? A lower bound for planted clique in the semi-random model (2017, background): “This setting, where the majority of points are corrupted, was studied by Steinhardt et al. (2016); Charikar et al. (2017); and Steinhardt et al. (2017).”
A Data Prism: Semi-verified learning in the small-alpha regime (2018, background): “The works (Steinhardt et al., 2016) and (Charikar et al., 2017) and the very recent work (Diakonikolas et al., 2017b) consider the setting where a minority of the data is “good” (i.e. α 1/2), with (Charikar et al., 2017) formally proposing the “semi-verified” learning model where one may obtain a…”
A Data Prism: Semi-Verified Learning in the Small-Alpha Regime (2017, background): “eriﬁed” reviews, which is independent of the total number of items to review, and depends inverse linearly on the desired error (to logarithmic factors). Onenatural question isprompted bytheresults of[12],whichprovide efﬁcientalgorithms fortheregime where r = poly(1/α), but where the number of revie”
Resilience: A Criterion for Learning in the Presence of Arbitrary Outliers (2017, background): “…recently that provable algorithms for learning in the presence of a large fraction of arbitrary (and potentially adversarial) data have been formulated in high-dimensional settings (Diakonikolas et al., 2016; Lai et al., 2016; Charikar et al., 2017; Steinhardt et al., 2016; Bhatia et al., 2015).”