Efficient constrained sampling via the mirror-Langevin algorithm

Abstract

We propose a new discretization of the mirror-Langevin diffusion and give a crisp proof of its convergence. Our analysis uses relative convexity/smoothness and self-concordance, ideas which originated in convex optimization, together with a new result in optimal transport that generalizes the displacement convexity of the entropy. Unlike prior works, our result both (1) requires much weaker assumptions on the mirror map and the target distribution, and (2) has vanishing bias as the step size tends to zero. In particular, for the task of sampling from a log-concave distribution supported on a compact set, our theoretical results are significantly better than the existing guarantees.

arXiv comment26 pages, 4 figures

References in corpus (12)

• Underdamped Langevin MCMC: A non-asymptotic analysis
• Convergence of Langevin MCMC in KL-divergence
• Optimal scaling and diffusion limits for the Langevin algorithm in high dimensions
• Stochastic Quasi-Newton Langevin Monte Carlo
• Rapid Convergence of the Unadjusted Langevin Algorithm: Isoperimetry Suffices
• Exponential ergodicity of mirror-Langevin diffusions
• Proximal Langevin Algorithm: Rapid Convergence Under Isoperimetry
• Wasserstein Control of Mirror Langevin Monte Carlo
• Primal Dual Interpretation of the Proximal Stochastic Gradient Langevin Algorithm
• Information Newton's flow: second-order optimization method in probability space
• Mirrorless Mirror Descent: A Natural Derivation of Mirror Descent
• The Mirror Langevin Algorithm Converges with Vanishing Bias

Cited by in corpus (6)

• Sampling Constrained Continuous Probability Distributions: A Review
• The Mirror Langevin Algorithm Converges with Vanishing Bias
• KALE Flow: A Relaxed KL Gradient Flow for Probabilities with Disjoint Support
• Projected Stochastic Gradient Langevin Algorithms for Constrained Sampling and Non-Convex Learning
• A Particle-Based Algorithm for Distributional Optimization on \textit{Constrained Domains} via Variational Transport and Mirror Descent
• Sampling with Mirrored Stein Operators