  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.
