Pegasos swMATH ID: 8752 Software Authors: Shalev-Shwartz, Shai; Singer, Yoram; Srebro, Nathan; Cotter, Andrew Description: 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 Homepage: http://link.springer.com/article/10.1007/s10107-010-0420-4 Related Software: LIBSVM; LIBLINEAR; UCI-ml; AdaGrad; ImageNet; SVMlight; Saga; SSVM; AlexNet; Scikit; Adam; SGD-QN; RCV1; L-BFGS; SIFT; bmrm; Forgetron; RSVM; MNIST; SeDuMi Cited in: 126 Documents Standard Articles 1 Publication describing the Software, including 1 Publication in zbMATH Year Pegasos: primal estimated sub-gradient solver for SVM. Zbl 1211.90239Shalev-Shwartz, Shai; Singer, Yoram; Srebro, Nathan; Cotter, Andrew 2011 all top 5 Cited by 320 Authors 5 Richtárik, Peter 4 Takáč, Martin 3 Jin, Rong 3 Zhu, Shenghuo 2 Aggarwal, Charu C. 2 Bach, Francis R. 2 Couellan, Nicolas P. 2 Gao, Yang 2 Grimmer, Benjamin 2 Guo, Zheng-Chu 2 Iiduka, Hideaki 2 Lan, Guanghui 2 Landwehr, Niels 2 Li, Qingna 2 Patrascu, Andrei-Tudor 2 Phung, Dinh Q. 2 Piccialli, Veronica 2 Rosasco, Lorenzo A. 2 Sciandrone, Marco 2 Shalev-Shwartz, Shai 2 Shi, Lei 2 Tian, Yingjie 2 Villa, Silvia 2 Vũ, Bằng Công 2 Vucetic, Slobodan 2 Wang, Zhuang 2 Yang, Tianbao 2 Zhai, Tingting 2 Zhou, Shuisheng 1 Ahookhosh, Masoud 1 Alama, Jesse 1 Allende, Héctor 1 Andoni, Alexandr 1 Asi, Hilal 1 Bai, Lan 1 Bai, Zuo 1 Baykal, Cenk 1 Bertsimas, Dimitris John 1 Beznosikov, Aleksandr 1 Bischl, Bernd 1 Blaschko, Matthew B. 1 Blondel, Mathieu 1 Bottou, Léon 1 Bshouty, Nader H. 1 Burns, Collin 1 Cao, Longbing 1 Carrizosa, Emilio 1 Chalise, Prabhakar 1 Chang, Yu-Ming 1 Cheng, Yiyuan 1 Chow, Yinlam 1 Cocianu, Catalina-Lucia 1 Cotter, Andrew 1 Csiba, Dominik 1 Cui, Jiangtao 1 Cuomo, Salvatore 1 Curtis, Frank E. 1 De Baets, Bernard 1 De Nicolao, Giuseppe 1 De Raedt, Luc 1 Demircioğlu, Aydin 1 Deng, Naiyang 1 Deng, Wan-Yu 1 Díaz, Mateo 1 Dieuleveut, Aymeric 1 Dinuzzo, Francesco 1 Djuric, Nemanja 1 Drozda, Paweł 1 Duchi, John C. 1 Dutta, Aritra 1 Fan, Neng 1 Feldman, Dan 1 Feng, Hui 1 Ferreira, Orizon Pereira 1 Ferri, Francesc J. 1 Finley, Thomas 1 Frandi, Emanuele 1 Frasconi, Paolo 1 Gao, Kaifeng 1 Gao, Wei 1 Ghadimi, Saeed 1 Glasmachers, Tobias 1 Grapiglia, Geovani Nunes 1 Gu, Bin 1 Hao, Zhifeng 1 Hayes, David Neil 1 Hazan, Tamir 1 He, Jianghua 1 Heskes, Tom M. 1 Ho, Derek Y. H. 1 Hoi, Steven C. H. 1 Holmes, Geoffrey 1 Horn, Daniel R. 1 Hou, Di 1 Hsu, Chun-Nan 1 Hu, Bo 1 Huang, Guangbin 1 Huang, Han-Shen 1 Huang, Kaizhu 1 Huang, Lingxiao ...and 220 more Authors all top 5 Cited in 56 Serials 14 Machine Learning 10 Information Sciences 10 Journal of Machine Learning Research (JMLR) 6 Neural Networks 6 SIAM Journal on Optimization 5 Mathematical Programming. Series A. Series B 5 Computational Optimization and Applications 4 International Journal of Computer Vision 3 Optimization Methods & Software 3 Optimization Letters 2 Annals of Operations Research 2 Journal of Industrial and Management Optimization 2 Statistical Analysis and Data Mining 1 Artificial Intelligence 1 The Annals of Statistics 1 Applied Mathematics and Optimization 1 Journal of Optimization Theory and Applications 1 Circuits, Systems, and Signal Processing 1 Advances in Mathematics (Beijing) 1 Bulletin of the Iranian Mathematical Society 1 Optimization 1 Computers & Operations Research 1 Journal of Automated Reasoning 1 International Journal of Approximate Reasoning 1 Journal of Scientific Computing 1 Neural Computation 1 The Annals of Applied Probability 1 Journal of Global Optimization 1 Numerical Algorithms 1 Communications in Statistics. Simulation and Computation 1 European Journal of Operational Research 1 Linear Algebra and its Applications 1 Pattern Recognition 1 SIAM Review 1 Computational Statistics and Data Analysis 1 Cybernetics and Systems Analysis 1 Advances in Computational Mathematics 1 Annals of Mathematics and Artificial Intelligence 1 Mathematical Problems in Engineering 1 Soft Computing 1 Mathematical Methods of Operations Research 1 Data Mining and Knowledge Discovery 1 International Journal of Applied Mathematics and Computer Science 1 Optimization and Engineering 1 4OR 1 Computational Management Science 1 Advances in Data Analysis and Classification. ADAC 1 Foundations and Trends in Machine Learning 1 Science China. Information Sciences 1 ISRN Applied Mathematics 1 EURO Journal on Computational Optimization 1 Computer Science Review 1 Springer Series in Statistics 1 Open Mathematics 1 International Journal of Systems Science. Principles and Applications of Systems and Integration 1 Japanese Journal of Statistics and Data Science all top 5 Cited in 18 Fields 83 Computer science (68-XX) 56 Operations research, mathematical programming (90-XX) 41 Statistics (62-XX) 23 Numerical analysis (65-XX) 7 Calculus of variations and optimal control; optimization (49-XX) 4 Functional analysis (46-XX) 3 Probability theory and stochastic processes (60-XX) 3 Systems theory; control (93-XX) 3 Information and communication theory, circuits (94-XX) 2 Convex and discrete geometry (52-XX) 2 Biology and other natural sciences (92-XX) 1 Linear and multilinear algebra; matrix theory (15-XX) 1 Real functions (26-XX) 1 Ordinary differential equations (34-XX) 1 Dynamical systems and ergodic theory (37-XX) 1 Operator theory (47-XX) 1 Statistical mechanics, structure of matter (82-XX) 1 Game theory, economics, finance, and other social and behavioral sciences (91-XX) Citations by Year