Langevin Monte Carlo: random coordinate descent and variance reduction
Langevin Monte Carlo: random coordinate descent and variance reduction
复制标题
DOI：
--
复制
发表时间：
2020-07
期刊：
影响因子：
--
通讯作者：
Zhiyan Ding;Qin Li
中科院分区：
文献类型：
--
作者：
Zhiyan Ding;Qin Li
从$\mathbb{R}^d$（其中$d\gg 1$）上的对数凹分布函数采样是一个有着广泛应用的流行问题。本文研究了随机坐标下降法（RCD）在朗之万蒙特卡罗（LMC）抽样方法中的应用，发现了两个方面的理论：1。在LMC上直接应用RCD确实减少了每次迭代的有限差分近似的数量，但它引起了大的方差误差项。然后需要更多的迭代，并且最终该方法没有获得计算优势; 2.当方差减少技术（如佐贺和SVRG）被纳入RCD-LMC，方差误差项减少。新的方法，相比香草LMC，减少$d$ folds的总计算成本，并实现最优的成本率。我们进行调查，在过阻尼和欠阻尼设置。
Sampling from a log-concave distribution function on $\mathbb{R}^d$ (with $d\gg 1$) is a popular problem that has wide applications. In this paper we study the application of random coordinate descent method (RCD) on the Langevin Monte Carlo (LMC) sampling method, and we find two sides of the theory: 1. The direct application of RCD on LMC does reduce the number of finite differencing approximations per iteration, but it induces a large variance error term. More iterations are then needed, and ultimately the method gains no computational advantage; 2. When variance reduction techniques (such as SAGA and SVRG) are incorporated in RCD-LMC, the variance error term is reduced. The new methods, compared to the vanilla LMC, reduce the total computational cost by $d$ folds, and achieve the optimal cost rate. We perform our investigations in both overdamped and underdamped settings.