論文の概要: Scalable Distributed Algorithms for Size-Constrained Submodular
Maximization in the MapReduce and Adaptive Complexity Models
- arxiv url: http://arxiv.org/abs/2206.09563v4
- Date: Mon, 25 Sep 2023 15:28:22 GMT
- ステータス: 処理完了
- システム内更新日: 2023-09-27 05:02:43.788390
- Title: Scalable Distributed Algorithms for Size-Constrained Submodular
Maximization in the MapReduce and Adaptive Complexity Models
- Title（参考訳）: MapReduceおよび適応複雑度モデルにおけるサイズ制約付き部分モジュラ最大化のためのスケーラブル分散アルゴリズム
- Authors: Tonmoy Dey, Yixin Chen, Alan Kuhnle
- Abstract要約: MapReduceモデルのサブモジュール関数は、多くの注目を集めています。
単調および部分モジュラー関数のサイズ制約に対して、いくつかの部分制約適応アルゴリズムが整合性を満たすことを示す。
また,この問題に対して,定数MRラウンドを用いた最初の線形分散アルゴリズムを開発した。
- 参考スコア（独自算出の注目度）: 19.626627053947423
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Distributed maximization of a submodular function in the MapReduce model has
received much attention, culminating in two frameworks that allow a centralized
algorithm to be run in the MR setting without loss of approximation, as long as
the centralized algorithm satisfies a certain consistency property - which had
only been shown to be satisfied by the standard greedy and continous greedy
algorithms. A separate line of work has studied parallelizability of submodular
maximization in the adaptive complexity model, where each thread may have
access to the entire ground set. For the size-constrained maximization of a
monotone and submodular function, we show that several sublinearly adaptive
algorithms satisfy the consistency property required to work in the MR setting,
which yields highly practical parallelizable and distributed algorithms. Also,
we develop the first linear-time distributed algorithm for this problem with
constant MR rounds. Finally, we provide a method to increase the maximum
cardinality constraint for MR algorithms at the cost of additional MR rounds.
- Abstract（参考訳）: MapReduceモデルにおける部分モジュラ関数の分散最大化は注目されており、標準的なグリージーアルゴリズムと連続グリージーアルゴリズムで満たされていたような一定の一貫性特性を満たさない限り、近似を失うことなくMR設定で一元的アルゴリズムを動作させることができる2つのフレームワークで決定されている。
適応的複雑性モデルにおいて、各スレッドが基底集合全体にアクセス可能な部分モジュラー最大化の並列化性について研究した。
モノトーンおよびサブモジュラー関数のサイズ制約による最大化について, MR設定における動作に必要な整合性を満たす部分線形適応アルゴリズムがいくつか存在することを示す。
また, この問題に対して, MRラウンドを一定とした最初の線形時間分散アルゴリズムを開発した。
最後に,追加のMRラウンドを犠牲にして,MRアルゴリズムの最大濃度制約を増大させる手法を提案する。
関連論文リスト
- 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 [20.13836086815112]
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) - Effective Dimension Adaptive Sketching Methods for Faster Regularized
Least-Squares Optimization [56.05635751529922]
スケッチに基づくL2正規化最小二乗問題の解法を提案する。
我々は、最も人気のあるランダム埋め込みの2つ、すなわちガウス埋め込みとサブサンプリングランダム化アダマール変換(SRHT)を考える。
論文 参考訳（メタデータ） (2020-06-10T15:00:09Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。