Finite-Time Analysis of Projected Langevin Monte Carlo
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.
Cite
Text
Bubeck et al. "Finite-Time Analysis of Projected Langevin Monte Carlo." Neural Information Processing Systems, 2015.Markdown
[Bubeck et al. "Finite-Time Analysis of Projected Langevin Monte Carlo." Neural Information Processing Systems, 2015.](https://mlanthology.org/neurips/2015/bubeck2015neurips-finitetime/)BibTeX
@inproceedings{bubeck2015neurips-finitetime,
title = {{Finite-Time Analysis of Projected Langevin Monte Carlo}},
author = {Bubeck, Sebastien and Eldan, Ronen and Lehec, Joseph},
booktitle = {Neural Information Processing Systems},
year = {2015},
pages = {1243-1251},
url = {https://mlanthology.org/neurips/2015/bubeck2015neurips-finitetime/}
}