mlsanityData to 7 Oct 2026

Fast sampling from constrained spaces using the Metropolis-adjusted Mirror Langevin algorithm

arXiv 2312.08823 ↗First posted 14 Dec 2023stat.CO cs.DS cs.LGcited by 11

Not on the map. Why?

Abstract (arXiv)

We propose a new method called the Metropolis-adjusted Mirror Langevin algorithm for approximate sampling from distributions whose support is a compact and convex set. This algorithm adds an accept-reject filter to the Markov chain induced by a single step of the Mirror Langevin algorithm (Zhang et al., 2020), which is a basic discretisation of the Mirror Langevin dynamics. Due to the inclusion of this filter, our method is unbiased relative to the target, while known discretisations of the Mirror Langevin dynamics including the Mirror Langevin algorithm have an asymptotic bias. For this algorithm, we also give upper bounds for the number of iterations taken to mix to a constrained distribution whose potential is relatively smooth, convex, and Lipschitz continuous with respect to a self-concordant mirror function. As a consequence of the reversibility of the Markov chain induced by the inclusion of the Metropolis-Hastings filter, we obtain an exponentially better dependence on the error tolerance for approximate constrained sampling. We also present numerical experiments that corroborate our theoretical findings.

Key facts. Cited by 11 papers in the map (data through 7 Oct 2026). Builds on 35 of its 64 references that are in the map. First posted on arXiv 14 Dec 2023.

Builds on

35 of 64 references.

References · 35

  1. 2013Sinkhorn Distances: Lightspeed Computation of Optimal Transportation Distancescited by 2,277
  2. 2019Rapid Convergence of the Unadjusted Langevin Algorithm: Isoperimetry Sufficescited by 224
  3. 2014Theoretical guarantees for approximate sampling from smooth and log-concave densitiescited by 206
  4. 2015Non-asymptotic convergence analysis for the Unadjusted Langevin Algorithmcited by 195
  5. 2018Sampling as optimization in the space of measures: The Langevin dynamics as a composite optimization problemcited by 123
  6. 2018Log-concave sampling: Metropolis-Hastings algorithms are fastcited by 117
  7. 2017User-friendly guarantees for the Langevin Monte Carlo with inaccurate gradientcited by 116
  8. 2016Relatively-Smooth Convex Optimization by First-Order Methods, and Applicationscited by 108
  9. 2017Convergence of Langevin MCMC in KL-divergencecited by 86
  10. 2022Gradient-Based Constrained Sampling from Language Modelscited by 64
  11. 2018Mirrored Langevin Dynamicscited by 61
  12. 2020Optimal dimension dependence of the Metropolis-Adjusted Langevin Algorithmcited by 57
23 more
  1. 2020Wasserstein Control of Mirror Langevin Monte Carlocited by 55
  2. 2020Efficient constrained sampling via the mirror-Langevin algorithmcited by 55
  3. 2015Sampling from a log-concave distribution with Projected Langevin Monte Carlocited by 52
  4. 2017Sampling from a log-concave distribution with compact support with proximal Langevin Monte Carlocited by 43
  5. 2020Exponential ergodicity of mirror-Langevin diffusionscited by 37
  6. 2021The Mirror Langevin Algorithm Converges with Vanishing Biascited by 37
  7. 2018Coupling and Convergence for Hamiltonian Monte Carlocited by 36
  8. 2019Stochastic Runge-Kutta Accelerates Langevin Monte Carlo and Beyondcited by 33
  9. 2017Convergence Rate of Riemannian Hamiltonian Monte Carlo and Faster Polytope Volume Computationcited by 32
  10. 2022Sampling with Riemannian Hamiltonian Monte Carlo in a Constrained Spacecited by 28
  11. 2021Sqrt(d) Dimension Dependence of Langevin Monte Carlocited by 25
  12. 2022Convergence of the Riemannian Langevin Algorithmcited by 23
  13. 2020Riemannian Langevin Algorithm for Solving Semidefinite Programscited by 22
  14. 2017Fast MCMC sampling algorithms on polytopescited by 17
  15. 2022Alternating Mirror Descent for Constrained Min-Max Gamescited by 13
  16. 2019Strong Self-Concordance and Samplingcited by 11
  17. 2022Condition-number-independent convergence rate of Riemannian Hamiltonian Monte Carlo with numerical integratorscited by 10
  18. 2023Algorithmic Aspects of the Log-Laplace Transform and a Non-Euclidean Proximal Samplercited by 9
  19. 2013Efficient Sampling from Time-Varying Log-Concave Distributionscited by 7
  20. 2015The Mixing Time of the Dikin Walk in a Polytope - A Simple Proofcited by 7
  21. 2023Sampling with Barriers: Faster Mixing via Lewis Weightscited by 7
  22. 2022Unbiased constrained sampling with Self-Concordant Barrier Hamiltonian Monte Carlocited by 6
  23. 2018John's Walkcited by 3

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2024: 6; 2025: 2; 2026: 3.

11 papers.

  1. 2024In-and-Out: Algorithmic Diffusion for Sampling Convex Bodiescited by 18
  2. 2024Mirror and Preconditioned Gradient Descent in Wasserstein Spacecited by 11
  3. 2024Constrained Sampling with Primal-Dual Langevin Monte Carlocited by 10
  4. 2024R'enyi-infinity constrained sampling with d3 membership queriescited by 3
  5. 2025Mirror Mean-Field Langevin Dynamicscited by 3
  6. 2025Oracle-based Uniform Sampling from Convex Bodiescited by 3
  7. 2024Randomized Midpoint Method for Log-Concave Sampling under Constraintscited by 2
  8. 2026Polynomial Convergence of Riemannian Diffusion Modelscited by 2
  9. 2024Log-Concave Coupling for Sampling Neural Net Posteriorscited by 0
  10. 2026Functional Stochastic Localizationcited by 0
  11. 2026Generating Physically Consistent Molecules with Energy-Based Modelscited by 0