南方科技大学知识苑(SUSTech KC): Convergence of unregularized online learning algorithms

题名	Convergence of unregularized online learning algorithms
作者	Lei，Yunwen1,2 ; Shi，Lei 3; Guo，Zheng Chu 4
发表日期	2018-04-01
发表期刊	JOURNAL OF MACHINE LEARNING RESEARCH 影响因子和分区
ISSN	1532-4435
EISSN	1533-7928
卷号	18页码:1-33
摘要	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.
关键词	Convergence analysis Learning theory Online learning Reproducing kernel Hilbert space
相关链接	[Scopus记录]
收录类别	EI
语种	英语
学校署名	第一
ESI学科分类	COMPUTER SCIENCE
Scopus记录号	2-s2.0-85048749125
来源库	Scopus
成果类型	期刊论文
条目标识符	http://sustech.caswiz.com/handle/2SGJ60CL/44292
专题	工学院_计算机科学与工程系
作者单位	1.Shenzhen Key Laboratory of Computational Intelligence, Department of Computer Science and Engineering, Southern University of Science and Technology, ,Shenzhen,518055,China 2.Department of Mathematics, City University of Hong Kong, ,Kowloon,Hong Kong 3.School of Mathematical Sciences, Shanghai Key Laboratory for Contemporary Applied Mathematics, Fudan University, ,Shanghai,200433,China 4.School of Mathematical Sciences, Zhejiang University, ,Hangzhou,310027,China
第一作者单位	计算机科学与工程系
第一作者的第一单位	计算机科学与工程系
推荐引用方式 GB/T 7714	Lei，Yunwen,Shi，Lei,Guo，Zheng Chu. Convergence of unregularized online learning algorithms[J]. JOURNAL OF MACHINE LEARNING RESEARCH,2018,18:1-33.
APA	Lei，Yunwen,Shi，Lei,&Guo，Zheng Chu.(2018).Convergence of unregularized online learning algorithms.JOURNAL OF MACHINE LEARNING RESEARCH,18,1-33.
MLA	Lei，Yunwen,et al."Convergence of unregularized online learning algorithms".JOURNAL OF MACHINE LEARNING RESEARCH 18(2018):1-33.