論文の概要: Practical Parallel Algorithms for Non-Monotone Submodular Maximization
- arxiv url: http://arxiv.org/abs/2308.10656v1
- Date: Mon, 21 Aug 2023 11:48:34 GMT
- ステータス: 処理完了
- システム内更新日: 2023-08-22 13:36:45.905830
- Title: Practical Parallel Algorithms for Non-Monotone Submodular Maximization
- Title（参考訳）: 非単調部分モジュラー最大化のための実用的な並列アルゴリズム
- Authors: Shuang Cui, Kai Han, Jing Tang, He Huang, Xueying Li, Aakas Zhiyuli,
Hanxiao Li
- Abstract要約: Submodularは、人工知能の分野における様々な分野に広く応用されている。
部分モジュラーアルゴリズムの並列化可能性の1つは適応的な複雑性であり、これは対象関数に対する多数のクエリを並列に実行できるラウンドの数を示している。
証明可能な近似比と非単調なサブモジュラー問題に対するサブ適応複雑性をともに持つ最初のアルゴリズムを$k$-systemに提案する。
- 参考スコア（独自算出の注目度）: 20.13836086815112
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Submodular maximization has found extensive applications in various domains
within the field of artificial intelligence, including but not limited to
machine learning, computer vision, and natural language processing. With the
increasing size of datasets in these domains, there is a pressing need to
develop efficient and parallelizable algorithms for submodular maximization.
One measure of the parallelizability of a submodular maximization algorithm is
its adaptive complexity, which indicates the number of sequential rounds where
a polynomial number of queries to the objective function can be executed in
parallel. In this paper, we study the problem of non-monotone submodular
maximization subject to a knapsack constraint, and propose the first
combinatorial algorithm achieving an $(8+\epsilon)$-approximation under
$\mathcal{O}(\log n)$ adaptive complexity, which is \textit{optimal} up to a
factor of $\mathcal{O}(\log\log n)$. Moreover, we also propose the first
algorithm with both provable approximation ratio and sublinear adaptive
complexity for the problem of non-monotone submodular maximization subject to a
$k$-system constraint. As a by-product, we show that our two algorithms can
also be applied to the special case of submodular maximization subject to a
cardinality constraint, and achieve performance bounds comparable with those of
state-of-the-art algorithms. Finally, the effectiveness of our approach is
demonstrated by extensive experiments on real-world applications.
- Abstract（参考訳）: サブモジュールの最大化は、機械学習、コンピュータビジョン、自然言語処理など、人工知能の分野における様々な分野に広く応用されている。
これらの領域でデータセットのサイズが大きくなるにつれて、サブモジュラー最大化のための効率的かつ並列化可能なアルゴリズムを開発する必要性が高まっている。
部分モジュラル最大化アルゴリズムの並列化可能性の1つの尺度は適応的複雑性であり、対象関数に対する多項式数のクエリを並列に実行できる逐次ラウンドの数を示す。
本稿では,knapsack制約を考慮した非単調部分モジュラー最大化問題について検討し,$$(8+\epsilon)$-approximation under $\mathcal{O}(\log n)$ Adaptive complexity, which is \textit{optimal} up to a factor of $\mathcal{O}(\log\log n)$。
さらに,$k$-system制約を受ける非単調部分モジュラー最大化問題に対して,証明可能な近似比とサブリニア適応複雑性を両立した最初のアルゴリズムを提案する。
副産物として,我々の2つのアルゴリズムは,濃度制約を受ける部分モジュラー最大化の特別な場合にも適用可能であり,最先端アルゴリズムと同等の性能限界を達成することができることを示した。
最後に,本手法の有効性を実世界の応用に関する広範な実験により実証した。
関連論文リスト
- Provably Faster Algorithms for Bilevel Optimization via Without-Replacement Sampling [96.47086913559289]
勾配に基づくアルゴリズムはバイレベル最適化に広く用いられている。
本研究では,より高速な収束率を実現する非置換サンプリングに基づくアルゴリズムを提案する。
合成および実世界の両方のアプリケーションに対してアルゴリズムを検証する。
論文 参考訳（メタデータ） (2024-11-07T17:05:31Z) - 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) - Sample Complexity for Quadratic Bandits: Hessian Dependent Bounds and
Optimal Algorithms [64.10576998630981]
最適なヘッセン依存型サンプルの複雑さを, 初めて厳密に評価した。
ヘシアン非依存のアルゴリズムは、すべてのヘシアンインスタンスに対して最適なサンプル複雑さを普遍的に達成する。
本アルゴリズムにより得られたサンプルの最適複雑さは,重み付き雑音分布においても有効である。
論文 参考訳（メタデータ） (2023-06-21T17:03:22Z) - Accelerated First-Order Optimization under Nonlinear Constraints [73.2273449996098]
我々は、制約付き最適化のための一階アルゴリズムと非滑らかなシステムの間で、新しい一階アルゴリズムのクラスを設計する。
これらのアルゴリズムの重要な性質は、制約がスパース変数の代わりに速度で表されることである。
論文 参考訳（メタデータ） (2023-02-01T08:50:48Z) - Fast Computation of Optimal Transport via Entropy-Regularized Extragradient Methods [75.34939761152587]
2つの分布間の最適な輸送距離の効率的な計算は、様々な応用を促進するアルゴリズムとして機能する。
本稿では,$varepsilon$加法精度で最適な輸送を計算できるスケーラブルな一階最適化法を提案する。
論文 参考訳（メタデータ） (2023-01-30T15:46:39Z) - Quantum Goemans-Williamson Algorithm with the Hadamard Test and
Approximate Amplitude Constraints [62.72309460291971]
本稿では,n+1$ qubitsしか使用しないGoemans-Williamsonアルゴリズムの変分量子アルゴリズムを提案する。
補助量子ビット上で適切にパラメータ化されたユニタリ条件として目的行列を符号化することにより、効率的な最適化を実現する。
各種NPハード問題に対して,Goemans-Williamsonアルゴリズムの量子的効率的な実装を考案し,提案プロトコルの有効性を実証する。
論文 参考訳（メタデータ） (2022-06-30T03:15:23Z) - Scalable Distributed Algorithms for Size-Constrained Submodular Maximization in the MapReduce and Adaptive Complexity Models [17.462968952951883]
MapReduce(MR)モデルのサブモジュラー関数は注目されている。
MR設定において,複数のサブ線形適応アルゴリズムが動作に必要な整合性を満たすことを示す。
論文 参考訳（メタデータ） (2022-06-20T04:17:32Z) - Best of Both Worlds: Practical and Theoretically Optimal Submodular Maximization in Parallel [17.462968952951883]
主アルゴリズムは、独立した関心を持つ可能性のある2つのコンポーネントから組み立てられる。
LINEARSEQの変種は、文献のどのアルゴリズムよりも小さい$O(log(n))$の適応複雑性を持つ。
論文 参考訳（メタデータ） (2021-11-15T17:10:40Z) - 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) - Adaptive Sampling for Fast Constrained Maximization of Submodular
Function [8.619758302080891]
非モノトーンサブモジュラに対する多対数適応性を有するアルゴリズムを一般側制約下で開発する。
本アルゴリズムは,$p$-system 側制約下での非単調部分モジュラ関数の最大化に適している。
論文 参考訳（メタデータ） (2021-02-12T12:38:03Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。