Random Coordinate Langevin Monte Carlo
This work addresses the scalability issue of MCMC sampling for high-dimensional problems, offering a more efficient method for practitioners in statistics and machine learning, though it is incremental as it builds on LMC.
The authors tackled the high computational cost of Langevin Monte Carlo (LMC) by proposing Random Coordinate LMC (RC-LMC), which updates only one coordinate per iteration, reducing complexity; for log-concave distributions with Lipschitz gradients and Hessians, RC-LMC is cheaper than classical LMC by a factor proportional to the square root of the dimension.
Langevin Monte Carlo (LMC) is a popular Markov chain Monte Carlo sampling method. One drawback is that it requires the computation of the full gradient at each iteration, an expensive operation if the dimension of the problem is high. We propose a new sampling method: Random Coordinate LMC (RC-LMC). At each iteration, a single coordinate is randomly selected to be updated by a multiple of the partial derivative along this direction plus noise, and all other coordinates remain untouched. We investigate the total complexity of RC-LMC and compare it with the classical LMC for log-concave probability distributions. When the gradient of the log-density is Lipschitz, RC-LMC is less expensive than the classical LMC if the log-density is highly skewed for high dimensional problems, and when both the gradient and the Hessian of the log-density are Lipschitz, RC-LMC is always cheaper than the classical LMC, by a factor proportional to the square root of the problem dimension. In the latter case, our estimate of complexity is sharp with respect to the dimension.