Randomness and permutations in coordinate descent methods
Randomness and permutations in coordinate descent methods
复制标题
DOI：
10.1007/s10107-019-01438-4
复制
发表时间：
2018-03
影响因子：
2.7
通讯作者：
Mert Gurbuzbalaban;A. Ozdaglar;N. D. Vanli;Stephen J. Wright
中科院分区：
文献类型：
--
作者：
Mert Gurbuzbalaban;A. Ozdaglar;N. D. Vanli;Stephen J. Wright
我们考虑凸二次问题的精确线搜索坐标下降（CD）方法。我们的主要重点是研究的CD方法，使用随机排列在每个时代的性能，并比较它的CD方法，使用确定性的顺序和随机采样与替换的性能。我们专注于一类凸二次问题的对角占优的Hessian矩阵，我们表明，使用随机置换，而不是随机与替换采样提高了CD方法在最坏情况下的性能。此外，我们证明，作为海森矩阵变得更加对角占优，通过使用随机排列获得的性能改善增加。我们还表明，对于这个问题类，使用任何固定的确定性顺序产生一个上级性能比使用随机排列。我们提出了详细的理论分析，在文献中使用的三种不同的收敛标准，并支持我们的理论结果与数值实验。
We consider coordinate descent (CD) methods with exact line search on convex quadratic problems. Our main focus is to study the performance of the CD method that use random permutations in each epoch and compare it to the performance of the CD methods that use deterministic orders and random sampling with replacement. We focus on a class of convex quadratic problems with a diagonally dominant Hessian matrix, for which we show that using random permutations instead of random with-replacement sampling improves the performance of the CD method in the worst-case. Furthermore, we prove that as the Hessian matrix becomes more diagonally dominant, the performance improvement attained by using random permutations increases. We also show that for this problem class, using any fixed deterministic order yields a superior performance than using random permutations. We present detailed theoretical analyses with respect to three different convergence criteria that are used in the literature and support our theoretical results with numerical experiments.