Hoeffding's lemma for Markov Chains and its applications to statistical learning

Jianqing Fan; Bai Jiang; Qiang Sun

paper

Hoeffding's lemma for Markov Chains and its applications to statistical learning

arXiv:1802.00211

Abstract

We extend Hoeffding's lemma to general-state-space and not necessarily reversible Markov chains. Let ${X_{i}}_{i \geq 1}$ be a stationary Markov chain with invariant measure $π$ and absolute spectral gap $1 - λ$ , where $λ$ is defined as the operator norm of the transition kernel acting on mean zero and square-integrable functions with respect to $π$ . Then, for any bounded functions $f_{i} : x \mapsto [a_{i}, b_{i}]$ , the sum of $f_{i} (X_{i})$ is sub-Gaussian with variance proxy $\frac{1 + λ}{1 - λ} \cdot \sum_{i} \frac{( b _{i} - a _{i} ) ^{2}}{4}$ . This result differs from the classical Hoeffding's lemma by a multiplicative coefficient of $(1 + λ) / (1 - λ)$ , and simplifies to the latter when $λ = 0$ . The counterpart of Hoeffding's inequality for Markov chains immediately follows. Our results assume none of countable state space, reversibility and time-homogeneity of Markov chains and cover time-dependent functions with various ranges. We illustrate the utility of these results by applying them to six problems in statistics and machine learning.

Hoeffding's lemma for Markov Chains and its applications to statistical learning

Abstract

References in corpus (5)

Cited by in corpus (7)