Distributed Box-Constrained Quadratic Optimization for Dual Linear SVM
Ching-pei Lee, Dan Roth · 2015
Training machine learning models sometimes needs to be done on large amounts of data that exceed the capacity of a single machine, motivat-ing recent works on developing algorithms that train in a distributed fashion. This paper pro-poses an efficient box-constrained quadratic opti-mization algorithm for distributedly training lin-ear support vector machines (SVMs) with large data. Our key technical contribution is an ana-lytical solution to the problem of computing the optimal step size at each iteration, using an ef-ficient method that requires only O(1) commu-nication cost to ensure fast convergence. With this optimal step size, our approach is superior to other methods by possessing global linear con-vergence, or, equivalently, O(log(1/)) iteration complexity for an -accurate solution, for dis-tributedly solving the non-strongly-convex linear SVM dual problem. Experiments also show that our method is significantly faster than state-of-the-art distributed linear SVM algorithms includ-ing DSVM-AVE, DisDCA and TRON. 1.