A convergence rate estimate for the SVM decomposition method

Abstract

The training of Support Vector Machines using the decomposition method has one drawback; namely the selection of working sets such that convergence is as fast as possible. It has been shown by Lin that the rate is linear in the worse case under the assumption that all bounded Support Vectors have been determined. The analysis was done based on the change in the objective function and under a SVMlight selection rule. However, the rate estimate given is independent of time and hence gives little indication as to how the linear convergence speed varies during the iteration. In this initial analysis, we provide a treatment of the convergence from a gradient contraction perspective. We propose a ..