An Optimal Sauer Lemma Over $k$-ary Alphabets
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. In 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$.
%and have suboptimal dependence on the number of labels and list size.
% The Sauer-Shelah-Perles Lemma is a fundamental combinatorial inequality that bounds the size of a family of binary vectors in terms of its Vapnik-Chervonenkis (VC) dimension. It plays a central role in combinatorics, probability, and computer science, and underlies the applications of VC theory in discrete mathematics and learning theory.
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 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 improves the dependence on $k$ as well. Our proof uses the polynomial method. In contrast to the classical VC case, where multiple direct combinatorial proofs are known, we are not aware of a purely combinatorial argument in the DS setting. This raises new structural questions about hypothesis classes of bounded DS dimension.
As consequences, we obtain improved sample complexity bounds for list PAC learning and for uniform convergence of list predictors, sharpening recent results of Charikar et al.~(STOC~2023), Hanneke et al.~(COLT~2024), and Brukhim et al.~(NeurIPS~2024).
%and have suboptimal dependence on the number of labels and list size.
% The Sauer-Shelah-Perles Lemma is a fundamental combinatorial inequality that bounds the size of a family of binary vectors in terms of its Vapnik-Chervonenkis (VC) dimension. It plays a central role in combinatorics, probability, and computer science, and underlies the applications of VC theory in discrete mathematics and learning theory.
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 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 improves the dependence on $k$ as well. Our proof uses the polynomial method. In contrast to the classical VC case, where multiple direct combinatorial proofs are known, we are not aware of a purely combinatorial argument in the DS setting. This raises new structural questions about hypothesis classes of bounded DS dimension.
As consequences, we obtain improved sample complexity bounds for list PAC learning and for uniform convergence of list predictors, sharpening recent results of Charikar et al.~(STOC~2023), Hanneke et al.~(COLT~2024), and Brukhim et al.~(NeurIPS~2024).
