An Optimal Sauer Lemma Over $k$-ary Alphabets

• URL: http://arxiv.org/abs/2604.12952v1
• Date: Tue, 14 Apr 2026 16:50:38 GMT
• Title: An Optimal Sauer Lemma Over $k$-ary Alphabets
• Abstract summary: We show that the Sauer-Shelah-Perles Lemma bounds are suboptimal for alphabet sizes $k>2$.<n>Our bound is tight for every size $k$, list size $ell$, and dimension value, replacing the exponential dependence on $ell$ in the Natarajan-based bound.<n>In contrast to the classical case, we are not aware of any purely proof in the DS setting.
• Score: 46.089126569274676
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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).

Related papers

• Optimistic Rates for Multiclass PAC Learning [39.91890433860882]
  Worst-case multiclass bounds do not become smaller when the best classifier is already nearly correct.<n>For a class of Natarajan dimension $d_N$ and Daniely-Shalev-Shwartz dimension $d_DS$, the optimal excess risk is known at the two endpoints.<n>We close the gap: at every fixed oracle risk $Lstar$, the optimal excess risk is $widetilde(sqrtLstar d_N/n+d_DS/n)$, uniformly in the alphabet size.
  arXiv  Detail & Related papers  (2026-08-11T12:46:03Z)
• The Sample Complexity of Multiclass and Sparse Contextual Bandits [106.74652380822778]
  We aim to identify an approximately optimal policy from a given class based on bandit feedback.<n>Motivated by bandit multiclass classification with zero-one rewards, we focus on the emph$s$-sparse setting.<n>We show that, with $s$-sparse rewards, the induced model class admits a sharp DEC bound that scales with $s$ and directly yields the optimal rate.
  arXiv  Detail & Related papers  (2026-05-28T09:12:20Z)
• Sample Complexity of Agnostic Multiclass Classification: Natarajan Dimension Strikes Back [84.81507553557556]
  We show that multiclass PAC sample complexity is governed by two distinct dimensions.<n>Unlike binary or online classification, multiclass learning inherently involves two structural parameters.<n>A key ingredient is a novel online procedure based on a self-adaptive multiplicative-weights algorithm performing a label-space reduction.
  arXiv  Detail & Related papers  (2025-11-16T15:47:47Z)
• Private List Learnability vs. Online List Learnability [26.86418374191696]
  This work explores the connection between differential privacy (DP) and online learning in the context of PAC list learning.<n>We prove that a finite $k$-monotone dimension is another necessary condition for DP $k$-list learnability, alongside finite $k$-Littlestone dimension.
  arXiv  Detail & Related papers  (2025-06-15T14:10:46Z)
• Learning and Computation of $Φ$-Equilibria at the Frontier of Tractability [85.07238533644636]
  $Phi$-equilibria is a powerful and flexible framework at the heart of online learning and game theory.<n>We show that an efficient online algorithm incurs average $Phi$-regret at most $epsilon$ using $textpoly(d, k)/epsilon2$ rounds.<n>We also show nearly matching lower bounds in the online setting, thereby obtaining for the first time a family of deviations that captures the learnability of $Phi$-regret.
  arXiv  Detail & Related papers  (2025-02-25T19:08:26Z)
• Fast Rates for Bandit PAC Multiclass Classification [73.17969992976501]
  We study multiclass PAC learning with bandit feedback, where inputs are classified into one of $K$ possible labels and feedback is limited to whether or not the predicted labels are correct. Our main contribution is in designing a novel learning algorithm for the agnostic $(varepsilon,delta)$PAC version of the problem.
  arXiv  Detail & Related papers  (2024-06-18T08:54:04Z)
• A Characterization of List Learnability [15.368858716555888]
  We consider list PAC learning where the goal is to output a list of $k$ predictions. Generalizing the recent characterization of multiclass learnability, we show that a hypothesis class is $k$-list learnable if and only if the $k$-DS dimension is finite.
  arXiv  Detail & Related papers  (2022-11-07T21:28:05Z)
• Unlabelled Sample Compression Schemes for Intersection-Closed Classes and Extremal Classes [16.684376456880642]
  We show that all classes of VC dimension $d$ admit unlabelled compression schemes of size $O(d)$. We also prove that all intersection-closed classes with VC dimension $d$ admit unlabelled compression schemes of size at most $11d$.
  arXiv  Detail & Related papers  (2022-10-11T13:54:41Z)
• Sample-efficient proper PAC learning with approximate differential privacy [51.09425023771246]
  We prove that the sample complexity of properly learning a class of Littlestone dimension $d$ with approximate differential privacy is $tilde O(d6)$, ignoring privacy and accuracy parameters. This result answers a question of Bun et al. (FOCS 2020) by improving upon their upper bound of $2O(d)$ on the sample complexity.
  arXiv  Detail & Related papers  (2020-12-07T18:17:46Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.