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 1


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

  • $\begingroup$ 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)? $\endgroup$
    – Clement C.
    Apr 16, 2018 at 15:04
  • $\begingroup$ 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. $\endgroup$
    – Aryeh
    Apr 16, 2018 at 15:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.