A Profile-Separation Framework for Quantitative Convergence of No-U-Turn Samplers

技術要約：NUTS（No-U-Turn Sampler）の定量的収束に向けたプロファイル分離フレームワーク

問題提起
ハミルトニアン・モンテカルロ法（HMC）は、ハミルトニアン軌道をシミュレートすることで遠方の提案生成を行うが、その効率は積分時間に決定的に依存する。軌道が短すぎると移動が最小限に留まり、長すぎると訪れた領域を逆行して計算を無駄にする。NUTSは、エンドポイントの診断（モーメントベクトルが始点に向いていることを示す指標）によってリープフロッグ軌道を適応的に構築し、終了させることでこの問題に対処する。NUTSは確率的プログラミング・システム（StanやPyMCなど）の実用的な成功の中心であるが、その状態依存的かつ再帰的な停止規則は、歴史的に定量的な混合理論の開発を阻んできた。既存のNUTSに関する非漸近的な境界値の多くは、ランダムなUターン診断が決定論的な正弦関数に集中するガウス型ターゲット構造に依拠していた。このような結果を一般的な強対数凹（strongly log-concave）ターゲットへと拡張することは、リフレッシュされたモーメント、ランダムな倍数決定、数値的なエネルギー誤差、および特定の選択規則の間の結合依存性により、依然として大きな課題となっている。

手法
本論文は、$(m, L)$-強対数凹ターゲット（フロベニウス・ヘッセ行列の正則性を満たすもの）に対する多項式（multinomial）およびバイアス付き漸進的（biased-progressive）NUTS変数の定量的収束を確立するためのプロファイル分離フレームワークを導入する。コアとなる手法は、以下のステップを通じて、適応的な停止メカニズムを混合解析からデカップリングすることである：

1. 定常Uターン・プロファイル： 著者は、決定論的な集団レベルのオブジェクトである定常プロファイル $u(t) = \mathbb{E}[V_0^\top (X_t - X_0)]$ を定義する。これはNUTSで使用されるエンドポイント診断の平衡平均を表す。一般的なターゲットの場合、これは明示的なガウス型の正弦関数の代わりとなる。
2. プロファイル分離： 特定の深さ $k^*$ が「プロファイル分離されている」という十分条件を導入する。これには、プロファイル $u(t)$ がすべての事前終端ダイアディック（dyadic）期間において一様に正であり、かつ候補となる終端期間において一様に負であり、かつそのマージンが $d/\sqrt{m}$ のオーダーであることを要求する。
3. 固有診断の安定性： 実践的な数値診断（リープフロッグに基づくもの）と正確な集団プロファイルとの偏差を定量化する。これには以下が含まれる：
   • 正確なスカラー診断の $u(t)$ 周辺への集中。
   • これらの診断におけるリープフロッグの数値誤差。
   • 一様なエネルギーウィンドウの失敗。
   • 極めて短い区間における正値性の失敗。
4. 終端深度の認証： プロファイル分離のマージンが、結合された確率的および数値的誤差を上回るという仮定の下で、あらゆるランダムな倍数決定の実現が、真のUターンを介して、最大深度キャップに達する前に、同一のカーディナリティ $K^*$ で終了することを証明する。
5. 終端深度から連結度への転送： 共通の終端深度とエネルギーウィンドウが認証されると、NUTSの遷移は固定インデックスのリープフロッグ提案の明示的な混合物を含むことが示される。著者は、ランダムな倍数決定の初期点対称性と詳細釣合い恒等性を利用して、チェガー（Cheeger）の等長性（isoperimetry）を適用して制限付き連結度境界を導出するための正の作用素（多項式の場合は直交射影、バイアス付き漸進的な場合は2ステップ・スケルトン）を構成する。

主な貢献

1. ターゲットに依存しない停止証明： 本論文は、ガウス解析における決定論的プロファイル・メカニズムを「プロファイル分離」へと抽象化し、これをガウス型以外の一般的な強対数凹ターゲットに適用可能な条件へと昇華させた。これにより、実践的なリープフロッグ・ツリーによって検査されるすべての完全な軌道および再帰的サブツリーに対して、符号を伝達する固有の証明書を提供する。
2. 終端深度から連結度への定理： 共通の終端深度が認証されると、適応的なNUTSの遷移が固定時間の移動推定値によって抑えられることを示す新しい定理を確立する。これは、軌道の問題（どこでツリーが止まるか）と混合の問題（カーネルがカットを横切るか）を分離するものである。
3. 非レイジー・カーネルのための正の作用素： 著者らは、人工的なレイジー化（lazification）を伴わない元の多項式およびバイアス付き漸進的カーネルが、正のスペクトル特性を持つことを示す。多項式の再ルーティングは直交射影であることが示され、バイアス付き漸進的カーネルの2ステップ・スケルトンは半正定値であり、カーネルを修正することなく連結度議論を可能にすることが示される。
4. 一般的な軌道および数値解析： 非線形プロファイルのための平衡恒等式、平均二乗変位の不等式、および普遍的な初期正値性の境界を提供している。これらは、全ハミルトニアン・ヤコビアンの境界を必要とせずに、正確な診断の集中および決定論的なリープフロッグとフローの比較を確立する。
5. 検証ルート： 固有の証明書のための具体的な検証ルートを提供する。これには、非線形積のスペクトル表現、近等方ターゲットに対する摂動境界、および線形異方性を除去するためのメトリック適応の条件が含まれる。

結果
主要な定理（定理 3.7）は、ウォームスタート混合のための無条件な遷移境界を提供する。$T^*$ を選択された物理的軌道長、$a^* = \sqrt{m}T^*$ とする。全変動誤差 $\epsilon$ に達するために必要な遷移数 $n$ は、以下によって抑えられる：

• 多項式NUTS： $\tilde{O}\left( (1 + a^{*2}\kappa^2(1+\gamma)^{4/3}) \log(M/\epsilon) \right)$
• バイアス付き漸進的NUTS： $\tilde{O}\left( (1 + a^{*4}\kappa^3(1+\gamma)^2) \log(M/\epsilon) \right)$

ここで $\kappa = L/m$ は条件数であり、$\gamma$ はヘッセ行列の正則性に関連する。

計算量に関しては、本論文は認証された遷移と未認証の遷移を区別している。認証イベントにおいて、コストは選択された深度 $K^*$ に比例する。最大深度キャップに関する追加の制限がない場合、無条件の決定論的計算量境界は最大キャップ $K_{cap}$ に比例する。しかし、著者は $K^*$ と $K_{cap}$ の間を補完する洗練された期待値および高確率境界を提供しており、$K_{cap}$ が認証された深度と同程度である場合、決定論的次数 $K^* n$ を回収する。

ガウス型ターゲットの場合、本フレームワークは次元依存性 $\tilde{O}(d^{1/4})$ を回収し、先行研究のガウス特化型文献で特定された「加速」および「トラップ」のレジームを明示的に特徴付け、プロファイル分離が2スケール・ダイコトミー（二分法）を回収することを示す。

意義と主張
本論文は、ガウス構造や人工的な修正（レイジー化やメトロポリス補正など）に依存しない、一般的な強対数凹ターゲットに対する実用的なNUTSの最初の定量的混合理論を提供すると主張している。主要な貢献は、軌道から混合への還元であり、プロファイル分離が、統計的および数値的誤差によってゼロから分離されている限り、実践的なNUTSの適応的な停止メカニズムが、固定時間のHMC推定を利用できるほど予測可能に振る舞うことを実証した点にある。

著者は、結果がグローバルかつ無条件の遷移境界である一方で、未認証の遷移（キャップまで実行されるもの）がマルコフ連鎖の一部であることを反映するために、計算量は別途考慮されていることを強調している。本フレームワークは、線形異方性を除去するために固定されたポスト・ウォームアップ・メトリックを使用することを正当化し、高次元の非ガウス設定におけるNUTSの経験的な成功に対して厳密な基礎を提供する。本論文は、プロファイル分離が急速な混合のために必要であると主張しているのではなく、それが広範なクラスのターゲットにわたって適応的HMCの解析を統一する十分条件であることを主張している。