論文の概要: 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の厳密な解を開発した。
関連論文リスト
- Optimal level set estimation for non-parametric tournament and crowdsourcing problems [49.75262185577198]
クラウドソーシングによって動機づけられた我々は、$d$の質問に対する$n$の専門家の回答の正しさを部分的に観察する問題を考える。
本稿では、専門家$i$が疑問に答える確率を含む行列$M$が、行と列の置換までの双等方性であることを仮定する。
我々は,この分類問題に対して最小限のアルゴリズムを最適に構築する。
論文 参考訳（メタデータ） (2024-08-27T18:28:31Z) - A Dynamic Algorithm for Weighted Submodular Cover Problem [11.354502646593607]
基底集合の要素を挿入・削除する動的設定における部分モジュラー被覆問題について検討する。
本稿では,更新毎に多対数クエリの複雑さを用いてO(epsilon-1)$-bicriteria近似を求めるランダム化アルゴリズムを提案する。
論文 参考訳（メタデータ） (2024-07-13T21:00:41Z) - 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) - Agnostically Learning Multi-index Models with Queries [54.290489524576756]
本稿では,ガウス分布下での非依存学習の課題に対するクエリアクセスのパワーについて検討する。
クエリアクセスは、MIMを不可知的に学習するためのランダムな例よりも大幅に改善されていることを示す。
論文 参考訳（メタデータ） (2023-12-27T15:50:47Z) - Minimum Cost Adaptive Submodular Cover [4.680686256929023]
適応部分モジュラ函数の最小コスト被覆の問題を考える。
このアルゴリズムは,すべての$pge 1$に対して,同時に$(p+1)p+1cdot (ln Q+1)p$近似を保証することを示す。
論文 参考訳（メタデータ） (2022-08-17T15:26: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) - 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) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。