Convergence

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

$$\min_{I}(\min(eig(K_{II}))) > 0$$

where I is any subset of $\{1,\ldots,l\}$ with $\vert I\vert \leq q$, K_II 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.