Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2406.12600 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866929719735222272 |
|---|---|
| author | Abeles, Baptiste Clerico, Eugenio Neu, Gergely |
| author_facet | Abeles, Baptiste Clerico, Eugenio Neu, Gergely |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2406_12600 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Generalization bounds for mixing processes via delayed online-to-PAC conversions Abeles, Baptiste Clerico, Eugenio Neu, Gergely Machine Learning 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. |
| title | Generalization bounds for mixing processes via delayed online-to-PAC conversions |
| topic | Machine Learning |
| url | https://arxiv.org/abs/2406.12600 |