論文の概要: Linear-Time Algorithms for Adaptive Submodular Maximization
- arxiv url: http://arxiv.org/abs/2007.04214v1
- Date: Wed, 8 Jul 2020 15:54:28 GMT
- ステータス: 処理完了
- システム内更新日: 2022-11-12 10:09:57.201640
- Title: Linear-Time Algorithms for Adaptive Submodular Maximization
- Title（参考訳）: 適応部分モジュラー最大化のための線形時間アルゴリズム
- Authors: Shaojie Tang
- Abstract要約: まず, 濃度制約を考慮した適応的部分モジュラー問題を提案する。
第二に、完全適応部分モジュラリティの概念を導入する。
提案アルゴリズムは,O(nlogfrac1epsilon)$関数の評価値のみを用いて,$frac1-1/e-epsilon4-2/e-2epsilon$近似比を実現する。
- 参考スコア（独自算出の注目度）: 17.19443570570189
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In this paper, we develop fast algorithms for two stochastic submodular
maximization problems. We start with the well-studied adaptive submodular
maximization problem subject to a cardinality constraint. We develop the first
linear-time algorithm which achieves a $(1-1/e-\epsilon)$ approximation ratio.
Notably, the time complexity of our algorithm is $O(n\log\frac{1}{\epsilon})$
(number of function evaluations) which is independent of the cardinality
constraint, where $n$ is the size of the ground set. Then we introduce the
concept of fully adaptive submodularity, and develop a linear-time algorithm
for maximizing a fully adaptive submoudular function subject to a partition
matroid constraint. We show that our algorithm achieves a
$\frac{1-1/e-\epsilon}{4-2/e-2\epsilon}$ approximation ratio using only
$O(n\log\frac{1}{\epsilon})$ number of function evaluations.
- Abstract（参考訳）: 本稿では,2つの確率的部分モジュラー最大化問題に対する高速アルゴリズムを提案する。
まず,濃度制約を満たした適応部分モジュラー最大化問題から始める。
近似比(1-1/e-\epsilon)$の線形時間アルゴリズムを開発した。
特に、我々のアルゴリズムの時間複雑性は$O(n\log\frac{1}{\epsilon})$(関数評価の数)であり、これは濃度制約とは独立であり、$n$は基底集合のサイズである。
次に,完全適応部分モジュラリティの概念を導入し,分割マトロイド制約を受ける完全適応部分モジュラリティ関数を最大化する線形時間アルゴリズムを開発した。
1-1/e-\epsilon}{4-2/e-2\epsilon}$の近似比をo(n\log\frac{1}{\epsilon})$の関数評価のみを用いて達成することを示す。
関連論文リスト
- 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) - Linear Query Approximation Algorithms for Non-monotone Submodular
Maximization under Knapsack Constraint [16.02833173359407]
この研究は、2つの定数係数近似アルゴリズムを導入し、クナップサック制約の基底集合に対して非単調な部分モジュラーに対して線形なクエリ複雑性を持つ。
$mathsfDLA$は6+epsilon$の近似係数を提供する決定論的アルゴリズムであり、$mathsfRLA$は4+epsilon$の近似係数を持つランダム化アルゴリズムである。
論文 参考訳（メタデータ） (2023-05-17T15:27:33Z) - Refined Regret for Adversarial MDPs with Linear Function Approximation [50.00022394876222]
我々は,損失関数が約1,300ドル以上のエピソードに対して任意に変化するような,敵対的決定過程(MDP)の学習を検討する。
本稿では,同じ設定で$tildemathcal O(K2/3)$に対する後悔を改善する2つのアルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-01-30T14:37:21Z) - Explicit Second-Order Min-Max Optimization Methods with Optimal Convergence Guarantee [86.05440220344755]
我々は,非制約のmin-max最適化問題のグローバルなサドル点を求めるために,不正確な正規化ニュートン型手法を提案し,解析する。
提案手法は有界集合内に留まるイテレートを生成し、その反復は制限関数の項で$O(epsilon-2/3)$内の$epsilon$-saddle点に収束することを示す。
論文 参考訳（メタデータ） (2022-10-23T21:24:37Z) - Best Policy Identification in Linear MDPs [70.57916977441262]
縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。
複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
論文 参考訳（メタデータ） (2022-08-11T04:12:50Z) - 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) - Beyond Pointwise Submodularity: Non-Monotone Adaptive Submodular
Maximization in Linear Time [17.19443570570189]
濃度制約を受ける非単調適応部分モジュラー問題について検討する。
適応的ランダムグリードアルゴリズムは適応的部分モジュラリティの下で1/e$の近似比を達成することを示す。
我々は,$O(nepsilon-2log epsilon-1)$値オラクルクエリを期待して,1-1/e-epsilon$近似比を高速化するアルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-08-11T21:06:52Z) - 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) - Submodular Maximization in Clean Linear Time [42.51873363778082]
我々は,濃度(サイズ)制約下での部分モジュライメーションの厳密な1-1/e$近似を保証する,最初の決定論的アルゴリズムを提供する。
解に対して許容される濃度が一定であるとき、関数評価のサブ線形数を作るアルゴリズムは、任意の定数比を保証できないことを示す。
我々は,映画推薦,位置情報要約,twitterテキスト要約,ビデオ要約など,複数のリアルタイム機械学習アプリケーションにおいて,我々のアルゴリズムを広範囲に評価する。
論文 参考訳（メタデータ） (2020-06-16T17:06:45Z) - Second-order Conditional Gradient Sliding [79.66739383117232]
本稿では,emphSecond-Order Conditional Gradient Sliding (SOCGS)アルゴリズムを提案する。
SOCGSアルゴリズムは、有限個の線形収束反復の後、原始ギャップに二次的に収束する。
実現可能な領域が線形最適化オラクルを通してのみ効率的にアクセスできる場合に有用である。
論文 参考訳（メタデータ） (2020-02-20T17:52:18Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。