  We study the generalization performance of online learning algorithms trained
on samples coming from a dependent source of data. We show that the
generalization error of any stable online algorithm concentrates around its
regret--an easily computable statistic of the online performance of the
algorithm--when the underlying ergodic process is $\beta$- or $\phi$-mixing. We
show high probability error bounds assuming the loss function is convex, and we
also establish sharp convergence rates and deviation bounds for strongly convex
losses and several linear prediction problems such as linear and logistic
regression, least-squares SVM, and boosting on dependent data. In addition, our
results have straightforward applications to stochastic optimization with
dependent data, and our analysis requires only martingale convergence
arguments; we need not rely on more powerful statistical tools such as
empirical process theory.
