Uniform convergence of Vapnik--Chervonenkis classes under ergodic sampling

Original · EN

We show that if X is a complete separable metric space and C is a countable family of Borel subsets of X with finite VC dimension, then, for every stationary ergodic process with values in X, the relative frequencies of sets C converge uniformly to their limiting probabilities. Beyond ergodicity, no assumptions are imposed on the sampling process, and no regularity conditions are imposed on the elements of C. The result extends existing work of Vapnik and Chervonenkis, among others, who have studied uniform convergence for i.i.d. and strongly mixing processes. Our method of proof is new and direct: it does not rely on symmetrization techniques, probability inequalities or mixing conditions. The uniform convergence of relative frequencies for VC-major and VC-graph classes of functions under ergodic sampling is established as a corollary of the basic result for sets.