Sampling from a log-concave distribution with projected Langevin Monte Carlo

DOI10.1007/S00454-018-9992-1zbMATH Open1397.65010arXiv1507.02564OpenAlexW2963813262WikidataQ130021959 ScholiaQ130021959MaRDI QIDQ1650786FDOQ1650786

Authors: Sébastien Bubeck, Ronen Eldan, Joseph Lehec 

Publication date: 13 July 2018

Published in: Discrete \& Computational Geometry (Search for Journal in Brave)

Abstract: 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 $ildeO(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 $ildeO(n^4)$ was proved by Lov{'a}sz and Vempala.

Full work available at URL: https://arxiv.org/abs/1507.02564

Recommendations

• On sampling from a log-concave density using kinetic Langevin diffusions
• Sampling from log-concave distributions
• scientific article; zbMATH DE number 7415079
• Sampling from non-smooth distributions through Langevin diffusion
• Conditional path sampling of SDEs and the Langevin MCMC method
• Log-concave sampling: Metropolis-Hastings algorithms are fast
• Mixing of Hamiltonian Monte Carlo on strongly log-concave distributions: continuous dynamics
• Efficient sampling from time-varying log-concave distributions

zbMATH Keywords

log-concave measuresLangevin Monte Carlorapidly-mixing random walkssampling and optimization

Mathematics Subject Classification ID

Convergence of probability measures (60B10) Monte Carlo methods (65C05) Randomized algorithms (68W20) Approximation algorithms (68W25) Applications of operator theory in optimization, convex analysis, mathematical programming, economics (47N10)

Cites Work

• Markov chains and mixing times. With a chapter on ``Coupling from the past by James G. Propp and David B. Wilson.
• Exponential convergence of Langevin distributions and their discrete approximations
• A Stochastic Approximation Method
• Title not available (Why is that?)
• Stochastic differential equations with reflecting boundary condition in convex regions
• Title not available (Why is that?)
• A random polynomial-time algorithm for approximating the volume of convex bodies
• Hit-and-Run from a Corner
• Characterization of the law of the iterated logarithm in Banach spaces
• Representation formula for the entropy and functional inequalities
• Coupling of multidimensional diffusions by reflection
• Bypassing KLS: Gaussian cooling and an \(O^\ast(n^3)\) volume algorithm
• The geometry of logconcave functions and sampling algorithms
• Stochastic Minimization with Constant Step-Size: Asymptotic Laws
• Random walks on polytopes and an affine interior point method for linear programming

Cited In (38)

• Efficient Bayesian Computation for Low-Photon Imaging Problems
• The Langevin Monte Carlo algorithm in the non-smooth log-concave case
• Weak approximation of transformed stochastic gradient MCMC
• Analysis of Langevin Monte Carlo via convex optimization
• Title not available (Why is that?)
• On the privacy of noisy stochastic gradient descent for convex optimization
• Normalizing constants of log-concave densities
• Geodesic Walks in Polytopes
• Stability of the Prékopa-Leindler inequality for log-concave functions
• Oracle lower bounds for stochastic gradient sampling algorithms
• Stochastic zeroth-order discretizations of Langevin diffusions for Bayesian inference
• Constrained ensemble Langevin Monte Carlo
• Truncated log-concave sampling for convex bodies with reflective Hamiltonian Monte Carlo
• On stationary-point hitting time and ergodicity of stochastic gradient Langevin dynamics
• On stochastic gradient Langevin dynamics with dependent data streams in the logconcave case
• Stochastic gradient Markov chain Monte Carlo
• Kinetic Langevin MCMC sampling without gradient Lipschitz continuity -- the strongly convex case
• Convergence of Langevin MCMC in KL-divergence
• Title not available (Why is that?)
• Complexity of zigzag sampling algorithm for strongly log-concave distributions
• Lévy Langevin Monte Carlo
• Log-concave sampling: Metropolis-Hastings algorithms are fast
• Riemannian Langevin algorithm for solving semidefinite programs
• User-friendly guarantees for the Langevin Monte Carlo with inaccurate gradient
• Optimising portfolio diversification and dimensionality
• The forward-backward envelope for sampling with the overdamped Langevin algorithm
• Efficient sampling from time-varying log-concave distributions
• Sampling from non-smooth distributions through Langevin diffusion
• Ergodicity of supercritical SDEs driven by \(\alpha \)-stable processes and heavy-tailed sampling
• Simplest random walk for approximating Robin boundary value problems and ergodic limits of reflected diffusions
• Convergence error analysis of reflected gradient Langevin dynamics for non-convex constrained optimization
• On sampling from a log-concave density using kinetic Langevin diffusions
• Sampling from log-concave distributions
• Emerging directions in Bayesian computation
• Title not available (Why is that?)
• High-dimensional Bayesian inference via the unadjusted Langevin algorithm
• Higher order Langevin Monte Carlo algorithm
• (Non)-penalized multilevel methods for non-uniformly log-concave distributions

This page was built for publication: Sampling from a log-concave distribution with projected Langevin Monte Carlo

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1650786)