Breaking Reversibility Accelerates Langevin Dynamics for Global Non-Convex Optimization

Abstract

Langevin dynamics (LD) has been proven to be a powerful technique for optimizing a non-convex objective as an efficient algorithm to find local minima while eventually visiting a global minimum on longer time-scales. LD is based on the first-order Langevin diffusion which is reversible in time. We study two variants that are based on non-reversible Langevin diffusions: the underdamped Langevin dynamics (ULD) and the Langevin dynamics with a non-symmetric drift (NLD). Adopting the techniques of Tzen, Liang and Raginsky (2018) for LD to non-reversible diffusions, we show that for a given local minimum that is within an arbitrary distance from the initialization, with high probability, either the ULD trajectory ends up somewhere outside a small neighborhood of this local minimum within a recurrence time which depends on the smallest eigenvalue of the Hessian at the local minimum or they enter this neighborhood by the recurrence time and stay there for a potentially exponentially long escape time. The ULD algorithms improve upon the recurrence time obtained for LD in Tzen, Liang and Raginsky (2018) with respect to the dependency on the smallest eigenvalue of the Hessian at the local minimum. Similar result and improvement are obtained for the NLD algorithm. We also show that non-reversible variants can exit the basin of attraction of a local minimum faster in discrete time when the objective has two local minima separated by a saddle point and quantify the amount of improvement. Our analysis suggests that non-reversible Langevin algorithms are more efficient to locate a local minimum as well as exploring the state space. Our analysis is based on the quadratic approximation of the objective around a local minimum. As a by-product of our analysis, we obtain optimal mixing rates for quadratic objectives in the 2-Wasserstein distance for two non-reversible Langevin algorithms we consider.

References in corpus (19)

• Stochastic Gradient Hamiltonian Monte Carlo
• Generalisation of the Eyring-Kramers transition rate formula to irreversible diffusion processes
• Optimal non-reversible linear drift for the convergence to equilibrium of a diffusion
• On the Convergence of Stochastic Gradient MCMC Algorithms with High-Order Integrators
• Variance Reduction using Nonreversible Langevin Samplers
• Accelerating diffusions
• Eigenvalues of the Hessian in Deep Learning: Singularity and Beyond
• Kramers' law: Validity, derivations and generalisations
• Underdamped Langevin MCMC: A non-asymptotic analysis
• Rapid Mixing of Hamiltonian Monte Carlo on Strongly Log-Concave Distributions
• A Hitting Time Analysis of Stochastic Gradient Langevin Dynamics
• Improving the convergence of reversible samplers
• Dirichlet's and Thomson's principles for non-selfadjoint elliptic operators with application to non-reversible metastable diffusion processes
• Escaping the Local Minima via Simulated Annealing: Optimization of Approximately Convex Functions
• Is There an Analog of Nesterov Acceleration for MCMC?
• Global Convergence of Stochastic Gradient Hamiltonian Monte Carlo for Non-Convex Stochastic Optimization: Non-Asymptotic Performance Bounds and Momentum-Based Acceleration
• On the Theory of Variance Reduction for Stochastic Gradient Monte Carlo
• Non-Asymptotic Analysis of Fractional Langevin Monte Carlo for Non-Convex Optimization
• Nonreversible Langevin Samplers: Splitting Schemes, Analysis and Implementation

Cited by in corpus (12)

• Is There an Analog of Nesterov Acceleration for MCMC?
• Decentralized Stochastic Gradient Langevin Dynamics and Hamiltonian Monte Carlo
• Fractional Underdamped Langevin Dynamics: Retargeting SGD with Momentum under Heavy-Tailed Gradient Noise
• On the Heavy-Tailed Theory of Stochastic Gradient Descent for Deep Neural Networks
• A Universally Optimal Multistage Accelerated Stochastic Gradient Method
• Accelerated Linear Convergence of Stochastic Momentum Methods in Wasserstein Distances
• First Exit Time Analysis of Stochastic Gradient Descent Under Heavy-Tailed Gradient Noise
• Faster Convergence of Stochastic Gradient Langevin Dynamics for Non-Log-Concave Sampling
• On the Generalised Langevin Equation for Simulated Annealing
• Non-Convex Optimization via Non-Reversible Stochastic Gradient Langevin Dynamics
• On the convergence of an improved and adaptive kinetic simulated annealing
• Revisiting the Effects of Stochasticity for Hamiltonian Samplers