mlsanityData to 7 Oct 2026

Sampling Can Be Faster Than Optimization

arXiv 1811.08413 ↗First posted 20 Nov 2018stat.ML cs.LGcited by 68

Not on the map. Why?

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.

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

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 9; 2022: 12; 2023: 20; 2024: 14; 2025: 6; 2026: 7.

68 papers.

Sort:

By area:

  1. 2022COLD Decoding: Energy-based Constrained Text Generation with Langevin Dynamicscited by 159
  2. 2024Fine-Tuning of Continuous-Time Diffusion Models as Entropy-Regularized Controlcited by 136
  3. 2023Policy Representation via Diffusion Probability Model for Reinforcement Learningcited by 105
  4. 2024Self-Improvement in Language Models: The Sharpening Mechanismcited by 102
  5. 2024Langevin Unlearning: A New Perspective of Noisy Gradient Descent for Machine Unlearningcited by 48
  6. 2023Reverse Diffusion Monte Carlocited by 41
  7. 2024Diffusion Models as Constrained Samplers for Optimization with Unknown Constraintscited by 33
  8. 2022Composable Text Controls in Latent Space with ODEscited by 28
  9. 2024Provable Benefit of Annealed Langevin Monte Carlo for Non-log-concave Samplingcited by 23
  10. 2025Proving Olympiad Inequalities by Synergizing LLMs and Symbolic Reasoningcited by 17
  11. 2021On Convergence of Federated Averaging Langevin Dynamicscited by 14
  12. 2021When is the Convergence Time of Langevin Algorithms Dimension Independent? A Composite Optimization Viewpointcited by 12
38 more
  1. 2022Low-Precision Stochastic Gradient Langevin Dynamicscited by 12
  2. 2024Posterior Sampling with Denoising Oracles via Tilted Transportcited by 12
  3. 2023Convergence Rates for Non-Log-Concave Sampling and Log-Partition Estimationcited by 10
  4. 2023Langevin Monte Carlo for strongly log-concave distributions: Randomized midpoint revisitedcited by 10
  5. 2022On Quantum Speedups for Nonconvex Optimization via Quantum Tunneling Walkscited by 9
  6. 2021Convergence Analysis of Schr"odinger-F"ollmer Sampler without Convexitycited by 7
  7. 2022Statistical and Computational Trade-offs in Variational Inference: A Case Study in Inferential Model Selectioncited by 7
  8. 2023Taming under isoperimetrycited by 7
  9. 2022Heavy-tailed Sampling via Transformed Unadjusted Langevin Algorithmcited by 6
  10. 2022Constrained Langevin Algorithms with L-mixing External Random Variablescited by 6
  11. 2021Simulated annealing from continuum to discretization: a convergence analysis via the Eyring--Kramers lawcited by 5
  12. 2023Fast Conditional Mixing of MCMC Algorithms for Non-log-concave Distributionscited by 5
  13. 2025On the query complexity of sampling from non-log-concave distributionscited by 5
  14. 2023Non-Log-Concave and Nonsmooth Sampling via Langevin Monte Carlo Algorithmscited by 4
  15. 2023On Mixing Rates for Bayesian CARTcited by 4
  16. 2023Stochastic Quantum Sampling for Non-Logconcave Distributions and Estimating Partition Functionscited by 4
  17. 2023Tractable MCMC for Private Learning with Pure and Gaussian Differential Privacycited by 4
  18. 2024Sampling from multi-modal distributions with polynomial query complexity in fixed dimension via reverse diffusioncited by 4
  19. 2021A Deterministic Sampling Method via Maximum Mean Discrepancy Flow with Adaptive Kernelcited by 3
  20. 2021Unadjusted Langevin algorithm for sampling a mixture of weakly smooth potentialscited by 3
  21. 2023DiffFlow: A Unified SDE Framework for Score-Based Diffusion Models and Generative Adversarial Networkscited by 3
  22. 2023Reflection coupling for unadjusted generalized Hamiltonian Monte Carlo in the nonconvex stochastic gradient casecited by 3
  23. 2025Exponential Convergence Guarantees for Iterative Markovian Fittingcited by 3
  24. 2021Can Stochastic Gradient Langevin Dynamics Provide Differential Privacy for Deep Learning?cited by 2
  25. 2022Mean-Field Analysis of Two-Layer Neural Networks: Global Optimality with Linear Convergence Ratescited by 2
  26. 2023Privacy Risk for anisotropic Langevin dynamics using relative entropy boundscited by 2
  27. 2023Human adaptation to adaptive machines converges to game-theoretic equilibriacited by 2
  28. 2024Kernelized Normalizing Constant Estimation: Bridging Bayesian Quadrature and Bayesian Optimizationcited by 2
  29. 2026Dimension-Free Multimodal Sampling via Preconditioned Annealed Langevin Dynamicscited by 2
  30. 2021Quantifying the mini-batching error in Bayesian inference for Adaptive Langevin dynamicscited by 1
  31. 2022Evaluating Out-of-Distribution Detectors Through Adversarial Generation of Outlierscited by 1
  32. 2023To smooth a cloud or to pin it down: Guarantees and Insights on Score Matching in Denoising Diffusion Modelscited by 1
  33. 2023Subsampling Error in Stochastic Gradient Langevin Diffusionscited by 1
  34. 2024Monte Carlo with kernel-based Gibbs measures: Guarantees for probabilistic herdingcited by 1
  35. 2025Quantum Speedups for Sampling and Non-convex Optimization with Stochastic Oraclescited by 1
  36. 2025A Gradient Guided Diffusion Framework for Chance Constrained Programmingcited by 1
  37. 2026New Trends in the Stability of Sinkhorn Semigroupscited by 1
  38. 2026Towards Diverse Scientific Hypothesis Search with Large Language Modelscited by 1

50 most cited of 68 All 68 (JSON)