Uniform convergence of Vapnik–Chervonenkis classes under ergodic sampling

By Terrence M. Adams, Andrew B. Nobel. 2010

63 citations recorded by the source corpus.

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 ∈ 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.

Subfields: Discrete Mathematics and Combinatorics, Mathematical Physics, Statistics and Probability

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Discrete Mathematics and Combinatorics

1. Alexander Rakhlin
2. Ambuj Tewari
3. Nathan Kallus
4. Karthik Sridharan
5. Masatoshi Uehara

In Mathematical Physics

1. Alexander Rakhlin
2. Ambuj Tewari
3. Nathan Kallus
4. Karthik Sridharan
5. Masatoshi Uehara

In Statistics and Probability

1. Masatoshi Uehara
2. Nathan Kallus
3. Alexander Rakhlin
4. Ambuj Tewari
5. Karthik Sridharan
6. Stefan Wager
7. Peter Richtárik
8. Susan Athey

Citations in the corpus

• Efficiently Breaking the Curse of Horizon in Off-Policy Evaluation with Double Reinforcement Learning (2019, methodology): “We will either use the condition that Adams and Nobel, 2010 for definition).”
• Efficiently Breaking the Curse of Horizon: Double Reinforcement Learning in Infinite-Horizon Processes (2019, methodology): “The condition (11a) and (11b) are needed to invoke a uniform law of large numbers for an ergodic sequence (Adams and Nobel, 2010).”
• Sequential complexities and uniform martingale laws of large numbers (2015, methodology): “For a countable class with a finite VC dimension, a GC theorem has been recently shown by Adams and Nobel [2] for ergodic sequences.”