REVIEW 2 cited by
Concentration inequalities for Markov chains by Marton couplings and spectral methods
Not yet reviewed by Pith; the record is open.
This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.
SPECIMEN: schema-true, not a live event
T0 review · schema-true
One-sentence machine reading of the paper's core claim.
pith:XXXXXXXX · record.json · timestamp
Signed reviews
read the original abstract
We prove a version of McDiarmid's bounded differences inequality for Markov chains, with constants proportional to the mixing time of the chain. We also show variance bounds and Bernstein-type inequalities for empirical averages of Markov chains. In the case of non-reversible chains, we introduce a new quantity called the "pseudo spectral gap", and show that it plays a similar role for non-reversible chains as the spectral gap plays for reversible chains. Our techniques for proving these results are based on a coupling construction of Katalin Marton, and on spectral techniques due to Pascal Lezaud. The pseudo spectral gap generalises the multiplicative reversiblication approach of Jim Fill.
Forward citations
Cited by 2 Pith papers
-
Recovering semipermeable barriers from reflected Brownian motion
Semipermeable barrier locations can be recovered from discrete samples of reflected Brownian motion, with T^{-2/3} error for fixed sampling intervals and exp(-c√T) error in a high-frequency regime.
-
PAC-Bayesian Reinforcement Learning Trains Generalizable Policies
A mixing-time-aware PAC-Bayes bound is turned into PB-SAC, an algorithm that computes tightening certified performance lower bounds during SAC training on MuJoCo tasks.
Discussion (0). Continue with ORCID to comment.