Improved Sample Complexity for Multiclass PAC Learning
Authors: Steve Hanneke
Shay Moran
Qian Zhang
Venue: NeurIPS 2024 poster (2024)
Keywords: Multiclass learning
PAC learning
Statistical learning
List learning
Primary area: learning_theory
TL;DR: We improve the upper bound of the sample complexity of multiclass PAC learning.

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.

Improved Sample Complexity for Multiclass PAC Learning
Steve Hanneke Purdue University steve. hawneke@gmai..coo
Shay Moran Technion and Google Research
smoran@technion.c ac.
Qian Zhang
Purdue University
zhan3761 11tr3/61ppurdueeeee edu
Abstract
We aim to understand the optimal PAC sample complexity in multiclass learning. While finiteness of the Seniely-Shaaev-SSheeee to characterize the PAC learnability of a concept class [Brukhim. Carmon, Dinur, Moran, and Ychudayoff. 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 positive answer to either of the two questions would completely resolve the optimal sample complexity up to log factors of the DS dimension.
(DS) dimension has been shown
Introduction
Multiclass learning refers to the problem of classifying an input feature from a set (feature space) X to label in a set (label space) y with | > 2 ()) can be infinite) [Natarajan, 1989, Ben-David et al., 1995, Daniely and Shalev-Shwartz, 2014, Brukhim et al., 2022]. When | 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 [I.i et al., 2004], etc. For theoretical analysis of multiclass learning, 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 x V. 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 Cheniii-hhevvseekiss (VC) dimension has been proved by Vapnik and Chervonenkis [1968], the characterization of the multiclass PAC lcarnability remained open until Brukhim et al. [2022] showed the equivalence between the PAC learnability of concept class and the finiteness of its Shalev-Shwartz, 2014] instead of Natarajan dimension or graph dimension.
(DS) dimension (dim, see Definition 1.4) [Daniely and
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 ( + log(1/8))/es where d is the VC dimension of the concept class. Since DS dimension and VC dimension coincide for binary concept classes, is natural to ask if the sample complexity of a concept class H S y for | > is also in
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

((d + log(1/6))/a where d = dim(H) is the DS dimension of H. In terms of the upper bound, it asks if there exists a multiclass leamer whose worst case error rate is in O((d+ log(1/8)) with probability at least - 6, where denotes the size of the training sequence. However, on the one hand, an explicit proof of the (2(d + log( /e) lower bound on the sample complexity still missing in the literature. On the other hand, the current best upper bound on worst case error rate to our knowledge is O (42/2 log(dd) d log (log(n))) log" (n) -log((18)) [Brukhim et al., 2022], which differs
from the conjectured rate by the factor (log(log(n)) + vd log(d) log)(n...
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. Specifi- cally, for concept class H = ) with dim(H) d, we prove an (2( + log(1 log(1/5)) /0)) lower bound on its sample complexity and construct a multiclass learner whose worst case error rate is ((d//2 log(d) log(n) + log(1/5))
with probability at least 6, which implies that the sample
complexity of H is O dd/2 log(d) (1811188)) 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 (log(log) (n)) log" (n)/n) to ((og(()) (n)/n) (treating d as a constant). The multiclass learner we construct builds upon 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 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 would imply an (1//n) 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 al., 1994] on its projection
finite sequence of features (see Section 1.1 for definitions). Then, informally speaking, the "density" (defined through the average degree of the one-inelusion graph) of a concept class can be used 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 multiple of its DS dimension, then the sample complexity is in O[[dim (H) + llg((/8))
which matches the lower bound we prove. Thus, a sample complexity for
proof of the above upper bound directly leads to ((dim + log(1/8))/ multiclass learning. When dim (+)) 1, we successfully prove the (log(1/0)/ 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 pivot shifting does not increase the DS dimension of concept class, then its density is upper bounded by twice the DS dimension. We leave the impact of pivot shifting DS dimension another open question.
Throughout the paper, we use N denote the set of positive integers. For any n N, we define [n] == {1...., n3. For any sets X, Y sequence x = (I1,.... In) E X"", and function f y we define the subsequence x-; == (I1.... 11 Ts+1..... ..,,, zn,) for E [n]] and flx := (f(x)).....
The projection of a set F = yx to is defined as Fix = {flx f F) ym
Outline In Section 1. 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.
1.1 Multiclass learning
In this section, we formally introduce the problem of multiclass learning [Valiant, 1984], For any distribution P over X Vi, the error rate of a classifier h E y under P is defined as
crp(h) == P(((x, v) E X' x y : # h(x)3).
2

---

In this paper, we focus on realizable distributions: for a concept class H. = ) a distribution P over N' x V is H-realizable if inf prp(h) Let RE(H) denote the set of H-realizable distributions. Besides, ((r,, u=)) E (X' x 3 is H-realizable if 3he E H such that yi h(xx), Vi E [n].
Definition 1.1 (Multiclass learner). A multiclass learner (or a learner) is an algorithm which given sequence s ==o x )) and concept class H = y .oulputs classifier A(s, H) y
Then, define multiclass PAC learning as follows.
Definition 1.2 (Multiclass PAC learning). For any concept class H = yx, the (PAC) sample complexity MA... (0, N of a multiclass learner A is a mapping from (e, E 1)² to the smallest positive integer such that for any m. 2 -M..u(e,5) 6) and any distribution P RE(H), Ps-P"(CIp(AA) H)) > =) & 6, and we define MA.H(EE, 5) 00 if no such integer exists. We say H. is PAC learnable by A if MA,H((, 8) < -0 for all (E, (0,1) The (PAC) sample complexity of H is defined as MH (E, 5) :- inf MA.H(e, 6) for any (c, () E (0,
Sometimes it is easier to analyze the expected error rate
EAH.,P: N - [0, 1], Ps ( H))] = ((..(..Y)))= (Y * (X))
for a learner A and distribution P over X' x y, or transductive error rate
trams N - [0, 1]: n
sup s= (M..)..........MM))))))))))).)
Li-1 [(())=A(( ;.H))(:))
We further define 6A. == SUPPERE(H) CA, CH == A and Er,ttams == inf H, By a leave-one-out argument [Brukhim et al., 2022, Fact 14], we observe that EA.H & A.HH.. Aden-Ali et al. [2023, Theorem 2.1] upper bounded the high probability error rate using the trans- ductive error rate, which leads to guarantee on PAC sample complexity. Based on their result, we prove the same upper bound up multiplicative constant 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.
Definition 1.3 (Pseudo-cube and k- k-pseudo-cube). For any d, k E N. a class H C. y²t is called k-pseudo-cuhe of dimension d if it is non-empty, finite, and for every h E H and E [d], there exist at least l i-neighbors of h in H. where is i-neighbor of h if g(i) + h(í) and أ(و) = h(j) for all
j e [d] A pseudo-cube of dimension d is a 1-pseudo-cube of dimension d.
Definition 1.4 (DS dimension and k-DS dimension, Charikar and Pabbaraju 2023). For any d, k E N, we say X E 2 is k-DS shattered by H = Yx if contains d-dimensional k-pseudo-cube, The k-DS dimension dimg(H) of H is the maximun size of k-DS shattered sequence. We say x is DS shattered by H if it is I-DS shattered by H. The DS dimension dim(H) of H is defined as dimi (H).
Now, we introduce some existing results in multiclass learning. Brukhim et al. [2022] proved that class H = ye is PAC learnable if and only if d := dim (H) 00, and there exists multiclass learner A which for any P E RE(H), de (0, 1), n E N, and S ~ pa, satisfies that with probability least 1- 8,
P (A(S, H))- O (SuP log(d)) a (n))) log (o)+1))(1/)))
(1)
which 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 (*(n) = Q (d/n). 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 My is still missing.
The learner A in Brukhim et al. [2022] relies on orienting the one- 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 C yd for n e N is a hypergraph (H)) = (H, E) where H is the vertex-set and E denotes the edge-set set defined as follows. For any i [m]] and f: [n]][ - Y, we define the set ei, (h E H h(j) = f()), Vj e [n]][]]]- Then, the edge-set is defined as
E:= = ((e,,,,) :i: :iE [m]. f [m]]((]] + VVe,, # 23).
For any (ei,f,) i) E E. and h e H, we say h E (e). if E ei, and the size of the edge is ((), ;= leisl-
3

---

Typically, we consider the one mne-inclsiion graph of the projection of a concept class H. S y to sequence x E x with n N, i.e., ((H])). The "density" of H. discussed in Section is defined via the "maximal average degree" (defined below) of the hypergraph g(H(x).
Definition 1.6 (Degree and average degree), For any hypergraph G = EV,E) and u V, we define the degree of in G to be deg(e; G) == He E : e.|e| 2 2 When the underlying graph is clear in the context, we simply write deg(v) in abbreviation. I < oc, we can define the average degree and average out-degree of G to be
avgdeg(G): == [V Eeev (v; G) = M EeeB: /el and avgoutdeg(G) := V VI Eee - 1).
For general V, we can define the maximal average degree of G to be md(G) == sup avgdeg( (G[U), where G[U] (U, E(U)) denotes the induced hypergraph of G on U = with E|U]= = (e (enU: e EuenU + Ø).
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 E En, we have
avgdeg( G) = T Eeenseaa & L 2(1e| - 1) = (G))
(2)
Now, we can define the density of concept class as follows.
Definition 1.7. The density of H = y is defined px(m) == suP md(G(H) Vm N.
1.2 Main results
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 rate under any realizable distribution. Definition 1.8 (Nondegenerate concept class, Hanneke et al. 2023). A concept class H E y* is called nondegenerate if there exist ba, h2 E HH and To, X such that hy (mo) ha(2r) and by (11) * (21)... ). 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. S yx with dim (H) = d and any (e, 8) E (0, 1) we have
a((d + log(1/6))/e) & Mx(s, 5) & ((d3/2 log(d) log(d/e) + log(1/5))/e).
(3)
Our upper bound follows from a reduction to list learning and improved sample complexity for list learning summarized below.
Theorem 1.10 (Informal summary of Theorem 2.7 and 2.10). Assume that there exists list learner which given a concept class H with dim(H) = and training sequence of size n E N outputs a menu of size p(H, n) with expected error rate upper bounded by B3H, n)/n for some functions p and nondecreasing in n. Then, there exists a multiclass learner whose error rate is O((((H,)) n) + d dloo(p(HH H. n)) + log(1/8))/n) with probability at least 1- 8.
Moreover, there exists a list learner satisfying p(H. n) = ((eev)) ((g(V))))og((n)) and 3 n) = O (d3/2 log(d) log(n)).
We refer readers to Section 2.1 for detailed definitions regarding list learning. Note that if p( H, n) and B (H, n) of some list learner is independent of n, there exists 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 O((d + log( ( 1/8))/E) sample complexity, by directly bounding the average degrees of one-inclusion graphs. In particular, we show in Theorem 3.2 that any H. with dim O(log(1/8)ee 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.
1 has MH 6)
Proposition 1.11 (Informal summary of the results in Section 3). Assume thut 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 have MH(E, 8) e ([dim(H) + (og()/)))/=) for any H S yx.
4

---

2 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 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.
2.1 List learning
In list learning, the menus defined below serve as classifiers in multiclass learning. Definition 2.1 (k-menu, Brukhim al. 2022). A menu of size k N is function μ X (Y = : & k). A 1-menu can be viewed as a classifter in y and vice versa.
For any distribution P over X x y. the error rate of k-menu j under defined e := P([(2, y) E X' x y y $ p(z))) which agrees with the definition of the error rate of classifiers when the size of the menu is
Definition 2.2 (k--list learner). A list learner A size k E N is an algorithm which given sequence s E on x y and concept class H S y oulputs a k-menu A(s, H). A 1-list learner can be viewed as multiclass learner, and vice versa.
Similar to multiclass learners, the expected error rate of list learner AA is defined as
EA : N - [0, I], n - [s- H))] = P(s (Y $ A(S, (X))
for any concept class H y and distribution P over X x y. Restricting to realizable distributions, we can define
EAH := sup EAHH. PERB(H)
and E
inf k: list learners A EA
Next, we define list PAC learning.
Definition 2.3 (List PAC learning, Charikar and Pabbaraju 2023). For any concept class H S ye and k E N, the (PAC) sample complexity MA.. (0, - N of a k-list learner A is a mapping from (e, 8) (0, 1)² to the smallest positive integer such that for every 2 MA.H((E,) and every
distribution P E RF(H), Ps-P= (er (A(S, H)) > E) & 6. and we define MA.H((,,)) = 0c if such integer exists. We say H is k-list PAC learnable by Af MA,H,,, < for all (s, 8) E 1). The k-list (PAC) sample complexity of H is defined as M (e, 8) == inff-lisst k-list leamnr M MA.H(E for any (s, 1)?.
Note that H is PAC learnable by learner A if and only if H is 1-list learnable by A. and the PAC sample complexity of H is Mx M For list PAC learning, was proved by Charikar and Pabbaraju [2023] that concept class H is k-list learnabale if and only if de dim)(H) < oo, and there exists a k-list learner A which for any P e RE(H)), 5 e (0, 1), n N, and S ~ P", satisfies that with probability at least 8,
er (A (S, H)) =0 (v'ds log(do, (oo))dd)++og (kg log(n))) (og" (ogg1))(1
(dd/((k)) (kn)) has been proved in Charikar and Pabbaraju [2023, Theorem 6]. However, a lower bound of the same order on the k 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- d-nondegeneracy as follows.
For the expected eтror rate, the lower bound & (n) = Ω (dz/
Definition 2.4 (b-nondegenerate concept class). concept class H yx is called k-nondegenerate for k E N if there exist hi,.... ,14+1 E H and æo, 21 E X such that (hg(2o)) : [k + 1J31 = 1 and H. is called k-degenerate if is not k-nondegenerate.
((h,(x1) :j [K 17}1
We claim that only one training point is sufficient for the k-list learning of a k-degenerate concept class H. Indeed, H k-list learnable if [ & k. Now, suppose that [H] > k + 1 and is k-degenerate. Upon observing any point (x', y/) E X y realizable by H. if (h E H h(x²)
y'}l & k, then I - (h(x) h E H. h((x'= 5/ is k-menu which always contains the correct label. If [[ E H: h(x')= v > A + 1. then, for any E f2'(2', we must have [h(x)) h H, h(2')) v'll & k
5

---

because otherwise H. is k--onnegennraae. Then, 2 (h(x) : h H. H,h(())= = y/} 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 E N, k-nondegenerate concept class H _ )xx with dim=(H)) ds E N,
E (0, 8(k+1)) and & e (,, 4(1+1)) we have (E, > (og))))0112)) In particular, when h = 1, for any E E (0, 1/16) and Ó E (0,1/8), we have Mu(E,6) (dim(H)-1))
16(k-1)5
(5)
32s
The proof of Theorem 2.5 is presented in Appendix A where we construct hard distributions based on properties of k-pseudo-cubes.
2.2 Reduction from multiclass learning to list learning
We first introduce the theorem that provides guarantee PAC sample complexity based on expected error rate, which will be used frequently in our analysis.
Theorem 2.6. Fix concept class H S y and consider learner A which satisfies p(n) & RE(H) with M,, nondecreasing in the sample size n. Then, there
Mn/n n for any n E N and exists learner A' such that for any P RE(H), 8 (0,1), 2 4. and the training sequence ~ P", with probability at least 1 - 8, we have
cIp( H)) < 4.82 (8.34M (n/2] + log (2/()//)/
The proof of Theorem 2.6 is provided in Appendix B. Now, we consider general list learners whose sizes may depend on the sample size. The theorem below states our reduction to list learning.
Theorem 2.7. Assume that there exists a list learner Ajst which for any H. S y D RE(H), e N. and S ~ DD,, outputs a menu Alist H) of size p(H, n) satisfying H, & B(H, n)/n for some function 22 x N [0,s0). Without loss of generality, we assume that p(H, n) and ((H,n) are nondecreasing in n. Then, there exist multiclass learners Ared (see Algorithm 1) and Ared which for any concept class of DS dimension d, D E RE(H), 8 E (0, 1), and n 2 4, satisfy O ((3(H, m1) + ((H, n1 /n))
A,e,, H.D(
where n1 = ni- - 2[nn3]] and for S D", with probability at least
CTD (Aee 8, 70) O ((S(HL, m1) + d dloo (oH, ) log( (1))))/)).
(6)
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& of size & E N developed Charikar and Pabbaraju [2023] cannot lead to improved error rate of multiclass learning using our current result. The construction of Ared from Auit is shown in Algorithm 1.
Algorithm 1: Multiclass learner Ared using list learner Ajist.
Input: List learner Aust. concept class H. S yx training sequence S ((11, 31) .1),.... . (Nn:yn.)
Vn.)) E (X' x 31 for n 2 3, test feature Un+1 1 X.
Output: label y E y for the feature In+1.
M1 - n 2/./3].
|n/3]:
S¹ ((z,, [e))m] 52 - ((zi, 9:)) x' - (I. Inti)
A H), N -E Lupp(a)
Hy - (hly: h H1 In + 17; [ma] ]: h(x)) & ((x:))) < NN+13
5 Sample (I,,..., Inn.) ~ (22m) "2;
AT, Hxx where
((T,, (1,4tm
return the label 72(2 + 1).
In step of Algorithm 1, AG is a multiclass learner defined in Proposition H.5 in the appendix. Moreover, we prove in Proposition H.5 that for any D RE(H), n E N, 8 E (), and S ~ D", with probability at least 8. we have
(Ap(A, H)) = O ((dim + log(1/5)) /n)))))

---

where dimg (H) is the graph dimension [Natarajan and Tadepalli, 1988] of 7 (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 ft. Then, we count the number of errors (N) made by ju in the last two thirds samples. Then, we consider Hx which is a subset of H/ such that the number of errors on x' is bounded by N + 1. We show in Lemma H.9 that dimg is well controlled. However, as we do not observe the label of the test point, we can only consider resampling from elements in S as the new training sequence fed to Ag together with the concept class Hx. 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 Hx only depends on S but not the test point (Xn+1, Yn+1). We tackle this challenge by proving that some permutation of the error event together with the constraint on correctness of fu on the last two points in x' when leaving the last element (i.e., the test point) out is subset of the error event when leaving the previous element (i.e., the point in 8²) out. The details of the proof is presented in Appendix C.
2.3 Sampled boosting of list learners
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 list sample compression scheme of size r (dd (o) for concept classes of DS dimension and sample size n. One can show that its error rate is O ((r log(n/r) + log(1/5))/n) using standard techniques for sample compression schemes [David et al., 2016], which however brings the extra log factor log(n/r). 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 E N menus .i,..... lK each of size p. we define their majority vote to μ Maj(U1,,.... ..,i())...., with
((x) Maj(U1,
(4x) (x) ,
ty y: 1[k E [K] y E px > K/2], Vx e X.
Note that μ has size 2p- - 1. For p = 1, the above definition recovers the majority vote classifiers.
Algorithm 2: Sampled boosting Aboost of a list learner Auit
Input: List learner Atist, concept class H = y training sequence
S = {((11, (11,,11),-.11)1 ( (n)) (X' x ")", (0, 1/2), v (0,7/18), ā e (0, 1).
Output: Menu p.
for i = 1,..., n do
L D (1(2,, (:)3) 1/n:
3 < log (11 + 711(111100 7)), m (112 K 104--44lge [4log(n/6)/11
for k = .......A. K do
Draw samples 5 D [4 (Sk H):
7
for io 1, I,..., do
L P1 v:)3) - (1 exp (-a (21 - 1)):
DK+11 - D (Σr_
exp (-ax (21 - 1))):
10 return μ - Maj ((H))e(K))
Here, 7 and v are fixed constants, enabling us invoke weak list learners (of constant and confidence levels) to Algorithm 2. Next, we upper bound the error rate of the boosted list learner.
Theorem 2.8. Assume that Alist is a list learner with MA H (1/2 122 v, < ac for some ?y e (0, 1/2) and v (0, 1/18). Then, for any D RE(H), E N. and 8 > O, sampling S~ SDDn, with probability at least - 8, the menu p produced by Aboost using Atiat in Algorithm 2 satisfies that
erp(u) O MM
(111/2- log(n/6)
77
7

---

The proof of Theorem 2.8 is generalization of the proof of da Cunha et al. [2024, Theorem 1.1] and 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 Brukhim 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 learner A with (A,H(1) =0(
20th (2921 log" (d) log(m) and
M. (A,H(E,,)) 0) 0 d9/2 log"(d) log(d/e)))og(11/)) for any n E N, (e,6) E (0, and H = ya with dim(H) = d.
There is extra log(d) factor in the above upper bound compared 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 log(d) factor compared to their sample compression scheme. Therefore, we invoke their list sample compression scheme as Anist to Algorithm and build list learner whose error rate depends on only one log factor in both n and d.
Theorem 2.10. There exists a list learner AL which for any H. = yd with dim H)) = d and sample size n. E N outputs a menu of size ((evd)) log()) with (A), - O 2//2 log(d) log(n)
2.4 Improved upper bounds on sample complexity
Applying the list learner Ag in Theorem 2.10 to our reduction, Theorem 2.7 immediately implies the following result.
Theorem 2.11. There exists multiclass learner Amulti such that for any H S yxx of DS dimension d, D e RE(H), d (0, 1), n > d + 1, and S ~ DD, with probability at least 6, we have
erp(AmutiiS) H)) 0 62/2 log(d) log(n) +1og(1/61)
which implies that
M M4 -0:00)=06
0040/ log(e) (os(dd/))-og((1/)) Ve,5 E (0.
(8)
Farthermore, if there exists list learner Agondlist of size [i(d) and expected error rale AAvoatia (( H(n) & (n for some functions S1 N - N and J2 N - (0,00), then, there exists multiclass learner Aun such that
Me, ((doog(Fi(d))) + f2(d) + log(1/8))/e), Ve, 8 (0,
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;(()) >> dim for k < W, our requirement on Agoodlist 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 (log(log(n)) log 2 (m)/n) to (log(n)/n), which steps further towards the goal of (1/nn) 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 vd log(() (d) log(d/e). However,
not aware of any existing list learner satisfying the requirements of Agoodlist in Theorem 2.11. Thus, we leave the construction of Agoodlist as an open question.
Open Question 1. Does there exist a list learner such that given a concept class H. C &x*, its size is fi (dim(H)) and its expected error rate is A (n) fz(dim(H)))/ for some functions fi - and f2 N [0, o
Ideally, we would expect list learner with size O(dim(H)) and expected emor rate O(dim(H) H)/n) as it immediately implies an upper bound MH(E, 8) O((dim( (H) log dim())) + log (og()/ which matches the lower bound in (5) up to the factor log (ogiimH))))
3 Density, DS dimension, and pivot shifting
We now introduce an alternative route toward proving the optimal sample complexity of multiclass PAC lcarning: bounding the density pad : [0, a0) (Definition 1.7) of concept classes H. The
8

---

following proposition summarizes existing results that illustrate the role of density in multiclass learnin.
Proposition 3.1 (Daniely and Shalev-Shwartz 2014, Charikar and Pabbaraju 2023, Aden-Ali et al. 2023). For any H = )ux and n. E N, we have
(2(())/2en) & EN & HH,trass & PH(()//n.
(10)
Assume that p & [(dim(H)) for some function ::N - (0) and all n. E N. Then, there exists a learner A based on orienting the one-clusion graph (Definition 1.5) of the projected concept class (see Aden-Ali et al. [2023, Appendix for the formal definition of the algorithm) with sample complexity MA.H(E, 6)= = ( [[dim(H))+oog for all e, e, (0, 1).
In Proposition 3.1, the first inequality of (10) follows from Charikar and Pabbaraju [2023, Theorem 6], the last inequality of (10) follows from Daniely and -hhlr--- [2014, Theorem 2], and the last paragraph follows from Aden-Ali et al. [2023, Theorem 2.2]. Thus, for sharper multiclass sample complexity, it suffices to bound the density of concept class with some functions of its DS dimension. Furthermore, by Definition 1.7 and (2), it suffices to bound the average out-degree (Definition 1.6) of finite one-inclusion graphs. In fact, it has been conjectured that (*x(n) & c-dim (H) for some constant e > 0 [Daniely and Shalev-Shwartz, 2014] and the question remained open since then. A positive resolution of this conjecture would immediately imply that the MM(e,, 6) @ ((dim(H) (H) + log (1/8))/n) by Proposition 3.1 and Theorem 2.5. It is worth mentioning that for H S {0, 1 Haussler et al. [1994] proved that jow & 2dim(H() (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 = yx with dim (H) = 1, we have (n((n) & 2, Vn E N. Thus, Mz(e, (1og()/ for any positive e, 8 E (1) and any H with dim 1.
The above theorem follows from the following fact we prove for one- inclinnlusoon graphs of DS dimension I concept classes. The proofs of Theorem 3.2 and Proposition 3.3 are presented in Appendix F.
Proposition 3.3. For any n E N and V, = ) with |V.l < oo and (im(V..) = 1, there exists no cycle (see Desinition 3.4) in the one-inclusion graph GVV..) (see Definition 1.5).
Definition 3.4 (Cycle in finite hypergraph). A cycle of length m E [N{1}} in finite hyergraph G CV E) consists of pairwise different vertices un ......, 1 E V and pairwise different edges e0 m- 1 E such that v², a(++1) mod m E e² for all E 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- me-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 E NM(1 and V, S ymm, we define
((K)) = Oyey UVEr(tt (V)1..... 1)- E _= (yI,..., Un- 1,3), w), "ul......--1111 1n-1, Vn3.
Then, E y is said to be a pivot of Vn if (v1,.... "un....,,n1........ a) E for any "aa....,bn-1) E VV,).. We emphasize that when P(V.)) = D. every a E y a pivot of Vn,
a,
Then, we can present Lemma 3.6 whose proof is provided in Appendix G.
Lemma 3.6. Assume that for some n E N1(1), any d E N, any m [n- 1), and any H = ym with dim(H) H) & and [ < sc, we have ( & d. Consider an arbitrary set Vn S ym such that [Va] < 00 and dV.( < d. Vn, has a pivot, then we have avgoutdeg(G(V,,
& d.
In Aden-Ali et al. [2023, Section 2.4]. the label space considered finite. However. extending the compactness argument in Brukhim et al. [2022, Appendix BJ, we can prove that there exists an orientation of the hypergraph with its maximum out out-deeree upper bounded by the ceiling of the density even when the graph is infinite, which implies that the above sample complexity of the learee A still holds for infinite label spaces.

---

Though it only works for special classes, Lemma 3.6 can serve as a building block in the induction step for the proof of avgoutdeg($ 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 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 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 [1] E V, and Vn S ) with [Val < 00, we define (V.) Oyey (wn, .......... -n-1)) y (y) -.l....... 1n-1, v) Vn, (y1, ... Ua-1, 1, a) Vn For any y (y1 Mn- 1) (Va) and the edge (t) in G(V,), we define the set by {y E y "ul,...,yn-11 V) E (en,y n))-
< dim(H) H) for finite H. = Unen)"". Moreover, the base
A mapping :a - y is called a pivot shifting on Vn to a if y(y) Tyy for all y E BV())) Let a.VV denote the set of all pivot shifting on Vn to a. For any Y E Tay, we define
V = (V.)) (a,, (()) y Pa(V..) U ((y.a) : Ba(V.)); i.e, Vn,, is obtained by replacing the label v(y) (y, 7y)) with a for all y E Ba(V...
We prove that the average out- out-degree does not decrease after pivot shiftings in the following lemma. Lemma 3.8. For any a E V, E y with |V| < co, and y E Ta,y, we have
(vgoutdeg(G(V7)) > @Vgo)tdeg(G(V)).
The proof 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 E N and any V C t n= with |V| < oo and dim(V) d, are there some a E y and y E Fay such that dim(V?) & d?
Nevertheless, we have taken a further and specific step toward the verification of the conjecture that μn & 2d)m(H): positive resolution of the above question would lead to the conclusion that Ni < (H) by Lemma 3.6, Lemma 3.8, and Brukhim et al. [2022, Lemma 13].
Acknowledgments and Disclosure of Funding
Shay Moran is Robert J. Shillman Fellow; he acknowledges support by ISF grant 1225/20, by BSF grant 2018385, by Israel PBC-VATAT, by the Technion Center for Machine Learning and Intelligent Systems (MLIS), and by the the European Union (ERC, GENERALIZATION and opinions expressed are however those of the author(s) only and do not necessarily reflect those of the European Union or the European Research Council Executive Agency. Neither the European Union nor the granting authority can be held responsible for them.
101039692). Views
References
Aden-Ali, Y. Cherapanamjeri, A. Shetty, and N. Zhivotovskiy. Optimal pac bounds without uniform convergence. In 2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS), pages 1203-1223, Los Alamitos, CA, USA, nov 2023. IEEE Computer Society. doi: 10.1009FOCSS57990022220 2023.00071. /Btpatpts////daeeeeeeeeeeeerrree 2007.00071..
arg/10.
S. Ben-David, N. Cesa-Bianchi, D. Haussler, and P. Long. Characterizations of learnability for classes of (O...., valuee functions. Journal of Computer and System Sciences, 50:74-86, 1995.
10

---

S. Bendavid, N. Cesabianchi, D. Haussler, and P.M. Long. Characterizations of learnability for classes of [0, .... -lvalue functions. Journal of Computer and System Sciences, 50(1))74-86, 1995. ISSN 0022-0000. doi: https://doi.orr//1... 1006/////0.0000/ss.ss.s.coo 199ssssssss99.9... 1008. https:t:s:: h/wpp/.///wwww/e htttt::://ww..ccceeeeereeett sciencedirect.. comm http://eennc/articleeeeeeee http://aaaaaaacccaaaaa//0/000010
Nataly Brukhim, Daniel Carmon, Irit Dinur, Shay Moran, and Amir Yehudayoff. A characterization of multiclass Icarnability. In 2022 IEEE 63rd Annual Symposium Foundations of Computer Science (FOCS), pages 943-955, IEEE, 2022.
Moses Charikar and Chirag Pabbaraju. A characterization of list learnability. In Proceedings of the 55th Annual ACM Symposium on Theory of Computing, STOC 2023, page 1713-1726, New York, NY, USA, 2023. Association for Computing Machinery. ISBN 9781450399135. doi: 10.1 10.1145/3544446.3585 355.555199
URL https::/p//.... /ttp:://doo..eee http://doioogg/////////o
org/oogg//// 10. 11115/55654446666 3585190.
Arthur da Cunha, Kasper Green Larsen, and Martin Ritzert. Boosting, voting classifiers and random- ized sample compression schemes. arXiv preprint arXiv:2402.02976, 2024.
Amit Daniely and Shai Shalev-Shwartz. Optimal learners for multiclass problems. In Conference Learning Theory, pages 287-316. PMLR, 2014.
Ofir David, Shay Moran, and Amir Ychudayoff. Supervised learning through the lens of compression. In D. Lee, M. Sugiyama, U. Luxburg, I. Guyon, and R. Garnett, edi- tors, Advances in Neural Information Processing Systems, volume 29. Curran Associates, Inc., 2016. URL https::/prooee http:////occeeenns.eeee neurips cct.ccc/ppaaa wwwpappr_.eeeeeeeeeceee files fiappe__illespppprr/a2212 pttppp//pp///iiil/// 59f51fd6937412b 220 Paper .df.
S. Hanneke. The optimal sample complexity of PAC lcarning, Journal of Machine Learning Research, 17(38):1-15, 2016.
Steve Hanneke, Shay Moran, and Qian Zhang. Universal rates for multiclass learning. In The Thirty Sixth Annual Conference on Learning Theory, pages 5615-5681. PMLR, 2023.
D. Haussler. Sphere packing numbers for subsets of the Boolean n-cube with bounded Vapnik- Chervonenkis dimension. Journal of Combinatorial Theory A, 69(2):1172332, 1995.
D. Haussler, N. Littlestone, and M. Warmuth. Predicting (0, 1) functioss on randomly drawn points. Information and Computation, 1 115(2):248-292, 1994.
Kamran Kowsari, Kiana Jafari Meimandi, Mojtaba Heidarysafa. Sanjana Mendu, Laura Barnes, and Donald Brown. Text classification algorithms: A survey, Information, 10(4):150, 2019.
Tao Li, Chengliang Zhang, and Mitsunori Ogihara. A comparative study of feature selection and multiclass classification methods for tissue classification based on gene expression. Bioinformatics, 20(15):2429-24 2437, 2004.
B. K. Natarajan. On learning sets and functions. Machine Learning, 4:67-97, 1989.
Balas K Natarajan and Prasad Tadepalli. Two frameworks for learning. In Machine Learning Proceedings 1988, pages 402-415. Elsevier, 1988.
Waseem Rawat and Zenghui Wang. Deep convolutional neural networks for image classification: A comprehensive review. Neural Computation, 290)):332-2249, 2017. doi: 10.1 10.1162/neco_e 2009000
I. G. Valiant. theory of the learnable. Communications of the ACM, 27(1 (7(11))1113)) 111:1114-1100 November 1984.
V. Vapnik and A. Chervonenkis. On the uniform convergence of relative frequencies of events to their probabilities. Proc. USSR Acad. Sci., 181(4):781-78) 1968.

---

A Lower bound
Before proving Theorem 2.5, we first introduce two lemmas regarding k-pseudo-cubee that will be used in the proof.
Lemma A.1. For any positive integers k, d, any label class y, any k-psendo-cube H s yd of dimension d, any j [d], and any label y V, define H == {h H1 h(() y). Then, we have
H
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 E [d] and y E y such that Hg] > k+1 The definition of pseudo- culds implies that H > k + 1. Then, there exist h, h H3J with h + h.. Let (fi,-..: f.}) and (fi:-.., f%r denote the set of j-neighbors of h and h' in H respectively. Since h * h/' and h(j) y = N((j,, there exists some j' e [d]}() such that
h('') * H(G'). It follows that s((i') = h(j') o 1'(G') Ji(') and thus S; * fj for any i, E [k].
Then, have
k H
( H h(j) # wil > MHH
k+1
and
μ| = Kh E H :h() v11 + |و > |.Ib
which is contradiction. Thus, we must have HHl
H
Lemma A.2. For any integer k 3 1, d 3 2, n E [d- 11, and 1 & jn <...< Y, any k-pseudo-cube = yd of dimension d, and any hypothesis g E H, define J := (Ji...... In and K =kn....kkaa)) such that 1 & ki ... < ka-n & d and (ji,... In, .i,...,ke ka-n) } = [c]] Then, Hg = {h/K : h H, H,,(ji) = g(5)), VEE [m]] is a k-pseudo cube of dimension d n.
<. In & d, any label class
Proof. For any J E Hg,J, there exists some h H such that f = hlk. Then, for any E [d- there exists k distinct hu,.... h4 E H such that hm (x)) * h(ki) and hm = Ii(l) for all / E [d] and glu and thus J' hmlk Hg. for all
In.. we have h|j hn m E [k]. Then, we have f(i) = h(k)) # hm (k,) = (t) and f()) = h(kk)) (k)) = fm()) for any [d Mi) and m [b]. which implies that Hg. is a k-pseudo-cube of dimension d n.
m E [k]. Since k; $
Proof of Theorem 2.5. Consider an arbitrary k-nondegenerate concept class H S Y for some E N. Let To, 41 X and hi,..., hh++1 H witness the k-nondegeneracy specified in Definition 2.4. For any E (0, 1/2 + 1)) and 8 E (0, 1), let ~ Bernoulli (A: + 1)e) and J ~ Unif([k + 1]). Then,
for any j [k + 1]. (x), (zr)) follows the H-realizable distribution Pasi over X' x y defined by Pe.s (1(20, h (zo)))) = 1- (k + 1)e and Pa P2,)({(11, h, (x1)))) = (k + 1)e. Sample (4....,44, In) Bernoull(s)) independent of JI and define S ((I))) 1 )..... (II, (x())))) and S' ((xo, (2o) (z),) Then, for any k-list learner A, we have
(ar) & A(S, ()x))) O.....I. In (2))(2)) $ A(S", H)(x1),1=11
-P = 1))(h()))))) & AA("",
-(k 1)eE(P(h)(()) A(S', H))=))) H[))
28,
where the last incquality follows from the facts that h. (zo) = h1 (zo). [/g (xx)))..,,,,+)(())) = A + 1, h=(21)) ~ (Hr hx+1(21))) Since J ~ Unif[ [k + 1J), there exists E [k 1]
such that
((()((r)) $ A(S", H))))) = 0, ....,,... In = 0)
=P(hy(æ)) $ A(S, ()(z))) = O,... I, = 0) >
12

---

where S == ((x1, h2 (r(1))).....
(ZI,, Sesin,hle (2 Pa, is independent of (æ1, (r,h)((z1)) ~ Pe.j-
Since
2[++Ij &
1-(++ < 1og(1-(k+1])) for & E (0,1/2(k + 1)), if n & 2(k+1)e
[k+I]E
log(l/6)
<
[1 (k+1)e) we have
6)
P(h = O,....,,, In -) -1 (k: + 1)s)a > 6.
Then, with probability greater than 6, we have crp,,
Crp,,( (A(S), H)) > E, which implies that log(110) (c, 2 1)
Next, consider arbitrary concept class H yx such that dim&((H) = de E MM(1) for some k E N. Then, there exist sequence := (a), I.a)) X and a k-pseudo-cube H = H/x of dimension dx. Denote the elements H with y² = (wi...., Vdy),...
= (v1 11 ,..., | For
any E (0, 1/8(k + 1)), consider the categorical distribution Q2 over [d,] defined by Qe =
1 1-4(k+1)e and (ti)) 4(k+1)s for i E [d)] Let J ~ Unif([[H[]). For any i E [de]] ((1) and im. define I' :- (81 -...----.. dmm
de
I (i1, (m1...., im)) ([dx]\[o) with
[dg- 1] and
such that E/1 <...< &d and (i,,..., im 8 .......... dd--m) [d,]- Then, we have that conditional on (i1, vY, ,..., (7m; y'm),, y' I follows the uniform distribution over the set H, which is k d-pscudo-cube by Lemma A.2. Consequently,
apply Lemma A.l to conclude that
Hyy. 1+1
( (( <
for any y e y and i' e [dg - m]. which immediately implies that
k
PP E (u),....,=)](( b,) (Im, (im. &
(11)
+
for any distinct U1 .I...., Up E e.. Let (I, II,...,II,) ~ Q=+11 For any k-list leaner A, by (11), we have
1 for n E N be independent of J. Define S = ((01, vi,)............... "/,,, v(.))
PPv' & A(S, (z1)), 1) PPv!' & A(S, (z1), I + 1, + JI,..., + In)
Ply & A(S. (z1),, = 1,4 * i,...,, #
2 E 1 Po $ A(S. (...H))2z),1 i|AsS, H), (T, (I,,,) (..))......... vi,))
P(I P(I * i, I,....,I, x1)
Σ
k +
1-2
( 4(k + 1)E
=4a
di
Since ~ Unit([[A[[] there exists j = j(A, H) E [[]]] such that
P(U/ $ A(S", H)))))()))) + 1) = Plyf A(S, Hx)))) I * 1|J 5) 48 (1- 4(k + 1)e
where Si = ((0),) Vi, (II,, v/, )). Note that if we define the distribution Pas over X' x y/by
Pes((ar,v() 4(k: 1)e and Pes((a,)v)))
4(k: + 1)e dy
Vie [dJ(
13

---

then, we have (S, (xr,w/)) (1-
P. For any n & (de (de-1) log(2)
(2/22
we have
8(k+1Ja
log (dd 1])
1(k+1je 2 and
P(y $ A(S), H)(xI), # 1) 22
Now, we define the algorithm A' by
(s, H)) (x1) = (oi and (ss H)(x)) == A(s, ()),,, Vo E M1)11
for any s U 00 m x m) Then, we have
E (A((S), H])] P A'(S" H)(ar), + 1)
=P(w/ $ A(S', H)))), I + #1)
>2.
(12)
On the other hand, the definition A' yields that of E A') (z1)) and hence
err,, (A'(8) & Pa. (2 (an)) 4(k + 1)s.
Suppose the following holds
P(erp.,, (A(S), H)) 8) 4(k + +1
(13)
Since er erp,,, (A'(S", H)) & err.. (A(S), ()), the above inequality implies that
P(erp,, (A'(S), H)) > 2) & 4(k: 1)
and therefore
(d'(5, HH)] <s + E er (A'(() H)) I llrr, (A((),,)))
S + 4(k 1)eP(err, (A'(5), (S),7) 71) 6)
22
which contradicts (12). Thus, we can conclude that (13) is false, i.e.,
1
P(erp,,, (A(S), H)) E) 4(k + 1)
(do-1)log(2) For E (0, 1/4k//(k= + 1)J, have P(erp.,, (A(S", (()),,)))))))))))))) > > ô and thus 8(k-1j=
for <
(d+ - (og(2)
5)
8(k + 1)
In conclusion, for 5, = O(1/k), we have
de + log 1/0)
M5 6) = 12 ()
ks
B Proof of Theorem 2.6
Proof. Consider an algorithm A: (U (X' })}²) x 222 - y which for any hypothesis class H. S yx H-realizable distribution D. and n E N, satisfies that
M
P(. (A(T, H)( Y) &
(14)
where M, is nondecreasing in the sample size
14

---

For an arbitrary sequence S = be the subsequence of excluding (* y:) for any i [n+ + 1]. Let (Tm, (X, where m E N, Tm E (X' x " and (X E X' x V. Moreover, for any i E [n + 1]. let T Unif(S_:) Then, for any algorithm A x yik 2 y and concept class H y have
(2n. Vn), (In+1, Mn+1l) ) (X' x ))++1, .define S_ to
S) m+
1
P ((A(Tm. H)( 1)
P(A(TM. Hz)))) v))
1
E L (ARNEET 1 P0(.).)
Σ P((2))) 9i) TT)P(A H)(I:) # wil(I, v.) $ Tm)
n1 + 1 m
1
n+1
Σ
P(A(TM. 10(xx) * vel(as. yo) $ Tm)
7+
12 1
n1 + 1 m
1
n+1
Σ
P(A(T H((xx) # vy).
(15)
n n+1 n
Note that if S is consistent with H. then Uni is H-realizable.
Next, define the algorithm AMaj.m (U x 4) x 23 yxt by mMaj. RR, H) := Majority((A(t: H)) Rmm,, VRE (X x v)", V.
By the definition above, for any permutation R, of E (X x ))),, we have AMaj.m RRx H)- AMaj.m ( R, H).
(16)
Moreover, for any i [n + 1J, the above definition yields that
1 (s (;)() $1
n ((s E ST A(s, (z:) # wHl
= 2P (ATTTT m Hz,z)) # m))
Then, by (15), we have
1 R-
2(n + 1)
n Σ
1 Lm (H)()))) <
(()((T..))())) # Y). n2 + m
Choosing m [(n + 1)/2| and defining AMaj : AMa5.((++1)221 for any H-realizable sequence S, by (14) and the above results, we have
2(n + M (x+11/21 & 88.34M (m+ (17)
Σ Ama (
(n + 1- [(n + 1)/2l)[(n+ 1)/2
for any n > 4. (16) and (17) imply that the algorithm AMaj satisfies Assumptions 2.1 and 2.3 in Aden-Ali al. [2023].
Now, we can define the randomized algorithm Aran which given a sample S (X' x y)"" with n E N and concept class H. outputs the classifier AMaj (S, H) if & 3 and outputs random classifier following the uniform distribution over the sequence (AMaj H)
if > 4, i.c.
PR (S.H) = AMAnj 70)
Vt [ln/4], 4|/44| - 1].
3|n/4|'
where See denotes the subsequence of S consisting of the first / elements in S. Then, by Aden-Ali et al. [2023, Theorem 2.1 for any n > 4, H-realizable distribution D, and confidence parameter
15

---

ō E (0, 1), given training sample S ~ D", we have
4/n/4|-1
er H))
Σ
erp (EDMM H))
3|m/4]
11/2/4
8.34M
m/
1
2
<4.82
log
5
11
11
with probability at least - 8.
C Proof of Theorem 2.7
The following proof requires several lemmas from Appendix H.
Proof of Theorem 2.7. Assume that have access to a list learning algorithm Arist which for any concept class H S y of DS dimension d, any H-realizable distribution D, any n E N, and (X,)) Di+11 outputs a menu Anst H) of size p(n) N satisfying
P(Y Aust H)( < 3(H.
for some function B ::2 x N (0).
For n1, n2 E N, let (Sa 52 (X, Y)) ~ D +2m++1 where S E (X x , S2 E (X' x 2) and (x, Y) X' x V. Let ( H). According the property of Allat the size of jú is p(n)) and we have
3(H,m))
P(Y ((()) &
For notational convenience, define S' : (52 (X,Y)), S" = (x and enumerate the elements of as
((X1, Yi), ..., 21 12m2+1))
where (X2nz+1, X2ng+1 +1) denotes (X, Y). We now define
N = Σ ly(((x)
ie [2n2]
and
Xa H.s: Xamg R.N.N
= X(npe)) Ia Hil [2n2 + 1] ((X,) & ((X.)) & &N+1].
follows from the property and Lemma H.9 that
E|N = 2n, n1)
(18)
711
and, conditional on S²,
& (2 logg e + 4)d logg(((m))) + 2N + 2).
Sample 1) Unif + 1])**1 independent of S" where (4,, .... Anz) [2ng 1J"
and / E [2m + 1]. Then, we define the sequence T(S', 11) = ((1,, ,..,..., (L Mlnn) )) and the
classifier
i == Ao (T(S' Hs)))
1]. where AG the algorithm specified in Proposition H.5. Since conditional on S" the distribution of each element in T(S', I) is -eaaraaii,,,,,, by Corollary H.6, there exists some constant C" such that
for any i E [2ng +
C'dima
Cidlog(p(mi)) + C2N Cs
Phhs Y11S") &
(19)
72g
11
16

---

for some constant C1, C2 C3 > 0.
For I' (f,,...; (g)) U independent of all other random variables, define
(S', = ((pi(1)) (. ................................ (pi(Kng) xx.(t.,))) where pi [2na] 22n 1J. - klasi+ + (As 1) for all ie [2m + 1]. Consider the classifier
hsr = (c(T" 1),
for each i [2mg + 1J. Since Y; is not used in the construction of hs we can also denote h as hss.. x,, where S" ((X,,))),,. (X,-1, Y1-1), (X1+1, Y++1)..... (X2m2+1, Yen++1) 1)). Thus, treating S = (S1, ~ 2 as the training sample, we can define the classifier hs Da by
hs(x)) == hig4, I,, 2ng+1 (2ne + 1),
where we emphasize that the RHS depends on S through the construction of jr. Then, recalling that (X, ~ D is independent of S, our task is to upper bound the expectated error rate of hg:
P [ns(X) * +V).
We first relate hi hgr v for ie [2n + 1]:
2n
((hsaa()) Vr(5") 3
1
E Lir he , [8")
2n²
2=1
2mg
1
Σ
P(i $ D)
1 hng (0
2n
1
2no+1 1
har hir (5
E
2(2mg + 1)
which implies that
2ng +1
P(h Y11S > 2(2n2 +
E
1
h 1.
1-1
1
2n
I' s²).
E
E
h
2(2 +
Conditional on I' and S¹ for any e [2mg 1] and any sequence (X 2) we let h denote the classifier when replacing S' with s in hsr. ie., N... = Aa(T" 1'), Ha). For any i [2ng + 11, define the set
Ven, B, = {s = ((x1,81).... (1 E (X x 2)2ma+1 (,) # wi
and the permutation
T' : (X' x 2 (X x 2) (21,..., 21) + (21, 24 22n +1, 24... 22nz))
We also define the set
B = =
(12na+11 11) e (X' x 2)
y2ng ()(2mz) yong+1 E fi(22ng and hir 2 + 1) * 3/22+1
We would like to show that T'B) ((11, (1),,,,)... (#2m2+11, 11)++1)) B. we let (c),,() E X x y denote the j-th element of (s(s) for each j [2na + 1]. By the definition of n² and T have
B. for all i [2ng]. For any
( Vr,,)) and (s) (():(T)),r;)). (pi(T (T,)))) WVa
17

---

Define
Σ y)zū((z)) sE(2nz]
ny
Since U2ng E M((2))) and 1/22+11 (1 1), we have
(x)(s) =
Σ uyfeū(a))
Σ
mo8((zz) = nl
je [2
je [e ()((22))
and therefore,
(s) (mj io (t0)
HHaaf ( 12n-11)) 1.8.1
( 12ng (2ng) h Hij E [2m2 + 1] h(a,) (ay))) n +1}
= [Kr((h): E Hs}
where for any h y2 k2(h)) E y2 is defined by
K4 (i) = h(p, (()) + h(2n2 + 1)15=1 Vj E [2nz + 1].
i.e. M() (p)((((()))) for E [2ma] and (22m2 1) (t). Note that n; is bijection from
Hy to H.r1(s)- Thus, for any h E Har(s)) we have
h(p,(t))) N; (1), Vj [n2], and h(i) N; (2) 1). Similarly, for any h E Hg, we have
h(1)) K. (T)) Vj [n2]. and h(2ng 1) (t).
Given the above analysis, we have
T 1) 2 (s, H2) 1)
(T) H (1)
which immediately implies that
ho ((()) NT, 2n +1 (2m + 1) # 92n++1 = vi
and thus (s)s B₁. Since [2ng] and e B is arbitrary, we have T'(B) B, for any i E [2nz]-
Then, conditional on I' and 51, we have
D2 (B,) > 1 DD
Since B = B2ng+1 holds trivially, we have
2ng+1
((hsa(()) # 111
Σ E E I 1 r' St
2(2ng + +)
1
1 1ynn en(Xznp)) 1 Vang n 11) hhy mang (2n 1
2
Taking expectation on both sides and applying (18) and (19), we have Cidlogp(n1) 2C, nn m22 C's f12
Cidlogp(m) + C2E[N N + C3
n12
P(hsrr Yi)
1
E 2
Vang EpI X2ng)
1 2ng 1)xY2nn
18

---

which leads to
P (x(X)) # x
TP hi p 11 (2m2 + 1) o Y2ng+1
EE
Lynng eā( ll 1
+ E
[Vang ( 1Ynn (2mp 1
h N.22 (2ng
PP 2m (((2mm)) + IP (92(2222m)) 22 $ (XX222+1)
2 2(Cidlogp(n) 2C (H, n2 m12 + C3)
n2
(3(H, Cid 2C2 m1), m1) + Cs)
n1
Now, for any N such that 3, setting nı 2/n/3/. no In/3], (8, D
with S E (X' y)" and (x, Y) V. we have
P (hs(X) # x) +x)= = (
((H,n., + +d loogp((n))
Then, when B(H, n)) and p(n) nondecreasing in by Theorem 2.6, there exists learner A' such that for any n > 4 and 8 E (0, 1), with probability at least 1 over D", we have
(A,(AA(S, H) = O 3(H, m1) + d d'logp(n + log(1/6)
D Proofs of the results in Section 2.3
In this section, 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 Ajist satisfies that MA - 7, 12) < op for some y (0, 1/2) and E (0,7/18]. Define the random variable Jk == Lern, (1x)>1/2-1 for any k [K]. Then, have
J
P(Ja 1) E.
Define the event = E Ju > 2vK] }. By the multiplicative Chernoff bound, we have
P(E) =
Σ Ju > 2nK
<E-uKi3 <
K > 3log(1/8) Define Za = Σ. Da(i(2, b))) exp (-a (21 1)) for all & e [K].
Since DK+1 's a probability distribution over S, we have
DK+1(((x),va))
De(((x; exp (-a (21, (.sn((a)) 1))
ZK
exp -ax Σk=1 (21 - -1)
1
[ Zk
1=1
which implies that
Zu
Σ
exp
21 (21xeuete))11)
(20)
k-
1=1
19

---

For any lo e [ we have
7
(x(((2),))))) exp (-a (ema(e))) 1))
Σ
Di(l(1i,
Σ
(EE)(()))
-(1 CrD. (Hx))e torD (#x)e = CTD, (1=) - t
If Jk 0, we have
Zx & y6 + (1- V1-22.
J3 = 1, we have
?
2x e"
1/2 - 7/22 & V 11
Then, under the event 8 we can upper bound
Zz <1 72)0111)
4
k=1
(->K
?
(7 + 4)v)
exp
2
(_>K) 7
8
exp
n
where the second last inequality follows from
& 4(7+4) and the last inequality follows from By (20) and the above inequality, we have that on E
18
K 2 (log(n/))
Σ exp Σ
K
(21 (21 (21merx(x))-1) -1) < 6,
a
(-a ' R-1 (21meepe(m)) - 1)) & 5 for all [n]. follows that
which implies that exp
exp(-f(x; y:)) & 81/ak
for f(x, y) = 1 Σ (21 1), V(z, v) x V. Thus, we have f(z,
log(1/0) aK
2 2log(1/5)
[ [loo(n/8)//l e 1/2-9
log
1/2+>
Since by definition,
f(x,)) > y Xxxx)
we can conclude that on E
YA E m(xz), Vie [n].
ie.. with probability at least 1 8, 8, E u(x;) for all E [n]. Moreover, by da Cunha al. [2024, Lemma 3.3], the randomized compression scheme S - (S²,... ...,. sk) is stable. Thus, we can apply da Cunha et al. [2024, Theorem 1.2] with compression size sn = mK to conclude the proof.
O M (1/22-2.0) log(n/8)
For the proof's of Corollary 2.9 and Theorem 2.10, we will need the following Lemma.
Lemma D.I. If 0 satisfies & alog(x/a) + b for some b > 0, then, have 2a + 26.
20

---

Proof. Define f(x) := 2 a log(z/a) - b for x > O. Then, we have f((x) =-a which implies that f decreases with x for E (0, a) and increases with for a. Since 2a 2b a, it suffices to prove that f(2a + 26) > O) Indeed,
I(2a + 26) = (2 - log a) + - a log(( a + b)/a) > a ((a + b)/a- - ( + b)/a)) > 0.
Proof of Corollary 2.9. By Brukhim et al. [2022. Theorem 36] (choosing t Ivd), there exists an n r sample compression scheme As for any H = y of DS dimension dim( (H) = d < o0 where
r = O(d dl log())) log(n)) with p = O((evd) v
log(n)). (((ee))))oo((n)))
(21)
Then, by David et al. [2016, Theorem 3.1]. there exists universal constant C 0 such that for any D E RE(H), 8 e (0, 1), n e N large enough, and S ~ "D", letting hg == AMr (S, H) denote the output classifier of the above n - r sample compression scheme AM. we have that
C(r C(r log(n//)) log(1/5))
erp(h)) &
n with probability at least 1 8. Thus, for any E (0, 1),
log(n/r) + C' (lo((1/8)
Cr log
n Cr/e
Cr log
(c) C' Clo((1/0)
n 2
+
we have (hs & e with probability at least 1 - 6. By Lemma D.I, it suffices to require
2Cr
Ce
2o'l0)(10)) 2C r rlog +
Ce
+ log 5 (1))
(1))
>
log
Applying the upper bound of r in (21), it suffices to require
n 2 C" (d3/2 d logg(p) log(1/e)
log(n) log(1/5)
for some universal constant C' > By Lemma D.I again, it suffices require
n 2 (d' + dlog(p)) log(1/E) log (dC' + dlog(p)) log(1/e) 2C" 2C' 1og(1/8)
E
Since log(log(1/e)/5) (1/8)/e) = log(11 1/8) + log log(1/e)
& llo((1/e), suffices to require d + dlog(p)
n > C" (dd + d log(p)) log( log(1/s) log
log(1/0)
E
for some universal constant C" > Applying the upper bound of p in (21), suffices to require that n 30 C
(d log(d) + log log(n)) log(1/s) L//=) log
d log d) + log log(n)
log(1/6)
for some universal constant C" > 0. For E = 1/6 and 5 = 1/54, we require that
n > (d log(d) + d dog log(n)) log (og()))((d) d log(n)
for some universal constant C > 0. C1(2(C) 1) 1)d log d) log ((v + 1)d log(d)) &
& dv Fep we have 22 log(d) > d log() and Ci log (d) + d log lng(n)) log(d (/ log(d) + d lloogoo(f log(n))
<CiVV2C, 3/2 log(d) log ( ((V2C) 1)d log(d) n.
2012 201 (d 2d) + d). and
If n >
we have log(log(n)) > loCgd) log(log(n)) > 20 ddg >
Ci (ddd/ + dlog log(n)) log(d 3/2 log(d) + d lo log(n))
<2 <2C,dlog(oggnn) log(2d log(n))
=20 log(2d) log(log(n)) + 20, log(log(m)) log (log log(n))
& log(log(n)) logglog log(n))) & n.
21

---

Therefore, we can conclude that nf > Ci(v2C + 1)d log(d) log ((v2C1 + 1) log(d)) = O log have P(erD (hs) 1/6) 1/54, i...
MA H (1/2 1/3,
1//41//54) 1/54) O 2 (d))-
Let AB denote the multiclass learner output by Aboost Algorithm 2 using AM as the weak list learner of size 1. Then, by Theorem 2.8, we have
2 (d) log(n) d log
A ( O
Vn N.
Next, by Theorem 2.6, there exists a multiclass learner A such that for any D e RE(H), Ó (0, 1),
E N. and S D", with probability at least 1 1- 5, have
er (A(S H)) =0 d 1 (d) log(n) log (1g())))
d8/2 log" log(n)
Setting ö 1/n and observing that erp [0, 1J. it follows that (A.(()) 0 Moreover, by Lemma D.I, for any e (0, 3 O a log" log(d/e))log(1/))) implies that er H)) & with probability at least 1 - 6. Thus, we have
MA = log (d) log(d/s) + log 1/0)
Proof of Theorem 2.10. By Brukhim et al. [2022, Theorem 39] (choosing t = [vd]. there exists an list sample compression scheme Aist of size O((evd) v log(n)) for any H y of DS dimension dim (H) = d < ao where
r r= O log(n)).
(22)
Define the following loss function for menus 14,
E(p, (z, v)) 1 pee(()), V(z, v) E X
Then, we can apply the proof of David et al. [2016, Theorem 3.1] with the loss function E to show that there exists universal constant C scheme ALsC for H. any D e RE(H), 8 e (0, 1), n E large enough, and S ~ D=, letting μs = ALsc S, H) denote the output menu, we have
such that for any
list sample compression
erp(Al H)) = E( H), (X,Y)) S] < C(rlog(n/r) + log(1/8)
with probability at least 8. Thus, for any E (0, 1).
Cr log(n/r) +
C' Colo((1/))
Cr log Cr/E
+ Cr
log (9)+ C' (log(1/0)
we have erD (S, < with probability at least 1 - 8. By Lemma D.I, it suffices to require
2Cr
Ce
2C log(1/0) 2C'
Ce
+ log )1))
n >
log
r rlog
&
Since Allec is an - r list sample compression scheme for H with bounded in (22), The above results imply that in order for (Perr (S, H)) e) & 8, it suffices require
(3/2 log(1/s) log(n) + log(1/0)
C"
E
for some universal constant C' > 0. By Lemma D.I again, it suffices to require
232 2C'd8:21og(1/6
TeC' (1/8///og(///))) log(1/e) (eC'))2log((/e) 2C' 1og(1/5)
3
log
22

---

Since (og(log(1/e)/3 = (0g(1/E) + log (///) < llgg(1/)), it suffices to require
n = C" d 1o d/e log (L/E) log(1/6)
log
for some universal constant C" > 0, which implies that
M (1/2 - 1/3, 1/54) = O (dg(
Now, we can define Ap to be the list learner output by Aboost in Algorithm using Aust as the weak list learner of size O((ev d) v log(n)) for training sample size N. Then, by Theorem 2.8, have that for any training sample size n E N,
d d log(d) log(n)
(n),
and the size of A, is also (((evd)
E Proof of Theorem 2.11
Proof. By Theorem 2.10, there exists a list learner AL with p(H,n) =((eev)) log(")) and 8(H, n) (d log(d) log(n)) for any N and concept class H = y with dim d e N in the context of Theorem 2.7. Thus, by Theorem 2.7, there exists multiclass learner Amulti A'aa such that for any D E RE(H), any 5 E (0, 1), D", and mi 2[n/3], with probability at least 1- 5,
B(H, m1) + d log p(H, + (og(1/))
(Amiimit (S,H)) =0
8/2 log (d) log(n) + 8/2 log(ev/ log (n)) + log(1/0)
=0
d log(d) log(n) + log(1/6)
n
For any E e (0, 1). by Lemma D.1,
3/2 log(d)
5 log(d (/e) +
log(1/8)
1
+
2
3/2 log(d)
3
2 log((/))
1 log(d) + log log(d) + log(1/e)
E
2
3/2 log(d)
3/2 log(d)
2 log(116)
log
then, we have
3/2 log(d) (d) >
log(n) log(1/8)
i.c.,
/ log(d) log(n) + log(1/5) E.
n
follows that
M M(E, =0 =0 (fd log(d) log(d/e) log( (o/()
8
(9) follows directly from (6) by plugging in p(H, (d) and ((H, f2(d) for d dim(H) and any n E N.
23

---

F
Classes of DS dimension
In this section, we present the proof of Proposition 3.3 and Theorem 3.2.
Proof of Proposition 3.3. Let E, denote the edge set of the hypergraph g(V.). Suppose on the contrary that there exists cycle consisting of pairwise different vertices yd ...... y yn e Vn and pairwise different edges e" = fe fo)...., emm (eem 1.fm 11 mm-1) E En for some m e {4...., |V, such that yd, y mod m (e 8;) for all 0 & J & m 1. Since the edges are pairwise different, by the definition of En, we have ij # i(j-1) mod for all & j & m - 1.
Define a a= im-1 [n]] b =- in E [m]. Do = va ya. p-1 = Va + Po. and qo = vi yb Vb! Then, have b.
For any ls N, we define
jk == max(j E No j m 1, va = Pk-1);
(1k +1) mod and 9k v/." y/ (J++1) +1) mod because رj{ Define y/a
Pk:
K = min e N: Pk: p-1}-
By definition, we have Po,... po...., PK are pairwise different. There are two cases depending on the values of .1..... 9K as follows.
1. Suppose that there exists some k [K] such that 9N # qu- Define to : 0 and
I min k [K] k 1 Ok
for all w N with the convention that inf Ø +00. Define
v max
Lw * +00].
We have e E [K] and at
* - for all w E [v]. Note that
p-1 = PK = Vo m-1
go 1/b
Pla = Po = Vaa
9 = go
= Yb!
tw-
Pl = ya
q 1
yn
Pl 1 ya
qu y d
qi... yb 11
Ph.. = Va
for all w [v]. and
PK P-1 jx
9K =
Since it always holds that 9к = q. there are two cases depending on the value of n. and go as follows.
1.1 Suppose that ạ * go. Then, Val(a.)) contains the following pseudo-cube of dimension 2:
(ph-1190 1, qu),
(pi, 111-1: 1, 9 (Pia- 1, 91.) (Pig-1.
(pi, (Pt.-111 W. .),
(pi.-1, 1, ).),
(p-1, )
(p-1. 90),
which contradicts the assumption that dim( Vn) 1.
24

---

1.2 Suppose that qu, = 90- Then, (al(a,)) contains the following pseudo-cube of dimension
2:
(pt, 1,, q0):
(pi, - Q1,
(Pl, 91
(pt,-1, 112),
(Pt,-1: 91.
(pt.-1: 91, q0),
which contradicts the assumption that dim( Vv))
Thus, Case does not exist.
2. Suppose that qi Qo for all [K]. Since ya Po Po- 1b
90
Q1
P and
y * y"i there must exist some e [n]] fa. b} such that y. y.--
y
y. * y y
We define To := v.. and Fj := yd y. for & E [K]. There are two cases depending on the value of rk for [K] as follows.
2.1 Suppose that there exists some E [K] such that rs * TT. Similar to Case 1, we define to == 1 and
w =- min [K] k 1w-1, ri
for N. Define max(w E N L * +00). We have V [K] and riw * T
for w E [u]. Note that
p-1 = PK y To De
Po Va
To Ve
Po vhl
Tlo 1i Ve
t 1+1
Nw 11+1
Pl. 1 = Ya
Mhe = We
Pl., 1/
The v.
for all e [u], and
PK P-1 vaa +1
TK = v2 11+1
Since it always holds that r'K = rt,, there are two cases depending on the value of gr, and qu as follows. 1.1 Suppose that rı. * ro. Then, Val(a,o) contains the following pseudo-cube of dimension 2:
(Po, ro),
(po, rl = r1);
(pt rla);
(pi. )
(pt,- r(,-));
(P1,-1,
(p-1, Tt.),
(p-1,7o),
which contradicts the assumption that dim dim(),) 1.
25

---

2.1.2 Suppose that = ro. Then, (al(a.)) contains the following pseudo-cube of dimension
(po, ro);
(po, F1p = r1):
(1t,-1, 1%0)
(1,
(pi, (1,--1 11o-1
(pt.-1,77 r1, ro),
which contradicts the assumption that dim(V,) 1. 2.2 Suppose that Tik = rı for all E [K]. Then, we have
Ya ya-
To ye
Ve Po ya
0
p-1 ya x
v22 x
TI
which implies that (a.e) contains a pseudo-cube of dimension 2.
Thus, Case 2 does not exist either.
In conclusion, there exists cycle in the hypergraph G(V.) = (Vn, Enn
Proof of Theorem 3.2. It suffices to show that the for any N and V, _ )", the average degree of most
G ((V)) (V, F.n) with [V,l oo and di,(V,
We prove by induction on [Vr] When [v/] = 1. we have E. = Ø and avgdeg( = 0 < 2. When and avgdeg(G) &
|Val 2, have > |el
Suppose that avgdeg(G)
for any Vn size [V, & m with some m N. When VV] = m + 1, since there no cycle in G according Proposition 3.3, the set of vertices of degree (V,) {y Vn, deg(y) 1}) is not
empty. Define V2 == V, V. and E to be the edge set such that (V? ERA) is the one-inclusion graph Val
on V22 Then, have V
[V/||
and
Σ
lel
Σ
|e| + 2
66 E. 0//32
et B2
because deleting a vertex of degree decreases the total degree by at most 2. By the induction hypothesis, have Eeery |el & 2 Thus,
Σ
lel & 2(V2 + (V2 V/
which implies that avgdeg G)) < 2. By induction, avgdeg ()) < 2 for any V, with [Val < oo and dim(V,) 1.
G
Pivot shifting
In this section, present the proofs of Lemma 3.6 and Lemma 3.8.
Proof of Lemma 3.6. For notational convenience, we let V denote B(V..) which is defined in Definition 3.5. Define
Vn-1 := U ( E ym-1, ( 1n-1,8) 8) E Va}
yEy
26

---

and
V"-1 == Vn-1\Va-I
Let E, denote the edge set in ((V))) and En-1 denote the edge set in G(V For any y define
Va,y {1V1..... Un) Vn Un y, (V1...... Fn- Vn-13.
By the assumption on a V/ we have [Val |V + Eyey Vnyl. IV VV and [Va
[V--1| = Σ [we)((o) [Vn.l Defining
F = {(ei,s 1) En i n):
we have
Σ (|e|-11 1V-- 1V
Fm
For any y E V, we define
En = ((eu, En f(n) y, [n 1]}
and let F, denote the edge set in g(Vn,)); for any (ei.f, E Emy: we define
(1 == Hy e y V Vn and s2(e) := Hy ear y & Vn.yl.
Then, we have |e| = se + s2()), En = (UneyEnnn) u En and
Σ (|e) 1)
eEEn-1
Σ
(I
Σ
Σ
(x2(e) 1) +
Σ sa(e)) (EEe,vie
cEEn.a
(a)
Note that by the induction hypothesis, we have
Σ
V
e
and by definition, we also have
Σ EE D.
1)=
Σ (81
(si(e) 1).
We claim that dim(Vn.)) & d- for all (a) Suppose on the contrary that dim Vn.g) > d - 1. Since dim(V,) d, have dim(yn.y) d and there exists set i i= (a1.-.., id) [n] with i < is < ... < ig such that Vn contains a pseudo-cube H, of dimension Since for any (yI...., Un) Vn we have Yn = y. must hold that id & n Now, we can define
Hy. = (1h...... Vl. a) E y (yh,...., 9is) E Hy} Ul Vi v) E gott1 (Yi, (y:...... ..... Vi.)) E Hy).
By the assumption that IV--1l = IVnal we have HHyal = 2| and Hy S Valin...aan. For any & [d] and any (Yiys....y Mher H): (yi...... Biss a) E Hy since there exists an k-neighbor of (J....... Wig) denoted by (Vi...... V ......... (ia) in Hy, (Vi.,...,'', :/g,, of (W)..... a) a) Hy. and vise-versa. Thus, Hy a pseudo-cube of dimension + which contradicts the assumption that dim(V,) & d. Therefore, must have (im(Vn.)) & d 1. Then, by the induction hypothesis, we have for any E (a),
Wirr y²) Hy is k-
neighbor of (.i..... Wig. s/' in Hy for y' y, Moreover, (Wi,..... ,.......,....................... y) is (d + 1) -eeiihh
E(ell
(lel - 1) & (d - V).l..
27

---

Summarizing the results above, we have
Σ (|el 1)
Σ (lel 11 + Σ Σ
(le)
1)
yey Eniy
Σ <E
(lel -1 1) + Σ
(lel 1)+
e
Σ yE)i(a)
Σ (82(e) - 1) +
Σ
82(e) +
Σ
(s2(e) + (81(E) 1))
eEEn, 1:8 (e)=0
(e))
eE eEEn, (e)32
Σ
(lel 1)+
Σ
(lel 1) + Σ
Σ
1))
Σ
82(E)
oF F
BE Fina
yE)i(a)
(e))
(()))
Σ
Σ
(si(e)-1 -)
(a) E yi (c)32
</V/l 1oa1-1V-111
Σ
(le) - 1)+ + Σ
Σ ((c) 1)
eEEn-1
yE)i (aa e
</VVl - -V + v +
(d - 1)
(
-VV 11 -V + V + (d 1)([Val - -Vn-1l)
V.l.
Proof of Lemma 3.8. Consider arbitrary N((1] and V, S _)n By the definition of P. (V,), (V)). have |V [Va] Let E., denote the edge set of G(V,) and En.y denote the edge set of 9 (V)). It
suffices to prove that EesE, (lel 1) LoeE,,, (lel 1). Define
E { k) E E, k i} and Eny = {len, k)) E En.y k i3
for all ie [n]. By the definition of Vi we have
Σ (lel 1)
((el
Σ (lel - 1). En
(23)
CE E
For any i [n] and f [n]][i] - V. we define
ci ((11........ Un) E Vn : yk = fkk Vk e [n]]((]] and
< = (WV1...... Mn) V7
= f(k) vk E [n]M[]
distinguish edges in E., and En.y. For any y E V. i [n 1J. and ʃ [n- 1]((0 >V, define fg : [m]][]] - y such that Vyl[m-1J/60 f and [n(n) y. Then, we have
Σ
(1ei,y1-1) -
Σ
(1e7,,111 -1
VE)M DEEE
< (e DEB.,, (1e), 1) Mee.sa (les,5al 1)
which implies that
Σ 1Ic & Σ Σ (lel-1) - 1). 1=1 ct Ex
1=1 e
and from (23),
Σ
((l-)) &
Σ (le-1)). 1).
Thus, can conclude that avgoutdeg( ((V))) (rgoutdeg(G(VV))) for any E Ta....
28

---

H Lemmas regarding graph dimension
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.
H.1 Learning algorithm for classes with finite graph dimension
We first provide the definition of graph dimension.
Definition H.1 (Graph dimension). For H. = yx and n E N, x (x1...., II)) X is said to be G-shattered by H. is there exists f [n]] y such that for any i [n]. there exists g E H satisfying g(x,,) f(i) for all E i and ((ra)) # f(i) for all i e [n]]i. The graph dimension of H. denoted as dima (H) is the maximum size of G-shattered sequence.
Define Log [0, 00) - [1, = log(z v e) where v max(x, ej. For any H. S V E [dimg (H)), and
1 _ X that G-shattered by H. there exists f [m]] - such that for any = [n], there exists E H satisfying g(x;) = f(i) for all i e i and g(x;) + f(i) for all
i [n]]i. Thus, we can define
H(()
h [n]
{0, 13, Mav= h H}.
For general n e N, x S X with [x| and f E )" we define
Mx(x): = h:: [h:[m] 13, - ((())-((o) h e H} and
TH( : sup sup [H
xEx:|M/n fE)
Note that rH(n) [H(x)] 2 for any [d)m We have the following lemma.
Lemma H.2. For any H = yd with dim d, we have TH(() & Ed (t) In particular, if 2 d, then Tn(()) & (en/d)".
Proof. We first prove by induction on n that for any x (ai..... nn E X and f y
[x] < xxx x 7 G-shatters x'|).
(24)
For n 1, is obviously that (x)] & and [[x S H G-shatters x') 2 1. If [f x H G-shatters x'}| = 1, then x is not G-shattered by H. which implies that [x)(()) & 1. Thus, (24) holds. Now, suppose that (24) holds for any n. Consider =
YO = {(y2...... .y)) E {0, 13m- m- (0, 12.......4.. .n) Hy(x) or (1, U2..... Vn.) E Hx(x)), and y1 = ((12,..., ,.)) E {0, 11n-" n- (0, 10.3 ,,) )
Hx and (1, .......,.... E (x)))
We have (x)(x)] | + | and |Y 174 (x) Then, by the induction hypothesis, we have
and H G-shatters x3}. Yr & [x x H G-shatters x')| [xx = x : $
For any y V, define
H = (h H 3hE E H s.t. A/x and h'Ix differs only at and y e (h(x1), (M(x)), (xxx))
Then, H G-shatters x' implies that H G-shatters x' o (m.). We also have yz H (x). follows from the induction hypothesis that
|Y'| = H (0) (x) & 1[x xx: HF() G-shatters x') & 1[x S x: a E x' and H G-shatters x'}].
In conclusion, we have
[x) =|r01 + +|
(x' Ex:rı $ x' and H G-shatters x3I1 + 1[ ex:r x and H G-shatters x'M
= (x' 7 G-shatters x'}|.
29

---

which is exactly (24). By (24), we have
TH(n) & 1x SES x: H. G-shatters x
Σ n
1-0
For any (measurable) classifier h X' - y, define
(h(h) == {(z, y) E X x y h(x) # y).
Then, for any probability measure D over X' V
define
crp == (())(h)) = ((xx))-D(((X) # Y).
Definition H.3. S S X D' is said to be E-ner (E (0, 1)) for H s yx with respect distribution over x y for any E H.
eh
ER(h) n S == E S h(z) + y) * #8.
For any integer n e N. set 2, and 7 (21,...,, E 2", we say = T if = i; for some e [m] and use [T' denote the length of the sequence T. For notational convenience, we use Ø to also denote an empty sequence (a sequence length 0). For any subset E s Z. we use T o E E T denote the subsequence of T consisting of all elements in E, i.e., for I = (i [m] zz E},
To E EOT (zi)ier-
Then, we have n EJ = =
Proposition H.4. For any H = y* with dimg(H) any H-realizable distribution D, any E (0, 1]. any é N, and any ERM algorithm A, consider Sn ~ DD. With probability at least 1 - 8. we have
22e
d ))
(AD(A(S,. H)) & n
d v dogg
loga
Proof. For any and E [2/n, 1]. define
B = (5 (X' x ")" 3h H s.t. er)(h) >< e and ER(h) n S = O and
B' = ((8,7) (X' x y) |S| [T |n]. 3h E H s.t.
erp (h) c, ER(h)
Ø, and ER(h) T en/2).
Let (8,T) ~ D22n with 5,7 (X' x ")a Since (S, 7) B' implies that E B, we have P((S B') EL (S.))e 1s Bl B'(S)]
On S E B, there exists h E H. such that er (h) > s and ER(h) = Ø. Then, ER(h) > en/2 implies that (S,T) e B'. follows that
B'[S) ((E()))))( n T|> en/2|S).
Since T is independent of S, h is determined by S. and (EE(h)) = erp(h) > on S B, we know that on S B. [E(h) n T' follows the Binomial distribution (nn, (h) conditional S. and
Ls BE [ TJ|S] = (r)(h))ss > enLseB.
Thus, by Lemma H.8, since
have
1 ((ER)()))()) o T| & en/2[S) < P(ER(h)) o e1p(())22)))IssB o Ise
which implies that
P((ST)) E B')
P(S B).
2
30

---

By the definition of B', we have
P((S.T) 7) E B¹)
E
sup 1
LkE
IE
sup 1 bmmdd//eeddaaaaassssssssssaa/sas LiEH
SE
sup ER(A))S=g) (B00://SS--1BBBB)))((s))s))))) [ER()))( kiE
For any m N, r ((21.81)..... 11)...................... (Ims vmm) E (X' x y)m" and y we define
hr [m]] - 10, 1) - h(x.)=
and Hr (hr h H}. Note that Hr Ho. ((11, km)), which implies that
HHr TH(m).
(25)
For any & E [m]] and 1 < i <............................... < i < m, we use (() to denote a permutation of r where (ry, yj) appears in the ł--th position for all j [R]] specifically, [(fi...fa)) (Irr()): (i)( [e[n] where a (iz) := j for e [k] and (o()))ee( == (k I....,m) m). Then, for any [2n]
with i n, have
sup ( keH
10)01, vie[)]
Eiefon) -2i (2)22))))
kEM(s.T) Σ NEH:s.D
100=1, wai Eiqpo) (21)(22-
Since (S,T) ~ D2n, we also have
Σ
-1)))11,
Ei (20)<((-)/2)))
= EE
Σ
1x())1, vie He ((1)<(2-e/2)))
h
hEH(S.T)
Thus,
E
sup 1 E pe (S(N)
heH
Σ
E
Σ
1n(-11 Viei Il Eispan (22)<(2-)/2)))
(n)
is [2n]. 1|
hEM
Σ
E
Eiston ((1)<(2-e/2)))
1x()=11, Viel
(2n)
(EH(
ic [2n]: =
(122-//2)m)
Eiqenn ((0)<(2-e/2))
2n
2 en/2
Iiid (())<(2-e/2))
(26)
he
cn/2
[[((s,))
2 sn (2n),
(27)
where (26) follows from Lemma H.7 and (27) follows from (25). Finally, have proved that
D²(B) P(S E B) 2PS((S 7) B') & (2x(2))2 -2n/2 en/2
(28)
Since is H-realizable and A an ERM algorithm, we must have A(S,, H.) E and ER(A(S,, H)) S, 0
31

---

almost surely. Moreover, by the definition of if that (A H)) E. Thus, we have
if S, $ B, then (R(A(S,, H)) n Sn = Ø implies
IP (errp( ((s,. H0) < <<)
P(S, B) = 1 (B)..
Solving 2TH (2n) (2n)2==mn)) en/2 8, we get
E=1ı 2 1ogg(T:(2n)) + log2
2 8 )
2 d
Zen )) + logg
2 (
d dlogg
where the last inequality follows from Lemma H.2. Note that 1 1 (Iog2(TM((2)) (2n)) + loga (3)) >
2. which implies that the above choice of is legitimate. Applying (28), we can conclude that with n
probability at least 1 1 6,
2 erp(A(S,, H)) < n
(d dlogg d
2en
))
5 )
logz
Proposition H.5. There exists learning algorithm Ag such that for any H = y²x with dima (H) = any H-realizable distribution D, any E (0, 1], and any n N, given Sn DD, it holds with probability at least - 8 that
erp(Ac(S, H)) = 0 (# d+ Log ( )t)
(29)
Proof. The algorithm Ag is the algorithm S,, Majority (ERM#) (S, 2))) defined in Hanneke [2016], where ERM, denotes an ERM algorithm on the concept class H. Applying the error rate of ERM algorithms proved in Proposition H.4 in the proof of Hanneke [2016, Theorem 2), we establish (29).
The above proposition immediately implies the following corollary on the expected error rate of the learning algorithm Aç.
Corollary H.6. There exists a learning algorithm Ag such that for any H S y with dim d. any H-realizable distribution DD and any E N it holds that
Es,-DD (erp(Ac(Ss, H0)) (X.)) [Ac(S,, HX(X) Y]
(30)
Proof. According to Proposition H.5, there exists some constant > 0 such that for any 5 e (0, 17.
it holds with probability least 1 8 that
cr H)) & C' d log 8 ve))
which implies that for any > C(d+1)
n
P ((Cr(AA((S, H)) 1) - xd
Since (Ac H)) is nonnegative, we have
E [erp(Ac(S,, H))] =
((erD(Ac(Snn H)) > t) dt
C(d+1)
0
c +d
n
O(d-11
=0
n2
32

---

Lemma H.7. For any n. E N and m E N n [n, 2n]. we have
< 2m
(31)
2m
Proof. Note that
m
m(m .).... (m 1)
22
2n(21 2n 1)... (n + 1)
We prove by induction on m. When m 2n, we have
2m-2n
Suppose that (31) holds for some m N n [n + 1, 1,2m..
Then, we have
m
1
2
2m
2m 2121-
2n
m
2n
2
Thus, by induction, (31) holds for any Lemma H.8. For X B(n, p), if up 2, then
[n, 2n)
P(X < 2p/2) 1/2.
Proof. If np > 8, since B[X] = np, by the multiplicative Chernoff bound, we have
PPX np/2) mp/8 <e- & 1/2.
For np have
[np/2]
Σ ('11- p)
P(X & np/2) =
For < pm E 8, we have 6/n < < 8/n and n 2 Thus,
pp - (1-p)m F(X & np/2) = Σ 1
3
n
Consider
fa(x, p) log(x(2= 1)(x 2)) (x 3) log( 1 p), x x> 6, 12.13p000 6/2.
Fixing p (0, 1], we have > 6/p and for 2 6/p.
2a fa(x 1 x- x-2 log( 1 p)
à
1
2
p
p
p
p
6
6-p
6 6-2p 2p
Thus, fixing pe e (0, 17, fs(.p) is decreasing function [6/p, o0). Therefore, we have
fs(x, & fs(6/p.p),
which implies that
ga(r,p) & go(p/p.P)
for
9s(x,p) : x(x 1)(x - 2)
p3 (1 p) p (0, > 6/p.
6
33

---

Since log 2-2+1 +1++1000 < 0 for 2 E (0, 1] and gz( = log -- for g(2) = = -1- (1-2)
defined on E (0, 1], we have
0 0= & g(2) $
lim g(z) 1/2 +
for = (0, 1]. Thus, we have
(1 2)
1-2) 2
log(2) +
3= 0.
Plugging in z = 1- 6/6 for > 6, we have
log(1 ( 6/t(1 - -3/t)
0.
1- 6/6
Then, defining
f(t) == ltg(t) + log(t - 1) + log(t - 2) -3log(t) + (t- 6/t), t t> 6,
we have
1 + log - 66/t) + 6/t(1 3/t)
f'(1) -10)
6/6 > 0,
which implies that f(t) increases with t for tort= > 6. Since
ga(6/p.p)= = 6/p(6/p ()(6/p 2) p3 (111))6/p- 0/0/p-3
6
and
1 = 111 - =01-
1)(1 (1--22)(((1110 (1-
we know that ga(6/p. p) decreases with p E (0, 1]. Thus,
t(t 1)( 2)
fs(6/p.p) < lim ga(6/p.p) = lim
(1- 6/t)*=3 36e
p
10200
6
Following the above steps, for
92(2,p) p) 2(x - 1) p²(1 p) m
2
91 (2x p) == sp(1 - p)=-1, and
go g0 p) = (1 p)?
where p E (0, 1]. x > 6/p.
is easy to prove that for any i 0, 1, and p E (0, 1].
9 p) (6/ppp x lim (6(ppp.)) 4-
Specifically, we have
t(t - 1)
(x < lim (0:
2 (6/1)2(1 6/1)²-2 = 18e
In (x. & lim t(6/t)(1 - 6/t)²-1 -6 and
9o (x. lim (1 6/t)* -
Then, we can conclude that
IP(X & np/2)
<
Σ
sup 12/
9x(x,)) (36 18 + 6 1)e
1
2
0
34

---

Next, we consider the regime that < np < 6. Now, we have
Σ pL p)
n
P(X & mp/2) =
sup
[r p).
T- (001))
Following the procedures in the previous case, it is not hard to verify that for = 0, 1, 2,
4 (1 - 4/t)*=+
4'
sup 2//4
ge(T.p)
lim gi(4/p.p) p-u
lim <
i! e
It implies that
n2 p² (1 p) m)
4
1
P(X & np/2)
i!
2
i-0
1-0
Finally, we consider the regime that 2 & np < 4. Now, we have
P(X & np/2) (1 p)" + np p)=
sup
91(2,p).
Following the previous procedures, is not hard to verify that for 0, 1,
2
2
g:(x, p) lim (2/p..))) = lim (1- 2/t)
sup 23///// p-0
i!
It implies that
1
P(X & 2p/2) &
2
==
In conclusion, np > 2, then
1
P(X & np/2)
H.2 Bounding the graph dimension
For any H s yd of DS dimension dim(H) = d < 0,, sequence = (zi,...,, In) E X", menu
p: X (Y / |Y| & p} of size e N with N, and d' E [n], define
H. [hls h H. ( [n]] : M(a))) u(x:)) & d
Hs = (h|s h E H. (i E [m] h(xz) & ((x,)) s i) and
Hs = h:: [m]]] - V, h((1) Hssws
for all i [n] which denotes the collection of all subsets of [n] of size d'. We have the following lemma.
Lemma H.9. dima(Hs,,.))) < (e)g + 4)( (p) + 2d") for any d' [n].
For any ie 2|m] by Bendavid al. [1995], Daniely and Shalev-Shwartz [2014], we have dima(H's,ul & 5 (pg (7'ss & (p) 5d logz(p).
Proof.
For any j C [n] that is G-shattered by Hss,.. define j' : j.i. We have that li'l > li - d' and i' is G-shattered by H's which immediately implies that [j'| & dima(H's,.) & 5d (ogz(p) and
1i' + d' & 5dlogg(p) d' It follows that
dimo(Hs,ul & ldga(p) + d' =: dj.
35

---

For any m E N and = such that for any K [m]] there exists g H.S..aa satisfying g f(k) for all K and
- [n]] that is G-shattered by Hs,,.dr, there exists f: [m] y
g(ie) f(k) for all E [m]]] K. It follows that a. (i)l 2 If m > d', by Lemma H.2, we have
di
2
a (i) &
Σ
(Hls,aas())
&
Σ (m) &
2 v
em
d1
12
1:21
which implies that
E di (I log2
) + log2
m
< d1 (Iv
em
log2
d' log2
d'
dj
d'
By Lemma H.11, we have
m $ (2 + 4) + d²) = (2log2(e) + 4) + 2d"),
which implies that
(HmG(HSsuii (2logg(e) 4)(5dlog2(p) 2d').
Lemma H.10. If x > 0 satisfies & a (og2(2/00 + b for some a, b > 0, then, we have x & 2a + 2b.
Proof. Define f(x) := x a (1/2 for x > Then, we have f'(x) implies that f decreases with for I E (0, log(2)) and increases with x for x > a/ log 2). Since 2a 26 a/ (2), it suffices to prove that f(2a + 26) > Indeed,
log 2) which
f(2a 2b) + b loogz((a b)/a) ((a + b)/a loge((a b)/a)) 0.
Lemma H.11. Ifr > 0 satisfies x & azogg(z/a) + (x/b)( + for some a, b, c > O, then, we have & 4a 4b 2c.
Proof. Since
x Ealogg(z/a) (blla))bbblog blogg (llg)(//b) +
loga b
= (a b)++blogg
a a+ c (a+ b)
log, a b
a a
a + b
<(a loga a a+b +
by Lemma H.10, we have
2(a + b) 2(a + b c) 4a 4b 2c.
36

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: In our abstract and introduction, we make the main claims that this paper reduces the gap between the lower and upper bounds of the multiclass PAC sample com- plexity and propose two possible routes towards completely resolving the optimal sample complexity, which are the paper's major contributions and scope.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification: As is shown in Theorem 1.9, though have reduced log factor, there is still (d) log(d/e) (d/=)) gap between upper and lower bounds of the multiclass PAC sample complexity. We leave the development of sharper sample complexity upper bound in Open Question 1 and Open Question 2.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well well-specification asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested few datasets with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
37

---

3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification: For each of our theoretical results, we provide the full set of assumptions in its statement as well as a complete and correct proof the appendices.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated referenced in the statement of any theorems. The proof' can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [NA]
Justification: The paper is fully theoretical and does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is a dataset and/or model, the authors should describe the steps taken make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access the model. In general. releasing code and data often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how replicate the results, access a hosted model (e.g., in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
4.1 If the contribution is primarily a new algorithm, the paper should make clear how to reproduce that algorithm.
4.2 the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
4.3 the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
4.4 We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (c.g., to registered users), but it should be possible for other researchers have some path reproducing verifying the results.
38

---

5. Open access to data and code
Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, described in supplemental material?
Question:
Answer: [NA]
Justification:
The paper is fully theoretical and does not include experiments.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (uttps://nips.
wrriiissssnooollooo onPolicyl for more details.
While encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https: gwt////i//////e////g
/ //nips.
for more details.
The authors should provide instructions data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [NA]
Justification: The paper is fully theoretical and does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [NA]
Justification: The paper is fully theoretical and does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi-
dence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
39

---

The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful figures symmetric error bars that would yield results that are out of range (e.g. negative rates).
show in tables or
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [NA]
Justification:
The paper is fully theoretical and does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary failed experiments that NeurlPS Code of Ethics https: //tp:r///.......eeeeeeeee http://uurriscccppupb.eee cctpublic/Ettiiecceceececoo htw.hi///eehiscileeeeeeleeeeee
didn't I make it into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the
Answer: [Yes]
Justification: The research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive socictal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: There is no societal impact of the work performed.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
40

---

Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), faireess 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 direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that 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 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 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 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 monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper deseribe 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)?
Question:
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 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 best faith effort.
12. Licenses for existing assets
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?
Question:
Answer: [NA]
Justification:
The paper does not use existing assets.
Guidelines:
The answer NA means that the paper does use existing assets. The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include 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 use in package should be provided. For popular datasets, paperswi wwwode.hcoe...c. com datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
41

---

For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's s creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
The paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details the dataset/code/moodl as part their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
42


Reviews:
[{"review_id": "Fj4jt7WrRa", "reviewer": "Reviewer_wmES", "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.", "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": "None", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "The main strength of this paper is that it addresses one of the most fundamental problems in learning theory -- the complexity of multiclass learning and provides an improved bound on the sample complexity.", "weaknesses": "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.\n\nThe technical improvement is rather weak (some log factors) and doesn't address the main gap (polynomial gap in d).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for reviewing our paper. Below, $d$ denotes DS dimension and $d_G$ denotes graph dimension.\n\n## Graph dimension \n\n* The DS dimension is the right quantity to look at here. \nThe optimal multiclass PAC sample complexity is described by DS dimension and **not** by graph dimension. \nAs is stated in line 26-28, [1] showed that a concept class is PAC learnable if and only if its DS dimension is finite. \n[2, Sec. 6] showed that finite graph dimension does not characterize PAC learnability by proposing a PAC learnable class with **infinite** graph dimension. \n[3, Example 1] provided a family of concept classes $\\mathcal H_i$ for all $1\\le i\\le\\infty$ such that $d_G(\\mathcal H_i)=i$ and $\\mathcal M_{\\mathcal{H}_i}(\\epsilon,\\delta)\\le \\log(1/\\delta)/\\epsilon$, indicating that their DS dimensions are uniformly bounded.\n[1, Example 8] is a concept class with DS dimension 1 (thus it is PAC learnable) and infinite graph dimension.\nThus, graph dimension cannot appear in the optimal multiclass PAC sample complexity. \n\n* By the above examples, graph dimension cannot lower bound the PAC sample complexity of general concept classes. \nThe best upper bound using graph dimension is $O((d_G(\\mathcal{H})+\\log(1/\\delta))/\\epsilon)$ by our Proposition I.5 (see also line 226), which can be infinite for PAC learnable classes. \nBy [3, Example 1], the optimal upper bound cannot depend on graph dimension, and the above upper bound can be arbitrarily worse than our upper bound using DS dimension as our upper bound is always non-trivial with a finite gap of at most $\\sqrt{d}\\log(d)\\log(d/\\epsilon)$ from the optimal bound for PAC learnable classes. \n\n* Moreover, Daniely and Shalev-Shwartz [4] did not provide optimal bound on PAC sample complexity in terms of graph dimension. Instead, in [4, Conjecture 11], they conjectured that the optimal bound is given by DS dimension. In the last paragraph, they wrote \n> it is known (Daniely et al., 2011) that the graph dimension does not characterize the sample complexity, since it can be substantially larger than the sample complexity in several cases.\n\nWe will include the key points in the above discussion in our revision. \n\n\n## Technical summary\n\nWe believe that it is necessary to include enough technical summaries to introduce results and ideas. We made efforts on providing sufficient motivation of the technical summaries. For example, in Sec. 1, we reviewed existing results in multiclass PAC learning in the first two paragraphs, motivating the introduction of the concepts in PAC learning in Sec. 1.1. In paragraph 3 of Sec. 1, we previewed our reduction to list learning, motivating the technical summary of list learning. In paragraph 4 of Sec. 1, we provided the motivation of the pivot shifting in Sec. 3. In Sec. 2.2, after the main result, we provided a technical overview in line 229-241 to explain the key points of the proof. In Sec. 2.3, we provided the intuition of Alg. 2 in the first paragraph. In Sec. 3, we built the technical summary on existing results to explain the motivation of upper bounding the density and pivot shifting. \nWe will elaborate more on technical summary in the revision. \n\n## Comparison with previous work\n\nWe believe that our paper makes adequate comparisons with previous work. We compared our upper bound to the previous best bound (line 39 and 120) in line 49 and 288. We mentioned that a potentially sharp lower bound on PAC sample complexity is still missing in the literature in line 37 and 124. In line 244-251, we compared to the list sample compression scheme in [1] to explain how we saved a $\\log(n)$ factor using sampled boosting. \nIn line 268-271, we compared to the bound of directly invoking the learner in [1] to Alg. 2 to explain how we avoided a $\\log(d)$ factor using list learning. \nIn Prop. 3.1, we reviewed known results on density to explain the reason of bounding the density. \nIn line 329-334, we referred to the induction technique in Haussler et al. (1994) to motivate pivot shifting. \nIn line 348-352, we compared pivot shifting to the standard shifting technique. \n\n\n## Technical improvement\n\n* We do not think that our improvement is weak. The optimal PAC sample complexity is a fundamental and difficult problem in statistical learning theory. The characterization of multiclass PAC learnability remained open for decades until recently solved by [1]. \nThe improvement of log factors in sample complexity is highly non-trivial: e.g., in binary classification, though the upper bound with a $\\log(1/\\epsilon)$ factor was established in 1982 [5], the log factor was not removed until 2016 [6].\n\n* In this paper, we focus on improving the dependence of PAC sample complexity on $\\epsilon$ (equivalently, the dependence of the error rate on $n$). In learning theory, it is important to study the dependence of error rate on $n$ with $d$ fixed because a learner is typically applied to a fixed concept class with increasing $n$ so that $n$ is much larger than $d$. Moreover, by [7], our upper bound improves the universal learning rate from $\\log^2(n)/n$ to $(\\log n)/n$ for the concept classes studied in [7]. \nIdeally, we want tight dependence on each parameter. However, as tight dependence on either $d$ or $\\epsilon$ is unknown, we believe it is meaningful to explore better dependence on either parameter. \n\n* Besides the removal of a log factor, we also proposed two possible routes toward removing the remaining log factor of $\\epsilon$. \n\n\n[1] Brukhim et al. A characterization of multiclass learnability. 2022. \n\n[2] Natarajan. Some results on learning. 1989.\n\n[3] Daniely et al. Multiclass learnability and the ERM principle. 2015.\n\n[4] Daniely and Shalev-Shwartz. Optimal learners for multiclass problems. 2014.\n\n[5] Vapnik. Estimation of Dependencies Based on Empirical Data. 1982.\n\n[6] Hanneke. The Optimal Sample Complexity of PAC Learning. 2016.\n\n[7] Hanneke et al. Universal rates for multiclass learning. 2023.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "greMOH0uNs", "reviewer": "Reviewer_jEdN", "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. \n\nBesides, 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.", "questions": "See above.", "limitations": "See above.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper is well-written and easy to follow. Motivation and key results in the main paper are presented clearly and concisely, though I would also want the proofs in the Appendix to be discussed and commented on in the same way as in the main paper. I did not go through the proof very carefully, but it looks good at first glance. I would try to go through that in the details in the rebuttal phase. \n\nI like the presentation of this paper: first presenting the improvement on the sample complexity of Multiclass PAC Learning using a technique, and then proposing an alternative view that can potentially lead to a matching upper bound. This gives good insights to the readers, not simply about the sample complexity improvements, but also about the problem itself. \n\nOverall, I think this is a good paper and vote to accept it.", "weaknesses": "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. \n\nSome minor comments:\n1. 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for reviewing our paper. We appreciate your positive feedback. \nWe will include the proof sketches and high-level intuitions of the results presented in the Appendix in the revised version of the paper.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "cCQmAgQNiB", "reviewer": "Reviewer_s6iC", "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.\n\nTheir 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. \n\nTheir 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$. \n\nCombining this with their above reduction results in their upper bound.", "questions": "See weaknesses.", "limitations": "Yes.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "This paper is a highly technical paper that makes significant progress on a classic and important open problem in learning theory. In addition to improving the current best bounds, it provides an approach for further improvements. In particular, their reduction implies that improvements on list learning will result in improvements on multiclass classification.", "weaknesses": "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. \n\nOf 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for reviewing our paper. We appreciate your positive feedback. \nWe provided a proof sketch for Theorem 2.7 in line 229-241. We will elaborate more on it and include the proof intuition for other major theorems in the revision. We believe that the extra space can be accounted for by the additional page allowed if the paper is accepted.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "byNu1pKqWU", "reviewer": "Reviewer_AhgM", "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.", "questions": "Please refer to the Weaknesses for details.", "limitations": "This work does not seem to have any potential negative societal impact.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. Based on the Daniely-Shalev-Shwartz (DS) dimension, using the reduction and the boosting technique, the explicit lower bound on the sample complexity of multi-class learning is derived, and the upper bound of the error rate for multi-class learning is improved by a logarithmic factor.\n2. In order to obtain the corresponding optimal theoretical bounds, the implementation limitations of some relevant assumptions are formalized as open problems and discussed in detail, i.e., the construction of the specific list learners and the impact of pivot shifting on DS dimension.", "weaknesses": "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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for reviewing our paper. We appreciate your positive feedback. \nFirst, we need to emphasize that in this paper, we study multiclass PAC sample complexity for general concept classes which can have **infinite** number of labels ($|\\mathcal{Y}|=\\infty$). Our results hold for general concept classes independent of the number of labels. \nBelow, $d$ denotes DS dimension, $d_N$ denotes Natarajan dimension, and $d_G$ denotes graph dimension. \n\n## Graph dimension and Natarajan dimension\n\n* As we have stated in line 26-28, [1] showed that a concept class is PAC learnable if and only if its DS dimension is finite. Moreover, as is detailed below, it has been shown in the literature that finite graph dimension or Natarajan dimension does **not** characterize multiclass PAC learnability.\n\n* For the graph dimension, [2, Section 6] showed that finite graph dimension does not characterize multiclass PAC learnability by identifying a PAC learnable class with infinite graph dimension and infinite label space. \n[3, Example 1] provided a family of concept classes whose graph dimensions can be any positive integers or infinite, and all those concept classes are PAC learnable with sample complexity $\\log(1/\\delta)/\\epsilon$. \n[1, Example 8] is a concept class with DS dimension 1 (thus it is PAC learnable), infinite graph dimension, and infinite label space. \n\n* For the Natarajan dimension, [1, Theorem 2] provided a concept class with Natarajan dimension 1 and infinite DS dimension (thus it is not PAC learnable). \n\n* Thus, graph dimension and Natarajan dimension cannot appear in the optimal PAC sample complexity. \nIn general, for $\\mathcal{H}\\subseteq \\mathcal{Y}^{\\mathcal{X}}$, we have $d_N(\\mathcal{H})\\le d(\\mathcal{H})\\le d_G(\\mathcal{H})$ [4] and for the special case of $|\\mathcal{Y}|<\\infty$, $d_G(\\mathcal{H})\\le 5\\log_2(|\\mathcal{Y}|)d_N(\\mathcal{H})$ [3]. Quantitative scaling between those dimensions for general concept classes is still missing, and as is discussed above, there exist $\\mathcal{H}$ and $\\mathcal{H}'$ such that $d_N(\\mathcal{H})=1$, $d(\\mathcal{H})=\\infty$, $d(\\mathcal{H}')=1$, and $d_G(\\mathcal{H}')=\\infty$. \n\n* For detailed comparisons, our lower bound in eq. (2) is better than the best lower bound in terms of Natarajan dimension in [3, Theorem 5], and the Natarajan dimension cannot upper bound the PAC sample complexity of general concept classes by [1, Theorem 2] discussed before.\nThe graph dimension cannot lower bound the PAC sample complexity of general concept classes by the above examples of PAC learnable concept classes with infinite graph dimensions. \nThe best upper bound in terms of the graph dimension is $O((d_G(\\mathcal{H})+\\log(1/\\delta))/\\epsilon)$ by Proposition I.5 of our paper (see also line 226), which can be infinite for PAC learnable concept classes by the examples discussed before. \nMoreover, by [3, Example 1], there exists $\\mathcal H_i$ for all $1\\le i\\le\\infty$ such that $d_G(\\mathcal H_i)=i$ and $\\mathcal{M}_{\\mathcal{H}_i}(\\epsilon,\\delta)\\le \\log(1/\\delta)/\\epsilon$, indicating that their DS dimensions are uniformly bounded in terms of $i$. Thus, the optimal upper bound cannot depend on graph dimension, and the upper bound using graph dimension can be arbitrarily worse than our upper bound using DS dimension as our upper bound is always non-trivial with a finite gap of at most $\\sqrt{d}\\log(d)\\log(d/\\epsilon)$ from the optimal bound for PAC learnable concept classes. \n\n## Number of classes \n\n* As mentioned before, our upper and lower bounds on multiclass PAC sample complexity are independent of the number of classes which can be infinite. We actually prove the following result. There exists an algorithm $A$ and universal constants $C_1,C_2>0$ such that for any feature space $\\mathcal{X}$, label space $\\mathcal{Y}$ ($|\\mathcal{Y}|$ can be arbitrarily large or infinite), and concept class $\\mathcal{H}\\subseteq\\mathcal{Y}^{\\mathcal{X}}$, we have $\\mathcal M_{\\mathcal{H}}(\\epsilon,\\delta)\\ge C_1({d+\\log(1/\\delta)})/{\\epsilon}$ and $\\mathcal{M}_{A,\\mathcal{H}}(\\epsilon,\\delta)\n\\le C_2({d^{3/2}\\log(d)\\log(d/\\epsilon)+\\log(1/\\delta)})/\\epsilon$. \nAs we have listed above, there are many concept classes with infinite label space and finite DS dimension. Actually, by taking finite levels in the tree example in [1, Figure 3], we can construct a series of concept classes with DS dimension 1 and number of labels increasing to infinity. Thus, any bound that increases to infinity with the number of labels cannot be optimal and is worse than our upper bound for general concept classes. It follows that the optimal bound must be uniformly bounded with respect to the number of labels and the number of labels should not exist in the optimal bound. \n\nWe will incorporate the key points in the above discussion in the revised version of the paper. \n\n\n[1] Brukhim et al. A characterization of multiclass learnability. FOCS 2022. \n\n[2] Natarajan. Some results on learning. 1989.\n\n[3] Daniely et al. Multiclass learnability and the ERM principle. JMLR, 2015.\n\n[4] Daniely and Shalev-Shwartz. Optimal learners for multiclass problems. COLT 2014.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "0CUc8CDaSe", "reviewer": "Reviewer_aJcM", "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.", "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?  \n\n2) 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": "Yes", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 1, "contribution": 3, "strengths": "The paper introduces a novel boosting algorithm for list-learning which enables the log improvement in $1/\\epsilon$, allowing for the effective application of list-learning machinery to the multiclass problem. It improves on previous best lower bounds via the addition of the usual dependence on the confidence parameter $\\log(1/\\delta)$.", "weaknesses": "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.\n\nIt 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for reviewing our paper. Below, $d$ denotes DS dimension and $d_k$ denotes $k$-DS dimension.\n\n## List learning\n\n* The advantage of reducing to list learning is that it reduces the original problem to an easier problem: list learning is easier than multiclass learning. Indeed, a multiclass learner is a list learner of any size. If a concept class is PAC learnable with some sample complexity, then it is also $k$-list PAC learnable with the same sample complexity for any size $k$. \nOn the contrary, for any $k\\ge2$, we cannot directly obtain a multiclass learner from a general $k$-list learner. \nIf a concept class is $k$-list PAC learnable with some sample complexity, it is unclear whether it is multiclass PAC learnable and what its multiclass sample complexity is. As mentioned in line 285 (there is a typo, it should be \"$\\mathsf{dim}_k(\\mathcal{H})\\ge$'' instead of \"$\\mathsf{dim}_k(\\mathcal{H})>$''), $d_k(\\mathcal{H})$ is nonincreasing with $k$. Consequently, a $k$-list PAC learnable concept class (i.e., $d_k(\\mathcal{H})<\\infty$) is not necessarily multiclass PAC learnable. \nThus, Theorem 2.7 and 2.11 are highly non-trivial because they reduce the harder problem of multiclass learning to the easier problem of list learning: quantitatively, if a concept class is $k$-list learnable with some error rate $r(n)$, it is also multiclass learnable with an error rate bounded by $r(n)+d\\log(k)/n$. \n\n* Regarding $\\mathcal A_{\\text{goodlist}}$, if there is a multiclass learner $A$ with error rate bounded by $f(d)/n$, then $A$ is also a $k$-list learner with $\\epsilon_{A,\\mathcal{H}}(n)\\le f(d)/n$ for any $k\\in\\mathbb{N}$. Thus, our conjecture on list learners holds if the conjecture of the same rate on multiclass learners holds, indicating that the conjecture for such a list learner is weaker than that for a multiclass learner, hence more approachable. \nMoreover, in Theorem 2.10, our list learner already saves a log factor compared to the previous best list learner in [1]. It is reasonable to conjecture the removal of the remaining log factor. \n\n* The fact that we reduced a log factor in the upper bound of multiclass sample complexity by reducing to list learning also shows its advantage. \nThe improvement of log factors in PAC sample complexity is significant; e.g., in binary classification, though the upper bound with a $\\log(1/\\epsilon)$ factor was established in 1982 [2], the log factor was not removed until 2016 [3]. \nGiven that we reduced multiclass learning to an easier problem of list learning and thus removed a log factor, we believe our paper has made a significant contribution to multiclass learning. \n\n* Finally, with a large or infinite label space, it is natural to consider reducing the size of the label space by proposing a list learner. This idea has been adopted in [1], the first paper to establish the equivalence of multiclass PAC learnability and the finiteness of DS dimension. [1] proposed a list learner to construct a list sample compression scheme and built their multiclass learner using the labels in the list. \n\n\n## Lower bound\n\nOne cannot derive the $\\Omega((d_k-\\log\\delta)/k\\epsilon)$ bound using the $\\Omega(d_k/kn)$ expected error lower bound in [4] as a black box since one must stick to the distribution constructed for the lower bound when applying it as a black box. \nThus, for the PAC lower bound, we have to construct **different** hard distributions from that in [4] for both the $\\log(1/\\delta)/k\\epsilon$ (line 486) and the $d_k/k\\epsilon$ (line 511) terms. The detailed constructions are provided in the proof of Theorem 2.5 in Appendix B. To list one difference between our constructions and that in [4], our distributions are not uniform over the $\\mathcal{X}$ sequence selected and depends on the parameter $\\epsilon$, while theirs are uniform over the $\\mathcal{X}$ sequence selected. \n\nFinally, our major contribution is the upper bound. We include the lower bound and its proof for comparison and completeness as it is missing in the literature (see line 37 and 124). \n\n## Presentation\n\n* We provided the reference [1, Fact 14] of the leave-one-out argument in line 102 where it first appears. We have added the reference in line 236 in the revision. The current proof outlines are concise due to the space limitation, but we believe that they convey the key points of the proof. If the reviewer has other questions regarding the proof outlines, we are glad to answer in the discussion. We will extend the proof outlines to improve the readability in the revision. \n\n* Due to the space limitation, we have to put some definitions in the appendix, but we included the references of the definitions when they appear in the main text. We will move the important definitions in Appendix A to the main text with the additional page if the paper is accepted. \nWe believe that we have provided intuition for the definitions. We summarized the existing results in Proposition 3.1 to motivate the idea of upper bounding the density. \nIn Theorem 3.2, this idea is supported by its success for classes of DS dimension 1. \nIn line 329-335, we explained the reason of considering the pivot of a concept class. In line 346-352, we provided the intuition of pivot shifting and compared it to the standard shifting in the literature. Lemma 3.7 explained the partial validity of pivot shifting, which naturally leads to Open Question 2 about the remaining validity of pivot shifting in upper bounding the density using DS dimension. \nWe have added more explanations in words for the technical definitions to improve the readability in the revision. \n\n\n[1] Brukhim et al. A characterization of multiclass learnability. 2022. \n\n[2] Vapnik. Estimation of Dependencies Based on Empirical Data. 1982.\n\n[3] Hanneke. The Optimal Sample Complexity of PAC Learning. 2016.\n\n[4] Charikar and Pabbaraju. A characterization of list learnability. 2023.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: 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.
Decision: Accept (poster)