This is a work we finished one year ago and is accepted as a regular paper in ICDM 2010. NESVM is a fast SVM algorithm for primal linear and kernel SVM problems, with the optimal convergence rate of first-order method and simple computation in each iteration. The PDF of the paper can be downloaded here:
NESVM: a Fast Gradient Method for Support Vector Machines
You can also find it on arXiv. SVM is a fundamental classification tool for various machine learning tasks. However, its efficiency is not satisfying for large-scale classification problems. There exist several appealing SVM solvers, e.g., LIBSVM, SVM-Light, SVM-Perf, Pegasos. Most of them focus on solving dual SVM or solving primal SVM in an online way.
Compared with existing SVM solvers, NESVM is competitive in three aspects:
- NESVM is a fast gradient method with the optimal convergence rate at and linear time complexity. It is based on Nesterov’s method proposed in paper Smooth minimization of non-smooth functions. Only two matrix-vector multiplications are required in each iteration round.
- NESVM directly tackles the original primal problem of batch SVM and its implementation is fairly simple, thus it can be easily extended to and embedded in many other complex classification tasks.
- NESVM proposes novel smooth and differentiable alternatives for hinge loss and norm, which are commonly used in machine learning and difficult to optimize because they are not differentiable everywhere.
We compared the performance of NESVM with other popular SVM solvers on several datasets, here is an example of event recognition in computer vision:
I will post the code of NESVM in a few days.