A new method to select working sets for Decomposition Methods solving Support Vector Machines
Daniel T. H. Lai, Marimuthu Swami Palaniswami, Navin Mani · 2003
In this report, we propose a iteration measure to determine a better working set choice for the decomposition method. The decomposition method generally solves a sequence of sub problems instead of the entire problem at each iterative step. This makes it an ideal optimization method for solving the Support Vector Machine classifier, which is usually trained on a large dataset using machines with limited processing memory. The rate of convergence of the decomposition algorithm depends largely on the order of the sub problems solved and has been shown to be linear in the worst case. Our iteration measure determines the amount of overstep if the update on an iterate causes it to exit the feasible region. We then choose a working set that minimizes this amount of overstep, there by also increasing the step towards the minimum of the objective function. We report some initial results, which show a good improvement to the rates of convergence for our benchmark datasets.