# 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)? Aug 3 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. :( Aug 4 at 19:18
• The log factor is later removed by chaining, see p. 31 right before Sec. 4.4. Aug 4 at 20:20
• Thanks. I have some reading to do then. :) Aug 5 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. Aug 4 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. Aug 4 at 20:18
• Would you mind sharing this Haussler's result, please? Aug 5 at 17:50
• sciencedirect.com/science/article/pii/0097316595900527 Aug 5 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. Aug 6 at 13:57