Generalization bounds for mixing processes via delayed online-to-PAC conversions
<|reference_start|>Generalization bounds for mixing processes via delayed online-to-PAC conversions: 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.<|reference_end|>
@article{abeles2024generalization,
    title={Generalization bounds for mixing processes via delayed online-to-PAC
  conversions},
    author={Baptiste Abeles, Eugenio Clerico, Gergely Neu},
    journal={arXiv preprint arXiv:2406.12600},
    year={2024},
    archivePrefix={arXiv},
    eprint={2406.12600},
    primaryClass={cs.LG}
}