Sampling from a log-concave distribution with Projected Langevin Monte Carlo

We extend the Langevin Monte Carlo (LMC) algorithm to compactly supported\nmeasures via a projection step, akin to projected Stochastic Gradient Descent\n(SGD). We show that (projected) LMC allows to sample in polynomial time from a\nlog-concave distribution with smooth potential. This gives a new Markov chain\nto sample from a log-concave distribution. Our main result shows in particular\nthat when the target distribution is uniform, LMC mixes in $\\tilde{O}(n^7)$\nsteps (where $n$ is the dimension). We also provide preliminary experimental\nevidence that LMC performs at least as well as hit-and-run, for which a better\nmixing time of $\\tilde{O}(n^4)$ was proved by Lov{\\'a}sz and Vempala.\n