In the book »Understanding Machine Learning: From Theory to Algorithms«, written by Ben-David and Shalev-Shwartz, there is a proof which I do not understand. The context is proving that if a hypothesis class $\mathcal{H}$ has finite VC dimension, then it enjoys the uniform convergence property.
The proof of this implication involves Sauer's Lemma (hypothesis classes with finite VC dimension have »small effective size«) and a theorem stating that hypothesis classes with »small effective size« enjoy the uniform convergence property. The proof of the latter sub-implication involves this theorem (Theorem 6.11 in the book):
Let $\mathcal{H}$ be a hypethesis class of binary classifiers over a domain $\mathcal{X}$ and let $\tau_{\mathcal{H}}$ be its growth function (from Sauer's Lemma). Then, for all $m \in \mathbb{N}$, for every distribution $\mathcal{D}$ over $\mathcal{X} \times \{0, 1\}$ and every $\delta \in (0, 1)$: $$ \forall h \in \mathcal{H}: \mathbb{P}_{S \sim \mathcal{D}^m}\left[ | L_{\mathcal{D}}(h) - L_S(h) | \leq \frac{4 + \sqrt{\log(\tau_{\mathcal{H}}(2m))}}{\delta\sqrt{2m}} \right] \geq 1 - \delta $$
In the proof for this theorem it is stated, that it follows immediately from the inequality $$ \mathbb{E}_{S \sim \mathcal{D}^m}\left[ \sup_{h \in \mathcal{H}} | L_{\mathcal{D}}(h) - L_S(h) | \right] \leq \frac{4 + \sqrt{\log(\tau_{\mathcal{H}}(2m))}}{\sqrt{2m}}, $$ the fact that the random variable $\theta := \sup_{h \in \mathcal{H}} | L_{\mathcal{D}}(h) - L_S(h) |$ is nonnegative and Markov's inequality.
However, I do not see how it follows immediately from those facts. What am I missing?
