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

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

Abstract:this http URL 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 this http URL, uses base classifiers of the form $\mathbf{h}(x)=\alpha \mathbf{v} \bm{\varphi}(x)$, where a single binary classifier $\bm{\varphi}$ is shared across all classes and the label dependence is carried by a vote vector $\mathbf{v} \in\{\pm1\}^K$. 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 $\max\{1/n,1/\sqrt{2K}\}$, which still leaves a dimension-dependent slowdown relative to the original this http URL analysis. In this paper, we sharpen this combinatorial step. For the minimax quantity $\mathfrak{W}_{n,K}$ governing the factorized edge, we prove $\max\{1/n,C_K\}\le\mathfrak{W}_{n,K}\le C_{\min\{n,K\}}$, where $C_q=1$ for $q=1$, $C_q=q/(3q-4)$ for even $q\ge2$, and $C_q=(q+1)/(3q-1)$ for odd $q\ge2$. Since $C_q\downarrow 1/3$, our bounds show that $\mathfrak{W}_{n,K}=\Theta(1)$ uniformly over $n$ and $K$. Consequently, Factorized this http URL achieves the same boosting-type convergence rate as this http URL up to a universal constant factor, removing the previously suggested additional dependence on $n$ or $K$ in the number of boosting rounds.

Machine Learning (cs.LG)

arXiv:2608.01091 [cs.LG]

(or arXiv:2608.01091v1 [cs.LG] for this version)

https://doi.org/10.48550/arXiv.2608.01091 Focus to learn more arXiv-issued DOI via DataCite (pending registration)

arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.

Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.

Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.