Vapnik-Chervonenkis type conditions and uniform Donsker classes of functions
type: Item
instance of: scholarly article
title: Vapnik-Chervonenkis type conditions and uniform Donsker classes of functions
zbMATH Open document ID: 1044.60027
author: Michel Talagrand
published in: The Annals of Probability
publication date: 2004-06-10T00:00:00Z
full work available at URL: https://projecteuclid.org/euclid.aop/1055425790
review text: 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.
Mathematics Subject Classification ID: 60F17
zbMATH DE Number: 2072330
zbMATH Keywords: shattering
zbMATH Keywords: combinatorial dimension
zbMATH Keywords: Donsker classes
reviewed by: Ken-ichi Yoshihara
MaRDI profile type: Publication
OpenAlex ID: W2022644078
cites work: Scale-sensitive dimensions, uniform convergence, and learnability
cites work: Universal Donsker classes and metric entropy
cites work: Uniform Central Limit Theorems
cites work: Uniform and universal Glivenko-Cantelli classes
cites work: Some limit theorems for empirical processes (with discussion)
cites work: Gaussian characterization of uniform Donsker classes of functions
cites work: Sign-Embeddings of l n 1
cites work: Probability Inequalities for Sums of Bounded Random Variables
cites work: Entropy and the combinatorial dimension
cites work: The Glivenko-Cantelli problem
cites work: Type, infratype and the Elton-Pajor theorem
cites work: The Glivenko-Cantelli problem, ten years later
DOI: 10.1214/AOP/1055425790
description: scientific article; zbMATH DE number 2072330