論文の概要: Linear Submodular Maximization with Bandit Feedback

• arxiv url: http://arxiv.org/abs/2407.02601v1
• Date: Tue, 2 Jul 2024 18:40:52 GMT
• ステータス: 処理完了
• システム内更新日: 2024-07-04 18:24:13.248693
• Title: Linear Submodular Maximization with Bandit Feedback
• Title（参考訳）: 帯域フィードバックを用いた線形部分モジュラ最大化
• Authors: Wenjing Chen, Victoria G. Crawford,
• Abstract要約: 準モジュラー目的関数 $f:2UtomathbbR_geq 0$, ここでは $f=sum_i=1dw_iF_i$ に対する近似アルゴリズムの開発を検討する。 F_i$ 関数へのオラクルアクセスが期待できるが、係数 $w_i$ は未知であり、$f$ はノイズの多いクエリによってのみアクセス可能である。 我々のアルゴリズムは、$fの線形構造を利用していないアルゴリズムと比較して、サンプル効率の点で大幅に改善されていることを示す。
• 参考スコア（独自算出の注目度）: 7.926559636438099
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Submodular optimization with bandit feedback has recently been studied in a variety of contexts. In a number of real-world applications such as diversified recommender systems and data summarization, the submodular function exhibits additional linear structure. We consider developing approximation algorithms for the maximization of a submodular objective function $f:2^U\to\mathbb{R}_{\geq 0}$, where $f=\sum_{i=1}^dw_iF_{i}$. It is assumed that we have value oracle access to the functions $F_i$, but the coefficients $w_i$ are unknown, and $f$ can only be accessed via noisy queries. We develop algorithms for this setting inspired by adaptive allocation algorithms in the best-arm identification for linear bandit, with approximation guarantees arbitrarily close to the setting where we have value oracle access to $f$. Finally, we empirically demonstrate that our algorithms make vast improvements in terms of sample efficiency compared to algorithms that do not exploit the linear structure of $f$ on instances of move recommendation.
• Abstract（参考訳）: 帯域フィードバックによる部分モジュラ最適化は,近年,様々な文脈で研究されている。 多様化されたレコメンデータシステムやデータ要約のような現実世界の多くの応用において、部分モジュラ函数は追加の線形構造を示す。 準モジュラー対象関数 $f:2^U\to\mathbb{R}_{\geq 0}$, $f=\sum_{i=1}^dw_iF_{i}$ の最大化のための近似アルゴリズムの開発を検討する。 F_i$ 関数へのオラクルアクセスが期待できるが、係数 $w_i$ は未知であり、$f$ はノイズの多いクエリによってのみアクセス可能である。 本研究では,線形帯域に対する最適アーム識別における適応的アロケーションアルゴリズムに着想を得たこの設定のためのアルゴリズムを開発し,その近似により,値のオラクルアクセスが$f$となるような設定に任意に近づくことが保証される。 最後に、我々のアルゴリズムは、移動推奨インスタンス上の$f$の線形構造を活用できないアルゴリズムと比較して、サンプル効率の点で大幅に改善されていることを実証的に示す。

関連論文リスト

• Fair Submodular Cover [18.37610521373708]
  フェア・サブモジュラー被覆 (FSC) の研究は、与えられた基底集合$U$, 単調部分モジュラー関数 $f:2UtomathbbR_ge 0$, しきい値$tau$ が与えられる。 まず、二項近似比を$(frac1epsilon, 1-O(epsilon))$とするFSCの離散アルゴリズムを導入する。 次に、$(frac1epsilon, 1-O(epsilon))$-を達成する連続アルゴリズムを示す。
  論文  参考訳（メタデータ） (2024-07-05T18:37:09Z)
• Refined Regret for Adversarial MDPs with Linear Function Approximation [50.00022394876222]
  我々は,損失関数が約1,300ドル以上のエピソードに対して任意に変化するような,敵対的決定過程(MDP)の学習を検討する。 本稿では,同じ設定で$tildemathcal O(K2/3)$に対する後悔を改善する2つのアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-01-30T14:37:21Z)
• Best Policy Identification in Linear MDPs [70.57916977441262]
  縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。 複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
  論文  参考訳（メタデータ） (2022-08-11T04:12:50Z)
• Submodular + Concave [53.208470310734825]
  第一次最適化法が凹関数の最大目的値に収束できることはよく確立されている。 本研究では、滑らかな函数凸体(英語版)の行列式を$F(x) = G(x) +C(x)$で始める。 このクラスの函数は、保証がないような凹凸函数と連続DR-部分モジュラ函数の両方の拡張である。
  論文  参考訳（メタデータ） (2021-06-09T01:59:55Z)
• Minimax Optimization with Smooth Algorithmic Adversaries [59.47122537182611]
  対戦相手が展開するスムーズなアルゴリズムに対して,Min-playerの新しいアルゴリズムを提案する。 本アルゴリズムは,制限周期のない単調進行を保証し,適切な勾配上昇数を求める。
  論文  参考訳（メタデータ） (2021-06-02T22:03:36Z)
• The Power of Subsampling in Submodular Maximization [51.629656762796564]
  このアプローチは,既存の手法よりもはるかに単純であるにもかかわらず,最適/最先端の結果をもたらすことを示す。 我々は,映像要約,位置情報要約,映画推薦タスクにおけるアルゴリズムの有効性を実証的に示す。
  論文  参考訳（メタデータ） (2021-04-06T20:25:57Z)
• Practical and Parallelizable Algorithms for Non-Monotone Submodular Maximization with Size Constraint [20.104148319012854]
  サイズ制約に関して、必ずしも単調ではない部分モジュラ函数に対して存在および並列化可能である。 最適な適応性とほぼ最適な複雑性クエリを持つアルゴリズムによって達成される最適な近似係数を、0.193 - varepsilon$に改善する。
  論文  参考訳（メタデータ） (2020-09-03T22:43:55Z)
• Revisiting Modified Greedy Algorithm for Monotone Submodular Maximization with a Knapsack Constraint [75.85952446237599]
  修正されたグリードアルゴリズムは、近似係数が0.305$であることを示す。 最適なデータ依存上界を導出する。 また、分岐やバウンドといったアルゴリズムの効率を大幅に改善するためにも使うことができる。
  論文  参考訳（メタデータ） (2020-08-12T15:40:21Z)
• Linear-Time Algorithms for Adaptive Submodular Maximization [17.19443570570189]
  まず, 濃度制約を考慮した適応的部分モジュラー問題を提案する。 第二に、完全適応部分モジュラリティの概念を導入する。 提案アルゴリズムは,O(nlogfrac1epsilon)$関数の評価値のみを用いて,$frac1-1/e-epsilon4-2/e-2epsilon$近似比を実現する。
  論文  参考訳（メタデータ） (2020-07-08T15:54:28Z)
• Submodular Maximization in Clean Linear Time [42.51873363778082]
  我々は,濃度(サイズ)制約下での部分モジュライメーションの厳密な1-1/e$近似を保証する,最初の決定論的アルゴリズムを提供する。 解に対して許容される濃度が一定であるとき、関数評価のサブ線形数を作るアルゴリズムは、任意の定数比を保証できないことを示す。 我々は,映画推薦,位置情報要約,twitterテキスト要約,ビデオ要約など,複数のリアルタイム機械学習アプリケーションにおいて,我々のアルゴリズムを広範囲に評価する。
  論文  参考訳（メタデータ） (2020-06-16T17:06:45Z)

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

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