6.3 Glivenko-Cantelli Theorem and Donsker Theorem
We now generalize the preceding discussion to arbitrary function classes.
6.3.1 Glivenko-Cantelli Theorem
Recall that a class \(\mathcal {F}\) is Glivenko-Cantelli when \[\|{\mathbb {P}_n-P}\|_{\mathcal {F}}\xrightarrow {a.s.}0, \] where \[ \mathbb {P}_nf = \frac 1 n \sum _{i=1}^n f(X_i), \quad \|{\mathbb {P}_n-P}\|_{\mathcal {F}} = \sup _f \frac 1 n \sum _{i=1}^nf(X_i) -{\mathbb{E}} f(X). \]
Proof. First, we prove \(\|P_n - P\|_{\mathcal {F}}\to 0\) in mean. Using the symmetrization lemma \begin{align*} \mathbb {E} \|P_n - P\|_{\mathcal {F}} &\le 2 \mathbb {E}_X \mathbb {E}_\epsilon \left \| \frac {1}{n} \sum _{i=1}^n \epsilon _i f(X_i) \right \|_{\mathcal {F}} \\ &\le 2 \mathbb {E}_X \mathbb {E}_\epsilon \left \| \frac {1}{n} \sum _{i=1}^n \epsilon _i f(X_i) \right \|_{\mathcal {F}_M} + 2 P F\{F > M\}. \end{align*}
Use \(\epsilon -\)net \(\mathcal {G}\) to cover \(\mathcal {F}_M\). \[ \mathbb {E}_\epsilon \left \| \frac {1}{n} \sum _{i=1}^n \epsilon _i f(X_i) \right \|_{\mathcal {F}_M} \le \mathbb {E}_\epsilon \left \| \frac {1}{n} \sum _{i=1}^n \epsilon _i f(X_i) \right \|_{\mathcal {G}} + \varepsilon . \] The cardinality of \(\mathcal {G}\) can be chosen equal to \(N(\epsilon , \mathcal {F}_M, L_1(\mathbb {P}_n))\). Use \(\psi _2(x)=e^{x^2}-1\), and use the maximal inequality, we have \begin{align*} \mathbb {E}_\epsilon \left \| \frac {1}{n} \sum _{i=1}^n \epsilon _i f(X_i) \right \|_{\mathcal {G}} + \varepsilon &\le \sqrt {1 + \log N(\varepsilon , \mathcal {F}_M, L_1(\mathbb {P}_n))} \;\sup _{f \in \mathcal {G}} \left \| \frac {1}{n} \sum _{i=1}^n \epsilon _i f(X_i) \right \|_{\psi _2 \mid X} + \varepsilon \\ \text {(Hoeffding)} &\le \sqrt {1 + \log N(\varepsilon , \mathcal {F}_M, L_1(\mathbb {P}_n))} \sqrt {\frac {6}{n}} M + \varepsilon \xrightarrow {P} \epsilon . \end{align*}
\(\mathbb {E} \|P_n - P\|_{\mathcal {F}}\) converges almost surely to \(0\) by the following lemma.
Another direction follows from another side of symmetrization lemma and Sudakov’s inequality. \[ \frac {1}{2}\,\mathbb {E} \left \| \frac {1}{n} \sum _{i=1}^n \epsilon _i \bigl (f(X_i) - P f\bigr ) \right \|_{\mathcal {F}} \le \mathbb {E} \| \mathbb {P}_n - P \|_{\mathcal {F}} \to 0. \] \[ \frac {1}{\sqrt {n}} \sup _{\varepsilon > 0} \varepsilon \sqrt {\log N\!\left (\varepsilon , \mathcal {F}, L_2(\mathbb {P}_n)\right )} \le 3 \mathbb {E}_\xi \left \| \frac {1}{n} \sum _{i=1}^n \xi _i f(X_i) \right \|_{\mathcal {F}}. \] And we get the results. □6.3.2 Donsker Theorem
Recall that a class \(\mathcal {F}\) is P-Donsker when \(\mathbb {G}_n\xrightarrow {d}\mathbb {G}.\) Here we define \(F\) as the envelope of \(\mathcal F\). \[ \mathbb {G}_n f = \sqrt {n}(\mathbb {P}_n - P)f = \frac {1}{\sqrt {n}} \sum _{i=1}^n (f(X_i) - Pf). \]