論文の概要: Pack only the essentials: Adaptive dictionary learning for kernel ridge regression

• arxiv url: http://arxiv.org/abs/2604.22386v1
• Date: Fri, 24 Apr 2026 09:22:09 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-04-27 15:36:26.412946
• Title: Pack only the essentials: Adaptive dictionary learning for kernel ridge regression
• Title（参考訳）: Pack only the essentials: Adaptive Dictionary Learning for kernel ridge regression
• Authors: Daniele Calandriello, Alessandro Lazaric, Michal Valko,
• Abstract要約: カーネルリッジ回帰 (KRR) の大きな限界の1つは、n 個のサンプルに対するカーネル行列 K_n の保存と操作が O(n2) 空間を必要とすることである。 INK-Estimateはデータセットを漸進的に処理し、RSS、有効次元、Nystrom近似をオンザフライで更新するアルゴリズムである。 本稿では,INK-Estimateをベースとした非正規化RSSを用いた新しいアルゴリズムであるSQUEAKを紹介する。
• 参考スコア（独自算出の注目度）: 69.32538992633842
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: One of the major limits of kernel ridge regression (KRR) is that storing and manipulating the kernel matrix K_n for n samples requires O(n^2) space, which rapidly becomes unfeasible for large n. Nystrom approximations reduce the space complexity to O(nm) by sampling m columns from K_n. Uniform sampling preserves KRR accuracy (up to epsilon) only when m is proportional to the maximum degree of freedom of K_n, which may require O(n) columns for datasets with high coherence. Sampling columns according to their ridge leverage scores (RLS) gives accurate Nystrom approximations with m proportional to the effective dimension, but computing exact RLS also requires O(n^2) space. (Calandriello et al. 2016) propose INK-Estimate, an algorithm that processes the dataset incrementally and updates RLS, effective dimension, and Nystrom approximations on-the-fly. Its space complexity scales with the effective dimension but introduces a dependency on the largest eigenvalue of K_n, which in the worst case is O(n). In this paper we introduce SQUEAK, a new algorithm that builds on INK-Estimate but uses unnormalized RLS. As a consequence, the algorithm is simpler, does not need to estimate the effective dimension for normalization, and achieves a space complexity that is only a constant factor worse than exact RLS sampling.
• Abstract（参考訳）: カーネルリッジ回帰 (KRR) の大きな限界の1つは、n 個のサンプルに対するカーネル行列 K_n の保存と操作には O(n^2) 空間が必要であることである。 ナイストローム近似は、K_n から m カラムをサンプリングすることで空間複雑性を O(nm) に還元する。 一様サンプリングは、M が K_n の最大自由度に比例する場合のみ KRR の精度(エプシロンまで)を保ち、コヒーレンスの高いデータセットに対して O(n) 列を必要とする。 リッジレバレッジスコア(RLS)に従って列をサンプリングすると、実効次元に比例するmの正確なナイストロム近似が得られるが、正確な RLS も O(n^2) 空間を必要とする。 (Calandriello et al 2016)は、データセットを漸進的に処理し、RSS、有効次元、Nystrom近似をオンザフライで更新するアルゴリズムであるINK-Estimateを提案する。 その空間複雑性は実次元でスケールするが、K_n の最大の固有値(最悪の場合 O(n) )に依存する。 本稿では,INK-Estimateをベースとした非正規化RSSを用いた新しいアルゴリズムであるSQUEAKを紹介する。 その結果、アルゴリズムはより単純で、正規化の有効な次元を見積もる必要がなく、正確なRSSサンプリングよりも悪い一定の要素しか持たない空間複雑性を実現する。

関連論文リスト

• Analysis of Nystrom method with sequential ridge leverage scores [69.32538992633842]
  大規模なカーネルリッジ回帰(KRR)は、大規模なカーネルマトリックスK_tを格納する必要があるため制限される。 近年の研究では、尾根レバレッジスコア(RLS)に比例するサンプリング分布が、近似に強い再構成保証をもたらすことが示されている。 本稿では,LS推定値を漸進的に計算するINK-ESTIMATEアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2026-04-22T00:49:25Z)
• Robust Kernel Sparse Subspace Clustering [0.0]
  本稿では,カーネルスパースSC (RKSSC) アルゴリズムを初めて提案する。 この概念は、原則として他のSCアルゴリズムにも適用でき、この種の汚職の存在に対して堅牢性を達成することができる。
  論文  参考訳（メタデータ） (2024-01-30T14:12:39Z)
• On the Size and Approximation Error of Distilled Sets [57.61696480305911]
  カーネル・インジェクション・ポイント(Kernel Inducing Points)などのデータセット蒸留のカーネル・リッジ回帰に基づく手法について理論的に考察する。 我々は、RFF空間におけるその解が元のデータの解と一致するように、元の入力空間に小さな一組のインスタンスが存在することを証明した。 KRR溶液は、全入力データに最適化されたKRR溶液に対して近似を与えるこの蒸留されたインスタンスセットを用いて生成することができる。
  論文  参考訳（メタデータ） (2023-05-23T14:37:43Z)
• Efficient Dataset Distillation Using Random Feature Approximation [109.07737733329019]
  本稿では,ニューラルネットワークガウス過程(NNGP)カーネルのランダム特徴近似(RFA)を用いた新しいアルゴリズムを提案する。 我々のアルゴリズムは、KIP上で少なくとも100倍のスピードアップを提供し、1つのGPUで実行できる。 RFA蒸留 (RFAD) と呼ばれる本手法は, 大規模データセットの精度において, KIP や他のデータセット凝縮アルゴリズムと競合して動作する。
  論文  参考訳（メタデータ） (2022-10-21T15:56:13Z)
• SreaMRAK a Streaming Multi-Resolution Adaptive Kernel Algorithm [60.61943386819384]
  既存のKRRの実装では、すべてのデータがメインメモリに格納される必要がある。 KRRのストリーミング版であるStreaMRAKを提案する。 本稿では,2つの合成問題と2重振り子の軌道予測について紹介する。
  論文  参考訳（メタデータ） (2021-08-23T21:03:09Z)
• Square Root Bundle Adjustment for Large-Scale Reconstruction [56.44094187152862]
  QR分解によるランドマーク変数のnullspace marginalizationに依存するバンドル調整問題の新たな定式化を提案する。 平方根束調整と呼ばれる私たちのアプローチは、一般的に使用されるSchur補完トリックと代数的に等価です。 BALデータセットを用いた実世界での実験では、提案されたソルバが単一の精度でも平均的等しく正確なソリューションで達成できることを示す。
  論文  参考訳（メタデータ） (2021-03-02T16:26:20Z)
• Faster Kernel Interpolation for Gaussian Processes [30.04235162264955]
  大規模データセットへのプロセス(GP)回帰のスケーリングにおける重要な課題は、正確な推論がnxnのカーネル行列を必要とすることである。 構造化カーネル(SKI)は最もスケーラブルな方法の一つである。 1つのO(n)時間前計算ステップの後、SKIをO(m log m)に還元できることが示される。 我々は, m と n の広い範囲で実際に高速化を実演し, 1億点を超える3次元気象レーダデータセット上でGP推定に適用した。
  論文  参考訳（メタデータ） (2021-01-28T00:09:22Z)
• Adaptive Explicit Kernel Minkowski Weighted K-means [1.3535770763481905]
  カーネル K-平均は、K-平均をカーネル空間に拡張し、非線形構造を捉えることができ、任意の形状のクラスターを識別することができる。 本稿では, 線形および非線形アプローチの利点を, 駆動された対応する有限次元特徴写像を用いて組み合わせる手法を提案する。
  論文  参考訳（メタデータ） (2020-12-04T19:14:09Z)

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

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