Abstract
We study two important SVM variants: hardmargin SVM (for linearly separable cases) and nuSVM (for linearly nonseparable cases). We propose new algorithms from the perspective of saddle point optimization. Our algorithms achieve (1epsilon)approximations with running time 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 nuSVM is based on quadratic programming approach which requires Omega(n^2 d) time in worst case [Joachims, 1998; Platt, 1999]. In the paper, we provide the first nearly linear time algorithm for nuSVM. The current best algorithm for hard margin SVM achieved by Gilbert algorithm [GĂ¤rtner and Jaggi, 2009] 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 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.
BibTeX  Entry
@InProceedings{huang_et_al:LIPIcs:2018:8851,
author = {Lingxiao Huang and Yifei Jin and Jian Li},
title = {{SVM via Saddle Point Optimization: New Bounds and Distributed Algorithms}},
booktitle = {16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2018)},
pages = {25:125:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770682},
ISSN = {18688969},
year = {2018},
volume = {101},
editor = {David Eppstein},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/8851},
URN = {urn:nbn:de:0030drops88515},
doi = {10.4230/LIPIcs.SWAT.2018.25},
annote = {Keywords: nuSVM, hardmargin SVM, saddle point optimization, distributed algorithm}
}
Keywords: 

nuSVM, hardmargin SVM, saddle point optimization, distributed algorithm 
Collection: 

16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2018) 
Issue Date: 

2018 
Date of publication: 

04.06.2018 