<p>I now realize that a lower bound has indeed been established by Anthony and Bartlett (see the presentation <a href="https://rads.stackoverflow.com/amzn/click/026201825X" rel="nofollow noreferrer">here</a>). </p>

<p>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 <a href="https://arxiv.org/abs/1606.08920" rel="nofollow noreferrer">to appear in Ann. Stat</a>.</p>

CC BY-SA 4.0
2019-02-18T17:36:44.880Z
In your paper you do not cite this work (http://www.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?
gradstudent
CC BY-SA 4.0
2019-02-18T19:21:39.220Z
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.
Aryeh
CC BY-SA 4.0
2021-01-14T22:30:20.767Z
It's now known that proper learning cannot always guarantee the optimal rate for realizable PAC.
Aryeh
CC BY-SA 4.0
2013-01-08T20:19:10.693Z
2018-10-24T19:35:44.773Z
2018-10-24T19:35:44.773Z
Aryeh
<p>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.</p>

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

CC BY-SA 3.0
2011-06-14T20:31:21.047Z
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
CC BY-SA 3.0
2011-06-14T23:09:29.110Z
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
CC BY-SA 3.0
2011-06-15T05:42:06.123Z
OK -- looks like I've got myself another exercise for the ML course... :) Thanks for the input, Aaron and Lev!
Aryeh
CC BY-SA 3.0
2011-06-17T17:54:47.557Z
@Aaron, maybe this should have been an answer.
Suresh Venkat
<lg.learning><machine-learning>
Agnostic PAC sampling lower bound
Aryeh
# Agnostic PAC sampling lower bound

(Asked by: username_0 on 2011-06-14)

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?

**Tags:** lg.learning, machine-learning
> **Comments:**
> **username_1**: 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.  
> **username_2**: 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...  
> **username_0**: OK -- looks like I've got myself another exercise for the ML course... :) Thanks for the input, Aaron and Lev!  
> **username_3**: @Aaron, maybe this should have been an answer.  

---

## 1 answers

### Answer by username_0 on 2013-01-08. Score: 6

I now realize that a lower bound has indeed been established by Anthony and Bartlett (see the presentation [here](https://rads.stackoverflow.com/amzn/click/026201825X)).

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](https://arxiv.org/abs/1606.08920).

> **Comments:**
> **username_4**: In your paper you do not cite this work (http://www.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?  
> **username_0**: 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.  
> **username_0**: It's now known that proper learning cannot always guarantee the optimal rate for realizable PAC.  

---

