SVM via Saddle Point Optimization: New Bounds and Distributed Algorithms
This provides faster algorithms for SVM training, beneficial for machine learning practitioners dealing with high-dimensional, large datasets, though it is incremental as it builds on existing optimization frameworks.
The paper tackles the problem of efficiently solving two SVM variants (hard-margin and ν-SVM) by proposing new algorithms based on saddle point optimization, achieving (1-ε)-approximations with nearly linear time complexity of Õ(nd + n√(d/ε)) and improved distributed communication costs.
We study two important SVM variants: hard-margin SVM (for linearly separable cases) and $ν$-SVM (for linearly non-separable cases). We propose new algorithms from the perspective of saddle point optimization. Our algorithms achieve $(1-ε)$-approximations with running time $\tilde{O}(nd+n\sqrt{d / ε})$ for both variants, where $n$ is the number of points and $d$ is the dimensionality. To the best of our knowledge, the current best algorithm for $ν$-SVM is based on quadratic programming approach which requires $Ω(n^2 d)$ time in worst case~\cite{joachims1998making,platt199912}. In the paper, we provide the first nearly linear time algorithm for $ν$-SVM. The current best algorithm for hard margin SVM achieved by Gilbert algorithm~\cite{gartner2009coresets} requires $O(nd / ε)$ time. Our algorithm improves the running time by a factor of $\sqrt{d}/\sqrtε$. Moreover, our algorithms can be implemented in the distributed settings naturally. We prove that our algorithms require $\tilde{O}(k(d +\sqrt{d/ε}))$ communication cost, where $k$ is the number of clients, which almost matches the theoretical lower bound. Numerical experiments support our theory and show that our algorithms converge faster on high dimensional, large and dense data sets, as compared to previous methods.