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@princeton.co
Shay Moran
Indraneel Mukherjee
Technion
indraneel htt.:/eeee.mmmheeeeeeppooooooooo
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 "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 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 Ad [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 E (1, 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 (I,, {]] 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 "-rralizable
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, E)] 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,)) [onn (2e, yr. ()].
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- byreeeiighting 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 Seiiaarymeexx 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 rrarrealiz,,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": "wUD6lLxqdOJ", "reviewer": "Reviewer_U7yb", "summary": "The paper presents an analysis of multiclass boosting, showing that the boosting problem itself is simpler to learn (in terms of the sample complexity wrt the number of classes), than the problem of producing acceptable weak learners which can be boosted.", "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": "It would be helpful to contrast the boosting algorithm in algorithm 1 against the other algorithms described in reference 13, especially Adaboost.MM, and to unify the notation a little (as this paper refers to sigma-gains, which are the cost matrices in ref 13).\n\nThe text after Theorem 6 is confusing. If any ERM learner can learn a gamma-realizable hypothesis with O(log(k)) sample complexity, then it would be helpful to clearly explain what restrictions force the weak learner to have a sample complexity of O(k^2).\n\nUpdate: thank you for the responses, I think some of the clarifications for the other reviewers and I should be included in the final text.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The theoretical work is hard to place in the literature of boosting as there is little analysis of what the results imply for extant multiclass boosting algorithms, or the relative complexity of large multiclass problems. It's also unclear at what level the number of classes starts to be the dominant complexity issue for boosting weak learners. Much of the text says k > 2, but some sections require k >> 2, and I'm unclear as to the boundary between the two, or appropriate inferences to draw from the theory when applied to smaller problems.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "7scEglE-vt5", "reviewer": "Reviewer_13Ym", "summary": "This paper analyzes theoretically the resources required by multiclass boosting to guarantee convergence. Namely, the authors propose an AdaBoost algorithm variant tailored to solve multiclass tasks. The algorithm uses the standard classification loss function, as opposed to state-of-the-art multiclass AdaBoost algorithms that use tailored loss functions. The convergence of the proposed algorithm is guaranteed if the boosting sample complexity has a logarithmic dependency on the number of classes k in the training dataset and if the number of samples used by the weak learner at each boosting iteration has a k^2 complexity. The paper also shows that the weak learner must be best in class when the number of classes is very large, making each call to the weak learner oracle very costly / challenging.", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "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": "In terms of originality, the paper proposes a novel theoretical analysis of multiclass boosting by using a multiclass variant of the AdaBoost algorithm. In contrast to state-of-the-art algorithms, the proposed method uses the standard classification loss function and does not convert the learning of the multiclass problem into multiple binary problems. \n\nIn terms of significance, the paper provides a set of interesting theoretical findings regarding the resources required by multiclass boosting to guarantee convergence especially in the case of a large number of classes. It would be good to understand how these findings could be applied (if possible) to other boosting schemes, such as gradient boosting. In other words, how general are the theoretical findings for all the multiclass boosting schemes? Also, how can these findings be used in practice. \n\nIn terms of clarity and quality, the paper could be improved as suggested in the next paragraphs:\n\n- What is the definition of an \"easy-to-learn\" base class, and what would be an example of such a class, a tree stump? Are decision trees of max_depth N > 1 an easy-to-learn base class?\n- It would be good to mention the boosting resources under study also in the abstract.\n- A very popular boosting framework nowadays is gradient boosting. A discussion would be appreciated if the authors could explain how the findings could be applied to gradient boosting. If they do not apply, would the challenges of multiclass boosting described in the paper apply to gradient boosting as well? \n- One of the main contribution of the paper is that the proposed algorithm and theoretical analysis use the standard classification loss as opposed to tailored loss functions. Could the authors explain why using a tailored loss function as proposed in [13] is a disadvantage compared to their proposed algorithm? What are the challenges with using tailored loss functions?\n- It would be good if the authors would explain the statement in lines 197-198 about the logarithmic dependence of the algorithm on k.\n- Would it be possible for the authors to design a set of experiments in which their proposed method is applied to a real dataset, where the base class is the decision tree? As base learners need to be \"easy-to-learn\", probably tree stumps could be used as a base class. Could such experiments validate the theoretical findings and show that if k is large and the sample complexity / number of calls to the weak learner oracle is not of the complexity suggested by the theoretical analysis, then the model does not converge even for a large number of iterations?\n- AdaBoost is known to be sensitive to noisy datasets. How is this taken into account by the theoretical analysis proposed in this paper?", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors do not discuss the potential negative societal impact of their work, but that looks reasonable to me. I do not see any negative impact of their proposed work.\n\nIn terms of limitations, the authors describe the cost using the standard classification loss on the lower bound of the excess error.\n", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "8"}, "extra_text": {}}, {"review_id": "2b2Dw6hEk1n", "reviewer": "Reviewer_jfEb", "summary": "The paper “Multiclass Boosting and the Cost of Weak Learning”  studies boosting in the multiclass regime, especially by focusing on the how number of classes k affects the resources required for boosting.\n\nThe contribution that I found most interesting is the demonstrated gap between the sample complexity dependence on the number of classes needed for boosting versus weak learning. (log(k) versus k^2). \n\nThe other contribution of this paper is a modified boosting algorithm for the framework above.", "questions": "", "limitations": "", "rating": 6, "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": "I think the paper's contributions are interesting and worthwhile.  They are not groundbreaking contributions to the theory of multiclass boosting, but they elucidate some important aspects.  I would recommend acceptance subject to the following comments being addressed.\n\nmain comments\n\n1. How is your Algorithm 1 distinguished from the multiclass boosting algorithm of Mukherjee and Schapire (2011)?  (As in, what does section 3 add on its own?)  Or is section 3 meant as a tool and inspiration to the tradeoff later shown?\n2. It seems to me that Theorem 7 / Corollary 8 depend on a (justified) assumption where the weak learning oracle is used as a black box.  Otherwise, one could presumably use the upper bounds of [9] to find a linear combination of weak learners without the k^2 dependence.  I think this should be pointed out to avoid confusion. (Or please correct me if I am mistaken.)\n3. Are lower bounds from Daniely et al. (2015) on multiclass learnability pertinent to your results? (You cite only their upper bounds.)\n\nminor\n\nl. 74 “which they proved to be necessary and sufficient” (who is “they”? You should state the authors’ names.)\n\nDo these results point to any general principles for designing multiclass weak learners? (c.f. Reyzin (AAAI 2014) for such a discussion for the binary case.)\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "no concerns", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper studies the problem of multiclass boosting and proves a few different results. 1) proving that the number of samples required by a 
weak learner is exponentially more than the number of samples needed by the booster; 2) proving that the weak learner's accuracy parameter must be smaller than an inverse polynomial; and 3) giving a trade-off between number of oracle calls and the
resources required of the weak learner.  This is a nice set of interesting and even surprising set of results about multiclass boosting and would add to the conference.
Decision: Accept (Poster)