Timezone: »

Finite-Time Analysis of Projected Langevin Monte Carlo
Sebastien Bubeck · Ronen Eldan · Joseph Lehec

Wed Dec 09 04:00 PM -- 08:59 PM (PST) @ 210 C #93 #None

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 zeroth-order oracle. Our proof uses elementary concepts from stochastic calculus which could be useful more generally to understand SGD and its variants.

Author Information

Sebastien Bubeck (MSR)
Ronen Eldan
Joseph Lehec

More from the Same Authors