@inproceedings{29fdeec50f37405884e2cb303e974f23,
title = "Beating SGD: Learning SVMs in sublinear time",
abstract = "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!",
author = "Elad Hazan and Tomer Koren and Nathan Srebro",
year = "2011",
language = "English (US)",
isbn = "9781618395993",
series = "Advances in Neural Information Processing Systems 24: 25th Annual Conference on Neural Information Processing Systems 2011, NIPS 2011",
publisher = "Neural Information Processing Systems",
booktitle = "Advances in Neural Information Processing Systems 24",
note = "25th Annual Conference on Neural Information Processing Systems 2011, NIPS 2011 ; Conference date: 12-12-2011 Through 14-12-2011",
}