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.

给出了使用两种蒙特卡罗采样方法（MALA 和 HMC）在良好条件的分布下性能的下界，并确定了每种方法的最短混合时间和松弛时间。该文还发现了跃点积分和 Chebyshev 多项式之间的新连接。

针对良好条件分布的 Metropolized 采样方法下限

Lower Bounds on Metropolized Sampling Methods for Well-Conditioned  Distributions

The Metropolis-adjusted Langevin algorithm (MALA) is a Metropolis-Hastings
method for approximate sampling from continuous distributions. We derive upper
bounds for the contraction rate in Kantorovich-Rubinstein-Wasserstein distance
of the MALA chain with semi-implicit Euler proposals applied to log-concave
probability measures that have a density w.r.t. a Gaussian reference measure.
For sufficiently "regular" densities, the estimates are dimension-independent,
and they hold for sufficiently small step sizes $h$ that do not depend on the
dimension either. In the limit $h\downarrow0$, the bounds approach the known
optimal contraction rates for overdamped Langevin diffusions in a convex
potential. A similar approach also applies to Metropolis-Hastings chains with
Ornstein-Uhlenbeck proposals. In this case, the resulting estimates are still
independent of the dimension but less optimal, reflecting the fact that MALA is
a higher order approximation of the diffusion limit than Metropolis-Hastings
with Ornstein-Uhlenbeck proposals.

本文研究了自适应 Metropolis-Langevin 算法在连续分布中采样的效果，推导出了对于密度函数满足某些特征的情况下，Kantorovich-Rubinstein-Wasserstein 距离的上界；并且该上界不依赖于维度，且在一定步长范围内成立。