{'fraction_non_alphanumeric': 0.04722380063316828, 'fraction_numerical': 0.01972562708012014, 'mean_word_length': 3.95296009649211, 'pattern_counts': {'":': 0, '<': 6, '<?xml version=': 0, '>': 13, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 14, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Learning Halfspaces with Pairwise Comparisons: Breaking the Barriers of Query Complexity via Crowd Wisdom

In this paper, we study the problem of efficient learning of halfspaces under Massart noise. This is a challenging noise model and only very recently has significant progress been made for problems with sufficient labeled samples. We consider the more practical yet less explored setting where the learner has a limited availability of labeled samples, but has extra access to pairwise comparisons. For the first time, we show that even when both labels and comparisons are corrupted by Massart noise, there is a polynomial-time algorithm that provably learns the underlying halfspace with near-optimal query complexity and noise tolerance, under the distribution-independent setting. In addition, we present a precise tradeoff between label complexity and comparison complexity, showing that the former is order of magnitude lower than the latter, making our algorithm especially suitable for label-demanding problems. Our central idea is to appeal to the wisdom of the crowd: for each instance (respectively each pair of instances), we query the noisy label (respectively noisy comparison) for a number of times to alleviate the noise. We show that with a novel design of an filtering process, together with a powerful boosting framework, the total query complexity is only a constant times more than learning from experts.


Introduction
Learning of halfspaces has been one of the most important problems in machine learning dating back to the Perceptron algorithm [Rosenblatt, 1958]. In noise-free settings, where all the labels are consistent with some underlying hypothesis, it is well-known that the problem can be solved in polynomial time by linear programming [Maass andTurán, 1994, Cristianini andShawe-Taylor, 2000]. However, in real-world scenarios, labels are often corrupted, which has driven a large body of works on designing computationally efficient and noise-tolerant algorithms. For instance, Blum et al. [1996] proposed a polynomial-time algorithm that recovers the underlying hypothesis in presence of random classification noise, where each label is flipped with probability exactly equal to 1 2 − α for some α ∈ (0, 1 2 ]. A more realistic model, called Massart noise (also known as bounded noise), was proposed in Sloan [1988Sloan [ , 1992, Massart and Nédélec [2006] as a generalization to the random classification noise. In this noise model, the label of each instance x i could be flipped with different probability 1 2 − α i ≤ 1 2 − α, where α i is unknown but its lower bound α ∈ (0, 1 2 ] is given to the learner. The quantity η := 1 2 − α is termed the Massart noise rate, and α is called the Massart parameter. Due to the highly asymmetric nature of this noise type, however, it is much more challenging to design computationally and query efficient algorithms. Generally speaking, most of the existing theoretical analyses of learning halfspaces with Massart noise are based on the framework of probably approximately correct (PAC) learning, and can be categorized as either distribution-dependent or distribution-independent in terms of the instance space. In the distribution-dependent setting, there have been a considerable number of works that developed polynomial-time algorithms that can achieve any error rate > 0, though with different noise tolerance and label complexity. For example, Awasthi et al. [2015] initiated the study of distribution-dependent PAC learning with Massart noise by assuming that the instance distribution is uniform over a unit sphere, and obtained a computationally efficient algorithm which can tolerate small constant noise rate η ≤ 1.8 × 10 −6 . The same distributional condition was also studied in  and Yan and Zhang [2017], where they successfully handled any noise rate η < 1 2 and obtained label complexity polynomial in poly(d, 1 α , 1 ). Awasthi et al. [2016] investigated whether there exist polynomial algorithms that work for the broad family of isotropic log-concave distributions, which covers prominent distributions such as logistic distribution and normal distribution. They showed that using the technique of polynomial regression, it is possible to obtain label complexity bound of d 2 poly(1/α) /poly( ), which was the first result that has an explicit dependence on α under this family of distributions. Recently, Zhang et al. [2020] and Diakonikolas et al. [2020] concurrently improved this result to O(d/α c ), for some small constant c ≥ 4. It is worth noting that a label complexity lower bound of Ω(d/α 2 ) was provided in Yan and Zhang [2017] for uniform distribution over the unit sphere, whereas it remains an open question of whether it is possible to obtain such bound under isotropic log-concave distributions [Zhang et al., 2020].
Compared to the rich literature of distribution-dependent PAC learning with Massart noise, less is known for the significantly more challenging setting of distribution-independent learning. In fact, this is a long-standing open problem and only very recently has a polynomial-time algorithm been developed by Diakonikolas et al. [2019], which obtains error rate of η + with label complexity O(1/γ 3 ) where γ > 0 is the large margin parameter of the underlying hypothesis. This bound was further improved to O(1/γ 2 ) with same error rate in Chen et al. [2020]. This naturally raises the first question: can we design a computationally efficient algorithm under the distribution-independent setting, such that it can achieve an error rate of ?
On the other spectrum, the success of all the aforementioned algorithms hinges on the condition that there are sufficient labeled samples available to the learner, which could be stringent on both practical and theoretical aspects. On the practical side, labels are extremely expensive to gather for many applications. For example, in medical diagnosis, a precise evaluation of an individual's health is difficult even for medical specialists, but it is often easier to compare the status of two different patients. On the theoretical side, a number of recent works have discovered the fundamental limitation of label-only algorithms, and have suggested to leverage pairwise comparisons as a remedy [Kane et al., 2017, Xu et al., 2017, Hopkins et al., 2019. Kane et al. [2017] considered the noise-free setting and built up a framework on which learning of halfspaces costs exponentially fewer labels as long as a combinatorial quantity k is small. Concurrently, Xu et al. [2017] proposed a noise-tolerant algorithm using O(log d) labels and O(d) comparisons, by assuming the underlying distribution is isotropic log-concave and the comparison tags are corrupted by adversarial noise. Later, Hopkins et al. [2020] extended the framework of Kane et al. [2017] to handle the setting that both labels and comparison tags are corrupted by Massart noise. Under s-concave distributions, they obtained query complexity O(k/α 10 ) while their algorithm runs in time poly(d 1/α 5 ), which is computationally efficient only when the Massart parameter α is a constant. This raises our second question: can we design a polynomial-time algorithm that efficiently leverages both types of noisy queries, while still achieving a query complexity quadratic in the Massart parameters as in the label-only case?
In this paper, we answer the two questions in the affirmative. We show that, what is extremely hard in standard PAC setting, is surprisingly easy if we appeal to the wisdom of the crowd. The main idea is to query the label multiple times for each instance (likewise for comparison tag), which significantly mitigates the effect of Massart noise. However, this may cause a serious issue that the query complexity could be orders of magnitude larger than what we obtain in the standard setting (i.e. query each instance for one time). As a matter of fact, we will present a natural approach in Section 3 which naively applies the idea to learn halfspaces with both labels and comparisons, and we show that such natural approach always needs log m times more queries than that of standard approach. Hence, to break the barrier we design a computationally efficient algorithm that interleaves learning and querying, and we provably show that this multiplicative logarithmic factor in query complexity can be removed. We remark that the idea of using the crowd wisdom to alleviate the Massart noise was explored in [Awasthi et al., 2017b] for label-only applications, which does not extend to problems with both label and comparison queries. Indeed, in order to efficiently leverage the comparison oracle, we have to develop a new filtering scheme to detect the most informative pairs to compare, which is the core technical contribution in this work.

Summary of our contributions
We study the problem of efficient learning halfspaces with both labels and comparisons corrupted by Massart noise. We present the first polynomial-time algorithm that provably learns the underlying halfspace with near-optimal query complexity and noise tolerance in distribution-independent setting. We show that, by carefully designing the filtering process, together with a powerful boosting framework we keep a query complexity that is only a constant times more than that of learning from experts (noiseless case). Our algorithm consists of three crucial components, as stated below.
1) Mitigating labeling by comparison. Given that the learner only has a limited availability of labeled samples, we exploit the power of pairwise comparisons to mitigate the labeling cost. In particular, we will first sort all the instances with a manageable number of comparisons. Under mild conditions, we show that all the instances are sorted correctly with high probability, based on which it suffices to find a "threshold instance" where the labels shift. In particular, if the data set size is m, then the label complexity and comparison complexity are polylog(m) and O(m log 2 m) respectively. See a more formal statement in Section 3.1.
2) Interleaving learning and annotation. In order to fully make use of the crowd feedback, we present an adaptive query scheme that interleaves learning and feedback gathering. Namely, we will first learn a weak hypothesis h 1 , based on which the algorithm concentrates on identifying the instances where h 1 may make mistakes on, and query the crowd to obtain the labels for these instances. Therefore, we can learn another hypothesis that complements h 1 . The identification process, or the filtering process, is the most crucial component in our algorithm. Informally speaking, we first construct an interval using a small amount of labels and comparison tags where instances outside it are informative. For each of those instances, we use pairwise comparison to determine if h 1 will misclassify. This ensures that our query complexity is manageable. See a more formal statement in Section 4.
3) Boosting weak learners. As we carefully limited the label and comparison complexity, the obtained hypotheses might be suboptimal. Hence, we appeal to a standard boosting framework which integrates the weak learners into a strong hypothesis with desired error rate.
Our algorithm naturally implies a tradeoff between labels and comparisons (see Table 2): without any additional information or queries, the best-known label complexity is Θ m α 2 [Awasthi et al., 2017b]; while both types of queries are allowed, we obtain an exponentially improved label complexity ofÕ log 2 m α 2 1 , with a tradeoff of O m β 2 comparisons.
Roadmap. In Section 2, we introduce more related works that address crowdsourcing and learning with pairwise comparison. In Section 3 we present the detailed problem setup and a natural approach. In Section 4, we present our main algorithm and theoretical analysis. We conclude this paper in Section 5, and the proof details are deferred to the appendix.

Related Works
PAC learning of halfspaces. Learning halfspaces is a long-standing problem in machine learning, dating back to the Perceptron algorithm [Rosenblatt, 1958]. The problem is extensively studied in the past few decades under the standard PAC learning model [Valiant, 1984, Sloan, 1992, Kearns and Valiant, 1988, Kearns et al., 1992, Blum, 1990, Blum et al., 1996, Kalai et al., 2005, Klivans et al., 2009, and a large body of recent studies showed significant progress of near-optimal performance guarantee in terms of noise tolerance, sample complexity, and label complexity [Awasthi et al., 2017a, Zhang, 2018, Diakonikolas et al., 2019, Zhang et al., 2020 Learning with comparisons. Pairwise comparison has been widely applied in practical problems and a large volume of works have established performance guarantee under different setting. For example, Fürnkranz and Hüllermeier [2010], Park et al. [2015] considered the problem of estimating users' preference to items by presenting pairs of items and collecting the preferences. In particular, under the matrix completion framework [Candès and Recht, 2009], it was shown in Park et al. [2015] that with mild assumptions recovery of the true preference is possible. Wah et al. [2014] studied the problem of image retrieval and interactive classification based on similarity comparisons. There is also a large body of works investigating the ranking problem based on pairwise comparison, which is either parametric [Jamieson and Nowak, 2011, Heckel et al., 2016, Shah et al., 2015 or non-parametric , Shah and Wainwright, 2017, Pananjady et al., 2017, Shah et al., 2019. Apart from that, Heckel et al. [2018] proposed an active ranking algorithm for estimating an approximate ranking, whereas another line of research focuses on finding exact rankings [Hunter et al., 2004, Negahban et al., 2012, Hajek et al., 2014. Interestingly, Balcan et al. [2016] studied the problem of learning close approximations to underlying combinatorial functions through pairwise comparisons, and they showed that a broad class of functions can be provably learned.
Learning from the crowd. The noise in crowd mainly comes from the imperfectness of its workers. A body of research assumes each instance is presented to multiple workers, enabling algorithmic designs for aggregating annotations to improve the quality of labels [Aydin et al., 2014, Fan et al., 2015, Ho et al., 2013, Karger et al., 2011, Khetan and Oh, 2016, Liu et al., 2012, Raykar et al., 2010, Shah and Lee, 2018, Tian and Zhu, 2015, Welinder et al., 2010. The Dawid-Skene model is a prominent choice for algorithmic design where the worker's quality parameter and instance labels are updated alternatively to achieve a higher-quality classifier, and has been widely examined [Ho et al., 2013, Fan et al., 2015, Khetan and Oh, 2016, Zhang et al., 2016, Zhou et al., 2012. Another line of research has been focused on pruning low-quality workers. For instance, Dekel and Shamir [2009] pre-trained a model on the entire data set and reweighted the labels from each worker based on his performance with respect to the pre-trained hypothesis. Awasthi et al.
[2017b] constructed a graph that identifies all high-quality workers by discovering and making use of a community structure presented in the crowd, with the observation that high-quality workers would often form a large connected component in the graph. Other works proposed to design better incentive mechanisms, for instance, a mechanism based on peer prediction [Jurca and Faltings, 2009, Miller et al., 2009, Radanovic et al., 2016, answers with confidence [Shah and Zhou, 2016], penalty for blind agreement [Dasgupta and Ghosh, 2013].

Preliminaries
We study the problem of learning halfspaces with Massart noise, with access to both labels and comparison tags from the crowd. Let X ⊂ R d be the instance space and Y = {−1, 1} be the set of possible labels for each x ∈ X . Let D be the joint distribution over X × Y, and denote by D X the marginal distribution on X . Let H = {h : X → Y} be the hypothesis classes. The error rate of a hypothesis h ∈ H over D is defined as err D (h) = Pr (x,y)∼D (h(x) = y). We consider the realizable setting, where there exists a hypothesis h * ∈ H such that err D (h * ) = 0, i.e. y = h * (x). In order to incorporate the pairwise comparisons, we consider a natural extension that has been widely used [Xu et al., 2017, Hopkins et al., 2020: for each pair of instances (x, x ) ∈ X × X , there is an underlying zero-error comparison function Z * (x, x ), which outputs 1 if x ≥ x and −1 otherwise. Here, we slightly abuse the notation x ≥ x to indicate that x is more likely a positive instance than x is. In the context of linear classifiers, observe that any hypothesis h ∈ H can be expressed as h w (x) = sign (w · x), and thus Z * (x, x ) = sign (w * · (x − x )) where w * is the parameter of h * .
Standard PAC learning. We will always be interested in the ( , δ)-PAC learnable classes H in the paper. That is, for any , δ ∈ (0, 1), there exists a learning algorithm which takes as input m ,δ correctly labeled instances drawn from D and returns a hypothesis h such that, with probability at least 1 − δ, err D (h) ≤ . In view of the classic VC theory [Anthony and Bartlett, 2002], it suffices to pick where d is the VC dimension of the hypothesis class H. We will reserve m ,δ for the above expression. In our analysis, we concentrate on the dependence on . Hence, we will often use a shorthand m in place of m ,δ , and thus m can roughly be thought of asÕ(1/ ).
Learning from the crowd. Although we assumed the existence of a perfect hypothesis, the learner only has access to two noisy oracles, a label revealing oracle O L and a pairwise comparison oracle O C . Let P be the distribution of crowd workers. The oracle O L takes as input an instance x ∈ X and returns a label y by querying a crowd worker i randomly drawn from a distribution P, while the other oracle O C takes as input a pair of instances (x, x ) ∈ X × X , and returns a tag z ∈ {−1, 1} by querying a worker j ∼ P. For a given instance x (respectively a pair (x, x )), by querying O L (respectively O C ) multiple times, it is possible to collect a set of different responses due to the Massart noise. To be more concrete, we consider the following scenario: there exist a large pool of crowd workers, at least an a fraction of which are reliable and return correct answer w.r.t. h * with probability at least p; while the other 1 − a perform arbitrarily, i.e. they might provide adversarial feedback. In other words, for a given instance, each time O L will return its correct label with probability bounded from below by p · a = 1 2 + α. Here, we assume α ∈ (0, 1 2 ] that ensures the correctness of majority. Likewise, for a given pair of instances, each time O C will return their correct comparison tag with probability at least 1 2 + β, where β ∈ (0, 1 2 ]. We define label complexity as the total number of calls made to O L , and the comparison complexity as that of calls made to O C . The total query complexity will be the sum of them. For a learning algorithm that ( , δ)-PAC learns a classifier, we measure its performance by its overhead, or average cost per labeled instance as introduced in Awasthi et al. [2017b], which is defined as the ratio of total query complexity to m ,δ , the number of instances needed to ( , δ)-PAC learn a hypothesis under the standard PAC setting. Likewise, we define the labeling overhead, denoted by Λ L , for labeling oracle and the comparison overhead, denoted by Λ C , for the comparison oracle.
Given a set of annotations A = {a 1 , . . . , a n } (either the labels or comparison tags), we define Maj(A) as outcome by majority vote. Specifically, suppose h 1 , h 2 and h 3 are three classifiers in H. The function Maj(h 1 , h 2 , h 3 ) maps any instance x to a label y, which is the outcome of majority vote of h 1 (x), h 2 (x) and h 3 (x).
Our theoretical analysis will depend on two mild assumptions, as stated below.
Assumption 1. There exists a polynomial-time algorithm O H that ( , δ)-PAC learns H using m ,δ correctly labeled samples. In addition, there exists a hypothesis h * : X → Y with zero classification error over D, and a comparison function Z * : X × X → {−1, 1} with zero comparison error over D × D.
Assumption 2. For any given instance, each time O L returns its correct label with probability at least 1 2 + α; and for any given pair of instances, each time O C returns their correct comparison tag with probability at least 1 2 + β. Here α ∈ (0, 1 2 ] and β ∈ (0, 1 2 ] are given to the learner.
Observe that Assumption 1 can be easily met since we presume that all the instances are correctly labeled, and there is a rich literature on efficient PAC learning of halfspaces [Rosenblatt, 1958, Valiant, 1984, Maass and Turán, 1994. Alternatively, one can think of Assumption 2 as that each worker i ∼ P gives a correct label with probability 1 2 + α i , where α i ≥ α. In that case, Assumption 2 can be reduced to standard Massart setting when the crowd only includes a single worker. However, we remark that there always exists a large pool of workers in the crowd, which Algorithm 1 Compare-and-Label Input: A set of unlabeled instances S = {x i } m i=1 , a parameter δ. Output: A sorted and labeled set S.
Apply RandomizedQuickSort to S: for each pair (x, x ) being compared, query k 1 workers and take the majority. Obtain a sorted listŜ = (x 1 ,x 2 , . . . ,x m ).
Ask k 2 workers to give their labels ofx t , and denote the majority byŷ t .
14 For all t < t,ŷ t ← −1. 15 return The sorted and labeled set of instances can provide different responses upon request. The conditions α, β ∈ (0, 1 2 ] in Assumption 2 ensure the correctness of the majority, while some prior works showed that by collecting extra information from the crowd [Prelec et al., 2017] or by hiring a number of experts [Awasthi et al., 2017b], it is possible to handle the case α, β ∈ (− 1 2 , 0]. We leave such extensions as our future work. We will always implicitly assume the two conditions throughout our analysis.

A natural approach and the limitation
In order to utilize the comparison oracle, we consider a natural approach of "compare and label", which was recently considered in Xu et al. [2017], Hopkins et al. [2020]. The primary idea is that we can make calls to the comparison oracle O C first, and use any sorting algorithm, say Quicksort, to rank all the instances. If the comparison oracle is perfect, then it remains to find a threshold left to which the instances will be classified as negative, and otherwise be positive. Here, we choose the Randomized QuickSort since it often admits superior comparison complexity. A more detailed discussion can be found in appendix F.
We present our approach for crowdsouring in Algorithm 1. To alleviate the noise, for each instance x t , we have to query O C multiple times in order to ensure that the majority voteẑ t is correct with high probability (recall in Assumption 2 we only assumed a weak probability of correct comparison). Then we apply binary search to find the threshold t, based on which the labels of all the instances can be correctly identified with high probability.
It is well known that the randomized process in Randomized QuickSort guarantees an average of O(m log m) comparisons, which provides us the query complexity as follows.
Proposition 1. (average version) Algorithm 1 correctly labels all the instances in S with probability at least 1 − δ. On average, it makes a total of O 1 α 2 · log m · log log m δ calls to O L , and a total of Observe that Randomized QuickSort further guarantees O(m log m) queries with probability at least 1 − 1 m , we present a high-probability version of Proposition 1 in the following. We prove the propositions by first showing that with high probability, the instances of S are sorted correctly. Then we show that based on such sorted list of instances, we can find the correct threshold with high probability. See Appendix A for the proof.
This approach outperforms the standard algorithms with superior query complexity and noise tolerance. More importantly, our result is distribution-independent while the existing ones often impose strong assumptions on the underlying distribution. Recall that for PAC learning we will need |S| = m . Hence, in view of Proposition 2, the labeling and comparison overhead of this algorithm are respectively given by Note that the dependence on Massart parameters, i.e. 1 α 2 or 1 β 2 , is unavoidable even when the underlying marginal distribution is uniform over a unit sphere [Yan and Zhang, 2017], so we focus on the dependence on m . Here, Λ L is loosely upper bounded by a constant provided that m is large enough, which is favorable especially when labels are precious. However, we note that Λ C grows with the size of the training set. In other words, if we expand the training size, the average cost on each labeled instance will also increase. In the next section, we show that with a more involved algorithmic design, the comparison overhead can be reduced to a constant level as well.

Main Algorithm and Performance Guarantee
In this section, we present a more involved algorithm which interleaves learning and annotation collection. The main idea is based on the boosting framework which was used for PAC learning from label-only queries under the crowdsoucing setting [Awasthi et al., 2017b]. Suppose that our target error rate is . In place of gathering all correct labels for learning (which requires m labels), we can first learn a weak classifier h 1 with slightly worse error rate of √ . This step only consumes a small amount of labels and pairwise comparisons. Based on h 1 , it is possible to identify the "hard instances", where h 1 will very likely make mistakes. We will then learn another classifier h 2 that fits on a subset of them: we use subset in that there is a budget on labeling and comparison complexity. Finally, it is easy to find instances where h 1 and h 2 disagree on, which can be used to learn the last classifier h 3 . Formally, we will need the following result.
Theorem 3 ( Schapire [1990]). For any p < 1 2 and distribution D, consider three classifiers: h 1 (x), h 2 (x), h 3 (x), that are p-close to the target classifier over three different distribution: 1) the Let S I ← Filter(S 2 , h 1 ), for a set of samples S 2 of size Θ(m ,δ ) drawn from D X .

21
Let S C be a sample set of size Θ(m √ ,δ ) drawn from D X .

23
Let W I ← {(x, y) ∈ S All | y = h 1 (x)}, and let W C ← S All \W I .

24
Draw a sample set W of size Θ(m √ ,δ ) from a distribution that equally weights W I and W C .

25
Let h 2 ← O H (W ). 26 Phase 3: construct the distributions D 1 , D 2 and D 3 . The main algorithm is described in Algorithm 2, where in each phase we carefully control the label and comparison complexity to simulate these distributions. We state the main result of this paper below.
Theorem 4 (Main result). With probability 1 − O 1 m √ , Algorithm 2 returns a classifier h ∈ H with error rate err D (h) ≤ by making O 1 α 2 · log 2 m · log log m total calls to O L and O m β 2 total calls to O C , given that log 2 ( d √ ) ≤ 1 √ . Furthermore, Algorithm 2 runs in polynomial time.
In the following, we elaborate on each phase, and provide our performance guarantee. The proof of Theorem 4 is sketched at the end of this section.

Analysis of Phase 1
The goal of Phase 1 is to learn a weak classifier with error rate √ on D. This can easily be fulfilled if we sample a set of m √ unlabeled instances, and invoke Algorithm 1 to obtain the desired hypothesis h 1 . Note that this is different from the natural approach as we presented in 3.1: the natural approach gathers all necessary instances (i.e. m unlabeled data) and feed them to Algorithm 1, which leads to an overwhelming comparison overhead.
Since the set S 1 is guaranteed to be labeled correctly with high probability (Proposition 2), we can learn h 1 with any standard polynomial-time algorithm O H (see Assumption 1 for the definition). The following lemma summarizes the performance of the learned hypothesis h 1 . Draw a random worker t from P to compare x with x − and x + , obtain Z t (x, x − ) and Z t (x, x + ).

41
If t is even, then continue to the next iteration.

Analysis of Phase 2
Phase 2 aims to simulate the distribution D 2 using the noisy feedback from the crowd, while maintaining a reasonable overhead. In particular, we need to find O(m √ ) instances that h 1 will misclassify, and O(m √ ) instances that h 1 will label correctly. Since the error rate of h 1 is O( √ ) (which is very small), identifying a batch of instances S I that h 1 will make mistakes on is the primary challenge.
We tackle this challenge by designing a novel algorithm termed Filter. Note that err D (h 1 ) ≤ √ indicates that if we hope to obtain S I with size m √ , we have to collect m √ / √ = m instances in view of Chernoff bound. That gives the size of the set S 2 .
In Algorithm 3, we present the Filter algorithm. Note that since the size of S (i.e. S 2 ) is O(m ), we cannot invoke Algorithm 1 directly: this leads to an overwhelming overhead as the natural approach. In contrast, we randomly sample a subset S p of S with O(log |S|) members, for which we can apply Algorithm 1 to obtain a sorted list of labeled instances S p . Based on S p , we identify two crucial instances x − and x + termed support instances. Roughly speaking, x − is the negative instance that is "closest" to positive, and x + is the positive instance that is "closest" to negative (similar to the support vectors in SVM). See Figure 1 for an illustration. Now for each x ∈ S\S p , we can make use of the comparison to identify whether it lies between x − and x + , Figure 1: Illustration of Algorithm 3. Each circle represents an instance in S, where we use solid circles to highlight the instances in S p ⊂ S. We call the oracles to sort and label all the instances in S p correctly. We use x − to denote the rightmost instance in S p that is labeled as −1, and use x + to denote the leftmost instance in S p that is labeled as +1. We will think of [x − , x + ] as an interval, and instances outside the interval (e.g. x 1 , x 5 ) are potentially informative and will be used to test the performance of h; those inside the interval (e.g. x 3 ) will be discarded.
or outside the interval. For those outside the interval, we think of them as good cases to test h (i.e. h 1 ). This is because Proposition 2 guarantees that S p will be annotated correctly with high probability and hence, instances left to x − are likely to be negative (likewise for x + ). On the other hand, recall that the crowd feedback of pairwise comparison is noisy. In this regard, each instance x will be tested multiple times (with a maximum of N times). For each x, if there exists a majority vote that agrees with h, we will believe that h is correct. This follows from the observation that h has a small error rate of √ (so it is correct on most instances) and with probability at least 1 2 + β a comparison tag is given correctly (so majority vote will not be too bad). Otherwise, after N/2 times of the filtering step there is no majority vote that is consistent with h, it is very likely that h makes mistake on the current instance x, and we add it to S I . The proof of the lemma relies on a set of new results that characterize the iteration number of the while-loop of Algorithm 3, the ratio of instances that fall within the interval [x − , x + ]. In addition, we show that for any instance x where h(x) = h * (x), with probability greater than 1/2 it will be identified and put into S I , and if h(x) = h * (x) it will be put into S I with vanishing probability.
Finding the instances that h 1 will label correctly is not hard. To see this, suppose we draw 2m √ instances to form S C . Since err D (h 1 ) ≤ √ , using Chernoff bound we are guaranteed that at least 2(1 − 2 √ )m √ ≥ m √ instances will be annotated correctly by h 1 . On the other hand, we can obtain high-quality labels for S C by invoking Algorithm 1.
These observations together lead to the following performance guarantee of Phase 2 in Algorithm 2. Readers may refer to Appendix C for a detailed proof.
In addition, when log 2 ( d √ ) ≤ 1 √ , the label complexity is O 1 α 2 · log 2 m · log log m and the comparison complexity is O m β 2 .

Analysis of Phase 3
Given the hypotheses h 1 and h 2 , we sample a set of m √ unlabeled instances that fall into the region R := {x : h 1 (x) = h 2 (x)}. Such instances can easily be gathered by rejection sampling: we randomly draw an instance x ∼ D and put it in S 3 if x ∈ R; otherwise we reject this instance and continue drawing another instance from D. Note that in this phase, we do not need to call O L nor O C . Then we apply Algorithm 1 to the unlabeled set S 3 . Since the size of S 3 is m √ , we are guaranteed an error rate of √ on D 3 in view of Proposition 2.

Proof Sketch of Theorem 4
Combining Lemma 5, Lemma 7 and Lemma 8, and using the union bound in probability, with probability at least 1 − O 1 m √ , the following holds: which contributes to a classifier h with err D (h) ≤ by taking majority vote of h 1 , h 2 , h 3 (Theorem 3). In addition, the total label complexity is O log 2 m ·log log m α 2 , and the total comparison complexity is O( m β 2 ), as long as log 2 ( d √ ) ≤ 1 √ . Hence, the labeling and comparison overhead of Algorithm 2 are respectively given by This completes the proof of Theorem 4.

Conclusion and Future Works
In this paper, we have presented a computationally and query efficient algorithm that learns an unknown hypothesis from the labels and pairwise comparison tags corrupted with Massart noise in distribution-independent setting. We provably showed that our algorithm enjoys near-optimal query complexity with only o α (1) labeling overhead and O β (1) comparison overhead. To this end, we have developed a set of new algorithmic results with theoretical guarantee. We believe that it would be interesting to explore other types of crowd feedback, such as multiclass labels. It is also interesting to study agnostic PAC learning [Kalai et al., 2005] under the crowdsourcing setting.
A Proof of Propositions in 3.1 Proposition 9 (Restatement of Proposition 1). Algorithm 1 correctly labels all the instances in S with probability at least 1 − δ. On average, it makes a total of O 1 α 2 · log m · log log m δ calls to O L , and a total of O 1 β 2 · m log m · log m δ calls to O C , where m = |S|.
Proof. By assumption 2, given an instance pair (x, x ) ∈ X × X , if we randomly sample a worker j ∼ P, with probability at least 1 2 + β, the worker j gives the correct comparison result. Let k 1 be the number of workers we query for each pair in Algorithm 1, then the probability that majority vote makes mistake on pair (x, x ) is given by Pr Z * (x, x ) · k 1 j=1 z j (x, x ) ≤ 0 . Without loss of generality, we assume the ground truth to be −1.
By Hoeffding's inequality, where a = −1, b = +1 are the corresponding lower and upper bounds of z j (x, x ). Let k 1 · E j z j (x, x ) + t = 0, the RHS of the inequality becomes e −2k 1 β 2 . Let q m be the total number of comparisons made by algorithm RandomizedQuickSort. We apply the union bound to conclude that Let the RHS be the confidence parameter δ. Then we have Given that the average number of comparisons made by RandomizedQuickSort is O(m log m), while the worst case is O(m 2 ). In either case, on each pair suffices to guarantee that with probability at least 1 − δ, all the instances in the sample set will be sorted correctly. While on average, the total number of calls made to the comparison oracle is As for the label complexity. By Assumption 2, for any given instance x ∈ X , if we randomly draw a worker i ∼ P, the probability that worker i gives a correct label is at least 1 2 + α. Similar to the previous analysis, let y l = h * (x l ) be the true label for instance x l , by Hoeffding's inequality, we conclude that provided that we use log m δ workers to label each instance. Due to binary search, the total number of calls we made to the labeling oracle is Combining the guarantees for comparison and labeling, the given instance set S is sorted correctly, and the correct threshold is identified with high probability. On average, this algorithm makes it makes a total of O 1 α 2 ·log m·log log m

B Analysis of Phase 1
Lemma 11 (Restatement of Lemma 5). In Phase 1, with probability In addition, the label complexity is O Proof. In Phase 1, by Proposition 10, all the instances in S 1 are correctly labeled with probability 1− δ 6 . In addition, given the sample size |S 1 | = m √ Lemma 12. In each iteration of the while-loop of Algorithm 3, after identifying the support instances x − , x + , with probability at least 1 − 1 m 50 , the interval [x − , x + ] contains less than a 1/2 fraction of unfiltered instances, where m is the initial size of the input set S.
Proof. In each while-loop, the algorithm randomly samples a subset S p ⊆ S with b instances.
Naturally, the support instances x − and x + could be any x i and x i+1 in S p respectively. We consider that extreme cases like all the sub-samples are subject to identical labels are also possible. Thus, we hope the interval formed by any x i and x i+1 , ∀i ∈ {0, 1, 2, . . . , b}, contains less than a 1/2 fraction of unfiltered instances.
Denote by E i the event that interval [x i , x i+1 ] contains more than a 1/2 fraction of the unfiltered instances. As illustrated by Figure 2, let a be the distance from x i to the leftmost instance x 0 . Then, event E i is given by that max(i − 1, 0) of the sub-samples are on the left-hand-side of x i and Figure 2: Sub-sampling. Solid circles represent instances in S p , while the rest represent instances in S\S p . We will imagine that all instances are sorted and placed on an axis with equal distance. The support instances x − and x + are defined as in Figure 1. Here, we use x i to indicate the i-th sample in S p , where i ∈ {1, 2, . . . , b}. In addition, we use x 0 to denote the leftmost instance in S and use x b+1 to denote the rightmost instance in S. We consider x 0 and x b+1 are not observed yet.
the other b − i are on the right-hand-side of x i with distance at least 1 2 . In the following, we only take the integral for a from 0 to 1 2 , because if a > 1 2 the fraction contains by [x i , x i+1 ] must be less than 1 2 . Therefore, for any i ∈ {0, 1, where the second inequality is because a ∈ [0, 1 2 ]. Similarly, ∀i ∈ { b 2 + 1, . . . , b}, . By union bound, In Algorithm 3, the parameter b = 100 log(m), which means the probability that the interval [x − , x + ] contains less than a 1/2 fraction of the unfiltered instances is no less than 1 − 1 m 50 .
Lemma 13. With probability at least 1 − 1 m 2 , the iteration number of the while-loop in Algorithm 3 is O log m , where m is the initial size of the input set S.
Proof. The iteration number of the while-loop in Algorithm 3 is determined by the amount of instances being removed from S in each iteration. We will first show that a significant fraction of the unfiltered instances are potentially informative after the sub-sampling. Then, for each informative instances, we show that it will go to S or S I with probability > 1/2. At last, using the Chernoff bound, we show that in each iteration, at least a 1/8 fraction of instances will be removed from S with high probability, which contributes to logarithmic iteration number as desired.
Lemma 12 guarantees that, in one while-loop, with probability at least 1 − 1 m 50 , the interval [x − , x + ] contains no more than a 1/2 fraction of the instances, which means more than 1/2 fraction are outside the interval and potentially informative, i.e. Z * (x, x − ) = −1 or Z * (x, x + ) = +1.
Suppose Assumption 2 is satisfied, and further consider that 1 2 + β > 0.85 here for ease of presentation, as it's always easy to boost any 1 2 + β > 1 2 . Then, for any instance x, the probability that worker t ∼ P gives both correct comparison tags with respect to x − and x + is For an x lying outside the interval [x − , x + ], we are interested in the probability that even though N workers are queried, the following never occurs: Maj z 1:t (x, x − ) = 1 and Maj z 1:t (x, x + ) = −1, ∀t = {1, 2, . . . , N }, as it will keep x in S as an unfiltered instance. Denote by E t the event that two equations hold when worker t provides its tags. If any worker t makes mistake, it would potentially trigger an event E t in the future, where t ≥ t. Therefore, we consider the following: if any one of the vote makes mistake, we require the next 2 workers to give both correct comparison tags such that the majorities keep correct. The problem boils down to a biased random walk. Recall that in each round, worker t give both correct tags with probability > 0.7. Consider a walk starting from the origin. With probability > 0.7, it move to the right, and with the remaining probability, it move to the left. The probability that this random walk ever crosses the origin is given by the ruin of gambling probability (Theorem 23). Therefore, In other words, with probability larger than 4 7 > 1 2 , an x lying outside the interval [x − , x + ] will added either in set S or set S I . In either case, it will be removed from S.
Applying the Hoeffding's inequality, in an iteration, with probability 1−exp(− |S| /32), we have at least 1/8 of the instances in S\S p being removed from S. Although the size of S decreases, it is guaranteed that |S| ≥ 100 log m.

C.2 Query Complexity in Sub-sampling
Lemma 14. With probability 1 − 1 m , Algorithm 3 correctly label the subsets S p 's in all iterations by making O 1 α 2 · log 2 m · log log m total calls to the O L and O 1 β 2 · log 3 m · log log m total calls to the O C , where m is the initial size of the input set S.
Proof. By Lemma 13, the iteration number of the while-loop in Algorithm 3 is log m. In each iteration, suppose we invoke Algorithm 1 to correctly label S p that contains b = 100 log m instances with probability 1 − δ . In order to guarantee that S p 's are labeled correctly in all iterations, we let δ · log m = 1 m . Then, in each iteration, the number of calls required to O L is Similarly, the number of calls required to O C is In conclusion, the total number of calls to O L in all iterations is given by respectively, the total number of calls to O C is given by Proof. Eventually, an instance x that goes to either S I or S will be removed from S. As we showed in Lemma 13, the probability that labeler t ∼ P gives both correct comparison tags with respect to x − , x + with probability > 0.7. Thus, if h * (x) = h(x), consider t = N , the majority of N = O(log(1/ √ )) labels are correct with probability at least 1 − √ , such an instance goes to S I with probability at most √ . If h * (x) = h(x), again we consider a biased random walk that with probability > 0.7, the vote is correct and with remaining probability, it is wrong. We give the probability that the majority ever makes mistake, or the majority ever agrees with h 1 , as Eq.C.2, which is < 3 7 . Therefore, for each x where h * (x) = h(x), it goes to S I w.p. at least 4 7 > 1 2 .
Lemma 16  Proof. For ease of exposition, we assume that the error rate of h 1 is exactly √ as per Lemma 11, according to Lemma 15, we have Then, following the sampling process in Algorithm 2, we have The claim follows by the Chernoff bound.

C.4 Query Complexity in Filtering
Lemma 17 (Restatement of Lemma 6). With probability at least 1 − O 1 m , the following holds. Algorithm 3 returns an instance set S I with size m √ by making O m β 2 calls to the O C .
When the interval [x − , x + ] contains less than a 1/2 fraction of the instances, the remaining 1/2 fraction are informative for testing hypothesis h 1 . For each of these instances, the expected number of iterations that it participated in is L < 2, because in each iteration it gets removed with probability larger than 1/2. By Chernoff bound, w.p. at least 1 − exp(−Ω(|S| √ )), the number of instances that h 1 will misclassify is Θ(|S| √ ), and w.p. at least 1 − exp(−Ω(|S|)), the number of instances that h 1 correctly labels is Θ(|S| (1 − √ )) = Θ(|S|). If h 1 (x) = h * (x), let N i be the expected number of queries until we have i more correct tag pairs than the incorrect ones. Then, N 1 ≤ 0.7(1) + 0.3(N 2 + 1) and N 2 = 2N 1 , which gives N 1 ≤ 2.5. In other words, the inner For-loop breaks at the Filtering step by querying less than 2.5 workers. If the inner For-loop breaks at the Filtering step, x goes to S and gets removed from S. On the other hand, if x is mistakenly discard (reserved for the next iteration) and the inner loop breaks at one step before Filtering, the expected number of queries must be no more than N 1 as well, because as an interruption to the filtering process, it always costs less queries in view of the law of total probability. Thus, for each x where h(x) = h * (x), the expected number of queries we need is less than LN 1 , which is upper bounded by a constant. Apply the Bernstein's inequality, for all Θ(|S| (1 − √ )) such instances, w.p. 1 − exp(−Ω(|S|)), the number of queries is O(|S|). If h 1 (x) = h * (x), the number of queries needed for each x is no more than LN = O(log(1/ )) in Algorithm 3. Therefore, w.p. 1 − exp(−Ω(|S| √ )), the total number of queries spent on these instances is at most O(|S| √ log(1/ )) ≤ O(|S|). On the other hand, for these instances that lie in the interval [x − , x + ], we will think of an x in different While-loop iterations as different test cases. Because of Lemma 12 and 13, we have the total size of such uninformative test cases no more than 1 2 m + 7 8 m + 7 8 2 m + 7 8 3 m + · · · + 1 = O(m).
In addition, for each of these test cases, let N 1 be the expected number of queries until we have one more correct tag pairs than the incorrect ones. Then, similar to the informative cases where h 1 (x) = h * (x), N 1 ≤ 2.5. Again, we apply the Bernstein's inequality and the total number of queries for these instances is no more than O(|S|) w.p. at least 1 − exp(− |S|).
Note that even though we only presented the dependence on m for the clarity of proof, we didn't remove the 1 β 2 factor because of the majority vote process. Thus, the total number of calls to O C is O m . In addition, when log 2 ( d √ ) ≤ 1 √ , the label complexity is O 1 α 2 · log 2 m · log log m and the comparison complexity is O m β 2 .
Proof. As guaranteed by Lemma 16, the size of W is Θ(m √ ) almost surely. The error rate of classifier h 2 on the distribution D , which has equal probability on the distributions induced by W I and W C , is √ . It remains to show that h 2 achieves the matching error rate √ on the target distribution D 2 in phase 2. We apply the super-sampling technique proposed in Awasthi et al. [2017b]. Let d (x) denote the density of point x in distribution D , likewise d 2 (x) for points in D 2 . It is sufficient to show that for any x, d (x) = Θ(d 2 (x)).
For ease of presentation, we again assume err D (h 1 ) is exactly √ . Let d(x), d C (x), and d I (x) be the density of instance x in distributions D, D C , and D I , respectively. Note that, for any x such that h 1 (x) = h * (x), we have d(x) = d C (x)(1 − 1 Proof. We first consider the query complexity in 3 phases. According to Lemma 11, 18 and 19, the total number of calls to O L is O 1 α 2 · log 2 m · log log m , and the total number of calls to O C is O m β 2 , as long as log 2 ( d √ ) ≤ 1 √ . In addition, in each phase, with high probability, the algorithm returns a classifier with error rate no more than √ on its corresponding distribution D 1 , D 2 or D 3 . Applying union bound, with probability at least 1 − O 1 m √ , according Theorem 3, we conclude that the classifier h returned by Algorithm 2 has error < on D.

F Useful Lemmas
Lemma 21 (High-probability bound for Randomized QuickSort). With probability at least 1−1/m, the following holds. Given a set of instance S with m elements, the computation complexity of sorting all the elements by Randomized QuickSort is O(m log m).
Proof. QuickSort is a recursive algorithm: in each round, it picks a pivot, splits the problem into two subsets, and continue playing QuickSort on each subset. The program keeps doing this until the inputs for all recursive calls contain only one element.
We consider Randomized QuickSort in our algorithm. Note that Randomized QuickSort differs from QuickSort only in the way it picks the pivots: in each round, it picks a random element in set S.
Consider a special element t ∈ S. Let L i be the size of input in the ith level of recursion that contains t. Obviously L 0 = m, and Theorem 23 (Probability of Ruin). Consider a player who starts with i dollars against an adversary that has N dollars. The player bets one dollar in each gamble, which he wins with probability p. The probability that the player ends up with no money at any point in the game is Theorem 24 (Bernstein Inequality). Let X 1 , . . . , X n be independent random variables with expectation µ. Supposed that for some positive real number L and every k > 1, Then,