Is There an Analog of Nesterov Acceleration for MCMC?

Abstract

We formulate gradient-based Markov chain Monte Carlo (MCMC) sampling as optimization on the space of probability measures, with Kullback-Leibler (KL) divergence as the objective functional. We show that an underdamped form of the Langevin algorithm performs accelerated gradient descent in this metric. To characterize the convergence of the algorithm, we construct a Lyapunov functional and exploit hypocoercivity of the underdamped Langevin algorithm. As an application, we show that accelerated rates can be obtained for a class of nonconvex functions with the Langevin algorithm.

References in corpus (12)

• A Differential Equation for Modeling Nesterov's Accelerated Gradient Method: Theory and Insights
• User-friendly guarantees for the Langevin Monte Carlo with inaccurate gradient
• Sampling Can Be Faster Than Optimization
• A Lyapunov Analysis of Momentum Methods in Optimization
• Log-concave sampling: Metropolis-Hastings algorithms are fast
• Non-asymptotic convergence analysis for the Unadjusted Langevin Algorithm
• Convergence of Langevin MCMC in KL-divergence
• Rapid Mixing of Hamiltonian Monte Carlo on Strongly Log-Concave Distributions
• Direct Runge-Kutta Discretization Achieves Acceleration
• Acceleration via Symplectic Discretization of High-Resolution Differential Equations
• Sampling as optimization in the space of measures: The Langevin dynamics as a composite optimization problem
• Breaking Reversibility Accelerates Langevin Dynamics for Global Non-Convex Optimization

Cited by in corpus (35)

• Sampling Can Be Faster Than Optimization
• Stochastic Runge-Kutta Accelerates Langevin Monte Carlo and Beyond
• Decentralized Stochastic Gradient Langevin Dynamics and Hamiltonian Monte Carlo
• Complexity of randomized algorithms for underdamped Langevin dynamics
• On the Convergence of Langevin Monte Carlo: The Interplay between Tail Growth and Smoothness
• Optimal Convergence Rate of Hamiltonian Monte Carlo for Strongly Logconcave Distributions
• CoolMomentum: A Method for Stochastic Optimization by Langevin Dynamics with Simulated Annealing
• Bounding the error of discretized Langevin algorithms for non-strongly log-concave targets
• Breaking Reversibility Accelerates Langevin Dynamics for Global Non-Convex Optimization
• Proximal Langevin Algorithm: Rapid Convergence Under Isoperimetry
• Nonasymptotic analysis of Stochastic Gradient Hamiltonian Monte Carlo under local conditions for nonconvex optimization
• Primal Dual Interpretation of the Proximal Stochastic Gradient Langevin Algorithm
• Geometric Methods for Sampling, Optimisation, Inference and Adaptive Agents
• On the Ergodicity, Bias and Asymptotic Normality of Randomized Midpoint Sampling Method
• Stochastic Proximal Langevin Algorithm: Potential Splitting and Nonasymptotic Rates
• Information Newton's flow: second-order optimization method in probability space
• Complexity of zigzag sampling algorithm for strongly log-concave distributions
• Convergence of Stein Variational Gradient Descent under a Weaker Smoothness Condition
• Estimating Normalizing Constants for Log-Concave Distributions: Algorithms and Lower Bounds
• De-randomizing MCMC dynamics with the diffusion Stein operator
• Hessian-Free High-Resolution Nesterov Acceleration for Sampling
• Simulated annealing from continuum to discretization: a convergence analysis via the Eyring--Kramers law
• Stochasticity of Deterministic Gradient Descent: Large Learning Rate for Multiscale Objective Function
• Sampling with Mirrored Stein Operators
• Faster Differentially Private Samplers via Rényi Divergence Analysis of Discretized Langevin MCMC
• Variational Transport: A Convergent Particle-BasedAlgorithm for Distributional Optimization
• A Unifying and Canonical Description of Measure-Preserving Diffusions
• On the cost of Bayesian posterior mean strategy for log-concave models
• The Wasserstein Proximal Gradient Algorithm
• Variational Optimization on Lie Groups, with Examples of Leading (Generalized) Eigenvalue Problems
• When is the Convergence Time of Langevin Algorithms Dimension Independent? A Composite Optimization Viewpoint
• Fast Convergence of Langevin Dynamics on Manifold: Geodesics meet Log-Sobolev
• A Decentralized Approach to Bayesian Learning
• Stochastic Approximate Gradient Descent via the Langevin Algorithm
• A New Framework for Variance-Reduced Hamiltonian Monte Carlo