In the world of big data, large but costly to label datasets dominate many fields. Active learning, a semi-supervised alternative to the standard PAC-learning model, was introduced to explore whether adaptive labeling could learn concepts with exponentially fewer labeled samples. While previous results show that active learning performs no better than its supervised alternative for important concept classes such as linear separators, we show that by adding weak distributional assumptions and allowing comparison queries, active learning requires exponentially fewer samples. Further, we show that these results hold as well for a stronger model of learning called Reliable and Probably Useful (RPU) learning. In this model, our learner is not allowed to make mistakes, but may instead answer ``I don't know.'' While previous negative results showed this model to have intractably large sample complexity for label queries, we show that comparison queries make RPU-learning at worst logarithmically more expensive in both the passive and active regimes.

Clarity: While I can understand the statements in this paper, I think the presentation can be much improved. For example: - As RPU learning implies PAC learning, is there really a need to present Algorithm 1 and Theorem 3.5? Aren't we already happy with Theorem 4.11? - in Algorithm 1, Threshold(S) is only informally defined, and an elaboration is needed. I think basically, the algorithm can successfully approximately recover b if it can find two neighboring and - examples? Also, what is the active learning algorithm used here?

The reviewer are unanimous in their support of accepting this paper. The paper makes an important contribution to the literature on learning with label queries and comparison queries, showing that comparison queries dramatically improve the query complexity of learning (nonhomogeneous) halfspaces under distribution assumptions, and furthermore the results even hold in the more-challenging "RPU" model (where the predictor must never be wrong, but may abstain with epsilon probability). The approach stems from general principles, and may lead to further follow-up works.

In the world of big data, large but costly to label datasets dominate many fields. Active learning, a semi-supervised alternative to the standard PAC-learning model, was introduced to explore whether adaptive labeling could learn concepts with exponentially fewer labeled samples. While previous results show that active learning performs no better than its supervised alternative for important concept classes such as linear separators, we show that by adding weak distributional assumptions and allowing comparison queries, active learning requires exponentially fewer samples. Further, we show that these results hold as well for a stronger model of learning called Reliable and Probably Useful (RPU) learning. In this model, our learner is not allowed to make mistakes, but may instead answer I don't know.''