Polynomial-Time Decomposition Algorithms for Support Vector Machines.
This paper studies the convergence properties of a general class of decomposition algorithms for support vector machines (SVMs). We provide a model algorithm for decomposition, and prove necessary and sufficient conditions for stepwise improvement of this algorithm. We introduce a simple rate certifying condition and prove a polynomial-time bound on the rate of convergence of the model algorithm when it satisfies this condition. Although it is not clear that existing SVM algorithms satisfy this condition, we provide a version of the model algorithm that does. For this algorithm we show that when the slack multiplier C satisfies \sqrt{1/2}  C  mL, where m is the number of samples and L is a matrix norm, then it takes no more than 4LC2m4/&epsi; iterations to drive the criterion to within &epsi; of its optimum.
Introduction
The soft margin formulation in (Cortes & Vapnik, 1995) has the advantage that it provides a
design criterion for support vector machines (SVMs) for both separable and nonseparable data
while maintaining a convex programming problem. To maintain a computationally feasible
approach across all kernels, algorithms are developed for the Wolfe Dual Quadratic Program
(QP) problem whose size is independent of the dimension of the ambient space. The Gram
matrix for the Wolfe Dual is is the number of data samples. For large m
the storage requirements for this matrix can be excessive, thereby preventing the application
of many existing QP solvers. This barrier can be overcome by decomposing the original QP
problem into smaller QP problems and employing algorithmic strategies that solve a sequence
of these smaller QP problems. For the class of algorithms considered here these smaller QP
problems are restrictions of the original QP problem where optimization is allowed over a
subset of the data called the working set. The key is to select working sets that guarantee
progress toward the original problem solution at each step. Such algorithms are commonly
referred to as decomposition algorithms, and many existing SVM algorithms fall into this
class (Cristianini & Shawe-Taylor, 2000; Joachims, 1998; Keerthi, Shevade, Bhattacharyya,
1998). In this paper
we provide a model algorithm for decomposition and prove necessary and su-cient conditions
for stepwise improvement of this algorithm. These conditions require that each working set
contain a certifying pair (dened in section 3). Computation of a certifying pair takes O(m)
time. We dene a simple \rate certifying" condition on certifying pairs that enables the proof
of a polynomial-time bound on the rate of convergence. It is not clear that the working sets
chosen by existing SVM algorithms contain certifying pairs that satisfy this condition. On the
other hand, we provide an O(m log m) algorithm for determining a certifying pair that does.
The next section sets the stage for our development by providing a formal denition of the
problem and establishing some of its basic properties.
Preliminaries
be a nite set of observations from a two-class pattern recognition
problem where x 1g. The Support Vector Machine (SVM) maps the
space of covariates X to a Hilbert space H of higher dimension (possible innite), and ts an
optimal linear classier in H. It does so by choosing a map  in such a way that
known and easy to evaluate function K. Su-cient conditions for
the existence of such a map are provided by Mercer's theorem (Vapnik, 1998). Let z
so that
A linear classier in H is given by
LANL Technical Report: LA{UR{00-3800 2 Preliminaries
In the soft margin formulation of (Cortes & Vapnik, 1995) the optimal is given by
optimizes the Wolfe Dual quadratic programming problem,
s.t.
where
The choice of the unspecied parameter C > 0 has been investigated but we do not address
that here. Once  has been determined the optimal value of b is given by
~ v()
low  b  ~ v()
high
where ~ v()
low and ~ v()
high are dened in section 3. This paper is concerned with the analysis
of a class of algorithms for WD(S) that are motivated by situations where m is so large that
direct storage of Q is prohibitive.
Let WD(S) denote an instance of the Wolfe Dual dened by the sample set S. Let (S)
represent the set of feasible solutions for WD(S),
Note that (S) is both convex and compact. Denote the Wolfe Dual criterion by
and let   (S) represent the set of optimal solutions for WD(S),
R()g:
verifying that Q is symmetric and
positive semi-denite. Thus, R() is a concave function over (S) and R
unique. The Lagrangian for WD(S) takes the form
LANL Technical Report: LA{UR{00-3800 3 Optimality using Certifying Pairs
Then the Karush-Kuhn-Tucker (KKT) conditions (e.g. see (Avriel, 1976), p.96) for WD(S)
take the form
where we have made use of the relation
There are three regimes for  i ; two where it equals a bound, and one where it falls between
the bounds. Combining the conditions above with these three regimes we obtain a simpler set
of conditions that are equivalent to the KKT conditions
It is possible to use the satisfaction of these equations as a stopping condition for optimization
algorithms, but they involve . An alternative set of optimality conditions were introduced
in (Keerthi et al., 2001; Keerthi & Gilbert, 2000) that do not use . In the next section we
present these conditions and use them to develop a simple optimality test.
3 Tests for Optimality using Certifying Pairs
We dene a partition of the index set of S based upon the data
I low
I
I
and
low g
and let
i2I low
i2I high
where the sup and inf of the empty set are dened as 1 and 1 respectively.
LANL Technical Report: LA{UR{00-3800 3 Optimality using Certifying Pairs
Denition 1.  is properly ordered for S if jV int
low  v
high
or jV int
low  V int  v
We now prove a result rst stated by Keerthi and Gilbert (Keerthi & Gilbert, 2000).
Theorem 1. (Keerthi and Gilbert)
A feasible  for the Wolfe dual problem WD(S) is optimal if and only if  is properly
ordered for S.
Proof. The optimality conditions (7) can be rewritten as
low
Now suppose that  is optimal. Then equations (12) imply that
low
low
The rst equation implies that jV int and the second equation implies that v
low  v
high .
When jV int the second and third equations imply that
low  V int  v
high
and so  is properly ordered. On the other hand, suppose  is properly ordered. Then jV int
By the denitions of v
low and v
high it is clear that
low
low
and we can choose  to be any point in [v
low
high
so that the conditions (12) are satised. Consequently,  is optimal if and only if it
is properly ordered for S.
Tests for proper ordering can be simplied if we dene
~
I low = I low [ I int
~
I high = I high [ I int
and
i2 ~ I low
I high
Then  is properly ordered for WD(S) if and only if
low  ~ v
The proof of this statement follows directly from the proof of Theorem 1.
Lack of optimality can be determined by the existence of a certifying pair.
Denition 2. A certifying pair for  2 (S) is a pair of indices i and j in the index set of S
whose values (v are su-cient to prove that  is not properly ordered for
S.
We note that Keerthi et. al. (Keerthi & Gilbert, 2000) refer to this as a violating pair.
However, because we later dene rate certifying pair we decided not to adopt this terminology.
Theorem 2.  is not properly ordered for S if and only if there exists a certifying pair. A
certifying pair can be obtained by making at most one pass through the data while making two
comparisons.
Proof. Suppose that  is not properly ordered for S. Then there exists indices i 2 ~
I high and
I low such that v i < v j . Choose any such pair. To determine a certifying pair make one pass
through the data while keeping track of indices that represent
high and ~ v
low . Stop at the rst
point where ~
high < ~ v
low .
4 A General Decomposition Algorithm
Algorithmic solutions for the Wolfe dual must consider the fact that when m is large the storage
requirements for Q can be excessive. This barrier can be overcome by decomposing the original
QP problem into smaller QP problems.
Suppose we partition the index set of  into a working set W and a non-working set W c .
Note that W indexes a subset of the data. Then are
partitioned accordingly and Q is partitioned as follows
QW c W QW c
W c W . Then (3) can be written
xed this becomes a QP problem of size dim(W ) with the same generic properties
as the original. This motivates algorithmic strategies that solve a sequence of QP problems
over dierent working sets. The key is to select a working set at each step that will guarantee
progress toward the original problem solution.
Theorem 3. Consider the subset constrained Wolfe dual problem dened as follows. Consider
a feasible . Dene a subset W of the index space of S with complement W c . Optimize the
Wolfe dual criterion with respect to   subject to the constraint that   =  on W c . Let
denote a solution to this constrained problem. Then, R(  ) > R(), if and only if W contains
a certifying pair for .
Proof. Since R is concave,  is non-optimal for WD(S) if and only if there is a feasible innitesimal
_
at  such that
> 0: (16)
Further, the solution to the constrained Wolfe dual produces an increase in R if and only if there
is a feasible constrained _
(with nontrivial components on W only) such that dR()  _
Consequently, to prove the theorem it is su-cient to show that a feasible _
W exists that satises
if and only if W contains a certifying pair.
The derivative of R is given by
_
. The feasible directions _
satisfy _
when In terms of d these conditions become d  high , and
low . Decompose
components under the subsets dened by I high , I low , and I int . Then (16) can be written
d high  v high low  v low
and the feasibility constraints are
d high  1 low low  0; d int free: (18)
Assume that W contains a certifying pair. Then it must satisfy one of the following inequalities,
low
low
In all four cases we can verify (17)-(18) by choosing d for the certifying pair and
so that
The proof of \if" is nished.
Now assume that there is a feasible _
W for which dR()  _
W > 0. Then (17)-(18) are
be the restrictions of V int (I int ) to the indices of W . If
jV int (W )j > 1 then any two components certifying
pair. If jV int (W
d high  v high low  v low
Combining with (18) gives
d high  (v high v  low  (v low v  1) < 0; d high  0; d low  0
For this inequality to hold at least one of the two terms must be negative. To make the rst
term negative at least one component of (v high v  1) must be negative. Similarly, to make
the second term negative at least one component of (v low v  1) must be positive. Either case
gives a certifying pair. Finally, if jV int (W
d high  v high low  v low < 0
d high  low  1; d high  0; d low  0
Without loss of generality let the components of d high and d low be normalized so that
i2I high
i2I low
Then (d high  v high low  v low ) is the dierence between convex combinations of V high (W ) and
convex combinations of V low (W ). For this dierence to be negative the two convex hulls must
overlap. This implies a certifying pair. This nishes the \only if" part, so the proof is nished.
Theorem 3 motivates a class of algorithms of the form Algorithm A 1 below. Members from
this class solve a sequence of decomposed QP problems of the form in (15) over working sets
that can vary in size from 2 to jSj and contain at least one certifying pair. The initialization
ensures that W (0) contains at least one certifying pair. The QPSolve routine on line 11 solves
the QP problem restricted to the current working set W (k 1). Line 14 chooses a certifying
pair for inclusion in the next working set. The algorithm terminates when a certifying pair no
longer exists. The AnySubset routine on line chooses a subset of samples to be included with
the certifying pair in the next working set. This subset is irrelevant to the issue of guaranteed
improvement, but is likely to have an eect on the rate of convergence.
e
Algorithm Decomposition Algorithm.
1:
2:
3:
4: OUTPUT:
5:
7:
8: ~
I low
9: ~
I
10: W (0) subset of I S with at least one sample from each class:
12: loop
13:
14: Update membership in ~
I low ; ~
I high for samples in W (k 1)
I low
I high ; and v i > v j
17: if
19: end if
22: end loop
Convergence
In general, the stepwise improvement of Algorithm A 1 is not su-cient to guarantee convergence.
Indeed, Keerthi and Ong (Keerthi & Ong, 2000) provide an example where each working set
contains a certifying pair but Algorithm A 1 does not converge to the optimal solution. However,
convergence results have been proved for some special cases, e.g. see (Keerthi & Gilbert, 2000),
(Chang, Hsu, & Lin, 2000), (Lin, 2000). The convergence result in (Keerthi & Gilbert, 2000)
denes   to be -optimal if it satises ~ v
low < ~
high It then shows that the
generalized SMO (GSMO) algorithm converges to a -optimal solution in a nite number of
steps. The GSMO algorithm is a special case of Algorithm A 1 where the AnySubset function
returns the empty set. The analysis in (Keerthi & Gilbert, 2000) leaves open the question of
accuracy with respect to the optimal solution, that is it provides no bound on jR(  ) R  j or
(Chang et al., 2000) give a proof of convergence for a special case of Algorithm A 1 where
the working set is dened to be the indices corresponding to the nontrivial components of d in
e
the solution to the optimization problem
s.t. d
where q  2. Their proof shows that, with this choice of working set, Algorithm A 1 produces
a sequence f(k)g whose limit point is optimal for WD(S). More recently (Lin, 2000) has
provided a similar proof of convergence for SV M light where the working set is dened by
Joachims (Joachims, 1998) to be the indices corresponding to the nontrivial components of d
in the solution to a slightly dierent optimization problem
s.t. d
where q  2.
The analysis in (Chang et al., 2000) and (Lin, 2000) is asymptotic and therefore leaves open
the question of nite step convergence to the optimum. In the following section we provide a
nite step convergence proof for a special case of Algorithm A 1 that corresponds to \chunking".
5.1 Finite Step Convergence for Chunking
Chunking (as described in (Cristianini & Shawe-Taylor, 2000)) is a decomposition method in
which each working set contains all support vectors from the current solution plus an additional
set of samples that violate an \optimality condition". If the optimality condition is chosen so
that the additional set always contains at least one certifying pair 1 then the resulting algorithm
takes the form of Algorithm A 1 where the AnySubset routine returns, at a minimum, the indices
for all samples with  i > 0. The following theorem holds for this class of chunking algorithms.
Theorem 4. Let S be a nite set of observations containing at least one sample from each
class. Consider Algorithm A 1 where the AnySubset routine returns any set that contains the
indices for all samples with  i > 0. This algorithm converges to a solution of WD(S) for nite
k.
Proof. Algorithm A 1 terminates only when there are no certifying pairs, and if it terminates
then  2   (S). We assume that QPSolve provides an exact solution to the constrained Wolfe
dual. Then Theorem 3 guarantees that when we are not at a solution the criterion for WD(S)
is strictly increased from one step to the next, i.e. R((k
all nontrivial contribution to R is made by the working set. Thus, no working set is revisited,
and since there are a nite number of working sets, and R  is unique, termination in nite k is
guaranteed.
This requires a slight modication to the chunking algorithm in (Cristianini & Shawe-Taylor, 2000).
e
We now show that with the proper choice of certifying pair we can provide polynomial-time
bounds on the run time of Algorithm A 1 .
5.2 Convergence Rate
In this section we give a nite step convergence result for Algorithm A 1 when each working
set contains a rate certifying pair (dened below). We also provide bounds on the convergence
rate. More specically we give a polynomial bound on the number of iterations required to
drive jR() R  j to within  of its optimum. Note that the criterion has a strong dependence
on the size of the sample set m. In general R becomes unbounded as m ! 1. Consequently
the development of convergence rates requires the normalization of R in terms of the number
of samples. For example, in empirical risk minimization it is standard to divide the number of
training errors by the number of samples to obtain the fraction of training errors. However at
present we know of no natural normalization for R. Therefore to allow for the incorporation
of an appropriate normalization we implicitly denote the error tolerance as a function of m
through the notation  m .
Let   be an optimal parameter value and R the optimal criterion value.
Because of concavity,
which can be rewritten as
If we dene
we obtain
Let
denote a parameter value which diers from  in at most two places and dene
When  ()  () for some 0 <  < 1 then we can bound the distance to the optimum by
()=. We use this to determine a bound on the convergence rate for Algorithm A 1 .
Let  k denote the value of the state at the k-th iteration and let
k denote a parameter that
diers from  k in at most two indices. We note that in previous sections the subscripted  k was
used for the k-th component of the vector  and the parenthetic (k) was used for the state of
the algorithm at the k-th iteration. However, in the present analysis we need no components
of the vector and feel the use of  k for the state at the k-th iteration is a better notation for
this section. Let R
e
and
Denition 3. Algorithm A 1 is a rate certifying algorithm if there exists an  such that the
certifying pair chosen on line 14 satises
for all k. A rate certifying pair is a pair of indices in the index set of S for which
at iteration k of a rate certifying algorithm.
Chang, et. al. (Chang et al., 2000) establish a relationship of this type for a particular
choice of rate certifying pair with
use it to prove asymptotic convergence. The
following theorem gives a bound on the number of iterations that are su-cient to drive the
criterion to within  m of its optimum for a rate certifying algorithm.
Theorem 5. Let (k) denote the sequence of states generated by Algorithm A 1 . If it is a rate
certifying algorithm then R
BL
iterations, where
(R  R( 0
and L is the maximum of the norms of the 2 by 2 matrices determined by restricting Q to
indices. In words, if we wish to get an accuracy of  m , then it is su-cient to performq
BL
Proof. Let fi; jg  W (k) denote the indices of a rate certifying pair in the working set such
that
Following (Dunn, 1979) we consider the following auxiliary equations. Let
k dier from
k in the two indices
dr k  (
e
we have
which can be written
We show by induction that  k  B k as follows.
We now control  k . Plugging the denition of ! k in equation (26) into equation (27) for  k
we obtain
In the latter case j
Putting the two equations from (28) together we obtain
where
since  k   Therefore, by (Dunn, 1979) equations (29) and (30) imply that
but going back through the relations
L and  k  B k implies
Consequently, when
BL
then
and
The proof is nished.
5.3 E-cient Computation of a Rate Certifying Pair
In the previous section we determined that   k   k is su-cient to establish
(Chang et al., 2000) show that a certifying pair always exists such that
They
do this by considering the solution to a linear programming (LP) problem (similar to the LP
problem for  k ), and then restricting this solution to two indices. In this section we show how
to solve this LP to produce a rate certifying pair in O(m log m) operations.
be the current solution and dene
Let   be the solution to the linear program
s.t.
Note that the solution to this problem and (19) are related by   . As in section 3,
dene
~
I
low
I
low
I
I
high
I
and choose
low
high
From (Chang et al., 2000) we know that the certifying pair (i; j) given by
is a rate certifying pair with rate
. The following lemma establishes that this pair can
be determined in a computationally e-cient manner.
Lemma 1. Given y, the rate certifying pair (i;
can be computed in O(m log m) time.
Proof. We describe an algorithm that computes this pair in O(m log m) time. Our algorithm
solves the LP in (31) and then computes the two indices using (32)-(33). Once the LP is solved
it is straightforward to implement (32)-(33) in O(m) steps, so we describe only the LP solution.
Consider the LP in (31). Recall that dR() . The Karush-Kuhn-Tucker conditions
for the solution  are
with  i  0,  i  0 and   These equations can be written
high
low
int
where
I
low
I
I
e
To solve these equations, x  and determine  to satisfy
high
low v i   0:
For example, if v i > , then set  To determine  we
use the constraint
Written out this becomes
i2I
low
| {z }
i2I
high
| {z }
i2I
int
Our strategy is to choose  so that it splits the samples into I
low and I
high in such a way that
the rst and second sums cancel as closely as possible. When they do not cancel exactly we
shift  so that the split occurs on a value v i , thereby placing samples with this value into I
int
and allowing us to choose their parameters  i to satisfy the equality. More specically we sort
the values of v in increasing order and use k to index the sorted list (i.e. v k  v k+1 ). As
increases from 1 to 1, jumping over values where being determined as above,
the value of   y is monotonically increasing and must pass from negative to positive. In fact it
is easy to see that   y increases by C each time an individual sample is jumped. Suppose that
this increasing function achieves the value 0 on the interval (v k ; v k+1 ). Then we let  be any
value in this interval and since I
int is empty and  was chosen to satisfy (35) we have a solution.
Suppose this increasing function skips the value 0 and jumps from a < 0 to b > 0 at
and there are a total of M  1 samples with this value of v (i.e.
Then set place the rst of these samples in I
low (the rest remain in
I
high ). If a=C is integral then this gives   and we have a solution once again (with
M of the samples satisfying (35) with equality and I
before). If a=C is not integral
then its remainder is used to determine  k+M 1 , the component of  corresponding to v k+M 1 .
This gives   and places this sample in I
int , and again we have a solution. Note that
there are many solutions to these equations. This construction gives   and   , both of which
are necessary to implement (32)-(33). It takes O(m log m) steps to sort the v, followed by an
additional pass through the list to initialize , placing all samples in I
high and yielding (0)  y.
Since   y begins at (0)  y and increases by C each time  is increased past a data point, the
components of  for all the points up to k
C c are changed by C placing them in I
low .
Then, if (0)y
C is not integral its remainder is used to determine the component of  for the
which is moved to I
int . Updating  in this way requires at most one complete
pass through the list. This completes the proof.
Algorithm 5.3 computes a rate certifying pair using the method described in the proof
above. In addition to the sort, this algorithm makes a total of four passes through the list.
The number of computations in this procedure can sometimes be reduced. Let i; j be a rate
certifying pair. Then v i and v j are on opposite sides of   , and since i; j is also a certifying
e
must lie between ~
high and ~
low (dened in (13) and (14)). This means that the sorting
operation required in our search for  can be restricted to the v i in this interval. Since the
sorting operation dominates the run time this can lead to a substantial savings when the number
of samples in this interval is small.
Algorithm Certifying Pair Algorithm.
INPUTS: y, v, and  (at the current iteration)
fsample indices for a rate certifying pairg
fL is an ordered list of indices in nondecreasing order of fv i g so that v L(l)  v L(l+1) g
finitially place all samples in I
high and compute (0)  yg
do
if (y
else if (y
end for
fdetermine split point index and move samples into I
low g
l  bEtaDotY=Cc
for l  do
end for
fif needed, move sample into I
int g
if (EtaDotY <
l  l
else
value in [v L(l  use v L(i
fdetermine indices for rate certifying pairg
LANL Technical Report: LA{UR{00-3800 6 Discussion
5.4 Summary of Rates
If we use Algorithm A 2 to choose a rate certifying pair then
2 and by theorem 5 Algorithm
A 1 will drive the criterion to within  m of its optimum in no more than
iterations. Further, with  so that
neglecting lower order
terms, the number of iterations simplies to
In the case where the working sets are of size two we can use this result to establish a worst
case overall run time for Algorithm A 1 . At each iteration we must solve a 2 by 2 QP problem,
update the v i (k), and determine the next certifying pair. The time to solve the 2 by 2 QP
problem is a constant, and it takes order m operations to update the v i (k). If we add m log m
operations to determine the certifying pair, the worst case run time is of order
Now consider our choice for  m obtained through an appropriate normalization of R (see discussion
at the beginning of this section). Because R tends to increase with m,  m will be an
increasing function of m. Although the form of this function is not yet known it will clearly
improve the run-time bounds presented above. For example, if  then the order of the
polynomial in these bounds is reduced by p.
6 Discussion
This paper considers a class of algorithms for support vector machines that decompose the
original Wolfe Dual QP problem into a sequence of smaller QP problems dened on subsets of
the data. Following the work of Keerthi et al. (Keerthi & Gilbert, 2000; Keerthi et al., 2001)
we provide a scalar condition that is necessary and su-cient for optimality of the QP problem.
This leads naturally to the introduction of certifying pairs as a necessary and su-cient condition
for stepwise improvement, and motivates the use of Algorithm A 1 as a model algorithm for this
problem. By leveraging the results of Chang, et al. (Chang et al., 2000) we have developed
Algorithm A 2 for selecting the certifying pair in Algorithm A 1 . Theorem 5 shows that the
number of iterations for this instantiation of Algorithm A 1 is O(m 4 ) and the overall run time
is O(m 5 log m).
Many existing SVM algorithms are either special cases of Algorithm A 1 or can be made
so through slight modication. For example, Platt's Sequential Minimal Optimization (SMO)
algorithm, which chooses working sets of size two, is designed to choose a pair that give a strict
increase in R at each step (Platt, 1998). The original algorithm however, contains a
aw that
LANL Technical Report: LA{UR{00-3800 References
can lead to improper behavior (Keerthi et al., 2001; Keerthi & Gilbert, 2000). This behavior
can be traced to its inability to guarantee a certifying pair in each working set. By forcing
each working set to contain a certifying pair the corrected algorithm not only has guaranteed
convergence, but also improved performance (Keerthi et al., 2001).
The SV M light algorithm in (Joachims, 1998) uses a modication of Zoutendijk's method
(Zoutendijk, 1970) to choose working sets of size q  2. This choice can be shown to contain
the q=2 largest v i from ~
I low and the q=2 smallest v i from ~
I high , thus guaranteeing at least one
certifying pair.
The chunking algorithm described in (Cristianini & Shawe-Taylor, 2000) and the decomposition
algorithm of (Osuna et al., 1997) both attempt to ensure improvement in R by choosing
working sets that include support vectors from the current solution plus a subset of samples
that violate an \optimality condition" with respect to this solution. A strict implementation of
the algorithms described in these papers can lead to undesirable behavior because they cannot
guarantee a certifying pair in their working sets. However, such a guarantee can be achieved
with a slight modication (as we did for the chunking algorithm in section 5.1).
It is not clear that the algorithms above satisfy the rate certifying condition in Denition 3,
nor that this is necessary to establish rates for them. We have described a new SVM algorithm
that satises the rate certifying condition and has polynomial-time rates. It is not yet clear how
this algorithm will compare with existing algorithms in practice. Note that Keerthi's GSMO
algorithm (Keerthi et al., 2001) and Jochamin's SV M light algorithm (Joachims, 1998) require
O(m) time to determine a certifying pair while A 2 requires O(m log m) time. However, we
know of no bounds on the rates of convergence for GSMO and SV M light (although they seem
to work well in practice), but can guarantee a polynomial convergence rate when we use A 2 .
Finally we note that the polynomial-time bound on the number of iterations scales as
4 , which is unattractive. We leave open the issue of the tightness of this bound, although
we suspect that it may be loose. A closely related issue is the determination of a proper
normalization for R that would give rise to an explicit functional dependence of  on m. This
is likely to improve the rate.



--R

Nonlinear Programming: Analysis and Methods (1st edition).
The analysis of decomposition methods for support vector machines.

An Introduction to Support Vector Machines and Other Kernel-based Learning Methods (1st edition)
Rates of convergence for conditional gradient algorithms near singular and non-singular extremals

Convergence of a generalized SMO algorithm for SVM classi
Improvements to Platt's SMO algorithm for SVM classi
On the convergence of the decomposition method for support vector machines.

Support vector machines: training and applications.

Fast training of support vector machines using sequential minimal optimiza- tion
Statistical Learning Theory.
Methods of Feasible Directions: A study in linear and non-linear pro- gramming
--TR

--CTR
Hong Qiao , Yan-Guo Wang , Bo Zhang, A simple decomposition algorithm for support vector machines with polynomial-time convergence, Pattern Recognition, v.40 n.9, p.2543-2549, September, 2007
Tobias Glasmachers , Christian Igel, Maximum-Gain Working Set Selection for SVMs, The Journal of Machine Learning Research, 7, p.1437-1466, 12/1/2006
Rong-En Fan , Pai-Hsuen Chen , Chih-Jen Lin, Working Set Selection Using Second Order Information for Training Support Vector Machines, The Journal of Machine Learning Research, 6, p.1889-1918, 12/1/2005
Thorsten Joachims, Training linear SVMs in linear time, Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining, August 20-23, 2006, Philadelphia, PA, USA
Nikolas List , Hans Ulrich Simon, General Polynomial Time Decomposition Algorithms, The Journal of Machine Learning Research, 8, p.303-321, 5/1/2007
Don Hush , Patrick Kelly , Clint Scovel , Ingo Steinwart, QP Algorithms with Guaranteed Accuracy and Run Time for Support Vector Machines, The Journal of Machine Learning Research, 7, p.733-769, 12/1/2006
Cheng-Ru Lin , Ken-Hao Liu , Ming-Syan Chen, Dual Clustering: Integrating Data Clustering over Optimization and Constraint Domains, IEEE Transactions on Knowledge and Data Engineering, v.17 n.5, p.628-637, May 2005
Luca Zanni , Thomas Serafini , Gaetano Zanghirati, Parallel Software for Training Large Scale Support Vector Machines on Multiprocessor Systems, The Journal of Machine Learning Research, 7, p.1467-1492, 12/1/2006
support vector machines;decomposition algorithms;polynomial-time algorithms