Online regularized learning with pairwise loss functions

详细信息    查看全文

• 作者：Zheng-Chu Guo ; Yiming Ying ; Ding-Xuan Zhou
• 关键词：Pairwise learning ; Online learning ; Regularization ; RKHS
• 刊名：Advances in Computational Mathematics
• 出版年：2017
• 出版时间：February 2017
• 年：2017
• 卷：43
• 期：1
• 页码：127-150
• 全文大小：
• 刊物类别：Computer Science
• 刊物主题：Computational Mathematics and Numerical Analysis; Mathematical Modeling and Industrial Mathematics; Mathematical and Computational Biology; Computational Science and Engineering; Visualization;
• 出版者：Springer US
• ISSN：1572-9044
• 卷排序：43

文摘

Recently, there has been considerable work on analyzing learning algorithms with pairwise loss functions in the batch setting. There is relatively little theoretical work on analyzing their online algorithms, despite of their popularity in practice due to the scalability to big data. In this paper, we consider online learning algorithms with pairwise loss functions based on regularization schemes in reproducing kernel Hilbert spaces. In particular, we establish the convergence of the last iterate of the online algorithm under a very weak assumption on the step sizes and derive satisfactory convergence rates for polynomially decaying step sizes. Our technique uses Rademacher complexities which handle function classes associated with pairwise loss functions. Since pairwise learning involves pairs of examples, which are no longer i.i.d., standard techniques do not directly apply to such pairwise learning algorithms. Hence, our results are a non-trivial extension of those in the setting of univariate loss functions to the pairwise setting.