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(ε−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.

Department(s)

Mathematics and Statistics

Research Center/Lab(s)

Intelligent Systems Center

Comments

University of Missouri, Grant 903-751819

Keywords and Phrases

Diffusion approximation; Exit problem; Random perturbations of dynamical systems; Saddle point; Stochastic gradient descent

International Standard Serial Number (ISSN)

0921-7134; 1875-8576

Document Type

Article - Journal

Document Version

Citation

File Type

text

Language(s)

English

Rights

© 2021 IOS Press, All rights reserved.

Publication Date

01 Jan 2021

Link to Full Text

Share

 
COinS