English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

We prove a Chernoff-type bound for sums of matrix-valued random variablessampled via a regular (aperiodic and irreducible) finite Markov chain.Specially, consider a random walk on a regular Markov chain and a Hermitianmatrix-valued function on its state space. Our result gives exponentiallydecreasing bounds on the tail distributions of the extreme eigenvalues of thesample mean matrix. Our proof is based on the matrix expander (regularundirected graph) Chernoff bound [Garg et al. STOC '18] and scalarChernoff-Hoeffding bounds for Markov chains [Chung et al. STACS '12].  Our matrix Chernoff bound for Markov chains can be applied to analyze thebehavior of co-occurrence statistics for sequential data, which have beencommon and important data signals in machine learning. We show that given aregular Markov chain with $n$ states and mixing time $\tau$, we need atrajectory of length $O(\tau (\log{(n)}+\log{(\tau)})/\epsilon^2)$ to achievean estimator of the co-occurrence matrix with error bound $\epsilon$. Weconduct several experiments and the experimental results are consistent withthe exponentially fast convergence rate from theoretical analysis. Our resultgives the first bound on the convergence rate of the co-occurrence matrix andthe first sample complexity analysis in graph representation learning.

A Matrix Chernoff Bound for Markov Chains and Its Application to Co-occurrence Matrices