論文の概要: Beyond Pointwise Submodularity: Non-Monotone Adaptive Submodular
Maximization in Linear Time
- arxiv url: http://arxiv.org/abs/2008.05004v4
- Date: Tue, 15 Dec 2020 18:41:15 GMT
- ステータス: 処理完了
- システム内更新日: 2022-10-31 10:45:24.205307
- Title: Beyond Pointwise Submodularity: Non-Monotone Adaptive Submodular
Maximization in Linear Time
- Title（参考訳）: 点次部分モジュラリティを超えて:非モノトン適応部分モジュラー最大化
- Authors: Shaojie Tang
- Abstract要約: 濃度制約を受ける非単調適応部分モジュラー問題について検討する。
適応的ランダムグリードアルゴリズムは適応的部分モジュラリティの下で1/e$の近似比を達成することを示す。
我々は,$O(nepsilon-2log epsilon-1)$値オラクルクエリを期待して,1-1/e-epsilon$近似比を高速化するアルゴリズムを提案する。
- 参考スコア（独自算出の注目度）: 17.19443570570189
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In this paper, we study the non-monotone adaptive submodular maximization
problem subject to a cardinality constraint. We first revisit the adaptive
random greedy algorithm proposed in \citep{gotovos2015non}, where they show
that this algorithm achieves a $1/e$ approximation ratio if the objective
function is adaptive submodular and pointwise submodular. It is not clear
whether the same guarantee holds under adaptive submodularity (without
resorting to pointwise submodularity) or not. Our first contribution is to show
that the adaptive random greedy algorithm achieves a $1/e$ approximation ratio
under adaptive submodularity. One limitation of the adaptive random greedy
algorithm is that it requires $O(n\times k)$ value oracle queries, where $n$ is
the size of the ground set and $k$ is the cardinality constraint. Our second
contribution is to develop the first linear-time algorithm for the non-monotone
adaptive submodular maximization problem. Our algorithm achieves a
$1/e-\epsilon$ approximation ratio (this bound is improved to $1-1/e-\epsilon$
for monotone case), using only $O(n\epsilon^{-2}\log \epsilon^{-1})$ value
oracle queries. Notably, $O(n\epsilon^{-2}\log \epsilon^{-1})$ is independent
of the cardinality constraint. For the monotone case, we propose a faster
algorithm that achieves a $1-1/e-\epsilon$ approximation ratio in expectation
with $O(n \log \frac{1}{\epsilon})$ value oracle queries. We also generalize
our study by considering a partition matroid constraint, and develop a
linear-time algorithm for monotone and fully adaptive submodular functions.
- Abstract（参考訳）: 本稿では,濃度制約を受ける非単調適応部分モジュラー最大化問題について検討する。
対象関数が適応部分モジュラーかつポイントワイズ部分モジュラーである場合、このアルゴリズムが1/e$近似比を達成することを示すために、まず、encitep{gotovos2015non} で提案された適応ランダムグリーディアルゴリズムを再検討する。
同じ保証が適応部分モジュラリティ(ポイントワイド部分モジュラリティに頼らない)の下で成立するかどうかは不明である。
我々の最初の貢献は、適応的ランダムグリーディアルゴリズムが適応的部分モジュラリティの下で1/e$近似比を達成することを示すことである。
適応的ランダムグリードアルゴリズムの1つの制限は、$O(n\times k)$ value oracle queryを必要とし、$n$は基底集合のサイズ、$k$は濃度制約である。
第2の貢献は,非単調適応部分モジュラー最大化問題に対する最初の線形時間アルゴリズムの開発である。
このアルゴリズムは1/e-\epsilon$近似比(モノトーンの場合は1-1/e-\epsilon$)を達成し、oracleクエリの値が$o(n\epsilon^{-2}\log \epsilon^{-1})である。
特に、$O(n\epsilon^{-2}\log \epsilon^{-1})$ は濃度制約とは独立である。
モノトーンの場合,$O(n \log \frac{1}{\epsilon})$value oracle queryを期待して,1-1/e-\epsilon$近似比を高速化するアルゴリズムを提案する。
また,分割マトロイド制約を考慮し,モノトーンおよび完全適応部分モジュラー関数に対する線形時間アルゴリズムを開発することで,本研究を一般化する。
関連論文リスト
- Fair Submodular Cover [18.37610521373708]
フェア・サブモジュラー被覆 (FSC) の研究は、与えられた基底集合$U$, 単調部分モジュラー関数 $f:2UtomathbbR_ge 0$, しきい値$tau$ が与えられる。
まず、二項近似比を$(frac1epsilon, 1-O(epsilon))$とするFSCの離散アルゴリズムを導入する。
次に、$(frac1epsilon, 1-O(epsilon))$-を達成する連続アルゴリズムを示す。
論文 参考訳（メタデータ） (2024-07-05T18:37:09Z) - 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) - Best Policy Identification in Linear MDPs [70.57916977441262]
縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。
複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
論文 参考訳（メタデータ） (2022-08-11T04:12:50Z) - Partial-Monotone Adaptive Submodular Maximization [19.29174615532181]
サンプリングベースのポリシが近似比$(m+1)/10$ユーティリティ関数が$m$適応単調かつ適応部分モジュラーであることを示す。
これにより、ユーティリティ機能がほぼ適応的なモノトンである多くの機械学習アプリケーションのバウンダリが改善される。
論文 参考訳（メタデータ） (2022-07-26T12:16:12Z) - 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) - Practical and Parallelizable Algorithms for Non-Monotone Submodular
Maximization with Size Constraint [20.104148319012854]
サイズ制約に関して、必ずしも単調ではない部分モジュラ函数に対して存在および並列化可能である。
最適な適応性とほぼ最適な複雑性クエリを持つアルゴリズムによって達成される最適な近似係数を、0.193 - varepsilon$に改善する。
論文 参考訳（メタデータ） (2020-09-03T22:43:55Z) - 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) - Continuous Submodular Maximization: Beyond DR-Submodularity [48.04323002262095]
最初に、バニラ座標の昇華の単純な変種を証明し、Coordinate-Ascent+ と呼ぶ。
次にCoordinate-Ascent++を提案し、同じ回数のイテレーションを実行しながら(1-1/e-varepsilon)$-approximationを保証する。
Coordinate-Ascent++の各ラウンドの計算は容易に並列化でき、マシン当たりの計算コストは$O(n/sqrtvarepsilon+nlog n)$である。
論文 参考訳（メタデータ） (2020-06-21T06:57:59Z) - Regularized Submodular Maximization at Scale [45.914693923126826]
亜モジュラリティは本質的に多様性、カバレッジ、代表性の概念に関係している。
正規化部分モジュラ函数 $f = g ell$ を行列式部分モジュラ関数 $g$ とモジュラ関数 $ell$ の差分として最大化する手法を提案する。
論文 参考訳（メタデータ） (2020-02-10T02:37:18Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。