Spectral Gaps of Hit-and-Run and Coordinate Hit-and-Run

技術要約：Hit-and-Run および Coordinate Hit-and-Run のスペクトル・ギャップ

問題提起
本論文は、凸体 $K \subset \mathbb{R}^n$ からのサンプリングにおける Hit-and-Run (HAR) および Coordinate Hit-and-Run (CHAR) マルコフ連鎖の収束率を扱う。Ball walk の収束については、Kannan, Lovász, and Simonovits (1997) によって、関数的等周定数（具体的にはポアンカレ定数および KLS 定数）との関連付けが成功しているが、Hit-and-Run について同様の関連付けは未解決の問題であった。Lovász and Vempala (2004) による従来の HAR の境界値は、体の外半径 $R$ に依存しており、混合時間は $O(n^2 R^2 \log(M/\varepsilon))$ となっていた。この $R$ への依存性は、準等方的な体に対しては最適ではなく、次元依存性が立方オーダーからほぼ二次オーダーへと改善できる可能性がある。さらに、Ball walk は初期の「温かさ（warmness）」パラメータに対して線形な依存性を被るのに対し、HAR は初期距離に対して対数的な依存性を維持することが知られている。中心となる問いは、初期距離に対する対数的な依存性を維持しつつ、HAR の収束率をポアンカレ／KLS 定数によって抑えることができるか、という点である。

手法
著者らは、従来の HAR 収束証明の基礎であったコンダクタンス（conductance）を境界付ける手法を回避する証明手法を導入する。代わりに、本論文では、スペクトル・ギャップを関数的等周定数に直接結びつけることで直接的に境界付ける。

手法の核心は以下の通りである：

1. 双対証明書（Dual Certificates）: スペクトル・ギャップは、双対証明書を用いて書き換えられる。この再定式化により、$H^1_0(K; \mathbb{R}^n)$ における発散方程式 $\text{div } u = f$ の可解性を特徴付ける Babuška–Aziz 定数（PDE 解析で研究されているもの）の特定へと至る。
2. 作用素の構成: 連鎖のディリクレ形式（エネルギー）のノルムに対応する有界線形作用素 $T$ を定義する。目標は、$T^* g_f = f$ かつ $\|g_f\| \leq C \|f\|$ を満たす双対証明書 $g_f$ を見つけることである。
3. 定数の接続: 証明は以下の不等式の連鎖を確立する：
   • スペクトル・ギャップは、Babuška–Aziz 定数 ($C_{BA}$) の逆数によって下限が抑えられる。
   • $C_{BA}$ は、境界までの距離 $\delta(x)$ を重みとして組み込んだ 改良ポアンカレ定数 ($C_{IPI}$) によって漸近的に抑えられることが示される。
   • $C_{IPI}$ は、単位球を含む凸体に対する標準的な ポアンカレ定数 ($C_{PI}$) によって抑えられる。

このアプローチは、幾何学的なコンダクタンスの議論ではなく、双対性と微積分に基づいている。著者らは、この証明フレームワークは HAR と CHAR で本質的に同一であり、主な違いはスペクトル・ギャップの境界における次元因子にあると述べている。

主要な貢献と結果
本論文は、単位球を含む凸体 $K$ に対する以下の理論的結果を提供する（$\pi$ は $K$ 上の一様分布とする）：

1. スペクトル・ギャップの境界:

   • Hit-and-Run の場合: $\lambda_{HR} \gtrsim \frac{1}{n^2 C_{PI}(\pi)}$。
   • Coordinate Hit-and-Run の場合: $\lambda_{CHAR} \gtrsim \frac{1}{n^3 C_{PI}(\pi)}$。
   • $C_{PI}(\pi) \lesssim \|\text{cov}_\pi\|_{op} \log n$ という関係を用いると、これらの境界は $\lambda_{HR} \gtrsim \frac{1}{n^2 \|\text{cov}_\pi\|_{op} \log n}$ となる。

2. 混合時間の改善:

   • 初期分布の $\chi^2$ ダイバージェンス $M$ から $\chi^2$ ダイバージェンス $\varepsilon$ を達成するための混合時間は：
     • HAR: $O(n^2 C_{PI} \log(M/\varepsilon))$。
     • CHAR: $O(n^3 C_{PI} \log(M/\varepsilon))$。
   • 準等方的な体（$\|\text{cov}_\pi\|_{op} \approx 1$）において、KLS 予想が進展していると仮定した場合（$C_{PI} \approx O(1)$）、HAR の複雑度は $O(n^2 \log n \log(M/\varepsilon))$ となる。これは、従来の $O(n^2 R^2 \log(M/\varepsilon))$ という境界を洗練させ、次元依存性を（$R^2 \sim n$ を通じて）立方オーダーからほぼ二次オーダーへと改善したものである。

3. テクニカル・レマ:

   • 有界凸領域について、$C_{BA} \leq 1 + 4 C_{IPI}$ であることを証明している。
   • $C_{IPI} \lesssim n^2 C_{PI} / r^2$ （ここで $r$ は内半径）であることを確立し、重み付きポアンカレ定数と重みなしポアンカレ定数の間の必要な接続を提供している。

意義
本論文は、Hit-and-Run の収束を、Ball walk に対してのみ確立されていた接続と同様に、ポアンカレ定数および KLS 定数に直接結びつけることで、10年来の未解決問題を解決したと主張している。

• 境界の洗練: HAR の既知の境界を、外半径 $R$ への依存性を排除して、より本質的な幾何学的特性であるポアンカレ定数へと洗練させた。
• 次元依存性: 等方的な体に対して、混合時間の次元依存性を立方オーダーからほぼ二次オーダー（$O(n^2 \log n)$）へと改善し、サンプリングにおける予想される最適レートに HAR の理論的性能を近づけた。
• 手法の転換: 双対性と Babuška–Aziz 定数に基づく新しい証明フレームワークを導入しており、これは他のマルコフ連鎖にも適用可能な、コンダクタンスに基づく解析に代わる手法を提供している。
• CHAR の解析: この手法は Coordinate Hit-and-Run にも成功的に拡張され、$O(n^3 C_{PI} \log(M/\varepsilon))$ という大幅に改善された混合時間境界をもたらした。これは漸近的にタイトであると予想されている。

著者らは、Ball walk が避けられない線形な温かさパラメータへの依存性を有するのに対し、Hit-and-Run は改善された等周境界の恩恵を受けつつ、初期距離に対する対数的な依存性を保持していると主張している。