Rapid mixing bounds for Hamiltonian Monte Carlo and geodesic walks, via positive curvature and momentum

Speaker: Oren Mangoubi (uOttawa)

Time: 1:30-2:30 Jan 20 (Friday)

Location: KED B015

Abstract:  Most existing methods for analyzing ``geometric" Markov Chain Monte Carlo (MCMC) algorithms such as Hamiltonian Monte Carlo (HMC) and geodesic walks use conductance bounds.  Unfortunately, conductance bounds cannot capture improvements obtained from momentum or positive curvature. To take advantage of positive curvature and momentum, our analysis of HMC and geodesic walks instead uses probabilistic coupling bounds, obtained via comparison geometry.

Specifically, we obtain rapid mixing bounds for HMC in an important class of strongly log-concave target distributions, showing that HMC is faster than many competitor algorithms such as the Langevin MCMC algorithm in this regime.  

We also introduce the geodesic walk, an implementable Markov chain that achieves a volume-measure stationary distribution on a Riemannian manifold $\mathcal{M}$ without computationally intensive Metropolis-Hastings corrections.  For positively-curved $\mathcal{M}$, we show that the geodesic walk has mixing time $\mathcal{O}^*(\frac{\mathfrak{M}_2}{\mathfrak{m}_2})$, where $\mathfrak{M}_2$ and $\mathfrak{m}_2$ are, respectively, upper and lower bounds on the sectional curvature of $\mathcal{M}$.