The Optimal Sample Complexity of Multiclass and List Learning Chirag Pabbaraju∗
arXiv:2604.24749v1 [cs.LG] 27 Apr 2026
April 28, 2026
Abstract While the optimal sample complexity of binary classification in terms of the VC dimension is well-established, determining the optimal sample complexity of multiclass classification has remained open. The appropriate complexity parameter for multiclass classification is the DS √ dimension, and despite significant efforts, a gap of DS has persisted between the upper and lower bounds on sample complexity. Recent work by Hanneke et al. (2026) shows a novel algebraic characterization of multiclass hypothesis classes in terms of their DS dimension. Building up on this, we show that the maximum hypergraph density of any multiclass hypothesis class is upper-bounded by its DS dimension. This proves a longstanding conjecture of Daniely and Shalev-Shwartz (2014). As a consequence, we determine the optimal dependence of the sample complexity on the DS dimension for multiclass as well as list learning.
∗
Stanford University. Email: [email protected].
1
1
Introduction
Classification is a foundational task in machine learning, and understanding the minimum number of training samples required to achieve a desired classification accuracy, or determining the sample complexity of the classification task, is a core pursuit in learning theory. In the classification task, we seek to assign labels from a label space Y = {1, 2, . . . , k} to unlabeled points in a data domain X . The Probably-Approximately-Correct or PAC model of Valiant [Val84] defines a concrete theoretical framework for this task. In binary classification, where the number of classes k = 2, the optimal sample complexity of the learning task is completely understood. Namely, if the data is labeled, or rather realizable, by some target hypothesis from a hypothesis class H, then Θ(dVC ) samples, where dVC is a measure of complexity of the class known as the VC dimension [VC74], are both sufficient and necessary. In slightly more detail, one provably requires dVC + log(1/δ) Θ (1) ε many samples from a generic data distribution D, in order to output, with probability 1 − δ, a hypothesis fb that classifies with error errD (fb) := Pr(x,y)∼D [fb(x) ̸= y] at most ε on a new test point [Han16]. A similar exact characterization for binary classification also exists in the more general agnostic setting, where the data is not necessarily labeled by any hypothesis in the class. Here, the dependence on the error parameter ε degrades from 1/ε to 1/ε2 . Despite such a clean picture for binary classification, the landscape of multiclass classification, where the number of classes k > 2, is still not as exactly figured out. Keeping the sample complexity aspect aside, even the problem of determining a complexity parameter similar to the VC dimension, which provably characterizes the learning task was discovered rather recently in the work of [BCD+ 22]. The analogous object turns out to be a quantity known as the DS dimension dDS [DSS14]1 . Given this, the right answer for the optimal sample complexity of multiclass classification, similar to (1) for binary classification, would appear to dDS + log(1/δ) Θ . (2) ε Unfortunately, a precise and provable characterization of this form has proven to be elusive. In their work showing that the DS dimension characterizes multiclass learnability, [BCD+ 22] showed an upper bound of 1.5 dDS + log(1/δ) e O (3) ε e notation hides polylogarithmic factors. [HMZ24] got rid of on the sample complexity, where the O 1.5 some of these factors, but the dDS scaling persisted. On the lower bound side, [HMZ24] showed a sample complexity lower bound of dDS + log(1/δ) Ω . (4) ε √ It is widely conjectured that the bound above is optimal, and that the additional dDS term in (3), along with any log factors, are extraneous. We note that the state of affairs is similar in the agnostic multiclass learning as well. 1
We formally define all the relevant combinatorial quantities in Section 2
2
In a separate line of attack, [AACSZ23] showed a qualitatively different upper bound on the sample complexity of learning a multiclass hypothesis class H in the realizable setting, which depends on a combinatorial object known as the maximum density function µH (·). In particular, [AACSZ23] showed that with n samples, with probability 1 − δ, it is possible to achieve error at most ⌈µH (n)⌉ + log(1/δ) . (5) O n The attractive aspect about this bound is that it is completely devoid of any log factors. While the term in the numerator, namely µH (n), is in general a non-decreasing function in n, a promising avenue to derive the optimal sample complexity bound in (2) would be to show that the function µH (n) is uniformly upper-bounded by the DS dimension dDS . Indeed, this is precisely a conjecture formulated by [DSS14] in their original work that defined the DS dimension. Conjecture ([DSS14]). Let H ⊆ Y X be a hypothesis class having DS dimension dDS . There is an absolute constant c > 0 such that for any n > 0, µH (n) ≤ c · dDS . There is reason to believe that the conjecture above is true, since in the special case of k = 2, the desired bound holds, by a beautiful result due to [HLW94]. In addition, an upper bound of the form c · dDS · log(k) also holds [DSS14]. However, the conjecture in full generality has remained open since being proposed, and has resisted several natural proof approaches. Given the context of [AACSZ23]’s results, a positive resolution of the conjecture is especially meaningful, since it would establish the optimal sample complexity of multiclass learning.
1.1
Results
Building upon a recent structural breakthrough by [HMMS26], our main result is a positive resolution of the longstanding conjecture of [DSS14], helping bypass the d1.5 DS barrier on the sample complexity of multiclass learning. In fact, we show a more general result: for every ℓ ≥ 1, ⌈µℓH (n)⌉ ≤ dℓDS , where µℓH (n) and dℓDS are the maximum ℓ-density function and the ℓ-DS dimension respectively. These quantities are parameterized versions of µH (n) and dDS that were mentioned above, and satisfy that µ1H (n) = µH (n) and d1DS = dDS . Theorem 1 (Density upper-bounded by DS). Let H ⊆ [k]X be a hypothesis class having ℓ-DS dimension dℓDS . For all integers ℓ ≥ 1 and n > 0, ⌈µℓH (n)⌉ ≤ dℓDS .
(6)
Several corollaries follow from Theorem 1, which we proceed to list down. Multiclass Learning.
We begin consequences for multiclass learning. Recall from (3) with the
e that [BCD+ 22] had shown an O
d1.5 DS +log(1/δ) ε
upper bound on the sample complexity of this task in the realizable setting. While their bound was improved upon by [HMZ24], who shaved off several logarithmic factors, the d1.5 DS dependence persisted. As the first main corollary of Theorem 1, we obtain the optimal sample complexity for realizable multiclass learning. Corollary 1.1 (Optimal Sample Complexity for Multiclass Learning). Let H ⊆ [k]X be a hypothesis class having DS dimension dDS . There exists a learning algorithm A, such that for any distribution
3
Realizable Reference [BCD+ 22, HMZ24] [AACSZ23] [HMZ24] This work (Corollary 1.1)
Agnostic
Sample Complexity 1.5 e dDS +log(1/δ) O ε O µH (·)+log(1/δ) ε Ω dDS +log(1/δ) ε O
dDS +log(1/δ) ε
Reference [BCD+ 22] [CEH+ 25] [CEH+ 25] This work (Corollary 1.2)
Sample Complexity 1.5 e dDS +log(1/δ) O ε2 e dreal + dNat +log(1/δ) O ε ε2 dNat +log(1/δ) Ω dreal + 2 ε ε e O
dNat +log(1/δ) dDS ε + ε2
Table 1: Sample Complexity Bounds for Multiclass Learning D over X × [k] realizable by H, and any ε, δ ∈ (0, 1)2 , with probability at least 1 − δ over a sample S ∼ Dm , where dDS + log(2/δ) , m ≥ 9.64 ε it holds that errD (fbS ) ≤ ε, where fbS = A(S). The result above follows by directly plugging in the upper bound on ⌈µH (n)⌉ from Theorem 1 into Theorem 2.2 of [AACSZ23], and the learning algorithm achieving the guarantee is a majority vote over one-inclusion graph predictors (see Definition 4) trained on increasing pre dDS +log(1/δ) fixes of S. Together with the lower bound of Ω on the sample complexity given by ε [HMZ24, Theorem 2.5], we thus confirm that the optimal sample complexity of multiclass learning dDS +log(1/δ) is Θ . ε We next consider multiclass learning in the agnostic setting, where the distribution D over X ×[k] may be arbitrary, and not necessarily realizable by H. Here, the objective of the learning algorithm is to achieve expected to inf h∈H errD (h). For this setting, [BCD+ 22] showed an 1.5error comparable e dDS +log(1/δ) upper bound of O on the sample complexity. Recently, [CEH+ 25] improved this to ε2 e dreal + dNat +log(1/δ) a near-tight sample complexity upper bound of O , where dreal is the optimal ε ε2 sample complexity of learning H in the realizable setting, dNat is the Natarajan dimension of H e notation hides polylogarithmic factors [NT88, Nat89] (which satisfies that dNat ≤ dDS ), and the O in dNat , dreal and 1/ε. Note crucially that this bound was stated in terms of dreal , which, at the time, was unknown. As a direct consequence of Corollary 1.1, we get the following more precise upper bound for the learning algorithm given by [CEH+ 25]. Corollary 1.2 (Optimal Sample Complexity for Agnostic Multiclass Learning). Let H ⊆ [k]X be a hypothesis class having DS dimension dDS and Natarajan dimension dNat . There exists a learning algorithm A, such that for any distribution D over X × [k], and any ε, δ ∈ (0, 1)2 , with probability at least 1 − δ over a sample S ∼ Dm , where dDS dNat + log(1/δ) e + , m=O ε ε2 it holds that errD (fbS ) ≤ inf h∈H errD (h) + ε, where fbS = A(S). 4
Realizable Reference [CP23] [BDMM23] [HMMS26] [HMZ24] This work (Corollary 1.3)
Sample Complexity 1.5 ℓ6 (dℓDS ) +log(1/δ) e O ε 5 ℓ4 (dℓDS ) +log(1/δ) e O ε 1.5 ℓ(dℓDS ) +ℓ log(1/δ) e O ε ℓ d +log(1/δ) Ω DS ℓε O
ℓdℓDS +ℓ log(1/δ) ε
Agnostic Reference
Sample Complexity 1.5 ℓ6 (dℓDS ) +log(1/δ) e O 2
[CP23]
ε
[HMZ24] This work (Corollary 1.4)
Ω e O
ℓ
dDS +log(1/δ) ℓε
ℓdℓDS ℓ4 dℓNat +log(1/δ) ε + ε2
Table 2: Sample Complexity Bounds for List Learning Combined with the agnostic sample complexity lower bound of Ω
dNat +log(1/δ) dreal ε + ε2
also
shown by [CEH+ 25], we thus get that the optimal sample complexity of agnostic multiclass learning dNat +log(1/δ) dDS e (upto log factors) is Θ ε + . Table 1 summarizes the above results. ε2 List Learning. We now turn to the related task of list learning. In list learning, an algorithm is permitted to output a list hypothesis µ, which maps any point x to a list of ℓ labels instead of a single label. The error of the list hypothesis is measured as errD (µ) = Pr(x,y)∼D [y ∈ / µ(x)]. In this way, the algorithm has a more relaxed goal: so long as the list of labels it outputs merely contains the target label, it does not get penalized. When ℓ = 1, this task is equivalent to standard multiclass learning. When ℓ > 1, list learning has a characterization analogous to multiclass learning in terms of the ℓDS dimension dℓDS [CP23], whose finiteness is both sufficient and necessary for thetask. Concretely, dℓ +log(1/δ)
in the realizable case, [HMZ24] showed a sample complexity lower bound of Ω DS ℓε for 6 ℓ 1.5 e ℓ (dDS ) +log(1/δ) , whereas list learning. [CP23] showed a sample complexity upper bound of O ε 4 ℓ 5 ℓ (d ) +log(1/δ) DS e [BDMM23] also showed an (incomparable) upper bound of O . Very recently, ε ℓ 1.5 ℓ ℓ(d ) +ℓd log(1/δ) DS DS e [HMMS26] proved an upper bound of O , thus significantly improving on the ε dependence on list size ℓ. Note that similar to the multiclass learning barrier,q a barrier of (dℓDS )1.5
also persists for list learning; our Theorem 1 enables getting rid of the extra as all log factors.
dℓDS factor, as well
Corollary 1.3 (Near-optimal Sample Complexity for List Learning). Let H ⊆ [k]X be a hypothesis class having ℓ-DS dimension dℓDS , for any ℓ ≥ 1. There exists a list learning algorithm A, such that for any distribution D over X × [k] realizable by H, and any ε, δ ∈ (0, 1)2 , with probability at least 1 − δ over a sample S ∼ Dm , where ℓ dDS + log(2/δ) m ≥ 4.82(ℓ + 1) , ε it holds that errD (b µS ) ≤ ε, where µ bS = A(S). 5
The bound above is optimal in its dependence on all parameters except ℓ, where there is still Recall that for realizable multiclass learning, we were able to directly invoke the previous results of [AACSZ23]. As it turns out, their framework is general enough to also capture list learning, and this requires only a little more work. We provide the necessary details in Appendix A.1. Finally, we consider the task of agnostic list learning. Here, the objective again is have small excess error compared to inf h∈H errD (h).To our knowledge, the previous best sample complexity ℓ6 (dℓDS )1.5 +log(1/δ) e upper bound for this task is that of O given by [CP23]. We improve upon 2 a 1ℓ -versus-ℓ gap; in particular, it is optimal in its dependence on dℓDS .
ε
this by generalizing the results of [CEH+ 25] to the agnostic list learning setting, and then using Corollary 1.3. The necessary details are given in Appendix A.2. Corollary 1.4 (Improved Sample Complexity for Agnostic List Learning). Let H ⊆ [k]X be a hypothesis class having ℓ-DS dimension dℓDS and ℓ-Natarajan dimension dℓNat . There exists a list learning algorithm A, such that for any distribution D over X × [k], and any ε, δ ∈ (0, 1)2 , with probability at least 1 − δ over a sample S ∼ Dm , where ℓ ℓdDS ℓ4 dℓNat + log(1/δ) e + , m=O ε ε2 it holds that errD (b µS ) ≤ inf h∈H errD (h) + ε, where µ bS = A(S). The dependence on the ℓ-DS dimension dℓDS above is optimal upto log factors (the ℓ-Natarajan
dimension satisfies dℓNat ≤ dℓDS ), since an Ω
dℓDS +log(1/δ) ℓε
lower bound on sample complexity already dℓ
term in the carries over from the realizable setting. For ℓ > 1, it is not clear to us that the εNat 2 sample complexity is necessary. At a high level, a list predictor seems to have a “hedging” advantage when competing with only the best single hypothesis h ∈ H, which makes the standard lower bound strategy from the ℓ = 1 setting not work. We note that this term appears to be necessary in the case where the algorithm has to compete with the best list hypothesis that can be formed from hypotheses in H. Table 2 summarizes the results above. We emphasize that we view the main contribution of this work to be the structural result in Theorem 1, which directly implies a host of results. The optimal multiclass learning results follow as direct corollaries from prior work, whereas the list learning results also follow largely from generalizing pre-existing technical machinery. Lastly, we note that all our results extend to the setting with an infinite label space where k = ∞; we elaborate more on this in Remarks 2 and 4.
2
Preliminaries
We will denote the unlabeled data domain by X and identify the label space Y by [k] = {1, 2, . . . , k}. A hypothesis class H is a subset of [k]X . The error of any hypothesis h with respect to a data distribution D over X × [k] is defined as errD (h) = Pr(x,y)∼D [h(x) ̸= y]; for a list hypothesis µ, the error is errD (h) = Pr(x,y)∼D [y ∈ / µ(x)]. A distribution D is realizable by H if inf h∈H errD (h) = 0. Definition 1 (PAC learning [Val84]). Let H ⊆ [k]X be a hypothesis class. We say that H is (list) PAC learnable by a learning algorithm A with sample complexity mA,H : (0, 1) × (0, 1) → N if for every ε, δ ∈ (0, 1)2 , every distribution D over X × [k] realizable by H, for m ≥ mA,H (ε, δ), PrS∼Dm [errD (A(S)) ≥ ε] ≤ δ, where A(S) is the (list) hypothesis output by the learning algorithm on input S.
6
The definition of agnostic PAC learning allows for arbitrary distributions over X ×[k] not necessarily realizable by H, and the guarantee required of the algorithm is instead PrS∼Dm [errD (A(S)) ≥ inf h∈H errD (h) + ε] ≤ δ, for m ≥ mA,H (ε, δ). We now define several combinatorial quantities relevant to multiclass and list learning. These quantities will be parameterized in terms of a list size ℓ ≥ 1, where ℓ appears in the superscript of the quantity (e.g., dℓDS ). When ℓ = 1, we sometimes drop the superscript for convenience, and simply refer to the corresponding quantity without the superscript (e.g., dDS ). For a sequence S ∈ X n , we denote the restriction of H on S as H|S . Definition 2 (ℓ-DS dimension [DSS14, CP23]). Let H ⊆ [k]X be a hypothesis class for k ≥ 2, and let S ∈ X d be a sequence. Let us think of the members of H|S as vectors in [k]d . For any i ∈ [d], we say that f, g ∈ H|S are i-neighbors if fi ̸= gi and fj = gj , ∀j ̸= i. For any 1 ≤ ℓ < k, we say that H ℓ-DS shatters S if there exists a non-empty F|S ⊆ H|S , |F|S | < ∞ such that ∀f ∈ F|S , ∀i ∈ [d], f has at least ℓ i-neighbors in F|S . The ℓ-DS dimension of H, denoted as dℓDS = dℓDS (H), is the largest integer d such that H ℓ-DS shatters some sequence S ∈ X d . A different dimension that will also be relevant to our discussion is the ℓ-Natarajan dimension. Definition 3 (ℓ-Natarajan dimension [NT88, Nat89, CP23]). A hypothesis class H ⊆ [k]X ℓNatarajan shatters a sequence S ∈ X d if there exist (ℓ + 1)-sized lists yi ∈ {Y ⊆ [k] : |Y | = ℓ + 1}, Qd i = 1, . . . , d, such that i=1 yi ⊆ H|S . The ℓ-Natarajan dimension of H, denoted as dℓNat = dℓNat (H), is the largest integer d such that H ℓ-Natarajan shatters some sequence S ∈ X d . Observe that dℓNat ≤ dℓDS for every ℓ ≥ 1. We now define a key combinatorial object for a hypothesis class: the one-inclusion graph. Definition 4 (One-inclusion graph [HLW94, RBR06]). The one-inclusion graph of H ⊆ [k]n is a hypergraph G(H) = (V, E) that is defined as follows. The vertex set is V = H. For each i ∈ [n] and f : [n] \ {i} → [k], let ei,f be the set of all h ∈ H that agree with f on [n] \ {i}. The edge set is the multiset: E = {ei,f : i ∈ [n], f : [n] \ {i} → [k], ei,f ̸= ∅}. (7) We say that the edge ei,f ∈ E is in the direction i, and is adjacent to/contains the hypothesis/vertex h if h ∈ ei,f . Every vertex h ∈ V is adjacent to exactly n edges. The size of the edge ei,f is the size of the set |ei,f |. Note that when k is finite, the one inclusion graph of any hypothesis class H ⊆ [k]n is also finite. We proceed to define the other key quantity in Theorem 1, namely the maximum density function µℓH (n) of the one-inclusion graph. Definition 5 (ℓ-density). Let G(H) = (V, E) be the one-inclusion graph of H ⊆ [k]n . For any integer 1 ≤ ℓ < k, the ℓ-density of H is 1 X Densℓ (H) = (|e| − ℓ)+ , |V | e∈E
where (x)+ = max(x, 0). Observe that for every H ⊆ [k]n , Densℓ (H) ≤ n. Definition 6 (Maximum ℓ-density function). Let H ⊆ [k]X be a hypothesis class. For any integer 1 ≤ ℓ < k, the maximum ℓ-density function of H for sample size n µℓH (n) = maxn S∈X
max
F |S ⊆H|S ,|F |S |<∞
7
Densℓ (F|S ).
Remark 1 (Differing Names, Differing Definitions). There has been some unfortunate inconsistency in the literature in how the quantities above are named/defined. In their original paper, [DSS14] defined µH (n) differently. Their definition was as follows: µ′H (n) = maxn S∈X
1 F |S ⊆H|S ,|F |S |<∞ |F|S | max
X
|e|.
(8)
e∈E:|e|>1
Indeed, in the original statement of their conjecture, [DSS14] asked whether µ′H (n) ≤ c · dDS . µ′ (n)
However, we can verify that H2 ≤ µH (n) ≤ µ′H (n), and so the discrepancy is only upto a factor of 2 (and ℓ + 1 more generally). It is also worth mentioning that while [HLW94] originally also referred to Dens(H) defined above in Definition 5 as “density”, this quantity in the case of ℓ > 1 has been instead referred to as the “shifting average ℓ-degree” in [CP23, HMMS26].
3
Main Structural Result
Our proof of Theorem 1 builds upon the elegant algebraic characterization of multiclass hypothesis classes derived very recently by [HMMS26]. We first formally define the key technical objects from [HMMS26] that enable our result. Let W ⊆ [k]n be a hypothesis class. We can think of each w ∈ W as a vector (w1 , . . . , wn ) ∈ [k]n . Associate W with the vector space of functions VW = {f : W → R}, equipped with pointwise addition and scalar multiplication. We can interpret the members of this vector space equivalently as vectors in R|W | . Then, for any s ≥ 0 and 1 ≤ ℓ < k, consider the following special subset of VW comprising of bounded-degree, bounded-support monomials2 : n Mℓs (W ) := f : W → R f (w) = w1α1 w2α2 . . . wnαn ∀w ∈ W, αi ∈ {0, 1, . . . , k − 1} ∀i ∈ [n], |{i ∈ [n] : αi ≥ ℓ}| ≤ s} .
(9)
With the R|W | viewpoint of VW , the above definition says that if we index the coordinates of a vector by w ∈ W , then Mℓs (W ) comprises of those vectors where the entry in the wth coordinate is given by w1α1 w2α2 . . . wnαn , where the degree αi of each wi is at most k − 1, and at most s values of αi are greater than or equal to ℓ. The breakthrough insight in [HMMS26] is that the set of monomials Mℓs (W ) spans VW . While this structural characterization is contained in the proof of Theorem 2.1 in [HMMS26], we state this result as a standalone lemma. Lemma 3.1 (Spanning Lemma [HMMS26]). Let W ⊆ [k]n be a hypothesis class. For all integers ℓ ≥ 1 and s ≥ dℓDS (W ), Mℓs (W ) spans VW . We build upon the linear-algebraic characterization in the spanning lemma to show our main Theorem 1. Before we proceed to the formal details of the proof, let us sketch the proof for the ℓ = 1 case, which is simpler and captures the main ideas. The core intuition is the following: any monomial w1α1 . . . wnαn in the spanning set, which has αi = 0, is constant on every edge in direction i in the one-inclusion graph of the hypothesis class. Therefore, one can consider the subspace of functions in VW that have this defining property, and has dimension equal to the number of edges in direction i. Any monomial within the spanning set that has αi = 0 belongs to this subspace. 2
We identify every member of Mℓs (W ) with a fixed monomial representation w1α1 w2α2 . . . wnαn .
8
But crucially, the total number of linearly independent monomials in the spanning set that have αi = 0 must lower-bound the dimension of the subspace, unlocking the key inequality. More concretely, let W ⊆ [k]n be a hypothesis class with DS dimension dDS . In this case, for s = dDS , each monomial in the spanning set M1s (W ) is a monomial in at most s “active” coordinates i, where αi > 0. Given that M1s (W ) spans VW , choose a basis B ⊆ M1s (W ). Since VW has dimension |W |, the basis B has exactly |W | monomials. The key definition now is that of a direction-wise subspace Ui for every direction i ∈ [n]. This subspace comprises of all the monomials that are constant when restricted to an edge in direction i in the one-inclusion graph G(W ). As a toy example with n = 2, consider W = {(2, 1), (3, 1), (4, 2), (5, 2), (6, 2)}. Then, U1 comprises of all the vectors in R5 of the form (a, a, b, b, b). We can readily see that the dimension of Ui is exactly the number of different behaviors realized by W on [n] \ {i}, or equivalently, the number of distinct edges in G(W ) in direction i — let us call this number Ni . Now, consider the set of monomials Bi0 in the basis B for which the coordinate i is not active (i.e., αi = 0), and let Bi1 = B \ Bi0 . Observe that every monomial in Bi0 belongs to Ui , since it evaluates to the same number on the members of any edge in direction i. However, since all the monomials in Bi0 are linearly independent, it must hold that |Bi0 | ≤ dim(Ui ) = Ni
=⇒
|W | − Ni ≤ |W | − |Bi0 | = |Bi1 |.
Now let us sum this last inequality over all i ∈ [n]. The term on the left is equal to n X i=1
(|W | − Ni ) =
X
X
(|ei,a | − 1) =
i∈[n] ei,a ∈G(W )
X
(|e| − 1) = |W | · Dens1 (W ).
e∈G(W )
P On the other hand, summing the term on the right, namely ni=1 |Bi1 |, simply counts, for every monomial b ∈ B, the number of coordinates i at which it is active. Since B ⊆ M1s (W ), and every monomial in the spanning set has at most s active coordinates, we get that this sum is at most s · |B| = s|W | = dDS |W |. Dividing by |W | on both sides gives the inequality in the theorem statement. We now restate Theorem 1 for convenience, and prove it for the general case of ℓ ≥ 1. Theorem 1 (Density upper-bounded by DS). Let H ⊆ [k]X be a hypothesis class having ℓ-DS dimension dℓDS . For all integers ℓ ≥ 1 and n > 0, ⌈µℓH (n)⌉ ≤ dℓDS .
(6)
Proof. Fix ℓ ≥ 1. When n ≤ dℓDS , the inequality is immediate, since µℓH (n) ≤ n ≤ dℓDS . So, assume that n > dℓDS . For notational ease, let s = dℓDS . Fix any S ∈ X n , F |S ⊆ H|S , and let W := F|S denote this restriction for notational ease. Note that the ℓ-DS dimension of W is at most s, since the dimension cannot increase upon projection. Consider the set of monomials Mℓs (W ) defined in (9). By Lemma 3.1, we know that Mℓs (W ) spans VW . So, let B ⊆ Mℓs (W ) be a basis for VW . Note again that B comprises of monomials satisfying the condition in (9) that defines the set Mℓs (W ); furthermore, |B| = dim(VW ) = |W |. Now, for every i ∈ [n], we will define a subspace Ui ⊆ VW . To this end, let us set up some notation. For any w ∈ W , let w−i ∈ [k]n−1 denote its behavior on [n] \ {i}, and let Ti ⊆ [k]n−1 = {w−i : w ∈ W } comprise of all such distinct behaviors. Additionally, let P<ℓ comprise of all 9
univariate real-valued polynomials of degree at most ℓ − 1 mapping [k] to R. Then, the subspace Ui comprises of all functions f : W → R, such that if we restrict f to w ∈ W that share the same behavior a on [n] \ {i}, then f is simply a univariate polynomial pa of degree at most ℓ − 1 in wi . Formally, Ui := {f : W → R | ∀a ∈ Ti ∃pa ∈ P<ℓ ∀w ∈ W : (w−i = a =⇒ f (w) = pa (wi )}. (10) P We can verify that Ui is indeed a subspace of VW . We now claim that dim(Ui ) = a∈Ti min(ℓ, |ei,a |). This is more readily seen in the case of ℓ = 1; in this case, any f ∈ Ui is required to be constant on all w that share the same behavior a on [n] \ {i}. Then, dim(Ui ) = |Ti |, corresponding to exactly one degree of freedom for every behavior on [n] \ {i}. More generally, observe that the edge sets ei,a for a ∈ Ti partition W , and for a, a′ ∈ Ti , the constraint on f ∈ Ui at points w satisfying w−i = a is independent of the constraint at points w satisfying w−i = a′ . Going back to our viewpoint of Ui as vectors in R|W | , we can thus consider the restrictions of f ∈ Ui onPthe members of an edge ei,a , which constitute a subset Wa ⊆ R|ei,a | , and obtain that dim(Ui ) = a∈Ti dim(Wa ). It remains to argue that dim(Wa ) = min(ℓ, |ei,a |). Let |ei,a | = t, and suppose {h(1) , . . . , h(t) } ∈ (j) ei,a . Denote zj = hi . Observe that by definition of the edge, zj ̸= zj ′ . Furthermore, by the constraint in (10), Ui contains precisely those f for which f (h(j) ) = pa (zj ) for all j ∈ [t], for some pa (z) = c0 + c1 z + · · · + cℓ−1 z ℓ−1 . That is, the members of Wa are of the form ℓ−1 (1) f (h ) 1 z1 z1 .. . . . . = c0 .. + c1 .. + · · · + cℓ−1 .. , ℓ−1 (t) f (h )) 1 zt zt or equivalently, Wa is the column span of the t × ℓ Vandermonde matrix ℓ−1 2 1 z1 z1 . . . z1 ℓ−1 2 1 z2 z2 . . . z 2 M := . .. .. .. .. . . . . ℓ−1 2 1 zt zt . . . zt
We then claim that dim(Wa ) = rank(M ) = min(ℓ, t). To see this, suppose first that t ≤ ℓ. In this case, the square submatrix of QM comprising of the first t rows and columns is the t×t Vandermonde matrix. Its determinant is 1≤i<j≤t (zj − zi ) ̸= 0, since for every i ̸= j, zj ̸= zi as argued above. Thus, in this case, rank(M ) = t. On the other hand, suppose that t > ℓ. In this case, the square submatrix of M comprising Q of the first ℓ rows and columns is the ℓ × ℓ Vandermonde matrix. Again, its determinant is 1≤i<j≤ℓ (zj − zi ) ̸= 0. So, in this case, rank(M ) = ℓ. We conclude that dim(Wa ) = rank(M ) = min(ℓ, t) as claimed. Hence, X X dim(Ui ) = dim(Wa ) = min(ℓ, |ei,a |). a∈Ti
a∈Ti
10
Next, for any i ∈ [n], let Bi<ℓ ⊆ B be the monomials in the basis B that have degree smaller than ℓ at coordinate i. That is, Bi<ℓ := {f ∈ B | f (w) = w1α1 . . . wnαn ∀w ∈ W, αi < ℓ}. Further, let Bi≥ℓ = B \ Bi<ℓ . Observe crucially, that every monomial in Bi<ℓ also belongs to Ui . This is because for any fixed behavior a on [n] \ {i}, if we consider the evaluation of the monomial on (j) any member h(j) of ei,a , this equals some fixed constant times (hi )αi , and αi < ℓ by definition of Bi<ℓ . On the other hand, by virtue of B being a basis, it also holds that all monomials in Bi<ℓ are linearly independent. Thus, X |Bi<ℓ | ≤ dim(Ui ) = min(ℓ, |ei,a |) a∈Ti
=⇒
|Bi≥ℓ | = |B| − |Bi<ℓ | ≥ |B| −
X
min(ℓ, |ei,a |) = |W | −
a∈Ti
X
min(ℓ, |ei,a |)
a∈Ti
=
X
|ei,a | −
a∈Ti
X
min(ℓ, |ei,a |)
a∈Ti
(since the edges sets ei,a for a ∈ Ti partition W ) X (|ei,a | − ℓ)+ . = a∈Ti
Summing over all i ∈ [n], we get n X X i=1 a∈Ti
(|ei,a | − ℓ)+ ≤
n X
|Bi≥ℓ | =⇒ |W | · Densℓ (W ) ≤
i=1
n X
|Bi≥ℓ |.
i=1
(since the left term sums (|e| − ℓ)+ over all edges e in G(W )) P But now, observe that the sum ni=1 |Bi≥ℓ | counts, over all the basis monomials in B, the number of coordinates i that have degree at least ℓ. Since B ⊆ Mℓs (W ), this number is at most s, by definition of Mℓs (W ) (see (9)). Thus, we get that |W | · Densℓ (W ) ≤
n X
|Bi≥ℓ | ≤
X
s = s|B| = s|W |.
f ∈B
i=1
Dividing by |W | gives Densℓ (W ) ≤ s = dℓDS . Thus, we have shown that for every S ∈ X n , F|S ⊆ H|S , denoting W = F|S , it holds that Densℓ (W ) ≤ dℓDS . It follows that µℓH (n) = maxn max Densℓ (F|S ) ≤ dℓDS . S∈X
F |S ⊆H|S
Finally, since dℓDS is always an integer, it must hold that ⌈µℓH (n)⌉ ≤ dℓDS , completing the proof. Remark 2 (Extension to Infinite Label Spaces). We note that Theorem 1 also holds when k = ∞. Observe that the definition of µℓH (n) (Definition 6) only considers restrictions F |S that have finite size on sequences S ∈ X n . Thus, for any such F|S = W , the number of possible labels that can be realized by members of W on any single coordinate i ∈ [n] is finite (say ki < ∞). It can then be verified that the spanning lemma continues to hold for VW , where in the definition of the monomial set Mℓs (W ), instead of requiring 0 ≤ αi < k, we change the degree condition on each αi to be 0 ≤ αi < ki . Thereafter, the proof of Theorem 1 above goes through verbatim, giving us that Densℓ (W ) ≤ dℓDS (W ) ≤ dℓDS (H). 11
Remark 3 (Optimality of the Constant). We note that the upper bound in Theorem 1 is tight including the constant. To see this, consider the hypothesis class H = [k]s × [ℓ]m−s as k gets large. We have that dℓDS (H) = s, whereas 1 ℓ s−1 m−s ℓ ⌈µH (m)⌉ ≥ Dens (H) = s m−s s · k ·ℓ · (k − ℓ) = s 1 − −−−→ s = dℓDS (H). k ℓ k k→∞ On the other hand, if we consider the definition µ′H (n) originally considered by [DSS14] (and defined in (8)), [DSS14] already show the lower bound dDS ≤ µ′H (n). As discussed in Remark 1, µ′H (n) ≤ µH (n), meaning that the upper bound implied by Theorem 1 for this definition of µ′H (n) 2
is loose by at most a factor of 2.
4
Concluding Thoughts
Our proof for upper-bounding µℓH (n) by dℓDS is inherently algebraic. In contrast, classical proofs of this result for the binary case (where the DS dimension becomes equal to the VC dimension) have a distinctly combinatorial flavor [HLW94, Hau95]. For example, the elegant proof by [Hau95] is based on the classical shifting operation. In the binary case, the VC dimension and the one-inclusion graph respect nice invariances upon shifting — shifting does not increase the VC dimension, and does not decrease the number of edges in the one-inclusion graph. When k > 2, neither of these properties hold (see Example 19 in [BCD+ 22]). Indeed, these pathologies appear to obstruct most natural inductive proof strategies while working with the DS dimension. In the discussion section of their paper, [HMMS26] comment on the implications of combinatorial proofs for DS dimension-related results beyond their mere appeal. Namely, while they used their algebraic characterization to prove an optimal Sauer’s lemma for multiclass classes, they speculated that other proofs of their result that have a more combinatorial flavor could lead to improving the sample complexity of multiclass learning. It is thus interesting to us that their algebraic characterization itself turned out to be one way to complete the puzzle. With regards to future directions, now that the precise dependence of the sample complexity on the DS dimension seems to be figured out, it would be interesting to focus on the other relevant parameters and pin down their optimal dependence, particularly in the list learning setting. For example, there are still polynomial factor gaps in the dependence on the list size ℓ in the upper and lower bounds for sample complexity. In a different direction, it would be interesting to further explore what could be achieved using algebraic methods in multiclass and list learning.
Acknowledgements This work is supported by a Google PhD Fellowship, and Moses Charikar’s and Gregory Valiant’s Simons Investigator Awards. The author would like to thank Oliver Janzer for helpful discussions about this problem.
References [AACSZ23] Ishaq Aden-Ali, Yeshwanth Cherapanamjeri, Abhishek Shetty, and Nikita Zhivotovskiy. Optimal pac bounds without uniform convergence. In 2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS), pages 1203–1223. IEEE, 2023. 3, 4, 6, 15 12
[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. 2, 3, 4, 12, 15
[BDMM23] Nataly Brukhim, Amit Daniely, Yishay Mansour, and Shay Moran. Multiclass boosting: simple and intuitive weak learning criteria. Advances in Neural Information Processing Systems, 36:1403–1425, 2023. 5 [CEH+ 25]
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. arXiv preprint arXiv:2511.12659, 2025. 4, 5, 6, 15, 17, 18
[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. 5, 6, 7, 8, 14, 15, 17, 18
[DSS14]
Amit Daniely and Shai Shalev-Shwartz. Optimal learners for multiclass problems. In Conference on Learning Theory, pages 287–316. PMLR, 2014. 2, 3, 7, 8, 12
[Han16]
Steve Hanneke. The optimal sample complexity of pac learning. Journal of Machine Learning Research, 17(38):1–15, 2016. 2
[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. 12
[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. 3, 7, 8, 12
[HMMS26] Steve Hanneke, Qinglin Meng, Shay Moran, and Amirreza Shaeiri. An optimal sauer lemma over k-ary alphabets. arXiv preprint arXiv:2604.12952, 2026. 3, 5, 8, 12, 14, 15, 17, 18 [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. 2, 3, 4, 5
[Nat89]
Balas K Natarajan. On learning sets and functions. Machine Learning, 4(1):67–97, 1989. 4, 7
[NT88]
Balaubramaniam Kausik Natarajan and Prasad Tadepalli. Two new frameworks for learning. In Machine Learning Proceedings 1988, pages 402–415. Elsevier, 1988. 4, 7
[PS25]
Chirag Pabbaraju and Sahasrajit Sarmasarkar. A characterization of list regression. In Gautam Kamath and Po-Ling Loh, editors, Proceedings of The 36th International Conference on Algorithmic Learning Theory, volume 272 of Proceedings of Machine Learning Research, pages 870–920. PMLR, 24–27 Feb 2025. 15
[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. 7 13
[SSBD14]
Shai Shalev-Shwartz and Shai Ben-David. Understanding machine learning: From theory to algorithms. Cambridge university press, 2014. 16
[Val84]
Leslie G Valiant. A theory of the learnable. Communications of the ACM, 27(11):1134– 1142, 1984. 2, 6
[VC74]
Vladimir Vapnik and Alexey Chervonenkis. Theory of pattern recognition, 1974. 2
[vN28]
J v. Neumann. Zur theorie der gesellschaftsspiele. Mathematische annalen, 100(1):295– 320, 1928. 16
A
List Learning Results
Most of the technical machinery required for the implications of Theorem 1 to list learning already exist in the literature. We give the necessary details in this appendix, albeit in an admittedly condensed manner.
A.1
Realizable Case
Proof of Corollary 1.3. Consider the one-inclusion graph list predictor A given in Algorithm 1 in [CP23]. At a high level, given a training dataset S = {(x1 , y1 ), . . . , (xn , yn )}, in order to make a prediction on any test point x, the algorithm constructs the one-inclusion graph G(H|(x1 ,...,xn ,x) ) of the class H projected onto the unlabeled data (x1 , . . . , xn , x). It then maps/orients every edge e in the graph to a subset of the hypotheses adjacent to/contained in e, where this subset has size at most ℓ. For any such “ℓ-list” orientation σ ℓ , one can define the ℓ-outdegree of a vertex v in the graph (denoted outdegℓ (v; σ ℓ )), which is the count of edges adjacent to v that have been oriented to a subset that does not include v. The one-inclusion graph list predictor A then specifically constructs an orientation σ ℓ for which the maximum outdegree of any vertex according to that orientation is minimized. To predict a list of labels for the test point x, the algorithm then looks at the edge corresponding to the labeled training data (x1 , y1 ), . . . , (xn , yn ). The orientation σ ℓ would have oriented this edge to some set of at most ℓ hypotheses. The algorithm outputs the list of labels that these hypotheses assign to x. Given any training dataset S = {(x1 , y1 ), . . . , (xn , yn )} realizable by H, we will be concerned with the leave-one-out error of A, defined as n h i X Mn := 1 yi ∈ /µ bℓS−i (xi ) , i=1
where S−i = S \ {(xi , yi )}, and µ bℓS−i = A(S−i ) is the output of the one-inclusion graph list predictor trained on S−i . Because the algorithm constructs the same one-inclusion graph irrespective of the point xi that is held out as the test point, it follows that n h i X 1 yi ∈ /µ bℓS−i (xi ) = outdegℓ (y; σ ℓ ), i=1
where y = (y1 , . . . , yn ) is the vertex corresponding to the ground-truth labels. Now, the proof of Lemma 3.20 in [HMMS26] shows that for any class W ⊆ [k]n , there exists an ℓ-list orientation σ ℓ of the edges of G(W ) such that ℓ ℓ ℓ max outdeg (v; σ ) ≤ max Dens (F) ≤ ⌈µW (n)⌉ . (11) v∈G(W )
F ⊆W
14
But by Theorem 1, the right-hand side above is upper-bounded by dℓDS (W ). Plugging this into the leave-one-out error bound above, we get that n h i X Mn = 1 yi ∈ /µ bℓS−i (xi ) ≤ dℓDS (H). (12) i=1
We now observe that the one-inclusion graph list predictor A satisfies both the assumptions — symmetry and bounded leave-one-out error — required of Theorem 2.1 in [AACSZ23], with the loss function L : [k]≤ℓ × [k] → [0, 1] interpreted as L(µ, y) = 1[y ∈ / µ]. We can therefore apply that theorem, and obtain that ℓ n−1 dDS (H) + log(2/δ) 4 X Mn + log(2/δ) ℓ errD µ bS≤t ≤ 4.82 ≤ 4.82 , (13) 3n n n t=n/4
with probability at least 1 − δ over the draw of S = {(x1 , y1 ), . . . , (xn , yn )} from Dn , and where S≤t = {(x1 , y1 ), . . . , (xt , yt )}. But then, consider the list predictor defined by the Top-ℓ vote µ bℓS (x) = Top-ℓ µ bℓS≤n/4 (x), . . . , µ bℓS≤n−1 (x) , where Top-ℓ returns the list of the first ℓ labels sorted in descending order according to the count of lists in µ bℓS≤n/4 (x), . . . , µ bℓS≤n−1 (x) that they occur in. Crucially, whenever the Top-ℓ vote µ bℓS (x) does not contain a label y, it must necessarily hold that at least 3n/4 ℓ+1 out of the 3n/4 lists ℓ ℓ bS≤n−1 (x) do not contain y; otherwise, the Top-ℓ vote would have picked y. In µ bS≤n/4 (x), . . . , µ conclusion, we get that h h ii errD (b µℓS ) = E(x,y)∼D 1 y ∈ /µ bℓS (x) n−1 X 4 ≤ E(x,y)∼D (ℓ + 1) 1[y ∈ /µ bℓS≤t (x)] 3n t=n/4
= (ℓ + 1) ·
4 3n
n−1 X
errD µ bℓS≤t
t=n/4
ℓ dDS (H) + log(2/δ) . ≤ 4.82(ℓ + 1) n
(from (13))
Remark 4 (Extension to Infinite Label Spaces). When considering an infinite label space, the only step above that needs additional justification is the outdegree bound in (11). With an infinite label space, the one-inclusion graph G(H|x1 ,...,xn ,x ) may be infinite. While [AACSZ23, HMMS26] show the existence of an ℓ-list orientation that has ℓ-outdegree at most µ(n) only for finite one-inclusion graphs, a compactness argument similar to that given in Appendix B in [BCD+ 22] / Appendix A in [CP23] / Appendix C.1 in [PS25] can be used to show the existence of an ℓ-list orientation on the infinite graph, which also satisfies the required ℓ-outdegree bound. With this additional consideration, the rest of the proof holds as is.
A.2
Agnostic Case
Proof of Corollary 1.4. Fix D to be any arbitrary distribution over X × [k]. We follow the proof structure of [CEH+ 25]. 15
Step 1: Approximation by Finite List Cover. Let A be the list learner from Corollary 1.2 which achieves near-optimal sample complexity in the realizable setting. Note that this learner is deterministic. Consider any sample S = {(x1 , y1 ), . . . , (xm , ym )} that is realizable by H. By a standard minimax argument, there exists a compression function κ which maps S to a subsample S ′ ∈ S k1 (m) , where k1 (m) = O(ℓdℓDS log m), and a list reconstruction function ρ with list size |ρ(S ′ )(x)| ≤ O(ℓ log m) for all x ∈ X , such that yi ∈ ρ(S ′ )(xi ) for every i ∈ [m]. To see this, fix any distribution P over S. Since S is realizable by H, the distribution P is also realizable by H. Then, by the guarantee in Corollary 1.2 for A, we know that for d := O(ℓdℓDS ), there exists T ∈ S d for which Pr(x,y)∼P [y ∈ / A(T )(x)] ≤ 1/3. By the minimax theorem [vN28], there exists a distribution Q over sequences T ∈ S d , such that for every fixed (xi , yi ) ∈ S, PrT ∼Q [yi ∈ / A(T )(xi )] ≤ 1/3. Consider sampling j sequences T1 , . . . , Tj i.i.d. from Q, for j = O(log m). We have that " / PrT1 ,...,Tj ∼Qj yi ∈
j [
# A(Tr )(xi ) ≤ 3−j ≤ 1/2m.
r=1
By a union bound over i ∈ [m] and an application of the probabilistic S method, we get that there exist T1 , . . . , Tj such that for every i ∈ [m], it holds that yi ∈ jr=1 A(Tr )(xi ). We thus set S κ(S) = S ′ = (T1 , . . . , Tj ), and ρ(S ′ )(x) = jr=1 A(Tr )(x). Note that |ρ(S ′ )(x)| ≤ O(ℓ log m) as required. Given this, consider obtaining a sample S1 ∼ Dn1 from the data distribution D, for n1 to be specified later. Define the finite list cover family: O(d)
F(S1 ) := {ρ(S ′ ) : S ′ = (T1 , . . . , TO(log n1 ) ), Tr ∈ S1 O(d log(n ))
O(ℓdℓ
∀r}.
log(n ))
1 1 We have that |F(S1 )| = n1 = n1 DS , and every member of F(S1 ) is a list function mapping to a list of size O(ℓ log n1 ). Next, fix any h ∈ H, and let S1 (h) = {(x, y) ∈ S : y = h(x)}, so that S1 (h) is realizable by h. By our compression argument above, we have that there exists µh ∈ F(S1 ) such that y ∈ µh (x) for every (x, y) ∈ S1 (h). In other words, µh has zero empirical loss on S1 under the loss function
1[h(x) = y, y ∈ / µ(x)]. Then, by the standard “compression implies generalization” argument (e.g., Theorem 30.2 in [SSBD14]), we get that for every h ∈ H, with probability at least 1 − δ/3 over the draw of S1 , there exists µh ∈ F(S1 ) such that ℓ ℓdDS log2 (n1 ) + log(1/δ) Pr(x,y)∼D [h(x) = y, y ∈ / µh (x)] ≤ O . n1 Step 2: Multiplicative Weights. Condition on the high-probability good event on the sample S1 above, and let F (S1 ) be the finite cover of list hypotheses constructed there. Now consider obtaining a fresh sample S2 = {(x1 , y1 ), . . . , (xT , yT )} ∼ DT , for T to be specified later. We run 16
the multiplicative weights procedure given in Algorithm 3 in [CEH+ 25]. Namely, we initialize w1 (µ) = 1 for every µ ∈ F(S1 ), and proceed in rounds t = 1, 2, . . . , T . At round t, we sample µt ∼ pt , where pt is a distribution over F (S1 ) satisfying pt (µ) ∝ wt (µ). Then, for every µ ∈ F(S1 ), the reward rt (µ) is defined as " # [ rt (µ) = 1 yt ∈ µ(xt ), yt ∈ / µr (xt ) . r<t
We correspondingly update wt+1 (µ) = wt (µ) exp(rt (µ)/2) for every µ ∈ F(S1 ). At the end of T rounds, we obtain the list hypothesis ν, defined as ν(x) =
T[ −1
µt (x).
t=1
We have that |ν(x)| ≤ O(ℓT log n1 ). Furthermore, the analysis of the multiplicative weights procedure from [CEH+ 25] extends verbatim to our setting. Namely, Theorem 3.4 in [CEH+ 25] guarantees that for every µ ∈ F(S1 ), with probability at least 1−δ/3 (over the draw of S2 and the multiplicative weights procedure, which then results in ν), the list hypothesis ν satisfies log(|F(S1 )|) + log(1/δ) . Pr(x,y)∼D [y ∈ µ(x), y ∈ / ν(x)] ≤ O T Learning a List-Bounded Classifier. Suppose both the good events from Steps 1 and 2 have occurred, and consider the list hypothesis ν constructed at the end of Step 2. Draw a fresh sample S3 ∼ Dn3 , for n3 to be specified later. With respect to ν, define the “inside-menu” loss LνD of a predictor as LνD (µ) = Pr(x,y)∼D [y ∈ ν(x), y ∈ / µ(x)],
for list predictors µ,
LνD (h) = Pr(x,y)∼D [y ∈ ν(x), y ̸= h(x)],
for single-label predictors h.
Thus, LνD only penalizes a predictor on points (x, y) where y ∈ ν(x). Our goal now in this step is to derive an agnostic learner for this loss. For this, we will extensively utilize the machinery from [CP23] and [HMMS26]. For any sample S, let hS ∈ arg min h∈H
1 X 1[y ∈ ν(x), y ̸= h(x)]. |S| (x,y)∈S
Then, let S + = {(x, y) ∈ S : y ∈ ν(x), hS (x) = y}. Note that S + is realizable by both H and the list ν. We are then in a position to directly instantiate Lemma 7.5 from [CP23] for the purposes of obtaining a sample compression on S + of size O(ℓ6 dℓNat log(p) log(|S + |)), where p = O(ℓT log n1 ) is the list size of ν. However, we will save a factor of ℓ2 by instead routing through an optimization in [HMMS26], which lets us derive a sample compression of size k3 := O(ℓ4 dℓNat log(p) log(|S + |)) instead. We choose not to repeat all their arguments here, and only provide a sketch for how this compression scheme is constructed: Consider the subclass H′ ⊆ H|S + comprising of all the patterns realized by H on S + that are also realizable 17
by the list ν. Now, [HMMS26, Lemma 3.20] shows that there is an ℓ-list orientation σ ℓ of the one-inclusion graph of this class that has maximum ℓ-outdegree at most its ℓ-exponential dimension, which, by Lemma 6.6 in [CP23], is at most O(ℓ2 dℓNat log(p). This outdegree bound allows one to use the one-inclusion graph predictor as a weak list learner, whereupon, by a similar minimax argument as that in Step 1, one obtains a valid compression and reconstruction for S + . This last part is similar to the proof of Lemma 7.5 in [CP23], and requires: (1) the weak learner to have error O(1/ℓ), and (2) a Chernoff bound to ensure that a Top-ℓ vote over the weak learner predictions (i.e., the output of the reconstructor) contains the correct label. These latter two steps together incur an additional ℓ2 log(|S + |) cost, giving a total compression set size of O(ℓ4 dℓNat log(p) log(|S + |)) as claimed. The list predictor µ b output by the reconstructor of this compression scheme satisfies that µ b(x) ⊆ + ν(x) for every x ∈ X , and furthermore, for every (x, y) ∈ S , it holds that y ∈ µ b(x). In other b ν + on S + . By definition of hS , it then also follows words, µ b has zero empirical inside-menu loss L S b ν on S, i.e., that µ b has minimum empirical inside-menu loss L S b ν (b bν L S µ) ≤ inf LS (h), h∈H
and hence, this compression scheme is an agnostic sample compression scheme for the inside-menu loss. By a generalization bound for agnostic compression schemes (e.g., see Theorem 11 in [CP23]), we get that with probability at least 1 − δ/3 over S3 ∼ Dn3 , s k log n + log(1/δ) 3 3 . (14) LνD (b µ) ≤ inf LνD (h) + O h∈H n3 This implies, by a similar chain of inequalities as in [CEH+ 25, Theorem 3.5], that with probability at least 1 − δ/3 over S3 ∼ Dn3 , the following inequality holds uniformly for all h ∈ H: s k log n + log(1/δ) 3 3 . errD (b µ) − errD (h) ≤ Pr(x,y)∼D [y ∈ / ν(x), h(x) = y] + O n3 Putting it all together. Let h⋆ ∈ H satisfy that errD (h⋆ ) ≤ inf h∈H errD (h) + ε/4. Condition on the good event in Step 1 over the sample S1 ∼ Dn1 , which happens with probability at least 1 − δ/3, to obtain a list cover F(S1 ) with the guarantee that there exists µ⋆ ∈ F(S1 ) for which ℓ ℓdDS log2 (n1 ) + log(1/δ) ⋆ ⋆ Pr[h (x) = y, y ∈ / µ (x)] ≤ O . (15) n1 Next, condition further on the good event in Step 2 over the sample S2 ∼ Dn2 and the multiplicative weights procedure, which happens with probability at least 1 − δ/3, and results in a list hypothesis ν with the guarantee log(|F(S1 )|) + log(1/δ) ⋆ Pr[y ∈ µ (x), y ∈ / ν(x)] ≤ O . (16) T A union bound gives us that with probability at least 1 − 2δ/3 over Steps 1 and 2, Pr[h⋆ (x) = y, y ∈ / ν(x)] = Pr[h⋆ (x) = y, y ∈ / ν(x), y ∈ / µ⋆ (x)] + Pr[h⋆ (x) = y, y ∈ / ν(x), y ∈ µ⋆ (x)] ≤ Pr[h⋆ (x) = y, y ∈ / µ⋆ (x)] + Pr[y ∈ / ν(x), y ∈ µ⋆ (x)] ℓ ℓdDS log2 (n1 ) + log(1/δ) log(|F(S1 )|) + log(1/δ) ≤O + , n1 T 18
(17)
where in the last inequality, we combined (15) and (16). Finally, condition on the good event in Step 3, which happens with probability at least 1 − δ/3 over the draw of S3 ∼ Dn3 , and results in an ℓ-list predictor µ b that satisfies s k log n + log(1/δ) 3 3 . errD (b µ) − errD (h⋆ ) ≤ Pr[y ∈ / ν(x), h⋆ (x) = y] + O n3 Taking a union bound over the event in (17), we get that with probability at least 1 − δ over all the steps, it holds that s 2 ℓ ℓd log (n1 ) + log(1/δ) log(|F(S1 )|) + log(1/δ) k3 log n3 + log(1/δ) + + errD (b µ) − errD (h⋆ ) ≤ O DS n1 T n3 s 2 2 ℓ ℓ ℓd log (n1 ) + log(1/δ) ℓdDS log (n1 ) + log(1/δ) k3 log n3 + log(1/δ) = O DS + + . n1 T n3 We set n1 , T and n3 such that each of the terms in the parentheses above is at most ε/4. This requires setting ℓ 4 ℓ ℓ ℓdDS + log(1/δ) ℓ dNat + log(1/δ) ℓdDS + log(1/δ) e e e , T =O , n3 = O . n1 = O ε ε ε2 Recalling that errD (h⋆ ) ≤ inf h∈H errD (h) + ε/4, we then get errD (b µ) ≤ inf errD (h) + ε, h∈H
which is the required agnostic list learning guarantee. The total sample complexity is ℓ ℓdDS ℓ4 dℓNat + log(1/δ) e n1 + T + n3 = O + . ε ε2
.
19