Smoothed Picard Hamiltonian Monte Carlo

Abstract

We develop a new low-accuracy sampler, called \emph{smoothed Picard Hamiltonian Monte Carlo}, which combines Gaussian smoothing, Picard iteration, and higher-order discretization. For a log-concave target $\pi \propto \exp (-V)$ in dimension $d$ satisfying $0\prec \alpha I⪯{\nabla }^{2}V⪯\beta I$, with condition number $\kappa :=\beta /\alpha$, smoothed Picard HMC returns a sample with $\sqrt{\alpha }{W}_2(\cdot ,\pi )\le \epsilon$ using $\tilde{O}({\kappa }^2+{\kappa }^{7/6}{d}^{1/6}/{\epsilon }^{1/3})$ gradient queries. We also prove stronger $W_q$ bounds, and then develop an algorithmic framework, the recursive warm start generator, to upgrade these $W_q$ bounds to stronger divergence guarantees. This produces a warm start for the proximal bouncy particle sampler, introduced in a companion work, leading to a high-accuracy log-concave sampler with complexity $\tilde{O}(({\kappa }^{7/6}{d}^{1/6}+{\kappa }^{1/2}{d}^{1/4})\mathrm{polylog}(1/\epsilon ))$.