Is there an analog of Nesterov acceleration for gradient-based MCMC?
From MaRDI portal
Publication:2040101
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.
In continuous optimization problems, Nesterov's accelerated gradient descent method accelerates the convergence speed of the simple gradient descent method. This paper considers an analogue of such an acceleration method in Markov chain Monte Carlo (MCMC) methods, which in general have a major issue in convergence speed. As in the accelerated gradient descent for optimization, by introducing a momentum variable, the authors derive the stochastic differential equation for the accelerated dynamics in the space of probability distributions with the Kullback-Leibler divergence to the target distribution as the objective functional. Analyzing the convergence rate of the continuous accelerated dynamics and the discretization error, the authors show that the derived accelerated sampling algorithm improves the dimension and accuracy dependence of the unadjusted Langevin algorithm, which corresponds to the unadjusted gradient decent optimization. Thus, this paper provides a solid theoretical foundation for practical accelerated MCMC methods.
Recommendations
Cites work
- A function space HMC algorithm with second order Langevin diffusion limit
- A variational perspective on accelerated methods in optimization
- A variational principle for the Kramers equation with unbounded external forces
- Acceleration of convergence to equilibrium in Markov chains by breaking detailed balance
- Adaptive restart for accelerated gradient schemes
- Adaptive thermostats for noisy gradient systems
- Analysis of Langevin Monte Carlo via convex optimization
- Conservative-dissipative approximation schemes for a generalized Kramers equation
- Convergence of Langevin MCMC in KL-divergence
- Convex functions on non-convex domains
- Coupling and convergence for Hamiltonian Monte Carlo
- Exponential convergence to equilibrium for kinetic Fokker-Planck equations
- Extension of convex function
- Generalization of an inequality by Talagrand and links with the logarithmic Sobolev inequality
- Gradient flows in metric spaces and in the space of probability measures
- High-dimensional Bayesian inference via the unadjusted Langevin algorithm
- scientific article; zbMATH DE number 3850830 (Why is no real title available?)
- scientific article; zbMATH DE number 3790208 (Why is no real title available?)
- scientific article; zbMATH DE number 3313108 (Why is no real title available?)
- Hypocoercivity
- Improving the convergence of reversible samplers
- Introductory lectures on convex optimization. A basic course.
- Irreversible samplers from jump and continuous Markov processes
- Langevin diffusions and Metropolis-Hastings algorithms
- Log-concave sampling: Metropolis-Hastings algorithms are fast
- Logarithmic Sobolev Inequalities
- MCMC using Hamiltonian dynamics
- Nonasymptotic convergence analysis for the unadjusted Langevin algorithm
- On sampling from a log-concave density using kinetic Langevin diffusions
- Optimal Transport
- Riemann manifold Langevin and Hamiltonian Monte Carlo methods. With discussion and authors' reply
- Sampling can be faster than optimization
- The Bouncy Particle Sampler: A Non-Reversible Rejection-Free Markov Chain Monte Carlo Method
- The Variational Formulation of the Fokker--Planck Equation
- The zig-zag process and super-efficient sampling for Bayesian analysis of big data
- Theoretical Guarantees for Approximate Sampling from Smooth and Log-Concave Densities
- User-friendly guarantees for the Langevin Monte Carlo with inaccurate gradient
Cited in
(43)- Accelerated information gradient flow
- Efficient stochastic optimisation by unadjusted Langevin Monte Carlo. Application to maximum marginal likelihood and empirical Bayesian estimation
- Complexity of zigzag sampling algorithm for strongly log-concave distributions
- High-dimensional MCMC with a standard splitting scheme for the underdamped Langevin diffusion
- Polynomial accelerated MCMC and other sampling algorithms inspired by computational optimization
- scientific article; zbMATH DE number 7626720 (Why is no real title available?)
- scientific article; zbMATH DE number 7626754 (Why is no real title available?)
- Sampling can be faster than optimization
- Convexization in Markov chain Monte Carlo
- Optimal convergence rate of Hamiltonian Monte Carlo for strongly logconcave distributions
- Projected Wasserstein Gradient Descent for High-Dimensional Bayesian Inference
- From Optimization to Sampling Through Gradient Flows
- Birth–death dynamics for sampling: global convergence, approximations and their asymptotics
- On explicit L^2-convergence rate estimate for underdamped Langevin dynamics
- Exponential entropy dissipation for weakly self-consistent Vlasov-Fokker-Planck equations
- The entropy production of stationary diffusions
- Gradient-Based Markov Chain Monte Carlo for Bayesian Inference With Non-differentiable Priors
- Uniform-in-time propagation of chaos for kinetic mean field Langevin dynamics
- Tail probability estimates of continuous-time simulated annealing processes
- Optimal friction matrix for underdamped Langevin sampling
- An entropic approach for Hamiltonian Monte Carlo: the idealized case
- Convergence of simulated annealing using kinetic Langevin dynamics
- Rapid convergence of the unadjusted Langevin algorithm: isoperimetry suffices
- Discrete-time simulated annealing: a convergence analysis via the Eyring-Kramers law
- Appropriate state-dependent friction coefficient accelerates kinetic Langevin dynamics
- Symplectic techniques for stochastic differential equations on reductive Lie groups with applications to Langevin diffusions
- Error bounds for particle gradient descent, and extensions of the log-Sobolev and Talagrand inequalities
- Gradient-adjusted underdamped Langevin dynamics for sampling
- Parallelized midpoint randomization for Langevin Monte Carlo
- Convergence in total variation for the kinetic Langevin algorithm
- Resolving the mixing time of the Langevin algorithm to its stationary distribution for log-concave sampling
- Tensor train based sampling algorithms for approximating regularized Wasserstein proximal operators
- Accelerating optimization over the space of probability measures
- HMC and underdamped Langevin united in the unadjusted convex smooth case
- Query lower bounds for log-concave sampling
- Fisher information lower bounds for sampling
- Faster high-accuracy log-concave sampling via algorithmic warm starts
- A gentle introduction to gradient-based optimization and variational inequalities for machine learning
- Convergence rates for an adaptive biasing potential scheme from a Wasserstein optimization perspective
- Graph-accelerated Markov chain Monte Carlo using approximate samples
- Reflection coupling for unadjusted generalized Hamiltonian Monte Carlo in the nonconvex stochastic gradient case
- Analysis of kinetic Langevin Monte Carlo under the stochastic exponential Euler discretization from underdamped all the way to overdamped
- Kinetic interacting particle Langevin Monte Carlo
This page was built for publication: Is there an analog of Nesterov acceleration for gradient-based MCMC?
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2040101)
