Logic seminar

Please note the time

David Lippel, Haverford College

“Reverse VC calculations”

Let F be a family of sets; for example, F is some uniformly definable family in the real field. The Vapnik-Chervonenkis (VC) dimension of F is a measure of the combinatorial complexity of F. Once you know the VC dimension of F, theorems from computational geometry, like the Epsilon-Net Theorem, give nice geometric consequences for F. I will discuss a statistical strategy for reversing the flow of information in these theorems. Instead of starting with knowledge of the VC dimension, we merely hypothesize ”dimension=d” for some value d. Then, we observe the geometric behavior of F (e.g. using computer experiments) and compare the observed behavior with the behavior that is predicted by the theorems (under the hypothesis ”dimension=d”). If our observed results have sufficiently low probability (conditioned on ”dimension=d”), then we can reject the hypothesis ”dimension=d” with a high degree of confidence. A variant of the strategy gives probabilistic lower bounds for the shatter function of F, and thus we get partial information about the VC density of F. Ultimately, we hope to use such methods to analyze VC density in both the reals and the p-adics. This project is joint work with Deirdre Haskell and Nigel Pynn-Coates.