論文の概要: Analysis of Nystrom method with sequential ridge leverage scores

• arxiv url: http://arxiv.org/abs/2604.20077v1
• Date: Wed, 22 Apr 2026 00:49:25 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-04-23 15:36:10.893042
• Title: Analysis of Nystrom method with sequential ridge leverage scores
• Title（参考訳）: 逐次リッジレバレッジスコアを用いたNystrom法の解析
• Authors: Daniele Calandriello, Alessandro Lazaric, Michal Valko,
• Abstract要約: 大規模なカーネルリッジ回帰(KRR)は、大規模なカーネルマトリックスK_tを格納する必要があるため制限される。 近年の研究では、尾根レバレッジスコア(RLS)に比例するサンプリング分布が、近似に強い再構成保証をもたらすことが示されている。 本稿では,LS推定値を漸進的に計算するINK-ESTIMATEアルゴリズムを提案する。
• 参考スコア（独自算出の注目度）: 69.32538992633842
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Large-scale kernel ridge regression (KRR) is limited by the need to store a large kernel matrix K_t. To avoid storing the entire matrix K_t, Nystrom methods subsample a subset of columns of the kernel matrix, and efficiently find an approximate KRR solution on the reconstructed matrix. The chosen subsampling distribution in turn affects the statistical and computational tradeoffs. For KRR problems, recent works show that a sampling distribution proportional to the ridge leverage scores (RLSs) provides strong reconstruction guarantees for the approximation. While exact RLSs are as difficult to compute as a KRR solution, we may be able to approximate them well enough. In this paper, we study KRR problems in a sequential setting and introduce the INK-ESTIMATE algorithm, that incrementally computes the RLSs estimates. INK-ESTIMATE maintains a small sketch of K_t, that at each step is used to compute an intermediate estimate of the RLSs. First, our sketch update does not require access to previously seen columns, and therefore a single pass over the kernel matrix is sufficient. Second, the algorithm requires a fixed, small space budget to run dependent only on the effective dimension of the kernel matrix. Finally, our sketch provides strong approximation guarantees on the distance between the true kernel matrix and its approximation, and on the statistical risk of the approximate KRR solution at any time, because all our guarantees hold at any intermediate step.
• Abstract（参考訳）: 大規模なカーネルリッジ回帰(KRR)は、大規模なカーネルマトリックスK_tを格納する必要があるため制限される。 行列K_t全体を格納するのを避けるため、Nystrom法はカーネル行列の列のサブセットをサブサンプリングし、再構成された行列上で近似KRR解を効率的に見つける。 選択されたサブサンプリング分布は、統計的および計算的トレードオフに影響を与える。 KRR問題に対して、最近の研究では、リッジレバレッジスコア(RLS)に比例するサンプリング分布が、近似に対する強い再構成保証を提供することを示した。 正確なRSSはKRR解と同じくらい計算が難しいが、十分に近似できるかもしれない。 本稿では,KRR問題を逐次的に検討し,LS推定を漸進的に計算するINK-ESTIMATEアルゴリズムを導入する。 INK-ESTIMATEはK_tの小さなスケッチを保持し、各ステップでLSの中間推定を計算する。 まず、スケッチ更新は以前見た列へのアクセスを必要としないので、カーネルマトリックスを渡すだけで十分です。 第二に、アルゴリズムは、カーネルマトリックスの有効次元にのみ依存するように、固定された小さなスペース予算を必要とする。 最後に、我々のスケッチは、真のカーネル行列と近似の間の距離、および近似KRR解の統計的リスクについて、全ての保証が任意の中間ステップで保たれるため、強い近似保証を提供する。

関連論文リスト

• A Sample Efficient Alternating Minimization-based Algorithm For Robust Phase Retrieval [56.67706781191521]
  そこで本研究では,未知の信号の復元を課題とする,ロバストな位相探索問題を提案する。 提案するオラクルは、単純な勾配ステップと外れ値を用いて、計算学的スペクトル降下を回避している。
  論文  参考訳（メタデータ） (2024-09-07T06:37:23Z)
• Robust Kernel Sparse Subspace Clustering [0.0]
  本稿では,カーネルスパースSC (RKSSC) アルゴリズムを初めて提案する。 この概念は、原則として他のSCアルゴリズムにも適用でき、この種の汚職の存在に対して堅牢性を達成することができる。
  論文  参考訳（メタデータ） (2024-01-30T14:12:39Z)
• Stochastic Optimization for Non-convex Problem with Inexact Hessian Matrix, Gradient, and Function [99.31457740916815]
  信頼領域(TR)と立方体を用いた適応正則化は、非常に魅力的な理論的性質を持つことが証明されている。 TR法とARC法はヘッセン関数,勾配関数,関数値の非コンパクトな計算を同時に行うことができることを示す。
  論文  参考訳（メタデータ） (2023-10-18T10:29:58Z)
• Robust, randomized preconditioning for kernel ridge regression [4.633920223660256]
  カーネルリッジ回帰問題に最も強い保証を持つ2つの方法を記述する。 提案手法は, KRR問題の範囲を効率的に解き, 実用化に適している。
  論文  参考訳（メタデータ） (2023-04-24T21:48:24Z)
• Efficient Dataset Distillation Using Random Feature Approximation [109.07737733329019]
  本稿では,ニューラルネットワークガウス過程(NNGP)カーネルのランダム特徴近似(RFA)を用いた新しいアルゴリズムを提案する。 我々のアルゴリズムは、KIP上で少なくとも100倍のスピードアップを提供し、1つのGPUで実行できる。 RFA蒸留 (RFAD) と呼ばれる本手法は, 大規模データセットの精度において, KIP や他のデータセット凝縮アルゴリズムと競合して動作する。
  論文  参考訳（メタデータ） (2022-10-21T15:56:13Z)
• Target alignment in truncated kernel ridge regression [12.139222986297264]
  ターゲット関数とカーネルのアライメントがカーネルリッジ回帰(KRR)の性能に与える影響について検討する。 我々は,TKRRが完全KRRで達成可能なものよりも高速に達成できるエンフェール整列系が存在することを示す。 また、バンドリミテッドアライメントの設定を考慮し、TKRRの正規化面が多重降下や非単調な挙動を含む過渡的な効果を示すことを示す。
  論文  参考訳（メタデータ） (2022-06-28T19:16:10Z)
• SreaMRAK a Streaming Multi-Resolution Adaptive Kernel Algorithm [60.61943386819384]
  既存のKRRの実装では、すべてのデータがメインメモリに格納される必要がある。 KRRのストリーミング版であるStreaMRAKを提案する。 本稿では,2つの合成問題と2重振り子の軌道予測について紹介する。
  論文  参考訳（メタデータ） (2021-08-23T21:03:09Z)
• Fast Statistical Leverage Score Approximation in Kernel Ridge Regression [12.258887270632869]
  Nystr"om approximationは、カーネルリッジ回帰(KRR)問題を迅速に解決する高速ランダム化方法です。 本稿では,静止Kernel-based KRRの統計的レバレッジスコアを正確に推定する線形時間アルゴリズム(モジュロポリログ項)を提案する。
  論文  参考訳（メタデータ） (2021-03-09T05:57:08Z)
• SimpleMKKM: Simple Multiple Kernel K-means [49.500663154085586]
  単純なマルチカーネルk-means(SimpleMKKM)と呼ばれる,単純で効果的なマルチカーネルクラスタリングアルゴリズムを提案する。 我々の基準は、カーネル係数とクラスタリング分割行列における難解な最小化最大化問題によって与えられる。 クラスタリング一般化誤差の観点から,SimpleMKKMの性能を理論的に解析する。
  論文  参考訳（メタデータ） (2020-05-11T10:06:40Z)

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

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