2015
NIPS
NeurIPS 2015
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.
🌉
Interdisciplinary Bridge
— Machine Learning and Mathematics & Optimization
🧭
Keyword Pioneer
— langevin monte carlo
🐣
Hot Topic Early Bird
— langevin dynamics
🐝
Cross-Pollinator
— Artificial Intelligence, Computer Science, Computer Vision, Data Science & Analytics, Deep Learning, Healthcare & Medicine, Interdisciplinary, Knowledge & Reasoning, Machine Learning, Mathematics & Optimization, Natural Language Processing, Reinforcement Learning, Robotics, Security & Privacy, Speech & Audio
Authors
Topics
Machine Learning > Optimization & Theory > Bayesian Inference
Machine Learning > Optimization & Theory > Stochastic Processes
Mathematics & Optimization > Mathematics > Probability
Machine Learning > Optimization & Theory > Stochastic Methods
Machine Learning > Bayesian & Probabilistic > Bayesian Inference
Machine Learning > Bayesian & Probabilistic > Markov Chain Monte Carlo