論文の概要: Stochastic Multi-round Submodular Optimization with Budget
- arxiv url: http://arxiv.org/abs/2404.13737v1
- Date: Sun, 21 Apr 2024 18:24:43 GMT
- ステータス: 処理完了
- システム内更新日: 2024-04-23 17:42:20.316811
- Title: Stochastic Multi-round Submodular Optimization with Budget
- Title(参考訳): 予算を考慮した確率的マルチラウンドサブモジュール最適化
- Authors: Vincenzo Auletta, Diodato Ferraioli, Cosimo Vinci,
- Abstract要約: この問題に対して簡単な欲求的アルゴリズムを適用できることが示される。
これは、たとえ予算をラウンドに順応的に割り当てなくても、最適値に対する$(1/2-epsilon)近似を保証する。
- 参考スコア(独自算出の注目度): 7.902059578326225
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: In this work we study the problem of Stochastic Budgeted Multi-round Submodular Maximization (SBMSm), in which we would like to maximize the sum over multiple rounds of the value of a monotone and submodular objective function, subject to the fact that the values of this function depend on the realization of stochastic events and the number of observations that we can make 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 whenever a certain single-round optimization problem can be optimally solved in polynomial time, then there is a polynomial time dynamic programming algorithm that returns the same solution as the optimal algorithm, that can adaptively choose both which observations to make and in which round to have them. Unfortunately, this dynamic programming approach cannot be extended to work when the single-round optimization problem cannot be efficiently solved (even if we allow it would be approximated within an arbitrary small constant). Anyway, in this case we are able to provide a simple greedy algorithm for the problem. It guarantees a $(1/2-\epsilon)$-approximation to the optimal value, even if it non-adaptively allocates the budget to rounds.
- Abstract(参考訳): 本研究では,SBMSm(Stochastic Budgeted Multi-round Submodular Maximization)の問題を考察し,この関数の値が確率的事象の実現に依存し,全てのラウンドで達成できる観測回数が与えられた予算によって制限されるという事実から,モノトーンとサブモジュラー目的関数の値の複数ラウンドの合計を最大化したいと考える。
この問題は拡張され、(適応的な)影響の最大化や確率的探索のようなよく研究された問題に一般化される。
まず、ある単一ラウンド最適化問題を多項式時間で最適に解くことができれば、最適なアルゴリズムと同じ解を返す多項式時間動的プログラミングアルゴリズムが存在し、どの観察を行うか、どのラウンドを持つかを適応的に選択できることを示す。
残念なことに、この動的プログラミングアプローチは、シングルラウンド最適化問題を効率よく解けない場合(任意の小さな定数内で近似することを許すとしても)、機能するように拡張することはできない。
いずれにせよ、このケースでは、この問題に対する単純な欲求的アルゴリズムを提供できる。
たとえ予算をラウンドに順応的に割り当てなくても、最適値に対する$(1/2-\epsilon)$-approxationを保証する。
関連論文リスト
- Accelerated First-Order Optimization under Nonlinear Constraints [73.2273449996098]
我々は、制約付き最適化のための一階アルゴリズムと非滑らかなシステムの間で、新しい一階アルゴリズムのクラスを設計する。
これらのアルゴリズムの重要な性質は、制約がスパース変数の代わりに速度で表されることである。
論文 参考訳(メタデータ) (2023-02-01T08:50:48Z) - Portfolio optimization with discrete simulated annealing [0.0]
離散凸関数と非凸コスト関数の存在下で最適なポートフォリオを求めるための整数最適化法を提案する。
これにより、与えられた品質でソリューションを実現できる。
論文 参考訳(メタデータ) (2022-10-03T10:39:05Z) - Multi-block-Single-probe Variance Reduced Estimator for Coupled
Compositional Optimization [49.58290066287418]
構成問題の複雑さを軽減するために,MSVR (Multi-block-probe Variance Reduced) という新しい手法を提案する。
本研究の結果は, 試料の複雑さの順序や強靭性への依存など, 様々な面で先行して改善された。
論文 参考訳(メタデータ) (2022-07-18T12:03:26Z) - Parallel Quasi-concave set optimization: A new frontier that scales
without needing submodularity [14.93584434176082]
擬凸集合関数のクラスは、単調結合関数への双対クラスとして誘導される。
我々は,グローバルな最大値保証を持つ多種多様な特徴サブセット選択の例を通して,幅広い応用の可能性を示す。
論文 参考訳(メタデータ) (2021-08-19T15:50:41Z) - Minimax Optimization with Smooth Algorithmic Adversaries [59.47122537182611]
対戦相手が展開するスムーズなアルゴリズムに対して,Min-playerの新しいアルゴリズムを提案する。
本アルゴリズムは,制限周期のない単調進行を保証し,適切な勾配上昇数を求める。
論文 参考訳(メタデータ) (2021-06-02T22:03:36Z) - Instance Specific Approximations for Submodular Maximization [45.91235224228292]
実世界のインスタンス上で最適な解に対して,アルゴリズムの性能をベンチマークする手法を模索する。
大きな疑問は、実際に遭遇したインスタンスの最適なソリューションと比較して、アルゴリズムのパフォーマンスを測定する方法です。
我々の主な貢献は、サブモジュラー最小化のための新しいアルゴリズムではなく、サブモジュラーインスタンスのアルゴリズムがいかに最適かを測定する分析手法である。
論文 参考訳(メタデータ) (2021-02-23T19:39:32Z) - Adaptive Sampling for Fast Constrained Maximization of Submodular
Function [8.619758302080891]
非モノトーンサブモジュラに対する多対数適応性を有するアルゴリズムを一般側制約下で開発する。
本アルゴリズムは,$p$-system 側制約下での非単調部分モジュラ関数の最大化に適している。
論文 参考訳(メタデータ) (2021-02-12T12:38:03Z) - Finding Global Minima via Kernel Approximations [90.42048080064849]
関数評価のみに基づく滑らかな関数のグローバル最小化を考える。
本稿では,近似関数を共同でモデル化し,大域的最小値を求める手法を検討する。
論文 参考訳(メタデータ) (2020-12-22T12:59:30Z) - 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) - 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) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。