mlsanityData to 14 Oct 2026

Empirical PAC-Bayes Bounds for Markov Chains

arXiv 2509.20985 ↗First posted 25 Sep 2025stat.ML cs.LGcited by 3

Not on the map. Why?

Abstract (arXiv)

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.

Key facts. Cited by 3 papers in the map (data through 14 Oct 2026). Builds on 18 of its 60 references that are in the map. First posted on arXiv 25 Sep 2025.

Builds on

18 of 60 references.

References · 18

  1. 2017Computing Nonvacuous Generalization Bounds for Deep (Stochastic) Neural Networks with Many More Parameters than Training Datacited by 533
  2. 2021User-friendly introduction to PAC-Bayes boundscited by 239
  3. 2023Generalization Bounds: Perspectives from Information Theory and PAC-Bayescited by 61
  4. 2016Simpler PAC-Bayesian Bounds for Hostile Datacited by 46
  5. 2019PAC-Bayes Un-Expected Bernstein Inequalitycited by 36
  6. 2017Mixing time estimation in reversible Markov chains from a single sample pathcited by 27
  7. 2019Estimating the Mixing Time of Ergodic Markov Chainscited by 25
  8. 2023More PAC-Bayes bounds: From bounded losses, to losses with general tail behaviors, to anytime validitycited by 17
  9. 2020Learning Partially Known Stochastic Dynamics with Empirical PAC Bayescited by 16
  10. 2021Chebyshev-Cantelli PAC-Bayes-Bennett Inequality for the Weighted Majority Votecited by 13
  11. 2023Tighter PAC-Bayes Bounds Through Coin-Bettingcited by 13
  12. 2022Split-kl and PAC-Bayes-split-kl Inequalities for Ternary Random Variablescited by 11
6 more
  1. 2013Predictive PAC Learning and Process Decompositionscited by 10
  2. 2024Generalization bounds for mixing processes via delayed online-to-PAC conversionscited by 9
  3. 2021PAC-Bayesian theory for stochastic LTI systemscited by 7
  4. 2024Better-than-KL PAC-Bayes Boundscited by 4
  5. 2024Minimax optimality of deep neural networks on dependent data via PAC-Bayes boundscited by 4
  6. 2024Estimating the Mixing Coefficients of Geometrically Ergodic Markov Processescited by 3

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2025: 1; 2026: 2.

3 papers.

  1. 2025PAC-Bayesian Reinforcement Learning Trains Generalizable Policiescited by 1
  2. 2026PAC-Bayesian Reconstruction Guarantees for Time Series Variational Autoencoderscited by 1
  3. 2026Minimax estimation of the pseudo-spectral gap of continuous Markov chains, with applications to empirical concentration boundscited by 0