論文の概要: Stochastic Multi-round Submodular Optimization with Budget

• arxiv url: http://arxiv.org/abs/2404.13737v2
• Date: Tue, 9 Jul 2024 09:43:57 GMT
• ステータス: 処理完了
• システム内更新日: 2024-07-10 23:21:23.734904
• Title: Stochastic Multi-round Submodular Optimization with Budget
• Title（参考訳）: 予算を考慮した確率的マルチラウンドサブモジュール最適化
• Authors: Vincenzo Auletta, Diodato Ferraioli, Cosimo Vinci,
• Abstract要約: 我々は,複数のラウンドの和を適応的に最大化したい,Em Budgeted Multi-round Submodular Maximization (SBMSm) の問題について検討する。 本稿では,SBMSmの近似アルゴリズムを提案する。まず,各ラウンドに費やされる予算を非適応的に割り当て,各ラウンドに割り当てられた予算を用いて目的関数を適応的に最大化する。
• 参考スコア（独自算出の注目度）: 7.902059578326225
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: In this work we study the problem of {\em Stochastic Budgeted Multi-round Submodular Maximization} (SBMSm), in which we would like to adaptively maximize the sum over multiple rounds of the value of a monotone and submodular objective function defined on a subset of items, subject to the fact that the values of this function depend on the realization of stochastic events and the number of items that we can select over all rounds is limited by a given budget. This problem extends, and generalizes to multiple round settings, well-studied problems such as (adaptive) influence maximization and stochastic probing. We first 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 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. Such algorithm guarantees a $(1-1/e-\epsilon)$-approximation to the optimal adaptive value. Finally, by introducing a metric called {\em budget-adaptivity gap}, we measure how much an optimal policy for SBMSm, that is adaptive in both the budget allocation and item selection, is better than an optimal partially adaptive policy that, as in our greedy algorithm, determined the budget allocation in advance. We show a tight bound of $e/(e-1)$ on the budget-adaptivity gap, and this result implies that our greedy algorithm guarantees the best approximation among all partially adaptive policies.
• Abstract（参考訳）: 本研究では,各項目の集合上で定義された単調および部分モジュラー目的関数の値の複数のラウンドに対する和を適応的に最大化し,その関数の値が確率的事象の実現に依存し,全てのラウンドで選択できる項目の数は,与えられた予算によって制限されるという,SBMSm(Stochastic Budgeted Multi-round Submodular Maximization)の問題について検討する。 この問題は拡張され、(適応的な)影響の最大化や確率的探索のようなよく研究された問題に一般化される。 まず、アイテム数と確率事象が何らかの境界付けられた場合、SBMSmの多項式時間動的プログラミングアルゴリズムが存在することを示す。 次に,SBMSmに対して,まず,各ラウンドに費やされる予算を非適応的に割り当て,次に各ラウンドに割り当てられた予算を用いて,目的関数をグリーディかつ適応的に最大化する,簡単なグリーディ近似アルゴリズムを提案する。 そのようなアルゴリズムは、最適適応値に対する$(1-1/e-\epsilon)$-approximationを保証する。 最後に,予算アダプティビティギャップと呼ばれる指標を導入することにより,予算アロケーションと項目選択の両方に適応するSBMSmの最適政策が,我々の欲求アルゴリズムのように事前に予算アロケーションを決定する最適な部分アダプティビティポリシよりも優れているかを測定する。 予算-適応性ギャップには$e/(e-1)$の厳密な境界が示されており、この結果は、我々の欲求アルゴリズムが全ての部分適応ポリシーの中で最高の近似を保証していることを示唆している。

関連論文リスト

• Biased Pareto Optimization for Subset Selection with Dynamic Cost Constraints [23.67466377818849]
  コスト制約付きサブセット選択は、与えられた予算を超えることなく、単調な目的関数を最大化するための基底セットからサブセットを選択することを目的としている。 我々は、動的環境に適した偏り選択とウォームアップ戦略でPOMCを強化したBPODCを提案する。
  論文  参考訳（メタデータ） (2024-06-18T08:14:51Z)
• Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic Shortest Path [80.60592344361073]
  線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。 エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。 既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
  論文  参考訳（メタデータ） (2024-02-14T07:52:00Z)
• Combinatorial Stochastic-Greedy Bandit [79.1700188160944]
  我々は,選択した$n$のアームセットのジョイント報酬以外の余分な情報が観測されない場合に,マルチアームのバンディット問題に対する新規グリーディ・バンディット(SGB)アルゴリズムを提案する。 SGBは最適化された拡張型コミットアプローチを採用しており、ベースアームの大きなセットを持つシナリオ用に特別に設計されている。
  論文  参考訳（メタデータ） (2023-12-13T11:08:25Z)
• Contextual Combinatorial Bandits with Probabilistically Triggered Arms [55.9237004478033]
  確率的に誘発される腕(C$2$MAB-T)を様々な滑らかさ条件下で検討した。 トリガー変調 (TPM) 条件の下では、C$2$-UC-Tアルゴリズムを考案し、後悔すべき$tildeO(dsqrtT)$を導出する。
  論文  参考訳（メタデータ） (2023-03-30T02:51:00Z)
• 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)
• Minimax Optimization with Smooth Algorithmic Adversaries [59.47122537182611]
  対戦相手が展開するスムーズなアルゴリズムに対して,Min-playerの新しいアルゴリズムを提案する。 本アルゴリズムは,制限周期のない単調進行を保証し,適切な勾配上昇数を求める。
  論文  参考訳（メタデータ） (2021-06-02T22:03:36Z)
• Online Stochastic Optimization with Wasserstein Based Non-stationarity [12.91020811577007]
  有限期間の地平線上の複数の予算制約を持つ一般的なオンライン最適化問題を検討する。 意思決定者の目標は、予算制約の対象となる累積報酬を最大化することである。 この定式化は、オンラインリニアプログラミングやネットワーク収益管理を含む幅広いアプリケーションを取り込む。
  論文  参考訳（メタデータ） (2020-12-13T04:47:37Z)
• 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)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。