Global convergence of decomposition learning methods for support vector machines.
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.
Takahashi
Norikazu
N
Department of Computer Science and Communication Engineering, Kyushu University, Fukuoka 812-8581, Japan. norikazu@csce.kyushu-u.ac.jp
Nishi
Tetsuo
T
D000465:Algorithms; D001185:Artificial Intelligence; D016247:Information Storage and Retrieval / Q000379:methods*; D007257:Information Theory; D010363:Pattern Recognition, Automated / Q000379:methods*; D011382:Programming, Linear; D012815:Signal Processing, Computer-Assisted