论文标题
随机坐标Langevin Monte Carlo
Random Coordinate Langevin Monte Carlo
论文作者
论文摘要
Langevin Monte Carlo（LMC）是一种流行的马尔可夫链蒙特卡洛采样方法。一个缺点是，它需要在每次迭代中计算完整梯度，如果问题的尺寸很高，则需要昂贵的操作。我们提出了一种新的采样方法：随机坐标LMC（RC-LMC）。在每次迭代中，单个坐标都会随机选择以通过沿该方向加噪声的部分导数的倍数更新，并且所有其他坐标仍然没有受到影响。我们研究了RC-LMC的总复杂性，并将其与经典的LMC进行比较，以进行对数符合概率分布。当对数密度的梯度是Lipschitz时，如果对数密度高度偏向高维问题，RC-LMC的价格低于经典LMC，而当对数密度的梯度和Hessian均为Lipschitz时，RC-LMC始终比经典的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.
