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, 2011 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, 2011 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, 2011 at 5:42
  • $\begingroup$ @Aaron, maybe this should have been an answer. $\endgroup$
    – Suresh Venkat
    Jun 17, 2011 at 17:54

1 Answer 1

Reset to default
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, 2019 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, 2019 at 19:21
  • $\begingroup$ It's now known that proper learning cannot always guarantee the optimal rate for realizable PAC. $\endgroup$
    – Aryeh
    Jan 14, 2021 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.