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 学习阈值函数的设定，并在保留整体查询复杂性和运行时间的同时，可以成功地处理来自可能反对者的注释。

使用成对比较从群众中高效学习 PAC

Efficient PAC Learning from the Crowd with Pairwise Comparisons

We study the sample complexity of learning threshold functions under the
constraint of differential privacy. It is assumed that each labeled example in
the training data is the information of one individual and we would like to
come up with a generalizing hypothesis $h$ while guaranteeing differential
privacy for the individuals. Intuitively, this means that any single labeled
example in the training data should not have a significant effect on the choice
of the hypothesis. This problem has received much attention recently; unlike
the non-private case, where the sample complexity is independent of the domain
size and just depends on the desired accuracy and confidence, for private
learning the sample complexity must depend on the domain size $X$ (even for
approximate differential privacy). Alon et al. (STOC 2019) showed a lower bound
of $\Omega(\log^*|X|)$ on the sample complexity and Bun et al. (FOCS 2015)
presented an approximate-private learner with sample complexity
$\tilde{O}\left(2^{\log^*|X|}\right)$. In this work we reduce this gap
significantly, almost settling the sample complexity. We first present a new
upper bound (algorithm) of $\tilde{O}\left(\left(\log^*|X|\right)^2\right)$ on
the sample complexity and then present an improved version with sample
complexity $\tilde{O}\left(\left(\log^*|X|\right)^{1.5}\right)$.
Our algorithm is constructed for the related interior point problem, where
the goal is to find a point between the largest and smallest input elements. It
is based on selecting an input-dependent hash function and using it to embed
the database into a domain whose size is reduced logarithmically; this results
in a new database, an interior point of which can be used to generate an
interior point in the original database in a differentially private manner.

本文探讨了在差分隐私约束下学习阈值函数的样本复杂度问题，并提出了一种新的算法来减少样本复杂度。该算法基于选择输入相关哈希函数和将数据库嵌入到大小对数减小的域中，从而在不泄露个体信息的情况下生成内部点。