A Smoothing Algorithm for l1 Support Vector Machines

A smoothing algorithm is presented for solving the soft-margin Support Vector Machine (SVM) optimization problem with an ℓ1 penalty. This algorithm is designed to require a modest number of passes over the data, which is an important measure of its cost for very large datasets. The algorithm uses smoothing for the hinge-loss function, and an active set approach for the ℓ1 penalty. The smoothing parameter α is initially large, but typically halved when the smoothed problem is solved to sufficient accuracy. Convergence theory is presented that shows O(1+log(1+log_+(1/α))) guarded Newton steps for each value of α except for asymptotic bands α=Theta(1) and α=Theta(1/N), with only one Newton step provided ηαgg1/N, where N is the number of data points and the stopping criterion that the predicted reduction is less than ηα. The experimental results show that our algorithm is capable of strong test accuracy without sacrificing training speed.