Efficient PAC Learning from the Crowd with Pairwise Comparison

Efficient PAC learning of threshold functions is arguably one of the most important problems in machine learning. With the unprecedented growth of large-scale data sets, it has become ubiquitous to appeal to the crowd wisdom for data annotation, and the central problem that attracts a surge of recent interests is how one can learn the underlying hypothesis from the highly noisy crowd annotation while well-controlling the annotation cost. On the other hand, a large body of recent works have investigated the problem of learning with not only labels, but also pairwise comparisons, since in many applications it is easier to compare than to label. In this paper, we study the problem of PAC learning threshold functions from the crowd, where the annotators can provide (noisy) labels or pairwise comparison tags. We design a label-efficient algorithm that interleaves learning and annotation, which leads to a constant overhead of our algorithm (a notion that characterizes the query complexity). In contrast, a natural approach of annotation followed by learning leads to an overhead growing with the sample size.