We show that the gradient norm $\|\nabla f(x)\|$ for $x \sim \exp(-f(x))$, where $f$ is strongly convex and smooth, concentrates tightly around its mean. This removes a barrier in the prior state-of-the-art analysis for the well-studied Metropolized Hamiltonian Monte Carlo (HMC) algorithm for sampling from a strongly logconcave distribution \cite{DwivediCWY18}. We correspondingly demonstrate that Metropolized HMC mixes in $\tilde{O}(\kappa d)$ iterations\footnote{We use $\tilde{O}$ to hide logarithmic factors in problem parameters.}, improving upon the $\tilde{O}(\kappa^{1.5}\sqrt{d} + \kappa d)$ runtime of \cite{DwivediCWY18, ChenDWY19} by a factor $(\kappa/d)^{1/2}$ when the condition number $\kappa$ is large. Our mixing time analysis introduces several techniques which to our knowledge have not appeared in the literature and may be of independent interest, including restrictions to a nonconvex set with good conductance behavior, and a new reduction technique for boosting a constant-accuracy total variation guarantee under weak warmness assumptions. This is the first mixing time result for logconcave distributions using only first-order function information which achieves linear dependence on $\kappa$; we also give evidence that this dependence is likely to be necessary for standard Metropolized first-order methods.

通过基于梯度范式的均值紧密集中证明了Metropolized Hamiltonian Monte Carlo算法在从强logconcave分布中进行采样方面的状态最前沿，通过介绍不同于先前文献的限制和新的降低技术，我们提出了高精度混合时间结果， 大大优化了传统的Metropolized first-order方法。

Metropolized Hamiltonian Monte Carlo的对数平滑梯度集中性与更紧致的运行时