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?
3
$\begingroup$
$\endgroup$
5
$\begingroup$
$\endgroup$
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.
-
$\begingroup$ Very nice, David! You wouldn't happen to have a copy of Littlestone's paper, would you?.. $\endgroup$ – Aryeh Jan 28 '13 at 17:11
-
$\begingroup$ 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? $\endgroup$ – Aryeh Jan 29 '13 at 8:38
-
$\begingroup$ 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. $\endgroup$ – david Jan 29 '13 at 11:23
-
$\begingroup$ Right! So your proof is the "survivor analysis" I had in mind... Thanks for clarifying -- I feel dumb about writing the same bound. $\endgroup$ – Aryeh Jan 29 '13 at 20:18
