論文の概要: Matrix Sketching in Bandits: Current Pitfalls and New Framework

• arxiv url: http://arxiv.org/abs/2410.10258v1
• Date: Mon, 14 Oct 2024 08:13:28 GMT
• ステータス: 処理完了
• システム内更新日: 2024-10-30 02:05:09.599595
• Title: Matrix Sketching in Bandits: Current Pitfalls and New Framework
• Title（参考訳）: バンドのマトリックススケッチ:現在の落とし穴と新しいフレームワーク
• Authors: Dongxie Wen, Hanyan Yin, Xiao Zhang, Zhewei Wei,
• Abstract要約: 線形バンディット設定では、スケッチベースのアプローチがマトリックススケッチを活用して、時間単位の複雑さを低減する。 共分散行列のスペクトル尾が急速に減少しない場合、線形後悔につながる。 Dyadic Block Sketchingを提案する。Dyadic Block Sketchingは,大域的なスペクトル損失を抑えるために,スケッチサイズを適応的に管理する,革新的なストリーミング行列スケッチ手法である。
• 参考スコア（独自算出の注目度）: 20.496072342424895
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: The utilization of sketching techniques has progressively emerged as a pivotal method for enhancing the efficiency of online learning. In linear bandit settings, current sketch-based approaches leverage matrix sketching to reduce the per-round time complexity from \(\Omega\left(d^2\right)\) to \(O(d)\), where \(d\) is the input dimension. Despite this improved efficiency, these approaches encounter critical pitfalls: if the spectral tail of the covariance matrix does not decrease rapidly, it can lead to linear regret. In this paper, we revisit the regret analysis and algorithm design concerning approximating the covariance matrix using matrix sketching in linear bandits. We illustrate how inappropriate sketch sizes can result in unbounded spectral loss, thereby causing linear regret. To prevent this issue, we propose Dyadic Block Sketching, an innovative streaming matrix sketching approach that adaptively manages sketch size to constrain global spectral loss. This approach effectively tracks the best rank-\( k \) approximation in an online manner, ensuring efficiency when the geometry of the covariance matrix is favorable. Then, we apply the proposed Dyadic Block Sketching to linear bandits and demonstrate that the resulting bandit algorithm can achieve sublinear regret without prior knowledge of the covariance matrix, even under the worst case. Our method is a general framework for efficient sketch-based linear bandits, applicable to all existing sketch-based approaches, and offers improved regret bounds accordingly. Additionally, we conduct comprehensive empirical studies using both synthetic and real-world data to validate the accuracy of our theoretical findings and to highlight the effectiveness of our algorithm.
• Abstract（参考訳）: スケッチ技術の利用は、オンライン学習の効率を高めるための重要な方法として徐々に現れてきた。 線形バンディット設定では、現在のスケッチベースのアプローチは行列スケッチを利用して、円周時間の複雑さを \(\Omega\left(d^2\right)\) から \(O(d)\) に還元する。 この効率の改善にもかかわらず、これらのアプローチは臨界落とし穴に遭遇し、共分散行列のスペクトル尾部が急速に減少しない場合、線形後悔につながる可能性がある。 本稿では,線形帯域における行列スケッチを用いた共分散行列の近似に関する後悔解析とアルゴリズム設計について再検討する。 本研究では,不適切なスケッチサイズがスペクトル損失の非有界化を招き,線形後悔を引き起こすことを示す。 この問題を回避するために,グローバルスペクトル損失を抑えるためにスケッチサイズを適応的に管理する,革新的なストリーミング行列スケッチ手法であるDyadic Block Sketchingを提案する。 このアプローチは、オンラインで最高のランク-\(k \)近似を効果的に追跡し、共分散行列の幾何学が好まれるときに効率を確実にする。 そこで,提案したDyadic Block Sketchingを線形バンディットに適用し,最悪の場合であっても,共分散行列の事前知識を必要とせずに,結果として得られるバンディットアルゴリズムがサブ線形後悔を実現することを示す。 提案手法は,既存のスケッチベースアプローチのすべてに適用可能な,効率的なスケッチベース線形包帯の一般的なフレームワークであり,それに応じて改善された後悔境界を提供する。 さらに,我々の理論的な結果の精度を検証し,アルゴリズムの有効性を明らかにするために,合成データと実世界のデータの両方を用いて総合的な実証研究を行う。

関連論文リスト

• A Mirror Descent-Based Algorithm for Corruption-Tolerant Distributed Gradient Descent [57.64826450787237]
  本研究では, 分散勾配降下アルゴリズムの挙動を, 敵対的腐敗の有無で解析する方法を示す。 汚職耐性の分散最適化アルゴリズムを設計するために、(怠慢な)ミラー降下からアイデアをどう使うかを示す。 MNISTデータセットの線形回帰、サポートベクトル分類、ソフトマックス分類に基づく実験は、我々の理論的知見を裏付けるものである。
  論文  参考訳（メタデータ） (2024-07-19T08:29:12Z)
• Learning the Positions in CountSketch [49.57951567374372]
  本稿では,まずランダムなスケッチ行列に乗じてデータを圧縮し,最適化問題を高速に解くスケッチアルゴリズムについて検討する。 本研究では,ゼロでないエントリの位置を最適化する学習ベースアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-06-11T07:28:35Z)
• PopArt: Efficient Sparse Regression and Experimental Design for Optimal Sparse Linear Bandits [29.097522376094624]
  そこで我々はPopArtと呼ばれる単純で効率的なスパース線形推定法を提案する。 我々は, 粗い線形バンディットアルゴリズムを導出し, 美術品の状態に対する後悔の上界の改善を享受する。
  論文  参考訳（メタデータ） (2022-10-25T19:13:20Z)
• A Validation Approach to Over-parameterized Matrix and Image Recovery [29.29430943998287]
  複数のランダムな線形測定から低ランク行列を復元する問題を考察する。 提案手法は,より深いネットワークを持つ画像である画像に有効であることを示す。
  論文  参考訳（メタデータ） (2022-09-21T22:01:23Z)
• Sharp Analysis of Sketch-and-Project Methods via a Connection to Randomized Singular Value Decomposition [14.453949553412821]
  本研究では,スケッチ・アンド・プロジェクト手法の収束率の急激な保証を得るための理論的枠組みを開発する。 収束速度はスケッチサイズとともに少なくとも直線的に改善され、データ行列が特定のスペクトル崩壊を示すとさらに高速になることを示す。 我々の実験は、この理論を支持し、非常にスパースなスケッチでさえ、我々のフレームワークによって予測される収束特性を示すことを示した。
  論文  参考訳（メタデータ） (2022-08-20T03:11:13Z)
• Stochastic Online Linear Regression: the Forward Algorithm to Replace Ridge [24.880035784304834]
  オンラインリッジ回帰とフォワードアルゴリズムに対して高い確率的後悔境界を導出する。 これにより、オンライン回帰アルゴリズムをより正確に比較し、有界な観測と予測の仮定を排除できる。
  論文  参考訳（メタデータ） (2021-11-02T13:57:53Z)
• Unfolding Projection-free SDP Relaxation of Binary Graph Classifier via GDPA Linearization [59.87663954467815]
  アルゴリズムの展開は、モデルベースのアルゴリズムの各イテレーションをニューラルネットワーク層として実装することにより、解釈可能で類似のニューラルネットワークアーキテクチャを生成する。 本稿では、Gershgorin disc perfect alignment (GDPA)と呼ばれる最近の線形代数定理を利用して、二進グラフの半定値プログラミング緩和(SDR)のためのプロジェクションフリーアルゴリズムをアンロールする。 実験結果から,我々の未学習ネットワークは純粋モデルベースグラフ分類器よりも優れ,純粋データ駆動ネットワークに匹敵する性能を示したが,パラメータははるかに少なかった。
  論文  参考訳（メタデータ） (2021-09-10T07:01:15Z)
• Fast Convex Quadratic Optimization Solvers with Adaptive Sketching-based Preconditioners [37.03247707259297]
  二次正則化を伴う最小二乗問題を検討し,適応的なスケッチサイズを持つ新しいスケッチベース反復手法を提案する。 スケッチのサイズは、線形収束を保証するためにデータ行列の有効次元と同じくらい小さくすることができる。 効果的な寸法の観点からスケッチサイズを選択する際の大きな困難は、後者が実際には通常不明であるという事実にあります。
  論文  参考訳（メタデータ） (2021-04-29T04:36:41Z)
• Learning-Augmented Sketches for Hessians [54.97773807211337]
  第二次手法の文脈でヘッセンの学習スケッチを設計する方法を紹介します。 学習したスケッチは,「学習されていない」スケッチと比較して,重要な問題に対する近似精度が向上することを示す。
  論文  参考訳（メタデータ） (2021-02-24T14:50:59Z)
• Learning the Positions in CountSketch [51.15935547615698]
  本稿では,まずランダムなスケッチ行列に乗じてデータを圧縮し,最適化問題を高速に解くスケッチアルゴリズムについて検討する。 本研究では,ゼロでないエントリの位置を最適化する学習アルゴリズムを提案する。 このアルゴリズムは, 従来よりも低階近似の精度を向上し, 初めて$k$-meansクラスタリングのような他の問題に適用できることを示す。
  論文  参考訳（メタデータ） (2020-07-20T05:06:29Z)
• Effective Dimension Adaptive Sketching Methods for Faster Regularized Least-Squares Optimization [56.05635751529922]
  スケッチに基づくL2正規化最小二乗問題の解法を提案する。 我々は、最も人気のあるランダム埋め込みの2つ、すなわちガウス埋め込みとサブサンプリングランダム化アダマール変換(SRHT)を考える。
  論文  参考訳（メタデータ） (2020-06-10T15:00:09Z)

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

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