Tuesday, November 24, 2020 at 9:30am to 10:00am
Yuval Filmus, Technion, Haifa, Israel
Abstract: The Sauer–Shelah–Perles (SSP) lemma is a fundamental result in VC theory, with important applications in statistical learning theory. It bounds the number of sets in a family in terms of the size of the universe and the VC dimension. We generalize the SSP lemma to some lattices, such as the lattice of subspaces of a finite-dimensional vector space over a finite field. The SSP lemma fails for some lattices, and we identify a local obstruction which we conjecture is the only reason for such failure.
The talk will not assume any familiarity with VC theory or with statistical learning theory.
Joint work with Stijn Cambie (Raboud University Nijmegen), Bogdan Chornomaz (Vanderbilt University), Zeev Dvir (Princeton University) and Shay Moran (Technion).
Zoom Meeting: https://ucla.zoom.us/j/96564290758
Meeting ID: 965 6429 0758
Passcode: Please see your email for the passcode to join via Zoom
Warning: You must be registered under your name to be admitted.