Uniform Approximation and Bracketing Properties of VC classes

2010/07/23 by Terrence Adams, Terrence M. Adams, Andrew B. Nobel +2 · 1 citation
Computer Science · Mathematics · #60F15 (primary) #60G10 #62G05 (secondary) #Algorithms and Data Compression #Complexity and Algorithms in Graphs #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (stat.ML) #Machine Learning and Algorithms #Probability (math.PR) #Statistics Theory (math.ST) #math.PR #math.ST #msc:60F15 #msc:60G10 #msc:62G05 #stat.ML #stat.TH

paper · pdf · doi:10.48550/arxiv.1007.4037

10 pages

arxiv created 2010/07/23 · openalex publication_date 2010/07/23 · arxiv updated 2010/07/26 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We show that the sets in a family with finite VC dimension can be uniformly approximated within a given error by a finite partition. Immediate corollaries include the fact that VC classes have finite bracketing numbers, satisfy uniform laws of averages under strong dependence, and exhibit uniform mixing. Our results are based on recent work concerning uniform laws of averages for VC classes under ergodic sampling.

Citations

• The Gap Dimension and Uniform Laws of Large Numbers for Ergodic\n Processes

Cited by

• Reducing statistical time-series problems to binary classification

Related

• Uniform Approximation of Vapnik-Chervonenkis Classes
• Approximation by uniformly distributed sequences
• Uniform decomposition of probability measures: quantization, classification, rate of convergence
• Uniform Brackets, Containers, and Combinatorial Macbeath Regions
• Improving Generalization Bounds for VC Classes Using the Hypergeometric\n Tail Inversion