Breaking Locality Accelerates Block Gauss-Seidel
Breaking Locality Accelerates Block Gauss-Seidel
复制标题
DOI：
--
复制
发表时间：
2017-01
期刊：
影响因子：
--
通讯作者：
Stephen Tu;S. Venkataraman;Ashia C. Wilson;Alex Gittens;Michael I. Jordan;B. Recht
中科院分区：
文献类型：
--
作者：
Stephen Tu;S. Venkataraman;Ashia C. Wilson;Alex Gittens;Michael I. Jordan;B. Recht
Nesterov 和 Stich 最近的工作表明，在提前选择固定坐标划分的情况下，动量可用于加速块 Gauss-Seidel 的收敛速度。我们表明，这种设置限制性太大，通过使用随机采样坐标运行非加速高斯-赛德尔来构造破坏局部性的实例，其性能大大优于使用任何固定分区的加速高斯-赛德尔。受这一发现的启发，我们分析了随机坐标采样设置中的加速块 Gauss-Seidel 算法。我们的分析利用新的数据相关参数捕获了加速的好处，当矩阵子块条件良好时，该参数表现良好。根据经验，我们表明，与非加速 Gauss-Seidel 和经典共轭梯度算法相比，具有随机坐标采样的加速 Gauss-Seidel 为大规模机器学习任务提供了加速。
Recent work by Nesterov and Stich showed that momentum can be used to accelerate the rate of convergence for block Gauss-Seidel in the setting where a fixed partitioning of the coordinates is chosen ahead of time. We show that this setting is too restrictive, constructing instances where breaking locality by running non-accelerated Gauss-Seidel with randomly sampled coordinates substantially outperforms accelerated Gauss-Seidel with any fixed partitioning. Motivated by this finding, we analyze the accelerated block Gauss-Seidel algorithm in the random coordinate sampling setting. Our analysis captures the benefit of acceleration with a new data-dependent parameter which is well behaved when the matrix sub-blocks are well-conditioned. Empirically, we show that accelerated Gauss-Seidel with random coordinate sampling provides speedups for large scale machine learning tasks when compared to non-accelerated Gauss-Seidel and the classical conjugate-gradient algorithm.