論文の概要: RAMA: A Rapid Multicut Algorithm on GPU
- arxiv url: http://arxiv.org/abs/2109.01838v1
- Date: Sat, 4 Sep 2021 10:33:59 GMT
- ステータス: 処理完了
- システム内更新日: 2021-09-07 16:47:26.534410
- Title: RAMA: A Rapid Multicut Algorithm on GPU
- Title（参考訳）: RAMA: GPU上の高速マルチカットアルゴリズム
- Authors: Ahmed Abbas and Paul Swoboda
- Abstract要約: 本稿では,マルチカット問題(マグニチュード相関クラスタリング)に対する高並列原始双対アルゴリズムを提案する。
我々のアルゴリズムは、最適距離を推定する原始解と双対下界を生成する。
最大$mathcalO(108)$変数を数秒で、小さな原始双対ギャップで、非常に大規模なベンチマーク問題を解くことができる。
- 参考スコア（独自算出の注目度）: 23.281726932718232
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We propose a highly parallel primal-dual algorithm for the multicut (a.k.a.
correlation clustering) problem, a classical graph clustering problem widely
used in machine learning and computer vision. Our algorithm consists of three
steps executed recursively: (1) Finding conflicted cycles that correspond to
violated inequalities of the underlying multicut relaxation, (2) Performing
message passing between the edges and cycles to optimize the Lagrange
relaxation coming from the found violated cycles producing reduced costs and
(3) Contracting edges with high reduced costs through matrix-matrix
multiplications.
Our algorithm produces primal solutions and dual lower bounds that estimate
the distance to optimum. We implement our algorithm on GPUs and show resulting
one to two order-of-magnitudes improvements in execution speed without
sacrificing solution quality compared to traditional serial algorithms that run
on CPUs. We can solve very large scale benchmark problems with up to
$\mathcal{O}(10^8)$ variables in a few seconds with small primal-dual gaps. We
make our code available at https://github.com/pawelswoboda/RAMA.
- Abstract（参考訳）: 本稿では,マルチカットのための高並列な素数双対アルゴリズムを提案する。
相関クラスタリング) 問題は、機械学習やコンピュータビジョンで広く使われている古典的なグラフクラスタリング問題である。
提案アルゴリズムは,(1) 下位のマルチカット緩和の不等式に該当する競合するサイクルを見つけること,(2) エッジとサイクル間のメッセージパッシングを行い,検出された違反サイクルから生じるラグランジュ緩和を最適化すること,(3) 行列行列行列乗算による高コストの制約エッジを求めること,の3段階からなる。
本アルゴリズムは最適までの距離を推定する原始解と双対下界を生成する。
我々は,GPUにアルゴリズムを実装し,CPU上で動作する従来のシリアルアルゴリズムと比較して,ソリューションの品質を犠牲にすることなく,実行速度を1～2桁改善したことを示す。
最大$\mathcal{O}(10^8)$変数を数秒で、小さな原始双対ギャップで、非常に大規模なベンチマーク問題を解くことができる。
コードはhttps://github.com/pawelswoboda/ramaで利用可能です。
関連論文リスト
- GreedyML: A Parallel Algorithm for Maximizing Submodular Functions [2.9998889086656586]
分散メモリマルチプロセッサ上での単調部分モジュラ関数の最大化のための並列近似アルゴリズムについて述べる。
我々の研究は、データ要約、機械学習、グラフスカラー化といった分野における実践的な応用のために、大規模データセットのサブモジュラー最適化問題を解決する必要性によって動機付けられている。
論文 参考訳（メタデータ） (2024-03-15T14:19:09Z) - Accelerating Cutting-Plane Algorithms via Reinforcement Learning
Surrogates [49.84541884653309]
凸離散最適化問題に対する現在の標準的なアプローチは、カットプレーンアルゴリズムを使うことである。
多くの汎用カット生成アルゴリズムが存在するにもかかわらず、大規模な離散最適化問題は、難易度に悩まされ続けている。
そこで本研究では,強化学習による切削平面アルゴリズムの高速化手法を提案する。
論文 参考訳（メタデータ） (2023-07-17T20:11:56Z) - Breaking 3-Factor Approximation for Correlation Clustering in
Polylogarithmic Rounds [0.23633885460047763]
相関クラスタリング問題に対する並列アルゴリズムについて検討する。
目標は、エンティティをクラスタに分割し、ラベルとの相違を最小限にすることである。
現在、全ての効率的な並列アルゴリズムは、近似比が少なくとも3である。
3 より優れた近似比を実現するための最初の多元対数アルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-07-13T12:32:49Z) - Learning the Positions in CountSketch [49.57951567374372]
本稿では,まずランダムなスケッチ行列に乗じてデータを圧縮し,最適化問題を高速に解くスケッチアルゴリズムについて検討する。
本研究では,ゼロでないエントリの位置を最適化する学習ベースアルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-06-11T07:28:35Z) - Batch-efficient EigenDecomposition for Small and Medium Matrices [65.67315418971688]
EigenDecomposition (ED)は多くのコンピュータビジョンアルゴリズムとアプリケーションの中心にある。
本稿では,コンピュータビジョンの応用シナリオに特化したQRベースのED手法を提案する。
論文 参考訳（メタデータ） (2022-07-09T09:14:12Z) - A Push-Relabel Based Additive Approximation for Optimal Transport [5.111364864495785]
最適な輸送を計算するための厳密なアルゴリズムは遅くなる。
我々は、OT距離の$varepsilon$approximationを求めるための、新しい非常に単純なアプローチを導入する。
我々のアルゴリズムは、OT距離を計算するために、O(n2/varepsilon2)$のほぼ最適実行時間を達成する。
論文 参考訳（メタデータ） (2022-03-07T21:40:14Z) - GPU-accelerated Faster Mean Shift with euclidean distance metrics [1.3507758562554621]
平均シフトアルゴリズムはクラスタリング問題の解法として広く用いられている。
従来の研究では,GPUを高速化する高速平均シフトアルゴリズムが提案されている。
本研究では,ユークリッド距離測定値を扱うために,従来のアルゴリズムを拡張し改良する。
論文 参考訳（メタデータ） (2021-12-27T20:18:24Z) - 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) - Lagrangian Decomposition for Neural Network Verification [148.0448557991349]
ニューラルネットワーク検証の基本的なコンポーネントは、出力が取ることのできる値のバウンダリの計算である。
ラグランジアン分解に基づく新しい手法を提案する。
ランニングタイムのごく一部で、既成の解法に匹敵するバウンダリが得られることを示す。
論文 参考訳（メタデータ） (2020-02-24T17:55:10Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。