An Optimal Sauer Lemma Over $k$-ary Alphabets
arXiv:2604.12952v1 Announce Type: cross
Abstract: 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) dimension. For classes of fu…