Pegasos

Pegasos: primal estimated sub-gradient solver for SVM. We describe and analyze a simple and effective stochastic sub-gradient descent algorithm for solving the optimization problem cast by Support Vector Machines (SVM). We prove that the number of iterations required to obtain a solution of accuracy ϵ is O (1/ϵ) , where each iteration operates on a single training example. In contrast, previous analyses of stochastic gradient descent methods for SVMs 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 O (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 also extends to non-linear kernels while working solely on the primal objective function, though in this case the runtime does depend linearly on the training set size. Our algorithm is particularly well suited for large text classification problems, where we demonstrate an order-of-magnitude speedup over previous SVM learning methods


References in zbMATH (referenced in 103 articles , 1 standard article )

Showing results 61 to 80 of 103.
Sorted by year (citations)
  1. Do, Thanh-Nghi: Non-linear classification of massive datasets with a parallel algorithm of local support vector machines (2015) ioport
  2. Do, Thanh-Nghi; Poulet, François: Parallel multiclass logistic regression for classifying large scale image datasets (2015) ioport
  3. Gu, Bin; Sheng, Victor S.; Wang, Zhijie; Ho, Derek; Osman, Said; Li, Shuo: Incremental learning for (\nu)-support vector regression (2015)
  4. Kuang, Zhanghui; Wong, Kwan-Yee K.: Relatively-paired space analysis: learning a latent common space from relatively-paired observations (2015)
  5. Mareček, Jakub; Richtárik, Peter; Takáč, Martin: Distributed block coordinate descent for minimizing partially separable functions (2015)
  6. Mokhtari, Aryan; Ribeiro, Alejandro: Global convergence of online limited memory BFGS (2015)
  7. Prasse, Paul; Sawade, Christoph; Landwehr, Niels; Scheffer, Tobias: Learning to identify concise regular expressions that describe email campaigns (2015)
  8. Sopyła, Krzysztof; Drozda, Paweł: Stochastic gradient descent with Barzilai-Borwein update step for SVM (2015)
  9. Xu, Yangyang; Yin, Wotao: Block stochastic gradient iteration for convex and nonconvex optimization (2015)
  10. Yang, Tianbao; Mahdavi, Mehrdad; Jin, Rong; Zhu, Shenghuo: An efficient primal dual prox method for non-smooth optimization (2015)
  11. Alama, Jesse; Heskes, Tom; Kühlwein, Daniel; Tsivtsivadze, Evgeni; Urban, Josef: Premise selection for mathematics by corpus analysis and kernel methods (2014)
  12. Couellan, Nicolas; Jan, Sophie: Incremental accelerated gradient methods for SVM classification: study of the constrained approach (2014)
  13. Feng, Hui; Jiang, ZiDong; Hu, Bo; Zhang, JianQiu: The incremental subgradient methods on distributed estimations in-network (2014)
  14. Lee, Ching-Pei; Lin, Chih-Jen: Large-scale linear rankSVM (2014)
  15. Mančev, Dejan; Todorović, Branimir: A primal sub-gradient method for structured classification with the averaged sum loss (2014)
  16. Mandal, Indrajit; Sairam, N.: New machine-learning algorithms for prediction of Parkinson’s disease (2014)
  17. Ñanculef, Ricardo; Frandi, Emanuele; Sartori, Claudio; Allende, Héctor: A novel Frank-Wolfe algorithm. Analysis and applications to large-scale SVM training (2014)
  18. Sapienza, Michael; Cuzzolin, Fabio; Torr, Philip H. S.: Learning discriminative space-time action parts from weakly labelled videos (2014) ioport
  19. Tian, Yingjie; Ping, Yuan: Large-scale linear nonparallel support vector machine solver (2014)
  20. Blondel, Mathieu; Seki, Kazuhiro; Uehara, Kuniaki: Block coordinate descent algorithms for large-scale sparse multiclass classification (2013)