# Semi-verified PAC Learning from the Crowd with Pairwise Comparisons

Shiwei Zeng
<EMAIL_ADDRESS>
Stevens Institute of Technology  Jie Shen
<EMAIL_ADDRESS>
Stevens Institute of Technology

###### Abstract

We study the problem of crowdsourced PAC learning of threshold functions with
pairwise comparisons. This is a challenging problem and only recently have
query-efficient algorithms been established in the scenario where the majority
of the crowd are perfect. In this work, we investigate the significantly more
challenging case that the majority are incorrect, which in general renders
learning impossible. 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 the correct annotation, it is possible to PAC learn the underlying
hypothesis class while drastically mitigating the labeling cost 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.

##  1 Introduction

Efficient and noise-tolerant learning of threshold functions is arguably one
of the most important problems in machine learning, and has been broadly
investigated under different noise models, such as random classification noise
[AL87], Massart noise [Slo88, MN06], Tsybakov noise [Tsy04], and agnostic
noise [Hau92, KSS92]. In recent years, under certain distributional
assumptions on the unlabeled data, a variety of computationally efficient
algorithms have been established with PAC guarantees [ZSA20, DKTZ20, DKK+20b,
ABL17]. The success of these algorithms, however, crucially relies on one or
more of the following conditions: 1) there are sufficient number of labeled
data; 2) the majority of the labels are correct; and 3) the marginal
distribution of the unlabeled data is well-behaved.

Establishing PAC guarantees without these conditions has been a long-term
research line that is of central importance from both theoretical and
practical perspectives. In particular, to move away from the first condition,
there have been a surge of recent works on learning with enriched queries; to
address the violation of the second condition, the semi-verified model (also
known as list-decodable model) has been proposed; to complement the absence of
the last condition, the crowdsourced PAC model has been put forward. We
elaborate on each line of research in the following.

Learning with enriched queries. In the data acquisition and algorithmic design
of practical machine learning systems, it is often observed that labels are
precious, while other types of information such as pairwise comparisons are
relatively easy to gather. For example, in a movie recommendation application,
it is easier for a user to tell which one of two movies she likes more than to
provide an exact rating from 1 to 10 say [PNZ+15]. This has motivated a large
body of recent studies in the context of PAC learning threshold functions with
pairwise comparisons, and one of the interesting results is that though one
cannot in general reduce the overall query complexity, it is possible to
significantly reduce the label complexity [KLMZ17, XZS+17, HKL19].

Semi-verified learning. When the majority of the labels are incorrect, it is
clear that learning becomes impossible in terms of finding the true
hypothesis. One alternative is to find a hypothesis that performs as well as
the hypothesis with best possible error rate in the given hypothesis class,
known as agnostic learning or learning with adversarial noise [Hau92, KSS92].
Another way to tackle the problem, which is more in line with this work, is to
consider that the learner has additional access to a small amount of verified
labels, known as semi-verified learning or list-decodable learning [CSV17].
Such model has been extensively studied for mean estimation, linear
regression, subspace recovery, to name a few; see [DKS18a, KKK19, CMY20,
RY20b, BK21] and the references therein.

Crowdsourced PAC learning. Generally speaking, it is computationally hard to
learn threshold functions in the presence of noise, even for the fundamental
concept of linear threshold functions [GR06, FGKP06]. Therefore, most positive
results are established under distributional assumptions on the unlabeled
data, say Gaussian or log-concave [ABL17, ZSA20, DKTZ20, DKK+20b]. Very
recently, [ABHM17, SZ20] showed that by exploring the structure of the crowd
annotations, which is often the way that learners collect labels in practice,
it is possible to PAC learn any class of threshold functions without
distributional assumptions on the unlabeled data. In addition, the two works
carried out more properties: [ABHM17] broke the second condition, that is,
their algorithm works under the semi-verified setting, whereas [SZ20] broke
the first condition, that is, their algorithm is label-efficient.

In this paper, we consider the following question:

> Can we PAC learn the class of threshold functions when all of these
> conditions are violated?

That is, the learner is assumed to have access to a small amount of labels,
and even worse, the majority of these obtained labels are incorrect. In this
case, can we still PAC learn the underlying class of threshold functions
without distributional assumptions on the unlabeled data?

We present an affirmative answer to the above question by studying a semi-
verified crowdsourced PAC learning model with pairwise comparisons and
presenting a query and label-efficient algorithm that runs in polynomial time
and enjoys PAC guarantee. In the sequel, we elaborate on the problem setup,
and in particular, on what we mean by “query-efficient” and “label-efficient”.

###  1.1 Formal setup

Let $\mathcal{X}$ be the instance space (i.e. unlabeled data),
$\mathcal{Y}=\\{-1,1\\}$ be the label space. Denote by ${D}$ the joint
distribution on $\mathcal{X}\times\mathcal{Y}$, and by ${D}_{X}$ the marginal
distribution over $\mathcal{X}$. Let
$\mathcal{F}=\\{f:\mathcal{X}\rightarrow\mathbb{R}\\}$ be the class of real-
valued functions. The class of threshold functions is given by
$\mathcal{H}=\\{h:x\mapsto\mathrm{sign}\left(f(x)\right),f\in\mathcal{F}\\}$.
For example, when $\mathcal{F}=\\{f_{w}:x\mapsto w\cdot x\\}$, $\mathcal{H}$
is the class of halfspaces, also known as linear threshold functions. We focus
on the classical realizable setting of [Val84], where there is an underlying
threshold function $h^{*}(x)=\mathrm{sign}\left(f^{*}(x)\right)$ that has zero
error on the distribution ${D}$, that is, for any $(x,y)\sim{D}$,
$y=h^{*}(x)$. For any hypothesis $h:\mathcal{X}\rightarrow\mathcal{Y}$, we
define the error rate as
$\mathrm{err}_{{D}_{X}}(h)=\Pr_{x\sim{D}_{X}}(h(x)\neq h^{*}(x))$. We are
interested in the hypothesis classes that are PAC learnable in the sense of
[Val84], which we call the standard PAC learning model. Namely,

######  Assumption 1.

There exists an efficient algorithm $\mathcal{A}_{\mathcal{H}}$ satisfying the
following: for any $\epsilon,\delta\in(0,1)$, $\mathcal{A}_{\mathcal{H}}$
draws $m_{\epsilon,\delta}$ correctly labeled instances and returns a
hypothesis $h$ such that with probability $1-\delta$,
$\mathrm{err}_{{D}_{X}}(h)\leq\epsilon$. We call $\mathcal{A}_{\mathcal{H}}$ a
standard PAC learner.

Recall that under the above standard PAC learning model, many interesting
classes such as halfspaces can be efficiently learned. In addition, it
suffices to pick

$m_{\epsilon,\delta}=K\cdot\frac{1}{\epsilon}\cdot\Big{(}d\log\frac{1}{\epsilon}+\log\frac{1}{\delta}\Big{)},$
(1.1)

where $K\geq 1$ is some absolute constant and $d$ is the VC-dimension of the
class $\mathcal{H}$ [KV94].

For any pair of instances $(x,x^{\prime})\in\mathcal{X}\times\mathcal{X}$, the
underlying comparison function is given by
$Z^{*}(x,x^{\prime})=\mathrm{sign}\left(f^{*}(x)-f^{*}(x^{\prime})\right)$.
For example, in the movie recommendation application, $f^{*}(x)$ may represent
the true preference of a user to a movie $x$, and the comparison query of “do
you like movie $x$ more than $x^{\prime}$” reads as “is
$f^{*}(x)>f^{*}(x^{\prime})$”. Note that the user can provide the answer
without having to realize the true function values. In the context of learning
with pairwise comparisons, we will need the following quantity

$n_{\epsilon,\delta}:=K\cdot\frac{1}{\epsilon}\cdot\Big{(}d\log\frac{1}{\epsilon}+\Big{(}\frac{1}{\delta}\Big{)}^{10^{-3}}\Big{)},$
(1.2)

which will characterize the sample complexity of a comparison-based algorithm.
The additive term $\big{(}\frac{1}{\delta}\big{)}^{10^{-3}}$ is due to the
fact that the failure probability of existing sorting algorithms only decays
to zero in a rate inversely polynomial in the sample size.

We study the problem of PAC learning threshold functions in the context of
crowdsourcing. The key difference from the standard PAC model is that the
learner can draw instances from ${D}_{X}$ but the labels do not come with the
instances. Rather, the learner has access to a large pool of workers and can
query a few workers on the label of an instance or a comparison tag of two
instances. We consider a fundamental crowd model that has been broadly studied
in the literature: an $\alpha$ fraction of the workers always provide the
correct label according to $h^{*}$, termed perfect workers, while the
remaining $1-\alpha$ may behave arbitrarily or even collude with each other,
termed low-quality workers. Specifically, let $\mathcal{P}^{{L}}$ be the
uniform distribution over the pool of workers who will provide labels. A
worker $t$ is defined by an annotation function
$h_{t}:\mathcal{X}\rightarrow\mathcal{Y}$. Then
$\alpha=\Pr_{t\sim\mathcal{P}^{{L}}}\big{(}\forall
x\in\mathcal{X},h_{t}(x)=h^{*}(x)\big{)}$. Likewise, denote by
$\mathcal{P}^{{C}}$ the uniform distribution over the pool of workers who will
provide comparison tags. We assume that a $\beta$ fraction of the workers
always annotate the comparison tag by $Z^{*}$, while the rest of the $1-\beta$
behave arbitrarily. Due to the presence of the low-quality workers, a common
strategy of the learner is to assign an instance (or a pair) to multiple
workers, and aggregate the results via, e.g. majority voting. This is the
approach of most crowdsourcing algorithms [HJV13, KO16]. Yet, such natural
machinery quickly breaks down when the low-quality workers form the majority,
i.e. either $\alpha$ or $\beta$ is less than $1/2$. Therefore, the learner has
to resort to a trusted expert $\mathcal{E}$ to obtain some verified queries
which are guaranteed to be correct.

The query complexity of a crowdsourced PAC learner is measured in three
aspects: the total number of label queries from the crowd which we denote by
$m_{L}$, that of comparison queries from the crowd which is denoted by
$m_{C}$, and that of verified queries from the trusted expert which is denoted
by $m_{V}$. Closely related to $m_{L}$ and $m_{C}$ are the following
quantities:
$\Lambda_{L}:=\frac{m_{L}}{m_{\epsilon,\delta}},\Lambda_{C}:=\frac{m_{C}}{m_{\epsilon,\delta}},$
termed labeling overhead and comparison overhead, respectively. These two
quantities measure the query complexity of a crowdsourced PAC learner compared
to the one needed in the standard PAC model. We say a crowdsourced PAC learner
is query-efficient if $\Lambda_{L}+\Lambda_{C}+m_{V}=O(1)$, meaning that the
overall query complexity is of the same order of the standard PAC model even
facing a large fraction of low-quality workers. We say a crowdsourced PAC
learner is label-efficient if $\Lambda_{L}=o(1)$. Our goal is to design a PAC
learning algorithm that is both query-efficient and label-efficient; in
addition, we aim to control the number of calls to the trusted expert since
otherwise the problem is trivial.

###  1.2 Main results

Our main contribution is a query and label-efficient algorithm that runs in
polynomial time and returns a hypothesis with desired PAC guarantees, even
though the majority of the annotations are incorrect and there is no
distributional assumption on the unlabeled data.

######  Theorem 1.

For any $\alpha,\beta,\epsilon,\delta\in(0,1)$, Algorithm 1 runs in
$\mathrm{poly}(d,\frac{1}{\alpha},\frac{1}{\beta},\frac{1}{\epsilon})$ time,
and with probability $1-\delta$ returns $h:\mathcal{X}\rightarrow\mathcal{Y}$
with $\mathrm{err}_{{D}_{X}}(h)\leq\epsilon$ by acquiring
$O(\frac{1}{\alpha})$ verified labels and $O(\frac{1}{\beta})$ verified
comparison tags. The label complexity is
$\frac{1}{\alpha^{2}}\big{(}\frac{1}{\alpha}+\frac{1}{\beta}\big{)}\cdot\tilde{O}\big{(}\log\frac{d+\big{(}\frac{1}{\alpha}+\frac{1}{\beta}\big{)}\frac{1}{\delta}}{\epsilon}\big{)}$,
and the comparison complexity is
$\frac{1}{\beta^{2}}\cdot\tilde{O}\big{(}\big{(}\frac{1}{\alpha}+\frac{1}{\beta}\big{)}^{\frac{1001}{1000}}\cdot\frac{d+\big{(}\frac{1}{\delta}\big{)}^{\frac{1}{1000}}}{\epsilon}\big{)}$.
Furthermore, the labeling overhead is
$o\big{(}\frac{1}{\alpha^{2}}\big{(}\frac{1}{\alpha}+\frac{1}{\beta}\big{)}\cdot\log\big{(}\frac{1}{\alpha}+\frac{1}{\beta}\big{)}\big{)}$
and the comparison overhead is
$\tilde{O}_{\delta}\big{(}\frac{1}{\beta^{2}}\big{(}\frac{1}{\alpha}+\frac{1}{\beta}\big{)}^{\frac{1001}{1000}}\big{)}$
when $\epsilon\in\left(0,(\log d)^{-4}\right)$. In particular, when $\alpha$
and $\beta$ are constants, the labeling overhead is $o(1)$, the comparison
overhead is $O_{\delta}(1)$, and the number of verified data is $O(1)$.

######  Remark 2.

This is the first label-efficient algorithm that works in the semi-verified
crowdsourced learning setting where the low-quality workers can form a strong
majority. The most important message from the theorem is that both the
overheads and the number of verified data are independent of the sample size,
meaning that the algorithm is query-efficient even for large-scale learning
problems. Moreover, this algorithm is label-efficient since $\Lambda_{L}$ may
tend to zero. Comparing to the best known algorithm of [ABHM17], which also
studies the problem of semi-verified learning from the crowd but with access
to only labels, ours requires exponentially fewer labels without sacrificing
the overall query complexity.

###  1.3 Overview of techniques

The starting point of our algorithmic design is the results from [SZ20], which
shows that if $\alpha\geq 0.7$ and $\beta\geq 0.7$, it is possible to PAC
learn any underlying class of threshold functions with $o(1)$ labeling
overhead and $O(1)$ comparison overhead. Since in the semi-verified setting,
both $\alpha$ and $\beta$ may take any value in $(0,1]$, a natural idea is to
design a mechanism to prune those low-quality workers from the pool, hence
increasing the ratio of perfect workers to $\alpha^{\prime}$ and
$\beta^{\prime}$ respectively, such that $\alpha^{\prime}\geq 0.7$ and
$\beta^{\prime}\geq 0.7$, for which the algorithm of [SZ20] can be applied.

The design of such pruning paradigm is subtle: on one hand, the verified
annotations are so powerful that if the learner had unlimited access, the
problem would become trivial; on the other hand, though low-quality workers
form the majority, there are still a non-negligible $\alpha$ fraction who are
perfect workers. Therefore, the principle of the algorithmic design is to find
good test cases that can be used to identify and prune a noticeable fraction
of low-quality workers by considering the underlying structure of the crowd;
this shares the same merit of the algorithm of [ABHM17].

Our new technical insight is a query and label-efficient win-win argument:
either some (or all) low-quality workers collude and provide incorrect
annotations, for which a noticeable fraction of them will be pruned from the
pool, or most of them provide the correct annotation. We remark that we do not
implement such a mechanism that is independent of the algorithm of [SZ20]; for
the sake of query and label efficiency, we will build upon theirs by
integrating new components. In the following, we introduce the general idea of
how to convert [SZ20] into a semi-verified learner.

Let us first consider the case that $\alpha\in(0,1]$ and $\beta\geq 0.7$. In
this scenario, for any given instance $x$, the perfect workers will provide
the correct label, say $+1$. Now we consider the behavior of the low-quality
workers: even if they collude with each other and all of them provide the
incorrect label $-1$, they can only form a majority with size at most
$1-\alpha$. Alternatively, if we observe that the majority size is greater
than this threshold, it must be the case that some perfect workers contribute
to the majority voting as well, hence the majority voting is correct. On the
flip side, if the majority size is less than $1-\alpha$, we can request a
verified label, and can prune at least $\alpha$ fraction of workers (since at
least $\alpha$ fraction are incorrect). We note that in the algorithmic
design, we only draw a small set of worker for the sake of query efficiency,
hence we use an empirical majority size threshold $1-\frac{\alpha}{4}$ as a
proxy to the population majority size. After one of such pruning step, the
ratio of perfect workers will increase to $\frac{\alpha}{1-\alpha/4}$. It is
possible to show that with $O(\frac{1}{\alpha})$ steps, the perfect workers
will form the majority. During the course of pruning, another important aspect
that we need to take into account is the labeling and comparison overhead.
Since $\beta\geq 0.7$, the comparison-based labeling scheme of [SZ20] can
faithfully sort an instance set; this combined with the pruning step suffices
to ensure the PAC guarantee and overhead bound.

We next consider that both $\alpha$ and $\beta$ are in $(0,1]$. There are two
technical challenges now. First, the comparison-based labeling scheme of
[SZ20] fails immediately. However, this can be easily fixed since we can apply
the above pruning paradigm on the comparison tags. The more serious issue with
$\beta<\frac{1}{2}$ roots in their filtering process, which roughly speaking,
will perform majority voting over a constant number of workers. In this
regard, an empirical majority size may deviate far from the population one,
thus the pruning fails. We also note that if we were to increase the constant
number, we would suffer high query complexity. We thus develop a new testing
stage that samples a large enough set of test cases and query the crowd for
their majority size. If less than an $\epsilon$ fraction of the test cases
have majority size $<1-\alpha$, we can show that the total fraction of such
test cases in the underlying distribution ${D}_{X}$ is smaller than
$\epsilon$, hence the filtering process correctly filters all the desired
instances except for an $\epsilon$ fraction; this is sufficient to establish a
robust version of the performance guarantee.

###  1.4 Roadmap

In Section 2, we describe the related works. Section 3 gives additional
background and notations in crowdsourced PAC learning. In Section 4, we
present our main algorithm and its theoretical guarantees. The conclusion is
given in Section 5, and the proof details are deferred to the appendix.

##  2 Related Works

This work falls into the broad intersection of label-efficient learning, semi-
verified learning, and crowdsourced PAC learning. We describe some important
related works.

Label-efficient learning roots in the practical challenge of gathering high-
quality labels, especially for some domains such as medical diagnosis. There
are a few techniques to mitigate the labeling cost, such as active learning
and learning with enriched queries. Generally speaking, the main idea of
active learning is to start off with a coarse hypothesis, and uses the current
hypothesis to select certain informative instances to label [CAL94]. While
this shares the spirit of the boosting technique that will be used to build
our algorithm, the procedures are quite different as active learning
algorithms often need to proceed and refine the hypothesis for many iterations
[BBZ07, Han14, ABL17]. Another approach is to presenting more easily obtained
queries to the annotators, among which pairwise comparison has been widely
believed as a natural alternative. In fact, such query type has been
extensively investigated in ranking [JN11, SBGW16, SW17, FHO+17, SBW19,
AAKP20], best-$k$ item selection [FHO+17, RLS20], and recommendation systems
[FH10, FJO+18]. More in line with this work is PAC learning with pairwise
comparisons [KLMZ17, XZS+17, HKL19, HKLM20]; yet, the way that we utilize
comparison queries is quite different from these works and their guarantees
were established under the non-crowdsourcing model.

The semi-verified learning model was recently proposed in [CSV17], in order to
study the robustness of learning algorithms in the presence of large portion
of noisy data. This model is also known as list-decodable learning where a
learner is allowed to output a finite list of hypotheses among which at least
one is guaranteed to be close to the true hypothesis. Such model has been
broadly studied under the non-crowdsourcing setting for various problems such
as mean estimation [KS17, DKK20a, RY20a], learning mixtures of Gaussian
[DKS18b], linear regression [KKK19, RY20a], and subspace recovery [BK20,
RY20b]. Under the crowdsourcing setting, [SVC16, MV18] considered recovery of
true values of a finite data set and [ABHM17] examined PAC learnability which
aligns more closely with our work. In fact, our algorithm shares the merits
with [ABHM17] but we carefully leverage comparison queries to achieve label
efficiency. We emphasize that crowdsourced PAC learning was also investigated
in [SZ20], but their algorithm fails immediately when the majority are
incorrect.

##  3 Preliminaries

Crowdsourced PAC learning. The key difference between crowdsourced PAC
learning and non-crowdsourced one is how the learner gathers the label. Under
the non-crowdsourced PAC model, the sample generation oracle first randomly
draws $(x,y)\sim{D}$, and returns the labeled instance under the passive
learning setting or returns only the instance $x$ under the active learning
setting. In the latter case, the learner may additionally call a label
revealing oracle to obtain the label but no matter how many times the learner
makes the call, the label is persistent [CAL94]. Under the crowdsourced PAC
model, the learner only has access to an oracle who can draw instances from
${D}_{X}$. In order to obtain the labels, the learner may assign each instance
$x$ to $k$ workers to gather a collection of annotations $h_{1}(x),\dots
h_{k}(x)$, and may use e.g. majority voting as the final label of $x$.
Therefore, in addition to PAC guarantee, another very important evaluation
metric of a crowdsourced PAC learning algorithm is the query complexity,
namely, the label and comparison queries made to the crowd workers as well as
to the trusted expert.

Given an input $z$ and a set of workers $\mathcal{W}$, we define
$\mathrm{Maj}_{\mathcal{W}}(z)$ to be the majority vote over the annotations
from the workers in $\mathcal{W}$, where $z$ can either be an instance or a
pair of instances. We denote by $\mathrm{Maj{\mathchar
45\relax}size}_{\mathcal{W}}(z)$ the fraction of the workers in $\mathcal{W}$
that agree with $\mathrm{Maj}_{\mathcal{W}}(z)$, which is referred to as the
empirical majority size. Similarly, we can consider the population version
$\mathrm{Maj{\mathchar
45\relax}size}_{\mathcal{P}}(z)=\max\\{\Pr_{t\sim\mathcal{P}}(h_{t}(z)=1),\Pr_{t\sim\mathcal{P}}(h_{t}(z)=-1)\\}$.
Specifically, let $h_{1}$, $h_{2}$ and $h_{3}$ be three classifiers. The
function $\mathrm{Maj}(h_{1},h_{2},h_{3})$ maps any instance $x$ to the label
$y=\mathrm{Maj}_{h_{1},h_{2},h_{3}}(x)$.

Given a distribution $\mathcal{P}$ over workers and an annotated set $S$
(either a set with labels or one with comparison tags), denote by
$\mathcal{P}_{\mid S}$ the distribution $\mathcal{P}$ conditioned on workers
that agree with the annotations in $S$; this will be useful to prune the low-
quality workers. Given any region $R\subseteq\mathcal{X}$, denote by ${D}[R]$
the density of instances $x\in R$ in distribution ${D}$.

##  4 Main Algorithm and Theoretical Guarantees

We first summarize the main idea of existing crowdsourced PAC learning
algorithms, and elaborate on why they break down to provide query and label-
efficient PAC guarantees in the presence of overwhelming number of low-quality
workers. Then we propose our robust algorithm that induces a win-win result,
along with theoretical guarantees.

1

2

3

40: Parameters $\alpha,\beta$, distributions $\mathcal{P}^{{L}}$ and
$\mathcal{P}^{{C}}$, target error rate $\epsilon$, confidence $\delta$, a
standard PAC learner $\mathcal{A}_{\mathcal{H}}$.

50: Hypothesis $\hat{h}:\mathcal{X}\rightarrow\mathcal{Y}$.

61: $\tau\leftarrow\frac{8}{\alpha}+\frac{8}{\beta}$,
$\delta^{\prime}\leftarrow\frac{\delta}{\tau}$.

7Phase 1:

82: $\overline{S_{1}}\leftarrow\textsc{Prune-Compare-and-
Label}(S_{1},\alpha,\beta,\frac{\delta^{\prime}}{6})$, for an instance set
$S_{1}$ of size $n_{\sqrt{\epsilon}/2,\delta^{\prime}/6}$ from ${{D}_{X}}$.

93:
$h_{1}\leftarrow\mathcal{A}_{\mathcal{H}}(\overline{S_{1}},\frac{\sqrt{\epsilon}}{2},\frac{\delta^{\prime}}{6})$.

10Phase 2:

114: ${S_{I}}\leftarrow\textsc{Semi-verified-
Filter}(S_{2},h_{1},\alpha,\beta,\frac{\delta^{\prime}}{12})$, for an instance
set $S_{2}$ of size $\Theta(n_{\epsilon,\delta^{\prime}/12})$ drawn from
${{D}_{X}}$.

125: Let $S_{C}$ be an instance set of size
$\Theta(n_{\sqrt{\epsilon},\delta^{\prime}/12})$ drawn from ${{D}_{X}}$.

136: $\overline{S_{\text{All}}}\leftarrow\textsc{Prune-Compare-and-
Label}(S_{I}\cup S_{C},\alpha,\beta,\delta^{\prime}/12)$.

147: $\overline{W_{I}}\leftarrow\\{(x,y)\in\overline{S_{\text{All}}}\mid y\neq
h_{1}(x)\\}$,
$\overline{W_{C}}\leftarrow\overline{S_{\text{All}}}\backslash\overline{W_{I}}$.

158: Draw a sample set $\overline{W}$ of size
$\Theta(n_{\sqrt{\epsilon}/2,\delta^{\prime}/12})$ from a distribution that
equally weights $\overline{W_{I}}$ and $\overline{W_{C}}$.

169:
$h_{2}\leftarrow\mathcal{A}_{\mathcal{H}}(\overline{W},\frac{\sqrt{\epsilon}}{2},\frac{\delta^{\prime}}{6})$.

17 Phase 3:

1810: $\overline{S_{3}}\leftarrow\textsc{Prune-Compare-and-
Label}(S_{3},\alpha,\beta,\delta^{\prime}/6)$, for an instance set $S_{3}$ of
size $n_{\sqrt{\epsilon}/2,\delta^{\prime}/6}$ drawn from ${{D}_{X}}$
conditioned on $h_{1}(x)\neq h_{2}(x)$.

1911:
$h_{3}\leftarrow\mathcal{A}_{\mathcal{H}}(\overline{S_{3}},\frac{\sqrt{\epsilon}}{2},\frac{\delta^{\prime}}{6})$.

20return $\hat{h}\leftarrow\mathrm{Maj}(h_{1},h_{2},h_{3})$.

Algorithm 1 Main Algorithm

###  4.1 Overview

Our main algorithm follows the same pipeline of existing crowdsourced PAC
learning algorithms of [ABHM17, SZ20]. The key idea is to gather sufficient
number of correctly labeled instances from the crowd, thus reducing the
problem to standard PAC learning for which a standard PAC learner
$\mathcal{A}_{\mathcal{H}}$ can be used to produce the desired hypothesis
without distributional assumptions on the instances. For the sake of query
efficiency, however, a boosting framework of [Sch90] was utilized.

######  Theorem 3 ([Sch90]).

For any $p<\frac{1}{2}$ and distribution ${D}_{X}$, consider three classifiers
$h_{1}(x)$, $h_{2}(x)$, $h_{3}(x)$ satisfying the following. 1)
$\mathrm{err}_{{D}_{X}}(h_{1})\leq p$; 2) $\mathrm{err}_{{D}_{2}}(h_{2})\leq
p$ where ${D}_{2}:=\frac{1}{2}{D}_{C}+\frac{1}{2}{D}_{I}$, ${D}_{C}$ denotes
the distribution ${D}_{X}$ conditioned on $\\{x:h_{1}(x)=h^{*}(x)\\}$, and
${D}_{I}$ denotes ${D}_{X}$ conditioned on $\\{x:h_{1}(x)\neq h^{*}(x)\\}$; 3)
$\mathrm{err}_{{D}_{3}}(h_{3})\leq p$ where ${D}_{3}$ is ${D}_{X}$ conditioned
on $\\{x:h_{1}(x)\neq h_{2}(x)\\}$. Then
$\mathrm{err}_{{D}_{X}}(\mathrm{Maj}(h_{1},h_{2},h_{3}))\leq 3p^{2}-2p^{3}$.

In particular, by choosing $p=\frac{\sqrt{\epsilon}}{2}$ in the above theorem,
we can further reduce the problem to learning three weak hypotheses each of
which has error rate $\frac{\sqrt{\epsilon}}{2}$. Note that for each
hypothesis to be learned, by Assumption 1, it suffices to acquire
$m_{\sqrt{\epsilon},\delta}$ correctly labeled instances, which is lower than
the $m_{\epsilon,\delta}$ labels for learning without boosting. Of course,
such improvement does not come for free: the learner must draw instances from
three different distributions, and the main challenge boils down to a query
and label-efficient paradigm for such sampling scheme.

To this end, [SZ20] leveraged pairwise comparisons in two important ways: 1) a
comparison-based labeling scheme for small instance sets which sorts unlabeled
instances using comparison queries and then applies binary search with label
queries to annotate the entire data set; 2) a label-efficient filtering
process for large instance sets which uses a constant number of comparison
queries on most of the instances along with a few label queries to infer the
correct label of all instances. Technically speaking, the success of the two
components crucially hinges on the correctness of majority voting. Now, in the
presence of overwhelming number of low-quality workers, they can collude to
push the majority vote towards the incorrect annotation, making these
approaches break down immediately.

Our main technical contributions fall into the design of robust version of the
two components, which we term Prune-Compare-and-Label and Semi-verified-Filter
respectively. By integrating these two robust components into the boosting
framework, we obtain our main algorithm, Algorithm 1. Our key observation is
generally the following: for any instance $x$, even if all the low-quality
workers collude and provide the incorrect annotation, they can form a majority
size at most $\mathrm{Maj{\mathchar
45\relax}size}_{\mathcal{P}^{{L}}}(x)=1-\alpha$, since the perfect workers
will provide correct labels which consist of $\alpha$ fraction. Thus, if
$\mathrm{Maj{\mathchar 45\relax}size}_{\mathcal{P}^{{L}}}(x)>1-\alpha$, this
indicates that there must be some perfect workers that contribute to the
majority size, hence the majority voting must be correct. Otherwise, we can
always request a verified label and prune at least $\alpha$ fraction of
workers who must be low-quality. We will then restart the main algorithm with
the new pool of workers. In the practical algorithmic design, the learner only
has access to an empirical majority size. It is not hard to see that as long
as we choose a set $\mathcal{W}$ of $O(\frac{1}{\alpha^{2}}\log\left\lvert
S\right\rvert)$ workers for some instance set $S$ in question, the empirical
majority size is close enough to the population one. The same idea can be
applied to pairwise comparison query as well, with the parameter $\alpha$
being replaced by $\beta$. We note that whenever querying the crowd, we can
always check such condition on majority size until the perfect workers form a
majority size, say $70\%$, or most low-quality workers are forced to annotate
correctly.

The above is indeed a win-win result in a strong sense: either they do not
agree with the perfect workers, for which they will be pruned from the pool;
or they annotate correctly, for which we can safely take the majority vote.

Such pruning idea works when for each instance in a given set $S$, the learner
is allowed to draw a set of $O(\frac{1}{\alpha^{2}}\log\log\left\lvert
S\right\rvert)$ workers for labeling (respectively,
$O(\frac{1}{\beta^{2}}\log\left\lvert S\right\rvert)$ for comparison). When
$\left\lvert S\right\rvert=O(n_{\sqrt{\epsilon},\delta})$, we can well control
the query complexity; this gives our new algorithm Prune-Compare-and-Label
(Algorithm 2), which consists of a semi-verified version of Quicksort
(Algorithm 3) and binary search (Algorithm 4).

However, it will be a trouble when $\left\lvert
S\right\rvert=\Theta(n_{\epsilon,\delta})$. In particular, if we were to
perform $\Theta(\left\lvert S\right\rvert)$ pairwise comparisons, then the
total comparison complexity would be $O(\frac{1}{\beta^{2}}\cdot
n_{\epsilon,\delta}\log n_{\epsilon,\delta})$, which would resulted in a
comparison overhead $m_{C}=O_{\delta}(\frac{1}{\beta^{2}}\log
n_{\epsilon,\delta})$ which grows with the sample size $n_{\epsilon,\delta}$.
Unfortunately, such situation indeed occurs in the algorithm of [SZ20], in
particular, their filtering algorithm. Since lowering the size of workers will
deviate our estimate of the population majority size, we have to design a new
approach, which is termed Semi-verified-Filter (Algorithm 5). Here, the
primary idea is to sample a moderate set of instances and prune sufficient
number of the low-quality workers such that the density of instances where the
majority size is less than $1-\beta$ is small. Technically speaking,
throughout the course of Semi-verified-Filter, the vast amount of comparison
queries are requested in the for-loop (Step 11). A notable feature of the
algorithm is that both $x^{-}$ and $x^{+}$ are fixed. Thus, we only need to
check the density of the two regions:

$\displaystyle R_{1}:=\\{x:\mathrm{Maj{\mathchar
45\relax}size}_{\mathcal{P}^{{C}}}(x,x^{-})\leq 1-\frac{\beta}{2}\\},$ (4.1)
$\displaystyle R_{2}:=\\{x:\mathrm{Maj{\mathchar
45\relax}size}_{\mathcal{P}^{{C}}}(x,x^{+})\leq 1-\frac{\beta}{2}\\};$ (4.2)

this is exactly the purpose of invoking Test (Algorithm 6) at Step 6 of Semi-
verified-Filter.

###  4.2 Prune-Compare-and-Label

1

2

3

0: An instance set $S$, parameters $\alpha$, $\beta$, $\delta_{1}$.

40: A sorted and labeled set $\overline{S}$.

51: $\hat{S}\leftarrow\textsc{Semi-verified-Quicksort}(S,\beta,\delta_{1})$.

62: $\overline{S}\leftarrow$ Semi-verified-
BinarySearch$(\hat{S},\alpha,\delta_{1})$.

7return $\overline{S}$.

Algorithm 2 Prune-Compare-and-Label

1

2

3

0: An instance set $S=\\{x_{i}\\}_{i=1}^{n}$, $\beta$, $\delta_{1}$.

40: A sorted list $\hat{S}$.

51: $k_{1}\leftarrow\frac{1}{2\beta^{2}}\cdot\log\frac{3006n\cdot\log
n}{\delta_{1}}$.

62: Apply randomized Quicksort to $S$ tailored to semi-verified learning: for
each pair $(x,x^{\prime})$ being compared, draw a set of $k_{1}$ workers
$\mathcal{W}^{{C}}$ from $\mathcal{P}^{{C}}$ and do the following:

3: if $\beta\geq 0.7$ or $\mathrm{Maj{\mathchar
45\relax}size}_{\mathcal{W}^{{C}}}(x,x^{\prime})\geq 1-\frac{\beta}{4}$ then

4: Use $\mathrm{Maj}_{\mathcal{W}^{{C}}}(x,x^{\prime})$ as the comparison tag.

5: else

6: Get a verified comparison tag $z^{*}\leftarrow Z^{*}(x,x^{\prime})$.
Restart Algorithm 1 with
$\mathcal{P}^{{C}}\leftarrow\mathcal{P}^{{C}}_{\mid(x,x^{\prime},z^{*})}$ and
$\beta\leftarrow\frac{\beta}{1-\frac{\beta}{8}}$.

77: end if

8return $\hat{S}$.

Algorithm 3 Semi-Verified-Quicksort

1

2

0: A sorted instance set $\hat{S}=\\{\hat{x}_{i}\\}_{i=1}^{n}$, $\alpha$,
$\delta_{1}$.

30: A labeled set $\overline{S}$.

41: $t_{\min}\leftarrow 1$, $t_{\max}\leftarrow n$,
$k_{2}\leftarrow\frac{32}{\alpha^{2}}\log\frac{6\log n}{\delta_{1}}$.

2: while $t_{\min}<t_{\max}$ do

3: $t=(t_{\min}+t_{\max})/2$.

54: Draw a set of $k_{2}$ workers $\mathcal{W}^{{L}}$ from
$\mathcal{P}^{{L}}$.

5: if $\alpha\geq 0.7$ or $\mathrm{Maj{\mathchar
45\relax}size}_{\mathcal{W}^{{L}}}({x}_{t})\geq 1-\frac{\alpha}{4}$ then

6: $\hat{y}_{t}\leftarrow\mathrm{Maj}_{\mathcal{W}^{{L}}}(x_{t})$.

7: If $\hat{y}_{t}=1$, then $t_{\max}\leftarrow t-1$; else $t_{\min}\leftarrow
t+1$.

8: else

9: Get a verified label $y_{t}^{*}\leftarrow h^{*}(x_{t})$. Restart Algoirthm
1 with
$\mathcal{P}^{{L}}\leftarrow\mathcal{P}^{{L}}_{\mid({x}_{t},y_{t}^{*})}$ and
$\alpha\leftarrow\frac{\alpha}{1-\frac{\alpha}{8}}$.

610: end if

11: end while

12: For all $t^{\prime}>t,\hat{y}_{t^{\prime}}\leftarrow+1$.

713: For all $t^{\prime}<t,\hat{y}_{t^{\prime}}\leftarrow-1$.

8return
$\overline{S}=\\{(\hat{x}_{1},\hat{y}_{1}),(\hat{x}_{2},\hat{y}_{2}),\dots,(\hat{x}_{m},\hat{y}_{m})\\}$.

Algorithm 4 Semi-Verified-BinarySearch

Similar to prior comparison-based PAC learning algorithms [XZS+17], the
primitive in our algorithm that ensures label efficiency is a “compare and
label” approach, which first sorts all the instances in a set $S$ and then
query the label of the instances during binary search. In the non-crowdsourced
setting, [XZS+17] assumes comparison and labeling error rate as small as
$\epsilon$ to guarantee the success, while the crowdsourced learner of [SZ20]
assumes the correctness of the majority of the crowd. We fortify the latter by
adding certain conditions to ensure that the majority vote is always correct
(with high probability).

Specifically, as we discussed before, if the population majority size
$\mathrm{Maj{\mathchar
45\relax}size}_{\mathcal{P}^{{C}}}(x,x^{\prime})>1-\beta$, then it must be the
case that some perfect workers agree with the majority vote (since the low-
quality workers themselves can only form a majority size at most $1-\beta$);
this implies the correctness of
$\mathrm{Maj}_{\mathcal{P}^{{C}}}(x,x^{\prime})$. By the Chernoff bound, we
can show that by drawing $O(\frac{1}{\beta^{2}}\log\left\lvert S\right\rvert)$
workers, the empirical majority size will be a faithful estimate of the
population one, though the condition becomes $\mathrm{Maj{\mathchar
45\relax}size}_{\mathcal{W}^{{C}}}(x,x^{\prime})\geq 1-\frac{\beta}{4}$ which
is up to a constant scaling of $\beta$. Note that when the condition is
violated, we need to request a verified comparison tag from the trusted
expert, and can prune at least $\frac{\beta}{4}$ fraction of workers who are
low-quality; this improves the population of perfect workers. Likewise, during
binary search, we can check the majority size of the labels from the crowd,
which either allows us to obtain a correct majority vote or to prune a
noticeable fraction of low-quality workers.

Observe that if we were to query a verified label/comparison whenever the
workers in $\mathcal{W}$ do not fully agree, we would always prune a few low-
quality workers, say $\epsilon$ fraction. However, this results in query
inefficiency since such method does not take into account the underlying
structure of the crowd. We summarize the performance guarantees of both
algorithms below.

######  Lemma 4.

Consider the Semi-verified-Quicksort algorithm. Given any set of instances
$S$, with probability $1-\frac{2\delta_{1}}{3}$, the algorithm either
increases the fraction of perfect workers from $\beta$ to
$\frac{\beta}{1-\frac{\beta}{8}}$, or correctly sorts $S$.

######  Lemma 5.

Consider the Semi-verified-BinarySearch algorithm. Suppose that $\hat{S}$ is
correctly sorted. With probability $1-\frac{\delta_{1}}{3}$, the algorithm
either increases the fraction of perfect workers from $\alpha$ to
$\frac{\alpha}{1-\frac{\alpha}{8}}$, or correctly labels $\hat{S}$, namely,
for all $(x,y)\in\overline{S}$, $y=h^{*}(x)$.

We further note that comparing to the non-robust version, Prune-Compare-and-
Label does not require extra crowd labels or comparison tags to label $S$,
because once it decides to query the verified data, it will end up restarting
the main algorithm. Thus, the label and comparison complexity of Prune-
Compare-and-Label matches that of the non-robust counterpart in [SZ20].

######  Proposition 6.

Consider the Prune-Compare-and-Label algorithm, i.e. Algorithm 2. If the
algorithm does not restart and $\left\lvert
S\right\rvert\geq(\frac{1}{\delta_{1}})^{1/1000}$ , then with probability
$1-\delta_{1}$, it correctly sorts and labels all the instances in $S$ with
$O(\frac{1}{\alpha^{2}}\cdot\log\log\left\lvert S\right\rvert)$ label queries
and $O(\frac{1}{\beta^{2}}\cdot\left\lvert
S\right\rvert\cdot\log^{2}\left\lvert S\right\rvert)$ comparison tags.

In light of Theorem 3, $h_{1}$ and $h_{3}$ are trained on two distributions
${D}_{X}$ and ${D}_{3}$ which are not hard to construct if $h_{2}$ is given:
${D}_{X}$ is the original marginal distribution, and ${D}_{3}$ can be obtained
by rejection sampling. By Assumption 1, drawing a sample of
$\Theta(n_{\sqrt{\epsilon},\delta^{\prime}})$ instances on each distribution
respectively and feeding them to $\mathcal{A}_{\mathcal{H}}$ induces the
following corollaries on the performance of $h_{1},h_{3}$.

######  Corollary 7.

With probability $1-\frac{\delta^{\prime}}{3}$,
$\mathrm{err}_{{D}_{X}}(h_{1})\leq\frac{\sqrt{\epsilon}}{2}$.

######  Corollary 8.

With probability $1-\frac{\delta^{\prime}}{3}$,
$\mathrm{err}_{{D}_{3}}(h_{3})\leq\frac{\sqrt{\epsilon}}{2}$.

###  4.3 Semi-verified-Filter

1

0: Set of instances $S$, classifier $h$ with error
$\mathrm{err}_{{D}}(h)\in\big{[}\frac{\sqrt{\epsilon}}{6},\frac{\sqrt{\epsilon}}{2}\big{]}$,
confidence $\delta_{2}$, parameters $\alpha,\beta$.

20: The set $S_{I}$ whose instances are misclassified by $h$.

31:
$b\leftarrow\frac{4}{\sqrt{\epsilon}}\log\frac{16}{\delta_{2}}+(\frac{24}{\delta_{2}})^{1/1000}$.

42: Sample uniformly a subset $U\subset S$ of $b$ instances.
$\overline{U}\leftarrow\textsc{Prune-Compare-and-
Label}(U,\alpha,\beta,\delta_{2}/4)$.

53: Let $x^{-}$ be the rightmost instance of those labeled as $-1$, and
$x^{+}$ be the leftmost instance of those labeled as $+1$.

64: $S_{I}\leftarrow\emptyset$, $S_{\text{in}}\leftarrow\emptyset$,
$N\leftarrow\frac{1}{\beta^{2}}\log\frac{1}{\epsilon}$.

5: if $\beta<0.7$ then

6: Run Test $(x^{-},\beta,\delta_{2}/8)$, Test $(x^{+},\beta,\delta_{2}/8)$.

77: end if

88: for $x\in S\backslash U$ do

99: $\text{ANS}\leftarrow\text{YES}$.

1010: for $t=1,\dots,N$ do

1111: Draw a worker $t\sim\mathcal{P}^{{C}}$ to obtain the comparison tag
$Z_{t}(x,x^{-})$. If $Z_{t}(x,x^{-})=\\{x<x^{-}\\}$, then
$Z_{t}(x,x^{+})\leftarrow\\{x<x^{+}\\}$, else query $Z_{t}(x,x^{+})$.

1212: If $t$ is even, then continue to the next iteration.

1313: Filtering: If $\big{[}\mathrm{Maj}(Z_{1:t}(x,x^{-}))=\\{x<x^{-}\\}$ and
$h(x)=-1\big{]}$ or $\big{[}\mathrm{Maj}(Z_{1:t}(x,x^{+}))=\\{x>x^{+}\\}$ and
$h(x)=1\big{]}$, then $\text{ANS}\leftarrow\text{NO}$ and break.

1414: end for

1515: If $\mathrm{Maj}\big{(}Z_{1:N}(x,x^{-})\big{)}=\\{x>x^{-}\\}$ and
$\mathrm{Maj}\big{(}Z_{1:N}(x,x^{+})\big{)}=\\{x<x^{+}\\}$ then
$\text{ANS}\leftarrow\text{NO}$ and $S_{\text{in}}\leftarrow
S_{\text{in}}\cup\\{x\\}$.

1616: If $\text{ANS}=\text{YES}$, then $S_{I}\leftarrow S_{I}\cup\\{x\\}$.

1717: end for

1818: $\overline{S_{\text{in}}}\leftarrow\textsc{Prune-Compare-and-
Label}(S_{\text{in}},\delta_{2}/4,\alpha,\beta)$.

1919: $S_{I}\leftarrow
S_{I}\cup\\{x:(x,y)\in\overline{U}\cup\overline{S_{\text{in}}}\ \text{and}\
y\neq h(x)\\}$.

20return $S_{I}$.

Algorithm 5 Semi-verified-Filter

As we introduced before, except for an efficient labeling scheme, it is of the
same importance to have a query and label-efficient filtering process, which
is for an accurate simulation of ${D}_{2}$ over which $h_{2}$ is trained. This
is the most challenging part because it requires identifying the instances
where $h_{1}$ is incorrect. To keep it label-efficient, the filtering scheme
incorporates an similar idea to that in “compare-and-label”. Given a large
enough sample set $S$, the goal is to identify two support instances
$x^{-},x^{+}$ that are close enough to the “threshold instance” where the
labels in $S$ shift. If we spend a few label queries to infer the labels of
$x^{-},x^{+}$, then they help to filter a large number of instances in $S$ by
querying pairwise comparisons. This is because for any $x$,
$[h^{*}(x^{-})=-1,x<x^{-}]$ imply $h^{*}(x)=-1$ (similar holds for $x^{+}$).
The pairwise comparisons of any other instance with $x^{-},x^{+}$ become
exceptionally informative. On the other hand, since the aim is to identify
those instances where $h_{1}$ is incorrect (which form only a
$\frac{\sqrt{\epsilon}}{2}$ fraction in $S$), another key point is an adaptive
querying scheme that spends only a constant number of queries on the points
that $h_{1}$ may correctly classify.

We thus build on the non-semi-verified filter of [SZ20] and integrate a new
component, Test, that ensures to recover a distribution ${D}^{\prime}$ that is
close enough to ${D}_{2}$ even in presence of a large number of low-quality
workers. To see the necessity of this new component, we remark it is crucial
to query a constant number of workers for most instances in $S$ to ensure
query complexity since $\left\lvert
S\right\rvert=\Theta(n_{\epsilon,\delta})$. This constant load, however,
contradicts with the sample-size-varying load we used in Prune-Compare-and-
Label; in other words, the empirical majority size no longer serves as a good
estimate of the population one. To tackle this technical challenge, we are
concerned with two regions, $R_{1}$ and $R_{2}$ (recall the definition at the
end of Section 4.1), which, by definition, include the instances $x$ that
would form a low-confidence pair with either support instance $x^{-}$ or
$x^{+}$. Observe that both $x^{-},x^{+}$ are fixed. If the density of $R_{1}$
and $R_{2}$ in distribution ${D}_{X}$ is smaller than $\epsilon$, it means the
filter uses $x^{-},x^{+}$ to correctly identify the instances except for an
$\epsilon$ fraction. Meanwhile, Test works on a set of instances that is
smaller than that Semi-verified-Filter works on. This is a key design to
guarantee that the total comparison complexity does not blow up.

1

2

3

40: An instance $x^{\prime}$, parameter $\beta$, confidence $\delta_{2}$.

51: Draw a set $S_{r}$ of $\frac{4}{\epsilon}\log\frac{8}{\delta_{2}}$
instances from ${D}_{X}$.

62: $N\leftarrow\frac{32}{\beta^{2}}\cdot\log(\frac{32\left\lvert
S_{r}\right\rvert}{\delta_{2}})$.

73: for $x\in S_{r}$ do

84: Draw a set of $N$ workers $\mathcal{W}$ from $\mathcal{P}^{{C}}$ and
obtain the comparison tags on $(x,x^{\prime})$.

95: if $\mathrm{Maj{\mathchar
45\relax}size}_{\mathcal{W}}(x,x^{\prime})<1-\frac{\beta}{4}$ then

6: Get a verified comparison tag $z^{*}\leftarrow Z^{*}(x,x^{\prime})$.

107: Restart Algorithm 1 with
$\mathcal{P}^{{C}}\leftarrow\mathcal{P}^{{C}}_{\mid(x,x^{\prime},z^{*})}$ and
$\beta\leftarrow\frac{\beta}{1-\frac{\beta}{8}}$.

8: end if

9: end for

Algorithm 6 Test

######  Lemma 9.

If Test terminates without restarting Algorithm 1, we have the density
${D}_{X}[R_{1}\cup R_{2}]\leq\frac{\epsilon}{4}$ with probability
$1-\frac{\delta_{2}}{4}$. In addition, the comparison complexity of Test is
$O\big{(}\frac{1}{\epsilon\beta^{2}}\log\big{(}\frac{1}{\delta_{2}}\big{)}\log\big{(}\frac{1}{\epsilon\delta_{2}}\big{)}\big{)}$.

In general, Semi-verified-Filter ensures that in Phase 2, the learner draws a
set of $\Theta(n_{\sqrt{\epsilon},\delta^{\prime}})$ instances from a
distribution ${D}^{\prime}$ that is $\frac{\sqrt{\epsilon}}{2}$-close to
${D}_{2}$, which suffice to learn a hypothesis $h_{2}$ with
$\mathrm{err}_{{D}_{2}}(h_{2})\leq\frac{\sqrt{\epsilon}}{2}$. Therefore, we
have the following guarantee.

######  Lemma 10.

Consider Phase 2 of Algorithm 1, with probability
$1-\frac{\delta^{\prime}}{3}$,
$\mathrm{err}_{{D}_{2}}(h_{2})\leq\frac{\sqrt{\epsilon}}{2}$.

By Corollaries 7, 8, and the above lemma, we have three hypotheses
$h_{1},h_{2},h_{3}$ that satisfy the requirement of Theorem 3; this suffices
to produce a hypothesis $\hat{h}$ with the desired PAC guarantee. We further
note that each verified label/comparison helps to prune a significant fraction
of the low-quality workers but not the perfect workers, resulting in the upper
bounds on the number of verified data and total restarts of the main
algorithm. Hence, our main theorem, Theorem 1 follows; see Appendix A for the
full proof.

##  5 Conclusion and Future Works

We have presented a query and label-efficient algorithm that learns an unknown
threshold function without distributional assumptions on the unlabeled data,
via exploiting the wisdom of the crowd. Under the semi-verified learning
model, we provided novel techniques that efficiently prune low-quality workers
even they are the majority by acquiring only a constant number of verified
data. This yields a strong query and label-efficient win-win argument. It is
interesting to consider semi-verified learning without perfect workers, under
which we may have to design a more involved pruning algorithm. It would also
be interesting to design task-independent pruning paradigms, or consider other
query types or combining the current framework with active learning techniques
to achieve label efficiency.

## References

  * [AAKP20] Arpit Agarwal, Shivani Agarwal, Sanjeev Khanna, and Prathamesh Patil.  Rank aggregation from pairwise comparisons in the presence of adversarial corruptions.  In Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pages 85–95. PMLR, 2020.
  * [ABHM17] Pranjal Awasthi, Avrim Blum, Nika Haghtalab, and Yishay Mansour.  Efficient PAC learning from the crowd.  In Satyen Kale and Ohad Shamir, editors, Proceedings of the 30th Annual Conference on Learning Theory, pages 127–150, 2017.
  * [ABL17] Pranjal Awasthi, Maria-Florina Balcan, and Philip M. Long.  The power of localization for efficiently learning linear separators with noise.  Journal of the ACM, 63(6):50:1–50:27, 2017.
  * [AL87] Dana Angluin and Philip D. Laird.  Learning from noisy examples.  Machine Learning, 2(4):343–370, 1987.
  * [BBZ07] Maria-Florina Balcan, Andrei Z. Broder, and Tong Zhang.  Margin based active learning.  In Proceedings of the 20th Annual Conference on Learning Theory, pages 35–50, 2007.
  * [BK20] Ainesh Bakshi and Pravesh Kothari.  List-decodable subspace recovery via sum-of-squares.  CoRR, abs/2002.05139, 2020.
  * [BK21] Ainesh Bakshi and Pravesh K. Kothari.  List-decodable subspace recovery: Dimension independent error in polynomial time.  In Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, pages 1279–1297, 2021.
  * [CAL94] David Cohn, Les Atlas, and Richard Ladner.  Improving generalization with active learning.  Machine Learning, 15(2):201–221, 1994.
  * [CMY20] Yeshwanth Cherapanamjeri, Sidhanth Mohanty, and Morris Yau.  List decodable mean estimation in nearly linear time.  In Proceedings of the 61st IEEE Annual Symposium on Foundations of Computer Science, pages 141–148, 2020.
  * [CSV17] Moses Charikar, Jacob Steinhardt, and Gregory Valiant.  Learning from untrusted data.  In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, pages 47–60, 2017.
  * [DKK20a] Ilias Diakonikolas, Daniel Kane, and Daniel Kongsgaard.  List-decodable mean estimation via iterative multi-filtering.  In Proceedings of the 34th Annual Conference on Neural Information Processing Systems, 2020.
  * [DKK+20b] Ilias Diakonikolas, Daniel M. Kane, Vasilis Kontonis, Christos Tzamos, and Nikos Zarifis.  A polynomial time algorithm for learning halfspaces with Tsybakov noise.  CoRR, abs/2010.01705, 2020.
  * [DKS18a] Ilias Diakonikolas, Daniel M. Kane, and Alistair Stewart.  List-decodable robust mean estimation and learning mixtures of spherical gaussians.  In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, pages 1047–1060, 2018.
  * [DKS18b] Ilias Diakonikolas, Daniel M. Kane, and Alistair Stewart.  List-decodable robust mean estimation and learning mixtures of spherical gaussians.  In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, pages 1047–1060. ACM, 2018.
  * [DKTZ20] Ilias Diakonikolas, Vasilis Kontonis, Christos Tzamos, and Nikos Zarifis.  Learning halfspaces with Massart noise under structured distributions.  In Proceedings of the 33rd Annual Conference on Learning Theory, pages 1486–1513, 2020.
  * [FGKP06] Vitaly Feldman, Parikshit Gopalan, Subhash Khot, and Ashok Kumar Ponnuswami.  New results for learning noisy parities and halfspaces.  In Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science, pages 563–574, 2006.
  * [FH10] Johannes Fürnkranz and Eyke Hüllermeier.  Preference learning and ranking by pairwise comparison.  In Preference Learning, pages 65–82. Springer, 2010.
  * [FHO+17] Moein Falahatgar, Yi Hao, Alon Orlitsky, Venkatadheeraj Pichapati, and Vaishakh Ravindrakumar.  Maxing and ranking with few assumptions.  In Proceedings of the 31st Annual Conference on Neural Information Processing Systems, pages 7060–7070, 2017.
  * [FJO+18] Moein Falahatgar, Ayush Jain, Alon Orlitsky, Venkatadheeraj Pichapati, and Vaishakh Ravindrakumar.  The limits of maxing, ranking, and preference learning.  In Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pages 1426–1435. PMLR, 2018.
  * [GR06] Venkatesan Guruswami and Prasad Raghavendra.  Hardness of learning halfspaces with noise.  In Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science, pages 543–552, 2006.
  * [Han14] Steve Hanneke.  Theory of disagreement-based active learning.  Foundations and Trends in Machine Learning, 7(2-3):131–309, 2014\.
  * [Hau92] David Haussler.  Decision theoretic generalizations of the PAC model for neural net and other learning applications.  Information and Computation, 100(1):78–150, 1992.
  * [HJV13] Chien-Ju Ho, Shahin Jabbari, and Jennifer Wortman Vaughan.  Adaptive task assignment for crowdsourced classification.  In Proceedings of the 30th International Conference on Machine Learning, volume 28 of JMLR Workshop and Conference Proceedings, pages 534–542, 2013.
  * [HKL19] Max Hopkins, Daniel M. Kane, and Shachar Lovett.  The power of comparisons for actively learning linear classifiers.  CoRR, abs/1907.03816, 2019.
  * [HKLM20] Max Hopkins, Daniel Kane, Shachar Lovett, and Gaurav Mahajan.  Noise-tolerant, reliable active classification with comparison queries.  In Proceedings of the 33rd Annual Conference on Learning Theory, pages 1957–2006, 2020.
  * [JN11] Kevin G. Jamieson and Robert D. Nowak.  Active ranking using pairwise comparisons.  In Proceedings of the 25th Annual Conference on Neural Information Processing Systems 2011. Proceedings of a meeting held 12-14 December 2011, Granada, Spain, pages 2240–2248, 2011.
  * [KKK19] Sushrut Karmalkar, Adam R. Klivans, and Pravesh Kothari.  List-decodable linear regression.  In Proceedings of the 33rd Annual Conference on Neural Information Processing Systems, pages 7423–7432, 2019.
  * [KLMZ17] Daniel M. Kane, Shachar Lovett, Shay Moran, and Jiapeng Zhang.  Active classification with comparison queries.  In Chris Umans, editor, Proceedings of the 58th Annual IEEE Symposium on Foundations of Computer Science, pages 355–366, 2017.
  * [KO16] Ashish Khetan and Sewoong Oh.  Achieving budget-optimality with adaptive schemes in crowdsourcing.  In Proceedings of the 30th Annual Conference on Neural Information Processing Systems, pages 4844–4852, 2016.
  * [KS17] Pravesh K. Kothari and Jacob Steinhardt.  Better agnostic clustering via relaxed tensor norms.  CoRR, abs/1711.07465, 2017.
  * [KSS92] Michael J. Kearns, Robert E. Schapire, and Linda Sellie.  Toward efficient agnostic learning.  In David Haussler, editor, Proceedings of the 5th Annual Conference on Computational Learning Theory, pages 341–352, 1992.
  * [KV94] Michael J. Kearns and Umesh V. Vazirani.  An Introduction to Computational Learning Theory.  MIT Press, 1994.
  * [MN06] Pascal Massart and Élodie Nédélec.  Risk bounds for statistical learning.  The Annals of Statistics, pages 2326–2366, 2006.
  * [MV18] Michela Meister and Gregory Valiant.  A data prism: Semi-verified learning in the small-alpha regime.  In Proceedings of the 31st Conference On Learning Theory, pages 1530–1546, 2018.
  * [PNZ+15] Dohyung Park, Joe Neeman, Jin Zhang, Sujay Sanghavi, and Inderjit S. Dhillon.  Preference completion: Large-scale collaborative ranking from pairwise comparisons.  In Proceedings of the 32nd International Conference on Machine Learning, pages 1907–1916, 2015.
  * [RLS20] Wenbo Ren, Jia Liu, and Ness B. Shroff.  The sample complexity of best-k items selection from pairwise comparisons.  CoRR, abs/2007.03133, 2020.
  * [RY20a] Prasad Raghavendra and Morris Yau.  List decodable learning via sum of squares.  In Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, pages 161–180, 2020.
  * [RY20b] Prasad Raghavendra and Morris Yau.  List decodable subspace recovery.  In Proceedings of the 33rd Annual Conference on Learning Theory, pages 3206–3226, 2020.
  * [SBGW16] Nihar B. Shah, Sivaraman Balakrishnan, Aditya Guntuboyina, and Martin J. Wainwright.  Stochastically transitive models for pairwise comparisons: Statistical and computational issues.  In Proceedings of the 33nd International Conference on Machine Learning, pages 11–20, 2016.
  * [SBW19] Nihar B. Shah, Sivaraman Balakrishnan, and Martin J. Wainwright.  Feeling the bern: Adaptive estimators for bernoulli probabilities of pairwise comparisons.  IEEE Transactions on Information Theory, 65(8):4854–4874, 2019\.
  * [Sch90] Robert E. Schapire.  The strength of weak learnability.  Machine Learning, 5:197–227, 1990.
  * [Slo88] Robert H. Sloan.  Types of noise in data for concept learning.  In Proceedings of the First Annual Workshop on Computational Learning Theory, pages 91–96, 1988.
  * [SVC16] Jacob Steinhardt, Gregory Valiant, and Moses Charikar.  Avoiding imposters and delinquents: Adversarial crowdsourcing and peer prediction.  In Proceedings of the 30th Annual Conference on Neural Information Processing Systems, pages 4439–4447, 2016.
  * [SW17] Nihar B. Shah and Martin J. Wainwright.  Simple, robust and optimal ranking from pairwise comparisons.  Journal of Machine Learning Research, 18:199:1–199:38, 2017.
  * [SZ20] Jie Shen and Shiwei Zeng.  Efficient PAC learning from the crowd with pairwise comparisons.  CoRR, abs/2011.01104, 2020.
  * [Tsy04] Alexander B. Tsybakov.  Optimal aggregation of classifiers in statistical learning.  The Annals of Statistics, 32(1):135–166, 2004.
  * [Val84] Leslie G. Valiant.  A theory of the learnable.  Communications of the ACM, 27(11):1134–1142, 1984.
  * [XZS+17] Yichong Xu, Hongyang Zhang, Aarti Singh, Artur Dubrawski, and Kyle Miller.  Noise-tolerant interactive learning using pairwise comparisons.  In Proceedings of the 31st Annual Conference on Neural Information Processing Systems, pages 2431–2440, 2017.
  * [ZSA20] Chicheng Zhang, Jie Shen, and Pranjal Awasthi.  Efficient active learning of sparse halfspaces with arbitrary bounded noise.  In Proceedings of the 34th Annual Conference on Neural Information Processing Systems, pages 7184–7197, 2020.

##  Appendix A Omitted Proofs

######  Lemma 11.

Consider the Semi-verified-BinarySearch algorithm. Suppose that $\hat{S}$ is
correctly sorted. With probability $1-\frac{\delta_{1}}{3}$, the algorithm
either increases the fraction of perfect workers from $\alpha$ to
$\frac{\alpha}{1-\frac{\alpha}{8}}$, or correctly labels $\hat{S}$, namely,
for all $(x,y)\in\overline{S}$, $y=h^{*}(x)$.

###### Proof.

Recall that the algorithm queries a set $\mathcal{W}^{{L}}$ of
$k_{2}=\frac{32}{\alpha^{2}}\log\frac{6\log n}{\delta_{1}}$ workers for
labeling each instance selected by the binary search. Since
$\mathrm{Maj{\mathchar
45\relax}size}_{\mathcal{P}^{{L}}}(x)=\operatorname{\mathbb{E}}[\mathrm{Maj{\mathchar
45\relax}size}_{\mathcal{W}^{{L}}}(x)]$ for any $x$, by the Chernoff bound, we
have

$\Pr\Big{(}\left\lvert\mathrm{Maj{\mathchar
45\relax}size}_{\mathcal{P}^{{L}}}(x)-\mathrm{Maj{\mathchar
45\relax}size}_{\mathcal{W}^{{L}}}(x)\right\rvert\geq\frac{\alpha}{8}\Big{)}\leq
2\cdot e^{-2k_{2}\cdot(\frac{\alpha}{8})^{2}}=\frac{\delta_{1}}{3\log n}.$

Taking the union bound over the labeling of $\log n$ instances, we have that
with probability $1-\frac{\delta_{1}}{3}$, for all $x\in S$,
$\left\lvert\mathrm{Maj{\mathchar
45\relax}size}_{\mathcal{P}^{{L}}}(x)-\mathrm{Maj{\mathchar
45\relax}size}_{\mathcal{W}^{{L}}}(x)\right\rvert\leq\frac{\alpha}{8}$. Thus,
if $\mathrm{Maj{\mathchar 45\relax}size}_{\mathcal{W}^{{L}}}(x)\geq
1-\frac{\alpha}{4}$, we must have $\mathrm{Maj{\mathchar
45\relax}size}_{\mathcal{P}^{{L}}}(x)\geq 1-\frac{3\alpha}{8}>1-\alpha$,
indicating that there must be some perfect workers who agree with
$\mathrm{Maj}_{\mathcal{W}^{{L}}}(x)$ such that
$\mathrm{Maj}_{\mathcal{W}^{{L}}}(x)=h^{*}(x)$. Note that if $\alpha\geq 0.7$,
$k_{2}$ workers also suffice to ensure
$\mathrm{Maj}_{\mathcal{W}^{{L}}}(x)=h^{*}(x)$ with high probability. As a
result, if the algorithm finishes without restarting, we are sure that
$\forall(x,y)\in\overline{S},y=h^{*}(x)$. On the flip side, if the algorithm
prunes due to $\mathrm{Maj{\mathchar
45\relax}size}_{\mathcal{W}^{{L}}}(x)<1-\frac{\alpha}{4}$, we must have
$\mathrm{Maj{\mathchar
45\relax}size}_{\mathcal{P}^{{L}}}(x)<1-\frac{\alpha}{8}$, indicating that if
we query a verified label for $x$, it is guaranteed that more than a
$\frac{\alpha}{8}$-fraction of the workers can be pruned and
$\alpha\leftarrow\frac{\alpha}{1-\frac{\alpha}{8}}$. ∎

######  Lemma 12.

Consider the Semi-verified-Quicksort algorithm. Given any set of instances
$S$, with probability $1-\frac{2\delta_{1}}{3}$, the algorithm either
increases the fraction of perfect workers from $\beta$ to
$\frac{\beta}{1-\frac{\beta}{8}}$, or correctly sorts $S$.

###### Proof.

Given that $k_{1}=\frac{1}{2\beta^{2}}\cdot\log\frac{3006n\cdot\log
n}{\delta_{1}}$. By traditional guarantee of Randomized Quicksort, with
probability $1-\frac{1}{n^{c}}$, the total number of pairs that needs to be
compared is $(c+2)n\log n$. By requirement on the size $n$ and set $c=1000$,
with probability $1-\frac{\delta_{1}}{3}$, $(c+2)n\log n=1002n\log n$. In
addition, similar to the proof of 5, we have $\mathrm{Maj{\mathchar
45\relax}size}_{\mathcal{P}^{{C}}}(x,x^{\prime})=\operatorname{\mathbb{E}}[\mathrm{Maj{\mathchar
45\relax}size}_{\mathcal{W}^{{C}}}(x,x^{\prime})]$ for any $(x,x^{\prime})$,
and

$\Pr\left[\bigcup_{l=1}^{1002n\log n}\left[\left\lvert\mathrm{Maj{\mathchar
45\relax}size}_{\mathcal{P}^{{C}}}(x,x^{\prime})_{l}-\mathrm{Maj{\mathchar
45\relax}size}_{\mathcal{W}^{{C}}}(x,x^{\prime})_{l}\right\rvert\leq\frac{\beta}{8}\right]\right]\leq\frac{\delta_{1}}{3}.$

In other words, with probability $1-\frac{\delta_{1}}{3}$, the following is
guaranteed. If $\mathrm{Maj{\mathchar
45\relax}size}_{\mathcal{W}^{{C}}}(x,x^{\prime})\geq 1-\frac{\beta}{4}$, we
must have $\mathrm{Maj{\mathchar
45\relax}size}_{\mathcal{P}^{{C}}}(x,x^{\prime})\geq
1-\frac{3\beta}{8}>1-\beta$, indicating that
$\mathrm{Maj}_{\mathcal{W}^{{C}}}(x,x^{\prime})=Z^{*}(x,x^{\prime})$. Same
guarantee holds when $\beta\geq 0.7$. As a result, if the algorithm never
restarts, $\hat{S}$ is correctly sorted according to $Z^{*}$. On the other
hand, if the algorithm prunes and $\mathrm{Maj{\mathchar
45\relax}size}_{\mathcal{W}^{{C}}}(x,x^{\prime})<1-\frac{\beta}{4}$, we must
have $\mathrm{Maj{\mathchar
45\relax}size}_{\mathcal{P}^{{C}}}(x,x^{\prime})\geq 1-\frac{\beta}{8}$,
meaning that by querying a verified comparison for $(x,x^{\prime})$ we can
remove at least $\frac{\beta}{8}$-fraction of the workers and update
$\beta\leftarrow\frac{\beta}{1-\frac{\beta}{8}}$. ∎

######  Proposition 13 (Restatement of Corollary 6).

Consider the Prune-Compare-and-Label algorithm, i.e. Algorithm 2. If the
algorithm does not restart and $\left\lvert
S\right\rvert\geq(\frac{1}{\delta_{1}})^{1/1000}$ , then with probability
$1-\delta_{1}$, it correctly sorts and labels all the instances in $S$ with
$O(\frac{1}{\alpha^{2}}\cdot\log\log\left\lvert S\right\rvert)$ label queries
and $O(\frac{1}{\beta^{2}}\cdot\left\lvert
S\right\rvert\cdot\log^{2}\left\lvert S\right\rvert)$ comparison tags.

###### Proof.

See Lemma 4 and Lemma 5. If Prune-Compare-and-Label does not query a verified
data and prune the workers, the total number of label queries and comparison
tags from the crowd follow that in Proposition 23. ∎

######  Corollary 14 (Restatement of Corollary 7).

With probability $1-\frac{\delta^{\prime}}{3}$,
$\mathrm{err}_{{D}_{X}}(h_{1})\leq\frac{\sqrt{\epsilon}}{2}$.

###### Proof.

By drawing a sample $S_{1}$ of $n_{\sqrt{\epsilon}/2,\delta^{\prime}/6}$ from
${D}_{X}$ and labeling it by Prune-Compare-and-Label, with probability at
least $1-\frac{\delta^{\prime}}{6}$, $\overline{S_{1}}$ is labeled correctly
according to $h^{*}$ (Proposition 6). Furthermore, we note that
$n_{\sqrt{\epsilon}/2,\delta^{\prime}/6}\geq
m_{\sqrt{\epsilon}/2,\delta^{\prime}/6}$. By Assumption 1,
$\mathrm{err}_{{D}_{X}}(h_{1})\leq\frac{\sqrt{\epsilon}}{2}$ with probability
$1-\frac{\delta^{\prime}}{3}$. ∎

######  Corollary 15 (Restatement of Corollary 8).

With probability $1-\frac{\delta^{\prime}}{3}$,
$\mathrm{err}_{{D}_{3}}(h_{3})\leq\frac{\sqrt{\epsilon}}{2}$.

###### Proof.

In Phase 3 of Algorithm 1, by rejection sampling we can successfully sample a
set $S_{3}$ of $n_{\sqrt{\epsilon}/2,\delta^{\prime}/6}$ from ${D}_{3}$. Again
by Proposition 6 and Assumption 1,
$\mathrm{err}_{{D}_{3}}(h_{3})\leq\frac{\sqrt{\epsilon}}{2}$ with probability
$1-\frac{\delta^{\prime}}{3}$. ∎

######  Lemma 16.

$\forall\alpha,\beta\in(0,1]$, with probability $1-\delta$, Algorithm 1 will
restart $O(\frac{1}{\alpha}+\frac{1}{\beta})$ times. In addition, the required
number of verified labels from $\mathcal{E}$ is $O(\frac{1}{\alpha})$ and that
of the verified comparison tags is $O(\frac{1}{\beta})$.

###### Proof.

By Lemma 5, everytime we get a verified label from $\mathcal{E}$, we must
prune some workers and increase $\alpha$ to
$\alpha^{\prime}=\frac{\alpha}{1-\frac{\alpha}{8}}$ with probability
$1-\frac{\delta_{1}}{3}$. Let $N_{i}$ be the total number of workers remained
in the crowd and $\alpha_{i}$ be the fraction of perfect workers after $i$
calls of the main algorithm. Note that we don’t need to know $N_{i}$ but it
will help our deduction. Note also that $\alpha_{0}=\alpha$. We have that

$\displaystyle\alpha_{k}$
$\displaystyle=\frac{\alpha_{0}N_{0}}{N_{0}-\frac{\alpha_{0}}{8}N_{0}-\frac{\alpha_{1}}{8}N_{1}-\dots-\frac{\alpha_{k}}{8}N_{k-1}}$
$\displaystyle=\frac{\alpha_{0}N_{0}}{N_{0}-k\cdot\frac{\alpha_{0}}{8}N_{0}}=\frac{\alpha_{0}}{1-k\cdot\frac{\alpha_{0}}{8}},$

where the second equality is due to $\alpha_{i}N_{i}=\alpha_{0}N_{0}$ for all
$i$ as we do not remove any perfect workers from the crowd. Therefore, let
$\alpha_{k}=C$ for some desired fraction of perfect workers. Then,

$k=\frac{8(C-\alpha_{0})}{C\alpha_{0}}=\frac{8}{\alpha_{0}}-\frac{8}{C}.$

By setting $C=0.7$, we have that
$k=\frac{8}{\alpha}-\frac{80}{7}=O(\frac{1}{\alpha})$. Similarly, by Lemma 12,
it is guaranteed that with probability at least $1-\frac{2\delta_{1}}{3}$,
each time Algorithm 3 prunes the workers, we would increase $\beta$ to
$\beta^{\prime}=\frac{\beta}{1-\frac{\beta}{8}}$. Thus, it takes at most
$O(\frac{1}{\beta})$ prunings for the fraction of perfect workers $\beta$
surpass some given constant, say $0.7$. As a result, by acquiring
$O(\frac{1}{\alpha})$ verified labels and $O(\frac{1}{\beta})$ verified
comparisons, the fraction of perfect workers can be increased to a strong
majority, i.e. $\geq 0.7$, such that the algorithm no longer prunes.
Therefore, the main algorithm only restarts for
$O(\frac{1}{\alpha}+\frac{1}{\beta})$ times. ∎

######  Lemma 17 (Restatement of Lemma 9).

If Test terminates without restarting Algorithm 1, we have the density
${D}_{X}[R_{1}\cup R_{2}]\leq\frac{\epsilon}{4}$ with probability
$1-\frac{\delta_{2}}{4}$. In addition, the comparison complexity of Test is
$O\big{(}\frac{1}{\epsilon\beta^{2}}\log\big{(}\frac{1}{\delta_{2}}\big{)}\log\big{(}\frac{1}{\epsilon\delta_{2}}\big{)}\big{)}$.

###### Proof.

Recall that by definition,

$\displaystyle R_{1}:=\\{x:\mathrm{Maj{\mathchar
45\relax}size}_{\mathcal{P}^{{C}}}(x,x^{-})\leq 1-\frac{\beta}{2}\\},\quad
R_{2}:=\\{x:\mathrm{Maj{\mathchar
45\relax}size}_{\mathcal{P}^{{C}}}(x,x^{+})\leq 1-\frac{\beta}{2}\\}.$

Without loss of generality, we prove the lemma for $x^{-}$. We remark that the
following guarantee holds for $x^{+}$ as well.

For any instance $x\in S_{r}$, let

$\ell_{i}=\begin{cases}1,&\text{if}\ \text{worker $i$ agrees with
$\mathrm{Maj}_{\mathcal{P}^{{C}}}(x,x^{-})$,}\\\
0,&\text{otherwise.}\end{cases}$ (A.1)

Since we query a set $\mathcal{W}$ of
$N=\frac{32}{\beta^{2}}\cdot\log\big{(}\frac{32\left\lvert
S_{r}\right\rvert}{\delta_{2}}\big{)}$ workers from the crowd to compare
$(x,x^{-})$. Note that $\mathrm{Maj{\mathchar
45\relax}size}_{\mathcal{P}^{{C}}}(x,x^{-})=\operatorname{\mathbb{E}}[\mathrm{Maj{\mathchar
45\relax}size}_{\mathcal{W}}(x,x^{-})]=\mu$, which is also the probability
that $\ell_{i}=1$. Therefore, by Hoeffding’s inequality we have

$\displaystyle\Pr\left[\mathrm{Maj{\mathchar
45\relax}size}_{\mathcal{W}}(x,x^{-})\geq 1-\frac{\beta}{4}\right]$
$\displaystyle\leq\Pr\left[\Big{\lvert}\mathrm{Maj{\mathchar
45\relax}size}_{\mathcal{W}}(x,x^{-})-\mathrm{Maj{\mathchar
45\relax}size}_{\mathcal{P}^{{C}}}(x,x^{-})\Big{\rvert}\geq\frac{\beta}{8}\right]$
$\displaystyle=\Pr\left[\left\lvert\frac{1}{N}\sum_{i=1}^{N}\ell_{i}-\mu\right\rvert\geq\frac{\beta}{8}\right]$
$\displaystyle\leq 2\cdot
e^{-\frac{2N\cdot\left(\frac{\beta}{8}\right)^{2}}{(1-0)^{2}}}$
$\displaystyle=2\cdot
e^{-2\cdot\frac{32}{\beta^{2}}\cdot\log\left(\frac{32\left\lvert
S_{r}\right\rvert}{\delta_{2}}\right)\cdot\left(\frac{\beta}{8}\right)^{2}}$
$\displaystyle=\frac{\delta_{2}}{16\left\lvert S_{r}\right\rvert}.$

By union bound, with probability $1-\frac{\delta_{2}}{16}$, if there exists
some $x\in R_{1}$ in set $S_{r}$, the algorithm detects and removes it.

In other words, if Test terminates without restarting Algorithm 1, the density
${D}_{X}[R_{1}]\leq\frac{\epsilon}{8}$ with probability
$1-\frac{\delta_{2}}{8}$. Therefore, if Algorithm 5 reaches its Step 7, we
have ${D}_{X}[R_{1}\cup R_{2}]\leq\frac{\epsilon}{4}$ with probability at
least $1-\frac{\delta_{2}}{4}$.

In addition, the total number of comparison tags in Test is

$\frac{8}{\epsilon}\log\frac{16}{\delta_{2}}\cdot\frac{32}{\beta^{2}}\cdot\log\Big{(}\frac{8\left\lvert
S_{r}\right\rvert}{\delta_{2}}\Big{)}=O\Big{(}\frac{1}{\epsilon\beta^{2}}\log\frac{1}{\delta_{2}}\log\Big{(}\frac{1}{\epsilon\delta_{2}}\Big{)}\Big{)}.$
(A.2)

∎

######  Lemma 18 (Restatement of Lemma 10).

Consider Phase 2 of Algorithm 1, with probability
$1-\frac{\delta^{\prime}}{3}$,
$\mathrm{err}_{{D}_{2}}(h_{2})\leq\frac{\sqrt{\epsilon}}{2}$.

###### Proof.

Let $R:=R_{1}\cup R_{2}$. By Lemma 9, with probability
$1-\frac{\delta_{2}}{4}$, ${D}_{X}[R]\leq\frac{\epsilon}{4}$. We first argue
that for any $x\notin R$, Semi-verified-Filter does a good job to simulate
${D}_{I}$. Consider distribution ${D}^{\prime}$ that has equal probability on
the distributions induced by $\overline{W}_{I}$ and $\overline{W}_{C}$ and let
$d^{\prime}(x)$ denote the density of point $x$ in this distribution. Likewise
let $d_{2}(x)$ be the density of points in ${D}_{2}$. We want to show that for
any $x\notin R$, $d^{\prime}(x)=\Theta(d_{2}(x))$.

Recall that $\mathrm{err}_{{D}}(h_{1})=\Theta(\frac{\sqrt{\epsilon}}{2})$. Let
$d_{X}(x)$, $d_{C}(x)$, and $d_{I}(x)$ be the density of instance $x$ in
distributions ${D}_{X}$, ${D}_{C}$, and ${D}_{I}$, respectively. Note that,
for any $x$ such that $h_{1}(x)=h^{*}(x)$, we have
$d_{X}(x)=d_{C}(x)(1-\frac{1}{2}\sqrt{\epsilon})$. Similarly, for any $x$ such
that $h_{1}(x)\neq h^{*}(x)$, we have
$d_{X}(x)=d_{I}(x)\frac{1}{2}\sqrt{\epsilon}$. $N_{C}(x)$, $N_{I}(x)$,
$M_{C}(x)$ and $M_{I}(x)$ be the number of occurrences of $x$ in the sets
$S_{C}$, $S_{I}$, $\overline{W_{C}}$ and $\overline{W_{I}}$, respectively. For
any $x$, there are two cases:

If $h_{1}(x)=h^{*}(x)$: Then, there exist absolute constants $c_{1}$ and
$c_{2}$ according to Lemma 22, such that

$\displaystyle d^{\prime}(x)$
$\displaystyle=\frac{1}{2}\operatorname{\mathbb{E}}\left[\frac{M_{C}(x)}{|\overline{W_{C}}|}\right]\geq\frac{\operatorname{\mathbb{E}}[M_{C}(x)]}{c_{1}\cdot
m_{\sqrt{\epsilon}}}\geq\frac{\operatorname{\mathbb{E}}[N_{C}(x)]}{c_{1}\cdot
m_{\sqrt{\epsilon}}}=\frac{|S_{C}|\cdot d_{X}(x)}{c_{1}\cdot
m_{\sqrt{\epsilon}}}$ $\displaystyle=\frac{|S_{C}|\cdot
d_{C}(x)\cdot(1-\frac{1}{2}\sqrt{\epsilon})}{c_{1}\cdot
m_{\sqrt{\epsilon}}}\geq c_{2}d_{C}(x)=\frac{c_{2}d_{2}(x)}{2},$

where the second and sixth transitions are by the sizes of $\overline{W_{C}}$
and $|S_{C}|$ and the third transition is by the fact that if $h(x)=h^{*}(x)$,
$M_{C}(x)>N_{C}(x)$.

If $h_{1}(x)\neq h^{*}(x)$: Then, there exist absolute constants
$c^{\prime}_{1}$ and $c^{\prime}_{2}$ according to Lemma 22, such that

$\displaystyle d^{\prime}(x)$
$\displaystyle=\frac{1}{2}\operatorname{\mathbb{E}}\left[\frac{M_{I}(x)}{|\overline{W_{I}}|}\right]\geq\frac{\operatorname{\mathbb{E}}[M_{I}(x)]}{c^{\prime}_{1}\cdot
m_{\sqrt{\epsilon}}}\geq\frac{\operatorname{\mathbb{E}}[N_{I}(x)]}{c^{\prime}_{1}\cdot
m_{\sqrt{\epsilon}}}\geq\frac{\frac{4}{7}~{}d_{X}(x)|S_{2}|}{c^{\prime}_{1}\cdot
m_{\sqrt{\epsilon}}}$
$\displaystyle=\frac{\frac{4}{7}~{}d_{I}(x)\frac{1}{2}\sqrt{\epsilon}\cdot|S_{2}|}{c^{\prime}_{1}\cdot
m_{\sqrt{\epsilon}}}\geq
c^{\prime}_{2}d_{I}(x)=\frac{c^{\prime}_{2}d_{2}(x)}{2},$

where the second and sixth transitions are by the sizes of $\overline{W_{I}}$
and $|S_{2}|$, the third transition is by the fact that if $h(x)\neq
h^{*}(x)$, $M_{I}(x)>N_{I}(x)$, and the fourth transition holds by Lemma 21.

For $x\in R$, we have ${D}_{X}[R]\leq\frac{\epsilon}{4}$. Therefore,
${D}_{2}[R]\leq\frac{\sqrt{\epsilon}}{4}$ because
${D}_{X}=\frac{\sqrt{\epsilon}}{2}{D}_{I}+(1-\frac{\sqrt{\epsilon}}{2}){D}_{C}$
and ${D}_{2}=\frac{1}{2}{D}_{I}+\frac{1}{2}{D}_{C}$. As a result, except for a
$\frac{\sqrt{\epsilon}}{4}$ fraction under ${D}_{2}$, $\forall x$
$d^{\prime}(x)\geq\Theta(d_{2}(x))$, meaning that ${D}^{\prime}$ is a good
simulation of ${D}_{2}$. By Lemma 10, since
$\left\lvert\overline{W}\right\rvert=\Theta(n_{\sqrt{\epsilon},\delta^{\prime}})$,
applying the super-sampling lemma (Lemma 20) we know that
$\mathrm{err}_{{D}_{2}}(h_{2})\leq O(\frac{\sqrt{\epsilon}}{2})$ with
probability . ∎

######  Theorem 19 (Restatement of Theorem 1).

In a semi-verified crowdsourced learning model when $\alpha,\beta\in(0,1]$,
there is an efficient algorithm that runs in time polynomial in
$(d,\frac{1}{\alpha},\frac{1}{\beta},\frac{1}{\epsilon})$, and with
probability $1-\delta$ returns $h\in\mathcal{H}$ with
$\mathrm{err}_{D}(h)\leq\epsilon$ by acquiring a total number of
$O(\frac{1}{\alpha})$ verified labels and $O(\frac{1}{\beta})$ verified
comparison tags from $\mathcal{E}$. The label complexity is
$\frac{1}{\alpha^{2}}\Big{(}\frac{1}{\alpha}+\frac{1}{\beta}\Big{)}\cdot\tilde{O}\bigg{(}\log\frac{d+\big{(}\frac{1}{\alpha}+\frac{1}{\beta}\big{)}\frac{1}{\delta}}{\epsilon}\bigg{)}$,
and the comparison complexity is
$\frac{1}{\beta^{2}}\cdot\tilde{O}\bigg{(}\Big{(}\frac{1}{\alpha}+\frac{1}{\beta}\Big{)}^{\frac{1001}{1000}}\cdot\frac{d+\big{(}\frac{1}{\delta}\big{)}^{\frac{1}{1000}}}{\epsilon}\bigg{)}$.
Furthermore, the labeling overhead is
$o\Big{(}\frac{1}{\alpha^{2}}\big{(}\frac{1}{\alpha}+\frac{1}{\beta}\big{)}\cdot\log\big{(}\frac{1}{\alpha}+\frac{1}{\beta}\big{)}\Big{)}$
and the comparison overhead is
$\tilde{O}_{\delta}\Big{(}\frac{1}{\beta^{2}}\big{(}\frac{1}{\alpha}+\frac{1}{\beta}\big{)}^{\frac{1001}{1000}}\Big{)}$
when $\epsilon\in\left(0,(\log d)^{-4}\right)$.

###### Proof.

Following Corollary 7, 8, Lemma 10 and Lemma 16, if the main algorithm outputs
a hypothesis $h$ without restarting, we have the following guarantees with
probability $1-\delta$: (i)
$\mathrm{err}_{{D}_{X}}(h_{1})\leq\frac{\sqrt{\epsilon}}{2}$;
$\mathrm{err}_{{D}_{2}}(h_{2})\leq\frac{\sqrt{\epsilon}}{2}$;
$\mathrm{err}_{{D}_{3}}(h_{3})\leq\frac{\sqrt{\epsilon}}{2}$ hold
simultaneously; (ii) the algorithm queries at most $O(\frac{1}{\alpha})$
verified labels and $O(\frac{1}{\beta})$ verified comparison tags from
$\mathcal{E}$. By Theorem 3, the classifier $\hat{h}$ returned by Algorithm 1
is such that $\mathrm{err}_{{D}}(\hat{h})\leq\epsilon$ with probability
$1-\delta$. It remains to show the label and comparison compleixty,
$m_{L},m_{C}$, and corresponding overhead $\Lambda_{L},\Lambda_{C}$.

The label complexity follows from that of [SZ20] (Theorem 24), except that the
main algorithm might be restarted by a total of
$O(\frac{1}{\alpha}+\frac{1}{\beta})$ times. Note that
$O(\frac{1}{\delta_{1}})=O(\frac{1}{\delta_{2}})=O(\frac{1}{\delta^{\prime}})=O((\frac{1}{\alpha}+\frac{1}{\beta})\cdot\frac{1}{\delta})$.

$\displaystyle m_{L}$
$\displaystyle=\Big{(}\frac{1}{\alpha}+\frac{1}{\beta}\Big{)}\cdot
O\Big{(}\frac{1}{\alpha^{2}}\cdot\log
n_{\sqrt{\epsilon},\delta^{\prime}}\cdot\log\log
n_{\sqrt{\epsilon},\delta^{\prime}}\Big{)}$
$\displaystyle=\frac{1}{\alpha^{2}}\Big{(}\frac{1}{\alpha}+\frac{1}{\beta}\Big{)}\cdot\tilde{O}\bigg{(}\log\frac{d+\big{(}\frac{1}{\alpha}+\frac{1}{\beta}\big{)}\frac{1}{\delta}}{\epsilon}\bigg{)},$

On the other hand, the comparison complexity is a summation of that in Test
and [SZ20], multiplying by a factor of $O(\frac{1}{\alpha}+\frac{1}{\beta})$,

$\displaystyle m_{C}$
$\displaystyle=\Big{(}\frac{1}{\alpha}+\frac{1}{\beta}\Big{)}\cdot
O\bigg{(}\frac{1}{\beta^{2}}\cdot
n_{\sqrt{\epsilon},\delta^{\prime}}\cdot\log^{2}n_{\sqrt{\epsilon},\delta^{\prime}}+n_{\epsilon,\delta^{\prime}}+\frac{1}{\epsilon\beta^{2}}\log\Big{(}\frac{1}{\delta^{\prime}}\Big{)}\log\Big{(}\frac{1}{\epsilon\delta^{\prime}}\Big{)}\bigg{)}$
$\displaystyle=\frac{1}{\beta^{2}}\Big{(}\frac{1}{\alpha}+\frac{1}{\beta}\Big{)}\cdot
O\bigg{(}\frac{d\log\frac{1}{\epsilon}+\big{(}\big{(}\frac{1}{\alpha}+\frac{1}{\beta}\big{)}\frac{1}{\delta}\big{)}^{\frac{1}{1000}}+\log\big{(}\big{(}\frac{1}{\alpha}+\frac{1}{\beta}\big{)}\frac{1}{\delta}\big{)}\cdot\big{(}\log\frac{1}{\epsilon}+\log\big{(}\frac{1}{\alpha}+\frac{1}{\beta}\big{)}\frac{1}{\delta}\big{)}}{\epsilon}\bigg{)}$
$\displaystyle=\frac{1}{\beta^{2}}\cdot\tilde{O}\bigg{(}\Big{(}\frac{1}{\alpha}+\frac{1}{\beta}\Big{)}^{\frac{1001}{1000}}\cdot\frac{d+\big{(}\frac{1}{\delta}\big{)}^{\frac{1}{1000}}}{\epsilon}\bigg{)}$

These in allusion to
$m_{\epsilon,\delta}=K\cdot\big{(}\frac{1}{\epsilon}(d\log(1/\epsilon)+\log(1/\delta)\big{)}$
immediately give the overheads as follows:

$\displaystyle\Lambda_{L}$
$\displaystyle=O\bigg{(}\frac{1}{\alpha^{2}}\Big{(}\frac{1}{\alpha}+\frac{1}{\beta}\Big{)}\cdot\frac{\log
n_{\sqrt{\epsilon},\delta^{\prime}}}{m_{\epsilon,\delta}}\cdot\log{\log
n_{\sqrt{\epsilon},\delta^{\prime}}}\bigg{)}$
$\displaystyle\leq\frac{1}{\alpha^{2}}\Big{(}\frac{1}{\alpha}+\frac{1}{\beta}\Big{)}\cdot\frac{\epsilon}{d+\log(1/\delta)}\cdot\tilde{O}\bigg{(}\log\frac{d+\big{(}\frac{1}{\alpha}+\frac{1}{\beta}\big{)}\frac{1}{\delta}}{\epsilon}\bigg{)}$
$\displaystyle=\frac{1}{\alpha^{2}}\Big{(}\frac{1}{\alpha}+\frac{1}{\beta}\Big{)}\log\Big{(}\frac{1}{\alpha}+\frac{1}{\beta}\Big{)}\cdot\frac{\epsilon}{d}\cdot\tilde{O}\Big{(}\log\frac{d}{\epsilon}\Big{)},$

and

$\displaystyle\Lambda_{C}$
$\displaystyle=\frac{1}{\beta^{2}}\Big{(}\frac{1}{\alpha}+\frac{1}{\beta}\Big{)}\cdot
O\Bigg{(}\frac{n_{\sqrt{\epsilon},\delta^{\prime}}}{m_{\epsilon,\delta}}\cdot\log^{2}n_{\sqrt{\epsilon},\delta^{\prime}}+\frac{n_{\epsilon,\delta^{\prime}}}{m_{\epsilon,\delta}}+\frac{\frac{1}{\epsilon}\log\big{(}\frac{1}{\delta^{\prime}}\big{)}\log\big{(}\frac{1}{\epsilon\delta^{\prime}}\big{)}}{m_{\epsilon,\delta}}\Bigg{)}$
$\displaystyle\leq\frac{1}{\beta^{2}}\Big{(}\frac{1}{\alpha}+\frac{1}{\beta}\Big{)}\cdot
O\Bigg{(}\sqrt{\epsilon}\cdot\frac{d\log\frac{1}{\epsilon}+\big{(}\big{(}\frac{1}{\alpha}+\frac{1}{\beta}\big{)}\frac{1}{\delta}\big{)}^{\frac{1}{1000}}}{d\log\frac{1}{\epsilon}+\log\frac{1}{\delta}}\cdot\log^{2}\bigg{(}\frac{d+\big{(}\frac{1}{\alpha}+\frac{1}{\beta}\big{)}\frac{1}{\delta}}{\epsilon}\bigg{)}$
$\displaystyle\quad\quad+\frac{d\log\frac{1}{\epsilon}+\big{(}\big{(}\frac{1}{\alpha}+\frac{1}{\beta}\big{)}\frac{1}{\delta}\big{)}^{\frac{1}{1000}}}{d\log\frac{1}{\epsilon}+\log(\frac{1}{\delta})}+\frac{\log\big{(}\big{(}\frac{1}{\alpha}+\frac{1}{\beta}\big{)}\frac{1}{\delta}\big{)}\log\big{(}\big{(}\frac{1}{\alpha}+\frac{1}{\beta}\big{)}\frac{1}{\epsilon\delta}\big{)}}{d\log\frac{1}{\epsilon}+\log\frac{1}{\delta}}\Bigg{)}$
$\displaystyle\leq\frac{1}{\beta^{2}}\Big{(}\frac{1}{\alpha}+\frac{1}{\beta}\Big{)}^{\frac{1001}{1000}}\log^{2}\Big{(}\frac{1}{\alpha}+\frac{1}{\beta}\Big{)}\cdot
O\Bigg{(}\sqrt{\epsilon}\cdot\frac{d\log\frac{1}{\epsilon}+\big{(}\frac{1}{\delta}\big{)}^{\frac{1}{1000}}}{d\log\frac{1}{\epsilon}+\log\frac{1}{\delta}}\cdot\log^{2}\bigg{(}\frac{d+\frac{1}{\delta}}{\epsilon}\bigg{)}$
$\displaystyle\quad\quad+\frac{d\log\frac{1}{\epsilon}+\big{(}\frac{1}{\delta}\big{)}^{\frac{1}{1000}}}{d\log\frac{1}{\epsilon}+\log(\frac{1}{\delta})}+\frac{\log\big{(}\frac{1}{\delta}\big{)}\big{(}\log\frac{1}{\epsilon}+\log\frac{1}{\delta}\big{)}}{d\log\frac{1}{\epsilon}+\log\frac{1}{\delta}}\Bigg{)}$

Recall that by the definition of $n_{{\epsilon},\delta}$ and
$m_{\epsilon,\delta}$ in Section 3, we have
$m_{\epsilon,\delta}=\Theta(n_{\epsilon,\delta})=\Theta(\frac{d}{\epsilon}\log\frac{1}{\epsilon})$
when $\delta$ is a constant. In this case, we can see that

$\Lambda_{C}\leq\frac{1}{\beta^{2}}\Big{(}\frac{1}{\alpha}+\frac{1}{\beta}\Big{)}^{\frac{1001}{1000}}\log^{2}\Big{(}\frac{1}{\alpha}+\frac{1}{\beta}\Big{)}\cdot
O_{\delta}\Big{(}\sqrt{\epsilon}\cdot\log^{2}\frac{d}{\epsilon}+2\Big{)}.$

When $\epsilon\in\left(0,(\log d)^{-4}\right)$,
$\Lambda_{C}=\tilde{O}_{\delta}\Big{(}\frac{1}{\beta^{2}}\big{(}\frac{1}{\alpha}+\frac{1}{\beta}\big{)}^{\frac{1001}{1000}}\Big{)}$.
In addition,
$\Lambda_{L}=o\big{(}\frac{1}{\alpha^{2}}\big{(}\frac{1}{\alpha}+\frac{1}{\beta}\big{)}\log\big{(}\frac{1}{\alpha}+\frac{1}{\beta}\big{)}\big{)}$,
because $\Lambda_{L}$ goes to $0$ when $\epsilon$ goes to $0$. ∎

##  Appendix B Useful Lemmas

######  Lemma 20 (Robust Super-Sampling Lemma, Lemma 4.12 in [ABHM17]).

Given a hypothesis class $\mathcal{H}$ consider any two discrete distributions
${D}$ and ${D}^{\prime}$ over $\mathcal{X}\times\mathcal{Y}$ such that except
for an $\epsilon$ fraction of the mass under ${D}$, we have that for all $x$,
$d^{\prime}(x)\geq c\cdot d(x)$ for an absolute constant $c>0$ and both
distributions are labeled according to $h^{*}\in\mathcal{H}$. There exists a
constant $c^{\prime}>1$ such that for any $\epsilon,\delta$, with probability
$1-\delta$ over a labeled sample set $S$ of size
$c^{\prime}m_{\epsilon,\delta}$ drawn from ${D}^{\prime}$,
$\mathcal{O}_{\mathcal{H}}(S)$ has error of at most $2\epsilon$ with respect
to $D$.

######  Lemma 21 (Lemma 22 in [SZ20]).

Consider Algorithm 5. Assume that the subset $U$ and $S_{\text{in}}$ are
correctly labeled. If the algorithm never restarts, for all but an
$\frac{\epsilon}{4}$-fraction of the instances $x$ in $S_{2}$, we have the
following guarantees: if $h(x)=h^{*}(x)$, it will be added to $S_{I}$ with
probability at most $\frac{1}{4}\sqrt{\epsilon}$; if $h(x)\neq h^{*}(x)$, it
goes to $S_{I}$ with probability at least $\frac{4}{7}$.

###### Proof.

Follow the guarantee of Lemma 9. If the algorithm never restarts, then for all
but an $\frac{\epsilon}{4}$-fraction of the instances $x$ in $S_{2}$, we have
$\mathrm{Maj{\mathchar 45\relax}size}_{\mathcal{P}^{{C}}}(x,x^{\prime})\geq
1-\frac{\beta}{2},x^{\prime}\in\\{x^{-},x^{+}\\}$. Consider any instance $x\in
S$ outside the interval $[x^{-},x^{+}]$. When $\beta<0.7$,
$\mathrm{Maj{\mathchar
45\relax}size}_{\mathcal{P}^{{C}}}(x,x^{\prime})\geq\frac{1}{2}+\Theta(1)$
which suffices for the filtering scheme from [ABHM17] to work and the
guarantee follows from the Lemma 4.2 in that work. If $\beta\geq 0.7$, lemma
follows from that of [SZ20]. We then consider any instance $x\in S$ that falls
into the interval $[x^{-},x^{+}]$. With probability at least
$1-\frac{\sqrt{\epsilon}}{4}$, it will be added to $S_{\text{in}}$ and
correctly labeled by Prune-Compare-and-Label. That is, if $h(x)=h^{*}(x)$, it
will be added to $S_{I}$ with probability at most $\frac{\sqrt{\epsilon}}{4}$;
if $h(x)\neq h^{*}(x)$, it will be added to $S_{I}$ with probability at least
$1-\frac{\sqrt{\epsilon}}{4}\geq\frac{4}{7}$. This completes the proof. ∎

######  Lemma 22 (Lemma 4.7 in [ABHM17]).

With probability at least
$1-\exp(-\Omega(n_{\sqrt{\epsilon},\delta^{\prime}}))$, $\overline{W}_{I}$,
$\overline{W}_{C}$ and $S_{I}$ all have size
$\Theta(n_{\sqrt{\epsilon},\delta^{\prime}})$.

###### Proof.

Notice that
$n_{\epsilon,\delta^{\prime}}=\Omega(m_{\epsilon,\delta^{\prime}})$, the lemma
follows from [ABHM17]. ∎

The following two results from [SZ20] will be useful.

######  Proposition 23 (Prop. 3 in [SZ20]).

Suppose $\alpha\geq 0.7,\beta\geq 0.7$. Consider the Prune-Compare-and-Label
algorithm, i.e. Algorithm 2. If $\left\lvert
S\right\rvert\geq(\frac{3}{\delta})^{1/1000}$, then with probability at least
$1-\delta$, it correctly sorts and labels all the instances in $S$. The label
complexity is $O\big{(}\log\left\lvert S\right\rvert\cdot\log{\log\left\lvert
S\right\rvert}\big{)}$, and the comparison complexity is given by
$O\big{(}\left\lvert S\right\rvert\cdot\log^{2}\left\lvert
S\right\rvert\big{)}$.

######  Theorem 24 (Theorem 7 in [SZ20]).

Suppose $\alpha\geq 0.7,\beta\geq 0.7$. With probability $1-\delta$, Algorithm
1 runs in time $\mathrm{poly}(d,\frac{1}{\epsilon})$ and returns a classifier
$h\in\mathcal{H}$ with error rate $\mathrm{err}_{{D}_{X}}({h})\leq\epsilon$.
In addition, the label complexity is $O\Big{(}\log
n_{\sqrt{\epsilon},\delta}\cdot\log\log n_{\sqrt{\epsilon},\delta}\Big{)}$,
and the comparison complexity is
$O\left(n_{\sqrt{\epsilon},\delta}\log^{2}n_{\sqrt{\epsilon},\delta}+n_{\epsilon,\delta}\right)$.


Realizing algebraic 2-complexes by cell complexes

W. H. Mannan

MSC: 57M20, 20F05, 16E05, 16E10 Keywords 2-complex, Wall’s D(2)

problem, Realisation problem

> Abstract The realization theorem asserts that for a finitely presented group
> $G$, the D(2) property and the realization property are equivalent as long
> as $G$ satisfies a certain finiteness condition. We show that the two
> properties are in fact equivalent for all finitely presented groups.

##  1 Introduction

An open question in low dimensional topology is: Given a finite cell complex
of cohomological dimension $n$ (with respect to all coefficient bundles) must
it be homotopy equivalent to a finite $n$-complex (that is a finite cell
complex whose cells are all of dimension less than or equal to $n$)? In 1965
Wall introduced the problem and showed that a counter example must have $n\leq
2$ (see [4]). The Stallings-Swan theorem (proved a few years later - see [3])
implied that $n>1$. So a counter example must be (up to homotopy equivalence)
a finite 3-complex of cohomological dimension 2, which is not homotopy
equivalent to any finite 2-complex. The question of whether or not such a
complex exists is known as ‘Wall’s D(2) problem’.

This question may be parameterized by fundamental group. That is, we say a
finitely presented group $G$ satisfies the D(2) property if every connected
finite 3-complex with fundamental group $G$ is homotopy equivalent to a finite
2-complex. Wall’s D(2) problem then becomes: “Does every finitely presented
group $G$ satisfy the D(2) property?”.

We say a module over $\mathbb{Z}[G]$ is f.g. free if it has a finite basis and
we say a module $S$ is f.g. stably free if $S\oplus F_{1}\cong F_{2}$, where
$F_{1}$ and $F_{2}$ are f.g. free.

Another property which a finitely presented group $G$ may satisfy is the
realization property.

######  Definition 1.

An algebraic 2-complex over $G$ is an exact sequence of f.g. stably free
modules over $\mathbb{Z}[G]$:

$S_{2}\stackrel{{\scriptstyle\partial_{2}}}{{\to}}S_{1}\stackrel{{\scriptstyle\partial_{2}}}{{\to}}S_{0}$

where coker($\partial_{1}$)$\cong\mathbb{Z}$.

We say a finitely presented group $G$ satisfies the realization property if
every algebraic 2-complex over $G$ is ‘geometrically realizable’. That is, it
is chain homotopy equivalent to $C_{*}(X)$, the chain complex (over
$\mathbb{Z}[G]$) arising from the universal cover of a finite 2-complex $X$,
with $\pi_{1}(X)=G$.

This property may be stated in purely algebraic terms. Given a connected
finite 2-complex $X$ we may quotient out a maximal tree in its 1-skeleton to
attain a Cayley complex $Y$ in the same homotopy type as $X$. The process of
going from a presentation of $G$ to $C_{*}(Y)$ (where $Y$ is the Cayley
complex of the presentation) is a formulaic application of Fox’s free
differential calculus (see [1], §48). Hence a finitely presented group $G$
satisfies the realization property precisely when every algebraic 2-complex
over $G$ arises (up to chain homotopy equivalence) from a finite presentation
of $G$.

Our main result is that the ‘geometric’ D(2) property is equivalent to the
‘algebraic’ realization property:

######  Theorem 1.1.

A finitely presented group $G$ satisfies the D(2) property if and only if it
satisfies the realization property.

In one direction this is proved in [1], Appendix B:

Weak Realization Theorem: The realization property for $G$ implies the D(2)
property for $G$.

In the other direction, it is sufficient to show that every algebraic
2-complex $\mathcal{A}$ over $G$ is chain homotopy equivalent to $C_{*}(Y)$
for some finite cell complex $Y$. Then the D(2) property for $G$ would imply
that $Y$ was homotopy equivalent to a finite 2-complex $X$, which would
geometrically realize $\mathcal{A}$.

Johnson does this in [1], Appendix B, subject to the existence of a truncated
resolution:

$F_{3}\to F_{2}\to F_{1}\to F_{0}\to\mathbb{Z}\to 0$

where the $F_{i}$ are f.g. free modules over $\mathbb{Z}[G]$. In the next
section we use a stronger “eventual stability” result ([2], theorem 1.1), to
show it may be done for any finitely presented group $G$.

##  2 Realizing algebraic 2-complexes by finite cell complexes

Let $G$ be a finitely presented group and let $\mathcal{A}$ denote following
the algebraic 2-complex over $G$:

$S_{2}\stackrel{{\scriptstyle d_{2}}}{{\to}}S_{1}\stackrel{{\scriptstyle
d_{1}}}{{\to}}S_{0}$

######  Theorem 2.1.

We may realize $\mathcal{A}$ up to chain homotopy equivalence by a finite
geometric 3-complex.

###### Proof.

Let $Y_{1}$ denote the Cayley complex of a finite presentation of $G$. Then
$C_{*}(Y_{1})$ is an algebraic $2$-complex:

$C_{2}\stackrel{{\scriptstyle\partial_{2}}}{{\to}}C_{1}\stackrel{{\scriptstyle\partial_{1}}}{{\to}}C_{0}$

and the $C_{i}$ are f.g. free modules over $\mathbb{Z}[G]$.

Let $C\cong S_{2}\oplus C_{1}\oplus S_{0}$ and let $S\cong C_{2}\oplus
S_{1}\oplus C_{0}$. Also let $Q$ be a f.g. free module such that $C\oplus Q$
and $S\oplus Q$ are f.g. free. Let $\vec{e_{1}},\cdots,\vec{e_{n}}$ denote a
basis for $C\oplus Q$ and let $Y_{2}$ denote the wedge of $Y_{1}$ with $n$
$2$-spheres. Hence $C_{*}(Y_{2})$ is:

$C_{2}\oplus(C\oplus Q)\stackrel{{\scriptstyle\partial_{2}\oplus
0}}{{\to}}C_{1}\stackrel{{\scriptstyle\partial_{1}}}{{\to}}C_{0}$

Let

$\mathcal{A}^{\prime}=S\oplus
Q\stackrel{{\scriptstyle\iota}}{{\to}}S_{2}\oplus(S\oplus
Q)\stackrel{{\scriptstyle d_{2}\oplus 0}}{{\to}}S_{1}\stackrel{{\scriptstyle
d_{1}}}{{\to}}S_{0}$

where $\iota$ denotes the natural inclusion into the second summand. The
natural inclusion
$\mathcal{A}\hookrightarrow\mathcal{A}^{\prime}$ is a simple homotopy
equivalence.

By [2], theorem 1.1 we have a chain homotopy equivalence:

$\left\\{S_{2}\oplus S\stackrel{{\scriptstyle d_{2}\oplus
0}}{{\to}}S_{1}\stackrel{{\scriptstyle
d_{1}}}{{\to}}S_{0}\right\\}\tilde{\to}\left\\{C_{2}\oplus
C\stackrel{{\scriptstyle\partial_{2}\oplus
0}}{{\to}}C_{1}\stackrel{{\scriptstyle\partial_{1}}}{{\to}}C_{0}\right\\}$

By extending this to the identity on $Q$ we get a chain homotopy equivalence:

$\displaystyle S_{2}\oplus(S\oplus Q)\,\stackrel{{\scriptstyle d_{2}\oplus
0}}{{\to}}S_{1}\,\,\stackrel{{\scriptstyle d_{1}}}{{\to}}\,\,S_{0}\,\quad$
$\displaystyle\downarrow{\phi_{2}}\quad\qquad\qquad\downarrow{\phi_{1}}\,\,\quad\downarrow{\phi_{0}}$
$\displaystyle C_{2}\oplus(C\oplus Q)\stackrel{{\scriptstyle\partial_{2}\oplus
0}}{{\to}}C_{1}\,\,\stackrel{{\scriptstyle\partial_{1}}}{{\to}}\,\,C_{0}\quad$

We pick a basis $\vec{f_{1}},\cdots,\vec{f_{m}}$ for $S\oplus Q$. Then for
each $i$ we have $\phi_{2}\iota\vec{f_{i}}\in
H_{2}(\tilde{Y_{2}};\mathbb{Z})$. The Hurewicz isomorphism theorem implies an
isomorphism
$h:H_{2}(\tilde{Y_{2}};\mathbb{Z})\tilde{\to}\pi_{2}(\tilde{Y_{2}})$ and the
covering map induces an isomorphism
$p:\pi_{2}(\tilde{Y_{2}})\tilde{\to}\pi_{2}(Y_{2})$.

For each $i\in\\{1,\cdots,m\\}$, let $E_{i}$ be a 3-ball and let
$\psi_{i}:\partial E_{i}\to Y_{2}$ denote a map representing the homotopy
element $ph\phi_{2}\iota\vec{f_{i}}$, where we identify $S^{2}$ with $\partial
E_{i}$.

Let $Y$ denote the 3-complex constructed by attaching the 3-cells $E_{i}$ to
$Y_{2}$ via the attaching maps $\psi_{i}$. Then $C_{*}(Y)$ is given by:

$S\oplus Q\stackrel{{\scriptstyle\phi_{2}\iota}}{{\to}}C_{2}\oplus(C\oplus
Q)\stackrel{{\scriptstyle\partial_{2}\oplus
0}}{{\to}}C_{1}\,\,\stackrel{{\scriptstyle\partial_{1}}}{{\to}}\,\,C_{0}\quad$

We now have a chain homotopy equivalence
$\mathcal{A}^{\prime}\tilde{\to}C_{*}(Y)$:

$\displaystyle S\oplus
Q\,\stackrel{{\scriptstyle\iota}}{{\to}}S_{2}\oplus(S\oplus
Q)\,\stackrel{{\scriptstyle d_{2}\oplus
0}}{{\to}}S_{1}\,\,\stackrel{{\scriptstyle d_{1}}}{{\to}}\,\,S_{0}\,\quad$
$\displaystyle\downarrow
1\,\,\quad\qquad\downarrow{\phi_{2}}\quad\qquad\qquad\downarrow{\phi_{1}}\,\,\quad\downarrow{\phi_{0}}$
$\displaystyle S\oplus
Q\stackrel{{\scriptstyle\phi_{2}\iota}}{{\to}}C_{2}\oplus(C\oplus
Q)\stackrel{{\scriptstyle\partial_{2}\oplus
0}}{{\to}}C_{1}\,\,\stackrel{{\scriptstyle\partial_{1}}}{{\to}}\,\,C_{0}\quad$

Thus $\mathcal{A}$ is geometrically realized by $Y$. ∎

In particular, if the D(2) property holds for $G$, then we may find a finite
2-complex, $X$ in the homotopy type of $Y$, as $Y$ is cohomologically
2-dimensional (the cohomology of $Y$ is an invariant of the chain homotopy
type of $C_{*}(Y)$). Thus $\mathcal{A}$ is geometrically realized by the
2-complex $X$.

Hence the D(2) property for $G$ implies the realization property for $G$. From
the Weak Realization Theorem ([1], Appendix B) we know that the realization
property for $G$ implies the D(2) property for $G$. Our proof of theorem 1.1
is therefore complete.

## References

  * [1] F.E.A. Johnson, ‘Stable Modules and the D(2) Problem’, LMS Lecture Note Series 301 (2003).
  * [2] W.H. Mannan , ‘Homotopy types of truncated projective resolutions’, Homology, Homotopy and Applications, vol. 9(2) (2007) pp.445 - 449. (http://intlpress.com/HHA/v9/n2/a16/v9n2a16.pdf)
  * [3] R.G. Swan, ‘Groups of cohomological dimension one’, J. of Algebra 12 (1969) 585-610
  * [4] C.T.C. Wall, ‘Finiteness conditions for CW–complexes’, Ann. of Math. 81 (1965)pp. 56 - 69.

W. H. Mannan
J8 Hicks Building
Department of Pure Mathematics
University of Sheffield
Hounsfield Road
Sheffield S3 7RH
Telephone: (0114) 2223724
<EMAIL_ADDRESS>