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

arXiv: https://arxiv.org/abs/2405.01425 · HTML: https://mlsanity.com/paper/2405.01425/

## Key facts

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

## Builds on (most cited first, 22 of 22)

- [Renyi Differential Privacy](https://mlsanity.com/paper/1702.07476/) (2017)
- [Pyro: Deep Universal Probabilistic Programming](https://mlsanity.com/paper/1810.09538/) (2018)
- [Rapid Convergence of the Unadjusted Langevin Algorithm: Isoperimetry Suffices](https://mlsanity.com/paper/1903.08568/) (2019)
- [Analysis of Langevin Monte Carlo via convex optimization](https://mlsanity.com/paper/1802.09188/) (2018)
- [Structured Logconcave Sampling with a Restricted Gaussian Oracle](https://mlsanity.com/paper/2010.03106/) (2020)
- [Improved analysis for a proximal algorithm for sampling](https://mlsanity.com/paper/2202.06386/) (2022)
- [Wasserstein Control of Mirror Langevin Monte Carlo](https://mlsanity.com/paper/2002.04363/) (2020)
- [Efficient constrained sampling via the mirror-Langevin algorithm](https://mlsanity.com/paper/2010.16212/) (2020)
- [Sampling from a log-concave distribution with Projected Langevin Monte Carlo](https://mlsanity.com/paper/1507.02564/) (2015)
- [Sampling from a log-concave distribution with compact support with proximal Langevin Monte Carlo](https://mlsanity.com/paper/1705.08964/) (2017)
- [The Mirror Langevin Algorithm Converges with Vanishing Bias](https://mlsanity.com/paper/2109.12077/) (2021)
- [Convergence Rate of Riemannian Hamiltonian Monte Carlo and Faster Polytope Volume Computation](https://mlsanity.com/paper/1710.06261/) (2017)
- [Improved dimension dependence of a proximal algorithm for sampling](https://mlsanity.com/paper/2302.10081/) (2023)
- [Sampling with Riemannian Hamiltonian Monte Carlo in a Constrained Space](https://mlsanity.com/paper/2202.01908/) (2022)
- [The Langevin Monte Carlo algorithm in the non-smooth log-concave case](https://mlsanity.com/paper/2101.10695/) (2021)
- [Eldan's Stochastic Localization and the KLS Conjecture: Isoperimetry, Concentration and Mixing](https://mlsanity.com/paper/1612.01507/) (2016)
- [Penalized Overdamped and Underdamped Langevin Monte Carlo Algorithms for Constrained Sampling](https://mlsanity.com/paper/2212.00570/) (2022)
- [Fast sampling from constrained spaces using the Metropolis-adjusted Mirror Langevin algorithm](https://mlsanity.com/paper/2312.08823/) (2023)
- [Condition-number-independent convergence rate of Riemannian Hamiltonian Monte Carlo with numerical integrators](https://mlsanity.com/paper/2210.07219/) (2022)
- [Algorithmic Aspects of the Log-Laplace Transform and a Non-Euclidean Proximal Sampler](https://mlsanity.com/paper/2302.06085/) (2023)
- [Reducing Isotropy and Volume to KLS: Faster Rounding and Volume Algorithms](https://mlsanity.com/paper/2008.02146/) (2020)
- [Sampling with Barriers: Faster Mixing via Lewis Weights](https://mlsanity.com/paper/2303.00480/) (2023)

## Built on by (most cited first, 19 of 19)

- [Sampling and Integration of Logconcave Functions by Algorithmic Diffusion](https://mlsanity.com/paper/2411.13462/) (2024)
- [Mixing Time of the Proximal Sampler in Relative Fisher Information via Strong Data Processing Inequality](https://mlsanity.com/paper/2502.05623/) (2025)
- [Fast Convergence of Phi-Divergence Along the Unadjusted Langevin Algorithm and Proximal Sampler](https://mlsanity.com/paper/2410.10699/) (2024)
- [Complexity Analysis of Normalizing Constant Estimation: from Jarzynski Equality to Annealed Importance Sampling and beyond](https://mlsanity.com/paper/2502.04575/) (2025)
- [Faster logconcave sampling from a cold start in high dimension](https://mlsanity.com/paper/2505.01937/) (2025)
- [R'enyi-infinity constrained sampling with d3 membership queries](https://mlsanity.com/paper/2407.12967/) (2024)
- [Oracle-based Uniform Sampling from Convex Bodies](https://mlsanity.com/paper/2510.02983/) (2025)
- [A unified complexity bound for logconcave sampling](https://mlsanity.com/paper/2606.12694/) (2026)
- [Randomized Midpoint Method for Log-Concave Sampling under Constraints](https://mlsanity.com/paper/2405.15379/) (2024)
- [Covariance estimation using Markov chain Monte Carlo](https://mlsanity.com/paper/2410.17147/) (2024)
- [Beyond the d2.5-mixing bound for Dikin walks on polytopes](https://mlsanity.com/paper/2607.13943/) (2026)
- [Spectral Gaps of Hit-and-Run and Coordinate Hit-and-Run](https://mlsanity.com/paper/2608.16878/) (2026)
- [Alternating Diffusion for Proximal Sampling with Zeroth Order Queries](https://mlsanity.com/paper/2603.19633/) (2026)
- [A proximal gradient algorithm for composite log-concave sampling](https://mlsanity.com/paper/2605.12461/) (2026)
- [Ballistic Convergence in Hit-and-Run Monte Carlo and a Coordinate-free Randomized Kaczmarz Algorithm](https://mlsanity.com/paper/2412.07643/) (2024)
- [The Geometry of Efficient Nonconvex Sampling](https://mlsanity.com/paper/2603.25622/) (2026)
- [On two proofs of d2 mixing of weighted Dikin walks](https://mlsanity.com/paper/2608.28566/) (2026)
- [Thin-shell stability of Gaussian cooling: logconcave sampling with sesteric complexity from a cold start](https://mlsanity.com/paper/2609.15884/) (2026)
- [Reflected Proximal Dynamics for Accelerated High-Accuracy Log-Concave Sampling](https://mlsanity.com/paper/2610.16248/) (2026)

## 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.