UNIFORM CONVERGENCE OF VAPNIK-CHERVONENKIS CLASSES UNDER ERGODIC SAMPLING

• 成果类型: Article
• 署名作者: Adams, Terrence M.; Nobel, Andrew B.
• 署名单位: United States Department of Defense; University of North Carolina; University of North Carolina Chapel Hill
• 刊物名称: ANNALS OF PROBABILITY
• ISSN/ISSBN: 0091-1798
• DOI: 10.1214/09-AOP511
• 发表日期: 2010
• 页码: 1345-1367
• 关键词: rates; THEOREMS; LAWS

摘要

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 is an element of 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 iid 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