# Simulated annealing from continuum to discretization: a convergence analysis via the Eyring--Kramers law

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 10 of its 55 references that are in the map.
- First posted on arXiv 3 Feb 2021.

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

- [How to Escape Saddle Points Efficiently](https://mlsanity.com/paper/1703.00887/) (2017)
- [Escaping From Saddle Points --- Online Stochastic Gradient for Tensor Decomposition](https://mlsanity.com/paper/1503.02101/) (2015)
- [Non-convex learning via Stochastic Gradient Langevin Dynamics: a nonasymptotic analysis](https://mlsanity.com/paper/1702.03849/) (2017)
- [Rapid Convergence of the Unadjusted Langevin Algorithm: Isoperimetry Suffices](https://mlsanity.com/paper/1903.08568/) (2019)
- [Non-asymptotic convergence analysis for the Unadjusted Langevin Algorithm](https://mlsanity.com/paper/1507.05021/) (2015)
- [Non-convex Optimization for Machine Learning](https://mlsanity.com/paper/1712.07897/) (2017)
- [Sampling Can Be Faster Than Optimization](https://mlsanity.com/paper/1811.08413/) (2018)
- [State-Dependent Temperature Control for Langevin Diffusions](https://mlsanity.com/paper/2011.07456/) (2020)
- [Is There an Analog of Nesterov Acceleration for MCMC?](https://mlsanity.com/paper/1902.00996/) (2019)
- [On Stationary-Point Hitting Time and Ergodicity of Stochastic Gradient Langevin Dynamics](https://mlsanity.com/paper/1904.13016/) (2019)

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

- [Score-Based Diffusion meets Annealed Importance Sampling](https://mlsanity.com/paper/2208.07698/) (2022)
- [Two-Scale Gradient Descent Ascent Dynamics Finds Mixed Nash Equilibria of Continuous Games: A Mean-Field Perspective](https://mlsanity.com/paper/2212.08791/) (2022)
- [Variational Learning of Gaussian Process Latent Variable Models through Stochastic Gradient Annealed Importance Sampling](https://mlsanity.com/paper/2408.06710/) (2024)
- [Fisher information dissipation for time inhomogeneous stochastic differential equations](https://mlsanity.com/paper/2402.01036/) (2024)
- [Continuous Policy and Value Iteration for Relaxed Stochastic Control Problems and Its Convergence](https://mlsanity.com/paper/2506.08121/) (2025)

## Abstract (arXiv)

We study the convergence rate of continuous-time simulated annealing (Xt; , t ≥ 0) and its discretization (xk; , k =0,1, ldots) for approximating the global optimum of a given function f. We prove that the tail probability mathbbP(f(Xt) > min f +δ) (resp. mathbbP(f(xk) > min f +δ)) decays polynomial in time (resp. in cumulative step size), and provide an explicit rate as a function of the model parameters. Our argument applies the recent development on functional inequalities for the Gibbs measure at low temperatures -- the Eyring-Kramers law. In the discrete setting, we obtain a condition on the step size to ensure the convergence.