Sampling from a log-concave distribution with Projected Langevin Monte Carlo
Bubeck, Sébastien; Eldan, Ronen; Lehec, Joseph (2017), Sampling from a log-concave distribution with Projected Langevin Monte Carlo. https://basepub.dauphine.fr/handle/123456789/17068
TypeDocument de travail / Working paper
External document linkhttps://hal.archives-ouvertes.fr/hal-01428950
Series titleCahier de recherche CEREMADE, Université Paris-Dauphine
MetadataShow full item record
Abstract (EN)We extend the Langevin Monte Carlo (LMC) algorithm to compactly supported measures via a projection step, akin to projected Stochastic Gradient Descent (SGD). We show that (projected) LMC allows to sample in polynomial time from a log-concave distribution with smooth potential. This gives a new Markov chain to sample from a log-concave distribution. Our main result shows in particular that when the target distribution is uniform, LMC mixes in O(n 7) steps (where n is the dimension). We also provide preliminary experimental evidence that LMC performs at least as well as hit-and-run, for which a better mixing time of O(n 4) was proved by Lovász and Vempala.
Subjects / KeywordsLangevin Monte Carlo algorithm; Stochastic Gradient Descent
Showing items related by title and author.