Empirical PAC-Bayes bounds for Markov chains
This work addresses the challenge of applying generalization theory to dependent data for researchers in machine learning and statistics, offering a practical, empirical solution that is incremental but fills a gap in existing bounds.
The paper tackles the problem of deriving PAC-Bayes generalization bounds for data with temporal dependence, specifically Markov chains, by proving a new bound that depends on the pseudo-spectral gap and providing an empirical estimate for it in finite state spaces, resulting in the first fully empirical bound that is shown to be as tight as non-empirical versions in simulations.
The core of generalization theory was developed for independent observations. Some PAC and PAC-Bayes bounds are available for data that exhibit a temporal dependence. However, there are constants in these bounds that depend on properties of the data-generating process: mixing coefficients, mixing time, spectral gap... Such constants are unknown in practice. In this paper, we prove a new PAC-Bayes bound for Markov chains. This bound depends on a quantity called the pseudo-spectral gap. The main novelty is that we can provide an empirical bound on the pseudo-spectral gap when the state space is finite. Thus, we obtain the first fully empirical PAC-Bayes bound for Markov chains. This extends beyond the finite case, although this requires additional assumptions. On simulated experiments, the empirical version of the bound is essentially as tight as the non-empirical one.