Pegasos: Primal estimated sub-GrAdient sOlver for SVM

Shai Shalev-Shwartz, Yoram Singer, Nathan Srebro

Research output: Contribution to conferencePaper

593 Scopus citations

Abstract

We describe and analyze a simple and effective iterative algorithm for solving the optimization problem cast by Support Vector Machines (SVM). Our method alternates between stochastic gradient descent steps and projection steps. We prove that the number of iterations required to obtain a solution of accuracy is (1/). In contrast, previous analyses of stochastic gradient descent methods require (1/2) iterations. As in previously devised SVM solvers, the number of iterations also scales linearly with 1/, where is the regularization parameter of SVM. For a linear kernel, the total run-time of our method is (d/()), where d is a bound on the number of non-zero features in each example. Since the run-time does not depend directly on the size of the training set, the resulting algorithm is especially suited for learning from large datasets. Our approach can seamlessly be adapted to employ non-linear kernels while working solely on the primal objective function. We demonstrate the efficiency and applicability of our approach by conducting experiments on large text classification problems, comparing our solver to existing state-of-the-art SVM solvers. For example, it takes less than 5 seconds for our solver to converge when solving a text classification problem from Reuters Corpus Volume 1 (RCV1) with 800,000 training examples.

Original languageEnglish (US)
Pages807-814
Number of pages8
DOIs
StatePublished - Aug 23 2007
Externally publishedYes
Event24th International Conference on Machine Learning, ICML 2007 - Corvalis, OR, United States
Duration: Jun 20 2007Jun 24 2007

Other

Other24th International Conference on Machine Learning, ICML 2007
CountryUnited States
CityCorvalis, OR
Period6/20/076/24/07

All Science Journal Classification (ASJC) codes

  • Software
  • Human-Computer Interaction
  • Computer Vision and Pattern Recognition
  • Computer Networks and Communications

Fingerprint Dive into the research topics of 'Pegasos: Primal estimated sub-GrAdient sOlver for SVM'. Together they form a unique fingerprint.

  • Cite this

    Shalev-Shwartz, S., Singer, Y., & Srebro, N. (2007). Pegasos: Primal estimated sub-GrAdient sOlver for SVM. 807-814. Paper presented at 24th International Conference on Machine Learning, ICML 2007, Corvalis, OR, United States. https://doi.org/10.1145/1273496.1273598