論文の概要: Worst-Case Adaptive Submodular Cover
- arxiv url: http://arxiv.org/abs/2210.13694v1
- Date: Tue, 25 Oct 2022 01:38:35 GMT
- ステータス: 処理完了
- システム内更新日: 2022-10-26 15:33:59.227828
- Title: Worst-Case Adaptive Submodular Cover
- Title(参考訳): 最悪ケース適応型サブモジュラカバー
- Authors: Jing Yuan, Shaojie Tang
- Abstract要約: 最悪の場合,適応的部分モジュラー被覆問題について検討する。
タイトな$(log (Q/eta)+1)$-approximationポリシーを開発します。
また、最悪の最大被覆問題も研究している。
- 参考スコア(独自算出の注目度): 19.29174615532181
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: In this paper, we study the adaptive submodular cover problem under the
worst-case setting. This problem generalizes many previously studied problems,
namely, the pool-based active learning and the stochastic submodular set cover.
The input of our problem is a set of items (e.g., medical tests) and each item
has a random state (e.g., the outcome of a medical test), whose realization is
initially unknown. One must select an item at a fixed cost in order to observe
its realization. There is an utility function which is defined over items and
their states. Our goal is to sequentially select a group of items to achieve a
``goal value'' while minimizing the maximum cost across realizations (a.k.a.
worst-case cost). To facilitate our study, we introduce a broad class of
stochastic functions, called \emph{worst-case submodular function}. Assume the
utility function is worst-case submodular, we develop a tight $(\log
(Q/\eta)+1)$-approximation policy, where $Q$ is the ``goal value'' and $\eta$
is the minimum gap between $Q$ and any attainable utility value $\hat{Q}<Q$. We
also study a worst-case maximum-coverage problem, whose goal is to select a
group of items to maximize its worst-case utility subject to a budget
constraint. This is a flipped problem of the minimum-cost-cover problem, and to
solve this problem, we develop a tight $(1-1/e)$-approximation solution.
- Abstract(参考訳): 本稿では,最悪の状況下での適応型サブモジュラーカバー問題について検討する。
この問題は、プールベースのアクティブラーニングと確率的部分モジュラー集合被覆という、以前に研究された多くの問題を一般化する。
問題の入力は一連の項目(例えば、医療試験)であり、各項目はランダムな状態(例えば、医療試験の結果)を持ち、その実現は最初不明である。
その実現を観察するために、一定コストでアイテムを選択する必要がある。
アイテムとその状態に対して定義されたユーティリティ関数がある。
私たちの目標は、‘goal value’を達成するためにアイテムのグループを順次選択し、実現全体(すなわち最悪のケースコスト)の最大コストを最小化することにあります。
本研究では,より広い確率関数のクラスである \emph{worst-case submodular function を導入する。
ここで、$Q$は `goal value'' であり、$\eta$ は $Q$ と任意の達成可能なユーティリティ値 $\hat{Q}<Q$ の最小のギャップである。
また,最大被覆率問題についても検討し,予算制約を課す最悪の実用性を最大化するために,項目群を選択することを目標とした。
これは最小コスト被覆問題のフリップ問題であり、この問題を解決するために、1-1/e)$-approximationの厳密な解を開発した。
関連論文リスト
- Agnostically Learning Multi-index Models with Queries [54.290489524576756]
本稿では,ガウス分布下での非依存学習の課題に対するクエリアクセスのパワーについて検討する。
クエリアクセスは、MIMを不可知的に学習するためのランダムな例よりも大幅に改善されていることを示す。
論文 参考訳(メタデータ) (2023-12-27T15:50:47Z) - Ranking with submodular functions on a budget [17.877243904657952]
サブモジュラー評価と予算制約を有する項目のランク付けのための新しい定式化を提案する。
基本性およびknapsack型予算制約を持つMSR問題に対して,近似保証付き実用的なアルゴリズムを提案する。
論文 参考訳(メタデータ) (2022-04-08T16:29:45Z) - Submodular + Concave [53.208470310734825]
第一次最適化法が凹関数の最大目的値に収束できることはよく確立されている。
本研究では、滑らかな函数凸体(英語版)の行列式を$F(x) = G(x) +C(x)$で始める。
このクラスの函数は、保証がないような凹凸函数と連続DR-部分モジュラ函数の両方の拡張である。
論文 参考訳(メタデータ) (2021-06-09T01:59:55Z) - Beyond Pointwise Submodularity: Non-Monotone Adaptive Submodular
Maximization subject to a Knapsack Constraint [26.171841086317574]
ナップサック制約を受ける非モノトーン適応サブモジュラ問題について研究する。
アイテムの状態は最初不明であり、そのアイテムの状態を明らかにするためにアイテムを選択する必要がある。
私たちの主な貢献は、適応サブモジュール関数を最大化する$frac1$近似を実現するサンプリングベースのランダム化アルゴリズムを開発することです。
論文 参考訳(メタデータ) (2021-04-10T20:11:11Z) - The Power of Subsampling in Submodular Maximization [51.629656762796564]
このアプローチは,既存の手法よりもはるかに単純であるにもかかわらず,最適/最先端の結果をもたらすことを示す。
我々は,映像要約,位置情報要約,映画推薦タスクにおけるアルゴリズムの有効性を実証的に示す。
論文 参考訳(メタデータ) (2021-04-06T20:25:57Z) - Near-Optimal Regret Bounds for Contextual Combinatorial Semi-Bandits
with Linear Payoff Functions [53.77572276969548]
我々は、C$2$UCBアルゴリズムが分割マトロイド制約に対して最適な後悔結合$tildeO(dsqrtkT + dk)$を有することを示した。
一般的な制約に対して,C$2$UCBアルゴリズムで腕の報酬推定値を変更するアルゴリズムを提案する。
論文 参考訳(メタデータ) (2021-01-20T04:29:18Z) - Adaptive Submodular Meta-Learning [28.24164217929491]
適応的なサブモジュラーメタラーニング問題を紹介し,研究する。
私たちの問題の入力は、各アイテムが最初に不明なランダムな状態を持つアイテムのセットです。
本研究の目的は,タスクセット上で最高のパフォーマンスを達成する項目群を適応的に選択することである。
論文 参考訳(メタデータ) (2020-12-11T01:28:55Z) - Fast Adaptive Non-Monotone Submodular Maximization Subject to a Knapsack
Constraint [13.357957711519134]
制約されたサブモジュール問題には、パーソナライズされたレコメンデーション、チーム形成、バイラルマーケティングによる収益化など、さまざまな応用が含まれている。
我々は5.83のランダム化近似を達成し、O(n log n)$禁断時間、すなわち少なくとも$n$を他の最先端アルゴリズムよりも高速に実行する単純なグリーディアルゴリズムを提案する。
そこで我々は,非単調な目的に対する最初の定数近似である9-近似を求め,実データと合成データに改良された性能を示すアルゴリズムの実験評価を行った。
論文 参考訳(メタデータ) (2020-07-09T18:15:01Z) - Adaptive Cascade Submodular Maximization [19.29174615532181]
本研究では,適応条件下でのカスケード部分モジュラー問題について検討する。
本研究の目的は,選択項目の有効性を最大化するために,選択項目の最適シーケンスを特定することである。
論文 参考訳(メタデータ) (2020-07-07T16:21:56Z) - Maximizing Determinants under Matroid Constraints [69.25768526213689]
我々は、$det(sum_i in Sv_i v_i v_itop)$が最大になるような基底を$S$$$$M$とする問題を研究する。
この問題は、実験的なデザイン、商品の公平な割り当て、ネットワーク設計、機械学習など、さまざまな分野に現れている。
論文 参考訳(メタデータ) (2020-04-16T19:16:38Z) - Near-optimal Regret Bounds for Stochastic Shortest Path [63.029132134792555]
最短経路 (SSP) は計画と制御においてよく知られた問題であり、エージェントは最小の総コストで目標状態に到達する必要がある。
任意の学習アルゴリズムは、最悪の場合、少なくとも$Omega(B_star sqrt|S| |A|K)$後悔しなければならない。
論文 参考訳(メタデータ) (2020-02-23T09:10:14Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。