Show simple item record

hal.structure.identifierMicrosoft Corporation [Redmond]
dc.contributor.authorBubeck, Sébastien
hal.structure.identifierThe Weizmann Institute of Science
dc.contributor.authorEldan, Ronen
hal.structure.identifierCEntre de REcherches en MAthématiques de la DEcision [CEREMADE]
dc.contributor.authorLehec, Joseph
HAL ID: 11520
ORCID: 0000-0001-6182-9427
dc.date.accessioned2018-09-12T08:16:03Z
dc.date.available2018-09-12T08:16:03Z
dc.date.issued2018
dc.identifier.issn0179-5376
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/17998
dc.language.isoenen
dc.subjectLangevin Monte Carlo algorithmen
dc.subjectStochastic Gradient Descenten
dc.subjectSampling and optimizationen
dc.subjectLog-concave measuresen
dc.subjectRapidly-mixing random walksen
dc.subject.ddc519en
dc.titleSampling from a log-concave distribution with Projected Langevin Monte Carloen
dc.typeArticle accepté pour publication ou publié
dc.description.abstractenWe 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.en
dc.relation.isversionofjnlnameDiscrete and Computational Geometry
dc.relation.isversionofjnlvol59en
dc.relation.isversionofjnlissue4en
dc.relation.isversionofjnldate2018-06
dc.relation.isversionofjnlpages757–783en
dc.relation.isversionofdoi10.1007/s00454-018-9992-1en
dc.relation.isversionofjnlpublisherSpringeren
dc.subject.ddclabelProbabilités et mathématiques appliquéesen
dc.relation.forthcomingnonen
dc.relation.forthcomingprintnonen
dc.description.ssrncandidatenonen
dc.description.halcandidatenonen
dc.description.readershiprechercheen
dc.description.audienceInternationalen
dc.relation.Isversionofjnlpeerreviewedouien
dc.relation.Isversionofjnlpeerreviewedouien
dc.date.updated2018-06-27T12:04:34Z
hal.author.functionaut
hal.author.functionaut
hal.author.functionaut


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record