On Stationary-Point Hitting Time and Ergodicity of Stochastic Gradient Langevin Dynamics

Abstract

Stochastic gradient Langevin dynamics (SGLD) is a fundamental algorithm in stochastic optimization. Recent work by Zhang et al. [2017] presents an analysis for the hitting time of SGLD for the first and second order stationary points. The proof in Zhang et al. [2017] is a two-stage procedure through bounding the Cheeger's constant, which is rather complicated and leads to loose bounds. In this paper, using intuitions from stochastic differential equations, we provide a direct analysis for the hitting times of SGLD to the first and second order stationary points. Our analysis is straightforward. It only relies on basic linear algebra and probability theory tools. Our direct analysis also leads to tighter bounds comparing to Zhang et al. [2017] and shows the explicit dependence of the hitting time on different factors, including dimensionality, smoothness, noise strength, and step size effects. Under suitable conditions, we show that the hitting time of SGLD to first-order stationary points can be dimension-independent. Moreover, we apply our analysis to study several important online estimation problems in machine learning, including linear regression, matrix factorization, and online PCA.

arXiv comment41 pages

References in corpus (20)

• Adding Gradient Noise Improves Learning for Very Deep Networks
• Complete Dictionary Recovery over the Sphere I: Overview and the Geometric Picture
• Global Optimality of Local Search for Low Rank Matrix Recovery
• Neural GPUs Learn Algorithms
• No Spurious Local Minima in Nonconvex Low Rank Problems: A Unified Geometric Analysis
• User-friendly guarantees for the Langevin Monte Carlo with inaccurate gradient
• A Comprehensive Study of Deep Bidirectional LSTM RNNs for Acoustic Modeling in Speech Recognition
• On the Power of Over-parametrization in Neural Networks with Quadratic Activation
• On the Convergence of Stochastic Gradient MCMC Algorithms with High-Order Integrators
• Bayesian Posterior Sampling via Stochastic Gradient Fisher Scoring
• Escaping Saddles with Stochastic Gradients
• Identity Matters in Deep Learning
• The Power of Normalization: Faster Evasion of Saddle Points
• Neon2: Finding Local Minima via First-Order Oracles
• On Nonconvex Optimization for Machine Learning: Gradients, Stochasticity, and Saddle Points
• Generalization Bounds of SGLD for Non-convex Learning: Two Theoretical Viewpoints
• Accelerated Gradient Descent Escapes Saddle Points Faster than Gradient Descent
• Sharp Analysis for Nonconvex SGD Escaping from Saddle Points
• Neural Random-Access Machines
• Replica Exchange for Non-Convex Optimization

Cited by in corpus (4)

• Replica Exchange for Non-Convex Optimization
• Convergence Speed and Approximation Accuracy of Numerical MCMC
• Distributed Gradient Methods for Nonconvex Optimization: Local and Global Convergence Guarantees
• Stochastic Gradient Langevin Dynamics with Variance Reduction