論文の概要: GreedyML: A Parallel Algorithm for Maximizing Submodular Functions
- arxiv url: http://arxiv.org/abs/2403.10332v2
- Date: Wed, 30 Oct 2024 18:51:58 GMT
- ステータス: 翻訳完了
- システム内更新日: 2024-11-01 16:56:13.452434
- Title: GreedyML: A Parallel Algorithm for Maximizing Submodular Functions
- Title（参考訳）: GreedyML: サブモジュール関数の最大化のための並列アルゴリズム
- Authors: Shivaram Gopal, S M Ferdous, Hemanta K. Maji, Alex Pothen,
- Abstract要約: 分散メモリマルチプロセッサ上での単調部分モジュラ関数の最大化のための並列近似アルゴリズムについて述べる。
我々の研究は、データ要約、機械学習、グラフスカラー化といった分野における実践的な応用のために、大規模データセットのサブモジュラー最適化問題を解決する必要性によって動機付けられている。
- 参考スコア（独自算出の注目度）: 2.9998889086656586
- License:
- Abstract: We describe a parallel approximation algorithm for maximizing monotone submodular functions subject to hereditary constraints on distributed memory multiprocessors. Our work is motivated by the need to solve submodular optimization problems on massive data sets, for practical applications in areas such as data summarization, machine learning, and graph sparsification. Our work builds on the randomized distributed RandGreedI algorithm, proposed by Barbosa, Ene, Nguyen, and Ward (2015). This algorithm computes a distributed solution by randomly partitioning the data among all the processors and then employing a single accumulation step in which all processors send their partial solutions to one processor. However, for large problems, the accumulation step could exceed the memory available on a processor, and the processor which performs the accumulation could become a computational bottleneck. Here, we propose a generalization of the RandGreedI algorithm that employs multiple accumulation steps to reduce the memory required. We analyze the approximation ratio and the time complexity of the algorithm (in the BSP model). We also evaluate the new GreedyML algorithm on three classes of problems, and report results from massive data sets with millions of elements. The results show that the GreedyML algorithm can solve problems where the sequential Greedy and distributed RandGreedI algorithms fail due to memory constraints. For certain computationally intensive problems, the GreedyML algorithm can be faster than the RandGreedI algorithm. The observed approximation quality of the solutions computed by the GreedyML algorithm closely matches those obtained by the RandGreedI algorithm on these problems.
- Abstract（参考訳）: 分散メモリマルチプロセッサ上での遺伝的制約を考慮した単調部分モジュラ関数を最大化するための並列近似アルゴリズムについて述べる。
我々の研究は、データ要約、機械学習、グラフスカラー化といった分野における実践的な応用のために、大規模データセットのサブモジュラー最適化問題を解決する必要性によって動機付けられている。
我々の研究は、Barbosa, Ene, Nguyen, Ward (2015)によって提案されたランダム化された分散RandGreedIアルゴリズムに基づいている。
このアルゴリズムは、すべてのプロセッサ間でデータをランダムにパーティショニングして分散ソリューションを計算し、その後、すべてのプロセッサが部分的なソリューションを1つのプロセッサに送信する単一の集積ステップを使用する。
しかし、大きな問題に対して、集積ステップはプロセッサ上で利用可能なメモリを超える可能性があり、集積を実行するプロセッサは計算ボトルネックとなる可能性がある。
本稿では、複数の累積ステップを用いて必要なメモリを削減するRandGreedIアルゴリズムの一般化を提案する。
アルゴリズムの近似比と時間複雑性を(BSPモデルで)解析する。
また、3種類の問題に対して新しいGreedyMLアルゴリズムを評価し、数百万要素からなる大規模データセットの結果を報告する。
その結果,GreedyMLアルゴリズムはメモリ制約により逐次Greedyアルゴリズムと分散RandGreedIアルゴリズムがフェールする問題を解くことができることがわかった。
ある計算集約的な問題に対して、GreedyMLアルゴリズムはRandGreedIアルゴリズムよりも高速である。
GreedyMLアルゴリズムによって計算された解の近似品質は、これらの問題のRandGreedIアルゴリズムによって得られた解と密接に一致している。
関連論文リスト
- An Efficient Algorithm for Clustered Multi-Task Compressive Sensing [60.70532293880842]
クラスタ化マルチタスク圧縮センシングは、複数の圧縮センシングタスクを解決する階層モデルである。
このモデルに対する既存の推論アルゴリズムは計算コストが高く、高次元ではうまくスケールしない。
本稿では,これらの共分散行列を明示的に計算する必要をなくし,モデル推論を大幅に高速化するアルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-09-30T15:57:14Z) - Accelerating Cutting-Plane Algorithms via Reinforcement Learning
Surrogates [49.84541884653309]
凸離散最適化問題に対する現在の標準的なアプローチは、カットプレーンアルゴリズムを使うことである。
多くの汎用カット生成アルゴリズムが存在するにもかかわらず、大規模な離散最適化問題は、難易度に悩まされ続けている。
そこで本研究では,強化学習による切削平面アルゴリズムの高速化手法を提案する。
論文 参考訳（メタデータ） (2023-07-17T20:11:56Z) - Linearized Wasserstein dimensionality reduction with approximation
guarantees [65.16758672591365]
LOT Wassmap は、ワーッサーシュタイン空間の低次元構造を明らかにするための計算可能なアルゴリズムである。
我々は,LOT Wassmapが正しい埋め込みを実現し,サンプルサイズの増加とともに品質が向上することを示す。
また、LOT Wassmapがペア距離計算に依存するアルゴリズムと比較して計算コストを大幅に削減することを示す。
論文 参考訳（メタデータ） (2023-02-14T22:12:16Z) - Accelerating ERM for data-driven algorithm design using output-sensitive techniques [26.32088674030797]
データ駆動型アルゴリズム設計のための効率的な学習アルゴリズムを開発するための技術について研究する。
提案手法は,超平面の集合によって誘導されるポリトープを列挙する出力感受性アルゴリズムである。
本稿では、価格問題、リンクベースのクラスタリング、動的プログラミングに基づくシーケンスアライメントのアルゴリズムを提供することにより、我々の技術を説明する。
論文 参考訳（メタデータ） (2022-04-07T17:27:18Z) - Review of Serial and Parallel Min-Cut/Max-Flow Algorithms for Computer
Vision [6.574107319036238]
Hochbaum pseudoflowアルゴリズムは最速のシリアルアルゴリズムであり、Boykov-Kolmogorovアルゴリズムは最もメモリ効率が高い。
既存の min-cut/max-flow アルゴリズムは、大きな問題ではシリアルアルゴリズムを著しく上回るが、中小問題ではオーバーヘッドが増大する。
論文 参考訳（メタデータ） (2022-02-01T14:06:27Z) - 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) - Linear Bandit Algorithms with Sublinear Time Complexity [67.21046514005029]
既存の線形バンディットアルゴリズムを高速化し,arms $k$ でステップ毎の複雑性サブリニアを実現する。
提案するアルゴリズムは、いくつかの$alpha(t) > 0$ と $widetilde o(stt)$ regret に対して1ステップあたり$o(k1-alpha(t))$ の複雑さを達成することができる。
論文 参考訳（メタデータ） (2021-03-03T22:42:15Z) - Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
本稿では,線形モデルから信号整数を推定する古典整数最小二乗問題について検討する。
問題はNPハードであり、信号処理、バイオインフォマティクス、通信、機械学習といった様々な応用でしばしば発生する。
本稿では, 深いニューラルネットワークを用いて, 単純化されたメモリバウンドA*アルゴリズムの最適推定を推定し, HATSアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-01-07T08:00:02Z) - A new heuristic algorithm for fast k-segmentation [0.0]
文献には$k$-segmentationの厳密で近似的な方法が存在する。
本稿では,既存の手法を改善するために,新しいアルゴリズムを提案する。
計算コストのごく一部で正確な手法と競合するアキュラシーを提供することを実証的に見出した。
論文 参考訳（メタデータ） (2020-09-02T04:50:17Z) - Towards Solving Large-scale Expensive Optimization Problems Efficiently
Using Coordinate Descent Algorithm [3.1600708674008393]
計算予算が限られているLSEGO問題に対処するために,修正された座標 Descent アルゴリズム (MCD) を提案する。
提案アルゴリズムは,関心領域の探索と,指数速度で半分に折り畳むことで検索空間の縮小という,2つの主要なステップの恩恵を受ける。
提案アルゴリズムは,次元1000の20個のベンチマーク関数上でのデルタグルーピングと協調的共進化との比較を行った。
論文 参考訳（メタデータ） (2020-03-07T22:48:38Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。