Timezone: »

 
Poster
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
in Poster Session »

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.

[ PDF] 

Author Information

Sebastien Bubeck (MSR)
Ronen Eldan (Weizmann)
Joseph Lehec

More from the Same Authors