TAIL PROBABILITY ESTIMATES OF CONTINUOUS-TIME SIMULATED ANNEALING PROCESSES

We study the convergence rate of a continuous-time simulated annealing process (X-t; t >= 0) for approximating the global optimum of a given function f. We prove that the tail probability P(f(X-t) > min f + delta) decays polynomial in time with an appropriately chosen cooling schedule of temperature, and provide an explicit convergence rate through a non-asymptotic bound. Our argument applies recent development of the Eyring-Kramers law on functional inequalities for the Gibbs measure at low temperatures.