Convergence of Langevin-Simulated Annealing algorithms with multiplicative noise

Abstract

We study the convergence of Langevin-Simulated Annealing type algorithms with multiplicative noise, i.e. for $V:{\mathbb{R}}^d\to \mathbb{R}$ a potential function to minimize, we consider the stochastic equation $d{Y}_t=-\sigma {\sigma }^{\top }\nabla V(Y_t)dt+a(t)\sigma (Y_t)d{W}_t+a(t{)}^2{\rm Y}(Y_t)dt$, where $(W_t)$ is a Brownian motion, where $\sigma :{\mathbb{R}}^d\to {\mathcal{M}}_d(\mathbb{R})$ is an adaptive (multiplicative) noise, where $a:{\mathbb{R}}^{+}\to {\mathbb{R}}^{+}$ is a function decreasing to $0$ and where ${\rm Y}$ is a correction term. This setting can be applied to optimization problems arising in Machine Learning. The case where $\sigma$ is a constant matrix has been extensively studied however little attention has been paid to the general case. We prove the convergence for the $L^1$-Wasserstein distance of $Y_t$ and of the associated Euler-scheme ${\bar{Y}}_t$ to some measure ${\nu }^{\star }$ which is supported by $\text{argmin}(V)$ and give rates of convergence to the instantaneous Gibbs measure ${\nu }_{a(t)}$ of density $\propto \exp (-2V(x)/a(t{)}^2)$. To do so, we first consider the case where $a$ is a piecewise constant function. We find again the classical schedule $a(t)=A{\log }^{-1/2}(t)$. We then prove the convergence for the general case by giving bounds for the Wasserstein distance to the stepwise constant case using ergodicity properties.

arXiv comment31 pages + Supplementary Material (6 pages)