<p>You have to specify a loss -- say, <span class="math-container">$\ell_1$</span> for simplicity, so the risk of a hypothesis <span class="math-container">$h$</span> is <span class="math-container">$E|h(X)-Y|$</span>. Then at the very least, by reduction to the VC case, to achieve accuracy <span class="math-container">$\epsilon$</span> you will need at least 
<span class="math-container">$$\Omega(d_F(\epsilon)/\epsilon^2)
\qquad (*)$$</span>
examples, where <span class="math-container">$d_F(\epsilon)$</span> is the fat-shattering dimension of the class <span class="math-container">$F$</span> at scale <span class="math-container">$\epsilon$</span>. Just take an <span class="math-container">$\epsilon$</span>-shattered set of size <span class="math-container">$d_F(\epsilon)$</span> and put uniform point masses on the <span class="math-container">$x$</span>'s, while setting the <span class="math-container">$y$</span>'s to be <span class="math-container">$\pm\epsilon$</span> with appropriate probabilities (just as in the binary case -- which is carefully worked out in these notes:
<a href="https://www.cs.bgu.ac.il/~asml162/wiki.files/agnostic-pac-lb.pdf" rel="nofollow noreferrer">https://www.cs.bgu.ac.il/~asml162/wiki.files/agnostic-pac-lb.pdf</a>
).</p>

<p>I don't know if this is the tightest bound possible; the best upper bound I know, given here, 
<a href="https://www.sciencedirect.com/science/article/pii/S0022000097915579" rel="nofollow noreferrer">https://www.sciencedirect.com/science/article/pii/S0022000097915579</a>
behaves as
<span class="math-container">$$ O(\Omega(d_F(\epsilon/5)\log(1/\epsilon)/\epsilon^3.$$</span></p>

<p>Update.
The lower bound <span class="math-container">$(*)$</span> is for excess risk -- i.e., in the agnostic PAC setting. The realizable PAC lower bound can be straightforwardly be adapted to give a lower bound of <span class="math-container">$\Omega(d_F(\epsilon)/\epsilon)$</span> for the absolute risk.</p>

CC BY-SA 4.0
2019-02-19T14:51:55.613Z
Thank you for the answer. In the notes I see the derivation for the excess risk, while the paper you provided uses $\epsilon$ as absolute loss (in $l_1$). Do you have a guide to lead through the main results in this respect?
Dr.Raghnar
CC BY-SA 4.0
2019-02-19T14:58:04.127Z
I'm not sure I understand your question fully, but I added an update concerning the realizable case/non-excess risk.
Aryeh
CC BY-SA 4.0
2019-02-18T20:16:48.270Z
2019-02-19T14:57:27.627Z
2019-02-19T14:57:27.627Z
Aryeh
<p>Is well known that the lower bound on number of example necessary to reach a given error for concept classes <span class="math-container">$\Omega(d/\varepsilon)$</span> (cf. also
<a href="https://cstheory.stackexchange.com/questions/6995/agnostic-pac-sampling-lower-bound">Agnostic PAC sampling lower bound</a>
)</p>
<p>I am looking for the lower bound of example necessary to define a real value bound function as PAC learnable, given a VC dimension, bound and precision.</p>
<p>I have found in <a href="https://www.sciencedirect.com/science/article/pii/089054019290010D" rel="nofollow noreferrer">this '92 paper by Haussler</a> some bounds for finite and infinite sets some bounds. E.g. for a finite set of <span class="math-container">$|F|$</span> bounded function <span class="math-container">$0 \leq f \leq M$</span>, theorem 1 states that
<span class="math-container">$$ m \geq \frac{M^2}{2\epsilon^2} \left( \textrm{ln}|F| + \frac{2}{\delta}\right),$$</span>
with probability <span class="math-container">$\delta$</span>. Where <span class="math-container">$m$</span> is the number of training examples needed, and <span class="math-container">$\epsilon$</span> is defined as the &quot;regret&quot;, that is the difference between the optimal and empirical risks.</p>
<p>I was wondering:</p>
<ol>
<li>if there is a result regarding the optimal risk as well and evaluate the total risk, like for the concept classes bounds</li>
<li>if there are new results regarding these bounds for real-valued functions.</li>
</ol>

<machine-learning><lg.learning><pac-learning>
Lower bound of real valued bounded function
Dr.Raghnar
# Lower bound of real valued bounded function

(Asked by: username_0 on 2019-02-18)

Is well known that the lower bound on number of example necessary to reach a given error for concept classes $\Omega(d/\varepsilon)$ (cf. also
[Agnostic PAC sampling lower bound](https://cstheory.stackexchange.com/questions/6995/agnostic-pac-sampling-lower-bound)
)

I am looking for the lower bound of example necessary to define a real value bound function as PAC learnable, given a VC dimension, bound and precision.

I have found in [this '92 paper by Haussler](https://www.sciencedirect.com/science/article/pii/089054019290010D) some bounds for finite and infinite sets some bounds. E.g. for a finite set of $|F|$ bounded function $0 \leq f \leq M$, theorem 1 states that
$$ m \geq \frac{M^2}{2\epsilon^2} \left( \textrm{ln}|F| + \frac{2}{\delta}\right),$$
with probability $\delta$. Where $m$ is the number of training examples needed, and $\epsilon$ is defined as the "regret", that is the difference between the optimal and empirical risks.

I was wondering:

1. if there is a result regarding the optimal risk as well and evaluate the total risk, like for the concept classes bounds
2. if there are new results regarding these bounds for real-valued functions.

**Tags:** machine-learning, lg.learning, pac-learning


---

## 1 answers

### Answer by username_1 on 2019-02-18. Score: 1

You have to specify a loss -- say, $\ell\_1$ for simplicity, so the risk of a hypothesis $h$ is $E|h(X)-Y|$. Then at the very least, by reduction to the VC case, to achieve accuracy $\epsilon$ you will need at least
$$\Omega(d\_F(\epsilon)/\epsilon^2)
\qquad (\*)$$
examples, where $d\_F(\epsilon)$ is the fat-shattering dimension of the class $F$ at scale $\epsilon$. Just take an $\epsilon$-shattered set of size $d\_F(\epsilon)$ and put uniform point masses on the $x$'s, while setting the $y$'s to be $\pm\epsilon$ with appropriate probabilities (just as in the binary case -- which is carefully worked out in these notes:
<https://www.cs.bgu.ac.il/~asml162/wiki.files/agnostic-pac-lb.pdf>
).

I don't know if this is the tightest bound possible; the best upper bound I know, given here,
<https://www.sciencedirect.com/science/article/pii/S0022000097915579>
behaves as
$$ O(\Omega(d\_F(\epsilon/5)\log(1/\epsilon)/\epsilon^3.$$

Update.
The lower bound $(\*)$ is for excess risk -- i.e., in the agnostic PAC setting. The realizable PAC lower bound can be straightforwardly be adapted to give a lower bound of $\Omega(d\_F(\epsilon)/\epsilon)$ for the absolute risk.

> **Comments:**
> **username_0**: Thank you for the answer. In the notes I see the derivation for the excess risk, while the paper you provided uses $\epsilon$ as absolute loss (in $l_1$). Do you have a guide to lead through the main results in this respect?  
> **username_1**: I'm not sure I understand your question fully, but I added an update concerning the realizable case/non-excess risk.  

---

