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

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.