A Space-Efficient One-Pass Online SVM Algorithm

Yangwei Liu, Ziyun Huang, Jinhui Xu

Research output: Contribution to journalArticlepeer-review

Abstract

In this paper we consider the problem of training a Support Vector Machine (SVM) online using a stream of data in random order. We provide a fast online training algorithm for general SVM on very large datasets. Based on the geometric interpretation of SVM known as the polytope distance, our algorithm uses a gradient descent procedure to solve the problem. With high probability our algorithm outputs an (ϵ,δ)-approximation result in constant time and space, which is independent of the size of the dataset, where (ϵ,δ)-approximation means that the separating margin of the classifier is almost optimal (with error ≤ ε), and the number of misclassified training points is very small (with error ≤ δ). Experimental results show that our algorithm outperforms most of existing online algorithms, especially in the space requirement aspect, while maintaining high accuracy.

Original languageEnglish (US)
Pages (from-to)63-79
Number of pages17
JournalInternational Journal of Computational Geometry and Applications
Volume34
Issue number1-2
DOIs
StatePublished - Jun 1 2024

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Geometry and Topology
  • Computational Theory and Mathematics
  • Computational Mathematics
  • Applied Mathematics

Fingerprint

Dive into the research topics of 'A Space-Efficient One-Pass Online SVM Algorithm'. Together they form a unique fingerprint.

Cite this