An Optimal Sauer Lemma Over k-ary Alphabets
Published in arXiv preprint arXiv:2604.12952, 2026
We prove a tight Sauer inequality for multiclass and list prediction using the DS and list-DS dimensions. The result improves sample complexity bounds for list learning and uniform convergence.
Also listed in my CV under the manuscript title “A Sharp Sauer Lemma for Classes of {1, …, K}-valued Functions” (under submission).
Steve Hanneke, Qinglin Meng, Shay Moran, Amirreza Shaeiri (alphabetical order)
Download Paper
