Exact rates in Vapnik-Chervonenkis bounds (Q1868113)

This article contains a sharp exponential bound for the empirical process indexed by Vapnik-Červonenkis (VC) classes of sets, as well as several open problems and a nice historical account of this subject. Here is the main result. Let \[ H(q,p)= q\log(q/p)+ (1- q)\log((1- q)/(1- p))\qquad (q,p\in (0,1)) \] be the Kullback information for the Bernoulli distribution, and for \(0< \varepsilon< 1\) and \(q\in (\varepsilon, 1-\varepsilon)\), set \[ \Lambda_q(\varepsilon)= H(q+ \varepsilon,q)\wedge H(q- \varepsilon,q). \] Let \(S\) be a Polish space, \(\mu\) a probability measure on it, and \(\Gamma\) a VC class of Borel sets of \(S\) of index \(V\). Let \(J= \{q= \mu(C): C\in\Gamma\}\) and \(p= p(\varepsilon)= \text{arg min}_{q\in J}\Lambda_q(\varepsilon)\). Let \(X_i\) be independent identically distributed random variables with law \(\mu\) and \(\mu_n(C)= \sum^n_{i=1} I_C(X_i)/n\), \(n\in\mathbb{N}\), be the corresponding empirical measure. Then, there exists \(K\) such that for all \(n\) and for all \(\varepsilon\) small enough, \[ \text{Pr}\Biggl\{\sup_{C\in\Gamma} |\mu_n(C)- \mu(C)|> \varepsilon\Biggr\}\leq Kn^{3V+ 21}\exp\{- n\Lambda_p(\varepsilon)\}. \] The exponent, which is exact, comes from Chernoff's large deviation bounds for a single \(C\).