# Faster high-accuracy log-concave sampling via algorithmic warm starts

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

## Key facts

- Cited by 45 papers in the map (data through 14 Oct 2026).
- Builds on 48 of its 101 references that are in the map.
- First posted on arXiv 20 Feb 2023.

## Builds on (most cited first, 30 of 48)

- [Deep Learning with Differential Privacy](https://mlsanity.com/paper/1607.00133/) (2016)
- [Renyi Differential Privacy](https://mlsanity.com/paper/1702.07476/) (2017)
- [Sampling is as easy as learning the score: theory for diffusion models with minimal data assumptions](https://mlsanity.com/paper/2209.11215/) (2022)
- [Rapid Convergence of the Unadjusted Langevin Algorithm: Isoperimetry Suffices](https://mlsanity.com/paper/1903.08568/) (2019)
- [Private Stochastic Convex Optimization: Optimal Rates in Linear Time](https://mlsanity.com/paper/2005.04763/) (2020)
- [Concentrated Differential Privacy](https://mlsanity.com/paper/1603.01887/) (2016)
- [Underdamped Langevin MCMC: A non-asymptotic analysis](https://mlsanity.com/paper/1707.03663/) (2017)
- [Sampling as optimization in the space of measures: The Langevin dynamics as a composite optimization problem](https://mlsanity.com/paper/1802.08089/) (2018)
- [Log-concave sampling: Metropolis-Hastings algorithms are fast](https://mlsanity.com/paper/1801.02309/) (2018)
- [Privacy Amplification by Iteration](https://mlsanity.com/paper/1808.06651/) (2018)
- [Structured Logconcave Sampling with a Restricted Gaussian Oracle](https://mlsanity.com/paper/2010.03106/) (2020)
- [The Randomized Midpoint Method for Log-Concave Sampling](https://mlsanity.com/paper/1909.05503/) (2019)
- [Differential Privacy Dynamics of Langevin Diffusion and Noisy Gradient Descent](https://mlsanity.com/paper/2102.05855/) (2021)
- [Improved analysis for a proximal algorithm for sampling](https://mlsanity.com/paper/2202.06386/) (2022)
- [On sampling from a log-concave density using kinetic Langevin diffusions](https://mlsanity.com/paper/1807.09382/) (2018)
- [Privacy of Noisy Stochastic Gradient Descent: More Iterations without More Privacy Loss](https://mlsanity.com/paper/2205.13710/) (2022)
- [Optimal dimension dependence of the Metropolis-Adjusted Langevin Algorithm](https://mlsanity.com/paper/2012.12810/) (2020)
- [A Universal Catalyst for First-Order Optimization](https://mlsanity.com/paper/1506.02186/) (2015)
- [Fast mixing of Metropolized Hamiltonian Monte Carlo: Benefits of multi-step gradients](https://mlsanity.com/paper/1905.12247/) (2019)
- [Private Convex Optimization via Exponential Mechanism](https://mlsanity.com/paper/2203.00263/) (2022)
- [Differentially Private Learning Needs Hidden State (Or Much Faster Convergence)](https://mlsanity.com/paper/2203.05363/) (2022)
- [Minimax Mixing Time of the Metropolis-Adjusted Langevin Algorithm for Log-Concave Sampling](https://mlsanity.com/paper/2109.13055/) (2021)
- [Convergence of Langevin Monte Carlo in Chi-Squared and Renyi Divergence](https://mlsanity.com/paper/2007.11612/) (2020)
- [Proximal Langevin Algorithm: Rapid Convergence Under Isoperimetry](https://mlsanity.com/paper/1911.01469/) (2019)
- [Optimal Convergence Rate of Hamiltonian Monte Carlo for Strongly Logconcave Distributions](https://mlsanity.com/paper/1905.02313/) (2019)
- [Improved Discretization Analysis for Underdamped Langevin Monte Carlo](https://mlsanity.com/paper/2302.08049/) (2023)
- [Faster Differentially Private Samplers via R'enyi Divergence Analysis of Discretized Langevin MCMC](https://mlsanity.com/paper/2010.14658/) (2020)
- [A Proximal Algorithm for Sampling from Non-smooth Potentials](https://mlsanity.com/paper/2110.04597/) (2021)
- [On the Ergodicity, Bias and Asymptotic Normality of Randomized Midpoint Sampling Method](https://mlsanity.com/paper/2011.03176/) (2020)
- [Logsmooth Gradient Concentration and Tighter Runtimes for Metropolized Hamiltonian Monte Carlo](https://mlsanity.com/paper/2002.04121/) (2020)

## Built on by (most cited first, 30 of 45)

- [Provably Robust Score-Based Diffusion Posterior Sampling for Plug-and-Play Image Reconstruction](https://mlsanity.com/paper/2403.17042/) (2024)
- [Reverse Diffusion Monte Carlo](https://mlsanity.com/paper/2307.02037/) (2023)
- [Provable Guarantees for Generative Behavior Cloning: Bridging Low-Level Stability and High-Level Behavior](https://mlsanity.com/paper/2307.14619/) (2023)
- [High-accuracy sampling for diffusion models and log-concave distributions](https://mlsanity.com/paper/2602.01338/) (2026)
- [When does Metropolized Hamiltonian Monte Carlo provably outperform Metropolis-adjusted Langevin algorithm?](https://mlsanity.com/paper/2304.04724/) (2023)
- [Shifted Interpolation for Differential Privacy](https://mlsanity.com/paper/2403.00278/) (2024)
- [Entropy contraction of the Gibbs sampler under log-concavity](https://mlsanity.com/paper/2410.00858/) (2024)
- [Query lower bounds for log-concave sampling](https://mlsanity.com/paper/2304.02599/) (2023)
- [Fast parallel sampling under isoperimetry](https://mlsanity.com/paper/2401.09016/) (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)
- [Generalized Sobolev Transport for Probability Measures on a Graph](https://mlsanity.com/paper/2402.04516/) (2024)
- [Proximal Interacting Particle Langevin Algorithms](https://mlsanity.com/paper/2406.14292/) (2024)
- [A Simple Proof of the Mixing of Metropolis-Adjusted Langevin Algorithm under Smoothness and Isoperimetry](https://mlsanity.com/paper/2304.04095/) (2023)
- [Sampling from the Mean-Field Stationary Distribution](https://mlsanity.com/paper/2402.07355/) (2024)
- [Kinetic Interacting Particle Langevin Monte Carlo](https://mlsanity.com/paper/2407.05790/) (2024)
- [Efficient Statistics With Unknown Truncation, Polynomial Time Algorithms, Beyond Gaussians](https://mlsanity.com/paper/2410.01656/) (2024)
- [Convergence of Kinetic Langevin Monte Carlo on Lie groups](https://mlsanity.com/paper/2403.12012/) (2024)
- [Characterizing Dependence of Samples along the Langevin Dynamics and Algorithms via Contraction of Phi-Mutual Information](https://mlsanity.com/paper/2402.17067/) (2024)
- [Faster Sampling via Stochastic Gradient Proximal Sampler](https://mlsanity.com/paper/2405.16734/) (2024)
- [On the query complexity of sampling from non-log-concave distributions](https://mlsanity.com/paper/2502.06200/) (2025)
- [Learning Latent Energy-Based Models via Interacting Particle Langevin Dynamics](https://mlsanity.com/paper/2510.12311/) (2025)
- [Non-Log-Concave and Nonsmooth Sampling via Langevin Monte Carlo Algorithms](https://mlsanity.com/paper/2305.15988/) (2023)
- [Fast Score-Based Sampling via Log-Concave Reductions](https://mlsanity.com/paper/2512.24152/) (2025)
- [R'enyi-infinity constrained sampling with d3 membership queries](https://mlsanity.com/paper/2407.12967/) (2024)
- [Fast Mixing of Data Augmentation Algorithms: Bayesian Probit, Logit, and Lasso Regression](https://mlsanity.com/paper/2412.07999/) (2024)
- [Conditionally Strongly Log-Concave Generative Models](https://mlsanity.com/paper/2306.00181/) (2023)
- [R'enyi Pufferfish Privacy: General Additive Noise Mechanisms and Privacy Amplification by Iteration](https://mlsanity.com/paper/2312.13985/) (2023)
- [Mixing times of data-augmentation Gibbs samplers for high-dimensional probit regression](https://mlsanity.com/paper/2505.14343/) (2025)
- [High-accuracy log-concave sampling with stochastic queries](https://mlsanity.com/paper/2602.14342/) (2026)

## Abstract (arXiv)

Understanding the complexity of sampling from a strongly log-concave and log-smooth distribution π on ℝd to high accuracy is a fundamental problem, both from a practical and theoretical standpoint. In practice, high-accuracy samplers such as the classical Metropolis-adjusted Langevin algorithm (MALA) remain the de facto gold standard; and in theory, via the proximal sampler reduction, it is understood that such samplers are key for sampling even beyond log-concavity (in particular, for distributions satisfying isoperimetric assumptions). In this work, we improve the dimension dependence of this sampling problem to tildeO(d1/2), whereas the previous best result for MALA was tildeO(d). This closes the long line of work on the complexity of MALA, and moreover leads to state-of-the-art guarantees for high-accuracy sampling under strong log-concavity and beyond (thanks to the aforementioned reduction). Our starting point is that the complexity of MALA improves to tildeO(d1/2), but only under a warm start (an initialization with constant R'enyi divergence w.r.t. π). Previous algorithms took much longer to find a warm start than to use it, and closing this gap has remained an important open problem in the field. Our main technical contribution settles this problem by establishing the first tildeO(d1/2) R'enyi mixing rates for the discretized underdamped Langevin diffusion. For this, we develop new differential-privacy-inspired techniques based on R'enyi divergences with Orlicz--Wasserstein shifts, which allow us to sidestep longstanding challenges for proving fast convergence of hypocoercive differential equations.