論文の概要: Efficient Linear Bandits via Cluster-Aware Sketching

• arxiv url: http://arxiv.org/abs/2609.27594v1
• Date: Wed, 23 Sep 2026 09:10:29 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-09-25 00:05:17.965572
• Title: Efficient Linear Bandits via Cluster-Aware Sketching
• Title（参考訳）: クラスタ・アウェア・スケッチによる効率的な線形帯域分割
• Abstract要約: 有限なアームセットを持つ高次元設定における線形包帯の計算効率の問題について検討する。 線形帯域では、特徴ベクトルの次元$d$の増加は、更新毎にO(d2)$の計算コストを増大させる。 SOFULのような伝統的なスケッチベースの手法は、固定サイズの行列スケッチによる計算を減らすが、空虚な線形後悔を引き起こすリスクを負う。
• 参考スコア（独自算出の注目度）: 49.7868381442861
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the problem of computational efficiency for linear bandits in high-dimensional settings with a finite arm set. In linear bandits, the increase in the dimension $d$ of the feature vectors leads to growing computational costs of $O(d^2)$ at each round of update. Traditional sketching-based methods such as SOFUL reduce computation via fixed-size matrix sketching, yet run the risk of incurring vacuous linear regret when the spectral tail of the data is heavy and the sketch size is inadequately selected. To guarantee regret convergence and effectively reduce computational costs, we introduce a clustering mechanism and propose the Cluster Sketch Linear Bandit (CS-LB) algorithm. Our method preserves the full covariance information in each cluster to guarantee robust sublinear regret without spectral-tail vulnerabilities, performs cluster switching by assigning a sentinel for each cluster, and reduces per-round update computation to $O(l^2d)$ via a tunable sketch size $l<d$. Experiments on synthetic datasets demonstrate that our method consistently maintains a favorable trade-off between efficiency and regret.
• Abstract（参考訳）: 有限なアームセットを持つ高次元設定における線形包帯の計算効率の問題について検討する。 線形帯域では、特徴ベクトルの次元$d$の増加は、更新毎にO(d^2)$の計算コストを増大させる。 SOFULのような従来のスケッチベースの手法は、固定サイズの行列スケッチによる計算を減らすが、データのスペクトルテールが重く、スケッチサイズが不十分な場合に、空の線形後悔を引き起こすリスクを負う。 後悔の収束を保証し,計算コストを効果的に削減するために,クラスタリング機構を導入し,CS-LBアルゴリズムを提案する。 本手法は,スペクトルテールの脆弱性を伴わずに,堅牢なサブ線形後悔を保証するために,各クラスタ内の完全な共分散情報を保存し,各クラスタにセンチネルを割り当ててクラスタ切替を行い,調整可能なスケッチサイズ$l<d$により,ラウンドごとの更新計算を$O(l^2d)$に削減する。 合成データセットの実験は、我々の手法が効率と後悔の間の良好なトレードオフを一貫して維持していることを示している。

関連論文リスト

• Generalized Linear Bandits: Almost Optimal Regret with One-Pass Update [70.38810219913593]
  非線形リンク関数を組み込んで古典線形モデルを拡張したコンテキスト型多武装バンディットフレームワークである一般化線形バンディット問題(GLB)について検討する。 GLBは現実世界のシナリオに広く適用できるが、その非線形性は計算効率と統計効率の両方を達成する上で大きな課題をもたらす。 本稿では,$mathcalO(1)$時間と1ラウンドあたりの空間複雑度をほぼ最適に再現するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2025-07-16T02:24:21Z)
• Sparse Linear Bandits with Blocking Constraints [22.01704171400845]
  データ・ポーア・システマにおける高次元スパース線形包帯問題について検討する。 線形モデルに対するラッソ推定器の新たなオフライン統計的保証を示す。 本稿では,最小限のコストで最適空間パラメータ$k$の知識を必要としない相関に基づくメタアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-10-26T01:42:03Z)
• Matrix Sketching in Bandits: Current Pitfalls and New Framework [20.496072342424895]
  線形バンディット設定では、スケッチベースのアプローチがマトリックススケッチを活用して、時間単位の複雑さを低減する。 共分散行列のスペクトル尾が急速に減少しない場合、線形後悔につながる。 Dyadic Block Sketchingを提案する。Dyadic Block Sketchingは,大域的なスペクトル損失を抑えるために,スケッチサイズを適応的に管理する,革新的なストリーミング行列スケッチ手法である。
  論文  参考訳（メタデータ） (2024-10-14T08:13:28Z)
• Sketchy: Memory-efficient Adaptive Regularization with Frequent Directions [22.09320263962004]
  ディープラーニング(DL)学習タスクにおけるKronecker-factored gradient covariance matrixのスペクトルは、小さなリード固有空間に集中している。 本稿では,行列プレコンディショナを維持するためのメモリと計算要求を低減させる汎用的手法について述べる。 ShampooやAdamと競合する手法で、第2の瞬間を追跡するにはサブ線形メモリしか必要ありません。
  論文  参考訳（メタデータ） (2023-02-07T21:50:06Z)
• Efficient Dataset Distillation Using Random Feature Approximation [109.07737733329019]
  本稿では,ニューラルネットワークガウス過程(NNGP)カーネルのランダム特徴近似(RFA)を用いた新しいアルゴリズムを提案する。 我々のアルゴリズムは、KIP上で少なくとも100倍のスピードアップを提供し、1つのGPUで実行できる。 RFA蒸留 (RFAD) と呼ばれる本手法は, 大規模データセットの精度において, KIP や他のデータセット凝縮アルゴリズムと競合して動作する。
  論文  参考訳（メタデータ） (2022-10-21T15:56:13Z)
• Sketch-and-Lift: Scalable Subsampled Semidefinite Program for $K$-means Clustering [16.153709556346417]
  セミデフィニティプログラミング(SDP)はクラスタリングなどの幅広い計算困難問題に対処するための強力なツールである。 本稿では,SDP緩和した$K$-meansクラスタリングを近似する線形時間複雑性アルゴリズムを提案する。 シミュレーション実験により,提案手法の統計的精度は最先端の高速クラスタリングアルゴリズムより優れていることが示された。
  論文  参考訳（メタデータ） (2022-01-20T15:31:28Z)
• Covariance-Free Sparse Bayesian Learning [62.24008859844098]
  共分散行列の明示的な反転を回避する新しいSBL推論アルゴリズムを導入する。 私たちの手法は、既存のベースラインよりも数千倍も高速です。 我々は,SBLが高次元信号回復問題に難なく対処できる新しいアルゴリズムについて紹介する。
  論文  参考訳（メタデータ） (2021-05-21T16:20:07Z)
• Stochastic Bundle Adjustment for Efficient and Scalable 3D Reconstruction [43.736296034673124]
  カメラ数に比例したReduced Camera System(RCS)を解く際のボトルネックによって、Levenberg-Marquardt (LM)アルゴリズムのような現在のバンドル調整ソルバが制限される。 本稿では,CS を LM のほぼ内部で分解し,効率と拡張性を向上するバンドル調整アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-08-02T10:26:09Z)
• Effective Dimension Adaptive Sketching Methods for Faster Regularized Least-Squares Optimization [56.05635751529922]
  スケッチに基づくL2正規化最小二乗問題の解法を提案する。 我々は、最も人気のあるランダム埋め込みの2つ、すなわちガウス埋め込みとサブサンプリングランダム化アダマール変換(SRHT)を考える。
  論文  参考訳（メタデータ） (2020-06-10T15:00:09Z)

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

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