Online kernel learning with nearly constant support vectors

详细信息    查看全文

• 作者：Ming Lin^aAuthor Vitae ; Lijun Zhang^bAuthor Vitae ; Rong Jin^bAuthor Vitae ; Shifeng Weng^cAuthor Vitae ; Changshui Zhang^a ; Author Vitae
• 关键词：Online learning ; Kernel machine ; Nyströ ; m ; Sample complexity
• 刊名：Neurocomputing
• 出版年：2016
• 出版时间：29 February 2016
• 年：2016
• 卷：179
• 期：Complete
• 页码：26-36
• 全文大小：852 K

文摘

Nyström method has been widely used to improve the computational efficiency of batch kernel learning. The key idea of Nyström method is to randomly sample M support vectors from the collection of T   training instances, and learn a kernel classifier in the space spanned by the randomly sampled support vectors. In this work, we studied online regularized kernel learning using the Nyström method, with a focus on the sample complexity, i.e. the number of randomly sampled support vectors that are needed to yield the optimal convergence rate O(1/T)$O(1/T)$, where T   is the number of training instances received in online learning. We show that, when the loss function is smooth and strongly convex, only $O\left({\log }^{2}T\right)$ randomly sampled support vectors are needed to guarantee an O(logT/T)$O(\log T/T)$ convergence rate, which is almost optimal except for the $\log T$ factor. We further validate our theory by an extensive empirical study.