Empirical PAC-Bayes bounds for Markov chains

• URL: http://arxiv.org/abs/2509.20985v1
• Date: Thu, 25 Sep 2025 10:28:49 GMT
• Title: Empirical PAC-Bayes bounds for Markov chains
• Authors: Vahe Karagulyan, Pierre Alquier,
• Abstract summary: We prove a new PAC-Bayes bound for Markov chains.<n>This bound depends on a quantity called the pseudo-spectral gap.<n>On simulated experiments, the empirical version of the bound is essentially as tight as the non-empirical one.
• Score: 4.042110592015443
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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 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.

Related papers

• Statistical Consistency of Discrete-to-Continuous Limits of Determinantal Point Processes [8.737375836744933]
  We show that continuous DPPs can be obtained as limits on random graphs with Bernoulli edges.<n>We show that continuous DPPs can be obtained as limits on random graphs with Bernoulli edges.
  arXiv  Detail & Related papers  (2026-03-02T10:00:25Z)
• Complexity of PXP scars revisited [2.558693399161971]
  We revisit a quantum quench scenario in which either a scarring or thermalizing initial state evolves under the PXP Hamiltonian.<n>We study the time evolution of spread complexity and related quantities in the Krylov basis.
  arXiv  Detail & Related papers  (2025-06-26T11:25:44Z)
• A universal constraint for relaxation rates for quantum Markov generators: complete positivity and beyond [0.0]
  We show that positivity can be relaxed to 2-positivity without affecting the validity of the universal constraint.<n>We also explore the connection between these bounds and the number of steady states in quantum processes.
  arXiv  Detail & Related papers  (2025-05-30T11:11:40Z)
• Ito Diffusion Approximation of Universal Ito Chains for Sampling, Optimization and Boosting [64.0722630873758]
  We consider rather general and broad class of Markov chains, Ito chains, that look like Euler-Maryama discretization of some Differential Equation. We prove the bound in $W_2$-distance between the laws of our Ito chain and differential equation.
  arXiv  Detail & Related papers  (2023-10-09T18:38:56Z)
• A unified recipe for deriving (time-uniform) PAC-Bayes bounds [31.921092049934654]
  We present a unified framework for deriving PAC-Bayesian generalization bounds. Our bounds are anytime-valid (i.e., time-uniform), meaning that they hold at all stopping times.
  arXiv  Detail & Related papers  (2023-02-07T12:11:59Z)
• Lower Bounds for Learning in Revealing POMDPs [88.23337313766355]
  This paper studies the fundamental limits of reinforcement learning (RL) in the challenging emphpartially observable setting. For emphmulti-step revealing POMDPs, we show that the latent state-space dependence is at least $Omega(S1.5)$ in the sample complexity.
  arXiv  Detail & Related papers  (2023-02-02T18:59:30Z)
• Observation of Time-Crystalline Eigenstate Order on a Quantum Processor [80.17270167652622]
  Quantum-body systems display rich phase structure in their low-temperature equilibrium states. We experimentally observe an eigenstate-ordered DTC on superconducting qubits. Results establish a scalable approach to study non-equilibrium phases of matter on current quantum processors.
  arXiv  Detail & Related papers  (2021-07-28T18:00:03Z)
• Interplay between transport and quantum coherences in free fermionic systems [58.720142291102135]
  We study the quench dynamics in free fermionic systems. In particular, we identify a function, that we dub emphtransition map, which takes the value of the stationary current as input and gives the value of correlation as output.
  arXiv  Detail & Related papers  (2021-03-24T17:47:53Z)
• Causal Expectation-Maximisation [70.45873402967297]
  We show that causal inference is NP-hard even in models characterised by polytree-shaped graphs. We introduce the causal EM algorithm to reconstruct the uncertainty about the latent variables from data about categorical manifest variables. We argue that there appears to be an unnoticed limitation to the trending idea that counterfactual bounds can often be computed without knowledge of the structural equations.
  arXiv  Detail & Related papers  (2020-11-04T10:25:13Z)
• PAC-Bayes Analysis Beyond the Usual Bounds [16.76187007910588]
  We focus on a learning model where the learner observes a finite set of training examples. The learned data-dependent distribution is then used to make randomized predictions.
  arXiv  Detail & Related papers  (2020-06-23T14:30:24Z)
• On the complex behaviour of the density in composite quantum systems [62.997667081978825]
  We study how the probability of presence of a particle is distributed between the two parts of a composite fermionic system. We prove that it is a non-perturbative property and we find out a large/small coupling constant duality. Inspired by the proof of KAM theorem, we are able to deal with this problem by introducing a cut-off in energies that eliminates these small denominators.
  arXiv  Detail & Related papers  (2020-04-14T21:41:15Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.