# Applying Hoeffding inequality twice in proof for a cs229(ml) problem

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.

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)