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