mlsanityData to 7 Oct 2026

The Randomized Midpoint Method for Log-Concave Sampling

arXiv 1909.05503 ↗First posted 12 Sep 2019cs.LG cs.DS math.PRcited by 77

Not on the map. Why?

Abstract (arXiv)

Sampling from log-concave distributions is a well researched problem that has many applications in statistics and machine learning. We study the distributions of the form p*proptoexp(-f(x)), where f:ℝdrightarrowℝ has an L-Lipschitz gradient and is m-strongly convex. In our paper, we propose a Markov chain Monte Carlo (MCMC) algorithm based on the underdamped Langevin diffusion (ULD). It can achieve ε· D error (in 2-Wasserstein distance) in tildeOleft(kappa7/6/ε1/3+kappa/ε2/3right) steps, where Doversetdef=√fracdm is the effective diameter of the problem and kappaoversetdef=fracLm is the condition number. Our algorithm performs significantly faster than the previously best known algorithm for solving this problem, which requires tildeOleft(kappa1.5/εright) steps. Moreover, our algorithm can be easily parallelized to require only O(kappalogfrac1ε) parallel steps. To solve the sampling problem, we propose a new framework to discretize stochastic differential equations. We apply this framework to discretize and simulate ULD, which converges to the target distribution p*. The framework can be used to solve not only the log-concave sampling problem, but any problem that involves simulating (stochastic) differential equations.

Key facts. Cited by 77 papers in the map (data through 7 Oct 2026). First posted on arXiv 12 Sep 2019.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 10; 2022: 12; 2023: 16; 2024: 18; 2025: 16; 2026: 5.

77 papers.

Sort:

By area:

  1. 2022Sampling is as easy as learning the score: theory for diffusion models with minimal data assumptionscited by 440
  2. 2023Parallel Sampling of Diffusion Modelscited by 112
  3. 2022Variational inference via Wasserstein gradient flowscited by 84
  4. 2022Private Convex Optimization via Exponential Mechanismcited by 47
  5. 2025Fast Solvers for Discrete Diffusion Models: Theory and Applications of High-Order Algorithmscited by 47
  6. 2023Faster high-accuracy log-concave sampling via algorithmic warm startscited by 44
  7. 2021ScoreGrad: Multivariate Probabilistic Time Series Forecasting with Continuous Energy-based Generative Modelscited by 42
  8. 2024Accelerating Diffusion Models with Parallel Sampling: Inference at Sub-Linear Time Complexitycited by 42
  9. 2023Towards a Complete Analysis of Langevin Monte Carlo: Beyond Poincar'e Inequalitycited by 31
  10. 2025Accelerated Diffusion Models via Speculative Samplingcited by 30
  11. 2023Improved dimension dependence of a proximal algorithm for samplingcited by 29
  12. 2024Faster Diffusion Sampling with Randomized Midpoints: Sequential and Parallelcited by 29
38 more
  1. 2022Sampling with Riemannian Hamiltonian Monte Carlo in a Constrained Spacecited by 28
  2. 2025Beyond Log-Concavity and Score Regularity: Improved Convergence Bounds for Score-Based Generative Models in W2-distancecited by 27
  3. 2023Improved Discretization Analysis for Underdamped Langevin Monte Carlocited by 26
  4. 2021Sqrt(d) Dimension Dependence of Langevin Monte Carlocited by 25
  5. 2021A Proximal Algorithm for Sampling from Non-smooth Potentialscited by 23
  6. 2021A Convergence Theory for SVGD in the Population Limit under Talagrand's Inequality T1cited by 21
  7. 2022A Proximal Algorithm for Samplingcited by 21
  8. 2022Resolving the Mixing Time of the Langevin Algorithm to its Stationary Distribution for Log-Concave Samplingcited by 21
  9. 2023Sampling via Gradient Flows in the Space of Probability Measurescited by 20
  10. 2021Lower Bounds on Metropolized Sampling Methods for Well-Conditioned Distributionscited by 19
  11. 2024Zeroth-Order Sampling Methods for Non-Log-Concave Distributions: Alleviating Metastability by Denoising Diffusioncited by 19
  12. 2021The query complexity of sampling from strongly log-concave distributions in one dimensioncited by 18
  13. 2022Convergence of Stein Variational Gradient Descent under a Weaker Smoothness Conditioncited by 16
  14. 2021On Convergence of Federated Averaging Langevin Dynamicscited by 14
  15. 2023Chain of Log-Concave Markov Chainscited by 13
  16. 2024Error bounds for particle gradient descent, and extensions of the log-Sobolev and Talagrand inequalitiescited by 13
  17. 2021When is the Convergence Time of Langevin Algorithms Dimension Independent? A Composite Optimization Viewpointcited by 12
  18. 2023Query lower bounds for log-concave samplingcited by 12
  19. 2023When does Metropolized Hamiltonian Monte Carlo provably outperform Metropolis-adjusted Langevin algorithm?cited by 12
  20. 2024Fast parallel sampling under isoperimetrycited by 12
  21. 2022Condition-number-independent convergence rate of Riemannian Hamiltonian Monte Carlo with numerical integratorscited by 10
  22. 2023Langevin Monte Carlo for strongly log-concave distributions: Randomized midpoint revisitedcited by 10
  23. 2023Algorithmic Aspects of the Log-Laplace Transform and a Non-Euclidean Proximal Samplercited by 9
  24. 2023Accelerating optimization over the space of probability measurescited by 9
  25. 2024Parallelized Midpoint Randomization for Langevin Monte Carlocited by 9
  26. 2024GIST: Gibbs self-tuning for locally adaptive Hamiltonian Monte Carlocited by 9
  27. 2021Wasserstein distance estimates for the distributions of numerical approximations to ergodic stochastic differential equationscited by 8
  28. 2022Quantum Algorithms for Sampling Log-Concave Distributions and Estimating Normalizing Constantscited by 8
  29. 2022Unadjusted Hamiltonian MCMC with Stratified Monte Carlo Time Integrationcited by 8
  30. 2025Assessing the Quality of Denoising Diffusion Models in Wasserstein Distance: Noisy Score and Optimal Boundscited by 8
  31. 2024Sampling from the Mean-Field Stationary Distributioncited by 7
  32. 2025Sublinear iterations can suffice even for DDPMscited by 7
  33. 2022Heavy-tailed Sampling via Transformed Unadjusted Langevin Algorithmcited by 6
  34. 2024The Poisson Midpoint Method for Langevin Dynamics: Provably Efficient Discretization for Diffusion Modelscited by 6
  35. 2024Parallel Simulation for Log-concave Sampling and Score-based Diffusion Modelscited by 6
  36. 2023Universal Smoothed Score Functions for Generative Modelingcited by 5
  37. 2024A Separation in Heavy-Tailed Sampling: Gaussian vs. Stable Oracles for Proximal Samplerscited by 5
  38. 2025On the query complexity of sampling from non-log-concave distributionscited by 5

50 most cited of 77 All 77 (JSON)