Rigorous proof of termination of SMO algorithm for support vector Machines

Sequential minimal optimization (SMO) algorithm is one of the simplest decomposition methods for learning of support vector machines (SVMs). Keerthi and Gilbert have recently studied the convergence property of SMO algorithm and given a proof that SMO algorithm always stops within a finite number of iterations. In this letter, we point out the incompleteness of their proof and give a more rigorous proof.

I. Introduction

Due to their high generalization performance, support vector machines (SVMs) [1] have attracted great attention in the field of pattern recognition, machine learning, neural networks and so on. Learning of an SVM leads to a quadratic programming (QP) problem with the size being equal to the number of training samples. Since many techniques for solving QP problems are available [2], SVM learning can be implemented with one of them. However, if the number of training samples is very large, those conventional methods cannot be directly applied because it is impossible to store all elements of an matrix in memory. To overcome this difficulty, so-called decomposition methods have been proposed [3], [4]. Given a QP problem, a decomposition method tries to find an optimal solution by solving QP subproblems with variables iteratively. Since is much smaller than in general, decomposition methods can avoid the memory-related problem.