




















We establish Chernoff-type bounds for the largest eigenvalue of sums of Hermitian random matrices generated by a time-inhomogeneous Markov chain. Our primary regime assumes a compact state space and contractivity of each Markov kernel in Wasserstein distance, i.e., positive Ollivier-Ricci curvature. This assumption is convenient to verify in inhomogeneous settings and is satisfied by several chains of practical interest, such as stochastic gradient descent on strongly convex smooth objectives. We also develop analogous bounds for noncompact state spaces under a notion of spectral gap for inhomogeneous chains introduced by Saloff-Coste and Zuniga. Finally, we illustrate the utility of our results through an analysis of the Elo rating system, a popular method for ranking players in sports analytics, under a dynamic version of the Bradley-Terry-Luce model.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。