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

arXiv: https://arxiv.org/abs/2608.01091 · HTML: https://mlsanity.com/paper/2608.01091/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 3 of its 9 references that are in the map.
- First posted on arXiv 2 Aug 2026.

## Builds on (most cited first, 3 of 3)

- [VC Classes are Adversarially Robustly Learnable, but Only Improperly](https://mlsanity.com/paper/1902.04217/) (2019)
- [The Optimal Sample Complexity of PAC Learning](https://mlsanity.com/paper/1507.00473/) (2015)
- [The return of AdaBoost.MH: multi-class Hamming trees](https://mlsanity.com/paper/1312.6086/) (2013)

## Abstract (arXiv)

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 h(x)=α v bmvarphi(x), where a single binary classifier bmvarphi is shared across all classes and the label dependence is carried by a vote vector v ∈±1K. 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 max1/n,1/√2K, which still leaves a dimension-dependent slowdown relative to the original AdaBoost.MH analysis. In this paper, we sharpen this combinatorial step. For the minimax quantity mathfrakWn,K governing the factorized edge, we prove mathfrakWn,K = C_minn+1,K, where Cq=1 for q=1, Cq=q/(3q-4) for even q≥2, and Cq=(q+1)/(3q-1) for odd q≥2. Since Cqdownarrow 1/3, our bounds show that mathfrakWn,K=Theta(1) uniformly over n and K. 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 n or K in the number of boosting rounds.