<p>I'm not sure if claims about optimal constants are meaningful when trying to optimize all 3; often it is the case that one can be made better at the expense of another. One way to simplify the issue is to look at the expectation, so you only have to deal with one constant. This is the approach taken by Devroye-Lugosi (the book suggested by Clément).</p>
<p>The optimal lower bound on the <em>excess risk</em> (a related, but not identical quantity to uniform deviation), was given here:</p>
<p><a href="https://projecteuclid.org/journals/annals-of-statistics/volume-47/issue-5/Exact-lower-bounds-for-the-agnostic-probably-approximately-correct-PAC/10.1214/18-AOS1766.short" rel="nofollow noreferrer">https://projecteuclid.org/journals/annals-of-statistics/volume-47/issue-5/Exact-lower-bounds-for-the-agnostic-probably-approximately-correct-PAC/10.1214/18-AOS1766.short</a></p>
<p>Regarding the optimal constant for the upper bound, the authors say that computing it &quot;seems to be beyond the reach of current methods&quot;. I think it is also the case for uniform deviation.</p>

CC BY-SA 4.0
2021-08-04T19:16:49.947Z
Gasp! That statement is hella scary. I was not necessarily looking for the very absolute tightest, though. I would have been happy with something less crazy that $41^d$ or that bonkers exponent. Tough luck for now I guess.
user332582
CC BY-SA 4.0
2021-08-04T20:18:13.953Z
The constant 41 comes from their simplified proof of Haussler's famous packing number bound; if you go back to his original paper, you'll see much better constants.
Aryeh
CC BY-SA 4.0
2021-08-05T17:50:44.363Z
Would you mind sharing this Haussler's result, please?
user332582
CC BY-SA 4.0
2021-08-05T17:58:45.687Z
https://www.sciencedirect.com/science/article/pii/0097316595900527
Aryeh
CC BY-SA 4.0
2021-08-06T13:57:15.690Z
Thanks for all the replies. I'm marking this question as accepted. I will do some reading and hopefully get a better grasp of it all.
user332582
CC BY-SA 4.0
2021-08-04T08:10:56.660Z
2021-08-04T08:10:56.660Z
Aryeh
<p>The following result is adapted from <a href="https://www.cambridge.org/core/books/neural-network-learning/665C8C7EB5E2ABC5367A55ADB04E2866" rel="nofollow noreferrer">Anthony and Bartlett, 1999 (Theorem 4.9)</a>.</p>
<p><strong>Theorem</strong> There exist positive constants <span class="math-container">$m_0 \le 400$</span>, <span class="math-container">$c_1 \le 8$</span>, <span class="math-container">$c_2 \le 41$</span>, <span class="math-container">$c_3 \ge 1/576$</span> such that, if <span class="math-container">$(\Omega,\mathcal F,\mathbb P)$</span> is a probability space, <span class="math-container">$(X_n)_{n\in \mathbb N}$</span> is a <span class="math-container">$\mathbb P$</span>-i.i.d. sequence of random variables taking values in a measurable space <span class="math-container">$(\mathcal X,\mathcal F_{\mathcal X})$</span>, <span class="math-container">$\mathcal C\subset \mathcal F_{\mathcal X}$</span> is an at-most-countable family of sets with VC dimension <span class="math-container">$d\in \mathbb N$</span>, then, for any <span class="math-container">$\varepsilon&gt;0$</span> and all <span class="math-container">$m\in \mathbb N$</span> such that <span class="math-container">$m \ge m_0(d+1)/\varepsilon^2$</span>, it holds
<span class="math-container">$$
    \mathbb P \left( \sup_{C \in \mathcal C} \left| \frac 1 m \sum_{k=1}^m \mathbb I\{ X_k \in C\} - \mathbb P(X_1 \in C) \right| &gt; \varepsilon \right)
    \le
    c_1 c_2^d \exp (-c_3m\varepsilon^2) \;.
$$</span></p>
<blockquote>
<p>My question is: <em>are these outrageous constants really the best (as far as we know)</em>?</p>
</blockquote>
<p>I am asking because bounds of the form <span class="math-container">$c'_1 m \exp (- c'_3 m \varepsilon^2)$</span> typically holds for vastly better constants <span class="math-container">$c'_1,c'_3$</span> but it seems that when it comes to these sample complexity bounds, nobody cares about the constants, and the focus appears to always be on the rates. This feels a bit underwhelming though because having a logarithmic improvement at a cost of such a huge constants kind of defeats the purpose for any somewhat practical application (if the better rates kick in after a number of seconds higher than the age of the universe, is it really an improvement?). Does anybody know what the &quot;right&quot; (i.e., sharp) constants are for the optimal rate above?</p>

CC BY-SA 4.0
2021-08-03T23:05:35.230Z
Have you checked what Theorem 3.1 from https://www.springer.com/gp/book/9780387951171 gives (combined with the bounded difference inequality)?
Clement C.
CC BY-SA 4.0
2021-08-04T19:18:14.080Z
It seems to me that they have an extra $\log(m)$ term there. Am I wrong? If so, it is what I was trying to get around, unfortunately. :(
user332582
CC BY-SA 4.0
2021-08-04T20:20:15.310Z
The log factor is later removed by chaining, see p. 31 right before Sec. 4.4.
Aryeh
CC BY-SA 4.0
2021-08-05T17:53:52.210Z
Thanks. I have some reading to do then. :)
user332582
<reference-request><machine-learning><pr.probability><lg.learning><vc-dimension>
What is tightest known (VC-style) sample complexity bound for uniform convergence of empirical means?
user332582
# What is tightest known (VC-style) sample complexity bound for uniform convergence of empirical means?

(Asked by: username_0 on 2021-08-03)

The following result is adapted from [Anthony and Bartlett, 1999 (Theorem 4.9)](https://www.cambridge.org/core/books/neural-network-learning/665C8C7EB5E2ABC5367A55ADB04E2866).

**Theorem** There exist positive constants $m\_0 \le 400$, $c\_1 \le 8$, $c\_2 \le 41$, $c\_3 \ge 1/576$ such that, if $(\Omega,\mathcal F,\mathbb P)$ is a probability space, $(X\_n)\_{n\in \mathbb N}$ is a $\mathbb P$-i.i.d. sequence of random variables taking values in a measurable space $(\mathcal X,\mathcal F\_{\mathcal X})$, $\mathcal C\subset \mathcal F\_{\mathcal X}$ is an at-most-countable family of sets with VC dimension $d\in \mathbb N$, then, for any $\varepsilon>0$ and all $m\in \mathbb N$ such that $m \ge m\_0(d+1)/\varepsilon^2$, it holds
$$
\mathbb P \left( \sup\_{C \in \mathcal C} \left| \frac 1 m \sum\_{k=1}^m \mathbb I\{ X\_k \in C\} - \mathbb P(X\_1 \in C) \right| > \varepsilon \right)
\le
c\_1 c\_2^d \exp (-c\_3m\varepsilon^2) \;.
$$

> My question is: *are these outrageous constants really the best (as far as we know)*?

I am asking because bounds of the form $c'\_1 m \exp (- c'\_3 m \varepsilon^2)$ typically holds for vastly better constants $c'\_1,c'\_3$ but it seems that when it comes to these sample complexity bounds, nobody cares about the constants, and the focus appears to always be on the rates. This feels a bit underwhelming though because having a logarithmic improvement at a cost of such a huge constants kind of defeats the purpose for any somewhat practical application (if the better rates kick in after a number of seconds higher than the age of the universe, is it really an improvement?). Does anybody know what the "right" (i.e., sharp) constants are for the optimal rate above?

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

> **Comments:**
> **username_1**: Have you checked what Theorem 3.1 from https://www.springer.com/gp/book/9780387951171 gives (combined with the bounded difference inequality)?  
> **username_0**: It seems to me that they have an extra $\log(m)$ term there. Am I wrong? If so, it is what I was trying to get around, unfortunately. :(  
> **username_2**: The log factor is later removed by chaining, see p. 31 right before Sec. 4.4.  
> **username_0**: Thanks. I have some reading to do then. :)  

---

## 1 answers

### Answer by username_2 on 2021-08-04. Score: 4 | Accepted answer

I'm not sure if claims about optimal constants are meaningful when trying to optimize all 3; often it is the case that one can be made better at the expense of another. One way to simplify the issue is to look at the expectation, so you only have to deal with one constant. This is the approach taken by Devroye-Lugosi (the book suggested by Clément).

The optimal lower bound on the *excess risk* (a related, but not identical quantity to uniform deviation), was given here:

<https://projecteuclid.org/journals/annals-of-statistics/volume-47/issue-5/Exact-lower-bounds-for-the-agnostic-probably-approximately-correct-PAC/10.1214/18-AOS1766.short>

Regarding the optimal constant for the upper bound, the authors say that computing it "seems to be beyond the reach of current methods". I think it is also the case for uniform deviation.

> **Comments:**
> **username_0**: Gasp! That statement is hella scary. I was not necessarily looking for the very absolute tightest, though. I would have been happy with something less crazy that $41^d$ or that bonkers exponent. Tough luck for now I guess.  
> **username_2**: The constant 41 comes from their simplified proof of Haussler's famous packing number bound; if you go back to his original paper, you'll see much better constants.  
> **username_0**: Would you mind sharing this Haussler's result, please?  
> **username_2**: https://www.sciencedirect.com/science/article/pii/0097316595900527  
> **username_0**: Thanks for all the replies. I'm marking this question as accepted. I will do some reading and hopefully get a better grasp of it all.  

---

