Support Vector Machine Solvers

By L. Eon Bottou, Olivier Chapelle, Dennis DeCoste, Jason Aaron Edward Weston. 2007

351 citations recorded by the source corpus.

Subfields: Artificial Intelligence, Computer Vision and Pattern Recognition, Statistical Learning Theory

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computer Vision and Pattern Recognition

In Statistical Learning Theory

Citations in the corpus

Large Scale Image Completion via Co-Modulated Generative Adversarial Networks (2021, background): “The time complexity of training a linear SVM is between O(n2) and O(n3) (Bottou & Lin, 2007), compared to O(nd2 + d3) of FID (Heusel et al., 2017) and O(n2d) of KID (Bińkowski et al., 2018), where n is the sampling size and d is the dimension of feature space.”
"What is relevant in a text document?": An interpretable machine learning approach (2016, background): “take advantage of the word similarity information encoded in the distributed word 411 embeddings, whereas for a BoW/SVM model, any training algorithm that solves the 412 dual optimization problem for an arbitrary kernel has a computational cost that scales 413 at least quadratically in the number of”
Learning with Augmented Class by Exploiting Unlabeled Data (2014, methodology): “…SVM techniques as Besides the already deﬁned L + 2 U instances, here we introduce another This is a quadratic programming (QP) problem very close to the standard SVM dual problem and can be efﬁciently solved using the existing Sequential Minimal Optimization (SMO) solver (Bottou and Lin 2007).”
A Unified View on Multi-class Support Vector Classification (2016, methodology): “The first of these all-in-one formulations was independently proposed by Weston and Watkins (1999), Vapnik (1998), and Bredensteiner and Bennett (1999). Crammer and Singer (2002) modified this machine, and their approach is frequently used, in particular when dealing with structured output. In addit”
SVM optimization: inverse dependence on training set size (2008, background): “In fact, Bottou and Lin (2007) argue that any method that solves the dual problem very accurately might in general require runtime O(dm2), and also provide empirical evidence suggesting that modern dual-decomposition methods come close to a runtime of O(dm2 log(1/E)).”
How Complex Is Your Classification Problem? (2018, methodology): “The asymptotic computing cost of the measure is dependent on that of the linear SVM, and can take O(n) operations in the worst case [Bottou and Lin, 2007].”
How to Scale Up Kernel Methods to Be As Good As Deep Neural Nets (2014, background): “[7] provides an excellent account of various design considerations.”
Hyperparameter Search in Machine Learning (2015, background): “The inﬂuence of hyperparameters can also be subtle, for instance regularization and kernel complexity can signiﬁcantly affect training time for support vector machines [8].”
Multiple instance learning: A survey of problem characteristics and applications (2016, methodology): “For example, the computational complexity of 1915 an SVM is between O(n2) and O(n3) when using traditional QP and LP solvers [180], where n is the number of instances.”
Simple and Efficient Multiple Kernel Learning by Group Lasso (2010, methodology): “Experiments on multiple data sets show the promising performance of the proposed technique compared with other competitive methods.”