Random Coordinate Underdamped Langevin Monte Carlo
This work addresses efficiency issues in MCMC sampling for high-dimensional problems, offering a method that reduces computational costs, though it is incremental as it builds on existing ULMC techniques.
The paper tackles the high computational cost of Underdamped Langevin Monte Carlo (ULMC) in high dimensions by proposing Random Coordinate ULMC (RC-ULMC), which updates only one coordinate per iteration, and shows it is always cheaper than classical ULMC, with significant cost reductions for highly skewed, high-dimensional problems.
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.