Random Coordinate Langevin Monte Carlo
Random Coordinate Langevin Monte Carlo
复制标题
DOI：
--
复制
发表时间：
2020-10
期刊：
影响因子：
--
通讯作者：
Zhiyan Ding;Qin Li;Jianfeng Lu;Stephen J. Wright
中科院分区：
文献类型：
--
作者：
Zhiyan Ding;Qin Li;Jianfeng Lu;Stephen J. Wright
Langevin Monte Carlo (LMC) 是一种流行的马尔可夫链蒙特卡罗采样方法。一个缺点是它需要在每次迭代时计算完整梯度，如果问题的维度很高，那么这是一项昂贵的操作。我们提出了一种新的采样方法：随机坐标LMC（RC-LMC）。在每次迭代中，随机选择一个坐标，通过沿该方向的偏导数加上噪声的倍数进行更新，并且所有其他坐标保持不变。我们研究了 RC-LMC 的总复杂度，并将其与经典 LMC 的对数凹概率分布进行比较。当对数密度的梯度为 Lipschitz 时，如果对数密度对于高维问题高度倾斜，则 RC-LMC 比经典 LMC 更便宜；当对数密度的梯度和 Hessian 矩阵均为 Lipschitz 时，RC-LMC 总是比经典 LMC 便宜，其成本与问题维度的平方根成正比。在后一种情况下，我们对复杂性的估计相对于维度来说是尖锐的。
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.