Almost sure convergence rates of adaptive increasingly rare Markov chain Monte Carlo

这是一份关于论文《Almost sure convergence rates of adaptive increasingly rare Markov chain Monte Carlo》（自适应日益稀少的马尔可夫链蒙特卡洛算法的几乎必然收敛速率）的详细技术总结。

1. 研究背景与问题 (Problem)

核心挑战：
在计算统计学中，近似期望值 $\nu(f) = \int f(x)\nu(dx)$ 是一个普遍问题。当无法直接从目标分布 $\nu$ 采样（例如由于归一化常数未知）时，马尔可夫链蒙特卡洛（MCMC）方法是标准工具。

自适应 MCMC 的困境：
自适应 MCMC 通过利用历史数据来更新转移机制，通常能改善收敛性能。然而，这种机制引入了非马尔可夫性，使得理论分析变得极其复杂。传统的自适应 MCMC 理论通常需要严格的假设（如“渐近适应”diminishing adaptation）来保证收敛性，且关于几乎必然收敛速率（almost sure convergence rates）和重正化蒙特卡洛和的极限理论（如重对数律）在自适应设置下尚不完善。

本文目标：
研究**自适应日益稀少（Adaptively Increasingly Rare, AIR）**MCMC 算法的收敛性质。AIR 算法的特点是适应（更新参数）发生的频率随时间推移而降低。本文旨在证明在这些算法下，蒙特卡洛和的收敛速率，并给出几乎必然收敛的界。

2. 方法论 (Methodology)

本文采用了一种结合增广状态空间、泊松方程和鞅逼近的技术路线。

• 增广状态空间 (Augmented State Space)：
  为了处理多模态目标分布等复杂情况，作者将状态空间扩展为 $Y = X \times \Phi$，其中 $\Phi$ 是辅助变量空间。这允许将经典的非增广设置作为特例包含在内，并有助于解决多模态性等问题。

• AIR 机制定义：
  适应参数 $\Gamma_n$ 仅在特定时间点 $T_m$ 更新，而非每一步都更新。更新间隔 $k_j$ 随 $j$ 增长（$k_j = \lceil j^\beta \rceil$），导致适应频率随时间降低。

• 泊松方程与鞅分解 (Poisson's Equation & Martingale Decomposition)：
  利用泊松方程 $u_\gamma(y) - P_\gamma u_\gamma(y) = h(y) - \pi_\gamma(h)$ 将蒙特卡洛和分解为三部分：

  1. 鞅部分 ($M_n$)： 由泊松方程解生成的鞅差序列。
  2. 余项部分 ($R_m$)： 由于适应参数在 $T_m$ 时刻跳跃而产生的误差项。
  3. 边界项： 初始和终止项。

  在 AIR 设置下，由于适应频率降低，余项 $R_m$ 中的许多项相互抵消或变得稀疏，从而简化了控制难度。

• Wasserstein 收缩假设 (Wasserstein Contraction Assumption)：
  这是本文的核心假设。作者不依赖传统的总变差距离（Total Variation）或几何遍历性，而是假设转移核 $P_\gamma$ 关于某个类 Wasserstein 函数 $W$ 具有收缩性：
  $$\tau(P_\gamma) \le M, \quad \tau(P_\gamma^{k_0}) \le \tau < 1$$
  其中 $\tau$ 是收缩系数。这一假设比传统的均匀或几何遍历性更广泛，涵盖了更多类型的核。

• 几乎必然收敛证明：
  利用鞅大数定律（针对有界增量或 $L^2$ 有界增量的鞅）和 Borel-Cantelli 引理，分别控制鞅部分和余项部分，证明归一化后的和几乎必然趋于零。

3. 主要贡献与结果 (Key Contributions & Results)

3.1 理论突破

• 无需“渐近适应”假设： 与传统的自适应 MCMC 极限理论不同，本文证明在 AIR 框架下，不需要“渐近适应”（diminishing adaptation）这一技术性假设即可证明几乎必然收敛。
• Wasserstein 收缩框架下的极限理论： 首次在水星斯坦（Wasserstein）收缩假设下，为自适应 MCMC 建立了重正化蒙特卡洛和的几乎必然收敛速率。
• 接近重对数律的速率： 证明了收敛速率 $r(n)$ 可以取为 $\sqrt{n}(\log n)^{1/2+\varepsilon}$ 或 $n^{1/2+\varepsilon}$。当 $\varepsilon$ 很小时，这非常接近独立同分布（i.i.d.）情况下的重对数律（Law of the Iterated Logarithm），这是理论上无法进一步改进的界限。

3.2 具体定理与速率

根据适应频率参数 $\beta$ 的不同，得到了不同的收敛速率：

1. 均匀有界偏心率 (Uniformly Bounded Eccentricity) 情形：

   • 若 $\beta \ge 1$（适应频率较低）：
     $$\lim_{n \to \infty} \frac{1}{\sqrt{n}(\log n)^{1/2+\varepsilon}} \sum_{j=1}^n (f(X_j) - \nu(f)) = 0 \quad \text{a.s.}$$
   • 若 $\beta \in (0, 1)$（适应频率较高）：
     速率稍慢，为 $n^{1/2+\varepsilon}$，其中 $\varepsilon$ 需满足 $\varepsilon > \frac{1}{1+\beta} - \frac{1}{2}$。
   • 改进： 若满足额外的“减弱适应”（waning adaptation）条件（假设 3.14），即使 $\beta \in (0, 1)$ 也能达到 $\sqrt{n}(\log n)^{1/2+\varepsilon}$ 的速率。

2. Lyapunov 函数条件情形：
   对于更一般的非有界状态空间，引入 Lyapunov 函数 $V$ 和增长条件，证明了类似的收敛速率，但 $\varepsilon$ 的下界取决于 $V$ 的阶数 $p$。

3.3 应用实例

文章将理论应用于三种具体场景：

1. 均匀遍历性 (Uniform Ergodicity)： 包括有界状态空间和自适应立体投影 MCMC（Adaptive Stereographic MCMC）。
2. 几何遍历性 (Geometric Ergodicity)： 包括基于协方差近似的自适应随机游走 Metropolis 算法。
3. 弱 Harris 遍历性 (Weak Harris Ergodicity)： 基于 [HMS11] 的弱收缩条件，适用于无限维空间（如 pCN 算法）。

4. 意义与影响 (Significance)

• 理论深度： 填补了自适应 MCMC 在“几乎必然收敛速率”和“重对数律”方面的理论空白。以往的研究多集中在均方误差（MSE）或分布收敛，而本文提供了路径上的（path-wise）收敛保证。
• 实用价值： 给出的收敛界（如公式 3）具有实际指导意义。即使在只运行一次模拟（single run）的情况下，用户也能根据 $C(\omega)$ 和 $r(n)$ 估算误差范围，这对于评估算法在单次运行中的可靠性至关重要。
• 算法设计指导： 证明了 AIR 策略（减少适应频率）不仅在数值上有效（节省计算资源），在理论上也能简化分析并放宽假设条件（如无需渐近适应）。
• 通用性： 通过引入类 Wasserstein 收缩假设，该方法统一了多种遍历性场景（均匀、几何、弱 Harris），为分析复杂 MCMC 算法提供了更强大的工具。

总结

该论文通过引入增广状态空间和基于泊松方程的鞅逼近技术，在较弱的收缩假设下，严格证明了自适应日益稀少（AIR）MCMC 算法的几乎必然收敛速率。其结果不仅去除了传统理论中繁琐的假设，还给出了接近最优（重对数律）的收敛界，为自适应 MCMC 的理论分析和实际应用提供了重要的新视角。