Lower Bounds on Metropolized Sampling Methods for Well-Conditioned Distributions
Lower Bounds on Metropolized Sampling Methods for Well-Conditioned Distributions
复制标题
DOI：
--
复制
发表时间：
2021-06
期刊：
影响因子：
--
通讯作者：
Y. Lee;Ruoqi Shen;Kevin Tian
中科院分区：
文献类型：
--
作者：
Y. Lee;Ruoqi Shen;Kevin Tian
在实践中，当将大都市调整后的兰格文算法（MALA）和多步汉密尔顿蒙特卡洛（HMC）带有Leapfrog Integrator，我们将两种最受欢迎的采样方法的性能提供了下限。我们的主要结果是$ \ widetilde {\ omega}（\ kappa d）$的几乎紧密的下限在Mala的混合时间上，从一个指数级温暖的开始，与一系列算法结果匹配，并与对数因素相匹配，并回答了一个公开的因素Chewi等人的问题。 al。我们还表明，在任何数量的跨越步骤下，对HMC的放松时间是必不可少的，并且通过更改步骤计数来绑定可实现的收益。我们的HMC分析借鉴了LeapFrog Integration和Chebyshev多项式之间的新联系，这可能具有独立的关注。
We give lower bounds on the performance of two of the most popular sampling methods in practice, the Metropolis-adjusted Langevin algorithm (MALA) and multi-step Hamiltonian Monte Carlo (HMC) with a leapfrog integrator, when applied to well-conditioned distributions. Our main result is a nearly-tight lower bound of $\widetilde{\Omega}(\kappa d)$ on the mixing time of MALA from an exponentially warm start, matching a line of algorithmic results up to logarithmic factors and answering an open question of Chewi et. al. We also show that a polynomial dependence on dimension is necessary for the relaxation time of HMC under any number of leapfrog steps, and bound the gains achievable by changing the step count. Our HMC analysis draws upon a novel connection between leapfrog integration and Chebyshev polynomials, which may be of independent interest.