Finite-Time Analysis of Projected Langevin Monte Carlo
We analyze the projected Langevin Monte Carlo (LMC) algorithm, a close cousin of projected Stochastic Gradient Descent (SGD). We show that LMC allows to sample in polynomial time from a posterior distribution restricted to a convex body and with concave log-likelihood. This gives the first Markov chain to sample from a log-concave distribution with a first-order oracle, as the existing chains with provable guarantees (lattice walk, ball walk and hit-and-run) require a zerothorder oracle. Our proof uses elementary concepts from stochastic calculus which could be useful more generally to understand SGD and its variants.
The authors consider the projected Langevin Monte-Carlo (PLMC) algorithm for sampling from a log-concave density with a compact support. They establish a polynomial-time bound for sampling with a prescribed accuracy. The result is new, nontrivial and, in my opinion provides a very interesting contribution to the theory of computational statistics/machine learning. I went through the proof (without reading the parts which are in the supplementary material) and checked all the details. I have found only a couple of small typos (cf. below). Not only the proof is correct, but also it contains a very elegant argument that makes use of the Skorohod embedding. I am sure any mathematically driven person will appreciate this argument.Here are some minor remarks: - I recommend to add somewhere in the discussion that the PLMC needs not only a first-order oracle but also a projector to the compact set under consideration.- Concerning the discussion on H&R in Section 1.2: the authors seem to claim that H&R requires a zeroth-order oracle, but my understanding is that H&M requires to sample from the restriction of the distribution on the segments. Could the authors comment on the relationship between these two tasks? - Beginning of section 2.1: why do you need to introduce the pair (x,phi)? It is my impression that it suffices to introduce x. Then you can remove the equation of line 184 and replace phi by x-w in the equation on line 187.- line 210: "Dirac" instead of "dirac" -line 225: "paths" instead of "path" - line 244 and Eq (3): in these two formulae there is a \bar W_T that should be replaced by \bar W_t (small t instead of capital T). - line 298: please provide a precise reference for the version of the Khintchine inequality you use.- line 321: could you provide a reference where it is clearly stated that the uniform distribution on a compact set is a stationary distribution for the reflected BM ?N.B. In the confidence evaluation above I have put 4 (and not 5) just because I cannot be absolutely certain of my evaluation of the paper without carefully reading all the details of the proofs which are put in the supplementary material.