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

DOI10.1007/S00454-018-9992-1MaRDI QIDQ1650786zbMATH OpenOpenAlexWikidataFDO

Authors Sébastien Bubeck, Ronen Eldan, Joseph Lehec

Publication date 13 July 2018

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

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

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)

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.

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

Cites work

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

Cited in

(38)

• (Non)-penalized multilevel methods for non-uniformly log-concave distributions
• Efficient Bayesian Computation for Low-Photon Imaging Problems
• Weak approximation of transformed stochastic gradient MCMC
• The Langevin Monte Carlo algorithm in the non-smooth log-concave case
• Analysis of Langevin Monte Carlo via convex optimization
• scientific article; zbMATH DE number 7415079 (Why is no real title available?)
• Normalizing constants of log-concave densities
• On the privacy of noisy stochastic gradient descent for convex optimization
• 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
• Complexity of zigzag sampling algorithm for strongly log-concave distributions
• Convergence of Langevin MCMC in KL-divergence
• scientific article; zbMATH DE number 7415116 (Why is no real title available?)
• Lévy Langevin Monte Carlo
• Log-concave sampling: Metropolis-Hastings algorithms are fast
• User-friendly guarantees for the Langevin Monte Carlo with inaccurate gradient
• Riemannian Langevin algorithm for solving semidefinite programs
• 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
• On sampling from a log-concave density using kinetic Langevin diffusions
• Sampling from log-concave distributions
• Convergence error analysis of reflected gradient Langevin dynamics for non-convex constrained optimization
• Emerging directions in Bayesian computation
• scientific article; zbMATH DE number 7626754 (Why is no real title available?)
• High-dimensional Bayesian inference via the unadjusted Langevin algorithm
• Higher order Langevin Monte Carlo algorithm

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)