mlsanityData to 14 Oct 2026

Hoeffding's Inequality for Markov Chains under Generalized Concentrability Condition

arXiv 2310.02941 ↗First posted 4 Oct 2023stat.ML cs.LG math.PRcited by 3

Not on the map. Why?

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.

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

27 of 88 references.

References · 27

  1. 2022Generative Adversarial Networkscited by 5,627
  2. 2017Improved Training of Wasserstein GANscited by 2,235
  3. 2018Demystifying MMD GANscited by 1,293
  4. 2016f-GAN: Training Generative Neural Samplers using Variational Divergence Minimizationcited by 506
  5. 2015Data-driven Distributionally Robust Optimization Using the Wasserstein Metric: Performance Guarantees and Tractable Reformulationscited by 291
  6. 2017MMD GAN: Towards Deeper Understanding of Moment Matching Networkcited by 254
  7. 2016Distributionally Robust Stochastic Optimization with Wasserstein Distancecited by 185
  8. 2015Training generative neural networks via Maximum Mean Discrepancy optimizationcited by 151
  9. 2017The Cramer Distance as a Solution to Biased Wasserstein Gradientscited by 119
  10. 2013Non-strongly-convex smooth stochastic approximation with convergence rate O(1/n)cited by 111
  11. 2018Differentiable Learning of Quantum Circuit Born Machinecited by 93
  12. 2019Distributionally Robust Optimization and Generalization in Kernel Methodscited by 73
15 more
  1. 2016Harder, Better, Faster, Stronger Convergence Rates for Least-Squares Regressioncited by 64
  2. 2018Banach Wasserstein GANcited by 56
  3. 2013Adaptivity of averaged stochastic gradient descent to local strong convexity for logistic regressioncited by 32
  4. 2015Scan B-Statistic for Kernel Change-Point Detectioncited by 29
  5. 2017Sobolev GANcited by 29
  6. 2018On gradient regularizers for MMD GANscited by 28
  7. 2017Fisher GANcited by 22
  8. 2022Learning fair representation with a parametric integral probability metriccited by 20
  9. 2015Perturbation theory for Markov chains via Wasserstein distancecited by 18
  10. 2020Distributional Robustness with IPMs and links to Regularization and GANscited by 17
  11. 2019Change Detection with the Kernel Cumulative Sum Algorithmcited by 12
  12. 2021A Class of Dimension-free Metrics for the Convergence of Empirical Measurescited by 5
  13. 2018Probabilistic Contraction Analysis of Iterated Random Operatorscited by 3
  14. 2020A Hoeffding Inequality for Finite State Markov Chains and its Applications to Markovian Banditscited by 3
  15. 2022Change Detection of Markov Kernels with Unknown Pre and Post Change Kernelcited by 3

Built on by

Cited by year (2026 to 14 Oct)

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

3 papers.

  1. 2024Computing the Bias of Constant-step Stochastic Approximation with Markovian Noisecited by 9
  2. 2026Learning Ergodic Dynamical Systems from a Finite Trajectorycited by 1
  3. 2026Minimax estimation of the pseudo-spectral gap of continuous Markov chains, with applications to empirical concentration boundscited by 0