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?


1 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.

  • $\begingroup$ Very nice, David! You wouldn't happen to have a copy of Littlestone's paper, would you?.. $\endgroup$
    – Aryeh
    Jan 28, 2013 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, 2013 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, 2013 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, 2013 at 20:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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