# Fast parallel sampling under isoperimetry

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

## Key facts

- Cited by 12 papers in the map (data through 14 Oct 2026).
- Builds on 11 of its 25 references that are in the map.
- First posted on arXiv 17 Jan 2024.

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

- [Rapid Convergence of the Unadjusted Langevin Algorithm: Isoperimetry Suffices](https://mlsanity.com/paper/1903.08568/) (2019)
- [Underdamped Langevin MCMC: A non-asymptotic analysis](https://mlsanity.com/paper/1707.03663/) (2017)
- [Log-concave sampling: Metropolis-Hastings algorithms are fast](https://mlsanity.com/paper/1801.02309/) (2018)
- [The Randomized Midpoint Method for Log-Concave Sampling](https://mlsanity.com/paper/1909.05503/) (2019)
- [On sampling from a log-concave density using kinetic Langevin diffusions](https://mlsanity.com/paper/1807.09382/) (2018)
- [Faster high-accuracy log-concave sampling via algorithmic warm starts](https://mlsanity.com/paper/2302.10249/) (2023)
- [Improved Discretization Analysis for Underdamped Langevin Monte Carlo](https://mlsanity.com/paper/2302.08049/) (2023)
- [Learning Nonsymmetric Determinantal Point Processes](https://mlsanity.com/paper/1905.12962/) (2019)
- [Fractionally Log-Concave and Sector-Stable Polynomials: Counting Planar Matchings and More](https://mlsanity.com/paper/2102.02708/) (2021)
- [Sampling Arborescences in Parallel](https://mlsanity.com/paper/2012.09502/) (2020)
- [More on zeros and approximation of the Ising partition function](https://mlsanity.com/paper/2005.11232/) (2020)

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

- [Fast Solvers for Discrete Diffusion Models: Theory and Applications of High-Order Algorithms](https://mlsanity.com/paper/2502.00234/) (2025)
- [Learning general Gaussian mixtures with efficient score matching](https://mlsanity.com/paper/2404.18893/) (2024)
- [Accelerating Diffusion Models with Parallel Sampling: Inference at Sub-Linear Time Complexity](https://mlsanity.com/paper/2405.15986/) (2024)
- [Accelerated Diffusion Models via Speculative Sampling](https://mlsanity.com/paper/2501.05370/) (2025)
- [Faster Diffusion Sampling with Randomized Midpoints: Sequential and Parallel](https://mlsanity.com/paper/2406.00924/) (2024)
- [Complexity Analysis of Normalizing Constant Estimation: from Jarzynski Equality to Annealed Importance Sampling and beyond](https://mlsanity.com/paper/2502.04575/) (2025)
- [Parallelized Midpoint Randomization for Langevin Monte Carlo](https://mlsanity.com/paper/2402.14434/) (2024)
- [Assessing the Quality of Denoising Diffusion Models in Wasserstein Distance: Noisy Score and Optimal Bounds](https://mlsanity.com/paper/2506.09681/) (2025)
- [Predictability Enables Parallelization of Nonlinear State Space Models](https://mlsanity.com/paper/2508.16817/) (2025)
- [Parallel Simulation for Log-concave Sampling and Score-based Diffusion Models](https://mlsanity.com/paper/2412.07435/) (2024)
- [Accelerating Discrete Diffusion Models with Parallel-In-Time Sampling](https://mlsanity.com/paper/2607.00773/) (2026)
- [Generating Input Distributions for Explaining Portfolio Optimization Pipelines](https://mlsanity.com/paper/2606.25808/) (2026)

## Abstract (arXiv)

We show how to sample in parallel from a distribution π over mathbb Rd that satisfies a log-Sobolev inequality and has a smooth log-density, by parallelizing the Langevin (resp. underdamped Langevin) algorithms. We show that our algorithm outputs samples from a distribution hatπ that is close to π in Kullback--Leibler (KL) divergence (resp. total variation (TV) distance), while using only log(d)O(1) parallel rounds and widetildeO(d) (resp. widetilde O(√ d)) gradient evaluations in total. This constitutes the first parallel sampling algorithms with TV distance guarantees. For our main application, we show how to combine the TV distance guarantees of our algorithms with prior works and obtain RNC sampling-to-counting reductions for families of discrete distribution on the hypercube ± 1n that are closed under exponential tilts and have bounded covariance. Consequently, we obtain an RNC sampler for directed Eulerian tours and asymmetric determinantal point processes, resolving open questions raised in prior works.