2025-11-16T12:28:12.323029

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

Hofstadler, Latuszynski, Roberts et al.
We consider adaptive increasingly rare Markov chain Monte Carlo (MCMC) algorithms, which are adaptive MCMC methods, where the adaptation concerning the "past'' happens less and less frequently over time. Under a contraction assumption with respect to a Wasserstein-like function we deduce upper bounds of the convergence rate of Monte Carlo sums taking a renormalisation factor into account that is "almost'' the one that appears in a law of the iterated logarithm. We demonstrate the applicability of our results by considering different settings, among which are those of simultaneous geometric and uniform ergodicity. All proofs are carried out on an augmented state space, including the classical non-augmented setting as a special case. In contrast to other adaptive MCMC limit theory, some technical assumptions, like diminishing adaptation, are not needed.
academic

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

基本信息

  • 论文ID: 2402.12122
  • 标题: Almost sure convergence rates of adaptive increasingly rare Markov chain Monte Carlo
  • 作者: Julian Hofstadler (University of Bath), Krzysztof Latuszyński (University of Warwick), Gareth O. Roberts (University of Warwick), Daniel Rudolf (University of Passau)
  • 分类: math.NA cs.NA math.PR math.ST stat.TH
  • 发表时间: October 14, 2025 (arXiv版本)
  • 论文链接: https://arxiv.org/abs/2402.12122

摘要

本文研究自适应渐稀Markov链Monte Carlo (AIR MCMC)算法，这是一类自适应MCMC方法，其中对"过去"的自适应随时间推移变得越来越稀少。在关于Wasserstein-like函数的收缩假设下，作者推导出Monte Carlo求和的收敛速度上界，该上界考虑了"几乎"出现在迭代对数律中的重正化因子。论文通过考虑同时几何遍历性和一致遍历性等不同设置来证明结果的适用性。所有证明都在增广状态空间上进行，包括经典非增广设置作为特例。与其他自适应MCMC极限理论相比，不需要一些技术假设，如递减自适应。

研究背景与动机

问题定义

在计算统计学中，一个普遍存在的挑战是近似期望值： ν(f)=∫Xf(x)ν(dx)\nu(f) = \int_X f(x)\nu(dx) 其中ν\nu是目标分布，f:X→Rf: X \to \mathbb{R}是感兴趣的可积函数。

研究动机

  1. 直接采样困难：当从ν\nu直接采样不可能或计算上不可行时（例如密度包含未知正规化常数），需要替代方法。
  2. 自适应MCMC的挑战：传统自适应MCMC方法通过考虑整个历史来更新单步转移机制，导致非Markov过程，使得数学分析复杂化。
  3. 技术假设的简化需求：现有自适应MCMC理论通常需要技术性假设（如递减自适应），限制了方法的适用性。

现有方法的局限性

  • 自适应MCMC的非Markov性质导致复杂的证明技术
  • 需要严格的技术条件才能保证收敛性
  • 缺乏关于重正化Monte Carlo求和收敛性的结果

核心贡献

  1. 提出AIR MCMC理论框架：在Wasserstein收缩假设下，为AIR算法建立了几乎必然收敛速度理论。
  2. 改进的收敛速度：获得了形如r(n)=n(log⁡n)1/2+εr(n) = \sqrt{n}(\log n)^{1/2+\varepsilon}或r(n)=n1/2+εr(n) = n^{1/2+\varepsilon}的收敛速度，接近迭代对数律的最优速度。
  3. 技术假设的简化：不需要递减自适应等传统技术假设，扩大了方法的适用范围。
  4. 增广状态空间分析：在增广状态空间上进行分析，包含经典非增广设置作为特例。
  5. 广泛的适用性：结果适用于同时几何遍历性和一致遍历性等多种设置。

方法详解

AIR MCMC算法定义

给定参数β>0\beta > 0，设置kj=⌈jβ⌉k_j = \lceil j^\beta \rceil，仅在特定时间点进行自适应： Tm=∑j=1mkjT_m = \sum_{j=1}^m k_j

关键观察：对于任何β>0\beta > 0，存在常数cβ,Cβc_\beta, C_\beta使得： cβm1+β≤Tm≤Cβm1+βc_\beta m^{1+\beta} \leq T_m \leq C_\beta m^{1+\beta}

这意味着自适应频率递减。

核心技术框架

1. Wasserstein-like函数

对于距离类函数d:Y×Y→R+d: Y \times Y \to \mathbb{R}_+，定义： W(μ1,μ2):=inf⁡ξ∈C(μ1,μ2)∫Y2d(x,y)ξ(dx,dy)W(\mu_1, \mu_2) := \inf_{\xi \in C(\mu_1,\mu_2)} \int_{Y^2} d(x,y)\xi(dx,dy)

2. 主要假设（Assumption 3.1）

对每个γ∈I\gamma \in I，假设：

  • πγ\pi_\gamma是PγP_\gamma的不变分布
  • τ(Pγ)≤M\tau(P_\gamma) \leq M且τ(Pγk0)≤τ\tau(P_\gamma^{k_0}) \leq \tau 其中M∈[1,∞)M \in [1,\infty)，τ∈[0,1)\tau \in [0,1)，k0∈Nk_0 \in \mathbb{N}独立于γ\gamma。

3. Poisson方程求解

对于函数h:Y→Rh: Y \to \mathbb{R}和γ∈I\gamma \in I，Poisson方程的解为： uγ(y)=∑ℓ=0∞(Pγℓf(y)−πγ(f))u_\gamma(y) = \sum_{\ell=0}^{\infty}(P_\gamma^\ell f(y) - \pi_\gamma(f))

鞅近似技术

利用Poisson方程分解Monte Carlo求和： ∑j=1n(h(Yj)−πΓj−1(h))=Mn+Rm+有界项\sum_{j=1}^n (h(Y_j) - \pi_{\Gamma_{j-1}}(h)) = M_n + R_m + \text{有界项}

其中：

  • MnM_n：鞅项
  • RmR_m：余项，对AIR算法大幅简化

主要理论结果

定理3.5（β≥1\beta \geq 1情况）

在有界偏心率假设下，对任意ε>0\varepsilon > 0： lim⁡n→∞1n(log⁡n)1/2+ε∑j=1n(f(Xj)−ν(f))=0a.s.\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.}

定理3.6（β∈(0,1)\beta \in (0,1)情况）

对ε>11+β−12\varepsilon > \frac{1}{1+\beta} - \frac{1}{2}： lim⁡n→∞1n1/2+ε∑j=1n(f(Xj)−ν(f))=0a.s.\lim_{n \to \infty} \frac{1}{n^{1/2+\varepsilon}} \sum_{j=1}^n (f(X_j) - \nu(f)) = 0 \quad \text{a.s.}

定理3.11（Lyapunov条件）

在Lyapunov函数存在性假设下，对ε>max⁡{0,11+β+1p−12}\varepsilon > \max\{0, \frac{1}{1+\beta} + \frac{1}{p} - \frac{1}{2}\}： lim⁡n→∞1n1/2+ε∑j=1n(f(Xj)−ν(f))=0a.s.\lim_{n \to \infty} \frac{1}{n^{1/2+\varepsilon}} \sum_{j=1}^n (f(X_j) - \nu(f)) = 0 \quad \text{a.s.}

应用实例

1. 一致遍历性设置

使用平凡度量d(y1,y2)=1{y1≠y2}d(y_1, y_2) = \mathbf{1}_{\{y_1 \neq y_2\}}，此时WW对应全变差距离。

推论4.5：对有界函数ff，在β≥1\beta \geq 1和ε>0\varepsilon > 0下： ∣1n∑j=1n(f(Xj(ω))−ν(f))∣≤(log⁡n)1/2+εnC(ω)\left|\frac{1}{n}\sum_{j=1}^n (f(X_j(\omega)) - \nu(f))\right| \leq \frac{(\log n)^{1/2+\varepsilon}}{\sqrt{n}} C(\omega)

2. 几何遍历性设置

考虑漂移-小集条件（Assumption 4.7），使用加权度量： dq(y1,y2)=1{y1≠y2}(Vq(y1)+Vq(y2))d_q(y_1, y_2) = \mathbf{1}_{\{y_1 \neq y_2\}}(V^q(y_1) + V^q(y_2))

3. 弱Harris遍历性

使用距离类函数： d~q(y1,y2)=d(y1,y2)(1+Vq(y1)+Vq(y2))\tilde{d}_q(y_1, y_2) = \sqrt{d(y_1, y_2)(1 + V^q(y_1) + V^q(y_2))}

技术创新点

1. 简化的余项控制

AIR算法的关键优势是余项RmR_m中的大部分困难项相消，使得： ∣Rm∣≤n1/(1+β)⋅常数|R_m| \leq n^{1/(1+\beta)} \cdot \text{常数}

2. 无需递减自适应

与传统方法不同，不需要∥Γn−Γn−1∥→0\|\Gamma_n - \Gamma_{n-1}\| \to 0的假设。

3. 增广状态空间处理

通过Y=X×ΦY = X \times \Phi的设置，统一处理多模态分布等复杂情况。

实验验证

论文主要为理论分析，通过以下方式验证结果：

1. 具体算法实例

  • 自适应随机游走Metropolis算法
  • 自适应立体投影MCMC算法
  • preconditioned Crank-Nicolson (pCN)算法

2. 数值对比参考

引用CLR18的数值实验，显示AIR算法在β∈[1,2]\beta \in [1,2]时性能与纯自适应方法相当。

相关工作

经典自适应MCMC理论

  • 大数定律：HST01, AR05, AM06, RR07, SV10, FMP11, PHL20
  • 中心极限定理：AM06, SV10
  • 收敛到正确目标测度：RR07, FMP11

定量遍历性结果

  • AA07, AW15：显示∥P(Xn∈⋅)−ν∥tv≤C/n\|P(X_n \in \cdot) - \nu\|_{tv} \leq C/n
  • AW15, CLR18：均方误差界，显示1/n1/n阶收敛速度

本文贡献的独特性

  1. 路径收敛界：与现有的期望误差界不同，提供几乎必然的路径收敛
  2. Wasserstein收缩设置：扩展了传统的一致/几何遍历性框架
  3. 接近最优速度：收敛速度接近迭代对数律的理论最优值

结论与讨论

主要结论

  1. AIR MCMC算法在Wasserstein收缩假设下具有良好的几乎必然收敛性质
  2. 收敛速度接近理论最优，形如n(log⁡n)1/2+ε\sqrt{n}(\log n)^{1/2+\varepsilon}
  3. 技术假设相比传统方法显著简化

局限性

  1. 一致性要求：Assumption 3.1要求所有界关于γ\gamma一致，较为限制性
  2. 小β\beta政权：当β∈(0,1)\beta \in (0,1)时收敛速度变差，需要额外假设改进
  3. 纯自适应算法：对β=0\beta = 0的纯自适应情况仍需进一步研究

未来方向

  1. 弱化一致性假设：在随机逼近型算法框架下可能放松Assumption 3.1
  2. 扩展到纯自适应：利用SV10的技术处理β=0\beta = 0情况
  3. 改进小β\beta政权：开发无需额外假设的技术处理β∈(0,1)\beta \in (0,1)

深度评价

优点

  1. 理论深度：在Wasserstein收缩框架下建立了完整的AIR MCMC理论
  2. 技术创新：巧妙利用AIR结构简化鞅近似中的余项控制
  3. 广泛适用性：涵盖一致、几何、弱Harris遍历性等多种设置
  4. 实用价值：提供路径收敛界，对单次模拟有实际指导意义

不足

  1. 假设限制性：一致性假设在实际应用中可能难以验证
  2. 小β\beta处理：需要额外的Lipschitz和衰减自适应条件
  3. 数值验证有限：主要为理论分析，缺乏充分的数值实验

影响力

  1. 理论贡献：为AIR MCMC提供了坚实的理论基础
  2. 方法学价值：Wasserstein收缩方法可能启发其他算法分析
  3. 实用前景：路径收敛界对MCMC诊断和停止准则有重要意义

适用场景

  1. 高维统计推断：适用于复杂后验分布的采样
  2. 多模态分布：通过增广状态空间处理多模态问题
  3. 计算资源受限：AIR算法减少自适应频率，节省计算成本

参考文献

论文包含34篇重要参考文献，涵盖了自适应MCMC理论的主要发展，特别是：