# Hoeffding's Inequality for Markov Chains under Generalized Concentrability Condition

arXiv: https://arxiv.org/abs/2310.02941 · HTML: https://mlsanity.com/paper/2310.02941/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 27 of its 88 references that are in the map.
- First posted on arXiv 4 Oct 2023.

## Builds on (most cited first, 27 of 27)

- [Generative Adversarial Networks](https://mlsanity.com/paper/2203.00667/) (2022)
- [Improved Training of Wasserstein GANs](https://mlsanity.com/paper/1704.00028/) (2017)
- [Demystifying MMD GANs](https://mlsanity.com/paper/1801.01401/) (2018)
- [f-GAN: Training Generative Neural Samplers using Variational Divergence Minimization](https://mlsanity.com/paper/1606.00709/) (2016)
- [Data-driven Distributionally Robust Optimization Using the Wasserstein Metric: Performance Guarantees and Tractable Reformulations](https://mlsanity.com/paper/1505.05116/) (2015)
- [MMD GAN: Towards Deeper Understanding of Moment Matching Network](https://mlsanity.com/paper/1705.08584/) (2017)
- [Distributionally Robust Stochastic Optimization with Wasserstein Distance](https://mlsanity.com/paper/1604.02199/) (2016)
- [Training generative neural networks via Maximum Mean Discrepancy optimization](https://mlsanity.com/paper/1505.03906/) (2015)
- [The Cramer Distance as a Solution to Biased Wasserstein Gradients](https://mlsanity.com/paper/1705.10743/) (2017)
- [Non-strongly-convex smooth stochastic approximation with convergence rate O(1/n)](https://mlsanity.com/paper/1306.2119/) (2013)
- [Differentiable Learning of Quantum Circuit Born Machine](https://mlsanity.com/paper/1804.04168/) (2018)
- [Distributionally Robust Optimization and Generalization in Kernel Methods](https://mlsanity.com/paper/1905.10943/) (2019)
- [Harder, Better, Faster, Stronger Convergence Rates for Least-Squares Regression](https://mlsanity.com/paper/1602.05419/) (2016)
- [Banach Wasserstein GAN](https://mlsanity.com/paper/1806.06621/) (2018)
- [Adaptivity of averaged stochastic gradient descent to local strong convexity for logistic regression](https://mlsanity.com/paper/1303.6149/) (2013)
- [Scan B-Statistic for Kernel Change-Point Detection](https://mlsanity.com/paper/1507.01279/) (2015)
- [Sobolev GAN](https://mlsanity.com/paper/1711.04894/) (2017)
- [On gradient regularizers for MMD GANs](https://mlsanity.com/paper/1805.11565/) (2018)
- [Fisher GAN](https://mlsanity.com/paper/1705.09675/) (2017)
- [Learning fair representation with a parametric integral probability metric](https://mlsanity.com/paper/2202.02943/) (2022)
- [Perturbation theory for Markov chains via Wasserstein distance](https://mlsanity.com/paper/1503.04123/) (2015)
- [Distributional Robustness with IPMs and links to Regularization and GANs](https://mlsanity.com/paper/2006.04349/) (2020)
- [Change Detection with the Kernel Cumulative Sum Algorithm](https://mlsanity.com/paper/1903.01661/) (2019)
- [A Class of Dimension-free Metrics for the Convergence of Empirical Measures](https://mlsanity.com/paper/2104.12036/) (2021)
- [Probabilistic Contraction Analysis of Iterated Random Operators](https://mlsanity.com/paper/1804.01195/) (2018)
- [A Hoeffding Inequality for Finite State Markov Chains and its Applications to Markovian Bandits](https://mlsanity.com/paper/2001.01199/) (2020)
- [Change Detection of Markov Kernels with Unknown Pre and Post Change Kernel](https://mlsanity.com/paper/2201.11722/) (2022)

## Built on by (most cited first, 3 of 3)

- [Computing the Bias of Constant-step Stochastic Approximation with Markovian Noise](https://mlsanity.com/paper/2405.14285/) (2024)
- [Learning Ergodic Dynamical Systems from a Finite Trajectory](https://mlsanity.com/paper/2607.22399/) (2026)
- [Minimax estimation of the pseudo-spectral gap of continuous Markov chains, with applications to empirical concentration bounds](https://mlsanity.com/paper/2610.20007/) (2026)

## Abstract (arXiv)

This paper studies Hoeffding's inequality for Markov chains under the generalized concentrability condition defined via integral probability metric (IPM). The generalized concentrability condition establishes a framework that interpolates and extends the existing hypotheses of Markov chain Hoeffding-type inequalities. The flexibility of our framework allows Hoeffding's inequality to be applied beyond the ergodic Markov chains in the traditional sense. We demonstrate the utility by applying our framework to several non-asymptotic analyses arising from the field of machine learning, including (i) a generalization bound for empirical risk minimization with Markovian samples, (ii) a finite sample guarantee for Ployak-Ruppert averaging of SGD, and (iii) a new regret bound for rested Markovian bandits with general state space.