論文の概要: Logarithmic Regret for Unconstrained Submodular Maximization Stochastic Bandit

• arxiv url: http://arxiv.org/abs/2410.08578v1
• Date: Fri, 11 Oct 2024 07:07:12 GMT
• ステータス: 処理完了
• システム内更新日: 2024-10-30 23:04:57.376559
• Title: Logarithmic Regret for Unconstrained Submodular Maximization Stochastic Bandit
• Title（参考訳）: 非拘束的部分モジュラー最大化確率帯域に対する対数回帰法
• Authors: Julien Zhou, Pierre Gaillard, Thibaud Rahier, Julyan Arbel,
• Abstract要約: 本稿では,オンラインの非依存サブモジュール問題(Online USM)を,帯域幅のフィードバックを伴う設定で解決する。 この枠組みでは、決定者は、既知の間隔で値を取る非単調な部分モジュラ函数からノイズの報奨を受ける。 本稿では、オフラインおよびオンラインのフル情報設定から、Double-Greedy-Explore-then-Commit(DG-ETC)を適用したDG-ETCを提案する。
• 参考スコア（独自算出の注目度）: 12.096516329746292
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We address the online unconstrained submodular maximization problem (Online USM), in a setting with stochastic bandit feedback. In this framework, a decision-maker receives noisy rewards from a nonmonotone submodular function, taking values in a known bounded interval. This paper proposes Double-Greedy - Explore-then-Commit (DG-ETC), adapting the Double-Greedy approach from the offline and online full-information settings. DG-ETC satisfies a O(d log(dT)) problemdependent upper bound for the 1/2-approximate pseudo-regret, as well as a O(dT^{2/3}log(dT)^{1/3}) problem-free one at the same time, outperforming existing approaches. To that end, we introduce a notion of hardness for submodular functions, characterizing how difficult it is to maximize them with this type of strategy.
• Abstract（参考訳）: オンラインの非制約部分モジュラー最大化問題(Online USM)について,確率的帯域幅フィードバックを用いて検討した。 この枠組みでは、決定者は、既知の有界区間で値を取る非単調な部分モジュラ函数からノイズの報奨を受ける。 本稿では、オフラインおよびオンラインのフル情報設定から、Double-Greedy-Explore-then-Commit(DG-ETC)を適用したDG-ETCを提案する。 DG-ETC は O(d log(dT)) 問題依存上界を 1/2-近似擬回帰に対して満たし、O(dT^{2/3}log(dT)^{1/3}) 問題依存上界を同時に満たし、既存のアプローチより優れている。 そのために, 部分モジュラ函数に対する硬さの概念を導入し, この戦略でそれらを最大化することがいかに困難であるかを特徴付ける。

関連論文リスト

• Bridging the Gap Between General and Down-Closed Convex Sets in Submodular Maximization [8.225819874406238]
  Mualem citemualem23re は、この手法がダウンクローズド制約と非ダウンクローズド制約の間を滑らかにできないことを示す。 本研究では,物体を2つの異なる凸体に自然分解した新しいオフラインおよびオンラインアルゴリズムを提案する。 また、3つのオフラインおよび2つのオンラインアプリケーションにまたがる提案アルゴリズムの優位性を実証的に示す。
  論文  参考訳（メタデータ） (2024-01-17T14:56:42Z)
• Combinatorial Stochastic-Greedy Bandit [79.1700188160944]
  我々は,選択した$n$のアームセットのジョイント報酬以外の余分な情報が観測されない場合に,マルチアームのバンディット問題に対する新規グリーディ・バンディット(SGB)アルゴリズムを提案する。 SGBは最適化された拡張型コミットアプローチを採用しており、ベースアームの大きなセットを持つシナリオ用に特別に設計されている。
  論文  参考訳（メタデータ） (2023-12-13T11:08:25Z)
• Sub-linear Regret in Adaptive Model Predictive Control [56.705978425244496]
  本稿では,STT-MPC (Self-Tuning tube-based Model Predictive Control) について述べる。 システム力学を最初に認識したアルゴリズムと比較して,アルゴリズムの後悔を解析する。
  論文  参考訳（メタデータ） (2023-10-07T15:07:10Z)
• Meta-Learning Adversarial Bandit Algorithms [55.72892209124227]
  我々は,バンディットフィードバックを用いたオンラインメタラーニングについて研究する。 我々は自己協和障壁正規化器を用いてオンラインミラー降下一般化(OMD)をチューニングすることを学ぶ。
  論文  参考訳（メタデータ） (2023-07-05T13:52:10Z)
• Bandit Multi-linear DR-Submodular Maximization and Its Applications on Adversarial Submodular Bandits [21.54858035450694]
  分割マトロイド制約を持つ部分モジュラー帯域に対するサブ線形後悔アルゴリズムを提案する。 バンドイットの逐次部分モジュラーに対して、既存の研究はO(T2/3)$ regret を証明し、近似比は1/2$である。
  論文  参考訳（メタデータ） (2023-05-21T08:51:55Z)
• Randomized Greedy Learning for Non-monotone Stochastic Submodular Maximization Under Full-bandit Feedback [98.29086113546045]
  本稿では,非拘束型マルチアームバンディットのフルバンドフィードバックとサブモジュール性に対する報奨問題について検討する。 RGLは、サブモジュールおよび非サブモジュール設定において、他のフルバンド変種よりも経験的に優れていることを示す。
  論文  参考訳（メタデータ） (2023-02-02T18:52:14Z)
• Supermodular $\mf$-divergences and bounds on lossy compression and generalization error with mutual $\mf$-information [17.441807469515254]
  超モジュラーな$mf$-divergencesを導入し、3つのアプリケーションを提供します。 本稿では,有界入力/出力相互$mf$-informationと一般化レート歪み問題との相関関係について述べる。 我々の境界は、以前最もよく知られていた境界よりも厳密に改善されるレート歪曲関数上の新しい下限に基づいている。
  論文  参考訳（メタデータ） (2022-06-21T09:17:06Z)
• Online Nonsubmodular Minimization with Delayed Costs: From Full Information to Bandit Feedback [98.7678704343537]
  我々は,オンラインおよび近似的オンライン帯域勾配勾配アルゴリズムのいくつかの変種に対する後悔の保証を,特別な構造を持つ非部分モジュラ関数のクラスに焦点をあてる。 我々は,決定の選択と帰属費用の受け取りの遅れが無拘束である場合でも,エージェントの完全な情報と盗賊のフィードバック設定に対する後悔の限界を導出する。
  論文  参考訳（メタデータ） (2022-05-15T08:27:12Z)
• Continuous Submodular Function Maximization [91.17492610120324]
  連続部分モジュラリティ (continuous submodularity) は、幅広い応用を持つ関数のクラスである。 連続的な部分モジュラ最適化の応用は、影響、推論のMAP、フィールドへの推論など多岐にわたる。
  論文  参考訳（メタデータ） (2020-06-24T04:37:31Z)
• Batch greedy maximization of non-submodular functions: Guarantees and applications to experimental design [0.0]
  非部分モジュラーな非退化集合関数の濃度制約に対するグリーディを解析する。 我々の理論的保証は、部分モジュラリティと超モジュラリティ比の組み合わせによって特徴づけられる。
  論文  参考訳（メタデータ） (2020-06-03T18:58:06Z)
• Streaming Submodular Maximization under a $k$-Set System Constraint [42.31117997337689]
  非単調な部分モジュラーのストリーミングを非単調な部分モジュラーのストリーミングに変換する新しいフレームワークを提案する。 また,$k$ible $k$-setシステム制約を考慮したモノトンサブモジュールストリーミングのアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-02-09T12:32:14Z)

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

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