We introduce a unified operator-theoretic framework for analyzing mixing times of finite-state ergodic Markov chains that applies to both reversible and non-reversible dynamics. The central object in our analysis is the projected transition operator $PU_{\perp 1}$, where $P$ is the transition kernel and $U_{\perp 1}$ is orthogonal projection onto mean-zero subspace in $\ell^{2}(π)$, where $π$ is the stationary distribution. We show that explicitly computable matrix norms of $(PU_{\perp 1})^k$ gives non-asymptotic mixing times/distance to stationarity, and bound autocorrelations at lag $k$. We establish, for the first time, submultiplicativity of pointwise chi-squared divergence in the general non-reversible case. We provide for all times $χ^{2}(k)$ bounds based on the spectrum of $PU_{\perp 1}$, i.e., magnitude of its distinct non-zero eigenvalues, discrepancy between their algebraic and geometric multiplicities, condition number of a similarity transform, and constant coming from smallest atom of stationary distribution(all scientifically computable). Furthermore, for diagonalizable $PU_{\perp 1}$, we provide explict constants satisfying hypocoercivity phenomenon for discrete time Markov Chains. Our framework enables direct computation of convergence bounds for challenging non-reversible chains, including momentum-based samplers for V-shaped distributions. We provide the sharpest known bounds for non-reversible walk on triangle. Our results combined with simple regression reveals a fundamental insight into momentum samplers: although for uniform distributions, $n\log{n}$ iterations suffice for $χ^{2}$ mixing, for V-shaped distributions they remain diffusive as $n^{1.969}\log{n^{1.956}}$ iterations are sufficient. The framework shows that for ergodic chains relaxation times $τ_{rel}=\|\sum_{k=0}^{\infty}P^{k}U_{\perp 1}\|_{\ell^{2}(π)}$.


翻译:我们引入了一个统一的算子理论框架,用于分析有限状态遍历马尔可夫链的混合时间,该框架适用于可逆与非可逆动力学。我们分析的核心对象是投影转移算子 $PU_{\\perp 1}$,其中 $P$ 是转移核,$U_{\\perp 1}$ 是在 $\\ell^{2}(\\pi)$ 空间上向均值为零的子空间的正交投影,$\\pi$ 是平稳分布。我们证明了 $(PU_{\\perp 1})^k$ 的可显式计算矩阵范数给出了非渐近的混合时间/到平稳分布的距离,并界定了滞后 $k$ 的自相关性。我们首次在一般非可逆情况下建立了逐点卡方散度的次可乘性。我们基于 $PU_{\\perp 1}$ 的谱(即其不同非零特征值的模、其代数重数与几何重数之间的差异、相似变换的条件数,以及来自平稳分布最小原子的常数——所有这些在科学上都是可计算的),为所有时间 $\\chi^{2}(k)$ 提供了界限。此外,对于可对角化的 $PU_{\\perp 1}$,我们提供了满足离散时间马尔可夫链亚强制现象的显式常数。我们的框架使得能够直接计算具有挑战性的非可逆链的收敛界限,包括用于V形分布的基于动量的采样器。我们为三角形上的非可逆游走提供了已知最尖锐的界限。我们的结果结合简单的回归揭示了对动量采样器的一个基本见解:虽然对于均匀分布,$n\\log{n}$ 次迭代足以实现 $\\chi^{2}$ 混合,但对于V形分布,它们仍然是扩散性的,因为 $n^{1.969}\\log{n^{1.956}}$ 次迭代就足够了。该框架表明,对于遍历链,弛豫时间 $\\tau_{rel}=\\|\\sum_{k=0}^{\\infty}P^{k}U_{\\perp 1}\\|_{\\ell^{2}(\\pi)}$。

0
下载
关闭预览

相关内容

FlowQA: Grasping Flow in History for Conversational Machine Comprehension
专知会员服务
34+阅读 · 2019年10月18日
Stabilizing Transformers for Reinforcement Learning
专知会员服务
60+阅读 · 2019年10月17日
Transferring Knowledge across Learning Processes
CreateAMind
29+阅读 · 2019年5月18日
Unsupervised Learning via Meta-Learning
CreateAMind
43+阅读 · 2019年1月3日
STRCF for Visual Object Tracking
统计学习与视觉计算组
15+阅读 · 2018年5月29日
Focal Loss for Dense Object Detection
统计学习与视觉计算组
12+阅读 · 2018年3月15日
IJCAI | Cascade Dynamics Modeling with Attention-based RNN
KingsGarden
13+阅读 · 2017年7月16日
国家自然科学基金
13+阅读 · 2017年12月31日
国家自然科学基金
2+阅读 · 2015年12月31日
国家自然科学基金
2+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2014年12月31日
国家自然科学基金
2+阅读 · 2014年12月31日
VIP会员
相关资讯
Transferring Knowledge across Learning Processes
CreateAMind
29+阅读 · 2019年5月18日
Unsupervised Learning via Meta-Learning
CreateAMind
43+阅读 · 2019年1月3日
STRCF for Visual Object Tracking
统计学习与视觉计算组
15+阅读 · 2018年5月29日
Focal Loss for Dense Object Detection
统计学习与视觉计算组
12+阅读 · 2018年3月15日
IJCAI | Cascade Dynamics Modeling with Attention-based RNN
KingsGarden
13+阅读 · 2017年7月16日
相关基金
国家自然科学基金
13+阅读 · 2017年12月31日
国家自然科学基金
2+阅读 · 2015年12月31日
国家自然科学基金
2+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2014年12月31日
国家自然科学基金
2+阅读 · 2014年12月31日
Top
微信扫码咨询专知VIP会员