Uniform convergence of Vapnik–Chervonenkis classes under ergodic sampling
Adams, Terrence M. ; Nobel, Andrew B.
Ann. Probab., Tome 38 (2010) no. 1, p. 1345-1367 / Harvested from Project Euclid
We show that if $\mathcal{X}$ is a complete separable metric space and $\mathcal{C}$ is a countable family of Borel subsets of $\mathcal{X}$ with finite VC dimension, then, for every stationary ergodic process with values in $\mathcal{X}$ , the relative frequencies of sets $C\in\mathcal{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 $\mathcal{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.
Publié le : 2010-07-15
Classification:  VC dimension,  VC class,  ergodic process,  uniform convergence,  uniform law of large numbers,  60F15,  37A50,  60C05,  60G10,  37A30
@article{1278593952,
     author = {Adams, Terrence M. and Nobel, Andrew B.},
     title = {Uniform convergence of Vapnik--Chervonenkis classes under ergodic sampling},
     journal = {Ann. Probab.},
     volume = {38},
     number = {1},
     year = {2010},
     pages = { 1345-1367},
     language = {en},
     url = {http://dml.mathdoc.fr/item/1278593952}
}
Adams, Terrence M.; Nobel, Andrew B. Uniform convergence of Vapnik–Chervonenkis classes under ergodic sampling. Ann. Probab., Tome 38 (2010) no. 1, pp.  1345-1367. http://gdmltest.u-ga.fr/item/1278593952/