  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.
