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 @math steps (where @math 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 @math was proved by Lov 'a sz and Vempala.
@cite_15: Sampling from various kinds of distributions is an issue of paramount importance in statistics since it is often the key ingredient for constructing estimators, test procedures or confidence intervals. In many situations, the exact sampling from a given distribution is impossible or computationally expensive and, therefore, one needs to resort to approximate sampling strategies. However, there is no well-developed theory providing meaningful nonasymptotic guarantees for the approximate sampling procedures, especially in the high-dimensional problems. This paper makes some progress in this direction by considering the problem of sampling from a distribution having a smooth and log-concave density defined on @math , for some integer @math . We establish nonasymptotic bounds for the error of approximating the true distribution by the one obtained by the Langevin Monte Carlo method and its variants. We illustrate the effectiveness of the established guarantees with various experiments. Underlying our analysis are insights from the theory of continuous-time diffusion processes, which may be of interest beyond the framework of distributions with log-concave densities considered in the present work.
@cite_8: In this paper we consider a continuous-time method of approximating a given distribution using the Langevin diusion dLtdWt 1 2 r log (Lt)dt. We ®nd conditions under this diusion converges exponentially quickly to or does not: in one dimension, these are essentially that for distributions with exponential tails of the form (x) exp (y |x| , 0< <1, exponential convergence occurs if and only if 1. We then consider conditions under which the discrete approximations to the diusion converge. We ®rst show that even when the diusion itself converges, naive discretizations need not do so. We then consider a Metropolis-adjusted' version of the algorithm, and ®nd conditions under which this also converges at an exponential rate: perhaps surprisingly, even the Metropolized version need not converge exponentially fast even if the diusion does. We brie y discuss a truncated form of the algorithm which, in practice, should avoid the diculties of the other forms.
The chain is also closely related to a line of works in Bayesian statistics on Langevin Monte Carlo algorithms, starting essentially with @cite_8 . The focus there is on the unconstrained case, that is @math . In this simpler situation, a variant of Theorem was proven in the recent paper @cite_15 . The latter result is the starting point of our work. A straightforward way to extend the analysis of Dalalyan to the constrained case is to run the unconstrained chain with an additional potential that diverges quickly as the distance from @math to @math increases. However it seems much more natural to study directly the chain . Unfortunately the techniques used in @cite_15 cannot deal with the singularities in the diffusion process which are introduced by the projection. As we explain in Section our main contribution is to develop the appropriate machinery to study .