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 $\mathbf{h}(x)=\alpha \mathbf{v}\phi (x)$, where a single binary classifier $\phi$ is shared across all classes and the label dependence is carried by a vote vector $$\begin{gathered} \mathbf{v}\in \\ {\pm 1 \\ }^K \end{gathered}$$. 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 $$\begin{gathered} \max \\ 1/n,1/\sqrt{2K} \end{gathered}$$, 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 ${\mathfrak{W}}_{n,K}$ governing the factorized edge, we prove $$\begin{gathered} {\mathfrak{W}}_{n,K}=C_{\min \\ n+1,K \\ } \end{gathered}$$, where $C_q=1$ for $q=1$, $C_q=q/(3q-4)$ for even $q\ge 2$, and $C_q=(q+1)/(3q-1)$ for odd $q\ge 2$. Since $C_q\downarrow 1/3$, our bounds show that ${\mathfrak{W}}_{n,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.