提出高效生成高维哈密顿采样初始状态的方法,显著提升采样效率。
Algorithmic warm starts for Hamiltonian Monte Carlo
- 非马尔可夫化哈密顿蒙特卡洛在4次方根量级内生成良好初始状态。
- 总采样复杂度达~d^{1/4},优于此前最优的~d^{1/2}。
- 适用于强对数凹分布,适合需要高精度采样的实际应用。
从连续概率密度中生成样本是统计学、工程与科学中的核心算法问题。在高维情形下,哈密顿蒙特卡洛(HMC)是主流软件包的标准算法。然而,尽管已有大量关于HMC的研究并取得广泛成功,其迭代次数随维度d的变化关系仍不明确。已有研究表明,带拒绝采样的HMC在接近平稳分布的热启动下可在O(d^{1/4})次迭代内收敛;但若无热启动,其速度显著下降,例如在各向同性高斯分布上仍需Ω(d^{1/2})次迭代。因此,获取热启动成为HMC的计算瓶颈。本文针对满足强对数凹性(或等周性)及三阶导数有界的分布,证明非拒绝采样的HMC可在~O(d^{1/4})次迭代内生成热启动,此后可利用带拒绝采样的HMC加速收敛。最终复杂度为~O(d^{1/4}),是此类假设下的最快采样算法,优于此前最优的~O(d^{1/2})。该结果解决了长期悬而未决的维度复杂性问题,并为实际实现提供了简单易行的热启动方案。
原文摘要 · Abstract (English)
Generating samples from a continuous probability density is a central algorithmic problem across statistics, engineering, and the sciences. For high-dimensional settings, Hamiltonian Monte Carlo (HMC) is the default algorithm across mainstream software packages. However, despite the extensive line of work on HMC and its widespread empirical success, it remains unclear how many iterations of HMC are required as a function of the dimension $d$. On one hand, a variety of results show that Metropolized HMC converges in $O(d^{1/4})$ iterations from a warm start close to stationarity. On the other hand, Metropolized HMC is significantly slower without a warm start, e.g., requiring $Ω(d^{1/2})$ iterations even for simple target distributions such as isotropic Gaussians. Finding a warm start is therefore the computational bottleneck for HMC. We resolve this issue for the well-studied setting of sampling from a probability distribution satisfying strong log-concavity (or isoperimetry) and third-order derivative bounds. We prove that \emph{non-Metropolized} HMC generates a warm start in $\tilde{O}(d^{1/4})$ iterations, after which we can exploit the warm start using Metropolized HMC. Our final complexity of $\tilde{O}(d^{1/4})$ is the fastest algorithm for high-accuracy sampling under these assumptions, improving over the prior best of $\tilde{O}(d^{1/2})$. This closes the long line of work on the dimensional complexity of MHMC for such settings, and also provides a simple warm-start prescription for practical implementations.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。