acceptodds
Under review as a conference paper at ICLR 2027

Factorized AdaBoost.MH Achieves the Same Convergence Rate as AdaBoost.MH

Abstract

AdaBoost.MH reduces multi-class classification to a collection of binary subproblems and enjoys the classical boosting-type convergence guarantee under a weak learning condition. A more structured variant, Factorized AdaBoost.MH, uses base classifiers of the form , where a single binary classifier is shared across all classes and the label dependence is carried by a vote vector . This factorization is algorithmically attractive and achieves better performance in practice, but its convergence depends on whether one can always choose a vote vector with sufficiently large induced binary weight mass. Previous work resolved this question with a lower bound , which still leaves a dimension-dependent slowdown relative to the original AdaBoost.MH analysis. In this paper, we sharpen this combinatorial step and provide an exact characterization. For the minimax quantity governing the factorized edge, we prove , where for , for even , and for odd . Since , our bounds show that uniformly over and . Consequently, Factorized AdaBoost.MH achieves the same boosting-type convergence rate as AdaBoost.MH up to a universal constant factor, removing the previously suggested additional dependence on or in the number of boosting rounds.

Primary area:
learning theory
Keywords:
Boosting, Learning Theory

Reviews

Among:
Shape:
1234this paper, Top 4%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.33 over 3 reviews, above 96% of the others.
Reviewer_sFzWOpenReview ↗
Rating
4
Confidence
1
Informativeness
3
Presentation
3
Soundness
3
Read review
Paper summary

This paper studies the convergence of Factorized AdaBoost.MH through a minimax quantity that measures the weight retained after reducing a multiclass problem to a binary one. It provides an exact characterization of this quantity and uses it to show that the factorized method has a boosting-round upper bound of the same order as AdaBoost.MH, up to a constant factor.

Critical strengths

The paper gives a sharp characterization of the combinatorial quantity governing the factorized edge. The analysis is technically interesting and improves on prior bounds by removing their apparent dependence on the number of examples or classes.

Critical weaknesses
  1. The problem setting and terminology need to be clarified. The paper should distinguish classes from labels consistently. For example, the first sentence of the second paragraph of the Introduction appears to conflate the two concepts. Multiclass classification and multi-label classification are different settings. Although AdaBoost.MH can be applied to both, the paper defines YY as a signed one-hot label matrix, so each example has exactly one positive entry. The results therefore concern multiclass classification and do not directly establish a result for general multi-label classification.

  2. There is a notation error in Lemma 4.3. In the definition of the nearly balanced vector set (lines 655–658), the sum should run from j=1j=1 to KK, not nn, since each vote vector has KK coordinates (classes).

Questions for authors

see Critical Weaknesses.

Reviewer_mQMmOpenReview ↗
Rating
4(+1)
Confidence
2
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

The paper studies the training-error convergence of Factorized AdaBoost.MH (Kégl, 2014). In that method each weak hypothesis has the form h(x)=αvφ(x)h(x) = \alpha v \varphi(x): a single binary classifier φ\varphi shared by all classes, and a vote vector v∈{±1}Kv \in \lbrace \pm 1 \rbrace^K that sets how each class responds to it.

Once vv is fixed, the multi-class problem reduces to a binary problem whose usable weight is wΣ′=∥(W⊙Y)v∥1≤1w'_\Sigma = \lVert (W \odot Y) v \rVert_1 \le 1. Under the empirical δ\delta-weak learning assumption, the factorized edge is then at least δwΣ′\delta w'_\Sigma. The convergence rate is therefore governed by the worst-case quantity

Wn,K=min⁡W,Ymax⁡v∈{±1}K∥(W⊙Y)v∥1.\mathfrak{W}_{n,K} = \min_{W, Y} \max_{v \in \lbrace \pm 1 \rbrace^K} \lVert (W \odot Y) v \rVert_1 .

Zou et al. (2024) showed Wn,K≥max⁡{1/n,1/2K}\mathfrak{W}_{n,K} \ge \max\lbrace 1/n, 1/\sqrt{2K} \rbrace, which still allowed a min⁡{n2,2K}\min\lbrace n^2, 2K \rbrace-factor increase in the number of boosting rounds.

The paper's main result (Theorem 3.5) is the exact value Wn,K=Cmin⁡{n+1,K}\mathfrak{W}_{n,K} = C_{\min\lbrace n+1, K \rbrace}, where

Cq={1,q=1,q3q−4,q≥2 even,q+13q−1,q≥2 odd.C_q = \begin{cases} 1, & q = 1, \\\\ \dfrac{q}{3q-4}, & q \ge 2 \text{ even}, \\\\ \dfrac{q+1}{3q-1}, & q \ge 2 \text{ odd}. \end{cases}

Hence Wn,K∈(1/3,1]\mathfrak{W}_{n,K} \in (1/3, 1]. The argument has four parts:

  • Lower bound (Theorem 3.1). Take the better of the all-ones vote vector and a random (nearly) balanced vote vector, then optimize over the true-class weight mass.
  • Refined lower bound (Theorem 3.3). Merge all label columns that are never a true label into one column, which shows the effective number of classes is min⁡{n+1,K}\min\lbrace n+1, K \rbrace.
  • Matching upper bounds (Theorems 3.1 and 3.4). Explicit worst-case weight matrices (Appendix C) attain the lower bound.
  • Consequence. Factorized AdaBoost.MH reaches zero training error within ⌈18log⁡(nK)/δ2⌉+1\lceil 18 \log(nK)/\delta^2 \rceil + 1 rounds, versus ⌈2log⁡(nK)/δ2⌉+1\lceil 2 \log(nK)/\delta^2 \rceil + 1 for AdaBoost.MH, so the overhead is a universal constant.

The paper is purely theoretical and contains no experiments.

Critical strengths

1. It settles the quantity behind an open problem, with matching bounds. Kégl (2014a) asked whether wΣ′w'_\Sigma has a lower bound that doesn't depend on nn. Zou et al. (2024) gave a positive bound, but it still shrinks as nn and KK grow. This paper finds the exact value of Wn,K\mathfrak{W}_{n,K} and gives explicit worst-case examples that hit it, so this quantity can't be improved any further. The practical impact is that factorized weak learners need at most a constant factor more rounds (9 in the worst case) to reach zero training error, instead of the min⁡{n2,2K}\min\lbrace n^2, 2K \rbrace factor allowed by earlier work. For example, with n=K=1000n = K = 1000 the old guarantee allowed roughly 2000 times more rounds. This is the main reason I'm leaning towards acceptance.

2. The proofs are simple, self-contained, and easy to check. The key steps check out:

  • the conditional expectations E[vj∣vc=±1]=∓1/(K−1)\mathbb{E}[v_j \mid v_c = \pm 1] = \mp 1/(K-1) for balanced vote vectors and ∓1/K\mp 1/K for nearly balanced ones (Lemmas 4.2–4.3);
  • the optimization over the true-class mass ρ\rho that gives CKC_K;
  • the column-merging step in Appendix B.2, which keeps wΣ′w'_\Sigma exactly the same;
  • both worst-case constructions in Appendix C;
  • the case analysis in Appendix D that puts the bounds together.

Small cases can also be checked by hand. For example, with n=2n = 2 and K≥3K \ge 3, every vote vector on the C.2 construction gives exactly 0.5=C30.5 = C_3. The "effective class number" n+1n+1 also has a nice intuitive explanation: label columns that no example uses can all be merged into one column that's always false. Because of all this, the result is easy to trust and to build on.

Critical weaknesses

1. The scope is a bit narrow. What the paper gives us is the exact value of one constant in the training-error analysis of one particular boosting algorithm. To be fair, that's exactly what Kégl's open problem asked, and the answer is final. But it doesn't go beyond that: there's nothing on margins or generalization, and there are no numbers at all. Even a small brute-force table of Wn,K\mathfrak{W}_{n,K} for small (n,K)(n, K), or a plot of the actual wΣ′w'_\Sigma during real runs, would help show whether the gap between the old and new bounds matters in practice. Related work is also only in the appendix, with 7 references. It would help to place the result next to other multi-class weak-learning conditions (e.g., Mukherjee & Schapire, JMLR 2013), especially for readers outside boosting theory.

2. The "same convergence rate" claim needs a couple of caveats. The title, abstract, intro (lines 109–111) and conclusion (lines 472–474) say the result holds "under the same empirical weak learning condition" as AdaBoost.MH. I think two things should be spelled out:

  • (a) What the base learner has to do. Theorem 3.5 shows a good vote vector always exists, but Eq. (3.9) also needs every round to actually return a pair (v,φ)(v, \varphi) with edge at least δWn,K\delta \mathfrak{W}_{n,K}. That works if the base learner picks (v,φ)(v, \varphi) together to maximize the edge. This is easy when φ\varphi is searched exhaustively, because for a fixed φ\varphi the best vote is just vj=sign(∑iWijYijφ(xi))v_j = \mathrm{sign}\big(\sum_i W_{ij} Y_{ij} \varphi(x_i)\big). But it isn't guaranteed if vv is fixed some other way first and φ\varphi is fit afterwards. One sentence saying this would make the claim precise.
  • (b) "Same condition." In Eq. (2.9), Assumption 2.1 is applied to pseudo-labels yi′y'_i that depend on W(t)W^{(t)} and vv, so they change from round to round. AdaBoost.MH only needs it for the fixed labels YY. The δ\delta is defined the same way, but the binary problems it has to hold on aren't the same. This setup comes from Kégl (2014a) and Zou et al. (2024), so I don't hold it against this paper, but I'd soften the "same condition" wording.

To be clear, neither point affects whether the theorems are correct. They're about how the main claim is worded.

Minor issues:

  • Conclusion (lines 469–476). It states the older, non-matching bounds from Theorem 3.1, max⁡{1/n,CK}≤Wn,K≤Cmin⁡{n,K}\max\lbrace 1/n, C_K \rbrace \le \mathfrak{W}_{n,K} \le C_{\min\lbrace n,K \rbrace}, instead of the exact result from Theorem 3.5. That doesn't fit with the claim right after it that the paper "closes the remaining gap." It also oversells a bit: the paper settles Wn,K\mathfrak{W}_{n,K}, but saying it "supports their use as a structured alternative to one-against-all weak rules" goes further than a training-error result with no experiments can back up.
  • "Conjecture." The effective class number is called a "conjecture" (lines 107 and 326–327), but Theorems 3.3–3.4 actually prove it.
  • Section 4 only sketches the non-tight lower bound. A short sketch of the merging argument (B.2) and the C.2 construction would be more useful, since those are what make the result exact.
  • Slowdown factor. The intro (line 085) says min⁡{n2,K}\min\lbrace n^2, K \rbrace, but Eq. (3.8) says min⁡{n2,2K}\min\lbrace n^2, 2K \rbrace.
  • Typos. In Appendix C.2, Zi(v)=((n+1)vi−2V−4u)/(nD)Z_i(v) = ((n+1)v_i - 2V - 4u)/(nD) should have (n+2)vi(n+2)v_i, which is what the next line uses. In Section 2, f(T)(x)=∑t=1Th(T)(x)f^{(T)}(x) = \sum_{t=1}^T h^{(T)}(x) should use h(t)h^{(t)}. In the title of Assumption 2.1 (line 196), "learing" should be "learning".
  • AI Use Statement. It says AI gave "proof ideas" for Theorems 3.3–3.4, but also says AI wasn't used to come up with claims or help with proofs. These two statements should be made consistent.
Questions for authors

Clarification questions (the answers could change my assessment):

  1. What exactly does the base learner need to do? For Eq. (3.9) to hold, each round has to return a pair (v,φ)(v, \varphi) with edge at least δWn,K\delta \mathfrak{W}_{n,K}. Is the assumption that the base learner maximizes the edge jointly over (v,φ)(v, \varphi), with vv set in closed form, vj=sign(∑iWijYijφ(xi))v_j = \mathrm{sign}\big(\sum_i W_{ij} Y_{ij} \varphi(x_i)\big), for each candidate φ\varphi? Does the guarantee still hold for base learners that fix vv first (or pick it heuristically) and then fit φ\varphi, for example trees trained on the pseudo-labelled sample? Related to this: in what sense is the weak-learning condition "the same" as for AdaBoost.MH, given that in Eq. (2.9) it is applied to pseudo-labels that change every round? A clear statement of both points in the paper would make me more comfortable with the headline claim.

  2. Do the worst cases actually happen? The bad weight matrices in Appendix C are built by an adversary. Can weights like these actually come up when running Factorized AdaBoost.MH from the uniform start Wij=1/(nK)W_{ij} = 1/(nK)? If not, is the constant along real runs better than 1/31/3? This would tell us whether the exact value matters in practice or only for the worst case.

  3. Any numerical sanity check? Have you checked Wn,K=Cmin⁡{n+1,K}\mathfrak{W}_{n,K} = C_{\min\lbrace n+1, K \rbrace} numerically for small (n,K)(n, K), for example by brute force over all vote vectors? A small table would add confidence at very little cost.

Reviewer_5niTOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
1
Soundness
2
Read review
Paper summary

The paper revisits the convergence of Factorized AdaBoost.MH. This multiclass classifier uses a set of base classifiers where the label dependence is carried by a vote vector combined with a binary classifier that is shared across all classes. Its training convergence depends on the choice of the vote vector that has sufficiently large induced binary weight mass. Previous work addressed this problem with a lower bound which includes a dimension-dependent slowdown, which is an artifact of their lower bound. This paper sharpens the combinatorial step and provides an exact characterization of the bound such that Factorized AdaBoost.MH achieves the same boosting-type convergence rate as AdaBoost.MH up to a universal constant factor. It thus removes the previous dependence on the number of samples and classes in the number of boosting rounds. The proof separates the lower-bound into two complementary choices of vote vector.

This is a purely theoretical ML paper, there are no experimental results. Only theorems and proofs of the bound.

Critical strengths

The existing lower bound of AdaBoost.HM is criticised for a possible slowdown depending on the number of samples or classes. The paper removes a dimension-dependent gap in the convergence guarantee. It shows that the new sufficient number of boosting rounds has no additional dependence on these numbers. This reduces the complexity of boosting rounds making it comparable to standard AdaBoost.MH up to a universal constant.

Critical weaknesses

The paper is difficult to follow even for ML practitioners. This is not to say that it is unnecessarily complicated since as a theory paper it can reasonably assume familiarity with boosting and convergence proofs. The accessibility could be improved with a clearer explanation of the induced-weight quantity, why it controls convergence, and how the proof’s components fit together.

The related work section is in the appendix rather than the main paper and it is in a form of a high level introduction to this area of work rather than a critical positioning of the contribution. There is one closely related paper from 2024 that the bounds are compared against and demonstrated to be not tight, otherwise there is very sparse related literature from 1999 to 2019, 7 references in total. This raises a question whether the distinction from prior works, in particular on multiclass boosting from Schapire, is sufficiently explained.

The improvement in round complexity is clear, but its implications for overall training time is not. That is, the paper does not establish the computational cost of obtaining the vote vectors required by this guarantee, or whether the practical factorized learner achieves the guaranteed edge. It is also not clear that this proof may lead to a more efficient vote selection approach.

Questions for authors

The main questions are related to weaknesses pointed out above regarding the significance of the contributions and their positioning with respect to other works and the implications for practical training.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.