MCMC using bouncy Hamiltonian dynamics: A unifying framework for Hamiltonian Monte Carlo and piecewise deterministic Markov process samplers¶
作者: Andrew Chin, Akihiko Nishimura
来源: Journal of Computational and Graphical Statistics
主题: 统计计算 / 算法
相关性: 5/10
机构绿灯: Johns Hopkins University(US News 前 50,免分进入精读)
链接: 期刊页 · arXiv
一、领域脉络与小综述¶
-
这个方向是什么:本文属于统计计算(statistical computing)中的马尔可夫链蒙特卡洛(MCMC)方法设计。其根本问题是:在高维贝叶斯推断中,如何设计既具有高采样效率(低自相关、快速混合)又易于实现和调参的采样算法。当前该领域的两大主流范式是:(1) 基于哈密顿动力学的 HMC(利用梯度信息进行全局探索);(2) 基于分段确定性马尔可夫过程(PDMP)的非可逆采样器(如 zig-zag、bouncy particle sampler,通过事件驱动实现非可逆性)。本文试图在理论上统一这两大范式。
-
发展脉络(history):
- 奠基工作:Metropolis et al. (1953) 提出 Metropolis 算法,为所有 MCMC 方法奠定基础;Duane et al. (1987) 提出 HMC,引入哈密顿动力学作为提议机制,利用梯度信息抑制随机游走行为。Neal et al. (2011) 的综述确立了 HMC 在现代贝叶斯计算中的核心地位。
- PDMP 的兴起:Davis (1984) 建立了 PDMP 的一般理论框架;Fearnhead et al. (2018) 系统阐述了 PDMP 在 MCMC 中的应用;Bouchard-Côté et al. (2018) 提出 bouncy particle sampler (BPS),Vanetti et al. (2017) 提出 zig-zag sampler 并给出一般化的 Hamiltonian PD-MCMC 框架。这些工作的核心贡献是引入非可逆性,打破细致平衡条件,从而抑制随机游走行为。
- HMC 与 PDMP 的早期联系:Nishimura et al. (2024) 发现 zig-zag sampler 与使用拉普拉斯动量的 HMC 之间存在联系,这是两大范式之间最早的桥梁。Deligiannidis et al. (2021) 在高维极限下发现 BPS 的某个坐标过程收敛到 Randomized HMC,但仅涉及单变量边际。
-
本文的位置:作者将上述联系推广为一般性框架——任何时间可逆、保体积的确定性动力学都可作为有效的 Metropolis 提议,而 PDMP 的特征性速度变化(bounce)提供了接受-拒绝的替代方案。这一框架不仅统一了 HMC 与 PDMP,还通过"惯性变量"的引入构造了一类全新的确定性动力学(bouncy Hamiltonian dynamics),其刷新极限恢复 PDMP,而无需刷新时则退化为经典 HMC。
-
子线索聚类:
- HMC 及其变体(Duane et al. 1987; Neal et al. 2011; Girolami & Calderhead 2011; Blanes et al. 2014; Bou-Rabee & Sanz-Serna 2017, 2018):关注如何选择动能函数、数值积分器、步长自适应,以提高 HMC 的采样效率。
- PDMP 采样器(Davis 1984; Fearnhead et al. 2018; Bouchard-Côté et al. 2018; Bierkens et al. 2019, 2020; Vanetti et al. 2017):关注事件驱动模拟、事件率设计、非可逆性带来的效率增益,以及在高维和受限域上的应用。
-
HMC 与 PDMP 的交叉(Nishimura et al. 2024; Deligiannidis et al. 2021; 本文):关注两大范式之间的理论联系、统一框架、以及如何互相借鉴以构造新算法。
-
这个方向在追问的核心问题:
- 统一性:HMC 与 PDMP 这两大范式之间是否存在一个统一的数学框架?它们各自的优劣能否在统一框架下得到解释?
- 效率增益的来源:PDMP 的非可逆性带来的效率增益究竟来自何处?能否在确定性动力学中复现这种增益?
- 可扩展性:如何设计在高维(数万参数)问题上仍保持高效且易于调参的采样器?PDMP 的事件率计算和 HMC 的数值积分在高维下各有何瓶颈?
-
理论保证:如何刻画这些采样器的收敛速度、几何遍历性、以及在高维极限下的行为?
-
⚠️ 作者的 framing(这是作者的说法):作者将缺口 frame 成"HMC 与 PDMP 之间缺乏一个统一的确定性动力学框架"。他们声称,已有的联系(Nishimura et al. 2024 的 zig-zag 与拉普拉斯动量 HMC;Deligiannidis et al. 2021 的 BPS 高维极限)只是特例,而他们的 bouncy Hamiltonian dynamics 是"第一个"同时具备以下性质的框架:(1) 确定性、时间可逆、保体积;(2) 产生不连续轨迹(bounce);(3) 在刷新极限下收敛到 PDMP;(4) 无需刷新时退化为经典 HMC。作者淡化了 Deligiannidis et al. (2021) 的工作——指出其仅涉及单变量边际收敛,而他们的收敛是 Skorokhod 拓扑下的全路径强收敛。值得研究者去查的问题:作者在引言中未提及的竞争路线包括:(a) 基于"事件驱动 HMC"的其他尝试(如利用反射或折射的 HMC 变体);(b) 非可逆 HMC 的构造(如利用涡旋或流场的非可逆提议);(c) 随机化 HMC(Randomized HMC)与 PDMP 的联系。这些路线是否已被其他作者探索过?作者为何未引用?
-
张力:未见明显对立引用。但存在一个微妙的张力:Deligiannidis et al. (2021) 发现 BPS 在高维极限下收敛到 Randomized HMC(一个随机过程),而本文发现 BPS 是 bouncy Hamiltonian dynamics 的刷新极限(一个确定性过程)。这两个极限过程看似矛盾——一个随机、一个确定——但实际上是不同极限(高维极限 vs. 刷新频率极限)下的不同结果。这一张力值得研究者注意:两种极限的交换顺序是否会产生不同的行为?
二、最核心、最简单的例子 / 数学问题¶
第一步:符号、模型、可观测数据
- 目标分布:\(\pi(x)\),定义在 \(\mathbb{R}^d\) 上,可能仅知其未归一化形式。MCMC 的目标是构造以 \(\pi(x)\) 为平稳分布的马尔可夫链。
- 增广目标:\(\pi(x, v, \iota) = \pi(x) \pi(v) \pi(\iota)\),其中:
- \(x \in \mathbb{R}^d\):位置变量(目标参数),是我们要采样的对象。
- \(v \in \mathbb{R}^d\):速度变量(辅助变量),在 HMC 中对应动量,在 PDMP 中对应速度。其边际分布 \(\pi(v)\) 通常取为标准高斯 \(N(0, I)\)。
- \(\iota \geq 0\):惯性变量(本文新引入的辅助变量),其边际分布 \(\pi(\iota)\) 取为指数分布 \(\text{Exp}(1)\)。\(\iota\) 的期望值控制两次 bounce 之间的平均时间。
- 势能:\(U_{\text{tar}}(x) = -\log \pi(x)\)(目标势能),\(U_{\text{sur}}(x)\)(替代势能,用于构造确定性动力学,可能不等于 \(U_{\text{tar}}\))。\(U_{\text{dif}}(x) = U_{\text{tar}}(x) - U_{\text{sur}}(x)\) 为势能差。
- 确定性动力学:由 Hamilton 方程 \(\frac{dx}{dt} = \frac{\partial K}{\partial v}\),\(\frac{dv}{dt} = -\frac{\partial U_{\text{sur}}}{\partial x}\) 定义,其中 \(K(v) = \|v\|^2/2\) 为动能。该动力学保体积(Liouville 定理)、时间可逆、保能量 \(U_{\text{sur}}(x) + K(v)\)。
- 可观测数据:在 MCMC 应用中,我们只能观测到算法产生的样本序列 \(\{x^{(i)}\}_{i=1}^n\)。算法的内部状态(\(v, \iota\))不可直接观测,但影响样本的统计性质(自相关、混合速度)。
第二步:最小内核
核心问题:如何构造一个确定性动力学,使其轨迹既具有 HMC 的全局探索能力,又具有 PDMP 的非可逆性(抑制随机游走)?
最简特例:\(d=1\),目标分布 \(\pi(x) \propto e^{-U_{\text{tar}}(x)}\),替代势能取 \(U_{\text{sur}}(x) = 0\)(即自由粒子动力学,\(x_t = x_0 + tv_0\),\(v_t = v_0\))。
标准 HMC 的做法:从 \((x_0, v_0)\) 出发,沿自由粒子轨迹运行时间 \(T\),到达 \((x_T, v_T) = (x_0 + Tv_0, v_0)\),然后以概率 \(\min(1, e^{-[U_{\text{tar}}(x_T) - U_{\text{tar}}(x_0)]})\) 接受。若拒绝,则回到 \((x_0, -v_0)\)。这个过程是时间可逆的,但轨迹是连续的、光滑的。
标准 BPS 的做法:从 \((x_0, v_0)\) 出发,沿自由粒子轨迹运行,但速度 \(v\) 在随机时间发生翻转(bounce)。bounce 事件发生的速率是 \(\lambda(t) = [v_t \nabla U_{\text{tar}}(x_t)]_+\)(即势能沿轨迹上升的速率)。当 bounce 发生时,\(v \leftarrow v - 2\frac{v \cdot \nabla U_{\text{tar}}(x)}{\|\nabla U_{\text{tar}}(x)\|^2}\nabla U_{\text{tar}}(x)\)(即相对于 \(\nabla U_{\text{tar}}\) 的法线反射)。这个过程是非可逆的(速度方向倾向于指向势能下降的方向),但轨迹是不连续的(速度在 bounce 时刻发生跳变)。
本文的 bouncy Hamiltonian dynamics 的做法:引入惯性变量 \(\iota\),其演化方程为
为什么这个例子能说明核心思想:在 \(U_{\text{sur}} = 0\) 的特例下,bounce 时间由 \(\iota_0 = U_{\text{dif}}(x_t) - U_{\text{dif}}(x_0) = U_{\text{tar}}(x_t) - U_{\text{tar}}(x_0)\) 决定。即当势能上升量等于初始惯性时发生 bounce。这与 BPS 的随机 bounce 不同——bounce 时间是确定性的(由初始条件决定),但通过随机刷新 \(\iota\)(每次 bounce 后重置为新的指数随机变量)引入随机性。关键洞察:bounce 事件等价于"当势能上升超过阈值时反弹",这既保证了轨迹不进入低概率区域(高势能区域),又通过确定性反射保持了时间可逆性。当 \(\iota\) 的刷新频率趋于无穷时,bounce 时间趋于随机(Poisson 过程),恢复 BPS;当 \(\iota\) 永不刷新时,轨迹退化为经典 HMC 的提议(但带有 bounce 修正)。
为什么这个例子是"最小内核":它剥离了所有技术细节(一般替代势能、多维、数值积分),只保留了核心机制——惯性变量作为"能量预算",耗尽时触发反射。理解了这一点,就能理解本文的所有推广:一般替代势能只是改变了轨迹的形状,多维只是将反射推广到超平面,数值积分只是近似实现。
三、这篇论文做了什么¶
三句话: 1. 研究了什么问题:如何构造一类新的确定性动力学(bouncy Hamiltonian dynamics),它既能作为 HMC 的提议机制(时间可逆、保体积),又能通过惯性耗尽触发反射产生类似 PDMP 的不连续轨迹,从而在理论上统一 HMC 与 PDMP 两大采样范式。 2. 核心工具/方法:引入惯性变量 \(\iota\) 作为"能量预算",通过 \(\iota\) 的耗尽触发确定性反射;利用时间可逆、保体积的动力学性质构造 Metropolis 提议;通过周期性刷新 \(\iota\) 建立与 PDMP 的联系,并证明刷新极限下的强收敛性。 3. 主要结论:(i) 建立了 bouncy Hamiltonian dynamics 的一般框架,证明其满足时间可逆、保体积、能量守恒(增广能量)等性质,因此可作为有效的 Metropolis 提议;(ii) 证明了在惯性刷新频率趋于无穷时,bouncy Hamiltonian dynamics 强收敛到对应的 PDMP(定理 3.2/3.3);(iii) 提出了 Hamiltonian bouncy particle sampler (HBPS),在理论上证明其渐近效率优于随机游走 Metropolis(定理 4.1),并在两个真实数据应用(22,174 维稀疏逻辑回归和 11,235 维系统发育 probit 模型)中展示了优于 BPS 的实用性能。
关键设定与假设:
- 设定:目标分布 \(\pi(x)\) 定义在 \(\mathbb{R}^d\) 上,\(U_{\text{tar}}(x) = -\log \pi(x)\) 二次连续可微。选择替代势能 \(U_{\text{sur}}(x)\) 构造确定性动力学,\(U_{\text{dif}} = U_{\text{tar}} - U_{\text{sur}}\) 为势能差。增广目标为 \(\pi(x, v, \iota) = \pi(x) \cdot N(v; 0, I) \cdot \text{Exp}(\iota; 1)\)。
- 假设:
- \(U_{\text{sur}}\) 二次连续可微,且 \(\limsup_{\|x\| \to \infty} \|\nabla U_{\text{sur}}(x)\|/\|x\| < \infty\)(控制轨迹在尾部的行为,保证不爆炸)。
- 排除退化情形:\(\nabla U_{\text{dif}}(x) = 0\) 且 \(\iota = 0\) 同时发生的集合是低维流形(定理 3.1 的技术假设,保证 bounce 规则良定义)。
- 目标分布 \(\pi(x)\) 的尾部行为受控(对数凹或类似条件),保证几何遍历性。
- 相比已有工作的变化:
- 相比 HMC:允许替代势能 \(U_{\text{sur}} \neq U_{\text{tar}}\),通过 bounce 修正势能差,而非依赖接受-拒绝。这放宽了 HMC 对精确动力学的要求。
- 相比 PDMP:bounce 时间是确定性的(由惯性耗尽决定),而非随机的(Poisson 过程)。这使动力学具有时间可逆性,从而可作为 Metropolis 提议。
- 相比 Nishimura et al. (2024):将 zig-zag 特例推广到一般替代势能,并建立了强收敛(而非仅弱收敛或边际收敛)。
主要结果:
- 定理 3.1(框架的良定义性):在假设条件下,bouncy Hamiltonian dynamics 在 \(\mathbb{R}^{2d+1}\) 上良定义(除零测集外),且满足:(i) 时间可逆;(ii) 保体积;(iii) 保增广能量 \(U_{\text{tar}}(x) + K(v) + \iota\)。这三个性质保证了该动力学可作为有效的 Metropolis 提议(类似于 HMC 的证明思路)。
- 定理 3.2/3.3(与 PDMP 的联系):在惯性刷新频率趋于无穷时,bouncy Hamiltonian dynamics 的位置-速度分量在 Skorokhod 拓扑下弱收敛(定理 3.2)且强收敛(定理 3.3)到对应的 PDMP。直觉:刷新频率越高,惯性耗尽的时间越接近指数分布(由刷新过程的极值理论),从而 bounce 时间趋于 Poisson 过程。
- 定理 4.1(HBPS 的效率优势):在对数凹目标上,HBPS 的渐近方差严格小于随机游走 Metropolis。证明思路:利用 Peskun-Tierney 排序(Peskun 1973; Tierney 1998),构造 HBPS 与随机游走 Metropolis 的耦合,使得 HBPS 的转移核在非对角元上逐点占优。关键条件:HBPS 的旅行时间等于随机游走的提议标准差。
证明路线与技术技巧:
- 定理 3.1 的证明路线:
- 良定义性:排除零测集后,证明轨迹在任意有限时间内不会遇到退化情形(\(\nabla U_{\text{dif}} = 0\) 且 \(\iota = 0\))。这需要用到 Sard 定理或类似的光滑映射性质。
- 时间可逆性:构造时间反转映射 \((x, v, \iota) \mapsto (x, -v, \iota)\),证明该映射与动力学流可交换。关键在于 bounce 规则(反射)在时间反转下不变。
- 保体积性:直接计算动力学流的 Jacobian。在两次 bounce 之间,动力学是 Hamilton 流,保体积;在 bounce 时刻,反射映射的 Jacobian 行列式为 \(-1\)(绝对值 1)。技术细节:由于 bounce 时刻由 \(\iota\) 的零交叉决定,需要证明该交叉是横截的(非退化),从而反射映射是光滑的。
- 能量守恒:直接计算 \(\frac{d}{dt}[U_{\text{tar}}(x_t) + K(v_t) + \iota_t]\),利用 Hamilton 方程和 \(\iota\) 的演化方程,得到 0。
- 定理 3.3 的证明路线:
- 耦合构造:将 bouncy Hamiltonian dynamics 和 PDMP 定义在同一个概率空间上,共享初始条件和随机数(即刷新时刻的指数变量)。
- 事件时间比较:在每次刷新间隔内,bouncy dynamics 的 bounce 时间与 PDMP 的 bounce 时间之差为 \(O(\Delta t^2)\)(由 \(\iota\) 的线性演化与指数分布的差异决定)。
- 误差累积:在 \([0, T]\) 内,刷新次数为 \(O(1/\Delta t)\),每次刷新引入 \(O(\Delta t^2)\) 的误差,总误差为 \(O(\Delta t)\)。因此,当 \(\Delta t \to 0\) 时,两条轨迹在 Skorokhod 度量下收敛。
- 技术技巧:Skorokhod 拓扑的选择是关键——由于 bounce 时刻的微小偏移,通常的均匀度量不适用,而 Skorokhod 度量允许时间轴的微小变形。
- 定理 4.1 的证明路线:
- Peskun-Tierney 排序:构造 HBPS 的转移核 \(Q_{\text{HBPS}}\) 和随机游走 Metropolis 的转移核 \(Q_{\text{RW}}\),证明对任意 \(x \neq x^*\),\(Q_{\text{HBPS}}(x \to x^*) \geq Q_{\text{RW}}(x \to x^*)\)。
- 耦合论证:给定相同的随机数 \((v, \iota)\),HBPS 的轨迹长度 \(\sigma\)(旅行时间)等于随机游走的提议标准差。HBPS 的接受概率为 1(因为 bounce 保证了能量守恒),而随机游走的接受概率 \(\leq 1\)。因此,HBPS 的提议分布随机占优于随机游走的提议分布。
- 技术技巧:利用对数凹假设保证 HBPS 的轨迹不会"卡住"(即 bounce 次数有限),从而转移核良定义。
真实例子与应用:
- 例子 1:稀疏逻辑回归(22,174 维)。数据来自一项比较达比加群酯和华法林两种抗凝药物的观察性研究,包含 72,489 名患者和 22,174 个协变量。模型使用桥接先验(bridge prior)进行贝叶斯稀疏回归。在 Gibbs 采样框架中,条件后验 \(\beta | \cdot\) 是对数凹的高维分布。HBPS 被用于更新 \(\beta\)。结果:HBPS 在最小 ESS/时间上比 BPS 快 4 倍,比 Pólya-Gamma 增强采样器快 11 倍。关键点:HBPS 无需调参(除了旅行时间),而 BPS 需要调刷新率。
- 例子 2:系统发育 probit 模型(11,235 维)。数据来自 HIV 病毒的 535 个样本和 21 个二元性状。模型使用系统发育布朗扩散作为潜变量先验。条件后验 \(x | \Gamma, T, y\) 是截断高斯分布。HBPS 被用于更新潜变量 \(x\)。结果:HBPS 在相关性参数上与 BPS 相当,但在偏相关参数上快 2.8 倍(当使用算子分裂联合更新 \(x\) 和 \(\Gamma\) 时)。关键点:HBPS 的确定性动力学允许算子分裂,而 BPS 的随机 bounce 使得分裂方案难以实现。
🔎 结论是否比证明窄:
- 定理 4.1 的证明仅针对对数凹目标和高斯随机游走,但作者在讨论中暗示 HBPS 可能对更一般的目标有效。这是一个未经证明的推广。
- 定理 3.2/3.3 的收敛性是在固定时间区间 \([0, T]\) 上建立的,未涉及 \(T \to \infty\) 的渐近行为。作者在讨论中未明确说明这一点。
- 作者声称 HBPS "无需调参",但实际上旅行时间 \(T\) 仍需选择(尽管作者建议用 no-U-turn 算法自动选择)。这是一个轻微的过度声明。
- 定理 3.1 的证明依赖于 \(U_{\text{sur}}\) 的梯度有界性(通过 \(\limsup\) 假设),但作者未讨论该假设在实践中的验证难度。
四、开放问题¶
-
一般目标的收敛性:定理 4.1 的 Peskun-Tierney 排序仅对对数凹目标成立。对于非对数凹目标(如多峰分布),HBPS 是否仍然优于随机游走 Metropolis?这需要新的证明技术。(扎根于定理 4.1 的假设条件)
-
高维极限行为:Deligiannidis et al. (2021) 发现 BPS 在高维极限下收敛到 Randomized HMC。HBPS 在高维极限下的行为是什么?是否也存在类似的极限定理?这需要将本文的刷新极限与高维极限结合分析。(扎根于定理 3.2/3.3 与 Deligiannidis et al. 2021 的对比)
-
自适应旅行时间:作者建议用 no-U-turn 算法选择旅行时间,但未提供理论保证。能否证明自适应选择的旅行时间保持 HBPS 的渐近效率?这类似于 HMC 中 no-U-turn 的自适应理论。(扎根于第 5 节的实验设置)
-
局部与坐标级扩展:作者在第 6.2 节提出了局部和坐标级扩展的框架,但未给出具体算法和实验。这些扩展是否能像 zig-zag 那样实现"超级高效"(即维度无关的混合时间)?(扎根于第 6.2 节的讨论)
-
数值近似的一致性:第 6.1 节的数值近似方案(算法 3)引入了 \(O(\Delta t^2)\) 的误差,但作者未证明该误差对采样器收敛性的影响。能否证明近似方案的遍历性?误差界是多少?(扎根于第 6.1 节的算法 3)
提醒:要确认上述问题是否为真 gap,建议去读以下近期工作的引言部分:(a) zig-zag 和 BPS 的后续改进工作(如局部 zig-zag、因子图 PDMP);(b) HMC 的自适应理论(如 Hoffman et al. 2014 的 no-U-turn 后续分析);(c) 高维极限下 MCMC 的收敛性分析(如 Deligiannidis et al. 2021 的后续工作)。如果这些工作的引言都指向同一个未解决问题,那很可能是共识性的 gap;如果它们各说各话,那可能是一个尚未被明确定义的机会。
Maintained by 陈星宇 · Homepage · Source on GitHub