mlsanityData to 7 Oct 2026

Fast parallel sampling under isoperimetry

arXiv 2401.09016 ↗First posted 17 Jan 2024cs.DS math.ST stat.MLcited by 12

Not on the map. Why?

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.

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

Builds on

11 of 25 references.

References · 11

  1. 2019Rapid Convergence of the Unadjusted Langevin Algorithm: Isoperimetry Sufficescited by 224
  2. 2017Underdamped Langevin MCMC: A non-asymptotic analysiscited by 131
  3. 2018Log-concave sampling: Metropolis-Hastings algorithms are fastcited by 117
  4. 2019The Randomized Midpoint Method for Log-Concave Samplingcited by 77
  5. 2018On sampling from a log-concave density using kinetic Langevin diffusionscited by 61
  6. 2023Faster high-accuracy log-concave sampling via algorithmic warm startscited by 44
  7. 2023Improved Discretization Analysis for Underdamped Langevin Monte Carlocited by 26
  8. 2019Learning Nonsymmetric Determinantal Point Processescited by 15
  9. 2021Fractionally Log-Concave and Sector-Stable Polynomials: Counting Planar Matchings and Morecited by 6
  10. 2020Sampling Arborescences in Parallelcited by 3
  11. 2020More on zeros and approximation of the Ising partition functioncited by 1

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2024: 5; 2025: 5; 2026: 2.

12 papers.

  1. 2025Fast Solvers for Discrete Diffusion Models: Theory and Applications of High-Order Algorithmscited by 47
  2. 2024Learning general Gaussian mixtures with efficient score matchingcited by 43
  3. 2024Accelerating Diffusion Models with Parallel Sampling: Inference at Sub-Linear Time Complexitycited by 42
  4. 2025Accelerated Diffusion Models via Speculative Samplingcited by 30
  5. 2024Faster Diffusion Sampling with Randomized Midpoints: Sequential and Parallelcited by 29
  6. 2025Complexity Analysis of Normalizing Constant Estimation: from Jarzynski Equality to Annealed Importance Sampling and beyondcited by 11
  7. 2024Parallelized Midpoint Randomization for Langevin Monte Carlocited by 9
  8. 2025Assessing the Quality of Denoising Diffusion Models in Wasserstein Distance: Noisy Score and Optimal Boundscited by 8
  9. 2025Predictability Enables Parallelization of Nonlinear State Space Modelscited by 7
  10. 2024Parallel Simulation for Log-concave Sampling and Score-based Diffusion Modelscited by 6
  11. 2026Accelerating Discrete Diffusion Models with Parallel-In-Time Samplingcited by 1
  12. 2026Generating Input Distributions for Explaining Portfolio Optimization Pipelinescited by 0