Noise-Tolerant Interactive Learning Using Pairwise Comparisons
We study the problem of interactively learning a binary classifier using noisy labeling and pairwise comparison oracles, where the comparison oracle answers which one in the given two instances is more likely to be positive. Learning from such oracles has multiple applications where obtaining direct labels is harder but pairwise comparisons are easier, and the algorithm can leverage both types of oracles. In this paper, we attempt to characterize how the access to an easier comparison oracle helps in improving the label and total query complexity. We show that the comparison oracle reduces the learning problem to that of learning a threshold function. We then present an algorithm that interactively queries the label and comparison oracles and we characterize its query complexity under Tsybakov and adversarial noise conditions for the comparison and labeling oracles. Our lower bounds show that our label and total query complexity is almost optimal.
he authors study the active binary classification setting where
+ The learner can ask the label of an instance. The labelling oracle will provide a noisy answer (with either adversarial noise or Tsybakov)
+ In addition to the labeling oracle, there is a comparison oracle. The leaner then can ask which of two instances is more likely to be positive. This oracle's answers is also noisy.
The authors provide results which show that if the learner uses comparison queries, then it can reduce the label-query complexity. The problem that the authors study seem to be a valid and interesting one. The presentation of the result however should be improved. In the current state, accurately parsing the arguments is hard. Also, it would have been better if a better proof sketch was included in the main paper (to give the reviewer an intuition about the correctness of the results without having to read the supplements).
The core idea is to use the usual active-type algorithm, but then replace the label-request queries with a sub-method that uses mostly comparison queries (along with a few label queries). This is possible by first sorting the instances based on comparison queries and then doing binary search (using label queries) to find a good threshold. 
One thing that that concerning is the assumption on the noise level. On one hand, the authors argue that the major contribution of the paper compared to previous work is is handling noise. However, their positive result is not applicable when the amount of noise is more than some threshold (which depends on epsilon and even delta).
Also, the authors do not discuss if the learner is allowed to perform repeated comparison queries about the same pair of instances. This seems to be helpful. [Furthermore, the authors assume that the outcome of the queries are iid, even when they have been asked about overlapping pairs]