Improved Sample Complexity for Multiclass PAC Learning

Authors: steve  hanneke
shay  moran
qian  zhang
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-14 14:39:42

Abstract: We aim to understand the optimal PAC sample complexity in multiclass learning. While finiteness of the Daniely-Shalev-Shwartz (DS) dimension has been shown to characterize the PAC learnability of a concept class [Brukhim, Carmon, Dinur, Moran, and Yehudayoff, 2022], there exist polylog factor gaps in the leading term of the sample complexity. In this paper, we reduce the gap in terms of the dependence on the error parameter to a single log factor and also propose two possible routes towards completely resolving the optimal sample complexity, each based on a key open question we formulate: one concerning list learning with bounded list size, the other concerning a new type of shifting for multiclass concept classes. We prove that a positive answer to either of the two questions would completely resolve the optimal sample complexity up to log factors of the DS dimension.

Main paper: 
 introduction: 
 Multiclass learning refers to the problem of classifying an input feature from a set (feature space) X to a label in a set (label space) Y with |Y| ą 2 (Y can be infinite) [Natarajan, 1989 , Ben-David et al., 1995 , Daniely and Shalev-Shwartz, 2014 , Brukhim et al., 2022] . When |Y| " 2, the problem is known as binary classification. Multiclass learning has wide applications to various tasks in machine learning including image classification [Rawat and Wang, 2017] , natural language processing [Kowsari et al., 2019] , tissue classification [Li et al., 2004] , etc. For theoretical analysis of multiclass learning, a probabilistic setting is typically assumed, where all the feature-label pairs in the training sequence are assumed to be independent and identically distributed (iid) samples from some distribution P over X ˆY. Then, the objective of the learner is to minimize the error rate of the output classifier under the distribution P . A basic framework in the probabilistic setting is Probably Approximately Correct (PAC) learning [Valiant, 1984] . Though the characterization of PAC learnability of a binary concept class with the finiteness of its Vapnik-Chervonenkis (VC) dimension has been proved by Vapnik and Chervonenkis [1968] , the characterization of the multiclass PAC learnability remained open until Brukhim et al. [2022] showed the equivalence between the PAC learnability of a concept class and the finiteness of its Daniely-Shalev-Shwartz (DS) dimension (dim, see Definition 1.4) [Daniely and Shalev-Shwartz, 2014 ] instead of Natarajan dimension or graph dimension.However, the problem of establishing the optimal sample complexity or error rate (see Section 1.1 for formal definitions) for multiclass learning remains unsolved. For binary concept classes, Hanneke [2016] showed that the sample complexity is in Θppd `logp1{δqq{εq where d is the VC dimension of the concept class. Since DS dimension and VC dimension coincide for binary concept classes, it is natural to ask if the sample complexity of a concept class H Ď Y X for |Y| ą 2 is also in Θppd `logp1{δqq{εq where d " dimpHq is the DS dimension of H. In terms of the upper bound, it asks if there exists a multiclass learner whose worst case error rate is in Oppd `logp1{δqq{nq with probability at least 1 ´δ, where n denotes the size of the training sequence. However, on the one hand, an explicit proof of the Ωppd `logp1{δqq{εq lower bound on the sample complexity is still missing in the literature. On the other hand, the current best upper bound on worst case error rate to our knowledge is O `pd 3{2 logpdq`d logplogpnqqq log 2 pnq`logp1{δq n ˘ [Brukhim et al., 2022] , which differs from the conjectured rate by the factor plogplogpnqq `?d logpdqq log 2 pnq.In this paper, we step forward towards improved sample complexity and error rate in multiclass learning. As the concept class is fixed and the sample size increases during an online learning process, we mainly focus on improving the error rate in terms of the sample size n. Specifically, for a concept class H Ď Y X with dimpHq " d, we prove an Ωppd `logp1{δqq{εq lower bound on its sample complexity and construct a multiclass learner whose worst case error rate is Oppd 3{2 logpdq logpnq `logp1{δqq{nq with probability at least 1 ´δ, which implies that the sample complexity of H is O `d3{2 logpdq logpd{εq`logp1{δq ε ˘. Our results greatly narrow the gap between the upper and lower bounds of the sample complexity and the error rate. The dependence of the upper bound of the error rate on the sample size has also been improved from Oplogplogpnqq log 2 pnq{nq to Oplogpnq{nq (treating d as a constant). The multiclass learner we construct builds upon a list learner which predicts a list of labels for the test point (see Section 2.1 for a detailed introduction to list learning). Actually, we prove a reduction from multiclass learning to list learning and upper bound the error rate of the constructed multiclass learner with some function of the list size and the expected error rate of the list learner (the probability of excluding the true label in the predicted list). Moreover, the upper bound indicates that a list learner with size independent of n and expected error rate scaling linearly in 1{n in terms of the sample size n would imply an Op1{nq error rate (treating d as a constant). We leave the construction of such list learners an open question. Furthermore, we also explore an alternative combinatorial approach towards improved sample complexity in multiclass learning. For a concept class, we can define a hypergraph called the one-inclusion graph [Haussler et al., 1994] on its projection to a finite sequence of features (see Section 1.1 for definitions). Then, informally speaking, the "density" (defined through the average degree of the one-inclusion graph) of a concept class can be used to upper bound the error rate of multiclass learning [Daniely and Shalev-Shwartz, 2014, Aden-Ali et al., 2023] . Specifically, if we can upper bound the density of any concept class H by a multiple of its DS dimension, then the sample complexity is in OppdimpHq `logp1{δqq{εq, which matches the lower bound we prove. Thus, a proof of the above upper bound directly leads to a ΘppdimpHq `logp1{δqq{εq sample complexity for multiclass learning. When dimpHq " 1, we successfully prove the Θplogp1{δq{εq sample complexity in Theorem 3.2. For general concept classes, we develop a technique named "pivot shifting" similar to the shifting operator [Haussler, 1995] on concept classes. We show that if a pivot shifting does not increase the DS dimension of a concept class, then its density is upper bounded by twice the DS dimension. We leave the impact of pivot shifting on DS dimension as another open question.Throughout the paper, we use N to denote the set of positive integers. For any n P N, we define rns :" t1, . . . , nu. For any sets X , Y, sequence x " px 1 , . . . , x n q P X n , and function f P Y X , we define the subsequence x ´i :" px 1 , . . . , x i´1 , x i`1 , . . . , x n q for i P rns and f | x :" pf px 1 q, . . . , f px n qq. The projection of a set F Ď Y X to x is defined asF | x :" tf | x : f P F u Ď Y n .Outline In Section 1.1, we introduce the problem of multiclass learning and review some existing results. In Section 1.2, we summarize the key points of our theoretical results. In Section 2, we introduce list learning, present the reduction from multiclass learning to list learning, and improve the sample complexity upper bound of multiclass learning via this reduction together with a boosting technique for list learners. In Section 3, we prove the optimal sample complexity for classes of DS dimension 1, introduce the intuition and the definition of "pivot shifting", and demonstrate its potential application to the proof of the optimal sample complexity of multiclass learning.In this section, we formally introduce the problem of multiclass learning [Valiant, 1984] . For any distribution P over X ˆY, the error rate of a classifier h P Y X under P is defined as er P phq :" P ptpx, yq P X ˆY : y ‰ hpxquq.In this paper, we focus on realizable distributions: for a concept class H Ď Y X , a distribution P over X ˆY is H-realizable if inf hPH er P phq " 0. Let REpHq denote the set of H-realizable distributions. Besides, ppx i , y i qq n i"1 P pX ˆYq n is H-realizable if Dh P H such that y i " hpx i q, @i P rns. Definition 1.1 (Multiclass learner). A multiclass learner (or a learner) A is an algorithm which given a sequence s P Y 8 n"0 pX ˆYq n and a concept class H Ď Y X , outputs a classifier Aps, Hq P Y X .Then, we can define multiclass PAC learning as follows. ř n i"1 1 hpxiq‰Aps´i,Hqpxiq .We further define ε A,H :" sup P PREpHq ε A,H,P , ε H :" inf A ε A,H , and ε H,trans :" inf A ε A,H,trans .By a leave-one-out argument [Brukhim et al., 2022, Fact 14] , we observe that ε A,H ď ε A,H,trans . Aden-Ali et al. [2023, Theorem 2 .1] upper bounded the high probability error rate using the transductive error rate, which leads to a guarantee on PAC sample complexity. Based on their result, we prove the same upper bound up to a multiplicative constant on the high probability error rate using the expected error rate in Theorem 2.6.Next, we define pseudo-cubes and DS dimensions of concept classes. Here, we also present their extensions to the setting of k-list learning for future reference in Section 2.1. Now, we introduce some existing results in multiclass learning. Brukhim et al. [2022] proved that a class H Ď Y X is PAC learnable if and only if d :" dimpHq ă 8, and there exists a multiclass learner A which for any P P REpHq, δ P p0, 1q, n P N, and S " P n , satisfies that with probability at least 1 ´δ,EQUATIONwhich is also the best upper bound before this paper to our knowledge. In terms of lower bound, it follows from Charikar and Pabbaraju [2023, Theorem 6] that ε H pnq " Ω pd{nq. Thus, the current upper and lower bounds of the expected error rate does not match. Moreover, a potentially sharp lower bound on the sample complexity M H is still missing.The learner A in Brukhim et al. [2022] relies on orienting the one-inclusion graphs defined below as a building block. Definition 1.5 (One-inclusion graph, Haussler et al. 1994) . The one-inclusion graph (OIG) of H Ď Y n for n P N is a hypergraph GpHq " pH, Eq where H is the vertex-set and E denotes the edge-set defined as follows. For any i P rns and f : rnsztiu Ñ Y, we define the set e i,f :" th P H : hpjq " f pjq, @j P rnsztiuu. Then, the edge-set is defined asE :" tpe i,f , iq : i P rns, f : rnsztiu Ñ Y, e i,f ‰ Hu.For any pe i,f , iq P E and h P H, we say h P pe i,f , iq if h P e i,f and the size of the edge is|pe i,f , iq| :" |e i,f |.Typically, we consider the one-inclusion graph of the projection of a concept class H Ď Y X to a sequence x P X n with n P N, i.e., GpH| x q. The "density" of H discussed in Section 3 is defined via the "maximal average degree" (defined below) of the hypergraph GpH| x q. Definition 1.6 (Degree and average degree). For any hypergraph G " pV, Eq and v P V , we define the degree of v in G to be degpv; ř ePE p|e| ´1q. For general V , we can define the maximal average degree of G to be mdpGq :" sup U ĎV :|U |ă8 avgdegpGrU sq, where GrU s " pU, ErU sq denotes the induced hypergraph of G on U Ď V with ErU s :" te X U : e P E, e X U ‰ Hu.Note that for finite graphs, the average out-degree does not depend on the choice of orientation on G. Moreover, since |e| ě 2 for all e P E n , we have avgdegpGq "EQUATIONNow, we can define the density of a concept class as follows.Definition 1.7. The density of H Ď Y X is defined as µ H pmq :" sup xPX m mdpGpH| x qq, @m P N.In this section, we summarize the key points of our theoretical results. The full versions of some results are stated in Section 2 and 3. We first need the following definition to rule out trivial concept classes for which one training point suffices to achieve zero error rate under any realizable distribution. Definition 1.8 (Nondegenerate concept class, Hanneke et al. 2023) . A concept class H P Y X is called nondegenerate if there exist h 1 , h 2 P H and x 0 , x 1 P X such that h 1 px 0 q " h 2 px 0 q and h 1 px 1 q ‰ h 2 px 1 q. H is called degenerate if it is not nondegenerate.Our main result on the multiclass PAC sample complexity is as follows.Theorem 1.9 (Partial summary of Theorem 2.5 and 2.11). For any nondegenerate concept class H Ď Y X with dimpHq " d and any pε, δq P p0, 1q 2 , we have Ωppd `logp1{δqq{εq ď M H pε, δq ď Oppd 3{2 logpdq logpd{εq `logp1{δqq{εq.(3)Our upper bound follows from a reduction to list learning and an improved sample complexity for list learning summarized below. We refer readers to Section 2.1 for detailed definitions regarding list learning. Note that if ppH, nq and βpH, nq of some list learner is independent of n, there exists a multiclass learner with error rate linear in 1{n. We leave the establishment of such list learners as Open Question 1.In addition to the above approach, we propose an alternative route toward obtaining the conjectured Θppd `logp1{δqq{εq sample complexity, by directly bounding the average degrees of one-inclusion graphs. In particular, we show in Theorem 3.2 that any H with dimpHq " 1 has M H pε, δq " Θplogp1{δq{εq, which was not previously known. Moreover, we approach the general case via a new technique we call "pivot shifting". Specifically, we obtain the following result, which relies on an assumption on such pivot shifting. The verification of this assumption is left as Open Question 2. Proposition 1.11 (Informal summary of the results in Section 3). Assume that for any finite concept class, there exists a pivot shifting such that the DS dimension of the concept class does not increase after the pivot shifting, then we have M H pε, δq " Θ ppdimpHq `logp1{δqq{εq for any H Ď Y X . 
multiclass learning via list learning: 
 In this section, we prove a reduction from multiclass learning to list learning in Section 2.2. We improve the existing list learners using boosting in Section 2.3. Then, using a boosted list learner and the reduction, we improve the multiclass learning sample complexity upper bound in Section 2.4. We first present some definitions and results of list learning in Section 2.1.In list learning, the menus defined below serve as classifiers in multiclass learning. Charikar and Pabbaraju [2023] that a concept class H is k-list learnabale if and only if d k :" dim k pHq ă 8, and there exists a k-list learner A k which for any P P REpHq, δ P p0, 1q, n P N, and S " P n , satisfies that with probability at least 1 ´δ,EQUATIONFor the expected error rate, the lower bound ε k H pnq " Ω pd k {pknqq has been proved in Charikar and Pabbaraju [2023, Theorem 6 ]. However, a lower bound of the same order on the k-list PAC sample complexity is still missing in the literature. To establish a lower bound, we also need to rule out trivial classes in list learning. In analogy to Definition 1.8, we define k-nondegeneracy as follows. Definition 2.4 (k-nondegenerate concept class). A concept class H P Y X is called k-nondegenerate for k P N if there exist h 1 , . . . , h k`1 P H and x 0 , x 1 P X such that |th j px 0 q : j P rk `1su| " 1 and |th j px 1 q :j P rk `1su| " k `1. H is called k-degenerate if it is not k-nondegenerate.We claim that only one training point is sufficient for the k-list learning of a k-degenerate concept class H. Indeed, H is k-list learnable if |H| ď k. Now, suppose that |H| ě k `1 and is k-degenerate. Upon observing any point px 1 , y 1 q P X ˆY realizable by H, if |th P H : hpx 1 q " y 1 u| ď k, then x Þ Ñ thpxq : h P H, hpx 1 q " y 1 u is a k-menu which always contains the correct label. If |th P H : hpx 1 q " y 1 u| ě k `1, then, for any x P X ztx 1 u, we must have |thpxq : h P H, hpx 1 q " y 1 u| ď k because otherwise H is k-nondegenerate. Then, x Þ Ñ thpxq : h P H, hpx 1 q " y 1 u is a k-list which always contains the correct label. Now, we are ready to present the following lower bound on the k-list PAC sample complexity. Theorem 2.5. For any k P N, k-nondegenerate concept class H Ď Y X with dim k pHq " d k P N, ε P ´0, 1 8pk`1q ¯, and δ P ´0, 1 4pk`1q ¯, we have M k H pε, δq ě pd k ´1q logp2q`4 logp1{δq 16pk`1qε. In particular, when k " 1, for any ε P p0, 1{16q and δ P p0, 1{8q, we have M H pε, δq ě pdimpHq´1q logp2q`4 logp1{δq 32ε .(5)The proof of Theorem 2.5 is presented in Appendix A where we construct hard distributions based on properties of k-pseudo-cubes.We first introduce the theorem that provides a guarantee on PAC sample complexity based on expected error rate, which will be used frequently in our analysis. pnq " O ppβpH, n 1 q `d log ppH, n 1 qq{nq where n 1 :" n ´2tn{3u, and for S " D n , with probability at least 1 ´δ, er D pA 1 red pS, Hqq " O ppβpH, n 1 q `d log ppH, n 1 q `logp1{δqq{nq .The proof of Theorem 2.7 is presented in Appendix C. Note that the order of the error rate upper bound of the constructed multiclass learner is not smaller than that of the original list learner in the above theorem. Thus, the list learner A k of size k P N developed in Charikar and Pabbaraju [2023] cannot lead to an improved error rate of multiclass learning using our current result. The construction of A red from A list is shown in Algorithm 1.Algorithm 1: Multiclass learner A red using a list learner A listInput: List learner A list , concept class H Ď Y X , training sequence S " ppx 1 , y 1 q, . . . , px n , y n qq P pX ˆYq n for n ě 3, test feature x n`1 P X . Output: A label y P Y for the feature x n`1 . n 1 Ð n ´2tn{3u, n 2 Ð tn{3u; S 1 Ð ppx i , y i qq iPrn1s , S 2 Ð ppx i , y i qq n i"n1`1 , x 1 Ð px n1`1 , . . . , x n , x n`1 q; p µ Ð A list pS 1 , Hq, N Ð ř px,yqPS 2 1 yR p µpxq ; H x 1 Ð th| x 1 : h P H, |ti P rn `1szrn 1 s : hpx i q R p µpx i qu| ď N `1u; Sample pI 1 , . . . , I n2 q " Unifpr2n 2 sq n2 ; p h Ð A G pT, H x 1 qwhere T Ð ppI j , y Ij `n1 qq jPrn2s ; return the label p hp2n 2 `1q.In step 6 of Algorithm 1, A G is a multiclass learner defined in Proposition H.5 in the appendix. Moreover, we prove in Proposition H.5 that for any D P REpHq, n P N, δ P p0, 1q, and S " D n , with probability at least 1 ´δ, we haveer D pA G pS, Hqq " O ppdim G pHq `logp1{δqq {nqwhere dim G pHq is the graph dimension [Natarajan and Tadepalli, 1988] of H (see Definition H.1 in the appendix). The above bound for classes of finite graph dimensions is also novel in the literature.We briefly comment on the analysis of Algorithm 1. We first apply the list learner to the first third of the training samples to obtain the menu p µ. Then, we count the number of errors (N ) made by p µ in the last two thirds samples. Then, we consider H x 1 which is a subset of H| x 1 such that the number of errors on x 1 is bounded by N `1. We show in Lemma H.9 that dim G pH x 1 q is well controlled. However, as we do not observe the label of the test point, we can only consider resampling from elements in S 2 as the new training sequence fed to A G together with the concept class H x 1 . Thus, there still exist great challenges of upper bounding the error probability for the test point that will never be sampled. We need to emphasize that the standard leave-one-out argument [Brukhim et al., 2022, Fact 14 ] cannot be directly applied as the definition of N that determines H x 1 only depends on S 2 but not the test point pX n`1 , Y n`1 q. We tackle this challenge by proving that some permutation of the error event together with the constraint on correctness of p µ on the last two points in x 1 when leaving the last element (i.e., the test point) out is a subset of the error event when leaving the previous element (i.e., the point in S 2 ) out. The details of the proof is presented in Appendix C.We now build a list learner whose invocation to Theorem 2.7 yields the upper bound in Theorem 1.9. Brukhim et al. [2022, Lemma 39] proposed a list sample compression scheme of size r " Opd 3{2 logpnqq for concept classes of DS dimension d and sample size n. One can show that its error rate is O ppr logpn{rq `logp1{δqq{nq using standard techniques for sample compression schemes [David et al., 2016] , which however brings the extra log factor logpn{rq. Recently, da Cunha et al. [2024] proposed stable randomized sample compression schemes for binary classification whose generalization does not induce the extra log factor in n and used this framework to analyze a subsampling-based boosting algorithm for weak learners. Motivated by its success, we extend their boosting algorithm [da Cunha et al., 2024, Algorithm 1] for multilclass list learners in Algorithm 2. Before presenting the algorithm, we first need to define the majority vote of menus. For K P N menus µ 1 , . . . , µ K each of size p, we define their majority vote to be µ " Majpµ 1 , . . . , µ k q with µpxq " Majpµ 1 , . . . , µ k qpxq :" ty P Y : |tk P rKs : y P µ k pxqu| ą K{2u , @x P X .Note that µ has size 2p ´1. For p " 1, the above definition recovers the majority vote of classifiers.Algorithm 2: Sampled boosting A boost of a list learner A list Input: List learner A list , concept class H Ď Y X , training sequence S " tpx 1 , y 1 q, . . . , px n , y n qu P pX ˆYq n , γ P p0, 1{2q, ν P p0, γ{18s, δ P p0, 1q. Output: Menu µ. for i " 1, . . . , n doD 1 ptpx i , y i quq Ð 1{n; α Ð 1 2 log pp1 `γq{p1 ´γqq, m Ð M A list ,H p1{2 ´γ, νq, K Ð r4 logpn{δq{γs; for k " 1, . . . , K do Draw m samples S k " D m k ; µ k Ð A list pS k , Hq; for i " 1, . . . , n do D k`1 ptpx i , y i quq Ð D k ptpx i , y i quq exp `´α `21 yiPµ k pxiq ´1˘˘; D k`1 Ð D k`1 { `řn i"1 D k ptpx i , y i quq exp `´α `21 yiPµ k pxiq ´1˘˘˘; return µ Ð Maj `pµ k q kPrKs ˘.Here, γ and ν are fixed constants, enabling us to invoke weak list learners (of constant error and confidence levels) to Algorithm 2. Next, we upper bound the error rate of the boosted list learner. Theorem 2.8. Assume that A list is a list learner with M A list ,H p1{2 ´γ, νq ă 8 for some γ P p0, 1{2q and ν P p0, γ{18s. Then, for any D P REpHq, n P N, and δ ą 0, sampling S " D n , with probability at least 1 ´δ, the menu µ produced by A boost using A list in Algorithm 2 satisfies thater D pµq " O ´MA list ,H p1{2´γ,νq logpn{δq γn ¯.The proof of Theorem 2.8 is a generalization of the proof of da Cunha et al. [2024, Theorem 1.1] and is presented in Appendix D together with the proofs of other results in this section. Since multiclass learners are list learners of size 1, we can also boost multiclass learners using Algorithm 2. For instance, invoking the multiclass learner in Brukhim et al. [2022, Theorem 1] to Algorithm 2 and applying Theorem 2.6, we achieve the following sample complexity in multiclass learning.Corollary 2.9. There exists a multiclass learnerA with ε A,H pnq " O `d3{2 log 2 pdq logpnq n ˘and M A,H pε, δq " O `d3{2 log 2 pdq logpd{εq`logp1{δqε ˘for any n P N, pε, δq P p0, 1q 2 , andH Ď Y X with dimpHq " d.There is an extra logpdq factor in the above upper bound compared to that in Theorem 1.9, which explains the reason of routing through list learning with our reduction in Theorem 2.7: the list sample compression scheme in Brukhim et al. [2022] saves a logpdq factor compared to their sample compression scheme. Therefore, we invoke their list sample compression scheme as A list to Algorithm 2 and build a list learner whose error rate depends on only one log factor in both n and d. Theorem 2.10. There exists a list learner A L which for any H Ď Y X with dimpHq " d and sample size n P N outputs a menu of size O `pe ? dq? d logpnq ˘with ε A L ,H pnq " O `d3{2 logpdq logpnq n ˘.Applying the list learner A L in Theorem 2.10 to our reduction, Theorem 2.7 immediately implies the following result. Theorem 2.11. There exists a multiclass learner A multi such that for any H Ď Y X of DS dimension d, D P REpHq, δ P p0, 1q, n ě d `1, and S " D n , with probability at least 1 ´δ, we haveEQUATIONwhich implies thatEQUATIONFurthermore, if there exists a list learner A goodlist of size f 1 pdq and expected error rate ε A goodlist ,H pnq ď f 2 pdq{n for some functions f 1 : N Ñ N and f 2 : N Ñ r0, 8q, then, there exists a multiclass learner A lin such that M A lin ,H pε, δq " O ppd logpf 1 pdqq `f2 pdq `logp1{δqq{εq , @ε, δ P p0, 1q.The proof of Theorem 2.11 follows directly from Theorem 2.7 and Theorem 2.10 and is provided in Appendix E. Moreover, observing that dim k pHq ě dim k 1 pHq for k ă k 1 , our requirement on A goodlist does not violate the lower bound in Charikar and Pabbaraju [2023, Theorem 6] .Compared to the upper bound (1) by Brukhim et al. [2022] , (7) improves the dependence of the error rate on the sample size n from O `logplogpnqq log 2 pnq{n ˘to O plogpnq{nq, which steps further towards the goal of Op1{nq expected error rate (treating the DS dimension as a constant). Combining ( 5) and ( 8), we arrive at (3) where the gap has been improved to the factor ? d logpdq logpd{εq. However, we are not aware of any existing list learner satisfying the requirements of A goodlist in Theorem 2.11. Thus, we leave the construction of A goodlist as an open question.Open Question 1. Does there exist a list learner such that given a concept class H Ď Y X , its size is f 1 pdimpHqq and its expected error rate is ε A list ,H pnq " f 2 pdimpHqq{n for some functions f 1 : N Ñ N and f 2 : N Ñ r0, 8q?Ideally, we would expect a list learner with size OpdimpHqq and expected error rate OpdimpHq{nq as it immediately implies an upper bound M H pε, δq " OppdimpHq logpdimpHqq `logp1{δqq{εq which matches the lower bound in (5) up to the factor logpdimpHqq. 
density, ds dimension, and pivot shifting: 
 We now introduce an alternative route toward proving the optimal sample complexity of multiclass PAC learning: bounding the density µ H : N Ñ r0, 8q (Definition 1.7) of concept classes H. The following proposition summarizes existing results that illustrate the role of density in multiclass learning. Proposition 3.1 (Daniely and Shalev-Shwartz 2014 , Charikar and Pabbaraju 2023 , Aden-Ali et al. 2023) . For any H Ď Y X and n P N, we haveµ H pnq{p2enq ď ε H ď ε H,trans ď µ H pnq{n.(10)Assume that µ H pnq ď f pdimpHqq for some function f : N Ñ r0, 8q and all n P N. Haussler et al. [1994] proved that µ H ď 2dimpHq (for binary classes, the DS dimension is the VC dimension), which also motivates the above conjecture. In this paper, we confirm the above conjecture for concept classes of DS dimension 1. Theorem 3.2. For any H Ď Y X with dimpHq " 1, we have µ H pnq ď 2, @n P N. Thus, M H pε, δq " Θ plogp1{δq{εq for any positive ε, δ P Op1q and any H with dimpHq " 1.The above theorem follows from the following fact we prove for one-inclusion graphs of DS dimension 1 concept classes. The proofs of Theorem 3.2 and Proposition 3.3 are presented in Appendix F. Proposition 3.3. For any n P N and V n Ď Y n with |V n | ă 8 and dimpV n q " 1, there exists no cycle (see Definition 3.4) in the one-inclusion graph GpV n q (see Definition 1.5). Definition 3.4 (Cycle in finite hypergraph). A cycle of length m P Nzt1u in a finite hyergraph G " pV, Eq consists of pairwise different vertices v 0 , . . . , v m´1 P V and pairwise different edges e 0 , . . . , e m´1 P E such that v j , v pj`1q mod m P e j for all 0 ď j ď m ´1.We prove Proposition 3.3 by contradiction and analyzing different cases of the cycle. However, it is hard to extend such result to classes of higher DS dimensions. For general concept classes, motivated by the proof for binary classes [Haussler et al., 1994, Lemma 2 .4], we also consider proving by induction on the size of the sequence the class projects to. Though the analysis for binary classes does not apply to general concept classes, we discover that the analysis in the induction step proceeds seamlessly for some special concept classes where a common label which we call a "pivot" exists for each edge in the last dimension of size greater than 1 in its one-inclusion graph. Before summarizing this result in Lemma 3.6 below, we first introduce the definition of a "pivot" formally. Definition 3.5 (Pivot of finite concept class). For any n P Nzt1u and V n Ď Y n , we definePpV n q :" Y yPY Y y1 PYztyu ␣ py 1 , . . . , y n´1 q P Y n´1 : py 1 , . . . , y n´1 , yq, py 1 , . . . , y n´1 , y 1 q P V n ( .Then, a P Y is said to be a pivot of V n if py 1 , . . . , y n´1 , aq P V n for any py 1 , . . . , y n´1 q P PpV n q.We emphasize that when PpV n q " H, every a P Y is a pivot of V n .Then, we can present Lemma 3.6 whose proof is provided in Appendix G. Though it only works for special classes, Lemma 3.6 can serve as a building block in the induction step for the proof of avgoutdegpGpHqq ď dimpHq for finite H Ď Y nPN Y n . Moreover, the base case n " d `1 has been verified in Brukhim et al. [2022, Lemma 13 ]. Consequently, it suffices to extend the induction step for concept classes without a pivot. With Lemma 3.6, it is natural to consider modifying the concept class to create a pivot for it while at the same time preserving the DS dimension of the modified class nonincreasing. The technique used here is similar to shifting [Haussler, 1995 , Brukhim et al., 2022] , though we do not shift the whole edge "downwards" but only shift the last label in some vertex of the edge to a candidate pivot. The difference is necessary, as it has already been shown that the DS dimension of a concept class can increase after the standard shifting [Brukhim et al., 2022, Example 19 ]. Thus, we name the technique used here "pivot shifting". Definition 3.7 (Pivot shifting). For any n P Nzt1u, a P Y, and V n Ď Y n with |V n | ă 8, we define P a pV n q :" Y yPY ␣ py 1 , . . . , y n´1 q P Y n´1 : py 1 , . . . , y n´1 , yq P V n , py 1 , . . . , y n´1 , aq R V n ( .For any y " py 1 , . . . , y n´1 q P P a pV n q and the edge pe n,y , nq in GpV n q, we define the set L y :" ty P Y : py 1 , . . . , y n´1 , yq P pe n,y , nqu.A mapping γ : P a pV n q Ñ Y is called a pivot shifting on V n to a if γpyq P L y for all y P P a pV n q.Let Γ a,Vn denote the set of all pivot shifting on V n to a. For any γ P Γ a,Vn , we define V γ n :" pV n z tpy, γpyqq : y P P a pV n quq Y tpy, aq : y P P a pV n qu ; i.e., V n,γ is obtained by replacing the label γpyq in py, γpyqq with a for all y P P a pV n q.We prove that the average out-degree does not decrease after pivot shiftings in the following lemma. Lemma 3.8. For any a P Y, V Ď Y 8n"2 Y n with |V | ă 8, and γ P Γ a,V , we have avgoutdegpGpV γ qq ě avgoutdegpGpV qq.The proof is presented in Appendix G. A key observation for the proof is that by definition, only edges of sizes greater than one contribute to the average out-degree. However, we are not able to show that the DS dimension does not increase after some pivot shifting, which we leave as an open question. Thus, whether pivot shifting is applicable to upper bounding density with DS dimension remains open. Open Question 2. For any d P N and any V Ď Y 8 n"d`2 Y n with |V | ă 8 and dimpV q " d, are there some a P Y and γ P Γ a,V such that dimpV γ q ď d?Nevertheless, we have taken a further and specific step toward the verification of the conjecture that µ H ď 2dimpHq: a positive resolution of the above question would lead to the conclusion that µ H ď 2dimpHq by Lemma 3.6, Lemma 3.8, and Brukhim et al. [2022, Lemma 13] .Before proving Theorem 2.5, we first introduce two lemmas regarding k-pseudo-cubes that will be used in the proof. Lemma A.1. For any positive integers k, d, any label class Y, any k-pseudo-cube H Ď Y d of dimension d, any j P rds, and any label y P Y, define H j y :" th P H : hpjq " yu. Then, we have|H j y | ď |H| k `1 .Proof. When d " 1, the result follows trivially from the definition of k-pseudo-cubes. We prove the result for d ě 2 by contradiction. Suppose on the contrary that there exist some j P rds and y P Y such that|H j y | ą |H| k`1 .The definition of pseudo-cubes implies that |H| ě k `1. Then, there exist h, h 1 P H j y with h ‰ h 1 . Let tf 1 , . . . , f k u and tf 1 1 , . . . , f 1 k u denote the set of j-neighbors of h and h 1 in H respectively. Since h ‰ h 1 and hpjq " y " h 1 pjq, there exists some j 1 P rdsztju such that hpj 1 q ‰ h 1 pj 1 q. It follows that f i pj 1 q " hpj 1 q ‰ h 1 pj 1 q " f 1 l pj 1 q and thus f i ‰ f 1 l for any i, l P rks. Then, we have|th P H : hpjq ‰ yu| ě k|H j y | ą k|H| k `1and|H| " |th P H : hpjq ‰ yu| `|H j y | ą |H|,which is a contradiction. Thus, we must have|H j y | ď |H| k`1 . Lemma A.2.For any integer k ě 1, d ě 2, n P rd ´1s, and 1 ď j 1 ă ¨¨¨ă j n ď d, any label class Y, any k-pseudo-cube H Ď Y d of dimension d, and any hypothesis g P H, define J :" pj 1 , . . . , j n q and K " pk 1 , . . . , k d´n q such that 1 ď k 1 ă ¨¨¨ă k d´n ď d and tj 1 , . . . , j n , k 1 , . . . , k d´n u " rds. Then, H g,J :" th| K : h P H, hpj i q " gpj i q, @i P rnsu is a k-pseudo-cube of dimension d ´n.Proof. For any f P H g,J , there exists some h P H such that f " h| K . Then, for any i P rd ´ns, there exists k distinct h 1 , . . . , h k P H such that h m pk i q ‰ hpk i q and h m plq " hplq for all l P rdsztk i u and m P rks. Since k i R tj 1 , . . . , j n u, we have h| J " h m | J " g| J and thus f m :" h m | K P H g,J for all m P rks. Then, we have f piq " hpk i q ‰ h m pk i q " f m piq and f plq " hpk l q " h m pk l q " f m plq for any l P rd ´nsztiu and m P rks, which implies that H g,J is a k-pseudo-cube of dimension d ´n.Proof of Theorem 2.5. Consider an arbitrary k-nondegenerate concept class H Ď Y X for some k P N. Let x 0 , x 1 P X and h 1 , . . . , h k`1 P H witness the k-nondegeneracy as specified in Definition 2.4. For any ε P p0, 1{2pk `1qq and δ P p0, 1q, let I " Bernoullippk `1qεq and J " Unifprk `1sq. Then, for any j P rk `1s, px I , h j px I qq follows the H-realizable distribution P ε,j over X ˆY defined by P ε,j ptpx 0 , h j px 0 qquq " 1 ´pk `1qε and P ε,j ptpx 1 , h j px 1 qquq " pk `1qε. Sample pI 1 , . . . , I n q " Bernoullipεq n independent of pI, Jq and define S " ppx I1 , h J px I1 q, . . . , px In , h J px In qq and S 1 " ppx 0 , h J px 0 q, . . . , px 0 , h J px 0 qq. Then, for any k-list learner A, we havePph J px I q R ApS, Hqpx I q|I 1 " 0, . . . , I n " 0q ěPph J px 1 q R ApS 1 , Hqpx 1 q, I " 1q "PpI " 1qPph J px 1 q R ApS 1 , Hqpx 1 qq "pk `1qεErPph J px 1 q R ApS 1 , Hqpx 1 q|ApS 1 , Hqqs ěε,where the last inequality follows from the facts that h J px 0 q " h 1 px 0 q, |th 1 px 1 q, . . . , h k`1 px 1 qu| " k `1, h J px 1 q " Unifpth 1 px 1 q, . . . , h k`1 px 1 quq. Since J " Unifprk `1sq, there exists j P rk `1s such that Pph j px I q R ApS j , Hqpx I q|I 1 " 0, . . . , I n " 0q "Pph J px I q R ApS, Hqpx I q|J " j, I 1 " 0, . . . , I n " 0q ě ε, where S j :" ppx I1 , h j px I1 qq, . . . , px In , h j px In qqq " P n ε,j is independent of px I , h j px I qq " P ε,j . Since1 2pk`1qε ď 1´pk`1qε pk`1qε ă 1 ´logp1´pk`1qεq for ε P p0, 1{2pk `1qq, if n ď logp1{δq2pk`1qε ă logpδq logp1´pk`1qεq , we have PpI 1 " 0, . . . , I n " 0q " p1 ´pk `1qεq n ą δ.Then, with probability greater than δ, we have er Pε,j pApS j , Hqq ě ε, which implies thatEQUATIONNext, consider an arbitrary concept class H Ď Y X such that dim k pHq " d k P Nzt1u for some k P N. Then, there exist a sequence x :" px 1 , . . . , x d k q P X d k and a k-pseudo-cube H Ď H| x of dimension d k . Denote the elements in H with y 1 " py 1 1 , . . . , y1 d k q, . . . , y |H| " py |H| 1 , . . . , y |H| d k q. For any ε P p0, 1{8pk `1qq, consider the categorical distribution Q ε over rd k s defined by Q ε pt1uq " 1´4pk`1qε and Q ε ptiuq " 4pk`1qε d k´1 for i P rd k szt1u. Let J " Unifpr|H|sq. For any i P rd k szt1u and I " pi 1 , . . . , i m q P prd k sztiuq m with m P rd k ´1s and i 1 ă ¨¨¨ă i m , define I 1 :" pi 1 1 , . . . , i 1d k ´mq such that i 1 1 ă ¨¨¨ă i 1 d k ´m and ti 1 , . . . , i m , i 1 1 , . . . , i 1 d k´mu " rd k s. Then, we have that conditional on pi 1 , y J i1 q, . . . , pi m , y J im q, y J | I 1 follows the uniform distribution over the set H y J ,I which is a k-pseudo-cube by Lemma A.2. Consequently, we can apply Lemma A.1 to conclude that|pH y J ,I q i 1 y | ď |H y J ,I | k `1for any y P Y and i 1 P rd k ´ms, which immediately implies thatEQUATIONfor any distinct v 1 , . . . , v k P Y.Let pI, I 1 , . . . , I n q " Q n`1 ε for n P N be independent of J. Define S :" ppx I1 , y J I1 q, . . . , px In , y J In qq. For any k-list leaner A, by (11), we havePpy J I R ApS, Hqpx I q, I ‰ 1q ěPpy J I R ApS, Hqpx I q, I ‰ 1, I ‰ I 1 , . . . , I ‰ I n q ě d k ÿ i"2Ppy J I R ApS, Hqpx I q, I " i, I 1 ‰ i, . . . , I n ‰ iq" d k ÿ i"2Er1I 1‰i,...,In ‰i Ppy J i R ApS, Hqpx i q, I " i|ApS, Hq, pI 1 , y J I1 q, . . . , pI n , y J In qqs ěd k ÿ i"2 PpI " iq k `1 PpI 1 ‰ i, . . . , I n ‰ iq "4ε ˆ1 ´4pk `1qε d k ´1 ˙n .Since J " Unifpr|H|sq, there exists j " jpA, Hq P r|H|s such thatPpy j I R ApS j , Hqpx I q, I ‰ 1q " Ppy J I R ApS, Hqpx I q, I ‰ 1|J " jq ě 4ε ˆ1 ´4pk `1qε d k ´1 ˙n ,where S j :" ppx I1 , y j I1 q, . . . , px In , y j In qq. Note that if we define the distribution P ε,j over X ˆY by P ε,j ptx 1 , y j 1 uq " 1 ´4pk `1qε and P ε,j ptx i , y j i uq " 4pk `1qε d k ´1 , @i P rd k szt1u, then, we have pS, px I , y j I qq " P n`1 ε,j . For any n ď pd k ´1q logp2q 8pk`1qε ă logp1{2q logp1´4pk`1qε{pd k ´1qq , we have ´1 ´4pk`1qεd k ´1 ¯n ą 1 2 andPpy j I R ApS j , Hqpx I q, I ‰ 1q ą 2ε. Now, we define the algorithm A 1 by A 1 ps, Hqpx 1 q :" ty j 1 u and A 1 ps, Hqpxq :" Aps, Hqpxq, @x P X ztx 1 u for any s P Y 8 m"0 pX ˆYq m . Then, we have ErerP ε,j pA 1 pS j , Hqqs ěPpy j I R A 1 pS j , Hqpx I q, I ‰ 1q "Ppy j I R ApS j , Hqpx I q, I ‰ 1q ą2ε.(12)On the other hand, the definition of A 1 yields that y j 1 P A 1 pS j , px 1 qq and hence er Pε,j pA 1 pS j , Hqq ď P ε,j pX ztx 1 uq " 4pk `1qε.Pper Pε,j pApS j , Hqq ą εq ďEQUATION)Since er Pε,j pA 1 pS j , Hqq ď er Pε,j pApS j , Hqq, the above inequality implies that Pper Pε,j pA 1 pS j , Hqq ą εq ď 1 4pk `1q and therefore ErerP ε,j pA 1 pS j , Hqqs ďε `E " er Pε,j pA 1 pS j , Hqq1 er P ε,j pA 1 pS j ,Hqqąε ı ďε `4pk `1qεPper Pε,j pA 1 pS j , Hq ą εq ď2ε, which contradicts (12). Thus, we can conclude that (13) is false, i.e.,Pper Pε,j pApS j , Hqq ą εq ą 1 4pk `1qfor n ď pd k ´1q logp2q 8pk`1qε . For δ P p0, 1{4pk `1qs, we have Pper Pε,j pApS j , Hqq ą εq ą δ and thusM k H pε, δq ě pd k ´1q logp2q 8pk `1qε .In conclusion, for ε, δ " Op1{kq, we haveM k H pε, δq " Ω ˆdk `logp1{δq kε ˙.B Proof of Theorem 2.6Proof. Consider an algorithm A : pY 8 k"1 pX ˆYq k q ˆ2Y X Ñ Y X which for any hypothesis class H Ď Y X , H-realizable distribution D, and n P N, satisfies thatP pT,pX,Y qq"D n`1 pApT, HqpXq ‰ Y q ď M n n (14)where M n is nondecreasing in the sample size n.For an arbitrary sequence S " ppx 1 , y 1 q, . . . , px n , y n q, px n`1 , y n`1 qq P pX ˆYq n`1 , define S ´i to be the subsequence of S excluding px i , y i q for any i P rn `1s. Let pT m , pX, Y qq " UnifpSq m`1 where m P N, T m P pX ˆYq m and pX, Y q P X ˆY. Moreover, for any i P rn `1s, let T i m " UnifpS ´iq m . Then, for any algorithm A :EQUATION)Note that if S is consistent with H, then UnifpSq is H-realizable.Next, define the algorithm A Maj,m :pY 8 k"1 pX ˆYq k q ˆ2Y X Ñ Y X byA Maj,m pR, Hq :" MajorityppApr, Hqq rPR m q, @R P pX ˆYq n , @n P N.By the definition above, for any permutation R π of R P pX ˆYq n , we haveEQUATIONMoreover, for any i P rn `1s, the above definition yields that 1 AMaj,mpS´i,Hqpxiq‰yi ď1 1 n m |tsPS m ´i:Aps,Hqpxiq‰yiu|ě 1 2 ď 2 n m |ts P S m ´i : Aps, Hqpx i q ‰ y i u| "2PpApT i m , Hqpx i q ‰ y i q. Then, by (15), we have1 n `1 n`1 ÿ i"1 1 AMaj,mpS´i,Hqpxiq‰yi ď 2pn `1q n `1 ´m PpApT m .HqpXq ‰ Y q.Choosing m " tpn `1q{2u and defining A Maj :" A Maj,tpn`1q{2u , for any H-realizable sequence S, by ( 14) and the above results, we have for some function β : 2 Y X ˆN Ñ r0, 8q.n`1 ÿ i"1 1 AMajpS´i,Hqpxiq‰yi ď 2pn `1q 2 M tpn`1q{2uFor n 1 , n 2 P N, let pS 1 , S 2 , pX, Y qq " D n1`2n2`1 where S 1 P pX ˆYq n1 , S 2 P pX ˆYq 2n2 , and pX, Y q P X ˆY. Let p µ " A list pS 1 , Hq. According to the property of A list , the size of p µ is ppn 1 q and we have PpY R p µpXqq ď βpH, n 1 q n 1 .For notational convenience, define S 1 :" pS 2 , pX, Y qq, S 2 :" pS 1 , S 2 , pX, Y qq, and enumerate the elements of S 1 as ppX 1 , Y 1 q, . . . , pX 2n2`1 , Y 2n2`1 qq where pX 2n2`1 , Y 2n2`1 q denotes pX, Y q. We now define N :" ÿ iPr2n2s 1 YiR p µpXiq and H S 1 :"H pX1,...,X2n 2 `1 q, p µ,N " ! h| pX1,...,X2n 2 `1q : h P H, |ti P r2n 2 `1s : hpX i q R p µpX i qu| ď N `1) .It follows from the property of p µ and Lemma H.9 that ErN s "2n 2 βpH, n 1 q n 1 (18)and, conditional on S 1 , dim G pH S 1 q ď p2 log 2 e `4qp5d log 2 pppn 1 qq `2N `2q.Sample pI, Iq " Unifpr2n 2 `1sq n2`1 independent of S 2 where I " pI 1 , . . . , I n2 q P r2n 2 `1s n2 and I P r2n 2 `1s. Then, we define the sequence T pS 1 , Iq :" ppI 1 , Y I1 q, . . . , pI n2 , Y In 2 qq and the classifierp h S 1 ,I :" A G `T pS 1 , Iq, H S 1for any i P r2n 2 `1s, where A G is the algorithm specified in Proposition H.5. Since conditional on S 2 , the distribution of each element in T pS 1 , Iq is H S 1 -realizable, by Corollary H.6, there exists some constant C 1 ą 0 such thatEQUATION)for some constant C 1 , C 2 , C 3 ą 0.For I 1 " pI 1 1 , . . . , I 1 n2 q " Unifpr2n 2 sq n2 independent of all other random variables, define T i pS 1 , I 1 q :" ppρ i pI 1 1 q, Y ρipI 1 1 q q, . . . , pρ i pI 1 n2 q, Y ρipI 1 n 2 q qq where ρ i : r2n 2 s Ñ r2n 2 `1sztiu, k Þ Ñ k1 kăi `pk `1q1 kěi for all i P r2n 2 `1s. Consider the classifier r h S 1 ,I 1 ,i :" A G pT i pS 1 , I 1 q, H S 1 q for each i P r2n 2 `1s. Since Y i is not used in the construction of r h S 1 ,I 1 ,i , we can also denote r h S 1 ,I 1 ,i as r h S 1 ´i,Xi,I 1 ,i , where S 1 ´i :" ppX 1 , Y 1 q, . . . , pX i´1 , Y i´1 q, pX i`1 , Y i`1 q, . . . , pX 2n2`1 , Y 2n2`1 qq. Thus, treating S :" pS 1 , S 2 q " D n1`2n2 as the training sample, we can define the classifier p h S P Y X by p h S pxq :" r h S 2 ,x,I 1 ,2n2`1 p2n 2 `1q, where we emphasize that the RHS depends on S 1 through the construction of p µ. Then, recalling that pX, Y q " D is independent of S, our task is to upper bound the expectated error rate of p h S :P ´p h S pXq ‰ Y ¯.We first relate p h S 1 ,I to r h S 1 ,I 1 ,i for i P r2n 2 `1s:Pp p h S 1 ,I pIq ‰ Y I |S 2 q ě 1 2n 2 `1 2n2`1 ÿ i"1 E " 1 iRI 1 p h S 1 ,I piq‰Yi |S 2 ı " 1 2n 2 `1 2n2`1 ÿ i"1 Ppi R IqE " 1 p h S 1 ,I piq‰Yi |S 2 , i R I ı ě 1 2p2n 2 `1q 2n2`1 ÿ i"1 E " 1 r h S 1 ,I 1 ,i piq‰Yi |S 2 ı , which implies that Pp p h S 1 ,I pIq ‰ Y I |S 1 q ě 1 2p2n 2 `1q 2n2`1 ÿ i"1 E " 1 r h S 1 ,I 1 ,i piq‰Yi |S 1 ı " 1 2p2n 2 `1q 2n2`1 ÿ i"1 E " E " 1 r h S 1 ,I 1 ,i piq‰Yi |S 1 , I 1 ı ˇˇS 1 ı .Conditional on I 1 and S 1 , for any i P r2n 2 `1s and any sequence s P pX ˆYq 2n2`1 , we let r h s,I 1 ,i denote the classifier when replacing S 1 with s in r h S 1 ,I 1 ,i , i.e., r h s,I 1 ,i " A G pT i ps, I 1 q, H s q. For any i P r2n 2 `1s, define the setB i :" ! s " ppx 1 , y 1 q, . . . , px 2n2`1 , y 2n2`1 qq P pX ˆYq 2n2`1 : r h s,I 1 ,i piq ‰ y i )and the permutationπ i : pX ˆYq 2n2`1 Ñ pX ˆYq 2n2`1 , pz 1 , . . . , z 2n2`1 q Þ Ñ pz 1 , . . . , z i´1 , z 2n2`1 , z i , . . . , z 2n2 q.We also define the set B :" ! s " ppx 1 , y 1 q, . . . , px 2n2`1 , y 2n2`1 qq P pX ˆYq 2n2`1 : y 2n2 P p µpx 2n2 q, y 2n2`1 P p µpx 2n2`1 q, and r h s,I 1 ,2n2`1 p2n 2 `1q ‰ y 2n2`1) .We would like to show that π i pBq Ď B i for all i P r2n 2 s.For any s " ppx 1 , y 1 q, . . . , px 2n2`1 , y 2n2`1 qq P B, we let px i j , y i j q P X ˆY denote the j-th element of π i psq for each j P r2n 2 `1s. By the definition of π i and T i , we have T 2n2`1 ps, I 1 q " ppI 1 1 , y I 1 1 q, . . . , pI 1 n2 , y I 1 n 2 qq and T i pπ i psq, I 1 q " ppρ i pI 1 1 q, y I 1 1 q, . . . , pρ i pI 1 n2 q, y I 1 n 2 qq.Definen s :" ÿ jPr2n2s 1 yj R p µpxj q .Since y 2n2 P p µpx 2n2 q and y 2n2`1 P p µpx 2n2`1 q, we haven π i psq :" ÿ jPr2n2s 1 y i j R p µpx i j q " ÿ jPr2n2`1szt2n2u1 yj R p µpxj q " n s and therefore,H π i psq "H px i 1 ,...,x i 2n 2 `1 q, p µ,n π i psq "H px i 1 ,...,x i 2n 2 `1q, p µ,ns " ! h| px1,...,xi´1,x2n 2 `1,xi,...,x2n 2 q : h P H, |tj P r2n 2 `1s : hpx j q R p µpx j qu| ď n s `1)" tκ i phq : h P H s uwhere for any h P Y 2n2`1 , κ i phq P Y 2n2`1 is defined by κ i phqpjq :" hpρ ´1 i pjqq1 j‰i `hp2n 2 `1q1 j"i , @j P r2n 2 `1s, i.e., hpjq " κ i phqpρ i piqq for j P r2n 2 s and hp2n 2 `1q " κ i phqpiq. Note that κ i is a bijection from H s to H π i psq . Thus, for any h P H π i psq , we have hpρ i pI 1 j qq " κ ´1 i phqpI 1 j q, @j P rn 2 s, and hpiq " κ ´1 i phqp2n 2 `1q. Similarly, for any h P H s , we have hpI 1 j q " κ i phqpρ i pI 1 j qq, @j P rn 2 s, and hp2n 2 `1q " κ i phqpiq. Given the above analysis, we have r h s,I 1 ,2n2`1 p2n 2 `1q "A G pT 2n2`1 ps, I 1 q, H s qp2n 2 `1q "A G pT i pπ i psq, I 1 q, H π i psq qpiq " r h π i psq,I 1 ,i piq, which immediately implies that r h π i psq,I 1 ,i piq " r h s,I 1 ,2n2`1 p2n 2 `1q ‰ y 2n2`1 " y i i and thus π i psq P B i . Since i P r2n 2 s and s P B is arbitrary, we have π i pBq Ď B i for any i P r2n 2 s. Then, conditional on I 1 and S 1 , we haveD 2n2`1 pB i q ě D 2n2`1 pπ i pBqq " D 2n2`1 pBq Since B Ď B 2n2`1 holds trivially, we have Pp p h S 1 ,I pIq ‰ Y I |S 1 q ě 1 2p2n 2 `1q 2n2`1 ÿ i"1 E " E " 1 r h S 1 ,I 1 ,i piq‰Yi |S 1 , I 1 ı ˇˇS 1 ı ě 1 2 E " 1 Y2n 2 P p µpX2n 2 q 1 Y2n 2 `1 P p µpX2n 2 `1q 1 r h S 1 ,I 1 ,2n 2 `1 p2n2`1q‰Y2n 2 `1 ˇˇS 1 ı .Taking expectation on both sides and applying ( 18) and ( 19), we haveC 1 d log ppn 1 q `2C 2 βpH, n 1 qn 2 {n 1 `C3 n 2 " C 1 d log ppn 1 q `C2E rN s `C3 n 2 ěPp p h S 1 ,I pIq ‰ Y I q ě 1 2 E " 1 Y2n 2 P p µpX2n 2 q 1 Y2n 2 `1P p µpX2n 2 `1q 1 r h S 1 ,I 1 ,2n 2 `1 p2n2`1q‰Y2n 2 `1 ı which leads to P ´p h S pXq ‰ Y "P ´r h S 1 ,I 1 ,2n2`1 p2n 2 `1q ‰ Y 2n2`1 ďE " 1 ´1Y2n 2 P p µpX2n 2 q 1 Y2n 2 `1P p µpX2n 2 `1q ı `E " 1 Y2n 2 P p µpX2n 2 q 1 Y2n 2 `1 P p µpX2n 2 `1q 1 r h S 1 ,I 1 ,2n 2 `1 p2n2`1q‰Y2n 2 `1 ı ďP pY 2n2 R p µpX 2n2 qq `P pY 2n2`1 R p µpX 2n2`1 qq `2pC 1 d log ppn 1 q `2C 2 βpH, n 1 qn 2 {n 1 `C3 q n 2 ď 2pβpH, n 1 qn 2 {n 1 `C1 d log ppn 1 q `2C 2 βpH, n 1 qn 2 {n 1 `C3 q n 2 .Now, for any n P N such that n ě 3, setting n 1 " n ´2tn{3u, n 2 " tn{3u, pS, pX, Y qq " D n`1 with S P pX ˆYq n and pX, Y q P X ˆY, we haveP ´p h S pXq ‰ Y ¯" O ˆβpH, n 1 q `d log ppn 1 q n ˙.Then, when βpH, nq and ppnq are nondecreasing in n, by Theorem 2.6, there exists a learner A 1 such that for any n ě 4 and δ P p0, 1q, with probability at least 1 ´δ over S " D n , we haveer D pA 1 pS, Hq " O ˆβpH, n 1 q `d log ppn 1 q `logp1{δq n ˙.In this section, we provide the proofs of Theorem 2.8, Corollary 2.9, and Theorem 2.10 in Section 2.3.Proof of Theorem 2.8. Assume that A list satisfies that M A list ,H p1{2 ´γ, νq ă 8 for some γ P p0, 1{2q and ν P p0, γ{18s. Define the random variable J k :" 1 er D k pµ k qą1{2´γ for any k P rKs.ErJks " PpJ k " 1q ď ν.Define the event E :"! ř K k"1 J k ě 2νK). By the multiplicative Chernoff bound, we havePpEq " P ˜K ÿ k"1 J k ě 2νK ¸ď e ´νK{3 ď δ as K ě 3 logp1{δq ν . Define Z k :" ř n i"1 D k ptpx i , y i quq exp `´α `21 yiPµ k pxiq´1˘˘f or all k P rKs. Since D K`1 is a probability distribution over S, we haveEQUATION)For any k P rKs, we haveZ k " n ÿ i"1 D k ptpx i , y i quq exp `´α `21 yiPµ k pxiq ´1˘" ÿ iPrns:yiPµ k pxiq D k ptpx i , y i quqe ´α `ÿ iPrns:yiRµ k pxiq D k ptpx i , y i quqe α "p1 ´er D k pµ k qqe ´α `er D k pµ k qe α " er D k pµ k qpe α ´e´α q `e´α .If J k " 0, we haveZ k ď γe α `p1 ´γqe ´α " a 1 ´γ2 . If J k " 1, we have Z k ď e α " c 1 `γ 1{2 ´γ{2 ď a 1 `4γ.Then, under the event E c , we can upper boundK ź k"1 Z k ďp1 ´γ2 q p1{2´νqK p1 `4γq νK ď exp ´´γK ´γ 2 ´pγ `4qν ¯ď exp ˆ´γK 4 ˙ď δ n .where the second last inequality follows from ν ď γ 18 ď γ 4pγ`4q and the last inequality follows from K ě 4 logpn{δq γ . By (20) and the above inequality, we have that on E c ,n ÿ i"1 exp ˜´α K ÿ k"1 `21 yiPµ k pxiq ´1˘¸ď δ,which implies that exp ´´α ř K k"1 `21 yiPµ k pxiq ´1˘¯ď δ for all i P rns. It follows thatexpp´f px i , y i qq ď δ 1{αK for f px, yq :" 1 K ř K k"1 `21 yPµ k pxq´1˘, @px, yq P X ˆY. Thus, we havef px i , y i q ě logp1{δq αK " 2 logp1{δqlog ´1{2`γ 1{2´γ ¯r4 logpn{δq{γs ą 0, @i P rns.Since by definition, f px, yq ą 0 ô y P µpxq, @px, yq P X ˆY, we can conclude that on E c , y i P µpx i q, @i P rns, i.e., with probability at least 1 ´δ, y i P µpx i q for all i P rns. Moreover, by da Cunha et al. [2024, Lemma 3.3 ], the randomized compression scheme S Þ Ñ pS 1 , . . . , S K q is stable. Thus, we can apply da Cunha et al. [2024, Theorem 1.2] with compression size s n " mK " O ´MA list ,H p1{2´γ,νq logpn{δq γ ¯to conclude the proof.For the proofs of Corollary 2.9 and Theorem 2.10, we will need the following Lemma. Lemma D.1. If x ą 0 satisfies x ď a logpx{aq `b for some a, b ą 0, then, we have x ď 2a `2b.Proof. Define f pxq :" x ´a logpx{aq ´b for x ą 0. Then, we have f 1 pxq " x´a x , which implies that f decreases with x for x P p0, aq and increases with x for x ą a. Since 2a `2b ą a, it suffices to prove that f p2a `2bq ě 0. Indeed, f p2a `2bq " p2 ´log 2qa `b ´a logppa `bq{aq ą a ppa `bq{a ´logppa `bq{aqq ě 0.Proof of Corollary 2.9. By Brukhim et al. [2022, Theorem 36 ] (choosing t " r ? ds), there exists an n Ñ r sample compression scheme A M for any H Ď Y X of DS dimension dimpHq " d ă 8 where r " Oppd 3{2 `d logppqq logpnqq with p " Oppe ? dqEQUATIONThen, by David et al. [2016, Theorem 3.1] , there exists a universal constant C ą 0 such that for any D P REpHq, δ P p0, 1q, n P N large enough, and S " D n , letting h S :" A M pS, Hq denote the output classifier of the above n Ñ r sample compression scheme A M , we have that er D ph S q ď Cpr logpn{rq `logp1{δqq n with probability at least 1 ´δ. Thus, for any ε P p0, 1q, ifn ě Cr ε logpn{rq `C logp1{δq ε " Cr ε log ˆn Cr{ε ˙`Cr ε log ˆC ε ˙`C logp1{δq ε ,we have er D ph S q ď ε with probability at least 1 ´δ. By Lemma D.1, it suffices to requiren ě 2Cr ε log ˆCe ε ˙`2C logp1{δq ε " 2C ε ˆr log ˆCe ε ˙`log ˆ1 δ ˙˙.Applying the upper bound of r in ( 21), it suffices to requiren ě C 1 ˆpd 3{2 `d logppqq logp1{εq ε logpnq `logp1{δq ε ḟor some universal constant C 1 ą 0. By Lemma D.1 again, it suffices to require n ě 2C 1 pd 3{2 `d logppqq logp1{εq ε log ˆeC 1 pd 3{2 `d logppqq logp1{εq ε ˙`2C 1 logp1{δq ε .Since logplogp1{εq{εq " logp1{εq `log logp1{εq ď 2 logp1{εq, it suffices to requiren ě C 2 ˆpd 3{2 `d logppqq logp1{εq ε log ˆd3{2 `d logppq ε ˙`logp1{δq ε ḟor some universal constant C 2 ą 0.Applying the upper bound of p in (21), it suffices to require thatn ě C 3 ˆpd 3{2 logpdq `d log logpnqq logp1{εq ε log ˆd3{2 logpdq `d log logpnq ε ˙`logp1{δq εḟor some universal constant C 3 ą 0. For ε " 1{6 and δ " 1{54, we require thatn ě C 1 pd 3{2 logpdq `d log logpnqq log ´d3{2 logpdq `d log logpnq for some universal constant C 1 ą 0. If C 1 p ? 2C 1 `1qd 3{2 logpdq log `p? 2C 1 `1qd 3{2 logpdq ˘ď n ď e d ? 2C 1 d , we have ? 2C 1 d 3{2 logpdq ě d log logpnq and C 1 pd 3{2 logpdq `d log logpnqq logpd 3{2 logpdq `d log logpnqq ďC 1 p a 2C 1 `1qd 3{2 logpdq log ´pa 2C 1 `1qd 3{2 logpdq ¯ď n. If n ą e d ? 2C 1 d, we have logplogpnqq ą ? 2C 1 d logpdq, logplogpnqq 2 ą 2C 1 d log 2 pdq ě 2C 1 pd logp2dq `dq, andC 1 pd 3{2 logpdq `d log logpnqq logpd 3{2 logpdq `d log logpnqq ď2C 1 d logplogpnqq logp2d log logpnqq "2C 1 d logp2dq logplogpnqq `2C 1 d logplogpnqq logplog logpnqq ď logplogpnqq 3 logplog logpnqqq ď n. Therefore, we can conclude that if n ě C 1 p ? 2C 1 `1qd 3{2 logpdq log `p? 2C 1 `1qd 3{2 logpdq ˘"Θpd 3{2 log 2 pdqq, we have Pper D ph S q ą 1{6q ď 1{54, i.e., M A M ,H p1{2 ´1{3, 1{54q " Opd 3{2 log 2 pdqq.Let A B denote the multiclass learner output by A boost in Algorithm 2 using A M as the weak list learner of size 1. Then, by Theorem 2.8, we haveε A B ,H pnq " O ˆd3{2 log 2 pdq logpnq n ˙, @n P N.Next, by Theorem 2.6, there exists a multiclass learner A such that for any D P REpHq, δ P p0, 1q, n P N, and S " D n , with probability at least 1 ´δ, we haveer D pApS, Hqq " O ˆd3{2 log 2 pdq logpnq `logp1{δq n ˙.Setting δ " 1{n and observing that er D P r0, 1s, it follows that ε A,H pnq " O ´d3{2 log 2 pdq logpnq n ¯.Moreover, by Lemma D.1, for any ε P p0, 1q, n ě O ´d3{2 log 2 pdq logpd{εq`logp1{δq ε ¯implies that er D pApS, Hqq ď ε with probability at least 1 ´δ. Thus, we haveM A,H pε, δq " O ˆd3{2 log 2 pdq logpd{εq `logp1{δq ε ˙.Proof of Theorem 2.10. By Brukhim et al. [2022, Theorem 39 ] (choosing t " r ? ds), there exists an n Ñ r list sample compression scheme A list of size p " Oppe ? dqEQUATIONDefine the following loss function for menus µ, ℓpµ, px, yqq :" 1 yRµpxq , @px, yq P X ˆY.Then, we can apply the proof of David et al. [2016, Theorem 3.1] with the loss function ℓ to show that there exists a universal constant C ą 0 such that for any n Ñ r list sample compression scheme A LSC for H, any D P REpHq, δ P p0, 1q, n P N large enough, and S " D n , letting µ S :" A LSC pS, Hq denote the output menu, we have er D pA LSC pS, Hqq " EpX,Y q"D rℓpA LSC pS, Hq, pX, Y qq | Ss ď Cpr logpn{rq `logp1{δqq n with probability at least 1 ´δ. Thus, for any ε P p0, 1q, ifn ě Cr ε logpn{rq `C logp1{δq ε " Cr ε log ˆn Cr{ε ˙`Cr ε log ˆC ε ˙`C logp1{δq ε ,we have er D pA LSC pS, Hqq ď ε with probability at least 1 ´δ. By Lemma D.1, it suffices to requiren ě 2Cr ε log ˆCe ε ˙`2C logp1{δq ε " 2C ε ˆr log ˆCe ε ˙`log ˆ1 δ ˙˙.Since A list is an n Ñ r list sample compression scheme for H with r bounded in (22), The above results imply that in order for Pper D pA list pS, Hqq ą εq ď δ, it suffices to requiren ě C 1 ˆd3{2 logp1{εq ε logpnq `logp1{δq ε ḟor some universal constant C 1 ą 0. By Lemma D.1 again, it suffices to require n ě 2C 1 d 3{2 logp1{εq ε log ˆeC 1 d 3{2 logp1{εq ε ˙`2C 1 logp1{δq ε .Since logplogp1{εq{εq " logp1{εq `log logp1{εq ď 2 logp1{εq, it suffices to require n ě C 2 ˆd3{2 logpd{εq logp1{εq `logp1{δq ε ḟor some universal constant C 2 ą 0, which implies that (9) follows directly from (6) by plugging in ppH, nq " f 1 pdq and βpH, nq " f 2 pdq for d " dimpHq and any n P N.M A list ,H p1{2 ´1{3, 1{54q " O ´d3{2 logpdq ¯. Now,In this section, we present the proof of Proposition 3.3 and Theorem 3.2.Proof of Proposition 3.3. Let E n denote the edge set of the hypergraph GpV n q. Suppose on the contrary that there exists a cycle consisting of pairwise different vertices y 0 , . . . , y m´1 P V n and pairwise different edges e 0 " pe i0,f0 , i 0 q, . . . , e m´1 " pe im´1,fm´1 , i m´1 q P E n for some m P t4, . . . , |V n |u such that y j , y pj`1q mod m P pe ij ,fj , i j q for all 0 ď j ď m ´1. Since the edges are pairwise different, by the definition of E n , we have i j ‰ i pj´1q mod m for all 0 ď j ď m ´1.Define a :" i m´1 P rns, b :" i 0 P rns, p 0 :" y 0 a " y 1 a , p ´1 :" y m´1 a ‰ p 0 , and q 0 :" y 0 b " y m´1 b . Then, we have a ‰ b.For any k P N, we define j k :" maxtj P N 0 : j ď m ´1, y j a " p k´1 u,p k :" y pj k `1q mod m a, and q k :"y j k b " y pj k `1q mod m b because i j k " a. Define K :" mintk P N : p k " p ´1u.By definition, we have p 0 , . . . , p K are pairwise different. There are two cases depending on the values of q 1 , . . . , q K as follows.1. Suppose that there exists some k P rKs such that q k ‰ q 0 . Define l 0 :" 0 and l w :" mintk P rKs : k ą l w´1 , q k ‰ q lw´1 u for all w P N with the convention that inf H " `8. Define v :" maxtw P N : l w ‰ `8u.We have v P rKs and q lw ‰ q lw´1 for all w P rvs. Note that p ´1 " p K " y m´1 a , q 0 " y m´1 b , p l0 " p 0 " y 0 a , q l0 " q 0 " y 0 b , p lw´1 " y j lw ´1`1 a , q lw´1 " y j lw ´1`1 b , p lw´1 " y j lw a , q lw " y j lw b , p lw " y j lw `1 a , q lw " y j lw `1 b for all w P rvs, andp K " p ´1 " y j K `1 a , q K " y j K `1 b .Since it always holds that q K " q lv , there are two cases depending on the value of q lv and q 0 as follows.1.1 Suppose that q lv ‰ q 0 . Then, V n | pa,bq contains the following pseudo-cube of dimension 2: pp l1´1 , q 0 q, pp l1´1 , q l1 q, pp l2´1 , q l1 q, pp l2´1 , q l2 q, . . . pp lv´1 , q lv´1 q, pp lv´1 , q lv q, pp ´1, q lv q, pp ´1, q 0 q, which contradicts the assumption that dimpV n q " 1.1.2 Suppose that q lv " q 0 . Then, V n | pa,bq contains the following pseudo-cube of dimension 2: pp l1´1 , q 0 q, pp l1´1 , q l1 q, pp l2´1 , q l1 q, pp l2´1 , q l2 q, . . . pp lv´1 , q lv´1 q, pp lv´1 , q lv " q 0 q, which contradicts the assumption that dimpV n q " 1.Thus, Case 1 does not exist.2. Suppose that q k " q 0 for all k P rKs. Since y 0 a " p 0 " p j1 a , y 0 b " q 0 " q 1 " p j1 b , and y 0 ‰ y j1 , there must exist some c P rnszta, bu such that y m´1 c " y 1 c " y 0 c ‰ y j1 c " y j1`1 c . We define r 0 :" y 0 c and r k :" y j k c " y j k `1 c for k P rKs. There are two cases depending on the value of r k for k P rKs as follows.2.1 Suppose that there exists some k P rKs such that r k ‰ r 1 . Similar to Case 1, we define l 0 :" 1 and l w :" mintk P rKs : k ą l w´1 , r k ‰ r lw´1 u for w P N. Define v :" maxtw P N : l w ‰ `8u. We have v P rKs and r lw ‰ r lw´1 for all w P rvs. Note that p ´1 " p K " y m´1 a , r 0 " y m´1 c , p 0 " y 0 a , r 0 " y 0 c , p 0 " y j1 a , r l0 " r 1 " y j1 c , p lw´1 " y j lw ´1`1 a , r lw´1 " yj lw ´1`1 c , p lw´1 " y j lw a , r lw " y j lw c ,for all w P rvs, andp K " p ´1 " y j K `1 a , r K " y j K `1 c .Since it always holds that r K " r lv , there are two cases depending on the value of q lv and q 0 as follows. 2.1.1 Suppose that r lv ‰ r 0 . Then, V n | pa,cq contains the following pseudo-cube of dimension 2: pp 0 , r 0 q, pp 0 , r l0 " r 1 q, pp l1´1 , r l0 q, pp l1´1 , q l1 q, . . . pp lv´1 , r lv´1 q, pp lv´1 , r lv q, pp ´1, r lv q, pp ´1, r 0 q, which contradicts the assumption that dimpV n q " 1.V 2 n´1 :" V n´1 zV 1 n´1 . Let E n denote the edge set in GpV n q and E n´1 denote the edge set in GpV n´1 q. For any y P Y, define V n,y :" ␣ py 1 , . . . , y n q P V n : y n " y, py 1 , . . . , y n´1 q P V 1 n´1 ( . For any y P Y, we define E n,y :" tpe i,f , iq P E n : f pnq " y, i P rn ´1suByand let E 1 n,y denote the edge set in GpV n,y q; for any e " pe i,f , iq P E n,y , we define s 1 peq :" |ty P e i,f : y P V n,y u| and s 2 peq :" |ty P e i,f : y R V n,y u|.Then, we have |e| " s 1 peq `s2 peq, E n " pY yPY E n,y q Y E n n , and ÿ We claim that dimpV n,y q ď d ´1 for all y P Yztau. Suppose on the contrary that dimpV n,y q ą d ´1.Since dimpV n q " d, we have dimpV n,y q " d and there exists a set i :" ti 1 , . . For any k P rds and any py i1 , . . . , y i d , yq, py i1 , . . . , y i d , aq P H y,a , since there exists an k-neighbor of py i1 , . . . , y i d q denoted by py i1 , . . . , y 1 i k , . . . , y i d q in H y , py i1 , . . . , y 1 i k , . . . , y i d , y 1 q P H y,a is a kneighbor of py i1 , . . . , y i d , y 1 q in H y,a for y 1 " y, a. Moreover, py i1 , . . . , y i d , yq is a pd `1q-neighbor of py i1 , . . . , y i d , aq in H y,a and vise-versa. Thus, H y,a is a pseudo-cube of dimension d `1, which contradicts the assumption that dimpV n q ď d. Therefore, we must have dimpV n,y q ď d ´1. Then, by the induction hypothesis, we have for any y P Yztau, In this section, we provide the technical lemmas on learning with finite graph dimension and bounding the graph dimension of certain classes. Those lemmas are used in the proof of Theorem 2.7.We first provide the definition of graph dimension. Definition H.1 (Graph dimension). For H Ď Y X and n P N, x " px 1 , . . . , x n q P X n is said to be G-shattered by H is there exists f : rns Ñ Y such that for any i Ď rns, there exists g P H satisfying gpx i q " f piq for all i P i and gpx i q ‰ f piq for all i P rnszi. The graph dimension of H, denoted as dim G pHq is the maximum size of a G-shattered sequence.Define Log : r0, 8q Ñ r1, 8q, x Þ Ñ logpx _ eq where x _ e " maxtx, eu. For any H Ď Y X , n P rdim G pHqs, and x " tx 1 , . . . , x n u Ď X that is G-shattered by H, there exists f : rns Ñ Y such that for any i Ď rns, there exists g P H satisfying gpx i q " f piq for all i P i and gpx i q ‰ f piq for all i P rnszi. Thus, we can defineHpxq :" ! h : rns Ñ t0, 1u, i Þ Ñ 1 r hpxiq"f piq ˇˇr h P H ) .For general n P N, x Ď X with |x| " n, and f P Y n , we defineH f pxq :" ! h : rns Ñ t0, 1u, i Þ Ñ 1 r hpxiq"f piq ˇˇr h P H ) and τ H pnq :" sup xĎX :|x|"n sup f PY n |H f pxq|.Note that τ H pnq " |Hpxq| " 2 n for any n P rdim G pHqs. We have the following lemma.Lemma H.2. For anyH Ď Y X with dim G pHq " d, we have τ H pnq ď ř d i"0 `n i ˘. In particular, if n ě d, then τ H pnq ď pen{dq d .Proof. We first prove by induction on n that for any x " tx 1 , . . . , x n u Ď X and f P Y n ,EQUATIONFor n " 1, it is obviously that |H f pxq| ď 2 and |tx 1 Ď x : H G-shatters x 1 u| ě 1. If |tx 1 Ď x : H G-shatters x 1 u| " 1, then x is not G-shattered by H, which implies that |H f pxq| ď 1. Thus, (24) holds. Now, suppose that (24) holds for any k ă n. Consider s x :" tx 2 , . . . , x n u, Y 0 :" tpy 2 , . . . , y n q P t0, 1u n´1 : p0, y 2 , . . . , y n q P H f pxq or p1, y 2 , . . . , y n q P H f pxqu, and Y 1 :" tpy 2 , . . . , y n q P t0, 1u n´1 : p0, y 2 , . . . , y n q P H f pxq and p1, y 2 , . . . , y n q P H f pxqu.We have |H f pxq| " |Y 0 | `|Y 1 | and |Y 0 | " |H f ps xq|. Then, by the induction hypothesis, we have|Y 0 | ď |tx 1 Ď s x : H G-shatters x 1 u| " |tx 1 Ď x : x 1 R x 1 and H G-shatters x 1 u|.For any y P Y, define H y :" th P H : Dh 1 P H s.t. h| x and h 1 | x differs only at 1 and y P thpx 1 q, h 1 px 1 quu.Then, H y G-shatters x 1 Ď s x implies that H G-shatters x 1 Y tx 1 u. We also have Y 1 " H f p1q f ps xq. It follows from the induction hypothesis that|Y 1 | " |H f p1q f ps xq| ď |tx 1 Ď s x : H f p1q G-shatters x 1 u| ď |tx 1 Ď x : x 1 P x 1 and H G-shatters x 1 u|.In conclusion, we have|H f pxq| "|Y 0 | `|Y 1 | ď|tx 1 Ď x : x 1 R x 1 and H G-shatters x 1 u| `|tx 1 Ď x : x 1 P x 1 and H G-shatters x 1 u| "|tx 1 Ď x : H G-shatters x 1 u|, By the definition of B 1 , we have PppS, T q P B 1 q "E " sup hPH 1 er D phqěε 1 ERphqXS"H 1 |ERphqXT |ąεn{2 ȷ "E " sup hPH 1 er D phqěε 1 ERphqXS"H 1 |ERphqXpS,T q|ąεn{2 ȷ ďE " sup hPH 1 ERphqXS"H 1 |ERphqXpS,T q|ąεn{2ȷ .For any m P N, r " ppx 1 , y 1 q, . . . , px m , y m qq P pX ˆYq m , and h P Y X , we define h r : rms Ñ t0, 1u, i Þ Ñ 1 hpxiq"yi and H r :" th r : h P Hu. Note that H r " H py1,...,ymq ppx 1 , . . . , x m qq, which implies thatEQUATIONFor any k P rms and 1 ď i 1 ă ¨¨¨ă i k ď m, we use r pi1,...,i k q to denote a permutation of r where px j , y j q appears in the i j -th position for all j P rks, specifically, r ti1,...,i k u " px σpiq , y σpiq q iPrns where σpi j q :" j for all j P rks and pσplqq lPrnszti1,...,i k u :" pk `1, . . . , mq. Then, for any i Ď r2ns with |i| " n, we havesup hPH 1 ERphqXS"H 1 |ERphqXpS,T q|ąεn{2 ď ÿ hPH pS,T q 1 hpiq"1, @iPrns 1 ř iPr2ns hpiqăp2´ε{2qn " ÿ hPH pS,T q i 1 hpiq"1, @iPi 1 ř iPr2ns hpiqăp2´ε{2qn .Since pS, T q " D 2n , we also haveE » - ÿ hPH pS,T q i 1 hpiq"1, @iPi 1 ř iPr2ns hpiqăp2´ε{2qn fi fl " E » - ÿ hPH pS,T q 1 hpiq"1, @iPi 1 ř iPr2ns hpiqăp2´ε{2qn fi fl .Thus,EQUATIONwhere (26) follows from Lemma H.7 and (27) follows from (25). Finally, we have proved that EQUATIONCpd `1 `e´1 q n "O ˆd n ˙.Since log z´z`1 ď 0 for z P p0, 1s and g 1 pzq " log z´z`1 for gpzq :" z logpzq`1´z´1 2 p1´zq 2 defined on z P p0, 1s, we have 0 " gp1q ď gpzq ď lim zÑ0`g pzq " 1{2for z P p0, 1s. Thus, we have logpzq `p1 ´zqp1 ´1´z 2 q z ě 0.Plugging in z " 1 ´6{t for t ą 6, we have logp1 ´6{tq `6{tp1 ´3{tq 1 ´6{t ě 0.Then, defining f ptq :" logptq `logpt ´1q `logpt ´2q ´3 logptq `pt ´3q logp1 ´6{tq, t ą 6, we havef 1 ptq " 1 t `1 t ´1 `1 t ´3 t `logp1 ´6{tq `6{tp1 ´3{tq 1 ´6{t ą 0,which implies that f ptq increases with t for t ą 6. Since g 3 p6{p, pq " 6{pp6{p ´1qp6{p ´2q 6 p 3 p1 ´pq 6{p´3 and e f ptq " tpt ´1qpt ´2qt ´3p1 ´6{tq t´3 , we know that g 3 p6{p, pq decreases with p P p0, 1s. Thus, f 3 p6{p, pq ď lim pÑ0`g 3 p6{p, pq " lim tÑ8 tpt ´1qpt ´2q 6 p6{tq 3 p1 ´6{tq t´3 " 36e ´6.Following the above steps, for g 2 px, pq :" xpx ´1q 2 p 2 p1 ´pq x´2 , g 1 px, pq :" xpp1 ´pq x´1 , and g 0 px, pq :" p1 ´pq x , where p P p0, 1s, x ě 6{p, it is easy to prove that for any i " 0, 1, 2, and p P p0, 1s, g i px, pq ď g i p6{p, pq ď lim pÑ0`g i p6{p, pq.Specifically, we have g 2 px, pq ď lim tÑ8 tpt ´1q 2 p6{tq 2 p1 ´6{tq t´2 " 18e ´6, g 1 px, pq ď lim tÑ8 tp6{tqp1 ´6{tq t´1 " 6e ´6, and g 0 px, pq ď lim tÑ8 p1 ´6{tq t " e ´6.Then, we can conclude that PpX ď np{2q ď 3 ÿ i"0 sup pPp0,1s,xě6{p g i px, pq " p36 `18 `6 `1qe ´6 ă 1 2 .For any m P N and j " tj 1 , . . . , j m u Ď rns that is G-shattered by H S,µ,d 1 , there exists f : rms Ñ Y such that for any K Ď rms, there exists g P H S,µ,d 1 satisfying gpj k q " f pkq for all k P K and gpj k q ‰ f pkq for all k P rmszK. Lemma H.11, we have m ď p2 log 2 peq `4qpd 1 `d1 q " p2 log 2 peq `4qp5d log 2 ppq `2d 1 q, which implies that dim G pH S,µ,d 1 q ď p2 log 2 peq `4qp5d log 2 ppq `2d 1 q.Lemma H.10. If x ą 0 satisfies x ď a log 2 px{aq `b for some a, b ą 0, then, we have x ď 2a `2b.Proof. Define f pxq :" x ´a log 2 px{aq ´b for x ą 0. Then, we have f 1 pxq " 1 ´a x logp2q , which implies that f decreases with x for x P p0, a{ logp2qq and increases with x for x ą a{ logp2q. Since 2a `2b ą a{ logp2q, it suffices to prove that f p2a `2bq ě 0. Indeed, f p2a `2bq " a `b ´a log 2 ppa `bq{aq " a ppa `bq{a ´log 2 ppa `bq{aqq ě 0.Lemma H.11. If x ą 0 satisfies x ď a log 2 px{aq `b log 2 px{bq `c for some a, b, c ą 0, then, we have x ď 4a `4b `2c.Proof. Since • Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations. • The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster. • The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology. • If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)? Answer: [NA] Justification: The paper does not include experiments and poses no such risks. Guidelines:• The answer NA means that the paper poses no such risks.• Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters. • Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images. • We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make a best faith effort. 12. Licenses for existing assets Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected? Answer: [NA] Justification: The paper does not use existing assets. Guidelines:• The answer NA means that the paper does not use existing assets.• The authors should cite the original paper that produced the code package or dataset.• The authors should state which version of the asset is used and, if possible, include a URL. • The name of the license (e.g., CC-BY 4.0) should be included for each asset.• For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided. • If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset.38th Conference on Neural Information Processing Systems (NeurIPS 2024).InAden-Ali et al. [2023, Section2.4], the label space considered is finite. However, extending the compactness argument inBrukhim et al. [2022, Appendix B], we can prove that there exists an orientation of the hypergraph with its maximum out-degree upper bounded by the ceiling of the density even when the graph is infinite, which implies that the above sample complexity of the learner A still holds for infinite label spaces. 
 
 Appendix:  


Decision: The authors make progress in answering a fundamental result in learning theory: the sample complexity of multi-class learning. The authors improve the existing gap by poly-log factors, and outlining directions to potentially get a tight bound. The reviewers appreciated the results. The authors are encouraged to incorporate the comments specially those about the presentation of the technical results.

Reviews: review: paper_summary: paper_summary: This paper gives better bounds on the complexity of multiclass learning using DS-dimension and provides a lower bound. The improvement is relatively minor.
strength_weakness: strength_weakness: The writing of the paper and the presentation style can be improved substantially. The technical summary is way too dense and the comparison with the previous work is very narrow.

The technical improvement is rather weak (some log factors) and doesn't address the main gap (polynomial gap in d).
questions: questions: -- I am not convinced that DS-dimension is the right quantity to look at here. Don't we already have optimal bounds for the sample complexity of multiclass learning in terms or Graph Dimension (see Daniely and Shalev-Shwartz)? Can you please explain how your results compare to the Graph Dimension results?
limitations: limitations: None
paper_summary: paper_summary: The paper considers the problem of analyzing the sample complexity of Multiclass PAC Learning. The key contributions of this paper are two-fold: (1) Give an improved upper bound for the sample complexity by a poly-log factor, and (2) give the first (formal) lower bound for the Multiclass PAC Learning problem, which matches that of binary concept class. The key idea is to use a reduction from multiclass learning to list learning, which can then be further analyzed using recent works on boosting algorithms for list learners. 

Besides, the paper also explores a (potential) alternative approach to analyze the sample complexity for a concept class in Multiclass PAC Learning by alternatively analyzing its corresponding one-inclusion graph. Following this route, if we can give an upper bound for the density of any concept class (defined by the average degree of its corresponding one-inclusion graph) by multiple of its DS dimensions, we can have a matching lower bound for the problem of Multi-class PAC Learning. They argue that this approach is promising by giving proof for the case where the DS dimension of the concept class is 1.
strength_weakness: strength_weakness: There is not much to comment on the weaknesses of this paper. A fastidious reviewer might argue that this paper is a collection of many good but not-so-strong results (in the sense that the list learner techniques used for the proofs of lower and upper-bound using are not completely new), but I think it is good enough for me. 

Some minor comments:
1. It is good to include a proof sketch for every result presented in the Appendix, as well as the high-level intuitions behind the results. Though the statements of key results are clear, readers like us would like to see what is actually going on behind the proofs and would appreciate it if the authors could break down the steps for better readability.
questions: questions: See above.
limitations: limitations: See above.
paper_summary: paper_summary: This work is focused on improving sample complexity upper and lower bounds on multiclass classifcation for a general hypothesis class. Their bounds are given in terms of the so-called DS-dimension of the hypothesis class, which can be viewed as a generalization of the VC dimension to the multiclass setting. Their bounds improve on the best known upper bounds and leave a factor of $O(\sqrt{d})$ between their upper and lower bounds on the sample complexity.

Their main idea is to apply a reduction to list learning, where the learner is allowed to output a set of $k$ potential labels for each $x$ and is evaluated based on whether any of the outputted labels are correct. In particular, they provide a multiclass algorithm that works by calling a list learning algorithm as a subroutine. The subsequent guaranteed loss then grows logarithmically with $k$, the number of used labels. 

Their full algorithm consequently requires a list learner, and they provide one that adapts a previously known boosting technique for binary classification to multiclass list learners. To apply boosting, they define the majority vote of a set of lists as the set of labels are included in at least half of the lists. Note that the resulting list has size $2k$ if each of the lists have size $k$. 

Combining this with their above reduction results in their upper bound.
strength_weakness: strength_weakness: Many of the proof ideas are differed to the appendix. I think it would improve the presentation to include small "proof intution" sections following the theorems. While this would cost more space, I think this can be accounted for by moving the highly technical algorithm blocks into the appendix and merely giving summaries of what the algorithms do in English. 

Of course, this paper is "incremental" in that it merely improves existing bounds to an preexisting problem, but I do not see this as cause at all for rejection. The improvements are clearly non-trivial, and the problem being studied is of fundamental importance.
questions: questions: See weaknesses.
limitations: limitations: Yes.
paper_summary: paper_summary: For the problem of analyzing the optimal PAC sample complexity for multi-class learning, two possible routes to induce the improved sample complexity and error rate are proposed. On the one hand, benefiting from the reduction from multi-class learning to list learning and the boosting technique, the dependence of the corresponding upper bounds on the sample size is improved by a logarithmic factor. On the other hand, the introduction of "pivot shifting" shows its potential ability to improve the sample complexity of multi-class learning.
strength_weakness: strength_weakness: The theoretical analysis in this paper improves the existing theoretical results for multi-class learning on the DS dimension, but the relationship between the obtained theoretical bounds and other data-independent complexity bounds based on combinatorial dimensions, e.g., the graph dimension, the Natarajan dimension and its scale-sensitive analog, is not discussed and compared, which is not conducive to demonstrating the improvement of these theoretical results from a macro perspective. In addition, existing theoretical results on multi-class learning show that data-independent generalization bounds often depend on the number of classes, and the best (weakest) known dependency is logarithmic. The results in this paper focus on improving the dependency on the number of samples, and do not explicitly discuss and analyze the dependency on the number of classes. These related issues require further analysis and explanation.
questions: questions: Please refer to the Weaknesses for details.
limitations: limitations: This work does not seem to have any potential negative societal impact.
paper_summary: paper_summary: This paper presents improved sample complexity upper and lower bounds for multiclass classification, shaving previous upper bounds to within a factor of $\log(1/\epsilon)$ from the conjectured optimal dependence on $\epsilon$, and adding a dependence of $\log(1/\delta)$ to previous best lower bounds. To do so, the authors study multiclass classification through the lens of the more genearal problem of list-learning -- this generality allows for a theorem stating that the conjectured optimal dependence of $1/\epsilon$ in the sample complexity holds given a conjecture about the sample complexity of list-learning. They further discuss the potential of technique they term ``pivot shifting'' to remove the extra log factor of $1/\epsilon$ in the multi class complexity, showing that whenever pivoting shifting does not increase a characteristic combinatorial complexity measure by more than a constant factor, pivot shifting eliminates the extra log factor.
strength_weakness: strength_weakness: Outside of Section 1, I found the presentation of the paper to be very weak. Certain paragraphs present hard to follow proof outlines (e.g. line 236 "the standard leave-one-out argument" is not something I am familiar with and is not explained in the main body). Section 3, which introduces the concept of pivot shifting, provides little intuition into the notation-heavy definitions provided, and cannot be understood without reference to definitions which only appear in the appendix.

It is also a bit unclear what the upside of introducing the generality of list-learning is. The second half of Theorem 2.11 (line 281) does not feel like particularly compelling evidence for the conjectured $1/\epsilon$ dependence, given that it relies on an analogous intuitive conjecture on the sample complexity of the more general problem of list learning.
questions: questions: 1) Is there a particularly compelling reason to believe in the existence of some $\mathcal{A}_{goodlist}$ in Theorem 2.11? What do see as the advantage of thinking about multi-class learning through this extra layer of generality?  

2) Could you elaborate on the $\log(1/\delta)$ factor in the lower bound (Theorem 2.5) -- does the proof technique follow that of Charikar and Pabbaraju [2023], or is this a different construction?
limitations: limitations: Yes

Comments: title: Response to rebuttal
comment: Thank you for your response and we are glad to hear that.
Thank you for increasing the rating.
Thank you for raising your rating. We will further elaborate on the technical aspects of the paper and improve its readability.
Thank you again for your support.
Thanks, sounds good. I can increase the score to 5.
Thank you for your response, my score will remain the same, and I think this paper should be accepted.
Thank you for your reply, and apologies for not fully understanding your contribution on the first read. On account of this, I raise my rating to a 5. 

In particular, I thank the authors prompting me to absorb the advatange of the reduction analyzed in Theorem 2.7. This makes clear to me the utility of considering the conjectured $\mathcal{A}_{goodlist}$, and eliminates the concerns in the second half of the above "weaknesses" section of my initial review.

I still feel the presentation leaves a fair amount to be desired. While I understand that the contribution is rather technical,   
the sheer density and abruptness of the writing in certain parts do make for a particularly good reading experience in my opinion. While it's of course possible improve such things in the next version, it does limit my revised rating. 

Whether the technical contribution outweighs this downside is probably not something I'm qualified to comment on, as the paper is part of a line of work that I'm not familiar with.
Thanks for your detailed feedback. It has partially addressed my concerns.