[edit]
Logsmooth Gradient Concentration and Tighter Runtimes for Metropolized Hamiltonian Monte Carlo
[edit]
Proceedings of Thirty Third Conference on Learning Theory, PMLR 125:25652597, 2020.
Abstract
We show that the gradient norm $\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 stateoftheart analysis for the wellstudied Metropolized Hamiltonian Monte Carlo (HMC) algorithm for sampling from a strongly logconcave distribution. We correspondingly demonstrate that Metropolized HMC mixes in $\tilde{O}(\kappa d)$ iterations, improving upon the $\tilde{O}(\kappa^{1.5}\sqrt{d} + \kappa d)$ runtime of prior work 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 constantaccuracy total variation guarantee under weak warmness assumptions. This is the first highaccuracy mixing time result for logconcave distributions using only firstorder function information which achieves linear dependence on $\kappa$; we also give evidence that this dependence is likely to be necessary for standard Metropolized firstorder methods.
Related Material


