論文の概要: Robust Adaptive Submodular Maximization
- arxiv url: http://arxiv.org/abs/2107.11333v2
- Date: Mon, 26 Jul 2021 03:11:31 GMT
- ステータス: 処理完了
- システム内更新日: 2021-07-27 10:48:11.297010
- Title: Robust Adaptive Submodular Maximization
- Title（参考訳）: robust adaptive submodular maximization
- Authors: Shaojie Tang
- Abstract要約: 適応的部分モジュラー最適化問題,すなわち最悪の適応的部分モジュラーとロバストな部分モジュラーの2つの変種について検討する。
我々は,最適な最悪のケースユーティリティに対して,$frac1p+1$制約比を達成する適応的な最悪のケース欲求政策を開発する。
また、プールベースアクティブ学習サブモジュールセットカバーや適応型バイラルマーケティングなど、理論的結果のいくつかの応用についても述べる。
- 参考スコア（独自算出の注目度）: 26.171841086317574
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Most of existing studies on adaptive submodular optimization focus on the
average-case, i.e., their objective is to find a policy that maximizes the
expected utility over a known distribution of realizations. However, a policy
that has a good average-case performance may have very poor performance under
the worst-case realization. In this study, we propose to study two variants of
adaptive submodular optimization problems, namely, worst-case adaptive
submodular maximization and robust submodular maximization. The first problem
aims to find a policy that maximizes the worst-case utility and the latter one
aims to find a policy, if any, that achieves both near optimal average-case
utility and worst-case utility simultaneously. We introduce a new class of
stochastic functions, called \emph{worst-case submodular function}. For the
worst-case adaptive submodular maximization problem subject to a $p$-system
constraint, we develop an adaptive worst-case greedy policy that achieves a
$\frac{1}{p+1}$ approximation ratio against the optimal worst-case utility if
the utility function is worst-case submodular. For the robust adaptive
submodular maximization problem subject to a cardinality constraint, if the
utility function is both worst-case submodular and adaptive submodular, we
develop a hybrid adaptive policy that achieves an approximation close to
$1-e^{-\frac{1}{2}}$ under both worst case setting and average case setting
simultaneously. We also describe several applications of our theoretical
results, including pool-base active learning, stochastic submodular set cover
and adaptive viral marketing.
- Abstract（参考訳）: 適応的部分モジュラー最適化に関する既存の研究の多くは、平均ケース、すなわち、その目的は、既知の実現の分布よりも期待される効用を最大化するポリシーを見つけることである。
しかし、平均的なパフォーマンスが良いポリシーは、最悪のケースではパフォーマンスが非常に悪いかもしれない。
本研究では,適応部分モジュラー最適化問題の2つの変種,すなわち,最悪の場合適応部分モジュラー最大化とロバスト部分モジュラー最大化について検討する。
最初の問題は、最悪のケースのユーティリティを最大化するポリシーを見つけることであり、後者は、少なくとも、最適な平均ケースのユーティリティと最悪のケースのユーティリティの両方を同時に達成するポリシーを見つけることを目的としている。
確率関数の新しいクラスである \emph{worst-case submodular function} を導入する。
p$-system制約を受ける最悪のケース適応サブモジュラー最大化問題に対して、ユーティリティ関数が最悪のケースサブモジュラーである場合、最適なワーストケースユーティリティに対する$\frac{1}{p+1}$近似比を達成する適応的最悪のケースグリーディポリシーを開発する。
基数制約を受けるロバスト適応部分モジュラー最大化問題に対して、実用関数が最悪ケース部分モジュラーかつ適応部分モジュラーの両方である場合、最悪のケース設定と平均ケース設定の両方で1-e^{-\frac{1}{2}}$に近い近似を同時に達成するハイブリッド適応ポリシーを開発する。
また、プールベースアクティブラーニング、確率的サブモジュール集合被覆、適応的バイラルマーケティングなど、理論的結果のいくつかの応用について述べる。
関連論文リスト
- Provably Mitigating Overoptimization in RLHF: Your SFT Loss is Implicitly an Adversarial Regularizer [52.09480867526656]
人間の嗜好を学習する際の分布変化と不確実性の一形態として,不一致の原因を同定する。
過度な最適化を緩和するために、まず、逆選択された報酬モデルに最適なポリシーを選択する理論アルゴリズムを提案する。
報奨モデルとそれに対応する最適ポリシーの等価性を用いて、優先最適化損失と教師付き学習損失を組み合わせた単純な目的を特徴とする。
論文 参考訳（メタデータ） (2024-05-26T05:38:50Z) - Towards Efficient Exact Optimization of Language Model Alignment [93.39181634597877]
嗜好データから直接ポリシーを最適化するために、直接選好最適化(DPO)が提案された。
問題の最適解に基づいて導出されたDPOが,現実の最適解の妥協平均探索近似に繋がることを示す。
本稿では、アライメント目的の効率的な精度最適化(EXO)を提案する。
論文 参考訳（メタデータ） (2024-02-01T18:51:54Z) - Non-monotone Sequential Submodular Maximization [13.619980548779687]
我々は、$k$の重み付けが最大になるように、基底セット$V$から$k$の項目群を選択してランク付けすることを目指している。
本研究の結果は,レコメンデーションシステムや最適化など,様々な分野に影響を及ぼす。
論文 参考訳（メタデータ） (2023-08-16T19:32:29Z) - Balancing Utility and Fairness in Submodular Maximization (Technical
Report) [27.20340546154524]
実用性と公平性のバランスをとるために,emphBi Maxim Submodularization (BSM) と呼ばれる新しい問題を提案する。
BSMは任意の定数係数で近似できないため、効率的なインスタンス依存近似スキームの設計に焦点をあてる。
論文 参考訳（メタデータ） (2022-11-02T09:38:08Z) - Group Equality in Adaptive Submodular Maximization [13.619980548779687]
非適応的条件と適応的条件の両方で群等式制約を受ける古典的部分モジュラー問題について検討する。
この問題に対する最初の定数近似アルゴリズムを開発した。
論文 参考訳（メタデータ） (2022-07-07T15:12:02Z) - Partial-Adaptive Submodular Maximization [28.24164217929491]
適応部分モジュラー問題に関するほとんどの研究は、完全に適応的な設定に焦点を当てている。
本稿では,バッチ内で複数の選択を同時に行うことができる部分適応部分モジュラーの問題について検討する。
我々のアプローチは、過去の選択から観察を待つ時間を削減するとともに、適応性の利点を享受します。
論文 参考訳（メタデータ） (2021-11-01T14:48:41Z) - Bayesian Optimization for Min Max Optimization [77.60508571062958]
そこで我々は,最適化すべき関数が事前に分かっていないような設定でMin Max Optimizationを実行するアルゴリズムを提案する。
我々は,改善を期待する2つの獲得機能とガウス過程の上部信頼境界を拡張した。
これらの取得機能は、ベンチマーク設定よりも高速に収束する、より良いソリューションを可能にすることを示す。
論文 参考訳（メタデータ） (2021-07-29T06:49:34Z) - Beyond Pointwise Submodularity: Non-Monotone Adaptive Submodular
Maximization subject to a Knapsack Constraint [26.171841086317574]
ナップサック制約を受ける非モノトーン適応サブモジュラ問題について研究する。
アイテムの状態は最初不明であり、そのアイテムの状態を明らかにするためにアイテムを選択する必要がある。
私たちの主な貢献は、適応サブモジュール関数を最大化する$frac1$近似を実現するサンプリングベースのランダム化アルゴリズムを開発することです。
論文 参考訳（メタデータ） (2021-04-10T20:11:11Z) - Planning with Submodular Objective Functions [118.0376288522372]
準モジュラー目的関数を用いて計画を行い、累積報酬を最大化する代わりに、劣モジュラー関数によって誘導される値の最大化を目標とする。
本フレームワークは, 基本性制約を特別な場合として, 標準計画と準モジュラー目標を仮定する。
論文 参考訳（メタデータ） (2020-10-22T16:55:12Z) - Continuous Submodular Function Maximization [91.17492610120324]
連続部分モジュラリティ (continuous submodularity) は、幅広い応用を持つ関数のクラスである。
連続的な部分モジュラ最適化の応用は、影響、推論のMAP、フィールドへの推論など多岐にわたる。
論文 参考訳（メタデータ） (2020-06-24T04:37:31Z) - Convergence of adaptive algorithms for weakly convex constrained
optimization [59.36386973876765]
モローエンベロープの勾配のノルムに対して$mathcaltilde O(t-1/4)$収束率を証明する。
我々の分析では、最小バッチサイズが1ドル、定数が1位と2位のモーメントパラメータが1ドル、そしておそらくスムーズな最適化ドメインで機能する。
論文 参考訳（メタデータ） (2020-06-11T17:43:19Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。