We study crowdsourced PAC learning of threshold functions, 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.

本文基于两种算法（一个可直接恢复出真实标签，另一个则可以在标注标签子集的情况下可靠地推断出大型实例集的真实标签）从而开发利用配对比较查询可在指数级减少标签复杂性的方法，用于众包 PAC 学习阈值函数的设定，并在保留整体查询复杂性和运行时间的同时，可以成功地处理来自可能反对者的注释。