Online sparse passive aggressive learning with kernels

• Main Authors: LU, Jing, ZHAO, Peilin, HOI, Steven C. H.
• Format: text
• Language: English
• Published: Institutional Knowledge at Singapore Management University 2016
• Subjects: Computer Sciences; Databases and Information Systems; Theory and Algorithms
• Online Access: https://ink.library.smu.edu.sg/sis_research/3416; https://ink.library.smu.edu.sg/context/sis_research/article/4417/viewcontent/Onlinesparsepassiveaggressivelearningwithkernels.pdf
• Institution: Singapore Management University

Conventional online kernel methods often yield an unboundedlarge number of support vectors, making them inefficient and non-scalable forlarge-scale applications. Recent studies on bounded kernel-based onlinelearning have attempted to overcome this shortcoming. Although they can boundthe number of support vectors at each iteration, most of them fail to bound thenumber of support vectors for the final output solution which is often obtainedby averaging the series of solutions over all the iterations. In this paper, wepropose a novel kernel-based online learning method, Sparse Passive Aggressivelearning (SPA), which can output a final solution with a bounded number ofsupport vectors. The key idea of our method is to explore an efficientstochastic sampling strategy, which turns an example into a new support vectorwith some probability that depends on the loss suffered by the example. Wetheoretically prove that the proposed SPA algorithm achieves an optimal regretbound in expectation, and empirically show that the new algorithm outperformsvarious bounded kernel-based online learning algorithms.