Nystrom 法と連続的に計算されたリッジレバレッジスコアの解析

arXiv:2604.20077v1 告知 タイプ：新規 要旨: 大規模な核関数回帰（KRR）は、大規模な核関数行列 K_t を保存する必要があるため、制約に苦しんでいます。KRR 法では、Nystrom 法は核関数行列 K_t の列のサブセットをサンプリングし、再構築された行列上で近似 KRR 解を効率的に求めます。選択されたサンプリング分布は、統計的な計算上のトレードオフに影響を与えます。KRR 問題については、近頃の研究では、リッジレバレッジスコア（RLS）に比例したサンプリング分布は、近似の再構築保証を提供する強力な手法であることを示しています。正確な RLS は KRR 解と同じくらい計算が困難ですが、十分に良い近似が可能であるかもしれません。この論文では、我々は KRR 問題をシーケンス設定で研究し、間欠的に RLS 推定量を計算する INK-ESTIMATE 算法を導入しました。INK-ESTIMATE は、各ステップで RLS の中間推定量を計算するために、K_t の小さなスキャッチーを維持します。まず、我々のスキャッチー更新は、以前に見た列へのアクセスを必要としないため、核関数行列の単一パスで十分です。第二に、アルゴリズムは核関数行列の有効次元のみに関与する、固定された小さな空間予算で実行されます。最後に、我々のスキャッチーは、真の核関数行列とその近似との間の距離について、そして任意の時間における近似 KRR 解の統計的リスクについて、強い近似保証を提供します。これは、我々の保証がすべての中間段階で成り立っているからです。

arXiv:2604.20077v1 Announce Type: new 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.