10
$\begingroup$

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?

Improve this question
$\endgroup$
4
  • 3
    $\begingroup$ 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. $\endgroup$ – Aaron Roth Jun 14 '11 at 20:31
  • 1
    $\begingroup$ 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... $\endgroup$ – Lev Reyzin♦ Jun 14 '11 at 23:09
  • $\begingroup$ OK -- looks like I've got myself another exercise for the ML course... :) Thanks for the input, Aaron and Lev! $\endgroup$ – Aryeh Jun 15 '11 at 5:42
  • $\begingroup$ @Aaron, maybe this should have been an answer. $\endgroup$ – Suresh Venkat Jun 17 '11 at 17:54
6
$\begingroup$

I now realize that a lower bound has indeed been established by Anthony and Bartlett (see the presentation here).

Edit 24-Sep-2018. This question has kept me occupied all of these years, and recently, I. Pinelis and I have obtained the exact optimal constant in the agnostic PAC lower bound to appear in Ann. Stat.

Improve this answer
$\endgroup$
3
  • $\begingroup$ In your paper you do not cite this work (jmlr.org/papers/volume17/15-389/15-389.pdf). Does optimal sample complexity upperbounds in the realizable case not of any connection to your work? Are these corresponding optimal sample complexity upperbounds known for the agnostic case? $\endgroup$ – gradstudent Feb 18 '19 at 17:36
  • $\begingroup$ I don't think the realizable case is all that related. In the realizable case, ERM does not guarantee optimal rates -- hence all the hard work Hanneke and others had to expend in order to remove the log factor, and it's still unknown whether a proper learner can achieve the optimal rate. Contrariwise, in the agnostic case, it has been known for a long time that ERM achieves the optimal rate. $\endgroup$ – Aryeh Feb 18 '19 at 19:21
  • $\begingroup$ It's now known that proper learning cannot always guarantee the optimal rate for realizable PAC. $\endgroup$ – Aryeh Jan 14 at 22:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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