論文の概要: A Jointly Efficient and Optimal Algorithm for Heteroskedastic Generalized Linear Bandits with Adversarial Corruptions

• arxiv url: http://arxiv.org/abs/2602.10971v1
• Date: Wed, 11 Feb 2026 16:01:06 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-02-12 21:44:02.093812
• Title: A Jointly Efficient and Optimal Algorithm for Heteroskedastic Generalized Linear Bandits with Adversarial Corruptions
• Title（参考訳）: 逆転破壊を伴うヘテロスケダス性一般化線形帯域の高効率化と最適解法
• Authors: Sanghwa Kim, Junghyun Lee, Se-Young Yun,
• Abstract要約: HCW-GLB-OMDはオンラインミラー降下(OMD)に基づく推定器とヘッセンに基づく信頼性重みの2つの要素から構成される。 我々のアルゴリズムは, 汚職項の最大$$-factor, インスタンスワイドの最小値最適度を, 敵の汚職を伴うヘテロスケダスティックGLBの様々なインスタンスで同時に達成する。
• 参考スコア（独自算出の注目度）: 42.12102281662932
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We consider the problem of heteroskedastic generalized linear bandits (GLBs) with adversarial corruptions, which subsumes various stochastic contextual bandit settings, including heteroskedastic linear bandits and logistic/Poisson bandits. We propose HCW-GLB-OMD, which consists of two components: an online mirror descent (OMD)-based estimator and Hessian-based confidence weights to achieve corruption robustness. This is computationally efficient in that it only requires ${O}(1)$ space and time complexity per iteration. Under the self-concordance assumption on the link function, we show a regret bound of $\tilde{O}\left( d \sqrt{\sum_t g(τ_t) \dotμ_{t,\star}} + d^2 g_{\max} κ+ d κC \right)$, where $\dotμ_{t,\star}$ is the slope of $μ$ around the optimal arm at time $t$, $g(τ_t)$'s are potentially exogenously time-varying dispersions (e.g., $g(τ_t) = σ_t^2$ for heteroskedastic linear bandits, $g(τ_t) = 1$ for Bernoulli and Poisson), $g_{\max} = \max_{t \in [T]} g(τ_t)$ is the maximum dispersion, and $C \geq 0$ is the total corruption budget of the adversary. We complement this with a lower bound of $\tildeΩ(d \sqrt{\sum_t g(τ_t) \dotμ_{t,\star}} + d C)$, unifying previous problem-specific lower bounds. Thus, our algorithm achieves, up to a $κ$-factor in the corruption term, instance-wise minimax optimality simultaneously across various instances of heteroskedastic GLBs with adversarial corruptions.
• Abstract（参考訳）: 本稿では, 対数汚職を伴うヘテロスケダスティック一般化線形包帯(GLB)の問題について考察する。 HCW-GLB-OMDは,オンラインミラー降下(OMD)に基づく推定器とヘシアンに基づく信頼性重みの2つの要素から構成される。 これは計算的に効率的であり、1イテレーションあたりの空間と時間の複雑さが${O}(1)$である。 リンク関数上の自己一致の仮定では、$\tilde{O}\left(d \sqrt{\sum_t g(τ_t) \dotμ_{t,\star}} + d^2 g_{\max} κ+ d κC \right)$, ここで、$\dotμ_{t,\star}$は最適な腕の周りの$μ$の傾斜である。 これを $\tildeΩ(d \sqrt{\sum_t g(τ_t) \dotμ_{t,\star}} + d C)$ の下界で補う。 そこで本アルゴリズムは, 汚職項において最大$κ$-factor を達成するとともに, 逆汚職を伴うヘテロスケダティックなGLBの様々なインスタンスに対して, インスタンスワイドの最小最適度を同時に達成する。

関連論文リスト

• Robust Distribution Learning with Local and Global Adversarial Corruptions [17.22168727622332]
  誤差を$sqrtvarepsilon k + rho + tildeO(dsqrtkn-1/(k lor2)$で有界な共分散を持つ場合、効率的な有限サンプルアルゴリズムを開発する。 我々の効率的な手順は、理想的だが難解な2-ワッサーシュタイン射影推定器の新たなトレースノルム近似に依存する。
  論文  参考訳（メタデータ） (2024-06-10T17:48:36Z)
• Restless Linear Bandits [5.00389879175348]
  未知の$mathbbRd$-valued stationary $varphi$-mixing sequence of parameters $(theta_t,t in mathbbN)$ が存在すると仮定される。 指数混合率が$theta_t$の場合、LinMix-UCBと呼ばれる楽観的なアルゴリズムが提案される。
  論文  参考訳（メタデータ） (2024-05-17T14:37:39Z)
• Efficient Frameworks for Generalized Low-Rank Matrix Bandit Problems [61.85150061213987]
  一般化線形モデル (GLM) フレームワークを用いて, citelu2021low で提案した一般化低ランク行列帯域問題について検討する。 既存のアルゴリズムの計算不可能性と理論的制約を克服するため,まずG-ESTTフレームワークを提案する。 G-ESTT は $tildeO(sqrt(d_1+d_2)3/2Mr3/2T)$ bound of regret を達成でき、G-ESTS は $tildeO を達成できることを示す。
  論文  参考訳（メタデータ） (2024-01-14T14:14:19Z)
• Best-of-Both-Worlds Algorithms for Linear Contextual Bandits [11.94312915280916]
  両世界のベスト・オブ・ワールドズ・アルゴリズムを$K$武器付き線形文脈包帯に対して検討する。 我々のアルゴリズムは、敵対的体制と敵対的体制の両方において、ほぼ最適の後悔の限界を提供する。
  論文  参考訳（メタデータ） (2023-12-24T08:27:30Z)
• Corruption-Robust Offline Reinforcement Learning with General Function Approximation [60.91257031278004]
  一般関数近似を用いたオフライン強化学習(RL)における劣化問題について検討する。 我々のゴールは、崩壊しないマルコフ決定プロセス(MDP)の最適方針に関して、このような腐敗に対して堅牢で、最適でないギャップを最小限に抑える政策を見つけることである。
  論文  参考訳（メタデータ） (2023-10-23T04:07:26Z)
• Minimax Rates for Robust Community Detection [19.229475414802213]
  逆ノードの破損を伴うブロックモデルにおけるコミュニティ検出の問題点について検討する。 我々の主な結果は、$epsilon$-fraction of corruption and unbounded error $O(epsilon) + e-fracC2 (1 pm o(1))$ where $C = (sqrta - sqrtb)2$ is the signal-to-noise ratio。 アルゴリズムがさらに機能するという意味では、我々のアルゴリズムは2倍に損なわれていることを示す。
  論文  参考訳（メタデータ） (2022-07-25T04:45:16Z)
• Corralling a Larger Band of Bandits: A Case Study on Switching Regret for Linear Bandits [99.86860277006318]
  本稿では,一組の逆アルゴリズムを組み合わせ,学習することの問題点について考察する。 Agarwal et al. の CORRAL はこの目標を、$widetildeO(sqrtd S T)$ の残酷なオーバーヘッドで達成している。 この問題に触発されて、後悔のオーバーヘッドが百万ドルにしか依存しない大規模バンディットアルゴリズムのバンドを囲む新しいレシピを提案する。
  論文  参考訳（メタデータ） (2022-02-12T21:55:44Z)
• Stochastic Linear Bandits Robust to Adversarial Attacks [117.665995707568]
  我々はロバスト位相除去アルゴリズムの2つの変種を提供し、その1つは$C$を知っており、もう1つはそうでない。 いずれの変種も、倒壊しない場合には、それぞれ$C = 0$ となり、それぞれ追加の加法項が生じる。 文脈的設定では、単純な欲求的アルゴリズムは、明示的な探索を行わず、C$を知らないにもかかわらず、ほぼ最適加法的後悔項で証明可能な堅牢性を示す。
  論文  参考訳（メタデータ） (2020-07-07T09:00:57Z)
• Curse of Dimensionality on Randomized Smoothing for Certifiable Robustness [151.67113334248464]
  我々は、他の攻撃モデルに対してスムースな手法を拡張することは困難であることを示す。 我々はCIFARに関する実験結果を示し,その理論を検証した。
  論文  参考訳（メタデータ） (2020-02-08T22:02:14Z)

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

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