連続（逐次）設定におけるリッジ・レバレッジ・スコアを用いたナイストロム法の解析

arXiv cs.LG / 2026/4/23

💬 オピニオンDeveloper Stack & InfrastructureModels & Research

共有:

要点

本論文は、大規模なカーネルリッジ回帰（KRR）でカーネル行列全体の保存を避けるために、ナイストロム型の列サブサンプリングを用いる問題設定を扱い、サンプリング分布がトレードオフに与える影響を指摘しています。
リッジ・レバレッジ・スコア（RLSs）に比例したサンプリングが復元に強い保証を与えることを活用しつつ、RLSs を厳密に計算するのはKRRと同程度に難しい点に対処します。
著者らは、カーネル行列の小さなスケッチを保持しながらRLSsを逐次的に推定する INK-ESTIMATE というアルゴリズムを提案しています。
INK-ESTIMATE は、既に見た列へのアクセスを不要にするスケッチ更新を行うため、カーネル行列に対する1回のパスで実行でき、さらに必要な空間計算量はカーネルの有効次元に依存する小さな固定予算で済みます。
真のカーネル行列と近似カーネル行列の距離に関する近似保証に加えて、任意の途中ステップにおける近似KRR解の統計的リスクについても強い保証が得られることを示しています。