Lower bound of real valued bounded function

Question

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.

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