A Smoothing Algorithm for l1 Support Vector Machines
Ibrahim Emirahmetoglu Jeffrey Hajewski Suely Oliveira David E. Stewart
A smoothing algorithm is presented for solving the soft-margin Support Vector
Machine (SVM) optimization problem with an $\ell^{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
$\ell^{1}$ penalty. The smoothing parameter $\alpha$ is initially large, but
typically halved when the smoothed problem is solved to sufficient accuracy.
Convergence theory is presented that shows
$\mathcal{O}(1+\log(1+\log_+(1/\alpha)))$ guarded Newton steps for each value
of $\alpha$ except for asymptotic bands $\alpha=\Theta(1)$ and
$\alpha=\Theta(1/N)$, with only one Newton step provided $\eta\alpha\gg1/N$,
where $N$ is the number of data points and the stopping criterion that the
predicted reduction is less than $\eta\alpha$. The experimental results show
that our algorithm is capable of strong test accuracy without sacrificing
training speed.