Consider a set \ \mathcal{S}\ with a
sigma algebra of
Borel subsets and a
probability measure \ \mathbb{P} ~. For a class of subsets, : \mathcal{C} \subset \bigl\{ C: C \text{ is measurable subset of }\mathcal{S} \bigr\} and a class of functions : \mathcal{F} \subset \bigl\{ f:\mathcal{S}\to \mathbb{R}, f \mbox{ is measurable}\ \bigr\} define random variables : \bigl\| \mathbb{P}_n - \mathbb{P} \bigr\|_{\mathcal C} = \sup_{C \in {\mathcal C}} \bigl| \mathbb{P}_n(C) - \mathbb{P}(C) \bigr| : \bigl\| \mathbb{P}_n - \mathbb{P} \bigr\|_{\mathcal F} = \sup_{f \in {\mathcal F}} \bigl| \mathbb{P}_n f - \mathbb{P} f \bigr| where \ \mathbb{P}_n(C)\ is the empirical measure, \ \mathbb{P}_n f\ is the corresponding map, and :\ \mathbb{P} f = \int_\mathcal{S} f \ \mathrm{d}\mathbb{P}\ , assuming that it exists.
Definitions • A class \ \mathcal C\ is called a '
Glivenko–Cantelli class
' (or
GC class, or sometimes
strong GC class) with respect to a probability measure if ::\ \bigl\| \mathbb{P}_n - \mathbb{P} \bigr\|_\mathcal{C} \to 0\ almost surely as \ n \to \infty ~. • A class \ \mathcal C\ is a
weak Glivenko-Cantelli class with respect to if it instead satisfies the weaker condition ::\ \bigl\| \mathbb{P}_n - \mathbb{P} \bigr\|_\mathcal{C} \to 0\ in probability as \ n \to \infty ~. • A class is called a
universal Glivenko–Cantelli class if it is a GC class with respect to any probability measure \mathbb{P} on (\mathcal{S}, A). • A class is a
weak uniform Glivenko–Cantelli class if the convergence occurs uniformly over all probability measures \mathbb{P} on (\mathcal{S}, A): For every \varepsilon > 0, ::\ \sup_{\mathbb{P} \in \mathbb{P}(\mathcal{S},A)} \Pr\left(\bigl\| \mathbb{P}_n - \mathbb{P} \bigr\|_\mathcal{C} > \varepsilon\right) \to 0\ as \ n \to \infty ~. • A class is a (strong)
uniform Glivenko-Cantelli class if it satisfies the stronger condition that for every \varepsilon > 0, ::\ \sup_{\mathbb{P} \in \mathbb{P}(\mathcal{S},A)} \Pr\left(\sup_{m \geq n} \bigl\| \mathbb{P}_m - \mathbb{P} \bigr\|_\mathcal{C} > \varepsilon\right) \to 0\ as \ n \to \infty ~. Glivenko–Cantelli classes of functions (as well as their uniform and universal forms) are defined similarly, replacing all instances of \mathcal{C} with \mathcal{F}. The weak and strong versions of the various Glivenko-Cantelli properties often coincide under certain regularity conditions. The following definition commonly appears in such regularity conditions: • A class of functions \mathcal{F} is
image-admissible Suslin if there exists a
Suslin space \Omega and a surjection T:\Omega \rightarrow \mathcal{F} such that the map (x, y) \mapsto [T(y)](x) is measurable \mathcal{X}\times\Omega. • A class of measurable sets \mathcal{C} is image-admissible Suslin if the class of functions \{\mathbf{1}_C \mid C\in\mathcal{C}\} is image-admissible Suslin, where \mathbf{1}_C denotes the
indicator function for the set C.
Theorems The following two theorems give sufficient conditions for the weak and strong versions of the Glivenko-Cantelli property to be equivalent.
Theorem (
Talagrand, 1987) :
Let \mathcal{F} be a class of functions that is integrable \mathbb{P}, and define \mathcal{F}_0 = \{f - \mathbb{P}f \mid f\in \mathcal{F}\}. Then the following are equivalent: •
\mathcal{F} is a weak Glivenko-Cantelli class and \mathcal{F}_0 is dominated by an integrable function •
\mathcal{F} is a Glivenko-Cantelli class Theorem (
Dudley, Giné, and Zinn, 1991) :
Suppose that a function class \mathcal{F} is bounded. Also suppose that the set \mathcal{F}_0 = \{f - \inf f \mid f\in \mathcal{F}\} is image-admissible Suslin. Then \mathcal{F} is a weak uniform Glivenko-Cantelli class if and only if it is a strong uniform Glivenko-Cantelli class. The following theorem is central to statistical learning of
binary classification tasks.
Theorem (
Vapnik and
Chervonenkis, 1968) :
Under certain consistency conditions, a universally measurable class of sets \ \mathcal{C}\ is a uniform Glivenko-Cantelli class if and only if it is a Vapnik–Chervonenkis class. There exist a variety of consistency conditions for the equivalence of uniform Glivenko-Cantelli and Vapnik-Chervonenkis classes. In particular, either of the following conditions for a class \mathcal{C} suffice: • \mathcal{C} is image-admissible Suslin. • \mathcal{C} is universally
separable: There exists a countable subset \mathcal{C_0} of \mathcal{C} such that each set C\in\mathcal{C} can be written as the pointwise limit of sets in \mathcal{C}_0. ==Examples==