論文の概要: Dynamic Non-monotone Submodular Maximization
- arxiv url: http://arxiv.org/abs/2311.03685v1
- Date: Tue, 7 Nov 2023 03:20:02 GMT
- ステータス: 処理完了
- システム内更新日: 2023-11-08 17:02:12.510886
- Title: Dynamic Non-monotone Submodular Maximization
- Title（参考訳）: 動的非モノトンサブモジュラー最大化
- Authors: Kiarash Banihashem and Leyla Biabani and Samira Goudarzi and
MohammadTaghi Hajiaghayi and Peyman Jabbarzade and Morteza Monemizadeh
- Abstract要約: 濃度制約$k$で非単調部分モジュラ函数を最大化することから、同じ制約の下で単調部分モジュラ函数を最大化することへの還元を示す。
我々のアルゴリズムは、ソリューションの$(epsilon)$-approximateを維持し、期待される$O(epsilon-3k3log3(n)log(k)$ query per updateを使用する。
- 参考スコア（独自算出の注目度）: 11.354502646593607
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Maximizing submodular functions has been increasingly used in many
applications of machine learning, such as data summarization, recommendation
systems, and feature selection. Moreover, there has been a growing interest in
both submodular maximization and dynamic algorithms. In 2020, Monemizadeh and
Lattanzi, Mitrovic, Norouzi{-}Fard, Tarnawski, and Zadimoghaddam initiated
developing dynamic algorithms for the monotone submodular maximization problem
under the cardinality constraint $k$. Recently, there have been some
improvements on the topic made by Banihashem, Biabani, Goudarzi, Hajiaghayi,
Jabbarzade, and Monemizadeh. In 2022, Chen and Peng studied the complexity of
this problem and raised an important open question: "Can we extend [fully
dynamic] results (algorithm or hardness) to non-monotone submodular
maximization?". We affirmatively answer their question by demonstrating a
reduction from maximizing a non-monotone submodular function under the
cardinality constraint $k$ to maximizing a monotone submodular function under
the same constraint. Through this reduction, we obtain the first dynamic
algorithms to solve the non-monotone submodular maximization problem under the
cardinality constraint $k$. Our algorithms maintain an
$(8+\epsilon)$-approximate of the solution and use expected amortized
$O(\epsilon^{-3}k^3\log^3(n)\log(k))$ or $O(\epsilon^{-1}k^2\log^3(k))$ oracle
queries per update, respectively. Furthermore, we showcase the benefits of our
dynamic algorithm for video summarization and max-cut problems on several
real-world data sets.
- Abstract（参考訳）: 部分モジュラ関数の最大化は、データ要約、レコメンデーションシステム、特徴選択など、機械学習の多くのアプリケーションでますます利用されている。
さらに、サブモジュラル最大化と動的アルゴリズムの両方に対する関心が高まっている。
2020年、monemizadeh と lattanzi, mitrovic, norouzi{-}fard, tarnawski, zadimoghaddam は濃度制約 $k$ の下で単調部分モジュラー最大化問題のための動的アルゴリズムの開発を開始した。
最近では、Banihashem、Biabani、Goudarzi、Hajiaghayi、Jabbarzade、Monemizadehによるトピックの改善が行われている。
2022年、チェンとペンはこの問題の複雑さを研究し、重要なオープンな疑問を提起した。
同じ制約の下で単調でない部分モジュラ函数を最大化することから、同じ制約下での単調な部分モジュラ函数を最大化することへの還元を示すことで、これらの疑問に肯定的に答える。
この還元により、濃度制約$k$で非単調部分モジュラー最大化問題を解くための最初の動的アルゴリズムを得る。
我々のアルゴリズムは、ソリューションの$(8+\epsilon)$-approximateを維持し、期待されている$O(\epsilon^{-3}k^3\log^3(n)\log(k))$または$O(\epsilon^{-1}k^2\log^3(k))$oracle query per updateを使用する。
さらに,実世界の複数のデータセット上での映像要約と最大カット問題に対する動的アルゴリズムの利点を示す。
関連論文リスト
- Fast algorithms for k-submodular maximization subject to a matroid
constraint [10.270420338235237]
マトロイド制約の下では、Threshold-Decreasing Algorithmを用いて$k$-submodular関数を最大化する。
我々は$k$-submodular関数に対して$(frac12 - epsilon)$-approximationアルゴリズムを与える。
論文 参考訳（メタデータ） (2023-07-26T07:08:03Z) - Dynamic Algorithms for Matroid Submodular Maximization [11.354502646593607]
マトロイドおよび濃度制約の下でのサブモジュラー複雑性は、機械学習、オークション理論、最適化における幅広い応用の問題である。
本稿では、これらの問題を動的に考慮し、モノトン部分モジュラ関数 $f: 2V rightarrow mathbbR+$ にアクセスでき、基底となる基底集合 $V$ の元の挿入と削除のシーケンス $calmathS$ が与えられる。
マトロイド制約下でのサブモジュラー問題に対する最初の完全動的アルゴリズムを開発する。
論文 参考訳（メタデータ） (2023-06-01T17:54:15Z) - Randomized Greedy Learning for Non-monotone Stochastic Submodular
Maximization Under Full-bandit Feedback [98.29086113546045]
本稿では,非拘束型マルチアームバンディットのフルバンドフィードバックとサブモジュール性に対する報奨問題について検討する。
RGLは、サブモジュールおよび非サブモジュール設定において、他のフルバンド変種よりも経験的に優れていることを示す。
論文 参考訳（メタデータ） (2023-02-02T18:52:14Z) - Submodular + Concave [53.208470310734825]
第一次最適化法が凹関数の最大目的値に収束できることはよく確立されている。
本研究では、滑らかな函数凸体(英語版)の行列式を$F(x) = G(x) +C(x)$で始める。
このクラスの函数は、保証がないような凹凸函数と連続DR-部分モジュラ函数の両方の拡張である。
論文 参考訳（メタデータ） (2021-06-09T01:59:55Z) - The Power of Subsampling in Submodular Maximization [51.629656762796564]
このアプローチは,既存の手法よりもはるかに単純であるにもかかわらず,最適/最先端の結果をもたらすことを示す。
我々は,映像要約,位置情報要約,映画推薦タスクにおけるアルゴリズムの有効性を実証的に示す。
論文 参考訳（メタデータ） (2021-04-06T20:25:57Z) - Revisiting Modified Greedy Algorithm for Monotone Submodular
Maximization with a Knapsack Constraint [75.85952446237599]
修正されたグリードアルゴリズムは、近似係数が0.305$であることを示す。
最適なデータ依存上界を導出する。
また、分岐やバウンドといったアルゴリズムの効率を大幅に改善するためにも使うことができる。
論文 参考訳（メタデータ） (2020-08-12T15:40:21Z) - Linear-Time Algorithms for Adaptive Submodular Maximization [17.19443570570189]
まず, 濃度制約を考慮した適応的部分モジュラー問題を提案する。
第二に、完全適応部分モジュラリティの概念を導入する。
提案アルゴリズムは,O(nlogfrac1epsilon)$関数の評価値のみを用いて,$frac1-1/e-epsilon4-2/e-2epsilon$近似比を実現する。
論文 参考訳（メタデータ） (2020-07-08T15:54:28Z) - Fast and Private Submodular and $k$-Submodular Functions Maximization
with Matroid Constraints [27.070004659301162]
差分プライバシーの枠組みにおいて, マットロイド制約を受ける単調部分モジュラ函数を最大化する問題について検討する。
マットロイド制約を受けるべき$k$submodular関数を保存する最初の$frac12$-approximationアルゴリズムを与える。
論文 参考訳（メタデータ） (2020-06-28T23:18:58Z) - Continuous Submodular Function Maximization [91.17492610120324]
連続部分モジュラリティ (continuous submodularity) は、幅広い応用を持つ関数のクラスである。
連続的な部分モジュラ最適化の応用は、影響、推論のMAP、フィールドへの推論など多岐にわたる。
論文 参考訳（メタデータ） (2020-06-24T04:37:31Z) - Regularized Submodular Maximization at Scale [45.914693923126826]
亜モジュラリティは本質的に多様性、カバレッジ、代表性の概念に関係している。
正規化部分モジュラ函数 $f = g ell$ を行列式部分モジュラ関数 $g$ とモジュラ関数 $ell$ の差分として最大化する手法を提案する。
論文 参考訳（メタデータ） (2020-02-10T02:37:18Z) - Streaming Submodular Maximization under a $k$-Set System Constraint [42.31117997337689]
非単調な部分モジュラーのストリーミングを非単調な部分モジュラーのストリーミングに変換する新しいフレームワークを提案する。
また,$k$ible $k$-setシステム制約を考慮したモノトンサブモジュールストリーミングのアルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-02-09T12:32:14Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。