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

Abstract

We study the convergence rate of continuous-time simulated annealing $(X_t;t\ge 0)$ and its discretization $(x_k;k=0,1,\dots )$ 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.

arXiv comment19 pages, 1 figure

References in corpus (7)

• Levy Flights, Non-local Search and Simulated Annealing
• Non-convex learning via Stochastic Gradient Langevin Dynamics: a nonasymptotic analysis
• Non-asymptotic convergence analysis for the Unadjusted Langevin Algorithm
• Poincaré and logarithmic Sobolev inequalities by decomposition of the energy landscape
• Is There an Analog of Nesterov Acceleration for MCMC?
• Rapid Convergence of the Unadjusted Langevin Algorithm: Isoperimetry Suffices
• On The Simulated Annealing In ${\mathbf{R}}^d$