Markov chain block coordinate descent
Markov chain block coordinate descent
复制标题
DOI：
10.1007/s10589-019-00140-7
复制
发表时间：
2018-11
影响因子：
2.2
通讯作者：
Tao Sun;Yuejiao Sun;Yangyang Xu;W. Yin
中科院分区：
文献类型：
--
作者：
Tao Sun;Yuejiao Sun;Yangyang Xu;W. Yin
块坐标梯度下降法（BCD）是求解大规模优化问题的一种有效方法。本文考虑BCD方法，连续更新一系列的块选择根据马尔可夫链。这种区块选择既不是独立同分布的。随机的或循环的。另一方面，它是一个自然的选择，一些应用在分布式优化和马尔可夫决策过程，其中i.i.d.随机和循环选择要么是不可行的要么是非常昂贵的。利用马尔可夫链的混合时间性质，证明了马尔可夫链BCD对于极小化Lipschitz可微函数的收敛性，该函数可以是非凸的。当函数是凸的和强凸的，我们建立了次线性和线性收敛速度，分别。我们还提出了一种马尔可夫链惯性BCD方法。最后，我们讨论了潜在的应用。
The method of block coordinate gradient descent (BCD) has been a powerful method for large-scale optimization. This paper considers the BCD method that successively updates a series of blocks selected according to a Markov chain. This kind of block selection is neither i.i.d. random nor cyclic. On the other hand, it is a natural choice for some applications in distributed optimization and Markov decision process, where i.i.d. random and cyclic selections are either infeasible or very expensive. By applying mixing-time properties of a Markov chain, we prove convergence of Markov chain BCD for minimizing Lipschitz differentiable functions, which can be nonconvex. When the functions are convex and strongly convex, we establish both sublinear and linear convergence rates, respectively. We also present a method of Markov chain inertial BCD. Finally, we discuss potential applications.