# Lower bound of real valued bounded function

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 )

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 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.

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.
• 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? Feb 19, 2019 at 14:51