Concentration inequalities for Markov chains by Marton couplings and spectral methods
From MaRDI portal
Publication:2515947
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.
Recommendations
- Concentration of measure inequalities for Markov chains and \(\Phi\)-mixing processes.
- Concentration inequalities for Markov processes via coupling
- Concentration of Markov chains with bounded moments
- Chernoff-Hoeffding bounds for Markov chains: generalized and simplified
- Effective Berry-Esseen and concentration bounds for Markov chains with a spectral gap
Cited in
(91)- Concentration inequalities for Markov processes via coupling
- Rapid mixing of geodesic walks on manifolds with positive curvature
- Local M-estimation with discontinuous criterion for dependent and limited observations
- Lower bounds for moments of global scores of pairwise Markov chains
- Respondent-driven sampling and sparse graph convergence
- Concentration of measure inequalities for Markov chains and \(\Phi\)-mixing processes.
- Adaptive invariant density estimation for ergodic diffusions over anisotropic classes
- Clustering in block Markov chains
- An online algorithm for the risk-aware restless bandit
- General Bernstein-like inequality for additive functionals of Markov chains
- On limit theorems for persistent Betti numbers from dependent data
- When Janson meets McDiarmid: Bounded difference inequalities under graph-dependence
- Adaptive invariant density estimation for continuous-time mixing Markov processes under sup-norm risk
- Fundamental design principles for reinforcement learning algorithms
- Generalized Markov chain tree theorem and Kemeny's constant for a class of non-Markovian matrices
- Concentration inequalities for non-causal random fields
- Adaptive Huber regression on Markov-dependent data
- Exponential inequalities for nonstationary Markov chains
- A quantitative McDiarmid's inequality for geometrically ergodic Markov chains
- Statistical estimation of ergodic Markov chain kernel over discrete state space
- Function-specific mixing times and concentration away from equilibrium
- Concentration of Markov chains with bounded moments
- A concentration bound for contractive stochastic approximation
- On concentration inequalities for vector-valued Lipschitz functions
- Metropolis-Hastings reversiblizations of non-reversible Markov chains
- Talagrand concentration inequalities for stochastic partial differential equations
- Generalized high-dimensional trace regression via nuclear norm regularization
- Nonparametric Bayesian posterior contraction rates for scalar diffusions with high-frequency data
- Rademacher complexity for Markov chains: applications to kernel smoothing and Metropolis-Hastings
- Mixing time estimation in reversible Markov chains from a single sample path
- Elementary bounds on mixing times for decomposable Markov chains
- Transportation and concentration inequalities for bifurcating Markov chains
- Effective Berry-Esseen and concentration bounds for Markov chains with a spectral gap
- A Hoeffding inequality for Markov chains
- A note on transportation cost inequalities for diffusions with reflections
- Transport-information inequalities for Markov chains
- A concentration bound for \(\operatorname{LSPE}( \lambda )\)
- Spectral norm bounds for block Markov chain random matrices
- Singular value distribution of dense random matrices with block Markovian dependence
- Concentration inequality for U-statistics of order two for uniformly ergodic Markov chains
- Obtaining measure concentration from Markov contraction
- An inequality for the coupling moment in the case of two inhomogeneous Markov chains
- Hypothesis testing for Markov chain Monte Carlo
- Problem solving is often a matter of cooking up an appropriate Markov chain
- Chernoff and Berry–Esséen inequalities for Markov processes
- New Bernstein and Hoeffding type inequalities for regenerative Markov chains
- Analysis of non-reversible Markov chains via similarity orbits
- The Convex Mixture Distribution: Granger Causality for Categorical Time Series
- Normal approximation for functions of hidden Markov models
- Learning Markov models via low-rank optimization
- On the occupancy problem for a regime-switching model
- Hoeffding's inequality for general Markov chains and its applications to statistical learning
- On the rate of convergence for the length of the longest common subsequences in hidden Markov models
- On the cover time of dense graphs
- MCMC for imbalanced categorical data
- Hold-out estimates of prediction models for Markov processes
- Complexity results for MCMC derived from quantitative bounds
- Analysis of a Class of Multilevel Markov Chain Monte Carlo Algorithms Based on Independent Metropolis–Hastings
- Improved estimation of relaxation time in nonreversible Markov chains
- Dimension‐independent Markov chain Monte Carlo on the sphere
- On the \(\alpha\)-lazy version of Markov chains in estimation and testing problems
- Community structure recovery and interaction probability estimation for gossip opinion dynamics
- Improving Hoeffding's inequality using higher moments information
- Gaussian concentration bounds for stochastic chains of unbounded memory
- Consistent inference for diffusions from low frequency measurements
- Sampling random graph homomorphisms and applications to network data analysis
- Probability and moment inequalities for additive functionals of geometrically ergodic Markov chains
- Analysis of two-component Gibbs samplers using the theory of two projections
- Minimax optimality of deep neural networks on dependent data via PAC-Bayes bounds
- Rademacher learning rates for iterated random functions
- Frontiers to the learning of nonparametric hidden Markov models
- Non-asymptotic estimates for Markov transition matrices via spectral gap methods
- Deviation inequalities for contractive infinite memory processes
- Geometric Ergodicity of Trans-Dimensional Markov Chain Monte Carlo Algorithms
- Markov chain entropy games and the geometry of their Nash equilibria
- Spectral gap of nonreversible Markov chains
- Hoeffding's inequality for continuous-time Markov chains via the spectral gap
- Estimation of the order of non-parametric hidden Markov models using the singular values of an integral operator
- Concentration inequalities for sums of Markov-dependent random matrices
- McDiarmid type inequalities for Wasserstein contractive Markov chains
- Nonparametric Bayesian estimation in a multidimensional diffusion model with high frequency data
- Mixing time estimation in ergodic Markov chains from a single trajectory with contraction methods
- Learning and testing irreducible Markov chains via the k-cover time
- Minimax learning of ergodic Markov chains
- Random interval distillation for detection of change-points in Markov chain Bernoulli networks
- Towards a Banach space Chernoff bound for Markov chains via chaining arguments
- Robust estimation of a Markov chain transition matrix from multiple sample paths
- Extremal alignments in LCS-inference
- Bernstein's inequalities for general Markov chains
- Mixing and concentration by Ricci curvature
- A method to derive concentration of measure bounds on Markov chains
This page was built for publication: Concentration inequalities for Markov chains by Marton couplings and spectral methods
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2515947)
