• xmlui.mirage2.page-structure.header.title
    • français
    • English
  • Help
  • Login
  • Language 
    • Français
    • English
View Item 
  •   BIRD Home
  • CEREMADE (UMR CNRS 7534)
  • CEREMADE : Publications
  • View Item
  •   BIRD Home
  • CEREMADE (UMR CNRS 7534)
  • CEREMADE : Publications
  • View Item
JavaScript is disabled for your browser. Some features of this site may not work without it.

Browse

BIRDResearch centres & CollectionsBy Issue DateAuthorsTitlesTypeThis CollectionBy Issue DateAuthorsTitlesType

My Account

LoginRegister

Statistics

Most Popular ItemsStatistics by CountryMost Popular Authors
Thumbnail

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
sampling.pdf (336.5Kb)
Type
Article accepté pour publication ou publié
Date
2018
Journal name
Discrete and Computational Geometry
Volume
59
Number
4
Publisher
Springer
Pages
757–783
Publication identifier
10.1007/s00454-018-9992-1
Metadata
Show full item record
Author(s)
Bubeck, Sébastien
Microsoft Corporation [Redmond]
Eldan, Ronen
The Weizmann Institute of Science
Lehec, Joseph cc
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 walks

Related items

Showing items related by title and author.

  • Thumbnail
    Sampling from a log-concave distribution with Projected Langevin Monte Carlo 
    Bubeck, Sébastien; Eldan, Ronen; Lehec, Joseph (2017) Document de travail / Working paper
  • Thumbnail
    The Langevin Monte Carlo algorithm in the non-smooth log-concave case 
    Lehec, Joseph (2021) Document de travail / Working paper
  • Thumbnail
    Bounding the Norm of a Log-Concave Vector Via Thin-Shell Estimates 
    Eldan, Ronen; Lehec, Joseph (2014) Chapitre d'ouvrage
  • Thumbnail
    Poisson processes and a log-concave Bernstein theorem 
    Klartag, Bo'az; Lehec, Joseph (2019) Article accepté pour publication ou publié
  • Thumbnail
    Circular law for random matrices with unconditional log-concave distribution 
    Adamczak, Radosław; Chafaï, Djalil (2015) Article accepté pour publication ou publié
Dauphine PSL Bibliothèque logo
Place du Maréchal de Lattre de Tassigny 75775 Paris Cedex 16
Phone: 01 44 05 40 94
Contact
Dauphine PSL logoEQUIS logoCreative Commons logo