# Predictive PAC Learning and Process Decompositions

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

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 19 Sep 2013.

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

- [Statistical Estimation from Dependent Data](https://mlsanity.com/paper/2107.09773/) (2021)
- [Maximum diffusion reinforcement learning](https://mlsanity.com/paper/2309.15293/) (2023)
- [Generalization bounds for mixing processes via delayed online-to-PAC conversions](https://mlsanity.com/paper/2406.12600/) (2024)
- [Approximation Bounds for Recurrent Neural Networks with Application to Regression](https://mlsanity.com/paper/2409.05577/) (2024)
- [Approximation Bounds for Transformer Networks with Application to Regression](https://mlsanity.com/paper/2504.12175/) (2025)
- [Sparse Deep Learning for Time Series Data: Theory and Applications](https://mlsanity.com/paper/2310.03243/) (2023)
- [Empirical PAC-Bayes Bounds for Markov Chains](https://mlsanity.com/paper/2509.20985/) (2025)
- [Generalization for slowly mixing processes](https://mlsanity.com/paper/2305.00977/) (2023)
- [Understanding Generalization through Decision Pattern Shift](https://mlsanity.com/paper/2605.13148/) (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 informally call a stochastic process learnable if it admits a generalization error approaching zero in probability for any concept class with finite VC-dimension (IID processes are the simplest example). A mixture of learnable processes need not be learnable itself, and certainly its generalization error need not decay at the same rate. In this paper, we argue that it is natural in predictive PAC to condition not on the past observations but on the mixture component of the sample path. This definition not only matches what a realistic learner might demand, but also allows us to sidestep several otherwise grave problems in learning from dependent data. In particular, we give a novel PAC generalization bound for mixtures of learnable processes with a generalization error that is not worse than that of each mixture component. We also provide a characterization of mixtures of absolutely regular (β-mixing) processes, of independent probability-theoretic interest.