Abstract
We propose a new gradient descent algorithm with added stochastic terms forfinding the global optimizers of nonconvex optimization problems. A keycomponent in the algorithm is the adaptive tuning of the randomness based onthe value of the objective function. In the language of simulated annealing,the temperature is state-dependent. With this, we prove the global convergenceof the algorithm with an algebraic rate both in probability and in theparameter space. This is a significant improvement over the classical rate fromusing a more straightforward control of the noise term. The convergence proofis based on the actual discrete setup of the algorithm, not just its continuouslimit as often done in the literature. We also present several numericalexamples to demonstrate the efficiency and robustness of the algorithm forreasonably complex objective functions.