  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 any
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)^{(m-1)/2}$ queries. On the other hand,
using the more powerful 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. Similar results hold when the input points have
bounded bit complexity, or when only one class has strong convex hull margin
against the rest. We complement the upper bounds by showing that in the worst
case any algorithm needs $\Omega\big(k m \log \frac{1}{\gamma}\big)$ seed and
label queries to learn a $k$-class classifier with strong convex hull margin
$\gamma$.
