Convergence of Langevin-simulated annealing algorithms with multiplicative noise.

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 differential equation dY_t = - \sigma \sigma ^\top \nabla V(Y_t) dt + a(t)\sigma (Y_t)dW_t + a(t)^2\Upsilon (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 \Upsilon is a correction term. This setting can be applied to optimization problems arising in Machine Learning; allowing \sigma to depend on the position brings faster convergence in comparison with the classical Langevin equation dY_t = -\nabla V(Y_t)dt + \sigma dW_t. 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 \operatorname {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. [ABSTRACT FROM AUTHOR]