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

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.