
Sampling from a log-concave distribution with Projected Langevin Monte Carlo
Bubeck, Sébastien; Eldan, Ronen; Lehec, Joseph (2018), Sampling from a log-concave distribution with Projected Langevin Monte Carlo, Discrete and Computational Geometry, 59, 4, p. 757–783. 10.1007/s00454-018-9992-1
View/ Open
Type
Article accepté pour publication ou publiéDate
2018Journal name
Discrete and Computational GeometryVolume
59Number
4Publisher
Springer
Pages
757–783
Publication identifier
Metadata
Show full item recordAuthor(s)
Bubeck, SébastienMicrosoft Corporation [Redmond]
Eldan, Ronen
The Weizmann Institute of Science
Lehec, Joseph

CEntre de REcherches en MAthématiques de la DEcision [CEREMADE]
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 / Keywords
Langevin Monte Carlo algorithm; Stochastic Gradient Descent; Sampling and optimization; Log-concave measures; Rapidly-mixing random walksRelated items
Showing items related by title and author.
-
Bubeck, Sébastien; Eldan, Ronen; Lehec, Joseph (2017) Document de travail / Working paper
-
Lehec, Joseph (2021) Document de travail / Working paper
-
Eldan, Ronen; Lehec, Joseph (2014) Chapitre d'ouvrage
-
Klartag, Bo'az; Lehec, Joseph (2019) Article accepté pour publication ou publié
-
Adamczak, Radosław; Chafaï, Djalil (2015) Article accepté pour publication ou publié