Part of Advances in Neural Information Processing Systems 24 (NIPS 2011)
Elad Hazan, Tomer Koren, Nati Srebro
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!