Generalization bounds for mixing processes via delayed online-to-PAC conversions
This work addresses the challenge of non-i.i.d. data in machine learning, providing theoretical guarantees for generalization in mixing processes, which is incremental as it builds on existing online learning and mixing theory.
The paper tackles the problem of bounding generalization error for statistical learning algorithms when training data comes from a stationary mixing process, rather than being i.i.d., by developing a framework that reduces this to online learning with delayed feedback, showing that bounded regret in this setting implies low generalization error with rates that trade off delay and dependence.
We study the generalization error of statistical learning algorithms in a non-i.i.d. setting, where the training data is sampled from a stationary mixing process. We develop an analytic framework for this scenario based on a reduction to online learning with delayed feedback. In particular, we show that the existence of an online learning algorithm with bounded regret (against a fixed statistical learning algorithm in a specially constructed game of online learning with delayed feedback) implies low generalization error of said statistical learning method even if the data sequence is sampled from a mixing time series. The rates demonstrate a trade-off between the amount of delay in the online learning game and the degree of dependence between consecutive data points, with near-optimal rates recovered in a number of well-studied settings when the delay is tuned appropriately as a function of the mixing time of the process.