Unregularized online learning algorithms with general loss functions

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journalpeer-review

33 Scopus Citations
View graph of relations


Related Research Unit(s)


Original languageEnglish
Pages (from-to)224-244
Journal / PublicationApplied and Computational Harmonic Analysis
Issue number2
Online published20 Aug 2015
Publication statusPublished - Mar 2017


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.

Research Area(s)

  • Bipartite ranking, Learning theory, Online learning, Pairwise learning, Reproducing kernel Hilbert space