<p>This is <em>almost</em> 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:
<a href="https://cstheory.stackexchange.com/questions/40217/tight-vc-bound-for-agnostic-learning">Tight VC bound for agnostic learning</a></p>

<p>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:
<a href="http://www.cambridge.org/gb/academic/subjects/computer-science/pattern-recognition-and-machine-learning/neural-network-learning-theoretical-foundations?format=HB&amp;isbn=9780521573535#JEHXi1lP4I6Gl8dg.97" rel="nofollow noreferrer">http://www.cambridge.org/gb/academic/subjects/computer-science/pattern-recognition-and-machine-learning/neural-network-learning-theoretical-foundations?format=HB&amp;isbn=9780521573535#JEHXi1lP4I6Gl8dg.97</a></p>

<p>Regarding the optimality of the Rademacher bound, see the discussion and links here concerning Sudakov's inequality:<a href="https://cstheory.stackexchange.com/questions/40312/rademacher-complexity-beyond-the-agnostic-setting">Rademacher complexity beyond the agnostic setting</a></p>

CC BY-SA 3.0
2018-04-16T15:04:22.233Z
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)?
Clement C.
CC BY-SA 3.0
2018-04-16T15:21:47.087Z
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.
Aryeh
CC BY-SA 3.0
2018-04-16T10:51:44.107Z
2018-04-16T10:58:45.050Z
2018-04-16T10:58:45.050Z
Aryeh
<p>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 </p>

<blockquote>
  <p><strong>Theorem 1.</strong> 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
$$</p>
</blockquote>

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

<blockquote>
  <p><strong>Theorem 2.</strong> $$
\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
$$</p>
</blockquote>

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

CC BY-SA 3.0
2018-04-16T10:45:10.023Z
Possible duplicate of [Tight VC bound for agnostic learning](https://cstheory.stackexchange.com/questions/40217/tight-vc-bound-for-agnostic-learning)
Aryeh
<reference-request><machine-learning><pr.probability><randomized-algorithms><vc-dimension>
Tighter Probability Bounds
xuhafiz
# Tighter Probability Bounds

(Asked by: username_0 on 2018-04-16)

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

**Tags:** reference-request, machine-learning, pr.probability, randomized-algorithms, vc-dimension

> **Comments:**
> **username_1**: Possible duplicate of [Tight VC bound for agnostic learning](https://cstheory.stackexchange.com/questions/40217/tight-vc-bound-for-agnostic-learning)  

---

## 1 answers

### Answer by username_1 on 2018-04-16. Score: 2 | Accepted 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](https://cstheory.stackexchange.com/questions/40217/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](https://cstheory.stackexchange.com/questions/40312/rademacher-complexity-beyond-the-agnostic-setting)

> **Comments:**
> **username_2**: 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)?  
> **username_1**: 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.  

---

