Fetching the paper…

Reading the bibliography…

2017

A Data Prism: Semi-Verified Learning in the Small-Alpha Regime

Meister, Michela, Valiant, Gregory

Original
PDF
Post on X

Understand

We consider a model of unreliable or crowdsourced data where there is an underlying set of $n$ binary variables, each evaluator contributes a (possibly unreliable or adversarial) estimate of the values of some subset of $r$ of the variables, and the learner is given the true value of a constant number of variables.

We show that, provided an $\alpha$-fraction of the evaluators are "good" (either correct, or with independent noise rate $p < 1/2$), then the true values of a $(1-\epsilon)$ fraction of the $n$ underlying variables can be deduced as long as $\alpha > 1/(2-2p)^r$.
This setting can be viewed as an instance of the semi-verified learning model introduced in [CSV17], which explores the tradeoff between the number of items evaluated by each worker and the fraction of good evaluators.
Our results require the number of evaluators to be extremely large, $>n^r$, although our algorithm runs in linear time, $O_{r,\epsilon}(n)$, given query access to the large dataset of evaluations.

A Data Prism: Semi-Verified Learning in the Small-Alpha Regime · Around

Built on

A survey of sampling from contaminated distributions
John W Tukey · 1960
Earlier work this paper cites.
Sphere packing numbers for subsets of the boolean n-cube with bounded vapnik-chervonenkis dimension
David Haussler · 1995
Earlier work this paper cites.
Matrix completion with noise
Emmanuel J Candes and Yaniv Plan · 2010
Earlier work this paper cites.
Matrix completion from a few entries
Raghunandan H Keshavan, Andrea Montanari, and Sewoong Oh · 2010
Earlier work this paper cites.
Robust statistics: the approach based on influence functions
Frank R Hampel, Elvezio M Ronchetti, Peter J Rousseeuw, and Werner A Stahel · 2011
Earlier work this paper cites.

Similar

Robust statistics
Peter J Huber · 2011
Cited alongside, same era.
Robust regression via hard thresholding
Kush Bhatia, Prateek Jain, and Purushottam Kar · 2015
Cited alongside, same era.
On the complexity of random satisfiability problems with planted solutions
Vitaly Feldman, Will Perkins, and Santosh Vempala · 2015
Cited alongside, same era.
Robust estimators in high dimensions without the computational intractability
Ilias Diakonikolas, Gautam Kamath, Daniel M Kane, Jerry Li, Ankur Moitra, and Alistair Stewart · 2016
Cited alongside, same era.

Then

Agnostic estimation of mean and covariance
Kevin A Lai, Anup B Rao, and Santosh Vempala · 2016
Later among the works it cites.
Strongly refuting random csps below the spectral threshold
Original
Prasad Raghavendra, Satish Rao, and Tselil Schramm · 2016
Later among the works it cites.
Avoiding imposters and delinquents: Adversarial crowdsourcing and peer prediction
Jacob Steinhardt, Gregory Valiant, and Moses Charikar · 2016
Later among the works it cites.
Learning from untrusted data
M. Charikar, J. Steinhardt, and G. Valiant · 2017
Closest in time.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…