NeurIPS 2015poster55 citations
Finite-Time Analysis of Projected Langevin Monte Carlo
Sebastien Bubeck, Ronen Eldan, Joseph Lehec
Abstract
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.
BibTeX
@inproceedings{NIPS2015_c0f168ce,
author = {Bubeck, Sebastien and Eldan, Ronen and Lehec, Joseph},
booktitle = {Advances in Neural Information Processing Systems},
editor = {C. Cortes and N. Lawrence and D. Lee and M. Sugiyama and R. Garnett},
pages = {},
publisher = {Curran Associates, Inc.},
title = {Finite-Time Analysis of Projected Langevin Monte Carlo},
url = {https://proceedings.neurips.cc/paper_files/paper/2015/file/c0f168ce8900fa56e57789e2a2f2c9d0-Paper.pdf},
volume = {28},
year = {2015}
}