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

技术摘要：用于加速马尔可夫链蒙特卡洛积分的真自回避行走

问题陈述
本文探讨了马尔可夫链蒙特卡洛（MCMC）方法中经验积分估计在有限时间内的质量问题。给定有限状态空间 $V$、不可约马尔可夫核 $P$ 以及平稳分布 $\pi$，目标是使用轨迹 $(X_t)_{t \geq 0}$ 的经验平均值来估计平稳积分 $\pi(f) = \sum_{x \in V} \pi(x)f(x)$。

标准的基于随机游走的 MCMC 方法受限于“局部过度采样”问题，即轨迹会频繁回到近期探索过的区域，导致占据不平衡（occupation imbalances）的修正缓慢。因此，经验平均值的误差通常以 $O(t^{-1/2})$ 的速度几乎处处（almost surely）收敛。虽然近期关于自排斥随机行走（SRRW）的研究改进了渐近方差常数，但其误差缩放仍维持在标准的 $O(t^{-1/2})$ 水平。作者试图寻求一种机制，以实现经验积分误差对样本量 $t$ 更尖锐（sharper）的依赖关系。

方法论
作者提出了一种**真自回避行走（TSAW）**动力学，其转移概率根据经验过度使用情况进行惩罚。该方法论分为三个截然不同的阶段：

1. 星形图上的预热（Warm-up on the Star Graph）： 作者首先在一个简化的模型（一个中心连接 $n$ 个叶节点的星形图）上进行分析。通过采用指数竞赛嵌入（exponential-race embedding），他们将离散的 TSAW 动力学映射到连续时间出生过程。这使得对覆盖时间（cover time）的详细分析成为可能，证明了指数自回避将探索规模从经典的库仑收集者阶数 $O(n \log n)$ 降低到了 $O(n \log \log n)$。

2. 有限字母自平衡模型： 作者构建了一个针对目标分布为 $p$ 的有限字母集 $[d]$ 的局部采样规则。在时刻 $t$ 转移到状态 $i$ 的概率通过一个由“过剩”或“亏欠”进行惩罚的 Softmax 函数定义：
   $$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$ 是偏离目标计数的偏差。
   利用 Lyapunov 函数 $V(t) = e^{\alpha M(t)}$（其中 $M(t)$ 是最大过剩量），作者证明了一个指数漂移不等式（exponential drift inequality）。这确立了最大过剩量在几乎处处意义下保持在 $O(\sqrt{\log t})$ 范围内，并具有一致的指数矩界限。

3. 提升至一般有限状态马尔可夫核： 该局部机制被扩展到一般不可约马尔可夫核 $P$ 及有限集 $V$ 上。转移规则根据有向边 $(i, j)$ 的差异对路径进行惩罚，该差异定义为经验转移计数 $N_t(i, j)$ 与期望流量 $L_t(i)P_{ij}$ 之间的差距：
   $$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)$ 的全局尾界。
   • 泊松方程（Poisson Equation）： 利用算子 $(I - P^\top)$ 的群逆将边偏差 $\epsilon_t$ 与顶点占据偏差 $L_t - t\pi$ 联系起来。这实现了将边界转化为占据计数界限的转化。

核心贡献与结果
本文确立了基于 TSAW 行走的以下几乎处处的界限：

• 占据数与转移计数： 对于每个状态 $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)$$
  几乎处处成立。

• 复现性（Recurrence）： 作者证明，在此动力学下，每个具有正转移概率的状态和有向边几乎处处被无限次访问。

意义与主张
论文声称，基于 TSAW 的估计器实现了比标准随机游走及现有自排斥行走估计器更尖锐的样本量 $t$ 依赖关系。具体而言：

• 标准方法和 SRRW（如 Doshi, Hu, and Eun [1] 中所述）表现出 $O(t^{-1/2})$ 的误差缩放。
• 所提出的 TSAW 估计器实现了 $O(\sqrt{\log t}/t)$，代表了 $O(\sqrt{t/\log t})$ 倍的改进因子。

作者将其工作定位在自回避随机行走、非线性马尔可夫链和 MCMC 方差缩减的交汇点。他们强调，其主要创新在于提供了显式的有限时间路径控制（explicit finite-time pathwise control）的经验占据和转移误差，而非仅仅是渐近方差的缩减。论文总结道，这种构造为通过自回避局部平衡规则构建非马尔可夫随机行走提供了一种严谨的机制，并提供了一种通用的设计范式。