Online Learning as Stochastic Approximation of Regularization Paths

Understand

In this paper, an online learning algorithm is proposed as sequential stochastic approximation of a regularization path converging to the regression function in reproducing kernel Hilbert spaces (RKHSs).

• We show that it is possible to produce the best known strong (RKHS norm) convergence rate of batch learning, through a careful choice of the gain or step size sequences, depending on regularity assumptions on the regression function.
• The corresponding weak (mean square distance) convergence rate is optimal in the sense that it reaches the minimax and individual lower rates in the literature.
• In both cases we deduce almost sure convergence, using Bernstein-type inequalities for martingales in Hilbert spaces.