跳转至

Piecewise deterministic sampling for constrained distributions

作者: Joël Tatang Demano, Paul Dobson, Konstantinos Zygalakis
来源: Statistics and Computing
主题: 统计计算 / 算法
相关性: 4/10
机构绿灯: University of Edinburgh(US News 前 50,免分进入精读)
链接: 期刊页 · arXiv


一、领域脉络与小综述

这个方向是什么

本文属于计算统计(computational statistics) 中"约束域采样"这一子方向。其根本问题是:如何从定义在凸集 M ⊂ ℝᵈ 上的目标分布 π(x) ∝ e^(−U(x)) 中高效地生成(近似)无偏样本。这类问题在贝叶斯统计(如参数有先验约束)、图像处理(像素值有界)、逆问题(解有物理约束)中广泛出现。当前该方向的成熟度处于"方法百花齐放但理论不完整"的阶段——SDE-based 方法(如投影 Langevin、mirror Langevin)已有较成熟的非渐近收敛分析,而 PDMC-based 方法(如 Zig-Zag、Bouncy Particle Sampler)在无约束情形下理论较完善,但约束情形的 PDMC 理论几乎是空白。

发展脉络

  • 奠基工作:Bierkens, Fearnhead & Roberts (2016) 提出 Zig-Zag 过程,首次将 PDMC 引入贝叶斯计算,并证明其可精确模拟(无离散化误差)且支持子采样。这是 PDMC 采样的基石。Bouchard-Côté et al. (2015) 提出 Bouncy Particle Sampler,进一步丰富了 PDMC 家族。这两篇奠定了"非扩散、不可逆、分段确定性"这一采样范式的理论基础。
  • 主要进展(无约束 PDMC 的完善):Bierkens et al. (2019) 证明 Zig-Zag 在温和条件下几何遍历;Fearnhead et al. (2018) 系统讨论了 PDMC 的实现细节(事件模拟、边界处理)。同时,Durmus, Guillemin & Monmarché (2020) 和 Deligiannidis et al. (2019) 分别建立了 BPS 的几何遍历性理论。这一阶段 PDMC 在无约束情形的理论框架基本成型。
  • 主要进展(约束 SDE 采样的发展):Durmus, Moulines 等 的一系列工作(2017-2019)建立了投影 Langevin 算法(PLMC)的非渐近收敛理论;Hsieh et al. (2018) 提出 mirror Langevin 动力学(MLAa),将 mirror descent 思想引入采样;Zhang et al. (2020) 提出 mirror Langevin 算法(MLAm)并给出 Wasserstein 收敛界;Chewi et al. (2020) 证明了 mirror Langevin 扩散的指数遍历性。Ahn & Chewi (2021) 进一步改进了 MLAm 的复杂度分析。这一线的工作表明:mirror map 是处理约束的 SDE-based 采样的核心工具。
  • 当前 frontier:Bierkens et al. (2023) 提出带边界反射的 PDMC 方法(如反射 Zig-Zag),但仅适用于简单几何(如超立方体)。Srinivasan et al. (2024) 提出 Metropolis-adjusted mirror Langevin 算法(MAMLA),将 mirror map 与 Metropolis 校正结合,实现无偏约束采样。本文的位置:作者声称首次将 mirror map 系统性地引入 PDMC 框架,构造了一类新的"mirror PDMC",同时获得 PDMC 的精确采样/子采样优势和 mirror map 的几何适应性。

子线索聚类

  1. SDE-based 约束采样:PLMC(投影)、MYULA(罚函数)、MLAa/MLAm(mirror map)、MAMLA(mirror + Metropolis)。共同点:基于 Langevin 扩散的离散化,存在离散化偏差(除 MAMLA 外),但理论分析成熟(非渐近收敛界、复杂度)。
  2. PDMC-based 无约束采样:Zig-Zag、BPS、Boomerang、Coordinate Sampler。共同点:连续时间、分段确定性、可精确模拟、不可逆性带来潜在加速;理论集中在遍历性(几何/指数)和中心极限定理。
  3. PDMC-based 约束采样(萌芽期):反射 Zig-Zag(Bierkens et al. 2023)、带边界条件的 PDMC(Bierkens et al. 2023)。共同点:处理简单约束几何,缺乏一般性框架。
  4. mirror map 在采样中的应用:从 mirror Langevin(SDE)到 mirror Hamiltonian Monte Carlo,再到本文的 mirror PDMC。共同点:利用 Legendre-Fenchel 变换将约束域映射到无约束空间。

这个方向在追问的核心问题

  1. 如何在约束域上构造不可逆、非扩散的马尔可夫过程? 当前主流答案是反射/投影,但缺乏一般性框架。
  2. 如何在不引入离散化偏差的前提下处理约束? PDMC 的精确模拟优势在约束情形下能否保持?
  3. mirror map 的几何自适应性能否与 PDMC 的不可逆性叠加? 两者结合是否能获得比单独使用任一方法更优的收敛行为?
  4. 子采样(subsampling)在约束 PDMC 中是否仍然精确? 这是大数据贝叶斯推断的关键需求。

已知瓶颈:(i) 约束 PDMC 的遍历性理论几乎空白(本文只给出无界性/不变测度的验证,未给出收敛速率);(ii) mirror map 的选取依赖问题结构,缺乏自适应策略;(iii) 高维情形下 mirror PDMC 的复杂度分析缺失。

⚠️ 作者的 framing

作者将缺口 frame 成:"SDE-based 约束采样方法(PLMC、MYULA、MLAa/MLAm)要么有偏差,要么收敛慢;而 PDMC 方法(Zig-Zag、BPS)虽然无偏且支持子采样,但无法直接处理约束。因此,将 mirror map 引入 PDMC 是'显然的下一步'。" 作者淡化了反射 PDMC(Bierkens et al. 2023)这一竞争路线的适用性,仅在一句话中提及"已有工作考虑简单几何的反射"。作者也回避了 MAMLA 作为无偏 SDE-based 替代方案的竞争力——在数值实验中 MAMLA 被用作 baseline,但作者未讨论其理论保证与 mirror PDMC 的相对优劣。

值得研究者去查的问题:为什么作者没有引用 Bierkens et al. (2023) "Piecewise deterministic Markov processes for sampling from constrained distributions" 或类似的反射 PDMC 工作?如果该工作已存在,本文的 novelty 是否只是"mirror map + 已有 PDMC 框架"的组合?另外,Livingstone & Zanella (2022) 关于 PDMC 子采样的工作也未出现在参考文献中——这是否意味着本文的子采样理论有遗漏?

张力

未见明显对立引用。但存在一个微妙的张力:SDE-based mirror Langevin 文献(Hsieh et al. 2018; Zhang et al. 2020; Chewi et al. 2020)强调 mirror map 的几何自适应性和非渐近收敛界,而 PDMC 文献(Bierkens et al. 2016; Bouchard-Côté et al. 2015)强调不可逆性和精确模拟。本文试图融合两者,但未给出融合后的收敛速率分析——这是两派文献之间的一个真实缺口。


二、最核心、最简单的例子 / 数学问题

第一步:符号、模型、可观测数据

目标:从定义在凸集 M ⊂ ℝᵈ 上的分布 π(x) ∝ e^(−U(x)) 采样,其中 U: M → ℝ 是已知(可能不可微)函数。

核心记号:

记号 含义 类型
M 凸约束集(proper subset of ℝᵈ) 已知结构
π(x) ∝ e^(−U(x)) 目标分布(仅知未归一化密度) 待采样对象
U(x) 势函数(负对数密度) 已知函数
ψ(x) mirror map(凸函数,定义在 M 上) 设计参数
ψ*(y) Legendre-Fenchel 共轭:ψ*(y) = sup_{x∈M} {xᵀy − ψ(x)} 导出量
∇ψ : M → ℝᵈ mirror map 的梯度(将 M 映射到 ℝᵈ) 核心工具
∇ψ* : ℝᵈ → M 逆 mirror map(将 ℝᵈ 映射回 M) 核心工具
(ζ_t, v_t) 对偶空间中的位置和速度 过程状态
(x_t, v_t) 原始空间中的位置和速度 过程状态
λ(ζ, v) 跳跃率函数 设计参数
V(ζ) 对偶空间中的势函数:V = U ∘ ∇ψ* + log det ∇²ψ* 导出量
ρ(dx, dv) 不变测度:π(dx) ⊗ ν(dv) 目标不变测度

模型:作者在对偶空间(dual space)中构造 PDMC,而非直接在原始约束域 M 上操作。具体地:

  1. 对偶变换:令 ζ = ∇ψ(x) ∈ ℝᵈ,则 x = ∇ψ*(ζ) ∈ M。由于 ∇ψ 是 M → ℝᵈ 的双射(由 mirror map 的性质保证),约束采样问题被转化为无约束采样问题。
  2. 对偶势函数:定义 V(ζ) = U(∇ψ(ζ)) − log det ∇²ψ(ζ)。(注意:这里 log det 项来自变量替换的 Jacobian。)目标分布在对偶空间中的密度为 π̃(ζ) ∝ e^(−V(ζ))。
  3. PDMC 动力学:在对偶空间中运行标准的 Zig-Zag 或 BPS 动力学,其不变测度为 π̃(ζ) ⊗ ν(v)。
  4. 映射回原始空间:通过 x = ∇ψ*(ζ) 将对偶空间中的样本映射回 M。

可观测数据:研究者能观测到的是算法输出的样本序列 {x_t}(原始空间)或 {ζ_t}(对偶空间),以及算法的计算成本(梯度评估次数、跳跃次数等)。不可观测的是:目标分布 π 的归一化常数、真实收敛速率、以及算法在有限时间内的偏差。

第二步:最小内核

最小例子:一维截断高斯分布。设 M = (0, +∞),目标分布 π(x) ∝ e^(−U(x)),其中 U(x) = (x−μ)²/(2σ²)(即高斯分布截断到正半轴)。

选择 mirror map:取 ψ(x) = x log x − x(负熵函数)。则: - ∇ψ(x) = log x,因此对偶变量 ζ = log x ∈ ℝ。 - ∇ψ(ζ) = e^ζ,因此 x = e^ζ ∈ (0, +∞) 自动满足约束。 - ∇²ψ(ζ) = e^ζ,因此 log det ∇²ψ*(ζ) = ζ。

对偶势函数:V(ζ) = U(e^ζ) − ζ = (e^ζ − μ)²/(2σ²) − ζ。

核心命题:在对偶空间中运行 Zig-Zag 动力学(速度 v ∈ {−1, +1},跳跃率 λ(ζ, v) = (v·V'(ζ))₊),其不变测度为 π̃(ζ) ∝ e^(−V(ζ))。映射回原始空间后,x = e^ζ 服从截断高斯分布。

为什么这个例子是"最小内核": 1. 它展示了 mirror map 的核心作用:将约束域 M 通过 Legendre-Fenchel 变换映射到无约束空间 ℝᵈ,使得 PDMC 可以直接运行。 2. 它揭示了关键的技术难点:对偶势函数 V 的梯度 V'(ζ) = e^ζ·U'(e^ζ) − 1。当 ζ → −∞(即 x → 0)时,V'(ζ) → −1(有界);当 ζ → +∞(即 x → +∞)时,V'(ζ) ≈ e^ζ/σ² → +∞(无界)。这意味着跳跃率 λ 在 ζ 很大时趋于无穷,需要 Poisson thinning 来处理。 3. 它展示了"无偏性"的来源:PDMC 的精确模拟保证了对偶空间中的样本无偏,而 mirror map 的可逆性保证了映射回原始空间后仍然无偏。

这个最小内核揭示了本文的核心数学贡献:将约束采样问题转化为对偶空间中的无约束 PDMC 问题。所有后续的定理(不变测度验证、遍历性条件)都是围绕这个变换建立的。


三、这篇论文做了什么

三句话

① 研究了什么问题:如何构造一类新的 PDMC(mirror PDMC),使其能够从凸集 M 上的目标分布 π 中精确采样(无离散化偏差),同时保持 PDMC 的子采样能力。

② 核心工具/方法:将凸优化中的 mirror map(Legendre-Fenchel 变换)引入 PDMC 框架。具体地,在对偶空间 ℝᵈ 中运行 Zig-Zag 或 Bouncy Particle 动力学,其势函数为 V = U ∘ ∇ψ* + log det ∇²ψ*,然后通过逆 mirror map 映射回原始约束域 M。

③ 主要结论:(a) 构造了一类新的 mirror PDMC(mirror Zig-Zag 和 mirror Bouncy Particle Sampler),并验证了其不变测度正确;(b) 证明了 mirror PDMC 支持精确子采样(exact subsampling),即可以用无偏梯度估计替代全梯度而不破坏不变测度;(c) 在数值实验中,mirror PDMC 在 Gamma 分布、截断高斯、Dirichlet 后验等约束采样问题上优于 SDE-based 方法(PLMC、MYULA、MLAa、MLAm、MAMLA)。

关键设定与假设

设定(在第二节记号基础上补全):

  1. mirror map 的假设:ψ 是 M 上的本质光滑、严格凸函数(essentially smooth, strictly convex),且满足** Legendre 型条件*(即 ∇ψ 是 M 的内部到 ℝᵈ 的双射)。这个假设保证了 ∇ψ 存在且光滑。统计含义:这等价于要求约束集 M 存在一个"光滑的参数化",使得边界在变换后消失。

  2. 势函数 U 的假设:U 在 M 上连续可微(或至少弱可微),且 ∇U 在 M 上满足某种增长条件(保证对偶势 V 的梯度有界或可控制)。相比已有文献:PLMC 只要求 U 在 M 上可微且投影有定义;MLAa/MLAm 要求 U 相对 ψ 光滑(relative smoothness)。本文的假设介于两者之间——不要求 U 全局 Lipschitz,但要求变换后的 V 满足 PDMC 的跳跃率可模拟条件。

  3. 跳跃率的构造:mirror Zig-Zag 的跳跃率 λ(ζ, v) = Σᵢ (vᵢ ∂ᵢV(ζ))₊,其中 V 是对偶势。关键点:这个跳跃率与标准 Zig-Zag 完全相同,只是势函数从 U 换成了 V。这意味着所有 PDMC 的理论工具(Poisson thinning、子采样)都可以直接套用。

  4. 子采样设定:在贝叶斯框架下,U(x) = −log π₀(x) − Σⱼ log f(yⱼ|x)(先验 + 数据对数似然)。对偶势 V 同样分解为 V(ζ) = V₀(ζ) + Σⱼ Vⱼ(ζ),其中 Vⱼ = −log f(yⱼ|∇ψ(ζ)) + (1/K)log det ∇²ψ(ζ)。子采样即用随机子集 J ⊂ {1,...,K} 构造 V 的无偏估计,配合 Poisson thinning 实现精确子采样。

相比已有文献的强化/弱化: - 强化:本文的 mirror PDMC 是无偏的(精确模拟),而 PLMC、MYULA、MLAa、MLAm 都有离散化偏差(尽管 MLAm 的偏差可以控制)。 - 弱化:本文未给出收敛速率分析。作为对比,PLMC 有非渐近 L² 收敛界(Durmus & Moulines 2019),MLAm 有 Wasserstein 收敛界(Zhang et al. 2020),MAMLA 有 Metropolis-Hastings 的遍历性保证。本文只验证了不变测度正确,未证明收敛速度。

主要结果

定理 1(不变测度):在假设 1-2 下,mirror Zig-Zag 过程 (ζ_t, v_t) 以 π̃ ⊗ Unif({±1}ᵈ) 为不变测度,其中 π̃(ζ) ∝ e^(−V(ζ))。证明思路:验证生成元(generator)在测试函数上的零作用,即 ∫ Lf d(π̃⊗ν) = 0。这是 PDMC 标准论证的推广——关键在于 V 的定义保证了 π̃ 是跳跃率 λ 的"平衡测度"。

定理 2(子采样不变性):若用无偏估计 V̂(ζ) 替代 V(ζ) 构造跳跃率,则 mirror Zig-Zag 仍以 π̃ ⊗ Unif({±1}ᵈ) 为不变测度。证明思路:利用 Poisson thinning 的性质——只要估计是无偏的,thinning 过程的不变测度不变。这是 Bierkens et al. (2019) 子采样理论的直接推广。

数值实验: - Gamma 分布(d=1, 100):mirror Zig-Zag 的 Wasserstein-1 误差低于 MLAa、MLAm、MAMLA,且无可见偏差。 - 截断高斯(d=10):mirror Zig-Zag 和 mirror BPS 的估计无偏,而 PLMC 和 MYULA 有可见偏差。 - Dirichlet 后验(d=5):mirror Zig-Zag 和 mirror BPS 的收敛速度优于 SDE-based 方法,且子采样版本(MZZ-SS)在保持无偏的同时显著降低计算成本。

🔎 结论是否比证明窄

是,且明显。具体表现:

  1. 定理只覆盖不变测度,不覆盖收敛速率。作者在 Section 4.2 只证明了"如果对偶 Zig-Zag 遍历,则 mirror Zig-Zag 遍历",但没有给出任何收敛速率估计。然而在数值实验中,作者声称 mirror PDMC "converge faster"(Figure 3, 4, 6),这超出了定理的保证范围。

  2. 子采样理论只覆盖"不变性",不覆盖"效率"。定理 2 只说明子采样不破坏不变测度,但未分析子采样引入的方差对收敛速率的影响。在 Figure 6 中,作者展示了 MZZ-SS 的收敛行为,但没有理论解释为什么子采样版本收敛更快。

  3. 遍历性条件未验证。作者在 Section 4.2 提到"在温和条件下"对偶 Zig-Zag 遍历,但未给出这些条件的具体形式,也未验证数值实验中的例子是否满足这些条件。特别是,Gamma 分布的 mirror map(负熵)导致对偶势 V 可能不是凸的——这超出了标准 Zig-Zag 遍历性理论的适用范围。

  4. "优于 SDE-based 方法"的 claim 缺乏理论支撑。数值实验中 mirror PDMC 优于 MLAa/MLAm/MAMLA,但作者没有给出任何复杂度对比(如 mixing time 的显式界)。作为对比,Zhang et al. (2020) 和 Ahn & Chewi (2021) 对 mirror Langevin 算法给出了显式的迭代复杂度。


四、开放问题

以下问题均扎根于本文的具体语句:

  1. 收敛速率分析(扎根于 Theorem 1-2 只证明不变测度,未给速率):mirror PDMC 的 mixing time 是多少?在什么条件下(如 V 的凸性、光滑性、Poincaré 不等式)能获得显式的收敛速率?这与 Zhang et al. (2020) 对 mirror Langevin 的 Wasserstein 分析能否类比?

  2. mirror map 的自适应选取(扎根于 Section 4.1 的 remark:"a case by case approach will provide a more useful bound"):是否存在系统性的方法选择 mirror map ψ 以优化 PDMC 的收敛速率?这与 mirror descent 中 Bregman 距离的选取有何联系?

  3. 高维行为的刻画(扎根于数值实验只覆盖 d ≤ 100):mirror PDMC 在 d 很大时的 mixing time 如何随维度增长?是否存在维度灾难?这与 PDMC 在高维无约束情形的已知结果(如 Bierkens et al. 2019 的维度依赖分析)有何异同?

  4. 子采样的方差控制(扎根于 Theorem 2 只保证不变性,未分析方差):mirror Zig-Zag 的子采样版本(MZZ-SS)的渐近方差是多少?控制变量(control variate)的最优参考点如何选择?这与 Bierkens et al. (2019) 对 Zig-Zag 子采样的方差分析能否推广?

  5. 非凸约束集(扎根于假设 M 是凸集):mirror map 方法能否推广到非凸约束集(如离散集合、流形)?这与 Riemannian Langevin 方法(Girolami & Calderhead 2011)有何联系?

  6. 与优化理论的深层联系(扎根于 mirror map 源自凸优化):mirror PDMC 的连续时间极限是否对应于某种 mirror descent 的随机微分方程?这种联系能否用于设计新的采样算法?


提醒:要确认上述问题是否为真 gap,建议去读以下近期工作的 intro:(i) Bierkens et al. (2023) 关于带边界 PDMC 的工作;(ii) Ahn & Chewi (2021) 关于 mirror Langevin 复杂度的工作;(iii) Srinivasan et al. (2024) 关于 MAMLA 的工作。如果这些工作的 intro 都指向"约束 PDMC 的收敛速率分析是开放的",那么问题 1 就是共识性 gap;如果它们给出了速率分析,那么本文的贡献就比表面看起来更有限。


Maintained by 陈星宇 · Homepage · Source on GitHub

评论