Random Coordinate Underdamped Langevin Monte Carlo
arXiv:2010.11366
Abstract
The Underdamped Langevin Monte Carlo (ULMC) is a popular Markov chain Monte Carlo sampling method. It requires the computation of the full gradient of the log-density at each iteration, an expensive operation if the dimension of the problem is high. We propose a sampling method called Random Coordinate ULMC (RC-ULMC), which selects a single coordinate at each iteration to be updated and leaves the other coordinates untouched. We investigate the computational complexity of RC-ULMC and compare it with the classical ULMC for strongly log-concave probability distributions. We show that RC-ULMC is always cheaper than the classical ULMC, with a significant cost reduction when the problem is highly skewed and high dimensional. Our complexity bound for RC-ULMC is also tight in terms of dimension dependence.
References in corpus (11)
- The Ensemble Kalman Filter for Inverse Problems
- User-friendly guarantees for the Langevin Monte Carlo with inaccurate gradient
- Diffusion limits of the random walk Metropolis algorithm in high dimensions
- Underdamped Langevin MCMC: A non-asymptotic analysis
- Optimal scaling and diffusion limits for the Langevin algorithm in high dimensions
- The Randomized Midpoint Method for Log-Concave Sampling
- Couplings and quantitative contraction rates for Langevin dynamics
- Ensemble Kalman Inversion for nonlinear problems: weights, consistency, and variance bounds
- Wasserstein contraction properties for hypoelliptic diffusions
- On the Ergodicity, Bias and Asymptotic Normality of Randomized Midpoint Sampling Method
- Random Coordinate Langevin Monte Carlo