论文标题
加速汉密尔顿蒙特卡洛通过Chebyshev整合时间
Accelerating Hamiltonian Monte Carlo via Chebyshev Integration Time
论文作者
论文摘要
汉密尔顿蒙特卡洛（HMC）是抽样中流行的方法。尽管有很多关于各个方面的方法研究这种方法的作品，但一个有趣的问题是如何选择其集成时间以实现加速。在这项工作中，我们考虑从分布$π（x）\ propto \ exp（-f（x））$通过HMC通过时间变化的集成时间来加速采样过程。当潜在的$ f $为$ l $ -smooth和$ m $ -s strongly凸，即\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ hmc所需要的$ε$ - $ε$ε$ sserstein-2 $（$ε$ ous pogughots $ε$ qu $ outs $ o（ \ frac {1}ε）$，其中$κ：= \ frac {l} {m} $是条件号。我们提出了一个基于Chebyshev多项式根源的时变整合时间的方案。我们表明，在二次潜在$ f $的情况下，即当目标$π$是高斯分布时，理想的HMC只需选择集成时间，就需要$ O（\sqrtκ\ log \ log \ frac {1} 1}ε）$到达wasserstein-2距离少于$ε$;对条件编号的依赖性的这种改善类似于优化的加速。与建议集成时间的HMC的设计和分析建立在Chebyshev多项式的工具上。实验发现，即使是从没有二次的平滑凸电势的分布中进行采样，也可以采用我们时变的整合时间方案的优势。
Hamiltonian Monte Carlo (HMC) is a popular method in sampling. While there are quite a few works of studying this method on various aspects, an interesting question is how to choose its integration time to achieve acceleration. In this work, we consider accelerating the process of sampling from a distribution $π(x) \propto \exp(-f(x))$ via HMC via time-varying integration time. When the potential $f$ is $L$-smooth and $m$-strongly convex, i.e.\ for sampling from a log-smooth and strongly log-concave target distribution $π$, it is known that under a constant integration time, the number of iterations that ideal HMC takes to get an $ε$ Wasserstein-2 distance to the target $π$ is $O( κ\log \frac{1}ε )$, where $κ:= \frac{L}{m}$ is the condition number. We propose a scheme of time-varying integration time based on the roots of Chebyshev polynomials. We show that in the case of quadratic potential $f$, i.e., when the target $π$ is a Gaussian distribution, ideal HMC with this choice of integration time only takes $O( \sqrtκ \log \frac{1}ε )$ number of iterations to reach Wasserstein-2 distance less than $ε$; this improvement on the dependence on condition number is akin to acceleration in optimization. The design and analysis of HMC with the proposed integration time is built on the tools of Chebyshev polynomials. Experiments find the advantage of adopting our scheme of time-varying integration time even for sampling from distributions with smooth strongly convex potentials that are not quadratic.
