論文の概要: Practical $0.385$-Approximation for Submodular Maximization Subject to a Cardinality Constraint

• arxiv url: http://arxiv.org/abs/2405.13994v1
• Date: Wed, 22 May 2024 20:56:57 GMT
• ステータス: 処理完了
• システム内更新日: 2024-05-24 20:04:17.232765
• Title: Practical $0.385$-Approximation for Submodular Maximization Subject to a Cardinality Constraint
• Title（参考訳）: 心的制約を考慮した部分モジュラー最大化のための実用的0.385$-近似法
• Authors: Murad Tukan, Loay Mualem, Moran Feldman,
• Abstract要約: 非単調制約部分モジュラー・サブアニメーションは、様々な機械学習応用において重要な役割を果たす。 既存のアルゴリズムは、近似保証と実用効率のトレードオフにしばしば苦労する。 我々は,$0.385$-approximationの保証と$O(n+k2)$の低い,実用的なクエリ複雑性を組み合わせた新しいアルゴリズムを提案する。
• 参考スコア（独自算出の注目度）: 18.290666675596984
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Non-monotone constrained submodular maximization plays a crucial role in various machine learning applications. However, existing algorithms often struggle with a trade-off between approximation guarantees and practical efficiency. The current state-of-the-art is a recent $0.401$-approximation algorithm, but its computational complexity makes it highly impractical. The best practical algorithms for the problem only guarantee $1/e$-approximation. In this work, we present a novel algorithm for submodular maximization subject to a cardinality constraint that combines a guarantee of $0.385$-approximation with a low and practical query complexity of $O(n+k^2)$. Furthermore, we evaluate the empirical performance of our algorithm in experiments based on various machine learning applications, including Movie Recommendation, Image Summarization, and more. These experiments demonstrate the efficacy of our approach.
• Abstract（参考訳）: 非単調制約部分モジュラー最大化は、様々な機械学習アプリケーションにおいて重要な役割を果たす。 しかし、既存のアルゴリズムは近似保証と実用効率のトレードオフに悩まされることが多い。 現在の最先端技術は、最近の0.401$-approximationアルゴリズムであるが、その計算複雑性により、非常に実用的ではない。 この問題の最良の実践的アルゴリズムは1/e$-approximationのみを保証する。 そこで本研究では, 0.385$-approximation の保証と$O(n+k^2)$の低い, 実用的なクエリ複雑性を組み合わせた, 濃度制約を受ける部分モジュラ最大化のための新しいアルゴリズムを提案する。 さらに,映画推薦,画像要約など,さまざまな機械学習アプリケーションを用いた実験において,提案アルゴリズムの実証性能を評価する。 これらの実験は我々のアプローチの有効性を実証する。

関連論文リスト

• Fairness in Monotone $k$-submodular Maximization: Algorithms and Applications [0.0]
  我々は、fair $k$submodular問題を研究し、実行時間$mathO(knB)$で$frac13$近似を開発する。 我々は$k$-submodular関数がアクセスできないが、ほぼアクセス可能な場合にのみ近似を保証する。
  論文  参考訳（メタデータ） (2024-11-08T04:20:12Z)
• Practical Parallel Algorithms for Non-Monotone Submodular Maximization [20.13836086815112]
  Submodularは、人工知能の分野における様々な分野に広く応用されている。 部分モジュラーアルゴリズムの並列化可能性の1つは適応的な複雑性であり、これは対象関数に対する多数のクエリを並列に実行できるラウンドの数を示している。 証明可能な近似比と非単調なサブモジュラー問題に対するサブ適応複雑性をともに持つ最初のアルゴリズムを$k$-systemに提案する。
  論文  参考訳（メタデータ） (2023-08-21T11:48:34Z)
• Provably Efficient Reinforcement Learning via Surprise Bound [66.15308700413814]
  本稿では,一般値関数近似を用いた効率の良い強化学習アルゴリズムを提案する。 本アルゴリズムは, 線形設定と疎高次元線形設定の両方に適用した場合に, 合理的な後悔境界を達成できる。
  論文  参考訳（メタデータ） (2023-02-22T20:21:25Z)
• Differentially-Private Hierarchical Clustering with Provable Approximation Guarantees [79.59010418610625]
  階層クラスタリングのための微分プライベート近似アルゴリズムについて検討する。 例えば、$epsilon$-DPアルゴリズムは入力データセットに対して$O(|V|2/epsilon)$-additiveエラーを示さなければならない。 本稿では,ブロックを正確に復元する1+o(1)$近似アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-01-31T19:14:30Z)
• Improved Regret for Efficient Online Reinforcement Learning with Linear Function Approximation [69.0695698566235]
  線形関数近似による強化学習と,コスト関数の逆変化について検討した。 本稿では,未知のダイナミクスと帯域幅フィードバックの一般設定に挑戦する,計算効率のよいポリシ最適化アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-01-30T17:26:39Z)
• Resolving the Approximability of Offline and Online Non-monotone DR-Submodular Maximization over General Convex Sets [13.23676270963484]
  DR-サブモジュラー連続関数は、機械学習、通信システム、研究、経済学の分野において多くの実世界の応用を持つ。 tfrac14 (1 - m)$-the-art offline algorithmと一致する時間オンラインアルゴリズムを提示する。 また、我々のアルゴリズムとDuの(2022)オフラインはどちらも強い意味で最適であることを示す。
  論文  参考訳（メタデータ） (2022-10-12T07:04:24Z)
• Minimax Optimization with Smooth Algorithmic Adversaries [59.47122537182611]
  対戦相手が展開するスムーズなアルゴリズムに対して,Min-playerの新しいアルゴリズムを提案する。 本アルゴリズムは,制限周期のない単調進行を保証し,適切な勾配上昇数を求める。
  論文  参考訳（メタデータ） (2021-06-02T22:03:36Z)
• Adaptive Sampling for Fast Constrained Maximization of Submodular Function [8.619758302080891]
  非モノトーンサブモジュラに対する多対数適応性を有するアルゴリズムを一般側制約下で開発する。 本アルゴリズムは,$p$-system 側制約下での非単調部分モジュラ関数の最大化に適している。
  論文  参考訳（メタデータ） (2021-02-12T12:38:03Z)
• Revisiting Modified Greedy Algorithm for Monotone Submodular Maximization with a Knapsack Constraint [75.85952446237599]
  修正されたグリードアルゴリズムは、近似係数が0.305$であることを示す。 最適なデータ依存上界を導出する。 また、分岐やバウンドといったアルゴリズムの効率を大幅に改善するためにも使うことができる。
  論文  参考訳（メタデータ） (2020-08-12T15:40:21Z)
• Reinforcement Learning with General Value Function Approximation: Provably Efficient Approach via Bounded Eluder Dimension [124.7752517531109]
  一般値関数近似を用いた効率の良い強化学習アルゴリズムを確立する。 我々のアルゴリズムは、$d$が複雑性測度である場合、$widetildeO(mathrmpoly(dH)sqrtT)$の後悔の限界を達成することを示す。 我々の理論は線形値関数近似によるRLの最近の進歩を一般化し、環境モデルに対する明示的な仮定をしない。
  論文  参考訳（メタデータ） (2020-05-21T17:36:09Z)

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

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