Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

It is well-known that for classical PAC learning, $\Omega(d/\varepsilon)$ examples are necessary in order to acheive an error bound of $\varepsilon$ w.h.p., where $d$ is the VC-dimension of the concept class.

Is it known that $\Omega(d/\varepsilon^2)$ examples are needed in the agnostic case?

share|cite|improve this question
I am not sure what the lower bound looks like, one should exist if the Hoefding bound is tight (and I think it is). This bound states that for 1 fn, if the probability of error is p, then you need at most $m = O(1/\epsilon^2)$ samples to estimate p to within error +- $\epsilon$ w.h.p. So consider any concept class with 2 concepts, $f_1$ and $f_2$ and VC-dimension 2. Take a distribution over examples so that $p_1 = p_2 + \epsilon$ (or vice versa) -- this is possible because VC-dimension is 2. It seems that an algorithm using only $O(1/\epsilon)$ examples would imply an improved Hoefding bound. – Aaron Roth Jun 14 '11 at 20:31
Namely, I think the Hoeffding bound is tight at $p=1/2$ for $O(1/\epsilon^2)$. I think the reasoning above is generally known... – Lev Reyzin Jun 14 '11 at 23:09
OK -- looks like I've got myself another exercise for the ML course... :) Thanks for the input, Aaron and Lev! – Aryeh Jun 15 '11 at 5:42
@Aaron, maybe this should have been an answer. – Suresh Venkat Jun 17 '11 at 17:54
up vote 5 down vote accepted

I now realize that a lower bound has indeed been established by Anthony and Bartlett (see the presentation here). I've also come up with an alternate proof, based on some recent work of mine in L1 deviation of the empirical distribution.

share|cite|improve this answer
Ran El-Yaniv points out that my technique establishes a lower bound on the convergence rate for binary Glivenko-Cantelli classes, but not for agnostic PAC. Even if we restrict ourselves to the ERM learner (which we can, without loss of generality) -- to argue that this learner will need about $d/\epsilon^2$ examples requires constructing an adversarial distribution pretty much along the lines of Anthony and Bartlett. – Aryeh Jan 11 '13 at 7:47

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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