Convergence of Unregularized Online Learning Algorithms

Yunwen Lei, Lei Shi, Zheng Chu Guo*

*Corresponding author for this work

Research output: Contribution to journalJournal articlepeer-review

9 Citations (Scopus)


In this paper we study the convergence of online gradient descent algorithms in reproducing kernel Hilbert spaces (RKHSs) without regularization. We establish a sufficient condition and a necessary condition for the convergence of excess generalization errors in expectation. A sufficient condition for the almost sure convergence is also given. With high probability, we provide explicit convergence rates of the excess generalization errors for both averaged iterates and the last iterate, which in turn also imply convergence rates with probability one. To our best knowledge, this is the first high-probability convergence rate for the last iterate of online gradient descent algorithms in the general convex setting. Without any boundedness assumptions on iterates, our results are derived by a novel use of two measures of the algorithm's one-step progress, respectively by generalization errors and by distances in RKHSs, where the variances of the involved martingales are cancelled out by the descent property of the algorithm.

Original languageEnglish
Number of pages33
JournalJournal of Machine Learning Research
Publication statusPublished - Apr 2018

Scopus Subject Areas

  • Software
  • Control and Systems Engineering
  • Statistics and Probability
  • Artificial Intelligence

User-Defined Keywords

  • Convergence analysis
  • Learning theory
  • Online learning
  • Reproducing kernel Hilbert space


Dive into the research topics of 'Convergence of Unregularized Online Learning Algorithms'. Together they form a unique fingerprint.

Cite this