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

02/03/2021

∙

by   Wenpin Tang, et al.

∙

0

∙

share

We study the convergence rate of continuous-time simulated annealing (X_t; t ≥ 0) and its discretization (x_k; k =0,1, …) for approximating the global optimum of a given function f. We prove that the tail probability ℙ(f(X_t) > min f +δ) (resp. ℙ(f(x_k) > 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.