True Self-Avoiding Walk for Accelerating Markov-Chain Monte Carlo Integration

技術要約：マルコフ連鎖モンテカルロ積分を加速するための真の自己回避歩行（True Self-Avoiding Walk）

問題提起
本論文は、マルコフ連鎖モンテカルロ（MCMC）法における経験的積分推定の有限時間における品質を取り扱う。有限の状態空間 $V$、既約マルコフ核 $P$、および定常分布 $\pi$ が与えられたとき、目標は軌跡 $(X_t)_{t \geq 0}$ の経験平均を用いて定常積分 $\pi(f) = \sum_{x \in V} \pi(x)f(x)$ を推定することである。

標準的なランダムウォークに基づくMCMC手法は、「局所的な過剰サンプリング（local oversampling）」に悩まされる。これは、軌跡が最近探索した領域を再訪してしまうことで、占有の不均衡の修正が遅れる現象である。その結果、経験平均の誤差は通常、ほとんど確実に $O(t^{-1/2})$ のオーダーでスケールする。近年の自己反発型ランダムウォーク（SRRW）に関する研究は漸近分散定数を改善しているものの、誤差のスケーリング自体は標準的な $O(t^{-1/2})$ レベルに留まっている。著者らは、サンプルサイズ $t$ に対する経験的積分誤差の依存性を、より鋭いものにするためのメカニズムを追求している。

手法
著者らは、使用頻度に応じて遷移確率にペナルティを課す**真の自己回避歩行（TSAW）**ダイナミクスを提案している。その手法は、以下の3つの明確な段階で構成される：

1. スターグラフ上でのウォームアップ： 著者らはまず、スターグラフ（ハブと $n$ 個のリーフが接続されたグラフ）上の簡略化されたモデルを分析する。**指数レース埋め込み（exponential-race embedding）**を用いることで、離散的なTSAWダイナミクスを連続時間出生過程へと写像する。これにより、カバレッジ時間の詳細な分析が可能となり、指数的な自己回避が、古典的なクーポンコレクター問題のオーダー $O(n \log n)$ から $O(n \log \log n)$ へと探索スケールを減少させることを示す。

2. 有限アルファベットの自己均衡モデル： ターゲット分布 $p$ を持つ有限アルファベット $[d]$ に対する局所的なサンプリング規則を構築する。時刻 $t$ における状態 $i$ への遷移確率は、ターゲットに対する「超過」または「不足」によってペナルティを課すソフトマックス関数を介して以下のように定義される：
   $$P(X_{t+1} = i \mid \mathcal{F}_t) \propto \exp\left(-\lambda \Delta_i(t)\right),$$
   ここで $\Delta_i(t) = L_t(i) - t p_i$ は、ターゲットカウントからの偏差である。
   リアプノフ関数 $V(t) = e^{\alpha M(t)}$ （ここで $M(t)$ は最大超過量）を用いることで、指数ドリフト不等式を証明する。これにより、最大超過量がほとんど確実に $O(\sqrt{\log t})$ の範囲内に抑えられることが確立される。また、一様な指数モーメント境界も示される。

3. 一般的な有限状態マルコフ核への拡張： この局所的なメカニニズムを、有限集合 $V$ 上の一般的な既約マルコフ核 $P$ へと拡張する。遷移ルールは、経験的な遷移カウント $N_t(i, j)$ と期待フロー $L_t(i)P_{ij}$ の間の不一致に基づいて、有向エッジ $(i, j)$ にペナルティを課す：
   $$P(X_{t+1} = j \mid X_t = i, \mathcal{F}_t) \propto P_{ij} \exp\left(-\lambda \epsilon_t(i, j)\right),$$
   ここで $\epsilon_t(i, j) = N_t(i, j) - L_t(i)P_{ij}$ である。
   分析には以下が含まれる：

   • 行ごとの簡約化（Row-wise Reduction）： 各状態 $i$ からの出発時刻におけるプロセスを分離することで、グローバルなダイナミクスを、局所的な有限アルファベット・プロセスの集合へと集約する。
   • グローバルな不一致境界： 局所的な指数モーメント境界を適用し、最大エッジ不一致 $M(t)$ に対するグローバルなテール境界を導出する。
   • ポアソン方程式： オペレータ $(I - P^\top)$ の群逆を用いて、エッジの不一致 $\epsilon_t$ を頂点の占有不一致 $L_t - t\pi$ に関連付ける。これにより、エッジの境界を占有カウントの境界へと変換する。

主な貢献と結果
本論文は、TSAWベースの歩行について以下のほとんど確実な（almost-sure）境界を確立している：

• 占有数および遷移カウント： すべての状態 $i$ およびエッジ $(i, j)$（ただし $P_{ij} > 0$）について、不一致は以下の通りである：
  $$L_t(i) - t\pi_i = O(\sqrt{\log t})$$
  $$N_t(i, j) - t\pi_i P_{ij} = O(\sqrt{\log t})$$
  （これらはすべてほとんど確実に成立する）。

• 積分推定誤差： 有界な関数 $f: V \to \mathbb{R}$ に対して、積分推定量の誤差は以下のように収束する：
  $$\left| \frac{1}{t} \sum_{s=0}^{t-1} f(X_s) - \sum_{i \in V} \pi_i f(i) \right| = O\left(\frac{\sqrt{\log t}}{t}\right)$$
  （ほとんど確実に成立）。

• 再帰性： これらのダイナミクスの下で、正の遷移確率を持つすべての状態およびすべての有向エッジは、ほとんど確実に無限回訪問されることを証明する。

意義と主張
本論文は、TSAWベースの推定器が、標準的なランダムウォークベースの手法や既存の自己反発型歩行推定器と比較して、サンプルサイズ $t$ に対して大幅に鋭い依存性を達成することを主張している。具体的には：

• 標準的な手法および SRRW（Doshi, Hu, and Eun [1] による分析）は、誤差のスケーリングが $O(t^{-1/2})$ である。
• 提案されたTSAW推定器は $O(\sqrt{\log t}/t)$ を達成しており、これは $O(\sqrt{t/\log t})$ の改善因子を表している。

著者らは、本研究を自己回避歩行、非線形マルコフ連鎖、およびMCMCの分散減少の交差点に位置づけている。彼らは、主要な新規性が、単なる漸近的な分散減少ではなく、経験的な占有および遷移誤差に対する**明示的な有限時間パス制御（finite-time pathwise control）**を提供した点にあると強調している。本論文は、この構成が、経験的推定を改善するための厳密なメカニズムを提供し、自己回避的な局所バランス規則から非マルコフ的なランダムウォークを構築するための一般的な設計パラダイムを提供するものであると結論付けている。