Multiclass Boosting: Simple and Intuitive Weak Learning Criteria
Authors: Nataly Brukhim
Amit Daniely
Yishay Mansour
Shay Moran
Venue: NeurIPS 2023 poster (2023)
Keywords: Boosting
Multiclass classification
PAC Learning
List PAC Learning

Abstract: We study a generalization of boosting to the multiclass setting.
We introduce a weak learning condition for multiclass classification that captures the original notion of weak learnability as being “slightly better than random guessing”. We give a simple and efficient boosting algorithm, that does not require realizability assumptions and its sample and oracle complexity bounds are independent of the number of classes. 

In addition, we utilize our new boosting technique in several theoretical applications within the context of List PAC Learning. 
First, we establish an equivalence to weak PAC learning. Furthermore, we present a new result on boosting for list learners, as well as provide a novel proof for the characterization of multiclass PAC learning and List PAC learning. Notably, our technique gives rise to simplified algorithms and analysis compared to previous works.

Multiclass Boosting: Simple and Intuitive Weak Learning Criteria
Nataly Brukhim
Amit Daniely
Department of Computer Science Princeton University
Department of Computer Science
Hebrew University
Google Research
Yishay Mansour Department of Computer Science
Shay Moran
Faculty of Mathematics
Tel Aviv University Google Research
Faculty of Computer Science
Faculty Data and Decision Sciences
Technion Google Research
Abstract
We study a generalization of boosting to the multiclass setting. We introduce weak learning condition for multielass classification that captures the original notion of weak learnability as being "slightly better than random guessing". We give a simple and efficient boosting algorithm, that does require realizability assumptions and its sample and oracle complexity bounds are independent of the number of classes.
In addition, we utilize our new boosting technique in several theoretical applications within the context of List PAC Learning. First, we establish an equivalence to weak PAC learning. Furthermore, we present a new result on boosting for list learners, as well as provide novel proof for the characterization of multiclass PAC learning and List PAC learning. Notably, our technique gives rise to simplified analysis, and also implies an improved error bound for large list sizes, compared to previous results.
Introduction
Boosting is a powerful algorithmic approach used to boost the accuracy of weak learning models, transforming them into strong learners. Boosting was first studied the context of binary classifica- tion in line of seminal works which include the celebrated Adaboost algorithm, as well an many
other algorithms with various applications (see e.g. [14 22 [T]
The fundamental assumption underlying boosting is that a method already exists for finding poor, yet not entirely trivial classifiers. Concretely, binary boosting assumes there exists learning algorithm that, when presented with training examples, can find a classifier h X + {0, 1} that has classification error less than 1/2. That is, performs slightly better than random guessing. The intuition is that this is the most minimal assumption one can make about learning algorithm, without being impractical. This assumption is called the weak learning assumption, and it central the study of boosting.
While binary boosting theory has been extensively studied, extending it to the multiclass setting has proven to be challenging. In particular, it turns out that the original notion of weak learnability being "slightly better than a random guess", does not easily extend the multiclass case. For
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

example, perhaps the most natural extension is to assume that the learner has accuracy that is slightly better than 1/k, where y/ (I..., k). However, this naive extension is in fact known to be too weak for boosting (see Section 2 below for a detailed discussion). Instead, previous works [19 7 23 have formulated various complex weak learning assumptions with respect to carefully tailored loss functions, and rely on restrictive realizability assumptions, making them less useful in practice.
weak learning assumption. In this work, we generalize the classic formulation of boosting to the multiclass setting. We introduce weak learning condition that captures the original intuition of seater-tha--rnddon guessing". The key idea that renders this condition
weak learnability as "slightly useful compared to previous attempts, is based on a "hint" given to the weak learner. The hint takes the form of a list of k labels per example, where At is possibly smaller than []*]. Then, the assumption is that there exists learner capable of producing not entirely trivial classifiers, if it was provided with a "good hint". In other words, if the list provided to the learner happens to contain the correct label, expect the learner perform slightly better than randomly guessing label from the list. Specifically, the assumption is that for any k 2 2, if the given lists of size k contain the true labels, the learner will output a classifier h X' y with error slightly better than random guessing among the k labels. Notice that this encompasses both the binary case when k = 2, as well as the naive extension mentioned above, when = | We call this new condition the "better-than-rande guess". or BRG condition.
The BRG condition also generalizes the classic binary case condition in a practical sense. Previous methods on multiclass boosting are framed within the PAC (Probably Approximately Correct) setting, correspond to known hypothesis class H C y and assume that weak learning hold for every distribution D over the entire domain X. Practically, these requirements can be very difficult to check or guarantee. In contrast, as in binary boosting, the BRG condition can be relaxed to more benign empirical weak learning assumption, that can be verified immediately in an actual learning setting.
Recursive boosting. Our main contribution is a new boosting algorithm that is founded on the BRG condition. Our boosting methodology yields simple and efficient algorithm. It is based on the key observation that even a naive weak learner can produce a useful hint. Recall that when given no hint all, the naive weak learner can still find a hypothesis with slight edge (y >> 0), over random guessing among | labels. Although this may result in a poor predictor, we prove that it effectively reduces the label space per example to approximately 1/7 labels. This initial hint serves as the starting point for subsequent iterations of the boosting algorithm. The process continues recursively until the label list per example is reduced size 2, at which point any classic binary boosting can yield a strong classifier. Unlike previous methods, our boosting algorithm and guarantees do not rely on realizability assumptions nor do they scale with [)] In fact, we show that the sample and oracle-cat call complexity of our algorithm are entirely independent of [3%, which implies our approach is effective even in cases where the label space y is possibly infinite. Moreover, the overall running time of our algorithm is polynomial in the size of its input.
An important insight that underlies our approach is the link between the naive weak learning condition, which we term weak-BRG learning, to that of list learning. In list learning [5] g [8] predicting a single outcome for a given unseen input, the goal is to provide a short list of predictions. this technique an intermediate goal of the algorithm, by which effectively reducing the size of the label space in each round. The generalization analysis relies on sample compression arguments which result in efficient bounds the sample and oracle complexities.
rather than
Here
Perhaps surprisingly, the connection between weak learnability and list learnability even more fundamental. We prove that there is an equivalence between these two notions. Specifically, we establish that a 7-wea learner is equivalent to an (1/7)-list learner.
Lastly, we demonstrate the strength of our boosting framework. First, we give generalization of our boosting technique to hold for list PAC learning algorithms. Then, we showcase the effectiveness of the weak learning criteria in capturing learnability in two fundamental learning settings: PAC learning, and List PAC learning. Recently, [5] proved a characterization of multiclass PAC learning using the list learnability using a natural extension of the DS dimension. Here we show that in both cases, assuming the appropriate dimension is bounded, one can devise a simple weak learning algorithm. Thus, it is also amenable to a boosting method similarly to our approach, leading to a novel and alternative proof of the characterization of learnability. We note that for cases where the dimension
(DS) dimension. In a subsequent study, [ gave a characterization of
2

---

is much smaller than the list size, we have an improved result over previous bound. Moreover, our approach offers simpler algorithm and analysis technique, potentially benefiting future applications as well.
1.1
Main result
The main contributions in this work are as follows.
Multiclass boosting framework. Our main result is a boosting framework for the multiclass setting, which is natural generalization of binary boosting theory. We give simple weak learning assumption that retains the notion of weak learnability as "slightly-better random-guess" from the binary case. Furthermore, give an efficient multiclass boosting algorithm, as formally stated in Theorem[[belov Our boosting algorithm given in Section (Algorithm{3) 3
2. Applications: List PAC learning. First, we establish an equivalence between List PAC learning and Weak PAC learning, demonstrating the strong ties between List PAC learning and multiclass boosting theory. Furthermore, we present new result on boosting for list learners. Lastly, we give a novel and alternative proof for characterization of PAC learning and List PAC learning. particular, the results imply simplified algorithmic approach compared to previous works, and improved error bound for cases where the list size is larger than the appropriate dimension g
We will now introduce the main weak learning assumption, which we call the "better-than-random guess", or BRG condition, and state our main result in Theorem [ellow.
In its original form, the boosting question begins by assuming that a given hypothesis class H. C {0, 1)xt is weakly-PAC learnable. Similarly, here we present the BRG condition framed as weak (multiclass) PAC setting, followed by relaxation an empirical variant of the assumption.
Definition (BRG condition). We say that hypothesis h X' + satisfies the R-BRG condition with respect a list function μ + y² on a distribution D over examples if
Pr [M(x) = 2 +.) (a.N)~
Pr E m(x)) (2.8)>D
We say that a learning rule W satisfies the 7BRRG condition for hypothesis class H. if for every H- H-realizable distribution D. for every > 2, for every list function p : X y³, the output hypothesis h outputted by W satisfies Equation (1) with probability 1- 6,, when given mo()) i.i.d. examples from D. and given μ.
In words, the condition determines that if y belongs the set u(z), then h has higher probability of correctly classifying x by an additional factor of 7, compared to a random guess from the list (((x).
However, requiring that the labels be deterministic according to target function from known class H. and that weak learning hold for every distribution D over the entire domain X are impractical, as they can be very difficult to check or guarantee.
Instead, as in the binary boosting setting, our condition be relaxed a more benign empirical weak learning assumption. as given next.
Definition 2 (Empirical BRG condition). Let S E (X x y)m, We say that a learning rule W satisfies the empirical y-BRG condition for S there an integer my such that for every distribution p over mm) for every k 2 for every list function μ X + y*,, when given my examples from S drawn i, i.i.d. according to p. and given μ. outputs a hypothesis h such that,
Σp: p: 1[h(z)) vil 2
+7
Σ
p
1 a(xx)).
Next, we give our main result of efficient boosting algorithm, stated in Theorem Tbelow.
We denote X|s {u X By s.t. (x. E S).
3

---

Theorem (Boosting (Informal)). There exists multiclass boosting algorithm B such that for any e, 6 > O, and any distribution D over X x V. when given a training set S ~ Dm and oracle access to learning rule W where = Ô 9.cc) and applying B with total of O (1/r²) oracle calls to W. it outputs predictor H :X + y such that with probability least - 6, we get that W satisfies the empirical B/-BGG condition for S then,
Pr (r.y)~
H(z) F sc
1.2 Related work
Boosting theory has been extensively studied, originally designed for binary classification (e.g.- AdaBoost and similar variants) [23]. There are various extension boosting to the multiclass setting.
The early extensions include AdaBoost.MH, AdaBoost.MR, and approaches based on Error- Correcting Output Codes (ECOC) 24 M. These works often reduce the k-class task into a single binary task. The binary reduction can have various problems, including increased complexity, and lack of guarantees of an optimal joint predictor.
Other works on multiclass boosting focus on practical considerations and demonstrate empirical performance improvements across various applications 29
21) However, they lack comprehensive theoretical framework for the multiclass boosting problem and often rely on earlier formulations such as one-versus-all reductions the binary setting or multi-dimensional predictors and codewords.
16
15
3
Notably, work by [9] established a theoretical framework for multiclass boosting, which generalizes previous learning conditions. However, this requires the assumption that the weak learner minimizes complicated loss function, that is significantly different from simple classification error. Moreover, it is based on a restrictive realizability assumption with respect to a known hypothesis class. In contrast, we do not require realizability, and only consider the standard classification loss.
More recently, 7 followed a formulation for multiclass boosting similar to that of [1)]. They proved a hardness result showing that broad, yet restricted, class of boosting algorithms must incur cost which scales polynomially with | Our approach does not fall in this class of algorithms. Moreover, our algorithm has sample and oracle complexity bounds that are entirely independent of (
2 Warmup: too-weak weak learning
When there are only 2 labels, the weak learner must find a hypothesis that predicts the correct label bit better than random guess. That is, with success probability that is slightly more than 1/2. When the number of labels & is more than 2, perhaps the most natural extension requires that the weak learner outputs hypotheses that predict the correct label bit better than a random guess among l labels. That is, with a success probability that is slightly more than 1/k.
However, this is in fact known to be too weak for boosting (see e.g., [23] Chapter 10). Here we first give simple example that demonstrates that fact. However, we also show that all is not yet lost for the "better-than teatthha---a sandom-guess intuition. Specifically, we describe how this condition can still allow us extract valuable knowledge about which labels are incorrect. This observation will serve as foundation for our main results, which we will elaborate on in the next section.
We start by defining the notion of better- Definition (weak-BRi learning). learning algorithm W a weak- BRG learner for a hypothesis class H. C [k] if there is y 0 and ma (0, 1) + N such that for any do > O, and any H-realizable distribution D over x [b], when given ma 2 mo(5)) samples from D, returns h X - y such that with probability 86.
weak learner that term weak-BRG learning.
1 Pr h(() vl 2 k + (x.g)~D
To get an intuition for why this definition is indeed too weak for boosting, consider the following simple example. Suppose that X' {a, b, c). y = 2, and that the training set consists of the
"Th Ô notation conceals polylog(m, 1/8) factors.

---

three labeled examples (a, 1), (b. 2), and 3). Further, we suppose that we are using weak learner which chooses weak classifiers that never distinguish between and In particular. the weak learner always chooses one of two weak classifiers: hn and h22 defined as follows. For E {a, b) then h1 always returns and h2 always returns For x = c they both return 3.
Then, notice that for any distribution over the training set, either 11 or h2 must achieve an accuracy of at least 1/2, which is significantly higher than the aceuracy of 1/k = 1/3. However, regardless of how weak classifiers are aggregated, any final classifier / that relies solely on the predictions of the weak hypotheses will unavoidably misclassify either b. As result, the training aceuracy of H on the three examples can never exceed 2/3, making it impossible to achieve perfect accuracy through any boosting method.
Furthermore, we note that this simple example can also be extended to a case where the data is realizable by hypothesis class which is not learnable by any learning algorithm (let alone boosting). For example, consider the hypothesis class H = {1, 3] for = N. Then, H is not PAC learnable (e.g., via No-Free-Lunch ([26), Theorem 5.1)). However, similarly as above, one can construct learning rule that returns a hypothesis with accuracy 1/2 > 1/k over an H-realizable distribution.
Next, we will examine useful observation that will form the basic building block of our algorithmic methodology. We demonstrate that the natural weak learner given in Definition 3 while weak, is nonetheless useful. This can be shown by examining the guarantees obtained through its application in boosting. Specifically, we consider the following classic variant boosting via the Hedge algorithm.
Algorithm Boosting via Hedge
Given: Training data S E (A' x (,) parameter 7) >> O. Output: predictor H X' + R.
1: Initialize: W1 wi(1)
for all = L.... m.
2: for t = ,,, do
3: Denote by Dr the distribution over [m] obtained by normalizing wi
4: Draw my examples from Dj and pass the weak learner.
5: Get weak hypothesis h4 : + V,, and update for 1..., m:
Wr+ (i) (i)e 7- (1,)
6: end for
7: Output H such that for all y) X' [k).
H(x,y) v) = Σ [[b((x) = w/.
Notice that the output of Algorithm I returns a predictor that is not classifier, but scoring function with the aim of predicting the likelihood of given label candidate y E [k]] for some x E X. Typically, boosting algorithms combine the weak hypothesis into such a scoring function yet their final output applies an argmax over it, to yield valid classifier. However, since the weak learning assumption is too weak as we have shown above, taking the argmax is useless in this setting.
Instead, the following lemma shows that by boosting the "too-weak" learner, we can guarantee to eliminate one label for each example in the data. Towards that end, we consider relaxed variant of the weak-BRG learner, to be defined over a data set S, which we term the empirical weak-BRC learner. Specifically, we say that a learner satisfies the empirical weak-BRG condition if there an integer mo such that for any distribution over the training examples, when given my examples drawn i.idd from the learner outputs a hypothesis that satisfies Equation
Proofs are deferred to the appendix.
Lemma 1 (Remove one label), Let S E (X' x [ Let W be empirical weak-BRG learner for with respect to some ni and sample size my- Then, the output H (X' x [и]] + [0, T] obtained
by running Algorithm with T > 8log(m) and 1) v In(m)
2T guarantees that for all (x. v) E S,
5

---

H(x-y) T 2 2 Moreover, for all (x, v) E S the minimally scored label é = arg minse[M] (z, e)
must be incorrect. That i + y.
Notice that if we to take the argmax of H is typically done in boosting, the guarantees given in Lemma do not suggest this will result in the correct prediction. In fact, this approach might yield rather bad classifier even for the set S on which it was trained. In other words, for any (x, S it may be that there is some incorrect label y' & y with (o,,y' > (xx y).
However, notice that the lemma does suggest good classifier of incorrect labels. That is, the lowest scored label will always be an incorrect one, over the training data. This property can be shown to generalize via compression arguments, discussed in Section | This allows to effectively reduce the size of the label space by one, and is used as the basic building of our algorithm, as detailed the next section.
3 Multiclass boosting results
We start by introducing the notion of weak learnability that is assumed by our boosting algorithm. We note that it is relaxation of the empirical BRG condition introduced in Definition 2 in the sense that it does not make any guarantees for the case that the given hint list does not contain the correct label. This may seem like significantly weakening the assumption, yet turns out to be sufficient for boosting approach to hold.
In the resulting fully relaxed framework, no assumptions at all are made about the data. Although the BRG condition is not explicitly assumed to hold, when this is the case, our final bound given in Theorem implies a high generalization accuracy.
Definition 4 (Relaxed Empirical 7-BRG learning). Let S E (X V)TH 7 > and integer ma- Let M be set of list functions of the form Fp X ++ 4* for any integer k. such that for each E M and i E [ml. then yi E ((z.). A learning algorithm satisfies this condition with respect to (S, n, mmm M), for any distribution p over S and any μ :X + yk such that E M, when given a sample S pm and access to μ, it returns h X' + such that,
Pr [b(x) = k +% (m,y)~p
Notice that when the list μ returns the set of possible labels y and it of size k, this condition essentially equivalent to the empirical weak-BRG condition, which shown above is too weak
for boosting. Requiring that the condition will hold for any list size k S [}] is sufficient to facilitate boosting, shown in Theorem 2
The starting point of our overall boosting algorithm (given Algorirhm 3 is a simple learning procedure specified in Algorithm [ is used to effectively reduce the size of the label space. In particular, it is used to produce the initial "hint" function that is used by the boosting method.
Algorithm 2 Initial hint
Given: S E (X x Vy" parameters mo, P 0.
Output: A function μ X' + yp.
1: Set S : S.
2:
for 1...., do
3: Let Uy denote the uniform distribution over Sj.
4:
Draw me examples from U1 and pass the weak learner, with μo y.
5: Get weak hypothesis h2 X' + Y.
6: Set S be all the points in S, which hy predicts incorrectly.
7:
end for
8: Output μ defined by:
((x) =
We also allow lists that return an infinite subset of labels. In that case we simply have that the weak hypothesis satisties (((r))pphh()) y] 2 7.

---

We can now present our main boosting method in Algorithm 3 and state its guarantees in Theorem
Algorithm Recursive Boosting
Given: Training data 5 E (X ") edge y >> 0, parameters T. > 0.
Output: predictor H -
1: Initialize: get μl by applying Algorithm over S.
2: for =.,.....
3: Call Hedge (Algorithm T with S and μú, and parameters 7), T to get Hy Hy:A y
W Modify Algorithm to receive μ4 as input, and line pass to the weak leamnrr
4: Construct M5+1 Als + - such that for all x,
(++1(2)= - yy M p5(2)) A (z >
T
p p-j+15
5: end for
6:
Output the final hypothesis H pdp
The following theorem is formally stating the main result given in Theorem 1
Theorem (Boosting). Let W denote a learning rule that when given any set of labeled examples and list function, returns some hypothesis X + V. Let e, 0, 7, n0 > 0, and let DD a distribution
T for m 2 mo (In(mm)lan(")) Ix()))
over x y. Then, when given sample
oracle access to
T
W and 8.n(m)) p 2ln(m) and тj = V 2T Algorithm 3 outputs a predictor H such that 72
In(m)
the following holds. Denote by M the sets of list functions on which W was trained throughout Algorithm 3 Then, with probability least 1 5, we get that if W satisfies the --BRG condition (as given in Definition 4 with respect to (S, 7, mo, M) then,
Pr (m.n)~
(x)) + Se.
Observe that Theorem 2 implicitly assumes that the sample complexity of the weak learner mo is not strongly dependent on the overall sample size m and scales most nolyylogarihhmically with m. In other words, although the statement holds for any mp. the result becomes vacuous otherwise.
In addition, notice that Theorem is quite agnostic in the sense that have made prior assump- tions about the data distribution. Concretely, Theorem Ltells us that the generalization error will be small the given oracle learner W happens to satisfy the --BRG condition with respect the particular inputs it receives throughout our boosting procedure.
Adaptive boosting Boosting algorithms typically do not assume knowing the value of y and adapted to on the fly, as in the well-known Adaboost algorithm 23 However, the boosting algorithm given in Algorithm[] [ well our boosting method algorithm with a value estimating If the estimation of 7 provided to the algorithm is too large, the algorithm may fail. This can be resolved by a simple preliminary binary-search-type procedure, in which we guess gamma, and possible halve it based on the observed outcome. This procedure only increases the overall runtime by logarithmic factor of (In(1/7)), and has no affect on the sample complexity bounds.
whole, requires feeding the
4 Applications to List PAC learning
The applications given in this section are based on the framework List PAC learning g and demonstrate that it is in fact closely related to the multiclass boosting theory. First, we establish an equivalence between list learnability and weak learnability the context of the PAC model. Furthermore, we present new result on boosting for list PAC learners. Lastly, we give novel and alternative proof for characterization of PAC learnability and List PAC learnability. In particular, these imply simplified algorithmic approach compared to previous works 8]
7

---

We start with introducing list learning in Definition 5 followed by the definition of weak PAC learning, similarly to the weak-BRe learning definition we give in this work.
Definition 5 (k- PAC Learning). We say that a hypothesis class H. S yx is k-list PAC learnable, if there is an algorithm such that for every H-realizable distribution D. and every c, > 0. when given S ~ Din for 2 m(e, 5), it returns us X + y*h such that with probability 1 - 8,
Pr y E ps(()) - (2.0)~
Definition 6 (7-weak PAC Learning). We say that hypothesis class H. C. yxx is 7-weak PAC learnable, there an algorithm such that for every H-realizable distribution D, and every > when given S ~ Dmh for m 2 m(8), it returns hg X + y such that with probability 1 6,
Pr (a.y)~/
1y hs())) 7..
Next, in the following lemmas we show the strong connection between these two notions. Specifically, we give an explicit construction of a list learner given oracle access to a weak learner, and vice versa. Lemma 2 (Weak = List Learning). Let H S yxx be a hypothesis class. Assume W is a y-weak PAC learner for H with sample complexity mwy (0, 1) + N. Let be the smallest integer such that < 7, and denote = 11
k. Then, there is an (I- - 1--isst PAC learner with sample complexity
ō) m(e,,)== =Ō
(m/TT 0²c
where T = ( is the number of its oracle calls to W.
Lemma 3 (List= = Weak Learning). Let H S. yx be hypothesis class. Assume C is k-List PAC learner for H with sample complexity my (0, + N. Then, for any >> O there is an 7-Weak PAC learner where 7 = =12 with sample complexity m(0) = Ô (mele, 1/2) ks + (k//)²) where q= = 2k (2/6) is the number of its oracle calls to L.
Lastly. Theorem 3 concludes this section demonstrating the strong ties between weak and list learnability. Concretely, it combines the results of both Lemma [ and Lemma B above to show that when the appropriate parameters y and k are optimal, then y-PAC learnability and k-list PAC learnability are in fact equivalent.
Theorem 3 (Optimal accuracy < Optimal list size). Let H C y Denote by k(H) the smallest integer for which H. is k-list PAC learnable, assuming that k(H) < co. Denote by ((H the supremum over E [0, for which H is 7-weak PAC learnable. Then, it holds that k(H) (H()) 1.
4.1 List boosting and conformal learning
List prediction rules naturally arise in the setting of conformal learning. In this model, algorithms make their predictions while also offering some indication of the level of reliable confidence in those predictions. For example in multiclass classification, given an unlabeled test point x, the conformal learner might output a list of all possible classes along with scores which reflect the probability that x belongs each class. This list can then be truncated a shorter one which contains only the classes with the highest score. See the book by (28 and surveys by 25 for more details.
We now consider closely related notion of List PAC learnability, that similarly to conformal learning allows the list size to depend on the desired confidence. This was also defined in (8], termed weak List PAC Learning, due to the dependence of the list size on the input parameter.
Indeed, it is natural to expect that the list size will increase when we require more refined accuracy, and perhaps that this is weaker notion of learnability than that of List PAC learning, which corresponds to a fixed list size.
Interestingly, it turns out that weak List PAC Learning is in fact equivalent to strong List PAC Learning. In other words, list learner with a list size that varies with the desired accuracy parameter can be boosted to a list learner with fixed list size, and arbitrarily good accuracy. The proof is by way of generalization of our boosting technique to lists, as stated in Theorem 4
Theorem 4 (List boosting). Let H. C yx Let cu, du > O, and assume that there exists an algorithm such that for every H--relizzblle distribution D, and for some integer ky := ko(Co), when given S ~ Dm for m 2 m(co, (o), it returns psg X - ykk such that with probability 1 do.
Pr (a.a)DD
[y E us(x)]] 2 1 - -00
8

---

Then, there is k-List PAC learning algorithm for H. for fixed list size k
1-260
Observe that Theorem 4 indeed generalizes classic boosting. Specifically, consider the binary setting and notice that when ky 1, and cy is slightly smaller than 1/2, Theorem 4 implies that weak learning with edge = 2 cu, is equivalent to strong learning with arbitranly small error. The following corollary shows that weak List PAC Learning implies strong List PAC Learning.
Corollary 1. If class H C ydt is weakly-List Listt PAC learnable then it is also List PAC learnable.
4.2 Characterization of List PAC learnability
We now foeus on the characterization of List PAC learnability, which also implies the characteri- zation of PAC learnability. Towards that end, we define the Daniely-Shwarth (DS) dimension [9] Specifically, we give the natural generalization of it k-sized lists, called the k-DS dimension.
Definition 7 (k-DS dimension (8). Let H. S V be hypothesis class and let S E x be sequence.
We say that H. k-DS shatters if there exists JF C H. [F] < Do such that ff E Fls. Vi E [d], f has least i-neighbors. The k-DS dimension H, denoted as d d ss (HH). is the largest integer such that H. k-DS shatters some sequence S xxd.
We note that when k = 1, this captures the standard DS dimension 9 We show that when the k-DS dimension bounded, one can construct simple weak learner which satisfies our BRG condition. Thus, it is also amenable to our boosting method, leading to qualitatively similar results for characterization of learnability in [5] 8. The result given the next theorem.
Theorem 5 (PAC and List-PAC learnability). Let H S. yd be an hypothesis class with k-DS dimension d < oc. Then, H List PAC learnable. Furthermore, there learning algorithm A for H. with the following guarantees. For every H-realizable distribution D, every ò > 0 and every integer m, given an input sample S ~ Dm, , the algorithm outputs = A(S) such that
( d + log(1
(1( 7 v O (x:9)><
Pr
m
with probability at least 1- over S. In particular, if = 1, then H is PAC learnable.
We remark that for cases where d < lt we have an improved result over the bound given by 8 For comparison, the error bound given by 8. Theorem 2 is Ô d²-0 +
Thus, Theorem 5 demonstrates that our boosting- baased approach gives rise to alternative proof for the characterization of PAC Icarnability and List PAC learnability. Moreover, our approach offers a simpler algorithm and analysis technique, that can perhaps be of use in future applications well.
5 Generalization via compression
This section is concerned with the analysis of our boosting method given in Algorithm 3 and the proof of our main result given in Theorem (and formally in Theorem 2
The boosting algorithm given in this work best thought of a sample compression scheme 17
sample compression scheme (Definition 8) is an abstraction of common property to many learning algorithms. It can be viewed as a two-party protocol between a compresser and a reconstructor. The compresser gets as input sample S. The compresser picks a small subsample S' of S and sends it to the reconstructor. The reconstructor outputs an hypothesis h. The correctness criteria is that needs to correctly classify all examples in the input sample S. We formally define it next.
Definition 8 (Sample Compression Scheme [77). Let r & m be integers. An m + r sample compression scheme consists of a reconstruction function
(X x y)" - y
such that for every S E (X x y)T there exists S' C S of size r, such that for all (x, v) E S it holds that h(x) = y, where h = p(S").
'The Ô notation conceals polylog(m, 1/7) factors.

---

We are now ready to prove the main result, given in Theorem 2 The next paragraph highlights the assumptions that were made, followed by the proof of the theorem.
Specifically, we assume for simplicity that the learning algorithm does not employ internal random- ization. Thus, it can be regarded as fixed, deterministic mapping from sequence of mo unweighted examples, and a function X' + y to hypothesis h X' + V. We note that our results remain valid for a randomized learner as well, yet we assume the above for ease of exposition.
The proof is given via a sample compression scheme, demonstrating that weak learnability holds, then the final predictor H can be represented using a small number of training examples, and that it is consistent with the entire training set.
Proof of Theorem 2
First, we fix the sample S and assume that the 7-BRG condition holds for S as in the theorem statement. We will then show for each j = I...p that 4j+1 satisfies the following properties: (a) for each x E X' it returns at most p - - labels, (b) for all (x, E S, it holds that y (5+1(x)). (Ir), and (c) it can be represented using only a small number of training examples.
First, note that μ1 is indeed mapping to at most labels by its construction in Algorithm 2 Moreover, recall that by the above assumption. the weak learner is a deterministic mapping from its input to hypothesis. Therefore, any hypothesis produced by the weak learner within Algorithm 2 can be represented simply by the sequence of mo examples on which it was trained. Lemma F implies that there is a subset S" Ç S. of size at most mo P, where p = flog(m)/+ />] such that the following holds: There are p hypotheses hy : X + V. that comprise the list fl,, where each hy can be represented by mo examples in S". It is also guaranteed by Lemma 4 that for all (z, v) E S, it holds that y (u (1r).
Next, we will show that the 3 properties (a)-(c) above holds for #2 (and similarly for all j 2 2). Consider the first T weak hypotheses i," ..... "..,,...,, n generated by Algorithm 3 within its first call to Algorithm| 1 Notice that each h²" can now be represented by the sequence of mo examples on which it was trained, as well as the same mo p examples from above that correspond to ft. Therefore, we can represent the mapping P2 by a total of T mm + mo p examples. Next, we will show that (a) and (b) hold, by applying Lemma] 1 Specifically, we use it to prove that for each (z, v) E 8, (2 returns p- labels, and also that y E (22(2).
We first show that the conditions of Lemma 1 are met, by considering a simple conversion of all the labels according to fu- Specifically, since both Lemma I and Algorithm [ [[ssume the labels in [k). yet both A Algorithm 3 and our weak learner assume the labels in S are in 3 we can think of mapping each y y to ip + 1] according to μl. getting its corresponding label E E [p + 1] in the mapped space, and then remapping back to the ) space when returning to Algorithm
X x [p]. such that the é-th entry of nn (x) is y. denoted 44 (x))- = y. By Definition 4 we obtain a hypothesis h : X' Y. For its internal use in Algorithm| 1 we convert it into hypothesis h' X ~ [p 1) such that if h(x) u(x)), set h' (x) = l set
Concretely, for each pair (z. y) S, convert it to (I,
for l that satisfies μ1 (z), = h((r), or h' h'(z) = + if there is no such é E [p]. Finally, we set the output H, of Algorithm 1 to be defined with respect the original, remapped, weak hypotheses h.
Now applying Lemma D with As := p. we get that for all (Ix, E S. we have HI, v) > T/p. There- fore, it must hold that y E (1:))). Moreover, since Evenr(()) H1 H1 v') S Ey'y (1 $ T,
Lemma ! implies that there must be a label y' * y such that y u1 (x) for which H (I. v/ < <Tpp. Therefore, by construction of #2 we get that y & #2(2)), and [22 (z)l < \x --
3, 3.....P 1. Namely, the same arguments as above show that by applying Lemma]] [ with k: == p - j + 2, we get that μ4j+1 satisfies the above
Next, we continue in a similar fashion for all rounds
conditions over S. Moreover, to represent each weak hypotheses h!(") generated by Algorithm within its j-th call to Algorithm[I [ we use the sequence of mo examples on which it was trained, as well as the same (j - 1) T mo + mo p examples from above that correspond uú.
Overall, we have shown that if W satisfies the BBBRG condition (as given in Definition with respect to (S. 755,mo,, mo, .)) then the final predictor H Mp is both consistent with the sample S, and can be represented using only r examples, where,
r == (p- - 1) T mo + mg == O (
p mo In(m) = O (mg In (m)
(5)
72
2:3
10

---

We can now apply a sample compression scheme bound to obtain the final result. Specifically, we apply Theorem 6 (for l 1), for m - sample compression scheme algorithm A equipped with a reconstruction function / (see Definition 8). We denote enr (T) = Pr(x.g)>D(HH * v). Then, by Theorem we get that,
r (mn(m) + (n( m
Pr
H consistent with S = (
S~D",,A
where the overall randomness of our algorithm is denoted by A. Plugging in r from Equation ( and given in the theorem statement, yields the desired bound.
Acknowledgments and Disclosure of Funding
AD received funding from the European Research Council (ERC) under the European Union's s Horizon 2022 research and innovation program (grant agreement No. 101041711), and the Israel Science Foundation (grant number 2258/19) 19). This research was done as part of the NSF-Simons Sponsored Collaboration on the Theoretical Foundations of Deep Learning.
YM received funding from the European Research Council (ERC) under the European Union's Horizon 2020 research and innovation program (grant agreement No. 882396), by the Israel Science Foundation (grant number 993/17), the Yandex Initiative for Machine Learning at Tel Aviv University and grant from the Tel Aviv University Center for AI and Data Science (TAD).
SM is a Robert J. Shillman Fellow: he acknowledges support by ISF grant 1225/20, by BSF grant 201 8018385, by an Azrieli Faculty Fellowship. by Israel PBC-VATAT, by the Technion Center for Machine Learning and Intelligent Systems (MLiS), and by the the European Union (ERC, GENER- ALIZATION, 101039692). Views and opinions expressed are however those of the author(s) only and do not necessarily reflect those of the European Union or the European Research Council Executive Agency. Neither the European Union nor the granting authority can be held responsible for them.
References
[1] Erin L Allwein, Robert E Schapire, and Yoram Singer. Reducing multiclass to binary: A unifying approach for margin classifiers. Journal of machine learning research, 1(Dec): 13-141, 2000.
[2] Anastasios N Angelopoulos and Stephen Bates. A gentle introduction conformal prediction and distribution- free uncertainty quantification. arXiv preprint arXiv:2107.00511,, 2021.
[3] Ron Appel and Pietro Perona. A simple multi-class boosting framework with theoretical guarantees and empirical proficiency. In International Conference on Machine Learning, pages 186-199 194. PMLR, 2017.
[4] Oscar Beijbom. Mohammad Saberian, David Kriegman, and Nuno Vasconcelos. Guess-averse loss functions for cost-sensitive multiclass boosting. International Conference on Machine Learning, pages 586-594. PMIR, 2014.
[5] Nataly Brukhim, Daniel Carmon, Irit Dinur, Shay Moran, and Amir Yehudayoff. A characteri- zation multiclass learnability, arXiv preprint arXiv:2203.01550, 2022.
[6] Nataly Brukhim and Elad Hazan. Online boosting with bandit feedback. In Algorithmic Learning Theory, pages 397-420. PMLR, 2021.
[7] Nataly Brukhim, Elad Hazan, Shay Moran, and Robert E. Schapire. Multiclass boosting and the cost of weak learning. In NIPS, 2021.
[8] Moses Charikar and Chirag Pabbaraju. A characterization of list learnability. arXiv preprint trXiv:2211.04950 2022.
[9] Amit Daniely and Shai Shalev-Shwartz. Optimal learners for multiclass problems. In COLT, pages 287-316, 2014.
[10] Sally Floyd and Manfred Warmuth. Sample compression, learnability, and the vapnik- chervonenkis dimension. Machine learning, 21(3):269-304 1995.

---

[11] Yoav Freund. Boosting weak learning algorithm by majority. In Mark A. Fulk and John Case, editors, Proceedings of the Third Annual Workshop on Computational Learning Theory, COLT 1990, University of Rochester, Rochester, NY, USA, August 6-8, 1990, pages 202-216. Morgan Kaufmann, 1990.
[12] Yoav Freund and Robert E. Schapire. A decision-theorette generalization of on-line learning and an application to boosting. J. Comput. Syst. Sci., 55(1):119-135) 1997.
[13] David Haussler, Nick Littlestone, and Manfred K Warmuth. Predicting {0, 1)-functions randomly drawn points. Information and Computation, 115(2):48-292,, 1994.
[14] M. Kearns. Thoughts on hypothesis boosting. Unpublished. December 1988.
[15] Balázs Kégl. The return of adaboost. mh: Multi-class hamming trees. ICLR, 2014.
[16] Vitaly Kuznetsov, Mchryar Mohri, and Umar Syed. Multi-class deep boosting. Advances in Neural Information Processing Systems, pages 2501-2509, 2014.
[17] Nick Littlestone and Manfred Warmuth. Relating data compression and learnability. Unpub- lished manuscript, 1986.
[18] Shay Moran, Ohad Sharon, and Iska Tsubari. List online classification. arXiv preprint arXiv:2303. 153883 2023.
[19] Indraneel Mukherjee and Robert E Schapire. A theory of multiclass boosting. Journal of Machine Learning Research, 14:437-497 2011.
[20] Benjamin Rubinstein, Peter Bartlett, and Hyam Rubinstein. Shifting, one- mnciinlusion mistake bounds and tight multiclass expected risk bounds. In NIPS, pages 1193-1200, 2006.
[21] Mohammad J Saberian and Nuno Vasconcelos. Multiclass boosting: Theory and algorithms. In Advances in Neural Information Processing Systems, pages 2124-2132, 2011.
[22] Robert E. Schapire. The strength of weak learnability. Machine Learning, 5(2):197-227, 1990.
[23] Robert E Schapire and Yoav Freund. Boosting: Foundations and algorithms. Cambridge university press, 2012.
[24] Robert E Schapire and Yoram Singer. Improved boosting algorithms using confidence-rated predictions. Machine learning, 37(3):997-336, 1999.
[25] Glenn Shafer and Vladimir Vovk. A tutorial conformal prediction. Journal of Machine Learning Research, 9(3), 2008.
[26] Shai Shalev-Shwartz and Shai Ben-David. Understanding machine learning: From theory to algorithmms Cambridge University Press, 2014.
[27] John von Neumann. Zur theorie der gesellschaftsspille. Mathematische Annalen, 100(1):295- 320, 1928.
[28] Vladimir Vovk, Alexander Gammerman, and Glenn Shafer. Algorithmic learning in a random world, volume 29. Springer, 2005.
[29] Shaodan Zhai, Tian Xia, and Shaojun Wang. A multi-class boosting method with direct optimization. In Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 273-282, 2014.
12

---

A Missing proofs of Section 2
Proof of Lemma
/ Pr
First, standard analysis of the Hedge algorithm 12 implies that,
(1 = vol) S In(m) D:
+ 17T + H (3..
(6)
For completeness re-prove it here. Denote de E Li=1 (1(1) and ar PrenD,la(asi) vil). and observe that,
m2
Σ wr(i)e 111, ( Φ. Di(ile -((iee-v(h(0)))>- (M)(()))
11+1
w (1)
Φ:
yil + r/²) Φr 110t + Tr) S oie -
where the two inequalities follows from e= $ x + x² for x 2 0, and + x S E", respectively, Therefore, after T rounds we get Φr I me Eis TT Furthermore, for every E [m]] we have,
))H(())))) = wr( S or S me EI_
Taking logarithms and re-arranging we get Equation (6). as needed.
Next, we lower bound the left-hand side with + y by the weak learning guarantee. By also substituting !7 = 21
II(m))
we get,
In(m) T
H HI Mi)
k
T
Plugging in T yields the desired bound.
To prove the second part of the lemma, observe that by its first statement it holds that for each (3r, v) E S there must be label l + for which (ar, e) < T/k.
The following lemma proves that Algorithm 2 constructs a good initial hint to the boosting algorithm (Algorithm 3).
Lemma (Initial hint). Let mo, >> >
and let S E (X' x y) Given oracle access to an empirical Algorithm
y-BRG learner for S (Definition 4), when run with p [In(m)/7], Allgoi//l 2 outputs p of size such that for all (x, 9) E S it holds that y E p(z).
Proof. Observe that for all E [p] the output of the weak learner satisfies,
Pr (x.g)r=l,
(2)(x) yl 2 7
where this follows from Definition This implies that |spl I pm < e Pm <1
B
Missing proofs of Section
We say that list function μ X - y is consistent with sample S E (X 2) if for every (x, y) S, it holds that y E p(z).
We now define a compression scheme for lists as follows. Specifically,
say that an algorithm A is based on an m - r compression scheme for k-lists if there exists a reconstruction function p: (X x)") x)")" + (D such that when A is provided with set S E (X' x ) of training examples, somehow chooses (possibly in randomized fashion) subset S' S S of size r, and outputs k-list
function μ p(S'). Denote its error with respect to distribution D over X' x y as,
(p)
Pr
y $ m(x)].
(may)~
Next, we prove generalization bound for a compression scheme for k-lists. The proof follows similarly to [17 [0], extending these classical generalization bounds to the notion of lists.
13

---

Theorem 6. Letr S m be integers and & < 131. Let A denote a (possibly randomized) algorithm based on an m - r compression scheme for k-lists. For any S E (X x y)m t denote by fss the output of A over S. Let > O and set e rln(m)+ln(1/8) Then, for any distribution D over X x V, with probability at least - 8 it holds that if fs is consistent with S then, cND S.
Proof. We want to show that,
Pr [Is is consistent with S + (fr)(ss) S 2 1 S~Dm
(8)
In other words, we want to show that,
Pr Js is consistent with S A errp(fs) > >g S-Dm A
of S
(9)
The equivalence of Equations 8 and ( is because if A and B are events, then A = B is exactly equivalent to (-A) V B whose negation is A A (-B).
We overload notation and for any S' E (X 11"" we denote fs = p(S'), where p is the reconstruction function associated with A.
First, we fix indices i1,....ii ip E [m]. Given the random training set S. Observe that for any list function f X + y* that is c-had, then the probability of also having f be consistent with S S' is most (1 cm- This holds for any such f. and in particular fsr if it happens be c-bad. Since this also holds for any other fixed choice of indices i i,....,,, 4 E [m)] we can bound the above for all possible sequences of indices. Therefore, by the union bound, since there are m² choices for these indices, we have that for any fs chosen by A it holds that,
Pr [Is consistent with S A fs is e-bad S.DDi,,
(10)
Ess En Js consistent with S S S" A Ss is e-bad
Pr SmDm
(11)
Σ
[ss consistent with S S fs is e-bad SwDD
Pr
(12)
f
=m".
Pr D' glnpp
[s consistent with S" A fs is c-bad
(13)
m
Pr S S"n-Dm- g'-D"
fs consistent with S" fs is esdd
Pr swaDr
fsr is bad
(14)
m²
Pr Dm gpr
fsr consistent with s" fsr is e-bad
(15)
mm.. ES
[fst is consistent with s" gm
Pr
fsr is c-bad
(16)
I <m((1 - (1)-))m- c)m-r
(17)
where in Equation 12 inequality holds since for any particular selection of the examples S E (X' x 2) for which fs" e-bad, we have that Prs"*Dm-r fsr is consistent with s" S (1 (1--)mm- This means that also holds true if these examples are selected random. Then, we get the desired bound since m" (1 m) < m'e (rmm-) = 8, which follows by solving for 5 via our definition of above.
the notation S' = {22,) Vis .... (Iz.. Vb,)), and where the last
Theorem 7. Letr S m be integers and k < 13). Let A denote a (possibly randomized) algorithm based on an m - r compression scheme for k-lists. For any S E (X x y)m denote by fs the output of A over S. Let 8 > 0 and set (ln(m)+(mm1//))) Then, for any distribution D over X x Y,
Pr
(fTr((s) >
Pr
Is is not consistent with S + 8.
(18)
SWDD
SNDD
14

---

Proof. Let CA(S) 1 fs is consistent with S First, using the simple fact that for any two events and holds that Pr[A]] = Pr[A A B] Pr(A A - B & Pr[A A B) + Pr[-B], we get,
Pr Iss is e-bad]
(Ca(S) fs is e-bad] + Pr SNDMA ,
Pr
[Ca(S]]
SwD"
S-Dm,
Thus, it remains to prove that,
Pr [Ca(S) A Js is e-bad] So S~Dm
(19)
which holds true by Theorem 6 above.
Algorithm 4 Boosting Weak-to-List Learning
Given: training data S (X x 3) edge y > O, parameters T, > O.
Output: list μ + y
1: Let & be the smallest integer such that & <.
2: Call Hedge (Algorithm T with S and parameters n, T to get H : X y [0,
3:
Construct 2 + y such that for all x,
m(x) = LEE H(x >
T k
4: Output μ X ya-1 W & S, truncate paz) to first k 1 labels, if contains more.
The following lemma describes the list-learning guarantees that can be obtained when given access y-weak learner (Definition (). It is re-phrasing of Lemma from the main paper, using exact constants. The next paragraph highlights the assumptions that were made, followed by the proof of the lemma.
Specifically, we assume for simplicity that the learning algorithm does not employ internal random- ization. Thus, can be regarded as fixed, deterministic mapping from sequence of my unweighted examples, to a hypothesis h X' + y. We note that our results remain valid for randomized learner as well, yet we assume the above for ease of exposition.
Lemma 5 (Weak-to-Liss Boosting). Let H. C yx be hypothesis class. Let E, O, let k be the smallest integer such that & % and denote = 7 Let D be an H-realizable distribution over x y. Then, when given sample
+ In(2/5). oraale access 6 and T > 81n(m) and fj V In(m)
16 mo (n²)
D for m 2
a²e
to 7-weau learner (Definition 6 for H with 2 ma
(T))
o²
Algorithm 4 outputs list function X + y such that with probability at least - 6,
Pr (x.9)=
y & m(x) Sc.
Proof. By the learning guarantee Definition 6 we know that for every distribution over the examples in S, when given mg examples from D, with probability least 6/(22") the learner
returns h: X' + y such that
m Σ (() = vi 2
1 K
+o.
In line 2 of Algorithm we call Algorithm| 1 with S and the weak learner, with T, ") and mo as defined above. Then, we follow the same proof in Lemma [ applied to S such that the guarantees of the weak learner holds with probability at least 1 - 1-/((1)) as above. Then, taking the union bound over all T calls the weak learner, by the same argument of Lemma we get that with probability least 1 - 6/2 it holds that for all (z, y) E S,
I
[(b((x) 2
0
(20)
T
15

---

where hi....,hy hy are the weak hypotheses obtained via Algorithm and that comprise of H, the output of Algorithm| [ Moreover, notice that since the weak learning algorithm can be regarded as a fixed, deterministic mapping from a sequence of my unweighted examples to a hypothesis, hypothesis h4 can be expressed via these very my examples. Notice that H can be represented by m. examples. Thus, the list function jr defined in Line 4 of Algorithm 4 can also be represented mg
by - my examples.
Furthermore, we show that for every (I, E S the list p(a) is indeed of size at most A: - 1. This is true since for every æ E by the definition of H it holds that Eesy Hxx E) S T, and so we have that for all (ar, y) it holds that at most k labels & E y can satisfy ( [p(x)] < 1
T/k, and thus
Lastly, we observe that μ is consistent with S. That is, by Equation 20 and the definition of μ know that for every (z, y) E S, we have y E μuæz).
Overall, we get that with probability at least 1 T 6/(27) =1 5/2 over the random choice of Tmy examples, holds that the list function μl consistent with the sample S. Moreover, can be represented using only r examples, where r = T'm-
We apply a sample compression scheme bound to obtain the final result. Specifically, we consider the bound given in Theorem for a m - r sample compression scheme for k-lists. Then, f is consistent with S then with probability of at least 6/2 over the choice of S it also holds that,
rln(m) + In(2/8)
Pr (x
$ u(x)]
m r
Plugging in r Tmg from above, and setting
8 mo (m)
In(2/0)
8 8ln(m)mo
m
O2E
+ o²
yields the desired bound. That is, with probability least 1 5, we have Proly & ((x))
L
B.1 Proof of Lemma 3
Proof of Lemma
First, recall that the given oracle is such that for every H-realizable distribution
D. when given S D for my 2 me(e, ò), it returns us X + y such that with probability
1- 6,
y E us(x)) 21-6. (2
Pr
(21)
Then, we show that there is 7-weak learning algorithm W for H where y 1-2r k= for any 0. The construction of the algorithm W as follows. First, my == (e, do) for 8 = 1/2. The y-weak learner W has sample size to be determined later such that m mg, and is given training set ~ D Then, the learner W first calls the k-list learner with parameters e, ôg. my over S and obtains the list function μı that satisfies Equation (1 with probability at least - 60 1/2.
Henceforth, we only consider the probability-hall half event which we have that Equation (2T) holds. Furthermore, let Z denote the set of all elements (x., y) ~ 'D for which y E (s(r). Then, notice that by randomly picking j S k and denoting the hypothesis lt'. X + y defined by the j-the entry of ps. ps,iee. i.e., (z)()) = p=(z), we get for any (a, y) Z,
Pr -y- -1 1g( (z) Un-inif(k))
1
Te
Then, by von Neumann's minimax theorem (27 holds that for any distribution D' over Z, there exists some particular jo S k for which
1 12 (x)] 2 K (v
Pr (z.g)~
Since this true for the distribution D conditioned on as well, the algorithm can pick j S uniformly at random and so it will pick jo with probability $. Overall we get that when given S the
16

---

algorithm can call the list learner to obtain Ms and sample j uniformly to obtain ligg 2' + ) such that,
1-c
Pr Sm-m
Pr (rUUni((A)
1 = n]g(t)] (a.w)D
Pr
2
2
60.
Since we set dn 1/2, we get that,
1
Pr S~D J-m
yy = l1s(t)) 2 (a.D))>
Pr
(22)
2k
Lastly, note that the confidence parameter of 2F can easily be made arbitrarily large using standard seffidence-boosttign techniques. That is, for any 5 > O, we can set q = 2k (2g(2/6) and draw sample sets S1...,,, from D and call the algorithm
described so far to generate hypotheses hi.... hg which satisfy Equation (22) with respect to the different samples S, and different random draws of Unif(k). By the choice of q. we have that the probability that no h has accuracy at least 1-c is most (1 2k ) se t = 6/2. Thus, we get that with probability at least 1 5/2 least one of these hypothesis is good, in that it has accuracy of least 1-s We then pick the best hypothesis as tested over another independent set Sq+1, which we sample i.idd from D' where
r 10log(21/6) and e' e/ e/k: Then, by Chernoff's inequality we have for each of the h1, hy that with probability 1 - (2g) that the gap between its accuracy over Sq+1 and over D is at most //2. By taking the union bound, we get that this holds with probability 1 6/2 for all hi,.... hg simultaneously.
c²2
Thus when we choose the h with the most empirical accuracy over Sy+1, then with probability 1 6 it will have empirical accuracy of at least 1-c /2/ and true accuracy of at least 1-c c' Therefore, with probability at least 1 5 we get that the hypothesis chosen by our final algorithm has accuracy of least 7 I-2r over D.
Overall, get that W is a weak PAC learner for H. where 7 1-2c and with sample complexity m O (k- log(1/0) me00, 1/2) 2
log(k/8) 6a
B.2 Proof of Theorem
Proof of Theurem 3 We start with showing that 7(H) 2 1/k(H). By assumption, we have that for any fixed é1, 81 > 0, when given mi := mi (e1, 51) examples S drawn i.i.d. from a H-realizable distribution D, the list learner returns a function us X -> )k((H) such that,
Pr Sm/Dm
Pr [v E [s())) 2 a) 21 1-5 (as))
(23)
By Lemma 3 we get that for any O, there is 7-weak learner for H. where 7 := 1-2c
k(H)
Moreover, by definition of (HH) as the supremum over all such y values, we have (H)) 2 (1-)) Lastly, since this holds for any choice of e, we can take + 0 and get 7(H) 2 F[Z)
k(R)
We now show that (HH < 1/k(H). Let denote the smallest integer for which 1 < <HH,,, and let
To ((H) - 1 > 0. We will now show how to construct list learner via the given weak learner, for a list size of i 1. suffices to show that, since by the choice of we have 7(H) < 1/(k: - 1),
1/)(H) and we get the desired bound of (H)) 1/k(H). Thus, all that is left is to show the existence of the (k- ( -)- learner.
and so it holds that k(H) < k-
Let e1, 8, > 0, and let m(e1, 61) be determined as m in lemma for e1, 81. Set T = &log(m)
Let
ma := mo == (2T)) denote the sample size of a 7-weak PAC learner with 7 := 2
+ 1
Denote this weak learner by W. Then, by applying Lemma with the 7-weak learner W and with = Fo. we obtain the (k= 1)-list learner, which concludes the proof.
17

---

B.3 Proof of Theorem 4
Proof of Theorem The proof follows by constructing weak learner from the given oracle, and then applying weak-to-lis tostist boosting procedure.
First, by Lemma we get that there is 7-weak learning algorithm W for H. where 7 :=
1-26o
Ag
Then, by applying lemma 5 with this y-weak learner W, obtain (t 1)-List PAC learner, where < 1-1 Then, we also get that
1-2co S t-1 and so (t - -
ko 1-2en
Therefore, there is k-List PAC learning algorithm for H with fixed list size k
Kp
1-2c0
C Proof of Theorem
At a high level, the proof describes a construction of simple weak learner which is shown to satisfy BRG condition (Definition 4. This implies it is also amenable our boosting method, which yields the final result given in Theorem 5
The construction of the weak learner is based on an object called the One-inclusion Graph (OIG) [13 20 of a hypothesis class, which is often useful devising learning algorithms. Typically, one interested in orienting the edges of this graph in a way that results in accurate learning algorithms. As the analysis used to characterize PAC, and List PAC learning [5] [ as well as in most applications of the OIG 9 13 20). good learner corresponds to orientation with small maximal out-degree. However, here we show that a simpler task of minimizing the in-degree is sufficient to obtain a reasonable weak learner, and therefore strong learner as well.
We start with introducing relevant definitions.
The DS dimension was originally introduced by 19.. Here we follow the formulation given in 5 and so we first introduce the notion of pseudo-cubes.
Definition 9 (Pscudo-cube). A class H C yd called a pseudo-cube of dimension d if is non-empty, finite and for every h E H and E [d], there is an i-neighbor g H of h (i.e., g(i) # h(i) and g(i) = f(r all j + i).
When y = {0, 1). the two notions "Boolean cube" and "pseudo-cube" coincide: The Boolean cube {0, 11 is of course pseudo-cube. Conversely, every pseudo-cube H S {0, 1] is the entire Boolean cube = (0, 1)dd When | > 2, the two notions do not longer coincide. Every copy of the Boolean cube is pseudo-cube, but there are pseudo-cubes that are not Boolean cubes (see (5] for further details). We are now ready to define the DS dimension.
Definition 10 (DS dimension). A set S E X is DS-shattered by H C yx if HIs contains an n-dimensional pseudo-cube. The DS dimension dDs(H) is the maximum size of DS-shattered sequence.
A natural analogue of this dimension in the context of predicting lists of size k is follows: Definition 11 (k-DS dimension [).. Let H. S yx be hypothesis class and let S Xd be sequence. We say that H. k-DS shatters S if there exists F C H. |1, < oo such that Vf E Fls, Vi e [d]. f has at least k i-neighbors. The k-DS dimension of H. denoted as d = (H), is the largest integer d such that H k-DS shatters some sequence S E X
Observe that the two definitions above differ only in the number of i-neighbors they require each hypothesis have, and that dps dk for k = 1. Moreover, there are simple hypothesis classes with infinite DS dimension, yet finite kDDS dimension for k 2 2, see Example 3 in [8]
Next, we define the object called the One-inclusion Graph (OIG) [3 20 of hypothesis class, and related definitions which will be used for the construction of the weak learner.
Definition 12 (One-inclusion Graph [3 20 The one-inclusion graph of H C y is a hypergraph ((H) = (V, E) that is defined as follows
The vertex-set is V H. For each E [m] and
'We note that although Lemma assumes access a L-List PAC learner, same argument holds weaker version of list learner with size ko which depends on 6o, and the proofs of both cases identical. We use the term vone-inclusion graph" although it is actually hypergraph.
18

---

[i) + V let ei be the set of all h E H that agree with f on [n] \ {i}. The edge-set is [
E = {e
[n]. X (i) - e,,,, + 0).
(24)
We say that the edge e, & E is in the direction i, and is adjacent to/contains the vertex if E ei. Every vertex & V adjacent to exactly m edges. The size of the edge ei, the size of the set lei,fl
We remark that similarly to [ 8 edges could be of size one, and each vertex e is contained in exactly edges. This is not the standard structure of edges in hypergraphs, but use this notation because it provides a better model for learning problems.
With respect to the one-inclusion graph, one can think about the degrees of its vertices, all of which originally introduced [8], and are natural generalizations of the degrees defined [9]
Definition 13 (k-degree). Let G(H) (V, be the one-inclusion graph of C c)m The k-degree of a vertex E V is
E deg" E
now define the notion of orienting edges of one-inclusion graph to lists of vertices they are adjacent to. As alluded to earlier, orientation corresponds the behavior of (deterministic) learning algorithm while making predictions on an unlabeled test point, given a set labeled points input.
Definition 14 (List orientation). A list orientation at of the one-inclusion graph G(H) = (V, F) having list size k is a mapping o²: E - (V' V I < k} such that for each edge E E, (e) e.
The deoure of a list orientation o² is defined as: Definition 15 (l--out-degre list orientation). Let G (V, be the one-inclusion graph of hypothesis class H. and let a be k-list orientation of it. The k-out-degree of u V in o* is
outdeg" ow; :e: (c)))
(25)
The maximum k-oue- of t
outdeg (a*) sup outdeg" (u;tde""(;;o")) (e;a*).
(26)
veV
The following lemmas demonstrates how a bound on the dimensions helps one greedily construct a list orientation of small maximum k-out-degree.
Lemma 6 (Lemma 3.1, 8). If C pd+1 has k-DS dimension at most d, then there exists a k-list orientation t of G(H) with outdeg" 1 (o < d.
We now describe list version of the one-inclusion algorithm below, originally introduced by X
Algorithm 5 The one-inclusion list algorithm for H. C y>
Input: An N-realizable sample U = ((x1, v1),... ... (In, Vn)).
Output: A k-list hypothesis u X + (Y C ): |Y k}.
For each E X. the k-list 2 (z) is computed follows:
1: Consider the class of all patterns over the unlabeled data H (as......... S yn+1,
2: Find k--ist orientation o² of G(Hlie
that minimizes the maximum keout- 3: Consider the following edge defined by revealing all labels in
(h E H (() Vi E [m] h(1) y.)-
4: Set (x) (1(x)) : h (
19

---

Lemma 7. Let H. C yd be a hypothesis class, let D be an H--ralizable distribution over X x y, and let k. be integers. Let M be an upper bound on the maximum k-out-degree of all orientations rf chosen by Algorithm 5 and let p denote its output for an input sample U ~ 'Dn, Then,
M
Pr (U,(2.)))~Dm== (x) 7
n 1+1
Proof. By the leave-one-out symmetrization argument (Fact 14. we have,
Pr
Lub (z) E
Pr (U',))DDtt 1nif((+11 pb0 (x)) # vl
(U((na))~DD++)
It therefore suffices to show that for every sample U' that is realizable by H.
M
Pr
[ (xf) # v/
(27)
Uninff(n+1))
n n+1
Fix U that is realizable by H for the rest of the proof. Denote by ot the orientation of ((H') that the algorithm chooses.
Let y' denote the vertex (PH') defined by y' = (V/..... 1h+1). and let e, denote the edge in the
7th direction adjacent to y'. Then, we have that
m+
Pr [ (a() v/l
(af) # v/
i~Unif(n+1)
T +
1
1 ( 35
n +
outdeg (1/: (
n n
M
n + 1
C.1 Initial phase: pre-processing
Lemma 8. Let H. C y be a hypothesis class with k-DS dimension d < 00. Then, for every H-realizable S E (X x y) any D distribution over S, for sample U D" for n == when given U E (X x yy", Algorithm 5
returns bu X + y such that,
BUNDa
Pr [y E (()) 2 d=1 (aa))
(28)
Proof. This follows directly by combining Lemma and Lemma 7
Lemma 9. Let 7 C yd with k-DS dimension d < oc, and let S E (X x xymm be an H-realizable set. Denote by L a k-list learning algorithm as given Algorithm 5 Denote q (d + In(2m), and let r = qd O In(m)). Then, there exists algorithum A based on m - r compression scheme for p-lists as described next. When provided with S, and given oracle access to L, the algorithm yields a list function μ X + yp such that μ is consistent with S.
k and
Proof. We describe an algorithm that sequentially finds subsets of examples S S each of size d, and returns list u X' + y* using examples. First, let i/ denote the uniform distribution over the m examples in and let Z+I By Lemma 8 applied to the distribution 24, for a random sample Si ~ Ld, in expectation at least of the examples (xc v) E S satisfy that E μ1 (z), where in is the output of over Sy. particular, there exists S for which the corresponding μ4 covers at least am examples. Algorithnically, it can be found via a brute-force search over all possible md subsets S C S. Next, remove from S all examples (x. y) for which y E μ (x) and repeat the same reasoning the remaining sample. This way at each step j find sample S and list
20

---

Mj = (())) that covers at least an a-fraction of the remaining examples. After g steps, all examples
in are covered since |5y1 I (1 - )+ < <e *ेत m <
The final list returned by our method is y defined by the concatenation:
plx)
U 15(2),
j=1
and is based only on the examples in S m. S which is total of examples as claimed.
C.2 Constructing a weak learner for wrong labels
The following lemmas demonstrates how bound on the dimensions helps one greedily construct list orientation of small maximum (p - ---uuddeeree for class with labels.
Lemma 10. Let p. E and assume H S [p]" is a hypothesis class with a (p 1)-DS dimension al most d, where d < n. Then, there exists an orientation Gp of G(H) with outdeg outdeg"~((pp-)) (ap-1) 4(p- d)
Proof. Notice that H is finite, and so the number of vertices in ((H) is finite. We consider another notion of dimension called the k-Exponential dimension. We say that S X is k-exponential shattered by 7 S yx if HH|s 2 (k: + 1)lsI. The k-exponential dimension dHH is the maximum size of an k-exponential shattered sequence.
Notice that for the case that ) = [p] and k = p 1, we have that set S is (p 1) e--xonnnntiaal shattered if [ ss] 2 pl Observe that this definition coincides with that of the (p - 1)DDS dimension holds that
shattering. That is, a set (p 1)-DS shattered if for every h E H|s and every i has exactly p neighbors that agree with on [x]] {i). This definition implies that [H|ss 2 pS
Therefore, for H C [p)" we have that
h (H) = d% 1
Then, by Corollary 6.5 of ( we get that there is an there is a (p- 1)- orientation of G(H) with maximum (p- -out--eeee most 4(p 1) (H). Replacing de (HL) by d (H) yields the desired bound.
The following lemma is analogous to Lemma
Lemma 11. Let p N and assume H [p] a hypothesis class with (p - D)-DS dimension at most d. For every H-realizable set S E (X' x (p))m. any D distribution over S, denote by uby :X + 1p]p-1 the p 1-list that is the output of Algorithm when given a sample U DApd Then,
EUnDAAd
Pr Iy E mb (x)) 2 (r.g)/
Pr
1
(29)
4p
Proof. For any U [011 v1), ..., (In, yn)) where
4pd, and any text point (z., v) D, let
H C [-] be the class of all patterns over the unlabeled data (l as in Algorithm 5
Notice that by Lemma 10 have that for any such class H, there is orientation with maximal
(p -eout-deere of at most d. Therefore, by Lemma 7 we get that,
EU-Dand
ly pb pz (w)] (aUN)
Pr
Pr y 1t (z)) (V.( d
d(4p 1) +1
>
(4p--11)) - 1)/4p.
4pd +1
4pd +1
21

---

Theorem 8. Let p E N and assume H. C [p]* is a hypothesis class with (p 10-11 1)-DS dimension at most d, and let S (X [p be an realllize set of examples. Denote by C a (p - learning algorithm as given in Algorithm 5 and let r = 4pd [8p² In(2m)).
Then, there exists an algorithm A based an m + compression scheme for (p 1 such that, when provided with S and given oracle access to L, the algorithm A yields a list function a + (p]-11 that is consistent with S.
Proof. Let D denote any distribution over the examples in S. For random sample U ~ -UApd denote luu = L(U). By Lemma
11 we have that in expectation over the random choice of U, ju (x)] -1- 1.2 Therefore, there exists particular set U of size 4pd for
holds that ()( which this holds as well. Algorithmically, this particular set can be found via a brute-force search over all possible m Apd subsets U C S of size 4pd. We now have a (p - 1)- function pu = L(U) such that with probability 1 satisfies Pr(a.))~D(V E (c))) 2 1 4p"
Notice that while μu covers large fraction of the examples, it is not entirely consistent with S. The remainder of the proof will be concerned with boosting the list learner we have described above, into new list X' y that is indeed consistent with the entire sample.
Towards that end, we first use yay to define a classifier Jo X' + [y] that predicts the incorrect labels. Specifically, we set fxx(x) 5 for ý E [p] \ ( Thus, we have that with probability 1,
1
(x) vl (#.9)~
Pr
(30)
4p
So far we have shown that for any distribution D over S there is a set U E S and a corresponding function fu X + [p] (constructed from peu L(U) as above), that satisfies Equation (30).
Next, by von Neumann's 's minimax theorem 27 there exists a distribution Q over all possible subsets U C S of size at most 4pd such that for all examples (x, y) E S it holds that:
1
Pr UNQ Pf = 4p
Let Uj...., Ug be random samples from Q where i = [8p² In (2mm). Denote U2 = (U1, U2), and define Fo, to be a corresponding averaged-vote, such that for any X' and y E [p]:
Σ [1(((((0=)))
Fo, v)
Observe that for a fixed example pair (I, S then by Chernoff bound we have,
Pr Ge~Qu
(x,
2 2p
< Pr ve~Q'
Fo, 2 BlFo, (z. y)1 +
1
(31)
4p
se 200/4//)) =c -1/(80") < 2m
1
(32)
Then, by union bound over all m examples in S we have that with positive probability over the random choice of Ug it holds that Fo, (x, y) < 2p over all (I, y) E S simultaneously. This implies that there exist particular choice of Ug for which we have with probability for all (x, y) S that:
y & arg max Fo, (x, 9).
$E(p)
In words, this means that taking the plurality- as induced by Uc, we will yield an incorrect label with probability 1 over all examples in S simultancously.
Lastly, we ready define the final list function μ : X - ipp-11 by:
((x) = [p] \ arg max Fo, (x.
(E(P)
To conclude, we have constructed an algorithm based on m -> 4pd compression scheme for (p -istts, that is consistent with the training sample S, as claimed.
D
22

---

Algorithm 6 L-List PAC Learning for a class H. C y with dhs xc
Given: Training data S E (X' x ")m.
Output: A list X + y
1: Set k- (d + 1) In (2m) (as chosen in Lemma 9).
2: Initialize: applying pre- pre-processing as given Lemma 9 to get μr X + y.P
3: for wrj=1,.... ......
k do
4: Let S and 7 denote and H. with all labels converted from y to Ip j + 1] via Mj.
5: Call the list learner given in Theorem over 5 and HJ, to obtain jıy X - (p - j + 1]p-5.
6: Define Uj+1 X - yp- by:
Ms+1(z) = (v: -{v: 3e, 15(x)) = a (E
7:
end for
8: Output the final list μ == Mp-k++1
Proof of Theorem The proof is given via sample compression scheme argument, demonstrating that for a class with a finite k-DS dimension Algorithm i k-list PAC learner. That is, we prove that it returns list μ : X' + 3*t which be represented using small number of training examples, and that is consistent with the entire training set.
We will then show for each j I...p k that 1z+1 satisfies the following 2 properties: (a) the list Pj+1 is consistent with the entire sample S, and (b) it can represented using only small number ry of training examples.
First, notice that by Lemma it is guaranteed μni is consistent with S, and that it can be represented by r1 d(d + 1) (2m2) examples, as it is constructed by an m + compression scheme.
Next, will show that the properties (a) and (b) above hold for all round j of Algorithm 6 the class H! has only p - j + 1 labels, and its k-DS dimension remains d as in H. Furthermore, by the properties of the k-DS dimension it holds that for any k' k have dbs S dis. Thus, for all j S p-pp- k.
2. Notice that in each
Lps (H²) & (Ht) = d.
Therefore, can apply Theorem 8 and get that both properties (a) and (b) hold with ry 4(p j 1)d [8(p j + 1)a [2(2))] for all j 2, ..., P k.
Overall, have shown that the final list μ Mp-k+1 is both consistent with the sample S, and can be represented using only r examples, where,
p k+1
+
Σ
(33)
j=2
p- k+1
= d(d + 1) ln(2m) + Σ
(4pp-j - + 1)d [8(p j + 1)2 In(2m))
(34)
f=2
S d(d + 1) ln(2m) + 32d In (2m)pp +
(35)
0 k In 1n((m))
(36)
where the bound follows by plugging the value of p from Algorithm (and Lemma 9
We can now apply a sample compression scheme bound to obtain the final result. Specifically, we apply Theorem for m + r sample compression scheme algorithm A equipped with reconstruction function (see Definition 8). We denote (πT = P((x))))(u(()) $ v). Then, by
Theorem we get that for any 8 > 0.
rln(m) + lm(1/8] $ 6,
Pr
( >
m T r
Plugging in r from Equation
36) yields the desired bound.
23


Reviews:
[{"review_id": "hZEqLqFTBq", "reviewer": "Reviewer_Zpmo", "summary": "This paper proposes a generalization of boosting to the multiclass setting. To this end, the authors introduce a new weak learning assumption for multiclass based on a ‘hint’, which takes the form of a list of $k$ labels, named ‘Better-than-Random Guess’ (BRG). the authors present a main boosting method and provide theoretical analysis for PAC guarantees. Finally, the authors demonstrate applications based on the framework of List PAC learning.", "questions": "Could you provide some experiments, including synthetic ones? It would be very helpful to understand this paper.", "limitations": ".", "rating": 4, "confidence": 1, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "- This paper proposes a new weak learning assumption, which encompasses both the binary case (i.e., $k=2$) as well as the cases with $k>2$.\n- The main method is well-written.\n- This paper provides abundant theoretical analyses.", "weaknesses": "- Although this paper is based on theories, it lacks experiments, including synthetic ones, and there is no conclusion.\n- Due to the lack of experiments, there is insufficient comparison with previous works, with only half a page dedicated to it in section 1.2.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their feedback and suggestions.\n- “lack of experiments” - we emphasize that the main contribution of this work is the theoretical framework extending classical boosting theory to the multiclass setting. The algorithmic contribution is not the main focus of the paper. The question of finding the simplest and minimal assumptions on weak learnability as in the binary case has been studied in various works over the years, and in this work we provide the first intuitive and simple condition that leads to a simple boosting procedure. We leave the question of obtaining an optimal running time and performing empirical evaluations as an interesting future work. We certainly hope this will be further explored in a following line of work.\n- “comparison with previous work” - we refer the reviewer to the introduction, where we compare the current paper to various lines of work in the context of multiclass boosting. Moreover, the related work section covers other works in the broader context of boosting, starting from early extensions from the binary case and up to the most recent work in the area. The most related works, and most recent results on multiclass boosting theory, are [16] and [6], which are discussed in both sections. \n"}, {"review_id": "IlE2FIHaj5", "reviewer": "Reviewer_bGbo", "summary": "The paper proposes a novel treatment of traditional (non-gradient) boosting to multiclass prediction problems. In particular it shows that a novel relaxation of the weak learning criterion allows the definition of boosting algorithm with the usual success guarantee of reducing the empirical misclassification rate on the given data sample arbitrarily with high probability. This relaxation requires the base learner to also accept as “hint” a subset of labels and to, for each possible subset size k, to return a hypothesis that achieves an error rate better than 1-1/k with high probability. The proposed boosting algorithm makes use of this property by recursively eliminating candidate labels from the hints of each training example based on the hypotheses produced by previous iterations. Moreover, the paper shows a connection of the proposed theory to list-PAC learning and in particular gives a new characterisation of list-PAC learnability.", "questions": "- In footnote 3 the authors state the assumption that m0 does only depend poly-logarithmically on m. It is unclear to me how strong an assumption that is and in fact also how sensitive the feasibility of the method is to violations of that assumption.\n- My other questions is how to address the potential limitation listed below.", "limitations": "One potential limitation might be the definition of weak learners that satisfy the weak learning assumption. This is because it seems to require the restriction to different subsets of classes for different inputs. It is not immediately obvious to me how one would incorporate this, e.g., with a decision tree (if it depends on the concrete model at all). \n", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "- The paper develops a beautifully simple extension of boosting to the multiclass case that, in contrast to previous approaches, does actually work to define a successful strong learner\n- The connection to list learnability are very interesting\n- The paper is well written and accessible", "weaknesses": "- Papers on classical boosting, in contrast to the additive ensembles produced by gradient boosting, feel rather narrow at this point. In particular, generalisations from misclassification rate to proper statistical loss functions are unclear.\n- There is no empirical performance investigation of the proposed recursive boosting algorithm", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their feedback and suggestions.\n\n- “Papers on classical boosting … narrow” - Gradient boosting methods are valuable algorithmic tools but lack a theoretical framework for studying the task of interest: multiclass classification, with respect to classification loss. Unlike binary boosting theory, gradient boosting methods cannot characterize sample complexity needed to reach a desired level of accuracy or reveal fundamental limitations. In contrast, our approach directly generalizes the theoretical boosting framework for multiclass classification that can answer these questions for general multiclass learning settings.\nMoreover, it does so through the classification loss itself, rather than proxy losses, as is the case for the gradient-based approach. \n- “empirical performance” - We note that, as the reviewer points out, our generalization provides a “beautifully simple extension of boosting to the multiclass case”. As such, and as discussed above,  we view the main contribution of this work to be the generalization of boosting theory. The algorithmic contribution is not the main focus of the paper. We leave the question of obtaining an optimal running time and performing empirical evaluations as an interesting future work. We certainly hope this will be further explored in a following line of work. \n- Footnote 3 - In the context of PAC learning, m_0 is only dependent on gamma, the edge of the WL. The comment says that the results hold even if m_0 is sublinear in m. We now see that this footnote is confusing and we will re-phrase it in the final version.\n- “weak learners that satisfy the weak learning assumption” -  observe that when given a list of, let’s say the top-5 choices of labels y per example x, we can “re-name” the labels of each example to be each position in the list! Therefore, we have effectively reduced the original label space to contain only 5 labels. That is, because the label names themselves don’t matter, we can do this re-naming and apply any standard learning algorithm as a WL (e.g., decision trees). We hope this answers the question, and will clarify this point in the paper as well. \n\n"}, {"review_id": "l0CyV3Nea1", "reviewer": "Reviewer_Rb54", "summary": "Boosting algorithms is an important fundamental question in SLT starting with celebrated AdaBoost algorithm. While the original results consider binary setting and the condition on the weak learner is straightforward, it is not trivial to formulate the same result for classification with more than one classes.\n\nI did not have the chance to go through the proofs carefully due to time constraint. I do not see where there could be a potential mistake that cannot be fixed. I did not read through section 4 and I am not familiar with list learning.\n\npros:\n- interesting fundamental problem\n- the paper is well written\n- a new condition for multiclass boosting\n- relatively simple proof\n- connection to list learning\n\ncons:\n- the only disadvantage I can see is that this paper would better fit other venues\n\n\nminor comments and questions:\n- should Theorem 1 be stated only for realizable case, since you relying on the compression scheme generalization bound?\n- it is better to refer to Theorem 30.2 (than to Corollary 30.3) in Shalev-Swartz and Ben-David since your \"outer\" risk is equal to zero only with probability close to one\n- perhaps this is obvious or I have missed it, but how does your condition compare to conditions of existing results for the multi-class boosting?", "questions": "-", "limitations": "-", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "-", "weaknesses": "-", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their feedback and suggestions.\n\n- “Theorem 1 ” Notice that in our framework (in contrast to previous works on multiclass boosting) realizability assumption is not needed, and the empirical BRG assumption suffices to get the result. The reason is that by using compression bounds we only need to show that the boosting algorithm’s output is consistent with the training data, which is shown in the proof of Theorem 2.\n- “Theorem 30.2” we agree with the reviewer that this would be a better reference. We remark that in our current version of the paper we use a more accurate (and more general) statement of a compression bound that we prove in the paper. We will incorporate this in the final version of the paper as well.  \n- “compare to conditions of existing results' ' - first we note that conditions of previous works, in particular [6,16] assume the PAC setting and realizability w.r.t a hypothesis class, whereas here these restrictions are removed. Moreover, these prior works require the WL to be agnostic and learn for any re-labeling of the data. Thus, these methods operate in the rather narrow setting of assuming realizability of the data, while also having access to an agnostic learner. However, it may be interesting to examine, when restricting to the PAC setting, how these conditions are related.  \n \n"}, {"review_id": "vHx5kvt5jC", "reviewer": "Reviewer_Ut8K", "summary": "This paper tackles the problem of multi-class boosting by proposing a novel definition for weak-learning based on list boosting. The authors define a weak-learning condition for multi-class learning based on the simple principle of slightly better than random guessing. This definition is then used as a stepping stone in order to filter the potential classes for a sample recursively, thus reaching a stage where either the binary weak-learning condition can be applied, or the weak-learning condition BRG leads to boostability. The authors propose several theoretical justifications and definitions for the results presented in the paper.", "questions": "* How does the current framework compare to existing ones? Are the WL conditions introduced in [6] and [16] stronger than BRG?\n* Any experimental results available?", "limitations": "The limitation of have not been discussed.", "rating": 4, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "# Motivation\nMulti-class boosting has received a lot of attention since the introduction of binary boosting, in particular since the extension of the weak-learning condition from binary to multi-class setting is tricky. As such, the novel definition of weak-learning introduced in this paper is quite interesting, especially since its simplicity mirrors the binary one.\n\n# Theoretical results\nThe strongest point of this paper. The authors propose several theoretical justifications throughout the paper, and the generalization result in Theorem 2 is quite promising, same for the relation between weak PAC learning and list PAC learning in Theorem 3.", "weaknesses": "# Existing frameworks\nThere are several existing frameworks for multi-class boosting based on specific weak-learning conditions (some of which are cited in the paper). I strongly think that an actual comparison between the proposed framework and the existing ones should have been included. Particularly for methods such as Adaboost.MM and Adaboost.MR and their WL conditions, and the WL framework introduced in \"Multiclass boosting and the cost of weak learning.\" [6].\n\n# Experimental results\nI'm not entirely sure why no experimental results are proposed in the main paper. There are several multi-class boosting that have been successfully used in practice, despite their WL conditions, as such it is important for new/novel methods to be compared to state-of-the-art approaches. In particular how the proposed method fares against state-of-the-art ones both in accuracy (or other multi-class performance measures) and in runtime. The recursive nature of Algorithm 1 and its dependance on 3 hyper-parameters might lead to prohibitive runtimes, even though several optimizations have been mentioned in the main paper.\n\n# Conclusion and future works\nI strongly think that a section on the future works and possibilities would've been more appropriate than the proof of Theorem 2. More globally, the paper could benefit from a better global organization.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their feedback and suggestions.\n\n- “comparison between … existing ones” - The reviewer implies that we have not included a comparison to prior works, yet all of the works they mention are explicitly discussed in the paper. Addboost.MR is mentioned in line 130, and is a rather old extension to multiclass boosting (other works such as [16] have generalized it). Adaboost.MM is given in [16], a framework we compare with both in the introduction and in the related work section. Similarly, [6] builds off of the framework of [6] and discussed in our paper as well. To briefly explain the comparison to these results, first we note that conditions of previous works, in particular [6,16] assume the PAC setting and realizability w.r.t a hypothesis class, whereas here these restrictions are removed. Moreover, these prior works require the WL to be agnostic and learn for any re-labeling of the data. Thus, these methods operate in the rather narrow setting of assuming realizability of the data, while also having access to an agnostic learner. However, it may be interesting to examine, when restricting to the PAC setting, how these conditions are related.  \n- “lack of experiments” - we emphasize that the main contribution of this work is the theoretical framework extending classical boosting theory to the multiclass setting. The algorithmic contribution is not the main focus of the paper. The question of finding the simplest and minimal assumptions on weak learnability as in the binary case has been studied in various works over the years, and in this work we provide the first intuitive and simple condition that leads to a simple boosting procedure. We leave the question of obtaining an optimal running time and performing empirical evaluations as an interesting future work. We certainly hope this will be further explored in a following line of work.\n"}]

Author rebuttal:

Meta-review: The work provides an original and rigorous analysis of Multiclass Boosting, notably by introducing a clever "better than random guessing" assumption based on a "hint" given to the weak learner. This kind of analysis is welcomed as it goes beyond the straightforward extension of existing works and thus fosters new ideas. 

Nevertheless, I agree with the reviewers that it is unfortunate that the authors disregard empirical experiments. Although not required to justify acceptance, empirically evaluating the proposed "Recursive Boosting" method would have been natural. It might have aroused the interest of a larger audience, which is suited to a broad venue such as NeurIPS.

Finally, as I noted a few grammatical typos looking at the paper, I enjoin the authors to proofread their manuscript carefully. The References section should also be revised, as it contains a few arXiv bibliographic entries accepted in peer-reviewed venues.
Decision: Accept (poster)