Machine Learning Seminar

Machine Learning Seminar

Geoffrey Wolfer


Ben-Gurion University

Estimating the Mixing Time of Ergodic Markov Chains

We address the problem of estimating the mixing time tmix of an arbitrary ergodic finite Markov chain from a single trajectory of length m. The reversible case was addressed by Hsu et al. [2017], who left the general case as an open problem. In the reversible case, the analysis is greatly facilitated by the fact that the Markov operator is self-adjoint, and Weyl's inequality allows for a dimension-free perturbation analysis of the empirical eigenvalues. As Hsu et al. point out, in the absence of reversibility (and hence, the non-symmetry of the pair probabilities matrix), the existing perturbation analysis has a worst-case exponential dependence on the number of states d. Furthermore, even if an eigenvalue perturbation analysis with better dependence on d were available, in the non-reversible case the connection between the spectral gap and the mixing time is not nearly as straightforward as in the reversible case. Our key insight is to estimate the pseudo-spectral gap instead, which allows us to overcome the loss of self-adjointness and to achieve a polynomial dependence on d and the minimal stationary probability π⋆. Additionally, in the reversible case, we obtain simultaneous nearly (up to logarithmic factors) minimax rates in tmix and precision ε, closing a gap in Hsu et al., who treated ε as constant in the lower bounds. Finally, we construct fully empirical confidence intervals for the pseudo-spectral gap, which shrink to zero at a rate of roughly √(1/m), and improve the state of the art in even the reversible case.

Date: Wed 12 Jun 2019

Start Time: 10:30

End Time: 11:30

1061 | Electrical Eng. Building