On the fast convergence of random perturbations of the gradient flow

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 ({\epsilon }^{-1}))$ time on the average, where $\epsilon$ 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.

Revise and Resubmit at Asymptotic Analysis

References in corpus (2)

• The Anisotropic Noise in Stochastic Gradient Descent: Its Behavior of Escaping from Sharp Minima and Regularization Effects
• Exit asymptotics for small diffusion about an unstable equilibrium

Cited by in corpus (4)

• Quasi-potential as an implicit regularizer for the loss function in the stochastic gradient descent
• Exit Time Analysis for Approximations of Gradient Descent Trajectories Around Saddle Points
• On the Global Convergence of Continuous-Time Stochastic Heavy-Ball Method for Nonconvex Optimization
• Stationary Behavior of Constant Stepsize SGD Type Algorithms: An Asymptotic Characterization