Logsmooth Gradient Concentration and Tighter Runtimes for Metropolized Hamiltonian Monte Carlo

We show that the gradient norm $\\|\\nabla f(x)\\|$ for $x \\sim \\exp(-f(x))$,\nwhere $f$ is strongly convex and smooth, concentrates tightly around its mean.\nThis removes a barrier in the prior state-of-the-art analysis for the\nwell-studied Metropolized Hamiltonian Monte Carlo (HMC) algorithm for sampling\nfrom a strongly logconcave distribution. We correspondingly demonstrate that\nMetropolized HMC mixes in $\\tilde{O}(\\kappa d)$ iterations, improving upon the\n$\\tilde{O}(\\kappa^{1.5}\\sqrt{d} + \\kappa d)$ runtime of (Dwivedi et. al. '18,\nChen et. al. '19) by a factor $(\\kappa/d)^{1/2}$ when the condition number\n$\\kappa$ is large. Our mixing time analysis introduces several techniques which\nto our knowledge have not appeared in the literature and may be of independent\ninterest, including restrictions to a nonconvex set with good conductance\nbehavior, and a new reduction technique for boosting a constant-accuracy total\nvariation guarantee under weak warmness assumptions. This is the first\nhigh-accuracy mixing time result for logconcave distributions using only\nfirst-order function information which achieves linear dependence on $\\kappa$;\nwe also give evidence that this dependence is likely to be necessary for\nstandard Metropolized first-order methods.\n