論文の概要: Stochastic Multi-round Submodular Optimization with Budget
- arxiv url: http://arxiv.org/abs/2404.13737v3
- Date: Tue, 24 Sep 2024 15:58:29 GMT
- ステータス: 翻訳完了
- システム内更新日: 2024-09-26 02:43:46.571009
- Title: Stochastic Multi-round Submodular Optimization with Budget
- Title(参考訳): 予算を考慮した確率的マルチラウンドサブモジュール最適化
- Authors: Vincenzo Auletta, Diodato Ferraioli, Cosimo Vinci,
- Abstract要約: 我々は、アイテムの部分集合上で定義された単調部分モジュラー目的関数の和を、複数のラウンドで適応的に最大化することを目指している。
目的関数はイベントの実現にも依存しており、全てのラウンドで選択できるアイテムの総数は、限られた予算で制限されている。
- 参考スコア(独自算出の注目度): 7.902059578326225
- License:
- Abstract: In this work, we study the Stochastic Budgeted Multi-round Submodular Maximization (SBMSm) problem, where we aim to adaptively maximize the sum, over multiple rounds, of a monotone and submodular objective function defined on subsets of items. The objective function also depends on the realization of stochastic events, and the total number of items we can select over all rounds is bounded by a limited budget. This problem extends, and generalizes to multiple round settings, well-studied problems such as (adaptive) influence maximization and stochastic probing. We show that, if the number of items and stochastic events is somehow bounded, there is a polynomial time dynamic programming algorithm for SBMSm. Then, we provide a simple greedy $1/2(1-1/e-\epsilon)\approx 0.316$-approximation algorithm for SBMSm, that first non-adaptively allocates the budget to be spent at each round, and then greedily and adaptively maximizes the objective function by using the budget assigned at each round. Finally, we introduce the {\em budget-adaptivity gap}, by which we measure how much an adaptive policy for SBMSm is better than an optimal partially adaptive one that, as in our greedy algorithm, determines the budget allocation in advance. We show that the budget-adaptivity gap lies between $e/(e-1)\approx 1.582$ and $2$.
- Abstract(参考訳): 本研究では,SBMSm(Stochastic Budgeted Multi-round Submodular Maximization)問題について考察する。
目的関数は確率的事象の実現にも依存し、全てのラウンドで選択できるアイテムの総数は、限られた予算で制限される。
この問題は拡張され、(適応的な)影響の最大化や確率的探索のようなよく研究された問題に一般化される。
項目数と確率事象が何らかの境界付けられた場合、SBMSmの多項式時間動的プログラミングアルゴリズムが存在することを示す。
次に,SBMSmに対する1/2(1-1/e-\epsilon)\approx 0.316$-approximationアルゴリズムを提案し,まず,各ラウンドに費やされる予算を非適応的に割り当てる。
最後に、我々は、SBMSmの適応ポリシーが最適部分適応ポリシーよりもどれだけ優れているかを測る、予算適応性ギャップ(英語版)を導入し、我々の欲求アルゴリズムのように、前もって予算配分を決定する。
予算と適応性のギャップは$e/(e-1)\approx 1.582$から$2$の間にある。
関連論文リスト
- Archive-based Single-Objective Evolutionary Algorithms for Submodular Optimization [9.852567834643288]
我々は、制約付き部分モジュラー問題の異なるクラスに対して証明可能な成功を収めた、初めての単目的アルゴリズムを紹介する。
私たちのアルゴリズムは$(lambda)$-EAと$(+1)$-EAの変種です。
論文 参考訳(メタデータ) (2024-06-19T10:08:12Z) - Biased Pareto Optimization for Subset Selection with Dynamic Cost Constraints [23.67466377818849]
コスト制約付きサブセット選択は、与えられた予算を超えることなく、単調な目的関数を最大化するための基底セットからサブセットを選択することを目的としている。
我々は、動的環境に適した偏り選択とウォームアップ戦略でPOMCを強化したBPODCを提案する。
論文 参考訳(メタデータ) (2024-06-18T08:14:51Z) - Combinatorial Stochastic-Greedy Bandit [79.1700188160944]
我々は,選択した$n$のアームセットのジョイント報酬以外の余分な情報が観測されない場合に,マルチアームのバンディット問題に対する新規グリーディ・バンディット(SGB)アルゴリズムを提案する。
SGBは最適化された拡張型コミットアプローチを採用しており、ベースアームの大きなセットを持つシナリオ用に特別に設計されている。
論文 参考訳(メタデータ) (2023-12-13T11:08:25Z) - Maximum-Likelihood Inverse Reinforcement Learning with Finite-Time
Guarantees [56.848265937921354]
逆強化学習(IRL)は報酬関数と関連する最適ポリシーを回復することを目的としている。
IRLの多くのアルゴリズムは本質的にネスト構造を持つ。
我々は、報酬推定精度を損なわないIRLのための新しいシングルループアルゴリズムを開発した。
論文 参考訳(メタデータ) (2022-10-04T17:13:45Z) - Minimum Cost Adaptive Submodular Cover [4.680686256929023]
適応部分モジュラ函数の最小コスト被覆の問題を考える。
このアルゴリズムは,すべての$pge 1$に対して,同時に$(p+1)p+1cdot (ln Q+1)p$近似を保証することを示す。
論文 参考訳(メタデータ) (2022-08-17T15:26:47Z) - Robust Subset Selection by Greedy and Evolutionary Pareto Optimization [23.0838604893412]
サブセット選択は、ある目的関数を最大化するために、グラウンドセットからサブセットを選択することを目的としている。
グリーディアルゴリズムは1-e-betagamma$の近似比を得ることができ、$beta$と$gamma$は対象関数の相関と部分モジュラリティ比である。
論文 参考訳(メタデータ) (2022-05-03T11:00:54Z) - Understanding the Effect of Stochasticity in Policy Optimization [86.7574122154668]
最適化手法の優位性は、正確な勾配が用いられるかどうかに大きく依存することを示す。
次に,政策最適化におけるコミット率の概念を紹介する。
第三に、外部のオラクル情報がない場合には、収束を加速するために幾何を利用することと、最適性をほぼ確実に達成することとの間に本質的にトレードオフがあることが示される。
論文 参考訳(メタデータ) (2021-10-29T06:35:44Z) - Minimax Optimization with Smooth Algorithmic Adversaries [59.47122537182611]
対戦相手が展開するスムーズなアルゴリズムに対して,Min-playerの新しいアルゴリズムを提案する。
本アルゴリズムは,制限周期のない単調進行を保証し,適切な勾配上昇数を求める。
論文 参考訳(メタデータ) (2021-06-02T22:03:36Z) - Adaptive Sampling for Fast Constrained Maximization of Submodular
Function [8.619758302080891]
非モノトーンサブモジュラに対する多対数適応性を有するアルゴリズムを一般側制約下で開発する。
本アルゴリズムは,$p$-system 側制約下での非単調部分モジュラ関数の最大化に適している。
論文 参考訳(メタデータ) (2021-02-12T12:38:03Z) - A Two-Timescale Framework for Bilevel Optimization: Complexity Analysis
and Application to Actor-Critic [142.1492359556374]
双レベル最適化は、2レベル構造を示す問題のクラスである。
このような二段階問題に対処するための2段階近似(TTSA)アルゴリズムを提案する。
本稿では,TTSAフレームワークの特殊な事例として,2段階の自然なアクター・クリティカルポリシー最適化アルゴリズムが有用であることを示す。
論文 参考訳(メタデータ) (2020-07-10T05:20:02Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。