How many samples are needed for ERM to have $\epsilon$ excess risk relative to the best hypthosis $h^*$? Assume a bounded (and Lipschitz, if needed) loss function.

The only survey I have been able to find is http://dept.stat.lsa.umich.edu/~tewaria/research/tewari13learning.pdf. Page 20 gives a bound of $O(\frac{d_\epsilon}{\epsilon^2} \log \frac{1}{\epsilon} + \log \frac{1}{\delta})$, where $d_\epsilon$ is the fat-shattering dimension at scale $\epsilon$, but I don't think it is correct. For instance, there should probably be factors of $\epsilon$ on the $\log \frac{1}{\delta}$.

An outline of the proof or a pointer to a survey/paper/lecture notes that has it would be great as well.

  • $\begingroup$ You can find proofs for a quite similar bound at Alon et al Theorem 3.1 and at Bartlett and Long Theorems 12 and 21 $\endgroup$ – Meni Jan 17 '18 at 11:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.