# Convergence Rates for Non-Log-Concave Sampling and Log-Partition Estimation

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

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- Builds on 21 of its 59 references that are in the map.
- First posted on arXiv 6 Mar 2023.

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

- [Sampling is as easy as learning the score: theory for diffusion models with minimal data assumptions](https://mlsanity.com/paper/2209.11215/) (2022)
- [Log-concave sampling: Metropolis-Hastings algorithms are fast](https://mlsanity.com/paper/1801.02309/) (2018)
- [Sharp convergence rates for Langevin dynamics in the nonconvex setting](https://mlsanity.com/paper/1805.01648/) (2018)
- [Sampling Can Be Faster Than Optimization](https://mlsanity.com/paper/1811.08413/) (2018)
- [Towards a Theory of Non-Log-Concave Sampling: First-Order Stationarity Guarantees for Langevin Monte Carlo](https://mlsanity.com/paper/2202.05214/) (2022)
- [Optimal dimension dependence of the Metropolis-Adjusted Langevin Algorithm](https://mlsanity.com/paper/2012.12810/) (2020)
- [Information Theory with Kernel Methods](https://mlsanity.com/paper/2202.08545/) (2022)
- [Coupling and Convergence for Hamiltonian Monte Carlo](https://mlsanity.com/paper/1805.00452/) (2018)
- [Faster Convergence of Stochastic Gradient Langevin Dynamics for Non-Log-Concave Sampling](https://mlsanity.com/paper/2010.09597/) (2020)
- [Finding Global Minima via Kernel Approximations](https://mlsanity.com/paper/2012.11978/) (2020)
- [Resolving the Mixing Time of the Langevin Algorithm to its Stationary Distribution for Log-Concave Sampling](https://mlsanity.com/paper/2210.08448/) (2022)
- [The query complexity of sampling from strongly log-concave distributions in one dimension](https://mlsanity.com/paper/2105.14163/) (2021)
- [Estimating Normalizing Constants for Log-Concave Distributions: Algorithms and Lower Bounds](https://mlsanity.com/paper/1911.03043/) (2019)
- [Nonconvex sampling with the Metropolis-adjusted Langevin algorithm](https://mlsanity.com/paper/1902.08452/) (2019)
- [Fisher information lower bounds for sampling](https://mlsanity.com/paper/2210.02482/) (2022)
- [Dimensionally Tight Bounds for Second-Order Hamiltonian Monte Carlo](https://mlsanity.com/paper/1802.08898/) (2018)
- [Sampling from Arbitrary Functions via PSD Models](https://mlsanity.com/paper/2110.10527/) (2021)
- [Computational Separations between Sampling and Optimization](https://mlsanity.com/paper/1911.02074/) (2019)
- [Sum-of-Squares Relaxations for Information Theory and Variational Inference](https://mlsanity.com/paper/2206.13285/) (2022)
- [Non-Convex Optimization with Certificates and Fast Rates Through Kernel Sums of Squares](https://mlsanity.com/paper/2204.04970/) (2022)
- [A minimax near-optimal algorithm for adaptive rejection sampling](https://mlsanity.com/paper/1810.09390/) (2018)

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

- [Zeroth-Order Sampling Methods for Non-Log-Concave Distributions: Alleviating Metastability by Denoising Diffusion](https://mlsanity.com/paper/2402.17886/) (2024)
- [Optimal Convergence Analysis of DDPM for General Distributions](https://mlsanity.com/paper/2510.27562/) (2025)
- [A Sharp KL-Convergence Analysis for Diffusion Models under Minimal Assumptions](https://mlsanity.com/paper/2508.16306/) (2025)
- [On the query complexity of sampling from non-log-concave distributions](https://mlsanity.com/paper/2502.06200/) (2025)
- [Non-Log-Concave and Nonsmooth Sampling via Langevin Monte Carlo Algorithms](https://mlsanity.com/paper/2305.15988/) (2023)
- [When can Regression-Adjusted Control Variates Help? Rare Events, Sobolev Embedding and Minimax Optimality](https://mlsanity.com/paper/2305.16527/) (2023)
- [Kernelized Normalizing Constant Estimation: Bridging Bayesian Quadrature and Bayesian Optimization](https://mlsanity.com/paper/2401.05716/) (2024)
- [Gibbs-Based Information Criteria and the Over-Parameterized Regime](https://mlsanity.com/paper/2306.05583/) (2023)
- [Asymptotically Optimal Change Detection for Unnormalized Pre- and Post-Change Distributions](https://mlsanity.com/paper/2410.14615/) (2024)
- [Minimax Optimal Two-Stage Algorithm For Moment Estimation Under Covariate Shift](https://mlsanity.com/paper/2506.23453/) (2025)

## Abstract (arXiv)

Sampling from Gibbs distributions and computing their log-partition function are fundamental tasks in statistics, machine learning, and statistical physics. While efficient algorithms are known for log-concave densities, the worst-case non-log-concave setting necessarily suffers from the curse of dimensionality. For many numerical problems, the curse of dimensionality can be alleviated when the target function is smooth, allowing the exponent in the rate to improve linearly with the number of available derivatives. Recently, it has been shown that similarly fast convergence rates can be achieved by efficient optimization algorithms. Since optimization can be seen as the low-temperature limit of sampling from Gibbs distributions, we pose the question of whether similarly fast convergence rates can be achieved for non-log-concave sampling. We first study the information-based complexity of the sampling and log-partition estimation problems and show that the optimal rates for sampling and log-partition computation are sometimes equal and sometimes faster than for optimization. We then analyze various polynomial-time sampling algorithms, including an extension of a recent promising optimization approach, and find that they sometimes exhibit interesting behavior but no near-optimal rates. Our results also give further insights into the relation between sampling, log-partition, and optimization problems.