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?


1 Answer 1


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)$.

  • $\begingroup$ Thanks for this proof! Can you mind to look at this question? math.stackexchange.com/questions/4472957/… . I have not crossposted here. $\endgroup$
    – user158501
    Jun 15, 2022 at 18:03
  • 1
    $\begingroup$ I wrote to the authors, I hope they will respond to your query. $\endgroup$ Jun 15, 2022 at 19:30

Your Answer

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