# An Optimal Sauer Lemma Over $k$-ary Alphabets

Source: [An Optimal Sauer Lemma Over $k$-ary Alphabets](<https://www.sota2.com/research/paper/69df1bc87d0172140ec7bbd9>)

Collection index: [llms.txt](<https://www.sota2.com/research/llms.txt>)

Data updated: 2026-04-16T05:00:11.996Z

Authors: Steve Hanneke, Qinglin Meng, Shay Moran, Amirreza Shaeiri

Published: 2026-04-14T16:50:38.000Z

## 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 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 generally with its extension, the list-DS dimension -- the combinatorial parameters that characterize multiclass and list PAC learnability. Our bound is tight for every alphabet size $k$, list size $\\ell$, and dimension value, replacing the exponential dependence on $\\ell$ in the Natarajan-based bound by the optimal polynomial dependence, and improving the dependence on $k$ as well. Our proof uses the polynomial method. In contrast to the classical VC case, where several direct combinatorial proofs are known, we are not aware of any purely combinatorial proof in the DS setting. This motivates several directions for future research, which are discussed in the paper.   As consequences, we obtain improved sample complexity upper bounds for list PAC learning and for uniform convergence of list predictors, sharpening the recent results of Charikar et al.~(STOC~2023), Hanneke et al.~(COLT~2024), and Brukhim et al.~(NeurIPS~2024).

## Recorded benchmark results

A research result applies to its stated dataset, split, metric and evaluation configuration. Compare like-for-like settings, preserve the metric's unit and direction, and distinguish paper-reported results from independent reproduction. The best result recorded here is not a claim of exhaustive, current global coverage.

- [List Learning on List Learning (realizable)](<https://www.sota2.com/research/sota/list-learning-on-list-learning-realizable.md>): List Learning; List Learning (realizable); Sample Complexity: 1.5.

## Original sources and implementation

[Original paper](<https://arxiv.org/abs/2604.12952>)

[PDF](<https://arxiv.org/pdf/2604.12952.pdf>)