技術要約：再生核ヒルベルト空間における教師あり学習のためのサブサンプリング

問題提起

ビッグデータの時代において、大規模なデータセットに対して統計的学習モデルを訓練する際に伴う計算コストとエネルギー消費は、極めて重要なボトルネックとなっている。様々なデータ削減手法（スケッチ、コアセット、確率的最適化など）が存在するが、その多くはタスクに依存しない（task-agnostic）か、あるいは最適な選択のための計算困難な確率に依存している。特に、仮説が再生核ヒルベルト空間（RKHS）内に存在する非パラメトリック教師あり学習において、既存の手法は、推定量の漸近分散を最小化するような、データ依存型の最適なサブサンプリング・スキームを提供できないことが多い。カーネル法は通常、元のデータセットサイズ $n$ に対して $O(n^2)$ または $O(nm)$の計算量を要するため、スケーラビリティに課題がある。サブサンプリングはこれを$O(s^2)$（ここで$s \ll n$）に削減するが、標準的な一様サブサンプリングは個々のデータ点の情報価値を無視しており、推定精度において劣った結果をもたらす。

手法

著者らは、経験的リスクの不偏推定を保証するためにホーブーツ・トンプソン（Horvitz-Thompson）再重み付けスキームを利用した、RKHSにおける**サブサンプリング・リスク最小化（SRM）**のフレームワークを提案している。コアとなる手法は以下の通りである：

1. 理論的枠組み:

   • 設定: 凸かつ2回微分可能な損失関数 $\ell$ とリッジペナルティを持つ、非パラメトリック教師あり学習（分類および回帰）。推定量は正則化された経験的リスクを最小化する。
   • サブサンプリング戦略: 本論文では2つの戦略を分析している：
     • 多項式サブサンプリング（復元抽出）: 包含確率 $\pi_{n,i}$ を伴って独立に点を選択する。
     • ポアソン・サブサンプリング（非復元抽出）: 確率 $s_n \pi_{n,i}$ で独立に点を含める。
   • 漸近解析: 関数確率空間とマルチンゲール理論のツールを用いることで、著者らはSRM推定量の漸近正規性を確立している。彼らは、包含確率 $\pi_{n,i}$ に依存する漸近共分散作用素 $\Sigma^*$ を導出している。

2. 最適サブサンプリング・スキーム:

   • 著者らは、L-最適性を、漸近共分散作用素のトレース（真のリスクのヘッセ行列による前処理済み）を最小化することと定義している。
   • 彼らは、最適な包含確率を決定するL-最適絶対関心関数 $\psi^*$ の閉形式の表現を導出した：
     $$\psi^*(z) = |\ell'(h_0(x), y)| \sqrt{k(x, x)}$$
     ここで、$h_0$ は真の正則化リスク最小化因子、$\ell'$ は損失の微分、$k$ はカーネルである。
   • これは、予測誤差が大きく（大きな $|\ell'|$）、あるいはカーネルの自己類似性が高いデータ点が、より高い確率でサンプリングされるべきであることを意味している。

3. 実用的実装（パイロット推定器）:

   • $h_0$ は未知であるため、著者らはプラグイン・アプローチを提案している：
     1. 小規模なデータ部分集合（$k_n \ll s_n$）を用いて、パイロット推定器 $\hat{h}_{k_n}$ を計算する。
     2. $\hat{h}_{k_n}$ を用いて最適な確率を推定する。
     3. 推定された確率が技術的な仮定（具体的には、確率が速すぎる速度でゼロに収束しないこと）を満たすように、ハイパーパラメータ $\alpha \in (0, 1]$ を用いて平滑化を行う：
        $$\tilde{\pi}_{n,i}^\alpha = (1-\alpha)\tilde{\pi}_{n,i} + \frac{\alpha}{n}$$
     4. ポアソン・サブサンプリングの場合、確率が有効な範囲（$\leq 1/s_n$）に収まるように事後的な切り捨て（truncation）を適用する。
   • この $\alpha$-パイロット推定器に対して、一貫性と漸近正規性の理論的保証が提供されている。

主な貢献

• RKHSにおける漸近正規性: 本論文は、関数的確率空間の手法とマルチンゲール理論を用いることで、無限次元のRKHSにおけるサブサンプリング推定量の漸近正規性を確立しており、パラメトリックな結果とは一線を画している。
• 最適スキームの導出: 非パラメトリック・カーネル法に特化した最適なサブサンプリング・スキームの最初の導出を行い、最適な包含確率がカーネルの対角成分で重み付けされた損失勾配の大きさの大きさに比例することを示した。
• 戦略の比較: 著者らは、多項式サブサンプリングとポアソン・サブサンプリングのトレードオフを分析し、最適な選択が極限比 $c = \lim s_n/n$ に依存することを実証している。注目すべきは、リッジ正則化の存在により、これら2つの戦略は $c=0$ の場合において、パラメトリックな設定での知見とは異なり、漸近的効率が同一ではない点である。
• 堅牢な実用的アルゴリズム: パイロット推定器と平滑化および切り捨てを組み合わせた2段階の「パイロット」アルゴリズムの提案は、統計的保証を維持しながら、理論的に最適なスキームを実用可能にしている。

結果

合成データセット（分類および回帰）および実世界のデータセット（UCI Covertype）を用いて、提案された $\alpha$-パイロットSRMを以下と比較する数値実験を行った：

• 一様サブサンプリング（ベースライン）。
• Nyström法。
• ランダムフーリエ特徴量（RFF）。
• カーネル・スケッチ。

知見:

• 平滑化パラメータ: $\alpha$ が 0.1 から 0.4 の間のとき、最適サブサンプリングの利点と一様サンプリングの安定性のバランスが取れ、汎化誤差が最小となった。
• 大規模データ・レジーム: 大規模なデータセットにおいて、提案されたSRMは、汎化誤差と計算時間（CPU）のトレードオフにおいて、一様サブサンプリングを大幅に上回る性能を示した。
• 近似手法との比較: 実世界のCovertypeデータセットにおいて、SRM法はNyström、RFF、およびスケッチよりも効率的であった。低次元の合成タスクにおいては、カーネル近似（Nyström、RFF）の方が高速であり、これはサブサンプリングとカーネル近似が相補的な技術であることを示唆している。
• ハイブリッド・アプローチ: サブサンプリングとNyström法を組み合わせることで、さらに性能が向上した。これは、本手法が既存のカーネル近似技術と互換性があることを示している。

意義と主張

本論文は、統計的効率を損なうことなく、カーネルベース学習の計算負荷を軽減するための、理論的根拠に基づいた実用的な手法を提供すると主張している。漸近共分散のトレースに基づいて最適なサブサンプリング・スキームを導出することで、著者らは大規模なデータセットから「情報量の多い」個体を取り出す方法を提示している。

著者らは、本研究をよりエネルギー効率の高い学習への一歩として控えめに位置づけている。本手法は最適化問題のサイズを $O(n^2)$ から $O(s^2)$ へと削減するものの、パイロット推定器に依存していることを指摘している。また、現在の理論は正則化されたリスクに基づいていることを認め、非正則化設定への拡張や、多段階のオンライン・プロシージャの開発が今後の研究の方向性であるとしている。本研究は、既存のパラメトリックなサブサンプリング理論では十分にカバーされていない、RKHS特有の課題に対処している点で独自性を持っている。