Sampling from a log-concave distribution with Projected Langevin Monte Carlo
This addresses a fundamental problem in computational statistics and machine learning for sampling from high-dimensional distributions, though it appears incremental as it builds on existing methods with a projection step.
The paper tackles the problem of sampling from log-concave distributions by extending Langevin Monte Carlo with a projection step, showing it mixes in polynomial time, specifically $ ilde{O}(n^7)$ steps for uniform distributions, and provides experimental evidence it performs comparably to hit-and-run.
We extend the Langevin Monte Carlo (LMC) algorithm to compactly supported measures via a projection step, akin to projected Stochastic Gradient Descent (SGD). We show that (projected) LMC allows to sample in polynomial time from a log-concave distribution with smooth potential. This gives a new Markov chain to sample from a log-concave distribution. Our main result shows in particular that when the target distribution is uniform, LMC mixes in $\tilde{O}(n^7)$ steps (where $n$ is the dimension). We also provide preliminary experimental evidence that LMC performs at least as well as hit-and-run, for which a better mixing time of $\tilde{O}(n^4)$ was proved by Lov{á}sz and Vempala.