論文の概要: The Cost of Parallelizing Boosting

• arxiv url: http://arxiv.org/abs/2402.15145v1
• Date: Fri, 23 Feb 2024 07:03:52 GMT
• ステータス: 処理完了
• システム内更新日: 2024-02-26 15:32:27.243386
• Title: The Cost of Parallelizing Boosting
• Title（参考訳）: 並列化ブースティングのコスト
• Authors: Xin Lyu, Hongxun Wu, Junzhao Yang
• Abstract要約: 本研究は,学習用弱強化アルゴリズムの並列化コストについて検討する。 ブースティングの"軽い"並列化でさえ、トレーニングの複雑さが指数関数的に爆発的に大きくなる必要があることを示す。
• 参考スコア（独自算出の注目度）: 1.9235143628887907
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the cost of parallelizing weak-to-strong boosting algorithms for learning, following the recent work of Karbasi and Larsen. Our main results are two-fold: - First, we prove a tight lower bound, showing that even "slight" parallelization of boosting requires an exponential blow-up in the complexity of training. Specifically, let $\gamma$ be the weak learner's advantage over random guessing. The famous \textsc{AdaBoost} algorithm produces an accurate hypothesis by interacting with the weak learner for $\tilde{O}(1 / \gamma^2)$ rounds where each round runs in polynomial time. Karbasi and Larsen showed that "significant" parallelization must incur exponential blow-up: Any boosting algorithm either interacts with the weak learner for $\Omega(1 / \gamma)$ rounds or incurs an $\exp(d / \gamma)$ blow-up in the complexity of training, where $d$ is the VC dimension of the hypothesis class. We close the gap by showing that any boosting algorithm either has $\Omega(1 / \gamma^2)$ rounds of interaction or incurs a smaller exponential blow-up of $\exp(d)$. -Complementing our lower bound, we show that there exists a boosting algorithm using $\tilde{O}(1/(t \gamma^2))$ rounds, and only suffer a blow-up of $\exp(d \cdot t^2)$. Plugging in $t = \omega(1)$, this shows that the smaller blow-up in our lower bound is tight. More interestingly, this provides the first trade-off between the parallelism and the total work required for boosting.
• Abstract（参考訳）: 本稿では,Karbasi と Larsen の最近の研究に続き,学習のための弱強強化アルゴリズムの並列化コストについて検討する。 第一に、我々は厳密な下界を証明し、ブースティングの"明るい"並列化でさえ、トレーニングの複雑さを指数関数的に膨らませる必要があることを示します。 具体的には、$\gamma$をランダムな推測よりも弱い学習者の利点とする。 有名な \textsc{AdaBoost} アルゴリズムは、各ラウンドが多項式時間で走るような$\tilde{O}(1 / \gamma^2)$ラウンドで弱い学習者と相互作用することで正確な仮説を生成する。 どのようなブースティングアルゴリズムも$\omega(1 / \gamma)$ rounds の弱い学習者と相互作用するか、あるいは$\exp(d / \gamma)$ のブローアップをトレーニングの複雑さで発生させるかのいずれかで、$d$ は仮説クラスのvc次元である。 任意のブースティングアルゴリズムが$\Omega(1 / \gamma^2)$の相互作用のラウンドを持つか、より小さな指数的な$\exp(d)$を発生させることでギャップを埋める。 -下界を補完すると、$\tilde{O}(1/(t \gamma^2))$ rounds のブーピングアルゴリズムが存在し、$\exp(d \cdot t^2)$ の爆発しか起こらないことを示す。 これは、$t = \omega(1)$を差し込むと、下限の小さなブローアップがきついことを示す。 より興味深いことに、これは並列性とブースティングに必要な全作業の間の最初のトレードオフを提供する。

関連論文リスト

• The Sample Complexity of Smooth Boosting and the Tightness of the Hardcore Theorem [53.446980306786095]
  スムースブースターは任意の例にあまり重みを付けない分布を生成する。 もともとは耐雑音性のために導入されたが、そのようなブースターは微分プライバシー、軽度、量子学習理論にも応用されている。
  論文  参考訳（メタデータ） (2024-09-17T23:09:25Z)
• Learning a Single Neuron with Adversarial Label Noise via Gradient Descent [50.659479930171585]
  モノトン活性化に対する $mathbfxmapstosigma(mathbfwcdotmathbfx)$ の関数について検討する。 学習者の目標は仮説ベクトル $mathbfw$ that $F(mathbbw)=C, epsilon$ を高い確率で出力することである。
  論文  参考訳（メタデータ） (2022-06-17T17:55:43Z)
• Threshold Phenomena in Learning Halfspaces with Massart Noise [56.01192577666607]
  ガウス境界の下でのマスアートノイズ付きmathbbRd$におけるPAC学習ハーフスペースの問題について検討する。 この結果は,Massartモデルにおける学習ハーフスペースの複雑さを定性的に特徴づけるものである。
  論文  参考訳（メタデータ） (2021-08-19T16:16:48Z)
• Quantum learning algorithms imply circuit lower bounds [7.970954821067043]
  量子アルゴリズムの設計と回路下界の一般接続を確立する。 我々の証明は、学習理論、擬似ランダム性、計算複雑性に関するいくつかの研究に基づいている。
  論文  参考訳（メタデータ） (2020-12-03T14:03:20Z)
• Impact of Representation Learning in Linear Bandits [83.17684841392754]
  本研究では,表現学習が帯域幅問題の効率性を向上させる方法について検討する。 我々は,$widetildeO(TsqrtkN + sqrtdkNT)$ regretを達成する新しいアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-10-13T16:35:30Z)
• Near-Optimal Reinforcement Learning with Self-Play [50.29853537456737]
  我々は,直接の監督なしに自己対決で最適な政策を学習するセルフプレイアルゴリズムに焦点をあてる。 本稿では,サンプル複雑性を$tildemathcalO(SAB)$,サンプル複雑性を$tildemathcalO(S(A+B)$とする新しいemphNash Vラーニングアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-06-22T05:00:13Z)
• Sample Efficient Reinforcement Learning via Low-Rank Matrix Estimation [30.137884459159107]
  連続状態と行動空間を用いた強化学習において,Q$関数を効率よく学習する方法を考える。 我々は、$epsilon$-Schmidt $Q$-functionと$widetildeO(frac1epsilonmax(d1, d_2)+2)$のサンプル複雑性を求める単純な反復学習アルゴリズムを開発する。
  論文  参考訳（メタデータ） (2020-06-11T00:55:35Z)
• Model-Free Reinforcement Learning: from Clipped Pseudo-Regret to Sample Complexity [59.34067736545355]
  S$状態、$A$アクション、割引係数$gamma in (0,1)$、近似しきい値$epsilon > 0$の MDP が与えられた場合、$epsilon$-Optimal Policy を学ぶためのモデルなしアルゴリズムを提供する。 十分小さな$epsilon$の場合、サンプルの複雑さで改良されたアルゴリズムを示す。
  論文  参考訳（メタデータ） (2020-06-06T13:34:41Z)
• Quantum Boosting [8.93449755281201]
  ブースティングは、弱い不正確な機械学習アルゴリズムを強力な正確な学習アルゴリズムに変換するテクニックである。 量子技術が古典的AdaBoostの時間複雑性をいかに改善できるかを示す。
  論文  参考訳（メタデータ） (2020-02-12T15:47:54Z)

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

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