論文の概要: Sparse Optimistic Information Directed Sampling

• arxiv url: http://arxiv.org/abs/2510.24234v1
• Date: Tue, 28 Oct 2025 09:42:15 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-10-29 15:35:36.996902
• Title: Sparse Optimistic Information Directed Sampling
• Title（参考訳）: サンプリングによるスパース最適化情報
• Authors: Ludovic Schwartz, Hamish Flynn, Gergely Neu,
• Abstract要約: 我々は,SOIDSが最適に情報と後悔のバランスをとることができることを示す。 我々は,SOIDSがデータ豊かさとデータ貧弱さの両面において,最善の最悪の後悔を同時に達成していることを示す。
• 参考スコア（独自算出の注目度）: 11.986224119327387
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Many high-dimensional online decision-making problems can be modeled as stochastic sparse linear bandits. Most existing algorithms are designed to achieve optimal worst-case regret in either the data-rich regime, where polynomial depen- dence on the ambient dimension is unavoidable, or the data-poor regime, where dimension-independence is possible at the cost of worse dependence on the num- ber of rounds. In contrast, the sparse Information Directed Sampling (IDS) algo- rithm satisfies a Bayesian regret bound that has the optimal rate in both regimes simultaneously. In this work, we explore the use of Sparse Optimistic Informa- tion Directed Sampling (SOIDS) to achieve the same adaptivity in the worst-case setting, without Bayesian assumptions. Through a novel analysis that enables the use of a time-dependent learning rate, we show that SOIDS can optimally balance information and regret. Our results extend the theoretical guarantees of IDS, pro- viding the first algorithm that simultaneously achieves optimal worst-case regret in both the data-rich and data-poor regimes. We empirically demonstrate the good performance of SOIDS.
• Abstract（参考訳）: 多くの高次元オンライン意思決定問題は確率的スパース線形帯域としてモデル化できる。 既存のアルゴリズムのほとんどは、周囲次元の多項式デペン・デエンスが避けられないデータリッチ・レシエーションや、次元独立性が可能なデータポーア・レシエーションにおいて、ラウンドの無数の悪さを犠牲にして最適な最悪ケースの後悔を実現するように設計されている。 対照的に、スパース情報指令サンプリング(IDS)アルゴリトムは、両政権で同時に最適なレートを持つベイズ的後悔境界を満たす。 本研究では, ベイズ的仮定を使わずに, 最悪の場合において同じ適応性を実現するために, スパース最適インフォーマ-イオン誘導サンプリング (SOIDS) を用いる方法について検討する。 時間依存学習率の活用を可能にする新たな分析により,SOIDSは情報と後悔のバランスを最適に保てることを示す。 以上の結果から,IDSの理論的保証が拡張され,データ豊かさとデータ貧弱さの両面において,最善の最悪の後悔を同時に達成するアルゴリズムがプロバイディングされた。 我々は,SOIDSの優れた性能を実証的に実証した。

関連論文リスト

• Generalized Linear Bandits: Almost Optimal Regret with One-Pass Update [60.414548453838506]
  非線形リンク関数を組み込んで古典線形モデルを拡張したコンテキスト型多武装バンディットフレームワークである一般化線形バンディット問題(GLB)について検討する。 GLBは現実世界のシナリオに広く適用できるが、その非線形性は計算効率と統計効率の両方を達成する上で大きな課題をもたらす。 本稿では,$mathcalO(1)$時間と1ラウンドあたりの空間複雑度をほぼ最適に再現するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2025-07-16T02:24:21Z)
• Optimizing Input Data Collection for Ranking and Selection [2.3708672042234213]
  予算が与えられた入力データとシミュレーションデータを収集する逐次サンプリングアルゴリズムを設計する。 サンプリング予算の増加に伴い,MPBの最適性の後方確率は指数速度で1つに収束することを示す。 シミュレーション出力平均予測を改善するため,カーネルリッジ回帰を用いてOSARを拡張した。
  論文  参考訳（メタデータ） (2025-02-23T17:33:43Z)
• Provably Mitigating Overoptimization in RLHF: Your SFT Loss is Implicitly an Adversarial Regularizer [52.09480867526656]
  人間の嗜好を学習する際の分布変化と不確実性の一形態として,不一致の原因を同定する。 過度な最適化を緩和するために、まず、逆選択された報酬モデルに最適なポリシーを選択する理論アルゴリズムを提案する。 報奨モデルとそれに対応する最適ポリシーの等価性を用いて、優先最適化損失と教師付き学習損失を組み合わせた単純な目的を特徴とする。
  論文  参考訳（メタデータ） (2024-05-26T05:38:50Z)
• Differentially Private Optimization with Sparse Gradients [60.853074897282625]
  微分プライベート(DP)最適化問題を個人勾配の空間性の下で検討する。 これに基づいて、スパース勾配の凸最適化にほぼ最適な速度で純粋および近似DPアルゴリズムを得る。
  論文  参考訳（メタデータ） (2024-04-16T20:01:10Z)
• Mean Estimation with User-Level Privacy for Spatio-Temporal IoT Datasets [5.34194012533815]
  実世界のデータセット上での低い推定誤差を保証するために,ユーザレベルの差分プライベートアルゴリズムを開発した。 インド都市のITMS(Intelligent Traffic Management System)データを用いて,本アルゴリズムを検証した。 ファストケースデータセットにおける擬似ユーザ生成に基づくアルゴリズムの性能を,ミニマックスアプローチを用いて評価する。
  論文  参考訳（メタデータ） (2024-01-29T06:21:29Z)
• Asymptotically Optimal Information-Directed Sampling [37.816004557470556]
  有限時間で最適であり、最悪の場合に最適である有限個の動作を持つ線形包帯に対する単純かつ効率的なアルゴリズムを導入する。 この手法は、高頻度情報指向サンプリング(IDS)フレームワークに基づいており、低境界を定義する最適化問題によって与えられる情報ゲインのサロゲートである。
  論文  参考訳（メタデータ） (2020-11-11T18:01:59Z)

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

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