Stochastic Runge-Kutta Accelerates Langevin Monte Carlo and Beyond

Abstract

Sampling with Markov chain Monte Carlo methods often amounts to discretizing some continuous-time dynamics with numerical integration. In this paper, we establish the convergence rate of sampling algorithms obtained by discretizing smooth Itô diffusions exhibiting fast Wasserstein-$2$ contraction, based on local deviation properties of the integration scheme. In particular, we study a sampling algorithm constructed by discretizing the overdamped Langevin diffusion with the method of stochastic Runge-Kutta. For strongly convex potentials that are smooth up to a certain order, its iterates converge to the target distribution in $2$-Wasserstein distance in $\tilde{\mathcal{O}}(d{\epsilon }^{-2/3})$ iterations. This improves upon the best-known rate for strongly log-concave sampling based on the overdamped Langevin equation using only the gradient oracle without adjustment. In addition, we extend our analysis of stochastic Runge-Kutta methods to uniformly dissipative diffusions with possibly non-convex potentials and show they achieve better rates compared to the Euler-Maruyama scheme in terms of the dependence on tolerance $\epsilon$. Numerical studies show that these algorithms lead to better stability and lower asymptotic errors.

arXiv comment56 pages; update acknowledgements

References in corpus (18)

• MCMC using Hamiltonian dynamics
• Equivalence of distance-based and RKHS-based statistics in hypothesis testing
• User-friendly guarantees for the Langevin Monte Carlo with inaccurate gradient
• Non-convex learning via Stochastic Gradient Langevin Dynamics: a nonasymptotic analysis
• Sampling Can Be Faster Than Optimization
• On the Convergence of Stochastic Gradient MCMC Algorithms with High-Order Integrators
• Underdamped Langevin MCMC: A non-asymptotic analysis
• Log-concave sampling: Metropolis-Hastings algorithms are fast
• A Kernel Test of Goodness of Fit
• Convergence of Langevin MCMC in KL-divergence
• Measuring Sample Quality with Kernels
• Direct Runge-Kutta Discretization Achieves Acceleration
• High-Order Langevin Diffusion Yields an Accelerated MCMC Algorithm
• Is There an Analog of Nesterov Acceleration for MCMC?
• Higher Order Langevin Monte Carlo Algorithm
• Fast mixing of Metropolized Hamiltonian Monte Carlo: Benefits of multi-step gradients
• Exotic aromatic B-series for the study of long time integrators for a class of ergodic SDEs
• Couplings and quantitative contraction rates for Langevin dynamics

Cited by in corpus (10)

• Generative Modeling with Denoising Auto-Encoders and Langevin Sampling
• On the Ergodicity, Bias and Asymptotic Normality of Randomized Midpoint Sampling Method
• A Contour Stochastic Gradient Langevin Dynamics Algorithm for Simulations of Multi-modal Distributions
• Complexity of zigzag sampling algorithm for strongly log-concave distributions
• Sqrt(d) Dimension Dependence of Langevin Monte Carlo
• Estimating Normalizing Constants for Log-Concave Distributions: Algorithms and Lower Bounds
• Hessian-Free High-Resolution Nesterov Acceleration for Sampling
• Learning Partially Known Stochastic Dynamics with Empirical PAC Bayes
• Convergence of Langevin Monte Carlo in Chi-Squared and Renyi Divergence
• Particle Dual Averaging: Optimization of Mean Field Neural Networks with Global Convergence Rate Analysis