Deep Learning for Computing Convergence Rates of Markov Chains

We sincerely thank you for your detailed feedback. In the following, we address the concerns (W1-4) and answer the questions (Q1-4).

W1. In Section 2, we only introduce necessary analytical concepts (e.g., random mapping representation, local Lipschitz constant, and contractive drift) to quickly set up for building the computational framework. In retrospect, we agree that we should add more background (e.g., Markov chains, stationary distributions, and traditional convergence analysis) to enhance the readability. This will be done in the revision.

Since DCDC is the first computational framework to bound the convergence of general state-space Markov chains, there are currently no other numerical methods available for direct comparison. Since analytical methods can only handle stylized (structured) Markov chains, the realistic (less structured) examples considered in this paper are clearly beyond their reach.

W2. Given a non-trivial Markov chain $X$, simulating $X_n$ for large $n$ is often very expensive, simulating $X_\infty$ directly is typically not feasible, and the convergence rate ($r<1$ with $C>0$ such that $W(X_n,X_\infty)\leq Cr^n$) is determined by the infinite sequence $W(X_0,X_\infty)$, $W(X_1,X_\infty)$, …. These three reasons make it impossible to reliably estimate the convergence rate via direct simulation in finite time. Now we have DCDC to generate a convergence bound $W(X_n,X_\infty)\leq Cr^n$, the correctness of which is theoretically guaranteed, so it is not necessary to verify the bound by estimating $W(X_n,X_\infty)$. Although estimating $W(X_n,X_\infty)$ can reveal whether the above bound is tight, it is often impractical due to the first two reasons mentioned earlier. In particular, for the examples in this paper, $X_\infty$ is unknown. In fact, complex dynamics + intractable equilibrium = notoriously hard convergence analysis (without DCDC).

W3. We plan to apply DCDC to high-dimensional chains in future work. In the current paper, we focus on 2D examples to verify the effectiveness, visualize the CDE solution, and gain valuable insights from the shape (e.g., a sunken surface, a sloping plane, and a wedge-like curve).

W4. The pointwise verification of an equality/inequality in a high dimensional space is indeed a fundamental issue. These issues, however, are common to other areas for which NN solvers of functional equations have demonstrated huge success [5]. For instance, Neural-network-based PDE solvers also face this same issue. While the sample complexity literature typically uses an L2-based criterion (based on suitable Sobolev norms), see, e.g., [6], typical applications often require approximations of PDE solution with uniform convergence guarantees on a specific set of points. While we expect dimension-dependent complexity rates as in the PDE literature, we note that our task is easier because we only need to prove an inequality, not an equality. However, given the successful record and vast literature of PINNs, we believe that our method can be at least equally successful in a wide range of settings and we plan to pursue a sharp sample complexity theory similar to that developed in the PDE literature in future research.

Q1. There are two primary classes of methods to bound the convergence of Markov chains: drift & minorization/contraction conditions (Chapter 9-20 of [2]) and spectral/operator theory (Chapter 22 of [2]). Poincare and log-sobolev inequalities belong to the latter while CD in [1] advances the former. “The former have been the most successful for the study of stability and convergence rates, despite the inherent difficulty of constructing an appropriate Lyapunov function” [3]. DCDC leverages deep learning to tackle this inherent difficulty (and more).

Q2. When $U$ is a constant, the constant is theoretically not important as CD is linear in $V$. However, in practice, we can use this constant to control the scale of $V$. In the SGD example, $KV=V-1$ leads to $\max V\approx1000$, so we use $0.1$ to scale $V$ down, which turns out to be easier to learn/approximate.

When $U$ is not a constant, it modifies the underlying metric (Section 2 of [1]). When a chain is expansive ($d(f(x),f(y))>d(x,y)$), we may find $U$ to make it non-expansive ($d_U(f(x),f(y))\leq d_U(x,y)$). The examples in this paper are already non-expansive, so we set $U$ to be constant. The application of DCDC to expansive chains is left for future research where sequential CDE solving (Section 3.4) becomes crucial.

Q3. In this paper, the infimum and supremum are computed over a mesh grid. The error can be controlled if the Lipschitz constant of the neural network is estimated (e.g., [4]).

Q4. Given $U$, $V$ is an expected discounted cumulative reward (Remark in Section 2), so it always exists but can be infinite. When $V=\infty$, the neural network in DCDC diverges to infinity. When it does not diverge to infinity, the training is successful if we verify the CDE.

[1] Qu, Y., Blanchet, J., Glynn, P., “Computable bounds on Convergence of Markov chains in Wasserstein distance”, 2023

[2] Andrieu, C., Lee, A., Power, S., Wang, A.Q., “Comparison of Markov chains via weak Poincare inequalities with application to pseudo-marginal MCMC”, 2022

[3] Douc, R., Moulines, E., Priouret, P., Soulier, P., “Markov Chains”, 2018

[4] Scaman, K., Virmaux, A., “Lipschitz regularity of deep neural networks: analysis and efficient estimation”, 2018

[5] Raissi, M., Perdikaris, P., Karniadakis, G.E., “Physics-informed neural networks: A deep learning framework for solving forward and inverse problems involving nonlinear partial differential equations”, 2018

[6] Lu, Y., Blanchet, J., Ying, L., “Sobolev Acceleration and Statistical Optimality for Learning Elliptic Equations via Gradient Descent”, 2021

We sincerely thank you for your positive feedback. Please feel free to read the other rebuttals.

We thank you for your valuable feedback and positive view about our paper. In the following, we address the concerns (1-4) and answer the questions (1-6).

1&4 Computational and Sample Complexity: The computational complexity, as with any typical deep learning method involving general non-convex optimization, is largely an open problem. There are, however, recent results for regularized ReLU architectures which can be studied to global convergence using convex relaxations (see [1]). We are interested in exploring the applications of these results in future work. We believe that we can use the parameter $\epsilon$ to control the complexity of these convex relaxations relative to the inequality-gap in the CD bound induced in terms of the parameter $\epsilon$. It is important to keep in mind (as we mention in the paper) that our task is simpler than finding an exact solution, because we care about a one-sided inequality. In terms of sample complexity, the curse of dimensionality is also, unfortunately, an issue that plagues virtually any algorithm that learns a function by sampling [2]. Our goal in this paper is to introduce a novel methodology (the first of its type) that enables the use of deep learning to address this important problem, but we admit that obtaining sharp sample complexity bounds is an important problem that we are also leaving for future research. We envision a sample complexity theory that depends on $\epsilon$ in such a way that as $\epsilon$ is small we recover the sample complexity guarantees that are expected if we know that the CDE is similar to the analysis in [3]. We also leave this important topic for future research.

2 Comparison with Existing Methods: We are not aware of other data driven computational frameworks to bound the convergence of general state-space Markov chains. Since analytical methods can only handle stylized (structured) Markov chains, the realistic (less structured) examples considered in this paper are clearly beyond the reach of the existing methods (which are based on analytical developments that are not “automatic” or computer based). We can provide a discussion, however, between CD and other existing methods to build the inequalities per-se, this discussion will summarize the comparison presented in [4].

3 Generality: Markov chains find important applications in a wide range of disciplines (including Computer Science, Economics, Electrical Engineering, Management Science, Operations Research etc.). We use non-trivial examples in Operations Research (e.g., queueing networks) and Machine Learning (e.g., stochastic gradient descent) to illustrate the applicability of the method. For complex Markov chains (e.g., reflected Brownian motions) in high dimensional spaces, one challenge is that contraction may occur along some but not all directions (e.g., $|\partial f/\partial x_1|<1$ or $|\partial f/\partial x_2|<1$ but not both), resulting in a local Lipschitz constant of one. In our ongoing work, we will introduce vector-valued CDs to address this issue.

5 Practical Applications: Thanks for this important question. Regarding the application to stochastic optimization, while we include an SGD example, admittedly this is just to show-case the applicability of the method. While the example that we provide already saturates what can be done with “standard methods” (which again, virtually all involve pen-and-paper approaches) we recognize that a broader ablation is needed to fully understand the potential of this approach. For the application to reinforcement learning, note that typical results mostly focus on finite state spaces using assumptions that are rather difficult to verify in general state spaces. Our methods open up the development of algorithms that satisfy CD type conditions. We will also mention this in the camera ready version

6 Assumptions and Limitations: The current paper focuses on compact spaces. The extension to non-compact spaces is left for future research. On compact spaces, the key assumption is CD itself (i.e., CD has a solution). As discussed at the end of Section 2, the CDE solution is an expected discounted cumulative reward, so it exists but can be infinite. When it is infinite, the chain has too little contraction to converge in Wasserstein distance. In this case, the neural network in DCDC diverges to infinity, which can be viewed as a certificate of non-convergence.

[1] Ergen, T., Pilanci, M., “Global optimality beyond two layers: Training deep ReLU networks via convex programs”, 2021

[2] Raissi, M., Perdikaris, P., Karniadakis, G.E., “Physics-informed neural networks: A deep learning framework for solving forward and inverse problems involving nonlinear partial differential equations”, 2018

[3] Lu, Y., Blanchet, J., Ying, L., “Sobolev Acceleration and Statistical Optimality for Learning Elliptic Equations via Gradient Descent”, 2021

[4] Qu, Y., Blanchet, J., Glynn, P., “Computable bounds on Convergence of Markov chains in Wasserstein distance”, 2023