arXiv:2608.01091cs.LG2026-08

因子化提升算法收敛速度与原始方法一致,突破了此前的维度依赖瓶颈。

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

  • 通过共享二分类器并用投票向量编码类别依赖,实现结构化提升
  • 证明因子化边界的最小最大值恒为常数阶,不随样本数或类别数变化
  • 理论证实其收敛率与原始AdaBoost.MH相同,适合高维多分类任务

AdaBoost.MH将多分类问题转化为一系列二分类子问题,在弱学习条件下具有经典的提升型收敛保证。其结构化变体因子化AdaBoost.MH采用形式为 $\mathbf{h}(x)=α\mathbf{v} \bmφ(x)$ 的基分类器,其中单一二分类器 $\bmφ$ 跨所有类别共享,类别依赖由投票向量 $\mathbf{v} \in\{\pm1\}^K$ 承载。该结构算法友好且实践中表现更优,但其收敛性依赖于能否始终选择具有足够大诱导二分类权重质量的投票向量。先前工作给出下界 $\max\{1/n,1/\sqrt{2K}\}$,仍存在相对于原始分析的维度相关减速。本文对此组合步骤进行优化:对控制因子化边界的极小极大量 $\mathfrak{W}_{n,K}$,我们证明 $\mathfrak{W}_{n,K} = C_{\min\{n+1,K\}}$,其中 $C_q=1$(当 $q=1$),$C_q=q/(3q-4)$(当 $q\ge2$ 且偶),$C_q=(q+1)/(3q-1)$(当 $q\ge2$ 且奇)。由于 $C_q\downarrow 1/3$,我们的界限表明 $\mathfrak{W}_{n,K}=Θ(1)$ 在 $n$ 与 $K$ 上统一成立。因此,因子化AdaBoost.MH在至多一个全局常数因子内实现了与AdaBoost.MH相同的提升型收敛速率,消除了此前建议的对 $n$ 或 $K$ 的额外依赖,从而减少了提升轮次数量的额外增长。

原文摘要 · Abstract (English)

{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)=α\mathbf{v} \bmφ(x)$, where a single binary classifier $\bmφ$ 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 {AdaBoost.MH} analysis. In this paper, we sharpen this combinatorial step. For the minimax quantity $\mathfrak{W}_{n,K}$ governing the factorized edge, we prove $\mathfrak{W}_{n,K} = C_{\min\{n+1,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}=Θ(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.

提升算法多分类收敛分析

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。