論文の概要: Simple Projection-Free Algorithm for Contextual Recommendation with Logarithmic Regret and Robustness

• arxiv url: http://arxiv.org/abs/2603.20826v1
• Date: Sat, 21 Mar 2026 13:57:29 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-03-24 19:11:39.105072
• Title: Simple Projection-Free Algorithm for Contextual Recommendation with Logarithmic Regret and Robustness
• Title（参考訳）: 対数レグレットとロバスト性を考慮した文脈推薦のための簡易射影自由アルゴリズム
• Authors: Shinsaku Sakaue,
• Abstract要約: そこで本研究では,ONS法よりも効率の良い簡単なアルゴリズムを提案する。 私たちの中核となる考え方は、コンテキストレコメンデーションに固有の不適切さを活用することであり、オンラインの分類から2階のパーセプトロンに類似した更新ルールにつながります。
• 参考スコア（独自算出の注目度）: 18.046669772867443
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Contextual recommendation is a variant of contextual linear bandits in which the learner observes an (optimal) action rather than a reward scalar. Recently, Sakaue et al. (2025) developed an efficient Online Newton Step (ONS) approach with an $O(d\log T)$ regret bound, where $d$ is the dimension of the action space and $T$ is the time horizon. In this paper, we present a simple algorithm that is more efficient than the ONS-based method while achieving the same regret guarantee. Our core idea is to exploit the improperness inherent in contextual recommendation, leading to an update rule akin to the second-order perceptron from online classification. This removes the Mahalanobis projection step required by ONS, which is often a major computational bottleneck. More importantly, the same algorithm remains robust to possibly suboptimal action feedback, whereas the prior ONS-based method required running multiple ONS learners with different learning rates for this extension. We describe how our method works in general Hilbert spaces (e.g., via kernelization), where eliminating Mahalanobis projections becomes even more beneficial.
• Abstract（参考訳）: コンテキストレコメンデーション(Contextual recommendation)は、学習者が報酬スカラーではなく(最適)アクションを観察するコンテキスト線形バンドイットの変種である。 最近、Sakaue et al (2025) は$O(d\log T)$ regret bound を用いて効率的な Online Newton Step (ONS) アプローチを開発し、$d$ はアクション空間の次元、$T$ は時間地平線である。 本稿では,ONS法よりも効率の良い簡単なアルゴリズムを提案する。 私たちの中核となる考え方は、コンテキストレコメンデーションに固有の不適切さを活用することであり、オンラインの分類から2階のパーセプトロンに類似した更新ルールにつながります。 これにより、ONSが要求するマハラノビス射影ステップが取り除かれる。 さらに重要なことは、同じアルゴリズムが、おそらくは準最適動作フィードバックに対して堅牢であるのに対して、以前のONSベースの手法では、この拡張のために異なる学習率で複数のONS学習者を走らせる必要があったことである。 我々は、我々の方法がヒルベルト空間(例えば、カーネル化)でどのように機能するかを説明し、そこではマハラノビス射影の除去がさらに有益になる。

関連論文リスト

• A Simple, Optimal and Efficient Algorithm for Online Exp-Concave Optimization [72.1530234801628]
  オンラインニュートンステップ(ONS)はオンライン学習における基本的な問題である。 ONSは、各ラウンドにおけるマハラノビス予想のために計算ボトルネックに直面している。 本稿では,O(normd2 T + dsqrtTlog)を最適に保ちつつ,全ランタイムを$O(normd2 T + dsqrtTlog)に減らしたONS,LightONSを提案する。 この設計により、より広いシナリオにおいて、LightONSはONSの効率的なプラグイン代替として機能する。
  論文  参考訳（メタデータ） (2025-12-29T03:59:51Z)
• Stacey: Promoting Stochastic Steepest Descent via Accelerated $\ell_p$-Smooth Nonconvex Optimization [15.179519413549086]
  我々は、非ユークリッドスムーズな最適化タスクを処理するために、Staceyと呼ばれる新しい高速化された$ell_p$急降下アルゴリズムを導入する。 アルゴリズムの基礎に関する理論的保証を提供するのに加えて、我々のアプローチと一般的な手法を実証的に比較する。
  論文  参考訳（メタデータ） (2025-06-07T00:47:07Z)
• Bayesian Algorithms for Adversarial Online Learning: from Finite to Infinite Action Spaces [51.513172647831745]
  オンライン学習のためのフォーム・トンプソン・サンプリングをフルフィードバックで開発する。 我々は、後悔の分解を、学習者が先入観を期待したことを後悔させ、また、過度な後悔と呼ぶ先延ばし的な用語を示します。
  論文  参考訳（メタデータ） (2025-02-20T18:10:12Z)
• Optimistically Optimistic Exploration for Provably Efficient Infinite-Horizon Reinforcement and Imitation Learning [13.429541377715296]
  無限水平割引線形マルコフ決定過程において, 速度-最適後悔保証を実現するための計算効率のよいアルゴリズムを提案する。 正規化された近似的動的プログラミングスキームと組み合わせると、結果のアルゴリズムは、$tildemathcalO (sqrtd3 (1 - gamma)- 7 / 2 T)$, $T$ はサンプル遷移の総数、$gamma in (0,1)$ は割引係数、$d$ は特徴次元を後悔する。
  論文  参考訳（メタデータ） (2025-02-19T17:32:35Z)
• Improved Regret for Efficient Online Reinforcement Learning with Linear Function Approximation [69.0695698566235]
  線形関数近似による強化学習と,コスト関数の逆変化について検討した。 本稿では,未知のダイナミクスと帯域幅フィードバックの一般設定に挑戦する,計算効率のよいポリシ最適化アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-01-30T17:26:39Z)
• Trading Off Resource Budgets for Improved Regret Bounds [6.85316573653194]
  対戦型オンライン学習問題に対するFPML(Follow the Perturbed Multiple Leaders)と呼ばれるアルゴリズムを提案する。 また, FPML は, 所要時間で $mathcalO(Tfrac1B+1ln(N)fracBB+1)$ となることを示す。 我々はFPMLがより強力なオラクルを必要とする線形プログラミングの新しいアルゴリズムにどのように導くかを示す。
  論文  参考訳（メタデータ） (2022-10-11T21:13:48Z)
• Online Prediction in Sub-linear Space [15.773280101995676]
  我々は、専門家のアドバイスによるオンライン学習のための最初のサブ線形空間とサブ線形後悔アルゴリズムを提供する。 また,任意の線形後悔アルゴリズムの線形メモリ下限を適応的逆数に対して証明することにより,(強い)適応的逆数と難解な逆数との分離を実証する。
  論文  参考訳（メタデータ） (2022-07-16T16:15:39Z)
• First-Order Regret in Reinforcement Learning with Linear Function Approximation: A Robust Estimation Approach [57.570201404222935]
  我々は,大規模状態空間を用いた強化学習において,$mathcalO(sqrtV_1star K)$として,後悔のスケーリングが得られることを示す。 この結果を得るためには,少なくとも2乗推定に基づく既存手法は不十分であることを示す。
  論文  参考訳（メタデータ） (2021-12-07T00:29:57Z)
• Efficient and Optimal Algorithms for Contextual Dueling Bandits under Realizability [59.81339109121384]
  我々は,学習者が文脈情報を用いて2つの決定を下す連続的な決定設定であるK$コンテキストデュエルバンディット問題について検討するが,一方の判断が他方よりも優れていることを示唆する強調基準に基づくフィードバックのみを観察する。 提案手法は, 最善応答後悔という新たな概念に対して, 最善応答後悔に対する最適後悔率を実現するアルゴリズムである。
  論文  参考訳（メタデータ） (2021-11-24T07:14:57Z)
• Online Markov Decision Processes with Aggregate Bandit Feedback [74.85532145498742]
  本稿では,オンライン有限水平マルコフ決定過程の新たな変種について検討する。 各エピソードにおいて、学習者は、エピソードの選択した方針によって実現された軌道に沿って蓄積された損失を被り、総括的盗聴フィードバックを観察する。 我々の主な結果は計算効率のよいアルゴリズムで、$O(sqrtK)$ regret for this set, where $K$ is the number of episodes。
  論文  参考訳（メタデータ） (2021-01-31T16:49:07Z)

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

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