Warm-Starting Iterative Gaussian Processes for Faster Sequential Inference

技術要約：逐次推論を高速化するための反復ガウス過程のウォームスタート

問題提起
ガウス過程（GP）は回帰、分類、およびベイズ最適化のための強力な非パラメトリックモデルであるが、そのスケーラビリティは、後験分布を計算するために共分散行列を反転させる際の $O(n^3)$ のコストによって制限される。反復解法（共役勾配法、確率的勾配降下法、交互射影法など）は、立方体のコストを回避して解を近似する方法を提供するが、通常、収束には多くの反復を必要とする。逐次的設定（能動学習、オンライン予測、ベイズ最適化など）において、データが漸進的に到着し、後験分布を頻繁に更新する必要がある場合、標準的な「コールドスタート」アプローチ（すべての重みをゼロに初期化し、以前の計算を破棄する手法）はボトルネックとなる。この非効率性は、動的な環境における反復型GPの有効性を制限している。

手法
本論文は、新しいデータ点を用いてGPの後験を更新する際に、反復線形ソルバーを初期化するための3つの「ウォームスタート」戦略を提案している。以前のより小さな線形システムの解（$u_1$）を利用して、新しいより大きなシステムの重み（$v$）を初期化することで、拡張された線形システムをゼロから解く代わりに、これらの手法は既存の解を活用する。

問題は、既存のデータ（ブロック1）と新しいデータ（ブロック2）を含めるように分割された行列 $H$ とベクトル $b$ を持つ、拡張された線形システム $Hv = b$ を解くこととして定式化される。提案されている3つの初期化手法は以下の通りである：

1. ナイーブ・ウォームスタート（Naïve Warm-Start）: 元のデータの重み（$v_1$）を以前の解（$u_1$）に初期化し、新しいデータの重み（$v_2$）をゼロに初期化する。
   $$v \leftarrow \begin{bmatrix} u_1 \\ 0 \end{bmatrix}$$
2. 残差ラインサーチ（Residual Line Search）: この手法は、残差の方向に最適なスカラー $\alpha$ を決定するためにラインサーチを行うことで、ナイーブなアプローチを改善する。これは、固定された $v_1 = u_1$ の下で二次目的関数を最小化する。
   $$v_2 = \alpha^* r, \quad \text{ただし } r = b_2 - H_{12}^\top u_1 \text{ および } \alpha^* = \frac{r^\top r}{r^\top H_{22} r}$$
3. 周辺システム解法（Marginal System Solve）: 最も複雑なこの手法は、より小さな周辺線形システム（$H_{22}v_2 = r$）を解き、$v_1 = u_1$ の条件下で目的関数を最小化する最適な $v_2$ を求める。
   $$v_2 = H_{22}^{-1} r$$

理論的分析
著者らは、正確な解を $v^*$ としたとき、再生核ヒルベルト空間（RKHS）距離 $d^2 = (v - v^*)^\top H (v - v^*)$ を用いて理論的な裏付けを提供している。彼らは以下を実証した：

• ナイーブ・ウォームスタートは、コールドスタートと比較してRKHS距離を厳密に減少させる（$d^2_{cold} - d^2_{naïve} \geq 0$）。
• 残差ラインサーチと周辺システム解法の両方は、この距離をさらに減少させる（$d^2_{naïve} > d^2_{line-search} > d^2_{marginal-solve}$）。
• RKHS距離を減少させることは、線形システムの初期残差を減少させることと同等であり、これは収束に必要な反復回数と直接相関している。

主な貢献と結果
本論文はこれら3つの初期化戦略を導入し、理論的分析および回帰ベンチマークとベイズ最適化タスクを用いた経験的実験を通じて検証を行っている。

• 回帰実験: UCIリポジトリのデータセット（例：3droad, protein, buzz）を用い、収束に必要な反復回数をコールドスタートのベースラインと比較した。

  • 高速化: 特定の許容誤差まで解く際、ウォームスタートは共役勾配法（CG）で最大1.4倍、確率的勾配降下法（SGD）で最大1.5倍、交互射影法（AP）で最大4.0倍の高速化を達成した。
  • 極端なケース: APにおいて、特に新しいデータの既存データに対する比率が小さい場合、特定のデータセットで最大19倍の高速化に達した。
  • 精度: 固定された計算予算（限定された反復回数）の下で、ウォームスタートはより正確な後験推定値を生み出し、最終的な残差ノルムを減少させた。

• ベイズ最適化（並列トンプソンサンプリング）: 固定された計算予算を用いた並列トンプソンサンプリングの実験において、これらの手法が目的関数を最大化する能力を評価した。

  • 性能向上: ウォームスタート手法は、コールドスタートと比較して、目的関数で見出された最終的な最大値を、CGで最大13%、SGDで最大46%、**APで最大10%**向上させた。
  • 蓄積される進捗: 結果は、ウォームスタートを行う場合、ソルバーの進捗がリセットされるのではなく、複数の逐次的な解法にわたって蓄積され、より正確な後験サンプルとより優れた最適化性能につながることを示した。

意義
本論文は、逐次的設定におけるガウス過程のスケーラビリティを向上させるための、シンプルかつ効果的で広く適用可能なツールとして、ウォームスタートを確立している。より小さな線形システムの解を利用することで、精度を犠牲にする疎近似を必要とせずに、これらの手法は収束を大幅に加速させる。著者らは、このアプローチが逐次的決定タスクにおけるスケーラビリティのボトルネックに直接対処し、同じ計算制約内でより頻繁かつ正確な後験更新を可能にすると主張している。これらの手法は、既存の反復ソルバー（CG, SGD, AP）と統合して、GPベースのアプリケーションの効率を向上させるための実用的な強化策として提示されている。