# 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?

## 1 Answer

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

Once that log-factor is removed from the VC bound, it becomes optimal up to constants (i.e., essentially unimprovable). See Section 5 in the Anthony-Bartlett book: http://www.cambridge.org/gb/academic/subjects/computer-science/pattern-recognition-and-machine-learning/neural-network-learning-theoretical-foundations?format=HB&isbn=9780521573535#JEHXi1lP4I6Gl8dg.97

Regarding the optimality of the Rademacher bound, see the discussion and links here concerning Sudakov's inequality:Rademacher complexity beyond the agnostic setting

• I'm curious: if you know it's a near-duplicate, you're the one who noticed it, and know it'll be closed as such, why do you answer it? Are the differences significant enough to justify it (and, in this case, why would it be closed)? Apr 16 '18 at 15:04
• It’s not an exact duplicate. I voted to close but I don’t know if it’ll actually be closed. If it gets closed, so be it. Apr 16 '18 at 15:21