Establishing an $\Omega(\sqrt{d})$ complexity lower bound for PDMP samplers and how to break it: a sub-$\sqrt{d}$ algorithm for Gaussian-tailed targets

技術要約：PDMPサンプラーにおける$\Omega(\sqrt{d})$の計算量下限の確立、およびガウス型裾を持つターゲットに対するSub-$\sqrt{d}$アルゴリズム

問題提起
Bouncy Particle Sampler (BPS) や Zig-Zag プロセスに代表される Piecewise Deterministic Markov Process (PDMP) サンプラーは、従来のマルコフ連鎖モンテカルロ（MCMC）法に代わる非可逆的な選択肢を提供する。しかし、その理論的な魅力にもかかわらず、既存のPDMPサンプラーの中で、次元 $d$ に対して $O(\sqrt{d})$ を超えるスケーリングを実現したものは存在しない。対照的に、勾配ベースの可逆的手法である Hamiltonian Monte Carlo (HMC) や Metropolis-Adjusted Langevin Algorithm (MALA) は、$O(d^{1/4})$ および $O(d^{1/3})$ という優れたスケーリングを達成している。本研究が取り組む中心的な問いは、$O(\sqrt{d})$ の障壁がPDMPフレームワーク固有の限界なのか、それとも単に特定のアルゴリズム設計の結果に過ぎないのかという点である。

手法
本論文は、理論的な下限の証明と、標準的な仮定を緩和する新しいアルゴリズムの構築という、二段構えのアプローチを採用している。

1. 理論的下限:
   著者は、広範なローカルPDMPサンプラーに対する $\Omega(\sqrt{d})$ の計算量下限を確立している。この証明は、以下の構造的な仮定に基づいている：

• ターゲットへの独立性: 決定論的なフローと補助空間は、特定のターゲット分布 $\pi$ に依存しない。
• 局所的なジャンプ: ジャンプカーネルは補助変数を変化させるが、空間的位置は変化させず、これにより空間軌跡の絶対連続性が保証される。
• 不変性: ターゲット分布は、離散的なサンプリング時点だけでなく、すべての連続時間において不変でなければならない。

独立同一分布（i.i.d.）のターゲットを分析することで、定常方程式 $L^*\mu = 0$ を満たすためには、期待ジャンプ率 $\mathbb{E}[\lambda]$ が $\Omega(\sqrt{d})$ のオーダーでスケールしなければならないことを証明している。実質的に独立したサンプル間の距離は $\sqrt{d}$ に比例して増大するため、独立したサンプルあたりの平均的なジャンプ数は $\Omega(\sqrt{d})$ となる。

2. アルゴリズムの革新（障壁の打破）:
   この限界を回避するために、本論文では、ターゲット密度がすべての連続時間において不変である必要があるという仮定を緩和するアルゴリズムを提案している。具体的には、ターゲットが標準的なMCMCと同様に、離散的なサンプリング時のみ不変であることを許容する。

• フレームワーク: この手法は、Metropolised NUTS-PDMP フレームワークに、HMCのリープフロッグ積分から着想を得た新しい Oscillating PDMP ダイナミクスを統合したものである。
• ダイナミクス: プロセスは、ランダムな連続時間において、位置の更新（$\dot{x} = v$）と速度の更新（$\dot{v} = -\nabla U(x)$）を交互に行う（固定間隔ではなく）。
• パスの再重み付け: 連続的な軌跡がターゲット測度を厳密に保存しないため、本アルゴリズムはパス・リサンプリング戦略を採用している。イベントレートの数値近似を用いて軌跡を生成し、条件付き確率密度に基づいて軌跡上の状態を再サンプリングする。この密度は、パスに沿ったハミルトニアンの変動を補正するために状態を再重み付けし、最終的な出力がターゲットからの正確なサンプルとなることを保証する。
• 適応性: アルゴリズムは、軌跡の長さを適応的に決定するために No-U-Turn (NUTS) 基準を利用し、さらに速度更新に対して局所的な適応ステップサイズを用いることで、可逆的なHMCで必要とされる複雑なグローバル・チューニング戦略を回避している。

主な貢献

• 計算量の下限: 標準的なPDMPサンプラー（連続時間の不変性を強制するもの）は、i.i.d. ターゲットに対して根本的に $\Omega(\sqrt{d})$ の計算量に制限されることを示す厳密な証明を提示した。
• Sub-$\sqrt{d}$ アルゴリズム: 連続時間の不変性を放棄した、新しい Metropolised PDMP アルゴリズムを導入した。パスの再重み付けと数値近似を活用することで、ガウス型の裾を持つターゲットに対して $O(d^\alpha)$ （ここで $\alpha \in [0.2, 0.3]$）の計算量を達成した。
• 局所的適応性: 提案されたフレームワークは、軌跡の長さと速度更新の間隔の両方において、自然に局所的な適応性を組み込むことができる。これは、複雑な戦略なしには可逆的なHMCで実装することが困難な機能である。

実証結果
著者は、5つのターゲット分布に対し、次元 $d \in \{2, \dots, 128\}$ におけるスケーリング結果を提示している：

• ガウス型の裾を持つターゲット: 標準ガウス分布、ベイズ・ロジスティック回帰、およびガウス混合モデルのターゲットにおいて、有効サンプルサイズ（ESS）あたりのイベント数は $O(d^{0.22})$ から $O(d^{0.29})$ の間でスケールする。勾配評価の数は $O(d^{0.26})$ から $O(d^{0.31})$ の間でスケールする。これらの結果は、従来のPDMPの $O(\sqrt{d})$ の限界を大幅に上回り、HMCの理論的なスケーリングに接近している。
• 非ガウス型ターゲット: アルゴリズムは、より重い裾を持つ（ロジスティック）分布や軽い裾を持つ（四次関数）分布に対しても堅牢性を示したが、スケーリング指数は高くなっており（$O(d^{0.43})$ から $O(d^{0.64})$）、これらがより困難なターゲットであることを反映している。

意義と主張
本論文は、標準的なPDMPフレームワークにおける根本的な限界を特定したと主張している。すなわち、連続時間の不変性の要求こそが、より優れた次元スケーリングを妨げている主要なボトルネックである。この制約を緩和することで、PDMPが sub-$\sqrt{d}$ のスケーリングを達成できることを示し、HMCとの性能差を埋めた。本研究は、「sub-$\sqrt{d}$」の性能が特定の設計によるアーティファクトではなく、メトロポリス・ハスティング法による再重み付けを介して近似的な不変性を運用することによって得られる結果であることを示唆している。結論として、標準的なPDMPに対する理論的な下限は確立されているものの、提案されたアルゴリズムは、特にガウス型の裾を持つターゲットに対して、PDMPの非可逆的な利点を維持しつつ、高次元での効率化への実用的な道筋を提供するものである。