論文の概要: Contextual Continuum Bandits: Static Versus Dynamic Regret

• arxiv url: http://arxiv.org/abs/2406.05714v2
• Date: Thu, 20 Jun 2024 16:47:04 GMT
• ステータス: 処理完了
• システム内更新日: 2024-06-22 01:26:51.769679
• Title: Contextual Continuum Bandits: Static Versus Dynamic Regret
• Title（参考訳）: コンテキスト連続帯域:静的Versus動的レグレット
• Authors: Arya Akhavan, Karim Lounici, Massimiliano Pontil, Alexandre B. Tsybakov,
• Abstract要約: 本研究では,学習者が側情報ベクトルを逐次受信し,凸集合内の行動を選択する,文脈連続帯域幅問題について検討する。 線形な静的な後悔を実現するアルゴリズムは,任意のアルゴリズムを拡張して,線形な動的後悔を実現することができることを示す。 インテリアポイント法にインスパイアされ,自己協和障壁を用いるアルゴリズムを提案する。
• 参考スコア（独自算出の注目度）: 70.71582850199871
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study the contextual continuum bandits problem, where the learner sequentially receives a side information vector and has to choose an action in a convex set, minimizing a function associated to the context. The goal is to minimize all the underlying functions for the received contexts, leading to a dynamic (contextual) notion of regret, which is stronger than the standard static regret. Assuming that the objective functions are H\"older with respect to the contexts, we demonstrate that any algorithm achieving a sub-linear static regret can be extended to achieve a sub-linear dynamic regret. We further study the case of strongly convex and smooth functions when the observations are noisy. Inspired by the interior point method and employing self-concordant barriers, we propose an algorithm achieving a sub-linear dynamic regret. Lastly, we present a minimax lower bound, implying two key facts. First, no algorithm can achieve sub-linear dynamic regret over functions that are not continuous with respect to the context. Second, for strongly convex and smooth functions, the algorithm that we propose achieves, up to a logarithmic factor, the minimax optimal rate of dynamic regret as a function of the number of queries.
• Abstract（参考訳）: 本研究では,学習者が側情報ベクトルを逐次受信し,コンベックスセットのアクションを選択する場合のコンテキスト連続帯域幅問題について検討し,コンテキストに関連付けられた関数を最小化する。 目標は、受信したコンテキストのすべての基礎となる関数を最小化することであり、標準的な静的な後悔よりも強い、動的な(コンテキスト的な)後悔の概念に繋がる。 目的関数が文脈に関して「より古い」と仮定すると、線形な静的な後悔を達成するアルゴリズムは、線形な動的後悔を達成するために拡張可能であることを示す。 さらに,観測がうるさい場合の凸面と滑らかな関数について検討した。 インテリアポイント法にインスパイアされ,自己協和障壁を用いるアルゴリズムを提案する。 最後に、2つの重要な事実を暗示するミニマックス下界を示す。 第一に、文脈に関して連続でない関数に対して線形な動的後悔を達成するアルゴリズムは存在しない。 第二に、強い凸と滑らかな関数に対して、提案するアルゴリズムは対数係数まで、クエリ数の関数としての動的後悔の最小値である。

関連論文リスト

• Stochastic Zeroth-Order Optimization under Strongly Convexity and Lipschitz Hessian: Minimax Sample Complexity [59.75300530380427]
  本稿では,アルゴリズムが検索対象関数の雑音評価にのみアクセス可能な2次スムーズかつ強い凸関数を最適化する問題を考察する。 本研究は, ミニマックス単純後悔率について, 一致した上界と下界を発達させることにより, 初めて厳密な評価を行ったものである。
  論文  参考訳（メタデータ） (2024-06-28T02:56:22Z)
• An Equivalence Between Static and Dynamic Regret Minimization [10.812831455376218]
  本研究では, 動的後悔最小化は, 拡張決定空間における静的後悔最小化と等価であることを示す。 R_T(u_1,dots,u_T)le tilde Oという形の動的後悔を保証するアルゴリズムを提供する。
  論文  参考訳（メタデータ） (2024-06-03T17:54:58Z)
• Adaptivity and Non-stationarity: Problem-dependent Dynamic Regret for Online Convex Optimization [70.4342220499858]
  本稿では,スムーズさを生かし,問題依存量による動的後悔のT$への依存を補う新しいオンラインアルゴリズムを提案する。 この結果が本質的な難易度に適応しているのは, 既往の結果よりも厳密であり, 最悪の場合, 同一レートの保護が可能であるからである。
  論文  参考訳（メタデータ） (2021-12-29T02:42:59Z)
• Minimax Optimization: The Case of Convex-Submodular [50.03984152441271]
  ミニマックス問題は連続領域を超えて連続離散領域や完全離散領域にまで拡張される。 連続変数に関して目的が凸であり、離散変数に関して部分モジュラーであるような凸-部分モジュラーミニマックス問題のクラスを導入する。 提案アルゴリズムは反復的であり、離散最適化と連続最適化の両方のツールを組み合わせる。
  論文  参考訳（メタデータ） (2021-11-01T21:06:35Z)
• Exact Asymptotics for Linear Quadratic Adaptive Control [6.287145010885044]
  最も単純な非帯域強化学習問題である線形二次制御(LQAC)について検討する。 ステップワイズ更新LQACアルゴリズムの残差,推定誤差,予測誤差の式を導出する。 安定系と不安定系のシミュレーションにおいて、我々の理論はアルゴリズムの有限サンプル挙動を著しくよく記述している。
  論文  参考訳（メタデータ） (2020-11-02T22:43:30Z)
• Dynamic Regret of Convex and Smooth Functions [93.71361250701075]
  非定常環境におけるオンライン凸最適化について検討する。 パフォーマンス指標として動的後悔を選択します。 本研究では, 滑らかさを活かして, 動的後悔をさらに高めることが可能であることを示す。
  論文  参考訳（メタデータ） (2020-07-07T14:10:57Z)
• Exploiting Higher Order Smoothness in Derivative-free Optimization and Continuous Bandits [99.70167985955352]
  強凸関数のゼロ次最適化問題について検討する。 予測勾配降下アルゴリズムのランダム化近似を考察する。 その結果,0次アルゴリズムはサンプルの複雑性や問題パラメータの点でほぼ最適であることが示唆された。
  論文  参考訳（メタデータ） (2020-06-14T10:42:23Z)

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

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