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

• URL: http://arxiv.org/abs/2608.01091v2
• Date: Sat, 08 Aug 2026 14:35:15 GMT
• Title: Factorized AdaBoost.MH Achieves the Same Convergence Rate as AdaBoost.MH
• Abstract summary: A more structured variant, Factorized AdaBoost.MH, uses base classifiers of the form $mathbfh(x)=mathbfv bmvarphi(x)$.<n>We show that Factorized AdaBoost.MH achieves the same boosting-type convergence rate as AdaBoost.MH up to a universal constant factor.
• Score: 11.157319736363823
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: {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{\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 {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.

Related papers

• Low-Rank Prompt Learning for Vision-Language Models with Fixed-Token Bases [11.437689514839333]
  We study a dense prompt matrix $mathbfPinmathbbRmtimes d$ trained from only a few examples per class.<n>We find that the token-side factor need not be learned at all.<n>In the CLIP prompt setting, the embedding-side coefficients carry the adaptation while the token basis can simply be fixed.
  arXiv  Detail & Related papers  (2026-09-08T21:26:37Z)
• Faster quantum linear system solver beyond the condition number [50.84794327094274]
  We present two quantum algorithms that produce the normalized solution $|xrangle$ of linear system $Ax=| b rangle$ to accuracy $$ with complexity independent of the condition number $=lVert A-1rVert$.<n>Our filtering-based solver is extremely simple with a favorable runtime prefactor.
  arXiv  Detail & Related papers  (2026-07-08T17:49:40Z)
• Optimal Scalar Quantization for Matrix Multiplication: Closed-Form Density and Phase Transition [50.36362492608702]
  We study entrywise scalar quantization of two matrices prior to multiplication.<n>We obtain a closed-form optimal point density [ star(u) propto exp!left(-fracu26right)bigl( (1-2)+2u22bigr), qquad u=fracx_X,, and prove a correlation-driven phase transition.
  arXiv  Detail & Related papers  (2026-03-20T01:53:44Z)
• What Functions Does XGBoost Learn? [0.8657572235098258]
  We introduce an infinite-dimensional function class $mathcalFd, s_inftytextST$ that extends finite ensembles of bounded-depth regression trees.<n>We show that every of the XGBoost objective is also an equivalent penalized regression problem over $mathcalFd, s_infty-textST$ with penalty $Vd, s_infty-textXGB(cdot)$.<n>Our results provide the first rigorous characterization of the function space
  arXiv  Detail & Related papers  (2026-01-09T00:22:08Z)
• A New Rejection Sampling Approach to $k$-$\mathtt{means}$++ With Improved Trade-Offs [0.12289361708127876]
  We present a simple and effective rejection sampling based approach for speeding up $k$-$mathttmeans$++.<n>Our first method runs in time $tildeO(mathttnnz (mathcalX) + beta k2d)$ while still being $O(log k )$ competitive in expectation.<n>Our second method presents a new trade-off between computational cost and solution quality.
  arXiv  Detail & Related papers  (2025-02-04T08:05:34Z)
• Overcomplete Tensor Decomposition via Koszul-Young Flattenings [56.82556231289414]
  We give a new algorithm for decomposing an $n_times n times n_3$ tensor as the sum of a minimal number of rank-1 terms.<n>We show that an even more general class of degree-$d$s cannot surpass rank $Cn$ for a constant $C = C(d)$.
  arXiv  Detail & Related papers  (2024-11-21T17:41:09Z)
• In-depth Analysis of Low-rank Matrix Factorisation in a Federated Setting [21.002519159190538]
  We analyze a distributed algorithm to compute a low-rank matrix factorization on $N$ clients.<n>We obtain a global $mathbfV$ in $mathbbRd times r$ common to all clients and a local $mathbfUi$ in $mathbbRn_itimes r$.
  arXiv  Detail & Related papers  (2024-09-13T12:28:42Z)
• Provably learning a multi-head attention layer [55.2904547651831]
  Multi-head attention layer is one of the key components of the transformer architecture that sets it apart from traditional feed-forward models. In this work, we initiate the study of provably learning a multi-head attention layer from random examples. We prove computational lower bounds showing that in the worst case, exponential dependence on $m$ is unavoidable.
  arXiv  Detail & Related papers  (2024-02-06T15:39:09Z)
• A Normal Map-Based Proximal Stochastic Gradient Method: Convergence and Identification Properties [7.281869462071603]
  The proximal gradient method (PSGD) is one of the state-of-the-art approaches for composite-type problems.<n>In this paper, we present a simple variant of PSGD based on Robinsons map.
  arXiv  Detail & Related papers  (2023-05-10T01:12:11Z)
• On the speed of uniform convergence in Mercer's theorem [6.028247638616059]
  A continuous positive definite kernel $K(mathbf x, mathbf y)$ on a compact set can be represented as $sum_i=1infty lambda_iphi_i(mathbf x)phi_i(mathbf y)$ where $(lambda_i,phi_i)$ are eigenvalue-eigenvector pairs of the corresponding integral operator. We estimate the speed of this convergence in terms of the decay rate of eigenvalues and demonstrate that for $3m
  arXiv  Detail & Related papers  (2022-05-01T15:07:57Z)
• Fast Graph Sampling for Short Video Summarization using Gershgorin Disc Alignment [52.577757919003844]
  We study the problem of efficiently summarizing a short video into several paragraphs, leveraging recent progress in fast graph sampling. Experimental results show that our algorithm achieves comparable video summarization as state-of-the-art methods, at a substantially reduced complexity.
  arXiv  Detail & Related papers  (2021-10-21T18:43:00Z)
• On the Self-Penalization Phenomenon in Feature Selection [69.16452769334367]
  We describe an implicit sparsity-inducing mechanism based on over a family of kernels. As an application, we use this sparsity-inducing mechanism to build algorithms consistent for feature selection.
  arXiv  Detail & Related papers  (2021-10-12T09:36:41Z)
• Improved Regret Bounds for Online Submodular Maximization [10.089520556398575]
  We consider an online optimization problem where at each step $tin[T]$, the algorithm chooses an action $x_t$ from the fixed convex and compact domain set $mathcalK$. A utility function $f_t(cdot)$ is then revealed and the algorithm receives the payoff $f_t(x_t)$.
  arXiv  Detail & Related papers  (2021-06-15T02:05:35Z)
• Quantum Boosting [8.93449755281201]
  Boosting is a technique that converts a weak and inaccurate machine learning algorithm into a strong accurate learning algorithm. We show how quantum techniques can improve the time complexity of classical AdaBoost.
  arXiv  Detail & Related papers  (2020-02-12T15:47:54Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.