Efficient Sampling on Riemannian Manifolds via Langevin MCMC
<|reference_start|>Efficient Sampling on Riemannian Manifolds via Langevin MCMC: We study the task of efficiently sampling from a Gibbs distribution $d \pi^* = e^{-h} d {vol}_g$ over a Riemannian manifold $M$ via (geometric) Langevin MCMC; this algorithm involves computing exponential maps in random Gaussian directions and is efficiently implementable in practice. The key to our analysis of Langevin MCMC is a bound on the discretization error of the geometric Euler-Murayama scheme, assuming $\nabla h$ is Lipschitz and $M$ has bounded sectional curvature. Our error bound matches the error of Euclidean Euler-Murayama in terms of its stepsize dependence. Combined with a contraction guarantee for the geometric Langevin Diffusion under Kendall-Cranston coupling, we prove that the Langevin MCMC iterates lie within $\epsilon$-Wasserstein distance of $\pi^*$ after $\tilde{O}(\epsilon^{-2})$ steps, which matches the iteration complexity for Euclidean Langevin MCMC. Our results apply in general settings where $h$ can be nonconvex and $M$ can have negative Ricci curvature. Under additional assumptions that the Riemannian curvature tensor has bounded derivatives, and that $\pi^*$ satisfies a $CD(\cdot,\infty)$ condition, we analyze the stochastic gradient version of Langevin MCMC, and bound its iteration complexity by $\tilde{O}(\epsilon^{-2})$ as well.<|reference_end|>
@article{cheng2024efficient,
    title={Efficient Sampling on Riemannian Manifolds via Langevin MCMC},
    author={Xiang Cheng, Jingzhao Zhang, Suvrit Sra},
    journal={arXiv preprint arXiv:2402.10357},
    year={2024},
    archivePrefix={arXiv},
    eprint={2402.10357},
    primaryClass={math.ST cs.LG math.PR stat.CO stat.ML stat.TH}
}