Efficient PAC Learning from the Crowd with Pairwise Comparisons

Shiwei Zeng, Jie Shen

Research output: Contribution to journalConference articlepeer-review

4 Scopus citations

Abstract

We study crowdsourced PAC learning of threshold function, where the labels are gathered from a pool of annotators some of whom may behave adversarially. This is yet a challenging problem and until recently has computationally and query efficient PAC learning algorithm been established by Awasthi et al. (2017). In this paper, we show that by leveraging the more easily acquired pairwise comparison queries, it is possible to exponentially reduce the label complexity while retaining the overall query complexity and runtime. Our main algorithmic contributions are a comparison-equipped labeling scheme that can faithfully recover the true labels of a small set of instances, and a label-efficient filtering process that in conjunction with the small labeled set can reliably infer the true labels of a large instance set.

Original languageEnglish
Pages (from-to)25973-25993
Number of pages21
JournalProceedings of Machine Learning Research
Volume162
StatePublished - 2022
Event39th International Conference on Machine Learning, ICML 2022 - Baltimore, United States
Duration: 17 Jul 202223 Jul 2022

Fingerprint

Dive into the research topics of 'Efficient PAC Learning from the Crowd with Pairwise Comparisons'. Together they form a unique fingerprint.

Cite this