# Sampling Can Be Faster Than Optimization

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

## Key facts

- Cited by 68 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 20 Nov 2018.

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

- [COLD Decoding: Energy-based Constrained Text Generation with Langevin Dynamics](https://mlsanity.com/paper/2202.11705/) (2022)
- [Fine-Tuning of Continuous-Time Diffusion Models as Entropy-Regularized Control](https://mlsanity.com/paper/2402.15194/) (2024)
- [Policy Representation via Diffusion Probability Model for Reinforcement Learning](https://mlsanity.com/paper/2305.13122/) (2023)
- [Self-Improvement in Language Models: The Sharpening Mechanism](https://mlsanity.com/paper/2412.01951/) (2024)
- [Langevin Unlearning: A New Perspective of Noisy Gradient Descent for Machine Unlearning](https://mlsanity.com/paper/2401.10371/) (2024)
- [Reverse Diffusion Monte Carlo](https://mlsanity.com/paper/2307.02037/) (2023)
- [Diffusion Models as Constrained Samplers for Optimization with Unknown Constraints](https://mlsanity.com/paper/2402.18012/) (2024)
- [Composable Text Controls in Latent Space with ODEs](https://mlsanity.com/paper/2208.00638/) (2022)
- [Provable Benefit of Annealed Langevin Monte Carlo for Non-log-concave Sampling](https://mlsanity.com/paper/2407.16936/) (2024)
- [Proving Olympiad Inequalities by Synergizing LLMs and Symbolic Reasoning](https://mlsanity.com/paper/2502.13834/) (2025)
- [On Convergence of Federated Averaging Langevin Dynamics](https://mlsanity.com/paper/2112.05120/) (2021)
- [When is the Convergence Time of Langevin Algorithms Dimension Independent? A Composite Optimization Viewpoint](https://mlsanity.com/paper/2110.01827/) (2021)
- [Low-Precision Stochastic Gradient Langevin Dynamics](https://mlsanity.com/paper/2206.09909/) (2022)
- [Posterior Sampling with Denoising Oracles via Tilted Transport](https://mlsanity.com/paper/2407.00745/) (2024)
- [Convergence Rates for Non-Log-Concave Sampling and Log-Partition Estimation](https://mlsanity.com/paper/2303.03237/) (2023)
- [Langevin Monte Carlo for strongly log-concave distributions: Randomized midpoint revisited](https://mlsanity.com/paper/2306.08494/) (2023)
- [On Quantum Speedups for Nonconvex Optimization via Quantum Tunneling Walks](https://mlsanity.com/paper/2209.14501/) (2022)
- [Convergence Analysis of Schr"odinger-F"ollmer Sampler without Convexity](https://mlsanity.com/paper/2107.04766/) (2021)
- [Statistical and Computational Trade-offs in Variational Inference: A Case Study in Inferential Model Selection](https://mlsanity.com/paper/2207.11208/) (2022)
- [Taming under isoperimetry](https://mlsanity.com/paper/2311.09003/) (2023)
- [Heavy-tailed Sampling via Transformed Unadjusted Langevin Algorithm](https://mlsanity.com/paper/2201.08349/) (2022)
- [Constrained Langevin Algorithms with L-mixing External Random Variables](https://mlsanity.com/paper/2205.14192/) (2022)
- [Simulated annealing from continuum to discretization: a convergence analysis via the Eyring--Kramers law](https://mlsanity.com/paper/2102.02339/) (2021)
- [Fast Conditional Mixing of MCMC Algorithms for Non-log-concave Distributions](https://mlsanity.com/paper/2306.10506/) (2023)
- [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)
- [On Mixing Rates for Bayesian CART](https://mlsanity.com/paper/2306.00126/) (2023)
- [Stochastic Quantum Sampling for Non-Logconcave Distributions and Estimating Partition Functions](https://mlsanity.com/paper/2310.11445/) (2023)
- [Tractable MCMC for Private Learning with Pure and Gaussian Differential Privacy](https://mlsanity.com/paper/2310.14661/) (2023)
- [Sampling from multi-modal distributions with polynomial query complexity in fixed dimension via reverse diffusion](https://mlsanity.com/paper/2501.00565/) (2024)

## Abstract (arXiv)

Optimization algorithms and Monte Carlo sampling algorithms have provided the computational foundations for the rapid growth in applications of statistical machine learning in recent years. There is, however, limited theoretical understanding of the relationships between these two kinds of methodology, and limited understanding of relative strengths and weaknesses. Moreover, existing results have been obtained primarily in the setting of convex functions (for optimization) and log-concave functions (for sampling). In this setting, where local properties determine global properties, optimization algorithms are unsurprisingly more efficient computationally than sampling algorithms. We instead examine a class of nonconvex objective functions that arise in mixture modeling and multi-stable systems. In this nonconvex setting, we find that the computational complexity of sampling algorithms scales linearly with the model dimension while that of optimization algorithms scales exponentially.