Uniform convergence of Vapnik-Chervonenkis classes under ergodic sampling (Q989178): Difference between revisions

Let \({\mathcal X}\) be a complete separable metric space and let \(\mathcal C\subseteq{\mathcal B}({\mathcal X})\) be a countable family of Borel subsets with finite VC dimension \(\dim({\mathcal C})<\infty\), where \(\dim({\mathcal C})\) is the largest integer \(k\in{\mathbb{N}}\) such that the shatter coefficient \(S(D;{\mathcal C})=|\{C\cap D: C\in{\mathcal C}\}|=2^k\) for some \(k\)-element subset \(D\subseteq{\mathcal X}\). The authors show that, for any stationary ergodic sequence \((X_n)_{n\geq1}\) with values in \({\mathcal X}\) the relative frequency of \(C\in{\mathcal C}\) converges uniformly to the limiting probability for some independent random variable \(X\) having the same distribution as \(X_1\), i.e., as \(n\to\infty\), \[ \sup_{C\in{\mathcal C}}\bigg|\frac1n\sum_{k=1}^n1_{\{X_k\in C\}}-P\{X\in C\}\bigg|\to0 \] almost surely. This extends previous results for i.i.d. or strongly mixing sequences originated by \textit{V. N. Vapnik} and \textit{A. Ya. Chervonenkis} [Theory Probab. Appl. 16, 264--280 (1971; Zbl 0247.60005)]. As a consequence the authors establish a related uniform convergence result for countable families \({\mathcal F}\) of Borel-measurable functions \(f:{\mathcal X}\to\mathbb R\), i.e., \[ \sup_{f\in{\mathcal F}}\bigg|\frac1n\sum_{k=1}^nf(X_k)-\mathbb E[f(X)]\bigg|\to0 \] almost surely in case \({\mathcal F}\) is a VC-major or VC-graph class. A brief discussion of what happens in case \({\mathcal C}\) (or \({\mathcal F}\)) is uncountable is also presented. Compared to the classical methods, the authors present a new technique of proof not relying on symmetrization techniques, probability inequalities, or mixing conditions. The proof of the main result is obtained by counterposition in the sense that, if the relative frequencies of sets \(C\in{\mathcal C}\) fail to converge uniformly, then \(\dim({\mathcal C})=\infty\). This result is first established for the special case \({\mathcal X}=[0,1]\) and the general case is then reduced to this special case by a series of reduction arguments. The reader is well guided through the details of the complex proof structure.