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.

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

  • $\begingroup$ 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? $\endgroup$
    – Dr.Raghnar
    Commented Feb 19, 2019 at 14:51
  • $\begingroup$ I'm not sure I understand your question fully, but I added an update concerning the realizable case/non-excess risk. $\endgroup$
    – Aryeh
    Commented Feb 19, 2019 at 14:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.