Empirical PAC-Bayes Bounds for Markov Chains

Vahe Karagulyan, Pierre Alquier
Proceedings of The 29th International Conference on Artificial Intelligence and Statistics, PMLR 300:361-369, 2026.

Abstract

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 \textit{pseudo-spectral gap}, $\gamma_{ps}$. The main novelty is that we can provide an empirical bound on $\gamma_{ps}$ 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 one that depends on $\gamma_{ps}$.

Cite this Paper

BibTeX
@InProceedings{pmlr-v300-karagulyan26a, title = { Empirical PAC-Bayes Bounds for Markov Chains }, author = {Karagulyan, Vahe and Alquier, Pierre}, booktitle = {Proceedings of The 29th International Conference on Artificial Intelligence and Statistics}, pages = {361--369}, year = {2026}, editor = {Khan, Emtiyaz and Li, Yingzhen and Solin, Arno and Ramdas, Aaditya}, volume = {300}, series = {Proceedings of Machine Learning Research}, month = {02--05 May}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v300/main/assets/karagulyan26a/karagulyan26a.pdf}, url = {https://proceedings.mlr.press/v300/karagulyan26a.html}, abstract = { 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 \textit{pseudo-spectral gap}, $\gamma_{ps}$. The main novelty is that we can provide an empirical bound on $\gamma_{ps}$ 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 one that depends on $\gamma_{ps}$. } }
Endnote
%0 Conference Paper %T Empirical PAC-Bayes Bounds for Markov Chains %A Vahe Karagulyan %A Pierre Alquier %B Proceedings of The 29th International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2026 %E Emtiyaz Khan %E Yingzhen Li %E Arno Solin %E Aaditya Ramdas %F pmlr-v300-karagulyan26a %I PMLR %P 361--369 %U https://proceedings.mlr.press/v300/karagulyan26a.html %V 300 %X 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 \textit{pseudo-spectral gap}, $\gamma_{ps}$. The main novelty is that we can provide an empirical bound on $\gamma_{ps}$ 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 one that depends on $\gamma_{ps}$.
APA
Karagulyan, V. & Alquier, P.. (2026). Empirical PAC-Bayes Bounds for Markov Chains . Proceedings of The 29th International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 300:361-369 Available from https://proceedings.mlr.press/v300/karagulyan26a.html.

Related Material