The DOI matches its Crossref record; 38 of the 38 references it cites were found in a registry or an index.
Pegasos: Primal Estimated sub-GrAdient SOlver for SVM
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.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Boyd, S., & Vandenberghe, L. (2004) · doi:10.1017/cbo9780511804441 · Cited by 56,601
Wu, Y. (1999) · Technometrics · doi:10.1080/00401706.1999.10485951 · Cited by 27,221
An Introduction to Support Vector Machines and Other Kernel-based Learning Methods
Cristianini, N., & Shawe-Taylor, J. (2000) · doi:10.1017/cbo9780511801389 · Cited by 13,855
(1973) · CERN Document Server (European Organization for Nuclear Research) · Cited by 12,895
Advances in kernel methods: support vector learning
Schölkopf, B., Burges, C. J. C., & Smola, A. J. (1999) · doi:10.5555/299094 · Cited by 5,789
Fast Training of Support Vector Machines Using Sequential Minimal Optimization
Platt, J. C. (1998) · Advances in Kernel Methods · doi:10.7551/mitpress/1130.003.0016 · Cited by 5,437
An Introduction to Support Vector Machines
Cristianini, N., & Shawe-Taylor, J. S. (2000) · ePrints Soton (University of Southampton) · Cited by 4,115
Pattern classification and scene analysis
Chien, Y. (1974) · IEEE Transactions on Automatic Control · doi:10.1109/tac.1974.1100577 · Cited by 3,398
Natural Gradient Works Efficiently in Learning
Amari, S.-I. (1998) · Neural Computation · doi:10.1162/089976698300017746 · Cited by 2,681
Adaptive Algorithms and Stochastic Approximations
Benveniste, A., Métivier, M., & Priouret, P. (1990) · Springer eBooks · doi:10.1007/978-3-642-75894-2 · Cited by 2,006
Training linear SVMs in linear time
Joachims, T. (2006) · Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining · doi:10.1145/1150402.1150429 · Cited by 1,920
Introduction to Stochastic Search and Optimization: Estimation, Simulation, and Control
Spall, J. C. (2003) · Wiley eBooks · doi:10.1002/0471722138 · Cited by 1,890
Online Passive-Aggressive Algorithms
Crammer, K., Dekel, O., Keshet, J., Shalev‐Shwartz, S., & Singer, Y. (2003) · Cited by 1,665
Self-citationMaking Large-Scale Support Vector Machine Learning Practical
Joachims, T. (1998) · Advances in Kernel Methods · doi:10.7551/mitpress/1130.003.0015 · Cited by 1,613
Some results on Tchebycheffian spline functions
Kimeldorf, G., & Wahba, G. (1971) · Journal of Mathematical Analysis and Applications · doi:10.1016/0022-247x(71)90184-3 · Cited by 1,254
The Tradeoffs of Large-Scale Learning
Bottou, L., & Bousquet, O. (2011) · Optimization for Machine Learning · doi:10.7551/mitpress/8996.003.0015 · Cited by 1,128
Solving large scale linear prediction problems using stochastic gradient descent algorithms
Zhang, T. (2004) · Twenty-first international conference on Machine learning - ICML '04 · doi:10.1145/1015330.1015332 · Cited by 1,106
Large margin classification using the perceptron algorithm
Freund, Y., & Schapire, R. E. (1998) · Proceedings of the eleventh annual conference on Computational learning theory · doi:10.1145/279943.279985 · Cited by 1,071
Kivinen, J., Smola, A. J., & Williamson, R. C. (2004) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2004.830991 · Cited by 1,004
Stochastic Approximation Algorithms and Applications
Puhalskii, A., Kushner, H. J., & Yin, G. G. (1998) · Journal of the American Statistical Association · doi:10.2307/2669885 · Cited by 994
A dual coordinate descent method for large-scale linear SVM
Hsieh, C.-J., Chang, K.-W., Lin, C.-J., Keerthi, S. S., & Sundararajan, S. (2008) · Proceedings of the 25th international conference on Machine learning - ICML '08 · doi:10.1145/1390156.1390208 · Cited by 872
Logarithmic regret algorithms for online convex optimization
Hazan, E., Agarwal, A., & Kale, S. (2007) · Machine Learning · doi:10.1007/s10994-007-5016-8 · Cited by 828
Parallel optimization: Theory, algorithms, and applications
(1998) · Computers & Mathematics with Applications · doi:10.1016/s0898-1221(98)90713-1 · Cited by 813
Training a Support Vector Machine in the Primal
Chapelle, O. (2007) · Neural Computation · doi:10.1162/neco.2007.19.5.1155 · Cited by 780
Fast Kernel Classifiers With Online And Active Learning
Bordes, A., Ertekin, Ş., Weston, J., & Bottou, L. (2005) · HAL · Cited by 749
Large Margin Classification Using the Perceptron Algorithm
Freund, Y., & Schapire, R. E. (1999) · Machine Learning · doi:10.1023/a:1007662407062 · Cited by 604
Efficient svm training using low-rank kernel representations
Fine, S., & Scheinberg, K. (2002) · doi:10.5555/944790.944812 · Cited by 579
On the Generalization Ability of On-Line Learning Algorithms
Cesa-Bianchi, N., Conconi, A., & Gentile, C. (2004) · IEEE Transactions on Information Theory · doi:10.1109/tit.2004.833339 · Cited by 426
Bottou, L., & Cun, Y. L. (2003) · Cited by 359
Logarithmic Regret Algorithms for Online Convex Optimization
Hazan, E., Kalai, A. T., Kale, S., & Agarwal, A. (2006) · Lecture notes in computer science · doi:10.1007/11776420_37 · Cited by 242
SVM optimization: inverse dependence on training set size
Shalev-Shwartz, S., & Srebro, N. (2008) · Proceedings of the 25th international conference on Machine learning - ICML '08 · doi:10.1145/1390156.1390273 · Cited by 240
Self-citationFast Rates for Regularized Objectives
Sridharan, K., Shalev‐Shwartz, S., & Srebro, N. (2008) · Cited by 106
Self-citationA Statistical Study of On-line Learning
Murata, N. (1999) · Cambridge University Press eBooks · doi:10.1017/cbo9780511569920.005 · Cited by 93
QP Algorithms with Guaranteed Accuracy and Run Time for Support Vector Machines
Hush, D. R., Kelly, P. J., Scovel, C., & Steinwart, I. (2006) · doi:10.5555/1248547.1248573 · Cited by 73
Primal-Dual Subgradient Methods for Convex ProblemsPreprint
Nesterov, Y. E. (2006) · SSRN Electronic Journal · doi:10.2139/ssrn.912637 · Cited by 48
Statistical analysis of learning dynamics
Murata, N., & Amari, S. (1999) · Signal Processing · doi:10.1016/s0165-1684(98)00206-0 · Cited by 37
Improved risk tail bounds for on-line algorithms
Cesa‐Bianchi, N., & Gentile, C. (2005) · Cited by 14
(1998)
Cited by
Object Detection with Discriminatively Trained Part-Based Models
Felzenszwalb, P. F., Girshick, R. B., McAllester, D., & Ramanan, D. (2010) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2009.167 · Cited by 9,853
(2015) · Cited by 2,857
Dlib-ml: A Machine Learning Toolkit
King, D. E. (2009) · doi:10.5555/1577069.1755843 · Cited by 2,777
Improving the Fisher Kernel for Large-Scale Image Classification
Perronnin, F., Sánchez, J., & Mensink, T. (2010) · Lecture Notes in Computer Science · doi:10.1007/978-3-642-15561-1_11 · Cited by 2,588
A comprehensive survey on support vector machine classification: Applications, challenges and trends
Cervantes, J., Garcia-Lamont, F., Rodríguez-Mazahua, L., & Lopez, A. (2020) · Neurocomputing · doi:10.1016/j.neucom.2019.10.118 · Cited by 2,381
Metadata
- Authors
- Shalev-Shwartz, S., Singer, Y., & Srebro, N.
- Venue
- Proceedings of the 24th international conference on Machine learning
- Publisher
- ACM
- Published
- 2007-06-20
- Pages
- 807-814
- OpenAlex
- W2142623206
- Cited by
- 973
- References
- 38
- FWCI
- 39.03
- Type
- conference paper
- Language
- en
- Open access
- closed
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.