On complexity issues of online learning algorithms

In this paper, some new probabilistic upper bounds are presented for the online learning algorithm proposed in , and more generally for linear stochastic approximations in Hilbert spaces. With these upper bounds not only does one recover almost sure convergence, but also relaxes the square summable condition on the step size appeared in the early work. Furthermore two probabilistic upper bounds are given for an averaging process, both of which achieve the same rate with respect to sample size as in "batch learning" algorithms, and one of which is tight in both sample size and regularization parameter.