Online to batch sample complexity

Question

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. Can anyone describe the proof, or better yet, help me find a copy of this paper? Is this the best possible?

Answer 1

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.