{"id":"arxiv/2604.12952","url":"https://arxiv.org/abs/2604.12952","tags":["cs.LG","math.CO","stat.ML"],"score":0,"title":"An Optimal Sauer Lemma Over $k$-ary Alphabets","domain":"cs.LG","source":"arxiv","authors":["Steve Hanneke","Qinglin Meng","Shay Moran","Amirreza Shaeiri"],"reviews":0,"subject":"cs.LG","summary":"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 functions over a $k$-ary alphabet, namely the multiclass setting, the Natarajan dimension has long served as an analogue of VC dimension, yet the corresponding Sauer-type bounds are suboptimal for alphabet sizes $k>2$. In this work, we establish a sharp Sauer inequality for multiclass and list prediction. Our bound is expressed in terms of the Daniely--Shalev-Shwartz (DS) dimension, and more…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-04-14","reactions":{}}