論文の概要: Scalable LinUCB: Low-Rank Design Matrix Updates for Recommenders with Large Action Spaces

• arxiv url: http://arxiv.org/abs/2510.19349v1
• Date: Wed, 22 Oct 2025 08:17:42 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-10-25 03:08:15.344857
• Title: Scalable LinUCB: Low-Rank Design Matrix Updates for Recommenders with Large Action Spaces
• Title（参考訳）: スケーラブルLinUCB: 大規模なアクションスペースを持つレコメンダのための低ランク設計マトリックス更新
• Authors: Evgenia Shustova, Marina Sheshukova, Sergey Samsonov, Evgeny Frolov,
• Abstract要約: 特にLinUCBはリコメンデータシステムで広く使われている。 本稿では,逆正規化設計行列を用いた高速かつメモリ効率の高い演算を実現するアルゴリズムであるScalable LinUCBを紹介する。 提案アルゴリズムの有効性を,レコメンデータシステムデータセットで実証した。
• 参考スコア（独自算出の注目度）: 6.9187437863525645
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Linear contextual bandits, especially LinUCB, are widely used in recommender systems. However, its training, inference, and memory costs grow with feature dimensionality and the size of the action space. The key bottleneck becomes the need to update, invert and store a design matrix that absorbs contextual information from interaction history. In this paper, we introduce Scalable LinUCB, the algorithm that enables fast and memory efficient operations with the inverse regularized design matrix. We achieve this through a dynamical low-rank parametrization of its inverse Cholesky-style factors. We derive numerically stable rank-1 and batched updates that maintain the inverse without directly forming the entire matrix. To control memory growth, we employ a projector-splitting integrator for dynamical low-rank approximation, yielding average per-step update cost $O(dr)$ and memory $O(dr)$ for approximation rank $r$. Inference complexity of the suggested algorithm is $O(dr)$ per action evaluation. Experiments on recommender system datasets demonstrate the effectiveness of our algorithm.
• Abstract（参考訳）: 特にLinUCBはリコメンデータシステムで広く使われている。 しかし、そのトレーニング、推論、メモリコストは、特徴次元とアクション空間のサイズによって増大する。 重要なボトルネックは、インタラクション履歴からコンテキスト情報を吸収する設計マトリックスを更新、反転、保存する必要性である。 本稿では,逆正規化設計行列を用いた高速かつメモリ効率の高い演算を実現するアルゴリズムであるScalable LinUCBを紹介する。 これを、その逆コレスキー型因子の動的低ランクパラメトリゼーションにより達成する。 数値的に安定なランク1とバッチ更新を導出し、行列全体を直接形成することなく逆を維持できる。 メモリ成長を制御するために,プロジェクタ分割積分器を用いて動的低ランク近似を行い,各ステップごとの平均更新コスト$O(dr)$とメモリ$O(dr)$を近似ランク$r$とする。 提案アルゴリズムの推論複雑性はアクション評価あたり$O(dr)$である。 提案アルゴリズムの有効性を,レコメンデータシステムデータセットで実証した。

関連論文リスト

• Fast and Accurate SVD-Type Updating in Streaming Data [0.0]
  提案するアルゴリズムは, 候補の因数分解を更新するアルゴリズムである。 特に,低ランク更新からスパース部分を切り離す小型リテーナ型アルゴリズムを開発した。 ゲインズ回転に基づく第2のアルゴリズムは、1回転あたり約10フロップしか持たず、問題の大きさと2次的にスケールする。
  論文  参考訳（メタデータ） (2025-09-02T21:17:37Z)
• FFT-based Dynamic Subspace Selection for Low-Rank Adaptive Optimization of Large Language Models [49.397861654088636]
  低次元空間へのSVD/QRベースの勾配射影を近似する2段階の手順を提案する。 当社の戦略はランタイムの高速化とメモリ使用量の削減を,さまざまなモデルサイズで最大25%削減できることが示されています。
  論文  参考訳（メタデータ） (2025-05-23T14:37:00Z)
• An Efficient Algorithm for Clustered Multi-Task Compressive Sensing [60.70532293880842]
  クラスタ化マルチタスク圧縮センシングは、複数の圧縮センシングタスクを解決する階層モデルである。 このモデルに対する既存の推論アルゴリズムは計算コストが高く、高次元ではうまくスケールしない。 本稿では,これらの共分散行列を明示的に計算する必要をなくし,モデル推論を大幅に高速化するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-09-30T15:57:14Z)
• Nearly Minimax Optimal Reinforcement Learning for Linear Markov Decision Processes [80.89852729380425]
  そこで本研究では,最小限の最小残差である$tilde O(dsqrtH3K)$を計算効率よく実現したアルゴリズムを提案する。 我々の研究は線形 MDP を用いた最適 RL に対する完全な答えを提供する。
  論文  参考訳（メタデータ） (2022-12-12T18:58:59Z)
• Fast and Accurate Pseudoinverse with Sparse Matrix Reordering and Incremental Approach [4.710916891482697]
  擬逆は行列逆の一般化であり、機械学習で広く利用されている。 FastPIはスパース行列に対する新たなインクリメンタル特異値分解法(SVD)である。 我々は,FastPIが精度を損なうことなく,他の近似手法よりも高速に擬似逆計算を行うことを示す。
  論文  参考訳（メタデータ） (2020-11-09T07:47:10Z)

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

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