<p>See Hanneke's disagreement coefficient,
<a href="http://projecteuclid.org/euclid.aos/1291388378" rel="nofollow">http://projecteuclid.org/euclid.aos/1291388378</a></p>

CC BY-SA 3.0
2015-03-10T13:30:51.307Z
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).
usul
CC BY-SA 4.0
2020-11-18T13:58:02.780Z
Oh wow, it's been a while! Maybe Steve will run across this question and rise to the challenge... :)
Aryeh
CC BY-SA 3.0
2015-03-10T06:48:10.993Z
2015-03-10T06:48:10.993Z
Aryeh
<p>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).</p>

<p><a href="http://en.wikipedia.org/wiki/Active_learning_(machine_learning)" rel="nofollow">Active learning</a> 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 ). </p>

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

CC BY-SA 3.0
2015-03-10T06:46:54.937Z
The $O(d/\epsilon)$ isn't quite right, unless it's hiding log factors...
Aryeh
<machine-learning><lg.learning><vc-dimension>
Characterizing the exponential savings in active learning
seteropere
# Characterizing the exponential savings in active learning

(Asked by: username_0 on 2015-03-08)

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](http://en.wikipedia.org/wiki/Active_learning_(machine_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?

**Tags:** machine-learning, lg.learning, vc-dimension
> **Comments:**
> **username_1**: The $O(d/\epsilon)$ isn't quite right, unless it's hiding log factors...  

---

## 1 answers

### Answer by username_1 on 2015-03-10. Score: 1

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

> **Comments:**
> **username_2**: 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).  
> **username_1**: Oh wow, it's been a while! Maybe Steve will run across this question and rise to the challenge... :)  

---

