Active Learning of Classifiers with Label and Seed Queries

We study exact active learning of binary and multiclass classifiers with margin. Given an n -point set X \subset \mathbb{R} m, we want to learn an unknown classifier on X whose classes have finite strong convex hull margin, a new notion extending the SVM margin. In the standard active learning setting, where only label queries are allowed, learning a classifier with strong convex hull margin \gamma requires in the worst case \Omega\big(1 \frac{1}{\gamma}\big) {\frac{m-1}{2}} queries. On the other hand, using the more powerful \emph{seed} queries (a variant of equivalence queries), the target classifier could be learned in O(m \log n) queries via Littlestone's Halving algorithm; however, Halving is computationally inefficient. In this work we show that, by carefully combining the two types of queries, a binary classifier can be learned in time \operatorname{poly}(n m) using only O(m 2 \log n) label queries and O\big(m \log \frac{m}{\gamma}\big) seed queries; the result extends to k -class classifiers at the price of a k!k 2 multiplicative overhead.