論文の概要: FastDOG: Fast Discrete Optimization on GPU

• arxiv url: http://arxiv.org/abs/2111.10270v1
• Date: Fri, 19 Nov 2021 15:20:10 GMT
• ステータス: 処理完了
• システム内更新日: 2021-11-22 15:48:48.451515
• Title: FastDOG: Fast Discrete Optimization on GPU
• Title（参考訳）: FastDOG: GPUの高速離散最適化
• Authors: Ahmed Abbas, Paul Swoboda
• Abstract要約: 本稿では,構造化予測で発生する0-1整数線形プログラムを解くために,並列に並列なラグランジュ分解法を提案する。 我々の原始的アルゴリズムと双対アルゴリズムは、サブプロブレムとBDDに対する最適化の同期をほとんど必要としません。 問題に依存しない状態で、最先端の特殊アルゴリズムに近づいたり、優れていたりします。
• 参考スコア（独自算出の注目度）: 23.281726932718232
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We present a massively parallel Lagrange decomposition method for solving 0-1 integer linear programs occurring in structured prediction. We propose a new iterative update scheme for solving the Lagrangean dual and a perturbation technique for decoding primal solutions. For representing subproblems we follow Lange et al. (2021) and use binary decision diagrams (BDDs). Our primal and dual algorithms require little synchronization between subproblems and optimization over BDDs needs only elementary operations without complicated control flow. This allows us to exploit the parallelism offered by GPUs for all components of our method. We present experimental results on combinatorial problems from MAP inference for Markov Random Fields, quadratic assignment and cell tracking for developmental biology. Our highly parallel GPU implementation improves upon the running times of the algorithms from Lange et al. (2021) by up to an order of magnitude. In particular, we come close to or outperform some state-of-the-art specialized heuristics while being problem agnostic.
• Abstract（参考訳）: 本稿では,構造化予測で発生する0-1整数線形プログラムを並列に分解する手法を提案する。 本稿では,ラグランジュ双対を解くための新しい反復更新スキームと,プライマル解の復号のための摂動法を提案する。 サブプロブレムを表現するには、Lange氏ら(2021年)に従い、バイナリ意思決定図(BDD)を使用します。 我々の原始的アルゴリズムと双対アルゴリズムはサブプロブレム間の同期をほとんど必要とせず、BDDの最適化には複雑な制御フローのない基本的な操作しか必要としない。 これにより、メソッドのすべてのコンポーネントに対してgpuが提供する並列処理を活用できます。 本稿では、マルコフ確率場におけるMAP推論の組合せ問題、発達生物学における二次配置と細胞追跡に関する実験結果を示す。 高度に並列なgpuの実装は、lange et al. (2021) のアルゴリズムの実行時間を最大で1桁改善する。 特に、問題非依存であるながら、最先端の専門的なヒューリスティックに近づいたり、あるいは及ばなかったりします。

関連論文リスト

• GreedyML: A Parallel Algorithm for Maximizing Constrained Submodular Functions [2.9998889086656586]
  分散メモリマルチプロセッサ上での単調部分モジュラ関数の最大化のための並列近似アルゴリズムについて述べる。 我々の研究は、大規模データセットにおける部分モジュラー最適化問題を解く必要性によって動機付けられている。
  論文  参考訳（メタデータ） (2024-03-15T14:19:09Z)
• Accelerating Cutting-Plane Algorithms via Reinforcement Learning Surrogates [49.84541884653309]
  凸離散最適化問題に対する現在の標準的なアプローチは、カットプレーンアルゴリズムを使うことである。 多くの汎用カット生成アルゴリズムが存在するにもかかわらず、大規模な離散最適化問題は、難易度に悩まされ続けている。 そこで本研究では,強化学習による切削平面アルゴリズムの高速化手法を提案する。
  論文  参考訳（メタデータ） (2023-07-17T20:11:56Z)
• Second-order optimization with lazy Hessians [55.51077907483634]
  一般の非線形最適化問題を解くためにニュートンの遅延ヘッセン更新を解析する。 我々は、メソッドの各ステップで新しい勾配を計算しながら、これまで見られたヘッセン反復を再利用する。
  論文  参考訳（メタデータ） (2022-12-01T18:58:26Z)
• On a class of geodesically convex optimization problems solved via Euclidean MM methods [50.428784381385164]
  ユークリッド凸化関数の違いは、統計学と機械学習の異なるタイプの問題の違いとして記述できることを示す。 最終的に、より広い範囲、より広い範囲の作業を支援するのです。
  論文  参考訳（メタデータ） (2022-06-22T23:57:40Z)
• DOGE-Train: Discrete Optimization on GPU with End-to-end Training [28.795080637690095]
  0-1整数線形プログラムの緩和を解くために,高速でスケーラブルなデータ駆動型手法を提案する。 グラフニューラルネットワーク(GNN)とラグランジュ分解に基づくアルゴリズムであるFastDOGを用いる。
  論文  参考訳（メタデータ） (2022-05-23T21:09:41Z)
• RAMA: A Rapid Multicut Algorithm on GPU [23.281726932718232]
  本稿では,マルチカット問題(マグニチュード相関クラスタリング)に対する高並列原始双対アルゴリズムを提案する。 我々のアルゴリズムは、最適距離を推定する原始解と双対下界を生成する。 最大$mathcalO(108)$変数を数秒で、小さな原始双対ギャップで、非常に大規模なベンチマーク問題を解くことができる。
  論文  参考訳（メタデータ） (2021-09-04T10:33:59Z)
• 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)
• Kernel methods through the roof: handling billions of points efficiently [94.31450736250918]
  カーネル法は、非パラメトリック学習に対するエレガントで原則化されたアプローチを提供するが、今のところ大規模な問題ではほとんど利用できない。 最近の進歩は、最適化、数値線形代数、ランダム射影など、多くのアルゴリズム的アイデアの利点を示している。 ここでは、これらの取り組みをさらに進めて、GPUハードウェアを最大限に活用する解決器を開発し、テストする。
  論文  参考訳（メタデータ） (2020-06-18T08:16:25Z)
• MPLP++: Fast, Parallel Dual Block-Coordinate Ascent for Dense Graphical Models [96.1052289276254]
  この研究は、人気のあるDual Block-Coordinate Ascent原則に基づく新しいMAP-solverを導入している。 驚いたことに、性能の低い解法に小さな変更を加えることで、既存の解法を大きなマージンで大幅に上回る新しい解法MPLP++を導出します。
  論文  参考訳（メタデータ） (2020-04-16T16:20:53Z)

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

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