Refined bounds for online pairwise learning algorithms

Xiaming Chen, Yunwen Lei*

*Corresponding author for this work

Research output: Contribution to journalJournal articlepeer-review

12 Citations (Scopus)


Motivated by the recent growing interest in pairwise learning problems, we study the generalization performance of Online Pairwise lEaRning Algorithm (OPERA) in a reproducing kernel Hilbert space (RKHS) without an explicit regularization. The convergence rates established in this paper can be arbitrarily closed to O(T−[Formula presented]) within T iterations and largely improve the existing convergence rates for OPERA. Our novel analysis is conducted by showing an almost boundedness of the iterates encountered in the learning process with high probability after establishing an induction lemma on refining the RKHS norm estimate of the iterates.

Original languageEnglish
Pages (from-to)2656-2665
Number of pages10
Early online date2 Dec 2017
Publication statusPublished - 31 Jan 2018

Scopus Subject Areas

  • Computer Science Applications
  • Cognitive Neuroscience
  • Artificial Intelligence

User-Defined Keywords

  • Learning theory
  • Online learning
  • Pairwise learning
  • Reproducing Kernel Hilbert Space


Dive into the research topics of 'Refined bounds for online pairwise learning algorithms'. Together they form a unique fingerprint.

Cite this