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?

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

See Hanneke's disagreement coefficient, http://projecteuclid.org/euclid.aos/1291388378

  • 3
    $\begingroup$ It would be great if you (or someone else) can expand the answer a bit with a summmary of what the disagreement coefficient is and in what sense it captures learning rates in active learning (especially when compared to passive learning). $\endgroup$ – usul Mar 10 '15 at 13:30
  • $\begingroup$ Oh wow, it's been a while! Maybe Steve will run across this question and rise to the challenge... :) $\endgroup$ – Aryeh Nov 18 '20 at 13:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.