Uniform convergence of Vapnik-Chervonenkis classes under ergodic sampling

DOI10.1214/09-AOP511MaRDI QIDQ989178zbMATH OpenOpenAlexWikidataFDO

Authors T. M. Adams, Andrew B. Nobel

Publication date 30 August 2010

Published in The Annals of Probability (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1010.3162

zbMATH Keywords

VC dimensionVC classstationary ergodic sequenceuniform strong law of large numbers

Mathematics Subject Classification ID

Stationary stochastic processes (60G10) Strong limit theorems (60F15) Combinatorial probability (60C05) Ergodic theorems, spectral theory, Markov operators (37A30) Dynamical systems and their relations with probability theory and stochastic processes (37A50)

Abstract: We show that if $mathcalX$ is a complete separable metric space and $mathcalC$ is a countable family of Borel subsets of $mathcalX$ with finite VC dimension, then, for every stationary ergodic process with values in $mathcalX$, the relative frequencies of sets $CinmathcalC$ 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 $mathcalC$. 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.

Recommendations

• A counterexample concerning uniform ergodic theorems for a class of functions
• A counterexample concerning the extension of uniform strong laws to ergodic processes
• Uniform approximation of Vapnik-Chervonenkis classes
• From uniform laws of large numbers to uniform ergodic theorems
• scientific article; zbMATH DE number 699473

Cites work

• scientific article; zbMATH DE number 3942594 (Why is no real title available?)
• scientific article; zbMATH DE number 3973963 (Why is no real title available?)
• scientific article; zbMATH DE number 46153 (Why is no real title available?)
• scientific article; zbMATH DE number 53676 (Why is no real title available?)
• scientific article; zbMATH DE number 699473 (Why is no real title available?)
• scientific article; zbMATH DE number 1749054 (Why is no real title available?)
• scientific article; zbMATH DE number 3799981 (Why is no real title available?)
• scientific article; zbMATH DE number 765034 (Why is no real title available?)
• scientific article; zbMATH DE number 774952 (Why is no real title available?)
• scientific article; zbMATH DE number 3245885 (Why is no real title available?)
• A counterexample concerning uniform ergodic theorems for a class of functions
• A note on the uniform laws for dependent processes via coupling
• A note on uniform laws of averages for dependent processes
• Combinatorial methods in density estimation
• Consistency in Nonlinear Econometric Models: A Generic Uniform Law of Large Numbers
• Convergence of stochastic processes
• Empirical discrepancies and subadditive processes
• Necessary and Sufficient Conditions for the Uniform Convergence of Means to their Expectations
• On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities
• On the density of families of sets
• Rates of convergence for classes of functions: The non-i.i.d. case
• Rates of convergence for empirical processes of stationary mixing sequences
• Rates of uniform convergence of empirical means with mixing processes
• The Glivenko-Cantelli problem
• The the uniform mean-square ergodic theorem for wide sense stationary processes
• Uniform Central Limit Theorems
• Weak convergence and empirical processes. With applications to statistics

Cited in

(20)

• Modeling of time series using random forests: theoretical developments
• The universal Glivenko-Cantelli property
• Statistical learning based on Markovian data maximal deviation inequalities and learning rates
• Empirical risk minimization and complexity of dynamical models
• scientific article; zbMATH DE number 7415073 (Why is no real title available?)
• Measuring the capacity of sets of functions in the analysis of ERM
• Sequential complexities and uniform martingale laws of large numbers
• Semiparametric estimation of moment condition models with weakly dependent data
• Independent block identification in multivariate time series
• scientific article; zbMATH DE number 3930014 (Why is no real title available?)
• scientific article; zbMATH DE number 7306919 (Why is no real title available?)
• Discrepancy-based theory and algorithms for forecasting non-stationary time series
• Censored quantile regression processes under dependence and penalization
• Instrument variable method based on nonlinear transformed instruments for Hammerstein system identification
• Entropy and the uniform mean ergodic theorem for a family of sets
• A general approach to the joint asymptotic analysis of statistics from sub-samples
• A counterexample concerning the extension of uniform strong laws to ergodic processes
• Uniform approximation of Vapnik-Chervonenkis classes
• Portfolio selection in non-stationary markets
• A counterexample concerning uniform ergodic theorems for a class of functions

This page was built for publication: Uniform convergence of Vapnik-Chervonenkis classes under ergodic sampling

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q989178)