arXiv CSopen access

An Optimal Sauer Lemma Over $k$-ary Alphabets

An Optimal Sauer Lemma Over k-ary Alphabets Steve Hanneke∗

Qinglin Meng†

Shay Moran‡

Amirreza Shaeiri§

arXiv:2604.12952v1 [cs.LG] 14 Apr 2026

April 2026

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 ℓ, and dimension value, replacing the exponential dependence on ℓ 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).

1

Introduction

The Sauer–Shelah–Perles Lemma is one of the foundational results of extremal combinatorics and statistical learning theory. It states
family of binary vectors of length n with VC Pdthatnany dimension d has cardinality at most i=0 i . This inequality lies at the heart of statistical learning theory, where it underpins the characterization of PAC learnability by the VC dimension. It also plays a central role in applications of VC theory across computer science, discrete mathematics, and probability theory. ∗

Purdue University, USA. Email: [email protected] Purdue University, USA. Email: [email protected] ‡ Technion, Israel and Google Research. Email: [email protected] § Purdue University, USA. Email: [email protected] †

A natural question is how this inequality extends beyond the binary setting. When the label space has size k > 2, the classical VC dimension no longer captures the learnability. Natarajan introduced a multiclass analogue of the VC dimension in the 1980s, and Sauer-type inequalities in terms of the Natarajan dimension have since been widely used. However, these bounds are not tight for k > 2. As we discuss in greater detail later, these suboptimal combinatorial bounds propagate to correspondingly loose guarantees on learning rates and sample complexities. Recent work has established that the correct parameter governing multiclass and list PAC learnability is the Daniely–Shalev-Shwartz (DS) dimension. It is therefore natural to ask whether sharper Sauer-type bounds can be obtained in terms of the DS dimension, and whether such bounds lead to improved quantitative guarantees for learning. In this work we establish a sharp Sauer inequality for k-ary hypothesis classes in terms of the DS dimension, and more generally, its list extension, the ℓ-DS dimension. The resulting bound is tight for all admissible parameter values, and improves previously known bounds based on the Natarajan dimension. Binary Alphabets. We now recall the classical Sauer–Shelah–Perles Lemma more formally, before discussing its multiclass extensions. Let H ⊆ {0, 1}n be a class of binary vectors. A set {i1 , . . . , id } ⊆ [n] of indices is shattered by H if {(h(i1 ), . . . , h(id )) : h ∈ H} = {0, 1}d , that is, if the restriction of H to {i1 , . . . , id } realizes the entire d-dimensional Boolean cube. The Vapnik–Chervonenkis (VC) dimension of H is the maximum size of a shattered set. The Sauer–Shelah–Perles Lemma states that if H has VC dimension d, then |H| ≤

d   X n i=0

i

.

The lemma was independently proved by Vapnik and Chervonenkis in [VC71], Sauer in [Sau72], and Shelah in [She72]; Shelah explicitly credits Micha Perles for an unpublished proof, which motivated the name “Sauer–Shelah–Perles”. The Sauer Lemma admits a remarkable variety of proofs. There are direct inductive arguments, combinatorial proofs via shifting and symmetrization, and linear-algebraic proofs. Gil Kalai is quoted as describing the lemma as unusually accessible: whichever natural approach one takes, a proof seems to emerge. We will return to this point when discussing our extension, for which we presently know only a proof based on an indirect algebraic argument.

Beyond Binary Alphabets Extending the Sauer Lemma to larger alphabets has been studied extensively over the past several decades. In the 1980s, Natarajan introduced a multiclass analogue of the VC dimension [Nat89], with the goal of extending the VC characterization of PAC learnability from binary to multiclass settings.

2

Cubes and the Natarajan dimension. Let Y be a finite alphabet, which without loss of generality we identify with [k] = {0, 1, . . . , k − 1}. For ℓ ≤ k, a subset B ⊆ [k]d is called an ℓ-cube if it is a Cartesian product of ℓ-subsets of [k]; that is, B = Y1 × · · · × Yd , where each Yi ⊆ [k] satisfies |Yi | = ℓ. For a class H ⊆ [k]n , we say that a set {i1 , . . . , id } ⊆ [n] is ℓ-Natarajan-shattered if {(h(i1 ), . . . , h(id )) : h ∈ H} contains an ℓ-cube. The ℓ-Natarajan dimension of H is the maximum size of a set that is (ℓ + 1)-Natarajan-shattered. This recovers several standard notions: when ℓ = 1 one obtains the classical Natarajan dimension, when k = 2 and ℓ = 1 this is exactly the VC dimension, and when ℓ = k − 1 it coincides with the Steele dimension [Ste78]. Natarajan showed that the Natarajan dimension characterizes PAC learnability when the label space Y is bounded. Whether this characterization extends to unbounded label spaces remained open until recently, when Brukhim et al. [BCD+ 22] showed that it does not. They further proved that the dimension characterizing PAC learnability in full generality is the Daniely–Shalev–Shwartz (DS) dimension, introduced in [DSS14], which underlies the main result of this paper. We defer its formal definition to the next section. In the remainder of this section, we discuss Sauer-type bounds based on the Natarajan dimension. Such bounds have been extensively studied in learning theory but also in other areas, including combinatorics, geometry, game theory, dynamical systems, model theory, and complexity theory; see, e.g., [Ste78, KM78, Alo83, Nat89, HL95, FM01, HR10, FS12, DSS18, CP23, GMRT23]. The Sauer-type inequality in this setting asserts that if H ⊆ Y n has ℓ-Natarajan dimension d, then |H| ≤ ℓ

n−d

i d   X n k . i ℓ + 1 i=0

Up to lower-order terms, this yields |H| ≲ ℓ n−d nd k (ℓ+1)d .

(1)

This inequality is due to [DSS18, CP23], extending earlier work of [HL95] in the case ℓ = 1. More recently, [GMRT23] obtained an improved but more intricate bound with the same asymptotic dependence. The bound is tight only when k = 2, in which case it coincides with the classical SauerShelah-Perles Lemma. For larger alphabets, it is not tight. The following two examples illustrate this gap and help motivate the sharper inequality established in this work. Example 1. Let H ⊆ [k]n consist of all vectors v satisfying the following property: for every v ∈ H, we have v(i) < ℓ for all but at most d coordinates i ∈ [n]. Equivalently, each vector may take arbitrary values in [k] on at most d coordinates, and is restricted to {0, 1, . . . , ℓ − 1} on the remaining coordinates. The ℓ-Natarajan dimension of H is d, and a direct counting argument shows that |H| =

d   X n i=0

i 3

(k − ℓ) i ℓ n−i .

In particular, for fixed d, this behaves as |H| ≈ ℓ n−d nd (k − ℓ)d . Compared to (1), this replaces the factor k (ℓ+1)d by (k − ℓ)d , which is exponentially smaller in ℓ and polynomially smaller in k. As we will show later, our inequality in terms of the DS dimension matches this behavior. In fact, this example will turn out to be extremal for the DS-based bound, thereby witnessing its sharpness. 1 Example 2. Consider the case n = 2. A class H ⊆ [k]2 can be identified with the edge set of a k × k bipartite graph. Having ℓ-Natarajan dimension equal to 1 is equivalent to the graph that does not contain a copy of Kℓ+1,ℓ+1 , the complete bipartite graph with sides of size ℓ + 1. Thus, upper bounding |H| in this case becomes a classical Turán-type problem: how many edges can a k × k bipartite graph have if it contains no Kℓ+1,ℓ+1 ? The Kővári-Sós-Turán theorem [KST54] implies that   1 2− ℓ+1 |H| = O k , and this bound is asymptotically tight for ℓ ≤ 2. Whether it is tight for larger ℓ is a longstanding and notoriously difficult open problem in extremal combinatorics (see, e.g. [Buk15]). By contrast, the bound (1) in this case yields only the trivial upper bound |H| = O(k 2 ). These examples illustrate two limitations of the Natarajan-based bound. The first suggests that the exponential dependence on ℓ in (1) may be unnecessarily pessimistic. The second example indicates that tight bounds purely in terms of the ℓ-Natarajan dimension may be difficult to obtain, as even the case n = 2 reduces to longstanding extremal problems. We will show that the bound can be improved when parameterizing by the DS dimension, yielding a sharp inequality and, as a consequence, substantial improvements in PAC sample complexity bounds.

2

The Inequality

We begin by defining the Daniely-Shalev-Shwartz (DS) dimension. The key combinatorial object underlying this notion is the concept of a pseudo-cube, which generalizes the notion of a cube (recall that an ℓ-cube is a Cartesian product of subsets of [k] of size ℓ). Pseudo-cubes and the DS dimension. A nonempty set B ⊆ [k]d is called an ℓ-pseudocube if for every v ∈ B and every coordinate i ∈ [d], there exist distinct vectors v1 , . . . , vℓ−1 ∈ B that agree with v on all coordinates except i. Thus, every vector in an ℓ-pseudo-cube has at least ℓ − 1 neighbors in every coordinate direction. Every ℓ-cube is clearly an ℓ-pseudo-cube, but the converse fails when d > 1. For example, B = {(1, 2), (3, 2), (3, 4), (5, 4), (5, 6), (1, 6)} is not isomorphic to the Boolean cube, while it is indeed a 2-pseudo-cube. For d = 2, a set B ⊆ [k]2 may be viewed as the edge set of a 1

Note that for k = 2 and ℓ = 1, this example also shows the tightness of the classical Sauer–Shelah–Perles Lemma.

4

bipartite graph on [k] ⊔ [k]. In this interpretation, B is an ℓ-pseudo-cube precisely when every non-isolated vertex has degree at least ℓ. In contrast, an ℓ-cube corresponds to the special case of a complete bipartite subgraph Kℓ,ℓ of the ambient k × k graph. For larger d, the combinatorial structure of pseudo-cubes becomes richer and connects to objects from topology and algebra; see [BCD+ 22]. Let H ⊆ [k]n . We say that a set {i1 , . . . , id } ⊆ [n] is ℓ-DS-shattered by H if {(h(i1 ), . . . , h(id )) : h ∈ H} contains an (ℓ + 1)-pseudo-cube. The ℓ-DS dimension of H is the maximum size of a set that is ℓ-DS-shattered. Since every (ℓ + 1)-cube is an (ℓ + 1)-pseudo-cube, the ℓ-DS dimension is always at least the ℓ-Natarajan dimension. Moreover, in the case of k = 2 and ℓ = 1, the ℓ-DS dimension equals the VC dimension. The (ℓ = 1)-DS dimension was introduced by Daniely and Shalev–Shwartz [DSS14] as a candidate dimension characterizing PAC learnability in the multiclass setting. Brukhim et al. [BCD+ 22] later confirmed that the DS dimension indeed characterizes multiclass PAC learnability. Subsequently, Charikar et al. [CP23] showed that, more generally, the ℓ-DS dimension characterizes list-PAC learning with lists of size ℓ, in which the learner outputs, for each input x, a list of at most ℓ labels and succeeds if the true label lies in this list. This list-learning framework arises naturally in applications such as recommendation systems, where a user is presented with a short list of options and success requires that at least one of them is correct. Beyond its practical motivation, list learning has also emerged as a useful intermediate tool in multiclass prediction, serving as a label-space reduction technique [BCD+ 22]. It has been studied extensively in recent years; see, e.g., [BCD+ 22, MSTY23, BHM23, BDMM24, HMT24, HMZ24, HMST25, PS25, CPT25, EK25, CEH+ 26]. We are now ready to state the main combinatorial inequality of the paper. Theorem 2.1 (A Sauer inequality for the Daniely–Shalev-Shwartz dimension). Let H ⊆ [k]n and let d denote the ℓ-DS dimension of H. Then |H| ≤

d   X n i=0

i

(k − ℓ) i ℓ n−i .

This bound coincides exactly with the size of the class in Example 1. Since that class has ℓ-DS dimension d, the inequality is tight for every admissible choice of n, k, ℓ, and d. In the special case ℓ = 1, the bound reduces to d   X n |H| ≤ (k − 1) i , i i=0

which recovers the classical Sauer–Shelah–Perles inequality when k = 2 and replaces the k2 term in the one-dimensional Natarajan bound by the linear factor (k − 1). The tightness of the bound and its dependence on ℓ and k stand in contrast to the 5

inequalities in terms of the ℓ-Natarajan dimension discussed in the previous section. In particular, as seen there, Natarajan-based bounds are not tight in general and exhibit exponential dependence on ℓ, whereas the inequality above achieves tight growth and replaces this by a polynomial dependence. This improvement in the dependence on ℓ plays a central role in the learning-theoretic applications presented in the next section. Organization of the remainder of the paper. We begin with the proof of the main Sauer-type inequality for the DS dimension. The subsequent section discusses several open problems and directions for further investigation, both in combinatorics and in learning theory. The final section turns to learning-theoretic implications, where we demonstrate concrete applications of the inequality to multiclass PAC learning. The discussion section may be read independently of the proof, and the applications section relies only on the statement of the inequality. Readers primarily interested in learningtheoretic consequences may therefore proceed directly to that section. The proof itself may nevertheless be of independent interest as a particularly transparent application of the polynomial method in extremal combinatorics. For additional applications of linear-algebraic methods in combinatorics, see the textbook of Babai and Frankl [BF20].

2.1

Proof

Proof of Theorem 2.1. The proof proceeds by a linear-algebraic argument. At its core lies the following elementary principle: in any vector space, the size of an independent set is at most the size of a spanning set. That is, if I is a linearly independent set and S is a spanning set, then |I| ≤ |S|. Thus, our strategy is to construct a suitable vector space V together with: • a linearly independent set of vectors indexed by the functions in H, and • a spanning set whose size equals the right-hand side of the claimed inequality. Since every spanning set must contain at least as many vectors as any independent set, this will immediately yield the desired upper bound on |H|. The Vector Space. We now describe the vector space V . Let F be any field containing at least k distinct elements; for concreteness, we take F = R. Since H ⊆ [k]n , we may view H as a subset of Rn . We consider V = {f : H → R}, the space of all functions from H to R, equipped with pointwise addition and scalar multiplication. This space is naturally isomorphic to R|H| , since each function is determined by its values on H.

6

The Independent Set. For each h ∈ H, define the indicator function ( 1 if g = h, 1h (g) = 0 otherwise. The collection {1h : h ∈ H} is linearly independent in V , and therefore forms an independent set of size |H|. The Spanning Set. We construct the spanning set using polynomials. Since H ⊆ Rn , every polynomial P (x1 , . . . , xn ) ∈ R[x1 , . . . , xn ] defines a function in V by restriction: namely, for each h ∈ H we evaluate P (h) by plugging in the coordinates of h. Thus, each polynomial induces a function from H to R. Our spanning set will consist of the monomials xe11 xe22 · · · xnen , where the exponents satisfy: • 0 ≤ ei < k for every i, and • all but at most d of the indices i satisfy ei < ℓ. The number of such monomials is d   X n i=0

i

(k − ℓ) i ℓ n−i ,

which matches exactly the right-hand side of the inequality in the theorem. Observe that this set of monomials mirrors the structure of the extremal family from Example 1. We now prove that the above set of monomials spans V . The proof proceeds by induction on n, while k, ℓ, and d are fixed. Base case: n = d. When n = d, the condition that all but at most d of the exponents satisfy ei < ℓ becomes vacuous. Thus, the spanning set consists of all monomials xe11 · · · xenn with 0 ≤ ei < k. We claim that these monomials span V . Indeed, since H ⊆ [k]n , it suffices to show that every function f : [k]n → R can be represented by a polynomial P (x1 , . . . , xn ) in which each variable has degree strictly less than k. 2 This follows from standard polynomial interpolation. In particular, for each h ∈ [k]n , the indicator function 1h can be explicitly written as   n Y  Y xi − j   .  h(i) − j  i=1

j∈[k] j̸=h(i)

2

In the special case k = 2, this reduces to the well-known fact from Boolean function analysis that every function on the Boolean cube {0, 1}n has a multilinear polynomial representation.

7

Each factor depends only on a single coordinate and has degree at most k − 1 in that coordinate. Therefore, every function on [k]n admits a polynomial representation in which each variable has degree less than k, and the claim follows. Induction step: n > d. Since n > d and the ℓ-DS dimension of H is d, the set H does not contain an (ℓ + 1)-pseudo-cube supported on all n coordinates. Indeed, otherwise [n] would be ℓ-DS-shattered, contradicting the definition of d. In particular, H is not an (ℓ + 1)pseudo-cube. Hence, there exist h1 ∈ H and a coordinate i ∈ [n] such that h1 has fewer than ℓ neighbors in direction i within H. Let H−i denote the projection of H onto the coordinates [n] \ {i}. By the induction hypothesis applied to H−i , there exists a polynomial P1 (in the variables xj with j ̸= i) satisfying the degree constraints and such that for every h ∈ H, ( 1 if h(j) = h1 (j) for all j ̸= i, P1 (h) = 0 otherwise. Let S denote the set of values taken by the i-th coordinate among the neighbors of h1 in H. Since h1 has fewer than ℓ neighbors in direction i, we have |S| < ℓ. Define Q1 (x) = P1 (x)

Y xi − j . h1 (i) − j j∈S

Then Q1 satisfies: Q1 (h1 ) = 1,

Q1 (h) = 0 for all h ∈ H, h ̸= h1 .

Moreover, all individual degrees in Q1 satisfy the required constraints: the degree in coordinate i is strictly less than ℓ, and the remaining coordinates satisfy the induction hypothesis constraints. We now remove h1 from H and denote the remaining class by H2 . Since H2 ⊆ H, it is also not an (ℓ + 1)-pseudo-cube, and the same argument produces h2 ∈ H2 and a polynomial Q2 satisfying Q2 (h2 ) = 1, Q2 (h) = 0 for all h ∈ H2 , h ̸= h2 . Continuing like this, we obtain an ordering h1 , h2 , . . . of H and polynomials Q1 , Q2 , . . . such that ( 1 if i = j, Qi (hj ) = 0 if i > j. Thus, the evaluation matrix Aij = Qi (hj ) is triangular with ones on the diagonal. In particular, the polynomials Q1 , . . . , Q|H| are linearly independent in V . Since there are |H| of them and dim V = |H|, they form a basis of V . Since each Qi is a linear combination of the allowed monomials, it follows that those monomials span V , as required.

8

2.2

Discussion and Open Problems

On the algebraic nature of the proof. Our proof relies on a linear-algebraic argument. Although algebraic methods have repeatedly proved powerful in extremal combinatorics, it is natural to wonder whether the DS Sauer inequality admits a direct combinatorial proof. Beyond aesthetic considerations, such a proof could shed light on the structural properties of hypothesis classes with finite DS dimension, and might even help address open problems in learning theory. A central open question in multiclass PAC learning is to determine the optimal dependence of the sample complexity on the DS dimension. The best known lower bound scales as DS/ε, where ε is the accuracy parameter, while the best known upper bound (due to [HMZ24]) scales as DS3/2 log(DS/ε) log(DS) . ε It is widely believed that the upper bound is not tight and can be improved to match the linear dependence suggested by the lower bound. In the binary setting, the optimal VC/ε upper bound is obtained via arguments that are closely tied to combinatorial proofs of the classical Sauer-Shelah-Perles lemma, such as the shifting/symmetrization argument and the inductive proof based on the inclusion graph [HLW94].3 It is, therefore, natural to speculate that a combinatorial proof of the DS Sauer inequality could lead to improved sample complexity bounds in the multiclass case as well. Special cases admitting combinatorial proofs. In certain restricted settings, purely combinatorial arguments are available. For example, when n = 2, a class H ⊆ [k] × [k] may be viewed as the edge set of a bipartite graph on [k] ⊔ [k]. In this case, having ℓ-DS dimension 1 is equivalent to the property that every nonempty subgraph contains a vertex of degree at most ℓ. In this case, a direct combinatorial proof of the bound is obtained by repeatedly peeling off a vertex of degree at most ℓ and deleting all incident edges. Since each step removes at most ℓ edges and the process continues for 2k steps, a simple counting argument yields |H| ≤ ℓ(2k − ℓ), which matches the bound of Theorem 2.1 for n = 2 and d = 1. There is also a combinatorial proof in the case d = ℓ = 1 and arbitrary n and k. This argument was found by Nitay Amiel, an undergraduate student at the Technion, and is presented in Appendix A. Relationship between ℓ-Natarajan and ℓ-DS dimensions. It is also natural to ask how the ℓ-Natarajan and ℓ-DS dimensions compare. It follows immediately from the definitions that ℓ-Nat(H) ≤ ℓ-DS(H). 3

There are alternative proofs of the optimal VC/ε bound, for example the argument of [Han16], which is effectively built upon uniform convergence analysis for certain conditional distributions. However, such uniform convergence techniques do not extend to the multiclass setting.

9

In the other direction, a general upper bound of the form ℓ-DS(H) ≤ O(ℓ · ℓ-Nat(H) · log k) follows from the Sauer inequality for the ℓ-Natarajan dimension. Indeed, suppose a set of size n is ℓ-DS-shattered. Then the restriction of H to this set contains an (ℓ + 1)-pseudo-cube, and in particular at least ℓn distinct vectors. On the other hand, if the ℓ-Natarajan dimension equals d, the Natarajan-Sauer bound implies that the number of distinct vectors on this set is at most i d   X n k n−d ℓ . i ℓ+1 i=0 Comparing the two bounds and solving for n yields n = O(ℓd log k), as claimed. It would be interesting to determine whether the factor of ℓ in this upper bound is necessary, or whether a sharper relationship between the two dimensions can be established. Maximum classes for the DS dimension. In the classical VC setting, a class is called maximum if it meets the Sauer–Shelah–Perles inequality with equality for all n. Such classes have been extensively studied in learning theory, combinatorics, geometry, and even computational biology [FW95, KW07, RBR09, RR12, RRB15, MW16, AMY17, CKP21, CCMW22, CCH+ 24, Law83, BLR89, GW94, BR95, Mor12, CKP22, Dre96, BCDK06]. They exhibit rich mathematical structure, with connections to geometry, topology, and algebra. Since our Sauer-type inequality for the DS dimension is tight, DS-maximum classes exist as well. It is therefore natural to ask whether these classes possess additional structure, and whether they admit alternative characterizations beyond the extremal counting construction. In the VC case, much of the structural understanding of maximum classes arises from combinatorial proofs of the classical Sauer lemma. Accordingly, exploring DS-maximum classes is naturally aligned with the search for a combinatorial proof of the DS Sauer inequality. A systematic study of DS-maximum classes therefore constitutes a promising direction for future work. Other algebraic Sauer inequalities. The present result is not the only instance in which algebraic techniques have been used to derive Sauer-type inequalities. There exist linearalgebraic proofs of the classical Sauer inequality [FP83, Smo97, MR16], as well as algebraic proofs for the corresponding inequalities for the Recursive Teaching dimension [SSYZ14] and for the Graph dimension [SYZ14].4 For the latter two dimensions, no purely combinatorial proofs are currently known. It would be interesting to understand whether such proofs exist, and whether they might reveal additional structural insights. 4 Related algebraic arguments have also been useful for other types of learning theoretic results. For instance, [YHC11] prove a result on identifiability of prior distributions over VC classes from data distributions, via a nested induction argument related to the one in our proof.

10

Moreover, in [SYZ14], the authors introduce a broader family of combinatorial dimensions - generalizing the Graph dimension - for which they establish tight Sauer-type bounds via algebraic methods. While the DS dimension does not appear to be a special case of this family, it would be interesting to clarify how it relates to these dimensions. For example, it is known that the DS dimension is upper bounded by the Graph dimension, but it is unclear how it compares to the other members of that family.

3

Implications for List Learning

List prediction is a natural and increasingly important extension of classical multiclass classification. Rather than outputting a single label, the learner outputs a short list of labels, and the prediction is deemed successful if the true label appears in this list. This relaxation arises in many practical settings. In recommendation systems, for example, the goal is not to predict a single item but to present the user with a short list of plausible options, with success measured by whether the user selects one of them (see Figure 1). Similarly, in large-scale classification problems with thousands of labels, it is often more meaningful to output a small candidate set than a single prediction. Another prominent example is the top-k loss function, in which the model is allowed k guesses for each sample. This loss is widely used in machine learning practice and competitions, and can be viewed as a variant of list learning; see, e.g., [LHS15, YLL+ 18]. List prediction also provides a principled way to address label ambiguity. In computer vision tasks, for instance, it may be inherently unclear whether an image depicts a pond or a river, and penalizing the model for every such mistake can be overly restrictive. Allowing a short list of plausible labels offers a natural alternative. From a theoretical perspective, list learning has emerged as a central theme in multiclass learning with large label spaces. Allowing the learner to output a short list of candidate labels can substantially reduce sample complexity, and list prediction has played a key role in a series of recent advances in multiclass and structured learning [BCD+ 22, CP23, MSTY23, BHM23, BDMM24, HMT24, HMZ24, PS25, HS25, HMS25, HMST25, EK25, CEH+ 26, CPT25]. In some of these works, list learning is studied as a goal in its own right, while in others it serves as a structural tool for reducing the label space and for overcoming barriers that arise in classical multiclass PAC learning. List-valued prediction rules also appear in related frameworks such as conformal learning, where algorithms output predictions together with measures of confidence or uncertainty. For example, such procedures may produce a set of plausible labels for an unlabeled test point x, which can be viewed as a list of candidate predictions. See the monograph of [VGS05] and the surveys [SV08, AB21] for further background. List learning is also closely connected to the setting of list-decodable learning in statistics; for a detailed exposition, see, for example, Chapter 5 of the recent textbook by [DK23]. These considerations motivate the formal study of list PAC learning, in which the learner is permitted to output a list of size L, and performance is measured by whether the true label appears in the predicted list.

11

Movie M1 List predictor

User features x

Movie M7 ✓ Movie M12

Figure 1: Illustration of list prediction in a recommendation setting. Given user features x, the learner outputs a short list of items. Prediction succeeds if the user’s true preference appears in the list.

3.1

List PAC Learning

We now formalize the learning setting. Let X be an instance space and Y a label set. A concept class is a set C ⊆ Y X of functions c : X → Y. The learning goal is to identify an unknown target concept c⋆ ∈ C from labeled examples. In classical multiclass PAC learning, the learner outputs a hypothesis h : X → Y that assigns each input a single label. In ℓ-list learning, the learner is allowed to output a set of at most ℓ labels for each input. Formally, an ℓ-list predictor is a function   Y h:X → , ≤ℓ
Y where ≤ℓ denotes the collection of subsets of Y of size at most ℓ. Prediction is deemed correct on (x, y) if y ∈ ĥ(x). We consider the standard realizable PAC model. For a distribution D
Y over X × Y and a function f : X → ≤ℓ , define the population loss   LD (f ) := Pr(x,y)∼D y ∈ / f (x) .
Y In the special case ℓ = 1, we identify ≤1 with Y, and the condition y ∈ / f (x) reduces to the usual misclassification event f (x) ̸= y. A distribution D is said to be realizable by C if inf LD (c) = 0.

c∈C

A learning algorithm receives m i.i.d. samples from D and outputs an ℓ-list predictor ĥ. Definition 3.1 (ℓ-list PAC learnability and sample complexity). Fix ℓ ∈ N. A concept class C is ℓ-list PAC learnable if there exists a learning algorithm A such that for every choice of error parameter ε ∈ (0, 1) and confidence parameter δ ∈ (0, 1) there exists an integer mC (ε, δ) with the following property: for every distribution D realizable by C, when given mC (ε, δ) i.i.d. samples from D, the algorithm outputs an ℓ-list predictor ĥ satisfying   Pr LD (ĥ) ≤ ε ≥ 1 − δ. The minimal such function mC (ε, δ) is called the sample complexity of ℓ-list PAC learning for C. Thus, the sample complexity quantifies the number of examples required to guarantee, 12

with confidence at least 1 − δ, that the resulting ℓ-list predictor has error at most ε. Classical multiclass PAC learning corresponds to the special case ℓ = 1. Allowing for larger lists weakens the prediction requirement and can strictly reduce sample complexity, particularly when the label space is large. The combinatorial parameter governing ℓ-list PAC learnability is the ℓ-DS dimension. For the remainder of this section, we write DSℓ (C) to denote the ℓ-DS dimension of a concept class C. While the preceding sections focused on classes H ⊆ [k]n , the definition of the ℓ-DS dimension naturally extends to arbitrary concept classes C ⊆ Y X . Formally, DSℓ (C) is the largest integer d for which there exist points x1 , . . . , xd ∈ X such that the set {(c(x1 ), . . . , c(xd )) : c ∈ C} contains a finite ℓ-pseudo-cube. If such sets exist for arbitrarily large d, we define DSℓ (C) = ∞. A fundamental result in the theory of list learning states that a concept class C is ℓ-list PAC learnable if and only if DSℓ (C) < ∞ [CP23, BCD+ 22]. This characterization was established by [BCD+ 22] in the case ℓ = 1 (the classical single-label setting), and was later extended by [CP23] to arbitrary ℓ. Beyond this qualitative characterization, a basic and central quantitative question is how the sample complexity depends on d := DSℓ (C) and on ℓ. The analysis of [CP23] yields an upper bound scaling as  6 3/2  ℓd e O , ε up to the standard logarithmic dependence on δ. Subsequently, [BDMM24] developed a boosting-based approach, obtaining an incomparable bound of order  4 5 e ℓd . O ε Using the sharp Sauer inequality for the ℓ-DS dimension established in this work, we obtain the following improved upper bound. Theorem 3.2 (PAC upper bound for ℓ-list learning). Let C ⊆ Y X be a concept class with d = DSℓ (C) < ∞. Then C is ℓ-list PAC learnable with sample complexity  3/2  ℓd + ℓd log(1/δ) e mC (ε, δ) = O , ε e hides polylogarithmic factors in d, ℓ, and 1/ε. where O(·) Notably, the bound has no dependence on the size of the label space, and in particular applies also when Y is infinite.

3.2

List Uniform Convergence

Uniform convergence and empirical risk minimization (ERM), defined below, are among the central principles of statistical learning theory. In the binary setting, the Fundamental 13

Theorem of PAC Learning states that PAC learnability, uniform convergence, and the ERM principle are equivalent [VC71]; see also the textbook treatment in [SSBD14]. More generally, for finite label spaces, uniform convergence and PAC learnability are known to coincide [SSSSS10]. Beyond its theoretical significance, ERM is also closely connected to widely used statistical principles such as maximum likelihood estimation. Informally, uniform convergence refers to the phenomenon whereby, given sufficiently many samples drawn from a distribution, the empirical losses of all hypotheses in a class simultaneously approximate their true population losses. This principle underlies the validity of ERM: if empirical losses uniformly approximate true losses, then minimizing empirical loss is a sound strategy for approximately minimizing population loss. In the context of list learning, following [HMT24], we study uniform convergence for hypothesis classes of ℓ-list predictors rather than single-label predictors. This is natural, since a list learning algorithm outputs an ℓ-list predictor and therefore selects its hypothesis from such a class. Accordingly, the notion of the ℓ-DS dimension naturally
extends to classes Y of list predictors. Let C be a class of ℓ-list predictors c : X → ≤ℓ . We say that a set {i1 , . . . , id } ⊆ [n] is ℓ-DS-shattered by C if {(y1 , y2 , . . . , yd ) : ∃c ∈ C, ∀j, yj ∈ c(ij )} contains an (ℓ + 1)-pseudo-cube. The ℓ-DS dimension of C is the maximum size of a set that is ℓ-DS-shattered. For a dataset S = ((xi , yi ))ni=1 , define the empirical loss n

LS (c) :=

1X 1{yi ∈ / c(xi )}. n i=1

Definition 3.3 (Uniform convergence and uniform sample complexity). A hypothesis class C of ℓ-list predictors satisfies uniform convergence if there exists a function 2 mUC C : (0, 1) → N

such that for every error parameter ε ∈ (0, 1) and confidence parameter δ ∈ (0, 1) the following holds: for every distribution D over X × Y, if S consists of mUC C (ε, δ) i.i.d. samples from D, then with probability at least 1 − δ, sup LD (c) − LS (c) ≤ ε. h∈C

The minimal such function mUC C (ε, δ) is called the uniform convergence sample complexity of C. It was shown by [HMT24] that any ℓ-list learnable class C ⊆ Y X with |Y| = k and DSℓ (C) = d satisfies uniform convergence with sample complexity  2  ℓ d + log(1/δ) UC e mC (ε, δ) = O , ε2 e hides logarithmic factors in k, d, ℓ. where O(·) 14

The following theorem exploits the sharp Sauer inequality for the ℓ-DS dimension established in this work, yielding an improvement in the dependence on ℓ. Theorem 3.4 (Uniform convergence for ℓ-list predictors). Let C ⊆ Y X be a class of ℓ-list predictors with d = DSℓ (C) < ∞ and |Y| = k. Then C satisfies uniform convergence with sample complexity   ℓd + log(1/δ) UC e mC (ε, δ) = O , ε2 e hides polylogarithmic factors in d, ℓ, k. where O(·)

3.3

Overview of the Proofs

In this subsection, we will give the proof sketches for learning and uniform convergence bounds stated above for ℓ-list prediction, and the formal proofs can be found in Section 3.4.1 and Section 3.4.2. Our arguments are based on the proof techniques developed in the works of [CP23, BDMM24, HMT24], whose bounds we refine. In particular, we follow their overall reduction from sample complexity bounds to combinatorial growth bounds. For the list learning guarantees, we refine several parts of the argument, in addition to substituting our new sharp Sauer lemma. For completeness and clarity, we present the proofs in a largely selfcontained manner, highlighting the points at which the new sharp Sauer inequality for the ℓ-DS dimension yields improved quantitative bounds. 3.3.1

Proof sketch for Theorem 3.2

At a high level, the proof proceeds in three stages. We first learn an intermediate ℓ′ -list predictor for some ℓ′ ≫ ℓ. This predictor’s role is to retain the true label with high probability while substantially narrowing the set of candidate labels (from possibly infinite to finite). We then use this intermediate predictor to filter a new independent sample, thereby reducing the original problem to a list learning problem with a finite label space. Finally, we solve this problem to obtain the target ℓ-list predictor. Let d = DSℓ (C). In the first stage, we apply the learner of [CP23] to an i.i.d. sample S1 √ ′ ℓ′ ′ d of size m1 , obtaining an intermediate ℓ -list predictor µ , where ℓ ≤ ℓ(ed) log(2m1 ). In the second stage, we draw another independent sample S2 of size m2 and retain only ′ those examples whose labels belong to the predicted list: Sreal = {(x, y) ∈ S2 : y ∈ µℓ (x)}. Since the distribution is realizable by C, the filtered sample Sreal is still realizable by C. Thus, the first two stages reduce the original list PAC learning problem to learning from a realizable sample, with labels from a ℓ′ s-list. The key tool in the third stage is the one-inclusion-list algorithm of [CP23]. At a high level, this algorithm is analyzed via the one-inclusion graph of the restriction of C to the sample. The vertices of this graph correspond to candidate labelings, and two vertices are adjacent if they differ on a single sample point. An orientation of this graph induces a prediction rule, and the sample complexity is controlled by the maximum ℓ-outdegree of the chosen orientation. Thus, the learning problem is reduced to a combinatorial question: how small can one make the relevant outdegree in the one-inclusion graph? 15

This is precisely where our main improvement enters. A central quantity in the analysis is the ℓ-exponential dimension Eℓ (C) from [CP23], which controls the maximum ℓ-outdegree. The previous argument upper bounded this quantity in terms of ℓ-Natarajan dimension using a Sauer-type bound whose dependence on ℓ is quadratic [DSS15, CP23]. Our optimal Sauer lemma sharpens this counting step by saving a factor of ℓ. Concretely, let g = Eℓ (C), and let S ∈ X g be a sample of size g that is ℓ-exponential shattered by C. Writing H = C|S , the definition of ℓ-exponential dimension gives |H| ≥ (ℓ+1)g . On the other hand, our optimal Sauer lemma implies the upper bound |H| ≤ ℓ

g



eℓ′ g d

d .

Comparing the lower and upper bounds yields g = O(ℓd log ℓ′ ). Thus, our Sauer lemma gives a sharper control of Eℓ (C) than in [CP23]. We combine this with two further improvements in the third stage. First, previous work [CP23] bounds the maximum ℓ-outdegree by the average degree of the one-inclusion graph, and then upper bounds that average degree by ℓ2 Eℓ (C) via induction. Our argument instead uses a sharper flow-based orientation method, inspired by [HLW94], to control the maximum ℓ-outdegree by the shifting average degree of the graph. We then show that this shifting average degree is at most Eℓ (C). This yields an additional factor-ℓ2 improvement. The underlying construction is implemented via an auxiliary integer flow network, and the details are deferred to the formal proof. Second, we use a standard confidence amplification argument from [HLW94] to obtain the final hypothesis, which saves another factor of ℓ2 . More specifically, we repeat the one-inclusion list learner on independent sub-samples and aggregate the resulting hypotheses by a standard voting step. Together, these refinements 5 improve the sample complexity upper  3/2  bound by a factor ofℓ compared  to [CP23]. ′ /δ) d +log(1/δ) ℓd log(ℓ e e Choosing m1 = O and m2 = O , we obtain the total ϵ ϵ  3/2  e ℓd +ℓd log(1/δ) . The formal algorithms and proofs sample complexity m = m1 + m2 = O ϵ are given in Section 3.4.1. 3.3.2

Proof sketch for Theorem 3.4

Before providing the proof sketch of the theorem, we first introduce the graph dimension [VC74, Nat89] that is known to characterize uniform convergence. A sequence S = {xi }ni=1 is Gℓ -shattered by a ℓ-list concept class C if there is p ∈ Y n called a pivot, such that for any b ∈ {0, 1}n there is cb ∈ C such that for all i ∈ [n], we have: 1{pi ∈ cb (xi )} = bi . The ℓ-graph dimension of C is Gℓ (C) the size of the largest Gℓ -shattered sequence, or infinity if there are Gℓ shattered sequences of arbitrary size. Now, according to [VC74], the VC dimension fully characterizes the uniform convergence of a binary hypothesis class. In particular, note that the ℓ-graph dimension of a list hypothesis class can be viewed as the VC dimension of the class of binary functions {(x, y) 7→ 1{y ∈ / c(x)} : c ∈ C}. In this way, for a list hypothesis class C, the ℓ-graph dimension Gℓ (C) fully 16

characterizes uniform convergence and the rate would be Θ

q

Gℓ (C) n



, where n is the sample

size. Thus, the remainder of the proof is upper bounding the ℓ-graph dimension by ℓ-DS dimension. The proof largely follows that of [HMT24], and we use our optimal Sauer lemma to obtain a sharper bound. The proof proceeds by lower bounding the cardinality of the projection class induced by C on a sample of size Gℓ (C) that is ℓ-graph shattered by C, and upper bounding the same quantity in terms of DSℓ (C). Let d = DSℓ (C) and g = Gℓ (C). Let S ∈ X g be a sample of size g that is ℓ-graph shattered by C. Define H = H(C|S ) = {h ∈ Y g : ∃c ∈ C, h ≺ c|S } as the class of projections induced (2ℓ)g g by C on the sample S. The lower bound follows from [HMT24], which gives |H| ≥ 4(2ℓ−1) gℓ . Next, the upper bound follows from our optimal Sauer lemma. In particular, by Theorem 2.1, we have |H| ≤ ℓg (gk)DSℓ (H) . Moreover, DSℓ (C) ≥ DSℓ (H), since any sample that is ℓ-DSg d shattered by H is also ℓ-DS-shattered by C. Thus, we have the upper  bound |H| ≤ ℓ (gk) . g e Combining the lower and upper bounds, we have d ≥ Ω . Finally, combining this ℓ(log g+log k) inequality with the uniform convergence rate in terms of the ℓ-graph dimension completes the proof.

3.4

Complete proofs of Theorem 3.2 and Theorem 3.4

In this section, we provide the complete proofs for Theorem 3.2 and Theorem 3.4. 3.4.1

Proof of Theorem 3.2

We first introduce the ℓ-exponential dimension [CP23] (see also [BCD+ 22]), a dimension directly defined in terms of the number of patterns realizable by the hypothesis class C. Definition 3.5 (ℓ-exponential dimension [CP23]). We say that a hypothesis class C ⊆ Y X ℓ-exponential shatters a sequence S ∈ X d if |H| ≥ (ℓ + 1)d where H = C|S is the restriction of C to S. The ℓ-exponential dimension of a hypothesis class C, denoted by Eℓ (C), is the largest integer d such that C ℓ-exponential shatters some sequence S ∈ X d . For simplicity, we denote ℓ-DS dimension DSℓ (C) as dℓDS and ℓ-exponential dimension Eℓ (C) as dℓE . Next, we define an important combinatorial object associated with a hypothesis class: the one-inclusion graph. Definition 3.6 (One-inclusion graph [HLW94, RBR06]). The one-inclusion graph of H ⊆ Y m is a hypergraph G(H) = (V, E) that is defined as follows. The vertex-set is V = H. For each i ∈ [m] and f : [m] \ {i} → Y, let ei,f be the set of all h ∈ H that agree with f on [m] \ {i}. The edge-set is E = {ei,f : i ∈ [m], f : [m] \ {i} → Y, ei,f ̸= ∅}. We say that the edge ei,f ∈ E is in the direction i, and is adjacent to the hypothesis/vertex h if h ∈ ei,f . Every vertex h ∈ V is adjacent to exactly m edges. The size of the edge ei,f is the size of the set |ei,f |. With respect to the one-inclusion graph, we consider the degrees of its vertices and the average degree of the graph. 17

Definition 3.7 (ℓ-degree [CP23]). Let G(H) = (V, E) be the one-inclusion graph of H ⊆ Y m . The ℓ-degree of a vertex v ∈ V is degℓ (v) = |{e ∈ E : v ∈ e, |e| > ℓ}|. Definition 3.8 (Average ℓ-degree [CP23]). Let G(H) = (V, E) be the one-inclusion graph of H ∈ Y m . The average ℓ-degree of H is avdℓ (H) =

1 1 X degℓ (v) = |V | v∈V |V |

X

|e|.

e∈E:|e|>ℓ

Next, we restate the definition of list orientation from [CP23]. The notion of orienting refers to assigning directions to the edges of a one-inclusion graph toward the lists of vertices they are adjacent to. Such an orientation captures the behavior of a deterministic learning algorithm when it predicts the label of an unlabeled test point, given a set of labeled examples as input. Definition 3.9 (List Orientation[CP23]). A list orientation σ ℓ of the one-inclusion graph G(H) = (V, E) having list size L is a mapping σ ℓ : E → {V ′ ⊆ V : |V ′ | ≤ ℓ} such that for each edge e ∈ E, σ ℓ (e) ⊆ e. With respect to a list orientation σℓ , one can consider the ℓ-outdegree of this orientation. In particular, we have the following definition. Definition 3.10 (ℓ-outdegree of a list orientation [CP23]). Let G(H) = (V, E) be the oneinclusion graph of H, and let σ ℓ be a ℓ-list orientation of it. The ℓ-outdegree of v ∈ V in σ ℓ is outdegℓ (v; σ ℓ ) = |{e : v ∈ e, v ∈ / σ ℓ (e)}|. The maximum ℓ-outdegree of σ ℓ is outdegℓ (σ ℓ ) = sup outdegℓ (v; σ ℓ ). v∈V

Now, we restate the definition of list realizability from [CP23]. Moreover, for completeness, we include the corresponding learning algorithm. Definition 3.11 (List realizability [BCD+ 22]). A sample S ∈ (X × Y)m is realizable by the list µ if y ∈ µ(x) for every (x, y) in S. A distribution D over X × Y is realizable by µ if for every m ∈ N, a random sample S ∼ Dm is realizable by µ with probability 1.

18

Algorithm 1 One-inclusion list algorithm AℓC,µℓ′ for a class C ⊆ Y X and list µℓ

′

′ Input: A sample S = (x1 , y1 ), · · · , (xm , ym ) realizable by H and µℓ . Output: A ℓ-list hypothesis AℓC,µℓ′ (S) = µℓS : X → {Y ⊆ Y : |Y | ≤ ℓ}. For each x ∈ X , the ℓ-list µℓS (x) is computed as follows. 1: Consider the class H ⊆ Y m+1 of all patterns over the unlabeled data that are realizable ′

′

′

by both C and µℓ i.e., H = {h ∈ C|(x1 ,...,xm ,x) : h(m + 1) ∈ µℓ (x) and h(i) ∈ µℓ (xi )}. 2: Find a ℓ-list orientation σ ℓ of G(H) that minimizes the maximum ℓ-outdegree. 3: Consider the edge in direction m + 1 defined by S: e = {h ∈ H : ∀i ∈ [m] h(i) = yi }. 4: Set µℓS (x) = {h(m + 1) : h ∈ σ ℓ (e)}.

Our proof adapts the conventional technique for bounding the leave-one-out error of a one-inclusion graph. The proof of this part can be divided into two steps: (1) In the first step, we upper bound the maximum ℓ-outdegree by ℓ-exponential dimension (see Lemma 3.20). Compared to Corollary 6.5 in [CP23], we save a factor of ℓ2 . (2) In the second step, using Theorem 2.1, we can further increase the bounding of the ℓ-exponential dimension by O(ℓdℓDS ), (see Corollary 3.21). Compared to Lemma 6.6 in [CP23], we save another factor of ℓ. Combining step 1 and step 2, and comparing with the analysis in Proposition 7.3 of [CP23], we improve the bound by a factor of ℓ3 in total. Then, we start our analysis of Algorithm 1, and start by bounding the maximum outdegree of the one-inclusion list algorithm. In previous papers [Hau95, RBR06, BCD+ 22, CP23], shifting is a major tool for bounding outdegree. For a beautiful introduction on the shifting operation, we refer the reader to the beginning of Section 3 in [BCD+ 22]. For completeness, we restate the definition and some major properties that we will use in our proof as follows. Definition 3.12 (Shifting [BCD+ 22]). Let H ⊆ [k]m and let i ∈ [m]. The shifting operator in the ith direction Si maps H to its shifted version Si (H) as follows. Shifting is first defined on edges. For f : [m] \ {i} → [k], let ef be the collection of h ∈ H that agree with f on [m] \ {i}. The shifting Si (ef ) is obtained by “pushing ef downward”; namely, Si (ef ) is the collection of all g ∈ [k]m that agree with f on [m] \ {i} and 1 ≤ g(i) ≤ |ef |. The shifting of H is the union of all shifted edges [ Si (H) = Si (ef ) ⊆ [k]m . f

Shifting has the useful property that the fixed point H∗ of the shifting operations (i.e., Si (H∗ ) = H∗ for all i ∈ [m]) is guaranteed to exist and is furthermore closed downward (i.e., if h ∈ H∗ ⊆ [k]m , and gi ≤ hi ∀i ∈ [m], then g ∈ H∗ ). We restate the following result from [CP23]: the shifting operation does not increase the ℓ-exponential dimension. This is an immediate corollary of Claim 22 in [BCD+ 22]. 19

Lemma 3.13 (Corollary 6.2, [CP23]). For every H ⊆ [k]m and i ∈ [m], dℓE (Si (H)) ≤ dℓE (H). Thus, dℓE (H∗ ) ≤ dℓE (H), where H∗ is the fixed point of the shifting operations i.e., Si (H∗ ) = H∗ for all i ∈ [m]. Next, we define the shifting average ℓ-degree. Definition 3.14 (Shifting average ℓ-degree [CP23]). Let G(H) = (V, E) be the one-inclusion graph of H ⊆ [k]m . The shifting average ℓ-degree of H is savdℓ (H) =

1 X (|e| − ℓ)+ , |V | e∈E

where (x)+ = max(x, 0). Let G(H) = (V, E) be the one-inclusion graph of H ⊆ [k]m . Given a subset of vertices U ⊆ V , we define the induced one-inclusion graph G(H)[U ] to be the hypergraph with vertex set U and edge set E ′ = {e ∩ E : e ∈ E, |e ∩ U | ≥ 1}. There is another equal definition of an induced one-inclusion graph defined by the subset H′ ⊆ H as G (H′ ). We now define the maximum density of G(H) using the second induced one-inclusion graph as follows. Definition 3.15 (Maximum ℓ-density of G(H)). Let G(H) = (V, E) be the one-inclusion graph of H ⊆ [k]m . The maximum ℓ-density of H is MDℓ (H) = max savdℓ (G (H′ )) . ′ H ⊆H

Subsequently, we restate the result from [CP23] that the shifting operation does not decrease the shifting average ℓ-degree savdℓ . Lemma 3.16 (Lemma 6.3, [CP23]). For every H ⊆ [k]m and i ∈ [m], savdℓ (Si (H)) ≥ savdℓ (H). Thus, savdℓ (H∗ ) ≥ savdℓ (H). To control the max ℓ-outdegree in the one-inclusion graph, after proving these results, [CP23] tends to prove an upper bound on the average degree of the one-inclusion graph G(H). Instead of that, we prove an upper bound on the shifting average degree savdℓ (H), which diverges from theirs and leads to a sharper (near optimal) upper bound. Now, we start to prove the upper bound of the shifting average ℓ-degree of G(H) by ℓ-exponential dimension. Lemma 3.17 (Shifting average ℓ-degree is bounded by ℓ-exponential dimension). For every H ∈ [k]m , we have savdℓ (H) ≤ dℓE (H).

20

Proof of Lemma 3.17. According to Lemma 3.13, we have that dℓE (H∗ ) ≤ dℓE (H). According to Lemma 3.16, we have that savdℓ (H∗ ) ≥ savdℓ (H). We only need to prove savdℓ (H∗ ) ≤ dℓE (H∗ ). We prove this by induction on the size of H∗ . For the base case, when |H∗ | = 1, we have savdℓ (H∗ ) = dℓE (H∗ ) = 0, and so the inequality holds. The induction step is justified as follows. Let h0 be the concept in H∗ so that no concept in H∗ is larger than h0 with respect to the natural partial order. Let |h0 | be the number of coordinates of h0 that are larger than ℓ. Because H∗ is closed downwards by the definition of shifting, all concepts h ≤ h0 are contained in H∗ , which implies that degℓ (h0 ) = |h0 |. This also implies that H∗ restrict to those |h0 | coordinates has size at least (ℓ + 1)|h0 | . Combining together, we have degℓ (h0 ) = |h0 | ≤ dℓE (H∗ ). Now, consider the class H∗′ = H∗ \ {h0 }, which is also closed downwards, and the inductive hypothesis implies that savdℓ (H∗′ ) ≤ dℓE (H∗′ ) ≤ dℓE (H∗ ). Now consider those edges in H∗ that contain h0 according to their sizes. For simplicity, we denote e′ ∈ G (H∗′ ) as the corresponding edge e ∈ G (H∗ ). 1.If such e’s size is less than or equal to ℓ, then the value (|e| − ℓ)+ = 0 in G (H∗ ), for the corresponding edge e′ , whose value (|e′ | − ℓ)+ = 0 also holds. 2. If e’s size is greater than ℓ, then the number of such edges is degℓ (h0 ). The value of those edges satisfies (|e′ | − ℓ)+ = (|e| − ℓ)+ − 1. Now, we have  X 1 X savd (H∗ ) = (|e| − ℓ)+ + (|e| − ℓ) m e∈E,h0 ∈e / e∈E,h0 ∈e,|e|>ℓ  1X ′ (|e | − ℓ)+ + degℓ (h0 ) = m e′ ∈E ′  1 = (n − 1)savdℓ (H∗′ ) + degℓ (h0 ) m  1 (n − 1)dℓE (H∗′ ) + dℓE (H∗ ) ≤ m ≤ dℓE (H∗ ). ℓ

This immediately leads to the following corollary. Corollary 3.18 (ℓ-exponential dimension bound maximum L-density of G(H)). For every H ⊆ [k]m with Eℓ (H) = dℓE (H), and every class H′ ⊂ H, we have savdℓ (H′ ) ≤ dℓE (H). This implies that MDℓ (H) ≤ dℓE (H). Proof of Corollary 3.18. According to Lemma 3.17, we have savdℓ (H′ ) ≤ dℓE (H′ ). We also have the naive inequality dℓE (H′ ) ≤ dℓE (H). Combining the two inequalities above, we obtain our final result. From here, we follow the proof technique of [HLW94], orienting the one-inclusion graph via constructing an integer flow network, and extend their result in binary classification to the multiclass setting. For H ⊆ [k]m and one-inclusion graph G(H) = (V, E), we construct an integer flow network I(H) (as shown in Figure 2) with a source s, a sink t, and two 21

intermediate node layers derived from the one-inclusion graph G(H). The first layer contains a node ei for each hyperedge ei in G(H), while the second layer contains a node vj for each vertex vj . The network’s directed edges and their respective capacities are defined as follows: 1. An edge connects the source s to each first-layer node ei with a capacity of (|ei | − ℓ)+ . 2. For each hyperedge ei , an edge with capacity 1 connects its corresponding node ei to each second-layer node vj for which the vertex vj ∈ ei .   3. An edge connects each second-layer node vj to the sink t with a capacity of MDℓ (H) .

e1 (|e

s

|− 1

v1

 M

ℓ) +

e2

1

v2

Dℓ (H  )

t

(|e

m|

1

−

ℓ)

 ) ℓ (H D

...

...  M

+

em

1

vn

Figure 2: integer flow network I(H)

We first show that for the above network I(H), there is an integer flow to achieve the maximum flow. Lemma 3.19. For the network I(H), there is an integer flow achieving the maximum flow, Pm ℓ i=1 (|ei | − ℓ)+ = |V | · savd (H). Proof of Lemma 3.19. The proof relies on the Max-Flow Min-Cut Theorem. First, we will P establish that the maximum flow value is precisely m (|e i | − ℓ)+ . Then, the existence of an i=1 integer-valued flow achieving this maximum follows directly from the Integrality Theorem of [FF56], as all capacities in the network are integers. The total capacity of the edges leaving P the source s is m (|e | i − ℓ)+ . By definition, the maximum flow cannot exceed this value. i=1 We will now show that the capacity of any s − t cut is at least this value, thereby proving the equality. Consider an arbitrary s − t cut (S, T ), where s ∈ S and t ∈ T . The capacity of the cut, C(S, T ), is the sum of capacities of all edges (u, v) with u ∈ S and v ∈ T . Let’s partition the nodes as ES , ET , VS , VT , where • ES = {ei | ei ∈ S} and ET = {ei | ei ∈ T } • VS = {vj | vj ∈ S} and VT = {vj | vj ∈ T }

22

The cut capacity is the sum of three components: X X X C(S, T ) = cap(s, ei ) + cap(vj , t) + cap(ei , vj ) | {z } | {z } | {z } e ∈E v ∈V e ∈E , i

T

Type 1

j

S

Type 2

i

S

vj ∈ei ∩VT

Type 3

Substituting the capacities gives: X   X C(S, T ) = (|ei | − ℓ)+ + |VS | · MDℓ (H) + |ei ∩ VT | ei ∈ET

ei ∈ES

P Our goal is to show that C(S, T ) ≥ m i=1 (|ei | − ℓ)+ . Since the sum over ET is already part of the target, we only need to prove: X   X |VS | · MDℓ (H) + |ei ∩ VT | ≥ (|ei | − ℓ)+ ei ∈ES

ei ∈ES

Rearranging the terms, this is equivalent to showing: X   |VS | · MDℓ (H) ≥ ((|ei | − ℓ)+ − |ei ∩ VT |) ei ∈ES

We can bound the term in the parentheses using the fact that for any ei ∈ ES , |ei | = |ei ∩ VS | + |ei ∩ VT |. This gives the key inequality: (|ei | − ℓ)+ − |ei ∩ VT | ≤ (|ei ∩ VS | − ℓ)+ Applying this inequality, it is sufficient to prove the following:   1 X |VS | · MDℓ (H) ≥ |VS | · (|ei ∩ VS | − ℓ)+ |VS | e ∈E i

S

  This inequality holds by the definition of MDℓ (H) in Definition 3.15, which is the maximum shifting average ℓ-degree on any subgraph of the original one inclusion graph G(H), and must be greater or equal to the shifting P average ℓ-degree on the subgraph induced by VS . Since the capacity of any cut is at least m i=1 (|ei | − ℓ)+ , the minimum cut capacity must also be at least this value. By the Max-Flow Min-Cut Theorem, the maximum flow is equal to the minimum cut capacity, which concludes the proof. Next, we show that we can orient the one-inclusion graph G(H) leveraging the integer flow in I(H), such that the maximum ℓ-outdegree can be upper bounded by the ℓ-exponential dimension dℓE (H). Lemma 3.20 (ℓ-Exponential Dimension Leads to List Orientation). For every H ∈ [k]m , there is a ℓ-list orientation σ ℓ of G(H) with maximum ℓ-outdegree at most MDℓ (H) ≤ dℓE (H). Proof of Lemma 3.20. We construct the orientation σ ℓ using the integer-valued maximum flow, f , guaranteed by the proof of Lemma 3.19. Recall that in the flow network IH (x̄), 23

edges from hyperedge nodes {ei } to vertex nodes {vj } have a capacity of 1, meaning the flow f (ei , vj ) across any such edge is either 0 or 1. We define the orientation σ ℓ of the one-inclusion graph G(H) based on this flow. For each hyperedge e, we orient it to the vertices {v ′ } such that f (e, v ′ ) = 0 in the flow f . Now, we show that this orientation respects the claimed outdegree bound. By our rule, an edge is directed away from vj (to some ei ) only if the flow f (ei , vj ) is 1. Therefore, the ℓ-outdegree of any vertex vj is the sum of flows on all incident edges from the hyperedge layer: X outdegℓ (vj ) = f (ei , vj ) ei ∋vj

By the principle of flow conservation at node vj in the network I(H), the total flow entering vj from the hyperedge nodes must equal the total flow leaving vj to the sink t, we have X f (ei , vj ) = f (vj , t) ei ∋vj

Finally, any flow by the capacity of the edge it traverses. The capacity of the  isℓ bounded  edge (vj , t) is MD (H) . Thus, we have:   f (vj , t) ≤ cap(vj , t) = MDℓ (H) Combining these steps and Corollary 3.18, we get the upper bound on the outdegree of any  vertex vj as MDℓ (H) ≤ dℓE (H). Subsequently, we will show how to upper bound the ℓ-exponential dimension by the ℓ-DS dimension. Corollary 3.21 (Controlling the ℓ-exponential dimension by ℓ-DS dimension). For every H ⊆ [k]m with DSℓ (H) = dℓDS and Eℓ (H) = dℓE < ∞, we have5 dℓE ≤ 40ℓdℓDS log k. Proof of Corollary 3.21. Consider the set S which realizes dℓE , so that |S| = dℓE . Then we have that ℓ |H|S | ≥ (ℓ + 1)dE . Also, from Theorem 2.1, we have dℓE



|H|S | ≤ ℓ 5

ekdℓE dℓDS

dℓDS .

In this paper, log(·) denotes the natural logarithm, and we define log(x) := max{log(x), 1}.

24

Combining the above two inequalities, we obtain (ℓ + 1)

dℓE

dℓE



≤ℓ

ekdℓE dℓDS

dℓDS .

By rearranging the term, we have 

ℓ+1 ℓ

dℓE

 ≤

ekdℓE dℓDS

dℓDS .

Taking the logarithm of both sides and rearranging the terms, we get  ℓ ekd log dℓ E dℓE DS
. ≤ ℓ dDS log 1 + 1ℓ Using the basic inequality log(1 + 1ℓ ) > 2ℓ1 when ℓ > 1, we have dℓE ≤ 2ℓ log (ek) + 2ℓ log dℓDS



dℓE dℓDS

 .

Leveraging Lemma A.2. in [SSBD14], we have dℓE ≤ 4ℓ log (ek) + 8ℓ log (4ℓ) . dℓDS Thus, we have: dℓE ≤ (4ℓ log (ek) + 8ℓ log (4ℓ)) dℓDS ≤ ℓdℓDS (8 log k + 16 log 2 + 4) ≤ 40ℓdℓDS log k.

Armed with Lemma 3.20 and Corollary 3.21, we are ready to bound the leave-one-out error of Algorithm 1. ′

Lemma 3.22. Let C ⊆ Y X be a concept class with DSℓ (C) = dℓDS < ∞ and let µℓ be a ℓ′ -list ′ (where ℓ′ ≫ ℓ). For every distribution D over X × Y that is realizable by both C and by µℓ , and for all integers m > 0,   40ℓdℓDS log(ℓ′ ) Pr(S,(x,y))∼Dm+1 y ̸∈ µℓS (x) ≤ , m where µkS = AℓC,µℓ′ (S). ′

Proof. Let D be a distribution that is realizable by C and µℓ . By the leave-one-out sym25

metrization argument, h i   ℓ ′ ℓ ′ Pr(S,(x,y))∼Dm+1 y ̸∈ µS (x) = Pr(S ′ ,i)∼Dm+1 ×Unif(m+1) yi ̸∈ µS−i ′ (xi ) , where µkS = AℓC,µℓ′ (S). It therefore suffices to show that for every sample S ′ that is realizable ′ by C and µℓ , h i 40ℓdℓ log(ℓ′ ) DS ′ . Pri∼Unif(m+1) yi′ ̸∈ µℓS−i ′ (xi ) ≤ m ′

Fix S ′ which is realizable by C and µℓ for the rest of the proof. The class H = C|(x′1 ,··· ,x′m+1 ) ′ constructed by the algorithm AℓC,µℓ′ for S−i and x′i is the same for all values of i, and is ′ realizable by µℓ . The ℓ-DS dimension of H is at most that of C. Denote by σ ℓ the orientation of G(H) that the algorithm chooses. Lemma 3.20 tells us that the maximum ℓ-outdegree of σ ℓ is at most dℓE , which can be further upper bounded by 40ℓdℓDS log(ℓ′ ) leveraging Corollary 3.21. ′ Let y ′ denote the vertex in G(H) defined by y ′ = (y1′ , · · · , ym+1 ), and let ei denote the edge th ′ in the i direction adjacent to y . Then, we have: Pri∼Unif(m+1)

h

i

′ yi′ ̸∈ µℓS−i ′ (xi )

m+1 i 1 X h ′ ′ = 1 yi ̸∈ µℓS−i ′ (xi ) m + 1 i=1 m+1  1 X  ′ 1 y ̸∈ σ ℓ (ei ) = m + 1 i=1

outdegℓ (y ′ ; σ ℓ ) m+1 40ℓdℓDS log(ℓ′ ) ≤ . m+1 =

The rest of the proof adapts the two-stage framework of [CP23, BCD+ 22]. The stages are as follows: (1) We learn a ℓ′ -list hypothesis with list size ℓ′ ≫ ℓ. (2) We then use this ℓ′ -list hypothesis to filter for realizable samples, re-apply the one-inclusion algorithm, and use the confidence amplification technique of [HLW94] to distill the final ℓ-list. For the first stage, we restate the results from [CP23] without proof. For a detailed algorithm and proof, one can refer to [CP23]. Lemma 3.23 (Learn a ℓ′ -list hypothesis [CP23]). Let C ⊆ Y X be a concept class with DSℓ (C) = dℓDS < ∞. Then for every distribution D on (X × Y) realizable ϵ, δ ∈ (0, 1),  ℓ by1.5C, every  (dDS ) log((dℓDS )1.5 /ϵ)2 +log(1/δ) with probability at least 1 − δ over a sample of S of size m = O ϵ ′

′ ℓ drawn i.i.d from √ ℓ D, we can learn a ℓ -list hypothesis µ with error rate at most ϵ, where ℓ′ ≤ ℓ(edℓDS ) dDS log(2m).

In the second step of our proof, we show that any concept class C with a finite ℓ-DS ′ dimension is learnable given realizability with respect to a large list µℓ (where ℓ′ ≫ ℓ). Our procedure, formalized in Algorithm 2, utilizes a confidence amplification technique from 26

[HLW94]. This analysis, which we detail here, is the source of our improvement, saving another factor of ℓ2 compared to the analysis in Lemma 7.5 of [CP23]. Our algorithm operates in two stages, mirroring the classic "generate-and-select" amplification strategy. First, we construct a set of candidate hypotheses G. This is done by running Algorithm 1 for ⌈log(2/δ)⌉ times. Each i-th run hi = AℓC,µℓ′ (Si ) is trained on an independent sample Si ′ with size O(ℓdℓDS log(ℓ′ )/ϵ) realizable by C and µℓ of size O(ℓdℓDS log(ℓ′ )/ϵ), and the resulting hypothesis hi is added to G. Second, we perform an ERM-based selection. We draw a new, independent validation sample Sval of size O(log(1/δ)/ϵ). The final output A(S) is the hypothesis in G that achieves the lowest empirical error on Sval . ′

Algorithm 2 List PAC learner for a class C ⊆ Y X and list µℓ

′ Input: A sample S = (x1 , y1 ), · · · , (xm , ym ) realizable by C and µℓ . Output: A ℓ-list hypothesis AℓPAC (S) = µℓS : X → {Y ⊆ Y : |Y | ≤ ℓ}. 1: Initialize G = ∅. Partition S into {S1 , S2 , · · · S⌈log(2/δ)⌉ , Sval }. 2: for i = 1, 2, · · · , ⌈log(2/δ)⌉ do 3: Run Algorithm 1 with input sample Si and get the list predictor µℓSi . 4: Update G = G ∪ {µℓSi } 5: end for 6: Output the hypothesis in G with lowest empirical error on test set Sval .

The following lemma shows that Algorithm 2 is a ℓ-list PAC learner given a sample ′ realizable by H and a list µℓ with ℓ′ ≫ ℓ. ′

Lemma 3.24. Let C ⊆ Y X be a concept class with DSℓ (C) = dℓDS < ∞ and let µℓ be a ℓ′ -list. ′ Then for every distribution D on (X × Y) realizable by Cand µℓ , every  ϵ, δ ∈ (0, 1), with ℓdℓDS log(ℓ′ /δ) probability at least 1 − δ over a sample of S of size m = O drawn i.i.d from D, ϵ the ℓ-list hypothesis µℓ = AℓPAC (S) output by Algorithm 2 satisfies   Pr(x,y)∼D y ̸∈ µℓ (x) ≤ ϵ. Proof. Let p = ⌈log(2/δ)⌉. The algorithm partitions S into {Si }pi=1 and Sval , with |Si | = 160ℓdℓDS log(ℓ′ ) n= and |Sval | = mval = 32 log(2/δ) + log(p + 1). The proof proceeds in two stages, ϵ ϵ with a final union bound. In the first stage of generation of the candidate hypothesis in G, according to Lemma 3.22, the expected error rate for each µℓSi is at most ϵ/4. Thus, by Markov inequality, each hypothesis µℓSi in G has error larger than ϵ/2 with probability smaller than 1/2. Since a different sample is used for each hypothesis µℓSi in G. It follows that G has a hypothesis µℓ of error at most ϵ/2 with probability at least 1 − δ/2. In the ERM selection step, according to lemma 5.1. in [HLW94], if G has a hypothesis of error at most ϵ/2 then the ERM step in Algorithm 2 executed with a sample Sval described above, outputs with probability at least 1 − δ/2 a hypothesis in G with error at most ϵ. Subsequently, armed with Lemma 3.23 and Lemma 3.24, we are now ready to prove Theorem 3.2. 27

Proof of Theorem 3.2. The proof is a three-stage argument. We construct the final ℓ-list learner by first learning an intermediate ℓ′ -list, then using it to filter a new sample set to be "realizable," and finally learning our target ℓ-list from this filtered set. We use a union bound over the failure probability of each stage. First, by Lemma 3.23, we draw an i.i.d. sample S1 of size   ℓ 1.5 (dDS ) log((dℓDS )1.5 /ϵ)2 + log(1/δ) . m1 = O ϵ ′

′

ℓ This yields an ℓ′ -list hypothesis µℓ with an error rate err(µ√ ) ≤ ϵ with probability at least ℓ ′ ′ ℓ 1 − δ/4. The resulting list size ℓ is bounded by ℓ ≤ ℓ(edDS ) dDS log(2m1 ). Second, we draw a new, independent sample S2 of size    ℓ 1 ℓdDS log(ℓ′ /δ) + log . m2 = O ϵ δ ′

We filter this sample to keep only points realizable by µℓ , creating the set Sreal = {(x, y) ∈ ′ S2 | y ∈ µℓ (x)}. A standard Chernoff bound shows that with probability at least 1 − δ/4, this realizable sub-sample Sreal has a size of at least  ℓ  ℓdDS log(ℓ′ /δ) ′ m2 = O . ϵ We assume the data distribution D is realizable by H, so Sreal is also realizable by H. Third, we use this realizable sample Sreal (of size m′2 ) as input to Algorithm 2. By Lemma 3.24, this algorithm outputs a final ℓ-list hypothesis µℓ with err(µℓ ) ≤ ϵ with probability at least 1 − δ/4. By a union bound over these three stages, the total failure probability is at most δ/4 + δ/4 + δ/4 = 3δ/4 ≤ δ. The total sample complexity is m = m1 + m2 . We substitute the bound for ℓ′ from Stage 1 into the log(ℓ′ ) term of m2 . This gives the total sample size:    ℓ 1.5 (dDS ) log((dℓDS )1.5 /ϵ)2 + ℓdℓDS log(1/δ) 1 ℓ 1 + ℓdDS log m=O ϵ ϵ δ  ℓ 1.5   √ 1.5 2 ℓ 1 ℓ (dDS ) log((dDS ) /ϵ) + log(1/δ) ℓ dℓDS ℓd log (edDS ) log . ϵ DS ϵ Omitting the polylogarithmic in dℓDS and 1/ϵ, we have the dominant term in the complexity is  ℓ 1.5  ℓ ℓ ′ (d ) ℓd · log(1/δ) ℓd · log(ℓ ) DS DS DS e O + + ϵ ϵ ϵ ! p ℓ ℓ 1.5 ℓ ℓ ℓd · d (d ) ℓd · log(1/δ) DS DS DS DS e =O + + ϵ ϵ ϵ  ℓ 1.5  ℓ e ℓ(dDS ) + ℓdDS log(1/δ) . =O ϵ  ℓ 1.5 ℓ  e ℓ(dDS ) +ℓdDS log(1/δ) . Thus, the overall sample complexity is O ϵ 28

3.4.2

Proof of Theorem 3.4

Proof of Theorem 3.4. Let d = DSℓ (C) and g = Gℓ (C). Let S ∈ X g be a sample of size g that is ℓ-graph shattered by C. Define H = H(C|S ) = {h ∈ Y g : ∃c ∈ C, h ≺ c|S } as the class of all possible patterns induced by C on the sample S. We first restate the following lemma from [HMT24] that lower bounds the cardinality of H.
Y X Lemma 3.25 ([HMT24]). Given an ℓ-list class C ⊆ ≤ℓ that ℓ-graph shatters S ∈ X n , n we let p ∈ Y be a pivot and let {cb }b∈{0,1}n ⊆ C|S be witnesses for the shattering such that pi ∈ cb (xi ) if and only if bi = 1. Denote by Ab = {y ∈ Y n : ∀i yi ∈ cb (xi )}, the set of functions realizable by cb . Then we have |∪

b∈{0,1}n

(2ℓ)n Ab | ≥ ℓn . n 4(2ℓ − 1)

Observe that ∪b∈{0,1}g Ab ⊆ H, since every function in Ab is realized by some projection of C on S. Combining with |S| = g, Lemma 3.25 yields |H| ≥ | ∪b∈{0,1}g Ab | ≥

(2ℓ)g ℓg . g 4(2ℓ − 1)

We next upper bound the cardinality of H using our optimal Sauer lemma. According to Theorem 2.1, we have |H| ≤ ℓg (gk)DSℓ (H) . We also note that DSℓ (C) ≥ DSℓ (H), since any sample that is ℓ-DS-shattered by H is also ℓ-DS-shattered by C. Thus, we have the upper bound |H| ≤ ℓg (gk)d . Combining the lower and upper bounds on H, we have ℓg (gk)d ≥

(2ℓ)g ℓg . 4(2ℓ − 1)g

Taking logarithms on both sides of the inequality, we obtain   1 d(log g + log k) ≥ g log 1 + − 2 log 2. 2ℓ − 1 Leveraging the basic inequality log(1 + x) ≥ x2 ∀ x ∈ [0, 1], we have d≥

g 2 log 2 − , 4ℓ(log g + log k) log g + log k

which yields

 d=Ω

g ℓ(log g + log k)

29

 .

(2)

For the sample complexity of uniform convergence, we first restate the following result from [VC74, DSBDSS11], which characterizes the sample complexity of uniform convergence via the ℓ-graph dimension. Lemma 3.26 (Characterization of uniform convergence [VC74, DSBDSS11]). A ℓ-list hypothesis class C satisfies uniform convergence if and only if Gℓ (C) the   < ∞. Furthermore, G (C)+log(1/δ) ℓ . sample complexity of uniform convergence of C is mUC C (ε, δ) = Θ ε2 Combining Lemma 3.26 with Equation (2), we obtain the desired upper bound on the sample complexity of uniform convergence:   ℓd log(ℓdk) + log(1/δ) UC , mC (ε, δ) = O ε2 which completes the proof.

Acknowledgments Steve Hanneke acknowledges support by grant no. 2024243 from the United States - Israel Binational Science Foundation (BSF). Shay Moran is a Robert J. Shillman Fellow; he acknowledges support by Israel PBC-VATAT, by the Technion Center for Machine Learning and Intelligent Systems (MLIS), and by the European Union (ERC, GENERALIZATION, 101039692). Views and opinions expressed are, however, those of the author(s) only and do not necessarily reflect those of the European Union or the European Research Council Executive Agency. Neither the European Union nor the granting authority can be held responsible for them.

30

References [AB21] Anastasios N Angelopoulos and Stephen Bates. A gentle introduction to conformal prediction and distribution-free uncertainty quantification. arXiv preprint arXiv:2107.07511, 2021. [Alo83] Noga Alon. On the density of sets of vectors. Discrete Mathematics, 46(2):199– 202, 1983. [AMY17] Noga Alon, Shay Moran, and Amir Yehudayoff. Sign rank versus VapnikChervonenkis dimension. Sbornik: Mathematics, 208(12):1724, 2017. [BCD+ 22] Nataly Brukhim, Daniel Carmon, Irit Dinur, Shay Moran, and Amir Yehudayoff. A characterization of multiclass learnability. In 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS), pages 943–955. IEEE, 2022. [BCDK06] Hans-Jürgen Bandelt, Victor Chepoi, Andreas W. M. Dress, and Jack H. Koolen. Combinatorics of lopsided sets. Eur. J. Comb., 27(5):669–689, 2006. [BDMM24] Nataly Brukhim, Amit Daniely, Yishay Mansour, and Shay Moran. Multiclass boosting: simple and intuitive weak learning criteria. Advances in Neural Information Processing Systems, 36, 2024. [BF20] László Babai and Péter Frankl. Linear algebra methods in combinatorics. to appear, 2020. [BHM23] Nataly Brukhim, Steve Hanneke, and Shay Moran. Improper multiclass boosting. In Gergely Neu and Lorenzo Rosasco, editors, The Thirty Sixth Annual Conference on Learning Theory, COLT 2023, 12-15 July 2023, Bangalore, India, volume 195 of Proceedings of Machine Learning Research, pages 5433–5452. PMLR, 2023. [BLR89] Béla Bollobás, Imre Leader, and Andrew J. Radcliffe. Reverse Kleitman Inequalities. Proceedings of the London Mathematical Society, s3-58(1):153–168, 01 1989. [BR95] Béla Bollobás and Andrew J. Radcliffe. Defect Sauer results. Journal of Combinatorial Theory, Series A, 72(2):189–208, 1995. [Buk15] Boris Bukh. Random algebraic construction of extremal graphs. Bulletin of the London Mathematical Society, 47(6):939–945, 2015. [CCH+ 24] Zachary Chase, Bogdan Chornomaz, Steve Hanneke, Shay Moran, and Amir Yehudayoff. Dual VC dimension obstructs sample compression by embeddings. In Shipra Agrawal and Aaron Roth, editors, The Thirty Seventh Annual Conference on Learning Theory, June 30 - July 3, 2023, Edmonton, Canada, volume 247 of Proceedings of Machine Learning Research, pages 923–946. PMLR, 2024. 31

[CCMW22] Jérémie Chalopin, Victor Chepoi, Shay Moran, and Manfred K. Warmuth. Unlabeled sample compression schemes and corner peelings for ample and maximum classes. J. Comput. Syst. Sci., 127:1–28, 2022. [CEH+ 26] Alon Cohen, Liad Erez, Steve Hanneke, Tomer Koren, Yishay Mansour, Shay Moran, and Qian Zhang. Sample complexity of agnostic multiclass classification: Natarajan dimension strikes back. In Proceedings of the 58th Annual ACM Symposium on Theory of Computing (STOC 2026), 2026. To appear. [CKP21] Victor Chepoi, Kolja Knauer, and Manon Philibert. Labeled sample compression schemes for complexes of oriented matroids. CoRR, abs/2110.15168, 2021. [CKP22] Victor Chepoi, Kolja Knauer, and Manon Philibert. Ample completions of oriented matroids and complexes of uniform oriented matroids. SIAM Journal of Discrete Mathematics, 36(1):509–535, 2022. [CP23] Moses Charikar and Chirag Pabbaraju. A characterization of list learnability. In Proceedings of the 55th Annual ACM Symposium on Theory of Computing, pages 1713–1726, 2023. [CPT25] Moses Charikar, Chirag Pabbaraju, and Ambuj Tewari. A characterization of list language identification in the limit. CoRR, abs/2511.04103, 2025. [DK23] Ilias Diakonikolas and Daniel M Kane. Algorithmic high-dimensional robust statistics. Cambridge university press, 2023. [Dre96] Andreas W. M. Dress. Towards a theory of holistic clustering. In Boris G. Mirkin, Fred R. McMorris, Fred S. Roberts, and Andrey Rzhetsky, editors, Mathematical Hierarchies and Biology, Proceedings of a DIMACS Workshop, November 13-15, 1996, volume 37 of DIMACS Series in Discrete Mathematics and Theoretical Computer Science, pages 271–290. DIMACS/AMS, 1996. [DSBDSS11] Amit Daniely, Sivan Sabato, Shai Ben-David, and Shai Shalev-Shwartz. Multiclass learnability and the erm principle. In Proceedings of the 24th Annual Conference on Learning Theory, pages 207–232. JMLR Workshop and Conference Proceedings, 2011. [DSS14] Amit Daniely and Shai Shalev-Shwartz. Optimal learners for multiclass problems. In Conference on Learning Theory, pages 287–316. PMLR, 2014. [DSS15] Amit Daniely, Michael Schapira, and Gal Shahaf. Inapproximability of truthful mechanisms via generalizations of the vc dimension. In Proceedings of the forty-seventh annual ACM symposium on Theory of Computing, pages 401–408, 2015. [DSS18] Amit Daniely, Michael Schapira, and Gal Shahaf. Inapproximability of truthful mechanisms via generalizations of the vapnik-chervonenkis dimension. SIAM J. Comput., 47(1):96–120, 2018. 32

[EK25] Liad Erez and Tomer Koren. From contextual combinatorial semi-bandits to bandit list classification: Improved sample complexity with sparse rewards. In The Thirty-ninth Annual Conference on Neural Information Processing Systems, 2025. [FF56] L. R. Ford and D. R. Fulkerson. Maximal flow through a network. Canadian Journal of Mathematics, 8:399–404, 1956. [FM01] Paul Fischer and Jiri Matousek. A lower bound for families of Natarajan dimension d. Journal of Combinatorial Theory, Series A, 95(1):189–195, 2001. [FP83] Péter Frankl and János Pach. On the number of sets in a null t-design. European Journal of Combinatorics, 4(1):21–23, 1983. [FS12] Zoltán Füredi and Attila Sali. Optimal multivalued shattering. SIAM Journal on Discrete Mathematics, 26(2):737–744, 2012. [FW95] Sally Floyd and Manfred Warmuth. Sample compression, learnability, and the Vapnik-Chervonenkis dimension. Machine Learning, 21(3):269–304, 1995. [GMRT23] Guorong Gao, Jie Ma, Mingyuan Rong, and Tuan Tran. Complexity of null dynamical systems and sauer–shelah lemmas. arXiv preprint arXiv:2310.05353, 2023. [GW94] Bernd Gärtner and Emo Welzl. Vapnik-Chervonenkis dimension and (pseudo-) hyperplane arrangements. Discrete Comput. Geom., 12(4):399–432, 1994. [Han16] Steve Hanneke. The optimal sample complexity of PAC learning. J. Mach. Learn. Res., 17:38:1–38:15, 2016. [Hau95] David Haussler. Sphere packing numbers for subsets of the boolean n-cube with bounded vapnik-chervonenkis dimension. Journal of Combinatorial Theory, Series A, 69(2):217–232, 1995. [HL95] David Haussler and Philip M. Long. A generalization of sauer’s lemma. Journal of Combinatorial Theory, Series A, 71(2):219–240, 1995. [HLW94] David Haussler, Nick Littlestone, and Manfred K Warmuth. Predicting {0, 1}functions on randomly drawn points. Information and Computation, 115(2):248– 292, 1994. [HMS25] Steve Hanneke, Qinglin Meng, and Amirreza Shaeiri. Representation preserving multiclass agnostic to realizable reduction. In Forty-second International Conference on Machine Learning, 2025. [HMST25] Steve Hanneke, Shay Moran, Hilla Schefler, and Iska Tsubari. Private list learnability vs. online list learnability. arXiv preprint arXiv:2506.12856, 2025.

33

[HMT24] Steve Hanneke, Shay Moran, and Waknine Tom. List sample compression and uniform convergence. In The Thirty Seventh Annual Conference on Learning Theory, pages 2360–2388. PMLR, 2024. [HMZ24] Steve Hanneke, Shay Moran, and Qian Zhang. Improved sample complexity for multiclass PAC learning. Advances in Neural Information Processing Systems, 37:42798–42839, 2024. [HR10] Gábor Hegedüs and Lajos Rónyai. Multivalued generalizations of the frankl– pach theorem. arXiv preprint arXiv:1008.4660, 2010. [HS25] Steve Hanneke and Amirreza Shaeiri. A trichotomy for list transductive online learning. In Forty-second International Conference on Machine Learning, 2025. [KM78] M. G. Karpovsky and V. D. Milman. Coordinate density of sets of vectors. Discrete Mathematics, 24(2):177–184, 1978. [KST54] Tamás Kóvári, Vera T Sós, and Pál Turán. On a problem of K. Zarankiewicz. Colloquium Mathematicae, 3(1):50–57, 1954. [KW07] Dima Kuzmin and Manfred K. Warmuth. Unlabeled compression schemes for maximum classes. Journal of Machine Learning Research, 8:2047–2081, 2007. [Law83] James F. Lawrence. Lopsided sets and orthant-intersection of convex sets. Pacific J. Math., 104:155–173, 1983. [LHS15] Maksim Lapin, Matthias Hein, and Bernt Schiele. Loss functions for top-k error: Analysis and insights. 2016 IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pages 1468–1477, 2015. [Mor12] Shay Moran. Shattering-extremal systems. arXiv preprint, 1211.2980, 2012. [MR16] Shay Moran and Cyrus Rashtchian. Shattered sets and the hilbert function. In MFCS 2016: 41st International Symposium on Mathematical Foundations of Computer Science, volume 58 of LIPIcs, pages 70:1–70:14. Schloss Dagstuhl– Leibniz-Zentrum für Informatik, 2016. [MSTY23] Shay Moran, Ohad Sharon, Iska Tsubari, and Sivan Yosebashvili. List online classification. In The Thirty Sixth Annual Conference on Learning Theory, pages 1885–1913. PMLR, 2023. [MW16] Shay Moran and Manfred Warmuth. Labeled compression schemes for extremal classes. In Proceedings of the 27th International Conference on Algorithmic Learning Theory, pages 34–49. Springer, 2016. [Nat89] Balas K Natarajan. On learning sets and functions. Machine Learning, 4(1):67– 97, 1989.

34

[PS25] Chirag Pabbaraju and Sahasrajit Sarmasarkar. A characterization of list regression. In Gautam Kamath and Po-Ling Loh, editors, International Conference on Algorithmic Learning Theory, 24-27 February 2025, Politecnico di Milano, Milan, Italy, volume 272 of Proceedings of Machine Learning Research, pages 870–920. PMLR, 2025. [RBR06] Benjamin Rubinstein, Peter Bartlett, and J Rubinstein. Shifting, one-inclusion mistake bounds and tight multiclass expected risk bounds. Advances in Neural Information Processing Systems, 19, 2006. [RBR09] Benjamin I. P. Rubinstein, Peter L. Bartlett, and J. Hyam Rubinstein. Shifting: One-inclusion mistake bounds and sample compression. J. Comput. Syst. Sci., 75(1):37–59, 2009. [RR12] Benjamin I. P. Rubinstein and J. Hyam Rubinstein. A geometric approach to sample compression. Journal of Machine Learning Research, 13:1221–1261, 2012. [RRB15] J. Hyam Rubinstein, Benjamin I. P. Rubinstein, and Peter L Bartlett. Bounding embeddings of VC classes into maximum classes. Measures of Complexity: Festschrift for Alexey Chervonenkis, pages 303–325, 2015. [Sau72] Norbert Sauer. On the density of families of sets. Journal of Combinatorial Theory, Series A, 13:145–147, 1972. [She72] Saharon Shelah. A combinatorial problem; stability and order for models and theories in infinitary languages. Pacific Journal of Mathematics, 41(1):247–261, 1972. [Smo97] Roman Smolensky. Well-known bound for the vc-dimension made easy. Computational Complexity, 6(4):299–300, 1997. [SSBD14] Shai Shalev-Shwartz and Shai Ben-David. Understanding machine learning: From theory to algorithms. Cambridge university press, 2014. [SSSSS10] Shai Shalev-Shwartz, Ohad Shamir, Nathan Srebro, and Karthik Sridharan. Learnability, stability and uniform convergence. Journal of Machine Learning Research, 11(90):2635–2670, 2010. [SSYZ14] Rahim Samei, Pavel Semukhin, Boting Yang, and Sandra Zilles. Algebraic methods proving sauer’s bound for teaching complexity. Theor. Comput. Sci., 558:35–50, 2014. [Ste78] J. Michael Steele. Existence of submatrices with all possible columns. Journal of Combinatorial Theory, Series A, 24(1):84–88, 1978. [SV08] Glenn Shafer and Vladimir Vovk. A tutorial on conformal prediction. Journal of Machine Learning Research, 9(3), 2008. 35

[SYZ14] Rahim Samei, Boting Yang, and Sandra Zilles. Generalizing labeled and unlabeled sample compression to multi-label concept classes. In Peter Auer, Alexander Clark, Thomas Zeugmann, and Sandra Zilles, editors, Algorithmic Learning Theory - 25th International Conference, ALT 2014, Bled, Slovenia, October 8-10, 2014. Proceedings, volume 8776 of Lecture Notes in Computer Science, pages 275–290. Springer, 2014. [VC71] V. N. Vapnik and A. Ya. Chervonenkis. On the uniform convergence of relative frequencies of events to their probabilities. Theory of Probability and Its Applications, 16(2):264–280, 1971. [VC74] Vladimir Vapnik and Alexey Chervonenkis. Theory of pattern recognition, 1974. [VGS05] Vladimir Vovk, Alexander Gammerman, and Glenn Shafer. Algorithmic learning in a random world, volume 29. Springer, 2005. [YHC11] Liu Yang, Steve Hanneke, and Jaime Carbonell. Identifiability of priors from bounded sample sizes with applications to transfer learning. In Sham M. Kakade and Ulrike von Luxburg, editors, Proceedings of the 24th Annual Conference on Learning Theory, volume 19 of Proceedings of Machine Learning Research, pages 789–806, Budapest, Hungary, 09–11 Jun 2011. PMLR. [YLL+ 18] Caixia Yan, Minnan Luo, Huan Liu, Zhihui Li, and Qinghua Zheng. Top-k multi-class svm using multiple features. Information Sciences, 432:479–494, 2018.

36

A

A Combinatorial Proof for the Case ℓ = 1

In this appendix, we give a purely combinatorial proof of the bound |H| ≤ 1 + n(k − 1) for every class H ⊆ [k]n whose ℓ-DS dimension equals 1 with ℓ = 1. We are grateful to Nitay Amiel, who discovered the following purely combinatorial proof while he was an undergraduate student at the Technion. Proof. We argue by induction on n. Base case: n = 1. If H ⊆ [k] then clearly |H| ≤ k. Since 1 + 1 · (k − 1) = k, the bound holds. Induction step. Assume the statement holds for n − 1. Let H ⊆ [k]n have 1-DS dimension equal to 1. For each vector h ∈ H, write h = (u, a) where u = (h(1), . . . , h(n − 1)) ∈ [k]n−1

and a = h(n) ∈ [k].

For each u ∈ [k]n−1 define S(u) = {a ∈ [k] : (u, a) ∈ H}. Thus S(u) is the set of extensions of u in the n-th coordinate. Now, partition according to the size of S(u) and define Hi = {u ∈ [k]n−1 : |S(u)| = i}. Then |H| =

k X

i |Hi |.

i=1

Let H∃ =

[

Hi

i≥1

be the set of (n − 1)-vectors that admit at least one extension. Then |H| = |H∃ | +

k X

(i − 1)|Hi |.

i=2

By the induction hypothesis, |H∃ | ≤ 1 + (n − 1)(k − 1). It remains to bound the second term. Consider the bipartite graph whose left vertices S are i≥2 Hi , whose right vertices are [k], and whose edges are {(u, a) : (u, a) ∈ H}. 37

We claim that this graph contains no cycle. Indeed, suppose there were a cycle u1 → a1 → u2 → a2 → · · · → um → am → u1 . Since u1 ̸= u2 , there exists a coordinate j < n such that u1 (j) ̸= u2 (j). Restricting H to the coordinates {j, n} then produces a 2-dimensional pseudo-cube, contradicting that the 1-DS dimension equals 1. Therefore the graph is acyclic, and hence |E| ≤ |V | − 1. Now, |E| =

k X

i |Hi |,

|V | =

i=2

Thus

k X

|Hi | + k.

i=2

i |Hi | ≤

i=2

k X

k X

|Hi | + k − 1,

i=2

which implies k X

(i − 1)|Hi | ≤ k − 1.

i=2

Combining the bounds, k X
|H| = |H∃ | + (i − 1)|Hi | ≤ 1 + (n − 1)(k − 1) + (k − 1) = 1 + n(k − 1). i=2

This completes the proof.

38