On the convergence of the decomposition method for support vector machines

By Chih-Wei Hsu, Chih-Jen Lin. IEEE Trans. Neural Networks, 2001

468 citations recorded by the source corpus.

Subfields: Artificial Intelligence, Computational Mechanics, Computer Vision and Pattern Recognition

View Paper: https://www.semanticscholar.org/paper/1226a673ce3f69738366be7b53eaf82dd33e290d

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 Computational Mechanics

In Computer Vision and Pattern Recognition

Citations in the corpus

A GA-based feature selection and parameters optimizationfor support vector machines (2006, methodology): “However, this method is time consuming and does not perform well ( Hsu and Lin, 2002; LaValle and Branicky, 2002).”
SVMTorch: Support Vector Machines for Large-Scale Regression Problems (2001, methodology): “Note however that more recently, Lin 2000 has shown the convergence of our algorithm for any value of the working set size but again without shrinking, under the following hypothesis: Assumption 1 The matrix K satisses min I mineigK I I 0 where I is any subset of f1; : : : ; l g with jIj q, K I I…”
Face Recognition: A Literature Review (2008, methodology): “But in a large number of QP problems, Reference [66] presented a decomposition algorithm that guarantees global optimality, and can be used to train SVMs over very large data set.”
Nonlinear optimization and support vector machines (2018, methodology): “A working set selection rule, based on the violation of the optimality conditions of Proposition 3, has been proposed in Joachims (1999) and analyzed in Lin (2001b).”
A tutorial on support vector regression (2004, unknown): “The next step is to make the SV algorithm nonlinear. This, for instance, could be achieved by simply preprocessing the training patterns xi by a map : X → F into some feature space F , as described in Aizerman, Braverman and Rozonoér (1964) and Nilsson (1965) and then applying the standard SV regres”
A tutorial on?-support vector machines (2005, background): “Due to this similarity, we believe that the convergence analysis of C-SVC [21] can be adapted here though detailed proofs have not been written and published.”
Training v-Support Vector Regression: Theory and Algorithms (2002, methodology): “It has been proved that if the decomposition method of LIBSVM is used for solving ( D ǫ ) , ǫ > 0, during iterations α i α ∗ i = 0 always holds (Lin 2001, Theorem 4.1).”
Fast Kernel Classifiers with Online and Active Learning (2005, methodology): “Empirical evidence shows that modern SVM solvers (Chang and Lin, 2001-2004; Collobert and Bengio, 2001) come close to these scaling laws.”
LIBSVM: A library for support vector machines (2011, unknown): “Given training vectors x i ∈ R n , i = 1 , . . . , l , in two classes, and a vector y ∈ R l such that y i ∈ { 1 , − 1 } , the primal optimization problem is min The dual problem is Chang and Lin (2001) show that problem (5) is feasible if and only if so the usable range of ν is smaller than (0 , 1].”
Incorporating Diversity in Active Learning with Support Vector Machines (2003, methodology): “In our experiments, we have used a modified version of bsvm ( Hsu & Lin, 2002 ) that trains support vector machines without bias to stay consistent with our theoretical motivation.”
Learning on the border: active learning in imbalanced data classification (2007, methodology): “An asymptotic convergence proof (Lin, 2001) only exist for the important case of the SVM QP problem using a specific direction selection strategy.”
A Study on Sigmoid Kernels for SVM and the Training of non-PSD Kernels by SMO-type Methods (2005, methodology): “If the working set selection is via (22), existing convergence proofs for PSD kernels (Lin 2001; Lin 2002) require the following important lemma which is also needed here: Lemma 3 There exists σ > 0 such that for any k , Proof.”
Fast training Support Vector Machines using parallel sequential minimal optimization (2008, methodology): “Because the technique of shrinking and cache [5,8,9] is applied to SMO, one column of ( ) O lm”