提出加速采样新方法，显著提升随机哈密顿蒙特卡洛收敛速度。
Accelerated Mixing Time of Randomized Hamiltonian Monte Carlo
- 用随机积分时间模拟哈密顿动力学，每轮重置速度为独立高斯变量。
- 在对数凹分布下，达到ε误差的总积分时间仅为O(α^{-1/2} log(ε^{-1}))。
- 适用于对收敛速度要求高的采样任务，如贝叶斯推断与优化问题。
我们证明随机哈密顿蒙特卡洛（RHMC）算法在对数凹概率分布采样中具有加速混合时间保证。RHMC通过重复模拟连续时间哈密顿动力学，每次采用随机积分时间，并在每轮间将速度重置为独立高斯变量。当目标分布为对数凹且满足α-塔拉格兰不等式（例如α-强对数凹分布）时，若使用均值为Θ(α^{-1/2})的三角形或指数分布的随机积分时间，则RHMC在KL散度意义下呈指数收敛，达到ε误差所需的总积分时间为O(α^{-1/2} log(ε^{-1}))。此外，若目标分布为对数凹，且使用均值呈指数增长的三角形分布随机积分时间序列，则总积分时间达到O(ε^{-1/2})。分析依赖于对哈密顿动力学路径上平均KL散度的界，灵感来自基于哈密顿动力学的加速优化方法。
原文摘要 · Abstract (English)
We show the Randomized Hamiltonian Monte Carlo (RHMC) algorithm has accelerated mixing time guarantees for sampling from log-concave probability distributions. RHMC proceeds by repeatedly simulating the continuous-time Hamiltonian dynamics for some random integration times, and resetting the velocity to be an independent Gaussian random variable between each simulation. We show that when the target distribution is log-concave and satisfies an $α$-Talagrand inequality (for example, if the target distribution is $α$-strongly log-concave), if we use a random integration time from either the triangular or the exponential distribution with mean $Θ(α^{-1/2})$, then RHMC converges exponentially fast in KL divergence, and the total integration time to reach error $\varepsilon$ in KL divergence scales as $O(α^{-1/2} \log(\varepsilon^{-1}))$. We also show that when the target distribution is log-concave, if we use a sequence of random integration times from the triangular distribution with exponentially increasing means, then the total integration time to reach error $\varepsilon$ in KL divergence scales as $O(\varepsilon^{-1/2})$. Our analysis relies on a bound on the average KL divergence along Hamiltonian dynamics, which is inspired by an analogous result on accelerated optimization methods based on Hamiltonian dynamics.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。