Optimal Convergence Rate of Hamiltonian Monte Carlo for Strongly Logconcave Distributions
Optimal Convergence Rate of Hamiltonian Monte Carlo for Strongly Logconcave Distributions
复制标题
DOI：
10.4230/lipics.approx-random.2019.64
复制
发表时间：
2019-05
期刊：
影响因子：
--
通讯作者：
Zongchen Chen;S. Vempala
中科院分区：
文献类型：
--
作者：
Zongchen Chen;S. Vempala
我们研究了强对数凹密度下抽样的哈密顿蒙特卡罗方法，其中$f：\mathbb{R}^dto\mathbb{R}$是$\mU-强凸的，$L$-光滑的(条件数为$\kappa=L/\mU)。我们证明了理想HMC的驰豫时间(谱隙的倒数)为$O(Kappa)$，改进了以前的最佳界$O(kappa^{1.5})$；我们用一个驰豫时间为$Omega(Kappa)$的例子补充了这一点。使用近乎最佳的ODE解算器实施时，HMC使用$\widetilde{O}((\kappa d)^{0.5}\varepsilon^{-1})$渐变求值每步和$\widetilde{O}((\kappa d)^{1.5}\varepsilon^{-1})$返回$\varepsilon$-以$2$-Wasserstein距离表示的近似点。
We study Hamiltonian Monte Carlo (HMC) for sampling from a strongly logconcave density proportional to $e^{-f}$ where $f:\mathbb{R}^d \to \mathbb{R}$ is $\mu$-strongly convex and $L$-smooth (the condition number is $\kappa = L/\mu$). We show that the relaxation time (inverse of the spectral gap) of ideal HMC is $O(\kappa)$, improving on the previous best bound of $O(\kappa^{1.5})$; we complement this with an example where the relaxation time is $\Omega(\kappa)$. When implemented using a nearly optimal ODE solver, HMC returns an $\varepsilon$-approximate point in $2$-Wasserstein distance using $\widetilde{O}((\kappa d)^{0.5} \varepsilon^{-1})$ gradient evaluations per step and $\widetilde{O}((\kappa d)^{1.5}\varepsilon^{-1})$ total time.