Generalization Bounds for Dependent Data using Online-to-Batch Conversion
<|reference_start|>Generalization Bounds for Dependent Data using Online-to-Batch Conversion: In this work, we give generalization bounds of statistical learning algorithms trained on samples drawn from a dependent data source, both in expectation and with high probability, using the Online-to-Batch conversion paradigm. We show that the generalization error of statistical learners in the dependent data setting is equivalent to the generalization error of statistical learners in the i.i.d. setting up to a term that depends on the decay rate of the underlying mixing stochastic process and is independent of the complexity of the statistical learner. Our proof techniques involve defining a new notion of stability of online learning algorithms based on Wasserstein distances and employing "near-martingale" concentration bounds for dependent random variables to arrive at appropriate upper bounds for the generalization error of statistical learners trained on dependent data.<|reference_end|>
@article{chatterjee2024generalization,
    title={Generalization Bounds for Dependent Data using Online-to-Batch
  Conversion},
    author={Sagnik Chatterjee, Manuj Mukherjee, Alhad Sethi},
    journal={arXiv preprint arXiv:2405.13666},
    year={2024},
    archivePrefix={arXiv},
    eprint={2405.13666},
    primaryClass={cs.LG}
}