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_3: 
@cite_7: Let M(x) denote the expected value at level x of the response to a certain experiment. M(x) is assumed to be a monotone function of x but is unknown to the experimenter, and it is desired to find the solution x = θ of the equation M(x) = α, where a is a given constant. We give a method for making successive experiments at levels x1, x2, ··· in such a way that xn will tend to θ in probability.
@cite_2: The behavior of the stationary distribution of a Markovian process of the form [( * ) X_ n + 1 ^a = _S (X_n^a - aY_n^a ) ] as a tends to zero is studied. The process @math is a constant step-size (constant gain) constrained stochastic approximation process, with @math being the projection onto the convex set of constraints S. If the gains a are held constant, the process @math does not converge to the point of solution but the stationary distribution of @math converges to the unit mass at the solution, if @math . Properly normalized the stationary distribution converges to a nondegenerated limit. This limit depends on the smoothness of the feasible set S in the neighborhood of the solution (in particular on the dimension of the largest linear subspace contained in the tangential cone).
Our main motivation to study the chain stems from its connection with the ubiquitous stochastic gradient descent (SGD) algorithm. In general this algorithm takes the form @math where @math is a centered i.i.d. sequence. Standard results in approximation theory, such as @cite_7 , show that if the variance of the noise @math is of smaller order than the step-size @math then the iterates @math converge to the minimum of @math on @math (for a step-size decreasing sufficiently fast as a function of the number of iterations). For the specific noise sequence that we study in , the variance is exactly equal to the step-size, which is why the chain deviates from its standard and well-understood behavior. We also note that other regimes where SGD does not converge to the minimum of @math have been studied in the optimization literature, such as the constant step-size case investigated in @cite_2 @cite_3 .