Efficient constrained sampling via the mirror-Langevin algorithm

2020/10/30 by Kwangjun Ahn, Ahn, Kwangjun, Sinho Chewi +1 · 14 citations
Biochemistry, Genetics and Molecular Biology · Computer Science · Engineering · Mathematics · #Algorithm #Applied mathematics #Computer science #Computer vision #Convexity #Diffusion and Search Dynamics #Discretization #Distribution (mathematics) #FOS: Computer and information sciences #FOS: Mathematics #Geometry #Kullback–Leibler divergence #Langevin dynamics #Machine Learning (cs.LG) #Markov Chains and Monte Carlo Methods #Mathematical analysis #Mathematical optimization #Mathematics #Regular polygon #Sampling (signal processing) #Smoothness #Sparse and Compressive Sensing Techniques #Statistics #Statistics Theory (math.ST) #cs.LG #math.ST #stat.TH

paper · pdf · doi:10.48550/arxiv.2010.16212

published in arXiv (Cornell University) 34 (Cornell University) · 26 pages, 4 figures

openalex publication_date 2020/10/30 · arxiv created 2021/10/25 · arxiv updated 2021/10/26 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05

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.

Citations

• Exact Hamiltonian Monte Carlo for Truncated Multivariate Gaussians
• Generalization of an Inequality by Talagrand and Links with the Logarithmic Sobolev Inequality
• Sampling as optimization in the space of measures: The Langevin dynamics as a composite optimization problem
• Proximal Langevin Algorithm: Rapid Convergence Under Isoperimetry
• Rapid Convergence of the Unadjusted Langevin Algorithm: Isoperimetry Suffices
• Information Newton's flow: second-order optimization method in probability space
• Wasserstein Control of Mirror Langevin Monte Carlo
• The Mirror Langevin Algorithm Converges with Vanishing Bias

Cited by

• Mirror Langevin diffusions: Convergence rates and Markov chain approximations
• Diffusion Approximations to Schrödinger Bridges on Manifolds
• Self-concordant Schrödinger operators: spectral gaps and optimization without condition numbers
• Constrained Dikin-Langevin diffusion for polyhedra
• Oracle-based Uniform Sampling from Convex Bodies
• Accelerating Constrained Sampling: A Large Deviations Approach
• Constrained Diffusers for Safe Planning and Control
• Bregman Centroid Guided Cross-Entropy Method
• Mirror Mean-Field Langevin Dynamics
• Strictly Constrained Generative Modeling via Split Augmented Langevin Sampling
• Sampling with Mirrored Stein Operators
• Projected Stochastic Gradient Langevin Algorithms for Constrained Sampling and Non-Convex Learning
• Mean Estimation from Coarse Data: Characterizations and Efficient Algorithms
• Exact simulation of diffusions and improved algorithms for log-concave sampling

Related

• Fast sampling from constrained spaces using the Metropolis-adjusted Mirror Langevin algorithm
• The Mirror Langevin Algorithm Converges with Vanishing Bias
• Exponential ergodicity of mirror-Langevin diffusions
• Mirrored Langevin Dynamics
• Resolving the Mixing Time of the Langevin Algorithm to its Stationary Distribution for Log-Concave Sampling