AI RESEARCH
Empirical PAC-Bayes bounds for Markov chains
arXiv CS.LG
•
ArXi:2509.20985v2 Announce Type: replace-cross 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 Marko chains. This bound depends on a quantity called the pseudo-spectral gap.