Convergence of Unregularized Online Learning Algorithms

Lei, Yunwen1,2; Shi, Lei3; Guo, Zheng-Chu4

2018

JOURNAL OF MACHINE LEARNING RESEARCH   影响因子和分区

1532-4435

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.

Learning theory Online learning Convergence analysis Reproducing kernel Hilbert space

SCI ; EI

英语

第一

Program of Shanghai Subject Chief Scientist[18XD1400700]

Automation & Control Systems ; Computer Science

Automation & Control Systems ; Computer Science, Artificial Intelligence

WOS:000435442100001

MICROTOME PUBL

20182605362261

Errors ; Hilbert spaces ; Iterative methods ; Learning algorithms ; Probability ; Vector spaces

Mathematics:921 ; Numerical Methods:921.6 ; Probability Theory:922.1

COMPUTER SCIENCE

Web of Science

1.Southern Univ Sci & Technol, Dept Comp Sci & Engn, Shenzhen Key Lab Computat Intelligence, Shenzhen 518055, Peoples R China
2.City Univ Hong Kong, Dept Math, Kowloon, Hong Kong, Peoples R China
3.Fudan Univ, Shanghai Key Lab Contemporary Appl Math, Sch Math Sci, Shanghai 200433, Peoples R China
4.Zhejiang Univ, Sch Math Sci, Hangzhou 310027, Zhejiang, Peoples R China

Lei, Yunwen,Shi, Lei,Guo, Zheng-Chu. Convergence of Unregularized Online Learning Algorithms[J]. JOURNAL OF MACHINE LEARNING RESEARCH,2018,18:1-33.

Lei, Yunwen,Shi, Lei,&Guo, Zheng-Chu.(2018).Convergence of Unregularized Online Learning Algorithms.JOURNAL OF MACHINE LEARNING RESEARCH,18,1-33.

Lei, Yunwen,et al."Convergence of Unregularized Online Learning Algorithms".JOURNAL OF MACHINE LEARNING RESEARCH 18(2018):1-33.