1
$\begingroup$

This question is about applying probabilistic bound (Hoeffding inequality) on proof.

The following proof is from Stanford cs229 Machine Learning course's problem set #2-5, proof for uniform convergence on erroneous distribution. http://cs229.stanford.edu/materials/ps2_key.pdf

The author used Hoeffding inequality (6) for step (9)->(10) and setp (11)->(12). If Hoeffding inequality is applied twice, Should the probability for equation (12)~(15) be not $1-\delta$, rather $(1-\delta)^2 $?

Any comments would be deeply appreciated. Thanks.

A proof for uniform convergence on some distribution

$\endgroup$
1
$\begingroup$

I think step (9)->(10), (11)->(12) are using the same condition, just by looking at your assumption, it should be $w.p. (1-\delta)$ we have both $\epsilon_\tau(h) \le \hat\epsilon_\tau(h) + \bar\gamma$ and $\hat\epsilon_\tau(h) \le \epsilon_\tau(h) + \bar\gamma$. The former one is used at (9), and the latter one is used at (11)

$\endgroup$
  • $\begingroup$ Thank you for kind advice! :-D I miss college days when I could ask this question to friends. $\endgroup$ – Chul-Woong Yang Feb 3 '18 at 5:33

Your Answer

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

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