論文の概要: Improved Parallel Algorithm for Non-Monotone Submodular Maximization under Knapsack Constraint

• arxiv url: http://arxiv.org/abs/2409.04415v1
• Date: Fri, 6 Sep 2024 17:17:52 GMT
• ステータス: 処理完了
• システム内更新日: 2024-09-09 15:05:01.230957
• Title: Improved Parallel Algorithm for Non-Monotone Submodular Maximization under Knapsack Constraint
• Title（参考訳）: Knapsack制約下での非モノトン部分モジュラ最大化のための並列アルゴリズムの改良
• Authors: Tan D. Tran, Canh V. Pham, Dung T. K. Ha, Phuong N. H. Pham,
• Abstract要約: 本研究は,knapsack制約下での非モジュラーサイズに対する効率的な並列アルゴリズムを提案する。 我々のアルゴリズムは, 既存の並列処理を 8+epsilon$ から 7+epsilon$ に改良し, 適応複雑性を$O(log n)$ にする。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: This work proposes an efficient parallel algorithm for non-monotone submodular maximization under a knapsack constraint problem over the ground set of size $n$. Our algorithm improves the best approximation factor of the existing parallel one from $8+\epsilon$ to $7+\epsilon$ with $O(\log n)$ adaptive complexity. The key idea of our approach is to create a new alternate threshold algorithmic framework. This strategy alternately constructs two disjoint candidate solutions within a constant number of sequence rounds. Then, the algorithm boosts solution quality without sacrificing the adaptive complexity. Extensive experimental studies on three applications, Revenue Maximization, Image Summarization, and Maximum Weighted Cut, show that our algorithm not only significantly increases solution quality but also requires comparative adaptivity to state-of-the-art algorithms.
• Abstract（参考訳）: 本研究は, クナプサック制約問題の下での非単調部分モジュラー最大化に対する効率よい並列アルゴリズムを, サイズ$n$の基底集合上で提案する。 我々のアルゴリズムは,既存の並列処理の最適近似係数を 8+\epsilon$ から 7+\epsilon$ に改善する。 このアプローチの鍵となる考え方は、新しい代替しきい値アルゴリズムフレームワークを作ることです。 この戦略は、連続ラウンドの定数数内で2つの不随伴候補解を交互に構成する。 そして、適応複雑性を犠牲にすることなく、アルゴリズムはソリューションの品質を高める。 収益の最大化、画像要約、最大重み付けという3つの応用に関する大規模な実験研究により、我々のアルゴリズムは解の質を著しく向上するだけでなく、最先端のアルゴリズムに比較適応性を必要とすることが示された。

関連論文リスト

• Provably Faster Algorithms for Bilevel Optimization via Without-Replacement Sampling [96.47086913559289]
  勾配に基づくアルゴリズムはバイレベル最適化に広く用いられている。 本研究では,より高速な収束率を実現する非置換サンプリングに基づくアルゴリズムを提案する。 合成および実世界の両方のアプリケーションに対してアルゴリズムを検証する。
  論文  参考訳（メタデータ） (2024-11-07T17:05:31Z)
• Practical Parallel Algorithms for Non-Monotone Submodular Maximization [20.13836086815112]
  Submodularは、人工知能の分野における様々な分野に広く応用されている。 部分モジュラーアルゴリズムの並列化可能性の1つは適応的な複雑性であり、これは対象関数に対する多数のクエリを並列に実行できるラウンドの数を示している。 証明可能な近似比と非単調なサブモジュラー問題に対するサブ適応複雑性をともに持つ最初のアルゴリズムを$k$-systemに提案する。
  論文  参考訳（メタデータ） (2023-08-21T11:48:34Z)
• Accelerating Cutting-Plane Algorithms via Reinforcement Learning Surrogates [49.84541884653309]
  凸離散最適化問題に対する現在の標準的なアプローチは、カットプレーンアルゴリズムを使うことである。 多くの汎用カット生成アルゴリズムが存在するにもかかわらず、大規模な離散最適化問題は、難易度に悩まされ続けている。 そこで本研究では,強化学習による切削平面アルゴリズムの高速化手法を提案する。
  論文  参考訳（メタデータ） (2023-07-17T20:11:56Z)
• Accelerated First-Order Optimization under Nonlinear Constraints [73.2273449996098]
  我々は、制約付き最適化のための一階アルゴリズムと非滑らかなシステムの間で、新しい一階アルゴリズムのクラスを設計する。 これらのアルゴリズムの重要な性質は、制約がスパース変数の代わりに速度で表されることである。
  論文  参考訳（メタデータ） (2023-02-01T08:50:48Z)
• Best of Both Worlds: Practical and Theoretically Optimal Submodular Maximization in Parallel [17.462968952951883]
  主アルゴリズムは、独立した関心を持つ可能性のある2つのコンポーネントから組み立てられる。 LINEARSEQの変種は、文献のどのアルゴリズムよりも小さい$O(log(n))$の適応複雑性を持つ。
  論文  参考訳（メタデータ） (2021-11-15T17:10:40Z)
• Minimax Optimization with Smooth Algorithmic Adversaries [59.47122537182611]
  対戦相手が展開するスムーズなアルゴリズムに対して,Min-playerの新しいアルゴリズムを提案する。 本アルゴリズムは,制限周期のない単調進行を保証し,適切な勾配上昇数を求める。
  論文  参考訳（メタデータ） (2021-06-02T22:03:36Z)
• 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)
• An Asymptotically Optimal Primal-Dual Incremental Algorithm for Contextual Linear Bandits [129.1029690825929]
  複数の次元に沿った最先端技術を改善する新しいアルゴリズムを提案する。 非文脈線形帯域の特別な場合において、学習地平線に対して最小限の最適性を確立する。
  論文  参考訳（メタデータ） (2020-10-23T09:12:47Z)
• A Two-Timescale Framework for Bilevel Optimization: Complexity Analysis and Application to Actor-Critic [142.1492359556374]
  双レベル最適化は、2レベル構造を示す問題のクラスである。 このような二段階問題に対処するための2段階近似(TTSA)アルゴリズムを提案する。 本稿では,TTSAフレームワークの特殊な事例として,2段階の自然なアクター・クリティカルポリシー最適化アルゴリズムが有用であることを示す。
  論文  参考訳（メタデータ） (2020-07-10T05:20:02Z)
• Linear-Time Algorithms for Adaptive Submodular Maximization [17.19443570570189]
  まず, 濃度制約を考慮した適応的部分モジュラー問題を提案する。 第二に、完全適応部分モジュラリティの概念を導入する。 提案アルゴリズムは,O(nlogfrac1epsilon)$関数の評価値のみを用いて,$frac1-1/e-epsilon4-2/e-2epsilon$近似比を実現する。
  論文  参考訳（メタデータ） (2020-07-08T15:54:28Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。