Random Coordinate Underdamped Langevin Monte Carlo
Random Coordinate Underdamped Langevin Monte Carlo
复制标题
DOI：
--
复制
发表时间：
2020-10
期刊：
影响因子：
--
通讯作者：
Zhiyan Ding;Qin Li;Jianfeng Lu;Stephen J. Wright
中科院分区：
文献类型：
--
作者：
Zhiyan Ding;Qin Li;Jianfeng Lu;Stephen J. Wright
欠阻尼朗之万蒙特卡罗（ULMC）是一种流行的马尔可夫链蒙特卡罗抽样方法。它需要在每次迭代时计算对数密度的全梯度，如果问题的维数很高，则这是一个昂贵的操作。我们提出了一种称为随机坐标ULMC（RC-ULMC）的采样方法，该方法在每次迭代时选择一个要更新的坐标，而其他坐标不变。我们研究了RC-ULMC的计算复杂度，并将其与经典的ULMC进行了比较。我们表明，RC-ULMC总是比经典的ULMC便宜，具有显着的成本降低时，问题是高度偏斜和高维。我们的复杂性约束RC-ULMC也紧的维度依赖。
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.