Vapnik-Chervonenkis type conditions and uniform Donsker classes of functions
Let \({\mathcal F}\) be a class of functions defined on a measurable space \(\Omega\). We say that a class of \({\mathcal F}\) of functions \(\varepsilon\)-shatters a set \(F\) if for some point \(x\) in \(F\) there exists a level \(\alpha(x)\in\mathbb{R}\) such that, given any subset \(G\) of \(F\), we can find a function \(f\) in \({\mathcal F}\), such that \(f(x)\leq\alpha(x)\) for \(x\in G\), while \(f(x)\geq \alpha(x)+\varepsilon\) for \(x\) in \(F- G\). We define the shattering function \(S_{\mathcal F}(\varepsilon)\) of \({\mathcal F}\) by \(S_{\mathcal F}(\varepsilon)= \sup\{n:{\mathcal F}\;\varepsilon\text{-shatters a set of cardinality }n\}.\) Let \(D(\varepsilon,{\mathcal F})\) be the Koltchinskii-Pollard capacity. The author proves among others the following: If \({\mathcal F}\) is uniformly bounded and \(\xi\) is some continuous positive nonincreasing function on \((0,\infty)\) such that for each \(\varepsilon> 0\), \(S_{\mathcal F}(\varepsilon)\leq \xi(\varepsilon)\), then \[ \forall\varepsilon< \Delta\quad \log D(\varepsilon,{\mathcal F})\leq \xi(\varepsilon)\log (4\Delta/\varepsilon)^K, \] where \(\Delta\) is the diameter of \({\mathcal F}\) for the uniform norm and \(K\) depends on \(\alpha\) only [cf. the author, ibid. 15, 837--870 (1987; Zbl 0632.60024)]. Combining this with the easy fact that \(S_{\mathcal F}(\varepsilon)\leq \log D(\varepsilon/2,{\mathcal F})\) we see that \(S_{\mathcal F}(\varepsilon)\approx\log D(\varepsilon,{\mathcal F})\) (within log terms). As a corollary, the author establishes that there exists a universal constant \(M\) such that a countable uniformly bounded class \({\mathcal F}\) that satisfies \[ \sup_{\varepsilon}\,\varepsilon^2 S_{\mathcal F}(\varepsilon)(\log(4\Delta/\varepsilon))^M< \infty \] is a uniform Donsker class.
scientific article; zbMATH DE number 2072330