# Tighter Probability Bounds

Let $\mathcal{F}$ be a class of binary functions on a probability space $\Omega$. For $f \in \mathcal{F}$, let $P(f) =\mathbb{E}(f(Z))$ and $P_n(f) = \frac{1}{n} \sum_{i=1}^n f(Z_i)$ where $Z_i$'s are i.i.d. samples from $\Omega$. It is known that

Theorem 1. If $\mathcal{F}$ has finite VC-dimension $d$, $$\mathbb{P}\left(\sup_{f \in \mathcal{F}} |P_n(f) - P(f)| \leq \sqrt{\frac{8}{n} \left(\log(\frac{4}{\delta}) + d\log(\frac{ne}{d})\right)}\right) \geq 1 - \delta$$

The following bound based on the Rademacher complexity of $\mathcal{F}$, denoted $\mathcal{R}_n(\mathcal{F})$, is also known.

Theorem 2. $$\mathbb{P}\left(\sup_{f \in \mathcal{F}} |P_n(f) - P(f)| \leq 2\mathcal{R}_n(\mathcal{F}) + \sqrt{\frac{1}{2n} \log (\frac{2}{\delta})}\right) \geq 1- \delta$$

Are there other bounds on $\sup_{f\in \mathcal{F}}|P_n(f) - P(f)|$ tighter than the ones above?

This is almost a duplicate (see my comment above) but I'll give a quick answer before it (likely) gets closed. The first inequality in the OP has a superfluous $\log(n/d)$, which may be removed via chaining, as discussed here: Tight VC bound for agnostic learning