On the fast convergence of random perturbations of the gradient flow

2017/06/02 by Jiaojiao Yang, Wenqing Hu, Yang, Jiaojiao +3
Computer Science · Mathematics · #37D05 #60J60 #68Q87 #68W20 #FOS: Mathematics #Markov Chains and Monte Carlo Methods #Probability (math.PR) #Statistical Methods and Inference #Stochastic Gradient Optimization Techniques

paper · pdf · doi:10.48550/arxiv.1706.00837

openalex publication_date 2017/06/02 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

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.

Citations

• Stochastic Approximation: A Dynamical Systems Viewpoint
• A Stochastic Approximation Method
• Non-strongly-convex smooth stochastic approximation with convergence rate O(1/n)
• Escaping From Saddle Points --- Online Stochastic Gradient for Tensor Decomposition

Related

• Asymptotic Analysis via Stochastic Differential Equations of Gradient Descent Algorithms in Statistical and Computational Paradigms
• Gradient Descent Converges to Minimizers
• The global convergence time of stochastic gradient descent in non-convex landscapes: Sharp estimates via large deviations
• Stochastic Modified Flows, Mean-Field Limits and Dynamics of Stochastic Gradient Descent
• Gradient Flow from a Random Walk in Hilbert Space