必要最小限だけ詰める：カーネルリッジ回帰のための適応型辞書学習

要旨: カーネルリッジ回帰（KRR）の主要な制約の1つは、n個のサンプルに対するカーネル行列K_nを保存し、操作するのにO(n^2)の空間が必要であり、それが大きなnに対して急速に実行不可能になる点です。Nystrom近似は、K_nからm個の列をサンプリングすることで、空間計算量をO(nm)へと削減します。一様サンプリングは、K_nの最大自由度（最大次数の自由度）に比例するmが必要な場合に限り、KRRの精度（εまで）を保持しますが、コヒーレンスが高いデータセットでは最大でO(n)個の列が必要になることがあります。リッジ・レバレッジスコア（RLS）に従って列をサンプリングすると、効果次元（effective dimension）に比例したmで正確なNystrom近似が得られますが、正確なRLSの計算にも同様にO(n^2)の空間が必要です。
（Calandriello et al. 2016）は、データセットを逐次的に処理し、RLS、効果次元、そしてNystrom近似をその場（on-the-fly）で更新するアルゴリズムであるINK-Estimateを提案しています。その空間計算量は効果次元に比例して増加しますが、最大固有値（largest eigenvalue）への依存が導入されており、最悪の場合それはO(n)です。
本論文では、INK-Estimateを基にしつつ、正規化されていないRLSを用いる新しいアルゴリズムSQUEAKを導入します。その結果、アルゴリズムはより単純になり、正規化のために効果次元を推定する必要がなくなり、必要な空間計算量は正確なRLSサンプリングに比べて定数倍だけ悪いにとどまります。