Beating SGD: Learning SVMs in Sublinear Time

Part of Advances in Neural Information Processing Systems 24 (NIPS 2011)

Bibtex »Metadata »Paper »

Authors

Elad Hazan, Tomer Koren, Nati Srebro

Abstract

<p>We present an optimization approach for linear SVMs based on a stochastic primal-dual approach, where the primal step is akin to an importance-weighted SGD, and the dual step is a stochastic update on the importance weights. This yields an optimization method with a sublinear dependence on the training set size, and the first method for learning linear SVMs with runtime less then the size of the training set required for learning!</p>