Communication-Efficient Distributed Block Minimization for Nonlinear Kernel Machines
Communication-Efficient Distributed Block Minimization for Nonlinear Kernel Machines
复制标题
DOI：
10.1145/3097983.3098080
复制
发表时间：
2017-08
期刊：
影响因子：
--
通讯作者：
Cho-Jui Hsieh;Si Si-Si;I. Dhillon
中科院分区：
文献类型：
--
作者：
Cho-Jui Hsieh;Si Si-Si;I. Dhillon
非线性核机器常常在各种任务上产生优异的预测性能；然而，它们面临着严峻的计算挑战。在这篇文章中，我们展示了如何克服使用多台计算机加速内核机器的重要挑战。特别是，我们开发了一个并行区块最小化框架，并在求解非线性核支持向量机和Logistic回归问题上证明了其良好的可扩展性。我们的框架通过形成海森矩阵的块对角线近似，将问题分成更小的子问题。然后，子问题被近似并行地解决。在此基础上，利用核机器的问题结构，设计了一种通信效率高的线搜索算法，以保证目标函数值的充分约简。我们证明了该方法的全局线性收敛速度，并且我们的分析涵盖了强凸函数和一些非强凸函数。将该算法应用于分布式系统中大规模核支持向量机问题的求解，与已有的并行求解器相比有了显著的改进。例如，在具有50万个样本的Covtype数据集上，我们的算法可以在32台机器上在20秒内获得96%的近似解，而所有其他并行核支持向量机求解器需要2000秒以上的时间才能获得95%的精度。此外，我们的算法是第一个可以扩展到海量数据集的分布式核支持向量机求解器。在KDDB数据集(2000万个样本和3000万个特征)上，我们的并行求解器可以在半小时内使用32台机器总共640个核来计算内核支持向量机解，而现有的求解器无法扩展到这个数据集。
Nonlinear kernel machines often yield superior predictive performance on various tasks; however, they suffer from severe computational challenges. In this paper, we show how to overcome the important challenge of speeding up kernel machines using multiple computers. In particular, we develop a parallel block minimization framework, and demonstrate its good scalability in solving nonlinear kernel SVM and logistic regression. Our framework proceeds by dividing the problem into smaller subproblems by forming a block-diagonal approximation of the Hessian matrix. The subproblems are then solved approximately in parallel. After that, a communication efficient line search procedure is developed to ensure sufficient reduction of the objective function value by exploiting the problem structure of kernel machines. We prove global linear convergence rate of the proposed method with a wide class of subproblem solvers, and our analysis covers strongly convex and some non-strongly convex functions. We apply our algorithm to solve large-scale kernel SVM problems on distributed systems, and show a significant improvement over existing parallel solvers. As an example, on the covtype dataset with half-a-million samples, our algorithm can obtain an approximate solution with 96% accuracy in 20 seconds using 32 machines, while all the other parallel kernel SVM solvers require more than 2000 seconds to achieve a solution with 95% accuracy. Moreover, our algorithm is the first distributed kernel SVM solver that can scale to massive data sets. On the KDDB dataset (20 million samples and 30 million features), our parallel solver can compute the kernel SVM solution within half an hour using 32 machines with 640 cores in total, while existing solvers can not scale to this dataset.