Title: Fast and Strong Convergence of Online Learning Algorithms,
Abstract: In this paper, we study the online learning algorithm without explicit
regularization terms. This algorithm is essentially a stochastic gradient
descent scheme in a reproducing kernel Hilbert space (RKHS). The polynomially
decaying step size in each iteration can play a role of regularization to
ensure the generalization ability of online learning algorithm. We develop a
novel capacity dependent analysis on the performance of the last iterate of
online learning algorithm. The contribution of this paper is two-fold. First,
our nice analysis can lead to the convergence rate in the standard mean square
distance which is the best so far. Second, we establish, for the first time,
the strong convergence of the last iterate with polynomially decaying step
sizes in the RKHS norm. We demonstrate that the theoretical analysis
established in this paper fully exploits the fine structure of the underlying
RKHS, and thus can lead to sharp error estimates of online learning algorithm.