Agnostic PAC sampling lower bound

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?

-
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

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