A Boosting-Type Convergence Result for AdaBoost.MH with Factorized Multi-Class Classifiers
Authors: Xin Zou
Zhengyu Zhou
Jingyuan Xu
Weiwei Liu
Venue: NeurIPS 2024 poster (2024)
Keywords: AdaBoost
Primary area: learning_theory

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.

A Boosting-Type Convergence Result for ADABOOST.MH with Factorized Multi-Class Classifiers
Xin Zou' Zhengyu Zhou' Jingyuan Xu Weiwei Liu
School of Computer Science, Wuhan University
National Engineering Research Center for Multimedia Software, Wuhan University Institute of Artificial Intelligence, Wuhan University
Hubei Key Laboratory of Multimedia and Network Communication Engineering, Wuhan University (zouxin2021, zzysince I 999, jingyuanxu777, liuweiwei863) gmail.com
Abstract
ADABOOST is 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 binary classifier and vote (or code) vector. However, the factorization makes it much more difficult to provide a convergence result for the factorized version of A AOBSO... MH. Then, Kégl raises open problem in COLT 2014 look for a convergence result for the factorized ADA ADABOOST.ME MH. In this work, we resolve this open problem by presenting convergence result for ADABoOST.MH with factorized multi-class classifiers.
Introduction
Boosting an approach machine learning based on the idea of creating highly accurate prediction rule by combining many relatively weak and inaccurate rules [19] and has inspired lot theoretical analysis and algorithm design in supervised learning [I] 17.. The seminal algorithm boosting, ADABoOST [9], requires 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.MI and ADABOOST.M2. Then, Schapire and Singer's seminal paper 20 proposes another extension named classifiers build a multi-class discriminant function of outputs when there are K classes, and then replace the weight vector in ADABoOST with weight matrix over instances and labels.
The main idea of ADABOOST.MO
is to use vector-valued base
The simplest implementation of the concept ADABOOST, MH use K independent one one-against- all 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- vector-values valued classifiers h into an input-independent code vector of length K, i.e., v E ( + K and label-indepente indeiendend scalar classifier şp. However, [5] gets in trouble when proving the convergence rate of the proposed implement of ADABOOST. MH due the factorization
"quall contribution
Corresponding author: Weiwei Liu ( cmm...mmmmmmmmmmmmmmmmmmmmmmmm..
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

step. So 14 raises an open problem in COLT 2014, looking for a convergence rate of the factorized ADABOOST.MI in [S]. with limited dependence on the sample size n.
Our contributions can be concluded as follows:
1. We provide convergence result (Theorem 3.3 of factorized ADABOOST.MH, where the step T which guarantees the training error to be is of order In)).
2. According to the requirement of [14,, we improve the dependence open problem by providing a convergence result (Theorem 3.4) where T is of order O (K In(n))). This result greatly improves when is much larger than K.
and resolve the
More related works deferred to Appendix
2 Preliminaries
We consider a multi-class classification problem where the input space X R2 and L = [K] attain
is the label space, where K is the number of classes and [K] {1..... K}. Assume the training data Dz = ((x1, ((x)))..... (Xa. ((,))),, where {(x;) E C is the label of x, Since we want
vector-valued classifiers, it is convenient to the one-hot labels y; E {-1, and all the other elements are -1 We use the new dataset D for Xi. where (((x)))) the input data of ADABOOST.MH and define an observation matrix (X.:Yn) (1),
X = (x) (X...... x²)" E gn label matrix Y == (y1 .')"" {-1,+11axx We call y and l the label and the index of x respectively, as in 14]
14 considers special case of MH, where each weak classifier has a specialized structure. ADABOOST.MH returns vector-valued discriminant function f - RKK with combined predictor Fr X + (11,+11 where Fx(x): sign(f(x):) for = 1,..., K. Here and this paper, we define
sign(r) {
+1 -1
r
I
The goal of the ADABOOST.MH algorithm 20 return f such that the Hamming loss of Fr.
(Fr, W)
TF,,T(F(xx)) # v.,),
is small possible, where II()) is the indicator function and W [w.,]] E [o, 1 is distribution over the data points and the labels. W can be chosen as any distribution over [n] x [K] and is different in different papers. In (20]. the authors set 1i,1 .k for any i E [n], [K] Here,
we follow [1] and set
{
if yi.i +1
(2)
if yi. -1
2n(K-1)
We define the weighted multi-class exponential margin-based error
K
(f W) = Wi exp (-f(x;)) v1.)
(3)
as surrogate for Ru (Fr, W). Since 1(FF # va.) = [(f(x)) S 0} - exp (-f(x;): 35,1).
we can get that (Fr, W) (F W).
It's well--known that ADA BoOST directly minimizes the exponential loss 119 Chapter 7], then, we can
apply the ADABOOST algorithm to the extended binary training set Up (x,, 34.) Mi= yielding the ADABOOST.ME MH algorithm, which directly minimizes Rfx W) and output the final discriminant function (.). where ((T) = Σ hx) a sum of 7 base classifiers h(() .Rd - R returned by base learner algorithm BASE(X, Y. W(!) in each iteration t.
Define
n
K
7h, W)
Σ
wa exp (-x(x)): v1.))
(4)

---

by similar calculation in 19 Proof of Theorem 3.1], we can obtain that:
T
( (T(T) W) = II 0 W(O).
According to the above discussion, we know that to minimize REXP (f(2), W), the base learner needs to find h9) that minimizes (() W at the 1-th iteration. In the following, we introduce two choices of h in (0 and [5], the corresponding convergence rate of REXP(F(2), W), and problems when trying to get convergence rate of RExp(f(T) W) for factorized ADABOOST.MH.
2.1
Unfactorized Choice
considers using h with the form h(x) = axp(x), where a E R and yp Rd + (-1,+1)* can be seen as the vector consists of K binary classifiers (f...... PK..
20
We consider the f-th iteration, and to simplify the notations, we omit the superscript and use W, h, (p, a to represent (((), h(t), (p(t), (!)) respectively. According [20). we define
wit Wi.1 (x(x:)1
(S)
as the edge, then we have
K ΣΣ
7(h, W)
Wid exp (-h(x:): y(l)
Wid exp ( (-oup(x;); (xx)p(x))..000 y1,1)
i=1 1=1
1=1
Σ
Wid1
Σ
Will e
(1)p(x)))x.1=11
WiT + E.dip(x)) W1i )x WAi1 = r, we can get that
Since Eitep(xe))m..=1
and Em Wi
Σ
Σ
--r
Wit
Wi
2
2
(x))
(lsp(x;))
So have:
h,, W) = 1+r
--r
+
6
2
2
Fix so first, minimizing Z(h, W) over yields that:
a In 1-r
This gives
7(h, W) VI- 22 72,
Then choose yp to minimize v1 -1-72, i.e. maximize |r|. If we have (()) 2 > 0 for all f, then we can get:
T
(-5²7) (-2T)
REXP(P(2 W) = II V 1 (-10) < (V1- S exp
which means that the weighted exponential error goes exponentially fast. Let exp exp (- W know that the weighted Hamming error becomes zero after
T
iterations. The condition (0) 2 for satisfied when the empirically weak learning condition on the classifier yp holds for the extended binary training set U (x,, kk))

---

Definition 2.1 (empirically 6-weak learning condition). For given binary dataset (xx.y1)..... (xm= }m)] where Yi ff-1,+1,, we say that the empirically d-weak learning condi- tion holds for some 8 >> 0 if for any distribution w E A over [m], we can always find binary classifier yp: +1} such that:
W. Vo (p(x)) 2
where
A
A
R
X 0 V [m],
the (m -iddiensiin probability simplex.
2.2
Factorized Choice
The original ADABOOST.MH 20 reduces the multi-class problem into K binary one-against-all classifications. 15 avoids such reduction by factorizing the vector-valued classifier h into input-independent vector of length K and a label-independent scalar classifier, Formally, [1] sets
h xx) = (vv((x);
where a R is positive real-valued base coefficient, v E (-1,+1]K an input-independent vote (or code) vector of length K, and y : Rd + {-1, is habel-independent binary classifier. For more details about the factorized ADABOOST.MH, please refer to Algorithm | in Appendix A
We consider the t-th iteration, and to simplify the notations, omit the superscript and use W, h, sp, at v to represent Wit) h(!), ((()))((0) aatt) v(() respectively. [15 shows that
6 te
aa -
7(h, W)
(μ++ 14-),
2
2
where
P u. (x)(())((()) # tvatk
1=1
is the weighted per-class error rate and
14+
Wi ((x(x) =1.13
the weighted per-class correct classification rate for each class 1, 1,..., K. Similar to Equa- tion (5). we define the multi-class edge of the classifier h as
>=>(v, W)
Σ 1=1
11
e (j++ 14-) Σ xp(x,)
Wi.t 01 V6l1.
(6)
1=1
where
= (pt m1-) =
Σ wi (xxx)) Vi,8
is the classwise edge of h. By a similar calculation as in Section 2.1 we know that 2(h, W) is minimized when we set
1+ 1-7) a =
which gives
Z(h, W) = v1 1-
So in order to minimize 2(h, W), we need to choose v and to maximize |n]. From the equation
7(, s, W) Σ Ui (M+ pl-), know that if 7(v, ip, W) < 0, then 7-v, W)

---

and we need to find binary classifier &p for all 1...., K, while for the unfactorized choice, we can find K binary classifiers ......, P separately for each class. In [14], the author tries to solve -Y(v, W) 2 O. So the problem reduces to finding v, yp that maximize From Equation 6 we know that for fixed ip, y is maximized when we choose V as
+1
PL+ 2 14 PI+ P1-
0y
for all classes 1= I,..., K.
Similar to Section 2.1 if there exists number 8 > 0 such that (v(0, w(o) 2 8 for all
t I,...,, T. then we can get an upper bound for RExP(f(T), W):
(F W)
II V V (vlo) s01 w()) & (VI-8) 1=1
(-2 T
82
I exp
(- <
which means that the weighted exponential eπrоr goes to error exponentially fast. Let exp 2n(K-1J. we know that the weighted Hamming emror becomes zero after
T 2 In (2n(2 1))
+1
8²
iterations. To get the exponential convergence rate, the question now is whether there exists number 5 0 such that y (v(t), so(t), W()) 2 5 for all 1,..., T.
2.3 Conditions for the Two Choices
For the condition in the unfactorized choice, if the empirically 8'-weak learning condition holds, then for a fixed weight matrix W, let / = {1 [K] >i= Wi,1 binary classifier ypr such that
> 0}, then for all I, there exists
Wid
(x,)8. 8
W/i11
m=1
then find tp such that 4p: = 8o for I I so that
K
Wil (x,) Vi = Wi (x.) yet 2
ΣΣ lel
Wi d' 8'.
IET
So the empirically 8'-weak learning condition is sufficient for exponential convergence rate for the
ADABOOST.M MH algorithm in (20).
For the factorized choice proposed in 15 we can not use the above argument since h is factorized
this problem by constructing secudo-weights and pseudo-labels and then applying the empirically we-k learning condition to the constructed dataset (x),)))... (xn:1hm)) 1.)).
rewrites 7
K
K
(x;)
Wi. U1 Vi.1 =
Σ (xx:) Σ
Wa [I(m Vi,1 = +1} Ifer y4tt = 11]
1=1
1=1
1
Σ (xx - - Σ ((xx))igg((u)) - - (otT)ue )uoo - w.
1=1
where we define
K
K
w
wrIHu Vil = +1}, w > 1=1
w wiII (ur Ve.t 1}
1=1
5

---

for simplicity. Then we define v/ = sign (w. -w,) as the i-th pseudo-label and wi | w as the i-th pseudo-weight, then
7 Σ w/ Di (((i).
However, since E w/= Σ | w
Ci -w;)=1, w' (wi,..., w.,) is not
necessarily a distribution on [n]. make use of the empirically 8'-weak learning condition, we define
w =
Σ
w S
we can get a lower bound w > such that u/s 2 w, then we have:
Σ w 3
w/ v/ (xxx)) wes
1/4 (xxx) 2 w/s 8 w. 0
i=1
where the first inequality is from the empirically 8'-weak learning condition. Since the number of examples n may be very large, wish the lower bound be independent of but it can depend on the number of classes K.
Then [14] raises open problem:
Whether there exists setup (X. W. Y, and function class) in which all of the 2 different vote vectors E (-1,+1} K lead to arbitrarily small (or zero) wsy or we can find constant (independent of n) lower bound w such that with at least one vote vector and classifier yp, w'z 2 w holds?
We resolve this open problem by showing that:
There exists constant
V2K such that: for any X, W, Y and fanc- tion class, there always exists a vote vector v s.t. wes 2 w holds. With this result, if the empirically 8'-weak learning condition holds, then for any X, W, Y, there always exists a vote vector v and binary classifier such that = Σi=1 ((xx) Ex= Wis
So if we run the AD- ABOOST.MH algorithmm with factorized h, REXP(f(T), W) becomes zero after at most T
8' Vi,t 2 V2R
4K In(2n --1K) + 1 iterations.
(6
3
Our Solution
In this section, provide formal theorems for above to the open problem and further discussions.
Because the training set size n may be very large, 11] requires the lower bound be independent of the training set size n (but can be dependent on the number of classes K), which much more difficult than finding a lower bound depends on To consider this problem more holistically, 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 w such that for any training set and weight matrix, there exists a code vector such that w/ 2 w (w's depends on the training set, weight matrix, and the code vector)" into "finding the lower bound of constrained minimax problem". We then provide n-dependent lower bound by the fact ||x|]| 2 ||x|| and the fact that the maximum is not smaller than the average, where llp is the f,-norm of vector. For the r-independent lower bound, we choose to lower bound the expected value of w/: when the drawn from some distribution on {-1, +1] To eliminate the trouble caused by the labels, we choose v to be Rademacher random vector with independent elements, i.e., == (61, ........ ...) where (ee 1] = (e,
code vector
bound with the help of Khintchine inequality [10] 2 for i 1,..., K. We then provide the lower

---

We define
K
W
W E Ruxk W., 2 for all E (m), [K]
Σ
W =
1=1
as the set all possible W. Lete())) [K] + (-1,+1] be
e(I) {
+1 i=l
-1 i
we the define y = {(e(4))..... e(())) E (f11,+1) 11....., In E -= [K]} as the set of all
possible Y, and define V = +13 as the set of all possible v. We then have:
w/,(W, Y.v)
Σ
Iu WT
K
wai [Terea. = +1] Iumu = -1]}
Σ W4.1 ey V4.1
Σ K(W
O v) = 1(W @ -)-iIli
where O is the Schur product and |x|| Ei= | is the -orm of the vector
The following two facts translate the problem that are concerned with into minimax problem. 3.1. The following two statements are equivalent:
(1) There exists setup (X, W, Y) in which all of the 2 different vote vectors v V lead to arbitrarily small (or zero) w'g.
(2) min max || (W O Y) v/11 is arbitrarily small (or zero).
YEXvE
Fact 3.2. The following two statements are equivalent:
(1) We can find 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's 2 w holds.
(2) we can find constant (independent of n) lower bound such that
min max ([ @ Y).
Wew.YEv
v/I1 Z W.
min max WEW.YEY begin with simple n--eependent lower bound. Theorem 3.3 (An n-dependent lower bound).
So, to find the lower bound w, we need to prove that
max/ (W O Y) v/I 2 w. Let's
min WEW.YEY
max
YY) v/11 2 n
Proof of Theorem 3.3
min max (W @ Y) v/li weW.Yeyvey
min max (W ② Y) v 1/ WEW.YEVvEY
Σ WiJl Vi, -
min max WEW.YEEVEEE.EE.
min max
Wil1
WEWsE(ml
where is from the fact that ||x[|] 2 ||x|| where ||x||<< max |x; is the norm of x; b comes 15i5n
from choosing et Vi,t for 1,..., K when is fixed; e from the fact that max 5
W7,1 >
xE
DE D Wht and the equation can be attained.
7

---

Remark 1. The lower bound in Theorem 3.3 depends on and if we use 1 as the lower bound of W'y then we need at most T 2n In(2n( 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 of the reasons that AT4] wants to get lower bound independent of
(6')
Next, we introduce how we solve the open problem to get lower bound independent of n. 1
Theorem 3,4 (An n-indepenndent lower bound).
min max (W + Y) v/1 Z V2K" WEW.YED'VE
Remark 2. Theorem 3.4 shows that there is a constant w
V2K such that for any setup W, Y, 2 This solves the open problem proposed by In(2n(K (111) iterations (see Corollary 3.69 to make the (87)
there always exists code vector such that w/: 144. So need al most T exponential error become zero.
To prove Theorem 3.4 we use the well-known Khintchine incquality (10) Lemma 3.5
Lemma 3.5 (10) Khintchine inequality). Let (enJa= be i.i.d. random variables with P(en, 1 = for -....., N, i.e,, a sequence with Rademacher distribution. Let < p < oo and let
31, -.y.....-0 Fn C. Then
1/p
1/2
Ap
Σ
In 2
EE El
Σ
En
Bp
In
for some constants Ap. Bp 0 depending only p, where
21/2-1/p 1/p
0 <<p5 S Po Po k 2 2<p<o
Ap
21/2 + (1/(++1)))//7)/
1
and
Bp { 1 2/(((( 1)/2)//7)\//
0 < 2<p< 0
where Po 1.847 and I is the Gamma function.
Proof of Theorem 3.4 The basic idea our proof is to consider the average performance of different code vectors for fixed choices of W, Y, i.c., use the fact that the maximum is less than the average, which gives:
min max W @ Y) v/l1 2 WEW
min WEW.YEVwDD
(I о Y) vll2
a
K
min NEW.YE)vol
Wiy U1 16.1
for any distribution on V.
We take U1 . be independent Rademacher random variables and then get:
K
min WeW.YEVV~D
E
Why Ve.1
min WEW.YEN
E
WA,1 Et Ve.1
1=1
1/2
A min WEW
W
K
1/2
K
min
W
2
WEW
i=1
1=1
K
K
min wew
2
K
km
1=1
/2
8

---

where applies Lemma 3.5 with and the fact that vi, for all i, puts in the value of A1; the concavity of v and Jensen's 's inequality.
With the lower bound of w we can now provide lower bound of the edge and convergence guarantee for the version of ADABOOST.ME MH proposed by [[5] conditioned the empirically 5'-weak learning condition.
Corollary 3.6 (Lower bound for 7)- the empirically 8' -'-weak learning condition holds, then for any X, W E W, Y E V, there always exists a binary classifier xp" and code vector v max such that
8
ryy
W)
V2K
If we run ADABOOST.MI with factorized h, then we have
(F W) S exp (-8))
8'
4k
and we need at most
4K In(2 - 1))
T
+1
(8')2
make the exponential error REXP (T(T), W) become zero.
Proof of Corollary 3.6 For any W, X, Y. let mia arg max (W @ Y) vvl1. Let wh, 3/ uss be VEV defined as before, where we replace v there by max By Theorem 3,4 w/y
V2K > 0.
By the empirically 8'-weak learning condition, there exists binary classifier yp" such that
w
1/4 50" (x:) 2
which means that
8
m(y 60, W) 2 w 2
/2K
For fixed W, X, Y, let (ip) be the code vector depending ip that is defined in Equation 7 Since the choice v" (5) maximizes y when is fixed, we have that:
8
7(v" (5 ) W) 2 ((
W)
/2K
that when we run ADABOOST.MH with factorized h, which returns sp" v ((*) at each iteration,
Combining the arguments in Sections 2.1 and 2.2 shows REXP (F()), W) exp
(- 8' "R
and
RExP W) < 2n(K-1 i.c Ru Eprr W) =
after at most
4K In(2n( - 1))
T
+1
(8')2
iterations.
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 lower bound of w's that independent of that the author thinks the number of examples n can be arbitrarily large in some cases, which may make the lower bound of w/z arbitrarily small.
Combine our two lower bounds in Theorems v +-1 such that:
3.4 for any X, W. Y, we can always find
" 2 max
V2K
so the lower bound can become arbitrarily small only when and K tend to infinity together.

---

4 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 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 7 where the training error becomes zero. So boosting al 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 reducing the multi-class classification problem multiple two-class problems, among which the most famous and influential one is ADABOOST.MI [20]. Moreover, ADABOOST. MH has inspired the proposal many other multi-class boosting algorithms. For example, inspired by the characteristics of ADA 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.ME algorithm to the multi-class case without reducing it to multiple two-class problems; [ demonstrates how to improve the efficiency and effectiveness of ADABOOST.MH and proposes the algorithm LDA-ADABOOST MH; [8] 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 also many other works based on ADABOOST. M.
12 []. Furthermore, many works (for example, 13 baseline, which further shows the importance of ADABOOST. For example, the only baseline used in 133 is ADABOOST MH. In summary, ADABOOST .M 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 shows that Kégl's work [T5) 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.
g 25 (77) use ADABOOST, MH as the
5 Conclusion
In this paper, we resolve the open problem raised by 14 by presenting a n-indeppndent lower bound for wyy In addition that, also provide n-deepenentt lower bound for wy to show that we: may be arbitrarily small only when n and tend to infinity together. Based on the lower bounds for w's and the empirically 8'-weak learning condition, 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.
Acknowledgments and Disclosure of Funding
This work is supported by the National Natural Science Foundation of China under Grant 624B2106. the Key R&D Program of Hubei Province under Grant 2024BAB038, National Key R&D Program of China under Grant 2023YFC3604002, and the Fundamental Research Fund Program of LIESMARS.
References
[1] Bassam AI-Salemi, Mohd Juzaiddin Ab Aziz, and Shahrul Azman Noah. Lda-adaboost..ii Accelerated adaboost.mh based on latent dirichlet allocation for text categorization. J. Inf. Sci., 41(1):27-40, 2015.
[2] Noga Alon, Steve Hanneke, Ron Holzman, and Shay Moran. A theory of PAC learnability of partial concept classes. In FOCS, pages 658-671, 101.6711222 2021.
[3] Nataly Brukhim, Daniel Carmon, Irit Dinur, Shay Moran, and Amir Yehudayoff. A characteri- zation of multiclass learnability. In FOCS, pages 943-955, 2022.
10

---

[4] Nataly Brukhim, Amit Daniely, Yishay Mansour, and Shay Moran. Multiclass boosting: Simple and intuitive weak learning criteria. NeurIPS, 2023.
[5] Nataly Brukhim, Steve Hanneke, and Shay Moran. Improper multiclass boosting, COLT, pages 5433-5452, 2023.
[6] Nataly Brukhim, Elad Hazan, Shay Moran, Indraneel Mukherjee, and Robert E. Schapire. Multiclass boosting and the cost of weak learning. NeurIPS, pages 3057-3067, 2021.
[7] Róbert Busa-Fekete, Balázs Kégl, Tamás Éltetö, and György Szarvas. Ranking by calibrated adaboost. In Olivier Chapelle, Yi Chang, and Tie- Yan Liu, editors, Yahoo! Learning to Rank Challenge, volume 14, pages 37-48, 2011.
[8] Andrea Esuli, Tiziano Fagni, and Fabrizio Sebastiani. Mp-boost: A multiple-pivol boosting algorithm and its application to text categorization. In Fabio Crestani, Paolo Ferragina, and Mark Sanderson, editors, SPIRE, volume 4209, pages 1-12, 2006.
[9] Yoav Freund and Robert E. Schapire. tecision- generalization of on-line learning and an application to boosting. J. Comput. Syst. Sci., 55(1):119-133, 1997.
[10] Uffe Haagerup. The best constants in the khintchine inequality. Studia Mathematica, 70(3):231- 283, 1981.
[11] Steve Hanneke. The optimal sample complexity of PAC learning. Mach. Learn, Res., 17:38:1-38:1,, 2016.
[12] Wei Hao and Jiebo Luo. Generalized multiclass adaboost and its applications to multimedia classification. CVPR Workshops, page 113, 2006.
[13] Trevor Hastie, Saharon Rosset, Ji Zhu, and Hui Zou. Multi-class adaboost. Statistics and its Interface, 2(3):349-336 -300, 2009.
[14] 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.
[15] Balázs Kégl. The return of adaboost.mh: multi-class hamming trees. In ICLR, 2014.
[16] Jacho Lee and Maxim Raginsky. Minimax statistical learning with wasserstein distances. In NeurlPS, pages 2692-2701, 2018.
[17] Omar Montasser, Steve Hanneke, and Nathan Srebro. VC classes are adversarially robustly learnable, but only improperly. Alina Beygelzimer and Daniel Hsu, editors, COLT, pages 2512-2530, 2019.
[18] Peng Peng. Yi Zhang, Yinan Wu, and Heming Zhang. An effective fault diagnosis approach based on gentle adaboost and adaboost.mh, 2018 IEEE International Conference on Automa- lion, Electronics and Electrical Engineering (AUTEEE), pages 8-12, 2018.
[19] Robert E. Schapire and Yoav Freund. Boosting: Foundations and Algorithms. The MIT Press, 05 2012.
[20] Robert E. Schapire and Yoram Singer. Improved boosting algorithms using confidence-rated predictions. Mach. Learn., 37(3)297-336, 1999.
[21] Fabrizio Sebastiani, Alessandro Sperduti, and Nicola Valdambrini. An improved boosting algorithm and its application to text categorization. In CIKM, pages 78-85, 2000.
[22] Vladimir Vapnik. Principles of risk minimization for learning theory. In NeurIPS, pages 831-838, 1991.
[23] Jingyuan Xu and Weiwei Liu. On robust multiclass learnability. In NeurlPS, 2022.
[24] Dong Yin, Kannan Ramchandran, and Peter I.. Bartlett, Rademacher complexity for adversari- ally robust generalization. In JCML, pages 7085-7094, 2019.

---

[25] Arman Zharmagambetov, Magzhan Gabidolla, and Miguel Á. Carreira-Perpiñan. Improved multiclass adaboost for image classification: The role of tree optimization. In ICIP, pages 424 428, 2021.
[26] Zhengyu Zhou and Wei Liu. Sample complexity for distributionally robust learning under cqi-r divergence. Mach. Learn. Res., 24:230:1-230:27, 2023.
[27] Zhu, Saharon Rosset, and Trevor Hastie. A new multiclass generalization of adaboost. Ann Arbor, 1001:48109.
12

---

A The pseudocode of the factorized ADABOOST.MH
In this section, we adapt the pseudocode of the factorized ADABOOST. from 14 X the n observation matrix, Y is the x d label matrix, W is the user-defined weight matrix used in the definition of the weighted Hamming error ① Let BASB(-....) be the base learner algorithm, and T be the number of iterations. Let (*) be the base coefficient v-(t) be the vector, (-) be the scalar base (weak) classifier, h (.) be the vector-based classifier, and (-))() be the final (strong) discriminant function.
Algorithm 1: The factorized ADABOOST.MH
Input :X, Y, W, BASE(;,".),T)
W(1 WW:
for to
(al9,v(9 v(),, (0(1) + (A, Y, W());
(.) t a (1) y(000 (.))
for i 4-1111 1 to do
for t 1 to do
exp (1) (xs))u.))
(1+1) + wil
(t)
Wi
Σ
" expl (by (2,)),
(t)
end
end
10 end
()) Output: :f (f) = =T ():
B Related Works
In addition to II ADABOOST.M2, ADABOOST.MEE MH, and factorized ADABOOST.MH. there are also some works on multi-class boosting.
To circumvent the hardness result for large class of natural boosting, 55) utilizes the technique learning and proposes efficient improper multi-class boosting algorithm with sample and oracle complexity bounds that are entirely independent of the number 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 trade-off between number of oracle calls and the resources required of the weak learner.
proposes an efficient multi-class boosting algorithm with the help of list learning, the success of the proposed algorithm is guaranteed by the relaxed --RRG condition.
In this paper, solve the open problem proposed in [4] and provide bound for the oracle complexity of the factorized ADABOOST.ME algorithm. The algorithm that we consider is different from those in [ 4), and the conditions also different. We find missing convergence result for factorized ADA BOOST.ME. MH, so we think our work is complementary of the related works [5] 6
13

---

NeurIPS Paper Checklist
Claims
Question: Do the main claims made in the abstract and introduction accurately reflect 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 perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize other settings.
is fine to include aspirational goals as motivation as long is clear that these goals not attained by the paper.
2. Limitations
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 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 separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results 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 few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?
Answer: [Yes]
14

---

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

---

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 the NeurlPS code and data submission guidelines (https://nips.. cc/
pub i quides Codeeubmme ss ssionn iisionoolice icy) for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https //nips. cc/
wwublic/guideen / //ddideee/Cdeeeeeeee Cooeeeooeeeeeeeeee SudeSuumiiee wwwmisssiiii ssssnooliccyyyyoco for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [NA]
Justification: Our paper is purely theoretical, with no experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [NA]
Justification: Our paper is purely theoretical, with no experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, at least for the experiments that support main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
should be clear whether the error bar is the standard deviation the standard error of the mean.
16

---

It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of enrors is not verified.
For asymmetric distributions, the authors should be careful to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of exccution) needed to reproduce the experiments?
Question:
Answer: [NA]
Justification: Our paper is purely theoretical, with no experiments.
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary failed experiments that didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics
Answer: [Yes]
Justification: This paper is about a theoretical result for multi-class boosting algorithm, clearly conforms with the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurlPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. if there is special consid- cration due to laws or regulations in their jurisdiction..
10. 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 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.
17

---

The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that 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 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 attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility ML).
11. Safeguards
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, scraped datasets)?
Question:
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 such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere 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 require this, but we encourage authors to take this into account and make 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 experiments, which needs 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 URL.
The name of the license (c.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 the package should be provided. For popular datasets, paperssww wwwoosocittcceeeoeo com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of 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.
18

---

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


Reviews:
[{"review_id": "U2yeZqTYKy", "reviewer": "Reviewer_BMi6", "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.", "questions": "See above.", "limitations": "The authors answers NA in the Checklist.", "rating": 9, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "This submission did a really good job in presenting the stories of ADABOOST, ADABOOST.MH and the factorized version of ADABOOST.MH. The backgrounds are also clearly shown in the paper, which makes the researchers who are not familiar with this kind of topic can fast gain the main ideas of this paper. Actually, I enjoy the reading of this paper. Technically, it is interesting to transform the open problem to a minmax problem, and both n-independent lower bound and n-dependent lower bound are provided in this paper. The Khintchine inequality plays the key role in the proof. The proof is simple and easy to follow. The significance of this paper is very important, because it solves a long lasting open problem.", "weaknesses": "I did not find the significant weakness about this paper. But I still have some questions. I hope the author can address them.\n1, Why there is the absolute value in the equations between lines 217 -218?\n2, In Corollary 3.5, why the exponential error can be zero? Is this an asymptotic result or non- asymptotic result?\n3, What are the derivations between lines 232 and 233? Can you provide more details?\n4, Why the first equation below line 219 hold? Can you explain this?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your recognition. We are glad you like our paper. Next, we answer your questions.\n\n1. **Why there is the absolute value in the equations between lines 217 -218?** Answer: Because we are handling the $\\ell_ 1$-norm of a vector, and the $\\ell_ 1$-norm of a vector is the sum of the absolute value of its elements.\n2. **In Corollary 3.5, why the exponential error can be zero? Is this an asymptotic result or non-asymptotic result?** Answer: We are sorry for confusing you, in fact it is a typo, we want to say that the **Hamming loss** can be zero. The reason why the Hamming loss becomes zero after $T^*$ steps is shown in the lines 237-238. It is a non-asymptotic result since we explicitly provide the convergence rate that is related to $T, K, \\delta^\\prime$.\n3. **What are the derivations between lines 232 and 233? Can you provide more details?** Answer: For the given $\\mathbf{W,X,Y}$, by Theorem 3.4, there exists $\\mathbf{v}^{\\max}$ such that $w_ {\\Sigma}^\\prime \\ge \\frac{1}{\\sqrt{2K}} > 0$. Since $w_ {\\Sigma}^\\prime > 0$, we know that $\\gamma\\left( \\mathbf{v}^{\\max} , \\varphi^*, \\mathbf{W} \\right) = \\sum_ {i=1}^n w_ i^\\prime \\cdot y_ i^\\prime \\cdot \\varphi^*(\\mathbf{x}_ i) = w_ \\Sigma^\\prime \\cdot \\sum_ {i=1}^n \\frac{w_ i^\\prime}{w_ \\Sigma^\\prime} \\cdot y_ i^\\prime \\cdot \\varphi^*(\\mathbf{x}_ i) \\ge w_ \\Sigma^\\prime \\delta^\\prime \\ge \\frac{\\delta^\\prime}{\\sqrt{2K}}$. The main skill of this step is to construct weights $\\frac{w_ i^\\prime}{w_ \\Sigma^\\prime}$ that form a distribution, the construction is dependent on the fact that $w_ \\Sigma^\\prime > 0$.\n4. **Why the first equation below line 219 hold? Can you explain this?** Answer: In this line, we consider choosing $\\mathbf{v}$ to be the Rademacher random vector with **independent** elements. By the independence, we can just replace the random variables $v_ 1, \\dots, v_ K$ with $K$ independent Rademacher random variables $\\varepsilon_ 1, \\dots, \\varepsilon_ K$.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "w1LWrXkMsZ", "reviewer": "Reviewer_iRY2", "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.\nThe key points of the proof are as follows:\n\n* Reformulating the proposition to be proved as a lower bound evaluation of a minimax problem.\n* Treating the code $v$ as a Rademacher random variable, bounding the maximum value from below by the expectation, and then applying Khintchine inequality.", "questions": "* Is it possible to confirm the $\\delta'$-weak learning condition is satisfied for a real-world dataset?\n* 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": "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.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper successfully resolves the open problem highlighted by [7].", "weaknesses": "It seems the paper does not sufficiently explain the significance of resolving the open problem pointed out by [7].", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your suggestions. We now provide explanations about the issues in weaknesses and questions.\n\n### **For the weakness: significance of the work.**\n\nThe main contribution of our work is solving an open problem in [1] and providing a convergence rate for the factorized AdaBoost.MH algorithm, which is thought to be meaningful by the Reviewers BMi6, jA8z, and HyZV.\n\nBoosting is a very important part of statistical learning theory and AdaBoost.MH is an important algorithm in multiclass boosting. Boosting algorithms are basic but important tools in statistical learning theory, for example, in the PAC learning framework, many algorithms are constructed by boosting algorithms [2-4]. Furthermore, the **convergence rate** of the boosting algorithm usually affects the sample complexity of the proposed algorithm, i.e., the sample complexity of the constructed algorithms usually depends on the value $T^*$. So we believe our convergence rate can be helpful in the field of statistical learning theory.\n\n### **For the questions.**\n\nFirstly, we should emphasize that the $\\delta$-weak learning condition is the most basic and commonly used assumption in boosting [5]. From the above answers, we know that boosting algorithms are usually used in statistical learning theory. In such applications [2-4], they try to construct a weak learner based on some known algorithms and then apply boosting results. In such cases, the weak learners are easily to be shown to satisfy the $\\delta$-weak learning condition. So, from the theoretical perspective, we can easily construct weak learners that satisfy the $\\delta$-weak learning condition based on known learning algorithms, which means that **we do not need to worry about whether the $\\delta$-weak learning condition holds when applying our convergence results to statistical learning theory problems**.\n\nTo the best of our knowledge, there is no work focusing on validating the $\\delta$-weak learning condition for real-world datasets. The validation of such a condition depends on a lot of factors, for example, it depends on the hypothesis class chosen for the weak learner, and the examples that we sample. Suppose $\\gamma(\\mathbf{w}, \\varphi)$ is the margin of $\\varphi$ under weight vector $\\mathbf{w}$, and $\\mathcal{H}$ be the hypothesis class used for the weak learner. By definition 2.1, to validate the empirically $\\delta$-weak learning condition, we need to calculate $\\underset{\\mathbf{w} \\in \\Delta^{m-1}}{\\min} \\underset{\\varphi \\in \\mathcal{H}}{\\min} \\gamma(\\mathbf{w}, \\varphi)$ and set it to be the value of $\\delta$. It is obvious that calculating $\\delta$ involves taking the minimum over $\\mathcal{H}$ and $\\Delta^{m-1}$, which is possible but generally computationally intractable.\n\nIt's an interesting topic to validate the $\\delta$-weak learning condition and confirm how quickly the weighted multi-class exponential margin-based error decreases by numerical experiments. However, our paper is purely theoretical, we focus on the theoretical perspectives of the factorized AdaBoost.MH algorithm. So the experiments are beyond the scope of this work.\n\n### **References**\n\n[1] Open problem: A (missing) boosting-type convergence result for adaboost.mh with factorized multi-class classifiers.\n\n[2] A theory of PAC learnability of partial concept classes.\n\n[3] A Characterization of Multiclass Learnability.\n\n[4] VC Classes are Adversarially Robustly Learnable, but Only Improperly.\n\n[5] Boosting : Foundations and Algorithms.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "RPPZOrxByI", "reviewer": "Reviewer_jA8z", "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.", "questions": "Please refer to the weaknesses part.", "limitations": "No. The theoretical results are only limited to the factorized AdaBoost.MH algorithm.", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "**Originality.** The proofs of this paper are based on basic algebraic and probabilistic tools, so I believe the paper is original.\n\n**Quality.** This is a high-quality paper. It is well-written and solves a COLT 2014 open problem. The proofs are sound and detailed, and the solution is elegant.\n\n**Clarity.** The writting of this paper is good. The definitions and notations are very clear, and the conditions of the theorems and corollaries are clearly stated.\n\n**Significance.** A long-playing open problem is beautifully solved by the paper. The paper provide a convergence rate for the effecient factorized AdaBoost.MH algorithm. So I think the paper is of great significance.", "weaknesses": "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.\n\nSecondly, I think it would be better to provide some high level intuitions about idea to solve the open problem.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your recognition. We are glad you like our paper.\n\n**For the first weakness:** As you say, complicated proofs are not neccessarily better. We believe that it is great to solve an open problem through a easy method.\n\n**For the second weakness:** Thank you for your reminder. The main idea of our proof is to take advantage of the properties of the terms $\\mathbf{W, Y}$ and $\\mathbf{v}$. The most intuitive idea is to use the property that the sum of the elements in $\\mathbf{W}$ is $1$. So, in the proof, we try to get the sum of the elements in $\\mathbf{W}$ or other terms that is related to the sum of the elements in $\\mathbf{W}$.\n- In Theorem 3.3, we utilize the relationship between norms to get a lower bound that involves the maximum row sum of $\\mathbf{W}$. Fortunately, since the sum of $\\mathbf{W}$ equals $1$, we know that the maximum row sum of $\\mathbf{W}$ is not less than $\\frac{1}{n}$.\n- In Theorem 3.4, we consider the average performance of some different code vectors rather than the worst performance of all possible code vectors. We take $\\mathbf{v}$ to be drawn from a uniform distribution on the binary cube $\\\\{ -1, +1 \\\\}^K$. And fortunately we find that the average performance can be deduced to the sum of the elements in $\\mathbf{W}$ according to the Khintchine inequality and Jensen's inequality.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "0s2GQVC4do", "reviewer": "Reviewer_g6ZT", "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).", "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": "N/A", "rating": 4, "confidence": 4, "soundness": 3, "presentation": 1, "contribution": 2, "strengths": "1. The authors derive two upper bounds for the algorithm's convergence: one that depends on the number of instances (n) and another that relies solely on the number of classes (K). While the first bound may be less relevant due to its dependence on n, which can grow arbitrarily large, the second bound offers a more useful guarantee of convergence.\n2. The authors further demonstrate that the lower bound on w'_{\\Sigma} (the weighted sum) can become arbitrarily small only in the limiting case where both the number of instances and classes approach infinity simultaneously.", "weaknesses": "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.\n2. 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.\n3. 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your suggestions. We now provide explanations about the issues in weaknesses and questions.\n\n### **For weaknesses.**\n**For the significance of our work.** Firstly, we claim that the main contribution of our work is solving an open problem in [1] and providing a convergence rate for the factorized AdaBoost.MH algorithm, which is thought to be meaningful by the Reviewers BMi6, jA8z, and HyZV. Since this paper focuses on the theoretical perspective, we next introduce the importance of boosting algorithms from the theoretical perspective. Boosting is a very important part of statistical learning theory and AdaBoost.MH is an important algorithm in multiclass boosting. Boosting algorithms are basic but important tools in statistical learning theory, for example, in the PAC learning framework, many algorithms are constructed by boosting algorithms [2-4]. Furthermore, the convergence rate of the boosting algorithm usually affects the sample complexity of the proposed algorithm, i.e., the sample complexity of the constructed algorithms usually depends on the value $T^*$. So we believe our convergence rate can be helpful in the field of statistical learning theory.\n\n**Regarding the experimental validation.** As stated above, boosting algorithms are very useful in statistical learning theory, so our results are surely valuable, especially in applications to statistical learning theory. Since our paper is **purely theoretical**, we focus on the theoretical perspectives of the factorized AdaBoost.MH algorithm. So the experiments were beyond the scope of this work. For some results about the effectiveness of the factorized AdaBoost.MH algorithm, please refer to [5].\n\n**For the writing issues.** We are sorry for confusing you. In the early sections, we use the undefined symbol $w_ {\\Sigma}^\\prime$ to introduce the main concerns of [1], it is truly not suitable. In fact, the ultimate concern of [1] is a convergence rate for the factorized AdaBoost.MH algorithm, we are glad to restate the concern of [1] as an upper bound for the convergence rate rather than a lower bound for $w_ {\\Sigma}^\\prime$, and then the $w_ {\\Sigma}^\\prime$ term will not appear before its definition. Since our aim is to study the convergence rate for the factorized AdaBoost.MH algorithm, it is important to provide an overview of factorized AdaBoost.MH algorithm. We recapitulate [1] in section 2.2 to provide a complete introduction to the problem that we solve. It is a good idea to condense this information into a concise summary, we are glad to do it in our revision.\n\n\n### **For questions.**\n\nWe are sorry for confusing you. In fact, we refer to our second result as being independent of $n$ because we are talking about $w_ {\\Sigma}^\\prime$ (which is focused on in [1]) rather than $T^*$. In fact, the $n$ term in $T^*$ is unavoidable since we need to set the upper bound of the exponential loss to be less than $\\frac{1}{2n(K-1)}$ (as done in the proof of Corollary 3.5). We will clarify it to remove ambiguity in our revision.\n\n### **References**\n\n[1] Open problem: A (missing) boosting-type convergence result for adaboost.mh with factorized multi-class classifiers.\n\n[2] A theory of PAC learnability of partial concept classes.\n\n[3] A Characterization of Multiclass Learnability.\n\n[4] VC Classes are Adversarially Robustly Learnable, but Only Improperly.\n\n[5] The return of AdaBoost.MH: multi-class Hamming trees.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "XzIeJDzbTK", "reviewer": "Reviewer_HyZV", "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.", "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]?\n\n[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": "No.", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "- This paper solves an open problem proposed in COLT 2014, which has been open for about 10 years. The proof is clear and the basic ideas behand the proofs are given.\n- This paper is well-written and easy to read.\n- The background is clearly introduced, which is friendly to new readers.", "weaknesses": "- A minor issue: part of the presentations are similar to that in [1].\n\n\n[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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your recognition. We are glad you like our paper.\n\n**For the weakness:** Thank you for your reminder. We use the presentations that are similar to that in [1] in order to make them consistent and make it convenient for the readers that have read [1] before to understand our paper. We would carefully check the presentations of our paper and change the unneccessary ones which are similar to [1].\n\n**For the question:** In fact, the vector $\\mathbf{v}$ in [1] is also assumed to belong to $\\\\{ -1,+1 \\\\}^K$. The authors of [1] forget to mention it after equation (5). According to the equation (12) in [1], we know that the vector $\\mathbf{v}$ considered in [1] in fact belongs to $\\\\{ -1,+1 \\\\}^K$.\n\n\n### References\n[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.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

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