論文の概要: Optimal Parallelization of Boosting

• arxiv url: http://arxiv.org/abs/2408.16653v1
• Date: Thu, 29 Aug 2024 15:56:22 GMT
• ステータス: 処理完了
• システム内更新日: 2024-08-30 13:12:46.425124
• Title: Optimal Parallelization of Boosting
• Title（参考訳）: ブースティングの最適並列化
• Authors: Arthur da Cunha, Mikael Møller Høgsgaard, Kasper Green Larsen,
• Abstract要約: Boostingの並列複雑性に関する最近の研究は、トレーニングラウンド数$p$とラウンドあたりの並列処理総数$t$とのトレードオフに関して、強い低い境界を確立している。 これらの進歩にもかかわらず、理論的な下界とこれらのアルゴリズムのトレードオフ空間の多くにおける性能の間には大きなギャップが残っている。 本研究では,弱強学習者の並列的複雑性に対する改善された下位境界と,これらの境界値が対数係数までの範囲で比較可能な並列ブースティングアルゴリズムの両方を提供することで,このギャップを解消する。
• 参考スコア（独自算出の注目度）: 10.985323882432086
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Recent works on the parallel complexity of Boosting have established strong lower bounds on the tradeoff between the number of training rounds $p$ and the total parallel work per round $t$. These works have also presented highly non-trivial parallel algorithms that shed light on different regions of this tradeoff. Despite these advancements, a significant gap persists between the theoretical lower bounds and the performance of these algorithms across much of the tradeoff space. In this work, we essentially close this gap by providing both improved lower bounds on the parallel complexity of weak-to-strong learners, and a parallel Boosting algorithm whose performance matches these bounds across the entire $p$ vs.~$t$ compromise spectrum, up to logarithmic factors. Ultimately, this work settles the true parallel complexity of Boosting algorithms that are nearly sample-optimal.
• Abstract（参考訳）: Boostingの並列複雑性に関する最近の研究は、トレーニングラウンド数$p$とラウンドあたりの並列処理総数$t$とのトレードオフに関して、強い低い境界を確立している。 これらの研究は、このトレードオフの異なる領域に光を放つ非常に非自明な並列アルゴリズムも提示している。 これらの進歩にもかかわらず、理論的な下界とこれらのアルゴリズムのトレードオフ空間の多くにおける性能の間には大きなギャップが残っている。 本研究では,弱強学習者の並列複雑性に対する低境界の改善と,これらバウンダリ全体の性能を比較検討した並列ブースティングアルゴリズムを両立させることにより,このギャップを解消する。 ～$t$妥協スペクトル、対数因子まで。 最終的に、この研究はサンプル最適化に近いブースティングアルゴリズムの真の並列複雑性を解決した。

関連論文リスト

• Provably Faster Algorithms for Bilevel Optimization via Without-Replacement Sampling [96.47086913559289]
  勾配に基づくアルゴリズムはバイレベル最適化に広く用いられている。 本研究では,より高速な収束率を実現する非置換サンプリングに基づくアルゴリズムを提案する。 合成および実世界の両方のアプリケーションに対してアルゴリズムを検証する。
  論文  参考訳（メタデータ） (2024-11-07T17:05:31Z)
• Improved Parallel Algorithm for Non-Monotone Submodular Maximization under Knapsack Constraint [0.0]
  本研究は,knapsack制約下での非モジュラーサイズに対する効率的な並列アルゴリズムを提案する。 我々のアルゴリズムは, 既存の並列処理を 8+epsilon$ から 7+epsilon$ に改良し, 適応複雑性を$O(log n)$ にする。
  論文  参考訳（メタデータ） (2024-09-06T17:17:52Z)
• Parallel Algorithms Align with Neural Execution [7.535219325248997]
  しかし並列アルゴリズムは計算能力を最大限に活用できるため、実行すべきレイヤは少ない。 このことは、CLRSフレームワーク上のシーケンシャルなコンポーネントに対して、検索、ソート、および強力な接続されたコンポーネントの並列実装を比較する際に観察されるように、トレーニング時間を劇的に短縮します。
  論文  参考訳（メタデータ） (2023-07-08T21:28:20Z)
• Accelerated First-Order Optimization under Nonlinear Constraints [73.2273449996098]
  我々は、制約付き最適化のための一階アルゴリズムと非滑らかなシステムの間で、新しい一階アルゴリズムのクラスを設計する。 これらのアルゴリズムの重要な性質は、制約がスパース変数の代わりに速度で表されることである。
  論文  参考訳（メタデータ） (2023-02-01T08:50:48Z)
• Optimal Algorithms for Stochastic Complementary Composite Minimization [55.26935605535377]
  統計学と機械学習における正規化技術に触発され,補完的な複合化の最小化について検討した。 予測と高い確率で、新しい過剰なリスク境界を提供する。 我々のアルゴリズムはほぼ最適であり、このクラスの問題に対して、新しいより低い複雑性境界によって証明する。
  論文  参考訳（メタデータ） (2022-11-03T12:40:24Z)
• SYNTHESIS: A Semi-Asynchronous Path-Integrated Stochastic Gradient Method for Distributed Learning in Computing Clusters [7.968142741470549]
  ulstochastic gradulient ulsearchは、同期および非同期分散学習アルゴリズムの制限を克服するために開発された。 algnameアルゴリズムは(O(sqrtNepsilon-2(Delta+1) d+N))と(O(sqrtNepsilon-2(+1) d+N))を持つ (エプシロン)分散共有メモリアーキテクチャにおける非デルタ学習の定常点
  論文  参考訳（メタデータ） (2022-08-17T17:42:33Z)
• Best of Both Worlds: Practical and Theoretically Optimal Submodular Maximization in Parallel [17.462968952951883]
  主アルゴリズムは、独立した関心を持つ可能性のある2つのコンポーネントから組み立てられる。 LINEARSEQの変種は、文献のどのアルゴリズムよりも小さい$O(log(n))$の適応複雑性を持つ。
  論文  参考訳（メタデータ） (2021-11-15T17:10:40Z)
• Provably Faster Algorithms for Bilevel Optimization [54.83583213812667]
  バイレベル最適化は多くの重要な機械学習アプリケーションに広く適用されている。 両レベル最適化のための2つの新しいアルゴリズムを提案する。 両アルゴリズムが$mathcalO(epsilon-1.5)$の複雑さを達成し,既存のアルゴリズムを桁違いに上回っていることを示す。
  論文  参考訳（メタデータ） (2021-06-08T21:05:30Z)
• Fast Parallel Algorithms for Euclidean Minimum Spanning Tree and Hierarchical Spatial Clustering [6.4805900740861]
  HDBSCAN$*$のための私達のアルゴリズムの仕事そしてスペースを減らすために十分分離の新しい概念を導入します。 我々のアルゴリズムは理論的に効率的であることを示す: 彼らは逐次対応の作業(操作数)と多対数深さ(並列時間)を持っている。 48コアマシンを用いた大規模実世界および合成データセットの実験により、我々の最速のアルゴリズムは11.13-55.89x、既存の並列アルゴリズムを少なくとも桁違いに上回った。
  論文  参考訳（メタデータ） (2021-04-02T16:05:00Z)
• On Effective Parallelization of Monte Carlo Tree Search [51.15940034629022]
  モンテカルロ木探索(MCTS)は、探索木を構築するためにかなりの数のロールアウトを必要とするため、計算コストがかかる。 効果的な並列MCTSアルゴリズムを設計する方法は、体系的に研究されておらず、まだよく分かっていない。 我々は,より効率的な並列MCTSアルゴリズムの設計に,提案する必要条件をどのように適用できるかを実証する。
  論文  参考訳（メタデータ） (2020-06-15T21:36:00Z)
• On the Dual Formulation of Boosting Algorithms [92.74617630106559]
  AdaBoost,LogitBoost,Soft-marginBoostのラグランジュ問題は、すべて一般化されたヒンジ損失エントロピーの双対問題であることを示す。 これらのブースティングアルゴリズムの2つの問題を見て、より良いマージン分布を維持するという観点から、ブースティングの成功を理解することができることを示す。
  論文  参考訳（メタデータ） (2009-01-23T02:14:42Z)

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

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