NIPS Proceedingsβ

Beating SGD: Learning SVMs in Sublinear Time

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

[PDF] [BibTeX]



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!