SVM via Saddle Point Optimization: New Bounds and Distributed Algorithms
  We study two important SVM variants: hard-margin SVM (for linearly separable
cases) and $\nu$-SVM (for linearly non-separable cases). We propose new
algorithms from the perspective of saddle point optimization. Our algorithms
achieve $(1-\epsilon)$-approximations with running time $\tilde{O}(nd+n\sqrt{d
/ \epsilon})$ 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 $\nu$-SVM is based on quadratic programming approach which requires
$\Omega(n^2 d)$ time in worst case~\cite{joachims1998making,platt199912}. In
the paper, we provide the first nearly linear time algorithm for $\nu$-SVM. The
current best algorithm for hard margin SVM achieved by Gilbert
algorithm~\cite{gartner2009coresets} requires $O(nd / \epsilon )$ time. Our
algorithm improves the running time by a factor of $\sqrt{d}/\sqrt{\epsilon}$.
Moreover, our algorithms can be implemented in the distributed settings
naturally. We prove that our algorithms require $\tilde{O}(k(d
+\sqrt{d/\epsilon}))$ 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.
