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?
