Reducing Communication in Proximal Newton Methods for Sparse Least Squares Problems
Reducing Communication in Proximal Newton Methods for Sparse Least Squares Problems
复制标题
DOI：
10.1145/3225058.3225131
复制
发表时间：
2018-08
期刊：
影响因子：
--
通讯作者：
Saeed Soori;Aditya Devarakonda;Zachary Blanco;J. Demmel;M. Gürbüzbalaban;M. Dehnavi
中科院分区：
文献类型：
--
作者：
Saeed Soori;Aditya Devarakonda;Zachary Blanco;J. Demmel;M. Gürbüzbalaban;M. Dehnavi
近似牛顿法是一种求解11正则化最小二乘问题的迭代算法。这些方法的分布式内存实现已经变得流行，因为它们能够分析大规模的机器学习问题。然而，这些方法的可伸缩性受到现代分布式体系结构通信开销的限制。为了在计算复杂度和数据通信之间找到一个有效的平衡点，我们提出了一种随机方差减少的近端方法以及迭代重叠和hessian重用。提出的RC-SFSITA算法在不改变带宽成本的情况下将延迟成本降低了k倍。RC-SFISTA在MPI和Spark上实现，并与最先进的框架ProxCoCoA进行了比较。RC-SFISTA的性能在1到512个节点上进行了多次基准测试，与ProxCoCoA相比，其速度提高了12倍，具有优于原始算法的缩放特性。
Proximal Newton methods are iterative algorithms that solve l1-regularized least squares problems. Distributed-memory implementation of these methods have become popular since they enable the analysis of large-scale machine learning problems. However, the scalability of these methods is limited by the communication overhead on modern distributed architecture. We propose a stochastic variance-reduced proximal method along with iteration-overlapping and Hessian-reuse to find an efficient trade-off between computation complexity and data communication. The proposed RC-SFSITA algorithm reduces latency costs by a factor of k without altering bandwidth costs. RC-SFISTA is implemented on both MPI and Spark and compared to the state-of-the-art framework, ProxCoCoA. The performance of RC-SFISTA is evaluated on 1 to 512 nodes for multiple benchmarks and demonstrates speedups of up to 12× compared to ProxCoCoA with scaling properties that outperform the original algorithm.