Sequential Minimal Optimization (SMO) (Platt:1999) is a major
tool for solving convex quadratic optimization problems induced by
Support Vector Machines (SVMs). It is based on the idea to
iterativley solve subproblems of size two.
In this work we will give a characterization of convex quadratic
optimization problems, which can be solved with the SMO technique as
well.
In addition we will present an efficient 1/m-rate-certifying pair
selection algorithm (HushScovel:2003, ListSimon:2006) leading to
polynomial-time convergence rates for such problems.
|