<p>Here is the sketch of a proof I know. 
Let us draw $s = \max\left(\frac{4M}{\varepsilon},\frac{c}{\varepsilon} \log\frac{1}{\delta}\right)$ samples from the unkown distribution (where $c$ isconstant), and feed them as input for the mistake-bounded algorithm. We can assume the learning algorithm is conservative, i.e., only changes its working hypothesis after an incorrect prediction has been made.</p>

<p>Look at the sequence of $k \le M$ hypothesis produced by the learner; we claim that, with probability $1-\frac\delta2$, at least one of them has error $&lt; \frac\varepsilon2$. Assume the contrary and observe that any hypothesis with error $\ge \frac\varepsilon 2$ will be found to be wrong within the next $\frac{2}\varepsilon \le \frac{s}{2M}$ random examples on average. Therefore the expected number of samples before the last hypothesis is produced is bounded by $s / 2$. By using a Chernoff-like bound for the sum of geometric random variables, we can bound the probability that a hypothesis with error $&lt; \frac \varepsilon 2$ is not found within $s$ samples by $\delta / 2$ (for a suitable value of $c$).</p>

<p>The rest is easy: we know that one of the hypothesis is good, so we just draw $O\left(\frac{1}{\varepsilon} \log{\frac{M}{\delta}}\right)$ additional samples, test each of them against this new sample set, and select the best one. By Chernoff bounds, it holds that with probability $1-\frac\delta 2$, the good one has empirical error $&lt; \frac{3}{4} \varepsilon$ on this set, while any wrong hypothesis with error $&gt; \varepsilon$ will have empirical error $&gt; \frac{3}{4} \varepsilon$. All in all, a hypothesis with error less than $\varepsilon$ will be selected with probability $1-\delta$.</p>

<p>My guess is that the bound is optimal, but I haven't found a reference for this.</p>

CC BY-SA 3.0
2013-01-28T17:11:00.433Z
Very nice, David! You wouldn't happen to have a copy of Littlestone's paper, would you?..
Aryeh
CC BY-SA 3.0
2013-01-29T08:38:32.813Z
I just realized that in the second stage, you need $$O( (1/\epsilon) \log (M/\delta) )$$ examples -- which matches the sample complexity in my first display and isn't quite as tight as what Littlestone has shown in that COLT paper... Am I missing something?
Aryeh
CC BY-SA 3.0
2013-01-29T11:23:26.303Z
Actually the two bounds you wrote are the same, since $\frac{1}{\epsilon}\log \frac{M}{\delta} = \frac 1 \epsilon \log M + \frac{1}{\epsilon} \log\frac 1 \delta$, and the first term is superseded by the $O(\frac M \epsilon)$ complexity of the first step.

I reckon you meant $$O(\frac{1}{\epsilon} M \log\frac M \epsilon}$$ in the first one.

By the way, I don't have an online copy of Littlestone's paper.
david
CC BY-SA 3.0
2013-01-29T20:18:55.897Z
Right! So your proof is the "survivor analysis" I had in mind... Thanks for clarifying -- I feel dumb about writing the same bound.
Aryeh
CC BY-SA 3.0
2013-01-28T13:34:40.757Z
2013-01-29T11:35:08.937Z
2013-01-29T11:35:08.937Z
david
<p>It is well known that a mistake bound can be converted to a PAC bound. I know how to prove a sample complexity of
$$ O( (1/\epsilon)[M + \log(M/\delta)] ), $$
where $M$ is an upper bound on the number of mistakes.
I am told that Nick Littlestone sharpened this to
$$ O((1/\epsilon)[M + \log(1/\delta)])$$
in his 1989 COLT <a href="http://dl.acm.org/citation.cfm?id=93365" rel="nofollow">paper</a>. Can anyone describe the proof, or better yet, help me find a copy of this paper? Is this the best possible?</p>

<machine-learning><lg.learning><online-learning>
Online to batch sample complexity
Aryeh
# Online to batch sample complexity

(Asked by: username_0 on 2013-01-26)

It is well known that a mistake bound can be converted to a PAC bound. I know how to prove a sample complexity of
$$ O( (1/\epsilon)[M + \log(M/\delta)] ), $$
where $M$ is an upper bound on the number of mistakes.
I am told that Nick Littlestone sharpened this to
$$ O((1/\epsilon)[M + \log(1/\delta)])$$
in his 1989 COLT [paper](http://dl.acm.org/citation.cfm?id=93365). Can anyone describe the proof, or better yet, help me find a copy of this paper? Is this the best possible?

**Tags:** machine-learning, lg.learning, online-learning


---

## 1 answers

### Answer by username_1 on 2013-01-28. Score: 5 | Accepted answer

Here is the sketch of a proof I know.
Let us draw $s = \max\left(\frac{4M}{\varepsilon},\frac{c}{\varepsilon} \log\frac{1}{\delta}\right)$ samples from the unkown distribution (where $c$ isconstant), and feed them as input for the mistake-bounded algorithm. We can assume the learning algorithm is conservative, i.e., only changes its working hypothesis after an incorrect prediction has been made.

Look at the sequence of $k \le M$ hypothesis produced by the learner; we claim that, with probability $1-\frac\delta2$, at least one of them has error $< \frac\varepsilon2$. Assume the contrary and observe that any hypothesis with error $\ge \frac\varepsilon 2$ will be found to be wrong within the next $\frac{2}\varepsilon \le \frac{s}{2M}$ random examples on average. Therefore the expected number of samples before the last hypothesis is produced is bounded by $s / 2$. By using a Chernoff-like bound for the sum of geometric random variables, we can bound the probability that a hypothesis with error $< \frac \varepsilon 2$ is not found within $s$ samples by $\delta / 2$ (for a suitable value of $c$).

The rest is easy: we know that one of the hypothesis is good, so we just draw $O\left(\frac{1}{\varepsilon} \log{\frac{M}{\delta}}\right)$ additional samples, test each of them against this new sample set, and select the best one. By Chernoff bounds, it holds that with probability $1-\frac\delta 2$, the good one has empirical error $< \frac{3}{4} \varepsilon$ on this set, while any wrong hypothesis with error $> \varepsilon$ will have empirical error $> \frac{3}{4} \varepsilon$. All in all, a hypothesis with error less than $\varepsilon$ will be selected with probability $1-\delta$.

My guess is that the bound is optimal, but I haven't found a reference for this.

> **Comments:**
> **username_0**: Very nice, David! You wouldn't happen to have a copy of Littlestone's paper, would you?..  
> **username_0**: I just realized that in the second stage, you need $$O( (1/\epsilon) \log (M/\delta) )$$ examples -- which matches the sample complexity in my first display and isn't quite as tight as what Littlestone has shown in that COLT paper... Am I missing something?  
> **username_1**: Actually the two bounds you wrote are the same, since $\frac{1}{\epsilon}\log \frac{M}{\delta} = \frac 1 \epsilon \log M + \frac{1}{\epsilon} \log\frac 1 \delta$, and the first term is superseded by the $O(\frac M \epsilon)$ complexity of the first step.  I reckon you meant $$O(\frac{1}{\epsilon} M \log\frac M \epsilon}$$ in the first one.  By the way, I don't have an online copy of Littlestone's paper.  
> **username_0**: Right! So your proof is the "survivor analysis" I had in mind... Thanks for clarifying -- I feel dumb about writing the same bound.  

---

