Global Convergence of Decomposition Learning
Methods for Support Vector Machines
Author(s): Norikazu Takahashi and Tetsuo Nishi
Journal: IEEE Transactions on Neural Networks
Volume: 17
Number: 6
Pages: 1362–1369
Month: November
Year: 2006
Published Version: http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=4012045c⃝2006IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing thismaterial for advertising or promotional purposes, creating new collective works, for resale orredistribution to servers or lists, or reuse of any copyrighted component of this work in otherworks.

1

Global Convergence of Decomposition Learning
Methods for Support Vector Machines
Norikazu Takahashi, Member, IEEE and Tetsuo Nishi, Fellow, IEEE

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 ofgeneral 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 numberof iterations under a very mild condition on how to selectvariables.
Index Terms— Support vector machines, quadratic programming, decomposition method, global convergence, termination

I. I NTRODUCTION
Support vector machines (SVMs) have recently attracted
great attention in various fields such as pattern recognition,
machine learning, neural networks, signal processing, andso on [1]–[4]. Given a set of l training samples, an SVM
has to solve a quadratic programming (QP) problem withl variables. If the number of training samples are considerably large, the conventional QP solvers cannot be directly
applied to SVM learning because large matrix computations
are required. To overcome this difficulty, several techniquescalled decomposition methods have recently been proposed[5]–[8]. A basic strategy commonly used in decomposition
methods is to execute two operations repeatedly until some
optimality condition is satisfied; one is to select q variables
among l and the other is to minimize the objective function
by updating only the the selected q variables. The set of q
variables selected for updating is called the working set. An
example of decomposition methods is the sequential minimal
optimization (SMO) algorithm proposed by Platt [5] in which
only two variables are selected for the working set in each
iteration. Another example is SVMlight [6], the most widelyused learning algorithm for SVMs, in which q, the size of theworking set, can be set to any even number. Since large matrix
computations are not required, decomposition methods areThis work was supported in part by the 21st Century COE (Center of
Excellence) Program “Reconstruction of Social Infrastructure Related toInformation Science and Electrical Engineering”.
N. Takahashi is with the Department of Computer Science and Communication Engineering, Kyushu University, Fukuoka, 812-8581 Japan (e-mail:norikazu@csce.kyushu-u.ac.jp).
T. Nishi was with the Department of Computer Science and Communication
Engineering, Kyushu University, Fukuoka, 812-8581 Japan. He is now with
the Faculty of Science and Engineering, Waseda University, Tokyo, 169-0072
Japan (e-mail: nishi-t@waseda.jp).

useful for SVMs especially when a large number of training
samples are given.
For any decomposition method, it is very important to guarantee that the sequence of solutions converges to an optimal
solution within a finite number of iterations. Some theoreticalresults concerning the global convergence of decomposition
methods can be found in the literature [9]–[16]. Keerthi and
Gilbert [9] analyzed the behavior of the generalized SMO
algorithm and gave a proof that the algorithm terminates within
a finite number of iterations under a pre-specified stopping
condition and tolerance1 . Lin [10] proved that the sequence ofsolutions obtained by an SMO algorithm converges asymptotically to an optimal solution. Recently, Chen et al. [12] carriedout a comprehensive study on SMO algorithms and gave
several results on asymptotic convergence, finite termination,
shrinking and caching, and convergence rate in a general
setting on the working set selection. However, the results given
in [9]–[12] rely heavily on the fact that only two variables are
updated in each iteration, and therefore it seems difficult toextend to the general case where q is greater than two.
Chang et al. [13] considered a kind of decomposition
method in which q is not restricted to two, and proved theconvergence of the method. However, the working set selectionin their method is formulated in a rather special form, andtherefore the result does not hold for other decomposition
methods. Lin [14] investigated the properties of the sequenceof solutions obtained by SVMlight in detail and proved thatany limit point of the sequence is an optimal solution. Lin [15]also showed that a class of decomposition methods including
SVMlight stops within a finite number of iterations if a relaxedversion of stopping criterion is used. These results are important because the convergence of SVMlight was guaranteed
theoretically for the first time. However, on the other hand,these results require a stronger assumption on the Hessian
matrix of the objective function than positive semi-definiteness[14, Assumption IV.1], except the special case where q = 2[10]. It is known that this assumption is satisfied if theGaussian kernel is used and training samples are different
from each other, but, it is also known that this assumption
does not hold true for any kernel function if training samples
contain two or more identical data [10]. List and Simon [16]considered a general class of QP problems which includes theone arising in SVMs, and shown that a decomposition method
converges to an optimal solution if its working set selection
method satisfies three abstract conditions. This result is generalin the sense that no specific working set selection method is
1 The authors of the present paper have recently pointed out the incompleteness of their proof and given a more rigorous proof [11].

2assumed, but still requires the same assumption on the Hessian
matrix of the objective function as [14] and [15].
In this paper, we will present a new convergence proof forgeneral decomposition methods for SVMs. Unlike the existing
results mentioned above, we will neither restrict ourselves toa specific working set selection nor assume any condition on
the Hessian matrix of the objective function except for positive
semi-definiteness. Instead, we will employ a relaxed version of
the Karush-Kuhn-Tucker (KKT) conditions as the optimality
condition. The relaxed version contains two positive parameters τ and ϵ, and approaches the strict KKT conditions as bothτ and ϵ go to zero. By using the global convergence theorem in
optimization theory [17], we will prove that the decomposition
method stops within a finite number of iterations after finding
an optimal solution for any τ and ϵ if the working set contains
at least one pair of indices violating the optimality conditionin each iteration. This condition on the working set selection
is very mild and thus can be applied to many decomposition
methods.
In our convergence proof, closedness of a point-to-set map[17] plays a central role. It is important to note that the pointto-set map defined for the decomposition method consideredin this paper is not closed if either the strict KKT condition or
the relaxed version which has been often used so far [6], [9],[11], [15] is employed as the optimality condition. Indeed thisis the main difficulty on proving the convergence in earlier
works. An extensive discussion is given in [14].
This paper is organized as follows. In Section II, the global
convergence theorem for general optimization problems andsome related results are reviewed for later discussions. In
Section III, the QP problem arising in SVMs, two types of
optimality conditions, and the algorithm of general decomposition methods are explained. In Section IV, the relationshipbetween two optimality conditions is firstly discussed and thenconvergence theorems for decomposition methods are proved.
In Section V, these convergence theorems are applied to somewell-known learning algorithms for SVMs. Finally, concluding
remarks are given in Section VI.
II. P RELIMINARIESFirst of all, we will review a fundamental result in optimization theory known as the global convergence theorem [17].
This theorem plays a central role in our global convergence
analysis of decomposition methods.
Let us consider the following optimization problem.
Problem 1: Find x which minimizes the objective function
f (x) under the constraint x ∈ X.
An algorithm for solving Problem 1 can be viewed as an
iterative process that generates a sequence {x(k)}∞k=0 byx(k + 1) ∈ A(x(k)),

k = 0, 1, . . .

(1)where x(0) ∈ X is a given initial point and A is a point-to-set
map that assigns to each point in the domain X a subset of X.
According to this definition, we can state that developing analgorithm for solving Problem 1 is equivalent to determining
the point-to-set map A. Apparently, the most desirable property of the map A is that the sequence {x(k)}∞k=0 generatedby (1) converges to an optimal solution of Problem 1 for any
initial point x(0) ∈ X.
Definition 1: Let X, Ω and A be a nonempty closed set
in Rn , a subset of X, and a point-to-set map from X to X,
respectively. If a continuous function Z defined in X satisfies
if x ∈/ Ω and y ∈ A(x) then Z(y) < Z(x)then Z is called a descent function for Ω and A.
Definition 2: Let X and Y be nonempty closed sets in Rn
and Rm , respectively. Let A be a point-to-set map from X to
Y . The map A is said to be closed at x̄ if the two assumptions1) x(k) ∈ X, ∀k and limk→∞ x(k) = x̄2) y(k) ∈ A(x(k)), ∀k and limk→∞ y(k) = ȳ
imply that ȳ ∈ A(x̄). The map A is said to be closed on X
if it is closed at each point in X.
In terms of these definitions, the global convergence theorem can be stated as follows.
Theorem 1 ( [17]): Let X, Ω and A be a nonempty closed
set in Rn , a subset of X, and a point-to-set map from X to X,
respectively. Let {x(k)}∞k=0 be a sequence generated by (1)with x(0) ∈ X. Every convergent subsequence of {x(k)}∞k=0
has a limit in Ω if the following conditions are satisfied.
1) For all k, x(k) belongs to a compact set S ⊆ X.
2) There exists a descent function Z for Ω and A.
3) The map A is closed on X \ Ω.
Note that Ω in Theorem 1 can be any subset of X. In
particular, if Ω is set to the set of optimal solutions ofProblem 1, Theorem 1 gives a sufficient condition for thesequence {x(k)}∞k=0 generated by (1) to converge to an
optimal solution. Theorem 1 is hence a very useful tool for
proving the global convergence of an algorithm. However, it
is difficult in general to develop a map A having the global
convergence property for the set of optimal solutions. Thus Ω
is often set to, for example, {x | x is a local optimal solution}and {x | x ∈ X, f (x) ≤ b} where b is a constant.
The following lemma can easily be obtained.
Lemma 1: Let A : X → Y and B : X → Y be pointto-set maps. If both A and B are closed at x, then the map
C(x) = A(x) ∪ B(x) is also closed at x.
Proof: Let {x(k)}∞k=0 be any sequence such that x(k) ∈X, ∀k and limk→∞ x(k) = x. Let {y(k)}∞k=0 be any sequence such that y(k) ∈ C(x(k)), ∀k and limk→∞ y(k) = y.
Then it is obvious that at least one of two statements:
1) y(k) ∈ A(x(k)) for infinitely many k,2) y(k) ∈ B(x(k)) for infinitely many kholds. We will assume without loss of generality that the firstcase holds true. Let the set of all k such that y(k) ∈ A(x(k))
be denoted by KA . Then the sequence {x(k)}k∈KA satisfies
x(k) ∈ X, ∀k ∈ KA and limk→∞,k∈KA x(k) = x. Also, thesequence {y(k)}k∈KA satisfies y(k) ∈ A(x(k)), ∀k ∈ KA
and limk→∞,k∈KA y(k) = y. Since the point-to-set map A isclosed at x, we have y ∈ A(x) which implies that y ∈ C(x).
Therefore the point-to-set map C is closed at x.
A result concerning the closedness of composite maps will
also be needed in later discussions.
Definition 3: Let A : X → Y and B : Y → Z be pointto-set maps. The composite map C = BA is defined as the

3point-to-set map C : X → Z with

Iup (α) = {i | αi < C, di = 1} ∪ {i | αi > 0, di = −1} ,C(x) = ∪y∈A(x) B(y) .
Lemma 2 ( [17]): Let A : X → Y and B : Y → Z be
point-to-set maps. If A is closed at x, B is closed on A(x)and Y is compact, then the composite map C = BA is closed
at x.

Ilow (α) = {i | αi < C, di = −1} ∪ {i | αi > 0, di = 1} .

III. D ECOMPOSITION M ETHOD
Suppose that we are given a set of l training samples{(pi , di )}li=1 where pi ∈ Rn is the i-th input pattern anddi ∈ {1, −1} represents the class to which pi belongs. The
learning of an SVM with the kernel function K(·, ·) leads tothe following QP problem (for more details on formulation,
see for example [1]).
Problem 2: Find α = [α1 , α2 , . . . , αl ]T which minimizes
the objective function
l
l
l
∑
1 ∑∑
qij αi αj −αi
2 i=1 j=1i=1

di αi = 0(2)

i = 1, 2, . . . , l(3)where qij = di dj K(pi , pj ) and C is a user-specified positive
constant.
Throughout this paper, we assume that the kernel function
K(·, ·) satisfies Mercer’s condition [1]. In this case, Q =[qij ] ∈ Rl×l is a positive semi-definite matrix, and therefore
Problem 2 is a convex QP problem. Note that the optimal
solution of Problem 2 is not necessarily unique because W (α)
is not strictly convex. The feasible region of Problem 2, thatis, the set of α satisfying (2) and (3), is denoted by S which isapparently a compact set. Also, the set {1, 2, . . . , l} is denotedby L.
B. Optimality Conditions
Since Problem 2 is a convex QP problem, optimal solutions
are completely characterized by the KKT conditions [17], thatis, α ∈ S is an optimal solution of Problem 2 if and only ifthere exist constants λ, µ1 , µ2 , . . . , µl , ν1 , ν2 , . . . , νl such that ∂W (α)/∂αi + λdi − µi + νi = 0 µi αi = 0νi (αi − C) = 0
(4)


µ
≥
0

i


νi ≥ 0for all i ∈ L. As shown in [9] and [15], this condition can be
rewritten in a more compact form as
min Fi (α) ≥Fi (α) = dimin Fi (α) ≥i∈Iup (α)

max Fi (α) − τ(6)i∈Ilow (α)

where τ is a positive constant [6], [7], [15].
In this paper, on the other hand, we employ neither (5) nor(6) but the inequality:
min Fi (α) >

ϵ (α)
i∈Iup

max Fi (α) − τ

(7)

ϵ (α)
i∈IlowϵIlow(α) = {i | αi ≤ C − ϵ, di = −1} ∪ {i | αi ≥ ϵ, di = 1} ,0 ≤ αi ≤ C,

where

max Fi (α)} .

i∈Ilow (α)ϵIup(α) = {i | αi ≤ C − ϵ, di = 1} ∪ {i | αi ≥ ϵ, di = −1} ,i=1i∈Iup (α)

min Fi (α) ≥i∈Iup (α)

for the optimality condition, where

under the constraintsl∑Ω∗ = {α ∈ S |In a practical situation, the optimality condition (5) is often
relaxed as

A. SVM Dual Problem

W (α) =

Let Ω∗ denote the set of optimal solutions of Problem 2. Then,by using the above notations, we can express Ω∗ as follows:

max Fi (α)

i∈Ilow (α)

( l
∑
j=1

)
qij αj − 1 ,(5)and ϵ is any positive constant smaller than C/2. Usually ϵ isϵset to a sufficiently small positive number. The role of Iup(α)ϵ
and Ilow(α) is to consider αi which is sufficiently close to 0
(C, resp.) to be exactly 0 (C, resp.). This is a technique used in
the implementation of SVMlight algorithm [6] (see the source
code2 of SVMlight developed by Joachims). In the following,
any α ∈ S satisfying (7) is said to be a (τ, ϵ)-optimal solution.
The set of (τ, ϵ)-optimal solutions is denoted by Ω(τ,ϵ) , thatis,Ω(τ,ϵ) = {α ∈ S |min Fi (α) >

ϵ (α)
i∈Iup

max Fi (α) − τ } .

ϵ (α)
i∈Ilow

Also, a pair of indices (i, j) such thatϵϵi ∈ Iup(α), j ∈ Ilow(α), Fi (α) ≤ Fj (α) − τ

is called a (τ, ϵ)-violating pair at α. If a pair (i, j) is not a(τ, ϵ)-violating pair at α, the pair is called a (τ, ϵ)-feasible
pair at α. It is obvious from these definitions that α ∈ S is a(τ, ϵ)-optimal solution if and only if there is no (τ, ϵ)-violating
pair at α.
Properties of the two sets Ω∗ and Ω(τ,ϵ) as well as therelationship between them will be studied in detail in the next
section.
C. Algorithm of Decomposition Method
A basic strategy commonly used in all decomposition methods is to repeat two operations until some optimality conditionis satisfied; one is to select q variables among l for the working
set and the other is to minimize the objective function W (α)
by updating only the selected q variables. This is formally
expressed as follows:
2 Sourcecode and binaries
http://svmlight.joachims.org/.

of

SVMlight

areavailableat4

Algorithm 1: Given training samples {(pi , di )}li=1 , a kernel
function K(·, ·), a positive constant C and an integer q(≤ l),
execute the following procedures.
1) Let α(0) = 0 and k = 0.
2) If α = α(k) satisfies the optimality condition (7) thenstop. Otherwise go to Step 3).
3) Select the working set LB (k) ⊆ L = {1, 2, . . . , l} where|LB (k)| ≤ q.
4) Find α = [α1 , α2 , · · · , αl ]T which minimizes the objective function W (α) under the constraints (2), (3) and
αi = αi (k), ∀i ∈ LN (k) = L \ LB (k).
5) Set α(k + 1) to an optimal solution of the optimization
problem in Step 4). Add 1 to k, and go to Step 2).
We will refer to the optimization problem in Step 4) as the
subproblem in the following. Since the subproblem has at mostq variables, the amount of memory required for Algorithm 1
is linear in l, while l2 elements of the matrix Q must be stored
in memory if Problem 2 is solved at a time. This is the main
advantage of decomposition methods. As for computation
time, each subproblem can be solved faster as q decreases.
In particular, in the case where q = 2, subproblems can besolved analytically and hence Algorithm 1 can be implemented
without QP solvers [5]. However, it should be noted that the
number of iterations increases as q decreases in general.
It is apparent that the sequence {α(k)}∞k=1 generated by
Algorithm 1 satisfies two conditions:α(k) ∈ S(8)

W (α(k + 1)) ≤ W (α(k))(9)

for all k. Since the objective function W (·) is bounded frombelow in S, Eq.(9) implies that the sequence {W (α(k))}∞k=0
necessarily converges to a certain value. However, on theother hand, it is not clear whether the sequence {α(k)}∞k=0converges to Ω(τ,ϵ) or not.
The optimality condition for the subproblem is expressedin the same form as (5), that is, for given LB (k) ⊆ L andα(k) ∈ S, α ∈ S is an optimal solution of the subproblem if
and only if the following conditions are satisfied.
{min
Fi (α) ≥max
Fi (α)i∈Iup (α)∩LB (k)αi = αi (k),i∈Ilow (α)∩LB (k)∀i ∈ LN (k) = L \ LB (k)Proposition 1: Ω(τ,ϵ) ⊇ Ω∗ for any τ > 0 and ϵ ∈ (0, C/2).
Proof: Let α be any point in Ω∗ . Then α satisfies (5).
It follows from Lemma 3 thatmin Fi (α) ≥

ϵ (α)
i∈Iup

max Fi (α) ≥i∈Ilow (α)

A. Properties of Ω∗ and Ω(τ,ϵ)
Before proceeding to the convergence analysis of Algorithm 1, we study properties of Ω∗ and Ω(τ,ϵ) .
ϵϵ(α) for
Lemma 3: Iup (α) ⊇ Iup(α) and Ilow (α) ⊇ Ilowany α ∈ S and ϵ ∈ (0, C/2).
Proof: We will prove only the first formula. The secondϵone can be proved similarly. Let i be any member of Iup(α).
Then αi satisfies 0 ≤ αi < C − ϵ if di = 1 and ϵ < αi ≤ C
if di = −1. In the former case, i belongs to Iup (α) because
either 0 < αi < C or αi = 0 holds. In the latter case, ibelongs to Iup (α) because either 0 < αi < C or αi = Cϵholds. Therefore, any member of Iup(α) belongs to Iup (α).
ϵ
This implies Iup (α) ⊇ Iup (α).

max Fi (α) .

ϵ (α)
i∈Ilow

From these two inequalities and (5), we havemin Fi (α) ≥

ϵ (α)
i∈Iup

max Fi (α)ϵ (α)
i∈Ilow

which implies α ∈ Ω(τ,ϵ) .
Lemma 4: Let {α(n)}∞n=0 be any sequence such thatα(n) ∈ S, ∀n and limn→∞ α(n) = ᾱ. Then there exist
positive integers n1 and n2 such that
Iup (α(n)) ⊇ Iup (ᾱ), ∀n ≥ n1
Ilow (α(n)) ⊇ Ilow (ᾱ), ∀n ≥ n2
Proof: We will prove only the first formula. The second
one can be proved in the same way. Let i be any memberof Iup (ᾱ). Then ᾱi satisfies ᾱi < C if di = 1 and ᾱi > 0
if di = −1. In the former case, since αi (n) converges toᾱi , there exists a positive integer n1 (i) such that αi (n) <C, ∀n ≥ n1 (i) which implies i ∈ Iup (α(n)), ∀n ≥ n1 (i). In
the latter case, it is shown in the same way that there exists
a positive integer n1 (i) such that i ∈ Iup (α(n)), ∀n ≥ n1 (i).
Let n1 = maxi∈Iup (ᾱ) n1 (i). Then all members of Iup (ᾱ)
belong to Iup (α(n)), ∀n ≥ n1 . This completes the proof.
This lemma was first given by Lin [14, Lemma IV.4]. We
have just restated the result in terms of our notations, andgiven a proof for the sake of the reader’s convenience.
Proposition 2: The set Ω∗ is closed.
Proof: Let {α(n)}∞n=1 be any sequence such that α(n) ∈∗Ω , ∀n and limn→∞ α(n) = ᾱ. It suffices for us to show thatᾱ ∈ Ω∗ . Since α(n) ∈ Ω∗ , ∀n, we havemini∈Iup (α(n))

Fi (α(n)) ≥maxi∈Ilow (α(n))

Fi (α(n)), ∀n.

It follows from this inequality and Lemma 4 that there exists
a positive integer n1 such thatmin Fi (α(n)) ≥i∈Iup (ᾱ)

IV. G LOBAL C ONVERGENCE A NALYSIS OF
D ECOMPOSITION M ETHODS

min Fi (α) ,i∈Iup (α)

max Fi (α(n)), ∀n ≥ n1 .

i∈Ilow (ᾱ)

By letting n go to infinity, we havemin Fi (ᾱ) ≥i∈Iup (ᾱ)

max Fi (ᾱ)

i∈Ilow (ᾱ)

which implies ᾱ ∈ Ω∗ . Therefore, Ω∗ is a closed set.
Lemma 5: Let {α(n)}∞n=0 be any sequence such thatα(n) ∈ S, ∀n and limn→∞ α(n) = ᾱ. Then there exist
positive integers n1 and n2 such thatϵϵ
Iup(α(n)) ⊆ Iup(ᾱ), ∀n ≥ n1ϵϵIlow(α(n)) ⊆ Ilow(ᾱ), ∀n ≥ n2

for any ϵ ∈ (0, C/2).
Proof: We will prove only the first formula. The second
one can be proved similarly. Let i be any nonmember ofϵIup(ᾱ). Then ᾱi satisfies ᾱi > C − ϵ if di = 1 and ᾱi < ϵ5

if di = −1. In the former case, since αi (n) converges toᾱi , there exists a positive integer n1 (i) such that αi (n) >ϵ
C − ϵ, ∀n ≥ n1 (i) which implies i ̸∈ Iup(α(n)), ∀n ≥ n1 (i).
In the latter case, it is shown in the same way that there exists
ϵa positive integer n1 (i) such that i ̸∈ Iup(α(n)), ∀n ≥ n1 (i).
ϵ (ᾱ) n1 (i). Then all nonmembers of Iup (ᾱ)
Let n1 = maxi̸∈Iupϵ
do not belong to Iup(α(n)), ∀n ≥ n1 . This is equivalent to
the first formula.
Proposition 3: The set S \ Ω(τ,ϵ) is closed for any τ > 0and ϵ ∈ (0, C/2).
Proof: Let {α(n)}∞n=1 be any sequence such that α(n) ∈S \ Ω(τ,ϵ) , ∀n and limn→∞ α(n) = ᾱ. Then we haveminϵ (α(n))i∈Iup

Fi (α(n)) ≤max

ϵ (α(n))i∈Ilow

Fi (α(n)) − τ, ∀n.

the same conclusion as Case 1). In Case 3), it follows from
Lemma 5 and the continuity of Fi (·) thatϵϵi ∈ Iup(α(n)), j ∈ Ilow(α(n)), Fi (α(n)) > Fj (α(n)) − τholds for sufficiently large n. This means (i, j) is a (τ, ϵ)feasible pair at α(n) for sufficiently large n. Therefore, in allcases, the set of (τ, ϵ)-feasible pairs at ᾱ is included in thatat α(n) for sufficiently large n. Conversely, the set of (τ, ϵ)violating pairs at α(n) is included in that at ᾱ for sufficiently
large n. Eq.(10) is immediately derived from this fact and thedefinition of Vq (·).
For any M ⊆ L and α ∈ S, we define the point-to-set map
ΓM (α) asΓM (α) , {y ∈ S | yi = αi ∀i ∈ L \ M,It follows from this inequality and Lemma 5 that there exists
a positive integer n1 such thatmin Fi (α(n)) ≤ϵ (ᾱ)i∈Iup

max Fi (α(n)) − τ, ∀n ≥ n1 .

ϵ (ᾱ)
i∈Ilow

By letting n go to infinity in both sides, we havemin Fi (ᾱ) ≤ϵ (ᾱ)i∈Iup

max Fi (ᾱ) − τϵ (ᾱ)
i∈Ilow

which means ᾱ ∈ S \ Ω(τ,ϵ) . Therefore, Ω(τ,ϵ) is a closed set
for any τ > 0 and ϵ ∈ (0, C/2).
Proposition 4: The set Ω(τ,ϵ) converges to Ω∗ as the positive constants τ and ϵ approach 0.
ϵProof: One can easily see that limϵ→0+ Iup(α) =ϵ
Iup (α) and limϵ→0+ Ilow (α) = Ilow (α), where ϵ → 0+means ϵ approaches 0 from right. Thus we havemin Fi (α) >maxi∈Ilow (α)

Fi (α) − τ }.

Furthermore, if τ approaches 0 from right, then the righthand side of the above inequality converges to Ω∗ , that is,limτ →0+ limϵ→0+ Ω(τ,ϵ) = Ω∗ .

∀i ∈ L \ M(12)

Fi (β(n)) ≥

max

(13)

Vq (α(n)) ⊆ Vq (ᾱ)(10)

for sufficiently large n.
Proof: Let (i, j) be any (τ, ϵ)-feasible pair at ᾱ. Then
at least one of the following three conditions holds.
ϵ1) i ∈/ Iup(ᾱ)ϵ2) j ∈/ Ilow(ᾱ)ϵϵ3) i ∈ Iup(ᾱ), j ∈ Ilow(ᾱ), Fi (ᾱ) > Fj (ᾱ) − τϵIn Case 1), it is easily seen from Lemma 5 that i ∈/ Iup(α(n))
for sufficiently large n, which means (i, j) is a (τ, ϵ)-feasible
pair at α(n) for sufficiently large n. In Case 2), we can drawi∈Ilow (β(n))∩M

Fi (β(n))

for all n. It is obvious from (12) thatβ̄i = ᾱi ,∀i ∈ L \ M .

Also, by applying the argument used in the proof of Proposition 2 to (13), we havemin

Let Vq (α) be the family of sets M ⊆ L such that |M | ≤ q
and M contains at least one (τ, ϵ)-violating pair at α ∈ S.
Then the following lemma holds.
Lemma 6: Let {α(n)}∞n=0 be any sequence such thatα(n) ∈ S, ∀n and limn→∞ ᾱ. If ᾱ ∈ S \ Ω(τ,ϵ) thenFi (y)} .

βi (n) = αi (n),i∈Iup (β̄)∩M

B. Convergence Proofmaxi∈Ilow (y)∩M

Lemma 7: For any M ⊆ L, the point-to-set map ΓM (α) is
closed on S.
Proof: Let {α(n)}∞n=0 be any sequence such that α(n) ∈S, ∀n and limn→∞ α(n) = ᾱ ∈ S. Let {β(n)}∞n=0 be any sequence such that β(n) ∈ ΓM (α(n)), ∀n and limn→∞ β(n) =β̄. Then β(n) satisfies

i∈Iup (β(n))∩Mi∈Iup (α)

Fi (y) ≥By using this definition, the set of optimal solutions of thesubproblem in Step 4) can be expressed as ΓLB (k) (α(k)). We
also define a point-to-set map A from S to itself as follows:{∪M ∈Vq (α) ΓM (α), if α ∈/ Ω(τ,ϵ)(11)A(α) =α,
if α ∈ Ω(τ,ϵ)

minlim Ω(τ,ϵ)ϵ→0+= {α ∈ S |mini∈Iup (y)∩M

Fi (β̄) ≥maxi∈Ilow (β̄)∩M

Fi (β̄) .

Therefore β̄ belongs to ΓM (ᾱ) which implies that ΓM (α) is
closed at ᾱ. Since ᾱ can be any point in S, we can conclude
that ΓM (α) is closed on S.
Lemma 8: The point-to-set map A(α) defined by (11) isclosed on S \ Ω(τ,ϵ) .
Proof: Let {α(n)}∞n=0 be any sequence such that α(n) ∈S \ Ω(τ,ϵ) , ∀n and limn→∞ α(n) = ᾱ ∈ S \ Ω(τ,ϵ) . Let{β(n)}∞
n=0 be any sequence such that β(n) ∈ A(α(n)), ∀n
and limn→∞ β(n) = β̄. Then it follows from Lemma 6 that
there exists a positive integer n1 such thatβ(n) ∈ ∪M ∈Vq (ᾱ) ΓM (α(n)),∀n ≥ n1 .

(14)

As shown in Lemma 7, the point-to-set map ΓM (α) is closed
at ᾱ for each M ∈ Vq (ᾱ). Moreover, we easily see from
Lemma 1 that ∪M ∈Vq (ᾱ) ΓM (α) is closed at ᾱ. This result,
together with (14), indicates that β̄ ∈ ∪M ∈Vq (ᾱ) ΓM (ᾱ).
Therefore A(α) is closed at ᾱ ∈ S \ Ω(τ,ϵ) . Since ᾱ can be6

any point in S \ Ω(τ,ϵ) , we can conclude that the point-to-set
map A(α) is closed on S \ Ω(τ,ϵ) .
Lemma 9: The objective function W (α) of Problem 2 is a
descent function for the set of (τ, ϵ)-optimal solutions Ω(τ,ϵ)
and the point-to-set map A(α) defined by (11).
Proof: Let β be any point belonging to A(α). If α ∈/Ω(τ,ϵ) , there exists an M ∈ Vq (α) such that α ∈/ ΓM (α) andβ ∈ ΓM (α). This implies that W (β) < W (α). Therefore
W (α) is a descent function for Ω(τ,ϵ) and A(α).
Now we are ready for giving the global convergence theorem for Algorithm 1, which is the main result of this paper.
Theorem 2: Let {α(k)}∞k=0 be the sequence generated by
Algorithm 1. If the working set LB (k) contains at least one(τ, ϵ)-violating pair at α(k) for all k, then any convergent(τ,ϵ)
subsequence of {α(k)}∞.
k=0 has a limit in Ω
Proof: From the definition of the point-to-set map A(α)
in (11) and the assumption on the working set LB (k), it isapparent that α(k + 1) ∈ A(α(k)) for all k. The sequence{α(k)}∞
k=0 belongs to S which is compact. As shown inLemma 8, the map A(α) is closed on S \ Ω(τ,ϵ) . Also,
as shown in Lemma 9, the objective function W (α) is a
descent function for Ω(τ,ϵ) and A(α). Therefore, we canconclude from Theorem 1 that any convergent subsequence(τ,ϵ)
of {α(k)}∞.
k=0 has a limit in Ω
The following theorem is immediately derived from Theorem 2 and Proposition 3.
Theorem 3: If the working set LB (k) contains at least one(τ, ϵ)-violating pair at α(k) for all k, then Algorithm 1 stopsat Ω(τ,ϵ) within a finite number of iterations for any τ > 0and ϵ ∈ (0, C/2).
Remark 1: According to Proposition 4, we can make Ω(τ,ϵ)
as close as we want to Ω∗ by setting τ and ϵ to sufficiently
small positive numbers. In other words, we can make the limitof the sequence of solutions generated by Algorithm 1 as close
as we want to an optimal solution of Problem 2.
Remark 2: In the above discussion, we have assumed thatthe subproblems can be solved exactly. However, this assumption is not necessarily required. In fact, if it is guaranteed that
W (α(k + 1)) is less than W (α(k)) as far as LB (k) contains
at least one (τ, ϵ)-violating pair at α(k), then Theorems 2 and3 still hold. This weaker condition will be useful in practicalsituations where the subproblems are solved numerically andthus only approximate solutions can be obtained.
Remark 3: If we employ (6) instead of (7) for the optimality
condition, the global convergence of Algorithm 1 cannot be
proved as above because the point-to-set map correspondingto (11) is not closed in this case.
Let us next consider the case where (τ, ϵ)-violating pairs are
not always contained in LB (k). Theorem 2 does not hold inthis case because W (α) is not a descent function for Ω(τ,ϵ) andA(α) defined by (11). However, if at least one (τ, ϵ)-violating
pair is selected for the working set within a certain period of
iterations, Algorithm 1 still has the convergence property. Thisis formally stated as follows.
Theorem 4: Let {α(k)}∞k=0 be the sequence generated by
Algorithm 1. If there exists a positive integer m such that oneof m sets LB (k), LB (k + 1), . . . , LB (k + m − 1) contains
at least one (τ, ϵ)-violating pair at α(k) for all k, then

Algorithm 1 stops at Ω(τ,ϵ) within a finite number of iterations
for any τ > 0 and ϵ ∈ (0, C/2).
Proof: Let us define the point-to-set map Am (α) as
Am (α){∪(M1 ,...,Mm )∈Vqm (α) ΓMm · · · ΓM1 (α), if α ∈/ Ω(τ,ϵ)=α,
if α ∈ Ω(τ,ϵ)
where Vqm (α) is the set of all sequences of the sets
(M1 , M2 , . . . , Mm ) such that 1) Mi ⊆ L, i = 1, 2, . . . , m,2) |Mi | ≤ q, i = 1, 2, . . . , m, and 3) at least one Mi contains
at least one (τ, ϵ)-violating pair at α. Let {α̃(k)}∞k=0 be thesequence defined by α̃(k) = α(mk). Then the sequence{α̃(k)}∞
k=0 satisfiesα̃(k + 1) ∈ Am (α̃(k)) ⊆ S,∀k .

By applying Lemmas 1, 2, 6 and 7 we can easily show that
Am (α) is closed on S \ Ωτ,ϵ . Moreover, it follows from Property 3) of Vqm (α) mentioned above that the objective function
W (α) is a descent function for Ω(τ,ϵ) and Am (α). Thus, byTheorem 1, any convergent subsequence of {α̃(k)}∞k=0 has alimit in Ω(τ,ϵ) . Since S \ Ω(τ,ϵ) is closed for any τ > 0 andϵ ∈ (0, C/2), the convergent subsequence enters Ω(τ,ϵ) within
a finite number of iterations.
V. A PPLICATION TO E XISTING L EARNING A LGORITHMS
In this section, we will discuss the global convergence ofsome existing decomposition methods by applying the results
obtained in the previous section.
A. Generalized SMO Algorithm
Generalized SMO algorithm [9] is a special type of decomposition methods in which the optimality condition is givenby (6) and the working set is composed of a pair of indices(i, j) violating (6) for α = α(k), that is,i ∈ Iup (α(k)), j ∈ Ilow (α(k)), Fi (α(k)) < Fj (α(k)) − τ .
It has already been proved that this algorithm always stops
within a finite number of iterations [9], [11]. We will now showthat almost the same result can be derived by using a theorem
in the previous section. To do so, we need to modify thegeneralized SMO algorithm slightly; the optimality conditionis given by (7) instead of (6), and the working set is composedof a (τ, ϵ)-violating pair at α(k) where τ and ϵ are sufficiently
small positive numbers. Then it is easily seen from Theorem 3
that the algorithm stops within a finite number of iterations.
B. SVMlight
SVMlight proposed by Joachims [6] is one of the mostwidely used decomposition methods for SVMs. The optimality
condition used in SVMlight is given by (6) and the working
set selection is done in a systematic way as follows:
Algorithm 2: Given an even number q(≤ l) and the current
solution α(k) ∈ S, execute the following procedures.
1) Sort {Fi (α(k))}li=1 in decreasing order. Let the list of
subscripts of the sorted list be i1 , i2 , . . . , il .

72) Set LB (k) = ∅, v = 0, m = 1 and n = l.
3) While im ̸∈ Ilow (α(k)) and m ≤ l, add 1 to m.
4) While in ̸∈ Iup (α(k)) and n ≥ 1, subtract 1 from n.
5) If m ≥ n then stop. Otherwise, add 2 to v and add{m, n} to the set LB (k).
6) If v = q then stop. Otherwise, go to Step 3).
For more details on the working set selection of SVMlight ,please consult [14].
As well as in case of the generalized SMO algorithm, weneed to modify both the optimality condition and the working
set selection in SVMlight in order to apply the results inthe previous section; the optimality condition is given by (7)instead of (6) and the working set selection is done by thefollowing algorithm:
Algorithm 3: Given an even number q(≤ l) and the current
solution α(k) ∈ S, execute the following procedures.
1) Sort {Fi (α(k))}li=1 in decreasing order. Let the the listof subscripts of the sorted list be i1 , i2 , . . . , il .
2) Set LB (k) = ∅, v = 0, m = 1 and n = l.
ϵ3) While im ̸∈ Ilow(α(k)) and m ≤ l, add 1 to m.
ϵ4) While in ̸∈ Iup (α(k)) and n ≥ 1, subtract 1 from n.
5) If m ≥ n then stop. Otherwise, add 2 to v and add{m, n} to the set LB (k).
6) If v = q then stop. Otherwise, go to Step 3).
We will show that LB (k) obtained by Algorithm 3 contains
at least one (τ, ϵ)-violating pair if α(k) ∈ S\Ω(τ,ϵ) . Recall thatα ∈ Ω(τ,ϵ) if and only if (7) holds. Thus if α(k) ∈ S \ Ω(τ,ϵ) ,the following inequality holds.
minϵ (α(k))i∈Iup

Fi (α(k)) + τ ≤max

ϵ (α(k))i∈Ilow

Fi (α(k))(15)

Let m1 be the value of m at the instance when Algorithm 3
ϵfirst exits Step 3). Then im1 ∈ Ilow(α(k)) and Fim1 (α(k)) =ϵ (α(k)) Fi (α(k)). Also, let n1 be the value of nmaxi∈Ilowat the instance when Algorithm 3 first exits Step 4). Thenϵϵ (α(k)) Fi (α(k)).
(α(k)) and Fin1 (α(k)) = mini∈Iup
in1 ∈ Iup
It follows from (15) that Fn1 (α(k)) + τ ≤ Fm1 (α(k)) which
implies that (n1 , m1 ) is a (τ, ϵ)-violating pair at α(k) and that
m1 < n1 . Therefore LB (k) obtained by Algorithm 3 contains
at least one (τ, ϵ)-violating pair at α(k).
By applying Theorem 3, we can conclude that SVMlightwith the optimality condition (7) and the working set selection
described by Algorithm 3 stops within a finite number of
iterations after finding a (τ, ϵ)-optimal solution.
Remark 4: In the software package SVMlight the optimality
condition and the working set selection are not implemented
exactly as described in (6) and Algorithm 2, respectively, forpractical reason. Difference is in the definition of Iup (α) andIlow (α). In the software, the following definitions are used:
Iup (α) = {i | αi < C − ϵ, di = 1} ∪ {i | αi > ϵ, di = −1} ,Ilow (α) = {i | αi < C − ϵ, di = −1} ∪ {i | αi > ϵ, di = 1}
where ϵ is a sufficiently small positive number. It is worthϵϵ(α)
noting that these definitions are same as Iup(α) and Ilow
except for the equal sign. The results of this paper show thatthe relaxation of the optimality condition has not only practicalbut also theoretical significance.

VI. C ONCLUDING R EMARKS
Global convergence property of decomposition methods
for SVMs are studied. We have first introduced a relaxed
optimality condition, and then proved a decomposition method
stops within a finite number of iterations after finding an
optimal solution if the working set selection satisfies a certain
condition. We have also shown that the generalized SMO
algorithm and SVMlight satisfy this condition and thus havethe global convergence property. Since our new convergence
theorems require little restriction on the working set selection
method, the authors believe that they can be applied to a wideclass of decomposition methods.
R EFERENCES[1] V. Vapnik, Statistical Learning Theory. New York: Wiley, 1998.
[2] B. Schölkopf, C. J. C. Burges, and A. J. Smola, Eds., Advances in Kernel
Methods: Support Vector Learning. Cambridge, Massachusetts: MIT
Press, 1999.
[3] N. Cristianini and J. Shawe-Taylor, An Introduction to Support Vector
Machines and Other Kernel-Based Learning Methods. Cambridge, UK:
Cambridge University Press, 2000.
[4] S. Haykin, Neural Networks. Upper Saddle River, NJ: Prentice Hall,
1999.
[5] J. C. Platt, “Fast training of support vector machines using sequential
minimal optimization,” in Advances in Kernel Methods: Support Vector
Machines, B. Schölkopf, C. Burges, and A. Smola, Eds. Cambridge,
MA: MIT Press, 1998.
[6] T. Joachims, “Making large-scale support vector machine learning
practical,” in Advances in Kernel Methods: Support Vector Machines,
B. Schölkopf, C. Burges, and A. Smola, Eds. Cambridge, MA: MIT
Press, 1998.
[7] S. S. Keerthi, S. K. Shevade, C. Bhattacharyya, and K. R. K. Murthy,“Improvements to Platt’s SMO algorithm for SVM classifier design,”
Neural Computation, vol. 13, pp. 637–649, 2001.
[8] C.-W. Hsu and C.-J. Lin, “A simple decomposition method for support
vector machines,” Machine Learning, vol. 46, pp. 291–314, 2002.
[9] S. S. Keerthi and E. G. Gilbert, “Convergence of a generalized SMO
algorithm for SVM classifier design,” Machine Learning, vol. 46, pp.
351–360, 2002.
[10] C.-J. Lin, “Asymptotic convergence of an SMO algorithm without any
assumption,” IEEE Trans. Neural Networks, vol. 13, pp. 248–250, Jan.
2002.
[11] N. Takahashi and T. Nishi, “Rigorous proof of termination of SMO
algorithm for support vector machines,” IEEE Trans. Neural Networks,
vol. 16, no. 3, pp. 774–776, May 2005.
[12] P.-H. Chen, R.-E. Fan, and C.-J. Lin, “A study on SMO-type decomposition methods for support vector machines,” to appear in IEEE Trans.
Neural Networks.
[13] C.-C. Chang, C.-W. Hsu, and C.-J. Lin, “The analysis of decomposition
methods for support vector machines,” IEEE Trans. Neural Networks,
vol. 11, no. 4, pp. 1003–1008, 2000.
[14] C.-J. Lin, “On the convergence of the decomposition method for support
vector machines,” IEEE Trans. Neural Networks, vol. 12, pp. 1288–1298,
Nov. 2001.
[15] ——, “A formal analysis of stopping criteria of decomposition methods
for support vector machines,” IEEE Trans. Neural Networks, vol. 13,
pp. 1045–1052, Sept. 2002.
[16] N. List and H. U. Simon, “A general convergence theorem for thedecomposition method,” in Proceedigns of the 17th Annual Conference
on Learning Theory, 2004, pp. 363–377.
[17] D. G. Luenberger, Linear and Nonlinear Programming. Reading, MA:
Addison-Wesley Publishing, 1989.