next up previous
Next: Experimental Results Up: The Decomposition Algorithm Previous: Comparisons with Other Algorithms


In a recent technical report [1], we have shown that our algorithm converges in the case where the working set size is equal to 2 and without shrinking, for any kernel that verifies Mercer's conditions. To do so, we have used a theorem proved by Keerthi et al [6]. Note however that more recently, Lin [9] has shown the convergence of our algorithm for any value of the working set size (but again without shrinking), under the following hypothesis:

Assumption 1   The matrix K satisfies

\begin{displaymath}\min_{I}(\min(eig(K_{II}))) > 0\end{displaymath}

where I is any subset of $\{1,\ldots,l\}$ with $\vert I\vert \leq q$, KII is a square sub-matrix of K, and $\min(eig(.))$ is the smallest eigenvalue of a matrix.

Note finally that shrinking is a heuristic and thus using it should speed up the algorithm but no convergence proof will hold anymore.

Journal of Machine Learning Research