# Generalization bounds for mixing processes via delayed online-to-PAC conversions

arXiv: https://arxiv.org/abs/2406.12600 · HTML: https://mlsanity.com/paper/2406.12600/

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- Builds on 15 of its 40 references that are in the map.
- First posted on arXiv 18 Jun 2024.

## Builds on (most cited first, 15 of 15)

- [Online Learning: A Modern Introduction Using Convex Optimization](https://mlsanity.com/paper/1912.13213/) (2019)
- [User-friendly introduction to PAC-Bayes bounds](https://mlsanity.com/paper/2110.11216/) (2021)
- [Learning Without Mixing: Towards A Sharp Analysis of Linear System Identification](https://mlsanity.com/paper/1802.08334/) (2018)
- [Online Learning under Delayed Feedback](https://mlsanity.com/paper/1306.0686/) (2013)
- [A Primer on PAC-Bayesian Learning](https://mlsanity.com/paper/1901.05353/) (2019)
- [How much does your data exploration overfit? Controlling bias via information usage](https://mlsanity.com/paper/1511.05219/) (2015)
- [Generalization Bounds: Perspectives from Information Theory and PAC-Bayes](https://mlsanity.com/paper/2309.04381/) (2023)
- [A unified recipe for deriving (time-uniform) PAC-Bayes bounds](https://mlsanity.com/paper/2302.03421/) (2023)
- [PAC-Bayes Generalisation Bounds for Heavy-Tailed Losses through Supermartingales](https://mlsanity.com/paper/2210.00928/) (2022)
- [Online-to-PAC Conversions: Generalization Bounds via Regret Analysis](https://mlsanity.com/paper/2305.19674/) (2023)
- [Predictive PAC Learning and Process Decompositions](https://mlsanity.com/paper/1309.4859/) (2013)
- [Statistical Estimation of Ergodic Markov Chain Kernel over Discrete State Space](https://mlsanity.com/paper/1809.05014/) (2018)
- [PAC-Bayes Generalisation Bounds for Dynamical Systems Including Stable RNNs](https://mlsanity.com/paper/2312.09793/) (2023)
- [Generalization Bounds for Dependent Data using Online-to-Batch Conversion](https://mlsanity.com/paper/2405.13666/) (2024)
- [PAC-Bayesian-Like Error Bound for a Class of Linear Time-Invariant Stochastic State-Space Models](https://mlsanity.com/paper/2212.14838/) (2022)

## Built on by (most cited first, 9 of 9)

- [Empirical PAC-Bayes Bounds for Markov Chains](https://mlsanity.com/paper/2509.20985/) (2025)
- [Online-to-PAC generalization bounds under graph-mixing dependencies](https://mlsanity.com/paper/2410.08977/) (2024)
- [PAC-Bayesian Reinforcement Learning Trains Generalizable Policies](https://mlsanity.com/paper/2510.10544/) (2025)
- [Adversarial Bandit Optimization with Globally Bounded Perturbations to Linear Losses](https://mlsanity.com/paper/2603.26066/) (2026)
- [Linear Bandits with Non-i.i.d. Noise](https://mlsanity.com/paper/2505.20017/) (2025)
- [Effective Sample Size and Generalization Bounds for Temporal Networks](https://mlsanity.com/paper/2508.06066/) (2025)
- [PAC-Bayesian Generalization Bounds for Graph Convolutional Networks on Inductive Node Classification](https://mlsanity.com/paper/2509.06600/) (2025)
- [Delay Complexity Dimension: Learning with Delayed and Censored Labels](https://mlsanity.com/paper/2610.18935/) (2026)
- [Minimax estimation of the pseudo-spectral gap of continuous Markov chains, with applications to empirical concentration bounds](https://mlsanity.com/paper/2610.20007/) (2026)

## Abstract (arXiv)

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.