\section{Main Algorithm and Theoretical Guarantees}\label{sec:algorithm}

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.

\begin{algorithm}[t]

\caption{Main Algorithm}
\label{alg:boost}

\begin{algorithmic}[1]

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

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

\STATE $\tau \leftarrow \frac{8}{\alpha}+\frac{8}{\beta}$, $\delta'\leftarrow\frac{\delta}{\tau}$.

\hspace{-12pt}{\textbf{Phase 1}}:

\STATE $\bar{S_1} \leftarrow \textsc{Prune-Compare-and-Label}\xspace(S_1,\alpha,\beta, \frac{\delta'}{6})$,  for an instance set $S_1$ of size $n_{\sqrt{\epsilon}/2,\delta'/6}$ from ${\D_{X}}$.

\STATE $h_1  \leftarrow \mathcal{A}_\H(\bar{S_1}, \frac{\sqrt{\epsilon}}{2}, \frac{\delta'}{6})$.

\hspace{-12pt}{\textbf{Phase 2}}:

\STATE  ${S_I} \leftarrow \textsc{Semi-verified-Filter}\xspace (S_2, h_1,\alpha,\beta, \frac{\delta'}{12})$, for an instance set $S_2$ of size $\Theta(n_{\epsilon,\delta'/12})$ drawn from ${\D_{X}}$.

\STATE Let $S_C$ be an instance set of size $\Theta(n_{\sqrt{\epsilon},\delta'/12})$ drawn from ${\D_{X}}$.

\STATE  $\overline{S_{\text{All}}} \leftarrow \textsc{Prune-Compare-and-Label}\xspace(S_I\cup S_C,\alpha,\beta, \delta'/12)$.

\STATE   $\bar{W_I} \leftarrow \{(x,y)\in\overline{S_{\text{All}}}\mid y\neq h_1(x) \}$, $\bar{W_C} \leftarrow \overline{S_{\text{All}}} \backslash \bar{W_I}$.

\STATE Draw a sample set $\bar W$ of size $\Theta(n_{\sqrt{\epsilon}/2,\delta'/12})$ from a distribution that equally weights $\bar{W_I}$ and $\bar{W_C}$.

\STATE  $h_2 \leftarrow \mathcal{A}_\H(\bar{W}, \frac{\sqrt{\epsilon}}{2}, \frac{\delta'}{6})$.

\hspace{-12pt} \textbf{Phase 3}:

\STATE   $\bar{S_3} \leftarrow \textsc{Prune-Compare-and-Label}\xspace(S_3,\alpha,\beta, \delta'/6)$, for an instance set $S_3$ of size  $n_{\sqrt{\epsilon}/2,\delta'/6}$ drawn from ${\D_{X}}$ conditioned on $h_1(x) \neq h_2(x)$.

\STATE   $h_3 \leftarrow \mathcal{A}_\H(\bar{S_3}, \frac{\sqrt{\epsilon}}{2}, \frac{\delta'}{6})$.

{\bfseries return}  $\hat{h} \leftarrow \mathrm{Maj}(h_1, h_2, h_3)$.

\vspace{-1pt}
\end{algorithmic}

\end{algorithm}

\subsection{Overview}\label{subsec:overview}

Our main algorithm follows the same pipeline of existing crowdsourced PAC learning algorithms of \cite{awasthi2017efficient,shen2020efficient}. 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}_\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 \cite{schapire1990strength} was utilized.

\begin{theorem}[\cite{schapire1990strength}]\label{thm:boost}
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$.
\end{theorem}

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~\ref{as:pac}, 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, \cite{shen2020efficient} 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 {\em 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 \textsc{Prune-Compare-and-Label}\xspace and \textsc{Semi-verified-Filter}\xspace respectively. By integrating these two robust components into the boosting framework, we obtain our main algorithm, Algorithm~\ref{alg:boost}. 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{\dash}size}_{\mathcal{P}^{{L}}}(x) = 1-\alpha$, since the perfect workers will provide correct labels which consist of $\alpha$ fraction. Thus, if $\mathrm{Maj{\dash}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 \abs{S})$ 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 {\em 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\abs{S})$ workers for labeling (respectively, $O(\frac{1}{\beta^2} \log\abs{S})$ for comparison). When $\abs{S} = O(n_{\sqrt{\epsilon},\delta})$, we can well control the query complexity; this gives our new algorithm \textsc{Prune-Compare-and-Label}\xspace (Algorithm~\ref{alg:label}), which consists of a semi-verified version of Quicksort (Algorithm~\ref{alg:robust_quick_sort}) and binary search (Algorithm~\ref{alg:robust_binary_search}).

However, it will be a trouble when $\abs{S} = \Theta(n_{\epsilon, \delta})$. In particular, if we were to perform $\Theta(\abs{S})$ 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 {\em grows} with the sample size $n_{\epsilon, \delta}$. Unfortunately, such situation indeed occurs in the algorithm of \cite{shen2020efficient}, 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 \textsc{Semi-verified-Filter}\xspace (Algorithm~\ref{alg:filter}). 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 \textsc{Semi-verified-Filter}\xspace, 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:
\begin{align}
R_1 := \{x: \mathrm{Maj{\dash}size}_{\mathcal{P}^{{C}}}(x, x^-) \leq 1-\frac{\beta}{2} \},\\
R_2 := \{ x: \mathrm{Maj{\dash}size}_{\mathcal{P}^{{C}}}(x, x^+) \leq  1-\frac{\beta}{2} \};
\end{align}
this is exactly the purpose of invoking \textsc{Test}\xspace (Algorithm~\ref{alg:test}) at Step 6 of \textsc{Semi-verified-Filter}\xspace.

\subsection{\textsc{Prune-Compare-and-Label}\xspace}\label{subsec:complabel}

\begin{algorithm}[t]

	\caption{\textsc{Prune-Compare-and-Label} }
	\label{alg:label}

	\begin{algorithmic}[1]

		\REQUIRE {An instance set $S$, parameters $\alpha$, $\beta$, $\delta_1$.}
		\ENSURE {A sorted and labeled set $\bar{S}$.}

		\STATE  $\hat{S} \leftarrow \textsc{Semi-verified-Quicksort}\xspace(S, \beta, \delta_1)$.

		\STATE $\bar{S} \leftarrow$ \textsc{Semi-verified-BinarySearch}$(\hat{S}, \alpha, \delta_1)$.

		{\bfseries return} $\bar{S}$.

	\end{algorithmic}
\end{algorithm}

\begin{algorithm}[t]

	\caption{\textsc{Semi-Verified-Quicksort}}
	\label{alg:robust_quick_sort}

	\begin{algorithmic}[1]

		\REQUIRE{An instance set $S = \{x_i\}_{i=1}^n$, $\beta$, $\delta_1$.}
		\ENSURE{A sorted list $\hat{S}$.}

		\STATE  $k_1 \leftarrow \frac{1}{2\beta^{2}}\cdot\log\frac{3006n\cdot\log n }{\delta_1}$.

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

		\IF{$\beta \geq 0.7$ or $\mathrm{Maj{\dash}size}_{\mathcal{W}^{{C}}}(x,x')\geq 1-\frac{\beta}{4}$}{ \label{step:maj_size_beta}
			\STATE	Use $\mathrm{Maj}_{\mathcal{W}^{{C}}}(x,x')$ as the comparison tag.
		}\ELSE{
			\STATE	Get a verified comparison tag $z^* \leftarrow Z^*(x,x')$.	{\bfseries Restart} Algorithm \ref{alg:boost} with $\mathcal{P}^{{C}}\leftarrow \mathcal{P}^{{C}}_{ \mid (x, x', z^*)}$ and $\beta\leftarrow\frac{\beta}{1-\frac{\beta}{8}}$.
		}
		\ENDIF

		{\bfseries return} $\hat{S}$.

	\end{algorithmic}
\end{algorithm}

\begin{algorithm}[t]

	\caption{\textsc{Semi-Verified-BinarySearch}}
	\label{alg:robust_binary_search}
	\begin{algorithmic}[1]

		\REQUIRE {A sorted instance set $\hat{S} = \{\hat{x}_i\}_{i=1}^n$, $\alpha$, $\delta_1$.}
		\ENSURE {A labeled set $\bar{S}$.}

		\STATE $t_{\min} \leftarrow 1$, $t_{\max} \leftarrow n$, $k_2 \leftarrow \frac{32}{\alpha^{2}}\log\frac{6\log n}{\delta_1}$.

		\WHILE{$t_{\min} < t_{\max}$}
		\STATE		$t = (t_{\min} + t_{\max})/2$.

		\STATE		Draw a set of $k_2$ workers $\mathcal{W}^{{L}}$ from $\mathcal{P}^{{L}}$.

		\IF{$\alpha \geq 0.7$ or $\mathrm{Maj{\dash}size}_{\mathcal{W}^{{L}}}({x}_t)\geq 1-\frac{\alpha}{4}$}{ \label{step:maj_size_alpha}
			\STATE	$\hat{y}_t \leftarrow \mathrm{Maj}_{\mathcal{W}^{{L}}}(x_t)$.
			\STATE \textbf{If} $\hat{y}_t=1$, \textbf{then} $t_{\max} \leftarrow t-1$; \textbf{else} $t_{\min} \leftarrow t+1$.
		}\ELSE{
			\STATE	Get a verified label $y_t^* \leftarrow h^*(x_t)$.
			{\bfseries Restart} Algoirthm \ref{alg:boost} with $\mathcal{P}^{{L}} \leftarrow \mathcal{P}^{{L}}_{\mid ({x}_t,y_t^*)}$ and $\alpha \leftarrow \frac{\alpha}{1-\frac{\alpha}{8}}$.
		}
		\ENDIF

		\ENDWHILE

		\STATE	For all $t' > t, \hat{y}_{t'} \leftarrow +1$.

		\STATE	For all $t' < t, \hat{y}_{t'} \leftarrow -1$.

		{\bfseries return} $\bar{S} = \{(\hat{x}_1, \hat{y}_1), (\hat{x}_2,\hat{y}_2), \dots, (\hat{x}_m, \hat{y}_m)\}$.

	\end{algorithmic}
\end{algorithm}

Similar to prior comparison-based PAC learning algorithms \cite{xu2017noise}, 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, \cite{xu2017noise} assumes comparison and labeling error rate as small as $\epsilon$ to guarantee the success, while  the crowdsourced learner of \cite{shen2020efficient} 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{\dash}size}_{\mathcal{P}^{{C}}}(x, x') > 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')$. By the Chernoff bound, we can show that by drawing $O(\frac{1}{\beta^2} \log \abs{S})$ workers, the empirical majority size will be a faithful estimate of the population one, though the condition becomes $\mathrm{Maj{\dash}size}_{\mathcal{W}^{{C}}}(x, x') \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.

\begin{lemma}\label{lem:beta}
	Consider the \textsc{Semi-verified-Quicksort}\xspace 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$.
\end{lemma}

\begin{lemma}\label{lem:alpha}
Consider the \textsc{Semi-verified-BinarySearch}\xspace 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\bar{S}$, $y=h^*(x)$.
\end{lemma}

We further note that comparing to the non-robust version,  \textsc{Prune-Compare-and-Label}\xspace 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 \textsc{Prune-Compare-and-Label}\xspace matches that of the non-robust counterpart in~\cite{shen2020efficient}.

\begin{proposition}\label{prop:complabel}
	Consider the \textsc{Prune-Compare-and-Label}\xspace algorithm, i.e. Algorithm~\ref{alg:label}. If the algorithm does not restart and $\abs{S}\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\abs{S})$ label queries and  $O(\frac{1}{\beta^2}\cdot \abs{S}\cdot\log^2\abs{S})$ comparison tags.
\end{proposition}

In light of Theorem~\ref{thm:boost}, $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~\ref{as:pac}, drawing a sample of $\Theta(n_{\sqrt\epsilon,\delta'})$ instances on each distribution respectively and feeding them to $\mathcal{A}_\H$ induces the following corollaries on the performance of $h_1,h_3$.

\begin{corollary}\label{coro:h1}
	With probability $1-\frac{\delta'}{3}$, $\mathrm{err}_{{D}_X}(h_1)\leq\frac{\sqrt\epsilon}{2}$.
\end{corollary}
\begin{corollary}\label{coro:h3}
	With probability $1-\frac{\delta'}{3}$, $\mathrm{err}_{{D}_3}(h_3)\leq\frac{\sqrt\epsilon}{2}$.
\end{corollary}

\subsection{\textsc{Semi-verified-Filter}\xspace}\label{subsec:filter}

\begin{algorithm}[t]
\caption{\textsc{Semi-verified-Filter}\xspace}
\label{alg:filter}
\begin{algorithmic}[1]

\REQUIRE {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$.}
\ENSURE {The set $S_I$ whose instances are misclassified by $h$.}

\STATE $b \leftarrow \frac{4}{\sqrt{\epsilon}} \log\frac{16}{\delta_2} + (\frac{24}{\delta_2})^{1/1000}$.

\STATE Sample uniformly a subset $U \subset S$ of $b$ instances. $\bar{U} \leftarrow \textsc{Prune-Compare-and-Label}\xspace(U,\alpha,\beta, \delta_2/4)$.

\STATE Let $x^-$ be the rightmost instance of those labeled as $-1$, and $x^+$ be the leftmost instance of those labeled as $+1$.

\STATE $S_I \leftarrow \emptyset$, $S_{\text{in}} \leftarrow \emptyset$, $N \leftarrow \frac{1}{\beta^2}\log\frac{1}{\epsilon}$.

\IF{$\beta < 0.7$}{
\STATE Run \textsc{Test}\xspace$(x^-, \beta, \delta_2/8)$, \textsc{Test}\xspace$(x^+, \beta, \delta_2/8)$.
}
\ENDIF

\FOR{$x\in S\backslash U$}{

\STATE $\text{ANS} \leftarrow \text{YES}$.

\FOR{$t=1, \dots, N$}{

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

\STATE \textbf{If} $t$ is even, \textbf{then} {\bfseries continue} to the next iteration.

\STATE {Filtering: }\textbf{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]$, \textbf{then} $\text{ANS} \leftarrow \text{NO}$ and {\bfseries break}. \label{step:filter-outside}

}
\ENDFOR

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

\STATE \textbf{If} $\text{ANS} = \text{YES}$, \textbf{then} $S_I \leftarrow S_I \cup \{x\}$.

}
\ENDFOR

\STATE $\bar{S_{\text{in}}} \leftarrow \textsc{Prune-Compare-and-Label}\xspace(S_{\text{in}}, \delta_2/4,\alpha,\beta)$.

\STATE $S_I \leftarrow S_I \cup \{x: (x, y) \in \bar{U} \cup \bar{S_{\text{in}}}\ \text{and}\ y \neq h(x) \}$.

{\bfseries return} $S_I$.

\end{algorithmic}
\end{algorithm}

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~\cite{shen2020efficient} and integrate a new component, \textsc{Test}\xspace, that ensures to recover a distribution ${D}'$ 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 $\abs{S} = \Theta(n_{\epsilon,\delta})$. This constant load, however, contradicts with the sample-size-varying load we used in \textsc{Prune-Compare-and-Label}\xspace; 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~\ref{subsec:overview}), 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, \textsc{Test}\xspace works on a set of instances that is smaller than that \textsc{Semi-verified-Filter}\xspace works on. This is a key design to guarantee that the total comparison complexity does not blow up.

\begin{algorithm}[t]

	\caption{\textsc{Test}}
	\label{alg:test}

	\begin{algorithmic}[1]

		\REQUIRE {An instance $x'$, parameter $\beta$, confidence $\delta_2$.}

		\STATE Draw a set $S_r$ of $\frac{4}{\epsilon}\log\frac{8}{\delta_2}$ instances from ${D}_X$.

		\STATE  $N\leftarrow\frac{32}{\beta^2}\cdot\log(\frac{32\abs{S_r}}{\delta_2})$.

		\FOR{$x\in S_r$}{

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

			\IF{$\mathrm{Maj{\dash}size}_{\mathcal{W}}(x,x')< 1-\frac{\beta}{4}$}{

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

			}
			\ENDIF
		}
		\ENDFOR
	\end{algorithmic}

\end{algorithm}

\begin{lemma}\label{lem:test}
	If \textsc{Test} terminates without restarting Algorithm~\ref{alg:boost}, 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 \textsc{Test}\xspace is  $O\big(\frac{1}{\epsilon\beta^2}\log\big(\frac{1}{\delta_2}\big)\log\big(\frac{1}{\epsilon\delta_2}\big)\big)$.
\end{lemma}

In general, \textsc{Semi-verified-Filter}\xspace ensures that in Phase~2, the learner draws a set of $\Theta(n_{\sqrt\epsilon,\delta'})$ instances from a distribution ${D}'$ 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.

\begin{lemma}\label{lem:h2}
	Consider Phase~2 of Algorithm~\ref{alg:boost}, with probability $1-\frac{\delta'}{3}$, $\mathrm{err}_{{D}_2}(h_2)\leq\frac{\sqrt\epsilon}{2}$.
\end{lemma}

By Corollaries \ref{coro:h1}, \ref{coro:h3}, and the above lemma, we have three hypotheses $h_1,h_2,h_3$ that satisfy the requirement of Theorem~\ref{thm:boost}; 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~\ref{thm:main_bothAlphaBeta} follows; see Appendix~\ref{sec:proof} for the full proof.

\section{The Omitted Algorithmic Framework}\label{app_sec:alg}

\section{Omitted Proofs} \label{sec:proof}

\begin{lemma}\label{lem:alpha-restate}
Consider the \textsc{Semi-verified-BinarySearch}\xspace 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\bar{S}$, $y=h^*(x)$.
\end{lemma}
\begin{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{\dash}size}_{\mathcal{P}^{{L}}}(x)=\E[\mathrm{Maj{\dash}size}_{\mathcal{W}^{{L}}}(x)]$ for any $x$, by the  Chernoff bound, we have
	\begin{equation*}
	 \Pr\Big(\abs{\mathrm{Maj{\dash}size}_{\mathcal{P}^{{L}}}(x) - \mathrm{Maj{\dash}size}_{\mathcal{W}^{{L}}}(x)} \geq \frac{\alpha}{8}\Big) \leq 2\cdot e^{-2k_2\cdot(\frac{\alpha}{8})^2} = \frac{\delta_1}{3\log n}.
	\end{equation*}
	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$, $\abs{\mathrm{Maj{\dash}size}_{\mathcal{P}^{{L}}}(x) - \mathrm{Maj{\dash}size}_{\mathcal{W}^{{L}}}(x)} \leq \frac{\alpha}{8}$. Thus, if $\mathrm{Maj{\dash}size}_{\mathcal{W}^{{L}}}(x) \geq 1 - \frac{\alpha}{4}$, we must have $\mathrm{Maj{\dash}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\geq0.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\bar{S}, y=h^*(x)$. On the flip side, if the algorithm prunes due to $\mathrm{Maj{\dash}size}_{\mathcal{W}^{{L}}}(x) < 1 - \frac{\alpha}{4}$, we must have $\mathrm{Maj{\dash}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}}$.
\end{proof}

\begin{lemma}\label{lem:beta-restate}
	Consider the \textsc{Semi-verified-Quicksort}\xspace 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$.
\end{lemma}
\begin{proof}
	Given that $k_1 = \frac{1}{2\beta^{2}}\cdot\log\frac{3006n\cdot\log n }{\delta_1}$. By traditional guarantee of \textsc{Randomized Quicksort}\xspace, 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~\ref{lem:alpha}, we have $\mathrm{Maj{\dash}size}_{\mathcal{P}^{{C}}}(x,x')=\E[\mathrm{Maj{\dash}size}_{\mathcal{W}^{{C}}}(x,x')]$ for any $(x,x')$, and
	\begin{equation*}
	\Pr\[\bigcup_{l=1}^{1002n\log n} \[\abs{\mathrm{Maj{\dash}size}_{\mathcal{P}^{{C}}}(x,x')_l - \mathrm{Maj{\dash}size}_{\mathcal{W}^{{C}}}(x,x')_l} \leq \frac{\beta}{8} \]\] \leq \frac{\delta_1}{3}.
	\end{equation*}
	In other words, with probability $1-\frac{\delta_1}{3}$, the following is guaranteed. If $\mathrm{Maj{\dash}size}_{\mathcal{W}^{{C}}}(x,x') \geq 1 - \frac{\beta}{4}$, we must have $\mathrm{Maj{\dash}size}_{\mathcal{P}^{{C}}}(x,x') \geq 1 - \frac{3\beta}{8} > 1 - \beta$, indicating that $\mathrm{Maj}_{\mathcal{W}^{{C}}}(x,x') =  Z^*(x,x')$. Same guarantee holds when $\beta\geq0.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{\dash}size}_{\mathcal{W}^{{C}}}(x,x') < 1 - \frac{\beta}{4}$, we must have $\mathrm{Maj{\dash}size}_{\mathcal{P}^{{C}}}(x,x') \geq 1 - \frac{\beta}{8}$, meaning that by querying a verified comparison for $(x,x')$ we can remove at least $\frac{\beta}{8}$-fraction of the workers and update $\beta \leftarrow \frac{\beta}{1-\frac{\beta}{8}}$.
\end{proof}

\begin{proposition}[Restatement of Corollary~\ref{prop:complabel}]\label{prop:complabel-restate}
	Consider the \textsc{Prune-Compare-and-Label}\xspace algorithm, i.e. Algorithm~\ref{alg:label}. If the algorithm does not restart and $\abs{S}\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\abs{S})$ label queries and  $O(\frac{1}{\beta^2}\cdot \abs{S}\cdot\log^2\abs{S})$ comparison tags.
\end{proposition}
\begin{proof}
	See Lemma~\ref{lem:beta} and Lemma~\ref{lem:alpha}. If \textsc{Prune-Compare-and-Label}\xspace 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~\ref{prop:naive_complabel}.
\end{proof}

\begin{corollary}[Restatement of Corollary~\ref{coro:h1}]\label{coro:h1-restate}

	With probability $1-\frac{\delta'}{3}$, $\mathrm{err}_{{D}_X}(h_1)\leq\frac{\sqrt\epsilon}{2}$.
\end{corollary}
\begin{proof}
	By drawing a sample $S_1$ of $n_{\sqrt{\epsilon}/2,\delta'/6}$ from ${D}_X$ and labeling it by \textsc{Prune-Compare-and-Label}\xspace, with probability at least $1-\frac{\delta'}{6}$, $\bar{S_1}$ is labeled correctly according to $h^*$ (Proposition~\ref{prop:complabel}). Furthermore, we note that $n_{\sqrt{\epsilon}/2,\delta'/6} \geq m_{\sqrt{\epsilon}/2,\delta'/6}$. By Assumption~\ref{as:pac}, $\mathrm{err}_{{D}_X}(h_1)\leq\frac{\sqrt\epsilon}{2}$ with probability $1-\frac{\delta'}{3}$.
\end{proof}

\begin{corollary}[Restatement of Corollary~\ref{coro:h3}]\label{coro:h3-restate}

	With probability $1-\frac{\delta'}{3}$, $\mathrm{err}_{{D}_3}(h_3)\leq\frac{\sqrt\epsilon}{2}$.
\end{corollary}
\begin{proof}
	In Phase~3 of Algorithm~\ref{alg:boost}, by rejection sampling we can successfully sample a set $S_3$ of $n_{\sqrt{\epsilon}/2,\delta'/6}$ from ${D}_3$. Again by Proposition~\ref{prop:complabel} and Assumption~\ref{as:pac}, $\mathrm{err}_{{D}_3}(h_3)\leq\frac{\sqrt\epsilon}{2}$ with probability $1-\frac{\delta'}{3}$.
\end{proof}

\begin{lemma}
	\label{lem:restart_restate}
	$\forall\alpha,\beta\in(0,1]$, with probability $1-\delta$, Algorithm~\ref{alg:boost} 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})$.
\end{lemma}
\begin{proof}
	By Lemma~\ref{lem:alpha}, everytime we get a verified label from $\mathcal{E}$, we must prune some workers and increase $\alpha$ to $\alpha' = \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
	\begin{align}
	\alpha_{k} &= \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}} \notag\\
	&= \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}}, \notag
	\end{align}
	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,
	\begin{equation*}
	k = \frac{8(C-\alpha_0)}{C\alpha_0} = \frac{8}{\alpha_0} - \frac{8}{C}.
	\end{equation*}
	By setting $C=0.7$, we have that $k=\frac{8}{\alpha}-\frac{80}{7} = O(\frac{1}{\alpha})$. 	Similarly, by Lemma~\ref{lem:beta-restate}, it is guaranteed that with probability at least $1-\frac{2\delta_1}{3}$, each time Algorithm~\ref{alg:robust_quick_sort} prunes the workers, we would increase $\beta$ to $\beta'=\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. $\geq0.7$, such that the algorithm no longer prunes. Therefore, the main algorithm only restarts for $O(\frac{1}{\alpha} +\frac{1}{\beta})$ times.
\end{proof}

\begin{lemma}[Restatement of Lemma~\ref{lem:test}]\label{lem:test-restate}
	If \textsc{Test} terminates without restarting Algorithm~\ref{alg:boost}, 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 \textsc{Test}\xspace is  $O\big(\frac{1}{\epsilon\beta^2}\log\big(\frac{1}{\delta_2}\big)\log\big(\frac{1}{\epsilon\delta_2}\big)\big)$.
\end{lemma}
\begin{proof}
	Recall that by definition,
	\begin{align*}
		R_1 := \{x: \mathrm{Maj{\dash}size}_{\mathcal{P}^{{C}}}(x, x^-) \leq 1-\frac{\beta}{2} \}, \quad
		R_2 := \{ x: \mathrm{Maj{\dash}size}_{\mathcal{P}^{{C}}}(x, x^+) \leq  1-\frac{\beta}{2} \}.
	\end{align*}
	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
	\begin{equation}
	\ell_i=
	\begin{cases}
	1, & \text{if}\ \text{worker $i$ agrees with $\mathrm{Maj}_{\mathcal{P}^{{C}}}(x,x^-)$,} \\
	0, & \text{otherwise.}
	\end{cases}
	\end{equation}
	Since we query a set $\mathcal{W}$ of $N =\frac{32}{\beta^2}\cdot\log\big(\frac{32\abs{S_r}}{\delta_2}\big)$ workers from the crowd to compare $(x,x^-)$. Note that $\mathrm{Maj{\dash}size}_{\mathcal{P}^{{C}}}(x,x^-) = \E[\mathrm{Maj{\dash}size}_{\mathcal{W}}(x,x^-)] = \mu$, which is also the probability that $\ell_i=1$. Therefore, by Hoeffding's inequality we have
	\begin{align}
		\Pr\[\mathrm{Maj{\dash}size}_{\mathcal{W}}(x,x^-)\geq1-\frac{\beta}{4}\]
		&\leq \Pr\[\Big\lvert \mathrm{Maj{\dash}size}_{\mathcal{W}}(x,x^-)-\mathrm{Maj{\dash}size}_{\mathcal{P}^{{C}}}(x,x^-)\Big\rvert\geq\frac{\beta}{8} \] \notag\\
		&= \Pr\[\abs{\frac{1}{N}\sum_{i=1}^{N}\ell_i-\mu}\geq\frac{\beta}{8} \] \notag\\
		&\leq 2\cdot e^{-\frac{2N\cdot\(\frac{\beta}{8}\)^2}{(1-0)^2}} \notag\\
		&= 2\cdot e^{-2\cdot\frac{32}{\beta^2}\cdot\log\(\frac{32\abs{S_r}}{\delta_2}\) \cdot\(\frac{\beta}{8}\)^2} \notag\\
		&= \frac{\delta_2}{16\abs{S_r}}. \notag
	\end{align}
	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 \textsc{Test} terminates without restarting Algorithm~\ref{alg:boost}, the density ${D}_X[R_1]\leq\frac{\epsilon}{8}$ with probability $1-\frac{\delta_2}{8}$. Therefore, if Algorithm~\ref{alg:filter}  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 \textsc{Test}\xspace is
	\begin{equation}
		\frac{8}{\epsilon}\log\frac{16}{\delta_2} \cdot \frac{32}{\beta^2}\cdot\log\Big(\frac{8\abs{S_r}}{\delta_2}\Big)
		= O\Big(\frac{1}{\epsilon\beta^2}\log\frac{1}{\delta_2}\log\Big(\frac{1}{\epsilon\delta_2}\Big)\Big) .
	\end{equation}
\end{proof}

\begin{lemma}[Restatement of Lemma~\ref{lem:h2}]\label{lem:h2-restate}
	Consider Phase~2 of Algorithm~\ref{alg:boost}, with probability $1-\frac{\delta'}{3}$, $\mathrm{err}_{{D}_2}(h_2)\leq\frac{\sqrt\epsilon}{2}$.
\end{lemma}
\begin{proof}
	Let $R := R_1 \cup R_2$.
	By Lemma~\ref{lem:test}, with probability $1-\frac{\delta_2}{4}$,  ${D}_X[R] \leq\frac{\epsilon}{4}$.
	We first argue that for any $x\notin R$, \textsc{Semi-verified-Filter}\xspace does a good job to simulate ${D}_I$.
	Consider distribution ${D}'$ that has equal probability on the distributions induced by $\bar{W}_I$ and $\bar{W}_C$ and let $d'(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'(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 12\sqrt{\epsilon})$. Similarly, for any $x$ such that $h_1(x) \neq h^*(x)$, we have $d_X(x) = d_I(x)\frac 12 \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$, $\bar{W_C}$ and $\bar{W_I}$, respectively.
	For any $x$, there are two cases:

	\medskip
	\noindent{If $h_1(x) = h^*(x)$:} Then, there exist absolute constants $c_1$ and $c_2$ according to Lemma~\ref{lem:SIsize}, such that
	\begin{align}
	d'(x)&= \frac 12 \E\left[ \frac{M_C(x)}{|\bar{W_C}|} \right] \geq \frac{\E[M_C(x)]}{ c_1 \cdot  m_{\sqrt \epsilon} } \geq \frac{\E[N_C(x)]}{c_1 \cdot  m_{\sqrt \epsilon} }
	= \frac{| S_C | \cdot d_X(x) }{c_1 \cdot  m_{\sqrt \epsilon} } \notag\\
	&= \frac{| S_C | \cdot d_C(x) \cdot (1- \frac 12 \sqrt{\epsilon}) }{c_1 \cdot  m_{\sqrt \epsilon} }
	\geq c_2 d_C(x) = \frac{c_2 d_2(x)}{2}, \notag
	\end{align}
	where the second and sixth transitions are by the sizes of $\bar{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)$.

	\noindent{If $h_1(x) \neq h^*(x)$:} Then, there exist absolute constants $c'_1$ and $c'_2$ according to Lemma~\ref{lem:SIsize}, such that
	\begin{align}
	d'(x) &= \frac 12 \E\left[ \frac{M_I(x)}{|\bar{W_I}|} \right] \geq \frac{\E[M_I(x)]}{c'_1 \cdot  m_{\sqrt \epsilon} }
	\geq \frac{\E[N_I(x)]}{c'_1 \cdot  m_{\sqrt \epsilon} }
	\geq \frac{ \frac 4 7~  d_X(x) | S_2|}{c'_1 \cdot  m_{\sqrt \epsilon} } \notag\\
	&= \frac{ \frac 4 7~  d_I(x) \frac 12 \sqrt{\epsilon} \cdot | S_2| }{c'_1 \cdot  m_{\sqrt \epsilon} }
	\geq  c'_2 d_I(x) = \frac{c'_2 d_2(x)}{2}, \notag
	\end{align}
	where the second and sixth transitions are by the sizes of $\bar{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~\ref{lem:composite-Filter}.

	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'(x)\geq \Theta(d_2(x))$, meaning that ${D}'$ is a good simulation of ${D}_2$. 	By Lemma~\ref{lem:h2}, since $\abs{\bar{W}}=\Theta(n_{\sqrt\epsilon,\delta'})$, applying the super-sampling lemma (Lemma~\ref{lem:super}) we know that $\mathrm{err}_{{D}_2}(h_2) \leq O(\frac{\sqrt\epsilon}{2})$ with probability .
\end{proof}

\begin{theorem}[Restatement of Theorem~\ref{thm:main_bothAlphaBeta}]\label{thm:main_bothAlphaBeta_restate}
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\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\(0,(\log d)^{-4}\)$.
\end{theorem}
\begin{proof}

	Following Corollary~\ref{coro:h1}, \ref{coro:h3}, Lemma~\ref{lem:h2} and Lemma~\ref{lem:restart_restate}, 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~\ref{thm:boost}, the classifier $\hat{h}$ returned by Algorithm~\ref{alg:boost} 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~\cite{shen2020efficient} (Theorem~\ref{thm:base}), 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'}) = O((\frac{1}{\alpha}+\frac{1}{\beta})\cdot\frac{1}{\delta})$.
	\begin{align}
		m_L &= \Big(\frac{1}{\alpha}+\frac{1}{\beta}\Big) \cdot O\Big(\frac{1}{\alpha^2}\cdot\log n_{\sqrt\epsilon,\delta'} \cdot \log\log n_{\sqrt\epsilon,\delta'} \Big) \notag\\
		&= \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), \notag
	\end{align}
	On the other hand, the comparison complexity is a summation of that in~\textsc{Test}\xspace and \cite{shen2020efficient}, multiplying by a factor of  $O(\frac{1}{\alpha}+\frac{1}{\beta})$,
	\begin{align}
		m_C &= \Big(\frac{1}{\alpha}+\frac{1}{\beta}\Big) \cdot O\bigg(\frac{1}{\beta^2}\cdot n_{\sqrt{\epsilon},\delta'} \cdot \log^2 n_{\sqrt{\epsilon},\delta'} + n_{\epsilon,\delta'} + \frac{1}{\epsilon\beta^2}\log\Big(\frac{1}{\delta'}\Big)\log\Big(\frac{1}{\epsilon\delta'}\Big) \bigg) \notag \\
		&= \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) \notag \\
		&= \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} \notag\bigg)
	\end{align}

	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:
	\begin{align}
		\Lambda_{L} &= O\bigg( \frac{1}{\alpha^2}\Big(\frac{1}{\alpha}+\frac{1}{\beta}\Big) \cdot \frac{ \log n_{\sqrt{\epsilon},\delta'} }{m_{\epsilon,\delta}} \cdot  \log {\log n_{\sqrt{\epsilon},\delta'}} \bigg) \notag\\
		&\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) \notag\\
		&= \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), \notag
	\end{align}
	and
	\begin{align}
		\Lambda_{C} &= \frac{1}{\beta^2}\Big(\frac{1}{\alpha}+\frac{1}{\beta}\Big)\cdot O\Bigg(\frac{n_{\sqrt{\epsilon},\delta'}}{m_{\epsilon, \delta}} \cdot \log^2 n_{\sqrt{\epsilon},\delta'} + \frac{n_{\epsilon,\delta'}}{m_{\epsilon,\delta}} + \frac{\frac{1}{\epsilon}\log\big(\frac{1}{\delta'}\big)\log\big(\frac{1}{\epsilon\delta'}\big)}{m_{\epsilon,\delta}} \Bigg) \notag\\
		&\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) \notag\\
		&\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) \notag\\
		&\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) \notag\\
		&\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) \notag
	\end{align}

	Recall that by the definition of $n_{{\epsilon}, \delta}$ and $m_{\epsilon, \delta}$ in Section~\ref{sec:setup}, 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
	\begin{equation*}
	\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).
	\end{equation*}
	When $\epsilon\in\(0,(\log d)^{-4}\)$, $\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$.
\end{proof}

\section{Useful Lemmas}\label{subsec:useful_lemmas}

\begin{lemma}[Robust Super-Sampling Lemma, {Lemma 4.12} in~\cite{awasthi2017efficient}]\label{lem:super}
	Given a hypothesis class $\H$ consider any two discrete distributions ${D}$ and ${D}'$ 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'(x)\geq c\cdot d(x)$ for an absolute constant $c>0$ and both distributions are labeled according to $h^*\in\H$. There exists a constant $c'>1$ such that for any $\epsilon,\delta$, with probability $1-\delta$ over a labeled sample set $S$ of size $c'm_{\epsilon,\delta}$ drawn from ${D}'$, $\O_\H(S)$ has error of at most $2\epsilon$ with respect to $D$.
\end{lemma}

\begin{lemma}[{Lemma 22} in~\cite{shen2020efficient}]\label{lem:composite-Filter}
	Consider Algorithm~\ref{alg:filter}. 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 $\frac14\sqrt{\epsilon}$; if $h(x)\neq h^*(x)$, it goes to $S_I$ with probability at least $\frac{4}{7}$.
\end{lemma}
\begin{proof}
 	Follow the guarantee of Lemma~\ref{lem:test}. 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{\dash}size}_{\mathcal{P}^{{C}}}(x,x')\geq1-\frac{\beta}{2},x'\in\{x^-,x^+\}$.
	Consider any instance $x \in S$ outside the interval $[x^-, x^+]$. When $\beta<0.7$, $\mathrm{Maj{\dash}size}_{\mathcal{P}^{{C}}}(x,x')\geq \frac12+\Theta(1)$ which suffices for the filtering scheme from~\cite{awasthi2017efficient} to work and the guarantee follows from the Lemma~{4.2} in that work. If $\beta\geq0.7$, lemma follows from that of~\cite{shen2020efficient}.
	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 \textsc{Prune-Compare-and-Label}\xspace. 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.
\end{proof}

\begin{lemma}[{Lemma 4.7} in~\cite{awasthi2017efficient}] \label{lem:SIsize}
	With probability at least $1-\exp(-\Omega(n_{\sqrt{\epsilon},\delta'}))$, $\bar{W}_I$, $\bar{W}_C$ and $S_I$ all have size $\Theta(n_{\sqrt{\epsilon},\delta'})$.
\end{lemma}
\begin{proof}
	Notice that $n_{\epsilon,\delta'} = \Omega(m_{\epsilon,\delta'})$, the lemma follows from~\cite{awasthi2017efficient}.
\end{proof}

The following two results from \cite{shen2020efficient} will be useful.

\begin{proposition}[Prop. 3 in \cite{shen2020efficient}]\label{prop:naive_complabel}
Suppose $\alpha\geq0.7,\beta\geq0.7$. Consider the \textsc{Prune-Compare-and-Label}\xspace algorithm, i.e. Algorithm~\ref{alg:label}. If $\abs{S} \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\abs{S}\cdot\log{\log\abs{S}} \big)$, and the comparison complexity is given by $O\big(\abs{S}\cdot\log^2\abs{S}\big)$.
\end{proposition}
\begin{theorem}[Theorem 7 in \cite{shen2020efficient}]\label{thm:base}
Suppose $\alpha\geq0.7,\beta\geq0.7$. With probability $1-\delta$, Algorithm~\ref{alg:boost} runs in time $\mathrm{poly}(d,\frac{1}{\epsilon})$ and returns a classifier $h\in\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\( n_{\sqrt{\epsilon},\delta}\log^2 n_{\sqrt{\epsilon},\delta}+n_{\epsilon,\delta}\)$.
\end{theorem}

\section{Conclusion and Future Works}\label{sec:conclusion}

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.

\section{Introduction}\label{sec:intro}

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~\cite{angluin1987learning}, Massart noise~\cite{sloan1988types,massart2006risk}, Tsybakov noise~\cite{tsybakov2004optimal}, and agnostic noise~\cite{haussler1992decision,kearns1992toward}. In recent years, under certain distributional assumptions on the unlabeled data, a variety of computationally efficient algorithms have been established with PAC guarantees~\cite{zhang2020efficient,diakonikolas2020learning,diakonikolas2020polynomial,awasthi2017power}. The success of these algorithms, however, crucially relies on one or more of the following conditions: {\bfseries 1)} there are sufficient number of labeled data; {\bfseries 2)} the majority of the labels are correct; and {\bfseries 3)} the marginal distribution of the unlabeled data is well-behaved.

Establishing PAC guarantees {\em 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 {\em learning with enriched queries}; to address the violation of the second condition, the {\em semi-verified model} (also known as list-decodable model) has been proposed; to complement the absence of the last condition, the {\em crowdsourced PAC model} has been put forward. We elaborate on each line of research in the following.

{\bfseries 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~\cite{park2015preference}. 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~\cite{kane2017active,xu2017noise,hopkins2019power}.

{\bfseries 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 \cite{haussler1992decision,kearns1992toward}. 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 \cite{charika2017learning}. Such model has been extensively studied for mean estimation, linear regression, subspace recovery, to name a few; see \cite{diakonikolas2018list,karmalkar2019list,cherapanamjeri2020,raghavendra2020subspace,bakshi2021list} and the references therein.

{\bfseries 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~\cite{guruswami2006hardness,feldman2006new}. Therefore, most positive results are established under distributional assumptions on the unlabeled data, say Gaussian or log-concave~\cite{awasthi2017power,zhang2020efficient,diakonikolas2020learning,diakonikolas2020polynomial}. Very recently, \cite{awasthi2017efficient,shen2020efficient} 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: \cite{awasthi2017efficient} broke the second condition, that is, their algorithm works under the semi-verified setting, whereas \cite{shen2020efficient} broke the first condition, that is, their algorithm is label-efficient.

In this paper, we consider the following question:
\begin{quote}
Can we PAC learn the class of threshold functions when {\em all} of these conditions are violated?
\end{quote}

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''.

\subsection{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 $\H = \{h: x \mapsto \sign{f(x)}, f \in \mathcal{F}\}$. For example, when $\mathcal{F} = \{f_w: x \mapsto w \cdot x\}$, $\H$ is the class of halfspaces, also known as linear threshold functions. We focus on the classical realizable setting of \cite{valiant1984theory}, where there is an underlying threshold function $h^*(x) = \sign{f^*(x)}$ 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 \cite{valiant1984theory}, which we call the {\em standard PAC learning model}. Namely,
\begin{assumption}\label{as:pac}
There exists an efficient algorithm $\mathcal{A}_\H$ satisfying the following: for any $\epsilon, \delta \in (0, 1)$, $\mathcal{A}_\H$ draws $m_{\epsilon, \delta}$ {\em 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}_\H$ a {\em standard PAC learner}.
\end{assumption}
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
\begin{equation}
m_{\epsilon,\delta} = K \cdot \frac{1}{\epsilon} \cdot \Big( d \log\frac{1}{\epsilon} + \log\frac{1}{\delta} \Big),
\end{equation}
where $K \geq 1$ is some absolute constant and $d$ is the VC-dimension of the class $\H$ \cite{kearns1994intro}.

For any pair of instances $(x, x') \in \mathcal{X} \times \mathcal{X}$, the underlying comparison function is given by $Z^*(x, x') = \sign{f^*(x) - f^*(x')}$. 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'$'' reads as ``is $f^*(x) > f^*(x')$''. 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
\begin{equation}
n_{\epsilon,\delta} := K \cdot \frac{1}{\epsilon} \cdot \Big( d \log\frac{1}{\epsilon} + \Big(\frac{1}{\delta}\Big)^{10^{-3}} \Big),
\end{equation}
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~\cite{ho2013adaptive,khetan2016achieve}. 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 {\em labeling overhead} and {\em 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 {\em 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 {\em 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.

\subsection{Main results}\label{subsec:main_result}

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.

\begin{theorem}\label{thm:main_bothAlphaBeta}
For any $\alpha, \beta, \epsilon, \delta \in (0, 1)$, Algorithm~\ref{alg:boost} 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\(0,(\log d)^{-4}\)$. 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)$.
\end{theorem}

\begin{remark}\label{rmk:onlyAlpha}
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~\cite{awasthi2017efficient}, 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.
\end{remark}

\subsection{Overview of techniques}

The starting point of our  algorithmic design is the results from \cite{shen2020efficient}, which shows that if $\alpha\geq0.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'$ and $\beta'$ respectively, such that $\alpha'\geq0.7$ and $\beta' \geq 0.7$, for which the algorithm of \cite{shen2020efficient} 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 \cite{awasthi2017efficient}.

Our new technical insight is a {\em 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 \cite{shen2020efficient}; 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 \cite{shen2020efficient} 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 \cite{shen2020efficient} 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 \cite{shen2020efficient} 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 < \frac12$ roots in their filtering process, which roughly speaking, will perform majority voting over a {\em 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.

\subsection{Roadmap}

In Section~\ref{sec:related}, we describe the related works. Section~\ref{sec:setup} gives additional background and notations in crowdsourced PAC learning. In Section~\ref{sec:algorithm}, we present our main algorithm and its theoretical guarantees. The conclusion is given in Section~\ref{sec:conclusion}, and the proof details are deferred to the appendix.

\section{Related Works}\label{sec:related}

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~\cite{cohn1994improving}. 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~\cite{balcan2007margin,hanneke2014theory,awasthi2017power}. 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~\cite{jamieson2011active,shah2016stochastic,shah2017simple,falahatgar2017max,shah2019feel,agarwal2020rank}, best-$k$ item selection~\cite{falahatgar2017max,ren2020sample}, and recommendation systems~\cite{furnkranz2010prefer,falahatgar2018limit}. More in line with this work is PAC learning with pairwise comparisons~\cite{kane2017active,xu2017noise,hopkins2019power,hopkins2020noise}; 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 \cite{charika2017learning}, 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~\cite{kothari2017better,dia2020list,raghavendra2020list}, learning mixtures of Gaussian~\cite{dia2018list}, linear regression~\cite{karmalkar2019list,raghavendra2020list}, and subspace recovery~\cite{bakshi2020list,raghavendra2020subspace}. Under the crowdsourcing setting, \cite{steinhardt2016avoid,meister2018data} considered recovery of true values of a finite data set and \cite{awasthi2017efficient} examined PAC learnability which aligns more closely with our work. In fact, our algorithm shares the merits with \cite{awasthi2017efficient} but we carefully leverage comparison queries to achieve label efficiency. We emphasize that crowdsourced PAC learning was also investigated in \cite{shen2020efficient}, but their algorithm fails immediately when the majority are incorrect.

\section{Preliminaries}\label{sec:setup}

{\bfseries 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~\cite{cohn1994improving}. 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{\dash}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{\dash}size}_{\P}(z) = \max\{ \Pr_{t\sim\P}( h_t(z) = 1), \Pr_{t\sim\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 $\P$ over workers and an annotated set $S$ (either a set with labels or one with comparison tags), denote by $\P_{\mid S}$ the distribution $\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}$.