Unregularized online learning algorithms with general loss functions

详细信息    查看全文

• 作者：Yiming Ying^a ; ^{yying@albany.edu} ; Ding-Xuan Zhou^b
• 关键词：Learning theory ; Online learning ; Reproducing kernel Hilbert space ; Pairwise learning ; Bipartite ranking
• 刊名：Applied and Computational Harmonic Analysis
• 出版年：2017
• 出版时间：March 2017
• 年：2017
• 卷：42
• 期：2
• 页码：224-244
• 全文大小：480 K
• 卷排序：42

文摘

In this paper, we consider unregularized online learning algorithms in a Reproducing Kernel Hilbert Space (RKHS). Firstly, we derive explicit convergence rates of the unregularized online learning algorithms for classification associated with a general α-activating loss (see Definition 1 below). Our results extend and refine the results in [30] for the least square loss and the recent result [3] for the loss function with a Lipschitz-continuous gradient. Moreover, we establish a very general condition on the step sizes which guarantees the convergence of the last iterate of such algorithms. Secondly, we establish, for the first time, the convergence of the unregularized pairwise learning algorithm with a general loss function and derive explicit rates under the assumption of polynomially decaying step sizes. Concrete examples are used to illustrate our main results. The main techniques are tools from convex analysis, refined inequalities of Gaussian averages [5], and an induction approach.