Multiclass Boosting and the Cost of Weak Learning
Authors: Nataly Brukhim
Elad Hazan
Shay Moran
Indraneel Mukherjee
Robert E. Schapire
Venue: NeurIPS 2021 Poster (2021)
Keywords: Boosting

Abstract: Boosting is an algorithmic approach which is based on the idea 
    of combining weak and moderately inaccurate hypotheses to a strong and accurate one. 
    In this work we study multiclass boosting with a possibly large number of classes or categories.
    Multiclass boosting can be formulated in various ways.
    Here, we focus on an especially natural formulation in which the weak hypotheses
    are assumed to belong to an ''easy-to-learn'' base class, and
    the weak learner is an agnostic PAC learner for that class
    with respect to the standard classification loss.
    This is in contrast with other, more complicated losses as have often been considered in the past.
    The goal of the overall boosting algorithm
    is then to learn a combination of weak hypotheses
    by repeatedly calling the weak learner.


We study the resources required for boosting, especially how they
depend on the number of classes $k$, for both the booster and weak learner.
We find that the boosting algorithm itself only requires $O(\log k)$
samples, as we show by analyzing a variant of AdaBoost for our
setting. In stark contrast, assuming typical limits on the number of weak-learner calls,
we prove that the number of samples required by a 
weak learner is at least polynomial in $k$, exponentially more than the
number of samples needed by the booster.
Alternatively, we prove that the weak learner's accuracy parameter
must be smaller  than an inverse polynomial in $k$, showing that the returned weak
hypotheses must be nearly the best in their class when $k$ is large.
We also prove a trade-off between number of oracle calls and the
resources required of the weak learner, meaning that the fewer calls to the
weak learner the more that is demanded on each call.

Multiclass Boosting and the Cost of Weak Learning
Nataly Brukhim
Elad Hazan
Princeton University
Princeton University
Google AI Princeton
Google AI Princeton
obrukhii@princettom..o
ehazzan@rrinceoon.co
Shay Moran
Indraneel Mukherjee
Technion
indraneel htt.:/eeee.mmmeeeeeeeppooooooooo
Google Research
smoran@@techiinn.acc
Robert E. Schapire
Microsoft Research
Abstract
Boosting is an algorithmic approach which is based on the idea of combining weak and moderately inaccurate hypotheses to strong and accurate one. In this work we study multielass boosting with a possibly large number of classes or categories. Multiclass boosting be formulated in various ways. Here, we focus on especially natural formulation which the weak hypotheses are assumed to belong to an "casy-to-learn" base class, and the weak learner is an agnostic PAC learner for that class with respect to the standard classification loss. This contrast with other, more complicated losses have often been considered in the past. The goal the overall boosting algorithm is then to learn a combination weak hypotheses by repeatedly calling the weak learner.
We study the resources required for boosting, especially how they depend on the number of classes k; for both the booster and weak learner. We find that the boosting algorithm itself only requires Ollog k) samples, as we show by analyzing variant of AdaBoost for our setting. In stark contrast, assuming typical limits on the number of weak-learner calls, we prove that the number of samples required by weak learner is at least polynomial in k, exponentially more than the number samples needed by the booster. Alternatively, we prove that the weak learner's s accuracy parameter must be smaller than inverse polynomial in k showing that the returned weak hypotheses must be nearly the best in their class when is large. We also prove trade-off between number of oracle calls and the resources required the weak learner, meaning that the fewer calls to the weak learner the more that is demanded each call.
Introduction
Boosting [16] is a fundamental primitive in machine learning, most widely studied and applied in the context of binary supervised learning. Yet many important problems require classification into great many target classes. For example, in image object recognition and building language models, the number of classes scales as the number of possible objects, or the dictionary size, respectively. is thus of practical as well as theoretical interest to generalize boosting the multiclass setting.
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

In contrast with binary classification, there are several versions of multiclass boosting since there more than one way to extend the weak learnability assumption. With only two labels, we simply require that the weak learner find hypothesis with error slightly better than 1/2, that is, bit better than random guessing. So when the number of labels k is more than 2. perhaps the most natural extension requires that the weak learner outputs hypotheses with classification error slightly better than a random guess among the k labels, that is, with error a little better than 1 - 1/k. However, this turns out to be too weak for boosting to be possible. Instead requiring classification error less than 1/2 is sufficient for boosting, but far stronger than mere random guessing. Other approaches are based on reducing the multiclass problem to multiple binary problems, constructing loss functions to be minimized by the weak learner that are significantly different than the simple classification error. See [3] [6 and references therein for detailed discussion.
Weak Learning Assumption. In this work we return to the classical formulation of boosting in which the weak learner aims to minimize ordinary classification loss, though in way that sidesteps some of the hurdles just discussed. Specifically, we assume the weak learner an agnostic PAC learner for some base class, meaning that it can find the approximately best hypothesis in that class. This requirement differs subtly, but importantly, from the kind we have been discussing in which, say, the weak hypotheses must have error not greater than some value; instead, the criterion is relative to this particular base class. Further, we take this class to consist of simple hypotheses, in line with the common supposition that weak hypotheses are rules of thumb from "easy-to-learr" class [16] [8). Thus, the weakness of the weak learner is manifested in the simplicity of the hypotheses in the base class, and the goal of the overall boosting algorithm is to learn target concepts outside the base class by aggregating the weak hypotheses provided by the weak learner. A similar setting was recently considered by 3 who studied binary-labeled classification.
Which target concepts can be approximated by boosting weak hypotheses from a given base-class? In this work we assume that the target concept can be represented by weighted plurality votes over the base class. To motivate this assumption, note that: (i) Most boosting algorithms (in both binary and multiclass settings) output weighted vote of weak hypotheses [16 10, 8 D. Thus, if one focuses on such algorithms, it becomes a necessary condition that the target concept can be approximated arbitrarily well by such votes, and hence yields our assumption. (ii) In addition, the work by [16] conducted a thorough study of a variety of natural weak learning assumptions for multiclass boosting, and showed that each of those assumptions implies the plurality vote assumption. (iii) Finally, weighted votes are extremely expressive: for example, in the binary-labelled case, the work by B showed that under extremely mild assumptions on the base-class, one can approximate arbitrarily complex concepts by weighted votes. Relatedly, [19] proved that assuming a non-trivial base-class, one can obtain Bayes-consistent learning algorithms by boosting using weighted votes.
1.1 Contributions
We study the resources required for boosting, especially how they depend on kt, the number of classes. For the booster, these include the number of examples needed for learning and the number of oracle calls to the weak learner. For the weak learner, we measure the required accuracy, that is, how close the returned hypothesis must be to the best in the base class, or alternatively, the number of unweighted samples the boosting algorithm feeds the weak learner in each round.
A Multiclass Boosting Algorithm. Our starting point (and first contribution) is natural variant of AdaBoost (Algorithm D. which demonstrates that it is possible to replace previously considered weak learners by one which aims to minimize the classification loss. Indeed, we prove that Algorithm T is able to learn any task which satisfies the general multiclass weak learning assumption of [13), which they proved to be necessary and sufficient (see Section 2).
However, closer inspection of our algorithm reveals a surprising phenomenon: while the sample complexity of the booster exhibits a standard logarithmic dependence on k (the number of labels), the
of the weak learner depends quadratically on k. which is exponentially worse. In more detail, our algorithm requires that at each round f, the weak learner returns a hypothesis he whose excess loss relative to the best hypothesis in the base class is less than 1/k, which means, since k is assumed to be large, that h4 is nearly optimal. Stated differently, using standard statistical arguments, in each round I, our boosting algorithm provides the weak learner with O(k2) unweighted training examples (ignoring parameters other than k). This demonstrates a striking discrepancy

---

between the amount of information (in the form of labeled examples) the boosting algorithm uses from the source distribution and between the amount of information exchanged between the boosting algorithm and the weak learner.
Thus, the central question of study in this paper is whether a large dependence on the number of labels & is inherent in the interaction between the weak learner and the boosting algorithm. This question has a direct and significant relationship with the overall complexity of multiclass boosting. Indeed, each call to the weak learner amounts to solving learning problem over the base class whose complexity is controlled by the prescribed excess loss. Thus, when the number of labels large, would be highly beneficial to improve the dependence exhibited by our Algorithm
An Impossibility Result. Interestingly (and somewhat disappointingly), we show that the discrep- ancy between the sample complexities of the booster and weak learner inevitable: in Section we prove that, assuming typical limits on the number of weak-learner calls, the number of samples required by the weak learner is at least polynomial in k. which is exponentially more than the number of samples needed by the booster. Alternatively, we prove that the weak learner's 's accuracy parameter must be smaller than an inverse polynomial in k, meaning that the returned weak hypotheses must be nearly the best in the base class when & is large. This lower bound follows from more general trade-off that we prove between the number of oracle calls (to the weak learner) and the sample complexity of the weak learner, meaning that the fewer calls to the weak learner the more that is demanded on each call. Specifically, we show that at least one of these quantities must be ((())) Ri).
From a technical perspective, the main challenge in proving this trade-off the construction of the base class; specifically, the requirement that the base class is easy- to--arm rules out naive randomized constructions e.g. as in the oralle-comllexity lower bound in (16) ) and requires a subtler treatment.
Summarizing, for the model of multiclass boosting that we study, we prove that there is a striking discrepancy between the amount of information (in the form of labeled examples) the boosting algorithm requires from the source distribution and the amount of information exchanged in the channel between the weak learner and the booster.
1.2 Related work
The boosting methodology is fairly mature method, originally formulated for binary classification (e.g. AdaBoost and similar variants) [16]. In contrast with binary classification, there are several versions of multielass boosting, since there is more than one way to extend the weak learnability assumption. The earlier extensions of boosting to the multiclass setting include AdaBoost. and AR [17), as well as (2)- These works often reduce the k-class problem into single binary problem with a k-fold augmented dataset, or to multiple one-versus-all binary problems using Error-Correcting Output Codes (ECOC). The binary reduction can have various problems, including increased complexity, and lack of guarantees of an optimal joint predictor.
When requiring weak learners with classification error less than 1/2, a reduction binary problems is unnecessary. Then, AdaBoost. MI is a straightforward extension of its binary counterpart. We refer the reader to the book by [16] (Chapter 10) for a through survey of the various extensions of AdaBoost to the multiclass setting.
5 15 were designed from practical perspective, and provide empirical results of their approaches. Thus, while these works achieve improved performance across various applications, they do not provide comprehensive theoretical framework for the multiclass boosting problem, and are often based on earlier formulations (c.g., a one-versus-all reduction to the binary setting, or multi-dimennional predictors and codewords).
More recent methods (20 12
Notably, previous work by [3 established a theoretical framework for multiclass boosting, which generalizes previous learning conditions. Moreover, as previous boosting methods were shown to require weak learning conditions that are either too strong or too weak, 13 outline an appropriate weak learning condition that is both necessary and sufficient for multiclass boosting. However, this requires the assumption that the weak learner minimizes tailored loss function that is significantly different from simple classification error. See the next section for a detailed discussion.
3

---

2 Background
We study boosting algorithms that aim to learn a combination of hypotheses from a fixed base class H S y The data domain X' is finite countable, and y is the finite set of labels [k] == {I,.... k). for k 2 2. In particular, we consider boosting the task of learning a target concept that can be presented as a plurality-vote of hypotheses from H with margin bounded away from 0. A plurality- vote over the hypotheses class is characterized by distribution À over H. and the corresponding classifier h -(A) is defined by
h(x)= == arg max - [f([r) =
(1)
ZE(M]
The boosting algorithm is given oracle access W, weak learner that is agnostic PAC learner for H. The weakness W is manifested in the simplicity of H Concretlly W defined as follows; for every distribution D over X' x V. and e" 8" > O, when given a sample of m (s 8²) examples drawn i.idd from D, W outputs h E H. such that with probability 1 1-6 1-5",
P ((..))=(((()) = yl Z sup ((sa)>D(h (x) = yl c. kt
The weak learner W considered in this work is defined with respect to the standard classification loss, rather than more complex formulations given in previous work on multiclass boosting. Next, discuss alternative weak learning condition that shown to be necessary and sufficient for multiclass boosting 13
2.1 Optimal weak learnability
We briefly review the formulation introduced by [33 which considers weak learning condition with respect to a particular gain function, rather than the standard classification objective. Albeit requires solving a seemingly unnatural classification sub-problem, it was shown to be, in certain sense, optimal. Consider the following formulation. For any hypothesis h E H. any labeled example (x, X ), and any incorrect label & e V, define:
+1,
if h = y: if h(x) = e otherwise.
-((()) = vl [[h(x) = -1=
-1
0.
Consider the following dual perspective shown by 13 that is associated with the above gain function:
m-aagin.. The 7-margin assumption with respect sample S, holds if there exists distribution over H (corresponding to plurality-vote), that has a large margin for every tuple (x, y, f), of labeled example from S, and an incorrect label. Concretely,
3λ E An. v(E E S. y.
ERSA BALA|on(E.U 2 2.
(4)
e-dg of H. The edge is the gap between the performance of a certain hypothesis over random
prediction. Define S = ((x E) (x, E S, f y) the set of incorrectly-labeled examples (with respect to S). The empirical 7-weak learnability assumption of H holds, if for any distribution D over 5. there a hypothesis E H that has an edge of y (as is typically referred to in the binary boosting setting with respect to D. over random prediction. Concretely.
VD E Ag.
3h E H,
E Te.0wolan(a,.) 27
(5)
'The simplicity of the base class is measured via its Natarajan dimension, extension of the VC-dimension the non-binary setting. See Section for the formal definition and discussion. NNte that for uniformly-random predictor f. and any distribution D. E
lay ( {]] 0.

---

Previous work by [13] has shown via a minimax argument that, for given training set S, for the realizabilitty of S by some y-margin plurality-vote h to hold, i... for equation (4) hold, it is both sufficient and necessary condition that equation (5) is satisfied. That is, 4 holds if and only if (5) holds. Note that these observations are only concerning a fixed training set S. Next, we extend these ideas using the following notion of a 7-realizable distribution.
Definition 1 (y-realizable samplerdistribution). Let R E (0,1), y* a hypotheses class. A sample 5 _ X' x y is y-realizable with respect to H if Equation (4) holds. A distribution D over X' x y is r-realizable with respect to H if any independent sample from it is "-realizable
The end goal of the boosting algorithm is to approximate target 7-realizable distribution D with respect to classification loss. The booster is provided with oracle access to a learner for the base class H. well as e" 8 > 0 and m(e". 8²)) examples drawn i..d. from D. The booster makes T iterative oracle calls to the learner and outputs a plurality-vote hy such that with probability - 8
((a)))(((T(T)) # s
(6)
3 Multiclass Adaboost:
algorithm and analysis
We give an efficient adaptive algorithm for multiclass boosting, which converts an agnostic-PAC learner for the base class H. to a learner for any target distribution that is yy-realizable with respect to H. Towards that end, we first give a reduction to the framework provided by [3]
Specifically, we show the that the o-gain weak-learning condition (defined in Equation 5 captured by a standard classification loss, agnostic PAC learner for H. (Equation 2
5) can be
Lemma 2. Let S C X x y be a training set, and 5 = [(x, () y) E E + y) the corresponding set of incorrectt-llaeelled examples. Let W be an agnostic- PAC learner for H yxx Let c 8 and edge y > O, and assume that S is "y-realizable sample w.r.t. H. Then, for any distribution D over S. there is a distribution D over S U S, such that when given sample of m mm ,8)) examples drawn ii.d from D. W outputs E H. s.t. with probability 8"
(e.e)~lla((t:1 Wi, {)] 2 k
Observe that our conversion of a classification loss learner to a a-gain learner comes at a cost, as incurs a multiplicative overhead of factor k in the excess error. The implications of that fact on the sample complexity of the learner are further described in Section
Next, present multiclass boosting approach, described in Algorithm I We remark that AdaBoost.MR [77 a previous boosting method that a version of AdaBoost for ranking loss, applics similar technique described in Algorithm However, their algorithm requires access variant of the o-gain learner for H. whereas our method only assumes a standard classification loss learner.
we show that the predictor outputted by the boosting algorithm, given Algorithm is consistent with the training data.
In the following result, formally stated in Theorem 3
Theorem 3. (Upper bound- Consistency) Wet be agnostic-PAC PAC learner for the base class H. C yX. Let y, 5 > O. and training set of m labelled examples. If is rrealizablle with respect to H. (see Definition 14, then applying Algorithm 1 with T > ((oo(m)))oog(k) and m mma 00r/kk8//6 8/T),
72
outputs with probability at least 1 8, an hrr that consistent with S.
'Our results remain valid for relaxed definition of r-realizable distribution for which r-rraalizable samples only drawn with high probability. However, we consider the above for simplicity of presentation.
5

---

Algorithm Multiclass Adaboost
1: Input: S = {(1), vi)........... (0mm }m)}.
2: Initialize: (i, mik-Ij if l # yi, else set 0, for & E [k]. [m²]
3: for /= 1,..., T do
4: Obtain D, from Dj (see Lemma 2. and pass mh examples to W drawn i.d from D,.
5: Let h2 be the weak hypothesis returned by W, compute its empirical edge:
7t = E2 (1,)0 [onn (2e, yr. f)].
6: Set 0z
in
1+7re I-
Update, for all E [m]] Vi + flE [k]:
e eea
if he (e = Yss if he (z:) E.
Ei. De+1(i,))
c
Zr
otherwise.
(i, exp( (-ay- Tn, (Ir. E))
74
where Ze is normalization factor (chosen so that D.+1 will be a distribution).
7: end for
8: Output the weighted plurality-vote.
T Σ at (1) t=1
- =1)
hy (x)
argmax (E(K]
Runtime analysis. The number of iterations required for Algorithm to succeed has only logarithmic dependence on the number of labels Nonetheless, since the algorithm maintains distribution DD over the data, of size m k. it might seem if the cost of each round linearly dependent on However, observe that the updates to distribution only pertain to incorrect labels é which at least one of f.,,..., he mistakenly predicted to be correct. Thus, at most mf such values are being updated. Moreover, note that performing a random sample from D; (step 4 of Algorithm can be done in time (llog)m)) 7 as D, D maintained by the algorithm can be kept sorted throughout the iterations. Therefore, the running time of each round is (m logmm))), and the overall running time only has poly-logarithmic dependence k.
Sample complexity upper bounds
In the previous section we have focused on the consistency model, and have shown that a multiclass boosting algorithm with running time of only log dependence on k, can achieve zero training error. In this section we examine the generalization aspects of the algorithm. The results described below have two main implications, concerning the sample-complexity required for the boosting algorithm as a black-box (subsection 4.2). and the sample-complexity of the weak-learner required in each iteration, within the boosting framework (subsection 4.1)
We show that the one hand, the sample complexity required for the booster defined in Algorithm 1 to learn a 7-realizable distribution D over X' J/, is upper bounded by m = ((lo(()). However, the upper bound we give on sample complexity of the weak learning oracle W is m. O(k²), omitting other terms. This striking contrast naturally raises the question of whether a different boosting approach exists, such that the large dependence on is significantly improved to match the logarithmic upper bound of the algorithm. In Section 5 we provide lower bound showing that these gaps are inherent the problem of multiclass boosting.
Natarajan dimension of H. In the binary case, the VC-dimension characterizes the sample com- plexity of hypothesis classes. In the multiclass case, [44 introduced an extension the VC-dimension to non-binary functions, defined as follows.

---

Definition 4. Let H. S. VV hypothesis class and let S S X. We say that H. N-shatters S if 2,, S y such that vxx E S, Ti (z) + Tz(z), and for every S S there is h E such that,
Vx E T, M(x) th (z), and Vx E S T, h(x) = T2(x).
The Natarajan dimension dy (H), is the maximal cardinality of a set that is N-shattered by H.
The
Natarajan dimension coincides with the VC-dimension for k = The Natarajan dimension of a hypothesis class, (H),, characterize the sample complexity required for PAC-learning the class H. up to multiplicative factor of (log(k)) Specifically, by [6 [ the sample complexity required to agnostically-PPa -PAC learn class H is upper bounded by.
mh (e, 8) O dd (H) log(k) +In(1/0)
(
2²
4.1 The sample complexity of weak-learning
In section B we have discussed a reduction of a classification-lor learner to a o-gain learner. However, this transtormation required a multiplicative overhead of factor the excess error. Observe that by plugging in any E" < 7//k, we get that the hypothesis returned by W has strictly positive edge, which allows boosting. The implications of that fact on the sample complexity of W are summarized
in Remark [] which immediately follows from Theorem 3 Lemma 2 and Equation (7)
Remark& 5. Given oracle access to an agnostic- PAC learner W for H. and sample set of size m, applying Algoritlum ] with T O(lo((mk)/7²) oracle calls W, setting ef < <//k, and passing ma 00 ( (og(F)
k?) examples to W. yields an output hy consistent with
4.2 The sample complexity of Boosting
Next, we show that the sample complexity required for multiclass boosting to learn a 7-realizable distribution D over X' x y, does only require a logarithmic dependence on k. This bound on the sample complexity is given by considering the output predictor Algorithm T and bound the sample complexity that is required for it to generalize.
In the following result, formally stated in Theorem 6 we bound the generalization error of predictor outputted by the boosting algorithm, given in Algorithm T In particular, we use a margins- -assed analysis of the generalization error (see margins- analysis for the binary case in [16], chapter 5.2), utilizing two key facts; (i) the predictor fyr obtained by Algorithm has a large empirical margin, and (ii) uniform convergence applies the margin of ftr. Moreover, the large large margin property both holds empirically, and generalizes, while requiring only a logarithmic dependence on k. These facts are formally stated and proved in the appendix.
Theorem 6. (Upper bound- Generalization) Let D be distribution over X x y that is --realizable by a hypotheses class H y and 7 > O. Let c, 5 O, and the training set be a random sample of m θ (H) (k) log(!) + (log(1/6) examples drawn i..d from D. Then, with probability 1 8.
722
over the random choice of the training set S, applying Algorithml with T = O (lg(mm)) outputs predictor by such that,
P P(.,))=
(T((x) # u] Se.
Note that although Theorem 6 pertains to the complexity required for learning via a boosting algorithm; similar statement can even be verified to hold for any ERM learner for 7. S y which can learn any 7-realizabll for H. with similar sample complexity. This follows from the definition of 7-realizability, the fact that sparse plurality-vote can be sampled from the realizable one (a proof technique also used Theorem [6) and the sample complexity bound given Z Overall, we get that the task of multiclass learning, either directly or via boosting, has a logarithmic dependence on k.
5 Matching Lower Bounds
In this section, we give lower bounds on the sample and oracle complexities required for a boosting algorithm to attain a small generalization error, for large number of labels Y k. Alternatively,
7

---

such bounds can be inverted to give a a lower bound on the generalization error that can be achieved by a boosting algorithm for a fixed sample complexity and running time. Thus, these bounds characterize the efficiency of any multiclass boosting algorithm, in terms of how the number of rounds and samples must depend on the desired accuracy, with respect to k.
5.1 Model definition
Recall that in previous sections, a weak learning algorithm W was defined be an agnostic-PAC
learner for a hypothesis class H. which satisfies Equation (2). Towards the goal of providing a lower bound for general boosting algorithm, consider two alternative, standard models of interaction between a booster and weak learner, that only differ in the input the weak learner expects to receive.
1. Boosting-by-reet bysammmpliingg in this form of interaction, the oracle W is a learning algorithm for H S y such that when given set of m (Gw, 8n 1/3) labelled examples drawn i.i.d. from distribution D over X' x V. it returns an eu optimall hypothesis in H. with respect to the classification loss over D. In this setting, we consider the learner W to simply be an ERM (empirical risk minimizer) for given sample.
in this model, the learner W is allowed to directly utilize the 2. distribution over examples DD so that the weighted training error is approximately minimized explicitly, but W may still return any opptimal hypothesis in H over D.
In addition, now define what is a general boosting algorithm here, for either interaction form. A boosting algorithm B is one which, when provided with oracle access a weak learner W for H (in either model of interaction; resampling or reweighting), as well as c., 8 0, and training set S of m = m(c". 88) examples drawn i.i.d. from a target distribution D over X' x y that is y-realizable (see Definition 1b. will with probability at least 1 8 output combined hypothesis that is a plurality-vote of hypotheses h H. obtained via the learner W, such that its classification error with respect to D is at most ca. In our construction, we simply fix e = 2y, and 8 = 1/2.
Although the boosting algorithm may be randomized, we can regard its randomization source, denoted R. as itself an input to the algorithm. Thus, we view B as a fixed and deterministic function of the training set S, the internal randomization R, and the responses obtained via the learning oracle W.
Note that we assume B does not know the hypothesis class H. and its only access to it is through its access to the learning oracle W. However, it is allowed to have other information about the weak learner, such restricted the booster such that it may only output plurality-vote of hypotheses h E H obtained via the learner W. Aside from the above, the boosting algorithm B is entirely unrestricted.
" the required sample size of W, the associated edge 7, etc. Note that also
5.2 Results
We derive lower bounds using simple construction of a class H. and base learner W, applied in both models described above; by-resampling and by-reweighting. The main idea of the construction is of designing a simple class H. such that its hypotheses will make diverse mistakes which the booster cannot know in advance. This forces the booster to pick a distribution D, with a large support of S(( ((Vk) elements, and require high accuracy & = 1/k. Otherwise, it can be shown no matter how the obtained hypotheses are combined in a plurality- there will always be large mistake, unless large number of rounds T 22( Vk) is used. This trade-off between oracle and sample complexities provides the lower bound we seek, showing that any booster incurs cost of 2 ((Vk).
Theorem 7. (Lower bound) Let 7 E (0, 1/21 denote the margin parameter, k > 2 number labels, and assume that k > 2/7. Let T > 0 denote the number of iterations. For any boosting algorithm B, by- byreeeeighting or by-resampling, there exists a class H. C yx, an agnostic- PPC learner W for H. and a target 3 -realizable distribution D. such that; If B is applied with oracle access to W for T iterations, and for all S T, picks error rates ef > 0= k-1/-- (reweighting model), or picks sample size m. < 1/0 (resampling model), and then outputs a final hypothesis hB, then,
2T
PS.R PD [b((T) F 27] 2 1/2,
8

---

where S is the initial random training sample drawn from D. and R. denotes the internal randomiza- tion of the boosting algorithm.
The trade-off between the oracle and sample complexity bounds is demonstrated in Corollary Seiilarymeexx next.
Corollary 8. (Lower bound complexity trade-off) By applying Theorem 7 with different values of T, we get that for any boosting algorithu B to achieve error rate at most 27,
1. There exists class H and learner W, s.t. if B makes T = =(2) oracle calls W, then there some S T which W must incur a sample complexity of m 22kk).
2. There exists a class H and learner W, s.s. either B makes T = 9(VK) oracle calls to W, or there is some & S T in which W must incur sample complexity of m. = Q(Vk).
3. There exists a class H and learner W, s.A. for all I S T, the sample complexity of W is m = O()), then B makes T = (KV oracle calls to W.
Recall that & is thought of the very large, dominating term, compared to 1/7. However, the results shown in Corollary [ only rely on the assumption >> 1/7- We remark that if k: > 1/7, the interplay between the time and sample complexity bounds changes accordingly. For example. if l > 1/72. can be similarly shown that the first item of Corollary 8 holds for T = 0(+)) as well.
5.3 Proof overview
Below is an informal, high-level, overview of the proof. We refer the reader to the appendix for the formal statements and proofs. We begin with describing the construction of the class H. Let X = (#1...., } be the domain, with n = 2y
1 data points, and assume that n << k. We fix the constant function f(z) 1 to be the target labelling. Then, the labelled data is { (I.. 1)}, and let the target distribution D be the uniform distribution over it. We note that our construction and the lower bound argument hold even for boosting algorithms that have full knowledge of the data and distribution D. However, recall that the boosting algorithm restricted to only output a weighted plurality-vots of hypotheses ht" ...hh" H obtained via W. Next, consider hypotheses of the following form; for all j [n]] and & E (2.... k3. define
hz,0(x) [1 if ar Kjjs otherwise.
We denote the set of all such hypotheses as Hall The base-class H. will be carefully chosen random subset of Hall The key properties that guide the construction of H are: (i) a uniform plurality vote over all hypotheses in H. yields the target-function f with margin ((y), and (ii) every weighted plurality vote of a proper subset of H is far-away from f.
We then use the probabilistic method randomly construct H. Specifically, the class H contains 2n - 2 carefully chosen hypotheses that are fixed, and a single random hypothesis, hy. where L drawn uniformly at random from the set of labels 2n, ..., k (recall that k > n).. We stress that the 2n hypotheses, and the index j, are chosen such that for each possible L, the obtained class satisfies the two properties noted above.
Observe that the class Hau is an easy-to-learn class, and it can be verified that it has a constant and that it is learnable by any ERM with sample complexity independent of k. Since H C Hall for any L, it exhibits theses traits as well. Moreover, by property (i) discussed above, it holds that there exists a plurality-vote over H. that is consistent with the data, with margin 7/2. That is, the distribution D which is uniform over X x {1} is 7/2 rr2rrealiz,,le, with respect to H.
Natarajan dimension
We refer to the randomly chosen hypothesis h, L as the hidden hypothesis. Note that if the booster cannot "discover" the hidden hypothesis throughout its run (i.c., obtain it via the weak learner), then by property (ii) of H. any weighted plurality it can output must have large error. Thus, it suffices to exhibit an agnostic PAC learner for H. for which the booster will fail to obtain the hidden hypothesis unless the saarraacysampll-coolleeee
are high.
The "fndeer-hooser" game. The above construction forces any successful boosting algorithm to find the hidden hypothesis. This is the crucial observation needed for our proof and it enables us to

---

design a weak learner which reduces the task of finding the hidden hypothesis to the following simple "finder-chooser" game. This an iterative game which a "chooser" player picks a "hidden" element I out of set of elements K, of size |K] = k. and a "finder" player iteratively attempts to discover it. Specifically, the finder is only required find any small subset of elements from K that the hidden element T. belongs to. Towards that end, in each round the finder queries the chooser, and the chooser replies with a binary response, which indicates the chooser has indeed picked the hidden element. We consider two different query- models in which the finder is allowed to interact with the chooser; via weights, or via examples (which correspond to the alternative model of boosting, discussed in subsection 5.1 In both cases, the finder is given binary response in each round, of whether or not the hidden element is in the subset it picked. If the finder failed, it continues to the next round, otherwise it succeeded to find subset which contains L, and the game ends.
clear that there a trade-off between the size of the picked subsets and the number of rounds needed to find the containing subset. We formalize this trade-off, and give bounds on the probability that the finder succeeds, when the chooser is uniform over K. This in turn, yields the desired bounds by reduction to the boosting setting.
6 Conclusion
We study the problem of multiclass boosting, where we focus on the case where the number of labels > 2 is large, and study how k affects complexity aspects of boosting. Our first result is a natural extension of Adaboost to the multiclass case, using simple weak learning oracle. We then show that there is a prominent gap between the sample complexities of the weak learner O(k2), and of the boosting algorithm (llog(k)) (k)), that are needed for learning. Finally, we give lower bound which shows that indeed, even for trivial (constant-tin -anstant--ime) learning tasks of both the base class and the target, learning via boosting is more challenging task. That is, large dependence on & is in fact an inherent cost required for multiclass boosting.
Acknowledgments and Disclosure of Funding
S. Moran is a Robert J. Shillman Fellow and is supported by the ISF, grant no. 1225/20, by an Azrieli Faculty Fellowship, and by BSF grant 2018385. Part of this work was done when S. Moran was at Google Al Princeton. N. Brukhim and E. Hazan acknowledge the support of NSF grant 1704860.
References
[1] Naman Agarwal, Nataly Brukhim, Elad Hazan, and Zhou Lu. Boosting for control of dynamical systems. In International Conference on Machine Learning, pages 96-103. PMIR, 2020.
[2] Erin L Allwein, Robert E Schapire, and Yoram Singer. Reducing multiclass to binary: A unifying approach for margin classifiers. Journal of machine leurning research, 1(Dec): 13-141, 2000.
[3] Noga Alon, Alon Gonen, Elad Hazan, and Shay Moran. Boosting simple leamerr. STOC, 2021.
[4] 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-194. PMLR, 2017.
[5] Oscar Beijbom. Mohammad Saberian, David Kriegman, and Nuno Vasconcelos. Guess-averse loss functions for cost-sensitive multielass boosting. International Conference on Machine Learning, pages 586-594. PMLR, 2014.
[6] Shai Ben-David, Nicolo Cesabianchi, David Haussler, and Philip M Long. Characterizations of learnability for classes of (O.... n)-valued functions. Journal of Computer and System Sciences, 50(1):74-88) 86, 1995.
[7] Karl Bringmann and Konstantinos Panagiotou. Efficient sampling methods for discrete dis- tributions. International Colloquium on Automata, Languages, and Programming, pages 133-144. Springer, 2012.
10

---

[8] Nataly Brukhim, Xinyi Chen, Elad Hazan, and Shay Moran. Online agnostic boosting via regret minimization. In Advances Neural Information Processing Systems, 2020.
[9] Amit Daniely, Sivan Sabato, Shai Ben-David, and Shai Shalev-Shwartz. Multiclass learnability and the erm principle. The Journal of Machine Learning Research, 16(1):2377-2404, 2015.
[10] Varun Kanade and Adam Kalai. Potential-based agnostic boosting. In Advances in neural information processing systems, 2009.
[1]] Balázs Kégl. The return of adaboost. mh: Multi-class hamming trees. ICLR, 2014.
[12] Vitaly Kuznetsov, Mehryar Mohri, and Umar Syed. Multi-class deep boosting. In Advances in Neural Information Processing Systems, pages 2501-2509, 2014.
[13] Indraneel Mukherjee and Robert E Schapire. theory of multiclass boosting. Journal of Machine Learning Research, 14:437-497, 2011.
[14] Balas K Natarajan. On learning sets and functions. Machine Learning, 4(1):67-97, 1989.
[15] Mohammad J Saberian and Nuno Vasconcelos. Multiclass boosting: Theory and algorithms. In Advances in Neural Information Processing Systems, pages 2124-2132, 2011.
[16] Robert E Schapire and Yoav Freund. Boosting: Foundations and algorithms. Cambridge university press, 2012.
[17] Robert E Schapire and Yoram Singer. Improved boosting algorithms using confidence-rated predictions, Machine learning, 37(3):297-336, 1999.
[18] Shai Shalev-Shwarts and Shai Ben-David Understanding Machine Learning From Theory to Algorithms. Cambridge University Press, 2014.
[19] Peter L. Bartlett Mikhail Traskin. Adaboost is consistent. In Advances in Neural Information Processing Systems 19: Proceedings of the 2006 Conference, volume 19, page 105. MIT Press, 2007.
[20] Shaodan Zhai, Tian Xia, and Shaojun Wang. A multi-class boosting method with direct optimization. Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 273-282, 2014.


Reviews:
[{"review_id": "b1H8DXOobtH", "reviewer": "Reviewer_6X9w", "summary": "This paper tackles the important problem of multi-class boosting, where the base learners are multi-class learners rather than binary ones. The authors introduce a new definition for the weak learning condition in the multi-class setting and propose several theoretical results based on this new condition. The centerpiece of the paper is the multi-class Adaboost algorithm, an Adaboost-like procedure incorporating the weak learning condition.", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "Multi-class boosting has attracted a lot on attention since the early days of boosting. Several weak learning conditions as well as frameworks have been proposed, each one having strength and weaknesses. This paper introduces yet another definition of weak learning condition in the multi-class setting, tailored for cases where the number of classes is arbitrarily high. The authors make use of several tools, such as the Natarajan dimension, in order to provide several theoretical results and guarantees. The key ideas are easy to grasp and overall the contributions are interesting.\n\nThere are however several shortcoming in the current version of the paper. First of all, while the main ideas are easy to grasp, the paper in itself is not easy to read. There are several awkward formulations and typos. For instance, in Section 1, the sentence on the relation between the number of samples required by the booster and the weak learner, is repeated several times. Formulations such as base class, which refers to the class of classifiers, can be misleading in a paper about multi-class boosting. The liberal usage of hypothesis, classifier and predictor, or plurality-vote instead of majority vote (the most commonly used term), or the agnostic term, is also confusing.  Lines 178, 179 and 249 contain several typos.\n\nSecondly, and this is my main gripe with this paper, it is unclear to me wether Algorithm 1 is derived from the theoretical contributions of the paper or wether the theoretical results are custom tailored for Algorithm 1. In the former case, I think that it would've interesting to have a (partial) derivation of the Algorithm and how all these results are combined. In the latter case, which I suspect to be the case, this severely limits the impact of the contributions.\n\nAnother important point, which follows up the previous one, is that only Algorithm 1 is studied in the theoretical discussions. I strongly think that proposing other approaches that benefit from the new WL condition would've given a better understanding of the impact of these results. Moreover, it's disappointing that there isn't a discussion on how other WL conditions and/or multi-class boosting algorithms are represented in the proposed setting, or how they compare.\n\nFinally, while I understand the authors' motivation for including all the theoretical results in the main paper, I think that the current version of the paper is overloaded with theoretical results and definitions, making it hard to clearly understand the scope of this paper. For instance, I'm not entirely certain I understand the relation between Section 5 and Algorithm 1.\n\nOverall, it's an interesting paper, but in my opinion, it needs to be polished a bit more.\n\nafter rebuttal : I appreciate the thorough response provided by the authors for all the points raised in my review, however I still think that the paper needs to be polished in order to deliver a clear message on its scope.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Not applicable.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "what's the point of this question?"}, "extra_text": {}}, {"review_id": "P5jgjJFhkYZ", "reviewer": "Reviewer_i7mp", "summary": "The authors propose  a new algorithm for multiclass boosting (Multiclass Adaboost) with strong theoretical guarantees. In particular, they show an upper bound by $O(\\ln k)$ on the number of oracle calls needed for consistency on the training set, under a margin-realizability assumption, where $k$ is the number of possible outputs. Moreover, they provide an upper bound on the sample complexity of the algorithm in terms of the Natarajan dimension of the hypothesis class, which, again, depends on $k$ as $O(\\ln k)$.\nFinally, they present a trade-off between the number of oracle calls T and the size of the sample that is passed through the weak learner : at least one of them must be of order greater than $\\sqrt{k}$ in order to keep a constant accuracy.", "questions": "", "limitations": "", "rating": 7, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "The paper is overall very well written and the contributions to the field seem to be strong. I have found interesting the idea of studying the algorithmic complexity in addition to the sample complexity of the proposed algorithm in order to exhibit a trade-off. As I am not an expert in boosting, I can not evaluate the impact of this paper on the litterature with high confidence. \n\nHowever I think that it could have been interesting to run some experiments in order to compare Multiclass Adaboost with the other existing approaches. Moreover, concerning the trade-off I was wondering if it was somewhat optimistic : do you think that in practice, for some specific hypothesis classes, $T$ and $m^w$ must be both strictly greater $O(\\sqrt{k})$ in order to keep a constant accuracy ?", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Due to the theoretical nature of the paper, I do not see any potential societal impact of this work.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "GoXfqfn2HF", "reviewer": "Reviewer_DyJ5", "summary": "This paper focuses on the boosting approach, in a multi-class setting, with a possibly large number of classes. It lays a theoretical background on the theoretical analysis of this particular setup, giving key definitions. Then, it presents a new boosting algorithm based on this groundwork, and provides a theoretical analysis of its training behaviour. It switches its focus to the generalization guarantees of the presented method. It ends on a broad study of the multi-class boosting task. It analyses the required quantity of information needed for a boosting algorithm to perform and presents a trade-off between the complexity of the weak learner and the number of calls by the boosting algorithm.", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "# Originality :\n\nThis paper presents a theoretical work in the multi-class boosting setup. It is a well-studied setup, as boosting is very popular, and the multiclass tasks are more and more common. However, the originality of this paper relies on the fact that it gives a theoretical framework to its algorithm and presents general and meaningful results on the sample complexity of multiclass boosting algorithms. It presents sample complexity theorems similar to Boosting : Fundation and Algorithms, but in the multiclass setup.\n\n# Quality : \n\nThe submission presents 3 theorems that are thouroughly proven in Supplementary Materials, the theoretical analysis is strong. It does not provide any experimantal result, but as it is a theoretical work on multiclass boosting, it does not impact negatively the quality of the paper. This work is complete, as it provides an algorithm, its theoretical analysis and the resultant general theorem about the sample complexity of multiclass boosting.\n\n# Clarity : \n\nThe submission is very dense : it provides an algorithm and a number of meaningful results in the available space. The content is well organized, starting with the theoretical background leading to the development of an algorithm. And ending on a theoretical study of this algorithm, that lead to a general result on multiclass boosting. It is clear for an informed reader that has some experience in the field, but could be a challenging read for a curious outsider that wants to have an in-depth understanding of the results. However, as the main claims are clearly provided in the introduction, the results are easily accessible.\n\n# Significance : \n\nThis work provides a unique theoretical framework to an intuitive result : the sample complexity of multiclass boosting algorithms grows with the number of classes. This paper provide an in-depth analysis of this statement, for a specific algorithm, and in general. This is an important theoretical result, that has applications for the day-to-day use of multiclass boosting approaches. To the best of my knowledge, the sample complexity of multiclass boosting algorithm was not studied, so this work is a generalization of fundamental work on the binary version.\n\n# Additional comments and straightforward corrections : \n\n## Important corrections : \n\n* Theorem 3 : $m_w = m_w(\\gamma/k, \\delta/T)$ is inconsistent with the proof where the assumption is made that $\\epsilon = \\gamma/(2k)$\n* 553+ The simplification of $\\epsilon_n \\leq 1/2 \\epsilon$ should be explained, as it is unclear as is (from eq. 59 to 60, the second term of the addition is clearly simplified in $\\epsilon/2$, but the third one is left to the reader, and the calculus requires too much work to be considered trivial).\n* 665 The assumption is made that $\\delta^B \\leq 1/2$, this means that the statement at line 640 does not lead to Theorem 7. It would if $\\delta^B \\geq 1/2$. However if the assumption is made that \\delta^B = 1/2, it works. So there is no need for $\\delta^B$ as in 664+2, you already have $P_{H, S, R}[...] < 1/2$ which is sufficient for the implications in lines 637-640. Similarly, at line 679+1\n\n## Strainghtforward corrections (The following are not exhaustive, but only what was found during reviewing, to the best of my knowledge) : \n\n* Last sentence of the abstract (p1 l20-22) is not that clear, especially l21-22, might want to replace \"of\" l21 and rephrase \"the more that is demanded\".\n* P4 footenote 3 \"for which a \\gamma-realizable samples\" sounds weird.\n* Alg1 l6 \"$y_i \\neq l \\in [k]$\" -> \"$l \\in [k], l \\neq y_i$\" seems clearer \n* Adding the notation \"$\\sigma$-gain\" at the end of l 153 could help with a smoother understanding of the following (it is used in l 179, but never clearly introduced in the paper)\n\n(Some lines where not labelled in the Supplementary Materials, so the comments use the last labelled line + the number of unlabelled lines)\n\n* As the supplementary material is already quite long, it could be more reader-friendly to remind the theorems before the proofs, similarly for the lemmas in Sections C.4-6\n* 463 \"Then, THE corresponding\" \n* 499+2 & 506 change 'the Lemma' by 'Lemma \\ref{lemma9}'\n* 505+2 \"by the the fact\" remove one 'the'\n* 505 + eq 35 : replace $=$ by $\\leq$ as $Z_t \\leq \\sqrt{1-\\gamma_t^2}$ and replace $(1-\\gamma_t)^{1/2 - \\gamma_t/4}$ -> by $(1-\\gamma_t)^{1/2- \\gamma_t/8}$ (no impact on the end of the proof)\n* 505 + eq 36 also holds because $1+x \\leq exp(x)$\n* 512, 522 \"a combined hypotheses\" -> \"a combination of hypotheses\" or \"the combined hypotheses\"\n* 566 \"for the case that\" sound weird\n* 573,574,575,579,585 use \"two\" and \"one\" instead of \"2\" and \"1\"\n* 585, 586,587  hypotheses -> hypothesis\n* 617 \"distribution of\" -> \"distribution over\"\n* 626+1 The lemma sounds weird : either move F, or add a comma\n* 657 corresponds -> correspond\n* 662 \"can by\" -> \"can be\" ?\n* 673 \"example was is\"\n* 696 'the Lemma' -> \"Lemma \\ref{}\"\n* 698 \"1 hypotheses\" -> \"one hypothesIS\"\n* 715 next -> Next\n* 723 \"note\" -> \"Note\"", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The assumptions on which the theoretical work is built are clearly stated in the paper, and I can not think of a negative societal impact of this submission. ", "review_text": "", "extra_scores": {"ethical_concerns": "This theoretical work has no ethical issues.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "13h"}, "extra_text": {}}, {"review_id": "33pbCz02MdK", "reviewer": "Reviewer_66dG", "summary": "As a theoretical work, this paper considers the multi-class boosting setting. It studies the resources required for boosting,  especially how they depend on the number of classes $k$, for both the booster and weak learner. Further, it gets several interesting theoretical results. ", "questions": "", "limitations": "", "rating": 7, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "First, I have to admit that am not an expert in this field, especially for the computational learning theory about boosting. But, I believe this is a solid work for multi-class boosting, especially for large class space settings.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "No.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The work is an original contribution to the theoretical study of multiclass boosting, and meets NeurIPS quality standard.

For the readers' benefit, I kindly ask the authors to take into account reviewer's 6X9w comments and clarify the scope of the contribution while preparing the camera-ready version.
Decision: Accept (Poster)