Skip to main content
Back

Decades-Old Learning Theory Gap Finally Closes With a Sharp Sauer Inequality

Researchers prove a tight Sauer-type bound for multiclass hypothesis classes using the DS dimension, tightening sample complexity for list PAC learning.

Paper, Full Access
  • A sharp Sauer-Shelah-Perles inequality is proven for k-ary alphabets, parameterized by the DS dimension.
  • The bound is tight for every alphabet size, list size, and dimension value.
  • Improves list PAC sample complexity by a factor of l^5 versus prior work.
  • Uniform convergence bound for list predictors improves from l^2 to linear in l.
  • Proof uses the polynomial method; no purely combinatorial proof is currently known.
  • Motivates open questions about improving the DS^(3/2) sample complexity to linear in DS.

A new result in learning theory closes a decades-old gap in one of the most cited inequalities in the field. The Sauer-Shelah-Perles lemma, which bounds how many distinct labelings a binary hypothesis class can produce in terms of its VC dimension, has a well-known analogue for classes over larger alphabets, but that analogue has never been tight when the alphabet has more than two symbols. A recent paper by Hanneke, Meng, Moran, and Shaeiri establishes a sharp Sauer inequality for multiclass and list prediction, parameterized by the Daniely-Shalev-Shwartz (DS) dimension rather than the older Natarajan dimension.

The consequence extends past aesthetics. The new bound directly improves the best known sample complexity results for list PAC learning and for uniform convergence of list predictors, sharpening prior work by Charikar and Pabbaraju (STOC 2023), Hanneke and coauthors (COLT 2024), and Brukhim and coauthors (NeurIPS 2024).

Where the old bound leaked

Recall the classical setting. If a class of binary vectors has VC dimension d, the Sauer-Shelah-Perles lemma bounds its size by a sum of binomial coefficients. Extending this to k-ary alphabets was originally done through the Natarajan dimension, introduced in the late 1980s. Natarajan proposed the notion as a barrier for PAC learning and showed it is the only barrier, provided that the number of labels is bounded.

Whether the Natarajan dimension characterized learnability in general remained open for decades. Recent work by Brukhim et al. resolved this by characterizing multiclass PAC learnability through the DS dimension, a combinatorial parameter defined by Daniely and Shalev-Shwartz in 2014. A follow-up by