# What is tightest known (VC-style) sample complexity bound for uniform convergence of empirical means?

The following result is adapted from Anthony and Bartlett, 1999 (Theorem 4.9).

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?

• Have you checked what Theorem 3.1 from springer.com/gp/book/9780387951171 gives (combined with the bounded difference inequality)? Commented Aug 3, 2021 at 23:05
• 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. :( Commented Aug 4, 2021 at 19:18
• The log factor is later removed by chaining, see p. 31 right before Sec. 4.4. Commented Aug 4, 2021 at 20:20
• Thanks. I have some reading to do then. :) Commented Aug 5, 2021 at 17:53

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.

• 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. Commented Aug 4, 2021 at 19:16
• 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. Commented Aug 4, 2021 at 20:18
• Would you mind sharing this Haussler's result, please? Commented Aug 5, 2021 at 17:50
• sciencedirect.com/science/article/pii/0097316595900527 Commented Aug 5, 2021 at 17:58
• 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. Commented Aug 6, 2021 at 13:57