Global Convergence of Stochastic Gradient Hamiltonian Monte Carlo for Non-Convex Stochastic Optimization: Non-Asymptotic Performance Bounds and Momentum-Based Acceleration

Abstract

Stochastic gradient Hamiltonian Monte Carlo (SGHMC) is a variant of stochastic gradient with momentum where a controlled and properly scaled Gaussian noise is added to the stochastic gradients to steer the iterates towards a global minimum. Many works reported its empirical success in practice for solving stochastic non-convex optimization problems, in particular it has been observed to outperform overdamped Langevin Monte Carlo-based methods such as stochastic gradient Langevin dynamics (SGLD) in many applications. Although asymptotic global convergence properties of SGHMC are well known, its finite-time performance is not well-understood. In this work, we study two variants of SGHMC based on two alternative discretizations of the underdamped Langevin diffusion. We provide finite-time performance bounds for the global convergence of both SGHMC variants for solving stochastic non-convex optimization problems with explicit constants. Our results lead to non-asymptotic guarantees for both population and empirical risk minimization problems. For a fixed target accuracy level, on a class of non-convex problems, we obtain complexity bounds for SGHMC that can be tighter than those for SGLD. These results show that acceleration with momentum is possible in the context of global non-convex optimization.

References in corpus (28)

• A Conceptual Introduction to Hamiltonian Monte Carlo
• A Differential Equation for Modeling Nesterov's Accelerated Gradient Method: Theory and Insights
• Stochastic Gradient Hamiltonian Monte Carlo
• A Variational Perspective on Accelerated Methods in Optimization
• The rate of convergence of Nesterov's accelerated forward-backward method is actually faster than $1/k^2$
• Complete Dictionary Recovery over the Sphere I: Overview and the Geometric Picture
• User-friendly guarantees for the Langevin Monte Carlo with inaccurate gradient
• The computation of averages from equilibrium and nonequilibrium Langevin molecular dynamics
• A Lyapunov Analysis of Momentum Methods in Optimization
• On the Convergence of Stochastic Gradient MCMC Algorithms with High-Order Integrators
• Learning One-hidden-layer Neural Networks with Landscape Design
• Bayesian Posterior Sampling via Stochastic Gradient Fisher Scoring
• Sparse Regression Learning by Aggregation and Langevin Monte-Carlo
• Underdamped Langevin MCMC: A non-asymptotic analysis
• Understanding the Acceleration Phenomenon via High-Resolution Differential Equations
• Rapid Mixing of Hamiltonian Monte Carlo on Strongly Log-Concave Distributions
• Bridging the Gap between Stochastic Gradient MCMC and Stochastic Optimization
• Local Lipschitz continuity in the initial value and strong completeness for nonlinear stochastic differential equations
• Direct Runge-Kutta Discretization Achieves Acceleration
• On Graduated Optimization for Stochastic Non-Convex Problems
• Optimizing The Integrator Step Size for Hamiltonian Monte Carlo
• Escaping the Local Minima via Simulated Annealing: Optimization of Approximately Convex Functions
• Stochastic Quasi-Newton Langevin Monte Carlo
• Asynchronous Stochastic Quasi-Newton MCMC for Non-Convex Optimization
• Does Hamiltonian Monte Carlo mix faster than a random walk on multimodal densities?
• Global Convergence of Langevin Dynamics Based Algorithms for Nonconvex Optimization
• Bounding the error of discretized Langevin algorithms for non-strongly log-concave targets
• Accelerating Greedy Coordinate Descent Methods

Cited by in corpus (20)

• Understanding the Acceleration Phenomenon via High-Resolution Differential Equations
• Bayesian Pose Graph Optimization via Bingham Distributions and Tempered Geodesic MCMC
• Fractional Underdamped Langevin Dynamics: Retargeting SGD with Momentum under Heavy-Tailed Gradient Noise
• Decentralized Stochastic Gradient Langevin Dynamics and Hamiltonian Monte Carlo
• Hausdorff Dimension, Heavy Tails, and Generalization in Neural Networks
• 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
• Breaking Reversibility Accelerates Langevin Dynamics for Global Non-Convex Optimization
• First Exit Time Analysis of Stochastic Gradient Descent Under Heavy-Tailed Gradient Noise
• Nonasymptotic analysis of Stochastic Gradient Hamiltonian Monte Carlo under local conditions for nonconvex optimization
• Faster Convergence of Stochastic Gradient Langevin Dynamics for Non-Log-Concave Sampling
• Global Non-convex Optimization with Discretized Diffusions
• AMAGOLD: Amortized Metropolis Adjustment for Efficient Stochastic Gradient MCMC
• Non-Convex Optimization via Non-Reversible Stochastic Gradient Langevin Dynamics
• SGLB: Stochastic Gradient Langevin Boosting
• Structured Logconcave Sampling with a Restricted Gaussian Oracle
• Asymmetric Heavy Tails and Implicit Bias in Gaussian Noise Injections
• A Unifying and Canonical Description of Measure-Preserving Diffusions
• Variance reduction for Random Coordinate Descent-Langevin Monte Carlo