# Random Coordinate Langevin Monte Carlo

arXiv: https://arxiv.org/abs/2010.01405 · HTML: https://mlsanity.com/paper/2010.01405/

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 3 Oct 2020.

## Built on by (most cited first, 7 of 7)

- [The query complexity of sampling from strongly log-concave distributions in one dimension](https://mlsanity.com/paper/2105.14163/) (2021)
- [Entropy contraction of the Gibbs sampler under log-concavity](https://mlsanity.com/paper/2410.00858/) (2024)
- [Query lower bounds for log-concave sampling](https://mlsanity.com/paper/2304.02599/) (2023)
- [Learning Rate Free Sampling in Constrained Domains](https://mlsanity.com/paper/2305.14943/) (2023)
- [Provable Accuracy Bounds for Hybrid Dynamical Optimization and Sampling](https://mlsanity.com/paper/2410.06397/) (2024)
- [Subspace Langevin Monte Carlo](https://mlsanity.com/paper/2412.13928/) (2024)
- [Spectral gap of Metropolis-within-Gibbs under log-concavity](https://mlsanity.com/paper/2509.26175/) (2025)

## Abstract (arXiv)

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.