A Matrix Chernoff Bound for Markov Chains and Its Application to Co-Occurrence Matrices
Abstract
We prove a Chernoff-type bound for sums of matrix-valued random variables sampled via a regular (aperiodic and irreducible) finite Markov chain. Specially, consider a random walk on a regular Markov chain and a Hermitian matrix-valued function on its state space. Our result gives exponentially decreasing bounds on the tail distributions of the extreme eigenvalues of the sample mean matrix. Our proof is based on the matrix expander (regular undirected graph) Chernoff bound [Garg et al. STOC '18] and scalar Chernoff-Hoeffding bounds for Markov chains [Chung et al. STACS '12].
Cite
Text
Qiu et al. "A Matrix Chernoff Bound for Markov Chains and Its Application to Co-Occurrence Matrices." Neural Information Processing Systems, 2020.Markdown
[Qiu et al. "A Matrix Chernoff Bound for Markov Chains and Its Application to Co-Occurrence Matrices." Neural Information Processing Systems, 2020.](https://mlanthology.org/neurips/2020/qiu2020neurips-matrix/)BibTeX
@inproceedings{qiu2020neurips-matrix,
title = {{A Matrix Chernoff Bound for Markov Chains and Its Application to Co-Occurrence Matrices}},
author = {Qiu, Jiezhong and Wang, Chi and Liao, Ben and Peng, Richard and Tang, Jie},
booktitle = {Neural Information Processing Systems},
year = {2020},
url = {https://mlanthology.org/neurips/2020/qiu2020neurips-matrix/}
}