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.
