**Inequality 1**


\begin{align}
\mathbb{P}\left(\frac{1}{n} \sum\_{i=1}^{n}\left(f\left(x\_{i}\right)-\mathbb{E}[f]\right) z\_{i} \geq \frac{\epsilon}{8}\right) \leq 2 \exp \left(-\frac{\epsilon^{2} n d}{9^{4} c L^{2}}\right)
\end{align}


Since we assumed that the range of the functions is in $[-1,1]$ we have $\mathbb{E}[f] \in[-1,1]$ and hence:


**Inequality 2**


$$
\mathbb{P}\left(\exists f \in \mathcal{F}: \frac{1}{n} \sum\_{i=1}^{n} \mathbb{E}[f] z\_{i} \geq \frac{\epsilon}{8}\right) \leq \mathbb{P}\left(\left|\frac{1}{n} \sum\_{i=1}^{n} z\_{i}\right| \geq \frac{\epsilon}{8}\right)
$$


**By Hoeffding's inequality, the above quantity is smaller than $2 \exp \left(-n \epsilon^{2} / 8^{3}\right)$ (recall that $\left.\left|z\_{i}\right| \leq 2\right)$.**


Thus we obtain with an union bound:
$$
\begin{aligned}
\mathbb{P}\left(\exists f \in \mathcal{F}: \frac{1}{n} \sum\_{i=1}^{n} f\left(x\_{i}\right) z\_{i} \geq \frac{\epsilon}{4}\right) & \leq|\mathcal{F}| \cdot \mathbb{P}\left(\frac{1}{n} \sum\_{i=1}^{n}\left(f\left(x\_{i}\right)-\mathbb{E}[f]\right) z\_{i} \geq \frac{\epsilon}{8}\right)+\mathbb{P}\left(\left|\frac{1}{n} \sum\_{i=1}^{n} z\_{i}\right| \geq \frac{\epsilon}{8}\right) \\
& \leq 2|\mathcal{F}| \cdot \exp \left(-\frac{\epsilon^{2} n d}{9^{4} c L^{2}}\right)+2 \exp \left(-\frac{n \epsilon^{2}}{8^{3}}\right)
\end{aligned}
$$




---


I am not getting how Union bound is getting happened using Ineq 1 and 2. Can anyone help me with that how they able to reach last inequality?



Union Bound of two events?
By the triangle inequality, the event
$$A=\left\{\exists f \in \mathcal{F}: \frac{1}{n} \sum\_{i=1}^{n} f\left(x\_{i}\right) z\_{i} \geq \frac{\epsilon}{4}\right\}$$
is contained in the union of the two events


$$B=\left\{\exists f \in \mathcal{F}: \frac{1}{n} \sum\_{i=1}^{n}\left(f\left(x\_{i}\right)-\mathbb{E}[f]\right) z\_{i} \geq \frac{\epsilon}{8}\right\}$$
and
$$D=\left\{\exists f \in \mathcal{F}: \ \frac{1}{n} \sum\_{i=1}^{n} \mathbb{E}[f] z\_{i} \geq \frac{\epsilon}{8}\right\} \,.
$$
Moreover, $B=\bigcup\_{f \in \mathcal{F}}B\_f$ where
$$B\_f=\left\{ \frac{1}{n} \sum\_{i=1}^{n}\left(f\left(x\_{i}\right)-\mathbb{E}[f]\right) z\_{i} \geq \frac{\epsilon}{8}\right\} \,,
$$
so
$$A\subset \left(\bigcup\_{f \in \mathcal{F}} B\_f \right) \cup B \,$$
To this relation the union bound is applied, together with inequality 2 to bound $P(D)$.


