论文标题
矩阵切尔诺夫（Chernoff
A Matrix Chernoff Bound for Markov Chains and Its Application to Co-occurrence Matrices
论文作者
论文摘要
我们证明了Chernoff型绑定，用于通过常规（Aperiodic和不可还原）有限的Markov链采样的矩阵值随机变量的总和。特别是，请考虑在常规马尔可夫链上进行随机步行，并在其状态空间上进行Hermitian矩阵值。我们的结果给出了样品平均矩阵极端特征值的尾部分布的指数减小。我们的证明是基于矩阵扩展器（常规无向图）Chernoff Bond [Garg等。 Markov链的STOC '18]和标量Chernoff-Hoeffding边界[Chung等。 Stacs '12]。 我们的矩阵Chernoff绑定了马尔可夫连锁店的限制，可以分析连续数据的共发生统计数据的行为，这些数据是机器学习中常见且重要的数据信号。我们表明，鉴于带有$ n $状态的普通马尔可夫链和混合时间$τ$，我们需要长度$ o（τ（\ log {（n）}+log {（τ）}）/ε^2）$的轨迹，以实现与误差限制$ $ε$的共发生矩阵的估计器。我们进行了几项实验，实验结果与理论分析的指数快速收敛率一致。我们的结果给出了第一个结合了共发生矩阵的收敛速率和图表学习中的第一个样本复杂性分析。
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]. Our matrix Chernoff bound for Markov chains can be applied to analyze the behavior of co-occurrence statistics for sequential data, which have been common and important data signals in machine learning. We show that given a regular Markov chain with $n$ states and mixing time $τ$, we need a trajectory of length $O(τ(\log{(n)}+\log{(τ)})/ε^2)$ to achieve an estimator of the co-occurrence matrix with error bound $ε$. We conduct several experiments and the experimental results are consistent with the exponentially fast convergence rate from theoretical analysis. Our result gives the first bound on the convergence rate of the co-occurrence matrix and the first sample complexity analysis in graph representation learning.
