Uniform convergence of Vapnik-Chervonenkis classes under ergodic sampling

DOI10.1214/09-AOP511zbMATH Open1220.60019OpenAlexW3103988912WikidataQ105584253 ScholiaQ105584253MaRDI QIDQ989178FDOQ989178

Authors: T. M. Adams, Andrew B. Nobel 

Publication date: 30 August 2010

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

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.

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

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

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)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• 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
• Title not available (Why is that?)
• Measuring the capacity of sets of functions in the analysis of ERM
• Semiparametric estimation of moment condition models with weakly dependent data
• Sequential complexities and uniform martingale laws of large numbers
• Independent block identification in multivariate time series
• Title not available (Why is that?)
• Title not available (Why is that?)
• 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 counterexample concerning the extension of uniform strong laws to ergodic processes
• A general approach to the joint asymptotic analysis of statistics from sub-samples
• 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)