An Optimal Sauer Lemma Over $k$-ary Alphabets

Steve Hanneke, Qinglin Meng, Shay Moran +1

The Sauer-Shelah-Perles Lemma is a cornerstone of combinatorics and learning theory, bounding the size of a binary hypothesis class in terms of its Vapnik-Chervonenkis (VC) dimensi…