The Vapnik-Chervonenkis (VC) dimension measures the ability of a family of sets to separate finite collections of points. The VC dimension plays a foundational role in machine learning, empirical processes and combinatorial geometry. In this talk we describe recent results concerning the structure of families with finite VC dimension. Our principal result states the following: for any family of measurable sets in a probability space, either (i) the family has infinite VC dimension or (ii) every set in the family can be approximated to within a given error by a fixed, finite partition. Immediate corollaries include the fact that families with finite VC dimension have finite bracketing numbers, and satisfy uniform laws of large numbers for ergodic processes. We will briefly discuss analogous results for VC major and VC graph families of functions. The talk will include the definition and examples of the VC dimension and related quantities. Joint work with Terry M. Adams
Probability and Combinatorics
Tuesday, October 19, 2010 - 4:30pm
Andrew Nobel
University of North Carolina