Global Convergence of Decomposition Learning Methods for Support Vector Machines |
| |
Authors: | Takahashi N Nishi T |
| |
Affiliation: | Dept. of Comput. Sci. & Commun. Eng., Kyushu Univ., Fukuoka; |
| |
Abstract: | Decomposition methods are well-known techniques for solving quadratic programming (QP) problems arising in support vector machines (SVMs). In each iteration of a decomposition method, a small number of variables are selected and a QP problem with only the selected variables is solved. Since large matrix computations are not required, decomposition methods are applicable to large QP problems. In this paper, we will make a rigorous analysis of the global convergence of general decomposition methods for SVMs. We first introduce a relaxed version of the optimality condition for the QP problems and then prove that a decomposition method reaches a solution satisfying this relaxed optimality condition within a finite number of iterations under a very mild condition on how to select variables |
| |
Keywords: | |
|
|