Convergence rate analysis for general state-space Markov chains is fundamentally important in areas such as Markov chain Monte Carlo and algorithmic analysis (for computing explicit convergence bounds). This problem, however, is notoriously difficult because traditional analytical methods often do not generate practically useful convergence bounds for realistic Markov chains. We propose the Deep Contractive Drift Calculator (DCDC), the first general-purpose sample-based algorithm for bounding the convergence of Markov chains to stationarity in Wasserstein distance. The DCDC has two components. First, inspired by the new convergence analysis framework in (Qu et.al, 2023), we introduce the Contractive Drift Equation (CDE), the solution of which leads to an explicit convergence bound. Second, we develop an efficient neural-network-based CDE solver. Equipped with these two components, DCDC solves the CDE and converts the solution into a convergence bound. We analyze the sample complexity of the algorithm and further demonstrate the effectiveness of the DCDC by generating convergence bounds for realistic Markov chains arising from stochastic processing networks as well as constant step-size stochastic optimization.

我们提出了深度收敛漂移计算器（DCDC），这是第一个用于以Wasserstein距离界定马尔可夫链收敛性的通用样本算法。DCDC包括两个部分，首先，我们引入了压缩漂移方程（CDE）的解，从而得到了明确的收敛界限；其次，我们开发了一种高效的基于神经网络的CDE求解器。通过这两个组成部分，DCDC解决了CDE并将解转换为收敛界限。我们分析了算法的样本复杂度，并通过生成收敛界限来验证DCDC的有效性，这些收敛界限适用于来自随机处理网络以及常数步长随机优化的实际马尔可夫链。

深度学习计算马尔可夫链的收敛速率