Global Convergence of Langevin Dynamics Based Algorithms for Nonconvex Optimization

Abstract

We present a unified framework to analyze the global convergence of Langevin dynamics based algorithms for nonconvex finite-sum optimization with $n$ component functions. At the core of our analysis is a direct analysis of the ergodicity of the numerical approximations to Langevin dynamics, which leads to faster convergence rates. Specifically, we show that gradient Langevin dynamics (GLD) and stochastic gradient Langevin dynamics (SGLD) converge to the almost minimizer within $\tilde{O}(nd/(\lambda \epsilon ))$ and $\tilde{O}(d^7/({\lambda }^5{\epsilon }^5))$ stochastic gradient evaluations respectively, where $d$ is the problem dimension, and $\lambda$ is the spectral gap of the Markov chain generated by GLD. Both results improve upon the best known gradient complexity results (Raginsky et al., 2017). Furthermore, for the first time we prove the global convergence guarantee for variance reduced stochastic gradient Langevin dynamics (SVRG-LD) to the almost minimizer within $\tilde{O}(\sqrt{n}{d}^5/({\lambda }^4{\epsilon }^{5/2}))$ stochastic gradient evaluations, which outperforms the gradient complexities of GLD and SGLD in a wide regime. Our theoretical analyses shed some light on using Langevin dynamics based algorithms for nonconvex optimization with provable guarantees.

29 pages, 1 figure, 1 table. In NeurIPS 2018

References in corpus (13)

• Stochastic Gradient Hamiltonian Monte Carlo
• Spectral gaps in Wasserstein distances and the 2D stochastic Navier--Stokes equations
• User-friendly guarantees for the Langevin Monte Carlo with inaccurate gradient
• On the Convergence of Stochastic Gradient MCMC Algorithms with High-Order Integrators
• Bayesian Posterior Sampling via Stochastic Gradient Fisher Scoring
• Underdamped Langevin MCMC: A non-asymptotic analysis
• Log-concave sampling: Metropolis-Hastings algorithms are fast
• The Power of Normalization: Faster Evasion of Saddle Points
• Accelerated Gradient Descent Escapes Saddle Points Faster than Gradient Descent
• Stochastic Variance-Reduced Cubic Regularized Newton Method
• Asynchronous Stochastic Quasi-Newton MCMC for Non-Convex Optimization
• Beyond Log-concavity: Provable Guarantees for Sampling Multi-modal Distributions using Simulated Tempering Langevin Monte Carlo
• Stochastic Gradient Hamiltonian Monte Carlo with Variance Reduction for Bayesian Inference

Cited by in corpus (8)

• Cyclical Stochastic Gradient MCMC for Bayesian Deep Learning
• Global Convergence of Stochastic Gradient Hamiltonian Monte Carlo for Non-Convex Stochastic Optimization: Non-Asymptotic Performance Bounds and Momentum-Based Acceleration
• Analysis of Langevin Monte Carlo via convex optimization
• Multi-variance replica exchange stochastic gradient MCMC for inverse and forward Bayesian physics-informed neural network
• On stochastic gradient Langevin dynamics with dependent data streams in the logconcave case
• Stochastic Variance-Reduced Hamilton Monte Carlo Methods
• A Particle-Based Algorithm for Distributional Optimization on \textit{Constrained Domains} via Variational Transport and Mirror Descent
• Adaptive Stochastic Gradient Langevin Dynamics: Taming Convergence and Saddle Point Escape Time