NeurIPS 2020

The Power of Comparisons for Actively Learning Linear Classifiers

Meta Review

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.