Simulated annealing from continuum to discretization: a convergence analysis via the Eyring--Kramers law
This provides theoretical guarantees for optimization algorithms, but it is incremental as it builds on existing convergence analysis using functional inequalities.
The paper tackles the problem of analyzing the convergence rate of continuous-time simulated annealing and its discretization for finding global optima, proving that the tail probability of not reaching the optimum decays polynomially with explicit rates derived from the Eyring-Kramers law.
We study the convergence rate of continuous-time simulated annealing $(X_t; \, t \ge 0)$ and its discretization $(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 +δ)$ (resp. $\mathbb{P}(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.