A Dual Coordinate Descent Method for Large-Scale Linear SVM

Cho-Jui Hsieh, Kai-Wei Chang, Chih-Jen Lin, Sathia S. Keerthi, and S. Sundararajan, in ICML, 2008.


[Full Text]

Abstract

In many applications, data appear with a huge number of instances as well as features. Linear Support Vector Machines (SVM) is one of the most popular tools to deal with such large-scale sparse data. This paper presents a novel dual coordinate descent method for linear SVM with L1- and L2- loss functions. The proposed method is simple and reaches an ϵ-accurate solution in O(log(1/ϵ)) iterations. Experiments indicate that our method is much faster than state of the art solvers such as Pegasos, TRON, SVMperf , and a recent primal coordinate descent implementation.

Bib Entry

@inproceedings{HCLKS08,
  author = {Hsieh, Cho-Jui and Chang, Kai-Wei and Lin, Chih-Jen and Keerthi, Sathia S. and Sundararajan, S.},
  title = {A Dual Coordinate Descent Method for Large-Scale Linear SVM},
  booktitle = {ICML},
  slides_url = {http://bilbo.cs.illinois.edu/~kchang10/icml_talk.pdf},
  year = {2008}
}

Links