On the Fast Convergence of Random Perturbations of the Gradient Flow
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.
J. Yang et al., "On the Fast Convergence of Random Perturbations of the Gradient Flow," Asymptotic Analysis, vol. 122, no. 3 thru 4, pp. 371-393, IOS Press, Jan 2021.
The definitive version is available at https://doi.org/10.3233/ASY-201622
Mathematics and Statistics
Keywords and Phrases
Diffusion approximation; Exit problem; Random perturbations of dynamical systems; Saddle point; Stochastic gradient descent
International Standard Serial Number (ISSN)
Article - Journal
© 2021 IOS Press, All rights reserved.
01 Jan 2021