mlsanityData to 7 Oct 2026

In-and-Out: Algorithmic Diffusion for Sampling Convex Bodies

arXiv 2405.01425 ↗First posted 2 May 2024cs.DS cs.LG math.STcited by 18

Not on the map. Why?

Abstract (arXiv)

We present a new random walk for uniformly sampling high-dimensional convex bodies. It achieves state-of-the-art runtime complexity with stronger guarantees on the output than previously known, namely in R'enyi divergence (which implies TV, W2, KL, chi2). The proof departs from known approaches for polytime algorithms for the problem -- we utilize a stochastic diffusion perspective to show contraction to the target distribution with the rate of convergence determined by functional isoperimetric constants of the target distribution.

Key facts. Cited by 18 papers in the map (data through 7 Oct 2026). Builds on 22 of its 84 references that are in the map. First posted on arXiv 2 May 2024.

Builds on

22 of 84 references.

References · 22

  1. 2017Renyi Differential Privacycited by 643
  2. 2018Pyro: Deep Universal Probabilistic Programmingcited by 379
  3. 2019Rapid Convergence of the Unadjusted Langevin Algorithm: Isoperimetry Sufficescited by 224
  4. 2018Analysis of Langevin Monte Carlo via convex optimizationcited by 126
  5. 2020Structured Logconcave Sampling with a Restricted Gaussian Oraclecited by 85
  6. 2022Improved analysis for a proximal algorithm for samplingcited by 72
  7. 2020Wasserstein Control of Mirror Langevin Monte Carlocited by 55
  8. 2020Efficient constrained sampling via the mirror-Langevin algorithmcited by 55
  9. 2015Sampling from a log-concave distribution with Projected Langevin Monte Carlocited by 52
  10. 2017Sampling from a log-concave distribution with compact support with proximal Langevin Monte Carlocited by 43
  11. 2021The Mirror Langevin Algorithm Converges with Vanishing Biascited by 37
  12. 2017Convergence Rate of Riemannian Hamiltonian Monte Carlo and Faster Polytope Volume Computationcited by 32
10 more
  1. 2023Improved dimension dependence of a proximal algorithm for samplingcited by 29
  2. 2022Sampling with Riemannian Hamiltonian Monte Carlo in a Constrained Spacecited by 28
  3. 2021The Langevin Monte Carlo algorithm in the non-smooth log-concave casecited by 26
  4. 2016Eldan's Stochastic Localization and the KLS Conjecture: Isoperimetry, Concentration and Mixingcited by 13
  5. 2022Penalized Overdamped and Underdamped Langevin Monte Carlo Algorithms for Constrained Samplingcited by 13
  6. 2023Fast sampling from constrained spaces using the Metropolis-adjusted Mirror Langevin algorithmcited by 11
  7. 2022Condition-number-independent convergence rate of Riemannian Hamiltonian Monte Carlo with numerical integratorscited by 10
  8. 2020Reducing Isotropy and Volume to KLS: Faster Rounding and Volume Algorithmscited by 9
  9. 2023Algorithmic Aspects of the Log-Laplace Transform and a Non-Euclidean Proximal Samplercited by 9
  10. 2023Sampling with Barriers: Faster Mixing via Lewis Weightscited by 7

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2024: 6; 2025: 4; 2026: 8.

18 papers.

Sort:

  1. 2024Sampling and Integration of Logconcave Functions by Algorithmic Diffusioncited by 12
  2. 2025Complexity Analysis of Normalizing Constant Estimation: from Jarzynski Equality to Annealed Importance Sampling and beyondcited by 11
  3. 2025Mixing Time of the Proximal Sampler in Relative Fisher Information via Strong Data Processing Inequalitycited by 11
  4. 2024Fast Convergence of Phi-Divergence Along the Unadjusted Langevin Algorithm and Proximal Samplercited by 10
  5. 2025Faster logconcave sampling from a cold start in high dimensioncited by 7
  6. 2024R'enyi-infinity constrained sampling with d3 membership queriescited by 3
  7. 2025Oracle-based Uniform Sampling from Convex Bodiescited by 3
  8. 2026A unified complexity bound for logconcave samplingcited by 3
  9. 2024Randomized Midpoint Method for Log-Concave Sampling under Constraintscited by 2
  10. 2024Covariance estimation using Markov chain Monte Carlocited by 2
  11. 2026Spectral Gaps of Hit-and-Run and Coordinate Hit-and-Runcited by 2
  12. 2026Alternating Diffusion for Proximal Sampling with Zeroth Order Queriescited by 1
6 more
  1. 2026A proximal gradient algorithm for composite log-concave samplingcited by 1
  2. 2026Beyond the d2.5-mixing bound for Dikin walks on polytopescited by 1
  3. 2024Ballistic Convergence in Hit-and-Run Monte Carlo and a Coordinate-free Randomized Kaczmarz Algorithmcited by 0
  4. 2026The Geometry of Efficient Nonconvex Samplingcited by 0
  5. 2026On two proofs of d2 mixing of weighted Dikin walkscited by 0
  6. 2026Thin-shell stability of Gaussian cooling: logconcave sampling with sesteric complexity from a cold startcited by 0