論文の概要: DASH: Distributed Adaptive Sequencing Heuristic for Submodular
Maximization
- arxiv url: http://arxiv.org/abs/2206.09563v1
- Date: Mon, 20 Jun 2022 04:17:32 GMT
- ステータス: 処理完了
- システム内更新日: 2022-06-22 19:58:25.837819
- Title: DASH: Distributed Adaptive Sequencing Heuristic for Submodular
Maximization
- Title（参考訳）: dash: サブモジュラー最大化のための分散適応シーケンスヒューリスティック
- Authors: Tonmoy Dey, Yixin Chen, Alan Kuhnle
- Abstract要約: 本稿では,分散環境でのSMCC問題について検討し,サブ線形適応性を導入する3つのMRモデルアルゴリズムを提案する。
我々のアルゴリズムであるDASHは、1回のMRラウンドで$frac12(1-1/e-varepsilon)を近似する。
マルチラウンドのMETADASHにより、MRモデルアルゴリズムは以前は不可能だった大きな濃度制約で動作することができる。
- 参考スコア（独自算出の注目度）: 39.762631085432055
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The development of parallelizable algorithms for monotone, submodular
maximization subject to cardinality constraint (SMCC) has resulted in two
separate research directions: centralized algorithms with low adaptive
complexity, which require random access to the entire dataset; and distributed
MapReduce (MR) model algorithms, that use a small number of MR rounds of
computation. Currently, no MR model algorithm is known to use sublinear number
of adaptive rounds which limits their practical performance. We study the SMCC
problem in a distributed setting and present three separate MR model algorithms
that introduce sublinear adaptivity in a distributed setup. Our primary
algorithm, DASH achieves an approximation of $\frac{1}{2}(1-1/e-\varepsilon)$
using one MR round, while its multi-round variant METADASH enables MR model
algorithms to be run on large cardinality constraints that were previously not
possible. The two additional algorithms, T-DASH and G-DASH provide an improved
ratio of ($\frac{3}{8}-\varepsilon$) and ($1-1/e-\varepsilon$) respectively
using one and $(1/\varepsilon)$ MR rounds . All our proposed algorithms have
sublinear adaptive complexity and we provide extensive empirical evidence to
establish: DASH is orders of magnitude faster than the state-of-the-art
distributed algorithms while producing nearly identical solution values; and
validate the versatility of DASH in obtaining feasible solutions on both
centralized and distributed data.
- Abstract（参考訳）: 単調な部分モジュラ最大化を基準制約(SMCC)に対象とする並列化可能なアルゴリズムの開発は、データセット全体へのランダムアクセスを必要とする適応度が低い集中型アルゴリズムと、少数のMRラウンドを使用する分散MapReduce(MR)モデルアルゴリズムの2つの研究方向を導いた。
現在、MRモデルアルゴリズムは、実用性能を制限する適応ラウンドのサブ線形数を使うことは知られていない。
分散設定におけるsmcc問題を調査し,分散設定にサブリニア適応性を導入する3つのmrモデルアルゴリズムを提案する。
我々の主アルゴリズムであるDASHは、1回のMRラウンドを用いて$\frac{1}{2}(1-1/e-\varepsilon)$の近似を達成し、その多ラウンド変種METADASHはMRモデルアルゴリズムを従来不可能だった大きな濃度制約で実行できるようにする。
T-DASHとG-DASHの2つの追加アルゴリズムは、それぞれ1/e-\varepsilon$(1/\varepsilon)$ MRラウンドで$1/e-\varepsilon$)と$1-1/e-\varepsilon$(1/\varepsilon)の改善比を提供する。
DASHは最先端の分散アルゴリズムよりも桁違いに高速であり、ほぼ同一の解値を生成するとともに、分散データと集中データの両方で実現可能な解を得る上でのDASHの有効性を検証する。
関連論文リスト
- Near-Optimal Online Learning for Multi-Agent Submodular Coordination: Tight Approximation and Communication Efficiency [52.60557300927007]
離散部分モジュラー問題を連続的に最適化するために,$textbfMA-OSMA$アルゴリズムを提案する。
また、一様分布を混合することによりKLの発散を効果的に活用する、プロジェクションフリーな$textbfMA-OSEA$アルゴリズムも導入する。
我々のアルゴリズムは最先端OSGアルゴリズムによって提供される$(frac11+c)$-approximationを大幅に改善する。
論文 参考訳（メタデータ） (2025-02-07T15:57:56Z) - 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) - An Efficient Algorithm for Clustered Multi-Task Compressive Sensing [60.70532293880842]
クラスタ化マルチタスク圧縮センシングは、複数の圧縮センシングタスクを解決する階層モデルである。
このモデルに対する既存の推論アルゴリズムは計算コストが高く、高次元ではうまくスケールしない。
本稿では,これらの共分散行列を明示的に計算する必要をなくし,モデル推論を大幅に高速化するアルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-09-30T15:57:14Z) - Practical Parallel Algorithms for Non-Monotone Submodular Maximization [15.187654042027111]
Submodularは、人工知能の分野における様々な分野に広く応用されている。
部分モジュラーアルゴリズムの並列化可能性の1つは適応的な複雑性であり、これは対象関数に対する多数のクエリを並列に実行できるラウンドの数を示している。
証明可能な近似比と非単調なサブモジュラー問題に対するサブ適応複雑性をともに持つ最初のアルゴリズムを$k$-systemに提案する。
論文 参考訳（メタデータ） (2023-08-21T11:48:34Z) - Sample Complexity for Quadratic Bandits: Hessian Dependent Bounds and
Optimal Algorithms [64.10576998630981]
最適なヘッセン依存型サンプルの複雑さを, 初めて厳密に評価した。
ヘシアン非依存のアルゴリズムは、すべてのヘシアンインスタンスに対して最適なサンプル複雑さを普遍的に達成する。
本アルゴリズムにより得られたサンプルの最適複雑さは,重み付き雑音分布においても有効である。
論文 参考訳（メタデータ） (2023-06-21T17:03:22Z) - Fast Computation of Optimal Transport via Entropy-Regularized Extragradient Methods [75.34939761152587]
2つの分布間の最適な輸送距離の効率的な計算は、様々な応用を促進するアルゴリズムとして機能する。
本稿では,$varepsilon$加法精度で最適な輸送を計算できるスケーラブルな一階最適化法を提案する。
論文 参考訳（メタデータ） (2023-01-30T15:46:39Z) - Best of Both Worlds: Practical and Theoretically Optimal Submodular Maximization in Parallel [17.462968952951883]
主アルゴリズムは、独立した関心を持つ可能性のある2つのコンポーネントから組み立てられる。
LINEARSEQの変種は、文献のどのアルゴリズムよりも小さい$O(log(n))$の適応複雑性を持つ。
論文 参考訳（メタデータ） (2021-11-15T17:10:40Z) - Lower Bounds and Optimal Algorithms for Smooth and Strongly Convex
Decentralized Optimization Over Time-Varying Networks [79.16773494166644]
通信ネットワークのノード間を分散的に保存するスムーズで強い凸関数の和を最小化するタスクについて検討する。
我々は、これらの下位境界を達成するための2つの最適アルゴリズムを設計する。
我々は,既存の最先端手法と実験的な比較を行うことにより,これらのアルゴリズムの理論的効率を裏付ける。
論文 参考訳（メタデータ） (2021-06-08T15:54:44Z) - Submodular Maximization subject to a Knapsack Constraint: Combinatorial
Algorithms with Near-optimal Adaptive Complexity [13.416309759182635]
我々は、ほぼ最適の$O(log n)$適応複雑性を持つ非単調部分モジュラーアルゴリズムに対する最初の定数近似を得る。
我々のアルゴリズムは$tildeO(n2)$の値クエリを要求するが、代わりに$tildeO(n)$で実行するように修正できる。
これはまた、この問題に対して線形適応的な複雑性を持つ最初のアプローチであり、濃度制約や単調な目的の特別な場合であっても、最先端の手法に匹敵する。
論文 参考訳（メタデータ） (2021-02-16T18:15:51Z) - Linear-Time Algorithms for Adaptive Submodular Maximization [17.19443570570189]
まず, 濃度制約を考慮した適応的部分モジュラー問題を提案する。
第二に、完全適応部分モジュラリティの概念を導入する。
提案アルゴリズムは,O(nlogfrac1epsilon)$関数の評価値のみを用いて,$frac1-1/e-epsilon4-2/e-2epsilon$近似比を実現する。
論文 参考訳（メタデータ） (2020-07-08T15:54:28Z) - Iterative Algorithm Induced Deep-Unfolding Neural Networks: Precoding
Design for Multiuser MIMO Systems [59.804810122136345]
本稿では,AIIDNN(ディープ・アンフォールディング・ニューラルネット)を一般化した,ディープ・アンフォールディングのためのフレームワークを提案する。
古典的重み付き最小二乗誤差(WMMSE)反復アルゴリズムの構造に基づく効率的なIAIDNNを提案する。
提案したIAIDNNは,計算複雑性を低減した反復WMMSEアルゴリズムの性能を効率よく向上することを示す。
論文 参考訳（メタデータ） (2020-06-15T02:57:57Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。