Let $X$ be a finite set and let $\emptyset\neq \mathcal{H}\subseteq \{ 0,1 \}^{\mathcal{X}}$. Let $\{(X\_n,L\_n)\}\_{n=1}^N$ be i.i.d. random variables on $X\times \{0,1\}$ with law $\mathbb{P}$. Without knowing more of $\mathcal{H}$, what is the best risk-bounds available via VC-dimension or Rademacher-complexity theory on the *true risk*
$$
\sup\_{h\in \mathcal{H}}\,\mathbb{E}\_{(X,L)\sim \mathbb{P}}[I(h(x)=L)] - \frac1{N}\sum\_{n=1}^N\, I(h(X\_n)=L\_n)?
$$



VC-based risk bounds for classifiers on finite set
$\newcommand\HH{\mathcal H}\newcommand\ep\varepsilon$Let
\begin{equation}
 D\_N:=\sup\_{h\in\HH}\Big(E\,I(h(X)=L) - \frac1{N}\sum\_{n=1}^N\, I(h(X\_n)=L\_n)\Big).
\end{equation}


It was shown in (the proof of) [Long's main result, 1999](https://link.springer.com/article/10.1023/A:1007666507971) (which he ascribed to Talagrand) that
\begin{equation}
 P(|D\_N|>\ep)\le\exp\Big(d\_\HH-cN\ep^2)
\end{equation}
for some real $c>0$, all $N$, and all real $\ep>0$, where $d\_\HH$ is the VC dimension of $\HH$.


Similar results, but in terms of certain covering numbers for $\HH$ rather than the VC dimension, were obtained by [Talagrand, 1994](https://projecteuclid.org/journals/annals-of-probability/volume-22/issue-1/Sharper-Bounds-for-Gaussian-and-Empirical-Processes/10.1214/aop/1176988847.full).


At least as recently as in October 2019, these results by Talagrand and Long still [seemed to be the state of the art](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.full).


