論文の概要: Factorized AdaBoost.MH Achieves the Same Convergence Rate as AdaBoost.MH

• arxiv url: http://arxiv.org/abs/2608.01091v2
• Date: Sat, 08 Aug 2026 14:35:15 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-08-11 19:16:36.409149
• Title: Factorized AdaBoost.MH Achieves the Same Convergence Rate as AdaBoost.MH
• Title（参考訳）: AdaBoost.MHはAdaBoost.MHと同じ収束率を達成する
• Authors: Xin Zou, Jingyuan Xu,
• Abstract要約: より構造化された亜種である Factorized AdaBoost.MH は $mathbfh(x)=mathbfv bmvarphi(x)$ という形の基底分類器を使用する。 因子化 AdaBoost.MH は AdaBoost.MH と同じ加速型収束率を普遍定数係数まで達成することを示す。
• 参考スコア（独自算出の注目度）: 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.
• Abstract（参考訳）: AdaBoost.MH} は、マルチクラス分類をバイナリサブプロブレムの集合に還元し、弱い学習条件下で古典的なブースティング型収束保証を享受する。 より構造化された変数である Factorized {AdaBoost.MH} は $\mathbf{h}(x)=α\mathbf{v} \bm{\varphi}(x)$ という形の基底分類器を使用し、単一のバイナリ分類器 $\bm{\varphi}$ はすべてのクラスで共有され、ラベル依存は投票ベクトル $\mathbf{v} \in\{\pm1\}^K$ によって運ばれる。 この因子化はアルゴリズム的に魅力的であり、実際はより良い性能を達成するが、その収束は、十分に大きな誘導二分重質量を持つ投票ベクトルを常に選択できるかどうかに依存する。 以前の研究により、この問題は$\max\{1/n,1/\sqrt{2K}\}$で解決された。 本稿では,この組み合わせのステップを整理する。 極小マックス量 $\mathfrak{W}_{n,K} に対して、分解されたエッジを管理する$\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$, $C_q=(q+1)/(3q-1)$ for odd $q\ge2$とする。 C_q\downarrow 1/3$ であるから、この境界は$\mathfrak{W}_{n,K}=\(1)$ が$n$ と$K$ に一様であることを示している。 その結果、Factized {AdaBoost.MH} は {AdaBoost.MH} と同じブーピング型収束率を普遍定数係数まで達成し、前述したブースティングラウンド数において$n$または$K$への追加依存を取り除く。

関連論文リスト

• Optimal Scalar Quantization for Matrix Multiplication: Closed-Form Density and Phase Transition [50.36362492608702]
  乗算前の2つの行列のエントリーワイズスカラー量子化について検討した。 我々は、閉形式の最適点密度 [ star(u) propto exp!left(-fracu26right)bigl( (1-2)+2u22bigr), qquad u=fracx_X を求め、相関駆動相転移を証明した。
  論文  参考訳（メタデータ） (2026-03-20T01:53:44Z)
• What Functions Does XGBoost Learn? [0.8657572235098258]
  無限次元関数クラス $mathcalFd, s_inftytextST$ を導入する。 XGBoost の目的の全ては、$mathcalFd, s_infty-textST$ のペナルティ$Vd, s_infty-textXGB(cdot)$ よりも同等のペナル化回帰問題であることを示す。 我々の結果は関数空間の最初の厳密な特徴を与える。
  論文  参考訳（メタデータ） (2026-01-09T00:22:08Z)
• A New Rejection Sampling Approach to $k$-$\mathtt{means}$++ With Improved Trade-Offs [0.12289361708127876]
  単純かつ効果的なリジェクションサンプリングに基づくアプローチで,$k$-$mathttmeans$++ を高速化する。 最初のメソッドは $tildeO(mathttnnz (mathcalX) + beta k2d)$ で実行されます。 第2の手法は,計算コストと解品質の新たなトレードオフを示す。
  論文  参考訳（メタデータ） (2025-02-04T08:05:34Z)
• Overcomplete Tensor Decomposition via Koszul-Young Flattenings [56.82556231289414]
  最小ランク1項の和として$n_times n times n_3$ tensorを分解する新しいアルゴリズムを与える。 次数-d$s のさらに一般的なクラスは、定数 $C = C(d)$ に対して階数 $Cn$ を超えることができないことを示す。
  論文  参考訳（メタデータ） (2024-11-21T17:41:09Z)
• Provably learning a multi-head attention layer [55.2904547651831]
  マルチヘッドアテンション層は、従来のフィードフォワードモデルとは分離したトランスフォーマーアーキテクチャの重要な構成要素の1つである。 本研究では,ランダムな例から多面的注意層を実証的に学習する研究を開始する。 最悪の場合、$m$に対する指数的依存は避けられないことを示す。
  論文  参考訳（メタデータ） (2024-02-06T15:39:09Z)
• A Normal Map-Based Proximal Stochastic Gradient Method: Convergence and Identification Properties [7.281869462071603]
  近位勾配法 (PSGD) は複合型問題に対する最先端手法の1つである。 本稿では,ロビンソン写像に基づくPSGDの簡易な変種について述べる。
  論文  参考訳（メタデータ） (2023-05-10T01:12:11Z)
• Fast Graph Sampling for Short Video Summarization using Gershgorin Disc Alignment [52.577757919003844]
  高速グラフサンプリングの最近の進歩を利用して,短い動画を複数の段落に効率よく要約する問題について検討する。 実験結果から,本アルゴリズムは最先端の手法と同等の映像要約を実現し,複雑さを大幅に低減した。
  論文  参考訳（メタデータ） (2021-10-21T18:43:00Z)
• On the Self-Penalization Phenomenon in Feature Selection [69.16452769334367]
  カーネル群に基づく暗黙の空間性誘導機構について述べる。 アプリケーションとしては、この疎結合誘導機構を使用して、特徴選択に一貫性のあるアルゴリズムを構築します。
  論文  参考訳（メタデータ） (2021-10-12T09:36:41Z)
• Quantum Boosting [8.93449755281201]
  ブースティングは、弱い不正確な機械学習アルゴリズムを強力な正確な学習アルゴリズムに変換するテクニックである。 量子技術が古典的AdaBoostの時間複雑性をいかに改善できるかを示す。
  論文  参考訳（メタデータ） (2020-02-12T15:47:54Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。