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

We study the convergence rate of continuous-time simulated annealing $(X_t; , t \ge 0)$anditsdiscretization$(x_k; , k =0,1, \ldots)$ for approximating the global optimum of a given function $f$. We prove that the tail probability $\mathbb{P}(f(X_t)>\min f+\delta )$ (resp. $\mathbb{P}(f(x_k)>\min f+\delta )$) 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.