Jeffrey Hajewski

Jeffrey Hajewski, Suely Oliveira, David E. Stewart

A new 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 data sets. The algorithm uses smoothing for the hinge-loss function, and an active set approach for the $\ell^{1}$ penalty.

Ibrahim Emirahmetoglu, Jeffrey Hajewski, Suely Oliveira et al.

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 $α$ 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/α)))$ guarded Newton steps for each value of $α$ except for asymptotic bands $α=Θ(1)$ and $α=Θ(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.