# 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. Jun 14, 2011 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... Jun 14, 2011 at 23:09
• OK -- looks like I've got myself another exercise for the ML course... :) Thanks for the input, Aaron and Lev! Jun 15, 2011 at 5:42
• @Aaron, maybe this should have been an answer. Jun 17, 2011 at 17:54