Solving Linear SVMs with Multiple 1D Projections

back to overview

Reference

Schneider, J., Bogojeska, J., & Vlachos, M. (2014). Solving Linear SVMs with Multiple 1D Projections. Paper presented at the Conference on Information and Knowledge Management (CIKM).

Publication type

Paper in Conference Proceedings

Abstract

We present a new methodology for solving linear Support Vector Machines (SVMs) that capitalizes on multiple 1D projections. We show that the approach approximates the optimal solution with high accuracy and comes with analytical guarantees. Our solution adapts on methodologies from random projections, exponential search, and coordi- nate descent. In our experimental evaluation, we compare our approach with the popular liblinear SVM library. We demonstrate a signi?cant speedup on various benchmarks. At the same time, the new methodology provides a comparable or better approximation factor of the optimal solution and exhibits smooth convergence properties. Our results are accompanied by bounds on the time complexity and accuracy.

Persons

Organizational Units

  • Institute of Information Systems
  • Hilti Chair of Business Process Management

Original Source URL

Link