Abstract
We study the generalization error of statistical learning algorithms in anon-i.i.d. setting, where the training data is sampled from a stationary mixingprocess. We develop an analytic framework for this scenario based on areduction to online learning with delayed feedback. In particular, we show thatthe existence of an online learning algorithm with bounded regret (against afixed statistical learning algorithm in a specially constructed game of onlinelearning with delayed feedback) implies low generalization error of saidstatistical learning method even if the data sequence is sampled from a mixingtime series. The rates demonstrate a trade-off between the amount of delay inthe online learning game and the degree of dependence between consecutive datapoints, with near-optimal rates recovered in a number of well-studied settingswhen the delay is tuned appropriately as a function of the mixing time of theprocess.