Online regularized learning with pairwise loss functions

Zheng-Chu Guo, Yiming Ying*, Ding-Xuan Zhou

*Corresponding author for this work

Research output: Journal Publications and ReviewsRGC 21 - Publication in refereed journalpeer-review

23 Citations (Scopus)

Abstract

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.
Original languageEnglish
Pages (from-to)127-150
JournalAdvances in Computational Mathematics
Volume43
Issue number1
DOIs
Publication statusPublished - 1 Feb 2017

Research Keywords

  • Online learning
  • Pairwise learning
  • Regularization
  • RKHS

Fingerprint

Dive into the research topics of 'Online regularized learning with pairwise loss functions'. Together they form a unique fingerprint.

Cite this