論文の概要: Generalized Linear Bandits: Almost Optimal Regret with One-Pass Update

• arxiv url: http://arxiv.org/abs/2507.11847v1
• Date: Wed, 16 Jul 2025 02:24:21 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-07-17 19:00:11.20049
• Title: Generalized Linear Bandits: Almost Optimal Regret with One-Pass Update
• Title（参考訳）: 一般線形帯域幅:ワンパスアップデートによるほぼ最適レグレット
• Authors: Yu-Jie Zhang, Sheng-An Xu, Peng Zhao, Masashi Sugiyama,
• Abstract要約: 非線形リンク関数を組み込んで古典線形モデルを拡張したコンテキスト型多武装バンディットフレームワークである一般化線形バンディット問題(GLB)について検討する。 GLBは現実世界のシナリオに広く適用できるが、その非線形性は計算効率と統計効率の両方を達成する上で大きな課題をもたらす。 本稿では,$mathcalO(1)$時間と1ラウンドあたりの空間複雑度をほぼ最適に再現するアルゴリズムを提案する。
• 参考スコア（独自算出の注目度）: 60.414548453838506
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the generalized linear bandit (GLB) problem, a contextual multi-armed bandit framework that extends the classical linear model by incorporating a non-linear link function, thereby modeling a broad class of reward distributions such as Bernoulli and Poisson. While GLBs are widely applicable to real-world scenarios, their non-linear nature introduces significant challenges in achieving both computational and statistical efficiency. Existing methods typically trade off between two objectives, either incurring high per-round costs for optimal regret guarantees or compromising statistical efficiency to enable constant-time updates. In this paper, we propose a jointly efficient algorithm that attains a nearly optimal regret bound with $\mathcal{O}(1)$ time and space complexities per round. The core of our method is a tight confidence set for the online mirror descent (OMD) estimator, which is derived through a novel analysis that leverages the notion of mix loss from online prediction. The analysis shows that our OMD estimator, even with its one-pass updates, achieves statistical efficiency comparable to maximum likelihood estimation, thereby leading to a jointly efficient optimistic method.
• Abstract（参考訳）: 非線型リンク関数を組み込んで古典線形モデルを拡張し,ベルヌーイやポアソンなどの報奨分布の幅広いクラスをモデル化する,文脈的多武装バンディットフレームワークである一般化線形バンディット問題(GLB)について検討する。 GLBは現実世界のシナリオに広く適用できるが、その非線形性は計算効率と統計効率の両方を達成する上で大きな課題をもたらす。 既存の方法は典型的には、2つの目的の間を行き来し、最適の後悔の保証のために1ラウンドあたりのコストが高くなるか、一定の時間更新を可能にする統計的効率を損なう。 本稿では,$\mathcal{O}(1)$ time and space complexities 1ラウンドあたりの誤差をほぼ最適に補正するアルゴリズムを提案する。 本手法のコアはオンラインミラー降下(OMD)推定器の厳密な信頼度セットであり,オンライン予測から混合損失の概念を生かした新しい分析から導かれる。 解析の結果,OMD推定器は1回更新しても最大推定値に匹敵する統計的効率を達成し,共同で楽観的手法を実現することができた。

関連論文リスト

• Distributionally Robust Optimization with Adversarial Data Contamination [36.409282287280185]
  凸リプシッツ損失関数を持つ一般化線形モデルに対するワッサーシュタイン-1 DRO 目標の最適化に焦点をあてる。 私たちの主な貢献は、データ汚染のトレーニングに対するロバストネスと分散シフトに対するロバストネスを統合した、新しいモデリングフレームワークです。 この研究は、データ汚染と分散シフトという2つの課題の下で学習するために、効率的な計算によって支援される最初の厳密な保証を確立する。
  論文  参考訳（メタデータ） (2025-07-14T18:34:10Z)
• Self-Boost via Optimal Retraining: An Analysis via Approximate Message Passing [58.52119063742121]
  独自の予測と潜在的にノイズの多いラベルを使ってモデルをトレーニングすることは、モデルパフォーマンスを改善するためのよく知られた戦略である。 本稿では,モデルの予測と提供ラベルを最適に組み合わせる方法について論じる。 我々の主な貢献は、現在のモデルの予測と与えられたラベルを組み合わせたベイズ最適集約関数の導出である。
  論文  参考訳（メタデータ） (2025-05-21T07:16:44Z)
• Provably Efficient Online RLHF with One-Pass Reward Modeling [59.30310692855397]
  本稿では,過去のデータを保存する必要がなく,一定時間で計算できるワンパス報酬モデリング手法を提案する。 提案手法は,統計的および計算効率の両面で向上することを示す理論的保証を提供する。 我々はUltrafeedback-binarizedおよびMixture2データセット上でLlama-3-8B-InstructとQwen2.5-7B-Instructモデルを用いて実験を行った。
  論文  参考訳（メタデータ） (2025-02-11T02:36:01Z)
• Achieving $\widetilde{\mathcal{O}}(\sqrt{T})$ Regret in Average-Reward POMDPs with Known Observation Models [56.92178753201331]
  平均逆無限水平POMDPを未知の遷移モデルで扱う。 この障壁を克服する斬新でシンプルな推定器を提示する。
  論文  参考訳（メタデータ） (2025-01-30T22:29:41Z)
• Adaptive debiased SGD in high-dimensional GLMs with streaming data [4.704144189806667]
  本稿では,高次元一般化線形モデルにおけるオンライン推論に対する新しいアプローチを提案する。 提案手法は単一パスモードで動作し,全データセットアクセスや大次元要約統計ストレージを必要とする既存手法とは異なる。 我々の方法論的革新の核心は、動的目的関数に適した適応的降下アルゴリズムと、新しいオンラインデバイアス処理である。
  論文  参考訳（メタデータ） (2024-05-28T15:36:48Z)
• Federated Coordinate Descent for Privacy-Preserving Multiparty Linear Regression [0.5049057348282932]
  我々は、FCDと呼ばれる新しい分散スキームであるFederated Coordinate Descentを紹介し、マルチパーティシナリオ下でこの問題に安全に対処する。 具体的には、セキュアな集約と追加の摂動により、(1)ローカル情報が他の当事者にリークされることがなく、(2)グローバルモデルパラメータがクラウドサーバに公開されることが保証される。 また,FCD方式は, 線形, リッジ, ラッソ回帰などの一般線形回帰に適用可能であることを示す。
  論文  参考訳（メタデータ） (2022-09-16T03:53:46Z)
• Distributed Dynamic Safe Screening Algorithms for Sparse Regularization [73.85961005970222]
  本稿では,分散動的安全スクリーニング(DDSS)手法を提案し,共有メモリアーキテクチャと分散メモリアーキテクチャにそれぞれ適用する。 提案手法は, 線形収束率を低次複雑度で達成し, 有限個の繰り返しにおいてほとんどすべての不活性な特徴をほぼ確実に除去できることを示す。
  論文  参考訳（メタデータ） (2022-04-23T02:45:55Z)
• Scalable Personalised Item Ranking through Parametric Density Estimation [53.44830012414444]
  暗黙のフィードバックから学ぶことは、一流問題の難しい性質のために困難です。 ほとんどの従来の方法は、一級問題に対処するためにペアワイズランキングアプローチとネガティブサンプラーを使用します。 本論文では,ポイントワイズと同等の収束速度を実現する学習対ランクアプローチを提案する。
  論文  参考訳（メタデータ） (2021-05-11T03:38:16Z)
• Online and Distribution-Free Robustness: Regression and Contextual Bandits with Huber Contamination [29.85468294601847]
  線形回帰と文脈的帯域幅という2つの古典的高次元オンライン学習問題を再考する。 従来の手法が失敗した場合にアルゴリズムが成功することを示す。
  論文  参考訳（メタデータ） (2020-10-08T17:59:05Z)

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

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