Skip to main navigation Skip to search Skip to main content

Semi-Verified PAC Learning from the Crowd

    Research output: Contribution to journal › Conference article › peer-review

    Abstract

    We study the problem of crowdsourced PAC learning of threshold functions. This is a challenging problem and only recently have query-efficient algorithms been established under the assumption that a noticeable fraction of the workers are perfect. In this work, we investigate a more challenging case where the majority may behave adversarially and the rest behave as the Massart noise - a significant generalization of the perfectness assumption. We show that under the semi-verified model of Charikar et al. (2017), where we have (limited) access to a trusted oracle who always returns correct annotations, it is possible to PAC learn the underlying hypothesis class with a manageable amount of label queries. Moreover, we show that the labeling cost can be drastically mitigated via the more easily obtained comparison queries. Orthogonal to recent developments in semi-verified or list-decodable learning that crucially rely on data distributional assumptions, our PAC guarantee holds by exploring the wisdom of the crowd.

    Original languageEnglish
    Pages (from-to)505-522
    Number of pages18
    JournalProceedings of Machine Learning Research
    Volume206
    StatePublished - 2023
    Event26th International Conference on Artificial Intelligence and Statistics, AISTATS 2023 - Valencia, Spain
    Duration: Apr 25 2023 → Apr 27 2023

    ASJC Scopus subject areas

    • Artificial Intelligence
    • Software
    • Control and Systems Engineering
    • Statistics and Probability

    Fingerprint

    Dive into the research topics of 'Semi-Verified PAC Learning from the Crowd'. Together they form a unique fingerprint.

    Cite this