Affiliations: [a] School of Mathematics and Statistics, Anhui Normal University, Wuhu, 241002, P.R. China. E-mail: y.jiaojiao1025@yahoo.com | [b] Department of Mathematics and Statistics, Missouri University of Science and Technology (formerly University of Missouri, Rolla), USA. E-mail: huwen@mst.edu | [c] Department of Electrical Engineering and Computer Sciences, University of California, Berkeley, USA. E-mail: junchi.li.duke@gmail.com
Abstract: We consider in this work small random perturbations (of multiplicative noise type) of the gradient flow. We prove that under mild conditions, when the potential function is a Morse function with additional strong saddle condition, the perturbed gradient flow converges to the neighborhood of local minimizers in O(ln(ε−1)) time on the average, where ε is the scale of the random perturbation. Under a change of time scale, this indicates that for the diffusion process that approximates the stochastic gradient method, it takes (up to logarithmic factor) only a linear time of inverse stepsize to evade from all saddle points. This can be regarded as a manifestation of fast convergence of the discrete-time stochastic gradient method, the latter being used heavily in modern statistical machine learning.
Keywords: Random perturbations of dynamical systems, saddle point, exit problem, stochastic gradient descent, diffusion approximation
