Global Convergence of SMO Algorithm for
Support Vector Regression
Author(s): Norikazu Takahashi, Jun Guo and Tetsuo Nishi
Journal: IEEE Transactions on Neural Networks
Volume: 19
Number: 6
Pages: 971–982
Month: June
Year: 2008
Published Version: http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=4479862c⃝2008IEEE. 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 SMO Algorithm for
Support Vector Regression
Norikazu Takahashi, Member, IEEE, Jun Guo, and Tetsuo Nishi, Fellow, IEEE

Abstract— Global convergence of the sequential minimal optimization (SMO) algorithm for support vector regression (SVR) is
studied in this paper. Given l training samples, SVR is formulated
as a convex quadratic programming problem with l pairs ofvariables. We prove that if two pairs of variables violating the
optimality condition are chosen for update in each step andsubproblems are solved in a certain way then the SMO algorithm
always stops within a finite number of iterations after finding an
optimal solution. Also, efficient implementation techniques for
the SMO algorithm are presented and compared experimentallywith other SMO algorithms.
Index Terms— support vector regression, sequential minimal
optimization, convergence, quadratic programming

I. I NTRODUCTIONT

RAINING of a support vector machine (SVM) for patternclassification is formulated as a quadratic programming(QP) problem in a number of variables equal to the number oftraining samples [1]. Recently several decomposition methods
for solving QP problems arising in the training of SVMs
have been proposed [2]–[6]. Sequential minimal optimization (SMO) algorithm proposed by Platt [3] and SVMlight
proposed by Joachims [4] are well-known and widely useddecomposition methods. The basic strategy commonly used inthese methods is to repeat two operations: 1) choosing a fixed
number of variables and 2) solving the QP subproblem withrespect to the selected variables, until an optimal solution isfound. Compared with the direct application of traditional QP
solvers, decomposition methods not only use less amount ofmemory but also require shorter computation time. In addition,some properties on global convergence of the method haverecently been clarified [7]–[15].
This paper considers SMO algorithms for support vector
regression (SVR). Given l training samples, SVR is formulated
as a QP problem with 2l variables, say α1 , α2 , . . ., αl , α̂1 ,
α̂2 , . . ., α̂n , where two variables αi and α̂i are closely related
to each other.
A simple approach to this problem is to consider the 2lvariables: α1 , α2 , . . ., αl , α̂1 , α̂2 , . . ., α̂n , are independent
from each other and to apply decomposition methods forThis work was presented in part at the 2006 International Joint Conference
on Neural Networks, Vancouver, BC, Canada, July 16–21, 2006. This work
was partly supported by the Okawa Foundation research grant, the Ministry of
Education, Culture, Sports, Science and Technology, Grant-in-Aid for JSPS
Research Fellows, 18-9473, and the 21st Century COE Program “Reconstruction of Social Infrastructure Related to Information Science and ElectricalEngineering”.
N. Takahashi and J. Guo are with the Department of Computer Science andCommunication Engineering, Kyushu University, Fukuoka, 819-0395 Japan(norikazu@csce.kyushu-u.ac.jp, guojun@kairo.csce.kyushu-u.ac.jp).
T. Nishi is with the Faculty of Science and Engineering, Waseda University,
Tokyo, 162-0072 Japan (nishi-t@waseda.jp).

pattern classification directly. For example, a software librarycalled LIBSVM [16], [17] selects two variables from the 2lvariables and solves the QP subproblem with respect to theselected variables in each step. This is thought of as a special
case of the generalized SMO algorithm [13]. An advantagesof this approach is that the global convergence is guaranteedby some existing results concerning the global convergence ofthe decomposition methods [7]–[15].
On the other hand, many researchers have tried to develop
SVR-oriented SMO algorithms by making use of the close
relationship between αi and α̂i . Smola and Schölkopf [18]proposed an SMO algorithm for SVR by extending the basic
idea of Platt’s SMO. This algorithm selects two pairs ofvariables (or four variables): αi , α̂i , αj and α̂j , in each step
according to the strategy similar to Platt’s SMO, and solves
the QP subproblem with respect to the selected variables
analytically by considering four cases depending on the valuesof two pairs of variables. Shevade et al. [19] pointed out thatthe method for updating the bias in Smola and Schölkopf’s
algorithm is inefficient, and made some improvements. Also,
they proposed a new method for selecting variables based on
the degree of violation of the optimality condition. Flake andLawrence [20] showed that the QP problems with 2l variables
can be transformed into non-smooth optimization problems
with l variables βi , αi − α̂i , i = 1, 2, . . . , l, and proposed
an SMO algorithm for solving these non-smooth optimization
problems. An advantage of Flake and Lawrence’s algorithm isthat the procedure for solving subproblems can be expressedin a very simple form.
While the global convergence property of SMO algorithms
for pattern classification has been clarified by several researchers [12]–[15], this is not the case at all for the above
mentioned SMO algorithms for SVR. The most important difference is that SMO algorithms for SVR choose four variables
in each step while those for pattern classification choose two.
For this reason, the existing results cannot be directly applied
to the convergence analysis of SMO algorithms for SVR.
In this paper, we study the global convergence of a general
SMO algorithms based on Flake and Lawrence’s formulation.
By using the same approach as in [13] and [14], we provethat the algorithm reaches an optimal solution within a finite
number of iterations if two conditions are satisfied. One isthat the algorithm must choose two variables violating the
optimality condition in each step. The other is that the valuesof the selected variables must be updated by using not an exact
solution of the subproblem but an approximate solution in acertain situation. One may think this is strange, but, as far as
the approach based on [13] and [14] is concerned, the global
convergence cannot be proved without this condition.

2This paper is organized as follows. Section II describes thebasic principle of SVR and Flake and Lawrence’s formulation
as a non-smooth optimization problem. In Section III, the optimality condition for the problem, the notion of violating pair,
and a general form of the SMO algorithm are presented. How
to solve subproblems is addressed in Section IV. In Section V,
we give a rigorous proof for the global convergence of the
SMO algorithm. Implementation issues will be discussed in
Section VI. Finally, Section VII provides our conclusion.
II. S UPPORT V ECTOR R EGRESSION
Consider a set of training samples {(xi , yi )}li=1 , where xi ∈d
R is the i-th sample value of the input vector, yi ∈ R is thecorresponding value of the model output and l is the numberof training samples. The goal of regression is to provide anestimate of the dependence of y on x, which can be expressedasy = f (x) + ν

0 ≤ αi ≤ C, i = 1, 2, . . . , l(2)0 ≤ α̂i ≤ C, i = 1, 2, . . . , l(3)T

where K(xi , xj ) = ϕ(xi ) ϕ(xj ) and ε is a user-specified
positive constant.
Let F1 ⊂ R2l be the feasible region of Problem 1. K(·, ·)in the objective function Q(α) is called a kernel function.
Throughout this paper, we assume that the kernel function
K(·, ·) satisfies Mercer’s condition. It is thus always guaranteed that the l × l matrix K = [kij ] with kij = K(xi , xj ) is
positive semi-definite.
Let α∗ = [α1∗ , α2∗ , . . . , αl∗ , α̂1∗ , α̂2∗ , . . . , α̂l∗ ]T be any optimal
solution of Problem 1. Then it follows from the Karush-KuhnTucker (KKT) conditions for Problem 1 that the conditionαi∗ α̂i∗ = 0, i = 1, 2, . . . , l(4)holds [18], [19]. This means that the set of optimal solutionsof Problem 1 does not change even though the condition

where f (·) is an unknown nonlinear function and ν is a noise
independent of x.
Basic concepts of SVMs can be applied to regression problems by introducing a certain loss function such as quadratic
function, Laplace function, Huber function and ε-insensitive
function. Among them, ε-insensitive function is one of themost widely used loss functions because it can produce sparse
support vectors. Throughout this paper, we will focus ourattention on SVR with the ε-insensitive function defined as{0
if |x| < ε|x|ε =|x| − ε otherwise

is added to the constraints (1)–(3). Let us now introduce
new variables βi = αi − α̂i for i = 1, 2, . . . , l. Then,since αi + α̂i can be expressed as |βi | under the conditions(2), (3) and (5), Problem 1 can be reformulated in terms of
β = [β1 , β2 , . . . , βl ]T as follows [20]:Problem 2: Find β = [β1 , β2 , . . . , βl ]T ∈ Rl that minimizes

In SVR, the unknown function f (x) is assumed to be
expressed in the following form:

subject to the constraints:

αi α̂i = 0, i = 1, 2, . . . , lW (β) = −l∑yi βi + ε

i=1

l
∑

C

l
∑

|yi − fSVR (xi )|ε + ∥w∥2

i=1

is minimized, where C is a positive constant, | · |ε is the εinsensitive loss function defined above, and || · || denotes the
Euclidean norm. The dual form of this problem leads to thefollowing convex QP problem with 2l variables.
Problem 1: Find α = [α1 , α2 , . . . , αl , α̂1 , α̂2 , . . . , α̂l ]T ∈2l
R that minimizesll∑∑Q(α) = −yi (αi − α̂i ) + ε(αi + α̂i )
i=1

i=1

(αi − α̂i ) = 0

i=1−C ≤ βi ≤ C, i = 1, 2, . . . , lNote that the objective function W (β) is neither quadratic
nor differentiable any more. However, it is still convex andtherefore Problem 2 has no local minimum. In the following,
the feasible region of Problem 2 is denoted by F2 ⊂ Rl . It isapparent that F2 is not empty.
Let β ∗ = [β1∗ , β2∗ , . . . , βl∗ ]T be any optimal solution of
Problem 2. Then the approximating function fSVR (x) derived
by SVR can be expressed asfSVR (x) =l∑βi∗ K(xi , x) + b

i=1

where the value of b is determined so thatl∑βi∗ K(xi , xm ) + b = ym − ε∗holds for any m such that 0 < βm
< C orfSVR (xn ) =
(1)

(6)

βi = 0i=1

subject to the constraints:
l
∑

l

i=1

fSVR (xm ) =

l
l
1 ∑∑
+
(αi − α̂i )(αj − α̂j )K(xi , xj )2 i=1 j=1

1 ∑∑βi βj kij
2 i=1 j=1l|βi | +

i=1

fSVR (x) = wT ϕ(x) + b
where w is the coefficient vector, b is the bias, and ϕ(·) isthe pre-specified nonlinear mapping. Values of the coefficient
vector and the bias are determined so that the functional
defined by

l
∑

(5)

l
∑

βi∗ K(xi , xn ) + b = yn + ε

i=1holds for any n such that −C < βn∗ < 0 [20].

3III. SMO A LGORITHM FOR SVR
In this section, we present a general form of SMO algorithms for solving Problem 2. Before doing so, we derive
the optimality condition for Problem 2. We also introduce thenotion of violating pairs.
A. Optimality Condition
As shown in [19], it follows from the KKT condition for
Problem 1 that α = [α1 , α2 , . . . , αl , α̂1 , α̂2 , . . . , α̂l ] ∈ F1 isan optimal solution if and only if there exists a constant λ suchthat the following conditions are satisfied for i = 1, 2, . . . , l.
∑l1) If 0 < αi < C and α̂i = 0 then yi − ε − j=1 (αj −α̂j )kij = λ.
∑l2) If αi = 0 and 0 < α̂i < C then yi + ε − j=1 (αj −α̂j )kij = λ.
∑l3) If αi = C and α̂i = 0 then yi −ε− j=1 (αj − α̂j )kij ≥λ.
∑l4) If αi = 0 and α̂i = C then yi +ε− j=1 (αj − α̂j )kij ≤λ.
∑l5) If αi = α̂i = 0 then yi − ε − j=1 (αj − α̂j )kij ≤ λ∑land yi + ε − j=1 (αj − α̂j )kij ≥ λ.
Substituting βi = αi − α̂i into these conditions, we can derive
the optimality conditions for Problem 2 as follows: +hi (β) ≤ −λ,if βi = Cif 0 < βi < C h+i (β) = −λ,+(7)h−i (β) ≤ −λ ≤ hi (β), if βi = 0(β) = −λ,if −C < βi < 0
 h−
i

 −
hi (β) ≥ −λ,if βi = −C
whereh±i (β) = −yi ± ε +l∑kij βj .

(8)

j=1

Since (7) is rewritten as
max h+
i (β) ≤ − λβi =C+
max h+
i (β) ≤ − λ ≤ min hi (β)
0<βi <C
0<βi <C+
max h−
i (β) ≤ − λ ≤ min hi (β)
βi =0
βi =0
max h−min h−
i (β) ≤ − λ ≤i (β)−C<βi <0−C<βi <0− λ ≤ min h−i (β)βi =−Cwe can express the optimality condition by a single inequality
as follows:
{
}
−
max
max h+
(β),
max
h
(β)
i
i
0<βi ≤C−C<βi ≤0
{
}
−
+
≤ min
min hi (β), min hi (β) . (9)−C≤βi <00≤βi <C

Let Di+ W (β) and Di− W (β) denote the right-hand and lefthand partial derivatives of W (β) with respect to βi , that is,
W (β + δei ) − W (β)
δ
W
(β
+
δe
i ) − W (β)
Di− W (β) = lim
δ→0−δ
Di+ W (β) = lim

δ→0+where ei is the vector whose i-th element is +1 and others are
zero. Then it is easily seen that in F2 these partial derivatives−
can be expressed in terms of h+i (β) and hi (β) defined in (8)as follows:{ +hi (β), βi ≥ 0
Di+ W (β) =(β), βi < 0h−{ i+hi (β), βi > 0
Di− W (β) =h−i (β), βi ≤ 0
Therefore, the optimality condition (9) can be rewritten in a
simpler form asmax−C<βi ≤C

Di− W (β) ≤min−C≤βi <C

Di+ W (β) .

(10)Since the SMO algorithm generally does not provide anexact optimal solution in a finite number of iterations, we willconsider hereafter the relaxed optimality condition:max−C<βi ≤C

Di− W (β) ≤min−C≤βi <C

Di+ W (β) + τ(11)instead of (10), where τ is a positive tolerance parameter.
Eq.(11) is called the τ -optimality condition.
B. Violating Pair
With the strict optimality condition (10), we can define theviolating pair as follows; a pair of indices (i, j) is said to bea violating pair at β ∈ F2 if the following conditions hold:−C < βi ≤ C, −C ≤ βj < C, Di− W (β) > Dj+ W (β)
It is obvious that the optimality condition (10) holds at β if
and only if there exists no violating pair at β. Similarly, we
can define the violating pair corresponding to (11). A pair ofindices (i, j) satisfying−C < βi ≤ C, −C ≤ βj < C, Di− W (β) > Dj+ W (β) + τ(12)
is called a τ -violating pair at β ∈ F2 . The τ -optimality
condition (11) holds at β if and only if there exists no τ violating pair at β. It is very important to note here that
two statements “(i, j) is a τ -violating pair” and “(j, i) is a
τ -violating pair” must be distinguished in this paper.
C. SMO Algorithm
A general SMO algorithm for solving Problem 2 is described as follows:
Algorithm 1: Given training samples {(xi , yi )}li=1 , kernel
function K(·, ·) and positive constants C, ε and τ , execute thefollowing procedure.
Step 1: Set n := 0 and choose an initial point β (0) ∈ F2 .
Step 2: If β = β (n) satisfies the τ -optimality condition (11)then stop.
Step 3: Choose a τ -violating pair (i(n) , j (n) ) at β (n)and solve Problem 2 under the additional constraints βk =(n)βk , ∀k ̸∈ {i(n) , j (n) }. Let β (n+1) be the point thus obtained.
Set n := n + 1 and go to Step 2.
It is apparent that the objective function W (β) is boundedfrom below in the feasible region F2 and the sequence4{W (β (n) )}∞n=0 obtained by Algorithm 1 is monotone decreasing, that is, W (β (n+1) ) ≤ W (β (n) ) holds for all n. Therefore
W (β (n) ) necessarily converges to a certain value. On the other
hand, however, it is not clear whether or not Algorithm 1
always stops within a finite number of iterations. To make clear
the condition which guarantees the termination of Algorithm 1
is one of the main goal in this paper.
Since the optimization problems arising in Step 3, which
will be called subproblems in the following, have only twovariables, they can be solved very easily. In the next section,
we will describe in detail how these subproblems can besolved.
IV. H OW TO S OLVE S UBPROBLEMSAs a general form of subproblems arising in Step 3 ofAlgorithm 1, we will consider in this section the following
problem: Given a point β̃ = [β̃1 , β̃2 , . . . , β̃l ]T ∈ F2 and two
indices i, j ∈ {1, 2, . . . , l} such that (i, j) is a τ -violating
pair at β̃, find β that minimizes W (β) under the constraints
β ∈ F2 and βk = β̃k , ∀k ̸= i, j. This problem has essentiallyonly two variables βi and βj and they must satisfy βi + βj =β̃i + β̃j . Therefore it is convenient for us to parameterize β
as β(t) = [β1 (t), β2 (t), . . . , βl (t)]T whereβi (t) = β̃i + t,

βj (t) = β̃j − t,βk (t) = β̃k , ∀k ̸= i, j.

Then the problem can be reformulated as follows:
Problem 3: Find t that minimizes
ψ(t) = W (β(t))= (−yi +l∑k=1

β̃k kik + yj −l∑β̃k kjk )t

k=1

1+ ηt2 + ε|β̃i + t| + ε|β̃j − t| + Wc
2
subject to −C ≤ βi (t) ≤ C and −C ≤ βj (t) ≤ C, whereη = kii + kjj − 2kij ≥ 0 and Wc represents a collection of
constant terms.
We now introduce some notations for later discussions.
First, according to the notation used in [13], we express(n)(βi , βj ) as βij for simplicity. We also use βij and βij (t)in the same sense. Let S be the square region defined by
S = [−C, C] × [−C, C] ⊂ R2 . Let S1 , S2 , S3 and S4 be foursquare regions defined as follows:
S1 = {βij ∈ S : 0 < βi ≤ C, 0 ≤ βj < C}
S2 = {βij ∈ S : −C < βi ≤ 0, 0 ≤ βj < C}
S3 = {βij ∈ S : −C < βi ≤ 0, −C ≤ βj < 0}
S4 = {βij ∈ S : 0 < βi ≤ C, −C ≤ βj < 0}
The interior and boundary of each region Si are denotedby intSi and ∂Si , respectively. Similarly, the interior andboundary of the region S are denoted by intS and ∂S,
respectively. Vertices of four square regions S1 , S2 , S3 and S4
are denoted by V1 = (C, 0), V2 = (C, C), V3 = (0, C), V4 =(−C, C), V5 = (−C, 0), V6 = (−C, −C), V7 = (0, −C) and

βj
V4

E3

V3

E2

V2

E4

S2

E9

S1

E1

V5

E10

O

E12

V1

S

βi
E5

S3

V6

E6

V7

E11 S4E8

E7

V8Fig. 1. Square regions S, S1 , . . . , S4 , vertices V1 , V2 , . . . , V8 , and sides
E1 , E2 , . . . , E12 .

V8 = (C, −C). Also, the sides excluding vertices of squareregions, are denoted by E1 , E2 , . . . , E12 as
E1 = {βij ∈ S : βi = C, 0 < βj < C},
E2 = {βij ∈ S : 0 < βi < C, βj = C},
and so on (see Fig.1).
Figure 2 shows the diagonal line on which the point βij (t)moves with t, and the graph of the objective function ψ(t)versus t. It is obvious that the objective function ψ(t) is convex
and hence there is no local minimum. However, since ψ(t)is not differentiable at t = −β̃i and t = β̃j , we need toconsider two types of derivatives: the right-hand and left-handderivatives defined by
ψ(t + δ) − ψ(t)δ→0+δ
ψ(t + δ) − ψ(t)′ψ− (t) = lim
δ→0−
δ
′
ψ+
(t) = limat these two points. With these notations, we can say, forexample, that t = t∗ is an optimal solution of Problem 3′′if βij (t∗ ) is an interior point of S and ψ−(t∗ ) ≤ 0 ≤ ψ+
(t∗ )
′
′
holds. Here we should note that ψ− (t) = ψ+ (t) holds for anyt ̸∈ {−β̃i , β̃j }.
Lemma 1: The following equations hold for the derivativesof ψ(t) and W (β).
′ψ+(t) =Di+ W (β(t)) − Dj− W (β(t))

(13)

′
ψ−
(t) =Di− W (β(t)) − Dj+ W (β(t))(14)
Proof: We will prove only (13) because (14) can be donein the same way. Since dβi (t)/dt = 1 and dβj (t)/dt = −1,
the right-hand derivative of ψ(t) at t = 0 can be expressed asfollows:
dβj (t)dβi (t)′+ Dj− W (β̃) ·ψ+(0) =Di+ W (β̃) ·
dt
dt
+
−
=Di W (β̃) − Dj W (β̃)(15)′′
Furthermore, since ψ+(t) = ψ+(0) β̃=β(t) holds, by substi-

tuting β̃ = β(t) into (15) we can derive (13).

5βj(βi (t), βj (t))
t = −β̃it = β̃jt=0βi(β̃i , β̃j )

(a)

ψ(t)
′
(β̃j )
ψ+′ψ−(β̃j )

β̃j

−β̃i

0

t

(b)
Fig. 2. (a) Diagonal line represented by (βi (t), βj (t)). (b) Objective function
ψ(t) and its right-hand and left-hand derivatives.

Lemma 2: The pair of indices (i, j) is a τ -violating pair atβ(t) if and only if′−C < βi (t) ≤ C, −C ≤ βj (t) < C, ψ−(t) > τ .
Proof: The conditions can be immediately derived bysubstituting (14) into (12).
Lemma 3: Let t∗ be an optimal solution of Problem 3. Then∗t < 0.
Proof: Since (i, j) is a τ -violating pair at β(0) = β̃, it′follows from Lemma 2 that β̃i > −C, β̃j < C and ψ−(0) >τ > 0. Since ψ(t) is convex, t∗ must be negative.
Lemma 4: t∗ is an optimal solution of Problem 3 if andonly if one of the following two conditions hold.
′∗′∗1) βij (t∗ ) ∈ intS
( 5 and ψ−) (t () ≤5 0 ≤ ψ)+ (t ) ′ ∗∗2) βij (t ) ∈ ∪k=3 {Vk } ∪ ∪k=2 Ek and ψ+ (t ) ≥ 0
Proof: It is apparent from the convexity of ψ(t) andLemma 3.
We easily see from these lemmas that an optimal solution t∗
can be found by decreasing the value of t from 0 until βij (t)satisfies one of two conditions given in Lemma 4. This search
process is formally stated as follows.
Algorithm 2: For Problem 3, find t∗ by executing the following procedure.
Step 1: Set m := 0 and tm := 0.

′
Step 2: If η ̸= 0 then set tmin := −ψ−(tm )/η. Otherwise,
set tmin := −∞.
Step 3: Let Sk be the region to which βij (tm ) belongs. If
βij (tmin ) ∈ Sk then set t∗ := tmin and stop. Otherwise, sett̂min := inf{t : βij (t) ∈ Sk }.
Step 4: If either i) βij (t̂min ) ∈ ∂S or ii) βij (t̂min ) ∈ intS′and ψ−(t̂min ) ≤ 0 holds, set t∗ := t̂min and stop. Otherwise
set m := m + 1 and tm := t̂min and go to Step 2.
One can easily see that t∗ found by Algorithm 2 is always
an optimal solution of Problem 3. However, we will hereafter
not consider Algorithm 2 but Algorithm 3 given below, which′
is obtained by replacing the condition ψ−(t̂min ) ≤ 0 in Step 4′of Algorithm 2 with ψ− (t̂min ) ≤ τ where τ is the positivetolerance parameter introduced in (11). The reason why we
do not consider Algorithm 2 will be explained later.
Algorithm 3: For Problem 3, find t∗∗ by executing thefollowing procedure.
Step 1: Set m := 0 and tm := 0.
′
Step 2: If η ̸= 0 then set tmin := −ψ−(tm )/η. Otherwise,
set tmin := −∞.
Step 3: Let Sk be the region to which βij (tm ) belongs. If
βij (tmin ) ∈ Sk then set t∗∗ := tmin and stop. Otherwise, sett̂min := inf{t : βij (t) ∈ Sk }.
Step 4: If either i) βij (t̂min ) ∈ ∂S or ii) βij (t̂min ) ∈ intS′and ψ−(t̂min ) ≤ τ holds, set t∗∗ := t̂min and stop. Otherwise
set m := m + 1 and tm := t̂min and go to Step 2.
Difference in the behavior of Algorithms 2 and 3 is illustrated in Fig.3 where it is assumed that ψ(t) is minimized
at t = tA , the point (β1 (tA ), β2 (tA )) belongs to S, ψ(t) is
not smooth at t = tB ∈ (tA , 0), and the derivatives of ψ(t)′′at t = tB satisfy 0 < ψ−(tB ) ≤ τ < ψ+(tB ). In this case,
Algorithm 2 returns the optimal solution tA while Algorithm 3
returns the approximate solution tB .
The following lemma shows some important properties of
Algorithm 3.
Lemma 5: Let t∗∗ be the solution obtained by Algorithm 3.
Then the following statements hold true.
1) ψ(t∗∗ ) < ψ(0).
2) The right-hand derivative of ψ(t) at t = t∗∗ satisfies′ψ+(t∗∗ ) ≥ 0

in any case. The left-hand derivative satisfies′(t∗∗ ) ≤ τ
ψ−

(16)

∗∗

if βij (t ) ∈ intS. In particular,′′ψ−(t∗∗ ) = ψ+(t∗∗ ) = 0

holds if βij (t∗∗ ) ∈ ∪4k=1 intSk .
3) The pair (i, j) is not a τ -violating pair at β(t∗∗ ).
4) The following inequality holds:
τ(17)
ψ(0) − ψ(t∗∗ ) ≥ √ ∥β̃ − β(t∗∗ )∥2 2
where ∥ · ∥ is the Euclidean norm.
Proof: It is obvious from Lemma 3 and Algorithm 3 thatthe first and second statements hold true. Substituting (14) into
(16), we have
Di− W (β(t∗∗ )) ≤ Dj+ W (β(t∗∗ )) + τ6′
Substituting tQ = t2 − ψ−(t2 )/η and taking (18) into account,
we derive (19). Therefore (19) holds for any η ≥ 0. Applying
the above argument to the intervals t2 ≤ t ≤ t1 and t1 ≤ t ≤0, we have
τ(20)
ψ(t1 ) − ψ(t2 ) ≥ (t1 − t2 )2τψ(0) − ψ(t1 ) ≥ (−t1 )(21)
2
From (19)-(21), we obtainττ
ψ(0) − ψ(t∗∗ ) ≥ (−t∗∗ ) = √ ∥β̄ − β(t∗∗ )∥
2
2 2

ψ(t)
′
(tB ) > τψ+′ψ−(tB ) ≤ τt∗ = tA tBt(a)which completes the proof.
We should note that the inequality like (17) cannot bederived for Algorithm 2. Inequality (17) plays an importantrole in our convergence proof for Algorithm 1, which will bepresented in the next section. This is the main reason why weconsider Algorithm 3 instead of Algorithm 2.

ψ(t)
′
ψ+
(tB ) > τ

V. G LOBAL C ONVERGENCE OF A LGORITHM 1′
ψ−(tB ) ≤ τtAt∗∗ = tBt(b)
Fig. 3.

Comparison between (a) Algorithm 2 and (b) Algorithm 3.

which implies that (i, j) is not a τ -violating pair. Thus the thirdstatement holds true. The fourth statement can be proved in
the same way as [13, Lemma 1]. Let m̄ be the value of mwhen Algorithm 3 stops. Then there are three possible cases:m̄ = 0, m̄ = 1 and m̄ = 2. We will consider here only thelast one, because it is the most general among three. In thiscase, ψ(t) can be expressed as1′
ψ(t) = η(t − t2 )2 + ψ−(t2 )(t − t2 ) + ψ(t2 )2in the interval t∗∗ ≤ t ≤ t2 , where we easily see from Step 4of Algorithm 3 that′ψ−(t2 ) > τ .

(18)

Let us show now thatτ(t2 − t∗∗ )(19)
2holds for any η ≥ 0. Suppose first that η = 0. Since ψ(t) is
linear in this case, we have from (18) that ψ(t2 ) − ψ(t∗∗ ) >τ (t2 − t∗∗ ). Thus (19) apparently holds. Suppose next thatη > 0. If the constraint βij (t) ∈ S is ignored, the function′
ψ(t) is minimized at t = tQ , t2 − ψ−(t2 )/η < 0. Since∗∗tQ ≤ t ≤ t2 and ψ(t) is convex, we haveψ(t2 ) − ψ(t∗∗ ) ≥t∗∗ − tQ
t2 − t∗∗· ψ(tQ ) +· ψ(t2 ) ≥ ψ(t∗∗ ) .
t2 − tQ
t2 − tQ′
Since ψ(tQ ) = ψ(t2 ) − (ψ−(t2 ))2 /(2η), the above inequality
can be transformed as follows:′(t2 ))2t2 − t∗∗ (ψ−ψ(t2 ) − ψ(t∗∗ ) ≥·t2 − tQ2η

In this section, we prove the convergence of Algorithm 1
under the assumption that the subproblems in Step 3 are solved
approximately by Algorithm 3. Although the subproblems are
not solved exactly, it is apparently true that β (n) belongs to thefeasible region F2 of Problem 2 for all n and that W (β (n) ) ismonotone decreasing with respect to n. This implies that thesequence {W (β (n) )}∞n=0 converges to a certain value since
W (β) is bounded from below in F2 .
The following theorem is the main result of this paper.
Theorem 1: Algorithm 1 stops in a finite number of iterations for any τ > 0 if subproblems in Step 3 are solved
approximately by Algorithm 3.
For any execution of Algorithm 1, we define the set of
integers L(p, q) as
L(p, q) = {n : (i(n) , j (n) ) = (p, q)}
where (p, q) is any pair of indices. Let I∞ be the set of pairs(p, q) such that |L(p, q)| = ∞ where |L(p, q)| represents the
cardinality of the set L(p, q). Obviously an execution of the
Algorithm 1 stops within a finite number of iterations if andonly if I∞ = ∅.
The first step to prove Theorem 1 is to show that thesequence {β (n) }∞n=1 is convergent.
Lemma 6: The sequence {β (n) }∞n=0 generated by Algorithm 1 converges to a point in F2 as n → ∞.
Proof: Since {W (β (n) )}∞n=0 is a decreasing sequencethat is bounded from below, it converges to some value as
n → ∞. It follows from (17) that√)2 2(W (β (n) ) − W (β (n+1) ) ≥ ∥β (n) − β (n+1) ∥ .
τ
By repeated application of the triangle inequality we get√)
2 2(
W (β (n) ) − W (β (n+k) ) ≥ ∥β (n) − β (n+k) ∥τwhich means {β (n) }∞n=0 is a Cauchy sequence. Since F2 isclosed, {β (n) }∞converges
to some point in F2 .
n=0

7

The limit point of the sequence {β (n) }∞n=0 will be denotedby β̄ in the following.
Lemma 7: Let (p, q) be any pair belonging to I∞ . There(n+1)
exists an n0 such that βpq
belongs to ∪4k=1 ∂Sk for alln ∈ L(p, q) ≥ n0 .
Proof: We will only show in the following that
(n+1)
βpq
∈ intS2

(22)

(n+1)

∪4k=1 ∂Sk and βi(n) j (n) ∈ ∪4k=1 ∂Sk for all n ≥ n0 .
Proof: It is easily seen from Lemma 7 and the definition
of I∞ that there exists an n1 such that (i(n) , j (n) ) ∈ I∞ and(n+1)
βi(n) j (n) ∈ ∪4k=1 ∂Sk hold for all n ≥ n1 . Therefore for each(n)does not hold infinitely many times. The proofs for the regions
S1 , S3 and S4 are omitted because they are similar to the one
given here. Assume that (22) holds for infinitely many n’s inL(p, q). Then, at least one of the following two cases occurs
infinitely many times.
(n)
(n+1)
1) βpq ∈ S2 and βpq∈ intS2(n)(n+1)2) βpq ∈ S1 ∪ S3 ∪ S4 and βpq∈ intS2
We first consider Case 1). Let M1 (p, q) ⊆ L(p, q) be the set
(n)
(n+1)
of integers n such that βpq ∈ S2 and βpq∈ intS2 . Since(n)(p, q) is a τ -violating pair at β
for all n ∈ M1 (p, q),(n)(n)
Dp− W (β (n) ) − Dp+ W (β (n) ) = h−
) − h+
)>τ
p (β
q (β

holds for all n ∈ M1 (p, q). By taking the limit, we have+h−p (β̄) − hq (β̄) ≥ τ .

(n)open set, there exists an n1 such that βpq ∈ intS1 , ∀n ≥ n1 .
However, this contradicts Lemma 7.
(n)Lemma 9: There exists an n0 such that βi(n) j (n) ∈n ≥ n1 there are two possibilities: i) βi(n) j (n) ∈ ∪4k=1 ∂Sk(n)and ii) βi(n) j (n) ∈ ∪4k=1 intSk . Let B (n) denote the number(n)of components of β (n) satisfying βi ∈ {−C, 0, C}. In Casei) B (n+1) is equal to B (n) or greater than B (n) by one. On
the other hand, in Case ii) B (n+1) is greater than B (n) byat least one. Therefore Case ii) cannot occur infinitely manytimes after n reaches n1 because otherwise B (n) goes toinfinity, which of course contradicts the fact that the numberof components of β (n) is finite.
From the above discussions we see that for any pair (p, q) ∈I∞ one of the following situations occurs.
(n)
(n+1)
a) βpq ∈ E1 and βpq∈ E2 hold for infinitely manyn’s in L(p, q). In this case, β̄pq = V2 = (C, C) and thefollowing inequality holds.

(23)

(n+1)
∈ intS2 for all n ∈ M1 (p, q),
On the other hand, since βpq+h+p (β̄) ≥ hq (β̄) + τ
(n)

(25)

(n+1)

∈ E9 hold for infinitely manyb) βpq ∈ E12 and βpq
n’s in L(p, q). In this case, β̄pq = O = (0, 0) and the
(n+1)
(n+1)
inequality (25) holds.
Dp− W (β (n+1) )−Dp+ W (β (n+1) ) = h−
)−h+
)=0
p (β
q (β
(n+1)
(n)
∈ E3 hold for infinitely manyc) βpq ∈ E9 and βpq
holds for all n ∈ M1 (p, q). Thus we haven’s in L(p, q). In this case, β̄pq = V3 = (0, C) and thefollowing inequality holds.
h− (β̄) − h+ (β̄) = 0
it follows from Part 2) of Lemma 5 thatpqwhich contradicts (23). We next consider Case 2). In this case,β̄pq belongs to ∂S2 ∩ (∂S1 ∪ ∂S3 ∪ ∂S4 ) = {V3 } ∪ E9 ∪ {O} ∪E10 ∪ {V5 }. Let M2 (p, q) ⊆ L(p, q) be the set of integers n
(n+1)
(n)
∈ intS2 . Sincesuch that βpq ∈ S1 ∪ S3 ∪ S4 and βpq(n+1)∈ intS2 for all n ∈ M2 (p, q),
βpq

+
h−
p (β̄) ≥ hq (β̄) + τ
(n)

(n+1)

(26)

∈ E4 hold for infinitely manyd) βpq ∈ E10 and βpq
n’s in L(p, q). In this case, β̄pq = V5 = (−C, 0) and theinequality (26) holds.
(n+1)
(n)
∈ E10 hold for infinitely manye) βpq ∈ E11 and βpq
−
(n+1)
+
(n+1)
−
(n+1)
+
(n+1)
n’s
in
L(p,
q).
In
this
case,
β̄pq = O = (0, 0) and theDp W (β)−Dp W (β) = hp (β)−hq (β)=0following inequality holds.
holds for infinitely many n’s. By taking the limit, we have
−
h−
(27)
p (β̄) ≥ hq (β̄) + τ−+
hp (β̄) − hq (β̄) = 0
(24)
(n+1)
(n)
f) βpq ∈ E6 and βpq∈ E5 hold for infinitely many
Let θn be the positive number satisfying
n’s in L(p, q). In this case, β̄pq = V6 = (−C, −C) and
(n)
(n+1)
the inequality (27) holds.
(1 − θn )βpq
+ θn βpq
∈ ∂S2
(n)
(n+1)
g) βpq ∈ E8 and βpq∈ E12 hold for infinitely manyand let us define γ (n) as
n’s in L(p, q). In this case, β̄pq = V1 = (C, 0) and thefollowing inequality holds.
γ (n) = (1 − θn )β (n) + θn β (n+1)
−
h+
(28)
(n)
p (β̄) ≥ hq (β̄) + τ
Since γpq ∈ ∂S2 ∩ (∂S1 ∪ ∂S3 ∪ ∂S4 ) converges to β̄pq , we
(n)
(n+1)
see from (24) that there exists an n1 such thath) βpq ∈ E7 and βpq∈ E11 hold for infinitely many
n’s
in
L(p,
q).
In
this
case,
β̄pq = V7 = (0, −C) and
−
(n)
+
(n)
hp (γ ) − hq (γ ) ≤ τ, ∀n ∈ M2 (p, q) ≥ n1 .
the inequality (28) holds.
(n+1)
(n)
(n+1)
This equation together with the fact that βpq∈ intS2The eight possible movements from βpq to βpq
forcontradicts Step 4 of Algorithm 3.
sufficiently large n ∈ L(p, q) are shown in Fig.4.
Lemma 8: If (p, q) ∈ I∞ then β̄pq belongs to ∪4k=1 ∂Sk .
We are now ready for giving the proof of Theorem 1.
Proof: We prove the thesis by contradiction. Assume
Proof of Theorem 1: Suppose that Algorithm 1 does notwithout loss of generality that β̄pq ∈ intS1 . Since intS1 is an stop. Then I∞ has at least one pair. Let (p, q) be any pair in

8

βj
E3

V4

βq

V3

E2

c)

a)
E9

S2

E4

β̄pq = V2

V2
E1

S1

O

d)

V5

b)

E10

e) O
E5

(a)

βi

g)

E11 S4

S3

βp

V1

E12

βp

E8

βp

β̄p1 p = V2

β̄p1 p = V3

f)
V6

h)
E6

V7

E7

V8

O

O
βp1

βp1
Fig. 4.

(n)

(n+1)

Eight possible movements from βpq to βpq

.

(b)

(n)

I∞ . In case a) described above, since βpq moves from E1
to E2 infinitely many times, it must return from E2 to E1
infinitely many times. In order for this to occur, there must(n)exist an index p1 such that βp1 p moves either i) from E1 to
E2 or ii) from E9 to E3 infinitely many times, and an index(n)q1 such that βqq1 moves either i) from E1 to E2 or ii) from
E8 to E12 infinitely many times (see Fig.5). Therefore (p1 , p)belongs to I∞ and one of the following conditions holds:+
β̄p1 p = (C, C), h+p1 (β̄) ≥ hp (β̄) + τ(29)+
β̄p1 p = (0, C), h−p1 (β̄) ≥ hp (β̄) + τ(30)

Similarly (q, q1 ) belongs to I∞ and one of the following
conditions holds:

βq1

βq1

β̄qq1 = V2

β̄qq1 = V1
βq

O

O
βq
(c)
(n)

(n)

(n)

Fig. 5. Possible movements of (a) βpq , (b) βp1 p and (c) βqq1 for sufficiently
large n.

for (p, q) ∈ I∞ . Then, by applying the relationship shownin Table I repeatedly, we see that there must exist an infinite
sequence of indices p0 (= p), p1 , p2 , . . . such that+β̄qq1 = (C, C), h+q (β̄) ≥ hq1 (β̄) + τ(31)−
β̄qq1 = (C, 0), h+q (β̄) ≥ hq1 (β̄) + τ(32)(pi+1 , pi ) ∈ I∞ ,i = 0, 1, 2, . . .

(33)

We easily see from (29)–(32) that p, q, p1 and q1 are different
from each other. For example, in the case where β̄p1 p = (C, C)
and β̄qq1 = (C, C), we have from (25), (29) and (31)β̄pi ∈ {0, C},i = 0, 1, 2, . . .

(34)

+
+
+
h+
q1 (β̄) < hq (β̄) < hp (β̄) < hp1 (β̄)

Thus p, q, p1 and q1 are different from each other. In the casewhere β̄p1 p = (0, C) and β̄qq1 = (C, 0), it is obvious thatp1 ̸= p, q and q1 ̸= p, q. Moreover, since++−h−q1 (β̄) < hq (β̄) < hp (β̄) < hp1 (β̄)

holds from (25), (30) and (32), we can conclude that p1 ̸= q1 .
In each case b) to h), there must be two indices p1 andq1 such that (p1 , p) ∈ I∞ , (q, q1 ) ∈ I∞ , and p, q, p1 andq1 are different from each other, as we have seen in case a).
Relationship between (p, q) and (p1 , p) for cases a) – h) issummarized in Table I, and relationship between (p, q) and(q, q1 ) for cases a) – h) is summarized in Table II.
In the following, we will show from Table I that I∞ must
contain infinitely many pairs. We will not consider Table II,
but the same discussion can be made by using Table II. Let
us first suppose that one of the cases a), c), e) and g) occurs

hsp00 (β̄) < hsp11 (β̄) < hsp22 (β̄) < · · ·(35)

where si represents “+” if β̄pi = C and “−” if β̄pi = 0.
Eq.(35) implies that all indices p, p1 , p2 , . . . are different fromeach other. Therefore, I∞ must contain infinitely many pairs.
Let us next suppose that one of the cases b), d), f) and h) occursfor (p, q) ∈ I∞ . Then there must exist an infinite sequence ofindices p0 (= p), p1 , p2 , . . . such that(pi+1 , pi ) ∈ I∞ ,i = 0, 1, 2, . . .

(36)

β̄pi ∈ {0, −C},i = 0, 1, 2, . . .

(37)

hsp00 (β̄) < hsp11 (β̄) < hsp22 (β̄) < · · ·(38)where si represents “+” if β̄pi = 0 and “−” if β̄pi = −C.
Eq.(38) implies that all indices p, p1 , p2 , . . . are different eachother. Therefore, I∞ must contain infinitely many pairs.
Since these results apparently contradict the fact that the
number of different pairs contained in I∞ is finite, we canconclude that I∞ is empty, that is, Algorithm 1 always stops
within a finite number of iterations.

9

TABLE IR ELATION BETWEEN (p, q) AND (p1 , p).
β̄pqa) (C, C)b) (0, 0)c) (0, C)d) (−C, 0)e) (0, 0)f) (−C, −C)g) (C, 0)h) (0, −C)β̄p1 p±h±p (β̄), hp1 (β̄)a) (C, C)+h+p (β̄) < hp1 (β̄)c) (0, C)b) (0, 0)d) (−C, 0)e) (0, 0)g) (C, 0)f) (−C, −C)h) (0, −C)e) (0, 0)g) (C, 0)f) (−C, −C)h) (0, −C)a) (C, C)c) (0, C)b) (0, 0)d) (−C, 0)−h+p (β̄) < hp1 (β̄)+
h+p (β̄) < hp1 (β̄)+
hp (β̄) < h−p1 (β̄)
−
h−
(
β̄)
<
h
p
p1 (β̄)−hp (β̄) < h+p1 (β̄)−h−p (β̄) < hp1 (β̄)−
hp (β̄) < h+p1 (β̄)
−
h−
(
β̄)
<
h
p
p1 (β̄)−hp (β̄) < h+p1 (β̄)−hp (β̄) < h−p1 (β̄)+h−p (β̄) < hp1 (β̄)++
hp (β̄) < hp1 (β̄)−
h+p (β̄) < hp1 (β̄)+
hp (β̄) < h+p1 (β̄)
−
h+
(
β̄)
<
h
p
p1 (β̄)TABLE IIR ELATION BETWEEN (p, q) AND (q, q1 ).
β̄pqa) (C, C)b) (0, 0)c) (0, C)d) (−C, 0)e) (0, 0)f) (−C, −C)g) (C, 0)h) (0, −C)

β̄qq1

±
h±
q (β̄), hq1 (β̄)a) (C, C)+h+q1 (β̄) < hq (β̄)g) (C, 0)+h−q1 (β̄) < hq (β̄)b) (0, 0)+h+q1 (β̄) < hq (β̄)h) (0, −C)+h−q1 (β̄) < hq (β̄)a) (C, C)+h+q1 (β̄) < hq (β̄)g) (C, 0)+h−q1 (β̄) < hq (β̄)b) (0, 0)+h+q1 (β̄) < hq (β̄)h) (0, −C)+h−q1 (β̄) < hq (β̄)c) (0, C)−h+q1 (β̄) < hq (β̄)e) (0, 0)−h−q1 (β̄) < hq (β̄)d) (−C, 0)−h+q1 (β̄) < hq (β̄)f) (−C, −C)−h−q1 (β̄) < hq (β̄)c) (0, C)−h+q1 (β̄) < hq (β̄)e) (0, 0)−h−q1 (β̄) < hq (β̄)d) (−C, 0)−h+q1 (β̄) < hq (β̄)f) (−C, −C)−h−q1 (β̄) < hq (β̄)

VI. I MPLEMENTATION AND E XPERIMENTS
A. Implementation of SMO Algorithm
The authors have recently studied in detail how to implement the SMO algorithm discussed in the previous section[21]. In the following, we will briefly review their results.
Convergence rate of the SMO algorithm strongly depends
on how to choose a violating pair in each iteration. The method
used in [21] is to choose i(n) and j (n) so that the following

two conditions are satisfied.
i(n) ∈ {i : Di− W (β (n) ) ≥ Dk− W (β (n) ), ∀k}(39)∈ {j : Dj+ W (β (n) ) ≤ Dk+ W (β (n) ), ∀k}

(40)

j

(n)

Since ϕ′− (t) is expressed as (14), the objective function W (β)
is expected to decrease most rapidly when i(n) and j (n) satisfy(39) and (40), respectively. In this sense, this method is basedon the steepest descent. It is apparent that any pair (i(n) , j (n) )satisfying (39) and (40) is a τ -violating pair because there
exists at least one τ -violating pair (i, j) at β (n) , which satisfies
Di− W (β (n) ) > Dj+ W (β (n) ) + τ , as far as β (n) does notsatisfy the τ -optimality condition.
The method expressed by (39) and (40) is identical to theone proposed by Shevada et al. [19]. On the other hand, Smolaand Schölkopf [18] and Flake and Lawrence [20] used methods
based on Platt’s SMO algorithm [3].
How to implement Algorithm 3 is another important problem. Of course we can encode the algorithm exactly same as
described in Section IV, but by using the technique introducedby Flake and Lawrence [20] we can obtain a code which ismore compact and faster.
The pseudo-code given in [21] is shown in Fig.6 wheresgn(u) takes 1 if u ≥ 0 and −1 otherwise, and step(u) takes
1 if u ≥ 0 and 0 otherwise. The first part (lines 4–20) is a
generalization of the code given in [20]. On the other hand,the second part (lines 21–39) was newly added by the authors,
because the case where η = 0 was not considered in [20].
It is important to note that the pseudo-code shown in Fig.6
is equivalent to Algorithm 3 only if τ < ϵ. However, since thevalue of τ is usually set to a sufficiently small positive number
comparing with ϵ (see [19] for example), this assumption will
not be violated in practice.
B. Experiments
In order to examine the efficiency of the authors’ SMO
algorithm [21], we compare the following six algorithms interms of CPU time and the number of iterations for several
benchmark data sets.
1) The algorithm used in LIBSVM version 2.71 or earlier[16], [17]. Two variables which most violate the KKT
condition for Problem 1 are selected from 2l variables.
The relationship between αi and α̂i is not considered
explicitly. Subproblems are solved exactly.
2) Smola and Schölkopf’s SMO algorithm [18]. Two pairsof variables αi , α̂i , αj and α̂j are selected according to
the strategy similar to Platt’s SMO algorithm. Subproblems are solved exactly.
3) Shevada et al.’s SMO algorithm [19]. Two pairs ofvariables αi , α̂i , αj and α̂j which most violate the KKT
condition for Problem 1 are selected. Subproblems are
solved exactly.
4) Flake and Lawrence’s SMO algorithm [20]. Two variables βi and βj are selected according to the strategy similar to Platt’s SMO algorithm. Subproblems are
solved exactly.
5) The authors’ SMO algorithm [21].

10

1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.

Fig. 6.

s := β̄i + β̄j ;η := kii + kjj − 2kij ;PlPlv := −yi + n=1 kin β̄n + yj − n=1 kjn β̄n ;if (η > 0) {βi := β̄i + (τ − v)/η;βj := s − βi ;if (βi · βj > 0) {m := βi · step(βi ) − βj · (1 − step(βi ));∆ := τ /η;βi := βi − min{m, ∆};elseif (βi · βj < 0) {∆ := (2ǫ + τ · sgn(βi ))/η;
βi := βi − min{|βi |, |βj |, ∆} · sgn(βi );}if (s ≥ 0 and βi < s − C)βi := s − C;elseif (s < 0 and βi < −C)
βi := −C;βj := s − βi ;}
else {if (β̄i ≤ 0 and β̄j ≥ 0)βi := s · step(s) − C;elseif ((β̄i > 0 and β̄j ≥ 0) or (β̄i ≤ 0 and β̄j < 0)) {if (|s| ≥ C or v > τ + 2ǫ)
βi := s · step(s) − C;else
βi := s · (1 − step(s));}
else {
if (v > τ + 2ǫ)
βi := s · step(s) − C;elseif (v > τ )βi := s · (1 − step(s));
else
βi := s · step(s);}βj := s − βi ;}Pseudo code of Algorithm 36) The same algorithm as 5) except that subproblems are
solved exactly by Algorithm 2 which is encoded in asimilar way as the pseudo code shown in Fig.6.
Although some new variable selection methods have recently been proposed for pattern classification problems [22]–[24], we do not consider these methods in our experiments
because it is not clear whether they can be applied to Problem 2 directly. However, it is of course important to verify
the applicability of these methods to Problem 2. This will be
another research topic for future.
All the above algorithms were implemented in MATLAB
and run on a PC with Intel Xeon dual processor 2.8GHz and
2GB of RAM. As the kernel function, we used the RBF kernel
defined by K(x, y) = exp(−∥x − y∥2 /(2σ 2 )). Benchmark
data sets are from UCI Machine Learning Repository [25],StatLib [26] and [20], and listed in Table III1 where the
1 All data sets in Table III are also available at [16].

dimension of the input patterns (d), the total number ofsamples (ltotal ), the number of samples used for training (l),and the values of parameters ε, τ , C and σ are specified.
The values of xi and yi in training samples are normalized
before training so that xi ∈ [−1, 1]d and yi ∈ [−1, 1] hold for
all i. The values of hyperparameters ε, τ and C are fixed to
0.1, 0.01 and 10, respectively, for all data sets. On the other
hand, the value of the kernel parameter σ was selected from{0.01, 0.05, 0.1, 0.5} so that the error rate for test samples isminimized.
TABLE III
BASIC INFORMATION ON BENCHMARK DATA SETS AND PARAMETERSETTINGData
abalonebodyfathousing
mg
mpg
pyrim
space-ga
trizaines

d
8
14
13
6
7
27
6
60

ltotal
4177
252
506
1385
392
74
3107
186

l
1000
100
200
600
200
50
1000
100

ε
0.1
0.1
0.1
0.1
0.1
0.1
0.1
0.1

τ
0.01
0.01
0.01
0.01
0.01
0.01
0.01
0.01

C
10
10
10
10
10
10
10
10

σ
0.5
0.1
0.1
0.5
0.5
0.01
0.1
0.05

For each benchmark data sets, we generate ten sets of ltraining samples which are randomly selected from the wholetraining samples, and apply the six different algorithms tothose ten sets of training samples. Experimental results are
summarized in Table IV where the number of iterations, CPUtime and the number of jumps are presented. Each value isobtained by averaging the results for ten sets. The number ofjumps represents how many transitions between regions S1 ,S2 , S3 and S4 in Fig.1 occurred in solving QP subproblems.
Although global convergence is theoretically guaranteed only
for Methods 1 and 5, τ -optimal solutions were always reachedin our experiments.
We first compare the six methods simply in terms of CPU
time. It is seen from Table IV that Method 1, the algorithm
used in LIBSVM version 2.71 or earlier, is the fastest forsix benchmark data sets. Methods 3, 5 and 6 are slower than
Method 1 but the difference is not so significant. Methods 2
and 4 are the slowest. In particular, for mg, they are about fourtime slower than others. In order to explain these results, we
focus our attention on the number of jumps. Table IV showsthat those methods which select variables most violating the
optimality condition (Methods 3, 5 and 6) require a muchsmaller number of jumps than those methods which selectvariables in a way similar to Platt’s SMO algorithms (Methods
2 and 4). Since all variables are set to zero initially, thismeans that the former group of methods select variables more
appropriately than the latter one. Table IV also shows thatthe number of jumps is zero or extremely small comparedto the number of iterations for Methods 3, 5 and 6. Theseexperimental results strongly support a conclusion from [17,Theorem 2] which says that no jump occurs at the final stage.
It is obvious that the advantage of updating two variables βi
and βj in Methods 5 and 6 (or two pairs of variables αi , α̂i , αjand α̂j in Methods 2, 3 and 4) becomes small as the numberof jumps decreases. In particular, if no jump occurs, these11

TABLE IV
E XPERIMENTAL R ESULTS
Data
abalonebodyfathousing

mg

mpg

pyrim

space-ga

trizaines

Method
1
2
3
4
5
6
1
2
3
4
5
6
1
2
3
4
5
6
1
2
3
4
5
6
1
2
3
4
5
6
1
2
3
4
5
6
1
2
3
4
5
6
1
2
3
4
5
6

Iteration
27566.034146.227480.634088.827219.727480.6
66.1
402.8
66.1
411.9
66.1
66.1
140.8
935.2
140.8
906.9
140.8
140.8
18779.548012.3
18649.848758.4
18741.1
18649.8
1541.54876.81544.74962.71555.01544.7
64.5
181.9
64.5
186.7
64.5
64.5
265.8
1364.5265.8
1327.8
265.8
265.8
219.6
644.8
219.6
684.8
219.6
219.6

CPU Time (sec)29.114238.9869
29.0673
38.3673
29.0467
29.10210.34650.5306
0.3491
0.53180.34880.34931.22892.0986
1.24922.0513
1.23641.238016.5560
38.2765
16.5473
38.3542
16.5728
16.5095
1.11454.0746
1.1583
4.15381.1685
1.1567
0.09720.14530.10460.14840.10120.1037
6.12679.13246.13589.06386.13386.13250.36210.8346
0.36870.86650.36490.3652

Jumps
119.3
28.8
117.7
28.7
28.8
37.6
0
38.4
0
0
131.2
0
125.6
0
0
518.9
29.2
532.1
29.3
29.2
401.8
5.3
410.3
5.4
5.3
14.9
0
15.0
0
0
263.7
0
257.1
0
0
20.1
0
21.6
0
0

methods will be slower than Method 1 because the procedure
for solving QP subproblems is unnecessarily complicated. Thisis a possible reason why Method 1 is faster than Methods 3,
5 and 6.
We next evaluate the effectiveness of the pseudo code of
Algorithm 3 shown in Fig. 6. This evaluation can be doneby comparing Methods 3 and 6 because these two methods
differ only in the procedure for finding exact solutions of QP
subproblems. It is seen from Table IV that Method 6 is fasterthan Method 3 for most data sets but the difference is verysmall. Therefore the implementation technique shown in Fig. 6
did not have the intended effect for the benchmark data sets
used in our experiments.
We finally consider the influence of using Algorithm 3 forsolving QP subproblems instead of Algorithm 2 on the performance of the SMO algorithm by comparing Methods 5 and 6.

It is seen from Table IV that there is no significant difference
between these two methods. This is because the behavior of
Algorithms 2 and 3 differ only when the jump occurs and thenumber of jumps is very small for all benchmark data sets.
VII. C ONCLUSION
We have proved that if a τ -violating pair is chosen for
update in each step and subproblems are solved by Algorithm 3 then the SMO algorithm stops within a finite number of
iterations after finding a τ -optimal solution. On the other hand,
however, it is still not clear whether or not the SMO algorithm
converges to a τ -optimal solution when subproblems are
solved exactly. This may be a future problem to be attacked.
Another future problem is to study global convergence of moregeneral decomposition algorithms for SVR where more than
two variables are updated in each step. This issue is alsomentioned in [8].
R EFERENCES[1] V. Vapnik, Statistical Learning Theory. New York: Wiley, 1998.
[2] E. Osuna, R. Freund, and F. Girosi, “An improved training algorithm forsupport vector machines,” in Proceedings of the 1997 IEEE Workshop
on Neural Networks for Signal Processing, 1997, pp. 511–519.
[3] 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.
[4] 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.
[5] 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.
[6] C.-W. Hsu and C.-J. Lin, “A simple decomposition method for support
vector machines,” Machine Learning, vol. 46, pp. 291–314, 2002.
[7] 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.
[8] 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.
[9] ——, “A formal analysis of stopping criteria of decomposition methods
for support vector machines,” IEEE Trans. Neural Networks, vol. 13,
pp. 1045–1052, Sept. 2002.
[10] 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.
[11] N. Takahashi and T. Nishi, “Global convergence of decomposition
learning methods for support vector machines,” IEEE Trans. Neural
Networks, vol. 17, no. 6, pp. 1362–1369, Nov. 2006.
[12] C.-J. Lin, “Asymptotic convergence of an SMO algorithm without any
assumption,” IEEE Trans. Neural Networks, vol. 13, pp. 248–250, Jan.
2002.
[13] 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.
[14] 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.
[15] P.-H. Chen, R.-E. Fan, and C.-J. Lin, “A study on SMO-type decomposition methods for support vector machines,” IEEE Trans. Neural
Networks, vol. 17, no. 4, pp. 893–908, July 2006.
[16] C.-C. Chang and C.-J. Lin, “LIBSVM: a library for support vector
machines,” 2001. [Online]. Available: http://www.csie.ntu.edu.tw/∼cjlin/
libsvm/[17] S.-P. Liao, H.-T. Lin, and C.-J. Lin, “A note on the decomposition
methods for support vector regression,” Neural Computation, vol. 14,
pp. 1267–1281, 2002.

12[18] A. J. Smola and B. Schölkopf, “A tutorial on support vector regression,”
Royal Holloway College, London, UK, NeuroCOLT Technical Report
NC-TR-98-030, 1998.
[19] S. K. Shevade, S. S. Keerthi, C. Bhattacharyya, and K. R. K. Murthy,“Improvements to the SMO algorithm for SVM regression,” IEEE Trans.
Neural Networks, vol. 11, no. 5, pp. 1188–1193, Sept. 2000.
[20] G. W. Flake and S. Lawrence, “Efficient SVM regression training with
SMO,” Machine Learning, vol. 46, pp. 271–290, 2002.
[21] J. Guo, N. Takahashi, and T. Nishi, “A novel sequential minimal optimization algorithm for support vector regression,” in Neural Information
Processing (Proceedings of the 13th International Conference on Neural
Information Processing), ser. Lecture Notes in Computer Science, vol.
4232, Oct. 2006, pp. 827–836.
[22] R.-E. Fan, P.-H. Chen, and C.-J. Lin, “Working set selection using
second order information for training support vector machines,” Journalof Machine Learning Research, vol. 6, pp. 1889–1918, 2005.
[23] D. Hush, P. Kelly, C. Scovel, and I. Steinwart, “QP algorithms withguaranteed accuracy and run time for support vector machines,” Journalof Machine Learning Research, vol. 7, pp. 733–769, 2006.
[24] T. Glasmachers and C. Igel, “Maximum-gain working set selection for
SVMs,” Journal of Machine Learning Research, vol. 7, pp. 1437–1466,
2006.
[25] A. Asuncion and D. Newman, “UCI machine learning repository,” 2007.
[Online]. Available: http://www.ics.uci.edu/∼mlearn/MLRepository.html[26] “StatLib – datasets archive.” [Online]. Available: http://lib.stat.cmu.edu/
datasets/