# Characterizing the exponential savings in active learning

Let $H$ be a hypothesis class with VC dimension $d$. In supervised learning, we need almost $O(\frac{d}{\epsilon})$ random labelled examples to return a hypothesis within $\epsilon$ from the target (separable case).

Active learning potential lies in its exponential saving in terms of the number of queries required compared to the supervised learning. This big saving in known for some structures ( for example learning threshold functions requires $O(\frac{1}{\epsilon})$ examples while we can achieve the same goal with $log \frac{1}{\epsilon}$ in active learning ).

What characterizes this exponential reduction in general? Are there certain properties such that if $H$ satisfies them then active learning would help?

• The $O(d/\epsilon)$ isn't quite right, unless it's hiding log factors... – Aryeh Mar 10 '15 at 6:46