A Boosting-Type Convergence Result for AdaBoost.MH with Factorized Multi-Class Classifiers

Authors: xin  zou
zhengyu  zhou
jingyuan  xu
weiwei  liu
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-12 12:59:04

Abstract: AdaBoost is a well-known algorithm in boosting. Schapire and Singer propose, an extension of AdaBoost, named AdaBoost.MH, for multi-class classification problems. Kégl shows empirically that AdaBoost.MH works better when the classical one-against-all base classifiers are replaced by factorized base classifiers containing a binary classifier and a vote (or code) vector. However, the factorization makes it much more difficult to provide a convergence result for the factorized version of AdaBoost.MH. Then, Kégl raises an open problem in COLT 2014 to look for a convergence result for the factorized AdaBoost.MH. In this work, we resolve this open problem by presenting a convergence result for AdaBoost.MH with factorized multi-class classifiers.

Main paper: 
 introduction: 
 Boosting is an approach to machine learning based on the idea of creating a highly accurate prediction rule by combining many relatively weak and inaccurate rules [19] and has inspired a lot on theoretical analysis and algorithm design in supervised learning [11, 17] . The seminal algorithm in boosting, ADABOOST [9] , requires no knowledge of the upper bound of the edge, which makes it convenient in practice.In addition to to binary ADABOOST, [9] also proposes two multi-class extensions, named AD-ABOOST.M1 and ADABOOST.M2. Then, Schapire and Singer's seminal paper [20] proposes another extension named ADABOOST.MH. The main idea of ADABOOST.MH is to use vector-valued base classifiers to build a multi-class discriminant function of K outputs when there are K classes, and then replace the weight vector in ADABOOST with a weight matrix over instances and labels.The simplest implementation of the concept in ADABOOST.MH is to use K independent one-againstall classifiers in which base classifiers are only loosely connected through the common normalization of the weight matrix. However, [15] points out that such an implement is suboptimal in most of the practical problems since it is limited to only decision stumps weak learners. To solve this problem, [15] proposes another base learner named multi-class Hamming trees, which optimizes the multi-class edge without reducing the problem to K binary classifications. The key idea in [15] is to factorize general vector-valued classifiers h into an input-independent code vector of length K, i.e., v ∈ {-1, +1} K , and label-independent scalar classifier φ. However, [15] gets in trouble when proving the convergence rate of the proposed implement of ADABOOST.MH due to the factorization step. So [14] raises an open problem in COLT 2014, looking for a convergence rate of the factorized ADABOOST.MH in [15] , with limited dependence on the sample size n.Our contributions can be concluded as follows:1. We provide a convergence result (Theorem 3.3) of factorized ADABOOST.MH, where the step T * which guarantees the training error to be 0 is of order O n 2 ln n . 2. According to the requirement of [14] , we improve the dependence on n and resolve the open problem by providing a convergence result (Theorem 3.4) where T * is of order O (K ln(nK)). This result greatly improves when n is much larger than K.More related works are deferred to Appendix B.Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?Answer: [Yes] Justification: We highly summarize what we do in the abstract. The introduction clearly introduces the concepts and issues that are related to our main results.Guidelines:• The answer NA means that the abstract and introduction do not include the claims made in the paper. • The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers. • The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings. • It is fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper. 
preliminaries: 
 We consider a multi-class classification problem where the input space is X = R d and L = [K] is the label space, where K is the number of classes and [K] := {1, . . . , K}. Assume we attain the training data D L = {(x 1 , ℓ(x 1 )), . . . , (x n , ℓ(x n ))}, where ℓ(x i ) ∈ L is the label of x i . Since we want to use vector-valued classifiers, it is convenient to use the one-hot labels y i ∈ {-1, +1} K for x i , where y i (ℓ(x i )) = 1 and all the other elements are -1. We use the new dataset D = {(x 1 , y 1 ), . . . , (x n , y n )} as the input data of ADABOOST.MH and define an observation matrix X := (x 1 , . . . , x n ) T ∈ R n×d , a label matrix Y := (y 1 , . . . , y n ) T ∈ {-1, +1} n×K . We call y and ℓ the label and the index of x respectively, as in [14] .[14] considers a special case of ADABOOST.MH, where each weak classifier has a specialized structure. ADABOOST.MH returns a vector-valued discriminant function f : X → R K with a combined predictor F f : X → {-1, +1} K where F f (x) l = sign(f (x) l ) for l = 1, . . . , K. Here and in this paper, we define sign(x) = +1x ≥ 0 -1x < 0 .The goal of the ADABOOST.MH algorithm [20] is to return f such that the Hamming loss ofEQUATIONis as small as possible, where I(•) is the indicator function and W = [w i,l ] ∈ [0, 1] n×K is a distribution over the data points and the labels. W can be chosen as any distribution over[n] × [K]and is different in different papers. In [20] , the authors setw i,l = 1 nK for any i ∈ [n], l ∈ [K].Here, we follow [14] and setEQUATIONWe define the weighted multi-class exponential margin-based errorEQUATIONas a surrogate for R H (F f , W). Since I{F f (x i ) l ̸ = y i,l } = I{f (x i ) l •y i,l ≤ 0} ≤ exp (-f (x i ) l • y i,l ), we can get that R H (F f , W) ≤ R EXP (f , W).It's well-known that ADABOOST directly minimizes the exponential loss [19, Chapter 7] , then, we can apply the ADABOOST algorithm to the extended binary training set ∪ n i=1 {(x i , y i,l )} K l=1 , yielding the ADABOOST.MH algorithm, which directly minimizes R EXP (f , W) and output the final discriminant functionEQUATIONby a similar calculation in [19, Proof of Theorem 3.1], we can obtain that:R EXP (f (T ) , W) = T t=1 Z(h (t) , W (t) ).According to the above discussion, we know that to minimize R EXP (f (T ) , W), the base learner needs to find a h (t) that minimizes Z(h (t) , W (t) ) at the t-th iteration. In the following, we introduce two choices of h in [20] and [15] , the corresponding convergence rate of R EXP (f (T ) , W), and problems when trying to get a convergence rate of R EXP (f (T ) , W) for factorized ADABOOST.MH.[20] considers using h with the form h(x) = αφ(x), where α ∈ R and φ : R d → {-1, +1} K can be seen as the vector consists of K binary classifiers φ 1 , . . . , φ K .We consider the t-th iteration, and to simplify the notations, we omit the superscript t and use W, h, φ, α to represent W (t) , h (t) , φ (t) , α (t) respectively. According to [20] , if we defineEQUATIONas the edge, then we haveZ(h, W) = n i=1 K l=1 w i,l exp (-h(x i ) l • y i,l ) = n i=1 K l=1 w i,l exp (-αφ(x i ) l • y i,l ) = i,l:φ(xi) l •y i,l =1 w i,l • e -α + i,l:φ(xi) l •y i,l =-1 w i,l • e α .Since i,l:φ(xi) l •y i,l =1 w i,l + i,l:φ(xi) l •y i,l =-1 w i,l = 1 and i,l:φ(xi) l •y i,l =1 w i,li,l:φ(xi) l •y i,l =-1 w i,l = r, we can get thati,l:φ(xi) l •y i,l =1 w i,l = 1 + r 2 , i,l:φ(xi) l •y i,l =-1 w i,l = 1 -r 2 .So we have:Z(h, W) = 1 + r 2 • e -α + 1 -r 2 • e α .Fix φ first, minimizing Z(h, W) over α yields that:α = 1 2 ln 1 + r 1 -r .Z(h, W) = 1 -r 2 .Then choose φ to minimize √ 1 -r 2 , i.e., maximize |r|. If we have r (t) ≥ δ > 0 for all t, then we can get:R EXP (f (T ) , W) = T t=1 1 -r (t) 2 ≤ 1 -δ 2 T ≤ exp - δ 2 2 T ,which means that the weighted exponential error goes to error exponentially fast. Let exp -δ 2 2 T < 1 nK , we know that the weighted Hamming error becomes zero afterT * = 2 ln(nK) δ 2 + 1iterations. The condition r (t) ≥ δ > 0 for all t is satisfied when the empirically weak learning condition on the classifier φ holds for the extended binary training set ∪ n i=1 {(x i , y i,l )} K l=1 .Definition 2.1 (empirically δ-weak learning condition). For a given binary dataset {(x 1 , y 1 ), . . . , (x m , y m )} where y i ∈ {-1, +1}, we say that the empirically δ-weak learning condition holds for some δ > 0 if for any distribution w ∈ ∆ m-1 over [m], we can always find a binary classifier φ : X → {-1, +1} such that:γ = m i=1 w i • y i • φ(x i ) ≥ δ,where∆ m-1 = λ ∈ R m λ i ≥ 0 ∀i ∈ [m], m i=1 λ i = 1is the (m -1)-dimensional probability simplex.The original ADABOOST.MH [20] reduces the multi-class problem into K binary one-against-all classifications. [15] avoids such a reduction by factorizing the vector-valued classifier h into an input-independent vector of length K and a label-independent scalar classifier. Formally, [15] setsh(x) = αvφ(x),where α ∈ R + is a positive real-valued base coefficient, v ∈ {-1, +1} K is an input-independent vote (or code) vector of length K, and φ : R d → {-1, +1} is a label-independent binary classifier.For more details about the factorized ADABOOST.MH, please refer to Algorithm 1 in Appendix A.We consider the t-th iteration, and to simplify the notations, we omit the superscript t and use W, h, φ, α, v to represent W (t) , h (t) , φ (t) , α (t) , v (t) respectively. [15] shows thatZ(h, W) = e α + e -α 2 - e α -e -α 2 • K l=1 v l (µ l+ -µ l-) ,whereµ l-= n i=1 w i,l I{φ(x i ) ̸ = y i,l }is the weighted per-class error rate andµ l+ = n i=1 w i,l I{φ(x i ) = y i,l }is the weighted per-class correct classification rate for each class l = 1, . . . , K. Similar to Equation (5), we define the multi-class edge of the classifier h asEQUATIONwhereγ l = v l (µ l+ -µ l-) = n i=1 w i,l • v l • φ(x i ) • y i,lis the classwise edge of h. By a similar calculation as in Section 2.1, we know that Z(h, W) is minimized when we setα = 1 2 ln 1 + γ 1 -γ , which gives Z(h, W) = 1 -γ 2 .So in order to minimize Z(h, W), we need to choose v and φ to maximize |γ|. From the equationγ(v, φ, W) = K l=1 v l (µ l+ -µ l-), we know that if γ(v, φ, W) ≤ 0, then γ(-v, φ, W) = -γ(v, φ, W) ≥ 0.So the problem reduces to finding v, φ that maximize γ. From Equation (6) we know that for fixed φ, γ is maximized when we choose v asEQUATIONfor all classes l = 1, . . . , K.Similar to Section 2.1, if there exists a number δ > 0 such that γ v (t) , φ (t) , W (t) ≥ δ for all t = 1, . . . , T , then we can get an upper bound for R EXP (f (T ) , W):R EXP (f (T ) , W) = T t=1 1 -γ v (t) , φ (t) , W (t) 2 ≤ 1 -δ 2 T ≤ exp - δ 2 2 T ,which means that the weighted exponential error goes to error exponentially fast. Let exp -δ 2 2 T < 1 2n(K-1) , we know that the weighted Hamming error becomes zero afterT * = 2 ln(2n(K -1)) δ 2 + 1iterations. To get the exponential convergence rate, the question now is whether there exists a number δ > 0 such that γ v (t) , φ (t) , W (t) ≥ δ for all t = 1, . . . , T .For the condition in the unfactorized choice, if the empirically δ ′ -weak learning condition holds, then for a fixed weight matrix W, letI = {l ∈ [K] n i=1 w i,l > 0}, then for all l ∈ I, there exists a binary classifier φ l such thatr l = n i=1 w i,l n i=1 w i,l φ l (x i )y i,l ≥ δ ′ ,then we can find a φ such that φ l = φ l for l ∈ I so thatr = n i=1 K l=1 w i,l • φ l (x i ) • y i,l = l∈I n i=1 w i,l • φ l (x i ) • y i,l ≥ l∈I n i=1 w i,l • δ ′ = δ ′ .So the empirically δ ′ -weak learning condition is sufficient for an exponential convergence rate for the ADABOOST.MH algorithm in [20] .For the factorized choice proposed in [15] , we can not use the above argument since h is factorized and we need to find a binary classifier φ for all l = 1, . . . , K, while for the unfactorized choice, we can find K binary classifiers φ 1 , . . . , φ K separately for each class. In [14] , the author tries to solve this problem by constructing pseudo-weights and pseudo-labels and then applying the empirically δ ′ -weak learning condition to the constructed dataset{(x 1 , y ′ 1 ), . . . , (x n , y ′ n )}. [14] rewrites γ as γ = n i=1 φ(x i ) K l=1 w i,l • v l • y i,l = n i=1 φ(x i ) K l=1 w i,l [I{v l • y i,l = +1} -I{v l • y i,l = -1}] = n i=1 φ(x i )(w + i -w - i ) = n i=1 φ(x i )sign(w + i -w - i )|w + i -w - i |,where we definew + i = K l=1 w i,l I{v l • y i,l = +1}, w - i = K l=1 w i,l I{v l • y i,l = -1}for simplicity. Then we define y ′ i = sign(w + i -w - i ) as the i-th pseudo-label andw ′ i = |w + i -w - i | as the i-th pseudo-weight, then γ = n i=1 w ′ i • y ′ i • φ(x i ).However, sincen i=1 w ′ i = n i=1 |w + i -w - i | ≤ n i=1 (w + i + w - i ) = 1, w ′ = (w ′ 1 , . . . , w ′ n ) is not necessarily a distribution on [n].To make use of the empirically δ ′ -weak learning condition, we definew ′ Σ := n i=1 w ′ i ≤ 1.If we can get a lower bound ω > 0 such that w ′ Σ ≥ ω, then we have:γ = n i=1 w ′ i • y ′ i • φ(x i ) = w ′ Σ n i=1 w ′ i w ′ Σ • y ′ i • φ(x i ) ≥ w ′ Σ • δ ′ ≥ ω • δ ′ ,where the first inequality is from the empirically δ ′ -weak learning condition. Since the number of examples n may be very large, we wish the lower bound ω to be independent of n, but it can depend on the number of classes K.Then [14] raises an open problem:Whether there exists a setup (X, W, Y, and function class) in which all of the 2 K different vote vectors v ∈ {-1, +1} K lead to arbitrarily small (or zero) w ′ Σ , or we can find a constant (independent of n) lower bound ω such that with at least one vote vector and classifier φ, w ′ Σ ≥ ω holds?We resolve this open problem by showing that:There exists a constant ω = 1 √ 2K such that: for any X, W, Y and function class, there always exists a vote vector v s.t. w ′ Σ ≥ ω holds. With this result, if the empirically δ ′ -weak learning condition holds, then for any X, W, Y, there always exists a vote vector v and a binary classifierφ such that γ = n i=1 φ(x i ) K l=1 w i,l • v l • y i,l ≥ δ ′ √ 2K . So if we run the AD- ABOOST.MH algorithm with factorized h, R EXP (f (T ) , W) becomes zero after at most T * = 4K ln(2n(K-1)) (δ ′ ) 2 + 1 iterations.Question: Does the paper discuss the limitations of the work performed by the authors?Answer: [NA] Guidelines:• The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper. • The authors are encouraged to create a separate "Limitations" section in their paper.• The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be. • The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with a few runs. In general, empirical results often depend on implicit assumptions, which should be articulated. • The authors should reflect on the factors that influence the performance of the approach.For example, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon. • The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size. • If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness. • While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations. 
our solution: 
 In this section, we provide formal theorems for our above answer to the open problem and further discussions.Because the training set size n may be very large, [15] requires the lower bound to be independent of the training set size n (but can be dependent on the number of classes K), which is much more difficult than finding a lower bound depends on n. To consider this problem more holistically, we provide two lower bounds, one depends on n and another depends on K.To solve this problem, we first formulate the problem of "finding a constant ω such that for any training set and weight matrix, there exists a code vector v such that w ′ Σ ≥ ω (w ′ Σ depends on the training set, weight matrix, and the code vector)" into "finding the lower bound of a constrained minimax problem". We then provide a n-dependent lower bound by the fact ∥x∥ 1 ≥ ∥x∥ ∞ and the fact that the maximum is not smaller than the average, where ∥ • ∥ p is the ℓ p -norm of a vector. For the n-independent lower bound, we choose to lower bound the expected value of w ′ Σ when the code vector v is drawn from some distribution D on {-1, +1} K . To eliminate the trouble caused by the labels, we choose v to be a Rademacher random vector with independent elements, i.e., v = (ε 1 , . . . , ε K ) whereP [ε i = 1] = P [ε i = -1] = 12 for i = 1, . . . , K. We then provide the lower bound with the help of Khintchine inequality [10] .We defineW := W ∈ R n×K W i,l ≥ 0 for all i ∈ [n], l ∈ [K]; n i=1 K l=1 W i,l = 1 as the set of all possible W. Let e(•) : [K] → {-1, +1} K be e(l) i = +1 i = l -1 i ̸ = l ,we the define Y := (e(l 1 ), . . . , e(l n )) T ∈ {-1, +1} n×K |l 1 , . . . , l n ∈ L = [K] as the set of all possible Y, and define V = {-1, +1} K as the set of all possible v. We then have:w ′ Σ (W, Y, v) = n i=1 |w + i -w - i | = n i=1 K l=1 w i,l {I[v l y i,l = +1] -I[v l y i,l = -1]} = n i=1 K l=1 w i,l • v l • y i,l = n i=1 (W ⊙ Y) T i , v = ∥(W ⊙ Y) • v∥ 1 ,where ⊙ is the Schur product and ∥x∥ 1 = n i=1 |x i | is the ℓ 1 -norm of the vector x. The following two facts translate the problem that we are concerned with into a minimax problem. Fact 3.1. The following two statements are equivalent:(1) There exists a setup (X, W, Y) in which all of the 2 K different vote vectors v ∈ V lead to arbitrarily small (or zero)w ′ Σ . (2) min W∈W,Y∈Y max v∈V ∥(W ⊙ Y)• v∥ 1 is arbitrarily small (or zero).Fact 3.2. The following two statements are equivalent:(1) We can find a constant (independent of n) lower bound ω such that for any setup (X, W, Y), there exists at least one vote vector and classifier φ such that w ′ Σ ≥ ω holds. (2) we can find a constant (independent of n) lower bound ω such that minW∈W,Y∈Y max v∈V ∥(W ⊙ Y) • v∥ 1 ≥ ω.So, to find the lower bound ω, we need to prove that minW∈W,Y∈Y max v∈V ∥(W ⊙ Y) • v∥ 1 ≥ ω. Let'sbegin with a simple n-dependent lower bound. Theorem 3.3 (An n-dependent lower bound). minW∈W,Y∈Y max v∈V ∥(W ⊙ Y) • v∥ 1 ≥ 1 n .Proof of Theorem 3.3.min W∈W,Y∈Y max v∈V ∥(W ⊙ Y) • v∥ 1 a ≥ min W∈W,Y∈Y max v∈V ∥(W ⊙ Y) • v∥ ∞ = min W∈W,Y∈Y max v∈V,i∈[n] K l=1 w i,l • y i,l • v l b ≥ min W∈W max i∈[n] K l=1 w i,l c = 1 n ,where a is from the fact that ∥x∥ 1 ≥ ∥x∥ ∞ where ∥x∥ ∞ = max1≤i≤n |x i | is the ℓ ∞ -norm of x; b comes from choosing v l = y i,l for l = 1, . . . , K when i is fixed; c is from the fact that max i∈[n] K l=1 w i,l ≥ 1 n n i=1 K l=1 w i,l = 1n and the equation can be attained.Remark 1. The lower bound in Theorem 3.3 depends on n, and if we use 1 n as the lower bound of w ′ Σ , then we need at most T * = 2n 2 ln(2n(K-1))(δ ′ ) 2+ 1 iterations to make the exponential error become zero, which quadratically increases as n. When the training set is large, T * becomes very large, which is one of the reasons that [14] wants to get a lower bound independent of n.Next, we introduce how we solve the open problem to get a lower bound independent of n. Theorem 3.4 (An n-independent lower bound). min 4 shows that there is a constant ω = 1 √ 2K such that for any setup W, Y, there always exists a code vector v such that w ′ Σ ≥ ω. This solves the open problem proposed by [14] . So we need at most T * = 4K ln(2n(K-1)) W∈W,Y∈Y max v∈V ∥(W ⊙ Y) • v∥ 1 ≥ 1 √ 2K . Remark 2. Theorem 3.(δ ′ ) 2A p N n=1 |x n | 2 1/2 ≤ E ε1,...,ε N N n=1 ε n x n 1/p ≤ B p N n=1 |x n | 2 1/2for some constants A p , B p > 0 depending only on p, whereA p =    2 1/2-1/p 0 < p ≤ p 0 2 1/2 (Γ((p + 1)/2)/ √ π) 1/p p 0 < p < 2 1 2 ≤ p < ∞ and B p = 1 0 < p ≤ 2 2 1/2 (Γ((p + 1)/2)/ √ π) 1/p 2 < p < ∞ ,where p 0 ≈ 1.847 and Γ is the Gamma function.Proof of Theorem 3.4. The basic idea of our proof is to consider the average performance of different code vectors for fixed choices of W, Y, i.e., use the fact that the maximum is not less than the average, which gives: minW∈W,Y∈Y max v∈V ∥(W ⊙ Y) • v∥ 1 ≥ min W∈W,Y∈Y E v∼D ∥(W ⊙ Y) • v∥ 1 = min W∈W,Y∈Y E v∼D n i=1 K l=1 w i,l • v l • y i,lfor any distribution D on V.We take v 1 , . . . , v K be independent Rademacher random variables and then get:min W∈W,Y∈Y E v∼D n i=1 K l=1 w i,l • v l • y i,l = min W∈W,Y∈Y E ε1,...,ε K n i=1 K l=1 w i,l • ε l • y i,l a ≥ A 1 min W∈W n i=1 K l=1 w 2 i,l 1/2 b = K 2 min W∈W n i=1 1 K K l=1 w 2 i,l 1/2 c ≥ K 2 min W∈W 1 K n i=1 K l=1 w i,l = 1 √ 2K ,where a applies Lemma 3.5 with p = 1 and the fact that y 2 i,l = 1 for all i, l; b puts in the value of A 1 ; c uses the concavity of √ • and Jensen's inequality.With the lower bound of w ′ Σ , we can now provide a lower bound of the edge γ and convergence guarantee for the version of ADABOOST.MH proposed by [15] conditioned on the empirically δ ′ -weak learning condition. Corollary 3.6 (Lower bound for γ). If the empirically δ ′ -weak learning condition holds, then for any X, W ∈ W, Y ∈ Y, there always exists a binary classifier φ * and code vector v max such thatγ(v max , φ * , W) ≥ δ ′ √ 2K .If we run ADABOOST.MH with factorized h, then we haveR EXP (f (T ) , W) ≤ exp - δ ′ 4K Tand we need at mostT * = 4K ln(2n(K -1)) (δ ′ ) 2 + 1to make the exponential error R EXP (f (T ) , W) become zero.Proof of Corollary 3.6. For any W, X, Y, letv max = arg max v∈V ∥(W ⊙ Y) • v∥ 1 . Let w ′ i , y ′ i , w ′Σ be defined as before, where we replace v there by v max . By Theorem 3.4,w ′ Σ ≥ 1 √ 2K > 0.By the empirically δ ′ -weak learning condition, there exists a binary classifier φ * such thatn i=1 w ′ i w ′ Σ • y ′ i • φ * (x i ) ≥ δ ′ , which means that γ(v max , φ * , W) ≥ w ′ Σ δ ′ ≥ δ ′ √ 2K .For fixed W, X, Y, let v * (φ) be the code vector depending on φ that is defined in Equation (7) .Since the choice v * (φ) maximizes γ when φ is fixed, we have that:γ(v * (φ * ), φ * , W) ≥ γ(v max , φ * , W) ≥ δ ′ √ 2K .Combining the arguments in Sections 2.1 and 2.2 shows R EXP (f (T ) , W) ≤ exp -δ ′ 4K T and that when we run ADABOOST.MH with factorized h, which returns φ * , v * (φ * ) at each iteration,R EXP (f (T ) , W) < 1 2n(K -1) , i.e. R H (F f (T ) , W) = 0after at mostT * = 4K ln(2n(K -1)) (δ ′ ) 2 + 1iterations.The previous discussions are based on fixing the training set size n and the number of classes K.Here we consider the case when they can tend to infinity. We think the reason [14] looks for a lower bound of w ′ Σ that is independent of n is that the author thinks the number of examples n can be arbitrarily large in some cases, which may make the lower bound of w ′ Σ arbitrarily small. Combine our two lower bounds in Theorems 3.3 and 3.4, for any X, W, Y, we can always find a v ∈ {-1, +1} K such that:w ′ Σ ≥ max 1 n , 1 √ 2K ,so the lower bound can become arbitrarily small only when n and K tend to infinity together.Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?Answer: [Yes]Answer: [NA] Justification: Our paper is purely theoretical, with no experiments. Guidelines:• The answer NA means that paper does not include experiments requiring code.• Please see the NeurIPS code and data submission guidelines (https://nips.cc/ public/guides/CodeSubmissionPolicy) for more details. • While we encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark). Guidelines:• The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.• If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction). 
discussion: 
 In this section, we discuss the importance of solving this problem.In statistical learning theory, algorithms can be divided into proper and improper learning algorithms. For proper learning, the most famous algorithms are ERM [22] and its variants [26, 16, 24] . For improper learning, boosting algorithms are usually used to construct improper algorithms [2, 3, 17, 23] . Furthermore, the convergence rate of the boosting algorithm usually affects the sample complexity of the constructed algorithm, i.e., the sample complexity of the constructed algorithms usually depends on the value T * where the training error becomes zero. So boosting algorithms are basic but important tools in statistical learning theory.In binary classification, ADABOOST [9] is one of the most famous and influential algorithms among all the binary boosting algorithms. Since the proposal of ADABOOST, many works have tried to extend the boosting framework to multi-class classification problems. Most multi-class boosting algorithms have been restricted to reducing the multi-class classification problem to multiple two-class problems, among which the most famous and influential one is ADABOOST.MH [20] . Moreover, ADABOOST.MH has inspired the proposal of many other multi-class boosting algorithms. For example, inspired by the characteristics of ADABOOST.MH that reduces the multi-class classification problem to multiple two-class problems, [13] chooses another line of thought to develop an algorithm that directly extends the ADABOOST.MH algorithm to the multi-class case without reducing it to multiple two-class problems; [1] demonstrates how to improve the efficiency and effectiveness of ADABOOST.MH and proposes the algorithm LDA-ADABOOST.MH; [18] proposes an efficient multi-class fault diagnosis approach based on the ADABOOST.MH algorithm; [7] proposes a method for ranking based on ADABOOST.MH. There are also many other works based on ADABOOST.MH [21, 12, 8] . Furthermore, many works (for example, [13, 8, 25, 27] ) use ADABOOST.MH as the baseline, which further shows the importance of ADABOOST.MH. For example, the only baseline used in [13] is ADABOOST.MH. In summary, ADABOOST.MH serves as a link between binary classification boosting algorithms and multi-class classication boosting algorithms, the cornerstone of multi-class boosting, and has a big influence on the multi-class boosting field. Our work is important because it shows that Kégl's work [15] , which solves the computational problem (at the level of the strong learner at least) of ADABOOST.MH, does indeed work in theory and works essentially as fast as binary ADABOOST. 
conclusion: 
 In this paper, we resolve the open problem raised by [14] by presenting a n-independent lower bound for w ′ Σ . In addition to that, we also provide a n-dependent lower bound for w ′ Σ to show that w ′ Σ may be arbitrarily small only when n and K tend to infinity together. Based on the lower bounds for w ′ Σ and the empirically δ ′ -weak learning condition, we provide an upper bound for the weighted exponential error and a number T * where the weighted exponential error becomes zero after at most T * iterations. 
broader impacts: 
 Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?Answer: [NA] Justification: Our paper is purely theoretical, and has no societal impact.Guidelines:• The answer NA means that there is no societal impact of the work performed.• If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact. • Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.• The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster. • The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology. • If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?Answer: [NA] Justification: Our paper is purely theoretical, with no experiments, so it clearly poses no such risks.Guidelines:• The answer NA means that the paper poses no such risks.• Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters. • Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images. • We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make a best faith effort.12. Licenses for existing assets Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?Answer: [NA] Justification: Our paper is purely theoretical, with no experiments, which needs no assets.Guidelines:• The answer NA means that the paper does not use existing assets.• The authors should cite the original paper that produced the code package or dataset.• The authors should state which version of the asset is used and, if possible, include a URL. • The name of the license (e.g., CC-BY 4.0) should be included for each asset.• For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided. • If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset. • For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.• If this information is not available online, the authors are encouraged to reach out to the asset's creators. • We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution. • For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review. 
 
 Appendix: In this section, we adapt the pseudocode of the factorized ADABOOST.MH from [14] . X is the n × d observation matrix, Y is the n × d label matrix, W is the user-defined weight matrix used in the definition of the weighted Hamming error (1) . Let BASE(•, •, •) be the base learner algorithm, and T be the number of iterations. Let α (t) be the base coefficient v (t) be the vote vector, φ (t) (•) be the scalar base (weak) classifier, h (t) (•) be the vector-based classifier, and f (t) (•) be the final (strong) discriminant function.Algorithm 1: The factorized ADABOOST.MH Input :X, Y, W, BASE(•, •, •), T ; 1 W (1) = 1 n W; 2 for t ← 1 to T do 3 α (t) , v (t) , ϕ (t) ← BASE(X, Y, W (t) ); 4 h (t) (•) ← α (t) v (t) φ (t) (•); 5 for i ← 1 to n do 6 for l ← 1 to K do 7 w (t+1) i,l ← w (t) i,l • exp -h (t) l (xi)y i,l n i ′ =1 K l ′ =1 w (t) i ′ ,l ′ exp -h (t) l ′ (x i ′ )y i ′ ,l ′ ; 8 end 9 end 10 end Output :f (T ) (•) = T t=1 h (t) (•);In addition to ADABOOST.M1, ADABOOST.M2, ADABOOST.MH, and factorized ADABOOST.MH, there are also some works on multi-class boosting.To circumvent the hardness result for a large class of natural boosting, [5] utilizes the technique of list learning and proposes an efficient improper multi-class boosting algorithm with sample and oracle complexity bounds that are entirely independent of the number of classes.[6] studies the resources required for boosting, especially how they depend on the number of classes K. [6] presents results on the sample complexity, oracle complexity, and finds a trade-off between number of oracle calls and the resources required of the weak learner.[4] proposes an efficient multi-class boosting algorithm with the help of list learning, the success of the proposed algorithm is guaranteed by the relaxed γ-BRG condition.In this paper, we solve the open problem proposed in [14] and provide a bound for the oracle complexity of the factorized ADABOOST.MH algorithm. The algorithm that we consider is different from those in [5, 6, 4] , and the conditions are also different. We find a missing convergence result for factorized ADABOOST.MH, so we think our work is a complementary of the related works [5, 6, 4] .NeurIPS Paper Checklist 


Decision: When it comes to bringing boosting to multiclass problems, the easiest-to-go path is usually indeed by a reduction to as many binary classification problems as required. Among others, one downside of this approach is that it is computationally demanding: instead of $T$ weak classifiers, one has to train $K T$ of them.

All but one reviewers concur with the assessment that what the paper proposes is an important result. I have read the paper and agree to an extent. It is important because it shows that Kegl's approach, which solves the computational problem (at the level of the strong learner at least), does indeed work in theory, and works essentially as fast as binary AdaBoost. The proof is simple and elegant, the sort of characteristics that have been observed elsewhere in famous boosting papers. Simplicity works in favor of the paper. I also like the dependency in L245: it makes sense that in *some* cases, the lowerbound does have to depend on $n$ (if the number of classes is very large).

The only reason why I do not rejoin my fellow reviewers on their commendations is because the proof of Theorem 3.4 is non-constructive. This could partially explain why the authors have been reluctant to provide experiments. A constructive proof with a simple, low complexity algorithm would have sealed the problem -- not just the open problem, but "the" multiclass boosting problem itself. I can see at least two potential algorithms following either from the presentation of the problem ("LP-style") or the proof technique (randomized) but each has downside. If there is something that boosting has taught, it is the value of simplicity and originality so there perhaps exists a simple original trick that would do the job. It would be good for the authors to elaborate on this (no additional result, just a discussion), as well as some of of the fixes suggested by reviewers.

I also do not consider that experiments would have been necessary for such a paper to be accepted. In conclusion, it is a fine paper which deserves to be published.

In the camera-ready version, I *strongly* encourage the authors to do some good polish of their paper, in particular number some important (in)equalities, polish the text to mix the story-telling style adopted with a more conventional approach. In particular, with the +1 camera ready page, add a section on why this problem is important (state of the art after introduction on both the technical and practical side of the problem, discussion at the end with references). Consider it as a necessary step to get a polished camera-ready that would also include readers with the same expectation as g6ZT. This will only boost further the paper's reading basis.

Reviews: review: paper_summary: paper_summary: Balázs presented a factorized version of ADABOOST.MH and empirically show that this extension achieves promising results. Balázs further raises the convergence property of factorized ADABOOST.MH as an open problem. This submission addresses this open problem and presents an elegant proof.
strength_weakness: strength_weakness: I did not find the significant weakness about this paper. But I still have some questions. I hope the author can address them.
1, Why there is the absolute value in the equations between lines 217 -218?
2, In Corollary 3.5, why the exponential error can be zero? Is this an asymptotic result or non- asymptotic result?
3, What are the derivations between lines 232 and 233? Can you provide more details?
4, Why the first equation below line 219 hold? Can you explain this?
questions: questions: See above.
limitations: limitations: The authors answers NA in the Checklist.
paper_summary: paper_summary: This paper resolves an open problem pointed out by [7]. The open problem involves providing a lower bound, which is independent of $n$, for the coefficient $w'_{\Sigma}$ of the weighted multi-class exponential margin-based error in the factorized version of ADABOOST.MH. This result demonstrates that if the $\delta'$-weak learning condition is satisfied, the aforementioned error can be reduced to 0 by adding weak learners.
The key points of the proof are as follows:

* Reformulating the proposition to be proved as a lower bound evaluation of a minimax problem.
* Treating the code $v$ as a Rademacher random variable, bounding the maximum value from below by the expectation, and then applying Khintchine inequality.
strength_weakness: strength_weakness: It seems the paper does not sufficiently explain the significance of resolving the open problem pointed out by [7].
questions: questions: * Is it possible to confirm the $\delta'$-weak learning condition is satisfied for a real-world dataset?
* If so, can we confirm how quickly the weighted multi-class exponential margin-based error decreases by numerical experiments? (Can we verify how tight $T^*$ is in practice by experiments?)
limitations: limitations: One limitation of this study appears to be the $\delta'$-weak learning condition. It would have been beneficial if the paper had provided examples or explanations to illustrate how strong this condition is for real-world datasets.
paper_summary: paper_summary: The paper solves a COLT 2014 open problem. The investigated problem is about presenting a convergence rate of the factorized AdaBoost.MH algorithm, which is based on AdaBoost.MH and aims to boost weak classifiers to a strong classifier in the multiclass setting. The paper shows two lower bounds (one depends on the sample size $n$ and another depends on the class number $K$) for the important term $\omega_\Sigma$, which leads to two convergence rates for the factorized AdaBoost.MH algorithm.
strength_weakness: strength_weakness: Firstly, the proof is a little easy compared with the solution of other open problems. However, it may not be seem as a weakness since complicated proofs are not neccessarily better.

Secondly, I think it would be better to provide some high level intuitions about idea to solve the open problem.
questions: questions: Please refer to the weaknesses part.
limitations: limitations: No. The theoretical results are only limited to the factorized AdaBoost.MH algorithm.
paper_summary: paper_summary: The paper addresses an open question posed by Kegl, 2014 regarding the convergence properties of AdaBoost.MH, a boosting algorithm designed for multi-class classification problems. Specifically, Kegl, 2014 noted that it is challenging to prove the convergence of this algorithm due to the weighted sum of binary classifications being less than one, thereby requiring a uniform lower bound on the weights. The authors of the current paper provide a solution to this open problem by establishing two convergence results: one dependent on the number of instances (n) and another independent of n, which is based on the number of classes (K).
strength_weakness: strength_weakness: 1.While the authors successfully address an open question in the field, I find it challenging to discern the significance of their findings beyond mere academic curiosity. As a consequence, it is unclear to me how this result contributes meaningfully to the broader machine learning community. To strengthen the case for this paper, I believe it would be beneficial for the authors to explicitly highlight the potential practical implications or applications of their convergence results, thus clarifying their relevance and value to the field.
2. Building upon my previous observation, I would like to emphasize the importance of empirical validation. While the theoretical convergence results are certainly valuable, their practical significance is amplified by experimental evidence demonstrating the correctness and effectiveness of these findings. To further strengthen the paper, I suggest that the authors include some concrete experimental results or simulations that illustrate the applicability of their proved bounds in real-world scenarios.
3. I found the writing style in the paper to be somewhat challenging to follow. The use of symbols like w'_{\Sigma} in the early sections can make it difficult for readers to quickly grasp the main ideas. Additionally, I noticed that Section 2.2 primarily recapitulates the Kegl, 2014 paper without adding significant value. Instead, I would suggest that the authors condense this information into a concise summary, allowing them to focus on presenting their own original contributions. By streamlining the writing and incorporating a clear summary of relevant background material, the authors can improve the overall readability and flow of the manuscript.
questions: questions: 1. I see that the result of Remark 2 still has ln(2n(K-1)) in the convergence result of T^{*}. It is definitely much better than the result of  Remark 1, but I am curious regarding why the authors call this particular result independent of n.
limitations: limitations: N/A
paper_summary: paper_summary: This paper studies the convergence rate of a variant of the boosting algorithm AdaBoost.MH, which is named factorized AdaBoost.MH. Factorized AdaBoost.MH replaces the one-against-all base classifier by the factorized base classifier which consists of a binary and a vote vector. This paper solves an open problem proposed in COLT 2014 and provide a convergence rate for factorized AdaBoost.MH.
strength_weakness: strength_weakness: - A minor issue: part of the presentations are similar to that in [1].


[1] Balázs Kégl. Open problem: A (missing) boosting-type convergence result for adaboost.mh with factorized multi-class classifiers. In Maria-Florina Balcan, Vitaly Feldman, and Csaba Szepesvári, editors, COLT, volume 35, pages 1268–1275, 2014.
questions: questions: - In equation (5) of [1], the vector $\mathbf{v}$ is not assumed to belong to $\\{ -1,+1 \\}^K$, while this paper makes such an assumption. Is the setting in your paper completely the same as that in [1]?

[1] Balázs Kégl. Open problem: A (missing) boosting-type convergence result for adaboost.mh with factorized multi-class classifiers. In Maria-Florina Balcan, Vitaly Feldman, and Csaba Szepesvári, editors, COLT, volume 35, pages 1268–1275, 2014.
limitations: limitations: No.

Comments: title: Response to author rebuttal
Keep the scores
Request for feedbacks
response
comment: I thank the authors for going through the review and responding to my questions. As pointed out, I am clearly the outlier in this reviewer group. I see that reviewer iRY2 also initially shared my main concern and the conversation there was very helpful. However, I feel that this significance needs to be properly mentioned in the manuscript itself which has not been done in its current format. The explanation regarding experimental validation can be defended, but some experiments should definitely elevate the quality of this paper in my opinion.

After going through all the reviews and discussions, I have decided to improve my scores slightly.
Thank you for improving the score, we are glad that we have addressed your concerns.
Thank you very much for your detailed explanation.
My concerns have been addressed.
I would like to improve my score.
Thank you for your reply. We are glad you like our paper.
I have read the response letter.
Dear Reviewer,

Thanks for reviewing our submission.

We have turned in our responses during the rebuttal period. Since it has been a few days after the beginning of the discussion period, we sincerely request for some feedback about whether we have solved your problems.
Thank you for your reminder, we are glad to add more discussions on the importance of AdaBoost.MH in our revision.

In binary classification, AdaBoost [1] is one of the most famous and influential algorithms among all the binary boosting algorithms. The paper [1], which proposes AdaBoost, has more than 22000 citations. Since the proposal of AdaBoost, there are many works trying to extend the boosting framework to multi-class classification problems. Most multi-class boosting algorithms have been restricted to reducing the multi-class classification problem to multiple two-class problems, among which the most famous and influential one is AdaBoost.MH [2]. The paper [2], which proposes AdaBoost.MH, has more than 4900 citations. Moreover, AdaBoost.MH has inspired the proposal of many other multi-class boosting algorithms. For example, inspired by the characteristics of AdaBoost.MH that reduces the multi-class classification problem to multiple two-class problems, [3] chooses another line of thought to develop an algorithm that directly extends the AdaBoost algorithm to the multi-class case without reducing it to multiple two-class problems; [4] demonstrates how to improve the efficiency and effectiveness of AdaBoost.MH and proposes the algorithm LDA-AdaBoost.MH; [5] proposes an efficient multi-calss fault diagnosis approach based on the AdaBoost.MH algorithm; [6] proposes a method for ranking based on AdaBoost.MH. There are also many other works based on AdaBoost.MH [7-9]. Furthermore, to the best of our knowledge, many works (for example, [3, 9-11]) use AdaBoost.MH as the baseline, which further shows the importance of AdaBoost.MH. For example, the only baseline used in [3] is AdaBoost.MH. In summary, AdaBoost.MH serves as a link between binary classification boosting algorithms and multi-class classification boosting algorithms, the cornerstone of multi-class boosting, and has a big influence on the multi-class boosting field.

From the application perspective, AdaBoost.MH shows influence on ranking [6],  computer vision [10], natural language processing [4, 9]. multimedia [8]. Moreover, AdaBoost.MH is also realized by a boosting package MultiBoost [12].

We are glad to add the above discussions in our revision. If you have further questions, please fell free to raise them and we are glad to discuss with you.


### **References**

[1] A decision theoretic generalization of on-line learning and an application to boosting.

[2] Improved Boosting Algorithms Using Confidence-rated Predictions.

[3] Multi-class AdaBoost.

[4] LDA-AdaBoost.MH: Accelerated AdaBoost.MH based on latent Dirichlet allocation for text categorization.

[5] An Effective Fault Diagnosis Approach Based On Gentle AdaBoost and AdaBoost.MH.

[6] Ranking by calibrated AdaBoost.

[7] An improved boosting algorithm and its application to text categorization.

[8] Generalized multiclass adaboost and its applications to multimedia classification.

[9] MP-Boost: A Multiple-Pivot Boosting Algorithm and Its Application to Text Categorization.

[10] Improved multiclass AdaBoost for image classification: The role of tree optimization.

[11] A New Multiclass Generalization of AdaBoost.

[12] MultiBoost: a multi-purpose boosting package.
Thank you for your reply, we are glad that you are satisfied with our answers.
The author did a good job in answering my questions. I am happy to recommend the acceptance.
Thank you for your response.

Regarding the points I raised in my questions, I was considering the possibility that adding experimental evaluations could increase the value of this paper.
As Reviewer g6ZT mentioned, I also believe that even for theoretical research, plotting the obtained upper and lower bounds for several examples can sometimes provide insights.
However, I don't intend to lower my evaluation of this paper due to the lack of experimental evaluations and your response is sufficient to me.

Thank you also for your explanation about the importance of the research.
I can certainly understand that boosting is a very important technique, but could you elaborate further on your thoughts about the positioning and importance of AdaBoost.MH within the boosting methods for multi-class classification?

For example, [1] states that AdaBoost.MH was a state-of-the-art method as of 2014, which seems to have been one of the significances of solving this problem.
(I'm not arguing that only state-of-the-art methods are important subjects for theoretical analysis. I'm just citing this as an example of one way to persuade readers of a problem's importance.)
In contrast, this paper introduces AdaBoost.M1, AdaBoost.M2, AdaBoost.MH, and AdaBoost.MH with multi-class Hamming trees.
However, although it mentions that AdaBoost.MH was improved by multi-class Hamming trees, there isn't much discussion about the performance of each method.
Also, all the research mentioned in Related Works is by the same author.
Are there no other studies applying boosting to multi-class classification problems?
For instance, the AdaBoostClassifier in scikit-learn, a widely used machine learning library, adopts the method from [2], which I believe is not cited in this paper.

Within these various boosting methods for multi-class classification, how is AdaBoost.MH positioned practically, theoretically, or historically, and why is it important?
I think providing this kind of background could potentially appeal to a wider audience about the value of this important research.

[1] B. Kégl, Open Problem: A (Missing) Boosting-type Convergence Result for AdaBoost.MH with Factorized Multi-class Classifiers, Proceedings of The 27th Conference on Learning Theory, PMLR 35:1268-1275, 2014.  
[2] J. Zhu, H. Zou, S. Rosset, T. Hastie, “Multi-class adaboost.” Statistics and its Interface 2.3 (2009): 349-360.
Thank you for your reply, we are glad that you are satisfied with our answers.
Thanks the authors for the effort in addressing my questions. I would like to keep my original recommendations.